Managing Self-Learning Experts under Per-Round Budget Constraints¶

会议: NeurIPS 2026
arXiv: 2510.22654
代码: https://github.com/ooaarg/mlcb-code
领域: 强化学习
关键词: 在线决策, 专家管理, 自学习专家, 预算约束, 置信界

一句话总结¶

针对有限训练预算下管理多个自适应学习专家的在线决策难题，本文提出 M-LCB 元算法，通过“下置信界（LCB）乐观分配训练资源、上置信界（UCB）保守选取执行决策”的双动作解耦机制，实现了极小化极大最优的累积遗憾界 $\tilde{O}(\sqrt{KT/M} + (K/M)^{1-\alpha}T^{\alpha})$。

研究背景与动机¶

在现代工业级在线推荐、广告竞价以及高频交易系统中，平台通常在后台维持着由多个自适应算法组成的专家候选池（如不同的强化学习策略、上下文多臂老虎机或参数化在线学习模型）。尽管系统在影子模式（Shadow Mode）下可以记录所有候选模型针对真实用户反馈所产生的损失，但计算资源与训练基础设施的吞吐量极其有限，每个决策轮次通常仅允许反向传播或增量更新至多 $M$ 个模型（$M \leq K$）。这要求系统运营者必须在每轮做出双重抉择：既要部署一个当下表现足够稳健的模型对外服务以控制即时业务损失，又要决定将有限的 $M$ 个更新配额投资给哪些最有潜力的专家，使其在未来迭代中逼近全局最优。

传统的多臂老虎机（MAB）算法通常假设各臂具有静态或对抗性的奖励分布，无法建模专家性能随训练轮数增加而单调提升的内生学习动态；而经典的专家聚合与模型选择方法（如 EXP3.P、CORRAL 或 Dynamic Balancing）往往要求完全信息反馈，或者受限于每轮仅能更新单一专家的严苛假设，其遗憾界关于候选专家数 $K$ 的扩展性无法直接适应批处理并发训练场景。如果盲目套用传统 UCB 准则直接选择单臂执行并更新，极易陷入恶性循环：早熟收敛但上限较低的次优专家会因为初期方差小而被过度开发，而收敛速度较慢但理论极限更优的复杂专家则会因缺乏训练预算而长期处于高不确定性状态，最终导致严重的次优陷阱。

解决该问题的核心矛盾在于训练资源分配的前瞻探索性与外部决策执行的即时保守性之间的目标脱节。分配训练预算本质上是在投资未来，需要对潜在最优的专家保持乐观；而对外执行决策则直接产生系统损耗，必须尽可能保守以规避未充分训练模型带来的高方差风险。核心 idea：将每轮的决策动作严格解耦为“训练子集分配”与“外部执行顾问选取”，提出 M-LCB 机制——利用自学习专家的结构化遗憾包络构建下置信界（LCB）以乐观贪心挑选前 $M$ 个最具潜力的训练专家，并在入选集合中依据上置信界（UCB）保守选取当期决策顾问，配合平滑包装器达成兼顾前瞻学习与稳健部署的最优平衡。

方法详解¶

整体框架¶

M-LCB 算法在每个离散轮次 $t = 1, \dots, T$ 维护一个由 $K$ 个自学习专家组成的候选池。每个专家 $k \in [K]$ 对应一个决策子空间 $\mathbf{U}_k \subseteq \mathbf{U}$，其内部学习动态满足任意时刻（Anytime）遗憾上界假设 $R_k(t) \leq U_k(n_k^t, \delta)$（其中 $n_k^t$ 为专家 $k$ 历史累计获得的训练更新次数）。在每一轮中，元算法首先依据各专家的历史损失与置信半径计算下置信界 $\text{LCB}_k(t, \delta)$ 与上置信界 $\text{UCB}_k(t, \delta)$；随后挑选出拥有最小 $\text{LCB}$ 的 $M$ 个专家构成训练集 $S_t$，并在 $S_t$ 中选取具有最小 $\text{UCB}$ 的专家作为本轮顾问 $i_t$；接着通过平滑包装器生成全局决策 $u^t$，承受外部环境反馈的损失，并仅针对集合 $S_t$ 内的专家分发真实损失以执行内部参数更新。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}, 'subGraphTitleMargin': {'top': 8, 'bottom': 16}}}%%
flowchart TD
    A["候选专家状态与历史累计损失<br/>n_k^t 次更新历史与损失 L_k(t)"] --> B["双置信界显式计算<br/>LCB 评估潜在最优 / UCB 评估当期风险"]
    B --> C["训练预算分配：前 M 个最小 LCB<br/>确定训练子集 S_t (|S_t| <= M)"]
    C --> D["决策顾问选取：S_t 中最小 UCB<br/>锁定最稳健执行专家 i_t in S_t"]
    D --> E["平滑决策包装器<br/>历史动作聚合生成全局决策 u^t"]
    E --> F["环境交互与损失暴露<br/>执行 u^t，观察环境状态并计算各模型损失"]
    F --> G["解耦式参数增量更新<br/>仅对 S_t 内专家执行梯度或策略步"]

关键设计¶

1. 双置信界解耦评估：分离潜在收益探索与即时执行风险

传统算法在处理探索与利用时通常使用单一指标打分，导致无法同时兼顾长期价值投资与短期执行安全。针对这一痛点，M-LCB 将置信界明确拆分为针对专家内在最优损失 $L_k^\star$ 的下置信界 $\text{LCB}_k(t, \delta)$ 与针对即时预期损失的上置信界 $\text{UCB}_k(t, \delta)$。对于已知具有任意时刻遗憾上界 $U_k(n, \delta)$ 的基学习器，置信区间定义为： $$ \text{LCB}k(t, \delta) := L_k(t) - \frac{U_k(n_k^t, \delta}})}{n_k^t}, \quad \text{UCBk(t, \delta) := L_k(t) + \sqrt{\frac{2\log(1/\delta $$ 其中 })}{n_k^t}$L_k(t) := \frac{1}{n_k^t}\sum_{\tau \in I_k(t)} \ell(u_k^\tau, \xi^\tau)$ 为专家 $k$ 在其所有更新轮次上的经验平均损失。$\text{LCB}_k$ 减去了由算法结构理论界保证的向后收敛半径，刻画了该专家在完全收敛后所能达到的极限最优性能下潜空间，值越小代表该专家越有希望成为全局最优模型；而 $\text{UCB}_k$ 加上了鞅集中不等式给出的向前泛化半径，刻画了该专家当前策略在最坏情况下的即时损失上界。

2. 训练与部署双动作选取机制：乐观投资预算、保守对外服务

在确定了各专家的置信区间后，元算法必须在严格的每轮 $M$ 次计算预算约束下做决策。针对次优专家早期因方差较小而抢占计算资源的问题，M-LCB 采取“双重贪心”策略： $$ S_t := \arg\min_{\substack{S \subseteq [K] \ |S| = M}} \sum_{k \in S} \text{LCB}k(t, \delta), \quad i_t := \arg\min_k(t, \delta) $$ 首先，训练集 } \text{UCB$S_t$ 直接选取全池中 $\text{LCB}$ 最小的 $M$ 个专家。这一步充分体现了对未充分训练专家的乐观态度——即使某个高级别复杂模型当期经验损失较高，只要其更新次数 $n_k^t$ 较小导致探索奖励项 $U_k/n_k^t$ 足够大，其 $\text{LCB}$ 便会被压得很低，从而强制系统向其分配宝贵的 GPU 训练配额，有效规避了次优陷阱。其次，在最终对外提供预测服务的顾问选择上，算法将候选范围严格限定在已入选训练集 $S_t$ 的 $M$ 个专家之中，并挑选出 $\text{UCB}$ 最低的专家 $i_t$。由于 $\text{UCB}$ 在高概率下严格上界化了平滑决策的真实期望损失，这种设计保证了对外暴露的业务风险被压制在当期可行范围内的最低点。

3. 平滑包装器与自归一化置信收紧：化解点收敛缺失并消除松弛

在非凸或随机在线优化过程中，基专家的参数并不一定保证逐点收敛（Pointwise Convergence），若直接输出单点动作可能引发剧烈震荡。M-LCB 引入平滑包装器（Smoothing Wrapper）$\upsilon$，将专家 $i_t$ 历史生成决策集合 $H_{i_t}^t := \{u_{i_t}^\tau : \tau \in I_{i_t}(t)\}$ 映射为全局动作 $u^t$。在凸损失与凸决策空间下，平滑包装器退化为历史轨迹的简单算术平均 $u^t = \frac{1}{|I_{i_t}(t)|} \sum_{\tau} u_{i_t}^\tau$，依据 Jensen 不等式自然满足凸期望界；而在非凸连续空间下，则采用在历史轨迹中均匀抽样候选动作的随机平滑方案，使得条件期望损失满足 $\mathbb{E}_{u \sim \upsilon(H)}[L(u) \mid H] \leq \frac{1}{|H|} \sum_{\tau \in H} L(u^\tau)$。进一步地，针对在线凸优化（OCO）类型的参数化专家，论文引入了基于自归一化过程（Self-Normalized Processes）的方差自适应经验置信界，利用经验补偿项替换粗糙的 Hoeffding 展开，在实际运行中进一步收紧了 $\text{LCB}$ 与 $\text{UCB}$，避免了常数膨胀对收敛速度的负面影响。

损失函数 / 训练策略¶

M-LCB 的元层并不直接参与底层模型梯度的反向传播，而是作为调度控制器协调各基专家的状态更新。 - 冷启动初始化：在主循环开始前，算法对每个候选专家 $k \in [K]$ 强制分配一次单步更新，确保在进入自适应阶段时所有专家的更新计数均满足 $n_k^t \geq 1$，从而保证置信界分母有定义。这一过程仅消耗 $K$ 个样本步骤，对长程渐近遗憾的影响为 $O(K)$ 常数级。 - 高概率置信度分配：置信参数 $\delta \in (0, 1)$ 在不同集中项间进行几何级数分配：单臂任意时刻包络分配 $\delta_{\text{arm}} = \frac{\delta}{2K}$，鞅集中不等式的时间衰减置信参数设定为 $\delta_n = \frac{\delta}{3.5 K n^2}$，利用 Basel 级数 $\sum_{n=1}^\infty \frac{1}{n^2} = \frac{\pi^2}{6} < 2$ 保证在全时间步和全专家空间上做 Union Bound 时总失误概率不超过 $\delta$。 - 参数解耦更新：在轮次 $t$ 观察到环境反馈 $\xi^t$ 后，仅对集合 $S_t$ 内的专家分派损失。若底层为在线梯度下降（OGD）专家，则其执行参数投影更新 $w_k^{\tau+1} = \Pi_{\mathbf{W}_k}[w_k^\tau - \eta_\tau \nabla_w \ell(f_k(w_k^\tau, x_t), y_t)]$；若底层为老虎机专家（如 UCB1），则刷新对应臂的计数与经验平均回报。不在 $S_t$ 内的专家保持冻结，其内部计数与参数完全不变。

实验关键数据¶

主实验：理论遗憾界对比与合成环境评估¶

论文针对专家单体具有 $O(\beta_k n^\alpha)$ 遗憾的泛化设定，严格推导了 M-LCB 的最坏情况累积遗憾界与极小化极大下界，并在包含 $K=10$ 个多臂老虎机专家（前 5 个为 $\epsilon$-Greedy，后 5 个为 UCB1，构建了次优收敛陷阱）的合成环境以及真实医疗临床数据集上进行了评测。

算法 / 比较基准	专家自学习支持	多臂并发更新支持	Top-$M$ 子集多重播放	累积遗憾上界（忽略对数因子）	极小极大最优性匹配
CORRAL + Smoothing Wrapper [26]	是	否 ($M=1$)	否	$\tilde{O}(\sqrt{KT} + K^\alpha T^{1-\alpha} + K^{1-\alpha} T^\alpha)$	否（受限于单臂更新）
EXP3.P + Smoothing Wrapper [26]	是	否 ($M=1$)	否	$\tilde{O}(\sqrt{KT} + K^{\frac{1-\alpha}{2-\alpha}} T^{\frac{1}{2-\alpha}})$	否
Dynamic Balancing [12]	是	否 ($M=1$)	否	$\tilde{O}(\sqrt{KT} + K^{1-\alpha} T^\alpha)$	否
Prediction with Limited Advice [28]	否（静态专家）	是 ($M \leq K$)	否	$\tilde{O}(\sqrt{\frac{KT \log K}{M}})$	仅在静态场景下匹配
H-INF [34]	否（静态专家）	是 ($M \leq K$)	否	$\tilde{O}(\max\{\sqrt{KT/M}, \sqrt{T \log K}\})$	仅在静态场景下匹配
M-LCB (本文)	是	是 ($M \leq K$)	是	$\tilde{\mathbf{O}}\left(\sqrt{\frac{\mathbf{K}\mathbf{T}}{\mathbf{M}}} + \left(\frac{\mathbf{K}}{\mathbf{M}}\right)^{1-\alpha} \mathbf{T}^{\alpha}\right)$	是（严格匹配定理2下界）

消融与代表性基学习器扩展分析¶

论文详细分析了当基专家实例化为不同优化算法和统计物理环境时，M-LCB 诱导出的全局遗憾表现。定义广义复杂度范数 $\|\boldsymbol{\beta}\|_{M, \gamma} := \left(\frac{1}{M}\sum_{k=1}^K \beta_k^{1/\gamma}\right)^\gamma$：

基学习器类型 / 问题环境	单体专家收敛率 $U_k(n, \delta)$	收敛阶数 $\alpha$	M-LCB 全局累积遗憾界（忽略对数与 $\sqrt{\frac{KT}{M}}$ 共享项）	关键机制与瓶颈参数
凸 Lipschitz OGD / OMD	$O(G_k R_k \sqrt{n})$	$\frac{1}{2}$	$O(T^{1/2} \\|GD\\|_{M, 1/2})$	梯度有界 $G_k$、参数域直径 $R_k$
有界 Bandit 凸优化 (BCO) [18]	$O(C_k d_k n^{5/6})$	$\frac{5}{6}$	$O(T^{5/6} \\|Cd\\|_{M, 1/6})$	维度 $d_k$、单点无梯度扰动估计
Lipschitz Bandit 凸优化 [18]	$O(\sqrt{C_k L_k R_k} d_k n^{3/4})$	$\frac{3}{4}$	$O(T^{3/4} \\|\sqrt{CLR}d\\|_{M, 1/4})$	局部 Lipschitz 连续性加速收敛
重尾随机老虎机 (矩指数 $\varepsilon$) [6]	$\tilde{O}(n^\alpha N_k^{1-\alpha})$	$\frac{1}{1+\varepsilon}$	$O\left(T^\alpha \left[\frac{1}{M}\sum_{k=1}^K N_k\right]^{1-\alpha}\right)$	极端噪声阶数 $\mathbb{E}[\\|X\\|^{1+\varepsilon}] \leq \sigma^{1+\varepsilon}$
对称重尾老虎机 [15]	$O(\sqrt{N_k n} \log^{3/2} n)$	$\frac{1}{2}$	$O\left(T^{1/2} \left[\frac{1}{M}\sum_{k=1}^K N_k\right]^{1/2}\right)$	截断中位数与自归一化均值修正
Hedge / 指数权重算法	$O(\sqrt{n \log N_k})$	$\frac{1}{2}$	$O(T^{1/2} \\|\sqrt{\log N}\\|_{M, 1/2})$	离散动作基元数 $N_k$ 的对数依赖

真实数据实证结果（华法林剂量预测与胎儿监护分析）¶

在华法林药物剂量预测基准（IWPC Warfarin，5528 例样本，93 维特征，3 分类，自举扩展至 $T=20,000$ 步，$K=7$ 个异构在线模型）中： - 当设定每轮更新预算 $M=2$ 时，M-LCB 累积损失为 6,604，极度贴近事后固定的全局单一最优专家的理论极限 6,589，显著优于 LimitedAdvice、RoundRobin 与 SmoothCORRAL。 - 当固定 $M=2$ 并将专家规模从 $K=7$ 逐步扩展至 $K=10$ 和 $K=15$ 时，经验遗憾的扩展斜率严格符合理论预期的 $O(\sqrt{KT/M})$ 规律。 - 在心宫监护数据集（Cardiotocography，真实非自举数据流，$K=15$ 个专家）上，当计算预算提升至 $M \geq 4$ 时，M-LCB 的 Top-$M$ 子集平均遗憾迅速收敛归零，平均预测准确率达到 95.0%（累积损失 105.6，逼近最优固定子集的 86.0），直接证实了多重播放泛化定理（Theorem 3）的有效性。

关键发现¶

预算边际递减效应：随着每轮训练预算 $M$ 从 1 增加到 4，M-LCB 锁定最佳专家的收敛速度呈现亚线性加速，验证了遗憾界中 $(K/M)$ 因子的主导作用。
免受次优陷阱干扰：在合成实验中，收敛快的低质量 $\epsilon$-Greedy 专家在初期会短暂占据主导，但随着其经验损失触底且置信半径收窄，M-LCB 能够平滑切换并将训练配额全面倾斜至上限更高的 UCB1 专家，而静态分配策略（如 LimitedAdvice）则会在次优专家上持续浪费预算。
对超参数的高度鲁棒性：网格搜索表明，置信缩放因子 $c$ 在跨越三个数量级（$[0.05, 1.0]$）时，累积遗憾的变动均保持在两个标准误差之内，证实了基于结构遗憾的置信界不需要繁琐微调。

亮点与洞察¶

解耦式探索-利用设计：彻底打破了传统多臂老虎机中“打分最高者同时负责执行与更新”的惯性思维，开创性地使用 LCB 进行前瞻性预算投资、使用 UCB 进行保守性部署，从数学根源上消除了内生自学习专家的次优陷阱。
紧凑严谨的匹配界理论证明：论文不仅给出了高概率遗憾上界，还基于重尾分布与信息论相对熵技巧构建了匹配的极小极大下界 $\Omega(\sqrt{KT/M} + (K/M)^{1-\alpha} T^\alpha)$，严格界定了预算约束下多智能体自学习管理的理论极限。
向 Top-$M$ 多重播放的天然泛化：算法本身无需改动，仅通过修改评估指标即可直接扩展到组合式多重播放场景，并保证子集平均遗憾达到同等阶数的最优速率，展现了极强的泛化潜能。

局限与展望¶

依赖已知的遗憾缩放函数：理论推导假设专家的理论收敛包络 $c(\delta)$ 为先验已知常数或已知阶数，在基模型内部黑盒结构完全不可知或超参数失配时，置信界可能会出现一定程度的松弛或过度探索。
缺乏与上下文特征的深度耦合：当前 M-LCB 假定专家在全空间或静态子空间上竞争，未建立上下文依赖的局部胜任力模型（Contextual Specialization），未来可进一步扩展至情境多臂老虎机（Contextual Bandits）与多专家门控网络场景。
离线策略重加权未纳入标准证明：在完全部分可观测（Partial Feedback）场景下，未入选训练的专家无法直接获得真实标签，虽然可通过逆倾向得分加权（IPS）等反事实评估方法补充，但会导致置信半径膨胀，其统一理论框架仍有待进一步完善。

基学习器类型 / 问题环境	单体专家收敛率 \(U_k(n, \delta)\)	收敛阶数 \(\alpha\)	M-LCB 全局累积遗憾界（忽略对数与 \(\sqrt{\frac{KT}{M}}\) 共享项）	关键机制与瓶颈参数
凸 Lipschitz OGD / OMD	\(O(G_k R_k \sqrt{n})\)	\(\frac{1}{2}\)	\(O(T^{1/2} \\|GD\\|_{M, 1/2})\)	梯度有界 \(G_k\)、参数域直径 \(R_k\)
有界 Bandit 凸优化 (BCO) [18]	\(O(C_k d_k n^{5/6})\)	\(\frac{5}{6}\)	\(O(T^{5/6} \\|Cd\\|_{M, 1/6})\)	维度 \(d_k\)、单点无梯度扰动估计
Lipschitz Bandit 凸优化 [18]	\(O(\sqrt{C_k L_k R_k} d_k n^{3/4})\)	\(\frac{3}{4}\)	\(O(T^{3/4} \\|\sqrt{CLR}d\\|_{M, 1/4})\)	局部 Lipschitz 连续性加速收敛
重尾随机老虎机 (矩指数 \(\varepsilon\)) [6]	\(\tilde{O}(n^\alpha N_k^{1-\alpha})\)	\(\frac{1}{1+\varepsilon}\)	\(O\left(T^\alpha \left[\frac{1}{M}\sum_{k=1}^K N_k\right]^{1-\alpha}\right)\)	极端噪声阶数 \(\mathbb{E}[\\|X\\|^{1+\varepsilon}] \leq \sigma^{1+\varepsilon}\)
对称重尾老虎机 [15]	\(O(\sqrt{N_k n} \log^{3/2} n)\)	\(\frac{1}{2}\)	\(O\left(T^{1/2} \left[\frac{1}{M}\sum_{k=1}^K N_k\right]^{1/2}\right)\)	截断中位数与自归一化均值修正
Hedge / 指数权重算法	\(O(\sqrt{n \log N_k})\)	\(\frac{1}{2}\)	\(O(T^{1/2} \\|\sqrt{\log N}\\|_{M, 1/2})\)	离散动作基元数 \(N_k\) 的对数依赖

算法 / 比较基准	专家自学习支持	多臂并发更新支持	Top-\(M\) 子集多重播放	累积遗憾上界（忽略对数因子）	极小极大最优性匹配
CORRAL + Smoothing Wrapper [26]	是	否 (\(M=1\))	否	\(\tilde{O}(\sqrt{KT} + K^\alpha T^{1-\alpha} + K^{1-\alpha} T^\alpha)\)	否（受限于单臂更新）
EXP3.P + Smoothing Wrapper [26]	是	否 (\(M=1\))	否	\(\tilde{O}(\sqrt{KT} + K^{\frac{1-\alpha}{2-\alpha}} T^{\frac{1}{2-\alpha}})\)	否
Dynamic Balancing [12]	是	否 (\(M=1\))	否	\(\tilde{O}(\sqrt{KT} + K^{1-\alpha} T^\alpha)\)	否
Prediction with Limited Advice [28]	否（静态专家）	是 (\(M \leq K\))	否	\(\tilde{O}(\sqrt{\frac{KT \log K}{M}})\)	仅在静态场景下匹配
H-INF [34]	否（静态专家）	是 (\(M \leq K\))	否	\(\tilde{O}(\max\{\sqrt{KT/M}, \sqrt{T \log K}\})\)	仅在静态场景下匹配
M-LCB (本文)	是	是 (\(M \leq K\))	是	\(\tilde{\mathbf{O}}\left(\sqrt{\frac{\mathbf{K}\mathbf{T}}{\mathbf{M}}} + \left(\frac{\mathbf{K}}{\mathbf{M}}\right)^{1-\alpha} \mathbf{T}^{\alpha}\right)\)	是（严格匹配定理2下界）