Exploration-exploitation tradeoff using variance estimates in multi-armed bandits

By Jean-Yves Audibert, R´emi Munos, Csaba Szepesvari. 2009

698 citations recorded by the source corpus.

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

Model-based reinforcement learning with parametrized physical models and optimism-driven exploration (2015, background): “In the case of linear dynamics or discrete systems, this optimistic exploration scheme has a number of desirable theoretical properties that make it a good choice [1], [3], [4], [7].”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “The weakness of this result is that the second term in the above equation only depends on the smallest gap ∆.”
Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning (2017, neutral): “PAC: [2, 3, 4, 5], (uniform) high-probability regret: [6, 7, 8]; expected regret: [9, 10, 11, 12]).”
Thompson Sampling: An Asymptotically Optimal Finite-Time Analysis (2012, methodology): “[4] was the first of a series of efficient policies, like UCB-V [3] or MOSS [2], for which good regret bounds in finite time were also provided.”
Towards scaling up Markov chain Monte Carlo: an adaptive subsampling approach (2014, background): “If the empirical standard deviation σ̂t of {log p(xi|θ) − log p(xi|θ)} is small, a tighter bound known as the empirical Bernstein bound (Audibert et al., 2009)”
Generic Exploration and K-armed Voting Bandits (2013, methodology): “Following Lai & Robbins (1985), several regret analysis have been proposed (see for instance Auer et al., 2002; Audibert et al., 2008; Auer & Ortner, 2011).”
Online Clustering of Bandits (2014, methodology): “…with the need of exploring new content so as to globally improve users’ experience, generates a wellknown exploration-exploitation dilemma, which is commonly formalized as a multi-armed bandit problem (e.g., (Lai & Robbins, 1985; Auer et al., 2001; Audibert et al., 2009; Caron et al., 2012)).”
Concentration inequalities for sampling without replacement (2013, background): “However, Maurer and Pontil [12] and Audibert, Munos and Szepesvári [1] showed that, in the case of sampling with replacement, a careful use of self-bounded properties of the variance yields better bounds.”
Automatic ad format selection via contextual bandits (2013, methodology): “In this experiment, we apply a variant of the UCB1 algorithm, UCB1(ρ), which can be seen as a generalized UCB1 algorithm [2].”
Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem (2013, positive): “Recently reﬁned upper-conﬁdence bounds (such as UCB-V (Audibert et al., 2009) or KL-UCB (Capp´e et al., 2013)) have improved performance for the regular K -armed ban-dit problem.”
Time-uniform, nonparametric, nonasymptotic confidence sequences (2018, background): “Maurer and Pontil [50] and Audibert, Munos and Szepesvári [3] prove empirical-Bernstein bounds for fixed times or finite time horizons.”
From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning (2014, methodology): “[2008] consists of playing a UCB-V strategy [Audibert et al., 2009] (see (1.”
Tracking the Best Expert in Non-stationary Stochastic Environments (2017, methodology): “As we aim to achieve smaller regrets for distributions with smaller statistical variances, we adopt a variant of the UCB algorithm developed by [1], called UCB-V, which takes variances into account when building its conﬁdence interval.”
LEAPSANDBOUNDS: A Method for Approximately Optimal Algorithm Configuration (2018, background): “Thus, the lemma holds by the empirical Bernstein bound (cf. Audibert et al., 2009, Theorem 1 and Appendix A).”