Provably Robust Temporal Difference Learning for Heavy-Tailed Rewards
Authors: Semih Cayci
Atilla Eryilmaz
Venue: NeurIPS 2023 poster (2023)
Keywords: temporal difference learning
natural actor-critic
reinforcement learning
policy evaluation
policy gradient
markov decision processes
TL;DR: In many RL applications, reward is heavy-tailed with infinite variance, and TD learning does not converge. To address this, we propose robust variants of TD learning and natural actor-critic, and prove their convergence with finite-time bounds.

Abstract: In a broad class of reinforcement learning applications, stochastic rewards have heavy-tailed distributions, which lead to infinite second-order moments for stochastic (semi)gradients in policy evaluation and direct policy optimization. In such instances, the existing RL methods may fail miserably due to frequent statistical outliers. In this work, we establish that temporal difference (TD) learning with a dynamic gradient clipping mechanism, and correspondingly operated natural actor-critic (NAC), can be provably robustified against heavy-tailed reward distributions. It is shown in the framework of linear function approximation that a favorable tradeoff between bias and variability of the stochastic gradients can be achieved with this dynamic gradient clipping mechanism. In particular, we prove that robust versions of TD learning achieve sample complexities of order $\mathcal{O}(\varepsilon^{-\frac{1}{p}})$ and $\mathcal{O}(\varepsilon^{-1-\frac{1}{p}})$ with and without the full-rank assumption on the feature matrix, respectively, under heavy-tailed rewards with finite moments of order $(1+p)$ for some $p\in(0,1]$, both in expectation and with high probability. We show that a robust variant of NAC based on Robust TD learning achieves $\tilde{\mathcal{O}}(\varepsilon^{-4-\frac{2}{p}})$ sample complexity. We corroborate our theoretical results with numerical experiments.

Provably Robust Temporal Difference Learning for Heavy-Tailed Rewards
Semih Cayci
Atilla Eryilmaz
Department of Mathematics
Department of Electrical and Computer Engineering
RWTH Aachen University
The Ohio State University Columbus, OH 43210 eryilmaz. 28osu. edu
Aachen, Germany cayci@mathc. www.hhachhhh.aaha...amaaaaaaaae.
Abstract
In broad class of reinforcement learning applications, stochastic rewards have heavy-tailed distributions, which lead to infinite second-order moments for stochas- tic (semi)gradients in policy evaluation and direct policy optimization. In such instances, the existing RL methods may fail miserably due to frequent statistical outliers. In this work, establish that temporal difference (TD) learning with a dynamic gradient clipping mechanism, and correspondingly operated natural actor-critic (NAC), can be provably robustified against heavy-tailed reward dis- tributions. It is shown in the framework of linear function approximation that a favorable tradeoff between bias and variability of the stochastic gradients be achieved with this dynamic gradient clipping mechanism. In particular, we prove that robust versions of TD learning achieve sample complexities of order O $) and ( ( }) with and without the full-rank assumption on the feature matrix, respectively, under heavy-tailed rewards with finite moments of order (1 + p) for some E (0, 1], both expectation and with high probability. We show that a robust variant of NAC based on Robust TD learning achieves Ö(E -- sample complexity. We corroborate our theoretical results with numerical experiments.
Introduction
In this paper, we develop framework for robust reinforcement learning in the presence of rewards with heavy-tailed distributions. Heavy-tailed phenomena, stemming from frequently observed statistical outliers, have been ubiquitous decision-making applications under uncertainty. To name a few examples, waiting times in wireless communication networks [44, 24, 58], completion times of SAT solvers [14], numerous payoff quantities (e.g., stock prices, consumer signals) in economics and finance [22, 35, 38, 37] exhibit heavy-tailed behavior. An important characteristic of heavy-taile random variables is the infinite order of higher moments, which stems from the frequently occurring outliers.
In reinforcement learning (RL), the goal is maximize expected total reward in Markov decision process (MDP) by continual interactions with the unknown and dynamic environment. Among policy optimization methods, Natural actor-critic (NAC) method and its variants [51, 30, 46, 17, 27, 29] have become particularly prevalent due to their desirable stability and versatility characteristics. emanating from the use of temporal difference (TD) learning as the critic for the policy evaluation component of the NAC operation. The existing theoretical analyses for temporal difference learning [4, 54] and natural policy gradient/actor-ere -riccc methods [62, 1, 57] assume that the stochastic gradients have finite second-orde moments, or even they are bounded. In particular, it is unknown whether natural actor-critic with function approximation robust for stochastic rewards of heavy- tailedd distributions with potentially infinite second-order moments. Furthermore, in practice, these methods
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

are prone to non-vann vanissiig and even increasing error under heavy-tailed reward distributions (see
Example 1). This motivates us for the following fundamental question in this paper:
Can temporal difference learning with function approximation be modified to provably achieve global optimality under stochastic rewards with heavy tails?
We provide an affirmative answer to the above question by proposing simple modification to the TD learning algorithm, which yields robustness against heavy tails. In partieular, we show that incorporating dynamic gradient clipping mechanism with a carefully-chosen sequence of clipping radii can provably robustify TD learning and NAC with linear function approximation, leading to global near-optimality even under stochastic rewards of infinite variance.
Example 1 (Failure of TD learning under heavy-tailed reward), In this example, we consider mandomly-generatee
duscounted-rewarr Markov reward process' (X,, Re), on a state space X with [X| = 64 states, with the discount factor 0.9 and the reward R,(X,) = (X,, N; E[N,) with sid Ne ~ P1r 1.4) for any L. In order to predict the value function, we use (projected) TD learning (see [4]) with linear function approximation based on Gaussian features of dimension
4 and projection radius p = 30. The performance results are shown in Figure 1. Since Rg is heavy-tailed
170.00
-.00
30/.00
170,22
200900
(a) Errors for TD Learning
(b) Errors for Robust TD Learning (c) Comparison of the expected errors
Figure 1: Non-convergen behavior of TD learning under heavy-tailed noise with tail index 1.4. Each faded green line is the MSE for an individual trial, and the solid lines with markers indicate the average mean squared error for TD learning and Robust TD learning.
with infinite variance, the existing convergence results for traditional TD learning, which assume that R2 has finite variance, not hold. Furthermore, Figure reveals that TD learning prone to non-varnishing and even increasing error in practice despite the projection step, iterate averaging and small learning rate, due to the statistical outliers that cause extremely large error often as indicated by non-negligible fraction of green lines in Figure la. On the other hand, with the same learning rate, projection radius and reward realizations, our robust variant of TD learning provides resilience against outliers (see Figure 1b), and leads to convergence in the expected behavior in Figure Ic.
Stochastic rewards with heavy-tailed distributions appear in many important applications. Below, we briefly provide two motivating applications that necessitate robust RL methods to handle heavy tails.
Application (1): Algorithm portfolios. In solving complicated problems such as Boolean satisfiability (SAT) and complete search problems, which appear in numerous applications [19, 43], multiple algorithmic solutions with different characteristics are available. The algorithm selection problem is concerned about the minimization of total execution times solve these problems [32, 49, 31], where different data distributions and machine characteristics, caused by recursive algorithms, are modeled as states, algorithm choices modeled actions, and the execution time of a selected algorithm is modeled as the cost (i.e., negative reward). It is well-known that the execution times, i.e., rewards, in the algorithm selection problem have heavy-tailed distributions with infinite-variance (e.g., Pareto(1, + p) with 0 < < as in [13]) similar to the case in Example [13, 15, 49]. Thus, algorithm selection problem requires robust techniques that consider here.
Application (2): Scheduling for wireless networks. The scheduling problem considers matching the users with random service demands to fading wireless channels (c.g., Gilbert-Ellin model) with stochastic transmission times so as to minimize the expected delay. A widely-adopted approach to
'The details of the setup, along with other numerical examples be found Section 4.

---

study the scheduling problem is to use MDPs (see, e.g., [40, 21, 10, 2J). It has been observed that the transmission times follow heavy-tailed distributions of infinite variance, due to various factors including the MAC protocol used, packet size, and channel fading [18, 58, 24, 23]. As such, solving this by using RI approach necessitates robust methods to handle heavy-tailed execution times.
Main contributions. Our main contributions in this paper contain the following.
Robust TD learning with dynamic clipping for heavy-tailed rewards. We propose Robust TD learning with a dynamic gradient clipping mechanism, and prove that this TD learning variant with linear function approximation can achieve arbitrarily small estimation error that vanishes at rates O(T 1ー=) and P) without and with full-rank assumption on the feature matrix, respectively, even for heavy-tailed rewards with moments of order 1 + for p E (0, 1]. Our proof techniques make use of Lyapunov analysis coupled with martingale techniques for robust statistical estimation in dynamical systems, and can be of independent interest in the analysis of first-order methods.
Robust NAC under heavy-tailed rewards. Based on Robust TD learning and the compatible function approximation result in [27]. we propose a robust NAC variant, and show that O - samples suffice to achieve 0 error under standard concentrability coefficient assumptions.
Hligh-probability error bounds. We provide high-probability (sub-Gaussian) error bounds for the robust NAC and TD learning methods in addition to the traditional expectation bounds.
From statistical viewpoint, introducing a vanishing bias to the semi-gradient via particular choices of dynamic gradient clipping, one can achieve robustness by eliminating the destructive impacts of statistical outliers even if the semi-gradient has infinite variance, leading to near optimality.
analysis in this work indicates favorable bias-variance tradeoff:: by
1.1 Related Work
Temporal difference learning. Temporal difference (TD) learning was proposed in [50], and has been the prominent policy evaluation method. The existing theoretical analyses of TD learning consider MDPs with bounded rewards [4, 7]. or rewards with finite variance [54], while we consider heavy-tailed rewards. Our analysis utilizes the Lyapunov techniques in [4].
Policy gradient methods. Policy gradient (PG), and its variant natural policy gradient (NPG) have attracted significant attention in RL [59, 52, 27]. Recent theoretical works investigate the local and global convergence of these methods in the exact case, with stochastic and bounded rewards [1, 57, 34, 39, 61]. As such, heavy-tailed rewards have not been considered in these works.
Bandits with heavy-tailed rewards. Stochastic bandit variants with heavy-tailed payoffs were studied in multiple works [6, 48, 33, 8). The stochastic bandit setting can be interpreted as a very simple single-state (i.e., stateless or memoryless) model-based and tabular RL problem. The model we consider in this paper is a model-free RL setting on an MDP with a large state space, which is considerably more complicated than the bandit setting.
Stochastic gradient descent with heavy-tailed noise. There has been an increasing interest in the analysis of SGD with heavy-tailed gradient noise recently [56, 11, 16], following the seminal work of [45]. In our work, we consider the RL problem, which has significantly different dynamics than stochastic convex optimization.
Robust mean and covariance estimation. In basic statistical problems of mean and covariance estimation [42, 41, 36) and regression [20], the traditional methods do not yield the optimal conver- gence rates for heavy-tailed random variables, which led to the development of robust mean and covariance estimation techniques (for reference, see [36, 28]). Our paper utilizes tools from robust mean estimation literature (particularly, truncated mean estimator analysis in [6]), but considers the more complicated problem of TD learning and policy optimization in a dynamic environment rather than static mean or covariance estimation problem with iid observations.
1.2 Notation
For symmetric matrix A E Rd Amin (A) denotes its minimum eigenvalue. B2 p) = {v R || - -vl2 S P) and [x) arg mingec || - v112 for any convex C c Rdd
3

---

2 Robust TD Learning for Value Prediction under Heavy Tails
First, consider the problem of predicting the value function for given discounted-reward Markov reward process with heavy-tailed rewards.
2.1 Value Prediction Problem
For finite but arbitrarily large state space X. let (Xe)reN be an X-valued Markov chain with the
transition kernel P X x X + [0, 1]. We consider Markov reward process (X,, Re)rEN such that at
state Xt, stochastic reward R2 Re (Xx) is obtained for all / 2 O. For a discount factor E [0, 1),
the value function for the MRP (X,, Ri)teN is the following:
V(z) = E
= EEX.
(1)
Objective. The goal is to learn without knowing the transition kernel P by using samples from system. In particular, for parameterized class of functions (Se) X - R O E RR), the goal is to solve the following stochastic optimization problem with mean squared error:
min E (e) - V(x)
@ER zmy
In order to solve (2) under Assumption 1, we propose robust variant of temporal difference
(TD) learning with linear function approximation [50. 54].
2.2 Robust Learning Algorithm
For given set of feature vectors (Φ(z) E Id : E X} with sup,ex [10(2)] < 1, we use
fe (.) = (O, (-)) as the approximation architecture. For a given dataset {(x,, R2 X/)
R x X t e N} with X PX,,, let the stochastic semi-gradien at IR be defined
ge( = Rg (X,) + (xe(XX) fx(x)) vefe(X))))))))
Robust TD learning is summarized Algorithm 1.
Algorithm I: Robust TD learning
Inputs: number of steps 7 2 1, clipping radii (bx)eer)) projection radius >> 0, step-size v) > 0 Set ((1) E (2 p)
\1 initialization
for = 1,2....... ... do
( + 1) = B2 { (t()) + ge (0(t)) (O())) < b,)}
end for Output: (.) = (ō(T), +()) where ē(T) ΣΣ (()
In the following, we will establish finite-time bounds for Robust TD learning by specifying the sequence of dynamic gradient clipping radii (bx) projection radius p and step-size 7).
2.3 Finite-Time Bounds for Robust TD Learning
We make the following assumptions on the Markov reward process.
Assumption 1. The stochastic process (X,, RI)EEN satisfies the following:
1. Ergodicity: (XI)εe an irreducible and aperiodic Markov chain with stationary distribution nP. Also, we assume that there are constants m >> 0, E (0, 1) such that
max =
|P((,, (z, u||TV S mç² ; Vt E Z,--
(3)
2. Heavy-tailed reward: For some p E (0, 1] and constant up E (0, oo),
3. Mcan reward: For any E N, R (X,) ++ X,] < ug 00, a.s., Vt N. r(X)) [-1, a.s.
(4)

---

We note that the uniform ergodicity and bounded mean reward assumptions are standard in TD learning literature [3, 54, 4]. Assumption 2 (Sampling). We consider two types of sampling strategies in this work:
2a. IID sampling: X, iid l and X; P(X,,-) -) for all & 2 1.
2b. Markovian sampling: X1 ~ μ and X = X2+1 ~ P(X,, .) for all 2
Assumption 3 (Realizability). There exists θ* E B2(0, p) such that V(-) = ,
Remark 1. We note that Assumption 3 holds directly in interesting realizable problem classes, e.g. linear MDPs [25], and allows us to obtain results on the statistical error performance of our design. In cases when it does not hold, results will continue to hold with additional function approximation error proportional to (x(.p) V (x) - (o, (x)) which unavoidable due to the limitation of the linear function approximation architecture.
The following lemma is important in bounding the moments of the gradient norm under Robust TD learning in terms of the projection radius p > and the upper bound uo on E [x]].
Lemma 1 (Tail bounds for l19. (0())) Let F a (0((1,, ((2), ((); Xt) for E Z,.
Then, under Assumption 1, we have:
(ell)(((())) 1 1 F Su < 00, a.s.,
(5)
for any & Z.,, where u = min + 2p) +p, un + 22p+3 pI+7].
Proof. Note that we have since supsex [1)]]] S 1. The upper bounds then follow by applying Minkowski's inequality and the triangle inequality for L spaces, respectively, to this inequality.
Tow (X)) - Seco (e))(X))
This lemma will be useful in the analysis of both the expected (Theorems 1-2), and the probbbbiyby bounds (Theorem 3) on the performance of Robust TD learning.
Next, we provide the main theoretical results in this paper: finite-time bounds for Robust TD learning. The proofs are mainly deferred to the appendix, while we provide a proof sketch for Theorem 3. In the following, we provide convergence bounds for the expected mean squared error under Robust TD learning with various choices of b;-
Theorem 1 (Expected error under Robust TD learning- iid sampling). Under Assumptions 1, 2a, 3.
we have the following bounds for Robust TD learning:
a) For be = (ul) for any / E Z4 and ?h 2p(1-2) (tT)=T
we have:
(Q(T), 91
6pu
VT >
(6)
00))009) 20d4
(1 TT)
b) Let A = EnEx (z) (z), and C,(u, Amin: 7. 1-y (4p + (1-7)Amin ) If Amin (A)
Amin 0, then with the diminishing step-size m/ (1 (1-7)eAmm and be for t Z4, for the average
iterate (ZT), we have?:
1p.1 P +
(1 1p.1 log(eT)
- (G(T), < Cplu, Amin: 7.p)
E e0). (u))..)).....o
1-p
T
and for the last iterate ( + 1). we have:
(xx) (+(x), O O(T+1)) Ep(u, , Amin+ Y,
log(eT)(1 -1p11 1 1 --
E max ((T)
ZEX
Amin
for any T > 1, where 1 = 1 x # y and 0 otherwise.
"The upper bound is C (u, Amin, p) Ern P O(T-P), which is further upper bounded as (6) and (7) by using intergral bounds.
5

---

The convergence rates in Theorem I are O(T rfz) and O(T without and with the full-rank assumption Amin > O, respectively. For p the convergence rates stated in Theorem both match the existing results for TD learning with bounded rewards [4], up to a larger scaling factor of raw second-order moment rather than variance, due to clipping centered around O.
Remark 2.
Remark 3 (Finite-time bounds in the unrealizable case). We note that results hold without Assumption 3 as well. In this general case, there will be an additional function approximation error proportional to B. VE[[V(<> (θ, [ (see Remark I). One would use richer function approximation scheme (e.g., larger projection radius p or dimension d) reduce this function approximation error, which will lead to an increase in the statistical error as we characterize in our
bounds. For the extension of our analysis the general case without Assumption 3, please see Appendix A.1.
In the following, we provide convergence bounds for Robust TD learning under Markovian sampling.
Theorem 2 (Expected enror under Robust TD learning Markovian sampling). Under Assumptions 1,2b and 3, let T > 1, > 0 be given, and define the mixing time т = minft E Z+ : m²² I v2p(u(T) 14r ). Then, with т)t = 7 v2p(ulT) 14r, Robust TD learning yields the following:
(()) < Tpu + 2v2p(1 + +2) + + + 6p)) (9)
E er)... amuu
(1 T
(1-7)
The proof of Theorem 2 is based similar Lyapunov technique as Theorem 1 in conjunction with the mixing time analysis in [4] for Markovian sampling, and can be found in Appendix A.
The bounds in Theorem involve expectation over the parameters ((), E [7). In the following, we provide a high-probabilliyy emror bound on the mean squared error under Robust TD learning.
Theorem 3 (Hiig--rooabilityy bound for Robust TD learning). For any E (0, 1), let Ls log(4/8). +
Under Assumptions 1. 2a, 3, with step-size 1j (001-)pL 20
and clipping radius b,
uf
(ur)
(B(T)) < PFT
3L4 Aif + 7L.tF)
(10)
(1 14
REX
holds with probability at least 1 - 5.
In the following, we give a proof sketch for Theorem The full proof can be found in Appendix A.
Proof sketch. Let L()) ||0 e 1 be the Lyapunov function, and X 1 X 1illg:l1a S b.).
Then, the Lyapunov drift can be decomposed as follows:
C(e(t + 1)) - L()(t)) < 2n (0(t) - 0*)] + 119x l2xd (()) (11)
(O(t)
where
B(I) = 9. (e(() (0)()=0))x E, (0(1) - )x E.Gg (0(() ( Xx),
the bias in the stochastic semi-gradient, and
(tt) 1 EE 11 [2xx]].
We can decompose B(t) further into a martingale difference sequence
Bo(t) = 9. (0(t) - θ*)x+ E. (e(() xx)x,,
and bias term
(t EE,g, - x*)
By Freedman's inequality for martingales [12, 53), we have 1 Σr Bu(t) S Tou L5 Tfr Azuma inequality, we have 1. Ei= Z(t)= < a 1
and by
each holding with probability at least 1 1-8/2.

---

By Hölder's inequality and Lemma 1, we can bound (t) S ub,² and E, 11 11xeelxxel S up; both with probability 1. Finally, by Lemma 2 in [54], we have the negative drift term
Eelge (0(1) e*) - -(1 - 7) Σ (())(S())(()))) -
By telescoping sum of (11) and rearranging the terms, we have:
T Σ (1 - (()(1)
- I B(O+ B 2(1 2(1- 7)T Σ ((()+ 1Bx.1
2n(1 >)T (1 (1-
The proof is concluded by substituting the above high probability bounds on the sample means of B(t), (t) and E, g1 | Xel (via union bound and integral upper bounds), and using Jensen's s inequality on the left side of the above inequality.
Most notably, this important theorem establishes that, by appropriately controlling the bias term of dynamic gradient clipping yield vanishing sample mean with high probability as the number of iterations increases, one can limit the variance of the semi- mradigradeet, thereby resulting in the provided global optrioppi guarantee.
3 Robust Natural Actor-Critic for Policy Optimization under Heavy Tails
In this section, we will study a two-timescale robust natural actor-critic algorithm (Robust NAC, in short) based on Robust TD learning, and provide finite-time bounds.
3.1 Policy Optimization Problem
We consider a discounted-reward Markov decision process (MDP) with a finite but arbitrarily large state space S, finite action space A, transition kernel P and discount factor y E (0.1). The controlled Markoy chain {(Sr Ar) S x A E N} has the probability transition dynamics P(S,41 E a|S{, At) = (S,
(S,,s), s). for any s E S. Taking the action A E A at state S, e yields a random reward of R2 (s, at any Z+. For given stationary randomized policy π = (I(a 8) ())) the value function y* and the state-action value function (also known as Q-function) Q" are defined
7- R. At) = =s], SES
(*) E
(12)
@7(s. a) = E.
Ru,S, A1) Ar) = 8, A1 = a). (s,4)
(13)
Remark 4 (From MDP to MRP). Under any stationary randomized policy the process (St, At) =; (Xt)cxo is a Markov chain over the state-space x = S x A, thus (X,, Re) with (X,), R.(S,, As) is a Markov reward process of the kind that we analyzed in Section 2. As such, we can use Robust TD learning to evaluate V(x)= = (=)x) for any x = (s, a) ESX A.
Haavy-tailed reward. We assume that the process (X,, Re)ss with the Markov chain X, (S,, A,) and the reward R. R2 (X.) satisfies Assumption 1. We denote the stationary distribution of X, = (S,, Ac) under x as ntt
Objective. For an initial state distribution X, the objective in this work is to find the following:
nt' E arg max (s)) =: V*),,,,
(14)
over the class of stationary randomized policies.
Policy parameterization. In this work, we consider finite but arbitrarily large state space S, and for such problems, the tabular methods do not scale [51, 3]. In order to address this scalability issue, we consider widely-used softmax parameterization with linear function approximation: for given set of feature vectors {s(s,, a) E Rd s E S, E }} and policy parameter W e gd
exp W (s)
(als) =
Ense exp(W 4 a')) (s,a) e S
(15)
In the following subsection, we will describe the robust natural actor-critic algorithm.
7

---

3.2 Robust Natural Actor-Critic Algorithm
For any iteration 1, we denote Ty = (W) throughout the policy optimization iterations.
For samples D(k) = ((St., Ar, Rx K A1,x) 2 1}. given (be,)),KEZ, and > 0, Robust NAC Algorithm is summarized in Algorithm 2.
Algorithm 2: Robust Natural Actor-Critte Algorithm
Inputs: clipping radii (b:)121. projection radius > 0, learning rate > 0, Ls > 0
for 1, K do
Set θ (1) = 0 // initialization: max-entropy policy
for = 1,2, ... do
Set 91 (e (0)(()
BB, k 1S Al,,) Je A(x)) ((Sckk ACn)) Ox(t + (0.,)) (x((t) T Dr
(k) (Ox(t)) ((1a (0)(t)) ((ll)(((()(())) s bi]}
end for
W(k 1) (kk) a 2 (t)
end for
(0, (0,)())) - Qtx (x)) a good approxi-
Remark 5.
The optimal solution O E arg min
GER
a (=,00)
mation of the natural policy gradient:
AA [G(mm))] > (A) E arg min
(w,, Vw log (als)) A (s,
wERd
(s,a)=d)* aa (-1a)
which follows from Jensen's inequality and leads to the Q-NPG [1]. For a detailed discussion, refer Appendix B.
3.3 Finite-Time Bounds for Robust Natural Actor-Critic
In this subsection, we will provide finite-time bounds for Robust NAC.
We assume that the resulting Markov reward process under Me for each i satisfies Assumptions 1-3 with stationary distribution ==** and uy 2 R A Sr,,, Ar,x]- We assume that the
dataset ((k) is obtained independently at each iteration 2 for simplicity, with (St.e, At,x) lid ~ f
and 5¹,, PAr. (St,k.)) and A, T-(SkS(,)) according Assumption 2a under the stationary distribution -= [n** (s, a)) SER, under mi. We make the following standard assumption for policy optimization, which is common in the policy gradient literature [1, 57, 34).
Assumption (Concentrabilityy. For any ls 2 1, we assume that there exists Crone < 0c such that:
d (s)m (als)
max (s.a)E8xA
Ccone: 1TTH (s,
(16)
where 10T* is the stationary distribution of (St,ky Ar,))211 under Te.
Theorem 4 (Finite-time bounds for Robust NAC). Under Assumptions 1-4 for any A: > 1, for any 5 E 10, and T, K 1, Robust NAC with p 2 max; | bi,k
7 (og(44//))
learning rates
v2(1-))oL 31क
and Vlog JA pVK achieves the following with probability at least 8:
" (max1sxsx TE
max ux)) T Ceanel IskSK (1 11-33TT1
min (V0 D D 2pv 2pvlog log & (1 VK
XITh (3Lg
+ 7L
ISKCK
where Ls log(4T/6).

---

The proof of Theorem 4 can be found in Appendix B.
Remark 6 (Sample complexity of Robust NAC). An immediate consequence of Theorem 4 is as follows: the best iterate error decays at a rate O VR +0 (2(++)
after K iterations of natural
policy gradient, which contains T steps of Robust TD learning per iteration. As such, in order to achieve ε error, one needs x K = Ó( 2 ((1p)//) samples.
Remark 7. Theorem 4 can be easily extended to expected error bounds and the full-rank case, where we would have O(K + P) by using Theorem 1. By extending the analysis in Theorem 2, one can prove results for Markovian sampling as well.
Remark 8 (Exploration in Robust NAC). Assumption implies that the stationary state-action distribution under T. should be sufficiently exploratory so that it should have a nonzero probability at each state-action pair that is visited by the optimal policy x². This assumption on the exploratory behavior of policy gradient methods is standard in reinforcement learning literature [1, 57, 34, 63]. Alternatively, entropy regularization can used for natural policy gradient methods to encourage exploration, which would imply weaker conditions at the expense of an additional bias term in the function approximation setting [47, 9].
4 Numerical Results
In this section, we present numerical results for Robust TD learning and its non-robust counterpart.
(1) Randomly-
MRP. In the first example, we consider a randomly-generated MRP with [ 256. The transition kernel is randomly generated such that P(x,x')) vid Unif(0, 1), and row- wise normalized to obtain a stochastic matrix. The feature dimension is d = 128, random features are generated according to the x-squared distribution (xx) +p(x:) (z))] with Pn(#:) ~ (0, Ta) for all X, O 3U/ for U Unif (0, 1) and v [- 1 (x) L The discount factor is
? 0.9, and the reward is (X,, r(X,) + E[[N] with N₂ std (.2) Mean squared error (2) under Robust TD learning and TD learning with the clipping radius b, = and diminishing step-size Wt Amin(1-9J in Theorem and projection radius p 30 are shown in Figure 2. Despite
2000
X0280
40010
10000
202.6
12.00
(a) Errors for TD Learning
(b) Errors for Robust TD Learning (c) Comparison of the expected errors
Figure 2: Performance of TD learning and Robust TD learning under heavy-tailed rewards of tail index 1.2. Each faded green line is the MSE for an individual trial, and the solid lines with markers indicates the average error performance for TD learning and Robust TD learning.
diminishing step-size and projection, TD learning fails miserably often and in expectation due to the outliers in the reward that lead to extremely large errors (Figure 2a). On the other hand, for the same feature vectors, state and reward realizations, Robust TD learning effectively climinates them in every sample path, and achieves good and consistent performance despite extremely heavy-tailed reward and gradient noise with tail index 1.2 (Figure 2a).
(2) Circular Random Walk. In this example, we consider circular random walk for X {1, 256), where each state x modulo- |X| [60]. The transition matrix is generated as P(r,x')= 1/3 if = x' and P(x,x') = 1/24 if 0 < |r x'I < 8. The reward and random feature generation the same as the first example. The performances of TD learning and Robust TD learning in this structured case after 1000 trials are given in Figure 3.
similar behavior as the randomly- -egnrrrtd MRP observed in this example: due to outliers, TD learning fails miserably, while Robust TD learning achieves good performance consistently.

---

200
(a) Errors for TD Learning
(b) Errors for Robust TD Learning (c) Comparison of the expected errors
Figure 3: Performances of Robust TD learning and TD learning for the circular random walk under heavy-tailed reward with tail index 1.2. Each faded green line is the error trajectory for an individual trial, and the solid lines indicate the expected errors for TD learning and Robust TD learning.
5 Conclusion
In this paper, we considered RL problem with heavy-tailed rewards, and proposed robust TD learning and NAC variants with dynamic gradient clipping mechanism with provable performance guarantees, both expectation and with high probability. Motivated by the results in this work, it would be interesting to explore single-timescale robust NAC and off- off-policy NAC for future work.
Acknowledgments and Disclosure of Funding
Atilla Eryilmaz's 's research was supported in part by NSF AI Institute (AI-EDGE) 2112471, CNS- NeTS-2106679, CNS-NeTS-20072311, and the ONR Grant N00014-19-1-2611.
References
[1] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approxi- mation with policy gradient methods in markov decision processes. In Conference on Learning Theory, pages 64-66. PMLR, 2020.
[2] Mukul Agarwal, Vivek S Borkar, and Abhay Karandikar. Structural properties of optimal transmission policies over randomly varying channel. IEEE Transactions Automatic Control, 1366)11111111 2008.
[3] Dimitri P Bertsekas and John N Tsitsiklis. Neuro-dynamic programming. Athena Scientific, 1996.
[4] Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. arXiv preprint arXiv: 1x06::88060245555 2018.
[5] Shalabh Bhatnagar, Richard Sutton, Mohammad Ghavamzadeh, and Mark Lee. Natural actor -rior-critic algorithms. Automatica, 45(11):24112243 2009.
[6] Sébastien Bubeck, Nicolo Cesa-Bianchi, and Gábor Lugosi. Bandits with heavy tail. IEEE Transactions on Information Theory, 59(11):71117711 2013.
[7] Qi Cai, Zhuoran Yang, Jason D Lee, and Zhaoran Wang. Neural lemporal-differenee learning converges to global optima. Advances Neural Information Processing Systems, 32, 2019.
[8] Semih Cayci, Atilla Eryilmaz, and Rayadurgam Srikant. Budget-constraing bandits over general cost and reward distributions. In International Conference Artificial Intelligence and Statistics, pages 1388-4392 PMLR, 2020.
[9] Semih Cayci, Niao He, and Rayadurgam Srikant. Linear convergence of entropy--regularized natural policy gradient with linear function approximation. arXiv preprint arXiv:2 200.04000499 2021.
10

---

[10] Kong-Rong Chen and Sean Meyn. Value iteration and optimization of multiclass queueing networks. Queueing Systems, 32:65-97, 1999.
[11] Ashok Cutkosky and Harsh Mehta. High-probability bounds for non-convex stochastic opti- mization with heavy tails. Advances in Neural Information Processing Systems, 34:4883-445 4895, 2021.
[12] David A Freedman. On tail probabilities for martingales. the Annals of Probability, pages 100-118, 1975.
[13] Carla P Gomes and Bart Selman. Algorithm portfolios. Artificial Intelligence, 126(1-2):33-62, 2001.
[14] Carla P Gomes, Bart Selman, Nuno Crato, and Henry Kautz. Heavy-tailed phenomena in satisfiability and constraint satisfaction problems. Journal of automated reasoning, 24(1-2):67, 2000.
[15] Carla Gomes, Bart Selman, Henry Kautz, et al. Boosting combinatorial search through randomization. AAAI/IAAI, 98:431-444 -37,, 1998.
[16] Mert Gurbuzbalaban, Umut Simsekli, and Lingjiong Zhu. The heavy-tail phenomenon in sgd.
In International Conference on Machine Learning, pages 3964-3975. PMLR, 2021.
[17] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. In International Conference Machine Learning, pages
PMLR, 2018.
[18] Mor Harchol-Balter. The effect of heavy-tailed job size distributions on computer system design. In Proc. of ASA-IMS Conf. on Applications of Heavy Tailed Distributions in Economics, Engineering and Statistics, 1999.
[19] Holger H Hoos and Thomas Stützle. Stochastic local search: Foundations and applications. Elsevier, 2004.
[20] Daniel Hsu and Sivan Sabato. Heavy-tailed regression with generalized median-of-means In International Conference on Machine Learning, pages 37-45. PMLR, 2014.
[21] Yu-Pin Hsu, Eytan Modiano, and Lingjie Duan. Scheduling algorithms for minimizing age of information in wireless broadcast networks with random arrivals. IEEE Transactions on Mobile Computing, 19(12):9933-2115, 2019.
[22] Marat Ibragimov, Rustam Ibragimov, and Johan Walden. Heavy-tailed distributions and robustness in economics and finance, volume 214. Springer, 2015.
[23] Predrag R Jelenković and Jian Tan. Is aloha causing power law delays? In Managing Traffic Performance Converged Networks: 20th International Teletraffic Congress, ITC20 2007, Ottawa, Canada, June 17-21, 2007. Proceedings, pages 149-1160.. Springer, 2007.
[24] Predrag R Jelenković and Jian Tan. Characterizing heavy-tailed distributions induced by retransmissions. Advances in Applied Probability, 45(1):106-1388 2013.
[25] 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.
[26] Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In In Proc. 19th International Conference on Machine Learning. Citeseer, 2002.
[27] Sham M Kakade, natural policy gradient. Advances in neural information processing systems, 14, 2001.
[28] Yuan Ke, Stanislav Minsker, Zhao Ren, Qiang Sun, and Wen-Xin Zhou. User-friendly covariance estimation for heavy-tailed distributions. Statistical Science, 4443)4454-47, 2019.

---

[29] Byungchan Kim, Jooyoung Park, Shinsuk Park, and Sungchul Kang. Impedance learning for robotic contact tasks using natural actor-critic algorithm. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)) 40(2):433 443, 2009.
[30] Vijay R Konda and John N Tsitsiklis. Actor-critic algorithms. In Advances in neural information processing systems, pages 1008-1014. Citeseer, 2000.
[31] Lars Kotthoff. Algorithm selection for combinatorial search problems: A survey, Data mining and constraint programming: Foundations of cross-disciplinary approach, pages 149-190, 2016.
[32] Michail G Lagoudakis, Michael L Littman, et al. Algorithm selection using reinforcement learning, In ICML, pages 511-518, 2000.
[33] Kyungjae Lee, Hongjun Yang, Sungbin Lim, and Songhwai Oh. Optimal algorithms for stochastic multi-armed bandits with heavy tailed rewards. Advances in Neural Information Processing Systems, 13:8452-8462. 2020.
[34] Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural proximal/trust region policy optimization attains globally optimal policy. arXiv preprini 1906. 2019.
[35] Mico Loretan and Peter CB Phillips. Testing the covariance stationarity of heavy-tailed time series: An overview of the theory with applications several financial datasets. Journal of empirical finance, 1(2):211-248, 1994.
[36] Gábor Lugosi and Shahar Mendelson. Mean estimation and regression under heavy-tailed distributions: survey. Foundations of Compustational Mathematics, 19(5): 1000:114-111999 2019.
[37] Benoit Mandelbrot. New methods in statistical economics. Journal of political economy. 71(5):421-440) 1963.
[38] Mark M Meerschaert and Hans-Peter Scheffler. Moving averages of random vectors with regularly varying tails. Journal of Time Series Analysis, 21(3):297-32,, 2000.
[39] Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global con- vergence rates of softmax policy gradient methods. In International Conference Machine Learning, pages 6820-6829. PMLR, 2020.
[40] Sean Meyn. Control techniques for complex networks. Cambridge University Press, 2008
[41] Stanislav Minsker. Geometric median and robust estimation in banach spaces. Bernoulli, pages 2308 2008-2233,2222 2015.
[42] Stanislav Minsker. Sub-gaussian estimators of the mean of random matrix with heavy- entries. The Annals of Statistics, (6(6A))2871-2903 2018.
[43] Rajeev Motwani and Prabhakar Raghavan. Randomized algorithms. Cambridge university press, 1995.
[44] Jayakrishnan Nair, Adam Wierman, and Bert Zwart. The fundamentals of heavy-tailss Prop- erties, emergence, and identification. In Proceedings of the ACM SIGMETTRCSSinteeaatoon conference on Measurement and modeling of computer systems, pages 387-388, 2013.
[45] Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. Inley-Interscience, 1983.
[46] Jan Peters and Stefan Schaal. Natural actor-critic. Neurocomputing,
2008
[47] Lior Shani, Yonathan Efroni, and Shie Mannor. Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 34, pages 5668-5675. 2020.
[48] Han Shao, Xiaotian Yu, Irwin King, and Michael R Lyu. Almost optimal algorithms for linear stochastic bandits with heavy-tailed payoffs. Advances Neural Information Processing Systems, 31, 2018
12

---

[49] Matthew Streeter and Daniel Golovin. An online algorithm for maximizing submodular functions. Advances in Neural Information Processing Systems, 21, 2008.
[50] Richard S Sutton, Learning to predict by the methods of temporal differences. Machine learning, 3(1):9-44, 1988.
[51] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[52] Richard S Sutton, David A McAllester, Satinder Singh, Yishay Mansour, et al. Policy gradient methods for reinforcement learning with function approximation. In NIPs, volume 99, pages 1057-1063. Citeseer, 1999.
[53] Joel A Tropp. Freedman's ' inequality for matrix martingales. Electronic Communications in Probability, 16(25):262-270, 2011.
[54] John Tsitsiklis and Benjamin Van Roy. An analysis of temporal-difference learning with function approximation. IEEE transactions automatic control, 42(5):674-690 1997.
[55] Martin J Wainwright. High-dimennionall statistics: non-asymptotic viewpoint, volume 48. Cambridge university press, 2019.
[56] Hongjian Wang, Mert Gurbuzbalaban, Lingjiong Zhu, Umut Simsekli, and Murat A Erdogdu. Convergence rates of stochastic gradient descent under infinite noise variance. Advances in Neural Information Processing Systems, 18:18666-8887, 2021.
[57] Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods:
Global optimality and rates of convergence. arXiv preprint wexXiv:/90.000 150, 2019.
[58] Ward Whitt. The impact of a heavy-tailed service-time distribution upon the m/gi/s waiting-time distribution. Queueing Systems, 36(1-3):71-83 2000.
[59] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforce- ment learning. Machine learning, 8(3-4):229-256, 1992.
[60] Eric Xia and Martin Wainwright. Krylov-bellman boosting: Super-linear policy evaluation in general state spaces. In International Conference on Artificial Intelligence and Statistics, pages 9137-9166. PMLR, 2023.
[61] Tengyu Xu, Zhe Wang, and Yingbin Liang. Improving sample complexity bounds for (natural) actor-critic algorithms. arXiv preprint arXiv:2004. 12956, 2020.
[62] Tengyu Xu, Zhe Wang, and Yingbin Liang. Non-asymptotic convergence analysis of two time-scale (natural) actor-critic algorithms. arXiv preprint arXlv:2005.03557, 2020.
[63] Rui Yuan, Simon S Du, Robert M Gower, Alessandro Lazaric, and Lin Xiao. Linear convergence of natural policy gradient methods with log-linear policies. arXiv preprint 10X:::22000014000 2022.
13

---

A Proofs for Robust TD Learning
The following lemma will be critical in our proofs.
Lemma (Lemma 4 [54]). For any two vectors V. V R
ITV TV 5 || Vllm
where
(T() + Σ P(x,a')V(x'), x'eX
(17)
is the Bellman operator.
Proof of Theorem. I. The proof follows the Lyapunov approach in [4]. Let L(O) ||0 10 be the Lyapunov function for any @ Rdd Then, by the non-expansivity of [l,,(.,)) (U.p), we have:
C(e(t - 1)) - ((e(t)) +
(llo - b,} (ng.(((t)) (@(t) (((t())((((t()))) - ()) S bb). (18)
Taking conditional expectation given F, and using the fact that (9()))) > b.} 1 (l())))()))lz & b, we get:
B[C(O(L+ + 1)) s (()()))))))))+)))))))) (1B - 0*)
[Pl 6 + ub; (19)
where we used
Elll (lllo((e(h)333110000000000223130 (1l,))))){{{ll((((((((())))))))
(20)
S ubb
in the last term. Now, for (e))((( 0.)] have the following inequality:
Eo (+(())
7. fec (eee)))))))))))) - V(X.)).
E. ((T)o))))))) Seco (x.) (Sec)) (X.) v(
where T is the Bellman operator (17). By using the fact that the value function is the fixed point of the Bellman operator T. we have the following:
Bell (()
fecoo (Jew) -V(X))) (fors) v(X,)]] - (Er [(((ox)(x)) (21)
= (x)))))))
By using Lemma conclude that:
Elg. (O())) -11>)) Σ m(x) (ooo(())))))) --(-)))
-(1-7))lferc) -V1k
(22)
zeX
Then, we can rewrite (19) as follows:
E[C(O(t 1)) < (()(t) 211 -11 - V11
2r
(() b.HFFa] + ru² (23)
The bias introduced by using the gradient clipping can be bounded as follows:
((g)()())) (((t)) -*) (") F..
< ( (I 6bHJ), (24)
which follows from Cauchy-Schwarz inequality, triangle inequality and the fact that max(]|0((]la, [[0*][2] p due projection. Using Hölder's inequality on the RHS of (24),
we obtain:
(O))) (t(t)) -
> b.FFF. < 2p Th. (()) > bF..
14

---

Using Markov's 's inequality, we bound the bias due to using the clipped stochastic gradient as:
Big. (0(1) (0(1) θ (1) b. S 2pub,"
(25)
Substituting (25) into (19), and taking expectation the trajectory Ft. we obtain:
([ + 1)) - [(+(t)) v -2n(1 (ll VIl + Anpub," p + n7 ubb
Telescoping sum over 1 1.2...., yields:
T [ll/eco - -1112)
EC(O(T++)) ((0(1)) v
- 21 77
Anpu ( Ps +1u Ps-d... (26)
Rearranging the terms, using Jensen's inequality and ((0(1)) S 4p², and substituting the step-size yields the result.
(b) For the full-rank case, note that
I VI - 04) (E)())(a)) (x)) 0*),
2 Amin -
which implies (together with (23)) that:
B[J0((+1)-0*11 (1 (1-m) (1-=)\((1-))00000)11111
- -11 pm,ppu, P b Pu.
With the step-size choice [I-9]AX* we obtain by induction:
E]]@(++1) - Xt Σ Bllfe()) V11
4pu
b/
bx
Amin
Min
k
km
By rearranging the terms and using the integral bound for the summations above, and using the Jensen's inequality for the p-norm, we obtain the result.
L
Proof of Theorem 2. Let Ft++ = ( @()), X,, X and R F[( + Also, let
((0) = E gt (O),
g())=
(
The bias due to Markovian sampling is:
Z,(9) = (5) -(0) (e -0)
With the above definitions, the Lyapunov drift at time t 2 1 can be bounded as follows:
E + 0- < |0(()) - e1 21y(1 - >)ll - Sew I| + 2 [[lg: (x
+ 2ng (@(t) e + (e()),,
where Xt = 1 1119, (0(())l2 b... Compared to the case of iid sampling in Theorem 1, the difference is ())) In the following, we bound EZ, (O())) by using the mixing time analysis in [4]. First, provide two essential properties of (e) to verify the conditions in Lemma 10 in [4].
Lemma 3. Under Assumption 1, have:
[I) s (p)2 θ B2)
(27)
(e) Zz()') < 6(1 2p) 0'12,, 0,0' (2 p).
(28)
15

---

Thus, we have:
EZ. (0()) ( -)]] 6 (T) @ 7)
(29)
We have the following inequality:
[|O(t) ( 22 | + 1 S Σ 11 (0()))
Taking the expectation above, and using Hölder's inequality:
E (1) @(( 2))l2 S E (Ella) T
S nTu
k=t-y
By using the information theoretic bound Lemma 9 in [4], we obtain
(0 r)) & 2(1 + 2p)²n,
under the uniform ergodicity assumption in Assumption Using the last two inequalities in (29), obtain:
EZ,(O(t)) & 2(1 2p) (1
6ru
(30)
By using the above result, we obtain the ultimate inequality for the Lyapunov drift as follows:
B]]((t+1)-0) 1 (t) - 11 211 Bl 4np
+ +1 6ru
The proof follows from identical steps as Theorem
Proof of Theorem 3. The main idea in the proof is to establish centering argument for both the bias (due to using clipped stochastic gradients) and the variability (controlled by 6,), and to use martingale concentration arguments based on Freedman's 's inequality and Azuma-Hoeffdiig inequality to bound the sample mean for the bias and variability, respectively. This strategy extends the approach [6] for robust mean estimation reinforcement learning, which has dynamic behavior unlike the mean estimation problem. Namely, for any E {1,2..... T). we have:
L(O(t 1)) < (()(t)) 21/(1 ffee -V1 & b.
+ ((
+ +n)B(t))+)) (t),
where the first line follows from Lemma 2, and
Btt) = -E (O.)) - +-) + + (e(t)) (0(t) - (1) bb,,, (31)
is the bias term, and
(tt) (00)) (1lo)) - 6.) B (00) (1)- s 6.
the variability. By telescoping sum over = 1,2,.... T and some algebraic manipulations, we have:
C(O(T + 1))
((O(1))
1 Σ S(O(t) -
-2n
T
T
T
(32)
T
T
T
+1
u
1-p
27
Σ
B(I) +
1
Σ z(t),
T
T
T t=1
where we used (20) in the second line. In the following, we will bound the empirical processes 1
T E.-1 (t) and E,_, B(t).
Note that {Z(1) E N} is martingale difference sequence (MDS) adapted to the filtration (F.: NJ. Furthermore, note that
Iz(+) < 26; < 262.
16

---

almost surely for any t < T. Thus, En= [ < T forms a martingale with bounded differences, and by using Azuma- nouma-Hoeftding mequality [55], we have:
1
T Σ t=1
Ls T
u 11-2 T 147
T
(() S bTV
(33)
L
L.3 1TD
with probability at least - 6/2 where the last inequality holds since T >> L8u 1-r.
We decompose (t) into predictable and non-predictable components follows:
B(t) = Elg. (Q(t) (@(t) +*) (1) > b.Hl + Bo(t),
(34)
where the martingale difference sequence (t(t) is defined as follows:
(t) - (l))((())) - 0*)1 (Ila: & (.)
+ ((((())))((()))) - e*)1 (19)( S b,). (35)
By (25) (with b, replaced by b,), the first term on the RHS of (34) is bounded by 2puc, Thus, we have:
T Σ B(t)
2p FFF Lg
T
S
Bu(t).
(36)
T
T
T
t=1
In order to upper bound + ΣT_ (t). we use Freedman's 's incquality for martingales [12]. To use Freedman's inequality, we verify the following conditions.
1. For any S T. we have:
(1))))0))0)((((((0))))))))))-a)) bb S 2pb, S 2pbr.
almost surely.
2. The normalized quadratic variation process satisfies:
1
BB(
T
t=1
((o(((()))((())) (1)))(())))) s b.F.FF))
T
40
T
u T
wbi-p S 4p²
I. 1-7
where the first inequality is due to Ver (2) < E[Z²] for any random variable Z with finite variance, the second inequality follows from Cauchy-Schwarz inequality and triangle inequality with max || (t)]l2 ||@*||2] < due to projection, the third inequality follows from (20) with b, replaced by b,.
Thus, by Freedman's inequality, have:
T T
ffr 2 2/2pu too I.
4pLigh, 3T
Bt =
T
1=1
F. I. Af.
$ +
T
17

---

with probability at least - 6/2. Therefore, from (36) and the above inequality, with probability at least 1 8/2, we have:
T B(t)
Tpu F- L 4
=
(37)
T
TT
Hence, by substituting (33) and (37) into (32) with union bound, and using the specified step-size
together with the facts that ((O(1)) I 4p and L(O(T + +)) 2 0, we conclude the proof.
L
A.1 Sinite-Time Analysis of Robust TD Learning without Realizability
In the following, release the realizability assumption, and show that an additional function approximation error appears in the bounds for the general case.
Theorem (Performance of Robust TD learning without realizability). Let
app
inf (0.2(
(0),
Then, under Assumptions and we have the following bounds for Robust TD learning:
For by = (ut) --r for any E 2 and = = 20(1-2) we have:
(w2) 1+y
(O(T, $
6pu T+E
1
2 aapp
(p
1 y 1 (38)
ar))..)))...
T)
for any T>b 1.
Proof of Theorem 5. Note that we define
- arg
min
B[[((z) (9, ((x)))
(e.2(0.p)
By (19), we have:
E[c(O(t 1))] s ((e(t)) 2 20))) 0*)
2,( - (1) > b, + 1/bbb (39)
To eliminate the realizability assumption (Assumption 3), make the following decomposition:
E, jg (O(())(()(() - 0*)] = E, + 7fen feco (fe)) (0r, ((x))),,
E, ((T))))) (X,) ((on)(())) (0", ((x)))
E. ((T fero (fere) - v(X))) + E. ((T[st)))))) (xx,)))))))))))))))))))))))))) (V(X,)
(0", ((x)))
Note that the last term corresponds to the approximation error, and we can bound its expectation as:
E ((T)e()) Seco (x.) (v(X,) (0*, +(x)))) (1-744 7 -1-7+
Secolle capp-
Since [Vx)] < + and [Jeco) (2)) S p for all x. and 7 (0, 1), have:
e - ( (((x))))(((x)))))) (V(X.) - (0", (xx))) 22 1 Eapp
for any f. Using this result, and following identical steps as Theorem with the same step-size yields the result.
18

---

B Proofs for Robust Natural Actor-Critic
Proof of Theorem 4. We use the following Lyapunov function for the analysis 57,
Σ (alss log . <a(ss)
(
Σ
dx (8)
(40)
Talss)
#EB
aEA
For the Lyapunov drift, any iteration have:
Thk (a)
[(T++1) - [(Tx) = Σ dx (s) (als) log
(41)
Th+ (als)
8,0
Since sup,,a [| ())s _ 1, Vw lo (alss is 1-Lipschitz continuous [1]. Thus, we have:
( V log (og V/ (42)
Since W + ((k)) + a we have:
[(T++1) [(T)) - 7 _ ( dx (s)r* log (c))
(43)
2
By performance difference lemma [26], have:
(*()s) v" (s)
[A (s,
(44)
amwn(-ls)
Using the last two inequalities, we have the drift inequality:
((T++1) - [(Tx)) - 7 2 (+x(T) - Σ dx (s) (v V logma(als)Or((T) - -A**(s,a))
2,0
-n(p ( (A) -
For the log-linear policy parameterization, we have v lo (a|s) ((s, a) - Σ Iwwld(s)0(s.d))
d'ER
Also, from the definition of A (s a) = 2" (s, EWER (d1))
[((V log (T) (s.
( 9 -
E (Q(s..))) - (1016)))))0000))00 )))
Σ d (3) a), Ox 2 (8, (5(((,,)) a))²
Σ nmm (s. a) a). Qth (*) (s.a))
I Ceone
where the first line follows from the fact that Var(X) S E[X for any random variable X with finite second-ore order moments, and the last line follows from change of measure argument. Then, by Theorem 3, we have:
Hs a) (8(s,,), - 5 (1 r
pu
3Lg
20+p
7L 1+F
with probability at least 8/K. Furthermore, we have:
[T) < p²
for any k; T by the projection. As such, we can bound the drift inequality as follows:
1/2 [(TT+1)) - [(Tx) - p² t Ceone
puk 14p
I-p 21re
3Lg
+ +
ifn
2
TFP
7(1 - 7) (vT (A) (F)- (45)
with probability least 8/K. By telescoping sum of the above inequality, using union bound, and noting that (als))) = [A] for any s, a, which leads to L(T1) = log A,), we conclude the proof. O
19


Reviews:
[{"review_id": "oy54X8lFer", "reviewer": "Reviewer_pbb6", "summary": "This paper discusses robust Temporal Difference (TD) methods for RL with heavy-tailed rewards. Specifically, it proposes robust variants of TD(0) and Natural Actor-Critic (NAC) for policy evaluation and RL control, respectively, and then derives their average iterate's convergence rates.", "questions": "1. Why should robust NAC converge to the optimal policy (in the value function sense)? I am not well-versed in the actor-critic literature, but is global convergence straightforward even in the function approximation setting? In the case of SARSA with linear-function approximation (Melo-Meyn-Ribeiro, 2008), one required that the policy improvement operator be Lipshitz with a `small' Lipschitz constant to ensure a unique fixed point of the Bellman operator. For example,  this holds for soft-max type policies with a sufficiently small inverse temperature parameter. In this work though, no such assumption is made apart from full realizability of the function approximation space. \n\nMelo, F.S., Meyn, S.P. and Ribeiro, M.I., 2008, July. An analysis of reinforcement learning with function approximation. In Proceedings of the 25th international conference on Machine learning (pp. 664-671).\n\n2. Is the obtained convergence rate of $\\tilde{O}(T^{-p})$ tight for $p < 1?$\n\nMinor:\n3. What is k in the subscript of $\\theta$ in Algorithm 1?\n\n4. In line 199, should $\\bar{\\chi}(t)$ in the definition of $Z(t)$ be $\\chi(t)?$\n\n4. In the displayed equation above line 482, what is $V(t)?$", "limitations": "I could not find any limitations section.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Convergence rates for TD(0) and NAC with function approximation are obtained in the non-trivial heavy-tailed reward setup.\n\n2. The above results have been obtained both in the generative as well as the Markovian noise model.", "weaknesses": "1. Assumption 3 is extremely strong. While the authors mention that there would be an additional non-vanishing approximation error when this assumption is not the case, it is unclear what the point of convergence would be in that case. \n\n2. No reasons/insights have been provided on why clipping helps deal with the heavy-tailed nature. \n\n3. In the related works section, it is mentioned that existing theoretical analyses for TD learning only provide guarantees in the expected error rather than in high probability. This is incorrect; e.g., see\n\na.) Patil, G., Prashanth, L.A., Nagaraj, D. and Precup, D., 2023, April. Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisation. In International Conference on Artificial Intelligence and Statistics (pp. 5438-5448). PMLR.\n\nb.) Dalal, G., Szörényi, B., Thoppe, G. and Mannor, S., 2018, April. Finite sample analyses for TD (0) with function approximation. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 32, No. 1).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the questions and comments. Below, we provide our responses to the reviewer's comments and questions in *Weaknesses* and *Questions*, respectively.\n\n- *W1: Assumption 3.* We thank the reviewer for pointing this out. Please note that we have also addressed this question in our general response above. The goal in TD learning with function approximation is to minimize the error $\\mathcal{L}(\\Theta)$ over the parameter $\\Theta$. If the value function $\\mathcal{V}$ does not lie in the class of functions of type $f_\\Theta$, there will be a non-vanishing function approximation error $\\mathcal{L}(\\Theta^\\star)$ where $\\Theta^\\star$ is the optimal parameter, we characterized this approximation error in the general response. This approximation error is unavoidable, and appears in the seminal works (Tsitsiklis and van Roy, 1997) and (Bhandari et al., 2018) as well, as these works consider convergence to the fixed point of the *projected* Bellman equation rather than the true value function, which is the fixed point of the Bellman equation. Our convergence results in this paper shows that all statistical errors vanish with $T$, and the optimal total error $\\mathcal{L}(\\Theta^\\star)$ is obtained as $T\\rightarrow\\infty$ at the rates we specified in the submission under a given linear function approximation architecture.\n\n- *W2: Intuitive explanation on how gradient clipping tames heavy tails.* As the reviewer suggested, we will expand the discussion in Line 210 on how gradient clipping helps taming heavy-tailed gradient noise in the updated version. We note that clipping bounds the gradient, thus making its variance bounded, but this comes at the expense of introducing a bias in the gradient update. By dynamically increasing the clipping radius over time carefully, the bias is gradually eliminated while controlling the variance, which establishes convergence.\n\n- *W3: Related works.* We would like to thank the reviewer for the references, we will cite these references in the updated version with appropriate commentary. In addition to noting the relationships, we will clarify that the focus in our work is the heavy-tailed regime, where we aim to establish high-probability bounds.\n\nIn the following, we provide our responses to the questions raised by the reviewer.\n\n- *Question 1.* Policy gradient methods, which contain *natural actor-critic (NAC)* algorithm that we investigate in our work, aim to find the optimal policy within a restricted policy class directly by using gradient-based optimization methods. Depending on the richness of this policy class (e.g., rank of the feature matrix, ambient dimension in our case), the optimal policy is approximated by the output of the policy optimization algorithm. An assumption to establish convergence of the NAC method to global optimum is the concentrability coefficient assumption (Assumption 4 in our paper), which implies that the state-action pairs visited by the optimal policy should be covered by the support of the state-action visitation distributions under the policy iterates. This assumption is standard in the policy gradient literature (e.g., Agarwal et al., 2021; Wang et al, 2019; Yuan et al., 2022; Scherrer et al., 2015, among many others, and also see Xie et al., 2022 on its role). Sufficient exploration and an initial state distribution with sufficiently large support set implies this assumption in general.\n\n- *Question 2.* The tightness of the bounds requires lower bounds for the statistical errors in the heavy-tailed regime $p < 1$. It is definitely an important and complicated question that we leave as a future work.\n\n- *Questions 3-5.* We thank the reviewer for pointing out the typos. The subscript $k$ is unnecessary in Algorithm 1, $\\bar{\\chi}(t)$ should be replaced by $\\chi(t)$ in Line 199, and $V(t)$ should be $Z(t)$ (the variability) in Line 482. We will correct these typos in the updated version.\n\n**References.**\n\nR. Yuan, et al., \"Linear convergence of natural policy gradient methods with log-linear policies.\" arXiv preprint arXiv:2210.01400 (2022).\n\nL. Wang et al., \"Neural policy gradient methods: global optimality and rates of convergence.\" International Conference on Learning Representations (2019).\n\nB. Scherrer et al., “Approximate modified policy iteration and its application to the game of tetris.” J. Mach. Learn. Res., vol. 16, pp. 1629–1676 (2015).\n\nA. Agarwal et al., \"On the theory of policy gradient methods: Optimality, approximation, and distribution shift.\" The Journal of Machine Learning Research 22.1: 4431-4506 (2021).\n\nT. Xie, et al., \"The role of coverage in online reinforcement learning.\" arXiv preprint arXiv:2210.04157 (2022)."}, {"review_id": "GjIrhcVWM2", "reviewer": "Reviewer_ZkyR", "summary": "The authors propose and study variants of TD(0) and Natural Actor-Critic that provably converge under (on-policy in the case of TD(0)) linear function approximation when the rewards may not have finite second moment or variance, but instead a finite (1+p) moment for $p \\in (0,1]$; the authors use this as the definition of \"heavy-tailed\" rewards.\n\nThe techniques used include:\n- Clipping the update direction using a decaying threshold\n- Using Holder's inequality + the decaying threshold to control the bias introduced by clipping the update direction, where in the normal analysis, one would upper-bound the expected noise by zero.\n\nThe rest of the techniques are otherwise similar to well-known previous work, in particular by Bhandari et al. 2018 (at least in essence, e.g., there is no difference in doing a Lyapunov analysis or using the Online-Gradient-Descent update bound for $g_t$ and $\\Theta_t$). Additional assumptions used include:\n1. realizability, and \n2. knowledge of a projection radius containing the optimum.\n\nThe authors complement the analysis with numerical results.", "questions": "Please comment on the weaknesses mentioned above. In particular:\n\n- The strength of the heavy-tailed assumption.\n- How hard it is to relax the projection onto ball of radius $\\rho$ for each of the iid and Markov cases?\n- Do you  need the realizability assumption if you instead bound the loss defined by $\\phi^T \\theta*$?", "limitations": "The technical limitations were already discussed in the \"Weaknesses\" and \"Questions\" section. This is a theoretical work so wider societal impacts are not apparent and addressable at this level.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The paper is very well-written. The logic follows clearly and easily. Examples are given when appropriate. The assumptions are laid out clearly. It's a nice, easy-to-follow read for a theoretician.\n\nThe paper contains the typical interesting (even if standard) results: the robust step-size case, the $1/t$ step-size case with knowledge of $\\lambda_\\textnormal{min}$, the simulator/i.i.d. sample case, and the Markov sample case under uniform exponential mixing.\n\nWhen $p=1$, the results naturally fall back to the $O(1/\\sqrt{T})$ and $O(1/T)$ rates of [4].\n\nConsidering NAC strengthens the paper, covering both policy-evaluation and control.", "weaknesses": "From a technical point of view, the assumptions are rather strong. Specifically,\n\n- Realizability is assumed, which is not really required for this MRP setting.\n- In addition, it is assumed that we have knowledge of an upper-bound $\\rho$ on the norm of the optimal $\\Theta^*$. This is not required by e.g., Bhandari et. al. 2018.\n- \"Heavy-tail\" is defined as satisfying a relaxed version of the usual (non-heavy-tailed) assumption: degree 2 is replaced by degree $1+p$ for $p \\in (0,1]$. In addition, it is assumed that this value $p$ is known. Does this definition suite the examples of heavy-tailed rewards given in the introduction?\n\nIn terms of related work, I am not entirely convinced that (as written on line 112), the cases of SGD and RL really differ here, at least as far as the main technique for introducing and handling bias (diminishing threshold + Holders on top of the noise term) is concerned. \n\nFinally, a recent (perhaps concurrent?) work (https://arxiv.org/pdf/2205.08464.pdf), considers defining and using robust losses instead of gradient-clipping. The merits and shortcomings of the two different approaches are worth discussing. The references therein also point to previous work (without theoretical guarantees) that use clipping of the rewards, the errors, or the update directions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the comments and questions. Below, we provide answers to the questions.\n\n- *Question 1.* We have provided our comments regarding the realizability assumption in our general response above.\n\n- *Question 2.* We thank the reviewer for this important question. While projection onto a general set can be computationally complex, fortunately projection onto a simple structure such as a $\\ell_2$-ball around 0 with radius $\\rho$ is a low-complexity operation. As such, this is considered in our design. Alternatively, the projection step can be eliminated by using early stopping methods as in (Cayci et al., 2023). We can add a comment related to this in our update. \n\n- *Question 3.* Exactly. If the error is defined with respect to the best in-class approximator $\\langle\\Phi(x), \\Theta^\\star\\rangle$ rather than the true value function, the realizability assumption can be eliminated.\n\nWe provide our responses to the comments and questions raised by the reviewer in the Weaknesses section below. We would like to thank the reviewer for the reference. We will cite the reference in the updated version with appropriate commentary.\n\n- Realizability can be assumed as we discussed in our general response, by incorporating the approximation error into the error bound \nin the general case.\n\n- As the reviewer pointed out, the techniques outlined in Section 8.2 of (Bhandari et al., 2018) regarding the choice of projection radius $\\rho$ can be used in our work as well. We will comment on this in our update.\n\n- Our statistical assumption on heavy-tailed rewards, i.e., existence of moments of order $1+p$ for some $p\\in(0,1]$, is satisfied by heavy-tailed distributions that are traditionally used for modeling, such as Pareto distribution with parameter $\\alpha\\in(1,2]$. Such power-law distributions are widely used in modeling various phenomena, including job sizes and delay statistics in computing and communication systems (Harchol-Balter, 2002) (Wei and He, 2007). We have also provided a comment on this in our general response.\n\n**References.**\n\nM. Harchol-Balter, \"Task Assignment with Unknown Duration.\" Journal of the ACM 49.2: 260-288 (2002).\n\nZ. Wei and J. He, \"Modeling end-to-end delay using pareto distribution.\" Second International Conference on Internet Monitoring and Protection (ICIMP 2007). IEEE, 2007.\n\nS. Cayci et al., \"Sample complexity and overparameterization bounds for temporal difference learning with neural network approximation.\" IEEE Transactions on Automatic Control, vol. 68, no. 5, pp. 2891-2905 (2023)."}, {"review_id": "ZnpQ1ANSb0", "reviewer": "Reviewer_z9uh", "summary": "The paper studies the value function estimation problem when the reward of the MDP is heavy tail. A robust version of TD learning is proposed which introduces a clipping step to the algorithm. The authors give both the theoretical analysis and numerical experiments for the proposed algorithm. And they further applied the robust TD learning algorithm to the policy optimization problem, and give a theoretical analysis for it. ", "questions": "In the experiment results, the curve for TD learning has a rapid increase in error at the initial phase. This is an interesting phenomenon given that the curve represents the averaged performance. Could the authors provide any comments on it? ", "limitations": "There is not a section about limitation. Since the work is mainly focused on the theoretical analysis, it shouldn't have a direct negative social impact. ", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper studies an important and interesting problem. The presentation is clear and the arguments are well supported by both theoretical and empirical evidence. ", "weaknesses": "The presentation can be improved. In algorithm 1, the variables have a subscript k which is not needed in this algorithm. The proof part skips some details, such as the end of the proof of Theorem 1. Some notations are not defined, such as the total variation and the \\mu-norm. The analysis shares a similar framework with that in [4], which limits the theoretical novelty of the analysis. The result mainly applies to the i.i.d. sampling case. And due to the mixing time assumption, the Markovian sampling case is essentially the same as the i.i.d. case, as one can easily get a near-independent sequence by subsampling. The experiments are conducted on artificial problems, and real-world application related experiments are not presented in the paper. The experiments are only about the value estimation, but do not solve the downstream policy optimization task. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and questions. \n\n- We refer to our general response above for our contributions, and for differences with [4] (i.e., Bhandari et al., 2018). \n\n- We thank the reviewer for pointing out the typo, we will remove the subscript $k$ in the updated version.\n\nBelow, we provide our answer to the question raised by the reviewer.\n\n- *Question 1.* In the heavy-tailed case, there is a large probability that the gradient noise will be very large. Initially, since the number of samples (i.e., number of TD learning iterations) is small, this very large gradient noise will cause a significant deviation in different directions than the descent direction even for the average-iterate, causing a large mean-squared error initially. As the number of iterations increase, the gradient noise will be canceled with the help of the gradient clipping and point the direction of improvement, which leads to vanishing error eventually."}, {"review_id": "jhNidXp0ad", "reviewer": "Reviewer_db5F", "summary": "This work discusses the failure of classical TD learning under heavy-tailed reward. This phenomenon motivates the author to propose a new technique, robust TD learning, with a dynamic gradient clipping mechanism to overcome this issue. The theoretical convergence rates for both in-expectation and high-probability cases are provided to ensure the convergence of this new algorithm under heavy-tailed reward. Some empirical experiments are taken to verify the theoretical result.", "questions": "1. It seems that some heavy-tailed distributions cannot satisfy both Assumption 1.2 and Assumption 1.3. For example, Cauthy distribution and Pareto(1, 1) distribution, because they have an infinite expectation. Do I misunderstand something here?  \n\n2. Does Theorem 3 directly imply Theorem 2? Why is it necessary to derive two bounds here? If I simply take an expectation on both sides of Theorem 3: (1) with the probability $1-\\delta$, it has the same rate as Theorem 2; (2) with the probability $delta$, bounding everything by a sufficiently large constant. Then tuning the parameter $delta$ could lead to the in-expectation bound.", "limitations": "This is a purely theoretical paper so no limitations and potential negative societal impact.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The question raised at the beginning of this paper, \"Can temporal difference learning with function approximation be modified to provably achieve global optimality under stochastic rewards with heavy tails?\" is well addressed by proposing a new algorithm and providing the convergence upper bounds. According to the related works, this problem has not been solved before.\n\nRegarding the quality and clarity, the whole paper is complete and well-presented except for some minor issues. \n\nThe motivation example is clear, and it well justifies the issue that this paper aims to solve, which makes this paper well-motivated on the theoretical side. Also, two applications are provided and formulated in the described senario. I believe this paper has made a clear contribution.\n\n", "weaknesses": "Lack of discussions on the assumptions: I agree that these assumptions are very standard in the convergence analysis of TD-based algorithms, but it is necessary to add more backgrounds. More explicitly, about the definition of heavy-tailed, some well-known heavy-tailed distributions may have infinite expectation (e.g. Cauchy distribution and Pareto distribution Pareto(1, 1)). This make me confused about Assumption 1.2.\n\nPresentation: The parameter $p$ has never been clearly explained until Assumption 1 (on page 4), though it has been used in Main contributions and Abstract.\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback and questions. Below, we provide our answers.\n\n- *Question 1.* Regarding Assumption 1.2, please also see our general response above. As the reviewer pointed out, our Assumption 1.2 implies that the random reward has finite mean and potentially infinite variance. Many important probability distributions that are used for statistical modeling in computing and communication systems satisfy this assumption. For example, Pareto distributions $\\mathbb{P}(X > x)\\leq c/x^{1+p}$ for some $p\\in(0,1)$ satisfy the aforementioned assumption, among other power-law distributions with finite mean and potentially infinite variance.\n\n- *Question 2.* We thank the reviewer for this question. The main difference between Theorem 2 and Theorem 3 is about sampling. In Theorem 3, we proved the result under iid sampling (Assumption 2a), while Theorem 2 is under more general Markovian sampling (Assumption 2b)."}, {"review_id": "8qrQnidkUW", "reviewer": "Reviewer_jt3m", "summary": "This paper studies the TD and NAC with heavy tailed reward noise. The authors provide both theoretical results and the numerical verification to support their claims.", "questions": "- My major concern on this paper is in the weakness section regarding the contribution. It could be better highlighted if the authors can demonstrate some non-trivial processes obtaining this $p / (1 + p) $ style result for the heavy-tailed noise.", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper is well written and easy to follow. The numerical results firmly support their theoretical claims and show the advantage of the robust algorithm. The theoretical results seem correct to me.\n- The authors suggest several practical cases where heavy-tailed reward noises are crucial and the robustness estimation algorithm can help to improve the performance. ", "weaknesses": "- Comparing with the previous TD learning results [4], it's not clear to me what's the major contribution of this paper. Is it simply combining the result and analysis in [4] and the concentration analysis for heavy-tailed noise (usually the robust-mean results)? \n- The algorithm parameter needs the knowledge of $p$, where I wonder how to estimate it in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback and questions. Below, we provide our answers to the comments in the Weaknesses section.\n\n- *W1: Contributions.* Please refer to our general response for our contributions and the differences between our paper and existing works in the literature.\n\n- *W2: Knowledge of $p$.* In our work, we assumed that moments of order $1+p$ for some $p\\in(0,1)$ exist. $p$ is estimated in practice by using the celebrated Hill estimator in extreme value theory (Resnick and Starica, 1998; Gomes et al., 2000). We also note that the exact knowledge of the tail index is not necessary. For example, for $R \\sim Pareto(1, 1+p_0)$ distributed rewards for some $p_0\\in(0,1]$, an upper bound $u$ on $\\mathbb{E}[|R|^{1+p}]$ can be used in the algorithm for any $p\\in(0,p_0)$. The performance of the algorithm depends on the accuracy of $u$ as an upper bound to the raw moments of order $1+p$.\n\nOur answer to the question raised by the reviewer is as follows.\n\n- *Question 1.* We thank the reviewer for pointing this out. A wide class of processes including Pareto distribution with parameter $\\alpha\\in(1,2)$ satisfy the moment assumptions in our paper, among other power-law distributions with finite moments of order $\\alpha\\in(1,2]$. Please also refer to our general response. We will clarify this part in the updated version.\n\n**References:**\n\nS. Resnick and C. Stărică, \"Tail index estimation for dependent data.\" The Annals of Applied Probability 8.4: 1156-1183 (1998)\n\nC. P. Gomes et al., \"Heavy-tailed phenomena in satisfiability and constraint satisfaction problems.\" Journal of automated reasoning 24.1-2: 67-100 (2000)."}, {"review_id": "BLYGeD5S2v", "reviewer": "Reviewer_GiX9", "summary": "This paper studies the problem of reinforcement learning under heavy-tailed reward. The paper present two algorithms: robust TD learning and robust NPG that achieves polynomial sample complexity in the generative setting. ", "questions": "See above.", "limitations": "NA", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The problem of heavy tail reward is important and understudied in RL. ", "weaknesses": "While the paper is well-written, I'm having trouble appreciating the technique contribution in this paper. Could the authors elaborate what techniques/results in the paper goes beyond a straight-forward combination of (1) robust mean estimation under heavy tail distribution and (2) existing analysis of TD learning and NPG?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback and questions. Please refer to our general response above for our contributions, and differences of our work with the existing papers."}]

Author rebuttal:
We would like to thank the reviewers for their very valuable feedback. In the following, we provide a general response to the questions commonly raised by the reviewers. In order to address specific questions, we will post individual comments.

**1. Realizability assumption and approximation error.** We note that the realizability assumption (Assumption 3) allows us to present our convergence rate results in a clear format. However, all of the results in the paper can be more generally stated without it by incorporating the unavoidable approximation error in the general case. As a showcase, we can state Theorem 1.a without Assumption 3 as follows.

*Theorem 1.a* Let $\epsilon_{app}=\min_{\Theta\in B_2(0,\rho)}\sqrt{\mathbb{E}[|\mathcal{V}(x)-f_\Theta(x)|^2]}$. Under Assumptions 1 and 2.a, with $b_t=(ut)^\frac{1}{1+p}$ and $\eta = \frac{2\rho(1-\gamma)}{(uT)^\frac{1}{1+p}}$, we have $\mathbb{E}|\mathcal{V}(x)-\langle\bar{\Theta}(T),\Phi(x)\rangle|^2\leq \frac{6\rho u^\frac{1}{1+p}}{(1-\gamma)T^\frac{p}{1+p}}+2(\rho+\frac{1}{1-\gamma})\epsilon_{app}$.

Here, note that $\epsilon_{app}=\min_{\Theta\in B_2(0,\rho)}\mathcal{L}(\Theta)$, where $\mathcal{L}(\Theta)=\sqrt{\mathbb{E}|\mathcal{V}(x)-\langle \Theta,\Phi(x)\rangle|^2}$, is the best possible error that can be achieved by using the specified approximation architecture $f_\Theta$. Thus, given $\{\Phi(x)\in\mathbb{R}^d:x\in\mathbb{X}\}$, the goal is to converge to the best $\Theta^\star$ that minimizes the total error $\mathcal{L}(\Theta)$. To make $\epsilon_{app}$ smaller, more powerful approximation schemes must be used. For example, larger dimension $d$ and projection radius $\rho$ implies smaller $\epsilon_{app}$ for linear approximation. The absence of Assumption 3 can be handled exactly the same way for all results in the paper. However, writing all results in this extended form creates an additional notational and conceptual complexity that is not the main focus of this work. As such, we omitted this extension in the original submission. Nevertheless, in the updated version, we will clarify this generalization with an example as we presented above. Similar approximation errors with respect to the true value function $\mathcal{V}$ appears in the seminal works [R1, R2] also, since these works consider convergence to the fixed point of the *projected* Bellman equation. The approximation error is characterized in Theorem 1.(c) in [R1] and Lemma 2 in [R2]. We will clarify this connection with the existing works in our update.

**2. Comparison with existing works.** We would like to thank the reviewers for pointing this out, and we will further clarify our contributions in the paper.

A major challenge that we tackled in this paper is to tame heavy-tailed noise in TD learning that stems from heavy-tailed rewards while keeping the computational efficiency of TD learning as a descent-type iterative stochastic method. In the heavy-tailed regime that we consider, the existing analyses of TD learning do not hold due to infinite variance of the gradient, including the seminal works [R1, R2]. Indeed, in practice, the original TD learning may diverge in the heavy-tailed regime, as we demonstrated in our numerical investigations.
There are many choices of robust mean-estimation techniques for heavy-tailed random variables, including median-of-means, Catoni’s M-estimator. In our design, we adopted the truncated (i.e., clipped) mean estimator to preserve the computational efficiency of TD learning as a descent-type iterative algorithm while taming heavy-tailed phenomenon in RL. However, achieving this goal introduces the following two main critical challenges, which we resolved in our work:
- The use of clipping introduces a bias in the stochastic semi-gradient in TD learning, and we identified in our Lyapunov analysis that this bias needs to be controlled along with the variance by adjusting the clipping radii appropriately. In particular, we achieved a favorable balance between this bias and variance of the stochastic semi-gradient by developing problem-dependent sequences of clipping radii, which drive the statistical error to 0 at the rates specified in the paper.
- The original truncated mean estimator is used for estimating the mean of a random variable from iid samples, which is not valid in TD learning. To address this non-iid behavior, we devised new Martingale techniques based on Freedman’s inequality on the Lyapunov drift in our analysis of Robust TD learning.

We acknowledge that these contributions were not clearly articulated in the original submission. Thanks to the comments of the reviewers, we will make sure that they are clarified in the updated version of the paper.

**3. Heavy-tailed regime** Our setting encapsulates reward distributions with a finite mean but potentially infinite variance as specified by our Assumption 1. This class includes well-known heavy-tailed distributions such as *Pareto* distribution with parameter $\alpha \in (1,2]$, but excludes more extreme distributions with infinite mean such as Cauchy, which would make the total discounted reward $\mathcal{V}$ infinite. We would like to note that, in many important RL applications, the reward distribution satisfies Assumption 1. For instance, in scheduling and routing applications in computing systems, job sizes and service times are heavy-tailed with finite mean and infinite variance: $p\in(0,0.25)$ in Bellcore, $p\in (0, 0.1)$ for the Web [R3] with $p$ in our Assumption 1. We will be happy to clarify these points in our update.

[R1] J. Tsitsiklis and B. van Roy. ”Analysis of temporal-diffference learning with function approximation.” Advances in neural information processing systems 9 (1996)

[R2] J. Bhandari et al., ”A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation.” arXiv preprint arXiv:1806.02450 (2018)

[R3] M. Harchol-Balter, ”Task Assignment with Unknown Duration.” Journal of the ACM 49.2:260-288 (2002)

Meta-review: This work explores the limitations of classical TD learning when dealing with heavy-tailed rewards. To address this, the authors introduce a novel technique called robust TD learning, which features a dynamic gradient clipping mechanism. Theoretical convergence rates for both expected and high-probability outcomes are provided to ensure the new algorithm's effectiveness under heavy-tailed rewards. Empirical experiments are conducted to validate the theoretical findings.

Evaluation:
The paper is clearly written and easy to comprehend.

While the research problem is compelling, some reviewers feel that the theoretical contributions lack depth. The authors' rebuttal did not fully convince the reviewers, and the meta-reviewer partially agrees with this assessment.

The authors do sufficiently address the issue of approximation error in their response. However, the RL setting described in the paper could be more nuanced. For example, is ergodicity required? How does the policy optimization approach solve the problem of online exploration? 

In summary, the paper is on the borderline of acceptance.
Decision: Accept (poster)