Thompson Sampling for (Combinatorial) Pure Exploration
Authors: Siwei Wang
Jun Zhu
Venue: ICLR 2022 Submitted (2022)
Keywords: pure exploration
(combinatorial) multi-armed bandit
Thompson Sampling

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.

Under review as a conference paper at ICLR 2022
THOMPSON SAMPLING FOR (COMBINATORIAL) PuRe EXPLORATION
Anonymous authors Paper under double-blind review
ABSTRACT
Pure exploration plays an important role in online learning. Existing work mainly focuses on the UCB approach that confidence bounds of all the arms de- cide 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 de- cisions, and design the first -a-edded algorithm framework TS- TS-Verify Verify for (combi- natorial) pure exploration. In TS- Veriff, the sum of independent random samples within 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.
INTRODUCTION
Pure exploration is an important task in online learning, and 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 D; with mean μ4: Once arm pulled, it returns an observation r;, which is drawn independently from distribution D; by the environment. At each time step f, 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 6, its output arm a(t) is the optimal arm (i.e., a(t) = arg max (4) 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 cos- metics, there is always testing phase before the commercialization phase (Audibert et al. 2010). The goal of the testing phase is help maximize the cumulative reward collected in the com- mercialization phase. Therefore, instead of regret minimization (Berry & Fristedi 1985 Auer et al.) 2002), the testing phase only needs to do exploration (e.g., to investigate which product 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, 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 pure exploration problem instance in combinatorial multi-armed bandits (CMAB). In this setting, still pull single set I C 20ml The expected reward of
arms (base arms) each time step, and there is super super arm 5 E I is Eieg μú i.e., the sum of the expected rewards of its contained base arms. And the goal of the player to find out the optimal super arm with error probability at most 8.
Most of the existing solutions for pure exploration follow the UCB approach (Audibert et al. 2010 Kalyanakrishnan al. 2012 Chen et al. 2014 Kaufmann & Kalyanakrishnan 2013). They com-

---

Under review as a conference paper at ICLR 2022
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 (Kalyanakrish- nnn et al. 2012 Kaufmann & Kalyanakrishnan 2013), it faces some challenges in the CMAB case (Chen 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 Ó(EiEs v 1/NN)) (here N, 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 Ö Vies 1 1/N,), which is much smaller. This means that the used upper confidence bound 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 Ö ((/T)) 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 Ö Eies 1/Nx), which has the same order 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) [Thmpsoon] 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 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 frequen- tist setting for both MAB and CMAB instances by adapting the idea of TS in the Bayesian setting (Li et al. 202T}. 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. 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- -ased policies that pull the arm with the largest upper confidence bound), then the mechanism of the TS- 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.
-CB-based algorithms, the upper confidence bound of the
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 f, the parameters of the game follow a posterior distribution Pt, and the random samples are drawn from P. indepen- dently well. Therefore, using the random samples to output the optimal arm can explicitly ensure the correctness of the 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. Be- cause of this, if we still use the random samples to output the optimal arm, then the distributions of random samples in the TS- algorithm need to be chosen carefully to make sure that it still has correctness guarantee in the frequentist setting.
Besides, the analysis of basba 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
2

---

Under review as a conference paper at ICLR 2022
set of samples. Therefore, we must draw several sets of samples make decisions, and this may fail existing analysis in regret minimization. For example, the analysis in (Agrawal & Goyal 2013) obtains lower bound for the probability that the optimal arm has the highest sample in 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 (c.g., its empirical mean equals to its real expected reward minus the confidence radius).
In this paper, we solve the above challenges, and design TS-based verification framework TS- Verify for (combinatorial) pure exploration under the frequentist setting. TS- Verify takes target (super) arm as input, and aims to verify that this target (super) arm is optimal with error constraint 6. At each time step 1. TS- VSr-vr first draws independent random samples 0f (t) for all the (base) arms i [m] and k = 1,2, .... M (i.e., totally M independent samples for each arm). Then it tries to find out the M best (super) arms under sample sets 0³ (t) = (t). ... 6% (t) for k 1, 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, mainly focus the behaviour (i.c., correctness guarantee and com- plexity upper bound) of this verification algorithm, which is almost the same as a complete pure exploration algorithm after we adapt the geplore-then-verie 2017]. In the general CMAB setting, we show that VS-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 satisty some specific properties, which is less general than our results. As for the MAB case, we show that TS-Verify asymptotically optimal, i.e., it has a comparable complexity as existing optimal algorithms (Kalyanakrishnan et al. 2012 Kaufmann & Kalyanakrishnan, 2013) when 8 - 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.
framework (Karnin) (006:) Chen al.,
2 RELATED WORKS
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 al- gorithms are successive-eliminate
(Even-Dar et al., 2006 Audibert et al., 2010: Kaufmann & al.
Kalyanakrishnan, 2013) and LUCB (Kalyanakrishnan 2013]. Both of them adapt the idea of UCB (Auer et al. 2002) and achieve an asymptotically
2012: Kaufmann & Kalyanakrishnan,
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- TS-Verify policy uses a totally dif- ferent approach, and can achieve an asymptotically optimal complexity upper bound as well.
Combinatorial pure exploration is first studied by Chen et al. (004).. They propose CLUCB, an LUCB-based algorithm that is efficient as long as there is an offline oracle to output the best su- per 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 spe- cific constraints so that they can apply 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 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.
3 PRELIMINARIES
3.1 PURE EXPLORATIOON IN MULTI-ARMED BANDIT
A pure exploration problem instance of MAB is a tuple (Im). D) Here [m] = (1, m) is the set of arms, D (Di; D2,..., Dm, are the corresponding reward distributions of the arms,
3

---

Under review as a conference paper at ICLR 2022
and 8 is the error constraint. In this paper, we assume that all the distributions Dj's supported on [0, 1]. Let ju, - Exx=D,L [X] denote the expected reward of arm and a arg ga 44 is the optimal arm with the largest expected reward. Similar with many existing works (e.g., (Audibert (aaal.221110 (010)), we also assume that the optimal arm unique. At each time step t, the learning policy can either pull an arm i(() E [m]] output an arm a(t) [m]] If chooses to pull arm i()), then will receive an observation ra(e) (I), which drawn independently from distribution Da The make sure that with probability at least 8, its output a(t) = a".
goal of the learning policy
Under this constraint, it aims to minimize the complexity z - Ein N,(T)), where T denotes the time step that policy chooses to output a(t), and (1) denotes the number of observations on arm i until time step t.
Let A.m - Pa- μ4 denote the expected reward gap between the optimal arm a" and any other arm i * a", For the optimal arm a", its A..m is defined as pe- maXişeo" μ4, We also define Hm A Eie(m] x._, and existing works (Kalyanakrishnan et al. 2012) show that the complexity
lower bound of any pure exploration algorithm 52 Hm log }).
3.2 PURE EXPLORATION IN COMBINATORIAL MULTI-ARMED BANDIT
A pure exploration problem instance of CMAB is extension of the MAB case. The arms E [m]] called base arms, and there is also super set I S 2(ml, For each super arm S E I, its expected reward is Eies P4. Let S = arg max Lies 14 denote the optimal super arm with the largest expected reward, and assume that the optimal super arm is unique (as in (Chen al.) 2014)). At each time step t, the learning policy π can either pull a base arm i(t) E [m]. or output super arm S(t) I. The goal of the learning policy is to make
that with probability least
1 6, 6, its output (() = S* Under this constraint, it also wants to minimize its complexity 2"
As assumed in many existing works (Chen et al. 2013 2014 Wang & Chen that there exists an offiie Oracle, which takes a set of parameters = 10 Om as input, and outputs the best super arm under this parameter set, i.c., Oracle(O) arg maxger EieS O,.
2018), also assume
In this paper, for of S we use Di, e reward gap between the optimal super arm and the best super arm that contains i. As for E S*, its A,, is defined as Aic A Ejes- Py - maxseIves Ejes ky. i.e. the expected reward gap between S* and the best super arm that does not contain i. We also define width A maxs45- |*1+ + 1S* \ S)), and Hi,c A width Exe(mi x.. Hz, - width ΣiE(ma) -7
Ejes- Pj maxseIses Ejes 24 to denote the expected
Chen et al. (017) prove that the complexity lower bound is H2, log 1),, where Ho, is the solution of the following optimization problem (here As,e Eies- p4 EiES Mh):
min
Nm
VE
m
s.t.
Σ VESYS-
Σ
1
<
< S,ot
VS ESEI,S#5
N
N
BES-1.
The following result shows the relationships between Ho,e, HI,c and H2,0- Proposition 1. For any combinatorial pure exploration instance, Ho,e H1, S H2
Proof. Since width 2 1, we have that HI,e S H2 As for the first inequality, note that vi E [m]. width is a feasible solution of the optimization problem. Hence we have that Hu,e S Hi.e- A?
N
3.3 GENERAL EXPLORE-- THER--TEE--- VERIFY FRAMEWORK
Due to space limit, the detailed descriptions of the general explore- the---erine---yyy framework (Chen et al. 2017) is deferred to Appendix A
Fact 1. (Lemma 4.8 in (Chen et al.) 2017 there exist i) complete pure exploration algorithm that outputs the optimal arm with probability least 8 and complexity at most O(Hr log &/2 + Cε);
4

---

Under review as a conference paper at ICLR 2022
Algorithm TS- Verify
1: Input: Error constraint ö, target ā (or $), (ô, 0.1., 6= m, N₁ - 0 R 0 for all E [m]]
2: Pull each arm once, update their number of pulls N₁ 's and the sum of their observations R
3: while true do
4: for k= 1,2, 1,2,.... ................................ M(, q, () do
5:
For each arm i, draw sample 0f (1) independently from distribution
N R. C(Sad))
N; N;
6:
(t) (t)) is the best (super) arm under parameter set [0] (t), 0h: (t)).
7:
end for
Pa(t) = M(6.g.t) Ek=1 () (t) = a] (fz(t) = M(d...)) E ((6.0))) 115 (t) = 51).
8:
9:
if (t(()) > 1 (Pş(t) > 1- - q) then
Return: Arm (super arm 5) is indeed the optimal one.
11: else
Arbitrarily choose o' E (t)) (1)) M(6..44 such that 5" S). k=1
M(8.a:) such that a' * (arbitrarily choose S'
Pull arm i(t) from the exploration set {a',ā) ā} (15",, $3), update its number of pulls Ni(o)
and the sum of its observations Ri(zy-
t ++1
15:
end if
16:
end while
and ii) a verification algorithm such that with probability at least 1- 6, outputs that its input is optimal with complexity at most O(Hv log 1 + Cvv) 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 ayplore-then-verip framework. It works correctly with probability at least 1 5, and its expected complexity is upper bounded by O( log by + Hy log +
C5 + Cv) fixed óg = 0.1.
According to Fact I in the rest of this paper, we focus on designing verification algorithms based on the TS approach. As long as we have verification algorithm with error probability 5 and complexity upper bound O (y log + ), using any efficient complete pure exploration algorithm (e.g., LUCB KKlyaankrisshaa et al. 2012) or CLUCB (Chen et al. 2014)) in the explore-then-verits framework can make sure that the expected complexity of the constructed pure exploration algorithm upper bounded by O(H log 2/ + Hy log 1/4 + Cg + Cv), which asymptotically the same as the complexity upper bound O(Hy log }) (since all the other terms do not depend on 8).
4 THOMPSON SAMPLING-BASED VERIFICATION
4.1 GENERAL VERIFICATION FRAMEWORK FOR PURE EXPLORATION
Our Thompson Sampling- based verification framework (TS- S--eiify) is described in Algorithm T We use N, to denote the number of observations arm i, R3 to denote the sum of all the observations from arm i, and (.(,), (() to denote the value of N,, Rú at the beginning of time step I.
At each time step t, for any i [m], TS- Verify first draws M q. t) 1og(12:2/0) /6) random samples g²
(t) M(..g.4) independently from a Gaussian distribution with mean (t( & R,(r)
(i.c., the em- M.(e)
pirical mean of arm i) and variance C(8.g.t)
(.) (i.c., inversely proportional to Nt)))), where C'ô q. is term depending on the settings and will be explained in detail later. Then Ve-Veryfy checks which (super) arm optimal the k-th sample set (t). ... 0% (t)] for
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 à (or target super arm 5) is the optimal one is large enough. If the number of such sample sets is larger than (1 M (6, q, t), then TS- TerVer outputs that the target (super) arm is optimal. Otherwise it knows that either the target (super) arm not optimal, or some (super) arms are sufficiently learned (i.e., they do have enough observations). In this
case, TS- Verify constructs exploration set (a', a) (or { (S))) where a' of is an arbitrary arm
5

---

Under review as a conference paper at ICLR 2022
(or S' * S is 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 use Gaussian random samples in TS- Verify is because it can simplify the analysis significantly (since the sum of independent Gaussian random variables 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.
4.2 TS- VERIFY FOR MULTI-ARMED BANDIT
We first apply TS- ---rrryyy to the classic MAB case. the following, we define $(x, H, 0²) - Prx-N(woo3) X 2 2²), and (zz) satisfies that o (()(x), 0, = x for all r E (0.
In the MAB case, we set q( choose to pull the arm with smaller number of observations.
(og()1mm and for the exploration set fa', a), we will (34)
Theorem 1. For q E [6, 0.1), with probability at least 1 - 6, we have that: i) if ā = a², TS- Verify will return that arm ā is the optimal arm with complexity upper bounded by O(H (log + log(m (m Hm))
log 3 Tog 1
+ Hm
log" (m (mnfm)), ); ū) if ā + a", TS-Verify will not stop. Specifically, if we choose log.
q 8, then the complexity upper bound is ( log + Hm (mH)))
Remark 1. The value in TS-Verify is used to control the number of times that we draw random samples at each time step. Note that (6, q,t) log(12( /5) Hence when q becomes larger. we need fewer samples, but the complexity bound becomes worse. Here is a trade-off between the algorithm''s 's complexity and the number of random samples it needs to draw. Our analysis shows that using q = 8 for some constant B N 1 can make sure that the complexity upper bound remains the same order, and reduce the number of random samples significantly.
4²
Proof. Firstly, we define the following three events:
log( 12m22 (8)
Ea,m =
Vt, it,i, (P((t) - -1s1
N:(t)
C(o,g, (02 ()/8))
E1,m
1i, 10)(1) - ic(0I
N,(t)
log( /5)
Eg
vt, (aa() pa(t)) <
M q.
Here Pa (t) denotes the probability that arm ä's sample is the largest one in the k-th sample set of time step t (i.e., Pr(O (t) = maxte(m] 0f (N,)), (t(t) )m also note that is not conditioned on m. We can see that (t) is its empirical mean in the M (8.q,t) sample sets.
By Chernonf- inequality, VI, (t(l)x(() pul >
[og(12m(1/8)) N.C.)
U therefore
Pr|-Cu,m] < Et, 6m S. Similarly, one can also prove that Ei < (note that there are M(5, q, () sample sets at time step I, and the variance of 0f (L) is C(d.g.t) ) and Pr[-E2ml S $ N.(1)
Then we only need to prove that under event Eu,m A E1,m A &2,, the two properties in Theorem I hold. To simplify the notations, in this proof, we denote M() M0. q,t), C(t) C(..q.t),
Li (l) = 1l2m11mm22//111111 /5) and (2(() 10m(l ( q, 1))
Consider the two cases in Theorem
i) When à = a": in this case, we claim that any arm cannot be pulled if N.()) 2 16(())La(())
and
A
we will prove this claim by contradiction.
If we choose to pull arm i # a" and Nt(t) 2 16C(0L2(() then from the description of TS- Verify,
A? Arm.
there exists & such that 0% (1) 0 (1) and Ni(1) N₂- (t). However, also have that (in the rest

---

Under review as a conference paper at ICLR 2022
of this paragraph, A(t) N.(s) and B(t) (.)
(t) s P.(t) + ((t)
(1)
< M4 + (t(t) + (At))C(()L((t))
(2)
Aim
+
(3)
2
where Incq.
I is because of Ei.m: Ineq. (2 is because of Eo.m: Ineq.
is because that (t) 2
(a() and therefore (A(t)C(t)L2z(t I A.m and (1(t)Lz(t) Dim (since q 6, Di.m
4
must have that C(t)L2(t) (t)). As for the arm a", we have that
A Aim
0% 0 2 V0--VBBUSE (())(())a(() 2 pa- (((L) ((DC(())2() > p4 +
2
where the last inequality is because that No- 2 N,(1) Z 8 2 8% (t). Similarly, if Na-(1) 2
160())2(()) A?
This contradicts with
(6(())
then arm a" cannot be pulled as well. This means that the
A
complexity Z satisfies
16C(Z)L2(Z)
Z S
16H,,
A?
/E(m]
For q S 0.1, we have that (34) = (log 3g
Then with C(Z) =
4log(12m22/0) L2(Z) = dP
log( (2mm2222222// and M(Z)
log(122* (8)
have that (note that require @ 2 6)
log(m 7 log
(log(m2)) + log 1)
Z s 0 11m
log
Therefore, after some basic calculations, we know that
log(mHmm) + log (log(mHm)) + log 8 1))
Z = Hm
log !
ii) When A a": in this case, we consider the probability that arm a" has a larger sample than ä, i.e. Pr[O (1) 2 0% ()))(,,(()) (.. and let A(I) Na(ey and B(I) N.,
Note that pa- 2 Pa. therefore, under event Eu,m. we must have that Pia (t) -aa(t) 2 (pa-
(t) - (Ha + (T))) 2 - -V (1)) - (t) Since 0 (t) (t) is
Gaussian random variable with mean Pa (t) (ta()) and variance A(t)C(t) B(t)C(tt, we have
that (recall that (xc, 14, 0²)= = Pix [X 2 x)):
Pr[O (t) 2 (t)) = ((0, P.. (t) Pa A(t))) B(t)(())
@(0, A (0)) B(()C(O)
@ ((V(())L(() (1) B()C(()
(itt) VA(t) + /B() 0,
C(I) VA(I) +B()
(I(1)
2 +
2
0,
C(t)
3q.
(4)
where Eq. 4 because that C(t) (3g) and & (6(3g), 0,1) 3g (by definition of Φ) This
(t,
implies that (t) maxig[m] 0 (1), R (1) < 34.

---

Under review as a conference paper at ICLR 2022
Note that Pa only depends on Eu, but does not depend on &i,m and &,, Therefore under event Eo,m Am A..mAAa A. we still have that Pa (t) I 1 - 13g. Also recall that we set M (6, t) log(12 /6)
q²
which implies /
[1g(1129/0) [6.g..) = 4- Hence, by event m, we know that pra (1) S (1) + s
1- 3-34 + q < q. i.e. TS-Verify will not stop in this case.
Theorem shows that the complexity upper bound of TS- Se-Vifffy (as well as the complete pure ex- ploration a algorithm constructed by applying the explore-then-veet framework) is asymptotically optimal in the MAB case, i.e., it matches the complexity lower bound Hm log }) (Kalyanakrish- nnnn al. 2012) when 5 - O. To the best of our knowledge, this is the first analysis using 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 with (1) 2 (6C(())a(t)/A3 A? .)) J. For a complete pure explo- ration 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 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 in the exploration set. This makes sure that there is at least one insufficiently learned arm in the exploration sel, i.e. if the targel arm is sufficiently learned, then the other arm that has af least one larger random sample than the targel arm must be insufficiently learned. Therefore, the number of pulls on sufficiently learned arms in TS- Verify is limited.
we can always put the target
The variance term C(8, q, t) in TS-Verify is chosen carefully to both ensure the correct- ness and reduce the complexity upper bound. Since C(8. q, t) is not too low, for any sub-optimal target â, there is always some probability that the optimal arm a" has larger sample than â, even if the observations of a² are bad (e.g., s, its empirical mean equals to its real expected reward minus the confidence radius). This ensures the correctness of TS- TS- V-rriff On the other hand, since C(8, q, t) is not too high, the required number of observations on nub-optimal arm i is still O A log h).
Remark 3.
4.3 TS-VERIFY FOR COMBINATORIAN MULTI-ARMED BANDIT
Then we come to the CMAB case, and we choose C(d,g, 1) = 4 (log(24/Z)e"88) For the exploration
(²(4))
set [SS'S), we will choose to pull the arm i E (8' \ 5) ($ S') with the smallest number of observations (t)..
Theorem 2. For q E (6, 0.1,, with probability at least 1-8, we have that: i TS- VerVify will return that super arm S the optimal super arm with complexity upper bounded by O(H1,c(log + log
+ Hi,e log" (12 ); ii) if $ + S*, 7SSVerify will not stop. Specifically, if we choose q = 8, then the complexity upper bound is OHH,e log } + lo,e (ITHH))))
log( (I))) log
log
Now we provide proof sketch for Theorem while deferring its complete proof to Appendix
Proof (sketch). In the CMAB case, we first define J = (S* SSS St S I} as the exchange sets of any super arm and the optimal super arm S* Then similar as the proof of Theorem we can also define three events Eo,c, E1,c, &2,c.
Ev,c =
VL, J. [(a(()) m V
Σ Yew N.(1)
log log(24(Z12218)
iEU
E1, =
Vt, E J, Σ
(0t - A(O))s
C(5.g,t) Σ
Ni(t)
NEU
iEU
log(12(/8))
E2,0 =
(t, PP(())
M(O, 4)
8

---

Under review as a conference paper at ICLR 2022
Here (t) denotes the probability that at time step t, is the best super arm under the k-th sample set (i.e., Pr Of (t) maxsez Eies 0 Rt) We can see that Py(t) is its empirical mean in the M (6, (6,q,t) sample sets.
Similarly, we also have that Pr(Co,e A &1.e A E2,a] 2 1- and therefore it is sufficient to prove that under event E A& 2, the two properties in Theorem hold. In this proof, we denote M() ( q,t), t), C(t) C(ô, g, t). L1 (t) = log 222 and L2 = log (2 M (6, t)/5).
Consider the two cases in Theorem 2
i) When 3 = 5 in this case, we claim that any arm i cannot be pulled if N,(1) Z 16 width C(t)aa))) and we will also prove this claim by contradiction.
Here we only consider the case that i E S", the case that i E S* is similar. For any arm i & S*, if it pulled time step and (t, 2
16 width ((t) then from the description of TS-Verify, there 27,ec
exists S + 5 and E S such that for some k. Ejes (t) 2 Ejes (t) (which is the same as Σ E. (t) N Es (t)), and (2(t) 2 Nt(t) for all (S* ( S*). Now let A(t) = Σ s' (z) and B(t)= - Σ jss (r) then the proof is almost the same as Theorem (note that there are at most width arms in S \ 8 or S (S).
Therefore, we know that the complexity Z satisfies
16 width ((Z)Lz(Z)
Z S
16Hz,
A
VE ml
log which means that Z OH (log + log((I (og(()HH,)))
log'( I[H los
H1,0
log 1
ii) When $ S* in this case, we consider the probability that Eies 0, 2 E S. (t) (i.e., super arm S is better than S in the k-th sample set). Here we denote A(t) = Eierrs N.(1)
1
B(t) = Eies+i3 N,(t)) and then the proof becomes almost the same as Theorem !
Compared to existing works, the complexity upper bound of 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 TS- Verify) only has bias EiEss N.(J) towards the sum of their empirical means, while the
sum of their upper confidence bounds (in CLUCB) has a bias of Ö(Eies V N.(1) )- 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 Ō( D( /Eies'ss M Therefore, our TerVer algorithm not only has correctness guarantee (with proper C(6,, q, t)), but also achieves a width lower complexity upper bound. We also conduct some experiments to compare the com- plexity 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(Ho, log )). we emphasize that this is because we do not assume the existence of more powerful offfine oracles, and only use simple offline oracle 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 (Dor 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 [Z] is unknown (which is common in real applications), we can use n instead (i.e., C(ō, q, 4 (2" (8)). This only increases the constant term the complexity (3g)
upper bound and does not influence the major term O O(H1, log z))

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
Our IS--aaeed algorithm is easy to implement and has low complexity in combinatorial pure ex- ploration. 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 combinatorial pure ex- ploration 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 Tin Section 4.2 and the complete proof of Theorem Appendix Besides, attach the detailed descriptions
of the general explore-then-verif framework (Chen et al. (017)) in Appendix [A] This can help to understand Fact i.e., how construct a complete pure exploration algorithm with complexity bound asymptotically the same as verification algorithm.
REFERENCES
Shipra Agrawal and Navin Goyal. Further optimal regret bounds for thompson sampling. In Inter- national Conference on Artificial Intelligence and Statistics, 2013.
Jean Yves Audibert, Sébastien Bubeck, and Rémi Munos. Best arm identification in multi-armed bandits. In COLT 2010 the Conference on Learning Theory, Haifa, Israel, June, pp. 41-53, 2010.
Peter Auer, Nicolo Cesa Resa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235 256, 2002.
Donald A Berry and Bert Fristedt. Bandit problems: sequential allocation of experiments (Mono- graphs on statistics and applied probability). Springer, 1985.
Lijie Chen, Anupam Gupta, Jian Li, Mingda Qiao, and Ruosong Wang. Nearly optimal sampling algorithms for combinatorial pure exploration. In Conference Learning Theory, pp. 482-534. PMLR, 2017.
Shouyuan Chen, Tian Lin, Irwin King, Michael R. Lyu, and Wei Chen. Combinatorial pure ploration multi-armed bandits. In International Conference on Neural Information Processing Systems, pp. 379-387, 2014.
Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework, re- sults and applications. In Proceedings of the 30th International Conference on Machine Learning, pp. 151-159, 2013.
Richard Combes, Sadegh Talebi, Alexandre Proutière, and Marc Lelarge. Combinatorial bandits revisited. In Advances in Neural Information Processing Systems, 2015.
Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6), 2006.
Victor Gabillon, Alessandro Lazaric, Mohammad Ghavamzadeh, Ronald Ortner, and Peter Bartlett. Improved learning complexity in combinatorial pure exploration bandits. In Artificial Intelligence and Statistics, pp. 1004-1012. PMLR, 2016.
Mare Jourdan, Mojmír Mutný, Johannes Kirschner, and Andreas Krause. Efficient pure exploration for combinatorial bandits with semi- bandit feedback. In Algorithmic Learning Theory, pp. 805- 849. PMLR, 2021.
10

---

Under review as a conference paper at ICLR 2022
Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. Pac subset selection in stochastic multi-armed bandits. International Conference on Machine Learning, 2012.
Zohar S Karnin. Verification based solution for structured mab problems. Advances in Neural
Information Processing Systems, 29:145-153, 2016.
Emilie Kaufmann and Shivaram Kalyanakrishnan. Information complexity in bandit subset selec-
tion. In Conference on Learning Thheory, pp. 228-251, 2013.
Emilic Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: asymptotically optimal finite-time analysis. In International Conference on Algorithmic Learning Theory, 2012.
Jialian Li, Chao Du, and Jun Zhu, A bayesian approach for subset selection in contextual bandits. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 1884-8391, 2021.
Pierre Perrault, Etienne Boursier, Vianney Perchet, and Michal Valko. Statistical efficiency of thompson sampling for combinatorial semi-bandits In Neural Information Processing Systems, 2020.
William R Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25(3/4):285-295 1933.
Siwei Wang and Wei Chen. Thompson sampling for combinatorial semi-bandit. In International Conference on Machine Learning, 2018.

---

Under review as a conference paper at ICLR 2022
APPENDIX
A GENERAL EXPLORE-THEN- VERIFY FRAMEWORK
Algorithm D Doutlines the general ssplore-then-eee framework (Chen al. 2017).
In this framework, there are several independent procedures, and the k-th procedure is active at time step only if mod 2 O. Each procedure contains two stages: an exploration stage and verification stage. The exploration stage of procedure k: is complete pure exploration algorithm, i.., it outputs the optimal arm with probability least âg (here we choose 6p 0.1). After the exploration stage of procedure & outputs arm, the verification stage of procedure & then tries 2F. Once a verification stage
to verify that the output arm is the optimal arm with confidence (of any procedure) outputs that its input arm is the optimal arm, then all the procedures terminate, and the peelor-then-verfffy framework outputs that arm as the result of pure exploration. We can that all these steps form complete pure exploration algorithm with error constraint 6 (which is different with the complete pure exploration algorithm in the exploration stage with error constraint 6g).
Algorithm 2
framework
1: Input:
Error constraint 5.
2: Init: For any &: 2 1. procedure & contains two stages. In the first stage, it explores with constant error probability 6a 0.1; in the second stage, it tries verify that the output arm of the exploration stage is the optimal arm with error probability 5 2
to pull). 4: If in any procedure k, the output arm of its exploration stage gets through the verification stage,
3: At time step f, if mod 2 0, then procedure l is active (i.c., it can choose
then output that arm and terminate the algorithm (as well any other procedures).
B PROOF OF THEOREM 2
Recall that J = 15* \ S,S S : S S Σ}, and the three events E El & are defined as following.
Yt, J, Σ (B.(t)) pbll N
log (24
N.(t)
EEU
NEU
Vt,k, E J, Σ (t) (((t)) 5
C(..g,t) Σ
iEU N:(t) log( Log(247)
iEU
1og(12((//)
E2,c
(os(t) ps(()) s
M(8.q.t) S
Note that the random variable (f:(t) (4;) is zero-mean and Ni(0) sub- sub-gaussian, and for different i, the random variables (pr(t) - p4)'s 's are independent. Therefore, Σiev (P: - 14) is zero-mean and Eiev Na(e sub-Gaussian. Then by concentration inequality.
Pr
Σ VEU
-a)(
-x)1
log log(24(711200)
<
= 1
N.(t)
IEU
This implies that
Pr( Pr(-Co,c| 5 Σ
<
1
6t
3'
U.
12

---

Under review as a conference paper at ICLR 2022
where the second inequality is because that |J] 2|Z], and the third inequality is because that E. 2 S 2.
Similarly, the random variable (t) (t)) a zero-mean Gaussian random variable with vari- C(6.g.)) and for different i, the random variables (0f (t) (,(t))'ss also independent. Then by concentration inequality,
ance N.(r)
((..0.1) E 1og(22//1/2M000.00000 ()/8) s 2 exxp(- log((4 (0000/og(2477"
Pr
(i(0)))
iEU N.(1)
VEU
((
This implies that
Pri-Eidd $ Σ
8
5
12I
12
12
6t
U.t.k
U.
t
where the second inequality is because that there are totally M(, () sample sets at time step L.
Let (t) Ifs $1. then we know that ( are M(, q, i.i.d.s with real mean
(t) and empirical mean (t).). Therefore
log(12t//))
Pr (p((t) -g(()) - V ((6.9.t)
< 2exp( log(12f//8)) 6t
which implies that
Pr|-E2, - Σ
6t2
3
Now it is sufficient to prove that under event Eo,e A Ere A E2.er the two properties in Theorem
hold. In this proof, we denote M(1) = M(8,g, C(t) C(o, 1), (1) = log (2 /8) and
(1) = (2 q, t))8).
Consider the two cases in Theorem 2
i) When 5 S* in this case, we claim that any arm cannot be pulled if N₁(t) 16 width Lz))) and we will prove this claim by contradiction.
A
For any arm É S* (the proof for arms i E S* is similar), it is pulled at time step I 16 width widtt ((t) then from the description of TS- there exists S # S* At,
and (t) 2
and i E \ S* such that for some k. Ejes 2 Ejes- (²) (which the same as Ejerrs (t) 2 Ejerrs (1), and N₃(t) 2 N:(t) for all j E (S* ( S*). Now let A(l) Ejest,- Noto and B(I) Ejeshs Noo have that
Σ (1)
Σ i0(1) (A(0C())2(()
(5)
JE
JESYS
Σ My (A(1)((()) + ((())((())(()
(6)
JESYS8*
Σ JESYS-
M4 +
km
As.m
Mg +
2
jESYS-
13

---

Under review as a conference paper at ICLR 2022
where Ineq. 5 is because of Ei.ci Ineq. ( is because of Eo,ci Ineq. is because that Vj S S", (t) 2 (t) 16 width C(t) and therefore (((t)C(()aa()) and (A(t)Li(t) <
A
Acm (since q 2 6. we must have that C(t)L2(t) (t)). Similarly, for arms j S* \. S, we have that
Σ
(1)
Σ
i²(()) ((O)(())2(()
JES
JES*
N
Σ
P1
((() ((()C())a(()
JES' S
A
Σ 1
(8)
Σ
A
s.m.
M
P4 +
2
JESTS'
where Incq. is because that Vj E 8t
$ (,,N(()) 2 N,(1) N
1GwidthC())Let A7
This contradicts
with Ejerts (t) 2 Ejesnss (t).
Therefore, we know that the complexity Z satisfies
width C(Z)L2(Z) ((2)222)))
Z
A
EE mm
With C(Z)
log 24 / d² (3q)
(3() (log 34), L2(Z) logg24 and M(Z)
log(122 (1222222)) (5) we have that (note that we require 2 8)
Z 0 H1,c log log( 2) + log
(10g((Z(Z) + log ) 1)
(9)
log
Then we can use the following lemma find an upper bound for complexity Z.
Lemma Given K functions fi (z), ..... fk (z) and K positive values X1, XK. if Vx 2 XA, K (f(x)) < holds for all 1 1 k S K, then for any 2 XR. Xu. Ex fx(r)
Proof. Since XI,..., .......xxx are positive values, for any x 2 Ex Xs. we must have that x 2 X Therefore K fx(x)) x, which implies that
KKf(()) Σ x.
This is the same as Ex fx(x)= < x
To apply Lemma we set fz = Hi,e log Jog"((Z Z2) loz
f2(2) = H1.c log( log
and
log
fz(Z) H1,0 log"
Tog 1 After some basic calculations, we get that X3 9(Hi,c
log
Tog ) X₂
[og([Z] Ha,e) + X3) and X1 = O(H,, (1Z)
((H,e
log
log
Then we know that for Z 2 O(H1,c + log (1,,)) log
log
b H1,c
lox ( fi fi) +
log
[2(Z) [z(2) Z (by Lemma
1h Tog
19 Therefore, This contradicts with Eq.
know that
2 = OHH,, & + log( H.) log
+ Hi,e
(og2((2[
log
ii When 3 * S*: in this case, we consider the probability that Eie (f(()) 2 Eiegis (t()), i.e. super arm S* better than Š in the k-th sample set. Here we denote A(t) Σiesis N.))
B(t) Eiesns M.O)
14

---

Under review as a conference paper at ICLR 2022
Note that E 2 Eiesrs Hi, therefore, under event Ea,es we must have that EiESAs & (t( - E. Px(t) 2 (B))) - Ss d (t() 2 -V)( (t)) Since E (1) - (1) is Gaussian random vari- able with mean Eiesu, P4((t) EiEsis- P4(t) and variance A(t)C(t) + B(t)C(t), we have that (recall that (2, 0²) = PIx=N(u (X 2 x():
Pr
Σ
0((1)2 2
Σ (7(
0, Σ
A:(1)= E
+
iES"LS
iESrS
> (00, (A(E)L(()) - (00))
*( (())(()) (B(()) A(0))) B()C()
[1(1) VA(I) + BB() .0,1
C(t) VA(t) B(t)
(t
2 + 2 C(I) 0,1
3q,
(10)
where Eq. 10 is because that C(t) (h and (()()) 0, 3q (by definition of Φ). This (34)
implies that Pr PriEees es (t) = maxsez Exes (t) (t), (t) < 1 3g.
Note that (t) only depends on Ei,e but does not depend on &1, and Ez.c. Therefore under event
E0 A E1, A E2 we still have that pg(() S 1- - 3q. Also recall that we set M q. 8)
log(12 (8)
which implies V
q. Therefore, by event &2,e, we know that P5(() I pg(()+ 1-3g 3q + < 1 q, i.e. TS-Verify will not stop in this case.
|Iop 1212 /5)
(b.g..)
C EXPERIMENTS
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 E N
Problem 1. For fixed value n, there 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 St, S2. S₁ contains the first base arms and S2 contains the last base arms.
totally 2n base arms. For the first base arms, their
Since there are only two super arms, our TS- Verify can also be used to do pure exploration, i.e., at time step f, if S₁ is the optimal super arm in at least (1 9) (5, t) sample sets, then we output that S₁ optimal; if S₂ the optimal super arm in at least (1 - M) (6. q. 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- TS- Veriff, we always choose q 6.
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. [[a]] We can see that when n increases, the complexity of TS- -errir does not increase lot, while the complexity of CLUCB increases linearly. This accords with our
analysis, since (n)) = 2n (0.8n) linear with (here (n), (n) are the values of H1,c, H2, under the problem instance with parameter n, respectively).
2n 6.25 is a constant but H2,(n)) = 2n (0.8m)7 12.5n is
(2n)²
Then fix 10, and compare the complexity of TS- Verify with CLUCB under different 6. The results (average complexities and their standard deviations) take an average over 20 independent runs, and are shown in Fig. [(b) We see that when 8 is large, the complexity of TS-Verify
15

---

Under review as a conference paper at ICLR 2022
TS-Verify
TS-Verify
2300
Complexity
5000
Complexity
2300
4000
1350
10
15
20
25
53
0.55
0.02
0:01
0.005
0.002
5.001
(a) 8 0.1
(b) n
Figure I: Comparison of TS-Verify and CLUCB
decreases as 5 decreases, and when å small, the complexity of TS- JS-Verify increases as 6 decreases. Moreover, the complexity of TS-Verify always increases slower than CLUCB (when decreases).
This also accords with our analysis. Note that there is term OHH,e log (17) in the complexity
log 1
bound in Theorem Since we choose q = 6, 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 8 from 0. to 0.002. When 8 = 0.002, the term O .. log 1)) becomes the majority term in complexity, therefore the complexity increases when decrease from 0.002 to 0.001.
All the above results indicate that our TS-Verify algorithm outperforms CLUCB
D DISCUSSIONS ABOUT THE OFFLINE ORACLES IN OPTIMAL ALGORITHMS FOR COMBINATORIAL PURE EXPLORATION
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.c., given a set of parameters 01,-.. 0m it can output arg maxger Enes Oi, 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 (Le.. its time complexity is polynomial with m) long this basic offline oracle is efficient.
However, the algorithms (Chen et al. 2017: Jourdan et al., 2021) require efficient and more powerful oracles. Otherwise the time complexity of their algorithms becomes exponential with In (Chen et af.] 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 an exponential time 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, EfficientGaapEli either suffers from exponential time complexity, or requires more powerful offline oracles to solve the above three problems efficiently.
well. The authors apply an approximate version
In (Jurdaan et al. 2021). the best-response oracle used by the X-player has time cost scaled with (3.),, where S. a super arm, N(S)) represents the set of super arms whose cells' boundaries intersect the boundary of the cell of S., and the cell of super arm S, is defined all the possible parameter sets [01. ....... 0m.] in which S, is the optimal super arm. Though the size of N(S)) is always smaller than I, it can still be exponential with Therefore, the CombGame algorithm in (Jourdan et al. I) either suffers from an exponential time complexity, or requires more powerful offline oracles to substitute the origin best-response oracle used by the X-player.
16

---

Under review as a conference paper at ICLR 2022
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 needs exploration the most at time t if aN log universal constant, No is the value N; in the optimal solution Ho.c- From this definition, we can 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 Ho,e. and this achieves the optimal complexity upper bound. However, the basic offline oracle in TS- -S-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 can- tell us which base arm (in these insufficiently learned super arms) needs exploration the most. Therefore, if we want to use more powerful offline oracle in TS-verify to achieve an optimal com- plexity 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 TETTSSeVerr Verify is reduced to O (Ho,e e log }t) 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 one of our future research topics.
(t) is the largest
among the set of base arms, where is some
17


Reviews:
[{"review_id": "wL0kr-E1wDA", "reviewer": "Reviewer_MaqF", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall I found the problem and proposed method interesting.  Carefully exploiting combinatorial action sets is non-trivial extension of BAI and top-k problems, even for linear joint rewards.  And the proposed verification procedure has some novelty in employing Thompson sampling; Thompson sampling methods have been used for other multi-armed bandit problems, but I am not aware of one in an explore-then-verify procedure.\n\nOverall I think the work is good.  Most of my questions/suggestions I believe can be addressed through writing (eg more verbal justification or clarification)\n\nMotivation for not using UCB-style verification method: I think the explanation in the first two paragraphs on page 2 need to be tightened up -- from the description, it sounds like you can simply rescale the confidence bounds used (since the user knows how many times each base arm is sampled and can construct the UCB for each set of arms to be the specified value).  Also, and not clear what it means for the random sample to be independent --independent with respect to what?  The base arms are from independent samples; do the authors mean that when you compute joint confidence regions for subsets of arms, and the subsets overlap (common base arms), that those mean values (for subsets of arms) will be correlated?  That would make sense to me.\n\nBase arm independence – Are the base arms assumed to be independent? (eg the base arms have diagonal covariance matrix)\nActions – if I understood correctly, only base arms can be pulled.  Is there a reason why the agent cannot pull combinations of arms?  Is that motivated from applications?  Also, would the lower/upper bounds depend on that (e.g. could you achieve better sample complexity by using subsets of arms in the verification step?)\n\nOracle models – The authors say multiple times that prior works assume powerful oracles, while the authors consider a weaker oracle, emphasizing that point for why the proposed method is only asymptotically optimal.  I don’t think there was any formal comparison about assumptions of the oracle that makes the differences clear, just statements that other papers considered more ‘powerful’ oracles.  \n\nExperiments – The work is theoretical in nature, and the authors proved sample complexity bounds.  I think it nonetheless is important to have some empirical results at least for some simple environments; for instance it can confirm that there are not large hidden constants in simple cases.  \n\nMinor: \n•\tOrganization suggestion: for readers not familiar with ‘explore-then-verify’ approaches, the word ‘verify’ or ‘verification’ does not appear until the bottom of page two --- it would be helpful to early on explain about why breaking up the pure exploration problem into two parts is helpful.    The authors do describe the basic explore-then-verify algorithm in the appendix; my suggestion here is an earlier, simple verbal explanation in the introduction for why it is a good approach\n•\tFact 1 – wouldn’t the lack of termination cause a problem?\n•\tH_{i,c} notation is properly defined, though a verbal explanation for what they are measuring would be helpful\n", "summary_of_the_paper": "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.   \n\nThis 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. \n\nThe 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).\n", "summary_of_the_review": "Overall I think the work is good.  I think the contribution is significant enough to merit publication.  Most of my questions/suggestions I believe can be addressed through writing (eg more verbal justification or clarification)  I did not carefully check the proofs, but nothing stood out as suspicious.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "mKSQtnm7fg9", "reviewer": "Reviewer_YozJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "For pure exploration, existing works based on UCB approaches, They use 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,  so the UCB approach requires much higher complexity than necessary. To solve this problem, author introduce the Thompson sampling to it.  Compared to these results, the TS-Verify policy uses a totally different approach, and can achieve an asymptotically optimal complexity upper bound as well. TS-based algorithm achieves a better complexity bound than CLUCB in the most general setting. However, since they do not assume the existence of a more powerful offline oracle, so cannot achieve the optimal complexity upper bound. The contributions seems not enough. The paper structure and writing is good.", "summary_of_the_paper": "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. \nThe 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. \n", "summary_of_the_review": "The algorithm works well, but the contribution may not be enough.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "18Wpl1Pn2Eo", "reviewer": "Reviewer_6x9v", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strong points\na) It is the first TS-based framework to solve the verification problem in pure exploration. \n\nb) The verification framework achieves lower complexity. \n\nWeak points\na) The paper mainly emphasizes the lower complexity of TS-verify compared with CLUCB. But CLUCB is a complete pure exploration framework while TS-verify can only determine whether the input is the optimal one. So, I think these two results are not directly comparable. \n\nb) The paper only proposes the TS-based verification framework but not the complete pure exploration algorithm. The authors claim that this verification framework combined with a complete pure exploration algorithm, such as CLUCB, can be used to find the best (super) arm. First, for completeness, I recommend authors include the pure exploration algorithm combined with TS-verify in the paper. Second, the authors should provide the complexity of this full framework. In this framework, does the complexity of CLUCB dominate the full complexity? If so, what is the advantage of the proposed algorithm to solve the pure exploration problem?\n\nc) Since it is the first TS-based algorithm to solve the pure exploration problem, it would be better to provide experimental verifications and comparisons to support the claims. \n\nd) It is a bit strange that the algorithm can go on forever in some cases.\n\n------\nThanks to the authors for the comments. I'm still not convinced by the setting and results. So I would rather keep my score.\n", "summary_of_the_paper": "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. \n\nBenefiting from independent samples of the TS algorithm, the TS-based verification framework achieves lower complexity than the UCB-based one. \n", "summary_of_the_review": "I think the formulated problem is a bit strange which is not a standard pure exploration problem. And the algorithm will not stop if the input arm is not optimal. So I would suggest authors give a complete pure exploration algorithm together with the complexity analysis.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "05K8LyeN6Rj", "reviewer": "Reviewer_TkoG", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n* The analysis of TS-Verify is correct in my view as I don’t see any errors. The techniques used are well-known and a similar analysis works for verification in both vanilla multi-armed bandit as well as the combinatorial bandit problem.\n\nWeaknesses:\n* The sample complexity obtained is in terms of $H_{1,c}$ which is larger than the lower bound that is in terms of $H_{0,c}$. It is said that this is possibly due to not having a powerful offline oracle that is assumed in existing works of [Chen et al 2017] and [Jourdan et al 2021]. But it is not clear to me how the oracles used in those works are useful for the problem considered here. In [Chen et al 2017] the oracle is used to reduce the computational complexity (as opposed to sample complexity) of their algorithm when the set $\\mathcal{I}$ of super-arms has a size exponential in the number of arms; the assumed oracle allows them to identify the best super-arm in $\\mathcal{I}$ given a set of means using polynomial computation in the number of arms. On the other hand, in [Jourdan et al 2021] the oracle is used to solve a max-min zero-sum game between the learner and the environment. There the oracle is assumed to provide the “best-response” allocation for any choice of arm means given by the environment. Other oracles considered in the literature are those used in tracking algorithms such as Track-and-Stop by [Garivier and Kaufmann 2016, http://proceedings.mlr.press/v49/garivier16a.pdf ] which find the optimal arm allocation for identifying the best arm if a given vector is indeed the true set of arm means. More clarification on which oracle and how it can be used for verification would be helpful.\n* The introduction describes at a high level why the analysis of TS is more involved than UCB-type analysis. However, the problem being solved using TS in existing literature is regret minimization. Indeed in works such as [Agrawal and Goyal 2013] and [Kaufmann et al 2012] the analysis of TS required the introduction of technically novel arguments-- Lemma 1 in [Agrawal and Goyal 2013] relates the conditional probability of sampling a suboptimal arm as being directly proportional to the conditional probability of sampling the optimal arm with the coefficient of proportionality decreasing, while Proposition 1 of [Kaufmann et al 2012] shows that the probability of sampling the optimal arm few times must be low by explicitly reasoning about the random number of sub-optimal arm samples taken between successive samples of the optimal arm. On the other hand, the TS analysis in the present paper uses standard concentration arguments, possibly because it is only concerned with verification and not exploration. In the regret minimization case, both objectives need to be simultaneously balanced.\n* At a high level, the motivation as to why a TS approach should be used for the verification subroutine is unexplained. Is it easier to implement than competing approaches, or applicable in more general situations? It is known that TS has shown good empirical performance in minimizing regret [Chapelle and Li 2011, https://papers.nips.cc/paper/2011/hash/e53a0a2978c28872a4505bdb51db06dc-Abstract.html ], however no simulations or real-data experiments were shown to demonstrate a similar benefit in the verification problem by the present paper.\n\nMinor questions / comments:\n* In TS-Verify, why was the Gaussian distribution used in Line 5? I imagine the analysis would hold with a distribution such as Uniform centered at the required non-zero mean with appropriately chosen width. If so, it could be mentioned that the Gaussian was chosen for convenience.\n* In the introduction it is mentioned that Bayesian regret loses many good properties in the frequentist setting. The text after that mentioning that the parameters of the game are chosen in i.i.d. Manner were confusing to me. Could you elaborate more on this, possibly referring to Section 3.1 in [Russo and Van Roy 2013, https://arxiv.org/abs/1301.2609 ].\n* In the analysis of Section 4.2, I felt that using A(t) and B(t) was probably not helpful, using $1/N_i(t)$ would be clearer. When stating that $N_{a*}(t) \\geq N_i(t)$, it could be helpful to remind that this is because of the strategy to pull the arm with a lesser number of observations.\n* It would be easier to use set symmetric difference notation to describe sets like $\\mathcal{J}$.\n\n", "summary_of_the_paper": "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.", "summary_of_the_review": "Pure exploration in bandits is a well-studied problem and Thompson Sampling is a well-known meta-algorithm. The paper provides a TS-based algorithm for best arm verification in MAB (or super-arm verification in combinatorial MAB). While the analysis is correct, more discussion about why the simpler (in comparison to [Agrawal and Goyal 2013] or [Kaufmann et al 2012]) analysis works in this problem would be helpful. Motivation for why TS should be used for verification could be described more, maybe by simulations or by describing its greater applicability. The introduction mentions two broad challenges in the analysis of TS strategy but does not describe at a high level how these challenges are overcome. Due to these shortcomings, I put it below the acceptance threshold.\n\n====== After reading author response, I've increased the score.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers overall thought the problem was worth studying.  However, no reviewer was particularly excited about this work.  The main concern was that the new problem formulation is difficult to compare to prior work. Reviewers felt both more explanation and a deeper detailed comparison would make this a stronger paper.
Decision: Reject