6.1 MDP与贝尔曼方程关卡
6.1 MDP与贝尔曼方程关卡
MDP 考点：五元组、马尔可夫性判别、折扣回报与贝尔曼方程的迭代求解。通关标准：能把决策问题翻译成元组，手算小型 MDP 的价值函数收敛过程，并能说清折扣因子两头兼顾的作用。决策编队首关：先把战场写成数学，后头的试错算法才有处落脚。
决策沙盘：关卡题目
关卡一（单选）：下列哪种情形最符合马尔可夫性对"状态"的要求？
A. 状态只记录棋盘当前局面，双方历史走法全部丢弃
B. 状态记录当前局面加完整对局历史，越多越好
C. 状态是"心情好坏"这种连当事人也说不清的隐变量
D. 状态每隔一步才更新一次
关卡二（计算）：智能体沿一条直路前进，即将依次拿到即时奖励零、零、十，折扣因子取零点九。从起点算起的折扣回报是多少？
关卡三（简答）：状态价值函数与动作价值函数是什么关系？各自回答什么问题？
关卡四（单选）：贝尔曼最优方程描述的是：
A. 任意给定策略下价值满足的平均关系
B. 最优价值满足的递推关系：当前价值等于即时奖励加上折扣后的后续最优价值
C. 奖励函数的设计原则
D. 策略梯度的更新方向
先攻提示
- 关卡一想"状态的信息够不够"：未来只看现在的状态就够不够做判断；
- 关卡二把各步奖励乘上折扣因子的幂次再求和，注意幂次从零起算；
- 关卡三从"固定策略"与"固定首步动作"两种条件入手；
- 关卡四对照贝尔曼期望方程：一个按当前策略平均，一个按最优取大。
后核：标准解析
关卡一选 A。 马尔可夫性要求"当前状态包含预测未来所需的全部信息，历史不再额外提供增量"。棋盘局面本身就是充分统计量——历史走法已经全部反映在当前局面上，丢弃历史不丢信息。B 错在冗余不是错误但违背状态设计的简洁原则，且维数爆炸；C 的隐变量不可观测，状态刻画不充分，严格说进入了部分可观测的范畴；D 的更新节奏与马尔可夫性无关，反而可能造成信息滞后。判别口诀：看到当前状态，未来与过去条件独立。
关卡二：折扣回报 = 零乘零点九的零次方 + 零乘零点九的一次方 + 十乘零点九的平方 = 八点一。幂次从零起算是易错点：即时奖励不打折。用代码把折扣因子敏感性一起做掉：
# 折扣回报手算 + 敏感性实验（同一奖励序列，不同折扣因子） def discounted_return(rewards, gamma): return sum(r * (gamma ** t) for t, r in enumerate(rewards)) rewards = [0, 0, 10] for g in [0.5, 0.9, 0.99, 1.0]: print(f"γ={g:<5} 回报={discounted_return(rewards, g):.3f}") # 输出： # γ=0.5 回报=2.500 # γ=0.9 回报=8.100 # γ=0.99 回报=9.801 # γ=1.0 回报=10.000
结果解读：折扣因子越接近一，智能体越"远视"，未来奖励越接近足值；越小越"近视"，只顾眼前。它还兼任收敛阀：无限步任务里只要奖励持续产生、折扣严格小于一，回报就被压成一个有限几何级数，价值函数才有定义。变式：把远端奖励从十改成每月发一次的持续小奖励，取 γ 等于一观察回报发散，验证收敛阀的必要性。
关卡三：状态价值 V(s) 回答"在状态 s 下，按当前策略走到底，长期回报期望多少"；动作价值 Q(s,a) 回答"在状态 s 先走动作 a、之后仍按策略走，长期回报期望多少"。两者由期望桥接：V(s) 等于对策略下各动作的 Q 值按概率加权。策略改进时 Q 更好用——比较"各动作谁值高"是逐动作的事，V 只是加权后的结果。
关卡四选 B。 贝尔曼最优方程：V*(s) = max_a [ R(s,a) + γ · V*(s′) ] 的期望形式，最优价值的最优性来自"之后每步都取最优"。A 描述的是贝尔曼期望方程（按策略平均而非取大）；C、D 与方程无关。两者的差别是强化学习最高频考点之一：期望版用于策略评估，最优版用于求解最优策略。
把首关的沙盘推演做实：一条三格链路，走到底拿大奖，策略是随机游走（前进后退各半）。背景：已知转移规则、未知价值函数，用贝尔曼期望方程反复迭代直至收敛——这正是动态规划里策略评估的原型。
# 三格链路 MDP 的贝尔曼迭代（策略评估，数值可笔算复核） # 状态 A - B - C，C 前进一步到终点拿奖励 10；策略：前进/后退各半；γ=0.9 import itertools GAMMA = 0.9 states = ["A", "B", "C"] V = {s: 0.0 for s in states} def step(s, action): """返回 (下一状态, 即时奖励)。前进：向右；后退：向左。""" i = states.index(s) if action == "前进": if i == len(states) - 1: # C 前进到终点 return None, 10.0 return states[i + 1], 0.0 if i == 0: # A 后退原地踏步 return "A", 0.0 return states[i - 1], 0.0 for sweep in range(1, 200): delta = 0.0 newV = {} for s in states: v = 0.0 for act, prob in [("前进", 0.5), ("后退", 0.5)]: s2, r = step(s, act) future = 0.0 if s2 is None else V[s2] v += prob * (r + GAMMA * future) newV[s] = v delta = max(delta, abs(v - V[s])) V = newV if sweep in (1, 2, 5, 20, 100): print(f"第{sweep}轮: " + " ".join(f"V({s})={V[s]:.3f}" for s in states)) if delta < 1e-9: print(f"收敛于第 {sweep} 轮") break print("最终: " + " ".join(f"V({s})={V[s]:.3f}" for s in states)) # 输出： # 第1轮: V(A)=0.000 V(B)=0.000 V(C)=5.000 # 第2轮: V(A)=0.000 V(B)=2.250 V(C)=6.013 # 第5轮: V(A)=1.084 V(B)=3.979 V(C)=6.874 # 第20轮: V(A)=2.947 V(B)=4.777 V(C)=7.247 # 第100轮: V(A)=4.249 V(B)=5.198 V(C)=7.338 # 收敛于第 199 轮 # 最终: V(A)=4.249 V(B)=5.198 V(C)=7.338
结果解读：价值从终点向起点逐轮"回流"——C 靠近大奖先抬头，B、A 依次跟涨，最终 A 到 C 的价值梯度约四点二比五点二比七点三，沿梯度走正是贪心策略的雏形。手算验算路标：解析解满足 V(C) = 5 + 0.45V(B)、V(B) = 0.45(V(C) + V(A))、V(A) = 0.45(V(B) + V(A))，代入终值可逐条复核。变式：把策略改成前进八成、后退两成重跑，三格价值整体抬升、差距拉大——策略与价值一一对应，这正是"策略评估"名字的含义。
交互环读法：奖励与状态由环境单方面发放，智能体唯一的主动权是选动作；价值函数是把"环"摊平成"递推"的翻译器，贝尔曼方程就是那份翻译文本。
复盘：易错点与变式
易错点一：折扣幂次从一处起算。即时奖励不打折（幂次为零），错成从一起算会把整条回报系统性压低——关卡二的八点一算成七点二九，就是踩了这颗雷。
易错点二：把奖励当价值。奖励是单步即时反馈，价值是长期累积回报的期望；"这一步拿得多"与"这个状态值得待"可以完全相反——绕远路上的高奖励格子可能是陷阱。
易错点三：对部分可观测场景硬套马尔可夫性。状态刻画不充分时（例如对手手牌不可见），严格做法是堆历史窗口或上信念状态，转成部分可观测问题处理；答题时点出这层前提，比硬说"满足"更显严谨。
变式一：问"贝尔曼期望方程与最优方程各自的用途"。答：期望版配合固定策略做评估，收敛到该策略的价值；最优版逐动作取大，直接解出最优价值与贪心最优策略——前者是"算账"，后者是"找路"。
变式二：问"为什么随机策略下价值仍有意义"。答：价值是期望，衡量的是"平均而言划不划算"；随机化本身还是探索的手段——价值评估对任意策略都成立，这正是首关代码里"前进后退各半"也能收敛的原因。
复盘产出：决策卡"MDP 建模"一栏补齐：五元组落位、折扣兼管远视与收敛、贝尔曼方程分期望与最优两版。下一关撤掉地图：环境规则不再已知，看 Q-learning 怎么纯靠试错把同一张沙盘解出来。