2.1 探索与利用

本节导读

核心内容

• 理解没有动作标签时，智能体怎样根据奖励改进行动。
• 建立“选择动作、观察奖励、更新估计”的最小强化学习循环。
• 用期望回报比较均匀随机、始终选最优、先试后定三种策略，看清探索成本与小样本误判。
• 理解探索与利用为什么会从试错学习中自然出现。

强化学习涉及状态、动作、奖励、策略和价值等多个概念。如果一开始就把这些概念放在一起讨论，就不容易看清智能体究竟是怎样从经验中学会选择动作的。因此，本节先从一个简单的多臂老虎机故事开始，只保留动作和奖励，再逐步加入强化学习所需的其他概念。

第 1 章中，我们使用 PPO 训练了一个控制 CartPole 的智能体。在这个任务中，程序并不会告诉智能体每一步的正确动作。智能体选择向左推或向右推，环境返回奖励，智能体再根据奖励调整后续的选择。这就是强化学习的基本学习方式。

现在，我们把这个过程简化一下。假设智能体面前有 A、B 两台老虎机。它每次选择一台，拉动摇臂并获得一个分数。这里，选择哪台老虎机是动作，拉动后得到的分数是奖励。

智能体第一次拉动 A 得到 6 分，第一次拉动 B 得到 4 分。根据这两次结果，下一次选择 A 是很自然的。不过，每台老虎机给出的奖励并不固定。一次得到 6 分，不代表以后每次都能得到 6 分；一次得到 4 分，也不能说明这台老虎机一定较差。

因此，智能体需要多次拉动老虎机，根据已经得到的奖励估计它们的平均奖励。老虎机也可以不止两台。把可选的老虎机数量记为 $K$，智能体要在 $K$ 台老虎机之间反复选择。这样的任务称为多臂老虎机问题（Multi-Armed Bandit Problem）。

有了平均奖励的估计，智能体可以继续选择当前估计最好的老虎机。这样做称为利用（exploitation）。不过，如果总是选择同一台老虎机，其他老虎机的数据就不会增加，早期的错误判断也无法得到修正。因此，智能体还需要尝试那些选择次数较少、平均奖励仍不确定的老虎机。这样做称为探索（exploration）。

本节我们将学习怎样估计动作的平均奖励，以及怎样在探索和利用之间进行选择。下一节再加入会随动作变化的状态，把这个单步问题扩展为序列决策问题。

核心概念

利用是选择当前估计最好的动作，探索是尝试仍然不确定的动作。探索会暂时消耗行动机会，却能产生新的信息；利用使用已有信息获得奖励，却可能把智能体锁定在早期误判的动作上。

核心公式

$$\mathbb{E}[R_a]=\sum _{r}rP(R_a=r)\text{（期望奖励：动作 }a\text{ 长期平均每次能得多少）}$$

期望奖励：

• $R_a$：选择动作 $a$ 后得到的随机奖励。
• $P(R_a=r)$：动作 $a$ 输出奖励 $r$ 的概率。
• $\mathbb{E}[R_a]$：所有可能奖励按概率加权的平均值。

$${\hat{\mu }}_a=\frac{1}{N_a}\sum _{i=1}^{N_a}{r}_i\text{（样本均值：估计动作 }a\text{ 的平均奖励）}$$

动作奖励估计：

• $N_a$：动作 $a$ 已经被选择的次数。
• $r_i$：第 $i$ 次选择动作 $a$ 后得到的奖励。
• ${\hat{\mu }}_a$：根据已有样本算出的平均奖励估计。

$$A_t=\{\begin{array}{ll}\arg {\max }_a{\hat{\mu }}_a,& \text{概率 }1-ϵ\\ \text{从所有动作中随机选择},& \text{概率 }ϵ\end{array}\text{（epsilon 贪心：在利用之外保留探索）}$$

$ϵ$-贪心策略：

• $A_t$：第 $t$ 轮实际选择的动作。
• $1-ϵ$：选择当前估计最优动作的概率。
• $ϵ$：随机尝试其他动作的概率。

用期望比较三种策略

现在给两台老虎机配上具体的数字：A 台出奖率 60%，B 台出奖率 40%。奖励规则也换成最容易计算的版本——中奖得 +1，未中奖得 −1。总共有 100 轮机会。

两个出奖率是环境内部的参数，下面的期望计算要用到它们；智能体在游戏里看不到这两个数，只能靠尝试去估计。

期望是什么

比较策略之前，需要一个工具回答“一个随机选择平均能得多少分”。这个工具就是期望（expectation）。

先从一个熟悉的例子开始。抛一枚均匀硬币，正面赢 1 元，反面亏 1 元。抛 1000 次，大约 500 次正面、500 次反面，总盈亏为

$$500\times (+1)+500\times (-1)=0$$

把次数换成比例再看一遍。500 恰好是 $0.5\times 1000$，代入后分子分母的 1000 约掉：

$$\frac{0.5\times 1000\times (+1)+0.5\times 1000\times (-1)}{1000}=0.5\times (+1)+0.5\times (-1)=0$$

这就是期望的算法：每种结果的数值乘以它出现的概率，再全部相加。写成一般形式：

$$\mathbb{E}[X]=\sum _{i=1}^n{p}_i\cdot x_i$$

其中 $x_i$ 是第 $i$ 种结果，$p_i$ 是它出现的概率。期望的含义是长期平均：单次结果会上下波动，重复次数多了，平均值会趋近期望值。

用这个算法计算两台机器每次投币的期望：

$$\mathbb{E}[R_A]=0.6\times (+1)+0.4\times (-1)=+0.2$$

$$\mathbb{E}[R_B]=0.4\times (+1)+0.6\times (-1)=-0.2$$

A 台平均每次赚 0.2，B 台平均每次亏 0.2。下面的策略比较全部建立在这两个数上。

策略 1：均匀随机

每轮以各 50% 的概率选择 A 或 B。一轮的结果分两步产生：先选机器，再看中奖与否，因此一轮共有四种结果：

事件	奖励	概率
选 A 且中奖	+1	0.5 × 0.6 = 0.3
选 A 且未中奖	−1	0.5 × 0.4 = 0.2
选 B 且中奖	+1	0.5 × 0.4 = 0.2
选 B 且未中奖	−1	0.5 × 0.6 = 0.3

按期望的算法，四种结果的数值乘以概率再相加：

$$\mathbb{E}[R_{\text{每轮}}]=0.3\times (+1)+0.2\times (-1)+0.2\times (+1)+0.3\times (-1)=0$$

也可以先按机器分组：选到 A 的轮次平均赚 0.2，选到 B 的轮次平均亏 0.2，两种情况各占一半：

$$\mathbb{E}[R_{\text{每轮}}]=0.5\times 0.2+0.5\times (-0.2)=0$$

两种算法得到同一个数。分组算法的依据是全期望公式，推导见补充框。

补充：全期望公式——先分组再平均的依据

全期望公式把总体平均拆成各组内部平均的加权和：

$$\mathbb{E}[R]=P(\text{选A})\mathbb{E}[R\mid \text{选A}]+P(\text{选B})\mathbb{E}[R\mid \text{选B}]$$

$\mathbb{E}[R\mid \text{选A}]$ 读作“选了 A 的条件下，奖励的平均值”，在这里就是 $\mathbb{E}[R_A]=0.2$。公式的含义是：总体平均 = 进入某组的概率 × 该组内部平均，再把各组相加。

它和逐项枚举是同一件事。枚举里用的联合概率可以拆成两步概率的乘积：

$$P(\text{选A且中奖})=P(\text{选A})\times P(\text{中奖}\mid \text{选A})=0.5\times 0.6=0.3$$

分组写法只是把枚举的四项按机器重新括起来：

$$0.5\times (0.6\times 1+0.4\times (-1))+0.5\times (0.4\times 1+0.6\times (-1))$$

每轮期望是 0，那么 100 轮的总期望怎么算？这里用到概率论的一个基本性质：

期望的线性性质：对任意随机变量 $X_1,X_2,\dots ,X_n$（不要求相互独立），

$$\mathbb{E}\left[\sum _{i=1}^n{X}_i\right]=\sum _{i=1}^n\mathbb{E}[X_i]$$

和的期望等于期望之和。

因此 100 轮的总期望就是每轮期望相加：

$$\mathbb{E}[R_{100}]=\underset{100}{\underbrace{0+0+\cdots +0}}=0$$

均匀随机的回报在 0 附近波动，选 A 赚到的恰好被选 B 亏掉的抵消。这个策略完全不学习：不管已经看到多少次结果，它始终五五开，不会利用任何“A 好像更好”的证据。

策略 2：始终选 A

假设事先知道 A 更好，100 轮全部投 A。每轮期望就是 A 的期望 0.2：

$$\mathbb{E}[R_{100}]=100\times 0.2=20$$

20 是这个环境里能达到的最好成绩，可以作为其他策略的参照上限。它的前提在真实问题里无法满足：哪台机器更好，必须由尝试得知。

策略 3：先试后定

更接近真实情况的做法分两段：前 20 轮交替尝试 A 和 B（各 10 次），记录各自的中奖比例；后 80 轮全部投给观测比例更高的一台。

前 20 轮每轮的期望与均匀随机相同，为 0。假设探索阶段判断正确、后 80 轮锁定 A，那么总期望为

$$\mathbb{E}[R_{100}]=0+80\times 0.2=16$$

比策略 2 少 4 分。这 4 分是探索成本：前 20 轮里花在 B 上的机会没有产出，换回的是关于两台机器的信息。

先试后定到这里已经展示了探索与利用的基本取舍：前 20 轮换取信息，后 80 轮使用信息。不过这笔账还隐藏一个前提——探索阶段真的能把更好的机器判断出来。下面检验这个前提。

观测比例会偏离真实比例

“10 次尝试足够看清两台机器”这个前提并不牢靠。先区分两个概念：真实出奖率是机器的固有参数，A 是 60%，意思是长期投下去，中奖比例会靠近 60%；观测出奖率是这一次 10 连投里数出来的比例，它随运气波动。

A 的真实出奖率是 60%，并不保证每 10 次恰好中 6 次。一组 10 连投可能只中 4 次，也可能中 7 次。下面是一次可能出现的探索记录（✅ 中奖，❌ 未中奖）：

机器	真实出奖率	10 次结果	中奖次数	观测出奖率
A	60%	❌✅❌❌✅❌✅❌✅❌	4	40%
B	40%	✅❌✅✅❌❌✅❌✅❌	5	50%

两台机器的固有参数没有变：A 每次仍有 60% 的机会中奖，B 每次仍只有 40%。只是这一组样本里，A 的运气差了一些，B 的运气好了一些。按观测比例决策，后 80 轮会全部投给真正较差的 B：真实更好的选项，在短期样本里显得更差。

补充：10 次里中几次，本身就是随机的

把第 $i$ 次投 A 的结果记为 $X_i$（中奖为 1，未中奖为 0），则 $P(X_i=1)=0.6$。10 次的总中奖次数

$$N_A=X_1+X_2+\cdots +X_{10}$$

是随机变量，可能等于 6，也可能等于 4 或其他值。观测出奖率 ${\hat{p}}_A=N_A/10$ 只是这一组样本的临时估计；机器的真实参数仍是 $p_A=0.6$。期望描述的是长期平均：$\mathbb{E}[N_A]=10\times 0.6=6$，即重复很多组 10 连投时，每组中奖次数的平均值趋近 6，单独一组完全可能偏离。

“恰好中 $k$ 次”的概率由二项分布给出：

$$P(N=k)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)p^k(1-p{)}^{n-k}$$

以 A 恰好中 4 次为例：

$$P(N_A=4)=\left(\genfrac{}{}{0ex}{}{10}{4}\right)\times 0.6^4\times 0.4^6\approx 11.1\%$$

三个因子各自的意思：$\left(\genfrac{}{}{0ex}{}{10}{4}\right)=210$ 是组合数，表示 10 个位置里选 4 个作中奖位置有多少种选法，只看哪些位置、不看顺序；$0.6^4$ 是这 4 次中奖各自的概率；$0.4^6$ 是其余 6 次未中奖各自的概率。每一种位置组合的概率都相同，因此总数要乘上组合数。

也就是说，一台真实出奖率 60% 的机器，10 次里只中 4 次这件事大约每 9 次就会遇到 1 次，并不罕见。

概率论保证的是试得足够多时，观测比例会靠近真实比例（大数定律）。10 次这样的短样本，不在保证范围内。

真正影响回报的是误判概率：探索阶段结束时，B 的中奖次数超过 A 的概率。按 A 的中奖次数分情况：

A 中奖次数	B 需要超过的次数	是否误判
0	1–10	是
1	2–10	是
⋮	⋮	⋮
9	10	是
10	不可能超过	否

A、B 中奖次数相同时锁定 A，计入判断正确。

补充：12.8% 是怎样加出来的

误判事件是 $n_A<n_B$。A 的 10 次与 B 的 10 次相互独立，所以“A 中 4 次且 B 中 5 次”这类组合的概率是两个概率的乘积；不同组合互不重叠，所以总误判概率是所有满足 $n_A<n_B$ 的组合概率之和：

$$P(\text{误判})=\sum _{k=0}^{9}P(n_A=k)\cdot P(n_B\ge k+1)\approx 12.8\%$$

约 12.8% 意味着：每 8 次左右完整的 100 轮实验中，约有 1 次会把较差的机器判断成较好的。一旦误判，后 80 轮全部投 B：

$$\mathbb{E}[R_{100}\mid \text{误判}]=0+80\times (-0.2)=-16$$

把两种结局按概率加权，得到策略 3 的完整期望：

$$\mathbb{E}[R_{100}]=87.2\%\times 16+12.8\%\times (-16)\approx 11.9$$

比不考虑误判的 16 又低约 4 分。两层损失的来源不同：第一层（20 − 16 = 4）是探索花掉的机会；第二层（16 − 11.9）是探索得到的样本太少、估计出错。策略的最终表现同时受这两层制约。

如果两台机器的差距缩小到 52% 对 48%，各试 10 次的误判概率约为 34%，打平的概率约 17%——超过一半的实验要么锁定错误的机器，要么分不出高下。探索的样本量直接决定回报：样本太少，误判概率高；样本太多，探索成本又吃掉收益。怎样分配探索机会，正是后面几节反复处理的问题。

真实期望看不到，能看到的只有一次次尝试的样本。策略设计要解决的，就是怎样用这些有限样本估计和使用动作价值。下面先把两台机器推广成一般的多臂老虎机问题。

多臂老虎机问题

两台机器是这个问题的最小版本。把机器数量推广为 $K$ 台，就得到一般的多臂老虎机：每个摇臂 $a\in \{1,2,\dots ,K\}$ 都对应一个未知奖励分布 $R_a$，拉动一次会返回一个随机奖励。智能体不知道哪个摇臂平均奖励最高，只能通过一次次尝试来估计。

形式化地说，第 $t$ 轮智能体选择一个动作 $A_t$，然后观察奖励：

$$R_t\sim R_{A_t}$$

每个摇臂的真实期望奖励记为：

$${\mu }_a=\mathbb{E}[R_a]$$

如果已经知道所有 ${\mu }_a$，最好的动作就是：

$$a^{\ast }=\arg \underset{a}{\max }{\mu }_a$$

真正的问题在于，智能体一开始并不知道这些期望。它必须先试，才能获得数据；但每一次试错都会消耗一次行动机会。如果一直探索，智能体会把大量机会浪费在差动作上；如果过早利用，又可能因为早期随机结果误判，把真正好的动作排除掉。

多臂老虎机去掉了状态转移和长期回报，只保留动作选择和奖励反馈。这个简化让我们先看清强化学习里最早出现的难题：动作价值不是提前给出的，而是在交互中估计出来的。

从期望奖励到行动规则

智能体会为每个动作维护一个估计值 ${\hat{\mu }}_a$。如果动作 $a$ 已经被选择过 $N_a$ 次，得到过奖励 $r_1,r_2,\dots ,r_{N_a}$，最直接的估计方式是样本均值：

$${\hat{\mu }}_a=\frac{1}{N_a}\sum _{i=1}^{N_a}{r}_i$$

这个公式回答的是“这个动作目前看起来平均能得多少分”。有了估计值，还需要一个行动规则，把这些估计变成下一步选择。最直接的规则是贪心策略：

$$A_t=\arg \underset{a}{\max }{\hat{\mu }}_a$$

贪心策略每一步都选择当前估计最高的动作。它看起来合理，却有一个明显问题：早期样本很少，估计值可能被偶然结果严重影响。前面的计算给出过一个定量例子：60% 对 40% 的两台机器各试 10 次，约有 12.8% 的概率把较差的一台判断成较好的。一个真实期望很高的摇臂，如果第一次拉到低奖励，就可能长期得不到再次尝试的机会。

因此，强化学习中的策略不能只回答“当前哪个动作估计最高”，还要回答“哪些动作虽然现在估计不高，但仍然值得再试”。这就是探索和利用问题。

$ϵ$-贪心策略

$ϵ$-贪心策略在贪心动作之外保留一小部分随机探索。每一步先掷一次概率为 $ϵ$ 的硬币：

• 以 $1-ϵ$ 的概率选择当前估计最好的动作；
• 以 $ϵ$ 的概率随机选择一个动作。

写成公式就是：

$$A_t=\{\begin{array}{ll}\arg {\max }_a{\hat{\mu }}_a,& \text{概率 }1-ϵ\\ \text{从所有动作中随机选择},& \text{概率 }ϵ\end{array}$$

这条规则的意义很直接：大部分时间相信当前经验，少部分时间给未知动作机会。它不会让智能体完全被早期几次随机结果锁死。

下面是一个最小实现：

import numpy as np


class EpsilonGreedy:
    def __init__(self, n_arms, epsilon=0.1):
        self.n_arms = n_arms
        self.epsilon = epsilon
        self.q = np.zeros(n_arms)
        self.n = np.zeros(n_arms)

    def select(self):
        if np.random.random() < self.epsilon:
            return np.random.randint(self.n_arms)
        return np.argmax(self.q)

    def update(self, arm, reward):
        self.n[arm] += 1
        self.q[arm] += (reward - self.q[arm]) / self.n[arm]

self.q 保存每个动作的平均奖励估计，self.n 记录每个动作被尝试过多少次。更新式：

$${\hat{\mu }}_a\leftarrow {\hat{\mu }}_a+\frac{r-{\hat{\mu }}_a}{N_a}$$

是样本均值的增量写法。它不需要保存全部历史奖励，只要用新奖励修正旧估计。

固定 $ϵ$ 的好处是稳定。无论当前估计多么确定，智能体都会保留探索机会。它的代价也很清楚：即使已经基本知道哪个动作最好，智能体仍然会按固定比例随机选择，长期看会损失一部分奖励。

让探索随时间减少

训练早期，智能体几乎没有经验，需要更多探索。训练后期，估计值已经比较稳定，继续大量随机尝试会降低收益。于是可以让 $ϵ$ 随时间下降：

class EpsilonDecaying:
    def __init__(self, n_arms, epsilon_start=1.0, epsilon_end=0.01, decay=0.995):
        self.n_arms = n_arms
        self.epsilon = epsilon_start
        self.epsilon_end = epsilon_end
        self.decay = decay
        self.q = np.zeros(n_arms)
        self.n = np.zeros(n_arms)

    def select(self):
        if np.random.random() < self.epsilon:
            arm = np.random.randint(self.n_arms)
        else:
            arm = np.argmax(self.q)
        self.epsilon = max(self.epsilon_end, self.epsilon * self.decay)
        return arm

    def update(self, arm, reward):
        self.n[arm] += 1
        self.q[arm] += (reward - self.q[arm]) / self.n[arm]

这个调度表达了一个常见训练节奏：早期多试，后期多信任已有经验。后面学习 DQN 时还会再次见到这个思想。DQN 在训练早期常用较大的 ε 收集多样经验，随后逐步降低 ε，让策略更多使用已经学到的动作价值。

更有针对性的探索

$ϵ$-贪心的探索方式很粗。只要进入探索分支，它会在所有动作中随机选择，包括那些已经明显很差的动作。更好的探索策略会继续追问：哪些动作仍然不确定，因而值得再试？

UCB（Upper Confidence Bound）的做法是给每个动作的估计奖励加上一个不确定性奖金：

$$A_t=\arg \underset{a}{\max }\left[{\hat{\mu }}_a+c\sqrt{\frac{\ln t}{N_a}}\right]$$

这里 ${\hat{\mu }}_a$ 是当前平均奖励估计，$N_a$ 是动作 $a$ 已经被尝试的次数。尝试次数越少，不确定性奖金越大；尝试次数越多，选择就越依赖真实估计值。

Thompson 采样换了一个角度。它为每个动作维护一个“这个动作真实平均奖励可能是多少”的分布，每一轮从各个分布中采样一次，然后选择采样值最高的动作。试得少的动作分布更宽，因此仍然有机会被选中；试得多的动作分布更窄，选择会逐渐稳定。

这些方法的共同目标不是盲目增加随机性，而是把探索机会分给仍有信息价值的动作。

从老虎机走向 MDP

多臂老虎机可以看作强化学习过程的最小版本：

• 动作集合已经存在；
• 奖励会在动作之后出现；
• 策略决定下一步选什么；
• 智能体根据经验更新对动作好坏的估计。

它缺少一个关键部分：状态不会因为动作而改变。CartPole 里向左推一下会改变小车位置和杆子角度，下一步可见的局面也随之变化。语言模型生成一个 token 后，后续上下文会改变，下一步可选动作的意义也会改变。

有了会变化的状态，问题就从“在同一个局面里反复选动作”扩展成“在一串连续变化的局面里做决策”。下一节引入马尔可夫决策过程，把状态、动作、转移、奖励和折扣放进同一套环境定义里。

扩展：多臂老虎机、遗憾与策略比较

前文已经用多臂老虎机说明了探索与利用，并给出了 $ϵ$-贪心、UCB 和 Thompson 采样的基本机制。下面保持同一个问题，进一步加入有限轮数 $T$ 和遗憾，比较不同探索方式为获取信息付出了多少奖励。

以下内容默认折叠，初读可以跳过。

展开阅读：有限轮数与遗憾的定量比较

多臂老虎机问题

前文关心“下一轮怎样选”。进一步比较算法时，还要规定一共可以选择多少轮。例如只允许行动 $T=1000$ 次，早期探索消耗的机会会直接影响最终累计奖励。

问题定义

沿用前面的符号，第 $t$ 轮选择 $A_t$ 并观察奖励 $R_t$。加入轮数上限后，目标写成

$$\max \mathbb{E}\left[\sum _{t=1}^T{R}_t\right].$$

这个目标同时计算学习和使用的结果。为了判断一个动作是否值得继续尝试，智能体必须考虑两部分收益：这次选择可能获得的奖励，以及这次观察对后续 $T-t$ 轮选择提供的信息。

遗憾

由于 ${\mu }_a$ 未知，智能体不可能每轮都选 $a^{\ast }$。我们用遗憾（Regret） 来衡量策略好坏：

$$\text{Regret}(T)=T\cdot {\mu }^{\ast }-\mathbb{E}\left[\sum _{t=1}^T{R}_t\right]=\sum _{t=1}^T\mathbb{E}[{\mu }^{\ast }-{\mu }_{A_t}]$$

其中 ${\mu }^{\ast }={\max }_a{\mu }_a$。遗憾是"如果每轮都选最优，能多拿多少"的期望差。

遗憾界（Regret Bound） 是评估算法的根本指标。一个好策略的遗憾应该随 $T$ 次线性增长（sublinear），即 $\text{Regret}(T)=o(T)$——这意味着随着 $T\to \infty$，智能体越来越接近最优，每轮的平均损失趋于 0。

增长率	含义	评价
$\Theta (T)$	线性	智能体没学到东西，纯随机
$\Theta (\sqrt{T})$	次线性	标准好策略（UCB、Thompson）
$\Theta (\log T)$	对数	理论下界（Lai-Robins 1985）

$ϵ$-贪心与衰减调度

前文已经实现了固定 ε 和衰减 ε。这里用遗憾看两种调度的长期差别。

$ϵ$-贪心算法

假设只有两个摇臂，真实平均奖励分别是 $0.8$ 和 $0.5$，并且智能体已经正确识别了第一个摇臂。若固定 $ϵ=0.1$，每轮有 $10\%$ 的概率随机探索；探索时有一半概率选到第二个摇臂。因此，每轮由随机探索带来的期望损失为

$$0.1\times \frac{1}{2}\times (0.8-0.5)=\mathrm{0.015.}$$

运行 $1000$ 轮后，仅这一部分就会产生约 $15$ 分遗憾。固定 ε 能持续防止早期误判，但即使估计已经稳定，损失仍会继续累积。

衰减调度

衰减调度让探索概率随数据增加而降低。例如从 ${ϵ}_0=1.0$ 开始，每轮乘以 $0.995$，第 $100$ 轮约为 $0.61$，第 $500$ 轮约为 $0.082$，第 $1000$ 轮约为 $0.0067$。如果设置下限 $0.01$，后期会保持 $1\%$ 的随机探索。

这条调度表达了明确的假设：早期估计误差大，探索更有价值；后期估计趋于稳定，行动机会应更多用于获得奖励。衰减太快会重现纯贪心的早期锁定，衰减太慢则会接近固定 ε 的持续损失。

补充：$ϵ$-贪心的理论性质

固定 $ϵ$-贪心会持续保留随机探索，因此即使已经知道哪个动作最好，也仍然会以 ε 的概率选择其他动作。这样做能防止早期误判，但长期看会产生持续损失，所以固定 ε 的累积遗憾通常按线性速度增长。

如果让 ε 随时间下降，例如从较大的初始值逐步衰减到很小，智能体会在早期多探索、后期多利用。合适的衰减策略可以把长期遗憾降到次线性；在一些更严格的设定下，可以得到接近对数级别的遗憾界。

PAC 样本复杂度换了一个问题问法：它不再问前 $T$ 轮一共损失多少，而是问"需要多少次尝试，才能以至少 $1-\delta$ 的概率找到一个距离最优不超过 $ϵ$ 的动作"。这个视角主要用于理论分析，本课程只需要知道它是在衡量"学到足够好策略所需的样本量"。

更有针对性的探索

前文已经看到，UCB 和 Thompson 采样会把探索集中到仍有可能较好的动作。下面用具体数值和后验更新把这个差别展开。

UCB：给不确定性加奖金

UCB（Upper Confidence Bound）的选择公式仍为：

$$A_t=\arg \underset{a}{\max }\left[{\hat{\mu }}_a+c\sqrt{\frac{\ln t}{N_a}}\right]$$

假设当前是第 $100$ 轮，取 $c=1$。摇臂 1 的估计值是 $0.65$，已经尝试 $50$ 次；摇臂 2 的估计值是 $0.55$，只尝试 $5$ 次。两者的 UCB 分数约为

$$0.65+\sqrt{\frac{\ln 100}{50}}\approx 0.95,0.55+\sqrt{\frac{\ln 100}{5}}\approx \mathrm{1.51.}$$

摇臂 2 的当前平均奖励更低，但样本太少，不确定性奖金更大，因此这一轮仍会获得尝试机会。

补充：UCB 的遗憾界

UCB1 的遗憾可以证明达到对数级别。常见形式是：

$$\mathbb{E}[\text{Regret}(T)]\le 8\sum _{a:{\mu }_a<{\mu }^{\ast }}\frac{\ln T}{{\Delta }_a}+\left(1+\frac{{\pi }^2}{3}\right)\sum _{a:{\mu }_a<{\mu }^{\ast }}{\Delta }_a$$

其中 ${\Delta }_a={\mu }^{\ast }-{\mu }_a$ 是次优摇臂与最优摇臂的差距。第一遍学习不需要记住这个式子，只需要理解它表达的机制：UCB 会逐渐减少对明显次优动作的尝试，把探索集中在真正难以区分的动作上。

Thompson 采样：按"成为最优"的可能性选择

Thompson 采样不计算置信上界，而是直接从每个动作当前可能的真实收益中采样。下面看 0/1 奖励下的具体更新。

在 0/1 奖励场景中，可以用 Beta 分布表示每个摇臂的后验：

$${\mu }_a\sim \text{Beta}({\alpha }_a,{\beta }_a)$$

拉到摇臂 $a$ 并得到奖励 1，就令 ${\alpha }_a\leftarrow {\alpha }_a+1$；得到奖励 0，就令 ${\beta }_a\leftarrow {\beta }_a+1$。这个更新规则很轻量，因此 Thompson 采样常用于推荐、广告和 A/B 测试系统。

补充：Thompson 采样的理论视角

Thompson 采样的理论分析常使用贝叶斯遗憾：先假设问题本身来自一个先验分布，再计算策略在这个先验下的期望损失。在常见随机老虎机设定下，它可以达到与 UCB 同阶的对数级别遗憾。

这个细节不是本章主线。主线只需要理解：Thompson 采样把"某个动作可能是最优"转化成选择概率，因此它比 $ϵ$-贪心更少浪费探索机会。

上下文老虎机与 RLHF

普通多臂老虎机假设每个摇臂的奖励分布固定不变。但在真实系统里，动作好不好常常取决于当前输入。

推荐系统里，同一篇文章对不同用户的吸引力不同；广告系统里，同一条广告面对不同人群会有不同点击率；大语言模型里，同一段回答的质量也必须放在具体问题下判断。

这就得到上下文老虎机（Contextual Bandit）：

• 每轮先观察上下文 $x_t$
• 再选择动作 $A_t$
• 收到奖励 $R_t$
• 目标是学习策略 $\pi (a\mid x)$，让动作依赖于当前上下文

从这个角度看，RLHF 可以先被理解成一种上下文老虎机问题：prompt 是上下文，模型生成的回答是动作，奖励模型给出的分数是奖励。这个抽象还没有包含完整的 token 级状态转移，但它已经解释了一个关键事实：模型不能只学习"哪个回答整体更常见"，而要学习"在这个 prompt 下，哪类回答更合适"。

后续进入 MDP 之后，我们会把这个问题继续展开：当一个回答由多个 token 逐步生成时，动作不再是一次性选择，当前 token 会改变后续状态和可选动作。这时，老虎机问题就扩展成真正的序列决策问题。

扩展小结

多臂老虎机（MAB）是 RL 最简化的形式——无状态、即时奖励，但完整保留了"探索-利用"的张力。$ϵ$-贪心用固定概率保留尝试机会，是理解探索的起点；UCB 把尝试机会分配给不确定性更高的动作；Thompson 采样用后验采样把"可能是最优"转化成选择概率。

多臂老虎机没有状态转移，奖励也会立刻出现。下一节马尔可夫决策过程 会先加入状态转移，进入局面不断变化的序列决策；第 2.3 节再加入策略、轨迹和长期回报。

延伸阅读

• Sutton & Barto《Reinforcement Learning: An Introduction》第 2 章
• Auer et al. 2002 "Finite-time Analysis of the Multiarmed Bandit Problem"
• Russo et al. 2018 "A Tutorial on Thompson Sampling"
• Lattimore & Szepesvári《Bandit Algorithms》