Explore-then-Commit | Codeboy's Blog

形式陈述

Explore-then-Commit 是随机赌博机遗憾的两阶段基线；其错误 commit 分析使用Hoeffding 集中控制固定预算经验均值。

考虑 $K$ 臂随机赌博机，臂 $i$ 的奖励独立同分布、取值于 $[0,1]$ ，均值为 $\mu_i$ 。总轮数为 $T$ 。Explore-then-Commit 预先选择每臂探索次数 $n$ ，并执行两阶段策略：

依次拉取每个臂恰好 $n$ 次，计算经验均值 $\widehat\mu_i$ ；
取 $\widehat i\in\arg\max_i\widehat\mu_i$ ，在剩余 $T-Kn$ 轮始终拉取 $\widehat i$ 。

算法要求 $Kn\le T$ 。并列时采用任意预先固定规则。探索阶段不根据观测改变预算，commit 后也不再修正错误判断；正是这种克制使分析透明，也暴露固定探索的局限。

两臂分析

先设两臂且 $\mu_1>\mu_2$ ，gap 为

\Delta=\mu_1-\mu_2>0.

探索阶段固定拉取次优臂 $n$ 次，产生 $n\Delta$ 期望遗憾。commit 选错当且仅当 $\widehat\mu_2\ge\widehat\mu_1$ 。由两个经验均值的 Hoeffding 界，

\Pr(\widehat\mu_2\ge\widehat\mu_1) \le \exp(-c n\Delta^2)

，其中 $c>0$ 是由奖励范围决定的常数。因此

\mathbb E R_T \le n\Delta+(T-2n)\Delta e^{-c n\Delta^2}.

在 $T\Delta^2$ 大于适当常数、且所得预算满足 $2n\le T$ 的 gap-dependent 区间，选择 $n\asymp \Delta^{-2}\log(T\Delta^2)$ 可把错误 commit 的尾部压低，得到约

\mathbb E R_T=O\!\left(\frac{\log(T\Delta^2)}{\Delta}\right).

第一项是确定的探索成本，第二项是罕见但会持续到终局的误识别成本；两者必须同时保留。

当 $T\Delta^2=O(1)$ 时， $\log(T\Delta^2)$ 可能非正，上述调参式不再适用；此时即使始终选错，实例相关遗憾也至多 $T\Delta=O(\sqrt T)$ 。因此不能把 gap-dependent 对数公式越过其参数区间机械外推。

多臂版本

设最佳均值为 $\mu_*$ ，次优臂 gap 为 $\Delta_i=\mu_*-\mu_i$ 。均匀探索产生

n\sum_{i:\Delta_i>0}\Delta_i

的期望遗憾。选错的概率可对各次优臂事件

\widehat\mu_i\ge\widehat\mu_*

取并集界，得到含 $\sum_i e^{-c n\Delta_i^2}$ 的 commit 成本。最小 gap $\Delta_{\min}$ 往往支配安全预算，即使其他臂很容易排除，均匀 ETC 仍给每个臂同样多的样本。

直觉

时间轴先轮换探索各臂，再越过预算分界持续选择经验最佳臂 — Explore-then-Commit 的两阶段时间轴

固定探索把遗憾拆成容易核算的两笔账：探索阶段确定支付次优臂 gap，利用阶段则承担一次误判延续到终局的尾部成本。预算太小放大误判，预算太大浪费容易实例，最优点依赖未知 gap。

例子与边界

一个可计算例子

两种页面布局的真实点击率分别为 $0.52$ 与 $0.50$ ，gap 只有 $0.02$ 。若每种只探索一百次，经验均值的典型波动远大于 $0.02$ ，commit 很容易押错；之后即使累计数万次展示，算法也拒绝查看反证。把探索预算提升到 $\Delta^{-2}$ 量级需要数千次每臂观测，显示小 gap 为何昂贵。

若真实 gap 为 $0.2$ ，同样预算又显得浪费：差异早已清楚，固定阶段仍继续探索。UCB 等自适应策略恰好利用置信区间逐臂停止无谓探索。

不知道 gap 时的困境

最优 $n$ 依赖未知 $\Delta$ 。取很小的 $n$ 会让难实例频繁误 commit；取很大的 $n$ 又在容易实例上支付多余遗憾。可选择一个 minimax 折中预算，或使用 doubling、successive elimination 等自适应设计，但这些已经改变算法。

ETC 因而更适合作为基线、批次受限实验或运营上必须在某个日期冻结决策的流程。它不是 UCB 的劣质写法：两阶段约束可能来自真实业务制度，但若没有此约束，自适应探索通常更有效。

与最佳臂识别的边界

commit 动作看似在识别最佳臂，但本页目标是固定时域内的累计遗憾。固定置信最佳臂识别允许随机停止，并以错误概率 $\delta$ 为首要约束；探索期间的累计奖励通常不计入目标。把 ETC 的 $n$ 直接称为“识别样本复杂度”，会遗漏这两个目标的差别。

分析还依赖奖励独立、固定均值和有界/次高斯尾部。对抗 bandit 中不存在要估计的固定 $\mu_i$ ，两阶段经验均值不能支持同样的指数误选界。

推论与应用

当运营制度要求在固定日期冻结版本时，ETC 的两阶段约束本身有现实意义；若允许持续适应，UCB 或 successive elimination 会根据各臂不确定性提前停止无谓探索。批次受限 bandit 则位于两者之间。

不知道 gap 时可选择 minimax 预算或 doubling，但这会改变实例依赖常数和切换次数。任何调参都应同时报告探索成本与误 commit 成本，不能只展示最终选臂准确率。

参考资料

Tor Lattimore and Csaba Szepesvári, Bandit Algorithms, Cambridge University Press, 2020.
Sébastien Bubeck and Nicolò Cesa-Bianchi, “Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems,” Foundations and Trends in Machine Learning 5(1), 2012, pp. 1–122.
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer, “Finite-time Analysis of the Multiarmed Bandit Problem,” Machine Learning 47, 2002, pp. 235–256.

形式陈述 ​

两臂分析 ​

多臂版本 ​

一个可计算例子 ​

不知道 gap 时的困境 ​