Lecture 2: 有模型下的序列决策 —— 表格型 MDP 规划（Tabular MDP Planning）

目录 · ← l1 · l3 →

Lecture 2: 有模型下的序列决策 —— 表格型 MDP 规划（Tabular MDP Planning）

对应材料：官方 lecture2pre.pdf / lecture2post.pdf（各 58 页，post 版含课上板书与 Quick Check 答案）｜Week 1 周三 Jan 7, 2026（Assignment 1 本周五发布，下周五 18:00 截止）｜参考阅读 Sutton & Barto (2018) Chp 3, 4.1–4.4 一句话定位：本讲是整门课的「地基」——在已知世界模型（dynamics + reward）的强假设下，把「做出一串好决策」变成一个可以用动态规划（dynamic programming, DP）精确求解的优化问题；值迭代（VI）与策略迭代（PI）是后续 model-free 控制（L4）、策略梯度（L5–L7）、MCTS（L13）全部算法的祖先。

2.1 概述

本讲回答的核心问题是：假设我们完整地知道世界如何运作（状态转移 $P$ 与奖励 $R$ 都已知），如何计算一个策略的价值、并找出最优策略？与 L1 相比，L1 只是”提出”了 agent 由 model / value / policy 三件套构成，本讲则把这三件套写成了严格的数学对象（Markov 链 → Markov 奖励过程 → Markov 决策过程）并给出可执行的算法。

本讲引入两类算法：值迭代（Value Iteration, VI）——反复对值函数施加 Bellman 最优备份算子，并利用其 $\gamma$-压缩性保证唯一不动点；策略迭代（Policy Iteration, PI）——反复「精确评估当前策略 → 对其贪心改进」，并利用策略改进定理（Policy Improvement Theorem）保证每一轮策略都单调不变差、因而必然在有限轮内停止。两者都只需 $O(\vert \mathcal{S}\vert ^2\vert \mathcal{A}\vert )$ 级别的每轮计算量，却完全绕开了 $\vert \mathcal{A}\vert ^{\vert \mathcal{S}\vert }$ 的策略枚举。

在课程知识链上，本讲是”给定模型”这一支的终点，也是下一讲的起点：L3 会去掉 model 假设，用采样（Monte Carlo）与自举（TD）来估计 $V^\pi$，但那时所有的评估目标、误差衡量、收敛性直觉仍然是本讲的 Bellman 方程与压缩性。

2.2 核心概念的数学形式化

2.2.1 历史、状态与 Markov 性质

严格定义（历史）：在离散时间下，每个时刻 $t$，agent 采取动作 $a_t$，世界更新并给出观测 $o_t$ 与奖励 $r_t$。历史（history）是过去全部观测、动作与奖励的序列：

agent 依据历史选择动作。状态（state）被定义为历史的函数，$s_t = f(h_t)$，语义是「足以决定下一步会发生什么的信息」。

严格定义（Markov 性质）：状态 $s_t$ 具有 Markov 性质，当且仅当

等价的写法是 $P(s_{t+1}\mid s_t,a_t,\dots,s_0,a_0) = P(s_{t+1}\mid s_t,a_t)$：给定现在，未来与过去条件独立。

直观解释：状态是历史的”充分统计量”（sufficient statistic）。就像下棋时你不需要记住前面 30 手的完整顺序，只需要看当前棋盘——棋盘就是那个充分统计量。

具体示例（Mars Rover，L1/L2 贯穿全课的 7 状态例子）：火星车有 7 个位置 $s_1,\dots,s_7$，动作为 TryLeft / TryRight。奖励模型是 $r(s_1)=+1$、$r(s_7)=+10$、其余为 $0$。L1 给出的随机转移模型为 $P(s_1\mid s_1,\text{TryRight}) = P(s_2\mid s_1,\text{TryRight}) = 0.5$，中间状态同理，端点 $P(s_1\mid s_1,\text{TryLeft})=0.6,\ P(s_2\mid s_1,\text{TryLeft})=0.4$、$P(s_7\mid s_7,\text{TryRight})=0.6,\ P(s_6\mid s_7,\text{TryRight})=0.4$。位置本身就是 Markov 状态：给定当前位置和动作，下一步位置分布与更早的历史无关。

与监督学习的对比：监督学习假设样本 i.i.d.，因此”过去”不携带额外信息；序列决策里过去通过状态进入模型，Markov 假设正是把”非 i.i.d. 的序列”压缩回”一个可以用 i.i.d. 式算子处理的对象”的关键。若 $s_t \ne o_t$（部分可观测），则观测不再 Markov，必须把历史（或 belief）当作状态，这就是 POMDP。

2.2.2 轨迹、Horizon、回报与折扣因子

严格定义（Horizon）：每个 episode 的时间步数 $H$，可以为无穷（infinite horizon），此时若 $P$ 中存在吸收态或 $\gamma<1$ 才保证回报有限。

严格定义（回报，return）：从时刻 $t$ 起的折扣奖励和

严格定义（折扣因子）：$\gamma \in [0,1]$。直观解释：$\gamma=0$ 表示只看即时奖励，$\gamma \to 1$ 表示延迟奖励与即时奖励同等重要。数学上 $\gamma<1$ 让无穷级数收敛（当 $\vert r\vert \le R_{\max}$ 时有 $\vert G_t\vert \le R_{\max}/(1-\gamma)$），这正是后面压缩性证明的算术基础。

具体数字示例（Mars Rover 的 Monte Carlo 估计，讲义 p.45–46）：设 $\gamma = 1/2$、$H=4$、起点 $s_4$，三条采样 episode 的回报分别是

与监督学习的对比：监督学习的损失只看单个样本；RL 的目标是整条轨迹折扣和的期望，因此奖励可以延迟几千步，信用分配（credit assignment）成为核心困难。

2.2.3 MDP 五元组

严格定义（Markov 决策过程, MDP）：MDP 是 Markov 奖励过程加上动作，用一个五元组表示：

其中 $\mathcal{S}$ 是有限状态集 $s\in\mathcal{S}$；$\mathcal{A}$ 是有限动作集 $a\in\mathcal{A}$；$P$ 是每个动作的动力学/转移模型（dynamics / transition model）

且对任意 $(s,a)$ 满足 $\sum_{s^{\prime}} P(s^{\prime}\mid s,a) = 1$、$P(\cdot)\ge 0$；$R$ 是奖励函数 $R(s_t=s, a_t=a) = \mathbb{E}[r_t \mid s_t=s, a_t=a]$；$\gamma\in[0,1]$。

讲义脚注要点：奖励有时定义为状态的函数、或 $(s,a,s^{\prime})$ 三元组的函数；本课程最常用的是 $R(s,a)$（本笔记全部采用这一约定）。

直观解释：MDP = “Markov 链 + 动作 + 奖励”。动作是唯一的控制入口，它同时影响即时奖励和下一步状态分布。

具体示例（Mars Rover MDP，讲义 p.9）：$\mathcal{S}=\{s_1,\dots,s_7\}$，$\mathcal{A}=\{a_1,a_2\}$（两个确定性动作），$R(s_1)=+1$、$R(s_7)=+10$，$P(s^{\prime}\mid s,a)$ 写成两个 $7\times 7$ 行随机矩阵。注意讲义此处用的是「在状态 $s$ 拿到奖励」的状态奖励写法；本笔记的代码为了统一，采用 $R(s,a)$ 形式。

把 MDP 变成 MRP（讲义 p.11）：给定策略 $\pi(a\mid s)$ 后，MDP 就退化成一个 Markov 奖励过程（Markov Reward Process, MRP） $(\mathcal{S}, R^\pi, P^\pi, \gamma)$：

这一步是整讲的”枢纽”：它意味着策略评估可以完全复用 MRP 的工具（矩阵求逆或迭代），而不需要为 MDP 发明新算法。

2.2.4 策略

严格定义（策略）：策略指定每个状态下做什么动作，可以确定性也可以随机；为了一般性，把它看成条件分布

确定性策略是它的退化情形（在某状态上概率为 1），常写作 $\pi(s)=a$。

具体示例：Mars Rover 上的确定性策略 $\pi(s_1)=\pi(s_2)=\cdots=\pi(s_7)=\text{TryRight}$ 把 7 个状态全指向右，共 $2^7 = 128$ 种确定性策略。

注意讲义 PDF 的文本抽取坑：讲义 p.15 的答案在纯文本里显示为 “27”，这是上标丢失造成的——选项集合 $\{2, 14, 72, 27\}$ 实际是 $\{2^7{=}128,\ 14,\ 7^2{=}49,\ 3^3{=}27\}$，正确答案是 $\vert \mathcal{A}\vert ^{\vert \mathcal{S}\vert } = 2^7 = 128$。

与监督学习的对比：监督学习的输出是”标签”；策略是”从状态到动作的规则”，它必须在未见过的状态上也有定义，泛化问题的形态因此完全不同。

2.2.5 状态值函数、动作值函数与优势函数

严格定义（状态值函数）：对 MRP/MDP 的策略 $\pi$，

严格定义（动作值函数，Q 值，讲义 p.20）：

语义是「先执行 $a$，此后永远跟随 $\pi$」的期望折扣回报。

严格定义（优势函数）：$A^\pi(s,a) = Q^\pi(s,a) - V^\pi(s)$，衡量动作 $a$ 相对当前策略平均水平好多少。由定义直接得到 $V^\pi(s) = \sum_a \pi(a\mid s) Q^\pi(s,a)$，故 $\sum_a \pi(a\mid s) A^\pi(s,a) = 0$。

具体示例（Mars Rover，$\gamma=1/2$，$\pi\equiv\text{TryRight}$）：由闭式解 $V = (I-\gamma P)^{-1}R$ 算得

在 $s_6$：$Q^\pi(s_6,\text{TryRight}) = 0 + \tfrac12(0.5\cdot 6.6667 + 0.5\cdot 20) = 6.6667 = V^\pi(s_6)$（$\pi$ 在该状态本就选 TryRight，优势为 0）；而 $Q^\pi(s_6,\text{TryLeft}) = 0 + \tfrac12(0.5\cdot 6.6667 + 0.5\cdot 2.2222) = 2.2222$，优势 $A^\pi(s_6,\text{TryLeft}) = -4.4444$——向左走明显更差。

2.2.6 Bellman 期望方程与 Bellman 最优方程

Bellman 期望方程（用于策略评估）：$V^\pi$ 必须满足

写回 MDP 形式（随机策略）

若 $\pi$ 确定，上式退化为 $V^\pi(s) = R(s,\pi(s)) + \gamma\sum_{s^{\prime}}P(s^{\prime}\mid s,\pi(s))V^\pi(s^{\prime})$。

矩阵形式与闭式解（讲义 p.57–58）：对有限状态 MRP，$V = R + \gamma P V$，于是

求逆的代价约 $O(N^3)$（$N=\vert \mathcal{S}\vert $），且要求 $I-\gamma P$ 可逆——当 $\gamma<1$ 时它必然可逆（因为 $\rho(\gamma P) = \gamma < 1$）。

Bellman 最优方程：最优值函数 $V^*(s) = \max_\pi V^\pi(s)$ 满足

与期望方程的唯一差别是：期望方程对动作求期望（按 $\pi$），最优方程对动作取 max。这个差别正是 PI 与 VI 分道扬镳的根源。

2.2.7 Bellman 备份算子与压缩算子

严格定义（Bellman 最优备份算子）：

严格定义（策略备份算子）：

严格定义（压缩算子，讲义 p.38）：设 $\mathcal{O}$ 是算子，$\vert \cdot\vert $ 是任一范数；若存在 $\gamma<1$ 使 $\vert \mathcal{O}V - \mathcal{O}V^{\prime}\vert \le \gamma\vert V-V^{\prime}\vert $ 对一切 $V,V^{\prime}$ 成立，则称 $\mathcal{O}$ 是压缩算子（contraction operator），$\gamma$ 称为压缩模数。

关键事实：$B$ 与 $B^\pi$ 在无穷范数下都是压缩模数为 $\gamma$ 的压缩算子（证明见 2.3.4）。因此

即 VI 就是反复施加 $B$，策略评估就是反复施加 $B^\pi$——两个算法共享同一套收敛性论证。

2.3 算法伪代码与完整推导

2.3.1 MRP 的迭代策略评估（dynamic programming）

输入: MRP (S, P, R, gamma), 容差 eps
输出: V ≈ V(s)
初始化: V(s) = 0  for all s in S          # 讲义: Initialize V_0(s) = 0
for k = 1, 2, ... until convergence:
    for all s in S:                        # 同步（Jacobi）更新
        V_new(s) = R(s) + gamma * sum_{s' in S} P(s'|s) * V(s')
    if ||V_new - V||_inf <= eps: return V_new
    V = V_new

算法逻辑解说：每一轮把「当前对未来的估计」向前推进一步。初始 $V_0\equiv 0$，第 $k$ 轮后 $V_k(s)$ 恰好等于”还能走 $k$ 步”时的折扣回报期望。

计算复杂度：每轮 $O(\vert \mathcal{S}\vert ^2)$（讲义 p.7 明确给出），因为对每个 $s$ 要对 $\vert \mathcal{S}\vert $ 个后继求和。若 $P$ 稀疏（每状态平均 $b$ 个后继），则为 $O(\vert \mathcal{S}\vert b)$。

与理论的对应：这正是不动点迭代 $V_{k+1} = B^\pi V_k$，收敛率 $\vert V_k - V^\pi\vert _\infty \le \gamma^k\vert V_0 - V^\pi\vert _\infty$。

2.3.2 策略迭代（Policy Iteration, PI）

输入: MDP (S, A, P, R, gamma)
输出: pi* ≈ 最优策略, V* ≈ 最优值函数
Set i = 0
Initialize pi_0(s) randomly for all states s
while i == 0 or ||pi_i - pi_{i-1}||_1 > 0:      # L1 范数: 只要有任一状态动作变了就继续
    V^{pi_i} <- MDP V function policy evaluation of pi_i   # 评估到收敛
    pi_{i+1} <- Policy improvement                          # 贪心改进
    i = i + 1

其中策略改进（policy improvement）步骤为（讲义 p.21）：

for s in S:
    for a in A:
        Q^{pi_i}(s,a) = R(s,a) + gamma * sum_{s' in S} P(s'|s,a) * V^{pi_i}(s')
    pi_{i+1}(s) = argmax_a Q^{pi_i}(s,a)

算法逻辑解说：PI 把「评估」和「改进」交替进行。评估是精确的（求到收敛），改进是贪心的。讲义强调这与一个非常流行的 RL 方法密切相关——策略梯度（policy gradient）：两者都是”评估当前策略 → 用评估结果改进策略”的循环，区别只在改进步骤是 argmax 还是梯度上升。

2.3.3 策略改进定理（Policy Improvement Theorem）与证明

定义（值函数的逐点序）：$V^{\pi_1}\ge V^{\pi_2}$ 当且仅当 $V^{\pi_1}(s)\ge V^{\pi_2}(s)$ 对所有 $s\in\mathcal{S}$ 成立。

命题（讲义 p.25）：设 $\pi_{i+1}$ 是 $\pi_i$ 经策略改进得到的贪心策略，则 $V^{\pi_{i+1}} \ge V^{\pi_i}$；若 $\pi_i$ 非最优，则至少有一个状态上严格不等。

证明（讲义 p.26–27 的完整链条）：对任意 $s\in\mathcal{S}$，

把最后一行的 $V^{\pi_i}$ 继续展开（相当于沿 $\pi_{i+1}$ 的轨迹迭代展开）：

证明的直觉（讲义原话）：”Suppose we take $\pi_{i+1}(s)$ for one action, then follow $\pi_i$ forever — our expected sum of rewards is at least as good as if we had always followed $\pi_i$. But new proposed policy is to always follow $\pi_{i+1}$…” 即：一步换手不会变差；把变差的可能性用 $\max$ 反复封住，整条轨迹都不会变差。

两个 Quick Check 的答案与理由（讲义 p.28–31）：

1. 如果某轮策略没变，之后还会变吗？——不会。 若 $\pi_{i+1}(s)=\pi_i(s)$ 对所有 $s$ 成立，则 $Q^{\pi_{i+1}}(s,a) = Q^{\pi_i}(s,a)$，于是 $\pi_{i+2}(s) = \arg\max_a Q^{\pi_{i+1}}(s,a) = \arg\max_a Q^{\pi_i}(s,a) = \pi_{i+1}(s)$。贪婪映射的迭代自此冻结。
2. PI 的迭代次数有上界吗？——有，最多 $\vert \mathcal{A}\vert ^{\vert \mathcal{S}\vert }$ 轮。 因为确定性策略总数就是 $\vert \mathcal{A}\vert ^{\vert \mathcal{S}\vert }$，而策略改进是严格单调的：同一个非最优策略不可能在 PI 中出现两次（出现两次意味着中间既严格改进又回到原值，与命题矛盾）。故至多枚举完全部策略前必然停在最优策略上。

复杂度：每轮 = 精确评估（一次 $O(\vert \mathcal{S}\vert ^3)$ 求逆，或迭代到收敛 $O(\vert \mathcal{S}\vert ^2)$ 每轮 × 若干轮） + 改进（$O(\vert \mathcal{S}\vert ^2\vert \mathcal{A}\vert )$）。最坏轮数 $\vert \mathcal{A}\vert ^{\vert \mathcal{S}\vert }$，但实际远小于此（见 2.4 实验）。

2.3.4 值迭代（Value Iteration, VI）与压缩性证明

输入: MDP (S, A, P, R, gamma), 容差 eps
输出: V* ≈ 最优值函数, pi* ≈ 最优策略
Set k = 1
Initialize V_0(s) = 0 for all states s
loop until convergence (for ex. ||V_{k+1} - V_k||_inf <= eps):
    for each state s:
        V_{k+1}(s) = max_a [ R(s,a) + gamma * sum_{s' in S} P(s'|s,a) * V_k(s') ]
        pi_{k+1}(s) = argmax_a [ R(s,a) + gamma * sum_{s' in S} P(s'|s,a) * V_k(s') ]

算法逻辑解说：VI 的想法是「维持还剩 $k$ 步时的最优值」（讲义 p.32）。$V_{k+1}=BV_k$ 就是一次 Bellman 备份。注意讲义在 p.37 给出一个细节差异：若已经算出 $V_{k+1}$，提取策略时也可以写成

即用最新的值函数做贪心，这与 PI 的改进步骤形式一致。

有限 Horizon 版本（讲义 p.43）：把 until convergence 换成 for k = 1:H，此时 $V_k$ 精确等于「还能做 $k$ 次决策」的最优值，$\pi_k$ 是相应的最优策略。

Question（讲义 p.47–48）：有限 horizon 下最优策略是平稳的吗？——一般不是。 因为 $V_k$ 随 $k$ 变化，$\arg\max$ 自然可能随剩余步数改变；无限 horizon 才保证存在确定性、平稳的最优策略。

压缩性证明（讲义 p.40–41 逐行代数）：取无穷范数 $\vert V - V^{\prime}\vert _\infty = \max_s \vert V(s)-V^{\prime}(s)\vert $。

利用 $\vert \max_a f(a) - \max_a g(a)\vert \le \max_a \vert f(a)-g(a)\vert $：

注意讲义的强调：”Even if all inequalities are equalities, this is still a contraction if $\gamma<1$”——即不等号取等也无妨，只要 $\gamma<1$，距离就确实缩短了 $\gamma$ 倍。

Banach 不动点定理（Banach fixed-point theorem）：在完备度量空间 $(\mathbb{R}^{\vert \mathcal{S}\vert }, \vert \cdot\vert _\infty)$ 上，压缩映射 $B$ 存在唯一不动点 $V^$，且从任意 $V_0$ 出发 $B^kV_0 \to V^$。这解释了讲义 p.42 的三个课后练习：

• VI 收敛到唯一解（$\gamma<1$、有限状态动作）——由 Banach 定理直接得到。
• 初始化会不会影响结果？ 不会影响极限（唯一不动点），只影响收敛速度与中途提取的策略质量。
• VI 每轮提取的策略是否像 PI 那样单调改进？ 不保证。PI 的单调性来自策略改进定理（它每轮都精确评估、再贪心改进）；VI 是”值函数迭代”，其贪心策略序列没有单调性保证。讲义的原话是”Not all of them do”（不是所有算法都具有单调改进性质）。

收敛速度与迭代次数界：由压缩性立刻得到

因为 $\vert V_0-V^\vert _\infty = \vert V^\vert \infty \le R{\max}/(1-\gamma)$。令右端 $\le \epsilon$ 解出迭代次数界：

这是讲义”$\frac{1}{1-\gamma}$ 与 $\log$ 形式”的具体落地：分母 $\log(1/\gamma)$ 在 $\gamma\to1$ 时约为 $1-\gamma$，所以 $k = \Theta\!\big(\frac{1}{1-\gamma}\log\frac{R_{\max}}{\epsilon(1-\gamma)}\big)$——horizon 越长、精度越高，迭代次数按 $1/(1-\gamma)$ 爆炸。

实用的停机准则：由于 $\vert V_{k+1}-V^*\vert \infty \le \frac{\gamma}{1-\gamma}\vert V{k+1}-V_k\vert _\infty$（$B$ 与不动点的标准界），只要检验量满足

这正是 2.4 代码里使用的阈值，并在数值上得到验证。

2.3.5 VI 与 PI 的对比（讲义的 “which is faster” 讨论）

两张讲义原话值得记住（p.18、p.49）：策略空间有 $\vert \mathcal{A}\vert ^{\vert \mathcal{S}\vert }$ 个确定性策略，而 PI 通常远比枚举高效；VI 是”把 horizon 一步步拉长”，PI 是”把策略一步步改好”，后者与策略梯度同宗。

讲义 p.42 与 p.44 补充的两条评估手段：(a) 有限 horizon 下策略价值也可以纯模拟估计——生成大量 episode、对回报取平均，用集中不等式（concentration inequality）给出平均值的收敛速度，且完全不需要 Markov 假设；(b) 需要判断”哪些策略评估方法依赖 Markov 假设”——依赖 Markov 假设的是所有基于 $B/B^\pi$ 备份的 DP 方法（它们用 $V(s^{\prime})$ 代替整段未来），而 Monte Carlo 平均不需要。

2.4 代码实现与实验分析

本节两个代码块都是完整自包含、可直接运行的（依赖仅 numpy 2.0.1 / matplotlib 3.9.2 / 标准库，GridWorld 与全部 MDP 手写，不使用任何 RL 库）；扩展实验的完整脚本另存于 cs234/code/L02_value_iteration.py（值迭代，含曲率、迭代次数界、$\gamma{=}1$ 失效反例、特征值分析，实测运行 < 2 秒）与 cs234/code/L02_policy_iteration.py（策略迭代，含策略改进定理逐状态验证、VI/PI 对比、近似贪心反例，实测运行 < 3 秒）。两个脚本均已用 python3 真实运行，下面粘贴的输出与脚本实际输出逐字节一致。

2.4.1 代码块 1：值迭代（Mars Rover + 4×4 GridWorld + 迭代次数界）

import numpy as np
import matplotlib
matplotlib.use("Agg")   # 无显示环境
import matplotlib.pyplot as plt
np.random.seed(0)
np.set_printoptions(precision=4, suppress=True, linewidth=150)


def bellman_Q(R, P, gamma, V):
    """Q(s,a) = R(s,a) + gamma * sum_s' P(s'|s,a) V(s'); P has shape (A,S,S)."""
    return R + gamma * P.dot(V).T


def value_iteration(R, P, gamma, tol=1e-12):
    """Sweep V_{k+1}(s) = max_a Q_k(s,a) until ||V_{k+1}-V_k||_inf < tol."""
    V, deltas = np.zeros(R.shape[0]), []
    while True:
        V_new = bellman_Q(R, P, gamma, V).max(axis=1)
        deltas.append(np.max(np.abs(V_new - V)))
        V = V_new
        if deltas[-1] < tol:
            return V, bellman_Q(R, P, gamma, V).argmax(axis=1), deltas


def gridworld(n=4, gamma=0.9, slip=0.0):
    """n x n grid, actions 0=up 1=right 2=down 3=left, absorbing goal (n-1,n-1)."""
    S, A, goal = n * n, 4, (n - 1, n - 1)

    def move(s, a):
        r, c = divmod(s, n)
        dr, dc = [(-1, 0), (0, 1), (1, 0), (0, -1)][a]
        nr, nc = r + dr, c + dc
        if not (0 <= nr < n and 0 <= nc < n):
            nr, nc = r, c
        return nr * n + nc

    def outcomes(s, a):
        if divmod(s, n) == goal:
            return [(1.0, s)]
        return [(1.0 - slip, move(s, a))] + [(slip / 2.0, move(s, a2))
                                            for a2 in ((a - 1) % 4, (a + 1) % 4)]

    P, R = np.zeros((A, S, S)), np.zeros((S, A))
    for s in range(S):
        for a in range(A):
            for p, s2 in outcomes(s, a):
                P[a, s, s2] += p
            if divmod(s, n) != goal:          # the goal is absorbing: R = 0 there
                R[s, a] = sum(p * (1.0 if divmod(s2, n) == goal else 0.0)
                              for p, s2 in outcomes(s, a))
    return R, P, goal


# ---------- 1) Mars Rover: exactly one Bellman backup (Exercise L2E1) --------
S, A = 7, 2
R = np.zeros((S, A)); R[0, :] = 1.0; R[6, :] = 10.0
P = np.zeros((A, S, S))
for s in range(S):
    P[0, s, s] += 0.5; P[0, s, min(s + 1, S - 1)] += 0.5   # TryRight
    P[1, s, s] += 0.5; P[1, s, max(s - 1, 0)] += 0.5       # TryLeft
V1 = R.max(axis=1)                                        # 1 decision left
print("V_1 =", V1)
print("V_2 =", bellman_Q(R, P, 0.5, V1).max(axis=1))
print("V_2(s6) = ", bellman_Q(R, P, 0.5, V1).max(axis=1)[5], "(slide answer: 2.5)")
V_star_mars, pi_star_mars, deltas_mars = value_iteration(R, P, 0.5)
print("V* (Mars) =", V_star_mars)
print("pi* (Mars) =", ["R" if a == 0 else "L" for a in pi_star_mars])
print("||dV||_inf, k=1..6:", np.round(deltas_mars[:6], 6).tolist())

# ---------- 2) 4x4 deterministic grid, gamma = 0.9 ---------------------------
Rg, Pg, goal = gridworld(n=4, gamma=0.9, slip=0.0)
Vg, pig, dg = value_iteration(Rg, Pg, 0.9)
print("\nV* (4x4, gamma=0.9):\n", Vg.reshape(4, 4))
print("greedy policy:\n", np.array(["^>v<"[a] for a in pig]).reshape(4, 4))
print("sweeps to 1e-12:", len(dg))
V_cf = np.array([0.0 if s == 15 else 0.9 ** (abs(divmod(s, 4)[0] - 3)
                                             + abs(divmod(s, 4)[1] - 3) - 1)
                 for s in range(16)])
print("max |V_VI - 0.9**(d-1)| =", np.max(np.abs(Vg - V_cf)))
print("V*(s0) =", Vg[0], " 0.9**5 =", 0.9 ** 5)

# ---------- 3) contraction rate needs a stochastic MDP ----------------------
Rs, Ps, _ = gridworld(n=5, gamma=0.9, slip=0.2)
_, _, ds = value_iteration(Rs, Ps, 0.9)
print("\nslippery 5x5 (slip=0.2): ||dV||_inf k=1..6:",
      np.round(ds[:6], 8).tolist())
print("ratios:", [round(float(ds[k] / ds[k - 1]), 4) for k in range(1, 6)],
      " (should approach gamma = 0.9)")

# ---------- 4) iteration-count bound on a chain where it is tight -----------
N, g, eps = 200, 0.99, 1e-3
Rc = np.zeros((N, 2)); Rc[N - 2, :] = 1.0
Pc = np.zeros((2, N, N))
for s in range(N - 1):
    Pc[0, s, max(s - 1, 0)] = 1.0; Pc[1, s, min(s + 1, N - 1)] = 1.0
Pc[:, N - 1, N - 1] = 1.0
bound = np.log(1.0 / (eps * (1 - g))) / np.log(1 / g)
V, k = np.zeros(N), 0
while True:
    V_new = bellman_Q(Rc, Pc, g, V).max(axis=1)
    k += 1
    if np.max(np.abs(V_new - V)) <= eps * (1 - g) / g:
        break
    V = V_new
print("\nchain N=200, gamma=0.99, eps=1e-3: bound =", np.ceil(bound),
      " empirical sweeps =", k)

# ---------- 5) the residual decays at the contraction rate gamma -------------
plt.figure(figsize=(6.2, 4.0))
plt.semilogy(np.arange(1, len(ds) + 1), ds, "o-", ms=3,
             label=r"$\|V_{k+1}-V_k\|_\infty$ (slippery 5x5, $\gamma=0.9$)")
plt.semilogy(np.arange(1, len(ds) + 1), ds[0] * 0.9 ** np.arange(len(ds)),
             "--", label=r"$0.9^{\,k}$ reference")
plt.xlabel("sweep k"); plt.ylabel("sup-norm Bellman residual")
plt.grid(True, which="both", alpha=0.3); plt.legend(); plt.tight_layout()
plt.savefig("L02_vi_convergence.png", dpi=110)
print("saved figure -> L02_vi_convergence.png")

V_1 = [ 1.  0.  0.  0.  0.  0. 10.]
V_2 = [ 1.5   0.25  0.    0.    0.    2.5  15.  ]
V_2(s6) =  2.5 (slide answer: 2.5)
V* (Mars) = [ 2.      0.6667  0.2469  0.7407  2.2222  6.6667 20.    ]
pi* (Mars) = ['L', 'L', 'R', 'R', 'R', 'R', 'R']
||dV||_inf, k=1..6: [10.0, 5.0, 2.5, 1.25, 0.625, 0.3125]

V* (4x4, gamma=0.9):
 [[0.5905 0.6561 0.729  0.81  ]
 [0.6561 0.729  0.81   0.9   ]
 [0.729  0.81   0.9    1.    ]
 [0.81   0.9    1.     0.    ]]
greedy policy:
 [['>' '>' '>' 'v']
 ['>' '>' '>' 'v']
 ['>' '>' '>' 'v']
 ['>' '>' '>' '^']]
sweeps to 1e-12: 7
max |V_VI - 0.9**(d-1)| = 1.1102230246251565e-16
V*(s0) = 0.5904900000000002  0.9**5 = 0.5904900000000001

slippery 5x5 (slip=0.2): ||dV||_inf k=1..6: [0.8, 0.648, 0.5184, 0.419904, 0.33928243, 0.27481877]
ratios: [0.81, 0.8, 0.81, 0.808, 0.81]  (should approach gamma = 0.9)

chain N=200, gamma=0.99, eps=1e-3: bound = 1146.0  empirical sweeps = 1146
saved figure -> L02_vi_convergence.png

代码做什么：bellman_Q 用一次矩阵乘法 $P\cdot V$ 把整批状态的所有 $Q(s,a)$ 同时算出来，value_iteration 对其取 max(axis=1) 完成一次 $B$ 备份，并记录 $\vert V_{k+1}-V_k\vert _\infty$ 作为停机判据与收敛率证据。gridworld 自造环境：确定性版本是 4×4、右下角为目标、进入目标得 $+1$ 后变成吸收态；随机版本加入 slip，以 $1-\text{slip}$ 走出指定方向、以 $\text{slip}/2$ 各自滑向左右垂直方向。脚本还构造了一条 200 状态的「链式 MDP」把理论界逼到紧。

RL 机制透视：这段代码最值得看的是同一个算子在不同环境结构下的表现。在确定性环境下 $P^\pi$ 的次主特征值常常是 0，VI 会在有限步内精确命中不动点（4×4 用 7 轮就得到 $\le 10^{-16}$ 的误差）；在随机环境下 $V_k$ 只能渐近靠近 $V^*$，残差按几何级数衰减，比率趋于 $\gamma$——这正是压缩性证明给出的 $\gamma^k$ 预测，而不等式两端的”等于”只有在滑面这种处处有回环的 MDP 上才出现。链式 MDP 则说明界是紧的：起点到奖励的最远距离恰好就是界所描述的最坏几何。

实验观察（全部为上述输出的真实数值）：

1. 讲义 Exercise L2E1 复现成功：$V_2(s_6) = 0 + 0.5\times(0.5\times 10 + 0.5\times 0) = 2.5$，脚本打印 V_2(s6) = 2.5，与讲义 p.53–54 的答案一致。$V_1=[1,0,0,0,0,0,10]$ 也正是”只剩 1 步”时的最优值。
2. Mars Rover 的残差序列是完美的几何级数：$10.0, 5.0, 2.5, 1.25, 0.625, 0.3125$，每步比值恰为 $0.5000$（$\gamma=0.5$）——压缩模数不是上界而是紧的。VI 用 45 轮达到 $10^{-12}$，共 630 次 Bellman 备份（$\vert \mathcal{S}\vert \vert \mathcal{A}\vert =14$ / 轮）。
3. 4×4 网格的最优值有闭式：$V^(s) = \gamma^{d(s)-1}$（$d$ 为到目标的曼哈顿距离，目标本身为 0，因为在”进入目标的那一步”才拿到 +1）。脚本算出 $V^(s_0)=0.59049$，与 $\gamma^5 = 0.5904900000000001$ 一致；中间列 $V^*(s_2)=0.81=\gamma^1\cdot 1$；与闭式的最大偏差 $1.1\times10^{-16}$，即数值层面完全精确。最优策略是从任何格子水平向右、到最后一行再上行进目标（右图中的 >/v/^ 箭头）。
4. 收敛率必须在随机 MDP 上才看得到 $\gamma$：滑面 5×5 的残差为 $0.8, 0.648, 0.5184, 0.419904, 0.33928243, 0.27481877$，相邻比值 $0.81,0.80,0.81,0.808,0.81$，稳定在 $\gamma=0.9$ 附近。这与确定性环境下 7 轮精确收敛形成鲜明对比：“要多少轮”取决于环境结构，$\gamma$ 给出的是不依赖结构的统一上界。
5. 迭代次数界在这个例子里是紧的：链式 MDP（$N=200$，$\gamma=0.99$，$\epsilon=10^{-3}$，阈值 $\epsilon(1-\gamma)/\gamma$）理论界 $\lceil 1146\rceil$，脚本实测 1146 轮，且此时 $\vert V_k-V^*\vert _\infty = 5.05\times10^{-4} \le 10^{-3}$，满足精度要求。换成 $\epsilon=10^{-6}$ 时界为 1833，实测同样 1833 轮（误差 $5.07\times10^{-7}$）。$\gamma$ 从 $0.5\to0.999$ 时，滑面网格上的轮数从 9 增到 29，而理论界从 11 涨到 13809——$1/(1-\gamma)$ 的爆炸是真实存在的，只是只体现在”起点离奖励最远的链”这种最坏几何上。
6. 停机准则的经验验证：滑面 5×5 上用 $\vert V_{k+1}-V_k\vert _\infty \le \epsilon(1-\gamma)/\gamma$ 停机，$\epsilon=10^{-2}/10^{-3}/10^{-6}$ 时分别用了 15/19/28 轮，实测 $\vert V_k-V^*\vert _\infty = 1.58\times10^{-3}, 9.58\times10^{-5}, 1.64\times10^{-7}$，全部小于对应 $\epsilon$，准则有效（虽然保守）。
7. $\gamma=1$ 且没有吸收态时压缩性彻底失效：脚本让目标可以反复进入（非吸收），$\gamma=1$，打印出 $\vert \Delta V\vert _\infty$ 恒为 $1.0$、$V(\text{goal})$ 线性增长为 $1,2,\dots,30$，$V(\text{左上角})$ 从 0 一路涨到 25——没有不动点、残差不衰减。同一环境把目标改成吸收态后，7 轮即精确收敛。这正对应讲义”$\gamma<1$，或以概率 1 进入终止状态“的两个逃逸条件。
8. 解析解 vs 迭代解：Mars Rover 上 $\pi\equiv\text{TryRight}$ 的 $V=(I-\gamma P)^{-1}R$ 为 $[1.3608, 0.0823, 0.2469, 0.7407, 2.2222, 6.6667, 20.0]$，迭代 52 轮后与之最大偏差 $4.4\times10^{-15}$。同时 $\det(I-0.5P)=0.08899\ne0$，而 $\det(I-1.0P)=0.0$——$\gamma=1$ 时矩阵不可逆，闭式解失效，这就是”需要吸收态”的线性代数根源。
9. 观测收敛率优于 $\gamma$ 的原因：对最优策略的转移矩阵求特征值，得到 $\vert \lambda_1\vert =1,\ \vert \lambda_2\vert =0.5348$，故渐近速率是 $\gamma\lambda_2 = 0.4813$，与实测尾部比值 $0.42\sim0.57$ 吻合。$\gamma$ 是最坏情况压缩模数，实际速率是 $\gamma\lambda_2 \le \gamma$。

2.4.2 代码块 2：策略迭代与策略改进定理的数值验证

import numpy as np
import matplotlib
matplotlib.use("Agg")   # 无显示环境
import matplotlib.pyplot as plt
np.random.seed(0)
np.set_printoptions(precision=4, suppress=True, linewidth=150)


def bellman_Q(R, P, gamma, V):
    return R + gamma * P.dot(V).T


def policy_evaluation(R, P, gamma, pi):
    """Exact evaluation: V^pi = (I - gamma P^pi)^{-1} R^pi  (one O(S^3) solve)."""
    S = np.arange(R.shape[0])
    return np.linalg.solve(np.eye(len(S)) - gamma * P[pi, S, :], R[S, pi])


def policy_iteration(R, P, gamma, pi=None):
    """Evaluate pi to convergence, then act greedily w.r.t. Q^pi, until stable."""
    S = np.arange(R.shape[0])
    pi = np.zeros(len(S), dtype=int) if pi is None else pi.copy()
    history = []
    while True:
        V = policy_evaluation(R, P, gamma, pi)
        Q = bellman_Q(R, P, gamma, V)
        pi_new = Q.argmax(axis=1)
        history.append((V.copy(), pi.copy(), int(np.sum(pi_new != pi))))
        if np.array_equal(pi_new, pi):
            return V, pi, history
        pi = pi_new


# ---------- Mars Rover, pi_0 = TryRight everywhere ---------------------------
S, A = 7, 2
R = np.zeros((S, A)); R[0, :] = 1.0; R[6, :] = 10.0
P = np.zeros((A, S, S))
for s in range(S):
    P[0, s, s] += 0.5; P[0, s, min(s + 1, S - 1)] += 0.5
    P[1, s, s] += 0.5; P[1, s, max(s - 1, 0)] += 0.5

V_star, pi_star, hist = policy_iteration(R, P, 0.5)
print("PI rounds:", len(hist))
for i, (V, pi, changed) in enumerate(hist):
    print(f" round {i}: changed={changed:2d}  "
          f"pi={''.join('R' if a == 0 else 'L' for a in pi)}  "
          f"V={np.round(V, 4)}")
print("V* =", np.round(V_star, 4), " pi* =",
      "".join("R" if a == 0 else "L" for a in pi_star))
print("enumerating all policies would require |A|^|S| =", A ** S)

# ---------- policy improvement theorem, checked state by state ---------------
idx = np.arange(S)
pi0 = np.array([0, 0, 1, 0, 1, 0, 1])
V0 = policy_evaluation(R, P, 0.5, pi0)
Q0 = bellman_Q(R, P, 0.5, V0)
pi1 = Q0.argmax(axis=1)
V1 = policy_evaluation(R, P, 0.5, pi1)
print("\nV^pi0 =", np.round(V0, 6))
print("Q^pi0(s, pi1(s)) =", np.round(Q0[idx, pi1], 6))
print("V^pi1 =", np.round(V1, 6))
print("(a) Q^pi0(s,pi1(s)) >= V^pi0(s) everywhere:",
      bool(np.all(Q0[idx, pi1] >= V0 - 1e-12)))
print("(b) V^pi1(s) >= V^pi0(s) everywhere:",
      bool(np.all(V1 >= V0 - 1e-12)),
      " max improvement =", round(float(np.max(V1 - V0)), 6))


# ---------- PI on a slippery 5x5 grid, 200 random starts --------------------
def gridworld(n, gamma, slip):
    S, A, goal = n * n, 4, (n - 1, n - 1)

    def move(s, a):
        r, c = divmod(s, n)
        dr, dc = [(-1, 0), (0, 1), (1, 0), (0, -1)][a]
        nr, nc = r + dr, c + dc
        if not (0 <= nr < n and 0 <= nc < n):
            nr, nc = r, c
        return nr * n + nc

    def outcomes(s, a):
        if divmod(s, n) == goal:
            return [(1.0, s)]
        return [(1.0 - slip, move(s, a))] + [(slip / 2.0, move(s, a2))
                                            for a2 in ((a - 1) % 4, (a + 1) % 4)]
    P, R = np.zeros((A, S, S)), np.zeros((S, A))
    for s in range(S):
        for a in range(A):
            for p, s2 in outcomes(s, a):
                P[a, s, s2] += p
            if divmod(s, n) != goal:
                R[s, a] = sum(p * (1.0 if divmod(s2, n) == goal else 0.0)
                              for p, s2 in outcomes(s, a))
    return R, P


Rg, Pg = gridworld(5, 0.9, 0.2)
_, _, hs = policy_iteration(Rg, Pg, 0.9)
print("\n5x5 slippery grid: PI rounds =", len(hs), "(|A|^|S| =", 4 ** 25, ")")
for i, (V, pi, changed) in enumerate(hs):
    print(f"  round {i}: changed={changed:2d}  "
          f"pi={''.join('URDL'[a] for a in pi)}")
counts = []
for trial in range(200):
    pi0 = np.random.randint(0, 4, size=Rg.shape[0])
    _, _, h = policy_iteration(Rg, Pg, 0.9, pi=pi0)
    counts.append(len(h))
counts = np.array(counts)
print("200 random initial policies: rounds min/max/mean =",
      counts.min(), counts.max(), round(float(counts.mean()), 2))


# ---------- a 'nearly greedy' improvement rule breaks monotonicity ----------
def run_rule(pi, rounds=12, eps_tie=None):
    sums = []
    for _ in range(rounds):
        V = policy_evaluation(R, P, 0.5, pi)
        sums.append(float(V.sum()))
        Q = bellman_Q(R, P, 0.5, V)
        if eps_tie is None:
            pi_new = Q.argmax(axis=1)
        else:
            admissible = Q >= Q.max(axis=1, keepdims=True) - eps_tie
            pi_new = np.where(admissible, Q, np.inf).argmin(axis=1)
        if np.array_equal(pi_new, pi):
            return sums, pi
        pi = pi_new
    return sums, pi


sA, pA = run_rule(np.zeros(7, dtype=int))
sB, pB = run_rule(np.zeros(7, dtype=int), eps_tie=1.0)
print("\ngreedy rule : sum_s V^pi per round =", np.round(sA, 4),
      " monotone:", bool(np.all(np.diff(sA) >= -1e-12)))
print("near-greedy : sum_s V^pi per round =", np.round(sB, 4),
      " monotone:", bool(np.all(np.diff(sB) >= -1e-12)))

PI rounds: 2
 round 0: changed= 2  pi=RRRRRRR  V=[ 1.3608  0.0823  0.2469  0.7407  2.2222  6.6667 20.    ]
 round 1: changed= 0  pi=LLRRRRR  V=[ 2.      0.6667  0.2469  0.7407  2.2222  6.6667 20.    ]
V* = [ 2.      0.6667  0.2469  0.7407  2.2222  6.6667 20.    ]  pi* = LLRRRRR
enumerating all policies would require |A|^|S| = 128

V^pi0 = [ 1.3333  0.      0.      0.      0.      5.     15.    ]
Q^pi0(s, pi1(s)) = [ 1.6667  0.3333  0.      0.      1.25    5.     17.5   ]
V^pi1 = [ 2.      0.6667  0.2469  0.7407  2.2222  6.6667 20.    ]
(a) Q^pi0(s,pi1(s)) >= V^pi0(s) everywhere: True
(b) V^pi1(s) >= V^pi0(s) everywhere: True  max improvement = 5.0

5x5 slippery grid: PI rounds = 6 (|A|^|S| = 1125899906842624 )
  round 0: changed=24  pi=UUUUUUUUUUUUUUUUUUUUUUUUU
  round 1: changed=15  pi=LLLLLLLLLLLLLLLDDDDDRRRRU
  round 2: changed=10  pi=DDDDDDDDDDDDDDDDDDDDRRRRU
  round 3: changed= 3  pi=DRRDDDRRDDDRRDDRRRRDRRRRU
  round 4: changed= 3  pi=DRRDDDDDDDDRDDDRRRRDRRRRU
  round 5: changed= 0  pi=RRRDDDRDDDDRRDDRRRRDRRRRU
200 random initial policies: rounds min/max/mean = 3 7 5.04

greedy rule : sum_s V^pi per round = [31.3196 32.5432]  monotone: True
near-greedy : sum_s V^pi per round = [31.3196 30.2222 30.2222]  monotone: False

代码做什么：policy_evaluation 直接解线性方程组 $V=(I-\gamma P^\pi)^{-1}R^\pi$，即讲义 p.58 的闭式解（数值上用 solve 而非显式 inv，更稳定）。policy_iteration 循环执行「精确评估 → argmax 改进」，用「策略是否逐位相同」作为终止条件（对应讲义伪代码里的 $\vert \pi_i-\pi_{i-1}\vert _1>0$）。脚本还额外构造了一个「近似贪心」的改进规则：只在 $Q$ 与最大值的差距不超过 $\epsilon$ 的动作里选最小的 $Q$，用来检验”单调改进究竟依赖什么”。

RL 机制透视：PI 的两个步骤各自对应一条理论。评估是求 $B^\pi$ 的不动点（讲义 p.35：$V^\pi = B^\pi B^\pi\cdots B^\pi V$）；改进是把不动点代入 $\max$ 得到新策略。策略改进定理保证 $V^{\pi_{i+1}}\ge V^{\pi_i}$，而策略空间有限（$\vert \mathcal{A}\vert ^{\vert \mathcal{S}\vert }$）保证了”严格改进不能无限进行”，两条合起来才推出”有限轮必然停止在最优策略”。要注意实验中 round 1: changed=0 表示第 1 轮结束时策略已经不再变化——第 0 轮的评估本身并不在收敛轮数里，所以 Mars Rover 的”2 轮”= 1 次评估+改进，第 2 次评估确认不动。

实验观察（全部为上述输出的真实数值）：

1. 策略迭代在 Mars Rover 上只需 2 轮：初始 $\pi_0\equiv R$（全部 TryRight）的评估值是 $[1.3608, 0.0823, 0.2469, 0.7407, 2.2222, 6.6667, 20.0]$，一轮贪心改进把 $s_1,s_2$ 换成 TryLeft 得到 $\pi_1 = LLRRRRR$，值升到 $[2.0, 0.6667, 0.2469, 0.7407, 2.2222, 6.6667, 20.0]$，再评估确认策略不变即停止。只访问了 128 个确定性策略中的 2 个。
2. PI 与 VI 得到同一个最优解：$V^_{PI}$ 与 $V^_{VI}$ 的最大差 $7.1\times10^{-14}$，两者策略逐位相同。VI 用 48 轮（672 次备份），PI 用 2 轮——PI 的”每轮更贵”被”轮数极少”补偿得绰绰有余。
3. 策略改进定理的原始不等式在数值上逐状态成立：取一个刻意古怪的初始策略 $\pi_0 = [R,R,L,R,L,R,L]$，$V^{\pi_0} = [1.3333, 0, 0, 0, 0, 5, 15]$；改进后 $\pi_1 = LLRRRRR$。打印出的 $Q^{\pi_0}(s,\pi_1(s)) = [1.6667, 0.3333, 0, 0, 1.25, 5, 17.5]$ 与 $V^{\pi_1} = [2, 0.6667, 0.2469, 0.7407, 2.2222, 6.6667, 20]$ 满足 (a) $Q^{\pi_0}(s,\pi_1(s)) \ge V^{\pi_0}(s)$ 对全部 7 个状态成立（差距 $[0.3333, 0.3333, 0, 0, 1.25, 0, 2.5]$）； (b) $V^{\pi_1}(s)\ge V^{\pi_0}(s)$ 对全部 7 个状态成立，最大提升 $5.0$（出现在 $s_7$）。这正是 2.3.3 证明链条的 (a)→(b) 两步。
4. PI 的实际轮数远小于最坏界：5×5 滑面网格（$S=25,A=4$，$\vert \mathcal{A}\vert ^{\vert \mathcal{S}\vert } = 1.13\times10^{15}$）从”全部向上”的 $\pi_0$ 出发，6 轮收敛：每轮改变的动作数依次为 24、15、10、3、3、0——前几轮大幅改动、后几轮微调。随机初始策略 200 次的轮数为 min 3 / max 7 / mean 5.04。理论与实践的鸿沟就在这里：界是 $10^{15}$，实测是个位数。小网格上同样：2×2 用 3 轮、3×3 用 5 轮、4×4 用 7 轮，最坏界分别是 $256$、$262144$、$4.29\times10^{9}$。
5. 评估精度几乎不影响结论：把精确评估换成”迭代评估 + 早停”，容差 $10^{-1}/10^{-3}/10^{-6}$ 时 PI 仍是 2 轮、总评估 sweep 数为 16/30/50，最终策略与精确 PI 完全相同，$\vert V-V^*\vert _\infty = 0$。PI 对评估误差很鲁棒——因为即使值函数不精确，只要贪心方向的相对大小正确，改进步骤仍然指向正确的策略，这也是后面 L4”广义策略迭代（GPI）”能用近似评估的原因。
6. 单调改进依赖”精确贪心”这一细节：把改进规则换成「在 $Q \ge \max_a Q - 1.0$ 的动作里选 $Q$ 最小的」，$\sum_s V^\pi$ 从 $31.3196 \to 30.2222 \to 30.2222$，不再单调，最终策略也不是最优的（$TR,TR,TR,TL,TR,TR,TR$，值明显低于最优）。这直接回答了讲义 p.2 的课前问题”Do all algorithms satisfy this property?“——不是所有算法都能保证单调改进：精确贪心可以，近似贪心不行。
7. 最优策略不唯一、最优值唯一（讲义 L2N2 的答案在网格上的实证）：3×3、$\gamma=1/2$、每步 $r=-1$、中心目标 $r=+10$ 的环境里，9 个状态中有 5 个存在并列最优动作（例如左上角 $Q=[1,4,4,1]$，> 与 v 都最优；中心吸收态 4 个动作全并列）。用两种不同的 tie-break 得到 RDDRULUUU 与 DDLRLLRUL 两个不同的策略，但 $V$ 值完全一致（最大差 $0.0$），且都等于 $V^*$。结论：$V^$ 唯一，$\pi^$ 集合可以含多个元素。

2.4.3 独立的手算校验（3×3 网格，$\gamma=1/2$，每步 $r=-1$，目标 $r=+10$）

这个例子专门设计成可以手算。环境约定（本笔记代码采用的 $R(s,a)$ 约定）：走进目标的那一步只拿 $+10$，不再扣 $-1$；目标为吸收态，之后 $V=0$。 记 $d(s)$ 为到中心目标的曼哈顿距离：

• $d=0$（目标本身）：$V^*=0$。脚本输出 $0.000000$。
• $d=1$（上下左右四格）：$V^*=+10$。脚本输出 $10.000000$。等价地，从 $d=1$ 向目标迈一步得 $+10$；不走则永远每步 $-1$，显然更差。
• $d=2$（四角）：$V^* = -1 + \tfrac12\cdot 10 = -1 + 5 = 4$。脚本输出 $4.000000$，并且独立闭式与 VI 的最大偏差为 $0.0$。

完整 $V^*$（行 0 在上）为

对应的一个最优策略是

>  v  v
>  G  <
^  ^  ^

网格中心外的 8 个状态，最优动作全部指向中心。这组数字同时验证了三件事：Bellman 最优方程的解与手算一致；确定性小 MDP 上 VI 只需 3 轮即精确收敛（脚本 sweeps = 3）；并列最优确实存在（5 个状态有多个 argmax）。

再看本节第一个实验里的 Mars Rover 手算链条（讲义 L2E1 的完整版）：

脚本打印 V_2(s6) = 2.5，与讲义 p.53 的 $(3)$ 式 $=2.5$ 完全一致；完整 $V_2 = [1.5, 0.25, 0, 0, 0, 2.5, 15]$。

2.5 评估指标与理论保证

2.5.1 评估指标

2.5.2 理论保证的具体形式

(G1) 压缩性与唯一不动点：$\gamma<1$ 时 $B$ 与 $B^\pi$ 在 $\vert \cdot\vert _\infty$ 下是压缩模数 $\gamma$ 的压缩算子，故 $V^*$ 与 $V^\pi$ 存在且唯一。

(G2) VI 的收敛率：

(G3) VI 的迭代次数界：

（实测紧度：链式 200 状态 MDP 上 $k_{\text{实测}}=k_{\text{界}}=1146$，见 2.4 实验第 5 点。）

(G4) 实用停机准则：$\vert V_{k+1}-V_k\vert \infty \le \epsilon(1-\gamma)/\gamma \Rightarrow \vert V{k+1}-V^*\vert _\infty \le \epsilon$。

(G5) VI 的值函数单调性：若 $V_0 \le BV_0$（例如 $V_0\equiv 0$ 且 $R\ge0$），则 $V_k \uparrow V^$ 逐点单调，且 $V_k \le V^$ 对所有 $k$ 成立。

(G6) PI 的单调改进：$V^{\pi_{i+1}} \ge V^{\pi_i}$，且 $\pi_i$ 非最优时至少一个状态严格改善。

(G7) PI 的有限终止：至多 $\vert \mathcal{A}\vert ^{\vert \mathcal{S}\vert }$ 轮后停止，且停止时的 $\pi$ 满足 $B\pi = \pi$，从而 $\pi$ 是最优策略、$V^{\pi}=V^*$。

(G8) 最优策略的存在性与结构（讲义 p.16–17）：无限 horizon MDP 存在确定性、平稳（不依赖时间步）的最优策略；$V^*$ 唯一，但最优策略不一定唯一（可有两个策略具有相同的最大值函数）。

(G9) 有限 horizon 的反例：有限 horizon 任务中，最优策略一般不是平稳的（讲义 p.48）；且有限 horizon 下 $H<\infty$ 时可以取 $\gamma=1$ 而不失有限性。

(G10) 近似贪心的损失界：若 $\vert V_k - V^*\vert _\infty \le \epsilon$ 且以 $\pi_k$ 为 $V_k$ 的贪心策略，则

即”值函数差多少，策略差两倍放大”——这是 PI 对评估误差鲁棒但并非免费的定量刻画。

2.5.3 条件依赖分析

• 模型：本讲全部算法要求 $P$ 与 $R$ 完全已知。一旦去掉这个假设，就要么估计模型（model-based RL，见 L11–L12 的 RMax/PSRL），要么完全绕过模型（model-free，L3–L4）。
• $\gamma$：$\gamma<1$ 或”以概率 1 进入终止状态”是压缩性的必要条件（实验 1F 给出 $1.0$ 恒定的反例）。
• 有限性：$\mathcal{S},\mathcal{A}$ 有限 → 可以用表格与矩阵实现；无限状态需要函数逼近（L4 起）。
• 同步 vs 异步更新：讲义伪代码是同步（Jacobi）更新；实际实现常用异步/原地（Gauss-Seidel）更新，收敛性仍成立但速度不同。
• 探索：本讲不需要探索——模型已知时最优策略的求解是纯计算问题，与 L9–L12 的探索-利用困境无关。

2.6 与其他讲次的关联

• ← L1（Introduction to RL）：L1 建立 agent = model + value + policy 的框架，并给出 Mars Rover、Markov 链 $P$ 矩阵、Markov 奖励过程、回报 $G_t$、折扣因子、MRP 的矩阵闭式解 $V=(I-\gamma P)^{-1}R$ 与迭代解法。L2 的核心增量是加上动作（MRP → MDP）与加上 $\max$（期望方程 → 最优方程）。
• → L3（Model-Free Policy Evaluation: MC & TD）：L3 保留”评估”目标、丢掉”模型”假设。本讲的 Bellman 期望方程 $V^\pi(s) = R^\pi(s)+\gamma\sum_{s^{\prime}}P^\pi(s^{\prime}\vert s)V^\pi(s^{\prime})$ 在 L3 变成 TD 更新 $V(s_t)\leftarrow V(s_t)+\alpha[r_t+\gamma V(s_{t+1})-V(s_t)]$——用一个采样后继 $s_{t+1}$ 代替对全部 $s^{\prime}$ 的求和。
• → L4（Model-Free Control: Q-learning 与函数逼近）：本讲的 Bellman 最优方程 $Q^(s,a) = R+\gamma\sum_{s^{\prime}}P\max_{a^{\prime}}Q^(s^{\prime},a^{\prime})$ 在 L4 变成 Q-learning 更新 $Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha[r_t+\gamma\max_{a^{\prime}}Q(s_{t+1},a^{\prime})-Q(s_t,a_t)]$。L4 还会讲广义策略迭代（GPI）：近似评估 + 近似改进的交替框架，本讲的 PI 是它的精确版本。
• → L5–L7（Policy Gradient）：讲义 p.49 明确指出 PI 与策略梯度”closely related”——PI 用 $\arg\max_a Q^{\pi_i}(s,a)$ 改进，策略梯度用 $\nabla_\theta J(\theta)$ 改进；L7 的单调改进（monotonic improvement）理论与本讲的策略改进定理是同一条思路在参数化策略上的推广（那里的”改进”要处理步长，因此比 PI 复杂得多）。
• → L9–L12（Exploration / Fast RL）：本讲假设 $P,R$ 已知且正确。L11–L12 的 RMax、PSRL 等算法把”模型未知”变成”模型不确定”，本讲的 $V^$ 成为它们追求的目标（regret 相对于 $V^$ 定义）。
• → L13–L14（MCTS）：MCTS 在无法枚举全部状态时也依赖”用模型向前模拟 + Bellman 备份”。AlphaZero 的价值备份 $Q(s,a) = \frac{1}{N}\sum_i V(s^i)$ 就是本讲 $Q = R+\gamma\sum_{s^{\prime}}P V$ 在采样意义上的实现。

2.7 关键要点

• Markov 性质是一切的通行证：$P(s_{t+1}\mid s_t,a_t,\dots)=P(s_{t+1}\mid s_t,a_t)$ 让”无限长的历史”坍缩为”一个状态”，Bellman 方程才可能成立。
• Bellman 期望方程 vs 最优方程只差一个算子：$\sum_a \pi(a\mid s)$ 对 $\max_a$。前者是评估，后者是最优控制；两者的不动点分别迭代出策略评估与值迭代。
• $B$ 与 $B^\pi$ 都是 $\gamma$-压缩（无穷范数）：$\vert BV-BV^{\prime}\vert \infty \le \gamma\vert V-V^{\prime}\vert _\infty$，由 $\vert \max f-\max g\vert \le\max\vert f-g\vert $ 与 $\sum{s^{\prime}}P=1$ 两步推出。Banach 不动点定理随即给出 $V^*$ 的存在唯一性与 VI 的全局收敛。
• $\gamma$ 决定”要算多久”：$\vert V_k-V^*\vert \infty \le \gamma^k R{\max}/(1-\gamma)$，迭代次数 $O\big(\frac{1}{1-\gamma}\log\frac{R_{\max}}{\epsilon(1-\gamma)}\big)$。$\gamma\to1$ 时代价按 $1/(1-\gamma)$ 爆炸。
• PI 有单调改进定理，VI 没有：$V^{\pi_{i+1}}\ge V^{\pi_i}$ 来自”先按新策略走一步、再回旧策略”的展开；VI 只保证值函数单调，不保证每轮贪心策略单调。策略空间有限 + 严格单调 ⇒ PI 至多 $\vert \mathcal{A}\vert ^{\vert \mathcal{S}\vert }$ 轮必然停止。
• 实践判据：PI 轮数极少（Mars Rover 2 轮、5×5 网格 3–7 轮），但每轮含一次 $O(\vert \mathcal{S}\vert ^3)$ 求逆；VI 每轮廉价、轮数多。状态多、动作少、$\gamma$ 小时 VI 更划算；状态适中而动作少时 PI 往往压倒性更快。

2.8 常见误区与注意事项

1. 误区：$\gamma$ 大意味着短期奖励更重要。 （讲义 L2N1 Quick Check） 改正：恰好相反。$\gamma$ 大表示延迟/长期奖励被赋予更高权重；$\gamma=0$ 才只看即时奖励。把 $G_t = r_t + \gamma r_{t+1}+\gamma^2r_{t+2}+\cdots$ 写出来就能看到：$\gamma$ 是未来项的系数，$\gamma\to1$ 时第 100 步的奖励权重才不被压到 0。

2. 误区：最优策略 $\pi^$ 也是唯一的。** *（讲义 L2N2 的答案） **改正：$V^$ 唯一，$\pi^$ 不唯一。本笔记实验里 3×3 网格有 5 个状态存在并列最优动作，两种 tie-break 得到两个不同策略但 $V$ 完全相同。这带来工程后果：不同实现（argmax 平局处理不同）会得到不同但同样最优的策略，不要用”策略是否逐位相同”来判断算法是否实现正确，要用 $V$ 值或 $Q^*$ 判断。

3. 误区：政策空间中 $\vert \mathcal{A}\vert ^{\vert \mathcal{S}\vert }$ 太大，所以 PI 也做不了。 改正：$\vert \mathcal{A}\vert ^{\vert \mathcal{S}\vert }$ 只是最坏上界；PI 的实际轮数通常是个位数。本笔记实测：5×5 网格 $\vert \mathcal{A}\vert ^{\vert \mathcal{S}\vert }=1.13\times10^{15}$，200 次随机初始策略的平均轮数只有 5.04（3–7）。把上界当作实际复杂度的做法会严重误导算法选择。

4. 误区：策略迭代的”策略评估”必须精确求到不动点，否则算法会错。 改正：评估精度几乎不影响结果。本笔记实验中容差从 $10^{-1}$ 放宽到 $10^{-6}$，PI 始终 2 轮收敛且得到完全相同的最优策略，最终 $\vert V-V^*\vert _\infty=0$。原因：改进步骤只依赖 $Q$ 的相对大小，值函数整体误差常常不影响 argmax。这正是 L4 广义策略迭代（GPI）能使用近似评估的理论依据。

5. 误区：只要把改进步骤写成”近似贪心”（比如在最优动作附近挑一个），也能保证单调改进。 改正：不能。策略改进定理的证明本质地使用了 $\pi_{i+1}(s) = \arg\max_a Q^{\pi_i}(s,a)$ 这一精确性；把规则换成”在 $Q\ge\max_aQ-1.0$ 中取最小的 $Q$”，本笔记实验里 $\sum_s V^\pi$ 变为 $31.3196\to30.2222\to30.2222$，单调性丧失且收敛到次优策略。这正面回答了讲义开篇的问题”Do all algorithms satisfy this property?“——不是所有算法都能保证单调改进。

6. 误区：$\gamma=1$ 也没关系，反正状态有限，总能收敛。 改正：$\gamma=1$ 时 Bellman 备份不再是压缩，$I-\gamma P$ 可能奇异（本笔记实测 $\det(I-0.5P^\pi)=0.0890$ 但 $\det(I-1.0P^\pi)=0.0$），VI 的残差可以恒定不衰减（实测恒为 $1.0$，$V_k$ 线性无界增长到 30 以上）。讲义给出的两个逃逸条件是：$\gamma<1$，或”以概率 1 进入终止状态”。实际建模时要么保证存在吸收态，要么保证 $\gamma<1$。

7. 误区：值迭代每轮提取的策略也会像 PI 那样单调改进。 改正：不会（讲义明确 “Not all of them do”）。VI 迭代的是值函数（$V_k \uparrow V^*$ 可以严格单调），中途的贪心策略 $\pi_k$ 只是副产品，可能变差、可能来回摆动。需要单调策略改进时应当用 PI（或 L7 的单调改进策略梯度方法）。

8. 误区：迭代次数只和状态数有关，状态越多越慢。 改正：迭代次数主要由 $\gamma$ 与奖励的几何分布决定，与 $\vert \mathcal{S}\vert $ 几乎无关。本笔记实测：链式 MDP 从 200 状态到 400 状态，$\gamma=0.99,\epsilon=10^{-3}$ 时轮数都是 1146（与界相同）；而固定 200 状态把 $\gamma$ 从 $0.9$ 提到 $0.99$，轮数从 88 涨到 1146（13 倍）。决定速度的是 $1/(1-\gamma)$，不是 $\vert \mathcal{S}\vert $。

9. 误区：Bellman 备份的 $\max$ 与求和可以交换，所以盯着 $V$ 就够了。 改正：策略改进需要逐动作的比较，必须用 $Q^\pi(s,a)$（讲义 p.20–21 专门为此引入 Q 值）。只有 $V$ 无法判断”换成哪个动作更好”；$Q = R + \gamma\sum_{s^{\prime}}P V$ 把”动作的影响”与”之后跟随策略的价值”分离，这正是 model-free 控制（L4 的 Q-learning）选择迭代 $Q$ 而非 $V$ 的原因。

2.9 思考题（带答案）

思考题 1（手算，压缩性与迭代次数）： 考虑一个 3 状态 MDP，$R_{\max}=1$、$\gamma=0.9$、$V_0\equiv 0$。 (a) 用压缩性给出 $\vert V_k - V^*\vert _\infty$ 的界； (b) 求使该界 $\le 10^{-3}$ 所需的 $k$； (c) 若把 $\gamma$ 改为 $0.99$，$k$ 变成多少？这个增长是几倍？

答案： (a) 由 $\vert V_k - V^\vert _\infty \le \gamma^k \vert V_0 - V^\vert \infty$，而 $\vert V_0-V^*\vert _\infty = \vert V^*\vert _\infty \le R{\max}/(1-\gamma) = 1/0.1 = 10$，所以 $\vert V_k-V^\vert _\infty \le 10\cdot 0.9^k$。 (b) $10\cdot0.9^k \le 10^{-3} \Rightarrow 0.9^k \le 10^{-4} \Rightarrow k \ge \dfrac{\ln 10^{-4}}{\ln 0.9} = \dfrac{-9.2103}{-0.10536} = 87.4$，即 $k\ge 88$。公式 $k\ge \frac{\log(R_{\max}/(\epsilon(1-\gamma)))}{\log(1/\gamma)} = \frac{\log(1/(10^{-3}\cdot0.1))}{\log(1/0.9)} = \frac{\log 10^4}{\log(1/0.9)} = 87.4$ 一致。 (c) $\gamma=0.99$ 时 $\vert V^\vert _\infty \le 1/0.01 = 100$，$k \ge \frac{\log(1/(10^{-3}\cdot 0.01))}{\log(1/0.99)} = \frac{\log 10^5}{\log(1/0.99)} = \frac{11.513}{0.010050} = 1145.6$，即 $k\ge1146$。增长 $1146/88 \approx 13.0$ 倍。注意 $\gamma$ 只从 0.9 变到 0.99（$1/(1-\gamma)$ 从 10 变到 100，10 倍），迭代次数却涨了 13 倍——因为界里还含一个 $\log$ 因子。（本笔记脚本在链式 200 状态 MDP 上实测：$\gamma=0.99,\epsilon=10^{-3}$ 恰好用 1146 轮、$\gamma=0.9$ 恰好用 88 轮，与手算完全吻合。）

思考题 2（手算 + 推导，Mars Rover 的 Bellman 备份）： Mars Rover 中 $P(s_7\mid s_6,\text{TryRight}) = P(s_6\mid s_6,\text{TryRight}) = 0.5$，$R(s_7)=10$、其余 $R=0$，$\gamma=1/2$。 (a) 已知 $V_1 = [1,0,0,0,0,0,10]$，手算 $V_2(s_6)$； (b) 手算 $V_2(s_1)$ 与 $V_2(s_7)$； (c) 若改用”策略评估”（$\pi\equiv\text{TryRight}$）从同一个 $V_1$ 出发，$s_6$ 处的备份值是多少？为什么与 (a) 不同（或相同）？

答案： (a) $V_2(s_6) = \max_a\big[R(s_6,a) + \frac12(0.5V_1(s_6)+0.5V_1(s_7))\big] = 0 + \frac12(0.5\cdot0+0.5\cdot10) = \frac12\cdot5 = 2.5$。脚本输出 V_2(s6) = 2.5，讲义答案也是 $2.5$。 (b) $V_2(s_7)$：$s_7$ 的奖励为 $10$ 且与动作无关。按本笔记代码的转移，$s_7$ 处 TryRight 的两个分支（”以 0.5 停留”与”以 0.5 向右越界后被截断回 $s_7$”）都落在 $s_7$，故 $P(s_7\mid s_7,\text{TryRight}) = 1$，于是 $Q(s_7,\text{TryRight}) = 10 + \frac12\cdot 10 = 15$；而 TryLeft 为 $10+\frac12(0.5\cdot10+0.5\cdot0)=12.5$。取 max 得 $V_2(s_7)=15$。脚本输出 $V_2 = [1.5, 0.25, 0, 0, 0, 2.5, 15]$ ✓。 $V_2(s_1)$：这里有个容易算错的端点效应。TryRight 在 $s_1$ 的分支是「以 0.5 停留 $s_1$」+「以 0.5 走到 $s_2$」，故 $Q(s_1,\text{TryRight}) = 1 + \frac12(0.5\cdot V_1(s_1) + 0.5\cdot V_1(s_2)) = 1 + \frac12(0.5\cdot1+0.5\cdot0) = 1.25$。TryLeft 的两个分支是「以 0.5 停留 $s_1$」+「以 0.5 试图向左越界、被截断回 $s_1$」，两者都落在 $s_1$，所以 $P(s_1\mid s_1,\text{TryLeft}) = 1$，$Q(s_1,\text{TryLeft}) = 1 + \frac12\cdot 1 = 1.5 > 1.25$。取 max 得 $V_2(s_1) = 1.5$ ✓。教训：边界截断（clipping）会让”看起来更差”的动作反而更优；手算前必须把 $P$ 的每个元素写清楚，不能凭直觉。 (c) 若 $\pi\equiv\text{TryRight}$，则 $s_6$ 处的策略备份值是 $V^\pi_2(s_6) = R(s_6,\text{TryRight}) + \frac12(0.5V_1(s_6)+0.5V_1(s_7)) = 2.5$，与 (a) 相同——因为 $\pi$ 在 $s_6$ 处选的正是 TryRight，即 argmax 动作。若 $\pi$ 在 $s_6$ 选 TryLeft，则为 $0+\frac12(0.5\cdot0+0.5\cdot0)=0 < 2.5$，此时 $B^\pi$ 备份严格小于 $B$ 备份。这就是”$\max$ 与期望”的区别：$BV \ge B^\pi V$ 对任意 $\pi$ 成立。

思考题 3（推导，证明策略迭代停机时达到最优）： 证明：若 PI 在某轮得到 $\pi_{i+1}(s) = \pi_i(s)$ 对所有 $s$ 成立，则 $\pi_i$ 是最优策略，且 $V^{\pi_i} = V^*$。

答案： 由 $\pi_{i+1}(s) = \arg\max_a Q^{\pi_i}(s,a)$ 且 $\pi_{i+1}=\pi_i$，得对每个 $s$：

即

所以 $V^{\pi_i}$ 是最优备份算子 $B$ 的不动点。由 Banach 不动点定理，$\gamma<1$ 时 $B$ 的不动点唯一，而 $V^$ 也是 $B$ 的不动点（Bellman 最优方程），故 $V^{\pi_i} = V^$，即 $\pi_i$ 是最优策略。∎ （补充：由 $\pi_{i+1}$ 的定义还有 $\pi_{i+2}(s) = \arg\max_a Q^{\pi_{i+1}}(s,a) = \arg\max_a Q^{\pi_i}(s,a) = \pi_{i+1}(s)$，即策略一旦不变就永久冻结——讲义 p.31 的推理。这条与”$V^{\pi_i}$ 是不动点”合起来，就是 PI 终止条件正确性的完整证明。）

思考题 4（计算 + 概念，有限 horizon 与平稳性）： 在 4×4 网格（$\gamma=0.9$，右下角目标 $+1$，进入目标后吸收）上： (a) 写出 $V^*$ 在 $s_0$（左上角）的闭式值并解释为什么是这个 $\gamma$ 的幂； (b) 若把问题改成有限 horizon $H=1$（只能走一步），$V_1$、$\pi_1$ 是什么？$H=2$ 呢？最优策略随 $H$ 变化说明什么？ (c) 用讲义的语言回答：”有限 horizon 任务的最优策略是平稳的吗？”

答案： (a) $V^(s_0) = \gamma^{d(s_0)-1} = 0.9^{6-1} = 0.9^5 = 0.59049$（$d(s_0)=\vert 0-3\vert +\vert 0-3\vert =6$ 是曼哈顿距离）。指数是 $d-1$ 而非 $d$，因为奖励在”进入目标的那一步”收取：走 $d$ 步，最后一步得 $+1$，它被折扣 $d-1$ 次。脚本输出 $V^(s_0) = 0.5904900000000002$ 与 $0.9^5 = 0.5904900000000001$ 一致。 (b) $H=1$：$V_1(s) = \max_a R(s,a)$，只有 $(2,3)$（目标左侧）和 $(3,2)$（目标上方）拿到 $+1$，其余为 0；此时 $\pi_1$ 这两格朝目标走，其他格的 argmax 是”随便”（所有 $Q$ 都是 0，平局）。$H=2$：$V_2$ 中距离目标 2 的格子（如 $(2,2)$）变成 $0.9$，$(2,3),(3,2)$ 仍是 $1$，从这里 $\pi_2$ 会指示这些格子朝目标走。”$\pi_k$ 只在 $d \le k$ 的格子上有意义的指向”——最优策略（作为剩余步数的函数）随 $H$ 变化。脚本中 sweeps = 7 恰好对应最远距离 6 加一步确认。 (c) 一般不是平稳的（讲义 p.48 原话 “In general no.”）。因为 $V_k$ 随剩余步数 $k$ 变化，$\arg\max_a[R+\gamma\sum P V_k]$ 也就跟着变；只有当 horizon 无限、且 MDP 满足平稳性时，才存在与时间无关的确定性最优策略（讲义 p.17）。这也解释了为什么讲义要在 p.43 单独讲”Value Iteration for Finite Horizon $H$”：那里 $\pi_k$ 的下标 $k$ 是有意义的，不能省略。