赌博机重要性加权估计

构造 ​

第 $t$ 轮根据历史 ${\mathcal{F}}_{t-1}$ 选择分布 $p_t$，抽取 $I_t\sim p_t$，只观察 ${\ell }_{t,I_t}$。对每个臂定义

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

只要 $p_{t,i}>0$，条件于过去和当轮损失向量，

$$\mathbb{E}[{\hat{\ell }}_{t,i}\mid {\mathcal{F}}_{t-1}]=\frac{{\ell }_{t,i}}{p_{t,i}}\text{Pr}(I_t=i\mid {\mathcal{F}}_{t-1})={\ell }_{t,i}.$$

因此一个坐标的观测可为所有坐标提供条件无偏估计：未选坐标记零，选中坐标按其逆采样概率放大。

均匀采样例子 ​

有 $K$ 个臂且 $p_{t,i}=1/K$ 时，若选中臂 $i$，估计为 $K{\ell }_{t,i}$；否则为零。它的均值仍是 ${\ell }_{t,i}$，却以低概率取大值。这不是换数字的演示，而是揭示 bandit 反馈的核心代价：为了从稀疏观测恢复全向量，必须支付方差。

二阶矩与探索 ​

直接计算得

$$\mathbb{E}[{\hat{\ell }}_{t,i}^2\mid {\mathcal{F}}_{t-1}]=\frac{{\ell }_{t,i}^2}{p_{t,i}}.$$

$p_{t,i}$ 越小，二阶矩越大；若为零，估计甚至不可定义。EXP3 等算法因而混入显式均匀探索以给概率下界，或使用 implicit exploration 的有偏/平滑估计来控制尾部。无偏不等于低误差，势函数证明必须保留这一方差项。

可测性与边界 ​

$p_t$ 必须相对过去可测，$I_t$ 再按该分布抽样，才能写出上述条件期望公理库条件期望Conditional expectation相对于子 σ-代数可测并保持其事件上积分的随机变量。。若损失会在看见当轮随机动作后再被对手选择，需明确 adversary 类型，简单条件无偏式可能改变。该估计只完成反馈重建；EXP3 的权重更新与 regret 推导是下一层内容，不能由“无偏”一句话自动得到。

参考资料

• Peter Auer et al., The Nonstochastic Multiarmed Bandit Problem, SIAM Journal on Computing, 2002.
• Sébastien Bubeck, Nicolò Cesa-Bianchi, Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems, Foundations and Trends in Machine Learning, 2012.