Closing the Computational-Statistical Gap in Best Arm Identification for Combinatorial Semi-bandits
Authors: Ruo-Chun Tzeng
Po-An Wang
Alexandre Proutiere
Chi-Jen Lu
Venue: NeurIPS 2023 poster (2023)
Keywords: best-arm identification; combinatorial semi-bandit; no-regret learning;

Abstract: We study the best arm identification problem in combinatorial semi-bandits in the fixed confidence setting. We present Perturbed Frank-Wolfe Sampling (P-FWS), an algorithm that (i) runs in polynomial time, (ii) achieves the instance-specific minimal sample complexity in the high confidence regime, and (iii) enjoys polynomial sample complexity guarantees in the moderate confidence regime. To our best knowledge, existing algorithms cannot achieve (ii) and (iii) simultaneously in vanilla bandits. With P-FWS, we close the computational-statistical gap in best arm identification in combinatorial semi-bandits. The design of P-FWS starts from the optimization problem that defines the information-theoretical and instance-specific sample complexity lower bound. P-FWS solves this problem in an online manner using, in each round, a single iteration of the Frank-Wolfe algorithm. Structural properties of the problem are leveraged to make the P-FWS successive updates computationally efficient. In turn, P-FWS only relies on a simple linear maximization oracle.

Closing the Computationall-Satiiiicc Gap in Best Arm Identification for Combinatorial Semi-bandits
Ruo-Chun Tzeng
Po-An Wang EECS
EECS
KTH, Stockholm, Sweden cetzzng@kthh..
KTH, Stockholm, Sweden wang9ekth.se
Alexandre Proutiere
Chi-Jen Lu
EECS and Digital Futures KTH, Stockholm, Sweden slepro@kth.se
Institute of Information Science Academia Sinica, Taiwan e illuiis. sinica. edu. tw
Abstract
We study the best arm identification problem combinatorial semi-bandits in the fixed confidence setting, We present Perturbed Frank-Woll Sampling (P-FWS), an algorithm that (i) runs in polynomial time, (ii) achieves the instance-specific mini- mal sample complexity in the high confidence regime, and (iii) enjoys polynomial sample complexity guarantees in the moderate confidence regime. To the best of our knowledge,
for the vanilla bandit problems, algorithm able to achieve (ii) and (iii) simultaneously. With P-FWS, we close the computationallstatiee gap in best arm identification in combinatorial semi-bandits. The design of P-FWS starts from the optimization problem that defines the information-tthorrtiiaa and instance-specific sample complexity lower bound. P-FWS solves this problem in an online manner using, in each round, a single iteration of the Frank-Wa Wolfe algorithm. Structural properties of the problem leveraged make the P-FWS successive updates computationally efficient. In turn, P-FWS only relies on a simple linear maximization oracle.
Introduction
An efficient method to design statistically optimal algorithms solving active learning tasks (e.g.. regret minimization pure exploration in bandits and reinforcement learning) consists in the following two-step procedure. The first step amounts to deriving, through change-of-measun arguments, tight information-tthorrtiicl fundamental limits satisfied by wide class of learning algorithms. These limits are often expressed as the solution of an optimization problem, referred in this paper to the lower-bound problem. Interestingly, this solution specifies the instance-specific optimal exploration process: characterizes the limiting behavior of the adaptive sampling rule any statistically optimal algorithm should implement. In the second step, the learning algorithm is designed so that its exploration process approaches the solution of the lower- problem. This design yields statistically optimal algorithms, but typically requires repeatedly solve the power-boung problem. This method has worked remarkably well for simple learning tasks such as regret minimization or best-arm identification with fixed confidence in classical stochastic bandits [Li87 GCIT GK16), but also in bandits whose arm-to com-tto-veeee to-average reward function satisfies simple structural properties (e-g., Lipschitz, unimodal) [MCP14] WTP21]
The method also provides a natural way of studying the computationaalsstaiiiieea gap KLLM22) for active learning tasks. Indeed, if solving the lower-bound problem in polynomial time is possible, one
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

may hope to devise learning algorithms that are both statistically optimal and computationally efficient. As of now, however, the computational complexity of the lower-bound problem remains largely unexplored, except for simple learning tasks. For example, in the case of best policy identification in tabular Markov Decision Processes, the lower-bound problem is non-convex [AMP1I] and its
complexity and approximability are unclear.
In this paper, we leverage the aforementioned two-step procedure to assess the computational- statistical gap for the best arm identification in combinatorial semi-bandits in the fixed confidence setting. We establish that, essentially, this gap does not exist (a result that was conjectured in [МКК22)). Specifically, we present an algorithm that enjoys the following three properties: (i) it runs in polynomial time, (ii) its sample complexity matches the fundamental limits asymptotically in the high confidence regime, and (iii) its sample complexity is at most polynomial in the moderate confidence regime. Next, after formally introducing combinatorial semi-bandits, we describe our contributions and techniques in detail.
Best arm identification in combinatorial semi-bandits. In combinatorial semi-bandits CBLL2 CTMSP* 15), the learner sequentially selects an action from combinatorial set X' C 1)
When in round t. the action (tt) (t)......... xx (t)) E X is chosen, the environment samples a K K-dimensional vector y(t) whose distribution is assumed to be Gaussian M(,, I). The learner then receives the detailed reward vector x (1) @ (t) where @ denotes the element- product (in other words, the learner observes the individual reward (t) of the arm k if and only if this arm is selected in round f, i.e., (t) = 1). The parameter μa characterizing the average rewards of the various arms is initially unknown. The goal of learner is to identify the best action i' (p)
argmax (x μu) with a given level of confidence 1 - 8, for some > while minimizing the expected number of rounds needed. We assume that the best action is unique and denote by A = { E IR | (x4) = 1} the set of parameters satisfying this assumption. The learner strategy is defined by three components: (i) a sampling rule dictating the sequence of the selected actions; (ii) stopping time defining the last round where the learner interacts with the environment; (iii) a decision rule specifying the action à X' believed to be optimal based the data gathered until
The sample complexity lower-bound problem. Consider the set of 6-PAC algorithms such that for any μ E A. the best action is identified correctly with probability at least 1 ô. We wish to find a d- PAC algorithm with minimal expected sample complexity [T]. To this aim, using classical change- of-measure arguments [GKI6]. may derive lower bound of the expected sample complexity satisfied by any 8-PAC algorithm. This lower bound is given by [u][]] 2 (Hik((6 1 6). The characteristic time (')) is defined as the value of the following problem
(ws, (n- A)2
(n) =sup inf XEAIt(1))
(1)
WEE WEANEA))()))
2
where") Σ (EEEx uy E E kl(a,)) is the KL-divergence between two Bernoulli
distributions with respective means and b, and Alt(μ) (X E A (A( + i" (m)) is the set of confusing parameters. As it turns out (see Lemma 1] (1) is at most quadratic in K, and hence the sample complexity lower bound is polynomial. 1 is concave program over Σ [WTP21]. and a point wt in its solution set corresponds to an optimal allocation of action draws: an algorithm sampling actions according to w and equipped with an appropriate stopping rule would yield a sample complexity matching the lower bound. In this paper. we provide computationally efficient algorithms to solve ! and show how these can be used to devise a 8-PAC best action identification algorithm with minimal sample complexity and running in polynomial time. We only assume that we have access to a computationally efficient Oracle, referred as the LM (Linear Maximization) Oracle, identifying the best action should fe be known (but for any possible μ4). This assumption, made in all previous work on combinatorial semi-bandit (see e.g. there is no computationally, efficient algorithm solving the offline problem argmax (x, 14) with known μr, there is no hope to solve its online version with unknown μ in a computationally efficient manner. The assumption holds for a large array of combinatorial sets of actions (S+03). including m-sets, matchings, thorough discussion).
crucial as indeed,
patts, spanning trees, matroids (refer to [CCG2Ib for a
We present proof in Appendix K for completeness - see also JMKK21 N denotes the (N 1) dimensional simplex.
2

---

The Most-Confusing--arran Parameeer (MCP) algorithm. The difficulty of solving I lies in the inner optimization problem, i.c., in evaluating the objective function:
(1
2)2
Fu(w)=
inf AEAlt(H))
min (w 14) xf(((())
(2)
2
where (w (4) = xec, (w. _ and C. {A E K
(A) x) < 0}. Evaluating F (w) is required to solve (I). but also in the design of an efficient stopping rule. Our first con- polynomial time algorithm able to approximate (w( for any given f and w. The algorithm'ss 's name refers to the fact that by computing Fu(w), we
tribution is MCP coost-Confusig-.. Confusing-Paramettrr)
implicitly identify the most confusing parameter X E arg in A (w, ("-A\"), The design of MCP leverages Lagrangian relaxation of the optimization problem defining (w. (4) and exploits the fact that the Lagrange dual function linearly depends on æ. In turn, this linearity allows us to make use of the Oracle. From these observations, we show that computing (w( boils down to solving two--lay two-player game, for which one of the players can simply update her strategy using the LM Oracle. We prove the following informally stated theorem quantifying the performance of the MCP algorithm (see Theorem for more precise statement).
Theorem 1. For any (w, 1c), the MCP algorithm with precision and certainty parameter O returns F and & satisfying F Fu(Fu(w) S F S (1+ (u 2 calls the LM Oracle is, almost surely, most polynomial in K, c-,, and 0-1
0 and F f===(w (.)...). The number of
The Perturbed Trolf Sampling (P (P-FWS) algorithm. The MCP algorithm allows us solve the lower-bound problem (I) for any given μ.. The latter is initially unknown, but could be estimated, Lork-and-Stop algorithm [GKI6] solving (I) with this plug-in estimator in each round would yield asymptotically minimal sample complexity. It would however be computationally expensive. To circumvent this difficulty, as in [WTP21], our algorithm, P-FWS, performs a single iteration of the Frank Wolfe algorithm for the program ①T) instantiated with an estimator of μ.. To apply the Frank- Wolfe algorithm, P-FWS uses stochastic smoothing techniques to approximate the non-differentiable objective function F' by smooth function. To estimate the gradient of the latter, FWFWS leverages both the LM Oracle and the MCP algorithm (more specifically its second output .). Finally, P-FWS stopping rule takes the form of classical Generalized Likelihood Ratio Test (GLRT) where the estimated objective function is compared to a time-dependent threshold. Hence the stopping rule also requires the MCP algorithm. We analyze the sample and computational complexities of P-WS. Our main results are summarized in the following theorem (refer to Theorem 4 for details).
Theorem 2. For any 8 E (0, 1), P-FWS is 5-PAC, and for any (c, E (0, 1) small enough, its sample complexity satisfies:
EglT] S (t H ( o(1+2)2
(1+2)
(H))-1- ((.,
where H(x)= In(x)) + Inln(x), K, |||||| and A- where Amin = (in (i" (IL) H.). Under P-FWS, the number of LM Oracle calls per round is at most polynomial in 8 and K. The total expected number of these calls is also polynomial.
0 is universal constant, and (ee, is polynomial in - E-1
To the best of our knowledge, P-FWS is the first polynomial time best action identification algorithm with minimal sample complexity in the high confidence regime (when 8 tends to 0). Its sample complexity is also polynomial in K in the moderate confidence regime.
Preliminaries
We start by introducing some notation. We use bold lowercase letters (c.g., x) for vectors, and bold uppercase letter (c.g., A) for matrices. O (resp. @) denotes the element-wise product (resp. sum over Zz). For æ E RRK E N, x² = (e]))E[K] is the i-th element- wiisent-wiseee power of æ. D max || denotes the maximum number of arms part of an action. For any μ E A, we define the sub-optimality (i" (H)
x. 4)) and the minimal gap as 4miu(u) = min 4. (14). P2 (resp. E,) denotes the probability measure (resp. expectation) when the arm rewards are parametrized by μ.. Whenever it is clear from the context, we will drop μ for simplicity, e.g. of notation.
gap of x E X' as (p) (i²())
i' (1)), An (1)),, and Amin = mingzi Age Refer to Appendix A for an exhaustive table
3

---

2.1 The lower-bound problem
Classical change-off of--off---eee measure arguments lead the asymptotic sample complexity lower bound En[r] 2 T (1)))(( - 5) where the characteristic time is defined in ( To have a chance to develop computationally efficient best action identification algorithm, we need that the sample complexity lower bound grows at most polynomially in K. This is indeed the case stated in the following lemma, whose proof is provided in Appendix
Lemma 1. For any la E A, T (1) AKDA (14)-2
We will use first-order methods to solve the lower-bound problem, and to this aim, we will need to evaluate the gradient w.r.t. w of (m(w,t)) pt). We apply the envelop theorem [WTP2T] to show that for (w, E+ x A,
V Wul 14) (μ (
where Σ+ En RRRK
2000 X (x) xedmmi ( and cl (Cx) is the closure of C.
(refer Lemma 19
Appendix G.2
2.2 The Linear Maximization Oracle
As mentioned earlier, we assume that we have access to computationally efficient Oracle, referred to as the LM (Linear Maximization) Oracle, identifying the best action if μ is known. More precisely, as in existing works in combinatorial semi-bandits [KWA+ 14, PPVI9 PBVP20), we make the following assumption.
Assumption 1. (i) There exists polynomial algorithm identifying i (v) any v E RK (ii) X is inclusion-wise maximal, i.e., there no x, x' X s.t. æ (iii for each k E [K], there exists X such that Fę = 1; (iv) X 2 2.
Assumption Tholds for combinatorial sets including m-sets, spanning forests, bipartite matching, s-t paths. For completeness, we verify the assumption for these action sets in Appendix In the design of our MCP algorithm, we will actually need solve for some E K the linear maximization problem max (xx, v) over X \ {&" [: in other words, will probably need to identify the second best action. Fortunately, this can be done in computationally efficient manner under Assumption The following lemma formalizes this observation. Its proof, presented in Appendix J is inspired by Lawler's 's m-best algorithm 72.
[
Lemma 2.
Let RKK and E X. Under Assumption 1 there exists an algorithm that solves max ex fxx (w, x²) by only making at most D queries to the LM Oracle.
3 Solving the lower bound problem: the MCP algorithm
Solving the lower bound problem first requires evaluate its objective function F2 (w) A naive approach, enumerating [w (1) for all x E X {i*}, would be computationally infeasible. In this section, we present and analyze MCP, an algorithm that approximates Fu(w) by calling the Oracle number of times growing at most polynomially in K.
3.1 Lagrangian relaxation
The first step towards the design of MCP consists in considering the Lagrangian relaxation of the optimization problem defining fa (we μ4) = infxec, (w, (μ-x)² (see e.g., [BV04 Vis21). ). For any (w.Hu) Σ+ x A and x * i", the Lagrangian Lu.u and Lagrange dual function Iu., of this problem defined as, Va 2 0.
(u, w (1 X)2 + aa x. A) and ( a)
inf Cu. (h, XER
2
respectively. The following proposition, proved in Appendix C.I provides useful properties of Iw.. Proposition Let (w, (1) E F. x A and x E X' (n)). (a) The Lagrange dual function is linear in x. More precisely, Iw Iw (2, a) (c,,u(a) + (a),

---

where (w) = a (p- -00---w--,0 _w (p)) and lu (a) -a (ut gw o (1k - 22" 22" (H))) (b) (u ar, -) is strictly concave (for any fixed x)).
(c) (m(w; (o) maxx20 g (2c, 0x) is atlained by oz (arii (1)
Am(())
(d)
[ S Lu 4D K || ww'll
From Proposition
D (c), strong duality holds for the program defining (wo and we conclude:
F3 [w)
min max Iw (x. a)..
(w( can henee be seen the value in two-player game. The aforementioned properties of the Lagrange dual function will help to compute this value.
3.2 Solving the two-player game with no regret
There is a rich and growing literature on solving zero-sum games using no-regret algorithms, see for example [RS33] ALLWI8 DFG2I [ODS2T]. Our game has the particularity that the x æ-player has a discrete combinatorial action set whereas the a-player has a convex action set. Importantly, for this game, we wish not only estimate its value F (w: but also an equilibrium action De such that (w( = max Pe (Te, a). Indeed, an estimate of Te will be needed when implementing the Frank-Wolfe algorithm and more specifically when estimating the gradient of Fj. (w). To return such an estimate, could think of leveraging results from the recent literature on last-iterate convergence, see e.g. [P19 GPDO20 LNP W 2L2221 APFS22
23 However, most of these results concern saddle-point problems only, and are not applicable in our setting. Here, we adopt much simpler solution, and take advantage of the properties of the Lagrange dual function Bu, a) to design an iterative procedure directly leading to estimates of (Fμ (w), (w), xe). In this procedure, the two players successively update their actions until a stopping criterion met, say up to the V-th iterations.
The procedure generates a sequence ((x(*), ( Iiags, and from this sequence, estimates (F, #) of (w), ).). The details of the resulting MCP algorithm are presented in Algorithm
æ-pllaye. We use a variant of the follow-the-Perturbee-- The a-player updates her action as follows:
(FTPL) algorithm
Han57 KV05.
Z
1mn 2 ))
n-1 Σ Ew (a (m)
2n
x argmin 2f
Σ Iw gw a (m))
+
argmin 24
17n
where 2n is a random vector, exponentially distributed and with unit mean (fZn)n21 are ii.d.). Compared to the standard FTPL algorithm, vary learning rate 7, over time to get anytime guarantees (as we do not know a priori when the iterative procedure will stop). This kind of time- varying learning rate also used in [Neu13) with similar motivation. Note that thanks to the linearity of fu and Lemma 2 the x--llaye update can be computed using at most D calls to the LM Oracle.
a-player and MCP outputs. From Proposition 1 [= 14) max Iw (ar, a). This suggests that the a-player can just implement a best-response strategy: after the x-player action (!!)) is selected, the a-player chooses (") (0())) (a (-)) This choice ensures that fa.-> (w, p1)
(m)
Iw u (x)()) (n)), and suggests natural outputs for MCP: should stops after N iterations, it can return F min (x((), (")) and â E argmin (x(() (")).
Stopping criterion. The design of the MCP stopping criterion relies on the convergence analysis and regret from the x--layer perspective of the above itcrative procedure, which we present in the next subsection. This convergence will be controlled by l (at) and its upper bound Lu, derived in Proposition [ Introducing Cą = (u (4 ( K + 1)+ 1/2()-1)22), the MCP stopping criterion is: Vn > co + (ccF)). Since vn strictly increases with and since F > Fy(w), this criterion ensures that the algorithm terminates in finite number of iterates. Moreover, as shown in the next subsection, it also ensures that å returned by MCP an (1 + appapoooxinitoo of (y((w) with probability at least 1 - 0.
5

---

Algorithm 1: (c, (CC.0)-CP(w..)
initialization: n ===1, 00, co = w (4 K(n (1))
+1 + vn((0-1//2)
while (n [n=1] or (n > and v S co + c)((cF)) do
Sample nn exp(1) K and set f/- / 1(In K + 1)/(44I
((1) f- argmin [mm=1 Iw S (w alm)) + (2 x)) /ma) (ties broken arbitrarily);
(()) t argmax Iw (x)")) (n(1m),))))))) (uniqueness ensured by Proposition (c));
( (a(()) < F then (f, () - (a (al)),, xx()));
4- n 1;
end
return (F,
3.3 Performance analysis of the MCP algorithm
We start the analysis by quantifying the regret from the x-player perspective of MCP before its stops. The following lemma is proved in Appendix C.3
Lemma 3. Let N N. Under (C.00)MMP(w.,
P
1 N
Σ
Iw (ax ,a(x))
min afe""
Σ
Io (z, (((1))
Co VN
2
Observe that on the one hand,
N
Iw ( (n) 2 min ( a(()) ) =
(4)
nE[N]
always holds. On the other hand, if xe E argmin max Iw Iu a),, then have:
N Bw (xx, (n))) S Σ
N
1
min Σ a=1
Iw (Ke, (n))) I max Iw (x:e at) = Fu(w).
(5)
N 20
N
a20
n=1
We conclude that for N such that VN 2
ca(l+e) Lemma together with the inequalities ef
and 5 imply that f (w(w) I
holds with probability at least - 0. Hence
14c
P (1+e))))) 2 8. From this observation, we essentially deduce the following theorem, whose complete proof is given in Appendix C.2
Theorem 3. Let e 1), Under Assumption A for any (w p1) E E4 x A, the (c, (w, p1) algorithm outputs (F, 2) satisfying P Fu(()) s (L+))))(())) > 0 and F max.>0 Iue.u (., a). Moreover, the number of LM Oracle calls the algorithm does almost surely at O [1lll || 11 H² D" In iuo-1
20++)22 FF
most
Falwy
4 The Perturbed Frofk-Wolfe Sampling (P-FWS) algorithm
To identify an optimal sampling strategy, rather than solving the lower-bound problem in each round as Track-and-Ste Stop algorithm would [GK16], we devise F-FWS, an algorithm that performs single iteration of the Frank- Wolfe algorithm for the lower-bound problem instantiated with an estimator of This requires us to first smooth the objective function Fw( = min fær (w,,, μ1) (the latter not differentiable at points w where the min is achieved for several sub-optimal actions æ:). To this aim, we cannot leverage the same technique as in [WTP2]], where r-subdifferential subspaces are built from gradients of [n (t). These subspaces could indeed be generated by a number of vectors (here gradients) exponentially growing with K. Instead, to cope with the combinatorial

---

decision sets, P-FWS applies more standard stochastic smoothing techniques as described in the next subsection. All the ingredients of P-FWS are gathered in $4.2 By design, the algorithm just leverages the MCP algorithm as subroutine, and hence only requires the IMM Oracle. In $4.3 we analyze the performance of P-FWS.
4.1 Smoothing the objective function F2
Here, we present and analyze a standard stochastic technique to smooth a function c. In P-FWS, this technique will be applied to the objective function = Fu.. Let $ IR H R be a concave and (-Lipschitz function. Assume that the set of points where &b is not differentiable is of Lebesgue- measure zero. To smooth L we can take its average value in a neighborhood of the point considered, see c.g. [FKMO5]. Formally, we define the stochastic smoothed approximate of & as:
(w) Ez Unitor((()) ( + n)]],
(6)
where Bg - {v E RK : ||l|| < 1} and ry E (0, minke[K] wa). The following proposition lists several properties of this smoothed function, and gathers together some of the results from 22 see Appendix[[] H for more details.
Proposition 2. For any w E+ and n E (0, min wx). Dn satisfies: (i) ((w) npt - $ S
((w); (i) p.. = EZ- (V / + n]]]; (iti) T. is eK -smooth (iv) if > n/ > 0,
then (w) (.)(w).
Note that with (i), we may control the approximation error between o, and & by 17 (ii) and (iii) ensure the differentiability and smoothness of é,,, respectively. (iii) is equivalent to (w(w') v (VV)) w' - w) EK
2n || - w'll.. Yw,w' E Σ.. Finally, (iv) stems from the concavity of Φ, and implies that the value (w,(w) monotonously increases while 1y decreases, and it is upper bounded by ((w) thanks to (i). The above results hold for + F₁ Indeed, first it is clear that the definition (2) of F₁ can be extended to RK; then, it can be shown that Fj is Lipschitz-continnn and elmost-everywhere differentiable- - refer to Appendices and H for formal proofs.
4.2 The algorithm
Before presenting P-FWS, we need to introduce the following notation. For 2 1, k E [K]. we define
(t) Σ1 (1)x(5) = 1}. (t) (t)t))t, and (t) E.=1 yn (s) = 1} (()
when No 0.
Sampling rule. The design of the sampling rule is driven by the following objectives: (i) the empirical allocation should converge to the solution of the lower-bound problem (T). and (ii) the number of calls the LM Oracle should be controlled. To meet the first objective, updates to plug an accurate estimator of fu in. The accuracy of our estimator will be guaranteed by alternating between forced exploration and FW update sampling phases. Now for the second objective, we also use forced exploration phases when in a Frank-Wore of calls to the LM Oracle predicted by the upper bound presented in Theorem BJs too large. In view of Lemma I and Theorem 3 this happens in round & if ja 1)ll or A (fa(t - 1)) is too large. Next, we describe the forced exploration and Frank- Wolfe update phases in detail.
need in the Frank-
update, the required number
Forced exploration. Initially, P-FWS applies the LM Oracle to compute the forced exploration set Xo {i' k E [K]], where eg is the K K-dimensional vector whose k-th component is equal to one and zero elsewhere. P-FWS then selects each action in Xo once. Note that A Assumption I (iii) ensures that the k-th component of i' (ex) is equal to one. In turn, this ensures that X, is [K] covering set, and that playing actions from Ng is enough to estimate μ.. P-FW5 starts an exploration phase at rounds i such that /t||/ is an integer or such that the maximum of 4min (ja(t - 1) and [/ - 1o is larger than vt ff-1. I. Whenever this happens, P-FWS pulls each x E X once.
Frank- Wolfe updates. When in round f, the algorithm is not in forced exploration phase, it im- plements an iteration of the Frank- Wolfe algorithm applied to maximize the smoothed function Fa(e-1)-n (wt(t 1)) Ez~Unifomm( B2) (F) () 1) + Z)] The sequence of parameters (m he2 is chosen to ensure that 77 chosen in ming Wa (t)), and hence w(t - 1) 2 RK. Also note that in round where the algorithm is not in forced exploration phase,
7

---

Algorithm 2: P-FWS (f(ee Dt, ne, Pt, (c)
initialization:
for k -1,1.... ,...., do
Xo + arx œ) (tie broken arbitrarily)
end
Sample æ E Xg in round-robin manner for 4|2o] rounds; update (4(4 and (41 1| 1,... do //| or m (fa(t 11)- - - 1) vt then Sample each E No once, update (t) and (t). and i t ++ [2o] - 1;
for
else
Compute V PF((c-1).m (0 (1 1)) by (pr, MMC algorithm;
xxt) + 8" (F m) (wt(t - 1))
Sample m1) and update (u(() and ((); end
if max min ((((t) 11)(t)) S Vt then
F + (e,, 5/12) (MC)()()),(())
t > (1 + tt) 3 (t. |ل26 6) then break;
end
return i (f((t));
by definition miiu (pa( 1)) 0. This implies that ju(t 1) A and that Fp(t-1) and F (w(t 1)) are well-defined. Now an ideal FW update would consist in playing an action (VFp(t- (+(t - 1))) = argmax (VF (w - 1)), æ²), see e.g. [Jag Unfortunately, we do not have access to FF (w
(w - 1)). But the latter can be approxi- mated, suggested in Proposition 2 (ii) by V 11)m.)) (w 1)) > Vian. (w(t
1) + nh 2 f(( - 1)), where ",,..,, , idd Uniform B2). &m is the action return by (Pe, (.)00.)MMP((( 1) 2 mm( 1)). P-FWS uses this approximation and the LM Oracle 1)) (#(t-1))
to select the action: xt) E i" (VP (a((t
The choices of the parameters Te, ni.
Pr and Og do matter. The impacts the sample complexity and should converge to as t + oo so that Fu (w) + (w) at any point E E4 (this is consequence of Proposition 2 (i)())). should not decay too fast however as it would alter the smoothness of Fy.m- We will show that should actually decay as 1/Vt. (Re, Pt, 0c) impact the trade-off between the sample complexity and the computational complexity of the algorithm. We let nt + oo and (pr, 0.) + as + oo so that
for any (w, x) E E x X. Stopping and decision rule. As often in best arm identification algorithms, the P e-FWS stopping rule takes the form of GLRT:
Wypmm n. (w) Fu (w), x
the 8
1 ))) max { (A(1)) ,1700) S VI. (1-4111) (1)))1)))))))
T= == inl 1> 1|%
1+
where et E Ry0, F. is returned by the (er, (e..8/t9-MMC (M)())))((((())))))))))))))))))) algorithm. The function 3 satisties
W 2 1, (t()))(w(t) 2 B(t,5)) (P)())))(tt)) * i" (+4) 8),
(8)
C2t
Ee, 02 0: W> e e ((1 < In
Examples of function 3 satisfying the above conditions can be found in [GK JP20 KK21]. The condition (8) will ensure the d-correctness of P F-FWS, whereas (9) will control its sample complexity. Finally, the action returned by P-FWS is simply defined as i (((T)). The complete pseudo-code of P-WWS is presented in Algorithm
Our Julia implementation could be found at http://ggthhbbcccocmc/e///////// Peruubeedww

---

4.3 Non-asymptotic performance analysis of P-FWS
The following theorem provides an upper bound of the sample complexity of P-FWS valid for any confidence level 8, as well as the computational complexity of the algorithm.
Theorem 4. Let μ E A and E (0, (0.1). P-FWS is parametrized using
(c,,T,, Re, Pt, 01) = ( 1
[t
1 16t tteve)
(10)
then (i) the algorithm finishes in finite time almost surely and Pu + i' (nI) S 6; (ii) its sam-
ple complexity satisfies PA [lim sups bnt S (T))
and for any e, E (0, with
E <
mi
22
mm
D³ 1ell
K
(1+
1
402
21+
E I (H) 6e
H
+ (),,
3
(T)
6e
where H(x) In + Inln and (E),E) E) (refer to (34 for detailed expression) is polynomial in
c1, -' E,,,,,, K. || and (1) (iii) the expected number of LM Oracle calls is upper bounded by a polynomial in 0 K. || and Ami (11)-1
The above theorem establishes the statistical asymptotic optimality of P-EWS since it implies that lim sups-sn [u[T]/ (n(1/)) < (1 + (T"(TT"())
6c). This upper bound matches the sample
complexity lower bound ① when + 0 and é + O.
Proof sketch. The complete proof of Theorem is presented in Appendix D
(i) Correctness. To establish the d-correctness of the algorithm,
introduce the event 9 under which Fr. computed by (er, 0/(2)) JMCP (i)),, (t))., is an (1 + e.)-approximation of Fa(t) (+) in each
round 4|%] + 1. From Theorem we deduce that IP [99] S 21=4|/ol+1 8 8/t² < 8/ R/4. In view of this implies that P + i' (H)] < 5.
(ii) Non-asymptotic sample complexity upper bound. Step 1. (Concentration and certainty equivalence) We first define two good events, e(1) and e! e(2) corresponds to the event where ju()) close to μe, and its occurrence probability can be controlled using the forced exploration rounds and concentration inequalities. Under E."), the selected action xxt) close to the ideal FW update. Again using concentration results and the performance guarantees of MCP given in Theorem
3 we can control the occurrence probability of c Overall, we show that Σ P. pn n ) 30. To this aim, we derive several important continuity results presented in Appendix G These results essentially allow us to study the convergence of the smoothed FW updates as if the certainty equivalence prineiple held, i.e., if (t()) μ.
Step 2. (Convergence of the smoothed FW updates) We study the convergence assuming that (E(") n
holds. We first show that Fuom is f-Lipschitz and smooth for e = 2D | ||]| por see Appendices and Then, in Appendix we establish that the dynamics of d = max Fm(w))
(()) [T=11 + xxx) + Observe that, mentioned earlier, 1/ / is indeed the optimal scaling choice for Th. We deduce that after a certain finite number Tj of rounds, di is sufficiently small and max
satisfy to. S (t 1)
(f((t)= -1)((()))))))))))))))))))))))))) S Vi.
Step 3. Finally, we observe that [r] I Ti + Σin,, Pu[IF, s (1++)))( =
E Pr (ee))) n and show that the second term in the r.h.s. in this inequality is equivalent to T* (#) In(1/5) as 5 + 0 using the property of the function 3 defining the stopping threshold and similar arguments as those used in GK16//TP2
(ii)) Expected number of LM Oracle calls. The MCP algorithm is called compute F, and to [t) (aax())((((((())))))
vt. Thus, from Theorem 3 and Lemma[]] [] the number of LM Oracle calls per-round is a polynomial in t and K. As the Fy [r] is polynomial (in In 5-1, K, ||llog and =m) the expected number of LM Oracle calls is also polynomial in the same variables.
perform the FW update only in rounds t such that max A (f(())=1

---

Related Work
We provide an exhaustive survey of the related literature Appendix To summarize, to the best of our knowledge, CombGame []MK22]] is the Late-of-the-art algorithm for BAI in combinatorial semi-bandits the high confidence regimes. A complete comparison to P-FWS is presented in Appendix B CombGame
initially introduced in [DKM19] for classical bandit problems. There, the lower- bound problem casted as a two-player game and the authors propose to use no-regret algorithms for each player solve it. [JMKK21] adapts the algorithm for combinatorial semi- bandits, and provides a non-asymptotic sample complexity upper bound matching (T) asymptotically. However, the resulting algorithm requires to call an oracle solving the Most-Confusing- Confusing-Parramterr problem as our MCP algorithm. The authors of [JMKK21] conjectured the existence of such a computationally efficient oracle, and we establish this result here.
Conclusion
In this paper, we have presented P-FWS, the first computationally efficient and statistically optimal algorithm for the best arm identification problem in combinatorial semi-bandits. For this problem, we have studied the computational-statitiine trade-off through the analysis of the optimization problem leading to instance-specific sample complexity lower bounds. This approach can be extended to study the computtaional-ssttiiiiii with underlying structure (e.g. linear bandits (DMSV20 [JP20), or RL in linear / low rank MDPs [AKKS20)) Most results on these problems are concerned with statistical efficiency, and ignore computational issues.
gap in other learning tasks. Of particular interest are problems
Acknowledgments and Disclosure of Funding
We thank Aristides Gionis and the anonymous reviewers for their valuable feedback. The research is funded by ERC Advanced Grant REBOUND (834862), the Wallenberg Al, Autonomous Systems and Software Program (WASP), and Digital Futures.
References
[AAS Kenshi Abe, Kaito Ariu, Mitsuki Sakamoto, Kentaro Toyoshima, and Atsushi Iwasaki. Last-iterate convergence with full-and noisy-information feedback in two-player zero-sum games. In Proc. of AISTATS, 2023.
[AKKS20] Alckh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank mdps. In Proc. of NeurIPS, 2020.
[ALLW18] Jacob Abernethy, Kevin A Lai, Kfir Y Levy, and Jun-Kun Wang. Faster rates for convex-concave games. In Proc. of COLT, 2018
[AMP21] Aymen Al Marjani and Alexandre Proutiere. Adaptive sampling for best policy identification in markov decision processes. In Proc. of ICML, 2021.
[APFS22] Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. last-iterate convergence beyond zero-sum games. In Proc. of ICML, 2022.
[BBGS1]] André Berger, Vincenzo Bonifaci, Fabrizio Grandoni, and Guido Schäfer. Budgeted matching and budgeted matroid intersection via the gasoline puzzle. Mathematical Programming. 2011.
[BGK22] Antoine Barrier, Aurélien Garivier, and Tomáš Kocák. A non-asymptotic approach to best-arm identification for gaussian bandits. In Proc. of AISTATS, 2022.
[BLM13] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013.
10

---

[BV04] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[CBL06] Nicolo Besa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[CBL12] Nicolo and System Sciences, 2012.
and Gábor Lugosi. Combinatorial bandits. Journal of Computer
[CCG21a] Thibaut Cuvelier, Richard Combes, and Eric Gourdin. Asymptotically optimal strategies for combinatorial cani-bandits in polynomial time. In Proc. of ALT, 2021.
[CCG21b] Thibaut Cuvelier, Richard Combes. and Eric Gourdin. Statistically efficient, polynomial-ting algorithms for combinatorial semi-bandits, Proc. of SIGMETRICS. 2021.
[CGL16] Lijie Chen, Anupam Gupta, and Jian Li. Pure exploration of multi armed bandit under matroid constraints. In Proc. of COLT, 2016.
[CGL+ + 17] Lijie Chen, Anupam Gupta, Jian Li, Mingda Qiao, and Ruosong Wang. Nearly optimal sampling algorithms for combinatorial pure exploration. Proc. of COLT, 2017.
[CLK 14] Shouyuan Chen, Tian Lin, Irwin King, Michael R Lyu, and Wei Chen. Combinatorial pure exploration of multi-armed bandits. In Proc. of NeurIPS, 2014.
[CMP17] Richard Combes, Stefan Magureanu, and Alexandre Proutiere. Minimal exploration in structured stochastic bandits. In Proc. of NeurlPS. 2017.
[CTMSP+ 15] Richard Combes, Mohammad Sadegh Talebi Mazraeh Shahi, Alexandre Proutiere, et al. Combinatorial bandits revisited. In Proc. of NeurlPS, 2015.
[DBW12] John C Duchi, Peter Bartlett, and Martin Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal on Optimization, 2012.
[DF221] Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. In Proc. of NeurlPS, 2021.
[DKC21] Yihan Du, Yuko Kuroki, and Wei Chen. Combinatorial pure exploration with full- bandit or partial linear feedback. In Proc. of AAAI, 2021.
[DKM19] Rémy Degenne, Wouter M Koolen, and Pierre Ménard. Non-asymptotic pure explo- ration by solving games. In Proc. of NeurlPS, 2019.
[DMSV20] Rémy Degenne, Pierre Ménard, Xuedong Shang, and Michal Valko. Gamification of pure exploration for linear bandits. In Proc. of ICML, 2020.
[DP19] Constantinos Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. Proc. of ITCS, 2019.
[FKM05] Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without gradient. In Proc. of SODA, 2005.
[FKV14] Eugene A Feinberg, Pavlo O Kasyanov, and Mark Voomeveld. Berge's maximum the- orem for noncompact image sets. Journal of Mathematical Analysis and Applications, 2014.
[GC11] A. Garivier and O. Cappé. The KL-UUCB algorithm for bounded stochastic bandits and beyond. In Proc. of COLT, 2011.
[GH16] Dan Garber and Elad Hazan. A linearly convergent variant of the conditional gra- dient algorithm under strong convexity, with applications to online and stochastic optimization. SIAM Journal on Optimization, 2016.

---

[GK16] Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Proc. of COLT. 2016.
[GPDO20] Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman Ozdaglar. Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems. In Proc. of COLT, 2020.
[H+ 16] Elad Hazan et al. Introduction online convex optimization. Foundations and Trends@ in Optimization, 2016.
[an57]] James Hannan. Approximation to bayes risk in repeated play. Contributions the Theory of Games, 1957.
[HK12] Elad Hazan and Satyen Kale. Projection-fiee online learning. In Proc. ICML, 2012.
[Jag 13] Martin Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In Proc. of ICML, 2013.
[JMK221] Marc Jourdan, Mojmír Mutný, Johannes Kirschner, and Andreas Krause. Efficient pure exploration for combinatorial bandits with semi-bande feedback. In Proc. of ALT, 2021.
[JP20] Yassir Jedra and Alexandre Proutiere. Optimal best-arm identification in linear bandits. In Proc. of NeurlPS, 2020.
[KCG16] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best-arm identification in multi-armed bandit models. JMLR, 2016.
[KK21] Emilie Kaufmann and Wouter Koolen. Mixture martingales revisited with applica- tions sequential tests and confidence intervals. JMLR, 2021.
[KLLM22] Daniel Kane, Sihan Liu, Shachar Lovett, and Gaurav Mahajan. Computational- statistical gap in reinforcement learning. In Proc. of COLT, 2022.
[KJJ++0] Julian Katz-Samuels, Lalit Jain, Kevin Jamicson, et al. An empirical process approach to the union bound: Practical algorithms for combinatorial and linear bandits. In Proc. of NeurIPS, 2020.
[KTAS12] Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. Pac subset selection stochastic multi-armed bandits. Proc. of ICML, 2012.
[KV05] Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 2005.
KWA+ + 14] Branislav Kveton, Zheng Wen, Azin Ashkan, Hoda Eydgahi, and Brian Eriksson. Matroid bandits: fast combinatorial optimization with learning. In Proc. of UAI. 2014.
[Lai87] Tze Leung Lai. Adaptive treatment allocation and the multi-armed bandit problem. The annals of statistics, 1987.
[aw72]] Eugene I. Lawler. A procedure for computing the k best solutions to discrete op- timization problems and its application the shortest path problem. Management science, 1972.
[LNP+21] Qi Lei, Sai Ganesh Nagarajan, Ioannis Panageas, al. Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes. In Proc. of AISTATS, 2021.
[MCP14] Stefan Magureanu, Richard Combes, and Alexandre Proutiere. Lipschitz bandits: Regret lower bounds and optimal algorithms. In Proc. of COLT, 2014.
[Neu15] Gergely Neu. First-order regret bounds for combinatorial semi-bandits. In Proc. of COLT, 2015.
12

---

[Oka73] Masashi Okamoto. Distinctness of the eigenvalues of a quadratic form in a multivariate sample. The Annals of Statistics, 1973.
[PBVP20] Pierre Perrault, Etienne Boursier, Michal Valko, and Vianney Perchet. Statistical efficiency of thompson sampling for combinatorial semi-bandits. In Proc. of NeurIPS, 2020.
[Per22] Pierre Perrault. When combinatorial thompson sampling meets approximation regret. In Proc. of NeurlPS, 2022.
[PPV19] Pierre Perrault, Vianney Perchet, and Michal Valko. Exploiting structure of uncertainty for efficient matroid semi-bandits. In Proc. of ICML, 2019.
[RG96] Ram Ravi and Michel X Goemans, The constrained minimum spanning tree problem. Scandinavian Workshop on Algorithm Theory. Springer, 1996.
[RS13] Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In Proc. of NeurlPS, 2013.
[S [S+03) Alexander Schrijver et al. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer, 2003.
[SN20] Arun Suggala and Praneeth Netrapalli. Follow the perturbed leader: Optimism and fast parallel algorithms for smooth minimax games. In Proc. of NeurlPS, 2020.
[Vis21] Nisheeth K. Vishnoi. Algorithms for Convex Optimization. Cambridge University Press, 2021.
[WLZL21] Chen-Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence in constrained saddle-point optimization. In Prof. of ICLR, 2021.
[WTP21] Po-An Wang, Ruo-Chun Tzeng, and Alexandre Proutiere. Fast pure exploration via wolfe- In Proc. of NeurIPS, 2021.
[ZODS21] Tom Zahavy, Brendan O O'Donoghue, Guillaume Desjardins, and Satinder Singh. Reward is enough for convex mdps. In Proc. of NeurIPS, 2021.
13


Reviews:
[{"review_id": "g3KHdmgxlH", "reviewer": "Reviewer_Vkf2", "summary": "The paper introduces a computationally efficient algorithm, P-FWS (Perturbed Frank-Wolfe Sampling), designed for best arm identification in Combinatorial semi-bandits. This algorithm operates in polynomial time and offers minimal sample complexity guarantees or polynomial sample complexity, depending on the problem regime. P-FWS is an online estimation algorithm that aims to achieve the information-theoretic lower bound at each stage. It leverages the Frank-Wolfe optimization routine as its core component, relying on linear maximization at each step. Overall, the paper presents an innovative and efficient approach to address the best arm identification problem in Combinatorial semi-bandits.", "questions": "Would this paper have any significance or relevance to the part of the bandit literature that focuses on tracking the lower bound and sampling based on such lower bound estimations, which are often computationally infeasible?", "limitations": "No potential negative societal impact discussed.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "One strength of the paper lies in its exploration of a novel and important problem within the bandit literature. The utilization of Perturbed Frank-Wolfe as the central algorithm for estimating the lower bound is a unique and valuable contribution that has the potential to complement and enhance existing works in the field. The paper showcases strong theoretical rigor by providing detailed proofs for all claims, ensuring the reliability and robustness of the presented findings. Overall, the paper's innovative problem formulation and theoretical foundation make it a valuable addition to the broader bandit literature.", "weaknesses": "One weakness of the paper is its challenging readability and navigation. The excessive use of definitions, constants, and interruptions in the flow of the paper makes it difficult to understand and follow. This overload of information can overwhelm the reader and hinder comprehension.\n\nFurthermore, the practical motivation and real-world use cases of the proposed algorithms are discussed in a limited scope. It would be beneficial to expand on the potential applications and provide more examples of how such algorithms can be applied in real-world scenarios.\n\nAdditionally, the absence of simulations in the main paper is notable. Although the paper highlights the computational efficiency of the proposed algorithms, there is a lack of performance comparison with other non-efficient methods. Including such comparisons would provide valuable insights into the comparative advantages and disadvantages of the proposed approach.\n\nOverall, addressing these weaknesses would enhance the clarity, applicability, and overall impact of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your careful review and feedback.\n\nAbout the presentation and readability, thanks for your feedback! We had chosen to write a long introduction to summarize all the ideas and contributions of the paper, and to help the reader understand the paper structure. This “unconventional” presentation may have been confusing. We will revert to a more classical and simplified structure. \n\nRegarding the practical motivation, we did not mention many of them because combinatorial bandits have been extensively studied and applied in the past. In particular, applications of combinatorial semi-bandits [11, 12, 14, 16, 23, 36, 43, 50] (references are those from the supplementary material) include: \n * The online ranking problem [23] of identifying the $m$ most relevant (out of a total of $K$) items can be modeled in our setting with $m$-sets or $m$-permutations as the decision set.\n * The routing problem [14, 43] of finding the routing tree with the lowest expected latency corresponds to our case with the set of all possible spanning trees in an ISP (Internet Service Provider) network as the decision set.\n * The loan-assignment problem [43], which aims to identify the matching between the lending institute and the lenders such that the expected paid rate is the highest, can be formulated by setting the decision set as the set of all possible perfect matchings in a bipartite graph.\n * The path planning problem [36] of finding the path from an origin $s$ to a destination $t$ with minimal expected traveling time can be modeled by using the set of all possible $s$-$t$ paths in the given directed acyclic graph as the decision set.\n\nWe will cite a few of these applications in the final version of the paper.\n\nAbout your question: \n> Would this paper have any significance or relevance to the part of the bandit literature that focuses on tracking the lower bound and sampling based on such lower bound estimations, which are often computationally infeasible?\n\nIndeed, this is exactly what we are addressing in this paper. For the case of combinatorial bandits, the problem specific lower bound solves an intricate optimization problem whose level of complexity was so far unknown. We prove that we can solve this problem in polynomial-time (this is the first result of this kind). As a consequence, we are able to devise an algorithm that tracks the lower bound in a computationally efficient way. Our algorithm is statistically optimal and runs in polynomial time, and this is the first algorithm to combine these two properties! \nWe would like to add that our algorithm also exhibits a sample complexity polynomial in $K$ in the moderate confidence regime (when $\\delta$ does not necessarily tend to 0). Note that no algorithm with both (i) minimal sample complexity in the high confidence regime and (ii) polynomial sample complexity in the moderate confidence regime was known even in the vanilla MAB problem (in the recent paper [6], the authors did not manage to get these guarantees). P-FWS enjoys these guarantees in a setting that is far more challenging than what [6] (or [40]) considers.\n\nAbout the absence of experiments. In this paper, we wanted to highlight its strong theoretical contributions – as listed in the previous paragraph. We implemented our algorithm P-FWS. But we found it difficult to compare its performance to that of other algorithms, for these algorithms are computationally too challenging (it takes too much time to run). Here is an illustrative example. We compare P-FWS to a simplified version of CombGame [36]. The experiments are performed on a Macbook (Apple M1) with 8 cores and 16GB memory. We made 100 runs to compute the expected sample complexity of the algorithms\n * On a graph with $K=20$ edges and a decision set consisting of $|X|=21025$ spanning trees and confidence $\\delta=0.1$, P-FWS has an expected sample complexity $\\tau$ of 1139 samples while CombGame with OFW has an expected sample complexity of 1325 samples but already takes 21 minutes for each run. \n * Now on a graph of $K=25$ edges and $|X|=0.3$ million spanning trees and confidence $\\delta=0.1$, P-FWS expected sample complexity is 2000 samples (and in average, each run takes 17 hours) while any run for CombGame fails to finish within 2 days.\n\nNote that the original CombGame algorithm could not be implemented – it takes way too much time to finish. We had to simplify it. More precisely, we use our MCP subroutine to perform two components of CombGame, namely the best-response player and the stopping rule. Even with this simplification, CombGame rapidly becomes computationally intractable as the size of the decision set increases. "}, {"review_id": "CYMVHFLPKV", "reviewer": "Reviewer_26At", "summary": "The paper is about best arm identification with fixed confidence, in combinatorial semi-bandits. The state of the art in that setting is that we have algorithms that have optimal asymptotic sample complexity, but their computational complexity is very large. The authors provide a new algorithm which remediates this problem. The algorithm is asymptotically optimal and has polynomial computational complexity (in the number of arms and parameters of the problem like the minimal gap).\nThe main contribution is a method to compute efficiently the closest alternative to an instance of the combinatorial semi-bandit problem, which is a sub-routine is several BAI algorithms. That method is incorporated into a BAI algorithm based on Frank-Wolfe.", "questions": "Can you provide an empirical analysis of the proposed method and compare it to other algorithms? Both for sample and computational complexity.\n", "limitations": "The limitations of the paper are adequately discussed. No concern about societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The algorithm presented is the first to have polynomial computational complexity in combinatorial BAI. This is a significant achievement towards having practical algorithms for that important problem. The sample complexity is also asymptotically optimal.\n\nThe new method MCP is the result of an interesting reformulation of the problem and a thorough analysis of its properties. Its integration in a Frank-Wolfe algorithm also uses innovative methods compared to the existing FW algorithm for BAI.\n\nThe algorithms and the results are clearly explained.", "weaknesses": "The dependence in K, D and other constants is indeed polynomial, but with very large exponents. Some bounds depend on K^15. Since this work presents the first algorithm with polynomial complexity, this is only a mild weakness.\n\nThe main weakness is that there is no experimental evaluation.\n- Is the method still very inefficient in practice? Can it actually run on a computer?\n- Some components of the algorithm seem to be included to make the analysis work, like the comparison of \\sqrt{t} with the norm of the empirical mean vector. A natural question is whether they are necessary in practice, or if they are artifacts of the analysis. This could have been studied empirically.\n- The paper does not provide only a computationally efficient subroutine for a known algorithm, but also proposes a new BAI algorithm based on Frank-Wolfe (another FW based method already exists, but it is not exactly the same). The sample complexity of the new method should then also be evaluated. Perhaps an innocuous looking modification made it very bad in practice, although the asymptotic guarantees are good?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your careful review and positive feedback.\n\nAbout the comment:\n> Some components of the algorithm seem to be included to make the analysis work, like the comparison of \\sqrt{t} with the norm of the empirical mean vector.\n\nWe agree that naturally, some of the components of our algorithm, like the comparison to $\\sqrt{t}$, have been precisely designed so that we obtain the desired performance guarantees. Now it is indeed interesting to see whether in practice, the algorithm would work tuning down these components. We leave this sensitivity analysis for future work.\n\nAbout the absence of experiments. In this paper, we wanted to highlight its strong theoretical contributions: for combinatorial bandits, our algorithm P-FWS is the first polynomial-time algorithm that is statistically optimal in the high confidence regime. In addition, it has a sample complexity polynomial in $K$ in the moderate confidence regime. \nWe implemented P-FWS. But we found it difficult to compare its performance to that of other algorithms, for these algorithms are computationally too challenging (it takes too much time to run). Here is an illustrative example. We compare P-FWS to a simplified version of CombGame [36]. The experiments are performed on a Macbook (Apple M1) with 8 cores and 16GB memory. We made 100 runs to compute the expected sample complexity of the algorithms\n * On a graph with $K=20$ edges and a decision set consisting of $|X|=21025$ spanning trees and confidence $\\delta=0.1$, P-FWS has an expected sample complexity $\\tau$ of $1139$ samples while CombGame with OFW has an expected sample complexity of 1325 samples but already takes 21 minutes for each run. \n * Now on a graph of $K=25$ edges and $|X|=0.3$ million spanning trees and confidence $\\delta=0.1$, P-FWS expected sample complexity is 2000 samples (and in average, each run takes 17 hours) while any run for CombGame fails to finish within 2 days.\n\nNote that the original CombGame algorithm could not be implemented – it takes way too much time to finish. We had to simplify it. More precisely, we use our MCP subroutine to perform two components of CombGame, namely the best-response player and the stopping rule. Even with this simplification, CombGame rapidly becomes computationally intractable as the size of the decision set increases. \n"}, {"review_id": "ronDtibUby", "reviewer": "Reviewer_d388", "summary": "\nThis manuscript studies the asymptotically optimal sample complexity for the best arm identification in stochastic combinatorial semi-bandits, under the fixed confidence setting. The main contribution is the introduction of a computationally efficient algorithm which achieves the asymptotically optimal sample complexity in the high-confidence regime, confirming the conjecture of [Jourdan et al. 2021] on the nonexistence of a statistical-computational gap. The proposed algorithm relies on the change-of-measure lower bound (Eqn. (1)) in [Garivier and Kaufmann, 2016], with two main ingredients: \n\n1. To solve the inner minimization problem, using the Lagrangian form the authors formulate it as a two-player zero-sum game. The minimizing player (choosing a super arm) uses a FTPL algorithm which is oracle-efficient based on a linear maximization (LM) oracle; the maximizing player (choosing the Lagrangian parameter) plays the best response. The standard result of online learning shows that the average plays converge to the minimax solution. Significance: medium. \n\n2. To solve the outer maximization problem, the authors use a perturbed Frank-Wolfe sampling algorithm. First, the objective function is smoothed by a Gaussian kernel to overcome the issue of multiple gradients. Second, the learner computes the estimated gradient for the smoothed objective and plays the best response to the estimated gradient. A stopping rule, as well as forced exploration rules, is also applied in the algorithm. Significance: medium. ", "questions": "The remainder term in Theorem 2 depends on Delta_min, which is pretty unfortunate, for this quantity could be small in combinatorial bandits. I am wondering if one can argue that this term is always negligible compared with the main term? More specifically, when Delta_min is small, then the optimal sample complexity T^* would also be large; I'm wondering if T^* could always dominate the poly(1/Delta_min) term in the remainder. ", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This manuscript proved the nonexistence of the statistical-computational gap in stochastic combinatorial semi-bandits and resolved a conjecture of [Jourdan et al. 2021]. The components in the algorithm design, i.e. the two-player games and the perturbed Frank-Wolfe sampling, are both interesting.", "weaknesses": "Overall I like this paper and lean towards acceptance. However, I do have some concerns on the significance of the results: \n\n1. The problem in study, i.e. a computationally efficient algorithm for best arm identification in stochastic combinatorial semi-bandits under the fixed confidence setting, is very specific and a bit narrow in scope. The proposed algorithm is very tailored to the current setting, and the results are asymptotic. The motivation of this manuscript seems to be mainly technical curiosity, where the proposed algorithm is too complicated and very unlikely to be used by practitioners. \n\n2. The nonexistence of statistical-computational gap is not very surprising, which slightly lowers the significance of the result. Also, the attained sample complexity is asymptotically optimal only in the high confidence regime and also involves a parameter polynomial in 1/Delta_min. \n\n3. The two-player zero-sum game approach for an oracle-efficient algorithm is nowadays pretty standard, especially when one player is playing FTPL and the other is using best response. So the significance of the first component is medium. \n\n4. The Frank-Wolfe sampling approach, albeit different from [Wang et al. 2021], is also pretty natural. The same also applies to the smoothing technique. The complicated notations and many seemingly arbitrary rules in the algorithm (more on the writing below) make it considerably harder to appreciate the main idea, and also degrade the significance. \n\nIn addition, I would like to point out that the writing quality of this manuscript is pretty poor. Just list several examples: \n\n1. The LM oracle is not even formally defined in the main text. \n\n2. Algorithm 2 is poorly explained. Why forced exploration when \\sqrt(t/|X_0|) \\in \\bN? Why does the best response to the estimated gradient correspond to a good decision? The definition of \\nabla F_{\\mu, \\eta, n} is deferred to a very later place. What is the intuition behind the stopping rule? What is the beta function in the stopping rule? Many components require explanations. \n\n3. Small places: \"would\" in Line 220, \"in\" in Line 257. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your careful review and feedback.\n\nAbout the paper scope. We believe that combinatorial bandits with semi-bandit feedback constitute one of the classical problems in the bandit literature. They find numerous applications, see [11, 12, 14, 16, 23, 36, 43, 50] (references are those from the supplementary material). Refer to the answer to reviewer Vkf2 for details. We will cite a few of these applications in the final version of the paper.\n\nAbout: \n> the results are asymptotic. \n\nOur primary objective was to derive an algorithm that is statistically optimal in the high confidence regime (when $\\delta$ goes to 0 – so indeed with asymptotic guarantees) and that runs in polynomial time. We achieved this objective, but our algorithm also exhibits non-asymptotic guarantees. It has a sample complexity polynomial in $K$ in the moderate confidence regime, see Theorem 4 (when $\\delta$ does not necessarily tend to 0). Note that no algorithm with both (i) minimal sample complexity in the high confidence regime and (ii) polynomial sample complexity in the moderate confidence regime was known even in the vanilla MAB problem (in the recent paper [6], the authors did not manage to get these guarantees). P-FWS enjoys these guarantees in a setting that is far more challenging than what [6] (or [40]) considers.\n\nAbout: \n> The nonexistence of statistical-computational gap is not very surprising. \n\nWe would like to emphasize that our result is new even for the vanilla MAB problem: as mentioned above, there is no existing algorithm whose sample complexity is both asymptotically optimal and is polynomial in $K$ in moderate regime. In addition, for combinatorial semi-bandits, we are the first to show the optimization problem leading to the problem-specific sample complexity lower bound can be solved in polynomial time. The level of complexity of this problem was so far unknown. Based on this result, we can devise an algorithm, P-FWS, that tracks the lower bound in a computationally efficient way. \n\nAbout: \n> The proposed algorithm is too complicated.\n\nBased on existing Julia implementations [21, 57], we implemented the sampling rule of P-FWS within 50 lines of code (this amount of code is comparable to what other sampling rules take), and used 100 lines of code to implement the MCP algorithm. We did not present this implementation in the paper because we found it difficult to compare the performance of our algorithm to that of other algorithms. The latter algorithms are computationally too challenging (it takes too much time to run). Here is an illustrative example. We compare P-FWS to a simplified version of CombGame [36]. The experiments are performed on a Macbook (Apple M1) with 8 cores and 16GB memory. We made $100$ runs to compute the expected sample complexity of the algorithms\n * On a graph with $K=20$ edges and a decision set consisting of $|X|=21025$ spanning trees and confidence $\\delta=0.1$, P-FWS has an expected sample complexity $\\tau$ of 1139 samples while CombGame with OFW has an expected sample complexity of 1325 samples but already takes 21 minutes for each run. \n * Now on a graph of $K=25$ edges and $|X|=0.3$ million spanning trees and confidence $\\delta=0.1$, P-FWS expected sample complexity is 2000 samples (and in average, each run takes 17 hours) while any run for CombGame fails to finish within 2 days.\n\nNote that the original CombGame algorithm had to be simplified. More precisely, we use our MCP subroutine to perform two components of CombGame, namely the best-response player and the stopping rule. Even with this simplification, CombGame rapidly becomes computationally intractable as the size of the decision set increases. \n\nAbout: \n> the attained sample also involves a parameter polynomial in $1/\\Delta_{\\min}$\n\nThe dependence of sample complexity in $1/\\Delta_{\\min}$ is unavoidable: it is easy to derive from Proposition 1 (c) that $T^*(\\mu)$ is at least $1/\\Delta_{\\min}^2$. \n\nAbout: \n> The two-player zero-sum game approach for an oracle-efficient algorithm is nowadays pretty standard.\n\nOur contributions consist in (i) establishing the property that allows one to relate Eq (3) to a two-player zero-sum game and (ii) designing an algorithm that not only converges to the equilibrium but also returns an equilibrium action, even in a setting where one of the domains (the action set of one player) is not convex. \n\nAbout (i), prior works [12, 57] apply Lagrangian multiplier method to derive the closed-form of $f_x(\\omega,\\mu)$, but as far as we know, no one noticed the linear-concave property of the Lagrangian dual function as we showed in Proposition 1. This property opens the opportunity to relate Eq (3) to a two-player zero-sum game.\n\nNow achieving (ii) is non-trivial. In the standard setting [2, 19, 52], the domains for both players are convex, and the objective is just to converge to the equilibrium with low cumulative regret. In our case, for MCP, one of the domains (that of the $x$-player) is combinatorial. Moreover, we wish to return the equilibrium action (which is more difficult that just ensuring low cumulative regret) – this type of convergence is referred to as last-iterate convergence in the literature, see e.g. [20] and other references cited in Section 3.2. \n\nAbout: \n> The Frank-Wolfe sampling approach is also pretty natural. \n\nThe Frank-Wolfe approach of [57] cannot be applied here because it would lead to a computationally infeasible algorithm as we explain in the paper. Hence, we had to use and analyze a different smoothing technique.\n\nAbout: \n> What is the intuition behind the stopping rule? What is the beta function in the stopping rule? \n\nThe stopping rule basically compares $F_{\\hat{\\mu}(t-1)}(\\omega(t))$ (which represents the distance of the current estimation to the closest bandit model with a different the best action) to a threshold function $\\beta$. Please refer to [29, 42] for details. See line 291-292 for possible choices of threshold function $\\beta$."}, {"review_id": "EcZpKZcn8L", "reviewer": "Reviewer_b447", "summary": "The paper presents Perturbed Frank-Wolfe Sampling (P-FWS), an algorithm for the best arm identification problem in combinatorial semi-bandits in the fixed confidence setting. The algorithm achieves instance-specific minimal sample complexity in the high confidence regime and polynomial sample complexity guarantees in the moderate confidence regime. The authors show that P-FWS closes the computational-statistical gap in best arm identification in combinatorial semi-bandits. They describe the design of P-FWS, which starts from the optimization problem defining the information-theoretical and instance-specific sample complexity lower bound. P-FWS solves this problem in an online manner using the Frank-Wolfe algorithm with computationally efficient successive updates.", "questions": "How do you think your work could be extended beyond the LM Oracle ? For instance, in https://arxiv.org/abs/2302.11182, there are several combinatorial problems that do not fit your setting. I think it should be good to add this reference (and perhaps other) and mention (as future work or limitation) that more general combinatorial problems exist, and that your setting is restricted. ", "limitations": "The paper assumes the availability of a computationally efficient Linear Maximization (LM) Oracle, which can identify the best action given knowledge of the parameter µ. While this assumption may hold for some combinatorial sets of actions, it may not be applicable in all scenarios.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "P-FWS is a new algorithm that addresses the best arm identification problem in combinatorial semi-bandits and achieves optimal sample complexity in both high and moderate confidence regimes. This makes it a significant contribution to the field. The paper highlights the closure of the computational-statistical gap in best arm identification in combinatorial semi-bandits. This is an important result, as it demonstrates the algorithm's efficiency in terms of both computational complexity and statistical performance.", "weaknesses": "The paper primarily focuses on theoretical analysis and does not include empirical experiments or evaluations on real-world datasets. While the theoretical guarantees are valuable, empirical results could provide further insights into the algorithm's practical performance and generalizability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your careful review and positive feedback.\n\nAbout experiments. In this paper, we wanted to highlight its strong theoretical contributions: for combinatorial bandits, our algorithm P-FWS is the first polynomial-time algorithm that is asymptotically optimal in the high confidence regime. It also has a sample complexity polynomial in $K$ in the moderate confidence regime. We implemented our algorithm P-FWS. But we found it difficult to compare its performance to that of other algorithms, for these algorithms are computationally too challenging (it takes too much time to run). Here is an illustrative example. We compare P-FWS to a simplified version of CombGame [36]. The experiments are performed on a Macbook (Apple M1) with 8 cores and 16GB memory. We made 100 runs to compute the expected sample complexity of the algorithms.\n * On a graph with $K=20$ edges and a decision set consisting of $|X|=21025$ spanning trees and confidence $\\delta=0.1$, P-FWS has an expected sample complexity $\\tau$ of 1139 samples while CombGame with OFW has an expected sample complexity of 1325 samples but already takes 21 minutes for each run. \n * Now on a graph of $K=25$ edges and $|X|=0.3$ million spanning trees and confidence $\\delta=0.1$, P-FWS expected sample complexity is 2000 samples (and in average, each run takes 17 hours) while any run for CombGame fails to finish within 2 days.\n\nNote that the original CombGame algorithm could not be implemented – it takes way too much time to finish. We had to simplify it. More precisely, we use our MCP subroutine to perform two components of CombGame, namely the best-response player and the stopping rule. Even with this simplification, CombGame rapidly becomes computationally intractable as the size of the decision set increases. \n\nAbout your comment on problems where the LM oracle cannot be implemented in polynomial time. Thanks for this remark and the reference. We will add and discuss it! This issue remains beyond the scope of our paper. It would be interesting to investigate whether the techniques of (Yang, Feidiao, et al.) could be used. We will mention this in the conclusion.\n\nReference:\n * (Yang, Feidiao, et al.) \"Follow the perturbed approximate leader for solving semi-bandit combinatorial optimization.\" Frontiers of Computer Science 15 (2021)\n"}]

Author rebuttal:

Meta-review: This paper makes a substantial advance on a problem of broad interest to the ML community: combinatorial semi-bandits. Prior to this work, we didn't have approaches that were both computationally and statistically efficient. Their Frank-Wolfe based solution might also inspire similar work on related problems.
Decision: Accept (poster)