# Safe Linear Thompson Sampling with Side Information

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

## Key facts

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

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

- [Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs](https://mlsanity.com/paper/2106.02684/) (2021)
- [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)
- [Active Learning with Safety Constraints](https://mlsanity.com/paper/2206.11183/) (2022)
- [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)
- [Interactively Learning Preference Constraints in Linear Bandits](https://mlsanity.com/paper/2206.05255/) (2022)
- [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)
- [ESCADA: Efficient Safety and Context Aware Dose Allocation for Precision Medicine](https://mlsanity.com/paper/2111.13415/) (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)
- [The Impact of the Geometric Properties of the Constraint Set in Safe Optimization with Bandit Feedback](https://mlsanity.com/paper/2305.00889/) (2023)
- [SaVeR: Optimal Data Collection Strategy for Safe Policy Evaluation in Tabular MDP](https://mlsanity.com/paper/2406.02165/) (2024)
- [Testing the Feasibility of Linear Programs with Bandit Feedback](https://mlsanity.com/paper/2406.15648/) (2024)
- [Improved Algorithms for Multi-period Multi-class Packing Problems with Bandit Feedback](https://mlsanity.com/paper/2301.13791/) (2023)
- [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)
- [Cooperative Multi-Agent Constrained Stochastic Linear Bandits](https://mlsanity.com/paper/2410.17382/) (2024)
- [Safe Linear Leveling Bandits](https://mlsanity.com/paper/2112.06728/) (2021)
- [Optimistic Safety for Online Convex Optimization with Unknown Linear Constraints](https://mlsanity.com/paper/2403.05786/) (2024)
- [Constrained Online Decision-Making: A Unified Framework](https://mlsanity.com/paper/2505.07101/) (2025)
- [Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget](https://mlsanity.com/paper/2506.02386/) (2025)
- [Multi-Agent Stage-wise Conservative Linear Bandits](https://mlsanity.com/paper/2510.00602/) (2025)
- [Leveraging User-Triggered Supervision in Contextual Bandits](https://mlsanity.com/paper/2302.03784/) (2023)
- [Disincentivizing Polarization in Social Networks](https://mlsanity.com/paper/2305.14537/) (2023)

## Abstract (arXiv)

The design and performance analysis of bandit algorithms in the presence of stage-wise safety or reliability constraints has recently garnered significant interest. In this work, we consider the linear stochastic bandit problem under additional textitlinear safety constraints that need to be satisfied at each round. We provide a new safe algorithm based on linear Thompson Sampling (TS) for this problem and show a frequentist regret of order O (d3/2log1/2d · T1/2log3/2T), which remarkably matches the results provided by (Abeille et al., 2017) for the standard linear TS algorithm in the absence of safety constraints. We compare the performance of our algorithm with UCB-based safe algorithms and highlight how the inherently randomized nature of TS leads to a superior performance in expanding the set of safe actions the algorithm has access to at each round.