🏠 总目录📚 本教程 07 · 探索与利用 ← →

还没试够的动作,怎样和目前最好的动作比较?

读后可检查:从老虎机对照 ε-贪心、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]$$

这条式子比较的是期望收益,不是某一次幸运或倒霉的实得差。 常称期望伪遗憾。举例:最好一台平均奖励 0.6,100 次的基准是 60;若算法期望累计 54,regret 就是 6。

选择方式 可能付出的代价
只选当前均值最高的 早期误判后,可能一直选次优臂
始终均匀随机 存在严格次优臂时,每次都付出固定平均差距,累计是线性量级
逐渐把机会给更有希望的臂 在合适假设下,平均每次的损失可以随时间下降
想看理论量级:为什么不能只背 O(log T)?

固定问题的界与最坏情况的界,不是同一道题。

即使两种方法同为 O(log T),也不说明常数相同、有限轮数表现相同,更不能据此称普通 UCB 已达到所有意义下的最优。

条件与证明见 Bubeck 与 Cesa-Bianchi 的第 2 章。现在只需记住:看到复杂度,先问环境和比较口径。


🎲 二、ε-贪心:最简单的办法

它容易实现,但均匀探索不会自动避开明显较差的选项。若 ε 固定为正,且存在严格次优臂,持续探索会带来线性累计遗憾;这并不意味着非平稳环境中保留探索就没有价值。

改进:ε 衰减

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试过 10 次均值 7.08.11B试过 1 次均值 6.09.52选C试过 4 次均值 5.47.16D试过 6 次均值 6.68.04UCB:选「均值 + 不确定性奖金」最大的,不是选均值最大的四臂示意:t = 22,c = 2 分;灰色是均值,橙色是奖金B 的均值不是最高,但均值加奖金后的总分最高,本次选 B这是乐观评分示意,不证明 B 最好;正文用两家餐厅继续算
灰色是估计均值,橙色是不确定性奖金。看柱顶:B 的总分最高,但这不证明它真实最好。四臂示意已有 21 次观察,下一次 t=22、c=2 分;下文两家餐厅另用 t=12。两例只演示评分,不作为理论保证。

$$a_t = \arg\max_a\Big[\underbrace{\hat\mu_a}_{\text{当前估计}} + \underbrace{c\sqrt{\tfrac{\ln t}{N_a}}}_{\text{不确定性奖金}}\Big]$$

固定 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:从后验里抽一个

它从“我现在认为各臂有多好”的分布中抽样,再选本次样本最大的。

  1. 为每个臂维护中奖率的后验分布。
  2. 从各臂分布独立抽一个可能的中奖率。
  3. 选这次抽样值最大的臂。
  4. 收到它的真实反馈,再更新该臂分布。

伯努利奖励可以配 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 设置中,策略向高奖励回答集中,可能降低多样性;也可能受到数据、解码与训练实现影响。不能只凭“训得久”就定因。

  1. 固定评估提示与解码设置,比较训练前后的任务质量和多样性。
  2. 同时看奖励、参考策略 KL、熵或覆盖指标。
  3. 再分别检查奖励设计、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 进入目标邻域;不是实际湿实验成功率

✅ 检查点

  1. 本章 regret 比较什么?什么时候可谈对数界,为什么不能说“任何算法至少如此”?
  2. 固定 ε 与带下限的衰减各有什么代价?
  3. UCB 的奖金是什么意思?餐厅算例为什么取 t = 12?
  4. Thompson Sampling 怎样更新?3 次成功、1 次失败后是什么分布?
  5. 后验更宽就一定更常被选吗?它自动解决延迟反馈了吗?
  6. 多步探索为什么可能困难?百万分之一的例子用了哪些条件?
  7. 参数噪声什么时候可能带来连贯探索?
  8. 生成参数与探索有何区别?为什么反向 KL 不会对模式集中完全不罚?
👀 答案
  1. 比较已知最优臂的期望累计收益与算法的期望累计收益。固定差距的平稳问题可有对数界;最坏情况与下界另有条件。所有臂相同就是 regret 为 0 的反例。
  2. 有严格次优臂时,固定正 ε 保留线性探索代价;带正下限的衰减最终也一样。无下限不等于从某轮起不再探索,但衰减过快会导致尝试不足。
  3. 奖金给未充分观察的臂一个乐观上界。已有 10+1 次观察,下一次是第 12 轮;示例分数约 8.00 与 9.15,选 B,但不证明 B 更好。
  4. 各臂后验采样、取最大、收到反馈后更新。Beta(1,1) 加 3 次成功和 1 次失败得到 Beta(4,2);该简式适用于二元奖励。
  5. 不一定,要同时看位置和其他臂。独立采样能分散部分选择,仍需处理待反馈、重复分配与容量限制。
  6. 动作决定能到达的状态。百万分之一来自“20 次独立二选一全对、错一次重来”的假设,不是所有长任务的成功率。
  7. 一段轨迹保留同一参数扰动时,动作变化可相关;若频繁重采样则不同。NoisyNet 不保证整局固定一次噪声。
  8. 生成参数改变候选分布,但单独没有反馈和学习更新。参考 (0.5,0.5)、当前 (1,0) 的反向 KL 为 1 比特;某个求和项为 0 不等于总惩罚为 0。

本节回顾

⚡ 走神救援

先记住这几件事

下一节 👉 08-DQN.md ⭐

打卡记录保存在你的浏览器里,首页能看到总进度