跳转至

Replicable Constrained Bandits

会议: NeurIPS 2026
arXiv: 2602.14580
OpenReview: https://openreview.net/forum?id=bDUTx2VJDq
领域: 其他
关键词: 多臂老虎机, 约束优化, 算法可复制性, UCB算法, 安全探索

一句话总结

本文首次研究了带约束随机多臂老虎机（Constrained MAB）的可复制学习问题，提出基于动态倍增分段与乐观-悲观安全调整的 DEBORA 算法家族，在软约束和硬约束下均实现了与非可复制最优算法一致的 \(\widetilde{\mathcal{O}}(\sqrt{T})\) 遗憾界与约束违规界。

研究背景与动机

随着人工智能系统在科学研究与高敏关键决策场景中的广泛渗透，机器学习研究的可重复性危机日益严峻。算法可复制性（Algorithmic Replicability）作为一种严格的理论框架应运而生：当在线学习算法在相同环境中使用同一内部随机源多次执行时，必须以至少 \(1-\rho\) 的高概率输出完全相同的决策序列。在经典无约束多臂老虎机（MAB）中，前人工作已证明可复制性并非不可企及，但现有方案无一例外高度依赖“臂消除”（Arm Elimination）机制，即在预设的固定分段（Epoch）阶段之间根据经验均值置信区间永久剔除次优动作。

然而，在在线拍卖预算限制、无线通信信道干扰、安全控制等现实决策场景中，学习者不仅需要最大化累计收益，还必须满足多项长期或单轮成本约束。面对带约束的 MAB 问题，现有的臂消除范式遭遇了根本性失效。首先，带约束问题的可行域通常是单纯形内的凸多胞形，最优策略本质上是动作空间上的随机概率分布而非单一确定性臂，臂消除无法直接对连续策略多胞形进行离散筛选；其次，多目标间的固有张力导致置信区间早期的粗糙估计可能将高收益策略误判为不可行，而收益驱动的动作剔除又会过早抹杀构成全局最优安全混合策略的关键基底动作，一旦破坏均匀探索假设，后续即使尝试补救也无法完成严格的理论收敛分析。

本文的切入角度是打破对固定阶段臂消除机制的路径依赖，将多臂老虎机中最经典的“面对不确定性保持乐观”（UCB）原则引入可复制学习。通过将学习进程划分为基于样本量动态倍增触发的非确定性分段，并在每个分段内通过可复制均值估计器构造乐观或保守的安全凸多面体，能够让策略在保持可复制性的同时实现细粒度的自适应探索。核心 idea：抛弃依赖预设分段的臂消除范式，构建基于动作抽样次数动态倍增触发的 UCB 框架 DEBORA；在软约束下通过反转成本置信区间构造乐观安全凸多胞形，在硬约束下借助已知 Slater 严格可行策略进行悲观自适应插值收缩，以极低的可复制性统计代价实现与经典算法同阶的 \(\widetilde{\mathcal{O}}(\sqrt{T})\) 遗憾与安全保证。

方法详解

整体框架

算法的整体输入包含决策轮数 \(T\)、动作总数 \(K\)、约束数量 \(m\)、容许失效率 \(\delta\)、可复制性容差 \(\rho\) 以及内部随机源 \(\xi\)。对于硬约束场景，还需额外输入满足 Slater 条件的严格安全基准策略 \(\bm{x}^\diamond\) 及安全裕度 \(\lambda_{\min}\)。算法将整个学习周期划分为若干动态演进的分段（Epoch），并在每个分段内保持抽样策略固定，以控制向可复制均值估计器（RepMean）查询统计量的总次数。

在每个分段 \(h\) 开始时，算法首先检查观测历史，利用基于网格量化与随机偏移的可复制估计器更新动作的收益和成本统计量；随后根据约束类型确定当前分段的动作选择分布：在无约束设定下直接选取 UCB 指标最大的单臂（DEBORA）；在软约束设定下求解乐观安全多胞形内的线性规划（DEBORA-S）；在硬约束设定下将乐观策略与严格安全策略依据最坏违规风险进行凸组合收缩（DEBORA-H）。当任意被选动作的累计抽样次数达到该分段起始时的两倍时，分段立即终止并触发下一轮策略更新。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["环境输入与随机源 &xi;"] --> B["动态倍增分段控制<br/>监测动作抽样次数是否翻倍"]
    B --> C["可复制均值估计<br/>RepMean 离散网格与随机偏移"]
    C --> D["乐观安全多胞形构建<br/>收益上置信界 + 成本下置信界"]
    D --> E["悲观安全插值收缩<br/>与 Slater 严格安全策略加权凸组合"]
    E -->|硬约束执行| F["安全动作抽样与环境反馈"]
    D -->|软约束执行| F
    F -->|更新抽样计数器| B

关键设计

1. 动态倍增分段机制：摆脱臂消除并控制可复制统计复杂度 针对直接将可复制均值估计器代入标准每轮更新的 UCB1 算法会导致置信界统计复杂度膨胀至 \(K^2 T^2\)、而预设固定分段又无法适应策略概率分布的矛盾，DEBORA 设计了动态倍增分段机制。算法维护动作 \(a\) 在当前分段起始时的抽样次数 \(\widetilde{N}_h(a)\) 以及实时累计抽样次数 \(N_t(a)\)。仅当当前执行动作的抽样计数满足 \(N_t(a) \ge \max\{2\widetilde{N}_h(a), 1\}\) 时，当前分段才宣告结束并进入下一分段 \(h+1\)。 这一设计的关键机制在于：每个动作 \(a\) 的有效抽样次数按几何级数增长（\(1, 2, 4, 8, \dots\)），因此单个动作最多只能触发 \(\lceil \log_2 T \rceil\) 次分段切换，总分段数被严格约束在 \(H \le K \lceil \log_2 T \rceil\) 阶之内。在每个分段更新时，仅对抽样发生翻倍的动作重新调用 RepMean 计算置信宽度为 \(\bm{\zeta}_h(a) = \sqrt{\frac{2\ln(2/\delta')}{\max\{\widetilde{N}_h(a), 1\}(\rho'-2\delta')^2}}\) 的估计值，其余动作复用历史估计。这既保证了在两次独立运行中分段转移点与策略选择高度一致（联合并界失效率被严格平摊），又免去了传统算法永久删除动作带来的不可逆信息损失。

2. 乐观安全多胞形构建：解决多目标张力下的混合策略优化 在带有 \(m\) 个成本约束 \(\bm{g}_i^\top \bm{x} \le \alpha_i\) 的软约束场景中，真实最优解 \(\bm{x}^\star\) 通常是落在单纯形边界上的非均匀混合分布。针对经验过滤容易过早排除最优混合基底的痛点，DEBORA-S 在每个分段利用可复制成本估计量 \(\widehat{\bm{g}}_{h,i}\) 及其置信半径 \(\bm{\zeta}_h\) 构造乐观安全决策空间： $\(\underline{\mathcal{X}}_h = \left\{\bm{x} \in \Delta_K \;\middle|\; (\widehat{\bm{g}}_{h,i} - \bm{\zeta}_h)^\top \bm{x} \le \alpha_i, \quad \forall i \in [m]\right\}\)$ 算法在 \(\underline{\mathcal{X}}_h\) 内寻找使乐观收益 \((\widehat{\bm{r}}_h + \bm{\zeta}_h)^\top \bm{x}\) 最大化的策略 \(\bm{x}_h^\circ\)。由于减去了置信半径 \(\bm{\zeta}_h\)，在干净事件 \(\mathcal{E}\) 下必定满足 \((\widehat{\bm{g}}_{h,i} - \bm{\zeta}_h)^\top \bm{x}^\star \le \bm{g}_i^\top \bm{x}^\star \le \alpha_i\)，从而以不低于 \(1-\delta\) 的概率保证真实最优安全策略 \(\bm{x}^\star\) 始终包含在可行域 \(\underline{\mathcal{X}}_h\) 之中。随着分段推进与样本累积，\(\bm{\zeta}_h\) 逐步收缩，可行域单调逼近真实安全多胞形 \(\mathcal{X}^\star\)，使得累计正向约束违规 \(V_T\) 与累计遗憾 \(R_T\) 能够同步收敛在 \(\widetilde{\mathcal{O}}(\sqrt{T})\) 速率。

3. 悲观安全插值收缩：利用 Slater 锚点实现硬约束每轮零违规 在硬约束设定下，单纯的乐观策略可能在探索初期或凸多胞形顶点处发生瞬间违规，这在安全关键系统中是绝对不可接受的。DEBORA-H 在假设已知满足 Slater 条件的严格安全策略 \(\bm{x}^\diamond\)（满足 \(\bm{g}_i^\top \bm{x}^\diamond \le \alpha_i - \lambda_i\)，其中 \(\lambda_{\min} = \min_i (\alpha_i - \lambda_i) > 0\)）的前提下，引入了悲观安全违规检测与自适应插值收缩机制。算法首先识别出在最坏置信界下存在违规风险的约束集合 \(\mathcal{V}_h = \{i \in [m] \mid (\widehat{\bm{g}}_{h,i} + \bm{\zeta}_h)^\top \widetilde{\bm{x}}_h > \alpha_i\}\)，并计算保守插值系数： $\(\sigma_h = \max_{i \in \mathcal{V}_h} \frac{\min\{(\widehat{\bm{g}}_{h,i} + \bm{\zeta}_h)^\top \widetilde{\bm{x}}_h, 1\} - \alpha_i}{\min\{(\widehat{\bm{g}}_{h,i} + \bm{\zeta}_h)^\top \widetilde{\bm{x}}_h, 1\} - \alpha_i + \lambda_i}\)$ 若 \(\mathcal{V}_h = \emptyset\) 则置 \(\sigma_h = 0\)。随后执行混合策略 \(\bm{x}_h^\star = \sigma_h \bm{x}^\diamond + (1-\sigma_h) \widetilde{\bm{x}}_h\)。该机制巧妙地利用了严格安全策略提供的安全边界裕度 \(\lambda_i\)，通过凸组合抵消最坏情况下的潜在违规量，从数学上严格锁定了每轮预期成本 \(\bm{g}_i^\top \bm{x}_t \le \alpha_i\) 恒成立，同时将插值带来的收益回退损失控制在与置信宽度同阶的渐近界限内。

损失函数 / 训练策略

作为纯在线学习与赌博机算法，本方案无需反向传播梯度训练，其核心优化策略体现在每分段求解的有界线性规划（LP）及置信参数的严密分配： - 可复制参数离散化：各分段调用的 RepMean 采用随机量化网格，网格单元宽度设为 \(\alpha = \frac{2\delta'}{1+\rho'-2\delta'}\)，网格偏移量 \(\alpha_{\text{off}} \sim \mathcal{U}([0, \alpha])\) 严格由共享随机源 \(\xi\) 生成。样本均值归入区间后取中点作为估计值，确保两次独立运行落入同一区间的概率下界为 \(1-\rho'\)。 - 误差预算分配准则：在 DEBORA 中，单个估计器的参数分配为 \(\delta' = \frac{\delta}{2K \lceil\log_2 T\rceil}\)，\(\rho' = \frac{\rho}{2K \lceil\log_2 T\rceil}\)；在引入约束的 DEBORA-S 和 DEBORA-H 中，由于每分段需估计 \(K(m+1)\) 个统计量，参数进一步细分缩放为 \(\delta' = \frac{\delta}{2(m+1)K^2 \lceil\log_2 T\rceil}\) 和 \(\rho' = \frac{\rho}{2(m+1)K^2 \lceil\log_2 T\rceil}\)，使得在整个时间跨度内的总失效率受控于 \(\delta\)，整体可复制性满足 \(\ge 1-\rho\)。

实验关键数据

主实验

论文对所提出的三种算法（DEBORA、DEBORA-S、DEBORA-H）给出了完备的理论上界证明，并与现有的代表性无约束可复制算法（Esfandiari et al., 2022; Komiyama et al., 2024）以及非可复制经典带约束老虎机算法（Pacchiano et al., 2021; Efroni et al., 2020）进行了理论保证对比。

算法设定 代表方法 可复制性保证 累计遗憾界 \(R_T\) 约束违规界 \(V_T\) 分段策略机制
无约束 MAB Alg. 1 (Esfandiari et al., 2022) \(\rho\)-可复制 \(\widetilde{\mathcal{O}}\left(\frac{K^2}{(\rho-\delta)^2} \sum \frac{1}{\Delta(a)}\right)\) 不适用 固定分段臂消除
无约束 MAB RSE (Komiyama et al., 2024) \(\rho\)-可复制 \(\widetilde{\mathcal{O}}\left(\sum \frac{\ln T}{\Delta(a)} + \frac{K^2 \ln \ln T}{\rho^2 \Delta(a)}\right)\) 不适用 固定分段臂消除
无约束 MAB DEBORA (本文) \(\rho\)-可复制 \(\widetilde{\mathcal{O}}\left(\frac{K \sqrt{KT \log(1/\delta)}}{\rho-\delta}\right)\) (高概率) 不适用 动态倍增 UCB (免消除)
软约束 MAB OptPess-LP (Efroni et al., 2020) 非可复制 \(\widetilde{\mathcal{O}}(m \sqrt{K T})\) \(\widetilde{\mathcal{O}}(m \sqrt{K T})\) 离线凸规划 / 椭球法
软约束 MAB DEBORA-S (本文) \(\rho\)-可复制 \(\widetilde{\mathcal{O}}\left(\frac{m K^2 \sqrt{KT} \log(1/\delta)}{\rho-2\delta}\right)\) \(\widetilde{\mathcal{O}}\left(\frac{m K^2 \sqrt{KT} \log(1/\delta)}{\rho-2\delta}\right)\) 乐观安全多胞形 LP
硬约束 MAB Conservative UCB (Pacchiano et al., 2021) 非可复制 \(\widetilde{\mathcal{O}}\left(\frac{m \sqrt{K T}}{\lambda_{\min}}\right)\) 0 (每轮高概率满足) 悲观收缩探索
硬约束 MAB DEBORA-H (本文) \(\rho\)-可复制 \(\widetilde{\mathcal{O}}\left(\frac{m K^2 \sqrt{KT} \log(1/\delta)}{\lambda_{\min}(\rho-2\delta)} + \gamma\right)\) 0 (每轮高概率满足) Slater 锚点悲观插值

消融实验

为验证各核心组件在解决带约束问题中的不可替代性，下表对设计空间进行了模块剥离与理论性质分析。

配置变体 可复制性 支持约束多胞形 单轮硬安全性 理论遗憾复杂度 核心瓶颈 / 失败机理
经典 UCB1 + 纯统计替换 \(\rho\)-可复制 否 否 \(\widetilde{\mathcal{O}}(K^2 T^2)\) (统计发散) 每轮均验证置信区间导致联合并界过大
预设固定分段 + 臂消除 \(\rho\)-可复制 否 否 线性遗憾 \(\mathcal{O}(T)\) 无法优化连续策略多胞形，易过早剔除最优混合基底
动态倍增 UCB (仅 DEBORA) \(\rho\)-可复制 否 否 \(\widetilde{\mathcal{O}}(\frac{1}{\rho-\delta} K^{1.5} \sqrt{T})\) 仅处理单一收益目标，无约束感知能力
DEBORA-S (移除悲观插值) \(\rho\)-可复制 是 否 (存在瞬时正违规) \(\widetilde{\mathcal{O}}(\frac{m K^2 \sqrt{KT}}{\rho-2\delta})\) 乐观决策常落于边界，初期及拐点处违反硬安全约束
DEBORA-H (完整模型) \(\rho\)-可复制 是 是 (以 \(\ge 1-\delta\) 恒成立) \(\widetilde{\mathcal{O}}\left(\frac{m K^2 \sqrt{KT}}{\lambda_{\min}(\rho-2\delta)}\right)\) 兼具 UCB 自适应性、多胞形求解与严格单轮安全性

关键发现

  • 可复制性无需牺牲多项式时间率：在带约束赌博机中，要求算法满足跨运行强可复制性，不会改变关于决策周期 \(T\) 的增长阶数。软约束下的遗憾与违规界、硬约束下的安全遗憾界均保持了理论最优的 \(\widetilde{\mathcal{O}}(\sqrt{T})\) 依赖。
  • 对 \(1/\rho\) 与 \(1/\lambda_{\min}\) 依赖的本质必要性：理论分析明确表明，遗憾界中对可复制性公差的反比例因子 \(1/\rho\)（与 Ahmadi et al., 2024 一致）以及对 Slater 安全裕度的反比例因子 \(1/\lambda_{\min}\)（与 Stradi et al., 2025b 一致）属于该类问题的理论下界，无法通过算法调优被完全消除。
  • 动态分段避免了不可逆误差累积：相较于预设固定周期的批处理方法，以 \(N_t(a) \ge \max\{2\widetilde{N}_h(a), 1\}\) 作为事件驱动的触发条件，使动作探索自然匹配各臂的方差衰减速率，分段总数自适应收敛至对数阶 \(K \log_2 T\)。

亮点与洞察

  • 首个免消除的可复制 UCB 范式：首次将经典面对不确定性保持乐观的 UCB 机制成功移植至可复制赌博机领域，打破了已有理论工作普遍认为可复制性必须依赖臂消除（Arm Elimination）的思维定势。
  • 乐观与悲观的双轨协调设计：在软约束中反转置信符号构造扩张可行域（乐观），在硬约束中引入 Slater 锚点执行阻尼收缩（悲观），两种几何操作统一在动态分段框架下，为受限环境下的连续策略优化提供了标准模板。
  • 极强的拓展迁移潜力：基于动态倍增分段的 UCB 结构不假设动作集合的单调递减性，为未来将可复制在线学习推广至非平稳（Non-Stationary）赌博机、上下文赌博机（Contextual Bandits）及受限强化学习（Constrained MDPs）奠定了理论基础。

局限与展望

  • 动作数量与约束数量的维度依赖较强：当前遗憾界包含 \(K^2 \sqrt{K}\) 和 \(m\) 的因子，在动作空间极大或超高维约束场景下，统计复杂度和在线线性规划的计算开销将显著增加。
  • 硬约束严重依赖已知的 Slater 锚点：DEBORA-H 必须预先获知严格可行的策略 \(\bm{x}^\diamond\) 及其安全裕度 \(\lambda_{\min}\)；在完全未知的极端未知环境中，若无法提供先验可行起点，则难以在初始阶段保证硬安全。
  • 未来改进方向：可进一步探索如何通过方差自适应或矩阵集中不等式将动作维数依赖降低至 \(\widetilde{\mathcal{O}}(\sqrt{K})\)，以及研究在缺乏先验安全锚点时通过二阶段纯探索寻找近似 Slater 策略的可行性。

相关工作与启发

  • vs Esfandiari et al. (2022) [Replicable Bandits]：前人奠定了可复制赌博机基础，但依赖固定分段与动作永久消除，只能处理无约束单目标离散臂选择；本文通过动态倍增分段提出首个可复制 UCB 算法，并推广至含多约束的多胞形决策。
  • vs Komiyama et al. (2024) [Replicability is Asymptotically Free in MAB]：前人通过 RSE 算法解耦了常规遗憾与可复制项，但同样基于臂消除且未涉及约束；本文在免臂消除的前提下实现了高概率遗憾保证与约束适配。
  • vs Pacchiano et al. (2021) [Stochastic Bandits with Linear Constraints]：前人提出了经典非可复制硬约束保守 UCB 算法；本文在其理论极限之上引入可复制机制，证明了硬约束零违规与可复制性可以完全兼容且不劣化 \(T\) 的渐近收敛率。

评分

  • 新颖性: ⭐⭐⭐⭐⭐ 开创了带约束在线学习的可复制性理论，提出首个免臂消除的可复制 UCB 框架。
  • 实验充分度: ⭐⭐⭐⭐☆ 理论推导完备扎实，覆盖无约束、软约束和硬约束全场景并附完整测度集中证明。
  • 写作质量: ⭐⭐⭐⭐⭐ 动机阐述深刻透彻，算法流程与几何直觉清晰，数学记号严谨自洽。
  • 价值: ⭐⭐⭐⭐⭐ 为解决高敏、安全关键场景下 AI 算法的可重复性危机提供了坚实的理论基石。

相关论文