The Nonstochastic Multiarmed Bandit Problem

By Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, Robert E. Schapire. 2002

2,743 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

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).”
Contextual Dueling Bandits (2015, neutral): “Similar to prior work on contextual (non-dueling) bandits (Auer et al., 2002; Langford and Zhang, 2007; Dudı́k et al., 2011; Agarwal et al., 2014), we propose a setting in which the learner has access to a space of policies Π, with the goal of performing as well as the “best” in the space.”
Taking the Human Out of the Loop: A Review of Bayesian Optimization (2016, background): “Note that we are assuming stochastic feedback, in contrast to deterministic or adversarial feedback [9], [10].”
Doubly Robust Policy Evaluation and Optimization (2014, background): “Contextual bandits (Auer et al., 2002/03; Lang-ford and Zhang, 2008), sometimes known as asso-Miroslav Dud´ık is Senior Researcher and John Langford is Principal Researcher, Microsoft Research, New York, New York, USA (e-mail: mdudik@microsoft.com; jcl@microsoft.com).”
Doubly Robust Policy Evaluation and Learning (2011, methodology): “Furthermore, most of previous analysis of doubly robust estimation studies asymptotic behavior or relies on various modeling assumptions (e.g., Robins et al. (1994), Lunceford & Davidian (2004), and Kang & Schafer (2007)).”
Learning from Logged Implicit Exploration Data (2010, background): “a linear in X × A, which is extraordinarily wasteful. In essence, this is a failure to take advantage of generalization. 3. Contextual Bandits. Existing approaches to contextual bandits such as EXP4 (Auer et al., 2002) or Epoch Greedy (Langford & Zhang, 2008), require either interaction to gathe”
Automated Curriculum Learning for Neural Networks (2017, methodology): “Our goal is to use the policy output by Exp3.”
Off-policy evaluation for slate recommendation (2016, methodology): “We frame the slate recommendation problem as a combinatorial generalization of contextual bandits [3, 23, 13].”
A contextual-bandit approach to personalized news article recommendation (2010, methodology): “The EXP4 algorithm [8] uses the exponential weighting technique to achieve añ O( √ T ) regret, 2 but the computational complexity may be exponential in the number of fe atures.”
Variational Bayesian Reinforcement Learning with Regret Bounds (2018, background): “gorithms can discover this fact will determine their overall performance (this is not truly the adversarial setting, and we make no claim on the regret of K-learning under true adversarial conditions [7]). As we see K-learning is by far the quickest to respond and ultimately ends with negative regre”
Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms (2010, methodology): “…context x t , A chooses an arm a t ∈ A , and 1 In the literature, contextual bandits are sometimes called bandits with covariate [28], associative reinforcement learning [14], bandits with expert advice [6], bandits with side information [27], and associative bandits [25]. receives payoﬀ r t,a t .”
Non-stochastic Best Arm Identification and Hyperparameter Optimization (2015, methodology): “We include in our comparison the EXP3 algorithm (Auer et al., 2002), a popular approach for minimizing cumulative regret in the non-stochastic setting.”
Introduction to Online Convex Optimization (2016, background): “High probability bounds for the MAB problem were given in (13), and for bandit linear optimization in (5).”
Learning Where to Attend with Deep Architectures for Image Tracking (2011, background): “Both Hedge and EXP3 learn gaze selection policies which choose among a discrete set of predetermined ﬁxation points.”
Mapping Instructions and Visual Observations to Actions with Reinforcement Learning (2017, background): “This enables learning in a contextual bandit setting (Auer et al., 2002; Langford and Zhang, 2007), where optimizing the immediate reward is sufficient and has better sample complexity than unconstrained reinforcement learning (Agarwal et al.”
Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits (2014, methodology): “The strongest known results (Auer et al., 2002; McMahan and Streeter, 2009; Beygelzimer et al., 2011) provide algorithms that carefully control the exploration distribution to achieve an optimal regret after T rounds of O KT log( Π /δ ) , with probability at least 1 − δ , relative to a set of…”
Reinforcement and Imitation Learning via Interactive No-Regret Learning (2014, background): “The problem may be cast as a contextual bandit problem[2, 6] where features of the current state define the context of explorati on.”
Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation (2013, background): “For example, the standard multi-armed bandit lower bound [5] pertain to a setting where we can view a single coordinate of the loss vector, but doesn’t apply as-is when we can view more than one coordinate (e.”
AI Safety Gridworlds (2017, background): “Robustness to adversaries (Auer et al., 2002; Szegedy et al., 2013): How does an agent detect and adapt to friendly and adversarial intentions present in the environment? 8.”
Contextual Decision Processes with low Bellman rank are PAC-Learnable (2016, background): “Terminate the subroutine when t > HM (cid:48) log 6 H √ M (cid:48) ζ / log(5 / 3) in Line 4 (the for-loop).”