arXiv：cs.LG· Mark Braverman, Jingyi Liu, Jieming Mao, Jon Schneider, Eric Xue·· 3 小时前
预算节奏与在线学习的近最优遗憾界
Optimally Pacing Budget Spending and Learning
AI 导读
研究者为对抗性设定下的预算受限在线学习建立了近最优遗憾界，针对任意包含 F 个专家的类别和给定预算节奏方案，提出全信息算法实现 O(D√log F + √T log F) 遗憾，与 Braverman 等人（2025）的下界匹配。该技术还扩展到在线资源分配问题，在允许分数分配时达到 O(D√log F) 遗憾，是已知首个在此类任务中实现 o(√T) 保证的算法。
正文
Abstract:We establish near-optimal regret bounds for budget-constrained online learning against arbitrary classes of budget-pacing experts in the adversarial setting. In particular, given any class of $F$ experts and a candidate budget pacing schedule, we provide a full-information algorithm which obtains regret $O(D \sqrt{\log F}+ \sqrt{T\log F})$ against all experts whose cumulative spending stays within distance $D$ of this schedule, matching lower bounds established by Braverman et al. (2025).
We additionally show that our technique extends to various problems in online resource allocation, where the learner gets to see the rewards and costs of the current options available to them, and establish $O(D\sqrt{\log F})$ regret bounds when fractional allocation is allowed. This is the first algorithm we are aware of which can achieve $o(\sqrt{T})$ guarantees for such tasks.
| Subjects: | Machine Learning (cs.LG); Computer Science and Game Theory (cs.GT) |
| Cite as: | arXiv:2610.11074 [cs.LG] |
| (or arXiv:2610.11074v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.11074 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Jingyi Liu [view email]
[v1]
Thu, 8 Oct 2026 01:32:09 UTC (50 KB)
来源：arXiv：cs.LG · arxiv.org