上下文赌博机

形式陈述 ​

交互协议 ​

先固定有限非空动作集 $\mathcal{A}=\{1,\dots ,K\}$，奖励取值于 $[0,1]$。上下文赌博机在普通多臂赌博机理路多臂赌博机模型Multi-armed bandit · MAB每轮选择一个臂，并且只观察该臂结果的部分反馈序贯决策模型。前加入每轮可见的上下文 $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)$。

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

策略类与上下文遗憾 ​

这里的策略正是一个以动作集为值域的预测器理路预测器与假设类Predictor · Hypothesis class区分可用于预测的函数、函数集合及其参数表示。，即映射

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

比较类在交互前确定，式中的最佳规则则在整段数据之后比较选出；“固定”指始终使用同一映射 $\pi$，并非每轮固定同一个动作。若 $\mathrm{\Pi }$ 包含所有函数，比较器可能复杂到无法泛化或优化；策略类复杂度和 oracle 可解性必须进入保证。

上式始终在实际产生的上下文与奖励表上评价比较器。反应型环境中的 policy regret 则会问“若从一开始改用比较策略，环境会产生什么轨迹”；它需要另外的反事实环境定义，不能由上式直接代替。涉及期望时还假定该上确界可测。

随机可实现模型 ​

在 IID 随机模型中，$(X_t,Y_t(1),\dots ,Y_t(K))$ 独立同分布。预先给定可测奖励函数类 $\mathcal{F}$；若存在 $f^{\ast }\in \mathcal{F}$，对几乎所有上下文及每个动作满足

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

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

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

IPS 无偏估计 ​

若第 $t$ 轮按已知概率 $p_t(a\mid X_t)$ 抽取动作，固定策略 $\pi$ 在本轮抽样前已经确定，且 $p_t(\pi (X_t)\mid X_t)>0$，则重要性加权估计理路赌博机重要性加权估计importance-weighted bandit estimator把单个被选臂的反馈放大为完整损失向量的条件无偏估计。的奖励版本为

令 ${\mathcal{G}}_t$ 包含此前历史、当前上下文和潜在奖励向量，且条件于 ${\mathcal{G}}_t$ 的动作抽样分布仍为 $p_t$。于是

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

连续动作集合的版本 ​

在线性等应用中，当前上下文还可以提供一个非空紧集 ${\mathcal{A}}_t\subseteq {\mathbb{R}}^d$，而不局限于固定的有限编号。这里假定动作集合以可测方式给出，允许的策略是支持在当前 ${\mathcal{A}}_t$ 上的可测概率核；所需的确定性选择也须可测。学习器选出 $A_t$ 后只观察该动作的标量奖励。随机模型可直接指定其给定当前信息与动作的条件均值 $g(X_t,A_t)$，无需假设未选动作的奖励已经被观测。

线性且连续的均值函数在每个紧动作集上达到最大值；采用最优选择时另假定存在相应可测选择。一般策略类的最优值若不达到，仍应使用上确界或说明近似选择误差。这个版本保留“先见上下文、再行动、只见所选反馈”的顺序，奖励范围与尾部条件由具体模型另行给出。

上面的有限臂 IPS 公式只适用于具有正点概率的动作。连续分布通常对每个单点赋零概率，不能把密度直接当作同一个分母；连续动作的重要性加权需要目标与采样测度之间的绝对连续条件及相应密度比，未由该有限求和证明建立。