07 - 收敛性与复杂度理论¶

学习时间: 4-5小时 重要性: ⭐⭐⭐⭐⭐ 深入理解RL算法的理论保证 前置知识: 随机过程、概率论、优化理论

🎯 学习目标¶

完成本章后，你将能够： - 掌握值迭代、策略迭代的收敛速率分析 - 理解TD学习的随机逼近收敛理论 - 掌握样本复杂度的下界和上界分析 - 理解近似误差对策略性能的影响 - 掌握探索-利用权衡的理论分析 - 能够分析RL算法的理论性能保证

1. 动态规划的收敛性分析¶

1.1 值迭代的收敛速率¶

回顾：值迭代 \(V_{k+1} = T^* V_k\)

定理 7.1（值迭代的线性收敛）

值迭代以线性速率收敛到 \(V^*\)：

\[\|V_{k+1} - V^*\|_\infty \leq \gamma \|V_k - V^*\|_\infty\]

因此：

\[\|V_k - V^*\|_\infty \leq \gamma^k \|V_0 - V^*\|_\infty\]

达到精度 \(\epsilon\) 所需的迭代次数：

\[k \geq \frac{\ln(\|V_0 - V^*\|_\infty / \epsilon)}{\ln(1/\gamma)} = O\left(\frac{1}{1-\gamma} \ln\frac{1}{\epsilon}\right)\]

证明：

由 \(T^*\) 的 \(\gamma\)-压缩性：

\[\|V_{k+1} - V^*\|_\infty = \|T^* V_k - T^* V^*\|_\infty \leq \gamma \|V_k - V^*\|_\infty\]

递推即得。

与 \(\gamma\) 的关系：

当 \(\gamma \to 1\) 时，\(\frac{1}{1-\gamma} \to \infty\)，收敛变慢。

1.2 策略迭代的收敛性¶

策略迭代： 1. 策略评估：求解 \(V^{\pi_k}\) 2. 策略改进：\(\pi_{k+1}(s) = \arg\max_a Q^{\pi_k}(s, a)\)

定理 7.2（策略迭代的收敛性）

策略迭代在有限次迭代内收敛到最优策略（对于有限MDP）。

收敛速率：

策略迭代的最坏情况界与值迭代相同（线性收敛）：

\[\|V^{\pi_{k+1}} - V^*\|_\infty \leq \gamma \|V^{\pi_k} - V^*\|_\infty\]

但实践中策略迭代通常收敛得远快于此界，迭代次数极少（通常 \(<|S|\) 次），因为每次策略改进的效果往往远大于 \(\gamma\) 的压缩。每次迭代代价更高（需要完整策略评估）。

1.3 迭代复杂度的比较¶

算法	每次迭代复杂度	迭代次数	总复杂度
值迭代	\(O(S^2 A)\)	\(O(\frac{1}{1-\gamma}\ln\frac{1}{\epsilon})\)	\(O(\frac{S^2 A}{1-\gamma}\ln\frac{1}{\epsilon})\)
策略迭代	\(O(S^3 + S^2 A)\)	\(O(\frac{1}{1-\gamma}\ln\frac{1}{\epsilon})\)	\(O(\frac{S^3 + S^2 A}{1-\gamma}\ln\frac{1}{\epsilon})\)

注：策略迭代的迭代次数上界较松，实际通常更少。

2. 蒙特卡洛方法的复杂度¶

2.1 样本复杂度上界¶

定理 7.3（MC预测的样本复杂度）

要达到 \(\|V - V^\pi\|_\infty \leq \epsilon\) 以概率至少 \(1-\delta\)，需要：

\[n = O\left(\frac{R_{max}^2}{(1-\gamma)^2 \epsilon^2} \ln\frac{S}{\delta}\right)\]

个episodes。

证明概要：

对每个状态，使用Hoeffding不等式
联合界（union bound）处理所有 \(S\) 个状态
解出所需样本数

2.2 样本复杂度下界¶

定理 7.4（MC方法的样本复杂度下界）

对于某些MDP，任何算法都需要至少：

\[\Omega\left(\frac{R_{max}^2}{(1-\gamma)^3 \epsilon^2}\right)\]

个样本才能以常数概率达到 \(\epsilon\)-最优策略。

注：上下界在 \(\epsilon\) 和 \(1-\gamma\) 的阶上匹配。

2.3 MC控制的收敛性¶

定理 7.5（GLIE MC控制的收敛）

在GLIE探索策略下，MC控制以概率1收敛到最优策略：

\[Q_k \xrightarrow{a.s.} Q^*, \quad \pi_k \xrightarrow{a.s.} \pi^*\]

收敛速率：

\[\|Q_k - Q^*\|_\infty = O\left(\frac{1}{\sqrt{k}}\right)\]

达到 \(\epsilon\)-最优策略需要 \(O(1/\epsilon^2)\) 个episodes。

3. 时序差分学习的收敛理论¶

3.1 TD(0)的随机逼近分析¶

TD(0)更新：

\[V_{k+1}(S_k) = V_k(S_k) + \alpha_k [R_{k+1} + \gamma V_k(S_{k+1}) - V_k(S_k)]\]

定理 7.6（TD(0)的收敛性）

在以下条件下： 1. 步长满足：\(\sum_k \alpha_k = \infty\)，\(\sum_k \alpha_k^2 < \infty\) 2. 所有状态被无限次访问 3. 策略是固定的

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

3.2 收敛速率分析¶

定理 7.7（TD(0)的收敛速率）

使用步长 \(\alpha_k = \frac{1}{k}\)：

\[\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})\)	0	高
TD(0)	\(O(1/k)\)	>0	低

TD(0)收敛更快但有偏差。

3.3 Q-Learning的收敛性¶

Q-Learning更新：

\[Q_{k+1}(S_k, A_k) = Q_k(S_k, A_k) + \alpha_k [R_{k+1} + \gamma \max_a Q_k(S_{k+1}, a) - Q_k(S_k, A_k)]\]

定理 7.8（Q-Learning的收敛性）

在以下条件下： 1. 步长满足Robbins-Monro条件 2. 所有状态-动作对被无限次访问 3. 奖励有界

Q-Learning以概率1收敛到 \(Q^*\)。

收敛速率：

\[\|Q_k - Q^*\|_\infty = O\left(\frac{1}{k^{1/3}}\right)\]

（比TD(0)慢，因为max操作引入非线性）

4. 样本复杂度的统一分析¶

4.1 样本复杂度的定义¶

定义：样本复杂度是指达到 \(\epsilon\)-最优策略所需的最小样本数（episodes或steps）。

形式化：

\[N(\epsilon, \delta) = \min\{n : P(\|V^{\pi_n} - V^*\|_\infty \leq \epsilon) \geq 1-\delta\}\]

4.2 不同算法的样本复杂度¶

算法	样本复杂度	备注
值迭代	\(O(\frac{SA}{(1-\gamma)^3\epsilon^2})\)	需要模型
MC控制	\(O(\frac{SA}{(1-\gamma)^3\epsilon^2})\)	无模型，高方差
Q-Learning	\(O(\frac{SA}{(1-\gamma)^5\epsilon^2})\)	无模型，探索代价
UCB-Q	\(O(\frac{SA}{(1-\gamma)^3\epsilon^2}\ln\frac{1}{\delta})\)	最优探索

4.3 下界理论¶

定理 7.9（RL的样本复杂度下界）

对于任何算法，存在MDP使得：

\[N(\epsilon, \delta) = \Omega\left(\frac{SA}{(1-\gamma)^3\epsilon^2}\ln\frac{1}{\delta}\right)\]

意义： - 样本复杂度至少与状态数 \(S\)、动作数 \(A\) 成正比 - 与 \(1/(1-\gamma)^3\) 成正比（长程依赖更难学） - 与 \(1/\epsilon^2\) 成正比（高精度需要更多样本）

5. 近似误差分析¶

5.1 近似策略迭代¶

问题：当使用近似值函数 \(\tilde{V} \approx V^\pi\) 时，策略性能如何？

定理 7.10（近似策略迭代的性能界）

设策略改进基于近似值函数 \(\tilde{V}\)，满足 \(\|\tilde{V} - V^\pi\|_\infty \leq \epsilon\)，则新策略 \(\pi'\) 满足：

\[\|V^{\pi'} - V^*\|_\infty \leq \gamma \|V^\pi - V^*\|_\infty + \frac{2\gamma \epsilon}{1-\gamma}\]

误差传播：

近似误差 \(\epsilon\) 被放大了 \(\frac{2\gamma}{1-\gamma}\) 倍。

5.2 值函数近似的误差界¶

定理 7.11（近似值迭代的收敛）

使用近似贝尔曼算子 \(\tilde{T}\)，满足 \(\|\tilde{T}V - TV\|_\infty \leq \epsilon\)：

\[\limsup_{k \to \infty} \|V_k - V^*\|_\infty \leq \frac{\epsilon}{1-\gamma}\]

意义：近似误差导致收敛到 \(V^*\) 的 \(\frac{\epsilon}{1-\gamma}\)-邻域。

5.3 函数逼近的致命三元组¶

致命三元组（Deadly Triad）：

当以下三个元素同时存在时，算法可能发散： 1. 函数逼近：使用近似值函数 2. 自举：TD学习 3. Off-Policy：学习策略与执行策略不同

示例：

Baird's Counterexample展示了即使使用线性函数逼近，TD学习也可能发散。

解决方案： - 使用On-Policy方法（如SARSA） - 使用梯度TD方法（GTD, TDC） - 使用经验回放（Experience Replay）

6. 探索-利用的理论分析¶

6.1 遗憾（Regret）框架¶

累积遗憾：

\[\text{Regret}(T) = \sum_{t=1}^T [V^*(s_t) - Q^{\pi_t}(s_t, a_t)]\]

目标：最小化累积遗憾，或使遗憾次线性增长：\(\text{Regret}(T) = o(T)\)

6.2 探索算法的遗憾界¶

定理 7.12（ε-贪婪的遗憾界）

使用 \(\epsilon_t = t^{-1/3}\)：

\[\text{Regret}(T) = O(T^{2/3})\]

定理 7.13（UCB的遗憾界）

使用UCB1探索：

\[\text{Regret}(T) = O(\sqrt{SAT \ln T})\]

最优界：

\[\text{Regret}(T) = \Omega(\sqrt{SAT})\]

UCB接近最优。

6.3 PAC-MDP框架¶

定义：算法是PAC-MDP（Probably Approximately Correct for MDPs），如果：

\[P(\text{算法在} T \text{步后输出}\epsilon\text{-最优策略}) \geq 1-\delta\]

且样本复杂度为 \(poly(S, A, 1/(1-\gamma), 1/\epsilon, \ln(1/\delta))\)。

样本复杂度：

达到PAC保证所需的样本数：

\[N = O\left(\frac{SA}{(1-\gamma)^3\epsilon^2}\ln\frac{SA}{\delta}\right)\]

7. 计算复杂度的深入分析¶

7.1 时间复杂度¶

算法	每次更新	每次episode	总时间（达到收敛）
值迭代	\(O(S^2 A)\)	-	\(O(\frac{S^2 A}{1-\gamma}\ln\frac{1}{\epsilon})\)
策略迭代	\(O(S^3)\)	-	\(O(\frac{S^3}{1-\gamma}\ln\frac{1}{\epsilon})\)
MC	\(O(T)\)	\(O(T)\)	\(O(\frac{T SA}{(1-\gamma)^3\epsilon^2})\)
TD(0)	\(O(1)\)	\(O(T)\)	\(O(\frac{T}{\epsilon})\)
Q-Learning	\(O(A)\)	\(O(TA)\)	\(O(\frac{TA}{(1-\gamma)^5\epsilon^2})\)

7.2 空间复杂度¶

算法	空间复杂度	说明
值迭代	\(O(SA)\)	存储转移概率和奖励
策略迭代	\(O(SA + S^2)\)	额外存储策略评估矩阵
MC	\(O(SA)\)	存储Q函数
TD(0)	\(O(S)\)	存储V函数
Q-Learning	\(O(SA)\)	存储Q函数

7.3 复杂度与问题规模的关系¶

维度诅咒（Curse of Dimensionality）：

当状态空间是 \(d\) 维连续空间时： - 离散化后状态数 \(S = O((1/\epsilon)^d)\) - 复杂度随维度 \(d\) 指数增长

解决方案： - 函数逼近 - 状态聚合 - 层次化表示

8. 本章总结¶

8.1 核心概念回顾¶

Text Only

收敛性与复杂度理论

动态规划：
├── 值迭代：线性收敛，O(1/(1-γ)) 迭代次数
├── 策略迭代：超线性收敛，每次迭代代价高
└── 复杂度：与 S²A/(1-γ) 成正比

蒙特卡洛：
├── 样本复杂度：O(1/((1-γ)³ε²))
├── 收敛速率：O(1/√n)
└── 无偏但高方差

时序差分：
├── TD(0)：O(1/k) 收敛，有偏
├── Q-Learning：O(1/k^(1/3)) 收敛
└── 样本效率高于MC

近似误差：
├── 近似误差放大：ε/(1-γ)
├── 致命三元组：函数逼近+自举+Off-Policy
└── 需要特殊算法保证收敛

探索-利用：
├── 遗憾框架：累积性能损失
├── UCB：O(√SAT) 遗憾，接近最优
└── PAC-MDP：样本复杂度保证

8.2 复杂度总结表¶

算法	样本复杂度	时间复杂度	空间复杂度	收敛速率
值迭代	-	\(O(\frac{S^2 A}{1-\gamma}\ln\frac{1}{\epsilon})\)	\(O(SA)\)	线性
策略迭代	-	\(O(\frac{S^3}{1-\gamma}\ln\frac{1}{\epsilon})\)	\(O(SA+S^2)\)	超线性
MC	\(O(\frac{SA}{(1-\gamma)^3\epsilon^2})\)	\(O(\frac{T SA}{(1-\gamma)^3\epsilon^2})\)	\(O(SA)\)	\(O(1/\sqrt{n})\)
TD(0)	\(O(\frac{SA}{(1-\gamma)^2\epsilon})\)	\(O(\frac{T SA}{\epsilon})\)	\(O(S)\)	\(O(1/k)\)
Q-Learning	\(O(\frac{SA}{(1-\gamma)^5\epsilon^2})\)	\(O(\frac{TA}{(1-\gamma)^5\epsilon^2})\)	\(O(SA)\)	\(O(1/k^{1/3})\)

8.3 实践指导¶

Text Only

根据复杂度选择算法：

小状态空间 + 有模型：
└── 值迭代或策略迭代

大状态空间 + 无模型：
├── 高样本效率重要 → TD方法
├── 无偏估计重要 → MC方法
└── 在线学习 → TD(0)或SARSA

需要理论保证：
├── 收敛保证 → On-Policy TD
├── 样本复杂度保证 → UCB类算法
└── 避免致命三元组 → 不同时使用函数逼近+自举+Off-Policy

✅ 自测问题¶

证明值迭代的线性收敛性。当γ接近1时，收敛速率如何变化？
比较MC和TD(0)的收敛速率。为什么TD(0)收敛更快但有偏差？
解释样本复杂度的下界 \(Ω(SA/(1-γ)³ε²)\) 中各项的意义。
什么是致命三元组？给出一个发散的例子，并讨论如何避免。
UCB算法的遗憾界为什么是 \(O(√SAT)\)？这与探索-利用权衡有什么关系？
维度诅咒如何影响RL算法的复杂度？有哪些缓解方法？

📚 延伸阅读¶

收敛性理论¶

Bertsekas & Tsitsiklis (1996)
"Neuro-Dynamic Programming"
全面的收敛性分析
Singh et al. (2000)
"Convergence Results for Single-Step On-Policy Reinforcement-Learning Algorithms"
TD算法的收敛性

样本复杂度¶

Kakade (2003)
"On the Sample Complexity of Reinforcement Learning"
样本复杂度的系统研究
Strehl et al. (2006)
"PAC Model-Free Reinforcement Learning"
PAC-MDP框架

探索-利用¶

Auer et al. (2002)
"Finite-time Analysis of the Multiarmed Bandit Problem"
UCB算法的分析
Jaksch et al. (2010)
"Near-optimal Regret Bounds for Reinforcement Learning"
MDP中的遗憾分析

近似理论¶

Munos (2003)
"Error Bounds for Approximate Policy Iteration"
近似策略迭代的误差分析
Sutton et al. (2009)
"Fast Gradient-Descent Methods for Temporal-Difference Learning with Linear Function Approximation"
梯度TD方法

恭喜完成基础阶段的理论学习！ 现在你已经掌握了RL算法的理论基础，可以深入研究函数逼近、深度强化学习等高级主题。

→ 下一步：../02-时序差分学习/01-时序差分学习基础.md