Variance-aware decision making with linear function approximation under heavy-tailed rewards
Authors: Xiang Li
Qiang Sun
Venue: Accepted by TMLR ()

Abstract: This paper studies how to achieve variance-aware regrets for online decision-making in the presence of heavy-tailed rewards with only finite variances.  For linear stochastic bandits, we address the issue of heavy-tailed rewards by modifying the adaptive Huber regression and proposing AdaOFUL. AdaOFUL achieves a state-of-the-art regret bound of $\widetilde{\mathcal{O}}\big(d\big(\sum_{t=1}^T \nu_{t}^2\big)^{1/2}+d\big)$ as if the rewards were uniformly bounded, where $\nu_{t}^2$ is the conditional variance of the reward at round $t$, $d$ is the feature dimension, {and $T$ is number of online rounds}. Building upon AdaOFUL, we propose VARA for linear MDPs, which achieves a variance-aware regret bound of $\widetilde{\mathcal{O}}(d\sqrt{H\mathcal{G}^*K})$. Here, $H$ is the length of episodes, $K$ is the number of episodes, and $\mathcal{G}^*$ is a smaller instance-dependent quantity that can be bounded by other instance-dependent quantities when additional structural conditions on the MDP are satisfied. Overall, our modified adaptive Huber regression algorithm may serve as a useful building block in the design of algorithms for online problems with heavy-tailed rewards.

Published in Transactions on Machine Learning Research (April/2024)
Variance-aware decision making with linear function approxi- mation under heavy-tailed rewards
Xiang Li School of Mathematioal Sciences Peking University
1=10077@pkueddu.co
Qiang Sun
giang.eun@uutrronto.co
Department of Statistionl Sciences University of Toronto
Reviewed on OpenReview: https: // openreview. net/ forum? dd
Abstract
This paper studies how to achieve varianco-aware regrets for online decision- decision-making in the presence of heavy-tailed rewards with only finite variances. For linear stochastic ban- dits, we address the issue of heavy-tailed rewards by modifying the adaptive Huber re- gression and proposing AdaOFUL. AdaOFUL achieves a state-of-the-ar regret bound of v2) 1/2 +d) if the rewards were uniformly bounded, where oi is the conditional variance of the reward at round 1, d is the feature dimension, and T is nunber of online rounds. Building upon AdaOFUL, we propose VARA for linear MDPs, which achieves variance-aware regret bound O(d/HG**) Here, H is the length of episodes, K is the number of episodes, and G* a smaller instanceedeeenddnt quantity that can be bounded by other dependent quantities when additional structural conditions on the MDP are satisfied. Overall, our modified adaptive Huber regression algorithm may serve as useful building block in the design of algorithms for online problems with heavy-tailed rewards.
1 Introduction
In many real-world scenarios, data exhibit heavy-tailed behaviors, which deviate significantly from classical assumptions statistical analyses. Examples include stock returns in financial markets (Cont, 2001; Hull, 2012), microarray data analysis (Posekany al., 2011), and advertiscr values in online advertising (Arnosti al., 2016). Such heavy-tailed distributions pose challenges to conventional algorithmic designs that often hinge upon uniformly bounded sub- Sab-Gaussian reward assumptions.
Many works studying decision-making under uncertainty focus on the multi-arm bandit problem and its extension, the linear bandits. Regret analysis this domain seeks to understand the suboptimality of algorithmic choices. However, traditional analyses often limit their applicability by assuming uniformly bounded or sub-Gar mub-Gaussian rewards. Some recent approaches address heavy-tailed behaviors by truncating rewards to achieve sub-linear worst-case regret bounds (Bubeck et al., 2013; Medina & Yang, 2016; Shao et al., 2018; Xue et al., 2021). Nevertheless, these truncation-based methods encounter estimation errors dependent. absolute moments of observations, not their central moments, suggesting suboptimality, especially in noiseless situations.
While linear bandits offer a general enough setting for understanding decision-making with heavy-tailed data, reinforcement learning (RL) elevates this understanding to long-horizon decision-making processes. RL, agents not only make decisions but also navigate through potentially infinite state and action spaces
hides constant factors and logarithmic dependence

---

Published in Transactions on Machine Learning Research (April/202)
over given horizon (Sutton & Barto, 2018). RL demonstrates remarkable empirical successes in various applications, including robotics (Tillicrap et al., 2015), dialogue systems (Li et al., 2016), and Go play (Silver et al., 2016). Recent theoretical advances have expanded RL's applicability, especially with linear function approximation in the context of lincar Markov decision processes (MDPs) (Yang & Wang, 2020; Jin et al., 2020b;a; Wagenmaker et al., 2022b; Zanelte et al., 2020; Ayoub et al., 2020; Zhou et al., 2021). More recently, the shift from worst-case regret analysis to varianco-aware regret analysis in RI. offers more nuanced insights into agent performance (Pananjady & Wainwright, 2020; Khamaru al., 2021; Li et al., 2023; Yin & Wang, 2021; Min et al., 2021). More specifically, variance-aware regrets depend on the variances of rewards and value functions and provide finer guarantees than worst-case bounds by characterizing problen-dependent performances across different problem instances. Yet, the challenge posed by heavy-tailed rewards remains.
This paper explores the intersection of decision-making under heavy-tailed rewards, ranging from linear bandits to RL applications. We use the term heasy-tailed rewards throughout the paper to refer to the rewards that have only finite variances. We aim to achieve the artancc-awwaeness and address the heavy-tailed issuc simultaneously. A desirable algorithm should have the following two properties. First, it should possess the flexibility to function as module, enhancing algorithms originally designed for bounded rewards to accommodate heavy-tailed rewards. Second, it should attain tight varianco-aware regret bounds based on central moments, rather than absolute moments.
1.1 Our contributions
We provide a particular algorithm satislying the mentioned characteristies. Our solution is motivated by adaptive Huber regression (Sun et al., 2020; Sun, 2021), which was originally proposed for analyzing offline independently and identically distributed (i.i.d.) data. It uses the (pseudo-) Huber loss to estimate the unknown coefficient with a universal robustification parameter. We adapt this method for online bandits and carefully choose different robustification parameters to handle non-i.id. data. The resulting algorithm, called AdaOFUL, UL, short for Adaptive Huber regression based OFUL, achieves the state-of-the-ar regret bound + d) for linear bandits with heavy-tailed rewards, where vs is the observed conditional
variance of the random reward at step and d is the feature dimension. Here Ö(-) hides constant factors and logarithmic dependence on T. T.Such a variance-aware regret bound has only been obtained in the literature of lincar bandits with sub-Gaussian or uniformly bounded rewards (Kirschner & Krause, 2018; Zhou & Gu, 2022). In contrast, truncation-based methods are suboptimal due to their estimation errors that depend on absolute moments instead of central moments, For example, the truncation-base et al., 2018; Xue et al., 2021) yield regret in the form of δ (odv'T) where 22 is the bound for the second moment of random rewards. Our regret bound depends on the central moment instead and is thus tighter.
algorithms from (Shao
Using AdaOFUL as a building block, we then propose the Variance- Aware Regret via the Adatptive Huber regression (VARA) algorithm for lincar MDPs with heavy-tailed rewards. In essence, VARA integrates AdaOFUL with the stale-of-the-ar worst-case algorithm LSVI-UCB++ from (He et al., 2022), enhancing regret performance through more careful analysis and resulting in a regret bound of O(dVHG*)) K). Here is the horizon length and g* is a variance-aware quantity bounded by the sum of weighted per-step conditional variances. Our regret bound is superior to the current state-of-the-art bounds in three ways. First, it depends on a tighter instance-dependent quantity G* without knowing the value of G* in advance and has optimal dependence on d and H. Second, assuming additional structural conditions on the underlying MDP, we can obtain further instance-dependent bounds of G*. including denendee,n,,nt,, first-order, and concontrabillty-deeedde bounds. Third, our regret bound O(d/HG* K)**)) is valid even when rewards have only finite variances, which achieves a level of generality that is unmatched by previous works.
Our findings indicate that heavy-tailed rewards do not pose a limitation for developing online decision decision-making with lincar function approximations. Our proposed modified adaptive Huber regression algorithm can be used as a general approach to adapt existing online algorithms designed for taght rewards to handle heavy-tailed ones while maintaining tight dependence on variance for regret bounds.
2

---

The pseudo- Huber loss (Hastie et al., 2009; Sun, 2021) is defined as Published in Transactions on Machine Learning Research (April/202)
Overview The rest of the paper proceeds follows. We state our main results for heavy-tailed linear bandits in Section 2 and for linear MDPs in Section 3. We review related work in Section 4 and conclude in Section 5. Most proofs are collected in the appendix.
Notation We use || to denote the f2-norm in RS, and (B)l the f2-norm ball in F with radius B O. For a positive definite matrix H Rdxd | Væ HE for vector æ Rd. For two semidefinite positive matrices H1. H2, we denote H1 2 H2 if H₂ - H1 is semidefinite positive. For an integer K E N let [K] := {1,2. ... K. For a set A, |A| denotes its cardinality. For real numbers a & 6 and z E R, we use P[a.M] == max(a, min(x, b}} to denote the projection x onto the closed interval [a, b].
2 Variance-awars Regret for Heavy-tailed Linear Bandits
In this section, we first introduce the heavy-tailed linear bandit and then present the AdaOFUL algorithm, showing it achieves state-of-the-art variance-aware regret even when faced with heavy-tailed rewards.
2.1 Heavy-tailed Stochastic Linear Bandit
Definition 2.1 (Heavy-tailed stochastic linear bandit). Let (Di)es denote fixed sequence of decision sets and (Fe)s1 a filtration. At round t, the agent chooses Φ; Dr and then observes the reward yı and its conditional variance vg. We assume = (t.,, 0*) + where 0* E TR is vector unknown to the agent and Et E R is a martingale difference random noise such that [[ = 0 and B[s = 1/. Both it and Φe are Fea--measurable and || x L. We assume ||@||| || < minimize the regret, formally defined as
with B known a priori. The agent aims to
RT) = Σ sup (Φ, (0, -
- ($,, 0*)
(2.1)
DED.
In heavy-tailed stochastic linear bandits, the mean-zero random noises e, have only bounded variances. We emphasize that in linear bandits, data are collected adaptively, and therefore, the distribution of e, depends 6e. Moreover, the choice of db depends all past observations (Øs, yo. Ve)
2.2 Algorithm Description
This section presents the AdaOFUL algorithm for heavy-tailed linear bandits. The AdaOFUT, algorithm is given in Algorithm 1. AdaOFUL follows the principle of Qptimism the Face of Uncertainty (OFU) (Abbasi- Yadkori al., 2011) to solve the heavy-tailed heterogeneous linear bandit problem. At each round it maintains a confidence set defined in equation 2.2 such that 0* C, uniformly for all t > 1 with high probability when the exploration radius 8-1 is properly chosen. Unlike the standard OFUT, algorithm (Abbasi-Yadkori Yadkori et al., 2011) which directly selects the most optimistic estimator O, to make an arm selection 6,, AdaOFUL uses adaptive Huber regression to compute new estimator 0, that takes into account the heavy-tailed rewards. The agent then selects the arm Φ: that maximizes the inner product (Φ, O) over 0 C- After playing the selected arm, the agent observes the reward and its conditional variance i;- The last step of round t updates the exploration radius 8, and the shape matrix H, for the confidence set construction.
Adaptive Sreudo-Huber regression
(x()) = T2===((2+++
(2.5)
which is a smooth approximation to the well-known Huber loss (Huber, 1964). Similar to the Huber loss, the Hoeudo-Huber loss resembles quadratic function for small values |æ| and approximately lincar when æ is large in magnitude, making the loss strongly convex when close the origin and less sensitive to changes in the tails. The parameter controls the balance between the quadratic and linear regions and is referred
3

---

Published in Transactions on Machine Learning Research (April/2024)
Algorithm Adaptive Huber regression based OFUL (AdaOFUL) Initialization: Ho AI, 0, 30 VAB,co=
C1
42-log 27
min
VT
for t= to T do 2
Construct the confidence set C--1 as in
C--1: (0 Balla(B): ||0- 10-00 -0-1 & B(c-1
(2.2)
Solve (Ø)..)
DEC ().
Play Φ and observe (yr, 4)) Set oz, wy and T₁ according to the following equation and record (o., w T,
< &tt
LB Φ
Φ:
+ w/
Ot max Vt, min,
=
(2.3)
ci d'
H
Wt.
Compute 0e by minimizing the following convex problem
i
ys ($. (p..0) 9
0, = argmin (,) with L,(0) 1012 (=
Σ
lr
(2.4)
de o.
Define the confidence set radius Bg as in equation 2.6 and set H.
H +
end
to the robustification parameter by Sun et al. (2020) in the case of the Huber loss. Since the value of the robustification parameter needs to be adaptive to the data for an optimal tradeoff between robustness and unbiasedness, we shall also refer to the pseudo-Huber regression with a data-adaptive as adaptive pseudo-Huber regression or simply adaptive Huber regression, in line with Sun et al. (2020).
To compute the pscudo-Huber estimator 0, for 0*, given the history {(0., Ms, [s]] up to time t, we solve the the convex optimization problem in equation 2.4 (Sun, 2021). Recall that o,'s 's are surrogate conditional variances, and T''s are the robustification parameters, given by equation 2.3, in which miin is small positive constant to avoid singularity, To is hyper-parameter, wy's are importance measures, Co and e₁ are specified in Algorithm 1, and L and B are constants defined in Definition 2.1.
Robustification parameter As shown in equation 2.3, the robustification parameter тr is set differently for each data point (Øt, vi) in the -uber regression. This is significant departure from the case of i.i.d. data, where all robustification parameters are typically set to the same value as i.i.d. data are naturally weighted equally (Sun et al., 2020). In linear bandits, the data are generated adaptively, where the choice of Φ, can depend on all past obscrvations. Since observations collected later rounds are less important as they are based on previous observations and contribute less to the estimation accuracy, we assign greater weight to earlier observations. To measure the importance of the 1-th observation, we use w; = -|0:1l,,,,/0 /o, as the importance measure for the t-th observation and set T Tov1 w/ of/w,, as the corresponding robustification parameter.
When laking To 00, the optimization problem in equation 2.4 reduces to weighted regularized least-squares, which has been proven to achieve worst-case optimality for linear bandits with uniformly bounded or sub- Gaussian rewards (Kirschner & Krause, 2018; Zhou Gu, 2022). However, an appropriate value of To is necessary balance robustness against heavy-tailed rewards and asymptotic unbiasedness. In Corollary 2.1, will demonstrate that setting To Ö(vd) is sufficient. to achieve the state-of-the-art regret bound.
4

---

Published in Transactions on Machine Learning Research (April/202)
Variance estimates We choose o, e VLBB :/(efdi), which implies ejd > w/B / This condition is used to lower bound the Hessian matrix LT)(..). For any de Balla(B); we expect L2 HT up to universal constant factors to proceed with theoretical analysis. A direct computation yields (²L = Hy, while for the other direction we show (T(( 2 (c- (c-supre[T) i 0 ()((T)))) HT for some universal constant 0 with high probability. With the last condition on de, for any feasible solution 0 Balla(B), the following quantity
(Ør, 0 0
| 0 0 o2
L2 प8
4c
700
+
can be sufficiently small provided that of d for a sufficiently large constant C>>
2.3 Regret Analysis
We first validate that the optimism holds with high probability in Theorem 2.1 and then establish a high probability bound for the regret in Theorem 2.2.
Theorem 2.1. Let k = d- log
(d))))))) For the heavy-tailed linear bandit in Definition 2.1, if /27)))) > max(v 2x, 2v ALB), then with probability at least 1 46, it holds that, for all 0 < / T,
0H & Be,
where
B. = 32
K To
212 log
5 + to log
212 8
+ 5vAB.
(2.6)
Theorem 2.1 establishes that 0* is contained in the set C. = (0 Balla(B): 10- 0, H. & B. for all > 0 with high probability. It is proved by using Bernstein-type concentration incquality for self-normalized vector-valued martingales with additional care paid to deal with heavy-tailed rewards. See the next subsection for proof sketch.
Theorem 2.2. Let mnin = 1/VT. Then with probability at least 1 - 45, we have
T
2L. V
2LBB
Reg(T) x 2,3
V2R
1 +
1+
Ved
where Br is defined equation 2.6, and co, c1 Õ(1) are positive constants given in Algorithm 1.
Theorem 2.2 provides regret bound in general form that depends on Br. As shown in equation 2.6, 3, is a hyperbolic function of the robustification parameter To- Increasing decreases the bias term O (m/ To) while increasing the range term O (Tu log(2??/6)). Therefore, choosing To carefully is essential to achiove the optimal trade-off between unbiasedness and robustness. Setting T Ö(Vi) minimizes the right-hand side of equation 2.6. This, combined with Theorem 2.2, yields the simplified regret bound equation 2.7 in the following corollary.
Corollary 2.1. Let To max (V2n, 2v V (og(222/5) and 64 (2 (2gg((()))))) v /llog(21)/0) + 5vd. Consequently, the regret bound in Theorem 2.2 becomes
d/B², then 3r
RTg(T)= = δ (4
ve + d max Σ [E[T]
(2.7)
(1
where Ö(.) hides constant factors and logarithmic dependence on T.
5

---

Published in Transactions on Machine Learning Research (April/202))
Corollary 2.1 demonstrates that AdaOFUL achieves state-of-the-art regret bound under heavy-tailed rewards, comparable to the case where rewards are uniformly bounded sub-Gaussian The regret upper bound in the noiseless case reduces to (dd), and in the noisy case, reduces to O /Eegry vî). In the worst case
scenario where 24 (1) for all > 1, the regret bound reduces to ((dvT), which matches the worst-case minimax lower bound (Dani et al., 2008). Hence, our varianco-awarr regret bound equation 2.7 is tighter than the pessimistic worst-case bound (dy'T) when E o1 T. To the best of our knowledge, such a variance-aware regret bound has only been obtained in the literature for sub-Gaussian rewards (Kirschner & Krause, 2018) uniformly bounded rewards (Zhou & Gu, 2022). We are the first to provide a variance-aware regret bound for heavy-tailed stochastic linear bandits.
2.4 Proof Sketch of Theorem 2.1
Step one: Hessian approximation Let 20) == x0(0..0) and dloog (1 de
TL² dio
for simplicity,
Lemma 2.1. Assume there exists a constant b 0 such that (0)) < 1² for all 1 1. If
Toy log 27 8 > max(v/2b,, 2vd), then with probability at least - 26, for all > 0 and any |0| & B,
HT S L2 = Hr.
4
Lemma 2.1 shows that with high probability and up to constant factors, LL approximates Hr well uniformly for all > and ||O| & B. By contrast, in standard ridge regressions, V (T)) equals to Hr because the corresponding loss Lr quadratic. The proof is deferred Section C.2.
Step two: High probability gradient bound In the following, we provide high-probability bound for IVL, (0*) H in Lemma 2.2.
Lemma 2.2. Assume there exists constant b > 0 such that B1="(0*)]F=-i) & 6² for all t > 1. With probability at least 1 - 26, for all T > 1, it follows that
kb²
272
27
(0 HT
&
kb2 log
+ To log
VBB
To bias term
8
variance term
range term
ridge term
We explain briefly about each term in Lemma 2.2. Following Zhou et al. (2021), a decomposition follows that [[)]( H. ET,((,, + Yi) for two sequences of random variables X,, Yr F. To illustrate the proof idea, we explain how to bound Σ Xx, since Σ Y can be bounded similarly. For the adaptive Huber regression, (Xthee(r) is not a martingale difference sequence but (X, E[X,([F-- is. We apply Bernstein inequality to upper bound (X, E[X(( which contributes to the variance and range terms. Thanks to the different robustification parameters Tr, we can control > [[- deterministically within O (x) resulting in the bias term. Finally, the last ridge term VXB exists because use ridge regularization to ensure that the Hessian is always invertible. The detailed proof is in Appendix C.3.
Step three: Combination through stationary condition
Notice that the gradient given by
T
T()x
Φ: 2, (0) az
V 20
and our estimator Or is the minimizer of a constrained problem in equation 2.4. By Proposition 1.3 in (Bubeck et al., 2015), the first-order stationary condition of the constrained convex optimization equation 2.4 implics that (frr) Or A) & 0 for all 0 E Balla(B). More specifically, due to ||0*| & B, we have
(vrr((r)) Or 0+) O.
(2.8)

---

Published in Transactions on Machine Learning Research April/2024)
AJJRRL GFLL TOFU
000
125
Expecea mgr
Dipectad oegget
125
000
40-
21-
AESOFIL DFUL
AdJOTUL OPLL TOFU
30-
AASOFLL OPUL
1.8
TOPU
3.-
14.
8 16-
2.--
Dieaace to.""
1.2
2.-
100
0.5
1.0
0.1
115
Figure 1: Regret and convergence results across three noise types: Case (a) 6, ~0 1) on the left, Case (b) Et t(df) with df ~ ((2,3) 3) in the middle, and Case (c) E t(df) with df ((1, on the right.
By the mean value theorem for vector-valued functions, we have
(Lr( - (L+ (11 + 1)0r)dn (0r 0*).
J0
Using Lemma 2.1 and the fact that [1(1 -11-11 1 0[0r]
B for all 1f E [0. 1J, we have
Hr & (0r - 0r, VLT(Or) - VLT(O")). 1 0r -0 1
(2.9)
By equation 2.9 and equation 2.8, we have
0r, Pr-00 & 4 (L*( HT
(2.10)
Combining equation 2.10, Lemma 2.1 and Lemma 2.2, we know that if Toy log 27 max /xb, 2vd), with probability at least 1 - 25, we have that ||0: 1* 3r for all 1 & < T where 3r is given in equation 2.6. It implies that 0* indeed locals in all constructed confidence regimes, i.e., for all 1 & 1 < T, 0* E C.. Notice our case completes the proof.
that by the choice of Bn and Ho, we still have 0* E C.. Finally,
2.5 A Numerical Study
Considered methods In this subsection, we conduct a numerical comparison between AdaOFUL and two bascline algorithms: original OFUL -Abbasi-Yadkori et al., 2011) and TOFU (Shao et al., 2018). TOFU is a truncation-based variant of OFUL, designed address the heavy-tail issue. Because these algorithms do not consider the variance information, for fair comparison, we abstain from the variance weights and set each o, = 1. Hyperparamoters were chosen based on observations from the initial couple of steps so that To vd and co c 1.
Experiment setup We experiment with the following configuration. We set d = 10 and [D,] = 20. The optimal 0 is generated by randomly sampling each coordinate from a uniform distribution (1(0 1) and normalizing the resultant vector to unit length so that B 1. To simulate varying action sets, we generate 20 distinct basic action sets, (A and assign D, A, if mod 20. For cach A,, cach arm vector Φ E A, formed in the same way 0* so that == 1. Rewards are generated by Ye = 0",,00) + E, with E being independent zero-mean noise. We investigate three noise types: Case (a) is Gaussian distribution
7

---

Published in Transactions on Machine Learning Research (April/202)
Ee ~V(, 1), while Cases (b) and (c) correspond to Student t-distributions E, t(df) with df, the degree of freedom, varying. Note that if a random variable X follows Student's i-distribution with a degree of freedom df, its mean is well defined for df > 1, its variance exists for df > 2, and its variance becomes infinite for 2 > df > 1. Case (b) sets df ~ ((2,3), 3), while Case (c) uses df ~ ((1 As we move from Case (a) to Case (c), the noise becomes increasingly heavy-tailed. To ensure a fair comparison, most parameters are shared, o.g., & and X = 1. The experiment runs for T 1000 steps and is replicated 10 times, with the outcomes averaged. The shadowed area depicts the area within one standard deviation, calculated over ten repetitions.
Experiment results Figure 1 shows the regret and convergence results across three noise cases. It clear that for all considered algorithms, the regrets continue to grow and the Ta convergence errors -0c- - tend to diminish. The continuous growth in regrets is also observed in previous heavy-tailed experiments (Shao et al., 2018). A key message is that AdaOFUL consistently achieves the lowest. regret, smallest convergence errors, and least variability. In the context of light-tailed noise (in the left column), OFUL has a slightly smaller regret than TOFU. The result. implics that the truncation technique might hurt the performance under light-tailed noises. As we transition to heavy-tailed noise with finite variance (in the middle column), TOFU outperforms OFUT, instead in terms of regret and convergence, implying truncation works better in this case. However, both remain suboptimal compared to AULOFUL. In the case where the noise is predominantly heavy-tailed with only bounded expectation (in the right column), TOFU and OFUL's convergence errors and regrets deteriorale, contrasting with the steadfast performance of AdaOFUL. These findings show AdaOFUL's empirical robustness even in the infinite variance noise regime.
3 An Extension to Linear MDPs
Ridge regression estimators are widely used in RL to provide confidence guarantees for bounded rewards. However, when dealing with heavy-tailed rewards, these estimators tend to degrade or even fail (as shown Figure 1). In response, we advocate for the use of the adaptive Huber regression, or AdaOFUL, as robust alternative lo ridge regression. AdaOFUL can seamlessly enhance the original algorithm to accommodate teived scenarios with minimal disruption to its core. In this section, we demonstrate this by integrating AdaOFUL as foundational element to solve lincar MDPs and provide varianco-aware regrets. This approach can also be extended to other linear problems such as linear mixture MDPs (Zhou & Gu, 2022).
3.1 Linear MDPs with Heavy-tailed Rewards
Preliminaries about linear MDPs An episodic finite horizon MDP is denoted by a tuple M = (S,A, H. (r (FP]) where S the state space with a possibly infinite number of states, A the action space, H E ++ the length of each episode, P,, S A - A(S) the transition probability function, and Th S x A - R the expected reward function. A linear MDP assumes that both the transition probability and the expected reward are linear in a known state-action feature map o(-,-) Rd (Bradtke & Barto, 1996; Mclo & Ribeiro, 2007; Yang & Wang, 2019; Jin et al., 2020b).
Definition 3.1 (Linear MDP). M is called kime-inhomogeneous linear MDP, if there exist some known feature map dbs a) S A + Balla(I), unknown signed measures {u hela S gdx[s], and unknown coefficients (0 [N[ S (W) such that ra(s, a) (Ø(s,a), 0% and Px a) = (),,a))))))) for any (s, a) E S A, E [H], where [x] == E.es (z)(s) & d for all h E [H].
For a time-inhomogeneons MDP, we denote its deterministic and timo-dependent policy by π = (Th (ha-- Let {(t,, (n)) [a))ee[H] be stale-action pairs such that on = nn (sn) and 8 ~ (- an). Define the occupancy measure for the policy т at the h-th round by (s, a) = 1 (sh s, an = alsı) where (a), 82, a.. , Sh, an) is trajectory starting from si and following the policy म. The state-action function QT(--) and value function (.)()) at the h-th round are defined as QR(.,)) = EIΣ"" ru(s,, a (s), a.) = (.-))] and (T(() = QT( ()) respectively. The optimal policy is denoted by x* and its value function denoted by Vi- One can show that (s)(s) = sup, (s) for any s S. For any value function V, write (P,,) a) (.- V(s') and (s))) [PAV2](s,
(s, a). With a slight abuse of notation, let (P,, (s, a) and (Va Rr a)
8

---

Published in Transactions on Machine Learning Research (April/2024)
denote the expectation and variance of the random reward R,(s, a) at the h-th round given state-action pair (8,a). a).
Linear MDPs with heavy-tailed rewards We consider linear MDPs with heavy-tailed random rewards that satisfy the following assumptions.
Assumption 3.1 (Realizable reward). We assume that the following holds.
For all (s, a) E x A and E [H], the random reward Rn a) is independent of $4+1(s, a), where 8h+1(8, a) ~ (-,(-),,)) represents the next state transitioned from (s,4) at the h-th round.
2. There exists known feature maps ((s, a) S x A - Balla(1) and unknown coefficients (1b% = (W)l so that (s, = (ő(s, a), + for all (s, E S x A and h e [H].
Assumption 3.2 (Bounded variance). We assume that the following holds.
1. There exist known constants σR, R > 0 such that [V, a) & oR and [V (V,d)](ssa) o for all (s, a, h) E S x A and h e [H].
2. There exist known upper bounds H.Y such that for any policy x, we have 0 & ER, & H and Var(R>) & y2 where Rx= > Ra Ra(8n, un) denotes the sum of random rewards along the trajectory following π.
Rationale behind the assumptions Assumption 3.1 assumes that the random reward at each round is independent of future states and its second moment can be realized using a known feature map. Under this assumption, lincar MDPs can recover tabular MDPs by setting the size of the state-action space as = | and using the canonical basis (bs.a) a) x(s.a) a) ((e,a) in R2d Assumption 3.2 places upper bounds on the means and variances of every random reward and the cumulative rewards. These upper bounds are available under the classic uniformly bounded reward assumption that & Su suPhe[m] Rs a) & 1 so that OR = ge = 1 and H V = H. We emphasize that almost all previous works use these '1" and "H" upper bounds implicitly in their algorithm design and regret analysis. In this way, they can't tell the effect of the expectation of cumulative rewards on the final regret from their variance. We are the first to distinguish them by separate H and V. Since only upper bounds for H. and V are required, in practice one can guess them using the doubling trick.² As we will observe, very large guessing values for H and V will not affect the order of the dominant (or variance-aware) term in our regret as long as T' is sufficiently large. As far as we know, Assumption 3.2 is the weakest moment condition on random rewards in the variance-aware RL literature.
Learning protocol Let FA, denote the a-field generated by all random variables up to, and including, the h-th round and k-th episode. At the beginning of each episode k, the environment selects the initial state $1,6- The agent proposes policy Th (=[]) based on the history up the end of episode k 1, and then exccutes Ty to generate a new trajectory {[Sp,R, R, (R, Here as,a = n (sn,)) Tn, ~ (sp,e an,s) and 8/, P(-Isn,,,
Here [s,s, a) denotes the distribution of the random reward conditioned on the state-action pair a) at horizon h, with its expected value being (s, a). The agent aims to minimize the cunulative regret over K episodes, given by
K Reg(K)= = Σ (v - 1y k-1
3.2 High-level Algorithm Description
In this subsection, we introduce VARA, an algorithm present in Algorithm 2, that extends AdaOFUL to solve lincar MDPs with heavy-tailed rewards. At a high level, the VARA algorithm is built on LSVI- UCB++ (He el al., 2022), an algorithm proposed recently to achieve minimax optimality for linear MDPs.
For example, we can guess 7/ 2,4,6, 6..... After logarithmic number of guessing, we can find true upper bound for sup, ERR, One can run a similar procedure for other quantities.

---

Published in Transactions on Machine Learning Research (April/2024)
Algorithm The VARA algorithm (informal)
Require K, H, H. V, W. p2.
for episode = to K do
for horizon h to do
Based on all (On, bhak estimate an optimistic Qn and pessimistic Q-value Q by LSVI- UCB++
V((.) maxa Qi a), ()) max, ()) x+() E argmax, a)
end
for
horizon h = Play 0n, = x (8n,k) and observe rh,k ~ (s,, an,k), 8h+1, ~ P(-|snnA an.)).
do
7
Observe feature vectors 01, (( an,k) and Φ1, @(sh,k: an,k).
Update the estimated variance h using observed data and estimated values Q and Q" Update the parameters Whik, Thiss W i Ar.k following the spirit AdaOFUL.
10
11
Using (0n,))E and {(an,s,, Wh, (T. Mek AdaOFUL produces On. as the estimate for 0% Using (e and {oo,,r Wr kb gi AdaOFUL produces 3/4, the estimate for 2b
12
13
end
14 end
LSVI-UCB++ (He et al., 2022) uses weighted ridge regression, where the weights depend on some proper variance estimators ss. The variance estimation tochniques in LSVI-UC++ are important to obtain variance-aware regrets. These techniques include (i) separate variance estimation, (ii) monolonicity of value functions, and (iii) rare-switching value function update.
Due to limited space, we present the detailed and formal algorithm description in Appendix and focus on the differences between VARA and LSVI-UCB+ (He et al., 2022) here. To obtain variance-aware regrets under heavy-tailed rewards, we made two improvements LSVI-UCB+++ First, while LSVI-UCB++ assumes a deterministic, uniformly bounded, and known reward function, we use AdaOFUL to estimate the parameters 0% and b for both the expected reward functions and their second-order moments. This complicates the construction of the variance estimators 0 and requires more detailed analysis of their impacts the final regrets (sce Lemma D.10). Second, previous works use the Nauma-Hooffding incquality to analyze the concentration effect in the suboptimality gap, which leads to the regret of Ö(vK). Instead, use varianco-aware Bernstein inequality and produce a much tighter upper bound of Ó(1) for the concentration effect (see Lemma D.8). We explain the analytical novelty in detail in Appendix D.2.
3.3 Regret Analysis
This section presents the statistical, space, and computational complexities of Algorithm 3. Theorem 3.1. Consider linear MDP satisfying Asumption 3.1 and 3.2. For any ò e (0, 1), with probability
at least 1 - 216, Algorithm 3 achieves the following regret
Reg K) = Ô ( + Hdy Ko Kiin +
112.5.HH + HdloR
+ H Hdo + Hd) Hde),
(3.1)
where amin is a manually set arbitrary lower bound for all variance estimators on,
g* min Σ
(x Rv + VA (s.
(3.2)
and 2ht (8. K Ik dh (8, a) with d (s, a) pm (sh. 8, au = also = 81.4) the probability of reaching (sn.k: an.k) (s) at the h-th step when the agent starts from $1,8 and follows the policy uy.
Trade-off by Gmin Theorem 3.1 reveals trade-off arising from the choice of mmin- The second term in equation 3.1, stemming from the imposed lower bound variance estimates for stability purposes, is
10

---

Published in Transactions on Machine Learning Research (April/202)
positively dependent on min- Consequently, if mii 0, this term vanishes. The third term is negatively dependent on min due to its effect on Hr. Consider an extreme case. Tf miin oo, Hr is reduced to XI, implying the shape of the confidence region C changes. This, then, would slightly decrease the confidence radii By and the regret. The choice of miin must balance these opposing effects. Corollary 3.1 implics that choosing the optimal o min WHL + do 12- K yields a regret barrier of Ô (Ild [Hd-v/dHH vd + do V When To the
K is sufficiently large, the regret bound in equation 3.3 can be further simplified to Ö best of our knowledge, Theorem 3.1 is the first to derive the variance-aware regret for linear MDPs, especially with heavy-tailed rewards.
Corollary 3.1. Under the same sctting of Thoorem 3.1, if we sct mmin = v H2 + do K-t, the regret of VARA is bounded by
Reg(K) K) = Ö (dVTTs* + HdP da VK H + Hdon Hd?)
(3.3)
Instance-dependentt quantity G* The quantity G is given by equation 3.2. Firstly, it is bounded above by 22 in Assumption 3.2, which sets an upper bound on the variance of the cumulative random rewards received when following any policy. Other upper bounds such as H, oR and gg don't involve in G and thus the regret when K sufficiently large. Secondly, even V is set to be extremely large, G* no greater than the sum of per-rount conditional variances [VARA, + W4 a), weighted by an averaged occupancy measure d (s.a) :- > dhh a). The function d (:.-) introduces a probability measure on S x A for any fixed h e [H] by the dcfinition of d% which records the history of the policies taken.
Our variance-aware regret has two key features. Firstly, we do not require any prior knowledge of g* to achieve variance awareness, which is the same as (Zanette & Brunskill, 2019). Secondly, the additional conditions imposod on the MDP structure lead other instance-dependent regrets. In the following, we also impose Assumption 3.3 for fair comparison with related work. However, we would like to emphasize that. all of our results are obtained in the presence of heavy-taaledd rewards.
Assumption 3.3. We assume that 0 & Rs( for all h E [M] and (s, S A.
3.4 Other Instance-dependent Regrets
Worst-case regret Under Assumption 3.3, V22 H² according to the law of total variance (Azar et al., 2013). Consequently, we can infer that G* < H2 and the regret reduces to the minimax optimal ((dH/HK) (He et al., 2022). The authors achieved this regret by directly setting min = 1/H, without taking into account. the trade-off introduced by min- Although this was sufficient for their worst-case scenario, it was not suitable for our goal of achieving variance awareness. If we also set Jmin 1/H, the second term in equation 3.1 becomes dv dvK, K, and cannot determine the dominant term between Hy and dvK. Once we balance the trade-off of mmin, the second term becomes much smaller, making ()) the dominant term.
Range-dependent regret Let Sa,a be the set of immediate successor states after one transition from state s upon taking action a, which is also the support set F(-(s,,), a). Define Lscce as the maximum value function range when restricted to the immediate successor states:
suce sup supl sup V+++(11) inf (+)) d'ES...
he[H]] (s.a) d'eS...
Since the variance is upper bounded by fourth of the square range of a random variable, we have suphe(m) sup( 4 h+ (s, a) & 1 1 and thus g* H(o + 2. Therefore, our regret reduces δ V + 42 ) It is worth noting that similar range-dependens regrets have been derived for tabular MDPs with bounded rewards (Bartlett & Tewari, 2009; Fruit et al., 2018; Zanctte & Brunskill, 2019), but to the best of our knowledge, we obtain the first such result for linear MDPs with heavy-tailed rewards.
First-order regret The first-order regret that scales proportionally to Vi*, where V := (31) is the value of the optimal value policy at the initial state 81, has been studied for tabular MDPs (Jin et al.,
11

---

Published in Transactions on Machine Learning Research (April/202))
2020a) and linear MDPs (Wagenmaker et al., 2022a). 3 However, under Assumption 3.3, the corresponding instance-dependent quantity H2V can be much larger than g². This is because
H B
H E (3a) (s, 1 HPV
g
H
(1,0)
2x [rn + PA i < H
2 h=1
where (a) uses 0 < R E and 0 < V & H - under Assumption 3.3, (b) uses the optimality condition h+1
(+) = [rh + PA V I(s,, a) for any (5, E S x A, and (c) uses ( & (s) for any h [H] and s E S and Loes ()),a) a)
since each episode starts at a fixed state 81. Moreover, even replacing g with the coarse upper bound H2V our regret bound becomes Ö( ((V/ which has a better dependence on d than Ö(VdHHVVT K) in (Wagenmaker et al., 2022n).
regret Let RS* denote the sum of random rewards collected in trajectory following the optimal policy n* It is straightforward to see that (ax(R=*) = Σ E (a.a))aa [V Rs. + VA V a). Since g* & sup, Σ o, V. V a), we can show that g* & Ct. .Var R,
Concentrablitt--deeeeeee
where Ct is a data coverage measure defined as
1- (( V Rr VaV (s)
Ct := sup
Σ 1=
E
(V R2 V (s)
Therefore, our regret reduces to Öldy Ot Var(Rx+)HH given C < sp. The C2 is counterpart of the generalized concentrability coefficient which quantifies the effect of the distribution shift in offline RL (Chen & Jiang, 2019; Xie et al., 2021; Cheng et al., 2022).
3.5 Space and Computational Complexities
Theorem 3.2 (Space and computational complexity). Assume the Nesterov accelerated method is used as a solver to solve the adaptive Huber regression. Solving a H-horizon finite MDP in K episodes. VARA takes Old 2 + ()) space and has a running time of (dd))A(H K + HK(d + 3/3
On one hand, VARA achieves the same space complexity as LSVI-UC+++ but is slightly worse than the original LSVI-UCB (Jin et al., 2020b) that needs + K) space. This is because the technique of monotone value function update requires remembering at most Ö(df) latest value functions, incurring a slightly worse dependence on d and H. On the other hand, the computational complexity of VARA ( + HK(d + --3// K3/1)) slightly worse than L.SVI-UC+++'s 's ((d))A(H*)) in terms of the dependence on K. This is because the adaptive Huber regression estimator does not have a closed-form solution. Even though the Nesterov accelerated method is used, a slightly larger computational complexity is still incurred due the possibly large conditional mumber. However, VARA's computational complexity is better than LSVI-UCBss O ((2) thanks to the rare-switching mechanism in LSVI-UCB+
+
4 Related Work
Hcavy-tailed rewards in online decision making The standard heavy-tailed setting assumes rewards with (1+ -)-monents where > 0. There exists large body of work considering this setting in multi-arm bandits, including deterministic (Vakili et al., 2013) and non-deterministic settings (Bubeck et al., 2013; Carpentier & Valko, 2014; Lattimore, 2017; Bhatt et al., 2022). To handle heavy-tailed rewards, robust mean estimation methods such as median of mcans and truncation have boen applied to lincar bandits (Medina & Yang, 2016; Shao el al., 2018; Lu et al., 2019; Xue et al., 2021). Given that our objective is to provide variance-aware regrets for general linear bandits, the minimal requirement is to have bounded second moments, which is the primary focus of this study. Under the assumption of rewards with bounded second
They assume all episodes start from the same initial state so that 81,8 = 81. However, our regret can be easily extended to the setting where initial states are different. In this case one should replace V K with X V (#1,)) the regret bound.
12

---

Published in Transactions on Machine Learning Research (April/202))
moments, the minimax optimal regret is Ö(dYT). Recently, Kang & Kim (2023) introduced the use of Huber regression to address heavy-tailed linear contextual bandits where the action set is fixed (such that D, D) and the arm Φe is independently and identically distributed, sampled from a fixed distribution over D. In contrast, our proposed AdaOFUL is simpler and more versatile, capable of being applicd to more complex scenarios where the arm Φe selected adaptively based on historical observations.
regreet
On the other hand, there are few RL algorithms designed to handle heavy-tailed rewards for MDPs. One is (Zhuang & Sui, 2021), which modifies UCRL2 and Q-Learning by using truncated rewards and achieves minimax optimal regret in tabular MDPs. However, none of these methods for linear bandits or MDPs provide varianco-aware regrets, even if variance information is available. Moreover, simple truncation methods are not optimal in the noiseless setting. Recently, Huang et al. (2023) extends the Huber regression to the more general (1+ ()+))-monne m)mmmnnt setting and provides dependett regret bounds for both linear bandits and linear MDPs
awree regrets for linear bandits A weighted ridge regression- based algorithm proposed by Kirschner & Krause (2018) achieves the same regret in equation 2.7 by assuming each & is More recently, Zhou & Gu (2022) obtained the same regret assuming each E is uniformly bounded and has finite conditional variance vg. In the case where the information of conditional variances {u is unknown, Zhang et al. (2021) and Kim et al. (2021) achieved regret bounds that involve sub-optimal dependence on d. The currently tightest variance-aware regret is achieved by Zhao et al. (2023) with an optimal dependence on d. Recently, Dai et al. (2022) explored variance-aware regrets in the context of high-dimension and sparse linear bandits, a topic that extends beyond the scope of our paper. All of the above works consider light-tailed noises, which are either sub-Gaussian or uniformly bounded.
Robust approach to instance-dependent bounds Recent research explores the robust mean estimation approach to obtain instance-dependent regrels, leveraging the observation that robust estimatoos can achieve estimation errors that only depend on the noise scale. Such estimators often have better theoretical guarantees than non-robust ones, whose estimation errors additionally depend on the range of the problem noise. For instance, Pananjady & Wainwright (2020) use the median-of- -oenanns--- technique (Lecué & Lerasle, 2020) to achieve local minimax optimality that depends on the standard deviations of the optimal value function and random rewards for synchronous tabular MDPs. In linear bandits, Wagenmaker et al. (2022a) use Catoni's estimator (Catoni, 2012) to estimate the mean of v H1'0//8//0 for a fixed unit-norm vector V. In contrast, we modify the adaptive Huber regression to estimate 0 directly. This difference makes their bounds depend on the second moments of y 's, while ours only relies on their variances. Moreover, all of these works, except. ours, still assume light-tailed rewards.
Varianco-aware regrets for tabular and lincar MDPs In the context of online episodic MDPs, Zanette & Brunskill (2019) first derived a variance-aware regret bound in the tabular setting with uniformly bounded rewards. Their model-based algorithm, Euler, achieves a regret that can be bounded by either CIVQSAHK,
ÖKK))SAK), where Q* = max(s,,, (V, + VA (s, 1s,,,, a) is the maximun per-round conditional variance and G is a deterministic upper bound on the maximum attainable reward on a single trajectory for any policy ग, such that Σ RR(Ss, (8k)) & g. One can show that our instance-dependent quantity G* is smaller than min{H (2) therein. Later, Jin et al. (2020a) adopted a modified analysis of Euler to obtain the regret bound ((5SHH²** with V = Vi ( In linear MDPs, there are several recent works on obtaining regret bounds for model-free algorithms. For example, Wagenmaker et al. (2022a) proposed an optimistic algorithm with a regret bound that scales as (( K). However, this algorithm is computationally inefficient. A computationally efficient alternative suffers from a slightly worse regret Ö(VdHH*V²*) K). All of these works utilize the instance-dependent quantity H² (assuming H = H) However, as we argued, our proposed quantity g* is smaller than H which implics that our algorithun may achieve better performance than these previous works. Another research direction
Unlike our setting, they assume all initial states are the same, denoted as 81. Furthermore, the original regret /S/SAH vy* K) by Jin al. (2020a) was derived for MDP where the reward function equals to one deterministi- cally only a single (h. s) pair. In this way, they have & V** To convert it in the considered setting where & V/* H, an additional factor of H should be multiplied their regret.
13

---

Published in Transactions on Machine Learning Research (April/202))
explores variance-adaptive algorithms for linear mixture MDPs, initially explored by (Zhou et al., 2021). Subsequent developments in this area were made by (Zhang et al., 2021; Zhou & Gu, 2022), culminating in the state-of-the-art advancements by (Zhao et al., 2023). While our study does not consider this particular setting, it is straightforward to extend our techniques and analysis to it, as linear mixture MDPs are generally considered simpler than linear MDPs.
Other instance-dependent bounds In the infinite-horiaat setting, Pananjady & Wainwright (2020); Khamaru et al. (2021); Li et al. (2023) provided variance-aware sample complexities for Q-Learning and variants tabular MDPs, given generative model that produces independent samples for all state- action pairs in every round. Variance-aware performance guarantees have also been established for offline RL optimization (Yin & Wang, 2021; Nguyen- Tang et al., 2023), off-policy evaluation (Min et al., 2021), stochastic approximation (Mou et al., 2020; 2022). Another approach to instance-dependennee bounds focuses on the minimum suboptimality gap, which is the minimum gap between the best and second-best actions over all states (He et al., 2021; Wagenmaker et al., 2022c; Wagenmaker & JJmieson, 2022; Dong & Ma, 2022). However, due to the differences in the settings, we cannot make meaningful comparison between these bounds and ours.
5 Conclusion
This paper introduces two new algorithms, AdaOFUL for linear bandits and VARA for linear MDPs, both of which use modifications of the original adaptive Huber regression and are designed to handle online sequential decisson-making With only the assumption of bounded reward variances, our algorithms achieve either state-of-the-art or finer variance-aware regreis. Additionally, linear MDPs, the instance-dependent quantity G* can be bounded by other instance-dependent quantities when additional structure assumptions are available. Our modified adaptive Huber regression can be useful building block for algorithm design in online problems with heavy-tailed rewards.
Acknowledgments
The work was done when Xiang Li was a visiting student in the IVGS program al the Department of Statistical Sciences, University of Toronto. Qiang Sun was partially supported part by the Natural Sciences and Engincering Research Council of Canada under Grant RGPIN-2018-06484 and a Data Sciences Institute Catalyst Grant.
References
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems, volume 24, 2011.
Nick Arnosti, Marissa Beck, and Paul Milgrom. Adverse selection and auction design for internet display advertising. American Economic Review, 106(10):2852 66, 2016.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. Tn International Conference on Machine Learning, pp. 2020.
PMLR,
Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen. Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model. Machine Learning, 91 (13):322-333)) 2013.
Peter Bartlett and Ambuj Tewari. Regal: regularization based algorithm for reinforcement learning in
weakly communicating mdps. In Conference on Uncertainty in Artificial Intelligence, pp. 35 42, AUAI Press, 2009.
Sujay Bhatt, Guanhua Fang, Ping Li, and Gennady Samorodnitsky. Nearly optimal Catoni's M-estimator for infinite variance. Tn International Conference on Machine Learning, pp. 1925-1944 2022.
14

---

Published in Transactions on Machine Learning Research (April/202))
Steven J Bradtke and Andrew G Barto. Linear least-squares algorithms for temporal difference learning. Machine Learning, 22(1):33-55) 57, 1996.
Sébastien Bubeck, Nicolo Cesa-Bianchh and Gábor Lugosi. Bandits with heavy tail. IEEE Transactions on Information Theory, 50(11):7711-7117, 2013.
Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and TrendsB in Machine Learning, 8(3-4):231 357, 2015.
Alexandra Carpentier and Michal Valko. Extreme bandits. In Advances in Neural Information Processing Systems, 2014.
Olivier Catoni. Challenging the empirical mean and empirical variance: A deviation study. Annales de l'IHP Probabilités et statistiques, (8(4):1148-1185) 2012.
Jinglin Chen and Nan Jiang. Information--hhoorllicc considerations in batch reinforcement learning. In International Conference on Machine Learning, pp. 1042-1051. PMLR, 2019.
Ching-An Cheng, Tengyang Xie, Nan Jiang, and Alekh Agarwal. Bellman-consistent pessimism for offline reinforcement learning. In International Conference on Machine Learning, volume 162, pp. 3852 3878, 2022.
Rama Cont. Empirical properties of asset returns: Stylized facts and statistical issues. 1(2):223, 2001.
Quanlilative Finance,
Yan Dai, Ruosong Wang, and Simon Shaolei Du. Variance-aware sparse linear bandits. In International Conference on Learning Representations, 2022.
Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. 2008.
Kefan Dong and Tengyu Ma. Asymptotic instancc-optimal algorithms for interactive decision making. arXiv preprinl ar Xiv:222066.0 02326, 2022.
David A Freedman. On tail probabilities for martingales. The Annals of Probabilily, 3(1):100 118, 1975.
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient bias-span-constrrincd exploration-eexlloittion in reinforcement learning. In International Conference Machine Learning, pp- 1578 1586, 2018.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer, 2009.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with lincar function approximation. In International Conference Machine Learning, pp. 4171 4180. PMLR, 2021.
Jiafan He, Heyang Zhao, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for linear markov decision processes. Xix preprint arXiv:2212.060 061361 2022.
Pihe Hu, Yu Chen, and Longbo Huang. Nearly minimax optimal reinforcement learning with linear function approximation. In International Conference on Machine Learning, pp. 8971-9019, 2022.
Jiayi Huang, Han Zhong, Liwei Wang, and Lin F Yang. Tackling heavy-tailed rewards in reinforcement learning with function approximation: Minimax optimal and instance-dependent regret bounds. arXiv preprint ar 23v: 2006606366,, 2023.
Peter J Huber. Robust estimation of a location parameter. The Annals of Matheratiial Stalistics, pp. 73 101, 1964.
John Hull. Risk Management and Financial Institutions. John Wiley & Sons, 2012.
15

---

Published in Transactions on Machine Learning Research (April/2024
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is Q-learning provably efficient? In A Advances in Newral Information Processing Systems, volume 31, 2018.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforce- ment learning. In International Conference on Machine Learning, pp. -879. PMLR, 2020a.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theery, pp. 2137 2143, 2020b.
Minhyun Kang and Gi-Soo Kim. Heavy-tailed linear bandit with Huber regression. In Uncertainty in Artificial Intelligence, pp. 1027-1036. PMLR, 2023.
Koulik Khamaru, Ashwin Pananjady, Feng Ruan, Martin J Wainwright, and Michael I Jordan. Is temporal difference learning optimal? An instance-dependent analysis. SIAM Journal Mathematics of Data Science, 3(4):1013-1040, 2021.
Yconoung Kim, Insoon Yang, and Kwang-Sung Jun. Improved regret analysis for varianco-udaptive lincar bandits and horizon-free linear mixture mdps.. arXiv preprial ar Xic:2211.032880 2021.
Johannes Kirschner and Andreas Krause. Information directed sampling and bandits with heteroscedastic noise. In Conference on Learning Theory, pp.
2018.
Tor Lattimore. A scale free algorithm for stochastic bandits with bounded kurtosis. Tn Advances in Neural Information Processing Systems, volume 30, 2017.
Guillaume Lecué and Matthien Lerasle. Robust machine learning by median-of-means: Thcory and practice. The Annals of Statistics, 48(2):906-93) 901, 2020.
Gen Li, Changxiao Cai, Yuxin Chen, Yuantao Gu, Yuting Wei, and Yuejie Chi. Is Q-learning minimax optimal? A tight sample complexity analysis. arXiv preprint arXiv:2102.065.8 2021.
Jiwei Li, Will Monroe, Alan Ritter, Dan Jurafsky, Michel Galley, and Jianfeng Gao. Deep reinforcement learning for dialogue generation. In Conference Empirical Methods in Natural Language Processing, pp- 1192 1202, 2016.
Xiang Li, Wonhao Yang, Jiadong Liang, Zhihua Zhang, and Michael I Jordan. A statistical analysis of Polyak-Rupper averaged Q-learning. In International Conference on Artificial Intelligence and Statistics, 2023.
Timothy P Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Contimuous control with deep reinforcement learning. arXiv preprint Xix: Xrvvv15509 15090.297.. 2015.
Shiyin Lu, Guanghui Wang, Yao Hu, and Lijun Zhang. Optimal algorithms for Lipschitz bandits with heavy-tailed rewards. In International Conference on Mochine Learning, pp. 4154 4163, 2019.
Andres Munoz Medina and Scott Yang. No-regret algorithms for heavy-tailed linear bandits. In International Conference on Machine Learning, pp. 1642-1650, 2016.
Francisco S Melo and Isabel Ribeiro. Q-learning with linear function approximation. International Conference on Computational Learning Theory, pp. 308-322 2007.
Yifei Min, Tianhao Wang, Dongruo Zhou, and Quanquan Gu. Variance-aware off-policy evaluation with linear function approximation. In Aduances in Newral Information Processing Systems, volume 34, pp. 7598 7610, 2021.
Wenlong Mou, Chris Junchi Li, Martin J Wainwright, Peter Bartlett, and Michael Jordan. On lincar stochastic approximation: Fino-grained Polyak-Rupper and non-asymptotic concentration. In Conference Learning Theory, pp. 2947-2960 2020.
16

---

Published in Transactions on Machine Learning Research (April/202)
Wenlong Mou, Koulik Khamaru, Martin J Wainwright, Peter L Bartlett, and Michael I Jordan. Optimal variance-reduced stochastic approximation in banach spaces. arXiv preprinl ar "xXi:2201.0857 2022.
Thanh Nguyen-Tang, Ming Yin, Sunil Gupta, Svetha Venkatesh, and Raman Arora. On instance-dependdnnt bounds for offline reinforcement learning with linear function approximation. In Association for the Advancement of Artificial Intelligence, 2023.
Ashwin Pananjady and Martin Wainwright, Instance-dependent lo bounds for policy evaluation in tabular reinforcement learning. IEEE Transactions Information Theory, 67(1):566-585, 2020.
Alexandra Posckany, Klaus Felsenstein, and Peter Sykacck. Biological assessment of robust noise models microarray data analysis. Bioinformatics, 27(6):807 814, 2011.
Han Shao, Xiaotian Yu, Irwin King, and Michael R Lyu. Almost optimal algorithms for linear stochastic bandits with heavy-tailed payoffs. In Advances in Newral Information Processing Systems, 2018.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panncershelvam, Marc Lanctot, et al. Mastering the game of Go with deep neural networks and tree search. Nalure, 529(7587):484 489, 2016.
Qiang Sun. Do we need to estimate the variance in robust mean estimation? arXio preprint ar arXiv:2107.00118, 2021.
Qiang Sun, Wen-Xin Zhou, and Jianqing Fan. Adaptive Huber regression. Journal of the American Stalisticnl Association, 115(529):254 265, 2020.
Richard S Sutton and Andrew G Barto. Reinforcement Learning: An Introduction. MIT Press, 2018.
Sattar Vakili, Keqin Liu, and Qing Zhao. Deterministic sequencing of exploration and exploitation for multi-armed bandit problems. IEEE Journal of Selected Topics in Signal Processing, 7(5):759 777775977777777 2013.
Andrew Wagenmaker and Kevin Jamieson. Instance-dependent near-optimal policy identification in linear MDPs via online experiment design. In Advances in Neural Information Processing Systems, 2022.
Andrew J Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson. First-order regret in reinforcement learning with linear function approximation: A robust estimation approach. In International Conference on Machine Learning, pp. 22384 22429. PMLR, 2022a.
Andrew J Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson. Reward-free RL is no harder than reward-aware RL in linear Markov decision processes. In International Conference on Muchine Learning, pp. 22430 22456, 2022b.
Andrew J Wagemmaker, Max Simchowitz, and Kevin Jamieson. Beyond no regret: Instance-dependent pac reinforcement learning. In Conference on Learning Theory, pp. 358 418, 2022c.
Tengyang Xie, Ching-An An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consistent pessimism for offline reinforcement learning. In Advances in Neural Information Processing Systems, volume 34, pp. 6683-6694, 2021.
Bo Xue, Guanghui Wang, Yimi Wang, and Lijun Zhang. Nearly optimal regret for stochastic linear bandits with heavy-tailed payoffs. In International Conference on International Joint Conferences on Artificial Intelligence, pp. 2936 2942, 2021.
Lin Yang and Mengdi Wang. Sample-optimal parametric Q-learning using linearly additive features. In International Conference on Machine Learning, pp. 6993-7004, 2019.
Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference Machine Learning, pp. 10746-10756 PMLR, 2020.
Ming Yin and Yu- Xiani Wang. Towards instance-optimal offine reinforcement learning with pessimism. In A Adaacces in Neural Information Processing Systems, pp. 2021.
17

---

Published in Transactions on Machine Learning Research (April/2024)
Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pp. 7304 7312. PMLR, 2019.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference Machine Learning, pp. 10978-10988, 2020.
Zihan Zhang, Jiaqi Yang, Xiangyang Ji, and Simon S Du. Improved variance-aware confidence sets for linear bandits and linear mixture MDP. In Advances in Neural Information Processing Systems, pp. 4342-4355, 2021.
Heyang Zhao, Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Variance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency. arXiv preprint arXiw:2302. 10971, 2023.
Dongruo Zhou and Quanquan Gu. Computationally efficient horizon-free reinforcement learning for linear mixture mdps. arXiv preprint wxXiv:2205.1550, 2022.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture Markov decision processes. In Conference on Learning Theory, pp. 4532 4576. PMLR, 2021.
Vincent Zhuang and Yanan Sui. No-regret reinforcement learning with heavy-tailed rewards. In International Conference on Artificial Intelligence and Statistics, pp. 3385 3393, 2021.
18

---

Published in Transactions on Machine Learning Research (April/2024)
Appendix
Overview
We describe VARA detailedly Appendix and explain the rationale behind its variance estimator Appendix B. Appendix contains proofs for Theorem 2.2 and related lemmas specifically for linear bandits. The thcoretical analysis for VARA is presented in Appendix D, where offer a proof sketch for Thoorem 3.1, while all related technical lemmas are deferred to Appendices F and G. We also highlight the differences between analysis and previous work. In Appendix E, we provide proof for Theorem 3.2 that analyzes the space and computational complexity of VARA.
Table of Contents
A Detailed Algorithm Description for VARA
B Variance Estimation for Value Functions
C Proof for Section 2.3
23
C.1 Proof of Theorem 2.2
23
C.2 Proof of Lemmna 2.1
25
C.3 Proof of Lemma 2.2
28
C.4 Proof of Lemma C.1
30
C.5 Proof of Lemma C.2
32
Proof of Theorem 3.1
D.1 High-Probability Events
33
D.2 Regret Analysis...
35
E Proof of Theorem 3.2
37
Omitted lemmas in Section D
38
F.1 Proof of Lemma D.1
38
F.2 Proof of Lemma D.2
................................
38
F.3 Proof of Lemma F.1
39
F.4 Proof of Lemmna D.3
41
F.5 Proof of Lemma D.4
42
F.6 Proof of Lemma D.5
42
F.7 Proof of Lemma D.6
44
F88 Proof of Lemma D.7
44
F.9 Proof of Lemuna D.8
46
F.10 Proof of Lemma D.9
48
F.11 Proof of Lemma D.10
49
G Auxiliary Lemmas
55
G.1 Concentration Inequalities
55
G.2 Elliptical Lemmas
56
G.3 Function Class and Covering Number
56
19

---

Published in Transactions on Machine Learning Research (April/202))
A Detailed Algorithm Description for VARA
For cach episode k, we perform optimistic value itcrations (Lines 3-11), compute the greedy policy of with respective to the pessimistic value function Q% (Line 12), and then execute it to collect a new trajectory of data (Lines 16-17). The rest Algorithm updates maintained estimators, inchuding the conditional variances oi (Line 19), the transition parameters Ph,k (Line 20), the reward parameters 0,,k, upn, (Lines 21-22), and the Hessian matrices H Hi.k (Line 23). In what follows, we discuss in detail the key steps of Algorithm 3 in more detail.
Reward estimation Since rewards are collected adaplively and have only finile second moments, use the same strategy adopted in AdaOFUT. to estimate 0%
p == argmin (eBall,(W)
A (0) := =2
1 + Σ lis
Th.j (Ths-
(Ōn.. ( 0
(A.1)
Thi
Following the spirit of Theorem 2.1, we set To = Ō(vd) with its detailed expression provided in equation D.5 of the online supplement.
Transition cstimation Let 6(s) RI be onc-hot vector that is zero everywhere except for the entry corresponding the state s, which is one. We define Eh, (- an,k) 8(sh+1,)) As B[En, 0, 8(h++1,)) is an unbiased estimator of (PP(-18a.. (b.k) 14, ((88, an,k) 14, Dn.k. Thus, we can learn ps by regressing (1))112) on Φb := ((5h.k: an.k):
[ - 111
ph Dh.k 8(8h+10)
Phik = argmin p
(A.2)
2
The
where | |F denotes the Frobenius norm. This problem admits closed-form solution given by We emphasize that VARA doesn't need to compute M4g actly out. VARA relies on only the matrix product of PA. and vectoerzied value function V that is M H - V ((*+11.)) for any value function V(-). As Theorem 3.2 shows, both the computation and space complexity do not depend on the finite value of [S].
MA.k:
H h.k
1 Σx 11 h. (
Variance estimation for rewards In linear MDPs, estimating the variance of the reward R, is straightforward. Since P, (s, a) (Ō(s, ()), we estimate thtt by
X I (12) (vb) 2 1 lins
Thi - (Zn.s:
argmin (EBalla(W)
(A.3)
Th
where Fr.k = /0 W Wi.k the corresponding robustification parameter and Wr.k
| Hiik is
the importance weight. We then estimate [V, Rn,ss, an) by
[ Ry an = ( th - [ On 1)o.n1)
(A.4)
Variance estimation Inspired by Hu at al. (2022), we set the variance estimator oh to be
W (vena HaR.5 bn
hh max oiine dH H Enc, Jn to 2ht
(A.5)
where Owin is a small positive constant to avoid singularity, by.k = max(llbneell 1 bonus term, En and Jn.k are defined as
H,
} is the
Jr.k
[Vn Rr VnA V MeVVn+1lle ( ab.k) + Pu.k Un.ks
(A.6)
20

---

Published in Transactions on Machine Learning Research (April/202)
Algorithm The VARA algorithm (formal)
Require K, H, H.V, W, WR R2. To. To
Initialization: H4,0 = H = X0 6/3ling 2nK2 C1
42-log 20 H2+W22 Mast 1.
for episode to K do
(-+1(-)= = V (-) =
for round h = H to do if there evisls a slage l [H] such that det (H > 2del Har then
3
Compute the products phn V h+1 and phn Vi+1 with Ma,s given in equation A.2.
4
(..)))) = -,((-)), -(((.)),n.kk1 0n,k-1+ + Mh,k V x+1 + (111))))))mm
5
Mh, h+1 (| 1 (%(:))= = min { (Qt(.-), Q (,
(f(---)= = ((((:-))(((-)))))) (,(,,),0,,k-))
6
), H 2% max (x
7
8
Record the last updating episode kjast = k.
else
Φ = 0n (.-)) 2 (...).
10
11
end
Vx(+) max, ln a), v max, (,(.
12
( argmax, ax(.a))
13
14
end
15
Receive the initial state $1.k- for round to H do
16
17
Play 0n = (sa,a) and observe Th, Re(Sn, an,x), 8h+1, P( an,x).
Observe feature vectors Φ1,k = Φ(8h,k kn,k) and Φn. = Φ( an,k). Set the bonus as by. = max{|l@r, H Φ p...
18
19
20
Set the estimated variance a as in equation A.5.
Compute 0g, via equation A.1 with Thi /uV wh (R/y/wn, /wn, and Wh,s o 1 m Compute 1ha via equation A.3 with Fr For/1 1 Wh Wiik and Wh, o Dack H
22
Update H HA + o and H HAA on
23
24
end
25 end
En = min HP, 22,30 || Hm + H. Phna(Vhtz - v (ond)
(A.7)
in which 30 5 (o [0molttVid1)
initial exploration radius, Pn,a(-1s,a) -T, is the empir-
ical transition kernel at the h-th round and k-the episode, Vn(-) the empirical variance operator defined in equation A.4, and Ry.k. Un are defined as
RA, = B BRell A1-1, k.
+ 271. Φn,k n
(A.8)
Un. min {D². 117,80 | 10
474 Pr. h+1 Wh+1)(8nne ant)) (on,))n))) (A.9)
with 8n = Ō(vo), Bpz = δ (ova @V mmn
being two initial exploration radiuses. In Appendix B, we
explain in detail why Th,k's ''s are taken in the above way.
B Variance Estimation for Value Functions
To achieve worst-case optimality, He et al. (2022) proposes two important techniques we adopt in Algorithm 3.
21

---

Published in Transactions on Machine Learning Research (April/202))
The first is the monotonicity of value functions. Specifically, aim to enforce decrease in le for the actual optimistic value function () and an increase & for the actual pessimistic value function (*(:,) This concept is explained in detail below. In linear MDPs, we have [Fx (i. = (Ø(s, a), / Va+1> for any value function V [ei] and [A,, a) (Ø(s, a), 0 for all E [H]. One crucial aspect of typical analysis (including ours) is demonstrating the high probability of the following event outlined in Appendix D.1. Specifically, for all h [H] and k E [K], need to establish that the following equations hold simultancously with high probability:
10 H. & 3n Ö(vd),
[1 14 V h+1 hh1lH By Ö(va), [(HAA-11 - - V h+1 HA.k-1 & Bv = Ö(vd).
(B.1)
Conditional on the event that all inqqualities equation B.1 hold, we can easily verify that
(v((s:),n..-i> - R,, ) < BRlØ(;)) HT.l- ). PAAA-1 v (1 Br| R.2
for both Va+1 E (Vh+n, 1+1 1. Therefore, we define the temporary optimistic value function by
( =
and the temporary pessimistic value function by
@h(,-)) ( (n. P V - 810( H
where 3: = BR + By = Ö(d)). The actual optimistic value function Q% (sx)) is the minimum function of history temporary optimistic value functions (,-,,, and the actual pessimistic value function ()())) is the maximum function of history temporary pessimistic value functions (+(-.)) (Line 7 in Algorithm 3). In this way, Qx(-.)) is always non-increasing in and (,-),) is always non-decreasing in k.
The second is the rare-switching value function update, which updates the value function only when the determinant of the covariance matrix significantly exceeds the previous value (Line in Algorithm 3). This approach allows the complexity, measured by the metric entropy, of the function class to which (-) or (+) belongs to be independent of K. Notably, the metric entropy is linearly dependent on (dH).. Moreover, the event equation B.1, can establish optimism and pessimism in Lemma D.4, i.e, for all & e [K] and h e [M]
(l+1() & ( & (+)
(B.2)
Directly estimating the variance the optimistic value function V (++1()) will encounter the dependence issue, which is discussed in (Jin et al., 2020b) and will introduce an additional vd factor in the regret due to the covering-basee decoupling argument. To climinate this factor, after noting the incquality
< 2[V 2 +[V V++1))())),
Hu et al. (2022) decompose the optimistic value function V V (+) into the optimal value function (+++(-) and the sub-optimality gap [ 1++) and estimate their variances [V, V and (V, -V= separately. The key insight is that: (i) as Viti is deterministic, there is no additional vd dependence in estimating 1 and (ii) vhe gradually converges to Viti though uniform argument is still used, the incurred Vd factor in the estimation of [V (Vh. h+1 vi++1) has ignorable effects on the final regret. We now describe the way estimate these two variances.
22

---

Published in Transactions on Machine Learning Research (April/2024)
For [VA 1+1((:)) since V is unknown, natural choice is to estimate it by the optimistic value function v h+1 Hence, we estimate [V Vi+ (sn,,,, an.)) via
W. h+ (8h, (h,a) [ h+1 1 (shh,, an.k)
V h+ (88, an. (n. 1
(B.3)
To measure estimation accuracy, we introduce an error term Un, guarantee that with high probability, [V h. V. A+1 n+1)( (80,k) ah.a) [VnV 1 (0ssA) Un. holds uniformly all h, k where
Un,k = min (v². ( 117630 | pT + 4H (A h+1 V (5
(A.9)
and Bo
② H
ddH
is exploration radius.
min
For VV - ()))), to meet the mcasurability condition of concentration incquality (Lemma G.3), we require
oie 2 d
sup
(V h+1 Vitt))((S, an,
(B.4)
kejsK
Note that Oh,k is meeasuaseeel while V v)+ -..a---measurabe. The condition equation B.4 essentially requires a Fo,k meesuraaee upper bound for [Va ( an,)) even j > k. Fortunately, we have for any k & & K,
[Va(V h+1 ( (L,
[P
h+1 ( ah.k)
(0)
H[PA h+1 vi+t ap,))
(8)
< H(PA(V (V)
h+1 Vitt1l ah.k)
(9) HIPA (Vh h-1 ((
(B.5)
where (a) uses V 1++) H and the optimism of Vh+1(), (b) follows from the pessimism in equation B.2, and (c) uses the monotonicity of value functions. The RHS of equation B.5 is Fi, mcasurable but intractable due to the population expectation (-).). By replacing P.(-) with the tractable
Pr, we introduce FA, to overestimate the RHS of equation B.5 where
E = min { 22,80 || n.
+ H. [P - -Vh+t)) (sn,e) and)..
(A.7)
Hence, equation B.4 is guaranteed by oî > d En... The extra d " factor is introduced to offset the error caused by the covering number argument.
C Proof for Section 2.3
C.1 Proof of Theorem 2.2
Now, we turn to the regret equation 2.1. Recall that at iteration i, we set
(Φ,, +)
argmax {Φ, 0)
BEC,,
Due to sup SuPeeUiso D. (6, 0*>| < R: LB, it follows that
Reg(T) = Σ sup ( 0") - ( 0*)
DED,
23

---

Published in Transactions on Machine Learning Research (April/2024)
sup DEC
(0,0) 0) - (6; 0+)
sup (0,, 0) (0., 08)
BECt-1
| (0-1))
sup OEC,-1
10 0 H
Notice that with probability 1-ô, 6, 0* E C. for all 3 1, i.e, 10, 0* H. & Br. Hence,
sup |0 - 0* H. ecc.
sup OEC.
100 O.lH, + +100, - 0* 23,-
Notice that B is increasing in and wi
di de
Therefore,
T -28T
Reg(T)) & 23T Σ Φ H
Σ Jyll; = 23T Σ min we}.
(C.1)
The last equality uses wa & 1 (which is due to oz 2 1 1 1/00 and co & 1). Notice that 10ll/a; & o & L/Omin- Then by Lemma G.5,
Φ2
min [1,w?} & 2d [1
TL2
min 1,
2xc.
(C.2)
dAo min
Oz
H
Recall that
| H
v LB
H
0: = max
Vt, Omin:
cid'
According to what value takes, we decompose [T'] into three sets [T]]
S Ul Te where
JI {te [T] o fur, mmint
l1 [
J2 te [ 0,
co
| H
tE [
0 VLB
o dd
First, it follows that
Σ
min (1, wr <
max(v, minn] min {1, w/}
tETi
max Jmin min (1, we)
te [e
(uz o2 2
Σ SE(T]
min (1, wz)
[=[T]
V 2k
Σ [E[T]
2 + 1.
(C.3)
24

---

Published in Transactions on Machine Learning Research (April/202)
Here (a) holds due to Cauchy-Schwarz inequality and (b) uses equation C.2 and min VT"
Second, for any E J2, we have
de
Co
E 1. Therefore,
H
Σ o
min (1,we)
Σ ae
1
Σ
om &
supiEJs O1
Σ
CO
CD
tEJ
LaJ2
1EJ2
SuP[a[T]
||
H
min 1
(E/2
suPre[T]]
|
Σ
min [1, w <
2Lx
(C.4)
6
[E|T]
where the last inequality uses ( &
1
11l
4 for all t 3 1 and equation C.2. VX
vx
Finally, for any t e Ts, we have L2 = do due to wf = | H
It implics or = LBwr/Vade
LB min(1, wt), v with the fact that we & 1. Therefore,
Σ
min [1,
wz} =
LB
Σ min (1,
LB Vend
Σ
min
{1, wi <
2LBr
(C.5)
Verd
Verd
te
teJa
[E[T]
Plugging equation C.3, equation C.4 and equation C.5 into equation C.1, we have
Reg(T) 2,T
V2k-
Σ kE|TT
+
2Lx
+ 2LBK
Vad
C.2 Proof of Lemma 2.1
Recall that 20) 0) oe
Direct computation yields that
V = AI
T
To
3
Φ
/ + =²((0)
oī
Clearly, for any f e Rdd
T
O
L < XI:
+
Σ
H
of
For the other direction, decompose it into four terms and analyze them respectively.
TOOT T
2² H
1
77 + (0
o
H
(C.6)
DiOTT T
V + 2((0)
V + 20*)
of
H2r
where E,111 E[-[F=-1]] for simplicity.
Since vg 0.-1 Ft-1, from Algorithm 1, have ds We, Te F.-1-
25

---

HT. Published in Transactions on Machine Learning Research (April/2024)
Analysis of Hir Notice that for any unit norm e R it follows that
T
3
Tt
Φt
H
V TÝ + =0(
T
Øt
v Te + 2 (0*)
00
2
Φt
sup
c5 + 27(0*
[=[7]
Φ1 2
n
sup
H
2 V C + 27 20*)
[E|2]
01 HT
M
Φ: 2
Tt
sup
Hr
v T + =0()0)
EE[T]
01 H.
(
Tt
w
sup
HTU.
2 27 20*)))
[
1 + wi
where (a) uses Hyp s H.
for all te [7] and (b) follows from
Φ: 2
T.
H d. 2
Φ:
w
w
H
w
oz
1 o
01
+ w
1 + w
By the arbitrariness v, we know that
Tt
W
HAT 3
sup
(C.7)
V Tē 2 (0*)
:E[7] 1 1 mi
Let X, +=(+=)(0*)) It obvious that 0 & X, & 1. We then focus on the concentration of D X To
that end, we need a variance-aware Bernstein's inequality Lemma G.2 for martingales. Lemma G.2 implies that with probability at least Tr, we have
T
T
T Var Va log + 5 5log
2KT2
2KT
Σ
X.
&
E,
X.
where K ;= 1 + 12 V1 and 2 is an upper bound satisfying MT B[X < V2
First notice that for any t > 1, we have
=²((0))
E,X, 1 - E,
E,
7 + 27 00*)
V
+ 20 ( + 0²) + +
(C.8)
1
6²
6²
w
E2 &
&
277
277
2T
1 + w
which implies that
T
82 3
82 T
xbb
E,X,
Σ
min
2T
+ w
25
To
where the last inequality uses Lemma G.5 and thus
T
T
2
TL
min(1, 1, w = min
1.
2d
1+ doo2
= 2k.
az
min
26

---

Published in Transactions on Machine Learning Research (April/202))
Secondly, we have
2
E
2
(0*)
b²
Var[X & E[ < E. 1
T? + (0
4
=00)
where (+) uses
7t 2/ (04)
which is also used in equation C.8. As a result, we have
2 o7 (00)
Rb²
[ar(X
w
2T
Once requiring T8 3 2nl?, have Σ Var (a. & 1 and thus we can set V 1 and obtain K 1.
Putting them together, if Tō >
2nh²
with probability at least 1 1- we have
log 2
kb
3b
27 K log
27
Σ X
5
+ 5 log 8
70
70
t=1
1
2T
3
27
27
log
log
+ 5 log
2
6
8
2T
$loog
(C.9)
12c
where the last equation is due to the definition of cu. Finally, taking a union bound for the last inequality from T to and using the fact that D 6- < 2, we have Σ X₂ & La for all T > 1 with probability
12c3
at least 1 1 25.
On the other hand, by the choice of as, we have of 3
10 (00l?r_ n 1 2/
which implics
w sup wi & co
sup (E[T]
(C.10)
+ w
TE[T]
Plugging equation C.9 and equation C.10 into equation C.7, have
1 HIT 1 4
Hr.
(C.11)
Analysis of H₂r
We first notice that
Pt
Tt
< 3
20)
T 20²00
TH + (0
/ (0))
3T:
(0) - =0{()))
(C.12)
Vo.² + 27
-( + 2
(**) / + (0) + T. + (0*)
Notice that (0) = 0 + 0
0*). then follows that for any c >>>
|+ 1 =1(0') (1+c)
0 0*
Φ 0 0*
=0(0) & 1 (0) + c1+
By discussing which is larger between zi((0) and 20*), we have
(²]( - =((00) & 1 min =(0)) + (1 +
Φ:
2
0*
(C.13)
0,
27

---

Published in Transactions on Machine Learning Research (April/2024)
Plugging equation C.13 into equation C.12, we have that
T1
T5
VT8 + +22(()
T + zi (0*)
3T:
min (0) =0(0))
3(1 + c)
Φ
2
0"
2 7
+ min (2](()
(0*)
2 2
7 min (=)(0),=(00))
2T
at
3
3(1 +c) / Φ:
(a)
3
+
0 0*
20
2T
01
2c
7
of
3
6(1 + c)
1.2 B2
(6)
3
6(1 +
d)
+
+
(C.14)
2c
TO
o
2c
T
where (a) uses
0+
(10) + |0+1 & BB due to | & L and 0, 0 E Ball and (b) uses
o. H. / dà which implies of > 1f
the following result. By the definition of or, we have oR vLB
As result of equation C.14, by definition of H3,, we have
(3 + 6(1 + c)ad d 2c
Σ 1-1
T
Φ Φ
H2r
(C.15)
oz
Putting pieces together Plugging equation C.11 and equation C.15 into equation C.6, with probability at least 1 1- 8, for any T b and for all e Balla B), we have
3
6(1 + c)
T T
Φ
(2LT(0) 2 HT HT
4
2c
0z
31
(1- 1
3
6(1 + c) d
T
Φ Φ
- I +
4
4
2c
Notice that c1 = 42-log 24
If we set c and
ToV
2T 5
2 maxf v 2kb, d), we have
3
6(1 + c)ard
max
$ 4
2c.
As a result, we have
31
T
Φ Φ z
1
LL 2
I
Hr.
ot oz
C.3 Proof of Lemma 2.2
For simplicity, we denote 2 = (00) for short. By triangle inequality, we have
T
[[*)((*)| म.े
||0*| H
T+
Φ
(2
2
o
H
T
|X0*
Σ
T2
Φ
(C.16)
H
dd
For the residual term ||0* H,,¹ Notice that H Al and thus H X La. Therefore, ||0* H & VBB
28

---

Published in Transactions on Machine Learning Research (April/2024)
For the self-normalized term |drl| matrix identity implies that
The fact that Hr HT-1 +
rrot
together with the Woodbury
of
H HT-
H 1 of + w
where w
Φ H.
T-1 Φ
T
(C.17)
o
OT
Hr
Clearly, wr is Fr 1 -measurable and thus is predictable. By definition of dr and equation C.17,
|d |drl H7
d
T
ΦT
Hrp
dr-1+
ΦT
V T
(T))
OT
V + (+
OT
1
d dT H-1
= =|dT-1
12
Hy=
1 1 wij
OT
2T
dj. T-1
HT ΦT
(27)
Φ H ΦT
+
v 7 + (27)²
OT
T
(27) )
0T
dr
2
2T
T
#
d= H
ΦT
(T))
#1 2
H T
ΦT
(C.18)
M
T
#
OT
o
12
For I, by equation C.17, we have
2Tr
1
H HT- Φ1 1T-010HH T-1
11 = v J + (2+) OT
dl
H
ΦT
o7 + w
2
1
d H ΦT
V / + (z+)
1 1+ /
σT
For 12, we have
T222)22
HT OT
12 7 (=
2
1 T
H H T-1
H H
7 (27)) OT
of (1 + w
7
WT
(
WT
1 + w
w
1+ w
Using the equations for 11, 12 and iterating equation C.18, we have
2 |drl
T
T
2
d.
T 72(2))
wf
(C.19)
H
V
T + (2
1+ wi
de
7 +
(2+)
1+ m
Recall that
TI2
== =d 1+
dlo² A
Lemma C.1. Assume [[(=)){[F--1] & 6² for all to 1. Let A, denotes the event where | H, & an for all n E [4]. With probability at least 6, we have for all T r>a 1,
Σ
T
2T,21 1A
d H Φe < 4 max O4 [T[
nbb 4m
+ by log
21
2To
log
21
+ (2))2)1/2 w7
3
8
29

---

Published in Transactions on Machine Learning Research (April/2024)
Lemma C.2. Assume [[ & 62 for all t > 1. For fixed > 0, with probability at least 1 - 6, the follow inequality uniformly holds for all 7 > 1,
7 (2)) Σ 1=
wi w
27
/2 v
oop voylog
+ (2
For any T > 1, we define
kb²
27
27
RT 8
+ by k: log To log
(C.20)
To
As result of Lemma C.1 and Lemma C.2, with probability at least 1 22, for all T 0,5
T Σ
2T 1 A
1
d H
oT and 2
Σ
T T/
$
at
(C.21)
w/ dt
78 (zt
w
Let B denote the event that the conditions in equation C.21 hold for T 2 0. By Lemma C.1 and Lemma C.2, know that (PB) 2 1 22.. We now introduce new event C' that is defined by
C: | |drller " & ar, for all T T20 0) = 5 A
t=0
In the following, will show that B s C. by mathematical induction. As result, it follows that
P(C) > P(B)= 1 8. 8.
Finally, we use mathematical induction to show that if B is true, then C must be true, i.e., all A, is true for all t l 0 on the condition that the last inequalities equation C.21 are valid for all T' > O. When t = 0, Ao is true by definition. Suppose that at iteration T - 1, for all 0 < t & T - 1, the event A, is truc, then we are going to show that Ar is also true. By comparing the definition of Ar and Ar-1, we only need to show that dd | & or which equivalent to |drl? nr a². It follows due to the following inequality
19.19)
72
d H
T
of(2))2
wf 1+ w
|d 1
2 H
VT + (zx)² 1 + W
+
T A:-1
2 d_ H
0:
T
T2(2))²
wf
+
7. + (2t))
1 1w
0t
7 +
(*+)
1+
M3
22
2
2
where (a) uses the condition that all A, is true for all 0 < 1 7- and (b) uses the conditions equation C.21. As a result, we can conclude that all (Areso is true and thus ||r] H. & ar for all T >
C.4 Proof of Lemma C.1
Proof of Lemma C.1. We will make use of the Freedman inequality Lemma G.1 to prove our result. Recall -.11,1 2 d,_, , with the event A defined in the lemma. For
that T: = To VI+wg Set Ye V L+u?
n
simplicity, we denote X, = Y, - EE- Notice that
d H,
Φ
Am-
< Idd-LAAma
$ 14-1
σi
Note that it's easy to verify that the following inequalities are when
30

---

Published in Transactions on Machine Learning Research (April/202)
As result, we have
2wh Vil 7:0--1
& 2
and thus
[x,
|
[[[T] 47004-1-
1 i
We also find that
(1 2wi
T²(=;²²
E F[
&
B[ F--1
E
i w
||de-11? mT!1 1
7, + (2,) Fi-1
2w
ai & min(1, 2w0 2 & 4 min w/ Ja
+ wi/
where (a) uses E(X- - EX)² < EX² for any random variable X and (b) uses E| & b²ož due to
E[(=)) [1-11 < b².
Notice that 10i1/a, & mill/mii & L/omin- Then by Lemma G.5, we have
I
min(1, w/} & 2d log 1+ TL²
Σ
= 2k.
(C.22)
dAo min
Hence, by equation C.22,
T Σ
T
E[1 Fi-1l 11
max min w ? <
min w )
a rE[2']
TL2
max oj sab² log [E[T]
1
8kb²
max o7 [e[2]
doo iuin
On the other hand, using E[2 F
0 we have
T
(2t)²²
6a
E
F
E
1
24 F
< E
F -1
$
+
(=t)²
V
(2+)2
2T.
2T.
which implies
T
T 6²
6² T
Σ
Wt
Σ
w
O't-1 E
at-1
2T:
+ wi
2TO
1 + wi
6a T
kb²
< sup ai
min (1, w2) < sup aq
re
[=(7]
2T
te [T]
By Freedman inequality in Lemma G.1, it follows that for a given T and To, with probability 1 5
27
272
2no
27
Ye
+ 4 max a+
by k: log
log
EE|T
8
kb²
2T
2To log
27
max
+ by k klo
[E[T]
4To
8
Finally, taking a union bound for the last inequality from T to and using the fact that Σ t- < completes the proof.
7
31

---

Published in Transactions on Machine Learning Research (April/202)
C.5 Proof of Lemma C.2
Proof of Lemma C.2. Set Y xf w and X; Y, - - Recall that 7 To /l-w2, Clearly,
+ Ttus
have (Yl & r w that
I+w? T and thus |x+] 1 [[Y:|FF--]]]
max T8. We also find
W
T2(
2
E|
EY
E
Fi
1+ w
Tp + (zt)²
wi
(b)
& 10 wi
[[(
E
w
w
where (a) uses E(X EX)² & EX² for any random variable X and (b) uses B[ & b due to [[ & v². Hence, by equation C.22, we have
E[ & 2
w +
$ To
T
min{1, wi < 2NT/l?
1
2
On the other hand,
Σ
T
B[Y
F-11
Σ
W
イ²(2)²²
Ft-1
1 + 3
.. + (2
T
w
T
<
Σ
min (1, w2]b² < 2xb²
+
w
By Lemma G.1, follows that with probability
27
T
T F[ + 2Toby log
27
2T
2T
Σ
Y
<
+
log
8
8
for given T and To. Putting all pieces together, it follows that with probability
272
T Y,
27 V2xb + Top log 8
Σ
Finally, taking union bound for the last inequality from T to and using the fact that E 1-2 < completes the proof.
7
D Proof of Theorem 3.1
Measurability Let Fi. denote the o-field generated by all random variables up to and including the h-th step and k-th episode. More specifically, let J = ((i.j) i [H], E [k-1]] 1] or i [h], k} denote the set of index pairs up to and including the h-th step and k-th episode and then Fr. (UG.)e (si. ( Dt.j, (is)
We make convention that Fo, FHH From algorithm, know that (i) Q vk at E FH for any Q E (Q, Q.Q.QQ and V E (V, V.V. V. V), and (ii)
1h-1A, Or.k, k/, Oh,k: Un Jn.k, Pr.k. Dh,k Fh.k, Whike Wh.kk Thikk Fr.ks HA.k, H E Fu.k-
32

---

Published in Transactions on Machine Learning Research (April/202) 2024)
D.1 High- Prob-Probabllity Events
Let = dlog (1
K
).
We first introduce the following high-probability events.
1. We define 2ạ² as the event that the following incqualitios hold for all E [H] and & e
1h E RU,E= == {l & W ||bbn - 1 & BRR
where
VRORR
2HK
BR 128
+ vd
log
+ 5VAW.
miin
8
2. We define Bo the event that the following inequalities hold for all h [H] and A E [K],
max ||cuet
1n h+1
< So,
Hn,e-1)
1 ph,k 1))kk-)( / h+11 12
HBo.
H1,a-1
where
471
2H
Bu
H : + log
+ 3v 1.3vxD dxH
mmin
5
8LK
32B² K2
K
4 = max
log 1+
log 1+
log
1+
(D.1)
XHV min
Vd2 min
oo min
Here we choose B > 3(3R + Bv) and L W + H
4K X
3. We define BR as the event that the following inequalities hold for all E [H]] and k [K]U[O),
0% E RA, == {10) < W 10n, 0% FI..k < BRR)
P - an,k) & RA, = RRe 1R A. + 271Bn Hiikk HT
(A.8)
where
2HK²
8R 128(V vay log 8
+ +VVAW.
4. We define By as the event such that for all episode &e [K], all stages h < 1 & H,
||uE - ( V H.N (Hă p Vi++1
max
< Bv.
(D.2)
HAr
where
By O OVaii vdxH)
4HK2
4T
8 8vd
41 max la, log
.log
1+
log
1+
(D.3)
Omin
oo
For simplicity, we further define By = Bi.
Our ultimate goal is to show By holds with high probability, target used in previous work (Hu et al., 2022; He el al., 2022). More specifically, we first obtain coarse confidence sets for all parameters in the sense that the confidence radius (that is 3r² and 36) is loose. In our analysis, Brz n B, serves as the 'coarse' event where the concentration results hold with larger confidence radius, and BR Bv serves as 'refined' event where the confidence radius (that is AR and (v) much tighter. Our first result is that B B, with high probability as shown in Lemma D.1 and D.2. Their proofs collected in Appendix F.1 and F.2.
B, holds
33

---

Published in Transactions on Machine Learning Research (April/202)
Lemma D.1. If we set
2nn Ra
2vd
2H log 8
To = max
(D.4)
Jmin
the event R holds with probability at least 1 - 46.
Lemma D.2. The event By holds with probability least 33.
These coarse confidence sets are then used to estimate variance for the reward functions and value functions. A key step is to show the adapted variance Th, 8 are indeed upper bounds of these variances (that is [V ah,a) + 1 (n,)) for all h [H]. A frequently used argument backward induction. That is given the estimation is optimistic at the stage h + 1, we then show the optimistic estimation is maintained at the stage h. Induction over the stage h would complete the proof. The following lemma provides estimation error bounds for [V (n,,R)(Sn,, an,e) and shows that the event BR holds with high probabilily. Its proof is deferred in Appendix F.4.
Lemma D.3. If set
2HK² Vlog
max 2xx 2vd/
(D.5)
8
the event BR holds with probability at least 86.
In Lemma D.4, we show that our constructed value functions V and V are indoed optimistic and pessimistic estimators of the true value functions under the event defined before. Its proof is deferred in Appendix F.5. Lemma D.4 (Optimism and pessimism). For any he E [H], if BR M B, holds, for any ke E [K]U(0),
V+( () Ox)
With the established optimism and pessimism, we can establish upper bounds for the estimation errors of the three terms, namely [V 111411shhhh (h,,), V. h+1 Vi++1) (sh, an,k), and VA(Vk h+1 Vi++1) (sn,ks an,k) in the following lemmas. Their proofs are deferred in Appendix F.6 and F.7. Lemma D.5. On the event Bu B4+1, it follows that for all lo E [K]
[aVVe Var h+1 (D0,R) an.x) & Un,
where
Un min {v², 117330 I (bnulle Hotk. + 474 4H- Pn. V (sn,,,
(A.9)
with (-),,))), WTTA-10(s,0)
Lemma D.6. On the event Bo n BR n Bu+1, it follows that for all k k K
max V
vitta) (sn.g, an.)) Vu Vitta) (snssan))) & Ens
where
En. min (22 27. - H. Pno (V h+1 Vi+ta (sn,)
(A.7)
with (-))(1),
())
With the last four lemmas, V 1+1 at stage h. Therefore, by the backward induction, we can prove the following lemma whose proof is in Appendix F.8.
easily prove dh, indeed serves upper bound of the true variance of
Lemma D.7. On the event Bo BR, the event By holds with probability least 1 - 25.
34

---

Published in Transactions on Machine Learning Research (April/202))
D.2 Regret Analysis
In the previous subsection, we know that with probability at least 1 - 176, the event By n Bn holds. Based on Lemma D.4, the optimism implies that
Reg(K)= E(r viT)(ssN)) & Σ (V (11))
We then relate the suboptimality gap [V V1th) to the term Σ Σ & H
Lemma D.8. We emphasize that the bound Lemma D.8 is much finer than previous bounds (e.g.,
Lemma B.1 in (He et al., 2022)) in the sense that the rest term is O(H)) instead of previous Ö(vHKH). This is because
We first adopt a varianco-aware Bernstein's inoquality to relate [ 17 (81,)) with a sum of martingale differences. In particular, we show that with high probability,
K Σ (v VT-
H
XA.N + 481 ΦN,N NT.
where {Nn,khheem is martingale difference sequence define by
XA.a == Pn(V244 ( an.a) (V - Vi (SN+1R).
The variance-aware Bernstein's inequality implies that with high probability,
K
H H
K
Σ
Σ
X
& Ō(1)
ΣVΣ
Σ
Σ
PA(Vh+
V (Sn. kn Õ(H).
h+1
We then use recursion argument to simplify the variance term above. More specifically, we show that with high probability,
PR Pa(V h+1 VrHH) & O(H)
H
V. (Vn.)) ah,kk h+1
h- h-1
K H
+ O(H3)
D H + +
We decouple the self-dependence on ΣK DH E PR(VA4I
V ( an.k) using this incquality
h+1
that 2(a² 62) for any 1
Combining the two steps, we then complete the proof of Lemma D.8. The detailed proof deferred to Appendix F.9.
In contrast, previous work directly applies Azuma-Hoeflding inequality to analyze the concentration of -V so that I E Xn. < &Ö(HHHH), which inevitably introduces the additional Ō(VK) dependence.
Lemma D.8 (Suboptimality gap). With probability at least 1- 8, on the event BR ABv, follows that
K
1 H + 38HH log 4(log, HK]
(81.a) & 63
and
H
K
H
4oog, HK)
PA
h+1 - V ap,s) < 8HB
Σ
Non H + 3881 2 log
35

---

Published in Transactions on Machine Learning Research (April/2024
Using similar argument, provide finer bound for the gap between optimistic and pessimistic value functions _k=1 Σ (A h+1 ( (n,a) in Lomma D.9. Its proof is provided in Appendix F.10. Lemma D.9 (Gap between optimistic and pessimistic value functions). With probability at least 1 - 6, on
the event By ABR. it follows that
K
H
K
H
4flog, HK]
Σ
Σ
Pv A+1 - ( an,)) & 12H3
Σ
Σ h=1
+ H log
The following issue is to upper bound the term - >
I M Since the estimation of reward motivated to analyze them simultaneously
variance concerns the other term Σ Σ 1 2n. H
via Σ - bi.k where b = max { |I pr @n p. }.
Previous works (Hu et al., 2022; Hc
et al., 2022) mainly use Canchy-Schware Schwarz incquality to analyze it and obtain
k whe)) = )
b E
Σ Σ
T
Σ Σ max u
VdH
Σ Σ A
o
R-1A-1
1=1
where the last equality uses the elliptical potential lemmas in Lemma G.5. A standard analysis of the law of total variation would imply v E Σ ohe = O(vH²K). However, this result doesn't satisfy our target for two reasons. First, due to the use of adaptive Huber regression, our definition of Th, more complicated than previous algorithms. We need more elaborate analysis to handle the additional terms in the definition of ks, Second, the previous result considers the worst-case scenario, while our target is to provide finer variance-aware regret. Therefore, it is imperative to provide finer bound for the sum of bonuses > E bn.A- We did it in Lemma D.10.
Lemma D.10 (Sum of bonuses). Set X æ=#w=. Let An denote the intersection event of Lemma D.8 and D.9. With probability at least 1 - 26, on the event BR n By nB. Bg² A.o,, we have
K
b =3 -Ō 6(Va + K.5.5. o min +
g2.5, + Hal
m
H (
Ha oR Hd..)).
where Õ(.) ignores constant factors and logarithmic dependence.
We emphasize that Lemma D.10 is perhaps the most technical lemma in our paper. To address the difficulty mentioned earlier, we divide the full index set I == [A] [K] into three disjoint subsets I U, Te according to which value Th takes (given σb, is the maximum value among five quantities). For those indexes in Ii where the bomuses are small enough, we still use the Cauchy-Schwarz incquality to bound EihAees bn. & Ö (vdH. V o..)) This sum-of-squared bonus quantity involves E(n,k)ez Er, and EinAyez Jn.k which we then pay additional efforts to analyze. For those indexes in T2 or Ja where the bomuses are relatively large, we directly analyze E(t,k)e)> b Thanks to the particular structure, E(nK)essuus b contributes to the non-leading term in the final bound. Putting pieces together, we complete the proof. A formal proof can be found in Appendix F.11.
At the end of the subsection, we summarize the proof in a few lines.
K E (81,))
(a)
K
Reg( K) =
Σ
V
VITA
(81.a)
h-1
(8)
K H
4 4|log, HK)
<
33
Σ
Σ
H
+ +8//H log
8
kmlh
36

---

Published in Transactions on Machine Learning Research (April/2024)
(d)
K
H
4flog, HK]
$
33
bb. + 38
H25 Hd
4 dv dvHKK* + HaK Amin
+ HHHHH Hdon + Hd!
muin
where (a) follows from the optimism result in Lemma D.4, (b) follows from the suboptimality gap result in Lemma D.8, (c) uses bb.k = max {1 11 Hilk pl ) and (d) follows from sum-of-bonus result in
Lemma D.10 and B 3R By ((vd).
E
Proof of Theorem 3.2
Proof of Theorem 3.2. We consider the two complexities respectively.
Space Complexity First, to perform AdaOFUL, VARA needs to store all seen rewards and feature vectors (i.e., Φ1.k: Φn,k), which is required by all RL/bandit algorithms robust heavy-tailed rewards (Shao et al., 2018; Xue et al., 2021; Zhuang & Sui, 2021). AdaOFUL also keeps all robustification parameters Th h Tt. then incurs O(Hdd) space storage in total.
Second, due to the rare-switching technique, one can show that Qn & (or 2+)) is the minimum (or maximum) of at most O(HH) temporary optimistic (or pessimistic) functions (see Lemma G.7). It means that we need to store at most OdHH) different versions of 0p, Mh Vi h+1 HA,K-I' 's. This incurs O H²) space cost.
Last, for all (h, E [H] x [K], we need to trace ( a)a to evaluate each pa, V = - H h,k Ei=1 hn on (sh+tl)))) for Ve (V) " atal v vh+th, which takes O(d[A(HK) space.
To sum VARA takes H2 + d(HHK) space.
Computational Complexity First, we use the Nesterov accelcrated method to compute each 0 Since
the loss function in equation A.1 is X-strongly convex and (x + K mmn
-smooth, the computational cost for cach
On. is ① (d/1+
K M(
Ö(mxx(d, H -/88 and the total cost is
We emphasize that we don't need to compute On, exactly. suffices to terminate at a solution θz once its accuracy satisfies | On,k Hn, & vd. The iteration complexity is proportional to the root of the conditional number, i.e., Ó (mxxx(1, d d 3/44). Since each iteration takes O(d) operation, the computation complexity is (maxx(d, g3/4))
Second, each time when updating the value function, we take the minimum over at most Ö(dH) quadratic functions. Morcover, the Sherman-Morrionn formula computes H and its products with any vectors, which takes ((d)) operations. As a result, it needs Ö(d H) to evaluate the updated (s,(s, for given pair (s, a). Hence, computing Qn.x(Sn,es);, choosing an,k = argmax, Qn. a), and estimating the variance Th, lead to O({ computational complexity for each episode.
Last, note W V H. (3 for any value function V(-). If remains unchanged, we only need to compute the new term 0 Φn. (()+11,), which has ((dHH|)) complexity each time. Tf V changes to V', we need to recalculate Ph,, V', which has H( {|(K) complexity each time. Combining the computational complexity for all horizons and noticing that the number of episodes that trigger the updating criterion is at most Óddf), VARA has a running time of A(HH + (H H 3//4 K3/4)). In terms of the dependence on K, it is slightly worse than LSVI-UCB++3 ((d*) since the adaptive Huber regression docsn't 't have a closed-form solution, but is better than LSVI-UCB's Ō(d])A)HK due the rare-switching mechanism.
37

---

Published in Transactions on Machine Learning Research (April/2024) 2024)
F Omitted lemmas in Section D
F.1 Proof of Lemma D.1
Proof of Lemma D.1. The proof idea of Lemma D.1 is similar to that of Theorem 2.1 except for the following changes. First, 01, = 0( (n.k) E I is instead the feature vector. Second, in the particular setting, we should respectively replace I., B, T, 5 therein with 1, W, K, 6/H defined here and redefine cD, C1 as co respectively. Third, by the choice of oh, we have on (var + +Hd2.5 b 42 24
6//3 log 20K2 C1 W ved @n, ( H which implies that w
Tht & cdd. Similarly, due to o = co @0 H have
h < c.. Last, for simplicity, we define Eh,k ri. (ib...0 and gn = o(Fr U (Sh (n,))). Then,
we have EN, Frus E[EN.&I9H,Al = 0 and VarfEna19%,Al < RR2 = b². Theorem 2.1 concerns the case where b = 1, however, its proof considers the general case where can be arbitrary. As a result, by a similar argument in Appendix C (which is doable due the four conditions mentioned above), once setting Toy/log log 2HK2 = max (v2nd, 2/ with probability at least. 1 - -3, we have for all h [M] and [K],
Amin
[2bn,
4 Hi.k & Bre, that the event Br holds.
F.2 Proof of Lemma D.2
We will make use of the following general results frequently. The proof is quite standard (Jin et al., 2020b; Wagenmaker et al., 2022a; Hu et al., 2022). We provide proof in Appendix F.3 for completeness. Lemma F.1. Fix any h [H]. Consider a specific value function f(-) which satisfies
(i) supses [f(s) & Co;
(ii) f V where V is class of functions with (())a)) the e-covering number of V with respective to the distance dist(f, f') == sup.es [f(s) [s))
We assume there exists a deterministic C, > and An, (which is Fu.a-measurablee such that Ai.k E {oR > (Sn,) //,) for all ee [K]. Let Pa,k be defined equation A.2 and dh,k, H be defined in our algorithm. Under any of the following conditions, with probability at least 8/ H, follows for all & [K],
1 iu: 11 fll & $
(F.1)
(i) If f()) is deterministic function and NKELK] An,k is true, equation F.1 holds with
K oh
4HK²
8Co log
4HK²
8Cog (ii) TI f(+) is random function and [ An, is true, equation F.1 holds with
3 3=8Cag
@ dlog
1+
log
8 + vddCo.
ds
d H
K 1+
4HK2N
8C, log
4HK2N,
B = B=8Co &Cog dlog
log
+ 3 ddCCoo
o dd
d2.5 HH
8
where No (V(V, and min {
Coo
XCavd 2 Ke
(ii) If f(+) is a random function, equation F.1 holds with
2Co B Owin / ddoo
K
N1 log 8
1+
3VdXCa
dA
38

---

Published in Transactions on Machine Learning Research (April/202)
where N1 [W(V, and E1 ACoyd o min
Using the last item suffices to prove Lemma D.2.
Proof of Lemma D.2. Let V+ denote the class of optimistic value functions mapping from to R with the parametric form given in equation G.1 and V the class of pessimistic value functions with the parametric form given in equation G.2. By Lemma G.8 and Lemma G.7,
log. log.V(V't. .E) & dlog (1+
4L = + dl 1+
dlog log 1+ ?d
(F.2)
A
where B 30 and W + H
Let. f f-
h+1- One can find that f e Vj with parameter L= W KH..
To plug in Lemma F.1,
Aarii
we first specify the parameters defined therein. We have |f < Co = H and E AHy o By equation F.2, it follows that
K min
log. log.N(V,,a0 ,1)
dlog
1+
4LK
)
+ d &olog (1
KB vd23H2o4 min
]
dH loga 1
K oo
XHv do? min
2
d Hig
3d
Hig
log2
By the third condition of Lemma F.1, with probability at least. 1
5 2
(1 - &h.k Viinn
& 30 for
all h e [K]. Similarly, we can also show that with probability at least 1 So for all & e [K]. Putting them together finishes the proof.
8
| ph, V <
2H
(ii) The analysis on Vhn h+1 is similar to (i).
(iii) The analysis (V] h+11 12 is similar to (i) except for the following two changes. First, Co H2 and Et XH2 Vd o min. Second, with 2 (f2 f E V*,, have (V [V DV+12 and
(a) log NggN((PTP & lov+
E & lov
- 2 < 3d Hig
2H
Here (a) uses the fact that the cover of V is a cover of [V+]² (which is also supported by Lemina G.9).
27
F.3 Proof of Lemma F.1
Proof of Lemma F.1. Since the case of k = 0 is trivial, we focus on ke [K]. By definition,
Ph.k H
1 Dh. 6(sh415)
H
-2 hhe Tis Φn. (ØT En.j)
= - AH H
2 tb Eliji
39

---

Published in Transactions on Machine Learning Research (April/202))
By the triangle inequality, it follows that
111 - Hl.
< Xl H f Hua + H Σ
Tne
Hu.k
=Nluffll +
Σ nn ch
H
<
vViCCo +
Σ
2 hh.
H
where the last inequality uses | vdCo.
Assume f(-) is a deterministic function. To evoke Lemma G.3, we set 9 = Fh.. Dy = one = The LAns and Z₁ XI دドー o on HA,K- Here 1 is the indicator function of the event.
A.
Clearly Dj E G3 [[, = 0 and |[nj|,,] & Ca. We also have x,ره & T Insl < 2C and 2Cg [x 2, Wh.j. As a result, Iy min |1, - & 2C who & HalS where the last inequality uses ane
The 2 Ho.. H H.. H -- (which is equivalent to why & HH2 By Lemma Lemma G.3, it follows
on.s
that with probability
for all E [K].
h
Σ
ha n ET flnns
a f
H
2
K
4HK²
8C
4HK²
< 8C dlog
1+
log
log
dA
8
Hd..5
1
Finally, on the event Nke[K]- An,k we will have all the indicator functions equal to one.
If f() is random function, we would use covering argument to handle the possible correlation between f(-) and history data, which would, unfortunately, enlarge B.
Denote the nn-net of V by N(V, where Eo min { Co. 2C,vd d exists f E 8(V, such that |lf fllo sup [f()) f(()] & co. Then,
min)
Hence, for any f V, there
k
k
Σ
h.j Φ
h f
0
2 h.j
S ETTs
+
Σ
0 hij
S (f
H 1
Hn.
H
(n)
(IT)
For the term (II), due to |onnl 1 and 15 fI < |Enillilss fl & 250, we have
k
2K
Σ
$ 2VV
h.
min VÀ
Hr
and) Since the definition of Va. For the term (I), we define Vi. = { E :VVEV:CCoh. > (Vnf')
involves only Th,k, kh an. E Fh for any fixed function E V, 1 Lyeen is measuuaareeble. On the event An, by definition of Eo. co.
(VnD(sL (n.k) & 2(Vn/)(sn, an.)) 2(Vn(J- (sn,, & 2C2o 20 4C
40

---

Published in Transactions on Machine Learning Research (April/2024)
Hence, A S foh (Wnf) (. /C2 In the following, we will evoke Lemma G.3 to analyze the term (I). For any fixed f E V, we set 9, - Fh.j.. Rj ni T JJj = Th rev, and Z AI Σj=1 oh Sn H Moreover, due to the choice of oh.j: it follows that
= (3f N(V, D..a) for all & E [K].
M min (1, (1,103512 (,,
Co Ohi
tb.i Thi
bu.i & Co
Co 82.6
H
Thij
By Lemma G.3 and the union bound, it follows that with probability 1 H for all E [K],
2 h.s En
sup (eN((Vee)
K
4HKKNo
SCo
4H 4H
$ 8 dlog (1
log
log
o dd
5
2 HH
where No IW(V,
As result, we know that - o sevi,, H
is no more than the RHS of the last inequality.
On the event nkacKy As, we have f E [kepK] Va. and thus all the indicator functions equal to one, completing the proof.
The proof is almost similar to the second item except that we use Lemma G.4 to analyze the term (1). Noticing we also have 17 = & 2Ca. By Lemma G.4 and the union bound, it follows that with probability 1 3; for all k [K],
Omiu
2Co
)
K
Ni 8
sup ('N((V)
Σ
2 his E reva
dloog
1+
+ log
Miin
Pay attention that here don't utilize the variance information that we change No [NV(V, to Ni = s(V,si) and don't require Nie[K] An, is true.
F.4 Proof of Lemma D.3
Proof of Lemma D.3. The proof idea of Lemma D.3 is similar to that of Lemma D.1 except that we pay more attention to the reward variance.
Given that Bg holds, we have 4b e RA, for all h e [H] and & [K]U[0].
We will prove the lemma by induction over k. When 0, we have 0n,0 = 0, H = XI and |0,,0 0% H
ex|0, & VAW & Ba for all h e [H. If suppose 0% Ray holds for all h e [H] and j e [A: 11. are
going to prove 0% RAck uniformly for h E [H]. The first thing we will show is
The 1VA Ri an.)) + Rhg for all h [H] and j e [b]]
(F.3)
Notice that [V (s k, an = (Zr,k. +tt (Rh,,, 0, We then have for all h [H]. [k].
[ Rr - -n an.i)l
(pn.j. - (Zn.j) 15t) + (Øn.s 0/)² - (Bhn. 0n.
K KZn. aba.k-1 *b 27d KØnnk, 01.j11- -0%)
41

---

Published in Transactions on Machine Learning Research (April/2024)
< |لا i H 11b1..11 1/111 H + 22 H 10 0% H
< 3ra Φins H + 2H,BBll $1.g Hnij- = Rh.,j
where the last inequality uses the hypothesis and the condition that Bya holds. As a result, we establish equa- tion F.3.
Let Ghnd oFFn-1.s U (8h...ah.))) One can show that both R and The are me.-mmasuae As result, the event Ens == ooos 2 1V Ro anz)) is also may-mmasuaable. On the event B it is obvious that Ahetan Ozepk] Eni is true since equation F.3 is truc.
U
On the other hand, set Enj This -dh... Len, the standardized reward. We then have En.J E Fhijt Ch,s
19. 0 and VarlEn,19h..] < 1. We define On,k as the solution of adaptive Huber regression the response (rn,ses,, he[[ and the feature {Øn, (5E We also define HA, as the counterpart matrix of Hi,k obtained by replacing Φb. with Φn.kl We then apply Theorem 2.1 to analyze the
concentration of 0n With probability at least 1 36, it follows that 10 0% H. < BR for all E [H]
and h [K] Because By is true, all indicator functions are equal to one. Therefore, we have 0n.k = On
and H H implying 0% RA, uniformly for h [H].
F.5 Proof of Lemma D.4
Proof of Lemma D.4. By symmelry, we only prove the RHS inequality, or say, the optimism inequality, We
prove it by induction. The statement is true for h == H + 1 since both V+++()) = V (-) = 0 for all k e [K].
Assume the statement is also true for h + 1, implying V (.) & (+) for all & e [K]. We assume there
exists sequence of updating episodes 1 & ki < <...< KNz $ K such that
Q+(,))) = min
( (,..,-).%...-I + MA.k V h+1>> (((((,))) H H .H). sN[NN]
(F.4)
Using (5 (d(s, a), 0% 1 V
h+11 i>s we have for any (s. E S A and k [K],
(b(:,),, 00.0-1111-11- + Ub. h+1 (1 Q%((.))
(.(.))) 0p, (.6,,,)0...111
0 + (o(:.)) p
VK V Vi++ ([(((())))) H
(4) (o(:)). 1,0 - 0% + (6l: ) (MLA-I -0 V + 31
(6) |(((;))
)l H. [- 1100 - 0% H 1aaia-11(M,,A-111 11) v h+1 Ha.k + 3
(c)
[1
20
where (a) uses (Ø(s, a). 1 h+1 V h+1)) = PA PA h+1 - V (s, 2 0 from the hypothesis, (b) follows from
(V
Cauchy-Schwarz inequality and (c) uses 0 0% H (1 14) h+1 Hn Ba By B the event BR Br.
V
As a result, by the last incquality and equation F.4, it follows that for all e [A]. o%(,))) 2%(,,)) > 0. Taking maximum over actions, we have Vh (.) > (-)() for all k [K], which implics the case of h is also true.
F.6 Proof of Lemma D.5
Proof of Lemma D.5. The proof technique has been used in Lemma C.13 in (Hu et al., 2022) and Lemma 7.2 in (He et al., 2022). We include the proof for completeness. By definition,
[Va V 1 an,k) (HEVV 1. (....)) < V h+1 21,b) &b,
42

---

Published in Transactions on Machine Learning Research (April/2024)
[V V h+1l(sn, an,s) iMn.--ilVi h+1l? Sh..-.n-iii- 1)10,1111 (pnn R+1 Dn.
Therefore, it follows that
Vn WiVtt h+1 Vn Vn n+1 (on,e anxe)
VAVA+I A+1 VnVh h+1 (sp, axxx) (s)k)))))) + Vn Vi+t1 - -aV (sn. and))
We then bound the two terms the RHS of the last inequality as follows.
Vn V h+1 &nVh+1 h+1 anx)
( h+ P. Dnnc)) (pn.-IlV*+ 1n.))
+ KuzV v h+ Φnn)) -MInk V h+1 on 1
K(H (n)--1) n+11? )n.n)
+ +HH (uz
V h+t1 Φn,n) (pona- V (n.
(MA,K-1 - p +++
|
+ SH | - 14) V h+1 H
HA
hik
where the second inequality uses the fact that both (1,, V 14 snn)) and (MAR v VitD 1),00 lie between and H. Simílarly, it follows that
Vn W Vn VAVh m+1 (sn,s, an.e)
P 1 an.a) + [En Vitta an..) - [P [P (s an,))
PAI(V N+1 - V/+ Vi++ (V + Vi* (7sn),s and)
+ [PA h+1 PA I h+1 + Pn Priitalllon. an)))
< 47H PN[VV h+1 (3
< 4HH PALV &
h+1 VKttllssh
< 4HH PA [ h+1 Vn II an,k)
+ 44
+ || - v
H
Hn,6-1
where for the third and fourth inequalities we use the optimism and pessimism in Lemma D.4 and the last incquality uses the following result.
(PPaVi+2 h+1 Pr,a V htal(sn, an.x) = K(u) - Mn V NtI 21.4)
< 11 Hii (HAn - M V
h+1 H
A similar inequality can be derived for [P
anw)). Finally, we have
Va Vh+t
Vir h+1
(Sh, on.k))
(Mn.k-1
V V+ 12|
47HP h+1 Vh+r) an,k)
Hh.k-
+ H1 H
(
k+1 H
+ (a 2 k
H
We complete the proof by noting that on the event Bo, we have
max {110 - (b.--1) Ha.k-1 (1 - P (M.--)
& 3o
HA.k-1
43

---

Published in Transactions on Machine Learning Research (April/2024)
(H - -h.x-1) =+11] H
$ H3..
F.7 Proof of Lemma D.6 Proof of Lemma D.6. For any j < h, we have
Va(Vh++ h+1 Vitta) (sh. ah.))
Pn(V h+1 1/ttt)/ (sh..) ah.i)
(b)
H Pa h+1 [h+ti (Sh.j and))
PM h+1 Ei+t1) (8h.; and)
where (a) uses the fact that Var(X) EX² for any random variable X, (b) uses 0 o (h+1() & (++(()) Vh (+)(+) & on the event Bu BB+1 from Lemma D.4, and (c) uses that V 1 V V++(()) and V (1)
(++ by definition. On the other hand, in the event Bo, we have
max $1008 ph. 1 V V Ha.s-1 | 1o.--1 Ha $ So.
As a result,
- Pno) vh-11 (sn.g und) = (ohns (1 - pm (ma--i [PPn-Pn))
< ||ln)|| [1(p) ph. v1) Vitll Boldn.sla
Similarily, we have [PA--PAn - -Prs) Kitza] ann) & Bolloans H Therefore,
VT.(Tha h+1 Vot (snisa an.s)
< H 23 H + [PnS(V - Khtii) (ons,an))) Ens
Repeating the above argument, we have a similar inequality for Vhan due symmetry.
F.8 Proof of Lemma D.7
Proof of Lemma D.7. Due to the backward recursion structure, we will use induction (over horizon h) to prove this lemma. First, equation D.2 true for h = H since v (++((-) = -+) = for all E [K]. Therefore, we have By holds. Assume equation D.2 holds for horizons no smaller than + i.c., Bx+1 holds with h+1 & H. In the following, will show, once Ba+1 n Bo holds, B, holds with probability at least than 1- 25 Repeating the argument, we have, given Bи BB. holds, with probability at least 1 1- 1-25, B 0 Bu holds. Hence, P(Bon Bi) s 1 58.
Note that
max (lui Mh.k-1) V
| ph,k
1) Hn,
1 Mh, V H
h+1 H
+ max ( (). b+1
Vi+t1)
(V
h+1
Vieti
Hi.k
Hick
would analyze the two terms in the RHS separately proceed with the proof.
44

---

Published in Transactions on Machine Learning Research (April/2024)
For the first term Since V is deterministic function, apply the first item in Lemma F.1 to bound it. In the following, specify the parameters defined therein. First, we have Co H. and AL. = oh 2 1 and is Fna-mmasurable. By Lemma D.5, on the event Bo n B we have for all e [K], VAV - VAVR. h+1 ] (SL.k (sh.k.nn)) & Un, with Un, defined in equation A.9. Hence, hh [V.
V h+ (sn,, an,a) Un, [V V 1 (n,s) for all & [K], implying ORECK] An, holds under Bo SoBBo AB++ and Ca = 1. By Lemma F.1, with probability at least 1 - H² [( Mh,K- V h+1 Ha.k-1 < 3 for all k [K] with 31 defined in the following. Finally, we simplify 31 as
4HK²
4HK²
B1 = /y dlog
1+
log
+
log
VIXH 5
o dd
5
d2.6
841 < 8vder
+ vdNH & 16V di + VdXH.
For the second term Since both V h+1 V and - - h+1 are FHAA-1-measurall random functions, we apply the second item in Lemma F.1 to analyze the second term. In the following, we specify the parameters defined therein. First, C. H and An, {oh, d (.HE) is Fl.a-measuralle. By Lemma D.6, on the event Bo BBBBnBB B1+1, we have simultancously [Va(Vh+11 Vi ( ah.j) Ens
-
and VA (a - Vitti (sn., an.)) & Ens for all j & & K with En. defined in equation A.7. As a result, for all j & k,
ohi 2 d H. Fng > HH. max [[Va(V h+1 - Vh+1l (on ans); VV - Vieti) (snj.an.))
It implics Co ा
1 and for any j E [k:].
Anj S {ohs C22 max { [Va(V h+1 ViLii (sh.s: an.)); Va(Khtt
Vitta) (sn.j.and))
Finally, with by Lemma G.8 and G.7, the covering entropy for Eo min
{
amin
XHLd o
K mnin
} and the function
V
class to which Vk A41 Vi+i and vk h+1
Vi+ belong is
dlog 1+ (1+ 4L dl log
SvdB2) )
K oo min
log No WW s00)
=
1
dH
dHHlog2 loga
1
Eo
H(P
By Lemma F.1, with probability at least --
H
max {1uz ().a-1)(V h+1
ViLti Har-1
||( 1n.k-11 (V++ Vi+ti) Ha.k-1 $ B2
for all & [K] with Br defined in the following. Finally, we simplify B2 as
B2 = 8
K 1+
HN
8
4Ng
dlog
log
log
dXX
o d)
8
d
8
HH (4++ 0(FH() +
41
8
(4 + H(()) + VXH.
22.
= 0
(Vii 1.5 + + vāž viXH)
o (vdiz + VJXH)
45

---

Published in Transactions on Machine Learning Research (April/2024)
Putting pieces together have shown that given Bb+1 n Bo is true, with probability at least 26, for all h [H] and & [K],
max 111ut pnnk- V h+1 H || pnn 1n H
B1 + B2 =0 - v
Therefore, By = B, holds.
F.9 Proof of Lemma D.8
Proof of Lemma D.8. For given ki let. klast denote the latest update episode before episode k, that is Mast & k Klast 1. By Lemma G.6, due to Hn z Hn and det(Hn Dd 1), it follows that for any E R2,
|| H Minn < 2/|20 H
(F.5)
By definition, (x(:)) & ( 0n + ki Vhunly + Bllo( )l M ha and 0 (s,
(Ø(s, a), 0% V.L Using an, x((s argmax (sn, we then have (V h - V. & (O (sh, an,k)
< (on.ks Or.hrann + Nomn V
Vh#t1 h+11 -00 + μ V 31 (l an,k) H t
(0)
( (On,Amm -1 0%) (1h, (1))) V h+1> (Con (V Ama vitti) + +28l on H
(6)
< 4.3 FT + ( 1h
( h+1 vx+t))>
4.8 4.31 H..k
+ (P h+1 Vi+ti (8n, ak,kk
( 43 13 H
+ (V Whtt V + Xh.k
Here (a) uses equation F.5, (b) uses
KΦn,,, (On, -1
0%) (Wh, 11 K
< 11 taod
11 11 0%, (ph 11) Valaa Ha
< Bl H. -1
$ 2,3 2/31 &1 1,
on Bz Bv, (c) uses ( 14 and (d) uses the notation
Vhhua h+1
hlane
- -V PA h+4 With (sh,) Pa V an.k),
X : : (V (Sp, an.k) (vh+1 (8h+
The last inequality implies
(v* - VV (V Vi (Sn+1Rk) + X + 43 43/
Iterating the above inequality over and using T V = V+++(-) = O, we have
(v: V (SM.))
Σ
Xi,x 43 (3l (1
(F.6)
Therefore, setting and summing equation F.6 over E [K], we have
k
K
Σ
v
(81,))
<
X + 0 H
(F.7)
46

---

Published in Transactions on Machine Learning Research (April/202)
We then need to analyze Σ Σ NA,s- Since 84414 Fisi.-mmeaur,ble, ax { he(H) V FH.k---meaurrabl have X A measurable. We also have B[Xna|FR.e 0, |Xr. & 2H and
h+1 is
E[ Fn.a] & E[(V h+1 v (FN+)))))) HE[V h+1 (
(b) HE h+1 (n HV A+1 V (sh.
where (a) uses VA+
W+t10 < H. and (6) uses the optimism in Lemma D.4. By the variance-aware Freedman incquality in Lemma G.2, with probability at least 1 2 it follows that
X & 33vi.
H Σ R-1h-1
Pa(V h+1
V ash, + 107
(F.8)
4[lgg, HK
where = log
On the other hand, it follows that
K Σ
PA h+1
(sn,) an,k)
Σ VV V (sh,k)
X1,k
k= h=2
k= h=1
(a)
H H
Xi,k + 1
X1,k
k=1 1==2::1
k= h=1
Σ
Σ
(H h 1) Xnax 4,31lon,
X
H
h-2
k- h-1
4H
Xn.abn
where (a) uses equation F.6 and (b) uses the notation bn if h 1; otherwise - h 2 for 2 H.
Clearly, have |bul & H for all h E [H]. By the variance-aware Freedman inequality in Lemma G.2, with probability at least 2, it follows that
H
K
H
ΣΣ K=1A-1
Xnaba
& 3HV...
H
Ph(Vi41 (44h) (A.)) + 10/1
As a result, we have
K
H
PA(V h+1
v (Sn,), an.)) & 3i.
H
( h+1 - Vilk (sn.t
H
+ 4H 3
Φi.k @ H + 10HH4
Using the incquality that x & 2(2² + b²) for any x & / x + b2, we have
K
H
K
PM
A+1
1 (snkk (1.)) &HH3
1= n.-1
+ -38H22H
(F.9)
Putting pieces together, we have
k
V
($1,
equation F.7
&
Σ
K
X + 4.3 4. H,,
hm
47

---

Published in Transactions on Machine Learning Research (April/2024)
H
K
H
equation
43
H +3vl.
H
PA
(VV
an.k) 1074 .2
h+1
k=1h=1
#=
h=1
K
H
equation
43
1 H hi-11
+3v6.
H
8HB
@n.kl 1,
HH + 107
\
k=1
h=1
K
H
63
+ 38HH
H
where the last inoquality uses va+b= E va vb and 2 & b for non-nogative numbers a,
F.10 Proof of Lemma D.9
Proof of Lemma D.9. The proof main idea is similar to that in Lemia D.8. For a given k, let Alast denote the latest update episode before episode k, that is Klast < k < Klast + 1. By definition, Qx(:-) & (<(())), Annn
Phykin V + B) ) pr M and (:,.) >= ()(:;))) Oi.kin Maik Vhh41) Bl( )) H hime
Using
0b. (sh,kk) argmax T% (ones
aeA
we then have
(V' (on,)) & (2" (sn,s:
< (Dh.k Mhl -1 (Vhun ((nr))) + 23 1n.1l Mma
Dn (MA.k-1 11 (V Vhit whurl) + (Di.ke Me h+1 whgr)) + 4 45 hime
(6)
63 6,1 ΦN. H + (shnee 14 blaes blunt))
63 ON. H + +P h+1 (on an.))
63 Φ H (Vh+1 Vh (5 Xn.
Here (a) uses equation F.5, (b)
uses
K (Hi, Mr)
Villnes Mines h+1
Vllun >>l
< snn 1 11 [1 (1)
(V
King
Vllnt Hu.kwat
h+1
x 2 Mina--- & 2.3 2.111
on By BBR (c) uses (Øn.k: 1 (Vhlua Vher)) = PA Wire Vhua (har))s an.)) PA (V - ( an,)), and (d) uses the notation
(V
X = Pa(V h+1 - - - (Vh.1 V (+++1.)))
(F.10)
The last inequality implies
(V* ((((k))) (vh h+ (5441..))) + Xn, + 6:311 H
Iterating the above inequality over h and using (++(() = V V+++(+)) = O, have
( (sn.a) <
Σ
X + 6,3 6,31)%
(F.11)
48

---

Published in Transactions on Machine Learning Research (April/2024)
Using the last incquality, it follows that
K
H
K
H
K "
Σ
Σ
Pa(V
h+1
Vh (5pr) (.),))
Σ
Σ
(V h
(SNa))
+
Σ
Σ
X
k- h-2
K
H
X + 831
+
Σ
X1,
1,
k= h= k=h
k=1 h=1
K
K
H - h 1) Xh,k + +631 Φ1
H h,--1
X1,k
1=1
k=1h=1 h=1
K
H
K H
6H
Σ
Φ
Σ
Σ
Xn,bbn
(F.12)
H
k=1 2
k=1
1-1
where (a) uses equation F.6 and (b) uses the notation bn if h 1; otherwise H h for 2 & & H.
Clearly, we have [ba| & for all 6 [.]].
We then need to analyze E N with XAA' 's defined in equation F.10. Since 8441, is Feeas.-maauurbble V 14 1h+1 is mmasurabaeerallee we have Xa,k is Feesa--maaurable. We also have E FF.N = 0, (&a,al & 27 and
E| F E[(V h+1 ( (a)
HEIVV h+1 19 - (V (S
where (a) uses IV* probability at least 6, it follows that
h+1 1(+)
1() < H. By the variance-aware Freedman inequality in Lemma G.2, with
K
H
K
H
Nn & 3H
H
PA V
( an,k) + 10HH
(F.13)
h+1
where log 4olg HK] As result, plugging equation F.13 into equation F.12, we have
K
H
H PR Vh (Sn.)s an.k)
PA h+1 vh (Sn.) 3H
+ 6H3
Φ H + 10HHL
h=2
Using the inequality that & 2(a² b²) for any & Val b² we have
K H
PA ( h+1 (SN4) < 12HB
Dh. H + +8.
F.11 Proof of Lemma D.10
Proof of Lemma D.10. Recall that bn.k = max 2,, 1e Hr }, Wh.k = o H -
and
Wh.k = oii @h 1 P As result, we have on bb.k max (wn,ks Wh.k)- On the other hand,
W Verd"
o max oim d H. Er, Jn.ks 20
+ HR..H) by.t
(A.5)
49

---

Published in Transactions on Machine Learning Research (April/2024)
Based on what value on takes, compose the full index set I = [H] [K] into three disjoint sets with ties broken arbitrarily:
J1 = [(h,k) = [I] x [K] oh E
{o d ER,Ns Un
J2 (h, k) - H [K] oh. =o 2b
W
J3
(h, [ [ oi Verd
Hdd H) bn.t
For simplicity, we denote 2 ==
bu. 0h,
maxt Whikk Th Therefore,
K H
3
b
Σ
oh, =
(F.14)
(h,,)EZ
1=1 (H,K)
Recall that dloog (1+ ddomio ) we have E(hiee
22 & 4Hx. This is because
K
H
K H
Σ (N,
W + wh.k)
@
min [1, w
Σ
min (1, x8,3
(h.))EI
(b) 4Hdlog
K
1+
4HK.
dAo min
where (a) uses 2n.6 & co & due oh, 2 co bn, co $ and (b) uses Lemma G.5. We will frequently use the above inequality.
Now, are ready to analyze the three terms in the RHS of equation F.14 respectively.
For the first term, follows that
Σ
Σ (h,
Σ
Thi
(N.Aee
(b.k))e
Σ (h,k)EJT
(o + d FAik + Jnak)
Σ
(HiN))EJs
Σ
(02 min + d Enn + Jn.k)
Σ
2
V
(H,A)EZ
(h,K)EI
HKo min + Σ (dH F Ja.k) V4HK.
(h,A)eI
We provide a upper bound for >x=1 Σn= ER in Lemma F.2 whose proof is deferred in Appendix F.11. Lemma F.2 (Sum of FR,x). On the event Bo Ao:
ΣΣ E o ((86 (88+
K h
Clnnkl H H2H2 log 4fogg HK]
+ HB)H
Σ
Σ
k=1k-1
where O(.) hides universal positive constants.
We also provide upper bound for ΣNI Jh.k in Lemma F.3 whose proof is deferred in Ap- pendix F.11.2.
Lemma F.3 (Sum of Jr,K). Recall that Jn,A = NV + V h h+ (s an,x) + RA x Un with R Un defined in equation A.8 and equation A.9 respectively. On the event BR BB AB Ao, with probability at least 1 - 25,
# Σ Σ Jn 0
( ( + + H3JH + 3
Σ
K
Σ
H
by + 22 log
4 4[log, HK]
1 + Ho lox 108 11)
6
50

---

Published in Transactions on Machine Learning Research (April/2024)
where 9 is defined in equation 3.2 and O(-) hides universal positive constants.
Putting pieces together and using va+b+ce va+ vb+ + vc, we have
Σ b
Σ
Th =0 (V V (Hlo g+)
(h,b)EJ
(h,k)EJi
4[log, HK]
+0
v VHR. V HD log
5
+ Ho R
log 8
(F.15)
+ +0
VHK. [(30 + H3)H1&8 + BRRl
Σ
blok
For the second term, due to oh,
Cu -1
bn we have 24, bn.w/On,k co for all (h, k)) E J2. Hence,
Σ back
Σ
suP(h,k)zZ Th
2
Th,
2h.
CO.
(h.4)eJ2
(k,k)EJ2
(h.k)EJa
(k,R))J2
max([lon,k]]
Hilh I Hy
4HK
sup (h,A)
Σ
(F.16)
cj
(h.A)EZ
where the last incquality uses 1 hd & - @l & vI and || H
& vx
for any
vx
(h, k) I.
For the third term, oh
2n Hence, Ho..5H bn, and thus on, = (Va + Hd.
Vord
The = ( (Vad
Σ
bh.k
Σ
HHR25
Σ zh
(h,k)eJa
(h,R)eJJa
W
W
Hd..5 H
Σ
2h & 4HR
+ Hd25 H
(F.17)
Vedd
Verd
(h.A)eT.
Combing equation F.15, equation F.16 and equation F.17, we have
Σ b = o C+ VHK [(Bo + H3)Hd3 + 3re]
Σ byck
(N,))Z
(N,A)e
where
W
C VH.. K (Ho + +** HR.
Vegd + cgvi
+ Hdl
+ HK. / H3 log 4llog, HK|
+ Ho? log 3
Using the inequality that x & 2(a² 122) for any x & / + 12, we have
Σ bn = (C H2add (Bo HB) 1133xe). (k
In the following, we are going to simplify the last incquality. For simplicity, we will use Ö(.) to hide logarithmic factors. Notice that Ö(d). By setting X #4422, have Bn By Ö(vi) and
51

---

Published in Transactions on Machine Learning Research (April/2024)
By + BR = Ö(vd). Moreover, 3g² = δ - vd + vAw) Ö (vd+ vd Omin
thus
and
9 = Ö (a + vddH) = Ö VaHHH vd). Therefore,
Σ
bh.k O (C+ Hmdd (3o H1) HKBRa)
(b,K)
122.56533 Hd on
=O(C++
+ 1 H Hd..))
min
We then analyze C. Using va+ b vā + vb for non nen-negative numbers a, b 2 0, have
Ō H.. k min
min
H2d351 H2dH + Hd on + Hd)
Putting the results together, we have
Σ bi.k δ (VaHKG K min
22.5 + Hd.. R
H + Hd on + Hd
Omin
F.11.1 Proof of Lemma F.2
Proof of Lemma F.2. By the definition of Fx, in equation A.7, it follows that
2H. H [ V+1 vhtza) (sn,
E
1=1 b=1
k=
(a)
47,50 Φ1 &1, 1 + [PA(V A4VV++ h
(sn,),
k= 1=1
(6)
H
4flog2 HK)
(430 16H3)H
222 log |
8
K
4llog, HK]
0 (30 H33H
Σ
Σ
H2 log
k-1 h-1
where (a) uses [(PAA PPAV [Sn,, an.)
KKnn,, (MnA
WD Bol (o ill on Bo and (b)
follows from Lemma D.9.
F.11.2 Proof of Lemma F.3
Proof of Lemma F.3. By Lemma D.3, on the event BR, we have R Vn (n and) & Rus for all
[H] and & [K]. By Lemma D.5, on the event By Bv, 1 I an,)) & VV i (sn, an,)) + Un, for all h [H] and & [K]. Therefore,
K H
M. + V.VA V ap,))
+
Ry +2 Σ
U
k=1
k= h=1
k= h=1
(T) + (IT) (IIT).
For the term (III), we have
H
H
U = ΣΣ
11733 (0NAle + 47 Pr
h41 (8 an,))
k=1h-1
52

---

Published in Transactions on Machine Learning Research (April/2024)
K
H
197.00 1 + 471 Pn (41 (5 an.))
K
H
4[og, HK]
(198)
64H3)H
Σ
1 @n. + 152H2 log
(F.18)
8
h=1
where (a) uses [[P PP)V ho (s an.))
Konn (KAR
1 1 < 3ol Φn. 1 on Bo; and
(b) follows from Lemma D.9.
For the term (II); have
k
H
K
K + 2HH3R
R = 3
Σ
|
I Ha
(F.19)
k-1h=1
We provide two ways to analyze the term (1).
On one hand, denote X Σ I VV Rr + VaVi (8hh,, for simplicity. Let GR Fi, be the a-field generated by all the random variables over the first & episodes. Then gę is Ga-r-measurable, X > 0 is G.- mh-maasurable, and [X&l & H(o + HZ). Therefore, [X, - E[Xx/Ox=1ll & H + H2) and Var[Xx19u-1] & H(o + H²) ( By the variance-aware Freedman inequality in Lemma G.2, with probability at least 8, we have
K
K
2|1og K| 8
X E[
Σ
E E[Xa|9a-11 1 log H(o H2) Σ
2[log2 K]
(o + +22) log
5
2 2 K]
E| FR-1J + ++ H²) log
8
k= 1
Notice that
Fx E
V. RA + VaV 1 an 9k-1
H
Σ
V Rs + V.V E (3.))d)
where di (s) = pT* s,an also $1,6) is the probability reaching (Sh,ks an,k) (s, at the h-th step when the agent starts from 81,6 and follows the policy ny. Therefore, we have
K "
2ooog, K
(1) 3 3
Σ
E
(x.0)~ax (V + V 1(t + 7H + H.) log
8
2 lo K
x 39 K + (H + H22 log
8
where
go K
((.aa)
(V,R, V.RR, VVV
k=
h=1
On the other hand, we have
k h
K H
(1)
Σ
Σ
VAVa
VAVIT
(sh,,, +
Σ
Σ
[V + VAVTA I (..))
Ri
53

---

Published in Transactions on Machine Learning Research (April/2024)
equation P:20
2H.
K
H
Pn h+1 - (sh. +
Σ
K
Σ
H
[R + Va an.))
K H
2HH
PM
PM
(Va1 h+1 (+t1) +
+ 2V2 2H( + H(. log 8
==1h=1
K 16
4foog HK]
& 2 + (o + +H2)
1 H
+ 72 log
K
H @ H + 78 log 4flog2 HK]
& 2V + 3H
+ 22 log 5
5
where the first inequality uses equation F.20, the second inequality uses Lemma F.4, and the third inequality uses Lemma D.8.
[V VA W411 (8h,k,
PalVa+al 2 (S0,,, ap,s) [T h+ (sh,, x)) (P (sh, an,k) [Px t (8h,ks xnx))
(a)
< 2 - PALV (a.]](((,,) (S2, an.k)
(6)
& 2H PA
V (SN an.k)
(c)
& 27 PA PA h41
h+1 ( (nak)
(F.20)
where (a) uses (+)+(() (.), (b) uses (+) < v+++(+) H, and (c) uses Lemma D.4.
Finally, we are going to put the pieces together. In order to simplicity notation, we use bj.k max(11<n. H T A and B By + BR- From the first bullet point, have
K
JAnk = o 0
K
H
b + H2 4flog, HK]
+ Ho log 1
.K. K [(B + H3)H + BRA]
5
h-14-1
From the second bullet point, we have
Jn.k 0 | [(B0 HB)H + BRe]
H bh.k H2
4flog2 HK]
Ho log 1
8
k=11=1
k=1k=1
Taking minimum of the last two inequalities and using min (9t V2 & g complete the proof.
F.11.3 Proof of Lemma F.4
Lemma F.4 (Total variance lemma). With probability at least 1 - 8, we have
k
H
Σ
VA VT an 2v2 + 211 + H2) log
Proof of Lemma F.4. The proof uses a similar argument as Lemma C.5 in (Jin et al., 2018). Notice that the first state $1,6 is fixed and an,k = (s,,)) Therefore, (52,A. SH,)) is a sequence generated by following policy Th starting
$1,k- Let Gx be the o-field generated by all the random variables over the first k episodes. X = H [V,, + ( Ge-r-mcasurable, X Ga-mcasurable, and [&el H(o + H(2).
We have the following properties about X Clearly क. is
Let E&(+)= [[. for simplicity.
22 > Ex-1
Σ
Ru Ra (SE.k, (1,2) 1iTH (51,2)
54

---

Published in Transactions on Machine Learning Research (April/202)
Σ (Rassh,aaaa)) Viti (5h+1,,) V (sh,
Ex-1 [Rn(s an Vith (sh+1k) V/ (sh.)))
E
[Ry - rb] (n) + (ra an,h) V/+ (sh+1x)) V/ (sh,))
(d)
E Σ
VV Rh Vo V -[[
where (a) uses (+) = O, (b) uses the independence due to the Markov property, (c) holds since (s (p,k) independent with S4+1. conditioning on (sh.k. and (d) uses V/ (sh,k) = Th (s ah,a) E Pa ()) w) (V (V7 (s++1,))] Using Var[X [K-1] & H(o + H2) [[[x( we have
K
K
VarlX & II H9)
Σ
1 & (o H
By the Freedman inequality in Lemma G.I, with probability at least 1 - ô, we have
H
VaRR +
K E[ FR-1l + V 2 H2) log x + H(0 + +H) Hog
X
k=1
2 (o + H²² log 5
2
$ V2K K + 2 V2K H H2) log
$ 2V2K (H + Hog)oog 8
G Auxiliary Lemmas
G.1
Concentration Inequalities
Lemma G.1 (Freedman inequality (Freedman, 1975)). Let (Xcherr be a stochastic process that adapts to the filtration Fg so that X, is F-mmasurable, [[X,[_F-1] 0, |X,] & M and [ & V where M and V >> 0 are positive constants. Then with probability least 6, have
T E
1 σ
2M
1
2V In
+
In
3
Lemma G.2 (Variance-aware Freedman inequality). Let hett be stochastic process that adapts to the filtration F, so that X, is Fi-maauurable, [[X,[F=-1]] - 0, |X,| & M and Σt= E[X]]=-1]] & V2 where M > and V > 0 are positive constants. Then with probability at least 1- 6, we have
Σ X
3
Σ
2K B[ log + 5M 5M
2K
8
where K 1 [2 loga M7
55

---

Published in Transactions on Machine Learning Research (April/2024)
Proof of Lemma G.2. By Theorem 5 in (Li et al., 2021), we have for any positive integer K 2 1,
P
Σ
X
8 max Σ E
F(-1)
V/2
In
2K
4M
ln
2K
1
2k
6
By setting a, > and In 2K 8 > 1, we complete the proof.
+ 1ogg 1. we have
12 2
& M Using max(a, bj & Eatb va & va + vb for any
The following two lemmas are the counterpart lemmas of Theorem 2.1 under the light-tail assumption.
Lemma G.3 (Bernstein's incquality for self-normalizer martingales, Lemma F.4 in (Hu et al., 2022)). Let (G) be a filtration and (at, ra3 be a stochastic process so that Cz E I&d is Gy-measurable and m E I is 0++1-meaurabbl If | & and (nhea satisfies that E[m[G.] = 0, E[ & o² and
In min 1, [mlllz,1)) & M for t 1. Then, for any (0, 1), with probability least 1 6, we have for
all t 1,
tL
4t + 4M log
4t
80 dlog
1
log
dA
8
8
2,
where Z, AI my. Rya] for f 1 and Zo XI.
Lemma G.4 (Hoeffding inequality for self-normalized martingales, Theorem in (Abbasi-Yadkor al., 2011)). Let (ar be a filtration and ( Jras be stochastic process so that æ; I2d is Ge-mesurrable and т/ R is G m-er-meaurebbe. If |aal]| & L and (me)e31 satisfies that [[m] 0 and Ind & M for all > Then, for any 8 E (0, 1), with probability at least - 6, have for all >> 1,
Σ ZyyH
< M dlog (1+
1+
tL? di
+ log
1
z,
where Z, = XI E/- 25 for t > and Zo= = AI.
G.2 Elliptical Lemmas
Lemma G.5 (Lemma. 11 in (Abbasi- (Abbasi-Yadkori et al., 2011)). Let (0t)121 = IRd and assume |æ,|| & for all
b Set Z, E Fg + AI. Then follows that
T
dd + TT2
min (1, Σ
< 2d
dA
Lemma G.6 (Lemma (Abbasi- Yadkori et al., 2011)). Suppose A, B Rdxd are two positive definite matrices satisfying that 2 B, then for any Rdd
det(A)
x
B
del det(B)
G.3 Function Class and Covering Number
This subsection collects important lemmas in (He al., 2022). Let K. k2........ denote the set of episodes where the algorithm updates the value function in Algorithm 3. For given total number of episodes K, it follows that [K] & K. Furthermore, due to the mechanism of rare-switching value function updates, |AC] is much smaller than K. Lemma G.7.
K Ao min
[C] & dH loga
56

---

Published in Transactions on Machine Learning Research (April/202)
Proof of Lemma G.7. The proof is almost identical to Lemma E.1 in (He et al., 2022) except that maintain the dependence on min- According to the determinant-based criterion, for each episode his there exists a stage h E [M] such that det (e HM - E 2det Hde A-1-1)). Since we always have H Z Ha - for all h E [H] it then follows that
II he[H]
det H ( 3 2 II
det H (H
he [e[H]
By induction, it follows that
I det Hi, 3 2/
II det HA > 2/
II dct(AI) = 2
h=[H]
he[H]
he[H]
On the other hand, due to Hi Hi, the determinant det H Hi
is upper bounded by
K
dH
II det H ke[H]
II he(H)
det Not(Hn,k) A
o
min
Combining the last two inequalities, we have
|K| & dHloog log2
1
Ao min
The optimistic value function Vx(+) mink & max. Qhe (+)a) belong to the function class D
y+ (1(() max min min w ol. a) + Bll a) H H. HH K
B [0, BJ, 1|w < 2
(G.1)
while the pessimistic value function
(-) maxk &k max. 2% (. a) belong to the function class V
- {15 max max max [w) ((,;a) a) - Bll0(; a)) H H) ,3 E [0, 1/osl & I,, H, 2 Ar). (G.2)
E KE|K
dk x Here B upper bounds 3 and L W HV
is uniformly bound for Oú.k-1 phi Vh+1 because
dK
10 Ph, h+all
Op.k-1l + || htal < W + HV
where the last inequality uses the boundedness of 0n, 's and the inequality ||pnk- V h+1ll & Hy proof can be found in Lemma E.2 of He et al. (2022)).
dK (whose
Lemma G.8 (Covering number of value functions). Let V denote the class of optimistic or pessimistic value functions with definition in equation G.1 and equation G.2 respectively. Assume [|o(s, a)ll < 1 for all (s, a) pairs, and let. a(V,a) be the e-covering number of V with respective the distance dist(J, = sup.es (f()) Then,
4L ) + dl log 1+
8d
]
log log.NVVt 8) dlog [+
11%/
de2
Proof of Lemma G.8. The result about D follows from Lemma E.6 in (He et al., 2022). The result about VF follows from Lemma E.7 in (He et al., 2022).
Lemma G.9 (Covering number of squared functions, Lemma E.8 in (He et al., 2022)). For the squared function class [V+]2 ; {f e v+}. let N([++ be the e-covering number of [V+]2 with respective to the distance dist(ff f') := supses if(s) f((s).. Then
log. ((V((()))ss))) & dlog (1+ SHL dl log [+ 1
32d H2 ]
1/%.
2e2
57


Reviews:
[{"review_id": "hQkTqx8YE5", "reviewer": "Reviewer_eYei", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Major concerns:\n\n1. Lemma 2.2 is crucial for constructing the confidence region and addressing the heavy-tailed issue. However, I am uncertain about the correctness of the proof of Lemma 2.2.\n\n   Specifically, at the top of page 30, the authors utilize Lemma C.1 to complete the proof, where Lemma C.1 requires $A_t$ to hold for any $t\\leq1$. However, Lemma 2.2 aims to establish that $A_t$ holds with a probability of at least $1-\\delta$ for any $t\\leq1$. Lemma 2.2 is a condition of Lemma C.1, and Lemma C.1 is used to prove Lemma 2.2, which creates a contradiction.\n\n   If mathematical induction is being used, please provide detailed steps for the induction, particularly the change of probability parameter $\\delta$. I am open to the possibility of being completely mistaken about this point.\n\n2. Based on the aforementioned concerns, I have doubts about the effectiveness of the Huber loss (Eq 2.3). Specifically, the Huber loss adaptively adjusts between squared loss and L1 loss to handle heavy-tailed problems, particularly the robustness of L1 loss when the loss value is extreme. However, both squared loss and L1 loss lack the ability to handle heavy-tailed issues, and their combination intuitively cannot reduce extreme values. \n\n   Can the authors provide some intuitive examples to explain the effectiveness of this loss? In my opinion, if the Huber loss is effective, it would be a more elegant strategy than truncation and the median of means. I am open to the possibility of being completely mistaken about this point.\n\n3. Can the authors conduct real-world experiments? Currently, most of the bandit models are verified using simulated datasets. If experiments can be conducted on real-world datasets, it would be a significant contribution to the community.\n\n## Minor comments:\n\n1. $R_h(s,a)$ above the Assumption is not defined. $r_h(s,a)$ represents the expected reward, while $R_h(s,a)$ represents the random reward. In step 17 of the formal VARA, it is observed that $r_{h,k}\\sim R_h(s_h, a_{h,k})$, where $R_h(s_h, a_$h,k$)$ seems to be a distribution. The authors may consider distinguishing between random variables and expectations using uppercase and lowercase letters, as the current usage can easily cause confusion.\n2. The MDP process has already been modeled through parameters $\\theta_h^\\*$ and $\\mu_h^\\*$, can the author provide an expression for $Q_h^\\*(\\cdot, \\cdot)$ regarding  $\\theta_h^\\*$ and $\\mu_h^\\*$?\n3. $V_1^\\*$ in the learning protocol is not defined. \n4. Lemma D.2 and Lemma D.4 are the most important tools for extending the bandit model to MDP. Regarding D.2, the author states: \"The proof is quite standard (Jin et al., 2020b; Wagenmaker et al., 2022a; Hu et al., 2022).\" What is the novelty of the analysis for VARA in Lemma D.2?\n5. For VARA, I did not understand the meaning of the lower bound $\\underline{V}_h^k(\\cdot)$. It seems the lower bound does not used in the formal VARS. Can the author provide further explanation?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates bandits and Markov Decision Processes (MDP) with heavy-tailed rewards. The main contribution of this paper is the construction of two variance-dependent regret bounds for bandits and linear MDP, respectively.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the comments in Strengths And Weaknesses.", "broader_impact_concerns": "I do not have any concerns on the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "jjF3GYRzcC", "reviewer": "Reviewer_hW9L", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is easy to very read and it is well structured. The algorithms are straightforward improvements on previous iterations but the additions, particularly the hyperparameter settings, are entirely non-obvious without the associated theory. I am familiar with but not an expert on this area of theory, and these results are clear, their relationships to previous results are made clear, and I believe they are impactful. The one linear bandit experiment illustrates the practical implication of the theory and is a meaningful companion to the regret bounds. I have not checked the proofs carefully but the proof sketches and results look reasonable to me.\n\nNo meaningful weaknesses.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents and analyzes the AdaOFUL linear bandit algorithm designed to handle heavy tailed reward distributions and the VARA algorithm for fixed horizon, linear MDPs under heavy tailed reward distributions. VARA utilizes AdaOFUL as a subroutine to estimate parameters for the first and second moments of the linear reward function and LSVI-UCB++ for optimistic policy improvement. The performance of AdaOFUL and VARA are analyzed in terms of regret bounds, computation, and memory compared with previous algorithms, where AdaOFUL and VARA have substantial advantages. Experiments suggest that AdaOFUL is indeed more effective practically than previous linear bandit algorithms in light tailed, heavy tailed, and unbounded reward distribution scenarios.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "No critical changes but I have some small questions and suggestions.\n\n1. Algorithm 1 is difficult to understand with its many references to equations in the text. I would like to see the equations inlined with the current references changed to comments.\n2. The $\\tilde{O}$ notation is explained in Corollary 2.1 but it is used in Section 1.1. Could that explanation be moved closer to its first use?\n3. The experiment figures are not very readable in greyscale, it would be nice if they were, especially since there are only three lines in each plot to differentiate.\n4. For the experiment figures, I am not sure why the regret of AdaOFUL continues to grow substantially even when its distance to $\\theta^*$ is relatively small. Especially in Cases (b) and (c), it looks like AdaOFUL's regret is growing only marginally slower than TOFU's, but AdaOFUL's convergence is much better. What am I missing?\n5. Also for the experiment, 10 repetitions were run, but I do not see the variability reported in the main paper. A histogram of the final regret and convergence across replicas could be illuminating.\n6. When defining MDPs, the state value function is defined as a sum of action values. I think that $a$ is unbound and instead the statement should be $V_h^{\\pi}(\\cdot) = Q_h^{\\pi}(\\cdot, \\pi_h(\\cdot))$.\n7. Clause 2 of Assumption 3.2, it appears like $\\mathcal{H}$ and $\\mathcal{V}$ are used without a previous definition. Upon checking that they were not defined previously, I guessed that they were being defined here implicitly as bounding values but making that clear here would have saved me some time backtracking through the paper.\n8. I cannot make sense of the second last sentence before the \"Learning protocol\" subsubsection near the end of Section 3.1, I think there is a typo.\n9. Is $V_1^*$ defined before its use at the end of Section 3.1?", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "GnEtgQ6lTM", "reviewer": "Reviewer_oNBg", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n* The paper is well written and the techniques are presented in a natural order for ease of reading.\n* It is nice that their results for linear MDP's does not require knowledge of the new variance parameter and is tighter than previously known rates.\n* The theoretical findings are supported by experiments which show the superior performance of their new algorithm.\n\n## Weaknesses\n* It is a bit unclear to me how the setting is \"heavy-tailed linear bandits\". In Definition 2.1, one is merely saying the conditional variance can be a generic quantity $\\nu_t^2$. While this recovers the setting with bounded second moments, what about the typical heavy-tailed setting where one assumes rewards have $(1+\\epsilon)$ moments which are bounded (e.g., see the cited paper Xue et al., 2021)? Without considering the full setup for generic $\\epsilon>0$, it just seems like this paper is restricted to the subgaussian case. See also the work \"Variance-aware Spare Linear Bandits\" (Dai et al., 2023).\n* I'm also concerned about the similarity to \"Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency\" (Zhao et al., 2023). It seems like they can already get the variance-aware regret in the same setting as this paper. The citation of this paper is noticeably absent despite the similarities.\n* Please also compare with the work \"Heavy-tailed Linear Bandit with Huber Regression\" by Kang and Kim, 2023, which is also not cited.\n\nIn conclusion, I would like to see the questions of (1) whether the results of this paper can really capture the full \"heavy tailed\" setting and (2) how the result compares to the recent and similar mentioned papers above. It is concerning that these recent works are not cited, and so I am left unsure of whether the results of this paper are not already contained in other papers, technical contributions notwithstanding.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper achieves variance-based regret bounds for linear bandits with heavy-tailed rewards. While the task of attaining variance-based regret or handling heavy-tailed rewards have supposedly been studied in isolation w.r.t. linear bandits, this work claims to be the first to jointly study the two problems. The main approach is to combine OFUL with Huber regression techniques. As an application, they show similar regret bounds can be achieved for linear MDPs, which yields tighter instance-dependent rates than previously known.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "## Writing Suggestions/Typos\n* section 1.1, second paragraph \"Adatptive\" should be \"Adaptive\"\n* page 4, below display (2.5) \"deinfed\" should be \"defined\"\n* page 6, below display (2.10), \"Combing\" should be \"Combining\".\n* Is dependence on $b$ being hidden in Lemma 2.2 or are you taking $b=1$ WLOG? I'm a bit confused by the $b=1$ remark at the end of page 6.\n* In Lemma G.2, it seems the inequality with V^2 is unnecessary as you just want to say Freedman's inequality holds for the actual sum of conditiional variances rather than an upper bound.", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: While I am enthusiastic about accepting this work, my excitement is somewhat dampened by it being unclear what the technical challenges were in obtaining these results, in light of previous work. This opinion is shared by at least one reviewer. The authors did mention explaining analytical novelty of the linear MDP results in an appendix, but this is really something that should take center stage for such a theory-focused paper. Also, from my look at the appendix, I saw the author's quickly emphasizing Lemma D.8 but was left wanting a more detailed discussion. In the future, I suggest the authors give proper focus to any novel technical tools/ideas within the main text (you can see well-known RL Theory papers to see how people do this); this might make the difference between an Accept decision versus an Accept decision along with a certification (e.g. Featured Certification in this case). It can also help others adopt your ideas. Still, I believe this paper is definitely worth accepting and congratulate the authors on their impressive work.

For the camera-ready version, please do a full pass over the paper to check for spelling issues and typos. You can run a spellchecker on LaTeX, but that won't fix all issues so you really should carefully look over the full paper (especially the appendix, which is where I found the most issues). There is one place in the paper (page 42) where you wrote "forth" instead of "fourth". Also, for intersections of events where the intersection has a subscript (like $h \in [H]$), use the command \bigcap to achieve the better $\bigcap$ rather than the command \cap which only gives  $\cap$.
Decision: Accept (poster)