Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Bounds
Authors: Jiayi Huang
Han Zhong
Liwei Wang
Lin Yang
Venue: NeurIPS 2023 poster (2023)
Keywords: machine learning
reinforcement learning
linear bandits
heavy-tailed rewards
instance-dependent regret

Abstract: While numerous works have focused on devising efficient algorithms for reinforcement learning (RL) with uniformly bounded rewards, it remains an open question whether sample or time-efficient algorithms for RL with large state-action space exist when the rewards are \emph{heavy-tailed}, i.e., with only finite $(1+\epsilon)$-th moments for some $\epsilon\in(0,1]$. In this work, we address the challenge of such rewards in RL with linear function approximation. We first design an algorithm, \textsc{Heavy-OFUL}, for heavy-tailed linear bandits, achieving an \emph{instance-dependent} $T$-round regret of $\tilde{O}\big(d T^{\frac{1-\epsilon}{2(1+\epsilon)}} \sqrt{\sum_{t=1}^T \nu_t^2} + d T^{\frac{1-\epsilon}{2(1+\epsilon)}}\big)$, the \emph{first} of this kind. Here, $d$ is the feature dimension, and $\nu_t^{1+\epsilon}$ is the $(1+\epsilon)$-th central moment of the reward at the $t$-th round. We further show the above bound is minimax optimal when applied to the worst-case instances in stochastic and deterministic linear bandits. We then extend this algorithm to the RL settings with linear function approximation. Our algorithm, termed as \textsc{Heavy-LSVI-UCB}, achieves the \emph{first} computationally efficient \emph{instance-dependent} $K$-episode regret of $\tilde{O}(d \sqrt{H \mathcal{U}^*} K^\frac{1}{1+\epsilon} + d \sqrt{H \mathcal{V}^* K})$. Here, $H$ is length of the episode, and $\mathcal{U}^*, \mathcal{V}^*$ are instance-dependent quantities scaling with the central moment of reward and value functions, respectively. We also provide a matching minimax lower bound $\Omega(d H K^{\frac{1}{1+\epsilon}} + d \sqrt{H^3 K})$ to demonstrate the optimality of our algorithm in the worst case. Our result is achieved via a novel robust self-normalized concentration inequality that may be of independent interest in handling heavy-tailed noise in general online regression problems.

Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Bounds
Jiayi Huang'
Han Zhong' Liwei Wang 1.2
Lin F. Yang
CCenter for Data Science, Peking University National Key Laboratory of General Artificial Intelligence, School of Intelligence Science and Technology, Peking University University of California, Los Angles [jyhuang, hanzhong) .kuu. edu. wanglwžeis pku. edu. en, linyangβee. ucla. edu
Abstract
While numerous works have focused on devising efficient algorithms for reinforce- ment learning (RL) with uniformly bounded rewards, it remains an open question whether sample or time-efficient algorithms for RL with large state-action space exist when the rewards are heavy-tailed, i.e. with only finite (1 + e)-th moments for some (0, 1]. In this work, we address the challenge of such rewards in RL with linear function approximation. We first design an algorithm, HEAVY-OFUL, for heavy- -tiyld linear bandits, achieving instance-dependee T-round regret of Öld 20+40 v /T= ut + dT 201+)) ) the first of this kind. Here, d is the feature dimension, and te is the (1 + e)-th central moment of the reward at the t-th round. We further show the above bound is minimax optimal when applied to the worst-case instances in stochastic and deterministic linear bandits. We then extend this algorithm to the RL settings with linear function approximation. Our algo- rithm, termed as HEAVY-LSVI- -CB, achieves the first computationally efficient instance-dependent K-episode regret of Oldv HU" K + dv K). Here, H is length of the episode, and L1", V are instance-dependent quantities scaling with the central moment reward and value functions, respectively. We also provide a matching minimax lower bound Q(dH 14e + d (H*K) to demonstrate the optimality of our algorithm in the worst case. Our result is achieved via a novel robust self-normalized concentration inequality that may be of independent interest in handling heavy-tailed noise in general online regression problems.
Introduction
Designing efficient reinforcement learning (RL. algorithms for large state-action space is significant challenge within the RI. community. A crucial aspect of RI. is understanding the reward functions, which directly impacts the quality of the agent's policy. In certain real-world situations, reward distributions may exhibit heavy-tailed behavior, characterized by the occurrence of extremely large values higher frequency than expected normal distribution. Examples include image noise in signal processing [14], stock price fluctuations in financial markets [12, 18], and value functions in online advertising [11, 19]. However, much of the existing RL literature assumes rewards to be either uniformly bounded or taile- (e.g., Gaussian),)n. In such light-tailed settings, the primary challenge lies in learning the transition probabilities, leading most studies to assume deterministic rewards for ease of analysis [5, 22, 15]. As we will demonstrate, the complexity of learning reward
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

functions may dominate in heavy-tailes settings. Consequently, the performance of traditional algorithms may decline, emphasizing the need for the development of new, efficient algorithms specifically designed to handle heavy-tailed rewards.
Heavy-tailed distributions have heen extensively studied in the field of statistics [9, 27] and in more specific online learning scenarios, such as bandits [7, 28, 31, 34, 40]. However, there is a dearth of theoretical research in RL concerning heavy-tailed rewards, whose distributions only admit finite (1+ moment for some E (0, 1]. One notable exception is Zhuang and Sui [44], which made a pioneering effort in establishing worst-case regret guarantees in tabular Markov Decision Processes (MDPs) with heavy-tailed rewards. However, their algorithm cannot handle RL settings with large itate-action space. Moreover, their reliance on truncation based methods is sub-optimal as these methods heavily depend on raw moments, which do not vanish in deterministic cases, Therefore, a natural question arises:
Can we derive sample and time-efficiert algorithmss for RL with large state-action space that achieve instance settace-deeendent regret in the presence of heavy-tailed rewards?
In this work, we focus on linear MDPs [35, 22] with heavy-tailed rewards and answer the above question affirmatively. We say a distribution is heavy-tailed if it only admits finite (1 + e)-th moment for some E (0, 1]. Our contributions are summarized as follows.
We first propose a computationally efficient algorithm HEAVY-OFUL for heavy-tailed linear bandits. Such a setting can be regarded as a special case of linear MDPs. HEAVY-OFUL achieves 1-e ), the first of this kind.
an instance-dependem T-round regret of (dT 20T3 V EEE
Here d is the feature dimension and v/+te is the (1 + e)-th central moment of the reward at the 1-th round. The instance- -eeteneeddeeeeenttt regret bound has a main term that only depends on the summation of central moments, and therefore does not have a /T term. Our regret bound is shown to be minimax optimal in both stochastic and deterministic linear bandits (See Remark 4.2 for details).
We then extend this algorithm to resulting in a new computationally efficient algorithm HEAVY-LSVI-UCB, which achieves a K K-episode regret scaling as D(dyHu* + + dy (HY*K) for the firs! time. Here, H is the length of the episode and 2t,,, V are quantities measuring the central moment of the reward functions and transition probabilities, respectively (See Theorem 5.2 for details). Our regret bound is instance-dependent since the main term only relies on the instance-dependent quantities, which vanishes when the dynamics and rewards are deterministic. When specialized to special cases, our restance-depentee regret recovers the variance-an -warre aware regret Li and Sun [26] (See Remark 5.3 for details) and improves existing first-order regret bounds [33, 26] (See Corollary 5.6 for details).
linear MDPs with heavy-tailed rewards,
We provide a minimax regret lower bound Q(dH + dv H*) for linear MDPs with heavy- tailed rewards, which matches the worst-case regret bound implied by our instance-dependent regret, thereby demonstrating the minimax optimality of HEAVY-LSVI-UCB in the worst case.
For better comparisons between our algorithms and state-of-the-are results, we summarize the regrets in Table and 2 for linear bandits and linear MDPs, respectively. More related works are deferred to Appendix A. Remarkably, our results demonstrate that variance-aware regret bounds of the same order as the case where rewards are uniformly bounded for both linear bandits and linear MDPs. The main technique contribution behind our results is a novel robust self-normalized concentration inequality inspired by Sun et al. [32]. To be more specific, it is a non-trivial generalization of adaptive Huber regression from independent and identically distributed di.i.d.) case to heavy-tailed online regression settings and gives a seff-normalized bound instead of the fo-morm bound in Sun al. [32]. Our result is computationally efficient and only scales with the feature dimension, d, (1 + e)-th central moment of the noise, v, and does not depend on the absolute magnitude as other neffnnormalized concentration inequalities [42, 41].
(i.e. finite variance) is sufficient to obtain
Road Map The rest of the paper is organized as follows. Section 2 introduces heavy-tailed linear bandits and linear MDPs. Section presents the robust self-normalized concentration inequality for general online regression problems with heavy-tailed noise. Section 4 and 5 give the main results for heavy-tailed linear bandits and linear MDPs, respectively. We then conclude in Section 6. Related work, experiments and all proofs can be found in Appendix.

---

Table Comparisons with previous works on linear bandits. T, for (ee), {vr (et))) dimension, the number of rounds, the variance or central moment of the reward at the t-th round.
are feature
Algorithm
Regret
dependent?
Instance-
Optimal?
Minimax
Determinitte- Optimal?
Heavy
Tailed
Rewards?
OFUL [1]
① (dvT
No
Yes
No
No
IDS-UCB [24]
No
Ö(d, Ei +d
Weighted OFUL+ [41]
Yes
Yes
Yes
No
AdaOFUL. [26]
MENU and TOFU [31]
dT
No
Yes
No
Yes
HEAVY-OFUL (Ours)
dT (iaee
Eien
dT
Yes
Yes
Yes
Yes
Table 2: Comparisons with previous works time inmomonooogen linear MDPs. d, K.H.K.V... are feature dimension, the length of the episode, the number of episodes, optimal value function, variance-dependent quantity defined in Li and Sun [26]. 4", V are defined in Theorem 5.2.
Algorithm
Regret
Dependent?
Moment-
Contral
Order?
Firt-
Minimux Optimal?
Computa--
timallly Ellicien??
Rewardk?
Heavy-
Talled
LSVI-UCB[22]
VOH*K
No
No
No
Yes
No
FORCE [33]
VVHHVVK
No
Yes
No
No
No
VOQL
① (dvHHK)
No
No
Yes
Yes
No
LSVI-UC+++1N [15]
VARA [26]
o Ö(dvHG-K
Yes
Yes
Yes
Yes
HEAVY-LSVI-UCB (Ours)
Ô HWHH i dvHV*K)
Yes
Yes
Yes
Yes
Yes
Notations Let ||||| := |a 12- Let [t] == (1.2.... .t). Let Ba(r)
== fa E
|
< r).
Let F)o.b] max(a, min b), denote the projection of x onto the close interval b]. Let a a((Xa)se(t) be the o-field generated by random vectors {Xa))e(t))
2 Preliminaries
2.1 Heavy-Tailed Linear Bandits
Definition 2.1 (Heterogeneous linear bandits with heavy-tailed rewards). Let {D: denote a series of fixed decision sets, where all Φ, E D, satisfy | L for some known upper bound L. At each round t, the agent chooses Φi E Dr, then receives reward RG from the environment. We define the filtration (Fe)121 Fi (f Rg) U ((++1)) for any t 2 1. We assume R, (tb,, 0-) + & with the unknown coefficient 0" E BBa(B) for some known upper bound B. The random variable E TR is Fe-measurable and satisfies F[ 0, [++ li+e for some 6 (0, 1] with Vt being F, 1eff---massne measurable.
The agent aims to minimize the rorud pseudo-regre defined as Regret(T) = 1 (d., 0*)), where o; argmax ΦED, (d) )*).
2.2 Linear MDPs with Heavy-Tailes Rewards
We use tuple M MMS,, AA H, (Ra hej (PA (Pi)ee))) to describe the time-inhomen inhomogeneous finite- horizon MDP, where S and A are state space and action space, respectively, H is the length of the episode, R2 S A + R is the random reward function with expectation Th S A - R. and PA : S x A + ASS) is the transition probability function. More details can be found in Puterman [30]. A time-dependent policy
(mx) heeh satisfies na S A(A) for any h (H). When the policy is deterministic, we use n (8k) to denote the action chosen at the h-th step given 8,, by policy æ. For any state-action pair (s, a) S A, we define the state-action value function QR a)
and state value function V (s) follows: (8, E -==h r(sw, aw = 04.
Vr (s) (s, (T)T))))) where the expectation is taken with respect to the transition probability of

---

M and the agent's policy я. If i is randomized, then the definition of V should have an expectation. Denote the optimal value functions as (s) = = (s) and (s, a) sup, Q7 (s, a).
We introduce the following shorthands for simplicity. At the h-th step, for any value function V S + R. let [P a) ( s.a) ((s),, [V, a) [P, a) [TP ( a) denote the expectation and the variance of the next-state value function at the h-th step given (s, a).
We aim to minimize the -episodee regrer defined Regret(K) Σx=
VT (st)).
In the rest of this section, we introduce linear MDPs with heavy-tailed rewards. We first give the definition of linear MDPs studied in Yang and Wang [35], Jin et al. [22]. with emphasis that the rewards their settings are deterministic or uniformly bounded. Then we focus on the heavy-tailes random rewards.
Definition 2.2. An MDP M (S, A, H, He (1Ph (ee)))) a time-inhomogeneous finite- horizon linear MDP, if there exist known feature maps Φ(s, a) S x A + Ba(1), unknown d-dimensional signed measures he over S with ll [S) == Saes (u(s)]ds S vd and unknown coefficients {0) ke(M] C (B) for some known upper bound such that
(s a) = a), 0%), Pa(-Is, a) =(o(s, a), (09(8,)),47))) (.)
for any state-action pair (s, a) E S x AA and timestep h [H] Assumption 2.3 (Realizable rewards). For all (s, a, h) E S A [H]. the random reward Rj (s) is independent of next state s' ~ (-Is, a) and admits the linear structure
[,, a) = (Ø(s,a) a)) 0%) + (s,
where e (s, a) is a mean-zero heavy-tailed random variable specified below.
We introduce the notation v, [X] = [[[X EXP "] for the n-th central moment of any random variable X. And for any random reward function at the h-th step Rr : S A R, let
Ry
(s, a) R, (sh, (s)) ax)) = (s)
[M Ry (s, a) E[[[RA E, RA](s, an)) an))***((( an) (s, a)] denote its expectation and the (1 + ()+t) central moment given (8), (2)) (s, a) for short.
Assumption 2.4 (Heavy-tailedness of rewards). Random variable En (s. a) satisfies [a, a) And for some known e, E (0, 1] and constants VR, MR- 2 0, the following unknown moments of En (8, a) satisfy
[+t))ss [E | a) S 1-t, [Mttlen|
I+t' S VR
for all (s,a,h) h) ESSXXX [H].
Assumption 2.4 generalizes Assumption 2.2 of Li and Sun [26], which is the weakest moment condition random rewards in the current literature of RL with function approximation. Setting
e == I and é' = immediately recovers their settings. Assumption 2.5 (Realizable central moments). There are some unknown coefficients (bb))e(( S (W) for some known upper bound W such that
[E/|=x|+*](,, a) (Ø(s, +i
for all (s,a, h) E x A x [H]
Remark 2.6. When e = 1, that is the rewards have finite variance, Li and Sun [26] use the fact that 1 (s,, a). assume the linear realizability of the second moment [,, R/ (s, a). and estimate it instead. However, when < there is no such relationship between the (1 + c)-th central moment [ [s, a) and the (1 + c)-th raw moment [E, (s, a). Thus, we adopt a new approach to estimate [M Ra, a) directly, and bound the error by novel perturbation analysis of adaptive Huber regression in Appendix C.3.
] [P2Rn](s, a) R,, (s, a)
[E,,
[E, R,
Assumption 2.7 (Bounded cumulative rewards). For any policy x, let {sh, an, Rí RaINe be random trajectory following policy æ. And define = >
hh E, [s), an) -H hm (s ax). We
assume (1) 0 < Ta < H. (2) E" [M (sh, an) < U. (3) Var(r=) S V.
Here, (1) gives an upper bound of cumulative expected rewards r. (2) assumes the summation of (1+ <)-th central moment of rewards [P1+e R2 (sh, on) is bounded since (Ei [vr+c RA (s),,,, ox)) ax))= मों < Rs. - (8h.an) S due to Jensen's inequality. And (3) is to bound the variance of rn along the trajectory following policy

---

Algorithm 1 Adaptive Huber Regression
Require: Number of total rounds T, confidence level 6, regularization parameter X, minn parameters for adaptive Huber regression cu, C1, To, estimated central moment 7/ and moment parameter that satisfy V I b for all - T.
Ensure: The estimated coefficient O..
1: K dl dllog(1 T / min ))-
2: Set H XI Σ sml T
| 1
3: Set 0z = max Dig min,
VLB (2nb2) 8
|| Φ
H
c
/ 2211
4: Set Tr TO
with wi = 10t H
5: Define the loss function (0) 11111 Σs= lu (
6: Compute O. - ()g (0).
Adaptive Huber Regression
At the core of our algorithms for both heavy-tailed linear bandits and linear MDPs is new approach adaptive Huber regression - to handle heavy-tailed noise. Sun et al. [32] imposed adaptive Huber regression to handle i.i.d. heavy-tailes noise by utilizing Huber loss [17] as a surrogate of squared loss. Li and Sun [26] modified adaptive Huber regression for heterogeneous online settings, where the variances each round are different. However, it is not readily applicable deal with heavy-tailed noise. Our contribution in this section is to construct a new self-normalized concentration inequality for general online regression problems with heavy-tailed noise.
We first give a brief introduction to Huber loss function and its properties.
Definition 3.1 (Huber loss). Huber loss is defined
if
S x > T
(+))
(3.1)
||z|
where 7 >> 0 is referred as robustness parameter.
Huber loss is first proposed by Huber [17] as a robust version of squared loss while preserving the convex property. Specifically, Huber loss is quadratic function of x when |x| is less than threshold т, while becomes linearly dependent on |a|] when |x| grows larger than T. has the property of strongly convex near zero point and is not sensitive to outliers. See Appendix C.I for more properties of Huber loss.
Next, we define general online regression problems with heavy-tailed noise, which include heavy- tailed linear bandits as a special case. Then we utilize Huber loss to estimate 0-. Below we give the main theorem to bound the deviation of the estimated 0, in Algorithm I from the ground truth 0*,
Definition 3.2. Let {Fi)121 be a filtration. For all > O, let random variables Yt. Et be Fi- measurable and random vector Φb (a(L) be Fe-1- Suppose ye (Φ., 0*) + Et, where 0 E BB(B) is an unknown coefficient and
[| = 1[ ui
for some E (0, 1]. The goal to estimate 0* at any round given the realizations of (Φs, ys )e((()-
Theorem 3.3. For the online regression problems in Definition 3.2, we solve for 0, by adaptive Huber regression in Algorithm with Co. C1, To in Appendix C.2. Then for any E (0. 1), with probability
at least 1 - 38, for all t < T. we have 0. 1- S Be, where H, is defined in Algorithm and
3, 3VBB + 240 v (kog 3T) 3T) مi (log(2T² /8)
(3.2)
Proof. To derive a tight Huber loss. Chernoff bounding technique used to bound the main error term, which requires careful analysis of the moment generating function. See Appendix C.2 for detailed proof. D
bound, we take the most advantage of the properties of
5

---

Algorithm 2 HEAVY-OFUL
Require: Number of total rounds T, confidence level 6, regularization parameter A, mins parameters for adptive Huber regression co, C12 Tu, confidence radius St.
1: A = d + Ti Co Ba Ho XI.
T1,-
2: fort= l...,, do
3: Observe D,,,
4: Set (#:, = GEgImaNGDD, (0, 0).
5: Play Φt and observe Re, Vt. 1
6: Set o₁ max { [/, minu
VLB
Φell
e (2x)
7: Set Ti = To V++u? fatle with wi 1101/0e1lH
121
8: Update H; - H,-1 + of PPIT..
9: Solve for O₂ by Algorithm and Cu = (0 R=110 0ellH. S 3c).
10: end for
We refer to the regression process in Line 6 of Algorithm adaptive Huber regression in line with Sun et al. [32] to emphasize that the value of robustness parameter Tę is chosen to adapt to data for better trade-off between bias and robustness. Specifically, since are dependent on {Φb.] sct. which is the key difference from the i.i.d. case in Sun et al. [32] where they 7 To. for all f I T. Thus, shown in Line 4 of Algorithm 1, inspired by Li and Sun [26], we adjust T. according to the importance of observations w; = / / where is specified below. In the where 1, different from Li and Sun [26]. we first choose 7, be small for robust purposes, then gradually increase it with f to reduce the bias.
in the online setting, &
Next, we illustrate the reason for setting via Line 3 of Algorithm 1. We use iG E Fi-1 to estimate the central moment V and use moment parameter upper bound of vt, b becomes constant that equals to 1. And d is
measure the closeness between in and Vt-
When we choose 14 a small positive constant to avoid singularity. The last two terms with respect to cy and 0j are set according to the uncertainty || H In addition, setting the parameter co S yields w, S which is essential to meet the condition of elliptical potential lemma [1].
Remark 3.4. The error bound 3, in (3.2) only related the feature dimension and moment parameter b. While the Bernstein-style self-normalized concentration bounds [42, 41] depend on the magnitude of Et, thus cannot handle heavy-tailes errors.
Linear Bandits
In this section, we show the algorithm HEAVY-OFUL in Algorithm for heavy-tailed linear bandits in Definition 2.1. We first give brief algorithm description, and then provide theoretical regret analysis.
4.1 Algorithm Description
HEAVY-OFUL follows the principle of Optimism in the Face of Uncertainty (OFU) [1], and uses adaptive Huber regression in Section to maintain a set C, that contains the unknown coefficient with high probability. Specifically, at the (-th round, HEAVY-OFUL estimates the expected reward of any arm & as maxøec.-. (Φ. 0). and selects the arm that maximizes the estimated reward. The agent then receives the reward R, and updates the confidence set C, based the information up to round with its center 0, computed by adaptive Huber regression as in Line of Algorithm 2.
4.2 Regret Analysis
We next give the instance- -eeendeen regret upper bound of HEAVY-OFUL in Theorem 4.1. Theorem 4.1. For the heavy-tailed linear bandits in Definition 2.1, we set co, C1, Tos B, in Algorithm according to Theorem 3.3 with b 1. Besides, let X d/B², and amin 1/vT. Then with

---

probability at least 1 36, the regret of HEAVY-OFUL is bounded by
Regret(T)) = =Ō di dd
Proof. The proof uses the self- normalizddl concentration inequality of adaptive Huber regression and a careful analysis to bound the summation of bonuses. See Appendix D. for a detailed proof. O
Theorem 4.1 shows HEAVY-QFUL achieves an instance-dependent regret bound. When assume Vt, Vt 2 1 have uniform upper bound (which can be treated as constant), then bound is reduced to Ö(dT++)) It matches the lower bound O(d + by Shao et al. [31] up to logarithmic factors. In the deterministic scenario, where and v 0. for all t 1, the bound is reduced to (d). It matches the lower bound ((d)) up to logarithmic factors.
Remark 4.2.
5 Linear MDPs
In this section, we show the algorithm HEAVY-LSVI-UCB in Algorithm for linear MDP with heavy-tailed rewards defined in Section 2.2. Let Φk.h == ((st,h, @g.h) ) for short. We first give the algorithm description intuitively, then provide the computational complexity and regret bound.
5.1 Algorithm Description
HEAVY-SVV-UCC features novel combination of adaptive Huber regression in Section 3 and existing algorithmic frameworks for linear MDPs with bounded rewards [22, 15]. At high level, HEAVY-LSVI-UCB employs separate estimation techniques to handle heavy-tailed rewards and transition kernels. Specifically, we utilize adaptive Huber regression proposed in Section 3 to estimate heavy-tailed rewards and weighted ridge regression [42, 15] estimate the expected next-state value functions. Then, it follows the value iteration scheme to update the optimistic and pessimistic estimation of the optimal value function Q V and Q V respectively, via a rare-switching policy as in Line 15 of Algorithm We highlight the key steps of HEAVY-LSVI-UCB as follows.
Estimation for expected heavy-tailed rewards Since the expected rewards have linear structure in linear MDPs, i.e., (8, a) (s(s,, 0,),, we use adaptive Huber regression estimate 0%:
AR 11112 Σ 1=1
k
Riih
(dii, h, 0)
k argmin (E 2
(5.1)
Vi.h
where UsA will be specified later.
Estimation for central moment of rewards By Assumption 2.5, the (1 + e)-th central moment of rewards is linear in Φ, i..., PPteRN](s, (Ø(s, a). wh)) Motivated by this, we estimate ,े by adaptive Huber regression as
Ah argmin (W),
An |1b112
Σ
|Eaaltte |Egellte-(00i (Bi +))
(5.2)
Vi.h
where W is the upper bound of || defined in Assumption 2.5. Since Es,h is intractable, we estimate it by E.p. = Rs - (0i.h, 1,,,), which gives 4bk as
AR ||
( +/)
F4.h argmin (W) 2
(5.3)
ViAh
The inevitable error between theh and Th,n be quantified by novel perturbation analysis of adaptive Huber regression in Appendix C.3.
"Consider the decision set consisting of unit bases of ddd Given that each arm pull can only yield information about single coordinate, it is inevitable that d pulls required for exploration.
7

---

Algorithm 3 HEAVY-LSVI-UCB
Require: Number of episodes K, confidence level ò, regularization parameter AR, Av, Mmins min confidence radius Hie, Po; 5u, Bv.
1: = dllog(1 + d' min
k ).
2: 00. = = 1 =
O, Ho, ARI, \v UPDATE TRUE.
3: for k 1.... K do
4: (+) (-)
#1 (+)== = O.
5:
for h = H .... do
6:
Compute 02 1... Wk-1.h and - via (5.1) and (5.8). UPDDAT then
7:
8:
(h(:)) ((((;)) ), O2 1,h + 1 + 8n, || + H + +r "'1
9:
(h(:)) ( 0k 11-1 - -3, (1)((1))))))) 1l, -3r1l0(:, ">>l>>>>>
10:
().),)) = min(Ah (..)). (.,),, H), (1),)(((.))) -00())))=x((000 max (,) Q2 (.,)),))))))
11:
Set Klast k.
12:
else
1 (+.)) Q 1 (,,)), (..22,())) (.,.). end if
13:
14:
()) max, Q (,,),, a), (+) max. Q ( a). xx)+ argmax, (%(-aa).
16:
end for
17:
Observe initial state 8k,1-
18:
for h = 1..... do
Take action assh = (s),A) and observe Rg sh.++1-
20:
Set AA, and Jh.h according to (5.4) and (5.9) respectively.
VI+WE Az0=o, Tk, To
y VT+wga h0047 with wk.h
Set TRi To
Wk.a
wh.h
22:
Update High H + VEA DEAREE and En,h Ek- oz Ge,n
23:
end for
24:
if 3h' E [H] such that det(HH Hb,N) 2 2 det H () or det(eeess)) Ex.'r 2 2 Exime
then
25:
Set UPDATE TRUE.
26:
else
Set UPDATE FALSE.
28:
end if
29:
end for
We then set the weight v for adaptive Huber regression as
| H. 1.6. y /m, W]
VkA max
Dk Pmin+
| H
(5.4)
Go
(2x)²
1
where Vinn is a small positive constant to avoid the singularity, 1/ = Bh (k, Wk.b is a high-probability upper bound of rewards' central moment Rale ax.) with
Di+ Rn)e (sE,,,,, (3..A,)),, = (dbu.h; 11.)1,))
(5.5)
WA.h = (3n -- 671 8I, 116) ( "r
(5.6)
where r is defined in Algorithm 3, 3g = Ō(V.v 20 /mmin) and 3R, = Ö(V 2t
Estimation for expected next-state value functions the following notations for simplicity:
For any value function f S R, we define
(s)sss l
Σ
o
(5.7)
JES
==1
where will be specified later. Note for any state-action pair (s, E S x A, by linear structure of transition probabilities, have
[n,f((s, a) = -WES (0(s, (((s))))) = (Ø(s, a), w/(
8

---

In addition, for any f.g: : S - R, it holds that wnlf - gl wn + 1) and wx,n + gl wx,n Wx,h [g] due to the linear property of integration and ridge regression.
We remark [f] [
is the estimation of [f] by weighted ridge regression on { ( And estimate the coefficients Wggh, Wk,h, Wk,h
A = Ws.n [Viil WAAh = TR,b ( Wx,h (v.A((V
(5.8)
where V. and V are optimistic and pessimistic estimation of the optimal value functions.
Estimation for variance of next-state value functions Jh for weighted ridge regression in (5.7) as
Inspired by He et al. [15], we set the weight
k = max
kkh V d H min, 10 x V d8 HH 0x -
(5.9)
where min is a small constant to avoid singularity, 02hn = [V V h+ (5k,, ax,)) + En, with
VA V (Sk.h, ak.h) (0k,A, wk 1k-1.0)0000 (Φk. 1.)-
(5.10)
Ex, min [47 Wk-1A 1 117/30 @ >;-1,>
H!?
(5.11)
DE min (2 1 h - 1,1) 47430 | ||x H22
(5.12)
where 3o = O(Vo'HH min).. Here 22 and DR. are upper bounds [VA i3 as,A) and max (V (= ak,)), (Vn (V V Vitt))(ss,n a..)). respectively.
5.2
Computational Complexity
Theorem 5.1. For the linear MDPs with heavy-tailed rewards defined in Section 2.2, the compu- tational complexity of HEAVY-LSVI-UCB is ((d A| K + HKR). Here is the cost of the optimization algorithm for solving adaptive Huber regression in (5.1). Furthermore, we can specialize R by adopting the Nesterov accelerated method, which gives R = Ö(d + d zi aito K a01o).
Proof. See Appendix E for a detailed proof.
Such complexity allows us to focus on the complexity introduced by the RI. algorithm rather than the optimization subroutine for solving adaptive Huber regression. Compared to that of LSVI-UCB++
[15], (d |A| 3 [ K), the extra term Ö O(H KRR) causes slightly worse computational time in terms of K. This is due to the absence of a closed-form solution of adaptive Huber regression in (5.1).
Thus extra optimization steps unavoidable. Nevertheless, Nesterov accelerated method gives
δ O (K2TF) 2(1+))
1:22
with respect to K, which implies the computational complexity of HEAVY-LSVI-UCE
better than that of LSVI-UCB [22], Ō(d (A(HK? in terms of K, thanks to the rare-switching updating policy. We conduct numerical experiments in Appendix B to further corroborate the computational efficiency of adaptive Huber regression.
5.3 Regret Bound
Theorem 5.2 (Informal), For the linear MDPs with heavy-tailed rewards defined in Section 2.2, we parameters in Algorithm 3 as follows: ÅR = df max { B², W2). \v =1/H2, Pmin, Omin, Co Ct. To. 7o. BRe, 18, BR. By in Appendix F.1. Then for any (0, 1). with probability at least - 166, the regret of HEAVY-LSVI-UCT is bounded by
Regret (K) = Ō (dVHUKK +dVHV*K,
where (0, 4 min U4, V* Vin V} with Ug V defined in Appendix F.2 and H,U, defined in Assumption 2.7.
Proof. See Appendix F.2 for a formal version of Theorem 5.2 and its detailed proof.

---

Quantities 21,,, V We make few explanations for the quantities 21", V On one hand, 22 is upper bounded by u, which is the upper bound of the sum of the (1 e)-th central moments of reward functions along a single trajectory. On the other hand, U is no more than Ug which is the sum of the (1 + e)-th central moments with respect to the averaged occupancy measure of the first K episodes. V is defined similar to LI", but measures the randomness of transition probabilities.
Remark 5.3. When
1, we can show that this regret is bounded by O(dyHg* K), where G" is an aariance-dependent quantity defined by Li and Sun [26]. Thus, our result recovers their variance-aware regret bound. See Remark F. 15 in Appendix F.2 for detailed proof.
To demonstrate the optimality of our results and establish connections with existing literature, can specialize Theorem 5.2 to obtain the worst-case regret [22, 2, 15] and first-order regret [33].
Corollary 5.4 (Worst-case regret), For the linear MDPs with heavy-tailed rewards defined in Sec- tion 2.2 and for any 8 E (0, 1), with probability at least - 166, the regret of HEAVY-LSVI-UCB is bounded by
Ō(dH The + dd Hs)..).
Proof. Notice U and V are upper bounded by HV and H.2 (total variance lemma in Jin al. [21]) respectively. When H. = H, and we treat Vn as a constant, the result follows.
Next, we give the regret lower bound of linear MDPs with heavy-tailed rewards in Theorem 5.5, which shows our proposed HEAVY-LSVI-UCD is minimax optimal in the worst case.
Theorem 5.5. For any algorithm, there exists an H--pisodic,, d-dimensional linear MDP with heavy-tailed rewards such that for any K, the algorithm's regret
Q(HH rो. + dvHOK).
Proof. Intuitively, the proof of Theorem 5.5 follows from a combination of the lower bound con- structions for heavy-tailed linear bandits in Shao et al. [31] and linear MDPs in Zhou et al. [42]. Sec Appendix G for a detailed proof.
Theorem 5.5 shows that for sufficiently large K, the reward term dominates in the regret bound. Thus, in heavy-tailed settings, the main difficulty is learning the reward functions.
Corollary 5.6 (First-order regret). For the linear MDPs with heavy-tailed rewards defined in Sec- tion 2.2 and for any 8 (0, 1), with probability at least 165, the regret of HEAVY-LSVI-UCB is bounded by
Hid/HU'' + d K
And when the rewards are uniformly bounded in [0, 1], the result is reduced to the first-order regret bound of O(d//(VV K).
Proof. See Section F33 for a detailed proof.
Our first-order regret improves the state-of-the-aa result
is minimax optimal in the worst case since V < H. And [26] by factor of VH.
6 Conclusion
In this work, we propose two computationally efficient algorithms for heavy-tailed linear ban- dits and linear MDPs, respectively. Our proposed algorithms, termed HEAVY-OFUL and HEAVY-LSVI-UCB, are based on a novel normalozdd concentration inequality for adaptive Huber regression, which may be of independent interest. HEAVY-OFUL and HEAVY-LSVI- UCB achieve minimax optimal and eestance-dependeed We also provide a lower bound for linear MDPs with heavy-tailed rewards to demonstrate the opti- mality of HEAVY-LSVI-UCH rewards in RL with function approximation and provide a new algorithm for this setting which both statistically and computationally efficient.
regret bounds scaling with the central moments.
To the best of our knowledge, we are the first study heavy-tailed
10

---

Acknowledgments
Liwei Wang is supported in part by NSF IIS 2110170, NSF DMS 2134106, NSF CCF 2212261, NSF IIS 2143493, NSF CCF 2019844, NSF IIS 2229881. Lin E. Yang is supported in part by NSF grant 2221871, and an Amazon Research Grant.
References
[1] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, volume 24, 2011.
[2] Alekh Agarwal, Yujia Jin, and Tong Zhang. VOQL: Towards optimal regret in model-free rl with nonlinear function approximation. The Thirty Sixth Annual Conference on Learning Theory, pages 987-1063, PMLR, 2023.
[3] Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008
[4] Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based rein- forcement learning with aalue-targeted regression. International Conference on Machine Learning, pages 463-474. PMLR, 2020.
[5] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272.
PMLR, 2017.
[6] Sujay Bhatt, Guanhua Fang, Ping Li, and Gennady Samorodnitsky. Nearly optimal catoni's m-estimator for infinite variance. In International Conference on Machine Learning, pages 1925-1944. PMLR, 2022.
[7] Sébastien Bubeck, Nicolo Cesa-Bianchi, and Gábor Lugosi. Bandits with heavy tail. IEEE Transactions on Information Theory, 59(11):7711-71) 2013.
[8] Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4):3313357,20 2015.
[9] Olivier Catoni. Challenging the empirical mean and empirical variance: a deviation study. In Annales de I'IH Probabilités et statistiques, volume 48, pages 1148-1185, 2012.
[10] Peng Chen, Xinghu Jin, Xiang Li, and Lihu Xu. A generalized catoni's m-estimator under finite a-th moment assumption with a E(1, 2). Electronic Journal of Statistics, 15 15(2):5523-5544
2021.
[11] Hana Choi, Carl F Mela, Santiago R Balseiro, and Adam Leary. Online display advertising markets: A literature review and future directions. Information Systems Research, 31(2): 556-575, 2020.
[12] Rama Cont. Empirical properties of asset returns: stylized facts and statistical issues. Quantita- live finance 1(2):223, 2001.
[13] David Freedman. On tail probabilities for martingales. the Annals of Probability, pages 100-118, 1975.
[14] A Ben Hamza and Hamid Krim. Image denoising: A nonlinear robust statistical approach. IEEE transactions on signal processing, (9(12):04553055 2001.
[15) Jiafan He, Heyang Zhao, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforce- ment learning for linear markov decision processes. In International Conference on Machine Learning, pages 12790-12822. PMLR, 2023.
[16] Pihe Hu, Yu Chen, and Longbo Huang. Nearly minimax optimal reinforcement learning with linear function approximation, In International Conference on Machine Learning, pages 8971-9019, 2022.

---

[17] Peter J Huber. Robust estimation of a location parameter. The Annals of Mathematical Statistics, pages 73-101, 1964.
[18] John Hull. Risk management Sons, 2012.
institutions, + Web Site, volume 733. John Wiley &
[19] Charles Jebarajakirthy, Haroon Iqbal Maseeh, Zakir Morshed, Amit Shankar, Denni Arli, and Robin Pentecost. Mobile advertising: A systematic literature review and future research agenda. International Journal of Consumer Studies, 45(6):1258-12911 1291, 2021.
[20] Zeyu Jia, Lin Yang, Csaba Szepesvari, and Mengdi Wang. Model- reinforcement learning with value-targeted regression. In Learning for Dynamics and Control, pages 666-686. PMLR, 2020.
[21] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably efficient? Advances in neural information processing systems, 31, 2018.
[22] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137- 2143. PMLR, 2020.
[23] Yeoneung Kim, Insoon Yang, and Awang-SSng Jun. Improved regret analysis for variance- adaptive linear bandits and horizon-free linear mixture mdps. Advances in Neural Information Processing Systems, 15:1060-1172, 2022.
[24] Johannes Kirschner and Andreas Krause. Information directed sampling and bandits with heteroscedastic noise. In Conference On Learning Theory, pages 358- 3884..4 PMLR, 2018.
[25] Gen Li, Changxiao Cai, Yuxin Chen, Yuting Wei, and Yuejie Chi. Is q-learning minimax optimal? tight sample complexity analysis. Operations Research, 2023.
[26] Xiang Li and Qiang Sun. Variance-aware robust reinforcement learning with linear function approximation with heavy-tailed rewards. arXiv preprint arXiv:2303.05606, 2023.
[27] Gábor Lugosi and Shahar Mendelson. Mean estimation and regression under heavy-tailed distributions: A survey. Foundations of Computaaiional Mathematics, 19(5):1145-113 2019.
[28] Andres Munoz Medina and Scott Yang. No-regret algorithms for heavy-tailed linear bandits. In International Conference on Machine Learning, pages 1642-1650, PMLR, 2016.
[29] Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of rein- forcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pages 2010-2020. PMLR, 2020.
[30] Martin Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
[31] Han Shao, Xiaotian Yu, Irwin King, and Michael Lyu. Almost optimal algorithms for linear stochastic bandits with heavy-tailed payoffs. Advances in Neural Information Processing Systems, 31, 2018
[32] Qiang Sun, Wen-Xin Zhou, and Jianqing Fan. Adaptive huber regression. Journal of the American Statistical Association, 1 2555525) 2020.
[33] 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, pages 22384-22429 PMLR, 2022.
[34] Bo Xue, Guanghui Wang, Yimu Wang, and Lijun Zhang. Nearly optimal regret for stochastic linear bandits with heavy-tailed payoffs. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pages 2936-2942, International Joint Conferences on Artificial Intelligence Organization, 2020.
12

---

[35] Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning. pages 6995-7004. PMLR, 2019.
[36] 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, pages 7304-7312. PMLR, 2019.
[37] Zihan Zhang. Jiaqi Yang. Xiangyang Ji, and Simon S Du. Improved variance-aware confidence sets for linear bandits and linear mixture mdp. Advances in Neural Information Processing Systems, 34:4342-4355, 2021.
[38] 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. In Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 4977-5020. PMLR, 2023.
[39] Han Zhong and Tong Zhang. theoretical analysis of optimistic proximal policy optimization in linear markov decision processes. arXiv preprint vrXiv:2305.08841 2023.
[40] Han Zhong, Jiayi Huang, Lin Yang. and Liwei Wang. Breaking the moments condition barrier: No-regret algorithm for bandits with super heavy-tailed payoffs. Advances in Neural Information Processing Systems, 34:157 157200, 2021.
[41] Dongruo Zhou and Quanquan Gu. Computationally efficient horizon-free reinforcement learning for linear mixture mdps. Advances in neural information processing xystems, 35:36337-36349, 2022.
[42] Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pages 5532-4576. PMLR, 2021.
[43] Runlong Zhou, Zhang Zihan, and Simon Shaolei Du. Sharp variance-dependent bounds in reinforcement learning: Best of both worlds in stochastic and deterministic environments. In International Conference on Machine Learning, pages 42878 42914. PMLR, 2023.
[44] Vincent Zhuang and Yanan Sui. No-regret reinforcement learning with heavy-tailed rewards. In International Conference on Artificial Intelligence and Statistics, pages 3385-3393. PMLR, 2021.
13


Reviews:
[{"review_id": "3SliNVU11s", "reviewer": "Reviewer_rJ6d", "summary": "The paper considers the problem of linear bandits and linear MDPs, when the noise may be heavy tailed. The main technical tool that they use is the Huber regressor, that enables them to detect extremal noise points that are less informative, and be more robust to these. They show how this regressor can be incorporated into optimistic algorithms to provide sublinear regret bounds.", "questions": "1. The setup being considered here with heavy-tailed additive noise is different than the situation where the rewards themselves are heavy-tailed. In the current case, the problem is more one of outlier detection to be robust to these extremal noise events. But in the other case, if an arm has a heavy tailed reward, it may be desirable to pull because there is the potential for receiving very high reward from this arm relative to other arms (i.e if an arm like a lottery ticket with low rewards with high probability but immense rewards with small probability).\n\nI am concerned that conflating these two problems may lead to confusion. Could the authors comment on this distinction? And if the authors agree, I would appreciate if the title were changed to accurately describe the setup and the distinction were made clear in the text.\n\n2. Could you comment on whether a different definition of heavy-tailed in terms of tail probabilities ", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "Quality: Claims are sound, and arguments appear to check out. The paper is well-contextualized in the literature.\n\nSignificance: Problem is relevant to practitioners, and theoretical tools may be reapplied in similar online problems elsewhere as well.\n\nOriginality: The technical work required to incorporate the huber regressor into the optimistic algorithms is nontrivial, and the efforts are appreciated.", "weaknesses": "Clarity: While the writing is well-organized, it is quite dense at times and a slog to parse through: for instances, Sections 2.2 and Section 5. It would be useful to move some things into the appendix and instead of encapsulating commentary into remark environments, including them in the main text to introduce more flow that would make it easier for the reader.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your being positive to our work. We also thank you for the advice on the organization of the paper. We will make some adjustments to make it easier for reading in the next revision.\n\n### Setup with heavy-tailed additive noise\n\nThe assumption with heavy-tailed additive mean-zero noise is standard in online regression settings, e.g., Section 3 of [1]. Let us consider a random variable $Y\\in\\mathbb{R}$ with the following structure: $Y=\\mu+\\varepsilon$ with $\\mu$ being a constant and $\\varepsilon$ being a heavy-tailed mean-zero noise. Then $Y$ itself is heavy-tailed as well with mean $\\mu$ since its central moment is bounded. The effort is made to recover the mean $\\mu$ in the presence of heavy-tailed noise $\\varepsilon$.\n\nIn addition, we believe our work has little to do with outlier detection. It is an interesting question whether Huber loss can be utilized in the field of outlier detection. However, it is definitely beyond our work.\n\nYou are right, the reward of a lottery ticket is a good example of heavy-tailed distributions. While its magnitude can be extremely large, its mean is supposed to be small. If the agent aims to get a high reward from a single pull of arm, she may choose the arm with a heavy-tailed reward since there is the potential for receiving very high reward from this arm relative to other arms. However, this introduces a different problem from ours. Since our goal is to get the most benefit in the long run, we wish to pull the arm with the maximum expected reward.\n\n### Definition of heavy-tailed distribution in terms of tail probabilities\n\nGood questions. We say a mean-zero random variable $\\varepsilon\\in\\mathbb{R}$ is heavy-tailed if it satisfies $\\mathbb{E}[|\\varepsilon|^{1+\\epsilon}]=\\nu^{1+\\epsilon}<\\infty$ with $\\epsilon\\in(0,1]$, which implies $\\mathbb{P}(|\\varepsilon|>x) \\le \\mathbb{E}[|\\varepsilon|^{1+\\epsilon}]/x^{1+\\epsilon} = \\nu^{1+\\epsilon}/x^{1+\\epsilon}$ for any $x>0$ by Markov's inequality. Symmetrically, if the tail probability of $\\varepsilon$ has the form above, we have $\\mathbb{E}[|\\varepsilon|^{1+\\epsilon}] = \\int_0^\\infty \\mathbb{P}(|\\varepsilon|>x) \\mathrm{d}x = \\nu^{1+\\epsilon} \\int_0^\\infty 1/x^{1+\\epsilon} \\mathrm{d}x = \\nu^{1+\\epsilon}$. Thus, the definition of heavy-tailed distribution in terms of tail probabilities follows.\n\n\n\n[1] Abbasi-Yadkori, Yasin, Dávid Pál, and Csaba Szepesvári. \"Improved algorithms for linear stochastic bandits.\" Advances in neural information processing systems 24 (2011)."}, {"review_id": "biZAEewss3", "reviewer": "Reviewer_6prC", "summary": "This paper first addresses Reinforcement learning (RL) with function\napproximation in the presence of heavy-tailed noises whose central moment is known. In\ngeneral, these online learning problems rely on the self-normalized inequality to construct a\nconfidence set of optimal parameter . However, the existing self-normalized inequalities\nhave a magnitude of noise term that is intractable with heavy-tailed noises. The authors\nsolve this problem by utilizing adaptive Huber regression and deriving a robust selfnormalized\ninequality without the noise magnitude term. By using the proposed selfnormalized\ninequality, they introduce two algorithms. The first algorithm, HEAVY-OFUL, is\ndesigned for linear bandits and shown to be minimax optimal. Building upon HEAVYOFUL,\nthey presents HEAVY-LSI-UCB for linear MDPs, which has a better first-order\nregret bound than previous works. Furthermore, they provide the minimax lower regret\nbound in linear MDPs with heavy-tailed noises, which implies the minimax optimality of\nHEAVY-LSI-UCB in the worst case.", "questions": "- Since the paper emphasizes the computational contributions of the proposed algorithms comparing with the existing ones, I think empirical results are needed. Can you provide experiments related to this?\n- If possible, please discuss computational aspects of the proposed algorithms.\n- In my understanding, the essential key in handling heavy-tailed noises is the robust self-normalized inequality (Theorem 3.3). However, it seems that the inequality involves the term, $b$, that requires prior information about central moment. While the closet work [1] suppose similar assumption, I think this is a strong condition. Can this be relaxed?\n- In line 219, the authors claim when $\\epsilon=1$ and $\\nu=0$, $\\forall t$, the regret upper bound of HEAVY-OFUL matches the lower bound of K-armed contextual bandit $\\Omega(d)$ [3]. Can you reconsider this argument? To my knowledge, the regret bound proposed in\n[3] is $\\Omega(\\sqrt{dT})$, not $\\Omega(d)$. Moreover, the settings are different each other in that [3] addresses finite-armed bandits, while this work deals with (possibly) infinite-armed bandits.\n\n[1]. Xiang Li and Qiang Sun. Variance-aware robust reinforcement learning with linear function approximation with heavy-tailed rewards. arXiv preprint arXiv:2303.05606, 2023\n[2]. Andrew J Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson. First order regret in reinforcement learning with linear function approximation: A robust\nestimation approach. In International Conference on Machine Learning, pages 22384–22429. PMLR, 2022.\n[3]. Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208–214. JMLR Workshop and Conference Proceedings, 2011.", "limitations": "There are no limitations discussed in the manuscript.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper is the first attempt to deal with heavy-tailed RL with function\napproximation.\n-  (Optimality) The regret bound of HEAVY-OFUL, is minimax optimal in both stochastic and deterministic linear bandits with heavy-tailed rewards. In addition, the regret bound of HEAVY-LSVI-UCB, recovers the previous variance-aware regret in [1] and improves the existing instance-dependent regrets in linear MDPs [1, 2].\n- (Originality) To address the heavy-tailed rewards, the novel robust self-normalized\ninequality is established.", "weaknesses": "- (Computational costs) The first concern is the practical usage of the proposed\nalgorithms. As the authors noted, the regret analyses of the algorithms inherently\ndepend on the robust self-normalized inequality (Theorem 3.3), which bounds the\ndeviation of estimated parameter and the optimal parameter . However, I believe\nthe fact that is obtained from adaptive Huber regression is problematic since it\nrequires iterative optimization steps due to the absence of a closed form for (Line 5\nof Alg. 1). Indeed, the proposed algorithms (Alg. 2, 3) contain the additional iterative\nalgorithm (Alg. 1) to ensure their theoretical results, and thus share the intrinsic\ndrawback of Huber regression, which is the linear computational complexity per\niteration. In particular, HEAVY-LSVI-UCB utilizes the adaptive Huber regression in\norder to optimize both rewards and central moments.\n- (Absent experiments) There are no experiments supporting the theoretical results of\nthe proposed algorithms and addressing concerns about computational costs, even in\nsimple synthetic problems.\n- (Assumption) The authors assumed that the central moment of rewards is known.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for raising the concerns.\n\n### Computational complexity\n\nWe say an algorithm is computationally efficient if the computational complexity scales polynomially to the parameters of the problem, e.g., $d,H,K$ of the linear MDP. We provide the computational complexity of Heavy-LSVI-UCB (Algorithm 3) here. For the linear MDPs with heavy-tailed rewards defined in Section 2.2, the computational complexity of Heavy-LSVI-UCB is $\\tilde{O}(HK\\mathcal{R} + d^4|\\mathcal{A}|H^3K)$. Here $\\tilde{O}(\\mathcal{R})$ is the cost of the optimization algorithm for solving adaptive Huber regression in (5.1). Such a complexity allows us to focus on the complexity introduced by the RL algorithm rather than the optimization subroutine for solving adaptive Huber regression. Compared to that of LSVI-UCB++, $\\tilde{O}(d^4|\\mathcal{A}|H^3K)$, the extra term $\\tilde{O}(HK\\mathcal{R})$ causes a slightly worse computational time in terms of $K$. This is due to the absence of a closed form solution of adaptive Huber regression in (5.1). Thus extra optimization steps are unavoidable. Nevertheless, since (5.1) is a convex optimization problem and thus can be solved efficiently, we can specialize $\\mathcal{R}$ by adopting Nesterov accelerated method, which gives $\\mathcal{R}=\\tilde{O}(d+d^{-\\frac{1-\\epsilon}{2(1+\\epsilon)}} H^{\\frac{1-\\epsilon}{2(1+\\epsilon)}} K^{\\frac{1+2\\epsilon}{2(1+\\epsilon)}})$. It implies the computational complexity of Heavy-LSVI-UCB is  better than that of LSVI-UCB, $\\tilde{O}(d^2|\\mathcal{A}|HK^2)$, with respect to $K$, thanks to the rare-switching updating policy. We thank the reviewers for raising the question of computational complexity and we will include it in the next revision. We provide the proof in global rebuttal due to lack of space.\n\n### Experiments\n\nNote that our paper focuses on the theoretical understanding of the heavy-tailed noise in bandits and RL environments. With that being said we are happy to include experimental study in our future versions. We also provide the computational complexity for solving adaptive Huber regression as $\\tilde{O}(K^{\\frac{1+2\\epsilon}{2(1+\\epsilon)}})$ in terms of $K$, where the standard Nesterov accelerated method suffices. To address the concerns about the empirically test of our proposed estimator based on adaptive Huber regression, we can refer to [1], which contains an implementation of a similarly designed estimator. It is indeed efficient in numerical studies.\n\n### Assumption that the central moments of rewards are known\n\nWe do NOT assume the central moments of rewards are known in heavy-tailed linear MDPs, which is the main difficulty of achieving instance-dependent regret bound. To address this challenge, we use adaptive Huber regression to estimate them (See Section 5.1). It is worth noting that Heavy-LSVI-UCB actually only requires the upper bound of the underlying moments. And see line 189 for more discussion on the moment parameter $b$. Thanks for raising the concern, we will highlight it in the next revision.\n\n### Lower bound of deterministic linear bandits\n\nPlease note that we consider deterministic linear bandits in line 219. Thus the central moments of the reward functions vanish, i.e., $\\nu_t=0$. And we set $\\epsilon=1$ to achieve the $\\tilde{O}(d)$ regret. You are right, the settings in [2] are different than ours since they consider finite-armed bandits with light-tailed noise. So their lower bound is not applicable to heavy-tailed linear bandit problems. We will clarify this in the next revision.\n\nIn fact, the $\\Omega(d)$ lower bound for deterministic linear bandits is straightforward. Consider the decision set $\\mathcal{D}=\\lbrace e_i \\rbrace_{i\\in[d]}$, where $e_i$ denotes the $i$-th unit basis in $\\mathbb{R}^d$. Each pull of arm can only obtain the information of a single coordinate. Since coefficient $\\theta^*$ lies in $d$-dimensional space, even if the rewards are deterministic, $d$ pulls for exploration are unavoidable.\n\n\n\n[1] Sun, Qiang, Wen-Xin Zhou, and Jianqing Fan. \"Adaptive huber regression.\" *Journal of the American Statistical Association* 115.529 (2020): 254-265.\n\n[2] Chu, Wei, et al. \"Contextual bandits with linear payoff functions.\" *Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics*. JMLR Workshop and Conference Proceedings, 2011."}, {"review_id": "lNbyUfs5Sr", "reviewer": "Reviewer_ZTTm", "summary": "In this paper, reinforcement learning problem is considered in the episodic setting for linear bandits and linear MDPs under heavy-tailed rewards with potentially infinite variance. Based on adaptive Huber regression and optimism in the face of uncertainty principle, the authors propose algorithms that utilize conditional reward variance.", "questions": "a)\tWhat happens in the absence of the realizability assumption in Assumption 2.6?\nb)\tThe paper [25] seems to be considering heavy-tailed rewards also, but with finite variance. As such, it would be fair to update the last column of Table 1 and 2 based on finiteness of the variance.", "limitations": "No substantial discussion on the limitations.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper looks technically sound, and the presentation of the material seems to be good with clearly stated assumptions and theorem statements.\n\nOn the technical side, the use of adaptive Huber regression in linear bandit and linear MDP setting to tackle heavy-tailed reward distributions is an interesting idea.", "weaknesses": "In Assumption 2.6, the centralized moments of order $1+\\epsilon$ of the random rewards at each step are assumed to be realizable for each state-action pair, which looks highly unrealistic. Also, in addition to the regret bounds, it would be interesting to see empirical evaluations of the proposed algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your positive comments!\n\n### Realizable central moments assumption\n\nIn Assumption 2.6, we assume the $(1+\\epsilon)$-central moments of reward functions have linear structure. This assumption is standard in current linear MDP literature where instance-dependent (variance-aware) regrets are achieved (see also Remark 2.7). In the absence of Assumption 2.6, we cannot estimate $(1+\\epsilon)$-central moments of reward functions for each state-action pair, which is crucial to achieving such an instance-dependent regret. To be more specific, since adaptive Huber regression needs the knowledge of the $(1+\\epsilon)$-central moments, without such a realizable assumption, there is no way to estimate them. And the best we can do is to use the upper bound of the moments $\\nu_R^{1+\\epsilon}$ instead, which only gives a worst-case regret as in Corollary 6.5. We leave it as future work to propose a computationally efficient algorithm without the knowledge of moments for the heavy-tailed linear bandits.\n\n### Experiments\n\nNote that our paper focuses on the theoretical understanding of the heavy-tailed noise in bandits and RL environments. With that being said we are happy to include experimental study in our future versions. We also provide the computational complexity for solving adaptive Huber regression as $\\tilde{O}(K^{\\frac{1+2\\epsilon}{2(1+\\epsilon)}})$ in terms of $K$, where the standard Nesterov accelerated method suffices. To address the concerns about the empirically test of our proposed estimator based on adaptive Huber regression, we can refer to [1], which contains an implementation of a similarly designed estimator. It is indeed efficient in numerical studies.\n\n### Settings of finite-variance rewards\n\nYes, [25] provided the first variance-aware regret in the presence of finite-variance rewards. However, we focus on the heavy-tailed settings where the variance of the reward functions can be non-existent. Thanks for your suggestions, and we will add some footnotes in Table 1 and 2 in the next revision.\n\n\n\n[1] Sun, Qiang, Wen-Xin Zhou, and Jianqing Fan. \"Adaptive huber regression.\" *Journal of the American Statistical Association* 115.529 (2020): 254-265."}, {"review_id": "WhWAGnW3hV", "reviewer": "Reviewer_gEhD", "summary": "main contributions include two-folds. For heavy-tailed payoffs, design heavy-tailed linear bandits, derive the variance-dependent T-round regret; In terms of Linear MDPs, instance-dependent K-episode regret is acquired. All paper results substantially depend on Huber loss regression techniques.", "questions": "Since the author believes that their proposed algorithm is computationally effective, why not provide specific examples to demonstrate the practical application effect of the proposed algorithm?", "limitations": "the authors adequately addressed the limitations.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "For heavy-tailed linear bandits, the author proposed how to tune the robustification parameter that balances bias and robustness on the fly.\nfor linear MDPs with bounded rewards problem, the author employs separate estimation techniques to handle heavy-tailed rewards and transition kernels, i.e, utilizing adaptive Huber regression to estimate heavy-tailed rewards and weighted ridge regression to estimate the expected next-state value functions.", "weaknesses": "The derived regrets depend on the feature dimension, the number of rounds, the variance or central moment of the reward at the t-th round. simultaneously. It seems to have worsened the obtained results comparing to the previous research works. the overall regret scales with feature dimension, again restricting this proposed approach to small dimension problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review.\n\n### Some corrections of the reviewer\n\n> For heavy-tailed payoffs, design heavy-tailed linear bandits, derive the variance-dependent $T$-round regret;\n\nIn the settings where $\\epsilon<1$, the variances of reward functions do not exist. And our regret bound actually relies on the $(1+\\epsilon)$-central moment $\\lbrace \\nu_t^{1+\\epsilon} \\rbrace_{t\\in[T]}$. We refer the reviewer to line 48 to 54 for more details.\n\n> For linear MDPs with bounded rewards problem, ...\n\nWe consider linear MDPs with heavy-tailed rewards, where the magnitude of reward can be infinite. The reviewer maybe means the cumulative expected rewards are bounded, as in Assumption 2.8.\n\n### Worse results\n\nWe respectfully disagree with the reviewer's argument that our work achieves worse results compared with previous works. Since we are the first to establish such regret bounds in the presence of heavy-tailed rewards, none of the previous research works are readily applicable to heavy-tailed settings. In contrast, our results are shown to be minimax optimal, can be used directly to deal with light-tailed rewards by setting $\\epsilon=1$ and recover or improve the SOTA results (See also line 69 to 71).\n\n### Computational complexity and experiments\n\nWe say an algorithm is computationally efficient if the computational complexity scales polynomially to the parameters of the problem, e.g., $d,H,K$ of the linear MDP. We provide the computational complexity of Heavy-LSVI-UCB (Algorithm 3) here. For the linear MDPs with heavy-tailed rewards defined in Section 2.2, the computational complexity of Heavy-LSVI-UCB is $\\tilde{O}(HK\\mathcal{R} + d^4|\\mathcal{A}|H^3K)$. Here $\\tilde{O}(\\mathcal{R})$ is the cost of the optimization algorithm for solving adaptive Huber regression in (5.1). Such a complexity allows us to focus on the complexity introduced by the RL algorithm rather than the optimization subroutine for solving adaptive Huber regression. Compared to that of LSVI-UCB++, $\\tilde{O}(d^4|\\mathcal{A}|H^3K)$, the extra term $\\tilde{O}(HK\\mathcal{R})$ causes a slightly worse computational time in terms of $K$. This is due to the absence of a closed form solution of adaptive Huber regression in (5.1). Thus extra optimization steps are unavoidable. Nevertheless, since (5.1) is a convex optimization problem and thus can be solved efficiently, we can specialize $\\mathcal{R}$ by adopting Nesterov accelerated method, which gives $\\mathcal{R}=\\tilde{O}(d+d^{-\\frac{1-\\epsilon}{2(1+\\epsilon)}} H^{\\frac{1-\\epsilon}{2(1+\\epsilon)}} K^{\\frac{1+2\\epsilon}{2(1+\\epsilon)}})$. It implies the computational complexity of Heavy-LSVI-UCB is  better than that of LSVI-UCB, $\\tilde{O}(d^2|\\mathcal{A}|HK^2)$, with respect to $K$, thanks to the rare-switching updating policy. We thank the reviewers for raising the question of computational complexity and we will include it in the next revision. We provide the proof in global rebuttal due to lack of space.\n\nAs for the experiments, please note that our paper focuses on the theoretical understanding of the heavy-tailed noise in bandits and RL environments. With that being said we are happy to include experimental study in our future versions. We also provide the computational complexity for solving adaptive Huber regression as $\\tilde{O}(K^{\\frac{1+2\\epsilon}{2(1+\\epsilon)}})$ in terms of $K$, where the standard Nesterov accelerated method suffices. To address the concerns about the empirically test of our proposed estimator based on adaptive Huber regression, we can refer to [1], which contains an implementation of a similarly designed estimator. It is indeed efficient in numerical studies.\n\n\n\n[1] Sun, Qiang, Wen-Xin Zhou, and Jianqing Fan. \"Adaptive huber regression.\" *Journal of the American Statistical Association* 115.529 (2020): 254-265."}]

Author rebuttal:
### Proof of computational complexity

First, to compute $\theta_{k-1,h}$ in line 6 of Algorithm 3, we notice the loss function in (5.1) is $\lambda_R$-strongly convex and $(\lambda_R+K/\nu_\mathrm{min}^2)$-smooth, so there are plenty of convex optimization algorithms available. For example, Nesterov accelerated method can be used. The number of iteration of Nesterov's method is ${O}(\sqrt{\beta/\alpha}\log(R^2/\epsilon))$ with one derivation ($O(d)$ operations) per iteration [1]. Here the loss function is supposed to be $\alpha$-strongly convex and $\beta$-smooth. $R$ is the maximum distance of two points and $\epsilon$ is the precision. Thus the total computational cost is $\tilde{O}(HK\mathcal{R})$ with $\mathcal{R} = \tilde{O}(d\sqrt{1+\frac{K}{\lambda_R\nu_\mathrm{min}^2}})=\tilde{O}(d+d^{-\frac{1-\epsilon}{2(1+\epsilon)}} H^{\frac{1-\epsilon}{2(1+\epsilon)}} K^{\frac{1+2\epsilon}{2(1+\epsilon)}})$.

Second, to evaluate the updated action-value function $Q^k_h(s,a)$ in line 10 of Algorithm 3 for a given pair $(s,a)$, we take the minimum over at most $\tilde{O}(dH)$ action-value functions (See Lemma F.8) with $O(d^2)$ operations (Using Sherman-Morrison formula to compute $H_{k-1,h}^{-1}$ and $\Sigma_{k-1,h}^{-1}$) for each function. Thus it takes $\tilde{O}(d^3H)$ to evaluate the updated action-value function. As a result, to compute $\hat w_{k-1,h}$ in line 6 of Algorithm 3, notice $\hat w_{k,h}=\Sigma_{k,h}^{-1} \sum_{i=1}^k \sigma_{i,h}^{-2} \phi_{i,h} V^k_h(s_{i,h+1})$, if $V^k_h$ remains unchanged, we only need to compute the new term $\sigma_{k,h}^{-2} \phi_{k,h} V^k_h(s_{k,h+1})$, which takes $\tilde{O}(d^3|\mathcal{A}|H)$ computational time. Else if $V^k_h$ is updated, we need to recalculate $\lbrace V^k_h(s_{i,h+1}) \rbrace_{i\in[k]}$, which takes $\tilde{O}(d^3|\mathcal{A}|HK)$ computational time. Note the number of updating episode is at most $\tilde{O}(dH)$ and the length of each episode is $H$, so the total computational cost is $\tilde{O}(d^4|\mathcal{A}|H^3K)$.

Last, to take action $a_{k,h}$ in line 19 of Algorithm 3, we need to compute $\lbrace Q^k_h(s_{k,h},a) \rbrace_{a\in\mathcal{A}}$ and take the maximum, which takes $\tilde{O}(d^3|\mathcal{A}|H)$ time, incurring a total cost of $\tilde{O}(d^3|\mathcal{A}|H^2K)$. Finally, combining the total costs above gives the computational complexity of Heavy-LSVI-UCB.



[1] Bubeck, Sébastien. "Convex optimization: Algorithms and complexity." *Foundations and Trends® in Machine Learning* 8.3-4 (2015): 231-357.

Meta-review: This paper studies linear MDPs in the finite horizon setting where the rewards may not only be unbounded, but heavy-tailed. They propose an algorithm that leverages robust mean estimation that naturally handles the heavy-tailed rewards for linear bandits, and then generalize it to linear MDPs. If this paper only took existing works and tacked on robust mean estimation, matching their rates in the bounded mean case, it would be unsatisfying and borderline. However, these authors go far beyond this to propose algorithms that are not only minimax optimal, but also obtain state of the art instance-dependent regret bounds that improve upon existing work even in the worst-case. Moreover, the algorithm is computationally efficient, a property which is frequently lost when addressing robust mean estimation. The results are clearly described in the context with the literature and lower bounds. Any concerns that were brought up by the reviewers were either confirmed to be addressed by the reviewers, or satisfied the AC.
Decision: Accept (poster)