已知模型 · 迭代求解
有限 MDP + 动态规划Finite MDP + Dynamic Programming
从"单臂选择"到"序列决策" — 在 GridWorld 上看值函数和策略的演化
3 小时
阅读 + 实操
3 个
交互演示
进阶
难度
有限 MDP + 动态规划 · 交互演示
迭代次数0
最大 Δ--
网格5×5
值函数 V(s):
低
高
|
终点
点击网格格子可切换状态类型
3.1 序列决策的形式化：为什么需要 MDP
GridWorld 里「好位置」的颜色是怎么算出来的？答案是：一个状态的价值 = 即时奖励 + 未来价值的折扣和。本章把这个直觉形式化成 MDP 五元组和贝尔曼方程，再用三种动态规划算法在网格上迭代求解 —— 你将第一次看到值函数热力图从混沌收敛到清晰的全过程。
下一步预告：DP 需要完整的环境模型（转移概率），真实问题往往拿不到；下一章改用蒙特卡洛——不靠模型，只靠完整回合的经验。
📌 发生了什么
- MDP 五元组 ⟨S, A, P, R, γ⟩ 定义序列决策问题
- 贝尔曼方程 V(s)=Σπ(a|s)[R+γV(s')] 是递归更新的根基
- 三种 DP 算法：策略评估、策略迭代、值迭代
⚠️ 常见陷阱
- 策略评估和值迭代是一回事？前者用期望方程不取 max，后者每步取 max 逼近最优。
- γ 越大越接近最优？γ=1 含自环策略会发散，PE 模式封顶 0.99。
- 值迭代中间的 V 是某策略的真实价值？不是，只有收敛后才等于 V*。
✅ 本章小结
- MDP 五元组 ⟨S, A, P, R, γ⟩ 定义序列决策问题
- 贝尔曼方程是所有 RL 算法递归更新的根基
- 三种 DP 算法：评估算 V、迭代交替改进、值迭代直接取 max
- 折扣因子 γ 控制远见，典型取 0.9~0.99
3.2 贝尔曼期望方程：给策略打分
动态规划的核心是 Bellman 方程：把「从某状态出发的长期价值」分解为「即时奖励 + 下一状态的价值」。
Bellman 期望方程：在策略 π 下，状态 s 的价值 = 对所有动作按 π 加权求和，每个动作的值为转移期望（即时奖励 + γ × 下一状态价值）。
3.3 贝尔曼最优方程：直接求最好
Bellman 最优方程：把求和换成 max —— 最优价值就是在所有动作中取最好的那个。求解它就得到最优状态价值 V*。
3.4 从 V 到 Q：动作价值与最优策略
动作价值形式：Q*(s,a) 是在状态 s 选动作 a 后、之后按最优策略行动的期望回报。最优策略 π*(s) = argmax_a Q*(s,a)。
3.5 策略迭代 vs 值迭代：怎么选
动态规划求最优策略的两条路线：策略迭代显式交替「评估-改进」，值迭代直接对最优方程做迭代。
| 方法 | 特点 | 适用 |
|---|---|---|
| 策略迭代 | 策略评估到收敛再改进，每轮稳定 | 收敛快、需完整模型 |
| 值迭代 | 直接迭代 Bellman 最优方程，单步即改进 | 实现简单、广用 |
| 截断策略迭代 | 策略评估只做 k 步就改进，折中 | 需调 k |
💡 两者都要求完全已知 P 和 R（model-based）；未知时需用后续的 MC / TD 方法。
3.6 值迭代核心代码走读
对每个状态套用 Bellman 最优方程，直到 V 不再变化（Python，与上方演示器同步）：
gamma = 0.9
V = np.zeros(n_states)
while True:
delta = 0
for s in states:
if is_terminal(s): continue
best = -np.inf
for a in actions(s):
q = 0
for s2, p, r in transitions(s, a):
q += p * (r + gamma * V[s2]) # 期望
if q > best: best = q
delta = max(delta, abs(best - V[s]))
V[s] = best
if delta <= theta: break # 收敛阈值📚 参考文献与延伸阅读
- Sutton & Barto, Reinforcement Learning (2nd ed.), §4 Dynamic Programming — 策略评估、迭代与异步 DP
- Bellman, R. (1957), Dynamic Programming — Bellman 方程与最优性原理的奠基之作
- Wikipedia: Bellman equation — 期望/最优方程的推导与性质
📝 课后练习
检验你的理解——答对为止