引言 / Introduction
In this chapter we consider our first learning methods for estimating value functions and discovering optimal policies. Unlike the previous chapter, here we do not assume complete knowledge of the environment. Monte Carlo methods require only experience—sample sequences of states, actions, and rewards from actual or simulated interaction with an environment.
本章介绍我们第一批学习方法，用于估计价值函数和发现最优策略。与上一章不同，这里我们不假设对环境有完整的了解。蒙特卡洛方法只需要经验——即从与环境的实际或模拟交互中获取的状态、动作和奖励的样本序列。
Monte Carlo methods are ways of solving the RL problem based on averaging sample returns. To ensure well-defined returns are available, we define MC methods only for episodic tasks. Experience is divided into episodes, and all episodes eventually terminate. Only on the completion of an episode are value estimates and policies changed.
蒙特卡洛方法是基于平均样本回报来解决强化学习问题的方法。为确保有定义良好的回报，我们仅对回合制任务定义MC方法。经验被划分为若干回合，所有回合最终都会终止。只有在回合完成时，价值估计和策略才会改变。
To handle the nonstationarity, we adapt the idea of generalized policy iteration (GPI) developed in Chapter 4 for DP. Whereas there we computed value functions from knowledge of the MDP, here we learn value functions from sample returns with the MDP.
为了处理非平稳性，我们沿用了第四章为DP开发的广义策略迭代（GPI）思想。在那里我们从MDP的知识计算价值函数，而在这里我们从MDP的样本回报中学习价值函数。
5.1 蒙特卡洛预测 / Monte Carlo Prediction
We begin by considering MC methods for learning the state-value function for a given policy. The value of a state is the expected return—expected cumulative future discounted reward. An obvious way to estimate it from experience is simply to average the returns observed after visits to that state.
我们首先考虑用MC方法学习给定策略下的状态价值函数。一个状态的价值是期望回报——即期望的累积未来折扣奖励。从经验中估计它的一个显而易见的方法就是简单地平均在该状态被访问后观察到的回报。
First-visit MC estimates vπ(s) as the average of returns following first visits to s. Every-visit MC averages returns following all visits to s. Both converge to vπ(s) as the number of visits goes to infinity.
首次访问MC将vπ(s)估计为首次访问s后回报的平均值。每次访问MC则平均所有访问s后的回报。两者都随着访问次数趋于无穷大而收敛到vπ(s)。
首次访问MC预测算法，估计V ≈ vπ
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
输入：待评估的策略 π
初始化：
V(s) ∈ ℝ，任意值，对所有 s ∈ S
Returns(s) ← 空列表，对所有 s ∈ S
循环（每个回合）：
按策略 π 生成回合：S₀,A₀,R₁,S₁,...,S_{T-1},A_{T-1},R_T
G ← 0
对回合中每一步 t = T-1, T-2, ..., 0 循环：
G ← γ·G + R_{t+1}
若 S_t 未出现在 S₀,S₁,...,S_{t-1} 中：
将 G 追加到 Returns(S_t)
V(S_t) ← average(Returns(S_t))
Example 5.1: Blackjack. Playing blackjack is naturally formulated as an episodic finite MDP. Each game is an episode. Rewards of +1, −1, and 0 for winning, losing, and drawing. The player makes decisions based on three variables: current sum (12–21), dealer's showing card (ace–10), and whether holding a usable ace. This gives 200 states.
例5.1：21点（Blackjack）。打21点自然地建模为回合制有限MDP。每局游戏是一个回合。赢、输、平的奖励分别为+1、−1和0。玩家基于三个变量做决策：当前总和（12-21）、庄家明牌（A-10）、以及是否有可用A。共200个状态。
💡 关键优势 / Key Advantage: MC方法对每个状态的估计是独立的——一个状态的估计不依赖于其他状态的估计（不像DP那样自举/bootstrap）。估计单个状态值的计算代价与状态总数无关。
5.2 动作价值估计 / Monte Carlo Estimation of Action Values
If a model is not available, it is particularly useful to estimate action values (values of state–action pairs) rather than state values. With a model, state values alone suffice to determine a policy. Without a model, one must explicitly estimate the value of each action.
如果没有模型，估计动作价值（状态-动作对的价值）比状态价值更有用。有模型时，仅状态价值就足以确定策略。没有模型时，必须显式地估计每个动作的价值。
The only complication is that many state–action pairs may never be visited. When MC methods are used to estimate action values, this is a serious problem. This is the general problem of maintaining exploration.
唯一的复杂之处是许多状态-动作对可能永远不会被访问到。当用MC方法估计动作价值时，这是一个严重的问题。这就是维持探索的一般性问题。
5.3 蒙特卡洛控制 / Monte Carlo Control
In Monte Carlo ES (Exploring Starts), all episodes start with a state–action pair randomly selected to cover all possibilities. The policy is improved by making it greedy with respect to the current action-value function.
在蒙特卡洛ES（探索起点）中，所有回合以随机选择的状态-动作对开始，以覆盖所有可能性。通过使策略关于当前动作价值函数变为贪心策略来进行策略改进。
蒙特卡洛ES（探索起点）控制，估计 π ≈ π*
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
初始化：
π(s) ∈ A(s)（任意），对所有 s ∈ S
Q(s,a) ∈ ℝ（任意），对所有 s ∈ S, a ∈ A(s)
Returns(s,a) ← 空列表
循环（每个回合）：
随机选择 S₀, A₀（保证所有对都能被选到）
按策略 π 从 S₀,A₀ 生成回合
G ← 0
对 t = T-1, T-2, ..., 0：
G ← γ·G + R_{t+1}
若 (S_t,A_t) 未在之前出现过：
将 G 追加到 Returns(S_t,A_t)
Q(S_t,A_t) ← average(Returns(S_t,A_t))
A* ← argmax_a Q(S_t,a)
π(S_t) ← A*
⚠️ 局限性：探索起点假设在实践中通常不现实——我们不能总是随意重置到任意状态-动作对。
5.4 无探索起点的MC控制 / MC Control without Exploring Starts
The only general way to ensure all actions are selected infinitely often is for the agent to continue to select them. On-policy methods evaluate/improve the policy used for decisions. Off-policy methods evaluate/improve a different policy from that used to generate data.
确保所有动作被无限次选择的唯一通用方法是让智能体持续选择它们。On-policy方法评估/改进用于决策的策略。Off-policy方法评估/改进一个不同于用于生成数据的策略。
The on-policy method uses ε-greedy policies: most of the time choose the action with maximal estimated value, but with probability ε select a random action. All nongreedy actions get probability ε/|A(s)|, and the greedy action gets 1 − ε + ε/|A(s)|.
On-policy方法使用ε-贪心策略：大部分时间选择估计价值最大的动作，但以概率ε随机选择一个动作。所有非贪心动作获得概率ε/|A(s)|，贪心动作获得1 − ε + ε/|A(s)|。
On-policy首次访问MC控制（ε-soft策略），估计 π ≈ π*
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
算法参数：小 ε > 0
初始化：π ← 任意 ε-soft 策略
循环（每个回合）：
按策略 π 生成回合
对每个 (S_t, A_t)：
Q(S_t,A_t) ← 更新（同MC ES）
A* ← argmax_a Q(S_t,a)
对所有 a ∈ A(S_t)：
π(a|S_t) ← 1−ε+ε/|A| 若 a=A*
π(a|S_t) ← ε/|A| 若 a≠A*
💡 策略改进定理保证：对于任何ε-soft策略π，关于qπ的ε-贪心策略π'保证满足 vπ'(s) ≥ vπ(s)。当ε-soft策略不再被改进时，它就是ε-soft策略中最优的。
5.5 Off-policy预测（重要性采样）/ Off-policy Prediction via Importance Sampling
All learning control methods face a dilemma: they seek to learn about optimal behavior but need to behave non-optimally to explore. Off-policy methods use two policies: a target policy π (being learned about) and a behavior policy b (used to generate data).
所有学习控制方法都面临一个困境：它们想学习最优行为，但需要非最优地行为来探索。Off-policy方法使用两个策略：目标策略π（被学习的对象）和行为策略b（用于生成数据）。
Importance sampling weights returns by the relative probability of trajectories under target and behavior policies. The importance-sampling ratio is:
重要性采样通过目标策略和行为策略下轨迹的相对概率来加权回报。重要性采样比率为：
ρt:T-1 = ∏k=tT-1 π(Ak|Sk) / b(Ak|Sk)
💡 关键发现：虽然轨迹概率依赖于MDP的转移概率（通常未知），但它们在分子和分母中完全相同，因此被抵消了。重要性采样比率仅依赖于两个策略和序列，而不依赖于MDP。
Ordinary importance sampling uses a simple average: V(s) = (1/|T(s)|) Σ ρt:T-1 Gt. This produces unbiased estimates but may have infinite variance.
普通重要性采样使用简单平均：V(s) = (1/|T(s)|) Σ ρt:T-1 Gt。这产生无偏估计，但可能有无穷大方差。
Weighted importance sampling uses a weighted average: V(s) = Σ ρt:T-1 Gt / Σ ρt:T-1. This always has finite variance and is preferred in practice.
加权重要性采样使用加权平均：V(s) = Σ ρt:T-1 Gt / Σ ρt:T-1。这总是有有限方差，在实践中更受青睐。
⚠️ 例5.5：普通重要性采样在某些问题上极其不稳定——即使经过数百万回合，估计值也无法收敛到正确值。这是因为重要性采样缩放回报的方差可能是无穷大的。
5.6 增量实现 / Incremental Implementation
MC prediction methods can be implemented incrementally, episode-by-episode. For on-policy methods, same techniques as Chapter 2 apply (averaging returns instead of rewards). For off-policy with weighted importance sampling, we maintain a cumulative weight sum Cn:
MC预测方法可以逐回合增量实现。对于on-policy方法，使用与第2章相同的技术（平均回报而非奖励）。对于带加权重要性采样的off-policy方法，我们维护累积权重和Cn：
Vn+1 = Vn + (Wn / Cn) · [Gn − Vn]
Cn+1 = Cn + Wn+1
Off-policy MC预测（策略评估），估计 Q ≈ qπ
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
输入：任意目标策略 π
初始化：Q(s,a) ∈ ℝ（任意），C(s,a) ← 0
循环（每个回合）：
b ← 满足 π 覆盖条件的任意策略
按 b 生成回合
G ← 0, W ← 1
对 t = T-1, T-2, ..., 0（当 W ≠ 0）：
G ← γ·G + R_{t+1}
C(S_t,A_t) ← C(S_t,A_t) + W
Q(S_t,A_t) ← Q(S_t,A_t) + (W/C(S_t,A_t))[G − Q(S_t,A_t)]
W ← W · π(A_t|S_t) / b(A_t|S_t)
5.7 Off-policy MC控制 / Off-policy Monte Carlo Control
In off-policy control, the target policy π ≈ π* is greedy with respect to Q (estimate of qπ), while the behavior policy b is soft (e.g., ε-greedy) to ensure exploration. The policy π converges to optimal at all encountered states.
在off-policy控制中，目标策略π ≈ π*关于Q（qπ的估计）是贪心的，而行为策略b是soft的（如ε-贪心）以确保探索。策略π在所有遇到的状态上收敛到最优。
Off-policy MC控制，估计 π ≈ π*
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
初始化：Q(s,a) ∈ ℝ，C(s,a) ← 0
π(s) ← argmax_a Q(s,a)
循环（每个回合）：
b ← 任意 soft 策略
按 b 生成回合：S₀,A₀,R₁,...,S_{T-1},A_{T-1},R_T
G ← 0, W ← 1
对 t = T-1, T-2, ..., 0：
G ← γ·G + R_{t+1}
C(S_t,A_t) ← C(S_t,A_t) + W
Q(S_t,A_t) ← Q(S_t,A_t) + (W/C(S_t,A_t))[G − Q(S_t,A_t)]
π(S_t) ← argmax_a Q(S_t,a)
若 A_t ≠ π(S_t)，退出内层循环（进入下一回合）
W ← W · 1/b(A_t|S_t)
⚠️ 潜在问题：此方法仅从回合的尾部学习——即当回合中所有剩余动作都是贪心的时候。如果非贪心动作很常见，学习将会很慢。
5.8 *折扣感知重要性采样 / Discounting-aware Importance Sampling
When episodes are long and γ is significantly less than 1, conventional importance sampling introduces enormous unnecessary variance. The key insight: treat discounting as a probability of partial termination. The return G0 can be decomposed into flat partial returns weighted by termination probabilities.
当回合很长且γ显著小于1时，传统重要性采样会引入巨大的不必要方差。关键洞察：将折扣视为部分终止的概率。回报G0可以分解为由终止概率加权的平坦部分回报。
Gt = (1−γ) Σh=t+1T-1 γh-t-1 G̅t:h + γT-t-1 G̅t:T
其中 G̅t:h = Rt+1 + Rt+2 + ··· + Rh（平坦部分回报）
5.9 *逐决策重要性采样 / Per-decision Importance Sampling
Even without discounting (γ=1), the structure of returns as sums of rewards can reduce variance. Each reward Rt+k in the return only needs to be scaled by the importance-sampling ratio up to that point, not the full ratio. This is per-decision importance sampling.
即使没有折扣（γ=1），回报作为奖励之和的结构也可以减少方差。回报中的每个奖励Rt+k只需要用截至该点的重要性采样比率来缩放，而非完整比率。这就是逐决策重要性采样。
G̃t = ρt:t Rt+1 + γρt:t+1 Rt+2 + γ²ρt:t+2 Rt+3 + ···
5.10 小结 / Summary
Monte Carlo methods learn value functions from sample episodes. They have at least four advantages over DP: (1) learn directly from interaction without a model; (2) work with simulation/samples; (3) easy to focus on a subset of states; (4) may be less harmed by violations of the Markov property (no bootstrapping).
蒙特卡洛方法从样本回合中学习价值函数。相比DP至少有四大优势：(1) 直接从交互中学习，无需模型；(2) 可与仿真/样本配合使用；(3) 容易聚焦于状态子集；(4) 可能较少受马尔可夫性违反的影响（不自举）。
MC control follows GPI: intermix policy evaluation (averaging returns) and policy improvement. On-policy methods learn the value of the exploratory policy. Off-policy methods separate behavior and target policies, using importance sampling.
MC控制遵循GPI：交替进行策略评估（平均回报）和策略改进。On-policy方法学习探索性策略的价值。Off-policy方法将行为策略和目标策略分离，使用重要性采样。
核心概念速查 / Key Concepts
| 术语 / Term | 英文 / English | 含义 / Meaning |
|---|
| 首次访问MC | First-visit MC | 仅平均首次访问状态后的回报 |
| 每次访问MC | Every-visit MC | 平均所有访问状态后的回报 |
| 探索起点 | Exploring Starts | 随机选择初始状态-动作对以确保覆盖 |
| On-policy | On-policy | 学习和使用同一策略 |
| Off-policy | Off-policy | 学习目标策略，使用行为策略生成数据 |
| 重要性采样 | Importance Sampling | 通过策略概率比加权回报 |
| 普通重要性采样 | Ordinary IS | 简单平均加权回报（无偏，方差可能无穷大） |
| 加权重要性采样 | Weighted IS | 加权平均（有偏但一致，方差有限） |
| ε-贪心策略 | ε-greedy Policy | 以1-ε概率选贪心动作，ε概率随机探索 |
| GPI | Generalized Policy Iteration | 策略评估与策略改进的交互过程 |