# Linear Stochastic Bandits Under Safety Constraints

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

## Key facts

- Cited by 90 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Aug 2019.

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

- [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)
- [Safe Exploration in Reinforcement Learning: A Generalized Formulation and Algorithms](https://mlsanity.com/paper/2310.03225/) (2023)
- [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)
- [Doubly robust Thompson sampling for linear payoffs](https://mlsanity.com/paper/2102.01229/) (2021)
- [A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraints](https://mlsanity.com/paper/2302.04375/) (2023)
- [Almost Optimal Variance-Constrained Best Arm Identification](https://mlsanity.com/paper/2201.10142/) (2022)
- [Active Learning with Safety Constraints](https://mlsanity.com/paper/2206.11183/) (2022)
- [Safe Exploration for Efficient Policy Evaluation and Comparison](https://mlsanity.com/paper/2202.13234/) (2022)
- [Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Risk](https://mlsanity.com/paper/2204.00706/) (2022)
- [On Safety in Safe Bayesian Optimization](https://mlsanity.com/paper/2403.12948/) (2024)
- [Safe Linear Bandits over Unknown Polytopes](https://mlsanity.com/paper/2209.13694/) (2022)
- [Safe Online Convex Optimization with Unknown Linear Safety Constraints](https://mlsanity.com/paper/2111.07430/) (2021)
- [Learning to Persuade on the Fly: Robustness Against Ignorance](https://mlsanity.com/paper/2102.10156/) (2021)
- [Interactively Learning Preference Constraints in Linear Bandits](https://mlsanity.com/paper/2206.05255/) (2022)
- [Log Barriers for Safe Black-box Optimization with Application to Safe Reinforcement Learning](https://mlsanity.com/paper/2207.10415/) (2022)
- [Safe Policy Optimization with Local Generalized Linear Function Approximations](https://mlsanity.com/paper/2111.04894/) (2021)
- [A safe exploration approach to constrained Markov decision processes](https://mlsanity.com/paper/2312.00561/) (2023)
- [A Reduction-Based Framework for Conservative Bandits and Reinforcement Learning](https://mlsanity.com/paper/2106.11692/) (2021)
- [Linear Stochastic Bandits over a Bit-Constrained Channel](https://mlsanity.com/paper/2203.01198/) (2022)
- [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)

## Abstract (arXiv)

Bandit algorithms have various application in safety-critical systems, where it is important to respect the system constraints that rely on the bandit's unknown parameters at every round. In this paper, we formulate a linear stochastic multi-armed bandit problem with safety constraints that depend (linearly) on an unknown parameter vector. As such, the learner is unable to identify all safe actions and must act conservatively in ensuring that her actions satisfy the safety constraint at all rounds (at least with high probability). For these bandits, we propose a new UCB-based algorithm called Safe-LUCB, which includes necessary modifications to respect safety constraints. The algorithm has two phases. During the pure exploration phase the learner chooses her actions at random from a restricted set of safe actions with the goal of learning a good approximation of the entire unknown safe set. Once this goal is achieved, the algorithm begins a safe exploration-exploitation phase where the learner gradually expands their estimate of the set of safe actions while controlling the growth of regret. We provide a general regret bound for the algorithm, as well as a problem dependent bound that is connected to the location of the optimal action within the safe set. We then propose a modified heuristic that exploits our problem dependent analysis to improve the regret.