A Simple Reduction Scheme for Constrained Contextual Bandits with Adversarial Contexts via Regression
Dhruv Sarkar, Abhishek Sinha · 2026
Read A Simple Reduction Scheme for Constrained Contextual Bandits with Adversarial Contexts via Regression by Dhruv Sarkar, Abhishek Sinha (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-05019.txt.
Description
Learning algorithms that must respect a budget face a harder problem when the situations they meet are chosen adversarially. Dhruv Sarkar and Abhishek Sinha study that problem, called constrained contextual bandits, in this 2026 learning theory paper. Each action brings a random reward and a random cost, and the algorithm must keep both regret and total budget violation low.
Earlier work mostly assumed friendly, random contexts. Building on a known framework called SquareCB, the authors give a simple reduction: solve the constrained problem by calling ordinary online regression tools on cleverly reshaped rewards. The scheme keeps working even after the budget runs out, which matches real deployments. Their guarantees improve on prior results for the adversarial setting, and the analysis is compact enough to teach from.
Catalog record
| CREATOR | Dhruv Sarkar, Abhishek Sinha |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 63 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-05019