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.
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.
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