# Safe Linear Stochastic Bandits

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Nov 2019.

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

- [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)
- [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)
- [Directional Optimism for Safe Linear Bandits](https://mlsanity.com/paper/2308.15006/) (2023)
- [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)
- [ESCADA: Efficient Safety and Context Aware Dose Allocation for Precision Medicine](https://mlsanity.com/paper/2111.13415/) (2021)
- [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)
- [Dynamic Regret Analysis of Safe Distributed Online Optimization for Convex and Non-convex Problems](https://mlsanity.com/paper/2302.12320/) (2023)
- [Price of Safety in Linear Best Arm Identification](https://mlsanity.com/paper/2309.08709/) (2023)
- [Safety Aware Changepoint Detection for Piecewise i.i.d. Bandits](https://mlsanity.com/paper/2205.13689/) (2022)
- [Distributed Multi-Task Learning for Stochastic Bandits with Context Distribution and Stage-wise Constraints](https://mlsanity.com/paper/2401.11563/) (2024)
- [Safe Linear Leveling Bandits](https://mlsanity.com/paper/2112.06728/) (2021)
- [Benefits of Monotonicity in Safe Exploration with Gaussian Processes](https://mlsanity.com/paper/2211.01561/) (2022)
- [Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits](https://mlsanity.com/paper/2301.13393/) (2023)
- [Multi-Agent Stage-wise Conservative Linear Bandits](https://mlsanity.com/paper/2510.00602/) (2025)
- [BanditLP: Large-Scale Stochastic Optimization for Personalized Recommendations](https://mlsanity.com/paper/2601.15552/) (2026)
- [Exploration of Unranked Items in Safe Online Learning to Re-Rank](https://mlsanity.com/paper/2305.01202/) (2023)
- [Robust Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2311.04731/) (2023)
- [The Safety-Privacy Tradeoff in Linear Bandits](https://mlsanity.com/paper/2504.16371/) (2025)
- [Secure Best Arm Identification in the Presence of a Copycat](https://mlsanity.com/paper/2507.18975/) (2025)
- [A Simple Reduction Scheme for Constrained Contextual Bandits with Adversarial Contexts via Regression](https://mlsanity.com/paper/2602.05019/) (2026)
- [Multi-Task Representation Learning for Conservative Linear Bandits](https://mlsanity.com/paper/2605.12176/) (2026)
- [Minimax Optimal Regret for Causal Logistic Bandits with Counterfactual Fairness](https://mlsanity.com/paper/2610.01377/) (2026)

## Abstract (arXiv)

We introduce the safe linear stochastic bandit framework---a generalization of linear stochastic bandits---where, in each stage, the learner is required to select an arm with an expected reward that is no less than a predetermined (safe) threshold with high probability. We assume that the learner initially has knowledge of an arm that is known to be safe, but not necessarily optimal. Leveraging on this assumption, we introduce a learning algorithm that systematically combines known safe arms with exploratory arms to safely expand the set of safe arms over time, while facilitating safe greedy exploitation in subsequent stages. In addition to ensuring the satisfaction of the safety constraint at every stage of play, the proposed algorithm is shown to exhibit an expected regret that is no more than O(√Tlog (T)) after T stages of play.