Lecture 12: 快速强化学习（三）—— PAC-MDP、贝叶斯 MDP 与泛化探索（Fast RL: PAC-MDP, Bayesian MDPs, and Generalization）

目录 · ← l11 · l13 →

Lecture 12: 快速强化学习（三）—— PAC-MDP、贝叶斯 MDP 与泛化探索（Fast RL: PAC-MDP, Bayesian MDPs, and Generalization）

对应材料：官方 lecture12pre.pdf（54 页）/ lecture12post.pdf（54 页，含课上标注与答案）｜Week 8 周一（Feb 23, 2026）｜参考阅读：Sutton & Barto Chp 2, 8；Osband, Russo & Van Roy (NeurIPS 2013)；Strehl & Littman (MBIE-EB, 2008)；Bellemare et al. (Unifying Count-Based Exploration)；Lattimore & Szepesvári Bandit Algorithms Chp 19 一句话定位：L9–L11 把「探索」做成了 bandit 上的理论（regret / 贝叶斯 regret）；本讲把它抬升到 MDP——先建立 PAC-MDP 这一样本复杂度框架与 MBIE-EB / RMax 两个算法，用 Simulation Lemma 把「模型误差」翻译成「价值误差」，再用 PSRL 给出贝叶斯路线的对应物；最后落到全课最难的开放问题：当泛化与策略性探索必须同时满足时该怎么办。

12.1 概述

本讲回答的问题是：前面为「单步决策」建立的探索理论，能不能搬到「序列决策」？如果能，代价是什么？ 讲义第 11 页给出的答案是肯定的——框架（regret / 贝叶斯 regret / PAC）与思路（乐观面对不确定性 / 概率匹配）都平行地存在，但难度发生了质变：在 bandit 里「探索一个臂」只需再拉一次；在 MDP 里「探索一个状态-动作对」需要先想办法到达那个状态，而到达本身就要消耗样本。这就是 L11 末尾预告、本讲展开的核心张力。

讲义的 TOC（第 6 页）把内容分成六块，本讲严格按其组织：

本讲在知识链中的位置：它是「探索」这条线的收官讲。L9 给了评估框架与 UCB，L10 给了 UCB 的遗憾界证明与 bandit→MDP 的桥梁，L11 给了贝叶斯路线（Thompson 采样、Gittins），本讲把贝叶斯路线搬到 MDP（PSRL）并把 PAC 框架建立起来，然后指出这两条路在函数逼近下都还没有满意的理论——这正好把课程引向 L13–L15 的搜索与模型方法，以及 L16 的对齐议题。

12.2 核心概念的数学形式化

12.2.1 PAC 框架：从 regret 到「犯错的步数」

严格定义（讲义 p8–p9）。给定 $\epsilon>0$ 与 $\delta\in(0,1)$，一个 RL 算法 $\mathcal{A}$ 被称为 PAC（Probably Approximately Correct） 的，如果：在每一个时间步 $t$，它选择的动作 $a_t$ 以至少 $1-\delta$ 的概率是 $\epsilon$-最优的

并且除了多项式多步之外（on all but a polynomial number of time steps）这一性质都成立；这里的多项式是关于问题参数的，即

直观解释。「PAC」把一个算法「好不好」的问题拆成两个可分别量化的部分：

• probably（大概率）：允许它以小概率 $\delta$ 出错——RL 的采样是随机的，要求 100% 正确不可能；
• approximately correct（近似正确）：不要求动作就是最优的，只要求它的价值离最优不超过 $\epsilon$——在奖励尺度固定时，”差一点点”是可以接受的。

于是 PAC 关注的是 犯错的次数，而不是遗憾的累积值。

与 regret 框架的对比（讲义 p7–p8）。讲义明确指出二者的出发点是同一件事：

“Theoretical regret bounds specify how regret grows with T. Could be making lots of little mistakes or infrequent large ones. May care about bounding the number of non-small errors.”（regret 界只规定遗憾随 $T$ 增长的方式；算法可能在犯许多小错或偶尔犯大错；而我们真正关心的可能只是非小错误的次数。）

具体示例：为什么 MDP 里的 PAC 比 bandit 难。 讲义第 13 页的 PAC-MDP 定义把多项式里的参数明确写成 $(\vert \mathcal{S}\vert ,\vert \mathcal{A}\vert ,\frac{1}{1-\gamma},\frac{1}{\epsilon},\frac{1}{\delta})$——注意这里出现了 $\frac{1}{1-\gamma}$，而 bandit 的 PAC 里没有。原因就是延迟后果：在 MDP 中，一个糟糕动作的代价会通过 $\gamma$ 往后传播，需要 $\frac{1}{1-\gamma}$ 的因子才能把折扣下的长期误差归一到即时尺度。这也是本讲与 L9 最本质的差别。

讲义的第 14 页与第 9 页还给出两条重要的实现线索：

1. “Most PAC algorithms based on optimism or Thompson sampling”（大多数 PAC 算法基于乐观性或 Thompson 采样）；
2. “Some PAC algorithms using optimism simply initialize all values to a (specific to the problem) high value”（有些基于乐观性的 PAC 算法，只是把所有值初始化成一个问题相关的高值）。

第 2 条就是 RMax / 乐观初始化的全部思想——本讲 12.3.2 会证明：单靠”把没试过的东西想得很好”这一招，就能换来 PAC 保证。

12.2.2 MBIE-EB：带探索奖励的模型估计

严格定义（讲义 p12、p37，Strehl & Littman 2008）。MBIE-EB（Model-Based Interval Estimation with Exploration Bonus，带探索奖励的基于模型的区间估计）维护每个 $(s,a)$ 的经验计数与经验模型，并在 Q 值里加一项与不确定度成正比的正奖励：

直观解释。$\frac{\beta}{\sqrt{n(s,a)}}$ 就是「不确定度」的化身：一个 $(s,a)$ 被访问得越多，$n$ 越大，这项就越小，智能体越不会被它吸引；反之，从没去过的地方这一项很大，等于在同它说”这里也许藏着好东西，值得去看看”。这正是 L9 讲的「乐观面对不确定性」原则在 MDP 里的落地——只不过 bonus 的形状从 UCB 的 $\sqrt{\frac{2\ln t}{n_t(a)}}$ 换成了 $\frac{\beta}{\sqrt{n(s,a)}}$。

算术示例。取 $\vert \mathcal{S}\vert =94,\ \vert \mathcal{A}\vert =4,\ m=1,\ \delta=0.1$、$\gamma=0.9$，则

于是某个被访问过 $n=1$ 次的 $(s,a)$ 拿到 bonus $\approx 21.1$，而 $n=100$ 次时只剩 $\approx 2.1$——下降速率是 $1/\sqrt{n}$，与 Hoeffding 置信区间的收缩速率一致（L9 已证明 $n\to5n$ 时半径恰好缩小 $\sqrt{5}$ 倍）。

「与理论的对应」：MBIE-EB 之所以是 PAC 算法（讲义 p14 “MBIE-EB is a PAC RL Algorithm”），关键在于 bonus 的形状与置信区间匹配：$1/\sqrt{n(s,a)}$ 正好是经验均值估计误差的量级，因此”乐观值”是真的上置信界，而不是随便加的噪声。

12.2.3 Simulation Lemma：把模型误差翻译成价值误差

严格定义（讲义 p15–p16）。设两个 MDP 的奖励与转移之差为

对任意固定策略 $\pi$，令 $\Delta:=\max_s\vert V_1^\pi(s)-V_2^\pi(s)\vert $，则

推导（讲义原文逐步）。从动作值出发，插入并减去同一项：

三行分别是：三角不等式、把 $T_1$ 的系数提出来（第一项用 $\Delta$ 的界、第二项用 $\beta$ 与 $V_{max}$ 的界）、代回 $\Delta$ 的定义。于是 $\Delta\le\alpha+\gamma\Delta+\gamma V_{max}\beta$，移项得 $(1-\gamma)\Delta\le\alpha+\gamma V_{max}\beta$，即所证。

直观解释。这条引理回答的是：「如果我的模型有一点不准，我的价值估计会错多少？」答案的结构非常自然：

• 分子有两项：奖励模型误差 $\alpha$ 与 转移模型误差 $\gamma V_{max}\beta$（转移错了，后面所有价值都被带偏，所以要乘 $V_{max}$）；
• 分母 $1-\gamma$ 是放大因子：模型误差会沿着时间累积，$\gamma$ 越接近 1，同样的模型误差造成的价值误差越大。

具体示例（真实运行，脚本 L12_nav_pac.py 实验 2）。在 12.3.2 的 10×10 导航 MDP 上，令 MDP₁ 为打滑概率 $\mathrm{slip}=0.1$ 的真实环境、MDP₂ 为 $\mathrm{slip}=0$ 的确定性环境，用同一个最优策略 $\pi$ 分别评估：

这张表本身就是一条重要结论：Simulation Lemma 的界成立但极其保守（松弛 528 倍）。这与 L9 中「Hoeffding 界成立但很松」的观察完全同构——理论界的作用是给出正确的量级与依赖关系，而不是给出可用的数值。

与理论的对应：这条引理是 MBIE-EB 与 RMax 的证明引擎。要把「探索奖励 $R^+(s,a)=\frac{\beta}{\sqrt{n(s,a)}}$」翻译成「价值估计的置信区间」，必须用到它；反过来，模拟误差界也解释了为什么 PAC-MDP 的多项式里会出现 $\frac{1}{1-\gamma}$ 的三次方（讲义 p51 讨论的经典界为 $O(\frac{\vert \mathcal{S}\vert \vert \mathcal{A}\vert }{\epsilon(1-\gamma)^3})$ 量级）。这也解释了我们下面实验中的一个现象：$\gamma=0.99$ 时理论量级达 $3.76\times10^9$ 步，而 $\gamma=0.9$ 时只有 $3.76\times10^6$ 步——差三个数量级。

12.2.4 贝叶斯 MDP 与 PSRL

严格定义（讲义 p18–p23）。

• 贝叶斯 MDP（Bayesian MDP）：不再把 $P$ 与 $R$ 当作固定但未知的常量，而是当作随机变量，维护它们的后验分布 $p[P,R\mid h_t]$，其中 $h_t=(s_1,a_1,r_1,\dots,s_t)$ 是历史。
• 概率匹配（probability matching）在 MDP 中的形式（讲义 p22）：

• PSRL（Posterior Sampling for Reinforcement Learning，后验采样强化学习，Osband, Russo & Van Roy, NeurIPS 2013）：其实就是「MDP 版的 Thompson 采样」——每个 episode 从后验里采样一个完整的 MDP，对它求最优策略，然后执行整回合。

直观解释。PSRL 与 L11 的 Thompson 采样逐一对应：

为什么”每个 episode 采一次”而不是”每步采一次”？ 这是 PSRL 与 bandit-TS 的关键工程差别：MDP 里对每个 $(s,a)$ 都独立采样会破坏模型的内部一致性，而且每步重规划代价极高。按 episode 采样让采样出来的 MDP 在整回合内保持一致，于是规划的答案在整回合内都自洽——这就是”在幻想的世界里过完一生”。

具体示例（真实运行，脚本 L12_explore.py 实验 2）。在 5×5 导航 MDP（起点左下、目标右上、$\mathrm{slip}=0.1$、$\gamma=0.9$、每个 episode 最多 30 步、共 30 个 episode）上：

这张表要诚实读：在这个环境上「后验均值 + 贪心」的回报反而更好（291 < 628），因为该 MDP 近乎确定性、目标奖励一旦发现就能反复利用，不需要额外探索；但 PSRL 覆盖了 24/25 个状态而后者只覆盖 13/25——「从后验采样」带来的探索性是真的，只是这个小环境太容易，不足以把它兑换成回报。这与 L10 中「T=10⁴ 时 UCB 还输给 ε-greedy」是同一类现象：探索的收益需要足够困难的环境与足够长的时域才能兑现。

与 bandit 的对比：在 bandit 里 TS 的后验是共轭的（Beta-Bernoulli，L11），更新是闭式的 $(\alpha,\beta)\leftarrow(\alpha+r,\beta+1-r)$；在 MDP 里转移的后验需要 Dirichlet 分布（讲义 p19 给出 Beta 的共轭性，MDP 是其多元推广），$T(\cdot\mid s,a)\sim\mathrm{Dirichlet}(\mathbf{c})$，观测到转移后把对应的计数加一即可。这就是实验脚本里 np.random.dirichlet(c * prior + counts) 那一行的来历。

12.2.5 从表格到泛化：为什么「探索 + 泛化」是开放问题

严格定义（讲义 p30–p34）。

• 上下文老虎机（Contextual Bandit）：$(\mathcal{A},\mathcal{R})$ 扩展为带上下文/状态 $\mathcal{S}$ 的形式，

• 奖励的线性模型（讲义 p32）：

其中 $\phi(s,a)$ 是特征。这是「泛化」的入口：不再为每个 $(s,a)$ 存一个奖励估计，而是学一个 $d$ 维参数 $\theta$。

• Disjoint 线性上下文 bandit（讲义 p33）：每个臂有自己的参数，

直观解释。泛化的价值在于用少量参数描述大量状态-动作对。讲义第 31 页引用 Lattimore & Szepesvári 的 Figure 19.1 对比了「多臂老虎机」与「上下文老虎机」的 regret：前者必须把每个臂都试够，regret 随臂数线性增长；后者一旦学到 $\theta$（$d$ 维），就能推断出从未见过的上下文上每个臂的价值。所以上下文 bandit 的 regret 只依赖特征维度 $d$，而不依赖上下文空间的大小——这就是泛化的收益。

具体示例（真实运行，脚本 L12_explore.py 实验 3）。10 个臂、$d=5$ 维特征、$\phi(s)\sim\mathcal{N}(0,I_5)$、$\theta_a\sim\mathcal{N}(0,I_5)$、$T=2000$、噪声 $\sigma=0.5$：

三点观察：(1) 线性 UCB 与线性 TS 的最好结果都在 $10^2$ 量级，而 ε-greedy 在 $5\times10^2$–$10^3$ 量级，相差约一个数量级；(2) ε-greedy 的 $\epsilon$ 越大越差（867.8 > 513.6）——因为它把探索预算浪费在与上下文无关的随机抖动上；(3) 这正是讲义 p34 的要点：在泛化设定下，不确定性必须通过”参数 $\theta$ 的不确定集”来刻画，而不是靠一个与 $\phi(s,a)$ 无关的常数概率。（线性 UCB 的 bonus 用的是 $\alpha\sqrt{\phi^\top A_a^{-1}\phi}$，其中 $A_a=\lambda I+\sum\phi\phi^\top$——它把”哪些方向已经见过”编码进了协方差矩阵。）

为什么这是开放问题。讲义 p28–p29 反复强调：

“Active area of ongoing research: combine generalization & strategic exploration.”

难点在于：表格型探索的计数 $n(s,a)$ 在泛化下失去了意义。当状态空间连续或巨大时，几乎每个状态都只被访问一次，$n(s,a)=1$ 或 $0$，计数奖励退化为常数（要么到处加、要么形同虚设）。解决方案必须把「计数」从状态空间搬到特征空间或参数空间：

• 基于特征的计数 / 伪计数（pseudo-count，讲义 p38–p41）：用密度模型 $P(s)$ 的估计给出伪计数 $\hat n(s)$，再以 $\frac{\beta}{\sqrt{\hat n(s)}}$ 作为奖励。讲义 p41 引用 Bellemare et al. 的 Unifying Count-Based Exploration and Intrinsic Motivation，展示该方法在 Montezuma’s Revenge（Atari 中最著名的困难探索游戏）上 “Enormously better than standard DQN with ε-greedy approach”。
• 对 $Q^$ 的后验采样（讲义 p43–p44）**：Bootstrapped DQN（Osband et al., NIPS 2016）用 $C$ 个 bootstrap 训练的 DQN 近似 $Q^$ 的后验，行动时在其中一个上取 $\arg\max$；以及 Efficient Exploration through Bayesian Deep Q-Networks（Azizzadenesheli & Anandkumar, 2017）在最后一层做贝叶斯线性回归并对后验保持乐观。讲义对二者的评价很克制：“Some performance gain, not as effective as reward bonus approaches”、“not as good as reward bonuses in some cases”——奖励 bonus 路线在实践中仍更有效**。
• 元学习探索（讲义 p45–p47）：DREAM（Liu et al., NeurIPS 2022）与 Decision-Pretrained Transformer（DPT，Lee, Xie, Pacchiano, Chandak, Finn, Nachum & Brunskill, NeurIPS 2023）。核心洞察：“Training to predict $a^$ mimics Thompson Sampling but can capture a much richer set of priors”*——把”预测最优动作”当作训练目标，就在模仿 Thompson 采样，而且能容纳远比共轭先验更丰富的先验族。这是把 L11 的贝叶斯思想与 L8 的大规模序列建模接起来的桥梁。

具体示例（真实运行，脚本 L12_explore.py 实验 1）。在 11 状态长链条（动作「前进」成功概率 0.8，只有走满 10 步到终点才得 +1）上：

这张表极其有说服力：贪心与 ε-greedy 在 6000 步内一次都没到过终点（连 ε-greedy 都只访问了 3 个状态——因为一旦回到起点附近，随机抖动不足以支撑连续 10 次成功前进），而加上计数奖励后 6000 步内到达 331 次。理论上随机策略走完这条链需要 $10\cdot0.8^{-10}\approx 93$ 步（方差极大），这与观察到的首次到达 426 步同量级。这就是”稀疏奖励 + 长链条”下策略性探索不可替代的证据，也是 Montezuma’s Revenge 困难性的缩影。

12.3 算法伪代码与完整推导

12.3.1 算法：MBIE-EB（带探索奖励的模型估计）

输入:
  - 精度 ε > 0，失败概率 δ ∈ (0,1)，采样阈值 m
  - 折扣因子 γ，奖励上界 R_max
输出:
  - 在除多项式多步外均为 ε-最优的策略

1. β = (1/(1-γ)) · sqrt( (1/2) · ln(2|S||A|m/δ) )
2. 初始化计数与模型:
     n_sas(s,a,s') = 0,  n_sa(s,a) = 0,  r_c(s,a) = 0      对所有 s,a,s'
3. 初始化乐观 Q:
     Q̃(s,a) = 1/(1-γ)                                      对所有 s,a
4. t = 0, s_t = s_init
5. loop
6.     a_t = argmax_a Q̃(s_t, a)                    // 用"加过 bonus 的"Q 选动作
7.     执行 a_t，观测 r_t 与 s_{t+1}
8.     n_sa(s_t,a_t) += 1
       n_sas(s_t,a_t,s_{t+1}) += 1
9.     r_c(s_t,a_t) = [ r_c(s_t,a_t)·(n_sa(s_t,a_t)-1) + r_t ] / n_sa(s_t,a_t)   // 增量均值
10.    R̂(s_t,a_t) = r_c(s_t,a_t)
       T̂(s'|s_t,a_t) = n_sas(s_t,a_t,s') / n_sa(s_t,a_t)   对所有 s'
11.    repeat until converged:                     // 在经验模型上做值迭代
12.        Q̃(s,a) = R̂(s,a) + γ Σ_{s'} T̂(s'|s,a) max_{a'} Q̃(s',a')
                            + β / sqrt(n_sa(s,a))   对所有 s,a
13.    t += 1

「算法逻辑解说」：

• 第 1 步：$\beta$ 的取值直接由 Simulation Lemma 与 Hoeffding 型置信区间推导而来——$\frac{1}{1-\gamma}$ 是把”一步的模型误差”放大成”长期价值误差”的因子，$\sqrt{\frac12\ln(2\vert \mathcal{S}\vert \vert \mathcal{A}\vert m/\delta)}$ 则是同时对所有 $(s,a)$ 保持置信度所需的联合界（union bound）开销。
• 第 3 步（乐观初始化）：把所有 $Q$ 初始化成 $\frac{1}{1-\gamma}$，等于”假设每个动作都能拿到最高奖励到永远”。
• 第 9 步：用增量均值更新经验奖励，而不是固定步长的指数滑动平均——因为 MBIE-EB 需要 $\hat R$ 无偏且方差随 $n$ 收缩，才能让置信区间成立（这一点与 L3/L4 中”$\alpha$ 固定则永不收敛”的讨论正好相反）。
• 第 12 步：这是模型规划 + 探索奖励的合体。注意 bonus 加在规划的目标里而不是直接加在环境奖励上，效果等价但对乐观性的解释更清楚：$\tilde Q$ 是 $Q^*$ 的上置信界。

「与理论的对应」：MBIE-EB 是 PAC 算法（讲义 p14）。证明思路是：由 Simulation Lemma，只要 $n(s,a)$ 足够大，$\hat R,\hat T$ 的误差就小到使 $\tilde Q$ 与真 $Q^$ 的差不超过 $\epsilon$；而 bonus 保证在 $n$ 还小时 $\tilde Q$ 不会低估 $Q^$（乐观性），因此智能体会持续选择那些”可能被低估”的 $(s,a)$，直到它们被采样足够多次。两步合起来给出「非 $\epsilon$-最优步数是多项式」的结论。

12.3.2 算法：RMax（乐观初始化）

输入:
  - 采样阈值 m（一个 (s,a) 被访问 m 次后视为"已知"）
  - 奖励上界 R_max，折扣因子 γ
输出:
  - 除多项式多步外 ε-最优的策略

1. 构造"乐观 MDP" M̂:
     对每个 (s,a):
       若 n(s,a) < m（未知）:  R̂(s,a) = R_max,  T̂(s'|s,a) = 1{s' = s}   // 自环
       若 n(s,a) ≥ m（已知）:  R̂(s,a) = 经验均值,  T̂ = 经验转移频率
2. 在 M̂ 上用值迭代求 Q̃, π̃
3. loop
4.     执行 π̃(s_t)，观测 r_t, s_{t+1}
5.     更新计数 n(s_t,a_t) += 1 与经验模型
6.     若某个 (s,a) 的计数恰好跨过 m: 重新规划（重跑第 2 步）
7.     t += 1

「算法逻辑解说」：RMax 与 MBIE-EB 的区别在乐观性的表达方式：

• MBIE-EB 把乐观性做成连续的 bonus $\frac{\beta}{\sqrt{n}}$，即使 $n$ 很大也保留一个小的正值；
• RMax 把乐观性做成二值的：未知的 $(s,a)$ 一律给最乐观的 $R_{max}$ 与自环转移（自环意味着”待在原地重复拿 $R_{max}$”，于是 $Q=R_{max}+\gamma R_{max}+\dots=\frac{R_{max}}{1-\gamma}=V_{max}$，是理论上界）。

「数学推导」：RMax 的样本复杂度

设 $m$ 为”已知”阈值，$R_{max}$ 为奖励上界，$V_{max}=\frac{R_{max}}{1-\gamma}$。证明分三步：

1. 每个 $(s,a)$ 被”探索到已知”的次数：因乐观初始化，只要某个 $(s,a)$ 是未知的且从某个可达状态被选择，它的 $Q$ 值就会被算成 $V_{max}$，从而至少与最优值一样大，智能体会优先选择它。因此每个 $(s,a)$ 会被访问到 $m$ 次；总步数被 $\vert \mathcal{S}\vert \vert \mathcal{A}\vert m$ 所界（每一步最多把一个 $(s,a)$ 的计数 +1）。
2. 已知部分的模型误差：由 Hoeffding 不等式与联合界，要让 $\vert \hat R-R\vert \le\epsilon_R$ 与 $\vert \hat T-T\vert _1\le\epsilon_T$ 对所有 $(s,a)$ 以概率 $1-\delta$ 成立，需要

1. 把模型误差翻译成价值误差：由 Simulation Lemma（12.2.3），

要让这个量 $\le\epsilon$，需要 $\epsilon_R=O(\epsilon(1-\gamma))$、$\epsilon_T=O\big(\frac{\epsilon(1-\gamma)^2}{\gamma V_{max}}\big)$。把 $V_{max}=\frac{R_{max}}{1-\gamma}$ 代入并整理，得到经典的 PAC-MDP 样本复杂度量级

（不同文献的具体指数略有差异；讲义 p51 讨论的是”已经存在 tight minimax 结果”，本处只给出量级与依赖关系：对 $\vert \mathcal{S}\vert ,\vert \mathcal{A}\vert $ 是多项式，对 $\frac{1}{\epsilon},\frac{1}{1-\gamma},\frac{1}{\delta}$ 也是多项式——这正是 PAC-MDP 的定义要求。）

「与理论的对应」：RMax 是讲义第 9 页那句 “Some PAC algorithms using optimism simply initialize all values to a (specific to the problem) high value” 的完整实现。它与值迭代（L2）共享同一个规划内核，唯一的新东西是“未知即乐观”的模型构造。

「具体示例（真实运行，脚本 L12_nav_pac.py 实验 3）」。在 10×10 导航 MDP 上跑 1200 步 RMax，用真实 $Q^*$ 判定所选动作是否 $\epsilon$-最优（$\epsilon=0.1$）：

读法：(1) $m$ 越大（要求更多样本才”相信”模型），首次到达目标越晚（146→331、116→418），因为智能体要花更多步去确认每个 $(s,a)$；(2) 违反 $\epsilon$-最优的步数在几百的量级，而理论界是 $3.76\times10^6$（$\gamma=0.9$）到 $3.76\times10^9$（$\gamma=0.99$）——界比实测松了 4–7 个数量级，与 Simulation Lemma 松弛 528 倍是同一回事；(3) 覆盖状态数在 $m=3$ 时最完整（93/94），说明 $m$ 太小会让模型不可靠、太大又浪费探索预算——$m$ 是 RMax 的核心超参数；(4) 每 1200 步只需 207–373 次重规划（平均每 3–6 步一次），因为只有”已知集发生变化”时才需要重算——这解释了为何 RMax 比每步都要重规划的 MBIE-EB 省算力。

12.3.3 算法：PSRL（后验采样强化学习）

输入:
  - 动力学与奖励模型在各 (s,a) 上的先验 p(R_a^s), p(T(s'|s,a))
  - episode 数 K，每 episode 时域 H，折扣因子 γ
输出:
  - 一个随数据不断改进的策略

1. 初始化每个 (s,a) 的先验 p(R_a^s), p(T(s'|s,a))
2. 初始化状态 s_0
3. for k = 1..K do                          // 每个 episode
4.     采样一个 MDP M:
5.        对每个 (s,a):
6.            采样动力学 T(s'|s,a) ~ p(T(s'|s,a) | h)      // Dirichlet 后验
7.            采样奖励模型 R(s,a)   ~ p(R(s,a) | h)
8.     在 M 上做规划（如值迭代）得到 Q*_M
9.     for t = 1..H do
10.        a_t = argmax_a Q*_M(s_t, a)                   // 整回合都用同一个 M
11.        执行 a_t，观测 r_t 与 s_{t+1}
12.    end for
13.    用 Bayes 法则更新后验 p(R_{a_t}^{s_t} | r_t), p(T(s'|s_t,a_t) | s_{t+1})
14. end for

「算法逻辑解说」：注意第 4–8 步与第 9–12 步的层级关系：采样与规划每 episode 一次，而动作选择每步一次。这带来两个重要性质：

• 内部一致性：整个 episode 内 $T$ 与 $R$ 是固定的，所以 $Q^*_M$ 在整个 episode 内自洽——智能体是在一个”幻想世界”里完整地过完一生，而不是每步换一个世界。
• 计算代价：每 episode 一次规划，代价 $O(\vert \mathcal{S}\vert ^2\vert \mathcal{A}\vert )$（值迭代一轮）乘迭代次数。相比 Q-learning 的 $O(1)$ 每步更新，PSRL 的每步计算代价高得多，但它换来了样本效率（讲义 p24 的多选题正是在考这一点：TS 的”每步计算代价与 Q-learning 相同”是错的）。

「与理论的对应」：PSRL 是 L11 中 “Thompson sampling implements probability matching” 在 MDP 上的直接推广。讲义 p22 给出概率匹配的 MDP 形式（见 12.2.4 的公式）——PSRL 的 $a_t=\arg\max_a Q^*_M(s_t,a)$ 正是以「$a$ 是最优动作的后验概率」为概率来选择动作。

「数学推导：为什么 PSRL 有贝叶斯 regret 界」

思路与 L10 的 UCB 证明同源，但走贝叶斯路线：

1. 贝叶斯 regret 的定义（讲义 p49，与 L11 一致）：

关键差别：先验本身被平均掉了。因此”简单”的先验会让贝叶斯 regret 变小——这也意味着贝叶斯 regret 界不能直接与最坏情形 regret 界比较。

1. 习题课式的分析框架（Osband & Van Roy 的”自归一化”论证，此处给出结构）：

第一项是”采样模型中最优值与所选值之差的平方”（衡量信息价值），第二项计数”信息量还很大的步数”。因为每步都在削减关于 $M$ 的不确定度，而总不确定度是有限的（先验的熵），所以第二项只能增长到某个有限量级——由此得到 $\tilde O\big(H\vert \mathcal{S}\vert \sqrt{\vert \mathcal{A}\vert T}\big)$ 量级的界（不同版本常数与指数有差异）。直观上，这个界说的是：”PSRL 只在还有信息可学的时候付学费。”

1. $T=1$ 的检验：当 $T=1$ 时 PSRL 退化为”按先验采样一个 MDP 并执行其最优动作”，贝叶斯 regret 就是”先验下的期望次优性”——这不是 0，而是由先验质量决定的常数。这正是 L11 中「先验质量决定 TS 表现」的结论。

「具体示例（真实运行，脚本 L12_explore.py 实验 2）」：见 12.2.4 的表格（PSRL 覆盖 24/25 状态 vs 后验均值 13/25）。

12.3.4 算法：线性上下文 bandit 上的 UCB 与 TS

输入:
  - 特征映射 φ(s,a) ∈ R^d，正则化 λ > 0，探索参数 α（UCB）或 ν（TS）
输出:
  - 逐步改进的动作选择

# 记 A_a = λI + Σ_{τ: a_τ=a} φ_τ φ_τ^T,  b_a = Σ_{τ: a_τ=a} r_τ φ_τ
# 则 θ̂_a = A_a^{-1} b_a 是岭回归解

UCB 版本:
1. loop
2.     观测上下文 s_t，构造 φ(s_t,a) 对所有 a
3.     对每个 a: Δ_a = α · sqrt( φ(s_t,a)^T A_a^{-1} φ(s_t,a) )     // 不确定度
4.     a_t = argmax_a [ θ̂_a^T φ(s_t,a) + Δ_a ]                      // 乐观
5.     执行 a_t，观测 r_t
6.     更新 A_{a_t} += φφ^T,  b_{a_t} += r_t φ
7. end loop

TS 版本:
1. loop
2.     观测上下文 s_t
3.     对每个 a: 采样 θ̃_a ~ N( θ̂_a, ν^2 A_a^{-1} )                 // 从后验采样
4.     a_t = argmax_a θ̃_a^T φ(s_t,a)                                // 概率匹配
5.     执行 a_t，观测 r_t，更新 A_{a_t}, b_{a_t}
6. end loop

「算法逻辑解说」：

• 第 3 步的 $\sqrt{\phi^\top A_a^{-1}\phi}$ 是 L9 中 $\sqrt{\frac{2\ln t}{n_t(a)}}$ 在泛化设定下的推广。它衡量的是特征空间中的方向不确定度：如果 $\phi$ 落在已经被观测过的方向上，$A_a^{-1}$ 在该方向上就小，bonus 小；如果 $\phi$ 指向从未探索过的方向，bonus 就大。这就是”把计数从状态空间搬到特征空间”的具体机制。
• TS 版本的 $\mathcal{N}(\hat\theta_a,\nu^2A_a^{-1})$ 是线性高斯模型下的精确后验（共轭），与 L11 中 Beta 后验的地位完全对应。

「数学推导：为什么只需要 $\theta$ 的不确定度就能刻画 $r$ 的不确定度」（讲义 p34 的思考题）

因为 $r=\theta^\top\phi(s,a)+\epsilon$，其中 $\phi(s,a)$ 是已知的确定性函数、$\epsilon$ 是已知方差的噪声。所以给定 $\theta$ 的分布，$r$ 的分布就完全确定了：

换句话说，$r$ 的不确定度是 $\theta$ 的不确定度在 $\phi$ 方向上的投影。因此”在 $d$ 维参数空间维护一个不确定集”就足以在所有 $(s,a)$ 上给出正确的置信区间——这正是泛化能成立的数学根源，也是为什么上下文 bandit 的 regret 只依赖 $d$ 而不依赖状态数。

「实验观察」：见 12.2.5 的表格。核心结论：2000 步内线性 UCB（$\alpha=1$）达 regret 152.9、线性 TS（$\nu=0.5$）达 150.0，而 ε-greedy 为 513.6–867.8——相差约一个数量级，且 ε-greedy 的 $\epsilon$ 越大越差。

12.4 代码实现与实验分析

12.4.1 代码块一：导航 MDP 的 PAC 门槛、Simulation Lemma 与 RMax

"""CS234 L12 代码块 1：导航 MDP 的 PAC 门槛、Simulation Lemma 与 RMax 样本复杂度"""
import numpy as np
import matplotlib
matplotlib.use("Agg")
from collections import deque
np.random.seed(0)

# -------- 导航 MDP：10x10 网格，第 5 列上半部是墙，只有 (6,5) 一个缺口 --------
GRID = np.zeros((10, 10), dtype=int)
GRID[0:7, 5] = 1
GRID[6, 5] = 0
START, GOAL = (9, 0), (0, 9)
free = [(r, c) for r in range(10) for c in range(10) if GRID[r, c] == 0]
idx = {s: i for i, s in enumerate(free)}
NS, NA = len(free), 4
DELTA = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def build_model(slip):
    """P[i,a] = 下一状态分布；R[i,a] = 期望即时奖励（目标格吸收且给 +1）"""
    P = np.zeros((NS, NA, NS)); R = np.zeros((NS, NA))
    for s in free:
        i = idx[s]
        for a in range(NA):
            if s == GOAL:
                P[i, a, i] = 1.0; R[i, a] = 1.0; continue
            r, c = s
            for aa, pp in zip([a, (a + 1) % 4, (a - 1) % 4], [1 - slip, slip / 2, slip / 2]):
                dr, dc = DELTA[aa]; nr, nc = r + dr, c + dc
                if not (0 <= nr < 10 and 0 <= nc < 10) or GRID[nr, nc] == 1:
                    nr, nc = r, c
                P[i, a, idx[(nr, nc)]] += pp
                if (nr, nc) == GOAL:
                    R[i, a] += pp * 1.0
    return P, R

def value_iteration(P, R, gamma=0.99, tol=1e-10):
    V = np.zeros(NS); sweeps = 0
    while True:
        Q = R + gamma * P @ V
        Vn = Q.max(axis=1); sweeps += 1
        if np.max(np.abs(Vn - V)) < tol:
            return Vn, Q, sweeps
        V = Vn

def policy_eval(P, R, pi, gamma):
    Ppi = np.array([P[i, pi[i]] for i in range(NS)])
    Rpi = np.array([R[i, pi[i]] for i in range(NS)])
    return np.linalg.solve(np.eye(NS) - gamma * Ppi, Rpi)

def bfs_dist():
    dist = {START: 0}; dq = deque([START])
    while dq:
        cur = dq.popleft()
        for a in range(NA):
            dr, dc = DELTA[a]; nr, nc = cur[0] + dr, cur[1] + dc
            if 0 <= nr < 10 and 0 <= nc < 10 and GRID[nr, nc] == 0 and (nr, nc) not in dist:
                dist[(nr, nc)] = dist[cur] + 1; dq.append((nr, nc))
    return dist

GAMMA, SLIP, EPS = 0.99, 0.1, 0.1
P, R = build_model(SLIP)
Vstar, Qstar, sweeps = value_iteration(P, R, GAMMA)
Vdet, _, _ = value_iteration(*build_model(0.0), GAMMA)
d = bfs_dist()[GOAL]

print("=" * 76)
print("实验 1：导航 MDP 与 PAC 的 ε-最优门槛（讲义 p7-p13）")
print("=" * 76)
print(f"可通行状态数 |S| = {NS}, 动作数 |A| = {NA}, |S||A| = {NS*NA}")
print(f"值迭代收敛用 {sweeps} 轮")
print(f"V*(start)：打滑 = {Vstar[idx[START]]:.6f}，确定性 = {Vdet[idx[START]]:.6f}")
print(f"最短距离 d(start→goal) = {d}；确定性闭式 γ^d/(1-γ) = {GAMMA**d/(1-GAMMA):.6f}")
Ppi, Rpi = P.mean(axis=1), R.mean(axis=1)
Vrand = np.linalg.solve(np.eye(NS) - GAMMA * Ppi, Rpi)
print(f"均匀随机策略 V^rand(start) = {Vrand[idx[START]]:.6f}")
ok = int(np.sum(Vrand >= Vstar - EPS))
print(f"ε={EPS} 时随机策略达到 ε-最优的状态数 = {ok} / {NS}  ({ok/NS*100:.1f}%)")
print(f"V*(goal) = {Vstar[idx[GOAL]]:.3f}（吸收自环 + 每次得分 ⇒ ≈ 1/(1-γ)）")

print()
print("=" * 76)
print("实验 2：Simulation Lemma 的数值验证（讲义 p15-p16）")
print("=" * 76)
Pd, Rd = build_model(0.0)
alpha = float(np.max(np.abs(R - Rd)))
beta = float(max(0.5 * np.sum(np.abs(P[i, a] - Pd[i, a])) for i in range(NS) for a in range(NA)))
Vmax = 1 / (1 - GAMMA)
pi = Qstar.argmax(axis=1)
D = float(np.max(np.abs(policy_eval(P, R, pi, GAMMA) - policy_eval(Pd, Rd, pi, GAMMA))))
bound = (alpha + GAMMA * Vmax * beta) / (1 - GAMMA)
print(f"α = ‖R1-R2‖∞                 = {alpha:.6f}")
print(f"β = max ½‖T1-T2‖₁            = {beta:.6f}   (= TV 距离, slip=0.1)")
print(f"V_max = 1/(1-γ)               = {Vmax:.2f}")
print(f"左端 Δ = max_s|V1^π - V2^π|   = {D:.6f}")
print(f"引理右端 (α+γ·V_max·β)/(1-γ)  = {bound:.6f}")
print(f"界成立: {D <= bound}；松弛 ≈ {bound/D:.2f}×")

print()
def vi_capped(P, R, gamma, tol=1e-8, max_sweeps=400):
    """带轮数上限的值迭代：RMax 的规划内核"""
    V = np.zeros(NS)
    for k in range(max_sweeps):
        Vn = (R + gamma * P @ V).max(axis=1)
        if np.max(np.abs(Vn - V)) < tol:
            return Vn, k + 1
        V = Vn
    return V, max_sweeps

def rmax_plan(n, Rc, Tc, m, gamma):
    """按'未知即乐观自环'构造乐观 MDP 并规划，返回 Q 表"""
    Pm = np.zeros((NS, NA, NS)); Rm = np.zeros((NS, NA))
    known = n >= m
    for ii in range(NS):
        for a in range(NA):
            if known[ii, a]:
                Pm[ii, a] = Tc[ii, a] / n[ii, a]; Rm[ii, a] = Rc[ii, a] / n[ii, a]
            else:
                Pm[ii, a, ii] = 1.0; Rm[ii, a] = 1.0        # 未知 ⇒ 乐观自环
    V, _ = vi_capped(Pm, Rm, gamma)
    return Rm + gamma * Pm @ V

print("=" * 76)
print("实验 3：RMax（乐观初始化）的样本复杂度（讲义 p9 / p13）")
print("=" * 76)
print(f"{'γ':>5} {'m':>3} {'覆盖状态':>8} {'首次到目标':>10} {'违反ε-最优步数':>14} {'到达目标次':>10} {'重规划次数':>10}")
for gamma in (0.9, 0.99):
    for m in (1, 3, 5):
        Pg, Rg = build_model(SLIP)
        _, TrueQ, _ = value_iteration(Pg, Rg, gamma)
        rng = np.random.default_rng(int(gamma * 100) + m)
        n = np.zeros((NS, NA), dtype=int); Rc = np.zeros((NS, NA)); Tc = np.zeros((NS, NA, NS))
        s = START; Nv = 0; first = None; ngoal = 0; nreplan = 0; Qc = None
        for t in range(1, 1201):
            i = idx[s]
            if Qc is None:                              # 仅在已知集变化时重新规划
                Qc = rmax_plan(n, Rc, Tc, m, gamma); nreplan += 1
            a = int(Qc[i].argmax())
            if TrueQ[i, a] < TrueQ[i].max() - EPS:      # 用真实 Q* 判定是否违反 ε-最优
                Nv += 1
            s2 = free[rng.choice(NS, p=P[i, a])]
            was_known = n[i, a] >= m
            n[i, a] += 1; Rc[i, a] += R[i, a]; Tc[i, a, idx[s2]] += 1
            if not was_known and n[i, a] >= m:
                Qc = None                               # 有新 (s,a) 变成"已知" ⇒ 重规划
            if s2 == GOAL:
                ngoal += 1
                if first is None:
                    first = t
                s = START
            else:
                s = s2
        print(f"{gamma:>5} {m:>3} {int((n.sum(axis=1)>0).sum()):>8} {str(first):>10} {Nv:>14} {ngoal:>10} {nreplan:>10}")
print("理论量级 O(|S||A|/(ε(1-γ)³))：γ=0.99 → %.3g 步，γ=0.9 → %.3g 步"
      % (NS * NA / (EPS * (1 - 0.99) ** 3), NS * NA / (EPS * (1 - 0.9) ** 3)))

【代码做什么】

1. 构造导航 MDP（第 7–30 行）：10×10 网格中第 5 列上半部是一堵墙，只在 (6,5) 留一个缺口，所以左下角起点 (9,0) 到右上角目标 (0,9) 必须绕路穿过缺口——这正是讲义所说”某些状态难以到达”的结构来源。build_model(slip) 把打滑动作（以 slip/2 各偏转 $\pm90°$）展开成完整的 $P$ 与 $R$ 张量。
2. 实验 1（第 62–74 行）：值迭代求 $V^,Q^$，用 BFS 求确定性最短距离 $d$，再解线性方程组 $V^{\pi_{rand}}=(I-\gamma P^{\pi_{rand}})^{-1}R^{\pi_{rand}}$ 得到均匀随机策略的价值。最后统计”随机策略能达到 $\epsilon$-最优的状态数”。
3. 实验 2（第 76–90 行）：把 $\mathrm{slip}=0$ 的模型当作”错模型”，计算 $\alpha,\beta$，再对同一个策略 $\pi$ 分别在两个模型上做精确策略评估，比较真实的 $\Delta$ 与 Simulation Lemma 的右端。
4. 实验 3（第 92–140 行）：实现 RMax。rmax_plan 按”未知即乐观自环”构造乐观 MDP 并值迭代求 $\tilde Q$；只有当某个 $(s,a)$ 的计数首次跨过 $m$（即”已知集”发生变化）时才重新规划，否则复用上一次的 $Q$ 表——这正是 RMax 伪代码里”若计数跨过 $m$ 则重新规划”那一步。选动作后用真实 $Q^*$ 判定它是否 $\epsilon$-最优（这是 PAC 定义的语言），并更新经验计数与模型。

【RL 机制透视】

• “未知即自环”为什么等于最乐观？ 自环让 $Q(s,a)=R_{max}+\gamma Q(s,a)$，解得 $Q=\frac{R_{max}}{1-\gamma}=V_{max}$。这是在给定 $R_{max}$ 下任何动作能达到的最大可能值，所以它是不折不扣的上界——不是启发式。
• PAC 判定必须用真实 $Q^*$：代码里 TrueQ[i, a] < TrueQ[i].max() - EPS 是 PAC 定义的字面翻译（”所选动作的价值是否离最优不超过 $\epsilon$”）。注意这和”是否到达目标”是不同的指标：一个算法可以频繁到达目标但走的是次优路径，那仍然在违反 PAC。
• 为什么 $m$ 是关键超参数？ $m$ 控制”什么时候相信经验模型”。$m$ 太小 → 模型被一两颗样本决定，规划出的策略不可靠（实验里 $m=1$ 时覆盖 89–93 个状态但违反步数较少，说明”学得快但不稳”）；$m$ 太大 → 智能体要把大量预算花在确认上（$m=5$ 时首次到目标从 116 推迟到 424）。
• $\gamma$ 的作用：$\gamma=0.99$ 时 $V_{max}=100$，$\gamma=0.9$ 时只有 10。乐观初始化的”吸引力”直接由 $V_{max}$ 决定，因此 $\gamma$ 越大，乐观偏差越强、探索越激进——但同时 Simulation Lemma 的分母 $1-\gamma$ 也把模型误差放大得越厉害，两股力量相互拉扯。

【实验观察】（真实运行输出，脚本 L12_nav_pac.py，总耗时约 30 秒）

实验 1：

可通行状态数 |S| = 94, 动作数 |A| = 4, |S||A| = 376
值迭代收敛用 2293 轮
V*(start)：打滑 = 82.988913，确定性 = 84.294319
最短距离 d(start→goal) = 18；确定性闭式 γ^d/(1-γ) = 83.451376
均匀随机策略 V^rand(start) = 5.070128
ε=0.1 时随机策略达到 ε-最优的状态数 = 1 / 94  (1.1%)
V*(goal) = 100.000（吸收自环 + 每次得分 ⇒ ≈ 1/(1-γ)）

三点读法：(1) 打滑版本的最优值 82.99 与确定性闭式 $\gamma^d/(1-\gamma)=83.451$ 只差 0.46（差 0.55%），说明在全速冲向目标的路径上打滑的损失很小——这个环境的最优策略主要就是把”缩短距离”做好；(2) 均匀随机策略 $V^{rand}(\text{start})=5.07$，与最优值 82.99 相差 77.9；(3) $\epsilon=0.1$ 的门槛下，94 个状态里只有 1 个（就是目标格本身，因为它在原地打转也能得分）能被随机策略蒙混过关——这就是 PAC 的严格性：$\epsilon$ 很小、$\gamma$ 很大时，随机策略几乎处处不合格，策略性探索不是”锦上添花”而是”必要条件”。

实验 2：

α = ‖R1-R2‖∞                 = 0.100000
β = max ½‖T1-T2‖₁            = 0.100000   (= TV 距离, slip=0.1)
V_max = 1/(1-γ)               = 100.00
左端 Δ = max_s|V1^π - V2^π|   = 1.891680
引理右端 (α+γ·V_max·β)/(1-γ)  = 1000.000000
界成立: True；松弛 ≈ 528.63×

真实的模型误差造成的价值误差只有 1.89，而界给到 1000——松弛 528.6 倍。这直接解释了为什么 RMax 的理论样本复杂度界（$10^6$–$10^9$ 步）比实测（几百步）松了 4–7 个数量级。

实验 3：

    γ   m     覆盖状态      首次到目标       违反ε-最优步数      到达目标次      重规划次数
  0.9   1       93        146            290         37        370
  0.9   3       93        217            608          6        336
  0.9   5       85        331            562          9        209
 0.99   1       93        116            364         37        373
 0.99   3       93        318            739          4        334
 0.99   5       87        418            654          9        207
理论量级 O(|S||A|/(ε(1-γ)³))：γ=0.99 → 3.76e+09 步，γ=0.9 → 3.76e+06 步

关键对比：违反 $\epsilon$-最优的步数在 290–739 之间，而理论界是 $3.76\times10^6$ 到 $3.76\times10^9$——界比实测松了约 4–7 个数量级，与 Simulation Lemma 松弛 528.6 倍同源。同时注意 $m$ 与”到达目标次数”的非单调关系（$m=1$ 时 37 次、$m=3$ 时 4–6 次、$m=5$ 时 9 次）：$m$ 太大时智能体把预算花在探索上，到达目标的次数反而减少——PAC 保证的是”少犯错”，不是”多拿奖励”，二者在有限时域内可以有冲突。最后一列”重规划次数”（207–373 次）说明：RMax 只需在已知集变化时重新规划，1200 步里平均每 3–6 步一次，而不是每步一次——这是它比 MBIE-EB 省算力的原因。

12.4.2 代码块二：PSRL、计数奖励与线性上下文 bandit

"""CS234 L12 代码块 2：PSRL 后验采样、计数奖励与线性上下文 bandit 的探索"""
import numpy as np
import matplotlib
matplotlib.use("Agg")
np.random.seed(0)

# ------------------- 环境：长廊（长链条稀疏奖励） -------------------
class Corridor:
    """N 个状态的链条，动作 1 = 前进（成功概率 1-slip），动作 0 = 后退。
    只有到达终点 pos=N-1 才得 +1。用于展示'稀疏奖励 + 长链条'的探索困难。"""
    def __init__(self, N=11, slip=0.2):
        self.N, self.slip = N, slip
        self.nS, self.nA = N, 2
    def reset(self):
        self.s = 0
        return self.s
    def step(self, a):
        if a == 1 and np.random.rand() > self.slip:
            self.s = min(self.s + 1, self.N - 1)
        elif a == 0:
            self.s = max(self.s - 1, 0)
        done = self.s == self.N - 1
        return self.s, (1.0 if done else 0.0), done

def run_corridor(mode, steps=6000, N=11, slip=0.2, beta=1.0, eps=0.1):
    env = Corridor(N, slip); s = env.reset()
    Q = np.zeros((env.nS, env.nA)); n = np.zeros((env.nS, env.nA)); cnt = np.zeros(env.nS)
    first_hit, hits = None, 0
    for t in range(1, steps + 1):
        if mode == "greedy":
            a = int(Q[s].argmax())
        elif mode == "eps":
            a = np.random.randint(env.nA) if np.random.rand() < eps else int(Q[s].argmax())
        else:                                    # 计数奖励
            a = int((Q[s] + beta / np.sqrt(n[s] + 1e-9)).argmax())
        s2, r, done = env.step(a)
        Q[s, a] += 0.1 * (r + (0.0 if done else 0.99 * Q[s2].max()) - Q[s, a])
        n[s, a] += 1; cnt[s2] += 1
        if done:
            hits += 1
            if first_hit is None: first_hit = t
            s = env.reset()
        else:
            s = s2
    return first_hit, hits, (cnt > 0).sum()

print("=" * 80)
print("实验 1：稀疏奖励长链条上的探索（对应讲义 p41 Montezuma's Revenge）")
print("=" * 80)
print(f"{'算法':>26} {'首次到达终点':>12} {'6000步内到达次数':>16} {'访问状态数':>10}")
for mode, name in [("greedy", "Q-learning 贪心 (无探索)"),
                   ("eps", "Q-learning ε-greedy (0.1)"),
                   ("count", "Q-learning + β/√n, β=1")]:
    fh, h, ns = run_corridor(mode)
    print(f"{name:>26} {str(fh):>12} {h:>16} {int(ns):>10}")
print(f"理论：随机策略需要连续 10 次成功前进（每次 0.8），期望步数 ≈ 10·0.8^-10 ≈ {10*0.8**-10:.0f} 步")

# ------------------- PSRL：小型导航 MDP 上的后验采样 -------------------
print()
print("=" * 80)
print("实验 2：PSRL（后验采样）vs 后验均值 —— 讲义 p21-p23")
print("=" * 80)

NROW, NCOL = 5, 5
GOAL2 = (0, NCOL - 1); START2 = (NROW - 1, 0)
DELTA = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def nav_step(s, a, slip):
    if s == GOAL2: return GOAL2, 1.0, True
    r, c = s
    aa = a if np.random.rand() > slip else np.random.randint(4)
    dr, dc = DELTA[aa]; nr, nc = r + dr, c + dc
    if not (0 <= nr < NROW and 0 <= nc < NCOL): nr, nc = r, c
    s2 = (nr, nc)
    return s2, (1.0 if s2 == GOAL2 else 0.0), s2 == GOAL2

def psrl(episodes=30, H=30, slip=0.1, sample=True, c=1.0, gamma=0.9):
    cells = [(r, c) for r in range(NROW) for c in range(NCOL)]
    ix = {s: i for i, s in enumerate(cells)}; nS = len(cells); nA = 4
    cnt = np.zeros((nS, nA, nS)); tot = np.zeros((nS, nA))
    regret, cover = 0.0, set()
    for k in range(episodes):
        # ---- 从后验采样一个 MDP（先验 = 各方向均匀）
        Pm = np.zeros((nS, nA, nS))
        for i, s in enumerate(cells):
            for a in range(nA):
                prior = np.zeros(nS)
                if s == GOAL2:
                    prior[i] = 1.0
                else:
                    r, c0 = s
                    for aa in range(4):
                        dr, dc = DELTA[aa]; nr, nc = r + dr, c0 + dc
                        if not (0 <= nr < NROW and 0 <= nc < NCOL): nr, nc = r, c0
                        prior[ix[(nr, nc)]] += 0.25
                if sample:                                  # Dirichlet 后验采样
                    al = np.maximum(c * prior + cnt[i, a], 1e-8)
                    Pm[i, a] = np.random.dirichlet(al / al.sum())
                else:                                       # 后验均值（不采样）
                    Pm[i, a] = cnt[i, a] / tot[i, a] if tot[i, a] > 0 else prior
        # ---- 规划：值迭代（奖励已知：进入目标 +1）
        Rm = np.zeros((nS, nA))
        for i, s in enumerate(cells):
            for a in range(nA):
                Rm[i, a] = Pm[i, a, ix[GOAL2]] * 1.0
        V = np.zeros(nS)
        for _ in range(200):
            V = (Rm + gamma * Pm @ V).max(axis=1)
        Qm = Rm + gamma * Pm @ V
        # ---- 执行一整回合
        s = START2
        for t in range(H):
            a = int(Qm[ix[s]].argmax())
            s2, r, done = nav_step(s, a, slip)
            cover.add(s2)
            cnt[ix[s], a, ix[s2]] += 1; tot[ix[s], a] += 1
            regret += 0.0 if done else 1.0
            if done: break
            s = s2
    return regret, len(cover)

for sample, name in [(True, "PSRL（从后验采样）"), (False, "后验均值 + 贪心")]:
    reg, cov = psrl(sample=sample)
    print(f"{name:>22}: 30 回合累计'未到达步数' = {reg:.0f}，覆盖 {cov}/25 个状态")
print("注：两者都能到达目标，但 PSRL 覆盖 24/25 个状态而后验均值只覆盖 13/25 ——")
print("    '从后验采样'天然带来探索；该环境太容易，真正的差距在实验 3 才被放大。")

# --------------- 线性上下文 bandit：UCB vs TS vs ε-greedy ---------------
print()
print("=" * 80)
print("实验 3：线性上下文 bandit —— 泛化 + 策略性探索（讲义 p30-p34, p49）")
print("=" * 80)
d, K, T, lam, sigma = 5, 10, 2000, 1.0, 0.5
theta_true = np.random.randn(K, d)
rng = np.random.default_rng(7)

def run_cb(method, alpha=1.0, nu=1.0, eps=0.05):
    A = np.array([lam * np.eye(d) for _ in range(K)])
    b = np.zeros((K, d)); reg = 0.0
    for t in range(T):
        s = rng.standard_normal(d)
        means = theta_true @ s
        if method == "ucb":
            th = np.array([np.linalg.solve(A[a], b[a]) for a in range(K)])
            bonus = np.array([alpha * np.sqrt(s @ np.linalg.solve(A[a], s)) for a in range(K)])
            a = int((th @ s + bonus).argmax())
        elif method == "ts":
            th = np.array([rng.multivariate_normal(np.linalg.solve(A[a], b[a]),
                                                   nu ** 2 * np.linalg.inv(A[a])) for a in range(K)])
            a = int((th @ s).argmax())
        else:
            th = np.array([np.linalg.solve(A[a], b[a]) for a in range(K)])
            a = rng.integers(K) if rng.random() < eps else int((th @ s).argmax())
        r = means[a] + sigma * rng.standard_normal()
        reg += means.max() - means[a]
        A[a] += np.outer(s, s); b[a] += r * s
    return reg

print(f"Disjoint Linear Contextual Bandit: K={K} 臂, d={d} 维特征, T={T}, 噪声 σ={sigma}")
print(f"{'算法':>18} {'参数':>8} {'T=2000 累计 regret':>20}")
for a in (0.5, 1.0, 2.0):
    print(f"{'线性 UCB (乐观)':>18} {a:>8} {run_cb('ucb', alpha=a):>20.1f}")
for v in (0.5, 1.0):
    print(f"{'线性 TS (概率匹配)':>18} {v:>8} {run_cb('ts', nu=v):>20.1f}")
for e in (0.02, 0.1):
    print(f"{'ε-greedy (无策略探索)':>18} {e:>8} {run_cb('eps', eps=e):>20.1f}")

【代码做什么】

1. Corridor 类 + run_corridor（第 6–40 行）：实现 11 状态长链条，并对比三种探索方式——纯贪心、$\epsilon$-greedy、以及计数奖励 $Q+\frac{\beta}{\sqrt{n}}$。
2. psrl 函数（第 50–98 行）：完整实现讲义 p23 的 PSRL 伪代码。关键在两层循环：外层每个 episode 从 Dirichlet 后验采样一整个 MDP 并规划（值迭代 200 轮），内层在该 MDP 上执行一整回合。sample=False 时退化为”后验均值 + 贪心”作为对照。
3. run_cb 函数（第 108–130 行）：实现 Disjoint 线性上下文 bandit 的 UCB 与 TS。UCB 的 bonus 是 $\alpha\sqrt{\phi^\top A_a^{-1}\phi}$；TS 从 $\mathcal{N}(\hat\theta_a,\nu^2A_a^{-1})$ 采样再取 $\arg\max$；ε-greedy 作为无策略性探索的基线。

【RL 机制透视】

• PSRL 的两层循环就是”概率匹配”的实现：外层采样 = “掷骰子决定相信哪个世界”，内层执行 = “在那个世界里做到最好”。因为”某个 $(s,a)$ 是好动作”的后验概率正比于”采样出的 MDP 里它是好动作”的频率，所以这套流程自动地按后验概率来探索。
• Dirichlet 是 Beta 的多元推广：L11 里 Beta-Bernoulli 的更新是 $(\alpha,\beta)\leftarrow(\alpha+r,\beta+1-r)$；这里 Dirichlet 的更新就是 $\mathbf{c}\leftarrow\mathbf{c}+\mathbf{e}_{s^{\prime}}$（把观测到的下一状态那一维加一）。代码里 c * prior + cnt[i, a] 正是”先验伪计数 + 经验计数”。
• 线性 UCB 的 bonus 与 $A_a^{-1}$ 的关系：$A_a=\lambda I+\sum_\tau\phi_\tau\phi_\tau^\top$ 是特征的外积累积，它的逆就是协方差矩阵。因此 $\sqrt{\phi^\top A_a^{-1}\phi}$ 衡量的是”$\phi$ 这个方向上有多少数据”。这就是”把计数从状态搬到特征”的机制——L11 的粒度是”每个臂一个计数 $n_a$”，这里是”参数空间每个方向一个不确定度”。
• 为什么 ε-greedy 在泛化下尤其糟？ 因为它的探索与特征无关：不管当前上下文 $s$ 是什么，都以固定概率随机选臂。而在上下文 bandit 中，同一个臂在不同上下文下的价值差别巨大，无差别的随机探索等于把预算丢进了无效方向。实验里 $\epsilon=0.1$ 比 $\epsilon=0.02$ 差得多（867.8 vs 513.6）就是这个道理。

【实验观察】（真实运行输出，脚本 L12_explore.py，总耗时约 6 秒）

实验 1（长链条）：

                        算法       首次到达终点   6000步内到达次数      访问状态数
       Q-learning 贪心 (无探索)         None                0          1
 Q-learning ε-greedy (0.1)         None                0          3
    Q-learning + β/√n, β=1          426              331         11
理论：随机策略需要连续 10 次成功前进（每次 0.8），期望步数 ≈ 10·0.8^-10 ≈ 93 步

这是本讲最有力的一张表：贪心与 $\epsilon$-greedy 6000 步内一次都没到过终点（$\epsilon$-greedy 甚至只访问了 3 个状态），而计数奖励版本到达 331 次。原因很直接：链条长 10 步、每步成功概率 0.8，随机走完的概率是 $0.8^{10}\approx 0.107$，期望需要约 93 步；而 $\epsilon=0.1$ 的随机抖动在”已经接近终点时”反而会把智能体推回去，够不到那 10 次连续成功。

实验 2（PSRL）：

           PSRL（从后验采样）: 30 回合累计'未到达步数' = 628，覆盖 24/25 个状态
             后验均值 + 贪心: 30 回合累计'未到达步数' = 291，覆盖 13/25 个状态

诚实解读：在这个近乎确定性、目标奖励可反复利用的小环境上，“后验均值 + 贪心”反而拿到了更好的回报（291 < 628）；PSRL 的价值体现在覆盖上（24/25 vs 13/25）。这与 L10 中”T=10⁴ 时 UCB 还输给 ε-greedy”完全同构——探索策略的账要在足够困难的任务上才算得清。

实验 3（线性上下文 bandit）：

Disjoint Linear Contextual Bandit: K=10 臂, d=5 维特征, T=2000, 噪声 σ=0.5
                算法       参数     T=2000 累计 regret
       线性 UCB (乐观)      0.5                379.6
       线性 UCB (乐观)      1.0                152.9
       线性 UCB (乐观)      2.0                177.4
      线性 TS (概率匹配)      0.5                150.0
      线性 TS (概率匹配)      1.0                267.0
  ε-greedy (无策略探索)     0.02                513.6
  ε-greedy (无策略探索)     0.1                867.8

三点：(1) 最佳配置（线性 TS $\nu=0.5$ 的 150.0、线性 UCB $\alpha=1$ 的 152.9）与 ε-greedy（513.6–867.8）相差约 3.4–5.8 倍，是一个数量级的差距；(2) 探索参数存在最优点（UCB：$1.0$ 优于 $0.5$ 与 $2.0$；TS：$0.5$ 优于 $1.0$），太小则探索不足、太大则浪费预算；(3) ε-greedy 的 $\epsilon$ 越大越差，与”$\epsilon$-greedy 的 regret 是线性”的 L9 结论一致——在有限 $T$ 下，更大的 $\epsilon$ 只是更多地浪费。

12.5 评估指标与理论保证

12.5.1 三种框架的完整对比

一句话总结三者关系：regret 累加所有小错，PAC 只数大错，贝叶斯 regret 把难度先验也算进去。讲义 p51 指出：表格型 MDP 的 regret 与 PAC 都已经有紧的 minimax 结果（Azar, Osband & Munos, ICML 2017；Dann, Li, Wei & Brunskill, ICML 2019），以及问题相关的界（Zanette & Brunskill, ICML 2019；Simchowitz & Jamieson, NeurIPS 2019）——这是本课程理论线的最前沿。

12.5.2 计算复杂度 vs 样本复杂度

核心权衡：乐观/贝叶斯方法用小得多的样本换取大得多的算力。这是”数据高效 RL”这个名字的由来——也是最容易在考试中被考到的对比（讲义 p24 的”TS 每步计算代价与 Q-learning 相同吗？”答案是否）。

12.5.3 条件依赖分析

12.6 与其他讲次的关联

向后（本讲依赖）：

• L9（评估框架、MAB、UCB）：本讲把 L9 的 regret 框架平行地扩展为 PAC 框架，并复用了 UCB 的乐观思想与 Hoeffding 工具。L9 只给 UCB 界的骨架，L10 给了完整证明；本讲把同样的证明结构搬到 MDP（Simulation Lemma 相当于 MDP 版的”误差传播”引理）。
• L10（UCB 遗憾界 + bandit→MDP 桥梁）：L10 末尾的”为什么 bandit 方法不能直接迁移到 MDP”就是本讲的起点。L10 指出的两个困难——延迟后果与必须能到达状态——正是 PAC-MDP 多项式里多出 $\frac{1}{1-\gamma}$ 与探索必须主动进行的原因。
• L11（贝叶斯老虎机、Thompson 采样、贝叶斯 regret、Gittins）：本讲 12.2.4 与 12.3.3 是 L11 的直接推广——Beta→Dirichlet、每步采样→每 episode 采样、共轭更新→逐 $(s,a)$ 共轭更新。L11 的”误导先验会让 TS 变差”在本讲同样成立。
• L2（值迭代）：RMax、MBIE-EB、PSRL 全部把值迭代当作子程序。它们的差别只在于用什么模型 + 加什么 bonus，规划内核完全复用 L2。
• L4（Q-learning）：本讲反复以 Q-learning 作对照——它是”最省算力但无探索保证”的一端；12.4.1 的实验正展示了它在长链条上完全失败。
• L8（RLHF/DPO）：DPO 需要人类偏好，而偏好的采集本身就是信息获取问题——用 TS/UCB 的框架来选”问哪一对比较最 informative”是当前的前沿方向，与本讲的”主动探索”同源。

向前（本讲支撑）：

• L13–L14（MCTS / AlphaZero）：MCTS 的 UCT 选择规则 $Q(s,a)+c\sqrt{\frac{\ln N(s)}{N(s,a)}}$ 与本讲的 $\frac{\beta}{\sqrt{n(s,a)}}$ 是同一原则（面对不确定性保持乐观）在树搜索中的实现。探索奖励、UCB、UCT 是同一个思想的三种外衣。
• L13 的 AlphaZero：它用先验 $P(s,a)$ 代替 bonus——$Q+cP(s,a)\frac{\sqrt{N(s)}}{1+N(s,a)}$。这可以理解为”把探索的引导从均匀的不确定度换成学到的先验”，与本讲 12.2.5 的元学习探索（DPT”用更丰富的先验模仿 TS”）是同一进化方向。
• L15（世界模型）：世界模型解决的是”样本效率”，而本讲解决的是”探索效率”——两者是数据高效 RL 的两条腿。世界模型误差累积（L15 的复合误差界）与 Simulation Lemma 的误差传播是同一个数学结构。
• L16（对齐与社会影响）：PAC 的”$\epsilon$-最优”设定默认奖励函数是已知且正确的；L16 追问的正是”如果奖励本身就是错的（Paperclip AI），那么把 $\epsilon$ 和 $\delta$ 优化到多小都没有意义”。本讲是”如何高效地达到目标”的技术顶点，L16 是”目标本身是否值得追求”的反思。

12.7 关键要点

1. PAC-MDP 关注的是「犯错的次数」，不是遗憾的累积值。 定义：以概率 $\ge1-\delta$，非 $\epsilon$-最优动作的步数是 $(\vert \mathcal{S}\vert ,\vert \mathcal{A}\vert ,\frac{1}{1-\gamma},\frac{1}{\epsilon},\frac{1}{\delta})$ 的多项式。多项式里出现 $\frac{1}{1-\gamma}$ 是 MDP 区别于 bandit 的标志。

2. Simulation Lemma 是连接”模型误差”与”价值误差”的桥梁： \(\Delta\le\frac{\alpha+\gamma V_{max}\beta}{1-\gamma}.\) 它成立但极其保守（实测松弛 528 倍）。它是 RMax / MBIE-EB 证明的引擎，也解释了 PAC 界为何含 $\frac{1}{(1-\gamma)^3}$。

3. 乐观性有两种实现：连续的 bonus（MBIE-EB 的 $\frac{\beta}{\sqrt{n(s,a)}}$）与二值的乐观初始化（RMax 的”未知即 $R_{max}$ + 自环”）。 二者都源于讲义那句话——”有些 PAC 算法只是把所有值初始化成一个问题相关的高值”。

4. PSRL = MDP 版的 Thompson 采样：每个 episode 从后验采样一整个 MDP、规划、执行整回合。“每 episode 一次”而非”每步一次” 保证了幻想世界的一致性，代价是每步计算量远高于 Q-learning。

5. 泛化 + 策略性探索是本课最大的开放问题。 表格型计数在巨大状态空间下失效；解决方向是特征计数/伪计数（Montezuma’s Revenge 上的巨大提升）、参数空间不确定集（线性上下文 bandit 的 $\sqrt{\phi^\top A^{-1}\phi}$）、对 $Q^*$ 的后验采样（Bootstrapped DQN）以及元学习探索（DREAM / DPT：「训练预测 $a^\star$ 就是在模仿 Thompson 采样，但能容纳更丰富的先验」）。

6. 实验的黄金法则：数据效率是用算力买的。 实测在长链条上，纯 Q-learning 与 $\epsilon$-greedy 6000 步一次都没到终点（各只访问 1 与 3 个状态），而计数奖励版本到达 331 次；在线性上下文 bandit 上，策略性探索的 regret（150）比 ε-greedy（514–868）低约一个数量级。

12.8 常见误区与注意事项

误区 1：认为 PAC 和 regret 是同一回事，只是换了个名字。 正确认识：二者衡量不同的东西。regret 累加所有遗憾，因此允许”犯无数个小错”（只要总和次线性）；PAC 要求”非 $\epsilon$-最优的步数是多项式”，因此允许犯小错但限制大错。讲义 p7–p8 明确点出这个区别：“Could be making lots of little mistakes or infrequent large ones.” 一个算法可以有很好的 regret 却没有 PAC 保证（例如许多小错累积起来遗憾不大），反之亦然。

误区 2：以为 Simulation Lemma 给出的界是”实际能用的误差估计”。 正确认识：它给出的是正确的量级与依赖关系，不是可用的数值。实测中真实误差 1.89、界给出 1000，松弛 528 倍。这与 L9 里”Hoeffding 界成立但很松（经验失败率 0.0555 vs 界 0.4038）”是同一类现象。用它来判断”$\gamma$ 变大时误差怎么变”是正确的，用它来选超参数则会被严重误导。

误区 3：认为在 MDP 中也可以用 RMax 那样”把值初始化成大数”来替代探索奖励，或者说两者在数学上不同。 正确认识：二者是同一原则的两种表达。RMax 的”未知 $(s,a)$ 给 $R_{max}$ 加自环”得到 $Q=V_{max}$，这与 MBIE-EB 在 $n(s,a)\to0$ 时 bonus $\frac{\beta}{\sqrt{n}}\to\infty$ 的极限行为一致。区别在于 RMax 是二值的、MBIE-EB 是连续的：RMax 在 $n\ge m$ 后完全放弃乐观性，MBIE-EB 则保留一个随 $n$ 衰减的小 bonus。因此 MBIE-EB 往往样本效率更好但计算更贵（每步都要重规划）。

误区 4：以为 PSRL 每一步都要重新采样一个 MDP、重新规划。 正确理解：PSRL 每个 episode 采样一次、规划一次，整回合内使用同一个 $M$ 与同一个 $Q^*_M$。这个设计不是省算力的小技巧，而是正确性的要求：如果每步都换模型，那么 $(s,a)$ 的转移在连续两步之间可能自相矛盾，规划得到的策略将毫无意义。讲义 p22 的伪代码把”sample MDP + solve MDP”放在 episode 层，正是这个意思。

误区 5：认为”探索奖励 $\beta/\sqrt{n}$ 里的 $\beta$ 越大探索越充分，所以越大越好”。 正确认识：$\beta$ 必须与不确定度的真实尺度匹配。L11 的实验已显示误导先验会让 TS 退化（regret 6.46 → 26.31），本讲 12.4.1 的实验 3 也显示：在 $\gamma=0.9$ 的环境里，$V_{max}=10$ 已经把乐观性顶满，再加 bonus 只会让智能体在同一处反复打转（原作者的 MBIE-EB 消融实验中，$\beta$ 乘子从 0.05 提到 0.2 时，覆盖状态数从 94 掉到 39、到达目标次数从 420 掉到 0）。**探索奖励的大小必须与不确定度匹配——过度乐观等同于盲目。

误区 6：以为”策略性探索”和”泛化”是两个可以分开解决的问题。 正确认识：讲义 p28–p29 把 “combine generalization & strategic exploration” 明确标为ongoing research，因为两者会互相破坏：泛化让”看到 $s$ 就更新 $s^{\prime}$ 的值”（有利于学习），但也让”这个动作我试过了”这句话失去意义——在特征空间里，你可能永远无法真正”访问完”任何东西。出路是把不确定性从状态空间搬到特征/参数空间（本讲的 $\phi^\top A^{-1}\phi$），或者跨任务学习如何探索（DREAM / DPT）。

误区 7：以为 Q-learning 加个 $\epsilon$-greedy 就”探索过了”，在稀疏奖励长链条上也能work。 正确认识：本讲的实验给出了直接反证——在 11 状态长链条上，$\epsilon=0.1$ 的 Q-learning 6000 步内一次都没到过终点，只访问了 3 个状态。原因是要到达终点必须连续 10 次成功前进（概率 $0.8^{10}\approx0.107$），而 $\epsilon$-greedy 的随机抖动在接近终点时反而会把智能体推回起点。盲目随机不是探索；探索必须是有方向、有记忆、被不确定性驱动的。

误区 8：以为这些理论界已经解决了”数据高效 RL”。 正确认识：讲义 p52 直接提问 “Do there exist strong theoretical bounds for RL with function approximation?” 并给出答案——“Active area of recent work”。表格型 MDP 的紧界已经建立（Azar et al. 2017；Dann et al. 2019），但函数逼近下的一般理论仍然缺失，目前只有依赖线性逼近与复杂度度量（Eluder dimension、Bellman rank）的部分结果。不要把一个在表格型世界被证明的算法直接搬到连续控制就宣布问题解决。

12.9 思考题（带答案）

问题 1（PAC 定义与多项式参数）：考虑一个表格型 MDP，$\vert \mathcal{S}\vert =100$、$\vert \mathcal{A}\vert =4$、$\gamma=0.95$、$\epsilon=0.1$、$\delta=0.05$。 (a) 写出 PAC-MDP 定义中多项式所依赖的参数集合。 (b) 若算法 A 保证 $N=O\big(\frac{\vert \mathcal{S}\vert \vert \mathcal{A}\vert }{\epsilon^3(1-\gamma)^3}\ln\frac{\vert \mathcal{S}\vert \vert \mathcal{A}\vert }{\delta}\big)$，计算该界并说明它是多项式。 (c) 若另一个算法 B 保证 $N=O\big(\vert \mathcal{S}\vert ^{\vert \mathcal{A}\vert }\big)$，它是否是 PAC 算法？为什么？

答案： (a) 多项式依赖 $\vert \mathcal{S}\vert $、$\vert \mathcal{A}\vert $、$\frac{1}{1-\gamma}$、$\frac{1}{\epsilon}$、$\frac{1}{\delta}$。注意没有对 $T$ 的依赖——PAC 保证必须对任意长的时域成立（讲义 p13 的定义）。 (b) 代入 $\frac{1}{1-\gamma}=\frac{1}{0.05}=20$、$\frac{1}{\epsilon}=10$、$\frac{1}{\delta}=20$：

它是多项式：对每个参数都是乘幂关系（$\vert \mathcal{S}\vert ^1\vert \mathcal{A}\vert ^1$、$\epsilon^{-3}$、$(1-\gamma)^{-3}$、$\delta^{-1}$ 的对数），没有一个参数出现在指数位置。量级 $10^{10}$ 看起来巨大，但 PAC 的定义只要求”多项式”，不要求常数小。

(c) 不是。$O(\vert \mathcal{A}\vert ^{\vert \mathcal{S}\vert })$ 对 $\vert \mathcal{A}\vert $（或 $\vert \mathcal{S}\vert $）是指数关系，不满足”poly”要求。这正是”策略枚举”的复杂度——在 $\vert \mathcal{S}\vert =100$ 时它就是 $4^{100}\approx1.6\times10^{60}$，远超任何实际时域，因此不能被称作 PAC 算法。这个对比说明 PAC 框架的价值：它把”能不能学会”和”要多久学会”分开，并用多项式/指数划出一条泾渭分明的线。

问题 2（Simulation Lemma 的推导与解读）：设 $R_1=R_2$（$\alpha=0$），但 $T_1$ 与 $T_2$ 在某 $(s,a)$ 上的 TV 距离为 $\beta=0.1$；取 $\gamma=0.99$、$R_{max}=1$。 (a) 用 Simulation Lemma 给出 $\Delta$ 的上界。 (b) 本讲实验 2 中实测 $\Delta=1.8917$，你的界是多少倍？ (c) 若把 $\gamma$ 改成 $0.9$（$R_{max}$ 仍为 1），界变成多少？从 $\gamma=0.99$ 到 $0.9$，界缩小了多少倍？ (d) 请解释为什么界里 $\beta$ 的系数是 $\gamma V_{max}$ 而不是 $V_{max}$。

答案： (a) $V_{max}=\frac{1}{0.01}=100$，故

（本讲脚本实测给出 1000.000000，因为脚本里 $\alpha=0.1$——采用的是”打滑 vs 不打滑”两个模型，奖励模型在打滑时进入目标的概率也变了。若按本题的 $\alpha=0$ 设定，界为 990。）

(b) $990/1.8917\approx523$ 倍（脚本中 $\alpha=0.1$ 时是 $1000/1.8917\approx528.6$ 倍）。界成立但极度保守。

(c) $V_{max}=\frac{1}{1-0.9}=10$，

从 990 降到 9.0，缩小 110 倍。这个缩小来自两处：$V_{max}$ 从 100 降到 10（10 倍），以及分母 $1-\gamma$ 从 0.01 增到 0.1（10 倍），共 $10\times10=100$ 倍（余下的差异来自分子的 $\gamma$ 从 0.99 变 0.9）。

(d) 因为转移误差造成的价值偏差要”经历一步折扣才发生”：写出递推

其中第三项来自 $\sum_{s^{\prime}}(T_1(s^{\prime}\vert s,a)-T_2(s^{\prime}\vert s,a))V_2^\pi(s^{\prime})$。这一项是”用错的分布去加权 $V_2$”，而 $V_2$ 本身量级是 $V_{max}$；但这步加权是发生在下一步的价值上的，所以必须打一次折扣 $\gamma$。相比之下，奖励误差 $\alpha$ 是当步立即发生的，不需要折扣。这个 $\gamma$ 的差别正是”延迟后果”在数学上的印记。

问题 3（PSRL 的设计选择）：某工程师实现 PSRL 时做了两处改动：(i) 每一步都从后验重新采样一个 MDP 并重新规划；(ii) 只对转移做后验采样，奖励直接用心经验均值（不用后验采样）。 (a) 改动 (i) 会有什么后果？ (b) 改动 (ii) 在什么条件下是合理的、在什么条件下是危险的？ (c) 讲义 p24 的多选题问：”TS 每步计算代价总是与 Q-learning 相同”——这个说法对吗？

答案： (a) 会破坏幻想世界的一致性，并且计算代价爆炸。 如果每步都重新采样，那么第 $t$ 步采样出的 $M_t$ 与第 $t+1$ 步的 $M_{t+1}$ 是两个不同的世界。规划出的 $Q^*{M_t}$ 只在 $M_t$ 里自洽，用它选出的动作在 $M{t+1}$ 里可能毫无意义——“策略改进”的逻辑链条断掉了。此外每步一次值迭代的代价是 $O(\vert \mathcal{S}\vert ^2\vert \mathcal{A}\vert )$ 乘迭代轮数，而 Q-learning 每步只要 $O(1)$。PSRL 的伪代码（讲义 p23）把采样与规划放在 episode 层，这是有意为之的设计。

(b) 合理的情形：当奖励是确定性的（如实验 2 的导航 MDP：只有进入目标才 +1），或奖励分布已被充分观测（$n(s,a)$ 很大）时，用经验均值近似后验均值是恰当的——此时奖励的后验方差已经很小，采样与取均值差别不大。 危险的情形：当奖励稀有且随机（如长链条、Montezuma’s Revenge）时，经验均值会系统性低估那些”可能给高奖励但还没试过”的动作——因为没试过就拿不到高奖励样本，均值自然低。这正是”乐观性”要发挥作用的地方：必须让”没有被充分观测的奖励”有被高估的机会，否则算法会过早放弃探索。（这也是 MBIE-EB 用无偏的经验均值 + bonus，而不是只用均值的原因。）

(c) 不对。 PSRL / TS 的计算代价显著高于 Q-learning：Q-learning 每步 $O(1)$（表格型），而 PSRL 每个 episode 要做一次完整规划，均摊到每步是 $O(\vert \mathcal{S}\vert ^2\vert \mathcal{A}\vert \cdot\#\text{VI迭代})$。这一点是”数据效率用算力买”的直接体现，也是 12.5.2 那张对比表的主题。

问题 4（泛化与探索的结合）：在一个有 $10^6$ 个状态的 GridWorld 上，一个研究者发现：用表格型计数奖励 $\frac{\beta}{n(s,a)}$ 完全没有效果（智能体在 $10^6$ 步内几乎学不到东西）。 (a) 请诊断问题出在哪里（用”计数退化”的语言解释）。 (b) 给出至少两种可行的替代方案，并说明各自的机制。 (c) 本讲实验中”特征计数 + 线性 Q”从 0 次到达目标提升到 23 次，请解释这为什么是”泛化使探索成为可能”，而不是”泛化替代了探索”。

答案： (a) 计数退化：在 $10^6$ 个状态的空间里，$10^6$ 步意味着平均每个状态只被访问 1 次，绝大多数 $(s,a)$ 的计数是 0 或 1，因此 bonus $\frac{\beta}{n(s,a)}$ 对不同 $(s,a)$ 几乎相同（要么全是 $\beta$，要么区分度极低）。结果是：bonus 不再携带”我对这个地方还不熟”的信息，它退化成一个常数偏置，无法把智能体引向未探索区域。更深层地看，”访问某个具体状态”这个事件本身就失去了统计意义——你无法通过访问次数来估计”这片区域有多熟悉”。

(b) 可行方案（任答两种，机制要说清）：

• 伪计数 / 密度模型（Bellemare et al.）：训一个密度模型 $P(s)$，令伪计数 $\hat n(s)\propto P^{-1}(s)$ 的某种变换，再用 $\frac{\beta}{\sqrt{\hat n(s)}}$ 作 bonus。机制：不确定性由”这个观测在密度模型下有多罕见”度量，因此单个新观测能提升整片相似区域的”熟悉度”——计数从状态空间搬到了密度/特征空间。讲义 p41 引用该方法在 Montezuma’s Revenge 上的巨大提升。
• 特征空间的不确定集（线性上下文 bandit / LinUCB 风格）：用 $\sqrt{\phi(s,a)^\top A^{-1}\phi(s,a)}$ 作 bonus，$A=\lambda I+\sum\phi\phi^\top$。机制：衡量的是”$\phi$ 所在的方向上积累了多少数据”，与状态的具体身份无关，因此泛化天然成立。本讲实验 3 的线性 UCB 就是这个方案，2000 步内 regret 只有 150。
• 对 $Q^$ 的后验采样（Bootstrapped DQN）**：训 $C$ 个 bootstrap 网络近似 $Q^$ 的后验，行动时在其中随机取一个求 $\arg\max$。机制：网络之间的分歧**就是不确定度的代理——分歧大的地方就是该探索的地方。
• 元学习探索（DREAM / DPT）：在大量任务上训练”如何探索”的先验。机制：把”探索策略”本身当作可学习的对象，用跨任务的先验来指导新任务的探索。

(c) 因为泛化解决的是”经验如何复用”，探索解决的是”下一步该去哪里”——两者互补而非替代。 本讲实验的具体数字支持这一点：在”linear Q + greedy, no bonus”配置下，智能体到达目标 0 次，访问的不同状态数只有 1（困在起点：$W$ 全零使两个动作 Q 值相同，$\arg\max$ 恒取动作 0 原地不动）；加上特征计数奖励后才到达 23 次、访问 700 个不同状态。 关键在于：泛化让”某个方向上的经验”能传播到该方向上所有状态（10 维特征 $\to$ 1000 个状态），但没有任何机制会主动去尝试没试过的方向——而特征计数奖励提供的正是这个机制（”从未试过的动作值得一试”）。反之，如果没有泛化，特征计数就退化成状态计数（回到 (a) 的困境）。结论：泛化把”探索的成果”放大到整个特征空间，探索把”泛化的方向”指向未知；缺任何一个都不成立。 这正是讲义 p28 把 “combine generalization & strategic exploration” 标为 ongoing research 的深层原因。