第五章 模型不确定性

第一部分 章节概述

本章讨论了在模型未知情况下的序贯决策问题。在前一章（第四章）中，我们假设马尔可夫决策过程（MDP）的转移概率和奖励函数是已知的。然而，在许多实际问题中，智能体并不知道环境的动态特性和奖励机制，必须通过与环境的交互经验来学习如何行动。通过观察其动作所导致的状态转移和奖励反馈，智能体需要选择能够最大化长期累积奖励的动作。

本章的核心主题是强化学习（Reinforcement Learning），涵盖了处理模型不确定性的三个关键挑战：

第一个挑战是探索与利用的平衡问题。智能体必须在充分探索环境以获取更多知识（探索），和利用已有知识来获取最大化奖励（利用）之间找到平衡。如果持续进行探索，则可以建立更全面的环境模型，但会牺牲部分奖励；如果仅利用当前认为最优的策略而从不尝试新策略，则可能错过更好的策略。

第二个挑战是信用分配问题。奖励往往在做出重要决策之后很久才收到，因此需要将后期奖励的"功劳"分配给早期的决策。这一问题在稀疏奖励的环境中尤为突出。

第三个挑战是泛化问题。由于智能体与环境的交互经验有限，必须能够将已学到的知识推广到尚未访问过的状态。

本章依次介绍了多臂老虎机问题、基于模型的方法（包括最大似然估计和贝叶斯方法）、无模型方法（Q学习、Sarsa、资格迹）以及泛化技术（局部近似、全局近似、状态抽象）。

本章对应的前置知识包括：概率论基础（第二章的贝塔分布和狄利克雷分布）、马尔可夫决策过程理论（第四章的贝尔曼方程、值迭代和策略迭代）以及优化基础。

---

第二部分 关键问题与研究动机

5.1 核心科学问题

本章围绕以下五个核心科学问题展开：

问题一：如何在不确定环境下平衡探索与利用？

这是强化学习中最基本的问题之一。在模型未知的环境中，智能体面临一个基本的矛盾：如果只探索，则无法获得高奖励；如果只利用已知信息，则可能错过更好的策略。多臂老虎机问题是这一问题的最简抽象。

问题二：如何表示和更新对环境模型的信念？

当环境模型未知时，智能体需要维护关于模型参数的信念分布。贝叶斯方法提供了一种原则性的框架来表示和更新这些信念。关键问题包括：如何选择合适的先验分布？如何高效地进行后验更新？

问题三：如何处理延迟奖励的信用分配？

在序贯决策问题中，动作的影响可能需要很多步之后才能显现。例如，在棋类游戏中，当前这一步的效果可能要到几十步之后才能判断。如何将最终的奖励信号有效地传播回之前的决策是一个核心挑战。

问题四：如何在有限经验下高效学习？

直接在每个状态-动作对上学习值函数是不现实的，因为状态空间可能非常大。必须使用某种形式的函数近似来泛化知识。

问题五：如何设计计算效率高的学习算法？

实际应用中，学习必须在有限计算资源下进行。需要在学习速度和计算成本之间找到平衡。

5.2 研究动机与历史背景

多臂老虎机问题的研究历史可追溯至二战期间。据Peter Whittle所述，"试图解决[老虎机问题]的努力耗尽了盟军分析家的精力和心智，以至于有人建议将这个问题扔到德国去，作为最终的知识破坏工具"。这说明这一问题的难度。

本章的研究动机来自于实际应用的广泛需求，包括：

• 临床试验设计：如何在评估新药效果和为患者提供最佳治疗之间平衡
• 自适应网络路由：如何在网络中动态选择最优路由
• 推荐系统：如何平衡推荐已知受欢迎内容和探索新内容的用户
• 机器人控制：如何在未知环境中学习有效行为

---

第三部分 主要公式与推导

5.1 探索与利用

5.1.2 贝叶斯模型估计

对于臂\(i\)的获胜概率\(\theta_i\)，我们使用贝塔分布作为后验分布。先验为均匀分布，即\(\text{Beta}(1,1)\)。设\(w_i\)为获胜次数，\(\ell_i\)为失败次数，则后验分布为\(\text{Beta}(w_i + 1, \ell_i + 1)\)。

后验获胜概率为：

\[ \rho_i = P(\text{win}_i | w_i, \ell_i) = \int_0^1 \theta \times \text{Beta}(\theta | w_i + 1, \ell_i + 1) \, d\theta = \frac{w_i + 1}{w_i + \ell_i + 2} \tag{5.1} \]

示例：两臂老虎机，拉6次后，第一臂：1胜0负（\(\theta_1 \sim \text{Beta}(2,1)\)），第二臂：4胜1负（\(\theta_2 \sim \text{Beta}(5,2)\)）。

最大似然估计：\(\hat{\theta}_1 = 1\)，\(\hat{\theta}_2 = 4/5 = 0.8\)。

贝叶斯后验概率：\(\rho_1 = 2/3 \approx 0.67\)，\(\rho_2 = 5/7 \approx 0.71\)。因此，只剩一次拉杆机会时，应选择第二臂。

5.1.4 最优探索策略

信念状态由计数\(w_1, \ell_1, \ldots, w_n, \ell_n\)表示。这\(2n\)个数字可以表示对\(\rho_{1:n}\)的连续概率分布。

最优价值函数：

\[ U^*(w_1, \ell_1, \ldots, w_n, \ell_n) = \max_i Q^*(w_1, \ell_1, \ldots, w_n, \ell_n, i) \tag{5.4} \]

最优策略：

\[ \pi^*(w_1, \ell_1, \ldots, w_n, \ell_n) = \arg\max_i Q^*(w_1, \ell_1, \ldots, w_n, \ell_n, i) \tag{5.5} \]

\(Q^*\)的分解：

\[ \begin{aligned} Q^*(w_1, \ell_1, \ldots, w_n, \ell_n, i) = &\frac{w_i + 1}{w_i + \ell_i + 2} \left[1 + U^*(\ldots, w_i + 1, \ell_i, \ldots)\right] \\ &+ \left(1 - \frac{w_i + 1}{w_i + \ell_i + 2}\right) U^*(\ldots, w_i, \ell_i + 1, \ldots) \tag{5.6} \end{aligned} \]

第一项对应臂\(i\)获胜的情况，第二项对应失败的情况。

5.2 最大似然基于模型的方法

最大似然估计

最大似然估计的转移概率和奖励函数：

\[ \hat{T}(s' | s, a) = \frac{N(s, a, s')}{N(s, a)} \tag{5.8} \]

\[ \hat{R}(s, a) = \frac{\rho(s, a)}{N(s, a)} \tag{5.9} \]

其中\(N(s,a)\)是从状态\(s\)执行动作\(a\)的总次数，\(N(s,a,s')\)是从\((s,a)\)转移到\(s'\)的次数，\(\rho(s,a)\)是累计奖励。

Dyna算法中的随机化更新

\[ Q(s, a) \leftarrow R(s, a) + \gamma \sum_{s'} T(s' | s, a) \max_{a'} Q(s', a') \tag{5.10} \]

5.3 贝叶斯基于模型的方法

5.3.2 模型参数的先验与后验

对离散状态空间，使用狄利克雷先验：

\[ b_0(\theta) = \prod_{s,a} \text{Dir}(\theta_{(s,a)} | \alpha_{(s,a)}) \tag{5.12} \]

\(t\)步之后的后验：

\[ b_t(\theta) = \prod_{s,a} \text{Dir}(\theta_{(s,a)} | \alpha_{(s,a)} + m_{(s,a)}) \tag{5.13} \]

5.3.3 贝叶斯自适应MDP

状态空间为\(S \times B\)，其中\(B\)是所有可能的信念空间。

转移函数：

\[ T(s', b' | s, b, a) = \delta_{\tau(s,b,a,s')}(b') \cdot P(s' | s, b, a) \tag{5.14} \]

其中\(\tau\)是信念更新函数，\(\delta\)是克罗内克\(\delta\)函数。

边缘转移概率需要积分：

\[ P(s' | s, b, a) = \int_\theta b(\theta) \theta_{(s,a,s')} \, d\theta \tag{5.16} \]

广义贝尔曼方程

\[ U^*(s, b) = \max_a \left[ R(s, a) + \gamma \sum_{s'} P(s' | s, b, a) U^*(s', \tau(s, b, a, s')) \right] \tag{5.17} \]

5.4 无模型方法

5.4.1 增量估计

样本均值：

\[ \hat{x}_n = \frac{1}{n} \sum_{i=1}^n x_i \tag{5.18} \]

增量更新形式：

\[ \hat{x}_n = \hat{x}_{n-1} + \frac{1}{n}(x_n - \hat{x}_{n-1}) \tag{5.19} \]

学习率形式：

\[ \hat{x} \leftarrow \hat{x} + \alpha(x - \hat{x}) \tag{5.21} \]

其中\((x - \hat{x})\)称为时序差分误差（TD误差）。

5.4.2 Q学习

原始贝尔曼方程：

\[ Q(s, a) = R(s, a) + \gamma \sum_{s'} T(s' | s, a) \max_{a'} Q(s', a') \tag{5.23} \]

增量更新规则：

\[ Q(s, a) \leftarrow Q(s, a) + \alpha\left(r + \gamma \max_{a'} Q(s', a') - Q(s, a)\right) \tag{5.24} \]

5.4.3 Sarsa

\[ Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha\left(r_t + \gamma Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t)\right) \tag{5.25} \]

Sarsa使用实际执行的下一个动作\(a_{t+1}\)，而Q学习使用\(\arg\max\)。

5.4.4 资格迹

TD误差：

\[ \delta = r_t + \gamma Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t) \tag{5.26} \]

更新后衰减资格迹：\(N(s, a) \leftarrow \gamma \lambda N(s, a)\)。

5.5 泛化

5.5.1 局部近似

线性近似：

\[ Q(s, a) = \sum_{s'} \theta_{s',a} \beta(s, s') \tag{5.27} \]

向量形式：

\[ Q(s, a) = \theta^\top \beta(s, a) \tag{5.29} \]

更新规则：

\[ \theta \leftarrow \theta + \alpha\left(r_t + \gamma \max_a \theta^\top \beta(s_{t+1}, a) - \theta^\top \beta(s_t, a_t)\right) \beta(s_t, a_t) \tag{5.30} \]

5.5.2 全局近似

感知机模型：

\[ q = \sum_{i=1}^m \theta_i x_i = \theta^\top x \tag{5.31} \]

感知机Q学习：

\[ Q(s, a) = \theta_a^\top \beta(s) \tag{5.32} \]

5.5.3 抽象方法

叶子节点的q值计算：

\[ q(s, a) = r + \gamma U(s') \tag{5.34} \]

分裂标准是最小化叶子节点的方差。

---

第四部分 关键算法与建模方法

5.1 最大似然模型强化学习（Algorithm 5.1）

算法流程：

1. 初始化：设置初始状态\(s_0\)，初始化计数\(N\)、奖励和\(\rho\)、\(Q\)表
2. 主循环：
3. 根据探索策略选择动作\(a_t\)
4. 观察新状态\(s_{t+1}\)和奖励\(r_t\)
5. 更新计数：\(N(s_t, a_t, s_{t+1}) \leftarrow N(s_t, a_t, s_{t+1}) + 1\)
6. 更新奖励和：\(\rho(s_t, a_t) \leftarrow \rho(s_t, a_t) + r_t\)
7. 基于新的\(T\)和\(R\)估计更新\(Q\)
8. 时间步递增

计算成本：每次更新都需要解决完整的MDP，复杂度为\(O(|S|^3)\)（值迭代）。

5.2 优先级扫描（Prioritized Sweeping, Algorithm 5.2）

核心思想：不是均匀地更新所有状态，而是优先更新那些变化最大的状态。

算法流程：

1. 将当前状态\(s\)的优先级设为无穷大
2. 当优先级队列非空时：
3. 取出最高优先级的状态\(s\)
4. 更新\(U(s)\)：\(U(s) \leftarrow \max_a [R(s,a) + \gamma \sum_{s'} T(s'|s,a)U(s')]\)
5. 对前驱状态\((s', a') \in \text{pred}(s)\)，更新其优先级：\(p = T(s|s',a') \times |U(s) - u|\)

优势：相比Dyna的随机更新，优先级扫描更有针对性，收敛更快。

5.3 Thompson采样

算法思想：

1. 从当前信念分布\(b_t\)中采样一个模型参数\(\theta\)
2. 假设\(\theta\)是真模型，使用动态规划求解最优策略
3. 下一个时间步更新信念，重复过程

优势：不需要手工设置探索参数。

劣势：计算成本高（每步需要重新求解MDP），且已被证明存在过度探索的问题。

5.4 Q学习（Algorithm 5.3）

核心更新：

\[ Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha\left(r_t + \gamma \max_a Q(s_{t+1}, a) - Q(s_t, a_t)\right) \]

特点：

• 异策略（off-policy）：学习最优策略而使用\(\epsilon\)-greedy等探索策略
• 收敛性：在满足一定条件（所有状态-动作对无限次访问，学习率衰减）下收敛到最优\(Q^*\)

5.5 Sarsa（Algorithm 5.3的变体）

核心更新：

\[ Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha\left(r_t + \gamma Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t)\right) \]

特点：

• 同策略（on-policy）：使用与执行相同的策略进行学习
• 更保守：学习过程中策略变化时\(Q\)值也会相应调整

5.6 Sarsa(λ)（Algorithm 5.4）

资格迹机制：

• 维护一个\(N(s,a)\)来表示对该状态-动作对的"资格"
• 每次访问时增加资格：\(N(s_t, a_t) \leftarrow N(s_t, a_t) + 1\)
• 每步衰减所有资格：\(N(s,a) \leftarrow \gamma\lambda N(s,a)\)
• 更新时对所有状态-动作对进行更新，资格越高的更新幅度越大

参数\(\lambda\)的作用：

• \(\lambda = 0\)：退化为单步Sarsa
• \(\lambda = 1\)：信用传播到起始状态

5.7 线性近似Q学习（Algorithm 5.5）

核心思想：使用线性函数近似\(Q(s,a) = \theta^\top \beta(s,a)\)

更新规则：

\[ \theta \leftarrow \theta + \alpha\left(r_t + \gamma \max_a \theta^\top \beta(s_{t+1}, a) - \theta^\top \beta(s_t, a_t)\right) \beta(s_t, a_t) \]

5.8 感知机和神经网络近似

感知机（单层线性网络）：只能表示线性函数

神经网络（多层感知机）：通过隐藏层可以表示非线性函数，使用反向传播调整权重。

---

第五部分 主要结论

5.1 探索与利用平衡

1. \(\epsilon\)-greedy方法：以\(\epsilon\)概率随机选择动作，\(1-\epsilon\)概率选择当前最优动作。简单但不能有效利用不确定性信息。

2. Softmax方法：使用logit模型，臂\(i\)被选中概率与\(\exp(\lambda \rho_i)\)成正比。\(\lambda\)控制探索程度。

3. 区间探索：计算置信区间，选择上界最高的臂。

4. Gittins分配指数：对于无限视野折扣问题，可以得到最优策略，但计算复杂度高。

5.2 基于模型 vs 无模型方法

基于模型的方法：

• 优点：样本效率高，可以利用模型进行规划
• 缺点：需要显式构建模型，可能有模型偏差

无模型方法：

• 优点：简单，不需要显式建模
• 缺点：样本效率低，需要大量交互

5.3 信用分配

• 单步TD方法（Q学习、Sarsa）：只更新最近的状态-动作对
• 资格迹方法：通过指数衰减将信用传播到早期状态，有效加速学习

5.4 泛化技术

• 局部近似：依赖距离度量，适合状态空间平滑的场景
• 全局近似（神经网络）：不依赖距离，可以学习复杂模式
• 状态抽象：通过合并相似状态减少计算量

---

第六部分 挑战与开放问题

6.1 探索-利用平衡的固有权衡

尽管存在Gittins分配指数等理论最优方法，但它们通常需要计算指数级别的状态空间。对于大规模问题，仍需依赖启发式方法。如何设计既理论上有保证又计算可行的探索策略仍是开放问题。

6.2 贝叶斯自适应MDP的计算困难

贝叶斯自适应MDP的状态空间是连续的（信念空间），直接应用值迭代或策略迭代不现实。的主要研究方向包括：

• 近似后验表示（如高斯过程、粒子滤波）
• 离线规划方法（如稀疏采样、Monte Carlo树搜索）
• 层次化方法

6.3 函数近似的收敛性

使用函数近似时，Q学习的收敛性不再有保证。特别是使用非线性函数近似（如深度神经网络）时，学习可能不稳定或发散。深度Q网络（DQN）通过经验回放和目标网络来缓解这一问题，但理论保证仍然有限。

6.4 稀疏奖励环境

在许多实际应用中，奖励是稀疏的——大多数状态-动作对的奖励为0或负数，只有少数关键转换有正奖励。如何高效地在稀疏奖励环境下学习是一个重要挑战。内在动机（intrinsic motivation）和分层强化学习是活跃的研究方向。

6.5 部分可观测性

本章假设状态完全可观测。在部分可观测的MDP（POMDP）中，智能体只能观察到与状态相关的信号。处理POMDP需要额外的记忆机制，将在下一章讨论。

6.6 多智能体学习

本章只考虑单智能体学习。在多智能体系统中，其他智能体的存在使环境变成非静态的，需要额外的理论框架。

---

第七部分 个人思考与批判性分析

7.1 探索策略的哲学思考

探索与利用的平衡反映了人工智能中的一个根本性权衡：确定性 vs 灵活性。

完全利用已知策略会导致"局部最优陷阱"——智能体可能永远无法发现更好的策略。这类似于人类生活中的"舒适区"问题：停留在已知的、确定的路径上可能获得稳定的回报，但也可能错过更好的机会。

从工程角度看，\(\epsilon\)-greedy的简洁性使其成为实际应用的首选。但这种简单的随机探索是否真的高效？本书提到的Softmax和区间探索方法实际上利用了更多的不确定性信息，理论上应该更高效。

7.2 贝叶斯方法的优势与局限

贝叶斯方法在处理模型不确定性时具有原则性的优势：它提供了一个统一的框架来表示和更新信念，不需要手工设计探索参数。

然而，贝叶斯方法也有明显的局限：

1. 计算复杂度：精确的贝叶斯推理通常是不可行的，需要近似方法
2. 先验选择：结果对先验敏感，且先验选择往往缺乏客观标准
3. 过度探索：如Thompson采样被证明存在过度探索问题

作者在书中提到"虽然动态规划解是最优的，但信念状态的数量——进而所需的计算和内存——是指数级的"。这揭示了理论与实践之间的巨大鸿沟。

7.3 Q学习 vs Sarsa的选择

Q学习是异策略算法，可以使用\(\epsilon\)-greedy等探索策略同时学习最优策略；Sarsa是同策略算法，学习的是当前策略下的值函数。

从收敛速度看：

• Q学习可能收敛更快，因为它直接学习最优策略
• Sarsa更保守，在学习过程中可能更稳定

从实际应用看，如果探索策略接近贪婪，Q学习和Sarsa表现相近；如果探索策略随机性大，Sarsa可能更合适。

7.4 资格迹的直观理解

资格迹机制启发自神经科学的"赫布定律"——同时激活的神经元连接会加强。在强化学习中，资格迹实现了一种"延迟的信用分配"：如果一个状态-动作对最近被激活（参与决策），即使当前的TD误差来自其他状态，它也会被更新。

\(\lambda\)参数控制信用的"传播距离"：

• \(\lambda = 0\)：只有直接前驱被更新
• \(\lambda = 1\)：信用传播到所有历史状态

这种机制大大加速了在稀疏奖励环境中的学习，但需要额外的计算和内存。

7.5 泛化方法的权衡

表格型表示是理想的选择（如果可行），因为它能准确表示每个状态-动作对的值。但在大型状态空间中这是不现实的。

局部近似的优缺点：

• 优点：解释性强，计算效率高
• 缺点：依赖距离度量，无法捕捉长程依赖

全局近似（神经网络）的优缺点：

• 优点：可以学习复杂模式，表达能力强
• 缺点：解释性差，可能不稳定，需要大量数据

状态抽象提供了一种减少状态空间大小的方法，但抽象的质量直接影响学习效果。自动发现好的抽象是强化学习中的一个重要开放问题。

7.6 与现代深度强化学习的联系

本章介绍的Q学习、神经网络近似等方法在2013年DQN（Deep Q-Network）论文中得到了进一步发展。DQN使用深度卷积网络作为函数近似器，并引入经验回放和目标网络来稳定学习。

值得注意的是，虽然深度强化学习在Atari游戏等任务上取得了突破性进展，但其样本效率仍然很低——这与本章讨论的问题一脉相承。

7.7 值得进一步探索的方向

1. PAC-MDP理论：研究在多长时间内可以以高概率学到接近最优的策略
2. 内在动机强化学习：通过好奇心驱动等机制解决稀疏奖励问题
3. 元学习：学习如何学习，快速适应新任务
4. 分层强化学习：通过多层次抽象简化学习

---

公式汇总

编号	名称	形式	物理意义	类型
(5.1)	后验获胜概率	\(\rho_i = \frac{w_i + 1}{w_i + \ell_i + 2}\)	贝塔分布后验均值	(T)
(5.4)	最优价值函数	\(U^* = \max_i Q^*\)	信念状态下的最优期望回报	(T)
(5.6)	Q函数分解	获胜/失败加权和	贝尔曼方程的期望形式	(T)
(5.8)	最大似然转移	$\hat{T}(s'	s,a) = N(s,a,s')/N(s,a)$	经验转移频率
(5.9)	最大似然奖励	\(\hat{R}(s,a) = \rho(s,a)/N(s,a)\)	经验平均奖励	(E)
(5.10)	Dyna更新	\(Q \leftarrow R + \gamma \sum T \max Q'\)	模型基础的TD更新	(T)
(5.12)	Dirichlet先验	\(b_0(\theta) = \prod \text{Dir}(\theta\|\alpha)\)	模型参数信念	(T)
(5.13)	Dirichlet后验	\(b_t(\theta) = \prod \text{Dir}(\theta\|\alpha+m)\)	更新后信念	(T)
(5.17)	广义贝尔曼方程	\(U^* = \max_a [R + \gamma \sum P U^*]\)	BAMDP的最优方程	(T)
(5.21)	增量估计	\(\hat{x} \leftarrow \hat{x} + \alpha(x - \hat{x})\)	随机梯度下降形式	(T)
(5.24)	Q学习更新	\(Q \leftarrow Q + \alpha(r + \gamma \max Q' - Q)\)	异策略TD学习	(T)
(5.25)	Sarsa更新	\(Q \leftarrow Q + \alpha(r + \gamma Q' - Q)\)	同策略TD学习	(T)
(5.26)	TD误差	\(\delta = r + \gamma Q' - Q\)	当前估计与目标的差	(T)
(5.27)	局部近似	\(Q(s,a) = \sum \theta \beta(s,s')\)	核函数线性组合	(T)
(5.31)	感知机	\(q = \sum \theta_i x_i\)	线性加权求和	(T)
(5.34)	叶子q值	\(q(s,a) = r + \gamma U(s')\)	基于模型的单步估计	(T)

注：(T)=理论推导，(E)=经验公式

---

参考文献

1. Gittins, J. C. (1989). Multi-armed Bandit Allocation Indices. John Wiley & Sons.
2. Sutton, R. S., & Barto, A. G. (1998). Reinforcement Learning: An Introduction. MIT Press.
3. Wiering, M., & Otterlo, M. V. (Eds.). (2012). Reinforcement Learning: State-of-the-Art. Springer.
4. Kochenderfer, M. J. (2015). Decision Making Under Uncertainty: Theory and Application. MIT Press.