Pure exploration in finitely-armed and continuous-armed bandits

By Sébastien Bubeck, R´emi Munos, Gilles Stoltz. 2011

284 citations recorded by the source corpus.

We consider the framework of stochastic multi-armed bandit problems and study the possibilities and limitations of forecasters that perform an on-line exploration of the arms. These forecasters are assessed in terms of their simple regret, a regret notion that captures the fact that exploration is only constrained by the number of available rounds (not necessarily known in advance), in contrast to the case when the cumulative regret is considered and when exploitation needs to be performed at the same time. We believe that this performance criterion is suited to situations when the cost of pulling an arm is expressed in terms of resources rather than rewards. We discuss the links between the simple and the cumulative regret. One of the main results in the case of a finite number of arms is a general lower bound on the simple regret of a forecaster in terms of its cumulative regret: the smaller the latter, the larger the former. Keeping this result in mind, we then exhibit upper bounds on the simple regret of some forecasters. The paper ends with a study devoted to continuous-armed bandit problems; we show that the simple regret can be minimized with respect to a family of probability distributions if and only if the cumulative regret can be minimized for it. Based on this equivalence, we are able to prove that the separable metric spaces are exactly the metric spaces on which these regrets can be minimized with respect to the family of all probability distributions with continuous mean-payoff functions.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning, Statistical Learning Theory

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 Management Science and Operations Research

In Reinforcement Learning

In Statistical Learning Theory

Citations in the corpus

On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models (2014, background): “The ﬁxed-budget setting has been studied by Audibert et al. (2010); Bubeck et al. (2011) for single best-arm identiﬁcation in bounded bandit models.”
Active Reinforcement Learning: Observing Rewards at a Cost (2020, background): “But there is a trade-off between simple regret and cumulative regret (Bubeck et al., 2011, Thm. 1): if the cumulative regret is small, then there is a lower bound on the simple regret.”
An Introduction to Deep Reinforcement Learning (2018, unknown): “1This term is mainly used in the bandit community where the agent is in only one state and where a distribution of rewards is associated to each action; see e.g., Bubeck et al., 2011.”
Improved empirical methods in reinforcement-learning evaluation (2015, unknown): “, 2013) as well as multi-armed bandits (Bubeck et al., 2011; Weinstein, 2014).”
Preference-based Online Learning with Dueling Bandits: A Survey (2018, background): “hen-exploit” algorithms. 1. Here, we consider the pure exploration setup with ﬁxed conﬁdence. Alternatively, one can ﬁx the horizon and control the error of the recommendation (Audibert et al., 2010; Bubeck et al., 2011, 2013). 6 Preference-based OnlineLearning with DuelingBandits: A Survey Such alg”
Blind Search for Atari-Like Online Planning Revisited (2016, methodology): “…games: First, while the UCB procedure is opti- mized for the learning-while-acting settings of MAB, the simple uniform and round-robin sampling of the actions provide much better formal and empirical guarantees when it comes to online action selection with MAB simulators [Bubeck et al., 2011].”
A Survey of Preference-Based Online Learning with Bandit Algorithms (2014, background): “Alternatively, one can fix the horizon and control the error of the recommendation [4, 8, 9]”
Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism (2021, background): “Contrary to UCB that achieves optimal regret in multi-armed bandits [52], LCB is provably not adaptively optimal for solving offline bandit problems under the C framework.”
Machine learning applications in drug development (2019, background): “An interesting take-out from the bandit literature is that the two objectives of treatment identification and curing patients cannot be achieved (optimally) by the same allocation strategy [74].”
Generic Exploration and K-armed Voting Bandits (2013, methodology): “We can also reverse the PAC question to control the prediction accuracy after a fixed number of samples as in (Audibert et al., 2010; Bubeck et al., 2011).”