  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.
