06 - 理论基础统一框架¶

学习时间: 4-5小时 重要性: ⭐⭐⭐⭐⭐ 从算子理论视角统一理解RL核心算法 前置知识: 贝尔曼方程、蒙特卡洛方法、泛函分析基础

🎯 学习目标¶

完成本章后，你将能够： - 从算子理论视角理解DP、MC、TD的统一数学框架 - 掌握n-step方法的统一视角和误差分析 - 理解TD(λ)的数学基础（前向/后向视角、资格迹） - 掌握不同算法的偏差-方差权衡分析 - 理解随机逼近理论在RL中的应用 - 能够根据问题特性选择合适的学习方法

1. 算子理论框架¶

1.1 贝尔曼算子回顾¶

贝尔曼期望算子 \(T^\pi\)：

\[(T^\pi V)(s) = \sum_a \pi(a|s) \sum_{s', r} p(s', r|s, a)[r + \gamma V(s')]\]

贝尔曼最优算子 \(T^*\)：

\[(T^* V)(s) = \max_a \sum_{s', r} p(s', r|s, a)[r + \gamma V(s')]\]

关键性质： - \(T^\pi\) 是 \(\gamma\)-压缩映射 - \(T^*\) 是 \(\gamma\)-压缩映射 - \(V^\pi\) 是 \(T^\pi\) 的唯一不动点 - \(V^*\) 是 \(T^*\) 的唯一不动点

1.2 算子视角下的学习方法¶

动态规划：直接应用贝尔曼算子

\[V_{k+1} = T^\pi V_k\]

蒙特卡洛：采样估计算子应用

\[\hat{V}(s) = \frac{1}{n} \sum_{i=1}^n G^{(i)}(s) \approx (T^\pi V)(s) \text{ 的采样估计}\]

时序差分：自举 + 采样

\[V(s) \leftarrow V(s) + \alpha[R + \gamma V(s') - V(s)]\]

这相当于：

\[V \approx T^\pi V \text{ （近似不动点迭代）}\]

1.3 统一的更新形式¶

所有RL算法都可以写成：

\[V_{k+1} = V_k + \alpha_k [\hat{T}V_k - V_k]\]

其中 \(\hat{T}\) 是贝尔曼算子的随机估计。

算法	\(\hat{T}\) 的形式	偏差	方差
DP	\(T^\pi\)（精确）	0	0
MC	采样回报 \(G\)	0	高
TD(0)	\(R + \gamma V(s')\)	>0	低
n-step TD	\(G_{t:t+n}\)	>0（小）	中

2. n-step方法：MC与TD的桥梁¶

2.1 n-step回报定义¶

n-step回报：

\[G_{t:t+n} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n V(S_{t+n})\]

特殊情况： - \(n=1\)：TD(0)目标 \(R_{t+1} + \gamma V(S_{t+1})\) - \(n=\infty\)（或直到终止）：MC目标 \(G_t\)

2.2 n-step TD的误差分析¶

截断误差：

\[\text{Bias}(G_{t:t+n}) = \mathbb{E}[G_{t:t+n} | S_t] - V^\pi(S_t) = \gamma^n \mathbb{E}[V(S_{t+n}) - V^\pi(S_{t+n}) | S_t]\]

方差：

\[\text{Var}(G_{t:t+n}) = \sum_{k=0}^{n-1} \gamma^{2k} \text{Var}(R_{t+k+1}) + \gamma^{2n} \text{Var}(V(S_{t+n}))\]

偏差-方差权衡： - \(n\) 小：偏差大（自举误差），方差小 - \(n\) 大：偏差小，方差大（累积奖励噪声）

2.3 最优n的选择¶

理论上，最优 \(n\) 取决于： - 奖励噪声水平 - 价值函数估计误差 - 折扣因子 \(\gamma\)

经验法则： - 高噪声环境：小 \(n\) - 价值估计准确：大 \(n\) - 长程依赖重要：大 \(n\)

2.4 代码实现：n-step方法¶

Python

import numpy as np
from collections import deque
from typing import Callable, Tuple

class NStepMethods:
    """n-step方法的统一实现"""

    def __init__(self, n_actions: int, gamma: float = 0.9):
        self.n_actions = n_actions
        self.gamma = gamma

    def n_step_td_prediction(self, env, policy, V: dict, n: int = 3,
                             alpha: float = 0.1, num_episodes: int = 1000) -> dict:
        """
        n-step TD预测

        参数:
            env: 环境
            policy: 策略
            V: 初始值函数
            n: 步数
            alpha: 学习率
            num_episodes: episode数量
        返回:
            V: 学习后的值函数
        """
        for episode in range(num_episodes):
            state, _ = env.reset()

            # 存储轨迹
            states = [state]
            rewards = [0]  # R_0 = 0

            T = float('inf')
            t = 0

            while True:
                if t < T:
                    # 执行动作
                    action = np.random.choice(self.n_actions, p=policy[state])
                    next_state, reward, terminated, truncated, _ = env.step(action)
                    done = terminated or truncated

                    states.append(next_state)
                    rewards.append(reward)

                    if done:
                        T = t + 1

                # 更新时间
                tau = t - n + 1

                if tau >= 0:
                    # 计算n-step回报
                    G = 0.0
                    for i in range(tau + 1, min(tau + n, T) + 1):
                        G += (self.gamma ** (i - tau - 1)) * rewards[i]

                    # 如果未终止，加上自举项
                    if tau + n < T:
                        G += (self.gamma ** n) * V.get(states[tau + n], 0.0)

                    # 更新
                    s_tau = states[tau]
                    V[s_tau] = V.get(s_tau, 0.0) + alpha * (G - V.get(s_tau, 0.0))

                if tau == T - 1:
                    break

                t += 1
                state = next_state

        return V

    def n_step_sarsa(self, env, Q: dict, n: int = 3, alpha: float = 0.1,
                     epsilon: float = 0.1, num_episodes: int = 1000) -> dict:
        """
        n-step SARSA（On-Policy控制）
        """
        for episode in range(num_episodes):
            state, _ = env.reset()

            # ε-贪婪选择动作
            if np.random.rand() < epsilon:
                action = np.random.randint(self.n_actions)
            else:
                action = np.argmax(Q.get(state, np.zeros(self.n_actions)))

            # 存储轨迹
            states = [state]
            actions = [action]
            rewards = [0]

            T = float('inf')
            t = 0

            while True:
                if t < T:
                    next_state, reward, terminated, truncated, _ = env.step(actions[t])
                    done = terminated or truncated

                    states.append(next_state)
                    rewards.append(reward)

                    if done:
                        T = t + 1
                    else:
                        # 选择下一个动作
                        if np.random.rand() < epsilon:
                            next_action = np.random.randint(self.n_actions)
                        else:
                            next_action = np.argmax(Q.get(next_state,
                                                          np.zeros(self.n_actions)))
                        actions.append(next_action)

                tau = t - n + 1

                if tau >= 0:
                    G = 0.0
                    for i in range(tau + 1, min(tau + n, T) + 1):
                        G += (self.gamma ** (i - tau - 1)) * rewards[i]

                    if tau + n < T:
                        s_next = states[tau + n]
                        a_next = actions[tau + n]
                        G += (self.gamma ** n) * Q.get((s_next, a_next), 0.0)

                    s_tau = states[tau]
                    a_tau = actions[tau]
                    sa_pair = (s_tau, a_tau)

                    Q[sa_pair] = Q.get(sa_pair, 0.0) + alpha * (G - Q.get(sa_pair, 0.0))

                if tau == T - 1:
                    break

                t += 1

        return Q

3. TD(λ)：前向与后向视角¶

3.1 λ-回报的前向视角¶

λ-回报（前向视图）：

\[G_t^\lambda = (1-\lambda) \sum_{n=1}^\infty \lambda^{n-1} G_{t:t+n}\]

性质： - \(\lambda = 0\)：\(G_t^0 = G_{t:t+1} = R_{t+1} + \gamma V(S_{t+1})\)（TD(0)） - \(\lambda = 1\)：\(G_t^1 = G_t\)（MC） - \(0 < \lambda < 1\)：n-step回报的指数加权平均

偏差-方差权衡： - \(\lambda\) 小：偏差大，方差小 - \(\lambda\) 大：偏差小，方差大

3.2 资格迹的后向视角¶

资格迹（Eligibility Traces）：

\[E_t(s) = \gamma \lambda E_{t-1}(s) + \mathbb{1}[S_t = s]\]

或对于状态-动作对：

\[E_t(s, a) = \gamma \lambda E_{t-1}(s, a) + \mathbb{1}[S_t = s, A_t = a]\]

直观理解： - 资格迹记录每个状态（或状态-动作对）对当前误差的"责任" - 最近访问的状态有更高的资格 - 衰减因子 \(\gamma\lambda\) 控制记忆的衰退速度

3.3 前向与后向视角的等价性¶

定理 6.1（TD(λ)的等价性）

在离线更新（offline update）情况下，前向视角和后向视角的TD(λ)是等价的：

\[\sum_{t=0}^T \delta_t E_t(s) = \sum_{t=0}^T [G_t^\lambda - V(S_t)] \mathbb{1}[S_t = s]\]

其中TD误差：

\[\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)\]

证明概要：

展开资格迹的定义，交换求和顺序，利用几何级数性质。

3.4 TD(λ)的收敛性¶

定理 6.2（TD(λ)的收敛性）

在以下条件下： 1. 策略是固定的 2. 步长满足Robbins-Monro条件 3. 所有状态被无限次访问

TD(λ)以概率1收敛到 \(V^\pi\)。

收敛速率：

\[\mathbb{E}[\|V_k - V^\pi\|^2] = O\left(\frac{1}{k}\right)\]

3.5 代码实现：TD(λ)¶

Python

class TDLambda:
    """TD(λ)算法实现"""

    def __init__(self, n_states: int, n_actions: int,
                 gamma: float = 0.9, lambda_: float = 0.9):
        self.n_states = n_states
        self.n_actions = n_actions
        self.gamma = gamma
        self.lambda_ = lambda_

    def td_lambda_prediction(self, env, policy, alpha: float = 0.1,
                            num_episodes: int = 1000) -> np.ndarray:
        """
        TD(λ)预测算法

        参数:
            env: 环境
            policy: 策略 [n_states x n_actions]
            alpha: 学习率
            num_episodes: episode数量
        返回:
            V: 状态值函数
        """
        V = np.zeros(self.n_states)

        for episode in range(num_episodes):
            # 初始化资格迹
            E = np.zeros(self.n_states)

            state, _ = env.reset()

            while True:
                # 选择动作
                action = np.random.choice(self.n_actions, p=policy[state])

                # 执行动作
                next_state, reward, terminated, truncated, _ = env.step(action)
                done = terminated or truncated

                # 计算TD误差（终止时不自举）
                delta = reward + self.gamma * V[next_state] * (1 - done) - V[state]

                # 更新资格迹
                E[state] += 1  # 累积迹（accumulating traces）
                # E[state] = 1  # 替换迹（replacing traces）

                # 更新值函数
                V += alpha * delta * E

                # 衰减资格迹
                E *= self.gamma * self.lambda_

                if done:
                    break

                state = next_state

        return V

    def sarsa_lambda(self, env, alpha: float = 0.1, epsilon: float = 0.1,
                    num_episodes: int = 1000) -> np.ndarray:
        """
        SARSA(λ)算法
        """
        Q = np.zeros((self.n_states, self.n_actions))

        for episode in range(num_episodes):
            # 初始化资格迹
            E = np.zeros((self.n_states, self.n_actions))

            state, _ = env.reset()

            # ε-贪婪选择动作
            if np.random.rand() < epsilon:
                action = np.random.randint(self.n_actions)
            else:
                action = np.argmax(Q[state])

            while True:
                # 执行动作
                next_state, reward, terminated, truncated, _ = env.step(action)
                done = terminated or truncated

                # 选择下一个动作
                if np.random.rand() < epsilon:
                    next_action = np.random.randint(self.n_actions)
                else:
                    next_action = np.argmax(Q[next_state])

                # 计算TD误差（终止时不自举）
                delta = reward + self.gamma * Q[next_state, next_action] * (1 - done) - Q[state, action]

                # 更新资格迹
                E[state, action] += 1

                # 更新Q函数
                Q += alpha * delta * E

                # 衰减资格迹
                E *= self.gamma * self.lambda_

                if done:
                    break

                state = next_state
                action = next_action

        return Q

    def watkins_q_lambda(self, env, alpha: float = 0.1, epsilon: float = 0.1,
                        num_episodes: int = 1000) -> np.ndarray:
        """
        Watkins's Q(λ)算法

        特点：当采取非贪婪动作时，将资格迹置零
        """
        Q = np.zeros((self.n_states, self.n_actions))

        for episode in range(num_episodes):
            E = np.zeros((self.n_states, self.n_actions))

            state, _ = env.reset()

            if np.random.rand() < epsilon:
                action = np.random.randint(self.n_actions)
            else:
                action = np.argmax(Q[state])

            while True:
                next_state, reward, terminated, truncated, _ = env.step(action)
                done = terminated or truncated

                # 计算TD误差（使用最大Q值，终止时不自举）
                max_q_next = np.max(Q[next_state])
                delta = reward + self.gamma * max_q_next * (1 - done) - Q[state, action]

                # 更新资格迹
                E[state, action] += 1

                # 更新Q函数
                Q += alpha * delta * E

                # 选择下一个动作
                if np.random.rand() < epsilon:
                    next_action = np.random.randint(self.n_actions)
                else:
                    next_action = np.argmax(Q[next_state])

                # Watkins's Q(λ)：如果采取非贪婪动作，迹置零
                if next_action != np.argmax(Q[next_state]):
                    E = np.zeros((self.n_states, self.n_actions))
                else:
                    E *= self.gamma * self.lambda_

                if done:
                    break

                state = next_state
                action = next_action

        return Q

4. 随机逼近理论¶

4.1 Robbins-Monro算法¶

问题：求解方程 \(h(\theta) = 0\)，其中只能观测到噪声版本：

\[H(\theta, \xi) = h(\theta) + \text{噪声}\]

Robbins-Monro更新：

\[\theta_{k+1} = \theta_k + \alpha_k H(\theta_k, \xi_k)\]

收敛条件： 1. \(\sum_k \alpha_k = \infty\)（保证足够探索） 2. \(\sum_k \alpha_k^2 < \infty\)（保证噪声衰减） 3. \(h\) 满足某些正则条件

4.2 随机逼近在RL中的应用¶

TD学习作为随机逼近：

目标：找到 \(V\) 使得 \(V = T^\pi V\)（即 \(h(V) = T^\pi V - V = 0\)）

观测：\(H(V, \xi) = R + \gamma V(S') - V(S)\)

更新：\(V_{k+1} = V_k + \alpha_k [R + \gamma V_k(S') - V_k(S)]\)

4.3 步长选择理论¶

常用步长方案：

样本平均：\(\alpha_k = 1/k\)
收敛到真值
适用于平稳环境
固定步长：\(\alpha_k = \alpha\)
指数加权平均
适用于非平稳环境
收敛到邻域而非精确值
递减步长：\(\alpha_k = 1/k^p\)，\(p \in (0.5, 1]\)
折中方案
比 \(1/k\) 初期学习更快
自适应步长：
AdaGrad、RMSProp、Adam等
根据梯度历史调整步长

4.4 收敛速率分析¶

定理 6.3（TD学习的收敛速率）

在适当条件下，TD(0)的收敛满足：

\[\mathbb{E}[\|V_k - V^\pi\|^2] \leq \frac{C}{k} + O\left(\frac{1}{k^2}\right)\]

其中 \(C\) 依赖于初始误差、步长选择和问题特性。

与MC的比较： - MC：\(O(1/\sqrt{n})\) 收敛（统计估计） - TD：\(O(1/k)\) 收敛（随机逼近） - 但TD有偏差，MC无偏

5. 偏差-方差权衡的深入分析¶

5.1 误差分解¶

对于值函数估计 \(\hat{V}\)，均方误差可以分解：

\[\text{MSE}(\hat{V}) = \mathbb{E}[(\hat{V} - V^\pi)^2] = \underbrace{(\mathbb{E}[\hat{V}] - V^\pi)^2}_{\text{偏差}^2} + \underbrace{\text{Var}(\hat{V})}_{\text{方差}}\]

5.2 不同算法的误差特性¶

算法	偏差	方差	适用场景
DP	0	0	小状态空间，已知模型
MC	0	高	需要无偏估计，episode任务
TD(0)	中	低	在线学习，连续任务
n-step TD	可调	可调	需要平衡偏差方差
TD(λ)	可调	可调	长程依赖重要

5.3 最优偏差-方差权衡¶

理论上：存在最优的 \(n\) 或 \(\lambda\) 使得MSE最小

实践中： - 通过交叉验证选择 - 根据问题特性启发式选择 - 自适应方法（根据学习进度调整）

6. 统一视角下的算法选择¶

6.1 决策树¶

Text Only

是否有环境模型？
├── 是 → 状态空间大小？
│   ├── 小 → 动态规划（Value/Policy Iteration）
│   └── 大 → 近似动态规划
└── 否 → 任务类型？
    ├── Episodic（有终止状态）
    │   ├── 需要无偏估计？
    │   │   ├── 是 → 蒙特卡洛
    │   │   └── 否 → n-step TD（n可调）
    │   └── 样本效率重要？
    │       ├── 是 → TD(λ)
    │       └── 否 → MC
    └── Continuing（无终止）
        ├── On-Policy？
        │   ├── 是 → SARSA / Expected SARSA
        │   └── 否 → Q-Learning
        └── 稳定性重要？
            ├── 是 → Expected SARSA / Double Q-Learning
            └── 否 → Q-Learning

6.2 问题特性与算法匹配¶

问题特性	推荐算法	原因
高奖励噪声	小n或TD(0)	减少方差累积
长程依赖	大n或TD(λ)	捕获长期回报
非平稳环境	固定步长TD	跟踪变化
需要收敛保证	MC或递减步长TD	理论保证
样本稀缺	TD(0)或Expected SARSA	高样本效率
大规模状态空间	函数逼近 + TD	泛化能力

7. 本章总结¶

7.1 核心概念回顾¶

Text Only

统一框架 = 算子理论 + 随机逼近

算子视角：
├── 贝尔曼算子 T^π 和 T* 是γ-压缩映射
├── DP：直接迭代应用算子
├── MC：采样估计算子输出
└── TD：近似不动点迭代

n-step方法：
├── MC和TD的连续谱
├── n=1：TD(0)
├── n=∞：MC
└── 偏差-方差权衡随n变化

TD(λ)：
├── 前向视角：λ-回报 = n-step回报的加权平均
├── 后向视角：资格迹记录状态"责任"
└── 等价性：离线更新时两种视角等价

随机逼近：
├── Robbins-Monro框架
├── 步长条件：Σα=∞, Σα²<∞
└── 收敛速率：O(1/k)

7.2 算法对比总结¶

维度	DP	MC	TD(0)	n-step TD	TD(λ)
需要模型	是	否	否	否	否
自举	是	否	是	是	是
采样	否	是	是	是	是
在线更新	否	否	是	是	是
偏差	0	0	>0	>0	>0
方差	低	高	低	可调	可调
收敛速率	线性	O(1/√n)	O(1/k)	O(1/k)	O(1/k)

7.3 学习路径¶

Text Only

下一步学习:
├── 函数逼近 - 处理大规模状态空间
│   ├── 线性函数逼近
│   ├── 神经网络（Deep RL）
│   └── 收敛性挑战（ deadly triad ）
├── 策略梯度方法 - 直接优化策略
│   ├── REINFORCE
│   ├── Actor-Critic
│   └── 自然策略梯度
└── 模型基础方法 - 学习并使用模型
    ├── 模型学习
    ├── 规划与学习的结合
    └── MBMF, MBVE等算法

✅ 自测问题¶

从算子理论视角，解释DP、MC、TD的统一性。为什么TD被称为"近似不动点迭代"？
n-step方法如何连接MC和TD？推导n-step回报的偏差和方差公式。
证明TD(λ)前向视角和后向视角的等价性（离线更新情况）。
Robbins-Monro条件的两个要求分别有什么意义？违反其中一个会怎样？
设计一个实验比较不同λ值对TD(λ)性能的影响。预期结果是什么？
给定一个具体问题，如何根据问题特性选择合适的学习算法？

📚 延伸阅读¶

理论基础¶

Sutton & Barto《Reinforcement Learning: An Introduction》
第7章：n-step Bootstrapping
第12章：Eligibility Traces
Tsitsiklis (1994)
"Asynchronous Stochastic Approximation and Q-Learning"
随机逼近在RL中的严格分析
Dayan (1992)
"The Convergence of TD(λ) for General λ"
TD(λ)收敛性的经典证明

资格迹理论¶

Sutton & Singh (1994)
"On Step-Size and Bias in Temporal-Difference Learning"
步长和偏差的深入分析
Kearns & Singh (2000)
"Bias-Variance Error Bounds for Temporal Difference Updates"
TD的偏差-方差权衡

现代进展¶

Sutton et al. (2016)
"The True Online TD(λ) Algorithm"
真正的在线TD(λ)算法
Daley et al. (2023)
"Eligibility Traces for Options"
资格迹在选项框架中的应用

恭喜你完成了基础阶段的学习！ 现在你已经建立了扎实的RL理论基础，可以进入更高级的主题：函数逼近、深度强化学习、策略梯度方法等。

→ 下一步：../02-时序差分学习/02-SARSA算法.md