# Testing the Feasibility of Linear Programs with Bandit Feedback

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 28 references that are in the map.
- First posted on arXiv 21 Jun 2024.

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

- [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)
- [Pure Exploration with Multiple Correct Answers](https://mlsanity.com/paper/1902.03475/) (2019)
- [Non-Asymptotic Pure Exploration by Solving Games](https://mlsanity.com/paper/1906.10431/) (2019)
- [An optimal algorithm for the Thresholding Bandit Problem](https://mlsanity.com/paper/1605.08671/) (2016)
- [Safe Linear Thompson Sampling with Side Information](https://mlsanity.com/paper/1911.02156/) (2019)
- [The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime](https://mlsanity.com/paper/1702.05186/) (2017)
- [Good Arm Identification via Bandit Feedback](https://mlsanity.com/paper/1710.06360/) (2017)
- [Sequential Nonparametric Testing with the Law of the Iterated Logarithm](https://mlsanity.com/paper/1506.03486/) (2015)
- [Active Learning with Safety Constraints](https://mlsanity.com/paper/2206.11183/) (2022)
- [Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling](https://mlsanity.com/paper/1806.00973/) (2018)
- [Sample complexity of partition identification using multi-armed bandits](https://mlsanity.com/paper/1811.05654/) (2018)
- [Regret Distribution in Stochastic Bandits: Optimal Trade-off between Expectation and Tail Risk](https://mlsanity.com/paper/2304.04341/) (2023)
- [An Anytime Algorithm for Good Arm Identification](https://mlsanity.com/paper/2310.10359/) (2023)
- [A Bad Arm Existence Checking Problem](https://mlsanity.com/paper/1901.11200/) (2019)

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

- [Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraints](https://mlsanity.com/paper/2410.18844/) (2024)
- [Safe and Efficient Online Convex Optimization with Linear Budget Constraints and Partial Feedback](https://mlsanity.com/paper/2412.03983/) (2024)
- [Constrained Linear Thompson Sampling](https://mlsanity.com/paper/2503.02043/) (2025)

## Abstract (arXiv)

While the recent literature has seen a surge in the study of constrained bandit problems, all existing methods for these begin by assuming the feasibility of the underlying problem. We initiate the study of testing such feasibility assumptions, and in particular address the problem in the linear bandit setting, thus characterising the costs of feasibility testing for an unknown linear program using bandit feedback. Concretely, we test if exists x: Ax ≥ 0 for an unknown A ∈ ℝm × d, by playing a sequence of actions xt∈ ℝd, and observing Axt + noise in response. By identifying the hypothesis as determining the sign of the value of a minimax game, we construct a novel test based on low-regret algorithms and a nonasymptotic law of iterated logarithms. We prove that this test is reliable, and adapts to the `signal level,' Gamma, of any instance, with mean sample costs scaling as widetildeO(d2/Gamma2). We complement this by a minimax lower bound of Omega(d/Gamma2) for sample costs of reliable tests, dominating prior asymptotic lower bounds by capturing the dependence on d, and thus elucidating a basic insight missing in the extant literature on such problems.