An Asymptotically Optimal Algorithm for the Convex Hull Membership Problem
This work addresses a fundamental problem in multi-armed bandits and decision-making, with incremental extensions to existing settings.
The paper tackles the convex hull membership problem in pure exploration by characterizing its sample complexity in one dimension and introducing Thompson-CHM, the first asymptotically optimal algorithm, which is extended to higher dimensions and validated with numerical experiments.
We study the convex hull membership (CHM) problem in the pure exploration setting where one aims to efficiently and accurately determine if a given point lies in the convex hull of means of a finite set of distributions. We give a complete characterization of the sample complexity of the CHM problem in the one-dimensional case. We present the first asymptotically optimal algorithm called Thompson-CHM, whose modular design consists of a stopping rule and a sampling rule. In addition, we extend the algorithm to settings that generalize several important problems in the multi-armed bandit literature. Furthermore, we discuss the extension of Thompson-CHM to higher dimensions. Finally, we provide numerical experiments to demonstrate the empirical behavior of the algorithm matches our theoretical results for realistic time horizons.