Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set
Authors: Heyang Zhao
Tianyuan Jin
Weixin Wang
Vincent Y. F. Tan
Pan Xu
Quanquan Gu
Venue: ICLR 2026 Poster (2026)
Keywords: linear bandits
heteroscedastic noise
simple regret
Primary area: reinforcement learning

Abstract: Recent years have witnessed increasing interests in tackling heteroscedastic noise in bandits and reinforcement learning \citep{zhou2021nearly, zhao2023variance, jia2024does, pacchiano2025second}. In these works, the cumulative variance of the noise $\Lambda = \sum_{t=1}^T \sigma_t^2$, where $\sigma_t^2$ is the variance of the noise at round $t$, has been used to characterize the statistical complexity of the problem, yielding simple regret bounds of order $\tilde{\mathcal O}(d \sqrt{\Lambda / T^2})$ for linear bandits with heteroscedastic noise \citep{zhou2021nearly, zhao2023variance}. 
However, with a closer look, $\Lambda$ remains the same order even if the noise is close to zero at half of the rounds, which indicates that the $\Lambda$-dependence is not optimal.

In this paper, we revisit the linear bandit problem with heteroscedastic noise. We consider the setting where the action set is fixed throughout the learning process. We propose a novel variance-adaptive algorithm VAEE (Variance-Aware Exploration with Elimination) for large action set, which actively explores actions that maximizes the information gain among a candidate set of actions that are not eliminated. With the active-exploration strategy, we show that VAEE achieves a *simple regret* with a nearly *harmonic-mean* dependent rate, i.e. $\tilde{\mathcal O}\Big(d\Big[\sum_{t = 1}^T \frac{1}{\sigma_t^2} - \sum_{i = 1}^{\tilde{O}(d)} \frac{1}{[\sigma^{(i)}]^2} \Big]^{-\frac{1}{2}}\Big)$ where $d$ is the dimension of the feature space and $\sigma^{(i)}$ is the $i$-th smallest variance among $\\{\sigma_t\\}_{t=1}^T$. For finitely many actions, we propose a variance-aware variant of G-optimal design based exploration, which achieves a 
$\tilde {\mathcal O}$ $\bigg(\sqrt{d \log |\mathcal A| }\Big[ \sum\_{t = 1}\^T \frac{1}{\sigma\_t\^2}- \sum\_{i = 1}^{\tilde{O}(d)} \frac{1}{[\sigma^{(i)}]^2} \Big]^{-\frac{1}{2}}\bigg)$  simple regret bound. We also establish a nearly matching lower bound for the fixed action set setting indicating that \emph{harmonic-mean} dependent rate is unavoidable. To the best of our knowledge, this is the first work that breaks the $\sqrt{\Lambda}$ barrier for linear bandits with heteroscedastic noise.

Published as a conference paper at ICLR 2026
BREAKING THE TOTAL VARIANCE BARRIER: SHARP SAMPLE COMPLEXITY FOR LINEAR HETEROSCEDAS- TIC BANDITS WITH FIXED ACTION SET
Heyang " Tianyuan Jin Weixin Wang Vincent Y. Tan Pan Xu Quanquan Gu
l DDpaarmeett of Computer Science, University of California, Los Angeles
2 Department of Electrical and Computer Engineering, National University of Singapore
a "Department of Biostatistics & Bioinformatics, Duke University
'Department of Computer Science, Duke University
Department of Electrical and Computer Engineering, Duke University (hyzhao, egu @gu)
@cs cucs.uclas uula edu {t (tinnyuan, vian)enus edu. sg [weixin, wang, pan. xu decukeecc .ddu
ABSTRACT
Recent years have witnessed increasing interests in tackling heteroscedastie noise in bandits and reinforcement learning (e.g., Zhou et al. 2021 Zhao et al. 2023a Jia al. 2024 Pacchiano 2025). In these works, the cumulative variance of the noise A Ex=1 of. where of is the variance of the noise round is used to characterize the statistical complexity of the problem, yielding simple regret bounds of order (d A/T2) for d-dimensional linear bandits with heteroscedas- tic noise (Zhou et 2021 Zhao et al. 2023a). However, with closer look, remains the same order even if the noise is close to zero at half of the rounds, which indicates that the A-dependence not optimal.
In this paper, we revisit the stochastic linear bandit problem with heteroscedastic noise, where the action set is prefixed throughout the learning process. We pro- pose novel variance-adaptive algorithm VAEE (Variance-Aware Exploration with Elimination) for large action set, which actively explores actions that maximizes the information gain among candidate set of actions that are not eliminated. With the active active-explon exploration strategy, we show that VAEE achieves a simple regret with a
nearly harmonic-mead dependent rate, i.e., ò ((d Σt of Eold
where (8) is the i-th smallest variance among {o:)T For finitely many ac- tions, we propose variance-aware variant of G-optimal design based exploration,
which achieves a simple regret of Ö Vdlog [A| ΣT= J -
O(d)
[OOP
We also establish nearly matching lower bound for the fixed action set setting indicating that harmonic-mean dependent rate is unavoidable. To the best of knowledge, this is the first work that breaks the vÁ barrier for stochastic linear bandits with heteroscedastic noise.
INTRODUCTION
The stochastic multi-armed bandit (MAB) problem is a fundamental framework for studying the exploration-explootttion trade-off in sequential decision-making (Auer al. (002). In the clas- sic stochastic bandit setting, an agent repeatedly selects an arm from set of arms and receives
"Equal contribution.
'The formal notation given by (c[EEz o. EiE Topp
where ((d,T) Ö(d) is
function of d and T. For simplicity, we ((d) denote ((d, throughout the paper.

---

Published as a conference paper at ICLR 2026
stochastic reward associated with the chosen arm. The goal of the agent is maximize the cumu- lative reward over a series of rounds by balancing exploration (trying out different arms to gather information) and exploitation (choosing the best-known arm based past observations). Over the past few decades, various algorithms have been proposed to tackle the stochastic bandit problem from the perspectives of minimax optimal sample complexity (Audibert & Bubeck 2009 Ménard & Garivier 2017, Jin et al. 2021 (023).
To further leverage the heteroscedastic nature of the noise in real-world applications, recent works have extended the classic bandit framework to account for heteroscedastic noise, where the vari- ance of the noise can vary across different arms and time steps (Zhou et al. 2021] Zhao et al.j 2023a Jia et al., [2024] Pacchiano, 2025). These works have shown that by taking into account the varying variance of the noise, it is possible to design more efficient algorithms that achieve bet- ter performance in terms of regret bounds. In detail, [Zhou et al. (2021) first considered the linear bandit problem with heteroscedastic noise and proposed variance-aware algorithm that achieved a regret bound of order Ó(d/A + vdT), where = =-r= of is the cumulative variance of the noise along T time steps and d is the dimension of the feature space. Later, Zhou & Gu (2022) improved the cumulative regret bound to Odv A + d), yielding simple regre bound of order O(d/A/T2 + d/T). More recently, Jia et al. 2024 proposed VarCB, which achieves a tighter cumulative regret bound of order Ō ((vIA|Ad + d²)) for contextual bandits with a fixed action set, where |A] is the size of the action set and A Σi=1 of is the variance budget, and further extended their analysis to general function classes. In the same work, they proved a minimax lower bound of order 2(, ( d) d+) when d < VAAT. T, showing that the VA dependence is unavoidable in the worst case over instances and variance sequences. Recently, He Gu (025)) further estab- lished (up logarithmic factors) matching variance-dependen. lower bounds of order Ω (dvAA for linear contextual bandits with time-varying action sets and arbitrary variance sequences, confirming that the v scaling is information-theorrtiialll optimal even when the entire variance sequence is revealed the learner. On the other hand, [e & Gu (2025) proved that for stochastic linear bandits where the action set prefixed, the Ω ((dvA) lower bound does not hold. This motivates to pursue sharper variance-dependent regret bounds for stochastic linear bandits with a fixed action set (either finite or infinite).
More specifically, existing regret bounds depend on the total variance term A, which overlooks the heterogeneity of information gain across actions and time steps with different noise levels. Consider an extreme case: if of parameter in the linear bandit problem could be recovered almost exactly. In such case, the regret bound should be essentially independent of the noise variance after time step to- This motivates an important open question in heteroscedastic stochastic linear bandits:
for all S to with to O(d) < T. the d-dimensional weight
Can we improve upon the VA dependence in the regret bounds in stochastic linear heteroscedastic bandits?
In this paper, we revisit the problem of best-arm identification in stochastic linear bandits under het- croscedastic noise, where the action set is prefixed and the variances of the reward distribution may vary significantly across actions. The primary performance metric focus is the simple regret, which measures the suboptimality of the action recommended after a fixed budget of exploration. Our results highlight the fundamental role of the harmonic mean of the variances in characterizing the attainable regret rate.
Our main contributions are summarized as follows:
Variance-adapptive exploration for large action sets. We propose novel algorithm, VAEE (Variance-Aware Exploration with Elimination). designed to handle large (potentially infinite) action sets. The key idea to maintain candidate set of promising actions and actively ex- plore those that maximize the information gain subject to elimination rules. We prove that VAEE
Simple regret quantifies the expected gap hetween the optimal reward and the reward of the arm proposed by the algorithm.
2

---

Published as a conference paper at ICLR 2026
Table 1: Comparison between different algorithms for stochastic (linear) contextual bandits. Here d is the feature dimension, I' is the number of rounds, {orheetry is the variance of noise at round t [T], |A] the size of the arm set, and A = Σ'= of is the cumulative variance of the noise. The time-varying means that the action set is allowed to change over time (possibly chosen in advance by an oblivious adversary), whereas fixed means that the same action set used all rounds. The infinite means the action set may contain infinitely many actions, whereas finite means the action set contains only finitely many actions. The lower bounds from Jia et al. (2024); He & Gu (2025) simple regret by
derived for the cumulative regret. We convert them to be comparable dividing them by T. Note that their lower bounds are derived for the worst case sequence of noise
variance, while our lower bound has refined dependence the noise variance sequence.
Algorithm
Simple Regret Upper Bound
Simple Regret Lower Bound
Action Set
Weighted OFUL Zhou et al. 2021
dy 1/T A/T/2 6/5 v ///72
Time-varying/Iniin
Weighted OFUL- Zhou de Gu
2012
Time-varying/Inlinn
VOFUL Zhang
Time varying/Inliiinn
VOFUL [Kim
2021
8812 /A/T2
Time-varying/Infiie
SAVE Zhao et ml 2023n
A/NTT
time- monevaaying/Tnfiiitt
LinNATS Xx 2023
6312 VA/T
Time-varying Innfiiilnniiiii
VarB Jia 2024
M
B(ymiut minit 2)A/77 (1/9)
Time-vag sere-vaariin/iiiii
Gu 2025
Time-varying/Iutie
VAEE (Ours)
Dim1 jolu Σ
2 a(d(Ei-i .t)
Fixed/Infinite
VAGD (Ours)
v dog
A
Σ ot
Fixed/Finite
achieves simple regret bound of
<dE - - Σ
( T
0(d)
6
where d is the feature dimension, and [1){)) are the ordered list of the variance sequence } This establishes nearly harmonic-mean dependent rate for the simple regret.
Variance-awane G-optimal design for finite action sets. For the case of a finite action set A. we propose a variance- adaptive variant of G-optimal design based exploration. We show that this strategy achieves simple regret bound with improved dependence the dimension d as follows
( (VValg dog A
T Σ
((d)
Lower bound matching the harmonie-mean rate. We establish a nearly matching lower bound for the fixed-action setting, showing that the harmonic-mean dependence is intrinsic to the prob- lem. This demonstrates that our algorithms are essentially optimal their variance dependence.
Breaking the VÀ barrier. To the best of our knowledge, this is the first work that surpasses the classical / /A-type dependence in simple regret bounds for linear bandits with heteroscedastic noise, where A denotes the variance proxy commonly used in prior analyses. A comprehensive comparison on the simple regret bounds is provided in Table 1 for the reader's reference.
Notations. We use bold lowercase letters (e.g., a) to denote vectors and bold uppercase letters (e.g., A) to denote matrices. For vector E Rdd we use ||a||2 to denote its Euclidean norm. For positive definite matrix A Rdxdd define the elliptical norm of vector We use I to denote the d x d identity matrix. For a set A, we use |A] to denote its cardinality. We use Ö(-) to hide logarithmic factors in d, T, 1/5, 1/ 1/0min: 1/ 1/0maxx For a sequence {a+)T= we use a( to denote the i-th smallest element in the sequence.
||a||A Va T Aa.
2 RELATED WORK
Variance-Awand Regret for Linear Bandits with Heteroscedastic Noise. The incorporation of variance information in linear bandit algorithms has garnered significant attention in recent years,
3

---

Published as a conference paper at ICLR 2026
leading to substantial improvements in regret bounds. Early work by Kirschner & Krause (2018) introduced the concept of informatiin-direectedd sampling for bandits with heteroscedastic noise, demonstrating that leveraging variance information
lead to more efficient exploration strate- gies. Later, /Zou et al. (202)) proposed a variance-aware algorithm for linear bandits that achieves a regret bound of order O + VdT), where A = E
1=1 of is the cumulative variance of the further improved by Zhou & Gu 2022)
tighter bound of Odv d)- Zhao et al. 2023b) later proposed a peeling-basee a algorithm that achieves a similar regret bound.
noise. This result
The challenge of unknown conditional variances has been addressed by several researchers. Zhang at. (002) Kim et al. (202T) developed algorithms that operates without prior knowledge of the variance, achieving regret bounds that adapt the observed noise levels. However, these approaches are not tractable for large action sets and incur sub-optimal dependence on d. Zhao et al. (2023a) proposed a computationally efficient algorithm that achieves regret bound of order O(dv A + d) without requiring prior knowledge of the variances.
extended the variance-aware framework of Zhao et al. (2033a) to the general function approximation setting, achieving regret bound of order Oddelder / (J) + detader lJ)(F)), where deluder is the eluder dimension and log(FF is the log-covering number of the function class F. Concurrently, Jia et al. (2024) introduced Va rCB, an algorithm that attains a regret bound of Ö ( /IAIAd++ d²) for bandits with few actions, and extended their results to general function classes. They also established a worst-case lower bound of order ((ymin [A],d)A + d) when S V|AIT. He & Gu (2025) further studied the setting where the action set can change arbitrarily over time and proved an instance-dependent lower bound of order (dv log T) for the expected cumulative regret. These results indicate that the vA dependence is unavoidable in such settings.
More recently. Pacchiano 2025)
Bandits with Heavy-Tailed Noise. The topic of robustness heavy- rewards has received considerable attention in recent years, addressing the limitations of classical bandit algorithms that assume sub-Gaussian bounded noise. Bubeck et al. (2013) pioneered this research direction by studying heavy-tailed rewards in multi-armed bandits, establishing that standard concentration in- equalities fail in such environments. For linear bandits, Medina Mediiaa & Yang (2016) proposed truncation- based methods and peciian-of-meant
estimators to handle heavy-tailed noise, achieving sublinear regret bounds. (hao et al. (2018) adopted median-of-mean techniques with a well-designed allo- cation of decisions to achieve nearly optimal regret bounds. Later, Xue et al. (2020) introduced SupLin-based algorithm (Chu et al. 201 I) which further improved the dimension dependence the regret bounds. More related works include Li & Sun (2024), Huang et al. 2023), which proposed Huber regression based algorithms to handle heteroscedastic heavy-tailed noise. Recently, Ye et al.) (025) proposed a Catoni's 's estimator based algorithm that achieves adaptive regret bounds in bandits with general function approximation.
Depeeden Bounds in MDPs. As natural extension of bandits, Markov Decision Pro- cesses (MDPs) have also been studied under the lens of variance-depenndnt regret bounds. In tabular MDPs, Zanette & Brunskill (2019) first established variance-dependent regret bound which scales with the square root of the maximum variance of the value function. Afterwards, Zhou et al. (2023) proposed MVP-V, an algorithm that achieves a regret bound scaling with the square root of the total variance of the value function, achieving worst-case optimal regret bound. In MDPs with linear function approximation, Zhao et al. (2023a) proposed a variance-aware algorithm that achieves a second-order and horizon-free regret bound. More recently, there have been several works (Wang) jet al., 2024 Zhho et al., 2024 Wang et al., 2025 Zhao et al., (025)) presenting variance-deepnnent regret bounds in MDPs with general function approximation.
3 PRELIMINARIES
We consider heteroscedastic variant of the stochastic linear bandit problem. Let T be the total number of rounds. The action set AA is fixed. At each round t e [T], the interaction between the agent and the environment is follows:
4

---

Published as a conference paper at ICLR 2026
1. The agent selects a, A based on the past observations Fi-1 (a1, (1.,71..... at-1; up to time --11 1.
2. The environment generates the stochastic noise 77 round and reveals the stochastic reward
Pt -0", a.) + V/t to the agent.
3. The agent observes the variance of rt.-
We assume that for all a E A. it holds that ||a||2 S and ||0' 1.
Remark 3.1. Our assumption that the action set is fixed necessary for achieving the harmonic- mean dependent rate. In scenarios where the action set can change arbitrarily over time, it is possible to construct instances where the cumulative variance measure of statistical complexity. This is because an adversarially chosen action set can force the algorithm to repeatedly explore less informative actions when the noise level is low, thereby negating the benefits of harmonic-mean based approach. A detailed study of this phenomenon is provided by HH Gui (2025), which demonstrates that in the case of adversarially changing contexts, there exists a lower bound of order (dd A/ log T) for the expected cumulative regret, indicating that the VÄ dependence is unavoidable in such settings.
Σ'= of remains the most appropriate
Therefore, to fully leverage the advantages of our proposed variance-adaptive algorithms and achieve the improved regret bounds, we focus on the standard stochastic linear bandit setting (Latti- more & Szepesvári, 2020) where the action set is fixed throughout the learning process.
We introduce the following assumption on the noise 1)c-
i.e. for all E R, holds that [exp (Arx) | FF-1] exp(X²at/2) where Fz-1 1 is the filtration up round I 1. We assume that there exist known constants Fmin; maax > 0 such that Jmin & at S Tmax for all E [7]-
Assumption 3.2. The noise T). is conditionally
Remark 3.3. This assumption follows from the original formulation of heteroscedastic bandits by Kirschner & Krause (2018). Later works (Zhou et al.) [2021] Zhao et al.) [202aa] Jia et al.] (2024) have slightly generalized this assumption to only require the variance of 7) to be bounded by of and the magnitude of 7) to be bounded by constant. However, this generalization does not significantly affect our analysis or results, as we will discuss in in[Appendix E that our algorithms can be extended handle heavy-tailed noise by replacing the least-squares estimator with robust estimator.
In this paper, we focus on the best-arm identification problem in linear bandits with heteroscedastic noise. The performance of an algorithm is measured by the simple regret defined as follows:
SR(T) E max nEA
(0", a) (0", âr)).
(3.1)
where år is the action recommended by the algorithm after I rounds of exploration.
Remark 3.4. In the stochastic linear bandit literature, simple regret is closely connected to cumu- lative regret. In particular, an algorithm achieves cumulative regret of order O(VdT), then its simple regret can be shown to be of order Ō Vd/T) (Lattimore & Szepesvári 2020). In the het- croscedastic setting, however, the varying and unpredictable noise levels make this relationship more subtle. For example, harmonic-mean dependence of the simple regret on the variances does not necessarily translate the same dependence for cumulative regret. In this work, we therefore focus on directly analyzing the simple regret of our proposed algorithms.
4 STOCHASTIC LINEAR BANDITS WITH INFINITE ACTION SPACE
In this section, we propose Variance-Aware Exploration with Elimination (VAEE), variance- adaptive approach designed for linear bandits operating in environments with heteroscedastic noise and potentially large action spaces. The algorithm is displayed in Algorithm I which builds upon the Optimism in the Face of Uncertainty for Linear bandits (OFUL) framework while incorporating variance information improve exploration efficiency and regret bounds.
Variance Adaptation. The algorithm explicitly incorporates variance information o, observed at each time step and uses variance- weighted updates for both the covariance matrix and parameter estimation (Zhou et al.) 202T). This allows the algorithm to adaptively adjust its confidence sets based on the observed noise levels, leading accurate estimates of the underlying parameters.
5

---

Published as a conference paper at ICLR 2026
Active Exploration. Algorithm 1 employs active exploration strategy that selects actions based on their potential to maximize information gain. Specifically, at each round, the algorithm chooses the action that maximizes the uncertainty in the parameter estimate, measured by the Mahalanobis distance with respect to the inverse covariance matrix. This encourages exploration of actions that expected provide the most informative feedback.
Algorithm Variance-Aware Exploration with Elimination (VAEE)
Require: A C RRd 8.
1: Initialize V/ < AIa, 0, 0, Ai t A.
2: for / =1,..., do
3: Pull the action a, < maxeEA, ||e||=z)-
4: The agent receives the reward Ti and the variance oz.
5: Calculate Vi2 Vi-1+ of "aaa""
6: Calculate O2 f V E
-=1 o, a.T..
7: Set confidence set as follows C, + 10 1100 0.11,, $ 8t}.
8: Eliminate low rewarding arms: A+t1 f {a E A maXecA, mingec, (0,e)) S
max (0, a)
9: end for
4.1 CASE STUDY ON WHY WEIGHTED OFUL FAILS
We now present two-dimensional case study illustrate that Weighted OFUL (Zhou et 2021 fails for structural reasons rather than due to loose analysis, especially when the variance se- quence contains low-variance windows and the information for learning the d-dimensional pa- rameter vector grows anisotropically across coordinates. In contrast, our variance-sequence-avaa design reallocates exploration toward weak coordinates and achieves an instance- and variance- sequence-dependent bound. In the example below, our algorithm attains simple regret of order eexp(-O(lo) T/ T/=²)), whereas Weighted OFUL yields only exp(- T)). When = 1/4, the simple regret of VAEE is sharper than that of Weighted OFUL by a factor of Te(VT)
Setup. Consider two-dimensional linear bandit with action set A = (2,, 2). where ei (1,0), e2 = (0, 1). and = (1 -1--8 E, E). and with true parameter vector
ei. We take confidence radii satisfying 3r S 3 = O (og T' and set = 1/4 The variance profile contains a global window W of length L in which the noise variance is of = T for all E W with E 1), while outside W the variance is constant.
Simplifying assumption. To isolate the behavior along the second coordinate, we make the fol- lowing simplifying assumption. We assume that before entering W, both algorithms have already collected enough information in the e₁ direction that the estimation error in the first coordinate is negligible. This is justified because pulls of éj and x both provide substantial information about the first coordinate, and both our method and Weighted OFUL sample (or e₁) frequently. As result, information in the first coordinate dominates that in the second, and the dominant source of error comes from limited information along the second coordinate, which is therefore our focus.
Weighted OFUL in the Low Variance Window. In the low-variance window W where of = T-", cach pull of an contributes T (a, e2)² units of information to the second coordinate.
Case (start with 02). If Weighted OFUL initially pulls e2 in W, then each pull adds 7 units of second-coordinate information. After about log T e22 such units have been gathered, the second- coordinate error at most E. Since Hx = (x, 0-) = E and 0" E C. w.h.p., we have Pzz S o(1).
UCB,, (f) and hence (t) 2
Moreover, after m = ( log T pulls of e2 we have m = O(log T/e3), so |le2ly,
( (le/vlogT) and therefore UCB2(t) = (ez, 0.) + S <=+0(B// = 0(c) o(1) using & = 1/4 and 3 O(Voo T). Thus UCB2(t) < UCB,(t) and Weighted OFUL switches to selecting

---

Published as a conference paper at ICLR 2026
Case 2 (keep pulling z). If instead Weighted OFUL keeps pulling throughout W, then each pull of information
I contributes only E²T to the 62 direction, so after pulls the total most L T
Simple Regret of Weighted OFUL. Choose L = c₁ CT log LE = ct log T. By
standard Chernof/Hooefddnng concentration, the failure probability of recommending dT = x decays
as exp (log T),, hence the simple regret satisfies SR(T) Σ e e.cxp @log 7))-
Simple Regret of Algorithm [ Since algorithm pulls the arm with the largest exploration bonus (Line 3 of Algorithm 1 it allocates the window W to 62 and gains I.7a en log units of second-coordinate information within W. By a standard concentration inequality, the failure probability of recommending at decays as exp
hence the simple regret satisfies SR(T) & E exp (llog//E2)) Since E = T our simple regret significantly lower than that of Weighted OFUL by a factor of T
4.2 THEORETICAL RESULTS FOR VAEE
We now present the main theoretical results for VAEE. The following theorem establishes simple regret bound with harmonic-mean dependence.
Theorem 4.1 (Simple Regret of VAEE). Set B. 2v 1oglog(411))) dolog dA+to min and
(2) 1 in Algorithm Let dip be the i-th smallest element in (o With probability least
1 - 6, the simple regret of Algoorimm satisfies
SR(T) Ö(Vd), min IskST+1
x
10
10 (k(--))
(6) of ]
Σ
i=
10
where (() 2d 2o + ErETTy /dd/
Remark 4.2. Theorem 4.1 provides a simple regret bound for VAEE that depends on the harmonic
mean of the variances o, To see this, we can simplify the bound by substituting & = ((d) and (T) = Ö(d), which yields the following simplified expression:
SR(T)= -0 -
Σ T
Óld)
(4.1)
This bound in 1 highlights that the simple regret decreases as the harmonic mean of the variances increases, effectively capturing the influence low-variance actions on the overall performance. Notably, this result breaks the traditional VĀ barrier, where A = Σ I of. demonstrating that our variance-adaptive approach can achieve significantly better performance in environments with heteroscedastic noise.
Remark 4.3. It is worth noting that our harmonic-mean dependence subtracted by the contribu- tion of the Ö(d) smallest variances. This subtraction is unavoidable due to the inherent difficulty of estimating dl-iimeniionl parameter, which requires at least d well-explored actions. In the worst- case scenario, these actions may correspond to the smallest variances, and then is impossible to achieve near zero simple regret with only T O(1) rounds of foise-free exploration. Therefore, the subtraction term in our bound is necessary to account for this fundamental limitation.
Nonetheless, we can still show that our simple regret bound strictly sharper than the VT-ype
bounds in prior works (Zhou al. 2021 Zhao
al.) 2023at Jia et al. 2024). To see this,
observe that minn
E [o
(k-1)
oT }}
(K)
is the solution to the following
equation:
x
c(t)
We further have
max(e?
((t)
(t)
(1)(2 + +1-1111 D
+ of)
x² < Σ Di=l of+2
(4.2)
t
2 1 EE

---

Published as a conference paper at ICLR 2026
Table 2: Simple and Cumulative Regrets of Algorithm and Weighted-OFUL (Zhou & Gu 2022
We use R(T s Σ SR(t) upper bound the regret of Algorithm | All comparisons in Table
are made under the assumption that D 1/02 >
Lond) 1/ For the concrete variance profiles in the table this assumption holds when T is large enough relative to d: for the fast-decaying,
flat-noise, and many- moderate-eptiiieee profiles is satisfied as soon as T > d, while for the front-
loaded super-precision profile holds once T > d=/1
Simple Regret
Cumulative Regret
Algorithm
Weighted OFUL
Algorithm
Weighted OFUL
Fast-Decaying Noise
of 1/12 of 1/d
Ól
o(
Öldj Ó(vāT)
Oid)
Flat Noise (1/a)
σly 4)
6l 4)
o(vaT)
a E (0, 1), of
Many Moderate Spilke
2, aT,
0 pm))
0 ((+)
O(dTl/)
O(dvr)
aT,
Frout-Loaded Super-Precision
/min41/2, 2h 1/22
1 TM
ōl p
ō(avT)
15 T4P
where the second inequality follows from mean inequality. Rearranging the terms yields x² Ódd/tt2 when (d)). Please refer to Appendix B for detailed derivations.
4.3 COMPARISON WITH WEIGHTED OFUL
In this subsection, we present case study to illustrate the limitations of using the cumulative vari- ance A Ei= of noise and the polential weakness of existing algorithms that rely on this measure. For simplicity, we
measure of statistical complexity in linear bandits with heteroscedastic
((d) assume ΣT= 1/0, i=1 1/(o(0)3. Therefore, according
4.1 and Zhou & Gu 2022).
T Σ
1/2
SHweighted OPULL d ET of T
SRAy
(4.3)
First, by the HM-AM inequality, we have T/(E, 7 S Eooi/T, which leads to general rela- tionship between the regret bounds of our methods: SRAy S SR -OFUL for any sequence
a?- Therefore, our regret bound is always sharper whenever Ei=11/1 > ΣoId) 1/(o In the we demonstrate the specific rate of improvement for some special variance sequences. We note that an improvement in simple regret does not necessarily lead to an improvement in cumulative regret. For example, this is evident in fast-decaying noise, as discussed in Remark 3.4
Table 2
STOCHASTIC LINEAR BANDITS WITH FINITE ACTION SPACE
In this section, we consider the special where the action set A is finite. We propose variance- adaptive G-optimal design based exploration strategy and establish a simple regret bound with harmonic-mean dependence which improves over Theorem 4.1 by a factor of vd.
5.1 VARIANCE-ADAPTIVG G-OPTIMAL DESIGN BASED EXPLORATION
G-optimal design. In Algorithm we need to find a nearly G-optimal design æ E A(A) that maximizes log det Vir). We first introduce some necessary notations and definitions garding Dooptimal and G-optimal designs. Let π : A + [0. 1] be a distribution on A so P(Ae), define V(T) E Rdxd and g(T) E R as fol- lows V(z)= EaEA T(a)aa, g(x) = maxae [|al//
that EnEA π (a) 1. Based
design æ is defined as a G- optimal design minimises And design is defined as a D-optimal design if it maximises f(T) log det (TT). The set Supp(T) is sometimes called the core set. The following theorem characterizes the size of the core set and the minimum of and establishes the equivalence optimal and D-optimal designs.
8

---

Published as a conference paper at ICLR 2026
Algorithm 2 Variance Adaptive G-Optimal Design (VAGD)
Require: A C _R_ Find nearly G-optimal design E ((A) with [supp(#)] I 4d log 16 as described in
Theorem 5.2 that minimizes
max [a]]v[))- subject to aEA
Σ T(a) =
aEA
2: Let To(a) < 2 for all E A.
3: for = =1...., do
4: Pull the action a, =- argmin EFET(a) (f
5: Observe reward r, and variance dr.
6: Update the set Ta(a:) +- Tz-1(a;) U {+} and Tr(a) t- Ti-1(a) for all
7: end for
8: Outout ar+1 argmax (02,a) a) where Or VT -V-'E of 2 3raa and Vi I +
Σ1= o 2 aaaa.
Theorem 5.1. (Lattimore & Szepesvári 2020 Siefer-Wolfowitz Assume that A C IR is compact and span(A) R" The following are equivalent: (a) n² is minimiser of g: (b) nt" a maximiser of (TT) log det (TT); (c) g
d.
Furthermore, there exists a minimiser xt of such that Supp (T*) S d(d 1)/2.
However, the which may cause additional overhead in our variance-adaptive algorithm. To address this issue, we can find an approximate G-optimal design with a smaller core set size using the following theorem. Theorem 5.2 (Lattimore et al. 2020). Suppose that A C IR is compact and span(A) = R.. There exists a probability distribution π E (AA) such that g S 2d and the cardinality of the core set of is at most 4d log log d + 16.
size of the G-optimal design given by Theorem 5. is at most d(d 1)/2.
Adaptive arm selection. After obtaining the approximate G-optimal design 9,, we use it to guide the arm selection process. Unlike traditional G-optimal design- based algorithms, which pull arms according to the fixed distribution π, our algorithm adaptively selects arms based on the observed variances o, Specifically, at each round t, choose the arm a, that has been pulled the fewest times relative to its probability under æ, weighted by the inverse of the observed variance. This adaptive strategy prevents over-exploration caused by the unpredictable and heteroscedastic nature of noise and ensures that we collect sufficient information from all arms in the core set of π.
variance-weighted Weighted least-squares estimator. Inspired by Zhou et (021). we use a variance- weighted least-squares estimator to estimate the unknown parameter 0 Specifically, after T rounds of ex- ploration, we compute the estimator Or as follows:
T V+=++
θ = VT T. r,,
Σ
o
a,a
1=1
Under the finite action space regime, we show that this estimator achieves tighter confidence bound compared to the general case, replacing the Vd factor with Vlog((AA)) in the confidence radius.
Finally, we recommend the action a that maximizes the estimated reward based Ör.
5.2 SIMPLE REGRET BOUND FOR VAGD
Theorem 5.3 (Simple Regret of Algorithm 2) Suppose that A C IRd is compact and span(A) = R.d. If we follow Algorithm 2 then holds that with probability at least
T
log log
(0, (0',a)) - (07)))+) // dlog((-A1/))/
Σ
o

---

Published as a conference paper at ICLR 2026
Remark 5.4. Theorem 5.3 establishes simple regret bound for Algorithm 2 that depends the harmonic mean the noise variances of while improving the dependence on the dimension d com- pared to Theorem 4.1 In particular, the vd factor in the numerator replaced by / (log(AA which can be substantially smaller when the action set is finite and of moderate size. This improvement obtained by exploiting the finite action space structure and employing variance-adaptive G-optimal design exploration strategy. Consequently, Algorithm i especially effective in settings with lim- ited action sets, enabling more efficient exploration and improved simple regret performance.
LOWER BOUND
In this section, we establish a lower bound for the simple regret in linear bandits with heteroscedastic noise. Our lower bound nearly matches the upper bound in Theorem 4.1 up to logarithmic factors, demonstrating the optimality of our proposed algorithm.
Theorem 6.1 pesstance-depndenn lower bound.). For any d > 2 and T 2 1, and any algorithm A, there exists linear bandit instance with heteroscedastic Gaussian noise satisfying our assumptions such that the simple regret is lower bounded as follows:
-1/2 1/2
E(SR(T)) N d
3 -d
(E7)
Σ o
16
lower bound for the simple regret in linear bandits with heteroscedastic noise. This lower bound matches the upper bound in Theorem 4.1 up to logarithmic factors, indicating that our proposed algorithm is nearly optimal in terms of its dependence on the harmonic mean of the variances of. This result highlights the fundamental difficulty of the best-arm identification problem in linear bandits with heteroscedastic noise and underscores the effectiveness of our variance -ddaanii approach. In contrast, in Table I the worst-case lower bound established in previous studies (He & Gul [025] Jia al., 2024) is derived by constructing an instance where all variances are equal, which does not capture the complexity of heteroscedastic linear bandits, especially when the variances vary significantly across actions and time steps.
Remark 6.2. Theorem 6.1 establishes variance-sequenccedeeeee
7 CONCLUSION AND FUTURE WORK
In this paper, we study the sample complexity of stochastic linear bandits with heteroscedastic noise under fixed action set. We propose variance-adaptive algorithm that achieves nearly instance- optimal simple regret bound, characterized by the harmonic mean of the noise variances. We further establish nearly matching lower bound, demonstrating the optimality of our algorithm. Together, these results provide comprehensive characterization of the statistical complexity of linear bandits with heteroscedastic noise.
There are several promising directions for future work. First, one could consider settings where the context is not fixed but instead sampled from an unknown distribution. Second, it would be natural to extend our results to the case where the noise variances are unknown and must be estimated from data. Third, in reinforcement learning, the variance of the noise governed by the transition dynamics, which can themselves be estimated from historical data. Extending our results to Markov decision processes using such estimated variances would be an interesting direction to explore.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENT
We thank the anonymous reviewers and area chair for their helpful comments. HZ and QG are supported in part by the National Science Foundation DMS- 233-1333113 and IIS-2403400. HZ is also supported in part by Amazon PhD Fellowship. T. Jin and V. Y. F. Tan are supported by Singapore Ministry of Education (MOE) AcRF Tier grant under grant number 4-8004062-00-00 WW and PX are supported in part by the National Science Foundation (DMS-2323112)) and the Whitehead Scholars Program at the Duke University School of Medicine. The views and conclusions contained in this paper 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. Advances in neural information processing systems, 24, 2011.
Jean-Y Yves Audibert and Sébastien Bubeck. Minimax policies for adversarial and stochastic bandits. In COLT, pp. 217-226, 2009.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235 256, 2002.
Sébastien Bubeck, Nicolo Cesa-Bianchi, and Gábor Lugosi. Bandits with heavy tail. IEEE Trans- actions on Information Theory, 59(11):7111-7711, 2013.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff func- tions. Proceedings of the fourteenth international conference on artificial intelligence and statistics, pp. 208-214. JMLR Workshop and Conference Proceedings. 2011.
David A Harville. Matrix algebra from a statistician's 's perspective, 1998.
Jiafan He and Quanquan Gu. Variance-dependers regret lower bounds for contextual bandits. arXiv preprint arXiv:2503. 12020, 2025.
Jiayi Huang, Han Zhong, Liwei Wang, and Lin Yang. Tackling heavy-tailed rewards in reinforce- ment learning with function approximation: Minimax optimal and instance-dependent regret bounds. Advances in Neural Information Processing Systems, (6:56576-56558 2023.
Zeyu Jia, Jian Qian, Alexander Rakhlin, and Chen-Yu Wei. How does variance shape the regret in contextual bandits? Advances in Neural Information Processing Systems, 37:83730-83785 83785, 2024.
Tianyuan Jin, Pan Xu, Jieming Shi, Xiaokui Xiao, and Quanquan Gu. Mots: Minimax optimal thompson sampling. In International Conference on Machine Learning, pp. 5074-5083. PMLR, 2021.
Tianyuan Jin, Xianglin Yang, Xiaokui Xiao, and Pan Xu. Thompson sampling with less exploration is fast and optimal. In International Conference on Machine Learning, pp. 15239-15261. PMLR, 2023.
Yeoneung Kim, Insoon Yang, and Lwaang-Sun Jun. Improved regret analysis for variance-adaptive linear bandits and horizon-free linear mixture mdps. arXiv preprint arXiv:2111.03289, 2021.
Johannes Kirschner and Andreas Krause. Information directed sampling and bandits with het- croscedastic noise. In Conference On Learning Theory, pp. 358-384 384. PMLR, 2018.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Tor Lattimore, Csaba Szepesvari, and Gellert Weisz. Learning with good feature representations in bandits and rl with a generative model. In International conference on machine learning, pp- 5662-5670. PMLR, 2020.
11

---

Published as a conference paper at ICLR 2026
Lucien Le Cam. Asymptotic Methods in Statistical Decision Theory. Springer, New York, 1986. ISBN 778-0-387-96317-4
Xiang Li and Qiang Sun. Variance-awar decision making with linear function approximation under heavy-tailed rewards. Transactions on Machine Learning Research, 2024.
Andres Munoz Medina and Scott Yang. No-regret algorithms for heavy-tailed linear bandits. In International Conference on Machine Learning, pp. 1642-1650. PMLR, 2016.
Pierre Ménard and Aurélien Garivier. minimax and asymptotically optimal algorithm for stochas- tic bandits. In International Conference on Algorithmic Learning Theory, pp. 223-237, 2017.
Aldo Pacchiano. Second order bounds for contextual bandits with function approximation. In The Thirteenth International Conference Learning Representations, 2025.
Mark S. Pinsker. Information and Information Stability of Random Variables and Processes. Holden-Day, San Francisco, 1964. English translation of the 1960 Russian edition.
David Ruppert. The elements of statistical learning: data mining, inference, and prediction, 2004.
Han Shao, Xiaotian Yu, Irwin King, and Michael R Lyu. Almost optimal algorithms for linear stochastic bandits with heavy-tailed payoffs. Advances in Neural Information Processing Systems, 31, 2018.
Qiang Sun. Do need to estimate the variance in robust mean estimation? arXiv:2107.00118, 2021.
arXiv preprint
Kaiwen Wang, Owen Oertell, Alekh Agarwal, Nathan Kallus, and Wen Sun. More benefits of being distributional:
Second-order bounds for reinforcement learning. In International Conference on Machine Learming, pp. 51192-51213. PMLR, 2024.
Zhiyong Wang.
Dongruo Zhou, John CS Lui. and Wen Sun. Model-based rl as a minimalist approach to horizon-free and second-order bounds. In The Thirteenth International Conference on Learning Representations, 2025.
Ruitu Xu, Yifei Min, and Tianhao Wang. Noise-adaptive thompson sampling for linear contextual bandits. Advances in Neural Information Processing Systems, 36:23630-23657, 2023.
Bo Xue, Guanghui Wang, Yimu Wang, and Lijun Zhang. Nearly optimal regret for stochastic linear bandits with heavy-tailed payoffs. arXiv preprint arXiv:2004. 13465, 2020.
Andrew Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity. In Proceedings of the 18th Anmual IEEE Symposium Foundations of Computer Science (FOCS), pp. IEEE, 1977.
Chenlu Ye. Yujia Jin, Alekh Agarwal, and Tong Zhang. Catoni contextual bandits are robust to heavy-tailed rewards. Forty-second International Conference on Machine Learning, 2025.
Andrea Zanette and Emma Brunskill. Tighter problem-dependers regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pp. 7304-7312. PMLR, 2019.
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-4355 2021.
Heyang Zhao, Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Variance-deppnndnt regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency. In The Thirty Sixth Annual Conference on Learning Theory, pp. 4977-5020. PMLR, 2023a.
Heyang Zhao, Dongruo Zhou, Jiafan He, and Quanquan Gu. Optimal online generalized linear regression with stochastic noise and its application to heteroscedastic bandits. In International Conference Machine Learning, pp. 42259-42279 PMLR, 2023b.
12

---

Published as a conference paper at ICLR 2026
Heyang Zhao, Jiafan He, and Quanquan Gu. A nearly optimal and low-switching algorithm for reinforcement learning with general function approximation. Advances Neural Information Processing Systems, 37:94684-94447 2024.
Runze Zhao, Yue Yu, Ruhan Wang, Chunfeng Huang, and Dongruo Zhou Instance-dependent continuous-time reinforcement learning via maximum likelihood estimation. arXiv preprint Stti:2500.0020033 2025.
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.
Runlong Zhou, Zhang Zihan, and Simon Shaolei Du. Sharp variance-dependent bounds in reinforce- ment learning: Best of both worlds in stochastic and deterministic environments. In International Conference on Machine Learning, pp. 42878 42914. PMLR, 2023.
13

---

Published as a conference paper at ICLR 2026
A LLM USAGE
We used an LLM only for grammatical and stylistic polishing of the manuscript. No research ideas or results were generated by the LLM. The authors wrote and verified all technical content.
B PROOF OF THEOREM 4.
Lemma B.1 (Matrix Inversion Lemma, Harville (1998). For any invertible matrix A E Raxd vector u, Rd, it holds that
(A + uv+ 1)- A- A uv A-1
1 v 11
Lemma B.2 (Elliptical Potential Lemma, Abbasi- Yadkori Yadkori et al. (211)). For any sequence of vec- tors {xx ) C R2, let Vo AI for some > 0 and V V XxX, for If xxll2 L for all i, then we have
A+ T
Σ min ||,,, |xx }} s 2d
dA
Lemma B.3, With probability at least -- 6, it holds for all t [7] that
dA to
1 0 0v, S B = 2/x+ 16 log(412/0) log
dd
Proof. The proof follows from the standard analysis of OFUL (Abbasi Yadkori et al. 2011 ) with weighted updates.
We have
10: 0 1 = (0: -0)) Vi(0,
( - 00)
Σ a.T Σ
0g a 0" -200) 200) Vi V V2-
Σ og a.Ta Σ
o.
a.aT
0-
200)
s=1
sm0
a, 10 Vi )V.'
Σ o5 a, 10
Σ
Pamlss
V.1 Σ Tg
Pa,
(B.1)
Jo.s
where the second equality follows from the definition of è, the third equality follows from the definition of тa and 7/. the inequality follows from Young's 's inequality. To further bound lo,s, introduce the following notation:
dp = 0,
d. = Σ 0 - a
aml
dA + so min dA
% == 64log(43//)) dog I 100 < S lo, S,,,
Decomposing lo,: into a martingale difference sequence, we have
1o. d d 20, 2 2m,a, V₂ d + J, 11
2 V
10 + m -
dr + or mp
Vi
(B.2)
1.,0
12.1
14

---

Published as a conference paper at ICLR 2026
From the matrix inversion lemma (Lemma B.1 D. we have
o 2 v a,a, V 1-1 d
1 = 0z m
V
1+ o a 1-
0 2 || 1|; v.- a Vi dc-1
a aiVi__ AeVi-1do-1 o 3
1 1 0, a 1==1
a, V d-1
0 2 11|
0 a
Based on our assumpition on the noise Th, I,. Ie is also a sub-Gaussian random variable with variance proxy bounded by
| 1l v
d v Ic. ar )2
o
(1 + 02
Adding 1 I, up to f and using Lemma
D.3 we have with probability at least 1 - 5/22
||a. 1|? |
1, I, I
(log(2/8)
II
(1+ *|a 1|? V, )2
5
(log(2/8)
Σ
min (1,1|11,11 ! 7t
dd + 10 -2
< 2%, log(2/6) 2d
d)
d) + to min
$ 7 8log(2/8) d dlg
(B.3)
d)
where the second inequality follows from the definition of I, and the fact that
12 1 1,
(I+o, Ila
the third inequality follows from Lemma B.2 and the last inequality follows from Young's inequal- ity.
Using union bound over all t 2 1, we have with probability at least - 8/2,
Σ h.s I, S nt + 880og(44 (t2 /5) dlog dA to to
dA
for all t 2 1.
For the second term 12, it follows from the matrix inversion lemma (Lemma B.I that
I2 0,
V, "naa
0,
V
a,a, a.a, T
V=l
a,
1 0, a. V a
0, 2 |a V
= =0, ni
||a |2
+ o₂
2
|
2
Vg
||a.|
11
o, ---''
+ 0,
|
12
15

---

Published as a conference paper at ICLR 2026
Using union bound over t 1, we have with probability at least - 5/2.
||a 1| V
1 S oi 1og(
1 5e a
for all t t 1. Thus, for any t 2 1,
||a|||
Σ
2 S Σ
logg 1/22/0 /6)
0,
1 00 2 a
8=1
s=1
< 1og(412/8)
min 1 - [
dA + to min
$ 2log 4t (4t²/)) dlog
(B.4)
dλ
where the last incquality follows from Lemma B.2
Substituting
B.3 and
B.4
into
B.2 and using induction on t, we have with probability at least
1 1- 6,
dA + to min
To S 74 := 64 log /8) log
dd
which further implies that
dd + to min
00 - 11; s 22 v. 2To, I 256 log((t22)))) /8) d
dd
Lemma B.4. If follow Algorithm
to choose the action a,, then it holds for any e [T] that
[ 2 m-
min 18kSt+1
((t) k +
[o 12 is the i-th smallest element in (o21 {07)==1>
Σizk
x E lo (2) 14-0) of.%1)]
where ((1) = -2d log d+Ergy o.2
Proof. When [0, 11. x S 2og + x), which further indicates that
Σ rE(T]
min (1, o?
1
|a 12 vー
< 2 log
1
1
||
|a
v=
TE(1]
< 2 log det(V>) (V>)
det Vo)
d Σrely o
< 2d
(B.5)
Let
+ -+Ej(0 o7
((t) 2d log
d
Note that for i < 6,
|ad < $1aoollz
5 ||ally
16

---

Published as a conference paper at ICLR 2026
due the fact that Vi-1 > Vi-1 and the definition of a, in Algorithm inequality (B.5), we obtain that
Therefore, following
Σ min(1 TE(O
1 oz |a
S
Σ min { 1, o?
1
ar (arly-- 1:ا2 S ((1).
(B.6)
rE((]
As LHS of (B.6) is strictly increasing with respect to |a ll ll as long as ((t) < t, we can derive a
bound for | lll by solving
Σ min
1, x² c(t).
(B.7)
To solve (B.7 define sorted sequence of (o,) in increasing order, denoted as
(1) S o, S ao
(2)
Let o, == 0. Suppose that æ E [o, (k-1) oi
(k) for some K E [t]. Then for < k, we have
1
min
x²
1;
lo p0
for 2 h, we have
x=a
min
(o
1
(ot
10
After rewriting the LHS of the above equality, have
2
(t))
11
We can then rearrange the above inequality to obtain
||a|ll? 1 5x²
where
x² = min
((t) 1:
+
0
1k-1)
(tt) k + 1
10
(8)
1skst+1
Eisk Jo
Σ
ii
This completes the proof.
Remark B.5. In the previous proof, x² is the solution for the implicit equation B.7 rewrite it as
We can also
e(t),
max ( x2)
which implies that
(t))
x²
E ii max .
We further have
(tt)
(t)
(t) +t
Σ o?)
2
t
of +-7
a
Rearranging the above inequality, obtain
((t) E 0?
0
o?
2² <
Ō
- ttt)
$2
when /. R(d).
17

---

Published as a conference paper at ICLR 2026
Theorem B.6 (Simple Regret of VAEE, restatement of Theorem 4.1). If set À 1 and Bg 2vA + 1 Lol//o///////// /5) dlogg dA
dA+fa in Algorithm then with probability at least 8, the
simple regret of Algorithm I is bounded as
SR(T) = Ö(va)
min 1skST+1
x
(T) k: + i
(0)2 oT
is the i-th smallest element in fo
x E ( (k-1) (K)) oT
where (() = 2dlog d+ d+ of
d
Proof. By Lemma B.3 with probability at least holds for all t E [T] that 0 E EC, == {0 Rd |10, O - B. In the following, we condition on the event that 0 E C. for all E [T).
With the conditioned event,
show by induction that for any [7] a" E Ar:
min (0,a). a*) 2 (0", a²) Z max (0",a) a DEC.-. OEC.-1
aEAt-1
where the first incquality follows from the fact that 0" Ct-1, the second inequality follows from the definition of a", and the last inequality follows from the definition of A,-1-
Let a* argmax a (0", a) be the optimal action. By the definition of simple regret, we have SR(T) (0"
aT)
< max max (0, a) - -10,,ay Ar OECT-1
< max (0T-1,a) a) + Br Brllablly,, (0T- ar) + Brllarllv aEAr
where the first inequality follows from the event that 0" E C, for all [T]. and the fact that a" E Ar, the second inequality follows from the definition of Cr-1 and the definition of ay in Algorithm
Then it suffices bound max.c.Ar (0T- (Ôr-1, ar). Since ar Ar, it is guaranteed that there exists 0/ E Cr-1 such that
(0),
max min (0, a) 2 0. aε AECr-1
which further implies that max (0, (0r-1,a) a) (01-1, aE
max (0, 1-- a) (0/ ar) + (0' 0r-1. ar)
A
max (0T a) (0',, ar) + Br 1| | Ilv AE
s 3 max ||a||
y ||||y= = 3 1 ||aT|lll
AEAr
where the last incquality holds because max (0T-1, a) - maXaEAΑ mingec, (0, a) < 28T maX ||aly, based on the definition of Cr-1 and the last equality follows from the action selection rule in Algorithm
Hence, the simple regret of Algorithm is bounded as SR(T) < 587 |ar lv,,
(T) 1: [o (0)2 is the i-th smallest element in (o21T
< x((d)) min ISkSI+1
Lizk
1012
E 10 1- (16)
where the last inequality follows from the choice of Br and the result in the previous lemma.
18

---

Published as a conference paper at ICLR 2026
C PROOF OF THEOREM 6.1
The proofs of our lower bound require the following Lemmas, which is standard technique used for lower bound.
Lemma C.1 (Le Cam two-point method (Le Cam 1986))
Let P and Q be probability measures on the same measurable space, and let Φ Q > {0, any (possibly randomized) test. Then
(pfo= = Qf -))
1 {(1 (1 - (I-
2
2
where &Tv(P,Q) = Supa ((A) Q(A)) is total variation distance. Moreover, by Pinsker's in- equality,
(Tv(P,Q) (L.(())))
Hence the average error of any test is bounded below by
{(
+ 2 (1- KL(P)IQ)).
Lemma C.2 (Pinsker's inequality (Pinsker 1964)). ) For any probability measures P, Q,
êTv(P, < KL((I)))
Lemma C.3 (Yao's minimax principle (Yao 1977)). Let IT be the set deterministic algorithms (measurable decision rules), family of instances with loss [(T, 9) and let D be distributions over P. Then
inf sup Eg [(T, 0) Z sup inf Ee Eo (TT 0)]-
#ell PcP
nED sell
In other words, the worst-case risk of the best deterministic algorithm is least the Bayes risk under any prior μ.
Now, we are ready prove our lower bound.
Proof of Theorem 6.7 Step 1 (per-coordinate two-point divergence). Let action set A {-1,1]d The unknown parameter belongs to
= (-ce +c] for some e > 0.
The optimal arm for 0 is a" (0) s0gn Since each coordinate mistake costs 2c, the simple regret
SR(T) = Eo (0, a (0)) - (0, ar) = 2c Eg (ign(ar,sgnn()))
where
Ham uu v) A
Σ j=1
Mug t
Let S S= Et= o,-² denote the total precision. Fix j E [d] and consider neighboring parameters that differ only coordinate j:
0 +c, 0(--)==-
0 = 0(. E {+c) ()..
Let p(i = P. oo... and ppú)) = Por.-) be the laws the full transcript under these two instances. By the chain rule for KL and the fact that a, TT. (H+-)) contributes to KI.
T
kL((P(2) pp2)
Σ E[KK. (.+) ,o0))
(3)) G-) [,,))], ,,
where ii ( = (0 at). The means differ only on coordinate j. so 1 (i+t) - -/
(1-) (+c
(-c))oous = 2 and thus
KL(N(uLLtt) (i+t) (::tt .of) (1( (n(
(2
2ca
20
20
o
19

---

Published as a conference paper at ICLR 2026
since of 1. Summing over t yields the instance divergence
KL(P("1P() 2c Σ =625.
26
Step 2 (I.e Cam Pinsker per-coordinate average error). Apply Lemma C.
with the test
[[3 +1] between p(i and p(), and bound the TV distance by Lemma
C.2
We get
2 {8, + +1} {s, z 2 (1 (1- V (L(P | (p!i) =
p
2 - ov5)
Choose c 5-/2
1/2 to obtain the uniform per-coordinate bound
1 マ (ol (3, +13 + plu # -13) Iv
001
for all j e [d].
Step 3 (aggregate to d coordinates under Hamming loss). This part requires the following lemma. The proof of this Lemma is defer to Appendix [..1
Lemma C.4 (From two-point bounds to d-dimensional Hamming -risk lower bound). Let θ {=c)" and put the uniform prior on O. Let Hy denote the full transcript and let & = 8 8(H)) E {+1] be any estimator of (0). For each coordinate j E [d], fix two instances 0 0 E that differ only in coordinate j (i.e., ofi,.) +c, 0f:-)
and g( of for all # j). Denote by p() and p(i) the corresponding laws of Hy under these two instances. Assume that for every J.
(6) +11 p * -1)) (1)) nh for some 1 10,
(C.1)
Then the Bayes Hamming risk under the uniform prior satisfies
Eg Eg [amm($, si)] ndd
(C.2)
and, consequently, by Yao's minimax principle,
inf sup Es signn 2 nd. oce
(C.3)
Invoke Lemma C.4 with 7)
to conclude that the Bayes Hamming risk under the uniform prior
on satisfies
Eg Eg [Hmm é, signi())))))))))))))))) (0)) > d.
By Lemma C.3
(ao''s principle), this also lower-bounds the minimax Hamming risk:
3
inf sup Eg [ign(() age
d.
8
Step 4 (convert Hamming loss to simple regret). In θ = t each coordinate mistake costs exactly 2c value. Therefore
3
3
3
inf sup Es O, 2 2c OE
8 cd
ds d 1/2
16
where we used 1/12
C.I PROOF OF LEMMA
Proof of Lemma C.4 By definition of Hamming distance,
Ham(s, sign ())
Σ 1 1 + sign(()))
20

---

Published as a conference paper at ICLR 2026
Taking expectation under the model instance 0 and then averaging the uniform prior on @ the Bayes Hamming risk equals
Eg Eg [amm(8 sign(0))
Σ
Bg Fot + sign(0,))
(C.4)
==1
Fix coordinate j E [d]. Write 0 0-), and condition on 0-j. Under the uniform prior on O, have P(0; + (- [P(0) -c c 0 [0 Hence, conditionally 0 O-j- the law of the transcript Hr is the equal mixture
M 2 p( + 1 P!
(C.5)
where pf and pl) are the endpoint laws that differ only in coordinate (with θ-j held fixed).
Identify the conditional Bayes error for coordinate j with the average two-point error. Consider the indicator loss for estimating sign(0,) by the (measurable) decision rule 8y(Hr) E {+1}. The conditional Bayes error probability for coordinate j. given 0 0- is
Err,(0-;)
E B
(0)
11 (3 HT)) + +1) (8) # -1} x-1]
Using C.5). this equals the average of the two endpoint errors:
Err, (er,(0_,))
p {8, + +1 + p (8,
(C.6)
By the assumption C. we have, for every 0 ー
Erry (0-) 2 1/-
(C.7)
Average 0- and sum over j. By the tower property (law of total expectation),
Pe & sign(0,)) Eo_, (0-;))
Combining with CC.7 yields
Eg Po * sign(0,)) 2 7
for every [d].
(C.8)
Summing (C.8 over j = 1,..., d and using
C.4) gives
Eg Eg (S sign
Eo (3, # sign(0,)) 2 nd,
which is
From Bayes to Minimax. By Yao's minimax principle (Lemma C.3 the Bayes risk under the uniform prior lower-bounds the minimax (worst-case) risk over θ of any deterministic policy:
inf sup E. [Ham (8, (ign 2 Eg Eg [Ham(& sign())) 2 nd,
dee
which is This completes the proof.
D PROOF OF THEOREM E.3
Lemma D.I. If we follow
Algorithm 2 to choose the action a1:7, and compute Ôr and Vr, then
holds that
T
xT
Vr 7
Σ
V(T).
o
a 00p
1=1
21

---

Published as a conference paper at ICLR 2026
Proof. Consider the action am A such that (((a)) and Σ rETr(() ož))(a) is minimized. Is straightforward that
VT Σ Σ
1 o7 (am)
T(a)aa
V(T).
(D.1)
of n (8m))
nEAA (aT)((am)
(TT((am))
Then it suffices to lower bound
(T a. (am)
We consider the arms in (opp(T)((mm)) For the round t(a) when the arm a pulled and ErET((a) [a) 2 EreTr(am.) ".-m(amm. it is guaranteed by the selection rule that a will not be pulled in the subsequent rounds. We denote by ((a) the last variance observed when pulling the arm Then we have
(a)
Σ TETr(a)
Σ
Ta(a)
Σ
07 ((a)
o7 π (amm)
[oa)) (Ta)
a {am)
aEsupp (am)
TETr(sm
[1 x (am)
o? π mamm))))))))
[o(a)]}
TETr(am)
(xr) Mam)
(upp(r))==
$ [1 ((m))
o (am)
(
TETr(Am.)
(D.2)
where the first inequality is due to the definition of (a) and the last inequality follows from the fact that {ar(a) ) (amm)) are the variance signals observed at distinct rounds.
Rearranging (.2),, we obtain that
[supp(rr]]11
(aa)
(D.3)
of Ta)
o IT (Tm))
[o
(Esupp(m)
(aT
TETs (n.)
A
Note that LHS of D.3) is exactly
Et=l of
which further indicates that
(spp(()) -1
Σ
of TT (Tmm)
2
|o
10
TET2 (am)
1=1
1=1
r
As result, we have
(supp(
VT
V(T)
D.I Lemma D.2. In Algorithm
following
for any arm E A, with probability at least 8, we have
( a)) S +
T
(upp( s)
< ||al||v())
'N (log(2
Σ
Proof. From the definition of Or and Vr, is straightforward to obtain the following inequality:
T
K0, - 0", 00, 1(V
o 2 ria:
Vr-i 0",a)l
T
= =I(v=
o
az?lt, a)
t=1
22

---

Published as a conference paper at ICLR 2026
T
Σ
o
ne
V7 a) (a,
(D.4)
t=1
Applying Lemma D.3 to D.4). we have that with probability at least 8,
T
(0
0
a>|
$
2
(a,,
t=1
T
2
0 a, V a|2 (og((22)
2 a LV 0, a a, Vr (2//)
v 2a Vi a loool//6))
where the last inequality is due to the fact that E og -. VT.
By Lemma D.I
we further have
K0T a)) S |lall,, v 2log(2/0)
1 supp(ar)
( 210g(2/8)/
Σ
from which the desired result follows by taking union bound over all A.
Lemma D.3 (Hoeffding's inequality). Let {-;} be stochastic process, {9ihe be a filtration so that for all i E [m]. x, is G-mmesurable, while [1 and 2z/9;-1 a, au-sub-Gaussian random variable. Then, for any & > 0, with probability at least 1 - 6, it holds that
of (1/8)
Theorem D.4 (Simple Regret of Algorithm restatement of Theorem 5.3 Suppose that AA C Rdd compact and span([A) = RR.d If we follow Algorithm then it holds that with probability least 1 1- 6,
4d log d+-16
(0" a0",a") - -0", s 2 dlog(lAA/8))/
1
Σ
o0
T
Proof. From the definition of ar+1, we have
a0) - (0", ar+1) (0, - 0", a141) + (0' Or,a²) + (0r, - -ar+1)
|rr 0" ar (0) 0- ,²,a))
T'
[supo())) [+)
(lar+1llv(=)=- + ||a (v()))))
+||+||aal0
(log(2)A1/6)/
2
[o (1)
log log d+16
s 2 dlog(2)Al/6)/
Σ
where the first inequality follows from the definition of 27 the second inequality is due to Lemma D.2 and the last inequality is due to Theorem 5.2
23

---

Published as a conference paper at ICLR 2026
Algorithm 3 Variance-Aware Exploration with Elimination (VAEE for heavy-tailed noise)
Require: ACR. 6. 1: Initialize Vo < AIg, O + 0, A1 + A.
2: for 1,..., T do
3: Pull the action a2 <- m ||e||v=-
4: The agent receives the reward rt and the variance ot.
5: Calculate Vi + Vi-1 + o, "a,a
6: Calculate
ri (a. 0)
0, - argmin
1012
fT.
| 101
1+0 *||a,1 1
where T; To
0, au v==
7: Set confidence set follows
C. t 1 10 delii-- S 3....
8: Eliminate low rewarding arms: Aet1 t {a E A. m mingee, (0,e) S maxsec, a)
9:
end for
E EXTENSION TO HEAVY-TAILED NOISE
In this section, we extend our results to the setting where the noise is heavy-tailed. Specifically, we consider the following assumption the noise.
Assumption E.1. For any round & (f 2 1), the noise 7)e satisfies that
E[m/ l1 1 = O,
E Eim a1: m---1] S o/.
This assumption is general than the sub- Gabssin assumption on the noise, which only requires the second moment of the noise to be bounded.
To handle the heavy-tailed noise, we consider the following adaptive pseudo-Huber regression esti- mator (Ruppert 2004 Sun 2021 Li & Sun 2024):
(x) := (VP+22
(E.1)
where 0 is robustification parameter. The pscudo-Hube loss behaves like the squared loss when [x] is small, and behaves like the absolute loss when |x| large, which is firstly applied by Li & Sun 2024) into the heteroscedastic linear bandit setting.
Lemma E.2 (Theorem 2.1, Li & Sun 2024). Let d log(1 + T/ If we set 2 max(v2k,,Vdl)) /oold)///ooo//////l// /2g /8), then with probability at least - 48, it holds for all t [T] that
2t 2t + To log 8 +5VA.
||0 llv - B = 32
log
8
Theorem E.3 (Simple Regret of Algorithm 3 Consider the linear bandit problem with heavy- tailed noise satisfying Assumption E. If we set To = O ((vd) and X = 1 Algorithm 3 then with probability least 1 48, holds that
SR(T) Ö(Vd)
mún 1skST41
(T) k
(k-1) (6) E (oT (o ,07
Σ i 10
where (T)) = 2d log the ascending order.
d4 d+E a
Recall that {o (1) 1T
is the sorted sequence of {ot]_= in
d
24

---

Published as a conference paper at ICLR 2026
Proof. The proof follows the same line the proof of Theorem 4.1 with the only difference being the confidence radius 3 By setting 70 (vvd), we have 3e ((vd). Following the same
analysis as in Theorem 4.1 we can obtain the desired result.
25


Reviews:
[{"review_id": "mZIfpB9JX9", "reviewer": "Reviewer_frPW", "summary": "This paper studied linear bandits with heteroscedastic noise, i.e. the variance of the noise can change from round to round.\n1. For both infinite-armed and finite-armed case, this paper proved a variance-aware regret bound, and provided an algorithm that achieved the bound.\n2. The paper showed that for the infinite-armed case, the regret bound was tight up to log factors.\n3. This paper provided a novel version of elliptical potential lemma for the heteroscedastic noise case in linear bandits.\n3. This paper provided some novel lower bound proof techniques for heteroscedastic linear bandits.", "questions": "1. Can the authors confirm if $\\tilde O$ also omits $\\log \\log |\\mathcal A |$ factors or not?\n2. Can we show a matching lower bound for the finite-aremd case, e.g., by following the lower bound proof in https://arxiv.org/pdf/1904.00242?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. This paper provides the first near-optimal regret bound for variance-aware linear bandits.\n2. This paper provides new insight that the confidence ellipsoid in heteroscedastic linear bandits should scale with the harmonic mean of the noise variances.", "weaknesses": "1. The author didn't show a matching lower bound for the finite-armed case.\n2. For the upper bound, the main technical contribution of this paper seems to be limited to page 16, where the authors extended the ellipsoid potential lemma to the weighted case.\n3. For the lower bound, the construction of the adversarial instances seemed also to be classical.", "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": "RW5ojujrBX", "reviewer": "Reviewer_KTha", "summary": "This paper studies the problem of heteroscedastic stochastic linear bandits, i.e. where the variance proxy of the subgaussian noise at each round is time-variant (but known). Prior work on this problem has given regret upper and lower bounds that scale with the arithmetic mean of the variance proxies. This work instead designs algorithms with regret that depends on the harmonic mean of the variance proxies. They give a lower bound with the same rate (ignoring log factors). They give an algorithm with $d$ dimension dependence for possibly-infinite action sets, and $\\sqrt{d \\log(|\\mathcal{A}|)}$ dependence for finite action sets. Their algorithms are phased elimination-based.", "questions": "1. Could you provide a more concrete description of the argument in Remark 4.3 as to why there is there the additional term in the regret bound? (Ideally, this would be in the form of a lower bound, but I understand that that it might be too much to ask at this point.)\n2. In Table 2, the comparisons are under the assumption that the $\\sum_{t=1}^T 1/\\sigma^2 \\gg \\sum_{i=1}^{\\tilde{O}(d)} 1/[\\sigma^(i)]^2$ as discussed in Section 4.2. Does this hold for all of the scenarios considered in Table 2? At a glance, it seemed to, but I think its important to verify.\n3. In line 369, the paper says \"Therefore, our regret bound is always sharper\". However, it seems that this is only under the assumption mentioned above. As such, I would suggest modifying the wording to acknowledge this.\n4. I found Section 4.1 somewhat hard to follow. Some suggestions to improve this are to explicitly state what the action set is in the example, and to be explicit about what the simplifying assumptions are, e.g. what exactly does \"$UCB \\approx$\" mean?\n5. In lines 469-471, it seems that when discussing the lower bounds in Table 1, the authors are referring to the lower bounds in prior work (and not their lower bound). However, it is not said so explicitly, making it somewhat confusing.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. To my knowledge, the paper fills an important gap in the literature in studying algorithms with regret that depends on the harmonic mean of the variance proxies (rather than just arithmetic mean). This then motivates a novel algorithm design to address this new setting.\n2. I found the paper to be very thorough in its results and the discussion about these results. These discussion made it very clear how their results relate to prior work. For example, it includes the following along with its main results:\n   - Motivation for the use of simple regret (Remark 3.4)\n   - Justification for use of elimination algorithms rather than optimistic algorithms (Section 4.1)\n   - Comparison with prior work in specific instances (Table 2)\n\nTo comment on each of the dimensions:\n- originality: new idea of studying harmonic mean, and new algorithm\n- significance: filling clear gap in the literature\n- quality: thorough results (although I didn't check all of the proofs)\n- clarity: clear presentation overall (other than points discussed in Questions box)", "weaknesses": "1. A weakness is that the regret bounds have an added dependence on the dimension, meaning that the bound is slightly weaker than the exact harmonic mean (at least when $d$ is similar in scale to $T$ ). The justification for this (Remark 4.3) was somewhat unclear to me. See Questions (1).\n2. A possible weakness is that the results do not extend to the contextual setting, although they provided strong justification (in my opinion) for studying the non-contextual setting. In particular, their comments suggest (in Remark 3.1) that the arithmetic mean-dependence is tight for the contextual setting, while the harmonic mean-dependence is tight for the non-contextual setting.", "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": "2t9oFL05cL", "reviewer": "Reviewer_btFg", "summary": "The paper studies linear bandits with heteroscedastic noise under a fixed action set, aiming to improve simple regret beyond the classical dependence on the cumulative noise variance $\\Lambda$ (“total variance”). It proposes two variance-adaptive algorithms:\n\n* VAEE (Variance-Aware Exploration with Elimination) for large/continuous action sets, which selects actions by maximizing information gain while progressively eliminating arms.\n* VAGD (Variance-Adaptive G-Optimal Design) for finite action sets, combining approximate G-optimal design with variance-adaptive sampling.\n\nBoth algorithms yield harmonic-mean–type simple-regret bounds of the form \n*  $\\tilde{O}\\left(d \\Big[\\sum_t 1/\\sigma_t^2 - \\sum_{i=1}^{\\tilde O(d)} 1/\\sigma_{(i)}^2\\Big]^{-1/2}\\right)$  for VAEE and \n\n* $\\tilde{O}\\left(\\sqrt{d\\log |{\\mathcal A}|}  \\Big[\\sum_t 1/\\sigma_t^2 - \\sum_{i=1}^{\\tilde O(d)} 1/\\sigma_{(i)}^2\\Big]^{-1/2}\\right)$ for VAGD,\n \nwhich the authors position as breaking the classic $\\sqrt{\\Lambda}$ barrier in simple regret. A matching instance-dependent lower bound (Theorem 6.1) shows a $\\Omega \\big(d (\\sum_t 1/\\sigma_t^2)^{-1/2}\\big)$ dependence.", "questions": "1. **Isolation of the Key Driver**\n\n   For VAEE, what component is primarily responsible for achieving the harmonic-mean regret rate — (i) the elimination step (Algorithm 1, Line 8), (ii) the variance-weighted estimator and confidence sets, or (iii) the fixed-action structure noted in Remark 3.1?\n   A brief ablation-style analysis or a theoretical “swap-in/swap-out” comparison would help clarify the main driver of improvement.\n\n2. **Complexity–Regret Trade-offs**\n\n   What are the computational complexities of VAEE (both per round and overall, including elimination checks) and VAGD (computing or approximating the design with $|\\mathrm{supp}(\\pi)| \\le 4d\\log\\log d + 16$)?\n   Some discussion on the scalability or possible computational bottlenecks would strengthen the practical perspective.\n\n3. **Unknown or Misspecified $\\sigma_t$**\n\n   Assumption 3.2 assumes conditionally $\\sigma_t$-sub-Gaussian noise with known bounds $(\\sigma_{\\min}, \\sigma_{\\max})$.\n   How robust are the results if $\\sigma_t$ is unknown or mis-specified? Additionally, can the heavy-tailed extension mentioned in the remarks achieve the same harmonic-mean dependence? A short discussion in the main text would help.\n\n4. **Non-Spanning Action Sets**\n\n   Theorem 5.2 assumes that $\\mathcal{A}$ spans $\\mathbb{R}^d$. What if this condition does not hold? Could the authors formalize the subspace reduction and restate Theorem 5.3 with $d'$ denoting the rank of $\\mathcal{A}$? In other words, if $\\mathcal{A}$ lies within a lower-dimensional linear subspace of dimension $d'$, can the existing bounds be adapted by replacing $d$ with $d'$?\n   Clarifying this case would enhance the completeness and generality of the theoretical results.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. **Clear statement of contributions and rates (with concrete formulas)**. \nThe abstract precisely states the harmonic-mean–dependent rates (including the subtracting of the  $\\tilde O(d)$ smallest variances) for both VAEE and VAGD, and emphasizes that this breaks the $\\sqrt{\\Lambda}$ barrier in simple regret.\n\n2. **Well-motivated setting and assumptions.** \nThe fixed action set requirement is explicitly justified: when contexts change adversarially, $\\sqrt{\\Lambda}$ remains unavoidable.\n\n3. **Accessible algorithmic presentation.** Algorithm 1 (VAEE) and Algorithm 2 (VAGD) are spelled out line-by-line, including the elimination step for VAEE (Line 8) and the variance-weighted design logic for VAGD (Lines 1–8 and estimator definition).\n\n4. **Thoughtful comparisons and intuition.** The case study in Section 4.1 contrasts VAEE with Weighted OFUL under a low-variance window and shows how VAEE reallocates exploration to weak coordinates; the discussion quantifies the differing simple-regret decay. Table 2 further compares simple and cumulative regrets across noise profiles.\n\n5. **Lower bound with standard, transparent techniques.** Theorem 6.1’s proof uses Le Cam’s method and Pinsker’s inequality, clearly documented in Appendix C. This makes the paper more complete.", "weaknesses": "1. **Lack of clear separation between settings.**\n   The paper studies both infinite and fixed action sets, but Table 1 does not indicate which results correspond to each case. A new column or clearer labeling would make the distinction explicit.\n\n2. **Unsubstantiated claim of “breaking the $\\sqrt{\\Lambda}$ barrier.”**\n   The main text claims improvement over the $\\sqrt{\\Lambda}$ bound but does not point to the derivation showing this. Equation (4.2) and Appendix B contain the critical argument and should be cited when stating the main contributions.\n\n3. **Unclear source of improvement in Algorithms 1–2.**\n   It remains ambiguous whether the tighter regret stems from (a) the elimination step, (b) a sharper analysis, or (c) the fixed-action assumption. A short discussion quantifying computational or analytical contributions would improve transparency.\n\n4. **Missing or delayed notation definitions.**\n   Several symbols appear before definition. For example, \n     - the global window $W$ (in line **278**), \n     - the terms $\\mathrm{UCB}_x(t)$, $\\mathrm{UCB}_0(t)$, $\\mathrm{UCB}_1(t)$ (in lines **284–286**), and \n     - $\\mathcal{P}(\\mathcal{A}*{\\ell})$ (in line 400). \n\n   Early or inline definitions would improve readability.\n\n5. **Lack of Empirical Illustration**\n\n    Despite the clear theoretical development and the well-specified variance settings in Table 2 (e.g., fast-decay, spiky variance profiles), the paper provides no empirical or synthetic validation.\n    Since the variance is explicitly given, a simple simulation would be straightforward and would help demonstrate the practical relevance of the proposed regret bounds and constants.\n    The absence of such experiments weakens the overall empirical support for the claimed improvements.", "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)