Simple regret for infinitely many armed bandits

By A. Carpentier, Michal Valko. 2015

95 citations recorded by the source corpus.

We consider a stochastic bandit problem with infinitely many arms. In this setting, the learner has no chance of trying all the arms even once and has to dedicate its limited number of samples only to a certain number of arms. All previous algorithms for this setting were designed for minimizing the cumulative regret of the learner. In this paper, we propose an algorithm aiming at minimizing the simple regret. As in the cumulative regret setting of infinitely many armed bandits, the rate of the simple regret will depend on a parameter β characterizing the distribution of the near-optimal arms. We prove that depending on β, our algorithm is minimax optimal either up to a multiplicative constant or up to a log(n) factor. We also provide extensions to several important cases: when β is unknown, in a natural setting where the near-optimal arms have a small variance, and in the case of unknown time horizon.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization (2016, methodology): “Relatedly, the stochastic pure-exploration inﬁnite-armed bandit problem was studied in Carpentier and Valko (2015), where a pull of each arm i yields an i.i.d. sample in [0 , 1] with expectation ν i , where ν i is a loss drawn from F .”
On Kernelized Multi-armed Bandits (2017, background): “An alternative line of work pertaining to X -armed bandits (Kleinberg et al., 2008; Bubeck et al., 2011; Carpentier and Valko, 2015; Azar et al., 2014) studies continuum-armed bandits with smoothness structure.”
The Power of Adaptivity in Identifying Statistical Alternatives (2016, background): “Previous work has focused on an alternative arm distribution reservoir that satisfies E✏  P(μ μ⇤ ✏)  E0✏ for some μ⇤ 2 [0, 1] where E,E0 are constants and is known [5, 21, 6, 7].”