EXP3 算法

部分反馈的核心障碍是：算法既要把一个被抽中的坐标恢复成整行损失的无偏估计，又要承担由 $1/p_{t,i}$ 放大产生的二阶矩。EXP3 沿用 Hedge 的势函数记账，但把“看不见的损失”换成重要性加权量；无偏性修复一阶项，额外的 $K$ 因子则准确记录信息缺失的价格。

势函数分析 ​

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

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

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

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

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

概率空间包含算法抽臂的全部随机性。对 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$，标准外部遗憾问题便退化。

EXP3 把全信息指数权重方法接到部分反馈协议上，因此它一端通向遗憾与比较器类公理库遗憾与比较器类Regret · Comparator class用累计损失相对预先规定的比较器类最优值来评价在线决策。中的最好固定臂基准，另一端通向重要性估计的方差控制。若环境具有固定均值和 gap，应改用随机赌博机与伪遗憾公理库随机赌博机与伪遗憾Stochastic bandit · Pseudo-regret每个臂从固定分布独立取样时，以均值差和选择次数表达期望损失。的模型与算法；若需要高概率保证，则必须采用与采样分布、偏置估计相匹配的 EXP3.P 或 EXP3-IX 分析，不能只替换定理标题。