# Thompson Sampling for Linearly Constrained Bandits

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Apr 2020.

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

- [BanditLP: Large-Scale Stochastic Optimization for Personalized Recommendations](https://mlsanity.com/paper/2601.15552/) (2026)
- [Thompson Sampling with Virtual Helping Agents](https://mlsanity.com/paper/2209.08197/) (2022)
- [Multi-User mmWave Beam and Rate Adaptation via Combinatorial Satisficing Bandits](https://mlsanity.com/paper/2604.14908/) (2026)

## Abstract (arXiv)

We address multi-armed bandits (MAB) where the objective is to maximize the cumulative reward under a probabilistic linear constraint. For a few real-world instances of this problem, constrained extensions of the well-known Thompson Sampling (TS) heuristic have recently been proposed. However, finite-time analysis of constrained TS is challenging; as a result, only O(√T) bounds on the cumulative reward loss (i.e., the regret) are available. In this paper, we describe LinConTS, a TS-based algorithm for bandits that place a linear constraint on the probability of earning a reward in every round. We show that for LinConTS, the regret as well as the cumulative constraint violations are upper bounded by O(log T) for the suboptimal arms. We develop a proof technique that relies on careful analysis of the dual problem and combine it with recent theoretical work on unconstrained TS. Through numerical experiments on two real-world datasets, we demonstrate that LinConTS outperforms an asymptotically optimal upper confidence bound (UCB) scheme in terms of simultaneously minimizing the regret and the violation.