还没试够的动作,怎样和目前最好的动作比较?
读后可检查:从老虎机对照 ε-贪心、UCB 与后验采样,再检查有状态探索的额外困难。
📑 本页目录(点开跳转)
07 · 探索与利用
⏱ 28 分钟 | ⭐ 推荐系统那一章的理论底座
🎯 一句话
只用熟悉的选项,可能错过更好的;一直试新选项,又会损失眼前收益。
本章比较三种分配尝试机会的方法:ε-贪心、UCB、Thompson Sampling。先看它们怎样选,再看各自结论需要什么前提;没有一个方法在所有环境中都最优。
🎰 一、把问题剥到最简:多臂老虎机
先暂时拿掉“这一步会影响下一步状态”的困难。
有 K 个可选动作(称为“臂”),每次选一个,只看到它的奖励。你有 T 次机会,希望累计收益尽量高。
本章先讨论平稳随机老虎机:每个臂的奖励来自固定分布,各次抽取独立;中奖记 1,未中奖记 0。它可以视为没有动作依赖状态演变的特例,不是任意 MDP 删去状态名称后都满足这些假设。
衡量指标:遗憾(Regret)
$$\text{Regret}(T) = T\cdot\mu^* - \sum_{t=1}^{T}\mathbb{E}[r_t]$$
- T:总共尝试多少次。
- μ*:最优臂的真实平均奖励,不是某次抽奖的最高值。
- E[rₜ]:算法在第 t 次获得奖励的期望,包括环境与算法随机性。
这条式子比较的是期望收益,不是某一次幸运或倒霉的实得差。 常称期望伪遗憾。举例:最好一台平均奖励 0.6,100 次的基准是 60;若算法期望累计 54,regret 就是 6。
| 选择方式 | 可能付出的代价 |
|---|---|
| 只选当前均值最高的 | 早期误判后,可能一直选次优臂 |
| 始终均匀随机 | 存在严格次优臂时,每次都付出固定平均差距,累计是线性量级 |
| 逐渐把机会给更有希望的臂 | 在合适假设下,平均每次的损失可以随时间下降 |
想看理论量级:为什么不能只背 O(log T)?
固定问题的界与最坏情况的界,不是同一道题。
- 平稳、有界奖励,且次优臂与最优臂有固定正差距时,标准 UCB 可得到与 log T 同阶的上界;常数仍依赖臂间差距。
- 经典对数下界对奖励族和“在所有问题上都表现一致良好”的算法有条件;不是“任何算法在每个实例都至少如此”。所有臂一样好时,这里的 regret 就是 0。
- 若考察 K ≥ 2、T ≥ K 的有界随机老虎机最坏情况,最小最大量级是 √(KT)。不能把固定差距的 log T 结论直接搬来。
即使两种方法同为 O(log T),也不说明常数相同、有限轮数表现相同,更不能据此称普通 UCB 已达到所有意义下的最优。
条件与证明见 Bubeck 与 Cesa-Bianchi 的第 2 章。现在只需记住:看到复杂度,先问环境和比较口径。
🎲 二、ε-贪心:最简单的办法
- 以 ε 的概率探索: 均匀随机选一个臂,可能仍抽到当前最优估计。
- 以 1−ε 的概率利用: 选当前平均奖励最高的臂。
它容易实现,但均匀探索不会自动避开明显较差的选项。若 ε 固定为正,且存在严格次优臂,持续探索会带来线性累计遗憾;这并不意味着非平稳环境中保留探索就没有价值。
改进:ε 衰减
eps_start, eps_min, decay = 1.0, 0.05, 0.995
for episode in (0, 100, 500, 1000, 2000):
eps = max(eps_min, eps_start * (decay ** episode)) # 或 eps = 1/t
print(f"第 {episode:>4} 轮:ε = {eps:.3f}")
实跑结果:1.000 → 0.606 → 0.082 → 0.050 → 0.050。
这里是平滑的指数衰减,不是第 500 轮发生断崖。 大约第 598 轮后,计算值低于 0.05,开始由下限托住。
这个下限保留了持续探索,也保留了平稳问题中的长期代价。不设下限时,ε 趋近 0 不等于从某一轮起严格不再探索;指数衰减过快仍可能使总探索不足。
代码注释中的 1/t 也是一种形状,不是通用最优参数。衰减速度要与臂间差距、环境变化和有限预算一起检查。DQN 中的使用还涉及状态与函数近似,见第 6 章。
📈 三、UCB:给不确定性一个奖金
UCB 选的是“乐观上界最高”的臂,不是直接计算“谁最可能最好”的概率。
$$a_t = \arg\max_a\Big[\underbrace{\hat\mu_a}_{\text{当前估计}} + \underbrace{c\sqrt{\tfrac{\ln t}{N_a}}}_{\text{不确定性奖金}}\Big]$$
- 当前估计 μ̂ₐ:已观察到的平均奖励。
- Nₐ:决策前已经观察到的该臂次数;未尝试的臂先各试一次,避免除以 0。
- t:当前决策轮次;c 控制奖金尺度。
固定 t 时,试得少的臂奖金通常更大。如果某个臂一直没被再试,ln t 增长也会提高它的奖金,让算法重新检查它。
回到第 1 章那个餐厅例子。 A 试过 10 次、平均 7 分,B 试过 1 次、得 6 分。已经有 11 次观察,下一次是 t = 12。
下面沿用原来的 c = 2 分,仅作启发式评分算例,不套用 [0,1] 奖励下的 UCB1 保证:
| 店 | 均值 | 不确定性奖金 | 相加后的分数 |
|---|---|---|---|
| A | 7 | 2 × √(ln 12 / 10) ≈ 1.00 | 约 8.00 |
| B | 6 | 2 × √(ln 12 / 1) ≈ 3.15 | 约 9.15 |
这一次选 B:它的乐观上界更高,不是已经证明 B 更好。
标准 [0,1] 有界奖励的 UCB1 使用 c = √2。若餐厅评分为 0–10 分,可先除以 10,或按奖励范围相应缩放奖金;不能只缩放均值而沿用原尺度的 c。
给定相同历史、参数与固定的平局规则,标准 UCB 的选择可为确定性。但环境仍随机,完整实验的可复现性还要保存数据与设置。
🎯 四、Thompson Sampling:从后验里抽一个
它从“我现在认为各臂有多好”的分布中抽样,再选本次样本最大的。
- 为每个臂维护中奖率的后验分布。
- 从各臂分布独立抽一个可能的中奖率。
- 选这次抽样值最大的臂。
- 收到它的真实反馈,再更新该臂分布。
伯努利奖励可以配 Beta 先验。 Beta(1,1) 是在 0–1 上均匀的一个选择,不是完全没有假设。
| 收到的反馈 | 后验更新 |
|---|---|
| 中奖,reward = 1 | α 加 1,β 不变 |
| 未中,reward = 0 | β 加 1,α 不变 |
这叫共轭:更新后仍属于 Beta 分布族。下列代码实现这个二元奖励版本,不能直接把任意评分或收入塞进来当作伯努利反馈。
import numpy as np
class ThompsonSampling:
def __init__(self, k):
self.alpha = np.ones(k) # 赢的次数 + 1
self.beta_ = np.ones(k) # 输的次数 + 1
def select(self):
# ⭐ 核心就这一行:从每个臂的后验里抽样,选最大的
return int(np.argmax(np.random.beta(self.alpha, self.beta_)))
def update(self, a, reward):
self.alpha[a] += reward
self.beta_[a] += 1 - reward
可检查的结果: 从 Beta(1,1) 出发,观察到 3 次成功、1 次失败,该臂后验应为 Beta(4,2),均值为 4/6,而不是样本成功率 3/4。
“分布更宽”并不自动等于更容易胜出。还要看它的位置以及其他臂的后验:一个均值很低但很宽的臂,未必常被选中。
在这个后验模型下,一个臂被选中的概率对应它后验上为最优臂的概率。探索和利用因此由同一次采样产生,而不是分别抛一次“探索开关”。
UCB vs Thompson Sampling
| 比较项 | UCB | Thompson Sampling |
|---|---|---|
| 决策依据 | 估计值加置信奖金 | 从后验抽样后比较 |
| 随机性 | 标准版可确定性选择 | 每次抽样带来随机性 |
| 需要核对 | 奖励范围、置信界与初始化 | 先验、似然与奖励类型 |
| 理论范围 | 固定差距的平稳有界问题可得对数界 | 例如 Beta-Bernoulli 平稳问题有对数界 |
| 延迟反馈 | 可使用批量、待反馈修正等变体 | 独立重采样可分散分配,但不消除反馈延迟 |
Thompson Sampling 的理论结果须连同模型假设阅读,见Agrawal 与 Goyal 的 regret 分析。
同一批一万次请求怎么理解? 如果候选、上下文、历史都相同,且尚未收到反馈,朴素确定性 UCB 可能重复同一选择。独立重采样的 Thompson Sampling 可产生不同选择,但也可能重复,后验很集中时尤其如此。
所以两者都要处理待反馈请求、容量与风险限制;不能得出“UCB 无法并行”或“Thompson 天然解决延迟”的结论。实际还要比较收益、探索成本和延迟,见推荐算法第 13 章。
🧊 五、有状态时的探索:难得多
在 MDP 中,当前动作还影响将来能看到什么。 困难不只是多试几个选项,而是能否连续走到有信息的状态。
假设到达一个新状态必须连续做对 20 次二选一,任何一次错误都要重来。若每步独立均匀随机,一次完整尝试成功的概率只有 2⁻²⁰,约百万分之一。这个概率来自这个人为设定,不是所有 20 步任务的规律。
Montezuma's Revenge 是稀疏奖励探索的经典例子:拿钥匙、开门等动作需要配合。不同算法、训练预算与游戏设置分数不同,不能把“训练几亿帧都是 0”写成普遍事实。
三类思路仍值得认识:
| 思路 | 做法 | 代表 |
|---|---|---|
| 内在奖励 | 用预测误差等信号鼓励访问尚不熟悉的状态 | RND、ICM |
| 计数式探索 | 给访问少的状态额外奖金;高维状态可能要近似计数 | Pseudo-count |
| 参数空间噪声 | 扰动网络参数,改变整套动作偏好 | NoisyNet |
内在奖励不是总能找到有用的新知识:不可预测的噪声也可能持续产生高误差。计数与参数扰动同样需要与任务验证配合。
参数噪声的“连贯性”取决于多久重采样。 若一段轨迹沿用同一扰动,就能产生相关的动作变化;不能说 NoisyNet 必然整局只采一次。NoisyNet 原论文按优化步骤重新采样,而不是固定的整局规则。
🤖 六、这一章在 RLHF 里的样子
生成的随机性可以增加候选覆盖,但不等于已经完成了强化学习中的探索。还需要反馈、目标与更新机制。
| 生成设置 | 它改变什么 | 不能直接等同什么 |
|---|---|---|
| temperature | 调整 logits 的相对尺度,影响采样分布 | 温度越高,学习就一定越有效 |
| top-k | 保留概率最高的固定数量候选 | 固定比例的随机探索 |
| top-p | 按累积概率保留候选集合 | ε-贪心或“自适应的 ε” |
| greedy | 每步取最高分候选 | 找到整段回答的全局最优,或最高真实奖励 |
有些接口把 temperature=0 作为贪心模式的约定;它不是直接把温度公式的分母设为 0。参数具体语义及组合顺序需核对实现,见解码策略。
回答变雷同,先检查发生了什么
在一些 RLHF 设置中,策略向高奖励回答集中,可能降低多样性;也可能受到数据、解码与训练实现影响。不能只凭“训得久”就定因。
- 固定评估提示与解码设置,比较训练前后的任务质量和多样性。
- 同时看奖励、参考策略 KL、熵或覆盖指标。
- 再分别检查奖励设计、KL 强度、采样与训练长度;保留对照,不直接认定某个调参方案一定有效。
KL 不是“遗漏一个模式免费”
一些目标使用 $D_{KL}(\pi_\theta\|\pi_{SFT})$,按当前策略加权。某个位置的当前概率为 0 时,该求和项为 0;但概率归一化会影响其他位置。
例如参考策略为 (0.5,0.5),当前策略为 (1,0),以 2 为底计算的 KL 是 1 比特,不是 0。
奖励项可能推动集中,KL 项对偏离收取代价;最终取决于它们的权衡。不能断言 KL 完全阻止塌缩,也不能说它对塌缩没有惩罚。
数值推导见数学原理 01b。参考策略的概率很低,也不严格等于“奖励模型从没见过这种输出”。
🔗 七、和站内其他章的关系
| 相关的地方 | 这里的位置 |
|---|---|
| 第 1 章的餐厅例子 | 用它理解探索策略,不把评分算例当成理论保证 |
| 推荐算法 13 Thompson Sampling | 本章是它的理论解释 ⭐ |
| 第 6 章 ε-贪心 | 说明固定探索与衰减探索各自的代价 |
| 全景导论 06b · 解码策略 | 生成参数影响候选覆盖,但不等同完整探索算法;去那里核对三个旋钮的作用与实现顺序 |
| 数学原理 01b · KL 散度 | 核对方向、归一化与正则代价;择峰是受限近似中的倾向,不是零惩罚定律 |
| A/B 测试 | 自适应分流着重累计收益;若要估计因果效果,还须匹配实验与统计推断方法 |
| 科学问题怎么变成模型 08 · 飞轮 | 用合成函数比较采样策略:8 个种子、每次 25 轮,贪心 2/8、UCB 8/8 进入目标邻域;不是实际湿实验成功率 |
✅ 检查点
- 本章 regret 比较什么?什么时候可谈对数界,为什么不能说“任何算法至少如此”?
- 固定 ε 与带下限的衰减各有什么代价?
- UCB 的奖金是什么意思?餐厅算例为什么取 t = 12?
- Thompson Sampling 怎样更新?3 次成功、1 次失败后是什么分布?
- 后验更宽就一定更常被选吗?它自动解决延迟反馈了吗?
- 多步探索为什么可能困难?百万分之一的例子用了哪些条件?
- 参数噪声什么时候可能带来连贯探索?
- 生成参数与探索有何区别?为什么反向 KL 不会对模式集中完全不罚?
👀 答案
- 比较已知最优臂的期望累计收益与算法的期望累计收益。固定差距的平稳问题可有对数界;最坏情况与下界另有条件。所有臂相同就是 regret 为 0 的反例。
- 有严格次优臂时,固定正 ε 保留线性探索代价;带正下限的衰减最终也一样。无下限不等于从某轮起不再探索,但衰减过快会导致尝试不足。
- 奖金给未充分观察的臂一个乐观上界。已有 10+1 次观察,下一次是第 12 轮;示例分数约 8.00 与 9.15,选 B,但不证明 B 更好。
- 各臂后验采样、取最大、收到反馈后更新。Beta(1,1) 加 3 次成功和 1 次失败得到 Beta(4,2);该简式适用于二元奖励。
- 不一定,要同时看位置和其他臂。独立采样能分散部分选择,仍需处理待反馈、重复分配与容量限制。
- 动作决定能到达的状态。百万分之一来自“20 次独立二选一全对、错一次重来”的假设,不是所有长任务的成功率。
- 一段轨迹保留同一参数扰动时,动作变化可相关;若频繁重采样则不同。NoisyNet 不保证整局固定一次噪声。
- 生成参数改变候选分布,但单独没有反馈和学习更新。参考 (0.5,0.5)、当前 (1,0) 的反向 KL 为 1 比特;某个求和项为 0 不等于总惩罚为 0。
本节回顾
⚡ 走神救援
先记住这几件事
- 探索要获取信息,利用要兑现已有知识,两者共同影响长期回报。
- UCB 使用不确定性奖金,Thompson Sampling 从后验中采样进行选择。
- 反馈延迟、环境变化和多步探索会改变方法的表现,先核对问题设定。
下一节 👉 08-DQN.md ⭐