10.1 回合制半梯度控制 / Episodic Semi-gradient Control
The extension to action values is straightforward. Now training examples are of the form St, At → Ut. The general semi-gradient Sarsa update:
向动作价值的扩展是直接的。现在训练样本形式为St,At→Ut。通用半梯度Sarsa更新：
wt+1 = wt + α [Ut − q̂(St, At, wt)] ∇q̂(St, At, wt)
For one-step Sarsa (episodic semi-gradient Sarsa):
对于单步Sarsa（回合制半梯度Sarsa）：
wt+1 = wt + α [Rt+1 + γq̂(St+1, At+1, wt) − q̂(St, At, wt)] ∇q̂(St, At, wt)
Episodic Semi-gradient Sarsa for Estimating q̂ ≈ q*
────────────────────────────────────────────
Input: differentiable q̂: S × A × ℝd → ℝ
Parameters: step size α > 0, small ε > 0
Initialize weights w arbitrarily
Loop for each episode:
S, A ← initial state and action (e.g., ε-greedy)
Loop for each step:
Take action A, observe R, S'
If S' is terminal:
w ← w + α [R − q̂(S, A, w)] ∇q̂(S, A, w)
→ next episode
Choose A' from q̂(S', ·, w) (e.g., ε-greedy)
w ← w + α [R + γq̂(S', A', w) − q̂(S, A, w)] ∇q̂(S, A, w)
S ← S', A ← A'
Policy improvement: for discrete, not-too-large action sets, compute q̂(St, a, wt) for all actions, find greedy action A*t = argmaxa q̂(St, a, wt), then use ε-greedy policy for action selection.
策略改进：对于离散且不太大的动作集，计算所有动作的q̂(St,a,wt)，找到贪婪动作A*t=argmaxaq̂(St,a,wt)，然后使用ε-greedy策略进行动作选择。
Example 10.1: Mountain Car Task. An underpowered car must drive up a steep mountain road. Gravity is stronger than the engine, so the car must first move
away from the goal to build up
inertia. This is a classic continuous control task where things must get worse before getting better.
- States: position xt ∈ [−1.2, 0.5], velocity ẋt ∈ [−0.07, 0.07]
- Actions: full throttle forward (+1), reverse (−1), zero throttle (0)
- Reward: −1 per step until car reaches goal
- Features: 8 tilings via tile coding with asymmetric offsets
- Initial values all zero → optimistic → drives exploration even with ε=0
例10.1：Mountain Car任务。动力不足的汽车必须开上陡峭的山路。重力强于引擎，所以汽车必须先
远离目标以积累
惯性。这是经典的连续控制任务——事情必须先变差才能变好。
- 状态：位置xt∈[−1.2,0.5]，速度ẋt∈[−0.07,0.07]
- 动作：全油门前进(+1)、全油门后退(−1)、零油门(0)
- 奖励：每步−1直到汽车到达目标
- 特征：8个瓦片集，瓦片编码配合非对称偏移
- 初始值全为零→乐观→即使ε=0也能驱动探索
10.2 半梯度n步Sarsa / Semi-gradient n-step Sarsa
The n-step return generalizes from tabular form to function approximation:
n步回报从表格形式泛化到函数近似：
Gt:t+n = Rt+1 + γRt+2 + ··· + γn−1Rt+n + γnq̂(St+n, At+n, wt+n−1)
wt+n = wt+n−1 + α [Gt:t+n − q̂(St, At, wt+n−1)] ∇q̂(St, At, wt+n−1)
As before, intermediate n (e.g., n=4 or 8) performs best on Mountain Car. Figure 10.4 shows a detailed study of α and n effects — intermediate bootstrapping is optimal, just as in tabular methods.
与之前一样，中间n值（如n=4或8）在Mountain Car上表现最好。图10.4展示了α和n效应的详细研究——与表格方法一样，中间自举是最优的。
Episodic Semi-gradient n-step Sarsa
────────────────────────────────────────────
Input: differentiable q̂: S × A × ℝd → ℝ
Parameters: step size α > 0, ε > 0, positive integer n
Initialize weights w arbitrarily
Loop for each episode:
Initialize S₀ ≠ terminal; select A₀ (ε-greedy); T ← ∞
Loop for t = 0, 1, 2, ...:
If t < T: take At, observe Rt+1, St+1
If St+1 terminal: T ← t+1
Else: select At+1 (ε-greedy)
τ ← t − n + 1
If τ ≥ 0:
G ← Σ γi−τ−1 Ri (i=τ+1 to min(τ+n, T))
If τ+n < T: G ← G + γn q̂(Sτ+n, Aτ+n, w)
w ← w + α [G − q̂(Sτ, Aτ, w)] ∇q̂(Sτ, Aτ, w)
Until τ = T − 1
10.3 平均奖励：持续性任务的新设定 / Average Reward
We now introduce a third classical setting — alongside episodic and discounted — for MDPs: the average reward setting. Like the discounted setting, it applies to continuing problems, but without discounting — the agent cares equally about delayed and immediate rewards.
现在引入MDP的第三种经典设定——与回合制和折扣设定并列：平均奖励设定。与折扣设定一样适用于持续性任务，但没有折扣——智能体对延迟奖励和即时奖励同等关注。
The quality of policy π is defined as the average reward (average rate of reward):
策略π的质量定义为平均奖励（平均奖励率）：
r(π) = limh→∞ 1⁄h Σt=1h E[Rt | S0, A0:t−1 ~ π] = Σs µπ(s) Σa π(a|s) Σs',r p(s',r|s,a) · r
where µπ is the steady-state distribution. The assumption that it exists and is independent of S0 is called ergodicity. All policies attaining maximal r(π) are considered optimal.
其中µπ是稳态分布。假设其存在且独立于S0，这称为遍历性。所有达到最大r(π)的策略被认为是最优的。
Returns are defined in terms of differences between rewards and the average reward — the differential return:
回报用奖励与平均奖励之间的差来定义——即差分回报：
Gt = (Rt+1 − r(π)) + (Rt+2 − r(π)) + (Rt+3 − r(π)) + ···
The corresponding differential value functions vπ(s), qπ(s,a) have Bellman equations with all γ's removed and rewards replaced by (r − r(π)):
相应的差分价值函数vπ(s)、qπ(s,a)的Bellman方程去掉了所有γ，用(r−r(π))替换奖励：
vπ(s) = Σa π(a|s) Σs',r p(s',r|s,a) [r − r(π) + vπ(s')]
qπ(s,a) = Σs',r p(s',r|s,a) [r − r(π) + Σa' π(a'|s') qπ(s',a')]
The differential TD errors:
差分TD误差：
δt = Rt+1 − R̄t + v̂(St+1, wt) − v̂(St, wt) (状态价值)
δt = Rt+1 − R̄t + q̂(St+1, At+1, wt) − q̂(St, At, wt) (动作价值)
where R̄t is an estimate at time t of the average reward r(π). With these alternate definitions, most algorithms carry through unchanged.
其中R̄t是t时刻对平均奖励r(π)的估计。有了这些替代定义，大多数算法无需改变即可沿用。
Differential Semi-gradient Sarsa for Estimating q̂ ≈ q*
────────────────────────────────────────────
Input: differentiable q̂: S × A × ℝd → ℝ
Parameters: step sizes α, β > 0
Initialize w arbitrarily; R̄ arbitrarily (e.g., R̄ = 0)
Initialize state S and action A
Loop for each step:
Take action A, observe R, S'
Choose A' from q̂(S', ·, w) (e.g., ε-greedy)
δ ← R − R̄ + q̂(S', A', w) − q̂(S, A, w)
R̄ ← R̄ + βδ
w ← w + αδ ∇q̂(S, A, w)
S ← S', A ← A'
Example 10.2: Access-Control Queuing Task. 10 servers, customers of 4 priorities (rewards 1,2,4,8). At each step, decide whether to accept or reject the next customer based on priority and number of free servers. Each busy server becomes free with p=0.06 per step. Differential semi-gradient Sarsa learns to maximize long-term reward without discounting.
例10.2：访问控制排队任务。10台服务器，4种优先级的客户（奖励1,2,4,8）。每步决定是否根据优先级和空闲服务器数量接受或拒绝下一个客户。每台忙碌服务器每步以p=0.06的概率变为空闲。差分半梯度Sarsa学习在无折扣情况下最大化长期奖励。
10.4 废弃折扣设定 / Deprecating the Discounted Setting
With function approximation in continuing problems, discounting is futile! The average of discounted returns over the on-policy distribution is always r(π)/(1−γ) — proportional to average reward. The discount rate γ has no effect on policy ordering.
在持续性问题的函数近似中，折扣是无效的！on-policy分布上折扣回报的平均值始终为r(π)/(1−γ)——与平均奖励成正比。折扣率γ对策略排序没有影响。
💡 证明直觉（对称性论证）：每个时间步与其他步完全相同。有折扣时，每个奖励在每个回报的每个位置恰好出现一次。第t个奖励的权重为 1+γ+γ²+···=1/(1−γ)。由于所有状态相同，回报的平均值就是该权重乘以平均奖励，即r(π)/(1−γ)。
Proof: J(π) = Σs µπ(s)vπγ(s) = r(π) + γJ(π) = r(π)/(1−γ). The discounted objective orders policies identically to the undiscounted (average reward) objective!
证明：J(π)=Σsµπ(s)vπγ(s)=r(π)+γJ(π)=r(π)/(1−γ)。折扣目标与无折扣（平均奖励）目标完全相同地排列策略！
The root cause: with function approximation we have lost the policy improvement theorem (Section 4.2). It is no longer true that improving the discounted value of one state guarantees improving the overall policy. γ changes from a problem parameter to a solution method parameter.
根本原因：有了函数近似，我们失去了策略改进定理（第4.2节）。改善一个状态的折扣值不再保证改善整体策略。γ从问题参数变为求解方法参数。
⚠️ 理论缺陷：策略改进定理的缺失也是回合制和平均奖励设定的理论空白。一旦引入函数近似，就无法保证任何设定下的改进。第13章的参数化策略方法提供了"策略梯度定理"作为替代保证。
10.5 差分半梯度n步Sarsa / Differential n-step Sarsa
The differential n-step return:
差分n步回报：
Gt:t+n = (Rt+1 − R̄t+n−1) + ··· + (Rt+n − R̄t+n−1) + q̂(St+n, At+n, wt+n−1)
δt = Gt:t+n − q̂(St, At, w)
Differential Semi-gradient n-step Sarsa
────────────────────────────────────────────
Input: differentiable q̂: S × A × ℝd → ℝ
Initialize w arbitrarily; R̄ arbitrarily
Parameters: α, β > 0, positive integer n
Initialize and store S₀ and A₀
Loop for each step t = 0, 1, 2, ...:
Take action At, observe Rt+1, St+1
Select At+1 (ε-greedy wrt q̂)
τ ← t − n + 1
If τ ≥ 0:
δ ← Σ(Ri − R̄) + q̂(Sτ+n, Aτ+n, w) − q̂(Sτ, Aτ, w)
R̄ ← R̄ + βδ
w ← w + αδ ∇q̂(Sτ, Aτ, w)
💡 实用提示：平均奖励的步长参数β需要非常小以使R̄成为良好的长期估计。但这会导致R̄受初始值偏差影响很多步。可以使用练习2.7中的无偏常数步长技巧来改善。