aiqbench analysis
This paper advances the theoretical foundations of online learning by extending contextual bandit algorithms to handle adversarial contexts with hard constraints on expected costs. The authors improve upon prior stochastic bounds by removing margin conditions and deriving tighter regret guarantees using a novel surrogate reward function and Lyapunov analysis. These results are significant for researchers developing robust reinforcement learning agents that must operate under strict safety or resource limitations without relying on probabilistic assumptions about the environment.
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.
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.
Machine Learning (cs.LG)
arXiv:2605.06190 [cs.LG]
(or arXiv:2605.06190v2 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2605.06190 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 271 words
Related coverage
Model-Adaptive and Risk-Constrained Frequency Hopping Against Predictive Jammers
arXiv · Sep 9, 2026
Best-of-Both Worlds for linear contextual bandits with paid observations
arXiv · Sep 9, 2026
Sequential Batch Learning in Finite-Action Linear Contextual Bandits
arXiv · Aug 19, 2026
Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback
arXiv · Jul 28, 2026