acceptodds
Under review as a conference paper at ICLR 2027

Optimal Regret Bounds for Linear Bandits with Heavy-Tailed Rewards

Abstract

In heavy-tailed linear bandits, a learner chooses among actions in the -dimensional unit ball, the mean rewards are linear in an unknown parameter, and the rewards only have bounded centered -th moments for some . Even for polynomially many actions, the best known upper and lower regret bounds differ by a factor that grows with . Let . For fixed , sufficiently large , and , we show that the minimax regret over rounds on the hardest set of actions is . Our main contribution is the lower bound, which separates the information shared across actions from the evidence available only at the optimal action. For with , it improves the previous lower bound by a factor of order and matches the known upper bound. We also propose Hybrid FTRL, which estimates the loss of each action by a direct or a linear estimate, whichever has the smaller moment bound. It attains the rate above on every finite action set, including the range where combining existing algorithms falls short. The rate shows that linear structure reduces regret only when exceeds .

Primary area:
learning theory
Keywords:
linear bandits, regret bounds

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_5fZ6OpenReview ↗
Rating
3(+2)
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies the problem of minimax-optimal regret minimization for linear bandits in dimension dd with N≤dBN \leq d^B for some constant B>0B>0, with finite pp-th moment assumption for p∈(1,2]p \in (1,2]. They provide a matching upper and lower bound, showing that the worst-case regret is of order T∧dlog⁡(1+N/dq/2)1/qT1/pT \land \sqrt{d}\log(1+ N/d^{q/2})^{1/q}T^{1/p}, for q=p/(p−1)q = p/(p-1).

Critical strengths

This paper apparently closes an existing gap between upper and lower bounds on linear bandits with heavily-tailed rewards.

Although I am not an expert on those topics, the literature review seems thorough.

Critical weaknesses

This paper is not clear at all. I found some sentences rather difficult to understand (e.g., lines 179, 290, 319, paragraph 353 - 358, 366-367, 381,...). Moreover, some key notations are used in the proofs and sketches of proofs and not introduced in the main text (e.g., ItQI^Q_t, IQ(D,U)I_Q(D,U), vfv_f, FkF_k). The full proof, while written in more detailed, is still hard to follow due to the missing notations, and to the tone being overly concise at the cost of readability.

I do believe that this paper would greatly benefit for an intensive and careful rewriting, and a resubmission.

[Edit] The authors have adequately addressed my concern, and I am happy to raise my score.

Questions for authors

My assessment rests on the fact that I find this paper much too unclear for publication. While it would not make me change my mind, I strongly encourage the authors to clarify the points mentioned above, as well as the following questions, before resubmission :

  • in the proof of the lower bound, are τ\tau and JJ the same stopping time ?
  • Why is the observation W_t in Section 5, while it was previously Y_t ?

I also strongly encourage the authors to ask for an external feedback on the clarity of the writing before resubmission.

5 comments
AuthorsOpenReview ↗

To Reviewer 5fZ6 (1/2)

We sincerely thank you for providing valuable feedback. We detail our response below point by point. Please kindly let us know whether you have any further concerns. If our response addresses your concerns, we would greatly appreciate it if you could reconsider your rating.


W1. Several sentences are difficult to understand (e.g., lines 179, 290, 319, 353–358, 366–367, 381).

R1. Thank you for pointing to the exact lines. We have rewritten each of these passages, and the new text is given below so that the response can be read without the revised paper.

  • Line 179 (Theorem 3.1). "For each such (d,N)(d,N), the lower bound holds on one explicit action set. There is a set A⋆\mathcal A^\star of NN unit vectors, chosen independently of TT, such that RT(A⋆,p)≥cp,Bmin⁡{T,F(d,N)T1/p}\mathfrak R_T(\mathcal A^\star,p)\ge c_{p,B}\min\lbrace T,F(d,N)T^{1/p}\rbrace for every T≥1T\ge 1."
  • Line 290 (why two channels). "Under a bounded pp-th moment, a reward component that shifts the mean by cc can occur with probability as small as order cqc^q, provided that the magnitude of the component is of order c1−qc^{1-q}. The hidden optimum UU shifts the mean of action UU by ρ\rho and the mean of any other action by at most ρκ\rho\kappa. We let the two shifts enter through two separate gates, so the gate that carries the small shift opens H=κ−qH=\kappa^{-q} times less often than the gate that carries the large shift. A reward is informative only when the corresponding gate is open. Hence a pull of a non-optimal action contributes at most rℓ/4=rρ/(4H)r_\ell/4=r_\rho/(4H) to the relative entropy between the auxiliary experiment and the baseline (Lemma 4.2). With a single gate for both shifts, this contribution could be as large as rρκ2/4r_\rho\kappa^2/4, and the argument would give Theorem 4.1 only with H=κ−2H=\kappa^{-2}. For κ\kappa of order d−1/2d^{-1/2}, the dimension factor would then be d1/qd^{1/q} instead of d\sqrt d. At p=2p=2 the two values of HH coincide, and for p<2p < 2 the separation of the two gates is what gives the factor d\sqrt d."
  • Line 319 (the coupling). "We run the true experiment PUP_U and the auxiliary experiment QUQ_U with the same randomness. Both experiments use the same hidden index UU, the same random seed of the policy, the same gate GtG_t in every round, the same uniform random variable that decides the sign of the reward in every round, and the same round JJ. The reward laws of PUP_U and QUQ_U differ only in a round where the diagonal gate is open and action UU is played. The two runs therefore produce the same actions and rewards before the first such round and select the same action in that round. By the definition of the list in (4.3), that round puts UU in the list L(D)L(\mathcal D). If no such round exists, the two runs are identical, so IJP=UI_J^P=U implies IJQ=U∈L(D)I_J^Q=U\in L(\mathcal D)."
  • Lines 353–358 (the action set). "Let b=⌈2B⌉b=\lceil 2B\rceil, let kk be a power of two with d/2<k≤d\sqrt d/2 < k\le\sqrt d, and let Fk\mathbb F_k be the finite field with kk elements. For sufficiently large dd we have k≥2bk\ge 2b. Index the coordinates of Rk2\mathbb R^{k^2} by pairs (x,y)∈Fk×Fk(x,y)\in\mathbb F_k\times\mathbb F_k. For each polynomial ff over Fk\mathbb F_k of degree at most bb, let vfv_f be the vector whose (x,y)(x,y) coordinate is k−1/2k^{-1/2} if y=f(x)y=f(x) and 00 otherwise. Each vector vfv_f has exactly kk nonzero coordinates and hence unit norm, and there are kb+1k^{b+1} such vectors. Two distinct polynomials of degree at most bb agree in at most bb points, so 0≤vf⊤vg≤b/k0\le v_f^\top v_g\le b/k for f≠gf\ne g."
  • Lines 366–367. "The bound (4.6) is proved for this particular set of NN actions and does not follow for a larger action set. The proof uses that every action other than the optimal action has inner product at most κ\kappa with the optimal action, and an added action may violate this condition."
  • Line 381 (Theorem 5.1). "In round tt the learner selects an action ItI_t and observes a loss WtW_t drawn from Pt,ItP_{t,I_t}, independently of the past given ItI_t. Then Hybrid FTRL (Algorithm 1) satisfies (5.1) for every action jj fixed in advance."

We also revised the other proof sketches of Sections 4 and 5 in the same way.

AuthorsOpenReview ↗

To Reviewer 5fZ6 (2/2)

W2. Key notation used in the proofs and proof sketches is not introduced in the main text (e.g., ItQI_t^Q, IQ(D,U)I_Q(D,U), vfv_f, Fk\mathbb F_k), and the full proofs are hard to follow because of missing notation and a very concise style.

R2. Thank you for listing these symbols. Each of these symbols is now defined in the main text where it first appears, and we repeat the definitions here for convenience. The symbols ItPI_t^P and ItQI_t^Q denote the action selected in round tt when the policy interacts with the true experiment PUP_U and with the auxiliary experiment QUQ_U, respectively. The quantity IQ(U;D)I_Q(U;\mathcal D) is the mutual information between the hidden index UU and the data D\mathcal D collected in the auxiliary experiment. The symbol Fk\mathbb F_k denotes the finite field with kk elements. The vector vfv_f has (x,y)(x,y) coordinate k−1/2k^{-1/2} if y=f(x)y=f(x) and 00 otherwise, as in the rewritten lines 353–358 in R1.

To make the full proofs easier to follow, we have made three kinds of changes. First, we expanded the concise passages. The proof sketches of Sections 4 and 5 are now written out in more detail, as in the passages quoted in R1. In the appendices, the proof of Theorem A.1 opens with an overview of its five steps, and Appendix B opens with an outline of the proof of the upper bound. Second, we added a notation table in the new Appendix D. The table lists the main symbols of the paper, each with its meaning and the place where it is introduced, so that the proofs can be read with the table at hand. Third, we revised the wording of the appendices for readability. The appendices now use the same terms as the main text, and each symbol has a single meaning throughout the paper.


Q1. In the proof of the lower bound, are τ\tau and JJ the same stopping time?

A1. Thank you for this question. The quantities JJ and τ\tau are two different objects with different roles in the proof.

The round JJ is drawn uniformly from {1,…,T}\lbrace 1,\dots,T\rbrace, independently of everything else, and is not revealed to the policy (Section 4.3). The purpose of JJ is to express the regret through a probability. Since JJ is uniform and independent, the expected number of rounds in which the policy does not play the optimal action equals T⋅Pr⁡(IJ≠U)T\cdot\Pr(I_J\ne U), so a lower bound on the probability of a mistake in round JJ gives a lower bound on the regret.

The time τ\tau appears only in Appendix A.1 and is the first round of the auxiliary run in which the diagonal gate is open and the policy plays action UU, with τ=∞\tau=\infty if no such round exists. The purpose of τ\tau is the coupling described in R1. The true run and the auxiliary run coincide before τ\tau. If τ≤T\tau\le T, then UU belongs to the list L(D)L(\mathcal D). If τ>T\tau > T, the two runs coincide in every round, and in particular in round JJ. In both cases, IJP=UI_J^P=U implies U∈L(D)U\in L(\mathcal D), and the proof needs exactly this implication.

Appendix A.1 now explains this difference where τ\tau is introduced.


Q2. Why is the observation WtW_t in Section 5, while it was previously YtY_t?

A2. Thank you for this question. The symbol YtY_t denotes a reward, and the symbol WtW_t denotes a loss. Sections 1 to 4 are written for rewards, and Section 5 is written for losses (line 377). We use losses in Section 5 for two reasons. First, FTRL is usually analysed with losses. Second, Theorem 5.1 also covers mean losses that change from round to round, a setting more general than the model of Sections 1 to 4. In the model of Sections 1 to 4, the reward and the loss are related by Wt=−YtW_t=-Y_t (line 386). The revised Section 5 states this relation in the first paragraph, before Theorem 5.1, and the notation table lists both symbols.

Dear Reviewer 5fZ6,

Thank you again for your time and effort in reviewing our paper. As the discussion period is coming to an end, we would like to follow up on our response. We have revised the paper to address all the points raised in your review, and we have also revised other parts of the paper to improve readability. If you have any further questions or concerns, we would be glad to address them before the discussion period ends. If our response and the revision have addressed your concerns, we would greatly appreciate it if you could reconsider your rating.

Reviewer_NzZsOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper characterizes how the minimax regret of finite-action linear bandits depends jointly on the dimension dd and the number of actions NN when rewards are heavy-tailed, meaning that only a centered pp-th moment with p∈(1,2]p\in(1,2] is bounded; let q=p/(p−1)q=p/(p-1). For fixed BB, large dd, and 2≤N≤dB2\le N\le d^B, the authors show that the worst-case regret over sets of NN actions is Θ(min⁡{T,d[log⁡(1+N/dq/2)]1/qT1/p})\Theta(\min\{T,\sqrt d[\log(1+N/d^{q/2})]^{1/q}T^{1/p}\}), closing a gap that grows polynomially in dd when p<2p<2. The lower bound is the main contribution. A learner can find the optimal action either by pulling it or by pulling other actions whose means depend on it, and the authors route these two kinds of evidence through separate rare "gates" in a five-point reward law. Because heavy tails let a small mean shift hide in a rare, large reward, a non-optimal action reveals only a 1/H1/H fraction of what the optimum reveals, where H=κ−qH=\kappa^{-q} and κ\kappa bounds the pairwise inner products of the actions. A list-based Fano argument then bounds direct discoveries of the optimum, and polynomial codes with κ≍d−1/2\kappa\asymp d^{-1/2} give H≍dq/2H\asymp d^{q/2}. For the upper bound, the authors propose Hybrid FTRL, a Tsallis-regularized FTRL method that chooses, separately for each action, between an importance-weighted and a linear loss estimate. All results are theoretical, with no experiments. The takeaway is that, for the hardest action sets, linear structure helps only once NN exceeds dq/2d^{q/2}, which is larger than dd when p<2p<2.

Critical strengths

The lower bound and what it reveals. The main result settles a question the prior work left open. For N=daN=d^a with a>q/2a>q/2, the new lower bound improves the previous one by a factor of order d1/2−1/q(log⁡d)1/qd^{1/2-1/q}(\log d)^{1/q} and meets the known upper bound. For d<N≤dq/2d<N\le d^{q/2}, no algorithm can beat the multi-armed rate N1/qT1/pN^{1/q}T^{1/p}, so heavy tails extend the range in which linear structure is useless from N≤dN\le d to N≤dq/2N\le d^{q/2}. The paper also explains why. Under heavy tails, the information a pull carries about a small mean shift scales with the qq-th power of the shift rather than its square, which makes the evidence shared across actions much weaker. The idea of splitting shared and direct evidence into separate rare channels, then bounding direct discoveries with a list version of Fano's inequality, seems likely to be useful beyond this problem.

Critical weaknesses
  1. The scope is narrower than the title and abstract suggest. Three restrictions add up. First, the result is about the hardest action set, which here is a specific algebraic code. The abstract's claim that linear structure helps only once NN exceeds dq/2d^{q/2} describes this worst case, not every action set. If the actions span only an rr-dimensional subspace, for example, the same upper bound applies with rr in place of dd, and linear structure already helps once NN exceeds rq/2r^{q/2}. The claim should be stated as a worst-case one. Second, the result covers only polynomially many actions, with constants that shrink as the exponent BB grows. This looks like a limit of the method. The lower bound depends on the action set only through its coherence κ\kappa, and standard bounds on spherical codes force κ\kappa to grow with NN. Once NN is exponential in dd, κ\kappa is bounded below by a constant and the argument gives only order d1/qT1/pd^{1/q}T^{1/p}, which is weaker than the earlier bound of Tajdini et al. in that range. Third, the hard instances use reward distributions that differ across actions and whose magnitudes grow with TT. Whether the d\sqrt d factor survives under a common noise law is open, and at p=2p=2 the result says nothing about bounded or Gaussian rewards. The authors acknowledge the first and third points and note that their constants depend on BB. They do not say that the method cannot reach beyond polynomial NN, and the title reads as a general resolution.

  2. The upper bound adds less than the contribution list suggests, and the p=2p=2 case may already be known. Since πiℓi≤1\pi_i\ell_i\le 1, at p=2p=2 the linear estimate always has the smaller moment bound. Hybrid FTRL then never uses the importance-weighted estimate and reduces to a combination of components the paper itself attributes to Ito (2024) and Zhao et al. (2025). For p<2p<2, the new algorithm beats the better of the two existing ones only when N/dq/2N/d^{q/2} grows but stays below any fixed power of dd. Even then the gain is at most of order (log⁡d/log⁡log⁡d)1/q(\log d/\log\log d)^{1/q}. On the lower side, Ito (2024) gives a lower bound matching dTlog⁡(Nmin⁡{1,S/d})\sqrt{dT\log(N\min\{1,S/d\})} for contextual linear bandits with NN actions and SS contexts. If this specializes to a single context, the p=2p=2 rate is already known for bounded rewards, which satisfy the paper's moment condition. The claimed log⁡d\sqrt{\log d} improvement at p=2p=2 would then be measured against the wrong baseline. In that case the paper's value rests on the p<2p<2 lower bound.

Questions for authors
  1. In the hard instance of Section 4.2, does the reward law at action ii depend on (U,i)(U,i) only through the mean μi\mu_i, with the shared channel used when ∣μi∣≤ρκ|\mu_i|\le\rho\kappa and the diagonal channel when μi=ρ\mu_i=\rho? If so, please state it explicitly, since it answers the natural worry that the instance is contrived. Also, is the finite-action hard instance of Tajdini et al. an additive-noise instance? If it is, the old gap is untouched for additive noise, and the abstract should say that the gap is closed for action-dependent reward laws. Do you have any partial result under a common noise law?

  2. Ito (2024) gives a lower bound matching dTlog⁡(Nmin⁡{1,S/d})\sqrt{dT\log(N\min\{1,S/d\})} for contextual linear bandits with NN actions and SS contexts. Does it specialize to a single context and a fixed finite action set? If so, the p=2p=2 rate is already known for bounded rewards, which satisfy your moment condition. Please compare against it in Table 1 and in the gains of Section 3.3, and restate the novelty as the case p<2p<2.

  3. Theorem 4.1 depends on the action set only through (N,κ)(N,\kappa), so its strength is capped by bounds on spherical codes. By Alon's rank lemma, NN unit vectors in Rd\mathbb{R}^d with coherence κ\kappa require log⁡N≲dκ2log⁡(1/κ)\log N\lesssim d\kappa^2\log(1/\kappa). At N=dBN=d^B this forces κ≳B/d\kappa\gtrsim\sqrt{B/d}, so any code loses a factor of order at least B\sqrt B against the upper bound, and the polynomial code loses order BB. At N=2cdN=2^{cd} it forces κ=Ω(1)\kappa=\Omega(1), and Theorem 4.1 gives only order d1/qT1/pd^{1/q}T^{1/p}, below the bound of Tajdini et al. Is this reading correct? If so, the polynomial restriction is a limit of the method, and the paper should state so. It should also state the best known lower bound for super-polynomial NN and note that the d\sqrt d in the main rate is exactly the Welch limit on coherence. Whether d[log⁡(N/dq/2)]1/q\sqrt d[\log(N/d^{q/2})]^{1/q} is the right rate beyond polynomial NN is a question for future work.

  4. Since πiℓi≤1\pi_i\ell_i\le 1, the hybrid rule seems to always select the linear estimate at p=2p=2. Can you confirm this, and quantify the range of NN in which Hybrid FTRL improves on the better of Robust MOSS and Zhao et al.? My calculation gives an improvement only when N/dq/2N/d^{q/2} grows but stays below any fixed power of dd, and then by at most (log⁡d/log⁡log⁡d)1/q(\log d/\log\log d)^{1/q}. If this is right, the third contribution should be presented as a refinement for p<2p<2 in that range.

Suggestions

Presentation. Notation is heavily reused across sections, which makes the paper hard to follow. For example, ℓ\ell is both the shared-signal bound and the leverage score, ν\nu is both the instance and the design, and π\pi is both the policy and the sampling distribution. Likewise, hh, LL, GG, QQ, DD, ss, vv and rr each carry two or more meanings. Some quantities are used before they are defined, such as MM in Section 3.2 and the branch names and tuning parameters in Section 5.3, which come before Algorithm 1. "Linear cap," "virtual regret," "admissible (d,N)(d,N)" and "direct hits" are never defined. A notation table and renamed symbols would help a lot.

6 comments
AuthorsOpenReview ↗

To Reviewer NzZs (1/4)

We sincerely thank you for the careful review and the constructive questions. We have carefully considered your concerns and provided a detailed explanation below. Please feel free to let us know if you have any additional concerns or questions.


W1 (first point). The result is about the hardest action set, and the claim that linear structure helps only once NN exceeds dq/2d^{q/2} should be stated as a worst-case claim. On a set spanning rr dimensions, linear structure already helps once NN exceeds rq/2r^{q/2}.

R1 (first point). Thank you for this suggestion, which we have followed in the revised paper. The last sentence of the abstract and the corresponding sentences in the introduction and in the conclusion now say that linear structure helps only once NN exceeds dq/2d^{q/2} in the worst case over action sets. We have also added the observation about low-dimensional action sets after Theorem 5.1. When the actions span an rr-dimensional subspace, applying Theorem 5.1 inside this subspace gives the upper bound with rr in place of dd. The revised paper writes dAd_{\mathcal A} for this dimension. On such an action set, the upper bound therefore improves on the independent-arm rate once NN exceeds rq/2r^{q/2}.


W1 (second point) & Q3. The result covers only polynomially many actions, with constants that shrink as BB grows. Theorem 4.1 depends on the action set only through (N,κ)(N,\kappa), so bounds on spherical codes make this a limit of the method. The paper should state this, give the best known lower bound for super-polynomial NN, and note that d\sqrt d is the Welch limit.

R1 (second point) & A3. Thank you for this careful analysis. Your reading is correct. The revised paper discusses the range of the coherence argument in a new paragraph at the end of Section 4.4 and in the new Appendix A.5, and the new paragraph covers the three points raised in the review.

First, the Welch bound gives κ≥1/2d\kappa\ge 1/\sqrt{2d} whenever N≥2dN\ge 2d, so H≤(2d)q/2H\le(2d)^{q/2}. The factor d\sqrt d in our rate is therefore the largest dimension factor that Theorem 4.1 can give, and our construction attains this factor.

Second, at N=dBN=d^B with fixed B>1B > 1 and large dd, Alon's rank lemma [1] gives κ≳B/d\kappa\gtrsim\sqrt{B/d}, and our polynomial code has κ=⌈2B⌉/k\kappa=\lceil 2B\rceil/k with d/2<k≤d\sqrt d/2 < k\le\sqrt d. The coherence of our code is therefore within a factor of order B\sqrt B of the smallest possible value, and the coherence of our code is the source of the dependence of the constant on BB. The revised paper states that the constant of Theorem 3.1 can be taken as cp,B=cp/(2⌈2B⌉)c_{p,B}=c_p/(2\lceil 2B\rceil), where cpc_p is the constant of Theorem 4.1.

Third, for NN exponential in dd, the coherence κ\kappa is bounded below by a constant, and the bound of Theorem 4.1 is at most of order d1/qT1/pd^{1/q}T^{1/p}. In this regime, Tajdini et al. [2] give the lower bound Ω(d1/q(log⁡N/log⁡d)1/qT1/p)\Omega(d^{1/q}(\log N/\log d)^{1/q}T^{1/p}) for d≤N≤2⌊d/4⌋d\le N\le 2^{\lfloor d/4\rfloor} and T≥4qdqT\ge 4^qd^q. The upper bound of Theorem 5.1 continues to hold, because Theorem 5.1 applies to every finite action set.

Theorem 4.1 therefore matches the upper bound for polynomially many actions with fixed BB, and the new paragraph states this range explicitly. Determining the minimax rate beyond polynomially many actions is left for future work, as noted in the conclusion.

AuthorsOpenReview ↗

To Reviewer NzZs (2/4)

W1 (third point) & Q1. The hard instances use reward laws that differ across actions, with magnitudes that grow with TT. Does the law at action ii depend on (U,i)(U,i) only through the mean μi\mu_i? Is the finite-action hard instance of Tajdini et al. an additive-noise instance? Is there a partial result under a common noise law?

R1 (third point) & A1.

Dependence on the action. The reward law at action ii depends on (U,i)(U,i) only through the mean μi\mu_i, with the shared channel used when ∣μi∣≤ρκ|\mu_i|\le\rho\kappa and the diagonal channel used when μi=ρ\mu_i=\rho. For μ∈[−ρ,ρ]\mu\in[-\rho,\rho], let PμP_\mu be the law on {0,±Bℓ,±Bρ}\lbrace 0,\pm B_\ell,\pm B_\rho\rbrace with

Pr⁡(Y=±Bℓ)=rℓ2(1±μ2ℓ1{∣μ∣≤ℓ}),Pr⁡(Y=±Bρ)=rρ2(1±μ2ρ1{∣μ∣>ℓ}),\Pr(Y=\pm B_\ell)=\frac{r_\ell}{2}\Big(1\pm\frac{\mu}{2\ell}\mathbf 1\lbrace |\mu|\le\ell\rbrace \Big),\qquad \Pr(Y=\pm B_\rho)=\frac{r_\rho}{2}\Big(1\pm\frac{\mu}{2\rho}\mathbf 1\lbrace |\mu| > \ell\rbrace \Big),

and the remaining probability at 00, where ℓ=ρκ\ell=\rho\kappa and rℓ,rρ,Bℓ,Bρr_\ell,r_\rho,B_\ell,B_\rho are as in (4.2). Since ∣μi∣≤ρκ|\mu_i|\le\rho\kappa for i≠Ui\ne U and μU=ρ\mu_U=\rho, the reward law in (4.2) is PU,i=PμiP_{U,i}=P_{\mu_i}. The revised paper states this explicitly in a new paragraph at the end of Section 4.2.

The instance of Tajdini et al. The finite-action hard instance of Tajdini et al. [2] also uses reward laws that depend on the action. In the proof of [2, Theorem 2], the reward of action xx equals γ−1/ϵ\gamma^{-1/\epsilon} with probability γ1/ϵθ⊤x\gamma^{1/\epsilon}\theta^\top x and equals 00 otherwise, where p=1+ϵp=1+\epsilon. This reward is a scaled Bernoulli variable whose success probability is proportional to the mean, so the noise law depends on the action through the mean, as in our instance. The previous lower bound and our lower bound are therefore proved in the same model, and Table 1 compares the two bounds within this model.

Common noise law. For p<2p < 2 and fixed (d,N)(d,N), a lower bound of order T1/pT^{1/p} cannot hold for all large TT under a common noise law. Suppose that Y=μi+ξY=\mu_i+\xi, where the noise ξ\xi is i.i.d. with a law that does not depend on the action and E∣ξ∣p≤1\mathbb E|\xi|^p\le 1. The difference between a reward of action ii and a reward of action jj then equals μi−μj\mu_i-\mu_j plus the symmetric noise ξ−ξ′\xi-\xi', and a short calculation gives Pr⁡(∣ξ−ξ′∣≤ε)≥ε/20\Pr(|\xi-\xi'|\le\varepsilon)\ge\varepsilon/20 for every 0<ε≤10 < \varepsilon\le 1. The median of nn such differences therefore estimates μi−μj\mu_i-\mu_j with accuracy of order n−1/2n^{-1/2} for every p>1p > 1, and successive elimination based on these medians has regret of order NTlog⁡(NT)\sqrt{NT\log(NT)}, which grows more slowly than T1/pT^{1/p} for fixed (d,N)(d,N). A lower bound with the time exponent 1/p1/p therefore needs reward laws that depend on the action. This argument is in line with the symmetric-noise results of Zhong et al. [3]. The elimination bound does not use the linear structure, and the joint dependence of the minimax regret on (d,N,T)(d,N,T) under a common noise law is an open question that we leave for future work. The revised paper includes this discussion in the new paragraph at the end of Section 4.2, and the proof is in the new Appendix A.4.

Magnitudes growing with TT. For p<2p < 2, a bound on the rewards that is uniform in TT would allow regret of order dTlog⁡N\sqrt{dT\log N} up to logarithmic factors, which is below T1/pT^{1/p} for fixed (d,N)(d,N) and large TT. Our construction therefore uses reward magnitudes that grow with TT.

AuthorsOpenReview ↗

To Reviewer NzZs (3/4)

W2 (upper bound) & Q4. At p=2p=2 the hybrid rule always selects the linear estimate, and for p<2p < 2 Hybrid FTRL improves on the better of Robust MOSS and Zhao et al. only when N/dq/2N/d^{q/2} grows but stays below any fixed power of dd. The third contribution should be presented as a refinement for p<2p < 2 in that range.

R2 & A4.

The case p=2p=2. At p=2p=2, the inequality πt,iℓt,i≤1\pi_{t,i}\ell_{t,i}\le 1 gives ℓt,i≤πt,i−1\ell_{t,i}\le\pi_{t,i}^{-1}, so the moment bound of the linear estimate is never larger than that of the direct estimate. Up to ties, Hybrid FTRL with N>dN > d therefore uses linear estimates only. The resulting bound has the same leading term as the bound of Ito [4, Corollary 1], and the resulting bound holds under a bounded second moment instead of bounded losses and for every T≥1T\ge 1.

The range for p<2p<2. Let x=N/dq/2x=N/d^{q/2}, and recall that G(d,N)G(d,N) in (3.4) is the factor of the better of the two previous upper bounds. The definitions (3.2) and (3.4) give G(d,N)/F(d,N)=[min⁡{x,log⁡N}/log⁡(1+x)]1/qG(d,N)/F(d,N)=[\min\lbrace x,\log N\rbrace /\log(1+x)]^{1/q}. The factor FF is of smaller order than the factor GG exactly when x→∞x\to\infty with log⁡x=o(log⁡d)\log x=o(\log d). The ratio G/FG/F is at most of order (log⁡d/log⁡log⁡d)1/q(\log d/\log\log d)^{1/q}, and this value is attained when xx is of order log⁡d\log d. For N≤dq/2N\le d^{q/2}, and for N=dq/2+εN=d^{q/2+\varepsilon} with fixed ε>0\varepsilon > 0, the factors FF and GG agree up to constants.

Changes in the paper. The third contribution in the introduction now presents Hybrid FTRL as a refinement of the previous upper bounds for p<2p < 2 in this range, and Section 3.3 contains the formula for G/FG/F given above. The third contribution also states the role of Hybrid FTRL in the main theorem, namely that a single algorithm attains the upper bound with constants that do not depend on (d,N)(d,N) over the whole range 2≤N≤dB2\le N\le d^B, and Theorem 3.1 requires this uniformity. As part of the notation changes, the revised paper writes σt,i\sigma_{t,i} for ℓt,i\ell_{t,i} and FprevF_{\mathrm{prev}} for GG.


W2 (p=2p=2) & Q2. Ito (2024) gives a lower bound matching dTlog⁡(Nmin⁡{1,S/d})\sqrt{dT\log(N\min\lbrace 1,S/d\rbrace )} for contextual linear bandits. If this lower bound specializes to a single context and a fixed finite action set, the p=2p=2 rate is already known for bounded rewards, and the log⁡d\sqrt{\log d} gain is measured against the wrong baseline.

R2 & A2. Thank you for pointing to this result. The lower bound of Ito [4, Corollary 2] is stated for K≤2d≤KSK\le 2^d\le K^S, where KK is the number of actions and SS is the number of contexts. For a single context, this condition holds only at K=2dK=2^d, and the bound then equals the Ω(dT)\Omega(d\sqrt T) bound of Dani et al. [5], since the proof of [4, Theorem 4] uses SS copies of the hypercube instance of [5]. For linear bandits without contexts, [4, Section 1] notes that the upper bound O(dTlog⁡+(K/d))O(\sqrt{dT\log_+(K/d)}) is matched by lower bounds at K=dK=d and at K=2dK=2^d, and lists the minimax rate for other values of KK as an open problem. The table below summarizes the lower bounds at p=2p=2.

RewardsLower boundRange of NN
Bounded [4, Table 1]Ω(dT)\Omega(\sqrt{dT})N=dN=d
Bounded [5]Ω(dT)\Omega(d\sqrt T)N=2dN=2^d
Bounded, SS contexts [4, Corollary 2]Ω(dTlog⁡(Nmin⁡{1,S/d}))\Omega(\sqrt{dT\log(N\min\lbrace 1,S/d\rbrace )})N≤2d≤NSN\le 2^d\le N^S
Bounded second moment [2]Ω(dTlog⁡N/log⁡d)\Omega(\sqrt{dT\log N/\log d})d≤N≤2⌊d/4⌋d\le N\le 2^{\lfloor d/4\rfloor}
Bounded second moment (ours)Ω(dTlog⁡(1+N/d))\Omega(\sqrt{dT\log(1+N/d)})2≤N≤dB2\le N\le d^B

In the table, NN denotes the number of actions, and all bounds hold for sufficiently large TT. For a fixed set of N=daN=d^a actions with a>1a > 1, the previous lower bound in our model is the bound of [2], and the log⁡d\sqrt{\log d} gain in Section 3.3 is measured against this bound. At p=2p=2, Theorem 3.1 shows that dTlog⁡(1+N/d)\sqrt{dT\log(1+N/d)} is the minimax rate for polynomially many actions when the rewards have a bounded second moment. As Section 3.2 states, this model is larger than the model of bounded losses, so the open problem of [4] for bounded losses is a separate question that remains open. Section 3.3 now contains this comparison with [4]. The bound of [4, Corollary 2] applies to a single context only at N=2dN=2^d, which is outside the range N≤dBN\le d^B of Theorem 3.1, so the comparison is placed in the text of Section 3.3 and not in Table 1.

Reviewer_qR5mOpenReview ↗
Rating
4
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies stochastic linear bandits with heavy-tailed rewards, where the only assumption on observation noise is a bounded pp-th moment for 1<p≤21 < p \le 2. They prove a regret lower bound of Ω~(d(log⁡N)1−1/pT1/p)\tilde{\Omega}(\sqrt{d} (\log N)^{1 - 1/p} T^{1/p}) for action set of size NN, closing the minimax regret dimension gap with prior known upper bound. They also propose a new FTRL based algorithm which achieves the optimal logarithmic factors as well, removing the extra polylog⁡dpoly\log d factor from prior upper bounds.

Critical strengths
  • the major contribution is the lower bound construction and proof. the paper introduces a new class of heavy tailed reward functions where instead of scaled Bernoulli in prior lower bounds they have two informative magnitudes in the support, allowing for smaller KL divergence between the optimal arm and suboptimal arms, while preserving the bounded moment condition. Another technique used is coupling of the bandit instance with another instance modifying the optimal arm reward, and showing distinguishing between the two instances is statistically insignificant.
Critical weaknesses
  • The lower bound is only for finite arm linear bandits using action sets with small inner products between all pairs of arms. minimax regret for canonical action sets in linear bandits such as unit ball and hypercube remain open.
Questions for authors
  • The FTRL based algorithm in [1] also achieves the same regret upper bound for adversarial algorithm while achieving instance dependent regret bounds in stochastic setting. Does Algorithm 1 achieve the same regret bounds, thus improving on prior instance dependent and best of both worlds upper bound? Was there a technical challenge preventing such an extension?

  • Can the lower bound be extended to an infinite action set such as hypercube? The coupling technique used in the current proof is no longer viable in such action set, but perhaps removing a region of near optimal arms instead of only the best arm can solve this?

[1] Zhao, Canzhe, Shinji Ito, and Shuai Li. "Heavy-tailed linear bandits: Adversarial robustness, best-of-both-worlds, and beyond." arXiv preprint arXiv:2508.13679 (2025).

1 comment
AuthorsOpenReview ↗

To Reviewer qR5m

We are very grateful for your careful reading of our paper and for your strong support. We especially appreciate your recognition of the lower-bound construction and of the coupling argument. Both of your questions point to directions that we find very valuable, and we respond to them below. Please feel free to let us know if you have any additional questions.


W1 & Q2. The lower bound holds only for finite action sets with small pairwise inner products, and the unit ball and the hypercube remain open. Can the lower bound be extended to an infinite action set such as the hypercube, perhaps by removing a region of near-optimal arms instead of only the best arm?

R1 & A2. Thank you for this valuable suggestion. Removing a region of near-optimal arms instead of only the best arm fits our argument well. In our proof, the true and the auxiliary trajectories coincide until the best arm is played while the diagonal gate is open. If the auxiliary experiment removes the signal of every action in the region, the two trajectories coincide in the same way until an action of the region is played while the diagonal gate is open, so the coupling extends as suggested. The step that we have not yet completed is the choice of the size of the region, because two parts of the proof pull in opposite directions on this choice. If the region is small, the actions just outside the region are still strongly correlated with the optimum. Playing these actions then reveals more about the location of the optimum through the shared channel, and the dimension factor in the bound becomes smaller. If the region is large, a single action belongs to the regions of many candidate optima. Each round in which the diagonal gate is open then adds many candidates to the list instead of one, and the list is no longer short enough for the argument. We will study this extension carefully in future work, and we believe that the extension is a promising route to a lower bound for the hypercube and the unit ball.


Q1. The FTRL algorithm of [1] attains the same adversarial bound together with instance-dependent bounds in the stochastic setting. Does Algorithm 1 achieve the same, and was there a technical challenge preventing such an extension?

A1. Thank you for pointing out this connection. Our paper discusses [1] in several places. Sections 1 to 3 compare our bounds with the upper bound of [1], and Hybrid FTRL in Section 5 uses the clipping and the bias correction of [1]. Theorem 5.1 is proved against an oblivious adversary, so the guarantee of Algorithm 1 already covers the adversarial setting. For the stochastic setting, we have not yet established instance-dependent bounds, and two ingredients are missing. The first ingredient is the tuning. Algorithm 1 fixes the clipping scale, the learning rate and the exploration rate in advance as functions of the horizon TT, whereas the best-of-both-worlds result of [1] relies on a learning rate that adapts to the observed data (HT-SPM). The second ingredient is the estimator. The analysis of [1] needs a self-bounding condition, which the standard least-squares estimator does not satisfy, and [1] introduces a variance-reduced linear estimator for this purpose. The same condition would have to be verified for our hybrid estimator. A natural next step is therefore to combine the hybrid estimator with the adaptive learning rate of [1] and to verify the self-bounding condition, and we leave this step for future work.

[1] C. Zhao, S. Ito, and S. Li. Heavy-tailed linear bandits: Adversarial robustness, best-of-both-worlds, and beyond. arXiv:2508.13679, 2025.

Comments on the paper

1 comment
AuthorsOpenReview ↗

To All Reviewers

We sincerely thank all reviewers for the careful reviews and the constructive comments. We have responded to each reviewer point by point and revised the paper accordingly. The new and rewritten text is marked in blue.

The theorems and the arguments of their proofs are the same as in the submission. Most changes concern notation and readability, and the other changes add the discussions requested by the reviewers. The main changes are as follows.

  1. Clarity and notation (5fZ6; NzZs Suggestion). The passages that Reviewer 5fZ6 found difficult are rewritten, together with the other proof sketches of Sections 4 and 5. Every symbol used in the main text is defined there, each symbol has a single meaning, and the new Appendix D contains a notation table. The full proofs in Appendices A and B now begin with outlines of their steps.
  2. Scope of the lower bound (NzZs W1, Q1, Q3). The abstract, the introduction and the conclusion state the threshold N=dq/2N=d^{q/2} as a worst case over action sets. New paragraphs at the end of Sections 4.2 and 4.4 discuss common noise laws and the range of the coherence argument, with the proofs in the new Appendices A.4 and A.5.
  3. The case p=2p=2 and the upper bound (NzZs W2, Q2, Q4). Section 3.3 now compares our bounds at p=2p=2 with those of Ito (2024) and gives the range of NN in which our upper bound is of smaller order than the previous upper bounds.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.