Abstract:We study budget-constrained contextual bandits with adversarial contexts, where each action yields a random reward and incurs a random cost. We adopt the standard realizability assumption: conditioned on the observed context, rewards and costs are drawn independently from fixed distributions whose expectations belong to known function classes. We focus on the continuing setting, in which the algorithm operates over the entire horizon even after the budget for cumulative cost is exhausted. In this setting, the objective is to simultaneously control regret and the violation of the budget constraint. Building on the seminal $\mathsf{SquareCB}$ framework of Foster et al. [2018], we propose a simple and modular framework that leverages online regression oracles to reduce the constrained problem to a standard unconstrained contextual bandit problem with adaptively defined surrogate reward functions. In contrast to prior works, which focus on stochastic contexts, our reduction yields improved guarantees for more general adversarial contexts, together with an efficient algorithm with a compact and transparent analysis.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2605.06190 [cs.LG] |
| (or arXiv:2605.06190v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2605.06190 arXiv-issued DOI via DataCite (pending registration) |
From: Abhishek Sinha [view email]
[v1]
Thu, 7 May 2026 13:04:49 UTC (183 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。