An Asymptotically Optimal Algorithm for the One-Dimensional Convex Hull Feasibility Problem

Gang Qiao, Ambuj Tewari

Introduction

In the field of Multi-Armed Bandits (MAB), the majority of research focuses on Best Arm Identification (BAI)—the task of finding the single arm with the highest mean. However, many practical applications, ranging from algorithmic fairness to multi-task learning, require a different type of structural knowledge: determining whether a specific target point $\gamma$ lies within the convex hull of the means of $K$ unknown distributions. This is known as the Convex Hull Membership (CHM) problem.

In a one-dimensional (1D) setting, the CHM problem simplifies to determining if a threshold $\gamma$ is bounded by the smallest and largest means of the available arms. Because the true means are unknown, they must be sampled sequentially. The goal is to minimize the total number of samples (sample complexity) required to reach a correct decision with a high confidence level ($1-\delta$). This paper introduces Thompson-CHM, the first algorithm for this problem that is proven to be asymptotically optimal, matching the theoretical information-theoretic lower bounds.

The Thompson-CHM Algorithm

Thompson-CHM is a modular algorithm that pairs a robust stopping rule with a novel sampling strategy designed to navigate the unique geometry of the CHM problem.

The Stopping Rule

The algorithm monitors three distinct conditions to determine when it has sufficient evidence to stop:

  1. Upper Infeasibility: All arms appear significantly above the threshold $\gamma$.
  2. Lower Infeasibility: All arms appear significantly below the threshold $\gamma$.
  3. Feasibility: At least one arm is significantly above $\gamma$ and another is significantly below $\gamma$.

The Sampling Rule

The core innovation of the paper lies in its sampling rule, which combines two sophisticated techniques to achieve optimality:

  • Murphy Sampling: This is a variation of Thompson Sampling that conditions the posterior distribution on the "worst-case" event. For example, if the algorithm is testing for feasibility, it samples as if the point is in the convex hull to better explore the boundaries of the decision space.
  • Top-Two Modification: To prevent the algorithm from over-sampling a single "interesting" arm, it employs a Bernoulli trial. This trial decides whether to pull the arm with the current maximum sampled mean or the minimum sampled mean, ensuring balanced exploration of the hull's boundaries.

Theoretical and Empirical Results

The authors provide a complete mathematical characterization of the sample complexity for 1D CHM. They prove that as the confidence requirement becomes stricter ($\delta \to 0$), the number of samples taken by Thompson-CHM converges to the information-theoretic lower bound.

Empirical Validation

The algorithm was evaluated using synthetic Bernoulli bandits with 7 arms (means ranging from 0.1 to 0.7). The researchers tested various threshold values ($\gamma$) to cover both feasible cases (e.g., $\gamma=0.25$) and infeasible cases (e.g., $\gamma=0.9$). The results demonstrated that the empirical sample complexity almost perfectly overlaps with the theoretical lower bound, outperforming "naive" approaches that treat the problem as two independent thresholding tasks.

Key Insights

The Feasibility Asymmetry

A critical insight of this work is the asymmetry in optimal sampling based on the underlying truth. If the target point is inside the hull (feasible), the optimal strategy focuses almost exclusively on the extreme arms (the minimum and maximum) to prove the boundary. Conversely, if the point is outside the hull (infeasible), the algorithm must sample every arm to ensure that none of them cross the threshold. Thompson-CHM is designed to adapt to this weight distribution automatically without prior knowledge of the state.

Generalization to Higher Dimensions

While the primary focus is 1D, the authors demonstrate that the 1D problem is a fundamental building block for higher dimensions. In $d$-dimensional space, the problem essentially reduces to identifying the extreme points (vertices) of the convex hull. The paper provides a framework for the $d$-dimensional case and the Interval CHM problem (determining if an interval intersects the hull).

Limitations and Future Directions

While Thompson-CHM achieves asymptotic optimality, several challenges remain for future research:

  • Computational Complexity in $d$-Dimensions: Extending the algorithm to $d \ge 2$ currently assumes "oracle access" to specific functions that determine optimal arm weights. Finding explicit forms for these functions in complex geometries is an open problem.
  • Small Sample Regimes: Asymptotic optimality focuses on the limit as $\delta \to 0$. Refining the algorithm's performance in low-budget or high-risk scenarios where samples are extremely limited remains a valuable area for exploration.
  • Geometric Complexity: The proof of optimality becomes significantly more difficult in higher dimensions due to the complex geometry of the "alternative" set (the configurations of means that would change the feasibility result).

Summary updated

BibTeX
@article{qiao2025asymptotically,
  author = {Gang Qiao and Ambuj Tewari},
  title = {{An Asymptotically Optimal Algorithm for the One-Dimensional Convex Hull Feasibility Problem}},
  journal = {Accepted by TMLR},
  year = {2025},
  url = {https://openreview.net/forum?id=r8eAwBMtlN},
}
Figure