Lecture 14: Basic Concepts in RL. Value Iteration. Policy Iteration

目录 · ← l13 · l15 →

第三部分：强化学习（Reinforcement Learning）

Lecture 14: Basic Concepts in RL. Value Iteration. Policy Iteration

概述

本讲建立强化学习的数学框架：马尔可夫决策过程 (MDP) 形式化“智能体-环境”交互，定义价值函数与贝尔曼方程刻画“长期回报”，并给出求解最优策略的两大经典算法：值迭代 (Value Iteration) 与策略迭代 (Policy Iteration)。核心直觉：把“序贯决策”转化为“在状态空间上求解不动点方程”。

核心概念与数学直觉

• 马尔可夫决策过程 (MDP)：元组 $(S, A, P_{sa}, \gamma, R)$
  • $S$：状态集合（环境的可能配置，如机器人位置/朝向）。
  • $A$：动作集合（智能体可执行的行为）。
  • $P_{sa}$：状态转移概率——在状态 $s$ 执行动作 $a$ 后转移到各状态的概率分布。马尔可夫性：下一状态只依赖当前状态与动作（历史无关）。
  • $\gamma \in [0, 1)$：折扣因子——权衡“当下收益”与“未来收益”。$\gamma$ 小=目光短浅；$\gamma$ 大=看重长远。保证无限时域回报有限（几何级数收敛）。
  • $R$：奖励函数 $R: S \times A \to \mathbb{R}$（或 $R: S \to \mathbb{R}$）。
  • 策略 (Policy)：$\pi: S \to A$（确定性）或 $\pi(a\vert s)$（随机）——智能体的行为规则。
  • 直觉：MDP 是“带奖励的马尔可夫链 + 可控动作”。RL 的任务 = 找策略 $\pi$ 使期望折扣累积回报最大。
• 价值函数：
  • 状态价值：$V^\pi(s) = E\left[ \sum_{t=0}^{\infty} \gamma^t R(s_t) \mid s_0 = s, \pi \right]$——从状态 $s$ 出发按策略 $\pi$ 行动的期望折扣回报。
  • 状态-动作价值（Q 函数）：$Q^\pi(s, a) = E\left[ \sum_{t=0}^{\infty} \gamma^t R(s_t) \mid s_0 = s, a_0 = a, \pi \right]$——先执行动作 $a$ 再按 $\pi$ 行动。
  • 最优价值：$V^(s) = \max_\pi V^\pi(s)$；最优策略 $\pi^$ 满足 $\pi^(s) = \arg\max_a Q^(s, a)$。
• 贝尔曼方程 (Bellman Equation)：价值函数的递归自洽关系： $V^\pi(s) = R(s) + \gamma \sum_{s'} P_{s\pi(s)}(s') V^\pi(s')$ $V^*(s) = R(s) + \gamma \max_{a} \sum_{s'} P_{sa}(s') V^*(s')$
  • 直觉：“从 $s$ 出发的价值 = 立即奖励 + 折扣后的未来价值期望”。贝尔曼方程把无限和化为一步 + 递归——这是所有 RL 算法的数学基石。
  • 不动点视角：$V^*$ 是贝尔曼最优算子的不动点；值迭代就是在反复应用该算子。
• 值迭代 (Value Iteration)： $V(s) := R(s) + \gamma \max_a \sum_{s'} P_{sa}(s') V(s')$，重复直到收敛。
  • 收敛后最优策略：$\pi^(s) = \arg\max_a \sum_{s^{\prime}} P_{sa}(s^{\prime}) V^(s^{\prime})$。
  • 直觉：从“只有 1 步视野”的价值开始，每轮迭代把视野多往后看一步（动态规划/自举）——价值逐渐向 $V^*$ 收敛（折扣 $\gamma < 1$ 保证收敛）。
• 策略迭代 (Policy Iteration)：交替两阶段：
  1. 策略评估 (Policy Evaluation)：固定 $\pi$，解贝尔曼方程求 $V^\pi$（线性方程组，或迭代求解）。
  2. 策略改进 (Policy Improvement)：$\pi^{\prime}(s) = \arg\max_a \sum_{s^{\prime}} P_{sa}(s^{\prime}) V^\pi(s^{\prime})$——贪心改进，保证不降（策略改进定理）。
     • 收敛：有限 MDP 中策略迭代在有限步收敛到 $\pi^*$（策略空间有限，单调改进）。
     • 对比：值迭代每步直接更新价值（隐含策略改进）；策略迭代显式维护策略。值迭代实现简单、实践中常用；策略迭代在状态数少时收敛更快（每步更贵）。

算法伪代码与逻辑解说：值迭代 / 策略迭代

伪代码 A：值迭代 (Value Iteration)

输入:
    - MDP (S, A, P_sa, γ, R)，收敛阈值 epsilon

输出:
    - 最优价值 V*，最优策略 π*

1. 初始化 V(s) = 0（所有 s）
2. 循环直到 max_s |V_new(s) - V(s)| < epsilon:
    2.1 对每个状态 s:
        V_new(s) = R(s) + γ * max_a Σ_{s'} P_sa(s') V(s')
    2.2 V = V_new
3. 对每个 s: π*(s) = argmax_a Σ_{s'} P_sa(s') V*(s')
4. 返回 V*, π*

伪代码 B：策略迭代 (Policy Iteration)

输入: MDP (S, A, P_sa, γ, R)
输出: 最优策略 π*

1. 初始化 π(s) = 任意动作（所有 s）
2. 循环直到策略不再变化:
    // 策略评估: 解线性方程组 V^π = R + γ P_π V^π
    2.1 对每个 s: V^π(s) = R(s) + γ Σ_{s'} P_{sπ(s)}(s') V^π(s')
        （或用迭代法重复应用上式直至收敛）
    // 策略改进: 贪心
    2.2 对每个 s: π'(s) = argmax_a Σ_{s'} P_sa(s') V^π(s')
    2.3 若 π' == π: 终止; 否则 π = π'
3. 返回 π*

【算法逻辑解说】

1. 值迭代 Step 2：每轮对每个状态做“一步展望”：当前奖励 + 最优后续价值。这是动态规划——利用子问题（后续状态的价值）的最优解构造当前最优解。$\gamma$ 折扣保证映射是压缩映射 ⇒ 收敛唯一不动点 $V^*$。
2. 值迭代 Step 3：价值收敛后，策略 = 每状态选“能导向最高价值”的动作——注意价值决定策略，无需显式存储策略。
3. 策略迭代 Step 2.1：固定策略下贝尔曼方程是线性方程组（$V = R + \gamma P_\pi V$），可解闭式（$(I - \gamma P_\pi)^{-1}R$）或迭代；状态数大时用迭代（每次 $O(\vert S\vert ^2)$ 或稀疏加速）。
4. 策略改进定理：$\pi^{\prime}$ 的贪心选择保证 $V^{\pi^{\prime}} \ge V^\pi$ 逐状态成立——单调改进 + 策略有限 ⇒ 有限步收敛。
5. 前提（Model-based）：两算法都需要已知 $P_{sa}$（模型）。当模型未知时，需要 L15 的无模型/学习模型方法。

关键要点

1. MDP 五元组 $(S, A, P_{sa}, \gamma, R)$：马尔可夫性 + 折扣回报是形式化的核心。
2. 贝尔曼方程 = 价值函数的递归自洽；$V^*$ 是不动点。
3. 值迭代：直接逼近 $V^*$；策略迭代：评估-改进交替，单调收敛。
4. 两者都是基于模型的动态规划；模型未知时转向 L15。
5. 价值函数把“长期回报”压缩为单状态标量——序贯决策简化为逐状态贪心。

常见误区与注意事项

• 混淆 $V$ 与 $Q$：$V(s)$ 是“状态的价值”（隐含策略）；$Q(s,a)$ 是“状态-动作的价值”，策略选择用 $Q$（$\arg\max_a Q(s,a)$）。$V^(s) = \max_a Q^(s,a)$。
• $\gamma = 1$ 不收敛：无限时域无折扣时回报可能发散——$\gamma < 1$ 是收敛的数学保障（压缩映射）。
• 值迭代收敛判据：用价值变化量（$\max_s \vert \Delta V\vert < \epsilon$）而非策略是否变化——价值接近最优时策略可能已最优但价值仍微调。
• 把奖励与回报混淆：奖励 $R$ 是立即信号；价值 $V$ 是折扣累积回报——策略优化的是后者。
• 状态数爆炸（维度灾难）：表格式 $V$ 对每个状态存一个值，状态空间大（连续/高维）时不可行——引出函数近似（L15）。

思考题

1. 问题：写出 $Q^(s,a)$ 的贝尔曼方程，并说明它与 $V^$ 方程的关系。
   • 答案：$Q^(s,a) = R(s,a) + \gamma \sum_{s^{\prime}} P_{sa}(s^{\prime}) \max_{a^{\prime}} Q^(s^{\prime},a^{\prime})$。关系：$V^(s) = \max_a Q^(s,a)$——把 $Q^$ 中的 max 代入即得 $V^$ 方程；反之 $Q^(s,a) = R(s,a) + \gamma \sum_{s^{\prime}} P_{sa}(s^{\prime}) V^(s^{\prime})$。
2. 问题：值迭代第 $k$ 轮后 $V_k$ 的物理解释是什么？
   • 答案：$V_k(s)$ = 从 $s$ 出发、至多 $k$ 步的最优期望折扣回报（之后截断）。每轮把视野延长一步；$k \to \infty$ 时 $V_k \to V^*$（几何收敛，误差 $O(\gamma^k)$）。因此值迭代天然可随时截断——实践中常用有限轮数近似。
3. 问题：策略迭代中为什么“策略改进”保证不使性能变差？
   • 答案：策略改进定理：对任意策略 $\pi$，定义 $\pi^{\prime}(s) = \arg\max_a Q^\pi(s,a)$，则 $V^{\pi^{\prime}}(s) \ge V^\pi(s)$ 对所有 $s$ 成立。直觉：$Q^\pi(s,\pi^{\prime}(s)) \ge Q^\pi(s,\pi(s)) = V^\pi(s)$——每状态选择当前最优动作，价值单调上升；等号仅在 $\pi$ 已最优时成立。