“线性赌博机把上下文赌博机中的每轮动作集合表示成向量：第 $t$ 轮学习器看到 $\mathcal A t\subseteq\mathbb R^d$，选择 $x t\in\mathcal A…”
形式陈述
交互协议
上下文赌博机在普通多臂赌博机前加入每轮可见的上下文
- 环境给出上下文
； - 环境在不知道本轮随机动作的条件下确定潜在奖励向量
； - 学习器根据历史和
选择动作 ，并只观察 。
上下文可以是用户特征、当前系统状态或查询内容。动作选择允许依赖当前上下文，却不能查看本轮潜在奖励或让对手在看见抽样结果后再改写它们。未选择动作的反事实奖励不可见，这使问题不同于完整监督的多类预测：后者通常能从标签计算每个候选动作或类别的损失。
策略类与 policy regret
这里的策略正是一个以动作集为值域的预测器，即映射
给定比较类
这里“固定”指整轮开始前从同一个策略类选一张上下文决策规则，并非每轮固定同一个动作。若
有些文献把上式称为 contextual regret，把 policy regret 专门留给环境奖励会因学习器过去动作而改变的反应型对手。使用术语时应给公式；本页采用最常见的“相对策略类遗憾”含义，同时提醒存在这一区分。
随机可实现模型
在 IID 随机模型中，
称奖励模型 realizable。最优策略为
函数类可错设时，分析必须明确是与类内最佳奖励预测器、最佳诱导策略，还是所有策略中的 Bayes 最优者比较；这三者的逼近误差不同。
另一条路线不建模奖励数值，而直接假设一个有限或可优化的策略类
IPS 无偏估计
若第
条件于历史、上下文和潜在奖励，
因此可以用 bandit 反馈比较许多策略。代价是分母很小时方差爆炸；算法必须保证足够探索，或采用裁剪、自归一化和 doubly robust 估计，同时跟踪由这些修改产生的偏差。
直觉
普通多臂赌博机只需弄清“哪只臂平均更好”，上下文赌博机还要学习“在什么情形下哪只臂更好”。每轮看见
IPS 提供的是一把“把随机日志还原成策略价值”的尺子：某动作越少被抽到，一次命中就要用越大的权重代表那些未被观察的同类轮次。无偏性由此得到，方差也从同一个分母里冒出来。另一条路线是 optimism：不直接重构每个策略的价值，而是为奖励模型维护置信集合，并在尚不能排除的最好情形下行动。
IPS 与 optimism 的分工
若奖励模型带置信集合，可对每个
IPS 与 optimism 不是同一算法的两种符号。前者构造策略价值的无偏反事实估计，后者维护奖励模型的不确定集合。许多现代方法会组合二者，但证明中仍要分别控制方差与模型置信事件。
例子与边界
新闻推荐
新闻推荐系统看到读者的语言、设备和当前栏目后，从数篇文章中选一篇，只观察被展示文章是否点击。一个策略可能规定“移动端早晨展示短新闻，桌面端晚间展示深度文章”。若系统始终按当前估计最优文章贪心展示，未探索文章永远缺少数据，早期噪声会被锁定；上下文相关的随机探索让每类读者上的反事实比较成为可能。
把未点击当作所有未展示文章的负标签是错误的：未展示动作没有产生可观测结果。反过来，只在历史日志中评价一个经常选择日志罕见动作的新策略，会出现极小 propensity 和巨大方差，即使 IPS 公式形式上仍无偏。
三条不能省略的边界
标准遗憾模型通常假设当前潜在奖励不会因当前随机选择概率本身而改变。广告竞争、库存和社交反馈可能让动作影响未来状态，此时问题更接近强化学习或反应型环境。上下文 bandit 没有状态转移信用分配，不能靠扩充上下文名称自动覆盖长期效应。
离线策略评价还要求日志 propensity 已知或可可靠估计，并满足 overlap：目标策略可能选择的动作在日志策略下必须有正概率。没有支持重叠时，缺失反事实无法由更多代数恢复。
推论与应用
当奖励均值可以写成上下文—动作特征的线性函数时，策略类比较可转成参数估计与椭球置信集问题，于是得到线性赌博机：动作不再只是有限编号，几何结构会决定哪些探索能够同时缩小许多动作的不确定性。
若模型更一般，仍可沿不确定性下的乐观原则设计算法。上下文在每轮改变可用动作的预测值，而置信宽度把“尚未验证的潜力”显式计入选择；相应证明必须说明置信事件为何对自适应采样序列同时成立。
在离线推荐与广告评估中，IPS 公式进一步导向反事实风险最小化和 doubly robust 估计。它们能降低模型偏差或方差，却不能创造日志策略从未覆盖的动作数据；overlap 因而既是统计条件，也是上线实验和日志设计的约束。
参考资料
- John Langford and Tong Zhang, “The Epoch-Greedy Algorithm for Multi-armed Bandits with Side Information,” NeurIPS, 2007.
- Alekh Agarwal et al., “Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits,” ICML, 2014.
- Lihong Li et al., “A Contextual-Bandit Approach to Personalized News Article Recommendation,” WWW, 2010.