Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

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 nK\sqrt{nK} lower bound.
  • Analyze Thompson sampling: its asymptotic optimality for Bernoulli arms, and the information-ratio bound 12nKln⁡K\sqrt{\tfrac12nK\ln K} 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 2nKln⁡K\sqrt{2nK\ln K} 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 E[Ti(n)]≤8ln⁡n/Δi2+O(1)\E[T_i(n)]\le8\ln n/\Delta_i^2+\order{1} is proved: arms i=1,…,Ki=1,\dots,K with reward distributions νi\nu_i and means μi\mu_i, gaps Δi=μ∗−μi\Delta_i=\mu^*-\mu_i, pull counts Ti(n)T_i(n), and regret Rn=∑iΔiE[Ti(n)]R_n=\sum_i\Delta_i\E[T_i(n)]. 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 Rn(ν)=o(na)R_n(\nu)=o(n^a) for every a>0a>0 and every instance ν\nu in the class.

DerivationProof sketch (after Lattimore & Szepesvári, chapter 16)
  1. DKL(Pr⁡ν ∥ Pr⁡ν′)=Eν[Ti(n)]  d(μi,μ∗+ε)\KL\big(\Pr_\nu\,\|\,\Pr_{\nu'}\big)=\E_\nu\big[T_i(n)\big]\;d(\mu_i,\mu^*+\varepsilon)

    Change of measure. Fix a suboptimal arm ii and ε>0\varepsilon>0, and let ν′\nu' equal ν\nu except that arm ii has mean μ∗+ε\mu^*+\varepsilon, so that in ν′\nu' it is the unique best arm. Only pulls of arm ii tell the two worlds apart, so the KL divergence between the laws of the whole interaction is

  2. Pr⁡ν(Ti(n)>n2)+Pr⁡ν′(Ti(n)≤n2) ≥ 12exp⁡ ⁣(−Eν[Ti(n)] d(μi,μ∗+ε))\Pr_\nu\big(T_i(n)>\tfrac n2\big)+\Pr_{\nu'}\big(T_i(n)\le\tfrac n2\big)\ \ge\ \tfrac12\exp\!\big(-\E_\nu[T_i(n)]\,d(\mu_i,\mu^*+\varepsilon)\big)

    Bretagnolle–Huber. For any event EE, Pr⁡ν(E)+Pr⁡ν′(Ec)≥12exp⁡(−DKL(Pr⁡ν∥Pr⁡ν′))\Pr_\nu(E)+\Pr_{\nu'}(E^c)\ge\frac12\exp(-\KL(\Pr_\nu\|\Pr_{\nu'})). Take E={Ti(n)>n/2}E=\{T_i(n)>n/2\}:

  3. 12exp⁡ ⁣(−Eν[Ti(n)] d(μi,μ∗+ε))≤2Canan(1Δi+1ε)\tfrac12\exp\!\big(-\E_\nu[T_i(n)]\,d(\mu_i,\mu^*+\varepsilon)\big)\le\frac{2C_an^a}{n}\Big(\frac1{\Delta_i}+\frac1\varepsilon\Big)

    Regret controls both terms. In ν\nu every pull of ii costs Δi\Delta_i; in ν′\nu' every other pull costs at least ε\varepsilon. So Rn(ν)≥nΔi2Pr⁡ν(E)R_n(\nu)\ge\frac{n\Delta_i}2\Pr_\nu(E) and Rn(ν′)≥nε2Pr⁡ν′(Ec)R_n(\nu')\ge\frac{n\varepsilon}2\Pr_{\nu'}(E^c), and consistency bounds both regrets by CanaC_an^a:

  4. lim inf⁡n→∞Eν[Ti(n)]ln⁡n ≥ 1−ad(μi,μ∗+ε) ⟶ 1d(μi,μ∗)\liminf_{n\to\infty}\frac{\E_\nu[T_i(n)]}{\ln n}\ \ge\ \frac{1-a}{d(\mu_i,\mu^*+\varepsilon)}\ \longrightarrow\ \frac1{d(\mu_i,\mu^*)}

    Take logarithms, divide by ln⁡n\ln n and let n→∞n\to\infty; then let a→0a\to0 and ε→0\varepsilon\to0, using the continuity of dd:

Two companions. In the worst case over instances, every policy has regret at least a constant times nK\sqrt{nK} (Auer, Cesa-Bianchi, Freund & Schapire, 2002): the instance-dependent ln⁡n/Δ\ln n/\Delta blows up as the gaps shrink, and gaps near K/n\sqrt{K/n} are the hardest. UCB1 is within a factor ln⁡n\sqrt{\ln n} of this, and MOSS (Audibert & Bubeck, 2009) is minimax optimal. And the Lai–Robbins bound is asymptotic: it constrains how regret grows as n→∞n\to\infty, 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 ii's posterior is Beta(1+si,1+fi)\mathrm{Beta}(1+s_i,1+f_i). The rule probability-matches: it pulls each arm with the posterior probability that the arm is optimal, Pr⁡(It=i∣Ft−1)=Pr⁡(i=arg max⁡jθj∣Ft−1)\Pr(I_t=i\mid\mathcal F_{t-1})=\Pr(i=\argmax_j\theta_j\mid\mathcal F_{t-1}). Long neglected, Thompson sampling was revived by strong results in online advertising and recommendation (Scott, 2010; Chapelle & Li, 2011).

DerivationThe information-ratio argument for (b)
  1. Δt=Et[μA∗−μAt],It=It(A∗;(At,Yt))\Delta_t=\E_t\big[\mu_{A^*}-\mu_{A_t}\big],\qquad I_t=I_t\big(A^*;(A_t,Y_t)\big)

    Let Et\E_t be expectation given the history before round tt. Define the expected regret of round tt, and the information that its action and observation (At,Yt)(A_t,Y_t) reveal about the optimal arm:

  2. Δt≤K2 It\Delta_t\le\sqrt{\tfrac K2\,I_t}

    Key inequality. Thompson sampling plays AtA_t with the same distribution as A∗A^*. A Cauchy–Schwarz and Pinsker argument then bounds the information ratio Δt2/It\Delta_t^2/I_t by K/2K/2 for KK arms with rewards in [0,1][0,1]:

  3. E∑t=1nΔt≤K2 E∑t=1nIt≤K2 n E∑t=1nIt\E\sum_{t=1}^n\Delta_t\le\sqrt{\tfrac K2}\ \E\sum_{t=1}^n\sqrt{I_t}\le\sqrt{\tfrac K2\,n\ \E\sum_{t=1}^nI_t}

    Sum over rounds and apply Cauchy–Schwarz once more:

  4. E∑t=1nIt=I(A∗;Hn)≤H(A∗)≤ln⁡K⟹BayesRegret(n)≤12Knln⁡K\E\sum_{t=1}^nI_t=I\big(A^*;\mathcal H_n\big)\le H(A^*)\le\ln K\quad\Longrightarrow\quad\text{BayesRegret}(n)\le\sqrt{\tfrac12Kn\ln K}

    By the chain rule of mutual information, the gains add up to the total information that the history carries about A∗A^*, which cannot exceed its entropy, at most ln⁡K\ln K:

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 O~(dn)\tilde{\mathcal O}(d\sqrt n) 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 E[∑tγtrt]\E[\sum_t\gamma^tr_t] 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 KK. Gittins discovered that it decomposes: each arm can be scored on its own.

DerivationWeber’s prevailing-charge proof (1992), sketched
  1. sup⁡τ≥1 Ex[∑t<τγt(r(Xt)−ν(x))]=0\sup_{\tau\ge1}\ \E_x\Big[\sum_{t<\tau}\gamma^t\big(r(X_t)-\nu(x)\big)\Big]=0

    One arm, fair charge. If the arm is played at a per-pull charge equal to its current index ν(x)\nu(x), 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:

  2. λˉt=min⁡s≤tν(Xs)\bar\lambda_t=\min_{s\le t}\nu(X_s)

    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.

  3. E[∑tγtrt]≤E[∑tγt λˉt(It)]\E\Big[\sum_t\gamma^tr_t\Big]\le\E\Big[\sum_t\gamma^t\,\bar\lambda^{(I_t)}_t\Big]

    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.

  4. largest index first = greedy merge of non-increasing sequences\text{largest index first}\ =\ \text{greedy merge of non-increasing sequences}

    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.

Check your understanding

Which change breaks the Gittins index theorem?

  1. Raising the discount factor from 0.9 to 0.99
  2. Using non-uniform priors on the arms' means
  3. Letting arms' states evolve even when they are not pulled (restless bandits)
  4. 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 ℓt∈[0,1]K\ell_t\in[0,1]^K for all rounds in advance; the learner picks AtA_t, sees only ℓt,At\ell_{t,A_t}, and is compared with the best fixed arm in hindsight, Rn=E[∑tℓt,At]−min⁡i∑tℓt,iR_n=\E\big[\sum_t\ell_{t,A_t}\big]-\min_i\sum_t\ell_{t,i}. 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:

text
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 arm

The loss-based form analyzed by Lattimore and Szepesvári (2020). The original EXP3 works with rewards and mixes in uniform exploration.

DerivationProof
  1. ln⁡WnW0 ≥ −ηL^n,i−ln⁡K\ln\frac{W_n}{W_0}\ \ge\ -\eta\hat L_{n,i}-\ln K

    Let Wt=∑iexp⁡(−ηL^t,i)W_t=\sum_i\exp(-\eta\hat L_{t,i}), with W0=KW_0=K. For any fixed arm ii, Wn≥exp⁡(−ηL^n,i)W_n\ge\exp(-\eta\hat L_{n,i}):

  2. ln⁡WtWt−1 ≤ −η∑ipt,iℓ^t,i+η22∑ipt,iℓ^t,i2\ln\frac{W_t}{W_{t-1}}\ \le\ -\eta\sum_ip_{t,i}\hat\ell_{t,i}+\frac{\eta^2}2\sum_ip_{t,i}\hat\ell_{t,i}^2

    Each round multiplies WW by ∑ipt,ie−ηℓ^t,i\sum_ip_{t,i}e^{-\eta\hat\ell_{t,i}}. The estimates are non-negative, so e−x≤1−x+x2/2e^{-x}\le1-x+x^2/2 and ln⁡(1+y)≤y\ln(1+y)\le y give

  3. ∑t∑ipt,iℓ^t,i−L^n,i ≤ ln⁡Kη+η2∑t∑ipt,iℓ^t,i2\sum_t\sum_ip_{t,i}\hat\ell_{t,i}-\hat L_{n,i}\ \le\ \frac{\ln K}\eta+\frac\eta2\sum_t\sum_ip_{t,i}\hat\ell_{t,i}^2

    Sum over tt and combine with the first line:

  4. Rn≤ln⁡Kη+ηnK2=2nKln⁡Katη=2ln⁡KnKR_n\le\frac{\ln K}\eta+\frac{\eta nK}2=\sqrt{2nK\ln K}\quad\text{at}\quad\eta=\sqrt{\frac{2\ln K}{nK}}

    Take expectations. Given the past, ∑ipt,iℓ^t,i\sum_ip_{t,i}\hat\ell_{t,i} has mean E[ℓt,At]\E[\ell_{t,A_t}], L^n,i\hat L_{n,i} has mean Ln,iL_{n,i}, and the variance term has mean ∑iℓt,i2≤K\sum_i\ell_{t,i}^2\le K, the price of seeing only one arm. Optimize η\eta:

Predict before you look

An adversarial bandit with K=10K=10 arms runs for n=10,000n=10{,}000 rounds. What total regret does the EXP3 bound 2nKln⁡K\sqrt{2nK\ln K} guarantee?

Show the answer

680

2⋅104⋅10⋅ln⁡10=4.6×105≈679\sqrt{2\cdot10^4\cdot10\cdot\ln10}=\sqrt{4.6\times10^5}\approx679: 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 O(log⁡n)\order{\log n}. Robustness to adversaries costs n\sqrt n instead of log⁡n\log n.

EXP3's guarantee holds in expectation, and its regret has high variance because estimates ℓ/p\ell/p can be huge; implicit exploration (EXP3-IX) gives high-probability bounds (Neu, 2015). With expert advice, EXP4 competes with the best of NN policies at regret O(nKln⁡N)\order{\sqrt{nK\ln N}}, the starting point of contextual bandits.

Key takeaways

  • Lai–Robbins: consistent policies pull each suboptimal arm at least (1−o(1))ln⁡n/d(μi,μ∗)(1-o(1))\ln n/d(\mu_i,\mu^*) times. The proof changes one arm's mean and combines the divergence decomposition with the Bretagnolle–Huber inequality; worst-case regret is Ω(nK)\Omega(\sqrt{nK}).
  • Thompson sampling matches the Lai–Robbins constant for Bernoulli arms, and its Bayesian regret is at most 12nKln⁡K\sqrt{\tfrac12nK\ln K} 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 2nKln⁡K\sqrt{2nK\ln K} regret: robustness costs n\sqrt n instead of log⁡n\log n.
  • Asymptotic bounds describe growth rates, not finite-horizon values: on the widget's arms Thompson sampling averages about 19 over 500 pulls, below 5.44ln⁡500≈345.44\ln500\approx34.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Which two-armed Bernoulli instance forces the largest asymptotic regret constant Δ/d(μ2,μ1)\Delta/d(\mu_2,\mu_1)?

  1. Means 0.5 and 0.9
  2. Means 0.1 and 0.5
  3. Means 0.5 and 0.6
  4. All the same: only the number of arms matters
Show the answer

C. Means 0.5 and 0.6

d(0.5,0.6)≈0.020d(0.5,0.6)\approx0.020, so Δ/d≈0.1/0.020≈4.9\Delta/d\approx0.1/0.020\approx4.9, against 0.4/0.51≈0.780.4/0.51\approx0.78 for 0.5 versus 0.9 and 0.4/0.37≈1.090.4/0.37\approx1.09 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 1/Δ21/\Delta^2, and that wins.

Question 2

In the information-ratio analysis of Thompson sampling, why does the final bound involve ln⁡K\ln K?

  1. Because there are ln⁡K\ln K rounds of exploration
  2. Because the total information gained about the optimal arm cannot exceed its entropy, which is at most ln⁡K\ln K
  3. Because Thompson sampling uses a learning rate proportional to ln⁡K\ln K
  4. 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 ln⁡K\ln K

Each round's regret is paid for in information about A∗A^*, since Δt2≤K2It\Delta_t^2\le\frac K2I_t, and the chain rule caps the total information at I(A∗;Hn)≤H(A∗)≤ln⁡KI(A^*;\mathcal H_n)\le H(A^*)\le\ln K. With a prior concentrated on a few arms, H(A∗)H(A^*) is smaller and so is the bound.

Question 3

An arm pays exactly μ\mu on every pull, with no uncertainty. What is its Gittins index?

  1. 0, since there is nothing to learn
  2. μ/(1−γ)\mu/(1-\gamma)
  3. It depends on the other arms
  4. μ\mu
Show the answer

D. μ\mu

For every stopping time the ratio is μ E[∑t<τγt]/E[∑t<τγt]=μ\mu\,\E[\sum_{t<\tau}\gamma^t]/\E[\sum_{t<\tau}\gamma^t]=\mu. 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 τ=1\tau=1) and usually more, an exploration bonus.

Question 4

Why does EXP3 divide the observed loss by pAtp_{A_t}?

  1. To make the estimate of every arm's loss unbiased, although only one arm is observed
  2. To give rarely played arms an optimism bonus
  3. To normalize the weights
  4. 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

E[ℓ^t,i]=pt,i⋅ℓt,i/pt,i=ℓt,i\E[\hat\ell_{t,i}]=p_{t,i}\cdot\ell_{t,i}/p_{t,i}=\ell_{t,i} for every arm, so exponential weights on the estimates track the true cumulative losses in expectation. The price is variance: E[∑ipt,iℓ^t,i2]=∑iℓt,i2≤K\E[\sum_ip_{t,i}\hat\ell_{t,i}^2]=\sum_i\ell_{t,i}^2\le K, which is where the factor KK in 2nKln⁡K\sqrt{2nK\ln K} 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).