Lecture 11: 快速强化学习 —— 贝叶斯老虎机与 Thompson 采样（Fast RL: Bayesian Bandits and Thompson Sampling）

目录 · ← l10 · l12 →

Lecture 11: 快速强化学习 —— 贝叶斯老虎机与 Thompson 采样（Fast RL: Bayesian Bandits and Thompson Sampling）

对应材料：官方 lecture11pre.pdf / lecture11post.pdf（各 50 页；首页标题写作 “Lecture 13” 并自注 “Typo: Lecture 11”，是笔误，本讲即第 11 讲）｜W7 周三 Feb 18, 2026（2/16 假期；A3 于 2/20 截止）｜参考阅读 Sutton & Barto Chp 2（多臂老虎机）、Chp 8（规划与学习）；Lattimore & Szepesvári Bandit Algorithms §7.1、Chp 19；Russo et al. A Tutorial on Thompson Sampling；Chapelle & Li, WWW 2010 一句话定位：L9–L10 用「乐观性（optimism）」把探索写成确定性的置信上界，L11 换成贝叶斯视角——把奖励参数当作随机变量、维护后验，用概率匹配（probability matching）实现探索；Thompson 采样（Thompson Sampling, TS）就是概率匹配的一个惊人地简单的实现，它在贝叶斯 regret 意义下与 UCB 同阶。本讲同时给出贝叶斯 bandit 的最优策略（Gittins index）这一「理论与实践的裂缝」，为 L12 把同一套框架搬到 MDP（PSRL、PAC-MDP）铺路。

11.1 概述

L9 建立了多臂老虎机（multi-armed bandit, MAB）的记号与 regret 框架，L10 用 Hoeffding 不等式推出 UCB1 的 $O(\sqrt{KT\log T})$ 频率派 regret 界。本讲换一套信息假设：不再只假设奖励有界，而是假设我们知道奖励参数的一个先验分布（prior） $p[R]$，于是可以用贝叶斯法则把观测转成后验（posterior） $p[R\mid h_t]$，并让后验直接决定动作。核心结论有三条：(1) 概率匹配——按「某个动作是最优动作的后验概率」来抽样，天然对不确定性保持乐观；(2) Thompson 采样（Thompson, 1933）恰好实现概率匹配，且实现成本只是「每步从后验抽一个参数、取 argmax」；(3) 在贝叶斯 regret 的度量下，TS 与 UCB 有相同（忽略常数）的界，尽管 TS 的频率派界至今（讲义写作时）仍不能匹配最好的频率派算法。本讲末尾回到「TS 到底是不是最优」：对已知 horizon 的贝叶斯 bandit，最优策略是 Gittins index 索引策略，而 TS 只是近似——这正是「计算可行」与「理论最优」分道扬镳的地方。

对应讲义页：p2–3（确定性奖励的判断题）、p5–p8（课程定位与今天大纲）、p9–p18（贝叶斯推断速成 + 贝叶斯 bandit 概览）、p20–p30（TS 算法与 broken-toe 演示）、p31–p35（概率匹配）、p37–p39（regret 与贝叶斯 regret、用乐观性界 regret）、p40–p43（上下文 bandit TS + Check Your Understanding）、p44–p45（最优策略与 Gittins index）、p49–p50（贝叶斯 regret 界与 PAC/regret 玩具表）。

11.2 核心概念的数学形式化

11.2.1 记号复习：多臂老虎机（p7）

多臂老虎机是一个二元组 $(\mathcal{A}, R)$：$\mathcal{A}$ 是已知的 $m$ 个动作（臂）的集合，$R_a(r)=P[r\mid a]$ 是臂 $a$ 上未知的奖励分布。每步 $t$ 智能体选 $a_t\in\mathcal{A}$，环境生成 $r_t\sim R_{a_t}$；目标是最大化累积奖励 $\sum_{\tau=1}^{t} r_\tau$。单步 regret（遗憾）与总 regret 定义为

其中 $V^=\max_a Q(a)$，$\Delta_a=V^-Q(a)$ 是间隙（gap），$N_t(a)$ 是前 $t$ 步中臂 $a$ 被拉动的次数。最大化累积奖励 $\iff$ 最小化总 regret（二者只差一个与算法无关的常数 $tV^*$）。

直观解释：老虎机是「只有一个状态的 MDP」；MDP 里的探索难在「数据分布依赖于策略」——你不去某个状态，就永远不知道它好不好，这正是不确定性下的「抽样偏差」。与监督学习的对比：监督学习的数据分布由数据集给定，模型好坏与「取哪个样本」无关；bandit/MDP 里「取哪个动作」直接决定你看到什么数据，所以探索本身是一个决策变量，这是 RL 独有的二阶问题。

11.2.2 贝叶斯推断速成（p10–p17）

频率派观点：参数 $\theta$ 是固定但未知的常数，我们用无偏估计 + 置信区间（confidence interval）来量化不确定性。贝叶斯观点：参数 $\theta_i$（第 $i$ 条臂奖励分布的参数）本身就是随机变量，先有先验（prior） $p(\theta_i)$，观测数据后用贝叶斯法则得到后验（posterior）：

式中的分母（证据 marginal likelihood）一般要对整个参数空间积分，通常难以精确计算。讲义给的关键出路是共轭（conjugate）：若先验与后验属于同一个参数族，则先验与似然共轭，更新就有闭式解；指数族（exponential family）都有共轭先验。

Bernoulli–Beta 共轭（p15–p16）：奖励为二元 $r\in\{0,1\}$，$r\sim\mathrm{Bernoulli}(\theta)$（广告点击率、病人治疗成功/失败都是这个形态）。取先验

即 $\theta\sim\mathrm{Beta}(\alpha,\beta)$，其中 $\Gamma(x)$ 是 Gamma 函数（讲义写作 “Gamma family”）。观测到一次奖励 $r\in\{0,1\}$ 后，后验仍是 Beta：

直观解释：$\alpha-1$ 像「伪成功次数」、$\beta-1$ 像「伪失败次数」；看到成功就 $\alpha\!\mathrel{+}\!=1$，看到失败就 $\beta\!\mathrel{+}\!=1$。具体示例：断趾治疗（broken toes）玩具例中 $\theta_i\sim\mathrm{Beta}(1,1)$（均匀先验，即「什么都不知道」），拉到臂 3 得到 $r=0$ 后，其后验就是 $\mathrm{Beta}(1,2)$——均值从 $0.5$ 掉到 $1/3$，符合直觉。与监督学习的对比：监督学习里正则化系数是超参数、没有概率含义；贝叶斯先验把「正则」变成了「可更新的分布」，先验强度 $\alpha+\beta$ 直接控制「需要多少数据才能推翻先验」，这一点在第 11.8 节的误导先验实验中会看得非常清楚。

11.2.3 贝叶斯老虎机（Bayesian bandits, p9, p18）

严格定义：贝叶斯老虎机 $(\mathcal{A},R,p[R])$ 在 $(A,R)$ 之上再加一个奖励分布的先验 $p[R]$。维护历史 $h_t=(a_1,r_1,\dots,a_{t-1},r_{t-1})$ 上的后验

并用 $p[R\mid h_t]$ 指导动作选择。讲义明确列出两条利用后验的路线：(a) 贝叶斯 UCB（Bayesian UCB）——用后验分位数当上界；(b) 概率匹配（probability matching）—— Thompson 采样。讲义同时给出一个诚实的警告：先验准确时性能更好，先验错得离谱时性能会更差（见 11.8 与实验 F）。

与 UCB 的对比：频率派 UCB 的 bonus $\sqrt{2\log(1/\delta)/N_t(a)}$ 只依赖计数，不需要先验，代价是要选一个 $\delta$（等价于用手调常数换取「对任意环境都成立」的保证）；贝叶斯 bandit 用先验换取更紧、更贴合实际环境的不确定性刻画，但失去分布无关（distribution-free）的稳健性。

11.2.4 概率匹配（Probability matching, p32–p35）

严格定义：设每个臂的 $Q(a)$ 在给定 $h_t$ 下是一个随机变量（因为参数未知），概率匹配按「$a$ 为最优动作的后验概率」选动作：

直观解释：已经确信最好的臂会被反复选；仍然模棱两可的臂会按「它可能是最好的」这一概率被选中——不确定性越大，被试探的概率越高。讲义的原话是「probability matching is often optimistic in the face of uncertainty: uncertain actions have higher probability of being max」（p35）。

困难点：这个概率一般难以从后验解析计算——要求一个 $m$ 维积分/排序概率。惊人之处：Thompson 采样恰好实现了它：

右端的意思是：从后验中抽一个奖励分布 $R$，取 argmax 得动作 $a$；重复无数次，$a$ 的出现频率就是左端的概率。具体示例：两个臂后验分别为 $\mathrm{Beta}(9,1)$（均值 0.9）与 $\mathrm{Beta}(4,5)$（均值 0.44），解析上 $P(\theta_1>\theta_2)\approx 0.9912$；从两个后验各抽一个样本、比较大小的经验频率是 $0.9910$（本讲代码实验 D，$M=4\times10^5$ 次采样）。与监督学习的对比：监督学习在预测时只输出一个点估计；概率匹配要求把整个后验搬进决策，这正是贝叶斯 RL 与「先估计再贪心」的本质区别。

11.2.5 Thompson 采样（Thompson Sampling, TS, p20）

严格定义（讲义 p20 伪代码的数学化）：初始化每臂先验 $p(R_a)$；每步 $t$：(1) 对每个臂从后验抽一个奖励分布 $\tilde R_a\sim p(R_a\mid h_t)$；(2) 计算 $\tilde Q(a)=\mathbb{E}[\tilde R_a]$；(3) 选

(4) 观测 $r_t$；(5) 用贝叶斯法则更新被拉动臂的后验（未被拉动的臂后验不变）。对 Bernoulli 奖励，第 (1)(5) 步就是「从 $\mathrm{Beta}(\alpha_a,\beta_a)$ 抽 $\theta_a$」与「$\alpha_a\!\mathrel{+}\!=r_t$ 或 $\beta_a\!\mathrel{+}\!=1-r_t$」。

直观解释：TS 相当于「把对世界的一种完整猜想当成真世界，并据此最优地行动，然后根据现实修正猜想」。它是 bandit 版的滚动时域 + 后验抽样，与 L12 的 PSRL 结构完全一致。与 $\varepsilon$-greedy 的对比：$\varepsilon$-greedy 的探索是无信息的（随机乱拉），TS 的探索是后验定向的（只试探那些「尚有可能最优」的臂），因此样本效率高得多；与 UCB 的对比见表 11-2。

11.2.6 regret 与 Bayesian regret（p37）

频率派 regret 假设存在一个真实但未知的参数 $\theta$，regret 是在该参数下对历史取期望：

其中 $\mathbb{E}_\tau$ 是对「算法 $\mathcal{A}$ 所产生的动作与奖励历史」取期望。贝叶斯 regret 在参数上也放一个先验：

细微差别（考试常考）：频率派界是「对任意 $\theta$ 都成立」的一致（uniform）保证，通常带 $\sqrt{\cdot}$ 与 $\log$ 因子、对间隙 $\Delta$ 敏感；贝叶斯界是对先验取平均的较弱要求，因此可以更小、更贴合实际，也正因此不能直接拿来宣称「对所有环境都好」。

11.2.7 用乐观性界 regret（p38）

讲义给出一个通用技巧：若 $U_t(a)$ 是一个同时对所有 $a$ 成立的上界，则

因为 $Q(a^)\le U_t(a^)\le U_t(a_t)$（第二个不等号来自 $a_t=\arg\max_a U_t(a)$ 的乐观贪心）。这个不等式把「比较真实最优」换成了「累加上界的超出量（excess）」，UCB 的证明骨架就是它（L10 详细推导过）。TS 的方差分析证明走的是同一类分解，只不过把「上界」换成「后验抽样」。

11.2.8 上下文老虎机（contextual bandit, p40–p41）

严格定义：上下文老虎机是 $(\mathcal{S},\mathcal{A},R)$，其中 $R_{a,s}(r)=P[r\mid a,s]$ 是给定状态 $s$ 与动作 $a$ 时的奖励分布；每步先观测上下文 $s_t$，再选 $a_t$，得到 $r_t\sim R_{a_t,s_t}$。当 $\mathcal{S}$ 或 $\mathcal{A}$ 很大时，须用函数表示 $(s,a)\mapsto r$，常见形式是奖励对特征的线性模型

「disjoint linear」变体让每条臂有自己的参数：$r(s,a)=\theta_a^\top\phi(s)+\epsilon$。讲义给出的实例是新闻文章推荐（Chapelle & Li, 2010）：臂 = 文章，奖励 = 是否点击，$Q(a)$ = 点击率；在数千人同时登录、上一位用户还没反馈（延迟反馈）的场景下，TS 的优势尤其明显（p42–p43 的 Check Your Understanding 就讨论这一点）。

11.3 算法伪代码与完整推导

11.3.1 Thompson 采样伪代码（讲义 p20）

Algorithm: Thompson Sampling for Bernoulli Bandits
---------------------------------------------------------------
Input : action set A = {1..m}; prior (alpha_a, beta_a) for each arm a
Output: action sequence a_1, a_2, ... and the maintained posteriors

1:  Initialize prior over each arm a: p(R_a)          # Beta(1,1) = uniform
2:  for iteration = 1, 2, ... do
3:      For each arm a, sample a reward distribution ~R_a from posterior
4:          theta_a ~ Beta(alpha_a, beta_a)           # p(R_a | h_t)
5:      Compute action-value function  Q(a) = E[~R_a] = theta_a
6:      a_t = argmax_{a in A} Q(a)                    # ties broken uniformly
7:      Observe reward r_t                            # r_t ~ Bernoulli(theta_a_t)
8:      Update posterior p(R_a_t) using Bayes rule:
9:          alpha_{a_t} += r_t ;  beta_{a_t} += 1 - r_t
10: end for

算法逻辑解说：(i) 第 3–4 步是唯一的随机性来源，每步都把整个后验「重置」成一个样本世界；(ii) 第 6 步在这个样本世界里贪心——所以 TS 不需要任何 bonus 项；(iii) 第 8–9 步只更新被拉臂，未被拉臂的后验原地不动，这正是共轭结构带来的 $O(m)$ 每步成本（与 UCB1 同阶，比每次重解 MDP 便宜得多）。

数学推导（TS 实现概率匹配）：设 $\tilde Q(a)$ 为从后验抽出的样本值。TS 选 $a_t=\arg\max_a\tilde Q(a)$，因此对任意 $a$，

最后一步用了「$\tilde Q$ 与 $Q$ 同分布（都是后验下的 $Q$）」这一事实——这正是概率匹配的定义。由全期望公式还可写成 $\pi(a\mid h_t)=\mathbb{E}_{R\mid h_t}[\mathbb{1}(a=\arg\max_a Q(a))]$。

与理论的对应：上式说明 TS 的探索是自校准的：后验越宽（不确定），样本取到极端值的概率越大，被选中的机会越多；后验收窄后自动退化为贪心。

11.3.2 Broken-toe 演示：逐步跟踪（p21–p30）

真值（虚构）$\theta_1=0.95$（Surgery）、$\theta_2=0.90$（Taping）、$\theta_3=0.10$（Nothing），先验全为 $\mathrm{Beta}(1,1)$：

三步后就锁定了最优臂，累计 regret 只有 $0.85$。注意讲义 p29 的笔误：该页把臂 1 的当前后验印成 $\mathrm{Beta}(2,1)$，但它已经观测到两次成功，前后一致的值应是 $\mathrm{Beta}(3,1)$（本讲代码按正确值推进）。TS vs 乐观性（p30）：同一玩具例中乐观性算法的拉动序列是 $a_1,a_2,a_3,a_1,a_2$，TS 是 $a_1,a_3,a_1,a_1,a_1$——乐观性确定性地把所有臂都试一遍（每个未访问臂都值 $V_{\max}$），TS 则按后验抽样，可能一开始就跳过错臂（这里是臂 3）也可能先试它。代价差异：乐观性对「臂数」有线性开销（必须每臂一次初始化），TS 没有强制初始化轮。

p50：把 PAC 指标与 regret 指标放在同一段历史上比较。设 $\varepsilon=0.05$，某步「$\varepsilon$-内」定义为 $\mathbb{1}\big(Q(a_t)\ge Q(a^)-0.05\big)$，$Q(a^)=0.95$：

两者各有 1 步落在 $\varepsilon$ 之外（乐观性错在第 3 步、TS 错在第 1 步），但错的位置不同、总 regret 相近（这 5 轮累计：乐观性 $0+0.05+0.85+0+0.05=0.95$，TS $0.85+0+0+0+0=0.85$）。本讲脚本用「最低索引优先」打破乐观性平局，得到 $a_1,a_2,a_3,a_1,a_1$，累计 $0.90$——差别仅来自平局规则，不影响结论。这正说明讲义 p7/p50 的两个框架在问不同的问题：regret 关心「总共亏了多少」（可以「经常小错」），PAC 关心「错得离谱的步数」（可以「偶尔大错」）。同一条轨迹可以 regret 相近而 PAC 表现不同——这是 L10/L12 引入 PAC 的动机（本讲只作过渡，PAC-MDP 的完整框架在 L12）。

11.3.3 贝叶斯 regret 界（p49）

讲义 p49 的结论形式是：记 $\mathrm{Regret}(\mathrm{UCB},T)$ 为 UCB 的频率派 regret，则

讲义原文为「Posterior sampling has the same (ignoring constants) regret bounds as UCB」，即 TS 的贝叶斯 regret 与 UCB 的 regret 界同阶（只差常数）。对 $K$ 臂、奖励有界的 bandit，UCB1 的经典界是

于是相应的贝叶斯 regret 界为 $O(\sqrt{KT\log T})$ 量级，且对先验取平均后常数更优。讲义同时强调一个反直觉的事实（p39）：TS 的频率派界（至今）不能匹配最好的频率派算法——即 $O(\sqrt{KT\log T})$ 这类对所有 $\theta$ 一致成立的界，标准 TS 还没被证明达到；但 TS 在经验上非常有效，尤其是在上下文 bandit 中（Chapelle & Li 的新闻推荐就是经典实证）。

11.3.4 贝叶斯 bandit 的最优策略：Gittins index（p44–p45）

TS 好用，但它最优吗？给定先验与已知 horizon，原则上可以算出一个真正最大化期望奖励的决策策略，但朴素做法会生成一个「以历史为输入的决策策略」，状态空间随 $t$ 爆炸。讲义给出出路：索引策略（index policy）——对每条臂只用自己的统计量算一个实数值索引，拉索引最大者（定义引自 Lattimore & Szepesvári, 2019）。对折扣贝叶斯 bandit，最优索引就是 Gittins index。

严格定义（退休/ prevailing-charge 形式）：单臂是一个「状态 = 后验 $(\alpha,\beta)$」的马尔可夫决策过程，每步可选「继续拉」或「退休」并领取固定报酬 $m$：

其中 $p=\tfrac{a}{a+b}$、$q=1-p$。索引 $G$ 是「使状态在继续与退休之间无差异的那个报酬」。最优性：以 $G$ 为索引的索引策略在折扣贝叶斯 bandit 上是最优的（Gittins 定理）。

TS 与 Gittins 的关系：两者都用后验，但规则不同——Gittins 索引是后验的确定性函数，TS 是后验的一次随机抽样；Gittins 需要解一个 DP（本讲代码在 $60\times60$ 后验网格上做 1001 次后向扫描），TS 每步只需 $O(m)$ 次采样。所以 TS 用极小的计算代价换取了「近似最优」，这正是它在深度 RL 场景里胜出的原因。

11.4 代码实现与实验分析

以下两个代码块均为自包含、可直接运行（仅 numpy / matplotlib / 标准库）；完整版实验脚本（含 broken-toe 逐步跟踪、p50 的 PAC/regret 对照表、$60\times60$ Gittins 网格）另存于 cs234/code/L11_ts_bayes.py，单次运行约 28 秒。

11.4.1 代码块 1：确定性奖励下的 UCB、regret 增长率与贝叶斯 regret

import numpy as np
import matplotlib
matplotlib.use("Agg")   # 无显示环境
import matplotlib.pyplot as plt
np.random.seed(0)


class BernoulliBandit:
    """多臂老虎机 (A, R)：臂 a 以概率 mu[a] 给奖励 1。"""
    def __init__(self, means, rng):
        self.mu = np.asarray(means, float)
        self.K = len(self.mu)
        self.star = float(self.mu.max())
        self.rng = rng

    def pull(self, a):
        return float(self.rng.random_sample() < self.mu[a])


class DeterministicBandit(BernoulliBandit):
    """同接口，但 r_t = mu[a] 精确成立（对应讲义 p2/p3 的思考实验）。"""
    def pull(self, a):
        return float(self.mu[a])


def run_ucb(b, T, rng):
    """UCB1: a_t = argmax_a Qhat(a) + sqrt(2 log t / N_t(a))。"""
    n = np.zeros(b.K); q = np.zeros(b.K); out = np.empty(T)
    for t in range(T):
        fresh = np.flatnonzero(n == 0)
        if fresh.size > 0:                    # 强制初始化轮：N_t(a) 先变 1
            a = int(fresh[0])
        else:
            a = int(np.argmax(q + np.sqrt(2.0 * np.log(t) / n)))
        r = b.pull(a); n[a] += 1; q[a] += (r - q[a]) / n[a]
        out[t] = b.star - b.mu[a]
    return out, n, q


def run_ts(b, T, rng, alpha0=1.0, beta0=1.0):
    """Bernoulli 奖励 + Beta 先验的 Thompson 采样。"""
    alpha = np.full(b.K, alpha0); beta = np.full(b.K, beta0)
    out = np.empty(T)
    for t in range(T):
        a = int(np.argmax(rng.beta(alpha, beta)))     # 每步抽一个样本世界
        r = b.pull(a); alpha[a] += r; beta[a] += 1 - r
        out[t] = b.star - b.mu[a]
    return out


def run_eps(b, T, rng, eps=0.1):
    n = np.zeros(b.K); q = np.zeros(b.K); out = np.empty(T)
    for t in range(T):
        fresh = np.flatnonzero(n == 0)
        if fresh.size > 0:
            a = int(fresh[0])
        elif rng.random_sample() < eps:
            a = int(rng.randint(b.K))
        else:
            a = int(np.argmax(q))
        r = b.pull(a); n[a] += 1; q[a] += (r - q[a]) / n[a]
        out[t] = b.star - b.mu[a]
    return out


print("--- 1) 确定性奖励：UCB 的经验均值就是真值 ---")
rng = np.random.RandomState(0)
reg, n, q = run_ucb(DeterministicBandit([0.9, 0.5, 0.3], rng), 2000, rng)
print("N_T =", n.astype(int), " Qhat =", q, " true =", [0.9, 0.5, 0.3])
print("max |Qhat-mu| =", float(np.abs(q - np.array([0.9, 0.5, 0.3])).max()),
      " R(2000) =", float(reg.sum()))
with np.errstate(divide="ignore", invalid="ignore"):
    print("naive t=0 bonus sqrt(2 log 0 / 0) =", float(np.sqrt(2 * np.log(0.0) / 0.0)))

print("\n--- 2) regret 增长率 R(2T)/R(T)，30 个随机种子 ---")
means = [0.9, 0.7, 0.6, 0.4, 0.2]
for name, fn in [("eps-greedy", lambda b, T, r: run_eps(b, T, r)),
                 ("UCB1", lambda b, T, r: run_ucb(b, T, r)[0]),
                 ("Thompson", lambda b, T, r: run_ts(b, T, r))]:
    R1 = np.mean([fn(BernoulliBandit(means, np.random.RandomState(s)), 1000,
                     np.random.RandomState(500 + s)).sum() for s in range(30)])
    R2 = np.mean([fn(BernoulliBandit(means, np.random.RandomState(s)), 2000,
                     np.random.RandomState(500 + s)).sum() for s in range(30)])
    print("%-11s R(1000)=%7.2f R(2000)=%7.2f ratio=%.3f" % (name, R1, R2, R2 / R1))

print("\n--- 3) 贝叶斯 regret E_{theta~Beta(1,1)^K}[R(T)]，60 个环境 ---")
for name, fn in [("Thompson", lambda b, T, r: run_ts(b, T, r)),
                 ("UCB1", lambda b, T, r: run_ucb(b, T, r)[0]),
                 ("eps-greedy", lambda b, T, r: run_eps(b, T, r))]:
    for T in (500, 1000):
        acc = 0.0
        for i in range(60):
            rr = np.random.RandomState(1000 + i)
            theta = rr.beta(1.0, 1.0, size=5)          # 先验抽一个真实 bandit
            acc += fn(BernoulliBandit(theta, rr), T,
                      np.random.RandomState(20000 + i)).sum()
        print("  %-11s T=%4d  BayesRegret=%7.2f" % (name, T, acc / 60))

print("\n--- 4) 误导先验 Beta(100,1) 加在一条真正差的臂上 ---")
theta_bad = np.array([0.10, 0.10, 0.10, 0.95])
good = bad = 0.0
for s in range(20):
    good += run_ts(BernoulliBandit(theta_bad, np.random.RandomState(300 + s)), 1000,
                   np.random.RandomState(400 + s)).sum()
    a0 = np.array([100.0, 1.0, 1.0, 1.0]); b0 = np.ones(4)
    alpha = a0.copy(); beta = b0.copy()
    bnd = BernoulliBandit(theta_bad, np.random.RandomState(300 + s))
    rr = np.random.RandomState(400 + s); acc = 0.0
    for t in range(1000):
        a = int(np.argmax(rr.beta(alpha, beta)))
        r = bnd.pull(a); alpha[a] += r; beta[a] += 1 - r
        acc += bnd.star - bnd.mu[a]
    bad += acc
print("  TS, honest prior Beta(1,1)   : %.2f" % (good / 20))
print("  TS, misleading Beta(100,1)   : %.2f" % (bad / 20))

代码做什么：第 1 段在确定性奖励环境上跑 UCB1，打印每臂拉动次数、经验均值、与真值的最大偏差，并显式演示「朴素地在 $t=0$ 处算 $\sqrt{2\log 0/0}$」会得到什么；第 2 段用 $R(2T)/R(T)$ 这个增长率判据区分线性与次线性 regret（线性给出 $2.0$，$\sqrt{T}$ 给出 $1.414$）；第 3 段按贝叶斯 regret 的定义先抽环境再跑算法，即对先验 $\mathrm{Beta}(1,1)^5$ 取平均；第 4 段把一条臂的先验故意设成 $\mathrm{Beta}(100,1)$（强烈相信它好），量化误导先验的代价。

RL 机制透视：(a) 增长率判据是本讲最实用的诊断工具——它不需要知道 $\Delta_a$，只看 regret 的形状就能识别算法是否「收敛」；(b) 贝叶斯 regret 的实验设计与频率派不同：环境的随机性来自先验，所以每个种子先抽 $\theta$ 再跑轨迹，两次期望的顺序不能交换；(c) 第 4 段展示的是先验强度 = 有效样本量的倒数：$\mathrm{Beta}(100,1)$ 意味着「相当于已经看过 100 次成功」，要推翻它需要上百次失败，所以 TS 会在坏臂上浪费大量步数——这正是讲义 p43 用来说明「TS 可能远差于乐观性」的机制。

实验观察（真实运行输出）：

• 确定性奖励、$\mu=(0.9,0.5,0.3)$、$T=2000$：$N_T=(1904,64,32)$，$\hat Q=(0.9,0.5,0.3)$，$\max_a\vert \hat Q(a)-\mu(a)\vert =0.0$，$R(2000)=44.8$（其中 $1.0$ 来自前三次强制初始化）。
• 朴素计算 sqrt(2*log(0)/0) 输出 nan，但 UCB1 的代码路径永远先做初始化轮，因此运行轨迹中从不出现 $0/0$。
• 增长率（30 种子）：$\varepsilon$-greedy $38.03\to73.02$，比值 1.920（≈线性）；UCB1 $80.67\to104.53$，比值 1.296；TS $13.17\to14.79$，比值 1.124。
• 贝叶斯 regret（60 环境）：TS $14.18\,(T{=}500)\to16.89\,(T{=}1000)$；UCB1 $48.22\to67.28$；$\varepsilon$-greedy $31.17\to52.55$。TS 在 $T=1000$ 时约为 UCB1 的 25%，与讲义 p49「同阶」的结论不矛盾（同阶只管 $\log$ 因子的指数，不管常数）。
• 误导先验：诚实先验 $6.46$，误导先验 $26.31$——代价约 4 倍。

11.4.2 代码块 2：概率匹配的数值验证与 Gittins index

import numpy as np
import matplotlib
matplotlib.use("Agg")   # 无显示环境
import matplotlib.pyplot as plt
np.random.seed(0)

# ---------- 1) TS 实现概率匹配：动作频率 == P(a 最优 | h_t) ----------
cases = [("Beta(4,5) vs Beta(7,5)", (4., 5.), (7., 5.)),
         ("Beta(1,1) vs Beta(4,5)", (1., 1.), (4., 5.)),
         ("Beta(9,1) vs Beta(4,5)", (9., 1.), (4., 5.))]
M = 400000
print("posterior (arm1 | arm2)      P(th1 > th2)   TS freq(a1)      gap")
for label, (a1, b1), (a2, b2) in cases:
    rr = np.random.RandomState(7)
    x = rr.beta(a1, b1, size=M); y = rr.beta(a2, b2, size=M)
    p_opt = float(np.mean(x > y))
    rr2 = np.random.RandomState(99)
    freq = float(np.mean(rr2.beta(a1, b1, size=M) > rr2.beta(a2, b2, size=M)))
    print("%-28s %13.4f %14.4f %8.4f" % (label, p_opt, freq, abs(p_opt - freq)))
print("=> TS 的动作频率等于 P(a 最优 | h_t)，即 TS = 概率匹配。")

# ---------- 2) Gittins index：退休形式的 DP ----------
GAMMA, AMAX, BMAX, TMAXC, NGRID = 0.9, 60, 60, 60, 1001


def make_gittins(gamma=GAMMA, amax=AMAX, bmax=BMAX, tmax=TMAXC, ngrid=NGRID):
    """G(a,b) = sup{m : V(a,b;m) >= 0}, V = max{0, mu - m + gamma E[V(next)]}。"""
    ag = np.arange(1, amax + 1); bg = np.arange(1, bmax + 1)

    def value_table(m):
        nxt = np.zeros((amax + 2, bmax + 2))
        for t in range(tmax, 1, -1):                  # 后向扫描，O(tmax^2)
            a_lo, a_hi = max(1, t - bmax), min(amax, t - 1)
            if a_lo > a_hi:
                continue
            a = np.arange(a_lo, a_hi + 1); p = a / t; b = t - a
            cont = gamma * (p * nxt[a + 1, b] + (1 - p) * nxt[a, b + 1])
            nxt[a, b] = np.maximum(0.0, p - m + cont)  # max{0,.} = 退休选项
        return nxt[np.ix_(ag, bg)]

    charges = np.linspace(0.0, 1.0, ngrid)            # V 对 m 分段线性递减
    Vs = np.stack([value_table(float(m)) for m in charges])
    pos = Vs > 0.0
    idx = np.clip(ngrid - 1 - np.argmax(pos[::-1], axis=0), 0, ngrid - 2)
    Vlo = np.take_along_axis(Vs, idx[None], axis=0)[0]
    Vhi = np.take_along_axis(Vs, (idx + 1)[None], axis=0)[0]
    den = np.where(Vlo - Vhi == 0, 1.0, Vlo - Vhi)
    frac = np.clip(Vlo / den, 0, 1)                   # 线性插值定位过零点
    tab = np.where(pos.any(axis=0),
                   charges[idx] + (charges[1] - charges[0]) * frac, 0.0)
    return (lambda a, b: float(tab[int(a) - 1, int(b) - 1])), tab


git, tab = make_gittins()
print("\nGittins index, Bernoulli arm with posterior Beta(a,b), gamma = 0.9")
print("%-12s %-14s %-10s" % ("Beta(a,b)", "posterior mean", "index G"))
for (a, b) in [(1, 1), (2, 1), (3, 1), (5, 1), (1, 2), (2, 2), (1, 3), (1, 5)]:
    print("%-12s %-14.4f %-10.4f" % ("Beta(%d,%d)" % (a, b), a / (a + b), git(a, b)))
ag = np.arange(1, 61)
means = ag[:, None] / (ag[:, None] + ag[None, :])
inside = (ag[:, None] + ag[None, :]) <= 40            # 远离截断边界
print("index >= posterior mean for every state with a+b <= 40:",
      bool(np.all((tab + 1e-9 >= means) | ~inside)))

# ---------- 3) 索引策略 vs TS vs UCB：断趾 bandit ----------
true_theta = np.array([0.95, 0.90, 0.10]); T = 50


class B:
    def __init__(self, mu, rng):
        self.mu = np.asarray(mu, float); self.star = self.mu.max(); self.rng = rng

    def pull(self, a):
        return float(self.rng.random_sample() < self.mu[a])


def run_ts(Bd, rng, T=T):
    al = np.ones(3); be = np.ones(3); out = np.empty(T)
    for t in range(T):
        a = int(np.argmax(rng.beta(al, be))); r = Bd.pull(a)
        al[a] += r; be[a] += 1 - r; out[t] = Bd.star - Bd.mu[a]
    return out


def run_ucb(Bd, rng, T=T):
    n = np.zeros(3); q = np.zeros(3); out = np.empty(T)
    for t in range(T):
        fr = np.flatnonzero(n == 0)
        a = int(fr[0]) if fr.size else int(np.argmax(q + np.sqrt(2 * np.log(t) / n)))
        r = Bd.pull(a); n[a] += 1; q[a] += (r - q[a]) / n[a]
        out[t] = Bd.star - Bd.mu[a]
    return out


rng = np.random.RandomState(11); Bg = B(true_theta, rng)
al = np.array([2., 1., 1.]); be = np.array([1., 2., 1.]); rig = np.empty(T)
for t in range(T):
    a = int(np.argmax([git(al[k], be[k]) for k in range(3)]))
    r = Bg.pull(a); al[a] += r; be[a] += 1 - r
    rig[t] = true_theta.max() - true_theta[a]
print("\ncumulative regret over T = 50, theta = (0.95, 0.90, 0.10)")
print("  Gittins index  R(50) = %6.2f" % rig.sum())
print("  Thompson       R(50) = %6.2f"
      % run_ts(B(true_theta, np.random.RandomState(11)), np.random.RandomState(12)).sum())
print("  UCB1           R(50) = %6.2f"
      % run_ucb(B(true_theta, np.random.RandomState(11)), np.random.RandomState(12)).sum())
print("initial priors [(2,1),(1,2),(1,1)] -> indices",
      np.round([git(2, 1), git(1, 2), git(1, 1)], 4))
print("index policy plays arm",
      int(np.argmax([git(2, 1), git(1, 2), git(1, 1)])) + 1)
rr = np.random.RandomState(3); s = rr.beta([2., 1., 1.], [1., 2., 1.])
print("TS samples theta", np.round(s, 4), "-> plays arm", int(np.argmax(s)) + 1)

代码做什么：第 1 段用同一组后验做两件事——解析地（蒙特卡洛近似）估计 $P(\theta_1>\theta_2)$，以及模拟 TS 的实际动作频率，两者应当相等；第 2 段用退休形式的 Bellman 方程求 Gittins index：对每个「恒定报酬 $m$」做一次后向扫描得到 $V(\cdot\,;m)$，再在 $m$ 的网格上用线性插值找到 $V=0$ 的过零点，从而一次算出整张后验网格的索引；第 3 段让索引策略、TS、UCB1 在断趾 bandit 上跑同样 50 步比较累计 regret，并打印「同一组先验下索引策略的选择 vs TS 的抽样」。

RL 机制透视：(a) 第 1 段是概率匹配的实证证明——TS 不需要显式计算那个难解的排序概率，抽样过程本身就把它算出来了；(b) Gittins 的 DP 里 np.maximum(0.0, ...) 就是退休选项，索引的数值意义是「这条臂此刻值多少」的相对价值，它把「探索价值」折算成当期等价报酬，所以索引策略天然处理探索-利用权衡；(c) 注意索引值普遍高于后验均值（$\mathrm{Beta}(1,1)$：$0.7030$ vs $0.5000$）——高出部分就是探索价值，这是 Gittins 与「贪心用均值」的本质区别；(d) 索引策略每步要比较索引，而 TS 每步只抽一次样，计算代价差了几个数量级。

实验观察（真实运行输出）：

• 概率匹配：$\mathrm{Beta}(4,5)$ vs $\mathrm{Beta}(7,5)$：$P=0.2554$，TS 频率 $0.2548$（差 $0.0006$）；$\mathrm{Beta}(1,1)$ vs $\mathrm{Beta}(4,5)$：$0.5553$ vs $0.5554$（差 $0.0001$）；$\mathrm{Beta}(9,1)$ vs $\mathrm{Beta}(4,5)$：$0.9912$ vs $0.9910$（差 $0.0002$）——全部在蒙特卡洛误差内。
• Gittins index（$\gamma=0.9$）：$G(1,1)=0.7030$、$G(2,1)=0.8000$、$G(3,1)=0.8460$、$G(5,1)=0.8910$；$G(1,2)=0.5000$、$G(2,2)=0.6350$、$G(1,3)=0.3800$、$G(1,5)=0.2490$。单调性正确：成功越多索引越高，失败越多索引越低。
• 「索引 $\ge$ 后验均值」在 $a+b\le 40$ 的所有格点上成立（True）；$60\times60$ 网格共 1001 次后向扫描、约 1.8 秒。
• 断趾 $T=50$：索引策略 $R(50)=0.00$（50 步全在最优臂上），TS $3.15$，UCB1 $4.40$。
• 同一先验组 $[(2,1),(1,2),(1,1)]$：索引 $[0.8000,0.5000,0.7030]\Rightarrow$ 选臂 1；TS 抽样 $\theta=[0.8792,0.4932,0.3773]\Rightarrow$ 也选臂 1（本例一致，但机制不同：前者确定性，后者随机）。

图：贝叶斯 regret 对比（原笔记引用的 code/L11_bayes_regret.png 未随笔记一并发布，此处保留说明）

图中曲线由 cs234/code/L11_ts_bayes.py 生成：TS（与 $c\sqrt{T}$ 参考线贴合）、UCB1、$\varepsilon$-greedy（尾部近似直线，即线性 regret）。

11.5 评估指标与理论保证

评估指标清单（本讲涉及）：(1) 累计与单步 regret $L_t$；(2) regret 增长率 $R(2T)/R(T)$——线性算法给 $2$，$O(\sqrt{T})$ 给 $\sqrt{2}\approx1.414$，$O(\log T)$ 给 $\approx1$；(3) 贝叶斯 regret；(4) 样本复杂度（达到 $\varepsilon$-最优或指定 regret 所需步数）；(5) 每步计算复杂度：UCB1 与 TS 均为 $O(m)$（TS 需 $m$ 次 Beta 采样），Gittins 需预解 DP、每步 $O(m)$ 次查表。

理论保证的具体形式：

• 共轭后验的正确性：$\theta\mid r\sim\mathrm{Beta}(r+\alpha,1-r+\beta)$（精确，无近似）。
• TS 实现概率匹配：$\pi(a\mid h_t)=P[Q(a)>Q(a^{\prime})\ \forall a^{\prime}\neq a\mid h_t]$（精确恒等式）。
• 贝叶斯 regret 界：$\mathrm{BayesRegret}(\mathrm{TS},T)\lesssim\mathrm{Regret}(\mathrm{UCB},T)=O(\sqrt{mT\log T})$（讲义 p49，忽略常数）。
• TS 频率派界的已知困难：标准 TS 的一致频率派界（当时）不匹配最好的频率派算法（讲义 p39）。
• Gittins 最优性：折扣贝叶斯 bandit 的最优策略是 Gittins index 索引策略（p45）。
• 乐观性界 regret：$\mathrm{Regret}\le\mathbb{E}[\sum_t U_t(a_t)-Q(a_t)]$（p38），要求 $U_t$ 同时对所有 $a$ 是上界。

条件依赖分析：(a) 先验质量决定贝叶斯方法的上限——先验准则 TS 极强，先验错则可能远差于 UCB（实验 F：$6.46$ vs $26.31$）；(b) horizon 是否已知决定「最优策略」是否可定义（Gittins 需要折扣或已知 horizon）；(c) 是否有上下文/函数逼近决定算法形态（线性上下文 bandit 需对 $\theta$ 维护不确定性集合）；(d) 反馈是否延迟影响 TS 在工程上的实现（p42–p43 的新闻推荐）。

11.6 与其他讲次的关联

• L9（Data Efficient RL: Bandits）：本讲的起点。L9 给出 MAB 记号、regret 定义、贪心/$\varepsilon$-greedy 的线性 regret 反例，以及 UCB1 的 $O(\sqrt{KT\log T})$ 证明骨架；L11 复用全部记号，只把「无先验 + 乐观性」换成「有先验 + 概率匹配」。
• L10（Fast RL: 贝叶斯 bandits、PAC）：L10 的 lecture10post 里已经出现 BayesRegret 与 TS 的框架，并给出 PAC 定义；L11 是同一材料的延续与深化（lecture11 首页即承接 “Last time: Bandits and regret and UCB”）。本讲 p50 的玩具表正是 L10 PAC 定义的直接应用。
• L12（Fast RL: MDPs）：lecture12 p4 明确写 “Last time: Fast Learning (Bayesian bandits to MDPs)”，其 p21–p23 把本讲的贝叶斯 bandit 直接推广为贝叶斯模型 RL / PSRL（维护 $p[P,R\mid h_t]$、每回合抽一个 MDP 并解最优策略），p9–p16 给出 PAC / MBIE-EB / Simulation Lemma。也就是说：本讲的 TS $\to$ L12 的 PSRL；本讲的概率匹配 $\to$ L12 的 PAC-MDP 乐观初始化。本讲不讲这些证明细节。
• L13–L14（MCTS）：UCB 树搜索把 L9 的 UCB 与「采样 + 树」结合；本讲的 Gittins index 与 TS 同属「用不确定性引导搜索」的思想谱系。
• L4（Q-learning）：L4 的 $\varepsilon$-greedy 探索是无信息探索的典型，本讲的实验正好量化了它的线性 regret 与 TS 的差距。
• L16（Value Alignment）：与本讲无关（同为 lecture10post.pdf 的后半部分，由另一位作者撰写）。

11.7 关键要点

1. 贝叶斯假设换来了什么：先验 $p[R]$ 把「不确定性」变成可计算的后验分布，于是探索可以量化定向；代价是丢掉分布无关的稳健性——先验错，一切错。
2. 共轭是工程可行性的关键：Bernoulli–Beta 让后验更新只需 $O(1)$ 整数加法（$\alpha\!\mathrel{+}\!=r$，$\beta\!\mathrel{+}\!=1-r$）。
3. TS = 概率匹配：$\pi(a\mid h_t)=P[Q(a)>Q(a^{\prime})\ \forall a^{\prime}\neq a\mid h_t]$，由「从后验抽样 + argmax」精确实现；不需要显式积分排序概率。
4. 乐观性不是 TS 的专利，但机制不同：UCB 用确定性上界 $U_t$，TS 用后验抽样；两者都在 regret 意义下达到 $O(\sqrt{mT\log T})$（贝叶斯意义下 TS 与 UCB 同阶），但 TS 的一致频率派界尚未匹配最好算法。
5. regret 与 PAC 是两把不同的尺子：regret 累加「亏了多少」，PAC 数「错得离谱的步数」；同一条 p50 轨迹上两者各有 1 步越界，但累计 regret 几乎相同（$0.90$ vs $0.85$）。
6. 诊断 regret 的实用判据：$R(2T)/R(T)$——实测 $\varepsilon$-greedy $1.92$（线性）、UCB1 $1.30$、TS $1.12$（本讲实验，$K=5$）。
7. 最优 ≠ 可行：折扣贝叶斯 bandit 的最优策略是 Gittins index（索引值高于后验均值，差额即探索价值），但需要解 DP；TS 是它的 $O(m)$ 近似，实践中常常足够好。

11.8 常见误区与注意事项

1. 误区：UCB 在确定性环境中会因为 $\sqrt{2\log t/N_t(a)}$ 出现 0/0 而崩溃。 正确认识：UCB1 的第一阶段会强制每臂各拉一次，因此 bonus 被求值时 $N_t(a)\ge1$ 恒成立；只有「朴素的实现」在 $t=0$、$N=0$ 处求值才会得到 nan（本讲实验打印出 nan 正是为了说明这一点）。确定性环境下 UCB 不仅不崩溃，而且表现更好：单次观测的经验均值就等于真值，置信界以概率 $1$（而非 $1-\delta$）成立，于是 regret 次线性且以概率 1 成立——这正是 p3 的答案（选第 1 项）。选项中「会以严格正概率出现线性 regret」是错的（那是随机环境 + 贪心/悲观的情形）；p2 里多印的「确定性环境下 UCB 一定比随机环境 regret 更大」也是干扰项（实测确定性 $103.20$、随机 $104.53$，前者并不更大）。
2. 误区：TS 的贝叶斯 regret 界就是它的频率派 regret 界。 正确认识：$\mathrm{BayesRegret}$ 对先验取了平均，是更弱的要求；讲义 p39 明确说标准 TS 的频率派界（当时）不能匹配最好的频率派算法。因此不能用「TS 与 UCB 同阶」去宣称「TS 对任意环境都和 UCB 一样好」。
3. 误区：概率匹配就是「按后验均值贪心 + 偶尔随机」。 正确认识：概率匹配按 $P(a\ \text{最优}\mid h_t)$ 抽样，这个概率随不确定性自动增大；它不是「以固定概率随机」，$\varepsilon$ 是数据无关的常数，而 TS 的探索概率由后验宽度决定并自动衰减到 0。实测中 $\varepsilon$-greedy 的 regret 增长率是 $1.92$（线性），TS 是 $1.12$。
4. 误区：先验只是一个无伤大雅的初始化技巧。 正确认识：先验强度直接决定「要多少数据才能推翻它」。$\mathrm{Beta}(100,1)$ 相当于已经看过 100 次成功；在真实成功率 $0.1$ 的臂上，TS 的 regret 从 $6.46$ 恶化到 $26.31$（4 倍）。p43 的答案正因此是「1 对、2 错、3 对」——选项中「乐观性在新闻推荐里一定更好」是错的：乐观性是数据驱动的，不需要先验，所以在先验不可信时更稳。
5. 误区：Gittins index 就是对后验均值的某种加权，所以和 TS 差不多。 正确认识：Gittins index 是折扣贝叶斯 bandit 的最优索引，其数值普遍严格高于后验均值（$\mathrm{Beta}(1,1)$：$0.7030$ vs $0.5000$），差额是「未来探索的期权价值」，必须解 Bellman 方程才能得到；TS 是它的抽样近似，两者在玩具例上可能给出同一动作（本讲实验都是臂 1），但机制与代价完全不同。
6. 误区：上下文 bandit 只是「多了一个输入的老虎机」，TS 不能直接用。 正确认识：上下文 bandit 中奖励的期望是 $(s,a)$ 的函数，需要把不确定性从「标量奖励」转移到「参数 $\theta$」（如线性模型 $r=\theta^\top\phi(s,a)+\epsilon$），再用 $\theta$ 的不确定性集合/后验来解释 $r$ 的不确定性；Chapelle & Li (2010) 的新闻推荐是 TS 在此设定下的经典成功案例，也是默认项目要求实现的算法之一。
7. 注意（讲义笔误）：lecture11pre/post.pdf 首页标题写作 “Lecture 13: Fast Reinforcement Learning” 并自注 “Typo: Lecture 11”；p29 把臂 1 的后验印成 $\mathrm{Beta}(2,1)$（应为 $\mathrm{Beta}(3,1)$）。引用时以正确值为准，并在正文注明。

11.9 思考题（带答案）

思考题 1（判断题复现，p2–p3）：在确定性奖励的 bandit 中，下列哪些陈述为真？(1) UCB 会以概率 1 具有次线性 regret；(2) UCB 会以某个严格正概率具有线性 regret；(3) UCB 会出现除以零，因而无法处理确定性环境；(4) 确定性环境下 UCB 一定比随机环境 regret 更大。

答案：只有 (1) 为真。

• (1) 真。确定性意味着「拉一次就能精确知道该臂的真实期望」，即 $\hat Q_s(a_i)=\mu_i$ 对 $s=1$ 就成立。于是 UCB 的置信上界在没有 $\delta$ 的意义下以概率 1 成立（讲义原话：the confidence bounds hold with 100% probability (not just $1-\delta$ probability)），UCB 的证明骨架照搬即可得以概率 1 次线性的 regret。实验验证：确定性下 $\max_a\vert \hat Q(a)-\mu(a)\vert =0.0$，30 个种子 regret 的 std = 0.00。
• (2) 假。线性 regret 需要「以正概率永久锁死在次优臂」，这在随机奖励 + 纯贪心 + 坏初值时才会发生；确定性奖励下第一次拉动即锁定真值，不存在这种事件。
• (3) 假。UCB1 的初始化阶段保证 $N_t(a)\ge1$ 后才计算 bonus；nan 只出现在「朴素地在 $t=0$ 求值」这一非算法路径上。
• (4) 假。实验：$\mu=(0.9,0.7,0.6,0.4,0.2)$、$T=2000$、30 种子下，确定性 $R=103.20$，Bernoulli $R=104.53$——确定性并不更差（直觉上更小，因为单次观测就无偏）。

思考题 2（推导题）：从 Thompson 采样的定义出发，证明它实现概率匹配；并由此说明「TS 在不确定性面前是乐观的」。再对 $m=2$、后验为 $\mathrm{Beta}(9,1)$ 与 $\mathrm{Beta}(4,5)$ 的臂，解释为什么不确定性更大的臂会有可观的被选概率。

答案： 设 $\tilde Q(a)$ 为从后验 $p(Q(a)\mid h_t)$ 抽出的样本。TS 取 $a_t=\arg\max_a\tilde Q(a)$，故

因为 $\tilde Q$ 与 $Q$ 在给定 $h_t$ 下同分布（抽样不改变分布），右端等于 $P[Q(a)>Q(a^{\prime})\,\forall a^{\prime}\neq a\mid h_t]$，即概率匹配。等价地，$\pi(a\mid h_t)=\mathbb{E}_{R\mid h_t}[\mathbb{1}(a=\arg\max_a Q(a))]$。 「乐观」体现在：一个后验方差大的动作，其 $Q$ 的分布右尾厚，因此「成为最大值」的概率高——与它的均值高低无关。对 $\theta_1\sim\mathrm{Beta}(9,1)$、$\theta_2\sim\mathrm{Beta}(4,5)$，解析上 $P(\theta_1>\theta_2)\approx0.9912$，本讲实验测得 TS 选臂 1 的频率 $0.9910$；反例则把两臂换成 $\mathrm{Beta}(4,5)$（均值 0.44）与 $\mathrm{Beta}(1,1)$（均值 0.5）：均值只差 $0.06$，但后者方差大得多，$P(\theta_2>\theta_1)=0.5553$（实验值 $0.5554$）——方差更大的一方赢得了超过一半的选择概率，这就是「面对不确定性保持乐观」的定量含义。

思考题 3（计算题）：某场景中臂 1 的先验被设为 $\mathrm{Beta}(100,1)$，真实成功率为 $0.1$；臂 2–4 先验 $\mathrm{Beta}(1,1)$，其中臂 4 真实成功率为 $0.95$。用它解释讲义 p43 的答案，并说明为什么「UCB 会更好」。

答案：$\mathrm{Beta}(100,1)$ 的均值是 $100/101\approx0.9901$，等价于「已经观测到 99 次成功、0 次失败」。要把它拉回 $0.1$ 附近，需要约 $100$ 次失败（每失败一次 $\beta$ 加 1），而每次试验都以 $0.9$ 的概率失败，所以大约要 100 多步才会放弃它。实测（20 次试验平均、$T=1000$）：诚实先验 $\mathrm{Beta}(1,1)$ 的 regret 是 $6.46$，误导先验是 $26.31$——约 4 倍，验证了讲义「TS could cause much worse performance than optimism if the initial prior is very misleading」。UCB1 不需要先验，其 bonus 完全由计数驱动，因此不会继承这个错误假设：它在前 4 步初始化后立刻就能通过 $\sqrt{2\log t/N_t(a)}$ 把臂 1 压下去（本讲实验 F 中 UCB1 在同样环境下的 regret 为 $38.85$——在没有正确先验可用时，它比误导先验的 TS 好，但明显差于有正确先验的 TS，这也是「先验带来收益也带来风险」的双面性）。

思考题 4（推导题）：对后有先验 $(\alpha,\beta)$ 的 Bernoulli 臂，写出其 Gittins index 的 Bellman 方程，并说明：(a) 为什么 $G(\alpha,\beta)$ 会高于后验均值 $\alpha/(\alpha+\beta)$；(b) 用本讲实验的数值验证这一点；(c) 从计算复杂度角度解释「Gittins 最优但 TS 更常用」。

答案：

(a) 大括号里的第二项是继续拉的期权价值：即使当前均值 $\mu$ 略低于 $m$，未来观测可能把后验推高（成功则 $\mu$ 上升），这个上行期权使「继续」比「立刻退休」更有价值，于是使状态无差异的 $m$ 可以超过当前均值。严格地，$V(a,b;\mu(a,b))>0$（因为期权价值非负且成功分支严格改善），故 $G>\mu$。 (b) 实验数值：$G(1,1)=0.7030>\mu=0.5000$（差 $+0.2030$）；$G(2,1)=0.8000>\mu=0.6667$；$G(1,5)=0.2490>\mu=0.1667$；在 $60\times60$ 后验网格、$a+b\le40$ 的全部格点上均满足 $G\ge\mu$（打印 True）。同时索引保持单调：$G(1,1)<G(2,1)<G(3,1)<G(5,1)$，$G(1,5)<G(1,3)<G(1,2)$。 (c) Gittins 需要先解一个 DP：本讲实现要在后验网格上做 $1001$ 次后向扫描（$60\times60$ 网格约 $1.8$ 秒）才能得到索引表，且对每个新的先验族/折扣因子都要重算；TS 每步只需 $m$ 次 Beta 采样与一次 argmax，即 $O(m)$。在臂数大、先验不断变化、或需要函数逼近的场景（L12 的深度 RL），TS 的「近似最优但极便宜」远比「精确最优但不可计算」实用——这正是 p44–p45 想传达的张力。