Year: 2021

Abstract:
Pure exploration plays an important role in online learning. Existing work mainly focuses on the UCB approach that uses confidence bounds of all the arms to decide which one is optimal. However, the UCB approach faces some challenges when looking for the best arm set under some specific combinatorial structures. It uses the sum of upper confidence bounds within arm set S to judge whether S is optimal. This sum can be much larger than the exact upper confidence bound of S, since the empirical means of different arms in S are independent. Because of this, the UCB approach requires much higher complexity than necessary. To deal with this challenge, we explore the idea of Thompson Sampling (TS) that uses independent random samples instead of the upper confidence bounds to make decisions, and design the first TS-based algorithm framework TS-Verify for (combinatorial) pure exploration. In TS-Verify, the sum of independent random samples within arm set S will not exceed the exact upper confidence bound of S with high probability. Hence it solves the above challange, and behaves better than existing UCB-based algorithms under the general combinatorial pure exploration setting. As for pure exploration of classic multi-armed bandit, we show that TS-Verify achieves an asymptotically optimal complexity upper bound.

heading: 1 INTRODUCTION
text: Pure exploration is an important task in online learning, and it tries to find out the target arm as fast as possible. In pure exploration of classic multi-armed bandit (MAB) (Audibert et al., 2010), there are totally m arms, and each arm i is associated with a probability distribution Di with mean µi. Once arm i is pulled, it returns an observation ri, which is drawn independently from distributionDi by the environment. At each time step t, the learning policy π either chooses an arm i(t) to pull, or chooses to output an arm a(t). The goal of the learning policy is to pull arms properly, such that with an error probability at most δ, its output arm a(t) is the optimal arm (i.e., a(t) = arg maxi∈[m] µi) with complexity (the total number of observations) as low as possible.
Pure exploration is widely adopted in real applications. For example, in the selling procedure of cosmetics, there is always a testing phase before the commercialization phase (Audibert et al., 2010). The goal of the testing phase is to help to maximize the cumulative reward collected in the commercialization phase. Therefore, instead of regret minimization (Berry & Fristedt, 1985; Auer et al., 2002), the testing phase only needs to do exploration (e.g., to investigate which product is the most popular one), and wants to find out the target with both correctness guarantee and low cost. In real world, sometimes the system focuses on the best action under a specific combinatorial structure, instead of the best single arm (Chen et al., 2014). For example, a network routing system needs to search for the path with minimum delay between the source and the destination. Since there can be an exponential number of paths, the cost of exploring them separately is unacceptable. Therefore, people choose to find out the best path by exploring the single edges, and this is a pure exploration problem instance in combinatorial multi-armed bandits (CMAB). In this setting, we still pull single arms (base arms) at each time step, and there is a super arm set I ⊆ 2[m]. The expected reward of a super arm S ∈ I is ∑ i∈S µi, i.e., the sum of the expected rewards of its contained base arms. And the goal of the player is to find out the optimal super arm with an error probability at most δ.
Most of the existing solutions for pure exploration follow the UCB approach (Audibert et al., 2010; Kalyanakrishnan et al., 2012; Chen et al., 2014; Kaufmann & Kalyanakrishnan, 2013). They com-
pute the confidence bounds for all the arms, and claim that one arm is optimal only if its lower confidence bound is larger than the upper confidence bounds of all the other arms. Though this approach is asymptotically optimal in pure exploration of classic MAB problems (Kalyanakrishnan et al., 2012; Kaufmann & Kalyanakrishnan, 2013), it faces some challenges in the CMAB case (Chen et al., 2014). In the UCB approach, for a super arm S, the algorithm usually uses the sum of upper confidence bounds of all its contained base arms as its upper confidence bound. This means that the gap between the empirical mean of super arm S and the used upper confidence bound of S is about Õ( ∑ i∈S √
1/Ni) (here Ni is the number of observations on base arm i). However, since the observations of different base arms are independent, the standard deviation of the empirical mean of super arm S is Õ( √∑ i∈S 1/Ni), which is much smaller. This means that the used upper confidence bound is much larger than the real one. Combes et al. (2015) deal with this problem by computing the upper confidence bounds for all the super arms independently, which leads to an exponential time cost and can be hard to implement. In fact, existing efficient UCB-based solutions either suffer from a higher complexity bound (Chen et al., 2014; Gabillon et al., 2016), or need further assumptions on the combinatorial structure to achieve an optimal complexity bound (Chen et al., 2017).
Then a natural solution to deal with this challenge is to use random sample of arm i (with mean to be its empirical mean and standard deviation to be Õ( √ 1/Ni)) instead of its upper confidence bound to judge whether a super arm is optimal. If we let the random samples of different base arms be independent, then the gap between the empirical mean of super arm S and the sum of random samples within S is Õ( √∑ i∈S 1/Ni), which has the same order as the gap between the empirical mean of super arm S and its real mean. Therefore, using independent random samples can behave better than using confidence bounds, and this is the key idea of Thompson Sampling (TS) (Thompson, 1933; Kaufmann et al., 2012; Agrawal & Goyal, 2013). In fact, many prior works show that TS-based algorithms have smaller cumulative regret than UCB-based algorithms in regret minimization of CMAB model (Wang & Chen, 2018; Perrault et al., 2020). However, existing researches only study using TS approaches under the Bayesian setting of pure exploration (Li et al., 2021), and there still lack results of adapting TS to the frequentist setting.
In this paper, we attempt to fill up this gap, and study using TS in pure exploration under the frequentist setting for both MAB and CMAB instances by adapting the idea of TS in the Bayesian setting (Li et al., 2021). We emphasize that it is non-trivial to design (and analyze) a TS-based algorithm under the frequentist setting. The first challenge is that there is a lot more uncertainty in the random samples than the confidence bounds. In UCB-based algorithms, the upper confidence bound of the optimal arm is larger than its expected reward with high probability. Thus, the arm with the largest upper confidence bound is either an insufficiently learned sub-optimal arm (i.e., the number of its observations is not enough to make sure that it is a sub-optimal arm) or the optimal arm, which means that the number of pulls on sufficiently learned sub-optimal arms is limited. However, for TS-based algorithms, there is always a constant probability that the random sample of the optimal arm is smaller than its expected reward. In this case, the arm with the largest random sample may be a sufficiently learned sub-optimal arm. Therefore, if we still choose to pull the arm with the largest random sample (similar as UCB-based policies that pull the arm with the largest upper confidence bound), then the mechanism of the TS-based policy should be designed carefully to make sure that we can still obtain an upper bound for the number of pulls on sufficiently learned sub-optimal arms.
Another challenge is that TS is an algorithm that follows the Bayesian framework and loses many good properties in the frequentist setting. In the Bayesian setting, at each time step t, the parameters of the game follow a posterior distribution Pt, and the random samples are drawn from Pt independently as well. Therefore, using the random samples to output the optimal arm can explicitly ensure the correctness of the TS-based algorithm. However, in the frequentist setting, the parameters of the game are fixed but unknown, and they have no such correlations with the random samples. Because of this, if we still use the random samples to output the optimal arm, then the distributions of random samples in the TS-based algorithm need to be chosen carefully to make sure that it still has correctness guarantee in the frequentist setting.
Besides, the analysis of TS-based algorithms in pure exploration is also very different with regret minimization. In regret minimization, at each time step, we only need to draw one sample for each base arm. However, in pure exploration, one set of samples is not enough at each time step, since the algorithm needs to i) check whether there is an arm that is the optimal one with high probability; ii) look for an arm that needs exploration, and none of these two goals can be achieved by only one
set of samples. Therefore, we must draw several sets of samples to make decisions, and this may fail existing analysis in regret minimization. For example, the analysis in (Agrawal & Goyal, 2013) obtains a lower bound for the probability that the optimal arm has the highest sample in one sample set. However, when we use several sets of samples to make decisions, we can notice the optimal arm only if it has the highest sample in most of these sample sets, which is much harder than it has the highest sample in only one sample set when its observations are bad (e.g., its empirical mean equals to its real expected reward minus the confidence radius).
In this paper, we solve the above challenges, and design a TS-based verification framework TSVerify for (combinatorial) pure exploration under the frequentist setting. TS-Verify takes a target (super) arm as input, and aims to verify that this target (super) arm is optimal with error constraint δ. At each time step t, TS-Verify first draws independent random samples θki (t) for all the (base) arms i ∈ [m] and k = 1, 2, · · · ,M (i.e., totallyM independent samples for each arm). Then it tries to find out the M best (super) arms under sample sets θk(t) = [θk1 (t), · · · , θkm(t)] for k = 1, 2, · · · ,M . If in most of these sample sets, the target (super) arm is the best one, then the algorithm will output that the target (super) arm is indeed optimal. Otherwise, the algorithm will choose to pull a (base) arm from the exploration set, which contains the target (super) arm and all the (super) arms that have been optimal in at least one sample set at this time step.
In the rest of this paper, we mainly focus on the behaviour (i.e., correctness guarantee and complexity upper bound) of this verification algorithm, which is almost the same as a complete pure exploration algorithm after we adapt the explore-then-verify framework (Karnin, 2016; Chen et al., 2017). In the general CMAB setting, we show that TS-Verify is near optimal and behaves better than existing UCB-based algorithms (Chen et al., 2014). The optimal algorithm (Chen et al., 2017) requires the combinatorial structure to satisfy some specific properties, which is less general than our results. As for the MAB case, we show that TS-Verify is asymptotically optimal, i.e., it has a comparable complexity as existing optimal algorithms (Kalyanakrishnan et al., 2012; Kaufmann & Kalyanakrishnan, 2013) when δ → 0. All these results indicate that out algorithm framework is efficient and general in dealing with pure exploration problems. To the best of our knowledge, this is the first result of using TS-based algorithms in pure exploration under the frequentist setting.

heading: 2 RELATED WORKS
text: Pure exploration of the classic MAB model is first proposed by Audibert et al. (2010). After that, people have designed lots of learning policies for this problem. The two most representative algorithms are successive-elimination (Even-Dar et al., 2006; Audibert et al., 2010; Kaufmann & Kalyanakrishnan, 2013) and LUCB (Kalyanakrishnan et al., 2012; Kaufmann & Kalyanakrishnan, 2013). Both of them adapt the idea of UCB (Auer et al., 2002) and achieve an asymptotically optimal complexity upper bound (i.e., it matches with the complexity lower bound proposed by Kalyanakrishnan et al. (2012)). Compared to these results, our TS-Verify policy uses a totally different approach, and can achieve an asymptotically optimal complexity upper bound as well.
Combinatorial pure exploration is first studied by Chen et al. (2014). They propose CLUCB, an LUCB-based algorithm that is efficient as long as there is an offline oracle to output the best super arm under any given parameter set. Chen et al. (2017) then design an asymptotically optimal algorithm for this problem. However, they require the combinatorial structure to follow some specific constraints so that they can apply a more powerful offline oracle. Recently, based on the game approach, Jourdan et al. (2021) provide another optimal learning policy for pure exploration in CMAB. But their algorithm still requires the existence of a more powerful offline oracle. Compared with these UCB-based algorithms, our TS-based algorithm achieves a better complexity bound than CLUCB (Chen et al., 2014) in the most general setting. However, since we do not assume the existence of a more powerful offline oracle, we cannot achieve the optimal complexity upper bound.

heading: 3 PRELIMINARIES

heading: 3.1 PURE EXPLORATION IN MULTI-ARMED BANDIT
text: A pure exploration problem instance of MAB is a tuple ([m],D, δ). Here [m] = {1, 2, · · · ,m} is the set of arms, D = {D1, D2, · · · , Dm} are the corresponding reward distributions of the arms,
and δ is the error constraint. In this paper, we assume that all the distributions Di’s are supported on [0, 1]. Let µi , EX∼Di [X] denote the expected reward of arm i, and a∗ = arg maxi∈[m] µi is the optimal arm with the largest expected reward. Similar with many existing works (e.g., (Audibert et al., 2010)), we also assume that the optimal arm is unique. At each time step t, the learning policy π can either pull an arm i(t) ∈ [m], or output an arm a(t) ∈ [m]. If it chooses to pull arm i(t), then it will receive an observation ri(t)(t), which is drawn independently from distribution Di(t). The goal of the learning policy is to make sure that with probability at least 1− δ, its output a(t) = a∗. Under this constraint, it aims to minimize the complexity Zπ , ∑m i=1Ni(T
π), where Tπ denotes the time step t that policy π chooses to output a(t), and Ni(t) denotes the number of observations on arm i until time step t.
Let ∆i,m , µa∗ − µi denote the expected reward gap between the optimal arm a∗ and any other arm i 6= a∗. For the optimal arm a∗, its ∆a∗,m is defined as µa∗ − maxi 6=a∗ µi. We also define Hm , ∑ i∈[m]
1 ∆2i,m , and existing works (Kalyanakrishnan et al., 2012) show that the complexity
lower bound of any pure exploration algorithm is Ω(Hm log 1δ ).

heading: 3.2 PURE EXPLORATION IN COMBINATORIAL MULTI-ARMED BANDIT
text: A pure exploration problem instance of CMAB is an extension of the MAB case. The arms i ∈ [m] are called base arms, and there is also a super arm set I ⊆ 2[m]. For each super arm S ∈ I, its expected reward is ∑ i∈S µi. Let S ∗ = arg maxS∈I ∑ i∈S µi denote the optimal super arm with the largest expected reward, and we assume that the optimal super arm is unique (as in (Chen et al., 2014)). At each time step t, the learning policy π can either pull a base arm i(t) ∈ [m], or output a super arm S(t) ∈ I. The goal of the learning policy is to make sure that with probability at least 1− δ, its output S(t) = S∗. Under this constraint, it also wants to minimize its complexity Zπ . As assumed in many existing works (Chen et al., 2013; 2014; Wang & Chen, 2018), we also assume that there exists an offline Oracle, which takes a set of parameters θ = [θ1, · · · , θm] as input, and outputs the best super arm under this parameter set, i.e., Oracle(θ) = arg maxS∈I ∑ i∈S θi.
In this paper, for i /∈ S∗, we use ∆i,c , ∑ j∈S∗ µj −maxS∈I:i∈S ∑ j∈S µj to denote the expected reward gap between the optimal super arm S∗ and the best super arm that contains i. As for i ∈ S∗, its ∆i,c is defined as ∆i,c , ∑ j∈S∗ µj − maxS∈I:i/∈S ∑ j∈S µj , i.e., the expected reward gap between S∗ and the best super arm that does not contain i. We also define width , maxS 6=S∗(|S \ S∗|+ |S∗ \ S|), and let H1,c , width ∑ i∈[m]
1 ∆2i,c
, H2,c , width2 ∑ i∈[m]
1 ∆2i,c .
Chen et al. (2017) prove that the complexity lower bound is Ω(H0,c log 1δ ), whereH0,c is the solution of the following optimization problem (here ∆S,c = ∑ i∈S∗ µi − ∑ i∈S µi):
min ∑ i∈[m] Nm
s.t. ∑
i∈S\S∗
1
Ni + ∑ i∈S∗\S 1 Ni ≤ ∆2S,c, ∀S ∈ I, S 6= S∗
The following result shows the relationships between H0,c, H1,c and H2,c. Proposition 1. For any combinatorial pure exploration instance, H0,c ≤ H1,c ≤ H2,c.
Proof. Since width ≥ 1, we have that H1,c ≤ H2,c. As for the first inequality, note that ∀i ∈ [m], Ni =
width ∆2i,c is a feasible solution of the optimization problem. Hence we have thatH0,c ≤ H1,c.

heading: 3.3 GENERAL EXPLORE-THEN-VERIFY FRAMEWORK
text: Due to space limit, the detailed descriptions of the general explore-then-verify framework (Chen et al., 2017) is deferred to Appendix A. Fact 1. (Lemma 4.8 in (Chen et al., 2017)) If there exist i) a complete pure exploration algorithm that outputs the optimal arm with probability at least 1− δ and complexity at most O(HE log 1δ +CE);
Algorithm 1 TS-Verify 1: Input: Error constraint δ, target ã (or S̃), q ∈ [δ, 0.1), t = m, Ni = 0, Ri = 0 for all i ∈ [m]. 2: Pull each arm once, update their number of pulls Ni’s and the sum of their observations Ri’s. 3: while true do 4: for k = 1, 2, · · · ,M(δ, q, t) do 5: For each arm i, draw sample θki (t) independently from distribution N (RiNi , C(δ,q,t) Ni
). 6: ak(t) (Sk(t)) is the best (super) arm under parameter set [θk1 (t), · · · , θkm(t)]. 7: end for 8: p̂ã(t) = 1 M(δ,q,t) ∑M(δ,q,t) k=1 I[ak(t) = ã] (p̂S̃(t) = 1 M(δ,q,t) ∑M(δ,q,t) k=1 I[Sk(t) = S̃]).
9: if p̂ã(t) > 1− q (p̂S̃(t) > 1− q) then 10: Return: Arm ã (super arm S̃) is indeed the optimal one. 11: else 12: Arbitrarily choose a′ ∈ {ak(t)}M(δ,q,t)k=1 such that a′ 6= ã (arbitrarily choose S′ ∈ {Sk(t)}M(δ,q,t)k=1 such that S′ 6= S̃). 13: Pull arm i(t) from the exploration set {a′, ã} ({S′, S̃}), update its number of pulls Ni(t) and the sum of its observations Ri(t). 14: t← t+ 1. 15: end if 16: end while
and ii) a verification algorithm such that with probability at least 1 − δ, it outputs that its input is optimal with complexity at most O(HV log 1δ + CV ) if its input is the optimal arm and does not terminate otherwise. Then we can construct a complete pure exploration algorithm based on the general explore-then-verify framework. It works correctly with probability at least 1 − δ, and its expected complexity is upper bounded by O(HE log 1δ0 +HV log 1 δ +CE +CV ) for fixed δ0 = 0.1.
According to Fact 1, in the rest of this paper, we focus on designing verification algorithms based on the TS approach. As long as we have a verification algorithm with error probability δ and complexity upper bound O(HV log 1δ + CV ), using any efficient complete pure exploration algorithm (e.g., LUCB (Kalyanakrishnan et al., 2012) or CLUCB (Chen et al., 2014)) in the explore-then-verify framework can make sure that the expected complexity of the constructed pure exploration algorithm is upper bounded by O(HE log 1δ0 + HV log 1 δ + CE + CV ), which is asymptotically the same as the complexity upper bound O(HV log 1δ ) (since all the other terms do not depend on δ).

heading: 4 THOMPSON SAMPLING-BASED VERIFICATION

heading: 4.1 GENERAL VERIFICATION FRAMEWORK FOR PURE EXPLORATION
text: Our Thompson Sampling-based verification framework (TS-Verify) is described in Algorithm 1. We use Ni to denote the number of observations on arm i, Ri to denote the sum of all the observations from arm i, and Ni(t), Ri(t) to denote the value of Ni, Ri at the beginning of time step t.
At each time step t, for any i ∈ [m], TS-Verify first draws M(δ, q, t) , log(12t 2/δ)
q2 random samples
{θki (t)} M(δ,q,t) k=1 independently from a Gaussian distribution with mean µ̂i(t) , Ri(t) Ni(t) (i.e., the empirical mean of arm i) and variance C(δ,q,t)Ni(t) (i.e., inversely proportional toNi(t)), where C(δ, q, t) is a term depending on the settings and will be explained in detail later. Then TS-Verify checks which (super) arm is optimal in the k-th sample set [θk1 (t), · · · , θkm(t)] for all k. In the MAB case, it can directly check which arm’s sample is the largest one; in the CMAB case, it can use Oracle to obtain the best super arm under the k-th sample set. After that, TS-Verify checks whether the number of sample sets in which the target arm ã (or target super arm S̃) is the optimal one is large enough. If the number of such sample sets is larger than (1 − q)M(δ, q, t), then TS-Verify outputs that the target (super) arm is optimal. Otherwise it knows that either the target (super) arm is not optimal, or some (super) arms are not sufficiently learned (i.e., they do not have enough observations). In this case, TS-Verify constructs an exploration set {a′, ã} (or {S′, S̃}), where a′ 6= ã is an arbitrary arm
(or S′ 6= S̃ is an arbitrary super arm) that has been optimal in at least one sample set, and uses some choosing rules (which will be explained in detail later) to pull an arm i(t) in the exploration set.
The reason that we use Gaussian random samples in TS-Verify is because it can simplify the analysis significantly (since the sum of independent Gaussian random variables is still a Gaussian one). We believe that using other kinds of random samples (e.g., uniform distributions in the confidence intervals) will have a similar behaviour.

heading: 4.2 TS-VERIFY FOR MULTI-ARMED BANDIT
text: We first apply TS-Verify to the classic MAB case. In the following, we define Φ(x, µ, σ2) , PrX∼N (µ,σ2)[X ≥ x], and φ(x) satisfies that Φ(φ(x), 0, 1) = x for all x ∈ (0, 1).
In the MAB case, we set C(δ, q, t) = 4 log(12mt 2/δ) φ2(3q) , and for the exploration set {a ′, ã}, we will choose to pull the arm with a smaller number of observations. Theorem 1. For q ∈ [δ, 0.1), with probability at least 1 − δ, we have that: i) if ã = a∗, TSVerify will return that arm ã is the optimal arm with complexity upper bounded by O(Hm(log 1δ + log(mHm)) log 1δ log 1q +Hm log2(mHm) log 1q ); ii) if ã 6= a∗, TS-Verify will not stop. Specifically, if we choose q = δ, then the complexity upper bound is O(Hm log 1δ +Hm log 2(mHm)). Remark 1. The value q in TS-Verify is used to control the number of times that we draw random samples at each time step. Note that M(δ, q, t) = log(12t
2/δ) q2 . Hence when q becomes larger, we
need fewer samples, but the complexity bound becomes worse. Here is a trade-off between the algorithm’s complexity and the number of random samples it needs to draw. Our analysis shows that using q = δ 1 β for some constant β ≥ 1 can make sure that the complexity upper bound remains the same order, and reduce the number of random samples significantly.
Proof. Firstly, we define the following three events:
E0,m = { ∀t, i, |µ̂i(t)− µi| ≤ √ log(12mt2/δ)
Ni(t)
} ;
E1,m = { ∀i, t, k, |θki (t)− µ̂i(t)| ≤ √ C(δ, q, t) log(12mt2M(δ, q, t)/δ)
Ni(t)
} ;
E2,m = { ∀t, |p̂ã(t)− pã(t)| ≤ √ log(12t2/δ)
M(δ, q, t)
} .
Here pã(t) denotes the probability that arm ã’s sample is the largest one in the k-th sample set of time step t (i.e., Pr[θkã(t) = maxi∈[m] θ k i (t)|{Ni(t), Ri(t)}mi=1], also note that it is not conditioned on E1,m). We can see that p̂ã(t) is its empirical mean in the M(δ, q, t) sample sets.
By Chernoff-Hoeffding inequality, ∀t, i, Pr[|µ̂i(t) − µi| > √
log(12mt2/δ) Ni(t) ] ≤ δ6mt2 , therefore Pr[¬E0,m] ≤ ∑ i,t δ 6mt2 ≤ δ 3 . Similarly, one can also prove that Pr[¬E1,m] ≤ δ 3 (note that there are M(δ, q, t) sample sets at time step t, and the variance of θki (t) is C(δ,q,t) Ni(t) ) and Pr[¬E2,m] ≤ δ3 .
Then we only need to prove that under event E0,m ∧ E1,m ∧ E2,m, the two properties in Theorem 1 hold. To simplify the notations, in this proof, we denote M(t) = M(δ, q, t), C(t) = C(δ, q, t), L1(t) = log(12mt 2/δ) and L2(t) = log(12mt2M(δ, q, t)/δ).
Consider the two cases in Theorem 1:
i) When ã = a∗: in this case, we claim that any arm i cannot be pulled if Ni(t) ≥ 16C(t)L2(t)∆2i,m , and we will prove this claim by contradiction.
If we choose to pull arm i 6= a∗ and Ni(t) ≥ 16C(t)L2(t)∆2i,m , then from the description of TS-Verify, there exists k such that θki (t) ≥ θka∗(t) and Ni(t) ≤ Na∗(t). However, we also have that (in the rest
of this paragraph, A(t) = 1Ni(t) and B(t) = 1 Na∗ (t) ) θki (t) ≤ µ̂i(t) + √ A(t)C(t)L2(t) (1)
≤ µi + √ A(t)L1(t) + √ A(t)C(t)L2(t) (2)
< µi + ∆i,m
2 , (3)
where Ineq. (1) is because of E1,m; Ineq. (2) is because of E0,m; Ineq. (3) is because that Ni(t) ≥ 16C(t)L2(t)
∆2i,m and therefore
√ A(t)C(t)L2(t) ≤ ∆i,m4 and √ A(t)L1(t) < ∆i,m 4 (since q ≥ δ, we
must have that C(t)L2(t) > L1(t)). As for the arm a∗, we have that
θka∗(t) ≥ µ̂a∗(t)− √ B(t)C(t)L2(t) ≥ µa∗ − √ B(t)L1(t)− √ B(t)C(t)L2(t) > µi +
∆i,m 2 ,
where the last inequality is because that Na∗(t) ≥ Ni(t) ≥ 16C(t)L2(t)∆2i,m . This contradicts with θki (t) ≥ θka∗(t).
Similarly, if Na∗(t) ≥ 16C(t)L2(t)∆2 a∗,m , then arm a∗ cannot be pulled as well. This means that the complexity Z satisfies
Z ≤ ∑ i∈[m] 16C(Z)L2(Z) ∆2i,m = 16HmC(Z)L2(Z).
For q ≤ 0.1, we have that φ2(3q) = Θ(log 13q ). Then with C(Z) = 4 log(12mZ2/δ) φ2(3q) , L2(Z) = log(12mZ2M(Z)/δ) and M(Z) = log(12Z 2/δ)
q2 , we have that (note that we require q ≥ δ)
Z ≤ Θ ( Hm
log(mZ) + log 1δ log 1q
( log(mZ) + log 1
δ
)) .
Therefore, after some basic calculations, we know that
Z = O ( Hm log(mHm) + log 1 δ
log 1q
( log(mHm) + log 1
δ
)) .
ii) When ã 6= a∗: in this case, we consider the probability that arm a∗ has a larger sample than ã, i.e., Pr[θka∗(t) ≥ θkã(t)|{Ni(t), Ri(t)}mi=1], and let A(t) = 1Nã(t) and B(t) = 1 Na∗ (t) . Note that µa∗ ≥ µã, therefore, under event E0,m, we must have that µ̂a∗(t) − µ̂ã(t) ≥ (µa∗ −√ B(t)L1(t)) − (µã + √ A(t)L1(t)) ≥ − √ A(t)L1(t) − √ B(t)L1(t). Since θka∗(t) − θkã(t) is a Gaussian random variable with mean µ̂a∗(t) − µ̂ã(t) and variance A(t)C(t) + B(t)C(t), we have that (recall that Φ(x, µ, σ2) = PrX∼N (µ,σ2)[X ≥ x]):
Pr[θka∗(t) ≥ θkã(t)] = Φ(0, µ̂a∗(t)− µ̂ã(t), A(t)C(t) +B(t)C(t)) ≥ Φ(0,− √ A(t)L1(t)− √ B(t)L1(t), A(t)C(t) +B(t)C(t))
= Φ( √ A(t)L1(t) + √ B(t)L1(t), 0, A(t)C(t) +B(t)C(t))
= Φ
(√ L1(t) C(t) · √ A(t) + √ B(t)√ A(t) +B(t) , 0, 1 )
≥ Φ ( 2 √ L1(t)
C(t) , 0, 1 ) = 3q, (4)
where Eq. (4) is because that C(t) = 4L1(t)φ2(3q) and Φ(φ(3q), 0, 1) = 3q (by definition of φ). This implies that Pr[θkã(t) = maxi∈[m] θ k i (t)|{Ni(t), Ri(t)}mi=1] ≤ 1− 3q.
Note that pã(t) only depends on E0,m but does not depend on E1,m and E2,m. Therefore under event E0,m∧E1,m∧E2,m, we still have that pã(t) ≤ 1−3q. Also recall that we setM(δ, q, t) = log(12t 2/δ) q2 ,
which implies √
log(12t2/δ) M(δ,q,t) = q. Hence, by event E2,m, we know that p̂ã(t) ≤ pã(t) + q ≤
1− 3q + q < 1− q, i.e., TS-Verify will not stop in this case.
Theorem 1 shows that the complexity upper bound of TS-Verify (as well as the complete pure exploration algorithm constructed by applying the explore-then-verify framework) is asymptotically optimal in the MAB case, i.e., it matches the complexity lower bound Ω(Hm log 1δ ) (Kalyanakrishnan et al., 2012) when δ → 0. To the best of our knowledge, this is the first analysis of using a TS-based algorithm to deal with pure exploration problems under the frequentist setting.
Remark 2. Focusing on verification is the mechanism we use to bound the number of pulls on sufficiently learned arms (i.e., arm i with Ni(t) ≥ 16C(t)L2(t)/∆2i,m). For a complete pure exploration algorithm, the optimal arm is unknown at the beginning. If it is insufficiently learned, then the variance of its random sample is large, and we cannot ensure that it is optimal in any of the sample sets. In this case, the exploration set may only contain sufficiently learned arms. However, in a verification algorithm, we only focus on the complexity when the target arm is optimal, and we can always put the target arm in the exploration set. This makes sure that there is at least one insufficiently learned arm in the exploration set, i.e., if the target arm is sufficiently learned, then the other arm that has at least one larger random sample than the target arm must be insufficiently learned. Therefore, the number of pulls on sufficiently learned arms in TS-Verify is limited.
Remark 3. The variance term C(δ, q, t) in TS-Verify is chosen carefully to both ensure the correctness and reduce the complexity upper bound. Since C(δ, q, t) is not too low, for any sub-optimal target ã, there is always some probability that the optimal arm a∗ has larger sample than ã, even if the observations of a∗ are bad (e.g., its empirical mean equals to its real expected reward minus the confidence radius). This ensures the correctness of TS-Verify. On the other hand, since C(δ, q, t) is not too high, the required number of observations on sub-optimal arm i is still O( 1
∆2i log 1δ ).

heading: 4.3 TS-VERIFY FOR COMBINATORIAL MULTI-ARMED BANDIT
text: Then we come to the CMAB case, and we choose C(δ, q, t) = 4 log(24|I|t 2/δ)
φ2(3q) . For the exploration
set {S′, S̃}, we will choose to pull the arm i ∈ (S′ \ S̃) ∪ (S̃ \ S′) with the smallest number of observations Ni(t).
Theorem 2. For q ∈ [δ, 0.1), with probability at least 1−δ, we have that: i) if S̃ = S∗, TS-Verify will return that super arm S̃ is the optimal super arm with complexity upper bounded byO(H1,c(log 1δ + log(|I|H1,c)) log 1δ log 1q + H1,c log2(|I|H1,c) log 1q ); ii) if S̃ 6= S∗, TS-Verify will not stop. Specifically, if we choose q = δ, then the complexity upper bound is O(H1,c log 1δ +H1,c log 2(|I|H1,c)).
Now we provide a proof sketch for Theorem 2, while deferring its complete proof to Appendix B.
Proof (sketch). In the CMAB case, we first define J = {S∗ \ S, S \ S∗ : S ∈ I} as the exchange sets of any super arm S ∈ I and the optimal super arm S∗. Then similar as the proof of Theorem 1, we can also define three events E0,c, E1,c, E2,c.
E0,c = ∀t, U ∈ J , |∑ i∈U (µ̂i(t)− µi)| ≤ √∑ i∈U 1 Ni(t) log(24|I|t2/δ)  ; E1,c =
∀t, k, U ∈ J , |∑ i∈U (θki (t)− µ̂i(t))| ≤ √ C(δ, q, t) ∑ i∈U 1 Ni(t) log(24|I|t2M(δ, q, t)/δ)  ; E2,c = { ∀t, |p̂S̃(t)− pS̃(t)| ≤ √ log(12t2/δ)
M(δ, q, t)
} .
Here pS̃(t) denotes the probability that at time step t, S̃ is the best super arm under the k-th sample set (i.e., Pr[ ∑ i∈S̃ θ k i (t) = maxS∈I ∑ i∈S θ k i (t)|{Ni(t), Ri(t)}mi=1]). We can see that p̂S̃(t) is its empirical mean in the M(δ, q, t) sample sets.
Similarly, we also have that Pr[E0,c ∧ E1,c ∧ E2,c] ≥ 1− δ, and therefore it is sufficient to prove that under event E0,c∧E1,c∧E2,c, the two properties in Theorem 2 hold. In this proof, we denoteM(t) = M(δ, q, t), C(t) = C(δ, q, t), L1(t) = log(24|I|t2/δ) and L2(t) = log(24|I|t2M(δ, q, t)/δ). Consider the two cases in Theorem 2:
i) When S̃ = S∗: in this case, we claim that any arm i cannot be pulled ifNi(t) ≥ 16 widthC(t)L2(t)∆2i,c , and we will also prove this claim by contradiction.
Here we only consider the case that i /∈ S∗, the case that i ∈ S∗ is similar. For any arm i /∈ S∗, if it is pulled at time step t and Ni(t) ≥ 16 widthC(t)L2(t)∆2i,c , then from the description of TS-Verify, there exists S 6= S∗ and i ∈ S \S∗ such that for some k, ∑ j∈S θ k j (t) ≥ ∑ j∈S∗ θ k j (t) (which is the same
as ∑ j∈S\S∗ θ k j (t) ≥ ∑ j∈S∗\S θ k j (t)), and Nj(t) ≥ Ni(t) for all j ∈ (S∗ \ S) ∪ (S \ S∗). Now let
A(t) = ∑ j∈S\S∗ 1 Nj(t) and B(t) = ∑ j∈S∗\S 1 Nj(t)
, then the proof is almost the same as Theorem 1 (note that there are at most width arms in S \ S∗ or S∗ \ S). Therefore, we know that the complexity Z satisfies
Z ≤ ∑ i∈[m] 16 widthC(Z)L2(Z) ∆2i,c = 16H1,cC(Z)L2(Z),
which means that Z = O(H1,c(log 1δ + log(|I|H1,c)) log 1δ log 1q +H1,c log2(|I|H1,c) log 1q ).
ii) When S̃ 6= S∗: in this case, we consider the probability that ∑ i∈S∗\S̃ θ k i (t) ≥ ∑ i∈S̃\S∗ θ k i (t)
(i.e., super arm S∗ is better than S̃ in the k-th sample set). Here we denote A(t) = ∑ i∈S̃\S∗ 1 Ni(t)
, B(t) = ∑ i∈S∗\S̃ 1 Ni(t) , and then the proof becomes almost the same as Theorem 1.
Compared to existing works, the complexity upper bound of TS-Verify (as well as the complete pure exploration algorithm constructed by applying the explore-then-verify framework) is width lower than the CLUCB policy in (Chen et al., 2014). This is because that we use the Thompson Sampling approach, i.e., for base arms in an exchange set S∗ \ S, the sum of their random samples (in TSVerify) only has a bias of Õ( √∑ i∈S∗\S 1 Ni(t) ) towards the sum of their empirical means, while the
sum of their upper confidence bounds (in CLUCB) has a bias of Õ( ∑ i∈S∗\S √ 1 Ni(t) ). Since the observations of the base arms are independently drawn by the environment, the gap between the sum of their empirical means and the sum of their real means is Õ( √∑ i∈S∗\S 1 Ni(t) ). Therefore, our TS-Verify algorithm not only has correctness guarantee (with proper C(δ, q, t)), but also achieves a width lower complexity upper bound. We also conduct some experiments to compare the complexity of TS-Verify with CLUCB, and the experimental results (which are listed in Appendix C) demonstrate the effectiveness of our algorithm.
Though the complexity bound of TS-Verify still has some gap with the optimal one O(H0,c log 1δ ), we emphasize that this is because we do not assume the existence of more powerful offline oracles, and only use a simple offline oracle to solve the combinatorial pure exploration problems. Both the existing optimal policies (Chen et al., 2017; Jourdan et al., 2021) either suffer from an exponential time cost, or require to adopt more powerful offline oracles (please see Appendix D for more details). Therefore, our algorithm is more general, and can be attractive in real applications with large scale (which means a large width) and complex combinatorial structures (which may result in a high implementation cost for the optimal learning algorithms). Remark 4. If the value |I| is unknown (which is common in real applications), we can use 2m instead (i.e., C(δ, q, t) = 4 log(24·2 mt2/δ)
φ2(3q) ). This only increases the constant term in the complexity upper bound and does not influence the major term O(H1,c log 1δ ).
ETHICS STATEMENT
Our TS-based algorithm is easy to implement and has low complexity in combinatorial pure exploration. Therefore, many important applications in our life, such as routing systems and online advertising systems, can benefit from this new approach, i.e., the systems can find out their optimal actions with much lower cost than before. Besides, the idea of using TS in combinatorial pure exploration may push the development of algorithms in other pure exploration problems. On the other hand, since this paper only contains pure theoretical results, its negative impact on society is not obvious.
REPRODUCIBILITY STATEMENT
To make our theoretical results reproducible, we include the complete proof of Theorem 1 in Section 4.2 and the complete proof of Theorem 2 in Appendix B. Besides, we attach the detailed descriptions of the general explore-then-verify framework (Chen et al., 2017) in Appendix A. This can help to understand Fact 1, i.e., how to construct a complete pure exploration algorithm with complexity bound asymptotically the same as a verification algorithm.

heading: A GENERAL EXPLORE-THEN-VERIFY FRAMEWORK
text: Algorithm 2 outlines the general explore-then-verify framework (Chen et al., 2017).
In this framework, there are several independent procedures, and the k-th procedure is active at time step t only if t mod 2k = 0. Each procedure k contains two stages: an exploration stage and a verification stage. The exploration stage of procedure k is a complete pure exploration algorithm, i.e., it outputs the optimal arm with probability at least 1 − δ0 (here we choose δ0 = 0.1). After the exploration stage of procedure k outputs an arm, the verification stage of procedure k then tries to verify that the output arm is the optimal arm with confidence 1 − δ
2k . Once a verification stage
(of any procedure) outputs that its input arm is the optimal arm, then all the procedures terminate, and the explore-then-verify framework outputs that arm as the result of pure exploration. We can see that all these steps form a complete pure exploration algorithm with error constraint δ (which is different with the complete pure exploration algorithm in the exploration stage with error constraint δ0).
Algorithm 2 Explore-then-verify framework 1: Input: Error constraint δ. 2: Init: For any k ≥ 1, procedure k contains two stages. In the first stage, it explores with
constant error probability δ0 = 0.1; in the second stage, it tries to verify that the output arm of the exploration stage is the optimal arm with error probability δ
2k .
3: At time step t, if t mod 2k = 0, then procedure k is active (i.e., it can choose an arm to pull). 4: If in any procedure k, the output arm of its exploration stage gets through the verification stage,
then output that arm and terminate the algorithm (as well as any other procedures).

heading: B PROOF OF THEOREM 2
text: Recall that J = {S∗ \ S, S \ S∗ : S ∈ I}, and the three events E0,c, E1,c, E2,c are defined as following.
E0,c = ∀t, U ∈ J , |∑ i∈U (µ̂i(t)− µi)| ≤ √∑ i∈U 1 Ni(t) log(24|I|t2/δ)  ; E1,c =
∀t, k, U ∈ J , |∑ i∈U (θki (t)− µ̂i(t))| ≤ √ C(δ, q, t) ∑ i∈U 1 Ni(t) log(24|I|t2M(δ, q, t)/δ)  ; E2,c = { ∀t, |p̂S̃(t)− pS̃(t)| ≤ √ log(12t2/δ)
M(δ, q, t)
} .
Note that the random variable (µ̂i(t) − µi) is zero-mean and 1Ni(t) sub-gaussian, and for different i, the random variables (µ̂i(t)− µi)’s are independent. Therefore, ∑ i∈U (µ̂i(t)− µi) is zero-mean
and ∑ i∈U 1 Ni(t) sub-Gaussian. Then by concentration inequality,
Pr |∑ i∈U (µ̂i(t)− µi)| > √∑ i∈U 1 Ni(t) log(24|I|t2/δ)  ≤ 2 exp(− log(24|I|t2/δ)) = δ 12|I|t2 .
This implies that
Pr[¬E0,c] ≤ ∑ U,t
δ 12|I|t2 ≤ ∑ t δ 6t2 ≤ δ 3 ,
where the second inequality is because that |J | ≤ 2|I|, and the third inequality is because that∑ t 1 t2 ≤ 2.
Similarly, the random variable (θki (t) − µ̂i(t)) is a zero-mean Gaussian random variable with variance C(δ,q,t)Ni(t) , and for different i, the random variables (θ k i (t)− µ̂i(t))’s are also independent. Then by concentration inequality,
Pr |∑ i∈U (θki (t)− µ̂i(t))| > √ C(δ, q, t) ∑ i∈U 1 Ni(t) log(24|I|t2M(δ, q, t)/δ)  ≤ 2 exp(− log(24|I|t2M(δ, q, t)/δ))
= δ
12|I|t2M(δ, q, t) .
This implies that
Pr[¬E1,c] ≤ ∑ U,t,k
δ 12|I|t2M(δ, q, t) ≤ ∑ U,t
δ 12|I|t2 ≤ ∑ t δ 6t2 ≤ δ 3 ,
where the second inequality is because that there are totally M(δ, q, t) sample sets at time step t.
Let Yk(t) = I[Sk(t) = S̃], then we know that {Yk(t)}M(δ,q,t)k=1 are M(δ, q, t) i.i.d.s with real mean pS̃(t) and empirical mean p̂S̃(t). Therefore
Pr [ |p̂S̃(t)− pS̃(t)| ≤ √ log(12t2/δ)
M(δ, q, t)
] ≤ 2 exp(− log(12t2/δ)) = δ
6t2 ,
which implies that
Pr[¬E2,c] ≤ ∑ t δ 6t2 ≤ δ 3 .
Now it is sufficient to prove that under event E0,c ∧ E1,c ∧ E2,c, the two properties in Theorem 2 hold. In this proof, we denote M(t) = M(δ, q, t), C(t) = C(δ, q, t), L1(t) = log(24|I|t2/δ) and L2(t) = log(24|I|t2M(δ, q, t)/δ). Consider the two cases in Theorem 2:
i) When S̃ = S∗: in this case, we claim that any arm i cannot be pulled ifNi(t) ≥ 16 widthC(t)L2(t)∆2i,c , and we will prove this claim by contradiction.
For any arm i /∈ S∗ (the proof for arms i ∈ S∗ is similar), if it is pulled at time step t and Ni(t) ≥ 16 widthC(t)L2(t)∆2i,c , then from the description of TS-Verify, there exists S 6= S ∗
and i ∈ S \ S∗ such that for some k, ∑ j∈S θ k j (t) ≥ ∑ j∈S∗ θ k j (t) (which is the same as∑
j∈S\S∗ θ k j (t) ≥ ∑ j∈S∗\S θ k j (t)), and Nj(t) ≥ Ni(t) for all j ∈ (S∗ \ S) ∪ (S \ S∗). Now
let A(t) = ∑ j∈S\S∗ 1 Nj(t) and B(t) = ∑ j∈S∗\S 1 Nj(t)
, we have that∑ j∈S\S∗ θkj (t) ≤ ∑ j∈S\S∗ µ̂j(t) + √ A(t)C(t)L2(t) (5)
≤ ∑
j∈S\S∗ µj +
√ A(t)L1(t) + √ A(t)C(t)L2(t) (6)
< ∑
j∈S\S∗ µj +
∆i,m 2
(7)
≤ ∑
j∈S\S∗ µj +
∆S,m 2 ,
where Ineq. (5) is because of E1,c; Ineq. (6) is because of E0,c; Ineq. (7) is because that ∀j ∈ S \ S∗, Nj(t) ≥ Ni(t) ≥ 16 widthC(t)L2(t)∆2i,m and therefore √ A(t)C(t)L2(t) ≤ ∆i,m4 and √ A(t)L1(t) < ∆i,m 4 (since q ≥ δ, we must have that C(t)L2(t) > L1(t)). Similarly, for arms j ∈ S
∗ \ S, we have that ∑
j∈S∗\S
θkj (t) ≥ ∑
j∈S∗\S
µ̂j(t)− √ B(t)C(t)L2(t)
≥ ∑
j∈S∗\S
µj − √ B(t)L1(t)− √ B(t)C(t)L2(t)
> ∑
j∈S∗\S
µj − ∆i,m
2 (8)
≥ ∑
j∈S\S∗ µj +
∆S,m 2 ,
where Ineq. (8) is because that ∀j ∈ S∗ \ S,Nj(t) ≥ Ni(t) ≥ 16 widthC(t)L2(t)∆2i,m . This contradicts with ∑ j∈S\S∗ θ k j (t) ≥ ∑ j∈S∗\S θ k j (t).
Therefore, we know that the complexity Z satisfies Z ≤ ∑ i∈[m] 16 widthC(Z)L2(Z) ∆2i,c = 16H1,cC(Z)L2(Z).
With C(Z) = 4 log(24|I|Z 2/δ)
φ2(3q) , φ 2(3q) = Θ(log 13q ), L2(Z) = log(24|I|Z 2M(Z)/δ) and M(Z) = log(12Z2/δ)
q2 , we have that (note that we require q ≥ δ)
Z ≤ Θ ( H1,c
log(|I|Z) + log 1δ log 1q
( log(|I|Z) + log 1
δ
)) . (9)
Then we can use the following lemma to find an upper bound for complexity Z. Lemma 1. Given K functions f1(x), · · · , fK(x) and K positive values X1, · · · , XK , if ∀x ≥ Xk,Kfk(x) < x holds for all 1 ≤ k ≤ K, then for any x ≥ ∑ kXk, ∑ k fk(x) < x.
Proof. Since X1, · · · , XK are positive values, for any x ≥ ∑ kXk, we must have that x ≥ Xk. Therefore Kfk(x) < x, which implies that∑ k Kfk(x) < ∑ k x.
This is the same as ∑ k fk(x) < x.
To apply Lemma 1, we set f1(Z) = H1,c log2(|I|Z)
log 1q , f2(Z) = H1,c log(|I|Z) log 1δ log 1q , and
f3(Z) = H1,c log2 1δ log 1q . After some basic calculations, we get that X3 = Θ(H1,c log2 1δ log 1q ), X2 = Θ(H1,c log(|I|H1,c) log 1δ
log 1q +X3) and X1 = Θ(H1,c log2(|I|H1,c) log 1q ).
Then we know that for Z ≥ Θ(H1,c(log 1δ + log(|I|H1,c)) log 1δ log 1q + H1,c log2(|I|H1,c) log 1q ), f1(Z) + f2(Z) + f3(Z) < Z (by Lemma 1). This contradicts with Eq. (9). Therefore, we know that Z = O(H1,c(log 1 δ + log(|I|H1,c)) log 1δ log 1q +H1,c log2(|I|H1,c) log 1q ).
ii) When S̃ 6= S∗: in this case, we consider the probability that ∑ i∈S∗\S̃ θ k i (t) ≥ ∑ i∈S̃\S∗ θ k i (t),
i.e., super arm S∗ is better than S̃ in the k-th sample set. Here we denote A(t) = ∑ i∈S̃\S∗ 1 Ni(t)
, B(t) = ∑ i∈S∗\S̃ 1 Ni(t) .
Note that ∑ i∈S∗\S̃ µi ≥ ∑ i∈S̃\S∗ µi, therefore, under event E0,c, we must have that∑
i∈S∗\S̃ µ̂i(t)− ∑ i∈S̃\S∗ µ̂i(t) ≥ ( ∑ i∈S∗\S̃ µi− √ B(t)L1(t))−( ∑ i∈S̃\S∗ µi+ √ A(t)L1(t)) ≥
− √ A(t)L1(t)− √ B(t)L1(t). Since ∑ i∈S∗\S̃ θ k i (t)− ∑ i∈S̃\S∗ θ k i (t) is a Gaussian random vari-
able with mean ∑ i∈S∗\S̃ µ̂i(t)− ∑ i∈S̃\S∗ µ̂i(t) and variance A(t)C(t) +B(t)C(t), we have that (recall that Φ(x, µ, σ2) = PrX∼N (µ,σ2)[X ≥ x]):
Pr  ∑ i∈S∗\S̃ θki (t) ≥ ∑ i∈S̃\S∗ θki (t)  = Φ 0, ∑ i∈S∗\S̃ µ̂i(t)− ∑ i∈S̃\S∗ µ̂i(t), A(t)C(t) +B(t)C(t)  ≥ Φ(0,− √ A(t)L1(t)− √ B(t)L1(t), A(t)C(t) +B(t)C(t))
= Φ( √ A(t)L1(t) + √ B(t)L1(t), 0, A(t)C(t) +B(t)C(t))
= Φ
(√ L1(t) C(t) · √ A(t) + √ B(t)√ A(t) +B(t) , 0, 1 )
≥ Φ ( 2 √ L1(t)
C(t) , 0, 1 ) = 3q, (10)
where Eq. (10) is because that C(t) = 4L1(t)φ2(3q) and Φ(φ(3q), 0, 1) = 3q (by definition of φ). This implies that Pr[ ∑ i∈S̃ θ k i (t) = maxS∈I ∑ i∈S θ k i (t)|{Ni(t), Ri(t)}mi=1] ≤ 1− 3q.
Note that pS̃(t) only depends on E0,c but does not depend on E1,c and E2,c. Therefore under event E0,c ∧E1,c ∧E2,c, we still have that pS̃(t) ≤ 1− 3q. Also recall that we set M(δ, q, t) = log(12t2/δ) q2 ,
which implies √
log(12t2/δ) M(δ,q,t) = q. Therefore, by event E2,c, we know that p̂S̃(t) ≤ pS̃(t) + q ≤
1− 3q + q < 1− q, i.e., TS-Verify will not stop in this case.

heading: C EXPERIMENTS
text: Here we conduct a simple experiment to compare the complexity of our algorithm with CLUCB, and to demonstrate the effectiveness of our algorithm. In this experiment, we consider the following combinatorial pure exploration problem instance with parameter n ∈ N+. Problem 1. For fixed value n, there are totally 2n base arms. For the first n base arms, their expected rewards equal to 0.1, and for the last n base arms, their expected rewards equal to 0.9. There are only two super arms S1, S2. S1 contains the first n base arms and S2 contains the last n base arms.
Since there are only two super arms, our TS-Verify can also be used to do pure exploration, i.e., at time step t, if S1 is the optimal super arm in at least (1 − q)M(δ, q, t) sample sets, then we output that S1 is optimal; if S2 is the optimal super arm in at least (1 − q)M(δ, q, t) sample sets, then we output that S2 is optimal; otherwise we pull all the arms in a round robin method. In this way, we can compare TS-Verify with CLUCB directly. As for the input q in TS-Verify, we always choose q = δ.
We first fix δ = 0.1, and compare the complexity of TS-Verify with CLUCB under different n. The results (average complexities and their standard deviations) take an average over 20 independent runs, and are shown in Fig. 1(a). We can see that when n increases, the complexity of TS-Verify does not increase a lot, while the complexity of CLUCB increases linearly. This accords with our analysis, since H1,c(n) = 2n · 2n(0.8n)2 = 6.25 is a constant but H2,c(n) = 2n · (2n)2
(0.8n)2 = 12.5n is linear with n (here H1,c(n), H2,c(n) are the values of H1,c, H2,c under the problem instance with parameter n, respectively).
Then we fix n = 10, and compare the complexity of TS-Verify with CLUCB under different δ. The results (average complexities and their standard deviations) take an average over 20 independent runs, and are shown in Fig. 1(b). We can see that when δ is large, the complexity of TS-Verify
decreases as δ decreases, and when δ is small, the complexity of TS-Verify increases as δ decreases. Moreover, the complexity of TS-Verify always increases slower than CLUCB (when δ decreases). This also accords with our analysis. Note that there is a term O(H1,c
log2(|I|H1,c) log 1q ) in the complexity
bound in Theorem 2. Since we choose q = δ, this term decreases as δ decreases. When δ = 0.1, this term is very large and becomes the majority term in complexity, and therefore the complexity decreases when we decrease δ from 0.1 to 0.002. When δ = 0.002, the termO(H1,c log 1δ ) becomes the majority term in complexity, therefore the complexity increases when we decrease δ from 0.002 to 0.001.
All the above results indicate that our TS-Verify algorithm outperforms CLUCB.

heading: D DISCUSSIONS ABOUT THE OFFLINE ORACLES IN OPTIMAL ALGORITHMS FOR COMBINATORIAL PURE EXPLORATION
text: Most existing works on combinatorial pure exploration (e.g., (Chen et al., 2014; 2017; Jourdan et al., 2021)) need to use the basic offline oracle, i.e., given a set of parameters [θ1, · · · , θm], it can output arg maxS∈I ∑ i∈S θi, the best super arm under this parameter set. Similar with (Chen et al., 2014), our TS-Verify algorithm also only needs to use this offline oracle, and it is efficient (i.e., its time complexity is polynomial with m) as long as this basic offline oracle is efficient.
However, the algorithms in (Chen et al., 2017; Jourdan et al., 2021) require efficient and more powerful oracles. Otherwise the time complexity of their algorithms becomes exponential with m. In (Chen et al., 2017), the NaiveGapElim algorithm needs to record all the super arms in I. This means that its time complexity can be exponential with m. As for the EfficientGapElim algorithm, it needs to solve three offline problems: OPT, Check and Unique, and directly solving these three problems leads to an exponential time cost as well. The authors apply an approximate version of Pareto curves to solve these problems, but this approach is only efficient under some special combinatorial structures. Therefore, for the most general combinatorial pure exploration setting, EfficientGapElim either suffers from an exponential time complexity, or requires more powerful offline oracles to solve the above three problems efficiently.
In (Jourdan et al., 2021), the best-response oracle used by the λ-player has time cost scaled with |N(St)|, where St is a super arm, N(St) represents the set of super arms whose cells’ boundaries intersect the boundary of the cell of St, and the cell of a super arm St is defined as all the possible parameter sets [θ1, · · · , θm] in which St is the optimal super arm. Though the size of N(St) is always smaller than I, it can still be exponential with m. Therefore, the CombGame algorithm in (Jourdan et al., 2021) either suffers from an exponential time complexity, or requires more powerful offline oracles to substitute the origin best-response oracle used by the λ-player.
In fact, existing optimal learning policies need to use the more powerful offline oracles to efficiently find the base arm that needs exploration the most. Here we say base arm i needs exploration the most at time t if αN∗i log 1 δ −Ni(t) is the largest one among the set of base arms, where α is some universal constant, N∗i is the value of Ni in the optimal solution H0,c. From this definition, we can see that if we always pull the base arm that needs exploration the most, then the frequency of pulling each base arm converges to the optimal solution of H0,c, and this achieves the optimal complexity upper bound. However, the basic offline oracle in TS-Verify can only find several insufficiently learned super arms (i.e., the super arms that have been optimal in at least one sample set), and cannot tell us which base arm (in these insufficiently learned super arms) needs exploration the most. Therefore, if we want to use a more powerful offline oracle in TS-verify to achieve an optimal complexity upper bound, then this offline oracle needs to tell us which base arm in these insufficiently learned super arms needs exploration the most. If this powerful offline oracle can always output the base arm that needs exploration the most, then the complexity upper bound of TS-Verify is reduced to O(H0,c log 1δ ) and becomes optimal. How to design such offline oracles (to look for the base arm that needs exploration the most in our TS-Verify framework) and how to implement them efficiently is one of our future research topics.

Review summaries:
This paper designs the first TS-based algorithm to solve the pure exploration problem for both multi-armed bandit (MAB) and combinatorial MAB (CMAB) problems. It mainly focuses on the verification problem where a target arm is given and the algorithm needs to determine whether it is the optimal one.   Benefiting from independent samples of the TS algorithm, the TS-based verification framework achieves lower complexity than the UCB-based one.  

The paper provides a Thompson Sampling (TS) algorithm for verifying whether a given arm is indeed the best arm (or best super-arm in a combinatorial bandit) with fixed confidence and its theoretical analysis. The proposed algorithm TS-Verify can be used as a subroutine within the explore-then-verify framework of [Karnin 2016, Chen et al 2017] which identifies the best arm (or super-arm) with fixed confidence. The theoretical analysis of the algorithm shows it uses a factor of width fewer samples for verification in combinatorial bandits compared to existing CLUCB algorithm [Chen et al 2014]. The key step in the analysis is defining three events that occur with high probability. $E_{0,m}$ is a concentration event due to independent samples from each arm distribution, $E_{1,m}$ is a single sample Gaussian tail and $E_{2,m}$ is a concentration event for independent Bernoulli samples. These events specify random events for all times, and each time step $t$ defines an independent probability measure. The analysis for the combinatorial bandit follows a similar path, and at a high level, the improved sample complexity is obtained due to the concentration of event $E_{0,c}$ in appendix.

This work studies pure exploration for stochastic combinatorial multi-armed bandits, for the fixed confidence setting.  Thus, the goal is to take actions so that the optimal action is identified with high probability (achieving a pre-specified fixed confidence) with as few samples as possible.  While similar problems have been well-studied when action space has (best arm identification, top-k identification), the more general combinatorial setting has not been.  A (common) simplifying assumption of linear reward is used.     This work proposes a explore-then-verify type method.  For some action sets and confidence levels, the explore stage can be done quickly while verification can be challenging.  In the proposed method, base arms are first explored (this work suggests low complexity off-the-shelf method), then a verification stage, for which the method proposes and analyzes a novel verification algorithm using Thompson-sampling.   The authors prove sample complexity bounds for their method, showing it can be competitive against state of the art methods, and is asymptotically optimal (as the confidence level delta goes to 0). 

Pure exploration plays an important role in online learning. Existing work mainly focuses on the UCB faces some challenges when looking for the best arm set under some specific combinatorial structures, so authors explore the idea of Thompson Sampling (TS) that uses independent random samples instead of the upper confidence bounds to make decisions, and design the first TS-based algorithm framework TS-Verify. In TS-Verify, the sum of independent random samples within arm set S will not exceed the exact upper confidence bound of S with high probability. As for pure exploration of classic multi-armed bandit, they show that TS-Verify achieves an asymptotically optimal complexity upper bound.  The TS-based verification framework TS- Verify takes a target (super) arm as input, and aims to verify that this target (super) arm is optimal with error constraint . At each time step, TS-Verify first draws independent random samples  for all the (base) arms. Then it tries to find out the M best (super) arms under sample sets.  If in most of these sample sets, the target (super) arm is the best one, then the algorithm will output that the target (super) arm is indeed optimal. Otherwise, the algorithm will choose to pull a (base) arm from the exploration set, which contains the target (super) arm and all the (super) arms that have been optimal in at least one sample set at this time step.