Gambling in a rigged casino: The adversarial multi-armed bandit problem

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

In the multi-armed bandit problem, a gambler must decide which arm of K non-identical slot machines to play in a sequence of trials so as to maximize his reward. This classical problem has received much attention because of the simple model it provides of the trade-off between exploration (trying out each arm to find the best one) and exploitation (playing the arm believed to give the best payoff). Past solutions for the bandit problem have almost always relied on assumptions about the statistics of the slot machines. In this work, we make no statistical assumptions whatsoever about the nature of the process generating the payoffs of the slot machines. We give a solution to the bandit problem in which an adversary, rather than a well-behaved stochastic process, has complete control over the payoffs. In a sequence of T plays, we prove that the expected per-round payoff of our algorithm approaches that of the best arm at the rate O(T/sup -1/3/), and we give an improved rate of convergence when the best arm has fairly low payoff. We also consider a setting in which the player has a team of "experts" advising him on which arm to play; here, we give a strategy that will guarantee expected payoff close to that of the best expert. Finally, we apply our result to the problem of learning to play an unknown repeated matrix game against an all-powerful adversary.

Subfields: Reinforcement Learning, Game & Decision Theory

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

In Game & Decision Theory

Citations in the corpus

Survey on Automated Machine Learning (2019, background): “, T trials the following two steps are repeated (Auer et al., 1995):”
Taking the Human Out of the Loop: A Review of Bayesian Optimization (2016, methodology): “Algorithm 2 Thompson sampling for Beta-Bernoulli bandit Require: α, β : hyperparameters of the beta prior 1: Initialize n a, 0 = n a, 1 = i = 0 for all a 2: repeat 3: for a = 1 , . . . , K do 4: ˜ w a ∼ Beta( α + n a, 1 , β + n a, 0 ) 5: end for 6: Observe y i by pulling arm a i 8: if y i = 0 then 9”
The offset tree for learning with partial labels (2008, methodology): “The problem considered here is a non-interactive version of the contextual bandit problem (see [2, 3, 5, 15, 20] for background on the bandit problem).”
Learning Where to Attend with Deep Architectures for Image Tracking (2011, methodology): “In an earlier version of this work (Bazzani et al., 2010) we learned the gaze selection policy with a portfolio allocation algorithm called Hedge (Freund & Schapire, 1997; Auer et al., 1998b).”
A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning (2017, neutral): “We try three different solvers: regret-matching, Hedge, and projected replicator dynamics.”
Portfolio Allocation for Bayesian Optimization (2010, methodology): “In Section 3, we propose the use of various hedging strategies for Bayesian optimization [2, 11].”
Online Learning: A Comprehensive Survey (2018, methodology): “w relax such stochastic assumption on the rewards. We assume the reward distribution can be aected by the previous actions taken by the player, which is termed as \Adversarial Bandits" problems Auer et al. (1995). In the following, we review several classes of adversarial bandits, including som”
Exploration exploitation in Go: UCT for Monte-Carlo Go (2006, background): “[2] Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E.”
Efficient bandit algorithms for online multiclass prediction (2008, methodology): “The Exp4 algorithm (for the “experts” setting) of Auer et al. [1998] and the contextual bandit setting of Langford and Zhang [2007] are both bandit settings where the learner has side information (e.”
Stochastic Approximations and Differential Inclusions (2005, background): “2003. hal-00242990 Stochastic Approximations and Differential Inclusions Michel Benaim Josef Hofbauer Sylvain Sorin December 2003 Cahier n° 2003-029 ECOLE POLYTECHNIQUE CENTRE NATIONAL DE LA RECHERCHE SCIENTIFIQUE LABORATOIRE D'ECONOMETRIE 1rue Descartes F-75005 Paris (33) 1 55558215 http://ceco.pol”
Hidden Incentives for Auto-Induced Distributional Shift (2020, background): “While bandit algorithms typically make the i.i.d. assumption, counter-examples exist (Gheshlaghi Azar et al., 2014; Shah et al., 2018); most famously, adversarial bandits (Auer et al., 1995).”
Dynamic Assortment Optimization with a Multinomial Logit Choice Model and Capacity Constraint (2010, background): “We are interested in finding a policy that minimizes the regret, which is equivalent to maximizing the total expected reward ∑T t=1 E [f(St)] .”
Convergence and No-Regret in Multiagent Learning (2004, background): “They proved, instead, that average payoffs converge (a Our analysis focuses on expectations of regret (total and average), similar to [10, 11].”
Deep Multi-User Reinforcement Learning for Distributed Dynamic Spectrum Access (2017, background): “Note that (11) balances between the softmax and ǫ-greedy strategies, known as Exp3 strategy [53].”
A Survey of Monte Carlo Tree Search Methods (2012, background): “[14] and further analyzed by Audibert and Bubeck [11], applies in the stochastic case (and hence also in the adversarial case).”
Reasoning about Hypothetical Agent Behaviours and their Parameters (2017, methodology): “[7, 17]) did not perform better than those which assume stationary reward distributions.”
Bandit Algorithms (2020, methodology): “Poland [2005] showed a near-optimal regret for finite-armed adversarial bandits while for combinatorial settings suboptimal rates have been shown by Awerbuch and Kleinberg [2004], McMahan and Blum [2004]. Semibandits seem to have been introduced in the context of shortest-path problems by György et ”