Variance-Dependent Regret Lower Bounds for Contextual Bandits
Authors: Jiafan He
Quanquan Gu
Venue: ICLR 2026 Poster (2026)
Keywords: Bandit
Reinforcement Learning
Primary area: reinforcement learning

Abstract: Variance-dependent regret bounds for linear contextual bandits, which improve upon the classical $\tilde{O}(d\sqrt{K})$ regret bound to $\tilde{O}(d\sqrt{\sum_{k=1}^K\sigma_k^2})$, where $d$ is the context dimension, $K$ is the number of rounds, and $\sigma^2_k$ is the noise variance in round $k$, has been widely studied in recent years. However, most existing works focus on the regret upper bounds instead of lower bounds. To our knowledge, the only lower bound is from Jia et al. (2024), which proved that for any eluder dimension $d_{\textbf{elu}}$ and total variance budget $\Lambda$, there exists an instance with $\sum_{k=1}^K\sigma_k^2\leq \Lambda$ for which  any algorithm incurs a variance-dependent lower bound of $\Omega(\sqrt{d_{\textbf{elu}}\Lambda})$. However, this lower bound has a $\sqrt{d}$ gap with existing upper bounds. Moreover, it only considers a fixed total variance budget $\Lambda$ and does not apply to a general variance sequence $\{\sigma_1^2,\ldots,\sigma_K^2\}$.
In this paper, to overcome the limitations of Jia et al. (2024), we consider the general variance sequence under two settings. For a prefixed sequence, where the entire variance sequence is revealed to the learner at the beginning of the learning process, we establish a variance-dependent lower bound of $\Omega(d \sqrt{\sum_{k=1}^K\sigma_k^2 }/\log K)$ for linear contextual bandits. For an adaptive sequence, where an adversary can generate the variance $\sigma_k^2$ in each round $k$ based on historical observations, we show that when the adversary must generate $\sigma_k^2$ before observing the decision set $D_k$, a similar lower bound of $\Omega(d\sqrt{ \sum_{k=1}^K\sigma_k^2} /\log^6(dK))$ holds. In both settings, our results match the upper bounds of the SAVE algorithm (Zhao et al. 2023) up to logarithmic factors. Furthermore, if the adversary can generate the variance $\sigma_k$ after observing the decision set $D_k$, we construct a counter-example showing that it is impossible to construct a variance-dependent lower bound if the adversary properly selects variances in collaboration with the learner.
Our lower bound proofs use a novel peeling technique that groups rounds by variance magnitude. For each group, we construct separate instances and assign the learner distinct decision sets. We believe this proof technique may be of independent interest.

Variance-deepndent regret bounds for linear contextual bandits, which improve upon the classical (dv regret bound to Ö(d Ex_ of), where d is the con- text dimension, K is the number of rounds, and of is the noise variance in round k, has been widely studied in recent years. However, most existing works focus on the regret upper bounds instead of lower bounds. To our knowledge, the only lower bound from Jia et al. (0024), which proved that for any eluder dimen- sion detu and total variance budget A, there exists an instance with Σ Σt=r of S for which any algorithm incurs a variance-dependen: lower bound of ())duA)) However, this lower bound has a vd gap with existing upper bounds. More- over, it only considers fixed total variance budget A and does not apply to general variance sequence [a?....,ok] ). In this paper, to overcome the limita- tions of Jia et al.] (2024), we consider the general variance sequence under two Published as a conference paper at ICLR 2026
VARIANCE-DEPENDENT REGRET LOWER BOUNDS FOR CONTEXTUAL BANDITS
Jiafan He
Quanquan Gu
Department of Computer Science University of Californi, Los Angeles Los Angeles, CA 90095 j Lafaahel 90ucla edu
Department of Computer Science University of California, Los Angeles Los Angeles, CA 90095 qguêcs ucla.
ABSTRACT
settings. For a prefixed sequence, where the entire variance sequence is revealed the learner at the beginning of the learning process, we establish a variance-
dependent lower bound of ((d Ek= of/ log K)) for linear contextual bandits.
For adaptive sequence, where adversary can generate the variance of in each round k based on historical observations, we show that when the adversary must generate of before observing the decision Da. similar lower bound
of (2dv Ek=n / (dK)) holds. In both settings, our results match the up- per bounds of the SAVE algorithm (Zhao et al.] 2023) up to logarithmic factors. Furthermore, the adversary can generate the variance d after observing the decision set DR. we construct counter-example showing that it is impossible to construct a variance- meriance-dependent lower bound if the adversary properly selects variances in collaboration with the learner. Our lower bound proofs use novel peeling technique that groups rounds by variance magnitude. For each group, we construct separate instances and assign the learner distinct decision sets. We believe this proof technique may be of independent interest.
INTRODUCTION
We consider the linear contextual bandit problem, where each arm is represented by a feature vector and the expected reward is linear function of this feature vector with an unknown parameter vec- for. Numerous studies have developed algorithms achieving optimal regret bounds for linear bandits (Chu et al., 2011 Abbasi- Yadkori al.) (01T). However, while these works establish minimax- optimal regret bounds in the worst-case, they do not exploit additional problem-dependent struc- tures. Our work focuses on incorporating reward variance information into the analysis, building upon line of research studying variance-dependent regret bounds for linear bandits (Zhou et al. 2021 Zhang et al., 2021 Zhou & Gul [2022] Zhao et al. 2022 Kim et al. 2022; Zhao et al.) (002) and general function approximation (Jia et al. 2024), which includes linear bandits special case. Notably, Zhao et al. (2023) established a near-optimal regret guarantee without requiring prior knowledge of the variances:

---

Published as a conference paper at ICLR 2026
Theorem 1.1 (Theorem 2.3, Zhao et al. (023). For any linear contextual bandit problem, the regret of the SAVE algorithm in the first K rounds is upper bounded by:
Regret(K) s =((d Odv
where di is the dimension and of is the noise variance of the selected action in round k.
However, most of these works have focused on developing algorithms with regret upper bound guarantees, while variance-dependent lower bounds remain understudied. The only exception Jia et al. (2024), which focuses general function classes with finite eluder dimension delu and provides the following variance-dependent lower bound:
Theorem 1.2 (Theorem 5.1, Jia et al. 2024). For any dimension d 2 2, action space size A, number of rounds K 2 2, and total variance budget A E [0, K]. there exists a contextual bandit problem with eluder dimension detu- d, action space size A, and adversarial sequence of variances satisfying Σ o I A such that for any algorithm, the regret lower bounded by:
K
Regret(K)) 2 Q2 (mimm(( VdA + d, VAK)).
When restricted to the linear bandit case, where d 2 VA, the above lower bound reduces to v VdA. which has gap of vd factor compared with the upper bound in Zhao et al. (2023). Moreover, Jia itt al. (2024) only considers instances with a fixed budget and relies on carcfully designed vari- ance sequences {of, o2. ... ). failing provide lower bounds for general variance sequences. Therefore, an open question arises:
Can we prove variance-dependent regret lower bounds for general variance sequences?
OUR CONTRIBUTIONS
In this paper, we answer this question affirmatively by constructing hard-to-lcarn instances in sev- }. we achieve Mdy Σx k= of
eral different settings. For any prefixed sequence .o?....,
variance-deppeddent expected lower bound, which matches the upper bound in Zhao et al. (2023) up to logarithmic factors and demonstrates its optimality. For general adaptive variance sequences where weak adversary (potentially collaborating with the learner) can generate variance of in each round & based on historical observations, our instance provides a high-probability lower bound of /
Oid / - which also matches the upper bound in Zhao et al. (2023) up to logarithmic fac- tors. To the best of our knowledge, this is the first high-probabiling lower bound for linear contextual bandit.
Our construction and analysis rely on the following new techniques:
A peeling technique for prefixed variance sequences that divides rounds into groups based on variance magnitude. Through orthogonal decision set construction, each group only interacts with its corresponding parameters, allowing us to establish separate lower bounds for different variance scales and combine them effectively.
A multi-instance framework that handles unknown group sizes in the adaptive setting. For each variance group, we maintain multiple instances designed for different possible intervals of round numbers and assign the learner these instances in a cyclic manner, ensuring uniform visits across instances and guaranteeing the visiting times of one instance matches its designed interval.
A gig-prrobability lower bound that handles adaptive group sizes through a union bound. We first convert expected regret bounds to constant- probabityr bounds through careful variance trol and auxiliary algorithms, then boost these to high-probability bounds by creating multiple independent instances.
Furthermore, we also study the setting with a strong adversary that can generate the variance o after observing the decision set Dz. Under this scenario, we proposed a counter algorithm that can collaborate with the adversary by properly selecting variance, achieving an (d)) regret even the total variance ΣK of S(K). This implies that it is impossible to derive variance-dependent lower bound for general variance sequence with strong adversary. As direct extension of this result, we also show that is impossible derive a puriance-dependees lower bound for stochastic linear bandits, where the decision set is fixed even for a general prefixed variance sequence.
Notation We use lower case letters to denote scalars, and use lower and upper case bold face letters to denote vectors and matrices respectively. We denote by [n] the set (1.....n). For vector
2

---

Published as a conference paper at ICLR 2026
I'' and positive semi-definite matrix Σ E Rdxd we denote by ||x|| the vector's Eg norm and by ||x|x = vx Σx the Mahalanobis norm. For two positive sequences {an] and {6x} with = 1. 2, .... we write On (b.,) if there exists an absolute constant C' > 0 such that on I Cb2, holds for all 2 1 and write an (b,,,) if there exists an absolute constant C > such that an 2 Cb2 holds for all n 2 1. We use (-) to further hide the polylogarithmic factors. We use {.}
to denote the indicator function.
2 RELATED WORK
Heteroscedastic Linear Bandits. For linear bandit problems, the worst-case regret has been widely
studied (Auer
2002 Dani et al.] 22008] Li et al. 2010 Chu et al., 2011; Abbasi-Yadkori et al.)
2011 Li et al. 2019), achieving O(vK) bounds in the first K rounds. Recently, series of works has considered heteroscedastic variants where noise distributions vary across rounds. Kirschner &
Krause (2018) first formally proposed a linear bandit model with heteroscedastic noise, assuming
0g-Sub- Gaussian noise in round k E [K]. Subsequently, (Zhou et al. 2021 Zhang et al., 2021
T2-sub-Gaussian
Kim et al.] 2022 Zhou & Gu. 2022 Dai et al.) (Zhao al.) |023] Jia et al. 2024) relaxed this to variance-based constraints where round l has variance of Among these works, Zhou et al. 2021
and Zhou & Gu (202)) obtained near-optimal regret guarantees of Od Σt= 2)
) but required knowledge of d% after observing the reward in round k. In contrast, ZZang et al. (2021): Kim et al. (022) handled unknown variances with computationally inefficient algorithms, achieving weaker
(ppoly(d) Σx= x3) bound. Recently, Zhao et al. 2023) improved upon these results with an
efficient algorithm (SAVE) achieving the near-optimal Ö(dy Σ o bound without requiring
variance knowledge. Beyond standard linear bandits, two directions have been explored. Dai et al. studied heteroscedastic sparse linear bandits, providing a framework to convert standard algorithms to the sparse setting. In different direction, Jia al. (2024) extended the analysis to contextual bandits with general function classes having finite eluder dimension, which includes linear bandits as special case, and achieved variance-dependent regret upper bounds.
Lower Bounds for Linear Contextual Bandits. For linear contextual bandit problems, several works (Dani et al., 2008 Chu al. 2011 Li al., (2099) have established theoretical lower bounds to illustrate the fundamental difficulty in learning process. For linear bandits with finite action sets, Chu et al. 2011 1) established an (((vK) lower bound, matching the upper bound up to logarithmic factors in the action set size and number of rounds K. For general stochastic linear bandits, Dani ct al. 2008) constructed an instance with 20(d) actions and obtained an ((dvK) lower bound. Later, Li et al. (2019) focused on linear contextual bandits, where the decision set can vary across rounds, and provided an (2dk/ log K) lower bound. However, all these works only focus on worst-case regret bounds and do not consider the heteroscedastic variance information. The only exception is Jia et al. 2024)) which provided an ((VdA) variance-dependent lower bound for fixed total variance budget A. Nevertheless, this work cannot handle general variance sequences and leaves open the question of variance dependent lower bounds in the general setting.
Variance-dependent Bounds for Multi-armed Bandits. |Auer et al. (2002) studied a multi-armes bandit problem in which the rewards are normally distributed with unknown mean and variance, and proposed the UCB (CB1-NORMAL algorithm, which achieves a variance-dependent regret bound o
of Õ 1, Ae A. + As) log K). Here o? is the variance of the reward for the i-th arm, A; is the suboptimality gap between i-th arm and the best arm, n is the number of arms, and K is the number of rounds. Audibert et al. (2009) considered multi-armed bandit (MAB) problem with bounded reward (by b > 0) and unknown mean and variance. They proposed the UCB-V algorithm that
regret bound of i of A. + b) log K. They also established a matching lower bound. Variance-dependee regret bounds have also been established for best-arm identification problem (Audibert & Bubeck 2010) in multi-armed stochastic handits. For example, Lu et al. (202T) studied the best-arm identification problem in stochastic multi-armed bandits, and
achieves a periance-dependee
+ ). They also proposed an algorithm that achieves a nearly matching upper bound. Lalitha et al. (2023) studied fixed- budget best-arm identification with heterogeneous reward variances. It is worth noting that these variance- dependent regret results for MAB rely on the assumption that the arms are fixed. Consequently, the sub-optimality gap A, and the variance of are assumed to remain constant across all rounds.
proved variance dependent lower bound of "( A
n²
3

---

Published as a conference paper at ICLR 2026
In sharp contrast, focus is on the linear contextual bandits, where the decision set Dj changes adaptively. This change depends on the history of actions and rewards, meaning the set of available arms (and even the size of the action set) is not fixed.
PRELIMINARIES
In this work, consider the heteroscedastic linear contextual bandit (Zhou al. 2021 Zhang jet al. 2. where the noise variance varies across rounds. Let K be the total number of rounds. In each round [K], the interaction between the learner and the environment proceeds follows:
1. The environment generates an arbitrary decision set D3 S RR, where each element repre- sents a feasible action that can be selected by the learner;
2. The learner observes Dj and selects X₃ E DR:
3. The environment generates the stochastic noise e and reveals the stochastic reward ra: (n,, X&) + C to the learner, where μ E Rd is the unknown weight vector for the underlying linear reward function.
Without loss of generality, we assume the random noise eg in each round & satisfies:
P([eR] - R)
E[Ea|XiR c1a-11] O, Ele Miak f1. = o S 1, Vk E
(3.1)
For any algorithm Alg and linear bandit instance M, the cumulative regret defined as follows:
Regret Alg MK, = Σ (x) (Xk, where x = arg max (x, 14).
(3.2)
xED,
KE[K]
For simplicity, may omit the subscripts Alg and/or M when there is ambiguity. Additionally, with a slight abuse of notation, we may use 0g to represent the variance of (which originally the standard deviation) when there is no ambiguity. In this work, focus providing variance- dependent lower bounds for the regret based on the variances sequence {o1,..,, o We consider two settings for the variance sequence {o [k].
oK):
Prefixed Sequence: The variance sequence is revealed to the learner at the beginning of the learning process.
An adversary (potentially collaborating with the learner) can generate the variance dı in each round based historical observations, with the learner receiving each variance at the beginning of the corresponding round. This setting can be further divided into categories based the power of the adversary:
Adaptive Sequence:
Weak Adversary: The adversary must generate the variance d before observing the decision set Dr.-
Strong Adversary: The adversary can generate the variance o after observing the decision set DІ.
Remark 3.1. Unlike the typical adversarial setting focused on maximizing regret for specific algorithm, our work uses the idea of an "adversary" to represent the environment's inherent ability to select the variance sequence. This "adversary" might even strategically choose variance levels (σx) based on the past decision sets Dj observed so far, potentially leading to variance levels that could temporarily improve the learner's performance or make the learning process appear easier. This seeming "cooperation," however, is ultimately aimed exploring the fundamental lower bounds regret that must hold for any learner in any environment. The key is that the variance is chosen without direct knowledge of the true underlying patterns μ. When this "adversary" (our "strong adversary") " can adjust the variance based on the learner's actions (D,), this strategic "cooperation" informed by past observations but blind μ4, becomes more effective in probing the true limits of leamaailiiy and challenging our lower bound results.
4 BELLANCE-DEPENDER LOWER BOUND WITH PREFIXED VARIANCE SEQUENCE
In this section, we consider the setting where the variance sequence Oxk is prefixed and fully revealed to the learner at the beginning of the learning process.
4

---

Published as a conference paper at ICLR 2026
4.1 MAIN RESULTS
We establish the following theorem for the variance-dependent lower bound.
Theorem 4.1. Let d > 1 and consider any prefixed sequence of variances for, σx) satisfying Σ of 2 1 384d2. For any algorithm Alg, there exists hard linear contextual bandit instance such that each action a E Da in round k has variance bounded by ok. For this instance, the expected regret of algorithm Alg over K rounds is lower bounded by:
E EjRegret (K)) 2 2
s(ddy dd E of (l/
Remark 4.2. For a prefixed sequence {o1,..., Theorem 4.1 shows that any algorithm incurs
regret lower bounded of (2(d Σ of.), which matches the upper bound in Zhao et al. (202)) up to logarithmic factors. Compared the lower bound in JJa et al. (2024). Theorem [.1 focuses on the linear contextual bandit setting and achieves v improvement over the standard linear bandit setting. It is also worth noting that the lower bound in Dia et al. (2024) only considers instances with fixed total variance Σ k= of constructed by using constant variance in the early rounds and zero variance in later rounds. In comparison, Theorem applies to any fixed variance sequence and is more flexible.
In Theorem 4.1 require that the total variance is no less than M(d)), which reduces to K 2 ((d)) when all variances 0% = 1. A similar requirement exists in standard linear bandits, since a trivial lower bound of (2) always holds for any algorithm, and the lower bound of (2dyK) can only be achieved when K 2 (2d Furthermore, for general sequences of variances with total variance smaller than (dd)), a large number of rounds K alone is not sufficient to establish the desired lower bound. The presence early rounds with zero variance would increase the total number of rounds without affecting the fundamental complexity of the problem. This observation suggests that requiring total variance no less than (cd2) (or other equivalent conditions) may be necessary for establishing the lower bound.
4.2 PROOF OVERVIEW OF THEOREM 4.1
In this subsection, prove the variance-dependeee lower bound in Theorem We first start with a fixed variance threshold a, and construct a class of hard-to-learn instances where actions are chosen from a hypercube action set AA = {}, and for any action E A. the reward follows (1/33- + (1,, a)). where = 1//96KK' and μ {-A, ad In this setting, the variance for each action is upper bounded by o², and these instances can be represented as linear bandit problem with feature (a, o a) and weight vector μı' (1/3, 14). Based on these hard-to- hard-to-learn instances, we have the following variance-depende
scaled Bernoulli distribution
lower bound for the regret:
Lemma 4.3. For a fixed variance threshold o and any bandit algorithm Alg, if the weight vector μa E (- A 1d is uniformly random selected from {-A, AJd, the variance in each round bounded by 0², and the expected regret over K 2 1.5 rounds is lower bounded by:
Eye (Regret (K)) 2 dv KVKo2/8v4
Remark 4.4. Lemma 4.3 establishes a variance-dependent lower bound for the regret with a fixed variance threshold σ. When all variances are equal (01 = = σк = σ), this bound matches the upper bound in Zhao et al. (2023) up to logarithmic factors. In addition, under this seed-variance setting, this lemma provides a tighter logarithmic dependency on the number of rounds K compared to Theorem 4.1 though it does not extend to dynamic variances.
Now, for any prefixed variance sequence {oI,.... Øx J. we divide the rounds into L = [log, K] + different groups based on the range of their variance as follows:
Ko : 11/K),
K, :k: o / for i I,...,, 1.
For each group K,; with i E [T. 1), we construct bandit instance M, with weight vector p following Lemma 4.3 where:
the variance threshold is set to be (1) 2' I/K:
the number of rounds is K; [Ka];
5

---

Published as a conference paper at ICLR 2026
the dimension is d, = d/L.
For group Kg, we construct different type of instance Mu: d/ L-armed bandit, where one ran- domly chosen arm gives constant reward while all other arms give reward O. Note that this instance in Mi can be equivalently represented as a dg = d/ dimmenssiona linear bandit where actions are one-hot vectors e;-
The basic idea for the lower regret bound to assign different orthogonal sub-instances based on the range of the variance d at the beginning of each round. This method ensures that each orthogonal instance will be learned with comparable variance, which makes it easier to derive a tighter lower regret bound. Finally, since the orthogonal instances cannot provide mutual information, the total regret can decomposed into the summation of the regret accumulated in each sub-instance.
create combined linear bandit instance with dimension do + d1 + + dL-1 = d with weight vector f = (Ho..... (L--): At the beginning of each round k, if round & belongs group K2, then the learner receives the decision set D (Ody 1d. 1. x, .d........ Odz-1)= x A.}. where Od, corresponds to zero vector with di- mension dj and A, is the action set in the bandit instance M₁ Under this construction, for any round k E K, the reward in the combined instance coincides with that of sub-instance M, Specifically, after the learner selects action x, they receive a reward drawn from a scaled Bernoulli distribution
Based these sub-instances,
with variance upper bounded by (1) (2' /K) for + O, and variance 0 for i 0. Note that in all groups. the variance is bounded by o With this construction in hand, we now proceed to prove the lower bound Theorem 4.1
Remark 4.5 (Linear Contextual Bandits vs. Stochastic Linear Bandits). In the proof of The- orem 4.1 we heavily rely on assigning different decision sets to rounds in the contextual bandit environment. This approach, however, does not extend to stochastic linear bandit problems, where all rounds share the same decision set. To see this limitation, consider any prefixed variance se- quence with 01 = _... = aa = 0. In this case, the learner can select canonical basis of the decision set in the first d rounds. Since these rounds have zero variance, the learner learns the exact rewards for all actions in the decision set and incurs no regret in subsequent rounds, regardless of the val- ues of OK. Consequently, it is impossible to establish an variance- lower bound of Mdd ΣK o) for stochastic linear bandits.
Proof of Theorem 4.1 Due to the orthogonal construction of decision sets across different groups KC,, actions in group X, provide no information about the weight vector μ4 for j * i. Consequently, the total regret can be decomposed into the sum of regrets from each sub-instance. For each sub- instance Mi with i 7 0, the regret is lower bounded by:
div Kio
Byp:
Σ keK.
max (pii x) (u,,xx) 2 [K; 1.5d.)
xED
8V6
di / Kio2(i)
di 1.5d; (2)
8V6
8v6
d: ΣMEK, of
(4.1)
16v6
16
where the first inequality follows from Lemma 4.3 the second inequality holds due to 1(x v) 2 Vz- vi. and the last inequality follows from the definition of group KG,
2
Taking a summation of (.1 over all groups, the total regret can be lower bounded as follows:
Ey [Regrot(K))
Σ Eyn.
Σ
max (pi, x) (Jai, XL.)
xED,
1=0
kek.
di EREK, 22
df -(1))
16V6
16
L- d
ΣLEK, of
d2
16
412
i=1

---

Published as a conference paper at ICLR 2026
dv El EKEK, of
d
(4.2)
16v6L
41
where the first inequality follows from 4.1 the second inequality follows from the definition of variance threshold (i) and dimension d; = d/ L, and the last incquality holds due to Ex v 2
E Ti. In addition, for the group No, we have
Σ kEKa
SSS Σ
1/K 1
(4.3)
kEKD
where the first inequality follows from the definition of group Kg and the second inequality follows from (Col S K. Therefore, have
d i== EKEK, of
d
E Regret (K)) []]
2
16V6L
4L2
d Σ kml
o -1
df
16
4L2
d.
K
of -1
32
where the first inequality follows from inequality follows from the fact that Σ
4.2 the second inequality follows from 44. and the last
1 384d2. This completes the proof.
5 VARIANCE- SEQUENCE
LOWER BOUNDS WITH ADAPTIVE VARIANCE
In the previous section, focused the setting where the variance sequence is prefixed and revealed to the learner at the beginning of the learning process. In this section, we extend our analysis to the setting where the variance sequence can be adaptive based historical observations, with the learner receiving the adaptive variance at the beginning of each round.
5.1
MAIN RESULTS
5.1.1 WEAK ADVERSARY
We first describe the learning process and the mechanism of variance adaptation. detail, adaptive variance process proceeds as follows:
1.
At the beginning of each round k. (weak) adversary selects the variance level a based on the historical observations, including actions {aı,..., 4x-1) }. rewards {ri,..., -T--1 }. and decision sets {D1, D2, ... D The adversary has access to all historical information but not to the underlying reward model parameters;
2. Given the selected variance level di, we construct and assign decision set Dj. to the learner, where the variance of the reward for each action a E Di: is bounded by of:
3. The learner observes the decision set Dx and variance level σыe then determines an action ag from D3 based its historical observations and current information. After selecting the action, the learner receives a reward Fi with variance bounded by oî.
Remark 5.1. It is worth noting that our concept of adversary differs from the weak/strong adversary in Jia al. (2024). Specifically, Jia al. (2024) considers adversary that attempts hinder the learner's is learning by allocating fixed total variance budget Σ of S across rounds max- imize regret. In contrast, our work considers an adversary that attempts to break the lower bounds themselves by collaborating with the learner. To prevent such exploitation, we must restrict the ad- versary from knowing the weight vector of the underlying reward model. Without this restriction, adversary could encode each entry μ4; of the weight vector μ through the corresponding variance a; μi allowing the learner to learn the weight vector after d rounds.
Under this setting, we establish the following theorem for the variance-dependent lower bound.

---

Published as a conference paper at ICLR 2026
Theorem 5.2 (Weak Adversary). For any dimension d 1, any adaptive sequence of variances (oi...., ok} and any algorithm Alg, there exists a hard instance such that each action a E Di in round & has variance bounded by o². For this instance, if Ek= of 2 (2(d),, then with probability least 1 1/K, K the regret of Alg over K rounds lower bounded by:
Regret (K) 2 sddd E of/ log (dd))))((K))
Remark 5.3. Theorem 5.2 provides a high-probability lower bound of ((dy Ex= oi), which matches the upper bound In Zhao et al. (2023) to logarithmic factors, albeit with looser logarith- mic dependencies than Theorem 4.1 due to the adaptive nature of the variance sequence. Unlike the expected lower bound in Theorem 4.1 for adaptive variance sequences, the cumulative variance
Ek= of depends the random process and observations. This dependence makes it challenging to establish an expected variance-dependent regret bound a fundamental difficulty that does not arise for standard dv K -type lower bounds in linear contextual bandits (Dani et al. 2008 Chu et al,, 2011 Lattimore & Szepesvári, 2018). To the best of our knowledge, our result provides the first high-probabbiltty lower bound for linear contextual bandits. In addition, our technique of converting an expected lower bound to high-probabiln one of independent interest and can potentially be used to derive high-probar potbhbbrbbbbttyy lower bounds for wider class of problems.
5.1.2 STRONG ADVERSARY
we require that for each round k E [K]. all actions x E Dr. share the same adaptive variance ok- This more restrictive than the setting in /Zhao et al. (2023), where the variance can differ across actions Da. However, extending is fundamentally incompatible with our adaptive instance construction. The key difficulty is that, in our lower-bound construction, the decision set D2 is generated before the adversary chooses the variance kk, which prevents assigning specific variances to individual actions x E DD-- Moreover, now consider strong adversary that can choose an after observing the decision set Da. The interaction between the learner and this strong adversary proceeds as follows:
In Theorem 5.2
lower bound to action-dependent variances
1. At the beginning of each round k we construct and assign a decision set D₂ based on historical observations, including actions {ui,.... Ax-1) } and rewards (kk-).
2. Given the decision set Dr in round k; the strong adversary selects the variance level 0 for round k. The adversary has access to all historical information but not to the underlying reward model parameters;
3. The learner observes the decision set D& and variance level Øj, then determines an action ag from Dj based on its historical observations and current information. After selecting the action, the learner receives a reward ra with variance bounded by o..
The following theorem shows that under this setting, the adversary could cooperate with the learner to break the lower bound.
Theorem 5.4 (Strong Adversary). For any linear contextual bandit problem and number of rounds K > 2d, if we first provide the decision set Dj and then allow an adversary to choose the variance o% based on the decision set DR. there exists one such type of adversary such that, there exists an algorithm whose regret in the first K rounds is upper bounded by Regret(K) < d, where the total variance Σk= of K/2.
Remark 5.5. Theorem highhlitss why Theorem 5.2 requires a weak adversary that set the vari- sequence before seeing the learner's choices. If the adversary could the decision first, it could potentially choose variances that would invalidate our lower bound. This finding underscores that our construction is precise and pinpoints the exact condition under which the derived lower bound holds.
Remark 5.6. worth noting that Jia et al. (2024) also considered the case where the adver- sary assigns variances to actions after observing the decision set and action choice, and provided a variance-dependent lower bound. However, their analysis focuses on an adversary that allocates variance across rounds to maximize the regret. In contrast, our work considers adversary that attempts to break these bounds, making it more challenging to establish lower bounds for general variance sequences. It is also worth noting that if the adversary's 's goal is to increase regret, choosing a prefixed sequence is a viable strategy. This case is already covered by our Theorem for prefixed sequences, which provides tighter lower bound than Theorem 5.2
8

---

Published as a conference paper at ICLR 2026
Theorem 5.4 suggests that it is impossible to derive variance-dependent lower bound if the ad- versary can determine the variance σj after observing the decision set Dj. which further precludes establishing lower bound when the adversary has the ability to assign action-dependent variances for each action x E Di after observing the decision set D2.- This result naturally extends to stochas- tic linear bandit problems, where the decision set 'D remains fixed across all rounds. In this case, since the adversary knows the decision set D = D in advance, Theorem directly implies:
Corollary 5.7. For any stochastic linear bandit problem with fixed decision set 'D and number of rounds K 2 2d, there exists a prefixed sequence (01, (01,...,0K' such that there exists algorithm whose regret in the first K rounds is upper bounded by: Regret A (K) S d, where the total variance
Σ of 2 K/2.
5.2 PROOF SKETCH OF THEOREM 5.2
Overall, the proof follows a similar structure as Theorem 4.1] where we divide the rounds into several groups based on their variance magnitude and create hard instances for each group. The key idea is to calculate individual regret bounds for each group and combine them for the final lower bound. However, there exist several challenges when dealing with adaptive variance sequences that require careful handling.
In this section, we provide the proof sketch of Theorem 5.2
Varying Size of Groups K. As discussed in Section 4.2 for each group K2, we create individ- ual instance M, with fixed variance threshold (i) = 2 2'1/K and establish a lower bound of ( on the expected regret. However, the construction of such instances relies on prior knowledge of the number of rounds [Ke], which can be calculated the beginning for pre- fixed variance sequence {oi..... ox] J. In contrast, for general adaptive variance sequences, the number of rounds [Ka] is not known a priori and can even be a random variable, which creates a barrier in constructing these instances.
To address the unknown number of rounds [KG]], instead of constructing a single instance M, for each group, we create L instances Mij. where L [log2 K + Each instance Mi,, is designed for specific range of round numbers, specifically Ma, for 2 < K, 2
For each round k in group Kg, the learner receives a decision set Dj from one of the instances in I... M,,L) in a eyclic manner. Through this sequential assignment, the number of visits to each instance Mi.j is /K,// L. Consequently, we expect that the instance Mij corresponding to the
true range 2/-1 [KG]] <
2 provides lower bound of ((d./o2()))
(dd.o22(). 25),
which leads to the final lower bound of (ddy Ex= o.).
Converting Expected Lower Bound to ProbaPrrbyyility Lower Bound. Another challenge is establishing the lower bound for the triggered instance Mi, corresponding the true range 2 <
|K,] 2). Traditional analysis of lower bounds in linear contextual bandits has focused on the expected regret. However, when dealing with adaptive variance sequences, this approach becomes insufficient as the adversary can dynamically adjust the variance sequence to break these bounds.
For instance, an adversary might continuously set 0 = until the lower bound of Ū(d I of) is violated at some round k, then switch to = 0 for all future rounds, causing the total variance sum Σk_ of to remain unchanged. In our construction, this means all rounds could fall into group Kz. allowing the adversary to adaptively change the number of rounds between different intervals 20-1 < [Kz] < 2/. Since the failure of the lower bound in any single instance ML,, leads to failure of the whole construction, an expected lower bound on regret cannot guarantee robust performance against adaptive sequences. This necessitates stronger high-probability lower bound that holds uniformly for all instances.
Unfortunately, expectation of Q(d, / (i())))) in instance Mi,j only implies a low-probability regret (Regret 2 ((())i))))) 2 d. 112 since the cumulative regret in KG; can be up to o (i)- [K,] in our instance. To solve this problem, we introduce an auxiliary algorithm that automatically detects the cumulative regret and switches to the standard OFUL algorithm (Abbasi- Yadkon et al.) 2011 if the cumulative regret is larger than 2(de 2 (1)2i) [ For this auxiliary algorithm, we can
In general settings, detecting cumulative regret is impossible as the learner lacks prior knowledge of the optimal reward and variance. However, in our lower bound construction, all instances are randomly selected from instance classes sharing the same optimal reward and variance, which are known to the leamner This knowledge enables the construction of the auxiliary algorithm.

---

Published as a conference paper at ICLR 2026
guarantee that the upper bound is at most (dd (i)2) while maintaining the same probability of high regret as the original algorithm. Therefore, an expectation of (2(d. (i)2) in instance Ma, implies constant-probabie
regret P(Regret 2 Q(d:y ( (I()).
After constructing an instance with constant-probabiliyy lower bound, we boost this probability by creating O log"(d)) (dK)) independent instances. When the learner encounters instance Ma.j. it is assigned one of these instances in cyclic manner. Through this construction, with probability at least 1 1/poly(K) the final regret is lower bounded by Regret 2 ((d
Remark 5.8. Unlike previous lower bounds for linear bandit, problems which focus expected regret, to the best of our knowledge, our result provides the first high-probability lower bound for linear contextual bandits. across different rounds in the random assignment process. For stochastic linear bandits with fixed decision set, we can only derive a constant- constant-probabiae probability lower bound. Moreover, for a fixed decision set stochastic linear bandit problem with covering number N S ((d), an algorithm can randomly select one action from the covering set and perform this action in all rounds. In this case, there exists a probability of 1/N = 1/ (x) to achieve zero regret, which precludes the possibility of establishing high-robbbbility lower bounds for large round numbers K. More details about the high- ceab--robbbilityy lower bound can be found in Section 5.2
is worth noting that our construction requires separate decision sets
CONCLUSION AND FUTURE WORK
In this paper, we study variance-dependent lower bounds for linear contextual bandits in different settings. For both prefixed and adaptive variance sequences with weak adversary, we establish tight lower bounds matching the upper bounds in Zhao et al. (2023) up logarithmic factors. We further demonstrate a fundamental limitation: when strong adversary can select variances after observ- ing decision sets, becomes impossible to establish meaningful variance-dependent lower bounds. However, our work has focused exclusively on linear bandit settings, while Jia et al. (2024) has established variance-dependent lower bounds for general function approximation with a fixed total variance budget A. Therefore, we leave for future work the generalization of our analysis of general variance sequence to contextual bandits with general function approximation.
ACKNOWLEDGMENT
We thank the anonymous reviewers and chair for their helpful comments. JH and QG supported in part by the National Science Foundation DMS-2323113 and IIS-2403400. JH is also supported by UCLA dissertation year fellowship. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
REFERENCES
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pp. 2312-2320, 2011.
Lean-Yves Audibert and Sébastien Bubeck. Best arm identification in multi-armed bandits. In COLT-23th Conference on learning theory-2010, pp. 13-p, 2010.
Jean-Yves Audibert, Rémi Munos, and Csaba Szepesvári. Exploration-exploiaatio tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 117619):1876-1992, 2009.
Peter Auer. Using confidence bounds for exploitation-exxllrraion trade-offs. Journal of Machine Learning Research, 3(Nov):397-422 2002.
Peter Auer, Nicolo Cesa-Biancha and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-22 256, 2002.
Nicolo press, 2006.
and Gábor Lugosi. Prediction, learning. and games. Cambridge university
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff func- tions. In Proceedings of the Fourteenth International Conference on Artificial Intelligecce and Statisties, pp. 208 214. JMLR Workshop and Conference Proceedings, 2011.
10

---

Published as a conference paper at ICLR 2026
Yan Dai, Ruosong Wang, and Simon Shaolei Du. Variance-awart sparse linear bandits. In The Eleventh International Conference on Learning Representations.
Varsha Dani, Thomas Hayes, and Sham M Kakade. Stochastic linear optimization under bandit
feedback. In 21 Annual Conference on Learning Theory, number 101, pp. 355-366, 2008.
Zeyu Jia, Jian Qian, Alexander Rakhlin, and Chen-Y Yu Wei. How does variance shape the regret in contextual bandits? Advances in Neural Information Processing Systems, 37:83730-83785, 2024.
Yconeung Kim, Insoon Yang, and Kwang-Sut Sung Jun. Improved regret analysis for variance-adaptive linear bandits and horizon-free linear mixture mdps. Advances in Neural Information Processing Systems, 35:1060-1072 2022.
Johannes Kirschner and Andreas Krause. Information directed sampling and bandits with het- croscedastic noise. In Conference On Learning Theory, pp. 358-884. PMLR, 2018.
Anusha Lalitha Lalitha, Kousha Kalantari, Yifei Ma, Anoop Deoras, and Branislav Kveton. Fixed- budget best-arm identification with heterogeneous reward variances. In Uncertainty in Artificial Intelligence, pp. 1164-1173 PMLR, 2023.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. preprint, pp. 28, 2018.
Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A canexttualbbnditt approach to personalized news article recommendation. Proceedings of the 19th international conference on World wide web, pp. 661-670, 2010.
Yingkai Li, Yining Wang, and Yuan Zhou. Nearly minimax-optimal regret for linearly parameterized bandits. In Conference on Learning Theory, pp. 2173-2174. PMLR, 2019.
Pinyan Lu, Chao Tao, and Xiaojin Zhang. Variance-dependent best arm identification. In Uncer- tainty in Artificial Intelligence, pp. 1120-1129. PMLR, 2021.
Zihan Zhang, Jiaqi Yang, Xiangyang Ji, and Simon S Du. Improved variance-aware confidence sets for linear bandits and linear mixture mdp. Advances in Neural Information Processing Systems, 34:4342-4335, 2021.
Heyang Zhao, Dongruo Zhou, Jiafan He, and Quanquan Gu. Bandit learning with general function classes: Heteroscedastic noise and variance-dependent regret bounds. CoRR, 2022.
Heyang Zhao, Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. fariance-dependee regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency. In The Thirty Sixth Annual Conference Learning Theory, pp. 4977-5020. PMLR, 2023.
Dongruo Zhou and Quanquan Gu. Computationally efficient horizon-free reinforcement learning for linear mixture mdps. Advances in neural information processing systems, 35:36337-36349, 2022.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learn- ing for linear mixture markov decision processes. In Conference Learning Theory, pp. 4532- 4576. PMLR, 2021.

---

Published as a conference paper at ICLR 2026
LLM USAGE
We used an LLM solely for grammatical and stylistic polishing of the manuscript. No research ideas or results were generated by the LLM. All technical content written and verified by the authors.
A EXPERIMENTS
In this section, we conduct experiments to show the difficulty of our construction of hard-to-learn instances.
A.1 EXPERIMENTAL SETUP
In this experiment, we follow the construction of hard-to-learn instances presented in the proof of Theorem 4.1 which breaks down the problem into several sub-instances.
Model Parameters. We consider contextual linear bandit with total dimension D 10, which we break down into two orthogonal sub-instances, M₁ and M2, each with dimension dj d2 = 5. The environment is defined by the set of true parameter vectors μ -141;42), where fixed vectors, br and μ22, each have non-zero entries drawn i.i.d. from L/(0, 1) in only 5 dimensions.
Variance Sequence We consider a prefixed variance sequence over 4000 rounds. The variance sequence is piecewise, defined by an abrupt shift at KSWITCH 2000:
Low Variance (01 0.1): Used in the first 2000 rounds (k s 2000).
High Variance (02 1.0): Used in the subsequent 2000 rounds (2000- k < 4000).
Scenario Assignment To illustrate the necessity of adaptively allocating different instances to the learner based on the variance level, we consider two scenarios for assigning the sub-instances (M1 or M2) to the learner:
1. Piecewise Assignment (Hard-to-Learn): The first 2000 rounds assigned the in- stance M1, and the second 2000 rounds are assigned the instance M2. (Switch occurs at TswIrch).
2. Alternating Assignment (Rapidly Switching): The odd rounds are assigned the instance M1, and the even rounds are assigned the instance M2. (Switch occurs at each round).
Decision Set each round A; the decision set Dp contains Namus 32 contexts. The base context entries are drawn i.i.d. from (1(0, 1). This context set is masked such that contexts interact only with li when Mi is assigned, and only with μ22 when M2 is assigned. Crucially, this orthogonal masking ensures that information gathered from one sub-instance cannot be transferred or used to estimate the parameter vector of the other sub-instance.
Noise and Reward For each round k, after the learner chooses an action E DR, receives reward (a) = a μ² + ck, where the noise eg is drawn from the Gaussian distribution W/ af with a, determined by the prefixed variance sequence (i.e., d; 0.1 for 2000 and o; 1.0 for k > 2000).
A.2 RESULTS AND DISCUSSION
In the experiment, we evaluate the performance of two key algorithms:
Abbasi- Yadkori et al. (201I):
: This provides a near-optimal variance-indeepedent
regret guarantee for the standard linear contextual bandit problem.
Weighted OFUL Zhou et al. (202T): This provides a near-optimal variance-dependent
regret guarantee for the linear contextual bandit problem, assuming the variance for each round known to the learner.
We repeat each baseline algorithm for 100 times and plot their cumulative regrets with respect the number of rounds in Figures [
[o
A.2.1 ANALYSIS OFUL
As shown in Figure and 2 (standard OFUL), the algorithm does not utilize the information re- garding the variance level and constructs similar confidence set size for the low-variance period and the later high-variance period, which leads to comparable regret in both periods. Also, for the altermating assignment (Figure B). even though each sub-instance M, alternates between low and high variance, OFUL fails to gain an advantage from the low-variance rounds and has a comparable total regret across all 4000 rounds.
12

---

Published as a conference paper at ICLR 2026
A.2.2 ANALYSIS OF WEIGHTED OFUL
The results for the Weighted OFUL algorithm (Figures 3 and J. which utilizes variance- based mechanism, show a totally different observation. For the Piecewise Assignment (Figure 3 Weighted OFUL utilizes the low variance in the first 2000 rounds and achieves much lower regret in that initial period. However, since the information gathered is only for instance M1 and cannot transfer the orthogonal instance M2, Weighted OFUL achieves much higher regret in the last 2000 rounds due to the high variance.
In comparison, for the Alternating Assignment (Figure 4), each instance (M1 and M2) effectively goes through 1000 rounds with low variance and then I000 rounds with high variance. Under this situation, Weighted OFUL can construct a tighter confidence set for both instances in the first 2000 rounds, which leads much smaller total regret over 4000 rounds. This result illustrates that the early stage with low variance can significantly speed up the learning process in the exploration stage and lead a low total regret. The ability to adaptively assign the decision set based on the variance level (as we used in constructing the lower bound) can avoid the early exploration stage having much smaller variance than the later exploitation stage, thus successfully circumventing the limitation.
Heggh and Df Neccre Sutbear Lirou fardt
DEC Nestebo Barlwayy Lireet OChang
1000
Figure 2: Weighted OFUL with Piccewise As- signment
Figure 1: OFUL with Piecewise Assignment
DPJ Nereeto Bebnnyy Band: (Chang
200
Figure 4: Weighted OFUL with Alternating As- signment
Figure 3: OFUL with Alternating Assignment
B PROOF OF THEOREM 5.2
In this section, prove the variance-dependens lower bound for adaptive variance sequences tablished in Theorem 5.2 We begin with the instance construction from Lemma 4.3 and establish the following prosaiit-ro lower bound for the regret:
Lemma B.I. For fixed variance threshold a, number of rounds K 2 1.5d2, and any bandit algorithm Alg. for the instance constructed in Lemma 4.3 with probability at least 221 (1//oo((dK)) the regret lower bounded by
Ko
Regret ()
16V6
Based the prostant--robabiiliyy lower bound, boost this probability by creating L Ω log" independent instances with dimension d' d/L and number of rounds K' = K/L, where each instance follows the structure in Lemma 4.3 with i..d. sampled weight vectors. Un- der this construction, the total dimension of all instances is d, which can be represented d-
13

---

Published as a conference paper at ICLR 2026
dimensional linear contextual bandit through orthogonal embedding, similar to previous struction: for instance i, we augment its actions by padding zeros in dimensions reserved for other instances, ensuring actions from different instances only interact with their corresponding param- eters. Here, we consider the case where the learner visits the instances in a cyclic manner and establish the following high-probabilityy regret lower bound for the constructed instance:
Lemma B.2. For fixed variance threshold a, number of rounds K 2 1.5d and any bandit algorithm Alg, with probability at least (1))) the regret lower bounded by
Regret(K)) 2 L(dv Ko² (dK)(
With the help of this high-probability lower regret bound from Lemma B.2 we begin the proof of Theorem 5.2 Following a similar framework the fixed-variance case, we first divide the rounds into groups based on their variance magnitude. Specifically, for any variance sequence [ol....,ok]] J. we partition the rounds into [log2 K] + 1 groups as follows:
Ko = [k: 1/
K; = -k: < ok / for i = 1,...,I--11 1-1.
To address the unknown number of rounds K; = [Kgl. instead of constructing a single instance
M; for each group, we create L instances Mij. where L [log, K + 1. Each instance Mi, is constructed according to Lemma B.2 with dimension d' = L2,, variance o(i) = 2''1'21/pp
1 K and number of rounds K' 2--1_ For each round &o in group K,, the learner receives decision set D, from one of the instances in (M......... Mi,.} in a cyclic manner.
Proof of Theorem 5.2 According to Lemma B.2 for each instance Maj, with probability at least 1 1/K3, the regret in the first 2 visits is lower bounded by
Regret(2i Ma,)) > I[(2-1 1.5d²) 2(d' / 22201 log log (d'K)),
(B.1)
where the indicator reflects the requirement that K' = 2/-1 > 1.5d For simplicity, we define & as the event that (B.I) holds for all instances Ma. By union bound, we have PP()) 2 21-10 1/K. Conditioned on event &, for adaptive sequence and each corresponding group K,, due to the cyclic visiting pattern, each instance Mi, is visited [Ka//L L times. There exists an instance Mij
with matching interval for the round number, i.e., 2/ S KGILT. S 2'. Therefore, we have
Σ max (1,,, x) (p),
xED, kEK;
2 Regret (2) (2)) (MMss)
2 1(2)-1 2 1.5d(²) ((d log (d''k)))))
2 I(K, 2 3d L) Q(d (1) (o)/ (dK)) (d)))
2 00 d'' (K,02 (1) log (dK) d' 3d 2 Lo (i) log (dk)
20( d
Σ kEK.
log (dK) 33d2 o /i)/ log' (dk)
(B.2)
where the first inequality follows from 2 < |KL/L < 2), the second inequality holds by the definition of event E, the third inequality follows from 2 |K < 2 the fourth inequality holds due to 1(x > y) V Vi /V. and the last inequality follows from the definition of group K,,
Taking a summation of B.2 over all groups, the total regret can be lower bounded as follows:
Regret (K)
max (1,,, x) - (p4,, Xx) xEDr
1=0 REK;
L-1
Σ Ω d'
Σ
o2/ (dK) V3Ld² o(1)/ log (dk)
1=1
kEK.
14

---

Published as a conference paper at ICLR 2026
1-1
2 Ω
Σ d/t..
Σ kE
o (dK) 2v3Td2 / /I. log (dK))
1=1
2 20 20(d/L3
d/L2
Σ o log (dK) - 2// / /L' log((d))))
(B.3)
1=1 kEK.
where the first inequality follows from (3.2). the second inequality follows from the definition of variance threshold (i) and dimension d' d/L?, and the last inequality holds due to Σ; 04 2
Zz. In addition, for the group Kn we have
ES Σ 1/K 1
(B.4)
kENo
kEKo
where the first inequality follows from the definition of group Ko and the second inequality follows from |Kol & K. Therefore, have
Regret(K)
Ω d/1.2.
/o/log" logg)))) 2/3TT2 log(()))
REK,
Ω d/1.2. 1
o - - 2v (o.
kEK,
2 20 20( d.
Σ
/ log logo(d (dk)
kEK,
where the first inequality follows from B.3 the second inequality follows from B.4). and the last inequality follows from the fact that Σ 2 2(d)). Thus, we complete the proof of Theorem
5.2
C PROOF OF THEOREM 5.4
In this subsection, we provide the proof of Theorem 5.4 We begin by describing a simple algorithm:
1. The learner maintains an explored action set A, which is initialized empty.
2. For each decision set DD in round k if there exists an action X₃ not in the spanning space of the explored action set A, the learner:
Selects an action X and receives reward TR:
Updates the explored set: A = AU Tx)),
3. Otherwise, when all actions lie in the spanning space of A, the learner:
Estimates the reward for each action through linear combinations of (x, r) E A:
Selects the action with maximum estimated reward.
It is worth noting that this algorithm assumes the received rewards have no noise to provide accurate estimates in step 3. While this assumption does hold in general, when an adversary can choose the variance d based the decision set Dr, they can cooperate with the learner by setting:
.7 when step triggered (exploration):
dz when step 3 is triggered (exploitation).
For dddimensional linear bandit problem, the explored action set satisfies |A| < This implies the learner performs at most d exploration steps with zero variance, while all remaining steps have variance one. Under this construction, the regret in the first K rounds is upper bounded by:
RegretAis
(K) S d,
where the total variance Σ of = K K/2 (since K 2 2d). Thus, through this cooperation 2)) lower bound is broken, completing the
between the adversary and learner, the π(dy ΣK proof of Theorem 5.4
15

---

Published as a conference paper at ICLR 2026
D PROOF OF KEY LEMMAS
D.1 PROOF OF LEMMA 4.3
When the variance threshold = 1, our construction reduces to the standard lower bound instances for linear contextual bandits (Zhou al. 2021 Specifically, when the number of rounds K' satisfying K 2 1.5 dZ, /Zhou et al. (2021)
In this subsection, we provide the proof of Lemma 4.3
provided the following variance-independent lower bound for these hard instances:
Lemma D.1 (Lemma C.8, Zhou et al. 202T). For any bandit algorithm Alg, the weight vector E {-A, A}" is drawn uniformly at random from f-A, A}", then the expected regret over K
rounds is lower bounded by:
dvK
E (R))
8v6
With the help of Lemma D.1 we start the proof of Lemma
4.3
Proof of Lemuna 4.3 For any algorithm Alg for linear contextual bandit with fixed variance thresh- old a, we construct an auxiliary algorithm Alg1 to solve the standard linear contextual bandit prob- lem:
At the beginning of each round l E K, Algl observes the decision set Dj: and sends it to Alg;
Alg selects action E D2 based on the historical observations and delivers it to AlgI;
Algl performs the action 0g, receives the reward тj and sends the normalized reward or Fk to Alg.
Now, we consider the performance of auxiliary algorithm Alg1 for the standard linear contextual bandit problem. It is worth noticing that the reward/noise in bandit instances for algorithm Alg and algorithm Alg only differ by a scalar factor a, therefore for each instance, we have
E [eegret Aig (K) = a EE[Regret Aig1 (K)].
(D.1)
If randomly select weight parameter vector μ E ( A d then according Lemma D.I the regret for Alg is lower bounded by
dvK dVKo²
Ey [Regret Aig (K) E, [Regret (K))
8/6
8V6
where the equation holds due D.I and the inequality holds due Lemma D.I Thus, we com-
plete the proof of Lemma 4.3
D.2 PROOF OF LEMMA
B.1
In this subsection, provide the proof of Lemma B.1
We begin by recalling the OFUL algorithm in Abbasi- Yadkori et al. (21TT) and its corresponding upper bound for the regret:
Abbbaii-adkook et al. 201T). For any linear contextual bandit problem, with probability at least 1 d, the regret for OFUL algorithm in the first K rounds is upper bounded by Regret(K) (d K log(dK/6))
Lemma D.2 (Theorem
It is worth noting that the reward/noise in the instance construction from Lemma 4.3 only differs by a scalar factor a from the standard bandit. Therefore, as discussed in Section D.I the regret in these two cases also only differs by scalar factor This leads to the following corollary:
Corollary D.3. For the instance construction from Lemma 4.3, there exists constant C' such that with probability at least 1 8, the regret for OFUL algorithm the first K rounds is upper bounded by Regret K) < Cd./Ko² log (og(dK/))
With the help of Corollary D.3 we can begin the proof of Lemma B.I
Proof of Lemma
B.
For any algorithm Alg, we construct an auxiliary algorithm Algl as follows:
At the beginning of each round l E [K], Algl observes the decision set D3 and sends it to
Alg:
16

---

Published as a conference paper at ICLR 2026
Alg selects action dk E Dj based on the historical observations and delivers it to AlgI;
Algl performs the action Og and receives the reward ris
Algl calculates the pseudo regret as:
Regret' (k)
ΣΣ 1=1
1
Tk-
V v96K
If the pseudo regret is larger than dv Ko² (8 + a v 2K (2g(28/8), Alg1 removes all previous information and performs the OFUL algorithm in all future rounds.
Based on the construction of the instances, whatever the weight vector μ is, the optimal action is to select an action in the same direction as the weight vector, obtaining an expected reward of 1/3 d/ /9K.. Under this scenario, with probability at least 1 - 8, for any round k [K], the difference between pseudo regret Regret' (I)) and true regret Regret(k) can be upper bounded by
(eggre(Ak) Regret' (k))
Ea
S oov Sov2ks 2K (2K(2)/)),
(D.2)
with the fact that the noise satisfies and |ex| S a. Thus, according to the criterion of auxiliary algorithm AlgI, with probability at least 1- 6, the regret of Algl before transitioning to OFUL is up to dv (8v/)) + 20 /2K log(2K/6). On the other hand, for the stage after transitioning to OFUL, Corollary D.3 suggests that with probability at least 8, the regret is no more than Therefore, with selection of 1/K, we have
where the inequality holds due to Lemma EleR [1:kk -1:k-1]
Cdyy Ko²
P Regret Alg, (K) 2 CdVKo2 Ko² +
2K log (2K3)
S 2//K.
(D.3)
For simplicity, let - -Cdd- Ko² log(dk2) dv +VV 20 2K log (2K2) and we have
E, [Regret Alg, (K)]
$ P Regret Alg, (K) 2 R] Ko + Regret Algi (K) 2 dv dVKo2/(6vV))) R
+ ARegret (K) 2 0] dd (16V6)
< 20 + F [Regret (K) 2 dvKo² /16v Ö(dv Ko² log(dK)) + dV (
(16v6).
where the first inequality holds due to E < P(X 2 21) R+ 2 22) + 2 0) 22
for 0 < X < R and æ1 > 22 > 0, and the second inequality holds due to D.3 Combining this result with the lower bound of expected regret in Lemma 4.1 we have
dv dVKo2/(SVB) Z 20 P [Regret Alg, (K) Z dv Ko² (K62/(1666] old Ko² log(dK))
dVKKo
which implies that
P Regret Alg, (K) 2 Ko² (16v6) 2 2(1 (l1/)og(dK)).
(D.4)
In addition, according to the criterion of auxiliary algorithm Algl with D.2). with probability at least 1 8 1 1/K, Algl will not switch the OFUL algorithm until the cumulative regret is which implies that
larger than d' (/oK///8V0/
PP RRegeet Alg (K) 2 dv KVKo2/(16V0)) 2 P [Regret AlRi (K) 2 TKoo (Ko2/(1600] 1/K
(2(1 log(dK)).
Thus, complete the proof of Lemma B.1
17

---

Published as a conference paper at ICLR 2026
D.3 PROOF OF LEMMA B.2
In this subsection, provide the proof of Lemma B.2
Proof of Lemma B.2 Since the learner visits the instances in cyclic manner, all K rounds, each instance M, ( = 1, 1.2,..., L) is visited K' = K times. As actions from different instances only interact with their corresponding parameters, according to Lemma [.1 for each instance Mi, with probability at least 211 (ol/lo((KK). the regret is lower bounded by
d'VK'o2 dVKo²
Regret K" ,M.) 16v6
16v6- L1.5"
Note that the weight vectors for each instance are independently sampled, hence the probability that at least one instance has regret no less than dvKo² dVKo2/16V6 L is at least
(1 - (11/logg(dK)) 2 11-1/A6 1/K3.
Under this condition, the total regret be lower bounded as:
Ko² Σ (K', 16 I
Regret (K)
(D.5)
Thus, obtain high-probability lower bound and complete the proof of Lemma B.2
E AUXILIARY LEMMAS
Lemma E.1 (Azuma Hoeffding inequality, Cesa-Bianchi & Lugosi 2006 Let {nk be mar-
tingale difference sequence with respect to filtration {9&} satistying 77) I R for some constant
R, т7 is Gk+1 meeasurable, [m = Then for any < 8 < 1, with high probability least
1 - 6, we have
K
mh - RV 2K log(1/8).
18


Reviews:
[{"review_id": "C4DGJ3kuQ3", "reviewer": "Reviewer_vE2i", "summary": "This work studies linear contextual bandits with changing decision sets and aims to characterize optimal variance-based regret rates, depending on the sequence of reward variances. Previous lower bounds were shown in terms of a fixed total variance budget, and had a mismatch in the dimension dependence. This paper strengthens the lower bound in these regards for various modeling assumptions on the adversary.", "questions": "Please see weaknesses above.", "limitations": "", "rating": 2, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* The paper refines known lower bounds in linear contextual bandits in terms of dimension dependence and generalized variance sequences, which requires novelties in the analysis such as a refined peelilng technique and separate analyses of different variance values.", "weaknesses": "* The presentation seems lacking in motivation. am not sure what the real world applicability of the various adversary (prefixed vs. weak vs. strong) scenarios are and there could also be more discussion of whether such refined variance-sequence based lower or upper regret bounds are known for the simpler finite-armed bandit case.\n* There are also no experiments empirically demonstrating the regret bounds exhibit such tight dependences.\n* I also find the presentation a bit confusing or lacking rigor in that, at times, especially Theorem 5.4. The writing at times (e.g., Remark 3.1) suggests the adversary may cooperate with the learner, but I'm not sure how to interpret this as \"adversary\" in bandits typically represents a worst-case environment or environment-generating process. I think this may be due to lack of clarity on the order of quantifiers in theorem statements. Perhaps a diagram or table would make it easier to understand. The utility of Theorem 5.4 is unclear as statements of the kind \"there exists an adversary\" implies such that there is an algorithm that can get small regret seem unsurprising. It is more useful to understand what is the worst-case behavior here, or is the strong adversary somehow weaker than the prefixed one? \n* Because of the wording of Theorem 5.4, it's unclear whether the statement \"it's impossible to derive a variance-dependent lower bound if the adversary can determine the variance after observing the decision set\" really follows as Theorem 5.4 concerns a _specific_ adversary and not the worst-case one.\n* Furthermore, the problem is quite complex as the decision sets are also being generated adversarailly (as it adaptive or oblivious?) and the adversary may decide the variance before or after the decision set which seems to affect the bounds. In particular, some intuition on why the weak and strong adversary leads to different rates would be helpful.\n* The scope of technical novelties of this work also seem limited, and it's a bit unsurprising that general variance sequence-based bounds can be derived using a grouping/peeling argment. Can the authors elaborate on difficulties of the general function approximation setting or discuss wider applicability of techniques introduced here?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qglX9KMmZi", "reviewer": "Reviewer_uLK1", "summary": "The paper studies linear contextual bandits with round-varying noise and asks whether the variance-aware upper bounds $\\tilde{O}(d\\sqrt{\\sum_t \\sigma_t^2})$ are actually tight. It shows that when the whole variance sequence is fixed in advance, for any sequence one can build a contextual instance on which every algorithm incurs $\\tilde{\\Omega}(d\\sqrt{\\sum_t \\sigma_t^2})$ regret matching known upper bounds. For an adaptive but weak adversary it further gets a high-probability lower bound with more high-order polylog factors. Finally, it shows that for a strong adaptive adversary, such variance-dependent lower bounds are impossible, giving a comprehensive understanding of second-order bound for linear contextual bandit.", "questions": "See weakness.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper closes a theoretical gap by deriving a new variance-dependent lower bound that matches previous upper bounds. This improves previous lower bound that depends on total-variance budget and suboptimal $d$ factor for linear contextual bandit.\n\n2. This paper is technically neat, the “variance-level peeling + orthogonal subproblems” construction is clean and reusable; the high-probability version for adaptive variance is nontrivial.\n\n3. The paper gives a comprehensive discussion for the separation of weak vs. strong adaptive adversaries and shows why the strong adversary cannot admit such lower bounds.", "weaknesses": "I did not see major weakness. The current lower bound relies on being able to assign (almost) orthogonal decision sets to different variance groups. That’s fine for an information-theoretic contextual lower bound with adversarially chosen context, but less reflective of i.i.d. contexts. Is it possible to improve the lower bound for linear contextual bandit with stochastic context?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lJgJcKmFmr", "reviewer": "Reviewer_9a2R", "summary": "The paper provides the first high probability lower bounds on variance dependent regret for linear contextual bandits. These bounds match the known upper bounds up to logarithmic factors under varied assumptions on the adversarial strength in deciding and revealing variance sequences. In proving these novel results, the authors devise a \"peeling\" proof machinery which has broader implications beyond the studied problem instance.", "questions": "Proof Rigor (Lemma A.2): Prior to Lemma A.2, the argument mentions considering a specific cyclic instance where the learner visits instances in a cyclic manner. However, the resulting lower bound is claimed to hold for any bandit algorithm. Please explicitly include or reference the standard information-theoretic reduction that proves the bound derived from this specific instance generalizes to all valid bandit algorithms?\n\nHeteroscedastic Variance Utility: Can you provide an expanded explanation of the utility of leveraging \"heteroscedastic variance information\". Furthermore, what key technical obstacles generally prevent obtaining variance-dependent lower bounds in bandit problems, and what was the unique aspect of the LCB problem that allowed the authors to overcome this limitation here?\n\nPeeling Technique and Extensions: Please highlight the novelty and essential nature of this grouping/peeling proof technique. What is the fundamental mechanism that allows it to achieve tighter, variance-dependent results compared to prior methods? Can the authors speculate on how this technique might be useful for other problems or domains, particularly in terms of extending the ideas to more complex bandit style problems beyond the linear contextual case?\n\nBroader Context: Please situate this result within the broader literature of lower bounds for bandit type problems (i.e., not just linear contextual). Does this result have broader implications based on the established hierarchy of these problems (e.g., standard MAB, stochastic contextual, LCB)?\n\nAdversarial Bound (Collaboration): Regarding the \"collaboration\" notion, please clarify the specific regret bound on SAVE (or the best known algorithm in this setup) that your lower bound is being compared against under your definition of the adversary.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The derivation of variance-dependent lower bounds is an important and challenging problem in bandits literature. Achieving near-tightness (up to logarithmic terms) under a generalized heteroscedastic setting is a significant theoretical advance.\n\nThe proposed \"peeling\" or \"grouping\" technique appears to be novel and essential in obtaining these sharper bounds, suggesting its potential applicability to other structured problems (see my questions for more discussion on the implications of this machinery).\n\nThe analysis under varied assumptions on adversarial strength adds depth and robustness to the result.", "weaknesses": "The bibliography contains several critical errors that must be corrected before publication:\n - The first entry appears to be duplicated.\n- The citation for Dani (2008) is reportedly incorrect and should instead refer to the CoLT (Contextual Linear Threshold) paper.\n- Several cited preprints have since been formally published (journal articles, updated conference proceedings) and must be updated to their final, official citations.\n\nThe statement of Theorem 4.1 (and many such statements) are imprecise and somewhat confusing. The authors should rigorously re-examine this statement for technical correctness and clarity.\n\nThe paper introduces a notion of \"collaboration\" or a specific form of an adversary. Claiming \"near-tight\" bounds is only meaningful if the lower bound is tight against the existing upper bounds (like SAVE or similar) under the same set of assumptions. If the adversarial definition is fundamentally different from the standard setting used for upper bounds, the claim of near-tightness seems misleading? Feel free to clarify this point for me, I am unfamiliar with this literature. \n\nThe writing quality is generally acceptable, but the material can be opaque at times. Given that most detailed proofs are deferred to the appendix, the main body should dedicate more space to building intuitive understanding of the key proof ideas. Specifically, the high-level intuition behind the \"peeling\" technique needs to be expanded in the main text for the uninitiated reader.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OLYoVUc3nO", "reviewer": "Reviewer_dB4e", "summary": "The paper studies the variance-dependent lower bound for the linear contextual bandits.\nWhile the previously known lower bound required the specific choice of variance-sequences $\\{\\sigma^2_k\\}$ and only considered the total fixed variance budget,  this paper extends the analysis to more general variance sequences.\n\n For the prefixed sequence, where the variance sequence is revealed to the learner at the beginning of the learning process, the paper establishes an expected lower bound of　$\\tilde{\\Omega}( d \\sqrt{\\sum_{k=1}^K \\sigma^2_k })$．\n\n\nFor the adaptive sequence: for the weak adversary (who must generate the $\\sigma_k$ before observing the decision set $D_k$), \nthey provide  the high probability lower bound of $\\tilde{\\Omega}( d \\sqrt{\\sum_{k=1}^K \\sigma^2_k })$.\n\n\nFor the strong adversary who can generate $\\sigma_k$ after observing the decision set $\\mathcal{D}_k$, they show that the counter algorithm can collaborate with the adversary and achieve $O(d)$ regret even when $\\sum \\sigma^2_k =\\Omega(K)$. This is due to the construction where the learner can effectively observe noise-free rewards in certain rounds depending on $\\mathcal{D}_k$ and action set, obtaining full exploration in just $d$ rounds. In the remaining rounds, even when the variance is one, the regret remains  $O(d)$ when $K >2d$.", "questions": "For the strong adversary who can generate $\\sigma_k$ after observing the decision set $\\mathcal{D}_k$, the reason why a counter algorithm cooperating with the adversary incurs only $O(d)$ regret is that the construction allows the adversary to assign zero variance in certain rounds. What if we restrict the strong adversary to generate strictly positive (non-zero) variance?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The heteroscedastic linear contextual bandit  is a general model and it is important to investigate the lower bound of the cumulative regret. The previous result  only considered the total fixed variance budget.  This paper extends the analysis to handle more general variance sequences.\n\n- The lower bounds match the upper bound in Zhao et al. (2023) up to logarithmic factors.\n- A peeling technique for prefixed variance sequence and the orthogonal construction of decision sets across different groups are novel techniques to provide novel hard-to-learn instances.\nTheorem 5.2 is the first high-probability lower bound for linear contextual bandit.", "weaknesses": "- Theorem 5.2 has additional dependency of $1/\\log^6(dK)$, which is logarithmic but still somewhat loose compared to the upper bound.\n- See also the question below regarding the assumptions in Theorem 5.4.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)