# Stage-wise Conservative Linear Bandits

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Sep 2020.

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

- [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)
- [Best Arm Identification with Safety Constraints](https://mlsanity.com/paper/2111.12151/) (2021)
- [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)
- [Learning to Persuade on the Fly: Robustness Against Ignorance](https://mlsanity.com/paper/2102.10156/) (2021)
- [An Accurate Non-accelerometer-based PPG Motion Artifact Removal Technique using CycleGAN](https://mlsanity.com/paper/2106.11512/) (2021)
- [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)
- [Feature and Parameter Selection in Stochastic Linear Bandits](https://mlsanity.com/paper/2106.05378/) (2021)
- [Convex Methods for Constrained Linear Bandits](https://mlsanity.com/paper/2311.04338/) (2023)
- [Multi-Environment Meta-Learning in Stochastic Linear Bandits](https://mlsanity.com/paper/2205.06326/) (2022)
- [Collaborative Multi-agent Stochastic Linear Bandits](https://mlsanity.com/paper/2205.06331/) (2022)
- [Safe Online Bid Optimization with Return on Investment and Budget Constraints](https://mlsanity.com/paper/2201.07139/) (2022)
- [The Impact of the Geometric Properties of the Constraint Set in Safe Optimization with Bandit Feedback](https://mlsanity.com/paper/2305.00889/) (2023)
- [Vehicle trajectory prediction in top-view image sequences based on deep learning method](https://mlsanity.com/paper/2102.01749/) (2021)
- [Learning to Act Safely with Limited Exposure and Almost Sure Certainty](https://mlsanity.com/paper/2105.08748/) (2021)
- [Safety Aware Changepoint Detection for Piecewise i.i.d. Bandits](https://mlsanity.com/paper/2205.13689/) (2022)
- [No-Regret Linear Bandits beyond Realizability](https://mlsanity.com/paper/2302.13252/) (2023)
- [Distributed Multi-Task Learning for Stochastic Bandits with Context Distribution and Stage-wise Constraints](https://mlsanity.com/paper/2401.11563/) (2024)
- [Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits](https://mlsanity.com/paper/2301.13393/) (2023)
- [Adaptive Budgeted Multi-Armed Bandits for IoT with Dynamic Resource Constraints](https://mlsanity.com/paper/2505.02640/) (2025)
- [Multi-Agent Stage-wise Conservative Linear Bandits](https://mlsanity.com/paper/2510.00602/) (2025)
- [On-Policy Distillation of Language Models for Autonomous Vehicle Motion Planning](https://mlsanity.com/paper/2604.07944/) (2026)
- [Exploration of Unranked Items in Safe Online Learning to Re-Rank](https://mlsanity.com/paper/2305.01202/) (2023)
- [Bandits with Anytime Knapsacks](https://mlsanity.com/paper/2501.18560/) (2025)
- [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 study stage-wise conservative linear stochastic bandits: an instance of bandit optimization, which accounts for (unknown) safety constraints that appear in applications such as online advertising and medical trials. At each stage, the learner must choose actions that not only maximize cumulative reward across the entire time horizon but further satisfy a linear baseline constraint that takes the form of a lower bound on the instantaneous reward. For this problem, we present two novel algorithms, stage-wise conservative linear Thompson Sampling (SCLTS) and stage-wise conservative linear UCB (SCLUCB), that respect the baseline constraints and enjoy probabilistic regret bounds of order O(√T log3/2T) and O(√T log T), respectively. Notably, the proposed algorithms can be adjusted with only minor modifications to tackle different problem variations, such as constraints with bandit-feedback, or an unknown sequence of baseline actions. We discuss these and other improvements over the state-of-the-art. For instance, compared to existing solutions, we show that SCLTS plays the (non-optimal) baseline action at most O(logT) times (compared to O(√T)). Finally, we make connections to another studied form of safety constraints that takes the form of an upper bound on the instantaneous reward. While this incurs additional complexity to the learning process as the optimal action is not guaranteed to belong to the safe set at each round, we show that SCLUCB can properly adjust in this setting via a simple modification.