Testing the Feasibility of Linear Programs with Bandit Feedback

Aditya Gangrade, Aditya Gopalan, Venkatesh Saligrama, Clayton Scott

Abstract

Most constrained bandit algorithms operate under the assumption that a feasible solution exists. This paper presents the first formal framework for testing this assumption in linear bandit settings. We introduce the Ellipsoidal Optimistic-Greedy Test (EOGT) and its variant T-EOGT, which provide provable sample complexity bounds. We also establish a minimax lower bound that characterizes how the problem scales with dimension $d$. Our findings indicate that testing feasibility is fundamentally more efficient than finding a near-optimal safe point, with sample complexity scaling quadratically with dimension in non-asymptotic regimes.

Introduction

In the field of "constrained bandits," a learner seeks to maximize rewards while adhering to hidden constraints—for instance, a clinical trial where a drug must be effective while keeping side effects below a threshold. Existing literature typically assumes feasibility, meaning there is at least one action satisfying all constraints. However, in practice, this assumption may fail, leading algorithms to waste resources searching for non-existent solutions. This paper addresses the fundamental question: How many samples are required to determine if a Linear Program (LP) is feasible given only noisy, bandit-style feedback?

Problem Formulation

The authors frame feasibility testing as determining the sign of a minimax value $\Gamma$: $$\Gamma := \max_{x \in \mathcal{X}} \min_{i \in [1:m]} (Ax)_i$$ If $\Gamma \geq 0$, the problem is feasible; if $\Gamma < 0$, it is not. This parameter $\Gamma$ represents the "safety margin" of the most feasible point or the "violation margin" of the least infeasible problem.

Geometric interpretation of the feasibility parameter $\Gamma$ in feasible (left) and infeasible (right) scenarios.

Methodology

The paper proposes two primary algorithms to address this challenge:

1. EOGT (Ellipsoidal Optimistic-Greedy Test)

EOGT employs a game-theoretic approach with a "feasibility-biased" max player and an "infeasibility-biased" min player. It constructs a confidence ellipsoid around the unknown constraint matrix $A$ using Online Linear Regression. Actions $x_t$ are selected optimistically to find a feasible point, while the test statistic monitors the "weakest" constraint.

Algorithm 1: The Ellipsoidal Optimistic-Greedy Test (EOGT).

2. T-EOGT (Tempered EOGT)

To address the "heavy-tailed" stopping time of EOGT, the authors designed T-EOGT. This variant uses a modified action selection rule that encourages additional exploration, ensuring an exponential decay in the probability of extreme delays.

Both algorithms utilize a Nonasymptotic Law of Iterated Logarithms (LIL) to determine stopping times. This provides a robust, "anytime" boundary that accounts for noise fluctuations without requiring a pre-fixed sample size.

Key Insights and Results

The research yields several critical insights into the nature of linear feasibility testing:

  • Efficiency of Testing: Verifying feasibility is significantly faster than finding a near-optimal safe point. Testing cost scales with the "safest" point, whereas optimization is constrained by the most difficult boundaries.
  • Dimensionality Scaling: Contrary to prior asymptotic work suggesting dimension-free costs, the authors prove that in practical regimes (moderate error probability $\delta$), the cost scales quadratically with dimension $d$.
  • Theoretical Bounds: The EOGT algorithm achieves an expected stopping time of $\tilde{O}(d^2/\Gamma^2)$, where the number of constraints $m$ has only a logarithmic effect. The authors also establish a minimax lower bound of $\Omega(d/\Gamma^2)$, confirming that linear dependence on $d$ is a fundamental requirement.

Conclusion

This work bridges the gap between pure exploration bandits and linear bandits by providing a rigorous framework for feasibility testing. While a gap remains between the $d$ in the lower bound and the $d^2$ in the upper bound—a common challenge in linear bandit theory—the proposed algorithms offer a practical and theoretically grounded approach to a critical problem in constrained optimization. Future work may extend these "anytime" tests to non-linear or kernelized constraint spaces.

Summary updated

Abstract

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 \ge 0$ for an unknown $A \in \mathbb{R}^{m \times d}$, by playing a sequence of actions $x_t\in \mathbb{R}^d$, and observing $Ax_t + \mathrm{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 $\widetilde{O}(d^2/\Gamma^2)$. We complement this by a minimax lower bound of $\Omega(d/\Gamma^2)$ 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.
BibTeX
@inproceedings{gangrade2024testing,
  author = {Aditya Gangrade and Aditya Gopalan and Venkatesh Saligrama and Clayton Scott},
  title = {{Testing the Feasibility of Linear Programs with Bandit Feedback}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=TfwGtfPkhV},
}
Figure