EXP3 算法

部分反馈的核心障碍是：算法既要把一个被抽中的坐标恢复成整行损失的无偏估计，又要承担由 $1/p_{t,i}$ 放大产生的二阶矩。EXP3 使用乘法权重方法理路乘法权重更新方法multiplicative weights update · MWU以指数方式降低高损失动作的权重，并用总权重势函数给出累计性能保证。的总权重夹逼，把“看不见的损失”换成重要性加权量；无偏性修复一阶项，额外的 $K$ 因子则准确记录信息缺失的价格。

更新形式与Hedge理路指数权重与 HedgeHedge algorithm · exponential weights在全信息有界损失下按累计损失指数加权，并取得平方根级专家 regret。相近，但重要性估计可能大于 $1$，不能直接调用它的单位区间损失界。下面改用适用于非负量的二次指数估计。

势函数分析 ​

记 $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$，

对非预见自适应对手，这控制模型页的 ${\overline{R}}_T=\underset{j}{max}\mathbb{E}[L_T-L_{T,j}]$。对确定的 oblivious 损失表，事后最好臂不随算法随机性变化，两种指标相等。取 $K\ge 2,T\ge 1$、$\eta =\sqrt{2\log K/(KT)}$，后一种情形得到

这里的期望包含算法抽臂的全部随机性。自适应对手下，最好臂也可能依赖同一段随机历史，因而不能把最小值直接移进期望。

例如两臂两轮，第一轮损失为 $(0,0)$，所以前两轮 EXP3 都均匀抽臂。若第一轮选臂 $1$，对手在第二轮设 $(0,1)$；否则设 $(1,0)$。它只读取过去动作，仍然非预见。算法期望总损失为 $1/2$，每个固定臂的期望总损失也为 $1/2$，故 ${\overline{R}}_2=0$；每张实际表却都有零损失臂，因此 $\mathbb{E}[{\mathrm{Reg}}_2]=1/2$。

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

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

一个广告位的点击收益可能按新闻周期变化，根本不存在固定均值 gap。若损失表预先确定，EXP3 可与事后最好固定广告比较；若损失依历史自适应变化，本页证明只保证 ${\overline{R}}_T$。UCB 的平稳均值论证在一般对抗表上没有适用对象；若环境真是平稳随机臂，利用 gap 的 UCB 可以给出更精细的界。

失败边界 ​

$K=1$ 时始终选择唯一臂，两种遗憾都为零，无需使用含 $\log K$ 的优化学习率。

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

EXP3 的证明提供了一种可迁移的分工：指数权重负责把估计损失与比较器理路遗憾与比较器类Regret · Comparator class用累计损失相对预先规定的比较器类最优值来评价在线决策。联系起来，反馈协议决定如何构造估计、能控制多大的二阶矩。迁移到组合动作时，需要先说明一次观测能恢复哪些坐标；仅把臂数换成动作集合大小，未必反映实际的信息结构。