text: We consider the problem of near-optimal arm identification in the fixed confidence setting of the infinitely armed bandit problem when nothing is known about the arm reservoir distribution. We (1) introduce a PAC-like framework within which to derive and cast results; (2) derive a sample complexity lower bound for near-optimal arm identification; (3) propose an algorithm that identifies a nearly-optimal arm with high probability and derive an upper bound on its sample complexity which is within a log factor of our lower bound; and (4) discuss whether our log^2(1 delta) dependence is inescapable for "two-phase" (select arms first, identify the best later) algorithms in the infinite setting. This work permits the application of bandit models to a broader class of problems where fewer assumptions hold.
  @cite_11: This paper describes the architecture and results of the TALP system presented at the SENSEVAL-2 exercise for the English lexical--sample task. This system is based on the LazyBoosting algorithm for Word Sense Disambiguation (, 2000), and incorporates some improvements and adaptations to this task. The evaluation reported here includes an analysis of the contribution of each component to the overall system performance.
summary: Regret minimization has been studied extensively for infinite bandit models , whereas @cite_11 is the first work dealing with pure-exploration for general reservoirs. The authors consider the fixed-budget setting, under the tail assumption for the reservoir distribution, already discussed.