Metraipolis › archive › dc_c80ae218deb5
Optimally Pacing Budget Spending and Learning — arXiv:2610.11074
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.11074
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-09T06:18:12.442Z
- SHA-256 of the archived text
2613e2ffac11c9b059fd8b2ee29046f4f9adef89b8a3314a7bd386e7b6f72f49- Stable URL of this page
https://metraipolis.com/documento/dc_c80ae218deb5
How to cite
Optimally Pacing Budget Spending and Learning — arXiv:2610.11074 — arXiv (en), https://arxiv.org/abs/2610.11074 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c80ae218deb5 (Metraipolis archive dc_c80ae218deb5, sha256 2613e2ffac11c9b059fd8b2ee29046f4f9adef89b8a3314a7bd386e7b6f72f49)
BibTeX
@misc{dcc80ae218deb5,
title = {Optimally Pacing Budget Spending and Learning — arXiv:2610.11074},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.11074},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c80ae218deb5; sha256 2613e2ffac11c9b059fd8b2ee29046f4f9adef89b8a3314a7bd386e7b6f72f49},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.11074. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2610.11074 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T05:49:00.706Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).