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

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