Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits
Authors: Julien Zhou
Pierre Gaillard
Thibaud Rahier
Houssam Zenati
Julyan Arbel
Venue: NeurIPS 2024 poster (2024)
Keywords: Combinatorial Semi-Bandit
Upper Confidence Bound
Thompson Sampling
Confidence Ellipsoid
Primary area: bandits

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.

Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits
Julien Zhou
Pierre Gaillard
Thibaud Rahier
Criteo AI Lab Paris, France
Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK, 38000 Grenoble, France
Criteo Al Lab, Paris, France
Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK, 38000 Grenoble, France
julien. www.minooiiiaaa..m
Houssam Zenati
Julyan Arbel
Université Paris-Saclay, Inria, Palaiseau, France
Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK, 38000 Grenoble, France
Abstract
We address the problem of stochastic combinatorial semi-bandin where player selects among P actions from the power of containing d base items. Adap- tivity to the problem's 's structure is essential in order to obtain optimal regret upper bounds. As estimating the coefficients of covariance matrix can be manageable in practice, leveraging them should improve the regret. We design "optimistic" covariance-adaative algorithms relying on online estimations of the covariance structure, called OLS-UCB- and COS-V (only the variances for the latter). They both yield improved gap-free regret. Although COS-V can be slightly suboptimal, it improves computational complexity by taking inspiration from Thompson Sampling approaches. It is the first sampling-basee algorithm satisfying O(VT) 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 >> but also when d, which is not covered by existing analyses.
Introduction
In sequential decision-making the bandit framework has been extensively studied and was instrumen- tal to several applications, e.g. A/B testing (Guo et al., 2020), online advertising and recommendation services (Zeng et al., 2016), network routing (Tabei al., 2023), demand-side management (Brégère al., 2019), etc. Its popularity stems from its relative simplicity, allowing it to model and analyze wide range challenging real-world settings. Reference books like Bubeck and Cesa- Cesa-Bianchi (2012) or Lattimore and Szepesvári (2020) offer wide perspective on the subject.
In this framework, a decisionnmaake or player must make choices and receives associated rewards, but it lacks prior knowledge of its environment. This naturally leads to an trade-off: the player must explore different actions to determine the best one, but inefficient exploration strategy may harm the cumulative rewards. Efficient algorithms rely on exploiting the
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

environment's 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 subset of base items and receives 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 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,..... (1...... yielding stochastic rewards. A player accesses these rewards through set A S {0, 1)dh of P N actions, each corresponding to a subset at most m 2 5 items ( We refer to actions a E A using their components vector a = (ai)iE(d) E {0, 1)dd where for all j E [d]. 0j = 1 if and only if action contains base item j.
The player interacts with an enviroument over a sequence of T E N rounds. At each round t E [T], the player chooses an action A, E AA the environment samples a reward vector Y E R the player observes the realization for every item contained in Ac, and receives their sum. The interactions between the player and the environment are summarized in Framework 1.
Framework Stochastic Combinatorial Semi-Bandie For each & E (1...., T):
The player chooses an action A, E .A.
The environment samples vector of rewards Y, Rd from fixed unknown distribution. The player receives the reward (Ar, Y2) = Ar,
The player observes Yr,; for all E [d] s.t. Ar,i 1.
Assumptions. We make the following assumptions. For all f E [T]. Y, is independent of the past rewards and the player's decision (AA,, Yi...., At-1, Yt-1, There exists a mean reward vector E|Y;] = μ E I and a second order moment matrix S = E[ E (R)... The positive semi- definite covariance matrix denoted Σ E Ma(R), with Σ = yup There exists known vector B E R4 such that for all E [T] and E [d]. |Y,il S B,/2 almost surely (and [Y,, - pil S B:). The objective of the decision-maker is to minimize the expected cumulative pseudo-regret defined as:
E. R = E Σ
Ar, mb) Di= AA
where (..-) denotes the usual inner product in Rd, a" arg maxae (a, ud) is an optimal action, and A a, (u) is the sub-optimality gap for action a E A.
1.1 Existing work and limitations
Combinatorial semi-bandi problems have been extensively studied by the bandit community since their introduction by Chen et al. (2013). Here, we only highlight key carlier works related to this paper. For 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 regret upper bound uniform over all possible covariance matrices Σ (hence, paying the worst-case). Combes et al. (2015) highlighted the importance of designing E-adaptive algorithms by showing that the regret could be improved by a factor of 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-UCS requires prior knowledge of positive semi-definite covariance proxy matrix T, such that for all t 2 1 and for all u E Rd, Efcxp( (u, Y, - 14)1 & exp(3 [lul(²). Estimating I in
"Throughout the paper, the term item (or base item) refers to an element in the set [d]. while an action denotes 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-adaptio gap-dependent regret upper bounds. Yet, it suffers from an additive constant of order A which prevents its conversion into an ((vT)(t) gap-free bound. Thus, none of the above works proposes ((VT) gap-free and covariance-adaptii
algorithm, ESCB-C, with asymptotically optimal
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 large action set A C {0. 1)dd 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 cani-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 ft E I at each round + 1 E [T' - 1] from distribution representing "belief" over the parameter μs, taking decision A,- E arg max (a. ja)), 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 known variance-prox I 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 A Am term, preventing ((VT) gap-free rate. A central contribution in our paper is the combination of the computational efficiency for sampling algorithms with the covariance-adum -vaapivce-adaativiity Õ(VT) 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 / >> 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-bande feedback. While the conventional stochastic combinatorial regret upper bound grows as O(VmdT) (Kveton et al., 2015), a O(mmPT) 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-grainee analyses, clearly taking the structure into account, are therefore needed.
1.2 Contributions
A new deterministic optimism-based algorithm (Section 2). 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:
We present OLS-UCB-C (Online
First optimal gap-free regret upper bound. OLS OLS-UCB-C yields similar gap-dependent regret bound as ESCB-C from Perrault et al. (2020b) up to logarithmic factors, and the first optimal covariance-adaptativy gap-free Õ D(VT) 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 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 opti- mization 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 caamiism-bssed 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:
(ewee denote Ô for O when T + cc. up poly- lol-rtogaii terms.
3

---

Improved complexity for P > 1 compared to other deterministic mani-bandit algorithms. COS-V can be efficient in the very large P regime, which is the main blind spot of OLS-UCB-O
First gap-free O(VT) 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. enables the derivation of gap-dependent bound for COS-V that does not involve the A Am term we typically find the analysis for other TS algorithms (Wang and Chen, 2018; Perrault et al., 2020a), consequently leading to new (VVT) variance-adaptive gap-free regret upper bound for a sampling algorithm.
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 the gap-free upper bound we establish for OLS-UCB-C.
Technical details are deferred Section 4, Section 5, and the Appendix.
Table Asymptotic Ö(-) regret bounds and per-round time complexities up poly-logarithmic terms d, for the following deterministic algorithms: UCB (Aucr et al., 2002a), UCBV (Audibert et al., 2009), CUCB (Kveton et al., 2015), OLS- UCB-UCB-- CC (Degenne and Perchet, 2016), ESCB-C (Perrault et al., 2020b), and OLS-UCE. (ours); well the two stochastic algorithms: 2TS-Gaussian (Perrault et al., 2020a) and COS-V (ours). Notations: refers actions; and j refer items; denotes the maximum number items per action; is a vector bounds on items' rewards;
covariance-prox) matrix; 7 is maximum of "correlations- proxy"; we abbreviate max(2; (z, 0} to (z)4 for any x E R 1//T refers to the complexity of the optimisation step needed in ESCB-C.
Coge
Fdbek.
Algorithm
Info.
Time Complexity
Gap-Free Asymptotic Regret
E. (a B)2) 1/2
UCB
P
Bndt.
UCBV
Ø
P
(T a TEa)
1/2
(Tmd) 1/2 1/11
CUCB
mP
OLS-UCB())
T
m² + Pd2
Ø
S-Bndt.
ESCB-C
m² + CIPT
Ø (TE, maXa/iEa Σ (Er,))+) 1/2
OLS-UCB-C
Ø
m² + Pd?
CTS-Gaussian"
r
poly(d)
Ø (Tm EiE(aj Eq,))
S-Bndt.
COS-v())
Ø
poly(d)
1/2
2
Covariance-adaptatiee deterministic algorithm: OLS-UCB-C
In this section, we design a new algorithm that efficiently leverages the semi-bandit feedback. approximates the coefficients of the covariance matrix Σ online. The approximation is symmetric by construction and yields a coefficient- wiife upper bound of Σ, but it is not necessarily positive semi-definite, constraint that can be challenging impose in practice.
2.1 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 [d] and every "reachable" couple (i,j) E [d]² at least once.
Nooe that OLS-UCB incur a term in its gap-dependent bound. This was overlooked by the authors but yields 2/3 gap-free bound. (b) Asssuming AA has matroid structure, the computational complexity is improved compared to O(P) for large P.

---

Rewards means estimation. At each round t + 1 E [T 1), the algorithm uses an empirical mean ju for μ defined as
Algorithm 2 ULS-UCB-C Input > 0, B E RÇ. for 1,...,7 do if {a E AA] mi]() (t,(i.) < 1] * then
i N,
Y:
(2)
where de diag(a) E MR. is the diago- nal matrix the elements in a A: (t,().) is the number of times items i and (with possi- bly == j) have been chosen together; N₂ (R) is the diagonal ma-
Choose any A, in the above set.
else
Compute fi-1 from (2).
(t.)) trix of item counts.
Compute Σ,- from (3) and (4).
Compute Z,-1 from (5).
Choose A, E .A from (6).
Rewards covariances estimation. The covari- ances are estimated by
Environment samples Y; Rd
Receive reward (A,, Y1) = E, M,,
(t,( S(,(is) j
(3)
end if end for
where St,(1,) = De.(i.)) E.=1 A Ae..AosYaRYa..
The algorithm uses E., coefficient-wis upper-confidence bound of E whose coefficients defined for a fixed as
B, B5
5
h2
En,(s) = Xe.(ts) +
4
(Te,(E5)
(i.()
(i,(1.))
2
1/2
where fe.5 = (1 2log(/o(//0)) + 2 log (flog(t) 1)) + log(1 +1)
Optimistic action choice. Following the 'optimistic' principle of UCB-like algorithms, the estimated rewards ((fe, a)) are inflated by bonuses, yielding corresponding upper confidence bounds. The bonuses involve the history through regularized empirical design matrix (with empirical covariances):
2, Σ dA E.,,Eda, +ds I
where dy, diag(Ei ( E (R))., I is identity matrix and E, the coefficient-wiss upper bound for the covariance matrix defined in (4). Formally, OLS-UCB-O chooses
A+11 arg max (a, (r) + fr,6 ||N:'allz.) aeA
(6)
where fi, 6log(1/6) + 6 log(t) + (d 2) log(log(tt)) + 3d 2 log((2) + log(1 + +c))
Efficiency improvement. While Perrault et al. (2020b) use an axis-reali 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.
2.2 Regret upper bounds
Theorem 1. Let T N* and 8 0.
Then, OLS-UCB-C (Alg. 2) satisfies the gap-dependent regret upper bound
d
E RT] = Ô (oog(m))
Fa.i
max
aEA/iEu, >0
A
where 02, =Eeea max Ei 0}, and the gap-free regret upper bound
E[Rr] = δ -0(1og(m)VT Ei
(log(m)VT
max oa.i aEA/iga
The proof is outlined in Section 5 and the specific details presented in Appendix E.
5

---

Optimal gap-free bound. This result shows that OLS-UCB-CO yields the same vap-dependent regret upper bound as ESCB-C (Perrault al., 2020b) (up to poly-logarithmic factors) and more importantly yields novel covariance-adaptin
and optimal ((VT) gap-free bound, as shown by the following lower-bound proven in Appendix A. Unfortunately, only the positive coefficients Σ are considered in our bound but the inclusion of negative correlations could be advantageous to reduce the rate at which the regret increases. However, could complicate the analysis greatly and is thus deferred to future research.
Theorem 2. Let m N' such that d/ 2 is an integer, T NN, and E I a covariance matrix. Then, there exists stochastic combinatorial semi-bande with d base items, and reward distribution with covariance matrix E on which for any policy n, the pseudo regret satisfies
1/2
E
T KEld
T
max Σ
8
AEA,EE
JEB
Improvement over CUCB. Our gap-free and gap-dependent bounds outperform those of CUCB (Kveton al., 2015) no matter the covariance structure, as (Tmd) 2 (TT(E) (e) Besides, in the particular case of a diagonal Σ. our gap-free upper bound gains a factor at least vm over the one of CUCB. In this scenario, o²,t Er, for all A and i a. Our gap-dependent and gap-free upper bounds are then roughly bounded as
Σ
Σ
and V Tr(E),,
min Au aEAfiEa
respectively.
Improvement over UCBV. Assuming that D.g En. the one of UCBV of order (TE. a Σa) 1/2 since in this case Σi=1 max 0² < E. ||]|x Existing semi-bandit analyses could only leverage remi-bandit feedback in the regime P > which natural in combinatorial bandits but not systematic in real-world applications.
for all i, our upper-bound uniformly improves
New sampling algorithm for combinatorial semi-bnnits:: COS-V
In this section, we introduce randomized algo- rithm inspired from TS, enabling to get potentially computational complexity at the cost of not lever- aging off-diagonal covariances.
Algorithm 3 COS-V
Input B. RÇ. for E [T] do
{a E A s.t min(L,)ea (1,6) < <1} # then
The difficulty in designing and analysing TS algo- rithms generally stems from controlling the dom exploration. To that end, we parametrize the exploration distribution using the same estimators as UCB-U
Choose A, in the above set.
else
Compute fuc-1 (2).
Compute (,,-1,(4.)) )eed (4).
3.1 Algorithm: COS-V
Compute (Z.-1,(t.)) from (5). Sample fh-11 from (7) Choose A, arg maxaed (a, #h-1)- Environment samples V, Rdd
We propose sampling strategy using "frequentist" estimators, COS-V, described Algorithm 3.
Receive reward (Ac, Y1) = Σ, Ve,Vi,
The algorithm begins with the same exploration phase OLS OLS-UCB-C. Thereafter each round t + 1 [T 1]. we sample parameters (Ps.)) using 1-dimensional normal distributions biased toward the positive orthant. Formally, for all i E [d]. we sample
end if
end for
Ze.0 fu, ~ N (pe. + (1 sc.5) m Ph n? ml
2//2,
where g1.s = 2 log (2dl log (1)3 (8) 1/2
and Si,s is the same as for OLS-UCB-C.
We denote for 2 up constant factor.

---

3.2 Regret upper bound
Theorem 3. Let T E N,, and 0.
Then, COS-V (Alg. 3) satisfies the gap-dependent regret upper bound
E E = -0(1og( log((m)²
mE
(8)
i,min
i=1
where minn = min (aa, a E A such that E a), and the gap-free regret upper bound
E R = δ log(m) Ei E
(9)
The proof is outlined in Section 5 and the specific details can be found in Appendix F.
Novel "arindee-dependdet bound. Theorem presents the first variance-deeendent bound for sampling- basedd semi-bande algorithm. Unfortunately, integrating the covariances Σx,; 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 A terms present the previous analyses of CTS (Wang and Chen, 2018; Perrault et al., 2020a). In particular, this improvement yields the first Ö(VT) gap-free regret upper bound for sampling strategy.
Mean and covariance estimation
In this section, present concentration results for ie (rewards means) and Σ, (rewards covariances, estimated with Xe) used in OLS-UCB-C and COS-V, which are central to prove Theorem and Theorem (sketched in Section 5).
4.1 Covariance-aware confidence region for the average reward
Average reward estimation. Let E A, t 2 d(d 1)/2, introduced in Section 2.1, the least square estimator for the mean reward vector μ using all the data gathered after round t is
N, E' A Y. N, E.= dA
where the 17 denote the deviations Y, -
Confidence region design. We design confidence regions inspired from LinUCB literature (Rus- mevichientong and Tsitsiklis, 2010; Filippi al., 2010; Labasi-Yadkon al., 201 1) and the work of Degenne and Perchet (2016). Major differences with those works include using Bernstein's 's style concentration inequalities involving the covariance matrix Σ, assuming a multidimensional noise term, and combining them with covering argument to relax dependence in d (peeling trick from Degenne and Perchet, 2016). We introduce the regularized design matrix defined by
Z V N,dy + I
where V, = Σ. da, Ed is the design matrix (of which the OLS-UCB-C and COS-V V use an empirical version). Let St = N.(A, 4), the deviations of (a, (ue) are bounded as
(a, jux n) < || al ||Se|lz,
(10)
Designing confidence region for ||S{|| 2,,1 therefore allows to control the deviations (a, fur uniformly on AA. Let > 0, we define the event
G { || S }
(11)
with frs = (1/5) 6(log(t) + (d+ 2) log log(log(())) + 3d(2 log(2) + log +))]
This event can also be written G; = { || 1lll N. 'N. S fe.t and is therefore equivalent to f4z belonging to an ellipsoid around the true reward mean vector μ.

---

Confidence region probability. The following result proven in Appendix B presents an upper bound for P(G)). Proposition 1. Let 2 d(d + 1)/2 and > 0. Then, P(G{) S 6/(l
Proving this result relies on an argument adapted from Faury al. (2020) and a covering trick from Degenne and Perchet (2016).
4.2 Confidence interval for covariances estimator
Rewards covariances estimator. Let t 2 d(d + 1)/2 and "reachable" couple (i,j) E [d] The coefficients of E can be estimated online by X as introduced in Section 2.1
(t.(1..) St,(K.) A
Rewards covariances upper confidence bound. Let 8 > We use the following coefficient-wise upper estimates of Σ in our algorithms
B,
5/4,8
E.,( = ((,(1)) +
+
4
(e,(it))
(1,(5.)
ni,
with h4 = (1 (1+ 2log(1/0))))) + 2log (tlog(t)dd(d+ 1))
log(1
1/2
Favorable event design. bounding those of Σ:
We define C2 as the event where all the coefficients of Σ, are indeed upper
c= (vi,5) E [d]² "reachable", E.((,,) 2 Eig}
(12)
Favorable event probability. The following result proven in Appendix C presents an upper bound for (CC)).
Proposition 2. Lert 2 d(d + 1)/2 and > O. Then, P(CT) < ()(tlo((t))).
5 Regret upper bounds
In this section, we provide sketch of the proof Theorem and Theorem For both OLS-UCB-C and COS-V, V, the idea to bound the regret is to find sequence of favorable events (E)))d((+1)) that are true with high probability, and under which the regret grows logarithmically with time.
5.1 Template bound
Let (E))erry be a sequence of events, then for both OLS-UCB-C and COS-V VV standard derivations yield
[r] & A Amax (d(d+1)/2 I 2/ P(ET) + Ef A(E)AA+..)
(13)
Assuming that the sequence of events (E))2d((41)/ happens with high enough probability, it is sufficient to control what happens conditionally to it. particular, Proposition 6 in Appendix states that if we can bound A 2 with a linear combination of terms evolving as n (,,j).) for every couple (i.j)= E A4+1 and different & 2 1, then we can infer worst-case behaviour, which yields Theorem and Theorem 3.
In the following, we will refer to the term Ei P(E as the unfavorable event probability and to the term E [ (8,) A A441] as the high-probabilityy regret.
5.2 Regret of OLS-UCB-C
For OLS-UCB-C we consider the sequence of events &, (G, C)) for 1 d(d 1)/2, corresponding the confidence regions of (f+))2d(d+1))) and of (E, (2)(())))224441)) (t.) defined in Section 4. Under these events, we can upper-bound the high- crah--rbbbbilityy regret from Eq. (13) with the following proposition (proven in Appendix E.

---

Proposition 3. Let 8 > 0. Then, OLS-UCB-C yielss
T-1
=olog(cy) log(m)²
- a eEAiiE A.
E
Σ
AAn
max
(=d(d+1)/2
as T + oc, where oa, Ejea(Eig)
Conclusion of the proof. Injecting results from Proposition 3 (high-probabilityy regret) as well as Proposition and Proposition 2 (unfavorable event probability) into the template bound (13), we get
E Rr) = o (og(())² lm)
Oa.i
(og ie|d
Σ
max aEA//iEa
(14)
A
for OLS-UCB-C as T + oo. 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 gap-dependent bound does not incur any term in A Am unlike Perrault et al. (2020b); Degenne and Perchet (2016).
5.3 Regret of COS-V
For the analysis of our stochastic algorithm COS-V, we need to consider events related to the sampling distributions in addition the events Gj and C, introduced in the precedent section. For this purpose. we denote the event Hi defined as
He 1 vi [d], (mix+ (1 g1,5)fi,
(2,,)2/2 me.
(2,,)) ne.s
Tis.s S ge,8fe
(15)
The high-level idea of the event 74 is to ensure that the sampled rewards i4.s upper-bound the true mean (4; while being far for all the items a". Showing that the event H. indeed occurs with high-probability (Lemma in Appendix F) and setting the events & = {G, nc, n Hz). ). we can upper-bound the high-probability regret in the following proposition (proof is in Appendix F.2).
Proposition 4. Let 8 > O. Then COS-V yields
T-1
(9n = =0 -0(10g ( (og(T)))og(m)
d
m m.
Σ (=d(++1)
A
log(m)²
Σ
A As,min
Conclusion of the proof. Injecting results from Proposition 4 Shigh-probabillis regret) as well as Lemma 7, Proposition 1 and Proposition 2 (unfavorable event probability) into the template bound (13) yields
Rr] =
=0(
-( [og(T))) log(m)
Σ
m.
(16)
Ai,in
kE[d]
as T > oc. This provides the gap-dependent bound of Theorem 3. As it does not incur any term in A Amm in Wang and Chen (2018); Perrault al. (2020a), this result can be used to derive Ö ((VT) gap-free bound for a sampling-based combinatorial semi-bandit algorithm.
6 Concluding remarks
We propose and analyze two algorithms for combinatorial semi emnibbandiss. OLS-UCB-CC is a deterministic, oovariacee-ddapivv algorithm. Compared other existing approaches, our algorithm is typically less computationally demanding and yields the first Ö(VT) 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 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 Õ(vT) gap-free regret upper bound among sampling-base based approaches.

---

References
Abbasi- Abbasi-Yadkori, Y., Pál, D., and Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems.
Abeille, and Lazaric, A. (2017). Linear thompson sampling revisited. In Artificial Intelligence and Statistics, pages 176-184. PMLR.
Audibert, J.-Y., Munos, R., and Szepesvári, C. (2009). Expplration--exploitationnn tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 410(19):1866-1902
Auer, P., Cesa-Bianchi, N., and Fischer, P. (2002a). Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47:235-256.
Auer, P., Cesa- Desa-Bianchi, N., Freund, Y., and Schapire, R. E. (2002b). The nonstochastic multiarmed bandit problem. SIAM Journal on Computing. 32(1):48-77.
Brégère, M., Gaillard, P., Goude, Y., and Stoltz, G. (2019). Target tracking for contextual bandits: Application to demand side management. In International Conference Machine Learning.
Bubeck, S. and Cesa-Bianchi, N. (2012). Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122.
Chen, W., Wang, Y., and Yuan, Y. (2013). Combinatorial multi-armed bandit: General framework and applications. In International Conference on Machine Learning.
Combes, R., Talebi Mazrach Shahi, M. S., Proutiere, A., ct al. (2015). Combinatorial bandits revisited. Advances in Neural Information Processing Systems.
Cuvelier, T., Combes, R., and Gourdin, E. (2021). Statistically efficient, polynomial-timg -imeiiall-imeeeeee algo- rithms for combinatorial semi-bandits. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5(1):1-31.
Degenne, R. and Perchet, V. (2016). Combinatorial semi-bandit with known covariance. Advances in Neural Information Processing Systems.
Faury, L., Abeille, M., Calauzènes, C., and Fercoq, O. (2020). Improved optimistic algorithms for logistic bandits. International Conference on Machine Learning, pages 0052-3060. PMLR.
Filippi, S., Cappe, O., Garivier, A., and Szepesvári, C. (2010). Parametric bandits: The generalized linear case. Advances in Neural Information Processing Systems.
Guo, D., Ktena, S. I., Myana, P. K., Huszar, F., Shi, W., Tejani, A., Kneier, M., and Das, S. (2020). Deep Bayesian bandits: Exploring in online personalized recommendations. In Conference Recommender Systems.
Kveton, B., Wen, Z., Ashkan, A., and Szepesvári, C. (2015). Tight regret bounds for stochastic combinatorial bandis. In International Conference on Artificial Intelligence and Statistics.
Lattimore, T. and Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press.
Liu, X., Zuo, J., Wang. S., Joe- Wong, C., Lui, J., and Chen, W. (2022). Batch-size independent regret bounds for combinatorial semi-bandits with probabilistically triggered arms or independent arms. Advances in Neural Information Processing Systems.
Perrault, P.. Boursier, E., Valko, M., and Perchet, V. (2020a). Statistical efficiency of thompson sampling for combinatorial semi-bandite Advances in Neural Information Processing Systems, 33:5429-544 5440.
Perrault, P., Valko, M., and Perchet, V. (2020b). Covariance-adapting algorithm for semi-handits with application to sparse outcomes. In Conference on Learning Theory.
Rusmevichientong. and Tsitsiklis, N. (2010). Linearly parameterized bandits. Mathematics of Operations Research, 351
10

---

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.

---

Appendix
The Supplementary organized as follows:
Appendix A proves the lower bound from Theorem 2,
Appendix outlines proofs concerning the concentration of the average estimator (Proposi-
tions I)
Appendix presents those for the covariance estimator (Proposition 2),
Appendix D) establishes general propositions used to upper-bound the number of times each item chosen,
Appendix E and Appendix F detail proofs for OLS-UCB-C and COS-V, Appendix presents some experimental results.
A Proof of the lower bound (Theorem 2)
Theorem 2. Let d, m E N such that d/m 2 2 is an integer, T N", and E žm- a covariance matrix. Then, there exists stochastic combinatorial semi-bandit with d base items, and reward distribution with covariance matrix E on which for any policy n, the pseudo regret satisfies
1/2
R
T (E(d]
T
max ΣEnd
8
aEA,E
JEa
Proof. We follow the methodology of Auer et al. (2002b), modifying it to account for the different variances among actions.
Let m E N such that d/m 2 2 is an integer, T E N and a covariance matrix Σ > 0. We consider the structure where A = fai..... ad/mJ C {0, 1]ad contains d disjoint actions each having m base elements. We consider that for all E [d/m]. (ap)iE(d) = (1 (p 1)m < i pm) pm Let be policy. As all the actions are disjoints, we can reduce ourselves d/m actions, where for all p E [d/m] the variance of the p-th action is (ap, Ep)-
multi-armed bandit with
Let E' E Ma/m((R) be the diagonal matrix where for all p [d/m], Ey a Eap Let 0, and
d/m
A 201
E min
k=
(17)
T
where E'in minpe(d/m E p.pp"
We denote Go NO, E') a (d/m) dd/mm-dimeesioonll centered Gaussian distribution with covariance matrix E'. Letp E [d/m], we consider the mean vector ((() E Rd//m having coordinate everywhere and A at coordinate p. for all i E [d/m]. (!!") = Alfi = p}. We introduce the Gaussian reward distributions G, (1(()) E') and denote Tp Σt 1l [A = p). Then, using policy n, and considering the reward distributions Gp and Go. the average number of times action p has been chosen satisfies
G (Tp) - E. [Tp] STTV Go)
Go), (T, Gp) S / Go), (T, (T.
(18)
where TV denotes the total variation distance, KL denotes the the last inequality uses Pinsker's 's inequality. Then, using the divergence decomposition between bandits (Lemma 15.1 in Lattimore and Szepesvári, 2020).
divergence and
d/m.
KL((T, Go), (T,, Gp))
Σ 1=1
Ex
[ix KL (L. E')
d/m
(p)
(1k
Ex Go
[Tx]
2
2Σ
12

---

Reinjecting this expression into Eq. (18), we get
d/m
(p)2
E E,,G, S R. [Tp)
T
P
ET
[Tk]
2
Σ
R,k
T
= = 2
A [Tp
2'ppp
d/m
E Go [Tp)
ER, + c
reinjecting Eq. (17)
Ey P.P
d/m
S BBn.colypltc G. [Tp)
Σ
Now, summing over the actions p.
d/m
d/m
d/m
d/m
B B Gr [Tpl S Σ
GN
[Tp + c
T
Σ
E Tp
k
7m
pml
k=
pml
d/m
d/m
< T +
T
E
k.k
Br. [Tp]
+-
Cauchy-Schwarz
k=1
d/m
< T +
cT
Σ
(19)
k,
We denote Ry
the average cumulative regret incurred with the reward distribution Gp, then
d/m
d/m
RP
E EGG (Tp))
p=1
p=1
Edem ==
d/m
E
d T
d/m
2c1
Σ E, (T2) p=1
reinjecting Eq. (17)
min
T
m
Ek,
d/m
2
2c
===
T
cl
Σ k,
from Eq. (19)
min
T
m1
A
d/m
d/m
20
min
m
E
m
d
c
d/m
Σ Eken
d/m
> 20
yy
min
m
T
E
k,
(1
m
d
C
Enmi
A
Taking == =
(1
d)
d/
d/m
2
Y k.
1 - d
m
k=1
d/m
1 d
T' Σ
Exe + as m/d / < 1/2.
8 m
A=1
13

---

Therefore, there exists at least one instance p* E [d/m] such that
d/m
T
T
k
k=1
Now, decomposing
d/m
d/m
Σ
Σ
Σ iEak fEaz
=
Enn
E
Σ Eig
k
max aEA,ER jEa
k=1
k=1
iEId
we get
R4P
T Σ
Σ Ein
max
aEA,iEa iE|d]
jEa
B
Concentration of the average rewards estimations (Proposition 1)
Proposition Let 2 d(d + 1)/2 and > Then, P(gş) s 6/(tlo((t)).
Proof. Let 2 d(d+ + 1)/2 and 5 > 0.
We have
f1,8 = 6 (lg((1/)) + 6 (log(() + (d + 2) log(log(1))) + 3d (2)g((2) + log(1 + c)
(log())2
log(1 + (e- 1>) ) + (d + 3d + (e 1))
log(t)
d
= -6log
8
Covering argument (Peeling trick). The peeling trick consists separating the space trajectories up to round t into an exponentially large number of parts, each having an exponentially small probability.
Formally, let < E < 1. For each E Nd we associate the set
(1 + e)pct1). Dp for ERR s.t. vi [d], (1 + c) S
(20)
As an abuse of notation, we denote by (t E Dp) the event (mm..(..)) + 1)se E &D))
Setting Pt.
log(t) [og[]+e]
define for each p E [Pt,e]
Ñ, diag ((1 + ((:+) (E(L)
E Ma(R),
Zi. V, N,dx I
(21)
In particular, under the event (t D,), N, 1 (1+
Using this covering, we decompose
P())) P
Σ da 17
frs
2.
(115.1lz. >18 (
Σ
IP
> (111ll2z) 118) >(s))((EE))
Σ IP
JM
We now apply the following Lemmas.
14

---

Lemma 1. Lert 2 d(d 1)/2, 0 <<<L, [Pt,e] and ó > 0. Then,
Norm, Norme.p
P
|| 2
6log
+ +6lo(1100) 5o,
(22)
where
Normp
SE
JXERS
1f
All
-
2)
11
exp(-11A11 Jdd,
/
1/2 Al| |
11 1spl-11Al1 Jdd.
Norm
AERU
2
Lemma 2. Let 2 d(d 1)/2, 0 <E< Normp Normp.
and p [Pt,e] Then,
1
(eep(Zr.))
log
dloo(() + log dct ZZo.p)
(23)
Moreover, under event (1 Dp).
Normp
log
S dllog(2) + z log (2 + +).
(24)
Normp.
In our case, setting = 1, they yield
P(G)) 2 Σ IP (1sslllzz > 6 6log
flog(t)² log(t)*) + 6d + 3d e) )}
n (t E(t))
Σ P p
((1ssilen.
> 6log (log(()2
log(t)) + 6
Norme.p }
Normp
n E(tED))
+ Lemma 2
llg(())
Norm,
PP
|Sellz.
> Glog
log(1)a + --logg
5
Norme
pe.
1
Lemma
(lo((1)2 log(t)d
8 log(t)² log(t)d log(t)d
flog(t)2
B.1 Proof of Lemma
Lemma 1. Let 2 d(d 1)/2, <<<< [Ptcc] and 8 > 0. Then,
Normp + 6log(1/6) 58, Norme,
|| 1111l 6log
(22)
where
Normp = / if
1/12//0 1/2 A||
1
exp( exp(-11A11 }dd,
2
1/Z1//2 All < } exp - -111 Jed.
Norm JAER
15

---

Proof. We adapt the proof' from Faury et al. (2020), which adapts Abbasi- Yadkori et al. (2011) itself. Let t 2 d(d + 1)/2, 0 < 1, p [Pt,,] 14 and O.
Let Rd such that |
1 l|
and [t]. We denote F/ o(11, Vi.... ...... 1-1, V.-1, At).
Then, [ATAA, 7all & 1/2 and
E
exp AATAA - X dT A.A, 2)
F 31
which yields that (Me(()) KEN = ((xxp SA - - KEN
is a F -upermartingale.
Let p [Pr,e] consider the density 9p of d-dimensional Gaussian with covariance matrix
(N,dx + 111 Z truncated in the ellipsoid {x IR, || x1 s }
(p(x) 1 1 Ø1 S 2)
||0|| 1
exp
Normp
where Norm, is the normalisation constant.
We integrate (Ma(A))
for x ~ 9ps and define (Mp.))
KEN
0.p 1.
All S 1}
Mp.
Ms(A)d
exp
(x 11l1 )ox
JARR
AERR
Normp
which is still a supermartingale.
12, 11/211111 (S (AT - -1A111 Then Let Xi.p E earg max
exp(Ar] 1 Sz - || 22.F)
Mp.
| exp
(A xi.p) St - 11 + +11iippl Zn. dA
Normp
exp(Ai S5 - || (E.NN
exp A A -1A11E. - 21 ZZ Ni.
dl
Normp
11 X 21 115
exp(A1,] Ss - 11 (I.0)
A - | - 22 Zk.p dd
exp
Normp
exp(Ai, Ss - 111i,p11.... (Z..))
AT 22z.piip) |11112 dA
exp
Norm,
exp(X Ss - ||2i,p11 2k.P! 11.
Norma,
Norm,
1 11112.221 1
exp (T - -ZZa,Ai..) -1 dd,
J
Normar
where we can recognize Ik.p the density of d-dimensional Gaussian with covariance matrix 17-1 truncated the ellipsoid for E RRd, / m||
2 k.p
S }
Ik.p (x) = 1 1 0. 201 S }
exp - -||20| -11x(122..)))
Norma.
with Norma the normalisation constant.
16

---

Besides, Jensen's 's inequality yields
1 Z. 2.
$ 2)
exp A (T(S.. -T -2ZeDdip) -1212 dd
AERO
Normer
2 ( ad
(k.p() exp
2d
(/ee (A) (Sx --Z nZ dd
2 exp
T 221x.p1i.)) (Sh+ ( 12--2 -Sa-2ZZ
/ [t.(A))dd BBd
exp
Therefore, for all & E N
Norm exp(>i,T5 - 11 1l
Mn
Norm,
Markov's 's inequality yields
1) 2 Mp. 2 ))
Norms exp(>i, - 11 12 2
2
Normp
Normp
Xi Ss - || 2 log
log(11 log(1/6)
Norm
Taking k in particular gives
Normp Norm
8 カラ P
max
A ATS,
1212,,, log
+ log(L/8)
1/2
S
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, 12, 2,
Instead, we introduce
7 St Ne. 4 S 2
for which
|| 15,11 S li
de.pll
S 1
1
//.22 L.p
1/2 1//2
1/221
0.p
1
4
Then
1
Normp ) + log(1/6) Norm
8 2 P
S 1l 1
St z
2 log
4
16
16
Normp Norm
16 + log(1/6)
IP
|| 1,.t 2
log
Norm, Norme,
IP
||S
l|sellz..
2 6log
+ =6lo((108)
17

---

B.2 Proof of Lemma 2
Lemma 2. Let t 2 d(d + 1)/2, 0 < < 1 and [Prc]]. Then,
Normp
/dt((z.p)
log
= dlog(2) + log
(23)
Normp.
del(Zo (Z,
Moreover, under event (t E pp).
Normp Normp.
log
< dllog(2)
dl + 6).
(24)
Proof. Let t 2 d(d + 1)/2. <E< 1 and [Pr,e (2020) yields
Then, following steps from Faury et al.
- JXERM 1
11
Norm, =
2 -xp1-1AA12 Add
1
1 1|1211 - 2) exp(-11l11jdx,
(det(Zo.p)
JXERS
and
/ /XERM K(1ZZBPA11
1/2 S 11 expl 1111-11///2,, }dd
Norme
4
1 1 Zn 1/2 S 11
exp(-11A/9jda.
Vet((zr,))
AERA
Noting that 1 Z 1/2 || S 1, we deduce
1
/ 1 1INI 2) expl-11113/a)
Normo
/det(Z
Therefore,
SE 1{11A S 1/2 } exp(-1111131
Normp
det det(Ze.p) det det(Zo.p)
Norm
Sgg. 1 ||II| S 1 exp(-1Al13jaX
We treat the integrals
Sas (1fINII }} + +1{+ < || S $1) exp(-
Ja [AAI S } expl-11113)ax
Sa {All < } exp(-11A[13)4
fee 1 {>1l S 1 exp(-11112)a
11 Jg0 11 |^ 1 1 exp(-1121/J00
Ja. 1|1121 < 1}
< ++ exp( (x16-1/16) S { < MAA S JaA
exp(-1/16) Jg I Jar
18

---

Thus
Normp Norme,
dct (t.p)
log
I dlog(2) + log
2
det(Zo.p)
= =dogg(2)
log
det (1 Zo.p 1/2 Zu 1/2) )
2
(1,() Ds,
I <dlog(2) log
II .E[d]
1
(1 + c) Di, + |B]
S <dlog(2) log
II sE(d]
[+ (e,(
(1 + (1+t)pt)
In particular under event (t E Pp).
Normp
d S dlog(() log(2 + +c)
log
Norm
C Concentration of the covariances estimations (Proposition 2)
Proposition 2. Lett 2 d(d + 1)/2 and > 0. Then, P(C)) < (t
is a direct application of the following proposition: Proposition 5. Let 5 E (0, 1). Then with probability - 8, for all t 2 d(d + 1)/2 and (i.j) E [d] "reachable".
B,By
(
5/u,
n2 (1,(55)
1
(xe(11)) - Eigls
+
4 (Mr((ts))
where he.8 = (1+ + 2og (1/6) + 2ogg(dd + 1)) + log(1 + +1)
Proof. Let 8 > 0, 1 2 d(d + A)/2. We remind
C. = (V(i,) E [d] "reachable", Σ.,(,.) 2 Eig}
Let (i,j) E [d]2 "reachable". Then
{((())) St,(t.)) Pe,
1
Σ An.
-11 Σ
i
Ae, v.1
1 (1 Σ
EAndYa.))
(1,(
nt,i s=1
And,
X(,(15) - Ei,1 = ne,()s)) ==1
A A,, - SSy
( Σ AoiYoit
Σ AosYos) Hattes
Rt, s=1
Res m=1
Yo.ioss As.
- St,)
-((11
As.s
Yo.t - mi]
(111
Σ
As.s Yos -111
(e,(1.)
n4,t a=1
new s=1
==1
+ Mi
1
Σ
Assi
Yo.s mi) ui
1 Σ
Abis Yo.s Mb
nh.1 s=1
nn. a=1
19

---

A triangle inequality yields
(Ra,0 - E.yl =
Σ
Agidos
Yeikas - S
+
Σ
Ao.
Ye, - -Hi
- - Aa.
Yas H1
n1,i
new
s=1
B + 2
As, Yes - -Ha] Σ
+
B:
Asd
Yes - Hs)
2
We make repeated use of the following Lemma
Lemma 3. Lef (H4)EeN- be a filtration, (Ut)eN- be Hy adapted martingales bounded by C E R with E[U]] O. and (1(V))eeN+ be predictable process and >> O.
Then with probability at least 1 8, for all t
E LIV.J 1 + 1+
C
P
2 2log(1/8) + log(1 +
((v3))
56.
((V)
1++ 1(V))
s=1
Therefore, with probability at least 1 5/2, for all (i,5) and
Σ Ans YarYas Stis 5
1
Agjidas YouYos - SSus +
B,B,
(i.(). a=1
(t,(i.))
+1
4(mz,(is)) +
s=1
B,B,
2 2log (log(1/6)+ +200)+22lgg 2log(d(d++ log(1 + t)
(oL +
B,B,
B,B,
S 4 (L
2 1/0) + 2 (og(((d + 1)) + log(1 + t)
BB
4m,,(
With probability at least 1 - 5/22, for all and 1,
B.
Ag,i
Ya,
14/
S
Ag,
Ys.i Mi
+
14,1 +
2n,,(i,))
sm1
B
B.
S
2 log((15) log(22) + log(1 + t) + 2n4
2 (e,,(i,))
Therefore, reinjecting those expressions yields that with probability least 1- 8. for all (i.j) and B,B;
B,B,
[&a, - Eisl < Amme,(t.))
log log(d(d + log(1 + Ami,(1.))
(2 (2g( + log(1 +t)
B,B₁
4 (M),(..))
(r.)
BBB,
1
2 log(1 /8) + (2g)(d)) + log(1 +
4
B,B,
//logg1/0) 2log(2d) log(1 + t)
4
(4,,8..)
B,B,
BBB;
2 log(1/)) 2 log log(d((++1))) log((++))
4 (t,(f.))
4n4,(.9)
(2 (2log (1/8(11)) 2 (2d) log(1 + +t)
B,B,
4 ATT
4T4,(E.0)
B,B
V 2 2log(110)) + 2 log(2d) + log(1 + +t.
2
20

---

To simplify this expression, using (n,(i)) & min(fr.(..)) R,,G))) and (e,(1.) & (e..(..) yields
BB
1
Exsl
/2log(1/6) 2 1)) log(1 + +t)
4
((,(1)))
B,Bj 1 (1+2)og(1/))++ (10
+
1)) + log + +1))
4 ((,11)))
B, 1
+ 4
n (,(t5)
Denoting hes5 (1+ 2 llg((1/)) 2 log (1 log(t))d(( + 1)) + log(1 1)) 1/2
we have with
probability least 1 lod+)))log(1))
28
B₁
5
h7 +
Σi,l S
(e,((ss)
(1,655)
union bound yields the desired results.
C.1 Proof for Lemma 3
Lemma Let (He LENN be a filtration, (Ut)teN be an Hi adapted martingales bounded by C' E R; with E[U1] O. and (1(Vi))ee> be predictable process and >> 0.
Then with probability at least 8, for all t
Σ LV..U
C
P
2log(1/6) log(1 Σ ((v.)) 26.
1 1 1 1(V)
V+ 1(V))
Proof.
Let
Then U, C sub-Gaussial and for all A
X²C² 11vi3
E
exp
AL[VIUU
H4 5
2
Then (Wr(A))EEN- = exp(A Σ (V.JU.
x²C²
E
((v+))
is a supermatringale.
EEN- This yield
We the Method of Mixtures by integrating for NN(0,1004
f
C
(-
X²C²
2 Wi(A)dA
exp
AER 2T
C.
/ exp
t A Σ
X²O2 1VVJU.
(1+ Σ 1(v+)) dA
22T AER
s=1
C
(Ein 1(V.JU.)
exp
2TT
20 + Eim 1(Va))
AER
2 (A-
Σ._ LVV.UU
020 + (1())) da
C2 + E.= ((V)))
exp ( (E 1(V.HU.)
1
20 + Ei= 1(v.))
V VI+ 1(V3)
$1.
Therefore,
> 2 LsV.JU,
C
P
21og(1/8) + log(1 + Σ ((v+)) 56.
+ Σm= 11V.}
V++E,1 1(V.)
21

---

Using the stopping time construction from Abbasi-Yadkori et al. (2011) yields the property for all
D Behaviour in the high-probability events (Section 5)
The following proposition states that under some assumptions the sequence of events (Er), the regret can be bounded by problem-dependent quantities (including Σ. T, or d). They are not all explicitly stated in Proposition 6 to make adaptive to both algorithms but are hidden in the constants.
Proposition Let r E N. e E (1, (oc+" Let (Ex) (Ex) 1)/2 be a sequence of events such that for all t 2 d(d + 1)/2, under Es.
A A++1
Ceeaa (1,(5
Σ
C. ni ((i5)EAess
Σ
(25)
SEAl.
mE(r)
where C and (Cr)s are depending on A4t1 and so that, for all E A, Ca, I 2m Let c E R2 and (Ca)sE(r) E (RR.)" be positive constants such that 1/c+ ΣsE|r) 1/c, = 1.
positive constants. CA is a positive constant
Then,
T
A {
(=d(d+1)/2
Ca.i
I 96c log(m)²
max aEA/iEa
A₂
iE(d
e, 23316 ca C. logg))))))) 1/2
A max
Σ
md?
1 + log
A Amin
{11 < e, < <2]60.30 (c.00,
(000000///((0C,,,,,, log(m)
I/ea
dm
A
1-2/ex
1/e, log(m)) +1 < es 600.30 ( (c.CC.log(())
C. 2/c2 A max
(26)
Cg
where (or))een (Bx KENN and ko E No are defined in Appendix D.
Proof. The proof classical and involves a decomposition Degenne and Perchet (2016); Perrault et al. (2020b)). By considering each of the sub-sum in Eq. (25) and designing sets of event that can happen only finite number of times.
events &, (see Kveton al. (2015);
We introduce two sequences (ax) keN) and (3*)keN- both begin at 1 and strictly decrease to 0 (see Appendix D.I for their definitions). These sequences are introduced to be able consider the different terms of Eq. (25) separately.
Let (ca) (Rt)" such that Ese(r] 1/c, =
Let t 2 d(d 1)/2, & E N We define the set
S₁ = {i Art1, n4,(1.)) S cimak
C
C2
1
(27)
A2 A
E
and the event
Ar.
Σ TES.
Ei CAuLE
2 3Km; W<ck
< BBm)
(28)
CA
NES)
A notable difference from previous approaches is the use of Ei,/Ca, i in A instead of set cardinals.
This enables the explicit appearance of the Ca, coefficients, which will involve the o² for the application of this proposition to our algorithms.
22

---

For s E [r], we define
C S7 = { (1.3) E A.41, (lwss S ccm²an
0o}
(29)
A Act1
and the events
A = {1staa 2 Bem? AI < ( < Bmm²]
(30)
The following Lemma, proven Appendix D.2, decomposes (&g (2)))2((+11)2 using these events.
Lemma 4. Let's consider the assumptions of Proposition Let A and (Nelr) be the events defined in Eg. (28) and Eq. (30). Let ho E N' such that O < mB3Ro < 2m and i 2 d(d + 1)/2.
kp
1(81 - Σ (ALK) + ΣΣ [Aj.a
km
Using it, we decompose
ko
ko
A 118)) <
Σ
Σ
A [ +
1 [Aii)]
(=d(411/2
b=d(d+ 1)/2
k=1
k=1
T-1
T-1
Ro
Σ
A
1(
+
A
1
1=d2+11)/2
1=1
8=1
(=d(1+1)/2
(31)
We begin with the first term of Eq. (31). Lett 2 d(d + 1)/2, and & E [Ro]. Then,
Σ
Eds
2 Bam;
v< h Σ
Egs
< B1
Σ
Eis
CA
CA
3am
CA
SESt
iESt,
iE
Therefore,
1(Ar,)
1
Σ
Eis
BAAL (i E
3ym CAmas veld
(32)
Summing over l and k; and including the gaps yields
A Ac+1
1
(33)
1)d(211)/2
k=
T
Eis 1 1 n E Sunl} + by Eq. (32)
A Asta
3pm
CA
(=di++1)/2
Am/l
seld
A
1 Mi St,e)
Bem CA
iE(d
t=d(d+1] 11/2d11/////
DAIL
C
Σ
(e(())) S cimay
by Eq. (27)
3Rm
CAeLi
Dal1l CA
E
(E(d
ddd++1)/2
(34)
Let [d], we consider all the actions associated to it. Let di No the number of actions associated to item i. Let l [q.) we denote et E A the (-th action associated item sorted by decreasing with
An C.o. by convention. Then
23

---

C
1 (e(())) S cimax
d(2+1)/2 CAeLIi
)ALLL
Ed,t
ne,(EN)) S cymak
Ac+1 = 6
Cef.
Ei
Eii (e,((dd) Camayl
A++1 =
Cafe
Σn
< (ti()))))
A+t1 = E +
decomposing the event
Café
c2may C
of
Σdj
A
D Cof
< (tid
A+11 = =c o t as
S
amaa C
Cet.
4
T
1
Σ s
1
(1,(1,))
As+1 = o
2
c C
p=1
T-1
Egs
A+41 o t we extend the sum over /
(16.(665))
Cpmara
A,"
1=0
1=1
41
(e,(1,)) C.mar.
we simplify the inner sum i E A4t1
A
1=0
9
A
Cofie Aep
cmmaa
Cog-1 /
ammaCC Σi,i
1)
the event can only happen a given nbr. of times
Cefii
A Ap-1
Cofi,
2
Camax
A
4-
Cop
"1mmaCC Ej.i
( Cog
Aggii Capte
)
<-
summation by parts
Σi,
p=1
C C Σii
Coffi
4-1
Cafa
2
A
Capts, )) + everything is positive
Cepea
c
C
Coffa Degi
dx
Ei,
x²
C2
C2
CimaaC
c
c
c
Σip
Aeg.
A
De!
20mman C
Capus
Agt
Ca. Aa
max AEA/EEE
(35)
24

---

Reinjecting Eq. (35) into Eq. (34) yields
T-1
Σ
DAT
kg
1
Σ
1
20mmCak Σid
max nEA/iEn Da
Ca.
3mm
t=d(d+1)/2
k=1
iE|d]
k=1
No
OCk
Ca. Dn
2cy
max rEA/iEa
BR
k=1
iE(d
Ca.$
= 96c
(m))
max aEA/iEa
(36)
Aa
sE|d]
We treat the r other terms in a similar way. Let 8 E [r). L 2 d(d + 1)/2, and A: E [ko]]
{ 15 2 Bem?
vl k < 3mm² [ 3Rm2 1s 2 1
Therefore,
11 [ S
Σ
IfAix n ((1,5) E eS }
BRm2
(37)
Summing over t and ls yields
AL41
tddd+133/2
T-1
kg
Σ
iAA n (((.d) E stat) + by Eq. (37)
Ac41
3mm (b.))E/d1
(=d(++1)/2
T-1
kg
Σ
Annn (((15) E si
3em
[d)
t-
d(d+ k2 k=1
kp
T-1
=
3
Σ
A I misess) S m
A 2/c,
+
by Eq. (29)
( [d]
d=(d+1)//2
At+1
(38)
Let (i, E [d]2, we consider all the actions which are associated to it. Let ((,))) E No be the number of actions associated to the tuple (i, Let I E [qc.))l this time, we denote ((.) E A the I-th action 0 by convention. Then, 3
associated to tuple (i.j), sorted by decreasing A "aan"
with
Σ
A
I me((. S
A 2/e, Act1
(2/d21)//2
T-1 ((aa))
A411 dasl }
1
A ((s))
T(,(i.) S m/2 (c,a
/0.
A 2/e,
Act1
T-1 ((..))
Act1 = dnol }
ne(lis) 2/0 2/00 1/ (c, 1/c0
1
(w))
A 2/e,,
((n))
2/00 < "m -2/00mm22///// (coOs.C.) 1/ea
Act1 = -(a)) /
2/err
A 2/ee
pml
((f)
p-1
p
(1.))
ΣΣ
1
< (t((i.) 2/e0 2/00 ( (c
A = =d(a)
2/ez
2/0x %(1))
1=p
p-1
(G
25

---

((3
T -1
1
1
< RL 2/0, (C,)CCC,) -1/e0 2
ie Act1
2/ea
2/ex
p=1
2=0
ep-1
(2.5)
((2))
((+,))
2// (caax
m2/0/ (c.a)CC,) 1)
A 2/e, ((.)
2/e,
p=1
de
655)
m 2/ (c,0CCC))
A ((6)) (5.5)
+
m
2/ (caa)CC.)
Asfan
A ept)
A 2/ex
2/e. oe
9(5))
(6.2)
((s -1
1-2/ex
-2/e,
< S (c.a
A 9(sa)) ((.d)
A
- A Aerr)
(((i))
p=1
(c.a,CCC)
(A 9(15)) (1.2)
1-2/ca
(
-2f0 dx
9(55)) (6.5))
((i5))
If C. 2, then
Σ
A 1 me,(is)) m/? (c.a
A
2/0, Ari
1ddd+1))/2
Auten x 1 dx
< <m(GaaCC,))11 1+
9(sr))
((i))
Amax
I mm(c,auC..)11
1
Amin
Reinjecting this expression into yields Eq, (38), for e, =2
A max
Σ
A
Σ
3am2 m m(c.anCC.))
1 log
Amin
1)/2
((d))(d) (e(Ho)
df m
1/2
(c.CC,))/2
1 log
max Amin
C
BR
< 346 (.CCC,
1/2 ma?
1 log
A Amax
(39)
Amin
Else, for 1 < <e. < 2. then
T-1 Σ
A 1 { paltes) S m/ (c.a
2/e. Act1
d=d+11)//
S 2/2
(A
1-2/0s
(1.)) x 22ee0 dx
9(w))
(Hi))
=/ (cG
(A
9(1)) ((i))
1-2/0s
C2
A 1-2/ee
A 1-2/ee
96.5)
(1.3)
5m²/ 2/. (c.a
(A ( ((i))
(A
1-2/es
Es
A1-2/e.
d)a)
-A1
1-2/es
9(1.5)
((.))
5 3m 2/0, (c,
1-2/e,
min
26

---

This yield
ko
Σ
Ac
Σ
[(Ai,)) v E Σ
1
3m 3m2/ex (c,ax,C,)
A min
1-2/ea
3Rm²
1dd++1))/2
k=1
(1j) kelkal
1/e,
3Cc,CC,)) d
1-2/ee Pm2/e.-2
12112//e
O
Bk
kE(Ro]
< 188.30t/ee (,,00///(c.CC,,og///// log(m))
1/e,
d2m2/e
1-2/e,
(40)
min
Finally, for es 2,
T-1
if
Σ DAi I mahce S (caa
1
2/e,
(=d(+1))/2
Act1
< mm2ee (caa)CC,)//e
(AA2)))
1-2/ea
(1,9)
2/e. -2/e dx
A 9(3))
((i3))
= =m? 2/2 (c.
9(n))) (A
1/2/ax
Cs
A 1-2/ce,
A
1-2/e,
(i.d)
Cx
((()))
((.))
%6.3
S m 2/cx (C.,,,C
Ea 2
Amax
A
1-2/ea
and
T-1 Σ
A A
Σ
3em? m
2fer
(c.ax
es
(Amax)
1-2/e.
C2 2
(dd+11)/2
1=1
(1J))]d ke[ko]
Ok 1/e,
Ps = (c,CC,)
e. dmm//e
1-2/ea 2/ea/-222
-21-2//e max
Bk
KE [kl
s 63.30t/e, (c,CC, log(m)
1/0,
es
dm=
m22//e 2/e A 21-2/e.
(41)
6g -
max
All in all, we reinject Eq. (36), Eq. (39), Eq. (40) and Eq. (41) into Eq. (31), yielding
Σ DAn 1{8)
1/d+111//2
T-1
A A
Σ A=
1 A(
+ Σ
Σ
A Arei
Σ k=
1(Ai
d=dd+11//
s=1 (=d(d+11//
Ca.i) aEA/EEa
< 96cz CeccC'Clggge Clo((m)2
2
max
Da
iE/d
1/2 Σ e, =2]3300 Ba0a6c,,CC, C, log(m)) mil²
A max 1 1
Amiu
+1f1 cs < <3] (s,C,, log(m)
1/ca d m/e A 112//e
+ +1f2 e, e. 633.00 (,CCCllo(m))
1/0,
C.
d/ Al-2/es
(42)
e, -
27

---

D.1 Definition of the sequences (ax) and (8k)
Let 1/5, x > We define Bu 0g 1. For 1, we define
B = g%
= =r
(43)
Let's first look for an adequate ki for Lemma 4, taking 1 S ko 2 low' 22m sufficient to have 0 < mm
11 S (2 (lggmm) + +3)
1og(1/3)
<
2m This choice particularly yields
Kg
3k-
BR
Bko
kg 11
3
+
+
Ok
Okko
3
T
k=1
1) -
3
1
(Aio
+
B
3
x
(44)
1
4ko
+
x
for x 4kg + 2.
Besides,
ko
ak
(4hg + 2)ko S 16log(m)2 + 52 log(m) + + s 48 18))
(45)
3x
as 2 5. Let c E R, 1. Then
l/c
ag
(4ko 2)1/0
(B1/0-14
No
s (8log(m) + 1/ 2/c
c-1
k
k=1
kn
< 30 (og(m) 1/0
5
k=1
5
30 log(m)
1/0
5
5 - 1
3/ log(m) 300
1/c
(5 -1)
30 logm")
1/c
[1og(3)
2 (2g))
22) -1)
exp
4
log(5)
= 30 log(m))
1/e
50m²-1 [
4
< 63m² (30 lc)
< 63 log(m))/e.
D.2 Proof of Lemma
Lemma 4. Let's consider the assumptions of Proposition 6. Let Ai, and (Ai,))ae(r) be the events defined in Eq. (28) and Eq. (30). Let Kn E NO such that 0 < m.k < 2m and 2 d(d + 1)/2.
kn
1 18&1 < Σ 1(
1AA.
k=1
28

---

Proof. Let's consider the assumptions of 6, AL, and (A(, be the events defined in Eq. (28) and Eq. (30). Let Kg N such that 0 < mšk
I and z d(d + 1)/2.
2m
first prove that the events for k 2 Ko cannot happen. Let 2 kip
Eii
A
Σ
3km; v<k. Σ
Bem
CAs1I
ieSt,
As 3um
<
m
Eig and (5) is a decreasing sequence of sets, Eig 3k. m imply Sc = and Eiese, Cail1 = < 8ym. Therefore, AL,
ming,a Co.
2m
EiEs. CALlaif
cannot happen and denote
Enit 2 Bam; v Σ
Eg CAsarie
A. U AI.
U
ALk
U kE|Kol
Σ
<
Bem
Cdetai
121
kE[Ka]
kESt.
iES
Likewise, for ls > ki and [r].
AiA { |18t 2 Bum²; VI MKk, < Bim²
As 3ko m < 1/2 < and (Si decreasing sequence of sets, then k < Bko m2 imply
S1 = 0 and |S = 0 < 3gm Therefore, Af, cannot happen and we denote
Ai
U Ai. U
Aii U
| 2 Bam? 1I k. 1i < 3cm²
kE(ko]
ke[Nol
The idea is now to prove that
Ao U U
Ai
Ag
A
C Ee.
8=1
We begin by considering (A))
(A1) = no (A)r,))
=nho
{
Ei,
Bum
Eis CACAIA
2 Bim)
CALLEA
iES
1=1
iESt,
Eis
=n
Σ
< 3km
(46)
CAeaad
iES),
Then, under (A denoting Si,0 Act1, St,bo and the sets Se, are decreasing with respect to k
CA
CA
(1,(5,))
iESt /S1
Ei,
Σ
CA 3maz
by Eq. (27)
C2
Ch
k= iES)
1
2
Ar-
Σ
Σi,
cmC
Olk
CALAIA
k=
2 A
Σ
Dis
Σ
Σii CALpA
mmC
Olk
CAean
km
NES!
iES)
29

---

A
Ac-1
Eit
E
Eij CA
qmC
ak+1
CAsaii
k=0
iES L.k
1E 1E81,811
A
Eii
No-1
amC
01
CACHLA
ak+1
Okk
C
iES,
k=1
iES
A Ac-1
ha-1
1
aik ) t
1
mΩk
Suu A4t1 and Eq. (46)
amC
α1
ax+1
k= l
A Ac-1
ko
Bk
Ako-1
+
G
O
OKko
kml
2
A111
$
t- by Eq. (44)
(47)
C
Likewise for 8 E [r].
|st < Bam? }.
(Ag) nk
(48)
Denoting Si,0 Ast1 x A4t1, as ki,ko = 0,
C. (((5))
C2
(65)
1=
(1
Aa4t 1
C. c2m2ax
+-
by Eq. (29)
C C2
C
ak
A2 A111
1o-1
(Se, - -1S,,
c.m²C
ak+1
k=0
A3 2
St.ol
kn-1
1
1
|S
c.m²C
a1
at+1
ak
k=
kg
1
Onk )
1
c.m²C
m
+
BRm
2
-
by Eq. (48)
ax+1
k=1
An-1
Aeti
3
Bx
B
+
C²C
ak
Okko
1=
1 A Art1
<
f-
by Eq. (44)
(49)
02
C
Therefore, under AC nm (Ai)
summing Eq. (47) and Eq. (49)
Σ
CAeHIA (1((d))
Σ
Σ
C.
1
A
e (((5)
Cs
BEAl+1
sE|r]
(KJ))Am
<E[r]
A
C
30

---

which contradict Eq. (25) and thus imply &, By contraposition, we have proved that & imply A. AU (Af). Therefore,
1 1 S (
[A
1=1
s
E Details for OLS-UCB-C (Section 5.2)
E.1 Proof of Proposition
Proposition
Let 8 0. Then, OLS-UCB-C yields
=o
( [1og(7)2 log(m)²
T.. aEA/iEa Do
Σ
AAL,,
max
(=d(d+1)/2
as T + where oā, EjEa
Proof. The objective is Proposition 6.
Proposition Let r E N, e too)" Let (Ei (E)) be a sequence of events such that for all 2 ((d++))/)))))))) under &
A2 A41
CAuai
C. Ti
Σ BEA,12
Σ
Σ
(25)
(1,(55)
ni
eE(rl ((.f)EEA+
where and (Ca)se(r) are problem-depender positive constants. CA is a positive constant depending on A441 and so that, for all A, Ca. S 2m be positive constants such that 1/c+ ExEir 1/e, =
Let E 14 and (cx)sE(r) E (RR))
Then,
Σ
A 1{8}
1m/(2+1)/2
Ca.
96c C Clo((m)
max aEA/iEa Ao
%Eld]
Σ
1 1f0s = =2] ca Ca log(m))
1/2
mdd
1 + log
A max
Amin
1 e, < 20.30 /ro (c,CC, log(m)))mmm)
1/0. dm
1-2/ex
Amin
+1f2 e. 60..00/e (CCCC,log(m))
l/c.
C.
d
2/e, 1122/e0
(26)
C,
where (ax)kEN.. (Bx)ReN= and kn E No are defined in Appendix D.I.
We need to check that its hypotheses are satisfied. Let l 2 d(d + 1)/2 and 8 > 0, then we have the Lemma.
Lemma 5. Let > 0 and t 2 1 Then under (G. i CC). OLS-UCB-C satisfies
462 4
(4d + h2 11,
5/ BB
|B
Σ
Σ
(1,(5.5)
n (((e))
3/2
sEAlt1
(1.))A4H1
(1
(K))
where 32 J
2
EjEAA EE,, (Ei,)+ 20 A
31

---

Therefore, we can choose = e (2, 3/2, 3) and (E₂) (Ge nC). Taking (4, 14,4,4, 4, and identifying the rest of the coefficients yields that ULS-UCB-- satisfies
A ((
(=d(d41)/2
σ²
$ 384 log(m)²
a. aEA/iia
max
Au
vE(d]
Amax Amin
+ 692]| fr. (4d + nr,,6) 1/2 log(m))
1 + log
+1460| /// /4/3 Ri, log(m) (//3mm2233/) d² A
1/3
296]| B| 2// I7.5 log(m)) 1/3 m2 2/3 A//3 1/3
max
As
f1. = 6 log(1/6) + 6 [log(() + + 2) log(lo8(())) + 3d (2log(2) +3d())+3(22) +
loog(1 + e)).
1/2
b1.5 1 2 (ogg(1/0))))) (1/6) + + 2og (oog(())d(( + 1)) + log(1 + 1)
deduce
A... 199nC) = o [1og(T) log(m)²
max aEA/iEa An ))
52
Σ
Σ
(50)
(ddd+11)2
iE|d]
E.2
Proof of Lemma 5
Lemma 5. Let and 2 d(d 1)/2 Then under (g, Cc), OLS-UCB-C satisfies
A2 Art1
452
Actidt
(4d + (1,6)]1111
Σ
B
Σ
|B
f7,
iEAr11
(k.))Ar
(1,0))))
2
(1))At+1
3/2
(K))AAt+)
((
where σ2 dennn 2 E Ey (Eah)) 20 A
Proof. Lett d(d + 1)/2 and 8 > 0. UCB- statisfies the following Lemma.
Lemma 6. Lett 2 d(d 1 and d > 0. Then for OLS-UCE C, under the event {Ge n C.).
A & (I,, Aet1llz, + ||N. A
Therefore, under (G, n C. and
0 < A Aess
< ( A+41 zz + I|N,3 A 1l,2)
2 Arss
< f2.6 A4t1 1z, + ||,,5 A 11 2,
< 2ff (IIN," Ac+1112, + +I|N," A 112.)
22 A111
< ||N, 1
112, + +IN, 1 1
(51)
2
32

---

From, here, we develop the right-hand hand side,
|N. A411l2 N,
'I,N,',
'At1
(Ze)is
E
(bJ)EA+4
As Z, E. dA, E'ds, +. + II get
BLG Eas
Re(1,)) Dgs
|B|
|
Ae+1
=
2 iEA
(((1)))
(1a)
rEAlh1
Zi.
|| 2
S Σ 2
Σ
Σ
iEAtt1
JEALI/E,,,
1E1
((,(i.5)
by rearranging terms. Now for all (i.5) E [d],, (i,)))
then
|
IN, 1.41
Σ
Σ
Eis)
Σ
iEAc41
Re,(2,)
jEAL-1/Ej, Et.
iEA
n²
(((6.)
Denoting 02 Aud.. =2 =jE 12, (Eis)+ (E.)) yields
+2
|B
[NT
A 12 5 Σ
(52)
(1,(5.5)
n (,(E,))
tEAr11
1EAc+1
The second term from the right-hand side of Eq. (51) is developed in the same manner but involves more terms.
IN. A4t1l = A N. ",,, Ast1
(Z.)s.
Σ
(i.))
We remind that 2, - E.- da, E,d,, + N, + I where for all (t,j) E [d]
BBB
5
h2
E,(()) (e((..)) +
4
(Te,(1.5)
n2
33

---

Being under the event C, Proposition yields E(((,)) S Eig
B.B;
5ha,a
+
+
Then.
(L,(E.5) Das
|N,
A4t1122
S
E
(14)E
B,Bj
5
122
Σ
+
4
(Tn,(1s))
ni (..))
(b+))
Σ
Ba(i.)
Eig
Σ
B²
5h4,
Nº.6
1
+
+
1EA++1
(((55)
iE
(1,(
||B||2
Σ
+
(1.0)
iEA+11
0 l.
|B
(1,(5.))
(EAL11
1EAl+1
5h4,8
||
E
1
Σ
|
3/2
4
n (((5))
(++)
((((5))
(1.))A++1
(1))
5h
[B|1
|B
1
+
3/2
4
4
3
iEA++1
iEA++1
(EAr+1
(53)
Reinjecting Eq. (52) and Eq. (53) into Eq. (51) yields
A Ae+1
||,
1 + +||N," Aet1ll.
2
20
(2d + n 22
Auni +
<
(1,(3.))
iE
AEAr+1
(i.))
5h4,6
|
Σ
Σ
3/2
n2 (((5))
(K))AC-
P(,(1.)
(1))AA
The desired inequality just comes from fr.5 2 fe.6
E.3
Proof of Lemma
Lemma 6. Lett 2 d(d 1)/2 and d > 0. Then for
under the event {G n C,).
A A & fr,6 (I,,', A4illl |N, Ac41llz,)
Proof. Lett d(d + 1)/2 and 8 > 0. The error in estimating the mean reward for action a with (a, Pc) is bounded as
T wl s |N, allz. || E: d.
The definition of Gr = Ei= d n1 z,-' S Se,t yields that in this event,
f4) S u) + Se,5lIN,' Aetillze
and
(a",n) St.6||N, aa (a)
By the definition of A.- for UCB-UCB-C in (6),
(a', fr, | N, a" d'11z, < (At+1, pe) + f,, AAtillz.
34

---

Combining the expressions gives
(a",p) + fes([ a" llz. - -|N,''a az])z,) S (A + St,s(I Astillz, + |N A4z1llz))
Now, the fact that under Ct, Zr uses coefficient-wise upper bounds of Σ, which yields that
IN."a'll2, S ||N, "
Rearranging terms the desired result.
E.4 Proof of the gap-free bound
Theorem 1. Let T N and 6 O.
Then, OLS-UCB-C (Alg. 2) satisfies the gap-dependent regret upper bound
E[RT] - ((log(m))
a. An
max aE A 20
where oa = =EEa max E. 0}, and the gap-free regret upper bound
E[Rr] = ō 01 [og(m))VT Ei=
max da. aEAjiEa
Proof. Let > 0, then
T-1 Σ
A Aun (9
A (enncnn s وA)}
t=d(d+))
t=d(d-1)
Σ
A 1(8enGn(AAa =1)>
d=d(+))
T-1
A (ann (iam,>>))) >Dr]
TA
(=d(d+1)
Adapting Proposition 6 to account for A A yields
Σ DA.ai
n (A A)) A log(T)² log(m)² (og(m)
Σ
o2s)
max
nEA/iEa
iE|4
where $ is an inequality up to constant factors (when T varies).
Balancing TA and 1/2 log(T)² log(m)² EiEM (maxac sa.)) yields
E [ o log(m)
Σ
o2 aEA/iEa
iE|d
F Details for COS-V V (Section 5.3)
F.1 Proof for Lemma 7
Lemma 7, Let 8 > 0. Then COS-V V satisfies
T
T
P(H < 6
ttg
()/22
35

---

Proof. Let 8 0, d(d + 1)/2. We remind
H4 = Vie [d], (ins 91,5Ses (..)) in. S ge
(2..)// ners
(54)
where 9r,5 (2log (2dt log(t))) + log(1/6)) 1/2
Conditionally to Fi = o(A1, V1, A,, Yi), for all i E [d]
P1, ~ N (uss + (1 fr. 2,0
2 2.. f2, 12,00
Let i E a". Then Gaussian concentration yields
112 (cBest (1 g1,
2 1/2
Pr.
(,(6,)) me,(1.))
ises
(2log(2ttlog()))/))
(((1))
6 dt log(t)²
ne,(3,)
and
([(nst + Sr, (1,
1/2
2 1/2
(,(6,))
> v 2 log)))
dt log(t)²
by integration.
union bound on i E [d] and t 2 d(d + 1)/2 yields the result
Σ
P( S
t(log (t)
(=d(11))/
[E[2]
F.2 Proof for Proposition
Proposition 4. Let 8 0. Then COS-V yields
E
Σ
T-1
A
19 = =o [og(TT) log(m)²
d
m Ins
A immin
(=d(d+1)
Proof. Let O. We first make use the following Lemma.
Lemma 8. Lert 2 d(d + 1)/2, 8 > 0. Then for COS-V, under (9, nC nH),
DALL
40mEi.
29mdh? 2, BBI3
+
(55)
n2,(0.))
tEAch
iEA++1
45mha,8
B
9m|| T2,(5.)
+
(56)
3/2
iEAc-1
(F,4))
VE
Ac
This enables to use "modified" version of Proposition 6, which do not consider covariances.
Proposition 7. Let E N, (1, Let (E, (E))2((111)/2 be sequence of events such that for all t 2 d(d 1)/2, under Es.
A2 Aus
C
Σ
C.
(57)
SEA+.1
seir
LiE
where C and (C.) are problem-dependen positive constants. C2 is positive constant depending on that, C, < 2m Let e E R,, and (co)se(r) (Rt))" be positive constants such that 1/c Eie(r l/c,- 1.
36

---

Then,
Σ A 1{8)
t=dd+11//2
C₁ Ai,min
s 106cyClogee log(m)²
Σ sE(d]
1 1fes =2] (c,0C, log(m)) 1/2
Amax
m 1 1 log
A min
+ 1 < es <
(c, (300
dm
1+1/es A
1-2/ex
min
+ +1f2 < es /00.30//e lo((m))
1/ea es dm
lt//ea
A
11-2/61
(58)
c
max
where (OK) (3x) keN and kn E N are defined in Appendix D.
Applied to COS-V, V, this yields
Σ
A ([nnncm)
t=d(d+1)/2
m m.
S 15360 7. log log(m)²
Σ
immin
<E[d]
A max
+ (r2 oc mo md
1 log
A
7320066..00000) 5/3 11/3
min
+ "1g 4/3 dA
1/3
max
where
fi, 6 log ( (4
3d 3d (2log(2) + log(1+e))
h4.5 = (1 + 2 log + 2og + 1)) + log(1 + 1)2
9t,6 = (1 + log lt)()))) + log(1/6)) 1/2.
We deduce
AA (Sencna)) -o(1 -o -0(oo(C)) log(m)² (
mm
E
Σ ((d((+1)
A i.min
E3
Proof for Lemma 8
Lemma 8. Lett 2 d(d+ 1)/2, 8> > 0. Then for COS-V, under (G, CC n Hc).
A A
40mE.,
Fandh?,s|BB1
Σ
(55)
f7.0
ieAii1
Re,(1.)
1
n2
(,(,,)
45mhy,
|B
9m 9ml|BB13
Σ
Σ
(56)
3/2
(t((..)
(((()))
37

---

Proof. Let d(d + 1)/2 and ā > 0. Then
A (a" - A)+1. H))
(a" 1 (i)) + (a" Alt1, (e p4)
S (a", 1 mi) + (A4t1. - 1)
by definition of A4+1- Besides.
(a" - (i)) Σ M4 fre,i
iEa"
Σ
[ pis + Mrg Te.))
VEa*
Under G. n C,, for all E a",
Z 14 p4, S fe,
(1.(1
Under He, for all i E a",
21/2
2//2
Be, + (1 + fi. (1,6))))
1.3
Fr, S 90,6fe,
1l,,(1,))
211²
Me, - ias S ff, (i.()
Therefore, under (Ge n 74 n C.).
S AAnn I (A441,4e 14)
We now develop the expression
A A < (A 11)
+ 2 (A142, )i)² < 2 (Al+1, Rm))
< 2 Σ
+ +ff2 De, - -Res))
2
1121 1
iEAr+1
< 2m Σ
(pra (us)) 2
+ +2 |N, 1
iEAl+1
< 2m(1 + 2),, P2. Σ
+ 2f2 IIN AAt11 112
iEA
< 118mgi
Σ
2f2 I 12.
nh
iEAl+1
38

---

As
Z (k.i)) 2
Egg
B
Σ
iE1++1
(,(,,)
tEAr+1
(1,(
iEA++1
(,(i,i)
Eij
dll [|| loce
2 54,66
|B
2
+
(1,(
(2,(6,5)
3/2
AE41
iEA++1
KEA
B
|B||
Σ
Σ IEA++1
n2 ((1,))
ieA++1
(d 11 (22 B|
n (1..)))
iEA1+1
iEAc+1
|B|
|
Σ
3/2
n2 (.,1)
AE
Th (2,(1
iE
and
(l,(i.)) Eig
Pe(a,)) Dig n
|B|
|N, A 112,
E
n2
(++1)E
iEAL11
iEAc11
(G,.)))
me( V Eiiy
Σ
Ej
Σ
|
Σ
Σ
(1.(
(1.))EA++1
xEAL11
1EAL11
(L
E/11/2
Σ
(1.(1.))
(i.))AA11
SEA++1
iEA,+1
(m
+ 1)E
Bl
(1,(1,))
Th (1,(11))
JEAL11
Therefore,
36mg2 Di,
3mg + (2,,5)1111
A 2
(1,(1.))
((,(1,5)
iE AEAs+1
iE
45g
9mgg.. 1
3/2
((,(1.)
tEAr
iEAl+1
4m Di,
B| n2 n2,(0.0)
(i,()
YEAcH
YEAh+1
4m Eg, (99
+1)
27mdgg, h2
+ 2d)
S
Σ
Σ
ni.(1.))
1EA
hEAr1
BB
9 1B13
3/2
YEAc+1
(1.0))
1EA++1
40m 40mf2 En,i)
29mdff
| 1,6
|B3
< Σ
SEA
AEA
B
22 9mg
1.8 B12
3/2
1EAc
1E
39

---

This finally yields
A 11,89..6
40m2ra
29mdh 11
(2,
YeAe11
iEA++1
45mhh,s11111
9m BB
Σ
iEAc11
2,(1.)
rEAc11
G Experimental results
This section outlines some experimental results.
G.1 Theoretical regret upper bound
In this experiment, the objective show the effect of the smallest suboptimality gap Amin over theoretical gap-dependent regret upper bounds for ESCB-C and OLS- ADSSUCB-GG C. To that end, we sampled 100 environments with different Amin. with a constant number of items 20, a horizon of 10a rounds, and randomly sampled structures. We represent theoretical upper bounds with respect to 1/Amin Fig. 1.
For readability reasoning. we have rescaled and reweighted the different components the sums that the leading term in the upper-bounds (1/Amin or 1/4 for ESCB-C OLS-UCB-C) is greater/smaller than the rest, in a significant number of cases. In particular, all the theoretical upper bounds have the form
C
C'
Rr
+ C,Restt
Amin
A2
where C, C' and C, are the tuned constants.
For OLS-UCB-C,
Rest Amax(d(d 1)/2)
Amax
+ [B So, (4d h2,5) l0g(mm/)
1 log
Amin
+ |||////3 44/3, 2/3
/// log(m) 2/3 2/3 2/3 2/ 11/33
+ || 2/3
log(m)
1/3
mm 2/3 A//3
max
For ESCB-C,
Rest Amax 1)/2)
maxae 02
+ log(?") lmg(
+log(?) log (m)
Σ
log
(a.d).max
(s.)).
vE(d]
1,
A maax
log log(m) m)
log
+log(T)log(m) log(m)
1/3
A,,mi
(1.7).min
When the minimal gap is too small (right part of Fig. 1), both upper-bounds are of the magnitude of either 1 1/42 2 or 1/Amin (depending on the algorithm). In this case, the theoretical regret bound of OLS- outperforms the one of ESCB-C (green dots vs. blue dots). On the other side, when the gap big enough, the remaining terms have more impact. In this case, ESCB-C has better thcoretical guarantee (orange dots red dots).
40

---

Theoretical gap-dependant Pseudo- Regret
OLS-UCB-C, 1/Delta not than the rest
OLS-UCB-C, 1/Delta geq than the rest ESCB-C, 1/Delta not geq than the rest
Pseudo-Regret (up to mult. cst.)
10u
ESCB-C, 1/Delta 22 geq than the rest
1010
10a
10a
102
1/Delta_(min (min)
Figure I: Evolution of regret upper bounds.
G.2 Comparison between ESCB-C and OLS-UCB-C
We evaluate ESCB-C (approximated as proposed Perrault et al., 2020b) and OLS-UCB-C d items, P = 10 actions, T = 10" rounds and randomly sampled structures.
We represent the pseudo-regret evolutions in Fig. The evolutions remain the until 10 rounds. After that, ESCB-C seemingly performs better than OLS-UCB-C which has a supplementary log(!) factor and more conservative. However, just before 10 rounds, change for ESCB-C while the pseudo-regret of OLS-UCB-C continues to increase smoothly. The average regret of ESCB-C C seems have an inflexion point upward meet the q75 curve.
observe slight regime
Pseudo-Regret
10
Average
Average OLS-UCB-C
10a_
Pseudo-Regret (log)
10a
10-1
10:
10a
10a
Round (log)
Figure 2: Pseudo-regret for ESCB-C and OLS-UCB-C for randomly sampled environments (with 925 and 975 confidence intervals).
41

---

When observing the final regret with respect to 1/ //ii in Fig. 3, overall ESCB-C seems to outperform OLS- UCB-C except on some corner cases. Those cases skew the distribution for ESCB-C. Especially, for the case with the smallest suboptimality gap (the rightmost part of the figure), OLS-UCB-C outperforms ESCB-C.
Pseudo-Regret after 10 rounds
ESCB-C
Average ESCB-C
OLS-UCB-C
Average for OLS-UCB-C
Pseudo-Regret (log)
104
10a
10
10a
102 1/Delta_ (min) (log)
10a
Figure 3: Regurtt with respect to 1/Amin
The evolution of the pseudo-regret in this case with the smallest suboptimality gap is presented in Fig. 4. While ESCB-C C seems to fare better the beginning, we actually see a sharp increase in its pseudo-regret before 10y rounds. It could have been caused by the computational approximation of ESCB-C (described in Perrault et al. (2020b)), and/or could be the impact of the 1/ term.
Pseudo-Regret in the worst environment
104
ESCB-C OLS-UCB-C
10a
Pseudo Regret (log)
10a
10a
10a
10a
10a
102
10a
10a
10a
Round (log)
Figure 4: SoouooRRegred in the "worst" environment.
42

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims of the paper are stated in Theorems and Propositions which for which the technical proofs are in the Appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The results and theorems are discussed with comments made especially about some limitations. particular, computational complexity is addressed.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create 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 (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn 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 few datasets or with 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, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
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 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
43

---

Answer: [Yes]
Justification: The Theorems and proofs are numbered and cross-referenced. The proofs for the main results are outlined the paper and formally written in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide 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.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper is mainly states theoretical results and include no experiments.
Guidelines:
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 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, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, 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 submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
44

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /nipp. ccppp.ccpppulcc///eecccc/ wetpiiii/ggiee...eeeeo/eooeoeeee /CodeSubmia (iioiicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
The answer NA means that the paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
45

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https ptttps://neuriii htt////nurripp.ppe hwtpp//bbbcc..ccccccttteeeeelele
Answer: [Yes]
Justification: We have reviewed the NeurlPS Code of Ethics. The paper does not involve human subjects or participants, and the data-related concerns are not applicable.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper is mainly theoretical and is not directly tied to application.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact 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.
46

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere 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 best faith effort.
12. Lieenses 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 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
47

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
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 NeurlPS 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.
48


Reviews:
[{"review_id": "Q1Nd9yj9SF", "reviewer": "Reviewer_zmBr", "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.", "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.\n- 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?\n- 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": "The authors have adequately addressed the limitations of their work.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is well-written in a reader-friendly manner. It contributes a  variety of highly non-trivial theoretical results that improve upon the current state-of-the-art, with extensive proofs in the appendix.", "weaknesses": "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.\n\nApart of that I have only the following rather minor issues and typos/suggestions:\n- 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?\n- 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.\n- In Algo 2, line 3,  does it have to be $\\leq 2$ instead of $\\leq 1$?\n- 8: yield[s]\n- 10: $\\mathcal{O}(\\sqrt{T})$ instead of $\\sqrt{T}$?\n- 28: At each round\n- 108: adaptative\n- 139: positive semi-definite\n- 269: $\\mathbb{P}(\\mathcal{C}^c)$\n- 272: sketch of the proof\n- You oftentimes write $A\\bigcap B$ instead of $A\\cap B$, why?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "___Concerning the minor questions and remarks___\n\nWe first wish to thank the reviewer for pointing out our typos and inaccuracies.\n\n> 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?\n\nThe theorem holds in expectation, and is applicable for both deterministic and for stochastic policies. \n\nBesides, it seems that there is a mistake in our formulation. We inverted a “for all\" and a “there exists\" statement. We should have written: “For any policy $\\pi$, there exist a stochastic combinatorial semi-bandit such that$\\dots$\". We are very grateful to the reviewer for pointing out this inaccuracy, which allowed us to correct a mistake.\n\n> In Algo.2, line 3, does it have to be $\\leq 2$ instead of $\\leq 1$ ?\n\nIt should be either $\\leq 1$ or $<2$. All the coefficients indexed by $(i,j)$ are correctly defined as soon as the corresponding interaction has been observed at least twice.\n\n> You oftentimes write $A\\bigcap B$ instead of $A\\cap B$, why?\n\nThe reason is purely aesthetic, we will uniformize the notation.\n\n___\n___Concerning the main questions___\n\n> 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.\n\nIn our analysis, $B$ appears in the negligible additive terms (w.r.t. the dependence in $T$). Using a “looser\" $B$ may make the convergence a little slower, but would not impact the asymptotic regret.\n\nIn practice, knowing a plausible upper bound on the rewards is sufficient. In realistic settings, we can assume that a player knows such an upper bound B_i. In that case, they can replace $Y_{t, i}$ with $min(max(Y_{t, i}, -B_i), B_i)$ and use our algorithms.\n\nOtherwise, one could try a Doubling Trick. We initialise $B$ at a certain power of $2$, and then we restart the algorithm each time an observation surpasses it, after doubling the current value of $B$. This would add a multiplicative factor to the regret bounds, of magnitude $\\log(B^*)$ where $B$ is a “true\" upper bound.\n\n> In Table 1, do you know how $C^{opt}_{1/T}$ scales in comparison to $d^2$ ? That is, do you know that OLS-UCB-C outperforms ESCB-C regarding time complexity?\n\n$C^{opt}_{1/T}$ scales with the horizon $T$, contrarily to ou per-rounds complexities. Ultimately, our complexity will then be better for horizons large enough.\n\n> 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?\n\nWe have formulated $f_{t, \\delta}$ and $g_{t, \\delta}$ so as to isolate $\\delta$ from the dependence on time and dimension. \n\nIts influence shows through $\\log(1/\\delta)$ factors in negligible additive terms. $\\delta$ is fixed at the beginning and characterizes a tradeoff when sizing the ellipsoids. It influences how quick we reach the asymptotic regret rate but not the said rate.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QXftZQw5mj", "reviewer": "Reviewer_47Sr", "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.", "questions": "1. Concerns regarding the role of `f_t,δ` and `g_t,δ` functions in Eq. 6 and 7.\nThe 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:\n\n     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. \n\n     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? \n\n   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. \n\n2. 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": "As described in the paper, the results and theorems are discussed with comments made especially about some limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper presents new algorithms that improve on both the computational efficiency and regret bounds by adapting to the covariance structure of the environment, which is crucial for applications where the rewards are not independent across actions.\n\n2. It provides the first gap-free regret bounds (regret bounds that do not depend on the minimum sub-optimality gap between the best and second-best actions) for these types of problems, extending the theory beyond independent rewards assumptions.", "weaknesses": "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. \n\n2. While the algorithms' theoretical framework and mathematical formulation are well-articulated, the lack of experimental results or simulations leaves a crucial gap.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "___Concerning the weaknesses___\n\n> 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.\n\nIn many realistic settings, a player would be able to tell what scale of values for $Y_{t, i}$ is normal or not. If they can identify an upper bound $B$, then they could use the algorithms with $min(max(Y_{t, i}, -B), B)$ instead of the \"true\" $Y_{t, i}$ observed.\n\nOtherwise, one could try a Doubling Trick. We initialise $B$ at a certain power of $2$, and then we restart the algorithm each time an observation surpasses it, after doubling the current value of $B$. This would add a multiplicative factor to the regret bounds, of magnitude $\\log(B)$, where $B^*$ is a “true\" upper bound.\n\n___\n___Concerning the main questions___\n\n> Concerns regarding the role of $f_{t,\\delta}$ and $g_{t,\\delta}$ functions in Eq. 6 and 7. The algorithms utilize the functions $f_{t,\\delta}$ and $g_{t,\\delta}$ to dynamically adjust the exploration strategy. The paper implies an increase in $f_{t,\\delta}$ and $g_{t,\\delta}$ as $t$ increases, which leads to an increasing exploration bonus and variance over time. [...]\n>> a) Increasing Exploration Over Time [...].   \nb) Design Justification for $g_{t,\\delta}$ and $f_{t,\\delta}$ [...].  \nc) Impact on Algorithm’s Performance [...].\n\nWe acknowledge the fact that the $\\log(t)$ increase can be counterintuitive and may add an explanation in subsequent versions to clarify it.\n\nThe exploration is actually not increasing over time. The decay on the exploration bonus, comes more from the number of times each item/couple has been observed $(n_{i,j})$ rather than from $\\log(t)$ (See Eq.4 and Eq.6 for example). Like for all the main variants of UCB, the exploration bonuses look like a sum of $\\sqrt{\\frac{\\log(\\delta)}{n_{i,j}}}$, which decreases as the number of time each item is chosen increases.\n\nUsing $\\log(t)$ (instead of $\\log(T)$) ensures adaptivity to the time horizon and has been commonly used in several other papers.\n\nThe justification for $f_{t, \\delta}$ is explained in Section 4: it originates from the way the ellipsoids are designed. $f_{t, \\delta}$ is involved in the definition of event $G_t$ in Eq.9 and its expression ensures Prop.1 is satisfied. $g_{t, \\delta}$ controls the exploration made by COS-V. Its expression is derived from union bounds which enable Lemma 5 to be satisfied.\n\n> 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?\n\nWe think that other distributions could actually be used. \n\nUsing Gaussian distributions was a natural direction as they are standard distributions, we know how to sample them efficiently, especially for given covariance matrices, and we know how to control their tails with usual tools.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hw8ukZ9QFz", "reviewer": "Reviewer_RAfE", "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.", "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": "A sharp dependence on the horizon $T$ is more important for the instance-dependent guarantees.", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written.\n\nThe worst-case guarantees and instance-dependent guarantees represent a significant enhancement over existing algorithms that adapt to covariance. \n\n2 different and relevant algorithms and analysis are proposed.\n\nThe comparison of regret rates and computational complexity between different algorithms is clear.", "weaknesses": "The log(T) term has a power 3 in the regret bound, which can be improved.\n\nThe approach of estimating the covariance matrix online and using it for confidence bounds is not new.\n\nNo empirical evaluation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "___Concerning dependance in $T$___\n\n> The log(T) term has a power 3 in the regret bound, which can be improved.\n> 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 ?\n> A sharp dependence on the horizon $T$ is more important for the instance-dependent guarantees.\n\nThe $\\log(T)$, actually has a power $2$ for OLS-UCB-C and $3$ for COS-V.  The two first exponents come from the online nature of the problem (Laplace trick) and the covariance estimations. The last one, only present in COS-V, comes from the union bounds made on the sampling distribution.\n\nESCB-C manages a $\\log(T)$ with power $1$, but suffers from more computational complexity than OLS-UCB-C and does not satisfy a $\\tilde{O}(\\sqrt{T})$ gap-free regret because it incurs a $1/\\Delta_{min}^2$ in the gap-dependent bound. For randomized algorithms, there exists $\\log(T)$ gap-dependent bounds for Combinatorial Thompson Sampling. However, they also suffer from additional terms that can be up to $1/\\Delta^d$, which prevent the $\\tilde{O}(\\sqrt{T})$ gap-free bound.\n\nAll in all, it is indeed possible to get better $\\log(T)$ exponents for the gap-dependent bounds. However, known approaches do not satisfy a $\\tilde{O}(\\sqrt{T})$ gap-free bound at the same time. It means that on “difficult\" instances, our algorithms will incur $\\tilde{O}(\\sqrt{T})$ regret, while others may suffer regrets that are a lot worse (Imagine $\\Delta \\sim 1/T$ for example).\n\nWe are not aware of any straightforward way to reduce the $\\log(T)$ exponents and keep the desired gap-free bounds at the same time.\n\n___\n___Concerning the covariance matrix___\n> The approach of estimating the covariance matrix online and using it for confidence bounds is not new.\n\nThe approach is indeed not new (and it is even natural) and we do not claim to be the first. But the way to incorporate those estimators in our analysis is rather new.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to sincerely thank the reviewers, ACs, SACs and PCs for their expertise and the time they are devoting to our submission. Their feedback and suggestions are very valuable and will be taken into account.

___General comments___

We were provided 3 high quality reviews that acknowledge the strengths of our submission, namely, the improvement over existing results by providing gap-free bounds, the clear presentation and the mathematical soundness.

We answer the specific questions of each reviewer in the per-review rebuttal.

Concerns over (the lack of) empirical evaluations have been raised by several reviewers. Our contributions being theoretical, we did not consider a priority to provide such evaluations and consider our contributions self-sufficient as is. We answer the concerns in more details in the following.

___
___Concerning empirical evaluations___

Although our contributions are mainly theoretical, we agree that some empirical evaluations could be interesting. However, we consider our submission self-sufficient as is. We detailed clear and complete proofs and strove to make the presentation clear. Their quality has been unanimously recognized as a main strength of our submission.

We are considering adding an experimental part in the Appendix for a new version, but we wish to show insightful results and illustrations to match the quality of our current main document. If the reviewers have specific demands and/or suggestions, we can try to produce them as our algorithms (and some competitors) can be easily implemented (although they all still need to be tuned).

For the sake of illustration, we provide regret curves in a PDF file, for a randomly generated synthetic environment, for OLS-UCB-C, where we see that it is comparable to other combinatorial algorithms.

Meta-review: 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.
Decision: Accept (poster)