Tuning Bandit Algorithms in Stochastic Environments

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

229 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

Counterfactual reasoning and learning systems: the example of computational advertising (2012, methodology): “In order to maximize the accumulated rewards, the player must construct policies π that balance the exploration of the action space with the exploitation of the best action identified so far (Auer et al., 2002; Audibert et al., 2007; Seldin et al., 2012).”
Bandit Algorithms (2020, methodology): “S by Auer et al. [2002b]. This algorithm can be interpretted as an efficient version of Exp4 with a carefully chosen initialization such that the exponential computation over all experts collapses into a simple expression.”
Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning (2018, methodology): “We use confidence intervals constructed using empirical Bernstein’s inequality (Audibert et al., 2007; Maurer and Pontil, 2009) βsar,k := √ 14σ̂2r,k(s, a)bk,δ max{1, Nk(s, a)} + 49 3 rmaxbk,δ max{1, Nk(s, a)− 1} , βsas ′ p,k := √ 14σ̂2p,k(s ′|s, a)bk,δ max{1, Nk(s, a)} + 49 3 bk,δ max{1, Nk(s, a)−…”
On Upper-Confidence Bound Policies for Switching Bandit Problems (2011, background): “More recently, finite-time bounds for the regret and improvements have been derived (see [5, 2, 16]), but those improvements do not address the issue of non-stationarity.”
Preference-based Evolutionary Direct Policy Search (2013, background): “Therefore, it is not clear how Bernstein-like bounds [4], where the empirical variance estimate is used in the concentration inequality, could be applied.”
Simple regret for infinitely many armed bandits (2015, background): “UCB-F is designed for ﬁxed horizon of n evaluations and it is an extension of a version of UCB-V by Audibert et al. (2007).”
Policy Search in a Space of Simple Closed-form Formulas: Towards Interpretability of Reinforcement Learning (2012, methodology): “Multi-armed bandit problems have been vastly studied, and several algorithms have been proposed, such as for instance all UCB-type algorithms [3, 2].”
On Upper-Confidence Bound Policies for Non-Stationary Bandit Problems (2008, background): “More recently, ﬁnite-time bounds for the regret have been derived (see Auer et al. (2002); Audibert et al. (2007)).”
Empirical Bernstein stopping (2008, methodology): “Nevertheless, the following result due to Audibert et al. (2007b) can be used to test the stopping condition after each sample without sacriﬁcing the advantages of geometric sampling.”
Preference-based reinforcement learning: evolutionary direct policy search using a preference-based racing algorithm (2014, background): “…as proposed by [16]: A more serious problem caused by incomparability is a complication of the variance estimation for S ( X , Y ) [16]. b Therefore, it is not clear how Bernstein-like bounds [4], where the empirical variance estimate is used in the concentration inequality, could be applied.”
Variance Penalizing AdaBoost (2011, unknown): “Significant performance gains are obtained over AdaBoost for arbitrary weak learners including decision trees (CART).”
Estimating means of bounded random variables by betting (2020, methodology): “[7], which outperform Hoeffding’s method for low-variance distributions at large sample sizes by data-dependently estimating the variance.”
Solving two-armed Bernoulli bandit problems using a Bayesian learning automaton (2010, result): “This confirms the observations from Audibert et al. (2007) where the high variance of UCB-tuned was first reported.”