Lecture 15: Model-based RL. Value Function Approximation

目录 · ← l14 · l16 →

Lecture 15: Model-based RL. Value Function Approximation

概述

上一讲假设转移概率 $P_{sa}$ 已知（动态规划）。现实往往模型未知。本讲给出两条路线：模型学习（从数据估计 $P_{sa}$ 再套用 DP）与无模型学习（直接学习价值函数/策略）。重点算法：Q-learning（无模型、off-policy 的价值迭代近似）、拟合值迭代 (Fitted Value Iteration)（价值函数的函数近似，处理连续状态），以及 REINFORCE（策略梯度，处理连续/随机动作）。

核心概念与数学直觉

两条路线总览： | 路线 | 思想 | 代表算法 | |—|—|—| | Model-based | 先学模型（$\hat{P}_{sa}$、$\hat{R}$），再在模型上做规划 | 估计转移概率 + 值迭代；模拟/规划 | | Model-free | 跳过模型，直接从经验学价值/策略 | Q-learning、SARSA、策略梯度 |
- 直觉：Model-based 像“先画地图再找路”；Model-free 像“不画地图，边走边记哪条路好”。
Q-learning（无模型值迭代）： $Q(s, a) := Q(s, a) + \alpha \left[ R(s) + \gamma \max_{a'} Q(s', a') - Q(s, a) \right]$
- $\alpha$：学习率（步长）。
- $s^{\prime}$：执行 $a$ 后实际观察到的下一状态（不需要 $P_{sa}$！）。
- $R(s) + \gamma \max_{a^{\prime}} Q(s^{\prime},a^{\prime})$：TD 目标 (temporal difference target)——用一步经验 + 当前估计近似贝尔曼目标。
- $R(s) + \gamma \max_{a^{\prime}} Q(s^{\prime},a^{\prime}) - Q(s,a)$：TD 误差——预测与目标的差距。
- off-policy 特性：更新用的 $\max_{a^{\prime}} Q(s^{\prime},a^{\prime})$ 与实际采取的动作无关——可以用任意行为策略收集经验（如 $\epsilon$-greedy），同时学习最优策略。
- 收敛条件：每个 $(s,a)$ 被无限次访问 + 学习率满足 Robbins-Monro 条件（$\sum \alpha_t = \infty, \sum \alpha_t^2 < \infty$）。
连续状态：价值函数近似 (Value Function Approximation)：状态空间连续/巨大时无法查表。用参数化函数 $V_\theta(s)$（如线性、神经网络）近似 $V(s)$。
- 拟合值迭代 (Fitted Value Iteration)：每轮用当前 $\hat{V}$ 构造回归目标 $y^{(i)} = R(s^{(i)}) + \gamma \max_a \hat{P}{sa}$ 的期望（或从经验估计），再监督学习拟合 $V\theta \approx y$——把 DP 变成回归问题。
- 线性函数近似：$V_\theta(s) = \theta^T \phi(s)$（$\phi$ 为状态特征）——最小二乘拟合目标值；配 Q-learning 即线性 Q-learning（如 DQN 的线性前身）。
- 深度 Q 网络 (DQN)：神经网络 $Q_\theta$ + 经验回放 + 目标网络稳定训练——AlphaGo、Atari 的核心组件（本课以概念为主）。
策略搜索与 REINFORCE：
- 思想：不再学价值，直接参数化策略 $\pi_\theta$（如“状态 → 动作分布”的神经网络），用梯度上升最大化期望回报。
- 问题：期望回报对 $\theta$ 的梯度涉及未知环境——似然比技巧 (likelihood ratio trick)： $\nabla_\theta E_\tau[R(\tau)] = E_\tau\left[ R(\tau) \nabla_\theta \log p_\theta(\tau) \right]$ ，其中 $p_\theta(\tau) = p(s_0)\prod_t \pi_\theta(a_t\vert s_t) p(s_{t+1}\vert s_t,a_t)$——环境动力学 $p(s^{\prime}\vert s,a)$ 不依赖 $\theta$，梯度中自动消失！
- REINFORCE 更新： $\theta := \theta + \alpha \sum_{t} \nabla_\theta \log \pi_\theta(a_t \| s_t) \cdot R_t$ （$R_t$ 为从 $t$ 起的折扣回报）
  - 直觉：采样若干轨迹；回报高的轨迹上的动作概率被推高（“好轨迹的动作更可能被重复”），回报低的被压低。这是“试错 + 强化”的直接实现。
- 方差问题：采样回报方差大 → 用基线 (baseline)（减均值）与Actor-Critic（用价值函数代替整条回报）降方差。

算法伪代码与逻辑解说：Q-learning（表格版）

伪代码

输入:
    - 环境（可交互采样）: 状态 s，动作 a，奖励 r，下一状态 s'
    - 学习率 alpha，折扣 gamma，探索率 epsilon，回合数 N

输出:
    - Q 表 Q(s, a)

1. 初始化 Q(s, a) = 0（所有 s, a）
2. 对回合 ep = 1..N:
    2.1 重置环境，得到初始状态 s
    2.2 循环直到回合结束:
        2.2.1 选动作: 以概率 epsilon 随机探索，否则 a = argmax_a' Q(s, a')  // ε-greedy
        2.2.2 执行 a，观察 r 与 s'
        2.2.3 更新: Q(s, a) += alpha * (r + gamma * max_a' Q(s', a') - Q(s, a))
        2.2.4 s = s'
3. 返回 Q

【算法逻辑解说】

Step 2.2.1 ε-greedy 探索：以 $\epsilon$ 概率随机动作保证“每个 $(s,a)$ 都被访问”——Q-learning 收敛的前提是充分探索。$\epsilon$ 常随时间衰减（先探索后利用）。
Step 2.2.3 TD 更新：不需要模型——$s^{\prime}$ 来自真实环境观察。$\max_{a^{\prime}} Q(s^{\prime},a^{\prime})$ 使用当前最优估计（自举，bootstrap）：用估计更新估计，这正是 TD 方法“从猜测中学习”的本质。
off-policy：行为策略（ε-greedy）与目标策略（贪心）不同——Q 最终逼近贪心最优策略的 $Q^*$。
对比蒙特卡洛：MC 用整条轨迹的回报更新（高方差、无偏）；TD 用一步更新（低方差、有偏）。Q-learning 是 TD 家族成员。
收敛：理论上在表格 + 无限探索 + 合适 $\alpha$ 下收敛到 $Q^*$；实践中配合函数近似（DQN 等）处理大规模状态。

算法伪代码与逻辑解说：REINFORCE（策略梯度）

伪代码

输入:
    - 参数化策略 π_θ(a|s)，学习率 alpha，回合数 N

输出:
    - 策略参数 θ

1. 初始化 θ
2. 对回合 ep = 1..N:
    2.1 采样一条轨迹: τ = (s_0, a_0, r_1, s_1, a_1, r_2, ..., s_T)
        （每一步 a_t ~ π_θ(·|s_t)）
    2.2 计算每步折扣回报: R_t = Σ_{k=t..T} γ^(k-t) r_k
    2.3 累计梯度: g = Σ_t R_t * ∇_θ log π_θ(a_t | s_t)
    2.4 更新: θ = θ + alpha * g          // 梯度上升（最大化期望回报）
3. 返回 θ

【算法逻辑解说】

Step 2.1 采样：策略是随机的（输出动作分布），从分布中采样动作——探索内建于策略。
Step 2.2 回报计算：$R_t$ 是“事后诸葛亮”——用整条轨迹的真实回报评价动作。
Step 2.3 核心公式：$\nabla_\theta \log \pi_\theta(a_t\vert s_t) \cdot R_t$——动作概率的梯度 × 回报。回报正 → 概率上升方向；负 → 下降方向。直觉：像“体罚/奖赏”调整每个动作的倾向。似然比技巧使环境动力学（未知）从梯度中消失——只需知道自己的策略。
Step 2.4：梯度上升（不是下降——目标是最大化回报）。可用基线减方差：$\theta := \theta + \alpha \sum_t \nabla \log \pi_\theta \cdot (R_t - b)$。
高方差警告：整条轨迹回报方差大——需要大量采样；Actor-Critic 用价值函数做基线/替代回报，是现代（PPO/A2C）的基础。

关键要点

模型未知时：Model-based（先学模型）或 Model-free（直接学价值/策略）。
Q-learning：无模型 TD 更新，off-policy，$\epsilon$-greedy 保证探索。
连续状态 → 价值函数近似（拟合值迭代、DQN）——把 RL 转成回归问题。
REINFORCE：策略梯度 + 似然比技巧，直接优化策略；高方差需基线/Actor-Critic。
探索-利用权衡是 RL 的核心张力：$\epsilon$ 衰减、策略随机性是常用机制。

常见误区与注意事项

混淆 on-policy 与 off-policy：Q-learning 是 off-policy（可复用历史/他人经验）；SARSA 与策略梯度是 on-policy（数据必须来自当前策略）。用错会学到错误目标。
Q-learning 更新漏掉 $\gamma$ 或 max：TD 目标 $r + \gamma \max_{a^{\prime}} Q(s^{\prime},a^{\prime})$ 三项缺一不可；漏 $\max$ 退化为 SARSA 的目标。
$\epsilon$ 恒为 0（纯利用）：从不探索 → 学到的 $Q$ 只反映已访问路径，可能远非最优。
REINFORCE 忘记基线：裸 REINFORCE 方差巨大，训练不稳定；基线（如状态价值）几乎总是必要。
奖励设计不合理：奖励稀疏（只在终点给）→ 学习极慢；奖励过于密集/易被钻空子 → 学到投机行为（reward hacking）。奖励设计是 RL 工程的核心。
函数近似 + 自举的稳定性：Q 网络 + TD 自举 + 非线性近似三者叠加易发散——经验回放与目标网络（DQN 技巧）缓解。

思考题

问题：Q-learning 为什么被称为 off-policy？SARSA 的更新是什么、为什么是 on-policy？
- 答案：Q-learning 更新用 $\max_{a^{\prime}} Q(s^{\prime},a^{\prime})$（目标策略是贪心），与行为策略（如 ε-greedy）无关 ⇒ off-policy。SARSA 更新用 $Q(s^{\prime}, a^{\prime})$（$a^{\prime}$ 是行为策略实际要执行的动作）⇒ 学的是当前行为策略的价值 ⇒ on-policy。on-policy 更稳（学啥用啥），off-policy 更省数据（可复用）。
问题：拟合值迭代如何把“无模型 + 连续状态”问题转化为回归问题？
- 答案：采样大量 $(s^{(i)}, a^{(i)}, r^{(i)}, s^{\prime}^{(i)})$ 经验；构造回归目标 $y^{(i)} = r^{(i)} + \gamma \max_a \hat{Q}(s^{\prime}^{(i)}, a)$（用当前近似 $\hat{Q}$ 计算）；用监督学习（最小二乘/神经网络）拟合 $Q_\theta \approx y$；重复多轮。价值近似把 RL 变成“不断构造数据集 + 拟合”的循环——这是 DQN 的骨架。
问题：推导 REINFORCE 中 $\nabla_\theta \log p_\theta(\tau)$ 为何不含环境动力学。
- 答案：$p_\theta(\tau) = p(s_0)\prod_t \pi_\theta(a_t\vert s_t) p(s_{t+1}\vert s_t,a_t)$。取 $\log$ 后对 $\theta$ 求导：$p(s_0)$ 与 $p(s_{t+1}\vert s_t,a_t)$ 均不含 $\theta$，导数全为 0——只剩 $\sum_t \nabla_\theta \log \pi_\theta(a_t\vert s_t)$。这就是“策略梯度只需知道自己的策略、无需环境模型”的数学依据。

Share on

Bluesky Facebook LinkedIn Mastodon X (formerly Twitter)

Runguo Li

Lecture 15: Model-based RL. Value Function Approximation

概述

核心概念与数学直觉

算法伪代码与逻辑解说：Q-learning（表格版）

算法伪代码与逻辑解说：REINFORCE（策略梯度）

关键要点

常见误区与注意事项

思考题

Share on