Multi-Armed Bandits

Why Does This Exist?

Every agent faces one tension before all others: play the current best or test the rest. Full RL tangles that tension with states, transitions, and delayed rewards. Bandits isolate it. One state, $k$ actions called arms, each paying from a fixed unknown distribution with true mean $\mu_a$. Pull for $T$ rounds, keep the total. That is the whole problem, named for the casino row of lever machines in Sutton and Barto (Chapter 2).

Solving it well matters beyond casinos: trial allocation, ad placement, and any A/B choice with a cost per sample. The rules invented here, UCB1 from Auer and colleagues (2002) and Thompson sampling from Thompson (1933), became the selection rules inside tree search and exploration bonuses everywhere. For the general tension see exploration vs exploitation; for the two smart rules see upper confidence bound and Thompson sampling.

The one idea you need first

An action value $Q(a)$ estimates the mean payout $\mu_a$ of one arm. The agent pulls, observes a reward, and nudges the estimate. Everything on this page is about which arm to pull next given those estimates, nothing about states or futures.

Think of It Like This

How It Actually Works

Each arm $a$ pays rewards with unknown mean $\mu_a$. The agent tracks $Q(a)$, usually the sample average, updated incrementally so no history is stored. After the $n$th pull of arm $a$ pays $R$:

The new reward moves the average by one $n$th of the surprise. Estimates in hand, three standard rules pick the next arm:

• Epsilon-greedy. With probability $1 - \varepsilon$ pull the current best arm, else pull uniformly at random. One knob, no memory of which arm needs testing most.
• UCB1. Pull $\arg\max_a \left( Q(a) + \sqrt{2 \ln t / N(a)} \right)$ with $t$ total pulls and $N(a)$ pulls of arm $a$. The bonus is large for rarely pulled arms and decays for tested ones: optimism in the face of uncertainty.
• Thompson sampling. Keep a posterior belief over each $\mu_a$, sample one plausible mean per arm, pull the highest sample. Winners get pulled more, losers still get sampled when beliefs overlap.

Success is measured by regret: the gap between always pulling the true best arm and what the rule actually banked. Good rules keep expected regret growing sublinearly, typically $O(\ln T)$ for UCB1, so the average shortfall per round shrinks toward zero.

Worked example

Arm estimates after $12$ total pulls: arm1 at $Q = 0.70$ over $n = 8$, arm2 at $Q = 0.50$ over $n = 2$. Since $\ln 12 \approx 2.4849$:

The next pull goes to arm2 despite the worse average: two pulls is too little evidence. Suppose arm2 then pays $3.00$ on its 3rd counted pull while its average sat at $1.50$ after earlier rounds. The incremental update gives $1.50 + (3.00 - 1.50) / 5 = 1.80$ when that reward is the 5th observation. One surprise moves a young average fast and an old average barely, which is exactly what the $1/n$ step does. The diagram draws the $1.4882$ against $2.0764$ decision.

Code

This snippet replays the worked example: one incremental average update and one UCB1 decision.

1import math2
3
4def incremental_mean(q: float, n_new: int, reward: float) -> float:5    """Fold the newest reward into the average; n_new counts this pull."""6    return q + (reward - q) / n_new7
8
9def ucb1(q: float, n: int, t: int) -> float:10    """UCB1 score for one arm after t total pulls."""11    return q + math.sqrt(2 * math.log(t) / n)12
13
14print(f"Q new={incremental_mean(1.50, 5, 3.00):.4f}")  # -> Q new=1.800015print(f"arm1={ucb1(0.70, 8, 12):.4f}")  # -> arm1=1.488216print(f"arm2={ucb1(0.50, 2, 12):.4f}")  # -> arm2=2.0764

The printout matches the hand arithmetic: $1.80$ for the update and $1.4882$ against $2.0764$ for the decision, so arm2 gets the next pull.

Watch Out For

The Quick Version

• A bandit is one state with $k$ unknown payout distributions, isolating the choice between cashing in and finding out.
• Averages update incrementally with $Q \leftarrow Q + (R - Q)/n$, so no reward history needs storing.
• Epsilon-greedy explores blindly, UCB1 adds an uncertainty bonus $\sqrt{2 \ln t / N(a)}$, Thompson sampling pulls the best of sampled beliefs.
• Regret measures the shortfall against always playing the true best arm; UCB1 keeps it growing only logarithmically.
• Fixed payout rates are assumed; drifting payouts need a constant step size so estimates track instead of anchor.

What to Read Next

• Exploration vs. Exploitation
• Upper Confidence Bound (UCB)
• Thompson Sampling in Bandits
• Epsilon-Greedy