# Stochastic Bandits with Linear Constraints

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

## Key facts

- Cited by 68 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jun 2020.

## Built on by (most cited first, 30 of 68)

- [Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs](https://mlsanity.com/paper/2106.02684/) (2021)
- [Safe Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2106.06239/) (2021)
- [DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learning](https://mlsanity.com/paper/2112.00885/) (2021)
- [An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints](https://mlsanity.com/paper/2102.05295/) (2021)
- [Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraints](https://mlsanity.com/paper/2202.00150/) (2022)
- [Best Arm Identification with Safety Constraints](https://mlsanity.com/paper/2111.12151/) (2021)
- [On Kernelized Multi-Armed Bandits with Constraints](https://mlsanity.com/paper/2203.15589/) (2022)
- [Truly No-Regret Learning in Constrained MDPs](https://mlsanity.com/paper/2402.15776/) (2024)
- [A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraints](https://mlsanity.com/paper/2302.04375/) (2023)
- [Active Learning with Safety Constraints](https://mlsanity.com/paper/2206.11183/) (2022)
- [Achieving Counterfactual Fairness for Causal Bandit](https://mlsanity.com/paper/2109.10458/) (2021)
- [Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Risk](https://mlsanity.com/paper/2204.00706/) (2022)
- [Safe Linear Bandits over Unknown Polytopes](https://mlsanity.com/paper/2209.13694/) (2022)
- [Learning to Persuade on the Fly: Robustness Against Ignorance](https://mlsanity.com/paper/2102.10156/) (2021)
- [Online Contextual Decision-Making with a Smart Predict-then-Optimize Method](https://mlsanity.com/paper/2206.07316/) (2022)
- [Interactively Learning Preference Constraints in Linear Bandits](https://mlsanity.com/paper/2206.05255/) (2022)
- [Pure Exploration in Bandits with Linear Constraints](https://mlsanity.com/paper/2306.12774/) (2023)
- [A Reduction-Based Framework for Conservative Bandits and Reinforcement Learning](https://mlsanity.com/paper/2106.11692/) (2021)
- [Constrained Pure Exploration Multi-Armed Bandits with a Fixed Budget](https://mlsanity.com/paper/2211.14768/) (2022)
- [Directional Optimism for Safe Linear Bandits](https://mlsanity.com/paper/2308.15006/) (2023)
- [Safe Reinforcement Learning with Instantaneous Constraints: The Role of Aggressive Exploration](https://mlsanity.com/paper/2312.14470/) (2023)
- [Honor Among Bandits: No-Regret Learning for Online Fair Division](https://mlsanity.com/paper/2407.01795/) (2024)
- [Provably Efficient RL for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spaces](https://mlsanity.com/paper/2502.18655/) (2025)
- [Safe Posterior Sampling for Constrained MDPs with Bounded Constraint Violation](https://mlsanity.com/paper/2301.11547/) (2023)
- [Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation](https://mlsanity.com/paper/2502.10138/) (2025)
- [Near-optimal Conservative Exploration in Reinforcement Learning under Episode-wise Constraints](https://mlsanity.com/paper/2306.06265/) (2023)
- [Convex Methods for Constrained Linear Bandits](https://mlsanity.com/paper/2311.04338/) (2023)
- [No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!](https://mlsanity.com/paper/2506.13244/) (2025)
- [The Impact of the Geometric Properties of the Constraint Set in Safe Optimization with Bandit Feedback](https://mlsanity.com/paper/2305.00889/) (2023)
- [Contextual Bandits with Budgeted Information Reveal](https://mlsanity.com/paper/2305.18511/) (2023)

## Abstract (arXiv)

We study a constrained contextual linear bandit setting, where the goal of the agent is to produce a sequence of policies, whose expected cumulative reward over the course of T rounds is maximum, and each has an expected cost below a certain threshold τ. We propose an upper-confidence bound algorithm for this problem, called optimistic pessimistic linear bandit (OPLB), and prove an widetildeO(fracd√Tτ-c0) bound on its T-round regret, where the denominator is the difference between the constraint threshold and the cost of a known feasible action. We further specialize our results to multi-armed bandits and propose a computationally efficient algorithm for this setting. We prove a regret bound of widetildeO(frac√KTτ - c0) for this algorithm in K-armed bandits, which is a √K improvement over the regret bound we obtain by simply casting multi-armed bandits as an instance of contextual linear bandits and using the regret bound of OPLB. We also prove a lower-bound for the problem studied in the paper and provide simulations to validate our theoretical results.