多臂赌博机模型

根协议 ​

有 $K$ 个臂。第 $t$ 轮策略依据历史

$$H_{t-1}=(I_1,X_{1,I_1},\dots ,I_{t-1},X_{t-1,I_{t-1}})$$

选择 $I_t$，随后只观察被选臂的奖励 $X_{t,I_t}$。非预见策略不能使用未来奖励，也不能访问未选臂的反事实结果。奖励表述与损失表述可互换，但一篇分析中符号方向和范围必须固定。

一种统一写法先引入潜在奖励表 $(X_{t,i}{)}_{t\le T,i\le K}$：$X_{t,i}$ 表示“第 $t$ 轮如果选臂 $i$ 会得到什么”。学习器只实现并观察其中一个坐标 $X_{t,I_t}$，其余潜在结果不可见。可观察历史生成的信息族为

$${\mathcal{F}}_t=\sigma (I_1,X_{1,I_1},\dots ,I_t,X_{t,I_t}),$$

合法策略要求 $I_t$ 的条件分布对 ${\mathcal{F}}_{t-1}$ 可测。这个条件精确排除了用未选奖励或未来行作弊。

环境分支而非共同前提 ​

随机模型通常令每臂的观测是固定分布 ${\nu }_i$ 的独立样本，潜在表可在开始时随机生成；对抗模型则允许损失行任意变化，只限制对手不能看见本轮尚未抽出的 $I_t$ 后再设值。两者共用可观察历史，却在概率来源、比较量和算法分析上分叉：前者有均值与 gap，后者只有相对最好固定臂的遗憾。

Bandit 的本质是反馈缺失，而不是“有多个选项”。若每轮能看到全部臂结果，就是 full-information 专家问题；若目标是在固定预算后只识别最好臂而不在乎过程中损失，则是 best-arm identification，不是累计遗憾任务。

根模型不假设奖励 IID，也不假设由对手设置。随机 bandit公理库随机赌博机与伪遗憾Stochastic bandit · Pseudo-regret每个臂从固定分布独立取样时，以均值差和选择次数表达期望损失。加入固定分布与均值，对抗 bandit公理库对抗赌博机模型Adversarial bandit损失向量可任意变化、学习器只观察所选坐标的在线决策模型。允许损失任意变化。把两组假设同时塞入根定义会掩盖算法为何成立。

三臂广告例子中，第 $t$ 轮选择版式 2 后只知道它是否被点击；版式 1 和 3 在同一用户身上的结果是反事实，数据中并不存在。若系统后台同时运行无干扰的随机对照并能观察三者结果，反馈结构才接近全信息。Bandit 的探索成本正来自必须实际选择某臂才能收窄它的不确定性。

合法策略可写为条件分布 ${\pi }_t(\cdot \mid H_{t-1})$。确定策略是其退化特例；随机化不是装饰，在对抗环境中可防止对手预先针对固定动作次序。冷启动时若某臂从不被选择，就没有数据识别它是否最优，因此多数遗憾算法显式保证每个臂获得正概率。

累计遗憾与纯探索目标也会要求不同动作。前者不愿频繁试差臂，后者可牺牲过程奖励来降低最终推荐错误。报告“找到了最好臂”不能代替遗憾保证，反过来也一样。

参考资料

• Bubeck, Cesa-Bianchi, “Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems,” 2012.
• Tor Lattimore, Csaba Szepesvári, Bandit Algorithms, Cambridge University Press, 2020, Chs. 4 and 11.