Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits

Authors: julien  zhou
pierre  gaillard
thibaud  rahier
houssam  zenati
julyan  arbel
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 12:01:04

Abstract: We address the problem of stochastic combinatorial semi-bandits, where a player selects among $P$ actions from the power set of a set containing $d$ base items. Adaptivity to the problem's structure is essential in order to obtain optimal regret upper bounds. As estimating the coefficients of a covariance matrix can be manageable in practice, leveraging them should improve the regret. We design ``optimistic''  covariance-adaptive algorithms relying on online estimations of the covariance structure, called OLS-UCB-C and COS-V (only the variances for the latter). They both yields improved gap-free regret. Although COS-V can be slightly suboptimal, it improves on computational complexity by taking inspiration from Thompson Sampling approaches. It is the first sampling-based algorithm satisfying a $\sqrt{T}$ gap-free regret (up to poly-logs). We also show that in some cases, our approach efficiently leverages the semi-bandit feedback and outperforms bandit feedback approaches, not only in exponential regimes where $P\gg d$ but also when $P\leq d$, which is not covered by existing analyses.

Main paper: 
 introduction: 
 In sequential decision-making, the bandit framework has been extensively studied and was instrumental to several applications, e.g. A/B testing (Guo et al., 2020) , online advertising and recommendation services (Zeng et al., 2016) , network routing (Tabei et al., 2023) , demand-side management (Brégère et al., 2019) , etc. Its popularity stems from its relative simplicity, allowing it to model and analyze a wide range of challenging real-world settings. Reference books like Bubeck and Cesa-Bianchi (2012) or Lattimore and Szepesvári (2020) offer a wide perspective on the subject.In this framework, a decision-maker or player must make choices and receives associated rewards, but it lacks prior knowledge of its environment. This naturally leads to an exploration-exploitation trade-off: the player must explore different actions to determine the best one, but an inefficient exploration strategy may harm the cumulative rewards. Efficient algorithms rely on exploiting the environment's structure, such as estimating the parameters of a reward function instead of exploring every action. This paper focuses on the stochastic combinatorial semi-bandit framework. At each round, the player chooses a subset of base items and receives a feedback for each item chosen. The action set is included in the base items' power set, and can therefore be exponentially big and difficult to explore. The main challenge in this framework is to effectively combine the information collected through different actions (that may share common base items).Problem formulation. We consider a set of d ∈ N * base items, each item i ∈ [d] = {1, . . . , d} yielding stochastic rewards. A player accesses these rewards through a set A ⊆ {0, 1} d of P ∈ N * actions, each corresponding to a subset of at most m ≥ 5 items (a) . We refer to actions a ∈ A using their components vector a = (a i ) i∈ [d] ∈ {0, 1} d where for all j ∈ [d], a j = 1 if and only if action a contains base item j.The player interacts with an environment over a sequence of T ∈ N * rounds. At each round t ∈ [T ], the player chooses an action A t ∈ A, the environment samples a reward vector Y t ∈ R d , the player observes the realization for every item contained in A t , and receives their sum. The interactions between the player and the environment are summarized in Framework 1.For each t ∈ {1, . . . , T }:• The player chooses an action A t ∈ A.• The environment samples a vector of rewards Y t ∈ R d from a fixed unknown distribution.• The player receives the reward ⟨A t , Y t ⟩ = i A t,i Y t,i .• The player observes Y t,i for all i ∈ [d] s.t. A t,i = 1.Assumptions. We make the following assumptions. For all t ∈ [T ], Y t is independent of the past rewards and the player's decision σ(A 1 , Y 1 , . . . , A t-1 , Y t-1 , A t ). There exists a mean reward vector E[Y t ] = µ ∈ R d and a second order moment matrixS = E[Y t Y ⊤ t ] ∈ M d (R).The positive semidefinite covariance matrix is denoted Σ ∈ M d (R), with Σ = S -µµ ⊤ .There exists a known vector B ∈ R d + such that for all t ∈ [T ] and i ∈ [d], |Y t,i | ≤ B i /2 almost surely (and |Y t,i -µ i | ≤ B i ). The objective of the decision-maker is to minimize the expected cumulative pseudo-regret defined as:EQUATIONwhere ⟨•, •⟩ denotes the usual inner product in R d , a * ∈ arg max a∈A ⟨a, µ⟩ is an optimal action, and ∆ a = ⟨a * -a, µ⟩ is the sub-optimality gap for action a ∈ A.Combinatorial semi-bandit problems have been extensively studied by the bandit community since their introduction by Chen et al. (2013) . Here, we only highlight key earlier works related to this paper. For a comprehensive introduction to this literature, we refer the interested reader to the monograph by Lattimore and Szepesvári (2020).A first line of works considers deterministic algorithms based on the optimistic principle and upper confidence bounds (UCBs). Chen et al. (2013) first designed CUCB, computing UCBs for the items' average rewards, converting these into UCBs for the actions' rewards, and choosing the action with the highest one. It was later analyzed by Kveton et al. (2015) , who proved a regret upper bound uniform over all possible covariance matrices Σ (hence, paying the worst-case). Combes et al. (2015) highlighted the importance of designing Σ-adaptive algorithms by showing that the regret could be improved by a factor of m when the items' average rewards are independent. Subsequently, Degenne and Perchet (2016) developed OLS-UCB, an algorithm intended to leverage the covariance structure. However, OLS-UCB requires prior knowledge of a positive semi-definite covariance-proxy matrix Γ, such that for all t ≥ 1 and for all u ∈ R d , E[exp(⟨u, Y t -µ⟩)] ≤ exp( 1 2 ∥u∥ 2 Γ ). Estimating Γ in (a) Throughout the paper, the term item (or base item) refers to an element in the set [d] , while an action denotes a subset of base items in A.practice is challenging and leads to regret bounds depending on it instead of the "true" covariance matrix Σ, potentially resulting in significantly looser bounds. This issue was addressed by Perrault et al. (2020b) , who proposed a covariance-adaptive algorithm, ESCB-C, with asymptotically optimal gap-dependent regret upper bounds. Yet, it suffers from an additive constant of order ∆ -2 min , which prevents its conversion into an Õ( √ T ) (b) gap-free bound. Thus, none of the above works proposes a Õ( √ T ) gap-free and covariance-adaptive regret bound, which is one of the key contributions of this paper. A common drawback of these works is also their potentially prohibitive computational complexity, due to the need to solve a maximization step over a large action set A ⊆ {0, 1} d that can be exponentially large. Some works, such as Cuvelier et al. (2021) or Liu et al. (2022) , propose solutions to achieve polynomial time complexity, for example by applying UCB at the item level only rather than the action level. However, these approaches only work for independent rewards or under specific assumptions on their distribution, making the analysis for generic and unknown distributions extremely challenging. Another approach to tackle the computational burden in combinatorial semi-bandits is to resort to sampling algorithms, which we detail below.A second line of works for stochastic combinatorial semi-bandits considers randomized algorithms inspired by Thompson Sampling (TS) for multi-armed bandits (Thompson, 1933) . These algorithms involve sampling a random vector μt ∈ R d at each round t + 1 ∈ [T -1] from a distribution representing a "belief" over the parameter µ, taking a decision A t+1 ∈ arg max a∈A ⟨a, μt ⟩, and updating the belief distribution using the observations. The main appeal of these approaches lies in their computational complexity, especially when solving a linear maximization problem in particular action spaces (such as matroids). Recent works have designed and analyzed such algorithms. Notably, Wang and Chen (2018) consider independent item's rewards. Perrault et al. (2020a) refine it and assume a known variance-proxy Γ and therefore suffers from the same drawbacks as Degenne and Perchet (2016) . Their technical analysis also yields a gap-dependent regret bound with an undesirable ∆ -m min term, preventing a Õ( √ T ) gap-free rate. A central contribution in our paper is the combination of the computational efficiency for sampling algorithms with the covariance-adaptivity Õ( √ T ) gap-free from our UCB approach.Besides, the literature concerning our setting has historically mostly focused on cases where the action set is exponentially large, namely P ≫ d, and the way to get quasi-optimal regret rates in these instances. However, outside of these regimes, the commonly derived regret bounds are too rough and fail to show the benefit of the semi-bandit feedback. While the conventional stochastic combinatorial semi-bandit regret upper bound grows as Õ( et al., 2015) , a Õ( √ mP T ) could be achieved using bandit feedback only (Auer et al., 2002b) . Intriguingly, the latter appears to outperform the semi-bandit rate as soon as P < d, making the extra information obtained through a richer feedback seemingly useless. Fine-grained analyses, clearly taking the structure into account, are therefore needed.√ mdT ) (KvetonA new deterministic optimism-based algorithm (Section 2). We present OLS-UCB-C (Online Least Squares Upper Confidence Bound with Covariance estimation), relying on the optimism principle. The analysis of OLS-UCB-C sketched in Section 5.2 shows the following properties:• First optimal gap-free regret upper bound. OLS-UCB-C yields a similar gap-dependent regret bound as ESCB-C from Perrault et al. (2020b) up to logarithmic factors, and the first optimal covariance-adaptative gap-free Õ( √ T ) regret bound (Theorem 1). • Improved performance over UCB in all regimes of P/d. Under some conditions on the covariance matrix Σ, we prove that OLS-UCB has a uniformly better regret than UCB, showing that properly leveraging semi-bandit feedback indeed consistently offers an advantage on (simple) bandit algorithms, which is not straightforward from existing analyses. • Improved complexity over concurrent algorithms. OLS-UCB-C circumvents the convex optimization problem that ESCB-C requires to solve at each round and is therefore more efficient, despite suffering in the very large P regime as many other deterministic algorithms.The first stochastic optimism-based algorithm (Section 3). We introduce COS-V (Combinatorial Optimistic Sampling with Variance estimation), a TS-inspired algorithm exploiting the "frequentist" confidence regions derived in Section 4. It satisfies the following:• Improved complexity for P ≫ 1 compared to other deterministic semi-bandit algorithms.COS-V can be efficient in the very large P regime, which is the main blind spot of OLS-UCB-C. • First gap-free Õ( √ T ) regret upper bound for a sampling algorithm. The analysis we provide in Section 5.3 exploits the common structure of the OLS-UCB-C and COS-V algorithms. It enables the derivation of a gap-dependent bound for COS-V that does not involve the ∆ -m term we typically find in the analysis for other TS algorithms (Wang and Chen, 2018; Perrault et al., 2020a) , consequently leading to a new Õ( √ T ) variance-adaptive gap-free regret upper bound for a sampling algorithm.A novel gap-free lower bound (Section 2.2). We show a gap-free lower bound on the regret for stochastic combinatorial semi-bandits, explicitly involving the structure of the problem (the items forming each action) and the covariance matrix Σ. This lower bound highlights the optimality of the gap-free upper bound we establish for OLS-UCB-C.Technical details are deferred to Section 4, Section 5, and the Appendix. et al., 2015) , OLS-UCB-C (Degenne and Perchet, 2016), ESCB-C (Perrault et al., 2020b) , and OLS-UCB-C (ours); as well as the two stochastic algorithms: CTS-Gaussian (Perrault et al., 2020a) and COS-V (ours). Notations: a refers to actions; i and j refer to items; m denotes the maximum number of items per action; B is a vector of bounds on the items' rewards; Γ is a covariance-proxy matrix; γ is the maximum of "correlationsproxy"; we abbreviate max{x, 0} to (x)+ for any x ∈ R ; C opt 1/T refers to the complexity of the optimisation step needed in ESCB-C.Algorithm Info. Time Complexity Gap-Free Asymptotic RegretBndt.UCB B P T a (a ⊤ B) 2 1/2 UCBV ∅ P T a a ⊤ Σa 1/2 S-Bndt. CUCB B mP T md 1/2 ∥B∥ ∞ OLS-UCB (a) Γ m 2 + P d 2 ∅ ESCB-C ∅ m 2 + P C opt 1/T ∅ OLS-UCB-C ∅ m 2 + P d 2 T i max a/i∈a j∈a (Σ i,j ) + 1/2 S-Bndt. CTS-Gaussian (b) Γ poly(d) ∅ COS-V (b) ∅ poly(d) T m i∈[d] Σ i,i 1/22 Covariance-adaptative deterministic algorithm: OLS-UCB-CIn this section, we design a new algorithm that efficiently leverages the semi-bandit feedback. It approximates the coefficients of the covariance matrix Σ online. The approximation is symmetric by construction and yields a coefficient-wise upper bound of Σ, but it is not necessarily positive semi-definite, a constraint that can be challenging to impose in practice. 
algorithm: ols-ucb-c: 
 We present OLS-UCB-C described in Alg. 2 and detail below the successive steps it performs.Initial exploration. The algorithm first explores by choosing every base item i ∈ [d] and every "reachable" couple (i, j)∈ [d] 2 at least once. Algorithm 2 OLS-UCB-C Input δ > 0, B ∈ R d + . for t = 1, . . . , T do if a ∈ A| min (i,j)∈a n t,(i,j) < 1 ̸ = ∅ then Choose any A t in the above set. else Compute μt-1 from (2).Compute Σt-1 from (3) and ( 4).Compute Ẑt-1 from (5).ChooseA t ∈ A from (6). Environment samples Y t ∈ R d . Receive reward ⟨A t , Y t ⟩ = i A t,i Y t,i . end if end forRewards means estimation. At each round t + 1 ∈ [T -1], the algorithm uses an empirical mean μt for µ defined asEQUATIONwhere d a = diag(a) ∈ M d (R) is the diagonal matrix of the elements in a ∈ A; n t,(i,j) is the number of times items i and j (with possibly i = j) have been chosen together;N t = diag((n t,(i,i) ) i∈[d] ) ∈ M d (R) is the diagonal ma- trix of item counts.Rewards covariances estimation. The covariances are estimated by χt,(i,j) = Ŝt,(i,j) -μt,i μt,j ,where Ŝt,(i,j) =1 n t,(i,j) t s=1 A s,i A s,j Y s,i Y s,j .The algorithm uses Σt , a coefficient-wise upper-confidence bound of Σ whose coefficients are defined for a fixed δ > 0 as Σt,(i,j) = χt,(i,j) +EQUATIONwhereh t,δ = 1 + 2 log(1/δ) + 2 log t log(t) 2 d(d + 1) + log(1 + t) 1/2. Optimistic action choice. Following the 'optimistic' principle of UCB-like algorithms, the estimated rewards (⟨μ t , a⟩) a∈A are inflated by bonuses, yielding corresponding upper confidence bounds.The bonuses involve the history through a regularized empirical design matrix (with empirical covariances):EQUATIONwhere d Σt = diag( Σt ) ∈ M d (R), I is the identity matrix and Σt is the coefficient-wise upper bound for the covariance matrix defined in (4). Formally, OLS-UCB-C choosesEQUATIONwhere f t,δ = 6 log(1/δ) + 6 log(t) + (d + 2) log(log(t)) + 3d 2 log(2) + log(1 + e) .Efficiency improvement. While Perrault et al. (2020b) use an axis-realignment technique to derive their confidence regions, our approach builds ellipsoidal confidence regions. This simplifies the computation of an upper confidence bound for each action as we have a closed-form expression. In comparison, Perrault et al. (2020b) need to solve linear programs in convex sets at each iteration.Theorem 1. Let T ∈ N * and δ > 0.Then, OLS-UCB-C (Alg. 2) satisfies the gap-dependent regret upper boundE[R T ] = Õ log(m) 2 d i=1 max a∈A/i∈a,∆a>0 σ 2 a,i ∆ a ,where σ 2 a,i = j∈a max{Σ i,j , 0}, and the gap-free regret upper boundE[R T ] = Õ log(m) √ T d i=1 max a∈A/i∈a σ 2 a,i .The proof is outlined in Section 5 and the specific details are presented in Appendix E.Optimal gap-free bound. This result shows that OLS-UCB-C yields the same gap-dependent regret upper bound as ESCB-C (Perrault et al., 2020b) (up to poly-logarithmic factors) and more importantly yields a novel covariance-adaptive and optimal Õ( √ T ) gap-free bound, as shown by the following lower-bound proven in Appendix A. Unfortunately, only the positive coefficients of Σ are considered in our bound but the inclusion of negative correlations could be advantageous to reduce the rate at which the regret increases. However, it could complicate the analysis greatly and is thus deferred to future research. Theorem 2. Let d, m ∈ N * such that d/m ≥ 2 is an integer, T ∈ N * , and Σ ⪰ 0 a covariance matrix. Then, there exists a stochastic combinatorial semi-bandit with d base items, and a reward distribution with covariance matrix Σ on which for any policy π, the pseudo regret satisfiesE[R T ] ≥ 1 8 T i∈[d] max a∈A,i∈a j∈a Σ i,j 1/2. Improvement over CUCB. Our gap-free and gap-dependent bounds outperform those of CUCB (Kveton et al., 2015) no matter the covariance structure, as(T md) 1/2 ∥B∥ ∞ ≳ (Tr(Σ)T ) 1/2 . (c)Besides, in the particular case of a diagonal Σ, our gap-free upper bound gains a factor at least √ m over the one of CUCB. In this scenario, σ 2 a,i = Σ i,i for all a ∈ A and i ∈ a. Our gap-dependent and gap-free upper bounds are then roughly bounded asd i=1 Σ i,i min a∈A/i∈a ∆ aand Tr(Σ)T , respectively.Improvement over UCBV. Assuming that Σ i,j ≥ 0 for all i, j, our upper-bound uniformly improves the one of UCBV of order T a a ⊤ Σa 1/2 , since in this case d i=1 max a∈A\i∈A σ 2 a,i ≤ a ∥a∥ Σ . Existing semi-bandit analyses could only leverage semi-bandit feedback in the regime P ≫ d, which is natural in combinatorial bandits but not systematic in real-world applications.3 New sampling algorithm for combinatorial semi-bandits: COS-VAlgorithm 3 COS-V Input δ > 0, B ∈ R d + . for t ∈ [T ] do if a ∈ A s.t min (i,j)∈a n t,(i,j) < 1 ̸ = ∅ then Choose A t in the above set. else Compute μt-1 (2). Compute ( Σt-1,(i,i) ) i∈[d] (4). Compute ( Ẑt-1,(i,i) ) i∈[d] from (5). Sample μt-1 from (7) Choose A t ∈ arg max a∈A ⟨a, μt-1 ⟩. Environment samples Y t ∈ R d . Receive reward ⟨A t , Y t ⟩ = i A t,i Y t,i . end if end forIn this section, we introduce a randomized algorithm inspired from TS, enabling to get potentially computational complexity at the cost of not leveraging off-diagonal covariances.The difficulty in designing and analysing TS algorithms generally stems from controlling the random exploration. To that end, we parametrize the exploration distribution using the same estimators as OLS-UCB-C.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: The results and theorems are discussed with comments made especially about some limitations. In particular, computational complexity is addressed.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. 
algorithm: cos-v: 
 We propose a sampling strategy using "frequentist" estimators, COS-V, described in Algorithm 3.The algorithm begins with the same exploration phase as OLS-UCB-C. Thereafter at each round t + 1 ∈ [T -1], we sample parameters (μ i,t ) i∈[d] using 1-dimensional normal distributions biased toward the positive orthant. Formally, for all i ∈ [d], we sampleEQUATIONwhere g t,δ = 1 + 2 log 2dt log(t) 2 /δ 1/2 and f t,δ is the same as for OLS-UCB-C.(c) We denote ≳ for ≥ up to a constant factor.Theorem 3. Let T ∈ N * , and δ > 0.Then, COS-V (Alg. 3) satisfies the gap-dependent regret upper boundEQUATIONwhere ∆ i,min = min{∆ a , a ∈ A such that i ∈ a}, and the gap-free regret upper boundEQUATION)The proof is outlined in Section 5 and the specific details can be found in Appendix F.Novel variance-dependent bound. Theorem 3 presents the first variance-dependent bound for a sampling-based semi-bandit algorithm. Unfortunately, integrating the covariances Σ i,j in the leading term is still an open problem. Possible leads include exploring other biasing strategies for sampling, or using oversampling approaches like Abeille and Lazaric (2017) which inflate the confidence regions in the linear bandits setting.Novel gap-free regret bound. An important novelty of our gap-dependent bound Eq. ( 16) is the absence of ∆ -m min terms present in the previous analyses of CTS (Wang and Chen, 2018; Perrault et al., 2020a) . In particular, this improvement yields the first Õ( √ T ) gap-free regret upper bound for a sampling strategy.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?• 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). 
mean and covariance estimation: 
 In this section, we present concentration results for μt (rewards means) and Σt (rewards covariances, estimated with χt ) used in OLS-UCB-C and COS-V, which are central to prove Theorem 1 and Theorem 3 (sketched in Section 5).4.1 Covariance-aware confidence region for the average reward Average reward estimation. Let a ∈ A, t ≥ d(d + 1)/2, as introduced in Section 2.1, the least square estimator for the mean reward vector µ using all the data gathered after round t isμt = N -1 t t s=1 d As Y s = µ + N -1 t t s=1 d As η s ,where the η s denote the deviations Y s -µ.Confidence region design. We design confidence regions inspired from LinUCB literature (Rusmevichientong and Tsitsiklis, 2010; Filippi et al., 2010; Abbasi-Yadkori et al., 2011) and the work of Degenne and Perchet (2016). Major differences with those works include using Bernstein's style concentration inequalities involving the covariance matrix Σ, assuming a multidimensional noise term, and combining them with a covering argument to relax dependence in d (peeling trick from Degenne and Perchet, 2016). We introduce the regularized design matrix defined byZ t = V t + N t d Σ + ∥B∥ 2 I ,where V t = t s=1 d As Σd As is the design matrix (of which the OLS-UCB-C and COS-V use an empirical version). Let S t = N t (μ t -µ), the deviations of ⟨a, μt ⟩ are bounded asEQUATION)Designing a confidence region for ∥S t ∥ Z -1 t therefore allows to control the deviations |⟨a, μt -µ⟩| uniformly on A. Let δ > 0, we define the event This event can also be written G t = ∥μ t -µ∥ NtZ -1 t Nt ≤ f t,δ and is therefore equivalent to μt belonging to an ellipsoid around the true reward mean vector µ.EQUATIONConfidence region probability. The following result proven in Appendix B presents an upper bound for P(G c t ). Proposition 1. Let t ≥ d(d + 1)/2 and δ > 0. Then, P(G c t ) ≤ δ/(t log(t) 2 ) .Proving this result relies on an argument adapted from Faury et al. ( 2020) and a covering trick from Degenne and Perchet (2016).Rewards covariances estimator. Let t ≥ d(d + 1)/2 and a "reachable" couple (i, j) ∈ [d] 2 . The coefficients of Σ can be estimated online by χt as introduced in Section 2.1 χt,(i,j) = Ŝt,(i,j) -μt,i μt,j .Rewards covariances upper confidence bound. Let δ > 0. We use the following coefficient-wise upper estimates of Σ in our algorithmsΣt,(i,j) = χt,(i,j) + B i B j 4 5h t,δ √ n t,(i,j) + h 2 t,δ n t,(i,j) + 1 n 2 t,(i,j) , with h t,δ = 1 + 2 log(1/δ) + 2 log t log(t) 2 d(d + 1) + log(1 + t) 1/2. Favorable event design. We define C t as the event where all the coefficients of Σt are indeed upper bounding those of Σ:EQUATIONFavorable event probability. The following result proven in Appendix C presents an upper bound for P(C c t ). Proposition 2. Let t ≥ d(d + 1)/2 and δ > 0. Then, P(C c t ) ≤ δ/(t log(t) 2 ) . 
regret upper bounds: 
 In this section, we provide a sketch of the proof for Theorem 1 and Theorem 3. For both OLS-UCB-C and COS-V, the idea to bound the regret is to find a sequence of favorable events (E t ) t≥d(d+1)/2 that are true with high probability, and under which the regret grows logarithmically with time.Let (E t ) t∈[T ] be a sequence of events, then for both OLS-UCB-C and COS-V standard derivations yieldE[R T ] ≤ ∆ max d(d + 1)/2 + T -1 t=d(d+1)/2 P(E c t ) + E T -1 t=d(d+1)/2 1{E t }∆ At+1 . (13)Assuming that the sequence of events (E t ) t≥d(d+1)/2 happens with high enough probability, it is sufficient to control what happens conditionally to it. In particular, Proposition 6 in Appendix D states that if we can bound ∆ 2 At+1 with a linear combination of terms evolving as n -k t,(i,j) for every couple (i, j) ∈ A t+1 and different k ≥ 1, then we can infer a worst-case behaviour, which yields Theorem 1 and Theorem 3.In the following, we will refer to the term T -1 t=d(d+1)/2 P(E c t ) as the unfavorable event probability and to the term E T t=d(d+1)/2 1{E t }∆ At+1 as the high-probability regret.For OLS-UCB-C we consider the sequence of events E t = {G t ∩ C t } for all t ≥ d(d + 1)/2, corresponding the confidence regions of (μ t ) t≥d(d+1)/2 and of ( Σt,(i,j) ) t≥d(d+1)/2, (i,j)∈[d] 2 defined in Section 4. Under these events, we can upper-bound the high-probability regret from Eq. ( 13) with the following proposition (proven in Appendix E.1).Proposition 3. Let δ > 0. Then, OLS-UCB-C yields E T -1 t=d(d+1)/2 ∆ At+1 1 G t ∩ C t = O log(T ) 2 log(m) 2 d i=1 max a∈A/i∈a σ 2 a,i ∆ a , as T → ∞, where σ 2 a,i = j∈a (Σ i,j ) + .Conclusion of the proof. Injecting results from Proposition 3 (high-probability regret) as well as Proposition 1 and Proposition 2 (unfavorable event probability) into the template bound (13), we getEQUATIONfor OLS-UCB-C as T → ∞. This provides the gap-dependent bound of Theorem 1. The gap-free bound is detailed in Appendix E.4. It is enabled by the fact that our gap-dependent bound does not incur any term in ∆ -2 min , unlike Perrault et al. ( 2020b); Degenne and Perchet (2016).For the analysis of our stochastic algorithm COS-V, we need to consider events related to the sampling distributions in addition to the events G ′ t and C t introduced in the precedent section. For this purpose, we denote the event H t defined asEQUATIONThe high-level idea of the event H t is to ensure that the sampled rewards μt,i upper-bound the true mean µ i while not being too far for all the items i ∈ a * . Showing that the event H t indeed occurs with high-probability (Lemma 7 in Appendix F) and setting the events E t = {G t ∩ C t ∩ H t }, we can upper-bound the high-probability regret in the following proposition (proof is in Appendix F.2).Proposition 4. Let δ > 0. Then COS-V yieldsE T -1 t=d(d+1) ∆ At+1 1 G t ∩ C t ∩ H t = O log(T ) 3 log(m) 2 d i=1 mΣ i,i ∆ i,min .Conclusion of the proof. Injecting results from Proposition 4 (high-probability regret) as well as Lemma 7, Proposition 1 and Proposition 2 (unfavorable event probability) into the template bound ( 13) yieldsEQUATIONas T → ∞. This provides the gap-dependent bound of Theorem 3. As it does not incur any term in ∆ -m min as in Wang and Chen (2018); Perrault et al. (2020a) , this result can be used to derive a Õ( √ T ) gap-free bound for a sampling-based combinatorial semi-bandit algorithm. 
concluding remarks: 
 We propose and analyze two algorithms for combinatorial semi-bandits. OLS-UCB-C is a deterministic, covariance-adaptive algorithm. Compared to other existing approaches, our algorithm is typically less computationally demanding and yields the first Õ( √ T ) gap-free regret rate that explicitly depends on the covariance of the base item rewards and the structure. COS-V is a variance-adaptive, TS-like algorithm. Its complexity is significantly lower under certain types of constraints, but its regret is suboptimal as it assumes worst-case correlations. However, leveraging the analysis of OLS-UCB-C, it also yields the first Õ( √ T ) gap-free regret upper bound among sampling-based approaches.Tabei, G., Ito, Y., Kimura, T., and Hirata, K. ( 2023). Design of multi-armed bandit-based routing for in-network caching. IEEE Access.Thompson, W. R. (1933) . On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-294.Wang, S. and Chen, W. ( 2018). Thompson sampling for combinatorial semi-bandits. In International Conference on Machine Learning.Zeng, C., Wang, Q., Mokhtari, S., and Li, T. ( 2016). Online context-aware recommendation with time varying multi-armed bandit. In International Conference on Knowledge Discovery and Data Mining.The Supplementary is organized as follows:-Appendix A proves the lower bound from Theorem 2, -Appendix B outlines proofs concerning the concentration of the average estimator (Propositions 1) -Appendix C presents those for the covariance estimator (Proposition 2), -Appendix D establishes general propositions used to upper-bound the number of times each item is chosen, -Appendix E and Appendix F detail proofs for OLS-UCB-C and COS-V, -Appendix G presents some experimental results.A Proof of the lower bound (Theorem 2)Theorem 2. Let d, m ∈ N * such that d/m ≥ 2 is an integer, T ∈ N * ,and Σ ⪰ 0 a covariance matrix. Then, there exists a stochastic combinatorial semi-bandit with d base items, and a reward distribution with covariance matrix Σ on which for any policy π, the pseudo regret satisfies EQUATIONEQUATIONwhereΣ ′ min = min p∈[d/m] Σ ′ p,p . We denote G 0 ∼ N (0, Σ ′ ) a (d/m)-dimensional centered Gaussian distribution with covariance matrix Σ ′ . Let p ∈ [d/m],we consider the mean vector µ (p) ∈ R d/m having coordinate 0 everywhere and ∆ at coordinate p, for all i ∈ [d/m], µ (p) i = ∆1{i = p}. We introduce the Gaussian reward distributions G p ∼ N (µ (p) , Σ ′ ) and denote T p = T t=1 1{A t = p}. Then, using policy π, and considering the reward distributions G p and G 0 , the average number of times action p has been chosen satisfiesEQUATION)where TV denotes the total variation distance, KL denotes the Kullback-Leibler divergence and the last inequality uses Pinsker's inequality. Then, using the divergence decomposition between multi-armed bandits (Lemma 15.1 in Lattimore and Szepesvári, 2020),KL (π, G 0 ), (π, G p ) = d/m k=1 E π,G0 T k KL N (0, Σ ′ ), N (µ (p) , Σ ′ ) = d/m k=1 E π,G0 T k µ (p) k 2 2Σ ′ k,k.Reinjecting this expression into Eq. ( 18), we getE π,Gp [T p ] ≤ E π,G0 [T p ] + T 2 d/m k=1 µ (p) k 2 Σ ′ k,k E π,G0 [T k ] = E π,G0 [T p ] + T 2 1 Σ ′ p,p ∆ 2 E π,G0 [T p ] = E π,G0 [T p ] + c T E π,G0 [T p ] Σ ′ min Σ ′ p,p d/m k=1 Σ ′ k,k← reinjecting Eq. ( 17)≤ E π,G0 [T p ] + c T E π,G0 [T p ] d/m k=1 Σ ′ k,k .Now, summing over the actions p,EQUATIONWe denote R (p)T the average cumulative regret incurred with the reward distribution G p , thend/m p=1 R (p) T = ∆ d/m p=1 (T -E π,Gp [T p ]) = 2c Σ ′ min d/m k=1 Σ ′ k,k T d m T - d/m p=1 E π,Gp [T p ]← reinjecting Eq. ( 17)≥ 2c Σ ′ min d/m k=1 Σ ′ k,k T d m T -T -cT d m d/m k=1 Σ ′ k,k ← from Eq. (19) = 2c Σ ′ min d m T d/m k=1 Σ ′ k,k 1 - m d -c 1 d/m d/m k=1 Σ ′ k,k ≥ 2c Σ ′ min d m T d/m k=1 Σ ′ k,k 1 - m d -c Σ ′ min . Taking c = 1 2 1 √ Σ ′ min (1 -m d ), d/m p=1 R (p) T ≥ d m T d/m k=1 Σ ′ k,k 1 2 1 - m d 2 ≥ 1 8 d m T d/m k=1 Σ ′ k,k ← as m/d ≤ 1/2 .Therefore, there exists at least one instancep * ∈ [d/m] such that R (p * ) T ≥ 1 8 T d/m k=1 Σ ′ k,k . Now, decomposing d/m k=1 Σ ′ k,k = d/m k=1 i∈a k j∈a k Σ i,j = i∈[d] max a∈A,i∈a j∈a Σ i,j , we get R (p * ) T ≥ 1 8 T i∈[d] max a∈A,i∈a j∈a Σ i,j .B Concentration of the average rewards estimations (Proposition 1)Proposition 1. Let t ≥ d(d + 1)/2 and δ > 0. Then, P(G c t ) ≤ δ/(t log(t) 2 ) .Proof. Let t ≥ d(d + 1)/2 and δ > 0.We havef t,δ = 6 log(1/δ) + 6 log(t) + (d + 2) log(log(t)) + 3d 2 log(2) + log(1 + e) = 6 log t log(t) 2 δ log(t) log(1 + (e -1)) d + 6d log(2) + 3d log(2 + (e -1)).Covering argument (Peeling trick). The peeling trick consists in separating the space of trajectories up to round t into an exponentially large number of parts, each having an exponentially small probability.Formally, let 0 < ϵ < 1. For each p ∈ N d we associate the setEQUATION)As an abuse of notation, we denote by (t ∈ D p ) the event n t,(i,i) + 1 i∈[d] ∈ D p .Setting P t,ϵ = log(t) log(1+ϵ) , we define for each pEQUATION)In particular, under the event(t ∈ D p ), N t ⪯ (1 + ϵ) Ñp .Using this covering, we decomposeP(G c t ) = P t s=1 d As η s Z -1 t > f t,δ = p∈[Pt,ϵ] d P ∥S t ∥ Z -1 t > f t,δ ∩ (t ∈ D p ) ≤ p∈[Pt,ϵ] d P ∥S t ∥ Z -1 t,p > f t,δ ∩ (t ∈ D p ) .We now apply the following Lemmas.Lemma 1. Let t ≥ d(d + 1)/2, 0 < ϵ < 1, p ∈ [P t,ϵ ] d , and δ > 0. Then,EQUATIONwhereEQUATION)Moreover, under eventEQUATIONIn our case, setting ϵ = e -1, they yieldP(G c t ) ≤ p∈[Pt,ϵ] d P ∥S t ∥ Z -1 t,p > 6 log t log(t) 2 δ log(t) d + 6d log(2) + 3d log(1 + e) ∩ (t ∈ D p ) ≤ p∈[Pt,ϵ] d P ∥S t ∥ Z -1 t,p > 6 log t log(t) 2 δ log(t) d + 6 log Norm p Norm t,p ∩ (t ∈ D p ) ← Lemma 2 ≤ p∈[Pt,ϵ] d P ∥S t ∥ Z -1 t,p > 6 log t log(t) 2 δ log(t) d + 6 log Norm p Norm t,p ≤ p∈[Pt,ϵ] d δ 1 t log(t) 2 1 log(t) d ← Lemma 1 = δ 1 t log(t) 2 1 log(t) d log(t) d = δ t log(t) 2 . B.1 Proof of Lemma 1 Lemma 1. Let t ≥ d(d + 1)/2, 0 < ϵ < 1, p ∈ [P t,ϵ ] d ,and δ > 0. Then,EQUATIONwhere Norm p = λ∈R d 1 ∥Z 1/2 0,p λ∥ ≤ 1 2 exp{-∥λ∥ 2 Z0,p }dλ , Norm t,p = λ∈R d 1 ∥Z 1/2 t,Let λ ∈ R d such that ∥λ∥ ≤ 1 2∥B∥ and s ∈ [t]. We denote F ′ t-1 = σ(A 1 , Y 1 , . . . , A t-1 , Y t-1 , A t ).Then, ∥λ ⊤ d As η s ∥ ≤ 1/2 andE exp λ ⊤ d As η s -λ ⊤ d As Σd As λ F ′ s-1 ≤ 1 which yields that M k (λ) k∈N * = exp λ ⊤ S k -∥λ∥ 2 V k k∈N * is a F ′ k -supermartingale.Let p ∈ [P t,ϵ ] d , we consider the density g p of a d-dimensional Gaussian with covariance matrix1 2 Ñp d Σ + ∥B∥ 2 I -1 = 1 2 Z -1 0,p , truncated in the ellipsoid x ∈ R d , ∥Z 1/2 0,p x∥ ≤ 1 2 , g p (x) = 1 x ∈ R d , ∥Z 1/2 0,p x∥ ≤ 1 2 } Norm p exp -∥x∥ 2 Z0,p ,where Norm p is the normalisation constant.We integrate M k (λ) k∈N * for λ ∼ g p , and define ( Mp,k ) k∈N * asMp,k = λ∈R d M k (λ)dλ = λ∈R d 1{∥Z 1/2 0,p λ∥ ≤ 1 2 } Norm p exp λ ⊤ S k -∥λ∥ 2 Z k,p dλ , which is still a supermartingale. Let λ * t,p ∈ arg max {Z 1/2 0,p ∥λ∥≤ 1 4 } (λ ⊤ S t -∥λ∥ 2 Zt,p ). Then Mp,k = exp(λ * ⊤ t,p S k -∥λ * t,p ∥ 2 Z k,p ) Norm p ∥Z 1/2 0,p λ∥≤ 1 2 exp (λ -λ * t,p ) ⊤ S t -∥λ∥ 2 Z k,p + ∥λ * t,p ∥ 2 Z k,p dλ = exp(λ * ⊤ t,p S k -∥λ * t,p ∥ 2 Zt,p ) Norm p ∥Z 1/2 0,p λ+Z 1/2 0,p λ * t,p ∥≤ 1 2 exp λ ⊤ S k -∥λ∥ 2 Z k,p -2λ ⊤ Z k,p λ * t,p dλ ≥ exp(λ * ⊤ t,p S k -∥λ * t,p ∥ 2 Zt,p ) Norm p ∥Z 1/2 0,p λ∥≤ 1 4 exp λ ⊤ S k -∥λ∥ 2 Z k,p -2λ ⊤ Z k,p λ * t,p dλ = exp(λ * ⊤ t,p S k -∥λ * t,p ∥ 2 Z k,p ) Norm p ∥Z 1/2 0,p λ∥≤ 1 4 exp λ ⊤ S k -2Z k,p λ * t,p -∥λ∥ 2 Z k,p dλ = exp(λ * ⊤ t,p S k -∥λ * t,p ∥ 2 Z k,p ) Norm p Norm k,p λ∈R d 1 ∥Z 1/2 0,p λ∥ ≤ 1 4 Norm k,p exp λ ⊤ S k -2Z k,p λ * t,p -∥λ∥ 2 Z k,p dλ ,where we can recognize g k,p the density of a d-dimensional Gaussian with covariance matrix1 2 Z -1 k,p , truncated in the ellipsoid x ∈ R d , ∥Z 1/2 0,p x∥ ≤ 1 4 , g k,p (x) = 1 ∥Z 1/2 0,p x∥ ≤ 1 4 Norm k,p exp -∥x∥ 2 Z k,p ,with Norm k,p the normalisation constant.Besides, Jensen's inequality yieldsλ∈R d 1{∥Z 1/2 0,p λ∥ ≤ 1 4 } Norm k,p exp λ ⊤ S k -2Z k,p λ * t,p -∥λ∥ 2 Z k,p dλ = R d g k,p (λ) exp λ ⊤ S k -2Z k,p λ * t,p dλ ≥ exp R d g t,p (λ)λ ⊤ S k -2Z k,p λ * t,p dλ = exp S k -2Z k,p λ * t,p ⊤ R d g t,p (λ)λdλ = 1 . Therefore, for all k ∈ N * 1 ≥ Mp,k ≥ Norm k,p Norm p exp(λ * ⊤ t,p S k -∥λ * t,p ∥ 2 Z k,p ) .Markov's inequality yieldsδ ≥ P Mp,k ≥ 1 δ ≥ P Norm k,p Norm p exp(λ * ⊤ t,p S k -∥λ * t,p ∥ 2 Z k,p ) ≥ 1 δ = P λ * ⊤ t,p S k -∥λ * t,p ∥ 2 Z k,p ≥ log Norm p Norm k,p + log(1/δ) .Taking k = t in particular givesδ ≥ P max ∥Z 1/2 0,p λ∥≤ 1 4 λ ⊤ S t -∥λ∥ 2 Zt,p ≥ log Norm p Norm t,p + log(1/δ) .The constraint on λ in the inner expression prevent to use the usual optimal value for subgaussian r.v. which could give a bound for ∥S t ∥ 2Z -1 t,p. Instead, we introduce λ t,p = 1 4 Z -1 t,p S t ∥S t ∥ Z -1 t,p , for which ∥Z 1/2 0,p λ t,p ∥ ≤ 1 4 ∥Z 1/2 0,p Z -1/2 t,p ∥ ∥S t ∥ Z -1 t,p ∥S t ∥ Z -1 t,p ≤ 1 4 . Then δ ≥ P 1 4 ∥S t ∥ Z -1 t,p - 1 16 ∥S t ∥ Z -1 t,p ≥ log Norm p Norm t,p + log(1/δ) = P ∥S t ∥ Z -EQUATIONNorm t,p = λ∈R d 1 ∥Z 1/2 0,p λ∥ ≤ 1 4 exp{-∥λ∥ 2 Zt,p }dλ = 1 det(Z t,p ) λ∈R d 1 ∥Z 1/2 0,p Z -1/2 t,p λ∥ ≤ 1 4 exp{-∥λ∥ 2 }dλ . Noting that ∥Z 1/2 0,p Z -1/2 t,p ∥ ≤ 1, we deduce Norm t,p ≥ 1 det(Z t,p ) R d 1 ∥λ∥ ≤ 1 4 exp{-∥λ∥ 2 }dλ .Therefore,Norm p Norm t,p ≤ det(Z t,p ) det(Z 0,p ) R d 1 ∥λ∥ ≤ 1 2 exp{-∥λ∥ 2 }dλ R d 1 ∥λ∥ ≤ 1 4 exp{-∥λ∥ 2 }dλ .We treat the integrals asR d 1 ∥λ∥ ≤ 1 2 exp{-∥λ∥ 2 }dλ R d 1 λ∥ ≤ 1 4 exp{-∥λ∥ 2 }dλ = R d 1 ∥λ∥ ≤ 1 4 + 1 1 4 < ∥λ∥ ≤ 1 2 exp{-∥λ∥ 2 }dλ R d 1 λ∥ ≤ 1 4 exp{-∥λ∥ 2 }dλ = 1 + R d 1 1 4 < ∥λ∥ ≤ 1 2 exp{-∥λ∥ 2 }dλ R d 1 ∥λ∥ ≤ 1 4 exp{-∥λ∥ 2 }dλ ≤ 1 + exp(-1/16) exp(-1/16) R d 1 1 4 < ∥λ∥ ≤ 1 2 dλ R d 1 ∥λ∥ ≤ 1 4 dλ = 2 d . Thus log Norm p Norm t,p ≤ d log(2) + 1 2 log det(Z t,p ) det(Z 0,p ) = d log(2) + 1 2 log det I + Z -1/2 0,p V t Z -1/2 0,p ≤ d log(2) + 1 2 log i∈[d] 1 + n t,(i,i) Σ i,i (1 + ϵ) pi Σ i,i + ∥B∥ ≤ d log(2) + 1 2 log i∈[d] 1 + n t,(i,i) (1 + ϵ) pi .In particular under event(t ∈ D p ), log Norm p Norm t,p ≤ d log(2) + d 2 log(2 + ϵ) .C Concentration of the covariances estimations (Proposition 2)Proposition 2. Let t ≥ d(d + 1)/2 and δ > 0. Then, P(C c t ) ≤ δ/(t log(t) 2 ) .It is a direct application of the following proposition:Proposition 5. Let δ ∈ (0, 1). Then with probability 1 -δ, for all t ≥ d(d + 1)/2 and (i, j)∈ [d] 2 "reachable", | χt,(i,j) -Σ i,j | ≤ B i B j 4 5h t,δ √ n t,(i,j) + h 2 t,δ n t,(i,j) + 1 n 2 t,(i,j).where h t,δ = (1 + 2 log(1/δ) + 2 log(d(d + 1)) + log(1 + t)) 1/2 . Proof. Let δ > 0, t ≥ d(d + A)/2. We remind C t = ∀(i, j) ∈ [d] 2 "reachable", Σt,(i,j) ≥ Σ i,j . Let (i, j) ∈ [d] 2 "reachable". Then χt,(i,j) = Ŝt,(i,j) -μt,i μt,j = 1 n t,(i,j) t s=1 A s,i A s,j Y s,i Y s,j - 1 n t,i t s=1 A s,i Y s,i 1 n t,i t s=1 A s,j Y s,j , And, χt,(i,j) -Σ i,j = 1 n t,(i,j) t s=1 A s,i A s,j Y s,i Y s,j -S i,j - 1 n t,i t s=1 A s,i Y s,i 1 n t,j t s=1 A s,j Y s,j -µ i µ j = 1 n t,(i,j) t s=1 A s,i A s,j Y s,i Y s,j -S i,j - 1 n t,i t s=1 A s,i Y s,i -µ i 1 n t,j t s=1 A s,j Y s,j -µ j + µ j 1 n t,i t s=1 A s,i Y s,i -µ i + µ i 1 n t,j t s=1A s,j Y s,j -µ j .A triangle inequality yields| χt,(i,j) -Σ i,j | ≤ 1 n t,(i,j) t s=1 A s,i A s,j Y s,i Y s,j -S i,j + 1 n t,i t s=1 A s,i Y s,i -µ i 1 n t,j t s=1 A s,j Y s,j -µ j + B j 2 1 n t,i t s=1 A s,i Y s,i -µ i + B i 2 1 n t,j t s=1A s,j Y s,j -µ j .We make repeated use of the following Lemma Lemma 3. Let (H t ) t∈N * be a filtration, (U t ) t∈N * be an H t adapted martingales bounded by C ∈ R * + with E[U 1 ] = 0, and (1{V t }) t∈N * be a predictable process and δ > 0.Then with probability at least 1 -δ, for all tP t s=1 1{V s }U s 1 + t s=1 1{V s } > C 1 + t s=1 1{V s } 2 log(1/δ) + log(1 + t s=1 1{V s }) ≤ δ .Therefore, with probability at least 1 -δ/2, for all (i, j) and t, (i,j) .1 n t,(i,j) t s=1 A s,i A s,j Y s,i Y s,j -S i,j ≤ 1 n t,(i,j) + 1 t s=1 A s,i A s,j Y s,i Y s,j -S i,j + B i B j 4(n t,(i,j) + 1) ≤ B i B j 4 1 n t,(i,j) + 1 2 log(1/δ) + 2 log(d(d + 1)) + log(1 + t) + B i B j 4n t,(i,j) ≤ B i B j 4 √ n t,(i,j) 2 log(1/δ) + 2 log(d(d + 1)) + log(1 + t) + B i B j 4n t,With probability at least 1 -δ/2, for all i and t, (i,i) .1 n t,i t s=1 A s,i Y s,i -µ i ≤ 1 n t,i + 1 t s=1 A s,i Y s,i -µ i + B i 2n t,(i,i) ≤ B i 2 √ n t,(i,i) 2 log(1/δ) + 2 log(2d) + log(1 + t) + B i 2n t,Therefore, reinjecting those expressions yields that with probability at least 1 -δ, for all (i, j) and t,| χt,(i,j) -Σ i,j | ≤ B i B j 4 √ n t,(i,j) 2 log(1/δ) + 2 log(d(d + 1)) + log(1 + t) + B i B j 4n t,(i,j) + B i B j 2 log(1/δ) + 2 log(2d) + log(1 + t) 4 √ n t,(i,i) n t,(j,j) + B i B j 4n t,(i,i) n t,(j,j) + B i B j 4 1 n t,(j,j) √ n t,(i,i) + 1 n t,(i,i) √ n t,(j,j) 2 log(1/δ) + 2 log(2d) + log(1 + t) + B i B j 4 1 √ n t,(i,i) + 1 √ n t,(j,j) 2 log(1/δ) + 2 log(2d) + log(1 + t) ≤ B i B j 4 √ n t,(i,j) 2 log(1/δ) + 2 log(d(d + 1)) + log(1 + t) + B i B j 4n t,(i,j) + B i B j 2 log(1/δ) + 2 log(2d) + log(1 + t) 4 √ n t,(i,i) n t,(j,j) + B i B j 4n t,(i,i) n t,(j,j) + B i B j 2 1 √ n t,(i,i) + 1 √ n t,(j,j)2 log(1/δ) + 2 log(2d) + log(1 + t) .To simplify this expression, using n t,(i,j) ≤ min{n t,(i,i) , n t,(j,j) } and n t,(i,j) ≤ √ n t,(i,i) n t,(j,j)yields | χt,(i,j) -Σ i,j | ≤ 5 B i B j 4 1 √ n t,(i,j)2 log(1/δ) + 2 log(d(d + 1)) + log(1 + t)+ B i B j 4 1 n t,(i,j)1 + 2 log(1/δ) + 2 log(d(d + 1)) + log(1 + t)+ B i B j 4 1 n 2 t,(i,j) . Denoting h t,δ = 1 + 2 log(1/δ) + 2 log t log(t) 2 d(d + 1) + log(1 + t) 1/2, we have with probability at least 1 -2δ d(d+1)t log(t) 2 | χt,(i,j) -Σ i,j | ≤ B i B j 4 5h t,δ √ n t,(i,j) + h 2 t,δ n t,(i,j) + 1 n 2 t,(i,j).A union bound yields the desired results.C.1 Proof for Lemma 3 Lemma 3. Let (H t ) t∈N * be a filtration, (U t ) t∈N * be an H t adapted martingales bounded by C ∈ R * + with E[U 1 ] = 0, and (1{V t }) t∈N * be a predictable process and δ > 0.Then with probability at least 1 -δ, for all tP t s=1 1{V s }U s 1 + t s=1 1{V s } > C 1 + t s=1 1{V s } 2 log(1/δ) + log(1 + t s=1 1{V s }) ≤ δ .Proof. Let t ≥ 2. Then U t is C sub-Gaussian and for all λ ∈ E exp λ1{V t }U t -λ 2 C 2 2 1{V t } H t-1 ≤ 1 Then (W t (λ)) t∈N * = exp(λ t s=1 1{V s }U s -λ 2 C 2 2 t s=1 1{V s })t∈N * is a supermatringale. We use the Method of Mixtures by integrating for a λ ∼ N (0, 1/C 2 ). This yieldλ∈R C √ 2π exp - λ 2 C 2 2 W t (λ)dλ = C √ 2π λ∈R exp λ t s=1 1{V s }U s - λ 2 C 2 2 (1 + t s=1 1{V s }) dλ = C √ 2π λ∈R exp t s=1 1{V s }U s 2 2C 2 (1 + t s=1 1{V s }) - 1 2 λ - t s=1 1{V s }U s C 2 (1 + t s=1 1{V s }) 2 C 2 (1 + t s=1 1{V s }) dλ = exp t s=1 1{V s }U s 2 2C 2 (1 + t s=1 1{V s }) 1 1 + t s=1 1{V s } ≤ 1 . Therefore, P t s=1 1{V s }U s 1 + t s=1 1{V s } > C 1 + t s=1 1{V s } 2 log(1/δ) + log(1 + t s=1 1{V s }) ≤ δ .Using the stopping time construction from Abbasi-Yadkori et al. ( 2011) yields the property for all t.D Behaviour in the high-probability events (Section 5)The following proposition states that under some assumptions on the sequence of events (E t ), the regret can be bounded by problem-dependent quantities (including Σ, T , or d). They are not all explicitly stated in Proposition 6 to make it adaptive to both algorithms but are hidden in the constants. Proposition 6. Let r ∈ N, e ∈ (1, +∞) r . Let (E t ) t≥d(d+1)/2 be a sequence of events such that for all t ≥ d(d + 1)/2, under E t ,EQUATION)where C and (C s ) s∈[r] are problem-dependent positive constants. C At+1,i is a positive constant depending on A t+1 and i so that, for all a ∈ A, . By considering each of the r sub-sum in Eq. ( 25) and designing sets of event that can happen only a finite number of times.C a,i ≤ 2mΣ i,i . Let c ∈ R * + and (c s ) s∈[r] ∈ (R * + ) r be positive constants such that 1/c + s∈[r] 1/c s = 1. Then, T -1 t=d(d+1)/2 ∆ At+1 1{E t } ≤ 96c 1 C log(m) 2 i∈[d] max a∈A/i∈a C a,i ∆ a + r s=1 1 e s = 2 346 c s CC s log(m) 1/2 md 2 1 + log ∆ max ∆ min + 1 1 < e s <We introduce two sequences (α k ) k∈N * and (β k ) k∈N * , both begin at 1 and strictly decrease to 0 (see Appendix D.1 for their definitions). These sequences are introduced to be able to consider the different terms of Eq. ( 25) separately.EQUATIONand the eventEQUATIONA notable difference from previous approaches is the use of Σ * i,i /C a,i in A 1 t,k instead of set cardinals. This enables the explicit appearance of the C a,i coefficients, which will involve the σ 2 a,i for the application of this proposition to our algorithms.For s ∈ [r], we defineS s t,k = (i, j) ∈ A t+1 , n es t,(i,j) ≤ c s m 2 α k C ∆ 2 At+1 C s (29)and the eventsEQUATION)The following Lemma, proven in Appendix D.2, decomposes (E t ) t≥d(d+1)/2 using these events.Lemma 4. Let's consider the assumptions of Proposition 6. Let A t,k and (A s t,k ) s∈[r] be the events defined in Eq. (28) and Eq. (30). Let k 0 ∈ N * such that 0 < mβ k0 < 1 2m and t ≥ d(d + 1)/2.1{E t } ≤ k0 k=1 1{A t,k } + r s=1 k0 k=1 1{A s t,k } .Using it, we decomposeEQUATIONWe begin with the first term of Eq. ( 31). Let t ≥ d(d + 1)/2, and kEQUATION)Summing over t and k, and including the gaps yieldsEQUATION) (34) Let i ∈ [d],we consider all the actions associated to it. Let q i ∈ N * be the number of actions associated to item i. Let l ∈ [q i ], we denote e l i ∈ A the l-th action associated to item i, sorted by decreasing∆ e l i C e l i ,i, withC e 0 i ,i ∆ e 0 i = 0 by convention. Then T -1 t=d(d+1)/2 ∆ At+1 C At+1,i 1 n t,(i,i) ≤ c 1 mα k C ∆ A t+1 C A t+1 ,i 2 Σ i,i ≤ T -1 t=0 qi l=1 ∆ e l i C e l i ,i 1 n t,(i,i) ≤ c 1 mα k C ∆ e l i C e l i ,i 2 Σ i,i , A t+1 = e l i = T -1 t=0 qi l=1 ∆ e l i C e l i ,i 1 n t,(i,i) Σ i,i c 1 mα k C ≤ 1 ∆ e l i C e l i ,i 2 , A t+1 = e l i = T -1 t=0 qi l=1 ∆ e l i C e l i ,i l p=1 1 1 ∆ e p-1 i C 2 e p-1 i ,i 2 < n t,(i,i) Σ i,i c 1 mα k C ≤ 1 ∆ e p i C 2 e p i ,i , A t+1 = e l i ← decomposing the event ≤ T -1 t=0 qi l=1 l p=1 ∆ e p i C e p i ,i 1 1 ∆ e p-1 i C e p-1 i ,i 2 < n t,(i,i) Σ i,i c 1 mα k C ≤ 1 ∆ e p i C 2 e p i ,i , A t+1 = e l i ← as ∆ e l i C e l i ,i ≤ ∆ e p i C e p i ,i = qi p=1 ∆ e p i C e p i ,i T -1 t=0 qi l=p 1 1 ∆ e p-1 i C e p-1 i ,i 2 < n t,(i,i) Σ i,i c 1 mα k C ≤ 1 ∆ e p i C 2 e p i ,i , A t+1 = e l i ≤ qi p=1 ∆ e p i C e p i ,i T -1 t=0 qi l=1 1 1 ∆ e p-1 i C e p-1 i ,i 2 < n t,(i,i) Σ i,i c 1 mα k C ≤ 1 ∆ e p i C 2 e p i ,i, A t+1 = e l i ← we extend the sum over lEQUATION, i ∈ A t+1 ← we simplify the inner sum≤ qi p=1 ∆ e p i C e p i ,i C e p i ,i ∆ e p i 2 c 1 mα k C Σ i,i - C e p-1 i ,i ∆ e p-1 i 2 c 1 mα k C Σ i,i← the event can only happen a given nbr. of times= C e q i i ,i ∆ e q i i 2 c 1 mα k C Σ i,i ∆ e q i i C e q i i ,i + qi-1 p=1 C e p i ,i ∆ e p i 2 c 1 mα k C Σ i,i ∆ e p i C e p i ,i - ∆ e p+1 i C e p+1 i ,i← summation by parts≤ c 1 mα k C Σ i,i C e q i i ,i ∆ e q i i + qi-1 p=1 C e p i ,i ∆ e p i 2 ∆ e p i C e p i ,i - ∆ e p+1 i C e p+1 i ,i← everything is positiveEQUATION)Reinjecting Eq. ( 35) into Eq. ( 34) yieldsEQUATION)We treat the r other terms in a similar way. Let s ∈[r], t ≥ d(d + 1)/2, and k ∈ [k 0 ], A s t,k = |S s t,k | ≥ β k m 2 ; ∀l < k, |S s t,l | < β l m 2 ⊆ 1 β k m 2 |S 2 t,k | ≥ 1 .Therefore,EQUATION)Summing over t and k yields 37)T -1 t=d(d+1)/2 ∆ At+1 k0 k=1 1{A s t,k } ≤ T -1 t=d(d+1)/2 ∆ At+1 k0 k=1 1 β k m 2 (i,j)∈[d] 2 1 A s t,k ∩ {(i, j) ∈ S s t,k } ← by Eq. (≤ (i,j)∈[d] 2 T -1 t=d(d+1)/2 k0 k=1 1 β k m 2 ∆ At+1 1{(i, j) ∈ S s t,k } = (i,j)∈[d] 2 k0 k=1 1 β k m 2 T -1 t=d(d+1)/2 ∆ At+1 1 n t,(i,j) ≤ m 2/es (c s α k CC s ) 1/es 1 ∆ 2/es At+1. ← by Eq. ( 29) ( 38)Let (i, j) ∈ [d] 2, we consider all the actions which are associated to it. Let q (i,j) ∈ N * be the number of actions associated to the tuple (i, j). Let l ∈ [q (i,j) ], this time, we denote e l (i,j) ∈ A the l-th action associated to tuple (i, j), sorted by decreasing ∆ e l (i,j), with 1 ∆ e 0 (i,j) = 0 by convention. Then,T -1 t=d(d+1)/2 ∆ At+1 1 n t,(i,j) ≤ m 2/es (c s α k CC s ) 1/es 1 ∆ 2/es At+1 ≤ T -1 t=0 q (i,j) l=1 ∆ e l (i,j) 1 n t,(i,j) ≤ m 2/es (c s α k CC s ) 1/es 1 ∆ 2/es At+1 , A t+1 = e l (i,j) = T -1 t=0 q (i,j) l=1 ∆ e l (i,j) 1 n t,(i,j) m -2/es (c s α k CC s ) -1/es ≤ 1 ∆ 2/es e l (i,j) , A t+1 = e l (i,j) = T -1 t=0 q (i,j) l=1 ∆ e l (i,j) l p=1 1 1 ∆ 2/es e p-1 (i,j) < n t,(i,j) m -2/es (c s α k CC s ) -1/es ≤ 1 ∆ 2/es e p (i,j) , A t+1 = e l (i,j) ≤ T -1 t=0 q (i,j) p=1 ∆ e p (i,j) q (i,j) l=p 1 1 ∆ 2/es e p-1 (i,j) < n t,(i,j) m -2/es (c s α k CC s ) -1/es ≤ 1 ∆ 2/es e p (i,j) , A t+1 = e l (i,j) ≤ q (i,j) p=1 ∆ e p (i,j) T -1 t=0 1 1 ∆ 2/es e p-1 (i,j) < n t,(i,j) m -2/es (c s α k CC s ) -1/es ≤ 1 ∆ 2/es e p (i,j) , i ∈ A t+1 ≤ q (i,j) p=1 ∆ e p (i,j) m 2/es (c s α k CC s ) 1/es ∆ 2/es e p (i,j) - m 2/es (c s α k CC s ) 1/es ∆ 2/es e p-1 (i,j) = m 2/es (c s α k CC s ) 1/es ∆ 2/es e q (i,j) (i,j) ∆ e q (i,j) (i,j) + q (i,j) -1 p=1 m 2/es (c s α k CC s ) 1/es ∆ 2/es e p (i,j) ∆ e p (i,j) -∆ e p+1 (i,j) ≤ m 2/es (c s α k CC s ) 1/es ∆ e q (i,j) (i,j) 1-2/es + q (i,j) -1 p=1 ∆ p e (i,j) -2/es ∆ e p (i,j) -∆ e p+1 (i,j) ≤ m 2/es (c s α k CC s ) 1/es ∆ e q (i,j) (i,j) 1-2/es + ∆ e 1 (i,j) ∆ e q (i,j) (i,j)x -2/es dx .If e s = 2, then T -1 t=d(d+1)/2 ∆ At+1 1 n t,(i,j) ≤ m 2/es (c s α k CC s ) 1/es 1 ∆ 2/es At+1 ≤ m(c s α k CC s ) 1/2 1 + ∆ e 1 (i,j) ∆ e q (i,j) (i,j) x -1 dx ≤ m(c s α k CC s ) 1/2 1 + log ∆ max ∆ min .Reinjecting this expression into yields Eq. ( 38), for e s = 2EQUATION)Else, for 1 < e s < 2, thenEQUATION)Finally, for e s > 2,EQUATIONEQUATION)All in all, we reinject Eq. ( 36), Eq. ( 39), Eq. ( 40) and Eq. ( 41) into Eq. ( 31), yielding Let β = 1/5, x > 0. We define β 0 = α 0 = 1. For k ≥ 1, we defineT -1 t=d(d+1)/2 ∆ At+1 1{E t } ≤ T -1 t=d(d+1)/2 ∆ At+1 k0 k=1 1{A t,k } + r s=1 T -1 t=d(d+1)/2 ∆ At+1 k0 k=1 1{A s t,k } ≤ 96c 1 C log(m) 2 i∈[d] max a∈A/i∈a C a,i ∆ a + r s=1 1 e s = 2 346 c s CC s log(m) 1/2 md 2 1 + log ∆ max ∆ min + 1 1 < e s < 2 63.30 1/es c s CC s log(m) 1/es d 2 m 2/EQUATION)Let's first look for an adequate k 0 for Lemma 4, takingEQUATIONfor x = 4k 0 + 2.Besides,k0 k=1 α k β k = (4k 0 + 2)k 0 ≤ 16 log(m) 2 + 52 log(m) + 42 ≤ 48 log(m) 2 (45) as m ≥ 5. Let c ∈ R, c > 1. Then k0 k=1 α 1/c k β k = (4k 0 + 2) 1/c k0 k=1 (β 1/c-1 ) k ≤ (8 log(m) + 14) 1/c k0 k=1(5c-1 c ) k ≤ 30 1/c log(m) 1/c k0 k=1 5 k = 30 1/c log(m) 1/c 5 5 k0 -1 5 -1 = 30 1/c log(m) 1/c 5 4 (5 k0 -1) = 30 1/c log(m) 1/c 5 4 exp log(5) 2 log( √ 2m) log(5) + 2 -1 = 30 1/c log(m) 1/c 5 4 50m 2 -1 ≤ 63m 2 30 1/c log(m) 1/c ≤ 63.30 1/c m 2 log(m) 1/c .Lemma 4. Let's consider the assumptions of Proposition 6. Let A t,k and (A s t,k ) s∈[r] be the events defined in Eq. (28) and Eq. (30). Let k 0 ∈ N * such that 0 < mβ k0 < 1 2m and t ≥ d(d + 1)/2.1{E t } ≤ k0 k=1 1{A t,k } + r s=1 k0 k=1 1{A s t,k } .Proof. Let's consider the assumptions of 6, A t,k and (A s t,k ) s∈[r] be the events defined in Eq. ( 28) and Eq. ( 30). Let k 0 ∈ N * such that 0 < mβ k0 < 1 2m and t ≥ d(d + 1)/2. We first prove that the events for k≥ k 0 cannot happen. Let k ≥ k 0 , A t,k = i∈S 1 t,k Σ * i,i C At+1,i ≥ β k m; ∀l < k, i∈S 1 t,l Σ i,i C At+1,i < β l m .Asβ k m < β k0 m < 1 2m ≤ min i,a Σi,iCa,i and (S 1 t,l ) l is a decreasing sequence of sets,i∈S t,k 0 Σi,i C A t+1 ,i < β k0 m imply S t,k0 = ∅ and i∈S t,k Σ * i,i C A t+1= 0 < β k m. Therefore, A t,k cannot happen and we denoteA t = k≥1 A t,k = k∈[k0] A t,k = k∈[k0] i∈S t,k Σ i,i C At+1,i ≥ β k m; ∀l < k, i∈S 1 t,l Σ i,i C At+1,i < β l m .Likewise, for k > k 0 and s ∈ [r],A s t,k = |S s t,k | ≥ β k m 2 ; ∀l < k, |S s t,k | < β l m 2 .As β k0 m 2 < 1/2 < 1 and (S s t,l ) l is a decreasing sequence of sets, then|S s t,k0 | < β k0 m 2 imply S s t,k0 = ∅ and |S s t,k | = 0 < β k m 2. Therefore, A s t,k cannot happen and we denoteA s t = k≥1 A s t,k = k∈[k0] A s t,k = k∈[k0] |S s t,k | ≥ β k m 2 ; ∀l < k, |S s t,k | < β l m 2 .The idea is now to prove thatA t ∪ r s=1 A s t c = A c t ∩ ∩ r s=1 A s t c ⊆ E c t .We begin by consideringEQUATIONThen, under (A t ) c , denoting S t,0 = A t+1 , as S t,k0 = ∅ and the sets S t,k are decreasing with respect to k,EQUATIONLikewise for s ∈ [r],EQUATION) Denoting S s t,0 = A t+1 × A t+1 , as S s t,k0 = ∅, (i,j)∈At+1 C s n es t,(i,j) = k0 k=1 (i,j)∈S t,k-1 \S t,k C s n es t,i ≤ k0 k=1 (i,j)∈S t,k-1 \S t,k C s 1 c 2 m 2 α k ∆ 2 At+1 C 1 C s ← by Eq. (29) = ∆ 2 At+1 c s m 2 C k0 k=1 1 α k |S t,k-1 | -|S t,k | = ∆ 2 At+1 c s m 2 C k0-1 k=0 1 α k+1 |S t,k | -|S t,k+1 | = ∆ 2 At+1 c s m 2 C |S t,0 | α 1 + k0-1 k=1 |S t,k | 1 α k+1 - 1 α k < ∆ 2 At+1 c s m 2 C 1 α 1 m 2 + k0-1 k=1 β k m 2 1 α k+1 - 1 α k ← by Eq. (48) = ∆ 2 At+1 c 2 C k0-1 k=1 β k-1 -β k α k + β k0-1 α k0 ≤ 1 c 2 ∆ 2 At+1 C . ← by Eq. (44) (49) Therefore, under A c t ∩ ∩ r s=1 A s t c, summing Eq. ( 47) and Eq. (49) i∈At+1 C At+1,i n t,(i,j) + s∈[r] (i,j)∈At+1 C s n es t,(i,j) < 1 c + s∈[r] 1 c s ∆ 2 At+1 C = ∆ 2 At+1 C ,which contradict Eq. ( 25) and thus imply E c . By contraposition, we have proved that E implyA t ∩ r s=1 A s t . Therefore, 1{E t } ≤ k0 k=1 1{A t,k } + r s=1 k0 k=1 1{A s t,k } .E Details for OLS-UCB-C (Section 5.2)E.1 Proof of Proposition 3 Proposition 3. Let δ > 0. Then, OLS-UCB-C yields E T -1 t=d(d+1)/2 ∆ At+1 1 G t ∩ C t = O log(T ) 2 log(m) 2 d i=1 max a∈A/i∈a σ 2 a,i ∆ a , as T → ∞, where σ 2 a,i = j∈a (Σ i,j ) + .Proof. The objective is to use Proposition 6.Proposition 6. Let r ∈ N, e ∈ (1, +∞) r . Let (E t ) t≥d(d+1)/2 be a sequence of events such that for all t ≥ d(dEQUATIONwhere C and (C s ) s∈[r] are problem-dependent positive constants. C At+1,i is a positive constant depending on A t+1 and i so that, for all a ∈ A,EQUATION)where (α k ) k∈N * , (β k ) k∈N * and k 0 ∈ N * are defined in Appendix D.1.We need to check that its hypotheses are satisfied. Let t ≥ d(d + 1)/2 and δ > 0, then we have the Lemma.Lemma 5. Let δ > 0 and t ≥ d(d + 1)/2. Then underEQUATIONAt+1,i = 2 j∈At+1/Σj,j ≤Σi,i (Σ i,j ) + ≤ 2σ 2 At+1,i .Therefore, we can choose r = 3, e = (2, 3/2, 3) and t ) = (G t ∩ t ). Taking c = (4, 4, 4, 4) and identifying the rest of the coefficients yields that OLS-UCB-C satisfiesT -1 t=d(d+1)/2 ∆ At+1 1{G t ∩ C t } ≤ 384f 2 T,δ log(m) 2 i∈[d] max a∈A/i∈a σ2 a,i ∆ a + 692∥B∥ ∞ f T,δ (4d + h 2 t,δ ) 1/2 log(m) 1/2 1 + log ∆ max ∆ min + 1460∥B∥ 4/3 ∞ f 4/3 T,δ h 2/3 t,δ log(m) 2/3 d 2 m 2/3 ∆ -1/3 min + 296∥B∥ 2/3 ∞ f 2/3 T,δ log(m) 1/3 d 2 m 2/3 ∆ 1/3 max .AsEQUATIONE.2 Proof of Lemma 5Lemma 5. Let δ > 0 and t ≥ d(d + 1)/2. Then under {G t ∩ C t }, OLS-UCB-C satisfiesEQUATIONAt+1,i = 2 j∈At+1/Σj,j ≤Σi,i (Σ i,j ) + ≤ 2σ 2 At+1,i .Proof. Let t ≥ d(d + 1)/2 and δ > 0. OLS-UCB-C statisfies the following Lemma.Lemma 6. Let t ≥ d(d + 1)/2 and δ > 0. Then for OLS-UCB-C, under the event {G t ∩ C t },∆ At+1 ≤ f t,δ ∥N -1 t A t+1 ∥ Zt + ∥N -1 t A t+1 ∥ Ẑt .Therefore, under {G t ∩ C t }, andEQUATIONFrom, here, we develop the right-hand side,∥N t A t+1 ∥ 2 Zt = A ⊤ t+1 N -1 t Z t N -1 t A t+1 = (i,j)∈At+1(Z t ) i,j n t,(i,i) n t, (j,j) .As Z t = t s=1 d As Σ * d As + d Σ * N t + ∥B∥ 2 I, we get ∥N -1 t A t+1 ∥ 2 Zt = (i,j)∈At+1n t,(i,j) Σ i,j n t,(i,i) n t,(j,j)+ i∈At+1 n t(i,i) Σ i,i n 2 t,(i,i) + i∈At+1 ∥B∥ 2 n 2 t,(i,i) ≤ i∈At+1 2j∈At+1/Σj,j ≤Σi,i n t,(i,j) Σ i,j n t,(i,i) n t,(j,j)+ i∈At+1 ∥B∥ 2 n 2 t,(i,i), by rearranging terms. Now as for all (i, j) ∈ [d] 2 , n t,(i,j) ≤ min{n t,(i,i) , n t,(j,j) }, then∥N -1 t A t+1 ∥ 2 Zt ≤ i∈At+1 1 n t,(i,i) 2 j∈At+1/Σj,j ≤Σi,i Σ i,j + i∈At+1 ∥B∥ 2 n 2 t,(i,i).At+1,i = 2 j∈At+1/Σj,j ≤Σi,i (Σ i,j ) + yieldsEQUATION)The second term from the right-hand side of Eq. ( 51) is developed in the same manner but involves more terms.∥N -1 t A t+1 ∥ 2 Ẑt = A ⊤ t+1 N -1 t Ẑt N -1 t A t+1 = (i,j)∈At+1( Ẑt ) i,j n t,(i,i) n t, (j,j) .We remind that Ẑt = . Then,∥N -1 t A t+1 ∥ 2 Ẑt ≤ (i,j)∈At+1n t,(i,j) Σ i,j n t,(i,i) n t,(j,j)+ (i,j)∈At+1n t,(i,j) n t,(i,i) n t,(j,j)EQUATION)Reinjecting Eq. ( 52) and Eq. ( 53) into Eq. ( 51) yieldsEQUATIONAt+1,i n t,(i,i) +(i,j)∈At+1(2d + h 2 t,δ /2)∥B∥ 2 ∞ n 2t,(i,j)+ (i,j)∈At+1 5h t,δ ∥B∥ 2 ∞ /2 n 3/2 t,(i,j) + (i,j)∈At+1 ∥B∥ 2 ∞ /2 n 3 t,(i,j).The desired inequality just comes from f T,δ ≥ f t,δ E.3 Proof of Lemma 6 Lemma 6. Let t ≥ d(d + 1)/2 and δ > 0. Then for OLS-UCB-C, under the event {G t ∩ C t },∆ At+1 ≤ f t,δ ∥N -1 t A t+1 ∥ Zt + ∥N -1 t A t+1 ∥ Ẑt .Proof. Let t ≥ d(d + 1)/2 and δ > 0. The error in estimating the mean reward for action a with ⟨a, μt ⟩ is bounded asa ⊤ (μ t -µ) ≤ ∥N -1 t a∥ Zt t s=1 d As η s Z -1 t . The definition of G t = t s=1 d As η s Z -1 t ≤ f t,δ yields that in this event, ⟨A t+1 , μt ⟩ ≤ ⟨A t+1 , µ⟩ + f t,δ ∥N -1 t A t+1 ∥ Zt , and ⟨a * , µ⟩ -f t,δ ∥N -1 t a * ∥ Zt ≤ ⟨a * , μt ⟩ .By the definition of A t+1 for OLS-UCB-C in (6),⟨a * , μt ⟩ + f t,δ ∥N -1 t a * ∥ Ẑt ≤ ⟨A t+1 , μt ⟩ + f t,δ ∥N -1 t A t+1 ∥ Ẑt .Combining the expressions gives⟨a * , µ⟩ + f t,δ (∥N -1 t a * ∥ Ẑt --1 t a * ∥ Zt ) ≤ ⟨A t+1 , µ⟩ + f t,δ (∥N -1 t A t+1 ∥ Zt + ∥N -1 t A t+1 ∥ Ẑt ) .Now, we use the fact that under C t , Ẑt uses coefficient-wise upper bounds of Σ, which yields that∥N -1 t a * ∥ 2 Zt ≤ ∥N -1 t a * ∥ 2 Ẑt .Rearranging terms the desired result.E.4 Proof of the gap-free bound Theorem 1. Let T ∈ N * and δ > 0.Then, OLS-UCB-C (Alg. 2) satisfies the gap-dependent regret upper boundE[R T ] = Õ log(m) 2 d i=1 max a∈A/i∈a,∆a>0 σ 2 a,i ∆ a ,where σ 2 a,i = j∈a max{Σ i,j , 0}, and the gap-free regret upper boundE[R T ] = Õ log(m) √ T d i=1 max a∈A/i∈a σ 2 a,i . Proof. Let ∆ > 0, then T -1 t=d(d+1) ∆ At+1 1{G t ∩ C t } = T -1 t=d(d+1) ∆ At+1 1 G t ∩ C t ∩ (∆ At+1 ≤ ∆) + T -1 t=d(d+1) ∆ At+1 1 G t ∩ C t ∩ (∆ At+1 > ∆) ≤ T ∆ + T -1 t=d(d+1) ∆ At+1 1 G t ∩ C t ∩ (∆ At+1 > ∆) .Adapting Proposition 6 to account for∆ At+1 > ∆ yields T -1 t=0 ∆ At+1 1{G t ∩ C t ∩ (∆ At+1 > ∆)} ≲ 1 ∆ log(T ) 2 log(m) 2 i∈[d] max a∈A/i∈a σ 2 a,i .where ≲ is an inequality up to constant factors (when T varies).Balancing T ∆ and1 ∆ log(T ) 2 log(m) 2 i∈[d] max a∈A/i∈a σ 2 a,i yields E[R T ] = O log(m) log(T ) √ T i∈[d] max a∈A/i∈a σ 2 a,i .F Details for COS-V (Section 5.3) Proof. Let δ > 0, t ≥ d(d + 1)/2. We remindEQUATIONwhere g t,δ = 2 log 2dt log(t) 2 + log(1/δ) EQUATIONProof. Let δ > 0. We first make use of the following Lemma.EQUATIONEQUATION)This enables to use a "modified" version of Proposition 6, which do not consider covariances.Proposition 7. Let r ∈ N, e ∈ (1, +∞) r . Let (E t ) t≥d(d+1)/2 be a sequence of events such that for all t ≥ d(d + 1)/2, under E t ,∆ 2 At+1 C ≤ i∈At+1 C i n t,(i,j) + s∈[r] i∈At+1C s n es t,(i,j) (57) where C and (C s ) s∈ [r] are problem-dependent positive constants. C i is a positive constant depending on i so that,EQUATIONwhere (α k ) k∈N * , (β k ) k∈N * and k 0 ∈ N * are defined in Appendix D.1.Applied to COS-V, this yieldsEQUATIONf t,δ = 6 log(1/δ) + 6 log(t) + (d + 2) log(log(t)) + 3d 2 log(2) + log(1 + e) , h t,δ = (1 + 2 log(1/δ) + 2 log(d(d + 1)) + log(1 + t)) 1/2 , g t,δ = (1 + log(2dt log(t) 2 ) + log(1/δ)) 1/2 .We deduceEQUATIONEQUATIONProof. Let t ≥ d(d + 1)/2 and δ > 0. Then∆ At+1 = ⟨a * A t+1 , µ⟩ = ⟨a * , µ -μt ⟩ + ⟨a * -A t+1 , μt ⟩ + ⟨A t+1 , μt -µ⟩ ≤ ⟨a * , µ -μt ⟩ + ⟨A t+1 , μt -µ⟩ by definition of A t+1 . Besides, ⟨a * , µ -μt ⟩ = i∈a * µ i -μt,i = i∈a * µ i -μt,i + μt,i -μt,i . Under G t ∩ C t , for all i ∈ a * , µ i -μt,i ≤ f t,δ Z 1/2 t,i n t,(i,i) . Under H t , for all i ∈ a * , μt,i + (1 + g t,δ )f t,δ Ẑ1/2 t,i n t,(i,i) -μt,i ≤ g t,δ f t,δ Ẑ1/2 t,i n t,(i,i) μt,i -μt,i ≤ -f t,δ Ẑ1/2 t,i n t,(i,i) . Therefore, under {G t ∩ H t ∩ C t }, 0 ≤ ∆ At+1 ≤ ⟨A t+1 , μt -µ⟩ .We now develop the expressionEQUATIONẐt,(i,i)EQUATIONẐt,(i,i)EQUATION∥N -1 t A t+1 ∥ 2 Zt = (i,j)∈At+1n t,(i,j) Σ i,j n t,(i,i) n t,(j,j)+ i∈At+1 n t(i,i) Σ i,i n 2 t,(i,i) + i∈At+1 ∥B∥ 2 n 2 t,(i,i) ≤ (i,j)∈At+1 n t,(i,j) Σ i,i Σ j,j n t,(i,i) n t,(j,j) + i∈At+1 Σ i,i n t,(i,i) + i∈At+1 d∥B∥ 2 ∞ n 2 t,(i,i) ≤ (i,j)∈At+1 n t,(i,j) (Σ i,i + Σ j,j )/2 n t,(i,i) n t,(j,j) + i∈At+1 Σ i,i n t,(i,i) + i∈At+1 d∥B∥ 2 ∞ n 2 t,(i,i) ≤ i∈At+1 (m + 1)Σ i,i n t,(i,i) + i∈At+1 d∥B∥ 2 ∞ n 2 t,(i,i).Therefore,∆ 2 At+1 ≤ i∈At+1 36mg 2 t,δ f 2 t,δ Σ i,i n t,(i,i) + i∈At+1 9mg 2 t,δ f 2 t,δ (2d + h 2 t,δ )∥B∥ 2 ∞ n 2 t,(i,i) + i∈At+1 45g 2 t,δ f 2 t,δ h t,δ ∥B∥ 2 ∞ n 3/2 t,(i,i) + i∈At+1 9mg 2 t,δ f 2 t,δ ∥B∥ 2 ∞ n 3 t,(i,i) + i∈At+1 4mf 2 t,δ Σ i,i n t,(i,i) + i∈At+1 2f 2 t,δ d∥B∥ 2 ∞ n 2 t,(i,i) ≤ i∈At+1 4mf 2 t,δ Σ i,i (9g 2 t,δ + 1) n t,(i,i) + i∈At+1 f 2 t,δ ∥B∥ 2 ∞ 27mdg 2 t,δ h 2 t,δ + 2d n 2 t,(i,i) + i∈At+1 45g 2 t,δ f 2 t,δ h t,δ ∥B∥ 2 ∞ n 3/2 t,(i,i) + i∈At+1 9mg 2 t,δ f 2 t,δ ∥B∥ 2 ∞ n 3 t,(i,i) ≤ i∈At+1 40mf 2 t,δ g 2 t,δ Σ i,i ) n t,(i,i) + i∈At+1 29mdf 2 t,δ ∥B∥ 2 ∞ g 2 t,δ h 2 t,δ n 2 t,(i,i) + i∈At+1 45g 2 t,δ f 2 t,δ h t,δ ∥B∥ 2 ∞ n 3/2 t,(i,i) + i∈At+1 9mg 2 t,δ f 2 t,δ ∥B∥ 2 ∞ n 3 t,(i,i).This finally yields∆ At+1 f 2 T,δ g 2 T,δ ≤ i∈At+1 40mΣ i,i n t,(i,i) + i∈At+1 29mdh 2 t,δ ∥B∥ ∞ n 2 t,(i,i) + i∈At+1 45mh t,δ ∥B∥ 2 ∞ n 3/2 t,(i,i) + i∈At+1 9m∥B∥ 2 ∞ n 3 t,(i,i).This section outlines some experimental results.In this experiment, the objective is to show the effect of the smallest suboptimality gap ∆ min over theoretical gap-dependent regret upper bounds for ESCB-C and OLS-UCB-C. To that end, we sampled 100 environments with different ∆ min , with a constant number of items d = 20, a horizon of T = 10 5 rounds, and randomly sampled structures. We represent theoretical upper bounds with respect to 1/∆ min in Fig. 1 .For readability reasoning, we have rescaled and reweighted the different components of the sums so that the leading term in the upper-bounds (1/∆ min or 1/∆ 2 min for ESCB-C or OLS-UCB-C) is greater/smaller than the rest, in a significant number of cases. In particular, all the theoretical upper bounds have the formR T ≤ C ∆ min + C ′ ∆ 2 min + C r Rest ,where C, C ′ and C r are the tuned constants.For OLS-UCB-C,Rest = ∆ max (d(d + 1)/2) + ∥B∥ ∞ f T,δ (4d + h 2 t,δ ) 1/2 log(m) 1/2 1 + log ∆ max ∆ min + ∥B∥ 4/3 ∞ f 4/3 T,δ h 2/3 t,δ log(m) 2/3 d 2 m 2/3 ∆ -1/3 min + ∥B∥ 2/3 ∞ f 2/3 T,δ log(m) 1/3 d 2 m 2/3 ∆ 1/3 max . For ESCB-C, Rest = ∆ max (d(d + 1)/2) + log(T ) log(m) 2 i∈[d] max a∈A/i∈a σ2 a,i ∆ imin + log(T ) log(m) i,j log ∆ (i,j),max ∆ (i,j),min + log(T ) log(m) i log ∆ i,max ∆ i,min + log(T ) log(m) i,j ∆ -1/3 (i,j),min .When the minimal gap is too small (right part of Fig. 1 ), both upper-bounds are of the magnitude of either 1/∆ 2 min or 1/∆ min (depending on the algorithm). In this case, the theoretical regret bound of OLS-UCB-C outperforms the one of ESCB-C (green dots vs. blue dots). On the other side, when the gap is big enough, the remaining terms have more impact. In this case, ESCB-C has a better theoretical guarantee (orange dots vs. red dots). We represent the pseudo-regret evolutions in Fig. 2 . The evolutions remain the same until 10 3 rounds. After that, ESCB-C seemingly performs better than OLS-UCB-C which has a supplementary log(t) factor and is more conservative. However, just before 10 5 rounds, we can observe a slight regime change for ESCB-C while the pseudo-regret of OLS-UCB-C continues to increase smoothly. The average regret of ESCB-C seems to have an inflexion point upward to meet the q75 curve. 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. 
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: The paper poses no such risks.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: The paper does not use existing assets.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. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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.38th Conference on Neural Information Processing Systems (NeurIPS 2024).(b) We denote Õ for O when T → ∞, up to poly-logarithmic terms.(a) Note that OLS-UCB incur a ∆ -2 term in its gap-dependent bound. This was overlooked by the authors but yields a T 2/3 gap-free bound.(b) Assuming A has matroid structure, the computational complexity is improved compared to a O(P ) for large P . 
 
 Appendix:  


Decision: All reviewers found the paper to be technically solid and the results to be interesting, and have only raised minor concerns. All of these concerns were addressed by the author rebuttals, and thus it was easy to come to the decision that the paper should be accepted to NeurIPS 2024.

Reviews: review: paper_summary: paper_summary: This paper tackles the combinatorial semi-bandits problem and provides many theoretical results, including gap-free variance-dependent upper bounds for both deterministic and stochastic sampling strategies, and for the least, they also provide a corresponding lower bound.
strength_weakness: strength_weakness: The paper does not provide any empirical evaluation, it would have been interesting to see how the presented algorithms perform empirically against its competitors. But given the theoretical contributions and nature of this paper, this is okay for me.

Apart of that I have only the following rather minor issues and typos/suggestions:
- Be more precise in the formulation of the lower bound (Thm. 2): In which sense does the inequality hold, in expectation? Also, is policy restricted deterministic policies here?
- Some of the notations may be clear for most readers, but should for the sake of completeness still be properly introduced. E.g., $\mathbb{N}^\ast$, $\mathbf{I}$ and which logarithm (base) $\log$ refers to.
- In Algo 2, line 3,  does it have to be $\leq 2$ instead of $\leq 1$?
- 8: yield[s]
- 10: $\mathcal{O}(\sqrt{T})$ instead of $\sqrt{T}$?
- 28: At each round
- 108: adaptative
- 139: positive semi-definite
- 269: $\mathbb{P}(\mathcal{C}^c)$
- 272: sketch of the proof
- You oftentimes write $A\bigcap B$ instead of $A\cap B$, why?
questions: questions: - Do you have a feeling how sensible the regret is w.r.t. the vector $B$? You assume this to be known, but I could imagine that in practice it's oftentimes unknown.
- In Table 1, do you know how $C_{1/T}^{opt}$ scales in comparison to $d^2$? That is, do you know that $OLS-UCB-C$ outperforms $ESCB-C$ regarding time complexity?
- Both your algorithms have a parameter $\delta > 0$, which is not contained in the upper bounds. Could you say how the behaviour of the regrets are w.r.t. this parameter?
limitations: limitations: The authors have adequately addressed the limitations of their work.
paper_summary: paper_summary: The paper "Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits" addresses the challenge of designing algorithms that adapt to covariance in the context of stochastic combinatorial semi-bandits, where decision-makers face a set of actions exponentially large in the number of base items.
strength_weakness: strength_weakness: 1. The assumption that the reward (Lines 45-46) for each base item \( Y_{t,i} \) is bounded by \( \frac{B_i}{2} \) may be strong, where reward distributions can exhibit significant variability and are not tightly bounded. 

2. While the algorithms' theoretical framework and mathematical formulation are well-articulated, the lack of experimental results or simulations leaves a crucial gap.
questions: questions: 1. Concerns regarding the role of `f_t,δ` and `g_t,δ` functions in Eq. 6 and 7.
The algorithms utilize the functions `f_t,δ` and `g_t,δ` to dynamically adjust the exploration strategy. The paper implies an increase in `f_t,δ` and `g_t,δ` as \( t \) increases, which leads to an increasing exploration bonus and variance over time. This design choice raises several concerns and questions, especially from an intuitive standpoint:

     a) Increasing Exploration Over Time: Typically, one might expect that as an algorithm learns more about the environment, the need for exploration would decrease, reducing the exploration bonus and variance. The paper’s approach where `f_t,δ` increases with \( t \) seems counterintuitive. An explanation or justification for why increased exploration is necessary or beneficial as the algorithm progresses would be crucial. 

     b) Design Justification for `g_t,δ` and `f_t,δ`: The paper lacks a detailed explanation for the design of `g_t,δ` and `f_t,δ`. Are there specific characteristics of the problem domain or empirical observations that suggest this approach? 

   c) Impact on Algorithm’s Performance: How does the increasing trend of `f_t,δ` and `g_t,δ` impact the algorithm's overall performance across different learning stages? Some insights into how this approach compares to more traditional methods where exploration decreases over time would be beneficial. 

2. The paper specifies using a Gaussian distribution in Eq. 7 for parameter sampling within the COS-V algorithm. Could the authors provide further justification for the choice of a Gaussian distribution in this context?
limitations: limitations: As described in the paper, the results and theorems are discussed with comments made especially about some limitations.
paper_summary: paper_summary: The paper focuses on stochastic combinatorial semi-bandit problems where a player selects from a power set of actions comprising subsets of d base items. It underscores the importance of adapting to the problem structure to achieve optimal regret bounds, emphasizing the use of covariance matrix estimation to enhance performance. The proposed "optimistic" algorithms, OLS-UCB-C and COS-V, employ online covariance estimation. While COS-V prioritizes improved computational efficiency over slight optimality, inspired by Thompson Sampling, it marks the first sampling-based algorithm to achieve a $T^.5$ gap-free regret bound.
strength_weakness: strength_weakness: The log(T) term has a power 3 in the regret bound, which can be improved.

The approach of estimating the covariance matrix online and using it for confidence bounds is not new.

No empirical evaluation.
questions: questions: Do you think the log(T)^3 factor can be reduced ? Why is there such a factor, whereas usually there is simply a log(T) factor ?
limitations: limitations: A sharp dependence on the horizon $T$ is more important for the instance-dependent guarantees.

Comments: comment: Thank you for your understanding and for raising the score; we value your careful consideration of our contributions.
Thank you for your clarification. I will increase the score by one point based on this discussion.
I read the authors’ rebuttal and the comments of other reviewers. I would like to keep my score unchanged.
We thank the reviewer for responding to our rebuttal and hope that we have adequately addressed their concerns regarding the design of our algorithms and our results. We kindly ask the reviewer to take this into consideration in their final assessment.

We would like to emphasize again that our contributions are focused on the theoretical aspects of combinatorial bandits. Our paper is already dense with significant theoretical contributions, including new gap-free regret bounds, improved computational complexity, and a novel stochastic algorithm with analysis that combines the computational efficiency of Thompson Sampling with the analytical strengths of optimistic algorithms, all of which contribute to a deeper understanding of combinatorial bandits.

The empirical study we provided in the rebuttal primarily serves to demonstrate that our algorithms can be implemented, achieve the expected logarithmic regret expected by the theory, and perform well in practice compared to their competitors. We acknowledge that this study alone is not sufficient, and we will strive to conduct more thorough experiments in the final version (although we do not expect it to be considered as a contribution of our current work).

Regarding the additional questions, due to time constraints during the rebuttal phase and the high computational cost of existing combinatorial bandit algorithms, our experiments were conducted on a single synthetic dataset and should be interpreted with caution.

> I have reviewed the experiments [...].

Note that due to the log-log scale, the early shape of the regret curves should be interpreted with caution, as they correspond to only a few rounds $(\approx 30)$ compared to the total number of rounds $(\approx 10\,000)$. Furthermore, the curves are only valid after the measurement at $t=10$; prior to that, they mistakenly appear flat. The early behavior is primarily influenced by how the algorithms perform initial exploration and may be affected by hyper-parameter calibrations, which were not thoroughly optimized in this case.

What is more important to observe in these experiments is the behavior at the end of the regret curves:

- Both OLS-UCB-C and ESCB-C-approx appear to have converged and entered the logarithmic regret regime. The difference between them seems to be due to constant terms related to their exploration strategies, but it does not seem to increase over time.
- Towards the end, the per-round regret of C-UCBV is higher than that of OLS-UCBV, indicating that its cumulative regret will eventually be higher. This synthetic instance was "easy" enough for both algorithms to reach the logarithmic regime. However, it's important to note that in more challenging instances, ESCB-C only guarantees a worst-case regret of $O(T^{2/3})$, while our algorithm provides a stronger guarantee of $O(\sqrt{T})$.

> Covariance-Adaptation and error bars.

Indeed, having error bars is important, and we will include them in the final version. Unfortunately, we did not have time to include them in this preliminary experiment presented in the rebuttal. The adaptivity of our algorithms (and ESCB-C) to the covariance structure of the base items can be inferred from the per-round regret (i.e., the derivative) at the end of the plot. We observe that ESCB-C and OLS-UCB-C maintain a relatively similar distance asymptotically. In contrast, C-UCBV (C-UCB with plugged-in variance estimators) has also converged, but its final per-round regret is slightly worse than both. This is likely because C-UCBV does not account for covariance but instead assumes worst-case correlations between items. However, we must emphasize that this could be an artifact, and these experiments are not thorough enough to draw definitive conclusions.
Dear authors, thank your for your rebuttal, I have no further questions.
Thank you for the response from the authors. 
1. I have reviewed the experiments conducted by the authors, and I am particularly curious about the regret pattern of OLS_UCBV, which shows a distinct zigzag shape: it starts with a slow increase in regret, followed by a sharp rise, and then it tends to converge. This has also piqued my curiosity about the specific settings of the randomly generated synthetic environment, and it appears that its results are inferior to those of C_UCBV and ESCB_C_approx.

2. Additionally, if it is Covariance-Adaptive, I would like to know how the fluctuations or error bars of the actual performance of the algorithm proposed by the authors compare to those of other algorithms across multiple random seeds.