Sutton & Barto Chapter 10 — On-policy Control with Approximation Explained

// the one-minute version

Control requires approximate action values: q̂(s,a,w) must both judge decisions and generate the policy that collects its next data. Episodic semi-gradient Sarsa combines ε-greedy improvement with the same gradient update as Chapter 9. Its n-step form trades bootstrap bias against return variance and often works especially well with tile coding. For systems that never naturally terminate, the chapter replaces discounted return with the average reward and learns differential values—how much better a decision is than the continuing system’s normal reward rate.

Asha can now predict how much return follows from a robot state, but that does not tell the robot whether to accelerate, brake, or reroute. She could build a model and look ahead, yet she wants a model-free controller. The new difficulty is circular: estimates determine actions, actions determine visited data, and visited data changes estimates. Approximation couples all three.

01 Prediction becomes control

State values evaluate a policy only after the action distribution is known. To improve the policy without a model, learn q̂(s,a,w), an estimate for taking a and then following π. For discrete actions, an ε-greedy policy chooses argmax_aq̂ most of the time and explores otherwise. Because this same policy supplies experience, the method remains on-policy.

general patternobserve → build a return target → move q̂(S_t,A_t,w) toward it → choose the next action from the updated estimates.

Approximation changes policy improvement. Raising one state-action estimate may raise estimates for similar pairs too, so a local update can change behavior across a region. Feature design is therefore part of policy design.

02 Episodic semi-gradient Sarsa, derived

At step t, Sarsa observes S_t,A_t,R_t+1,S_t+1,A_t+1. Its one-step target is R_t+1+γq̂(S_t+1,A_t+1,w). The TD error and update are

one-step Sarsaδ_t=R_t+1+γq̂(S_t+1,A_t+1,w)−q̂(S_t,A_t,w); w←w+αδ_t∇q̂(S_t,A_t,w).

At a terminal state the bootstrap term is zero. The update is semi-gradient because the target depends on w but is treated as fixed while differentiating. With q̂=wᵀx(s,a), the gradient is x(s,a). Action-value features are often made by giving each action its own copy of state features, so an update for “accelerate” does not directly alter “brake.”

03 n-step Sarsa decides how far evidence travels

The n-step return includes n observed rewards and then bootstraps:

n-step targetG_t:t+n=R_t+1+γR_t+2+⋯+γⁿ⁻¹R_t+n+γⁿq̂(S_t+n,A_t+n,w).

Then w moves by α[G_t:t+n−q̂(S_t,A_t,w)]∇q̂. Small n learns quickly but relies heavily on imperfect estimates. Large n uses more actual rewards but adds variance and delay. There is no universally best n; the representation, reward delay, and step size interact.

Generalized policy iteration survives approximation, but evaluation and improvement now interact through shared parameters.

04 Mountain Car: why going backward can be progress

The underpowered car cannot drive straight up the hill. It must move away from the goal, climb the opposite slope, then reverse to build momentum. Position and velocity are continuous, reward is −1 per step, and termination occurs at the summit. A one-step greedy reflex initially sees backward motion as useless; multi-step return eventually connects it to reaching the goal.

Tile coding gives local, overlapping state-action features. Early episodes are long, but experience sculpts a cost-to-go surface and the ε-greedy policy discovers the swing. The example demonstrates delayed credit, continuous generalization, and the need to compare algorithms over a fair range of step sizes—not at one hand-picked value.

05 Continuing tasks need a continuing objective

A warehouse, network router, or HVAC controller may run indefinitely. Cutting time into artificial episodes can make results depend on reset boundaries. Discounted return is finite, but γ also changes how the agent ranks policies. The average-reward formulation directly asks for the long-run reward rate:

average rewardr(π)=lim_h→∞(1/h) E_π[R₁+⋯+R_h].

This requires a continuing, typically unichain process so the long-run rate is well defined independent of start state. Values become differential: expected cumulative excess reward relative to r(π). Adding a constant to every differential value changes nothing; only differences matter.

06 Differential semi-gradient Sarsa

Maintain both w and an estimate R̄ of the average reward. The continuing TD error is

differential errorδ=R_t+1−R̄+q̂(S_t+1,A_t+1,w)−q̂(S_t,A_t,w).

Update R̄←R̄+βδ and w←w+αδ∇q̂(S_t,A_t,w). Intuitively, reward above the current baseline is good news. The n-step differential form sums rewards after subtracting R̄ and then bootstraps. This is not ordinary reward normalization: R̄ is part of the prediction equations and tracks policy performance.

07 Why discounting is not always the right story

Discounting is indispensable when future consequences truly matter less, termination occurs with constant hazard, or the task definition explicitly uses γ. But in a continuing task, “maximize discounted return from every state” can be awkward: policy comparisons may depend on transient start-state effects, while operations teams care about throughput or cost per hour.

Average reward separates transient differential value from steady-state performance. It does not make delayed consequences disappear; the differential value still credits actions for their future excess rewards. The choice between objectives is semantic, not merely numerical.

08 Asha’s controller: two legitimate formulations

episodicFor one delivery, reward −1 per second and termination at the correct shelf. Tile-coded n-step Sarsa minimizes trip time. Resetting at the depot is a real episode boundary.

continuingFor fleet dispatch, robots never collectively stop. Reward is completed deliveries minus energy and congestion cost each minute. Differential Sarsa optimizes this long-run rate without inventing midnight resets.

These are different questions. A controller that excels per trip may create global congestion; a steady-state controller may accept a slightly slower trip to increase fleet throughput. Objective design precedes algorithm choice.

09 Failure modes and experimental discipline

gotchasDo not translate a table into a network call and assume the theory survived. Generalization couples actions; policy improvement shifts the training distribution; a large α can create oscillating policies; ε must be reported; and average reward requires a truly continuing task. In episodic evaluation, distinguish training exploration from the greedy evaluation policy. Plot return distributions across seeds and inspect learned surfaces.

10 Questions a master’s student should be able to answer

Why use Sarsa instead of max-based Q-learning here?

Sarsa’s target uses the next action actually selected by the behavior policy, so it evaluates and improves that same exploratory policy. This on-policy alignment gives a comparatively stable setting for introducing approximation.

What exactly changes when n increases?

The target includes more sampled rewards before bootstrapping. Bias from the current approximation generally falls, while variance, delay, storage, and sensitivity to exploratory actions rise.

Why is average reward not just γ=1?

An undiscounted infinite sum usually diverges. Average reward extracts reward per time step, and differential values sum deviations from that rate. Together they define finite relative predictions.

Can average reward compare every MDP policy?

Clean theory usually assumes communicating or unichain structure. In multichain problems the achieved rate may depend on the recurrent class entered from the start state, so one scalar objective can hide important distinctions.

How should I evaluate an approximate controller?

Freeze learning, remove or separately report exploration, test multiple starting conditions and seeds, report learning speed and final performance, visualize coverage and action values, and compare against a simple baseline under the same interaction budget.

11 Chapter summary and exam-ready map

Approximate control: q̂ generalizes across state-action pairs while an ε-greedy policy closes the evaluation–improvement loop.
Episodic Sarsa: the semi-gradient update moves the current action value toward a sampled, bootstrapped on-policy target.
n-step control: n selects the mixture of observed rewards and bootstrap estimate.
Mountain Car: delayed credit and local generalization explain purposeful movement away from the goal.
Average reward: continuing performance is reward per step; differential value measures transient advantage over that rate.
Differential Sarsa: jointly estimates R̄ and q̂ from a baseline-corrected TD error.
Objective clarity: episodic discounted and continuing average-reward formulations answer different operational questions.

// master’s study sheetchapter 10

derive

episodicWrite one-step and n-step semi-gradient Sarsa, including the terminal boundary.

continuingDerive δ=R−R̄+q̂′−q̂ and the two coupled updates for R̄ and w.

compare

objectivesExplain what discounting and average reward each mean operationally, not only mathematically.

implement

mountain carTile-code position–velocity–action, sweep n and α, show cost-to-go, and evaluate without exploratory actions.

12 Source trail and scope

These are independent companion notes, not a replacement for the textbook. The chapter organization follows Sutton and Barto's second edition; explanations and examples here are original. Use the authors' book page, the MIT Press edition page, and the official table of contents for the primary source and exact section sequence.

Chapter 10 — On-policy Control with Approximation, explained.