Combinatorial Pure Exploration with Bottleneck Reward Function
Year: 2021

Abstract:
In this paper, we study the Combinatorial Pure Exploration problem with the Bottleneck reward function (CPE-B) under the fixed-confidence (FC) and fixedbudget (FB) settings. In CPE-B, given a set of base arms and a collection of subsets of base arms (super arms) following a certain combinatorial constraint, a learner sequentially plays a base arm and observes its random reward, with the objective of finding the optimal super arm with the maximum bottleneck value, defined as the minimum expected reward of the base arms contained in the super arm. CPE-B captures a variety of practical scenarios such as network routing in communication networks, and its unique challenges fall on how to utilize the bottleneck property to save samples and achieve the statistical optimality. None of the existing CPE studies (most of them assume linear rewards) can be adapted to solve such challenges, and thus we develop brand-new techniques to handle them. For the FC setting, we propose novel algorithms with optimal sample complexity for a broad family of instances and establish a matching lower bound to demonstrate the optimality (within a logarithmic factor). For the FB setting, we design an algorithm which achieves the state-of-the-art error probability guarantee and is the first to run efficiently on fixed-budget path instances, compared to existing CPE algorithms. Our experimental results on the top-k, path and matching instances validate the empirical superiority of the proposed algorithms over their baselines.

heading: 1 Introduction
text: The Multi-Armed Bandit (MAB) problem [25, 30, 4, 2] is a classic model to solve the explorationexploitation trade-off in online decision making. Pure exploration [3, 21, 7, 26] is an important variant of the MAB problem, which aims to identify the best arm under a given confidence or a given sample budget. There are various works studying pure exploration, such as top-k arm identification [17, 21, 7, 24], top-k arm under matriod constraints [9] and multi-bandit best arm identification [18, 7].
The Combinatorial Pure Exploration (CPE) framework, firstly proposed by Chen et al. [11], encompasses a rich class of pure exploration problems [3, 21, 9]. In CPE, there are a set of base arms, each associated with an unknown reward distribution. A subset of base arms is called a super arm, which follows a certain combinatorial structure. At each timestep, a learner plays a base arm and observes a random reward sampled from its distribution, with the objective to identify the optimal super arm
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
with the maximum expected reward. While Chen et al. [11] provide this general CPE framework, their algorithms and analytical techniques only work under the linear reward function and cannot be applied to other nonlinear reward cases.1
However, in many real-world scenarios, the expected reward function is not necessarily linear. One of the common and important cases is the bottleneck reward function, i.e., the expected reward of a super arm is the minimum expected reward of the base arms contained in it. For example, in communication networks [5], the transmission speed of a path is usually determined by the link with the lowest rate, and a learner samples the links in order to find the optimal transmission path which maximizes its bottleneck link rate. In traffic scheduling [31], a scheduling system collects the information of road segments in order to plan an efficient route which optimizes its most congested (bottleneck) road segment. In neural architecture search [32], the overall efficiency of a network architecture is usually constrained by its worst module, and an agent samples the available modules with the objective to identify the best network architecture in combinatorial search space.
In this paper, we study the Combinatorial Pure Exploration with the Bottleneck reward function (CPE-B) which aims to identify the optimal super arm with the maximum bottleneck value by querying the base arm rewards, where the bottleneck value of a super arm is defined as the minimum expected reward of its containing base arms. We consider two popular settings in pure exploration, i.e, fixed-confidence (FC), where given confidence parameter δ, the learner aims to identify the optimal super arm with probability 1− δ and minimize the number of used samples (sample complexity), and fixed-budget (FB), where the learner needs to use a given sample budget to find the optimal super arm and minimize the error probability.
Challenges of CPE-B. Compared to prior CPE works [11, 10, 20], our CPE-B aims at utilizing the bottleneck property to save samples and achieve the statistical optimality. It faces with two unique challenges, i.e., how to (i) achieve the tight base-arm-gap dependent sample complexity and (ii) avoid the dependence on unnecessary base arms in the results, while running in polynomial time. We use a simple example in Figure 1 to illustrate our challenges. In Figure 1, there are six edges (base arms) and three s-t paths (super arms), and the base arm reward w(ei), base arm gap ∆ei,ej and super arm gap ∆M∗,Msub are as shown in the figure. In order to identify the optimal path, all we
need is to pull e1, e2, e4 to determine that e1 is worse than e2 and e4, and e3, e5, e6 are useless for revealing the sub-optimality of M1 and M2. In this case, the optimal sample complexity should be O(( 2∆2e2,e1 + 1∆2e4,e1 ) ln δ−1), which depends on the tight base arm gaps and only includes the critical base arms (e1, e2, e4). However, if one naively adapts existing CPE algorithms [11, 12, 16] to work with bottleneck reward function, an inferior sample complexity of O( ∑ ei,i∈[6]
1 ∆2M∗,Msub ln δ−1) is
incurred, which depends on the loose super arm gaps and contains a summation over all base arms (including the unnecessary e3, e5, e6). Hence, our challenge falls on how to achieve such efficient sampling in an online environment, where we do not know which are critical base arms e1, e2, e4 but want to gather just enough information to identify the optimal super arm. We remark that, none of existing CPE studies can be applied to solve the unique challenges of CPE-B, and thus we develop brand-new techniques to handle them and attain the optimal results (up to a logarithmic factor).
Contributions. For CPE-B in the FC setting, (i) we first develop a novel algorithm BLUCB, which employs a bottleneck-adaptive sample strategy and achieves the tight base-arm-gap dependent sample complexity. (ii) We further propose an improved algorithm BLUCB-Parallel in high confidence regime, which adopts an efficient “bottleneck-searching” offline procedure and a novel “check-nearbottleneck” stopping condition. The sample complexity of BLUCB-Parallel drops the dependence on unnecessary base arms and achieves the optimality (within a logarithmic factor) under small enough δ. (iii) A matching sample complexity lower bound for the FC setting is also provided, which demonstrates the optimality of our algorithms. For the FB setting, (iv) we propose a novel algorithm BSAR with a special acceptance scheme for the bottleneck identification task. BSAR achieves the state-of-the-art error probability and is the first to run efficiently on fixed-budget path instances,
1The algorithmic designs and analytical tools (e.g., symmetric difference and exchange set) in [11] all rely on the linear property and cannot be applied to nonlinear reward cases, e.g, the bottleneck reward problem.
compared to existing CPE algorithms. All our proposed algorithms run in polynomial time.2 The experimental results demonstrate that our algorithms significantly outperform the baselines. Due to space limit, we defer all the proofs to the supplementary material.

heading: 1.1 Related Work
text: In the following we briefly review the related work in the CPE literature. Chen et al. [11] firstly propose the CPE model and only consider the linear reward function (CPE-L), and their results for CPE-L are further improved by [19, 10]. Huang et al. [20] investigate the continuous and separable reward functions (CPE-CS), but their algorithm only runs efficiently on simple cardinality constraint instances. All these works consider directly sampling base arms and getting their feedback. There are also several CPE studies which consider other forms of sampling and feedback. Chen et al. [12] propose the CPE for dueling bandit setting, where at each timestep the learner pulls a duel between two base arms and observes their comparison outcome. Kuroki et al. [23] study an online densest subgraph problem, where the decision is a subgraph and the feedback is the reward sum of the edges in the chosen subgraph (i.e., full-bandit feedback). Du et al. [16] investigate CPE with the full-bandit or partial linear feedback. All of the above studies consider the pure exploration setting, while in combinatorial bandits there are other works [13, 15, 14] studying the regret minimization setting (CMAB). In CMAB, the learner plays a super arm and observes the rewards from all base arms contained in it, with goal of minimizing the regret, which is significantly different from our setting. Note that none of the above studies covers our CPE-B problem or can be adapted to solve the unique challenges of CPE-B, and thus CPE-B demands a new investigation.

heading: 2 Problem Formulation
text: In this section, we give the formal formulation of CPE-B. In this problem, a learner is given n base arms numbered by 1, 2, . . . , n. Each base arm e ∈ [n] is associated with an unknown reward distribution with the mean of w(e) and an R-sub-Gaussian tail, which is a standard assumption in bandits [1, 11, 26, 29]. Let w = (w(1), . . . , w(n))> be the expected reward vector of base arms. The learner is also given a decision class M ⊆ 2[n], which is a collection of super arms (subsets of base arms) and generated from a certain combinatorial structure, such as s-t paths, maximum cardinality matchings, and spanning trees. For each super arm M ∈ M, we define its expected reward (also called bottleneck value) as MinW(M,w) = mine∈M w(e),3 i.e., the minimum expected reward of its constituent base arms, which is so called bottleneck reward function. Let M∗ = argmaxM∈M MinW(M,w) be the optimal super arm with the maximum bottleneck value, and OPT = MinW(M∗,w) be the optimal value. Following the pure exploration literature [17, 11, 10, 12], we assume that M∗ is unique, and this assumption can be removed in our extension to the PAC learning setting (see the supplementary material).
At each timestep, the learner plays (or samples) a base arm pt ∈ [n] and observes a random reward sampled from its reward distribution, where the sample is independent among different timestep t. The learner’s objective is to identify the optimal super arm M∗ fromM. For this identification task, we study two common metrics in pure exploration [21, 7, 26, 10], i.e., fixed-confidence (FC) and fixed-budget (FB) settings. In the FC setting, given a confidence parameter δ ∈ (0, 1), the learner needs to identify M∗ with probability at least 1− δ and minimize the sample complexity, i.e., the number of samples used. In the FB setting, the learner is given a fixed sample budget T , and needs to identify M∗ within T samples and minimize the error probability, i.e., the probability of returning a wrong answer.

heading: 3 Algorithms for the Fixed-Confidence Setting
text: In this section, we first propose a simple algorithm BLUCB for the FC setting, which adopts a novel bottleneck-adaptive sample strategy to obtain the tight base-arm-gap dependent sample complexity.
2Here “polynomial time” refers to polynomial time in the number of base arms n (which is equal to the number of edges E in our considered instances such as s-t paths, matchings and spanning trees).
3In general, the second input of function MinW can be any vector: for any M ∈ M and v ∈ Rn, MinW(M,v) = mine∈M v(e).
Algorithm 1 BLUCB, algorithm for CPE-B in the FC setting
1: Input:M, δ ∈ (0, 1) and MaxOracle. 2: Initialize: play each e ∈ [n] once, and update
empirical means ŵn+1 and Tn+1 3: for t = n+ 1, n+ 2, . . . do 4: radt(e) ← √ 2 ln( 4nt 3
δ )/Tt(e), ∀e ∈ [n] 5: wt(e)← ŵt(e)− radt(e), ∀e ∈ [n] 6: w̄t(e)← ŵt(e) + radt(e), ∀e ∈ [n] 7: Mt ← MaxOracle(M,wt) 8: M̃t ← MaxOracle(M\ S(Mt), w̄t) 9: if MinW(Mt,wt) ≥ MinW(M̃t, w̄t) then 10: return Mt 11: end if 12: ct ← argmine∈Mt wt(e) 13: dt ← argmine∈M̃t wt(e) 14: pt ← argmaxe∈{ct,dt} radt(e) 15: Play pt, and observe the reward 16: Update empirical means ŵt+1(pt) 17: Update the number of samples Tt+1(pt) 18: end for
We further develop an improvement BLUCB-Parallel in high confidence regime, whose sample complexity drops the dependence on unnecessary base arms for small enough δ. Both algorithms achieve the optimal sample complexity for a family of instances (within a logarithmic factor).
3.1 Algorithm BLUCB with Base-arm-gap Dependent Results
Algorithm 1 illustrates the proposed algorithm BLUCB for CPE-B in the FC setting. Here S(Mt) denotes the set of all supersets of super arm Mt (Line 8). Since the bottleneck reward function is monotonically decreasing, for any M ′ ∈ S(Mt), we have MinW(M ′,w) ≤ MinW(Mt,w). Hence, to verify the optimality of Mt, we only need to compare Mt against super arms inM\S(Mt), and this property will also be used in the later algorithm BLUCB-Parallel.
BLUCB is allowed to access an efficient bottleneck maximization oracle MaxOracle(F ,v), which returns an optimal super arm from F with respect to v, i.e., MaxOracle(F ,v) ∈ argmaxM∈F MinW(M,v). For F =M (Line 7), such an efficient oracle exists for many decision classes, such as the bottleneck shortest path [27], bottleneck bipartite matching [28] and minimum bottleneck spanning tree [8] algorithms. For F =M\ S(Mt) (Line 8), we can also efficiently find the best super arm (excluding the supersets of Mt) by repeatedly removing each base arm in Mt and calling the basic maximization oracle, and then selecting the one with the maximum bottleneck value.
We describe the procedure of BLUCB as follows: at each timestep t, we calculate the lower and upper confidence bounds of base arm rewards, denoted by wt and w̄t, respectively. Then, we call MaxOracle to find the super arm Mt with the maximum pessimistic bottleneck value fromM using wt (Line 7), and the super arm M̃t with the maximum optimistic bottleneck value fromM\ S(Mt) using w̄t (Line 8). Mt and M̃t are two critical super arms that determine when the algorithm should stop or not. If the pessimistic bottleneck value of Mt is higher than the optimistic bottleneck value of M̃t (Line 9), we can determine that Mt has the higher bottleneck value than any other super arm with high confidence, and then the algorithm can stop and output Mt. Otherwise, we select two base arms ct and dt with the minimum lower reward confidence bounds in Mt and M̃t respectively, and play the one with the larger confidence radius (Lines 12-14).
Bottleneck-adaptive sample strategy. The “select-minimum” sample strategy in Lines 12-14 comes from an insight for the bottleneck problem: to determine that Mt has a higher bottleneck value than M̃t, it suffices to find a base arm from M̃t which is worse than any base arm (the bottleneck base arm) in Mt. To achieve this, base arms ct and dt, which have the most potential to be the bottlenecks of Mt and M̃t, are the most necessary ones to be sampled. This bottleneck-adaptive sample strategy is crucial for BLUCB to achieve the tight base-arm-gap dependent sample complexity. In contrast, the sample strategy of prior CPE algorithms [11, 12, 16] treats all base arms in critical super arms (Mt and M̃t) equally and does a uniform choice. If one naively adapts those algorithms with the current reward function MinW(M,w), a loose super-arm-gap dependent sample complexity is incurred.
To formally state the sample complexity of BLUCB, we introduce some notation and gap definition. Let N = {e | e /∈ M∗, w(e) < OPT} and Ñ = {e | e /∈ M∗, w(e) ≥ OPT}, which stand for the necessary and unnecessary base arms contained in the sub-optimal super arms, respectively. We define the reward gap for the FC setting as
Algorithm 2 BLUCB-Parallel, an improved algorithm for the FC setting under small δ 1: Input: δ ∈ (0, 0.01) and sub-algorithm BLUCB-Verify. 2: For k = 0, 1, . . . , let BLUCB-Verifyk be the sub-algorithm BLUCB-Verify with δk = δ 2k+1
3: for t = 1, 2, . . . do 4: for each k = 0, 1, . . . such that t mod 2k = 0 do 5: Start or resume BLUCB-Verifyk with one sample, and then suspend BLUCB-Verifyk 6: if BLUCB-Verifyk returns an answer Mout, then return Mout 7: end for 8: end for
Algorithm 3 BLUCB-Verify, sub-algorithm of BLUCB-Parallel
1: Input:M, δV ∈(0, 0.01) and MaxOracle. 2: κ← 0.01 3:M̂∗,B̂sub←BLUCB-Explore(M, κ, MaxOracle) 4: Initialize: play each e ∈ [n] once, and update
empirical means ŵn+1 and Tn+1 5: for t = n+ 1, n+ 2, . . . do 6: radt(e)←R √ 2 ln( 4nt 3 δV )/Tt(e),∀e∈ [n] 7: wt(e)← ŵt(e)− radt(e), ∀e ∈ [n] 8: w̄t(e)← ŵt(e) + radt(e), ∀e ∈ [n] 9: M̃t = MaxOracle(M\ S(M̂∗), w̄t)
10: if MinW(M̂∗,wt) ≥ MinW(M̃t, w̄t) then 11: return M̂∗ 12: end if 13: ct ← argmine∈M̂∗ wt(e) 14: Ft ← {e ∈ B̂sub : w̄t(e) > wt(ct)} 15: pt ← argmaxe∈Ft∪{ct} radt(e) 16: Play pt, and observe the reward 17: Update empirical means ŵt+1(pt) 18: Update the number of samples Tt+1(pt) 19: end for
Definition 1 (Fixed-confidence Gap).
∆Ce =  w(e)−maxM 6=M∗ MinW(M,w), if e ∈M∗, (a)w(e)−maxM∈M:e∈M MinW(M,w), if e ∈ Ñ , (b) OPT−maxM∈M:e∈M MinW(M,w), if e ∈ N.
Now we present the sample complexity upper bound of BLUCB. Theorem 1 (Fixed-confidence Upper Bound). With probability at least 1 − δ, algorithm BLUCB (Algorithm 1) for CPE-B in the FC setting returns the optimal super arm with sample complexity
O ∑ e∈[n] R2 (∆Ce ) 2 ln ∑ e∈[n] R2n (∆Ce ) 2δ  . Base-arm-gap dependent sample complexity. Owing to the bottleneck-adaptive sample strategy, the reward gap ∆Ce (Definition 1(a)(b)) is just defined as the difference between some critical bottleneck value and w(e) itself, instead of the bottleneck gap between two super arms, and thus our result depends on the tight base-arm-level (instead of super-arm-level) gaps. For example, in Figure 1, BLUCB only spends Õ(( 2∆2e2,e1 + ∑ i=3,4,5,6 1 ∆2ei,e1
) ln δ−1) samples, while a naive adaptation of prior CPE algorithms [11, 12, 16] with the bottleneck reward function will cause a loose super-armgap dependent result Õ( ∑ ei,i∈[6]
1 ∆2M∗,Msub ln δ−1). Regarding the optimality, Theorem 1 matches
the lower bound (presented in Section 4) for some family of instances (up to a logarithmic factor). However, in general cases there still exists a gap on those needless base arms Ñ (e3, e5, e6 in Figure 1), which are not contained in the lower bound. Next, we show how to bridge this gap.

heading: 3.2 Remove Dependence on Unnecessary Base Arms under Small δ
text: Challenges of avoiding unnecessary base arms. Under the bottleneck reward function, in each sub-optimal super arm Msub, only the base arms with rewards lower than OPT (base arms in N ) can determine the relationship of bottleneck values between M∗ and Msub (the bottleneck of Msub is the most efficient choice to do this), and the others (base arms in Ñ ) are useless for revealing the sub-optimality of Msub. Hence, to determine M∗, all we need is to sample the base arms in M∗ and the bottlenecks from all sub-optimal super arms, denoted by Bsub, to see that each sub-optimal super
Algorithm 4 BLUCB-Explore, sub-algorithm of BLUCB-Verify, the key algorithm
1: Input:M, κ = 0.01 and MaxOracle. 2: Initialize: play each e ∈ [n] once, and update
empirical means ŵn+1 and Tn+1 3: for t = n+ 1, n+ 2, . . . do 4: radt(e)←R √ 2 ln( 4nt 3
κ )/Tt(e), ∀e∈ [n] 5: wt(e)← ŵt(e)− radt(e), ∀e ∈ [n] 6: w̄t(e)← ŵt(e) + radt(e), ∀e ∈ [n] 7: Mt ← MaxOracle(M,wt) 8: B̂sub,t←BottleneckSearch(M,Mt,wt) 9: if w̄t(e)≤ 12 (MinW(Mt,wt) + wt(e)) for
all e ∈ B̂sub,t then
10: return Mt, B̂sub,t 11: end if 12: ct ← argmine∈Mt wt(e) 13: B̂′sub,t ← {e ∈ B̂sub,t :
w̄t(e) > 1 2 (MinW(Mt,wt) + wt(e))}
14: pt ← argmaxe∈B̂′sub,t∪{ct} radt(e) 15: Play pt, and observe the reward 16: Update empirical means ŵt+1(pt) 17: Update the number of samples Tt+1(pt) 18: end for
arm contains at least one base arm that is worse than anyone in M∗. However, before sampling, (i) we do not know which is M∗ that should be taken as the comparison benchmark, and in each Msub, which base arm is its bottleneck (included in Bsub). Also, (ii) under combinatorial setting, how to efficiently collect Bsub from all sub-optimal super arms is another challenge.
To handle these challenges, we propose algorithm BLUCB-Parallel based on the explore-verifyparallel framework [22, 10]. BLUCB-Parallel (Algorithm 2) simultaneously simulates multiple BLUCB-Verifyk (Algorithm 3) with confidence δ V k = δ/2
k+1 for k ∈ N. BLUCB-Verifyk first calls BLUCB-Explore (Algorithm 4) to guess an optimal super arm M̂∗ and collect a near bottleneck set B̂sub with constant confidence κ, and then uses the required confidence δVk to verify the correctness of M̂∗ by only sampling base arms in M̂∗ and B̂sub. Through parallel simulations, BLUCB-Parallel guarantees the 1− δ correctness. The key component of this framework is BLUCB-Explore (Algorithm 4), which provides a hypothesized answer M̂∗ and critical base arms B̂sub for verification to accelerate its identification process. Below we first describe the procedure of BLUCB-Explore, and then explicate its two innovative techniques, i.e. offline subroutine and stopping condition, developed to handle the challenges (i),(ii). BLUCB-Explore employs the subroutine BottleneckSearch(M,Mex,v) to return the set of bottleneck base arms from all super arms inM \ S(Mex) with respect to weight vector v. At each timestep, we first calculate the best super arm Mt under lower reward confidence bound wt, and call BottleneckSearch to collect the bottlenecks B̂sub,t from all super arms inM\S(Mt) with respect to wt (Line 8). Then, we use a stopping condition (Line 9) to examine if Mt is correct and B̂sub,t is close enough to B̂sub (with confidence κ). If so, Mt and B̂sub,t are eligible for verification and returned; otherwise, we play a base arm fromMt and B̂sub,t, which is most necessary for achieving the stopping condition. In the following, we explicate the two innovative techniques in BLUCB-Explore.
Efficient “bottleneck-searching” offline subroutine. BottleneckSearch(M,Mex,v) (Line 8) serves as an efficient offline procedure to collect bottlenecks from all super arms in given decision classM\S(Mex) with respect to v. To achieve efficiency, the main idea behind BottleneckSearch is to avoid enumerating super arms in the combinatorial space, but only enumerate base arms e ∈ [n] to check if e is the bottleneck of some super arm inM\ S(Mex). We achieve this by removing all base arms with rewards lower than v(e) and examining whether there exists a feasible super arm M that contains e in the remaining decision class. If so, e is the bottleneck of M and added to the output (more procedures are designed to exclude S(Mex)). This efficient offline subroutine solves challenge (ii) on computation complexity (see the supplementary material for its pseudo-codes and details).
Delicate “check-near-bottleneck” stopping condition. The stopping condition (Line 9) aims to ensure the returned B̂sub,t = B̂sub to satisfy the following Property (1): for each sub-optimal super arm Msub, some base arm e such that w(e) ≤ 12 (MinW(M∗,w) + MinW(Msub,w)) is included in B̂sub, which implies that e is near to the actual bottleneck of Msub within 12∆M∗,Msub , and cannot be anyone in Ñ . Property (1) is crucial for BLUCB-Verify to achieve the optimal sample complexity, since it guarantees that in verification using B̂sub to verify M∗ just costs the same order of samples as
using Bsub, which matches the lower bound. In the following, we explain why this stopping condition can guarantee Property (1).
If the stopping condition (Line 9) holds, i.e., ∀e ∈ B̂sub,t, w̄t(e) ≤ 12 (MinW(Mt,wt) +wt(e)), using the definition of BottleneckSearch, we have that for any M ′ ∈M\S(Mt), its bottleneck e′ with respect to wt is included in B̂sub,t and satisfies that
w(e′) ≤ w̄t(e′) (a) ≤ 1
2 (MinW(Mt,wt) + MinW(M
′,wt)) ≤ 1
2 (MinW(Mt,w) + MinW(M
′,w)),
where inequality (a) comes from w̄t(e′) ≤ 12 (MinW(Mt,wt)+wt(e ′)) andwt(e ′)) = MinW(M ′,wt). Hence, we can defer that MinW(M ′,w) ≤ w(e′) ≤ 12 (MinW(Mt,w) + MinW(M
′,w)) for any M ′ ∈M \ S(Mt), and thus Mt = M∗ (with confidence κ). In addition, the returned B̂sub,t satisfies Property (1). This stopping condition offers knowledge of a hypothesized optimal super arm M̂∗ and a near bottleneck set B̂sub for verification, which solves the challenge (i) and enables the overall sample complexity to achieve the optimality for small enough δ. Note that these two techniques are new in the literature, which are specially designed for handling the unique challenges of CPE-B.
We formally state the sample complexity of BLUCB-Parallel in Theorem 2. Theorem 2 (Improved Fixed-confidence Upper Bound). For any δ < 0.01, with probability at least 1− δ, algorithm BLUCB-Parallel (Algorithm 2) for CPE-B in the FC setting returns M∗ and takes the expected sample complexity
O ( ∑ e∈M∗∪N R2 (∆Ce ) 2 ln ( 1 δ ∑ e∈M∗∪N R2n (∆Ce ) 2 ) + ∑ e∈Ñ R2 (∆Ce ) 2 ln (∑ e∈Ñ R2n (∆Ce ) 2 )) .
Results without dependence on Ñ in the dominant term. Let HV = ∑ e∈M∗∪N R2 (∆Ce) 2 and
HE = ∑ e∈[n] R2
(∆Ce) 2 denote the verification and exploration hardness, respectively. Compared to
BLUCB (Theorem 1), the sample complexity of BLUCB-Parallel removes the redundant dependence on Ñ in the ln δ−1 term, which guarantees better performance when ln δ−1 ≥ HEHE−HV , i.e., δ ≤ exp(− HEHE−HV ). This sample complexity matches the lower bound (within a logarithmic factor) under small enough δ. For the example in Figure 1, BLUCB-Parallel only requires Õ(( 2∆2e2,e1
+ 1
∆2e4,e1 ) ln δ−1) samples, which are just enough efforts (optimal) for identifying M∗.
The condition δ < 0.01 in Theorem 2 is due to that the used explore-verify-parallel framework [22, 10] needs a small δ to guarantee that BLUCB-Parallel can maintain the same order of sample complexity as its sub-algorithm BLUCB-Verifyk. Prior pure exploration works [22, 10] also have such condition on δ.
Time Complexity. All our algorithms can run in polynomial time, and the running time mainly depends on the offline oracles. For example, on s-t path instances with E edges and V vertices, the used offline procedures MaxOracle and BottleneckSearch only spend O(E) and O(E2(E + V )) time, respectively. See the supplementary material for more time complexity analysis.

heading: 4 Lower Bound for the Fixed-Confidence Setting
text: In this section, we establish a matching sample complexity lower bound for CPE-B in the FC setting. To formally state our results, we first define the notion of δ-correct algorithm as follows. For any confidence parameter δ ∈ (0, 1), we call an algorithm A a δ-correct algorithm if for the fixed-confidence CPE-B problem, A returns the optimal super arm with probability at least 1− δ. Theorem 3 (Fixed-confidence Lower Bound). There exists a family of instances for the fixedconfidence CPE-B problem, for which given any δ ∈ (0, 0.1), any δ-correct algorithm has the expected sample complexity
Ω ( ∑ e∈M∗∪N R2 (∆Ce ) 2 ln ( 1 δ )) .
This lower bound demonstrates that the sample complexity of BLUCB-Parallel (Theorem 2) is optimal (within a logarithmic factor) under small enough δ, since its ln δ−1 (dominant) term does
Algorithm 5 BSAR, algorithm for CPE-B in the FB setting
1: Input: budget T ,M, and AR− Oracle. 2: ˜log(n)← ∑n i=1 1 i . T̃0←0. A1, R1←∅. 3: for t = 1, . . . , n do 4: T̃t ← ⌈ T−n
˜log(n)(n−t+1) ⌉ 5: Ut ← [n] \ (At ∪Rt) 6: Play each e ∈ Ut for T̃t − T̃t−1 times 7: Update empirical mean ŵt(e), ∀e∈Ut 8: ŵt(e)←∞ for all e ∈ At 9: Mt ← AR-Oracle(⊥, Rt, ŵt)
10: for each e ∈ Ut do 11: if e ∈Mt then 12: M̃t,e←AR-Oracle(⊥, Rt∪{e}, ŵt) 13: else 14: M̃t,e ← AR-Oracle(e,Rt, ŵt)
15: end if 16: // AR-Oracle returns⊥ if the calculated feasible set is empty 17: end for 18: pt←argmax
e∈Ut MinW(Mt,ŵt)−MinW(M̃t,e,ŵt)
19: // MinW(⊥, ŵt) = −∞ 20: if pt ∈Mt then 21: At+1 ← At ∪ {pt}, Rt+1 ← Rt 22: else 23: At+1 ← At, Rt+1 ← Rt ∪ {pt} 24: end if 25: end for 26: return An+1
not depend on unnecessary base arms Ñ either. In addition, if we impose some constraint on the constructed instances, the sample complexity of BLUCB (Theorem 1) can also match the lower bound up to a logarithmic factor (see the supplementary material for details). The condition δ < 0.1 comes from the lower bound analysis, which ensures that the binary entropy of finding a correct or wrong answer can be lower bounded by ln δ−1. Existing pure exploration works [11, 10] also have such condition on δ in their lower bounds.
Notice that, both our lower and upper bounds depend on the tight base-arm-level (instead of superarm-level) gaps, and capture the bottleneck insight: different base arms in one super arm play distinct roles in determining its (sub)-optimality and impose different influences on the problem hardness.

heading: 5 Algorithm for the Fixed-Budget Setting
text: For CPE-B in the FB setting, we design a novel algorithm BSAR that adopts a special acceptance scheme for bottleneck identification. We allow BSAR to access an efficient accept-reject oracle AR-Oracle, which takes an accepted base arm e or ⊥, a rejected base arm set R and a weight vector v as inputs, and returns an optimal super arm from the decision classM(e,R) = {M ∈ M : e ∈ M,R ∩M = ∅} with respect to v, i.e., AR-Oracle ∈ argmaxM∈M(e,R) MinW(M,w). IfM(e,R) is empty, AR-Oracle simply returns ⊥. Such an efficient oracle exists for many decision classes, e.g., paths, matchings and spanning trees (see the supplementary material for implementation details).
BSAR allocates the sample budget T to n phases adaptively, and maintains the accepted set At, rejected set Rt and undetermined set Ut. In each phase, we only sample base arms in Ut and set the empirical rewards of base arms in At to infinity (Line 8). Then, we call AR-Oracle to compute the empirical best super arm Mt. For each e ∈ Ut, we forbid Rt and constrain e inside/outside the calculated super arms and find the empirical best super arm M̃t,e from the restricted decision class (Lines 12,14). Then, we accept or reject the base arm pt that maximizes the empirical reward gap between Mt and M̃t,e, i.e., the one that is most likely to be in or out of M∗ (Line 18).
Special acceptance scheme for bottleneck and polynomial running time. The acceptance scheme ŵt(e)←∞ for all e ∈ At (Line 8) is critical to the correctness and computation efficiency of BSAR. Since At and Rt are not pulled in phase t and their estimated rewards are not accurate enough, we need to avoid them to disturb the following calculation of empirical bottleneck values (Lines 9-18). By setting the empirical rewards of At to infinity, the estimation of bottleneck values for sub-optimal super arms Msub avoids the disturbance of At, because each Msub has at least one base arm with reward lower than OPT and this base arm will never be included inAt (conditioned on high probability events). As for M∗, its empirical bottleneck value can be raised, but this only enlarges the empirical gap between M∗ and Msub and does not affect the correctness of the choice pt (Line 18). Hence, this acceptance scheme guarantees the correctness of BSAR in bottleneck identification task.
Compared to existing CPE-L algorithm CSAR [11], they force the whole set At inside the calculated super arms in the oracle, i.e., replacing Lines 12,14 with AR-Oracle(At, Rt ∪ {e}, ŵt) and AR-Oracle(At∪{e}, Rt, ŵt), and deleting Line 8. Such acceptance strategy incurs exponential-time
complexity on s-t path instances,4 and only works for the linear reward function, where the common partAt between two compared super arms can be canceled out. If one naively applies their acceptance strategy to our bottleneck problem, the common part At is possible to drag down (dominate) the empirical bottleneck values of all calculated super arms (Lines 9,12,14) and their empirical gaps will become all zeros (Line 18), which destroys the correctness of the choice pt in theoretical analysis.
BSAR is the first to run in polynomial time on fixed-budget s-t path instances among existing CPE algorithms, owing to its skillful acceptance scheme and the simplified AR-Oracle (only work with one accepted base arm instead of At). Specifically, for E edges and V vertices, the time complexity of AR-Oracle is O(E(E + V )) and BSAR only spends O(E2(E + V )) time in decision making.
Now we give the definitions of fixed-budget reward gap and problem hardness, and then formally state the error probability result of BSAR. For e ∈ M∗, ∆Be = OPT −maxM∈M:e/∈M MinW(M,w), and for e /∈M∗, ∆Be = OPT−maxM∈M:e∈M MinW(M,w). Let ∆B(1), . . . ,∆ B (n) be the permutation of ∆B1 , . . . ,∆ B n such that ∆ B (1) ≤ · · · ≤ ∆ B (n), and the fixed-budget problem hardness is defined as HB = maxi∈[n] i
(∆B (i)
)2 . Let ˜log(n) = ∑n i=1 1 i .
Theorem 4 (Fixed-budget Upper Bound). For any T > n, algorithm BSAR (Algorithm 5) for CPE-B in the FB setting uses at most T samples and returns the optimal super arm with the error probability bounded by
O ( n2 exp ( − T − n
˜log(n)R2HB
)) .
Compared to the uniform sampling algorithm, which plays all base arms equally and has O(n exp(− T
R2n∆−2min )) error probability with ∆min = OPT −maxM 6=M∗ MinW(M,w), Theorem 4
achieves a significantly better correctness guarantee (when ∆Be > ∆min for most e ∈ [n]). In addition, when our CPE-B problem reduces to conventional K-armed pure exploration problem [7], Theorem 4 matches existing state-of-the-art result in [7]. To our best knowledge, the lower bound for the fixed-budget setting in the CPE literature [11, 20, 23, 16] remains open.
Our error probability analysis falls on taking advantage of the bottleneck property to handle the disturbance from the accepted arm set (which are not pulled sufficiently) and guaranteeing the estimation accuracy of bottleneck rewards. The differences between our analysis and prior analysis for CSAR [11] are highlighted as follows: (i) Prior analysis [11] relies on the linear property to cancel out the common part between two super arms when calculating their reward gap, in order to avoid the disturbance of accepted arms. In contrast, to achieve this goal, we utilize the special acceptance scheme of BSAR to exclude all accepted arms in the calculation of bottleneck rewards, which effectively addresses the perturbation of inaccurate estimation on accepted arms. (ii) Prior analysis [11] mainly uses the “exchange sets” technique, which only works for the linear reward function and leads to the dependence on the parameter of decision class structures. Instead, our analysis exploits the bottleneck property to establish confidence intervals in the base arm level, and effectively avoids the dependence on the parameter of decision class structures.

heading: 6 Experiments
text: In this section, we conduct experiments for CPE-B in FC/FB settings on synthetic and real-world datasets. The synthetic dataset consists of the s-t path and matching instances. For the s-t path instance, the number of edges (base arms) n = 85, and the expected reward of edges w(e) = [0, 10.5] (e ∈ [n]). The minimum reward gap of any two edges (which is also the minimum gap of bottleneck values between two super arms) is denoted by ∆min ∈ [0.4, 0.7]. For the matching instances, we use a 5× 3 complete bipartite graph, where n = 15, w(e) = [0.1, 1.08] and ∆min ∈ [0.03, 0.07]. We change ∆min to generate a series of instances with different hardness (plotted points in Figures 2(a),2(b),2(e)). In terms of the real-world dataset, we use the data of American airports and the number of available seats of flights in 2002, provided by the International Air Transportation Association database (www.iata.org) [6]. Here we regard an airport as a vertex and a direct flight connecting two airports as an edge (base arm), and also consider the number of available seats of a flight as the expected reward of an edge. Our objective is to find an air route connecting the starting and destination airports which maximizes the minimum number of available seats among its passing
4Finding a s-t path which contains a given edge set is NP-hard. See the supplementary material for its proof.
flights. In this instance, n = 9 and w(e) ∈ [0.62, 1.84]. We present the detailed graphs with specific values of w(e) for the s-t path, matching and real-world air route instances in the supplementary material.
In the FC setting, we set a large δ = 0.005 and a small δ = exp(−1000), and perform 50 independent runs to plot average sample complexity with 95% confidence intervals. In the FB setting, we set sample budget T ∈ [6000, 15000], and perform 3000 independent runs to show the error probability across runs. For all experiments, the random reward of each edge e ∈ [n] is i.i.d. drawn from Gaussian distribution N (w(e), 1). Experiments for the FC setting. We compare our BLUCB/BLUCB-Parallel with three baselines. BLUCB− is an ablation variant of BLUCB, which replaces the sample strategy (Lines 12-14) with the one that uniformly samples a base arm in critical super arms. CLUCB-B [11] is the state-of-the-art fixedconfidence CPE-L algorithm run with bottleneck reward function. UniformFC is a fixed-confidence uniform sampling algorithm. As shown in Figures 2(a)-2(c), BLUCB and BLUCB-Parallel achieve better performance than the three baselines, which validates the statistical efficiency of our bottleneckadaptive sample strategy. Under small δ, BLUCB-Parallel enjoys lower sample complexity than BLUCB due to its careful algorithmic design to avoid playing unnecessary base arms, which matches our theoretical results.
Experiments for the FB setting. Our BSAR is compared with four baselines. As an ablation variant of BSAR, BSR removes the special acceptance scheme of BSAR. CSAR-B [11] is the state-of-the-art fixed-budget CPE-L algorithm implemented with bottleneck reward function. CUCB-B [14] is a regret minimization algorithm allowing nonlinear reward functions, and in pure exploration experiments we let it return the empirical best super arm after T (sample budget) timesteps. UniformFB is a fixedbudget uniform sampling algorithm. One sees from Figures 2(d)-2(f) that, BSAR achieves significantly better error probability than all the baselines, which demonstrates that its special acceptance scheme effectively guarantees the correctness for the bottleneck identification task.

heading: 7 Conclusion and Future Work
text: In this paper, we study the Combinatorial Pure Exploration with the Bottleneck reward function (CPE-B) problem in FC/FB settings. For the FC setting, we propose two novel algorithms, which achieve the optimal sample complexity for a broad family of instances (within a logarithmic factor), and establish a matching lower bound to demonstrate their optimality. For the FB setting, we propose an algorithm whose error probability matches the state-of-the-art result, and it is the first to run efficiently on fixed-budget path instances among existing CPE algorithms. The empirical evaluation also validates the superior performance of our algorithms. There are several interesting directions worth further research. One direction is to derive a lower bound for the FB setting, and another direction is to investigate the general nonlinear reward functions.
Acknowledgments and Disclosure of Funding
The work of Yihan Du is supported in part by the Technology and Innovation Major Project of the Ministry of Science and Technology of China under Grant 2020AAA0108400 and 2020AAA0108403. Yuko Kuroki is supported by Microsoft Research Asia and JST ACT-X 1124477.

Review summaries:
The paper studies the extension of a combinatorial bandits problem studied by S. Chen et al, NeurIPS 2014. The extension here is to consider  (expected) reward as the minimum reward of the elements of a set rather than a linear combination as studied in Chen et al.   We are given a set of super-arms (which may overlap). The reward function associated with each super-arm is the minimum expected value of the reward associated with each of the base-arms in that super-arm. The problem is to find the best super-arm, the one with the maximal expected reward.   The paper provides algorithms, and upper and lower bounds on sample complexity for a given confidence bound, and error probability bound for a given budget.    The paper (including the supplemental material) is densely written with sparse discussion of the results. A table of notations would considerably help the reader.   Reported simulation results are limited.   Some of the motivating examples need better articulation (e.g. bottleneck path problem). 

The authors are interested in the combinatorial pure exploration problem, in which one aims at identifying the best "super arm" (a subset of "base arms") among a decision class that can arise from a certain combinatorial structure. In this paper, they focus on the combinatorial pure exploration problem in the specific case where the reward of a super arm is the minimum of the rewards of the base arms it contains. This very specific function -- called the bottleneck reward function -- raises very specific challenges when solving the combinatorial pure exploration problem.  The authors explain that none of the existing work on pure exploration or on multi armed bandits give good guarantees in the specific case of the bottleneck function, and propose tailor-made algorithms that exploit the specificities of the said function to reach optimal guarantees, both in the fixed-confidence setting and in the fixed-budget setting.

The authors focus on the Combinatorial Pure Exploration problem with bottleneck rewards (CPE-B) and consider two settings: fixed-confidence (FC) and fixed-budget (FB). They argue that the existing CPE algorithms cannot be adapted to solve the challenges arisen in CPE-B.  Then, for the FC setting, the paper proposes two algorithms, called BLUCB and BLUCB-Parallel, that provides optimal (within a logarithmic factor) sample-complexity for several important instances. Moreover, a lower-bound is also deduced that matches the guarantee of BLUCB-Parallel. For the FB setting, the authors provide an algorithm, called BSAR, that achieves the same error probability guarantee as that of the state-of-the-art work. The authors also claim that BLUCB-Parallel and BSAR are efficiently implementable in several important instances such as $s$-$t$ path, maximum cardinality matchings, spanning trees, etc.