Research map / Bandits and online learning / Online convex optimization and games
Testing the Feasibility of Linear Programs with Bandit Feedback
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 simple sequential tests for feasibility of an unknown linear program from bandit feedback, built on low-regret linear bandit methods and a nonasymptotic LIL, with a matching-in-d minimax lower bound of Omega(d/Gamma^2).
Problem
Testing whether an unknown linear program (constraints Ax >= 0) is feasible using noisy bandit feedback Ax_t + noise, with sample costs measured nonasymptotically in dimension d and signal level Gamma.
Approach
Cast feasibility as the sign of a minimax game value and build tests from low-regret / optimistic linear bandit actions, with stopping boundaries given by a nonasymptotic law of iterated logarithm, so that sample costs scale with d and the signal level rather than with log(1/delta) asymptotics.
Key results
- Ellipsoidal optimistic-greedy test (EOGT) is valid and well adapted, with expected stopping time scaling as O~(d^2/Gamma^2 + d log(m/delta)/Gamma^2).
- Tempered EOGT (T-EOGT) achieves E[tau] = O~(d^3/Gamma^2 + d/Gamma^2 log(8m/delta)) with exponential tail decay.
- Minimax lower bound Omega(d/Gamma^2) on expected stopping time of reliable tests over feasible instances with m=1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ellipsoidal optimistic-greedy selection with an adaptive stopping boundary instead of the tempered selection rule and deterministic boundaries | Linear bandit feasibility testing · Linear bandit feasibility testing | expected stopping time: d^3/\Gamma^2 instead of d^2/\Gamma^2 | Helped |
| Use tempered EOGT with deterministic anytime boundaries instead of EOGT | Linear bandit feasibility testing · Linear bandit feasibility testing | stopping-time tail: polynomial decay ... instead of exponential decay | Helped |
| Add early stopping when the running-mean action is certified feasible (ablation) | EOGT · Unit ball, m = 2, feasible instances | stopping time: < τ/10 | Helped |
| Replace the ellipsoidal confidence set with an L1 confidence set (ablation) | EOGT · Linear bandit feasibility testing | expected sample complexity: \widetilde{O}(d^3/\Gamma^2) | Hurt |
Surprising findings
- In simulations, all runs returned the correct hypothesis, suggesting the testing boundary is overly conservative.
- Early stopping on feasible instances was about a factor of 10 faster than the main stopping rule, though analysis does not explain this.
Limitations
- Gap between d/Gamma^2 lower bound and d^2/Gamma^2 upper bound for EOGT remains.
- Tempered test has weaker d^3 dependence in expected stopping time; EOGT's implementation relies on L1 relaxation with heuristic solving.
- Analysis is for sub-Gaussian linear noise over bounded domains; simulations restricted to m=2 and unit-ball domain.
Experimental setup
Metrics: expected stopping time error rate of returned hypothesis
Baselines: EOGT (ellipsoidal optimistic-greedy test)
Builds on: OFUL Murphy Sampling track-and-stop nonasymptotic law of iterated logarithm simulator technique for best arm identification
Closest papers by meaning
- Feasible Action Search for Bandit Linear Programs via Thompson Sampling (ICML 2025 · similarity 0.90)
- Greedy Algorithms for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure (NeurIPS 2025 · similarity 0.90)
- Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals (ICML 2024 · similarity 0.89)
- Constrained Linear Thompson Sampling (NeurIPS 2025 · similarity 0.89)
- Constrained Pareto Set Identification with Bandit Feedback (ICML 2025 · similarity 0.89)
- Batched Stochastic Linear Bandits with 1-Bit Communication Constraints (NeurIPS 2026 · 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.