"They gave me two levers and told me to make money. I pulled the left one, won a little, and pulled it again, and again, because it had paid me once and I am a creature of evidence. For a thousand rounds I was loyal to the left lever, proud of my discipline, until the day someone idly pulled the right one and it rained coins. The right lever had been the better lever the entire time, and I had never once asked it, because asking costs a pull and I was busy collecting on what I already knew. That is the whole tragedy of acting without a model: every pull spent learning is a pull not spent earning, and every pull spent earning is a question left unasked. They call this exploration versus exploitation as though it were a tidy dial to turn. It is not a dial. It is the oldest argument I have with myself, and I lose it whichever way I choose."
A Reinforcement Learner Still Exploring
Chapter Overview
Every model in the book until now has been handed its world. The forecasters of Part II were given a series and asked to extend it; the deep networks of Part III were given inputs and targets; even the Markov decision processes of Chapter 22 assumed you knew the transition and reward functions and could solve for the optimal policy by planning. This chapter removes that gift. Here the agent does not know how the world responds to its actions, and the only way to find out is to act and watch what happens. Learning to act under an unknown model is the defining problem of reinforcement learning, and it introduces a tension that planning never faces: the agent must spend some of its actions gathering information it does not yet have, even though those actions earn nothing while they teach. The chapter is the bridge from knowing the model and planning within it to not knowing the model and learning to control it from raw experience.
The cleanest place to meet that tension is the multi-armed bandit, a degenerate Markov decision process with a single state, where the only question is which action to take and the only unknown is each action's reward distribution. Stripping away the dynamics isolates exploration versus exploitation in its purest form, and the chapter uses it to build the two great families of principled exploration: optimism in the face of uncertainty, made concrete by the upper confidence bound (UCB) algorithm, and posterior sampling, made concrete by Thompson sampling, the Bayesian method whose predictive distributions are exactly the uncertainty machinery of Chapter 19. Regret, the gap between what the agent earned and what an oracle would have earned, becomes the yardstick that makes "good exploration" a number rather than an intuition. Contextual bandits then add a single state observation before each action, the half-step between the stateless bandit and the full sequential problem, and the place where recommendation, ad selection, and clinical-trial allocation actually live.
With exploration understood, the chapter restores the dynamics and turns to learning value from experience in a world with many states. Monte Carlo methods estimate the value of a state by averaging the returns that followed it across complete episodes, the most direct possible translation of "value is expected return" into an algorithm. Temporal-difference (TD) learning then makes the central move of the chapter: instead of waiting for an episode to finish, it bootstraps, updating each state's value toward an immediate reward plus the current estimate of the next state's value. That predict-then-correct update is not new to you. It is the same predict-update rhythm as the Kalman filter of Chapter 7, which predicts the next state and then corrects on the measurement; TD learning is that filtering loop turned toward value, predicting the return and correcting on the reward as it arrives.
Value estimation becomes control when the agent uses what it learns to improve its policy. Q-learning learns the value of state-action pairs directly and off-policy, converging toward the optimal policy even while it explores with another, and SARSA learns on-policy, valuing the actions it will actually take, exploration included, which makes it the more cautious of the two near danger. These two tabular algorithms, one bold and one careful, are the foundation that every method in the rest of Part VI builds on: the deep reinforcement learning of Chapter 25 is, in large part, Q-learning and policy methods with a neural network standing in for the table. Master the table here, and the network there is a change of representation, not a change of idea.
Prerequisites
This chapter assumes you have met the sequential-decision framework and now want to learn within it without being handed the model. From Chapter 22: Markov Decision Processes you need the core vocabulary that the whole chapter rests on: states, actions, rewards, returns and discounting, value functions and action-value functions, the Bellman equations, and the idea of an optimal policy, because reinforcement learning is precisely the project of recovering those quantities from experience when the transition and reward functions are unknown rather than solving for them when they are known. From Chapter 20: Online and Continual Learning you need the online-learning mindset, learning from a stream one sample at a time with running estimates and step sizes, since every algorithm here is an incremental update applied as experience arrives, never a batch fit. The Thompson-sampling material of Section 24.2 leans directly on the predictive distributions and posterior reasoning of Chapter 19: Probabilistic Forecasting and Uncertainty Quantification, where the same Bayesian machinery quantifies uncertainty for forecasts; here it drives exploration. Readers wanting to refresh the probability behind expectations, variance, and Bayesian updates, or the Markov-process foundations these chapters build on, will find them through the Table of Contents.
If you keep one idea from this chapter, keep this: when the model is unknown, the agent must learn to act from experience alone, balancing exploration against exploitation, and it does so by estimating values through Monte Carlo or temporal-difference updates and improving its policy with Q-learning or SARSA. The bandit isolates exploration in a single state and is tamed by optimism (UCB) or posterior sampling (Thompson), with regret as the scoreboard; contextual bandits add one observation before acting; Monte Carlo averages full-episode returns while temporal-difference learning bootstraps from one step, the same predict-update loop as the Kalman filter turned toward value; and Q-learning (off-policy, bold) and SARSA (on-policy, cautious) turn value estimation into tabular control, the foundation every deep method in the rest of Part VI rests on.
Chapter Roadmap
- 24.1 Multi-Armed Bandits The simplest reinforcement-learning problem: a single state, several actions, and an unknown reward distribution per action, where the only question is which arm to pull. Action-value estimates, the epsilon-greedy baseline, and why the stateless bandit is the cleanest stage for the exploration-exploitation dilemma.
- 24.2 UCB, Thompson Sampling, and Regret Principled exploration and how to score it: optimism in the face of uncertainty via the upper confidence bound, posterior sampling via Thompson sampling and its Bayesian roots in Chapter 19, and regret as the formal yardstick that turns "explore well" into a measurable quantity with logarithmic guarantees.
- 24.3 Contextual Bandits Adding a single observation before each action: the half-step between the stateless bandit and the full sequential problem, LinUCB and contextual Thompson sampling, and the applications that live exactly here, recommendation, ad selection, and adaptive clinical-trial allocation.
- 24.4 Monte Carlo and Temporal-Difference Learning Estimating value from experience in a world with many states: Monte Carlo averaging of complete-episode returns, the bootstrapping move of temporal-difference learning that updates from a single step, and the bias-variance trade-off between them, with TD as the predict-update loop of Chapter 7 turned toward value.
- 24.5 Q-Learning and SARSA Turning value estimation into control: Q-learning, which learns action values off-policy and converges toward the optimal policy while exploring with another, and SARSA, which learns on-policy and values the actions it will actually take, the bold and the cautious tabular algorithms side by side.
- 24.6 Exploration vs Exploitation The dilemma made general: from epsilon-greedy and optimistic initialization to count-based and uncertainty-driven strategies, why exploration is harder in long-horizon multi-state problems than in bandits, and the principles that carry forward into the deep reinforcement learning of Chapter 25.
Once you have worked through the six sections, the Hands-On Lab below chains them into a single progression on two environments. Each lab step maps to a section, so the lab doubles as a review: by the time you finish you will have raced the exploration strategies of Section 24.1 and Section 24.2 on a bandit by regret, built the contextual LinUCB of Section 24.3, and trained the tabular control algorithms of Section 24.5 on a gridworld, watching the exploration-exploitation principle of Section 24.6 shape every path.
Hands-On Lab: From Bandits to Control
Objective
Walk the full arc of the chapter in code, from a one-state bandit to tabular control, watching exploration cost and earn at every stage. You will first build a multi-armed bandit and race four strategies on it, epsilon-greedy, optimistic initialization, UCB, and Thompson sampling, scoring each by cumulative regret against the oracle, the measurable yardstick of Section 24.2, so that "explores well" stops being a slogan and becomes a curve. You will then add a context vector before each action and build a LinUCB contextual bandit from Section 24.3, the half-step into state. Finally you will restore full dynamics and train both Q-learning and SARSA from Section 24.5 on a gridworld with a cliff, and contrast the paths the two algorithms learn: Q-learning's bold optimal route along the edge and SARSA's cautious detour away from it, the on-policy versus off-policy distinction made visible as a trajectory rather than an equation. The single thread is that every action an agent takes is either a question or an answer, and the algorithms differ only in how they decide which to ask and when.
What You'll Practice
- Building a multi-armed bandit and implementing the epsilon-greedy and optimistic-initialization baselines of Section 24.1.
- Implementing UCB and Thompson sampling and ranking strategies by cumulative regret, following Section 24.2.
- Adding a context vector and building a LinUCB contextual bandit, following Section 24.3.
- Implementing tabular Q-learning and SARSA with temporal-difference updates, following Section 24.4 and Section 24.5.
- Contrasting on-policy and off-policy control by the trajectories they learn, following Section 24.5 and Section 24.6.
Setup
You need a Python environment with numpy for the bandit and tabular agents and gymnasium for the gridworld environment, whose CliffWalking-v0 task is the standard stage for contrasting Q-learning and SARSA. No deep-learning framework is required: every algorithm in this lab is a few lines of array arithmetic, which is exactly the point, the ideas are small and the table is the whole model. The one discipline that governs the bandit half of the lab is that regret must be measured against the true best arm, which you know because you generated the reward distributions, so keep the ground-truth means aside and never let any agent see them. The code below is the epsilon-greedy action-value update of Section 24.1, the incremental running-mean estimate that every bandit strategy in the lab extends.
import numpy as np
def epsilon_greedy_bandit(true_means, n_steps=2000, epsilon=0.1):
k = len(true_means)
Q = np.zeros(k) # estimated action values
N = np.zeros(k) # pull counts per arm
best = true_means.max() # oracle reward, used only to score regret
regret = 0.0
for _ in range(n_steps):
a = np.random.randint(k) if np.random.rand() < epsilon else int(Q.argmax())
r = np.random.randn() + true_means[a] # noisy reward from the chosen arm
N[a] += 1
Q[a] += (r - Q[a]) / N[a] # incremental running-mean update
regret += best - true_means[a] # gap to the oracle this step
return Q, regret
Steps
Step 1: Build the bandit and run the epsilon-greedy baseline
Generate a multi-armed bandit with several arms of differing unknown means, run the epsilon-greedy agent above, and plot its cumulative regret over time, the baseline view of Section 24.1. Try a fixed epsilon and a decaying one, and watch how a constant exploration rate keeps paying a linear regret toll forever while a decaying one bends the curve flat.
Step 2: Add UCB and Thompson sampling and race by regret
Implement the upper-confidence-bound rule and Thompson sampling from Section 24.2, run all the strategies on the same bandit, and overlay their cumulative-regret curves. Confirm that UCB and Thompson sampling achieve sublinear regret where fixed epsilon-greedy does not, making the logarithmic-regret guarantee a visible bend rather than a theorem.
Step 3: Add context and build LinUCB
Attach a context vector to each round so the best arm now depends on the observation, then build the LinUCB contextual bandit of Section 24.3, which fits a linear reward model per arm and adds an optimism bonus from the model's uncertainty. Compare its regret against a context-blind bandit and see the gain from conditioning the action on the state.
Step 4: Restore dynamics and train Q-learning on the gridworld
Switch to the CliffWalking-v0 gridworld and train tabular Q-learning with the temporal-difference update of Section 24.4 and the off-policy control of Section 24.5. Track the learning curve and render the greedy policy it converges to, the bold optimal route that hugs the cliff edge.
Step 5: Train SARSA and contrast the paths
Train SARSA on the same gridworld with the on-policy update of Section 24.5, holding the exploration rate equal, and render its policy beside Q-learning's. Explain why SARSA learns the cautious detour away from the cliff: it values the actions it will actually take, exploration included, so it accounts for the chance that an epsilon-random step near the edge ends in the fall, the exploration-exploitation lesson of Section 24.6 drawn as a path.
Expected Output
The lab produces one figure per stage and one clear contrast at the end. The bandit races of Steps 1 and 2 yield a panel of cumulative-regret curves in which fixed epsilon-greedy climbs roughly linearly while UCB and Thompson sampling flatten into sublinear growth, the difference between exploring forever and exploring just enough. The contextual stage of Step 3 shows LinUCB beating the context-blind bandit once the best arm depends on the observation, quantifying what a single state buys you. The tabular control of Steps 4 and 5 produces the chapter's signature picture: two policies on the same cliff gridworld, Q-learning converging to the shorter, riskier path along the cliff edge because its off-policy update values the optimal greedy action regardless of how it explores, and SARSA converging to the longer, safer path because its on-policy update prices in the exploratory missteps it will actually make. The reader finishes able to implement every algorithm in the chapter from scratch, to score exploration by regret rather than by intuition, and to read a learned policy as evidence of whether the agent valued the path it follows or the path it dreams of, the whole on-policy versus off-policy distinction made concrete.
The from-scratch agents of this lab are small on purpose, but the surrounding machinery is standardized so you never rebuild it. The gridworld, the cliff, the episode loop, and the reward bookkeeping that Steps 4 and 5 lean on are a single gymnasium.make("CliffWalking-v0") call against the standard reinforcement-learning environment API, the same reset and step interface that every agent in the rest of Part VI expects, so the tabular agents you write here plug into the exact harness the deep agents of Chapter 25 will use. Beyond the environment, libraries like contextualbandits ship LinUCB and Thompson-sampling policies ready to wrap a scikit-learn model, collapsing Step 3 into a few lines. The discipline the chapter teaches still governs the libraries: a regret curve scored against the wrong baseline, a contextual bandit fit on leaked rewards, or a Q-learning run whose exploration schedule never decays will each report a confident and wrong result in exactly the same few lines. The library makes the loop free; it does not make the exploration honest.
Stretch Goals
- Implement Double Q-learning and compare it against plain Q-learning on the gridworld, observing how decoupling action selection from value estimation reduces the maximization bias that makes Q-learning overestimate action values, a fix the deep methods of Chapter 25 reuse.
- Replace the constant exploration rate in Steps 4 and 5 with an optimistic-initialization scheme or a count-based bonus from Section 24.6, and measure whether the smarter exploration of the bandit chapters transfers cleanly to the multi-state setting or breaks down as the horizon grows.
- Add an adaptive clinical-trial flavor to the contextual bandit of Step 3: let the context encode patient features and the reward encode outcome, and discuss the ethical tension between exploring an uncertain treatment and exploiting the one currently believed best, the real-world face of regret.
What's Next?
This chapter taught the agent to act when no one handed it the model, learning value from raw experience and improving its policy with nothing but a table of numbers. That table is also the wall the chapter runs into. A tabular value function needs one entry per state or state-action pair, and the moment the state is an image, a sensor stream, or a continuous vector, the table explodes past any memory and never sees the same state twice, so the careful Monte Carlo and temporal-difference estimates you built have nothing to average over. Chapter 25: Deep Reinforcement Learning replaces the table with a neural network that generalizes value across states it has never visited, turning Q-learning into the deep Q-network and opening the policy-gradient and actor-critic families that carry reinforcement learning into high-dimensional worlds. The bandit's exploration dilemma, the temporal-difference update, and the off-policy versus on-policy split you mastered here all survive the move intact; only the representation changes, from a table you can print to a network you must train. The full path through Part VI and the rest of the book is laid out in the Table of Contents.
Bibliography & Further Reading
Foundational Texts
Sutton, R. S., Barto, A. G. "Reinforcement Learning: An Introduction." 2nd ed., MIT Press, 2018. incompleteideas.net/book/the-book.html
The canonical textbook of the field and the backbone of this chapter, covering bandits, Monte Carlo, temporal-difference learning, Q-learning, and SARSA in the order and notation used throughout Sections 24.1 to 24.6.
Lattimore, T., Szepesvari, C. "Bandit Algorithms." Cambridge University Press, 2020. tor-lattimore.com/downloads/book/book.pdf
The definitive modern reference on multi-armed and contextual bandits, with the rigorous regret analysis behind UCB, Thompson sampling, and LinUCB that underpins Sections 24.1 to 24.3.
Bandits and Exploration
Auer, P., Cesa-Bianchi, N., Fischer, P. "Finite-Time Analysis of the Multiarmed Bandit Problem." Machine Learning, 47, 235-256, 2002. doi.org/10.1023/A:1013689704352
The paper that introduced UCB1 and proved its logarithmic regret bound, the formal basis for the optimism-in-the-face-of-uncertainty strategy of Section 24.2.
Thompson, W. R. "On the Likelihood That One Unknown Probability Exceeds Another in View of the Evidence of Two Samples." Biometrika, 25(3-4), 285-294, 1933. doi.org/10.1093/biomet/25.3-4.285
The original 1933 paper introducing posterior sampling for sequential allocation, the idea now called Thompson sampling and the Bayesian exploration method of Section 24.2.
Agrawal, S., Goyal, N. "Analysis of Thompson Sampling for the Multi-armed Bandit Problem." COLT, 2012. arXiv:1111.1797. arxiv.org/abs/1111.1797
The first rigorous regret analysis of Thompson sampling, proving the logarithmic bound that put the 1933 heuristic on the same theoretical footing as UCB, supporting Section 24.2.
Russo, D., Van Roy, B., Kazerouni, A., Osband, I., Wen, Z. "A Tutorial on Thompson Sampling." Foundations and Trends in Machine Learning, 11(1), 2018. arXiv:1707.02038. arxiv.org/abs/1707.02038
The accessible modern tutorial on Thompson sampling across bandit and contextual settings, the recommended entry point to the posterior-sampling material of Sections 24.2 and 24.3.
Contextual Bandits
Li, L., Chu, W., Langford, J., Schapire, R. E. "A Contextual-Bandit Approach to Personalized News Article Recommendation (LinUCB)." WWW, 2010. arXiv:1003.0146. arxiv.org/abs/1003.0146
The paper that introduced LinUCB and framed news recommendation as a contextual bandit, the contextual-exploration algorithm built in Section 24.3 and the lab.
Temporal-Difference Learning and Control
Sutton, R. S. "Learning to Predict by the Methods of Temporal Differences." Machine Learning, 3, 9-44, 1988. doi.org/10.1007/BF00115009
The paper that introduced temporal-difference learning and the bootstrapping update, the central prediction method of Section 24.4 and the kin of the Kalman filter's predict-update loop.
Watkins, C. J. C. H., Dayan, P. "Q-learning." Machine Learning, 8, 279-292, 1992. doi.org/10.1007/BF00992698
The paper that introduced Q-learning and proved its convergence to the optimal action-value function, the off-policy tabular control algorithm of Section 24.5.
Rummery, G. A., Niranjan, M. "On-Line Q-Learning Using Connectionist Systems." Technical Report CUED/F-INFENG/TR 166, Cambridge University Engineering Department, 1994. cs.cmu.edu/.../rummery.pdf
The report that introduced the on-policy algorithm later named SARSA, the cautious counterpart to Q-learning compared throughout Section 24.5 and the lab.
Tools and Libraries
Towers, M., et al. "Gymnasium: A Standard Interface for Reinforcement Learning Environments." Farama Foundation. gymnasium.farama.org
The maintained successor to OpenAI Gym and the standard environment interface for reinforcement learning, supplying the CliffWalking gridworld and the reset-step API behind the control half of the lab.