Pull k slot machines to maximise cumulative reward. No states, no transitions — just the pure exploration–exploitation trade-off that underlies every RL algorithm.
The smallest non-trivial RL problem — no states, just arms and rewards.
Imagine k slot machines ("one-armed bandits"). Each machine i has an unknown true expected reward μi. At each time step t you choose one arm and receive a noisy reward rt ~ N(μselected, σ2). Your goal: maximise total reward over T steps.
You don’t know the true means — you can only estimate them from experience. This forces a fundamental tension: exploit the arm that looks best now, or explore others that might actually be better.
Regret = T · μ* − Σt rt where μ* = maxi μi
Regret measures how much cumulative reward you lost compared to always pulling the optimal arm. The goal of any bandit algorithm is to minimise regret.
Exploitation: always pull the arm with the highest estimated Q value. Problem: your estimates are noisy at the start, so you might commit to a suboptimal arm early and never discover a better one.
Exploration: try arms you’ve pulled fewer times. Problem: you waste pulls on arms you already know are mediocre.
This trade-off is not just about bandits — it is the core tension in all of reinforcement learning. Should the agent explore new parts of the state space, or exploit what it already knows?
Estimate each arm’s value with the sample mean of past rewards:
Qn+1(a) = Qn(a) + (1/n) · [rn − Qn(a)]
This is an incremental update that avoids storing all past rewards. The greedy policy always selects At = argmaxa Qt(a). It converges to the correct mean but gets stuck on local optima early on.
A simple fix: with probability ε pick a random arm (explore); otherwise pick the greedy arm (exploit):
At = random arm with prob ε
At = argmaxa Qt(a) with prob 1−ε
ε = 0.1 is a common default. The interactive demo above uses ε-greedy — try ε = 0 (pure greedy) vs ε = 0.5 (heavy exploration) and watch the regret difference after 1000 steps.
Initialise Q0(a) to a large value (e.g., +5) for all arms. The greedy agent will pull each arm at least once because the initial optimism makes them all look promising. After the first pull the inflated estimate falls toward reality, and the agent moves on to the next “optimistic” arm.
This encourages early exploration without any explicit exploration probability. It works well in stationary problems but fails when rewards drift over time (because the agent stops exploring after the optimism is burned off).
UCB selects arms that have either high estimated value or low pull count — uncertainty matters as much as reward:
At = argmaxa [Qt(a) + c √(ln t / Nt(a))]
The second term is a confidence bound: it shrinks as Nt(a) grows (more data reduces uncertainty) and grows with log t (all arms eventually get tried). UCB1 achieves O(log T) regret, which is asymptotically optimal. The constant c controls exploration width.
A Bayesian approach: maintain a prior distribution over each arm’s mean, sample one value from each arm’s posterior, and pull the arm with the highest sample. For Gaussian rewards, the posteriors are also Gaussian and easy to update.
Thompson Sampling often outperforms UCB in practice, achieves the same O(log T) regret bound, and naturally adapts to contextual settings where feature vectors describe each decision. It is widely used in recommendation systems and ad serving.
A k-armed bandit is an MDP with a single state: S = {s0}. Every action returns to the same state, so there is no state transition problem to solve. This makes it the simplest non-trivial RL setting — the Markov property holds trivially, and the Bellman equation reduces to:
v(s0) = maxa E[r | a]
The difficulty is purely statistical: estimating E[r | a] accurately with limited pulls. Understanding bandits well is the foundation for understanding exploration in full MDPs.
Say the answer out loud before you reveal it — recalling it is what makes it stick.
What is regret in the bandit setting and why do we minimise it?
Why does pure greedy fail on the k-armed bandit?
How does UCB balance exploration and exploitation differently from ε-greedy?
How is the k-armed bandit related to the full MDP formulation?
Greedy: pick argmax Q(a). ε-greedy: explore with prob ε. UCB1: pick argmax[Q(a)+c√(ln t/N(a))]. Incremental update: Q += (r-Q)/N. Regret = T·μ* − Σr_t. Optimal: O(log T) regret via UCB or Thompson Sampling.