多臂赌博机模型

Bandit 的本质是反馈缺失，而不是“有多个选项”。在损失有界的共同设定下，若每轮能看到全部臂结果，就得到全信息专家问题理路专家建议预测Prediction with expert advice在全信息反馈下组合多个专家，并与事后最好的固定专家比较。；学习器只有实际选择某臂，才能获得关于它的新证据，因此探索本身会消耗奖励。

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

三臂广告与信息边界 ​

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

遗漏反馈不能填成零奖励。例如两臂潜在奖励均为 $1$，以概率 $(1/4,3/4)$ 选择。未选位置填零时，第一臂记录的期望只有 $1/4$；用估计 ${\hat{X}}_1=4\mathbf{1}\{I=1\}$，它以概率 $1/4$ 取 $4$，否则取零，期望恢复为 $1$，方差却为 $3$。探索概率控制的是这种信息与方差代价，并未补出当轮真实反事实。

合法策略可写为条件分布 ${\pi }_t(\cdot \mid H_{t-1})$，确定策略是其退化特例。探索要求算法取得足够信息，却不要求每一轮都给所有臂正概率：随机模型中的 UCB 可先逐臂初始化，再确定性地选择置信上界最大的臂；EXP3 一类随机化算法则通过正采样概率构造重要性估计。两种机制分别依赖各自的环境假设。

环境与目标的分支 ​

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

目标也会分支。累计遗憾不愿频繁试差臂，最佳臂识别理路最佳臂识别best-arm identification以可靠选出最高均值臂为目标，研究纯探索的停止规则与样本复杂度。却可牺牲过程奖励来降低最终推荐错误；报告“找到了最好臂”不能代替遗憾保证，反过来也一样。全信息、随机 bandit、对抗 bandit 与纯探索因而共享动作集合，却不能共享同一条性能定理。