强化学习地基：从 Bellman 方程到 Q-learning

一

把问题先摆清楚。强化学习（reinforcement learning, RL）研究的是一个智能体（agent）在一个环境（environment）中反复决策的过程。每一步，智能体观察到当前的状态 $s$，选择一个动作 $a$，环境根据某种规则转移到新状态 $s’$，并返回一个奖励（reward）$r$。智能体的目标不是让某一步的奖励最大，而是让从现在到未来的累计奖励最大。

这个框架的标准形式叫马尔可夫决策过程（Markov Decision Process, MDP），它由五个部分组成：状态集合 $\mathcal{S}$、动作集合 $\mathcal{A}$、转移概率 $P(s’\mid s,a)$、奖励函数 $r(s,a)$、以及折扣因子 $\gamma\in[0,1)$。“马尔可夫”的意思是：下一个状态只依赖当前状态和当前动作，而与更早的历史无关——当前状态已经包含了做决策所需的全部信息1。

为什么需要折扣因子 $\gamma$？因为如果智能体永远活下去，累计奖励可能是无穷大，无法比较两个策略的好坏。引入 $\gamma$ 后，回报（return）被定义为从时刻 $t$ 起所有未来奖励的折扣和：

$$G_t = r_{t} + \gamma, r_{t+1} + \gamma^2 r_{t+2} + \cdots = \sum_{k=0}^{\infty} \gamma^k, r_{t+k}$$

$\gamma$ 越接近 1，智能体越看重长远；$\gamma$ 越小，越短视。这个看似技术性的选择，其实编码了一个深刻的态度：未来的奖励值多少现在的奖励。

智能体的行为由一个策略（policy）$\pi(a\mid s)$ 描述——在状态 $s$ 下选择各动作的概率。强化学习的全部任务，就是找到一个能让期望回报最大的策略 $\pi^*$。

二

直接搜索“最好的策略”是个天文数字级别的问题——策略的数量随状态和动作的数量指数爆炸。强化学习之所以可行，靠的是一个递归结构：价值函数。

定义状态 $s$ 在策略 $\pi$ 下的价值 $V_\pi(s)$ 为“从 $s$ 出发、按 $\pi$ 行动，能拿到的期望回报”：

$$V_\pi(s) = \mathbb{E}_\pi!\left[, G_t \mid s_t = s ,\right]$$

类似地，定义动作价值 $Q_\pi(s,a)$ 为“在 $s$ 先做动作 $a$、之后按 $\pi$ 行动的期望回报”。

这两个量的关键性质，是它们满足一个递归方程。把回报 $G_t = r_t + \gamma G_{t+1}$ 这条定义代进去，价值就能写成“当前一步的即时奖励，加上折扣后的下一状态价值”1：

$$V_\pi(s) = \sum_a \pi(a\mid s) \sum_{s’} P(s’\mid s,a),\big[, r(s,a) + \gamma, V_\pi(s’) ,\big]$$

这就是Bellman 期望方程。它把一个关于“无穷未来”的量，化简成了一个只涉及“当前与下一步”的自洽关系。这个递归结构，是 Richard Bellman 在 1950 年代研究动态规划（dynamic programming）时奠定的——他证明，很多看似需要枚举所有未来路径的最优化问题，都能拆解成一系列重叠的子问题，并通过这种递归关系高效求解1。

我们真正想要的是最优价值。最优策略下的价值 $V^*$ 满足Bellman 最优方程——它把“对所有动作求平均”换成了“取最好的那个动作”：

$$V^$$(s) = \max_a \sum_{s’} P(s’\mid s,a),\big[, r(s,a) + \gamma, V^(s’) ,\big]

对动作价值也一样：

$$Q^$$(s,a) = \sum_{s’} P(s’\mid s,a),\big[, r(s,a) + \gamma, \max_{a’} Q^(s’,a’) ,\big]

最优方程的意义在于：一旦你知道了 $Q^$Q∗，最优策略就是平凡的——在每个状态选 $Q^$ 最大的那个动作。问题从“搜索最好的策略”转化成了“求解这个不动点方程”。

三

如果环境的规则（转移概率 $P$ 和奖励 $r$）完全已知，求解 Bellman 最优方程有现成办法——值迭代（value iteration）：把方程当作一个更新规则，反复用右边算左边，价值估计会收敛到 $V^*$。这是动态规划的标准结果1。

但现实里，智能体往往不知道环境的规则。一个下棋的程序也许知道规则，但一个学走路的机器人不知道“这样发力会怎样”；一个玩陌生游戏的智能体不知道每个动作会把它带到哪里。它只能试——做一个动作，看环境给什么反馈，从经验里学。这就是强化学习区别于动态规划的地方：在不知道模型的情况下，仅凭采样到的经验逼近最优价值。

最早把这个想法系统化的，是 Richard Sutton 在 1988 年提出的时序差分（temporal-difference, TD）学习2。Sutton 的洞察非常漂亮：传统的预测学习，是等到最终结果出来，再用“预测值与真实结果之差”去修正。但 TD 不必等到最后——它用相邻两次预测之差来学习。

具体说，假设我在状态 $s$ 估计价值是 $V(s)$，走一步到 $s’$ 拿到奖励 $r$，那么 $r + \gamma V(s’)$ 是对同一个量 $V(s)$ 的一个更新的、更靠近真相的估计（因为它多观察了一步真实奖励）。两者之差

$$\delta = r + \gamma V(s’) - V(s)$$

叫TD 误差。它衡量“我原来的预测错了多少”。学习就是朝着消除这个误差的方向，微调 $V(s)$：

$$V(s) \leftarrow V(s) + \alpha,\delta$$

其中 $\alpha$ 是学习率。这个更新的妙处在于：它不需要知道环境模型（只用了实际采样到的 $r$ 和 $s’$），也不需要等到一局结束（走一步就能更新）。Sutton 还提出了一个推广 TD($\lambda$)，用一个叫 eligibility trace 的机制，在“只看一步”（TD(0)）和“看到结束”（蒙特卡洛）之间平滑插值2。这条 TD 误差，后来成了几乎所有现代强化学习算法的心跳。

四

TD 学的是状态价值 $V$，但 $V$ 不足以直接做决策——知道一个状态值多少钱，还不知道该往哪走（那需要环境模型告诉你每个动作会到哪个状态）。要绕开模型直接学“该怎么做”，得学动作价值 $Q$。

1989 年，剑桥的 Christopher Watkins 在博士论文里提出了Q-learning3。它把 TD 的思想用到了 $Q$ 上，而且做了一个关键的设计——更新目标里用的是 $\max$：

$$Q(s,a) \leftarrow Q(s,a) + \alpha,\big[, r + \gamma \max_{a’} Q(s’,a’) - Q(s,a) ,\big]$$

读懂这个式子，就读懂了价值型强化学习的核心。智能体在 $s$ 做了动作 $a$，观察到奖励 $r$ 和新状态 $s’$。它构造一个 TD 目标 $r + \gamma \max_{a’} Q(s’,a’)$——意思是“这一步实际拿到 $r$，加上从 $s’$ 出发最好能拿到的折扣价值”。然后把 $Q(s,a)$ 朝这个目标拉近一点。

这里的 $\max$ 是 Q-learning 被称为 off-policy（异策略） 的原因：无论智能体实际怎么走（它可能在随机探索），它学习的目标始终瞄准“如果之后都走最优会怎样”。换句话说，它可以一边用一个充满探索的、不那么聪明的策略去收集经验，一边学出那个最优策略。这种“行为策略”与“目标策略”的分离，是 Q-learning 极其实用的原因。

Watkins 与 Peter Dayan 在 1992 年给出了完整的收敛证明：只要所有状态-动作对被反复采样、价值用离散表格表示、学习率满足标准条件，Q-learning 就以概率 1 收敛到最优动作价值 $Q^*$3。这是强化学习史上第一批坚实的理论保证之一——它告诉人们，纯靠试错、不知道环境规则，也能可证明地学到最优。

五

把 Q-learning 跑出来，比公式更能说明问题。配套代码 code/12_q_learning_gridworld.py（纯 numpy）造了一个 4×4 的网格世界：起点在左上，目标（奖励 +1）在右下，右上角有个陷阱（奖励 −1），中间有两堵墙。智能体不知道任何规则——它甚至不知道哪里是陷阱、哪里是墙，只能撞上去、掉进去，从奖励里学。每走一步还有 −0.04 的小惩罚，逼它学会走捷径。

"""
第 12 章配套代码：表格型 Q-learning（gridworld）。
演示 Q-learning 更新 Q(s,a) <- Q + alpha*[r + gamma*max_a' Q(s',a') - Q]，
以及它如何在一个有墙、有陷阱、有目标的小网格里收敛出最优策略与价值。
Runnable with: numpy only.  python3 12_q_learning_gridworld.py
"""
import numpy as np

# 4x4 gridworld:
#  S . . .
#  . # . T   (# 墙不可进, T 陷阱 -1, G 目标 +1)
#  . # . .
#  . . . G
ROWS, COLS = 4, 4
START = (0, 0)
GOAL = (3, 3)
TRAP = (1, 3)
WALLS = {(1, 1), (2, 1)}
ACTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 上 下 左 右
ARROW = {0: "↑", 1: "↓", 2: "←", 3: "→"}


def step(s, a):
    """环境转移：返回 (下一状态, 奖励, 是否终止)。"""
    if s == GOAL:
        return s, 0.0, True
    if s == TRAP:
        return s, 0.0, True
    dr, dc = ACTIONS[a]
    nr, nc = s[0] + dr, s[1] + dc
    ns = (nr, nc)
    # 撞墙或越界则原地不动
    if nr < 0 or nr >= ROWS or nc < 0 or nc >= COLS or ns in WALLS:
        ns = s
    if ns == GOAL:
        return ns, 1.0, True
    if ns == TRAP:
        return ns, -1.0, True
    return ns, -0.04, False  # 每步小负奖励，鼓励走捷径


def q_learning(episodes=4000, alpha=0.1, gamma=0.95, eps=0.1, seed=0):
    rng = np.random.default_rng(seed)
    Q = np.zeros((ROWS, COLS, 4))
    returns = []
    for ep in range(episodes):
        s = START
        total, done, steps = 0.0, False, 0
        while not done and steps < 100:
            # epsilon-greedy 探索
            if rng.random() < eps:
                a = rng.integers(4)
            else:
                a = int(np.argmax(Q[s[0], s[1]]))
            ns, r, done = step(s, a)
            # Q-learning 更新（off-policy: 目标用 max_a' Q）
            best_next = 0.0 if done else np.max(Q[ns[0], ns[1]])
            td_target = r + gamma * best_next
            Q[s[0], s[1], a] += alpha * (td_target - Q[s[0], s[1], a])
            s = ns
            total += r
            steps += 1
        returns.append(total)
    return Q, returns


def show(Q, returns):
    V = np.max(Q, axis=2)
    print("=== Q-learning on 4x4 gridworld (S=起点 G=+1 T=-1 #=墙) ===")
    print("\n状态价值 V(s) = max_a Q(s,a):")
    for r in range(ROWS):
        row = []
        for c in range(COLS):
            if (r, c) in WALLS:
                row.append("  ###  ")
            else:
                row.append(f"{V[r, c]:+6.2f} ")
        print("  " + "".join(row))
    print("\n贪婪策略（每格最优动作箭头）:")
    for r in range(ROWS):
        row = []
        for c in range(COLS):
            if (r, c) in WALLS:
                row.append(" # ")
            elif (r, c) == GOAL:
                row.append(" G ")
            elif (r, c) == TRAP:
                row.append(" T ")
            else:
                row.append(f" {ARROW[int(np.argmax(Q[r, c]))]} ")
        print("  " + "".join(row))
    # 收敛：取末 200 局平均回报
    last = np.mean(returns[-200:])
    first = np.mean(returns[:200])
    print(f"\n平均回报: 前200局={first:+.3f} -> 末200局={last:+.3f}  (学到了避陷阱、走捷径)")


if __name__ == "__main__":
    Q, returns = q_learning()
    show(Q, returns)

用 $\varepsilon$-贪婪做探索（大部分时候选当前最优动作，偶尔随机乱走以发现新路），训练四千局后：

状态价值 V(s) = max_a Q(s,a):
   +0.59  +0.67  +0.74  +0.67
   +0.67   ###   +0.82  +0.00
   +0.74   ###   +0.91  +1.00
   +0.82  +0.91  +1.00  +0.00

贪婪策略（每格最优动作箭头）:
   →  →  ↓  ←
   ↓  #  ↓  T
   ↓  #  ↓  ↓
   →  →  →  G

几件事值得看。第一，价值呈现出清晰的梯度——离目标越近的格子价值越高，像一座从目标 G 向外缓降的山。这正是 Bellman 方程的几何含义：每个格子的价值，等于它能通向的最好邻居的折扣价值。第二，策略箭头形成了一条绕过墙、避开陷阱、流向目标的水流——智能体从没被告知“T 是陷阱”，它只是从一次次 −1 里学会了远离右上角。第三，平均回报从前 200 局的 +0.617 升到末 200 局的 +0.745，它确实在变好。

这个小程序里没有神经网络，$Q$ 就是一张 4×4×4 的表格。但它已经包含了强化学习最核心的循环：用 TD 误差，把试错得来的零散奖励，回传成一张关于“每个状态每个动作值多少”的地图。

六

表格型 Q-learning 有一个致命的天花板：它要为每个状态-动作对单独存一个数。网格世界有 16 个格子还行，但围棋有 $10^{170}$ 种局面，Atari 游戏的一帧画面有 $256^{100000}$ 种可能像素组合——表格根本存不下，更不可能每个都采样到。

这正是神经网络要登场的地方。如果把 $Q(s,a)$ 不再当作一张表，而是当作一个函数——输入状态、输出每个动作的价值——那就可以用一个神经网络去逼近它。相近的状态会被网络映射到相近的价值，于是智能体能把在一个局面学到的东西泛化到从没见过的局面。这就是从“表格型强化学习”到“深度强化学习”的跨越。

但这一步并不平凡。前面第二章讲反向传播时，监督学习的目标值是固定的标签；而在 Q-learning 里，更新目标 $r + \gamma\max_{a’}Q(s’,a’)$ 本身就含有正在被训练的那个 $Q$——你在追一个随自己移动的靶子。再加上强化学习采样到的相邻经验高度相关（连续几帧画面几乎一样），直接把神经网络塞进 Q-learning 会震荡、发散。整个 2000 年代，“用神经网络做 Q-learning”一直被认为是不稳定的。

这条暗线其实早有一个反例。1992 至 1995 年，IBM 的 Gerald Tesauro 用一个多层神经网络加 TD($\lambda$)，做出了 TD-Gammon——一个只靠和自己对弈、从零学起的西洋双陆棋程序，最终达到接近世界顶尖人类的水平，还下出了一些人类高手从未考虑、后来被证明更优的招法4。TD-Gammon 已经是“神经网络 + 时序差分 + 自我对弈”的完整配方，被后来的 DQN 和 AlphaGo 论文反复引为先声。但它当时被认为是双陆棋特有的幸运——这个游戏的骰子随机性恰好平滑了价值曲面，让神经网络好训。如何让这套配方在没有骰子、训练曲面崎岖的一般问题上也稳定工作，要再等将近二十年。

下一章讲的，就是 2013 到 2015 年 DeepMind 如何用两个朴素却关键的工程技巧——经验回放与目标网络——驯服了“神经网络 + Q-learning”，让一个智能体从原始像素学会打几十种 Atari 游戏，把这条沉睡了二十年的主线重新点燃。

配套的 manim 动画 assets/manim/ch12_q_learning.py（ValueDiffusion Scene）把 Bellman 更新的几何含义演出来：在一个 5×5 网格里，价值从带 +1 奖励的目标格出发，沿 Bellman 方程一圈圈“回灌”到邻近格子，绿色越来越深、红色标出陷阱；价值场成形后，每格朝价值最高的邻居指出一支箭头——贪婪策略就这样从价值里自然涌现出来。

本质

强化学习的全部出发点，是一个监督学习里没有的难题：没有人告诉你每一步的正确答案，你只能在很久之后收到一个总的回报，还得自己把功劳分摊回沿途每一个动作。Bellman 方程给出的解法是一个递归——一个状态的价值，等于即时奖励加上后继状态价值的折扣；价值不必一次算出，可以从有奖励的地方一圈圈向外回灌（动态规划），也可以在不知道环境规则时，用实际走出来的下一步去估计、边走边修正（时序差分）。Q-learning 的精妙在于它甚至不需要先有一个好策略：它直接学每个“状态-动作”对的最优价值，因此一边用着次优策略探索、一边却朝着最优价值收敛。它真正解决的，是“如何在延迟、稀疏、且依赖自身未来估计的反馈下，仍然学到该怎么行动”——这正是把“决策”变成可学习问题的地基。

参考文献

1. Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press. ISBN 9780262039246. MDP、回报 $G_t$、价值函数、Bellman 期望/最优方程、动态规划与值迭代的标准教科书出处；Bellman 1957《Dynamic Programming》与 Samuel 1959 跳棋程序的历史脉络见该书 §1.7、§3–4。MIT Press：https://mitpress.mit.edu/9780262039246/reinforcement-learning/ ；作者官方全文：http://incompleteideas.net/book/the-book-2nd.html

2. Sutton, R. S. (1988). Learning to Predict by the Methods of Temporal Differences. Machine Learning, 3, 9–44. TD 由相邻预测之差驱动；TD(λ) 用 eligibility trace 在 TD(0) 与蒙特卡洛之间插值。PDF：http://incompleteideas.net/papers/sutton-88.pdf ；Springer：https://link.springer.com/article/10.1007/BF00115009

3. Watkins, C. J. C. H., & Dayan, P. (1992). Q-learning. Machine Learning, 8, 279–292. Q-learning 由 Watkins 1989 博士论文提出、本文给出完整收敛证明：所有 (s,a) 反复采样、离散表示、学习率满足标准条件时以概率 1 收敛到 $Q^*$。PDF（Dayan 主页）：https://www.gatsby.ucl.ac.uk/~dayan/papers/cjch.pdf ；Springer：https://link.springer.com/article/10.1007/BF00992698

4. Tesauro, G. (1995). Temporal Difference Learning and TD-Gammon. Communications of the ACM, 38(3), 58–68. MLP + TD(λ) 纯自博弈（v2.1 训练 150 万局）达接近世界顶尖人类水平，下出新招；被 DQN/AlphaGo 引为早期 NN+RL 标志性成功。ACM：https://dl.acm.org/doi/10.1145/203330.203343 ；全文镜像：https://bkgm.com/articles/tesauro/tdl.html