上下文赌博机

协议 ​

上下文赌博机在普通多臂模型前加入每轮可见的上下文 $X_t\in \mathcal{X}$。第 $t$ 轮依次发生：

1. 环境给出上下文 $X_t$；
2. 环境在不知道本轮随机动作的条件下确定潜在奖励向量 $(Y_t(a){)}_{a\in \mathcal{A}}$；
3. 学习器根据历史和 $X_t$ 选择动作 $A_t\in \mathcal{A}$，并只观察 $Y_t(A_t)$。

上下文可以是用户特征、当前系统状态或查询内容。动作选择允许依赖当前上下文，却不能查看本轮潜在奖励或让对手在看见抽样结果后再改写它们。未选择动作的反事实奖励不可见，这使问题不同于完整监督的多类预测：后者通常能从标签计算每个候选动作或类别的损失。

策略类与 policy regret ​

策略是映射

$$\pi :\mathcal{X}\to \mathcal{A}.$$

给定比较类 $\mathrm{\Pi }$，学习器相对最佳固定策略的遗憾为

$$R_T(\mathrm{\Pi })=\underset{\pi \in \mathrm{\Pi }}{max}\sum _{t=1}^T{Y}_t(\pi (X_t))-\sum _{t=1}^T{Y}_t(A_t).$$

这里“固定”指整轮开始前从同一个策略类选一张上下文决策规则，并非每轮固定同一个动作。若 $\mathrm{\Pi }$ 包含所有函数，比较器可能复杂到无法泛化或优化；策略类复杂度和 oracle 可解性必须进入保证。

有些文献把上式称为 contextual regret，把 policy regret 专门留给环境奖励会因学习器过去动作而改变的反应型对手。使用术语时应给公式；本页采用最常见的“相对策略类遗憾”含义，同时提醒存在这一区分。

随机可实现模型 ​

在 IID 随机模型中，$(X_t,Y_t(1),\dots ,Y_t(K))$ 独立同分布。若存在 $f^{\ast }$ 使

$$\mathbb{E}[Y_t(a)\mid X_t=x]=f^{\ast }(x,a),$$

称奖励模型 realizable。最优策略为

$${\pi }^{\ast }(x)\in \arg \underset{a}{max}{f}^{\ast }(x,a).$$

函数类可错设时，分析必须明确是与类内最佳奖励预测器、最佳诱导策略，还是所有策略中的 Bayes 最优者比较；这三者的逼近误差不同。

另一条路线不建模奖励数值，而直接假设一个有限或可优化的策略类 $\mathrm{\Pi }$。算法通过带权分类/策略优化 oracle 从数据中寻找高估计收益策略。该路线的统计对象是策略价值，不要求每个动作奖励模型都准确。

IPS 无偏估计 ​

若第 $t$ 轮按已知概率 $p_t(a\mid X_t)$ 抽取动作，则策略 $\pi$ 的重要性加权奖励估计为

$${\hat{Y}}_t(\pi )=\frac{Y_t(A_t)\mathbf{1}\{\pi (X_t)=A_t\}}{p_t(A_t\mid X_t)}.$$

条件于历史、上下文和潜在奖励，

$$\mathbb{E}[{\hat{Y}}_t(\pi )]=Y_t(\pi (X_t)).$$

因此可以用 bandit 反馈比较许多策略。代价是分母很小时方差爆炸；算法必须保证足够探索，或采用裁剪、自归一化和 doubly robust 估计，同时跟踪由这些修改产生的偏差。

optimism 路线 ​

若奖励模型带置信集合，可对每个 $(x,a)$ 构造乐观预测，再选择乐观值最大的动作。线性上下文模型由此进入线性赌博机公理库线性赌博机Linear bandit · Stochastic linear bandit · 线性上下文赌博机假设动作特征的期望奖励由未知线性参数给出，并用自归一化置信椭球设计乐观动作选择与维度相关遗憾界。。更一般函数类需要能同时控制数据依赖动作下的估计误差，普通监督学习误差界不一定足够。

IPS 与 optimism 不是同一算法的两种符号。前者构造策略价值的无偏反事实估计，后者维护奖励模型的不确定集合。许多现代方法会组合二者，但证明中仍要分别控制方差与模型置信事件。

推荐内容例子 ​

新闻推荐系统看到读者的语言、设备和当前栏目后，从数篇文章中选一篇，只观察被展示文章是否点击。一个策略可能规定“移动端早晨展示短新闻，桌面端晚间展示深度文章”。若系统始终按当前估计最优文章贪心展示，未探索文章永远缺少数据，早期噪声会被锁定；上下文相关的随机探索让每类读者上的反事实比较成为可能。

把未点击当作所有未展示文章的负标签是错误的：未展示动作没有产生可观测结果。反过来，只在历史日志中评价一个经常选择日志罕见动作的新策略，会出现极小 propensity 和巨大方差，即使 IPS 公式形式上仍无偏。

边界 ​

标准遗憾模型通常假设当前潜在奖励不会因当前随机选择概率本身而改变。广告竞争、库存和社交反馈可能让动作影响未来状态，此时问题更接近强化学习或反应型环境。上下文 bandit 没有状态转移信用分配，不能靠扩充上下文名称自动覆盖长期效应。

离线策略评价还要求日志 propensity 已知或可可靠估计，并满足 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.