Explore-then-Commit

形式陈述 ​

Explore-then-Commit 是随机赌博机遗憾理路随机赌博机与伪遗憾Stochastic bandit · Pseudo-regret每个臂从固定分布独立取样时，以均值差和选择次数表达期望损失。的两阶段基线；其错误 commit 分析使用Hoeffding 集中理路Hoeffding 不等式Hoeffding's inequality独立有界随机变量和偏离期望的概率以平方偏差的指数速度衰减。控制固定预算经验均值。

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

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

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

流式实现只需保存 $K$ 个计数与奖励和，占 $O(K)$ 存储；探索的 $Kn$ 次观测各作常数次统计更新，随后用一次 $O(K)$ 扫描求经验均值的最大者。commit 阶段每轮直接选定同一臂，因此整个时域的基本运算为 $O(T+K)=O(T)$，其中已用 $T\ge K$；奖励取得、计数位宽及实数累加精度的成本另计。

两臂分析 ​

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

探索阶段固定拉取次优臂 $n$ 次，产生 $n\mathrm{\Delta }$ 伪遗憾。commit 选错必有 ${\hat{\mu }}_2\ge {\hat{\mu }}_1$；相等时是否选错取决于固定的平票规则。该事件要求至少一个经验均值朝错误方向偏离 $\mathrm{\Delta }/2$，所以两个单侧 Hoeffding 界与并集界理路并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。给出

因此，累计伪遗憾满足

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

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

当 $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$。均匀探索产生

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

使用相同的两个单侧界。于是 commit 的伪遗憾至多为 $2(T-Kn)\sum _{i:{\mathrm{\Delta }}_i>0}{\mathrm{\Delta }}_i{e}^{-n{\mathrm{\Delta }}_i^2/2}$。最小 gap ${\mathrm{\Delta }}_{min}$ 往往支配安全预算，即使其他臂很容易排除，均匀 ETC 仍给每个臂同样多的样本。