第 5 章：模型不确定性（Model Uncertainty）
章节作者：Mykel J. Kochenderfer 章节定位：理论篇第五章。在第 4 章中，转移与奖励模型被假定为已知；本章放宽这一假设——讨论"环境动态与奖励事先未知，智能体必须通过经验学习如何行动"的问题。这是强化学习（reinforcement learning）这一领域的主题，也是本章的核心。作者点出该领域面临的三大挑战：(1) 必须谨慎地在"探索环境"与"利用已知知识"之间取得平衡；(2) 奖励往往在重要决策做出很久之后才到达，需要把后续奖励的功劳"回溯"到早期决策上（credit assignment）；(3) 智能体必须从有限的经验中泛化（generalize）。本章的 5.1 节用单状态问题讨论探索—利用的张力，5.2–5.3 节用多状态问题讨论基于模型的方法，5.4 节讨论无模型方法，5.5 节讨论泛化方法。
5.1 Exploration and Exploitation
强化学习要求我们在"探索环境"与"利用通过评估性反馈所获得的知识"之间进行审慎的平衡。一味地持续探索可能换来全面的环境模型，但累积到的奖励会很少；一味地持续采用"当前认为最优"的决策而从不尝试新策略，则可能错过对策略的改进与更多奖励的累积。本节在单状态设定下引入探索—利用的张力及其挑战。
5.1.1 Multi-Armed Bandit Problems
在"探索—利用"问题上最早一批研究的对象是老虎机（slot machines）——由于通常由一根拉杆控制、且平均而言会"抢走"赌徒的钱，它们有时被戏称为"独臂强盗（one-armed bandits）"。多臂老虎机（bandit）问题出现在临床试验分配、自适应网络路由等众多应用场景中。这类问题在二战期间被首次形式化，被证明极难求解：Peter Whittle 曾评论说，"为求解 [bandit 问题] 而耗费的精力与心智之多，使有人建议把这个问题直接扔到德国去，作为智力破坏的终极手段（参见 [1] 后的评论）"。
文献中出现过多种 bandit 问题的形式化方式，本节聚焦于其中一种简单情形：一台有 n 根拉杆的老虎机，第 i 根拉杆以概率 θᵢ 吐出 1，以概率 1−θᵢ 吐出 0；下注不需要押金，但总共只允许拉 h 次。可以把该问题视为一个 h 步有限时域的 Markov 决策过程（第 4 章），其状态只有一个、动作有 n 个、奖励函数 R(s, a) 未知。
5.1.2 Bayesian Model Estimation
可以用 2.3.2 节引入的 beta 分布来表达我们对第 i 根拉杆的中奖概率 θᵢ 的后验，并采用 uniform 先验（对应 Beta(1,1)）。只需要记录每根拉杆的中奖次数 wᵢ 与未中奖次数 ℓᵢ；θᵢ 的后验就是 Beta(wᵢ+1, ℓᵢ+1)。由此可计算"下一次拉杆中奖"的后验概率：
例如，对一台双臂老虎机共拉了 6 次：第 1 根 1 次中奖 0 次未中，第 2 根 4 次中奖 1 次未中。在 uniform 先验下，θ₁ 的后验是 Beta(2,1)，θ₂ 的后验是 Beta(5,2)，两个后验绘制在图 5.1 中。
θ₁ 的最大似然估计是 1，θ₂ 的最大似然估计是 4/5。若只依据最大似然估计选择下一次拉杆，会选第 1 根——因为它看起来"保证能赢"。当然，从未观察到第 1 根的失败并不意味着它就一定不会失败。
与最大似然估计形成对比的是：图 5.1 中的 Bayesian 后验在 (0,1) 区间上赋予了非零密度——两根拉杆在 θ=0 处的密度都为 0（因为两根都观察到至少 1 次中奖），θ₂=1 处的密度为 0（因为观察到 1 次未中）。用式 (5.1) 可得两臂的中奖概率：
因此，若假定只剩 1 次拉杆机会，选第 2 根更优。
5.1.3 Ad Hoc Exploration Strategies
文献中提出过多种启发式探索策略。最常见的一种是 ε-greedy：以概率 ε 随机选择一根拉杆，否则选择 arg max_i ρᵢ。ε 越大越能更快地识别出最优臂，但也有更多次拉杆被浪费在次优臂上。
directed exploration 策略则会利用先前拉杆过程中收集到的信息。例如 softmax 策略：按 logit 模型（3.3.3 节）选择拉杆，第 i 根被选中的概率与 exp(λρᵢ) 成正比；精度参数 λ≥0 控制探索量的大小，λ→0 时退化为均匀随机选取，λ→∞ 时退化为贪心选取。另一种做法是 interval exploration：计算 θᵢ 的 α% 置信区间并选择上界最高的拉杆；α 越大探索越多。
5.1.4 Optimal Exploration Strategies
计数 w₁, ℓ₁, …, wₙ, ℓₙ 构成了一个 belief state——它总结了我们对各拉杆回报的信念。正如 5.1.2 节所述，这 2n 个数足以代表 ρ₁:ₙ 上 n 个连续概率分布；这些 belief state 可以作为该 n 臂 bandit 问题的 MDP 中的状态。用 dynamic programming 可以确定最优策略 π*，它指定在给定计数下应拉哪一根。
用 Q*(w₁:ₙ, ℓ₁:ₙ, i) 表示"在当前计数下拉第 i 根、之后按最优行动"所对应的期望回报。最优效用函数与最优策略可由 Q* 给出：
Q* 可以拆成两项：
第一项对应第 i 根赢的情形，第二项对应输的情形。系数 (wᵢ+1)/(wᵢ+ℓᵢ+2) 是式 (5.1) 给出的后验赢的概率。式中的第一个 U* 假设本次拉 i 根为赢，第二个 U* 假设本次为输。
给定有限时域 h，可对整个 belief 空间求 Q*：从 Σᵢ(wᵢ+ℓᵢ)=h 的边界态起步，此时 U*(w₁, ℓ₁, …, wₙ, ℓₙ)=0（已无拉杆机会）；再往 Σᵢ(wᵢ+ℓᵢ)=h−1 的状态回推并反复套用式 (5.6)。
尽管这种 dynamic programming 解法是最优的，所需的 belief state 数——进而所需的计算与存储——按 h 指数级增长。对该问题可构造一个无限时域、折扣形式的版本，并用 Gittins allocation index 高效求解。allocation index 可存为一张查表：给定一根臂的拉杆次数与中奖次数，返回一个标量的分配指数；下一次应拉的，就是分配指数最大的那根臂。
5.2 Maximum Likelihood Model-Based Methods
针对多状态问题，已经提出了多种强化学习方法。多状态问题比 bandit 问题更难——我们必须"主动规划去访问某些状态"以确定其值。一种强化学习方法是直接从经验中估计转移与奖励模型。维护转移的计数 N(s, a, s′) 与奖励的累加 ρ(s, a)；转移与奖励模型的最大似然估计为：
若对转移概率或奖励有先验知识，可把 N(s, a, s′) 与 ρ(s, a) 初始化为非零值。
随后就可以在"估计出的模型是正确的"这一假设下求解 MDP。当然，必须引入某种探索策略（如 5.1.3 节所述）以保证最终能收敛到最优策略。最大似然模型式强化学习的基本结构见算法 5.1。
Algorithm 5.1 Maximum likelihood model-based reinforcement learning
1: function MaximumLikelihoodModelBasedReinforcementLearning
2: t ← 0
3: s0 ← initial state
4: Initialize N, ρ, and Q
5: loop
6: Choose action a_t based on some exploration strategy
7: Observe new state s_{t+1} and reward r_t
8: N(s_t, a_t, s_{t+1}) ← N(s_t, a_t, s_{t+1}) + 1
9: ρ(s_t, a_t) ← ρ(s_t, a_t) + r_t
10: Update Q based on revised estimate of T and R
11: t ← t + 1
5.2.1 Randomized Updates
理论上，算法 5.1 第 10 行的 Q 更新可以使用任何 dynamic programming 算法，但通常没必要在每个时间步上重解整个 MDP。Dyna 是一种避免在每步重解整个 MDP 的算法，在当前状态上执行如下更新：
其中 R 与 T 是估计出的奖励与转移函数。随后在两次决策之间"还有多少时间"允许的范围里，对随机挑选的状态—动作做若干次额外的 Q 更新。更新完成后，用 Q 决定下一步要执行的动作——可以借助 softmax 或其他探索策略。
5.2.2 Prioritized Updates
prioritized sweeping 方法用优先队列帮助识别"最需要更新 U 的"那些状态（算法 5.2）。若从 s 转移到 s′，则根据更新后的转移与奖励模型更新 U(s)。再对前驱集 pred(s) = {(s*, a*) | T(s | s*, a*) > 0}（即所有"能一步到达 s"的状态—动作对）进行遍历；将 s* 的优先级提升到 T(s | s*, a*) × |U(s) − u|，其中 u 是更新前 U(s) 的值。因此，U(s) 的变化越大，能一步转移到 s 的状态优先级就越高。持续若干次迭代（或直到优先队列清空）地更新队列中优先级最高的状态。
Algorithm 5.2 Prioritized sweeping
1: function PrioritizedSweeping(s)
2: Increase the priority of s to ∞
3: while priority queue is not empty
4: s ← highest priority state
5: Update(s)
6: function Update(s)
7: u ← U(s)
8: U(s) ← max_a [R(s, a) + γ Σ_{s'} T(s' | s, a) U(s')]
9: for (s*, a*) ∈ pred(s)
10: p ← T(s | s*, a*) × |U(s) − u|
11: Increase priority of s* to p
5.3 Bayesian Model-Based Methods
5.2 节用最大似然估计的转移概率与奖励，再借助启发式探索策略在极限意义下收敛到最优策略。Bayesian 方法则不依赖任何启发——它允许我们"最优地"在探索与利用之间取得平衡。本节把 5.1.4 节对多臂 bandit 的形式化推广到一般 MDP 上。
5.3.1 Problem Structure
在 Bayesian 强化学习中，先对所有模型参数 θ 指定一个先验分布。模型参数可以包括"决定即时奖励分布"的参数，但本节只关注"决定状态转移概率"的参数。若 S 表示状态空间、A 表示动作空间，则参数向量 θ 共含 |S|²|A| 个分量，每一分量对应一个可能的转移概率。控制 T(s′|s, a) 的那个分量记作 θ_(s,a,s′)。
图 5.2 用一个 dynamic decision network 表示该问题的结构——它是图 4.1b 的扩展，把模型参数显式化。阴影节点表示状态可观测而模型参数不可观测；一般假定模型参数时不变（time invariant），即 θ_{t+1} = θ_t；然而我们对 θ 的信念会随转移到新状态而演化。
5.3.2 Beliefs over Model Parameters
希望表示"对 θ 的先验信念"，对离散状态空间而言最自然的方式是 Dirichlet 分布的乘积：每一个 Dirichlet 表示"在当前状态 s 与动作 a 下、下一状态的分布"。若 θ_(s,a) 是长度为 |S| 的向量、表示下一状态的分布，则先验为
该 Dirichlet 分布由 |S| 个 α_(s,a) 参数控制。常用 uniform 先验（α_(s,a) 的所有分量都设为 1），但若对动态有先验知识，也可按 2.3.2 节设置这些参数。
对 θ 的先验由所有 (s, a) 组合的 Dirichlet 乘积给出：
对小型离散状态空间经常用上述因子分解，但其他低维参数化表示在某些场景下更合适。
记 t 步之后对 θ 的后验为 b_t。假设前 t 步观察到 m_(s,a,s′) 次"由 s 经 a 转移到 s′"的事件，用 Bayes 规则计算后验。若 m_(s,a) 表示转移计数的向量，则后验为
5.3.3 Bayes-Adaptive Markov Decision Processes
把"在未知模型 MDP 中的最优行动"问题，可以形式化为一个"高维、模型已知"的 MDP——该高维 MDP 称为 Bayes-adaptive Markov decision process，与下一章将讨论的 partially observable Markov decision process 相关。
Bayes-adaptive MDP 的状态空间是 S × B 的笛卡尔积，其中 B 是"对模型参数 θ 的所有可能信念"构成的空间。S 是离散的，B 通常是高维的连续空间。一个 Bayes-adaptive MDP 的状态写作 (s, b)，由基础 MDP 的状态 s 与信念状态 b 组成；动作空间与奖励函数与基础 MDP 完全一致。
Bayes-adaptive MDP 的转移函数是 T(s′, b′ | s, b, a)——表示"在状态 s、信念 b 下执行动作 a 后，转移到新状态 s′ 与新信念 b′"的概率。新信念 b′ 是 (s, b, a, s′) 的确定性函数（即 5.3.2 节用 Bayes 规则推出的更新）。记该确定性函数为 τ，使得 b′ = τ(s, b, a, s′)。Bayes-adaptive MDP 的转移函数可分解为
其中 δ_x(y) 是 Kronecker delta 函数：
求 P(s′ | s, b, a) 需要积分：
与式 (5.1) 类似，上式可解析求解。
5.3.4 Solution Methods
可把 4.2.4 节针对"模型已知"MDP 的 Bellman 方程推广到模型未知的场景：
可惜的是，并不能直接把第 4 章讲的 policy iteration、value iteration 套过来——因为 b 是连续的。不过可以用 4.5 节的近似方法以及 4.6 节的在线方法。下一章将给出一些更能利用 Bayes-adaptive MDP 结构的方法。
求解"在信念空间上的最优值函数"的替代方案是 Thompson sampling：从当前信念 b_t 中抽一个样本 θ，假定 θ 就是真实模型，用 dynamic programming 求最优动作。下一时刻，更新信念、抽取新样本、重解 MDP。这种做法的好处是不必再选启发式探索参数；缺点是 Thompson sampling 已知会过度探索，且每步重解 MDP 计算开销较大。
5.4 Model-Free Methods
与基于模型的方法不同，model-free 强化学习不需要显式构造转移与奖励模型。在高维问题中，避免显式模型非常有吸引力。
5.4.1 Incremental Estimation
很多 model-free 方法都对"从各状态出发期望折扣回报"做增量式估计。设有随机变量 X，要从样本 x₁:ₙ 估计其均值。n 个样本之后，估计量为
可以证明
α(n) 称为学习率（learning rate）。为保证收敛到均值，对 α 的限制相当宽松——它不必是 1/n。在强化学习应用中常用常值学习率，此时旧样本的权重按 (1−α) 指数衰减。用常值学习率，每观测到一个新样本 x 后的更新规则是
该更新规则将在后续几节反复出现，它与随机梯度下降有联系：更新量与"新样本—旧估计"之差成正比，"新样本—旧估计"之差称为 temporal difference error。
5.4.2 Q-Learning
Q-learning 是最流行的 model-free 强化学习算法之一。其核心思想是把 incremental estimation 应用到 Bellman 方程上：
不再使用 T 和 R，而是用观测到的下一状态 s′ 和奖励 r 得到如下增量更新规则：
Q-learning 的伪代码见算法 5.3。与基于模型的方法一样，仍需某种探索策略以保证 Q 收敛到最优状态—动作值函数。Q 可初始化为非零值以编码对环境的先验知识。
Algorithm 5.3 Q-learning
1: function QLearning
2: t ← 0
3: s0 ← initial state
4: Initialize Q
5: loop
6: Choose action a_t based on Q and some exploration strategy
7: Observe new state s_{t+1} and reward r_t
8: Q(s_t, a_t) ← Q(s_t, a_t) + α(r_t + γ max_a Q(s_{t+1}, a) − Q(s_t, a_t))
9: t ← t + 1
5.4.3 Sarsa
Q-learning 的一个替代是 Sarsa——名字来源于它每步用 (s_t, a_t, r_t, s_{t+1}, a_{t+1}) 来更新 Q 函数。它用"实际执行的动作"来更新 Q，而不像 Q-learning 那样对所有可能动作取 max。Sarsa 与算法 5.3 几乎一样，仅第 8 行替换为
在合适的探索策略下，a_{t+1} 会收敛到 Q-learning 中用于更新的 arg max_a Q(s_{t+1}, a)。虽然 Q-learning 与 Sarsa 都收敛到最优策略，但收敛速度因应用而异。
5.4.4 Eligibility Traces
Q-learning 和 Sarsa 的一个缺点是学习可能很慢。例如，假设环境中只有一个目标状态提供大额奖励，其他所有状态的奖励都为零。在经过若干次随机探索后到达目标状态——无论是 Q-learning 还是 Sarsa，都只更新"紧邻目标状态的前一状态"的状态—动作值；通往目标路径上的其他状态—动作值仍保持为零。需要大量探索才能把非零值慢慢传播到状态空间中的其他位置。
Q-learning 和 Sarsa 可以借助 eligibility traces 把"达到目标的功劳"分配给过去的状态和动作——把到达目标的奖励沿路径往回传播，功劳按指数衰减，因此离目标更近的状态被分配更大的状态—动作值。常用 λ 作为指数衰减参数，带 eligibility traces 的 Q-learning 和 Sarsa 因此常被记为 Q(λ) 和 Sarsa(λ)。
算法 5.4 给出一种 Sarsa(λ) 的实现。维护所有状态—动作对的指数衰减访问计数 N(s, a)；在状态 s_t 执行动作 a_t 时把 N(s_t, a_t) 加 1；随后对每个状态 s、每个动作 a，把 Q(s, a) 加上 αδN(s, a)，其中
完成更新后做衰减 N(s, a) ← γλN(s, a)。尽管 eligibility traces 在稀疏奖励环境中的影响最为显著，在奖励更均匀分布的一般环境中它也能加速学习。
Algorithm 5.4 Sarsa(λ)-learning
1: function SarsaLambdaLearning(λ)
2: Initialize Q and N
3: t ← 0
4: s0, a0 ← initial state and action
5: loop
6: Observe reward r_t and new state s_{t+1}
7: Choose action a_{t+1} based on some exploration strategy
8: N(s_t, a_t) ← N(s_t, a_t) + 1
9: δ ← r_t + γ Q(s_{t+1}, a_{t+1}) − Q(s_t, a_t)
10: for s ∈ S
11: for a ∈ A
12: Q(s, a) ← Q(s, a) + αδN(s, a)
13: N(s, a) ← γλN(s, a)
14: t ← t + 1
5.5 Generalization
到目前为止本章都假设状态—动作值函数可以用一张表来表示——这仅对小规模离散问题有用。状态空间变大时的问题不仅是状态—动作表变大，还包括"准确估计值函数"所需的经验量也变大。智能体必须从有限经验泛化到尚未访问过的状态。已经探索出多种方法，其中许多与 4.5 节的近似 dynamic programming 技术相关。
5.5.1 Local Approximation
local approximation 方法的假设是"相近的状态往往具有相近的状态—动作值"。一种常见做法是：在集合 S 内的有限个状态和集合 A 内的有限个动作上存储 Q(s, a) 的估计。把这些估计排成向量 θ，共有 |S|×|A| 个分量；与状态 s、动作 a 对应的分量记作 θ_(s,a)。若有"权重函数"满足 Σ_{s′} β(s, s′)=1 对所有 s 成立，则任意状态上的状态—动作值可近似为
可定义权重函数的向量化版本：
其中 s₁, …, s_{|S|} 是 S 内的状态。还可以定义一个两参数的版本 β，输入是一个状态与一个动作、返回长度为 |S|×|A| 的向量。β(s, a) 与 β(s) 完全一致，只是把"非 a 的那些动作"对应的元素设为 0。用这套记号可以把式 (5.27) 改写为
式 (5.29) 的线性近似可很自然地接入 Q-learning。设观察到由 s_t 经 a_t 转移到 s_{t+1}、获得奖励 r_t，则状态—动作值估计（由 θ 表示）的更新规则为
上述更新规则来自：把式 (5.29) 直接代入标准 Q-learning 更新规则，再把最后一项乘以 β(s_t, a_t) 以让"距 s_t 更近"的那些状态获得更大的更新量。
算法 5.5 给出该线性近似的 Q-learning 方法。若对状态—动作值有先验知识，可以相应地初始化 θ。该方法可自然地扩展到其他强化学习方法，如 Sarsa。
上述算法假设 S 内的点是固定的。但对某些问题，可调 S 内这些点的位置以得到更好的近似。这些位置可基于 temporal difference error 进行调整，例如用 self-organizing map 这类表示（参见 5.7 节文献）。已经探索过多种"何时适合向 S 添加新点"的判据，例如"新观测到的状态距 S 内所有状态超过某阈值"。虽然存储可能成为瓶颈，但有些方法干脆把所有观测到的状态都存下来。
Algorithm 5.5 Linear approximation Q-learning
1: function LinearApproximationQLearning
2: t ← 0
3: s0 ← initial state
4: Initialize θ
5: loop
6: Choose action a_t based on θ⊤β(s_t) and some exploration strategy
7: Observe new state s_{t+1} and reward r_t
8: θ ← θ + α(r_t + γ max_a θ⊤β(s_{t+1}, a) − θ⊤β(s_t, a_t)) β(s_t, a_t)
9: t ← t + 1
5.5.2 Global Approximation
global approximation 方法不依赖"距离"概念。一种这样的近似方法是感知器（perceptron）。感知器自 1950 年代起就被广泛用于以神经元为蓝本来完成各种学习任务。一个感知器有 m 个输入节点 x₁:m、一组权重 θ₁:m 与一个输出节点 q。输出节点的取值由下式决定：
感知器的结构见图 5.3a。
在 perceptron Q-learning 中，针对每个可用动作各有一个感知器（共 n 个）。输入基于状态，输出是状态—动作值。定义一组基函数 β₁, …, β_m 作用在状态空间上，与 5.5.1 节中的权重函数类似。各感知器的输入是 β₁(s), …, β_m(s)。若 θ_a 是动作 a 对应感知器的 m 个权重，则
像 5.5.1 节一样可以定义两参数版本的 β；把 θ 定义成"所有感知器的所有权重"的拼接，就可以写出
基于感知器近似的 Q-learning 与算法 5.5 形式上完全一致，只是 θ 表示感知器权重（而非值估计）、β 表示基函数（而非距离度量）。
感知器只能表示线性函数，而神经网络可以表示非线性函数。神经网络是感知器的网络，按输入层、隐藏层、输出层组织（见图 5.3b，图中省略了权重）。增加隐藏节点一般会提升网络所能表示的状态—动作函数的复杂度。
可以用 backpropagation 算法调整神经网络中的权重以减小 temporal difference error。其核心思想是：先调整"从隐藏节点连到输出节点的边"上的权重，方式与感知器学习类似；再计算隐藏节点的误差，并相应调整"从输入节点连到隐藏节点的边"上的权重。虽然这种形式的函数近似在收敛性上不能保证，但在多种领域都能给出满意的性能。
5.5.3 Abstraction Methods
abstraction 方法把状态空间划分成若干离散区域，并对每个区域估计状态—动作值。abstraction 方法往往采用基于模型的学习，相比 model-free 学习常常收敛更快。abstraction 方法常用决策树来划分状态空间。树的内部节点上是"对状态空间各维度的各种测试"，叶节点对应若干区域。
abstraction 方法有多种实现方式。一种方法是从一个"由单节点决策树表示的单一区域"起步，然后依次执行 acting、modeling、planning 三个阶段。在 acting 阶段，根据与当前状态 s 对应的那个区域的状态—动作值选动作。观察到由 s 经 a 转移到 s′、获得奖励 r 之后，把经验元组 (s, a, s′, r) 存到 s 对应的叶节点上。
在 modeling 阶段，决定是否要分裂节点。对所有叶节点上的经验元组，计算
其中 r 是观测到的奖励、U(s′) 是 s′ 对应叶节点的值。分裂叶节点的判据是"叶节点上的经验元组值是否来自不同分布"。一种做法是选"使分裂后叶节点上经验元组方差最小"的分裂。设定某个停止准则（如叶节点方差低于某阈值）后即停止分裂。
在 planning 阶段，用叶节点上的经验元组估计状态转移模型与奖励模型，再用 dynamic programming 求解所得到的 MDP。modeling 与 planning 过程所需的计算量远大于其他泛化方法，但该方法能在更少的环境交互下找到更好的策略。
5.6 Summary
- 强化学习是从经验中学习智能行为的一种计算方法。
- 探索与利用必须审慎地取得平衡。
- 一般而言，最优地解决探索问题不可行，但有多种 Bayesian 与启发式近似方法通常表现良好。
- 关键是要确定"过去多少步的动作应对后来获得的奖励负责"。
- 基于模型的强化学习包含"从经验中建立模型"与"用模型生成规划"两步。
- model-free 强化学习直接估计状态与动作的值，不依赖显式的转移与奖励模型。
- 由于与世界的交互有限，必须从观测到的奖励与状态转移中做泛化。
- 泛化有多种实现方式：值函数的局部近似、全局近似、状态抽象等。
5.7 Further Reading
Sutton 与 Barto 的经典著作《Reinforcement Learning: An Introduction》是经典强化学习领域的标准入门书，给出了该领域形成的历史综述 [2]。Wiering 与 Otterlo 编辑的文集对 Sutton 与 Barto 著作出版后该领域的大量研究给出了较新的综述 [3]。Kovacs 与 Egginton 对强化学习软件做了综述 [4]。
多年来，多臂 bandit 问题及其众多变体受到了相当多的关注 [5]。Gittins 提出了求解多臂 bandit 问题的 allocation index 概念 [1]。近期工作聚焦在提升 allocation index 的计算效率上 [6]、[7]。
基于模型的强化学习可以分为非 Bayesian 方法与 Bayesian 方法 [8]。非 Bayesian 方法一般采用 5.2 节讨论的最大似然估计。Dyna 方法由 Sutton 提出 [9]。prioritized sweeping 由 Moore 与 Atkeson 提出 [10]。
Bayesian 模型方法最近才开始受到较多关注 [11]。Duff 讨论了把基于模型的强化学习形式化为 Bayes-adaptive Markov decision process [12]。一般而言，对这种 belief state 形式化做精确求解是棘手的。Strens 把 Thompson sampling [14] 的概念应用到了基于模型的强化学习中 [13]。上一章给出的在线规划算法的若干变体已经被扩展到 Bayesian 基于模型的强化学习上，包括 sparse sampling [15] 与 Monte Carlo tree search [16]、[17]。
model-free 强化学习算法常用于"显式构造转移与奖励模型不可行"的场景。Q-learning 与 Sarsa 是两种常用的 model-free 方法。eligibility traces 是 Sutton 在 temporal difference learning 的语境下提出的 [18]，后被扩展到 Sarsa(λ) [19] 与 Q(λ) [20]、[21]。
该领域当前大量研究关注"从有限经验做泛化"。Busoniu 等人的近期著作《Reinforcement Learning and Dynamic Programming Using Function Approximators》综述了多种局部与全局函数近似方法 [22]。多年来已提出多种不同的 abstraction 方法 [23]–[26]。
虽然本章没有讨论，Bayesian 方法在 model-free 强化学习中也有一些工作。一种做法是维护"对状态—动作值的分布" [27]、[28]。还有 Bayesian 策略梯度方法，在一些场景下取得了不错的效果 [29]。multiagent 强化学习也未在本章讨论，Busoniu、Babuska 与 De Schutter 综述了该方向的研究现状 [30]。
本章个人批注
本章是全书"理论篇"中对"模型未知"问题的最集中处理——它把第 3、4 章的优化/动态规划思想扩展到经验学习场景。读完后我有几点感受：
第一，5.1.4 节给出的"用 belief state 把 bandit 问题提升为 MDP"是一个在概念上非常干净的视角：探索—利用的张力在 5.1.2 节用 beta-binomial 后验的解析形式解决，在 5.1.4 节则被进一步推到了 belief MDP 框架下并指向 Gittins index——这相当于把单状态的最优探索问题"完全"解决，把它的复杂度转移到一个可查表的 index 上。Gittins index 与 5.3 节 Bayes-adaptive MDP 的关系也很有趣：后者是一般多状态问题的"理论最优"形式，但用 §5.3.4 的话说"精确求解不可行"，所以 5.4–5.5 节实际上是用"启发式"或"近似"去逼近那个理论上完美的解。
第二，5.4.2 Q-learning 的式 (5.24) 与 5.4.4 Sarsa(λ) 的式 (5.26) 形成清晰对照：Q-learning 用 max，off-policy；Sarsa 用实际执行的动作，on-policy；eligibility trace 则是把"单步 TD 误差"沿时间反传的工具。书中说"两者都收敛到最优策略，但速度因应用而异"——我理解这是在回避一个微妙的稳定性问题：函数近似下的 Q-learning 在理论上不一定收敛，eligibility trace 也不能完全修补这个差距。
第三，5.5 节"局部 vs. 全局 vs. 抽象"三种泛化方法的并置是很有教学价值的设计：local 假设平滑性、global（perceptron/NN）放弃距离概念、abstraction（决策树）把状态离散化。书中没有明说但读者能看出，这恰好对应了 4.5 节中"近似 dynamic programming 的三种典型方式"——本章的"强化学习 + 泛化"实际上是把 4.5 节的近似思想搬到了样本驱动的设定上。这一点对第 7 章之后的应用章（collision avoidance、surveillance）会非常重要，因为真实任务的状态空间都很大。
最后，§5.7 Further Reading 暴露了一个隐含线索：classical RL 的引用集中在 1988–2013 年（Sutton 1988 TD、Sutton 1991 Dyna、Watkins 1989 Q-learning、Moore & Atkeson 1993 prioritized sweeping、Poupart 2006 analytic BAMDP、Strens 2000 Thompson sampling、Asmuth & Littman 2011 MCTS BAMDP）。这与第 4 章 Further Reading 中"online planning 占主导"的引用形成对照——RL 那一支更早成型，但 2010 年之后 BAMDP 思路 + MCTS 的结合（Asmuth、Guez 等）把它和在线规划打通了。下一章的"state uncertainty / POMDP"会接上这条线。
与上下章的衔接（一段话）
第 4 章把"已知模型、确定性可观察"下的序贯决策问题铺到了底（policy iteration / value iteration / 近似 DP / 在线搜索 / 策略搜索）；本章在第 4 章的基础上放宽了"模型已知"假设，把 transfer 与 reward 也变成要从经验中估计的未知量——这正是从"动态规划"跨入"强化学习"的入口。结构上，作者用 5.1 节单状态 bandit 把探索—利用讲透（β 后验 + Gittins index），再在 5.2–5.3 节把它推广到多状态（MDP）的两种处理方式——最大似然 + 启发探索 vs. Bayesian 信念空间上的 Bayes-adaptive MDP；接着 5.4 节跳到 model-free 一脉（Q-learning / Sarsa / eligibility traces），5.5 节用 4.5 节的近似 DP 思想给出三种泛化方案（局部 / 全局 / 抽象），最终在 5.6 节给出一个"模型学习 vs. 值学习 vs. 泛化"的三轴总结。第 6 章将进一步放宽"完全可观察"假设，转入 POMDP——5.3.3 节 Bayes-adaptive MDP 的 (s, b) 状态结构与 5.3.4 节末尾"求解精确 belief-MDP 不可行、下一章给出更好的方法"的伏笔，正是为了把第 6 章的 POMDP 框架自然引入；5.4 节末尾"model-free 与基于模型并立"则为后续 6.x 章关于"在线规划 + 信念跟踪"的算法（如 sparse sampling、POMCP）埋下接口。