Finite-time Analysis of the Multiarmed Bandit Problem

By Peter Auer, Nicolò Cesa-Bianchi, P. Fischer. 2002

7,574 citations recorded by the source corpus.

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

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

Citations in the corpus

Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, background): “Dueling bandits generalizes the standard multi-armed bandit (MAB) (Auer et al., 2002).”
Deep Reinforcement Learning with Double Q-Learning (2015, background): “The overestimations should not be confused with optimism in the face of uncertainty (Sutton, 1990; Agrawal, 1995; Kaelbling et al., 1996; Auer et al., 2002; Brafman and Tennenholtz, 2003; Szita and Lőrincz, 2008; Strehl et al., 2009), where an exploration bonus is given to states or actions with unc”
Recurrent Environment Simulators (2017, background): “Various solutions have been proposed, such as density based or optimistic exploration (Auer et al., 2002). Oh et al. (2015) considered a memory-based approach that steers the agent towards previously unobserved frames.”
Beyond Individual and Group Fairness (2020, methodology): “Our algorithm is similar to the UCB algorithm for multi-armed bandits Auer et al. [2002] and maintains optimistic estimates of the parameters.”
Auto-Keras: An Efficient Neural Architecture Search System (2018, background): “Upper-confidence bound (UCB) [1] is selected as our acquisition”
Learning to reinforcement learn (2016, background): “As shown in Figure 2a (green line; “Independent”), meta-RL outperforms both Thompson sampling (gray dashed line) and UCB (light gray dashed line), although it performs less well compared to Gittins (black dashed line).”
Balanced Linear Contextual Bandits (2018, methodology): “(For some results, e.g., (Auer 2002), α needs to be slowly increasing in t .)”
Estimation Considerations in Contextual Bandits (2017, methodology): “Thompson sampling [61, 55, 5, 52] and upper confidence bound (UCB) [40, 12] are two different methods for assigning contexts to arms which are highly effective in dealing with the exploration-exploitation trade-off.”
A contextual-bandit approach to personalized news article recommendation (2010, methodology): “In contrast to theunguidedexploration strategy adopted by ǫgreedy, another class of algorithms generally known as upper confidence bound algorithms [4, 7, 17] use a smarter way to balanc e exploration and exploitation.”
Information-Theoretic Considerations in Batch Reinforcement Learning (2019, neutral): “…the problem is equivalent to the hard instances of best arm identiﬁcation with |A| H arms, so even if an algorithm can perform active exploration, the sample complexity is still Ω( H ln(1 /δ ) /ǫ 2 ) (see Krishnamurthy et al. (2016) for details, who use standard techniques from Auer et al. (2002)).”
Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms (2010, background): “In contrast, another class of algorithms generally known as “upper conﬁdence bound” algorithms [16, 5] use a smarter way to balance exploration and exploitation.”
Fairness in Learning: Classic and Contextual Bandits (2016, methodology): “Without a fairness constraint, it is known that it is possible to guarantee non-trivial regret to the optimal policy after only T = O ( k ) many rounds [Auer et al., 2002].”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “[23] show that this algorithm performs well in practice, but the performance degrades quickly if d is not chosen as a tight lower bound of mini =i∗ ∆i.”
PAC Bounds for Discounted MDPs (2012, methodology): “We modify the Upper Confidence Reinforcement Learning (UCRL) algorithm of Auer et al. (2010); Auer (2011); Strehl and Littman (2008) and, under the assumption that there are at most two possible next-states for each state/action pair, prove a PAC bound of”