十：强化学习：Bellman Equation 与策略迭代算法

来源:http://mp.weixin.qq.com/s?__biz=MzYyNTk3Njg1NA==&mid=2247483884&idx=1&sn=a0f6e0d57a7d9df2a2a4cf229c4ec75f&chksm=f01eb295c7693b83765176212fde2e515560e639c765f6d02c771967d01ee9bd958500fa1012#rd

1. 学习定位

第九天已经建立了 MDP 的基本框架：(S, A, P, R, gamma)、策略 pi、回报 G_t、价值函数 V^pi 和 Q^pi。第十天的重点是把这些定义变成可计算的递推方程和求解算法。 Bellman equation 的核心思想是：

长期价值 = 当前即时奖励 + 折扣后的下一步长期价值

策略迭代算法的核心思想是：

先评估当前策略有多好
再根据价值函数改进策略
不断重复，直到策略不再变化

本日知识链路：

MDP 定义
-> Bellman expectation equation
-> Bellman optimality equation
-> Bellman operator 与 fixed point
-> Dynamic Programming
-> Iterative Policy Evaluation
-> Policy Improvement
-> Policy Iteration
-> Value Iteration
-> Cliff Walking / Frozen Lake 等网格环境示例

2. Bellman 方程的位置

在强化学习中，价值函数不是孤立定义的。由于 MDP 具有马尔可夫性，从当前状态出发的长期价值可以拆成两部分：

1. 当前动作带来的即时奖励
2. 到达下一状态后的长期价值

这就是 Bellman 递推结构。它把“从现在到未来所有时刻”的目标，转化为“当前一步 + 下一状态的同类问题”。 从算法角度看，Bellman 方程有三类用途： - 策略评估：给定策略 pi，计算 V^pi 或 Q^pi。

• 策略改进：根据价值函数选择更好的动作。

• 最优控制：直接求最优价值函数 V* 或 Q*，再导出最优策略。

3. 贝尔曼期望方程

贝尔曼期望方程描述固定策略 pi 下的价值递推。 状态价值函数：

V^pi(s) = E_pi[G_t | S_t=s]

贝尔曼期望方程：

V^pi(s)
= sum_a pi(a|s) [ R(s,a) + gamma sum_{s'} P(s'|s,a) V^pi(s') ]

动作价值函数：

Q^pi(s,a) = E_pi[G_t | S_t=s, A_t=a]

动作价值的贝尔曼期望方程：

Q^pi(s,a)
= R(s,a) + gamma sum_{s'} P(s'|s,a) sum_{a'} pi(a'|s') Q^pi(s',a')

这些方程中的期望来自三类随机性： - 策略可能随机选择动作。

• 环境转移可能随机。

• 奖励可能随机。

4. 矩阵形式的策略评估

对有限 MDP，可以把固定策略下的环境转成一个 Markov Reward Process。 策略诱导的转移矩阵：

P_pi(s,s') = sum_a pi(a|s) P(s'|s,a)

策略诱导的奖励向量：

R_pi(s) = sum_a pi(a|s) R(s,a)

贝尔曼期望方程可写成：

V_pi = R_pi + gamma P_pi V_pi

移项得到：

(I - gamma P_pi) V_pi = R_pi
V_pi = (I - gamma P_pi)^(-1) R_pi

直接矩阵求逆在小规模状态空间中可行，但在大规模问题中代价高、数值风险大，因此实际常用迭代法。

5. 贝尔曼最优方程

最优价值函数定义为：

V*(s) = max_pi V^pi(s)
Q*(s,a) = max_pi Q^pi(s,a)

状态价值的贝尔曼最优方程：

V*(s)
= max_a [ R(s,a) + gamma sum_{s'} P(s'|s,a) V*(s') ]

动作价值的贝尔曼最优方程：

Q*(s,a)
= R(s,a) + gamma sum_{s'} P(s'|s,a) max_{a'} Q*(s',a')

期望方程和最优方程的核心区别：

Bellman expectation equation:
  固定策略 pi，对动作按 pi 求期望。

Bellman optimality equation:
  寻找最优行为，对动作取 max。

6. Bellman Operator 与不动点

贝尔曼方程可以理解为算子的不动点问题。 给定策略 pi 的 Bellman expectation operator：

(T_pi V)(s)
= sum_a pi(a|s) [ R(s,a) + gamma sum_{s'} P(s'|s,a) V(s') ]

最优 Bellman operator：

(T_* V)(s)
= max_a [ R(s,a) + gamma sum_{s'} P(s'|s,a) V(s') ]

对应不动点：

V^pi = T_pi V^pi
V* = T_* V*

当 0 <= gamma < 1 且奖励有界时，Bellman operator 在最大范数下是压缩映射。因此反复应用 Bellman backup 会收敛到唯一不动点。这是动态规划算法收敛的重要理论基础。

7. 动态规划算法的前提

动态规划（Dynamic Programming, DP）在强化学习中通常指：已知完整 MDP 模型时，用 Bellman 方程递推求策略或价值。 DP 的典型前提： - 状态空间和动作空间有限，或至少可以枚举/离散化。

• 已知状态转移概率 P(s'|s,a)。

• 已知奖励函数 R(s,a) 或 R(s,a,s')。

• 可以遍历状态和动作做 Bellman backup。

DP 的优点是理论清晰、可以精确利用模型。缺点是需要完整环境模型，且状态空间大时计算和存储代价很高。

8. 迭代策略评估

策略评估的目标是：给定策略 pi，求 V^pi。 迭代策略评估从任意初值 V_0 开始，反复更新：

V_{k+1}(s)
= sum_a pi(a|s) [ R(s,a) + gamma sum_{s'} P(s'|s,a) V_k(s') ]

停止条件通常是最大变化量小于阈值：

Delta = max_s |V_{k+1}(s) - V_k(s)|
stop if Delta < theta

这种更新也叫 Bellman backup。同步更新会先基于旧 V_k 计算所有新值；异步更新可以一边计算一边覆盖，常常收敛更快但实现和分析稍复杂。

9. 策略改进定理

策略改进定理说明：如果在每个状态下选择相对当前策略 pi 的 Q 值不低的动作，就能得到不差于原策略的新策略。 贪心改进：

pi_new(s) = argmax_a Q^pi(s,a)

其中：

Q^pi(s,a)
= R(s,a) + gamma sum_{s'} P(s'|s,a) V^pi(s')

如果 pi_new 和 pi 完全相同，说明策略已经对自身价值函数贪心，通常已经达到最优策略。

10. 策略迭代算法

策略迭代（Policy Iteration）交替执行两步：

1. Policy Evaluation:
   计算当前策略 pi 的 V^pi。

2. Policy Improvement:
   根据 V^pi 对每个状态选择贪心动作，得到 pi_new。

伪代码：

initialize pi randomly

loop:
  evaluate V^pi
  policy_stable = true

  for each state s:
    old_action = pi(s)
    pi(s) = argmax_a [ R(s,a) + gamma sum_{s'} P(s'|s,a) V^pi(s') ]
    if pi(s) != old_action:
      policy_stable = false

  if policy_stable:
    break

策略迭代通常在有限 MDP 中收敛到最优策略。每次策略改进不会使策略变差，有限确定性策略数量有限，因此最终会停止。

11. 截断策略评估与 Modified Policy Iteration

完整策略评估可能要迭代到非常精确，代价较高。实际可以只做若干轮评估，再进行策略改进。

evaluate pi for m iterations
improve pi greedily
repeat

这类方法称为 modified policy iteration。它位于 policy iteration 和 value iteration 之间： - m 很大时接近完整策略迭代。

• m=1 时更接近 value iteration。

12. 价值迭代算法

价值迭代（Value Iteration）直接对最优 Bellman 方程做迭代：

V_{k+1}(s)
= max_a [ R(s,a) + gamma sum_{s'} P(s'|s,a) V_k(s') ]

收敛后，用 V* 导出策略：

pi*(s) = argmax_a [ R(s,a) + gamma sum_{s'} P(s'|s,a) V*(s') ]

价值迭代不需要每轮完整评估一个策略，它把策略改进的 max 操作嵌入每次价值更新中。

13. Generalized Policy Iteration

Generalized Policy Iteration（GPI）是很多 RL 算法的共同骨架：

policy evaluation: 让价值函数更准确地评估当前策略
policy improvement: 让策略对当前价值函数更贪心

策略迭代、价值迭代、Monte Carlo control、Sarsa、Q-learning 都可以看作不同形式的 GPI，只是评估方式、改进方式和是否使用模型不同。

14. Cliff Walking 示例

Cliff Walking 是一个经典网格环境。智能体从起点走到终点，中间有悬崖区域。掉入悬崖会得到大负奖励并回到起点。 在 DP 或 TD 算法中，这个环境常用来对比策略： - 更贴近悬崖的路线步数更短，但风险更高。

• 更远离悬崖的路线更保守，但平均回报可能更稳定。

它适合说明： - 奖励设计如何影响策略。

• 探索策略会改变实际轨迹分布。

• on-policy 和 off-policy 方法可能学到不同风格的策略。

15. Frozen Lake 示例

Frozen Lake 是一个随机网格环境。智能体要从起点走到目标格，冰面可能打滑，实际移动方向不一定等于选择动作。 建模方式：

S: 网格位置
A: 上、下、左、右
P: 动作后滑到不同格子的概率
R: 到达目标给正奖励，掉入洞或普通移动给对应奖励
gamma: 控制短路径和长期成功率的权衡

Frozen Lake 适合说明随机转移环境中，最优策略不一定是几何上最短路径，而是最大化期望回报的路径。

16. 实现细节

在代码中，有限 MDP 常被表示为：

P[s][a] = [(prob, next_state, reward, done), ...]

一次 Bellman backup 需要遍历：

for s in states:
  for a in actions:
    q(s,a) = sum_{transition} prob * (reward + gamma * V[next_state])
  V_new[s] = sum_a pi(a|s) * q(s,a)       # policy evaluation
  V_new[s] = max_a q(s,a)                 # value iteration

终止状态通常需要特殊处理：

if done:
  target = reward
else:
  target = reward + gamma * V[next_state]

忽略 done 会把终止后的价值错误地加进目标，导致价值估计偏差。

17. 复杂度与局限

对有限 MDP，一轮 Bellman backup 的复杂度大致是：

O(|S| * |A| * average_next_states)

如果显式转移矩阵很稠密，可以近似为 O(|S|^2 |A|)。 DP 的局限： - 需要完整模型，现实中通常未知。

• 状态空间大时无法枚举。

• 连续状态/动作需要近似方法。

• 高维 LLM/Agent 场景中，状态和动作空间巨大，不能直接做表格 DP。

这些局限引出后续的 Monte Carlo、Temporal Difference、Sarsa、Q-learning 和深度强化学习。

18. 与 LLM、RLHF、Agent 的联系

在 LLM/RLHF 中，完整状态和转移模型通常不可知，因此很少直接做表格动态规划。但 Bellman 思想仍然重要： - 价值模型可以估计某个上下文或动作之后的长期质量。

• Agent 的工具调用策略可以用长期任务成功率评估，而不是只看当前一步是否看似合理。

• 多轮任务中的“当前回复”会影响后续用户反馈和可执行动作，天然具有 Bellman 递推结构。

• PPO、Actor-Critic 等方法中的 critic 本质上也在学习某种价值函数。

因此，Bellman 方程是理解后续值函数方法和策略梯度方法的基础。

19. 常见误区

误区一：把 Bellman 方程当成单独公式背诵。 它本质是 MDP 马尔可夫性和回报定义共同推出的递归关系。 误区二：混淆期望方程和最优方程。 期望方程评估固定策略，最优方程寻找最优动作。 误区三：认为 policy iteration 和 value iteration 完全无关。 它们都是 GPI 的不同实现。 误区四：忽略环境模型已知这个前提。 DP 需要 P 和 R。如果只能采样，就要转向 MC/TD 方法。 误区五：终止状态处理错误。 终止后不应继续加下一状态价值。

20. 核心总结

第十天需要掌握的最小闭环：

Bellman expectation:
  V^pi = T_pi V^pi
  固定策略，做期望。

Bellman optimality:
  V* = T_* V*
  最优控制，做 max。

Policy Evaluation:
  给定 pi，计算 V^pi。

Policy Improvement:
  根据 Q^pi 做贪心改进。

Policy Iteration:
  Evaluation 和 Improvement 交替直到稳定。

Value Iteration:
  直接用最优 Bellman backup 更新 V。

DP:
  已知 P 和 R，能遍历状态动作时使用。

21. 参考资料

• CSDN：贝尔曼公式理论详解：https://blog.csdn.net/qq_64671439/article/details/135305331

• CSDN：贝尔曼最优公式详解：https://blog.csdn.net/qq_64671439/article/details/135317754

• CSDN：策略迭代算法：https://blog.csdn.net/qq_64671439/article/details/135329688

• 动手学强化学习：动态规划算法：http://hrl.boyuai.com/chapter/1/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%AE%97%E6%B3%95/

• Sutton and Barto, Reinforcement Learning: An Introduction, Chapter 3-4：http://incompleteideas.net/book/RLbook2020.pdf

• OpenAI Spinning Up: Key Concepts in RL：https://spinningup.openai.com/en/latest/spinningup/rl_intro.html

• Hugging Face Deep RL Course：https://huggingface.co/learn/deep-rl-course/

          预览时标签不可点
  

  <div class="