对抗赌博机模型

未见坐标通常用重要性加权理路赌博机重要性加权估计importance-weighted bandit estimator把单个被选臂的反馈放大为完整损失向量的条件无偏估计。

估计；在 $p_{t,i}>0$ 时，其关于 ${\mathcal{G}}_t$ 的条件期望等于 ${\ell }_{t,i}$，但概率很小时方差很大。与随机 bandit理路随机赌博机与伪遗憾Stochastic bandit · Pseudo-regret每个臂从固定分布独立取样时，以均值差和选择次数表达期望损失。不同，这里没有固定均值和 gap，不能使用 ${\mathrm{\Delta }}_i$ 分解。缺失反馈会增加遗憾的维数代价，具体界还依赖算法与采用的遗憾指标。

无偏性可直接核验：条件于 ${\mathcal{G}}_t$，

但二阶矩为 ${\ell }_{t,i}^2/p_{t,i}$，概率越小方差越大；若 $p_{t,i}=0$，估计器甚至无定义。正概率是这里的必要条件，均匀混合探索只是控制尾部的一种办法；这里的损失版 EXP3由正指数权重保证正概率，并不显式混合探索。

反应式对手为何使问题退化 ​

当 $K\ge 2$ 时，对手若看见本轮 $I_t$ 后再设损失，可令被选臂损失 $1$、其余为 $0$。算法累计损失为 $T$，而至少有某臂被选次数不超过 $T/K$，因此遗憾至少为 $T(1-1/K)$。Non-anticipating 条件正是排除这种读心式环境，不等于假设损失随机或温和。

对自适应对手，比较向量 ${\ell }_t$ 可能依赖过去随机历史，因此期望条件要逐轮处理；把所有损失当成预先固定后直接应用独立集中并不合法。条件无偏性与鞅集中都必须相对正确的历史过滤陈述，不能用一个脱离历史的固定样本方差替代。

随机 bandit 的固定均值和 gap 在这里不存在；把 ${\mathrm{\Delta }}_i$ 分解或 IID 置信半径原样搬来，等于悄悄改变环境权限。反过来，允许对手依赖过去不等于允许它读取尚未实现的本轮随机动作，两个自适应层次必须分开。

EXP3理路EXP3 算法EXP3 · Exponential-weight algorithm for Exploration and Exploitation以重要性加权损失替代完整反馈，将指数权重方法转化为具有平方根期望遗憾的对抗赌博机算法。的势函数与全信息专家问题理路专家建议预测Prediction with expert advice在全信息反馈下组合多个专家，并与事后最好的固定专家比较。中的 Hedge 相似，但用 ${\hat{\ell }}_{t,i}$ 代替完整损失。其逐轮证明对非预见自适应对手控制 ${\overline{R}}_T=O(\sqrt{TK\log K})$；对确定的 oblivious 损失表，同一界也控制 $\mathbb{E}[{\mathrm{Reg}}_T]$。高概率或自适应环境下事后最优臂的期望保证需要进一步分析，不能直接交换最小值与期望。