Explore-then-Commit

算法 ​

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

1. 依次拉取每个臂恰好 $n$ 次，计算经验均值 ${\hat{\mu }}_i$；
2. 取 $\hat{i}\in \arg \underset{i}{max}{\hat{\mu }}_i$，在剩余 $T-Kn$ 轮始终拉取 $\hat{i}$。

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

两臂分析 ​

先设两臂且 ${\mu }_1>{\mu }_2$，gap 为

$$\mathrm{\Delta }={\mu }_1-{\mu }_2>0.$$

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

$$\text{Pr}({\hat{\mu }}_2\ge {\hat{\mu }}_1)\le \exp (-cn{\mathrm{\Delta }}^2)$$

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

$$\mathbb{E}{R}_T\le n\mathrm{\Delta }+(T-2n)\mathrm{\Delta }{e}^{-cn{\mathrm{\Delta }}^2}.$$

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

$$\mathbb{E}{R}_T=O\left(\frac{\log \left(T{\mathrm{\Delta }}^2\right)}{\mathrm{\Delta }}\right).$$

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

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

多臂版本 ​

设最佳均值为 ${\mu }_{\ast }$，次优臂 gap 为 ${\mathrm{\Delta }}_i={\mu }_{\ast }-{\mu }_i$。均匀探索产生

$$n\sum _{i:{\mathrm{\Delta }}_i>0}{\mathrm{\Delta }}_i$$

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

$${\hat{\mu }}_i\ge {\hat{\mu }}_{\ast }$$

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

一个可计算例子 ​

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

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

不知道 gap 时的困境 ​

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

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

与最佳臂识别的边界 ​

commit 动作看似在识别最佳臂，但本页目标是固定时域内的累计遗憾。固定置信最佳臂识别公理库最佳臂识别best-arm identification · pure exploration以可靠选出最高均值臂为目标，研究纯探索的停止规则与样本复杂度。允许随机停止，并以错误概率 $\delta$ 为首要约束；探索期间的累计奖励通常不计入目标。把 ETC 的 $n$ 直接称为“识别样本复杂度”，会遗漏这两个目标的差别。

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

参考资料

• Tor Lattimore and Csaba Szepesvári, Bandit Algorithms, explore-then-commit examples.
• Sébastien Bubeck and Nicolò Cesa-Bianchi, “Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems,” 2012.
• Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer, “Finite-time Analysis of the Multiarmed Bandit Problem,” 2002.