在预算有限时动态选择最优学习算法,实现高效自适应决策。
UCB-type Algorithm for Budget-Constrained Expert Learning
- 设计了基于置信区间的新算法,直接利用实际损失计算,无需额外优化。
- 理论证明:在每轮最多训练M个专家条件下,整体误差增长为√(KT/M) + (K/M)^(1-α)T^α。
- 适用于在线模型选择、金融策略切换等资源受限场景,特别适合自学习智能体协同。
在许多现代应用中,系统需在多个自适应学习算法间动态选择,以应对流式数据、金融交易策略切换或多个上下文老虎机/强化学习代理的协调问题。每轮只能选择一个预测器进行预测,并在固定训练预算下最多更新其中 M ≤ K 个专家。本文在随机设定下提出 exttt{M-LCB} 算法,一种计算高效的 UCB 风格元算法,可提供任意时间的后悔边界。其置信区间直接基于实际损失构建,无需额外优化,能自然反映底层专家的收敛特性。若每个专家内部后悔为 Õ(T^α),则 exttt{M-LCB} 的总体后悔被限制在 Õ(√(KT/M) + (K/M)^{1-α} T^α)。据我们所知,这是首个在每轮预算受限下对多个自适应专家并行训练给出后悔保证的结果。通过两个典型例子验证:(i) 带随机损失的在线参数模型;(ii) 本身为多臂老虎机算法的专家。这表明 exttt{M-LCB} 将经典老虎机范式扩展到更现实的、资源受限状态下具有状态依赖的自学习专家协同场景。
原文摘要 · Abstract (English)
In many modern applications, a system must dynamically choose between several adaptive learning algorithms that are trained online. Examples include model selection in streaming environments, switching between trading strategies in finance, and orchestrating multiple contextual bandit or reinforcement learning agents. At each round, a learner must select one predictor among $K$ adaptive experts to make a prediction, while being able to update at most $M \le K$ of them under a fixed training budget. We address this problem in the \emph{stochastic setting} and introduce \algname{M-LCB}, a computationally efficient UCB-style meta-algorithm that provides \emph{anytime regret guarantees}. Its confidence intervals are built directly from realized losses, require no additional optimization, and seamlessly reflect the convergence properties of the underlying experts. If each expert achieves internal regret $\tilde O(T^α)$, then \algname{M-LCB} ensures overall regret bounded by $\tilde O\!\Bigl(\sqrt{\tfrac{KT}{M}} \;+\; (K/M)^{1-α}\,T^α\Bigr)$. To our knowledge, this is the first result establishing regret guarantees when multiple adaptive experts are trained simultaneously under per-round budget constraints. We illustrate the framework with two representative cases: (i) parametric models trained online with stochastic losses, and (ii) experts that are themselves multi-armed bandit algorithms. These examples highlight how \algname{M-LCB} extends the classical bandit paradigm to the more realistic scenario of coordinating stateful, self-learning experts under limited resources.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。