第 1 课：MDP、回报与 Bellman 递推

本课目标与完成标准

学完后你应能：把轨迹写成 MDP 五元组，区分即时奖励、折扣回报与状态价值，并手推有限时域 Bellman 递推。

通过必须同时满足：

• 独立补齐本课唯一的代码填空题，并通过给定检查；
• 三个问答题均说明因果链，而不是只报术语；
• 能指出至少一个正确性边界和一个性能取舍；
• 总分不低于 8/10，且没有一票否决级概念错误。

前置关系

• 课程前置：Python、概率期望、基本深度学习
• 本课在路线中的作用：MDP 用状态、动作、转移、奖励和折扣描述顺序决策；它把“长期好坏”变成可递推的期望回报。

核心心智模型

1. 它是什么，解决什么问题

强化学习（Reinforcement Learning）的数学基石是马尔可夫决策过程（Markov Decision Process, MDP）。一个标准的离散时间 MDP 由五元组构成： $$\mathcal{M} = \langle \mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma \rangle$$

• $\mathcal{S}$：状态空间（State Space），必须满足马尔可夫性质：$P(s_{t+1} \mid s_t, a_t, \dots, s_0, a_0) = P(s_{t+1} \mid s_t, a_t)$，即“未来独立于过去，仅取决于现在”；
• $\mathcal{A}$：动作空间（Action Space）；
• $\mathcal{P}(s' \mid s, a)$：环境状态转移概率矩阵；
• $\mathcal{R}(s, a)$：即时奖励函数（Immediate Reward）；
• $\gamma \in [0, 1]$：折扣因子（Discount Factor）。 传统监督学习（SL）解决的是“单步静态映射”问题，模型只能评估单步输出与真值标签的瞬时损失；而顺序决策面临的核心困难是延迟奖励（Delayed Reward）与信用分配问题（Credit Assignment Problem）——智能体在第 0 步下的关键决策，可能要到第 100 步才爆发全局回报（如围棋的神之一手，或大模型推理链生成最终正确答案）。 MDP 与 Bellman 递推解决的核心工程问题是：如何将无限时域或长程序列的全局累积收益，递归拆解为局部可观测的即时奖励与下一状态价值，建立起时序差分学习与策略优化的闭环数学方程。

2. 它如何工作

MDP 状态转移与逆序回报递推流程如图 1-1 与图 1-2 所示：

马尔可夫决策过程 (MDP) 状态转移与回报

当前状态 s

动作 a

下一状态 s'

即时奖励 r = R(s, a)

未来回报 G_t = r + γ V(s')

执行动作 a ~ π环境转移动力学 P奖励函数 R折现累加 γ

图 1-1：MDP 状态转移五元组与 Bellman 期望方程分解拓扑

终止时刻 T: G_T = 0

倒数第一步: G_{T-1} = R_{T-1} + γ G_T

倒数第二步: G_{T-2} = R_{T-2} + γ G_{T-1}

时刻 0: G_0 = 累积折现回报

图 1-2：有限时域轨迹回报逆序动态规划递推流程

1. 轨迹的累积折扣回报（Cumulative Discounted Return）： 在一条从时刻 $t$ 到终止时刻 $T$ 的完整轨迹采样中，折扣回报定义为未来所有奖励的加权和： $$G_t = \sum_{k=0}^{T - t - 1} \gamma^k r_{t+k} = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \dots$$ 这一公式天然具备反向递推（Backward Recurrence）结构： $$G_t = r_t + \gamma G_{t+1} \quad (\text{终止步边界条件: } G_T = 0)$$ 如图 1-2 所示，算法只需从轨迹末端 $T-1$ 向前进行单遍线性扫描（时间复杂度 $O(T)$），即可一次性精准求出所有时刻的真实回报。

2. 状态价值与 Bellman 期望方程（Bellman Expectation Equation）： 状态价值函数 $V^\pi(s)$ 定义为在策略 $\pi$ 下从状态 $s$ 出发所能获得的累积回报的数学期望： $$V^\pi(s) = \mathbb{E}_\pi [G_t \mid s_t = s]$$ 利用条件期望全概率公式，将其递归展开为贝尔曼期望方程： $$V^\pi(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s) \left[ \mathcal{R}(s, a) + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}(s' \mid s, a) V^\pi(s') \right]$$ 这证明了：当前状态的长期价值等于当前即时奖励期望加上下一状态长期价值的折现期望。

3. 正确性条件与常见误区

• 终止（Terminated）vs 截断（Truncated）的致命混淆： 在 Gym/Gymnasium 及大模型训练中，环境返回的 done 信号包含两种截然相反的语义：
  • terminated = True：代表任务自然到达客观终止状态（如游戏通关、撞墙死机、或 LLM 生成了 <|end_of_text|> 结束符）。此时智能体在物理上再无未来，其后续价值严格为零（$V(s_{T}) = 0$）；
  • truncated = True：代表仅因工程人为限制（如超时超步、最大 Token 上限限制 max_seq_len）而强行切断采样。物理环境本可继续运行，因此绝对不能将截断末端的价值置零，必须通过价值网络对真实末状态进行自举（Bootstrap: $G_{T-1} = r_{T-1} + \gamma V(s_{T})$），否则会导致灾难性的价值系统性低估。
• 折扣因子 $\gamma$ 的大模型语义异化： 在传统游戏控制中，$\gamma < 1$（如 0.99）用于防止无穷时域回报发散；但在大语言模型（LLM）后训练（如 RLHF / PPO / GRPO）中，序列时域天然是有限的（最大上下文窗口），且核心目标是保证回答的最终准确率。此时通常强制设置 $\gamma = 1.0$。若盲目设置 $\gamma < 1$，会导致模型产生严重的“近视短视倾向”（倾向于生成简短的草率回答，惩罚深度长思考推理链）。

4. 性能与工程取舍

• 反向动规（$O(T)$）vs 正向朴素求和（$O(T^2)$）： 若在每个时刻 $t$ 独立向后切片求和 $\sum_{k=0}^{T-t-1} \gamma^k r_{t+k}$，计算复杂度为 $O(T^2)$。对于长度 $T = 4096$ 的轨迹，约需 $T^2/2 \approx 8.4 \times 10^6$ 次乘加；而采用本课代码实现的自后向前一维递推扫描（Reverse Linear Scan），只需 $O(T)$ 时间与常数额外内存，运算量约为前者的 $2/T$。

• 折扣因子 $\gamma$ 的方差-偏差权衡（Variance-Bias Dilemma）： $\gamma$ 越接近 1，智能体越具远见，对长程 delayed reward 建模越充分，但蒙特卡洛采样的方差巨大，需要海量样本才能收敛；$\gamma$ 越小，有效时域越短，累积回报方差越低，训练稳定性提升，但由于过早衰减未来，可能完全学不会需要长期前置铺垫的复杂全局策略。

具体演示：从轨迹回报到 LLM 生成

奖励 [1, 0, 2]、γ=0.9 时，反向得到 G₂=2、G₁=1.8、G₀=2.62。

单轮语言模型生成也能写成 MDP：状态 sₜ=(prompt, 已生成前缀)，动作 aₜ=下一个 token，转移是把 token 拼到前缀，EOS 结束轨迹。策略是 token 分布；纯文本拼接转移确定，不意味着策略确定。工具调用后的观测则可能来自随机或变化的环境。

若只在回答完成后给奖励，也可以用 contextual bandit：prompt x 是上下文，完整回答 y 是一个动作。两种写法使用同一个自回归模型，且 logπ(y|x)=Σₜ logπ(yₜ|x,y<ₜ)。结果奖励可在 token MDP 的末步发放；过程奖励在中间推理步骤发放，不等于每个 token 都有独立质量标签。

LLM 后训练常取 γ=1；若末端正确性奖励为 1、前面全为 0，则每个位置的未折扣 return 都为 1。取 γ<1 会改变长短回答的回报权重，不能不加说明地沿用。

实践任务：唯一代码填空题

补齐折扣回报的反向扫描。

规则：只能修改 TODO/______ 所在位置；不要删除断言或放宽误差。代码注释说明了每个边界条件。

def discounted_returns(rewards, gamma):
    out = [0.0] * len(rewards)
    running = 0.0
    for t in range(len(rewards) - 1, -1, -1):
        running = rewards[t] + gamma * running
        out[t] = round(running, 10)
    return ______

assert discounted_returns([1., 0., 2.], 0.9) == [2.62, 1.8, 2.0]
assert discounted_returns([], 0.9) == []

检查方法

运行两个断言；空轨迹必须返回空列表。

提交时请给出：补齐后的代码、实际运行输出（环境不可用时注明“仅静态审查”）以及对失败用例的解释。

Q1

不要背定义：请从输入、状态变化和输出三个阶段解释“MDP、回报与 Bellman 递推”的工作机制。

你的答案：

Q2

把时间上限截断也当成真正终止并把末端价值设为 0，会产生什么偏差？

你的答案：

Q3

若奖励整体乘 100，策略最优解可能不变，但学习动态会怎样变化？

你的答案：

评分与通过规则

• 代码 4 分：正常输入 2 分，边界输入 1 分，解释实现 1 分；
• Q1～Q3 各 2 分；
• 一票否决：结果碰巧正确但核心因果链错误、删除边界检查、把未运行结果说成实测。

需要提示时按四级机制请求：概念区域 → 具体方向 → 关键局部 → 完整答案。

Tip💡 点击展开参考答案与详细代码实现

参考答案（仅 answer 分支）

先完成题目再核对。即使代码一致，也要能解释关键步骤，并尝试更换一个输入规模。

def discounted_returns(rewards, gamma):
    out = [0.0] * len(rewards)
    running = 0.0
    for t in range(len(rewards) - 1, -1, -1):
        running = rewards[t] + gamma * running
        out[t] = round(running, 10)
    return out

assert discounted_returns([1., 0., 2.], 0.9) == [2.62, 1.8, 2.0]
assert discounted_returns([], 0.9) == []

Q1 参考答案

1. 输入：轨迹 $s_0, a_0, r_0, \dots, s_T$、终止/截断标志与折扣因子 $\gamma$。LLM 中状态是 Prompt 加已生成前缀，动作是下一个 token，奖励来自评测器。

2. 状态变化：样本层从 $G_T = 0$（截断时用 $V(s_T)$ 自举）出发，按 $G_t = r_t + \gamma G_{t+1}$ 逆序递推，把远端奖励分配给前面的决策步；期望层把它推广为 Bellman 期望方程 $V^\pi(s) = \sum_a \pi(a|s) [R(s,a) + \gamma \sum_{s'} P(s'|s,a) V^\pi(s')]$，约束相邻状态价值的一致性（详见第 2 节）。

3. 输出：各步回报 $G_0, \dots, G_{T-1}$ 与拟合的 $V(s)$，供后续计算优势 $A(s, a) = Q(s, a) - V(s)$ 做信用分配。

Q2 参考答案

将超时截断（Truncation）错误当作物理终止（Termination）并将末端价值强行置零（$V(s_T) = 0$），在后续奖励为正时会产生系统性价值低估偏差（Negative Value Bias）（后续奖励为负时则是高估）：

1. 数学本质破坏：物理终止代表系统进入吸收态（Absorbing State），物理上再无任何后续转移与奖励，其未来真实价值严格为 0；而截断只是由于人为工程限制（如达到环境最大步数限制 max_steps 或 LLM max_new_tokens），当前状态 $s_T$ 依然具有丰富的未来潜在价值（$V^*(s_T) > 0$）。

2. 信用分配歪曲：若强行置零，会导致末端倒数若干步的折现回报 $G_{T-1} = r_{T-1} + \gamma \times 0$ 丢失了本应继承的 $\gamma V(s_T)$，使得智能体误以为接近时间限制的状态是“极度危险或极其糟糕”的，诱导策略在临近截断时产生病态的自杀行为或逃避行为。

3. 正确工程实践：环境步满截断时，必须通过当前 Critic 价值网络对末状态 $s_T$ 进行自举（Bootstrap: $G_t^{\text{bootstrap}} = r_{T-1} + \gamma V(s_T)$），且绝对不能用环境在 reset() 之后产出的新 episode 起始状态来做自举。

Q3 参考答案

若即时奖励全部等比例放大 100 倍（$r' = 100r$），在理论最优性与实际深度强化学习训练动态中呈现出显著的分离：

1. 理论最优策略不变：根据马尔可夫决策过程的线性性质，由于 $G'_t = 100 G_t$，$Q'_*(s, a) = 100 Q_*(s, a)$，对于任意动作 $a_1, a_2$，若 $Q_*(s, a_1) > Q_*(s, a_2)$，则依然严格有 $Q'_*(s, a_1) > Q'_*(s, a_2)$，最优策略 $\pi^* = \arg\max_a Q^*(s, a)$ 的理论极值点保持完全一致。

2. 神经网络优化动态剧烈恶化：

   • 价值损失与梯度变大：Critic 的均方误差损失为 $\mathcal{L}_V = (V_\phi(s) - G_t)^2$。回报放大 100 倍后，误差放大 100 倍，损失值放大 $100^2 = 10^4$ 倍，而梯度 $2(V_\phi - G_t)\nabla_\phi V_\phi$ 放大约 100 倍。SGD 下这会让步长过大；Adam 按梯度二阶矩归一化，单步幅度受影响较小，但 Critic 需要把输出拟合到大 100 倍的数值范围，初期误差和训练不稳定性都会增加；
   • 策略梯度范数失衡：未进行方差标准化的策略梯度 $\nabla_\theta \mathcal{J} \approx \mathbb{E}[\nabla_\theta \log \pi_\theta(a|s) \cdot A(s, a)]$ 会直接放大 100 倍，导致单步参数更新过大破坏策略；
   • 正则化与惩罚项相对失真：若算法中包含未经缩放的固定超参数（如 PPO 中的熵正则系数 $\beta_{\text{ent}} H(\pi)$，或 RLHF 中与参考模型对齐的固定系数 KL 惩罚 $\beta_{\text{KL}} D_{\text{KL}}(\pi || \pi_{\text{ref}})$），奖励放大 100 倍将使得原有的 KL 惩罚或熵正则相对于奖励信号被削弱为原本的 $1/100$，导致探索过早崩塌或发生灾难性策略漂移（Reward Hacking）。因此，工业界在调节奖励尺度时必须同步调整网络学习率或对 Advantage/Return 实施 Running Normalization。

参考资料

• Back to Basics：token MDP 与完整回答 bandit（§2）

资料用于建立事实基线；本课数值例子是教学计算，不是模型训练结果。

← 上一课
第 8 课：故障恢复、Checkpoint … 下一课 →
第 2 课：Monte Carlo、TD 与…