Testing the Feasibility of Linear Programs with Bandit Feedback

arXiv:2406.15648v1 Announce Type: new
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 …

abstract arxiv assumptions cs.lg feedback linear literature math.st problem stat.ml stat.th study testing type while