Minimax Policies for Adversarial and Stochastic Bandits

By Jean-Yves Audibert, Sébastien Bubeck. 2009

486 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Reinforcement Learning

Citations in the corpus

On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization (2012, background): “An important exception is multi-armed bandits, where the attainable error/regret is known to be exactly Θ( √ d/T ), where d is the dimension and T is the number of queries1 Auer et al. (2002); Audibert and Bubeck (2009).”
Variational Bayesian Reinforcement Learning with Regret Bounds (2018, methodology): “ior distribution. Many algorithms exist that achieve low regret for bandits, see the survey [19], in particular the MOSS algorithm is known to achieve the optimal regret lower bound, up to constants, [5]. In the Bayesian case Thompson sampling also achieves close to the regret bound [87, 88], as doe”
Introduction to Online Convex Optimization (2016, background): “The logarithmic gap in attainable regret for non-stochastic MAB was resolved in (12).”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “[2010], Audibert et al. [2011]. The presentation adopted in this section is based on the last paper. OSMD with negative entropy was first studied by Helmbold and Warmuth [2009] for the full information setting and for a specific set C.”
Learning to Optimize via Posterior Sampling (2013, methodology): “Bubeck and Liu [12] combine the regret decomposition we derive in §5 with the confidence bound analysis of Audibert and Bubeck [8] to tighten the bound provided in §6.”
Accurate Inference for Adaptive Linear Models (2017, background): “r’s policy. For instance, ‘regret’ in sequential decision-making or risk in active learning are intimately connected with the accurate estimation of the underlying parameters [Castro and Nowak, 2008, Audibert and Bubeck, 2009, Bubeck et al., 2012, Rusmevichientong and Tsitsiklis, 2010] . Our motivat”
Multi-armed bandits with episode context (2011, methodology): “We also discuss methods for obtaining suitable predictors for use with PUCB.”
A Survey of Monte Carlo Tree Search Methods (2012, background): “TDL can learn heuristic value functions to inform the tree policy or the simulation (playout) policy.”
Bandit Algorithms (2020, methodology): “The UCRL algorithm and the upper and lower regret analysis is due to Auer et al. [2009], Jaksch et al. [2010]. Our proofs differ in minor ways.”
Near-Optimal Regret Bounds for Thompson Sampling (2017, methodology): “More recently, Audibert and Bubeck (2009) gave an algorithm MOSS, inspired by UCB1, with regret O ( √ NT ) that matches the Ω( √ NT ) problem-independent lower bound for the multiarmed bandit problem.”
The K-armed Dueling Bandits Problem (2012, background): “For conventional bandit problems, in every iteration, each bandit receives a real-valued payoff in [0,1], initially unknown to the algorithm.”
Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms (2014, methodology): “For the classical MAB setting with ω = 1 and p = 1, we obtain a distribution-independent bound of O( √ mn lnn), which matches (up to a logarithmic factor) the original UCB1 algorithm (Audibert et al., 2009).”
Learning to Optimize via Information-Directed Sampling (2014, background): “t(a)}log(t)/N t(a), whereV t(a) isanupperboundonthevarianceoftherewarddistributionatactiona. Whilethis methoddramaticallyoutperformsUCB1,itisstilloutperformedbyIDS.TheMOSSalgorithmof AudibertandBubeck[7]issimilartoUCB1andUCB–Tuned,butusesslightlydiﬀerentconﬁdence bounds. It is known to satisfy regre”
Stochastic matrix games with bandit feedback (2020, background): “The main threads are (a) using the online convex optimisation view and modifying the regularizer [2, 10, 42], for example, and (b) modifying the loss estimates to obtain high probability regret or adaptive bounds [5, 20, 26, 1].”
Combinatorial Bandits (2012, background): “(We refer to Audibert and Bubeck [11] for recent improvements of this result.”