An Asymptotically Optimal Algorithm for the Convex Hull Membership Problem
Authors: Gang Qiao
Ambuj Tewari
Venue: Accepted by TMLR ()

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

Published in Transactions on Machine Learning Research (10/2025)
An Asymptotically Optimal Algorithm for the Convex Hull Membership Problem
Gang Qiao
ginogong@@umich.co edu
Department of Statistics University of Michigan, Ann Arbor
Ambuj Tewari
tewaria@eumich. edu
Department of Statistics University of Michigan, Ann Arbor
Reviewed on OpenReview: https: // openreview. net/ forum? id= rBeAuBMt L.
net/forum?
Abstract
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 the convex hull of means of a finite 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 stopping rule and a sampling rule. In addition, we extend the algorithm to settings that generalize several important problems in the multi-armed bandit litcrature. 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 thcoretical results for realistic time horizons.
1 Introduction
The multi-armed bandit (MAB) problem is a fundamental problem in sequential decision making where agent is required to make series of decisions to pull an arm of K slot machine in order to maximize the total reward. Each of the arms is associated with a fixed but unknown probability distribution (Auer et al. 2002 Lai et al. 1985). An enormous literature has accumulated over the past decades on the MAB problem,
such as clinical trials and drug testing (Bastani & Bayati 2020 Durand et. al. 2018). recommendation system and online advertising (Bouneffouf et al.) [012]]
2014 Nguyen 2021] Tang et al. 2013 Zhou et al.
2017), information retrieval (Bounefoouf
al.] 2013 Losada et al.
2017). and finance (Huo & Fu 2017
Misra et al. 2019 Mueller et al. 2019 Shen et al. 2015). The MAB problem was first studied theoretically
in the seminal work (Robbins] 1952 and followed
by vast line of work in two canonical settings: regret
minimization AAgrawal & Goyal 2013 Auer
2002 Auer et al. 2002 Chapelle & Li 2011 Chu et al. 2011
Dudik et al. 2011 Langford & Zhang 2007 Li et al. 2010 Srinivas et al.) 2009; Valko et al. 2013 and pure
exploration Chen et al. 2017
Garivier & Kaufmann
2016 Locatelli et. al. 2016 Russo 2016).
In this paper, we study the convex hull membership (CHM) problem in pure exploration setting: testing whether fixed target point lies in the convex hull of the unknown mean vectors of K distributions efficiently and accurately as possible. Following the multi-armed sampling model, where each distribution corresponds to arm, and pulling an arm reveals an independent sample from the distribution. Unlike classical reward-maximizing bandit setting, our goal is to resolve geometric decision problem under limited stochastic feedback. Pure exploration problems are usually studies in one of two settings: fixed-confidence of success or fixed-budget of samples. We work the former. The usual non-stochastic version of the CHM problem is well studied in Filippozzi al. (2023) and has attracted significant attention in different scientific areas and proven its crucial applications in image processing (Jayaram & Fleyeh 2016 Yang &

---

Published in Transactions on Machine Learning Research (10/2025)
Cohen
1999
robot motion planning [Lengyel et al. 1990: Streinu 2000 and pattern recognition Katzzin
2018
Roy et al. 2008
The stochastic CHM problem arises in important applications including fairness (Mrrtinez et al. 2020 and multi-task learning (Lin et al.) 2019), where we consider the instance to determine whether a given point 0" E C Rd lies on the Pareto frontier of a collection of m objective functions (Fi,... Fm). A point 0 is said to be Pareto optimal if no other 0 E O exists such that F((0) S E.(0") for all [m], with strict incquality in at least one coordinate. In is well known that, under differentiability,, any Pareto optimal point satisfies first-order condition: there exists convex combination (A1, Am) with summation equal to 1 such that E X; (0") = 0, or equivalently, 02 E (()) In a multi-task learning setup, VP((0) = Ep, [V4(0)] where P.'s and I,'s are the underlying distributions and loss functions of the i-th task for i E [m]. Since P/'s are unknown, we utilize the empirical version of VF, which follows distributions with different means and fits in our stochastic CHM setting. Nevertheless, there is almost no literature on the stochastic convex hull membership problem where we have to sample in order to estimate the positions of the means. Recently, Niss et. al. (2022) provided the first. theoretical bounds for the CHM problem. Unfortunately, their results have significant gaps between the upper and lower complexity bounds. To the best of our knowledge, this fundamental primitive of developing the complexity bounds and an (asymptotically) optimal algorithm for the CHM problem remains open in the literature before this work.
To tackle the aforementioned problem, we introduce Thompson- CHM, a Thompson Saaioson--mmmiinn--baa rithm that has asymptotic sample complexity matching the inforatiion-theorel Garivier & Kaufmann (2016). The sample complexity lower bound is modeled as a function of the character- istic time (Garivier & Kaufmann 2016), which can be captured by the value of zero-sum pure exploration gamn between two players (Chernofi] 1959 Degenne et al. 2019). As discussed in Section any successful pure exploration player needs to solve this pure exploration game, and therefore, the intuition behind the game is essential to our algorithm design. The design of the strategy to match the lower bound is based on the individual confidence interval for each of the K arms so that any algorithm using this stopping time can ensure an oulput of a correct decision with high probability (at. least - 8) no malter what sampling rule the algorithm applies.
algo- lower bound proved in
We remark that Kaufmann et al. (2018) first proposed active sequential tosting procedure to study the lowest mean of finite set of distributions, and provide conditional modification of the popular heuristic Thompson Sampling (named as Murphy Sampling) to tackle the limitations of the Lower Confidence Bound algorithm (LCB) and standard Thompson Sampling in different settings. However, a major challenge in extending Thompson Sampling to our CHM problem is to study the entreme means (largest and lowest mean in one-dimensional setting) simelltaneossl. To tackle this challenge, we borrow a two-arm sampling construction proposed in the Best-Arm Identification setting. Russo (2016) pointed out that Thompson Sampling can have poor asymptotic performance and this defect can be improved by a top-two arm sampling modification to prevent the algorithm from sampling the arm of interest too frequently. This modification automatically controls the measurement effort of each arm and ensures that the long-term asymplotic behavior is closely linked to the optimal allocation of the algorithu. To the best of our knowledge, conditional Thompson sampling and two-arm sampling have never been combined before.
Our novel sampling rule is independent of the confidence paramcter 5 and ensures the sampled proportion of each arm asymptotically matches the estimated-best allocation design derived by the pure exploration game in the one-dinensional setting. Therefore, it automatically adapts exploration for both feasible and infeasible cases in the CHM problem. We provide a theoretical analysis of the asymptotic optimality and extend it to two more important settings: interval CHM problem (identifying if an interval (イ intersects with the convex hull of the means of K arms) and the d-dimensional CHM problem when d 2 2. The first extension generalizes the CHM problem and reproduces the state-of-art results for several important MAB problems in the literature, including thresholding bandit (Locatelli et al. 2016) and sequential test for lowest mean (Kaufnann et al. 2018). Moreover, the stochastic CHM problem in d-dimensional setting has several important applications but its complete solution remains open.
To highlight and sumunarize our results, our contribution in this work is threefold:
2

---

Published in Transactions on Machine Learning Research (10/2025)
We prove the information-theorrtiie lower bound the sample complexity of the one-dimensional convex hull membership (CHM) problem and reveal an oracle allocation of different arms for algorithm design.
We introduce a novel ThhompsonSaamplnng ration and oracle allocation for both feasible and infeasible cases and we rigorously prove the algorithm is asymptotically optimal and its complexity exactly matches the theoretical lower bound.
algorithm that automatically adapts the right explo-
Our final contribution two important extensions of the Thompson-CHMM Cwa.CCaaaalllatiii algorithm. First, we extend the algorithm to the one mie-dimensional interval CHM problem by presenting the sample complexity bounds and the analogous asymptotically optimal algorithm, and discuss how this extension generalizes several fundamental BAI problems in the literature. We also investigate the potential extension to the d-dimensional CHM problem (d 2 2) by showing the sample complexity bound which shares the same behavior as the one- dimensional case, and defer more details including the variant of the [Tompson--Cae CHM algorithm to the appendix.
2 Related Work
In this section, we bricfly discuss some works and applications that motivate our work and are closcly related to the convex hull membership problem in the literature.
Thresholding Bandits: One closely related previous work is popular combinatorial pure exploration bandit problem known as the thresholding bandit problem where the learner's objective is to find the set of arms whose means are above a threshold. It was first introduced in Chen et al. (2044) and has been extensively studied in both fixed-confidence and fixed-budget scttings (Chen et al.] 2014 Garivier et al., 2017 Kano et al., 2019 Locatelli et al., 2016 Tao et al., 2019). Compared to the thresholding bandit problem, the convex hull membership problem only requires boolean decision and needs the existence for both arms above and below the threshold to guarantee feasibility, A naive approach using the thresholding bandit problem to solve the CHM problem is to find the set of arms with means above and below the threshold by applying thresholding bandit algorithm twice, and use the results to build conclusion on if the threshold lies in the convex hull of the set of the arm means. Compared to the proposed Thompson- CHM algorithm, this two-step procodure is sub-optimal and expends unnocossary samples to determine the truc sets arms with means above and below the threshold.
Fair Sampling and Minimax Pareto Fairness: A recent series of works on fairness sampling and minimax Pareto fairness (Abernethy al. 2020 Anahideh et al.] 2022, Martinez et al. 2020 Nargesian et al. 2021) share similar frameworks with the fair data sampling procedure that is related to the CHM problem. As discussed in Niss et al. (2022). the main challenge of fair data sampling is to collect data of desired distribution requirements, therefore it reveals an appropriate representation of majority and minority groups in the data. In Anahideh et al. (2022). authors propose a fair active learning framework to balance the trade-off between model accuracy and fairness, in order to avoid discrimination in machine learning models. In Martincz et al. (2020). group fairness formulatod as a multi-objective optimization problem and proposes conditions for the classifier to be Pareto-efficient and achieve minimax risk, which closely related to the stochastic CHM setting.
3 Problem Setup and Formulation
We define the problem of efficiently and accurately identifying if a given point lies in (or if given interval/set intersects with, respectively) the convex hull of means of K probability distributions Vi, ,KK MK in dimension d based on their stochastic sequential samples as the d-dimensional convex hull membership (d-dim CHM) problem. In this paper, we start with the one-dimensional setting where the probability distributions are in the canonical one-dimensional exponential family. In the canonical one-dimensional exponential family, the marginal distribution of a value x given an unknown parameter 0 E R takes the form
P(z h(z) exp(n(x)0 -((})
where h(x), 7((x) and A(0) known functions.
3

---

Published in Transactions on Machine Learning Research (10/2025)
Throughout the paper, we denote by μ (J1.... .PK) the vector of unknown true means of the distri- butions ",,"",, , Ux, and À will be used as possible alternatives of the mean vector. The Kullback-Teibler divergence is a standard measure of how one probability distribution P differs from another Q with the form P(x) ((P()))())))( For the canonical ono-dimensional exponential family, it induces a bijection between the natural parameter and the mean parameter, and we define the Kullback-Leibler divergence two distri- butions with means μa and μl2 as a function d: (111)/2) + R+. Let Conv(p) = Conv(uu, .HK) denote the convex hull of the mean vector, which is the smallest convex set that contains all the means pi,... MKK. At each time t = 1,2, decision maker chooses from distribution Xt,A, VA,- Let F, denote the sigma algebra generated by (A1, XI,A,, Ar, X,,,)) We aim to design a sequential hypothesis testing procedure that consists of a Fi-1-measural sampling policy Tty a slopping rule 7 with respect to Fr, and a F--measurable decision rule (7)) E (feasible, infeasible).
arm A, E {1.... K} and independently draws reward
We now state the formal definition of feasible and infeasible cases.
Definition 3.1. (feasibility and infeasibility) Given fa (F1, "..,.... (Kk), where μa E CRd for i i= 1, K. For any set S, the problem defined above is S-feasible the set S Conv(w) o 0, otherwise, the problem is S-infcasible. When the set only contains a single clement S = {7}, the problem is simply called y-fcasible and 7-infeasible, respectively.
In the one-dimensional case, given a threshold y E R. our objective is to identify whether the unknown mean vector y is y-feasible, which is equivalent to determining if y lies in the closed interval between the smallest mcan reward (p)) = argminggis 14 and the largest mcan reward I (4)) argmaxısigk 14 based the sequential observations while minimizing the expected stopping time 7 and maximizing the probability to correctly identify the result. For simplicity, we assume the threshold y (and the extreme points of the set S, respectively) does not equal to (1,()) and (4)-(4)- This aims to avoid infinite samples to distinguish the maximum and minimum means of the distributions that are too close to the threshold. This assumption can be easily relaxed by introducing a "precision" term 8 to identify an e-optimal design instead (Tocatelli et al. 2016 Russo 2016). Additionally, we further assume the extreme points (or the vertices) of the convex hull Conv (4) are unique.
In the literature, two distinct settings have been extensively studied. In the fixedd-oofidencc setting, given a fixed confidence parameter 8 E (0, 1), the forecaster aims for a strategy that achieves the confidence ō about the quality of the decision rule while minimizing the sample needed, and in the fized-budget setting, the number of exploration rounds is fixed, and the forecaster tries to maximize the probability of making the right decision. We will focus on the finad-confidence setting this paper and introduce the 8-correct strategy.
Definition 3.2. (d-correctness) Let D be a set of distributions on Rdd, Given 8 E (0, 1), we call an identifi- cation strategy 8-correct on the problem class v E DD if with probability at least 1 5, the strategy returns the correct underlying case in a finite expected stopping time, ie., P(E(T]] oo) 1, and when μ is feasible, (7) = feasible) 2 1 - 8, otherwise (( (7) infeasible) 1 6, here L (7) is the decision rule of the stratogy.
Before continuing, pause to introduce some further notations here. We let Na(1)= -t- 1(A, = a} be the number of selections of arm a up to round t, and St) = X,1(A, a} be the sum of the gathered observations from that arm and (t( = S. (t) be their empirical mean.
4 A General Lower Bound
In this section, we extend the general eeformationn-hhoreeeee sample complexity lower bound proved in Garivier & Kaufmann (2016) to work for the one-dimensional convex hull membership problem.
We define Alt((H) to be the set of bandit models where the identification result different from that in μ. and A {w = (wi.-.., ..k) RK w +... ww 1] is a probability simplex of dimension K. The following bound was proved by Garivier & Kaufmann (2016) that E2 [7] 2 T (1)) 5), where
4

---

Published in Transactions on Machine Learning Research (10/2025)
kl(z, v) = x In())) + (1 x) In( 1 denotes the Kullback-Leible divergence in the binary reward case, and
(H) sup inf Ewad(Has da). WEA (E)
Note that kl - 6) ~ 1n(1/0) as + O, the lower bound above directly implies lim infs-so Bull] T (4). This max-min problem was first discussed in the seminal work by [Chrnoofi (1959), and the value of T (1)) can be viewed as the value of a zero-sum sinullaneous--move pure exploration game between two players. The player SUP aims to choose an optimal proportion of allocations w as a mixed strategy, and the adversary player INF tries choose the worst-case alternative arm means that is hard distinguish from the underlying truth to mislead SUP to an incorrect answer.
In(1/8]
This general informationn bound was established to analyze the sample complexity of the Best- Identification problem (Garivier & Kaufmann 2016), and was studied in different scttings (Degenne et al. 2019 2020 along with its popular variant that tackles pure exploration bandit problems with multiple correct answers (Degenne & Koolen, 2019p. To match this general lower bound, the sampling proportion [[E must converge to the minimizer w" E A of the pure exploration game as d + 0. This intuition inspires works on different sampling rules and their corresponding threshold functions B(t. 8) ensure correct
vecommendation with high probability (at least 5) (Degenne et al. 2019 Kaufmann & Koolen 2021 and novel sampling rules to match the lower bound N(t)tt w", where N(t) is the vector of selection counts (Kaufmann et al. 2018). With these considerations in mind, we can establish the sample complexity bound and the asymptotically optimal algorithm for the CHM problem. Specifically, following Degenne et al. Ey.77 20200, say that 8-correct algorithm is asymptotically optimal if for all μr, limsups-o0 In(1/8) - (H))
Without loss of generality, in the one-dimensional CHM problem, we assume that μ1 < #2 S M3 S -..-5 PK-1 < jg. The strict incqualities come from the aforementioned assumption of unique extreme points of (onv(u)) We have the following lower bound of any d-correct algorithm. The proof is provided in the appendix.
Theorem 1. Given a threshold 7 IR, the expected sample complerity E,(T] of any d-correct 1-dimensional E. [r] ln[1/6]
CHM strategy satisfies lim info-0
2 T (M), where
d(pin + Munnn
7 E Conot
T (1)
Σ Eisisk d(wi.))
Y E Conol
and
1 (aEf1,
Y Conv(
w (M)
ic (L.0) d0s1))
Y E Cono(H}
Eisisk 4(ppo)
Surprisingly, the characteristic time and oracle weights that match the general information- sample complexity show completely different behaviors in feasible and infeasible cases. In the feasible case where 7 lies in the convex hull Conv(μ), the algorithm should only sample the arms with minimum and maximum means, while in the infeasible case, the strategy should sample every single arm with specific fraction inversely proportional to the Luilbeck-Leibler divergence between its mean and the threshold yy We remark that the previous work on sequentially testing and learning the lowest mcan (Kaufmann et al.) 2018) demonstrates a similar phenomenon. In essence, this commonality arises from the fact that the one-dimensional CHM problem generalizes the problem of learning the smallest mean (see section 6.1 for details).
5 Algorithm
In this section, we introduce an asymptotically optimal Thompson Saaompson-SSmpping based algorithm for the one- dimensional CHM problem for given threshold 7 E IR.
5

---

Published in Transactions on Machine Learning Research (10/2025)
5.1
Stopping rule
From a learning point of view, the question of stopping at lime is essentially a classical statistical problem: does the past collected information allow us to assess that the threshold lies in or outside the convex hull set (Hnv(H) with risk at most 6? Inspired by Kaufmann et al. (2018), a natural design of the stopping rule is to compare separately each arm to the threshold ry and stop when either one arm lies significantly below y and one arm lies significantly above 7, or all arms lie significantly below 7 or all arms lie significantly above 7.
We denote dt (u, v) d(u, fu S r) and d (u, d(u, 2) 1u 2 v}. We define the first stopping time
when all arms lie significantly above 7/:
it E N [Va N. Na(t)d (Aa (t), 2 N.
Similarly, we define the second stopping time 72 when all arms lie signifieantly below 7:
72 inf E N+I (a(t)d+ (P)(1), x) 2 Thresh(6, (t))).
The third stopping time is when one arm significantly below y and another arm lies significantly above y T3 = it E N+1 02, such that Na, (t)dt (Aa, (t), 2 Thresh Na,
and No. (P)d (t), 2 Thresh(6, (t)))
Here Thresh (!)) is a threshold function to be specified later. Our algorithm stops if any of the three cases happen, ie., it stops at - = min(71, Ta} and returns feasibility or infeasibility based on the case detected. The stopping rule and decision rule ensures that, when the threshold function Thresh(6, NN)()) is carefully designed and the sampling rule guarantees the sampling allocation proportion converges to the solution w of the max-min problem, the algorithm Thompson- CHM is 8-correct.
Lemma 5.1. Let To be stopping rule satisfying TO S T. T is a stopping rule whose threshold function (hresh(ō,r) is non-decreasing in and satisfies the following: Vr 2 ro, Thresh(ō, S in(r/5) olln(100) then for any a and an anytime sampling strategy such that Ni + w" (w), we have lim sups-0 in(1/5) S T (p)
almost surely.
5.2 Sampling rule
Our contribution is sampling rule that extends and generalizes variant of Thompson sampling (called Murphy Sompling) introduedd in Kaulmann et al. (2018) to the one-dimensional CHM problem that ensures the algorithm allocates the optimal proportion to each arm asymptotically, therefore guarantees the asymp- totical optimality by Lemma 5.1 The sampling rule can automatically adapt the asymptotic optimality for both feasible cases and infeasible cases.
We denote by 11, F() the posterior distribution of the mean parameters after rounds. Inspired by Kaufmann ct al. (2018) that introduces Murphy Sampling after Murphy's Law, it performs some conditioning to the "worst event" to learn the smallest mean, introduce Thompson-CH., (Algorithm D to tackle the one-dimensional CHM problem.
Note that the top-two Thompson Sampling conditions the standard Thompson Sampling on the event argmax * argmax 0, with pre-specified probability (Russo 2016), and the Murphy Sampling condi- tions on min(H)) below the threshold (Kaufmann et al. 2018). In contrast, Thompson-CHM/ conditions on the "feasibility" of the underlying mean vector la and in each round t, the algorithm proceeds to pull an arm in the sample 0,- (o.,,.... 02,k) with largest smallest mean based on the previous information F.-1. The posterior is computed explicitly using Bayes' rule with tractable priors (e.g. Beta or uniform). To implement the conditioning, we adopt reject sampling: we repeatedly sample from the unconditioned posterior until a sample satislying feasibility is obtained. The next theorem guarantees that following this sampling procedure, the algorithm [Thompson-CHi CHM] can ensure the sampling proportion of each arm con- verges to the optimal allocation w" asymptotically, regardless of the position of y with respect to the convex hull Conv (u]. Therefore, we can conclude that the algorithm Thompson [CMM is asymptotically optimal in sample complexity.

---

Published in Transactions on Machine Learning Research (10/2025)
Algorithm Thompson-CHM
Input: stopping rule 7 with threshold function Thresh(6, t), risk 6, threshold Y Bernoulli distribution parameter St.
Output: decision rule Ia (u) E {feasible, infeasible} for t= 1, do stopping rule r holds then if r T== T3 then
return L (1) [feasible)
else
return L (H) {infeasible]
end if
end if
Sample 0: = (ft.1.... ... ,0.kk) 11-1 feasible).
Sample B Bernoulli (Bc)
if B ==1 then
Play A, argmin(0.)
else
Play arm A, = argmax(()) (.)
end if
end for
then the algorithm Thompson CHM ensures that N. w' (1L) almost surely for any μ4, and is 8-corvect for the CHM problem.
Theorem 2. 1f 3t amin 0.;)) d(maxx 01:))
d(min -.
We let (t) be the posterior probability of sampling arm at time t, Lec. (ta(t) = P(A, alFi-1), and define (t) and (t) as the summation and mean of (t( over time t.
For the feasible case, the first step the sampling rule performs the same as Thompson Sampling, and the probability of drawing the first arm at time can be written as a weighted sum (with weights 3r and 1- 3.) of the posterior probabilities that the first sample in Or is the maximum and minimum. The asymptotic convergence of sample proportions N1(t) former probability converges to and Bg converges to (m). The proof of (x "x (1) is symmetric.
w (H)) can be derived by the combination of facts that the
For the infeasible case when the lowest mean is larger than threshold or the largest mean is smaller than Y, the core idea of the proof is based on the following proposition, and the complete proofs of Theorem Lemma 5.1 and Theorem 2 are deferred to the appendix.
Proposition 5.2. (Simplified version of Lemma 12 of Russo (2066)) Consider any sampling rule, if for any arm E [K] and all c 0, Σ, (aa( 2 w + cJ < oo, then vbl)) - w².
The above result gives a sufficient condition in which (t() converges to the optimal allocation w", and implies that for any arm a that meets (t) 2 w + c, the arm has been over-allocated compared to the optimal proportion w Hence the total measurements the arm gets must be bounded in order to reduce towards w for optimality. The rest. of the proof is to establish the condition holds for [Thompson-CHM algorithm. We develop the conclusion by showing that, if arm has been over-allocated compared to w then IT, (6r,a < < fr,)) is exponentially small compared to max,. II,(0, < < 0,,,). Based on the known result, for any open set Ô c O, the posterior concentrates at rate II)(@) = exp (-t X E. Va (t)dd(a) Xa)): where v, = ye means 1 In St - 0. Combined with the properties of T (14) in the pure exploration game and the concentration rate of the posterior, can show that there exists 8' > 0 such that,
< B,,0) S expl_1(0 + +t))s (0ra < < (1) max.,b [1 < < 0,D))
where E, is a sequence converging to 0. This implies for any arm a such that J. 2 w + (ta(t) has an exponential decay rate, and Proposition 5.2 immediately yields (5)) + w=.

---

Published in Transactions on Machine Learning Research (10/2025)
It is worth mentioning that one tackle the one-dimensional CHM problem by first checking if y is smaller than the minimumn mean and then checking if ? is larger than the maximum mean. Using the results in Kaufmann et al. (2018). this strategy's sample complexity is at most two times the sample complexity stated in Theorem I However, this procedure has obvious drawbacks compared to our solution. First, this procedure does not generalize to higher dimensions since minimum and maximum means have no analogs higher dimensions. Moreover, even the one-dimensional case, this procodure incurs sub-optimality in its sample complexity in the infeasible case. By sequentially checking the one-sided setting twice, the arm that is farthest away from y will be sampled more than the optimal w"()) (and all other arms will be sampled less than w" (M), respectively), especially when the arms are not spread out significantly. This demonstrates the sub-optimality of this easy solution as our main results indicate an algorithm matching the theoretical lower bound should follow the optimal allocation w w (n). More details are discussed in the appendix.
6 Extensions of the Thompson-CHM Algorithm
6.1 Interval CHM Problem
In this section, we show that our results in Section 0 and Section 5 are fully generalizable to the interval feasibility setting, where our goal to determine the open set (7 x+) intersects with the convex hull set of μ. Here, we allow Y to be oc and y be too for better generalization results.
6.1.1 Asymptotic Optimality and the Algorithm
We build the first result on the general sample complexity lower bound.
Theorem 3. Given thresholds -00 S r S y+ < +o0, let (7", (²,"") arymin in KHEH h 14/_ The expected sample complerity [T] of any d-correct 1-dimensional CHM strategy satisfies lim inf In(1/4) T (p), where
[,//r] 2
a + d(kke))
(+ n Conof [1} + (TT, n Cone [u} =
(#) Eisisk alpert))
and
Mun (u-1) Minge 1
(YT,**) n Conv(r) +
1. (M)) =
(yT, (+), n Conv(
The stopping rule is similar with minor adjustments. To be more specific, we again define the first stopping time Ti when all arms lie significantly above y+:
E = inf e N+ IVa, Na (t)d (Pa(t), 2 (h
Similarly, we define the second stopping time 72 when arms lie significantly below 7
T2 = in E N+ [Va Na (1)dt (Da (1,77)) (t))).
To identify the feasible case, the third stopping time is when one arm is significantly below 7 and another arm lies significantly above 7-:
33 = it N+ 0z, such that Na, (t)d+ (Da, (t), Thresh(8, Na, (t))
and Na, (t)d (fay (t),z)) Thresh(6, Na, (t)))-
Again, the algorithm stops if any of the three cases happens and 5 min(71, 72. T3), and the following lemma ensures that the algorithm CTompson-CHMM 8-correct in the interval feasibility framework.
8

---

Published in Transactions on Machine Learning Research (10/2025)
T. Lemma 6.1. Let To be stopping rule satisfying To T. T is a stopping rule whose threshold function
Thresh(6, r) is non-decreasing in and satisfies the following: Vr 2 ro: Thresh(ō,r) S 1n(r/5) o(In(1 /6))
then for any is and an anytime sampling strategy such that Ni + w" (w), we have lim sups-0 In(178) S T (I)
To
almost surely.
The sampling rule in the interval CHM problem remains the same and we have the next theorem.
d(min0..r") 0,,7"))
Theorem 4. If Be dimin ) dimax - then the algorithm Thompson- CHM ensures that w" (I)) almost surely for any ,a, and is 8-correct for the CHM problem.
6.1.2 Connections with Other State-of-art Results
We comment some important connections of Section 6.1 with the previous state-of-art results in the MAB literature. Trivially, when y = y+, we immediately derive the same results as the CHM problem, implying& a direct generalization to the regular CHM problem. If we set ? = -o, the Bernoulli parameter 3g becomes 0, and this reproduces the same Murphy Sampling results from the state-of-art sequential test paper for learning the minima mean (Kaufmann et al. 2018
On the other hand, by setting y* +00 the interval CHM problem shares the same setup with the thresholding bandit problem with the threshold y In the infeasible case when y is larger than the largest mean in μ, testing if there exists an arm with a mean above the threshold is essentially equivalent to finding all arms with means above the threshold since to identify both questions, one needs to traverse all arms to conclude that the means of all arms are actually below the threshold, and our complexity bound exactly matches the stato-of-art optimal bound of thresholding bandit (Locatelli et al.) 2016]. When μ is feasible, the CHM problem strictly easier than the thresholding bandit, and our complexity strictly smaller than the state-of-art result. Notably, the Thompson- CHM algorithm adapts both feasible and infeasible cases for the thresholding bandit problem without knowing any information the throshold as priori.
6.2 Convex hull membership problem in higher dimensions
We now investigate and discuss the extensions of the Thompson CHM to d-dimensional setting where d 2 2. Before proceeding, we define the vertices set (or extreme point set) Vert(S) of convex set S to be the union of points that do not fall on any line segment connecting any two unique points in set S. The following theorem states that the lower bound for the CHM problem exhibits a shared behavior in all dimensions: in the feasible case, the optimal strategy should only sample arms whose means are extreme points, and in the infeasible case, it should sample all arms.
Theorem 5. Let Vert( Co) = (Par.".. Pmm) be the vertices set of Convluy. Given 7 E Rd where 2 < < 0o, the expected sample complexity [p((T of any 8-correct d-dimensional CHM strategy satisfies lim infa- mm]00]
E,1rl T (H), where
folposs" ( 7 E Conv(11) Eisesk alwam
(n)
& Conv(
and
Em felMos Mmm 7) (a=s.) a(parr)) Eisisk alpi)o))
γ E (4)
(H)
7$ $ Conufp
Here fo, fi, Sm are non-negative real-value functions, and E fi(Mays" Mmm 7) =1
Using Theorem 5 we can generalize the Choompon-CCHMllggeee algortttt to higher dimensions by simply replacing the Bernoulli distribution with a categorical distribution with parameters 3g = f((",,, He... 7) and assuming oracle access the functions ft for < i is We discuss more details of the Thompson- CHM algorithm in d-dimensional setting (d > 2) in the appendix.
9

---

Published in Transactions on Machine Learning Research (10/2025)
7 Numerical results
The paper's main results are reflected in some numerical experiments in this section. We consider Bernoulli bandits with means / = (0.1, 0.2, 0.7)) and á e and we consider Beta(1,1) prior and different y's to compare the sample complexity and sample weights to the theoretical results in both feasible and infeasible cases. We use the threshold function developed in Kaufmann ct al. (2018): Throsh(6, r) = In(1 +
In(r)) + (()()/ and T R+ + 1
is a function defined by T(x) = 2h-1 1 (14a)) ((2) where
h(w) = u- (n)) for u 2 and ((s) = En= n=* We also adopt the empirical implementation of (x) from Kaufmann et al. (0118) in our experiments. The property of the threshold function is verified in Kaufmann
al. (2018).
We first pick different values of y to compare the theoretical sample complexity and the sample complexity of ToThhpsso-CHHy in both feasible and infeasible cases. We choose yy to be (0.15, 0.25, 0.35, 0.45, 0.55, 0.65) for the feasible case and (0.75, 0.8, 0.85, 0.9, 0.95) for the infeasible case. Figure demonstrates the efficiency of the algorithm Thompson-CH.. In both feasible and infcasible cases, the sample complexity of Thompson- CHM matches the theoretical results proved Theorem well for realistic time horizons.
Thampson-Chet
theorelical bound
feeemeicol bound
kampp COmp
4.3
3.5
AB
Figure 1: Sample complexity for different 7's in feasible cases (left) and infeasible cases (right).
Figure provides insights into the asymplotic convergence performance of the sampling proportions (T(T)/T in Thompson- CoomppsonCCM] in both feasible and infeasible cases. In the feasible case when = 0.25, we note that Crampson-CHiy spent the most fraction time sampling the side arms (especially the minimum arm since y is much closer the arm with minimum mean compared the arm with maximum mean). In the infeasible case when 7 = 0.9, we can observe that the sampling proportion of the algorithm almost. matches the theoretical optimal w" w")) in Theorem
We further investigate how the sample complexity of Thompson-CHi CHM scales with the confidence parameter 6, as motivated by the logarithmic dependence predicted by our theoretical results. We choose = 0.4 for feasible case and 7 = 0.9 for infeasible case, and a varying range - log(6) to evenly range between 1 to For each d, we run 100 independent trials and report the average sample complexity. As shown in Figure 3 the empirical sample complexity grows linearly with log(1/6), closely tracking the theoretical lower bound up to constant factor. This supports the sharpness of our bound and confirms that the Thompson-CHM algorithm achieves asymptotic optimal sample complexity in terms of its ó dependence.
8 Discussion and conclusion
This work thoroughly investigates the convex hull membership (CHM) problem in the pure exploration setting. We propose novel asymptotically optimal algorithm tackle this problem, which we refer as Thompson-CHi CHM algorithm. The sampling rule combines the ideas of top-two Thompson sampling (Russo. 2016) and Murphy sampling (Kaufnann al. 2018), and it automatically guarantee the sampled
10

---

Published in Transactions on Machine Learning Research (10/2025)
Thampann-CHM theorbbicl antmaaallcatonn
Thamasnn-CHM
theoretical optinal plcczonn
Figure 2: Empirical proportion of samples compared to optimal allocation w'(H) in feasible cases (left) and infeasible cases (right) estimated using 100 repetitions.
Thomsson-CHe
Figure 3: Sample complexity for different d's in feasible cases (Ieft) and infeasible cases (right).
proportion of each converges to the optimal allocation derived by the information-thooretie lower bound in the one-dimensional setting, regardless of relative position between the threshold and the arm mean set. Moreover, we extend our results to the interval CHM setting that generalizes some important MAB problems in the literature and investigate the extensions of the Thompson-CHMI algorithm in higher dimensions.
Future work will attempt to derive a complete solution d-dimensional CHM problems with broader settings when d 2 2. We conjecture that the sample complexity bounds and the asymptotically optimal algorithm are identical to the one-dimensional case. The current theoretical results reveal challenges in the feasible d-dimensional setting due the complex geometric structure in the "alternative" set. It would be interesting to fully understand the CHM problem in d-dimensional case when d 2 2.
References
Jacob Aberncthy, Pranjal Awasthi, Matthäus Kleindessner, Jamic Morgenstern, and Jie Zhang. Adaptive sampling to reduce disparate performance. arXiv e-prints, pp. arXiv-2006, 2020.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with lincar payoffs. In Inter- national conference on machine learning, pp. 127 137-135. PMLR, 2013.
Hadis Anahideh, Abolfazl Asudeh, and Saravanan Thirumurngnnathan. Fair active learning. Expert Systems with Applications, 199:1 199:116981, 2022.
11

---

Published in Transactions on Machine Learning Research (10/2025)
Peter Auer. Using confidence bounds for exploitattonn-cxploratin trade-offs. Journal of Machine Learning Research, 3(Nov):397-4P) -422, 2002.
Peter Auer, Nicolo Disa-Bianchi, and Paul Fischer. Finile-lime analysis of the multiarmed bandit problem. Machine learning, 47(2) (2)5))235-26; -266, 2002.
Hamsa Bastani and Mohsen Bayati. Online decision making with high high-dimensional covariates. Operations Research, 68(1):776 294, 2020.
Djallel Bouneffouf, Amel Bouzeghoub, and Alda Lopes Gançarski. contextual- bandit algorithm for mobile context-aware recommender system. In International conference on neural information processing, pp. 324 331. Springer, 2012.
Djallel Bouneffouf, Amel Bouzeghoub, and Alda Lopes Gançarski. Contextual bandits for context- based information retrieval. International Conference on Neural Information Processing, pp. 35 42. Springer, 2013.
Djallel Bouncffouf, Romain Laroche; Tanguy Urvoy, Raphael Féraud, and Robin Allesiardo. Contextual bandit. for active learning: Active thompson sampling. In International Conference on Nearal Information Processing, pp. 405 412. Springer, 2014.
Olivier Chapelle and Lihong Ti. An empirical evaluation of thompson sampling. Advances in neural infor- mation processing systems, 24, 2011.
Lijie Chen, Jian Li, and Mingda Qiao. Towards instance optimal bounds for best arm identification. In Conference on Learning Theory, pp. 535-592. PMLR, 2017.
Shouyuan Chen, Tian Lin, Irwin King, Michael R Lyu, and Wei Chen. Combinatorial pure exploration of multi-armed bandits. Aduances in newral information processing systems, 27, 2014.
Herman Chernoff. Sequential design of experiments. The Annals of Mathematical Statistics, 30(3):755-770, 1959.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208 214. JMLR Workshop and Conference Proceedings, 2011.
Rémy Degenne and Wouter M Koolen. Pure exploration with multiple correct answers. Advances in Neural Information Processing Systems, 32, 2019.
Rémy Degenne, Wouter M Koolen, and Pierre Ménard. Non-asymplotic pure exploration by solving games. Advances in Neural Information Processing Systems, 32, 2019.
Rémy Degenne, Pierre Ménard, Xuedong Shang, and Michal Valko. Gamification of pure exploration for linear bandits. In International Conference on Machine Learning, pp. 2432 2442. PMLR, 2020.
Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, and Tong Zhang. Efficient optimal learning for contextual bandits. arXiv preprint arXio:1166. 2369, 2011.
Audrey Durand, Charis Achilleos, Demetris Tacovides, Katerina Strati, Georgios D) Mitsis, and Joelle Pineau. Contextual bandits for adapting treatment in a mouse model of de novo carcinogenesis. In Machine learning for healthcare conference, pp. 67 82. PMLR, 2018.
Rafaela Filippozzi, Douglas S Gonçalves, and Luiz-Rafael Santos. First-order methods for the convex hull membership problem. European Journal of Operational Research, 306(1):17-33 2023.
Aurélien Garivier and Emilic Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pp. 998 1027. PMLR, 2016.
Aurélien Garivier, Pierre Ménard, Laurent Rossi, and Pierre Menard. Thresholding bandit for doso-ranging: The impact of monotonicity. arxiv preprint arXio:1711 17t1101154444 2017.
12

---

Published in Transactions on Machine Learning Research (10/2025)
Xiaoguang Huo and Feng Fu. Risk-aware multi-armed bandit problem with application to portfolio selection. Royal Sociely open science, 4(11))171377, 2017.
MA Jayaram and Hasan Fleyeh. Convex hulls image processing: a scoping review. American Journal of Intelligent Systems, 6(2):48-58, 2016.
Hideaki Kano, Junya Honda, Kentaro Sakamaki, Kentaro Matsuura, Atsuyoshi Nakamura, and Masashi Sugiyama. Good arm identification via bandit feedback. Machine Learning, 108(5):721 745, 2019.
Naama Katzin. Convex hull as a hcuristic. 2018.
Emilie Kaufmann and Wouter M Koolen. Mixture martingales revisited with applications to sequential tests and confidence intervals. J. Mach. Learn. Res., 22:246-1, 2021.
Emilic Kaufmann, Olivier Cappé, and Aurélion Garivier. On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17(1):1-40 2016.
Emilie Kaufmann, Wouter M Koolen, and Aurélien Garivier. Sequential test for the lowest mean: From thompson to murphy sampling. Advances in Newral Information Processing Systems, 31, 2018
Tze Leung Lai, Herbert Robbins, al. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
John Langford and Tong Zhang. The spoch-greedy algorithm for multi-armed bandits with side information. Advances in neural information processing systems, 20, 2007.
Jed Lengyel, Mark Reichert, Bruce R Donald, and Donald P Greenberg. Real-time robot motion planning using rasterizing computer graphics hardware. ACM Siggraph Computer Graphics, 24(4):327 1990.
Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandit approach to personalized news article recommendation. Proceedings of the 19th international conference on World wide web, pp. 661-670, 2010.
Xi Lin, Hui-Ling Zhen, Zhenhua Li, Qing-Fu Fu Zhang, and Sam Kwong. Pareto multi-task learning. Advances in neural information processing systems, 32, 2019.
Andrea Locatelli, Maurilio Gutzeit, and Alexandra Carpentier. An optimal algorithm for the thresholding bandit. problem. In International Conference on Machine Learning, pp. 1690-1698. PMTR, 2016.
David E Losada, Javier Parapar, and Alvaro Barreiro. Multi-armed bandits for adjudicating documents in pooling- evaluation of information retrieval systems. Information Processing & Management, 53(): 1005 1025, 2017.
Natalia Martinez, Martin Bertran, and Guillermo Sapiro. Minimax pareto fairness: A multi objective perspective. In International Conference on Machine Learning, pp. 6755 6764. PMLR, 2020.
Kanishka Misra, Eric M Schwartz, and Jacob Abernethy. Dynamic online pricing with incomplete information using multiarmed bandit experiments. Marketing Science, 38(2):226 252, 2019.
Jonas W Mueller, Vasilis Syrgkanis, and Matt Taddy. Low-rank bandit methods for high-dimensional dy- namic pricing. Advances in Neural Information Processing Systems, 32, 2019.
Fatemeh Nargesian, Abolfazl Asudeh, and HV Jagadish. Tailoring data source distributions for fairness-aware data integration. Proceedings of the VLDB Endowment, 14(11):2519 2532, 2021.
Trung T Nguyen. On the edge and cloud: Recommendation systems with distributed machine learning. In 2021 International Conference on Information Technology (ICTT), pp. 929 934. IEEE, 2021.
Laura Niss, Yuckai Sun, and Ambuj Tewari. Achieving representative data via convex hull feasibility sampling algorithms. or Xiu preprint ar vxXio:2244006600 2022.
13

---

Published in Transactions on Machine Learning Research (10/2025)
Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mothe- matical Sociely, 58(5):527 535, 1952.
Partha Pratim Roy, Umapada Pal, Josep Lladós, and Fumitaka Kimura. Convex hull based approach for multi-oriented character recognition from graphical documents. In 2008 19th international conference pottern recognition, pp. 1-4. IEEE, 2008.
Daniel Russo. Simple bayesian algorithms for best arm identification. In Conference on Learning Theory, pp. 1417-1418. PMLR, 2016.
Weiwei Shen, Jun Wang, Yu-Gang Jiang, and Hongyuan Zha. Portfolio choices with orthogonal bandit learning. In Twenty-fourth intervational joint conference on artificial intelligence, 2.15.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. arXiv preprint 09x:0912..90000 2009.
Tleana Streinu. A combinatorial approach to planar non-colliding robot motion planning. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pp. 443 453. IEEE, 2000.
Liang Tang, Romer Rosales, Ajit Singh, and Deepak Agarwal. Automatic ad format selection via contex- tual bandits. In Proceedings of the 22nd ACM international conference Information & Knowledge Munagement, pp. 1587-1594, 1594, 2013.
Chao Tao, Saúl Blanco, Jian Peng, and Yuan Zhou. Thresholding bandit with optimal aggregate regret. Advances in Newral Information Processing Systems, 32, 2019.
Michal Valko, Nathaniel Korda, Rémi Munos, Thias Flaounas, and Nelo Cristianini. Finite-time analysis of kernelised contextual bandits. Xiv preprint XXix:1309.68699 2013.
Zhengwei Yang and Fernand S Cohen. Image registration and object recognition using affine invariants and convex hulls. IEEE Transactions Image Processing, 8(7):934-946, 1999.
Qian Zhou, XiaoFang Zhang, Jin Xu, and Bin Liang. Large-scale bandit approaches for recommender systems. In International Conference Newral Information Processing, pp. 811-821. Springer, 2017.
A Appendix and Proofs
A.1 Proofs for one-dimensional 7-CHM problem
We provide proofs of Theorem D Lemma 5.1 and Theorem 2 in this Section. As discussed in Section 6.1.2 the interval CHM problem fully generalizes the regular CHM problem, and the analogous results in the interval CHM problem follow the exactly same proofs and can be derived by properly adjusting to 7 and y in this section. Therefore, we only prove Theorem 1 Lemma 5.1 and Thcorem 2 for the case of extensions to the Gaussian bandit setting with unknown variances.
A.1.1 Proof of Theorem
We recall μ4 min(M1, ... _ and μ* max ,,x). In the one-dimensional case, the 7-CHM problem is to test if Conv(u). For the feasible case,
Alt(p) [A]T, (A) = infeasible] = (A] max d < or min X; > 7}.
ISiSK 1SiSK
14

---

Published in Transactions on Machine Learning Research (10/2025)
Therefore,
(n)
max min wE (
Σ
Wad(Haasa da)
max min weA
Σ
Wa wad(Ho: ?),
Σ
wad(Hur
max min (wid(H11 7), wK wxd(Hu:))) witwx=1
d(vi, ())(K)
d(u),7) + d(ux:))
d(ui,)) d(ux,
From the derivation, we can see the optimization problem derives its optimal solution when the strategy only samples arms with maximum and minimum mean with proportions wi - +d(px))) and
d(mi,))
Now we consider the infeasible case. Without loss of generality, assume f1 > (the case when Pk < t can be proved in the same way due to symmotry). In this case,
dug WK -
Alt(p) (1|4 (A) feasible) = (aA1 < Ak}.
and
T (²)) mmxx min
Σ
WaddHHadd
wEb AEAlt(
max min wad(par?) weY 15asK
Eisask k diHa, 7)
We can see from that in the infeasible case, the prcision-makee should sample all arms, and for each arm [1,...,'') it should be sampled with proportion Wa Eisigk 20
aleart)
A.1.2 Proof of Lemma 5.1
Now we proceed to prove Lemma We will make use of the following proposition.
Proposition A.1. (Lemma 22 of Kaufmann al. (2016)) For every 3, 0, if
1
(eIn(1/Br)
e
2 In
B
Bn
then we have
x +o In
Fx In
Now for the feasible case, on the event that
(1) + wi(H), (1) + pr,
and
Nx(1) + w (H), (t)(t) + pK.
t
for any 0, there exists >> O, such that for any > lo, we have
(2, 2 (1 (p)d(())))
and
(xx)) (1 (1)d(x))
15

---

Published in Transactions on Machine Learning Research (10/2025)
Following this,
T S T3
(2)) 2 T (t)) and (K)d (Ax()), 2 Thresh (x)))))
inf (A1 2 Thresh(6, 1) and Nx (t)++ (t) 2 Thresh(6,t))
inf [d[(1 - =)w (1) (((.)))) 7) 2 Thresh(6, 1) and (1-88) E (1-8)tuf
(μ (p)((ux))) 2 Thresh(6, ()
In ))
< inf
t|(1 min (wi (() 7), w (H)d(Ux x)) 2 In
+ 0
(/(1 e)(T (14) 2 In (3) + o In (
())}}
$ inf
Hence we have - =) S In (t) + o (In (t)). By setting 3 (1 - =-)TT(()) (1)
-1 x = = and v) = 8,
Proposition A.1 directly yields
eln [1-s)T (1))
1
S (1 - E)T (1)=-
In
(1 (1-ee {1e) (11)-10
1
In
e
+ In ( + In In
(1 (1)))))))11 ))
(1 - (H)
(1- (1-
1 In
+ o
In
11 - (1)-
Notice that e is arbitrary, we have
lim sup In(1/8)
S T (H).
8-50
For the infeasible case, WLOG we assume #1 > 7 (proof of the symmetric case pk < y is identical). On the event that for any arm a (I, KK}
Na + (H), (t(t) + Ha.
and for arbitrary e > 0, similarly, there exists to, and for any tor we have the following inequality to hold:
(a(t)d (Pa(t), 7) 2 (1 - e)tw" (p)dd(aa)))
Using a parallel statement of the feasible case,
Ta inf (i((ttta (t), 2 Thresh (,))()))
inf (1Va,, No(d (1),())))) (1), 2 Thresh(ō,
inf
f/Vo, (1 2) ww (1)) 7) N 8
In
1
inf
f|(1 E)t min (w] (w)d ?)} N In
+
In
5
isašk
In (3) + In
< inf
f|(1 - 2)
(1)) ())
Following the same statements and by applying Proposition A.1 we have
(1- (w)- In (3) +o In
(1
1 8
Thus, in the infeasible case,
limsup 8
T
S T (T)
In(1/8)
also holds.
16

---

Published in Transactions on Machine Learning Research (10/2025)
A.1.3 Proof of Theorem 2
We again consider feasible and infeasible cases separately. We recall the following notations
(t = P(A, = a(Fr-1), (a(t) (i), and va(() - (t).
Our proof is based on a classic result (see Corollary of Russo 2016 that for any arm a E [K], (a(t) + 0o, then
(t)
Na (t)
a.s
(t)
V (t)
and the following result from Kaufmann et al. (018)).
Proposition A.2. (Theorem 12 of Kaufmann et al. 2018)) Given threshold Yr for any (/1,,.. (K |m S ... pkx, and pı < 7). If we sequentially sample as follows: for any t E N+, sample ~~ 11 (-) minigigk <),, then play the arm At with lowest mean in O.. Then the sampling procedure ensures that the sampling frequencies satisfy
Ni(() +,
and for any 2 a S K,
(t) t
+ 0
almost surely.
Back to our proof, now we consider the feasible case first. In this case, we have μ with property μr < pK. For any N+,
(i( = Belle 01,1 < min 02g feasible) + (1 - 3,)II, 0t.1 > max Oe feasible) ifl
371
Notice that (argmin, Oa 1} and {ux 7 independent events,
11e 02.1 < min Oc. l feasible + 1 a.s.. jzl
And 11, (0t,1 < minjz1 1 00 le feasible) + 11, (0.,1 minjæ1 G1, lle feasible) directly yields
Ile 0c,1 max Otai1 feasible)
0 a.s..
j#1
Combine with the fact that Br + a (11:)++ (UNNr) we get
(u
N.tt) t
+ wi (u). Similarly,
(x((1= = B.TT, 00,
min Ouglia feasible) + $$1
-1- (1 B.) (r. max 0z, j feasible s#1
With the facts that 11, (0e,K < minsæ1 Pegipe feasible) + and 11, (0..k > max Oroipp feasible) + 1 almost surely, this leads to Ng(t) - w (m). Notice that w (41) wx 1, we have shown that N(t) w wH² almost sure in the feasible case.
For the infeasible case, use the following proposition. Proposition A.3. (Simplified version of Lemma of Russo 2016 arm E [K] and all c > 0,
Consider aney sumpling rule, if for any
{v((1)((5())) wa c) oo,
then (1) w².
17

---

Published in Transactions on Machine Learning Research (10/2025)
By applying similar proof strategy in Russo 2016 and Kaufmann et al. (2018), aim to prove the precondition in Proposition 5.2 For any K and 0, consider any round where (ta(() 2 w + e, we have
va(()= = Br 11 1 = argmin, or, b = argmax, dz.., min, 0z, < < max, 01,4)
I1 11,1(mmn,, 01,; < 7 < max; 01,i))
(1 B+) 11 (a argmax, Or.,, = argmin, Pr,i, min, 0r, < 7 < max, Oz.s)
(1-1(ming O2, < max; Or,;)
$ B 1 (0,,a <7 <><<0<>0000 02,b)
11 (0., < < 02,0)
+ (1 - (c) max II (0,,b < < 02,a)
m (0t, < < 02,6)
Following Russo (2016), recall we use H; y/ to demote that L=! In (xy Lv:) + O. Based on any known posterior
concentration rate result (for example, Proposition 5 in Russo (0166) that for any open set c O, the posterior concentrates at the rate II, exp (-émin En a (t)d(Pa: Aa)) Morcover, for any a, b [K].
<><<<>>8>> (0,,a < < (,,6) = exp
- min Σ
va(t)) 0r,a)
0, feasihle
a
Σ Fa(t)d((a:))) )
= exp
-t -tmin
Σ
(a(t)d(Har)) 7),
a:pa b7
This means, there is a sequence 6 -> 0 such that for any 1,
11(0. <> < 0b) exp (-1
(-1 (mii
(-1(min
Σ
(a(()d(pa:7)
Σ va(()d(aas))) #ex))
acpa
a:pa??
which implies
(b) S 8, maX,,6 111,1(00,0 < 0c,b) + (1 (3) IT. 11-1 <9 < Or,a) max.,5 1 < < 02,a) Eowarr Va (a(t)d(Ha: 7). Eaina>y (t) 7))) -Et) S tha (t)c Ex)
I1, 10t,a <7 01,6)
-t min
exp
max, exp -t min
(min Eamer Va(t)d(Ha: 7), Eaposn
eexp
1mminn
-1 min Σ va(())((ua))) 7); Σ va(()d(Ma:7))
Σ (a()))(ua 1)) 28t
min min
Σ
(a(d))(Ma;)))
a:pa St
aijin 27
<expl
min
Σ
(w + c)d(pa: 7),
Σ (w ccd((Has)) 7))
wid(Has :))]
min -min
Σ
wad(Hay 7),
Σ
22t,
ampoSa
A Sexp
-1
emin
d(pa; 7):
Σ d(pa;)) m)) 25t
a:pa>y
When e the (t) is bounded by an exponential decay term, therefore
Σ (t) 2 3 c co.
Therefore, we have (()) wr, and by the conclusions above, N(1)/1 w0.
18

---

Published in Transactions on Machine Learning Research (10/2025)
A.2 d-dimensional CHM problem when d 2
In this section, we provide further details and discussions about potential extensions of CToompoonCCHi algorithm to the higher dimensional case. Before moving forward, we first prove Theorem which gives insight into how to generalize our algorithm.
A.2.1 Proofs of Theorem 5
For the infeasible case when y & Conv(μ), the proof is identical to the one-dimensional case and omit it here.
For the feasible case when E Conv(u)) We assume A E Alt(p) is the optimal solution in the game T (H)) = supwes inf )mf Ea Wad(Ha, For any μu E {MI,-. ,K ; Vert(Conv((I)) we consider two different cases.
Case 1: if t4 E Conv(A), then we have X; Mı; and therefore wi O.
Case 2: if U4 E Conv(u)) Conv(A), in this case, X + μi, WLOG we assume Ml, (2,... , are the means that differs from those in the optimal solution X", i.c. f1,2,--. ... {il & Xji, so 1 S i S s. If w; * O, then d(pi, X > d(pg,>3 A3) for all j E (1,2, .. ,8)( this contradicts with the fact that P4 E Conv(H1, " Mar A1. AsJ.
Combining the statements above, we can see that for all 24's that is not one of the vertices of (4), in order to win the optimization game T" (m)=1, no proportion of the corresponding arm should be sampled.
A.2.2 Potential extension of Thompson-CHin algorithm
As discussed in Section 6.2 the Thompson- Chompson-CHM CHM algorithm outperforms the trivial solution (first checking if y is smaller than the minimum mean and then checking if y is larger than the maximum mean) in both generalizability and optimality. For the generalizability part, the [Thompson-CHie
can possibly generalize to higher dimensional cases and we will discuss more details in this section. For the optimality part, by the results in Kaufmann et al. (208)). the allocations of different arms in the trivial solution are not in align with the optimal w" (1²) and therefore, lead to sub-optimal sample complexity compared to the Thompson- CHM algorithm. For example, in the infeasible case when Y < P1 < ... < μK, by utilizing the result in 2d(pxx
Kaufmann et al. (2018) twice, sampling proportion of arm K is Σx d(u))) +4d(vx-7)-1 and for arm j
satisfying 1 S < --1, 1, its sampling proportion ΣK (dduxx))) This is direct example of the sub-optinality of the trivial solution to the CHM problem in the one-dimensional case.
d(ug)))
Theorem 5 demonstrates an important phenomenon that shares in all dimensions: in the feasible case, the optimal strategy should only sample orms whose means are extreme points, and in the infeasible case, it should sample all arms. And if we can prove analogs of the results for the stopping rule, it is possible to fully extend Thhmpponn-CHil algorithm to higher dimensions. We call X* the point that is on the boundary of Conv(μ) (14) that minimizes the la distance between 7 and 7", and we vertically project all the means "i. KKK to the line that connects 7 and y", and denote the projected points to be .i. .Kk then the d-dimensional distributions with means M1, , are feasible (infeasible) with respect to if and only if the 1-dimensional distributions with means "..... .Pk are fcasible (infcasible) with respect to 7 on the line that connects y and 7² With this important fact, it is possible to prove our conjecture that the analog of [Thompoon- CHM (described below) also asymptotically optimal in higher dimensions using similar techniques in the one-dimensional case.
We now generalize the CCoMpson-HHM algorithm to higher dimensions by replacing the Bernoulli distri- bution with categorical distribution with parameters 3: fil,., Hem. 7). Assuming oracle access to the functions fi for 1 < < k, the analog of [Tommpson-CHM algorithm in d-dimensional case is stated below. The future work is to find the exact form of functions f. and prove the asymptotic optimality of d-dimensional Thompson-CPP algorithm.
19

---

Published in Transactions on Machine Learning Research (10/2025)
Algorithm 2 d-dimensional Thompson-CHM (d22) 2)
Input: stopping rule with threshold function Thresh(6, 1), risk 8, threshold 7, Categorical distribution parameter ,., ,,K. Output: decision rule (1)) E (feasible, infeasible] for == 1. do
stopping rule т holds then if r === T3 then return (H) {feasible]
else
return (1t) finfcasible)
end if
end if
Sample 0, = (fr,1..... 0x,x) 1 feasible).
Sample B Categorical (B1. 3x)
B=i then Play A, =i
end if
end for
20


Reviews:
[{"review_id": "O4ZVzKfmbV", "reviewer": "Reviewer_qY65", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Comments/Suggestions:\n--\nFirstly, I usually do not have many comments regarding the presentation during the review process, but I would like to respectfully note that the overall presentation of the paper needs improvement. I noticed many typos and notation errors throughout the manuscript, including several on the first page. I encourage the authors to carefully proofread the paper. I hope the following comments and suggestions will help improve the clarity and quality of the manuscript.\n\nOn page 1, paragraph 3, the expression argmin_{\\theta \\in theta} (F_1(\\theta), ..., F_m(\\theta)) is problematic. The notation \\theta \\in theta should be corrected to \\theta \\in \\Theta, where \\Theta denotes the parameter set. Moreover, the meaning of “argmin” in the context of a multi-objective optimization problem is unclear and should be defined more rigorously. I also do not understand why the condition \\sum \\lambda_i \\nabla F(\\theta^*) = 0 is claimed to characterize all Pareto-optimal solutions; this point requires further explanation. In addition, it would improve clarity to include curly braces in the hypotheses H_0 and H_1. Lastly, in line 5 of paragraph 3, the notation Conv( {}} appears to contain a formatting error and should be corrected to Conv({}).\n\nOn page 4, paragraph 3, the expression argmax_{1 \\leq k \\leq K} \\mu_i should be corrected to argmax_{1 \\leq i \\leq K} \\mu_i.\n\nIn Definition 3.2, there is a mismatch in notation: \\boldsymbol{\\mu} is the mean vector, while \\mathcal{D} represents the set of distributions. Therefore, it should not be written as \\boldsymbol{\\mu} \\in \\mathcal{D}^K; instead, the correct expression should likely be \\nu \\in \\mathcal{D}^K.\n\nOn page 14, in the line immediately preceding section A.1.2, the index i should range over the set {1, ..., K}, so i \\in \\boldsymbol{\\mu} should be corrected to i \\in \\{1, ..., K\\}.\n\nSince the case of d \\geq 2 is only discussed in the final subsection of the appendix, I suggest the authors explicitly define the problem as one-dimensional in the main text to improve clarity. Moreover, the proposed method appears inherently limited to the one-dimensional setting, and any extension to higher dimensions (d \\geq 2) would likely be highly inefficient, as the number of extreme points can grow exponentially with dimension.\n\nIn the introduction, line 2, the phrase “has make” should be corrected to “has to make.”\n\nRegarding the structure of the introduction, the authors discuss the multi-armed bandit (MAB) problem in the first paragraph and the convex hull membership (CHM) problem in the second, without clearly establishing the connection between them. As someone familiar with MAB but not with CHM, I found the transition unclear. It is only in Section 3 that the reader understands that each distribution is treated as an arm in the MAB framework. It would help if the second paragraph of the introduction explained more clearly how the CHM problem is modeled as a best-arm identification problem within the MAB framework.\n\nIn Section 4, paragraph 2, it is not clear why \\boldsymbol{\\lambda} is treated as a MAB model. From the appendix, it seems to be simply a vector. This should be clarified.\n\nIn Section 5.1, please define the notations N^- and N^+ explicitly.\n\nStrengths and Weakness\n---\nOverall, I find the problem interesting and relevant to the TMLR audience. While the proposed approach and proofs are extensions of existing work (notably Kaufmann et al., 2018), they appear sound and well-motivated. Some limitations of the method include its restriction to the one-dimensional case and the focus on asymptotic guarantees. However, I do not consider these to be significant weaknesses for a TMLR submission. Therefore, I support acceptance of the paper, provided the authors substantially improve its presentation in response to the above comments.\n\n\n\n\n\nMinor Questions\n--\nWhen defining the decision rule I_{\\pi}(\\mu) on page 4, should it not also be a function of \\gamma?\n\nIn Section 3, the authors assume that \\gamma is not equal to any of \\mu_1 through \\mu_K. While it is clear that having \\gamma equal to one of the extreme values causes difficulties, why is it problematic when \\gamma = \\mu_2 or \\mu_{K-1}?\n\nAre there any assumptions made about the distributions \\nu_1, ..., \\nu_K, such as being sub-Gaussian?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the one-dimensional stochastic convex hull membership problem, in which one is given a constant \\gamma and seeks to determine whether \\gamma lies within the convex hull (in this case, the line segment) formed by a set of unknown means \\mu_1, ..., \\mu_K, each corresponding to an unknown distribution. The main idea is to reformulate the problem as a best-arm identification task in the MAB framework, treating each distribution as an arm, and determining whether \\gamma lies between the two extreme means.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see above.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "suE2Svc7On", "reviewer": "Reviewer_WEyF", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*: The problem is a natural extension of prior work; similarly, the authors do a good job establishing their solution in prior solutions. The exposition is generally not hard to follow. And of course, matching upper and lower bounds are a nice addition to the bandit literature.\n\n*Weaknesses*, in descending order of significance:\n\nThe authors use the lower bound for best-arm identification to get a lower bound on the CHM, but do not provide an argument as to why this is possible, either in plain English or formal notation.\n\nIn the experiments,\n- the authors \"consider Beta prior\" but do not specify which member of the family they chose.\n- the authors do not specify their choice of $\\delta$ to derive the blue curves in Figure 1.\n- the authors do not plot sample complexity for varying $\\delta$, even though the analytic results concern limits involving $\\delta\\to 0$. I would have liked to see how fast or slow the upper bound approaches the lower bound.\n\nThe authors should sketch how to derive the posterior $\\Pi_{t-1}(\\cdot| \\mathbf{\\mu} ~\\mathrm{feasible})$.\n\nSome notation could be cleaned up. For example: $d(\\mu_1,\\mu_2)$, \"kl\", and \"KL\" are all used to denote concepts related to the Kullback-Liebler divergence but it is sometimes challenging to distinguish them from one another.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors of this submission define and tackle the problem of convex hull membership (CHM) in the fixed-confidence pure-exploration bandit setting. In the one-dimensional case---which consumes the bulk of the submission---this amounts to determining, with $1-\\delta$ probability, if a given number $\\gamma$ lies between the maximum and minimum means of arms; the cost metric is the sample complexity, which is the number of arm pulls to make the decision.\n\nThe authors (implicitly) claim that a previous lower bound on best-arm identification by Garivier \\& Kaufmann implies a lower bound on CHM; specifically, the authors incorporate the $\\gamma$ value and the induced problem's feasibility. The lower bound is phrased in terms of the limit of an algorithm's sample complexity as failure probability $\\delta$ approaches 0; optimality is said to be achieved when the limit matches the lower bound.\n\nAs the authors discuss in Related Work section, a naive algorithm would take one pass to identify arms whose means lie above $\\gamma$ and another to identify those whose means lie below it. But this approach does not reuse measurements between passes. The algorithm proposed by the authors instead toggles between pulling the empirical maximum and pulling the empirical minimum, in a randomized fashion. Aside from being optimal in terms of sample complexity, the allocation of pulls is also optimal.\n\nThe authors extend their algorithm to two other settings. First, they generalize from determining point membership to determining interval intersection. Second, they generalize to high-dimensional rewards (and therefore means).\n\nThe authors conclude with some experiments that show how close their upper and lower bounds are.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses. There is not much missing content, but it should be added.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "6l0g2dcBp0", "reviewer": "Reviewer_sDAi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## strengths\n* matching upper and lower bounds on sample complexity for this problem\n* a generalized loewr bound for d-dimensional CHM problem which generalizes other pure exploration problems such as thresholding bandits and test for lowest mean.\n\n## weaknesses\n* The technical novelty feels a bit limited since much of the core ideas have been previously developed for finding the lowest mean, and the main add-on here is to do a two-arm sampling scheme to account for both boundaries of an interval. But, it remains unclear how to generalize this to higher dimensions and the authors admit it is left for future work.\n* The experiments also feel a bit limited. It'd be interesting for instance to compare to the naive/easy strategy mentioned on the bottom of p. 7 or to see how the proposed Thompson-CHM fares for higher-dimensional CHM problems, even if the theory is not yet complete there.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies a fixed-confidence pure exploration problem where one interacts with a $K$-armed bandit environment and aims to test the membership of an input element in the convex hull of the unknown reward vector of arms. This generlaizes the thresholding bandit problem and earlier works on finding the lowest mean in a pure exploration setting.\n\nFor one-dimensional rewards, the paper shows an asymptotic lower bound on sample complexity and a mathcing upper bound using a variant of Thompson Sampling. For higher dimensional feedback, they show an analogous lower bound. They also have synthetic experiments validating their theoretical results against the theoretical lower bound.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses above.\n\n## writing suggestions/typos\n* The notation can be a bit confusing in writing the decision rule as $I_{\\pi}(\\mu)$ and then using $\\mu$ in Definition 3.2, as here (at least to my understanding) $\\mu$ is not a test/input vector of means, but represents the true vector of means generating the sampling data from earlier in your setup. The true input whose membership you are testing for is $\\gamma$.\n* $kl(\\delta,1-\\delta)$ should be $KL(\\delta,1-\\delta)$ in 3rd paragraph of p 4.\n* Lemma 5.1 should be Lemma 5.1 in Appendix A.1.\n* It should be specified on top of p. 5 that $\\textbf{N}(t)$ is the vector of selection counts.\n* If I understand correctly, Lemma 5.1 is saying for any Thresh function satisfying the inequality, you'll have asymptotic optimality. This should be made more clear, Thompson-CHM would be desirably introduced before this lemma.\n* Also, it seems like Lemma 5.1 is the main result for Thompson-CHM and so it should be a theorem?\n* what is $\\theta_r$ in Theorem 2? Is this supposed to be $\\theta_t$? This notation is also used in Theorem 4.\n* The way Algorithm 1 is written appears a bit strange. Why is the unknown mean reward vector $\\mu$ an input to the algorithm? How can one compute the posterior without this knowledge?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)