4 · Multi-armed bandits
Strip RL down to its simplest form: one state, k actions, each a slot machine with an unknown payout. Estimate each arm's value by averaging — and watch a greedy agent stumble.
A k-armed bandit is an MDP with a single state and k actions, each arm paying from a fixed unknown reward distribution. We learn the action-value Q(a) — the mean reward of arm a — by sample-averaging the rewards we actually see, then act greedily by picking the arm with the highest estimate.
Without this:
Without the bandit you skip the cleanest place to meet action-value estimation and the explore/exploit problem — the two ideas at the heart of every value-based RL method.
The multi-armed bandit is RL with everything stripped away except the core challenge. Picture a row of k slot machines ("one-armed bandits"). Each pull of arm a pays a random reward drawn from that arm's own fixed distribution, with some true mean q*(a) you do not know. On every step you pick one arm and observe one reward. Your goal: maximise total reward over many pulls.
This is an MDP with a single state — there's no "next state" to worry about, every pull faces the same lineup of machines — so it isolates the one thing RL must do: figure out which actions are good from noisy experience alone.
The key quantity is the action-value Q(a): our estimate of the mean reward of arm a. The most natural estimate is the sample average — the average of all rewards we've actually received from that arm:
Q(a) = (sum of rewards seen from a) / (number of times a was pulled)
By the law of large numbers, the more we pull an arm, the closer its sample average gets to the true q*(a). An agent acting greedily simply pulls the arm with the highest current Q(a) estimate. But there's a catch we'll expose below: a greedy agent only trusts what it has already sampled — and an arm pulled once and unlucky may be wrongly written off forever.
Python (in browser)
A 10-armed bandit from scratch: Q(a) learned by incremental sample-averaging. Pure-greedy fixates on an early favourite; pure-random estimates well but never exploits.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
In a k-armed bandit, what is the action-value Q(a) and how is it estimated by sample-averaging?
- A k-armed bandit is an MDP with one state and k actions; each arm pays from a fixed unknown distribution with true mean q*(a).
- The action-value Q(a) is estimated by sample-averaging observed rewards: Q(a) <- Q(a) + (1/n)(r - Q(a)), the running mean.
- A purely greedy agent fixates on early estimates; a purely random agent estimates well but never exploits — neither is good enough.
Bandits run A/B tests, online ad and content selection, clinical-trial allocation, and hyperparameter search — anywhere you choose among options under uncertainty.
If you remove it: Without action-value estimation you have no way to turn noisy reward samples into a judgement of which action is best.