Constrained Contextual Bandits with Adversarial Contexts
The authors propose a unified algorithmic framework for constrained contextual bandits where contexts are chosen adversarially. They adapt existing methods by using online regression to estimate arm losses and a cost-aware surrogate reward function. The core contribution is a general regret decomposition inequality that simultaneously controls both cumulative regret and constraint violations, leading to strong performance guarantees across various feasibility settings.