第10章：价值函数的近似（Function Approximation）

一、导读

1.1 本章学习目标

第10章将 tabular 方法推广到大规模状态空间。当状态数量太大（如围棋的 $10^{170}$ 个状态）时，无法为每个状态维护单独的价值估计。函数近似方法用参数化的函数 $V(s; \mathbf{w})$ 来表示价值函数，通过调整参数 $\mathbf{w}$ 来拟合真实价值。

本章核心学习目标：

理解函数近似的动机：为什么 tabular 方法不够用
掌握梯度下降方法：用 SGD 最小化价值估计的均方误差
理解半梯度方法：处理自举带来的偏差
掌握线性特征近似：最常用的函数近似形式
了解深度强化学习的基础：用神经网络作为函数近似器

1.2 为什么本章如此重要

函数近似是连接经典强化学习和现代深度强化学习的桥梁。DQN 用神经网络近似 Q 函数，AlphaGo 用神经网络近似价值函数和策略——它们都是本章思想的直接应用。

1.3 核心问题引导

为什么不能简单地将 tabular 方法视为函数近似的特例？

梯度 MC 和梯度 TD 有什么区别？为什么梯度 TD 更复杂？

半梯度方法为什么叫"半"梯度？它与完整梯度的区别是什么？

函数近似下，off-policy 学习为什么可能发散？如何解决？

二、核心概念详解

10.1 从 Tabular 到函数近似

在 tabular 方法中，$V(s)$ 是一个查找表。在函数近似中，$V(s) \approx \hat{V}(s; \mathbf{w})$，其中 $\mathbf{w}$ 是参数向量。

目标是最小化均方价值误差（MSVE）：

$$\overline{VE}(\mathbf{w}) = \sum_{s} \mu(s) [v_\pi(s) - \hat{V}(s; \mathbf{w})]^2$$

其中 $\mu(s)$ 是状态分布。

python

import numpy as np

class LinearApproximator:
    def __init__(self, n_features):
        self.w = np.zeros(n_features)

    def predict(self, x):
        return np.dot(self.w, x)

    def update(self, x, target, alpha=0.01):
        prediction = self.predict(x)
        error = target - prediction
        self.w += alpha * error * x
        return error

def feature_demo():
    np.random.seed(42)
    n_features = 5
    approx = LinearApproximator(n_features)

    true_w = np.array([1, 2, -1, 0.5, 3])
    for i in range(1000):
        x = np.random.randn(n_features)
        target = np.dot(true_w, x) + np.random.randn() * 0.1
        error = approx.update(x, target, alpha=0.01)

    print(f"True weights: {true_w}")
    print(f"Learned weights: {np.round(approx.w, 2)}")
    print(f"Final error: {abs(error):.4f}")

feature_demo()

10.2 梯度蒙特卡洛方法

梯度 MC 使用 MC 回报作为目标，通过梯度下降更新参数：

$$\mathbf{w}_{t+1} = \mathbf{w}_t + \alpha [G_t - \hat{V}(S_t; \mathbf{w}_t)] \nabla_\mathbf{w} \hat{V}(S_t; \mathbf{w}_t)$$

python

def gradient_mc(env_factory, feature_fn, n_episodes=500, alpha=0.01, gamma=0.99):
    env = env_factory()
    n_features = len(feature_fn(env.reset()))
    w = np.zeros(n_features)

    for ep in range(n_episodes):
        state = env.reset()
        episode = []
        done = False

        while not done:
            action = np.random.randint(4)
            next_state, reward, done = env.step(action)
            episode.append((state, reward))
            state = next_state

        G = 0
        for t in range(len(episode) - 1, -1, -1):
            s, r = episode[t]
            G = gamma * G + r
            x = feature_fn(s)
            v_hat = np.dot(w, x)
            w += alpha * (G - v_hat) * x

    return w

class SimpleGrid:
    def __init__(self, size=5):
        self.size = size
        self.goal = (size-1, size-1)
        self.actions = [(-1,0),(1,0),(0,-1),(0,1)]

    def reset(self):
        self.state = (0, 0)
        return self.state

    def step(self, action):
        dr, dc = self.actions[action]
        r, c = self.state
        nr, nc = max(0,min(self.size-1,r+dr)), max(0,min(self.size-1,c+dc))
        self.state = (nr, nc)
        reward = 1.0 if self.state == self.goal else 0.0
        done = self.state == self.goal
        return self.state, reward, done

def tile_coding(state, size=5, n_tilings=4):
    features = np.zeros(size * size * n_tilings)
    for t in range(n_tilings):
        offset = t * 0.25
        r_idx = min(size-1, int((state[0] + offset) * size / 5))
        c_idx = min(size-1, int((state[1] + offset) * size / 5))
        idx = t * size * size + r_idx * size + c_idx
        features[idx] = 1.0
    return features

w = gradient_mc(SimpleGrid, lambda s: tile_coding(s), n_episodes=200)
print(f"Gradient MC: learned {np.sum(w > 0.01)} active features out of {len(w)}")

10.3 半梯度 TD(0)

半梯度 TD(0) 使用 TD 目标 $R_{t+1} + \gamma \hat{V}(S_{t+1}; \mathbf{w})$ 替代 MC 回报：

$$\mathbf{w}_{t+1} = \mathbf{w}_t + \alpha [R_{t+1} + \gamma \hat{V}(S_{t+1}; \mathbf{w}_t) - \hat{V}(S_t; \mathbf{w}_t)] \nabla_\mathbf{w} \hat{V}(S_t; \mathbf{w}_t)$$

称为"半梯度"是因为它没有对 $S_{t+1}$ 的依赖求导（忽略了目标对 $\mathbf{w}$ 的依赖）。

python

def semi_gradient_td0(env_factory, feature_fn, n_episodes=500, alpha=0.01, gamma=0.99):
    env = env_factory()
    n_features = len(feature_fn(env.reset()))
    w = np.zeros(n_features)

    for ep in range(n_episodes):
        state = env.reset()
        done = False

        while not done:
            action = np.random.randint(4)
            next_state, reward, done = env.step(action)
            x = feature_fn(state)
            x_next = feature_fn(next_state)
            v_hat = np.dot(w, x)
            v_next = 0 if done else np.dot(w, x_next)
            td_error = reward + gamma * v_next - v_hat
            w += alpha * td_error * x
            state = next_state

    return w

w_td = semi_gradient_td0(SimpleGrid, lambda s: tile_coding(s), n_episodes=200)
print(f"Semi-gradient TD(0): learned {np.sum(w_td > 0.01)} active features")

10.4 线性方法

线性函数近似是最常用的形式：

$$\hat{V}(s; \mathbf{w}) = \mathbf{w}^T \mathbf{x}(s) = \sum_i w_i x_i(s)$$

其中 $\mathbf{x}(s)$ 是状态 $s$ 的特征向量。常见的特征包括：

多项式特征：$x_i(s) = s^i$
傅里叶特征：$x_i(s) = \cos(2\pi k s)$
Tile coding：多个重叠的粗糙网格
径向基函数（RBF）：$x_i(s) = \exp(-||s - c_i||^2 / 2\sigma^2)$

10.5 Off-policy 函数近似的发散问题

在函数近似下，off-policy + bootstrapping 可能导致参数发散。经典的 Baird's counterexample 展示了这个问题。

解决方案包括：

GTD（Gradient TD）：使用修正的目标函数
TDC（TD with Corrections）：引入辅助参数来修正梯度
Emphatic TD：对重要性采样比率进行修正

三、实战案例

3.1 案例：Mountain Car 上的函数近似

python

class MountainCar:
    def __init__(self):
        self.position = -0.5
        self.velocity = 0.0

    def reset(self):
        self.position = -0.5 + np.random.uniform(-0.1, 0.1)
        self.velocity = 0
        return (self.position, self.velocity)

    def step(self, action):
        self.velocity += 0.001 * (action - 1) - 0.0025 * np.cos(3 * self.position)
        self.velocity = np.clip(self.velocity, -0.07, 0.07)
        self.position += self.velocity
        self.position = np.clip(self.position, -1.2, 0.6)

        if self.position <= -1.2:
            self.velocity = 0

        reward = -1.0
        done = self.position >= 0.5
        return (self.position, self.velocity), reward, done

def rbf_features(state, n_rbf=10):
    pos, vel = state
    features = []
    for i in range(n_rbf):
        for j in range(n_rbf):
            c_pos = -1.2 + (0.6 - (-1.2)) * i / (n_rbf - 1)
            c_vel = -0.07 + 0.14 * j / (n_rbf - 1)
            sigma = 0.2
            f = np.exp(-((pos - c_pos)**2 + (vel - c_vel)**2) / (2 * sigma**2))
            features.append(f)
    return np.array(features)

def sarsa_lambda_mountain_car(n_episodes=100, alpha=0.001, gamma=0.99, lam=0.9, epsilon=0.1):
    env = MountainCar()
    n_features = 100
    w = np.zeros(n_features)

    for ep in range(n_episodes):
        state = env.reset()
        x = rbf_features(state)
        action = np.argmax(np.random.randn(3) + w[:3]) if np.random.random() < epsilon else np.random.randint(3)

        done = False
        steps = 0
        while not done and steps < 200:
            next_state, reward, done = env.step(action)
            x_next = rbf_features(next_state)

            if np.random.random() < epsilon:
                next_action = np.random.randint(3)
            else:
                next_action = np.argmax([np.dot(w, x_next) for _ in range(3)])

            v_hat = np.dot(w, x)
            v_next = np.dot(w, x_next) if not done else 0
            td_error = reward + gamma * v_next - v_hat

            w += alpha * td_error * x
            x = x_next
            action = next_action
            state = next_state
            steps += 1

        if ep % 20 == 0:
            print(f"Episode {ep}: steps = {steps}")

    return w

print("Mountain Car with function approximation:")
w = sarsa_lambda_mountain_car(n_episodes=50)

四、本章小结

函数近似：用参数化函数表示价值函数，适用于大规模状态空间

梯度 MC：无偏但高方差

半梯度 TD：有偏但低方差，是实际中最常用的方法

线性方法：最常用，特征设计是关键

Off-policy 发散：函数近似下 off-policy 学习可能不稳定

五、思考与练习

思考题

为什么半梯度 TD 在函数近似下可能不收敛？

特征设计对函数近似的性能有多大影响？如何设计好的特征？

神经网络作为函数近似器有什么优势和劣势？

编程练习

在 Mountain Car 上比较不同特征（RBF、tile coding）的性能

实现线性 Q-learning 并在 CartPole 上测试

观察半梯度 Q-learning 在不同步长下的稳定性