UCB 与 ε-贪心：两种经典探索策略的定义与本质差异

htzhao

背景

在多臂老虎机（Multi-Armed Bandit）问题里，决策者面对一组可选动作（“拉哪台老虎机”或“选哪个策略/模型”），每次选择会得到随机回报。目标是在长期累积回报最大化。这个问题的核心矛盾只有一句话：**探索（exploration）与利用（exploitation）**如何平衡——既要尝试不熟悉的选项以获得信息，又要尽量选择当前看起来最好的选项以获得收益。

在所有探索策略中，ε-贪心（epsilon-greedy）和UCB（Upper Confidence Bound，上置信界）最具代表性：前者简单直接，后者体现了“用统计置信度驱动探索”的思想。两者表面都能“探索+利用”，但它们的定义与本质机制差异非常明显。

1. 问题设定：老虎机、均值与后悔值

设有 ​(K) 个臂（动作）​(a\in{1,\dots,K})。每次选择臂 (a) 会得到回报 ​(X_t(a))，其期望为 ​(\mu(a)=\mathbb E[X_t(a)])。最佳臂为 ​(a^*=\arg\max_a \mu(a))。

常用的学习信号是每个臂的经验均值：

[ \hat\mu_t(a)=\frac{1}{N_t(a)}\sum_{s\le t:,A_s=a} X_s(a), ]

其中 (N_t(a)) 是到时刻 (t) 为止臂 (a) 被选择的次数。

评估算法优劣常用“累计后悔值（regret）”：

[ R_T = T\mu(a^*) - \sum_{t=1}^T \mu(A_t), ]

它刻画“因为探索与误判而少赚了多少”。

2. ε-贪心：用固定比例的随机性换信息

2.1 定义（最常见版本）

ε-贪心的决策规则极为简单：

  • 以概率 ​(1-\epsilon) 选择当前经验均值最高的臂（利用）​[A_t = \arg\max_a \hat\mu_{t-1}(a)]
  • 以概率 ​(\epsilon) 在所有臂中均匀随机选一个（探索）

可以写成：

[ \mathbb P(A_t=a)= \begin{cases} 1-\epsilon + \epsilon/K,& a=\arg\max \hat\mu_{t-1}(a) \epsilon/K,& \text{otherwise} \end{cases} ]

2.2 直觉与性格

ε-贪心的探索是**“无差别的”**：探索阶段会把预算平均撒到所有臂上，不管某个臂是否已经被大量采样、估计是否稳定。它的优势是实现容易、计算几乎为零；缺点是探索“有点粗”。

2.3 常见改造：衰减 ε

实践中常让 ​(\epsilon) 随时间衰减（例如 ​(\epsilon_t = c/t) 或 ​(\epsilon_t=c/\sqrt{t})），以便后期更多利用。但要注意：这仍是全局衰减，并不区分“哪个臂更不确定”。

3. UCB：用置信区间驱动“定向探索”

ε-贪心在探索时“随便试”。UCB 的核心思想则是：对每个臂估计一个上界：均值 + 不确定度，选择“上界最大”的臂。它等价于一种策略哲学：对不确定的选项保持乐观（optimism in the face of uncertainty）。

3.1 定义（UCB1 代表性形式）

经典 UCB1 给每个臂定义一个分数：

[ \text{UCB}_t(a)=\hat\mu_{t-1}(a)+\sqrt{\frac{2\ln t}{N_{t-1}(a)}}. ] 然后选择： [ A_t = \arg\max_a \text{UCB}_t(a). ]

其中第二项是“置信半径”：

  • 当 (N(a)) 很小，半径很大 → 该臂“可能很强”，值得多试
  • 当 (N(a)) 很大，半径收缩 → 该臂已经“看清了”，不再因不确定性获得额外加成

3.2 置信半径从哪里来：Hoeffding 不等式的影子

当回报有界（例如 (X\in[0,1])）且独立时，Hoeffding 不等式给出：

[ \mathbb P\big(\mu(a) \ge \hat\mu(a)+u\big)\le \exp(-2N(a)u^2). ]

若把右侧控制为一个小概率 (p)，就得到：

[ u=\sqrt{\frac{\ln(1/p)}{2N(a)}}. ]

把 (p) 设计成随时间衰减（例如 ​(p\propto 1/t^4)），就能导出类似 ​(\sqrt{\ln t / N(a)}) 的结构。这一项正是 UCB “不确定度奖励”的来源：样本越多，估计越准，不确定度越小。

4. 本质区别：随机探索 vs 统计驱动的定向探索

两者最关键的分水岭不在“有没有探索”，而在探索如何分配。

4.1 探索预算的分配方式不同

  • **ε-贪心：**探索阶段“均匀随机”，对所有臂一视同仁

    • 即使某臂已经采样很多次，仍会在探索时被抽到

  • **UCB：**探索是“按臂自适应”，优先照顾样本少、置信区间宽的臂

    • 同样是试错，但试错更“有方向”

一句话总结：
ε-贪心把探索当作噪声；UCB 把探索当作统计推断的一部分。

4.2 对“采样次数 (N(a))”的使用方式不同

  • ε-贪心：​N(a) 仅通过 ​\hat\mu(a) 间接影响决策（样本多则均值更稳定，但算法不会显式知道“不确定度变小了”）
  • UCB：​N(a) 直接进入决策规则的加成项 ​U(a)，明确刻画“估计置信度”

这也是很多人直觉上的答案：UCB 相比 ε-贪心，确实更系统地把“采样次数影响估计准确性”纳入决策机制——但更准确的表述是：UCB 不仅考虑了 ​N(a)，还把它转化成了“可比较的置信上界”。

4.3 失败方式不同：谁更容易“乱试”或“卡死”

  • ε-贪心：

    • (\epsilon) 太大 → 长期乱试，后悔值增大
    • (\epsilon) 太小/衰减太快 → 早期误判后可能长期利用错误臂（“卡死”）

  • UCB：

    • 过度乐观项过大（例如把系数设得过高）→ 前期可能探索偏多
    • 但一般不会“永远卡死”，因为不确定度会推动被忽略臂重新被采样

4.4 理论侧：典型后悔值量级（直观层面）

在经典有界随机回报的设定里，UCB1 能给出相当漂亮的理论保证：次优臂被选择的次数是对数级别，累计后悔值常见量级为 (O(\log T))（省略常数与细节条件）。
ε-贪心若用常数 (\epsilon) 则会持续浪费探索预算，后悔值通常不如 UCB；若设计得当的衰减 (\epsilon_t)，也能达到不错的效果，但需要更仔细的调参。

5. 具体例子：三台老虎机会发生什么

设三臂真实均值分别是：

  • A：0.60（最优）
  • B：0.58（几乎一样好）
  • C：0.30（明显差）

ε-贪心的行为

探索时仍会抽到 C，哪怕早已确认它很差；如果 (\epsilon=0.1)，那么约 10% 的轮次都在“随机试”，其中 (1/3) 会浪费在 C 上，造成稳定损失。

UCB 的行为

早期会较快摸清 C 的下限；一旦 (N(C)) 增大、置信半径收缩，C 的上界会迅速落后于 A/B，从而很少再被选中。探索预算更多会分配在 A 与 B 的精细辨别上——这正是“定向探索”的价值。

6. 实践建议：什么时候用哪一个？

6.1 选择 ε-贪心的场景

  • 需要非常轻量的实现与计算（嵌入式、超大规模在线服务的极简版本）
  • 环境非平稳（均值会变）：可以用固定 (\epsilon) 维持持续探索
  • 作为 baseline 或快速原型验证

6.2 选择 UCB 的场景

  • 回报基本平稳、可近似独立且有界（或可归一化到有界）
  • 希望更少“无意义探索”，更快聚焦不确定但有潜力的选项
  • 需要较强的可解释性：每次选择来自“均值+不确定度”的透明打分

6.3 常见工程细节

  • UCB 要处理 (N(a)=0) 的初始化：通常每个臂先拉一次，或把未拉臂的 UCB 设为 (+\infty)
  • UCB 的对数项常用 (\ln t)，也可用 (\ln(T)) 或更保守的形式；系数可作为探索强度超参 (c)
  • 若回报噪声近似高斯/方差未知，可能会用 UCB-V、KL-UCB 等更细致版本

7. 结语：两种“探索观”的分野

ε-贪心代表一种朴素但有效的思路：用固定比例的随机性购买信息。
UCB 代表另一种更“统计学”的思路：把不确定性量化为置信区间，并让探索精准投向最不确定、最可能有价值的地方。

因此，UCB 相比 ε-贪心并非只是“考虑了采样次数 (n)”这么简单，而是将“样本量 → 估计误差 → 置信上界 → 决策”串成了一条闭环：探索不再是无差别的随机扰动，而成为一种由统计保证驱动的理性选择。

Comments