第 1 章：马尔可夫决策过程 (MDP) 基础¶
强化学习的数学语言 —— 理解 MDP 五元组和贝尔曼方程
⏱️ TL;DR（30 秒速览）¶
核心问题：如何在不确定的环境中做出最优决策？
MDP 五元组： - S（状态）：当前情况是什么 - A（动作）：能做什么选择 - P（转移概率）：动作如何影响未来 - R（奖励）：什么是"好"的 - γ（折扣因子）：未来有多重要
贝尔曼方程（一句话）：
现在的价值 = 即时奖励 + 未来的价值（打个折）
核心公式： $\(V(s) = \mathbb{E}[R + \gamma V(s')]\)$
关键洞察： - 当前选择影响未来，未来影响回报 - 用价值函数量化"长期好坏" - 用贝尔曼方程递归求解
学完这章你能： - ✅ 用 MDP 建模实际问题 - ✅ 理解贝尔曼方程的直观含义 - ✅ 计算价值函数 - ✅ 理解策略迭代 vs 价值迭代
代码实现：策略迭代、价值迭代、MDP 核心类
常见误区： - ❌ MDP 需要完整模型 → ✅ 这是动态规划的假设，不是 MDP 本身 - ❌ 折扣因子可有可无 → ✅ 保证收敛 + 模拟不确定性 - ❌ 价值函数是即时奖励 → ✅ 是长期累积奖励的期望
🎯 本章要解决什么问题¶
如果你翻开任何一本强化学习教材，第一章几乎都会讲马尔可夫决策过程（Markov Decision Process，简称 MDP）。这不是巧合。MDP 是强化学习的数学语言——就像微积分是物理学的语言、集合论是数学的语言一样。不理解 MDP，就无法真正理解强化学习。
但问题是，大多数 MDP 教程都过于抽象。一上来就是状态空间、转移概率、价值函数，公式一堆，却不知道这些东西到底有什么用。学完还是不知道 MDP 能解决什么实际问题。
本章的目标是让你真正理解 MDP 的直观含义，而不仅仅是记住公式。我们会从生活场景出发，逐步引出 MDP 的每个概念，让你明白：
- 为什么需要 MDP 这个框架？
- MDP 的五个组成部分各自代表什么？
- 贝尔曼方程为什么长这个样子？
- 如何用 MDP 建模实际问题？
为什么需要 MDP？¶
想象你要教一个机器人学会走路。你怎么告诉它"走得好"还是"走得不好"？
方法一：直接告诉它每个动作的好坏 - "抬左腿"：好 - "抬右腿"：好 - "同时抬两条腿"：不好（会摔倒）
这种方法叫监督学习。它的问题是：你需要事先知道每个动作的好坏。但很多时候，我们并不知道什么动作是好的——这正是我们想让机器人学习的！
方法二：告诉它每个状态的期望回报 - "站得稳"：长期来看能走很远 - "摔倒了"：长期来看走不远
这种方法叫强化学习。核心思想是：每个状态都有一个"长期价值"，机器人要学会选择能到达高价值状态的动作。
MDP 就是用来形式化这个"长期价值"的数学框架。
MDP 的核心洞察¶
MDP 的核心洞察可以概括为一句话：
当前的选择会影响未来的状态，未来的状态又会影响未来的回报。
这个洞察看似简单，但它引出了强化学习的所有核心概念： - 因为当前选择影响未来，所以我们需要策略（如何选择动作） - 因为未来状态不确定，所以我们需要转移概率 - 因为要考虑长期回报，所以我们需要折扣因子 - 因为要评估状态好坏，所以我们需要价值函数 - 因为要优化长期回报，所以我们需要贝尔曼方程
学完本章后，你将能够： - 用 MDP 五元组建模简单的决策问题 - 理解贝尔曼方程的直观含义和数学推导 - 计算给定策略的价值函数 - 理解策略迭代和价值迭代的原理 - 为后续学习动态规划、蒙特卡洛、时序差分打下坚实基础
📖 场景描述：从午餐选择到人生决策¶
场景一：每天中午吃什么？¶
这是一个你每天都要面对的"决策问题"。让我们用 MDP 的视角来分析它。
状态：影响你午餐决策的因素 - 天气（晴天/雨天/寒冷） - 预算（充足/紧张） - 上次吃了什么（食堂/外卖/带饭）
动作：你可以选择的午餐方案 - 去食堂（便宜但可能不好吃） - 点外卖（方便但贵） - 自己带饭（健康但要准备）
状态转移：你的选择如何影响明天的状态 - 如果今天吃食堂，明天可能还想吃食堂（审美疲劳） - 如果今天花了很多钱，明天预算可能变紧张 - 天气是外部环境，不受你控制
奖励：每个选择的即时满足感 - 食堂：满意度 6 分，成本 -2 分，净奖励 4 分 - 外卖：满意度 8 分，成本 -5 分，净奖励 3 分 - 带饭：满意度 7 分，成本 -1 分，净奖励 6 分
折扣因子：你有多重视未来 - γ = 0.9：比较重视未来（健康饮食） - γ = 0.5：只看眼前（及时行乐）
问题：给定这些因素，你应该如何选择午餐，才能让长期的总满意度最高？
这就是一个 MDP 问题！
场景二：下班回家走哪条路？¶
状态：当前位置（家/公司/地铁站/公交站） 动作：选择下一站去哪里 转移：交通状况（可能堵车、可能准点） 奖励：每步 -1 分（想早点到家） 折扣：γ = 1（因为肯定能到家，不需要折扣）
问题：哪条路的期望通勤时间最短？
场景三：投资还是消费？¶
状态：当前资产（10 万/50 万/100 万/...） 动作：投资多少、消费多少 转移：投资回报（可能赚、可能赔） 奖励：消费带来的效用 折扣：γ = 0.95（未来的快乐打点折）
问题：如何分配投资和消费，让一生的总效用最大？
🧠 核心概念详解¶
概念一：马尔可夫性质（Markov Property）¶
直觉理解：
马尔可夫性质是 MDP 的基础假设。它的含义是：未来只取决于现在，与过去无关。
用午餐选择举例： - 如果你今天吃了食堂，明天想吃什么，主要取决于今天的状态（天气、预算、刚吃过什么） - 至于你上周吃了什么、上个月吃了什么，对明天的决策没有额外影响
换句话说，当前状态包含了做决策所需的全部信息。
形式化定义：
马尔可夫性质可以写成：
左边是"考虑所有历史信息"的条件概率，右边是"只考虑当前状态和动作"的条件概率。马尔可夫性质说这两个概率相等。
为什么这样设计：
马尔可夫性质是一个简化假设。在现实中，未来可能确实与过去有关（比如你连续吃一周食堂后会特别想吃外卖）。但如果把整个历史都作为状态，状态空间会无限大，问题无法求解。
马尔可夫性质的妙处在于：我们可以通过扩展状态定义来满足它。比如在午餐问题中，把"上次吃了什么"纳入状态，就捕捉到了历史信息。
违反马尔可夫性质的后果：
如果问题本身不满足马尔可夫性质，而你强行用 MDP 建模，会发生什么？
答案是：学习算法可能无法收敛，或者收敛到次优解。因为算法假设当前状态包含全部信息，但实际不是，导致价值函数估计错误。
概念二：MDP 五元组¶
直觉理解：
MDP 用五个元素完整描述一个决策问题：
- S（状态空间）：所有可能的状态
- A（动作空间）：所有可能的动作
- P（转移概率）：动作如何影响状态
- R（奖励函数）：什么是"好"的
- γ（折扣因子）：未来有多重要
这五个元素缺一不可。少任何一个，问题都无法完整定义。
形式化定义：
其中： - \(S\)：状态集合，\(|S| = n_S\) - \(A\)：动作集合，\(|A| = n_A\) - \(P(s'|s, a)\)：在状态 \(s\) 采取动作 \(a\)，转移到 \(s'\) 的概率 - \(R(s, a, s')\)：在状态 \(s\) 采取动作 \(a\)，转移到 \(s'\) 获得的奖励 - \(\gamma \in (0, 1]\)：折扣因子
为什么这样设计：
每个元素都有其必要性：
状态 S：必须定义"当前情况是什么"。没有状态，就无法做决策。
动作 A：必须定义"能做什么"。没有动作，就没有决策。
转移概率 P：必须定义"动作如何影响世界"。没有转移，就无法预测未来。
奖励 R：必须定义"什么是好的"。没有奖励，就没有优化目标。
折扣因子 γ：必须定义"未来有多重要"。没有折扣，无限 horizon 问题的总回报可能发散。
概念三：价值函数（Value Function）¶
直觉理解：
价值函数回答了一个核心问题：某个状态（或状态 - 动作对）长期来看有多好？
注意关键词"长期"。价值函数不是看即时奖励，而是看从该状态开始，未来所有奖励的总和（折扣后）。
继续用午餐举例： - 状态"预算紧张"的即时奖励可能是负的（不能吃好吃的） - 但如果这个状态促使你开始带饭，长期来看可能更健康、更省钱 - 所以"预算紧张"的价值可能比看起来高
形式化定义：
状态价值函数 \(V_\pi(s)\)：从状态 \(s\) 出发，遵循策略 \(\pi\)，期望获得的累积折扣奖励。
动作价值函数 \(Q_\pi(s, a)\)：从状态 \(s\) 采取动作 \(a\)，然后遵循策略 \(\pi\)，期望获得的累积折扣奖励。
为什么这样设计：
价值函数的设计有几个关键考量：
1. 期望值：因为环境是随机的（转移概率），同样的动作可能导致不同结果。所以我们用期望值，而不是确定值。
2. 折扣因子：有两个原因 - 数学上：保证无限级数收敛（\(\sum \gamma^t < \infty\)） - 实际上：未来的奖励确实不如现在的确定（可能中途"死亡"）
3. 策略依赖：价值函数依赖于策略 \(\pi\)。同一个状态，在不同策略下价值不同。
概念四：贝尔曼方程¶
直觉理解：
贝尔曼方程是 MDP 的核心方程。它描述了一个深刻的洞察：
一个状态的价值，等于即时奖励加上后续状态的（折扣）价值。
用大白话说："现在的价值 = 现在得到的 + 未来的价值（打个折）"
这个方程看起来简单，但它是所有强化学习算法的基础。
形式化定义：
贝尔曼期望方程（给定策略 \(\pi\)）：
贝尔曼最优化方程（最优策略 \(\pi^*\)）：
为什么这样设计：
贝尔曼方程的设计基于递归思想。
考虑一个状态 \(s\) 的价值。从 \(s\) 出发，你会： 1. 选择一个动作 \(a\) 2. 获得即时奖励 \(R(s, a, s')\) 3. 转移到新状态 \(s'\) 4. 从 \(s'\) 继续，获得未来价值 \(V(s')\)
所以 \(s\) 的价值自然就是：即时奖励 + 未来价值（折扣后）。
这个递归关系就是贝尔曼方程。它的威力在于：把无限 horizon 的问题，转化为了有限方程。
概念五：策略与最优性¶
直觉理解：
策略 \(\pi\) 就是"决策规则"——在每种状态下，选择什么动作。
策略可以是： - 确定性：在状态 \(s\) 总是选择动作 \(a\) - 随机性：在状态 \(s\) 以概率 \(\pi(a|s)\) 选择动作 \(a\)
最优策略 \(\pi^*\) 是"最好的决策规则"——在所有策略中，能带来最高期望回报的。
形式化定义：
策略 \(\pi\) 是一个从状态到动作概率分布的映射：
最优策略 \(\pi^*\) 满足：
为什么这样设计：
策略的随机性设计有几个原因：
1. 探索：在强化学习中，智能体需要探索未知动作。随机策略天然支持探索。
2. 博弈：在对抗环境中（如石头剪刀布），确定性策略会被对手利用。随机策略是纳什均衡。
3. 鲁棒性：随机策略对环境变化更鲁棒。
（第一部分完成，待续...）
📐 公式推导¶
推导一：贝尔曼期望方程¶
问题设定：
我们想要计算给定策略 \(\pi\) 下，状态 \(s\) 的价值 \(V_\pi(s)\)。
定义回顾：
状态价值的定义是：
推导过程：
第一步，展开期望：
第二步，分离第一项：
第三步，注意到括号内就是从 \(S_1\) 开始的价值（折扣后）：
第四步，展开期望。期望是对动作和下一状态的联合分布求：
这就是贝尔曼期望方程。
关键理解：
推导的关键在于分离第一项。这个技巧把无限级数转化为了递归方程。
从直观上理解： - \(R_1\) 是即时奖励 - \(\gamma V_\pi(S_1)\) 是未来的（折扣）价值 - 期望是因为动作和下一状态都是随机的
矩阵形式：
对于有限状态 MDP，贝尔曼方程可以写成矩阵形式：
其中： - \(\mathbf{V}_\pi\) 是价值向量（\(n_S\) 维） - \(\mathbf{R}_\pi\) 是期望奖励向量 - \(\mathbf{P}_\pi\) 是策略 \(\pi\) 下的转移矩阵
这个方程有解析解：
但求逆的复杂度是 \(O(n_S^3)\)，对于大状态空间不实用。所以实践中用迭代法。
推导二：贝尔曼最优化方程¶
问题设定：
我们想要找到最优策略 \(\pi^*\)，使得价值函数最大。
最优价值函数定义：
推导过程：
第一步，从贝尔曼期望方程出发：
第二步，定义动作价值函数：
则：
第三步，对于最优策略，显然应该选择 \(Q\) 值最大的动作：
第四步，代入得：
这就是贝尔曼最优化方程。
关键理解：
最优化方程的核心是max 操作。它表示：最优策略总是选择能带来最大长期价值的动作。
这个方程有两个重要性质：
1. 存在性：对于有限 MDP，最优策略一定存在。
2. 唯一性：最优价值函数 \(V^*\) 是唯一的（但最优策略可能不唯一）。
推导三：策略改进定理¶
问题设定：
我们有一个策略 \(\pi\)，想要找到一个更好的策略 \(\pi'\)。
策略改进定理：
如果对于某个策略 \(\pi'\) 和所有状态 \(s\)：
则：
推导过程：
第一步，写出 \(V_{\pi'}\) 的贝尔曼方程：
第二步，用归纳法。假设对于所有 \(s\)，\(V_{\pi'}(s) \geq V_\pi(s)\)。
第三步，考虑 \(Q\) 函数的关系：
由于 \(V_{\pi'} \geq V_\pi\)，所以 \(Q_{\pi'} \geq Q_\pi\)。
第四步，结合条件 \(Q_\pi(s, \pi'(s)) \geq V_\pi(s)\)，得：
关键理解：
策略改进定理是策略迭代算法的理论基础。
它告诉我们：只要在某个状态下，新策略的动作比旧策略的 \(Q\) 值高，新策略就更好。
推论：贪婪策略改进
给定策略 \(\pi\)，定义贪婪策略：
则 \(\pi' \geq \pi\)。
推导四：策略迭代收敛性¶
问题设定：
策略迭代算法：策略评估 → 策略改进 → 重复。我们想要证明它会收敛到最优策略。
收敛性定理：
对于有限 MDP，策略迭代算法在有限步内收敛到最优策略。
推导思路：
第一步，每次策略改进都严格改进（或保持不变）：
第二步，有限 MDP 的策略数量有限（\(|A|^{|S|}\) 个确定性策略）。
第三步，价值函数有上界（最大可能回报）。
第四步，由 1、2、3，算法必然在有限步内收敛。
第五步，收敛时策略不再改进，满足贝尔曼最优化方程，所以是最优策略。
关键理解：
策略迭代的收敛性证明依赖于有限性。对于无限状态空间，需要额外条件。
💻 算法实现¶
实现一：MDP 核心类¶
"""
表格型 MDP 表示
用表格形式表示马尔可夫决策过程的五元组 (S, A, P, R, γ)
"""
import numpy as np
from typing import Dict, List, Tuple, Optional
class TabularMDP:
"""
表格型 MDP
适用于状态和动作空间有限的 MDP。
状态转移用字典表示：
P[s][a] = [(prob, next_state, reward, done), ...]
Attributes:
nS (int): 状态数量
nA (int): 动作数量
P (dict): 状态转移字典
gamma (float): 折扣因子
"""
def __init__(self, n_states: int, n_actions: int, gamma: float = 0.99):
"""
初始化 MDP
Args:
n_states: 状态空间大小 |S|
n_actions: 动作空间大小 |A|
gamma: 折扣因子 γ ∈ (0, 1]
- 接近 1：重视长期回报
- 接近 0：只看眼前利益
- 推荐：0.9-0.99
"""
self.nS = n_states
self.nA = n_actions
self.gamma = gamma
# 状态转移字典
# P[s][a] = [(prob, next_state, reward, done), ...]
# 表示在状态 s 采取动作 a，以概率 prob 转移到 next_state，获得奖励 reward
self.P = {s: {a: [] for a in range(n_actions)} for s in range(n_states)}
def add_transition(
self,
state: int,
action: int,
prob: float,
next_state: int,
reward: float,
done: bool = False,
):
"""
添加状态转移
Args:
state: 当前状态 s
action: 动作 a
prob: 转移概率 P(s'|s, a)
next_state: 下一状态 s'
reward: 奖励 R(s, a, s')
done: 是否终止状态
Example:
>>> mdp = TabularMDP(n_states=4, n_actions=2)
>>> # 在状态 0 采取动作 0，以概率 1.0 转移到状态 1，获得奖励 -1
>>> mdp.add_transition(0, 0, 1.0, 1, -1.0)
"""
# 验证概率
if not 0 <= prob <= 1:
raise ValueError(f"概率必须在 [0, 1] 范围内，得到 {prob}")
# 添加到转移字典
self.P[state][action].append((prob, next_state, reward, done))
def get_transitions(self, state: int, action: int) -> List[Tuple]:
"""
获取给定状态 - 动作对的所有可能转移
Args:
state: 状态 s
action: 动作 a
Returns:
转移列表 [(prob, next_state, reward, done), ...]
"""
return self.P[state][action]
def sample_next_state(self, state: int, action: int) -> Tuple[int, float, bool]:
"""
采样下一状态（用于仿真）
Args:
state: 当前状态
action: 动作
Returns:
next_state: 采样到的下一状态
reward: 获得的奖励
done: 是否终止
"""
transitions = self.P[state][action]
# 分离概率和其他信息
probs = [t[0] for t in transitions]
# 采样
idx = np.random.choice(len(transitions), p=probs)
_, next_state, reward, done = transitions[idx]
return next_state, reward, done
def is_valid(self) -> bool:
"""
验证 MDP 是否有效
检查每个状态 - 动作对的转移概率和是否为 1
Returns:
valid: 是否有效
"""
for s in range(self.nS):
for a in range(self.nA):
total_prob = sum(t[0] for t in self.P[s][a])
if abs(total_prob - 1.0) > 1e-6:
print(f"警告：状态 {s} 动作 {a} 的转移概率和为 {total_prob}，不是 1")
return False
return True
实现二：贝尔曼方程计算¶
"""
贝尔曼方程实现
实现贝尔曼期望方程和贝尔曼最优化方程的数值计算
"""
import numpy as np
from typing import Tuple, Optional
def bellman_expectation_V(
mdp,
V: np.ndarray,
policy: np.ndarray,
) -> np.ndarray:
"""
贝尔曼期望方程 - 计算 V_π
公式：
V_π(s) = Σ π(a|s) Σ P(s'|s,a) [R(s,a,s') + γV_π(s')]
a s'
算法复杂度：
- 时间：O(|S| * |A| * |S'|)，其中 |S'| 是每个状态 - 动作对的平均转移数
- 空间：O(|S|)
Args:
mdp: TabularMDP 实例
V: 当前价值函数，形状 (nS,)
policy: 策略 π(a|s)，形状 (nS, nA)
policy[s, a] 表示在状态 s 选择动作 a 的概率
Returns:
new_V: 更新后的价值函数，形状 (nS,)
Example:
>>> mdp = TabularMDP(n_states=4, n_actions=2)
>>> # 设置转移概率...
>>> V = np.zeros(4)
>>> policy = np.ones((4, 2)) * 0.5 # 随机策略
>>> new_V = bellman_expectation_V(mdp, V, policy)
"""
# 输入验证
if V.shape != (mdp.nS,):
raise ValueError(f"V 的形状 {V.shape} 不匹配，期望 ({mdp.nS},)")
if policy.shape != (mdp.nS, mdp.nA):
raise ValueError(
f"policy 的形状 {policy.shape} 不匹配，期望 ({mdp.nS}, {mdp.nA})"
)
# 初始化新价值函数
new_V = np.zeros(mdp.nS)
# 对每个状态应用贝尔曼方程
for s in range(mdp.nS):
# 对每个动作求和
for a in range(mdp.nA):
# 对每个可能的下一状态求和
for prob, next_s, reward, done in mdp.P[s][a]:
# 贝尔曼方程的核心：即时奖励 + 折扣后的未来价值
future_value = 0.0 if done else V[next_s]
new_V[s] += policy[s, a] * prob * (reward + mdp.gamma * future_value)
return new_V
def bellman_optimality_V(
mdp,
V: np.ndarray,
) -> np.ndarray:
"""
贝尔曼最优化方程 - 计算 V*
公式：
V*(s) = max Σ P(s'|s,a) [R(s,a,s') + γV*(s')]
a s'
与期望方程的区别：
- 期望方程：对动作求平均（给定策略）
- 最优化方程：对动作取 max（最优策略）
Args:
mdp: TabularMDP 实例
V: 当前价值函数估计，形状 (nS,)
Returns:
new_V: 更新后的价值函数，形状 (nS,)
"""
if V.shape != (mdp.nS,):
raise ValueError(f"V 的形状 {V.shape} 不匹配，期望 ({mdp.nS},)")
new_V = np.zeros(mdp.nS)
for s in range(mdp.nS):
q_values = [] # 存储每个动作的 Q 值
for a in range(mdp.nA):
q_sa = 0.0
for prob, next_s, reward, done in mdp.P[s][a]:
future_value = 0.0 if done else V[next_s]
q_sa += prob * (reward + mdp.gamma * future_value)
q_values.append(q_sa)
# 取最大 Q 值作为最优价值 ⭐ 关键区别
new_V[s] = max(q_values)
return new_V
def extract_greedy_policy(mdp, V: np.ndarray) -> np.ndarray:
"""
从价值函数提取贪婪策略
给定价值函数 V，贪婪策略选择能最大化 Q 值的动作：
π(s) = argmax_a Σ P(s'|s,a) [R(s,a,s') + γV(s')]
Args:
mdp: TabularMDP 实例
V: 价值函数，形状 (nS,)
Returns:
policy: 确定性策略，形状 (nS,)
policy[s] 是状态 s 的最优动作
"""
if V.shape != (mdp.nS,):
raise ValueError(f"V 的形状 {V.shape} 不匹配，期望 ({mdp.nS},)")
policy = np.zeros(mdp.nS, dtype=int)
for s in range(mdp.nS):
q_values = []
for a in range(mdp.nA):
q_sa = 0.0
for prob, next_s, reward, done in mdp.P[s][a]:
future_value = 0.0 if done else V[next_s]
q_sa += prob * (reward + mdp.gamma * future_value)
q_values.append(q_sa)
# 选择 Q 值最大的动作
policy[s] = np.argmax(q_values)
return policy
实现三：策略迭代算法¶
"""
策略迭代算法
通过交替进行策略评估和策略改进，找到最优策略
"""
import numpy as np
from typing import Tuple, Optional
def policy_evaluation(
mdp,
policy: np.ndarray,
V: Optional[np.ndarray] = None,
tol: float = 1e-6,
max_iter: int = 1000,
) -> np.ndarray:
"""
策略评估：计算给定策略 π 的价值函数 V_π
使用迭代法求解贝尔曼期望方程：
V_{k+1}(s) = Σ π(a|s) Σ P(s'|s,a) [R(s,a,s') + γV_k(s')]
收敛条件：max_s |V_{k+1}(s) - V_k(s)| < tol
Args:
mdp: TabularMDP 实例
policy: 策略 π(a|s)，形状 (nS, nA)
V: 初始价值函数（可选），形状 (nS,)
tol: 收敛容差
max_iter: 最大迭代次数
Returns:
V: 收敛后的价值函数，形状 (nS,)
Note:
迭代法的收敛性由压缩映射定理保证。
因为 γ < 1，贝尔曼算子是压缩映射，所以迭代必然收敛。
"""
if V is None:
V = np.zeros(mdp.nS)
for iteration in range(max_iter):
# 保存旧价值函数（用于检查收敛）
V_old = V.copy()
# 贝尔曼期望方程更新
V = bellman_expectation_V(mdp, V, policy)
# 检查收敛
delta = np.max(np.abs(V - V_old))
if delta < tol:
break
return V
def policy_improvement(
mdp,
V: np.ndarray,
) -> np.ndarray:
"""
策略改进：从价值函数提取贪婪策略
对于每个状态，选择能最大化 Q 值的动作：
π'(s) = argmax_a Σ P(s'|s,a) [R(s,a,s') + γV(s')]
Args:
mdp: TabularMDP 实例
V: 价值函数，形状 (nS,)
Returns:
policy: 确定性策略（one-hot 编码），形状 (nS, nA)
"""
# 提取贪婪动作
greedy_actions = extract_greedy_policy(mdp, V)
# 转换为 one-hot 编码的策略
policy = np.zeros((mdp.nS, mdp.nA))
policy[np.arange(mdp.nS), greedy_actions] = 1.0
return policy
def policy_iteration(
mdp,
tol: float = 1e-6,
max_iter: int = 100,
verbose: bool = False,
) -> Tuple[np.ndarray, np.ndarray, int]:
"""
策略迭代算法
算法流程：
1. 初始化任意策略 π_0
2. 策略评估：计算 V_{π_k}
3. 策略改进：π_{k+1} = greedy(V_{π_k})
4. 如果 π_{k+1} = π_k，返回；否则 k ← k+1，回到步骤 2
收敛性：
- 对于有限 MDP，策略迭代在有限步内收敛到最优策略
- 每次迭代都严格改进（或保持不变）
Args:
mdp: TabularMDP 实例
tol: 策略评估的收敛容差
max_iter: 最大迭代次数
verbose: 是否打印迭代信息
Returns:
V: 最优价值函数，形状 (nS,)
policy: 最优策略（one-hot 编码），形状 (nS, nA)
n_iters: 实际迭代次数
"""
# 初始化随机策略
policy = np.ones((mdp.nS, mdp.nA)) / mdp.nA
for iteration in range(max_iter):
# 策略评估
V = policy_evaluation(mdp, policy, tol=tol)
# 策略改进
new_policy = policy_improvement(mdp, V)
# 检查策略是否收敛
if np.array_equal(policy, new_policy):
if verbose:
print(f"策略迭代在 {iteration + 1} 次迭代后收敛")
break
policy = new_policy
return V, policy, iteration + 1
（第二部分完成，待续...）
🔬 算法对比¶
策略迭代 vs 价值迭代¶
| 维度 | 策略迭代 | 价值迭代 |
|---|---|---|
| 核心思想 | 交替评估和改进策略 | 直接迭代贝尔曼最优化方程 |
| 每次迭代 | 策略评估（多步）+ 策略改进（一步） | 贝尔曼最优更新（一步） |
| 收敛速度 | 迭代次数少，但每次迭代成本高 | 迭代次数多，但每次迭代成本低 |
| 内存需求 | 需要存储策略和价值函数 | 只需存储价值函数 |
| 适用场景 | 状态空间较小 | 状态空间较大 |
数学对比¶
策略迭代：
重复直到收敛：
# 策略评估
V_{k+1}(s) ← Σ π(a|s) Σ P(s'|s,a) [R + γV_k(s')] （多次迭代直到收敛）
# 策略改进
π'(s) ← argmax_a Σ P(s'|s,a) [R + γV(s')]
价值迭代：
选择建议¶
选择策略迭代如果： - 状态空间较小（< 1000） - 需要精确的最优策略 - 策略评估可以快速收敛
选择价值迭代如果： - 状态空间较大 - 可以接受近似最优 - 想简化实现
🧪 动手实验¶
实验一：午餐选择器 MDP 建模¶
任务描述：
将午餐选择问题建模为 MDP，并求解最优策略。
环境参数：
| 状态因素 | 取值 | 状态数 |
|---|---|---|
| 天气 | 晴天/雨天/寒冷 | 3 |
| 预算 | 充足/紧张 | 2 |
| 上次选择 | 食堂/外卖/带饭 | 3 |
| 总状态数 | 18 |
| 动作 | 即时奖励 |
|---|---|
| 食堂 | 满意度 6 - 成本 2 = 4 |
| 外卖 | 满意度 8 - 成本 5 = 3 |
| 带饭 | 满意度 7 - 成本 1 = 6 |
实验步骤：
- 创建 MDP 实例
- 定义状态转移概率
- 用策略迭代求解最优策略
- 分析不同状态下的最优选择
预期结果： - 预算紧张时：倾向带饭 - 预算充足时：可能点外卖 - 连续吃食堂后：可能想换口味
思考题： 1. 如果增加"健康值"状态，最优策略会如何变化？ 2. 折扣因子 γ 对策略有什么影响？ 3. 如果外卖奖励从 3 提高到 5，策略会变化吗？
实验二：网格世界导航¶
任务描述：
在网格世界中，智能体从起点走到终点，避开障碍。
环境设置：
- S：起点 (0,0) - G：终点 (3,3)，奖励 +10 - X：障碍 (1,1) 和 (2,2)，奖励 -10 - 每步奖励：-1 - 动作：上/下/左/右实验步骤：
- 创建 4x4 网格 MDP
- 定义转移概率（90% 按预期移动，10% 随机）
- 用价值迭代求解
- 可视化最优路径
分析指标： - 最优路径长度 - 各状态的价值分布 - 障碍附近的状态价值
实验三：折扣因子敏感性分析¶
任务描述：
研究折扣因子 γ 对最优策略的影响。
参数设置：
| 组别 | γ | 预期行为 |
|---|---|---|
| A | 0.5 | 短视，只看眼前奖励 |
| B | 0.9 | 平衡短期和长期 |
| C | 0.99 | 远视，重视长期回报 |
实验步骤：
- 在同一个 MDP 上，用不同 γ 值求解
- 比较最优策略的差异
- 比较最优价值函数的差异
预期现象： - γ 小：选择即时奖励高的动作 - γ 大：可能牺牲短期利益换取长期回报
实验四：策略迭代收敛性分析¶
任务描述：
分析策略迭代算法的收敛行为。
实验步骤：
- 记录每次迭代的策略变化
- 绘制收敛曲线（策略变化 vs 迭代次数）
- 分析收敛速度与 MDP 规模的关系
分析指标： - 收敛所需迭代次数 - 每次迭代的策略改进幅度 - 与价值迭代的对比
❓ 常见问题¶
Q1: 为什么需要折扣因子 γ？不能直接设为 1 吗？¶
A: 从数学和实际两个角度回答。
数学角度：
对于无限 horizon 问题，总回报是：
如果 \(R_t\) 不趋于 0，这个级数可能发散。折扣因子保证了级数收敛：
实际角度：
-
不确定性：未来的奖励不如现在的确定。可能中途"死亡"（episode 终止），拿不到未来奖励。
-
时间价值：经济学中，现在的钱比未来的钱更有价值（可以投资生息）。
-
计算便利：γ < 1 时，贝尔曼算子是压缩映射，保证迭代收敛。
什么时候用 γ = 1：
对于有限 horizon 或必然终止的 MDP（如迷宫问题），可以用 γ = 1。
Q2: 贝尔曼方程和动态规划有什么关系？¶
A: 贝尔曼方程是动态规划的核心。
动态规划的创始人 Richard Bellman 提出了最优性原理：
最优策略的子策略也是最优的。
这个原理的数学表达就是贝尔曼方程。
在强化学习中，我们用动态规划方法求解贝尔曼方程： - 策略迭代：用贝尔曼期望方程评估策略 - 价值迭代：用贝尔曼最优化方程直接更新价值
Q3: 策略迭代和价值迭代哪个更好？¶
A: 没有绝对答案，取决于场景。
策略迭代优势： - 迭代次数少（通常几次就收敛） - 每次迭代有明确的策略改进
策略迭代劣势： - 每次迭代需要多次策略评估（可能很慢） - 需要存储策略和价值函数
价值迭代优势： - 实现简单（就一行更新） - 内存需求低
价值迭代劣势： - 迭代次数多 - 收敛速度慢
经验法则： - 小状态空间（< 1000）：策略迭代 - 大状态空间：价值迭代 - 需要精确解：策略迭代 - 可以接受近似：价值迭代
Q4: 如果转移概率未知怎么办？¶
A: 这是强化学习与动态规划的关键区别。
动态规划：假设 MDP 已知（知道 P 和 R），直接求解。
强化学习：MDP 未知，需要通过与环境交互来学习。
当 P 和 R 未知时，不能用策略迭代或价值迭代。需要用： - 蒙特卡洛方法（第 3 章） - 时序差分学习（第 4 章） - Q-Learning、SARSA 等
Q5: MDP 能建模所有决策问题吗？¶
A: 不能。MDP 有几个关键假设：
1. 马尔可夫性质：未来只取决于现在。
如果问题不满足（如扑克牌游戏，需要记住出过的牌），可以用： - POMDP（部分可观测 MDP） - 扩展状态定义（把历史纳入状态）
2. 离散状态和动作：
如果是连续的（如机器人控制），可以用： - 离散化 - 函数近似（第 5 章） - 策略梯度方法（第 6 章）
3. 单智能体：
如果是多智能体（如博弈），可以用： - 博弈论 - 多智能体 RL
📚 延伸阅读¶
核心教材¶
- Sutton & Barto, Chapter 3: Markov Decision Processes
- https://www.andrew.cmu.edu/course/10-703/textbook/BartoSutton.pdf
-
最权威的 RL 教材，MDP 章节讲得非常清晰
-
Puterman, Chapter 1-3: Markov Decision Processes
- 专门讲 MDP 的专著，理论深入
在线资源¶
- David Silver 的 RL 课程 Lecture 2
- https://www.youtube.com/watch?v=lfHX2hHRMVQ
-
直观讲解 MDP 和贝尔曼方程
-
Spinning Up in Deep RL
- https://spinningup.openai.com
- 包含 MDP 基础的简明教程
代码资源¶
| 文件 | 内容 | 行数 |
|---|---|---|
bellman_equation.py |
贝尔曼方程计算 | ~300 |
value_function.py |
策略迭代/价值迭代 | ~200 |
games/lunch_decision.py |
午餐选择器环境 | ~150 |
games/commute_planner.py |
通勤规划环境 | ~150 |
✅ 本章检查清单¶
学完本章后，你应该能够：
概念理解： - [ ] 解释 MDP 五元组的含义 - [ ] 解释马尔可夫性质的含义和重要性 - [ ] 区分状态价值和动作价值 - [ ] 解释折扣因子的作用
数学推导： - [ ] 推导贝尔曼期望方程 - [ ] 推导贝尔曼最优化方程 - [ ] 理解策略改进定理
代码实现： - [ ] 实现表格型 MDP 表示 - [ ] 实现贝尔曼方程计算 - [ ] 实现策略迭代算法 - [ ] 实现价值迭代算法
实验分析： - [ ] 完成午餐选择器建模 - [ ] 完成网格世界导航 - [ ] 分析折扣因子的影响 - [ ] 比较策略迭代和价值迭代
应用判断： - [ ] 将实际问题建模为 MDP - [ ] 选择合适的求解算法 - [ ] 诊断 MDP 建模中的问题
📝 课后测验（10 分钟）¶
基础题（必答）¶
1. MDP 五元组是什么？每个元素的含义是什么？
点击查看答案
**答案**：MDP = (S, A, P, R, γ) - S（状态）：所有可能的情况 - A（动作）：所有可能的选择 - P（转移概率）：P(s'|s,a)，动作如何影响未来 - R（奖励）：R(s,a,s')，什么是"好"的 - γ（折扣因子）：未来回报的折扣率2. 贝尔曼期望方程和最优化方程的区别是什么？
点击查看答案
**答案**： - **期望方程**：给定策略π，计算 V_π(s) = Σ π(a|s) Σ P(s'|s,a)[R + γV(s')] - **最优化方程**：找最优策略，V*(s) = max_a Σ P(s'|s,a)[R + γV*(s')] 关键区别：期望方程对动作求平均，最优化方程对动作取 max。3. 为什么需要折扣因子 γ？设为 1 会有什么问题？
点击查看答案
**答案**： 1. **数学原因**：保证无限级数收敛（γ<1 时 Σγ^t 收敛） 2. **实际原因**：未来奖励不如现在确定（可能中途"死亡"） 3. **设为 1 的问题**： - 无限 horizon 问题可能发散 - 不模拟不确定性 - 仅适用于有限/必然终止的任务进阶题（选答）¶
4. 证明：如果 π' 是相对于 V_π 的贪婪策略，则 V_π' ≥ V_π
点击查看答案
**证明思路**： 1. 由贪婪策略定义：Q_π(s, π'(s)) ≥ V_π(s) 2. 展开 V_π' 的贝尔曼方程 3. 用归纳法证明 V_π' ≥ V_π 完整证明见"公式推导 - 策略改进定理"部分。5. 策略迭代和价值迭代哪个更好？为什么？
点击查看答案
**答案**：没有绝对答案，取决于场景。 | 场景 | 推荐 | 原因 | |------|------|------| | |S| < 1000 | 策略迭代 | 迭代次数少 | | |S| > 1000 | 价值迭代 | 每次迭代快 | | 需要精确解 | 策略迭代 | 有限步收敛 | | 可以近似 | 价值迭代 | 实现简单 |编程题（实践）¶
6. 实现一个简单的 MDP（如 4 状态网格世界），用策略迭代求解最优策略。
查看提示
**提示**： 1. 定义 4 个状态、2 个动作 2. 设置转移概率和奖励 3. 用 `policy_iteration` 函数求解 4. 可视化最优策略 参考代码：`chapter_01_mdp_fundamentals/value_function.py`🚀 下一章预告¶
第 2 章：动态规划
当 MDP 已知时，如何高效求解最优策略？本章将介绍： - 策略迭代的深入分析 - 价值迭代的收敛性证明 - 蒙特卡洛树搜索（MCTS） - 应用：网格寻路、AlphaGo 简化版
预告实验：实现一个能玩五子棋的 MCTS 智能体！🎯
最后更新：2026-04-22
作者：Hermes neko_yukirin@qq.com