Constrained Contextual Bandits with Adversarial Contexts

arXiv:2605.06190v2 Announce Type: replace Abstract: We study constrained contextual bandits with adversarial contexts, where each action yields a random reward and incurs a random cost. The conditional mean reward and cost belong to known function classes and are learned through online regression oracles. The benchmark is a stationary randomized policy whose expected cost is non-positive at every observed context. We extend the seminal mathsf{SquareCB} algorithm of Foster and Rakhlin (2020), which reduces the contextual bandits to a regression problem, to the constrained setting. A surrogate reward function is constructed which penalizes the positive part of the expected cost of an action distribution, and an auxiliary variable accumulates its predicted value. Then we use an exponential Lyapunov function to control both regret and cumulative constraint violation via a single inequality. If the cumulative squared prediction error is at most U_T, our algorithm achieves O(sqrt{KTU_T}) regret and O(sqrt{KTU_T}log T) cumulative expected cost, with high probability, improving upon the previous O(T^{3/4}) type bounds obtained in stochastic contextual settings with an unknown context distribution. Our results require neither additional margin conditions nor probabilistic assumptions on the context sequence.

Source: arXiv cs.LG | 2026-10-14