One lever per turn, K arms, hidden payouts. Pull the arm you already know is good, or gamble on the one that might be better? UCB1 answers with a single line of arithmetic — pick the arm with the highest optimistic estimate, mean plus a confidence bonus that shrinks as you learn. Down the center, data flows: the arms go in, the rule chooses, the regret comes out — and it grows only logarithmically. The blue team builds and defends it; the red team tries to break it.
source Auer, Cesa-Bianchi & Fischer, Finite-time Analysis of the Multiarmed Bandit Problem (UCB1), Machine Learning 47 (2002) 235–256 — doi:10.1023/A:1013689704352; lower bound: Lai & Robbins, Adv. Appl. Math. 6 (1985) 4–22. Rendered, not quoted.
Each arm keeps a running empirical mean μ̂i and a count ni. At step t, UCB1 pulls the arm maximising:
μ̂i + √( 2 · ln t / ni )
The second term is the confidence bonus — how far the true mean might exceed what we have seen (a Hoeffding tail). It is large for arms tried rarely and shrinks toward 0 as ni grows: optimism fades with knowledge, so exploration turns itself off exactly where it is no longer needed.
Live bonus at the current horizon T, per arm:
| arm | ni | bonus √(2 ln T / ni) |
|---|
Strip a reinforcement problem of its states and you are left with one question, the bandit’s: pull the known-good arm, or gamble on the maybe-better one? That is the explore–exploit tradeoff distilled to its atom.
Add states back and the same bonus reappears as the exploration term inside the-q-learning and every agent after it. Each sphere is the next one’s premise — the bandit is where exploration is born.
The blue team’s live check: re-run the fixed-seed simulation and confirm UCB’s average regret regret(T)/T is small and shrinking. If red removes the bonus, regret goes linear and this badge turns red.
A K-armed bandit: K levers, each paying 1 with a fixed hidden probability μi and 0 otherwise. You get one pull per step for a horizon of T steps, and you only ever see the arms you actually pulled.
Fixed fixture (means are hidden from the algorithm, known only to us for scoring — AMBER given, not learned):
| arm | hidden μi | gap Δi = μ* − μi |
|---|
The score is regret: what you lost by not pulling the best arm every time, regret(T) = Σt (μ* − μa(t)). Feed the arms into the panel below.
The bonus is on: each step pulls argmax of mean + √(2 ln t / n). Optimism drives it to try every arm, then concentrate on the best.
| arm | μi | pulls ni | μ̂i | bonus | UCB score |
|---|
Everything here is computed live from a fixed-seed PRNG — the counts, the bonuses, the regret. Nothing is looked up.
What the machine proves: UCB1’s regret grows only logarithmically, so the average regret(T)/T → 0. At seed 7, T=2000 the average regret is ≈0.031 and the best arm is pulled ≈93% of the time — against a greedy rule that locks on the wrong arm and bleeds ≈0.30 forever. This matches the Lai–Robbins logarithmic lower bound: no rule can do asymptotically better.
The blue team’s witness (left) recomputes these live; the red team (right) tries to make regret grow linearly.
And UCB is a worst-case frequentist bound, not an empirical champion: Bayesian Thompson sampling usually beats it in practice. "Optimal" here means the rate is optimal (Lai–Robbins), not that UCB wins every race.
"Good bandit algorithms drive regret to zero." Cut. Cumulative regret keeps growing, forever, at rate ~log T. It is the average regret(T)/T that vanishes — a different claim, and the true one.
"More exploration is always better." Cut. The bonus deliberately shrinks to 0. Exploration that never fades never lets you exploit — regret would stay linear.
"Greedy is a fine baseline." Kept, corrected. Pure greedy can lock onto a wrong arm forever (window 6 does exactly this) — a single unlucky first pull is unrecoverable. It needs forced exploration to be safe.
The red team’s move: delete the exploration bonus. UCB collapses to pure greedy on the empirical mean — no optimism, no recovery. Watch it lock on the wrong arm and let regret grow linearly.
Strip the √(2 ln t / n) term and a bad first sample is fatal: the algorithm never revisits the arm it wrote off. Regret climbs as a straight line, the witness (window 7) recomputes and turns red. Nothing is faked; the attack is real and it is caught.