EXP3 算法

损失版 EXP3 ​

有 $K$ 个臂，对手预先确定或非预见地生成 ${\ell }_t\in [0,1{]}^K$。算法只观察所选臂 $I_t$ 的损失。固定学习率 $\eta >0$，初始化 $w_{1,i}=1$，每轮执行：

1. 令 $p_{t,i}=w_{t,i}/\sum _j{w}_{t,j}$，按 $p_t$ 抽取 $I_t$；
2. 构造重要性加权估计$${\hat{\ell }}_{t,i}=\frac{{\ell }_{t,i}\mathbf{1}[I_t=i]}{p_{t,i}};$$
3. 更新 $w_{t+1,i}=w_{t,i}\exp (-\eta {\hat{\ell }}_{t,i})$。

指数权重保持每个 $p_{t,i}>0$，所以估计始终有定义。条件于轮前历史 ${\mathcal{F}}_{t-1}$，

$${\mathbb{E}}_t{\hat{\ell }}_{t,i}={\ell }_{t,i}.$$

这是一种不显式混合均匀探索的规范期望界版本；带参数 $\gamma$ 的原始写法、EXP3.P 与 EXP3-IX 使用不同采样或估计，学习率和结论不能交叉拼装。

势函数分析 ​

记 $W_t=\sum _i{w}_{t,i}$。由 $e^{-x}\le 1-x+x^2/2$（$x\ge 0$）和 $\log (1+u)\le u$，

$$\log \frac{W_{t+1}}{W_t}\le -\eta \sum _i{p}_{t,i}{\hat{\ell }}_{t,i}+\frac{{\eta }^2}{2}\sum _i{p}_{t,i}{\hat{\ell }}_{t,i}^2.$$

另一方面，对任意固定臂 $j$，$W_{T+1}\ge w_{T+1,j}$，因此

$$\log \frac{W_{T+1}}{W_1}\ge -\eta \sum _{t=1}^T{\hat{\ell }}_{t,j}-\log K.$$

合并并取条件期望。第一项实际等于已选臂损失，因为 $\sum _i{p}_{t,i}{\hat{\ell }}_{t,i}={\ell }_{t,I_t}$；二阶项虽含 $1/p_{t,i}$，平均后恰有

$${\mathbb{E}}_t\sum _i{p}_{t,i}{\hat{\ell }}_{t,i}^2=\sum _i{\ell }_{t,i}^2\le K.$$

于是对每个固定臂 $j$，

$$\mathbb{E}\sum _t{\ell }_{t,I_t}-\sum _t{\ell }_{t,j}\le \frac{\log K}{\eta }+\frac{\eta KT}{2}.$$

对 oblivious 对手，损失序列固定，因此可在取期望后再对固定臂取最小。取 $\eta =\sqrt{2\log K/(KT)}$，得到标准 expected external regret

$$\mathbb{E}\sum _t{\ell }_{t,I_t}-\underset{j}{min}\sum _t{\ell }_{t,j}\le \sqrt{2KT\log K}.$$

概率空间包含算法抽臂的全部随机性。对 non-anticipating adaptive adversary，${\ell }_t$ 可依过去但不能看见本轮 $I_t$ 后再选择；同一逐轮分析控制的是每个固定臂 $j$ 的 $\mathbb{E}[\sum _t{\ell }_{t,I_t}-\sum _t{\ell }_{t,j}]$，不应未经说明改成“对随机实现序列事后取最好臂”的期望，因为最小值与期望不能随意交换。

具体失败例子：把未观察损失直接记零 ​

设本轮 $K$ 臂均匀抽样，真实损失向量为 $(1,0,\dots ,0)$。若未选择坐标一律填零，第一坐标的“估计损失”只在以 $1/K$ 概率选中它时为 $1$，故条件期望是 $1/K$ 而不是真实损失 $1$；送入 Hedge 后，更新尺度会随当前抽样概率改变。重要性加权在选中第一臂时把观测放大为 $K$，使条件期望恢复为 $1$。代价是二阶矩按 $1/p_{t,i}$ 放大，EXP3 的 $\sqrt{K}$ 因子正来自这份部分反馈的信息价格。

一个广告位的点击收益可能按新闻周期恶意变化，根本不存在固定均值 gap。EXP3 仍与事后最好固定广告比较，而 UCB 的置信均值论证没有适用对象。若环境真是平稳随机臂，EXP3 的最坏情形保证通常不如利用 gap 的 UCB 精细。

失败边界 ​

上述是期望遗憾，不是高概率界。无偏估计可能重尾，直接对同一分析套 Hoeffding 不成立；EXP3.P 通过显式探索和偏置项获得高概率控制，EXP3-IX 则修改分母。若对手见到本轮随机选择后才设损失，它可总让所选臂损失为 $1$、其他臂为 $0$，标准外部遗憾问题便退化。

参考资料

• Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert Schapire, “The Nonstochastic Multiarmed Bandit Problem,” 2002.
• Sébastien Bubeck and Nicolò Cesa-Bianchi, 2012 survey.