Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits
Authors: Jie Bian
Vincent Y. F. Tan
Venue: Accepted by TMLR ()

Abstract: The Indexed Minimum Empirical Divergence (IMED) algorithm is a highly effective approach that offers a stronger theoretical guarantee of the asymptotic optimality compared to the Kullback--Leibler Upper Confidence Bound (KL-UCB) algorithm for the multi-armed bandit problem. Additionally, it has been observed to empirically outperform UCB-based algorithms and Thompson Sampling. Despite its effectiveness, the generalization of this algorithm to contextual bandits with linear payoffs has remained elusive. In this paper, we present novel linear versions of the IMED algorithm, which we call the family of LinIMED algorithms. We demonstrate that LinIMED provides a $\widetilde{O}(d\sqrt{T})$ upper regret bound where $d$ is the dimension of the context and $T$ is the time horizon. Furthermore, extensive empirical studies reveal that LinIMED and its variants outperform widely-used linear bandit algorithms such as LinUCB and Linear Thompson Sampling in some regimes.

Published in Transactions on Machine Learning Research (04/2024)
Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits
Jie Bian
jichian nusoon.annuueeeee nus.edu
Department of Electrical and Computer Engineering
National University of Singapore
Vincent Y. F. Tan
vlan Crrus. edds.sedus.... sg
Deportment of Mathematics Department of Electrical and Computer Engineering National University of Singapore
Reviewed on OpenReview: https: // openrevee.. net/ forum? id= WSP
Abstract
The Indexed Minimum Empirical Divergence (IMED) algorithm a highly effective ap- proach that offers stronger theoretical guarantee of the asymptotic optimality compared to the Kullback Leibler Upper Confidence Bound (KL-UCB) algorithm for the multi-armed bandit problem. Additionally, it has been observed to empirically outperform JCBB-ased algorithms and Thompson Sampling. Despite its effectiveness, the generalization of this algorithm to contextual bandits with linear payoffs has remained elusive. In this paper, we present novel linear versions of the IMED algorithm, which we call the family of LinIMED algorithms. We demonstrate that LinIMED provides a (dvTT) upper regret bound where d is the dimension of the context and T is the time horizon. Furthermore, extensive em- pirical studies reveal that LinIMED and its variants outperform widely-used linear bandit algorithms such as LinUCB and Linear Thompson Sampling in some regimes.
1 Introduction
The multi-armed bandit (MAB) problem (Lattimore & Szepesvári (020)) is classical topic in decision theory and reinforcement learning. Among the varions subfields of bandit problems, the stochastic lincar bandit the most popular area due to its wide applicability as personalized recommendation systems (Li al. (2010)), online advertising, and clinical trials. In the stochastic lincar bandit model, at each time step the learner has to choose arm A, from the time- varying action set A.. Each arm E Ar has corresponding context 21,a Rd, which is d-dimensional vector. By pulling the arm E A, at time step f, under the linear bandit setting, the learner will receive the reward Yr,,, whose expected value satisfies [rt,a (0", Ir,a); where 0 E d is an unknown parameter. The goal of the learner is to maximize his cumulative reward over a time horizon T, which also means minimizing the cunulative regret, defined Rr E En_ maxac., (0", Y.A. The learner needs to balance the tradc-off between the exploration of different arms (to learn their expected rewards) and the exploitation of the arm with the highest expected reward based on the available data.
large-scale, real-world applications such
1.1 Motivation and Related Work
The K-armed bandit setting is a special case the linear bandit. There exist several good algorithms such as UCB1 (Auer et al. (2002)), Thompson Sampling (Agrawal & Goyal (2012)), and the Indexed Minimum Empirical Divergence (IMED) algorithm (Honda & Takemura (2015)) for this setting. There are three main families of asymptotically optimal multi-armed bandit. algorithms based on different principles (Baudry et al.

---

Published in Transactions on Machine Learning Research (04/2024)
Problem independent regret bound
Regret bound inde- pendent K?
Principle that the algo- rithm is based on Optimism
OFUL
Abbasi- Yadkori
et al.
((dv'Tlog(T))
V
2011
Lin CBB (1. et al.
2010
Hard to analyze
Unknown
Optimism
LinIS (Agrawal Goyal (2013)
Oldi D(dy/Tlog(/
/
Posterior sampling
SCPLinUCB [Chu al.
2011
Oly dT log (KCT)
X
Optimism
LinUCB with OFUL's confidence
Old/T log(T))
V
Optimism
bound
Asymptotically Optimal (Kinschner et al. 20221)
IDS
O(dy (Tg())
/
Information
directed
sampling
LinIMED33 (this paper)
Oldy' [Tgg()))
/
Min. emp, divergence
SupLinIMED (this paper)
Oly df (KT))
x
Min. emp, divergence
Table 1: Comparison of algorithms for linear bandits with varying arm sets
However, among these algorithms, only IMED lacks extension for contextual bandits with linear In the context of the varying arm setting of the linear bandit problem, the LinUCB algorithm in Li et al. 2010) is frequently employed in practice. It has a theoretical guarantee on the regret in the order of O(dvT T (Tdg))lo((T)) using the confidence width as in OFUL (Abbasi
2023
payoff.
et al. (2011) ). Although the
SCpLinUCB algorithm introduced by Chu et al. (2011) uses phases to decompose the reward dependence of each time step and achieves an O(VdT) (the O(-) notation omits logarithmic factors in T) regret upper bound, its empirical performance falls short of both the algorithm in [i et al. (2010) and the Linear Thompson Sampling algorithm (Agrawal Goyal 2013 as mentioned in Lattimore & Szepesvári (2020 Chapter 22).
On the other hand, the Optimism in the Face of Uncertainty Linear (OFUL) bandit algorithm in Abbasi- Yadkori et al. 22011) achieves a regret upper bound of (dd/T) through an improved analysis of the confidence bound using a martingale tochnique. However, it involves a bilincar optimization problem over the action set and the confidence ellipsoid when choosing the arm at each time. This is computationally expensive, unless the confidence ellipsoid is a convex hull of finite set.
For randomized algorithms designed for the linear bandit problem, Agrawal & Goyal 2013 proposed the LinTS algorithm, which is in the spirit of Thompson Sampling Thompson (1933) and the confidence ellipsoid similar to that of LCnUCB-like algorithms. This algorithm performs efficiently and achieves a regret upper bound of Ō /T Ad K), where K is the number of arms at each time step such that |Arr] = for all Compared LinUCB with OFUL's confidence width, it has an extra O(vd Vlog K) term for the minimax regret upper bound.
Recently, MED-like (minimum empirical divergence) algorithms have come to the fore since these randomized algorithms have the property that the probability of selecting each arm is in closed form, which benefits downstream work such as offline evaluation with the inverse propensity score. Both MED in the sub- Gaussian environment and its deterministic version IMED have demonstratod superior performances over Thompson Sampling (Bian & Jun 2021), Honda Takenura (2055)) Baudry et al. (2023) also shows MED has a close relation to Thompson Sampling- In particular, it is argued that MED and TS can be interpreted as two variants of the same exploration strategy. [ian & Jun (2021) also shows that probability closed-form approximation of the
of selecting each arm of MED in the Sab-Gaussian case can be viewed same probability as in Thompson Sampling. We take inspiration from the extension of Thompson Sampling to linear bandits and thus are motivated to extend MED-like algorithms to the linear bandit setting and prove regret bounds that are competitive vis-à-vis the slate-of-the-ard bounds.
Thus, this paper aims answer the question of whether is possible to devise an extension of the IMED algorithm for the lincar bandit problem the varying arm set setting (for both infinite and finite arm sots) with regret upper bound of O(dVTlog being as efficient as LinUCB. The proposed family of algorithms, called LinIMED as well as SupLinIMED, can be viewed as gencralizations of the IMED algorithm (Honda & Takemura (205 to the lincar bandit setting. We prove that LinMMED and its variants achieve a regret upper bound of O(dVT) and they perform
which matches LinUCB with OFUL's confidence bound while
2

---

such that Published in Transactions on Machine Learning Research (04/2024)
efficiently, worse than LinUCB. SupLinIMED has regret bound of Ö(v dT), but works only for instances with finite arm sets. In our empirical study, we found that the different variants of LinIMED perform better than LinUCB and LinTS for various synthetic and real-world instances under consideration.
Compared to OFUL, LinIMED works more efficiently. Compared to SupLinUCB, our LinIMED algorithm is significantly simpler, and compared to LinUCB with OFUL's confidence bound, our empirical performance is better. This because in our algorithm, the exploitation term and exploration term are decoupling and this leads to finer control while tuning the hyperparameters in the empirical study.
Compared to Lin our algorithm's (specifically LinIMED-3) regret bound is superior, by an order of OlVd A Vlog K). Since fixed arm setting is a special case of finite varying arm setting, our result is more general than other fixed-arm linear bandit algorithms like Spectral Eliminator (Valko et al. (2014)) and PEGOE [Lattimore & Szepesvári (2020] Chapter 22)). Finally, we observe that since the index used in LinIMED has a similar form to the index used in the Information Directed Sampling (IDS) procodure in Kirschner et al. (2021) (which is known to be asymplotically optimal but more difficult to compute). LinIMED performs significantly better on the "End of Optimism" example in Lattimore & Szepesvari (2017).
We summarize the comparisons of LinIMED to other linear bandit algorithms in Table D
We discussion
comparisons to other linear bandit algorithms in Sections 3.2 3.3 and Appendix B
2 Problem Statement
For any d dimensional vector x E Id and a d x d positive definite matrix A, we use ||=||a a to denote the Mahalanobis norm Vx Ax. We use aAb (resp. a Vb) to represent the minimum (resp. maximum) of two real nunbers a and b.
Notations:
The Stochastic Linear Bandit Model: In the stochastic linear bandit model, the learner chooses an arm A₁ at each round t from the arm set A; = far,1, a.. S IR where we assume the cardinality of each set A can be potentially infinite such that [Arl = do for all & 2 1. Each arm Ar at time / has corresponding context (arm vector) Zι,a Rd, which is known to the learner. After choosing arm AG, the environment reveals the reward
Y = (0", X1) +
to the learner where X, Fe,A, is the corresponding context of the arm A,, 0" E Rd is an unknown coefficient of the linear model, ahe is an R-sub-Gaussian noise conditioned on (A, A2...., .a....,Ay A,, Y1, Y2...., Y--1) 22....,y-11. for any X E R, almost surcly,
R²
E [exp(An))
Y--1 S exp 2
Denote at == arg m... (0", zr,a)) as the arm with the largest reward at time t. The goal is minimize the expected cumulative regret over the horizon T. The (expected) cumulative regret is defined as
T Σ (0', 22,07) -8",
R = E
Assumption 1. For each time t, we assume that ||xell S L, and ||0*1| S. S for some fized L, S > 0. We also assume that A == max (8", Ir,a) (0", xe,)) & for each arm E A, and time t.
3 Description of LinIMED Algorithms
In the psoudocode of Algorithm [ for each time step in Line 4, we use the improved confidence bound of 0* in Abbasi-Yadkori et al. (2011) to calculate the confidence bound 9r-(77). After that, for each arm Ae, in Lines 0 and the empirical gap between the highest empirical reward and the empirical reward of arm a is estimated as
Å =
maxjEA, (0,-1, (0.-1, maxjEA, UCB UCB, (a)
if LinIMED-1,2
if LinIMED-3
3

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm LinIMED-E for z E (1,2.3)
Input: LinIMED mode z;, Dimension d, Regularivation parameter X, Bound on ||0 Sub-Gaussian parameter R, Concentration parameter 7 of 0", Bound on || for all t 2 1 and Ar, Constant
C21.
2: Initialize: Vo Alxxd, Wo Oax1(all zeros vector with d dimensions), 0g Vo- Wo VWo
3: for t= 1......77 do
Receive the set A, and compute 3e-1(7) RR /log (((1-1)22/2) + VxS)
7
5: for a E A do
6: Compute: p= = -0,11, and UCB.(a) = 10,-1, J2.a) + +V B (
Compute: Dr, (maxjEA, Bi. - (r..a) 1(2 1, 2} + (maxjeA, UCB.(j) UCB.(a)) 1 (xr =3 if a arg E. (Rt.j 1(x= 1,2] UCB, 1f- 3}) then
Le.a - log( (3--3111 (7) [ -1
(LinIMED-1)
10:
+ log I' A (1og \ 1 2
(LinIMED-2)
11:
+ log C (
( log
))]
1fx =3
(LinIMED-3)
maxucAd $7,0
12:
else
13:
4.a = 3 11-17t]| V.
log 10g(8(_17)]1Exaa
14:
end if
15:
end for
16: Pull the arm A, arg min, laa (ties are broken arbitrarily) and receive its reward Y,.
17:
Update:
18:
Vi == V + X,X,, W. = Wi- + Y,N,, and 0₂ = V.W.
19: end for
Then, in Lines to with the use of the confidence width of 3/-1(7), dex Ita for the empirical best arm arg argmax Pr,a (for LinIMED-1,2) or the highest UCB arm arg JAA, UCB, (a) (for LinIMED-3). The different versions of LinIMED encourage different amounts of exploitation. For the other arms, in Line 13 the index defined and computed as
compute the in-
I,a = Be-1(7)
+ log B1-1(7) (z 1
V=
Then with all the indices of the arms calculated, in Line 16 we choose the arm A, with the minimum index such that At arg min Lea (where ties are broken arbitrarily) and the agent receives its reward, Finally, in Line 18 we use ridge regression to estimate the unknown 0* as O2 and update the matrix V2 and the vector W. After that, the algorithm iterates to the next time step until the time horizon T. From the pseudo-code, we observe that the only differences between the three algorithms are the way that the square gap, which plays the role of the empirical divergence, is estimated and the index of the empirically best arm. The latter point implies that we encourage the empirically best to be selected more often in LinMEED-2 and LinIMED-3 compared to LinIMED-1; in other words, encourage more exploitation in LinIMED-2 and LinIMED-3. Similar to the core spirit of IMED algorithm Honda & Takemura (0015), the first term of our index Tt. for LinMMED-1 algorithm is while the second term - 1og( ( controls the exploration in our algorithm.
this is the term controls the exploitation,
3.1 Description of the SupLinIMED Algorithm
Now we consider the case in which the arm set A, at cach time finite but still timo-varying. In particular, A 01.,........... } C are sets of constant size K such that [Ael K < co. In the pseudocode of Al Algorithm 2 we apply the SUPLinUCB framework (Chu et al. 2011,, leveraging Algorithm (in Appendix A
4

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm 2 SupLinIMED Input: T N, 5' [og I, V for 1.2.... T do and Å [K]
for all E [ (T)
repeat
5:
with V to calculate the width wia and Use UCs (stated in Algorithm in Appendix A
sample mean Pi: for all A.
if wi,a I 1 for all E A. then /T
choose A = arrg med. I,a where I the same index function as in LinIMED algorithm: Calculate the index
log(2T) A (-log((wf,))
If arg max Y otherwise
1,a
Ai (2 - log((w; 10
where
Åi. = max Yú,b P.c. bed,
9:
Keep the same index sets at all levels: wit1 + wes for all s' E [S]
+ Case 1
10:
else if wfea - for all A, then
A.t1
a E A. Via + af max E'E, VVia + ) - 21-8)
11:
12:
+ s
Case 2
13:
clse
14:
Choose A₁ E Ag such that Wi,,, > 2
15: Update the index sets at all levels: Vith f Vi U(' if s witz + wi ifs s
+ Case 3
16: end if
17: until action A, is found
18:
end for
a subroutine within each phase. This ensures the independence of the choice of the from past observations of rewards, thereby yielding concentration inequality in the estimated reward (see Lemma in Chu et al. (2011)) that converges to within vd proximity of the unknown expected reward in finite arm setting. As a result, the regret yields an improvement of v ignoring the logarithmic factor. At each time step f and phase 8, in Line 5, we utilize the BaseLinUCB Algorithm as a subroutine to calculate the sample mean and confidence width since we also need these terms to calculate the IMED-style indices of each arm. In Lines 6-9 (Case 1), if the width of each arm less than /T we choose the arm with the smaller IMED-style index. In Lines 10-12 (Case 2), the framework is the same as in SupLinUCB (Chu et al. (201) if the width of each arm is smaller than 2- but there exist arms with widths larger than VT: then in Line 11 the "unpromising" arms will be eliminated until the width of each arm is smaller enough to satisfy the condition in Line 6. Otherwise, if there exist any arms with widths that are larger than 2-s, in Lines 14-15 (Case 3), we choose one such arm and record the context, and reward of this arm to the next layer V
3.2 Relation to the IMED algorithm of Honda Takemura (2015)
The IMED algorithm is a deterministic algorithm for the K-armed bandit problem. At each time step t, it chooses the arm a with the minimum index, i.e.,
a = arg min (I(() ( =E[K]
+ log Ti(t))
(1)
where Ti(t) E a} is the total arm pulls of the arm i until time t and (tn)(F(tt))) (t)) is some divergence measure between the empirical distribution of the sample mean for amn i and the arm with the highest sample mean. More precisely, Dmt(F. == inf D(F and g the family of distributions supported on (-o0, 1]. As shown in Honda & Takemura (2015), its asymptotic bound even better than KL-UCB (Garivier & Cappé (2011) algorithm and can be extended to semi-bounded support models such as 9. Also, this algorithm empirically outperforms the Thompson Sampling algorithm as shown
5

---

Published in Transactions on Machine Learning Research (04/2024)
in Honda & Takemura (2055). However, extension of IMED algorithm with minimax regret bound of (dV has not been derived. In our design of LinlMED algorithm, we replace the optimized KL-divergence mcasure in IMED in Eqn. 1 with the squared gap between the sample mcan of the arm i and the arm with the maximum sample mean. This choice simplifies our analysis and does not adversely affect the regret bound. On the other hand, we view the term (t) as the variance of the sample mean of arm i at time t; then in this spirit, we use (e-1(1)]lez,alllzz as the variance of the sample mean (which is (81-1, 21,a)) of arm at time t. We choose (Bt (B-- (7) || [ instead of the KI-divergence approximation for the index
since in the classical linear bandit sctting, the noise is sub--Gausiian and it is known that the KT-divergence of two Gaussian random variables with the same variance (H,, ))), N [u1 (u==)))²) has a closed form expression similar to (3c-
20
ignoring the constant
3.3 Relation to Information Directed Sampling (IDS) for Linear Bandits
Information Directed Sampling (IDS); introduced by Russo & Van Roy (2014), serves as a good principle for regret minimization in linear bandits to achieve the asymptotic optimality. The intuition behind IDS is to balance between the information gain the bost arm and the expected reward at each time step. This goal is realized by optimizing the distribution of selecting each arm π E D(AA (where A is the fixed finite arm set) with the minimum information ratio such that:
m == arg min (
IDS
RED(A) (T))
where Å, is the empirical gap and 9r is the so-called information gain (defined later). Kirschner & Krause (2018), Kirschnor et al. (2020) and Kirschner et al. (2021) apply the IDS principle to the lincar bandit setting, The first two works propose both randomized and deterministic versions of IDS for linear bandit. They showed a near-optimal minimax regret bound of the order of (ddT)). Kinschner al. (2021) designed an asymptotically optimal linear bandit algorithm retaining its near-optimal minimax regret properties. Comparing these algorithms with our LinIMED algorithms, we observe that the first term of the index of non-greedy actions in our algorithms is
), which is similar to the choice of informa-
tion ratio in IDS with the estimated gap (a) År. defined in Algorithm 1 and the information ratio (a(a) = (1-1(7)] v As mentioned in Kirschner & Krause (2018). when the noise is 1-subgaussian and | 1 1, the information gain in deterministic IDS algorithm approximately | which is similar to our choice 3 (1 ll However, our LinIMED algorithms are different from the deter-
ministic IDS algorithm in Kirschner & Krause (2018) since the estimated gap defined in our algorithm م is different from that in deterministic IDS. Furthermore, as discussed in Kirschner et al. (2020), when the noise is I-subgaussian and | < 1, the action chosen by UCB minimizes the deterministic information ratio. However, this is not the case for our algorithm since we have the second term - 1og(((_1(7) +
in LinIMED-1 which balances information and optimism. Compared IDS in Kirschner et al. (2021), their algorithm is randomized version of the deterministic IDS algorithm, which is more computationally expen- sive than our algorithm since our LinIMED algorithms are fully deterministic (the support of the allocation in Kirschner et al. (2021) is two). IDS defines more complicated version of information gain to achieve asymptotcaally optimality. Finally, to the best of our knowledge, all these IDS algorithms are designed for linear bandits under the setting that the arm set fixed and finite, while in our setting we assume the arm set is finite and can change over time. We discuss comparisons to other related work Appendix B
4 Theorem Statements
Theorem 1. Under Assumption 1
the assumption that (0", I),)) 2 0 for all t assumption that VXS > 1, the regret of the LinIMED-1 algorithum is upper bounded as follows:
1 and E A,, and the
Rr ((dTTTlo'((T))
6

---

Published in Transactions on Machine Learning Research (04/2024)
A proof sketch of Theorem is provided in Section
Theorem 2. Under Assumption and the assumption that VXS 2 1, the regret of the LinIMED-2 algorithm is upper bounded as follows:
Ri OddVTlog (T)).
Theorem 3. Under Assumplion the assumplion that vAS 2 1, and that C in Line 11 is a constanl, the regret of the LinIMED-3 algorithm is upper bounded as follows:
R S (dvVTlog(T))
Theorem 4. Under Assumption 7. the assumption that I, = 1, the regret of the SupLinIMED algorithm (which applicable to linear bandit problems with K < oo arms) upper bounded as follows:
Rr S (V (KT)
The upper bounds on the regret of LinIMED and its variants all of the form Ö(dVT), which, ignoring the logarithmic term, is the same OFUL algorithm (Abbasi-Yadkon et al. (2011)). Compared to LinTS, it has an advantage of O(VdA Vlog K). Also, these upper bounds do not depend on the number of arms K, which mcans it can be applied to lincar bandit problems with a large arm set (including infinite arm scts). One observes that LinIMED-2 and LinIMED-3 do not require the additional assumption that (0", ,Tr,a) 2 0 for all 2 1 and a E A, to achieve the (dv/T) upper regret bound. It is difficult to prove the regret bound for the LinIMED-1 algorithu without this assumption since in our proof we need to use that (0", X.) 2 0 for any time t to bound the Fi term. On the other hand, LinIMED-2 and LinIMED-3 encourage more exploitations in terms of the index of the empirically best arm at each time without adversely influencing the regret bound; this will accelerate the learning with peel-preproeessed datasets. The regret bound of LinIMED-3, in fact, matches that of LinUCB with OFUL's confidence bound. In the proof, we will extensively use technique known as the "peeling device" (Lattimore & Szepesvári 2020, Chapter 9). This analytical technique, commonly used in the theory of bandit algorithmss, involves the partitioning of the range of some random variable into several pieces, then using the basic fact that P(A n 2 B;)) s E P(ANB.)) we can utilize the more refined range of the random variable to derive desired bounds.
Finally, Theorem says that when the arm set finite, we can use the framework of SupLinUCB (Chu et al. 2011) with our LinIMED index J to achieve a regret bound of the order of Ō(VaT), which is vd better than the regret bounds yiclded by the family of LinIMED algorithms (ignoring the logarithmic terms). The proof provided in Appendix
5 Proof Sketch of Theorem 1
We choose to present the proof sketch of Theorem 1 ssice it contains the main ingredients for all the theorems in the preceding section. Before presenting the proof, we introduce the following lemma and corollary.
Lemma 1. (Abbasi- Yadkori et al. (2011] Theorem 2)) Under Assumplion
i for any time step 2 and
any 7 > 0, we have
P( - 0'1lve_ S (B--((7) 21
This lemma illustrates that the true parameter 6* lies in the ellipsoid centered 0,- with high probability, which also states the width of the confidence bound.
The second is a corollary of the elliptical patential count lemma in Abbasi- Yadkori et al. 2011
Corollary 1. (Corollary of Lattômore & Szepesvári 22000, Exercise 19.3)) Assume that Vo = Al and X
L for t [T], for any constant < m & 2, the following holds:
T
< 6d
2L2
Σ
||x 1
2 m
log (1
Amn

---

Published in Transactions on Machine Learning Research (04/2024)
We remark that this lemma is slightly stronger than the classical elliptical potential lemma since it reveals information about the upper bound of frequency that [|xil exceeds some value m. Equipped with this lemma, we can perform the peeling device on || in our proof of the regret bound, which novel technique to the best of our knowledge.
Proof. First we define at as the best arm time step t such that at = arg max (0", It,a), and use 27 = 2t,07 denote its corresponding context. Let A. == (0" ,-t) (0", Xi) denote the regret in time Define the following events:
Bg = 1100--11111000 0 10 S BB-1(1))) C. == max (0-11, Fe,bl > (0", xt¹) -6, bEAt
Dj ( 2 20).
where 8 and & are free parameters set be 8
and E =
)r, this proof sketch.
Vlog
Vlg T
Then the expected regret RT = E' EL A can be partitioned by events Br, Ce, Dr such that:
T Σ
R E A t=1
C,,
A 1(B, C, D2 + A.
(B,
> A 1 B
1=1
t=1
For F1, from the event C. and the fact that (0","7) = A. + (,) 2 A, (here is where we use that
(0" a1,) 2 O for all t and a), we obtain max (01-1, Z1,b) > (1 Vlog )r, For convenience, define
A, = arg max (0--1, ze,o) as the empirically best arm at time step t, where tics are broken arbitrarily, then use X; denote the corresponding context of the arm Å.. Therefore from the Cauchy-Schward Schwarz inequality, we have 10,-11lv,,,ll I1lellyz 2 1,)) > (1 VlogT ) This implies that
1 V
(1 VloT
[xolll--1 2
(2)
100-1llve.
On the other hand, we claim that |10-- l/ can be upper bounded as O(VT). This can be seen from the fact that [|0--Ilvı-, = |10-11 - 0" + 0 [lellv S 10 0" [|v + ||0"||v,-- Since the event B, holds, we know the first term is upper bounded by /B--1(7), and since the largest cigenvalue of the matrix V upper bounded by A + TLL and ||0*]| < S, the second term is upper bounded by SvA TLZ. Hence, I10:-I1lv--1 is upper bounded by O(VT). Then one can substitute this bound back into Eqn. ( and this yields
[&llv 2 Ω
Vlg A.) )
1
(3)
Furthermore, by our design of the algorithm, the index of A, is not larger than the index of the arm with the largest empirical reward at time t. Hence,
A + log (1-1(7)110011
IA B
S log (1-1(7)
(4)
In the following, we set as well another free parameter I as follows:
d dlog2 T VT
and 7 = 72
(5)
A7 If | 2 A B-16)) by using Corollary with the choice in Eqn. 5 the upper bound of F1 in this case is (dd T). Otherwise, using the event Dj and the bound in deduce that for all T sufficiently

---

Published in Transactions on Machine Learning Research (04/2024)
large, we have || 2 Q
A (.) (AT)) Therefore by using Corollary and the "peeling device"
Lattimore & Szepesvári 2020 Chapter 9) on A such that 2- A 2-11+ for l == 2,,,..., . [Q] where
Q - -log2 I and I is chosen as in Eqn. 5 Now consider,
T
A
}
F 0
| 20
(1-1(7) log (T/A3))
[Q1
A 1 1(xxile 20
31-1(7) log (T (T) }} 1/2 < A. 52 2252-111
A
+0(1)+T++ E
t=1 1=1
IQ
1+1, 1/11xa11:21 20
2 21
+0
3r-1(7) (7) log(T' .22()
1=1 1=1
[Q1
22 (3r()) (2 log (1+ 2L2 221 (T( log(T 221 11+10
+70)+7++B
(6)
d
1=1
T (r2) log (1+ (23)(17) log( (so
241 0 ((13r(7) (1Br(1))ogg log(
50()) + TT +
AT
0(1 + 7T (Br(T) log(
log 1+ 1233(1)) log( loB((=))
(233(1))08( )
(7)
r
A
where in Inequality 6 used Corollary
Substituting the choices of and y in (5) into yields the A²
upper bound E E A. [[B,, Ct Di} 1[lxxell; 1 of the order O(dvT T). Hence
O(dVT log 7). Other details are fleshed out in Appendix C.2
For F2, since O2 and D. together imply that x1) 8 < E + (x),, then using the choices of ô and
E, we have (0--1 X() > A. Substituting this into the event B, and using the Cauchy-Schwarz inequality, we have
logT"
A Br 1 log T'
Again applying the "peeling device" on A, and Corollary we can upper bound F2 as follows:
FB TTTT+ d3r(7) log log (1+
12Br(T)logT)
(8)
A
Then with the choice of T and y as stated in (5), the upper bound of the F2 also of order O(dyTlogg T). More details of the calculation leading Equ. are in Appendix C.3
For Fs, this is the case when the best arm time t does not perform sufficiently well so that the empirically largest reward at time t is far from the highest expected reward. One observes that minimizing F3 results in a
tradeoff with respect to Fi. On the event Ct we can again apply the "peeling device" on (0" ; > (0,-1, 2+2 where q N. Then using the fact that Le,At Lt,a; have
such that 2 < 10 x²) (0,-1,2)) <
1
9²8²
log 3, 1 V-1
+ log (1
(9)
43, (
On the other hand, using the event B, and the Cauchy Schwarz inequality, it holds that
(9+ 1)8
|| | 2
(10)
2
2/33-1(1))
9

---

Published in Transactions on Machine Learning Research (04/2024)
If [ 2 Br-17)) the regret this case bounded by O(dyTlog T). Otherwise, combining Equ.
A3
(9
and Eqn. 100 implies that
1) exp (- 1)3
x 2
48c-1(7)
(q
Using Corollary 1 we can now conclude that Fs is upper bounded as
(d3r()) ( log (1 I. (2)
FB S TT O
(11)
AT2
Substituting I' and y in Equ.
5 into Eqn.
11
we upper bound Fa by Old T). Complete
details are provided in Appendix
C.4
For Fa, using Lemma with the choice of = 1/t? and Q = - log we have
T
Q
F4 E Σ
A.
1
B.}
5 TT
+
A
1 (2 <A A.522
t=1
t=1 [=1
T [Q]
T [Q]
x²
< TT +
Σ 2 1+ ((B,) 1=
STT+ + ΣΣ
1+ 2-1+1 < TT
2
+
3
Thus, F4 S O(dyTlog log T). In conclusion, with the choice of and 7 in Equ.
we have shown that the
expected regret of LinIMED-1 R = Ei= F; is upper bounded by Odd log T).
For LinIMED-2, the proof is similar but the assumption that (0",=t,a) 2 0 is not required. For LinIMED-3, by directly using the UCB in Of Algorithm | we improve the regret bound to match the saate-of-thh-ail Odd/Tlog log T), which matches that of LinUCB with OFUL's confidence bound.
6 Empirical Studies
This section aims to justify the utility of the family of LinIMED algorithms we developed and to demonstrate their effectiveness through quantitative evaluations in simulated environments and real-world datasets such as the MovieLens dataset. We compare our LinIMED algorithms with LinTS and LinUCB with the choice 1) 22)² (here 7 (1+2)= and L v2) for the synthetic dataset with varying and finite set and B.(7) (R/dlog((1 + t)(²) /20 (here 7 = + and L. /20) for the MovieLens dataset respectively. The confidence widths /3)(7) for each algorithm are multiplied by factor a and we lune a by searching over the grid 0.1, 0.2, 0.95, 1.0} and report the best performance for each algorithm; see Appendix G Both 7's are of order 0 as suggested by our proof sketch in Eqn. (5) We set C 30 in LinIMED-3 throughout. The sub-Gaussian noise level is == 0.1. We choose LinUCB and LinTS as competing algorithms since they are paradigmatic examples of deterministic and randomized contextual linear bandit algorithms respectively. We also included IDS in our comparisons for the fixed and finite arm set settings. Finally, we only show the performances of SupLinUCH and SupLinIMED algorithms but only in Figs. [ and [ since it is well known that there is a substantial performance degradation compared to established methodologies like LinUCB or LinTS (as mentioned in Lattimore & Szepesvári (2020) Chapter 22) and also seen in Figs. and 2
x = T.2. We set Be(7) (Rv3d
6.1 Experiments on a Synthetic Dataset in the Varying Arm Set Setting
We perform an empirical study on a varying arm setting. We evaluate the performance with different dimensions d and different number of arms K. We the unknown parameter vector and the best context vector as 0r x ( v T Rdd There are K suboptimal arms vectors, which are all
the same (i.e., repeated) and share the context [[1 742., Va
742..) T /
)1 e gd
10

---

Published in Transactions on Machine Learning Research (04/2024)
16
Regret
Regret
Regret
LinUE
LRIMED--1
LniMEDD-
SupLinMED
SupLinUCB
5000
5000
1000
1000
Time
10
(b) K 100
(c) K 500
Figure 1: Simulation results (expected regrets) on the synthetic dataset with different K's
20
20
30
20
15
15
Regret
Regret
Regret
LiNUCB
LhiMED-1
LinlMED-2
LinIMED-3
SupLinIMED
SupLinUCB
2003
(003
200
5000
10020
2003
42001
5000
5000
10002
2000
4200
6000
5000
10000
Time
Time
Time
(a)
(b) 20
(c)
Figure 2: Simulation results (expected regrets) on the synthetic dataset with different d's
where Zt, Uniform 00, 0.1] is iid noise for each t E [7] and [K 2). Finally, there also "worst" 1]_ First fix d = 2. The results for different numbers of arms such = 10, 100, 500 are shown in Fig. D Note that each plot is repeated 50 times to obtain the mean and standard deviation of the regret. From Fig. [ we observe that LinIMED-1 and LinIMED-2 are comparable to LinUCB and LinTS, while LinIMED-3 outperforms LinTS and LinUCB regardless of the number of the arms Second, we set 10 with the dimensions
vector with context 0,.,, 0,
2, 20, 50. Each trial again repeated 50 times and the regret over time shown Fig. 2 Again, we see that LinIMED-1 and LinIMED-2 are comparable LinUCB and Lin LinIMED-3 clearly perform better than LinUCB and LinTSS
The experimental results synthetic data demonstrate that the performances of LinIMED-1 and LinIMED- 2 are largely similar but LinIMED-3 is slightly superior (corroborating our theoretical findings). More importantly, LinIMED-3 outperforms both the LinTS and LinUCB algorithms in a statistically significant manner, regardless the number arms K or the dimension the data.
6.2 Experiments on the "End of Optimism" instance
Algorithms based on the optimism principle such LinUCB and LinTS have been shown to be not asymp- totically optimal. A paradigmatic example is known the "End of Optimism" (Lattimore & Szepesvari 2017 Kirschner et al. 2.21)). In this two-dimensional case in which the truc parameter vector 6" = [1:0]. there are three arms represented by the arm vectors: [1;0], [0; and [] - s; 2s], where & > 0 is small. In this example, it observed that even pulling a highly suboptimal arm (the second one) provides a lot of information about the best arm (the first one). We perform experiments with the same confidence parameter {,(1) (R /Rd /3d + f) /2)² as in Section 6.1 (where the noise level R 0.1, dimension d = 2). We also include the asymptotically optimal IDS algorithm Kirschner al. 2021 with the choice of 7) (,())
11

---

Published in Transactions on Machine Learning Research (04/2024)
UinGC
500
UnIMED-1
LniMED-2
LniMED-3
ID5
Rogjel
Rogjet
100
100
00
50
0.0
0.0
Time
160
Time
100
Time
105
0.005
(b) 0.01
0.02
Figure 3: Simulation results (expected regrets) on the "End of Optimism" instance with different e's
1.
3.0
0.0
Clok-Thruuh Rate
3.0
0.6
0.0
Clok-Through
Clic-Thoouhh
LinUCS
LinUCa LinTS
LinUCa
LinTS
0.4
0.4
LinTS
0.2
LinIMED-2
LinIMED-2
LinIMED-2
IDS
IDS
Time
Time
Time
(a) K 20
(b) K 50
(c) K 100
Figure 4: Simulation results (CTRs) of the MovieLens dataset with different K's
this is suggested in Kirschner et al. [2021). Each algorithm is run over 10 independent trials. The regrets of all competing algorithms are shown in Fig. with E 0.05, 0.01, 0.02 and for fixed horizon T 10
From Fig. 3 observe that the LinIMED algorithms perform much better than LinUCB and LinTS and LinIMED-3 is comparable to IDS in this "End of Optimism" instance. In particular, LinIMED-3 performs significantly better than LinUCB and LinTS even when E is of a moderate value such as E = 0.02. We surmise that the reason behind the superior performance of our LinIMED algorithms on the 'End of Optimism" instance that the first term of our LinIMED index is á (
which can be viewed as an approximate and simpler version of the information ratio that movtivates the design the IDS) algorithm.
6.3 Experiments on the MovieLens Dataset
The MovieLens dataset (Cantador al. (2011)) is a widely-used benchmark dataset for research in recom- mendation systems. We specifically choose to use the MovieLens 10M dataset, which contains 10 million ratings (from 0 to 5) and 100,000 tag applications applied to 10,000 movies by 72,000 users. To preprocess the dataset, we choose the best K E {20, 50, 100} movies for considcration. At cach time t, one random user visits the website and is recommended one of the best K movies. We assume that the user will click on the recommended movie if and only the user's rating this movie at least 3. We implement the three versions of LinIMED, LinUCB, LinTS and IDS on this dataset. Each trial is repeated over runs and the averages and standard deviations of the click- throthh rates (CTRs) as functions of time are reported in Fig. 4 One observes that LinDMDD variants significantly outperform LinUCB and LinTS for all K (20,50 50, 100) when
12

---

Published in Transactions on Machine Learning Research (04/2024)
time horizon T is sufficiently large. LinIMED-1 and LinIMED-2 perform significantly better than IDS when k = 20, 50, LinIMED-3 perform significantly better than IDS when k = 50, 100. Furthermore, by virtue of the fact that IDS is randomized, the variance of IDS is higher than that of LinIMED.
7 Future Work
In the future, a fruitful direction of rescarch is to further modify the LinIMED algorithm to make it also asymplotccally optimal; we believe that in this case, the analysis would be more challenging, but the theo- retical and empirical performances might be superior to our three LinIMED algorithms. In addition, one can gencralize the family of IMED-stylc algorithms generalized linear bandits or neural contextual bandits.
Acknowledgements
This work supported by funding from a Ministry Education Academic Research Fund (AcRF) Tier 2 grant under grant number A-8000423-00--00 and AcRF Tier grants under grant numbers A-8000189-01-00 and A-8000980-00-00. This research is supported by the National Research Foundation, Singapore under its AI Singapore Programme (AISG Award No: DISG2-PDD-2023--------25 08400),,-,,, and is part of the programme DesCartes which is supported by the National Research Foundation, Prime Minister's Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme.
References
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in Newral Information Processing Systems, 24, 2011.
Shipra Agrawal and Navin Goyal. Analysis of Thompson sampling for the multi-armed bandit problem. In Conference Learning Theory, pp. 39.1-39.26. JMLR. Workshop and Conference Proceedings, 2012.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In Inter- national Conference on Machine Learning, pp. 127-135. PMLR, 2013.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 17:235-256, 2002.
Dorian Baudry, Kazuya Suzuki, and Junya Honda. A general recipe for the analysis of randomized multi- armed bandit algorithms. Xiviv preprint arXiv:2003. 06058, 2023.
Jie Bian and Kwang-Sune Jun. Maillard sampling: Boltzmann exploration done optimally, arXiv preprint arXiv:2111000 01109290. 2021.
Tván Cantador, Peter Brusilovsky, and Tsvi Kuflik. Second workshop on information heterogeneity and fusion in recommender systems (HetRec2011). In Proceedings of the Fifth ACM Conference on Recommender Systems, pp. 387-388, 2011.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208 214. JMLR Workshop and Conference Proceedings, 2011.
Aurélien Garivier and Olivier Cappé. The KI-UCB algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th Annual Conference on Learning Theory, pp. 359 376. JMLR Workshop and Conference Proceedings, 2011.
Junya Honda and Akimichi Takemura. Non-asymptotic analysis of a new bandit algorithm for semi-bounded rewards. J. Much. Learn. Res., 16:3721-3233 -7761, 2015.
Johannes Kirschner and Andreas Krause. Information directed sampling and bandits with heteroscodastic noise. In Conference On Learning Theory, pp. 358 384. PMLR, 2018.
13

---

Published in Transactions on Machine Learning Research (04/2024)
Johannes Kirschner, Tor Lattimore, and Andreas Krause. Information directed sampling for linear partial monitoring. In Conference on Learning Theory, pp. 2328 2369. PMLR, 2020.
Johannes Kirschner, Tor Lattimore, Claire Vernade, and Csaba Szepesvári. Asymptotically optimal
information-directed sampling. In Conference Learning Theory, pp. 2827.2821. PMTR, 2021.
Tor Lattimore and Csaba Szepesvari. The end of optimism? an asymptotic analysis finite-armed linear bandits. In Artificial Intelligence ond Statistics, pp. 728 737. PMLR, 2017.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th International Conference on World Wide Web, pp. 661-670, 2010.
Haolin Liu, Chen- Yu Wei, and Julian Zimmert. Bypassing the simulator: Near-optimal adversarial linear
contextual bandits. Advances in Neural Informalion Processing Systems, 36, 2024.
Daniel Russo and Benjamin Van Roy. Learning to optimize via information-direeted sampling. Advances in Newral Information Processing Systems, 27, 2014.
Hassan Saber, Pierre Ménard, and Odalric-Ambryee Maillard. Indexed minimum empirical divergence for unimodal bandits. Advances in Neural Information Processing Systems, 34:7346- 7346,,7736,-- 2021.
William R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of samples. Biometrika, 25(3/4):285 294, 1933. ISSN 00063444. URL http://www.jstee org/staabee2333286
Michal Valko, Rémi Munos, Branislav Kveton, and Tomáš Kocák. Spectral bandits for smooth graph func- tions. In International Conference on Machine Learning, pp. 54. PMLR, 2014.
14

---

Published in Transactions on Machine Learning Research (04/2024)
Supplementary Materials for the TMLR submission T Indexed Minimum Empirical Divergence Algorithms"
" "Linear
A BaseLinUCB Algorithm
Here, we present the BascLinUCB algorithm used a subroutine in SubLinIMED (Algorithm 2
Algorithm 3 BaseLinUCB
1 a= 22 21K V. S 2 1: Input: 2/2:
V, La +Iee, JT,11 Sr,A,
3: b, = -ETE. Y AT
4: = %V=V bb
Observe K arm features 2t,1, 01,,:..,, JtKK E RRd
for [K] do
Wtaa = a T V. 21,
8: Yr.- = (0,, vr.a)
9: end for
B Comparison to other related work
Saber et al. 2021 adopts the IMED algorithm to unimodal bandits which achieves asymptotically optimality for one-dimensional exponential family distributions. Tn their algorithm IMED-UB, they narrow down the search region to the neighboring regions of the empirically best arm and then implement the IMED algorithm for K-armed bandit as in Honda Takemura (2015). This design inspired by the lower bound and only involves the neighboring arms of the best arm. The settings in which the algorithm in Saber et. al. (2021) | is applied to is different from our proposed LinlMED algorithms we focus linear bandits, not unimodal bandits.
Liu et al. (202)) proposes an algorithm that achieves Ö(VT) regret for adversarial linear bandits with stochastic action sets in the absence of a simulator or prior knowledge on the distribution. Although their setting is different from ours, they also use a bonus term L in the lifted covariance matrix to encourage exploration. This is similar our choice of the second term
1) in LinIMED-1.
C Proof of the regret bound for LinIMED-1 (Complete proof of Theorem 1
Here and in the following, we abbreviate 3e(7) as 3e, i.e., we drop the dependence of 3r on 7, which taken be per Equ.
C.1 Statement Lemmas for LinIMED-1
We first state the following lemmas which respectively show the upper bound of Fi to F4:
Lemma Under Assumption [ the assumption that (0" Tr,a) 2 for all 2 and a A., and the assumption that VAS 2 1, then for the free parameter O < T < 1, the term F, for LinIMED-1 satisfies:
d log(
L log(F=)) )+)()
F =
log 1+
(12)
r
2
With the choice T in Eqn.
F s o (VT
15

---

Published in Transactions on Machine Learning Research (04/2024)
Lemma 3. Under Assumption I ond the assumption that VXS 2 1, for the free parameter I < 1, the term F2 for LinIMED-1 salisfies:
d3r log T
log 1+ L2 log T
F2 s 27T + O
(13)
AT2
With the choice Tf as Eqn.
F2 (NTTlogg)))
Lemma 4. Under Assumption 1 and the assumption that VAS 2 1, for the free parameter <<'< < 1, the terma F3 for LinIMED-1 satisfies:
d3T log(T)) log 1+ L2BT (oB(T)))
F3 2TT O
(14)
AT
With the choice I Eqn.
F3 S o o @VT :
Lemma 5. Under Assumption 1 for the free parameter 0 < L < 1, the term Fa for LinIMED-1 satisfies:
F4 s TT(())
With the choice of T as in Eqn.
F1 S o (ddvTTie ooo T)
C.2 Proof of Lemma 2
Proof. From the event C and the fact that (0", 27) D. + 10 X,) A. (here is where that (0", .r,a)) 0 for all I and a); we obtain maxsc (0--1, H1,h)
Vlog7 ). For convenience, define A, == arg max (0-11 ax, as the empirically best arm at time step t, whore tics are broken arbitrarily, then use X, to denote the corresponding context of the arm A.. Therefore from the Cauchy-Schwarz Schwarz incquality, we have 1 [ 1 2 (8. X,) > (1 VlogT" Vlog )d, This implics that
(1 Vlog )4
)a
[& 2
110,111 1lvi-
On the other hand, we claim that 110-- [l can be upper bounded as O(VT). This can be seen from the fact that ||@,-Illv_-, 110,-1 l" lr [[v], $ 1 0" [|v ||0* Since the event B, holds, we know the first term is upper bounded by / (2)) and since the maximum eigenvalue of the matrix Vi-1 is upper bounded by A + TL2 and ||0*|| < S, the second term is upper bounded by Sv + TL2, Hence, is upper bounded by O(VT). Then one can substitute this bound back into Eqn. 2 and this yields
[ 2 2
VT (1
Vlog T )
1
Furthermore, by our design of the algorithm, the index of A, is not larger than the index of the arm with the largest empirical reward at time t. Honce,
A2 A2A
4. =
+ log (-)(7)][X
< log
(-)
B (1-1())
V-1
V=
16

---

Published in Transactions on Machine Learning Research (04/2024)
IT 1 v, 2
Be-1 by using Corollary and the "peeling device"
A2
Lattimore & Szepesvári
2020
Chapter 9)
A such that 2-1 < A 2 1+1 for ..., [Q] where Q
2-1++
logg I'
T
A
Do} 1 ||xoll v.= 2
A
E
T
A
[ixolle
2
A
(15)
3
Br-1
1=1
T
A
T
A
E
D 1
[Xel V,-1
2
1(4
$ H + E
1 1 [|xolliz=1
2
1 1f4 >
r
B
B1-1
1=1
1=1
T [Q]
A?
TT + E
A
|
2
1 < A. 52
B--1)
[=1 [=1
T [Q]
STT +E
2 1+1
1
1
| 2
2-21
BT
[=1
[Q]
1+1 Bd
BT
ST +E E
2
log
1+
2 21
A 2-21
1=1
[Q]
2 37
=TT + E
2
12d log
1
1=1
[Q]
22Q+3 12
< TT + E
2 12d log
1
A
1=1
22Q431288
-TT + (2 1). 24d3r1o0
1
A
48d3T log
(1+
8L
<T
XT2
Then with the choice of as in Equ.
A?
E
A 1 ( Cr D.) 1 |
2
8
t=1
48
81. 8T
dd
T
log 1+
log²
Ad log T
s 00 (o <dddTTlog33)
(16)
Otherwise we have |xille v-1
since A, S 1 Substituting this into then using the event D, and the bound in we deduce that for all T sufficiently large, we A?
3 then log Bi -1-1
Equ.
have 1x Q D._. ( lg(( Therefore by using Corollary 1 and the "peeling device" (Lattimore &
Szepesvári 2020 Chapter 9) on A, such that 2- < A, < 2-1+1 for 1= [Q] where r: 2- is free paramcter that we can choose. Consider,
A? A 1 (Br, Co D.) 1 i |
E
B
A (Br, D.) 1 1 1222219111 1 1/11xell2_
Ai Be-1
<
+ E A C., 1 ( > 2-1101
T
4
<
3-1
17

---

Published in Transactions on Machine Learning Research (04/2024)
A 01)) + + +
Σ
T
A
|
20
A
1 1 > 2-111
3 (T/ (T/ A?
1=1
+E Σ
A
11xx111= 20
A
111
B log (T/ TT))))
2-21
S 0(1) + 7T E
2
1
||x:ll 20
(T 221) B log
[Q]
T
2 2-21
0(1) + EE
2
1+1
| 2 .2
B log(T (T' 22
1=1
t=1
[Q]
2L2 22t (T .221)
$ 0())+T++
1+1
dBr log(Tr 22t) log 11
1=1
01)) +TT +
[Q1
2 o
T d3, log( p2 1oglog (I+
1.2 log (f( )
AT2
1=1
d3r log( T r2)
Br log( (ox) (()2))
< 0()1)
+011+ +T
log (1
AT2
This proves Equ.
12
Then with the choice of the parameters as in Eqn. 15p
T
A. 1 C, D.) 1 if |Ixi1 <
A?
E
B
<0 + dv dvTlog T+ 0 d33 log
T
T
L L3B
T2
log
1+
logg
log
T
dl
log
T
Ad2 log" T
de dFlog"
s <0(dTTlog2 T)
Hence, we upper bound Fj as
F E
Σ
T
A .
1(B,, Di) 1 1f |xilR 2
A
+ +E
T
A 1 [B, C,, D.) 1
- 1(IxIR
A
B-11
B
1=1
1=1
7 (ddTTlog
T) +
<0(dVTlog2r)
which concludes the proof.
C.3 Proof of Lemma
Proof. Since Ct and D, together imply that (0",z)) - e + (0), then using the choices ó and s, we have (0-11 - Xe) > A. Substituting this into the event B, and using the Cauchy Schwarz inequality, we have
'logT'
A?
2
B,
1 log
Again applying the "peeling device" on A, and Corollary
1 we upper bound F2 as follows:
T
A?
FB < E A
>
B log T
1=1
18

---

Published in Transactions on Machine Learning Research (04/2024)
QQ1
A B log T
TT + E
A 1
|
1 < 22
1=1 1=1
ST + E
Σ
T
[Q]
2 1+1 1 1111x
2 2-21
BT log T
t=l 1=1
[Q]
(1+ 22 L2Br Br log
< TT + E
2-1+1 2 6dgr 7) log
1=1
[Q]
22101+1 1.23r log T
ST +
2 12d33 12d8r(1og T) log
1+
2
L2 log T
TT + (2
(l0g) log
1+
A
48d3T logT T
1 8L2 BT log
TT
log
r
AI
d33 logT
Br log T
TT + 0
log
1+
This proves Equ.
13
Hence with the choice of the parameter I' as in Equ.
F2 $ avTloo" + + O ddv (dVTlog?
s so =0(0v
di @dddlooo)))
C.4 Proof of Lemma 4
Proof. For F3, this is the case when the best arm at time i does not perform sufficiently well so that the empirically largest reward at time is far from the highest expected reward. One observes that minimizing Fa results in a tradeoff with respect to F.. On the event Ct, we can apply the "peeling device" on (0", - (0-11, such that g+1 < (0", x²) (0.11, < 2 where N. Then using the fact that IE S Tea we have
q282
log
+ log B
(17)
3 X1
43
| vr
V=!
VZl
On the other hand, using the event B, and the Cauchy-Schwarz Schwarz inequality, it holds that
(q+1))
(18)
2 2/Br-1
If 1|xx,122 v 2 A?
the regret in this case is bounded by Odd/Tlog T) (similar to the procedure to get from + 2 0, then combining Equ. 117 and Equ. 18 x7
Equ. 15 to Eqn. 16
Otherwise log Be-1l X.
log
implies that
(g + 1)222
q2
|x - 2
exp
4,,-1
(g 1)2
Notice here with VĀS 21, 1, |X
47
< 3
1
< 1, it holds that for all g E N,
9i
(q + 1)
y2
exp
<1.
(19)
4
(q + 1)2
19

---

Published in Transactions on Machine Learning Research (04/2024)
Using Corollary 1 one can show that:
T
4
A 1 (B, 1 |xxlll <
Be-1
t=1
TT +
T
[Q1
A (BI,Ci) 1
11x:1R
A
} 1 A 2
B0-1)
t=1 |=1
[
1
- 0/
Ai
S Σ Σ Σ
A 1(B)) 1
8 < 10
x1) - 10
2
3-1
t=l
.1 (1 < T Q0
2 2 1+1
14+1)
}
STT+ Σ
A
12 v.-
2
exp
1 <,, <A.50 52-141
45,-1
(q 1)2
1=1 1= 1
T Q
q²
3 12 < A. 22-1111
=TT+ Σ
A 1
12
12 | P2 2
43:-1 log T
exp
(g+ 1)2
T Q
2 1+1, 1/1
1112
(4 1) 2 21
(9 ( 1)2 11))}
d²
TTT +
Σ
| |
=
exp -
4, 1og.ogT T
t= [=1 q=1
x2
92
[Q]
exp
(9+1)²
22 SLLBrr log
exp
(9+1)²
TT +
2 141, 22 (00g3
-log
1
(q + 1)²
A
(a+
1)²
1=1 q=1
g²
[Q] 00
exp
(9+1)²
22t+1
L3 log T
TT + Σ
21 24dg3((ogg] T)
log
1
(q + 1)2
A
9=
[Q]
1+ 1 log T
00 exp
(0+1y>
= =TT+ +
2 (ldgT( log
(g + 11
[Q]
221-1 1.2 log T
ST TT +
21 24dBr(log T) log
1
(1.09)
1=1
[Q1
221-1
Br log T
TT +
21 27d33 T) log
1
X
1=1
[
221
L3 log T
<TT+ +)
2 27d3r log
1
X
216d3r Io
(1+ 8L2 Br log
< (T++
log
r
2
1=1
TT 0
dBr log T
log (1+
I Br TT
(20)
r
2
Hence
F3 = Σ A. 1
T
BB, [.). - 1 1 [IXxIRR1 < 3,
4
+ + A. (B,, C.) 1 /11xa1
T
A?
2
B
1=1
d3r log
(1+ -13 )) + 27T + 0
d3r Iog log (1 (1+ Lr3r log
< 0
r
2
20

---

Published in Transactions on Machine Learning Research (04/2024)
dir lTg(T)
I.2 BT log(T)
$ 27T +0
log 1 11
r
2
This proves Equ.
14
With the choice I as in Equ.
dv dr log 1
TL Br log T dd2 log" T
F3 s 2o
a T+O
dlog T log? T+ dvT log T)
= =o(VTTlog31) r)
C.5 Proof of Lemma
Proof. For Fi, the proof is straightforward by using Lemma ! with the choice of y. Indeed, one has
T F4 = E
T Q
A
1 (B:}
- TT + E
A
(2 < A. 11
t= 1=1
T Q
Q
T [Q]
$ TT + E
1+1 [B
< +
Σ
1+ P(B.)
STT+
Σ
2 1+1
t=1
1=1
T T-T
7²
TT
TT
TT
= 0
t2
3
With the choice of I in Eqn.
F4 < dVT log T 011)
< so (ddTTlo ddVTlog' T
C.6 Proof of Theorem i
Proof. Combining Lemmas
2 3 4 and 5
Pr Fi + F2+ F3 + Fa
o d r) + 00 (dVTToog' + r) + +0(o/TToog'
< 0 dv dv log
doog r)
= dv dVTToog T)
D Proof of the regret bound for LinIMED-2 (Proof of Theorem 2)
We choose and I as follows:
/d3r log
=
r
(21)
VT
21

---

Published in Transactions on Machine Learning Research (04/2024)
D.1 Statement of Lemmas for LinIMED-2
We first state the following lemmas which respectively show the upper bound of Fi to F4: Lemma 6. Under Assumption 1 and the assumption that VÁS 2 1, for the free parameter < 1, the term F1 for LinIMED-3 satisfies:
ST + O
dsrr log r
1. log T
log
X
Lemma 7. Under Assumption 1 and the assumption that VXS 2 1, for the free parameter 0 <T < 1, the term Fg for LinIMED-3 satisfies:
TT O
d3r log T
log 1 12
r
2I
Lemma Under Assumption term F3 for LinIMED-3 satisfies:
1 and the assumption that VXS 2 1, for the free parameter <T < <1, the
d3r log log (1 37 log bll + @ TTog Tog
1 (123rlogg log X
1 ))
F3 57T + O
T
AT
Lemma 9. Under Assumption 7
with the choice of = as in Eqg.
for the free porameter 0 < P <
the term Fa for LinIMED-3 satisfies:
F4 S
D.2 Proof of Lemma 6
Proof. We first partition the analysis into the cases A, + Ae and Å, = Ae as follows:
F E A. CD)
1=1
A. C,, 1 {A.+
+E Σ A. (B. C, -1 A1}
B
Case 1: A + Ar, this means that the index of Ag is Ie,A, = 11-111
+ log 0.-1 [x,] v=1
1
Using the
y-
fact that Le,, S L, we have:
2 L.A.
1
Te B X,
+ log
Br- Xx, 112
V=
< log T' A log
3 11-111 11,11
< log
Therefore
1,1
+ log
E log T
(22)
B X1 11
| v=1
X₂
vi=
22

---

Published in Transactions on Machine Learning Research (04/2024)
1x I
2
A7 Be-1"
using the same procedure to get from Eqn. 15 to Eqn. 16
one has:
T
D.) 1 1 + Ar) 1 {f [1xill 2
A
E
D 1 1B,,
_,
A
E
D: 1
Br-1
1=1
48d.3 log
8122TT
TT
11
T
AT2
dār log
Br
TT +
1+
r
AI
Else if ||Aiel? 1/-1
<
AL. B
this implies that log
B Xx
> log 1
33
2 0.
Then substituting the event
V,1
Dt = (ALA. 2 into Equ.
22 we obtain
< log T'
X,
2
With VĀS 21 1 we have BL-1 2 1, then one has
c²
[|allle 2
3--1 log T
Hence
T
A?
E
D.
1
Cr.
Br,
3
T
E²
<
E
A 1
|
v
Bz-1 log T
t=1
With the choice of = (1 device" on A. yields
2
Mr.
when T 2 149- > exp(5), E >>
Ag
to then performing the "peeling
Vlog oog T
T
2²
E
A
[Xell
12 1-1
2
114: 13
[Q]
< 149 + E Σ
Σ
A. 1 { 2-1 < A, 5 111 |x >
2-1
E² 3 log T
1=1 1=1
[Q]
T
01) + E
2
1+
|xil| /= m=
>
3r-1 log T
t=1
[Q]
T
2-21
< 001)+ E
2-141
141
Σ
|
> 100,3 log T
1=1
[Q]
221
200 ,r log T
< 0(1 + E
--111 2
(log T) log 1+
A
23

---

Published in Transactions on Machine Learning Research (04/2024)
QQ
22[2].
2000. log T )
$ 0(1) + E
2 (log T) log 1
A
i=1
< 01) + 4 log T
800L2 87 log T
log 1
X
Considering the event {A, < rJ we can upper bound the corresponding expectation as follows
T E A 1
E²
T
|
2
114.
<
< Σ
A
1(4.
<T TT.
log
t=1
t=1
Then
A
E
A
Ar, Bes Cr, Cr, Ar 1x
B--1
T
6²
<
E
D
||x
Be-1 log T
1=1
E²
A 1
||x:I| 2
1 1(4; 11}
Be-1 log
1=1
T
E²
E
Σ
A 1
||xalli 2
114 < <T>
3r-1 log
t=1
4800d3T log T
log (1+
800L2 BT log T
$ 0 7T +
r
AI
Hence
T
E
A 1 Bi, C.
T
A?
E
A 1 Br, Cr, A+ Ar, 1x!l
2
B
1=1
A
+ E
A 1 Cr, Dr, A. Ar, |xall/
B
1=1
dBT log
1+ L.3r
4800d log T
800L? Br log T
< + 0
+0(1 +
log
1+
AI
21
d,3T log T
L r log T
STT+OL
log
1
XT2
Case 2: If A, = AG, then from the event C. and the choice 5 =
A.
we have
VlogT
00-1-0-00 (1 Vlog T
A.
Furthermore, using the definition of the event Bi, that implies that
)2
Vogg
B
When T> 8> exp(2), (1
Vlog7 ا )2 > 1 then similarily, bound this term by O d3r
log(1 + 4//7)
To
24

---

Published in Transactions on Machine Learning Research (04/2024)
Summarizing the two cases,
d3T log'T
B2 log I
P 0(1) TT +0
log 1+
AT2
dB log T
L2 Br log T
TT + +0
log
1+
2
D.3 Proof of Lemma 7
Proof. Recall that
T
F2 =2 = E Σ A. 1 (B,,
From Ct and De, we derive that:
(0", (,, e (0.-1, X,))
With the choice 5 Vlog T
D., we have
Vlog T
(0.1 0r Xx)
(23)
log T
Then using the definition of the event B, in Equ. 23 yields
3 log T
Using a similar procedure as that from Equ. 15
Eqn.
16). we can upper bound Fg by
d3r log
L² log
F2 S TT + 0
log 1
r
A1
D.4 Proof of Lemma 8
Proof. From the event C. which is maxseA, (0r-1, S (0",,')) - 6, the index of the best arm at time can upper bounded as:
Iea; (10', x0)))))) - 8- (00-1,
1
+ +lo
Br ||> v
B B1-1|1=711 v
Case 1: Tf A, * Ae, then we have
1,,0 LeA. 2 log 3, X,
Suppose 2tto < (0 x;)) - (0,-1, < 2t28 for a E N, then one has
g282
log 3--1 Xell [i
E 4,,- x v=
log
(24)
3
25

---

Published in Transactions on Machine Learning Research (04/2024)
On the other hand, on the event Be,
(g + 136
b 2
(25)
B
A7 Be-
If
2
using the same procedure from Equ.
13 to Equ.
16
one has:
T 1 (B. 0.) 1 {( + A1)
A
E
A
2
31-1
t=1
A7
E
A. 1 11x.111-11 >
31-1
48dBT log
8L
TT
1+
AI
dBT
L'
TT +
log
1+
T
AT
Elsc if [xolle
Af 1
this implics that log ae_ 11
log 1 0. Then combining Eqn. 17
24
and
Equ.
25
implies that
(9+ 1)28²
q² (q + 1)2
| v 2
exp
41,-11
Then using the same procedure to get from Equ.
19
to Eqn.
20
we have
T
A?
A 1 C2) - 1 |1xile
A # A
3-1
dBr dog log T
1.2 Br log T
< TT + 0
r log (1+
(26)
2
Case 2: A. Ar. If [ v= 2
A
using the same procedure to get from Equ.
15
to Equ.
16
one
has:
T E
A
1 BB C.) 1 ( Ar
1
[|xelle, 2
A?
B2-1
1=1
A7
<
E
A 1
|x..12 >
8
1=1
48d.T
8L2BT
< TT
log
1+
r
2
1.2
= TT +
log
[+
Elsc |X,, 1- <
oi B
implics that log
1
> log A; 2 0.
8..1 1x11
y-1
26

---

Published in Transactions on Machine Learning Research (04/2024)
If log 9 | 1-1
log T, then using the same procedure to get from Equ.
24 to Equ.
26
we have
A?
T
Σ A. . 1 Br, CB, -1
Ar = Ac, log 3e [x
log
3r-1
Br-1
dog.oooT
L B2
TT
log
1+
r
A
If log a. X|| !--
2 log this means the index of A is I log T', by performing the "peeling
device" such that 2t
& (0", xt) - (0.-1.27) < 2220 for g E N, we have
2
q²0²
log T S
+ log
(27)
4/2 17 V=1
Br 1
On the other hand, using the definition of the event Bi,
(g + 1)6
| 2
(28)
2/ 3
Combining Equ. 27 and 28 we have
2 2xxp( 2[4+11
8
(1 11+1)v7
Then with 5 A.
"
this implics that
2/log T e'exp( 2[
(q 11+1)VT
vx On the other hand, from 5 VB-il+/lly S B
L
we have g 411
21 2 B
log T
Hence,
VAA.
T
A. 1 Be, ..
A3
,. A,, log
1
2 log Du 2T
31-1"
11-11 V
21. Pr log
2 T expl 21
<
E
Σ A 1 A <
(a+ 1)
2ol T exp( 11++1
Σ
<
(q 1)vT
1=1
log
2 T Tlog T exp(
2(
E
q a+1
Pog VXF
2 2e T TogT
q 4+1
27

---

Published in Transactions on Machine Learning Research (04/2024)
2LL/oog
< 2vee Tlg Togolog log
VAI
0o TTog Toolooog log
Br log 21
Summarizing the two cases (A, + At and A, At), we see that F33 is upper bounded by:
dBT
17
)) +
d log T
log (1+ 12 log T
F3 <T +0
log
1 XT
+TT+0
+0
r
I
AI
der
I2232 3T
d3y d:3ylog log T
12 log T
TT +
log
1+
-T
log (1+
T
A
2I
L2 log
TT + 0 1o log
XT
[d8r dog
logT
B² log 7) )) + +
(123rl007
(I2 log T X
))
S 5TT + +0
log (1+
Toog log
r
2
D.5 Proof of Lemma g
Proof. The proof of this case is straightforward by using Lemma 1 with the choice 7 2=
T
F4
E
A
{B.}
t=1
T
T A. 1 [ A. +T Σ
E
A. . (B.
[=1
1=1
T [Q]
<T + E
A, 1 [B,, A, 22
[=1
[Q]
TT E
2 2-1 2-141.1 (B.)
[=1 1=1
[Q]
ST +
2 1+1
Σ
P P
1=1
[Q]
-T +
2
1+1
1m1
< TT + (2 r)
<T + 7²
3
TT 0(1)
D.6 Proof of Theorem 2
Proof. Combining Lemmas and with the choices y and T in Eqn. 21 is bounded follows:
the regret of LinIMEDD2
Rr F
Fg
Fg
F4
28

---

Published in Transactions on Machine Learning Research (04/2024)
d,3T d.3 log T
I.2 Br log T
d log T
3, log
TT +
log
1+
+ TT +T
log 1+
r
A
r
A
d3r log T
By log T ))
L² log T)
+5T +0
log
1+
O
Vol flog
r
2
Al
+ +TT+
< STT + =0
d3r -0 log T
L2 1
T)
1) 0 T Too Tlog
12 log T
log
1+
r
212
2I
8/ Br log T T VdT (1+ Ad ))
TL
+ 0
TL Ad T
8 dT
VTlog Tlog
8dv Cddvllogs log T O (oVTVoogg) T) +0 co(TTlog /TTlog²1 T)
so d dVTlogg )
E Proof of the regret bound for LinIMED-3 (Proof of Theorem 3
First we define or as the best arm in time step such that of arg max "0", 21,a), and use x; == zt,o denote its corresponding context. Define Å, == arg max,eA, (CB.(a). Let A. == (0"x);) - (8", (x) denote the regret in time l. Define the following events:
By = 1100-11-0 - 00l S (B)1(1))) DZ== (Ar., >c}
where is free parameter set be A in this proof sketch.
Then the expected regret RT = E ET t=1 A can be partitioned by events B,, D2 such that:
T
T
T
PC = E
A 1 (B,
DJ) + A Dr
Br,
A
B
t=1
t=1
1=
F3
For the F1 case: From Dj we know Ar + Ae, therefore
A L.A. LAA, 3
1
log
(29)
3,
Xx
From D2 and I,A, I I,A, S log
we have
maxaEA: 23,0'
C
I.A. < log
(30)
E2
Combining Eqn.
29 and Eqn. 30
A A.
C
log 3e-1 ||
< log
3
Xx V
X1
V-
Then
A2 1,1,
< log
Xell
(31)
B 1 X2
29

---

Published in Transactions on Machine Learning Research (04/2024)
I 1x
2
A7 Be-1"
using the same procedure from Equ. 150
Eqn.
16
one has:
4 B
E
A
[B,, D1)
1
|1x:1l;;
tm
A7
E
A. [1xall
2
3,-1
48d log
8T
TT
1+
AI
dBT
Br
TT + +0
log
1+
r
A
Else || v-1 Bi-1 ,his implies that Be-1l1Xrilp/-
Ai
<
A2, plug this into Equ.
(31
and with the choice of
A: and D/, have
c
A
log(9C)
93,
X2
1,
Since 2 1 is constant, then
A
| v
98,-1 (9C)
Using the same procedure from Equ. 15
to Equ. 16
one has:
A 1 (B, DJ 1 |IXIIP
A?
E
3
A 93,-1 log(9C)
E
A. 1
(d3 [d3
log C
L log C' ))
+
log 1+
r
XI
Hence
(1rr log
1.2,r log C 1)
Fi < 27T + +0
log
1+
(32)
r
2
For the Fg case:
Since the event B; holds,
max UCB.(a) 2 UCB,(a)) (0-1,,2)) + - + (1 aEA:
(33)
On the other hand, from Dí we have
max UCB.(a) s UCB.(A) +c= (0-11,1,) + X aE,A.
Xelyy, te.
(34)
Combining Eqn.
33 and Eqn.
34
(0',))) < (i) + / B B +E.
Hence
4. - E
(8.- - 0* X,) / B /
30

---

Published in Transactions on Machine Learning Research (04/2024)
Then with 3
4 and B₁, we have
م S 22
therefore
A
|
2
9
Using the same procedure from Eqn.
15
to Eqn.
16
one has:
d3T
1.2
AIS ))
F2 < TT
+ 0
log
1+
(35)
r
For the F3 case: using Lemma with the choice == :
T
F = E > A. 1 {B.}
tm1
E
A 1
By. A. <
+ Σ
A 1 [B
1=1
1=1
T [q]
< <T
E
A 1
B 2 <
A. 2--
1=1 l=1
Σ> [Q]
+T E
2
1
{BB}
[Q]
$ TT
Σ
2
1+1
P
B
1=1
[Q]
7
TT +
2
6
[=1
<T + (2-
2²
<T
3
TT + 0(1)
(36)
E.1 Proof of Theorem
3
Proof. Combining Equ.
32
35
366
with the choices of 7 # and r
3r VT
and C > 1 is constant, the
regret of LinIMED-3 is bounded as follows:
Rr = Fi + F2 + Fg + F4
d3r log C 4TT +
1.2 log C 1) +
d3
1 x )) + 0(1)
1.2Br
log
1 +
log
r
2
r
lo2 C'
doT log
1
A
o dv (dVTlog(TT)
This completes the proof.
31

---

Published in Transactions on Machine Learning Research (04/2024)
F Proof of the regret bound for SupLinIMED (Proof of Theorem 4
Define 8 E [[og T as the index of s when the arm is chosen at time t. For the SupLinIMED, the index of arms except the empirically best arm is defined by Itaa
A
2 llog(w whereas the index of the empirically best arm is defined by 11, log(22) A (-2 log( A))) where Ai arg max dE 10% xr,a). Define the index of the best arm at time ai =- arg max (0", .Tr,a)
1,
Remark 1. Here the upper bound we set for the inder of the empirically best arm is log(2T), which is slightly larger than our previous log T (Line 10 in the LinIMED algorithm) since in the first step of the of the SupLinIMED algorithm or, more generally, the JupLinUCB-type algorithms, the width of each arm is less than 1. as a result, the indez of each arm is larger than log T.
/T.
Let the set of time indices such that the chosen arm is from Step (Lines 6-9 Algorithm 2 be Vo Then the cumulative expected regret of the SupLinIMED algorithm over time horizon T can be defined by the following equation:
Rr = E
Σ 10", It.a; - Xx) + LIE%
Σ 14
10 Ft,at Xz)
(37)
Since the index has not changed in Step (see Line in Algorithm
2 the second term of the regret is For the first term, partitioned it
the same in the original SUPLinUCB algorithm of Chu et al. 2011 by the following events:
B₁ =
n
100-0; - 24, I
a
wi.a
and
tE[T], (log []
D. = Ai 2 e
where a 2 In 2TK as in the SupLinUCB (Chu et al. 20111- We choose y = 222 throughout. Furthermore, 8 is the 0 obtained from Algorithm with Ve as the input, i.c.,
-I++t
0: = Ia+ Σ IT,,A T.AA) TEV?
Σ TEW;
IT.AA
Define A : (0", ,t,a; - Xx) as the instantaneous regret at each time step t. In addition, choose e = A the definition of Dr. Then the first term the expected regret in (37) can be partitioned by the events B, and Dj as follows:
Σ 10 Tt, Xx)
=E Σ A. LIEW
(B,, Dr)
+
Σ A.
1 (B, D.}
Σ A. 1 {B.} LIEV
LLE
LIE
=
=:Fa
=:fa
We recall that when & Vo, w < VT for all E A...
To bound Fj, we note that since B, occurs, the actual best arm of A., with high probability (1-ylog² T) by Chu et al. (2011 Lemma 5). As such,
max (0 (r,a) 2 '0 xr,a;) 2 (0", xx,,;) aeAr,
a a
a Wi,a; 2 (0", (0,,;)
VT
32

---

Published in Transactions on Machine Learning Research (04/2024)
where the last inequality is from the fact that = 222 and a = / 2TK 2 1 Flse if, in fact, the best
of $ As, the corresponding regret in this case is bounded by:
T
E Σ A 1f 1
SE
A.
1 1at $ An.)
t=1
ai & Ace)
$ E
1=1
P(a & As.)
ylog* T
log" T
21
π
log" T
12
(A )2
Case 1: 1f A; + Ar, this means that the index of A₁ is 4.A.
+ log a² |
Using the fact
that Tr,,, S 4.4; we have
(Â )2
+ log
S 2log
a² xell V.
a² x
v,
Then using the definition of the event Dr and the fact that (w = a² 1x
S 7, we have
A < 9a² [x logT < 9log T
T
3/ log' VT
Hence, A <
Therefore Fj in this case is upper bounded as follows:
A 1 (B,, (., 1 {Ai+AA + faz E Au
3 T
E Σ
SE
S <3/TlogT
VT
LIE
LIEOO
Case 2: If A; As, then using the definition of the event B,, we have
2
2 VT
(6
X,) (x) max (0'; (0,=)) 2 (0", )(,,5) aeA.,
(0),,,)
+A,
VT
therefore since event B, occurs,
3
A s (0 - 0" X,) +
< VT
VT
Hence Fj in this case is bounded as 2/T. Combining the above cases,
=² log2 T < O(v Tlog Tog
Fi < 33 + 3/T +
12
33

---

Published in Transactions on Machine Learning Research (04/2024)
To bound F2, note from the definition of B, that
max (t,,) 2 (0,', (1,,;) 2 (0", ((,;)) - 2 aed.,
VT
then on the event D,,
S max (0," st,a) <8+ <8) = A. aEAr
"0,,
+ (1))
VT
3
therefore
3 3
2
A, < 2
(0: - 07, x1) +
$
VT
2
Hence
F2 = E
Σ
A, 1 (B,,
1 ffoz Aui
+R
Ec..i.B. ..f ( A..)
LIEV
LIE
T
+ n²
$ E
A 1
Brs Di}
log² T
12
T
9
+ π
E
1 (B,,, D
log" 2 T
2/T
12
9
π²
T
log 2T T
2VT
12
9 T
n²
log* T
2 12
- O(VT)).
To bound F3, we use the proof as in of Chu et al. 2001
Lemma 1), which is restated as follows.
Lemma 10. For any a E [K], 8 E [[log T1, / E (T),
P 100 - 8; r(,)l
>
a a+1 1
Wia
S 7
TK
where a / In 2TK 7
Then using the union bound, we have for all e [T], e [[log T"], for all a E [K],
PP B.] =P
U
1000 0r st,aa,a)
a + 1
wiaa
sE(T), [[EK]
a+1 w
Σ
P
1100
2(,))
<E[T] aE| log 27) [E[K]
< (TK(1 + log T
7
TK
= 71 + (ogg)
34

---

Published in Transactions on Machine Learning Research (04/2024)
With the choice 7 2/2 and the assumption
D 1,
F3 = E
Σ
A. 1 {Bi)
LEE Wo
T
P Bi]
+ log
212
(1 + log T)
12
Ollg
Hence the first term Rr in 37 is upper bounded by:
E
(0" Ft.a; Xi) O((T) Olog + 0( T
LeVo
o((TTlogT)
On the other hand, by Chu ct al. 2001 Theorem 1), the second term in Ry in 37 is upper bounded as follows:
E
Σ 0 Ftaa
Xx)
<o(vaT log'
Hence the regret of our algorithu SupLinIMED upper bounded as follows:
Rr s o[Varlog"((T))
This completes the proof of Theorem
G Hyperparameter tuning in our empirical study
G.1 Synthetic Dataset
The below tables are the empirical results while tuning the hyperparameter a (scale of the confidence width) for fixed T = 1000.
Method
LinUCB
LinTS
LinIMED-1
LinIMED-2
Lin[MED-3 (C
30)
0.5
0.55
0.6
0.2
0.25
0.3
0.15
0.2
0.25
0.2
0.25
0.3
0.15
0.2
0.25
Regret
7.780
6.695
6.856
9.769
9.201
12.008
24.086
5.482
6.108
4.999
4.998
7.329
25.588
2.075
2.760
Table 2: Tuning when K 10, =
Method
LinUCB
LinTS
LinIMED-1
LinIMED-2
LinIMED-3 (C
30)
0.5
0.55
0.6
0.1
0.15
0.2
0.2
0.25
0.3
0.2
0.25
0.3
0.2
0.25
0.3
Regret
7.203
6.832
7.423
34.221
7.042
7.352
6.707
6.053
8.458
6.254
4.018
7.013
4.407
2.562
3.041
Table 3: Tuning when K 100, d=
35

---

Published in Transactions on Machine Learning Research (04/2024)
Method
Lin
Lin'T'S
Lin1MED-1
Lin
LinlMED-33
30)
0.5
0.56
0.1
0.15
0.2
0.15
0.2
0.25
0.2
0.25
0.15
0.2
Regret
7.919
5.679
7.063
69.955
6.925
7.037
24.393
5.625
6.335
6.335
4.831
7.040
41.335
1.936
2.250
Table 4: Tuning a when K 500, d
Method
LinUCB
LinTS
LiaIMED-1
LinIMED-2
LinIMED-3 (C'
30)
0.45
0.5
0.55
0.15
0.2
0.1
0.15
0.2
0.1
0.15
0.2
0.1
0.15
0.2
Regret
9.164
9.094
14.183
14.252
9.886
14.680
19.663
6.463
10.643
15.685
5.399
8.373
8.024
2.062
3.342
Table 5: Tuning a when K = 10, d
20
Method
LinUCB
LinTS
LinIMED-1
LinIMED-2
LinIMED-3 (C
30)
a
0.25
0.3
0.35
0.1
0.15
0.2
0.05
0.15
0.1
0.15
0.2
0.05
0.1
0.15
Regret
7.923
7.085
10.981
14.983
9.565
19.300
58.278
6.165
9.225
8.916
8.575
13.483
142.704
2.816
3.497
Table 6: Tuning a when K 10, d 50
We run these algorithms the da dataset with different choices of a, we choose the best with the corresponding least regret.
G.2 MovieLens Dataset
The below tables the empirical results while tuning the hyperparameter (scale of the confidence width) for fixed T 1000.
Method
LidUCB
LitTS
LmIMED-1
L-1NEDD-2
LinMMED33 [C =
30)
IDS
CTR
0.608
0.675
0.608
0.615
0.706
0.679
0.740
0.823
0.766
0.740
0.823
0.708
0.713
0.742
0.090
0.655
0.728
0.714
Table 7: Tuning a when = 20
Method
LidUCB
LinTS
LinIMED-1
Li
LiuIMED (C
30)
1DS
0.75
0.8
0.85
0
0.05
0.1
0.1
0.15
0.2
0.05
0.1
0.15
0.05
0.1
0.15
0.3
0.35
0.4
0.704
0.713
0.517
0.646
0.048
0.608
0.595
0.608
0.608
0.651
0.007
0.717
0.649
0.643
0.006
Table 8: Tuning when K = 50
Method
LinUCB
LinTS
LinMEDD-
LiiNEDD2
LinIMED-3 [C
30)
CTR
0.721
0.754
0.745
0.487
0.674
0.588
0.682
0.729
0.594
0.687
0.729
0.594
0.689
0.705
0.594
0.684
0.739
0.695
Table 9: Tuning a when = 100
We run these algorithms on the same dataset with different choices of and we choose the best a with the corresponding largest reward.
36


Reviews:
[{"review_id": "VV5Tsd9DNr", "reviewer": "Reviewer_DYKa", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n1. The first linear extension of the IMED algorithm.\n2. Experiments confirmed that LinIMED significantly improves on LinUCB and Linear Thompson Sampling in the End of Optimism instance. Moreover, experiments with real data using MovieLens were also conducted.\n3. The paper is easy to follow and well-structured and explained in a short length. \n\nWeakness\n\n1. The LinIMED itself seems to be a fairly simple method since it uses the similar confidence intervals of [Abbasi-Yadkori et al. 2011] and essentially the UCB is instead changed to IMED, which are not many novel techniques. The theoretical analysis is also just an application of ideas already used in existing studies.\n\n2. Missing related work:\nIndexed Minimum Empirical Divergence for Unimodal Bandits (NeurIPS 2021)\nHassan SABER, Pierre Ménard, Odalric-Ambrym Maillard\nhttps://proceedings.neurips.cc/paper/2021/hash/3c88c1db16b9523b4dcdcd572aa1e16a-Abstract.html\n\n3. No distribution-dependent regret bound is provided. Also, there exists a good summary of adversarial linear bandits by [Liu+NeurIPS2023]:\n Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits\nHaolin Liu · Chen-Yu Wei · Julian Zimmert\n\nWould it be great if the authors could add a comparison with this literature, though the submitted paper considers stochastic loss and adversarial action sets? ([Liu+2023] focuses on stochastic action sets, if I am not missing)\n\nQuestion: Asymptotically optimal is not achieved, but where do you see the difficulty in achieving it?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this study, they proposed the first Indexed Minimum Empirical Divergence (IMED)-based algorithm for linear bandits and provide \\tilde{O}(d \\sqrt{T})-regret bound where d is the dimension. The algorithms can deal with time-varying action space A_t at each round t. They also consider SupLinIMED, a variant of SupLinICB (Chu et al. 2011) with regret bound depending on the number of arms K. A series of experiments are provided to demonstrate that proposed methods work better than LinUCB or LinTS-based methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Could you try to add a discussion on the comparison with the related work mentioned above and other results in the context of adversarial linear bandits?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "WjLCSwc5xv", "reviewer": "Reviewer_hHYa", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The algorithm is novel in the linear bandit setting (to the best of my knowledge) and achieves nearly minimax-optimal regret.\n\n\nWeaknesses:\n- The authors claim that their approach is computationally efficient for large finite arm sets. I do not believe this is the case, however, as their algorithm involves computing an index for each arm, so the computational complexity will scale with $K$, the number of arms. This claim should be revised. \n- Algorithm 1 is extremely similar to information-directed sampling (see in particular the variants presented in [1] and [2]). More discussion of this should be given.\n- Many algorithms which achieve minimax optimal regret for linear bandits are already known. While technically the algorithm here is novel, it does not achieve a result any better than existing works, and, as noted, its techniques are very similar to existing works.\n\n\n[1] Kirschner, Johannes, and Andreas Krause. \"Information directed sampling and bandits with heteroscedastic noise.\" Conference On Learning Theory. PMLR, 2018.\n\n[2] Kirschner, Johannes, Tor Lattimore, and Andreas Krause. \"Information directed sampling for linear partial monitoring.\" Conference on Learning Theory. PMLR, 2020.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work studies the question of regret minimization in linear bandits. They propose an algorithm inspired by the multi-armed bandit IMEB algorithm, and prove that it achieves nearly-minimax optimal regret. Experimental results demonstrate that it yields small improvements over LinUCB and LinTS.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- The claim that the algorithm is computationally efficient should be removed (typically a linear bandit algorithm is considered computationally efficient if it can be reduced to efficient computation oracles, such as a linear maximization oracle).\n- The presentation could be cleaned up somewhat. The paper presents four algorithms total, and it is not clear what the advantage of one over the other are. For example, LinIMED-1 achieves the same regret bound as LinIMED-2, while requiring stronger assumptions. This makes the statement of the algorithm somewhat confusing. My suggestion would be to remove LinIMED-1 and LinIMED-2, or put them in the appendix, and only keep LinIMED-3 and SupLinIMED (and their corresponding theorems) in the main text. \n- The confidence intervals in Figures 1, 2, and 4 overlap significantly so it is not entirely clear which algorithm is the best or worst. The number of trials should be increased so there is greater separation between the approaches.\n- In addition to including more discussion comparing LinIMED to IDS, it would also be helpful to include empirical results for IDS.\n- In Figure 3, it would be helpful to also compare against an algorithm known to be asymptotically optimal (for example the asymptotically optimal variant of IDS mentioned in section 6.2). \n- A full proof is missing from the paper—only a proof sketch for Theorem 1 is given. Proofs for all results must be included (at least in the appendix). \n\nMinor typos:\n- The definition of regret given in the intro is incorrect—rather the max should be over the expected mean for each arm $a$ rather than, $Y_{t,a}$, the random reward received.\n- Some of the indices in Algorithm 1 are incorrect. For example, on line 9, the argmax is over $j$, but the objective of the argmax uses $a$.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "iul6mEnjBc", "reviewer": "Reviewer_CTEL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strengths of the paper are that it fills a genuine gap in the literature: the extension of a popular and effective family of algorithms for the multi-armed bandit problem to the linear case, and that the theoretical work is extensive and (to the best of my ability to judge in the time-frame) accurate. To elaborate, the IMED algorithms are, as the authors nicely summarise, successful approaches for the multi-armed bandit problem, particularly for reasons such as their capacity to be more easily incorporated into settings where counterfactual offline evaluation is necessitated. It is therefore a clear benefit to explore the extension of these methods to the linear bandit problem (and in future work, beyond). The theoretical work derives strong results for each of the algorithms, improving over what is achievable for linear Thompson Sampling, matching the best finite-time performance of optimistic algorithms, while maintaining an improved computational efficiency over these optimistic approaches. The layout of these results is mostly reader-friendly, with a detailed proof sketch for the first algorithm provided in the main text and explaining the key steps and the novelties therein, and the more detailed aspects relegated to appendices.\n\nThe most substantial weakness is in the experimental evaluation, specifically around the comparison to alternative approaches, and the choice of hyper parameters.\n1. I found the justification for not including SupLinIMED and other SupLin algorithms not to be the strongest. Why not just include these to illustrate this point and show the reader how much worse they actually are?\n2. You mention a similarity to Information Directed Sampling, and its asymptotic optimality - why not include it in your empirical comparison as a stronger benchmark?\n3. It is unclear whether the multiplication by $\\alpha$ breaks the theoretical guarantees of the previous section, and how the algorithms would perform if you had tested the version with the theoretical guarantees. It also seems curious to tune $\\alpha$ over $T=100$ rounds when the algorithms are run for much longer in practice.\n4. Why are very different horizons used across the various experiments?\n5. A precise explanation of what is shown in the plots is not quite given. There is a remark in the text that states a mean and standard deviation are computed, so I infer that they show means plus and minus one standard deviation, however it is not clear whether the distributions of regret are symmetric as this would imply. Thompson Sampling can, for instance, often lead to skewed distributions.\n6. I was a bit confused as to why repeated the suboptimal arms in the experiment of 6.1 makes any difference to the IMED algorithms, when there is a common $\\theta^*$ will the algorithm not perform the same as if there was only one of these suboptimal arms.\n7. Does the experimental setup allow $||\\theta^*||$ and $||x_t||$ to exceed the assumed bounds also?\n8. You speak to a statistical significant difference regardless of $d$ or $K$. This doesn't seem obvious in, for instance, Fig 2 (c)?\n9. Building on point 7, it seems that the LinIMED algorithms enjoy some favourable selection of its parameters (in ways that may break (or alter) the associated theoretical guarantees) but it is not clear whether this occurred for the TS and UCB variants?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the extension of the Indexed Minimum Empirical Divergence (IMED) family of algorithms (Honda and Takemura, 2015) to the linear bandit problem. The paper proposes three variants of linear IMED with different parameterisation of its indices and a SupLinIMED algorithm, inspired by the SupLinUCB/SupLinTS family of algorithms.\n\nThe motivation for proposing these algorithms is that existing algorithms for linear bandit problems are either computationally intensive or carry suboptimal theoretical guarantees. Inspired by the success of IMED algorithms for standard bandit problems, the linear IMED algorithms proposed realise closer to optimal order regret than is attainable with randomised policies with improved computational efficiency over other near-optimal algorithms.\n\nThe paper derives guarantees on the regret of all four proposed algorithms and studies all but the SupLinIMED algorithm in three numerical experiments: two synthetic and one constructed on the MovieLens dataset. The performance of the third algorithm LinIMED-3 is seen to be the strongest across these experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I feel the scope of the paper and the theoretical work are good and would upon resolution of concerns lean towards acceptance. However I would ideally have clarification on points 1-9 above and on the following additional remarks which are arranged in important (I) and strengthening (S) categories:\n\nI1: What is the dependence of the theoretical results on S, L, and R? And why is Assumption 1 bounding the gaps with 1 and not a free parameter like the other bounds? Does the assumption 1 bound imply something on S and L?\n\nI2: Would it be possible to add to Section 3 some intuition of why these are the appropriate functional forms for the IMED indices - they may seem somewhat arbitrary to the reader unfamiliar with Honda and Takemura (2015).\n\nI3: Is the S in Algorithm 3 the same S as used to bound $\\theta^*$? Should it be set as a ceiling or floor of $log(T)$ so that $[S]$'s make sense, and does line 15 of Alg 3 also apply for $s' \\in [S]$?\n\nI4: It would be useful to explain to the reader (or would be practitioner) how they should decide between the four algorithms presented when facing a practical problem.\n\nI5: Lemma 1 should have some more extensive conditions? I believe in Abassi-Yadkori it is required that $V_t$ is positive definite?\n\nS1: Formatting in Alg 1 could be clearer, maybe making use of cases in lines 10-12 and lines 6-9\n\nS2: Lots of brackets throughout are not sized adaptively to their inputs.\n\nS3: The wording 'Step 1/2/3' in Algorithm 3 suggests that the algorithm will sequentially progress through the steps without returning. Is this the case, and if not would these be more usefully referred to as 'Cases 1, 2, 3' instead?\n\nS4: On page 6, you say that the linear extension of IMED was 'unknown'. This isn't quite the right wording? Presumably there is more than one way to extend it (there are three in the paper), so it's the case that an extension of IMED 'with theoretical guarantees' had not been identified? or that an extension hadn't been considered in the literature?\n\nS5: On page 6, you mention 'the term $1/T_i(t)$ but eq(1) has a $log(T_i(t))$?\n\nS6: I think an L^2 appears as a typo on p8\n\nS7: There is a suppression of dependence on $\\gamma$ in the proof sketch and around eq (15) in the appendix: this should be indicated to the reader more clearly I feel.\n\nS8: shouldn't (16) lead to $O(\\sqrt{dT}\\log^{3/2}(T))$ also, once you account for $\\beta_T$?", "broader_impact_concerns": "I do not have broader impact concerns for this principally theoretical work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces the Linear Indexed Minimum Empirical Divergence (LinIMED) algorithms, a novel extension of the Indexed Minimum Empirical Divergence (IMED) approach, to the linear bandit setting. The proposed algorithms, including LinIMED and its variant SupLinIMED, aim to fill a gap in the literature by providing a computational and theoretical advancement over existing methods. The authors offer a comprehensive theoretical analysis, demonstrating that LinIMED algorithms achieve a $\widetilde{O} (d\sqrt{T})$ regret bound, where $d$ is the context dimension and $T$ is the time horizon. Empirical studies further validate the superior performance of LinIMED over popular linear bandit algorithms such as LinUCB and Linear Thompson Sampling in various settings.

The paper's major strength lies in its pioneering theoretical contribution and practical effectiveness, filling a notable gap in the literature on linear bandits. The introduction of LinIMED algorithms and the demonstration of their superior performance through rigorous theoretical analysis and extensive empirical validation highlight the paper's significant impact.
Decision: Accept (poster)