On the Minimax Regret for Contextual Linear Bandits and Multi-Armed Bandits with Expert Advice

Authors: shinji  ito
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 19:23:21

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.  This paper closes the gap between these bounds by presenting a matching lower bound of $\Omega( \sqrt{KT \log \frac{N}{K}} )$. 
  This lower bound is shown for the problem setting 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.

Main paper: 
 introduction: 
 This paper considers problems of multi-armed bandits with expert advice (MwE) [Auer et al., 2002 , Kale, 2014] , linear bandits [Dani et al., 2008 , Bubeck et al., 2012 , Cesa-Bianchi and Lugosi, 2012] , and contextual linear bandits (CLB) [Chu et al., 2011 , Abbasi-Yadkori et al., 2011 , 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 [2016] . For MwE, the well-known EXP4 algorithm [Auer et al., 2002] achieves O √ KT log N -regret, 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, as discussed by Seldin and Lugosi [2016] , when N = K, the problem is reduced to the standard K-armed bandit problem, for which the minimax regret is Θ( √ KT ) [Audibert and Bubeck, 2009] . This means that the regret bound of EXP4 has a gap of an O( √ log K)-factor when N = K. On the side of upper bounds, Kale [2014] addressed this issue by providing an algorithm achieving this open question by providing a lower bound of Ω KT log + N K , which, together with the upper bound by Kale [2014] , implies that the minimax regret is Θ KT log + N K . This lower bound is shown for the problem setting in which the player need to choose an expert before observing the advices in each round. As noted in Remark 1 below, 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 ∈ [K] = {1, 2, . . . , K} is linked to a feature vector φ(X t , i) ∈ R d that depends on the context X t at the t-th round, and the expected loss suffered for choosing i is expressed as a linear function of the feature vector: θ t , φ(X t , i) . In particular, this paper considers the problem setting of the stochastic-context and adversarial-loss model [Neu and Olkhovskaya, 2020, Liu et al., 2024] , i.e., problems with stochastic X t and adversarial θ t . We also assume that we are given access to the distribution of contexts, similarly to previous studies, such as those by Neu and Olkhovskaya [2020] . Linear bandit problems can be considered as special cases of contextual linear bandits in which the context space is a singleton.Upper and lower bounds on regret for (contextual) linear bandits are shown in Table 1 . For linear bandit problems, we show a regret upper bound of O dT log + (K/d) , which is slightly better than the known best bounds of O( √ dT 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 it matches lower bounds for two important special cases of K = 2 d [Dani et al., 2008, Theorem 3] , and K = d (equivalent to the standard K-armed bandits). However, specifying the tight minimax bounds for arbitrary values of K remains an open problem.For contextual linear bandits, this paper presents an upper bound of O( dT log + (K min{1, S/d})) together with a matching lower bound, where S = |X | is the cardinality of the context space. Note that the regret upper bound of O(d √ T log T ) by Liu et al. [2024] applies to the more general setting of the adversarial-context and adversarial-loss model. We also note that the problem formulation of contextual linear bandit problems in some existing studies [Neu and Olkhovskaya, 2020 , Kuroki et al., 2024 , Olkhovskaya 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| is the maximum number of actions in their settings. See [Liu et al., 2024] for a more detailed review of previous studies.To show the regret lower bound for BwE, we follow the approach employed in the study [Chen et 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 ν different experts, the minimax regret is Θ √ KT log ν . 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 Ω(√ KT log N ) = Ω( KT log(N/K)).In the proof of regret upper bounds for (contextual) linear bandits, we develop an algorithm based on the follow-the-regularized-leader (FTRL) approach with a Tsallis entropy regularizer with a parameter α ∈ (0, 1):ψ α (w) = -1 1-α i∈[K] (w(i) α -w(i)). This approach can be interpreted as a generalization of the EXP2 algorithm [Bubeck et al., 2012] . In fact, EXP2 can be regarded as the FTRL approach with Shannon entropy regularization, which coincides with the limit of α-Tsallis entropy as α approaches 1. This paper shows that the regret bounds can be further improved by not fixing α to 1 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 [Nguyen and Mehta, 2024] . In addition to FTRL with Tsallis entropy regularization, to achieve O KT log +-regret in contextual linear bandits, we combine a novel technique of context-dependent learning rate. More precisely, we introduce learning rate parameters η(X t ) that change depending on the observed context X t ∈ X . We show that tuning η : X → R >0 leads to improved regret bounds. [Seldin and Lugosi, 2016 ] Auer et al., 2002 ]Ω KT log N log K N ≥ K [This work] Ω KT log + N K N ≥ K LB [Bubeck et al., 2012] O √ dT log K [This work] O dT log + K d [Ω √ dT = Ω dT log + K d K = d [Dani et al., 2008] Ω √ d 2 T = Ω dT log + K d K = 2 d CLB [Liu et al., 2024] O d √ T log T [This work] O dT log + K min 1, S d [This work] Ω dT log + K min 1, S d K ≤ 2 d ≤ K S Notation For a natural number n, denote [n] = {1, 2, . . . , n}. For two real vectors x = (x(i)) i∈[d] , y = (y(i)) i∈[d] ∈ R d , letx, y denote the inner product between x and y, i.e.,x, y 2 Multi-armed bandit with expert advice= i∈[d] x(i)y(i). Let P(K) = w ∈ [0, 1] K | i∈[K] w(i) =Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: Table in the introduction describes the problem settings and results in this paper.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
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 j ∈ [N ] select an advice e t (j) ∈ [K], and the player chooses an expert J t ∈ [N ]. Then, after the player observes the expert advice (e t (j)) j∈[N ] , the player pulls the arm I t = e t (J t ) ∈ [K] and gets feedback of the suffered loss t (I t ) ∈ [0, 1]. The performance of the player is measured by means of regret R T defined asR T = max j * ∈[N ] E T t=1 t (I t ) - T t=1t (e t (j * )) .Remark 1. We consider the problem setting in which the player choose the expert J t before observing expert advice (e t (j)) j∈ [N ] . 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 1 . Therefore, we have decided to adopt this setting in this study.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 (e t , t ) follows an identical distribution D independently for all t = 1, 2, . . .. Note that, for (e, ) ∼ D, all elements of e and may be dependent, and that we impose the independence assumption only between data at different t. For each expert j ∈ [N ] we define µ j = E (e, )∼D [ (e(j))] and let j * ∈ [K] denote the best expert in terms of the expectation, i.e., j * ∈ arg min j∈[N ] µ j . In the BEI problem, the player repeats selecting arms and obtaining feedback for an arbitrary number of times T , and then outputs the estimated optimal expert J T ∈ [K].For a positive number ε, an expert j is called an ε-optimal expert if µ j < µ j * + ε. An algorithm A for BEI is called (ε, δ)-probably approximately correct (PAC) if it outputs an ε-optimal expert with probability at least (1 -δ). For any algorithm A for BEI, let T (A, D) denote the expected value of the number of rounds T until A is terminated when it is applied to the problem instance associated with D.This section shows that BEI problems can be reduced to BwE problems. More precisely, given an algorithm for BwE problems with a regret upper bound, we can construct an (ε, δ)-PAC algorithm with a bounded number of queries, as follows: Lemma 1. Let A be an algorithm for BwE such that the regret is bounded by R T ≤ r(T ) for every T .Then, for any ε ∈ (0, 1), there exists an (ε, 0.05)-PAC algorithm A for BEI such that T (A, D) ≤ T * for any D and T * such that T * ≥ 2500•r(T * ) ε .Proof. Consider the following algorithm A for best-expert identification: (i) Run A for T * rounds and let T j be the number of rounds in which the expert j is chosen, i.e.,T j = |{t ∈ [T * ] | J t = j}|.(ii) Output Ĵ = j with probability T j /T * , i.e., Ĵ is chosen so that Pr[J = j] = T j /T * for all j ∈ [N ]. Let us show that this is an (ε, 0.05)-PAC algorithm.Let N ε ⊆ [N ] denote the set of ε-optimal experts and letN c ε = [N ] \ N ε . Let T ε = j∈Nε T j denote the number of choosing ε-optimal experts. We then have R T * ≥ E ε • j∈N c ε T j = ε E [(T * -T ε )]as we suffer per-round regret of at least ε in expectation, in every round when an expert in N c ε is chosen. Hence, from Markov's inequality, we havePr [T ε ≤ 0.99T * ] = Pr [T * -T ε ≥ 0.01T * ] ≤ 100 T * E [T * -T ε ] ≤ 100 T * • R T * ε ≤ 100 T * • r(T * ) ε ≤ 100 2500 = 0.04,where the last inequality follows from the assumption of T * ≥ 2500•r(T * ) ε. Hence, from the construction of algorithm A ,Pr Ĵ ∈ N c ε = j∈N c ε E T j T * = E T * -T ε T * ≤ Pr [T ε ≤ 0.99T * ] • 1 + Pr [T ε > 0.99T * ] • 0.01 ≤ 0.04 + 0.01 = 0.05,which means that A is an (ε, 0.05)-PAC algorithm for BEI.For any p ∈ [0, 1], let Ber(p) represent a Bernoulli distribution of parameter p, i.e., if X ∼ Ber(p), then Pr[X = 1] = p and Pr[X = 0] = 1 -p.Without loss of generality, we consider the case that N and K can be expressed as N = N m + 1 and K = 2m + 1 for some positive integers N and m. We denote the set of experts byE = {0} ∪ {(u, v)} u∈[m],v∈[N ]and the set of arms byA = {0} ∪ {(u, b)} u∈[m],b∈{0,1}. The expert advice e t is given so that e t (0) = 0 and e t ((u, v)) ∈ {(u, 0), (u, 1)} for all u ∈ [m] and v ∈[N ]. Fix u * ∈ [m], v * ∈ [N ], and ε ∈ [0, 1). We define distributions of (e, ) as follows:• • D(ε, u * , v * ): When (e, ) follows D(ε, u * , v * ), and e follows the same distribution as D(ε) except for e((u * , v * )). The value of e((u * , v * )) is given as e((u* , v * )) = (u * , b u * v * ) = (u * , | ((u * , 0))-b |), where b is a random variable that follows Ber(1/2-ε) independently of the other randomness. In other words, the second element of e((u * , v * )) is chosen so that (e(u * , v * )) follows Ber(1/2 -ε).The probability distribution of D(ε, u * , v * ) is constructed so that the marginal distribution of e for (e, ) ∼ D(ε, u * , v * ) is same as that for D(ε). Indeed, the values of e is determined by(b uv ) u∈[m],v∈[N ], and the marginal distribution for bu * ,v * for D(ε, u * , v * ) is a mixture distribution given as Pr [ ((u * , 0)) = 0] • Ber 1 2 -ε + Pr [ ((u * , 0)) = 1] • Ber 1 2 + ε = 1 2 Ber 1 2 -ε + 1 2 Ber 1 2 + ε = Ber 1 2 , which is equivalent to distributions for D(ε). In addition, if (e, ) ∼ D follows D(ε, u * , v * ), the expected loss for choosing expert (u, v) is given as E (e, )∼D(ε,u * ,v * ) [ (e(u, v))] = 1 2 -ε • 1 [(u, v) = (u * , v * )] ,where1[•] represents the indicator function, i.e., 1[E] = 1 if E is true and 1[E] = 0 otherwise. This means that, for the problem instance of BEI associated with D(ε, u * , v * ), the expert (u * , v * ) is the only (ε/2)-optimal action. We denote D T (ε) = (D(ε)) T . Let D T (ε, u * ) denote the uniform mixture of {(D(ε, u * , v * )) T } v * ∈[N ] : D T (ε, u * ) = 1 N v * ∈[N ] D T (ε, u * , v * ).We first consider the special case of m = 1 and provide an instance-specific lower bound for BEI associated with D(ε) and{D(ε, 1, v * )} v * ∈N .Lemma 2. Suppose m = 1 and let A be an (ε/2, 0.05)-PAC algorithm for BEI. We then haveT (A, D(ε)) ≥ 1 2 ln(N /4) 4ε 2 =: T * 2 .Proof. Let T be the number of rounds the algorithm A proceeds. Let E denote the event that the algorithm A terminate at a round before T * + 1 (i.e., T ≤ T * ) and output Ĵ = 0. Then, from Pinsker's inequality, we have Pr E|((e t , t ))T * t=1 ∼ D T * (ε) -Pr E|((e t , t )) T * t=1 ∼ D T * (ε, 1) ≤ D KL (D T * (ε, 1)||D T * (ε)) ≤ 0.25 where the last inequality follows from Lemma 9 in the supplementary. As A is an (ε/2, 0.05)-PAC algorithm, we have Pr E|((e t , t )) T * t=1 ∼ D T * (ε, 1) ≤ 0.05. By applying the union bound, we obtain 1 -Pr E|((e t , t ))T * t=1 ∼ D T * (ε) = Pr T > T * |((e t , t )) T * t=1 ∼ D T * (ε) + Pr T ≤ T * , Ĵ = 0|((e t , t )) T * t=1 ∼ D T * (ε) ≤ Pr T > T * |((e t , t )) T * t=1 ∼ D T * (ε) + 0.05. Combining these inequalities, we ob- tain Pr T > T * |((e t , t )) T * t=1 ∼ D T * (ε) ≥ 0.95 -Pr E|((e t , t )) T * t=1 ∼ D T * (ε) ≥ 0.95 -0.25 -Pr E|((e t , t )) T * t=1 ∼ D T * (ε, 1) ≥ 0.95 -0.25 -0.05 = 0.65, which im- plies that T (A, D(ε)) ≥ E T | ((e t , t )) T * t=1 ∼ D T * (ε) ≥ 0.65T * .This completes the proof.We can obtain lower bound for BEI for general m by using Lemma 2 Theorem 1. Let A be an (ε/2, 0.05)-PAC algorithm for BEI. We then haveT (A, D(ε)) ≥ m 2 ln(N /4) 4ε 2 = mT * 2 .We are now ready to provide a lower bound for BwE. Theorem 2. For any algorithm for BwE and for any sufficiently large T > 0, there exists a problem instance for whichR T ≥ C T K log + N K , where C > 0 is a universal constant.Proof. We fix T and set m = (K -1)/2 and N= (N -1)/m . Assume that R T < C T K log + N K ≤ C √ T m log N =: r(T ). Fix ε = m log N T .Then, as we have 2500•r(T ) ε = T , there exists an (ε, 0.05)-PAC BEI algorithm A such that T (A, D) ≤ T for any D. This contradicts Lemma 1, which implies thatR T = Ω( T K log + N K ).This lower bound, together with the upper bound presented by Kale [2014] , means that the minimaxregret for BwE is of Θ KT log + N K .3 Contextual linear banditQuestion: Does the paper discuss the limitations of 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 a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.• The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
problem setting: 
 Before the game starts, the player is given a set X of contexts, a finite set [K] of arms, a feature mapping φ :X × [K] → R d .In each round, the environment chooses loss vector θ t ∈ R d . Then a context X t ∈ X is drawn from a fixed distribution D, and is revealed to the player. The player chooses an actionI t ∈ [K] and get feedback of t ∈ [-1, 1], of which expectation is θ t , φ(X t , I t ) .For any policy π * : X → [K], we define the regret byR T (π * ) = E T t=1 θ t , φ(X t , I t ) - T t=1 θ t , φ(X t , π * (X t )) , R T = sup π * :X →[K] R T (π * ).We assume that | θ t , φ(x, i) | ≤ 1 for all x ∈ X and a ∈ [K]. We also pose the following assumption regarding the distribution of the context.Assumption 1. We assume that the set of contexts is a finite set X = [S] and that there exists L ≥ S such that the probability g(x):= Pr[X t = x] is bounded from below as g(x) ≥ 1/L for all x ∈ [S].Assume that the function g is given.For any randomized policy p : X → P(K), we denoteV (p) = E X∼D,I∼p(X) φ(X, I)φ(X, I) , λ(p) = sup i∈[K],x∈X φ(x, i) V (p) -1 φ(x, i).Assumption 2. We assume that there exists an exploration policy p 0 : X → P(K) such that λ(p 0 ) < ∞.Let λ 0 > 0 denote (an upper bound of) the value of λ(p 0 ). We may assume that λ 0 ≤ Ld without loss of generality. In fact, if we set p 0 (x) to be a g-optimal design (see, e.g., [Lattimore and Szepesvári, 2020, Section 21 .1]) forZ x = {φ(x, i) | i ∈ [K]}, we then have φ(x, i) V (p) -1 φ(x, i) ≤ 1 g(x) φ(x, i) V (p 0 (x)) -1 φ(x, i) ≤ dL holds for all x ∈ X and i ∈ [K].The proposed algorithm is based on the framework follow-the-regularized-leader (FTRL) with Tsallis entropy regularization. For α ∈ (0, 1), define a regularization function ψ :EQUATIONUsing this regularizer, we define a randomized policy q t : X → P(K) on the basis of FTRL, and set an arm-selection policy p t , as follows:q t (x) = arg min w∈P(A)    i∈[K] w(i) t-1 s=1 θs , φ(x, i) + 1 η(x) ψ(w)    , p t = (1 -γ)q t + γp 0 (2)where θt is an unbiased estimator defined below, η(x) > 0 is a learning rate parameter that will be specified later, and γ ∈ (0, 1/2) is a parameter that will be chosen depending on η. In each round t, Algorithm 1 Contextual linear bandit algorithm based on FTRL with Tsallis entropy Input: Feature mapping φ, learning rates (η(x)) x∈X , exploration policy p 0 , parameters γ, α for t = 1, . . . , T do Compute p t given by ( 1) and ( 2). Observe X t , choose I t drawn from p t (X t ), and get feedback of t .Compute θt defined by (3). end for we choose I t following p t (X t ) and get feedback of t . We then compute an unbiased estimator θt of θ t defined byθt = t V (p t ) -1 φ(X t , I t ).(3) This is in fact an unbiased estimator asEQUATIONThe procedure of our proposed algorithm is summarized in Algorithm 1.This section provides an upper bound on the regret for Algorithm 1. In the following, we use the symbol β = 1 -α ∈ (0, 1) for simplicity of notation. We will show a regret upper bound as follows: Theorem 3. Suppose that 1/2 ≤ α < 1 and that γ satisfiesEQUATION)Then, the regret for Algorithm 1 is bounded as follows:R T (π * ) = O T 1 β min d • sup x∈X η(x), d α • sup x∈X η(x) g(x) β + γ + K β -1 α x∈X g(x) η(x) .From this theorem, by tuning parameters α and η(x) on the basis of T, d, K and g, we obtain the following: Corollary 1. For sufficiently large T , Algorithm 1 achieves the following:• By setting η(x) = η g(x) β = with η = Θ β(KS) β αd α T and β = Θ 1/ log + KS d , we obtain R T = O dT log + KS d + λ 0 √ T 1-β . • By setting η(x) = η = Θ βK β αdT for all x ∈ X and β = Θ 1 log K , we obtain R T = O √ dT log K + λ 0 min T d log K , L β α √ T 1-β .Remark 2. The proposed algorithm (Algorithm 1) can also work for the infinite context case, in which it enjoys the second regret upper bound in Corollary 1. In fact, this regret upper bound does not include S = |X | or L, and the value of g(x) is not required to define η(x) in showing this second upper bound. Hence, we can show this bound without the assumption that X is a finite set.In the infinite context case, however, further challenges regarding the computational complexity of the algorithm should be noted. For example, we need to compute V (p t ) in the algorithm as it appears in the definition of θt in (3), which tend to be computationally expensive, depending on the computational model and the setup of distributions.To prove Theorem 3, we introduce some notations:Denote ˆ t (x) = θt , φ(x, i) i∈[K] ∈ R K ,which is an unbiased estimator of ( θ t , φ(x, i) ) i∈ [K] . For any w, w ∈ P(K), let D(w, w ) denote the Bregman divergence associated with ψ, i.e., D(w, w ) = ψ(w) -ψ(w ) -∇ψ(w ), w -w .From the standard analysis technique for FTRL (see, e.g., [Lattimore and Szepesvári, 2020, Chapter 28] ) and the idea of ghost sample X 0 ∼ D drawn independently from all other randomness (see, e.g., [Neu and Olkhovskaya, 2020] ), we obtain the following upper bound:Lemma 3. For Algorithm 1, the regret is bounded asR T ≤ 2γT + K β -1 α x∈X g(x) η(x) + E T t=1 ˆ t (X 0 ), q t (X 0 ) -q t+1 (X 0 ) -1 η(X0) D(p t+1 (X 0 ), p t (X 0 )) .We note that X 0 is a 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 X 1 , X 2 , . . . , X T (and therefore is independent of any other variables including q t ). The first component of the right-hand side of this formula can be bounded via the following lemma:Lemma 4. Suppose that η > 0, ∈ R K and w ∈ P(K) satisfy η| (i)| ≤ 1-α 4 w(i) α-1 for all i ∈ [K]. We then have , w -w -1 η D(w , w) ≤ 4η 1-α i∈[K] w(i) 2-α (i) 2 .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 4, we use the following lemma:Lemma 5. It holds for any x ∈ X and iEQUATIONConsequently, we haveEQUATION)Combining Lemmas 4 and 5, we obtain the following:Lemma 6. Suppose that α ≥ 1/2 and that γ is given as (5). Then it holds for any t and x ∈ X thatˆ t (x), q t (x) -q t+1 (x) - 1 η(x) D(p t+1 (x), p t (x)) ≤ 4η(x) β i∈[K] q t (x, i) 2-α ˆ t (x, i) 2 . (8)Further, the expectation of the right-hand side of (8) can be bounded as in the following, which is the key lemma for leading to an improved regret bound of O( dT log+ KS d ). Lemma 7. We have E   η(X 0 ) i∈[K] q t (X 0 , i) 2-α ˆ t (X 0 , i) 2   ≤ 1 1 -γ min d • sup x∈X η(x), d α • sup x∈X η(x) g(x) β . (9)Proof. From the definition of ˆ t (x, i), for any fixed x ∈ X and i ∈ [K], we haveEQUATION)Denote η 1 = sup x∈X η(x)/g(x) β . Then, from (10), we haveEQUATIONwhere we define u(x, i) = g(x)q t (x, i) and v(x, i) = g(x)q t (x, i)φ(x, i) V (q t ) -1 φ(x, i). We then have (i) u(x, i) ≥ 0 for all x ∈ X and i ∈ [K];x ∈X i ∈[K] u(x , i ) = 1, (ii) x ∈X i ∈[K] v(x , i ) = d, and (iii) 0 ≤ v(x, i) ≤ 1 for all x ∈ X and i ∈ [K]. Indeed, the condition (i) is clear from the fact that u(x, i) is a probability mass function over X × [K] . The condition (ii) follows fromx ∈X i ∈[K] v(x , i ) = tr   V (q t ) -1 x∈X i∈[K] g(x)q t (x, i)φ(x, i)φ(x, i)   = tr V (q t ) -1 V (q t ) = tr(I d ) = d.The condition (iii) follows from Lemma 8 and the fact that as g(x)q t (x, i)φ(x, i)φ(x, a)V (q t ). Let U ⊆ X × [K] be the top-d subset with respect to the values of u(x, a), i.e., let U be such that |U | = d and u(x, i) ≥ u(x , i ) for any (x, i) ∈ U and any(x , i ) ∈ (X × [K]) \ U .Then, when we consider maximizing x∈X i∈[K] u(x, i) β v(x, i) subject to the constraint of (ii) and (iii) on v, the maximum is attained byv(x, i) = 1[(x, i) ∈ U ]. We hence have x∈X i∈[K] u(x, i) β v(x, i) ≤ (x,i)∈U u(x, i) β ≤ |U | 1-β (x,i)∈U u(x, i) β ≤ d α, where the second inequality follows from Hölder's inequality and the last inequality follows from the condition (i). By combining this with (11), we obtain [LHS of (9)] ≤ η1d α 1-γ . Similarly, denoting η 0 = sup x∈X η(x), we obtain [LHS of ( 9)] ≤ η0 1-γ E i∈[K] q t (X 0 , i)φ(X 0 , i) V (q t ) -1 φ(X 0 , i) = η0 1-γ E tr V (q t ) -1 i∈[K] q t (X 0 , i)φ(X 0 , i)φ(X 0 , i) = η0 1-γ x∈X i∈[K] v(x, i) = η0d1-γ , which completes the proof. Now we are ready to provide an upper bound on regret.We can easily see that Theorem 3 is a direct consequence of Lemmas 3, 6 and 7.Proof of Corollary 1. Suppose η(x) = η g(x) β with η = Θ β(KS) β αd α T and β = Θ 1/ log + KS d . We then have R T = O η d α T β + γT + K β η α x∈X g(x) α = O η d α T β + γT + (KS) β η α = O dT αβ KS d β + λ 0 (η ) 1/α T = O dT log + KS d + λ 0 √ T 1-β . Suppose η(x) = η = Θ βK β αdTfor all x ∈ X and β = Θ 1 log K . We then haveR T = O ηdT β + γT + K β ηα = O dK β T αβ + λ 0 min βK β T d , L 1-α α βK β d 1 2α T 1-1 2α = O √ dT log K + λ 0 min T d log K , L 1-α α 1 d log K 1 2α √ T 1-β = O √ dT log K + λ 0 min T d log K , L β α √ T 1-β .The following theorem implies that the regret upper bound given in Corollary 1 achieved by the Algorithm 1 is tight for S ≤ K ≤ 2 d . They provide a lower bound of Ω(d √ T ) for (non-contextual) linear bandit problems with K = 2 d . We use S copies of their problem instance of the dimensionality d , to prove Theorem 4. The context X t is drawn from uniform distribution over X = [S], each element of which corresponds to one of the copies of the linear bandit instance. Then, for any x ∈ X , the number of rounds t ≤ T at which X t = x is of Ω(T /S) with a probability at least 1/2. Hence, the expected cumulative regret suffered for rounds at which X t = x is of Ω(d T /S) for each x ∈ X . By summing this for all x ∈ X , we obtain the lower bound of Ω(Sd T /S) = Ω(d √ ST ). Note that features mapping φ need to be designed so that φ(x, i) and φ(x , i ) are orthogonal for any x = x and i, i ∈ [K]. We can satisfy this condition by setting the dimension of the entire feature space to d = d S.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] 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 crossreferenced.• All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
conclusion: 
 In this study, we investigated the minimax regret in the contexts of the multi-armed bandit with expert advice and contextual linear bandit problems. For the former, we established a regret lower bound of O( KT log N K ) in the setting where the player selects an 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 a regret upper bound of O( dT log(K min{1, S d })). As illustrated in Table 1 , this upper bound aligns with the lower bound under certain conditions on the parameters (K, S, D).Remaining challenges in the problem with expert advice include establishing similar lower bounds when the player can observe expert advice before decision-making in each round. Furthermore, determining the minimax regret in a broader parameter setting for (contextual) linear bandits remains an open problem. Relaxing Assumption 1 on the contextual distribution is also an important direction for enhancing practical applicability.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [NA] Justification: This study does not involve numerical experiments. 
open access to data and code: 
 Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [NA] Justification: This study does not involve numerical experiments. Guidelines:• The answer NA means that paper does not include experiments requiring code. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration 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 is not expected to have any societal impact. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This paper focuses on theoretical research and is not expected to have any societal impact.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: This paper does not use existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: Lemma 8. For any positive-definite matrix A ∈ R d×d and a real vectorx ∈ R d , if A xx , it holds that xA -1 x ≤ 1.Proof. From the assumption of A xx , we havex A -1 x = (A -1 x) A(A -1 x) ≥ (A -1 x) xx (A -1 x) = (x A -1 x) 2 , which implies x A -1 x ≤ 1.B Omitted lemmas and proofs in Section 2 Lemma 9. Suppose m = 1. It holds for any N , T * ∈ N and ε ∈ [0, 1/2] thatD KL (D T * (ε, 1) || D T * (ε)) ≤ ln N -1 + 1 + 4ε 2 T * N ≤ 1 + 4ε 2 T * -1 N Consequently, if T * ≤ ln(N /4) 4ε 2, then the above value of the KL divergence is at most 1/4. ( (0), b 1 , (c v ) v∈[N ] ) follows E 0 := Ber((1 -ε)/2) × Ber(1/2) × (Ber(1/2)) N . On the other hand, when (e, ) follows D(ε, 1, v * ) then ( (0), b 1 , (c v ) v∈[N ] ) follows E v * := Ber((1 -ε)/2) × Ber(1/2) × F N (ε, v * ), where we defineF v * = (Ber(1/2)) v * -1 × Ber(1/2 + ε) × (Ber(1/2)) N -v * . That is, if (c v ) v∈[N ] follows F v * , the v * -th element c v * follows Ber(1/2) and the other elements follow Ber(1/2) independently. Hence, from the data processing inequality, recalling the definition of D T * (ε) and D T * (ε, v * ) given in Section 2.3, we obtainEQUATION)Let p 0 : {0, 1} T * ×N → R and p v : {0, 1} T * ×N be the probability mass functions for(Ber(1/2)) N T * and (F v * ) T *. Then, from the definition of the KL divergence, we haveEQUATION)where we used Jensen's inequality and the fact that ln(x) is a concave function. The ratio p v * (c) p0(c) of probabilities can be expressed asp v (c) p 0 (c) = t∈[T * ] (1[c tv = 0] • (1 -2ε) + 1[c tv = 1] • (1 + 2ε)) = t∈[T * ] (1 + (4c tv -2)ε) . Hence, if v = v * then E c∼(F v * ) T * p v (c) p 0 (c) = t∈[T * ] E (ctv)∼Ber(1/2) (1 + (4c tv -2)ε) = 1,where we used the condition that elements of (c tv ) are independent. Further, if v = v * , we then haveE c∼(F v * ) T * p v (c) p 0 (c) = t∈[T * ] E (ctv)∼Ber(1/2+ε) (1 + (4c tv -2)ε) = 1 + 4ε 2 T .Therefore, we have[RHS of (13)] = 1 N v * ∈[N ] ln N -1 + 1 + 4ε 2 T * N = ln N -1 + 1 + 4ε 2 T * N ,which completes the proof.Proof. For each u ∈ [m], let T u (A, D(ε)) denote the expected value of the number of rounds in which the algorithm A observes t ((u, 0)) or t ((u, 1)) before termination. Then, we will show that T u (A, D(ε)) ≥ T * /2 under the assumption that A be an (ε/2, 0.05)-PAC algorithm.Fix any u ∈ [m] and suppose that A be an (ε/2, 0.05)-PAC BEI algorithm for problems with general m. Then we can construct an (ε/2, 0.05)-PAC BEI algorithm A for problems with m = 1 such thatT (A , D (ε)) ≤ T u (A, D(ε)), where D (ε) and D(ε) represent distributions with (m = 1, N = N ) and (m = M, 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 t other than (u, 0) or (u, 1), then generate e t from D(ε) and (a t ) from Ber(1/2) independently of e t , 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 losses to A. Then, this construction provide an (ε/2, 0.05)-PAC BEI algorithm for the instance of m = 1, and if the instance is associated with D (ε), the number of queries to this distributions has the expected value of T u (A, D(ε)). We hence haveT (A , D (ε)) ≤ T u (A, D(ε)).From Lemma 2, we haveT (A , D (ε)) ≥ T * /2. As we have T (A, D(ε)) = u∈[m] ≥ T u (A, D(ε)), we obtain T (A, D(ε)) ≥ mT * /2. C Omitted proofs in Section 3 C.1 Proof of Lemma 3 Proof. Fix π * : X → [K].From the definitions of p t in (2) and X 0 , and the fact that θt is an unbiased estimator of θ t as shown in (4), we haveEQUATION)From [Lattimore and Szepesvári, 2020, Theorem 28.5 ], for any x ∈ X , (q t (x)) t∈[T ] defined by the FTRL procedure (2) satisfiesEQUATIONCombining ( 14) and ( 8) with the fact that ψ(q 1 (x)) = ψ(1/K) = -K β -1 α , we obtain the desired inequality.Proof. From the definition of p t in (2), as we have V (p t ) γV (p 0 ), we haveEQUATIONFurther, as we have x,i) . This, together with ( 16), yields (6). From the definition (3) of θt , we haveV (p t ) (1 -γ)V (q t ) (1 -γ)g(x)q t (x, i)φ(x, i)φ(x, i) , from Lemma 8, we have φ(x, i) V (p t ) -1 φ(x, i) ≤ 1 (1-γ)g(x)qt(ˆ t (x, i) = θt , φ(x, i) = t φ(X t , I t ) V (p t )φ(x, i) ≤ φ(X t , I t ) V (p t )φ(X t , I t )φ(x, i) V (p t )φ(x, i),where we used Cauchy-Schwarz inequality and the assumption that | t | ≤ 1. From this and (6), we have (7).• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.Kale [2014] deals with more general settings of the multi-armed bandit with expert advice in which only a limited number of expert advice are accessible in each round. 


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

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: • 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.
• Future Work: The paper does not discuss potential directions for future research.
• No empirical results verifying the bounds.

I found some typos that the author(s) might want to correct.

• 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?

• In line 99,”$j^*\in\argmin_{j\in [N]}$ is missing $\mu_j$

• In line 213: "This section provide" to "This section provides"
questions: 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: limitations: The authors discuss the assumptions needed for their results to hold.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
Specifically, 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.
The 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.
To 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.
Nonetheless, 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.
It should also be clarified that proving the same lower bound for the standard setting remains an open problem that could be interesting to investigate.

Some 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.
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.
Another example is provided by the proof of Theorem 4, which is missing a more formal and explicit computation of the lower bound.

Finally, 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$.
questions: questions: - Could you clarify the doubts that were raised in the weaknesses above?
- 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?
- 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?

Minor comments/typos:
- Line 99: The argmin is missing $\\mu\_j$
- Line 104: “denote” instead of “denotes”
- Line 130: “and the set” instead of “the set”
- Line 143: “provability” instead of “probability”
- Line 180: “Lemma” instead of “to Lemma”
- Line 187: “drawn” instead of ”drown”
- Line 188: “gets” instead of “get”
- Line 192: “contexts” instead of “context”
- 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
- Math display after line 195: $I \\sim p(X)$ instead of $I \\sim p(x)$
- Line 196: “that there exists an” instead of “that an”
- 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: limitations: N/A
paper_summary: paper_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) 
The 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). 

Then, 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$.
The 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$.
strength_weakness: strength_weakness: 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)). 

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?
questions: questions: See weaknesses.
limitations: limitations: Purely theoretical work. The scope of the results is clearly indicated in the theorems.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

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,...,X_{t-1}$. I am confused about the usage of the lemma and hope for some explanations.
questions: questions: Please find my question in the comments above.
limitations: limitations: Yes.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: - Whether Algorithm 1 can be extended to infinite / unknown context case?
- Whether the additional term in the upper bound for contextual linear bandits is unavoidable?
limitations: limitations: See "weakness" and "questions".

Comments: comment: I thank the authors for the detailed response. Since my main concerns have been addressed, I am raising my score as I believe this paper provides valuable insights towards studying the minimax optimal rate of multiarmed bandit problems.
Thank you for your review and feedback on the manuscript and rebuttal.

You are right about both of the points you raised.
In the revised version, we will add the phrase "there exists" in the description of Assumption 2 and correct the "g" in "g-optimal" to the "G" capitalized.

We are deeply grateful to you for bringing these errors to our attention.
Thank you for addressing my questions. 

The phrasing of Assumption 2 is a bit confusing to me. You write "We assume that an exploration policy $p_0 : X \to \mathcal{P}(K)$ such that $\lambda(p_0) < \infty$." It feels like a word is missing. You are saying that a policy $p_0$ *$\textbf{exists}$* with $\lambda(p_0) < \infty$, correct?

I see now why such a policy should exist. Incidentally you wrote "g-optimal" and usually I see the "G" capitalized.
Thanks for the explanation. It is much more clear.
Thanks for the reply, and sorry for the confusion.
We understand that $\pi^*$ is a mapping from $2^{[K]}$ to $[K]$,
so of course,
the **value** of $\pi^*(X\_t)$ depends on $X\_t$.
My point is
whether the **mapping** $\pi^*$ **itself** can change according to the realization of $\\{ X\_t \\}_{t \in [T]}$.



As we mentioned,
in the definition of regret,
$\max_{\pi^*}$ is placed outside of $\mathbb{E}[ \cdot ]$,
where the expectation is taken over all randomness.
Thus,
when considering bounds on regret,
we focus on the value of
$$
\max_{\pi^*:2^{[K]} \rightarrow [K]} \mathbb{E}\_{\\{ X\_t \\}}\left[\sum_{t=1}^T r\_t( \pi^*(X\_t))\right],
$$
where the expectation is taken with respect to the contexts 
$\\{ X\_t \\}\_{t \in [T]} \sim {D}^T$.
The "optimal policy" here is the policy that attain the maximum above.
In contrast,
we guess that you are focusing on the following value:
$$
\mathbb{E}\_{\\{ X\_t \\}}\left[ \max_{\pi^*:2^{[K]} \rightarrow [K]} \sum_{t=1}^T r\_t( \pi^*(X\_t))\right].
$$
In the latter,
one is allowed to choose a different mapping $\pi^*$ depending on
$\\{ X\_t \\}\_{t \in [T]}$,
but not in the former.
We consider this is an important difference.
In the literature of adversarial linear contextual bandits,
regret is defined with the former concept.


> Also another more concrete question: what is the optimal policy for the contextual bandit problem above?

The optimal policy is one that maximizes 
$\mathbb{E}\_{\\{ X\_t \\}}\left[\sum_{t=1}^T r\_t( \pi^*(X\_t))\right]$.
As a simple example,
let us consider the case of $T = 2$,
$K = 4$,
$X = \\{ 1, 2, 3, 4 \\}$,
$r_1 = [1,1,-1,-1]$
and
$r_2 = [-1,-1,1,1]$.
Suppose that
$X_t$ is chosen from a uniform distribution over all subset of $X$ with size $2$.
Then we can see that
$$
\mathbb{E}\_{\\{ X\_t \\}}\left[r\_1( \pi^*(X\_1)) + r\_2( \pi^*( X\_2 ))\right] = 0
$$
for any $\pi^*:2^[K] \rightarrow [K]$,
which means that every $\pi^*$ is an optimal policy.
In fact,
as $X\_1$ and $X\_2$ follow an identical distribution,
we have
$$
\mathbb{E}\_{\\{ X\_t \\}}\left[r\_1( \pi^*(X\_1)) + r\_2( \pi^*( X\_2 ))\right] = \mathbb{E}\_{\\{ X\_t \\}}\left[r\_1( \pi^*(X\_1)) + r\_2( \pi^*( X\_1 ))\right].
$$
If $\pi^*(X\_1) \in \\{ 1 , 2 \\}$,
we have
$r\_1( \pi^*(X\_1)) + r\_2(\pi^*( X\_1 )) = 1 + (- 1) = 0$.
Otherwise,
i.e.,
if $\pi^*(X\_1) \in \\{ 3 , 4 \\}$,
we have
$r\_1( \pi^*(X\_1)) + r\_2(\pi^*( X\_1 )) = (-1) + 1 = 0$.
Hence,
the expected cumulative reward is $0$ for any $\pi^*$.
Also another more concrete question: what is the optimal policy for the contextual bandit problem above?
Thanks for the response. I think there is some misunderstandings. $\pi^*$ is a mapping from the context to the arm, i.e., a mapping from $2^{[K]}$ to $[K]$, so why can't $\pi^*$ depend on the context?
Thank you for your time and the opportunity to engage in further discussion.

The construction you proposed would not suffice as a proof of the lower bound on regret.
As can be seen in Line 189,
in the definition of regret,
the operator of $\sup_{\pi^*}$ is placed **outside** of the expectation operator $\mathbb{E}[\cdot]$.
This means that
we take the maximum with respect to $\pi^*$ **after** taking the expectation with respect to the context.
Consequently,
the "optimal policy"
$\pi^*: \mathcal{ X } \rightarrow [K]$ cannot depend on the realization of contexts
but is the policy that maximize the expected total rewards.

In the case of the problem instance you presented,
the policy $\pi^*$ is chosen to ensure that
$\pi^*(X_t) \in \arg\max_{x \in X\_t} r\_t(x)$
for (almost) all $t \in [T]$.
Such a policy $\pi^*: \mathcal{ X } \rightarrow [K]$ necessarily depends on the sequence $\\{ X\_t \\}_{t \in [T]}$.
Indeed,
for most randomly generated sequences $\\{ r\_t \\}\_{t \in [T]}$,
there exists no policy $\pi^*$ such that
$\pi^*(X_t) \in \arg\max\_{x \in X\_t} r\_t(x)$ $(t \in [T])$
for (almost) every possible realization of contexts $\\{ X\_t \\}\_{t \in [T]}$.

In the literature on adversarial linear contextual bandits,
it appears standard to define regret by taking the maximum with respect to the comparator policy after taking the expectation,
as we have done in our paper.
For reference,
please see Section 2 of [LWZ23] and Section 2 of [NO20].
This can be interpreted as a comparison with the optimal policy chosen without knowledge of the realization of randomly generated contexts.



Reference
* [LWZ23] H. Liu, C.-Y. Wei, and J. Zimmert. Bypassing the simulator: Near-optimal adversarial linear contextual bandits. NeurIPS2023.
* [NO20] G. Neu and J. Olkhovskaya. Efficient and robust algorithms for adversarial linear contextual bandits. COLT2020.
I am still confused about the proof so I hope for more detailed analysis. The linear contextual bandit problem seems too dirty so we can consider contextual bandit problem instead.  For example, we assume there are  $K$ arms in $X$. In each round. Let the context distribution $D$ be the uniform distribution over all subsets of $X$ with size $K/2$. Consequently, with high probability $X_i\neq X_j$ for any $i\neq j$. We then choose the reward function $r_t(x)$ as a Bernoulli variable with mean $1/2$.
Then the best response $\pi^*$ is the policy such that $\pi^*(X_t): = \arg\max_{x\in X_{t}}r_{t}(x)$. With hight probability, we have $\sum_{t=1}^T \max_{x\in X_{t}}r_t(x)=T$. However, to reach a sublinear regret, one needs to identify the arms with  reward $1$ in all but $o(T)$ rounds without any prior information. This seems impossible.

Could you please explain more about this?