近似方法 (Function Approximation)
在前面的章节中，我们一直使用表格（Tabular）方式来存储价值函数：一张Q表，或一张V表，每个状态（或状态-动作对）对应一个格子。这种方法在Grid World这种小任务中非常好用，但当我们走向真实世界时，表格方法会迅速崩溃。本章介绍Sutton & Barto第9-11章的核心内容：函数近似。
为什么需要函数近似
维度灾难 (Curse of Dimensionality)
考虑一个围棋棋盘：19x19的棋盘上每个位置有三种状态（黑、白、空），总状态数约为\(3^{361}\)，这是一个天文数字。即便是简单一些的Atari游戏，屏幕分辨率210x160，每个像素有256种颜色，状态空间也是\(256^{210 \times 160}\)。显然，我们不可能为每一个状态都单独维护一个Q值。
表格方法的核心假设是：每个状态都是独立的，状态A的经验完全不能帮助状态B。但在现实中，相似的状态往往具有相似的价值。比如在Atari的Pong游戏中，球在屏幕左上角和球在屏幕左上角偏右一个像素，这两个"不同的状态"对应的最优动作几乎完全相同。
泛化 (Generalization)
函数近似的核心优势在于泛化：当我们访问过一个状态并更新了它的价值后，与它相似的状态的价值估计也会随之改善。这是因为我们不再为每个状态单独存一个数字，而是用一个函数（带参数\(\mathbf{w}\)）来拟合整个价值函数：
其中\(\mathbf{w}\)是参数向量。通过调整\(\mathbf{w}\)，我们希望函数\(\hat{v}\)在所有状态上都尽可能接近真实的价值函数。
值函数近似
问题设定
我们的目标是找到一组参数\(\mathbf{w}\)，使得近似函数\(\hat{v}(s, \mathbf{w})\)尽可能接近真实价值\(v_\pi(s)\)。自然地，我们可以定义一个目标函数（均方误差）：
其中\(\mu(s)\)是状态分布，表示我们有多在乎每个状态上的误差。这个目标函数在强化学习中被称为Mean Squared Value Error。
用SGD（随机梯度下降）来最小化这个目标：
问题是，我们并不知道真实的\(v_\pi(S_t)\)。这正是不同算法的分歧所在：用什么来替代\(v_\pi(S_t)\)。
线性函数近似
最简单的函数近似形式是线性函数。我们先为每个状态\(s\)构造一个特征向量（feature vector）：
然后用参数\(\mathbf{w}\)与特征向量做内积：
这种形式下，梯度计算非常简单：
SGD更新公式变为：
线性函数近似的优势在于：它有良好的理论收敛保证，在on-policy预测问题中，线性TD(0)一定会收敛到一个全局最优解附近。它的劣势也很明显：表达能力有限，需要人工设计好的特征。
非线性函数近似 (Neural Networks)
当我们把\(\hat{v}(s, \mathbf{w})\)替换成一个神经网络时，就进入了深度强化学习的领域。神经网络可以自动从原始输入（如像素）中学习特征，不需要人工设计。
以DQN（Deep Q-Network）为例，它的核心思想就是用一个卷积神经网络来近似Q函数：
网络输入是游戏画面（状态\(s\)），输出是每个动作的Q值。DQN的成功离不开两个关键技巧：
- Experience Replay：将经验\((s, a, r, s')\)存入一个缓冲区，训练时随机抽样。这打破了样本之间的时序相关性，使得SGD的i.i.d.假设更加合理。
- Target Network：使用一个延迟更新的目标网络来计算TD Target，避免"追逐移动靶子"的不稳定问题。
非线性函数近似的理论保证远不如线性情况，但在实践中表现极为强大。
策略近似
参数化策略 (Parameterized Policy)
除了近似价值函数，我们也可以直接对策略进行参数化。使用参数\(\boldsymbol{\theta}\)定义一个参数化策略：
对于离散动作空间，最常见的参数化方式是Softmax策略：
其中\(h(s, a, \boldsymbol{\theta})\)是偏好函数（可以是线性函数\(\boldsymbol{\theta}^\top \mathbf{x}(s,a)\)或神经网络）。
对于连续动作空间（如机器人控制），常用高斯策略：
其中均值\(\mu\)和标准差\(\sigma\)都是状态的函数，由参数\(\boldsymbol{\theta}\)控制。
策略近似与值函数近似的关系是互补的：在Actor-Critic框架中，两者会同时使用，这在策略梯度一章中有更详细的讨论。
预测问题 (Prediction)
预测问题的目标是：给定一个策略\(\pi\)，学习该策略的价值函数\(v_\pi\)。在函数近似下，这意味着调整参数\(\mathbf{w}\)使得\(\hat{v}(s, \mathbf{w}) \approx v_\pi(s)\)。
梯度蒙特卡洛 (Gradient MC)
最直接的方法是用MC采样的回报\(G_t\)来替代真实的\(v_\pi(S_t)\)：
由于\(G_t\)是\(v_\pi(S_t)\)的无偏估计（\(\mathbb{E}[G_t | S_t = s] = v_\pi(s)\)），所以这个更新方向在期望上就是真实梯度的方向。因此，Gradient MC是一个真正的梯度方法，在一般条件下可以保证收敛到一个局部最优解（线性情况下是全局最优）。
Gradient MC的缺点与MC方法一样：方差大、必须等到episode结束才能更新。
半梯度TD (Semi-gradient TD)
将TD Target \(R_{t+1} + \gamma \hat{v}(S_{t+1}, \mathbf{w}_t)\)作为\(v_\pi(S_t)\)的替代：
这个方法被称为半梯度（Semi-gradient），原因在于：TD Target本身也依赖于参数\(\mathbf{w}\)（通过\(\hat{v}(S_{t+1}, \mathbf{w}_t)\)），但我们在求梯度时没有对TD Target求导，只对\(\hat{v}(S_t, \mathbf{w}_t)\)求了导。换句话说，我们在计算梯度的时候，把bootstrapped target当作了一个常数，忽略了它对\(\mathbf{w}\)的依赖。
为什么要这样做？如果我们对TD Target也求导，就会得到一个更复杂的更新规则（称为residual gradient方法），实际效果反而不好。半梯度TD虽然不是真正的梯度下降，但在线性函数近似下，on-policy的半梯度TD(0)被证明是收敛的。
直观对比：
| 方法 | 用什么替代\(v_\pi(S_t)\) | 是否真梯度 | 是否需要完整episode |
|---|---|---|---|
| Gradient MC | \(G_t\)（真实回报） | 是 | 是 |
| Semi-gradient TD(0) | \(R_{t+1} + \gamma \hat{v}(S_{t+1}, \mathbf{w})\) | 否 | 否 |
函数近似中的收敛性
函数近似引入了表格方法中不存在的收敛性问题。特别重要的是致命三要素（Deadly Triad）：
当以下三个因素同时出现时，学习算法可能发散（参数\(\mathbf{w}\)趋向无穷大）：
- 函数近似 (Function Approximation)：用参数化函数代替表格
- 自举 (Bootstrapping)：用估计值来更新估计值（如TD方法）
- 离策略学习 (Off-policy Learning)：用行为策略\(b\)的数据来学习目标策略\(\pi\)的价值
这三个因素中，任意去掉一个，都可以保证收敛：
- 去掉函数近似（用表格）：Tabular Q-learning收敛
- 去掉Bootstrapping（用MC）：Gradient MC收敛
- 去掉Off-policy（用on-policy）：Semi-gradient TD(0) on-policy收敛
这就解释了为什么DQN需要那么多技巧（Experience Replay、Target Network、梯度裁剪等）才能稳定训练——DQN恰好同时具备了三个致命因素。
控制问题 (Control)
控制问题的目标是直接学习最优策略。在函数近似下，我们用\(\hat{q}(s, a, \mathbf{w})\)来近似最优动作价值函数\(q_*(s, a)\)。
半梯度Sarsa (Episodic Semi-gradient Sarsa)
将Semi-gradient TD(0)从预测推广到控制：使用\(\hat{q}\)代替\(\hat{v}\)，用SARSA的更新方式：
其中\(A_{t+1}\)是根据当前策略（通常是\(\epsilon\)-greedy on \(\hat{q}\)）实际选取的动作。这是一个on-policy方法。
算法流程：
初始化参数向量 w
对每个episode:
初始化状态 S，根据 epsilon-greedy 选择动作 A
对每一步:
执行 A，观察 R, S'
如果 S' 是终止状态:
w <- w + alpha * [R - q_hat(S, A, w)] * grad q_hat(S, A, w)
退出循环
根据 epsilon-greedy 选择 A'
w <- w + alpha * [R + gamma * q_hat(S', A', w) - q_hat(S, A, w)] * grad q_hat(S, A, w)
S <- S', A <- A'
深度Q网络的雏形
从Semi-gradient Sarsa到DQN的演变：
- 将\(\hat{q}\)从线性函数换成神经网络
- 从on-policy（SARSA）换成off-policy（Q-learning），即用\(\max_{a'} \hat{q}(S', a', \mathbf{w})\)替代\(\hat{q}(S', A', \mathbf{w})\)
- 加入Experience Replay和Target Network来对抗Deadly Triad
DQN的TD Target为：
其中\(\mathbf{w}^{-}\)是Target Network的参数，每隔若干步才从主网络\(\mathbf{w}\)复制过来。这实质上是把一个快速移动的目标变成一个相对静止的目标，从而稳定训练。
特征构造
在线性函数近似中，特征向量\(\mathbf{x}(s)\)的设计至关重要。好的特征可以让线性方法达到非线性方法的效果；差的特征则会让学习变得困难甚至不可能。
多项式特征
对于一个连续状态\(s = (s_1, s_2)\)，多项式特征就是用状态变量的各种幂次组合来构造特征向量。例如二次多项式：
优点是简单直观，缺点是特征数量随阶数和维度指数增长，高维空间中不实用。
傅里叶特征
用傅里叶基函数作为特征：
其中\(\mathbf{c}_i\)是频率向量。傅里叶特征可以表达价值函数中的周期性模式和全局结构。在许多基准任务上，傅里叶特征的表现优于多项式特征，而且不需要太多人工调参。
Tile Coding (瓦片编码)
Tile Coding是实践中最常用的线性特征构造方法之一。它的思路很直观：
- 将连续的状态空间用多个重叠的网格（tiling） 覆盖
- 每个tiling把状态空间划分成若干瓦片（tile）
- 对于一个给定状态，在每个tiling中，它恰好落在一个tile里
- 特征向量就是一个二值向量：被激活的tile对应的分量为1，其余为0
比如一个二维状态空间\([0,1] \times [0,1]\)，我们用8个tiling覆盖，每个tiling有\(4 \times 4 = 16\)个tile，那么特征向量的维度为\(8 \times 16 = 128\)，其中恰好有8个分量为1。
Tile Coding的优势：
- 计算高效：特征向量是稀疏的二值向量，内积计算等价于查表求和
- 分辨率可控：通过调整tile的大小来控制泛化的程度
- 多分辨率：不同的tiling可以用不同的tile大小，实现粗细结合
Tile Coding的示意：
Tiling 1: Tiling 2 (偏移):
+---+---+---+ +---+---+---+
| | | | | | | |
+---+---+---+ +---+---+---+
| | * | | | * | | |
+---+---+---+ +---+---+---+
状态 * 在Tiling 1中激活第5号tile
状态 * 在Tiling 2中激活第4号tile
特征向量中只有第5号和第4号位置为1
在线性函数近似下：
即价值估计等于所有被激活的tile对应的权重之和。更新时只需要调整被激活的那几个\(w_i\)，计算量很小。
总结
函数近似是从Tabular RL走向现代深度强化学习的桥梁。核心思想可以概括为以下几点：
| 概念 | 表格方法 | 函数近似 |
|---|---|---|
| 存储方式 | 每个状态一个格子 | 参数化函数\(\hat{v}(s, \mathbf{w})\) |
| 泛化能力 | 无（状态间独立） | 有（相似状态共享参数） |
| 可扩展性 | 仅限小状态空间 | 适用于大规模/连续空间 |
| 收敛保证 | 较强 | 需要额外条件 |
| 更新方式 | 直接修改表格 | SGD调整参数\(\mathbf{w}\) |
从本章的视角来看，之前学过的所有算法（MC、TD(0)、SARSA、Q-learning）都可以被看作函数近似的特例——只不过它们用的"函数"是一张巨大的查找表。而DQN、PPO、SAC等现代方法，则是在函数近似的框架下，用神经网络作为近似器，配合各种技巧来克服收敛性问题。