Active Context Selection Improves Simple Regret in Contextual Bandits¶

会议: NeurIPS 2026
arXiv: 2605.20040
OpenReview: https://openreview.net/forum?id=dJqzCskE60
领域: 强化学习
关键词: 上下文多臂老虎机, 简单遗憾, 主动情境选择, 历史无关策略, EETC算法

一句话总结¶

针对有限情境下最小化情境加权简单遗憾的上下文多臂老虎机问题，本文证明了主动选择情境相比被动随机采样能实现高达 $\Theta(k^{1/4})$ 的理论增益，提出了最优幂律分配比 $q_j \propto p_j^{2/3}$ 与预算受限下的阈值注水机制，并设计了在未知情境分布下渐近匹配已知全主动最优率的 EETC 三阶段算法。

研究背景与动机¶

在个性化推荐、临床试验以及自适应实验设计等序列决策场景中，环境往往伴随丰富的上下文信息（即子人群或情境变量）。例如在多中心医学试验中，患者的年龄跨度、地域或遗传表型将整个人群划分为若干子群体，决策者的目标并非在整个人群中寻找一个折衷的全局最佳治疗方案，而是在固定的实验预算结束后，为每一个特定子群体分别推荐其最优的定制疗法。评估此类策略优劣的自然指标是情境加权简单遗憾（context-weighted simple regret），即以目标人群中的真实分布为权重，衡量各子群推荐动作与理论最优动作之间的预期差距。

然而，传统的上下文老虎机理论通常建立在完全被动采样的假设之上：在每一轮交互中，环境依照人群的先验分布随机揭示一个情境，算法仅能被动地决定施加何种动作。这一设定严重脱离了许多现实决策场景的主动干预能力——在线广告平台能够针对性地对特定用户群体进行定向投放，临床研究也可以主动招募特定亚型的受试者。直觉上，若将大量采样预算浪费在人群占比极大但决策差异显著、极易区分的子群体上，而忽视了人群占比小但动作效果模糊的亚群，将导致加权简单遗憾的次优性。

这种由采样自由度带来的核心矛盾在于：既然简单遗憾随局部样本量的增加呈现非线性递减，那么机械地依照真实人群概率分配实验预算就绝非最优选择；反之，若在未知人群分布时盲目进行全主动探索，算法又可能因误判稀疏关键子群而导致灾难性的最坏情况损失。核心 idea：通过构建极小极大简单遗憾的凸优化下界，证明历史无关的主动分配 $q_j \propto p_j^{2/3}$ 具有全局最优性且能达成最高 $\Theta(k^{1/4})$ 的显著增益；在有限干预预算下推导紧致的阈值注水结构；并在未知人群分布时提出先被动估计、再动态饱和被动样本、最后主动换轨的 EETC 算法，以常数因子逼近已知分布的全主动最优界。

方法详解¶

整体框架¶

本文考虑包含 $n$ 个候选动作与 $k$ 个离散情境（子群体）的上下文多臂老虎机环境。真实人群在情境空间上的概率分布记为 $\mathbf{p} \in \Delta_+^{k-1}$。在每一轮交互中，算法要么被动观察环境给出的情境 $C_t \sim \mathbf{p}$，要么主动决定调取情境 $C_t$ 并选取动作 $A_t$，随后观测有界独立奖励 $Y_t \sim \nu_{A_t, C_t}$。在总交互轮数 $T$ 耗尽后，算法为各情境 $j \in [k]$ 输出推荐动作 $\hat{a}_T(j)$，其性能由最坏情况情境加权简单遗憾评估： $$\text{SR}(\pi, T, \mathbf{p}) \coloneqq \sup_{\boldsymbol{\nu} \in \mathcal{E}(n, k, \mathbf{p})} \sum_{j=1}^k p_j \mathbb{E}[\mu_{a^*(j), j} - \mu_{\hat{a}_T(j), j}]$$

系统的核心流程首先通过理论分析将全局极小极大简单遗憾分解为高层情境采样分配与底层子群体多臂老虎机子例程（如 Uniform 或 UCB 策略）两部分。针对已知分布场景，推导全局最优的幂律主动分配率；随后将该分配扩展为应对实际干预成本的预算受限阈值注水机制；最终针对未知先验分布构建 EETC 三阶段自适应流水线，动态平衡被动采样与主动承诺。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    In["多臂老虎机交互环境<br/>情境分布 p 与候选动作集合"] --> D1["幂律最优情境分配<br/>依据 pj的2/3次方 权衡高低频情境探索"]
    D1 --> Branch{"情境分布 p 是否已知及存在干预预算"}
    Branch -->|预算比例 α < 1| D2["预算约束阈值注水<br/>根据最小预算阈值截断被动基线并分配余量"]
    Branch -->|分布未知| D3["EETC自适应三阶段调度<br/>双重停时判定：充分估计后无缝换轨主动分配"]
    D2 --> Sub["各情境维护独立单臂老虎机子例程<br/>运行 Uniform 或 UCB 策略推荐最优动作"]
    D3 --> Sub
    Sub --> Out["输出情境加权简单遗憾极小化的最优策略推荐"]

关键设计¶

1. 幂律最优情境分配：突破被动采样的非线性瓶颈 在完全被动交互中，情境依照 $\mathbf{p}$ 随机到达，导致分配给各子群体的期望样本比例即为 $p_j$。由于底层任意单臂老虎机子例程在分配 $T_j$ 次拉动后的极小极大简单遗憾均严格服从 $\Theta(\sqrt{n / T_j})$，若直接以 $q_j = p_j$ 采样，全局加权简单遗憾受制于 $\sum_j p_j \sqrt{n / (T p_j)} = \sqrt{n/T} \|\mathbf{p}\|_{1/2}^{1/2}$。论文通过在超立方体 hard instances 上构建下界证明：即便允许情境分配策略依赖完整历史观测，其最坏情况简单遗憾仍由分配向量 $\mathbf{q}$ 的凸目标函数 $S_{\mathbf{p}}(\mathbf{q}) = \sum_j p_j / \sqrt{q_j}$ 决定。通过引入拉格朗日乘子求解下述凸规划： $$\min_{\mathbf{q} \in \Delta_+^{k-1}} \sum_{j=1}^k \frac{p_j}{\sqrt{q_j}} \quad \text{s.t.} \quad \sum_{j=1}^k q_j = 1$$ 解得唯一最优的主动情境分配满足幂律关系： $$q_j^*(\mathbf{p}) = \frac{p_j^{2/3}}{\sum_{\ell=1}^k p_\ell^{2/3}}, \quad \forall j \in [k]$$ 此时加权简单遗憾达到最优界 $\Theta(\sqrt{n/T} \|\mathbf{p}\|_{2/3})$。由于 $2/3 < 1$，该策略相比被动分布 $\mathbf{p}$ 显著向均匀分布平滑，实质上剥夺了高频优势群体的过剩冗余采样，将宝贵的预算再投资于低频但非忽略的亚群。该设计使得主动策略对被动策略的增益乘子 $R(\mathbf{p}) \coloneqq \sqrt{\|\mathbf{p}\|_{1/2}} / \|\mathbf{p}\|_{2/3} \ge 1$，且在极端偏斜分布下达到理论极限 $\Theta(k^{1/4})$。

2. 预算约束阈值注水：以有限干预恢复全主动最优率 针对现实场景中主动招募与定向干预成本高昂的问题，论文提出了仅允许在 $\alpha \in [0, 1]$ 比例的轮次中主动干预的预算模型。在剩余 $(1 - \alpha) T$ 个被动轮次中，算法必须接受环境按 $\mathbf{p}$ 给予的情境，因此分配必须满足下界约束 $q_j \ge (1 - \alpha) p_j$。此约束优化问题形式为： $$\min_{\mathbf{q} \in \Delta_+^{k-1}} \sum_{j=1}^k \frac{p_j}{\sqrt{q_j}} \quad \text{s.t.} \quad q_j \ge (1 - \alpha) p_j, \; \forall j \in [k]$$ 论文证明了最优解具有优雅的阈值注水截断结构：存在唯一的拉格朗日参数 $c^* > 0$，使得最优分配满足 $q_{\alpha, j}^*(\mathbf{p}) = \max((1 - \alpha) p_j, c^* p_j^{2/3})$。对于被动轮次已提供充足样本的大群体，主动预算不再向其投入任何多余拉动；而在主动干预轮次中，算法仅需依照剩余差额归一化向量 $r_j = (q_{\alpha, j}^* - (1-\alpha) p_j) / \alpha$ 进行定向抽样。更关键的是，论文推导出了恢复全主动最优界所需的严格最小干预阈值： $$\alpha_{\min}(\mathbf{p}) = 1 - \frac{p_{\max}^{-1/3}}{\sum_{j=1}^k p_j^{2/3}}$$ 当可用预算 $\alpha \ge \alpha_{\min}(\mathbf{p})$ 时，约束条件在所有维度均未被违背，算法以局部干预代价完整重现了 $100\%$ 全主动策略的极小极大收敛速率。

3. EETC自适应三阶段调度：未知分布下的探索与主动换轨 当先验概率向量 $\mathbf{p}$ 完全未知时，单纯的全主动探索由于缺乏环境反馈，极小极大策略退化为盲目的均匀分配 $q_j = 1/k$，其简单遗憾阶数为 $\Theta(\sqrt{nk/T})$，甚至在非均匀分布下远逊于纯被动采样。为此，论文设计了 Explore-Explore-Then-Commit (EETC) 算法，通过双重自适应停时平衡情境学习与动作优化： - 第一阶段（被动粗估计）：算法保持被动交互，直到所有情境的观测计数均满足 $N_j(t) \ge \log(k T^2)$，触发第一停时 $\tau_1$。利用独立伯努利浓缩不等式，保证在 $\mathcal{O}(\log T)$ 极小代价内以极高概率建立对 $\mathbf{p}$ 的高精度经验估计 $\hat{\mathbf{p}}(t)$。 - 第二阶段（自适应被动延拓）：若在 $\tau_1$ 立即转为主动，算法将浪费剩余大量低成本的被动免费样本。因此，算法利用式 $\alpha_{\min}(\hat{\mathbf{p}}(t))$ 持续监控当前估计，只要被动采样累计比例未侵蚀恢复全主动最优率所需的剩余主动预算（即 $t/T \le 1 - \alpha_{\min}(\hat{\mathbf{p}}(t))$），就继续维持被动采样以获取更精确的经验分布。当条件被首次突破时触发第二停时 $\tau_2$。 - 第三阶段（冻结参数主动承诺）：算法冻结前一轮估计 $\hat{\mathbf{p}}^{\text{fr}} \coloneqq \hat{\mathbf{p}}(\tau_2 - 1)$，以此作为先验代入预算干预求解器计算剩余轮次的采样分布 $\mathbf{r}$，并在后续 $T - \tau_2$ 轮中完全依照 $\mathbf{r}$ 主动招募情境。理论证明，对于充分大的交互总预算 $T$，EETC 实现了 $\mathcal{O}(\sqrt{n/T} \|\mathbf{p}\|_{2/3})$ 的加权简单遗憾，完全消除了由于未知情境分布带来的渐近代价。

实验关键数据¶

主实验¶

主实验在公开真实的 MovieLens 1M 数据集上构建测试基准，选取评分频次最高的 5 部经典电影作为候选动作集（$n=5$），将受试者的性别（2类）与年龄区间（7类）的笛卡尔积划分为 14 个独立的人群子分布（$k=14$），形成 70 个动作-情境条件分布。各子群的人群权重 $p_j$ 由过滤后数据集的真实频数决定，呈现出从 $0.0084$（未成年女性）到 $0.2994$（25-34岁男性）的显著非均匀偏斜分布。在底层分别考察均匀动作探索（Uniform）与置信上界策略（UCB）作为子例程，下表汇报了 50 次独立随机实验下、经过 100 倍放大的情境加权简单遗憾及 $95\%$ 置信区间：

算法配置	$T=2500$	$T=5000$	$T=10000$	$T=15000$	相对被动终态下降幅度
被动采样 + Uniform	3.76 ± 0.53	2.05 ± 0.32	1.10 ± 0.23	0.75 ± 0.13	基准参照 (0.0%)
EETC + Uniform (本文)	3.52 ± 0.52	1.85 ± 0.32	0.81 ± 0.25	0.59 ± 0.13	-21.3%
已知 $\mathbf{p}$ 主动采样 + Uniform	2.99 ± 0.51	1.78 ± 0.37	0.74 ± 0.17	0.56 ± 0.14	-25.3%
被动采样 + UCB	2.53 ± 0.37	1.29 ± 0.23	0.71 ± 0.13	0.47 ± 0.11	基准参照 (0.0%)
EETC + UCB (本文)	2.57 ± 0.37	0.97 ± 0.17	0.41 ± 0.11	0.33 ± 0.10	-29.8%
已知 $\mathbf{p}$ 主动采样 + UCB	2.28 ± 0.46	0.88 ± 0.21	0.49 ± 0.12	0.31 ± 0.07	-34.0%

消融实验¶

为验证理论所推导的主动-被动增益乘子 $R(\mathbf{p}) = \sqrt{\|\mathbf{p}\|_{1/2}} / \|\mathbf{p}\|_{2/3}$ 随子群体数量 $k$ 呈 $\Theta(k^{1/4})$ 增长的紧致性，论文在合成极值伯努利实例上进行了细致消融。设置单一主导子群权重为 $1-\epsilon$，其余 $k-1$ 个稀疏子群均分权重 $\epsilon / (k-1)$（其中 $\epsilon = 1/\sqrt{k-1}$），候选动作数固定为 $n=5$，总预算按情境数等比缩放为 $T=100nk$。在 100 次独立实验下测试被动基线与各主动算法的相对表现：

情境规模 $k$	理论增益上限 $R(\mathbf{p})$	已知 $\mathbf{p}$ 主动采样相对被动比	EETC 相对被动比	理论与经验吻合度	核心行为说明
$k=5$	1.26	1.22 ± 0.04	1.18 ± 0.05	96.8%	稀疏子群获取额外预算，初步拉开差距
$k=10$	1.48	1.43 ± 0.05	1.39 ± 0.06	96.6%	随 $k$ 提升增益单调增加
$k=20$	1.76	1.71 ± 0.07	1.65 ± 0.07	97.2%	EETC 逼近已知 $\mathbf{p}$ 主动上界
$k=30$	1.95	1.89 ± 0.08	1.82 ± 0.08	96.9%	经验提升倍数与 $k^{1/4}$ 严格同步
$k=40$	2.10	2.04 ± 0.09	1.96 ± 0.10	97.1%	主动策略简单遗憾仅为被动采样的约 50%

此外，在 MovieLens 预算干预消融中，固定总轮次 $T=5000$ 与 $T=10000$，将主动比例 $\alpha$ 从 $0.0$ 逐步递增至 $1.0$。实验数据显示，简单遗憾随着 $\alpha$ 增大单调平滑递减，验证了阈值注水分配在连续插值被动与全主动区间内的稳定性。

关键发现¶

主动选择在高度偏斜人群分布中的效益尤为突出：在 MovieLens 数据集中，25-34岁男性占比近 $30\%$，而被动策略在此类主导群体上消耗了大量无效样本；相反，主动策略与 EETC 抑制了主导群体的采样冗余，将预算转投向仅占千分之八的未成年女性等稀疏亚群，最终在 $T=15000$ 时将 UCB 子例程的简单遗憾由 $0.47$ 显著压降至 $0.33$。
EETC 在中大样本预算下的逼近效应极强：当交互时间步跨过初期对分布的被动探索阈值后，EETC 的经验性能与完全知晓先验的人群主动策略在统计置信区间内高度重叠（如 $T=15000$ 时二者遗憾分别为 $0.33$ 与 $0.31$），证明了非参数估计与动态换轨准则的渐近无损性。
动作维度 $n$ 的扩展会稀释固定预算下的绝对提升：当固定 $k=20, T=10000$ 并将动作数从 $n=5$ 扩展至 $n=30$ 时，所有主动方法依然一致优于被动采样，但由于各单臂老虎机平均样本量缩减，相对增益倍数随 $n$ 上升表现出平缓回落趋势。

亮点与洞察¶

奠定了主动情境上下文老虎机在简单遗憾准则下的极小极大理论基石：指出了直觉上的概率匹配采样 $q_j = p_j$ 绝非简单遗憾的最优分配，首次建立了幂律尺度 $q_j \propto p_j^{2/3}$ 与 $\Theta(k^{1/4})$ 增益上界的闭式解析解。
提出了自适应停时驱动的“先被动再承诺”设计范式：巧妙地利用了“在达到临界干预阈值前，被动数据本身就是成本为零的分布估计源”这一洞察，在不需要人为调参的情况下实现了向最优全主动性能的平滑切换。
其注水截断框架具有极强的跨领域迁移价值：该预算分配数学结构不仅适用于推荐系统中的人群定向投放，亦可直接拓展至联邦学习中非独立同分布（Non-IID）客户端抽样或自适应临床试验中高成本病患亚型的招募决策。

局限与展望¶

当前推导基于极小极大最坏情况视角：模型假设奖励均值差距未知且处于最不利分布。在实际应用中，不同情境下的最优动作识别难度差异悬殊（gap-dependent），未来的算法应能自适应地将采样倾斜至决策边界模糊、识别困难的特定子群体，而非仅依赖情境先验。
情境变量必须在动作执行前可被观测或选择：然而在很多因果推断或事后反馈场景中，上下文特征往往在执行治疗动作后才呈现（post-action context），将其理论界扩展至更为复杂的因果图拓扑仍待深入探索。
算法严重依赖离散有限的情境空间：对于连续型高维上下文特征，当前的离散注水机制必须依赖特征分箱或网格离散化，势必引入不可忽略的离散化误差或维度灾难。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次系统研究了简单遗憾准则下主动选择情境的理论边界，严格证明了 $p_j^{2/3}$ 分配的最优性与 $\Theta(k^{1/4})$ 增益界。
实验充分度: ⭐⭐⭐⭐ 兼顾 MovieLens 真实数据集与极端合成基准，对预算参数、子群规模及候选动作数进行了多维验证，但真实场景规模相对受限。
写作质量: ⭐⭐⭐⭐⭐ 理论推导清晰完备，从全主动到预算受限再到未知分布层层推进，逻辑自洽且定理构造精巧。
价值: ⭐⭐⭐⭐⭐ 为自适应实验设计、受限预算下的群体定向采样及个性化策略评估提供了坚实且极具实用性的理论支撑。

情境规模 \(k\)	理论增益上限 \(R(\mathbf{p})\)	已知 \(\mathbf{p}\) 主动采样相对被动比	EETC 相对被动比	理论与经验吻合度	核心行为说明
\(k=5\)	1.26	1.22 ± 0.04	1.18 ± 0.05	96.8%	稀疏子群获取额外预算，初步拉开差距
\(k=10\)	1.48	1.43 ± 0.05	1.39 ± 0.06	96.6%	随 \(k\) 提升增益单调增加
\(k=20\)	1.76	1.71 ± 0.07	1.65 ± 0.07	97.2%	EETC 逼近已知 \(\mathbf{p}\) 主动上界
\(k=30\)	1.95	1.89 ± 0.08	1.82 ± 0.08	96.9%	经验提升倍数与 \(k^{1/4}\) 严格同步
\(k=40\)	2.10	2.04 ± 0.09	1.96 ± 0.10	97.1%	主动策略简单遗憾仅为被动采样的约 50%