Sutton & Barto Chapter 2 — Multi-armed Bandits Explained

// the one-minute version

A k-armed bandit removes changing state and delayed consequences so we can study one hard question in isolation: when should an agent exploit the action with the highest estimated value, and when should it explore an uncertain alternative? The true action value is q_*(a)=E[R_t|A_t=a], but it is unknown. Sample averages estimate it in a stationary world; constant step sizes track drift. ε-greedy explores uniformly, optimistic initial values make unexplored actions attractive, UCB adds a count-based uncertainty bonus, and gradient bandits learn softmax action preferences. Contextual bandits add a situation while still keeping each action's reward immediate.

The morning after defining her warehouse agent, Asha disables motion and turns the robot into a simpler experiment. At the same loading bay it can choose one of ten safe route-planning heuristics. Each choice immediately returns a score based on travel time and energy. There is no changing location in the learning problem and no delayed delivery sequence—just choose a route rule, observe a noisy score, repeat. One heuristic looks best after three trials. Should Asha use it forever, or spend deliveries testing the others? Chapter 2 strips RL down until only that decision remains.

01 Why begin with a bandit?

A full RL problem has states, actions, transitions, delayed reward, and long-term value. If an algorithm performs poorly, several causes are entangled. A bandit keeps actions and rewards but removes state transitions: every round begins in the same decision situation, the chosen action produces an immediate reward, and the round ends.

The name comes from a row of slot machines—“one-armed bandits”—with unknown payout rates. With k machines, the learner chooses A_t∈{1,…,k} and receives R_t. The true value of action a is its expected reward:

q_*(a) ≝ E[R_t | A_t=a]

If q_* were known, the solution would be trivial: always choose an action with maximum value. Learning exists because q_* is hidden and rewards are noisy. The agent therefore maintains an estimate Q_t(a) and must collect evidence while also trying to earn reward.

first-principles reductionBandits remove the “what state will this action cause?” question. What remains is the cost of uncertainty itself. Every exploratory observation can improve future decisions, but it can also sacrifice reward now.

02 Exploitation, exploration, and regret

A greedy action maximizes the current estimate Q_t(a). Choosing it is exploitation: use present knowledge to obtain reward. Choosing a non-greedy action is exploration: gather information that may change later choices.

Why not explore every action thoroughly first? Because information has an opportunity cost. If the experiment lasts only ten rounds, spending nine rounds on weak actions may never pay back. If it lasts a million rounds, early exploration can be extremely valuable. The correct policy depends on the horizon, noise, value gaps, and whether the world changes.

A useful performance idea is regret: the reward lost compared with always choosing the truly optimal action. Although the book's testbed plots average reward and percentage of optimal actions, regret explains the objective: exploration should reduce uncertainty fast enough that future gains outweigh its current cost.

Fig 1 — Exploitation earns from current estimates; exploration improves those estimates. A useful action rule prices both.

03 Estimating action values from samples

For a stationary bandit, the natural estimate is the average of rewards observed after choosing that action. If action a has been selected N_t(a) times before step t:

Q_t(a) = (sum of rewards received when a was chosen) / N_t(a)

Storing every reward is unnecessary. Suppose Q_n is the average of n−1 observations and R_n is new. Algebra turns the new average into an incremental update:

Q_n+1 = Q_n + (1/n)[R_n − Q_n]

This is the recurring RL shape: new estimate = old estimate + step size × error. The error R_n−Q_n is positive when the reward exceeds expectation and negative when it disappoints. The sample-average step size 1/n shrinks as evidence accumulates, giving every past reward equal weight.

Asha's numbersRoute heuristic B has rewards 6, 10, and 8, so Q(B)=8. The fourth reward is 12. The update is 8+(1/4)(12−8)=9. Asha needs only the old estimate and count; she does not retain the four raw rewards. The result is exactly their average.

04 Greedy and ε-greedy action selection

A purely greedy method chooses argmax_aQ_t(a), breaking ties randomly. It can fail permanently after unlucky early samples. If a genuinely excellent route produces two poor scores because a forklift happened to block it, greedy selection may never test it again.

ε-greedy adds a simple escape. With probability 1−ε it chooses greedily; with probability ε it chooses uniformly among all actions. For ε=0.1 and ten actions, the greedy action is selected about 91% of the time: 90% through exploitation plus its 1% share of random exploration. Every action continues to receive samples, so stationary estimates eventually approach their true values.

The book's ten-armed testbed draws ten true action values and noisy rewards, then averages performance over many independent runs. Greedy often improves rapidly but plateaus after committing to the wrong action. ε=0.1 explores more and achieves better long-run reward; ε=0.01 improves more slowly but gives up less immediate reward. There is no universally best ε—the horizon and environment determine the trade.

watch outε-greedy explores blindly. Once it decides to explore, an obviously bad action and a promising but uncertain action are equally likely. Its strength is simplicity and guaranteed continued coverage, not efficient use of information.

05 Nonstationary problems and recency

Sample averages assume q_*(a) is fixed. Asha's warehouse violates that assumption: traffic patterns change by shift, batteries age, and a route heuristic can improve after a software update. Lifetime averages become anchored to obsolete history.

Replace 1/n with a constant step size α∈(0,1]:

Q_n+1 = Q_n + α[R_n − Q_n]

Expanding the recursion shows an exponentially weighted average: recent rewards receive weight α; a reward i updates ago receives roughly α(1−α)ⁱ. Larger α adapts quickly but produces noisy estimates. Smaller α is stable but slow to forget. The effective memory is on the order of 1/α samples.

The book highlights a technical detail called unbiased constant-step-size tracking. Early constant-α estimates retain a bias from Q₁. A step size β_n=α/ō_n, with a small trace ō updated toward one, removes that initial bias while approaching α over time. The broader principle matters more than memorizing the trace: when the target moves, the learner needs controlled forgetting.

06 Optimistic initial values and UCB

Optimistic initialization begins every Q₁(a) above any plausible reward. A greedy agent tries an action, receives a lower reward, and reduces its estimate; untried actions remain optimistic and become attractive. Exploration emerges from disappointment rather than explicit randomness.

This works well in stationary problems and makes early exploration purposeful, but it is temporary. Once every estimate loses its optimism, there is no continuing drive to revisit actions. In a nonstationary warehouse, a previously weak route can later become strong and remain ignored.

Upper-confidence-bound (UCB) selection makes uncertainty explicit:

A_t = argmax_a [ Q_t(a) + c √(ln t / N_t(a)) ]

The first term exploits estimated reward. The second is an exploration bonus. It is large for rarely selected actions, shrinks when an action is sampled, and slowly grows for ignored actions as ln t increases. Untried actions are treated as maximizers. Parameter c controls how much uncertainty is worth.

UCB is efficient because it distinguishes “bad and well known” from “possibly good but uncertain.” Its assumptions are less comfortable in large, nonstationary, or function-approximation settings, where counts no longer describe uncertainty cleanly. The chapter presents it as a powerful bandit idea, not a universal exploration solution.

why the UCB testbed spikesIn a ten-armed bandit, UCB must try each unselected action during the first ten steps. At step 11 every action has one sample, so the action with the largest first reward is selected—creating a sharp average-reward spike. That first “winner” is also selected across many runs because of positive noise, so its next reward regresses toward its true mean and the spike drops. The shape is a consequence of forced coverage plus selection bias.

07 Gradient bandits: learn preferences, not values

Gradient bandit algorithms do not estimate reward values directly. They learn a numerical preference H_t(a), then convert all preferences into probabilities with softmax:

π_t(a) = exp(H_t(a)) / Σ_b exp(H_t(b))

Only relative preferences matter: adding the same constant to every H leaves the probabilities unchanged. After action A_t produces reward R_t, its preference increases in proportion to (R_t−R̄_t)(1−π(A_t)); other actions decrease in proportion to the same advantage and their probabilities. R̄ is a reward baseline.

If reward is above baseline, the chosen action becomes more probable. If below baseline, it becomes less probable. The baseline does not change the expected gradient but can substantially reduce variance. This is an early preview of REINFORCE with a baseline and actor–critic methods in Chapter 13.

preference versus valueA value learner says, “Route C is worth 8.4 expected points.” A gradient bandit only needs to say, “Prefer C more than B and much more than F,” then lets softmax turn those relative preferences into a stochastic policy. The second representation is naturally probabilistic.

08 Contextual bandits and the boundary of full RL

A plain bandit sees one situation forever. An associative or contextual bandit receives context before acting. Asha may see shift, package type, or congestion class, then choose a route heuristic. The best action can differ by context, so the learner estimates or predicts action quality conditionally.

Why is this not yet a full Markov decision process? Because the action's effect ends with its immediate reward; it does not control which context arrives next. A news recommender that chooses an article based on the current user but treats the next visit as externally determined is a contextual bandit. If today's recommendation changes the user's interests and future visits, the problem has sequential state dynamics and belongs in Chapter 3.

boundary testAsk: does the action affect only the immediate reward, or does it also change the distribution of future decision situations? Immediate only → contextual bandit. Future situations too → full RL.

common catches & gotchas

Judging from one run — Bandit rewards and initial estimates are noisy. Compare algorithms across many independent runs with confidence intervals.
Using lifetime averages in a drifting system — Sample averages converge beautifully to a value that may no longer exist. Use recency weighting and monitor change.
Calling ε the probability of a non-greedy action — Random exploration can still select the greedy action. With k actions its total probability is 1−ε+ε/k.
Treating UCB's bonus as true uncertainty — The count bonus is principled under bandit assumptions but is not a calibrated posterior standard deviation in every environment.
Optimism without plausible scale — An absurd initial value can create a long wasteful transient; too little optimism may not explore at all.
Forgetting safety and eligibility — Exploration must occur inside the set of allowed actions. A bandit rule is not permission to test unsafe production choices.

09 Questions master's students should answer

Why does the sample-average step size equal 1/n?

Because the mean of n observations can be written as the old mean plus one nth of the new observation's deviation from that mean. Expanding the recurrence shows every reward receives exactly weight 1/n.

When should I prefer constant α?

When action values drift and old evidence should fade. Choose α from the time scale of expected change: larger for rapid drift, smaller for noisy but stable processes. Validate with controlled nonstationary simulations.

Is UCB always better than ε-greedy?

No. UCB can use samples efficiently in stationary finite bandits, but ε-greedy is simpler, easier to extend, and sometimes more robust under drift, large spaces, or approximate values.

Why does a reward baseline help gradient bandits?

The policy gradient depends on relative advantage. Subtracting a baseline independent of the selected action leaves the expected gradient unchanged while reducing common reward variation, which usually lowers estimator variance.

What metrics should my experiment report?

Average reward measures utility; percentage of optimal actions measures identification; cumulative regret measures opportunity cost. Report all three over time and aggregate across seeds rather than selecting the best run.

10 Key takeaways

A bandit isolates exploration versus exploitation by removing state transitions and delayed reward.
The true value q_*(a) is an expectation; Q_t(a) is an estimate built from noisy rewards.
Incremental learning follows old + step size × error; 1/n produces a sample average, while constant α forgets old data.
ε-greedy guarantees continued coverage but explores uniformly, including actions already known to be poor.
Optimistic values drive early exploration through inflated estimates; UCB continually combines estimated value with a count-based bonus.
Gradient bandits learn a softmax policy through preferences and an advantage-like reward relative to a baseline.
Contextual bandits condition on a situation but remain non-sequential when actions do not affect future contexts.

// chapter study sheetbandit toolkit

value estimation

q*(a)=E[R|A=a]Unknown true expected reward of action a.

Q ← Q + (1/N)(R−Q)Sample-average update for a stationary action value.

Q ← Q + α(R−Q)Constant-step update that tracks nonstationary values.

action selection

greedyargmax Q; exploits completely; can lock onto early noise.

ε-greedyGreedy with 1−ε, uniformly random with ε.

optimistic Q₁Untried actions stay attractive until sampled; initial exploration only.

UCBQ(a)+c√(ln t/N(a)); reward estimate plus exploration bonus.

gradient banditLearn preferences H; softmax turns them into action probabilities.

experiment design

stationary testFixed q*; compare convergence and long-run optimal-action rate.

drifting testRandom-walk q*; compare sample average with constant α.

reportMean reward, optimal-action %, regret, uncertainty across seeds.

11 Wrapping up and source trail

Asha began with a robot and ended with a controlled scientific question: how should evidence and uncertainty share one decision? Sample averages taught her how to estimate; ε-greedy, optimism, and UCB gave different reasons to explore; constant step sizes acknowledged drift; gradient preferences showed that a policy can be learned directly. The simplification has done its job. Next, finite Markov decision processes restore changing state and delayed consequences, where an action controls not only today's score but tomorrow's possibilities.

These are independent companion notes written in original language. Primary references: the authors' book page, the author-hosted open-access draft, the MIT Press edition page, and the official contents.

Chapter 2 — Multi-armed Bandits, explained.