# Combinatorial Pure Exploration with Bottleneck Reward Function

Yihan Du
IIIS, Tsinghua University
Beijing, China
<EMAIL_ADDRESS>
&Yuko Kuroki
The University of Tokyo / RIKEN
Tokyo, Japan
<EMAIL_ADDRESS>
Wei Chen
Microsoft Research
Beijing, China
<EMAIL_ADDRESS>

###### 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.

##  1 Introduction

The Multi-Armed Bandit (MAB) problem [31, 36, 4, 2] is a classic model to
solve the exploration-exploitation trade-off in online decision making. Pure
exploration [3, 25, 7, 32] 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, 25, 7, 30], 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, 25, 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 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.111The 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.

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 [38], 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 [39], 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
$\delta$, the learner aims to identify the optimal super arm with probability
$1-\delta$ 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.

Figure 1: Illustrating example.

Challenges of CPE-B. Compared to prior CPE works [11, 10, 24], 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(e_{i})$, base arm gap
$\Delta_{e_{i},e_{j}}$ and super arm gap $\Delta_{M_{*},M_{\textup{sub}}}$ are
as shown in the figure. In order to identify the optimal path, all we need is
to pull $e_{1},e_{2},e_{4}$ to determine that $e_{1}$ is worse than $e_{2}$
and $e_{4}$, and $e_{3},e_{5},e_{6}$ are useless for revealing the sub-
optimality of $M_{1}$ and $M_{2}$. In this case, the optimal sample complexity
should be
$O((\frac{2}{\Delta_{e_{2},e_{1}}^{2}}+\frac{1}{\Delta_{e_{4},e_{1}}^{2}})\ln\delta^{-1})$,
which depends on the tight base arm gaps and only includes the critical base
arms ($e_{1},e_{2},e_{4}$). However, if one naively adapts existing CPE
algorithms [11, 12, 16] to work with bottleneck reward function, an inferior
sample complexity of
$O(\sum_{e_{i},i\in[6]}\frac{1}{\Delta_{M_{*},M_{\textup{sub}}}^{2}}\ln\delta^{-1})$
is incurred, which depends on the loose super arm gaps and contains a
summation over all base arms (including the unnecessary $e_{3},e_{5},e_{6}$).
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
$e_{1},e_{2},e_{4}$ 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 $\mathtt{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 $\mathtt{BLUCB\mbox{-}Parallel}$ in
high confidence regime, which adopts an efficient “bottleneck-searching”
offline procedure and a novel “check-near-bottleneck” stopping condition. The
sample complexity of $\mathtt{BLUCB\mbox{-}Parallel}$ drops the dependence on
unnecessary base arms and achieves the optimality (within a logarithmic
factor) under small enough $\delta$. (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
$\mathtt{BSAR}$ with a special acceptance scheme for the bottleneck
identification task. $\mathtt{BSAR}$ achieves the state-of-the-art error
probability and is the first to run efficiently on fixed-budget path
instances, compared to existing CPE algorithms. All our proposed algorithms
run in _polynomial time_.222Here “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).
The experimental results demonstrate that our algorithms significantly
outperform the baselines. Due to space limit, we defer all the proofs to
Appendix.

###  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. [24] 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. [29] 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.

##  2 Problem Formulation

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,\dots,n$. Each base arm
$e\in[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, 32, 35]. Let $\bm{w}=(w(1),\dots,w(n))^{\top}$ be the expected reward
vector of base arms. The learner is also given a decision class
$\mathcal{M}\subseteq 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\in\mathcal{M}$, we define its expected reward (also called
_bottleneck value_) as $\mathtt{MinW}(M,\bm{w})=\min_{e\in M}w(e)$,333In
general, the second input of function $\mathtt{MinW}$ can be any vector: for
any $M\in\mathcal{M}$ and $\bm{v}\in\mathbb{R}^{n}$,
$\mathtt{MinW}(M,\bm{v})=\min_{e\in M}v(e)$. i.e., the minimum expected reward
of its constituent base arms, which is so called _bottleneck reward function_.
Let
$M_{*}=\operatornamewithlimits{argmax}_{M\in\mathcal{M}}\mathtt{MinW}(M,\bm{w})$
be the optimal super arm with the maximum bottleneck value, and
$\mathtt{OPT}=\mathtt{MinW}(M_{*},\bm{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 Section B.3).

At each timestep, the learner plays (or samples) a base arm $p_{t}\in[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 $\mathcal{M}$.

For this identification task, we study two common metrics in pure exploration
[25, 7, 32, 10], i.e., fixed-confidence (FC) and fixed-budget (FB) settings.
In the FC setting, given a confidence parameter $\delta\in(0,1)$, the learner
needs to identify $M_{*}$ with probability at least $1-\delta$ 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.

##  3 Algorithms for the Fixed-Confidence Setting

In this section, we first propose a simple algorithm $\mathtt{BLUCB}$ for the
FC setting, which adopts a novel bottleneck-adaptive sample strategy to obtain
the tight base-arm-gap dependent sample complexity. We further develop an
improvement $\mathtt{BLUCB\mbox{-}Parallel}$ in high confidence regime, whose
sample complexity drops the dependence on unnecessary base arms for small
enough $\delta$. Both algorithms achieve the optimal sample complexity for a
family of instances (within a logarithmic factor).

###  3.1 Algorithm $\mathtt{BLUCB}$ with Base-arm-gap Dependent Results

Algorithm 1 $\mathtt{BLUCB}$, algorithm for CPE-B in the FC setting

1: Input: $\mathcal{M}$, $\delta\in(0,1)$ and $\mathtt{MaxOracle}$.

2: Initialize: play each $e\in[n]$ once, and update empirical means
$\hat{\bm{w}}_{n+1}$ and $T_{n+1}$

3: for $t=n+1,n+2,\dots$ do

4:
$\textup{rad}_{t}(e)\leftarrow\sqrt{2\ln(\frac{4nt^{3}}{\delta})/T_{t}(e)},\
\forall e\in[n]$

5: $\underline{w}_{t}(e)\leftarrow\hat{w}_{t}(e)-\textup{rad}_{t}(e),\ \forall
e\in[n]$

6: $\bar{w}_{t}(e)\leftarrow\hat{w}_{t}(e)+\textup{rad}_{t}(e),\ \forall
e\in[n]$

7: $M_{t}\leftarrow\mathtt{MaxOracle}(\mathcal{M},\underline{\bm{w}}_{t})$

8:
$\tilde{M}_{t}\leftarrow\mathtt{MaxOracle}(\mathcal{M}\setminus\mathcal{S}(M_{t}),\bar{\bm{w}}_{t})$

9: if
$\mathtt{MinW}(M_{t},\underline{\bm{w}}_{t})\geq\mathtt{MinW}(\tilde{M}_{t},\bar{\bm{w}}_{t})$
then

10: return $M_{t}$

11: end if

12: $c_{t}\leftarrow\operatornamewithlimits{argmin}_{e\in
M_{t}}\underline{w}_{t}(e)$

13:
$d_{t}\leftarrow\operatornamewithlimits{argmin}_{e\in\tilde{M}_{t}}\underline{w}_{t}(e)$

14:
$p_{t}\leftarrow\operatornamewithlimits{argmax}_{e\in\\{c_{t},d_{t}\\}}\textup{rad}_{t}(e)$

15: Play $p_{t}$, and observe the reward

16: Update empirical means $\hat{w}_{t+1}(p_{t})$

17: Update the number of samples $T_{t+1}(p_{t})$

18: end for

Algorithm 1 illustrates the proposed algorithm $\mathtt{BLUCB}$ for CPE-B in
the FC setting. Here $\mathcal{S}(M_{t})$ denotes the set of all supersets of
super arm $M_{t}$ (Line 8). Since the bottleneck reward function is
monotonically decreasing, for any $M^{\prime}\in\mathcal{S}(M_{t})$, we have
$\mathtt{MinW}(M^{\prime},\bm{w})\leq\mathtt{MinW}(M_{t},\bm{w})$. Hence, to
verify the optimality of $M_{t}$, we only need to compare $M_{t}$ against
super arms in $\mathcal{M}\setminus\mathcal{S}(M_{t})$, and this property will
also be used in the later algorithm $\mathtt{BLUCB\mbox{-}Parallel}$.

$\mathtt{BLUCB}$ is allowed to access an efficient _bottleneck maximization
oracle_ $\mathtt{MaxOracle}(\mathcal{F},\bm{v})$, which returns an optimal
super arm from $\mathcal{F}$ with respect to $\bm{v}$, i.e.,
$\mathtt{MaxOracle}(\mathcal{F},\bm{v})\in\operatornamewithlimits{argmax}_{M\in\mathcal{F}}\mathtt{MinW}(M,\bm{v})$.
For $\mathcal{F}=\mathcal{M}$ (Line 7), such an efficient oracle exists for
many decision classes, such as the bottleneck shortest path [33], bottleneck
bipartite matching [34] and minimum bottleneck spanning tree [8] algorithms.
For $\mathcal{F}=\mathcal{M}\setminus\mathcal{S}(M_{t})$ (Line 8), we can also
efficiently find the best super arm (excluding the supersets of $M_{t}$) by
repeatedly removing each base arm in $M_{t}$ and calling the basic
maximization oracle, and then selecting the one with the maximum bottleneck
value.

We describe the procedure of $\mathtt{BLUCB}$ as follows: at each timestep
$t$, we calculate the lower and upper confidence bounds of base arm rewards,
denoted by $\underline{\bm{w}}_{t}$ and $\bar{\bm{w}}_{t}$, respectively.
Then, we call $\mathtt{MaxOracle}$ to find the super arm $M_{t}$ with the
maximum pessimistic bottleneck value from $\mathcal{M}$ using
$\underline{\bm{w}}_{t}$ (Line 7), and the super arm $\tilde{M}_{t}$ with the
maximum optimistic bottleneck value from
$\mathcal{M}\setminus\mathcal{S}(M_{t})$ using $\bar{\bm{w}}_{t}$ (Line 8).
$M_{t}$ and $\tilde{M}_{t}$ are two critical super arms that determine when
the algorithm should stop or not. If the pessimistic bottleneck value of
$M_{t}$ is higher than the optimistic bottleneck value of $\tilde{M}_{t}$
(Line 9), we can determine that $M_{t}$ has the higher bottleneck value than
any other super arm with high confidence, and then the algorithm can stop and
output $M_{t}$. Otherwise, we select two base arms $c_{t}$ and $d_{t}$ with
the minimum lower reward confidence bounds in $M_{t}$ and $\tilde{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 $M_{t}$ has a higher bottleneck value than $\tilde{M}_{t}$, it suffices
to find a base arm from $\tilde{M}_{t}$ which is worse than any base arm (the
bottleneck base arm) in $M_{t}$. To achieve this, base arms $c_{t}$ and
$d_{t}$, which have the most potential to be the bottlenecks of $M_{t}$ and
$\tilde{M}_{t}$, are the most necessary ones to be sampled. This bottleneck-
adaptive sample strategy is crucial for $\mathtt{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
($M_{t}$ and $\tilde{M}_{t}$) equally and does a uniform choice. If one
naively adapts those algorithms with the current reward function
$\mathtt{MinW}(M,\bm{w})$, a loose super-arm-gap dependent sample complexity
is incurred.

To formally state the sample complexity of $\mathtt{BLUCB}$, we introduce some
notation and gap definition. Let $N=\\{e\mid e\notin
M_{*},w(e)<\mathtt{OPT}\\}$ and $\tilde{N}=\\{e\mid e\notin
M_{*},w(e)\geq\mathtt{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

######  Definition 1 (Fixed-confidence Gap).

$\Delta^{\textup{C}}_{e}\\!=\\!\left\\{\begin{array}[]{lr}w(e)-\max_{M\neq
M_{*}}\mathtt{MinW}(M,\bm{w}),\ \textup{if }e\in M_{*},&\textup{\qquad(a)}\\\
w(e)-\max_{M\in\mathcal{M}:e\in M}\mathtt{MinW}(M,\bm{w}),\ \textup{if
}e\in\tilde{N},&\textup{\qquad(b)}\\\ \mathtt{OPT}-\max_{M\in\mathcal{M}:e\in
M}\mathtt{MinW}(M,\bm{w}),\ \textup{if }e\in N.\end{array}\right.$

Now we present the sample complexity upper bound of $\mathtt{BLUCB}$.

######  Theorem 1 (Fixed-confidence Upper Bound).

With probability at least $1-\delta$, algorithm $\mathtt{BLUCB}$ (Algorithm 1)
for CPE-B in the FC setting returns the optimal super arm with sample
complexity

$O\left(\sum_{e\in[n]}\frac{R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\sum_{e\in[n]}\frac{R^{2}n}{(\Delta^{\textup{C}}_{e})^{2}\delta}\right)\right).$

Base-arm-gap dependent sample complexity. Owing to the bottleneck-adaptive
sample strategy, the reward gap $\Delta^{\textup{C}}_{e}$ (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, $\mathtt{BLUCB}$ only spends
$\tilde{O}((\frac{2}{\Delta_{e_{2},e_{1}}^{2}}+\sum_{i=3,4,5,6}\frac{1}{\Delta_{e_{i},e_{1}}^{2}})\ln\delta^{-1})$
samples, while a naive adaptation of prior CPE algorithms [11, 12, 16] with
the bottleneck reward function will cause a loose super-arm-gap dependent
result
$\tilde{O}(\sum_{e_{i},i\in[6]}\frac{1}{\Delta_{M_{*},M_{\textup{sub}}}^{2}}\ln\delta^{-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
$\tilde{N}$ ($e_{3},e_{5},e_{6}$ 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 $\delta$

Algorithm 2 $\mathtt{BLUCB\mbox{-}Parallel}$, an improved algorithm for the FC
setting under small $\delta$

1: Input: $\delta\in(0,0.01)$ and sub-algorithm
$\mathtt{BLUCB\mbox{-}Verify}$.

2: For $k=0,1,\dots$, let $\mathtt{BLUCB\mbox{-}Verify}_{k}$ be the sub-
algorithm $\mathtt{BLUCB\mbox{-}Verify}$ with
$\delta_{k}=\frac{\delta}{2^{k+1}}$

3: for $t=1,2,\dots$ do

4: for each $k=0,1,\dots\ \textup{ such that }\ t\textup{ mod }2^{k}=0$ do

5: Start or resume $\mathtt{BLUCB\mbox{-}Verify}_{k}$ with one sample, and
then suspend $\mathtt{BLUCB\mbox{-}Verify}_{k}$

6: if $\mathtt{BLUCB\mbox{-}Verify}_{k}$ returns an answer $M_{\textup{out}}$,
then return $M_{\textup{out}}$

7: end for

8: end for

Algorithm 3 $\mathtt{BLUCB\mbox{-}Verify}$, sub-algorithm of
$\mathtt{BLUCB\mbox{-}Parallel}$

1: Input: $\mathcal{M}$, $\delta^{V}\\!\in\\!(0,0.01)$ and
$\mathtt{MaxOracle}$.

2: $\kappa\leftarrow 0.01$

3:
$\\!\\!\\!\hat{M}_{*},\\!\hat{B}_{\textup{sub}}\\!\\!\leftarrow\\!\\!\mathtt{BLUCB\mbox{-}Explore}(\mathcal{M},\kappa,\mathtt{MaxOracle})$

4: Initialize: play each $e\in[n]$ once, and update empirical means
$\hat{\bm{w}}_{n+1}$ and $T_{n+1}$

5: for $t=n+1,n+2,\dots$ do

6:
$\textup{rad}_{t}(e)\\!\leftarrow\\!R\sqrt{2\ln(\frac{4nt^{3}}{\delta^{V}})/T_{t}(e)},\forall
e\\!\in\\![n]$

7: $\underline{w}_{t}(e)\leftarrow\hat{w}_{t}(e)-\textup{rad}_{t}(e),\ \forall
e\in[n]$

8: $\bar{w}_{t}(e)\leftarrow\hat{w}_{t}(e)+\textup{rad}_{t}(e),\ \forall
e\in[n]$

9:
$\tilde{M}_{t}=\mathtt{MaxOracle}(\mathcal{M}\setminus\mathcal{S}(\hat{M}_{*}),\bar{\bm{w}}_{t})$

10: if
$\mathtt{MinW}(\hat{M}_{*},\underline{\bm{w}}_{t})\geq\mathtt{MinW}(\tilde{M}_{t},\bar{\bm{w}}_{t})$
then

11: return $\hat{M}_{*}$

12: end if

13:
$c_{t}\leftarrow\operatornamewithlimits{argmin}_{e\in\hat{M}_{*}}\underline{w}_{t}(e)$

14:
$F_{t}\leftarrow\\{e\in\hat{B}_{\textup{sub}}:\bar{w}_{t}(e)>\underline{w}_{t}(c_{t})\\}$

15: $p_{t}\leftarrow\operatornamewithlimits{argmax}_{e\in
F_{t}\cup\\{c_{t}\\}}\textup{rad}_{t}(e)$

16: Play $p_{t}$, and observe the reward

17: Update empirical means $\hat{w}_{t+1}(p_{t})$

18: Update the number of samples $T_{t+1}(p_{t})$

19: end for

Algorithm 4 $\mathtt{BLUCB\mbox{-}Explore}$, sub-algorithm of
$\mathtt{BLUCB\mbox{-}Verify}$, the _key algorithm_

1: Input: $\mathcal{M}$, $\kappa=0.01$ and $\mathtt{MaxOracle}$.

2: Initialize: play each $e\in[n]$ once, and update empirical means
$\hat{\bm{w}}_{n+1}$ and $T_{n+1}$

3: for $t=n+1,n+2,\dots$ do

4:
$\\!\\!\textup{rad}_{t}(e)\\!\leftarrow\\!R\sqrt{2\ln(\frac{4nt^{3}}{\kappa})/T_{t}(e)},\
\forall e\\!\in\\![n]$

5: $\underline{w}_{t}(e)\leftarrow\hat{w}_{t}(e)-\textup{rad}_{t}(e),\ \forall
e\in[n]$

6: $\bar{w}_{t}(e)\leftarrow\hat{w}_{t}(e)+\textup{rad}_{t}(e),\ \forall
e\in[n]$

7: $M_{t}\leftarrow\mathtt{MaxOracle}(\mathcal{M},\underline{\bm{w}}_{t})$

8:
$\hat{B}_{\textup{sub},t}\\!\\!\leftarrow\\!\\!\mathtt{BottleneckSearch}(\mathcal{M},M_{t},\underline{\bm{w}}_{t})$

9: if
$\bar{w}_{t}(e)\\!\leq\\!\frac{1}{2}(\mathtt{MinW}(M_{t},\underline{\bm{w}}_{t})+\underline{w}_{t}(e))$
for all $e\in\hat{B}_{\textup{sub},t}$ then

10: return $M_{t},\hat{B}_{\textup{sub},t}$

11: end if

12: $c_{t}\leftarrow\operatornamewithlimits{argmin}_{e\in
M_{t}}\underline{w}_{t}(e)$

13:
$\hat{B}^{\prime}_{\textup{sub},t}\leftarrow\\{e\in\hat{B}_{\textup{sub},t}:$$\quad\bar{w}_{t}(e)>\frac{1}{2}(\mathtt{MinW}(M_{t},\underline{\bm{w}}_{t})+\underline{w}_{t}(e))\\}$

14:
$p_{t}\leftarrow\operatornamewithlimits{argmax}_{e\in\hat{B}^{\prime}_{\textup{sub},t}\cup\\{c_{t}\\}}\textup{rad}_{t}(e)$

15: Play $p_{t}$, and observe the reward

16: Update empirical means $\hat{w}_{t+1}(p_{t})$

17: Update the number of samples $T_{t+1}(p_{t})$

18: end for

Challenges of avoiding unnecessary base arms. Under the bottleneck reward
function, in each sub-optimal super arm $M_{\textup{sub}}$, only the base arms
with rewards lower than $\mathtt{OPT}$ (base arms in $N$) can determine the
relationship of bottleneck values between $M_{*}$ and $M_{\textup{sub}}$ (the
bottleneck of $M_{\textup{sub}}$ is the most efficient choice to do this), and
the others (base arms in $\tilde{N}$) are useless for revealing the sub-
optimality of $M_{\textup{sub}}$. 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 $B_{\textup{sub}}$, to see that each sub-optimal
super 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 $M_{\textup{sub}}$, which base
arm is its bottleneck (included in $B_{\textup{sub}}$). Also, (ii) under
combinatorial setting, how to efficiently collect $B_{\textup{sub}}$ from all
sub-optimal super arms is another challenge.

To handle these challenges, we propose algorithm
$\mathtt{BLUCB\mbox{-}Parallel}$ based on the explore-verify-parallel
framework [26, 10]. $\mathtt{BLUCB\mbox{-}Parallel}$ (Algorithm 2)
simultaneously simulates multiple $\mathtt{BLUCB\mbox{-}Verify}_{k}$
(Algorithm 3) with confidence $\delta^{V}_{k}=\delta/2^{k+1}$ for
$k\in\mathbb{N}$. $\mathtt{BLUCB\mbox{-}Verify}_{k}$ first calls
$\mathtt{BLUCB\mbox{-}Explore}$ (Algorithm 4) to guess an optimal super arm
$\hat{M}_{*}$ and collect a _near bottleneck set_ $\hat{B}_{\textup{sub}}$
with _constant confidence_ $\kappa$, and then uses the required confidence
$\delta^{V}_{k}$ to verify the correctness of $\hat{M}_{*}$ by only sampling
base arms in $\hat{M}_{*}$ and $\hat{B}_{\textup{sub}}$. Through parallel
simulations, $\mathtt{BLUCB\mbox{-}Parallel}$ guarantees the $1-\delta$
correctness.

The _key component_ of this framework is $\mathtt{BLUCB\mbox{-}Explore}$
(Algorithm 4), which provides a hypothesized answer $\hat{M}_{*}$ and critical
base arms $\hat{B}_{\textup{sub}}$ for verification to accelerate its
identification process. Below we first describe the procedure of
$\mathtt{BLUCB\mbox{-}Explore}$, and then explicate its two _innovative
techniques_ , i.e. offline subroutine and stopping condition, developed to
handle the challenges (i),(ii). $\mathtt{BLUCB\mbox{-}Explore}$ employs the
subroutine $\mathtt{BottleneckSearch}(\mathcal{M},M_{\textup{ex}},\bm{v})$ to
return the set of bottleneck base arms from all super arms in
$\mathcal{M}\setminus\mathcal{S}(M_{\textup{ex}})$ with respect to weight
vector $\bm{v}$. At each timestep, we first calculate the best super arm
$M_{t}$ under lower reward confidence bound $\underline{\bm{w}}_{t}$, and call
$\mathtt{BottleneckSearch}$ to collect the bottlenecks
$\hat{B}_{\textup{sub},t}$ from all super arms in
$\mathcal{M}\setminus\mathcal{S}(M_{t})$ with respect to
$\underline{\bm{w}}_{t}$ (Line 8). Then, we use a stopping condition (Line 9)
to examine if $M_{t}$ is correct and $\hat{B}_{\textup{sub},t}$ is close
enough to $\hat{B}_{\textup{sub}}$ (with confidence $\kappa$). If so, $M_{t}$
and $\hat{B}_{\textup{sub},t}$ are eligible for verification and returned;
otherwise, we play a base arm from $M_{t}$ and $\hat{B}_{\textup{sub},t}$,
which is most necessary for achieving the stopping condition. In the
following, we explicate the two innovative techniques in
$\mathtt{BLUCB\mbox{-}Explore}$.

Efficient “bottleneck-searching” offline subroutine.
$\mathtt{BottleneckSearch}(\mathcal{M},M_{\textup{ex}},\bm{v})$ (Line 8)
serves as an efficient offline procedure to collect bottlenecks from all super
arms in given decision class
$\mathcal{M}\setminus\mathcal{S}(M_{\textup{ex}})$ with respect to $\bm{v}$.
To achieve efficiency, the main idea behind $\mathtt{BottleneckSearch}$ is to
avoid enumerating super arms in the combinatorial space, but only enumerate
base arms $e\in[n]$ to check if $e$ is the bottleneck of some super arm in
$\mathcal{M}\setminus\mathcal{S}(M_{\textup{ex}})$. 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 $\mathcal{S}(M_{\textup{ex}})$). This
efficient offline subroutine solves challenge (ii) on computation complexity
(see Section B.2.1 for its pseudo-codes and details).

Delicate “check-near-bottleneck” stopping condition. The stopping condition
(Line 9) aims to ensure the returned
$\hat{B}_{\textup{sub},t}=\hat{B}_{\textup{sub}}$ to satisfy the following
Property (1): for each sub-optimal super arm $M_{\textup{sub}}$, some base arm
$e$ such that
$w(e)\leq\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})+\mathtt{MinW}(M_{\textup{sub}},\bm{w}))$
is included in $\hat{B}_{\textup{sub}}$, which implies that $e$ is near to the
actual bottleneck of $M_{\textup{sub}}$ within
$\frac{1}{2}\Delta_{M_{*},M_{\textup{sub}}}$, and cannot be anyone in
$\tilde{N}$. Property (1) is crucial for $\mathtt{BLUCB\mbox{-}Verify}$ to
achieve the optimal sample complexity, since it guarantees that in
verification using $\hat{B}_{\textup{sub}}$ to verify $M_{*}$ just costs the
same order of samples as using $B_{\textup{sub}}$, 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., $\forall
e\in\hat{B}_{\textup{sub},t},\bar{w}_{t}(e)\leq\frac{1}{2}(\mathtt{MinW}(M_{t},\underline{\bm{w}}_{t})+\underline{w}_{t}(e))$,
using the definition of $\mathtt{BottleneckSearch}$, we have that for any
$M^{\prime}\in\mathcal{M}\setminus\mathcal{S}(M_{t})$, its bottleneck
$e^{\prime}$ with respect to $\underline{\bm{w}}_{t}$ is included in
$\hat{B}_{\textup{sub},t}$ and satisfies that

$\displaystyle
w(e^{\prime})\leq\bar{w}_{t}(e^{\prime})\overset{\textup{(a)}}{\leq}\frac{1}{2}(\mathtt{MinW}(M_{t},\underline{\bm{w}}_{t})+\mathtt{MinW}(M^{\prime},\underline{\bm{w}}_{t}))\leq\frac{1}{2}(\mathtt{MinW}(M_{t},\bm{w})+\mathtt{MinW}(M^{\prime},\bm{w})),$

where inequality (a) comes from
$\bar{w}_{t}(e^{\prime})\leq\frac{1}{2}(\mathtt{MinW}(M_{t},\underline{\bm{w}}_{t})+\underline{w}_{t}(e^{\prime}))$
and
$\underline{w}_{t}(e^{\prime}))=\mathtt{MinW}(M^{\prime},\underline{\bm{w}}_{t})$.
Hence, we can defer that $\mathtt{MinW}(M^{\prime},\bm{w})\leq
w(e^{\prime})\leq\frac{1}{2}(\mathtt{MinW}(M_{t},\bm{w})+\mathtt{MinW}(M^{\prime},\bm{w}))$
for any $M^{\prime}\in\mathcal{M}\setminus\mathcal{S}(M_{t})$, and thus
$M_{t}=M_{*}$ (with confidence $\kappa$). In addition, the returned
$\hat{B}_{\textup{sub},t}$ satisfies Property (1). This stopping condition
offers knowledge of a hypothesized optimal super arm $\hat{M}_{*}$ and a near
bottleneck set $\hat{B}_{\textup{sub}}$ for verification, which solves the
challenge (i) and enables the overall sample complexity to achieve the
optimality for small enough $\delta$. 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 $\mathtt{BLUCB\mbox{-}Parallel}$ in
Theorem 2.

######  Theorem 2 (Improved Fixed-confidence Upper Bound).

For any $\delta<0.01$, with probability at least $1-\delta$, algorithm
$\mathtt{BLUCB\mbox{-}Parallel}$ (Algorithm 2) for CPE-B in the FC setting
returns $M_{*}$ and takes the expected sample complexity

$\displaystyle O\Bigg{(}\sum_{e\in M_{*}\cup
N}\frac{R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\Bigg{(}\frac{1}{\delta}\sum_{e\in
M_{*}\cup
N}\frac{R^{2}n}{(\Delta^{\textup{C}}_{e})^{2}}\Bigg{)}+\sum_{e\in\tilde{N}}\frac{R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\Bigg{(}\sum_{e\in\tilde{N}}\frac{R^{2}n}{(\Delta^{\textup{C}}_{e})^{2}}\Bigg{)}\Bigg{)}.$

Results without dependence on $\tilde{N}$ in the dominant term. Let
$H_{V}=\sum_{e\in M_{*}\cup N}\frac{R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}$ and
$H_{E}=\sum_{e\in[n]}\frac{R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}$ denote the
verification and exploration hardness, respectively. Compared to
$\mathtt{BLUCB}$ (Theorem 1), the sample complexity of
$\mathtt{BLUCB\mbox{-}Parallel}$ removes the redundant dependence on
$\tilde{N}$ in the $\ln\delta^{-1}$ term, which guarantees better performance
when $\ln\delta^{-1}\geq\frac{H_{E}}{H_{E}-H_{V}}$, i.e.,
$\delta\leq\exp(-\frac{H_{E}}{H_{E}-H_{V}})$. This sample complexity matches
the lower bound (within a logarithmic factor) under small enough $\delta$. For
the example in Figure 1, $\mathtt{BLUCB\mbox{-}Parallel}$ only requires
$\tilde{O}((\frac{2}{\Delta_{e_{2},e_{1}}^{2}}+\frac{1}{\Delta_{e_{4},e_{1}}^{2}})\ln\delta^{-1})$
samples, which are just enough efforts (optimal) for identifying $M_{*}$.

The condition $\delta<0.01$ in Theorem 2 is due to that the used explore-
verify-parallel framework [26, 10] needs a small $\delta$ to guarantee that
$\mathtt{BLUCB\mbox{-}Parallel}$ can maintain the same order of sample
complexity as its sub-algorithm $\mathtt{BLUCB\mbox{-}Verify}_{k}$. Prior pure
exploration works [26, 10] also have such condition on $\delta$.

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
$\mathtt{MaxOracle}$ and $\mathtt{BottleneckSearch}$ only spend $O(E)$ and
$O(E^{2}(E+V))$ time, respectively. See Section E for more time complexity
analysis.

##  4 Lower Bound for the Fixed-Confidence Setting

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 _$\delta$ -correct algorithm_ as follows. For any confidence
parameter $\delta\in(0,1)$, we call an algorithm $\mathcal{A}$ a
$\delta$-correct algorithm if for the fixed-confidence CPE-B problem,
$\mathcal{A}$ returns the optimal super arm with probability at least
$1-\delta$.

######  Theorem 3 (Fixed-confidence Lower Bound).

There exists a family of instances for the fixed-confidence CPE-B problem, for
which given any $\delta\in(0,0.1)$, any $\delta$-correct algorithm has the
expected sample complexity

$\Omega\Bigg{(}\sum_{e\in M_{*}\cup
N}\frac{R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\frac{1}{\delta}\right)\Bigg{)}.$

This lower bound demonstrates that the sample complexity of
$\mathtt{BLUCB\mbox{-}Parallel}$ (Theorem 2) is optimal (within a logarithmic
factor) under small enough $\delta$, since its $\ln\delta^{-1}$ (dominant)
term does not depend on unnecessary base arms $\tilde{N}$ either. In addition,
if we impose some constraint on the constructed instances, the sample
complexity of $\mathtt{BLUCB}$ (Theorem 1) can also match the lower bound up
to a logarithmic factor (see Appendix C for details). The condition
$\delta<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\delta^{-1}$. Existing pure exploration works [11, 10] also have such
condition on $\delta$ in their lower bounds.

Notice that, both our lower and upper bounds depend on the tight base-arm-
level (instead of super-arm-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.

##  5 Algorithm for the Fixed-Budget Setting

Algorithm 5 $\mathtt{BSAR}$, algorithm for CPE-B in the FB setting

1: Input: budget $T$, $\mathcal{M}$, and $\mathtt{AR-Oracle}$.

2: $\tilde{\log}(n)\\!\leftarrow\\!\\!\sum_{i=1}^{n}\\!\frac{1}{i}$.
$\tilde{T}_{0}\\!\leftarrow\\!0$. $A_{1},R_{1}\\!\leftarrow\\!\varnothing$.

3: for $t=1,\dots,n$ do

4:
$\tilde{T}_{t}\leftarrow\left\lceil\frac{T-n}{\tilde{\log}(n)(n-t+1)}\right\rceil$

5: $U_{t}\leftarrow[n]\setminus(A_{t}\cup R_{t})$

6: Play each $e\in U_{t}$ for $\tilde{T}_{t}-\tilde{T}_{t-1}$ times

7: Update empirical mean $\hat{w}_{t}(e)$, $\forall e\\!\in\\!U_{t}$

8: $\hat{w}_{t}(e)\leftarrow\infty$ for all $e\in A_{t}$

9: $M_{t}\leftarrow\mathtt{AR\mbox{-}Oracle}(\perp,R_{t},\hat{\bm{w}}_{t})$

10: for each $e\in U_{t}$ do

11: if $e\in M_{t}$ then

12:
$\tilde{M}_{t,e}\\!\leftarrow\\!\mathtt{AR\mbox{-}Oracle}(\perp,R_{t}\\!\cup\\!\\{e\\},\hat{\bm{w}}_{t})$

13: else

14:
$\tilde{M}_{t,e}\leftarrow\mathtt{AR\mbox{-}Oracle}(e,R_{t},\hat{\bm{w}}_{t})$

15: end if

16: // $\mathtt{AR\mbox{-}Oracle}$ returns $\perp$ if the calculated feasible
set is empty

17: end for

18: $p_{t}\\!\\!\leftarrow\\!\\!\operatornamewithlimits{argmax}\limits_{e\in
U_{t}}\mathtt{MinW}(\\!M_{t},\\!\hat{\bm{w}}_{t}\\!)\\!-\\!\mathtt{MinW}(\\!\tilde{M}_{t,e},\\!\hat{\bm{w}}_{t}\\!)$

19: // $\mathtt{MinW}(\perp,\hat{\bm{w}}_{t})=-\infty$

20: if $p_{t}\in M_{t}$ then

21: $A_{t+1}\leftarrow A_{t}\cup\\{p_{t}\\},R_{t+1}\leftarrow R_{t}$

22: else

23: $A_{t+1}\leftarrow A_{t},R_{t+1}\leftarrow R_{t}\cup\\{p_{t}\\}$

24: end if

25: end for

26: return $A_{n+1}$

For CPE-B in the FB setting, we design a novel algorithm $\mathtt{BSAR}$ that
adopts a special acceptance scheme for bottleneck identification. We allow
$\mathtt{BSAR}$ to access an efficient accept-reject oracle
$\mathtt{AR\mbox{-}Oracle}$, which takes an accepted base arm $e$ or $\perp$,
a rejected base arm set $R$ and a weight vector $\bm{v}$ as inputs, and
returns an optimal super arm from the decision class
$\mathcal{M}(e,R)=\\{M\in\mathcal{M}:e\in M,R\cap M=\varnothing\\}$ with
respect to $\bm{v}$, i.e.,
$\mathtt{AR\mbox{-}Oracle}\in\operatornamewithlimits{argmax}_{M\in\mathcal{M}(e,R)}\mathtt{MinW}(M,\bm{w})$.
If $\mathcal{M}(e,R)$ is empty, $\mathtt{AR\mbox{-}Oracle}$ simply returns
$\perp$. Such an efficient oracle exists for many decision classes, e.g.,
paths, matchings and spanning trees (see Appendix D for implementation
details).

$\mathtt{BSAR}$ allocates the sample budget $T$ to $n$ phases adaptively, and
maintains the accepted set $A_{t}$, rejected set $R_{t}$ and undetermined set
$U_{t}$. In each phase, we only sample base arms in $U_{t}$ and set the
empirical rewards of base arms in $A_{t}$ to infinity (Line 8). Then, we call
$\mathtt{AR\mbox{-}Oracle}$ to compute the empirical best super arm $M_{t}$.
For each $e\in U_{t}$, we forbid $R_{t}$ and constrain $e$ inside/outside the
calculated super arms and find the empirical best super arm $\tilde{M}_{t,e}$
from the restricted decision class (Lines 12,14). Then, we accept or reject
the base arm $p_{t}$ that maximizes the empirical reward gap between $M_{t}$
and $\tilde{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 $\hat{w}_{t}(e)\leftarrow\infty$ for all $e\in A_{t}$ (Line
8) is critical to the correctness and computation efficiency of
$\mathtt{BSAR}$. Since $A_{t}$ and $R_{t}$ 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 $A_{t}$ to infinity, the estimation of
bottleneck values for sub-optimal super arms $M_{\textup{sub}}$ avoids the
disturbance of $A_{t}$, because each $M_{\textup{sub}}$ has at least one base
arm with reward lower than $\mathtt{OPT}$ and this base arm will never be
included in $A_{t}$ (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 $M_{\textup{sub}}$ and does not affect the
correctness of the choice $p_{t}$ (Line 18). Hence, this acceptance scheme
guarantees the correctness of $\mathtt{BSAR}$ in bottleneck identification
task.

Compared to existing CPE-L algorithm $\mathtt{CSAR}$ [11], they force the
whole set $A_{t}$ inside the calculated super arms in the oracle, i.e.,
replacing Lines 12,14 with
$\mathtt{AR\mbox{-}Oracle}(A_{t},R_{t}\cup\\{e\\},\hat{\bm{w}}_{t})$ and
$\mathtt{AR\mbox{-}Oracle}(A_{t}\cup\\{e\\},R_{t},\hat{\bm{w}}_{t})$, and
deleting Line 8. Such acceptance strategy incurs _exponential-time_ complexity
on $s$-$t$ path instances,444Finding a $s$-$t$ path which contains a given
edge set is NP-hard. See Appendix D.3 for its proof. and _only works_ for the
linear reward function, where the common part $A_{t}$ between two compared
super arms can be canceled out. If one naively applies their acceptance
strategy to our bottleneck problem, the common part $A_{t}$ 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 $p_{t}$ in theoretical analysis.

$\mathtt{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 $\mathtt{AR\mbox{-}Oracle}$ (only work
with one accepted base arm instead of $A_{t}$). Specifically, for $E$ edges
and $V$ vertices, the time complexity of $\mathtt{AR\mbox{-}Oracle}$ is
$O(E(E+V))$ and $\mathtt{BSAR}$ only spends $O(E^{2}(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 $\mathtt{BSAR}$. For
$e\in M_{*}$,
$\Delta^{\textup{B}}_{e}=\mathtt{OPT}-\max_{M\in\mathcal{M}:e\notin
M}\mathtt{MinW}(M,\bm{w})$, and for $e\notin M_{*}$,
$\Delta^{\textup{B}}_{e}=\mathtt{OPT}-\max_{M\in\mathcal{M}:e\in
M}\mathtt{MinW}(M,\bm{w})$. Let
$\Delta^{\textup{B}}_{(1)},\dots,\Delta^{\textup{B}}_{(n)}$ be the permutation
of $\Delta^{\textup{B}}_{1},\dots,\Delta^{\textup{B}}_{n}$ such that
$\Delta^{\textup{B}}_{(1)}\leq\dots\leq\Delta^{\textup{B}}_{(n)}$, and the
fixed-budget problem hardness is defined as
$H^{\textup{B}}=\max_{i\in[n]}\frac{i}{(\Delta^{\textup{B}}_{(i)})^{2}}$. Let
$\tilde{\log}(n)=\sum_{i=1}^{n}\frac{1}{i}$.

######  Theorem 4 (Fixed-budget Upper Bound).

For any $T>n$, algorithm $\mathtt{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\left(n^{2}\exp\left(-\frac{T-n}{\tilde{\log}(n)R^{2}H^{B}}\right)\right).$

Compared to the uniform sampling algorithm, which plays all base arms equally
and has $O(n\exp(-\frac{T}{R^{2}n\Delta^{-2}_{\min}}))$ error probability with
$\Delta_{\min}=\mathtt{OPT}-\max_{M\neq M_{*}}\mathtt{MinW}(M,\bm{w})$,
Theorem 4 achieves a significantly better correctness guarantee (when
$\Delta^{B}_{e}>\Delta_{\min}$ for most $e\in[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, 24, 29, 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
$\mathtt{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 $\mathtt{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

(a) FC, $s$-$t$ path, large $\delta$

(b) FC, $s$-$t$ path, small $\delta$

(c) FC, real-world, small $\delta$

(d) FB, matching

(e) FB, matching

(f) FB, real-world

Figure 2: Experiments for CPE-B in the FC/FB setting on synthetic and real-
world datasets.

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\in[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
$\Delta_{\min}\in[0.4,0.7]$. For the matching instances, we use a $5\times 3$
complete bipartite graph, where $n=15$, $w(e)=[0.1,1.08]$ and
$\Delta_{\min}\in[0.03,0.07]$. We change $\Delta_{\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 flights. In
this instance, $n=9$ and $w(e)\in[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 Appendix A.

In the FC setting, we set a large $\delta=0.005$ and a small
$\delta=\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\in[6000,15000]$, and perform $3000$ independent runs to show the
error probability across runs. For all experiments, the random reward of each
edge $e\in[n]$ is i.i.d. drawn from Gaussian distribution
$\mathcal{N}(w(e),1)$.

Experiments for the FC setting. We compare our
$\mathtt{BLUCB}$/$\mathtt{BLUCB\mbox{-}Parallel}$ with three baselines.
$\mathtt{BLUCB-}$ is an ablation variant of $\mathtt{BLUCB}$, which replaces
the sample strategy (Lines 12-14) with the one that uniformly samples a base
arm in critical super arms. $\mathtt{CLUCB\mbox{-}B}$ [11] is the state-of-
the-art fixed-confidence CPE-L algorithm run with bottleneck reward function.
$\mathtt{UniformFC}$ is a fixed-confidence uniform sampling algorithm. As
shown in Figures 2(a)-2(c), $\mathtt{BLUCB}$ and
$\mathtt{BLUCB\mbox{-}Parallel}$ achieve better performance than the three
baselines, which validates the statistical efficiency of our bottleneck-
adaptive sample strategy. Under small $\delta$,
$\mathtt{BLUCB\mbox{-}Parallel}$ enjoys lower sample complexity than
$\mathtt{BLUCB}$ due to its careful algorithmic design to avoid playing
unnecessary base arms, which matches our theoretical results.

Experiments for the FB setting. Our $\mathtt{BSAR}$ is compared with four
baselines. As an ablation variant of $\mathtt{BSAR}$, $\mathtt{BSR}$ removes
the special acceptance scheme of $\mathtt{BSAR}$. $\mathtt{CSAR\mbox{-}B}$
[11] is the state-of-the-art fixed-budget CPE-L algorithm implemented with
bottleneck reward function. $\mathtt{CUCB\mbox{-}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. $\mathtt{UniformFB}$ is a fixed-budget uniform
sampling algorithm. One sees from Figures 2(d)-2(f) that, $\mathtt{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.

##  7 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
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.

## References

  * [1] Yasin Abbasi-Yadkori, 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 39–1, 2012.
  * [3] Jean-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, Marc Barthelemy, Romualdo Pastor-Satorras, and Alessandro Vespignani.  The architecture of complex weighted networks.  Proceedings of the National Academy of Sciences, 101(11):3747–3752, 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, 7(1):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 R 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–1541, 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.  Combinatorial 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–1105, 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] Loukas Georgiadis, Giuseppe F Italiano, Luigi Laura, and Nikos Parotsidis.  2-vertex connectivity in directed graphs.  Information and Computation, 261:248–264, 2018.
  * [21] A. V. Goldberg.  Finding a maximum density subgraph.  Technical report, University of California Berkeley, 1984.
  * [22] Yuri Gurevich and Saharon Shelah.  Expected computation time for hamiltonian path problem.  SIAM Journal on Computing, 16(3):486–502, 1987.
  * [23] Dorit S Hochbaum and Sung-Pil Hong.  About strongly polynomial time algorithms for quadratic optimization over submodular constraints.  Mathematical programming, 69(1):269–309, 1995.
  * [24] Weiran Huang, Jungseul Ok, Liang Li, and Wei Chen.  Combinatorial pure exploration with continuous and separable reward functions and its applications.  In International Joint Conference on Artificial Intelligence, pages 2291–2297, 2018.
  * [25] Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone.  PAC subset selection in stochastic multi-armed bandits.  In International Conference on Machine Learning, pages 655–662, 2012.
  * [26] Zohar S Karnin.  Verification based solution for structured mab problems.  In Advances in Neural Information Processing Systems, pages 145–153, 2016.
  * [27] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier.  On the complexity of best-arm identification in multi-armed bandit models.  The Journal of Machine Learning Research, 17(1):1–42, 2016.
  * [28] Samir Khuller and Barna Saha.  On finding dense subgraphs.  In International Colloquium on Automata, Languages, and Programming, pages 597–608. Springer, 2009.
  * [29] Yuko Kuroki, Atsushi Miyauchi, Junya Honda, and Masashi Sugiyama.  Online dense subgraph discovery via blurred-graph feedback.  In International Conference on Machine Learning, pages 5522–5532, 2020.
  * [30] 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–1773, 2020.
  * [31] Tze Leung Lai and Herbert Robbins.  Asymptotically efficient adaptive allocation rules.  Advances in Applied Mathematics, 6(1):4–22, 1985.
  * [32] 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.
  * [33] M Peinhardt and V Kaibel.  On the bottleneck shortest path problem.  Technical Report, 2006.
  * [34] 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.
  * [35] Chao Tao, Saúl Blanco, and Yuan Zhou.  Best arm identification in linear bandits with linear dimension dependency.  In International Conference on Machine Learning, pages 4877–4886, 2018.
  * [36] William R Thompson.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  Biometrika, 25(3/4):285–294, 1933.
  * [37] Hoang Tuy, Saied Ghannadan, Athanasios Migdalas, and Peter Värbrand.  A strongly polynomial algorithm for a concave production-transportation problem with a fixed number of nonlinear variables.  Mathematical Programming, 72(3):229–258, 1996.
  * [38] Wenwei Yue, Changle Li, and Guoqiang Mao.  Urban traffic bottleneck identification based on congestion propagation.  In 2018 IEEE International Conference on Communications, pages 1–6, 2018.
  * [39] 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.  In Proceedings of the 28th ACM International Conference on Multimedia, pages 1245–1254, 2020.

## Appendix

##  Appendix A More Details of Experimental Setups

(a) $s$-$t$ path

(b) Matching

(c) Real-world air route

Figure 3: Graphs of the $s$-$t$ path, matching and real-world air route
instances in our experiments.

In this section, we supplement more details of graphs and the expected rewards
of edges (base arms) for the $s$-$t$ path, matching and real-world air route
instances in our experiments.

Figure 3(a) shows the graph of $s$-$t$ path instance. The red path contains
$15$ edges with weights $[\Delta_{\min},2\Delta_{\min},\dots,15\Delta_{\min}]$
and is the optimal $s$-$t$ path with the maximum bottleneck value. There are
$5$ paths connecting $v_{3}$ and $t$, and each of them contains $14$ edges
with weights $\Delta_{\min}$. In this instance, we set
$\Delta_{\min}\in[0.4,0.7]$.

As shown in Figure 3(b), the matching instance uses a $5\times 3$ complete
bipartite graph with $n=15$ edges. The red matching is the optimal one, which
contains three edges with weights
$[0.1+14\Delta_{\min},0.1+13\Delta_{\min},0.1+12\Delta_{\min}]$. The remaining
12 black edges have weights
$[0.1,0.1+\Delta_{\min},\dots,0.1+11\Delta_{\min}]$ from top to bottom. In
this instance, $\Delta_{\min}\in[0.03,0.07]$.

Figure 3(c) illustrates the graph of real-world air route instance, which is
originated from [6]. We regard an airport (e.g., Los Angeles) as a vertex and
a direct flight connecting two airports (e.g., Los Angeles $\leftrightarrow$
Chicago) as an edge. The number marked on each edge denotes the number of
available seats of this flight, i.e., the expected reward of this edge. Our
objective is to find an air route connecting Los Angeles and Atlanta, and the
optimal route is [Los Angeles $\leftrightarrow$ Chicago $\leftrightarrow$
Atlanta].

##  Appendix B CPE-B in the Fixed-Confidence Setting

###  B.1 Proof for Algorithm $\mathtt{BLUCB}$

In this subsection, we prove the sample complexity of Algorithm
$\mathtt{BLUCB}$ (Theorem 1).

In order to prove Theorem 1, we first introduce the following Lemmas 1-5. For
ease of notation, we define a function $\mathtt{MinE}(M,\bm{v})$ to return the
base arm with the minimum reward in $M$ with respect to weight vector
$\bm{v}$, i.e.,
$\mathtt{MinE}(M,\bm{v})\in\operatornamewithlimits{argmin}_{e\in M}v(e)$.

######  Lemma 1 (Concentration).

For any $t>0$ and $e\in[n]$, defining the confidence radius
$\textup{rad}_{t}(e)=R\sqrt{\frac{2\ln(\frac{4nt^{3}}{\delta})}{T_{t}(e)}}$
and the events

$\xi_{t}=\left\\{\forall e\in[n],\
|w(e)-\hat{w}_{t}(e)|<\textup{rad}_{t}(e)\right\\}$

and

$\xi=\bigcap\limits_{t=1}^{\infty}\xi_{t},$

then, we have

$\Pr[\xi]\geq 1-\delta.$

###### Proof.

Since for any $e\in[n]$, the reward distribution of base arm $e$ has an R-sub-
Gaussian tail and the mean of $w(e)$, according to the Hoeffding’s inequality,
we have that for any $t>0$ and $e\in[n]$,

$\displaystyle\Pr\left[|w(e)-\hat{w}_{t}(e)|\geq
R\sqrt{\frac{2\ln(\frac{4nt^{3}}{\delta})}{T_{t}(e)}}\right]=$
$\displaystyle\sum_{s=1}^{t-1}\Pr\left[|w(e)-\hat{w}_{t}(e)|\geq
R\sqrt{\frac{2\ln(\frac{4nt^{3}}{\delta})}{T_{t}(e)}},\ T_{t}(e)=s\right]$
$\displaystyle\leq$ $\displaystyle\sum_{s=1}^{t-1}\frac{\delta}{2nt^{3}}$
$\displaystyle\leq$ $\displaystyle\frac{\delta}{2nt^{2}}$

Using a union bound over $e\in[n]$, we have

$\displaystyle\Pr\left[\xi_{t}\right]\leq\frac{\delta}{2t^{2}}$

and thus

$\displaystyle\Pr\left[\xi\right]\geq$ $\displaystyle
1-\sum_{t=1}^{\infty}\Pr[\neg\xi_{t}]$ $\displaystyle\geq$ $\displaystyle
1-\sum_{t=1}^{\infty}\frac{\delta}{2t^{2}}$ $\displaystyle\geq$ $\displaystyle
1-\delta$

∎

######  Lemma 2.

Assume that event $\xi$ occurs. Then, if algorithm $\mathtt{BLUCB}$ (Algorithm
1) terminates at round $t$, we have $M_{t}=M_{*}$.

###### Proof.

According to the stop condition (Line 9 of Algorithm 1), when algorithm
$\mathtt{BLUCB}$ terminates at round $t$, we have that for any
$M\in\mathcal{M}\setminus\mathcal{S}(M_{t})$,

$\mathtt{MinW}(M_{t},\bm{w})\geq\mathtt{MinW}(M_{t},\underline{\bm{w}}_{t})\geq\mathtt{MinW}(M,\bar{\bm{w}}_{t})\geq\mathtt{MinW}(M,\bm{w}).$

For any $M\in\mathcal{S}(M_{t})$, according to the property of the bottleneck
reward function, we have

$\mathtt{MinW}(M_{t},\bm{w})\geq\mathtt{MinW}(M,\bm{w}).$

Thus, we have $\mathtt{MinW}(M_{t},\bm{w})\geq\mathtt{MinW}(M,\bm{w})$ for any
$M\neq M_{t}$ and according to the unique assumption of $M_{*}$, we obtain
$M_{t}=M_{*}$. ∎

######  Lemma 3.

Assume that event $\xi$ occurs. For any $e\in M_{*}$, if
$\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{4}=\frac{1}{4}(w(e)-\max_{M\neq
M_{*}}\mathtt{MinW}(M,\bm{w}))$, then, base arm $e$ will not be pulled at
round $t$, i.e., $p_{t}\neq e$.

###### Proof.

Suppose that for some $e\in M_{*}$,
$\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{4}=\frac{1}{4}(w(e)-\max_{M\neq
M_{*}}\mathtt{MinW}(M,\bm{w}))$ and $p_{t}=e$. According to the selection
strategy of $p_{t}$, we have that
$\textup{rad}_{t}(c_{t})<\frac{\Delta^{\textup{C}}_{e}}{4}$ and
$\textup{rad}_{t}(d_{t})<\frac{\Delta^{\textup{C}}_{e}}{4}$.

Case (i): If $e$ is selected from $M_{*}$, then one of $M_{t}$ and
$\tilde{M}_{t}$ is $M_{*}$ such that
$e=\mathtt{MinE}(M_{*},\underline{\bm{w}}_{t})$, and the other is a sub-
optimal super arm $M^{\prime}$. Let
$e^{\prime}=\mathtt{MinE}(M^{\prime},\underline{\bm{w}}_{t})$.
$\underline{w}(e^{\prime})\leq\underline{w}(\mathtt{MinE}(M^{\prime},\bm{w}))\leq
w(\mathtt{MinE}(M^{\prime},\bm{w}))=\mathtt{MinW}(M^{\prime},\bm{w})$.
$\\{e,e^{\prime}\\}=\\{c_{t},d_{t}\\}$. Then,

$\displaystyle\underline{w}(e)-\bar{w}(e^{\prime})\geq$ $\displaystyle
w(e)-\underline{w}(e^{\prime})-2\textup{rad}_{t}(e)-2\textup{rad}_{t}(e^{\prime})$
$\displaystyle>$ $\displaystyle
w(e)-\mathtt{MinW}(M^{\prime},\bm{w})-\Delta^{\textup{C}}_{e}$
$\displaystyle\geq$ $\displaystyle 0.$

Then, we have

$\displaystyle\mathtt{MinW}(M_{*},\underline{\bm{w}}_{t})=\underline{w}(e)>\bar{w}(e^{\prime})\geq\mathtt{MinW}(M^{\prime},\bar{\bm{w}}_{t}),$

and algorithm $\mathtt{BLUCB}$ must have stopped, which gives a contradiction.

Case (ii): If $e$ is selected from a sub-optimal super arm $M$, then one of
$M_{t}$ and $\tilde{M}_{t}$ is $M$ such that
$e=\mathtt{MinE}(M,\underline{\bm{w}}_{t})$. Since $e\in M_{*}$, we have
$w(e)\geq\mathtt{MinW}(M_{*},\bm{w})>\mathtt{MinW}(M,\bm{w})$ and thus
$w(e)-\mathtt{MinW}(M,\bm{w})=w(e)-w(\mathtt{MinE}(M,\bm{w}))>0$. Then,

$\displaystyle\underline{w}(e)-\underline{w}(\mathtt{MinE}(M,\bm{w}))\geq$
$\displaystyle w(e)-2\textup{rad}_{t}(e)-\mathtt{MinW}(M,\bm{w})$
$\displaystyle>$ $\displaystyle
w(e)-\mathtt{MinW}(M,\bm{w})-\frac{\Delta^{\textup{C}}_{e}}{2}$
$\displaystyle>0,$

which contradicts $e=\mathtt{MinE}(M,\underline{\bm{w}}_{t})$. ∎

######  Lemma 4.

Assume that event $\xi$ occurs. For any $e\notin
M_{*},w(e)\geq\mathtt{MinW}(M_{*},\bm{w})$, if
$\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{2}=\frac{1}{2}(w(e)-\max_{M\in\mathcal{M}:e\in
M}\mathtt{MinW}(M,\bm{w}))$, then, base arm $e$ will not be pulled at round
$t$, i.e., $p_{t}\neq e$.

###### Proof.

Suppose that for some $e\notin M_{*},w(e)\geq\mathtt{MinW}(M_{*},\bm{w})$,
$\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{2}=\frac{1}{2}(w(e)-\max_{M\in\mathcal{M}:e\in
M}\mathtt{MinW}(M,\bm{w}))$ and $p_{t}=e$. According to the selection strategy
of $p_{t}$, we have that
$\textup{rad}_{t}(c_{t})<\frac{\Delta^{\textup{C}}_{e}}{2}$ and
$\textup{rad}_{t}(d_{t})<\frac{\Delta^{\textup{C}}_{e}}{2}$.

Since $e\notin M_{*}$, $e$ is selected from a sub-optimal super arm $M$. One
of $M_{t}$ and $\tilde{M}_{t}$ is $M$ such that
$e=\mathtt{MinE}(M,\underline{\bm{w}}_{t})$. Since
$w(e)\geq\mathtt{MinW}(M_{*},\bm{w})>\mathtt{MinW}(M,\bm{w})$, we have
$w(e)-\mathtt{MinW}(M,\bm{w})=w(e)-w(\mathtt{MinE}(M,\bm{w}))>0$. Then,

$\displaystyle\underline{w}(e)-\underline{w}(\mathtt{MinE}(M,\bm{w}))\geq$
$\displaystyle w(e)-2\textup{rad}_{t}(e)-\mathtt{MinW}(M,\bm{w})$
$\displaystyle>$ $\displaystyle
w(e)-\mathtt{MinW}(M,\bm{w})-\Delta^{\textup{C}}_{e}$ $\displaystyle\geq$
$\displaystyle 0,$

which contradicts $e=\mathtt{MinE}(M,\underline{\bm{w}}_{t})$. ∎

######  Lemma 5.

Assume that event $\xi$ occurs. For any $e\notin
M_{*},w(e)<\mathtt{MinW}(M_{*},\bm{w})$, if
$\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{4}=\frac{1}{4}(\mathtt{MinW}(M_{*},\bm{w})-\max_{M\in\mathcal{M}:e\in
M}\mathtt{MinW}(M,\bm{w}))$, then, base arm $e$ will not be pulled at round
$t$, i.e., $p_{t}\neq e$.

###### Proof.

Suppose that for some $e\notin M_{*},w(e)<\mathtt{MinW}(M_{*},\bm{w})$,
$\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{4}=\frac{1}{4}(\mathtt{MinW}(M_{*},\bm{w})-\max_{M\in\mathcal{M}:e\in
M}\mathtt{MinW}(M,\bm{w}))$ and $p_{t}=e$. According to the selection strategy
of $p_{t}$, we have that
$\textup{rad}_{t}(c_{t})<\frac{\Delta^{\textup{C}}_{e}}{4}$ and
$\textup{rad}_{t}(d_{t})<\frac{\Delta^{\textup{C}}_{e}}{4}$.

Case (i): If one of $M_{t}$ and $\tilde{M}_{t}$ is $M_{*}$, then the other is
a sub-optimal super arm $M$ such that
$e=\mathtt{MinE}(M,\underline{\bm{w}}_{t})$. Let
$f=\mathtt{MinE}(M_{*},\underline{\bm{w}}_{t})$.
$\\{e,f\\}=\\{c_{t},d_{t}\\}$. Then, we have

$\displaystyle\underline{w}(f)-\bar{w}(e)\geq$ $\displaystyle
w(f)-2\textup{rad}_{t}(f)-\underline{w}(e)-2\textup{rad}_{t}(e)$
$\displaystyle>$ $\displaystyle w(f)-\underline{w}(e)-\Delta^{\textup{C}}_{e}$
$\displaystyle\geq$
$\displaystyle\mathtt{MinW}(M_{*},\bm{w})-\underline{w}(\mathtt{MinE}(M,\bm{w}))-\Delta^{\textup{C}}_{e}$
$\displaystyle\geq$
$\displaystyle\mathtt{MinW}(M_{*},\bm{w})-\mathtt{MinW}(M,\bm{w})-\Delta^{\textup{C}}_{e}$
$\displaystyle\geq$ $\displaystyle 0.$

Thus,

$\displaystyle\mathtt{MinW}(M_{*},\bm{w})\geq\underline{w}(\mathtt{MinE}(M_{*},\bm{w}))\geq\underline{w}(f)>\bar{w}(e)\geq\mathtt{MinW}(M,\bar{\bm{w}}_{t})$

and algorithm $\mathtt{BLUCB}$ must have stopped, which gives a contradiction.

Case (ii): If neither $M_{t}$ nor $\tilde{M}_{t}$ is $M_{*}$ and $e=c_{t}$,
i.e., $e=\mathtt{MinE}(M_{t},\underline{\bm{w}}_{t})$, we have

$\displaystyle\bar{w}(d_{t})\geq\mathtt{MinW}(\tilde{M}_{t},\bar{\bm{w}}_{t})\geq\mathtt{MinW}(M_{*},\bar{\bm{w}}_{t})\geq\mathtt{MinW}(M_{*},\bm{w})$

and

$\displaystyle\underline{w}(d_{t})=\mathtt{MinW}(\tilde{M}_{t},\underline{\bm{w}}_{t})\leq\mathtt{MinW}(M_{t},\underline{\bm{w}}_{t})\leq\mathtt{MinW}(M_{t},\bm{w}),$

and thus

$\displaystyle 2\textup{rad}_{t}(d_{t})=$
$\displaystyle\bar{w}(d_{t})-\underline{w}(d_{t})$ $\displaystyle\geq$
$\displaystyle\mathtt{MinW}(M_{*},\bm{w})-\mathtt{MinW}(M_{t},\bm{w}),$

which contradicts
$\textup{rad}_{t}(d_{t})<\frac{\Delta^{\textup{C}}_{e}}{4}<\frac{\Delta^{\textup{C}}_{e}}{2}\leq\frac{\mathtt{MinW}(M_{*},\bm{w})-\mathtt{MinW}(M_{t},\bm{w})}{2}$.

Case (iii): If neither $M_{t}$ nor $\tilde{M}_{t}$ is $M_{*}$ and $e=d_{t}$,
i.e., $e=\mathtt{MinE}(\tilde{M}_{t},\underline{\bm{w}}_{t})$. Let
$c(M_{*},\tilde{M}_{t})=\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})+\mathtt{MinW}(\tilde{M}_{t},\bm{w}))$.
If $c(M_{*},\tilde{M}_{t})<w(e)<\mathtt{MinW}(M_{*},\bm{w})$, we have

$\displaystyle\underline{w}(e)\geq$ $\displaystyle w(e)-2\textup{rad}_{t}(e)$
$\displaystyle>$ $\displaystyle
c(M_{*},\tilde{M}_{t})-\frac{\Delta^{\textup{C}}_{e}}{2}$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})+\mathtt{MinW}(\tilde{M}_{t},\bm{w}))-\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})-\mathtt{MinW}(\tilde{M}_{t},\bm{w}))$
$\displaystyle=$ $\displaystyle\mathtt{MinW}(\tilde{M}_{t},\bm{w})$
$\displaystyle\geq$
$\displaystyle\underline{w}(\mathtt{MinE}(\tilde{M}_{t},\bm{w})),$

which contradicts $e=\mathtt{MinE}(\tilde{M}_{t},\underline{\bm{w}}_{t})$.

If $\mathtt{MinW}(\tilde{M}_{t},\bm{w})\leq w(e)\leq c(M_{*},\tilde{M}_{t})$,
we have

$\displaystyle\mathtt{MinW}(\tilde{M}_{t},\bar{\bm{w}}_{t})\leq$
$\displaystyle\bar{w}(e)$ $\displaystyle\leq$ $\displaystyle
w(e)+2\textup{rad}_{t}(e)$ $\displaystyle<$ $\displaystyle
c(M_{*},\tilde{M}_{t})+\frac{\Delta^{\textup{C}}_{e}}{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})+\mathtt{MinW}(\tilde{M}_{t},\bm{w}))+\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})-\mathtt{MinW}(\tilde{M}_{t},\bm{w}))$
$\displaystyle=$ $\displaystyle\mathtt{MinW}(M_{*},\bm{w})$
$\displaystyle\leq$ $\displaystyle\mathtt{MinW}(M_{*},\bar{\bm{w}}_{t}).$

In addition, from the uniqueness of $M_{*}$, we have
$M_{*}\notin\mathcal{S}(\tilde{M}_{t})$. Thus, the inequality
$\mathtt{MinW}(\tilde{M}_{t},\bar{\bm{w}}_{t})<\mathtt{MinW}(M_{*},\bar{\bm{w}}_{t})$
violates the optimality of $\tilde{M}_{t}$ with respect to $\bar{\bm{w}}_{t}$.
∎

Next, we prove Theorem 1.

###### Proof.

For any $e\in[n]$, let $T(e)$ denote the number of samples for base arm $e$,
and $t_{e}$ denote the last timestep at which $e$ is pulled. Then, we have
$T_{t_{e}}=T(e)-1$. Let $T$ denote the total number of samples. According to
Lemmas 3-5, we have

$\displaystyle
R\sqrt{\frac{2\ln(\frac{4nt_{e}^{3}}{\delta})}{T(e)-1}}\geq\frac{1}{4}\Delta^{\textup{C}}_{e}$

Thus, we obtain

$\displaystyle
T(e)\leq\frac{32R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\frac{4nt_{e}^{3}}{\delta}\right)+1\leq\frac{32R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\frac{4nT^{3}}{\delta}\right)+1$

Summing over $e\in[n]$, we have

$\displaystyle
T\leq\sum_{e\in[n]}\frac{32R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\frac{4nT^{3}}{\delta}\right)+n\leq\sum_{e\in[n]}\frac{96R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\frac{2nT}{\delta}\right)+n,$

where $\sum_{e\in[n]}\frac{R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\geq n$. Then,
applying Lemma 20, we have

$\displaystyle T\leq$
$\displaystyle\sum_{e\in[n]}\frac{576R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\frac{2n^{2}}{\delta}\sum_{e\in[n]}\frac{96R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\right)+n$
$\displaystyle=$ $\displaystyle
O\left(\sum_{e\in[n]}\frac{R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\sum_{e\in[n]}\frac{R^{2}n^{2}}{(\Delta^{\textup{C}}_{e})^{2}\delta}\right)+n\right)$
$\displaystyle=$ $\displaystyle
O\left(\sum_{e\in[n]}\frac{R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\sum_{e\in[n]}\frac{R^{2}n}{(\Delta^{\textup{C}}_{e})^{2}\delta}\right)\right)$

∎

###  B.2 Details for the Improved Algorithm $\mathtt{BLUCB\mbox{-}Parallel}$

In this subsection, we describe algorithm $\mathtt{BLUCB\mbox{-}Parallel}$ and
its sub-algorithms in details, present the pseudo-code of the offline
subroutine $\mathtt{BottleneckSearch}$ in Algorithm 6 and give the proofs of
theoretical results.

####  B.2.1 Detailed Algorithm Description

$\mathtt{BLUCB\mbox{-}Parallel}$ simulates multiple sub-algorithms
$\mathtt{BLUCB\mbox{-}Verify}$ (Algorithm 3) with different confidence
parameters in parallel. For $k\in\mathbb{N}$,
$\mathtt{BLUCB\mbox{-}Verify}_{k}$ denotes the sub-algorithm
$\mathtt{BLUCB\mbox{-}Verify}$ with confidence parameter
$\delta^{V}_{k}=\frac{\delta}{2^{k+1}}$ At each timestep $t$, we start or
resume sub-algorithms $\mathtt{BLUCB\mbox{-}Verify}_{k}$ such that $t$ is
divisible by $2^{k}$ with only one sample, and then suspend these sub-
algorithms. Such parallel simulation is performed until there exist some sub-
algorithm which terminates and returns the answer $M_{\textup{out}}$, and then
we output $M_{\textup{out}}$ as the answer of
$\mathtt{BLUCB\mbox{-}Parallel}$.

Algorithm $\mathtt{BLUCB\mbox{-}Verify}$ (Algorithm 3) calls Algorithm
$\mathtt{BLUCB\mbox{-}Explore}$ (Algorithm 4) as its preparation procedure.
Algorithm $\mathtt{BLUCB\mbox{-}Explore}$ uses a big constant confidence
parameter $\kappa$ to guesses an optimal super arm and an advice set
$\hat{B}_{\textup{sub}}$ which contains the bottleneck base arms for the sub-
optimal super arms, and then algorithm $\mathtt{BLUCB\mbox{-}Verify}$ verifies
the correctness of the answer provided by $\mathtt{BLUCB\mbox{-}Explore}$ with
the given confidence parameter $\delta^{V}$.

$\mathtt{BLUCB\mbox{-}Explore}$ first calculates an super arm $M_{t}$ with the
maximum pessimistic bottleneck value, and then uses a subroutine
$\mathtt{BottleneckSearch}$ (Algorithm 6) to find the set of bottleneck base
arms $\hat{B}_{\textup{sub},t}$ from all super arms in
$\mathcal{M}\setminus\mathcal{S}(M_{t})$ with respect to the lower reward
confidence bound $\underline{\bm{w}}_{t}$. Then, we check whether for any base
arm $e\in\hat{B}_{\textup{sub},t}$, the optimistic reward of $e$ is lower than
a half of its pessimistic reward plus the pessimistic bottleneck value of
$M_{t}$. If this stopping condition holds, we simply return $M_{t}$ as the
hypothesized optimal super arm and $\hat{B}_{\textup{sub},t}$ as the advice
set. Otherwise, we find the bottleneck $c_{t}$ from $M_{t}$ with respect to
$\underline{\bm{w}}_{t}$, and collect the set of base arms
$\hat{B}^{\prime}_{\textup{sub},t}$ which violate the stopping condition from
$\hat{B}_{\textup{sub},t}$. Let
$P_{t}^{E}\overset{\textup{def}}{=}\hat{B}^{\prime}_{\textup{sub},t}\cup\\{c_{t}\\}$
denote the sampling set of $\mathtt{BLUCB\mbox{-}Explore}$. We plays the base
arm with the maximum confidence radius in $P_{t}^{E}$.

$\mathtt{BLUCB\mbox{-}Verify}$ first calculates the super arm $\tilde{M_{t}}$
with the maximum optimistic bottleneck value in
$\mathcal{M}\setminus\mathcal{S}(\hat{M}_{*})$, and checks whether the
pessimistic bottleneck value of $\hat{M}_{*}$ is higher than the optimistic
bottleneck value of $\tilde{M_{t}}$. If so, we can determine that the answer
$\hat{M}_{*}$ is correct, and simply stop and return $\hat{M}_{*}$. Otherwise,
we find the bottleneck $c_{t}$ from $M_{t}$ with respect to the lower reward
confidence bound $\underline{\bm{w}}_{t}$, and collect the set of base arms
$F_{t}$ whose optimistic rewards are higher than the pessimistic bottleneck
value of $\hat{M}_{*}$ from $\hat{B}_{\textup{sub}}$. Let
$P_{t}^{V}\overset{\textup{def}}{=}F_{t}\cup\\{c_{t}\\}$ denote the sampling
set of $\mathtt{BLUCB\mbox{-}Verify}$. We samples the base arm with the
maximum confidence radius in $P_{t}^{V}$.

Now, we discuss the skillful subroutine $\mathtt{BottleneckSearch}$, which is
formally defined as follows.

######  Definition 2 ($\mathtt{BottleneckSearch}$).

We define $\mathtt{BottleneckSearch}(\mathcal{M},M,\bm{v})$ as an algorithm
that takes decision class $\mathcal{M}$, super arm $M\in\mathcal{M}$ and
weight vector $\bm{v}\in\mathbb{R}^{d}$ as inputs and returns a set of base
arms $A_{\textup{out}}$ that satisfies (i) for any
$M^{\prime}\in\mathcal{M}\setminus\mathcal{S}(M)$, there exists a base arm
$e\in A_{\textup{out}}\cap M^{\prime}$ such that
$\bm{v}(e)=\mathtt{MinW}(M^{\prime},\bm{v})$, and (ii) for any $e\in
A_{\textup{out}}$, there exists a super arm
$M^{\prime}\in\mathcal{M}\setminus\mathcal{S}(M)$ such that $e\in M^{\prime}$
and $\bm{v}(e)=\mathtt{MinW}(M^{\prime},\bm{v})$.

Algorithm 6 $\mathtt{BottleneckSearch}$, offline subroutine of
$\mathtt{BLUCB\mbox{-}Explore}$

1: Input: $\mathcal{M}$, $M_{\textup{ex}}$, $\bm{v}$ and existence oracle
$\mathtt{ExistOracle}(\mathcal{F},e)$: check if there exists a feasible super
arm $M\in\mathcal{F}$ such that $e\in M$, and return $M$ if there exists and
$\perp$ otherwise.

2: $A_{\textup{out}}\leftarrow\varnothing$

3: for $e\in[n]$ do

4: Remove all base arms with rewards lower than $v(e)$ from $\mathcal{M}$, and
obtain $\mathcal{M}_{\geq v(e)}$

5: if $e\\!\in\\!M_{\textup{ex}}$ and
$v(e)\\!=\\!\mathtt{MinW}(M_{\textup{ex}},\bm{v})$ then

6: for each $e_{0}\in M_{\textup{ex}}\setminus\\{e\\}$ do

7: Remove $e_{0}$ from $\mathcal{M}_{\geq v(e)}$, and obtain
$\mathcal{M}_{\geq v(e),-e_{0}}$

8: if $\mathtt{ExistOracle}(\mathcal{M}_{\geq v(e),-e_{0}},e)\neq\perp$, then
$A_{\textup{out}}\leftarrow A_{\textup{out}}\cup\\{e\\}$ and break

9: end for

10: else if $\mathtt{ExistOracle}(\mathcal{M}_{\geq v(e)},e)\neq\perp$ then

11: $A_{\textup{out}}\leftarrow A_{\textup{out}}\cup\\{e\\}$

12: end if

13: end for

14: return $A_{\textup{out}}$

Algorithm 6 illustrates the implementation procedure of
$\mathtt{BottleneckSearch}$. We access the subroutine
$\mathtt{BottleneckSearch}$ an efficient existence oracle
$\mathtt{ExistOracle}(\mathcal{F},e)$, which returns a feasible super arm that
contains base arm $e$ from decision class $\mathcal{F}$ if there exists, and
otherwise returns $\perp$, i.e.,
$\mathtt{ExistOracle}(\mathcal{F},e)\in\\{M\in\mathcal{F}:e\in M\\}$. Such
efficient oracles exist for a wide family of decision classes. For example,
for $s$-$t$ paths, this problem can be reduced to the well-studied $2$-vertex
connectivity problem [20], which is polynomially tractable (see Section E.1
for the proof of reduction). For maximum cardinality matchings, we just need
to remove $e$ and its two end vertices, and then find a feasible maximum
cardinality matching in the remaining graph. For spanning trees, we can just
merge the vertices of $e$ and find a feasible spanning tree in the remaining
graph, which can also be solved efficiently.

In the subroutine $\mathtt{BottleneckSearch}$, we enumerate all the base arms
to collect the bottlenecks. For each enumerated base arm $e$, we first remove
all base arms with the rewards lower than $w(e)$ from $\mathcal{M}$ and obtain
a new decision class $\mathcal{M}_{\geq w(e)}$, in which the super arms only
contain the base arms with the rewards at least $w(e)$. Then, we call
$\mathtt{ExistOracle}$ to check whether there exists a feasible super arm
$M_{e}$ that contains $e$ in $\mathcal{M}_{\geq w(e)}$. If there exist, then
we obtain that $e$ is the bottleneck of $M_{e}$ with respect to $\bm{v}$,
i.e., $e\in M_{e}$ and $w(e)=\mathtt{MinW}(M_{e},\bm{v})$, and add $e$ to the
output set $A_{\textup{out}}$. Otherwise, we can determine that $e$ is not the
bottleneck for any super arm in $\mathcal{M}\setminus\mathcal{S}(M_{t})$ with
respect to $\bm{v}$. However, for the particular $e$ such that $e\in M_{t}$
and $w(e)=\mathtt{MinW}(M_{t},\bm{v})$, directly calling
$\mathtt{ExistOracle}$ can obtain the output $M_{t}$, which should be
excluded. We solve this problem by repeatedly removing each base arm in
$M_{t}\setminus\\{e\\}$ and then calling $\mathtt{ExistOracle}$ on the new
decision classes, which can check whether $e$ is some super arm’s bottleneck
apart from $\mathcal{M}\setminus\mathcal{S}(M_{t})$.

####  B.2.2 Proof for Algorithm $\mathtt{BLUCB\mbox{-}Parallel}$

Below we give the theoretical results for the proposed algorithms.

For algorithm $\mathtt{BLUCB\mbox{-}Explore}$, define the events
$\xi_{0,t}=\left\\{\forall e\in[n],\
|w(e)-\hat{w}_{t}(e)|<\textup{rad}_{t}(e)\right\\}$ and
$\xi_{0}=\bigcap\limits_{t=1}^{\infty}\xi_{0,t}$. Then, similar to Lemma 1, we
have $\Pr[\xi_{0}]\geq 1-\kappa$. For algorithm
$\mathtt{BLUCB\mbox{-}Verify}$, define the events $\xi_{t}=\left\\{\forall
e\in[n],\ |w(e)-\hat{w}_{t}(e)|<\textup{rad}_{t}(e)\right\\}$ and
$\xi=\bigcap\limits_{t=1}^{\infty}\xi_{t}$. Then, applying Lemma 1, we have
$\Pr[\xi]\geq 1-\delta^{V}$. Let
$M_{\textup{second}}=\operatornamewithlimits{argmax}_{M\in\mathcal{M}\setminus\\{M_{*}\\}}\mathtt{MinW}(M,w)$
denote the second best super arm.

######  Lemma 6 (Correctness of $\mathtt{BLUCB\mbox{-}Explore}$).

For algorithm $\mathtt{BLUCB\mbox{-}Explore}$, assume that event $\xi_{0}$
occurs. Then, if algorithm $\mathtt{BLUCB\mbox{-}Explore}$ (Algorithm 4)
terminates at round $t$, we have that (i) $M_{t}=M_{*}$, (ii) for any
$M\in\mathcal{M}\setminus\mathcal{S}(M_{*})$, there exists a base arm
$e\in\hat{B}_{\textup{sub},t}\cap M$ satisfying
$w(e)\leq\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})+\mathtt{MinW}(M,\bm{w}))$,
i.e.,
$\Delta^{\textup{C}}_{\mathtt{MinW}(M_{*},\bm{w}),e}\geq\frac{1}{2}\Delta^{\textup{C}}_{M_{*},M}$
and (iii) for any $e\in\hat{B}_{\textup{sub},t}$, there exists a sub-optimal
super arm $M\in\mathcal{M}\setminus\mathcal{S}(M_{*})$ such that $e\in M$ and
$w(e)\leq\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})+\mathtt{MinW}(M))\leq\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})+\mathtt{MinW}(M_{\textup{second}},\bm{w}))$.

###### Proof.

According to the stop condition (Lines 9 of Algorithm 4) and the definition of
$\mathtt{BottleneckSearch}$ (Definition 2), when algorithm
$\mathtt{BLUCB\mbox{-}Explore}$ (Algorithm 4) terminates at round $t$, we have
that for any $\mathcal{M}\setminus\mathcal{S}(M_{t})$, there exists a base arm
$e\in\hat{B}_{\textup{sub},t}\cap M$ satisfying

$\bar{w}_{t}(e)\leq\frac{1}{2}(\mathtt{MinW}(M_{t},\underline{\bm{w}}_{t})+\underline{w}_{t}(e))=\frac{1}{2}(\mathtt{MinW}(M_{t},\underline{\bm{w}}_{t})+\mathtt{MinW}(M,\underline{\bm{w}}_{t}))$

and thus,

$w(e)\leq\frac{1}{2}(\mathtt{MinW}(M_{t},\bm{w})+\mathtt{MinW}(M,\bm{w})).$

Then, we can obtain $M_{t}=M_{*}$. Otherwise, we cannot find any base arm
$e\in M_{*}$ satisfying
$w(e)\leq\frac{1}{2}(\mathtt{MinW}(M_{t},\bm{w})+\mathtt{MinW}(M_{*},\bm{w}))<\mathtt{MinW}(M_{*},\bm{w})$,
where $M_{t}$ is a sub-optimal super arm. Thus, we have (i) and (ii).

Now we prove (iii). According to the stop condition (Lines 9 of Algorithm 4),
the definition of $\mathtt{BottleneckSearch}$ (Definition 2) and
$M_{t}=M_{*}$, we have that for any $e\in\hat{B}_{\textup{sub},t}$, there
exists a sub-optimal super arm $\mathcal{M}\setminus\mathcal{S}(M_{*})$ such
that $e\in M$ and
$\underline{w}_{t}(e)=\mathtt{MinW}(M,\underline{\bm{w}}_{t})$, and thus

$\bar{w}_{t}(e)\leq\frac{1}{2}(\mathtt{MinW}(M_{*},\underline{\bm{w}}_{t})+\underline{w}_{t}(e))=\frac{1}{2}(\mathtt{MinW}(M_{*},\underline{\bm{w}}_{t})+\mathtt{MinW}(M,\underline{\bm{w}}_{t})),$

Then, for any $e\in\hat{B}_{\textup{sub},t}$,

$w(e)\leq\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})+\mathtt{MinW}(M))\leq\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})+\mathtt{MinW}(M_{\textup{second}},\bm{w})),$

which completes the proof. ∎

######  Lemma 7.

For algorithm $\mathtt{BLUCB\mbox{-}Explore}$, assume that event $\xi_{0}$
occurs. For any two base arms $e_{1},e_{2}\in[n]$ s.t. $w(e_{1})<w(e_{2})$, if
$\textup{rad}_{t}(e_{1})<\frac{1}{6}\Delta^{\textup{C}}_{e_{2},e_{1}}$ and
$\textup{rad}_{t}(e_{2})<\frac{1}{6}\Delta^{\textup{C}}_{e_{2},e_{1}}$, we
have
$\bar{w}_{t}(e_{1})<\frac{1}{2}(\underline{w}_{t}(e_{1})+\underline{w}_{t}(e_{2}))$.

###### Proof.

if $\textup{rad}_{t}(e_{1})<\frac{1}{6}\Delta^{\textup{C}}_{e_{2},e_{1}}$ and
$\frac{1}{6}\Delta^{\textup{C}}_{e_{2},e_{1}}$, we have

$\displaystyle\bar{w}_{t}(e_{1})-\frac{1}{2}(\underline{w}_{t}(e_{1})+\underline{w}_{t}(e_{2}))$
$\displaystyle=\underline{w}_{t}(e_{1})+2\textup{rad}_{t}(e_{1})-\frac{1}{2}(\underline{w}_{t}(e_{1})+\underline{w}_{t}(e_{2}))$
$\displaystyle=\frac{1}{2}\underline{w}_{t}(e_{1})-\frac{1}{2}\underline{w}_{t}(e_{2})+2\textup{rad}_{t}(e_{1})$
$\displaystyle\leq\frac{1}{2}w_{t}(e_{1})-\frac{1}{2}(w_{t}(e_{2})-2\textup{rad}_{t}(e_{2}))+2\textup{rad}_{t}(e_{1})$
$\displaystyle=\frac{1}{2}w_{t}(e_{1})-\frac{1}{2}w_{t}(e_{2})+\textup{rad}_{t}(e_{2})+2\textup{rad}_{t}(e_{1})$
$\displaystyle<\frac{1}{2}w_{t}(e_{1})-\frac{1}{2}w_{t}(e_{2})+\frac{1}{2}\Delta^{\textup{C}}_{e_{2},e_{1}}$
$\displaystyle=0.$

∎

######  Lemma 8.

For algorithm $\mathtt{BLUCB\mbox{-}Explore}$, assume that event $\xi_{0}$
occurs. For any $e\in M_{*}$, if
$\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{12}=\frac{1}{12}(w(e)-\max_{M\neq
M_{*}}\mathtt{MinW}(M,\bm{w}))$, then, base arm $e$ will not be pulled at
round $t$, i.e., $p_{t}\neq e$.

###### Proof.

Suppose that for some $e\in M_{*}$,
$\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{12}=\frac{1}{12}(w(e)-\max_{M\neq
M_{*}}\mathtt{MinW}(M,\bm{w}))$ and $p_{t}=e$.

According to the selection strategy of $p_{t}$, we have that for any $i\in
P_{t}^{E}$,
$\textup{rad}_{t}(i)\leq\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{12}$.
From the definition of $\mathtt{BottleneckSearch}$ and $c_{t}$, we have that
for any $i\in P_{t}^{E}$, there exists a super arm $M\in\mathcal{M}$ such that
$i\in M$ and $\underline{w}_{t}(i)=\mathtt{MinW}(M,\underline{\bm{w}}_{t})$.

Case (i): Suppose that $e$ is selected from a sub-optimal super arm $M$, i.e.,
$e\in M$ and $\underline{w}_{t}(e)=\mathtt{MinW}(M,\underline{\bm{w}}_{t})$.
Then, using
$\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{12}<\frac{\Delta^{\textup{C}}_{e}}{2}$,
we have

$\displaystyle\underline{w}_{t}(e)\geq$ $\displaystyle
w(e)-2\textup{rad}_{t}(e)$ $\displaystyle>$ $\displaystyle
w(e)-(w(e)-\mathtt{MinW}(M_{\textup{second}},\bm{w}))$ $\displaystyle=$
$\displaystyle\mathtt{MinW}(M_{\textup{second}},\bm{w})$ $\displaystyle\geq$
$\displaystyle\mathtt{MinW}(M,\bm{w})$ $\displaystyle\geq$
$\displaystyle\mathtt{MinW}(M,\underline{\bm{w}}_{t})$

which gives a contradiction.

Case (ii): Suppose that $e$ is selected from $M_{*}$, i.e.,
$\underline{w}_{t}(e)=\mathtt{MinW}(M_{*},\underline{\bm{w}}_{t})$. We can
obtain $M_{*}=M_{t}$. Otherwise,

$\displaystyle\mathtt{MinW}(M_{*},\underline{\bm{w}}_{t})=$
$\displaystyle\underline{w}_{t}(e)$ $\displaystyle\geq$ $\displaystyle
w(e)-2\textup{rad}_{t}(e)$ $\displaystyle>$ $\displaystyle
w(e)-(w(e)-\mathtt{MinW}(M_{\textup{second}},\bm{w}))$ $\displaystyle=$
$\displaystyle\mathtt{MinW}(M_{\textup{second}},\bm{w})$ $\displaystyle\geq$
$\displaystyle\mathtt{MinW}(M_{t},\bm{w})$ $\displaystyle\geq$
$\displaystyle\mathtt{MinW}(M_{t},\underline{\bm{w}}_{t})$

Thus, We have $M_{*}=M_{t}$. From the definition of
$\mathtt{BottleneckSearch}$, for any
$e^{\prime}\in\hat{B}^{\prime}_{\textup{sub},t}$, there exists a super arm
$M^{\prime}\in\mathcal{M}\setminus\\{M_{*}\\}$ such that $e^{\prime}\in
M^{\prime}$ and
$\underline{w}_{t}(e^{\prime})=\mathtt{MinW}(M^{\prime},\underline{\bm{w}}_{t})$.
If $w(e^{\prime})\geq\frac{1}{2}(w(e)+\mathtt{MinW}(M^{\prime},\bm{w}))$,
using
$\textup{rad}_{t}(e^{\prime})<\frac{\Delta^{\textup{C}}_{e}}{12}<\frac{\Delta^{\textup{C}}_{e}}{4}$,
we have

$\displaystyle\underline{w}_{t}(e^{\prime})\geq$ $\displaystyle
w(e^{\prime})-2\textup{rad}_{t}(e^{\prime})$ $\displaystyle>$
$\displaystyle\frac{1}{2}(w(e)+\mathtt{MinW}(M^{\prime},\bm{w}))-\frac{1}{2}(w(e)-M_{\textup{second}})$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}(w(e)+\mathtt{MinW}(M^{\prime},\bm{w}))-\frac{1}{2}(w(e)-\mathtt{MinW}(M^{\prime},\bm{w}))$
$\displaystyle=$ $\displaystyle\mathtt{MinW}(M^{\prime},\bm{w}),$

which gives a contradiction.

If $w(e^{\prime})<\frac{1}{2}(w(e)+\mathtt{MinW}(M^{\prime},\bm{w}))$, we have

$\displaystyle\Delta^{\textup{C}}_{e,e^{\prime}}=$ $\displaystyle
w(e)-w(e^{\prime})$ $\displaystyle>$ $\displaystyle
w(e)-\frac{1}{2}(w(e)+\mathtt{MinW}(M^{\prime},\bm{w}))$ $\displaystyle=$
$\displaystyle\frac{1}{2}(w(e)-\mathtt{MinW}(M^{\prime},\bm{w}))$

Since
$\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{12}=\frac{1}{12}(w(e)-\mathtt{MinW}(M_{\textup{second}}))\leq\frac{1}{12}(w(e)-\mathtt{MinW}(M^{\prime},\bm{w}))\leq\frac{1}{6}\Delta^{\textup{C}}_{e,e^{\prime}}$
and
$\textup{rad}_{t}(e^{\prime})\leq\textup{rad}_{t}(e)<\frac{1}{6}\Delta^{\textup{C}}_{e,e^{\prime}}$,
according to Lemma 7, we have

$\displaystyle\bar{w}_{t}(e^{\prime})<$
$\displaystyle\frac{1}{2}(\underline{w}_{t}(e)+\underline{w}_{t}(e^{\prime}))$
$\displaystyle=$
$\displaystyle\frac{1}{2}(\mathtt{MinW}(M_{t},\underline{\bm{w}}_{t})+\underline{w}_{t}(e^{\prime})),$

which contradicts the definition of $\hat{B}^{\prime}_{\textup{sub},t}$. ∎

######  Lemma 9.

For algorithm $\mathtt{BLUCB\mbox{-}Explore}$, assume that event $\xi_{0}$
occurs. For any $e\notin M_{*},w(e)\geq\mathtt{MinW}(M_{*},\bm{w})$, if
$\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{2}=\frac{1}{2}(w(e)-\max_{M\in\mathcal{M}:e\in
M}\mathtt{MinW}(M,\bm{w}))$, then, base arm $e$ will not be pulled at round
$t$, i.e., $p_{t}\neq e$.

###### Proof.

Suppose that for some $e\notin M_{*},w(e)\geq\mathtt{MinW}(M_{*},\bm{w})$,
$\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{2}=\frac{1}{2}(w(e)-\max_{M\in\mathcal{M}:e\in
M}\mathtt{MinW}(M,\bm{w}))$ and $p_{t}=e$.

According to the selection strategy of $p_{t}$, we have that for any $i\in
P_{t}^{E}$,
$\textup{rad}_{t}(i)\leq\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{12}$.
From the definition of $\mathtt{BottleneckSearch}$ and $c_{t}$, we have that
for any $i\in P_{t}^{E}$, there exists a super arm $M\in\mathcal{M}$ such that
$i\in M$ and $\underline{w}_{t}(i)=\mathtt{MinW}(M,\underline{\bm{w}}_{t})$.

Since $e\notin M_{*}$, $e$ is selected from a sub-optimal super arm
$M^{\prime}$, i.e., $e\in M^{\prime}$ and
$\underline{w}_{t}(e)=\mathtt{MinW}(M^{\prime},\underline{\bm{w}}_{t})$. Then,

$\displaystyle\underline{w}_{t}(e)\geq$ $\displaystyle
w(e)-2\textup{rad}_{t}(e)$ $\displaystyle>$ $\displaystyle
w(e)-(w(e)-\max_{M\in\mathcal{M}:e\in M}\mathtt{MinW}(M,\bm{w}))$
$\displaystyle=$ $\displaystyle\max_{M\in\mathcal{M}:e\in
M}\mathtt{MinW}(M,\bm{w})$ $\displaystyle\geq$
$\displaystyle\mathtt{MinW}(M^{\prime},\bm{w})$ $\displaystyle\geq$
$\displaystyle\mathtt{MinW}(M^{\prime},\underline{\bm{w}}_{t})$

which contradicts
$\underline{w}_{t}(e)=\mathtt{MinW}(M^{\prime},\underline{\bm{w}}_{t})$. ∎

######  Lemma 10.

For algorithm $\mathtt{BLUCB\mbox{-}Explore}$, assume that event $\xi_{0}$
occurs. For any $e\notin M_{*},w(e)<\mathtt{MinW}(M_{*},\bm{w})$, if
$\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{12}=\frac{1}{12}(\mathtt{MinW}(M_{*},\bm{w})-\max_{M\in\mathcal{M}:e\in
M}\mathtt{MinW}(M,\bm{w}))$, then, base arm $e$ will not be pulled at round
$t$, i.e., $p_{t}\neq e$.

###### Proof.

Suppose that for some $e\notin M_{*},w(e)<\mathtt{MinW}(M_{*},\bm{w})$,
$\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{12}=\frac{1}{12}(\mathtt{MinW}(M_{*},\bm{w})-\max_{M\in\mathcal{M}:e\in
M}\mathtt{MinW}(M,\bm{w}))$ and $p_{t}=e$.

According to the selection strategy of $p_{t}$, we have that for any $i\in
P_{t}^{E}$,
$\textup{rad}_{t}(i)\leq\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{12}$.
From the definition of $\mathtt{BottleneckSearch}$ and $c_{t}$, we have that
for any $i\in P_{t}^{E}$, there exists a super arm $M\in\mathcal{M}$ such that
$i\in M$ and $\underline{w}_{t}(i)=\mathtt{MinW}(M,\underline{\bm{w}}_{t})$.
Thus, there exists a sub-optimal super arm $M^{\prime}\in\mathcal{M}$ such
that $e\in M^{\prime}$ and
$\underline{w}_{t}(e)=\mathtt{MinW}(M^{\prime},\underline{\bm{w}}_{t})$.

Case (i) Suppose that
$w(e)\geq\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})+\mathtt{MinW}(M^{\prime},\bm{w}))$.
Using
$\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{12}<\frac{\Delta^{\textup{C}}_{e}}{4}$,
we have

$\displaystyle\underline{w}_{t}(e)\geq$ $\displaystyle
w(e)-2\textup{rad}_{t}(e)$ $\displaystyle>$
$\displaystyle\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})+\mathtt{MinW}(M^{\prime},\bm{w}))-\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})-\max_{M\in\mathcal{M}:e\in
M}\mathtt{MinW}(M,\bm{w}))$ $\displaystyle=$
$\displaystyle\frac{1}{2}\mathtt{MinW}(M^{\prime},\bm{w})+\frac{1}{2}\max_{M\in\mathcal{M}:e\in
M}\mathtt{MinW}(M,\bm{w})$ $\displaystyle\geq$
$\displaystyle\mathtt{MinW}(M^{\prime},\bm{w}),$

which contradicts
$\underline{w}_{t}(e)=\mathtt{MinW}(M^{\prime},\underline{\bm{w}}_{t})$.

Case (ii) Suppose that
$w(e)<\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})+\mathtt{MinW}(M^{\prime},\bm{w}))$.
According to the definition of $\mathtt{BottleneckSearch}$ (Definition 2) and
$c_{t}$, there exists a base arm
$\tilde{e}\in\hat{B}_{\textup{sub},t}\cap\\{c_{t}\\}$ satisfying $\tilde{e}\in
M_{*}$ and
$\underline{w}_{t}(\tilde{e})=\mathtt{MinW}(M_{*},\underline{\bm{w}}_{t})$.

First, we prove $\tilde{e}\in P_{t}^{E}$ and thus
$\textup{rad}_{t}(\tilde{e})\leq\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{12}$.
If $M_{*}=M_{t}$, then $\tilde{e}=c_{t}$ and the claim holds. If $M_{*}\neq
M_{t}$, then $\tilde{e}\in\hat{B}_{\textup{sub},t}$. We can obtain that
$\tilde{e}$ will be put into $\hat{B}^{\prime}_{\textup{sub},t}\subseteq
P_{t}^{E}$. Otherwise, we have

$w(\tilde{e})\leq\bar{w}_{t}(\tilde{e})\leq\frac{1}{2}(\mathtt{MinW}(M_{t},\underline{\bm{w}}_{t})+\underline{w}_{t}(\tilde{e}))\leq\frac{1}{2}(\mathtt{MinW}(M_{t},\bm{w})+w(\tilde{e})).$

Since $w(\tilde{e})\geq\mathtt{MinW}(M_{*},\bm{w})$ and
$\mathtt{MinW}(M_{t},\bm{w})<\mathtt{MinW}(M_{*},\bm{w})$, the above
inequality cannot hold. Thus, we obtain that $\tilde{e}$ will be put into
$\hat{B}^{\prime}_{\textup{sub},t}\subseteq P_{t}^{E}$ and thus
$\textup{rad}_{t}(\tilde{e})\leq\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{12}$.

Next, we discuss the following two cases: (a) $e=c_{t}$ and (b) $e\neq c_{t}$.

(a) if $e=c_{t}$, then $M_{t}\neq M_{*}$. Using
$\textup{rad}_{t}(\tilde{e})\leq\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{12}<\frac{\Delta^{\textup{C}}_{e}}{2}$,
we have

$\displaystyle\mathtt{MinW}(M_{*},\underline{\bm{w}}_{t})=$
$\displaystyle\underline{w}_{t}(\tilde{e})$ $\displaystyle\geq$ $\displaystyle
w(e)-2\textup{rad}_{t}(e)$ $\displaystyle>$ $\displaystyle
w(e)-(\mathtt{MinW}(M_{*},\bm{w})-\max_{M\in\mathcal{M}:e\in
M}\mathtt{MinW}(M,\bm{w}))$ $\displaystyle\geq$
$\displaystyle\mathtt{MinW}(M_{*},\bm{w})-(\mathtt{MinW}(M_{*},\bm{w})-\mathtt{MinW}(M_{t},\bm{w}))$
$\displaystyle\geq$ $\displaystyle\mathtt{MinW}(M_{t},\bm{w})$
$\displaystyle\geq$
$\displaystyle\mathtt{MinW}(M_{t},\underline{\bm{w}}_{t}),$

which contradicts the definition of $M_{t}$.

(b) if $e\neq c_{t}$, i.e., $e\in\hat{B}^{\prime}_{\textup{sub},t}$ we have

$\displaystyle\Delta^{\textup{C}}_{\tilde{e},e}=$ $\displaystyle
w(\tilde{e})-w(e)$ $\displaystyle>$
$\displaystyle\mathtt{MinW}(M_{*},\bm{w})-\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})+\mathtt{MinW}(M^{\prime},\bm{w}))$
$\displaystyle=$
$\displaystyle\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})-\mathtt{MinW}(M^{\prime},\bm{w}))$

Since
$\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{12}=\frac{1}{12}(\mathtt{MinW}(M_{*},\bm{w})-\max_{M\in\mathcal{M}:e\in
M}\mathtt{MinW}(M,\bm{w}))\leq\frac{1}{12}(\mathtt{MinW}(M_{*},\bm{w})-\mathtt{MinW}(M^{\prime},\bm{w}))<\frac{1}{6}\Delta^{\textup{C}}_{\tilde{e},e}$
and
$\textup{rad}_{t}(\tilde{e})\leq\textup{rad}_{t}(e)<\frac{1}{6}\Delta^{\textup{C}}_{\tilde{e},e}$,
according to Lemma 7, we have

$\displaystyle\bar{w}_{t}(e)<$
$\displaystyle\frac{1}{2}(\underline{w}_{t}(\tilde{e})+\underline{w}_{t}(e))$
$\displaystyle=$
$\displaystyle\frac{1}{2}(\mathtt{MinW}(M_{*},\underline{\bm{w}}_{t})+\underline{w}_{t}(e))$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}(\mathtt{MinW}(M_{t},\underline{\bm{w}}_{t})+\underline{w}_{t}(e^{\prime}))$

which contradicts the definition of $\hat{B}^{\prime}_{\textup{sub},t}$. ∎

######  Theorem 5 (Sample Complexity of $\mathtt{BLUCB\mbox{-}Explore}$).

With probability at least $1-\kappa$, the $\mathtt{BLUCB\mbox{-}Explore}$
algorithm (Algorithm 4) will return $M_{*}$ with sample complexity

$O\left(\sum_{e\in[n]}\frac{R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\sum_{e\in[n]}\frac{R^{2}n}{(\Delta^{\textup{C}}_{e})^{2}\kappa}\right)\right).$

###### Proof.

For any $e\in[n]$, let $T(e)$ denote the number of samples for base arm $e$,
and $t_{e}$ denote the last timestep at which $e$ is pulled. Then, we have
$T_{t_{e}}=T(e)-1$. Let $T$ denote the total number of samples. According to
Lemmas 8-10, we have

$\displaystyle
R\sqrt{\frac{2\ln(\frac{4nt_{e}^{3}}{\kappa})}{T(e)-1}}\geq\frac{1}{12}\Delta^{\textup{C}}_{e}$

Thus, we obtain

$\displaystyle
T(e)\leq\frac{288R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\frac{4nt_{e}^{3}}{\kappa}\right)+1\leq\frac{288R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\frac{4nT^{3}}{\kappa}\right)+1$

Summing over $e\in[n]$, we have

$\displaystyle
T\leq\sum_{e\in[n]}\frac{288R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\frac{4nT^{3}}{\kappa}\right)+n\leq\sum_{e\in[n]}\frac{864R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\frac{2nT}{\kappa}\right)+n,$

where $\sum_{e\in[n]}\frac{R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\geq n$. Then,
applying Lemma 20, we have

$\displaystyle T\leq$
$\displaystyle\sum_{e\in[n]}\frac{5184R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\frac{2n^{2}}{\kappa}\sum_{e\in[n]}\frac{864R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\right)+n$
$\displaystyle=$ $\displaystyle
O\left(\sum_{e\in[n]}\frac{R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\sum_{e\in[n]}\frac{R^{2}n^{2}}{(\Delta^{\textup{C}}_{e})^{2}\kappa}\right)+n\right)$
$\displaystyle=$ $\displaystyle
O\left(\sum_{e\in[n]}\frac{R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\sum_{e\in[n]}\frac{R^{2}n}{(\Delta^{\textup{C}}_{e})^{2}\kappa}\right)\right).$

∎

######  Lemma 11.

For algorithm $\mathtt{BLUCB\mbox{-}Verify}$, assume that event
$\xi_{0}\cap\xi$ occurs. For any $e\in M_{*}$, if
$\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{8}=\frac{1}{8}(w(e)-\max_{M\neq
M_{*}}\mathtt{MinW}(M,\bm{w}))$, then, base arm $e$ will not be pulled at
round $t$, i.e., $p_{t}\neq e$.

###### Proof.

Suppose that for some $e\in M_{*}$,
$\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{8}=\frac{1}{8}(w(e)-\max_{M\neq
M_{*}}\mathtt{MinW}(M,\bm{w}))$ and $p_{t}=e$.

Since event $\xi_{0}$ occurs, according to Lemma 6, we have that (i)
$\hat{M}_{*}=M_{*}$, (ii) for any $M\neq M_{*}$, there exists a base arm
$e\in\hat{B}_{\textup{sub}}\cap M$ satisfying
$w(e)\leq\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})+\mathtt{MinW}(M,\bm{w}))$,
i.e.,
$\Delta^{\textup{C}}_{\mathtt{MinW}(M_{*},\bm{w}),e}\geq\frac{1}{2}\Delta^{\textup{C}}_{M_{*},M}$
and (iii) for any $i\in\hat{B}_{\textup{sub}}$, there exists a sub-optimal
super arm $M\neq M_{*}$ such that $i\in M$ and
$w(i)\leq\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})+\mathtt{MinW}(M))\leq\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})+\mathtt{MinW}(M_{\textup{second}},\bm{w}))$.
According to the selection strategy of $p_{t}$, we have that for any $i\in
P_{t}^{V}$,
$\textup{rad}_{t}(i)\leq\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{8}$.

First, since for any $i\in\hat{B}_{\textup{sub}}$,
$w(i)\leq\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})+\mathtt{MinW}(M_{\textup{second}},\bm{w}))<\mathtt{MinW}(M_{*},\bm{w})$
and $w(e)\geq\mathtt{MinW}(M_{*},\bm{w})$, we can obtain that $e=c_{t}$.

Then, for any $i\in F_{t}$, we have

$\displaystyle\Delta^{\textup{C}}_{e,i}=$ $\displaystyle w(e)-w(i)$
$\displaystyle\geq$ $\displaystyle
w(e)-\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})+\mathtt{MinW}(M_{\textup{second}},\bm{w}))$
$\displaystyle\geq$ $\displaystyle
w(e)-\frac{1}{2}(w(e)+\mathtt{MinW}(M_{\textup{second}},\bm{w}))$
$\displaystyle=$
$\displaystyle\frac{1}{2}(w(e)-\mathtt{MinW}(M_{\textup{second}},\bm{w}))$
$\displaystyle=$ $\displaystyle\frac{1}{2}\Delta^{\textup{C}}_{e}$

and

$\displaystyle\underline{w}_{t}(c_{t})-\bar{w}_{t}(i)=$
$\displaystyle\underline{w}_{t}(e)-\bar{w}_{t}(i)$ $\displaystyle\geq$
$\displaystyle w(e)-2\textup{rad}_{t}(e)-(w(i)+2\textup{rad}_{t}(i))$
$\displaystyle=$
$\displaystyle\Delta^{\textup{C}}_{e,i}-2\textup{rad}_{t}(e)-2\textup{rad}_{t}(i)$
$\displaystyle>$
$\displaystyle\frac{1}{2}\Delta^{\textup{C}}_{e}-\frac{\Delta^{\textup{C}}_{e}}{4}-\frac{\Delta^{\textup{C}}_{e}}{4}$
$\displaystyle=$ $\displaystyle 0,$

which implies $F_{t}=\varnothing$. Thus, for any $i\in\hat{B}_{\textup{sub}}$,
$\underline{w}_{t}(c_{t})\geq\bar{w}_{t}(i)$.

According to Lemma 6(ii), for any $M^{\prime}\neq\hat{M}_{*}$, there exists a
base arm $e^{\prime}\in\hat{B}_{\textup{sub}}\cap M^{\prime}$, we have

$\displaystyle\mathtt{MinW}(\hat{M}_{*},\underline{\bm{w}}_{t})=$
$\displaystyle\underline{w}_{t}(c_{t})$ $\displaystyle\geq$
$\displaystyle\bar{w}_{t}(e^{\prime})$ $\displaystyle\geq$
$\displaystyle\mathtt{MinW}(M^{\prime},\bar{\bm{w}}_{t})$

which implies that algorithm 3 has already stopped. ∎

######  Lemma 12.

For algorithm $\mathtt{BLUCB\mbox{-}Verify}$, assume that event
$\xi_{0}\cap\xi$ occurs. For any $e\notin
M_{*},w(e)<\mathtt{MinW}(M_{*},\bm{w})$, if
$\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{8}=\frac{1}{8}(\mathtt{MinW}(M_{*},\bm{w})-\max_{M\in\mathcal{M}:e\in
M}\mathtt{MinW}(M,\bm{w}))$, then, base arm $e$ will not be pulled at round
$t$, i.e., $p_{t}\neq e$.

###### Proof.

Suppose that for some $e\notin M_{*},w(e)<\mathtt{MinW}(M_{*},\bm{w})$,
$\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{8}=\frac{1}{8}(\mathtt{MinW}(M_{*},\bm{w})-\max_{M\in\mathcal{M}:e\in
M}\mathtt{MinW}(M,\bm{w}))$ and $p_{t}=e$.

Since event $\xi_{0}$ occurs, according to Lemma 6, we have that (i)
$\hat{M}_{*}=M_{*}$, (ii) for any $M\neq M_{*}$, there exists a base arm
$e\in\hat{B}_{\textup{sub}}\cap M$ satisfying
$w(e)\leq\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})+\mathtt{MinW}(M,\bm{w}))$,
i.e.,
$\Delta^{\textup{C}}_{\mathtt{MinW}(M_{*},\bm{w}),e}\geq\frac{1}{2}\Delta^{\textup{C}}_{M_{*},M}$
and (iii) for any $i\in\hat{B}_{\textup{sub}}$, there exists a sub-optimal
super arm $M\neq M_{*}$ such that $i\in M$ and
$w(i)\leq\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})+\mathtt{MinW}(M))\leq\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})+\mathtt{MinW}(M_{\textup{second}},\bm{w}))$.
According to the selection strategy of $p_{t}$, we have that for any $i\in
P_{t}^{V}$,
$\textup{rad}_{t}(i)\leq\textup{rad}_{t}(e)<\frac{\Delta^{\textup{C}}_{e}}{8}$.

Since $e\notin M_{*}=\hat{M}_{*}$, we have that $e\in F_{t}$ and there exists
a sub-optimal super arm $M^{\prime}$ such that $e\in M^{\prime}$ and
$w(e)\leq\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})+\mathtt{MinW}(M^{\prime}))$.
Then, we have

$\displaystyle\underline{w}_{t}(c_{t})-\bar{w}_{t}(e)\geq$ $\displaystyle
w(c_{t})-2\textup{rad}_{t}(c_{t})-(w(e)+2\textup{rad}_{t}(e))$
$\displaystyle\geq$
$\displaystyle\mathtt{MinW}(M_{*},\bm{w})-\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})+\mathtt{MinW}(M^{\prime},\bm{w}))-2\textup{rad}_{t}(c_{t})-2\textup{rad}_{t}(e)$
$\displaystyle>$
$\displaystyle\frac{1}{2}\Delta^{\textup{C}}_{M_{*},M^{\prime}}-\frac{\Delta^{\textup{C}}_{e}}{4}-\frac{\Delta^{\textup{C}}_{e}}{4}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\Delta^{\textup{C}}_{M_{*},M^{\prime}}-\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})-\max_{M\in\mathcal{M}:e\in
M}\mathtt{MinW}(M,\bm{w}))$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}\Delta^{\textup{C}}_{M_{*},M^{\prime}}-\frac{1}{2}(\mathtt{MinW}(M_{*},\bm{w})-\mathtt{MinW}(M^{\prime},\bm{w}))$
$\displaystyle=$ $\displaystyle 0,$

which contradicts $e\in F_{t}$. ∎

Recall that $B=\\{e\mid e\notin M_{*},w(e)<\mathtt{MinW}(M_{*},\bm{w})\\}$ and
$B^{c}=\\{e\mid e\notin M_{*},w(e)\geq\mathtt{MinW}(M_{*},\bm{w})\\}$.

######  Theorem 6 (Sample Complexity of $\mathtt{BLUCB\mbox{-}Verify}$).

With probability at least $1-\kappa-\delta^{V}$, the
$\mathtt{BLUCB\mbox{-}Verify}$ algorithm (Algorithm 3) will return $M_{*}$
with sample complexity

$O\left(\sum_{e\in
B^{c}}\frac{R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\sum_{e\in
B^{c}}\frac{R^{2}n}{(\Delta^{\textup{C}}_{e})^{2}}\right)+\sum_{e\in M_{*}\cup
B}\frac{R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\sum_{e\in M_{*}\cup
B}\frac{R^{2}n}{(\Delta^{\textup{C}}_{e})^{2}\delta^{V}}\right)\right).$

###### Proof.

Assume that event $\xi_{0}\cap\xi$ occurs. $\Pr[\xi_{0}\cap\xi]\geq
1-\kappa-\delta^{V}$.

First, we prove the correctness. According to Lemma 6, the hypothesized
$\hat{M}_{*}$ outputted by the preparation procedure
$\mathtt{BLUCB\mbox{-}Explore}$ is exactly the optimal super arm, and thus if
$\mathtt{BLUCB\mbox{-}Verify}$ terminates, it returns the correct answer.

Next, we prove the sample complexity upper bound. According to Theorem 5, the
preparation procedure $\mathtt{BLUCB\mbox{-}Explore}$ costs sample complexity

$O\left(\sum_{e\in[n]}\frac{R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\sum_{e\in[n]}\frac{R^{2}n}{(\Delta^{\textup{C}}_{e})^{2}\kappa}\right)\right).$

Then, we bound the sample complexity of the following verification part.
Following the analysis procedure of Theorem 5 with Lemmas 11,12, we can obtain
that the verification part cost sample complexity

$\sum_{e\in M_{*}\cup
B}\frac{R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\sum_{e\in M_{*}\cup
B}\frac{R^{2}n}{(\Delta^{\textup{C}}_{e})^{2}\delta^{V}}\right).$

Combining both parts, we obtain that the sample complexity is bounded by

$\displaystyle O\left(\sum_{e\in
B^{c}}\frac{R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\sum_{e\in
B^{c}}\frac{R^{2}n}{(\Delta^{\textup{C}}_{e})^{2}\kappa}\right)+\sum_{e\in
M_{*}\cup B}\frac{R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\sum_{e\in
M_{*}\cup
B}\frac{R^{2}n}{(\Delta^{\textup{C}}_{e})^{2}\delta^{V}}\right)\right)$
$\displaystyle=$ $\displaystyle O\left(\sum_{e\in
B^{c}}\frac{R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\sum_{e\in
B^{c}}\frac{R^{2}n}{(\Delta^{\textup{C}}_{e})^{2}}\right)+\sum_{e\in M_{*}\cup
B}\frac{R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\sum_{e\in M_{*}\cup
B}\frac{R^{2}n}{(\Delta^{\textup{C}}_{e})^{2}\delta^{V}}\right)\right).$

∎

######  Lemma 13 (Correctness of $\mathtt{BLUCB\mbox{-}Verify}$).

With probability at least $1-\delta$, if algorithm
$\mathtt{BLUCB\mbox{-}Verify}$ (Algorithm 3) terminates, it returns the
optimal super arm $M_{*}$.

###### Proof.

Assume that event $\xi$ occurs, where $\Pr[\xi]\geq 1-\delta^{V}$. If
algorithm $\mathtt{BLUCB\mbox{-}Verify}$ terminates by returning
$\hat{M}_{*}$, we have that for any
$M\in\mathcal{M}\setminus\mathcal{S}(\hat{M}_{*})$,

$\mathtt{MinW}(\hat{M}_{*},\bm{w})\geq\mathtt{MinW}(\hat{M}_{*},\underline{\bm{w}}_{t})\geq\mathtt{MinW}(M,\bar{\bm{w}}_{t})\geq\mathtt{MinW}(M,\bm{w}).$

For any $M\in\mathcal{S}(\hat{M}_{*})$, according to the property of the
bottleneck reward function, we have

$\mathtt{MinW}(\hat{M}_{*},\bm{w})\geq\mathtt{MinW}(M,\bm{w}).$

Thus, we have $\mathtt{MinW}(\hat{M}_{*},\bm{w})\geq\mathtt{MinW}(M,\bm{w})$
for any $M\neq\hat{M}_{*}$ and according to the unique assumption of $M_{*}$,
we obtain $\hat{M}_{*}=M_{*}$. In other words, algorithm
$\mathtt{BLUCB\mbox{-}Verify}$ (Algorithm 3) will never return a wrong answer.
∎

Now, we prove Theorem 2.

###### Proof.

Using Theorem 6, Lemma 13 and Lemma 4.8 in [10], we can obtain this theorem. ∎

###  B.3 PAC Learning

In this subsection, we further study the fixed-confidence CPE-B problem in the
PAC learning setting, where the learner’s objective is to identify a super arm
$M_{\textup{pac}}$ such that
$\mathtt{MinW}(M_{\textup{pac}},\bm{w})\geq\mathtt{OPT}-\varepsilon$, and the
uniqueness assumption of the optimal super arm is dropped. We propose two
algorithms $\mathtt{BLUCB\mbox{-}PAC}$ and
$\mathtt{BLUCB\mbox{-}Parallel\mbox{-}PAC}$ for the PAC learning setting,
based on $\mathtt{BLUCB}$ and $\mathtt{BLUCB\mbox{-}Parallel}$, respectively.

The PAC algorithms and their theoretical guarantees do not require the
uniqueness assumption of the optimal super arm. Compared to the PAC lower
bound, both proposed PAC algorithms achieve the optimal sample complexity for
some family of instances. Similar to the exact case, when $\delta$ is small
enough, the dominant term of sample complexity for algorithm
$\mathtt{BLUCB\mbox{-}Parallel\mbox{-}PAC}$ does not depend on the reward gaps
of unnecessary base arms, and thus $\mathtt{BLUCB\mbox{-}Parallel\mbox{-}PAC}$
achieves better theoretical guarantee than $\mathtt{BLUCB\mbox{-}PAC}$ and
matches the lower bound for a broader family of instances.

####  B.3.1 Algorithm $\mathtt{BLUCB\mbox{-}PAC}$

$\mathtt{BLUCB\mbox{-}PAC}$ simply replaces the stopping condition of
$\mathtt{BLUCB}$ (Line 9 in Algorithm 1) with
$\mathtt{MinW}(\tilde{M}_{t},\bar{\bm{w}_{t}})-\mathtt{MinW}(M_{t},\underline{\bm{w}}_{t})\leq\varepsilon$
to allow an $\varepsilon$ deviation between the returned answer and the
optimal one. The sample complexity of algorithm $\mathtt{BLUCB\mbox{-}PAC}$ is
given as follows.

######  Theorem 7 (Fixed-confidence Upper Bound for PAC).

With probability at least $1-\delta$, the $\mathtt{BLUCB\mbox{-}PAC}$
algorithm will return $M_{\textup{out}}$ such that
$\mathtt{MinW}(M_{\textup{out}},\bm{w})\geq\mathtt{MinW}(M_{*},\bm{w})-\varepsilon$,
with sample complexity

$O\left(\sum_{e\in[n]}\frac{R^{2}}{\max\\{(\Delta^{\textup{C}}_{e})^{2},\varepsilon^{2}\\}}\ln\left(\sum_{e\in[n]}\frac{R^{2}n}{\max\\{(\Delta^{\textup{C}}_{e})^{2},\varepsilon^{2}\\}\delta}\right)\right).$

Now we prove the sample complexity of algorithm $\mathtt{BLUCB\mbox{-}PAC}$
(Theorem 7).

###### Proof.

First, we prove the correctness. When the stop condition of
$\mathtt{BLUCB\mbox{-}PAC}$ is satisfied, we have that for any $M\neq M_{t}$,

$\mathtt{MinW}(M,\bm{w})-\mathtt{MinW}(M_{t},\bm{w})\leq\mathtt{MinW}(M,\bar{\bm{w}}_{t})-\mathtt{MinW}(M_{t},\underline{\bm{w}}_{t})\leq\mathtt{MinW}(\tilde{M}_{t},\bar{\bm{w}}_{t})-\mathtt{MinW}(M_{t},\underline{\bm{w}}_{t})\leq\varepsilon.$

If $M_{t}=M_{*}$, then the correctness holds. If $M_{t}\neq M_{*}$, the
returned super arm $M_{t}$ satisfies

$\mathtt{MinW}(M_{*},\bm{w})-\mathtt{MinW}(M_{t},\bm{w})\leq\varepsilon,$

which guarantees the correctness.

Next, we prove the sample complexity. When inheriting the proof of Theorem 1
for the baseline algorithm $\mathtt{BLUCB}$, to prove Theorem 7 for PAC
leaning, it suffices to prove that for any $e\in[n]$, if
$\textup{rad}_{t}(e)<\frac{\varepsilon}{2}$, base arm $e$ will not be pulled
at round $t$, i.e., $p_{t}\neq e$.

Suppose that $\textup{rad}_{t}(e)<\frac{\varepsilon}{2}$ and $p_{t}=e$.
According to the selection strategy of $p_{t}$, we have
$\textup{rad}_{t}(c_{t})<\frac{\varepsilon}{2}$ and
$\textup{rad}_{t}(d_{t})<\frac{\varepsilon}{2}$. According to the definition
of $d_{t}$, we have

$\displaystyle\mathtt{MinW}(\tilde{M}_{t},\bar{\bm{w}}_{t})-\mathtt{MinW}(M_{t},\underline{\bm{w}}_{t})\leq$
$\displaystyle\bar{w}(d_{t})-\mathtt{MinW}(\tilde{M}_{t},\underline{\bm{w}}_{t})$
$\displaystyle=$ $\displaystyle\bar{w}(d_{t})-\underline{w}(d_{t})$
$\displaystyle=$ $\displaystyle 2\textup{rad}_{t}(d_{t})$ $\displaystyle<$
$\displaystyle\varepsilon,$

which contradicts the stop condition. ∎

####  B.3.2 Algorithm $\mathtt{BLUCB\mbox{-}Parallel\mbox{-}PAC}$

$\mathtt{BLUCB\mbox{-}Parallel\mbox{-}PAC}$ is obtained by simply replacing
the stopping condition of $\mathtt{BLUCB\mbox{-}Verify}$ (Line 10 in Algorithm
3) with
$\mathtt{MinW}(\tilde{M}_{t},\bar{\bm{w}}_{t})-\mathtt{MinW}(M_{t},\underline{\bm{w}}_{t})\leq\varepsilon$.

Theorem 8 presents the sample complexity of algorithm
$\mathtt{BLUCB\mbox{-}Parallel\mbox{-}PAC}$.

######  Theorem 8 (Improved Fixed-confidence Upper Bound for PAC).

For any $\delta<0.01$, with probability at least $1-\delta$, algorithm
$\mathtt{BLUCB\mbox{-}Parallel\mbox{-}PAC}$ returns $M_{*}$ and takes the
expected sample complexity

$\displaystyle O\left(\sum_{e\in M_{*}\cup
N}\frac{R^{2}}{\max\\{(\Delta^{\textup{C}}_{e})^{2},\varepsilon^{2}\\}}\ln\left(\sum_{e\in
M_{*}\cup
N}\frac{R^{2}n}{\max\\{(\Delta^{\textup{C}}_{e})^{2},\varepsilon^{2}\\}\delta}\right)+\sum_{e\in\tilde{N}}\frac{R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\sum_{e\in\tilde{N}}\frac{R^{2}n}{(\Delta^{\textup{C}}_{e})^{2}}\right)\right).$

###### Proof.

First, we prove the correctness. When the stop condition of
$\mathtt{BLUCB\mbox{-}Verify}$ is satisfied, we have that for any
$M\neq\hat{M}_{*}$,

$\mathtt{MinW}(M,\bm{w})-\mathtt{MinW}(\hat{M}_{*},\bm{w})\leq\mathtt{MinW}(M,\bar{\bm{w}}_{t})-\mathtt{MinW}(\hat{M}_{*},\underline{\bm{w}}_{t})\leq\mathtt{MinW}(\tilde{M}_{t},\bar{\bm{w}}_{t})-\mathtt{MinW}(\hat{M}_{*},\underline{\bm{w}}_{t})\leq\varepsilon.$

If $\hat{M}_{*}=M_{*}$, then the correctness holds. If $\hat{M}_{*}\neq
M_{*}$, the returned super arm $\hat{M}_{*}$ satisfies

$\mathtt{MinW}(M_{*},\bm{w})-\mathtt{MinW}(\hat{M}_{*},\bm{w})\leq\varepsilon,$

which guarantees the correctness.

Next, we prove the sample complexity. We inherit the proofs of Theorems 2,6.
Then, to prove Theorem 8 for PAC leaning, it suffices to prove that
conditioning on $\xi_{0}\cap\xi$, for any $e\in[n]$, if
$\textup{rad}_{t}(e)<\frac{\varepsilon}{4}$, base arm $e$ will not be pulled
at round $t$, i.e., $p_{t}\neq e$.

Suppose that $\textup{rad}_{t}(e)<\frac{\varepsilon}{4}$ and $p_{t}=e$.
According to the selection strategy of $p_{t}$, we have
$\textup{rad}_{t}(c_{t})<\frac{\varepsilon}{4}$ and for any $e\in F_{t}$
$\textup{rad}_{t}(e)<\frac{\varepsilon}{4}$. Using
$F_{t}\subseteq\hat{B}_{\textup{sub}}$ and the definition of
$\hat{B}_{\textup{sub}}$, we have that for any $e\in F_{t}$

$\displaystyle\bar{w}(e)-\mathtt{MinW}(\hat{M}_{*},\underline{\bm{w}}_{t})\leq$
$\displaystyle w(e)+2\textup{rad}_{t}(e)-(w(c_{t})-2\textup{rad}_{t}(c_{t}))$
$\displaystyle<$
$\displaystyle\mathtt{MinW}(\hat{M}_{*},\bm{w})+2\textup{rad}_{t}(e)-(\mathtt{MinW}(\hat{M}_{*},\bm{w})-2\textup{rad}_{t}(c_{t}))$
$\displaystyle<$ $\displaystyle 4\cdot\frac{\varepsilon}{4}$ $\displaystyle=$
$\displaystyle\varepsilon$

and thus

$\displaystyle\mathtt{MinW}(\tilde{M}_{t},\bar{\bm{w}}_{t})-\mathtt{MinW}(\hat{M}_{*},\underline{\bm{w}}_{t})\leq\varepsilon,$

which contradicts the stop condition. ∎

##  Appendix C Lower Bounds for the Fixed-Confidence Setting

In this section, we present the proof of lower bound for the exact fixed-
confidence CPE-B problem. Then, we also provide a lower bound for the PAC
fixed-confidence CPE-B problem and give its proof.

First, we prove the lower bound for the exact fixed-confidence CPE-B problem
(Theorem 3). Notice that, the sample complexity of algorithm $\mathtt{BLUCB}$
also matches the lower bound within a logarithmic factor if we replace
condition (iii) below with that each sub-optimal super arm only has a single
base arm.

###### Proof.

Consider an instance $\mathcal{I}$ of the fixed-confidence CPE-B problem such
that: (i) the reward distribution of each base arm $e\in[n]$ is
$\mathcal{N}(w(e),R)$; (ii) both $M_{*}$ and the second best super arms are
unique, and the second best super arm has no overlapped base arm with $M_{*}$;
(iii) in each sub-optimal super arm, there is a single base arm with reward
below $\mathtt{MinW}(M_{*},\bm{w})$.

Fix an arbitrary $\delta$-correct algorithm $\mathbb{A}$. For an arbitrary
base arm $e\in M_{*}$, we construct an instance $\mathcal{I}^{\prime}$ by
changing its reward distribution to $\mathcal{N}(w^{\prime}(e),R)$ where
$w^{\prime}(e)=w(e)-2\Delta^{\textup{C}}_{e}$. Recall that
$M_{\textup{second}}=\operatornamewithlimits{argmax}_{M\neq
M_{*}}\mathtt{MinW}(M,\bm{w})$. For instance $\mathcal{I}^{\prime}$, from the
definition of $\Delta^{\textup{C}}_{e}$ (Definition 1),

$\displaystyle w^{\prime}(e)=$ $\displaystyle w(e)-2\Delta^{\textup{C}}_{e}$
$\displaystyle=$ $\displaystyle
w(e)-(w(e)-\mathtt{MinW}(M_{\textup{second}},\bm{w}))-\Delta^{\textup{C}}_{e}$
$\displaystyle=$
$\displaystyle\mathtt{MinW}(M_{\textup{second}},\bm{w})-\Delta^{\textup{C}}_{e}$
$\displaystyle<$ $\displaystyle\mathtt{MinW}(M_{\textup{second}},\bm{w})$

and
$\mathtt{MinW}(M_{*},\bm{w}^{\prime})=w^{\prime}(e)<\mathtt{MinW}(M_{\textup{second}},\bm{w})$.
Thus, $M_{\textup{second}}$ becomes the optimal super arm.

Let $T_{e}$ denote the number of samples drawn from base arm $e$ when
algorithm $\mathbb{A}$ runs on instance $\mathcal{I}$. Let
$d(x,y)=x\ln(x/y)+(1-x)\ln[(1-x)/(1-y)]$ denote the binary relative entropy
function. Define $\mathcal{H}$ as the event that algorithm $\mathbb{A}$
returns $M_{*}$. Since $\mathbb{A}$ is $\delta$-correct, we have
$\Pr\limits_{\mathbb{A},\mathcal{I}}[\mathcal{H}]\geq 1-\delta$ and
$\Pr\limits_{\mathbb{A},\mathcal{I}^{\prime}}[\mathcal{H}]\leq\delta$. Thus,
$d(\Pr\limits_{\mathbb{A},\mathcal{I}}[\mathcal{H}],\Pr\limits_{\mathbb{A},\mathcal{I}^{\prime}}[\mathcal{H}])\geq
d(1-\delta,\delta)$. Using Lemma 1 in [27], we can obtain

$\displaystyle\mathbb{E}[T_{e}]\textup{KL}(\mathcal{N}(w(e),R),\mathcal{N}(w^{\prime}(e),R))\geq
d(1-\delta,\delta),$

Since the reward distribution of each base arm is Gaussian distribution, we
have
$\textup{KL}(\mathcal{N}(w(e),R),\mathcal{N}(w(e^{\prime}),R))=\frac{1}{2R^{2}}(w(e)-w^{\prime}(e))^{2}=\frac{2}{R^{2}}(\Delta^{\textup{C}}_{e})^{2}$.
Since $\delta\in(0,0.1)$, $d(1-\delta,\delta)\geq 0.4\ln(1/\delta)$. Thus, we
have

$\displaystyle\frac{2}{R^{2}}(\Delta^{\textup{C}}_{e})^{2}\cdot\mathbb{E}[T_{e}]\geq
0.4\ln(\frac{1}{\delta}).$

Then,

$\displaystyle\mathbb{E}[T_{e}]\geq
0.2\frac{R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln(\frac{1}{\delta}).$

For an arbitrary base arm $e\notin M_{*},w(e)<\mathtt{MinW}(M_{*},\bm{w})$, we
can construct another instance $\mathcal{I}^{\prime}$ by changing its reward
distribution to $\mathcal{N}(w^{\prime}(e),R)$ where
$w^{\prime}(e)=w(e)+2\Delta^{\textup{C}}_{e}$. Let $M_{e}$ denote the sub-
optimal super arm that contains $e$.

For instance $\mathcal{I}^{\prime}$, from the definition of
$\Delta^{\textup{C}}_{e}$ (Definition 1),

$\displaystyle w^{\prime}(e)=$ $\displaystyle w(e)+2\Delta^{\textup{C}}_{e}$
$\displaystyle=$ $\displaystyle
w(e)+(\mathtt{MinW}(M_{*},\bm{w})-\mathtt{MinW}(M_{e}))+\Delta^{\textup{C}}_{e}$
$\displaystyle=$ $\displaystyle
w(e)+(\mathtt{MinW}(M_{*},\bm{w})-w(e))+\Delta^{\textup{C}}_{e}$
$\displaystyle=$
$\displaystyle\mathtt{MinW}(M_{*},\bm{w})+\Delta^{\textup{C}}_{e}$
$\displaystyle>$ $\displaystyle\mathtt{MinW}(M_{*},\bm{w}).$

Thus, $M_{e}$ become the optimal super arm. Similarly, using Lemma 1 in [27]
we can obtain

$\displaystyle\frac{2}{R^{2}}(\Delta^{\textup{C}}_{e})^{2}\cdot\mathbb{E}[T_{e}]\geq
0.4\ln(\frac{1}{\delta}).$

Then,

$\displaystyle\mathbb{E}[T_{e}]\geq
0.2\frac{R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln(\frac{1}{\delta}).$

Summing over all $e\in M_{*}$ and $e\notin
M_{*},w(e)<\mathtt{MinW}(M_{*},\bm{w})$, we can obtain that any
$\delta$-correct algorithm has sample complexity

$\Omega\left(\sum_{e\in M_{*}\cup
B}\frac{R^{2}}{(\Delta^{\textup{C}}_{e})^{2}}\ln\left(\frac{1}{\delta}\right)\right).$

∎

Next, we present the lower bound for the PAC fixed-confidence CPE-B problem,
where we can relax condition (ii) in the proof of the exact lower bound
(Theorem 3). To formally state our result, we first introduce the notion of
_$(\delta,\varepsilon)$ -correct algorithm_ as follows. For any confidence
parameter $\delta\in(0,1)$ and accuracy parameter $\varepsilon>0$, we call an
algorithm $\mathcal{A}$ a $(\delta,\varepsilon)$-correct algorithm if for the
fixed-confidence CPE-B in PAC learning, $\mathcal{A}$ returns a super arm
$M_{\textup{pac}}$ such that
$\mathtt{MinW}(M_{\textup{pac}},\bm{w})\geq\mathtt{MinW}(M_{*},\bm{w})-\varepsilon$
with probability at least $1-\delta$.

######  Theorem 9 (Fixed-confidence Lower Bound for PAC).

There exists a family of instances for the fixed-confidence CPE-B problem,
where for any $\delta\in(0,0.1)$, any $(\delta,\varepsilon)$-correct algorithm
has the expected sample complexity

$\Omega\Bigg{(}\sum_{e\in M_{*}\cup
B}\frac{R^{2}}{\max\\{(\Delta^{\textup{C}}_{e})^{2},\varepsilon^{2}\\}}\ln\left(\frac{1}{\delta}\right)\Bigg{)}.$

###### Proof.

Consider the instance $\mathcal{I}$ for the PAC fixed-confidence CPE-B
problem, where
$\varepsilon<\mathtt{MinW}(M_{*},\bm{w})-\mathtt{MinW}(M_{\textup{second}},\bm{w})$
(to guarantee that $M_{*}$ is unique) and (i) the reward distribution of each
base arm $e\in[n]$ is $\mathcal{N}(w(e),1)$; (ii) the PAC solution
$M_{\textup{pac}}$ is unique and the second best super arm has no overlapped
base arm with $M_{\textup{pac}}$; (iii) in each sub-optimal super arm, there
is a single base arm with reward below $\mathtt{MinW}(M_{*},\bm{w})$. Then,
following the proof procedure of Theorem 3, we can obtain Theorem 9. ∎

##  Appendix D CPE-B in the Fixed-Budget Setting

Algorithm 7 $\mathtt{AR\mbox{-}Oracle}$

1: Input: decision class $\mathcal{M}$, accepted base arm $a$, set of the
rejected base arms $R$ and weight vector $\bm{v}$.

2: Remove the base arms in $R$ from $\mathcal{M}$ and obtain a new decision
class $\mathcal{M}_{-R}$.

3: Sort the remaining base arms by descending rewards and denote them by
$e_{(1)},\dots,e_{(n-|R|)}$

4: for $e=e_{(1)},\dots,e_{(n-|R|)}$ do

5: Remove all base arms with the rewards lower than $w(e)$ from $\mathcal{M}$
and obtain a new decision class $\mathcal{M}_{-R,\geq w(e)}$

6: $M_{\textup{out}}\leftarrow\mathtt{ExistOracle}(\mathcal{M}_{-R,\geq
w(e)},a)$

7: if $M_{\textup{out}}\neq\perp$ then

8: return $M_{\textup{out}}$

9: end if

10: end for

In this section, we present the implementation details of
$\mathtt{AR\mbox{-}Oracle}$ and error probability proof for algorithm
$\mathtt{BSAR}$.

###  D.1 Implementation Details of $\mathtt{AR\mbox{-}Oracle}$

First, we discuss $\mathtt{AR\mbox{-}Oracle}$. Recall that
$\mathtt{AR\mbox{-}Oracle}\in\operatornamewithlimits{argmax}_{M\in\mathcal{M}(e,R)}\mathtt{MinW}(M,\bm{w})$,
where $\mathcal{M}(e,R)=\\{M\in\mathcal{M}:e\in M,R\cap M=\varnothing\\}$. If
$\mathcal{M}(e,R)=\varnothing$, $\mathtt{AR\mbox{-}Oracle}=\perp$. Algorithm 7
gives the algorithm pseudo-code of $\mathtt{AR\mbox{-}Oracle}$. As
$\mathtt{BottleneckSearch}$, $\mathtt{AR\mbox{-}Oracle}$ also uses the
existence oracle $\mathtt{ExistOracle}$ to find a feasible super arm that
contains some base arm from the given decision class if there exists, and
otherwise return $\perp$. We explain the procedure of
$\mathtt{AR\mbox{-}Oracle}$ as follows: we first remove all base arms in $R$
from the decision class $\mathcal{M}$ to disable the super arms that contain
the rejected base arms. Then, we enumerate the remaining base arms by
descending rewards. For each enumerated base arm $e$, we remove the base arms
with rewards lower than $w(e)$ and obtain a new decision class
$\mathcal{M}_{-R,\geq w(e)}$, and then use $\mathtt{ExistOracle}$ to find a
feasible super arm that contains the accepted base arm $a$ from
$\mathcal{M}_{-R,\geq w(e)}$. Once such a feasible super arm is found, the
procedure terminates and returns this super arm. Since the enumeration of base
arms is performed according to descending rewards and the computed decision
class only contains base arms no worse than the enumerated one,
$\mathtt{AR\mbox{-}Oracle}$ guarantees to return an optimal super arm from
$\mathcal{M}(e,R)$.

As for the computational efficiency, the time complexity of
$\mathtt{AR\mbox{-}Oracle}$ mainly depends on the step of finding a feasible
super arm containing some base arm $e$. Fortunately, this existence problem
can be solved in polynomial time for a wide family of decision classes. For
example, for $s$-$t$ paths, this problem can be reduced to the well-studied
$2$-vertex connectivity problem [20], which is polynomially tractable (see
Section E.1 for the proof of reduction). For maximum cardinality matchings, we
just need to remove $e$ and its two end vertices, and then find a feasible
maximum cardinality matching in the remaining graph; and for spanning trees,
we can just merge the vertices of $e$ and find a feasible spanning tree in the
remaining graph. All of the above cases can be solved efficiently.

###  D.2 Proof for Algorithm $\mathtt{BSAR}$

Below we present the proof of error probability for algorithm $\mathtt{BSAR}$.
To prove Theorem 4, we first introduce the lowing Lemmas 14-17.

######  Lemma 14.

For phase $t=1,\dots,n$, define events

$\mathcal{E}_{t}=\left\\{\forall i\in[n]\setminus(A_{t}\cup R_{t}),\
|\hat{w}_{t}(i)-w(i)|<\frac{\Delta^{\textup{B}}_{(n+1-t)}}{8}\right\\}.$

and $\mathcal{E}\triangleq\bigcap_{t=1}^{n}\mathcal{E}_{t}$. Then, we have

$\Pr\left[\mathcal{E}\right]\geq
1-2n^{2}\exp\left(-\frac{(T-n)}{128\tilde{\log}(n)R^{2}H^{B}}\right).$

###### Proof.

For any $t\in[n]$ and $e\in[n]\setminus(A_{t}\cup R_{t})$, according to the
Hoeffding’s inequality,

$\left\\{|\hat{w}_{t}(i)-w(i)|\geq\frac{\Delta^{\textup{B}}_{(n+1-t)}}{8}\right\\}\leq
2\exp\left(-\frac{\tilde{T}(\Delta^{\textup{B}}_{n-t+1})^{2}}{128R^{2}}\right).$

From the definition of $\tilde{T}$ and $H^{B}$, we have

$\displaystyle\Pr\left[|\hat{w}_{t}(i)-w(i)|\geq\frac{\Delta^{\textup{B}}_{(n+1-t)}}{8}\right]\leq$
$\displaystyle
2\exp\left(-\frac{\tilde{T}(\Delta^{\textup{B}}_{n-t+1})^{2}}{128R^{2}}\right)$
$\displaystyle\leq$ $\displaystyle
2\exp\left(-\frac{\frac{T-n}{\tilde{\log}(n)(n-t+1)}(\Delta^{\textup{B}}_{n-t+1})^{2}}{128R^{2}}\right)$
$\displaystyle=$ $\displaystyle
2\exp\left(-\frac{(T-n)}{128\tilde{\log}(n)R^{2}\frac{n-t+1}{(\Delta^{\textup{B}}_{n-t+1})^{2}}}\right)$
$\displaystyle\leq$ $\displaystyle
2\exp\left(-\frac{(T-n)}{128\tilde{\log}(n)R^{2}H^{B}}\right)$

By a union bound over $t\in[n]$ and $e\in[n]\setminus(A_{t}\cup R_{t})$, we
have

$\displaystyle\Pr[\mathcal{E}]\geq$ $\displaystyle
1-n^{2}\Pr\left[|\hat{w}_{t}(i)-w(i)|\geq\frac{\Delta^{\textup{B}}_{(n+1-t)}}{8}\right]$
$\displaystyle\geq$ $\displaystyle
1-2n^{2}\exp\left(-\frac{(T-n)}{128\tilde{\log}(n)R^{2}H^{B}}\right).$

∎

######  Lemma 15.

Fix any phase $t>0$. Assume that event $\mathcal{E}_{t}$ occurs and algorithm
$\mathtt{BSAR}$ does not make any mistake before phase $t$, i.e.,
$A_{t}\subseteq M_{*}$ and $R_{t}\cap M_{*}=\varnothing$. Then, for any
$e\in[n]\setminus(A_{t}\cup R_{t})$ s.t.
$\Delta^{\textup{B}}_{e}\geq\Delta^{\textup{B}}_{(n+1-t)}$, we have
$e\in(M_{*}\cap M_{t})\cup(\neg M_{*}\cap\neg M_{t})$.

###### Proof.

Suppose that $e\in(M_{*}\cap\neg M_{t})\cup(\neg M_{*}\cap M_{t})$.

Case (I). If $e\in M_{*},e\notin M_{t}$, then $M_{t}$ is a sub-optimal super
arm and
$\Delta^{\textup{B}}_{M_{*},M_{t}}\geq\Delta^{\textup{B}}_{e}\geq\Delta^{\textup{B}}_{(n+1-t)}$.
Then, we have

$\displaystyle\mathtt{MinW}(M_{*},\hat{\bm{w}}_{t})-\mathtt{MinW}(M_{t},\hat{\bm{w}}_{t})>$
$\displaystyle\mathtt{MinW}(M_{*},\bm{w})-\frac{1}{8}\Delta^{\textup{B}}_{(n+1-t)}-(\mathtt{MinW}(M_{t},\bm{w})+\frac{1}{8}\Delta^{\textup{B}}_{(n+1-t)})$
$\displaystyle=$
$\displaystyle\mathtt{MinW}(M_{*},\bm{w})-\mathtt{MinW}(M_{t},\bm{w})-\frac{1}{4}\Delta^{\textup{B}}_{(n+1-t)}$
$\displaystyle\geq$
$\displaystyle\Delta^{\textup{B}}_{e}-\frac{1}{4}\Delta^{\textup{B}}_{(n+1-t)}$
$\displaystyle\geq$ $\displaystyle\frac{3}{4}\Delta^{\textup{B}}_{(n+1-t)}$
$\displaystyle>$ $\displaystyle 0,$

which contradicts the definition of $M_{t}$.

Case (II). If $e\in M_{t},e\notin M_{*}$, then $M_{t}$ is a sub-optimal super
arm and
$\Delta^{\textup{B}}_{M_{*},M_{t}}\geq\Delta^{\textup{B}}_{e}\geq\Delta^{\textup{B}}_{(n+1-t)}$.
Then, we have

$\displaystyle\mathtt{MinW}(M_{*},\hat{\bm{w}}_{t})-\mathtt{MinW}(M_{t},\hat{\bm{w}}_{t})>$
$\displaystyle\mathtt{MinW}(M_{*},\bm{w})-\frac{1}{8}\Delta^{\textup{B}}_{(n+1-t)}-(\mathtt{MinW}(M_{t},\bm{w})+\frac{1}{8}\Delta^{\textup{B}}_{(n+1-t)})$
$\displaystyle=$
$\displaystyle\mathtt{MinW}(M_{*},\bm{w})-\mathtt{MinW}(M_{t},\bm{w})-\frac{1}{4}\Delta^{\textup{B}}_{(n+1-t)}$
$\displaystyle\geq$
$\displaystyle\Delta^{\textup{B}}_{e}-\frac{1}{4}\Delta^{\textup{B}}_{(n+1-t)}$
$\displaystyle\geq$ $\displaystyle\frac{3}{4}\Delta^{\textup{B}}_{(n+1-t)}$
$\displaystyle>$ $\displaystyle 0,$

which contradicts the definition of $M_{t}$.

Thus, the supposition does not hold and we obtain $e\in(M_{*}\cap
M_{t})\cup(\neg M_{*}\cap\neg M_{t})$. ∎

######  Lemma 16.

Fix any phase $t>0$. Assume that event $\mathcal{E}_{t}$ occurs and algorithm
$\mathtt{BSAR}$ does not make any mistake before phase $t$, i.e.,