UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problem

By Peter Auer, Ronald Ortner. Periodica Mathematica Hungarica, 2010

396 citations recorded by the source corpus.

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

View Paper: https://www.semanticscholar.org/paper/83c3e0371aa52d1ed6be3201b31f0233c0222f4c

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

Bounded Regret for Finite-Armed Structured Bandits (2014, background): “The improved UCB algo rithm [7] enjoys a bound on the expected regret of O( ∑”
Almost Optimal Exploration in Multi-Armed Bandits (2013, methodology): “…proceeds in rounds, where in round r it aims at eliminating (1/2)rsuboptimal arms2, i.e., arms i having ∆i > (1/2) r. 2A similar scheme was used by Auer & Ortner (2010) for improving the regret bound of the UCB algorithm with Since we do not know the suboptimality of each arm, we estimate it to…”
The multi-armed bandit problem with covariates (2011, background): “Such an improvement was recently attempted in [5] and also in [1] for modified UCB policies and we compare these results to ours below.”
Bandit Algorithms (2020, background): “An algorithm that does almost the same thing in disguise is called Improved UCB, which operates in phases and eliminates arms for which the upper confidence bound drops below a lower confidence bound for some arm [Auer and Ortner, 2010].”
Boltzmann Exploration Done Right (2017, methodology): “A variant of UCB using action elimination and due to Auer and Ortner (2010) has regret i> 1 log( T ∆ 2 i ) ∆ i corresponding to a KT (log K ) distribution-free bound.”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “In fact, the core idea is more transparent when expressed in terms of gains, and so we turn to the gain version of the problem.”
PAC-Bayes-Bernstein Inequality for Martingales and its Application to Multiarmed Bandits (2011, background): “…main goal is not improvement of existing bounds for stochastic multiarmed bandits, which are already tight up to √ ln(K) factors (Audibert and Bubeck, 2009; Auer and Ortner, 2010), but rather development of a new powerful tool for reinforcement learning and for other domains with richer structure.”