On the Minimax Regret for Contextual Linear Bandits and Multi-Armed Bandits with Expert Advice
Authors: Shinji Ito
Venue: NeurIPS 2024 poster (2024)
Keywords: contextual linear bandit
multi-armed bandit with expert advice
Primary area: bandits

Abstract: This paper examines two extensions of multi-armed bandit problems: multi-armed bandits with expert advice and contextual linear bandits.
  For the former problem, multi-armed bandits with expert advice, the previously known best upper and lower bounds have been $O(\sqrt{KT \log \frac{N}{K} })$ and $\Omega( \sqrt{KT \frac{ \log N }{\log K }} )$, respectively.
  Here, $K$, $N$, and $T$ represent the numbers of arms, experts, and rounds, respectively.
  We provide a lower bound of $\Omega( \sqrt{KT \log \frac{N}{K}} )$ for the setup in which the player chooses an expert before observing the advices in each round.
  For the latter problem, contextual linear bandits, we provide an algorithm that achieves $O ( \sqrt{d T \log ( K \min\{ 1, \frac{S}{d} \} )} )$ together with a matching lower bound, where $d$ and $S$ represent the dimensionality of feature vectors and the size of the context space, respectively.

On the Minimax Regret for Contextual Linear Bandits and Multi-Armed Bandits with Expert Advice
Shinji Ito The University of Tokyo and RIKEN shinji (enijiimmst.... i. u-tokyo... jc.
Abstract
This paper examines two extensions of multi-armes bandit problems: multi-arme bandits with expert advice and contextual linear bandits. For the former problem, multi-armed bandits with expert advice, the previously known best upper and lower N bounds have been Ol KT log K and RC / KT log N
log respectively. Here, K, N, and represent the numbers of arms, experts, and rounds, respectively. We provide a lower bound of S V KT N, K for the setup in which the player chooses an ex- pert before observing the advices in each round. For the latter problem, contextual linear bandits, provide algorithm that achieves O(y dT log( KK min } together with a matching lower bound, where and S represent the dimensionality of feature vectors and the size of the context space, respectively.
Introduction
This paper considers problems of multi-armed bandits with expert advice (MwE) [Auer et al. 2002 Kale 20144), linear bandits [Dani et al. 2008 Bubeck et al. 2012 Besa-Bianchi and Lugosi -abbasi-Yadkkrii 2012 and contextual linear bandits (CLB) CChu et al. 2011 Abbasi- Yadkori et al. 201 Neu and
Olkhovskaya 2020 Hanna et al. 2023
2024
One contribution of this paper is to present the minimax regret for MwE, which addresses the open question posed by [Seldin and Lugosi (016). For MwE, the well-known EXP4 algorithm [Auer et al.) 2002] achieves Ô [VKTlog. -regrett where K, T and N represent the numbers of arms, rounds and experts. This bound is, however, not always optimal for certain parameter settings of K and N. In fact, discussed by (Seldin and Lugosi [2066], when N = K, the problem is reduced to the standard K Kaarmed bandit problem, for which the minimax regret is O ((VKT) (Audibert and Bubeck 2009). This means that the regret bound EXP4 has a gap an ((vlop K )-ffctorr when K. On the side of upper bounds, Kale [2014) addressed this issue by providing an algorithm achieving
N o KT log+ K case of N = O(K). However, the minimax optimal bound for arbitrary settings of K and N has been an open question. The best known lower bound Ω (v/ KT
where we denote log, max (log x. 1). This is minimax optimal for the
log log K is shown by Seldin and Lugosi 2016), who conjectured that this lower bound is minimax optimal. This paper provides a solution to this open question by providing lower bound of ? (v KT KT log,
K which, together with the upper
Kale 2014) deals with more general settings of the multi-armed bandit with expert advice which only a limited number of expert advice are accessible in each round.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table I: Upper bounds (O(-)) and lower bounds (Q(()) on regret for three problems. BwE: multi- armed bandit with expert advice, LB: linear bandit, CLB: contextual linear bandit. K: number of arms, N: number of experts, d: dimensionality of feature vectors, S: size of the context space.
Setup
Reference
Bound
Parameter
BwE
Auer
2002
log
Kale
2014
KT log
Seldin and Lugosi
2016
KT log N Tog K
N N
[This work]
KT log+ K
N 2
LB
Bubeck et al.
2012
dT TTllo K)
[This work]
/dT' log+
Auer
2002
2
(VeT) -2
dT log d
K
K =
Dani et al.
2008
(VRT))
dT lool
K = 2d
CLB
Liu et al.
2024
0
(dv (dvT Tlog
[This work]
0
dl d'' log (K min {1, 1
[This work]
Ω doT (K min {1, (1)
K < 2d S KS
N This lower bound is bound by Kale [2014), implies that the minimax regret is θ (VKTlog,
shown for the problem setting in which the player need to choose an expert before observing the advices in each round. As noted in T though this problem setup is more challenging than the "classical" setting where the player can observe all expert advice before selecting an arm, almost all known existing algorithms, including those in Table 1 work for this setting.
Contextual linear bandit problems are a generalization of multi-armed bandit problems in which each arm i E [K] 21, K) is linked to feature vector i) E Rdd that depends on the context X2 at the t-th round, and the expected loss suffered for choosing is expressed as a linear function of the feature vector: (0,, o(X,,i)) In particular, this paper considers the problem setting of the stochastic-contex and adversarial model [Neu and Olkhovskaya 2020 Liu et al. 2024].
i.e., problems with stochastic X, and adversarial 0.. We also assume that distribution of contexts, similarly to previous studies, such as those by Neu and Olkhovskaya (202)) Linear bandit problems be considered special cases of contextual linear bandits in which the context space a singleton.
given access the
Upper and lower bounds regret for (contextual) linear bandits are shown in Table 1 For linear bandit problems, we show regret upper bound of O (VdT log (K/d)), which is slightly better (dTlop log K) by previous studies [Bubeck et al. 2012 Cesa-Bianchi and Lugosi 2012 Dani et al. 2007]. One notable aspect of this novel bound is that matches lower bounds for two important special cases of K 2 [Dani al. 2008 Theorem 3], and K d (equivalent to the standard Kaarmed bandits). However, specifying the tight minimax bounds for arbitrary values of K remains an open problem.
than the known best bounds of O (dT
For contextual linear bandits, this paper presents an upper bound of O / ddllogg (K min S/d})) together with matching lower bound, where S IX is the cardinality of the context space. Note that the regret upper bound of (ddTT log T') by Liu et al. (2024) applies to the more general setting of the adversarial-contxt and adversarial-loss model. We also note that the problem formulation of contextual linear bandit problems in some existing studies [Neu and Olkhovskayaa 2020 Kuroki et al. 2024 Oikhovskaya et al. 2024 is different from ours. As noted in Liu et al. 2024], however, this problem of different formulations can be reduced to our setting with dimension d[A]. where |A] the maximum number of actions in their settings. See LLu et al. 2024 for more detailed review of previous studies.

---

To show the regret lower bound for BwE, we follow the approach employed in the study [Chen al. 2024] on the minimax regret for problems interpolating problems of (full-information) online learning with expert advice and multi-armed bandit. They have shown that, for the generalization of a K-armed bandit problem in which each arm is associated with v different experts, the minimax regret is O (VKTlogg logv). v). Inspired by their construction of the problem instance, we consider a BwE instance in which N' = ((N/K) experts give advice for choosing one of two arms and there are independent (K) copies of such structures. This yields a lower bound of Q( /KT N7) log/K))))))))
In the proof of regret upper bounds for (contextual) linear bandits, we develop an algorithm based (FTRL) approach with a Tsallis entropy regularizer with on the Nollow-th--rggulaiizeeeeadd
1-a Eielky (w(i)) w(t)). This approach can be interpreted as a generalization of the EXP2 algorithm (Bubeck et al., 2012]. In fact, EXP2 can be regarded as the FTRI. approach with Shannon entropy regularization, which coincides with the limit of a-Tsallis entropy as a approaches 1. This paper shows that the regret bounds can be further improved by not fixing a to but by adjusting it appropriately. Similar approaches have been used successfully in various online learning problems including multi-armed bandits (Audibert and Bubeck 2009], bandits with expert advice [Kale] 2014), graph bandits (Eldowa et al., 2024]] and sleeping bandits [gguenn and Mehta, 2024). In addition to FTRL with Tsallis entropy regularization,
parameter E (0, 1): da (w)
to achieve O (v KT KT KS
log+ (#a
-regret in contextual linear bandits, we combine novel technique
of context-dependers learning rafe. More precisely, we introduce learning rate parameters (7x)), that change depending on the observed context X, X. We show that tuning 1) X - R> leads to improved regret bounds.
Notation For natural number n, denote [n]] 21. n.. For two real vectors x (x(())ee(4))) y = (v(1))ee() E Rdd let (I. v) denote the inner product between and y, i.e., (a. v) EiE (i)) Let P(K) = ww E [0, 1]KK ΣiELK] w(i) = 1} denote the set of proba- bility distributions over [K]. For any symmetric matrices A and B, denote A > B if and only if A B is positive-semidefiiit. Let tr(A) denote the trace of square matrices A.
2
Multi-armed bandit with expert advice
2.1 Problem setting
In the problem of multi-armed bandits with expert advice (BwE), the player is given the number of arms K and the number of experts N. In each round, each expert [N] select an advice ei(i) E [K]. and the player chooses an expert Jr E [N]. Then, after the player observes the expert advice (e) the player pulls the arm 4 e (J,)) E [K] and gets feedback of the suffered loss (T+) E [0, 1). The performance of the player is measured by means of regret Ry defined
T Σ 4T.)
Emcaor)
T
R max E J'
Remark 1. We consider the problem setting in which the player choose the expert Je before observing expert advice (ex (E)))ENN) This setting is more challenging compared to the one where the player can observe all expert advice before selecting an arm, because the available information is more
limited. On the other hand, existing algorithms by Auer et al. [2002] Kale (2014) can be applied to
this more challenging setting and achieve the regret upper bounds shown in Table [ Therefore, we have decided to adopt this setting this study.
Best expert identification The best expert identification (BEI) problem is a variant of BwE problem in which the player aims to identify the expert attaining the minimum value of expected loss from as few feedbacks as possible. We here assume that (c,, Ex) follows an identical distribution D independently for all = 1, 2...... Note that, for (e, f) D, all elements of e and may be dependent, and that we impose the independence assumption only between data at different l. For each expert j E [N] we define μı = E(G.))D [(()())) and let j" E [K] denote the best expert in terms of the expectation, i.c., j E arg [iN Mg. In the BEI problem, the player repeats selecting
3

---

arms and obtaining feedback for an arbitrary number of times T, and then outputs the estimated optimal expert Jr [4].
For positive number e, an expert j is called an e-optimal expert if Pj 13- + e. An algorithm A for BEI is called (e, -epobabby approximately correct (PAC) if it outputs an e-optimal expert with probability at least (1 - 6). For any algorithm A for BEI, let (AA, D) denote the expected value of the number of rounds 7" until A is terminated when it applied to the problem instance associated with D.
2.2 Reduction from BEI to BwE
This section shows that BEI problems can be reduced BwE problems. More precisely, given an algorithm for BwE problems with a regret upper bound, we can construct an (s, 6)-C algorithm with bounded number of queries, as follows:
Lemma 1. Suppose that there exists algorithm A for BwE such that the regret is bounded as RT S r(T) for every T. For an arbitrury e E (0, 1), let T be such that T 2 2500-r(T')
Then, there exists an (e, 0.05)-PAC algorithm A' for BEI such that TAA, S T for any D.
Proof. Consider the following algorithm A' for best-expert identification: (i) Run A for T rounds
and let T2 be the number of rounds in which the expert j is chosen, i.c., T, = [t [T"] Jr = jH-
(ii) Output j = with probability Tj/T", i.e., . is chosen so that Pr[J = j] = T for all
j E [N]. Let us show that this is an (e, 0.0 algorithm.
Let Ne C [N] denote the set of e-optimal experts and let No. [N] \G. Let To = EjEN Tj
denote the number of choosing e-optimal experts. We then have Rr- 2
E e EjeN: T3
E (T -Tz)] as we suffer per-round regret of at least in expectation, in every round when an expert in No is chosen. Hence, from Markov's s inequality, we have
100
Pr S 0.997*) = Pr [T" - Te 2 0.017" 5
E TT" Tsl
7
100
Rr
100
r(T*)
100
0.04,
T
8
2500
where the last inequality follows from the assumption of T tion of algorithm A',
2500-r(TT)
Hence, from the construc-
Pr j E No
Σ JENS
T
E
T T.
T
< Pr [Te
< 0.997*| -1+ Pr [T. > 0.997 0.01 - 0.04 0.01 = 0.05,
which means that A' is an (c, -PAC algorithm for BEI.
2.3
Construction of problem instance
For any p E [0, 1), let Ber(p) represent Bernoulli distribution of parameter p, i.e., if X Ber(p), then Pr[X = 1] = p and Pr[X = 0j p.p.
Without loss of generality,
consider the case that N and K can be expressed as N N'm + 1 and K = 2m + for some positive integers N' and m. We denote the set of experts by = {0} U {u, h) and the set of arms by A = {0} U b(u,b))uellm) be The expert advice e, is given so that (0) = 0 and ee((u, v)) E {(u, 0), (u, 1)} for all u E [m]] and v E [N'].
Fix u² E [m], u* E [N'], and [0, 1). We define distributions of (e, E) as follows:
D(z): When (e. f) follows DE=), {()) follows Ber((1 - -2) For each E [m], E((u, 0)) and É(uu, 1)) are given by E((u, 0)) = b, and E((u, 1)) = bu. where by follows Ber(1/2). The expert advice is given by e((u, v)) = (u, byr), where each bwo follows
Ber(1/2) for u E [m] and u E [N'). All elements of E(O), (bu)ue(m) and (tww)ue(ml.oet are independent.

---

Theorem 1. Let A be an (s/2, 0.050.05)PPC algoritlum for BEI. We then have T(A, D(E)) 2 mT DiE, u" v²): When (e, E) follows D(E, u², o²), and follows the same distribution as (e)
except for e((u,, )). The value of e((u", e²)) is given as e((ur, =²)) (u² bu
(u", |e((",, 0)) 1))- where V/ is a random variable that follows Ber(1/2 - independently
of the other randomness. other words, the second element of e((u", x*)) chosen that
E(e(u", v²)) follows Ber(1/2 -)).
The probability distribution of D(s, u", v²) is constructed that the marginal distribution of for (e, ~ D(e, v²) is same as that for D(e). Indeed, the values of is determined by (we))ufmlleeE(N)) and the marginal distribution of bu for D(e, u*, x²) is mixture distribution
given as Pr [e[("", 0)) 0] Ber -)) Pr [e((u",)) =] Ber (3 + +)
Ber ( E)
Ber ( + Ber (2) which equivalent to distributions for D(e). In addition, if (e, D
follows (E,, u. v²). the expected loss for choosing expert (u, v) is given as
E (e.))=D(C,,",p
[e(e(u, v)) = - E [(u, ""),,
where [[.] represents the indicator function, i.e., [ = 1 true and [ = 0 otherwise. This means that, for the problem instance of BEI associated with D(e, u", v²), the expert (u","*) is the only (s/2)-optimal action.
We denote Dr(e) "")) Dr(e,u")= = Ni (De,,,,
(D(s))².
Let Dr(e,u*) denote the uniform mixture of
1,
2.4 Lower bound for best-expert identification problems
We first consider the special case of m -1 and provide an instance-specific lower bound for BEI associated with D(s) and (D(e, } Ev..
Lemma 2. Suppose m = and let A be an (e/2,0.05)-PAC algorithm for BEL. then have T(A,
2 In(N" /4) T
Proof. Let T be the number of rounds the algorithm A proceeds. Let E denote the event that the al- gorithm A terminate at a round before T + (i.e., T TT) and output j = O. Then, from Pinsker's
inequality, we have Pr [E]( ( ~ Dr- (e)] - Pr [E] ((e,, 4 ()) ~ Dr- 1)]l s
DEL (Dr-(e, 1)I[Pr--e) (e)) S 0.25, where the last inequality follows from Lemma 9in the supple-
mentary, As A is an (z/2, -.OC) algorithm, we have Pr [El((e,, 4)) Dr (E, 1)] < 0.05.
By applying the union bound,
we obtain 1 Pr [El((er, ~ (r-(E))
Pr |T|T > [" ()) (1)( Dr-
+ Pr TT 0l((e,, 4)) Dr (s)
<
Pr Pr[T > T' (() Dr-(E)) + 0.05. Combining these inequalities, we ob-
tain Pr [T > T*I((e, ())T ~ (r)
2
0.95 Pr [E](((e, 4))T= ~ Dr- (c)]
2
0.95 0.25 Pr [E) Ti)TT (e,
> 0.95 0.25 0.05 0.65, which im-
plies that ((A, 2 E [ ((e, Dr (E) 2 0.657 This completes the proof.
We can obtain a lower bound for BEI for general m by using Lemma
m 2
In(N' /4)
18
2
2.5 Lower bound for multi-armed bandits with expert advice
are now ready to provide a lower bound for BwE.
Theorem 2. For any algorithm for BwE and for any sufficiently large T > O, there exists a problem instance for which R&r 2 C. CVTK log,
N. K. where C >> O is universal constant.
5

---

Proof. We fix and set m [(K - 1)/2] and N' [(V 1)/m] Fix
log N
so
Assume that Ry < C TK log+ N = r(T) = 0 (0 (og where CVTH the universal constant C is sufficiently small so that 2500-r(T) < T holds. Then, from Lemmal there exists an (s, 0.050- -PAC BEI algorithm A achieving (AA, D) - T for any D. This contradicis N Theorem which implies that Ry 2 C. CVTK log+ K
that <
14( 4e
K
This lower bound, together with the upper bound presented by Kale 2014). means that minimax regret for BwE of (VKT /KTlog+ log
3 Contextual linear bandit
3.1 Problem setting
Before the game starts, the player is given set X' of contexts, finite set [K] of arms, feature mapping Φ A' [K] + R.. In each round, the environment chooses loss vector 0g E RR.. Then context Xx, X is drawn from fixed distribution D, and revealed to the player. The player chooses an action I [K] and get feedback of & E [-1, 1]. of which expectation is (0,, øl ((x,, Te)).
For any policy nr X [K], we define the regret by
RT(TT)) E
Σ (0,, ((x, 1o)
Σ (0r, ((x, (X.)))
Rī
sup RT(="). [
We assume that K0c. (xx i)) < for a x X' and a E [K]. We also pose the following assumption regarding the distribution of the context.
Assumption 1. We assume that the set of contexts a finite set X = [S] and that there exists L 2 S such that the probability (xx) == Pr[X, = x] bounded from below as g(x) 1/L L for all [S]. Assume that the function g is given.
For any randomized policy X P(K), denote
(p)
E
6(Xx1)6(Xx11] X(p)
sup o(I, (()) i). <e(K),eeX
X~D.I-pX)
Assumption 2. We assume that there exists an exploration policy Po X + P(K) such that X(po) < 80.
Let Ao 0 denote (an upper bound of) the value of A(pa). We may assume that Ao Ld without loss of generality, In fact, if we set Po(x) to be g-optimal design (see, e.g., [Lattimore and Szepesvári
2020 Section 21.1J) for Z, = {Ø(x, i) í [K]], we then have Φ(x, i) ((p) o(x, -
(r, i) (po( (0 (x, S dL holds for x E X' and E [K].
g(m)
3.2
Algorithm
The proposed algorithm based on the framework bollow-the-rggulriiee--eeddd (FTRL) with Tsallis entropy regularization. For E (0, 1), define a regularization function v/ P(KK) - R by
v(w) = Σ
Σ KE[K]
w())
(I)
sE[K]
Using this regularizer, we define randomized policy ge : X P(K) the basis of FTRL, and set an arm-selection policy Pt, as follows:
qr (z) = arg min
Σ w(i) [E[K]
0. 6(zx
m(xx)) ((w)
1
9.
Pt (1 7)): + 7Po
(2)
WEP(A)

---

Algorithm Contextual linear bandit algorithm based on FTRL with Tsallis entropy
Input: Feature mapping @, learning rates (7(x))=Ex', exploration policy po, parameters 7,
for t = ,,..., ,T do
Compute Ps given by (I) and (2).
Observe Xt, choose I drawn from (X)), and get feedback of 4.
Compute O, defined by 3
end for
where dg an unbiased estimator defined below, 77(2;) >> specified later, and E (0, 1/2) is a parameter that will be chosen depending on 1). In each round t, we choose I following (Xe) and get feedback of b. We then compute unbiased estimator 0, of O, defined by
a learning rate parameter that will be
0, (AV(())--((X It)
(3)
This is in fact an unbiased estimator as
[0.] X,~D,
E
(Xx, 1t)
X (emiii))
E [V(pi) (x),) 0.] V(p.)) = 0r.
(4)
The procedure of our proposed algorithm is summarized in Algorithml |
3.3 Regret upper bound
This section provides an upper bound on the regret for Algorithm [ In the following, we use the symbol B = (0, 1) for simplicity of notation. We will show regret upper bound as follows:
Theorem 3. Suppose that 1/2 S a < and that y satisfies
16n(x) g(x)8
1/a
λy min
8 sup n(x, sup #EX
(5)
Then, the regret for Algorithm 7 bounded as follows:
Rr(T))=00 (T(()
min d sup n(()), d sup π(x) } =ex g(x)3 + +7) +
K3
g(x)
7)x))
=ex
DEX
From this theorem, by tuning parameters and n7x) on the basis of T, d, K and g, obtain the following:
Corollary 1. For sufficiently large T, Algorithm acchives the following:
By setting (zx) = n/9(2)) = with o/ =
B(KS)
and 3 (1/ (log++ (K)))),
ad=T
-OV (dTTog ( ADVTT-3)
we obtain R&t O
By setting (Tx)) = O
BK* adf
for all x E X and B = @ [ogg we obtain
T - Vog K + No min V dlog K L (TVV-1
R₁ =0
Remark 2. The proposed algorithm (Algorithm D can also work for the infinite context case, in which it enjoys the second regret upper bound in Corollary In fact, this regret upper bound does not include = | or J., and the value of g(x) not required to define ()))) in showing this second upper bound. Hence, In the infinite context case, however, further challenges regarding the computational complexity of the algorithm should be noted. For example, need compute V V(p.) in the algorithm appears the definition of 0, (3), which tend to be computationally expensive, depending on the computational model and the setup of distributions.
show this bound without the assumption that A' is finite set.

---

To prove Theorem we introduce some notations: Denote (x(x) ((0, 6(2,
E R
sE[K]
which is an unbiased estimator of ((0r, ((x, 8) sE(K]. For any w E P(K), let D (1, w denote the Bregman divergence associated with 4/, i.e., D(w, w/) vh(w) 1b( From the standard analysis technique for FTRL (see, e.g., [Lattimore and Szepesvári 2020 Chapter 28J) and the idea of ghost sample Xo DD drawn independently from all other randomness (see, e.g.. [Neu and Olkhovskaya 20200), we obtain the following upper bound:
(Vis
w')
Lemma 3. For Algorithm the regret is bounded as Rr I 2xT + K- E (((()))) - qx+1(Xo)) mixo mix, (Xo),
[(z] LEEt 722)
E
We note that Xo is random variable that does not appear in the decision-making process or algorithms, but appear only in the analysis, and is defined to be independent of X1, X2....... Xr (and therefore is independent of any other variables including q.). The first component of the right-hand side of this formula be bounded via the following lemma:
Lemma 4. Suppose that т i [K]. We then have (f, w - w²) - D(w', w) S T-a EiErK
EK and w P(K) satisfy nl((i)) I L w(i)a=1 for all
4n
This follows, e.g., directly from the first part of Lemma 9 given by Ito et al. 2024 To check the sufficient conditions for applying Lemma we use the following lemma:
Lemma 5. It holds for any E X and i [K] that
1
o(x, i) V(p)) s min
(6)
(1 - ((,,))
Consequently, we have
| [0 ((s,))
Ao do min {
(1- (z,
Combining Lemmas and obtain the following:
Lemma 6. Suppose that a 2 1/2 and that y is given as (l((z), )(1(1))
Then it holds for any t and x E X that
1 n(() ((pe)(t))
An(x)
(z,
Ee( (8)
B
KE[K]
Further, the expectation of the right-hand side of (8) can be bounded as the following, which the key lemma for leading an improved regret bound of O dI log.
KS
Lemma 7. We have
sup n(x), d sup 7(x)
(Xo) Σ
x(Xx,)))-al((00) i)2
S I1-
min
zex g(r) J.
(9)
zed
(E(K]
Proof. From the definition of (2., i), for any fixed E X and [K], have
E 12
E
E 1.) (o
[ - (p..
= =((x
1 1
x(x,1) ((())
o6 VV()) -1(r,)))
(10)

---

Denote 7/1 = supzex ((1)/((2)) Then, from
10
we have
[LHS of
9
7/
E
g
((xo)
Σ
(o
1
(E(K]
L+8
Σ 6(2,
((1))))))
1
?
TEN
71
u(x, 1) v(z,)),
(11)
1 ZE KE[K]
where define u(x,i) g( i) and v(x, t) g(>)) () (((.)))))))))))))))))))))())))) (ox We then have (i) u(r,i) 2 0 for all x E X and E [K]: EvEx Eve(K] u(æ', (2 = 1, (ii)
Ex'x EveKK] v( (') d, and (iii) 0 S v(r,i) s for all X and E [K] Indeed,
the condition (i) is clear from the fact that u(x, is probability mass function over x [K]. The condition (ii) follows from
EΣ FEE
o(d',8)= =r tr V(a.)- EE xEX {E|K]
Σ
((z));(z, (0((2) i))
=t -v((v))) = tr(Ia) =d
The condition (iii) follows from Lemma 8 and the fact that as (( d)Ø(r, i)0(x, a)T Y V(g).
Let U C X x [K] be the top-d subset with respect to the values of u(z, a), ie., let U be such that |U] = d and i(x 2 i(xx,))) for any (x,1) E U and any (z',1") E (X x [K]) \ U. Then, when we consider maximizing Enex Eie(K] u(æ, ()x i) subject to the constraint of (ii) and (iii) on v, the maximum is attained by v(z, = 1[(2,)) E U}. We hence have ELEX Eie[K] u(z,1))o(z,1) S E(.ner i)x, s 101--8 (Eeeneu u(z,E) S ddd, where the second inequality follows from Hölder's inequality and the last inequality follows from the Similarly, denoting no condition (i). By combining this with (TT. we obtain [LHS of ( T-
mdd
suPxEx 72x),, we obtain [LHS of Yu E tr (g))) "iEjK] (e i)o(Xo. i)o(Xo: = Yu I-
3o E
EiE(K] (x ()o 1) ((())) ( (6(xo,)) =
EnEx Eie[K] v(z, i) I-
and
which completes the proof.
Now we are ready to provide an upper bound on regret.
We easily see that Theorem 3 is direct consequence of Lemmas 3 6 and 7
Proof of Corollary 7 Suppose nTx))
1/g(x)3 with r/'
θ
B(KS) ad
and
B = (1/ (log (KS)))
We then have Ry = O
+ TT + na EvSx Eesxg(a)") =
B
d' + +T + n'a
(KS)
(Vai
dT
KS
B
+ +/0l7
al
d
+ Au T 0 (Vel (VdTlog, log+ (g
Suppose 11x))
0
9K* adT
for all E X and B = θ @ log
We then have
Ry 0 WTT + +
Rd na
O
dKoT aB
+ Ap min
1-ل [9K
T 2
}}
0
VdT log K + min
L'
L 1-0
VTI-B
Tlog K
alog K
0
Vill K + An mamin
(V 2log K _ (TT-T9) ))

---

3.4 Regret lower bound
The following theorem implies that the regret upper bound given in Corollary achieved by the Algorithm is tight for S S K _ 2d.
Theorem 4. Suppose any d' 2 1, S 2 1 and = S). Then, for any algoritim for contextual
linear bandit problems with K = 2 = d,S, and [ = S there exists a problem instance for which Rr = S2 (d'VST).
This theorem implies a regret lower bound of Ω (v dT dT log, (K min {1, (.) To see this, we first
note Theorem implies that, if some d' satisfies K 2 2" and d 2 d'S, we can obtain a regret lower bound of R = (2 /ST). Let (d, K, 5) be an arbitrary given parameter set that satisfies K < 2d KS We then have log2 K S d I S log2 K. Define d' == [loga KJ and S' = 2//log2/ K] S S. Then, we have K 2d and d St logg K S'd' I(d)., from Theorem 4, obtain regret lower bound of RT
(5') d'v''''''' = (2(vddd') By combining this with d' 2log K) = 22 (log+ (K min a we obtain Rr 52 (v log (K min 2))). We hence have the following lower bound: Corollary 2. For any (d, K) such that K 2d < KS and for any algorithm for contextual linear bandit problems, there exists a problem instance for which RT = Ω
( do (K (minn {1, à 1))
Proof of Theorem Theorem 4 can be shown by using the result of Dani et al. [0088] Theorem 3]. They provide lower bound of (Td for (non-contextual) linear bandit problems with K 24 We use S copies of their problem instance of the dimensionality d', to prove Theorem The context X, is drawn from uniform distribution over X [S], each element which corresponds to one of the copies of the linear bandit instance. Then, for any x E X, the number of rounds s T at which X, = z is of (ST/S) with a probability at least 1/2. Hence, the expected cumulative regret suffered for rounds at which X, = x is of ((d' /T/S) for each x E X. By summing this for all x E X, we obtain the lower bound of S2Sd VT/S) (dd' /ST). Note that features mapping á need to be designed so that (xx,)) and <(x', 1/) are orthogonal for any x # x' and i, E [K]. We can satisfy this condition by setting the dimension of the entire feature space to d'S.
4 Conclusion
In this study, we investigated the minimax regret in the contexts of the multi multi-armed bandit with expert advice and contextual linear bandit problems. For the former, established regret lower bound of O(V KTTlog N in the setting where the player selects expert before observing expert advice. This bound matches, up to a constant factor, the upper bound provided by Kale [2014). Additionally, for the contextual linear bandit problem, we proposed an algorithm that achieves regret upper bound
of O(v /T log( K min(1, {))). As illustrated in Table this upper bound aligns with the lower bound under certain conditions on the parameters (K,5, DDD.
Remaining challenges in the problem with expert advice include establishing similar lower bounds when the player can observe expert advice before decision-makee in each round. Furthermore, determining the minimax regret in broader parameter setting for (contextual) linear bandits remains an open problem. Relaxing Assumption on the contextual distribution is also an important direction for enhancing practical applicability.
References
Y. Abhasi-Yadkorf D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems, 24, 2011.
J.-Y. Y. Audibert and Bubeck. Minimax policies for adversarial and stochastic bandits. In Conference on Learning Theory, pages 217-226, 2009.
10

---

P. Auer, N. Gesa-Bianchi Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(())48-77, 2002.
Bubeck, N. Cesa-Bianchi, and S. M. Kakade. Towards minimax policies for online linear optimization with bandit feedback. In Conference Learning Theory, pages 41.1-41.14, 2012.
N. Cesa-Bianchi and G. Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5):1404-144 1422, 2012.
H. Chen, Y. He, and C. Zhang. On interpolating experts and multi-armed bandits. In International Conference on Machine Learning, pages 6776-6802, 2024.
W. Chu, L. Li, Reyzin, and R. Schapire. Contextual bandits with linear payoff functions. In International Conference on Artificial Intelligence and Statistics, pages 208-214, 2011.
V. Dani, S. M. Kakade, and T. Hayes. The price of bandit information for online optimization. Advances in Neural Information Processing Systems, 20, 2007.
V. Dani, T. P. Hayes, and S. M. Kakade. Stochastic linear optimization under bandit feedback. In Conference Learning Theory, 2008
K. Eldowa, E. Esposito, T. Cesari, and N. Cesa-Bianchi. On the minimax regret for online learning with feedback graphs. Advances in Neural Information Processing Systems, 36, 2024.
O. Hanna, L. Yang, and C. Fragouli. Efficient batched algorithm for contextual linear bandits with large action space via soft elimination. Advances Neural Information Processing Systems, 36, 2024.
0. A. Hanna, L. Yang, and C. Fragouli. Contexts can be cheap: Solving stochastic contextual bandits with linear bandit algorithms. In Conference on Learning Theory, pages 1791-1821, 2023.
S. Ito, T. Tsuchiya, and J. Honda. Adaptive learning rate for gullowtte-regulaaiize--eeee Com- petitive analysis and best-of- wwwtooff-oohhwoooe both-worlds. In Conference Learning Theory, pages 2522-2566 2024.
S. Kale. Multiarmed bandits with limited expert advice. In Conference on Learning Theory, pages 107-122, 2014.
Y. Kuroki, Rumi, T. Tsuchiya, F. Vitale, and N. Cesa-Bianchi, for linear contextual bandits. In International Conference on Artificial Intelligence and Statistics, pages 1216-1222 1224, 2024.
algorithms
Lattimore and C. Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
H. Liu, C.-Y. Wei, and J. Zimmert. Bypassing the simulator: Near-optimal adversarial linear contextual bandits. Advances Neural Information Processing Systems, 36, 2024.
G. Neu and J. Olkhovskaya. Efficient and robust algorithms for adversarial linear contextual bandits. In Conference on Learning Theory, pages 3049-3068, 2020.
Q M. Nguyen and N. Mehta. Near-optimal per-action regret bounds for sleeping bandits. In International Conference on Artificial Intelligence and Statistics, pages 2827-2835, 2024.
Olkhovskaya, J. Mayo, van Erven, G. Neu, and C.-Y. Wei. First-and second-order bounds for adversarial linear contextual bandits. Advances in Neural Information Processing Systems, 36. 2024.
Y. Seldin and G. Lugosi. A lower bound for aulti-armed bandits with expert advice. In 13th European Workshop Reinforcement Learning (EWRL), 2016.

---

A
Auxiliary lemma
Lemma 8. For any positive-defiitte matrix A Raxd and real vector a Rd if xx
holds that x -A & L.
Proof. From the assumption of A = xx. T, have
x T - (A A(A x)) 2 (1) xx (A-1x) = A x=xx)
which implies x =A 1.
B
Omitted lemmas and proofs in Section 2
Lemma 9, Suppose m It holds for any N', T and E E [0, that
N - 1 (1+
(1 + 45 4
DKL (Dr- (E, Dr- Pr-
in
N'
Consequently, if S
Iu(N' /4) 15a
then the above value of the KL divergence is at most 1/4.
Proof. For (e, E), b1 E {0. 13, (Co)nElNn E {0,1} be binary variables such that (((1, 0)) b.. 1)(1,1)
bus and c((1,v) bh col- Then, all the values of (c, e) determined by ((0).b, bj and (C.)VENNY) When (e, f) follows D(e), then (f(0), b1, (Co)uE(Ng) follows & = (er((1-e)/7) Ber(1/2) (Ber(1/2)) On the other hand, when (e, E) follows D(e, 1, u²) then (E(0), b, (c, (c.)vE(Ny) follows & = Ber((1 e)/2) x Ber(1/2) x (s, where we define F.r (Ber(1/2))""-11 Ber(1/2 E) x (Ber(1/2))
That if (Co)uE(N1) follows F.., the - element c.. follows Ber(1/2) and the other elements follow Ber(1/2) independently. Hence, from the data processing inequality, recalling the definition of Dr (8) and Dr (s, v²) given in obtain
Section 2.3
DKL. (Dr Dr. (c)) S DKL
Σ V'EN'
(E.r)²" 11 (86)
(Fo) || (
DRL.
(12)
N
o" ENN
Let Po 10,1)TxxN'' R and Pe
(0, x) be the probability mass functions for
(BBrr(1/2))**) and (F..)" T. Then, from the definition of the KL divergence, we have
T
]
Σ po(c) Po(C) (F..
[RHS of 12
N Σ
E
In
N
V"E[Ny
WE VE(NY
Po(c) [Po(c)
<
In
Σ
(13)
N
N
V'ENN'
vE[N'
where we used Jensen's inequality and the fact that In(x:) is concave function. The ratio Pa* (c) of probabilities be expressed
Pu(c)
(c) II (1(cw = 0] (1- 22) + 1/c. = 1] (1+
II (1+ (4cm - 2)E). <E(T*)
(c( (E(T*)
Hence, if v o v² then
[c(c Po(c)
II
E (err)/)
(1 (4cr 2)e)
on F.
tE[T")
(ceu)
12

---

where we used the condition that elements of (Ctv) are independent. Further, if u = v², we then have
Po(c)
E
II 1E
E (ce (cr))BB((1/244)
(1 (4Crv - 2)s) - (1 + 452)*
(~
(c
Therefore, we have
N' N' 1+ (1+ 4=2)
N' - 1+ (1 4c?) T" N'
[RHS of 13
Σ In C'C[N]
In
N
N'
which completes the proof.
B.1 Proof of Theorem
Proof. For each [m], let (A, D(=)) denote the expected value of the number of rounds in which the algorithm A observes (e((u, 0)) or (((u, 1)) before termination. Then, we will show that (A, D(s)) 2 Tm/2 /2 under the assumption that A is an (s/2, (.05)-PACC algorithm.
BEI algorithm for problems with general m. Then we can construct an (e/2, 0.05)-PAC BEI algorithm A'' for problems with m 1 such that T(A', D' (s)) < Tu (A, D(s)), where D (s) and D(s) represent distributions with (m 1, N'. N") N = N"), respectively. To show this, consider the following procedure for solving BEI for m = 1 based on A: Run algorithm A. When algorithm A pulls an arm a, other than (u, 0) or (u, 1), then generate e, from D(e) and E(az) from Ber(1/2) independently of éz, and feed them to A. When algorithm A pulls (u, 0) or (u, 1). then query the instance of m = 1 and feed the observed (z/2, 0.05) -PAC BEI algorithm for the instance of m I, and the instance associated with D' (E). the number queries to this distributions has the expected value of De)))) We hence have (AA', (e)) (A,, D()).
Fix any u E [m]] and suppose that an (e/2, 0.05)
and (m
losses to A. Then, this construction provide
From Lemma 2 we have T(A', (e)) 2 T /2. As have T(A, D(c)) 2 Euelm) Ta(A, ((e)) > Ene(m) Ds)), we obtain T(A, D(e)) 2 m² / /2
C Omitted proofs in Section 3
C.1 Proof of Lemma
Proof. Fix n" : X +
[K] From the definitions of in (2) and Xo. and the fact that Ô, is an unbiased
estimator of 0, shown in (4, have
RT(xT) = E
(0c, o(,, - 6xxx,
E
02, Σ
(x(x,,))0( (Xx, x (X.))
kE[K]
ve(X,, ()x(,,) - *(x,, (Xi)) )
E
O2 Σ
+ 2TT
KE[K]
E
(Xo, ()o(Xo. 6(No. x xXoo)
+ 2
KE[K]
E
Oz 9e(No, 9e(No,;)o(Xo..) - o(
+ 2/T
<E[K]
((((T( ( (((:)((2)))-(((((00))) + 2YT.
(())) -
E
(14)
13

---

From
Lattimore and Szepesvári
2020
Theorem 28.5], for any 2 E 2, (2:())) defined by the
FTRL procedure
satishes
ln ((xa)(X))) - ( (Xo)))
(((1 n(xx)
((0)))a())---11100)
D(p(t1())
(15)
n7(x)
Combining (4 and 8 with the fact that ((((()) = (11KK) = KP-1 we obtain the desired
inequality.
C.2 Proof of Lemma 5
Proof. From the definition of pt in (2). as we have V(p.) - >V(p)), we have
6(x, 1) V(p)))))) ((x,))))))))))))) o = o(x; i) (ox, 5 N(o0) do
? (16)
() i)o(z, r)o(r, T)T, from Lemma 8 we have Φxx, i) (pt) 60(x (p,)) S (1-7)g(=)e(((x)) This, together with (16), yields ( From the definition (3 Ge, we have
Further, as we have ((p)) = (1-))V = (1
[ :) = ( (r. 0( ((,, 1) = (x, 11 1.) (())))((r
S VV) 4))(a, (())))))))
where we used Cauchy-Schwarz inequality and the assumption that |& < 1. From this and have 7
6 we
14

---

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]
Table in the introduction describes the problem settings and results in this paper.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
Assumptions and limitations are explained in Sections 2.1 and 3.1
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification asymptotic approximations only holding locally). The authors should reflect 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 the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
15

---

Justification:
Assumptions are provided in Sections 2.1 and 3.1 Proofs are provided except
in cases where it is obvious from other lemmas/theorems combinations or from existing literature.
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 referenced in 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 to 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 the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
This study does not involve numerical 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 make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way 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 large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe 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 or verifying the results.
5. Open access to data and code
16

---

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:
This study does not involve numerical experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co 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 NeurIPS code and data submission guidelines (https
//nips.cc/publcc/uuu wwtpll/icgggiiee//eeeeeoe /ctde//gguudeeeeeeouSuuumbibbi ssionPolicy) 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 are 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: This study does not involve numerical 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 level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
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:
This study does not involve numerical 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.)
17

---

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: This study does not involve numerical experiments.
Guidelines:
The answer 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 htttps://neuripp:ttte http://awrrrr.cccoouau...laalaaa
Answer: [Yes]
Justification:
The authors have reviewed the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper focuses on theoretical research and not expected have any societal impact.
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 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.
18

---

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 as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: This paper focuses theoretical research and is not expected to have any societal impact.
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 require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: This paper does not existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include 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 (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the Datasets.paaeesstt
package should be provided. For popular datasets, paperswi thcode. cow 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.
19

---

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: This 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 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 involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of 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: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor 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.
20


Reviews:
[{"review_id": "ehVbxLL0jK", "reviewer": "Reviewer_aY6j", "summary": "This paper presents new bounds for regret minimization problem in multi-armed bandits with expert advice (MwE) and contextual linear bandits (CLB). For MwE, This paper bridges the gap between existing upper and lower bounds by establishing a new matching minimax optimal lower bound. In the case of CLBs, the authors propose a lower bound and devise an algorithm based on the follow-the-regularized-leader approach, which achieves a matching upper bound.", "questions": "The proposed algorithm for contextual linear bandits (CLB) requires an initial exploration policy p0 as one of its input parameters. How is this policy determined at the start of the algorithm? Are there any specific assumptions or conditions on p0 necessary for it to adhere to the presented upper bound?", "limitations": "The authors discuss the assumptions needed for their results to hold.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "• Novel contribution: The paper introduces new minimax optimal lower bounds for MwE and CLB. Additionally, for CLB, it devises an algorithm that achieves a matching upper bound.\n• Theoretical results: The paper provides comprehensive proofs for each of the newly introduced bounds, offering rigorous theoretical validation of the results.", "weaknesses": "• Motivation: The paper lacks an exploration of practical applications of the proposed work, thus indicating a deficiency in motivation. Incorporating a discussion on potential practical applications would significantly add value of the results presented in the paper.\n• Future Work: The paper does not discuss potential directions for future research.\n• No empirical results verifying the bounds.\n\nI found some typos that the author(s) might want to correct.\n\n• In line 84, ”the player chooses an expert $J_i \\in [K]$ should be replaced by ”the player chooses an expert $J_t \\in [N]$, correct?\n\n• In line 99,”$j^*\\in\\argmin_{j\\in [N]}$ is missing $\\mu_j$\n\n• In line 213: \"This section provide\" to \"This section provides\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Motivation: The paper lacks an exploration of practical applications of the proposed work, thus indicating a deficiency in motivation. Incorporating a discussion on potential practical applications would significantly add value of the results presented in the paper.\n\nWe appreciate your suggestion. \nSince our results on linear bandits and contextual linear bandits imply improvements in the regret upper bound compared to existing algorithms, \nwe expect improved performance in real-world applications and believe they will be useful in practice.\nHowever,\nthis study focuses primarily on the goal of revealing the limits of achievable regret upper bounds for the fundamental online decision-making problems,\nrather than on specific applications.\n\n> Future Work: The paper does not discuss potential directions for future research.\n\nThe revised version describes open questions and future research direction more explicitly,\nas we mentioned in \"Author Rebuttal\" above.\n\n\n> No empirical results verifying the bounds.\n\nThis paper does not include empirical results because,\nin general,\nresults of some specific numerical experiments are not very informative for the purpose of validating the analysis of *minimax* regret.\nIndeed,\nthe minimax regret corresponds to the *worst-case* scenario,\ni.e.,\nthe problem instances that are most unfavorable loss-sequences for the algorithm.\nNumerical experiments on specific data are rarely the worst-case input,\nand it is difficult to know how close to the worst-case it is.\nThe same reason may explain why many existing studies focusing on minimax regret do not include numerical experiments.\n\n\n> I found some typos that the author(s) might want to correct.\n\nWe deeply appreciate your pointing out the typo. \nWe consider that all of them need to be corrected as you pointed out, and we will reflect them in the revised manuscript.\n\n> The proposed algorithm for contextual linear bandits (CLB) requires an initial exploration policy p0 as one of its input parameters. How is this policy determined at the start of the algorithm? Are there any specific assumptions or conditions on p0 necessary for it to adhere to the presented upper bound?\n\nThe necessary assumption on $p_0$ is described in Assumption 2 (line 196),\nwhere $\\lambda( p_0 )$ is defined just above it.\nAs long as this assumption is satisfied,\n$p_0$ can be determined in any way.\nIn particular, if $p_0$ is determined using g-optimal design, then $\\lambda(p_0) \\le Ld$ holds,\nand hence this assumption is satisfied,\nas explained just after Assumption 2.\nThe parameter $\\lambda_0 = \\lambda(p_0)$ depending on $p_0$ affects the asymptotically non-dominant terms (in the regime of $T \\rightarrow \\infty$) of the regret upper bounds provided in Theorem 3 and Corollary 1.", "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": "SVtt3Fh4JG", "reviewer": "Reviewer_FSFk", "summary": "The paper investigates two significant extensions of multi-armed bandit problems: multi-armed bandits with expert advice (MwE) and contextual linear bandits (CLB). For MwE, the authors close the gap between previously known upper and lower bounds, establishing a matching lower bound of $\\\\Omega\\\\left(\\\\sqrt{KT \\\\log \\\\frac{N}{K}}\\\\right)$, where $K$, $N>K$, and $T$ denote the number of arms, experts, and rounds, respectively. This claim seemingly resolves an open question posed by Seldin and Lugosi (2016), where a $\\\\Omega\\\\left(\\\\sqrt{KT \\\\frac{\\\\log N}{\\\\log K}}\\\\right)$ regret lower bound was shown. For CLB instead, the authors introduce an algorithm that achieves an improved upper bound of $O\\\\left( \\\\sqrt{dT \\\\log\\\\left(K \\\\min\\\\{1, \\\\frac{S}{d}\\\\}\\\\right)\\} \\right)$, where $d$ is the dimensionality of feature vectors, and $S$ is the size of the context space. The authors also provide a matching lower bound, confirming the minimax regret is $\\\\Theta\\\\left( \\\\sqrt{dT \\\\log\\\\left(K \\\\min\\\\{1, \\\\frac{S}{d}\\\\}\\\\right)} \\\\right)$. The results are achieved using the follow-the-regularized-leader (FTRL) approach using the negative Tsallis entropy regularizer for an appropriate tuning of its parameter, and carefully designed context-dependent learning rates.", "questions": "- Could you clarify the doubts that were raised in the weaknesses above?\n- Could you expand a bit on how the argument at lines 278-279 allows us to keep the generality of the values of $S$, $K$, and $d$ as claimed?\n- Do you think the ideas from the different lower bounds for linear bandits could be adapted and combined to prove a regret lower bound for arbitrary values of $K$? Or is there a much larger technical hurdle that needs to be overcome?\n\nMinor comments/typos:\n- Line 99: The argmin is missing $\\\\mu\\_j$\n- Line 104: “denote” instead of “denotes”\n- Line 130: “and the set” instead of “the set”\n- Line 143: “provability” instead of “probability”\n- Line 180: “Lemma” instead of “to Lemma”\n- Line 187: “drawn” instead of ”drown”\n- Line 188: “gets” instead of “get”\n- Line 192: “contexts” instead of “context”\n- In assumption 1, it could be clearer to specify that $L \\\\ge S$ instead of just $L>0$ for it to make sense, otherwise it might not be satisfiable\n- Math display after line 195: $I \\\\sim p(X)$ instead of $I \\\\sim p(x)$\n- Line 196: “that there exists an” instead of “that an”\n- Line 252: the choice of naming the top-$d$ subset of pairs $(x,i)$ as $S$ might cause confusion in the reader, as $S$ is already defined to be the number $S = |\\\\mathcal{X}|$ of contexts", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This work provides relevant contributions to the theoretical understanding of multi-armed bandit problems in terms of the minimax regret.\nEven if the use of the follow-the-regularized-leader (FTRL) approach with negative Tsallis entropy regularization follow from a previous line of work of improved regret bounds in other bandit problems, as made explicit by the authors in the introduction, the regret analysis of the proposed algorithm for CLB requires novel ideas in tuning the learning rate and more care in leveraging the possibility to tune the parameter of the Tsallis entropy.\n\nMore interestingly, the authors manage to provide an improved lower bound for a harder version of bandits with experts advice that matches the regret of the algorithm proposed by Kale (2014).\nThey do so via a proof argument that adapts ideas from the previous work on bandits with feedback graphs by Chen et al. (2023) to MwE, requiring a careful construction of hard problem instances for the latter problem. This construction is nontrivial, interesting, and could potentially help in the design of hard problem instances for proving lower bounds of other related problems.\nFurthermore, introducing logarithmic factors in regret lower bounds is typically challenging and doing so enables a more complete understanding of the problems.\nSimilarly, the lower bound for CLB requires a clever adaptation of previous results.", "weaknesses": "While the lower bound for the MwE problem improves on prior results, it requires to consider a **harder** setting than the standard one by restricting the learner.\nSpecifically, they restrict the learner to selecting only experts rather than possibly choosing actions directly, and the learner can observe the expert advice only after making a decision.\nThe presentation is also somewhat misleading, as the authors claim to resolve the open problem left by Seldin and Lugosi (2016) for the “classical” problem of multi-armed bandits with expert advice while it is not exactly the case.\nTo fully address that open question, one needs to consider learners that may select actions irrespectively of the expert advice, and that observe the expert advice before choosing an action.\nNonetheless, the authors themselves make a clear point (rf. Remark 1) that this is indeed a more challenging setting, and my concern mainly revolves about the claims in the abstract and introduction.\nIt should also be clarified that proving the same lower bound for the standard setting remains an open problem that could be interesting to investigate.\n\nSome proofs in the paper feel more like sketches rather than complete proofs. While they provide a good overview of the approach and main ideas, they lack detailed steps and thorough explanations. This makes it challenging for readers to fully verify the results and understand all nuances of the arguments.\nFor instance, the proof of Corollary 1 would benefit from a more detailed explanation of the steps; additionally, an intuitive explanation of the choice of the context-dependent learning rate would help the reader while possibly helping in adapting a similar idea in other related problem settings.\nAnother example is provided by the proof of Theorem 4, which is missing a more formal and explicit computation of the lower bound.\n\nFinally, the results in this current work still do not achieve minimax optimality for the non-contextual linear bandits problem. Indeed, the only known lower bounds that match the upper bound provided in this work hold for the cases $K=d$ and $K=2^d$, respectively. The problem of proving a lower bound for arbitrary values of $K$ is still open and stating this explicitly would make the exposition of the contribution of this paper more transparent and clearer for the reader. A similar question could be made for the contextual version of the problem since the lower bound proved in this paper requires $2^{d/S} \\\\le K \\\\le 2^d$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> While the lower bound for the MwE problem improves on prior results, it requires to consider a harder setting than the standard one by restricting the learner.\n\nWe deeply appreciate your suggestion.\nWe agree that this is an important issue,\nand we will add this point to the abstract and introduction.\nIn addition, we will mention in the revised version that\nshowing a similar results in the \"classical\" problem setting remains as an open question.\n\n\n> For instance, the proof of Corollary 1 would benefit from a more detailed explanation of the steps; additionally, an intuitive explanation of the choice of the context-dependent learning rate would help the reader while possibly helping in adapting a similar idea in other related problem settings. \n\nThe revised version will includes a step-by-step explanation of how to calculate to show the bounds in Corollary 1.\nThe context-dependent learning rate is designed so that the regret upper bound of Theorem 3 is bounded well.\nIn fact,\nif we consider minimizing $\\sum_{x} \\frac{g(x)}{\\eta(x)}$ subject to the constraint of\n$\\sup_{x} \\frac{\\eta(x)}{ g(x)^{\\beta} } \\le$ const,\nthe optimal solution is given as $\\eta(x) \\propto (g(x))^{\\beta}$.\n\n\n> Finally, the results in this current work still do not achieve minimax optimality...\n\nAs you pointed out,\nfor linear bandits and contextual linear bandits,\nminimax regret bounds have only been identified when $K$ is within a specific setting or range.\nThe revised version will place more emphasis on this fact and make it clear that relaxing these assumptions is an open question to be resolved in future studies.\n\n\n> Could you expand a bit on how the argument at lines 278-279 allows us to keep the generality of the values of $S$, $K$, and $d$ as claimed?\n\nWe first note Theorem 4 implies that,\nif some $d'$ satisfies $K \\ge 2^{d'}$ and $d \\ge d'S$,\nwe can obtain a regret lower bound of $R_T = \\Omega(d'\\sqrt{ST})$.\nLet $(d, K, S)$ be an arbitrary given parameter set satisfying $K \\le 2^d \\le K^S$.\nWe then have\n$\\log_2 K \\le d \\le S \\log_2 K$.\nDefine $d' := \\lfloor \\log_2 K \\rfloor$\nand $S' := \\lfloor d / \\log_2 K \\rfloor \\le S$.\nThen,\nas we have\n$K \\ge 2^{d'}$ and $d \\ge S' \\log_2 K \\ge S'd'$,\nfrom Theorem 4,\nwe obtain a regret lower bound of \n$R_T = \\Omega(d' \\sqrt{S'T}) = \\Omega( \\sqrt{d' S' T d'} )$\nfor a problem instance with parameters $(d, K, S')$.\nBy combining this with\n$d' S' = \\Omega( d )$\nand\n$d' = \\Omega( \\log K ) = \\Omega( \\log_+ (K \\min \\\\{ 1, \\frac{S}{d} \\\\}))$,\nwe obtain\n$R_T = \\Omega( \\sqrt{\nd T \\log_+ ( K \\min \\\\{1, \\frac{S}{d} \\\\})\n})$.\nAs we have $S' \\le S$,\nthe same lower bound applies to the problem with parameters $(d, K, S)$ as well.\nThe revised version will include a more detailed explanation like the above.\n\n\n> Do you think the ideas from the different lower bounds for linear bandits could be adapted and combined to prove a regret lower bound for arbitrary values of $K$? \n\nWe believe there is hope, and we have tried that approach, but have not yet succeeded.\nWhat we have considered so far is a generalization based on the combination of standard multi-armed bandits ($K = d$) and hypercube bandits ($K = 2^d$).\nFor example,\nwe have considered a problem in which we choose one of the the $k$ hypercubes and then choose a point in that hypercube,\ni.e.,\nwe set $d = d' k$ and define an action set as $\\mathcal{A} = (\\{ -1, 1 \\}^{d'} \\times \\{ 0 \\}^{d-d'}) \\cup (\n\\{ 0 \\}^{d'} \\times \\{ -1, 1 \\}^{d'} \\times \\{ 0 \\}^{d - 2d'}) \\cup \\cdots \\cup (\\{ 0 \\}^{d-d'} \\times \\{ -1, 1 \\}^{d'})$.\nWe then have $K = |\\mathcal{A}| = 2^{d'} k = d 2^{d'} / d'$.\nThis construction almost covers the range of $K \\in [d , 2^d]$ by adjusting the parameter $d' \\in [1, d]$.\nWe conjecture that a lower bound of $\\Omega(d'\\sqrt{kT})$ \nholds in this setting.\nWe have been attempting to prove a lower bound using hard instances of hypercube bandits [DKH07],\nbut the existing methods of analysis (e.g. [CHZ24]) do not seem directly applicable and have not yet been able to show the lower bound.\n\n> Minor comments/typos:\n\nThank you so much for your many helpful comments.\nEach will be reflected in the revised version.\n\nReference:\n* [DKH07] V. Dani, S. M. Kakade, and T. Hayes. The price of bandit information for online optimization. NeurIPS2007.\n* [CHZ24] H. Chen, Y. He, and C. Zhang. On interpolating experts and multi-armed bandits. ICML2024.", "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": "NaJBJnNvrW", "reviewer": "Reviewer_PXkJ", "summary": "In this work, the authors tackle the existing gap between upper and lower bounds in bandits with expert advice. An existing lower bound scaled as $\\Omega(\\sqrt{KT \\frac{\\log N}{\\log K}}$, while the state of the art of only provided a $O(\\sqrt{KT \\log (N/K)}$ bound (Kale 2014) \nThe authors close this gap by proposing a novel lower bound that matches the result of Kale 2014 and improves upon the lower bound of Seldin and Lugosi (2016). \n\nThen, the authors also consider the problems of linear bandits and contextual linear bandits. For linear bandits, the authors improve upon the state of the art and provide tighter upper bounds, which match existing lower bounds for various relations of the dimension $d$ and the number of arms $K$.\nThe study of contextual linear bandits in this setting is fairly recent and there, the authors propose novel algorithm that improves upon the state of the art and a novel lower bound that matches their upper bound for certain combinations of dimensions $d$ and number of arms $K$.", "questions": "See weaknesses.", "limitations": "Purely theoretical work. The scope of the results is clearly indicated in the theorems.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "This paper provides several significant improvements for variations around the multi-armed bandits. Notably, several of their contributions are lower bounds, one of which closed an open problem that had been open for 8 years.\nThe strategy used to solve this problem is a reduction from the best expert identification problem to the bandits with expert advice setting, and this approach will likely lead to other improvements in different fields. \n\nIn the field of linear bandits, the approach using FTRL with the correct tuning of Tsallis entropy has proved crucial to solving many bandit problems, not just in the adversarial setting but in the more challenging best-of-both-worlds regime. \n\nIn all of these sections, the authors provide detailed proofs that appear correct.", "weaknesses": "If anything, this paper could benefit from some discussions about the use of FTRL with Tsallis-Inf with tuning of $\\alpha \\in (1/2, 1)$ which is used to solve many variations of the multi-armed bandits problem (for example but not limited to: bandits with feedback graphs (Zimmert and Lattimore (2019), Ito et al. (2022), Dann, Wei and Zimmert (2023) or Decoupling explorations and exploitation in MAB (Rouyer and Seldin (2020),  Jin, Liu and Luo (2023)). \n\nUsing this framework is very beneficial in best-of-both-worlds settings rather than in the purely adversarial or purely stochastic regimes. Have you considered generalizing your results to that setting?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Using this framework is very beneficial in best-of-both-worlds settings rather than in the purely adversarial or purely stochastic regimes. Have you considered generalizing your results to that setting?\n\nThanks for your suggestion.\nWe believe that our results can be extended to the best-of-both-worlds (BOBW) setting if some difficulties are overcome.\nChallenging factors are inferred from the fact that there are only limited number of results achieving BOBW with FTRL using Tsallis entropy with $\\alpha \\neq 1/2$.\nThe few such examples are [ITH24], [JLL23] and [RS20],\nwhich seem to require careful adjustment of learning rates that may depend on the feedback and output distributions so far,\nas is given,\ne.g.,\nin Algorithm 1 of [JLL23].\nThey also seem to require some sort of stability condition, as given in equation (25) of [ITH24] and in Section C.3 of [JLL23].\nIf we can overcome these challenges, we believe our results can be extended to the BOBW setting.\n\nReference:\n* [ITH24] Shinji Ito, Taira Tsuchiya, and Junya Honda. Adaptive learning rate for follow-the-regularized-leader: Competitive analysis and best-of-both-worlds. COLT2024.\n* [JLL23] Tiancheng Jin, Junyan Liu, and Haipeng Luo. Improved best-of-both-worlds guarantees for multiarmed bandits: FTRL with general regularizers and multiple optimal arms. NeurIPS2023.\n* [RS20] Chloé Rouyer and Yevgeny Seldin. Tsallis-INF for decoupled exploration and exploitation in multiarmed bandits. COLT2020.", "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": "UdR2Jpa7KZ", "reviewer": "Reviewer_sKYc", "summary": "This paper studies the problem of bandit learning with expert advice. The main contributions are two refined regret bounds: (1) A matching lower regret bound of $\\Omega(\\sqrt{KT\\log(N/K)})$ for multi-armed bandit problem; (2) $\\Theta(\\sqrt{dT\\log(K,\\min\\{1,S/d\\})})$ regret bound for contextual linear bandits.", "questions": "Please find my question in the comments above.", "limitations": "Yes.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This authors prove matching regret bounds for bandit problem with expert advice, which is significant enough for an acceptance.", "weaknesses": "My concern is about the writing. After reading the paper, I think the high-level intuitions of the construction for lower bounds could be clarified in one or two pages.\n\nI also have a question about the proof of Lemma 3. In equation (15), a lemma in the bandit algorithm book is introduced to derive regret bounds. As far as I can see, the lemma only works for fixed $X_0$. However, in the learning process $p_t$ might depends on the historical contexts $X_0,X_1,X_2,...,X_{t-1}$. I am confused about the usage of the lemma and hope for some explanations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> I also have a question about the proof of Lemma 3. In equation (15), a lemma in the bandit algorithm book is introduced to derive regret bounds. As far as I can see, the lemma only works for fixed $X_0$. However, in the learning process $p_t$ might depends on the historical contexts $X_0, X_1, X_2, \\ldots, X_{t-1}$. I am confused about the usage of the lemma and hope for some explanations.\n\nAs mentioned in lines 227--229,\nthe variable $X_0$ is a kind of *dummy* random variable that does not appear in the decision-making process or algorithms, but appear *only in the analysis*,\nand is defined to be independent of $X_1, X_2, \\ldots, X_{T}$\n(and therefore is independent of any other variables including $p_t$).\nThe approach of such an analysis is proposed by [NO20],\nin which this is referred to as the *ghost sample*.\nThe idea and usage of this technique are explained around (1) of Section 2 of [NO20].\nSince $X_0$ is independent of all other random variables, it justifies the approach of marginalizing w.r.t. $X_0$ after evaluating for a fixed $X_0$.\nThe revised version explains this more explicitly.\n\nReference\n* [NO20] G. Neu and J. Olkhovskaya. Efficient and robust algorithms for adversarial linear contextual bandits. COLT202.", "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": "hqKp8Ej6Lu", "reviewer": "Reviewer_nf4R", "summary": "This paper studies the problem of MAB with expert advice and the contextual linear MAB. Specificially, the authors proposed a lower bound of $\\Omega(\\sqrt{KT\\log\\frac{N}{K}})$, improving upon previously known lower bound $\\Omega(\\sqrt{KT\\frac{\\log N}{\\log K}})$ and showing that the previous upper bound $O(\\sqrt{KT\\log\\frac{N}{K}})$ is tight. For the second problem, the authors design an algorithm based on FTRL with Tsallis entropy regularizer and achieve $O(\\sqrt{dT \\log K(\\min(1,S/d))})$ regret bound. A matching lower bound is also proven (under certain condition of $K$) based on an extension of the previous lower bound constructed for linear bandits.", "questions": "- Whether Algorithm 1 can be extended to infinite / unknown context case?\n- Whether the additional term in the upper bound for contextual linear bandits is unavoidable?", "limitations": "See \"weakness\" and \"questions\".", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper bridges the gap between the lower and the upper bound for MAB with expert advice, solving an open problem in this field.\n- While it is not technically hard to show that a regret minimization algorithm can be transformed to a best expert identification algorithm, the reduction with a specific construction of the expert problem instance leads to a matching lower bound, which is interesting to me.\n- While both the algorithm and the lower bound construction for contextual linear case are kind of standard from a technical perspective, the matching regret bound is good to know.", "weaknesses": "While I do not have much concern for the MAB with expert advice problem, for the contextual linear bandit problem, one of my concern is that the algorithm only works for the finite context case, which is very restrictive in real applications. In addition, the implementation of the algorithm requires the knowledge of the context distribution, which is also a limitation of the algorithm. As for the regret bound, while the leading term matches the lower bound, the optimality of the additonal term is unclear. Specifically, in the second bound, $L$ may also be related to $T$ (e.g. $T^{-c}$), making the additional term dominant.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> one of my concern is that the algorithm only works for the finite context case, which is very restrictive in real applications.\n\nThe proposed algorithm (Algorithm 1) can also work for the infinite context case,\nin which it enjoys the second regret upper bound in Corollary 1 (line 222):\n$R_T = O \\left( \\sqrt{dT \\log K} + \\lambda_0 \\sqrt{T / (d \\log K)} \\right)$.\nIn fact,\nthis regret upper bound does not include $S = |\\mathcal{X}|$ or $L$,\nand\nthe value of $g(x)$ is not required to define $\\eta(x)$ in showing this second upper bound.\nHence,\nwe do not require Assumption 1 (line 192) to show this bound.\n\nIn the infinite context case,\nhowever,\nfurther challenges regarding the computational complexity and practicality of the algorithm should be noted.\nFor example,\nwe need to compute $V(p_t)$ (defined in line 195) in the algorithm as it appears in the definition of $\\hat{\\theta}_t$ in (3),\nwhich tend to be computationally expensive,\ndepending on the computational model and the setup of distributions.\nWe also require Assumption 2 (line 196) as well.\n\n\n>  In addition, the implementation of the algorithm requires the knowledge of the context distribution, which is also a limitation of the algorithm. \n\nWe agree with this comment.\nRelaxing this assumption is an important future research direction.\nWe believe that the technique of *Matrix Geometric Resampling* [NO20] can be used to relax the assumptions that the context distribution is known,\nand to consider settings where any number of samples from the distribution can be accessed.\nHowever,\nas long as this is employed,\nan extra $\\sqrt{\\log T}$ factor seems inevitable.\nTo further relax the assumption,\n[LWZ23] have proposed algorithms that do not even require access to a simulator from which the learner can draw samples from the context distribution.\nFor such a setup,\nthere is no known algorithm that achieve a $(\\log K)$-dependent bound or that avoid extra $\\sqrt{\\log T}$ factors,\nto our knowledge.\n\n\n\n> As for the regret bound, while the leading term matches the lower bound, the optimality of the additonal term is unclear. Specifically, in the second bound, $L$ may also be related to $T$ (e.g. $T^{-c}$), making the additional term dominant.\n\nThe parameter $L$ is defined on the basis of the context distribution,\nindependent of $T$,\nin Assumption 1 and does not grow with $T$ after fixing the problem instance.\nThus, after fixing the context distribution arbitrarily, the additional term will not be dominant in a regime in which $T$ is sufficiently large.\nHowever, conversely, if we consider the regime of considering the worst-case context distribution after fixing $T$,\nthen the additional term can be dominant,\nas the reviewer suggested.\n\nWe here note that the additional term in the second bound of Corollary 1\nis the **minimum** of $\\lambda_0 \\sqrt{\\frac{T}{d \\log K}}$ and $\\lambda_0 L^{\\beta/\\alpha} \\sqrt{T^{1-\\beta}}$,\nand hence large $L$ is not necessarily problematic.\nHowever,\nthe parameter $\\lambda_0$,\nwhich is defined in Assumption 2 on the basis of the context distribution and exploration policy $p_0$,\ncan be arbitrarily large depending on the context distribution,\nwhich might make the additional term dominant.\n\n\n> Whether Algorithm 1 can be extended to infinite / unknown context case?\n\nPlease refer to the response above.\n\n> Whether the additional term in the upper bound for contextual linear bandits is unavoidable?\n\nThis is an open question at this time to our knowledge.\nHowever, if the main term can be $O(\\sqrt{d^2 T \\log T})$ instead of $O(\\sqrt{d T \\log (K \\min \\\\{ 1, S/d \\\\}}))$,\nthen we can remove the terms regarding $\\lambda$ and $L$,\nas shown in Theorem 4 of [LWZ23].\n\n\nReference\n* [LWZ23]H. Liu, C.-Y. Wei, and J. Zimmert. Bypassing the simulator: Near-optimal adversarial linear contextual bandits. NeurIPS2023.\n* [NO20] G. Neu and J. Olkhovskaya. Efficient and robust algorithms for adversarial linear contextual bandits. COLT2020.", "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:
# Thank you and future revisions

First of all, we would like to express our deepest gratitude to the reviewers who spent a great deal of time reviewing this paper.
Thanks to the valuable peer review comments we received,
we are confident that the quality of our manuscript will be greatly improved.
The following revisions are planned as major changes:

### Note on the setup of multi-armed bandits with expert advice
In the revised version,
the notes on problem setup explained in Remark 1 of the current manuscript will also be mentioned in the abstract and introduction.
As noted in Remark 1 and in the comment by Reviewer FSFk,
the problem setting of BwE considered in this paper is more challenging than the "classical" setting where the player can observe all expert advice before selecting an arm,
while almost all known existing algorithms,
including those in Table 1,
work for this more challenging setting.
Although these facts were written in Remark 1,
we believe that the current abstract and introduction were misleading,
as Reviewer FSFk pointed out.
To avoid such confusion, we revise the manuscript so that readers will notice this fact just by reading the intro and abstract.

### Open question and future work
In the revised version, we will add descriptions of remaining open questions and potential future research directions.
For examples:
* Tight regret bounds for "classical" setting of multi-armed bandits with expert advice
* Tight bounds for linear bandits and contextual linear bandits with *more general* parameter setting of $K$, $S$, and $d$ (please see the comment by Reviewer FSFk and our response to it)
* Relaxing the assumption on the context distribution (please see the comment by Reviewer nf4R and our response to it)

### Correction of typos and more more detailed explanations
We will correct the typos the reviewers pointed and add intuitive explanations for the unclear points you commented on, as well as more detailed explanations of the steps in the analysis.


In addition to the above,
we will revise the manuscript in response to each of the comments received.
Once again, we are deeply grateful for the tremendous amount of helpful feedback.

Meta-review: This paper studies two related problems. First the authors show a novel lower bound for the setting of the CMAB problem which tightly matches the known upper upper. Second the authors propose a new algorithm for the Contextual Linear Bandit problem together with a matching lower bound.

Reviewers are mostly positive on this work, however, there are multiple important problems that need to be addressed before the final version. First the authors have to discuss the fact that the lower bound for MwE problem is in a harder setting than the standard. Next, the authors have to discuss the range of K for which their lower bounds hold for the linear bandit problem. Finally, the authors have to discuss the assumption that the proposed algorithm for the linear bandit setting requires knowledge of the contextual distribution and the computational problems in the case of an infinite number of contexts. Further, the presentation of the paper needs to be improved as multiple reviewers have pointed out. Nevertheless the works contributions are non-trivial and I am leaning towards recommending it for acceptance to the program.
Decision: Accept (poster)