Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Constrained Linear Thompson Sampling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes COLTS, a sampling-based (Thompson-style) approach for safe linear bandits that solves perturbed linear programs with a coupled noise design, giving S-COLTS (zero risk given a safe action) and R-COLTS (instance-independent regret and risk via resampling).
Problem
Safe linear bandits: maximize an unknown linear objective subject to unknown linear constraints each round, with efficient computation; existing confidence-based methods require second-order cone or NP-hard per-round optimization.
Approach
Perturb the objective and constraint estimates with a coupled noise vector (add psi to objective, -psi to every constraint row), then play the optimizer of the perturbed linear program; S-COLTS scales the optimum toward a known safe action, and R-COLTS resamples several perturbed programs and picks the one with the largest value to obtain optimism.
Key results
- S-COLTS achieves a 5.1x wall-clock speedup over SAFE-LTS on the d=m=9 instance while improving regret and never playing unsafe actions.
- For d=2, m>=10, SAFE-LTS regret is 2-4x larger than S-COLTS, and SAFE-LTS computational cost reaches over 18x that of S-COLTS at m=100.
- R-COLTS with 1 sample per round gives R_T=658 and S_T=2891 at T=5e4 on the d=m=9 instance; resampling (3 samples) reduces R_T to 301.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase r-COLTS resampling from 1 to 3 samples per round (ablation) | r-COLTS · r-COLTS simulation, T = 5 \cdot 10^4, 100 trials | regret: 658 \pm 170 -> 301 \pm 102 | Helped |
| Increase r-COLTS resampling from 1 to 3 samples per round (ablation) | r-COLTS · r-COLTS simulation, T = 5 \cdot 10^4, 100 trials | risk: 2891 \pm 171 -> 3266 \pm 172 | Hurt |
| Use s-COLTS instead of safe-LTS | hard constraint enforcement, d = m = 9 · s-COLTS simulation, d = m = 9 | regret | Helped |
| Use s-COLTS instead of safe-LTS | hard constraint enforcement, d = m = 9 · s-COLTS simulation, d = m = 9 | wall-clock time: 5.1 \times | Helped |
| Use s-COLTS instead of safe-LTS | hard constraint enforcement, d = 2, m = 100 · s-COLTS simulation, d = 2, m = 100 | regret: 2-4\times | Helped |
| Use s-COLTS instead of safe-LTS | hard constraint enforcement, d = 2, m = 100 · s-COLTS simulation, d = 2, m = 100 | computation time: starting from \approx 1.3\times for $m = 1$ to >18\times at $m = 100$ | Helped |
| Use exploratory-COLTS instead of s-COLTS | safe linear bandits with a positive-margin action · Safe linear bandits | regret | Mixed |
Surprising findings
- Resampling slightly worsens risk while significantly reducing regret in R-COLTS.
- Using smaller-than-theoretical noise (Unif(0.5 S^d)) in simulations performs better than the large noise required by the theory.
Limitations
- Theoretical bounds lose sqrt(d) relative to inefficient methods (O~(sqrt(d^3 T)) vs O~(sqrt(d^2 T))).
- Contextual extension is only informal; regret results for contextual settings require additional assumptions on the feature map or safe policy.
- S-COLTS requires a known safe action with positive safety margin; R-COLTS has no hard safety guarantee.
Experimental setup
Benchmarks: simulated safe linear bandit instances
Metrics: regret R_T risk S_T wall-clock time
Baselines: SAFE-LTS DOSS OPT-PESS ROFUL
Builds on: linear Thompson sampling OFUL SAFE-LTS DOSS ROFUL
Closest papers by meaning
- Feasible Action Search for Bandit Linear Programs via Thompson Sampling (ICML 2025 · similarity 0.94)
- Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Bandits (ICLR 2025 · similarity 0.90)
- Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown (NeurIPS 2025 · similarity 0.89)
- Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization (ICML 2024 · similarity 0.89)
- Thompson Sampling for Multi-Objective Linear Contextual Bandit (NeurIPS 2025 · similarity 0.89)
- Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits (NeurIPS 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.