Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox
Authors: Raymond Zhang
Richard Combes
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Combinatorial bandits
Thomspon Sampling
Primary area: bandits
TL;DR: We propose a modified version of Thompson sampling for combinatorial bandits, the first that does not exhibit exponential regret.

Abstract: We consider Thompson Sampling (TS) for linear combinatorial semi-bandits and subgaussian rewards. We propose the first known TS whose finite-time regret does not scale exponentially with the dimension of the problem. We further show the mismatched sampling paradox: A learner who knows the rewards distributions and samples from the correct posterior distribution can perform exponentially worse than a learner who does not know the rewards and simply samples from a well-chosen Gaussian posterior. The code used to generate the experiments is available at https://github.com/RaymZhang/CTS-Mismatched-Paradox

Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox
Raymond Zhang
Laboratoire des signaux et systèmes
Université Paris-Sace Paris-Saclay, CNRS, CentraleSupélec, 91190, Yvette,,,, France. Raymond.
Richard Combes
Laboratoire des signaux et systèmes
Université Paris-Saclay, CNRS, CentraleSupélec, 91190, Gif-sur- Y France. Richard, combes& cent raleuueee......................
Abstract
We consider Thompson Sampling (TS) for linear combinatorial semi-bandits and subgaussian rewards. We propose the first known TS whose finite-time regret does not scale exponentially with the dimension the problem. We further show the mismatched sampling paradox: A learner who knows the rewards distributions and samples from the correct posterior distribution can perform exponentially worse than learner who does not know the rewards and simply samples from a well-chosen Gaussian posterior. The code used to generate the experiments is CCS-smsstccC--issthhhhhhhh Paradoxx
available
1 Introduction and Setting
We consider the linear combinatorial bandit problem with semi-bandi feedback: At time
{1,..., T} learner selects an action A(t) where the set of available actions A {0. 1] is known combinatorial set, i.e., set of binary vectors. Then the environment draws random vector X(t) E
K and learner then observes (0) = A(t O ((),, where O denotes the Hadamard (element-wise) product, and the learner obtains reward of A(t) T (t).. We assume that the vectors (X(t)) are drawn i.i.d. from some distribution with expectation E(X(tt) p² and that the entries of (t) are independent. The vector y lies in some @ c Rd and is initially unknown to the
learner. The learner wants to minimize the regret:
R(T, p²) T Fmxx (A AAT AEA
E
Σ A(1)T [E(T]
E
Σ [=(7]
A
A(O)
Where A
arg max AeLA (ATx²) is the optimal action and gap between action A and optimal action A". The regret the expected difference between the sum of rewards obtained by an oracle who knows μ² and always selects the optimal decision and that obtained by the learner. We assume that the optimal decision unique. To state regret bounds, use the following notation. We denote by A min
T 1r" ATp p² the reward
min A AA the minimal reward gap and A(t) the reward gap of the action selected ||]] the maximal size of an action.
max A A the maximal reward gap, At)
max
time f.
max
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

The regret depends on the distributions of the random vector (t), which generates the rewards, and we will assume throughout the paper that X (1) is -sugauussian so that for all À E Rd:
E[exp(A A Xx)) & AT 1
This assumption holds in many scenarios of interest, for instance, when (t) e [a, b7 with o² (b- (b-a)9/4, when (() is normally distributed with a covariance matrix smaller than la We assume that a is known, or at least upper-bounded.
One of the candidate algorithms for this problem is Thompson Sampling (TS), which is based on Bayesian inference. We consider a prior distribution To over O a likelihood function and Ny the posterior distribution of μ¹ at time & knowing the observations and the actions up to time t:
I 1sett- 11 (A))) + (1 Ac(s))] (T()))
(u) So I [ee[ Leea ()))) + (1 A.(s))]=o(()))
The TS algorithm with prior mo and likelihood l consists in sampling 0()) from distribution Ty. and select action A(t) E arg m A (tt). The random vector P(t) called a Thompson Sample, acts as proxy for the unknown 11 and guides the exploration.
We will show how TS behaves with either Gaussian likelihood {(x, = (2m)-1/2e (2m)
(==-))? or
Berouuli likelihood ((z, μ4) = 1(x 1/ (1 p)) 0} in the next sections. If the likelihood e(X,(s) (4.) is selected as the distribution of Xx(s) knowing 14, then we say that TS is natural. If the likelihood E (s), (4:) is different from the distribution of (s) knowing f4:, we will say that TS is mismatched. An example of mismatched TS would be to select as the Gaussian likelihood, although the actual distribution of X()) knowing μ² is, say, Bernoulli or some other bounded distribution. Ultimately, the likelihood function is a choice left up to the learner to control how TS explores the suboptimal actions. Perhaps counterintuitively, mismatched TS can outperform natural TS, as we will demonstrate. The prior can be chosen in various ways, for instance, Jeffrey's 's non- non-informative prior. can even be chosen as an improper prior, where Se To (o( = +00 as long as the integral in the definition of T. is well-defined.
TS is usually computationally simple implement as it requires linear maximization over the action space A at each step, which we assume can be done in polynomial time in m and d. This fact explains the practical appeal of TS since whenever linear maximization over A can be implemented efficiently; the algorithm has low computational complexity. Also, for some problem instances, it tends perform well numerically.
2 Related Work and Contribution
Combinatorial bandits are generalization of classical bandits studied in [17]. Several asymptotically optimal algorithms are known for classical bandits, including the algorithm of (18). KL-UCB (S)
DMED [3 and TS [4 22). Other algorithms include the celebrated UCBI 14. Numerous
algorithms for combinatorial semi-bandits have been proposed, many of which naturally extend
algorithms for classical bandits to the combinatorial setting. CUCB 66 16) is natural extension of
UCBI to the combinatorial setting. ESCB (8 10 is an improvement of CUCB, which leverages the
independence of rewards between items. AESCB ( an approximate version of ESCB with roughly the same performance guarantees and reduced computational complexity. TS for combinatorial
semi bandits was considered in [IT 15 20 21 23 while TS for linear bandit was studied in [T] 3). Also, combinatorial semi-bandits are particular case of structured bandits, for which there exist asymptotically optimal algorithms such as OSSB [7]. It was also shown in (15) that TS is asymptotically and finite time optimal for matroid-like action sets. The Bayesian regret of TS has been extensively studied, e.g., 21
Three types of regret bounds exist in the literature: R(T is the the regret of the learner on the particular problem instance defined by μ², The minimax regret is max R((T, nu²) and the Bayesian regret E,,. [R(T, [*)] where is drawn according to some prior distribution. We will state regret bounds as a function of the parameters T, the time horizon; d, the problem dimension; m, the maximal size of an action; and Amin. the minimal gap.
regret, i.e.,
The paper 166 showed that the problem- regret of CUCB is upper bounded by dd 2 Amtr
and its minimax regret is upper bounded by O(v o In T + dm). 110 showed that the problem-

---

dependent regret of ESCB upper bounded by O
aa odd(lam)* In
dm and its minimax regret is
Amin
A uin
upper bounded by O (Vy/((im d( + dm). TS is upper bounded by
20 showed that the problem-dependent regret of
o
Φ dd (1) In
dm3
+ m ( m² +
2+4m
Amin
A min
Amin
While this bound is almost optimal in the asymptotic regime where T - co, it is exponentially suboptimal in the finite time regime since the last term of this expression scales exponentially with m. Unless one assumes particular type of action set as in [15]. all the known generic regret upper bound for TS in the literature (TT), [2], 20] feature an exponential dependency on m. (24) further showed that the problem-dependent regret of 'S for some simple combinatorial set can be lower
bounded by an expression scaling exponentially in m,
Amn (1 (1-(1-PA.. Pammn )T")), with Pammn = exp
2m
Amin
R(T,
4p2mmn
9
2
They further showed that Thompson Sampling is not minimax optimal for some combinatorial bandit problems. Therefore, the exponential term is not an artefact of the analysis of (20]. It is also noted that the regret upper bounds for ESCB and CUCB do not feature this exponential dependency in m, suggesting that those algorithms are better the finite time regime than the versions of TS analyzed so far in the literature. This is unfortunate because TS usually has very low computational complexity, and having an algorithm with both low computational complexity and low regret in the finite time regime would be highly desirable.
Our contribution (i) We propose new variant of TS with a regret upper bounded by:
o'd'nn m
1 m In T + P m, d, Amin
In T
Amax:
Amin
Amiu
where P is polynomial in m, d, Ampi' Amax- This polynomial term is a clear improvement over the bound of (20) in the finite time, high dimensional regime where T is relatively small and m is large. Indeed, the last term in this bound P (m, L/Amin Amax σ)) will be much smaller than the last term in the bound of [20) m (a(m² + 1)/Amin] 2+44 which is exponential in m. To design our variant, we add slight exploration boost to TS, which vanishes as T op but significantly impacts the algorithm behaviour when I is moderate and m is large. Also note that the improvement in the In m term comes from a direct application of a result (19).
(ii) We design new proof strategies to derive this upper bound, which are based on carefully bounding the sample path behaviour of TS. We believe those strategies
essential contribution to the analysis of TS and enable us to show that with high probability, TS will sample the optimal action at least (((*)) times with a O. This number serves to control the transient behaviour of TS.
(iii) As a by-produet, we show the mismatched sampling paradox of TS: in some cases, mismatched TS performs exponentially better than natural TS. For instance, in problem where X(t) has Bernoulli distribution, learner using a uniform (improper) prior and a Gaussian likelihood can perform exponentially better than learner using Beta prior (which includes Jefffress' prior) and the Bernoulli likelihood. In essence, trying to exploit the learner's statistical knowledge about the model ends up harming them.
(iv) We confirm our theoretical predictions using numerical experiments, which clearly show that our variant of TS outperforms by several orders of magnitude the Beta-based versions studied in the literature whose regret scales exponentially in the ambient dimension.
Algorithms
In this section, we present three TS algorithms: B-CTS Beta-Combinatoriaa Thompson Sampling), which is TS with a beta prior and a Bernoulli likelihood, G-CTS (Gaussian-Comile CombinatoCoiii Thompson Sampling) which is TS with uniform (improper) prior and a Gaussian likelihood, and finally BG-CTS (Boosted introducing carefully chosen exploration boost in G-CTS.
Thompson Sampling), an algorithm we propose by
3

---

3.1 Notation
We use the following notation state algorithms. We define the statistics vector containing the number of times each item has been selected, Ma
(t) Ee A(s), the
2 1 (A(s) = A] the number of times action A has been selected until V(1) D N(a) the diagonal matrix whose diagonal elements are (1/Ni 1/N,,(t)) ((t) == V(t) (t) se X((s) O A((s) the empirical average estimator for μ=", We denote by (((C) (A(s), A(s) C (()))) sEt--1 the history which contains all the information collected by the learner up time t. and which includes both the
observations and the selected actions. For two vectors a; 3 in (R+) we denote by Beta(a, B)
Beta( Oig 3.) the distribution of vector with independent entries, and where the i-th entry is 8
Beta og 3r) distributed.
3.2 B-CTS
B-CTS (see I in the algorithm format) considers the prior To Beta( 3(0)) where a0)), are two vectors in Rd chosen by the learner and the Bernoulli likelihood f(x, 11) = [ 1) +
- (1-x)1(a = 0}. If a()) = B(0) = (1, 1), then the prior To is uniform over [0, 1j If a(0) ((0) (1/2,
1/2). then the prior is Jeffreys' non-informative prior, which is proportional to the square root of the determinant of the Fisher information matrix. In B-CTS, the posterior distribution मe is also Beta distribution so that the Beta-CTS selects the action:
A() E arg max A 0(1) with O(t) Beta(a((), AeA
where vectors (t),, are defined
a(t)
Σ
X(s) O A(s) + (0) and 3(t)
Σ (1- (I))(s)) ( 8(0). se[t-1]
sE(t-1]
3.3 G-CTS
G-CTS considers the improper prior To which is constant and equal to 1/a on all Rd and Gaussian where o² the variance. Of course, since To is improper, for N, to be well-defined, we require that enough samples have been collected so that N(I) > 1. This is easily achieved by selecting d actions A , A" that cover A the sense that Eield A > 1, and initializing the algorithm by sampling each of them once. In G-CTS, the posterior
likelihood ((x,
distribution is also Gaussian distribution that the G-CTS selects the action:
A(t) arg max A ((t) with 8(t) N(((t),o&V(t))
AEA
3.4 BG-CTS
BG-CTS (see 2 in the algorithm format) is a modification of G-CTS that we propose and that selects
the action
A(t) E arg max A ((()) with O(t) ~ (((t),
with
A
v(()
=
f(t)
and S(I) == (1 A) [Inl+ (m 2) In
m In (1++)) 2
Int.
and À R+ is an input parameter of the algorithm. BG-CTS behaves like G-CTS with time- varying boost in its exploration denoted by g(t). This boost asymptotically behaves like a constant lim; 9(t) 1 + X. This boost ensures much better finite-time behaviour, especially in the moderate T, large m regime, to avoid the exponentially large regret that can occur in TS. The form of g(t) is not arbitrary and is derived from the nefmmnorml concentration inequalities that control the large deviations vector (t)). To make our analysis clearer, we will assume that there exists an exogenous process (Zt)) 1 of i.i.d. (0, La) vectors that serves as the random generator number for the Thompson samples with ((t) pi(t) + / V (t)Z(t).
This decomposition is useful for separating the algorithm's 's randomness from the bandit environment's randomness. We notice that for all > (ss) and the history H(tt) are independent. Furthermore, we call ((s) the random part of the Thompson sample, A ((t)) the Thompson sample of action A

---

4 Main Result
We now state Theorem 1 our main result.
Theorem 1, For À = 1, and o² subgaussian rewards. the regret of BG-CTS is upper bounded by:
R(T, ( & C Ind m
In + C g0 dmm Imm In InIn I + m, d,
Amax: 0
(1)
Amin
Amin
Awin
1 with C, C' universal constants and P polynomial in m. d, Aminn maxx
Theorem
T states that the regret of BG-CTS is upper bounded by an expression with both the correct behaviour when T is large i.e., both this bound and that of [20] give the same upper bound on R(T,,"), but also polynomial dependency in m, Amyn" Amax: d. This result predicts that BG-CTS performs much better than other TS variants the regime where the time horizon I is moderate and the decision size m is large.
lim sup-- In
A consequence of Theorem I combined with prior known results of [4 this is the mismatched sampling paradox for TS: a learner attempting to leverage his knowledge about the statistical model by using natural TS can perform exponentially worse than a learner willingly ignoring this knowledge and using mismatched TS by using an algorithm such as BG-CTS. Consider the example of (24] which features two disjoint actions of size and Bernuulii rewards. Suppose the learner attempts to leverage that she knows the rewards are Bernoulli and that the parameter space is [0. 1jd. She will employ a uniform prior over [0, 1] and the Bernoulli likelihood. This means using B-CTS and getting a regret that scales exponentially with d as shown in (24). Using B-CTS with Jeffrey's prior does not help either. On the other hand, if the learner pretends she does not know the parameter space nor the rewards distribution and uses B-CTS, she gets a regret scaling only polynomially in Furthermore, Bernoulli rewards are a² subgaussian with o² < 1/4 as stated above, so our regret upper bound for BG-CTS applies to this example.
d/2 written (1, -1, 1, D2 -... 0) and (0, ..... 1, 1,....
At first glance. seems outright absurd to use a prior whose support is the whole of g instead of the actual parameter space [0, 1j and using Gaussian likelihood, which is continuous when the rewards are binary, but this paradoxically gives exponentially better performance. This paradox leads us believe one should be careful when using posterior sampling for regret minimization. While this is natural for Bayesian inference, things seem to be much more complex when solving bandit problems, which feature both inference and control/exploration..
5 Regret Analysis
In this section, we describe how to prove our main result. Due to space constraints, some proof elements are relegated to the appendix. In particular, to make this proof (without their proofs) the results from previous work that we use for our analysis. A reader can try to follow the proof with the help of the diagram in figure 2
we reproduce
fundamental idea of our analysis is consider the event ML where both events occur:
Vs E [t], AA E A TA O(t) - A n1 & V (s)
and 1s [1] A 0(s) > A n²)
T(s))
> C2ta
Where C1
8 + 72,
C 2 = 1.238.
a 3/4 (1,)) > 0.131.
2 1
When 2, occurs, we say that we observe a clean run up to time A clean run up to time implics that the Thompson sample of any action A at any time E [t] cannot exceed the sum of its expected value and a bonus proportional to A ATV (t)A, which can be interpreted as the confidence bonus used in the CUCB algorithm. A clean run also implies that there exist many instants at which the Thompson sample of the optimal action is at least as large as its expected reward A" μ²"
5.1 Probability observing clean run
We first now show that most runs are clean, i.e., clean runs occur with high probability. Proposition 2 states that the probability of non-clean run up to time / much smaller than 1/4, and therefore non-clean runs cause little regret.
5

---

Proposition 2. For all t > Cs we have P(2)) > 1 4dt 2 3-t=1((mn 2 -2 - Catt with Ca C2/8
and C
23.
Proof: The proof is relatively technical, and involves decomposing 21, according to the fluctuations of (() and j((t). We decompose the Thompson sample of the optimal action as follows:
A B') A (s) S (s) A V())A*
with
(M(()) - 14") and (*) = OV 2g(s)
A' V1V2// (1/2())
U (*)s)
A' V
A' T V(s)
which represent the deviation between the empirical mean and the expected reward, and the deviation of the Thompson sample from the expected value of the Thompson sample.
We introduce the following deviation events
[max
|IV (s) ()))))l 2 8li
(max sc[t]
[()) > v6lnd)
se[r]
(M(s [t] (s) > 2/2f(()) C2t")
(max U (s) 3 oV 2f(tt).
==[r]
Each of those events can be interpreted as follows. B, means that the empirical mean of some item deviates from its expected value at least once, e, means that the randomization in the Thompson sample is abnormally large at least once, D; implies that the empirical mean of the optimal action deviates from its expected value at least once, and e means that there exist too few instants at which (*) is reasonably large.
Assume that none of B,, C, D., C, occur. For all A and all s [t]:
AA (AT)(s) A AT n01 < IAT (A n²) + (AT (0(s) ((s)) < CI
since if B, does not occur:
(m(s) - -²)] < ov 8 (1
and if C, does not occur and because g(t) < 2(2m 1) 6m see lemma f.
|A (0(s) - 70 [())) & av 72m In y (s)
Furthermore Dt and E, do not oceur, there exists least Czt instants such that 5*) (
and U*(s) (s) > /2](((,, which implies A 0(s) > A n²", This means that:
{s [4] A T(()) A > Oala
Therefore 24 occurs, and have clean run. Hence P(2G) > 1 P(B,)))))))))))))))))( - P(C.) - PP(.)) P(E.)
We now upper bound the probability of each event separately.
5.1.1 Probability of B,
Using union bound TP P(B.))
Σje[a] P maxx)e / (V((s((4(()) ()s)) /v8lnt 2dt-2
We used the concentration inequality first derived by [16) in their analysis of CUCB and recalled in lemma
5.1.2 Probability of C;
Using union bound and Chernoff bound for the Gaussian distribution (lemma 10 wheres Q is the tail function of the standard Gaussian distribution
P(C.) & Σ Σ (z((s)) > V6lnt) & 2tdQ(V6lnt) & 2xdexp((3111 31 = 2dt
[ SE[1]

---

5.1.3
Probability of 1
We have for > 2, P(),) & (Int) from the concentration inequality derived by 10 in their analysis of ESCB and recalled in lemma
5.1.4 Probability of E,
In order to control the probability of e, consider the following counting process:
((s)
Σ ((5(uu) ov2)(tt)
[E[+]
We wish to show that, with high probability, (s) > C21 One may readily check that ((s) is sum of binary variables and that its conditional expected increment verifies:
p(s) () (W(()) (s) ((s - 1))+(s)) = (s) > a 2v2
((v/())/(()))
since, conditional to H((s). S* (s) has gaussian distribution with mean 0 and variance 29 (s). Let us lower bound of the sum of By considering /. > Cs we have
P(s) > (t/2)p(t/2) (t/2) ((2))((((t)/oo(2)))) [E(E]
(v22)((cs/In(t/2)) > 2C²ta
using the fact that p increasing 8, and the study of f() done lemma f. and lemma 10 on g(t/2)
the asymptotic behaviour of the Q function.
We can now conclude by applying multiplicative Azuma-Hoefiding style bound to W(s) presented lemma in the appendix. With C4 C2/8 we have:
P(C,) (W((t) C2t9) & W(t) (1/2) Σ p(s) SE(E]
< < : p()) t e CC
5.1.5
Putting everything together
Adding the four previous bounds, for all t > Cs,, P(2,) > 1 4dt t- = 2 - -Ct
5.2
Thompson sample for the optimal action on clean run
We have already established that clean runs occur with high probability. and now we concentrate on how the algorithm behaves on those runs. Proposition 3 further shows that the optimal action will be selected numerous times when clean run occurs. In turn, the Thompson sample of the optimal action will be arbitrarily close to its expected reward. This argument is the cornerstone of our analysis (that believe be missing in the previous analysis of (20)) and will allow to control the transient behaviour the algorithm.
Proposition 3. For 3 (i d, A if 2,, occurs, then we must have MA+(t) > Ceta
and A T 0(t) > T - M(t). With Pi a polynomial in m, d, Amin J, Ce In C
C1/2, and h((t)
Clamy
It is noted that lim h(())
Proof: Let us consider a clean run. We can count the number of times the optimal action was not chosen and the variance term of the action is greater than Amin:
(Coovmbaa > Amiu H|
Σ ae[d]
E A(s), Cio
mlnt
min
Ni(s)
m
m o
Int
A
And since we have clean run: ((s [4] : A T(s)
>
A
> C2ta, At those times, the
variance term of the action played is less than A min- then it means that the optimal action has been
played due to the first condition 21, So we get:
M MA-(1) > C2ta d Int
2 min
7

---

With Cg C2/2 for
Pi m, d, Amin _ (2)
(1-
1
1/a
9
1+1/a
d
1+1/a
C2
D Aiin
using lemma f. Recall that under 24
A (A))( - A" 1²1 & Co
Since (t) > Cge has been selected at least Cet times up time t, we have V m so we get the announced result:
mlnt Cgta
(At)
A"TT") n²1 A
Cjomy
h(t)
5.3
Regret upper bound
We analyze the regret. Let us define some more events at time
(A(t) > 0)
(T())(0())) -P()) a x (F00)ATTV0
A (t)(((((t) - -p²) 3d(1)
Bie A(t), (4(1) μ4 Amin
4m
with f(1)= = (In (IA11) + (m + 2) dln 2) (n(In)) + m(L+dIn2) In (1 e))
The event 3: means suboptimal play. 3, implies that the empirical mean of one of the items in the action selected at time t deviates from its expectation. 8 means that the Thompson sample of the decision played far from its true value, and finally, D) is for when the Thompson sample from arm played is far from its empirical mean. The complete event system decomposed as follows.
5.3.1 Regret due 2
Using proposition 2 we have that F(A,) < 4dt + Cat." Then we can use the
fact that LIEN- 77 G LIEN Mlme 4. And furthermore, with lemma f. 9 we have that
C-1/a
Eneror e -ct
r Therefore, the regret caused by 2, is upper bounded by:
2m²
C C='//
1/a
Σ [E[T]
B[A(t)1 [L.)]
max
(()) A max
r
+ +4
a
[E[T]
5.3.2 Regret due C5 n 21,
We use proposition 3 and we get that for 1. > (1 d, 1/4 o), A 0(1) > A 1²= h()).
Combining with event 6, we know that when h(t) < Amin/ /4, the only action that can be played
the optimal one. We recall the formula of ((t) = Ciomy
m mnf Cata
And using lemma f. 8 this
happens for t > Pa Amm. o) = (2) 1+2/a (1 1) -1/0
1/a (
[160?
1-1/a
fm2m min
1+1/a
So the
Co
regret caused by this term upper bounded by:
Σ E[A(t) (6, 2,3] Amax max P1 (m, d, 1/4min, Ø), Ps (m, 1/Amin: 0)}
Te [T]
5.3.3
Regret due to 3z
This result comes from lemma from (6 and reproduced here lemma g By setting Amin
we have
322200
B[A(t)1 (5.)1 dAmax
A2 minn
5.3.4 Regret due f),
We show in lemma in the appendix that P(S,) 2 and E E [[A(t) (5:3]
Amax T

---

5.3.5 Regret due to &o B n Sy
We use lemma in this appendix, and we get with C
768
2304 In that
Id and
B[A(1) (
5.]]
Amin
[E[T]
3840 dlnmmmmmn
doddaa
IT + C² o' In
1152 o² ma In 1lm()))
Amin
Amin
Amia
Aii
5.3.6 Putting everything together
Finally, we can put everything together and obtain the regret upper bound found in with the following polynomial constant term
C
1/a
32m
5m
P
m, d,
Amin
Amax, o
A max
a
r
a
+
4
dI
max
min
+
3
(pi( (P,m,,
md In 2 InIn11 + e)
Amax
+ P2
m,
1152
min
min
A Amin
The degree of this polynomial depends 1 + 1/a 10 with 0.131. So the degrees of the polynomial in m,, d, 1/ mmin Amax are respectively 30, 10, 20, 20,
Numerical experiments
In this section we perform numerical experiments with Beta CTS, BG-CTS and ESCB on a case where there are only two actions A , A?) of size m d/2 with A (1,... ..., and A2 (0..... ..., 0, 1..., 1). This action set exhibited exponential regret in 224. We set μ (0.7, 0.7, 0.9, ... 0.9) with Bernoulli distribution. The algorithm Beta CTS Uniform prior is initialized with the uniform distribution, while the Beta CTS Jeffreys is initialized with the Jeffreys prior on [0, 1J. which puts more weight around the extremities of [0, 1J. increasing exploration.
10
B-UTS--XdE Aelico
LCTS-UUafom
30P
D-CTT-Ilufo
200000
BG-C78
BE-CTTS
Frod (100
150000
-00000
109
10000
10
Nandirr
(a) Average regret over time
(b) Average final regret as function
In the first experiment, we set time horizon o' 2 x 104, and each decision has m = 50 items. We run the experiment 100 times and plot the average regret over time and two empirical standard deviations Figure Ta The regret is nearly linear for the Beta-based Thompson samplings, whereas the subgaussian Thompson sampling and ESCB showcase regret of magnitude much lower. We set a time horizon the second experiment T x 104. For each decision size m E (5. 25, 45, 65), run the experiments 150 times, and we plot the final regret as a function of in Figure Ib In the Beta-based Thompson samplings, the final regret and its variance rapidly increase with m. In comparison, BG-CTS and ESCB do not seem to be affected.
7 Conclusion
proposed Boosted variance Gaussian Thompson Sampling for linear combinatorial bandits (BG-CTS) and proved using novel strategies that its regret is bounded polynomially. This variant of TS far outperforms the classical TS by several orders of magnitude on 2 decisions Bernoulli reward
example.

---

Acknowledgements
This paper is supported by the CHIST-ERA Wireless AI 2022 call MLDR project (ANR- 23-CHR4-0005), partially funded by AEI and NCN under projects PCI2023-145958-2 and 2023/05///ST7/00004 respectively.
References
[1] Mare Abeille and Alessandro Lazaric. "Linear thompson sampling revisited". In: Proc. of AISTATS. 2017.
[2] Shipra Agrawal and Navin Goyal. "Analysis of Thompson Sampling for the Multi-armed Bandit Problem". In: Proceedings the 25th Annual Conference on Learning Theory. 2012.
[3] Shipra Agrawal and Navin Goyal. "Thompson sampling for contextual bandits with linear payoffs". In: Proc. of ICML. PMLR. 2013.
[4] P. Auer, N. Cesa-Bianchi, and P. Fischer. "Finite time analysis of the multiarmed bandit problem". In: Machine Learning 47.2-3 (2002), pp. 235-256.
[5] O. Cappé et al. "Kullback-Leibler Upper Confidence Bounds for Optimal Sequential Alloca- tion". In: Annals of Statistics 41.3 (June 2013), pp. 516-541.
[6] Wei Chen, Yajun Wang, and Yang Yuan. "Combinatorial Multi-Armed Bandit: General Frame- work and Applications". In: Proc. of ICML. 2013.
[7] Richard Combes, Stefan Magureanu, and Alexandre Proutiere. "Minimal Exploration in Structured Stochastic Bandits". In: Proc. of NeurlPS. 2017.
[8] Richard Combes al. "Combinatorial Bandits Revisited". In: Proc. of NeurlPS. 2015.
[9] Thibaut Cuvelier, Richard Combes, and Eric Gourdin. "Statistically Efficient, Polynomial- Time Algorithms for Combinatorial Semi-Bandits" In: Proc. ACM Meas. Anal. Comput. Syst.
5.1 (2021), 09:1-09:31.
[10] Remy Degenne and Vianney Perchet. "Combinatorial semi-bandit with known covariance". In:
Proc. of NeurlPS. 2016.
[11] Aditya Gopalan, Shie Mannor, and Yishay Mansour. "Thompson Sampling for Complex Online Problems". In: Proc. of ICML. 2014.
[12] Robert D. Gordon. "Values of Mills' Ratio of Area to Bounding Ordinate and of the Normal Probability Integral for Large Values of the Argument". In: The Annals of Mathernatiaal Statistics (1941).
[13] Junya Honda and Akimichi Takemura. "An Asymptotically Optimal Bandit Algorithm for Bounded Support Models." " In: Proc. of COLT. Jan. 2010, pp. 67-79.
[14] Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. "Thompson Sampling: An Asymptoti- cally Optimal Finite- Analysis". In: Proc. of ALT. 2012.
[15] Junpei Komiyama, Junya Honda, and Hiroshi Nakagawa. "Optimal regret analysis of thompson sampling in stochastic multi-armed bandit problem with multiple plays". In: Proc. of ICML..
PMLR. 2015.
[16] Branislav Kveton et al. "Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits", In:
Proc. of AISTATS. 2015.
[17] T.I. Lai and H. Robbins. "Asymptotically efficient adaptive allocation rules". In: Advances in Applied Mathematics 6.1 (1985), pp. 4-2.
[18] Tze Leung Lai. "Adaptive Treatment Allocation and the Multi-Armed Bandit Problem". In: Ann. Statist. 15.3 (Sept. 1987). pp. 1091-1114.
[19] Pierre Perrault. "When Combinatorial Thompson Sampling meets Approximation Regret", In: Proc. of NeurIPS. 2023.
[20] Pierre Perrault et al. "Statistical Efficiency of Thompson Sampling for Combinatorial Semi- Bandits". In: Proc. of NeurIPS. 2020.
[21] Daniel Russo and Benjamin Van Roy. "An information -tteoreticc analysis of thompson
pling". In: The Journal of Machine Learning Research 17.1 (2016), pp. 2442-2471. [22] William R. Thompson. "On the likelihood that one unknown probability exceeds another in view of the evidence of two samples". In: Biometrika 25.3-4 (1933), pp. 285-294.
10

---

[23] Siwei Wang and Wei Chen. "Thompson Sampling for Combinatorial Semi- Mani-Bandits". In: Proc. of ICML. 2018.
[24] Raymond Zhang and Richard Combes. "On the Suboptimality Thompson Sampling in High Dimensions". In: Proc. of NeurlPS. 2021.

---

A
Glossary
List notation related problem setting
Notation
Description
Page
List
[T]
Set of time step until T {1, 21.....,
A
Combinatorial set of interest include {0, 1]a
A(t)
Action taken at time t Number of arms, dimension the problem Maximal size of decision Random vector of dimension representing the reward of each arm at time
d
m
X(t)
(())
Observation made by the learner at time é: Y(t) := A(t) O X(t)
The Hadamard operator of two vectors or matrix A,B the same size. (AQ B) Ai, Bi.j
The true unknown parameters
A
The optimal action
A
The reward gap between the optimal decision and the decision
Amin
The minimal reward gap, the reward gap between the optimal decision and of the second best decision
A max
The maximal reward gap, the reward gap between the optimal decision and of the worse decision Reward gap time of the action A(t) Sub-gaussian constant of the problem
A(I)
R(T,p"
Regret time T' for instance
List notations related to the algorithm and its analysis
Notation
Description
Page
List
p(t)
The empirical mean of the parameters at time
8(t)
Sample from the posterior distribution of μ² given by the algorithm at time t Number of times each arm has been selected until time Number of time the action A has been selected until time f Squared diagonal matrix containing the inverse of (tt).. The variance of the Thompson samples are proportional to V(t)
N(t)
()
V(t)
H(()
History up to time (The observation at time not included)
a(t)
First parameter of the Beta distribution at time Second parameter the Beta distribution at time / Bonus variance added to the Thompson samples distribution at time /
3())
s(0)
f(t)
Maximal concentration inequality function at time t, given by [10]
f(t)
Upper bound on the quantity g(t) * In([ Controls the deviation random part of the Thompson sample of the arm played.
M(t)
Vanishing term that controls how close the Thompson sample of the optimal action is to its mean during clean run Random i.i.d. Gaussian unitary vector of dimension d folowing A0 Ia) used to generate the Thompson samples time / Tail function of a standard Gaussian distribution Q(x) :- P(N(O, 1) x))
Z(1)
Q
(*(s))
Quantity related to the empirical mean of the best decision time Quantity related to the random part of the Thompson sample of the best decision at time S Counting process of the number of times the random part of the Thompson sample of the mean of the best decision deviated Polynomial term in m, d, 1/A 1/Amin, that represents the waiting time so that the best action is played more than fractional power of
S*(s)
((s)
7
Pi
g
12

---

Notation
Description
Page
List
P2
Polynomial term in m, 1/mmin; that represents the waiting time so that the average
g
mean of the best action is close its true mean
P
Polynomial term in m, d, 1/ min replacing the exponential term in the previous annalysis [10]
9
List of events
Notation
Description
Page
List
21
Event of clean run at time f
B,
The empirical mean deviated too much during the run until time The random vector (t) deviated to much during the run until time f
C,
Dr
The empirical mean the reward the optimal action deviated too much during the until time t
C,
The random part of the Thompson sample of best decision deviated too few times during the run until time t The algorithm plays suboptimal decision at time t At time t, the empirical mean of one of the arms played is too far from the true mean At time f, the Thompson sample of the decision played is too far from its true mean At time the random part of the Thompson sample of the decision played deviated too much
6
3:
31
6:
5t
List of the constants used in the paper
Notation
Description
Page
List
C
C V8+ 72
C2
C 233/4403 "Cav2
C3
C3 V1.238
5
Ca
C4 C2/8
C
C 23
C
C C4/2
C
C 768 constant in front of the log term in the regret bound
C'
C" = 2304 ln(2) constant in front of loglog term in the regret bound
a 3/4 (I²))(Ca)² ss 0.131
13

---

B Algorithm
Here the algorithm for Beta Combinatorial Thompson Sampling (Beta CTS) and Boosted Gaussian Combinatorial Thompson Sampling (BG-CTS) that we use in the paper.
Algorithm 1: Beta Combinatorial Thompson Sampling (Beta CTS) (with uniform prior)
Initialization: Uniform prior for beta distribution a(0) ((0) & [1]d;
for t 1, !....T T do
Draw (t()) (eta(a; 1), (t 1))
Compute A(t) arg max AEAA (=4
The environment draws (t(t) ~ Ber(u)))
Observe X(t) @ A(t), Receive reward X(t)
Update priors (t) = att 1) + (t) A(s) and B(t) = 1) - x
end
Algorithm 2: Boosted Gaussian Combinatorial Thompson Sampling (BG-CTS) (with improper prior)
Input: A> 0, 0
Initialization Vi [d], (0) = 0, (o( = 0 Uniform improper distribution on IR select
decisions until minne]j] N,(()= O. Update vi (d),N.(O), (4(0) accordingly. Generate
E [T], Vie [d], Z.(() ~ (00 1) i..dd.
for
7 do
Compute (1) (1 - 1) oV N.(1-1]
20(l)
(1(
Compute A(L) arg max nEA A (A))()))
The environment draws Vi E X((t).
Observe X(t) A(t), Receive reward A(t)
Update Vi E A(t), Nt(()= = N.(t - 1) + 1, (t) Na(t)=
X,(8) p. 1) +
N.())
N.()
end
C Proofs of main results
Here in 2 is the diagram of the regret decomposition on the complete event system green. In red the novel part of the proof that we introduce. It replaces the step 4 of the proof in [20) wich was inspired by (23) who we think addapted ideas from (2 and [14). We, in some sense, rediscovered those ideas for the case of combinatorial bandits by controling the numbre of times the optimal action is played
Lemma 4. We have
B 5, c A. (00))))))
And therefore (This is lemma 4 from 191)):
A(t)1 { A < 20 (200//11)AA0 |
Σ [E[T]
E[ f n B, 0 5. &
Σ
A
384 Immf(T)
Σ
A
Aimin
iE[d]
And
500o 300o"dlamj(T) < C dd T + C" dd Inm
mal In 2 2n +
In In T + 1152
Amin
Amin
A min
min
with C 768, O' 2304 1n
14

---

of to T O' af lai la In 1152 on In[1
Section 5.3.3
32mm
Ragret 21
31
3+
Regint (Lemmn Perreit 2022)
d'
Section 5.3.5
h
5.3.4
Regret [Lenna 9)
mux
Figure 2: Diagram of the proof of the main result
Anx max (P; (m, d,14 1/4 e), Pa (m, 1/baatn o)}
a
iPoprsaioo and 0
D2
Now imggkes Phoosston 2)
With panprroee 2
poootttnn 23
+4
4.2 2 4 e Im()) Cale
Propositonn 2
Regret aammm 9)
A.m $
15

---

Proof. 8 implies that we have
(
Σ (0:(1) 145)
iEA(t)
Σ (0,(t) Pc(t)) Σ (fi(t 1) -1-) AEA())
1EA())
Then 8r respectively 5h imply that
Σ (Pi(()) 14) 1 respectively keA(t))
(0:(1) Te((t)
ic (e
((8 Therefore, we have that
A(t) 20
Then because / increasing, we can use lemma 4 from 19 with 3G, 646 ((T). And we have that Vi, p, = 1 because We can also notice that because each arm is played at least once in our algorithm we do not have the first term in max that is counted elsewhere) We have that
not working triggering bandits. (B3rr and p; from their notation,
Σ E[A(1)1 (3e B S. [
A()) A(0) < 20088TTAATT
}
E
[E[T]
In(m)
< 646 f(T)
Σ
iimi
iE|d]
To make the formula more readable we use that for m >> 2 we have that 5 m >> 3 so that
3 + In(m)
In(m)
64T))(T)
Σ
3840 F(T)
Σ
imin
immin
ee[d]
se[d]
By definition of f. have that C 768. And assuming m 1, have that (m 2) +
in 2) < 3dm In 2 so C" can be taken as 2304 In and the last constant is 1152 In(2).
D Concentration results
Lemma 5. For t 2, let A > 0, let d, > 0. Let f(o:) : In( + mmnnt m7 In (1 + +) Then the event D, = (maxxef1] (s)s > 2 + A)f(d,)} happen with probability PD))) ō;
Proof. See lemma 3 of 110) Moreover, notice that in their lemma 6, they union bound all
the possible values of (N))eA [1] to get their result. (This is symbolized by their set D.))
Lemma 6 (Multiplicative Azuma Chernoff). Let (Wo)sen be a sum of random variable Vt
N W Σ X, Where (Xt)teN- verify that there exist (pe)teN eJ0, 1[ such that
WE N", P(X, 1/H(( 1)) = P
P(X: 0/H(t 1)) Pt-
t. Σ Pr 1=1
And (H(()) a filtration where VE N X, is H(t) measurable, We note my
16

---

Lett E N", 9g > 0 we have that
P ((, (1+ 8)ml) exp( 8mm
2 2+0
and A 1 >>6 >
P(W: < (1 -5mm)) < expl 62m
Proof.
For the first inequality, let Nº, A, E IR,, we have by Markov inequality:
P(W, 3 x) = P(AW 3 Az)
= 3 e²T))
< B(E Je ->ar
Let [t]. by definition of X, and using that Vx E R, exp(x)) > 1 + have that:
Exe - 1)] pse (1- (1-ps) ps)
= pa(c - 1) +
< exp(ps(e" - 1)).
Then, by the tower property of the expectation and induction:
B(e
E e e e Ax, [741]]
E [ exp(po(e* - 1))
Σ Ps(e -
< exp
SE[(]
Combining with the first equation, we have:
P(W: > x) < exp cxp (me(e) - 1) - Ax)
This is true for all x, A E R+ so by setting X = In(1 + 8) and x = (1 + 8)m, we have: :
P(W, (1 + 8)m;) exp (mlee" (n(+6) -1) (1 + In(1 + 6)m²)
< exp(mm(0 (1+ 5) In(1 6)))
8'mm
< exp( 2 8
Because Vg 0,5 - (1 + In + 8) 243
For the second inequality, let A R+:
P(W, x) P(- -xx)
P(ee-\W; c 220
< E(e AW, JE
Let [t], by definition of X, we have that
Ele AX |H(s 1)] p&e + (1 -1 Ps)
= =paee - -1)+1
<exp(ps(c - 1))
17

---

Then, by the tower property of the expectation and induction:
B()
E -e-AW-1FE [e Ax, 176-1]]
< E3 [e AWi-i exp(pa(e 1))
Σ ps(e - +E[[]
< exp
Combining with the first equation, we have:
P(W: < x) exp (mz(e 1) Ax)
This is true for all A E R+ by setting À = In(1 8) and (1 8) we have:
P(W, < (1 5)m,) < exp ( - 1) - (1 6) In(1 - 5)ml)
< exp(mm(-0
(1 (1-6) 6) In (n))
e
8)(1-5)
s'me
Lemma 7, Let [T], let us consider the event
B(t)
max
IV (s) (n" ((s)) l/x ov Slt
[E(c]]
We have that P((())) ft.
This result can be in part found in 16 in their proof of lemma 1.
Proof. We control it with the deviation of individual arms.
8lnt B,(() = is E [t], 1e; - [.(3)] NN Ni(s)
We have by double union bound, and because the rewards are o² subgaussian using Hoeffding:
P(B,(t)
Σ Σ P(K# P.(s) ov glat Ni(s) n) sEft ne|s]
n
Σ P(1 Σ (Xi(k) 14) ov8nln()
se [t] ne [
ke[m]
2t exp( - Int)
We have that B(()= C Uled Mi(l). So by union bound PP(((()) pr.
Lemma 8. Letie [d],e te [T], let us consider the event:
3(t) Bie A(t), P.(t) 15
min
2m
m
We have:
Amin
8m2 2
Σ 1
is A(1),t((1)
u
2m
m
Ami
26
SE|T9
And:
8m2
E
Σ
A() (3())
dA max
Amii 2r)
EE|T
This is result from 16) lemma 2 adapted to the 2² subgaussian case.
18

---

Proof. We use union bound and Hoeffding's inequality for o² subgaussian random variable. Let i E [d].
Ain 2m
E
A(t),Pi(t)
m
(T)
A Amin
iE A(t),
p4
2m
m
8
A min
<F
fi
N₂
2m
m
P
11
min
6
N₂
2m
72
min
exp
2
2m
Amin
exp
20
2m
exp
20²
Amin 2m
)
8mn
min
2c)
Then decomposing (t) with union bound of the {ie A(t), 10, over e [d]] we get the second result.
Amin
f and summing
Lemma 9. Let t E [T] we have
P (A A ())((()) (i(t)) > ov (8(())) (141)) ATOV()4(0))0)))) <
Which implies that P((((t)(((t) < t.
Defining:
f-+==(1+M (In (IA(t) + (m + 2) + d(In(2)) (n(()))((Inn)) m(1+dIn(2)) In (1+ 5)
we have that g(t) In((Alt) < f(t) and thus:
PP
A (L)(O()))))))) (()) 01/S//0ATTT0AA0000O))))
<
1
Finally:
?
Σ ( (5(1)
Amax 6
A
SE[T]
Proof. Let 0 by union bound we have:
19

---

P
A (t)(((t) -(()) > CO (
(1)((((t)) (()) > d2((E)
Σ P
( (0)V(0)A(()
AEA
C (2200)
Σ
P
OV ( (O)(()) > clH((t)
AEA
(AQQ(c)
IAI
exp( 2
2T
<| <|A|exp(- - 2 2)
By setting ([A]t) we have |A| exp
(-5) c2
hence the first result.
Then we have that : In(1AA) < (2 so that:
In (|Attt)
< In((A)) +
Int
< 1 + d1n(2)
Hence, the second result.
And by summing over l:
E
Σ
(()1
E EE [1 (5(()) [()I
tE
max E [P()))))
8E [T]
max f
E: [T
π
max
We recall simple tail bounds for Gaussian random variables. (see for instance 12
Lemma 10. Consider Z (O,, 1), then we have
400
P(Z > x) Q(x) V2T
c
$
dz
furthermore for all x > 0:
1 1 2
1 2 e < Q(x)
&
6
v
As well as:
Q(x) < - 2
It is also noted that by symmetry PP[ x) = (Q)
20

---

E
Functions Study
Lemma 1. Let be the following function:
m,,,m, X) (1+ X) (Int+ + (m + 2n In (1+ 2)
We have
Vt > m A N f(t,m, 2)
f(23, 1,
1.282.
m,))
f 2 1,
23
Proof.
f(t, (tt,mA A)
(1 + A) (Int + (m + 2) innnt 전タm In (1+ +
(1+ X) (In( + (m + 2) In T In (1+ 3
Using f.
we have that:
[(L, A)
Int (m + 2) Inlnt
S In(5)+ (m 2) In in(
1(1 m, 2)
Using f.
we have that for 23, Vm
f(1, m, A)
In + In
In 3n
But thanks to f. the right-hand side is decreasing in f, so:
f(,,m, A) 1 m,
f(23, 1,
Vt m N Ae R+
1.282.
f( 1,
Lemma 2. Let / b3 > 0 and let g R R+ be the following function
a a+t
g(1)
b+1 I.
Then Vt 3 (t) < g(0) <
Proof. Let Rt, we have
9(t) att
b+(
a b
b
b+1
b+1
=1 0
b+t
So is decreasing in t.
Lemma 3. The function
Int (m 2) 2)Innl
[(,
In(E) (m + 2) In In(
decreasing in m for > 23.
Which means that for 1. > 23, for Vm 2 1:
In + (m + 2) Int
In + In In()) ( + 3n
ln()) + (m + 2) In In(5))
21

---

Proof. Let [(m)
its derivative is: c+md
atmb
('(m) b(c + md) (a + mb)d (c md)2
bc ad
(c md)²
So (m(m) ii.f be ad O. Furthermore, In In è In( ())
Int < 0 for t >>
23 So
Vt 23, [(t, m) is decreasing m and > 23, f(t, m) < (1,,)..
Lemma 4. The function:
f(t) = In 3llln In(š) + 3l
decreasing.
Proof. We differentiate, and obtain
f()) <0
3
t
3 In( 5)) ) - tIn(g)
bm()))
(7
In
+
(lnt + 3lnln() 0.
Anl
We expend and simplify
1
1 +3 Inl 2)) ( iln(s)
3
+
In
(In + 3ln
t
tlnt'
2
(n(
(3l(
3lnt
llll
tin(5 ()
3lll(($)
31n 6
9 (l
9 Int (n(
+
tlmt
have
3lnt
3ltt
(ln(2)
tln())
iln
ilnt
and
3l Int
3 In(g)
and
9 In Int
9lnint
9lmln())
In
Ant
Anl
Therefore = (')) < and the function f is decreasing.
Lemma 5. Let >> 1 be a positive constant and let f be the following function:
c ln(1/2)
f(t) Q(c/In(t/22)
e2 (t/2)
2n
22

---

for t 2e we have
1
1
2+
f(t) >
(t/2)
2T 2c
22T 2
Proof. For 1 2e have that
c² (1((1122) so:
cy (//n(t/2)
1 1
1 c² In (1/2)
2c v (1(1122
For 1 > 2e we have that
exp (- In2(2((()2)) > exp (- (-2 In(t/2)). Therefore
vin(t/2)
S(1) > 2 + e² In(1/2)
cV ln(t/2)
(1/2) -
1 1
(1/2)
22 2c
Lemma f. 6.
In ln
Vt e, Int 2
Lemma f. 7. Let f.g the following funciion
[1,,m, X) = (1+ 2) (Int + (m + 2) Intl+
In (1+ )1+
f(t)
s(
Int
Fort> and 1 Å we have Int
thus
f(t) < (1 X) (2m + lnt,
and
g(t) < + A) (2m + 1).
Proof. For t > e, en >> Inlnt and for > 1 i. Int > In(1 + } thus the result
Lemma 8. Let a,c E Ri, two strictly positive constants such that >>> and define the
function f(t) = t" clnt. We have that Vt [ f(t) > 0. Furthermore, we have
( (1 !) cl
Proof. Let's study the function G(T) T - cln T T - s I (T). For T Se by using the concavity of the logarithm and differentiating T In (T) at the point &e we have that
c In (7)
in + (T (T-
- )
T
in -
Then for > Se
T - (7)
T
T
c
In
9
a
(1 1
c
T
Inc
23

---

1m 1-2
So for T
T f In (T) 0. Which means that by change of variable that for
im(=)
ف have that f(t) > 0. Hence, the first result.
t
t>
We have using that In(x) x:
In c 1
Finally, combined with the rest, we get the second result.
Lemma f. 9. Let > 0, a > the series Et=1 exp(-ct converges when T - +00 and
Σ exp
exp(- - cla)
Proof. Because the function exp(-ct") decreasing, by an integral test for convergence, have that:
+0
> 1=1
exp( (ap0-d))-
exp(-ct))dl
primitive of the function : t ~ exp(-ctt) is + co +00
tu
dt.
So:
cTa
ca +
exp(- -ct
t e
-
-0
r
24

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We introduced the setting and the assumption needed so that our main result applicable. We tried not to overstate results and be as close possible of our theoretical results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: As theoretical paper, we only claim that our result is true under some as- sumptions. We discussed the computational complexity of our method under the assumption that certain linear combinatorial problem can be solved efficiently.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
25

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We clearly stated the assumptions needed for our main result to hold. We provided complete proof of our results in the appendix with its lemmas. And we refer to previous works by citing them when needed.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
While this is not an experimental-focusee paper, we provided all the details needed to reproduce the plots found section 6: The parameters used, the number of arms, and the number of runs.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
26

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The paper generates synthetic data of the bandit model considered. The code is available https:/ggttubb.co//aay///aaaaaap Mismatthhdd Paradox
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurIPS code and data submission guidelines (https://nips) cc/
pub 1 /oddd////ooeuum ssi cesionPolice cyy) for more details.
While we encourage the release of code and data, understand that this might not be possible, so No an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
cttppsccccpbbleee gwwiiuuuuuuueeee CCteeoooSSSSaaa Sulbeeuummiiee comisssa aesionPollis oiyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The parameters of the algorithm and the environment are provided.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We plot the confidence intervals the regret in the simulation section, with standard deviations error intervals.
Guidelines:
27

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: Because of lack of space. Here they are: the experiments were run on a single core 19 (990H) laptop computer with 32GB of RAM with python 3. The experiments took less than hour to run.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http://ww......ooooocccccccceeee
Question:
Answer:
[Yes]
Justification:
We don't think that our research violates the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction)
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA].
28

---

Justification:
The work is for the moment very theoretical. It could be somehow used in some optimization algorithms but are far from real life applications.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This is theoretical work and no data or model was released.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer:[NA]
Justification:
Apart from python commonly available libraries, no asset was used.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
29

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, ppapersw sepersswihooe com/ dat asats s has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA].
Justification:
No new assets were introduced.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA].
Justification: Synthetic data was used.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA].
Justification: No human data used.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
30

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
31


Reviews:
[{"review_id": "xXjdTFylhc", "reviewer": "Reviewer_PpKq", "summary": "This paper proposes a modified version of posterior sampling that achieves optimal asymptotic regret bound, providing an algorithm through the methodology of Thompson Sampling that achieves such a bound.", "questions": "What is the guarantee for G-CTS?", "limitations": "adequately addressed", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is a technical paper, and the message is clear and intriguing. This paper validates the methodology of Thompson Sampling in the context of combinatorial bandits in terms of achieving polynomial dependence on the number of dimensions. The technique is novel, to my knowledge.", "weaknesses": "I am exactly doing this line of research, so I am not able to follow all the proof details. The paper is notation-heavy; for instance, there are nine events defined, eight of which are some sort of deviations. It is hard to parse and keep track of for a person outside the exact line of research.  I appreciate the authors' effort to explain, but I do believe in the main paper, the authors should write a more sketchy proof to highlight the key technique to prove novelty than writing a semi-rigorous proof: for instance, out of the eight deviation events, which are standard and bounded by conventional results? which are novel contributions? Of all the techniques involved, which is the key to this new result? In all, I feel it would be of great help if a clear logic line for the proof is demonstrated for people outside this line of research. At the current state, it is rather hard for me to evaluate the technical contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The decomposition under a clean run (event $\\mathfrak{A}$) is original. The decomposition of event $\\mathfrak{A}$  into  events $\\mathfrak{B},\\mathfrak{C},\\mathfrak{D}, \\mathfrak{E}$  is new. And how we handle event $\\mathfrak{E}$ is original. However, the handling of event  $\\mathfrak{B},\\mathfrak{C},\\mathfrak{D}$ are similar to prior work. The event $\\mathfrak{Z}, \\mathfrak{G}, \\mathfrak{F}, \\mathfrak{H}$ are not new and comes from [18]. However the way we handle $\\bar{\\mathfrak{G}} \\cap \\mathfrak{A}$ is.\n\nThe regret upper bound for G-CTS (Not SG-CTS) is given in the paper [18] Theorem 3. One needs to go to the appendices D, page 21, to see the exponential term. It states that under linear rewards, subgaussian noise of the rewards of the items (note that the noise can be correlated but known), the regret scale in $\\frac{d\\ln(m)^{2}\\ln(T)}{\\Delta_{\\min}}$. However, there is an exponential constant term. This is why we decided to add a little more exploration and to rework the analysis.", "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": "", "extra_scores": {}}, {"review_id": "Cd1ANALAMX", "reviewer": "Reviewer_npKN", "summary": "The authors present a new Thompson Sampling algorithm for linear combinatorial stochastic semi-bandits. The algorithm provably achieves a better finite-time regret than previous works, and specifically without an exponential dependency on the dimension of the problem.  The authors also present a \"paradox\" that shows using posterior knowledge is not always beneficial.", "questions": "* In line 26, do you mean $X(t)$ is uniformly distributed?\n* Can you provide summary of the algorithms as figures? It is hard to follow in the text what is the exact algorithm\n* Can you provide any intuitive explanation for the presented \"paradox\"?", "limitations": "The authors address the limitations of the paper.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "* The paper is presented clearly and the theory is sound.\n* The experiments suggest the algorithm is useful in practice.\n* The presented paradox is original and interesting", "weaknesses": "* The main result improves the known regret only for the term that does not depend on the time horizon, which is usually less interesting.\n* Code is not provided for the numerical experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We will provide the code in an open-source repository after the review process.\n\n* In line 26, $X(t)$ could be any random variable that is bounded in $[a,b]^{d}$. However, the one that maximizes its variance is the half Dirac in $a$ and $b$. The latter gives us the most deconcentrated random variable with a subgaussian parameter $(b-a)^2/4$. And any bounded random variable is subgaussian with parameter $(b-a)^2/4$.\n\n* Due to space constraints, the algorithms as figures were removed. They will be added back to the final version of the paper. You can find it in the pdf attached to the general answer.\n\n* One of the reasons behind the paradox is the fact that if the unknown parameter $\\theta$ lies in $[a,b]^d$ and we attempt to use TS to select decisions by assigning (for instance) a uniform prior over that set, then in many cases the algorithm will put too little probability mass on the set around the actual parameter $\\theta$ so that TS will never explore enough to discover $\\theta$ and will be stuck in an infinite loop of sampling suboptimal decisions. Indeed, when $d$ is large, any region that only contains vectors $\\theta$ such that $(1/d) \\sum_{i \\in [d]} \\theta_i$ is not close to $(b-a)/2$ will be assigned very little probability mass, from the law of large numbers. In the counter example of 2 actions, if the worst action is sampled first and gives a reward that is greater than the mean of the sum of the priors of the other action. Then, because of the prior, Thompson sampling will firmly believe it is the optimal action (again due to concentration). Therefore, it will not explore the other action, which is the best, for a very long time. [22] exploited this to create the example (see their section 3.2).", "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": "", "extra_scores": {}}, {"review_id": "NCgTmRmtyW", "reviewer": "Reviewer_4UPn", "summary": "This paper addresses Thompson Sampling for stochastic combinatorial bandits with sub-Gaussian rewards. In this area, previous work has identified the interesting phenomenon that some versions of Thompson sampling incur a per-instance regret which is exponential in the (maximum) number of arms pulled per round, m. This is not experienced by UCB-style algorithms, although those tend to have a worse computational complexity.\n\nThis paper furthers the discussion around the performance of TS in combinatorial bandits by identifying a variant which incurs only polynomial dependence on m. This is achieved by using a distribution with inflated variance to draw Thompson samples, rather than the 'true' posterior.\n\nThe paper contains non-trivial theoretical work to derive this bound, and contains an experiment demonstrating the superiority of the new TS approach over 'natural' variants and its comparable performance to ESCB, a state-of-the-art UCB-based algorithm.", "questions": "1. For which values of m and T specifically does the bound of this paper improve upon the bound in [18]? I appreciate this is problem dependent, but if this could at least be answered for the example considered in the experiments, that would be beneficial.\n\n2. The situation in the experiments seems as though it could also be tackled by a 2-armed bandit policy that receives full-bandit feedback on [0,d/2] and essentially ignores the combinatorial structure. If those rewards were scaled to [0,1] would the combinatorial algorithms be outperformed by algorithms for 2-armed bandits?\n\n3. When introducing B-CTS and G-CTS could you make clear if these are the variants to which the results of [18] and [22] apply?\n\n4. The conclusion that using a mismatched variance term outperforms the natural variance is an interesting one, and seems to mirror some findings in the bandit literature that randomisation strategies that are not TS-like or based on a posterior distribution (explicitly) can perform well in bandit problems (e.g. Perturbed History Exploration and bootstrapping based approaches, Kveton et al. (2019) and subsequent work). Can you comment on whether this polynomial dependence relies on using something close to the posterior, or whether other randomisation strategies would seem to be sensible candidates?\n\n5. Can you add to section 5 some clarity on what steps are novel and what are inspired by previous theoretical work? Some of the construction of a clear run seems to bear resemblance to (now) classic proofs for Thompson sampling (Agrawal and Goyal (2012), Kaufmann et al (2012), etc.) and the idea of using sample paths may have roots in other work too? (I'm not certain on that)\n\n\n\nAgrawal and Goyal (2012) http://proceedings.mlr.press/v23/agrawal12/agrawal12.pdf\nKaufmann et al (2012) https://arxiv.org/pdf/1205.4217\nKveton, Szepesvari, et al. (2019) https://arxiv.org/abs/1902.10089", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I find the research questions considered in this paper very interesting, and think that the multi-armed bandits community at NeurIPS will value this work. Thompson Sampling is a very popular algorithm for all kinds of bandit problems, and the fact that its most natural extension to combinatorial bandits has poor performance is an important issue. The theoretical results in this paper meaningfully contribute to the understanding of where 'natural' Thompson sampling is necessary and where it is only 'some notion of adding randomness' that is needed.\n\nThe theoretical work is based on state-of-the-art tools, does include some novel steps and is likely to be of its own interest. It does not appear to be a routine translation of existing tools.\n\nThe paper is mostly well-written and clear, and for someone acquainted with combinatorial bandits it is quite easy to follow.", "weaknesses": "The main weakness of the paper is that more could be done to articulate exactly where the results improve over existing bounds. The exponential and polynomial dependence on m is, as the paper states, in the constant order (wrt T) term. The main comparison between the results of the present paper and [18] is in terms of order results, and some constants are potentially large. It leaves the reader uncertain as to where in the space of T, m and d, the bound of this paper improves upon the bound of [18]. Adding some clarity around this would improve the paper, and help to establish the extent of its contribution.\n\nThere are some further points where I feel clarification could be made around theoretical and experimental results. I ask questions about these in the section below, and they are also central to me assessing the extent of the contribution.\n\nThere are some parts where the explanations are probably a bit too brief to be accessible to those without expert knowledge of the field - e.g. lines 52-64 discussing related literature use undefined technical terminology and discuss papers very quickly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1.\n    + From a theoretical point of view :\nWe share the same leading term in $\\log{T}$. However, for the exponential [18] vs. polynomial term, you need to compare $m^{8m}$ and $m^{20}  \\times d^{10}$. So, one can say that for $m>10$, our bound can be better. This does not take into account the term in $\\frac{1}{\\Delta_{\\min}}$. To be sure, if $m>20$, our bound is better.\n    + From an experimental point of view :\nThere is no way to reach the asymptotic bound in practice (for some parameter) of [18] because the logarithmic term in $T$ is too small compared to the exponential term. In theory, it is also impossible to reach our bound because $\\log(T)$ is very small compared to our polynomial term and for all practical $T$. However, it happens that in the simulation, the asymptotic regime is reached much faster than the theory predicts. Our simulations run for $m$ in a range $[5,65]$. One can already see the exponential gap happening around $m=13$.\n\n2. Yes. This is undead the case! However, one could imagine a slightly more complex set where one could not easily separate the arms into separate actions. (A set with many decisions with many arms but which share a few of them.) This would also create exponential regret in the Semi-bandit setting.\n\n3. For B-CTS and G-CTS, this is the version that [18] and [22] apply in the linear setting. However, in [18], they also provide a G-CTS with a slight modification to handle correlated subgaussian noise, but it still shows exponential regret.\n\n4. If we understand the reviewer correctly, we believe that the randomization that Kveton et al. (2019) use could indeed help an algorithm like Thompson sampling (B-CTS) to work a bit better without alleviating the exponential regret. In fact, those constant terms (polynomial or exponential) come from a kind of waiting time for the best action to be played enough time. As far as we know, randomization tries to lower the probability that the reward of the best action is underestimated. However, if the best action is not played enough, like in the two action examples, this would not help much. This randomization could help, for instance (in our case), so that the events $\\mathfrak{D}$ and $\\mathfrak{F}$ happen with a smaller probability or that we can have tighter bounds. This is indeed very interesting! \n\n5. The idea that, to control the behaviour of TS, one should lower the bound on the number of times the optimal decision is selected is undoubtedly not new. It was indeed exploited in Agrawal and Goyal (2012), Kaufmann et al (2012) for the multi-armed bandit setting. We also believe those ideas inspired [18], [21] in their proofs for the combinatorial setting. However, some more intricate proof techniques required to handle the exponential term are new.", "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": "", "extra_scores": {}}, {"review_id": "74DsMLrRX1", "reviewer": "Reviewer_yJpu", "summary": "The paper explores CTS for the linear combinatorial semi-bandit problem with subgaussian rewards. It introduces a novel TS algorithm that avoids exponential regret scaling with problem dimensionality. Theoretical bounds and experiments are provided.", "questions": "Can you explain better what makes your analysis work exactly ? What are the proof techniques that you used, and how this differs from [18] ? I put a good score for this paper as I think it worth it. But I can consider putting a lower score if a not satisfying answer is given to the questions.", "limitations": "The analysis only work for linear reward. Can you discuss why this is the case and how would it be possible to extend it the more general cases?", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper addresses a significant limitation in existing CTS algorithms by avoiding exponential regret scaling with problem dimensionality, which is a notable contribution to the field. It establishes new regret bounds that improve upon previous results in terms of finite-time performance. This is further shown experimentally. \n\nThe paper is well-organized and clearly presents its ideas.", "weaknesses": "The paper places significant emphasis on the \"mismatched sampling paradox,\" showcasing situations where a divergence between assumed and actual reward distributions can unexpectedly improve performance. While intriguing, this phenomenon isn't entirely novel, as it's known that Thompson Sampling (TS) can adapt to various posterior distributions. The paper's focus on this paradox, including its prominence in the title, may overshadow what could be considered the core contribution: a little boost on the exploration of CTS to better control the regret constant term.\n\nThe paper does not sufficiently clarify how the exploration boost is integrated into the analysis. The proof strategy is not well synthesized.\n\n[minor] Your main term scale with log(m)^2, but it is now possible to get a log(m) term instead. For example, use Lemma 4 in https://arxiv.org/pdf/2302.11182. I think this could be good to at least cite this paper mentioning that this could be done. line 203-204, I think the event D_t should contains the norm infty.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The Lemma 4 of  (https://arxiv.org/pdf/2302.11182) is very interesting. It could replace lemma 10 from [9] and provide us with a better bound with a $\\ln(m)$ instead of a $\\ln(m)^2$. We will make sure to correct and add that in the final version of the paper.\n\n$U^\\star(s)$ is a scalar; we do not believe an infinity norm is needed. (Or maybe you meant an infinity norm over the vector $(U^\\star(s))_{s\\in[t]}$ ?)\n\nThe novelty of our work is to target the exponential term in the regret of [18] and mainly their step 4 that we replaced completely by intersecting the event $\\mathfrak{G}$ ($\\mathfrak{C}$ in their notation) with the event of the clean run $\\mathfrak{A}$ that we introduced.\n\nOur proof relies on a maximal concentration inequality in the same spirit as Lemma 3 of  [9] to bound the maximal deviation of the estimate of the reward of the best action (event $\\mathfrak{D}$). This result was not used in [18] and is a key element in our proof.\nSome more basic concentration inequalities are used to control the probability of event $\\mathfrak{B}, \\mathfrak{C}$. And for the event $\\mathfrak{F}$ like in [18]. The way the event $\\bar{\\mathfrak{H}}$ is handled is not new and is already handled by the literature [18], or [9] and now (https://arxiv.org/pdf/2302.11182). \n\n\nWe are not convinced that this technique of added exploration could be used in other reward settings to alleviate the exponential regret. Even for 1-Lipshitz reward functions, the task seems rather tedious. First, we would need to find a way to extend the definition of $f$ to $\\mathbb{R}^d$ and not $[a,b]^d$. For instance, the example of theorem 6 of [22] $f$ is Lipshitz on $[0,1]^d$ but not on $\\mathbb{R}^d$. Furthermore, suppose one tries to apply SG-CTS to that example. In that case, we believe that in order to explore the optimal decision, all the Thompson samples would need to be simultaneously greater than a certain threshold. This is a very low probability set in high dimensions. We believe that, in general, the structure of Lipshitz functions could induce a lot of confusing sets of parameters where the initial prior would put a very small probability. If that were to happen, Thompson sampling would need an exponentially long time to explore all those zones. It is what happens in step 4 of [18]. Our method works for linear functions because there are essentially only two sets to be explored, and our posterior still puts enough probability on both of them.", "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": "", "extra_scores": {}}]

Author rebuttal:
We want to thank the reviewers for their questions and remarks; we will take them into account to improve the paper's clarity. Here is a general answer to all the questions asked by the reviewers.

The main contribution of our paper was to find a way to circumvent the exponential term in the work of [18] in step 4 of his analysis, page 13. We replace it with a polynomial term in Theorem 1. The exponential dependency is due to the fact that they control some of the regret by the expected time necessary for **all** of the Thompson samples to be simultaneously greater than a threshold, and this expected time scales exponentially in the ambient dimension. That in high dimension is an exponentially small set in probability. In fact, for the best action to be played, we only need the mean of the Thomspon samples to be greater than a certain threshold. Furthermore, we needed to add more variance to them to control some deviation of the estimate of the rewards.  

Below are some of the original proof elements we came up with to circumvent the problem:

1. First, we show that what we name a clean run happens with a high probability. Proposition 2. The way we decompose ${A^{\star}}^\top \theta(s)$ is original with the introduction of the random part of the Thompson sample $Z(t)$. The treatment of the event $\mathfrak{E}$ is original. It is a mix between a deconcentration inequality (i.e. a lower bound on the probability that a random variable is far from its expectation), a study of the function $f(t)/g(t)$, and a multiplicative Azuma Chernoff bound. The multiplicative Azuma Chernoff bound is, we think, classic, but we did not manage to find a reference for the direction of inequality, which we proved in the appendix.
 
2. Second, under the clean run event, we show that the optimal action is played at least a certain number of times. This is done in Proposition 3. It combines a concentration result from [9] and our last result.
 
3. Last, The subsubsection 5.3.2 is new and uses the last two results. It replaces the step 4, page 13 of [18] 


It was discussed that a graph representing the event and the regret decomposition, highlighting the novel contribution, would be added to the paper's appendices. If the reviewers believe that it facilitates the understanding of the proof, we propose adding it to the paper's final version.

We hope this answer will help the reviewers understand our work's novelty. Please do not hesitate to reach out for more details if needed.

Here are the algorithms in figure form.

Meta-review: The paper addresses a core problem in combinatorial multi-armed bandit algorithms -- of controlling the scaling of regret with the problem size. It contributes a carefully designed variant of Thompson sampling (TS) that alleviates the known exponential scaling of naive TS' regret with the number of arms. It also raises an interesting paradox about when TS is allowed to use mismatched likelihood distributions and can perform better than the vanilla one. 

All the reviewers (and I) agree that the paper makes solid contributions to bandit algorithm design; thus I recommend the paper for acceptance.
Decision: Accept (spotlight)