对抗赌博机模型

模型与信息顺序 ​

环境给出 ${\ell }_t\in [0,1{]}^K$，学习器从历史决定的分布 $p_t$ 抽取 $I_t$，只观察 ${\ell }_{t,I_t}$。评价期望外部遗憾

$$\mathbb{E}\sum _t{\ell }_{t,I_t}-\underset{i}{min}\sum _t{\ell }_{t,i}.$$

概率至少包含算法随机性。Oblivious 对手可预先任意固定损失序列；non-anticipating 自适应对手可看历史，却不能先看本轮 $I_t$ 再设置该轮损失，否则可总让所选臂损失为 1，标准问题退化。

未见坐标通常用重要性加权

$${\hat{\ell }}_{t,i}=\frac{{\ell }_{t,i}\mathbf{1}\{I_t=i\}}{p_{t,i}}$$

估计；条件期望等于 ${\ell }_{t,i}$，但 $p_{t,i}$ 太小时方差很大，所以算法必须保留探索。与随机 bandit 不同，这里没有固定均值和 gap，不能使用 ${\mathrm{\Delta }}_i$ 分解。与专家全信息模型相比，缺失反馈使典型遗憾从 $\sqrt{T\log K}$ 恶化到 $\sqrt{TK}$ 量级。

无偏性可直接核验：条件于历史，

$${\mathbb{E}}_t{\hat{\ell }}_{t,i}=p_{t,i}\frac{{\ell }_{t,i}}{p_{t,i}}+(1-p_{t,i})0={\ell }_{t,i}.$$

但二阶矩为 ${\ell }_{t,i}^2/p_{t,i}$，概率越小方差越大；若 $p_{t,i}=0$，估计器甚至无定义。这就是 Exp3 一类算法混入探索质量的定量原因。

对手若看见本轮 $I_t$ 后再设损失，可令被选臂损失 1、其余为 0；算法每轮损失 1，而事后至少有某臂只被选约 $T/K$ 次，产生线性遗憾。Non-anticipating 条件正是排除这种读心式环境，不等于假设损失随机或温和。

Exp3 的势函数与专家 Hedge 相似，但用 ${\hat{\ell }}_{t,i}$ 代替完整损失。无偏估计让一阶项恢复真实损失，二阶项则累积约 $K$ 的方差代价，优化学习率后出现 $O(\sqrt{TK\log K})$ 量级。相较全信息多出的 $\sqrt{K}$，正是隐藏坐标的价格。

对自适应对手，比较向量 ${\ell }_t$ 可能依赖过去随机历史，因此期望条件要逐轮处理；把所有损失当成预先固定后直接应用独立集中并不合法。高概率界通常还需显式探索或带偏的重要性估计来控制重尾。

参考资料

• Auer et al., “The Nonstochastic Multiarmed Bandit Problem,” 2002.
• Bubeck, Cesa-Bianchi, 2012.