Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox

Authors: raymond  zhang
richard  combes
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 16:27:08

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

Main paper: 
 introduction and setting: 
 We consider the linear combinatorial bandit problem with semi-bandit feedback: At time t P rT s :" t1, ..., T u a learner selects an action Aptq P A where the set of available actions A Ă t0, 1u d is a known combinatorial set, i.e., a set of binary vectors. Then the environment draws a random vector Xptq P R d , and the learner then observes Y ptq " Aptq d Xptq, where d denotes the Hadamard (element-wise) product, and the learner obtains a reward of Aptq J Xptq. We assume that the vectors pXptqq tě1 are drawn i.i.d. from some distribution with expectation EpXptqq " µ ‹ and that the entries of Xptq are independent. The vector µ ‹ lies in some Θ Ă R d and is initially unknown to the learner. The learner wants to minimize the regret:RpT, µ ‹ q :" T max APA ! A J µ ‹ ) ´E » - ÿ tPrT s Aptq J µ ‹ fi fl " E » - ÿ tPrT s ∆ Aptq fi fl .Where A ‹ P arg max APA tA J µ ‹ u is the optimal action and ∆ A :" A ‹J µ ‹ ´AJ µ ‹ is the reward gap between action A and optimal action A ‹ . The regret is 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 is unique. To state regret bounds, we use the following notation. We denote by ∆ min :" min APA:∆ A ą0 ∆ A the minimal reward gap and ∆ max :" max APA ∆ A the maximal reward gap, ∆ptq :" ∆ Aptq the reward gap of the action selected at time t, m :" max APA }A} 1 the maximal size of an action.The regret depends on the distributions of the random vector Xptq, which generates the rewards, and we will assume throughout the paper that Xptq is σ 2 -subgaussian so that for all λ P R d :Erexppλ J Xptqqs ď e λ J µ ‹ `}λ} 2 2 σ 2 2. This assumption holds in many scenarios of interest, for instance, when Xptq P ra, bs d with σ 2 " pb ´aq 2 {4, or when Xptq is normally distributed with a covariance matrix smaller than σ 2 I d . We assume that σ 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 π 0 over Θ, a likelihood function and π t the posterior distribution of µ ‹ at time t knowing the observations and the actions up to time t: π t pµq " ś sPrt´1s ś iPrds rA i psq pX i psq, µ i q `p1 ´Ai psqqsπ 0 pµq ş Θ ś sPrt´1s ś iPrds rA i psq pX i psq, µ i q `p1 ´Ai psqqsπ 0 pµqdµ The TS algorithm with prior π 0 and likelihood consists in sampling θptq from distribution π t , and select action Aptq P arg max aPA A J θptq. The random vector θptq, called a Thompson Sample, acts as a proxy for the unknown µ ‹ and guides the exploration.We will show how TS behaves with either Gaussian likelihood px, µq " p2πq ´1{2 e ´px´µq 2 {2 or Bernoulli likelihood px, µq " 1tx " 1uµ `p1 ´µq1tx " 0u in the next sections. If the likelihood pX i psq, µ i q is selected as the distribution of X i psq knowing µ i then we say that TS is natural. If the likelihood pX i psq, µ i q is different from the distribution of X i psq knowing µ i , 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 Xptq 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 π 0 can be chosen in various ways, for instance, Jeffrey's non-informative prior. It can even be chosen as an improper prior, where ş Θ π 0 pµqdµ " `8, as long as the integral in the definition of π t is well-defined.TS is usually computationally simple to implement as it requires a 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 to perform well numerically.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 is applicable. We tried not to overstate our results and be as close as 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 in 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 as long as it is clear that these goals are not attained by the paper. 
related work and contribution: 
 Combinatorial bandits are a generalization of classical bandits studied in [17] . Several asymptotically optimal algorithms are known for classical bandits, including the algorithm of [18] , KL-UCB [5] , DMED [13] and TS [14, 22] . Other algorithms include the celebrated UCB1 [4] . Numerous algorithms for combinatorial semi-bandits have been proposed, many of which naturally extend algorithms for classical bandits to the combinatorial setting. CUCB [6, 16] is a natural extension of UCB1 to the combinatorial setting. ESCB [8, 10] is an improvement of CUCB, which leverages the independence of rewards between items. AESCB [9] is an approximate version of ESCB with roughly the same performance guarantees and reduced computational complexity. TS for combinatorial semi bandits was considered in [11, 15, 20, 21, 23] while TS for linear bandit was studied in [1, 3] . Also, combinatorial semi-bandits are a 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 b een extensively studied, e.g., [21] .Three types of regret bounds exist in the literature: RpT, µ ‹ q is the problem-dependent regret, i.e., the regret of the learner on the particular problem instance defined by µ ‹ . The minimax regret is max µPΘ RpT, µ ‹ q and the Bayesian regret E µ ‹ rRpT, µ ‹ qs 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 ∆ min , the minimal gap.The paper [16] showed that the problem-dependent regret of CUCB is upper bounded by O ´dm ln T ∆min ānd its minimax regret is upper bounded by Op ? σ 2 dmT ln T `dmq. [10] showed that the problem- [20] showed that the problem-dependent regret of TS is upper bounded byO ˜σ2 dpln mq 2 ∆ min ln T `dm 3 ∆ 2 min `m ˆσ m 2 `1 ∆ min ˙2`4m ¸.While this bound is almost optimal in the asymptotic regime where T Ñ 8, it is exponentially suboptimal in the finite time regime since the last term of this expression scales exponentially with m. Unless one assumes a particular type of action set as in [15] , all the known generic regret upper bound for TS in the literature [11] , [23] , [20] feature an exponential dependency on m. [24] further showed that the problem-dependent regret of TS for some simple combinatorial set can be lower bounded by an expression scaling exponentially in m, RpT, θq ě ∆ min 4p ∆min p1 ´p1 ´p∆min q T ´1q, with p ∆min " exp# ´2m 9 ˆ1 2 ´p ∆ min m `1 ? m q ˙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 in 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.We propose a new variant of TS with a regret upper bounded by:O ˆσ2 d ln m ∆ min ln T `σ2 d 2 m ln m ∆ min ln ln T `P ˆm, d, 1 ∆ min , ∆ max , σ ˙ẇhere P is a polynomial in m, d, 1 ∆min , ∆ max .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 pm, d, 1{∆ min , ∆ max , σq will be much smaller than the last term in the bound of [20] m `σpm 2 `1q{∆ min ˘2`4m which is exponential in m. To design our variant, we add a slight exploration boost to TS, which vanishes as T Ñ 8 but significantly impacts the algorithm behaviour when T is moderate and m is large. Also note that the improvement in the ln m term comes from a direct application of a result in [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 are an essential contribution to the analysis of TS and enable us to show that with high probability, TS will sample the optimal action at least Ωpt α q times with α ą 0. This number serves to control the transient behaviour of TS.(iii) As a by-product, we show the mismatched sampling paradox of TS: in some cases, mismatched TS performs exponentially better than natural TS. For instance, in a problem where Xptq has Bernoulli distribution, a learner using a uniform (improper) prior and a Gaussian likelihood can perform exponentially better than a learner using a Beta prior (which includes Jeffreys' 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.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: As a theoretical paper, we only claim that our result is true under some assumptions. We discussed the computational complexity of our method under the assumption that a certain linear combinatorial problem can be solved efficiently.Guidelines:• The answer NA means that the paper has no 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 a 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 on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
algorithms: 
 In this section, we present three TS algorithms: B-CTS (Beta-Combinatorial Thompson Sampling), which is TS with a beta prior and a Bernoulli likelihood, G-CTS (Gaussian-Combinatorial Thompson Sampling) which is TS with a uniform (improper) prior and a Gaussian likelihood, and finally BG-CTS (Boosted Gaussian-Combinatorial Thompson Sampling), an algorithm we propose by introducing a carefully chosen exploration boost in G-CTS.We use the following notation to state algorithms. We define the statistics N ptq :" ř sPrt´1s Apsq, the vector containing the number of times each item has been selected, M A ptq :" ř sPrt´1s 1 tApsq " Au the number of times action A has been selected until t, V ptq :" D ´1 N ptq the diagonal matrix whose diagonal elements are p1{N 1 ptq, ..., 1{N d ptqq, p µptq :" V ptq ř sPrt´1s X i psq d A i psq the empirical average estimator for µ ‹ . We denote by Hptq " pApsq, Apsq d Xpsqq sPrt´1s the history which contains all the information collected by the learner up to time t, and which includes both the observations and the selected actions. For two vectors α, β in pR `qd we denote by Betapα, βq " Â d i"1 Betapα i , β i q the distribution of a vector with independent entries, and where the i-th entry is Betapα i , β i q distributed.B-CTS (see 1 in the algorithm format) considers the prior π 0 " Betapαp0q, βp0qq where αp0q, βp0q, are two vectors in R d chosen by the learner and the Bernoulli likelihood px, µq " 1tx " 1uµ p1 ´µq1tx " 0u. If αp0q " βp0q " p1, ..., 1q, then the prior π 0 is uniform over r0, 1s d . If αp0q " βp0q " p1{2, ..., 1{2q, 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 π t is also a Beta distribution so that the Beta-CTS selects the action: Aptq P arg maxG-CTS considers the improper prior π 0 which is constant and equal to 1{σ on all R d and Gaussian likelihood px, µq " p2πσ 2 q ´1{2 e ´pX´µq 2 {p2σ 2 q , where σ 2 is the variance. Of course, since π 0 is improper, for π t to be well-defined, we require that enough samples have been collected so that N ptq ě 1. This is easily achieved by selecting d actions A 1 , ..., A d that cover A in the sense that ř iPrds A i ě 1, and initializing the algorithm by sampling each of them once. In G-CTS, the posterior distribution π t is also a Gaussian distribution so that the G-CTS selects the action: Aptq P arg max APA A J θptq with θptq " N pp µptq, σ 2 V ptqq.BG-CTS (see 2 in the algorithm format) is a modification of G-CTS that we propose and that selects the action Aptq P arg max APA A J θptq with θptq " N pp µptq, 2gptqσ 2 V ptqq with gptq :" f ptq ln t and f ptq :" p1 `λq ´ln t `pm `2q ln ln t `m 2 ln ´1 `e λ ¯ānd λ P R `is an input parameter of the algorithm. BG-CTS behaves like G-CTS with a timevarying boost in its exploration denoted by gptq. This boost asymptotically behaves like a constant lim tÑ8 gptq " 1 `λ. This boost ensures a 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 gptq is not arbitrary and is derived from the self-normalized concentration inequalities that control the large deviations of vector p µptq. To make our analysis clearer, we will assume that there exists an exogenous process pZptqq tě1 of i.i.d. N p0, I d q vectors that serves as the random generator number for the Thompson samples with θptq " p µptq `σa 2gptqV 1 2 ptqZptq. This decomposition is useful for separating the algorithm's randomness from the bandit environment's randomness. We notice that for all s t, Zpsq and the history Hptq are independent. Furthermore, we call Zpsq the random part of the Thompson sample, A J θptq the Thompson sample of action AQuestion: For each theoretical result, does the paper provide the full set of assumptions and a 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 crossreferenced. • All assumptions should be clearly stated or referenced in 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 a short proof sketch to 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. 
main result: 
 We now state Theorem 1, our main result. Theorem 1. For λ " 1, and σ 2 subgaussian rewards, the regret of BG-CTS is upper bounded by:RpT, µ ‹ q ď C σ 2 d ln m ∆ min ln T `C1 σ 2 d 2 m ln m ∆ min ln ln T `P ˆm, d, 1 ∆ min , ∆ max , σ ˙(1)with C, C 1 universal constants and P a polynomial in m, d, 1 ∆min , ∆ max , σ.Theorem 1 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 lim sup T Ñ8RpT,µ ‹ q ln T , but also a polynomial dependency in m, d, 1 ∆min , ∆ max , σ. This result predicts that BG-CTS performs much better than other TS variants in the regime where the time horizon T is moderate and the decision size m is large.A consequence of Theorem 1 combined with prior known results of [24] 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 m " d{2 written p1, ..., 1, 0, ..., 0q and p0, ..., 0, 1, ..., 1q and Bernoulli rewards. Suppose the learner attempts to leverage that she knows the rewards are Bernoulli and that the parameter space is r0, 1s d . She will employ a uniform prior over r0, 1s d 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 d. Furthermore, Bernoulli rewards are σ 2 subgaussian with σ 2 1{4 as stated above, so our regret upper bound for BG-CTS applies to this example.At first glance, it seems outright absurd to use a prior whose support is the whole of R d instead of the actual parameter space r0, 1s d , and using a Gaussian likelihood, which is continuous when the rewards are binary, but this paradoxically gives exponentially better performance. This paradox leads us to 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.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: While this is not an experimental-focused 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. 
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 self-contained, we reproduce (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 .A fundamental idea of our analysis is to consider the event A t where both events occur : @s P rts, @A P A :|A J θptq ´AJ µ ‹ | ď C 1 σ ? m ln tA J V 1 2 psqA,and |ts P rts :A ‹J θpsq ě A ‹J µ ‹ u| ě C 2 t α Where C 1 " ? 8 `?72, C 2 " 1 2 13{4`C 2 3 {2 C3 ? 2π, pC 3 q 2 " 1.238, α " 3{4 ´p1{2qpC 3 q 2 « 0.131.When A t occurs, we say that we observe a clean run up to time t. A clean run up to time t implies that the Thompson sample of any action A at any time s P rts cannot exceed the sum of its expected value and a bonus proportional toA J V 1 2ptqA, 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 ‹J µ ‹ .We first now show that most runs are clean, i.e., clean runs occur with high probability. Proposition 2 states that the probability of a non-clean run up to time t is much smaller than 1{t, and therefore non-clean runs cause little regret.Proposition 2. For all t ě C 5 , we have PpA t q ě 1 ´4dt ´2 ´t´1 pln tq ´2 ´e´C4t α with C 4 " C 2 {8 and C 5 " 23.Proof : The proof is relatively technical, and involves decomposing A t according to the fluctuations of θptq and p µptq. We decompose the Thompson sample of the optimal action as follows:A ‹J θpsq " A ‹J µ ‹ `rU ‹ psq `S‹ psqs b A ‹ J V psqA ‹ with U ‹ psq :" A ‹J pp µpsq ´µ‹ q b A ‹ J V psqA ‹ and S ‹ psq :" σ a 2gpsq A ‹J V 1{2 psqZpsq b A ‹ J V psqA ‹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 B t :" tmax sPrts }V ´1 2 psqpµ ‹ ´pS ‹ psq ě σ a 2f ptqu| ď C 2 t α u D t :" tmax sPrts U ‹ psq ě σ a 2f ptqu.Each of those events can be interpreted as follows. B t means that the empirical mean of some item deviates from its expected value at least once, C t means that the randomization in the Thompson sample is abnormally large at least once, D t implies that the empirical mean of the optimal action deviates from its expected value at least once, and E t means that there exist too few instants at which S ‹ ptq is reasonably large.Assume that none of B t , C t , D t , E t occur. For all A P A and all s P rts:|A J θpsq ´AJ µ ‹ | |A J pp µpsq ´µ‹ q| `|A J pθpsq ´p µpsqq| ď C 1 σ ? m ln tA J V 1{2 psqAsince if B t does not occur:|A J pp µpsq ´µ‹ q| ď σ ? 8 ln tA J V 1{2 psqAand if C t does not occur and because gptq ă 2p2m `1q ă 6m see lemma f. 7:|A J pθpsq ´p µpsqq| ď σ ? 72m ln tA J V 1{2 psqAFurthermore if D t and E t do not occur, there exists at least C 2 t α instants such that S ‹ psq ě σ a 2f ptq and U ‹ psq ě ´σa 2f ptq, which implies A ‹J θpsq ě A ‹J µ ‹ . This means that:|ts P rts : A ‹J θptq ě A ‹J µ ‹ u| ě C 2 t αTherefore A t occurs, and we have a clean run. Hence PpA t q ě 1 ´PpB t q ´PpC t q ´PpD t q ´PpE t q.We now upper bound the probability of each event separately.Using a union bound PpB t q ď ř iPrds P ´max sPrts a V i psqpµ ‹ i psq ´p µpsqq ě σ ? 8 ln t ¯ď 2dt ´2. We used the concentration inequality first derived by [16] in their analysis of CUCB and recalled in lemma 7.Using a union bound and a Chernoff bound for the Gaussian distribution (lemma 10), wheres Q is the tail function of the standard Gaussian distribution :PpC t q ď ÿ iPrds ÿ sPrts P ´|Z i psq| ě ?6 ln t ¯ď 2tdQp ? 6 ln tq ď 2td expp´3 ln tq " 2dt ´2We have for t 2, PpD t q ď t ´1pln tq ´2 from the concentration inequality derived by [10] in their analysis of ESCB and recalled in lemma 5.In order to control the probability of E t , consider the following counting process:W psq " ÿ uPrss 1tS ‹ puq ě σ a 2f ptquWe wish to show that, with high probability, W psq ě C 2 t α . One may readily check that W psq is a sum of binary variables and that its conditional expected increment verifies:ppsq " EpW psq ´W ps ´1q|Hpsqq " PpS ‹ psq ě σ a 2f ptq|Hpsqq " Qp a f ptq{gpsqq since, conditional to Hpsq, S ‹ psq has a gaussian distribution with mean 0 and variance 2gpsq. Let us lower bound of the sum of p. By considering t ě C 5 we have ÿ sPrts ppsq ě pt{2qppt{2q " pt{2qQp a f ptq{gpt{2qq ě pt{2qQpC 3 a lnpt{2qq ě 2C 2 t α using the fact that p is increasing in s, and the study of f ptq gpt{2q done in lemma f. 1 , and lemma 10 on the asymptotic behaviour of the Q function.We can now conclude by applying a multiplicative Azuma-Hoeffding style bound to W psq presented in lemma 6 in the appendix. With C 4 " C 2 {8 we have :PpE t q ď P pW ptq ď C 2 t α q ď P ¨W ptq ď p1{2q ÿ sPrts ppsq ‚ ď e ´1 8 ř sPrts ppsq ď e ´1 8 C2t α " e ´C4t αAdding up the four previous bounds, for all t ě C 5 , PpA t q ě 1 ´4dt ´2 ´t´1 pln tq ´2 ´e´C4t α .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 a 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 we believe to be missing in the previous analysis of [20] ) and will allow us to control the transient behaviour of the algorithm. Proposition 3. For t ě P 1 pm, d, 1 ∆min , σq, if A t occurs, then we must haveM A ‹ ptq ě C 6 t α and A ‹J θptq ě A ‹J µ ‹ ´hptq. With P 1 a polynomial in m, d, 1 ∆min , σ, C 6 " C 4 {2, and hptq " C 1 σm b m ln t C6t α . It is noted that lim tÑ8 hptq " 0Proof: 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 ∆ min :ˇˇ!C1σ ? m ln tA J psqV 1 2 psqApsq ∆ min )ˇˇˇď ÿ iPrds ˇˇˇˇ# i P Apsq, C 1 σ d m ln t N i psq ∆ min m +ˇˇˇˇď d C 2 1 σ 2 m 3 ln t ∆ 2 minAnd since we have a clean run: |ts P rts : A ‹J θpsq ě A ‹J µ ‹ u| ě C 2 t α . At those times, if the variance term of the action played is less than ∆ min , then it means that the optimal action has been played due to the first condition of A t . So we get :M A ‹ ptq ą C 2 t α ´d C 2 1 σ 2 m 3 ln t ∆ 2 min ě C 6 t α With C 6 " C 2 {2 for t ě P 1 pm, d, 1 ∆min , σq :" `1 α ˘1`2 α `1 ´1 e ˘´1{α ´C2 1 C2 ¯1`1{α ´dσ 2 m 3 ∆ 2 min ¯1`1{αusing lemma f. 8. Recall that under A t :|A ‹J θptq ´A‹J µ ‹ | C 1 σ ? m ln tA J V 1{2 psqA.Since M A ‹ ptq ě C 6 t α has been selected at least C 6 t α times up to time t, we haveA ‹J V 1{2 A ‹ ď m ?C6t α so we get the announced result :|A ‹J θptq ´A‹J µ ‹ | ď C 1 σm c m ln t C 6 t α " hptqWe can now analyze the regret. Let us define some more events at time t: The event Z t means a suboptimal play. F t implies that the empirical mean of one of the items in the action selected at time t deviates from its expectation. G t means that the Thompson sample of the decision played is far from its true value, and finally, H t is for when the Thompson sample from the arm played is far from its empirical mean. The complete event system decomposed as follows.Z t :" t∆ptq ą 0u H t :" " A J ptqpθptq ´p µptqq ą σ b 8 f ptqA J ptqV ptqAptq * G t :" " A J ptqpθptqUsing proposition 2 we have that Pp s A t q ď 4dt ´2 `t´1 pln tq ´2 `e´C4t α . Then we can use the fact that řtPN ‹ 1 t 2 " π 2 6 , ř tPN ‹ 1 tpln tq 2 ă 4.And furthermore, with lemma f. 9 we have thatř tPN ‹ e ´C4t α ă C ´1{α 4α Γp 1 α q. Therefore, the regret caused by s A t is upper bounded by:ÿ tPrT s Er∆ptq1 s A t ( s ă ∆ max ÿ tPrT s Pp s A t q ă ∆ max « d 2π 2 3 `C´1{α 4 α Γ ˆ1 α ˙`4 ff . 5.3.2 Regret due to s G t X A tWe use proposition 3 and we get that for t ě P 1 pm, d, 1{∆ min , σq, A ‹J θptq ą A ‹J µ ‹ ´hptq. Combining with event s G t , we know that when hptq ă ∆ min {4, the only action that can be played is the optimal one. We recall the formula of hptq " C ÿ tPrT s Er∆ptq1 s F t X G t X s H t ( s 384σ 2 d ln m f pT q ∆ min and 384σ 2 d ln m f pT q ∆min ă C σ 2 d ln m ∆min ln T `C1 σ 2 d 2 m ln m∆min ln ln T `1152 σ 2 md 2 ln 2 lnp1`eq ∆min .Finally, we can put everything together and obtain the regret upper bound found in 1 with the following polynomial constant term :P ˆm, d, 1 ∆ min , ∆ max , σ ˙" ∆ max « C ´1{α 4 α Γ ˆ1 α ˙`4 ff `d∆ max ˆ32m 2 σ 2 ∆ 2 min `5π 2 3 ∆max ˆP1 ˆm, d, 1 ∆ min , σ ˙`P 2 ˆm, 1 ∆ min , σ ˙˙`1152 σ 2 md 2 ln 2 lnp1 `eq ∆ min .The degree of this polynomial depends on 1 `1{α ă 10 with α " 0.131. So the degrees of the polynomial in m, d, 1{∆ min , σ 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 1 , A 2 ( of size m " d{2 with A 1 " p1, ..., 1, 0, ..., 0q and A 2 " p0, ..., 0, 1, ..., 1q. This action set exhibited exponential regret in [24] . We set µ ‹ " p0.7, ..., 0.7, 0.9, ..., 0.9q with a 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 r0, 1s, which puts more weight around the extremities of r0, 1s, increasing exploration.  
conclusion: 
 We proposed a 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 a 2 decisions Bernoulli reward example.List The optimal action ∆ AThe reward gap between the optimal decision and the decision A ∆ minThe minimal reward gap, the reward gap between the optimal decision and one of the second best decision∆ maxThe maximal reward gap, the reward gap between the optimal decision and one of the worse decision ∆ptq Reward gap at time t of the action Aptq σ Sub-gaussian constant of the problem RpT, µ ‹ q Regret at time T for instance µ ‹ List notations related to the algorithm and its analysis Input: λ ą 0, σ ą 0 Initialization : @i P rds, N i p0q " 0, p µ i p0q " 0 Uniform improper distribution on R d , select decisions until min iPrds N i ptq ą 0. Update @i P rds, N i p0q, µ i p0q accordingly. Generate @t P rT s, @i P rds, Z i ptq " N p0, 1q i.i.d. for t " 1, ..., T do Compute θ i ptq " p µ i pt ´1q `σb 2gptq Nipt´1q Z i ptq.Compute Aptq " arg max APA tA T θptqu.The environment draws @i P rds, X i ptq.Observe Xptq d Aptq, Receive reward Aptq T Xptq.Update @i P Aptq, N i ptq " N i pt ´1q `1, p µ i ptq " Niptq´1 Niptq µ i pt ´1q `Xiptq Niptq . end 
safeguards: 
 Question: Does the paper describe 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)? 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 a 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 not require this, but we encourage authors to take this into account and make a 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 is used and, if possible, include a URL.• 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. 
 
 Appendix: Here in 2 is the diagram of the regret decomposition on the complete event system in green. In red is 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 :s F t X G t X s H t Ă " ∆ t ă 2σ b 8 f ptqA J ptqV ptqAptq * .And therefore (This is lemma 4 from [19] ):ÿ tPrT s Er∆ t 1 s F t X G t X s H t ( s ď ÿ tPrT s E " ∆ptq1 " ∆ t ă 2σ b 8 f ptqA J ptqV ptqAptq * . 384σ 2 ln m f pT q ÿ iPrds 1 ∆ i,min .And 500σ 2 d ln m f pT q ∆ min ă C σ 2 d ln m ∆ min ln T `C1 σ 2 d 2 m∆ptq ă 2σ b 8 f ptqA J ptqV ptqAptqThen because f is increasing, we can use lemma 4 from [19] with β i,T " 64σ 2 f pT q. And we have that @i, p i " 1 because we are not working on triggering bandits. ( β i,T and p i are from their notation, We can also notice that because each arm is played at least once in our algorithm we do not have the first term in d∆ max that is counted elsewhere) We have that :ÿ tPrT s Er∆ptq1 s F t X G t X s H t ( s ÿ tPrT s E " ∆ptq1 " ∆ptq ă 2σ b 8 f pT qA J ptqV ptqAptq * 64σ 2 f pT q ÿ iPrds 3 `lnpmq ∆ i,min .To make the formula more readable we use that for m ą 2 we have that 5 ln m ą 3 so that :64σ 2 f pT q ÿ iPrds 3 `lnpmq ∆ i,min ă 384σ 2 f pT q ÿ iPrds lnpmq ∆ i,minBy definition of f , we have that C " 768. And assuming m 1, d 3 we have that pm `2qp1 d ln 2q ă 3dm ln 2 so C 1 can be taken as 2304 ln 2 and the last constant is 1152 lnp2q.Lemma 5. For t 2, let λ ą 0, let δ t ą 0. Let f p δt q :" lnp 1 δt q `m ln ln t `m 2 ln `1 `e λ ˘. Then the event D t " tmax sPrts U ‹ psq ě σ a 2p1 `λqf pδ t qu happen with probability PpD t q ă δ t Proof. See lemma 3 of [10] . Moreover, notice that in their lemma 6, they use a union bound on all the possible values of pN i q iPA ‹ P rts m to get their result. (This is symbolized by their set D a )Lemma 6 (Multiplicative Azuma Chernoff). Let pW t q tPN ‹ be a sum of random variable : @t PN ‹ , W t " t ř s"1X s Where pX t q tPN ‹ verify that there exist pp t q tPN Ps0, 1r such that :@t P N ‹ , PpX t " 1|Hpt ´1qq " p t , PpX t " 0|Hpt ´1qq " 1 ´pt .And pHptqq tPN ‹ is a filtration where @t P N ‹ , X t is Hptq measurable. We note m t "t ř t"1 p t 1 .Let t P N ‹ , @δ ą 0 we have that :P pW t p1 `δqm t q ă expp δ 2 m t 2 `δ q and @ 1 ą δ 0P pW t p1 ´δqm t q ă expp δ 2 m t 2 qProof. For the first inequality, let t P N ‹ , λ, x P R `, we have by Markov inequality:PpW t xq " PpλW t λxq " Ppe λWt e λx qEpe λWt qe ´λx Let s P rts, by definition of X s and using that @x P R, exppxq 1 `x we have that :Ere λXs |Hps ´1qs " p s e λ `p1 ´ps q " p s pe λ ´1q `1 exppp s pe λ ´1qq.Then, by the tower property of the expectation and induction:Epe λWt q " E " e λWt´1 E " e λXt |H t´1 ‰‰ E " e λWt´1 ‰ exppp s pe λ ´1qq exp ¨ÿ sPrts p s pe λ ´1q ‚ .Combining with the first equation, we have :PpW t ą xq ă exp `mt pe λ ´1q ´λxis true for all x, λ P R `so by setting λ " lnp1 `δq and x " p1 `δqm t we have :PpW t ą p1 `δqm t q ă exp ´mt pe lnp1`δq ´1q ´p1 `δq lnp1 `δqm t ¯ exppm t pδ ´p1 `δq lnp1 `δqqqexpp´δ 2 m t 2 `δ qBecause @δ ą 0, δ ´p1 `δq lnp1 `δq ă ´δ2 2`δ . For the second inequality, let λ P R `:PpW t ă xq " Pp´λW t ą ´λxq " Ppe ´λWt ą e ´λx q Epe ´λWt qe λx Let s P rts, by definition of X s we have that :Ere ´λXs |Hps ´1qs " p s e ´λ `p1 ´ps q " p s pe ´λ ´1q `1 exppp s pe ´λ ´1qqThen, by the tower property of the expectation and induction: We have that PpBptqq ă d t 2 . This result can be in part found in [16] in their proof of lemma 1.Epe ´λWt q " E " e ´λWt´1 E "Proof. We control it with the deviation of individual arms.B i ptq :" ´ m#We have :E » - ÿ tPrT s 1 " i P Aptq, p µ i ptq ´µ‹ i ą ∆ min 2m ´ m * fi fl ă 8m 2 σ 2 p∆ min ´2 q 2And :E » - ÿ tPrT s ∆ptq1 tFptqu fi fl ă d∆ max ˆ8m 2 σ 2 p∆ min ´2 q 2Ṫhis is a result from [6] lemma 2 adapted to the σ 2 subgaussian case.Proof. We use a union bound and Hoeffding's inequality for σ 2 subgaussian random variable. Let i P rds,EQUATION" i P Aptq, p µ i ptq ´µ‹ i ą ∆ min 2m ´ m * ff ăE « 8 ÿ n"1 1 " p µ i ´µ‹ i ą ∆ min 2m ´ m , N i " n * ff ă 8 ÿ n"1 P ˆp µ i ´µ‹ i ą ∆ min 2m ´ m , N i " n ă 8 ÿ n"1 exp ˜´n 2σ 2 ˆ∆min 2m ´ m ˙2ă exp ´´1 2σ 2 `∆min 2m ´ m ˘21 ´exp ´´1 2σ 2 `∆min 2m ´ m ˘2ă 8m 2 σ 2 p∆ min ´2 q 2 .Then decomposing Fptq with a union bound of the i P Aptq, p µ i ptq ´µ‹ i ą ∆min 2m ´ m ( and summing over i P rds we get the second result. Lemma 9. Let t P rT s we have :P ˆAJ ptqpθptq ´p µptqq σ b 8gptq ln p|A|tq A J ptqV ptqAptq|Hptq ˙ă 1 t 2Which implies that PpHptq|Hptqq ă 1 t 2 . Defining :f ptq :" p1 `λq ´ln p|A|tq `pm `2qp1 `d lnp2qq lnpln tq `mp1`d lnp2qq 2 ln ´1 `e λ ¯¯,we have that gptq lnp|A|tq ă f ptq and thus:EQUATIONFinally:EQUATIONProof. Let c ą 0 by union bound we have :P ˆAJ ptqpθptq ´p µptqq cσ b 2gptqA J ptqV ptqAptq|Hptq ă ÿ APA P ˜AJ ptqpθptq ´p µptqq σ a 2gptqA J ptqV ptqAptq c|Hptq ă ÿ APA P ˜σa 2gptqA J ptqV 1 2 ptqZptq σ a 2gptqA J ptqV ptqAptq c|Hptq "|A|Qpcq ă |A| c ? 2π expp´c 2 2 q ă|A| expp´c 2 2 qBy setting c " a 4 ln p|A|tq ą 1 we have |A| exp ´´c 2¯" 1 t 2 hence the first result.Then we have that : lnp|A|q d lnp2q so that :ln p|A|tq ln t lnp|A|q `1 1 `d lnp2qHence, the second result.And by summing over t:EQUATIONWe recall simple tail bounds for Gaussian random variables. (see for instance [12] ) Lemma 10. Consider Z " N p0, 1q, then we havePpZ ě xq " Qpxq " 1 ? 2π ż `8 x e ´z2 2 dzfurthermore for all x ě 0:1 ? 2π x 1 `x2 e ´z2 2 ď Qpxq ď 1 ? 2π 1 x e ´x2 2As well as:Qpxq ď e ´x2 2It is also noted that by symmetry Pp|Z| ě xq " 2Qpxq.Lemma f. 1. Let f be the following function : `λq `lnp t 2 q `pm `2q ln lnp t 2 q `m 2 ln `1 `e λ ˘Ȗsing f. 2 we have that :f pt,f pt, m, λq f p t 2 , m, λqln t `pm `2q ln ln t lnp t 2 q `pm `2q ln lnp t 2 q Using f. 3 we have that for t ą 23, @m 1 f pt, m, λq f p t 2 , m, λq ln t `3 ln ln t lnp t 2 q `3 ln lnp t 2 q But thanks to f. 4, the right-hand side is decreasing in t, so :EQUATIONLemma f. 2. Let a b 0 and let g : R `Ñ R `be the following function :gptq :" a `t b `tThen @t 0, gptq ă gp0q ă a b Proof. Let t P R `, we have :gptq " a `t b `t " a `b `t b `t ´b b `t " 1 `a ´b b `t So g is decreasing in t.Lemma f. 3. The function f pt, mq :" ln t `pm `2q ln ln t lnp t 2 q `pm `2q ln lnp t 2 q is decreasing in m for t ą 23.Which means that for t ą 23, for @m 1 : ln t `pm `2q ln ln t lnp t 2 q `pm `2q ln lnp t 2 q ln t `ln ln t lnp t 2 q `3 ln lnp t 2 qProof. Let lpmq " a`mb c`md , its derivative is :l 1 pmq " bpc `mdq ´pa `mbqd pc `mdq 2 " bc ´ad pc `mdq 2So l 1 pmq ą 0 i.i.f. bc ´ad ą 0. Furthermore, ln ln t lnp t 2 q ´ln lnp t 2 q ln t ă 0 for t ą 23 So @t ą 23, f pt, mq is decreasing in m and @t ą 23, f pt, mq ă f pt, 1q.Lemma f. 4. The function :f ptq :" ln t `3 ln ln t lnp t 2 q `3 ln lnp t 2 q, is decreasing.Proof. We differentiate, and we obtainf 1 ptq ă 0 ðñ p 1 t `3 t ln t q ˆln ˆt 2 ˙`3 ln lnp t 2 q ˙´p 1 t `3 t lnp t 2 qqpln t `3 ln ln tq ă 0.We expend and simplify :p 1 t `3 t ln t q ˆln ˆt 2 ˙`3 ln lnp t 2 q ˙´p 1 t `3 t lnp t 2 q qpln t `3 ln ln tq " ´lnp2q t `ˆ3 lnp t 2 q t ln t ´3 ln t t lnp t 2 q 3 ln lnp t 2 q t´3 ln ln t t 9 ln lnp t 2 q t ln t ´9 ln ln t t lnp t 2 q ˙.We have :3 ln t t lnp t 2 q ą 3 ln t t ln t ą 3 lnp t 2 q t ln t and 3 ln ln t t ą 3 ln lnp t 2 q t and 9 ln ln t t lnp t 2 q ą 9 ln ln t t ln t ą 9 ln lnp t 2 q t ln t Therefore @t ą 3, f 1 ptq ă 0 and the function f is decreasing. Lemma f. 5. Let c ą 1 be a positive constant and let f be the following function :f ptq " Qpc a lnpt{2qq 1 ? 2π c a lnpt{2q 1 `c2 lnpt{2q pt{2q ´c2 2Then for t ą 2e we havef ptq 1 ? 2π 1 2c pt{2q ´c2 `1 2 2 " 1 ? 2π 1 2 5 4 2 c 2 2 c t ´c2 `1 2 2Proof. For t ą 2e we have that 1 ă c 2 lnpt{2q so :c a lnpt{2q 1 `c2 ln pt{2q ą 1 2c 1 a lnpt{2qFor t ą 2e we have that1 a lnpt{2q " exp `´12 ln lnpt{2q ˘ą exp `´1 4 lnpt{2q ˘. Therefore :f ptq 1 ? 2π c a lnpt{2q 1 `c2 lnpt{2q pt{2q ´c2 2 ą 1 ? 2π 1 2c pt{2q ´c2 `1 2 2Lemma f. 6.@t ą e, ln ln t ln t ă 1 2 Lemma f. 7. Let f, g the following function : f pt, m, λq :" p1 `λq ´ln t `pm `2q ln ln t `m 2 ln ´1 `e λ ¯ḡptq " f ptq ln t For t ą e and t ą 1 `e λ we have ln ln t ln t ă 1 2 thus f ptq ă p1 `λq p2m `1q ln t, and gptq ă p1 `λq p2m `1q .Proof. For t ą e, ln t ą ln ln t and for t ą 1 `e λ , ln t ą lnp1 `e λ q thus the result Lemma f. 8. Let α, c P R ‹ `, two strictly positive constants such that c α ą 1 and define the function f ptq :" t α ´c ln t. We have that @t ą ´c α ln c α 1´1 e ¯1 α , f ptq ą 0. Furthermore, we have :´c α ln c α 1´1 e ¯1 α ă `1 α ˘1`2 α `1 ´1 e ˘´1 α c 1`1 αProof. Let's study the function GpT q " T ´c ln ´T 1 α ¯" T ´c α ln pT q. For T c α e by using the concavity of the logarithm and differentiating T Þ Ñ c α ln pT q at the point c α e we have that : α we have that f ptq ą 0. Hence, the first result.We have using that lnpxq ă x :´ln c α ¯1 α " ˆ1 α ln ´´c α ¯α¯˙1 α ă ˆ1 α ˙1 α c αFinally, combined with the rest, we get the second result.Lemma f. 9. Let c ą 0, α ą 0 the series ř J t"1 expp´ct α q converges when T Ñ `8 and :8 ÿ t"1 expp´ct α q ă c ´1 α α Γp 1 α qProof. Because the function t Þ Ñ expp´ct α q is decreasing, by an integral test for convergence, we have that :8 ÿ t"1 expp´ct α q ă `8 ż 0 expp´ct α qdt.A primitive of the function :t Þ Ñ expp´ct α q is T Þ Ñ c ´1 α α `8 ş cT α t 1 α ´1e ´tdt. So : 8 ÿ t"1 expp´ct α q ă c ´1 α α `8 ż 0 t 1 α ´1e ´tdt ´0 c ´1 α α Γp 1 α qNeurIPS Paper Checklist• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a 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 a 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 a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it 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 can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. 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), fairness 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 not 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 or unintentional) misuse of the technology. • If there are 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 a system learns from feedback over time, improving the efficiency and accessibility of ML).38th Conference on Neural Information Processing Systems (NeurIPS 2024). 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: What is the guarantee for G-CTS?
limitations: limitations: adequately addressed
paper_summary: paper_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.
strength_weakness: strength_weakness: * The main result improves the known regret only for the term that does not depend on the time horizon, which is usually less interesting.
* Code is not provided for the numerical experiments.
questions: questions: * In line 26, do you mean $X(t)$ is uniformly distributed?
* Can you provide summary of the algorithms as figures? It is hard to follow in the text what is the exact algorithm
* Can you provide any intuitive explanation for the presented "paradox"?
limitations: limitations: The authors address the limitations of the paper.
paper_summary: paper_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.

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

The 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.
strength_weakness: strength_weakness: 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.

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

There 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.
questions: 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.

2. 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?

3. 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?

4. 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?

5. 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)



Agrawal and Goyal (2012) http://proceedings.mlr.press/v23/agrawal12/agrawal12.pdf
Kaufmann et al (2012) https://arxiv.org/pdf/1205.4217
Kveton, Szepesvari, et al. (2019) https://arxiv.org/abs/1902.10089
limitations: limitations: yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

The paper does not sufficiently clarify how the exploration boost is integrated into the analysis. The proof strategy is not well synthesized.

[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.
questions: 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: 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?

Comments: title: Reply to rebuttal
Response to Rebuttal
comment: I read the authors’ rebuttal and skimmed the comments of other reviewers. I would like to keep my score unchanged.
Thank you, I will in that case raise my score, I'd encourage that even if the space prohibits including in the main text some remark should be included in an appendix, or some reorganisation done to allow this inclusion.
The authors have addressed my concern. I would like to maintain my score.
Yes, we will incorporate those responses into our paper. We will emphasise the heuristic of the proof and especially the comparison with [18], Agrawal and Goyal (2012), Kaufmann et al (2012). We will also try to incorporate the exponential vs the polynomial scaling if the space constraint allows us.
Thanks very much for your response to my comments, all of these responses are convincing, I would just like to know if and how/where you intend to incorporate these responses into the updated paper?
Thank you for the response, I will keep my score