# Constrained Linear Thompson Sampling

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 38 references that are in the map.
- First posted on arXiv 3 Mar 2025.

## Builds on (most cited first, 24 of 24)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Linear Stochastic Bandits Under Safety Constraints](https://mlsanity.com/paper/1908.05814/) (2019)
- [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [Stochastic Bandits with Linear Constraints](https://mlsanity.com/paper/2006.10185/) (2020)
- [Safe Linear Thompson Sampling with Side Information](https://mlsanity.com/paper/1911.02156/) (2019)
- [On Multi-Armed Bandit Designs for Dose-Finding Clinical Trials](https://mlsanity.com/paper/1903.07082/) (2019)
- [The Elliptical Potential Lemma Revisited](https://mlsanity.com/paper/2010.10182/) (2020)
- [Active Learning with Safety Constraints](https://mlsanity.com/paper/2206.11183/) (2022)
- [Stability Constrained Reinforcement Learning for Real-Time Voltage Control](https://mlsanity.com/paper/2109.14854/) (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)
- [Contextual Bandits with Stage-wise Constraints](https://mlsanity.com/paper/2401.08016/) (2024)
- [Learning to be Fair: A Consequentialist Approach to Equitable Decision-Making](https://mlsanity.com/paper/2109.08792/) (2021)
- [Pure Exploration in Bandits with Linear Constraints](https://mlsanity.com/paper/2306.12774/) (2023)
- [Exploration in Linear Bandits with Rich Action Sets and its Implications for Inference](https://mlsanity.com/paper/2207.11597/) (2022)
- [Information-Theoretic Safe Exploration with Gaussian Processes](https://mlsanity.com/paper/2212.04914/) (2022)
- [Directional Optimism for Safe Linear Bandits](https://mlsanity.com/paper/2308.15006/) (2023)
- [Convex Methods for Constrained Linear Bandits](https://mlsanity.com/paper/2311.04338/) (2023)
- [The Impact of the Geometric Properties of the Constraint Set in Safe Optimization with Bandit Feedback](https://mlsanity.com/paper/2305.00889/) (2023)
- [Testing the Feasibility of Linear Programs with Bandit Feedback](https://mlsanity.com/paper/2406.15648/) (2024)

## Abstract (arXiv)

We study safe linear bandits (SLBs), where an agent selects actions from a convex set to maximize an unknown linear objective subject to unknown linear constraints in each round. Existing methods for SLBs provide strong regret guarantees, but require solving expensive optimization problems (e.g., second-order cones, NP hard programs). To address this, we propose Constrained Linear Thompson Sampling (COLTS), a sampling-based framework that selects actions by solving perturbed linear programs, which significantly reduces computational costs while matching the regret and risk of prior methods. We develop two main variants: S-COLTS, which ensures zero risk and widetildeO(√d3 T) regret given a safe action, and R-COLTS, which achieves widetildeO(√d3 T) regret and risk with no instance information. In simulations, these methods match or outperform state of the art SLB approaches while substantially improving scalability. On the technical front, we introduce a novel coupled noise design that ensures frequent `local optimism' about the true optimum, and a scaling-based analysis to handle the per-round variability of constraints.