Combinatorial Pure Exploration with Bottleneck Reward Function
Authors: Yihan Du
Yuko Kuroki
Wei Chen
Venue: NeurIPS 2021 Poster (2021)
Keywords: combinatorial pure exploration
bottleneck reward function
combinatorial bandits

Abstract: In this paper, we study the Combinatorial Pure Exploration problem with the Bottleneck reward function (CPE-B) under the fixed-confidence (FC) and fixed-budget (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.

Combinatorial Pure Exploration with Bottleneck Reward Function
Yihan Du IIS, Tsinghua University
Yuko Kuroki
The University of Tokyo Bockyo/Ri /RIKEN
Beijing, China
Tokyo, Japan yukok@is u-tokyo. ac. ac.jp
duyh18@maile www.s/ammaasssssssnuaaaaaa.. edu. cn
Wei Chen
Microsoft Research
Beijing, China
weic@microsoft. com
Abstract
In this paper, we study the Combinatorial Pure Exploration problem with the Bottleneck reward function (CPE-B) under the exeddcoofideece (FC) and fixed- budget (FB) settings. In CPE-B, given set of base arms and collection of subsets of base arms (super arms) following a certain combinatorial constraint, 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 practical scenarios such as network routing in communication networks, and its unique challenges fall on how to utilize the bottleneck property save samples and achieve the statistical optimality. None the existing CPE studies (most of them assume linear rewards) be adapted to solve such challenges, and thus we develop brand-new techniques to handle them. For the FC setting, propose novel algorithms with optimal sample complexity for broad family instances and establish a matching lower bound to demonstrate the optimality (within a logarithmic factor). For the FB setting, we design algorithm which achieves the state-of-the-ar error probability guarantee and is the first to run efficiently fixed-budge path instances, compared 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.
Introduction
The Multi-Armed Bandit (MAB) problem [25, 30, 4, 2] is a classic model to solve the exploration
exploitation trade-off in online decision making. Pure exploration [3, 21, 26] is an important variant of the MAB problem, which aims to identify the best arm under a given confidence or given sample budget. There various works studying pure exploration, such 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 al. [11], encom- passes a rich class of pure exploration problems [3, 21, 9]. In CPE, there set of base arms, each associated with an unknown reward distribution. A subset of base arms called a super arm, which follows certain combinatorial structure. At each timestep, a learner plays base arm and observes random reward sampled from its distribution, with the objective to identify the optimal super arm
35th Conference on Neural Information Processing Systems (NcurIPS 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.
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.c., 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], 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, fixedcoofidennt (FC). where given confidence parameter 6, the learner aims to identify the optimal super arm with probability 1 - 6 and minimize the number of used samples (sample complexity), and fixedbudger (FB), where the learner needs to use a given sample budget to find the optimal super arm and minimize the error probability.
wie.)-0.2
wfe.]-0.4
Challenges of CPE-B. Compared to prior CPE works [11, 10, 20J, our CPE-B aims at utilizing the bottleneck prop- erty 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/ 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(e)), base arm gap Ser.e and super arm gap A..Ma., are as shown in the figure. In order to identify the optimal path, all we need is to pull é1, 62, to determine that ei is worse than 62 and 64, and e3, es; ép are useless for revealing the sub-optimality of Mj and M2. In this case, the optimal sample complexity should be 6 which depends on the tight base arm gaps and only includes the critical O(( - 2 F4.91
M- - tes, sd) (optimal)
w(ee)-0.6
M ex)
M, [o, e.)
w(ei)-f.1
wie:)=0.5
w(e))-0.3
Base amn gup:
Deya - 0.2 0.1 - 0.1
Aece =..10.11 0.1 = 0.3
Super arm gap:
A.. = min(0.2 0.1} - m0. 0.63 = 0.1
AM. - m0.... 0.4] min(0.1. 0.,, 0.5) - 0.1
Let M......
del AM.. Av..
Figure 1: Illustrating example.
base arms (e1, e4). However, if one naively adapts existing CPE algorithms [11, 12, 16] to work with bottleneck reward function, an inferior sample complexity of O(Ee, A Myp
1 In 8 (11-1) is
incurred, which depends on the loose super arm gaps and contains a summation over all base arms (including the unnecessary c3, Es, eg). 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, ea 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 bottleneck-adaptiv sample strategy and achieves the tight base-arm-gap dependent sample complexity. (ii) We further propose an improved algorithm BLUCB-Parall regime, which adopts an efficient "bottleneck-searchinn"" searching" offline procedure and a novel scheck-nears bottleneck" stopping condition. The sample complexity of BLUCB-Paralles drops the dependence on unnecessary base arms and achieves the optimality (within a logarithmic factor) under small enough 8. (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 error probability and is the first to run efficiently on fixed-budget path instances,
in high confidence
'The algorithuic designs and analytical tools (e.g., symmetric difference and exchange set) in [1I] all rely on the linear property and cannot be applied to nonlinear reward cases, e.g. the bottleneck reward problem.
2

---

compared to existing CPE algorithms. All our proposed algorithms run in polynomial time." The experimental results demonstrate that our algorithms significantly outperform the baselines. Due to space limit, we defer all the proofs to the supplementary material.
1.1 Related Work
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 also several CPE studies which consider other forms of sampling and feedback. Chen et al. [12] propose the CPE for ducling bandit setting, where at each timestep the learner pulls a duel between two base arms and observes their comparison outcome. Kuroki al. [23] study an online densest subgraph problem, where the decision is 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 bunl-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 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 new investigation.
Problem Formulation
In this section, give the formal formulation of CPE-B. In this problem, a learner is given base arms numbered by 1.2..... n. Each base arm e E [n] is associated with an unknown reward distribution with the mean of wie) and R-sub-Gaussian tail, which is standard assumption in bandits [1, 11, 26, 29]. Let w = (w(1), u())) be the expected reward vector of base arms. The learner is also given decision class M S 2(x), which is 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 E .M, we define its expected reward (also called bottleneck value) as MinW(M, w) millee w(e),² i..., the minimum expected reward of its constituent base arms, which is so called bottleneck reward function. Let M. = argmax M EM 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 E [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, from M.
For this identification task, we study two common metrics in pure exploration [21, 7, 26, 10], i.e., ceeeddeonieeece (FC) and ó E (0, 1), the learner needs to identify M, with probability at least 1 - 5 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.
(FB) settings. In the FC setting, given a confidence parameter
3 Algorithms for the Fixed-Confidence Setting
In this section, we first propose simple algorithm BLUCB for the FC setting, which adopts novel bottleneck-adaptive sample strategy to obtain the tight base-arm-gap dependent sample complexity.
Here "polynomial time" refers to polynomial time in the number of base arms (which equal to the number edges E' in our considered instances such as s-t paths, matchings and spanning trees).
'n general, the second input of function Mink can be any vector: for any M E .M and v E R". MinW(M, v) mineee v(e).
3

---

Algorithm 1 BLUCE, algorithm for CPE-B in the FC setting
1: Input: M, E (0, 1) and MaxOracle.
9: if Min w,) 2 MinW wi) then
2: Initialize: play each e E [n]] once, and update
10: return M,
empirical means V x+1 and Tu+1
11:
end if
3: for t.= n +,,1,,1 n2
2. do
12:
C: < argmin WA
4: rad,(e) + - 2n( Ante
5 )TT, Ve E [n]
13:
dę <- argmin, w. (c)
14:
Pr f argmax red
5:
[x(e) (e) (e), Ve E [n]
6:
Wi (e) <- (e((e) + (e), Ve E [m)
15:
Play Pt. and observe the reward
16: Update empirical means u (px)
7:
Mr f- MaxOracle
17: Update the number of samples T (pe)
8:
M, f MaxOracle(M (SM)). wi)
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 8. 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(M)) denotes the set of all supersets of super arm M, (Line 8). Since the bottleneck reward function is monotonically decreasing, for any M' E (M,), we have MinW [M', w) S MinW M2, w). Hence, to verify the optimality of M,, we only need to compare Mj against super arms in M (S(M), and this property will also used in the later algorithm Parall.
BLUCB is allowed to access an efficient bottleneck maximization oracle MaxOracle(F, v). which returns an optimal super arm from F with respect v, i.e., MaxOracle(F, v) argmaxse. MinW MM, 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(M) (Line 8), we can also efficiently find the best super arm (excluding the supersets of M,) by repeatedly removing each base arm in M,, and calling the basic maximization oracle, and then selecting the one with the maximum bottleneck value.
We describe the procedure of BLUCB follows: at each timestep t, calculate the lower and upper confidence bounds of base arm rewards, denoted by w, and w, respectively. Then, we call MaxOracle find the super arm M, with the maximum pessimistic bottleneck value from M using w, (Line 7), and the super arm M, with the maximum optimistic bottleneck value from M \ (S(M) using W. (Line 8). Mr, and M, are two critical super arms that determine when the algorithm should stop or not. If the pessimistic bottleneck value of M, is higher than the optimistic bottleneck value of Mr (Line 9), we can determine that M, has the higher bottleneck value than any other super arm with high confidence, and then the algorithm can stop and output M,. Otherwise, we select two base arms or and de with the minimum lower reward confidence bounds in M, and M, respectively, and play the one with the larger confidence radius (Lines 12-14).
Bottleneck- addative sample strategy. The "select-minimum" sample strategy in Lines 12- 14 comes from an insight for the bottleneck problem: to determine that M, has higher bottleneck value than Me it suffices to find a base arm from M, which is worse than any base arm (the bottleneck base arm) in M,. To achieve this, base arms e and de, which have the most potential be the bottlenecks of M, and Mr, are the most necessary ones to be sampled. This bottleneck adaptivee sample strategy is crucial for BLUCB to achieve the tight base-arm-gat gap dependent sample complexity. In contrast, the sample strategy of prior CPE algorithms [11, 12, 16] treats all base arms in critical super arms (M, and M,) equally and does uniform choice. If one naively adapts those algorithms with the current reward function MinW( M, w), a loose super-arm-gal dependent sample complexity is incurred.
To formally state the sample complexity of BLUCB, we introduce some notation and gap definition. Let N = {e & M., w(e) < OPT) and Ñ: = {e & M,,w(e) 2 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

---

Algorithm 2 BLUCB-Parallel, an improved algorithm for the FC setting under small d Input: E 00,0.01) and sub-algorithm BLUCB-Veriite
2: For k: = 0, o...... let BLUCB-Verify, be the sub-algorithm BLUCB-Verify with òş 2 do 0, I.... such that mod 2* do 5: Start or resume BLUCB-Verify, with one sample, and then suspend BLUCB-Verify;
3: for tr = 1,2,,.... ...
4: for each
6: if BLUCB-Verify, returns an answer Maut, then return Maut
7: end for
8: end for
Algorithm 3 BLUCE-Verify. sub-algorithm of BLUCH-Parallel
1: Input: M,, 8 (0,0.01) and MaxOracle.
10:
if MinW M,, w,,) MinW(M,, (), then
2: λ + 0.01
11:
return M,
3:M. BaM,.BBubt-BLCC BLUCB-LUBBBBE BLuCB-BBUCB-Eppe-e- Explore MaxOracle
12:
end if
4: Initialize: play each E [n] once, and update
13:
Ct < argmin (e
empirical means Wn+1 and Tn+1
14:
Fi (E Babb (ū(()) > w,(c))
5: for t n + 1, ..... do
15:
Pt <- argmax.E radr(e)
6:
rad Rv 2 In( Ant2
8² (e), [e w + we(e) - (e), Ve E [n]
16:
Play Pt. and observe the reward
17: Update empirical means W (Pt)
7:
8: (e) (e(e) + (e), Ve [n]
18: Update the number of samples Te+ (pt)
9: Mj MaxOracle(M S(M.), w.
19: end for
Definition (Fixed-confidence Gap).
w(e) m MinW(M, w), if E Mc,
(a) (b)
A
w(e) MMeM MinW M, w), if N,
OPT M.eMM MinW(M, w), i
Now we present the sample complexity upper bound of BLUCB.
Theorem (Fixed-confidence Upper Bound). With probability at least algorithm BLUCB (Algorithum for CPE-B in the FC setring returns the optimal super arm with sample complexity
R
Ran
Σ eE(N]
Σ EE(n]
A
(A
Base-arm-gap dependent sample complexity. Owing to the bottleneck-adaative sample strategy, the reward gap A (Definition ((a)(b)) is just defined 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-armllevel (instead of super-arm- level) gaps. For example, in Figure 1, Ei=3,4.56 _ In samples, while a naive adaptation of prior CPE algorithms [11, 12, 16] with the bottleneck reward function will cause loose super-arm- In 8 -). Regarding the optimality, Theorem I matches gap dependent result Ô(Σ.. ((Eesse])) Ar.
BLUCB only spends 0(
69.51
the lower bound (presented in Section 4) for some family of instances (up logarithmic factor). However, in general cases there still exists gap those needless base arms N (cx, cs, cs in Figure 1), which are not contained in the lower bound. Next, we show how to bridge this gap.
3.2 Remove Dependence on Unnecessary Base Arms under Small
Challenges of avoiding unnecessary base arms. Under the bottleneck reward function, in each sub-optimal super arm Mab.- only the base arms with rewards lower than OPT (base arms in N) can determine the relationship of bottleneck values between M. and Maub (the bottleneck of Mab is the most efficient choice to do this), and the others (base arms in N) are useless for revealing the sub-optimalitt of Manh. Hence, to determine Ma, we need to sample the base arms in M, and the bottlenecks from all sub-optimal super arms, denoted by Babb to that each sub-optimal super
5

---

Algorithm 4 BLUCB-Explore, sub-algorithm of BLUCB-Verify, the key algorithm
1: Input: M, x 0.01 and MaxOracle.
10:
return M,, Bsub.t
2: Initialize: play each E [n]] once, and update
11:
end if
empirical means vi 2 and Tn+1
12:
Ct argmin m2(()
3: for f mt=n= 1, 2. do
13:
Blabb + feE Bunh.t
4: red;(e)++ RV In( int
)/T;(e), [eE [,(e)) - (e(e) - (e), Ve in]
(e(e) (M w. w (e))
x
5:
14:
Pt f BB
rad,
6:
(e(e) - ()(e) ( re),
(a) Ve e [n]
15: Play Pt, and observe the reward
7:
M, + MaxOracle w.
16: Update empirical means w (pa)
8:
B Bore-BeteeneccSarcMMM,,, Mr, w
17: Update the number of samples T (pt)
9: if (e) - (MinW(Mee w.) + w. (c)) for
18: end for
all e E Buhht then
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 Bub)). Also, (ii) under combinatorial setting, how to efficiently collect Buu from all sub-optimal super arms is another challenge.
To handle these challenges, we propose algorithm BLUCB-Parall Parallel based the peglore-verify- parallel framework [22. 10]. Paraalel (Algorithm 2) simultaneously simulates multiple BLUCE-Verify, (Algorithm 3) with confidence 6% = 5/2*+1 for k N. BLUCB-Verify, first calls BLUCB-Explore (Algorithm 4) to guess an optimal super arm M, and collect near bottleneck set Buub with constant confulence k, and then uses the required confidence 5% to verify the correctness of M, by only sampling base arms in M, and Buub- Through parallel simulations, BLUCB-Pare BLUCB-Parallel guarantees the 8 correctness.
The key component of this framework is BLUCB-Exee LLUCB-Explore (Algorithm 4), which provides a hypothe- sized answer M. and critical base arms Bash for verification to accelerate its identification process. Below we first describe the procedure of BLUCB- -xe and then explicate its two innovative techniques, i.c. offline subroutine and stopping condition, developed to handle the challenges (i). Excroee employs the subroutine BottleneckSSarchh(M Mex, v) to return the of bot- tleneck base arms from all super arms in MM' \ S(Mex) with respect to weight vector v. At each timestep, we first calculate the best super arm M, under lower reward confidence bound w,, and call BottleneckSearch to collect the bottlenecks Baub,e from all super arms in M \ ((M) with respect to an, (Line 8). Then, we use stopping condition (Line 9) to examine if M, is correct and B is close enough to Bun (with confidence k). If so, M, and Butb, eligible for verification and returned; otherwise, we play base arm from Mj and Bawb, which is most necessary for achieving the stopping condition. In the following, we explicate the two innovative techniques in BLUCB-ER Exppoo..
offline subroutine. BottleneckSearchi M, Mex, v) (Line 8) serves as an efficient offline procedure to collect bottlenecks from all super arms in given decision class M. \ ((Mxx) with respect to To achieve efficiency, the main idea behind Bottl NottleneckSearde ch is to avoid enumerating super arms in the combinatorial space. but only enumerate base arms e E [n] to check if is the bottleneck of some super arm in M \ ((Mc).. We achieve this by removing all base arms with rewards lower than e(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(Mx)) )). This efficient offiine subroutine solves challenge (ii) on computation complexity (see the supplementary material for its pseudo-codes and details).
Efficient "bottleneck-searchie
Delicate "check-nnerr-botlleeed stopping condition. The stopping condition (Line 9) aims to ensure the returned BLub, = Baub to satisfy the following Property (1): for each sub-optimal super arm Manh some base arm such that w(e) < 1/ (MinW(M.,, w) + Sinw(Mah, w)) is included in Bash which implies that e is near the actual bottleneck of Msub within 1 M. Ma and cannot be anyone in Ñ. Property (1) is crucial for BLUCB-Verify to achieve the optimal sample complexity, since it guarantees that in verification using Bab 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. Ve Bsub,t (e(()) - {Minn mc, + we (e)). using the definition of SottleneckSearde we have that for any M' M ((M), its bottleneck e' with respect w, included in Bsub, and satisfies that
w(ee) S we(ee) S (M,, w.) + MinW(M 20,) S (Min w) Min'(MM w)),
where inequality (a) comes from wx(c')) - (MinW( (M, w,)+ [,, (c')) and w, MinW w,). Hence, we can defer that MinW(M', w) I w(e') I 1/ (MinW(M.. w) + MinW(M , w)) for any M' E EMY MM) SMMe), and thus M, = M. (with confidence 1s). In addition, the returned Bauh. satisfies Property (1). This stopping condition offers knowledge of hypothesized optimal super arm M, and near bottleneck set Bub 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 specially designed for handling the unique challenges of CPE-B.
We formally state the sample complexity of SLLUCB-Paraller in Theorem 2.
Theorem 2 (Improved cxeedcooniieecc Upper Bound). For any < 0.01, with probability at least 1 - 6, algorithm BLUCB-Parallei (Algorithm 2) for CPE-B in the FC setting returns M, and takes the expected sample complexity
R²
1
Rtn (AC)²
R²
Rºn
Σ CEMLUN
In
In
Σ eEN
(AC)2
(A9))
cEMLUN
eEN
Results without dependence on Ñ in the dominant term. Let Hv = EcE
R² ( and
Hg Eee(n) (Agy= denote the verification and exploration hardness, respectively. Compared to BLUCB (Theorem 1), the sample complexity of BLUCB-Paralles removes the redundant dependence on Ñ in the In 1-1 term, which guarantees better performance when In 2 Hg H Hy ie., 8 < He exp(- H This sample complexity matches the lower bound (within a logarithmic factor) under small enough 5. For the example in Figure 1, BLUCB-Paralle Parallel only requires Ö A²
R²
"
A2...) In 1) samples, which just enough efforts (optimal) for identifying M..
The condition 8 < 0.01 in Theorem is due to that the used ppplorr-verify-prraaee framework [22, 10] needs a small 5 guarantee that BLUCB-Paralles alllllee can maintain the same order of sample complexity as its sub-algorithm BLUCB-Verify,, Prior pure exploration works [22, 10] also have such condition on 5.
Time Complexity. All our algorithms can run polynomial time, and the running time mainly depends the offline oracles. For example, on s-t path instances with E edges and V vertices, the used offline procedures MaxOracle and BottleneckSear only spend O(F) and O(E² ( V)) time, respectively. See the supplementary material for more time complexity analysis.
Lower Bound for the Fixed-Confidence Setting
In this section, we establish matching sample complexity lower bound for CPE-B in the FC setting. To formally state our results, we first define the notion of 8-correct algorithm as follows. For any confidence parameter 8 (0, 1), we call an algorithm fixedcconiieenc CPE-B problem, A returns the optimal super arm with probability at least 1 8.
8-correct algorithm if for the
Theorem 3 (Fixed-confidence Lower Bound), There exists family of instances for the fixed- confidence CPE-B problem, for which given any å E (0,0.1), any 8-correct algorithm has the expected sample complexity
Σ
R2 In
1 7
(AC
CEMLUN
This lower bound demonstrates that the sample complexity of BLUCB-Parallel (Theorem 2) optimal (within logarithmic factor) under small enough 6, since its In (dominant) term does
7

---

Algorithm 5 BSAR, algorithm for CPE-B in the FB setting
1: Input: budget T, M,, and AR Oracle.
15: end if
2: log(n)+ < Σ Tt
i= To 0. A1, R1 2.
16: If AR-Oracle returns 1 if the calculated
3: for = 1 72 do
feasible set is empty 17: end for
4: Te (n
T-n
18:
Prt argmax (M, MMMM MinW
5: Ug < [n] RA)
eEU,
6:
Play each e E U, for T; Ti-1 times Update empirical mean (e). VeEU,
19:
MMnnW -.:) -00
7:
20:
if Pr. E M, then
8: (e) + x for all e A,
21:
Att1 A, U [pt]: Ret1 + R
9: M, + OR-OOracleLL, wi:)
22:
else
for each e E U2 do
23:
A4+1 + A,, Re+1 t Rs L {pi)
11:
e M, then
24: end if
Mr. - AR-Oracle(_,
w0,)
25: end for
13: else
26: return An+1
14:
M t AR-Oracle(e, Re, uit)
not depend unnecessary base arms Ñ 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 logarithmic faccor (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 In 8-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- sise-arm-eved (instead of super- arm-level) gaps, and capture the bottleneck insight: different base arms in one super arm play distinct roles in determining its (stta-toyi and impose different influences the problem hardness.
5 Algorithm for the Fixed-Budge Setting
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 access an efficient accept-reject oracle AR-Oracle, which takes an accepted base arm or 1. a rejected base arm set I and a weight vector as inputs, and returns an optimal super arm from the decision class MMe, R) = {M E M E M. R n M = } with respect to v, i.e., AR-Oracle E argmax Me M(e, MinW w). If MMe,, R) is empty. AR-Oracle simply returns 1. 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 A rejected set R, and undetermined set U.. In each phase, only sample base arms in U/ and set the empirical rewards of base arms in A, to infinity (Line 8). Then, we call AR-Oracle to compute the empirical best super arm M, For each E U2 forbid R, and constrain inside/outside the calculated super arms and find the empirical best super arm Mr. from the restricted decision class (Lines 14). Then, we accept or reject the base arm Pt that maximizes the empirical reward gap between Mj and Mr.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 iiy (e) +- oo for all e E A, (Line 8) critical to the correctness and computation efficiency of BSAR. Since A, and R2 are not pulled in phase / 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 A, to infinity, the estimation of bottleneck values for sub-optimal super arms Msub avoids the disturbance of At, because each Ms has at least one base arm with reward lower than OPT and this base arm will never be included in A, (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 Mab 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 A, inside the calcu- lated super arms in the oracle, i.e., replacing Lines 12, 14 with AR-Oracle( A,, Re U [e), (e), and AR- AR-DracIe(A: U (e), R2, w.:), and deleting Line 8. Such acceptance strategy incurs exponential-ie
8

---

complexity on s-t path instances, 4 and only works for the linear reward function, where the common part A, between two compared super arms can be canceled out. If one naively applies their acceptance strategy to our bottleneck problem, the common part A, is possible to drag down (dominate) the empirical bottleneck values of all calculated super arms (Lines 9,12, 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 Exxed-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 OEE(E + V)) and BSAR only spends O + V)) time in decision making.
Now give the definitions of boddett reward gap and problem hardness, and then formally state the error probability result of BSAR. For E M., Ae = OPT - max MMMeM M MinW (M, w), and for e & M., A OPT ma Ms MinW(M, w). Let (1)- A be the permutation of A , A such that A (1) < ................................ < AB, (n) and the fixed-budget problem hardness is defined as H ma
(n)
Let log(n) = 7
Theorem 4 (Fixed-budget Upper Bound). For any T > n, algorithm BSAR (Algorithm 5) for CPE-B in the FB setting uses at most samples and returns the optimal super arm with the error probability bounded by
o On2200 exp
- n2
log(n)
Compared to the uniform sampling algorithm, which plays all base arms equalty and has Rend-t)) error probability with Amin = OPT max MinW M, w), Theorem 4
O(nexp(- T
achieves significantly better correctness guarantee (when A > Aii for most e E [n]) In addition, when our CPE-B problem reduces to conventional K K-armed pure exploration problem [7], Theorem 4 matches existing state-of-the-an 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 [1 [11] are highlighted as follows: (i) Prior analysis [1 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.
6 Experiments
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 E [nl). The minimum reward gap of any two edges (which is also the minimum gap of bottleneck values between two super arms) is denoted by Amin E 00.4. 0.7]. For the matching instances, we use a 5 x 3 complete bipartite graph, where n = 15, w(e) = [0.1, 1.08] and Amin [0.03, 0.07]. We change Amin to generate a series of instances with different hardness (plotted points in Figures 2(b). 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 connecting two airports as an edge (base arm), and also consider the number of available seats of a flight 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
vertex and a direct flight
Finding a s-t path which contains given edge set is hardard. See the supplementary material for its proof.

---

BUIC (ural
SLXB Touss
Sample Complettty
BLUCS-Partill (oun)
Complestty
Parcl- (our))
30 31
(a) FC, s-t path, large 8
(b) FC, s-t path, small 8 (c) FC, real-world, small 8
PSAR
BSR
Enor Protabiity
CSAR-R
Ereor Probwblky
ossRa cuccs
cuce-B
Unitormi
Unttmrfa
Sample Budget
Reward Cap Dats
(d) FB, matching
FB, matching
FB, real-world
Figure 2: Experiments for CPE-B in the FC/FB setting on synthetic and real-world datasets.
flights. In this instance, 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 small 5 = 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 E [6000, 15000]. and perform 3000 independent runs to show the error probability across runs. For all experiments, the random reward of each edge [mi] is i.i.d. drawn from Gaussian distribution (ww(e),
Experiments for the FC setting, We compare our BLUCE/BLUCBBPPrrll BLUCB is an ablation variant of BLUCE, 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 sate--ff-hhe-ad fixed- confidence CPE-I. algorithm run with bottleneck reward function. Uni orrFC is fixed-confidence uniform sampling algorithm. As shown in Figures 2(a)-2(c), BLUCB and SLUCC-Paraale, achieve better performance than the three baselines, which validates the statistical efficiency of our bottleneck- adaptive sample strategy. Under small 8, BLUCB due to its careful algorithmic design to avoid playing unnecessary base arms, which matches our theoretical results.
with three baselines.
enjoys lower sample complexity than
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 soute-of-the-eee fixed-budget CPE-L algorithm implemented with bottleneck reward function. CUCB-B [14] is regret minimization algorithm allowing nonlinear reward functions, and in pure exploration experiments we let return the empirical best super arm after T (sample budget) timesteps. Uni frrfo is a fixed- budget 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.
Conclusion and Future Work
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 broad family of instances (within a logarithmic factor), and establish matching lower bound to demonstrate their optimality. For the FB setting, we propose an algorithm whose eтror probability matches the oftee-of-the-art result, and it is the first to run efficiently on fixed-budger 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 to derive a lower bound for the FB setting, and another direction is to investigate the general nonlinear reward functions.
10

---

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 2020A AA10080000000 and 2020AAA01084003 Yuko Kuroki is supported by Microsoft Research Asia and JST ACT-X 1124477.
References
[1] Yasin Abbasi- Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems, 24:2312-2320, 2011.
[2] Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on Learning Theory, pages 2012.....
[3] Jven-Yves Audibert, Sébastien Bubeck, and Remi Munos. Best arm identification in multi-armed bandits. In Conference on Learning Theory, pages 41-53, 2010.
[4] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2-3):235 256, 2002.
[5] Ron Banner and Ariel Orda. Bottleneck routing games in communication networks. IEEE Journal on Selected Areas in Communications, 25(6:1173-1179, 2007.
[6] Alain Barrat, Mare Barthelemy, Romualdo Pastor-Satorras, and Alessandro Vespignani. The architecture of complex weighted networks. Proceedings of the National Academy of Sciences, 101(11):3747-3755 2004.
[7] Séebastian Bubeck, Tengyao Wang, and Nitin Viswanathan. Multiple identifications in multi- armed bandits. In International Conference on Machine Learning, pages 258-265, 2013.
[8] Paolo M. Camerini. The min-max spanning tree problem and some extensions. Information Processing Letters, 701):10-14, 1978.
[9] Lijie Chen, Anupam Gupta, and Jian Li. Pure exploration of multi-armed bandit under matroid constraints. In Conference on Learning Theory, pages 647-669, 2016.
[10] Lijie Chen, Anupam Gupta, Jian Li, Mingda Qiao, and Ruosong Wang. Nearly optimal sampling algorithms for combinatorial pure exploration. In Conference on Learning Theory, pages 482-534, 2017.
[11] Shouyuan Chen, Tian Lin, Irwin King, Michael Lyu, and Wei Chen. Combinatorial pure exploration of multi-armed bandits. In Advances in Neural Information Processing Systems, pages 379-387, 2014.
[12] Wei Chen, Yihan Du, Longbo Huang, and Haoyu Zhao. Combinatorial pure exploration for dueling bandit. In International Conference on Machine Learning, pages 1531-154) 2020.
[13] Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. In International Conference on Machine Learning, pages 151-159, 2013.
[14] Wei Chen, Yajun Wang. Yang Yuan, and Qinshi Wang. Combinatorial multi-armed bandit and its extension to probabilistically triggered arms. The Journal of Machine Learning Research, 17(1):1746-1778. 2016.
[15] Richard Combes, Mohammad Sadegh Talebi Mazraeh Shahi, Alexandre Proutiere, et al. Com- binatorial bandits revisited. In Advances in Neural Information Processing Systems, pages 2116-2124, 2015.
[16] Yihan Du, Yuko Kuroki, and Wei Chen. Combinatorial pure exploration with full-bandit or partial linear feedback. Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
[17] Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research, 7:1079-1 1005, 2006.

---

[18] Victor Gabillon, Mohammad Ghavamzadeh, Alessandro Lazaric, and Sébastien Bubeck. Multi- bandit best arm identification. In Advances in Neural Information Processing Systems, 2011.
[19] Victor Gabillon, Alessandro Lazaric, Mohammad Ghavamzadeh, Ronald Ortner, and Peter Bartlett. Improved learning complexity in combinatorial pure exploration bandits. In Artificial Intelligence and Statistics, pages 1004-1012, 2016.
[20] Weiran Huang, Jungseul Ok, Liang Li, and Wei Chen. Combinatorial pure exploration with con- tinuous and separable reward functions and its applications. In International Joint Conference on Artificial Intelligence, pages 2291-2299 2018.
[21] Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. PAC subset selection in stochastic multi-armed bandits. In International Conference on Machine Learning, pages 2012.
[22] Zohar S Karnin. Verification based solution for structured mab problems. In Advances in Neural Information Processing Systems, pages 145-153, 2016.
[23] Yuko Kuroki, Atsushi Miyauchi, Junya Honda, and Masashi Sugiyama. Online dense subgraph discovery via blurred-gres -rrred feedback. In International Conference on Machine Learning, pages 5522-5532, 2020.
[24] Yuko Kuroki, Liyuan Xu, Atsushi Miyauchi, Junya Honda, and Masashi Sugiyama. Polynomial- time algorithms for multiple-arm identification with full-bandit feedback. Neural Computation, 32(9):1733-177) 2020.
[25] Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Ad- vances in Applied Mathematics, (()):4222, 1985.
[26] Andrea Locatelli, Maurilio Gutzeit, and Alexandra Carpentier. An optimal algorithm for the thresholding bandit problem. In International Conference on Machine Learning, pages 1690-1698, 2016.
[27] M Peinhardt and V Kaibel. On the bottleneck shortest path problem. Technical Report, 2006.
[28] Abraham P Punnen and KPK Nair. Improved complexity bound for the maximum cardinality bottleneck bipartite matching problem. Discrete Applied Mathematics, 55(1):91-93, 1994.
[29] Chao Tao, Saúl Blanco, and Yuan Zhou. Best arm identification linear bandits with linear dimension dependency. In International Conference on Machine Learning, pages 4877-4886. 2018.
[30] William Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25(3/4):285-294 1933.
[31] Wenwei Yue, Changle Li, and Guoqiang Mao. Urban traffic bottleneck identification based on congestion propagation. 20/8 IEEE International Conference on Communications, pages 1-6, 2018.
[32] Yiyi Zhou, Rongrong Ji, Xiaoshuai Sun, Gen Luo, Xiaopeng Hong, Jinsong Su, Xinghao Ding, and Ling Shao. K-armed bandit based multi-modal network architecture search for visual question answering. Proceedings of the 28th ACM International Conference on Multimedia, pages 2245-1254 2020.
12


Reviews:
[{"review_id": "nDWTC65pW1x", "reviewer": "Reviewer_minG", "summary": "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "+ Originality: The model is relatively new and well-motivated: although combinatorial pure exploration problem has been studied before, none of the previous works focuses on the case with bottleneck reward functions. Concerning the involved techniques, the main algorithms proposed in this paper are (non-trivial) adaptations of previous known approaches/frameworks (i.e., explore-verify-parallel scheme in the FC setting and accept-reject scheme in the FB setting) into the context of CPE-B. Bottleneck reward function poses novel challenges and to overcome them, the authors provide several efficient oracles (such as Bottlenecksearch, ExistOracle, AR-Oracle) specifically designed for the bottleneck setting. In my opinion, these oracles are novel and they seem to be the contributions that stand out the most in this paper. Unfortunately, these oracles are not shown/discussed very clearly (due to the organization and writing flows of the paper). Most of related work is adequately cited (except for the literature on the guarantees’ lower-bounds in the FC setting).\n\n+ Quality: The main results on the performance guarantees of BLUCB, BLUCB-Parallel and BSAR algorithms seem technically sound: I do not spot any obvious error (note that I did not check through all details in the proofs). Several numerical experiments are conducted but it lacks adequate discussions. The paper also claims that the proposed algorithms are efficiently implementable. However, this claim is not shown clearly, especially on the efficiency of the oracles (see below). The results in the FC setting feel quite complete; on the other hand, the ones in the FB setting is less so: BSAR does not provide significant improvements in comparison to the benchmark CSAR and no lower-bound is available. \n\n+ Clarity: The texts itself is quite well-written. Overall, the technical discussions are relatively adequate for readers to follow. Nevertheless, the organization of the paper should be revised. Particularly, in my opinion, the oracles designed for Bottleneck reward are the novelties that really differ this work to the literature and should be analyzed with details in the main text (currently in the appendix). To do this, probably the authors should find a way to trim down the main algorithms given that the explore-verify-parallel and accept-reject schemes are previously known. \n\nAs mentioned above, my main concern is the claim on efficiency. Particularly, the proof on the running time of ExistOracle (Appendix C.2.1) is vague and rushed toward conclusions (this is the core result for the proofs on Bottlenecksearch, AR-Oracle and eventually, the running time of the algorithms). How is $s$-$t$ path reduced to 2-vertex connectivity problem? When no super arm in $M_{\\geq w(e)}$ contains the base arm $e$, how can one check this efficiently, given that $M_{\\geq w(e)}$ might contain exponentially many elements? Maybe I misunderstood something here. \n\n+ Significance: The paper provides the (first-ever) results for the CPE-B framework. They can be used as the foundation for other analyses on CPE-B and probably can be generalized to cases different from bottleneck rewards.  \n\n+ Other comments and questions:\n\n1/ Page 7: BLUCB-parallel is better than BLUCB when $\\delta \\le \\exp(-H_{E}/(H_{E}-H_{V}))$. Therefore, is it true that before running the algorithm, we cannot compute (efficiently) $\\Delta^C_e$ and thus, no way to know if this condition on $\\delta$ will hold? Neither can we tune a priori this $\\delta$ in BLUCB-parallel?\n2/ Page 5: line 4 of Algorithm 2, does this mean that ONLY when $t$ is an even number, we execute Verify_k? Why should we do this and is this a “wasteful” way of using odd iterations $t$?\n3/ Line 293: Which CPE-L algorithm of [10] is discussed here? CSAR?\n4/ Line 311: This sentence is very confusing. Result of BSAR in Theorem 4 matches with the bound of CSAR presented in Theorem 3 of [10] on the linear case; do the authors imply that even in the bottleneck case, CSAR will have the same guarantee? What is precisely the novelty of BSAR?\n5/ Line 313: if $\\Delta^B_i$ is the same order with $\\Delta_{\\textrm{min}}$, $H^B$ is also $\\mathcal{O}(n/\\Delta_{\\textrm{min}})$; given this, how do the authors claim that BSAR’s guarantee is “significantly” better than that of the uniform sampling algorithm?\n6/ Page 9: In Figure 2(a), it looks like the sample complexity of BLUCB and BLUCB-Parallel have a better order (in terms of $n$) than that of CLUCB. In Figure 2(b), this difference (in order) is much smaller. Why does this happen (the theoretical guarantees of CLUCB (in [10]) and BLUCB, BLUCB-Parallel have the same order in terms of $n$)? In Figure 2c and 2d, when the gap is large, CSAR can outperform BSAR; do we have a condition for when this will happen (based on the precise bound provide by [10])?\nCan the authors also report the elapsed time of these algorithms in the experiments?\n\n+ Some (possible) typos: line 137: denote  -> denotes; line 180” bottlenck -> bottleneck;  line 193: propose algorithm BLUCB-parallel -> propose the BLUCB-parallel algorithm;  Line 285: avoid them disturbing -> avoid disturbing\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical issues with this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "ebz-BJR9Ni0", "reviewer": "Reviewer_haVZ", "summary": "The paper considers a combinatorial bandit problem, where the reward of super arm (a subset of base arms) is determined by the minimum of rewards from the individual base arms, while only base arm is played in exploration, i.e., semi-bandit feedback. The authors propose two algorithms for pure exploration in fixed-confidence and fixed-budget settings, with asymptotical optimality.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "The proposed method is proven to be efficient as it matches the asymptotical order of lower bound of sample complexity (Theorems 2 & 3). The simulation results support the superiority of the proposed methods. In what follows, I leave some concerns and comments on this work.\n\n- The analysis in the fixed budget setting (Theorem 4) seems a straightforward extension of existing work [10], c.f., line 311. Please elaborate differences and challenges. In addition, it is unfortunate that there is no lower bound analysis for the fixed budget setting. It would be great if the paper includes some conjectures.\n\n - The paper studies semi-bandit feedback setting, where each base arm is individually explored. This needs to be justified. In addition, if the lower bound of sample complexity in Theorem 3 works for only semi-bandit feedback setting, it needs to be clearly stated.\n\n- I'm not sure if the experiment on the fixed budget setting shows a clear dominance of the proposed method over the others.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": ".", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "IgD7KrkVJpG", "reviewer": "Reviewer_69qt", "summary": "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. \n\nWe 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. \n\nThe paper provides algorithms, and upper and lower bounds on sample complexity for a given confidence bound, and error probability bound for a given budget.  \n\nThe paper (including the supplemental material) is densely written with sparse discussion of the results. A table of notations would considerably help the reader. \n\nReported simulation results are limited. \n\nSome of the motivating examples need better articulation (e.g. bottleneck path problem). ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "The paper provides an extension of [10], extending the results from linear rewards considered in [10] to bottleneck or minimum rewards. It  provides algorithms to find the bottleneck arm and corresponding super-arm(s), upper and lower bounds on sample size, under fixed confidence level, and error probability under fixed budget. \n\nThe suggested use-case of bottleneck shortest path needs further clarification. The shortest path, for example in a communications network, is chosen so as to transfer information from a source node to a destination node; what does sampling a base arm mean in this context? Given a collection of S-D paths, it makes sense to sample the paths (or super-arms); during the exploration phase, this will achieve the goal of information transfer (even if it is inefficient). Sampling base arms is wasteful in this context. Further this implies that the routing must be global rather than distributed which is the practical case in a large network.  In theory, the number of paths may be exponential in the network size; but in practice, many constraints are impose which limit the number of paths, and hence the number of super-arms to be considered. \n\nThe experimental section is weak. The main paper says “we defer detailed setup description and more results to the supplementary material” (line 320). But the supplementary material does not provide details, and hence the experiments cannot be replicated.  Given the lack of details, it is not possible, for example, to assess if a gap of 0.04 (Fig 2) is significant. The simulation results are limited and comparisons are only to algorithms defined in this paper, not to competing algorithms. Simulation results are thus limited and provide limited insights.  This is a significant weakness. \n\nThe paper is densely written with sparse discussion of the results. A table of notations would considerably help the reader. The paper contains very little in the way of discussion of the 4 theorems stated in the paper, and the main body of the paper does not even contain an outline of the proofs.  (As noted elsewhere, the paper does not even describe the brand-new techniques that are claimed to be needed.) The supplemental material contains proofs of theorems and attendant lemmas, but is also lacking in any discussion. As a specific example, after the formal statements of the Theorems, slightly looser versions could have been provided in terms of min / max of the weights directly. \n\nTime-complexity of the offline procedures (Table 1, Supplementary material) is O(E^3 \\sqrt{V}) which can be prohibitive for large graphs, even for a single call. It is hard to call this “fast”.  It is not clear how often these algorithms are invoked. \n\nWhat is the ‘family of instances’ for which BLUCB and BLUCB-Parallel achieve optimal sample complexity (L 134, L 179); BTW isn’t this ‘order optimal’ vs. ‘optimal’? \n\nIn a typical on-line setting, such as the bottleneck path problem, what does running BLUCB in parallel mean? How many instances are run in parallel? \n\nTheorem 2 strengthens the results of Theorem 1 by separating base arms into arms that are better / worse than the optimal arm. However, the specific numbers provided for the example of Figure 1 are not convincing \\tilde{O} (245 \\log(1/\\delta)) and \\tilde{O} (211 \\log(1/\\delta)). \n\nThe paper repeatedly assumes the existence of “efficient oracles”, which is troubling (it is stated that such oracles exist for paths, bipartite matchings, and spanning trees; but it does not state how efficient they are). \n\nWhat are the brand-new techniques introduced in this paper (line 75)? This should have been included in the summary of contributions. \n\nFootnote 2: is this element-wise minimization? \n\nThe sub-Gaussian parameter R must be defined. \n\nGrammar, syntax, and spelling demand careful attention. \n\n -- - --- \n====== Comments added after author rebuttal and discussion =====  \nMO, the paper is densely written, and would definitely have improved considerably with added discussion. The authors could have used the extra pages for this.\n\nThe authors have provided detailed responses to many, but not all, of my comments. For example, the response to my 'gap' comment is weak. I still do not know if a difference of 0.04 is significant enough to claim that the new method works better.\n\nThe authors' response partially but not fully eliminates my concerns regarding the experimental section: lack of detail (addressed), and limited experimentation.\n\nBased on the author responses (to my comments as well as those of other reviewers), I have raised my rating from '4' to '6' ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "\n The paper does not discuss limitations / potential negative societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "About 12 hours - rather dense paper  "}, "extra_text": {}}, {"review_id": "BBwtqBCJXb2", "reviewer": "Reviewer_vLPw", "summary": "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. \nThe 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "—  Strengths\nThe paper is overall very well written and easy to follow, as is the supplement with very clear and well guided proofs.\n\nThe problem is well explained and related works -- to my knowledge -- adequately cited. \nThe studied problem — combinatorial pure exploration with bottleneck function (CPE-B) is part of the more general combinatorial pure exploration problem (CPE), for which there exists several published works in the case of several classes of reward functions (linear, continuous and separable).\nThis work however focuses on the combinatorial pure exploration problem in the specific case where the reward function is the bottleneck function — i.e. the reward of a super arm is the minimum of the rewards of the base arms it contains — for which classical algorithms do not give significant guarantees. The author clearly explicit the specific challenges associated with CPE-B, namely, (1) the fact that the optimal sample complexity relies on base arm gaps which are tighter than super arm gaps, (2) the existence of unnecessary base arms which do not contribute to the reward of super arms.\n\nThe authors then propose several contributions to solve these problems. In the fixed-confidence setting, the authors propose the BLUCB algorithm which uses the specificities of the bottleneck function (e.g. its monotonicity) to focus on promising “critical” arms (i.e. the arms on which the reward on super arms relies) and solve the first challenge [Theorem 1], while BLUCB-parallel offers a solution to the second problem [Theorem 2]. The authors propose a lower bound [Theorem 3] which shows the optimality of their previous results.\nIn the fixed-budget setting, the authors propose the BSAR algorithm which provides optimal error probability [Theorem 4].\n\nAs far as I understand, the claims and associated proofs are correct, and all these contributions are novel. The authors therefore provide a very complete and realistically implementable solution to the CPE-B problem.\n\nThe proposed algorithms rely on several offline procedures/oracles, which complexity the authors adequately discuss in the supplement, removing any possible interrogation regarding the realistic implementability of the proposed methods.\n\n\n— Minor remarks\nThere are a few typos here and there (e.g. L72 \"in *an* online environment\", L84 \"for *the* bottleneck identification task\", L137 \"denote*s* the set\", L159 \"has *a* higher bottleneck value than \\tilde{M}_t\")\n\nThe authors solve a very specific instance of a problem that they themselves introduce. While I absolutely do not think that this is a rejection argument since pioneer work is crucial, I think that the motivation for the problem -- given its specificities -- could be better brought forward. The authors motivate the study of CPE with the bottleneck reward function by its natural occurence in communication networks, traffic scheduling and neural architectural search, I am however not aware in any prior interest in this reward function in the “theoretical” MBA/PE community, and would have liked a more detailed theoretical motivation, or experiments that reflect the applied motivation (by using data simulating one of the mentioned application fields for example). \nAnother possibility would be to give more insights in the main text concerning how solving the CPE-B problem could be a stepping stone to solving the CPE problem with a larger class of non-linear reward functions (as mentioned in the future work section and in the supplement) -- which I believe would be a significantly more impactful contribution.\n\nThe complexity of all proposed algorithms is polynomial in E and V. My understanding is however that in some combinatorial problems, E and V might me exponential in n (i.e. subset selection problem), in which case the algorithms would not run in polynomial time with respect to n. This is not an important issue but I find the text of the first sections a little ambiguous concerning which quantities the \"polynomial time\" refers to.\n\nThe reliance on small delta (<0.1, <0.01), both for Theorem 2 and 3 could be explained in a clearer way in the main text.\n\n---- POST-REBUTTAL UPDATE\nAfter reading the other reviews, the author responses to these reviews and the additional comments from reviewer 69qt, I wish to keep my original score of 7. I agree that the paper is densely written and packs a lot of information, but I believe that the authors managed to present the material in a structured and clear way nevertheless, which in my opinion makes it a strength of the paper in the end. The \"experiments\" section could benefit from additional results in a \"real-world\" setup that would help with the motivation of the problem introduced in the paper, which the author propose to do in their revised version.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors provided some research directions arising from their work, one of which being the investigation of general non-linear reward functions (going beyond the bottleneck reward function and its specificities). They did not discuss the potential negative societal impact of their work, which I do believe is absolutely minimal due to its very theoretical nature.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not believe this paper raises any ethical issue.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper examines a combinatorial exploration problem in which the learner aims to identify the best "slate" of arms, with a "bottleneck" criterion that defines the reward of each slate as the minimum possible reward of its constituent elements. The authors propose a series of tailor-made algorithms that exploit the problem's bottleneck structure to achieve optimal guarantees, both in a fixed-confidence and fixed-budget setting.

One of the reviewers expressed concerns about the writing style of the paper and the strength of the authors' experiments. During the discussion committee phase, these concerns were, to a large extent, alleviated by the authors' replies, so a decision was reached to accept the paper. At the same time, I would urge the authors to implement a version of their exchanges the reviewers and adjust the denser parts of the paper accordingly, as this would significantly strengthen their contribution.
Decision: Accept (Poster)