# Contextual Bandits with Stage-wise Constraints

arXiv: https://arxiv.org/abs/2401.08016 · HTML: https://mlsanity.com/paper/2401.08016/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jan 2024.

## Built on by (most cited first, 12 of 12)

- [Provably Efficient RL for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spaces](https://mlsanity.com/paper/2502.18655/) (2025)
- [Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation](https://mlsanity.com/paper/2502.10138/) (2025)
- [Online Learning with Unknown Constraints](https://mlsanity.com/paper/2403.04033/) (2024)
- [Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budget](https://mlsanity.com/paper/2405.15090/) (2024)
- [Online Bidding under RoS Constraints without Knowing the Value](https://mlsanity.com/paper/2503.03195/) (2025)
- [Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget](https://mlsanity.com/paper/2506.02386/) (2025)
- [Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraints](https://mlsanity.com/paper/2410.18844/) (2024)
- [Constrained Linear Thompson Sampling](https://mlsanity.com/paper/2503.02043/) (2025)
- [A Simple Reduction Scheme for Constrained Contextual Bandits with Adversarial Contexts via Regression](https://mlsanity.com/paper/2602.05019/) (2026)
- [Escaping Offline Pessimism: Vector-Field Reward Shaping for Safe Frontier Exploration](https://mlsanity.com/paper/2603.18326/) (2026)
- [Multi-Task Representation Learning for Conservative Linear Bandits](https://mlsanity.com/paper/2605.12176/) (2026)
- [Safety by Design: Realized-Cost Constraints for Contextual Bandits with Continuous Actions](https://mlsanity.com/paper/2608.26755/) (2026)

## Abstract (arXiv)

We study contextual bandits in the presence of a stage-wise constraint when the constraint must be satisfied both with high probability and in expectation. We start with the linear case where both the reward function and the stage-wise constraint (cost function) are linear. In each of the high probability and in expectation settings, we propose an upper-confidence bound algorithm for the problem and prove a T-round regret bound for it. We also prove a lower-bound for this constrained problem, show how our algorithms and analyses can be extended to multiple constraints, and provide simulations to validate our theoretical results. In the high probability setting, we describe the minimum requirements for the action set for our algorithm to be tractable. In the setting that the constraint is in expectation, we specialize our results to multi-armed bandits and propose a computationally efficient algorithm for this setting with regret analysis. Finally, we extend our results to the case where the reward and cost functions are both non-linear. We propose an algorithm for this case and prove a regret bound for it that characterize the function class complexity by the eluder dimension.