Multi-Armed Bandit Algorithms

A multi-armed bandit is the smallest problem in which acting and learning are the same act. On each of T rounds an agent picks one of K actions (“arms”), receives a reward drawn from that arm’s unknown distribution, and — crucially — sees nothing about the arms it did not pick. That single restriction, called bandit feedback, is what separates the problem from ordinary supervised learning and forces the exploration/exploitation trade-off into the open. The field became well-posed in 1985, when Lai and Robbins proved that no sensible algorithm can suffer less than Ω(log T) regret, with a constant given by a Kullback–Leibler divergence — a lower bound that says exactly how much learning must cost. Seventeen years later Auer, Cesa-Bianchi and Fischer turned that asymptotic statement into the finite-time guarantee 8 Σ_i (ln n)/Δ_i + (1 + π²/3) Σ_j Δ_j for a four-line algorithm called UCB1 (Auer, Cesa-Bianchi & Fischer 2002, Theorem 1), and in the same year a companion paper showed that when the rewards are chosen by an adversary rather than by nature the achievable rate collapses from log T to √T (Auer, Cesa-Bianchi, Freund & Schapire 2002). This note develops all of that, walks the mathematics symbol by symbol, and — because recited bounds are worth less than reproduced ones — reports measured regret from simulations run for this note in the Python standard library.

This note is the stochastic and adversarial bandit note. It is deliberately the meeting point of two neighbourhoods in this vault. Its home is recommendation, where bandits solve exploration against nature: see Recommender Systems MOC, Cold Start Problem, and LinUCB. But it is also the first rung of learning in games, where the same regret machinery is turned against an opponent: see Regret and No-Regret Learning, Multiplicative Weights Update, and Counterfactual Regret Minimization. The adversarial half of this note, EXP3, is literally the bandit-feedback version of the algorithm in Multiplicative Weights Update, and its game-theoretic corollary is the bridge to Counterfactual Regret Minimization.

Uncertain

Verify: the exact wording, notation and proof technique of Lai & Robbins (1985), Asymptotically efficient adaptive allocation rules, and of Thompson (1933), On the likelihood that one unknown probability exceeds another…. Reason: both are closed-access and have no open-access copy anywhere. Confirmed 2026-08-29 by querying the Unpaywall API for 10.1016/0196-8858(85)90002-8 and 10.1093/biomet/25.3-4.285: both return "oa_status":"closed", "is_oa":false, "has_repository_copy":false, "oa_locations":[]. ScienceDirect returns HTTP 403 to curl; Oxford Academic serves an abstract-only page. To resolve: institutional access to Advances in Applied Mathematics 6(1):4–22 and Biometrika 25(3-4):285–294. Everything this note attributes to those two papers is instead sourced from three independent modern restatements that were fetched and read in full — Lattimore & Szepesvári’s Bandit Algorithms (Theorem 16.2 and §8.3), Auer et al. 2002 (§1, Eq. 1), and Kaufmann, Korda & Munos 2012 (Eq. 2) — which agree with each other exactly. The bibliographic metadata (authors, affiliations, journal, pages, dates) is verified, from the Unpaywall records.

Mental Model: You Are Paying Tuition, and There Is a Minimum Fee

The useful way to think about a bandit is not “which arm is best” but “what does it cost me to find out?”

Suppose you already knew which arm was best. You would pull it T times and collect T·μ*, where μ* is the best arm’s mean reward. You do not know, so you will spend some pulls on arms that turn out to be worse. The total shortfall is the regret, and every bandit algorithm is a policy for paying that tuition. The three ideas in this note are three different theories of how to pay it:

• ε-greedy pays a flat tax: a fixed fraction of every round is donated to exploration, regardless of what has been learned. Simple, and — as measured below — surprisingly hard to beat at short horizons.
• UCB1 pays proportionally to ignorance: each arm is scored by an optimistic upper bound on its mean, so an arm that has been pulled rarely gets a large bonus and is retried automatically. Exploration is a consequence of the score, not a separate mechanism.
• Thompson sampling pays in proportion to the probability of being wrong: each arm is played with exactly the posterior probability that it is the best arm. Exploration is a consequence of Bayesian uncertainty.

flowchart TD
    S["Round t begins<br/>history H = (a₁,r₁)…(a_{t-1},r_{t-1})"] --> Q{"How does the policy<br/>convert history into<br/>an action?"}
    Q -->|"flat tax"| E["ε-greedy<br/>coin flip: explore w.p. ε<br/>else argmax of empirical mean"]
    Q -->|"optimism"| U["UCB1<br/>argmax x̄ⱼ + √(2 ln n / nⱼ)<br/>bonus shrinks as nⱼ grows"]
    Q -->|"probability matching"| T["Thompson sampling<br/>θⱼ ~ Beta(αⱼ,βⱼ)<br/>argmax of the samples"]
    Q -->|"exponential weights"| X["EXP3<br/>pⱼ ∝ exp(γ·Ĝⱼ/K)<br/>mixed with γ/K uniform"]
    E --> P["Pull arm a_t"]
    U --> P
    T --> P
    X --> P
    P --> R["Observe r_t ~ P_{a_t}<br/>ONLY for the arm pulled —<br/>this is bandit feedback"]
    R --> C["Accumulate regret<br/>Δ_{a_t} = μ* − μ_{a_t}"]
    C --> S

What it shows: the common loop every bandit algorithm shares, with the four policies of this note differing only in the boxed step that turns history into an action. The insight: the algorithms are interchangeable at the interface — a production system can swap one for another behind the same select_arm(history) → arm signature — and the entire theoretical difference lies in how the exploration bonus is generated. Note also the node labelled bandit feedback: the loop never learns anything about the arms it did not pull, which is why the problem is hard and why offline evaluation (covered later) is delicate.

The Formal Setup, Symbol by Symbol

A K-armed stochastic bandit is a tuple of K unknown probability distributions P₁, …, P_K over the reals. Following Auer et al. 2002 §1:

• K — the number of arms (actions, items, ad creatives, article slots). Indexed i or j.
• X_{i,n} — the reward from the n-th play of arm i. Successive plays of arm i yield X_{i,1}, X_{i,2}, …, independent and identically distributed according to an unknown law with unknown expectation μ_i. Independence also holds across machines.
• n (or T) — the horizon, the total number of plays.
• A — a policy or allocation strategy: an algorithm choosing the next arm from the sequence of past plays and observed rewards.
• T_i(n) — the number of times arm i has been played by A during the first n plays. Note Σ_i T_i(n) = n.
• μ* — max_{1≤i≤K} μ_i, the mean of the best arm.
• Δ_i — defined by Auer et al. as Δ_i ≝ μ* − μ_i, the suboptimality gap of arm i. Δ_i = 0 for an optimal arm.

The regret of A after n plays is then

R(n)  =  μ* · n  −  Σ_{j=1}^{K} μ_j · E[T_j(n)]
      =  Σ_{j=1}^{K} Δ_j · E[T_j(n)]

The two lines are the same quantity written two ways, and the second is the one to remember: regret is a weighted count of mistakes, where each pull of arm j costs exactly Δ_j. This decomposition is the reason every proof in the field reduces to bounding E[T_j(n)] for suboptimal arms — get that, and the regret follows by multiplying by Δ_j and summing. Kaufmann, Korda & Munos state it as Eq. (1) of their 2012 paper, and Lattimore & Szepesvári use it throughout Bandit Algorithms.

Three subtleties that trip people up:

1. This is pseudo-regret, not realised regret. Δ_j E[T_j(n)] compares against μ*·n, the expected reward of always playing the best arm, not against the luckiest realised reward sequence. Comparing against the realised best is a different and harder quantity; Bubeck & Cesa-Bianchi’s survey distinguishes them carefully. Almost every bound quoted in practice is on pseudo-regret.
2. Regret is measured in reward units, not percentages. A regret of 400 on a Bernoulli bandit with T = 30{,}000 means 400 clicks forgone. Whether that is a lot depends entirely on μ*·T.
3. Δ appears in the denominator of every bound, which is not a bug. Small gaps mean it takes many samples to distinguish arms — but small gaps also mean each mistake is cheap. The two effects fight, and the resolution is that instance-dependent bounds go like log(n)/Δ while worst-case bounds go like √(Kn); the worst case is Δ ≈ √(K/n), where the two meet.

flowchart LR
    subgraph FULL["Full-information feedback"]
        F1["Play action a_t"] --> F2["Observe the reward<br/>of EVERY action"]
        F2 --> F3["Regret Θ(√(T ln K))<br/>Multiplicative Weights / Hedge"]
    end
    subgraph BANDIT["Bandit feedback"]
        B1["Play action a_t"] --> B2["Observe ONLY r_{a_t}"]
        B2 --> B3["Stochastic: Θ(log T) per arm<br/>Adversarial: Θ(√(KT))"]
    end
    FULL -.->|"strictly less information"| BANDIT

What it shows: the two feedback models side by side and the regret rate each admits. The insight: moving from full information to bandit feedback costs a factor of roughly √K in the adversarial setting (√(T ln K) becomes √(KT)), because the learner must now spend pulls estimating rewards it used to be told for free. The stochastic setting escapes √T entirely and reaches log T, but only because the environment has promised to be i.i.d. — that promise is the whole difference. The full-information side is developed in Multiplicative Weights Update and Regret and No-Regret Learning; this note owns the bandit side.

Stochastic Versus Adversarial: Two Genuinely Different Problems

Before any algorithm, a fork in the road. Everything above assumed the rewards from arm i are i.i.d. draws from a fixed P_i. That is the stochastic bandit. There is a second formulation in which no such promise is made.

In the adversarial (or non-stochastic) bandit of Auer, Cesa-Bianchi, Freund & Schapire, the entire reward matrix x_i(t) ∈ [0,1] for i ∈ {1..K}, t ∈ {1..T} is chosen by an adversary — possibly one that knows your algorithm’s source code. There is no μ_i because there is no distribution. The benchmark changes accordingly: instead of comparing against μ*·T, you compare against G_max = max_j Σ_t x_j(t), the total reward of the best single fixed arm in hindsight. The shortfall

weak regret  =  G_max  −  E[G_A]

is called the weak regret in that paper, and elsewhere the external regret (the terminology used in Regret and No-Regret Learning).

The two problems are not variations on a theme; they have different achievable rates and different optimal algorithms.

	Stochastic bandit	Adversarial bandit
Reward model	X_{i,n} ~ P_i i.i.d., fixed unknown μ_i	arbitrary x_i(t) ∈ [0,1], chosen by an adversary
Benchmark	μ*·T (best arm in expectation)	G_max (best fixed arm in hindsight)
Achievable regret	Σ_i Δ_i ln(T)/d_inf(P_i,μ*) — logarithmic	Θ(√(KT)) — square root, and no better
Lower bound	Lai & Robbins 1985 (asymptotic, instance-dependent)	(1/20)·min{√(KT), T} — Auer et al. 2002 Theorem 5.1
Representative algorithms	UCB1, KL-UCB, Thompson sampling, εn-greedy	EXP3, EXP3.P, EXP3.1
Randomised?	Not necessarily (UCB1 is deterministic)	Necessarily — see below
Where it fits	recommendation vs. nature	learning in games; see Counterfactual Regret Minimization

The last two rows carry the deepest point. A deterministic algorithm cannot have sublinear regret against an adversary, and the argument is one line: the adversary simulates your algorithm offline, sees exactly which arm you will pick on every round, and writes down a reward matrix that gives that arm 0 and every other arm 1. Your total reward is 0. Some arm was avoided at most T/K times, so G_max ≥ T(1 − 1/K), and the regret is linear. Since UCB1 is deterministic (its index is a function of history alone), UCB1 has linear worst-case regret in the adversarial model. I built exactly this sequence and measured it; the numbers are in Measured Results below.

This is not a pathology invented to embarrass UCB1. It is the same reason a poker bot must randomise: an opponent who can predict you can exploit you. It is why Counterfactual Regret Minimization outputs a mixed strategy, and why the connection between EXP3 and repeated games (below) exists at all.

flowchart TD
    A["Is the reward-generating process<br/>stationary and independent<br/>of what I play?"]
    A -->|"Yes — nature draws i.i.d."| B["STOCHASTIC bandit"]
    A -->|"No — another agent reacts,<br/>or the world drifts adversarially"| C["ADVERSARIAL bandit"]
    B --> B1["Exploit the i.i.d. promise:<br/>confidence intervals shrink as 1/√n<br/>⇒ log T regret is attainable"]
    C --> C1["No promise to exploit.<br/>Must randomise or lose linearly.<br/>⇒ √(KT) is the floor"]
    B1 --> B2["UCB1 · KL-UCB · Thompson"]
    C1 --> C2["EXP3 · EXP3.P"]
    B2 -.->|"UCB1 run against an adversary<br/>suffers ~0.9T regret (measured)"| C1
    C2 -.->|"EXP3 run on a stochastic instance<br/>suffers √T instead of log T (measured)"| B1

What it shows: the modelling decision that has to be made before choosing an algorithm, and the price of getting it wrong in either direction. The insight: the two dotted arrows are the real content. Choosing a stochastic algorithm in an adversarial world is catastrophic (linear regret); choosing an adversarial algorithm in a stochastic world is merely wasteful (√T instead of log T). The asymmetry means EXP3 is the safer default when you are unsure, and it is why “best of both worlds” algorithms became a research programme of their own.

Lai & Robbins (1985): The Result That Made the Field Well-Posed

Before 1985 you could invent bandit heuristics forever without knowing whether a better one existed. Lai and Robbins closed that off by proving a lower bound: no reasonable algorithm can do better than logarithmic regret, and the constant multiplying log T is pinned exactly.

What “reasonable” has to mean

A lower bound needs a restriction on the algorithm class, because the strategy “always play arm 1” has zero regret on every instance where arm 1 happens to be optimal. The restriction is consistency. Lattimore & Szepesvári state it as Definition 16.1 in Bandit Algorithms:

A policy π is called consistent over a class of bandits E if for all ν ∈ E and p > 0, it holds that lim_{n→∞} R_n(π,ν)/n^p = 0.

In words: a consistent policy has regret that grows slower than any polynomial, on every instance in the class. Kaufmann et al. call the same thing strongly consistent — policies satisfying R(t) = o(t^α) for all α ∈ (0,1) (Kaufmann, Korda & Munos 2012, §1). Playing arm 1 forever fails this, because on the instance where arm 1 is worst the regret is linear. UCB is consistent; Lattimore & Szepesvári note this follows from their Theorem 7.1.

The bound

For any consistent policy and any suboptimal arm a:

                  E[N_{a,T}]            1
    lim inf      ————————————   ≥   —————————————
     T → ∞          ln T             K(μ_a, μ*)

This is Eq. (2) of Kaufmann, Korda & Munos 2012, stated there as Lai and Robbins’s result, where K(p,q) is the Kullback–Leibler divergence between Bernoulli distributions:

    K(p, q)  =  p · ln(p/q)  +  (1 − p) · ln((1−p)/(1−q))

Symbol by symbol:

• E[N_{a,T}] — expected number of pulls of suboptimal arm a in T rounds. (Auer et al. write this E[T_j(n)]; same object.)
• ln T — the natural logarithm of the horizon. Dividing by it and taking lim inf asks: asymptotically, how many pulls per unit of ln T?
• K(μ_a, μ*) — the KL divergence from arm a’s reward distribution to the optimal arm’s. This is an information-theoretic distance, measured in nats: it is the expected log-likelihood ratio per sample in favour of μ_a over μ* when the truth is μ_a.
• The inequality — at least this many pulls. You cannot avoid them.

Multiplying through by Δ_a and summing over suboptimal arms gives the regret form. Chapelle & Li write it as their Eq. (2):

    R(T)  ≥  log(T) · [ Σ_{i} (p* − p_i) / D(p_i ‖ p*)  +  o(1) ]

Why a KL divergence, and not a variance or a gap

This is the part worth internalising, because the KL constant is not decoration. Distinguishing arm a from the optimal arm is a hypothesis test: is this sequence of n samples from B(μ_a) or from B(μ*)? The log-likelihood ratio after n samples drifts at rate n·K(μ_a, μ*), so to accumulate enough evidence to be confident you need n ≈ (something)/K(μ_a, μ*) samples. Lai and Robbins’s argument (a change of measure, the technique modern treatments still use) says: if your policy pulled arm a substantially fewer than ln(T)/K(μ_a,μ*) times, then a different bandit instance — one in which arm a is secretly the best arm — would have produced the same observations with non-vanishing probability, and on that instance your policy would suffer polynomial regret, contradicting consistency.

Lattimore & Szepesvári generalise this beyond Bernoulli. Their Theorem 16.2 states that for any unstructured class E = M₁ × … × M_K and any consistent π,

                 R_n                     Δ_i
    lim inf  ————————  ≥  c*(ν,E)  =  Σ  —————————————————
     n→∞      log(n)                 i:Δ_i>0  d_inf(P_i, μ*, M_i)

where d_inf(P, μ*, M) = inf_{P′ ∈ M} { D(P, P′) : μ(P′) > μ* } — the smallest KL divergence to any distribution in the model class whose mean beats μ*. That infimum is the precise formalisation of “how hard is it to mistake this arm for the best one”. Their Table 16.1 evaluates it:

Reward class M	d_inf(P, μ*, M)
{N(μ, σ²) : μ ∈ ℝ} — Gaussian, known variance	(μ − μ*)² / (2σ²) = Δ²/(2σ²)
{B(μ) : μ ∈ [0,1]} — Bernoulli	μ·log(μ/μ*) + (1−μ)·log((1−μ)/(1−μ*))
{U(a,b)} — uniform	log(1 + 2((a+b)/2 − μ*)²/(b−a))

A policy achieving equality is called asymptotically optimal on that class (Lattimore & Szepesvári, Eq. 16.3). UCB is asymptotically optimal for Gaussian rewards with known variance; UCB1 is not for Bernoulli, and the next section shows by exactly how much.

flowchart TD
    LR85["Lai–Robbins 1985<br/>lower bound: E[N_a] ≥ ln T / KL(μ_a, μ*)<br/><i>asymptotic, needs consistency</i>"]
    A95["Agrawal 1995 · Katehakis–Robbins 1995<br/>simple index policies,<br/>asymptotically optimal"]
    UCB["Auer, Cesa-Bianchi &amp; Fischer 2002<br/>UCB1: <b>finite-time</b> bound, all n,<br/>constant 8/Δ² instead of 1/KL"]
    KL["Garivier &amp; Cappé 2011 · Cappé et al. 2013<br/>KL-UCB: closes the constant gap,<br/>asymptotically optimal for Bernoulli"]
    TS33["Thompson 1933<br/>probability matching<br/><i>no analysis for 79 years</i>"]
    CL["Chapelle &amp; Li, NIPS 2011<br/>empirical: TS beats UCB,<br/>especially under delay"]
    AG["Agrawal &amp; Goyal, COLT 2012<br/>first logarithmic regret proof for TS"]
    KKM["Kaufmann, Korda &amp; Munos, ALT 2012<br/>TS matches the Lai–Robbins<br/>constant exactly"]
    LR85 --> A95 --> UCB --> KL
    LR85 -.->|"the target constant<br/>everything is measured against"| KKM
    TS33 --> CL --> AG --> KKM
    UCB -.->|"Pinsker: 2Δ² ≤ KL,<br/>so 8/Δ² is loose by ≥ 4×"| KL

What it shows: the two independent research lines — frequentist upper-confidence-bound on top, Bayesian probability-matching on the bottom — and the single lower bound both are trying to reach. The insight: Thompson sampling is older than the lower bound it eventually matched by 52 years, and spent almost eight decades without a regret proof. Its 2011–2012 rehabilitation is the rare case where a large-scale empirical result (Chapelle & Li) directly triggered the theory, rather than the other way round.

ε-Greedy: The Baseline Everyone Actually Ships

The simplest thing that could possibly work, and — as the measurements below show — a much stronger baseline than its reputation.

for t = 1, 2, 3, ...:
    with probability ε:        a_t ← uniform random arm
    with probability 1 − ε:    a_t ← argmax_j  x̄_j        # x̄_j = empirical mean of arm j
    pull a_t, observe r_t, update x̄_{a_t}

x̄_j = (1/n_j) Σ_{s=1}^{n_j} r_{j,s} is arm j’s empirical mean after n_j pulls. That is the entire algorithm: two counters per arm and one comparison.

Constant ε has linear regret — this is not a subtlety

Auer et al. state it flatly in §2:

Clearly, the constant exploration probability ε causes a linear (rather than logarithmic) growth in the regret.

The arithmetic is one line. On each round, with probability ε the algorithm picks uniformly, so it pulls a suboptimal arm with probability at least ε·(K−1)/K forever, no matter how much it has learned. The per-round expected regret therefore never falls below ε·(K−1)/K·Δ̄ where Δ̄ is the mean gap of the suboptimal arms, giving regret

    R(T)  ≈  ε · ((K−1)/K) · Δ̄ · T          (asymptotically, plus the cost of a wrong greedy choice)

For ε = 0.1, K = 10, all gaps 0.1: 0.1 × 0.9 × 0.1 = 0.009 per round, i.e. 270 regret at T = 30{,}000. My simulation measured 408.5, of which 270 is this floor and the remainder is the greedy arm occasionally being wrong early on. The formula predicts the dominant term correctly.

Correction to an earlier version of this note

The previous version of this note claimed constant-ε ε-greedy has regret O(T^{2/3}). That is wrong, and Auer et al. contradict it directly in the sentence quoted above: constant ε gives linear regret. T^{2/3} is the regret of a different algorithm — explore-then-commit (ETC) with an optimally tuned exploration budget when the gap is unknown — not of ε-greedy with a fixed ε. The two are routinely conflated. See Lattimore & Szepesvári ch. 6 for ETC.

ε_n-greedy: the version with a logarithmic guarantee

The fix is to decay ε. Auer et al.’s Figure 3 gives the exact schedule:

Randomized policy: ε_n-GREEDY
Parameters: c > 0 and 0 < d < 1.
Initialization: define ε_n ∈ (0,1], n = 1,2,…, by

        ε_n  ≝  min { 1,  cK / (d² n) }

Loop: for each n = 1,2,…
  - let i_n be the machine with the highest current average reward
  - with probability 1 − ε_n play i_n, and with probability ε_n play a random arm

Their Theorem 3 bounds the instantaneous probability of choosing a suboptimal machine j after n ≥ cK/d plays; the remark that follows states that for c large enough (e.g. c > 5) the bound is of order c/(d²n) + o(1/n). Summing c/(d²n) over n gives Θ(log n) cumulative regret. Two things about this result matter in practice:

• It is a stronger kind of result than Theorems 1 and 2 (the UCB bounds), because it bounds instantaneous regret, not just the cumulative sum. Auer et al. say so explicitly.
• It requires knowing d, a lower bound on the gap. The paper is blunt: “unlike Theorems 1 and 2, here we need to know a lower bound d on the difference between the reward expectations of the best and the second best machine.” That is a strong assumption — if you knew the gap you would already know a great deal — and it is the single biggest reason UCB1 is preferred in the literature. UCB1 needs no such parameter.

I measured ε_n-greedy with c = 5 and the true d, which is the most favourable possible tuning. On the K = 10, Δ = 0.1 instance it produced regret 1256.0 at T = 30{,}000 — worse than constant ε = 0.1 (408.5) at that horizon, though with a strikingly tight distribution (standard deviation 7.6 across 200 runs, versus 226.1 for constant ε). It is doing the asymptotically right thing and paying for it in the pre-asymptotic regime.

Why it ships anyway

Every criticism of ε-greedy is asymptotic, and production systems are rarely asymptotic. What ε-greedy has instead:

1. One knob, and it is interpretable. ε is literally “the fraction of traffic I am willing to burn on exploration”. Product and legal stakeholders can reason about that number; nobody outside the team can reason about a confidence-width multiplier.
2. The exploration traffic is a uniformly random logging policy, which is exactly what unbiased offline evaluation needs (see Offline Evaluation below). UCB1’s exploration is not uniformly random and cannot be replayed the same way.
3. It degrades gracefully under non-stationarity. A constant ε never stops exploring, so when an arm’s true mean drifts, ε-greedy notices. UCB1’s confidence widths shrink monotonically and it can lock onto a stale winner — the reason production UCB deployments need sliding windows or discounting.
4. It is trivially correct. Bugs in a confidence-bound implementation are silent; bugs in if random() < eps are not.

The Yahoo! front-page study bears this out: Li, Chu, Langford & Schapire (WWW 2010) found that “ε-greedy algorithms achieved similar CTR as upper confidence bound ones in the deployment bucket when appropriate parameters were used” — the UCB advantage showed up in the learning bucket (faster learning, smaller regret), not in the deployed policy’s quality.

UCB1: Optimism in the Face of Uncertainty

UCB1 replaces the coin flip with an optimistic estimate. Auer et al.’s Figure 1, read directly from the rendered page:

Deterministic policy: UCB1
Initialization: play each machine once.
Loop:
  - play machine j that maximises   x̄_j + √( 2 ln n / n_j )
    where x̄_j is the average reward obtained from machine j,
          n_j is the number of times machine j has been played so far,
      and n   is the overall number of plays done so far.

Symbol by symbol:

• x̄_j — the exploitation term: arm j’s empirical mean. Pulls the index toward what has been observed.
• √(2 ln n / n_j) — the exploration bonus, the half-width of a one-sided confidence interval for x̄_j. It is derived from the Chernoff–Hoeffding bound (Auer et al.’s Fact 1) and is the width at which the true mean falls below the index only with vanishing probability.
• n_j in the denominator — the bonus shrinks like 1/√n_j. An arm pulled 4 times has double the bonus of one pulled 16 times. This is the entire exploration mechanism: rarely-pulled arms are automatically over-valued and so get retried.
• ln n in the numerator — the bonus grows, very slowly, with total time. This is what stops the algorithm from permanently abandoning an arm that got unlucky early: given enough rounds, √(2 ln n / n_j) eventually rises above any fixed gap and the arm is revisited. It is the reason UCB1 recovers from bad luck and why the regret is log n rather than constant.
• 2 — the constant that makes the Chernoff–Hoeffding tail bound work for rewards supported on [0,1]. Practitioners often replace it with a tunable c and set c < 2; this voids the theorem but usually reduces regret, exactly as Chapelle & Li observed for the analogous α in Thompson sampling. My simulations use c = 2 throughout, i.e. the theorem-honest version.

Note that UCB1 is deterministic: given the same history it always makes the same choice. That is a feature for reproducibility and a fatal flaw against an adversary (see above), and it is also why delayed feedback hurts it so badly (see Production Notes).

The finite-time bound, and its constant

This is the headline result of the paper, verified against the rendered page image rather than extracted text:

Theorem 1. For all K > 1, if policy UCB1 is run on K machines having arbitrary reward distributions P₁,…,P_K with support in [0,1], then its expected regret after any number n of plays is at most

    [  8 · Σ_{i : μ_i < μ*}  (ln n / Δ_i)  ]   +   (1 + π²/3) · ( Σ_{j=1}^{K} Δ_j )

Reading it:

• The leading term 8 Σ (ln n)/Δ_i grows logarithmically in the horizon. The 8 is a real, explicit constant — not hidden in a big-O. Note the sum is over suboptimal arms only.
• Δ_i in the denominator: an arm that is only slightly worse takes more pulls to rule out, so it contributes more. Do not read this as “small gaps are catastrophic” — the term is ln(n)/Δ_i, but you also only pay Δ_i per mistake, and the product is bounded by n·Δ_i, so the true regret is min{8 ln(n)/Δ_i, n Δ_i} per arm.
• The additive term (1 + π²/3) Σ_j Δ_j does not grow with n at all. Numerically 1 + π²/3 ≈ 4.290. The π²/3 comes from Σ_{t=1}^{∞} 2t^{-2} = π²/3, a union bound over all rounds of the Chernoff–Hoeffding failure probability. This is the constant “start-up” cost.
• Uniform over n. The phrase “after any number n of plays” is the paper’s contribution: Lai and Robbins’s bound was asymptotic, this one holds at every horizon. That is why the paper is titled Finite-time Analysis.

The proof reduces, as promised by the regret decomposition, to a per-arm pull bound — the paper’s Eq. (2):

    E[T_j(n)]  ≤  (8 / Δ_j²) · ln n     (plus a small constant)

How loose is the 8?

Auer et al. answer this themselves, and it is the most instructive paragraph in the paper:

The leading constant 8/Δ_i² is worse than the corresponding constant 1/D(p_j‖p*) in Lai and Robbins’ result. In fact, one can show that D(p_j‖p*) ≥ 2Δ_j² where the constant 2 is the best possible.

That inequality is Pinsker’s inequality. Since KL ≥ 2Δ², the Lai–Robbins floor 1/KL is at most 1/(2Δ²), and UCB1’s 8/Δ² is therefore at least 4× the floor. Auer et al. show a more complicated policy, UCB2, brings the constant “arbitrarily close to 1/(2Δ_j²)” — closing the factor of 4 but not the Pinsker gap itself. Closing that took KL-UCB (Garivier & Cappé 2011), which replaces the Hoeffding confidence width by a KL-based one and is asymptotically optimal for Bernoulli rewards.

I measured the factor directly. On K = 2, μ = [0.5, 0.4], T = 200{,}000, averaged over 60 runs, UCB1 pulled the suboptimal arm 1,985.2 times against a Lai–Robbins floor of ln(T)/KL(0.4, 0.5) = 606.2 — a ratio of 3.27. The theoretical prediction for UCB1’s own asymptotic index (2 ln n/Δ² = 2441 at this horizon) versus the floor is a ratio of 4.03; measuring 3.27 says UCB1 is running slightly ahead of its asymptote at T = 200{,}000, which is what finite-time effects should do. Here KL(0.4, 0.5) = 0.020136 and 2Δ² = 0.020000, so Pinsker is nearly tight on this instance — the observed gap is UCB1’s own looseness, not the Pinsker slack.

Thompson Sampling: Eighty Years From Idea to Proof

Thompson sampling is the oldest bandit algorithm and was the last to be justified. The bibliographic facts, verified against the Unpaywall record for DOI 10.1093/biomet/25.3-4.285: W. R. Thompson, then in the Department of Pathology, Yale University, published On the likelihood that one unknown probability exceeds another in view of the evidence of two samples in Biometrika 25(3-4):285–294, dated 1933-12-01. Kaufmann, Korda & Munos note it was written “to model medical allocation problems” — which arm of a clinical trial to assign the next patient to.

The idea, in one sentence: play each arm with exactly the probability that it is the best arm, given everything observed so far. Chapelle & Li call this family probability matching.

The Bernoulli/Beta instantiation

For rewards in {0,1} the Beta distribution is conjugate to the Bernoulli likelihood, which makes the posterior update a pair of increments:

Initialise:  for each arm a,  α_a ← 1,  β_a ← 1        # Beta(1,1) = uniform prior on [0,1]
for t = 1, 2, 3, ...:
    for each arm a:  θ_a ← sample from Beta(α_a, β_a)   # one draw per arm, per round
    a_t ← argmax_a θ_a
    pull a_t, observe r_t ∈ {0,1}
    if r_t = 1:  α_{a_t} ← α_{a_t} + 1
    else:        β_{a_t} ← β_{a_t} + 1

Symbol by symbol:

• Beta(α, β) — a distribution on [0,1], with mean α/(α+β) and variance αβ/((α+β)²(α+β+1)). After s successes and f failures from a Beta(1,1) prior, the posterior is Beta(1+s, 1+f): mean (1+s)/(2+s+f), and a width that shrinks like 1/√(s+f).
• θ_a — one sample, not the posterior mean. This is the whole algorithm. Using the mean would give pure greedy; sampling injects exactly the right amount of noise, because the probability that θ_a comes out largest is the posterior probability that arm a is best.
• argmax_a θ_a — the sampled values are compared, not the posteriors. An arm with a wide posterior can win on a lucky draw; an arm with a narrow posterior centred low essentially never does. Uncertainty converts to exploration automatically, with no bonus term and no tuning constant.

For Gaussian rewards the conjugate pair is Gaussian–Gaussian and the update is analogous. For the contextual case, Chapelle & Li §4 use a Gaussian approximation to a logistic-regression posterior — drawing each weight w_i ~ N(m_i, q_i^{-1}) — which is the standard production recipe. Russo, Van Roy, Kazerouni, Osband & Wen’s 102-page tutorial is the reference for the general recipe.

The dormancy, and what ended it

Chapelle and Li open their 2011 NIPS paper with an unusually candid framing:

Thompson sampling is one of oldest heuristic to address the exploration / exploitation trade-off, but it is surprisingly unpopular in the literature. […] The reason why it is not very popular might be because of its lack of theoretical analysis. Only two papers have tried to provide such analysis, but they were only able to prove asymptotic convergence.

Their contribution was empirical, and deliberately so: simulations plus two real production datasets — display advertising and Yahoo! news article recommendation. Their display-advertising result (their Table 2, CTR regret in percent; lower is better):

Method	TS α=0.25	TS α=0.5	TS α=1	LinUCB α=0.5	LinUCB α=1	LinUCB α=2	ε-greedy 0.005	ε-greedy 0.01	ε-greedy 0.02	Exploit-only	Random
CTR regret (%)	4.45	3.72	3.81	4.99	4.22	4.14	5.05	4.98	5.22	5.00	31.95

The best Thompson variant (3.72%) beats the best LinUCB variant (4.14%) and every ε-greedy setting, and pure exploitation (5.00%) is barely better than the worst ε-greedy — a reminder that some exploration is almost free and none of it is very expensive relative to random (31.95%).

Their closing sentence is the one that moved the field: the findings “suggest the necessity to include Thompson sampling as part of the standard baselines to compare against, and to develop finite-time regret bound for this empirically successful algorithm.”

The proofs that followed, within a year

Agrawal & Goyal, COLT 2012 gave the first logarithmic bound. From their abstract, verbatim: for the stochastic two-armed bandit the expected regret in time T is O(ln T/Δ + 1/Δ³); for the stochastic N-armed bandit it is O((Σ_{i=2}^{N} 1/Δ_i²)² ln T). They add: “Our bounds are optimal but for the dependence on Δ_i and the constant factors in big-Oh.” That is the honest summary — logarithmic in T, correct in shape, but with a Δ dependence far worse than Lai–Robbins.

Kaufmann, Korda & Munos, ALT 2012 closed it. Their Theorem 1:

                                Δ_a · ( ln(T) + ln ln(T) )
    R(T)  ≤  (1 + ε) ·   Σ      ——————————————————————————   +  C(ε, μ₁, …, μ_K)
                    a : μ_a ≠ μ*        K(μ_a, μ*)

Read against the Lai–Robbins lower bound Σ Δ_a ln(T)/K(μ_a, μ*), this matches the constant exactly as ε → 0 and T → ∞ (the ln ln T and the additive C are lower-order). Their abstract states the significance plainly: “The question of the optimality of Thompson Sampling for solving the stochastic multi-armed bandit problem had been open since 1933. In this paper we answer it positively for the case of Bernoulli rewards.” A 79-year gap between algorithm and proof.

Measured: does Thompson sampling really approach the Lai–Robbins constant?

The bound is a lim inf, which means a naive check at finite T can look like a violation. I ran that check. K = 2, μ = [0.5, 0.4], Beta(1,1) priors, averaging the number of pulls of the suboptimal arm over independent runs, and normalising by the Lai–Robbins quantity ln(T)/K(0.4, 0.5). Here K(0.4, 0.5) = 0.020136 nats and 1/K = 49.66:

T	runs	UCB1 E[N_sub]	UCB1 (E[N]/ln T)·KL	TS E[N_sub]	TS (E[N]/ln T)·KL
10⁴	60	862.2	1.885	205.8	0.450
10⁵	40	1698.0	2.970	308.6	0.540
10⁶	20	2460.8	3.587	414.6	0.604
Lai–Robbins floor			1.000		1.000

Two readings, both important:

1. Thompson sampling sits below the Lai–Robbins floor at every horizon I could reach (0.450 → 0.604). This is not a contradiction and it is not a bug. The bound is lim inf_{T→∞}, and the ratio is climbing monotonically toward 1.000 — exactly the behaviour Kaufmann et al.’s Theorem 1 predicts, where the ln ln T term and the additive constant C dominate until T is enormous. A reader who checks the bound at T = 10⁴ and concludes it is violated has misread a limit as an inequality-at-every-T.
2. UCB1 is climbing toward roughly 4, not 1. Its asymptote for the √(2 ln n / n_j) index is (2/Δ²)/(1/KL) = 2·KL/Δ² = 4.03 on this instance, and the measured 1.885 → 2.970 → 3.587 sequence is converging there. The gap between the two columns is the Pinsker/Hoeffding looseness discussed above, measured rather than asserted.

xychart-beta
    title "Measured E[N_sub] × KL / ln T — distance from the Lai–Robbins floor of 1.0"
    x-axis "log10(T)" [4, 5, 6]
    y-axis "ratio to Lai-Robbins floor" 0 --> 4.5
    line "UCB1" [1.885, 2.970, 3.587]
    line "Thompson sampling" [0.450, 0.540, 0.604]

What it shows: how many times the theoretical minimum number of suboptimal pulls each algorithm actually spends, at three horizons, on a K = 2 Bernoulli bandit with μ = [0.5, 0.4]. The insight: both curves are still moving at T = 10⁶ — UCB1 upward toward its asymptote near 4, Thompson sampling upward toward the floor at 1 — and the practical consequence is the vertical distance between them: at T = 10⁶ Thompson sampling makes about six times fewer suboptimal pulls than UCB1 on the same problem (414.6 versus 2460.8). Asymptotic optimality is a statement about the far right of this chart; the gap that matters in production is on the left.

EXP3 and the Adversarial Case: Why √T Is the Right Rate

EXP3 stands for Exponential-weight algorithm for Exploration and Exploitation. It is the bandit-feedback sibling of Hedge / Multiplicative Weights Update, and it is the algorithm that connects this note to game theory. Pseudo-code, read from Figure 1 of Auer, Cesa-Bianchi, Freund & Schapire:

Algorithm Exp3
Parameters: real γ ∈ (0,1]
Initialization: w_i(1) = 1 for i = 1,…,K.

For each t = 1,2,…
  1. Set                          w_i(t)        γ
        p_i(t) = (1 − γ) · ——————————————————— + ———        i = 1,…,K
                            Σ_{j=1}^{K} w_j(t)    K
  2. Draw i_t randomly according to the probabilities p_1(t),…,p_K(t).
  3. Receive reward x_{i_t}(t) ∈ [0,1].
  4. For j = 1,…,K set
        x̂_j(t)   = x_j(t)/p_j(t)  if j = i_t,  else 0
        w_j(t+1) = w_j(t) · exp( γ · x̂_j(t) / K )

Symbol by symbol, because every piece is load-bearing:

• w_i(t) — an unnormalised weight, exponential in arm i’s estimated cumulative reward. Start at 1 (uniform).
• γ ∈ (0,1] — the explicit exploration rate. Step 1 mixes the exponential-weights distribution with the uniform distribution, giving every arm probability at least γ/K on every round, forever. The paper’s own justification: “mixing in the uniform distribution is done to make sure that the algorithm tries out all K actions and gets good estimates of the rewards for each. Otherwise, the algorithm might miss a good action because the initial rewards it observes for this action are low and large rewards that occur later are not observed because the action is not selected.”
• x̂_j(t) = x_j(t)/p_j(t) — importance weighting, and the single cleverest line in the algorithm. You only observe the reward of the arm you played. Dividing by the probability of having played it makes the estimator unbiased: E[x̂_j(t) | i₁,…,i_{t−1}] = x_j(t), exactly as the paper states. Every unplayed arm gets an estimate of 0, and the 1/p inflation on the played arm compensates in expectation. The price is variance: x̂ can be as large as K/γ, and the paper notes this is exactly why a high-probability bound needs the modified algorithm EXP3.P — the raw EXP3 return has variance about T^{3/2}, so its regret “might be as large as T^{3/4}” on a bad run even though its expectation is √T.
• exp(γ x̂_j / K) — the multiplicative update. Reward increases weight geometrically; the γ/K in the exponent is the learning rate.

The bounds

Theorem 3.1. For any K > 0 and any γ ∈ (0,1]:

    G_max − E[G_Exp3]  ≤  (e − 1) · γ · G_max  +  (K ln K)/γ

The two terms are the trade-off, made completely explicit. (e−1)γ G_max is the price of the forced uniform exploration — proportional to γ. (K ln K)/γ is the price of learning slowly — inversely proportional to γ. Balancing them is elementary calculus, which is exactly what the corollary does.

Corollary 3.2. For any T > 0, assume g ≥ G_max and run EXP3 with

    γ  =  min { 1,  √( K ln K / ((e−1) g) ) }

Then

    G_max − E[G_Exp3]  ≤  2√(e−1) · √(g K ln K)  ≤  2.63 · √(g K ln K)

Since no action can pay more than 1 per trial, g = T is always a legal choice when the horizon is known, giving regret ≤ 2.63√(T K ln K). The paper also notes that if rewards live in [a,b] rather than [0,1], rescaling gives (b−a)·2√(e−1)·√(TK ln K).

Note what is absent: no Δ, no distributional assumption, no gap. The bound holds “for any assignment of rewards” — including one written by an adversary who read your code.

Why √T and not log T

Because √T is optimal here, and the paper proves it. Theorem 5.1:

For any number of actions K ≥ 2 and for any time horizon T, there exists a distribution over the assignment of rewards such that the expected weak regret of any algorithm is at least (1/20)·min{√(KT), T}.

Read that carefully: any algorithm, including randomised ones, including ones tuned for the instance. The √(KT) is a floor, not an artefact of EXP3’s analysis. EXP3.1 (the horizon-free variant) achieves O(√(KT ln K)), so the remaining gap between upper and lower bound is a factor √(ln K) — closed later by MOSS and INF/Poly-INF (Audibert & Bubeck; see Bubeck & Cesa-Bianchi’s survey).

The intuition for why the stochastic log T is unavailable: in the stochastic case, an arm’s mean is a fixed target and confidence intervals shrink like 1/√n, so after O(log T/Δ²) pulls you can rule an arm out permanently. Against an adversary there is nothing to rule out — an arm that has paid nothing for a million rounds may pay 1 on every remaining round, so the learner can never stop hedging. The γ/K floor in EXP3 is that permanent hedge, and its cost is exactly √T.

Auer et al. also note the lower bound’s K dependence is stronger than the Θ(√(T ln K)) obtainable from full-information results: “our lower bound implies that no upper bound is possible of the form O(T^α (ln K)^β) where 0 ≤ α < 1, β > 0.” That is the precise statement of the √K price of bandit feedback.

The bridge to games — the P6 rung

This is why the note belongs to Games and Strategic Systems in C MOC as well as to recommendation. Auer et al. devote their §9 to repeated games, and Theorem 9.3 is the payoff:

Let M be an unknown game matrix in [a,b]^{n×m} with value v. Suppose the row player, knowing only a, b and n, uses the mixed strategy EXP3.1. Then the row player’s expected payoff per round is at least

    v  −  8√(e−1)·√(n ln n / T)  −  8(e−1)·(n/T)  −  2·(n ln n / T)

Unpack what that says. v is the minimax value of the zero-sum game — by von Neumann’s theorem, max_p min_q pᵀMq = min_q max_p pᵀMq, the payoff the row player can guarantee if she knows the matrix and solves it with linear programming. Theorem 9.3 says a player who knows only the number of her own strategies and the range of the payoffs — not the matrix, not the opponent’s strategy set, not even the opponent’s moves, since bandit feedback shows her only her own realised payoff — converges to that same guarantee at rate O(√(n ln n / T)). Their Corollary 9.2 states the general form: EXP3.P.1 is Hannan-consistent in the unknown game setup.

That is the entire conceptual content of the “learning in games” programme in three lines, and it is the direct ancestor of Counterfactual Regret Minimization: CFR is what you get when you decompose this regret per information set in an extensive-form game and let both players run a no-regret learner in self-play. The zero-sum restriction is essential in both cases and is developed properly in Regret and No-Regret Learning — with more than two players, or non-zero-sum payoffs, no-regret play converges to the set of coarse correlated equilibria, not to Nash. See also The Price of Anarchy, which measures the welfare gap of exactly those equilibria.

sequenceDiagram
    participant R as Row player<br/>(runs EXP3.1)
    participant G as Unknown game<br/>matrix M
    participant C as Column player<br/>(arbitrary, may be adaptive)
    Note over R: knows only n (own strategies)<br/>and the payoff range [a,b]
    loop T rounds
        R->>R: p(t) = (1−γ)·softmax(Ĝ) + γ/n
        R->>G: sample row i_t ~ p(t)
        C->>G: choose column j_t (any rule)
        G-->>R: payoff M[i_t][j_t] ONLY
        Note right of R: bandit feedback:<br/>never sees j_t, never sees<br/>M[i][j_t] for i ≠ i_t
        R->>R: x̂ = payoff / p_{i_t}(t), then reweight
    end
    Note over R,C: Theorem 9.3: expected payoff per round<br/>≥ v − 8√(e−1)·√(n ln n / T) − …<br/>where v is the minimax value of M

What it shows: one round of the unknown-game protocol, with the information the row player does and does not receive. The insight: the row player never learns the game. She never sees the opponent’s move, never sees the matrix, and still converges to the value she would have obtained by solving the matrix with linear programming — at rate 1/√T. This is the sense in which regret minimisation replaces equilibrium computation when the game is too large to write down, and it is the reason Counterfactual Regret Minimization can solve poker without ever building the strategic-form matrix.

Measured: Reproducing the Bounds

Everything in this section was computed for this note on 2026-08-29 using only the Python standard library (random, math, statistics — no numpy), on a Fedora Linux box, with fixed seeds so every number is reproducible. UCB1 uses the theorem-honest constant (x̄_j + √(2 ln n / n_j)); Thompson sampling uses Beta(1,1) priors and random.betavariate; ε_n-greedy uses Auer et al.’s exact schedule ε_n = min{1, cK/(d²n)}. Every figure is a mean over independent runs with the run count stated.

Experiment 1 — regret curves and the ε-greedy / UCB1 crossover

Instance D: K = 5, μ = [0.8, 0.5, 0.5, 0.5, 0.5], gap Δ = 0.30, T = 60{,}000, 200 runs.

t	100	300	1,000	3,000	10,000	30,000	60,000
ε-greedy ε=0.10	9.7	17.2	34.9	82.7	250.4	728.8	1448.5
ε-greedy ε=0.01	9.6	21.7	52.0	87.6	115.6	163.5	235.1
UCB1	18.2	42.4	85.6	131.1	183.1	228.7	256.0
Thompson sampling	11.5	16.4	21.0	25.0	29.6	34.3	37.6

The crossover: UCB1 does not overtake ε-greedy (ε = 0.1) until t = 6{,}422. Before that point the flat-tax algorithm is strictly better, because UCB1 is still paying its start-up cost of pulling every arm until the confidence widths separate. After it, ε-greedy’s linear term takes over and the gap widens without limit — by T = 60{,}000 ε-greedy has 5.7× the regret.

Two further crossovers from the same run: Thompson sampling overtakes ε-greedy(0.1) at t = 222 and overtakes UCB1 at t = 11 — essentially immediately. And ε-greedy with ε = 0.01 (235.1) is still ahead of UCB1 (256.0) at T = 60{,}000; its linear slope is only 0.01 × 0.8 × 0.3 = 0.0024 per round, so its crossover with UCB1 lies beyond the 60,000-round horizon I measured. Tuning ε down buys a lot of horizon.

Instance A: K = 10, μ = [0.5, 0.4 × 9], gap Δ = 0.10, T = 200{,}000, 40 runs.

t	1,000	10,000	30,000	60,000	100,000	140,000	200,000
ε-greedy ε=0.10	49.7	210.1	390.8	661.3	1019.8	1380.0	1918.6
UCB1	83.2	593.7	1037.0	1328.0	1514.7	1643.5	1767.6
Thompson sampling	69.5	161.7	202.8	230.0	249.3	263.6	279.7

Here UCB1 does not overtake ε-greedy(0.1) until t = 178{,}766 — nearly 180,000 rounds. With ten arms and a gap of 0.1, UCB1’s logarithmic constant 8(K−1)/Δ = 720 per ln n is so large that the asymptotic advantage is invisible for the entire horizon most A/B tests ever reach. This is the single most practically important measurement in this note: the textbook ordering UCB1 > ε-greedy is an asymptotic statement, and the asymptote can be six figures away.

xychart-beta
    title "Instance A (K=10, Δ=0.10): cumulative regret, mean of 40 runs"
    x-axis "rounds t (thousands)" [1, 10, 30, 60, 100, 140, 200]
    y-axis "cumulative regret" 0 --> 2000
    line "epsilon-greedy 0.10" [49.7, 210.1, 390.8, 661.3, 1019.8, 1380.0, 1918.6]
    line "UCB1" [83.2, 593.7, 1037.0, 1328.0, 1514.7, 1643.5, 1767.6]
    line "Thompson sampling" [69.5, 161.7, 202.8, 230.0, 249.3, 263.6, 279.7]

What it shows: the three measured regret curves on a ten-armed Bernoulli bandit with a 0.1 gap. The insight: the two curve shapes are the theory made visible — ε-greedy’s line is straight (linear regret), UCB1’s flattens (logarithmic regret), and they cross late, at t ≈ 178{,}800. Thompson sampling is not merely lower but flattens fastest, which is the practical meaning of “asymptotically optimal constant”.

Experiment 2 — Thompson sampling’s variance advantage

The mean regret is only half the story; a production system also cares about the tail. All figures from 200 runs on instance A at T = 30{,}000:

Algorithm	mean	std. dev.	median	p90	min	max
ε-greedy ε=0.10	408.5	226.1	312.6	720.8	269.3	1594.1
ε-greedy ε=0.01	784.6	1000.8	280.5	2993.6	29.3	2997.6
εn-greedy (c=5, true d)	1256.0	7.6	1256.0	1266.0	1236.4	1276.1
UCB1	1052.6	91.6	1054.1	1175.2	835.7	1299.8
Thompson sampling	204.7	42.1	201.7	251.3	121.2	459.9

Thompson sampling wins on the mean and on the spread: its standard deviation (42.1) is less than half UCB1’s (91.6), a fifth of ε-greedy(0.1)‘s (226.1), and 1/24th of ε-greedy(0.01)‘s (1000.8). Its worst run over 200 (459.9) is better than ε-greedy(0.1)‘s median run.

The ε-greedy(0.01) row is the cautionary tale, and it is worth understanding mechanically rather than statistically. With ε = 0.01 and K = 10, each arm gets an exploration pull roughly once per 1,000 rounds. If the greedy arm locks onto a suboptimal arm early — which happens whenever a bad arm’s first few Bernoulli draws are lucky — the algorithm needs thousands of rounds of forced exploration to accumulate enough evidence to switch. The result is a bimodal distribution: median 280.5 (it usually locks onto the right arm and does beautifully, min 29.3) but p90 of 2,993.6 and max 2,997.6, which is essentially the ceiling 0.9 · Δ · T = 2700 plus exploration cost. Roughly one run in six locks onto the wrong arm and never recovers within the horizon. Averaging that with the good runs produces a mean (784.6) that describes no actual run. ε_n-greedy with the true gap sits at the opposite extreme: worse on the mean (1256.0) but with a standard deviation of 7.6, i.e. it does the same thing every time.

Thompson sampling avoids the lock-in failure structurally: the posterior for a rarely-pulled arm stays wide, so its sample keeps occasionally winning, and the arm keeps getting retried at a rate proportional to how plausible it still is. Sampling is an adaptive ε.

Experiment 3 — verifying UCB1’s Theorem 1

Theorem 1 is an upper bound, so the check is that measurement sits below it and that the ratio is stable:

Instance	T	Theorem 1 bound	measured UCB1 regret	ratio (bound/measured)
D (K=5, Δ=0.30)	60,000	1178.7	256.0	4.60
A (K=10, Δ=0.10)	30,000	7426.3	1052.6	7.06
A (K=10, Δ=0.10)	200,000	8792.2	1767.6	4.97

The bound holds in every case, and is loose by roughly 5–7× — consistent with the analysis: the factor-of-4 Hoeffding-versus-Pinsker slack identified by Auer et al. themselves, plus union-bound slack. Worth noting how slowly the bound moves: from T = 30{,}000 to T = 200{,}000 (6.7×) it rises only from 7,426 to 8,792, because it is logarithmic. Measured regret rose from 1,053 to 1,768 (1.68×), also logarithmic. The bound is the right shape, wrong constant — which is exactly what the theory says.

Experiment 4 — a deterministic algorithm against an adversary

The construction, exactly as described earlier: simulate UCB1 offline; on each round, set the arm UCB1 is about to choose to reward 0 and every other arm to reward 1. Because UCB1 is deterministic, the resulting T × K matrix is fixed in advance and is a legitimate oblivious adversary — no adaptivity is required. K = 10, T = 30{,}000.

	measured weak regret	as fraction of T
Best fixed arm in hindsight G_max	27,000 of 30,000	—
UCB1 (deterministic)	27,000	90.0%
ε-greedy ε=0.1 (50 runs)	44	0.15%
EXP3 (γ = 0.02113, 50 runs)	4 ± 58	0.01%
Corollary 3.2 upper bound, g = T	2,186	—
Theorem 5.1 lower bound (1/20)√(KT)	27	—

UCB1 collects literally zero reward over 30,000 rounds while a fixed arm would have collected 27,000. The regret is 90% of the horizon, matching the T(1 − 1/K) prediction exactly. Meanwhile EXP3’s regret on the same fixed sequence is 4 ± 58, statistically indistinguishable from zero, and even ε-greedy — whose randomised component is enough to break the construction — loses only 44.

The honest reading: this sequence is tailored to UCB1 specifically, so EXP3’s near-zero regret is not evidence that EXP3 is achieving its √T bound, only that the attack does not transfer. Randomisation is not a small robustness improvement; it is the difference between 90% and 0.01% of the horizon. That single fact is why every game-playing algorithm in Games and Strategic Systems in C MOC outputs a mixed strategy.

Experiment 5 — the √(KT) rate, measured

To actually exercise EXP3’s √T regime I used the minimax scaling: K = 10 arms with gap ε = √(K/T), the hardest instance size for each horizon (this is where the instance-dependent log(T)/Δ and the worst-case √(KT) bounds meet).

T	gap	EXP3	/√(KT)	UCB1	/√(KT)	Thompson	/√(KT)	√(KT)
2,000	0.0707	119.8	0.847	117.6	0.831	95.0	0.672	141.4
8,000	0.0354	236.8	0.837	237.7	0.840	198.5	0.702	282.8
32,000	0.0177	464.2	0.821	476.3	0.842	380.1	0.672	565.7
128,000	0.0088	950.3	0.840	978.0	0.864	863.0	0.763	1131.4

Across a 64-fold increase in horizon, EXP3’s regret normalised by √(KT) stays flat at 0.82–0.85. That is √T scaling measured, not asserted. And the sandwich holds: Theorem 5.1’s lower bound is 0.05·√(KT), Corollary 3.2’s upper bound with g = T is 2.63√(ln K) = 3.99 in the same units, and the measurement sits at 0.84 — comfortably between them.

Note also that UCB1 and EXP3 are indistinguishable in this regime (0.83–0.86 vs 0.82–0.85). In the minimax regime the stochastic structure buys you nothing, because the gaps are precisely too small to identify within the horizon. UCB1’s advantage exists only when Δ ≫ √(K/T).

Experiment 6 — what robustness costs, and when nothing matters

The price of EXP3 on a stochastic problem. On instance A (K=10, Δ=0.1, T=30{,}000), EXP3 with γ tuned per Corollary 3.2 scored pseudo-regret 1179.0 ± 121.7 (50 runs), against UCB1’s 1052.6 and Thompson sampling’s 204.7. So the adversarial insurance costs about 12% versus UCB1 and 5.8× versus Thompson sampling on this instance. Compare that to the 90%-of-horizon catastrophe UCB1 suffers in the other direction, and the asymmetry argued earlier is quantified: choosing the adversarial algorithm when the world is stochastic is cheap; choosing the stochastic algorithm when the world is adversarial is not.

When the algorithm choice does not matter at all. Instance B: K = 10, μ = [0.5, 0.48 × 9], gap Δ = 0.02, T = 30{,}000, 200 runs:

Algorithm	regret at T = 30{,}000
ε-greedy ε=0.10	350.5
ε-greedy ε=0.01	428.9
Thompson sampling	375.7
UCB1	501.8
εn-greedy	539.9
Uniform random (ceiling)	0.9 · 0.02 · 30000 = 540.0

Every algorithm is within a factor of 1.5 of pure random guessing, and UCB1 and ε_n-greedy are within 8% of it. The reason is a sample-size argument, not an algorithmic one: distinguishing 0.50 from 0.48 needs on the order of 1/Δ² = 2{,}500 observations per arm, i.e. 25,000 of the 30,000 rounds, so there is no horizon left in which to exploit what was learned. Any bandit deployment where T ≪ K/Δ² is running an expensive random-number generator. Estimate that ratio before shipping.

Contextual Bandits and LinUCB: When Every Request Is a Different Problem

Everything above assumes one global “best arm”. Recommendation almost never works that way — the best article for a 22-year-old in São Paulo is not the best article for a 60-year-old in Osaka. The contextual bandit (also called bandit with side information, or associative reinforcement learning) adds a feature vector observed before the choice:

1. At round t, observe a context: for each arm a in the (possibly changing) arm set A_t, a feature vector x_{t,a} ∈ ℝ^d.
2. Choose a_t ∈ A_t, observe payoff r_t for that arm only.
3. Improve the policy using (x_{t,a_t}, a_t, r_t).

The crucial structural gain is generalisation across arms. In a plain K-armed bandit, knowledge about arm 1 says nothing about arm 2, so a catalogue of a million items needs a million independent estimates. With shared parameters, one observation informs every arm whose features overlap — which is what makes bandits usable at web scale and is why Cold Start Problem handling is the canonical application.

LinUCB

Li, Chu, Langford & Schapire (WWW 2010) assume the payoff is linear in the features: E[r_{t,a} | x_{t,a}] = x_{t,a}ᵀ θ*_a (their Eq. 2). The model is called disjoint because each arm has its own θ*_a, not shared across arms. Algorithm 1, read from the rendered page:

Inputs: α ∈ ℝ₊
for t = 1, 2, 3, …, T do
    Observe features of all arms a ∈ A_t:  x_{t,a} ∈ ℝ^d
    for all a ∈ A_t do
        if a is new then
            A_a ← I_d            (d-dimensional identity matrix)
            b_a ← 0_{d×1}        (d-dimensional zero vector)
        end if
        θ̂_a  ← A_a⁻¹ b_a
        p_{t,a} ← θ̂_aᵀ x_{t,a}  +  α · √( x_{t,a}ᵀ A_a⁻¹ x_{t,a} )
    end for
    Choose arm a_t = argmax_{a ∈ A_t} p_{t,a}, ties broken arbitrarily; observe payoff r_t
    A_{a_t} ← A_{a_t} + x_{t,a_t} x_{t,a_t}ᵀ
    b_{a_t} ← b_{a_t} + r_t x_{t,a_t}
end for

Symbol by symbol, and note how exactly it mirrors UCB1:

• A_a — the d × d regularised design matrix D_aᵀD_a + I_d, accumulating outer products of the feature vectors seen for arm a. Initialising to I_d is the ridge regularisation.
• b_a — the d-vector accumulating Σ r · x, the feature/reward cross-product.
• θ̂_a = A_a⁻¹ b_a — the ridge regression solution. This is the exploitation term: θ̂_aᵀ x_{t,a} is the predicted payoff, playing the role of x̄_j in UCB1.
• √(x_{t,a}ᵀ A_a⁻¹ x_{t,a}) — the exploration bonus: the standard deviation of the ridge prediction at the point x_{t,a}. It is large in feature-space directions where little data has been collected. This is √(2 ln n/n_j) generalised from “how many times have I pulled this arm” to “how much have I observed in this direction of feature space”.
• α — the single tunable exploration multiplier, the analogue of UCB1’s √2.

Everything stays d × d regardless of how much data arrives, and the inverses can be cached, so the per-round cost is fixed. The paper notes that for the hybrid model the per-trial complexity is O(d² + k²). The authors state that for a fixed arm set of K arms the analysis of Chu et al. gives a regret bound of Õ(√(KdT)). This note keeps LinUCB compact deliberately; the full treatment is LinUCB.

The Yahoo! front-page result, with the measured numbers

The empirical study is the reason this paper is cited, and the numbers deserve to be stated precisely rather than gestured at.

• Data. Events from a random bucket on the Yahoo! Front Page Today Module, May 2009. In the random bucket, articles were selected uniformly at random from the pool. About 4.7 million events on May 01 (used for parameter tuning); about 36 million events May 03–09 (evaluation). The abstract describes the dataset as “over 33 million events.”
• Features. Users and articles each reduced to a six-dimensional vector (five soft cluster memberships from K-means plus a constant 1). The outer product gives 6 × 6 = 36 shared features z_{t,a} ∈ ℝ³⁶ for the hybrid model.
• Metric. Relative CTR — an algorithm’s click-through rate divided by the random policy’s. Reported separately for a small “learning bucket” (where the algorithm explores) and a larger “deployment bucket” (where the current best estimate is served).

Selected rows of their Table 1, with lift measured against ε-greedy:

Algorithm	CTR (deploy, 100% data)	lift	CTR (deploy, 1% data)	lift
ε-greedy (baseline)	1.596	—	1.234	—
ucb	1.594	0%	1.354	9.7%
ε-greedy (disjoint)	1.769	10.8%	1.262	2.3%
linucb (disjoint)	1.795	12.5%	1.382	12%
linucb (hybrid)	1.730	8.4%	1.482	20.1%
omniscient (best context-free policy in hindsight)	1.615	—	—	—

The three facts worth carrying away:

1. 12.5% click lift for LinUCB (disjoint) over ε-greedy in the deployment bucket on the full week — the number quoted in the abstract.
2. LinUCB beats the omniscient context-free policy (1.795 vs 1.615). The omniscient baseline computes each article’s empirical CTR from the logged data and always serves the best — it cannot be beaten by any non-personalised policy, even with hindsight. Beating it is proof that the lift comes from personalisation, not from better exploration.
3. The advantage grows as data gets scarcer. At 1% of the training data, hybrid LinUCB’s lift rises to 20.1% (deploy) and 27% (learn), versus 8.4%/25.4% at 100%. Feature sharing is worth most exactly when per-arm data is thin — which is the cold-start regime.

The paper’s own honest caveat, worth quoting because it contradicts the folk claim that UCB beats ε-greedy: “ε-greedy algorithms achieved similar CTR as upper confidence bound ones in the deployment bucket when appropriate parameters were used. Thus, both types of algorithms appeared to learn comparable policies. However, they seemed to have lower CTR in the learning bucket.” The UCB advantage was in learning speed, not in the quality of the deployed policy.

Offline Evaluation: The Replay Method

You cannot evaluate a bandit algorithm on a logged dataset the way you evaluate a classifier, and the reason is the same partial-label problem that defines the bandit setting: the log records a reward only for the arm the logging policy chose, and the algorithm under evaluation will usually want a different one. Li, Chu, Langford & Wang (WSDM 2011) call the obvious alternative — building a simulator — out for what it is: “the modeling step will introduce bias in the simulator and so make it hard to justify the reliability of this simulator-based evaluation.”

Their replay method is startlingly simple. Algorithm 1, verbatim:

Algorithm 1  Policy_Evaluator (with infinite data stream)
 0: Inputs: T > 0; bandit algorithm A; stream of events S
 1: h₀ ← ∅                        {an initially empty history}
 2: Ĝ_A ← 0                       {an initially zero total payoff}
 3: for t = 1, 2, 3, …, T do
 4:   repeat
 5:      get next event (x, a, r_a) from S
 6:   until A(h_{t−1}, x) = a      {the algorithm's choice matches the logged arm}
 7:   h_t ← concatenate(h_{t−1}, (x, a, r_a))
 8:   Ĝ_A ← Ĝ_A + r_a
 9: end for
10: Output: Ĝ_A / T

The mechanism, in one sentence: step through the log; if the algorithm would have chosen the arm that was actually logged, keep the event and feed the reward to the algorithm; otherwise discard the event entirely and move on. No modelling, no simulator, no importance weights.

Why it is unbiased rests entirely on the logging policy. The paper’s argument: “because the logging policy chooses each arm uniformly at random, each event is retained by this algorithm with probability exactly 1/K, independent of everything else. This means that the events which are retained have the same distribution as if they were selected by D.” Formally, Theorem 1 states that for all distributions D, all algorithms A, all T, and all streams S of i.i.d. events from a uniformly random logging policy,

    Pr_{Policy_Evaluator(A,S)}(h_T)  =  Pr_{A,D}(h_T)

— every history has identical probability under replay as in the real world, so any statistic of histories (including Ĝ_A/T) is unbiased. The theorem also quantifies the cost: the expected number of logged events L consumed to produce a length-T history is E[L] = KT, and with probability at least 1 − δ, L ≤ 2K(T + ln(1/δ)).

Three practical consequences follow immediately:

1. You must have run a uniformly random bucket to do this. Replay is unbiased only against uniform logging. If your log came from your current production ranker, the retained events are not distributed like D and the estimate is biased in favour of policies that resemble the logger. This is the single most common misapplication.
2. You burn a factor of K of your log. A million logged events with K = 20 arms yields roughly 50,000 evaluation rounds. This is why the Yahoo! study needed 36 million events to evaluate a 20-ish-arm problem, and why the random bucket has to be big enough to be statistically useful while small enough not to hurt users.
3. Longer evaluations get progressively noisier, not just shorter. Algorithm 2 (the finite-stream variant) has a random number of valid events with mean L/K; the paper’s Theorem 2 bounds the error as O(√((K g_π / L)·ln(1/δ))) with probability 1 − δ.

flowchart TD
    LOG["Logged event stream S<br/>from a UNIFORMLY RANDOM<br/>logging policy"] --> EV["Next event (x, a, r_a)"]
    EV --> ASK{"Would policy A,<br/>given history h and context x,<br/>have chosen arm a?"}
    ASK -->|"yes — probability exactly 1/K"| KEEP["Append to history<br/>Ĝ_A += r_a<br/>t += 1"]
    ASK -->|"no"| DROP["Discard the event entirely.<br/>History unchanged."]
    KEEP --> EV
    DROP --> EV
    KEEP --> DONE{"t = T ?"}
    DONE -->|yes| OUT["Output Ĝ_A / T<br/><b>unbiased</b> (Theorem 1)"]
    NOTE["Cost: E[L] = K·T logged events<br/>consumed per T evaluation rounds"] -.-> OUT

What it shows: the rejection-sampling loop at the heart of unbiased offline bandit evaluation. The insight: the whole method is a rejection sampler, and its correctness hinges on the single node labelled uniformly random logging policy — that is what makes the acceptance probability exactly 1/K and therefore independent of the arm, the context, and the history. Change the logger to anything non-uniform and the acceptance probability becomes arm-dependent, the retained sample stops matching D, and the estimate silently becomes biased. There is no error message; the numbers just come out wrong.

The Comparison Table

Everything above, in one grid. Regret columns state the published bound with its source; “measured” columns are from the simulations in this note (instance A: K=10, Δ=0.10).

Algorithm	Regret bound	Assumptions it needs	Tuning	Randomised?	Measured R(200k) on instance A	Choose it when
ε-greedy, constant ε	Θ(ε·((K−1)/K)·Δ̄·T) — linear (Auer et al. §2)	none	ε	yes	1918.6	short horizons; you need uniform-random logging for offline eval; you need a knob a PM can reason about
εn-greedy ε_n = min{1, cK/(d²n)}	instantaneous regret O(c/(d²n)) ⇒ cumulative Θ(log n) (Auer et al. Thm 3)	bounded rewards in [0,1]; a known lower bound d on the gap	c, d	yes	— (1256.0 at T=30k)	you genuinely know a gap lower bound, and want very low variance (measured sd 7.6)
UCB1 x̄_j + √(2 ln n/n_j)	8 Σ_{i}(ln n)/Δ_i + (1+π²/3)Σ_j Δ_j (Auer et al. Thm 1)	rewards i.i.d. with support in [0,1]; stationary; immediate feedback	none (or c)	no	1767.6	you need determinism/reproducibility; you have no gap knowledge; the environment is genuinely stochastic
UCB2	leading constant → 1/(2Δ_j²) (Auer et al. Thm 2)	as UCB1	α	no	—	you want UCB1’s constant improved by ~4× and can accept epoch bookkeeping
KL-UCB	reaches the Lai–Robbins bound for Bernoulli (Garivier & Cappé)	bounded rewards; exponential-family variants	none	no	—	Bernoulli rewards and you want the asymptotically optimal constant with a deterministic policy
Thompson sampling (Beta–Bernoulli)	(1+ε)Σ_a Δ_a(ln T + ln ln T)/K(μ_a,μ*) + C — asymptotically optimal (Kaufmann et al. Thm 1); earlier O((Σ 1/Δ_i²)² ln T) (Agrawal & Goyal)	a workable prior/posterior; stationary	prior (and optionally a variance scale α)	yes	279.7	almost always, in stochastic settings — best mean and lowest variance measured; robust to delayed/batched feedback
EXP3	2.63√(g K ln K) with g ≥ G_max (Auer et al. Cor. 3.2)	none at all — arbitrary rewards in [0,1]	γ (or use EXP3.1)	necessarily	1179.0 at T=30k (vs UCB1’s 1052.6)	rewards may be adversarial, strategic, or wildly non-stationary; you are playing against another agent
EXP3.P / EXP3.1	O(√(KT ln(KT/δ))) w.p. 1−δ; horizon-free	none	α, δ	yes	—	you need a high-probability bound, not just an expectation — raw EXP3’s regret can reach T^{3/4} on a bad run
LinUCB	Õ(√(KdT)) for fixed arm sets (Li et al. §3.1)	payoff linear in features: `E[r	x] = xᵀθ*`	α	no	—
Lower bounds	stochastic: Σ Δ_i ln(T)/d_inf (Lai–Robbins) · adversarial: (1/20)min{√(KT),T} (Auer et al. Thm 5.1)	consistency (stochastic)	—	—	—	the floors nothing can beat

Failure Modes and Gotchas

Constant ε never stops paying. The regret is linear, exactly ε·((K−1)/K)·Δ̄ per round forever. Measured: 270 of ε-greedy(0.1)‘s 408.5 regret at T = 30{,}000 on instance A is this floor. Symptom: a regret curve that is visibly a straight line on a linear-t plot after the first few thousand rounds. Diagnosis: plot cumulative regret against t; logarithmic algorithms bend, ε-greedy does not. Fix: decay ε, or switch to Thompson sampling.

Small ε is bimodal, and the mean lies. Measured on 200 runs at ε = 0.01: mean 784.6, median 280.5, p90 2993.6, min 29.3, max 2997.6. Roughly one run in six locks onto a suboptimal arm early and never escapes within the horizon; the rest do beautifully. The mean describes no actual run. Symptom: huge run-to-run variance in an A/B test with no obvious cause. Diagnosis: look at the distribution of outcomes across independent runs, never the average. Fix: Thompson sampling, whose measured standard deviation on the same instance was 42.1 versus 1000.8.

UCB1 against anything adaptive is a disaster, not a degradation. Because it is deterministic, an adversary who can simulate it forces linear regret. Measured on a 10-armed, 30,000-round oblivious sequence built by simulating UCB1: UCB1 collected exactly zero reward while the best fixed arm collected 27,000 — 90% of the horizon lost. Symptom: an exploration system whose performance collapses when an opposing optimiser (a competing bidder, an SEO adversary, a spam ring, another team’s ranker) is present. Diagnosis: ask whether anything in the loop can observe and react to your choices. Fix: randomise — EXP3, or Thompson sampling, or at minimum an ε floor.

T ≪ K/Δ² means you are shipping a random number generator. Measured on instance B (K=10, Δ=0.02, T=30{,}000): every algorithm landed between 350 and 540 regret against a uniform-random ceiling of 540 — UCB1 (501.8) and ε_n-greedy (539.9) were within 8% of pure guessing. Distinguishing 0.50 from 0.48 needs ~1/Δ² = 2{,}500 samples per arm; ten arms consumes 25,000 of the 30,000 rounds and leaves no horizon in which to exploit. Diagnosis: before building anything, compute K/Δ² from a pilot estimate of the gap and compare it to your realistic traffic. Fix: fewer arms, or a contextual model that shares statistical strength across arms, or accept that the choice does not matter and pick the cheapest to operate.

The Lai–Robbins bound is a lim inf, and reading it as a per-T inequality produces false alarms. Measured: Thompson sampling’s E[N_sub]·KL/ln T was 0.450 at T = 10⁴, i.e. below the “lower bound” of 1.0, rising to 0.604 at T = 10⁶. Nothing is violated — the bound is asymptotic, Kaufmann et al.’s matching upper bound carries an additive C(ε, μ) and a ln ln T, and the ratio is climbing toward 1 as it should. Diagnosis: if a measured quantity appears to beat an asymptotic bound, check the quantifier before checking the code.

Delayed and batched feedback breaks deterministic algorithms much harder than randomised ones. Chapelle & Li’s Table 1, 10 items, T = 10⁶, 100 repetitions, feedback delivered every δ steps:

δ (delay)	1	3	10	32	100	316	1000
UCB regret	24,145	24,695	25,662	28,148	37,141	77,687	226,220
Thompson sampling regret	9,105	9,199	9,049	9,451	11,550	21,594	59,256
ratio UCB/TS	2.65	2.68	2.84	2.98	3.22	3.60	3.82

At δ = 1000, UCB’s regret is 9.4× its own no-delay regret; Thompson sampling’s is 6.5×, and the gap between them widens from 2.65× to 3.82×. The mechanism is stated by the authors: “Thompson sampling alleviates the influence of delayed feedback by randomizing over actions; on the other hand, UCB is deterministic and suffers a larger regret in case of a sub-optimal choice.” A deterministic index that has not been updated picks the same arm for every request in the batch; a sampler spreads the batch across arms in proportion to their posterior probability of being best. This matters in every real system, because no production recommender updates its statistics per-request.

Offline replay against a non-uniform log is silently biased. Li et al.’s Theorem 1 requires “i.i.d. events from a uniformly random logging policy”. Replay against production-ranker logs retains events non-uniformly and systematically flatters policies that resemble the logger. There is no error and no warning — the numbers simply come out wrong, usually optimistically. Fix: maintain a genuine random bucket, or log propensities and use inverse-propensity scoring instead (Vowpal Wabbit exposes this as --cb_type ips).

Replay burns a factor of K of your log. E[L] = KT (Li et al. Theorem 1). Ten million logged events with 50 arms yields 200,000 evaluation rounds. Budget for it before promising an offline evaluation.

Non-stationarity defeats every algorithm in this note as written. All the bounds assume fixed μ_i. Russo et al.’s tutorial §6.3 is explicit about both the fix and its limit: “the agent should never stop exploring, since it needs to track changes as the system drifts. With minor modification, TS remains an effective approach so long as model parameters change little over durations that are sufficient to identify effective actions.” The two standard modifications are a sliding window (condition only on the most recent τ observations) and discounting the posterior toward the prior at rate γ — they call the latter nonstationary TS. Their caveat is the important part: “due to nonstationarity, no algorithm can promise regret that vanishes with time.”

Thompson sampling is the wrong choice when exploration is not needed. Russo et al. §8.2.1: “TS is a poor choice for problems where learning does not require active exploration. In such contexts, TS is usually outperformed by greedier algorithms that do not invest in exploration.” If the reward signal is dense and every action is observed anyway, a plain greedy policy on a well-fit model wins.

Reward scaling silently voids UCB1’s theorem. Theorem 1 assumes “support in [0,1]”. Feeding it dwell time in seconds, or revenue in dollars, makes the √(2 ln n/n_j) bonus negligible relative to the mean, and UCB1 degenerates into greedy. Rescale to [0,1] — and note that EXP3 has the same requirement, with Auer et al. giving the explicit (b−a) rescaling factor for rewards in [a,b].

Alternatives and When to Choose Them

A/B testing. The default alternative, and often the right one. A fixed-split A/B test allocates traffic uniformly for a fixed duration and then commits — it is explore-then-commit with a human deciding the commit point. It gives clean frequentist inference, a p-value stakeholders recognise, and no risk of an adaptive algorithm confounding the estimate. Its cost is exactly the regret a bandit saves: with K variants and a fixed split, (K−1)/K of the traffic during the test goes to a variant that will be discarded. Choose A/B when you need a defensible causal estimate of each variant’s effect; choose a bandit when you need cumulative reward and do not much care about per-arm confidence intervals. They answer different questions, and a bandit’s adaptive allocation is precisely what makes naive significance testing on its output invalid.

Best-arm identification (pure exploration). A different objective: minimise the probability of returning the wrong arm at the end, ignoring the reward collected along the way. The optimal algorithms differ (successive halving, LUCB, Track-and-Stop), and running a regret-minimising bandit and reading off its argmax is not the right way to identify the best arm — regret minimisation deliberately under-samples arms it has already ruled out, which is the opposite of what a confident final answer needs. Lattimore & Szepesvári devote Part VI to this.

Bayesian optimisation / Gaussian-process bandits. For continuous or very large structured action spaces with expensive evaluations (hyperparameter tuning, materials search). Same optimism-under-uncertainty logic, but the surrogate is a Gaussian process rather than K independent counters. Choose it when actions are points in a continuous space and evaluations are expensive; choose a K-armed bandit when actions are a discrete finite menu and evaluations are cheap and plentiful.

Full reinforcement learning. A bandit is a one-state Markov decision process: your action does not change the state you land in next. The moment actions have delayed consequences that change future opportunities — a recommendation that alters what the user will be interested in tomorrow, an ad that fatigues the audience — the bandit model is misspecified and you need full reinforcement-learning machinery with value functions and credit assignment (no note in this vault yet). Li et al. note this explicitly: offline bandit evaluation “may be viewed as a special case of the so-called ‘off-policy evaluation problem’ in reinforcement learning”. The bandit simplification is what buys you log T regret and unbiased replay; give it up only when you must.

Full-information online learning. If you actually get to see what every arm would have paid — a common situation in forecasting, portfolio selection, and expert aggregation — you are not in a bandit problem and should not pay bandit prices. Use Multiplicative Weights Update / Hedge, which achieves Θ(√(T ln K)) rather than Θ(√(KT)). See Regret and No-Regret Learning for the comparison.

Counterfactual Regret Minimization. When the environment is not nature but an opponent in an extensive-form game with hidden information, the right object is regret decomposed per information set, accumulated by tree traversal. Counterfactual Regret Minimization is that algorithm, and EXP3’s Theorem 9.3 (above) is the reason it works. Do not use a K-armed bandit on a game tree: the arm set is the set of whole strategies, which is astronomically large, and the whole point of CFR is to avoid enumerating it.

Production Notes

Uniform-random exploration buckets exist for evaluation, not just for learning. The Yahoo! front-page system ran a bucket in which “articles were randomly selected from the article pool to serve users” (Li et al. 2010 §5.2.1) — about 4.7 million events on a single day in May 2009. That bucket is what made the unbiased replay evaluation of Li et al. 2011 possible at all. The engineering lesson generalises: a small permanently-random slice of traffic is infrastructure, and it is much cheaper to maintain continuously than to retrofit when you need to evaluate a new policy. Budget for E[L] = KT events consumed per T evaluation rounds when sizing it.

Separate the learning bucket from the deployment bucket, and expect different winners in each. The Yahoo! study reports both, and the numbers diverge sharply: ucb had a 0% CTR lift over ε-greedy in the deployment bucket but 18.3% in the learning bucket at full data. The paper explains why both matter: “Since the deployment bucket is often larger than the learning bucket, CTR in the deployment bucket is more important. However, a higher CTR in the learning bucket suggests a faster learning rate (or equivalently, smaller regret) for a bandit algorithm.” A team measuring only deployment CTR will conclude UCB is worthless; a team measuring only learning CTR will overstate it.

Batched updates are the normal case, and they favour randomised algorithms. No production system updates arm statistics per request; feedback arrives in minute-scale batches. Chapelle & Li’s delay study (table above) is the quantitative warning: at a 1000-step delay UCB’s regret rises 9.4× while Thompson sampling’s rises 6.5×, and the gap between them widens from 2.65× to 3.82×. Their news-recommendation experiment used update delays of 10, 30 and 60 minutes, and reports that “while the deterministic UCB works well with short delay, its performance drops significantly as the delay increases. In contrast, randomized algorithms” hold up. If your update cadence is minutes, this is the single most decision-relevant fact in this note.

Under-explore deliberately, and expect it to help. Chapelle & Li’s posterior reshaping trick divides the Beta posterior’s parameters by α, or equivalently scales the Gaussian posterior’s standard deviation by α < 1, to exploit more aggressively. Their display-advertising table shows the best result at α = 0.5 (3.72% CTR regret) rather than the theory-honest α = 1 (3.81%), and they note that α < 1 “yielded better regrets in the non-asymptotic regime”. This is the same phenomenon as practitioners shrinking UCB1’s √2. The theory is tuned for the asymptote; production lives before it.

Bandit libraries: what is actually available. Vowpal Wabbit is the widely-deployed open-source implementation of contextual bandits and exposes five exploration policies as flags: --first (explore-first), --epsilon (ε-greedy), --bag (bagging), --cover (online cover) and --softmax (softmax, --cb_explore_adf only), plus --cb_type ips for inverse-propensity-scored evaluation (verified against the VW contextual-bandit tutorial, 2026-08-29). Note that ε-greedy is the first exploration policy every such library ships, for the reasons given earlier: it produces a known propensity for every logged decision, which is what IPS needs.

Handle non-stationarity explicitly or it will handle you. Two standard modifications, both from Russo et al. §6.3: a sliding window — “ignoring historical observations made beyond some number τ of time periods in the past”, which means “the agent never ceases to explore, since the degree to which the posterior distribution can concentrate is limited by the number of observations taken into account” — and discounting, in which the posterior is repeatedly blended back toward the prior at rate γ (they use γ = 0.01 in their demonstration). Both convert an asymptotically-optimal algorithm into a tracking algorithm, and both give up vanishing regret in exchange: “due to nonstationarity, no algorithm can promise regret that vanishes with time.”

Scale to large catalogues by generalising, not by adding arms. A million-item catalogue cannot be a million arms — T ≪ K/Δ² guarantees failure (see Failure Modes). The three production routes, in increasing order of sophistication: (i) restrict the arm set to a small candidate list produced by a non-bandit retriever, and run the bandit only on the final slate; (ii) cluster items and treat clusters as arms; (iii) use a contextual model with parameters shared across arms — LinUCB’s hybrid model, or a neural policy — so that one observation informs many arms. The Yahoo! study is a worked example of (iii): five user clusters and five article clusters give a 36-dimensional shared feature space, and the payoff for sharing is largest exactly where data is thinnest (20.1% lift at 1% of the data, versus 8.4% at 100%).

Delayed and partial rewards need an explicit decision, not a default. A click arrives in seconds; a conversion in hours; retention in weeks. Bandit theory assumes the reward for round t is available before round t+1. Production systems either (a) use a fast proxy reward and accept the proxy-vs-goal mismatch, (b) attribute late rewards to their originating round and accept the delay penalty quantified above, or (c) both, with a fast model corrected periodically by a slow one. There is no free option; pick one deliberately and write down which.

See Also

• Recommender Systems MOC — the parent map; bandits sit under Multi-Armed Bandit / Exploration
• LinUCB — the contextual bandit sketched here in compact form, developed in full
• Cold Start Problem — the canonical application: bandits as the strategy for items with no history
• Beyond-Accuracy Objectives — exploration as a lever against popularity bias and feedback loops
• Recommender Algorithms Catalog — where bandits sit among the other families
• Recommender Systems — the umbrella concept
• Games and Strategic Systems in C MOC — the other parent; this note is the P6 rung’s entry point
• Regret and No-Regret Learning — external regret, Hannan consistency, and the full-information/bandit feedback split
• Multiplicative Weights Update — the full-information ancestor of EXP3; same algorithm, more feedback
• Counterfactual Regret Minimization — where EXP3’s Theorem 9.3 leads: regret minimisation on game trees
• The Price of Anarchy — the welfare gap of the equilibria that no-regret dynamics actually converge to