# An Asymptotically Optimal Algorithm for the Convex Hull Membership Problem

arXiv: https://arxiv.org/abs/2302.02033 · HTML: https://mlsanity.com/paper/2302.02033/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 56 references that are in the map.
- First posted on arXiv 3 Feb 2023.

## Builds on (most cited first, 20 of 20)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Pareto Multi-Task Learning](https://mlsanity.com/paper/1912.12854/) (2019)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [Minimax Pareto Fairness: A Multi Objective Perspective](https://mlsanity.com/paper/2011.01821/) (2020)
- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Pure Exploration with Multiple Correct Answers](https://mlsanity.com/paper/1902.03475/) (2019)
- [Non-Asymptotic Pure Exploration by Solving Games](https://mlsanity.com/paper/1906.10431/) (2019)
- [Gamification of Pure Exploration for Linear Bandits](https://mlsanity.com/paper/2007.00953/) (2020)
- [An optimal algorithm for the Thresholding Bandit Problem](https://mlsanity.com/paper/1605.08671/) (2016)
- [Towards Instance Optimal Bounds for Best Arm Identification](https://mlsanity.com/paper/1608.06031/) (2016)
- [Good Arm Identification via Bandit Feedback](https://mlsanity.com/paper/1710.06360/) (2017)
- [Fair Active Learning](https://mlsanity.com/paper/2001.01796/) (2020)
- [Low-Rank Bandit Methods for High-Dimensional Dynamic Pricing](https://mlsanity.com/paper/1801.10242/) (2018)
- [Thresholding Bandit for Dose-ranging: The Impact of Monotonicity](https://mlsanity.com/paper/1711.04454/) (2017)
- [Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling](https://mlsanity.com/paper/1806.00973/) (2018)
- [Thresholding Bandit with Optimal Aggregate Regret](https://mlsanity.com/paper/1905.11046/) (2019)
- [First-order methods for the convex hull membership problem](https://mlsanity.com/paper/2111.07720/) (2021)
- [Achieving Representative Data via Convex Hull Feasibility Sampling Algorithms](https://mlsanity.com/paper/2204.06664/) (2022)

## Abstract (arXiv)

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.