Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Feasible Action Search for Bandit Linear Programs via 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 FAST, a Thompson-sampling-based efficient algorithm for feasible action search in linear bandits that finds a near-optimal-margin safe action (or detects infeasibility), and uses its output to initialise safe linear bandit methods.
Problem
Finding a feasible point (action with positive safety margin) for unknown linear constraints Φ*a ≥ 0 in a continuous action space via noisy bandit feedback, without a known safe initial action, and detecting infeasibility.
Approach
Runs Thompson sampling on a regression estimate of the constraint matrix with a coupled noise design (identical scaled spherical perturbation across all rows), plays a maximin point of the perturbed matrix game, and stops using a tracking statistic that bounds the optimal safety margin; the analysis avoids convexity by using a local optimism event at a saddle point.
Key results
- FAST stops in roughly eO(d^3/(ε^2 M*^2)) rounds with safety cost eO(d^3/|M*|), returning a point with margin at least (1-ε)M*.
- Initialising LC-LUCB with FAST output yields the first safe linear bandit method achieving eO(sqrt(d^3 T / M*^2)) regret with O(1) safety cost without a known safe action.
- In simulations with d=6, m=2, M*=0.4, FAST's stopping time is about 27x smaller than EOGT and each round about 100x faster.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use FAST with coupled uniform spherical perturbations to search for a near-optimal safety-margin action | Feasible FAS instance · Feasible FAS instance | stopping time | Helped |
| Use FAST with coupled uniform spherical perturbations to search for a near-optimal safety-margin action | Feasible FAS instance · Feasible FAS instance | excess-risk | Helped |
| Initialize LC-LUCB with the action found by FAST | Safe linear bandits · Safe linear bandits | regret | Helped |
| Initialize LC-LUCB with the action found by FAST | Safe linear bandits · Safe linear bandits | safety cost | Helped |
Surprising findings
- Independent per-row noise yields optimism rates as small as 2^{-Omega(m)}, so the coupled noise design is needed for analysis.
Limitations
- Theory for the practical small-variance noise N(0, Id/sqrt(d)) is not proven; reliability is an open question.
- Stopping time has an extra factor of d relative to the optimal lower bound.
- Zero optimal margin case has no nontrivial stoppage guarantee.
Experimental setup
Benchmarks: simulated linear bandit instances (d=6, m=2)
Metrics: stopping time safety cost regret runtime
Baselines: EOGT LC-LUCB SAFE-LTS
Builds on: Abeille & Lazaric (2017) linear Thompson sampling analysis EOGT (Gangrade et al., 2024) OFUL (Abbasi-Yadkori et al., 2011) LC-LUCB (Pacchiano et al., 2024)
Closest papers by meaning
- Constrained Linear Thompson Sampling (NeurIPS 2025 · similarity 0.94)
- Testing the Feasibility of Linear Programs with Bandit Feedback (ICML 2024 · similarity 0.90)
- Infrequent Exploration in Linear Bandits (NeurIPS 2025 · similarity 0.89)
- Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown (NeurIPS 2025 · similarity 0.88)
- Thompson Sampling for Multi-Objective Linear Contextual Bandit (NeurIPS 2025 · similarity 0.88)
- Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits (NeurIPS 2025 · similarity 0.88)
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.