Multi-Armed Bandits & Regret
Exploration vs exploitation, made precise.
Every recommendation engine, adaptive clinical trial and A/B test faces the same dilemma: exploit what looks best, or explore what might be better. Bandit theory makes the trade-off exact. Regret must grow at least logarithmically, with a constant set by KL divergences, and strikingly different algorithms (optimism, posterior sampling, index policies, exponential weights) each reach the limits of their own settings.
What you’ll learn
- Prove the Lai–Robbins lower bound with the divergence decomposition and the Bretagnolle–Huber inequality, and state the minimax lower bound.
- Analyze Thompson sampling: its asymptotic optimality for Bernoulli arms, and the information-ratio bound on its Bayesian regret.
- State the Gittins index theorem for discounted Bayesian bandits, sketch Weber's proof, and explain where index policies fail.
- Analyze EXP3 for adversarial bandits and prove its regret bound.
The price of learning: the Lai–Robbins bound
Recall the stochastic bandit of Monte Carlo Tree Search & UCT, where UCB1's finite-time bound is proved: arms with reward distributions and means , gaps , pull counts , and regret . How small can regret be? A policy that always pulls arm 1 has zero regret whenever arm 1 is best, so lower bounds must quantify over a class: a policy is consistent if for every and every instance in the class.
Change of measure. Fix a suboptimal arm and , and let equal except that arm has mean , so that in it is the unique best arm. Only pulls of arm tell the two worlds apart, so the KL divergence between the laws of the whole interaction is
Bretagnolle–Huber. For any event , . Take :
Regret controls both terms. In every pull of costs ; in every other pull costs at least . So and , and consistency bounds both regrets by :
Take logarithms, divide by and let ; then let and , using the continuity of :
Two companions. In the worst case over instances, every policy has regret at least a constant times (Auer, Cesa-Bianchi, Freund & Schapire, 2002): the instance-dependent blows up as the gaps shrink, and gaps near are the hardest. UCB1 is within a factor of this, and MOSS (Audibert & Bubeck, 2009) is minimax optimal. And the Lai–Robbins bound is asymptotic: it constrains how regret grows as , not its value at a fixed horizon. Non-asymptotic lower bounds describe how regret first grows roughly linearly while every arm is explored, and only later bends toward the logarithmic rate (Garivier, Ménard & Stoltz, 2019).
Thompson sampling: optimal by randomization
Thompson (1933) proposed the oldest bandit algorithm: keep a posterior over the arms' means, draw one sample from it, and act as if the sample were true. For Bernoulli arms with uniform priors, arm 's posterior is . The rule probability-matches: it pulls each arm with the posterior probability that the arm is optimal, . Long neglected, Thompson sampling was revived by strong results in online advertising and recommendation (Scott, 2010; Chapelle & Li, 2011).
Let be expectation given the history before round . Define the expected regret of round , and the information that its action and observation reveal about the optimal arm:
Key inequality. Thompson sampling plays with the same distribution as . A Cauchy–Schwarz and Pinsker argument then bounds the information ratio by for arms with rewards in :
Sum over rounds and apply Cauchy–Schwarz once more:
By the chain rule of mutual information, the gains add up to the total information that the history carries about , which cannot exceed its entropy, at most :
The argument says that regret is cheap whenever every mistake is informative, and it separates the algorithm (a bounded information ratio) from the problem (the entropy of the optimal action). The same template gives bounds for linear bandits, and posterior sampling extends to reinforcement learning (PSRL; Osband, Russo & Van Roy, 2013). Probability matching is not right for every objective, though: to identify the best arm rather than to minimize regret, top-two variants do better (Russo, 2016).
Bayesian bandits and the Gittins index
Suppose instead that the prior is real and the goal is to maximize exactly. Each arm's posterior is a Markov chain that moves only when the arm is pulled, so the problem is an MDP on the product of the arms' posterior states, exponentially large in . Gittins discovered that it decomposes: each arm can be scored on its own.
One arm, fair charge. If the arm is played at a per-pull charge equal to its current index , the best you can do is break even in expectation, and you do break even by continuing until the index first falls below that charge:
Prevailing charge. Whenever an arm's index falls below the charge in force, lower the charge to the index. The prevailing charge is the running minimum of the indices seen so far: a non-increasing sequence fixed by the arm's own trajectory, whatever the policy does with the other arms.
An upper bound for every policy. Playing an arm at its prevailing charge is never favorable in expectation, so any policy's expected discounted reward is at most the expected discounted prevailing charges it pays. Equality holds for policies that never leave an arm while its index exceeds its prevailing charge.
The index policy maximizes the bound and attains it. To maximize a discounted sum of several interleaved non-increasing sequences, always take the largest available element. Pulling the arm of largest index does exactly that, and it never leaves an arm in mid-excursion, so it attains equality.
Which change breaks the Gittins index theorem?
- Raising the discount factor from 0.9 to 0.99
- Using non-uniform priors on the arms' means
- Letting arms' states evolve even when they are not pulled (restless bandits)
- Having 100 arms instead of 2
Show the answer
C. Letting arms' states evolve even when they are not pulled (restless bandits)
The proof needs each arm's prevailing-charge sequence to depend only on that arm's own plays. Restless arms change while idle, so the decomposition fails. Whittle (1988) proposed an index heuristic for restless bandits that is asymptotically optimal under conditions (Weber & Weiss, 1990), and the general problem is PSPACE-hard (Papadimitriou & Tsitsiklis, 1999).
The limits are as instructive as the theorem. It needs geometric discounting: with a finite horizon the optimal policy is generally not an index policy. Indices of finite-state arms can be computed efficiently (Varaiya, Walrand & Buyukkoc, 1985; Katehakis & Veinott, 1987), but for Beta posteriors they have no closed form and are tabulated numerically. And Bayes-optimality holds on average over the prior; guarantees on a fixed instance need a separate, frequentist analysis.
Adversarial bandits: EXP3
Drop the probabilistic model altogether. An oblivious adversary fixes losses for all rounds in advance; the learner picks , sees only , and is compared with the best fixed arm in hindsight, . A deterministic learner suffers linear regret, because the adversary can simulate it, so the learner must randomize. EXP3 (Auer, Cesa-Bianchi, Freund & Schapire, 2002) runs exponential weights on importance-weighted loss estimates:
function EXP3(K arms, horizon n, learning rate η):
L̂ ← zeros(K) # estimated cumulative losses
for t = 1 to n:
p_i ← exp(−η · L̂_i) / Σ_j exp(−η · L̂_j) # exponential weights
draw A_t ~ p; observe only ℓ_t,A_t ∈ [0, 1]
L̂_{A_t} ← L̂_{A_t} + ℓ_t,A_t / p_{A_t} # unbiased for every armThe loss-based form analyzed by Lattimore and Szepesvári (2020). The original EXP3 works with rewards and mixes in uniform exploration.
Let , with . For any fixed arm , :
Each round multiplies by . The estimates are non-negative, so and give
Sum over and combine with the first line:
Take expectations. Given the past, has mean , has mean , and the variance term has mean , the price of seeing only one arm. Optimize :
An adversarial bandit with arms runs for rounds. What total regret does the EXP3 bound guarantee?
Show the answer
680
: about 0.07 per round against the best fixed arm, with no assumption on how the losses arise. On a fixed stochastic instance with constant gaps, a good stochastic algorithm pays only . Robustness to adversaries costs instead of .
EXP3's guarantee holds in expectation, and its regret has high variance because estimates can be huge; implicit exploration (EXP3-IX) gives high-probability bounds (Neu, 2015). With expert advice, EXP4 competes with the best of policies at regret , the starting point of contextual bandits.
Key takeaways
- Lai–Robbins: consistent policies pull each suboptimal arm at least times. The proof changes one arm's mean and combines the divergence decomposition with the Bretagnolle–Huber inequality; worst-case regret is .
- Thompson sampling matches the Lai–Robbins constant for Bernoulli arms, and its Bayesian regret is at most because each unit of regret buys information about the optimal arm.
- For discounted Bayesian bandits with independent arms that are frozen when idle, the Gittins index policy is optimal; restless arms and finite horizons break the decomposition.
- Against adversaries, exponential weights on importance-weighted losses (EXP3) give regret: robustness costs instead of .
- Asymptotic bounds describe growth rates, not finite-horizon values: on the widget's arms Thompson sampling averages about 19 over 500 pulls, below .
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Which two-armed Bernoulli instance forces the largest asymptotic regret constant ?
- Means 0.5 and 0.9
- Means 0.1 and 0.5
- Means 0.5 and 0.6
- All the same: only the number of arms matters
Show the answer
C. Means 0.5 and 0.6
, so , against for 0.5 versus 0.9 and for 0.1 versus 0.5. A pull of the worse arm costs less when the gap is small, but the number of pulls needed to tell the arms apart grows like , and that wins.
In the information-ratio analysis of Thompson sampling, why does the final bound involve ?
- Because there are rounds of exploration
- Because the total information gained about the optimal arm cannot exceed its entropy, which is at most
- Because Thompson sampling uses a learning rate proportional to
- Because Hoeffding's inequality is applied once per arm
Show the answer
B. Because the total information gained about the optimal arm cannot exceed its entropy, which is at most
Each round's regret is paid for in information about , since , and the chain rule caps the total information at . With a prior concentrated on a few arms, is smaller and so is the bound.
An arm pays exactly on every pull, with no uncertainty. What is its Gittins index?
- 0, since there is nothing to learn
- It depends on the other arms
Show the answer
D.
For every stopping time the ratio is . Known arms are the calibration standard: an uncertain arm's index is the known reward rate you would accept in exchange for it, which is at least its posterior mean (take ) and usually more, an exploration bonus.
Why does EXP3 divide the observed loss by ?
- To make the estimate of every arm's loss unbiased, although only one arm is observed
- To give rarely played arms an optimism bonus
- To normalize the weights
- To keep the estimates below 1
Show the answer
A. To make the estimate of every arm's loss unbiased, although only one arm is observed
for every arm, so exponential weights on the estimates track the true cumulative losses in expectation. The price is variance: , which is where the factor in comes from.
Further reading
- T. L. Lai & H. Robbins, "Asymptotically efficient adaptive allocation rules," Advances in Applied Mathematics 6(1), 4–22 (1985).
- P. Auer, N. Cesa-Bianchi, Y. Freund & R. E. Schapire, "The nonstochastic multiarmed bandit problem," SIAM Journal on Computing 32(1), 48–77 (2002).
- J. C. Gittins, "Bandit processes and dynamic allocation indices," Journal of the Royal Statistical Society, Series B 41(2), 148–177 (1979).
- D. Russo & B. Van Roy, "An information-theoretic analysis of Thompson sampling," Journal of Machine Learning Research 17, 1–30 (2016).
- T. Lattimore & C. Szepesvári, Bandit Algorithms (Cambridge University Press, 2020).