\section{Introduction}
Policy gradient methods are a popular class of Reinforcement Learning (RL) methods among practitioners, as they are
amenable to parametric policy classes \cite{schulman2015high, schulman2017proximal}, resilient to modeling assumption mismatches \cite{agarwal2019optimality, agarwal2020pc}, and
they directly optimizing the cost function of interest. However, one current drawback of these methods and most existing RL algorithms is the lack of robustness to data corruption, which severely limits their applications to high-stack decision-making domains with highly noisy data, such as autonomous driving, quantitative trading, or medical diagnosis. 

In fact, data corruption can be a larger threat in the RL paradigm than in traditional supervised learning, because supervised learning is often applied in a controlled environment where data are collected and cleaned by highly-skilled data scientists and domain experts, whereas RL agents are developed to learn in the wild using raw feedbacks from the environment. While the increasing autonomy and less supervision mark a step closer to the goal of general artificial intelligence, they also make the learning system more susceptible to data corruption: autonomous vehicles can misread traffic signs when the signs are contaminated by adversarial stickers \cite{eykholt2018robust}; chatbot can be mistaught by a small group of tweeter users to make misogynistic and racist remarks \cite{neff2016automation}; recommendation systems can be fooled by a small number of fake clicks/reviews/comments to rank products higher than they should be. Despite the many vulnerabilities, \textit{robustness} against data corruption in RL has not been extensively studied only until recently. 

The existing works on \textit{robust} RL are mostly theoretical and can be viewed as a successor of the adversarial bandit literature. However, several drawbacks of this line of approach make them insufficient to modern real-world threats faced by RL agents. We elaborate them below:
\begin{enumerate}[leftmargin=*]
	\item \textbf{Reward vs. transition contamination}: The majority of prior works on adversarial RL
	focus on reward contamination \cite{even2009online, neu2010online, neu2012adversarial, zimin2013online, rosenberg2019online, jin2020learning}, while in reality the adversary often has stronger control during the adversarial interactions. For example, when a chatbot interacts with an adversarial user, the user has full control over both the rewards and transitions during that conversation episode.
	\item \textbf{Density of contamination}: The existing works that do handle adversarial/time-varying transitions can only tolerate \textit{sublinear} number of interactions being corrupted \cite{lykouris2019corruption, cheung2019non, ornik2019learning, ortner2019variational}. These methods would fail when the adversary's attack budget also grows linearly with time, which is often the case in practice.
	\item \textbf{Practicability}: The majority of these work focuses on the setting of tabular MDPs and cannot be applied to real-world RL problems that have large state and action spaces and require function approximations.
\end{enumerate}
In this work, we address the above shortcomings by developing a variant of natural policy gradient (NPG) methods that, under the linear value function assumption, are provably robust against strongly adaptive adversaries, who can \textbf{arbitrarily contaminate} both rewards and transitions in $\epsilon$ fraction of all learning episodes. {Our algorithm does not need to know $\epsilon$, and is adaptive to the contamination level.} Specifically, it guarantees to find an $\tilde O(\epsilon^{1/4})$-optimal policy in a polynomial number of steps. Complementarily, we also present a corresponding lower-bound, showing that no algorithm can consistently find a better than $\Omega(\epsilon)$ optimal policy, even with infinite data. In addition to the theoretical results, we also develop a neural network implementation of our algorithm which is shown to achieve strong robustness performance on the MuJoCo continuous control benchmarks \cite{todorov2012mujoco}, proving that our algorithm can be applied to real-world, high-dimensional RL problems.

\section{Related Work}
\paragraph{RL in standard MDPs.} Learning MDPs with stochastic rewards and transitions is relatively well-studied for the tabular case (that is, a finite number of states and actions).
For example, in the episodic setting, the UCRL2 algorithm \cite{auer2009near} achieves $O(\sqrt{H^4S^2AT})$ regret, where $H$ is the episode length, $S$ is the state space size, $A$ is the action space size, and $T$ is the total number of steps. Later the UCBVI algorithm \cite{azar2017minimax, dann2017unifying} achieves the optimal $O(\sqrt{H^2SAT})$ regret matching the lower-bound \cite{osband2016lower, dann2015sample}. Recent work extends the analysis to various linear setting \cite{jin2020provably,yang2019reinforcement, yang2019sample, zanette2020frequentist, ayoub2020model, zhou2020provably,cai2019provably,du2019provably,kakade2020information} with known linear feature. For unknown feature, \cite{agarwal2020flambe} proposes a sample efficient algorithm that explicitly learns feature representation under the assumption that the transition matrix is low rank.
Beyond the linear settings, there are works assuming the function class has low Eluder dimension which so far is known to be small only for linear functions and generalized linear models \cite{osband2014model}. For more general function approximation, \cite{jiang2017contextual,sun2019model} showed that polynomial sample complexity is achievable as long as the MDP and the given function class together induce low Bellman rank and Witness rank, which include almost all prior models such as tabular MDP, linear MDPs \cite{yang2019reinforcement,jin2020provably}, Kernelized nonlinear regulators \cite{kakade2020information}, low rank MDP \cite{agarwal2020flambe}, and Bellman completion under linear functions \cite{zanette2020frequentist}.

\paragraph{Policy Gradient and Policy Optimization}
Policy Gradient \cite{williams1992simple,sutton1999policy} and Policy optimization methods are widely used in practice \cite{kakade2002approximately,schulman2015high, schulman2017proximal} and have demonstrated amazing performance on challenging applications \cite{berner2019dota,akkaya2019solving}. Unlike model-based approach or Bellman-backup based approaches, PG methods directly optimize the objective function and are often more robust to model-misspecification \cite{agarwal2020pc}. In addition to being robust to model-misspecification, we show in this work that vanilla NPG is also robust to constant fraction and bounded adversarial corruption on both rewards and transitions.


\paragraph{RL with adversarial rewards.}  Almost all prior works on adversarial RL study the setting where the reward functions can be adversarial but the transitions are still stochastic and remain unchanged throughout the learning process. Specifically, at the beginning of each episode, the adversary must decide on a reward function for this episode, and can not change it for the rest of the episode. Also, the majority of these works focus on tabular MDPs. Early works on adversarial MDPs assume a known transition
function and full-information feedback. For example,
\cite{even2009online} proposes the algorithm MDP-E and
proves a regret bound of $\tilde O(\tau \sqrt{T\log A})$ in the non-episodic setting, where $\tau$ is the mixing time of the MDP;
Later, \cite{zimin2013online} consider the episodic
setting and propose the O-REPS algorithm which applies
Online Mirror Descent over the space of occupancy measures, a key component adopted by \cite{rosenberg2019online} and \cite{jin2020learning}. O-REPS achieves the optimal regret
$\tilde O(\sqrt{H^2T\log(SA)})$ in this setting.
Several works consider the harder bandit feedback model while still assuming known transitions. The work \cite{neu2010online}
achieves regret $\tilde O(\sqrt{H^3AT}/\alpha)$ assuming that all states are reachable with some probability $\alpha$ under all policies. Later, \cite{neu2010online} eliminates the dependence on $\alpha$
but only achieves $O(T^{2/3})$ regret. The O-REPS algorithm
of \cite{zimin2013online} again achieves the optimal regret $\tilde O(\sqrt{H^3SAT})$.
To deal with unknown transitions, \cite{neu2012adversarial} proposes
the Follow the Perturbed Optimistic Policy algorithm and achieves $\tilde O(\sqrt{H^2S^2A^2T})$ regret given full-information feedback. Combining the idea of confidence sets and Online Mirror Descent, the UC-O-REPS algorithm of \cite{rosenberg2019online} improves the
regret to $\tilde O(\sqrt{H^2S^2AT})$.
A few recent works start to consider the hardest setting assuming unknown transition as well as bandit feedback. \cite{rosenberg2019online} achieves $O(T^{3/4})$ regret, which is improved by \cite{jin2020learning} to $\tilde O(\sqrt{H^2S^2AT})$, matching the regret of UC-O-REPS in the full information setting. Also, note that the lower
bound of $\Omega(\sqrt{H^2SAT})$ \cite{jin2018q} still applies. In summary, it is found that on tabular MDPs with oblivious reward contamination, an $O(\sqrt{T})$ regret can still be achieved. Recent improvements include best-of-both-worlds algorithms \cite{jin2020simultaneously}, data-dependent bound \cite{lee2020bias} and extension to linear function approximation \cite{neu2020online}.

\paragraph{RL with adversarial transitions and rewards.} Very few prior works study the problem of both adversarial transitions and adversarial rewards, in fact, only one that we are aware of \cite{lykouris2019corruption}. They study a setting where only a constant $C$ number of episodes can be corrupted by the adversary, and most of their technical effort dedicate to designing an algorithm that is agnostic to $C$, i.e. the algorithm doesn't need to know the contamination level ahead of time. As a result, their algorithm takes a multi-layer structure and cannot be easily implemented in practice. Their algorithm achieves a regret of $O(C\sqrt{T})$ for tabular MDPs and $O(C^2\sqrt{T})$ for linear MDPs, which unfortunately becomes vacuous when $C \geq \Omega(\sqrt{T})$ and $C \geq \Omega(T^{1/4})$, respectively. Note that the contamination ratio $C / T$ approaches zero when $T$ increases,  and hence their algorithm cannot handle constant fraction contamination.
Notably, in all of the above works, the adversary can \textit{partially adapt} to the learner's behavior, in the sense that the adversary can pick an adversary MDP $\M_k$ or reward function $r_k$ at the start of episode $k$ based on the history of interactions so far. However, it can no longer adapt its strategy after the episode starts, and therefore, the learner can still use a randomization strategy to trick the adversary.

A separate line of work studies the \textit{online MDP} setting, where the MDP is not adversarial but \textit{slowly} change over time, and the amount of change is bounded under a total-variation metric \cite{cheung2019non, ornik2019learning, ortner2019variational, domingues2020kernel}. Due to the slow-changing nature of the environment, algorithms in these works typically uses a sliding window approach where the algorithm keeps throwing away old data and only learns a policy from recent data, assuming that most of them come from the MDP that the agent is currently experiencing. These methods typically achieve a regret in the form of $O(\Delta^c K^{1-c})$, where $\Delta$ is the total variation bound. It is worth noting that all of these regrets become vacuous when the amount of variation is linear in time, i.e. $\Delta \geq \Omega(T)$. Separately, it is shown that when both the transitions and the rewards are adversarial in every episode, the problem is at least as hard as stochastic parity problem, for which no computationally efficient algorithm exists \cite{yadkori2013online}.

\paragraph{Learning robust controller.} A different type of robustness has also been considered in RL \cite{pinto2017robust, derman2020bayesian} and robust control \cite{zhou1998essentials, petersen2012robust}, where the goal is to learn a control policy that is robust to potential misalignment between the training and deployment environment. Such approaches are often conservative, i.e. the learned polices are sub-optimal even if there is no corruption. In comparison, our approach can learn as effectively as standard RL algorithms without corruption. Interestingly, parallel to our work, a line of concurrent work in the robust control literature \cite{zhang2020policy, zhang2020stability, zhang2021derivative} has also found that policy optimization method enjoys some implicit regularization/robustness property that can automatically converge to robust control policies. An interesting future direction could be to understand the connection between these two kind of robustness.


\paragraph{Robust statistics.} One of the most important discoveries in modern robust statistics is that there exists computationally efficient and robust estimator that can learn near-optimally even under the strongest adaptive adversary. 
For example, in the classic problem of Gaussian mean estimation, the recent works \cite{diakonikolas2016robust, lai2016agnostic} present the first computational and sample-efficient algorithms.
The algorithm in \cite{diakonikolas2016robust} can generate a robust mean estimate $\hat\mu$, such that $\|\hat\mu-\mu\|_2\leq O(\epsilon \sqrt{\log{(1/\epsilon)}})$ under $\epsilon$ corruption. 
Crucially, the error bound does not scale with the dimension $d$ of the problem, suggesting that the estimator remains robust even in high dimensional problems. 
Similar results have since been developed for robust mean estimation under weaker assumptions \cite{diakonikolas2017being}, and for supervised learning and unsupervised learning tasks \cite{charikar2017learning, diakonikolas2019sever}. We refer readers to \cite{diakonikolas2019recent} for a more thorough survey of recent advances in high-dimensional robust statistics.

\section{Problem Definitions}
\label{section:definitions}
A Markov Decision Process (MDP) $\mathcal{M} = (\Scal, \Acal, P, r, \gamma,\mu_0)$
is specified by a state space $\Scal$, an action space $\Acal$, a
transition model $P: \mathcal{S} \times \mathcal{A} \rightarrow \Delta(\mathcal{S})$ (where $\Delta(\mathcal{S})$ denotes a distribution over $\mathcal{S}$),
a (stochastic and possibly unbounded) reward function $r: \Scal\times \Acal \to \Delta(\R)$,
a discounting factor $\gamma \in [0, 1)$, and an initial state
distribution $\mu_0\in\Delta(\Scal)$, i.e. $s_0\sim \mu_0$. In this paper, we assume that $\Acal$ is a small and finite set, and denote $A = \lvert\Acal\rvert$. A policy $\pi: \Scal \to
\Delta(\Acal)$
specifies a decision-making strategy in which the agent chooses
actions based on the current state, i.e., $a \sim\pi(\cdot | s)$.

The value function $V^\pi: \Scal \to \mathbb{R}$ is
defined as the expected discounted sum of future rewards, starting at state $s$
and executing $\pi$, i.e.
$
V^\pi(s) := \EE \left[\sum_{t=0}^\infty \gamma^t  r(s_t, a_t)
| \pi, s_0 = s\right],
$
where the expectation is taken with respect to the randomness of the policy and environment $\mathcal{M}$.
Similarly, the \emph{state-action} value function $Q^\pi: \Scal
\times \Acal \to \mathbb{R}$
is defined as
$
Q^\pi(s,a) := \EE\left[\sum_{t=0}^\infty \gamma^t  r(s_t, a_t) | \pi,
s_0 = s, a_0 = a \right].
$



We define the discounted state-action
distribution $d_{s}^\pi$ of a policy $\pi$:
$
d_{s'}^\pi(s,a) := (1-\gamma) \sum_{t=0}^\infty \gamma^t {\Pr}^\pi(s_t=s,a_t=a|s_0=s'),
$
where $\Pr^\pi(s_t=s,a_t=a|s_0=s')$ is the
probability that $s_t=s$ and $a_t=a$, after we execute $\pi$ from $t=0$ onwards starting at state
$s'$ in model $\mathcal{M}$. Similarly, we define $d^{\pi}_{s',a'}(s,a)$ as:
$
d^{\pi}_{s',a'}(s,a) := (1-\gamma) \sum_{t=0}^{\infty} \gamma^t {\Pr}^{\pi}(s_t = s, a_t = s | s_0=s', a_0 = a').
$
For any state-action distribution $\nu$, we write $d^{\pi}_{\nu}(s,a):= \sum_{(s',a')\in\mathcal{S}\times\mathcal{A}} \nu(s',a') d^{\pi}_{s',a'}(s,a)$. For ease of presentation, we assume that the agent can reset to $s_0\sim \mu_0$ at any point in the trajectory. We denote $d^{\pi}_{\nu}(s) = \sum_{a}d^{\pi}_{\nu}(s,a)$. 

The goal of the agent is to find a policy $\pi$
that maximizes the expected value from the starting state $s_0$, i.e. the optimization problem is:
$  \max_\pi V^{\pi}(\mu_0) \defeq \EE_{s\sim\mu_0}V^{\pi}(s)$,
where the $\max$ is over some policy class.

For completeness, we specify a $d^{\pi}_{\nu}$-sampler and an unbiased estimator of $Q^{\pi}(s,a)$ in Algorithm~\ref{alg:sampler_est}, which are standard in discounted MDPs~\cite{agarwal2019optimality,agarwal2020pc}. The $d^{\pi}_\nu$ sampler samples $\sa$ i.i.d from $d^{\pi}_{\nu}$, and the $Q^{\pi}$ sampler returns an unbiased estimate of $Q^{\pi}(s,a)$ for a given pair $(s,a)$ by a single roll-out from $\sa$. 
Later, when we define the contamination model and the sample complexity of learning, we treat each call of $d^{\pi}_{\nu}$-sampler (optionally followed by a $Q^{\pi}(s,a)$-estimator) as a \emph{single episode}, as in practice both of these procedures can be achieved in a single roll-out from $\mu_0$.



\begin{assumption}[Linear Q function]\label{ass:linearMDP}
	For the theoretical analysis, we focus on the setting of linear value function approximation. In particular, we assume that there exists a feature map $\phi: \S\times \A\rightarrow \R^d$, such that for any $(s,a)\in \S \times \A$ and any policy $\pi:\S\to \Delta_\A$, we have
	\begin{eqnarray}
		Q^\pi(s,a) = \phi(s,a)^\top w^\pi \text{, for some } \|w^\pi\|\leq W
	\end{eqnarray}
	We also assume that the feature is bounded, i.e. $\max_{s,a}\|\phi(s,a)\|_2\leq 1$, and the reward function has bounded first and second moments, i.e. $\E{}{r(s,a)}\in [0,1]$ and $\mbox{Var}(r(s,a))\leq \sigma^2$ for all $(s,a)$.
\end{assumption}

\begin{remark}
	Assumption \ref{ass:linearMDP} is satisfied, for example, in tabular MDPs and linear MDPs of \cite{jin2020provably} or \cite{yang2019sample}.
	Unlike most theoretical RL literature, we allow the reward to be stochastic and unbounded. Such a setup aligns better with applications with a low signal-to-noise ratio and motivates the requirement for nontrivial robust learning techniques.
\end{remark}
\paragraph{Notation.}
When clear from context, we write $d^\pi(s,a)$ and $d^\pi(s)$ to denote
$d_{\mu_0}^\pi(s,a)$ and $d^{\pi}_{\mu_0}(s)$ respectively.
For iterative algorithms which obtain policies at each episode, we let $V^{i}$,$Q^{i}$ and $A^{i}$ denote the
corresponding quantities associated with episode $i$.
For a vector $v$, we denote $\|v\|_2=\sqrt{\sum_i v_i^2}$, $\|v\|_1=\sum_i |v_i|$,
and $\|v\|_\infty=\max_i |v_i|$. 
We use $\text{Uniform}(\Acal)$ (in short $\text{Unif}_{\Acal}$) to represent a uniform distribution over the set $\Acal$.



\subsection{The Contamination Model}
In this paper, we study the robustness of policy gradient methods under the \textit{$\epsilon$-contamination model}, a widely studied adversarial model in the robust statistics literature, e.g. see \cite{diakonikolas2016robust}. In the classic robust mean estimation problem, given a dataset $D$ and a learning algorithm $f$, the $\epsilon$-contamination model assumes that the adversary has full knowledge of the dataset $D$ and the learning algorithm $f$, and can arbitrarily change $\epsilon$-fraction of the data in the dataset and then send the contaminated data to the learner. The goal of the learner is to identify an $O(\poly(\epsilon))$-optimal estimator of the mean despite the $\epsilon$-contamination. 

Unfortunately, the original $\epsilon$-contamination model is defined for the offline learning setting and does not directly generalize to the online setting, because it doesn't specify the availability of knowledge and the order of actions between the adversary and the learner in the time dimension. 
In this paper, we define the $\epsilon$-contamination model for online learning as follows:
\begin{definition}[$\epsilon$-contamination model for Reinforcement Learning]\label{def: eps_con}
	Given $\epsilon$ and the clean MDP $\M$, an $\epsilon$-contamination adversary operates as follows:
	\begin{enumerate}[leftmargin=*]
		\item The adversary has full knowledge of the MDP $\M$ and the learning algorithm, and observes all the historical interactions.I 
		\item At any time step $t$, the adversary observes the current state-action pair $(s_t,a_t)$, as well as the reward and next state returned by the environment, $(r_t,s_{t+1})$. He then can decide whether to replace $(r_t,s_{t+1})$ with an arbitrary reward and next state $(r^\dagger_t,s^\dagger_{t+1})\in\R \times \S$.
		\item The only constraint on the adversary is that if the learning process terminates after $K$ episodes, he can contaminate in at most $\epsilon K$ episodes.
	\end{enumerate}
\end{definition}
Compared to the standard adversarial models studied in online learning \cite{shalev2011online}, adversarial bandits \cite{bubeck2012regret, lykouris2018stochastic, gupta2019better} and adversarial RL \cite{lykouris2019corruption, jin2020learning}, the $\epsilon$-contamination model in Definition \ref{def: eps_con} is stronger in several ways:
(1) The adversary can adaptively attack after observing the action of the learner as well as the feedback from the clean environments;
(2) the adversary can perturb the data arbitrarily (any real-valued reward and any next state from the state space) rather than sampling it from a pre-specified bounded adversarial reward function or adversarial MDP.

Given the contamination model, our first result is a lower-bound, showing that under the $\epsilon$-contamination model, one can only hope to find an $O(\epsilon)$-optimal policy. Exact optimal policy identification is not possible even with infinite data.
\begin{theorem}[lower bound]\label{thm:lb}
	For any algorithm, there exists an MDP such that the algorithm fails to find an $\left(\frac{\epsilon}{2(1-\gamma)}\right)$-optimal policy under the $\epsilon$-contamination model with a probability of at least $1/4$.
\end{theorem}
The high-level idea is that we can construct two MDPs, $M$ and $M'$, with the following properties: 1. No policy can be $O(\epsilon/(1-\gamma))$ optimal on both MDP simultaneously. 2. An $\epsilon$-contamination adversary can with large probability mimic one MDP via contamination in the other, regardless of the learner's behavior. Therefore, under contamination, the learner will not be able to distinguish $M$ and $M'$ and must suffer $\Omega(\epsilon/(1-\gamma))$ gap on at least one of them.

\subsection{Background on NPG} 
Given a differentiable parameterized policy $\pi_{\theta}: \mathcal{S}\to\Delta(\mathcal{A})$, NPG
can be written in the following actor-critc style update form. With the dataset $\{s_i,a_i, \widehat{Q}^{\pi_{\theta}}(s_i,a_i)\}_{i=1}^N$ where $s_i,a_i\sim d^{\pi_\theta}_{\nu}$, and $\widehat{Q}^{\pi_\theta}(s_i,a_i)$ is unbiased estimate of $Q^{\pi_\theta}(s,a)$ (e.g., via $Q^{\pi}$-estimator), we have
\begin{align}\label{eq:NPG_update}
	&\widehat{w} \in \argmin_{w: \|w\|_2 \leq W} \sum_{i=1}^N \left( w^{\top}\nabla \log\pi_\theta(a_i|s_i) - \widehat{Q}^{\pi_{\theta}}(s_i,a_i) \right)^2\nonumber\\
	&\theta' = \theta + \eta \widehat{w}.
\end{align}
In theoretical part of this work, we focus on softmax linear policy, i.e., $\pi_{\theta}(a|s) \propto \exp(\theta^{\top}\phi(s,a))$. In this case, note that $\nabla \log\pi_\theta(a|s) = \phi(s,a)$, and
it is not hard to verify that the policy update procedure is equivalent to:
\begin{align*}
	\pi_{\theta'}(a|s) \propto \pi_{\theta}(a|s) \exp\left( \eta \widehat{w}^{\top} \phi(s,a) \right), \quad \forall s,a,
\end{align*} which is equivalent to running Mirror Descent on each state with a reward vector $\widehat{w}^{\top}\phi(s,\cdot)\in\mathbb{R}^{|\A|}$. We refer readers to \cite{agarwal2019optimality} for more detailed explanation of NPG and the equivalence between the form in Eq.~\eqref{eq:NPG_update} and the classic form that uses Fisher information matrix. Similar to \cite{agarwal2019optimality}, we make the following assumption of having access to an exploratory reset distribution, under which it has been shown that NPG can converge to the optimal policy without contamination.

\begin{assumption}[Relative condition number]\label{assum:conditioning} With respect to any state-action distribution $\upsilon$,  define:
	\[
	\Sigma_\upsilon = \EE_{s,a \sim \upsilon}\left[ \phi_{s,a}\phi_{s,a}^\top\right],
	\]
	and define
	\[
	\sup_{w \in \R^d} \ \frac{w^\top \Sigma_{d^\star} w}
	{w^\top \Sigma_\nu w}
	=\kappa\text{, where }d^*(s,a) = d^{\pi^*}_{\mu_0}(s)\circ \text{Unif}_{\A}(a)
	\]
	We assume $\kappa$ is finite and small w.r.t. a reset distribution $\nu$ available to the learner at training time.
\end{assumption}



\section{The Natural Robustness of NPG Against Bounded corruption}\label{sec:npg}
Our first result shows that, surprisingly, NPG can already be robust against $\epsilon$-contamination, if the adversary can only generate small and bounded rewards. In particular, we assume that the adversarial rewards is bounded in $[0,1]$ (the feature $\phi(s,a)$ is already bounded).

\begin{theorem}[Natural robustness of NPG]\label{thm:npg_natural}
	Under assumptions \ref{ass:linearMDP} and \ref{assum:conditioning}, given a desired optimality gap $\alpha$, there exists a set of hyperparameters agnostic to the contamination level $\epsilon$, such that 
	Algorithm \ref{alg:q_npg_sample} guarantees with a $poly(1/\alpha, 1/(1-\gamma), |\A|,W,\sigma,\kappa)$ sample complexity that under $\epsilon$-contamination with adversarial rewards bounded in $[0,1]$, we have
	\begin{eqnarray}
		\EE\left[V^{*}(\mu_0) - V^{\hat\pi}(\mu_0)\right]
		\leq
		\tilde O\left(\max\left[\alpha, W\sqrt{\frac{|\Acal|\kappa\epsilon}{(1-\gamma)^3}} \mbox{ }\right]\right)\nonumber
	\end{eqnarray}
	where $\hat\pi$ is the uniform mixture of $\pi^{(1)}$ through $\pi^{(T)}$.
\end{theorem}
A few remarks are in order.
\begin{remark}[Agnostic to the contamination level $\epsilon$]
	It is worth emphasizing that to achieve the above bound, the hyperparameters of NPG are agnostic to the value of $\epsilon$, and so the algorithm can be applied in the more realistic setting where the agent does not have knowledge of the contamination level $\epsilon$, similar to what's achieved in \cite{lykouris2019corruption} with a complicated nested structure. The same property is also achieved by the FPG algorithm in the next section.
\end{remark}
\begin{remark}[Dimension-independent robustness guarantee]
	Theorem \ref{thm:npg_natural} guarantees that NPG can find an $O(\epsilon^{1/2})$-optimal policy after polynomial number of episodes, provided that $|\A|$ and $\kappa$ are small. Conceptually, the relative condition number $\kappa$ indicates how well-aligned the initial state distribution is to the occupancy distribution of the optimal policy. A good initial distribution can have a $\kappa$ as small as $1$, and so $\kappa$ is independent of $d$. Interested readers can refer to \cite{agarwal2019optimality} (Remark 6.3) for additional discussion on the relative condition number. Here, importantly, the optimality gap does not directly scale with $d$, and so the guarantee will not blow up on high-dimensional problems. This is an important attribute of robust learning algorithms heavily emphasized in the traditional robust statistics literature. 
\end{remark} 

The proof of Theorem \ref{thm:npg_natural} relies on the following NPG regret lemma, first developed by \cite{even2009online} for the MDP-Expert algorithm and later extend to NPG by \cite{agarwal2019optimality,agarwal2020pc}:
\begin{lemma}[NPG Regret Lemma]\label{thm:npg_regret}
	Suppose
	Assumption~\ref{ass:linearMDP} and \ref{assum:conditioning} hold and Algorithm \ref{alg:q_npg_sample}
	starts with $\theta^{(0)}=0$, $\eta
	=\sqrt{2\log |\Acal| /(W^2T)}$. Suppose in addition that the (random) sequence of iterates satisfies
	the assumption that
	\begin{equation}
		\EE\left[\EE_{s,a\sim d^{(t)}}\left[\left(Q^{\pi^{(t)}}(s,a)-\phi(s,a)^\top w^{(t)} \right)^2\right]\right]
		\leq \epsilon_{stat}^{(t)}.\nonumber
	\end{equation}
	Then, we have that
	\begin{align}
		\EE&\left[\sum_{t=1}^T \{V^{*}(\mu_0) - V^{(t)}(\mu_0) \}\right]\\
		&\qquad\leq
		\frac{W}{1-\gamma}\sqrt{2 \log |\Acal|T}
		+\sum_{t=1}^T \sqrt{ \frac{4|\Acal| \kappa \epsilon_{stat}^{(t)}}{(1-\gamma)^3}}.\nonumber
	\end{align}
\end{lemma}
Intuitively, Lemma \ref{thm:npg_regret} decompose the regret of NPG into two terms. The first term corresponds to the regret of standard mirror descent procedure, which scales with $\sqrt{T}$. The second term corresponds to the estimation error on the Q value, which acts as the reward signal for mirror descent. When not under attack,  estimation error $\epsilon_{stat}^{(t)}$ goes to zero as the number of samples $M$ gets larger, which in turn implies the global convergence of NPG. However, when under bounded attack, the generalization error $\epsilon_{stat}^{(t)}$ will not go to zero even with infinite data. Nevertheless, we can show that it is bounded by $O(\epsilon^{(t)})$ when the sample size $M$ is large enough, where $\epsilon^{(t)}$ denotes the fraction of episodes being corrupted in iteration $t$. Note that by definition, we have $\sum_{t} \varepsilon^{(t)} \leq \varepsilon T$.
\begin{lemma}[Robustness of linear regression under bounded contamination]\label{thm:robust_ols}
	Suppose the adversarial rewards are bounded in $[0,1]$, and in a particular iteration $t$, the adversary contaminates $\epsilon^{(t)}$ fraction of the episodes, then given M episodes, it is guaranteed that with probability at least $1-\delta$,
	\begin{align}
		\EE_{s,a\sim d^{(t)}}&\left[\left(Q^{\pi^{(t)}}(s,a)-\phi(s,a)^\top w^{(t)} \right)^2\right] \\
		&\leq 4 \left(W^2+WH\right)\left(\epsilon^{(t)} + \sqrt{\frac{8}{M}\log\frac{4d}{\delta}}\right).\nonumber
	\end{align}
	where $H = (\log \delta-\log M)/\log\gamma$ is the effective horizon.
\end{lemma}
This along with the NPG regret lemma guarantees that the expected regret of NPG is bounded by $O(\sqrt{T}+M^{-1/4}+\sqrt{\epsilon}T)$ which in turn guarantees to identify an $O(\sqrt{\epsilon})$-optimal policy.

In the special case of tabular MDPs, $\phi(s,a)$ will all be one-hot vectors and $W$ will in general by on the order of $O(\sqrt{SA})$, which means that the bound given by Theorem \ref{thm:npg_natural} still scales with the size of the state space. In the following corollary, we show that this dependency can be removed through a tighter analysis. 
\begin{corollary}[Dimension-free Robustness of NPG in tabular MDPs]\label{thm:npg_tabular}
	Given a tabular MDP and assumption \ref{assum:conditioning}, given a desired optimality gap $\alpha$, there exists a set of hyperparameters agnostic to the contamination level $\epsilon$, such that 
	Algorithm \ref{alg:q_npg_sample} guarantees with a $poly(1/\alpha, 1/(1-\gamma), |\A|,W,\sigma,\kappa)$ sample complexity that under $\epsilon$-contamination with adversarial rewards bounded in $[0,1]$, we have
	\begin{eqnarray}
		\EE\left[V^{*}(\mu_0) - V^{\hat\pi}(\mu_0)\right]
		\leq
		\tilde O\left(\max\left[\alpha, \sqrt{\frac{|\Acal|\kappa\epsilon}{(1-\gamma)^5}} \mbox{ }\right]\right)\nonumber
	\end{eqnarray}
	where $\hat\pi$ is the uniform mixture of $\pi^{(1)}$ through $\pi^{(T)}$.
\end{corollary}
In the more general case of linear MDP, $W$ will not necessarily scale with $d$ in an obvious way and thus we leave Theorem \ref{thm:npg_natural} untouched. 



\section{FPG: Robust NPG Against Unbounded Corruption}\label{sec:fpg}
\begin{algorithm}[!t]
	\caption{$d_{\nu}^\pi$ sampler and $Q^{\pi}$ estimator}
	\label{alg:sampler_est}
	\begin{algorithmic}[1]
		\setcounter{algorithm}{-1}
		\Function{$d_{\nu}^\pi$-sampler}{}
		\State  \hspace*{-0.1cm}\textbf{Input}:  A reset distribution $\nu\in\Delta(\Scal\times\Acal)$.
		\State Sample $s_0,a_0 \sim \nu$.
		\State Execute $\pi$ from $s_0, a_0$; at any step $t$ with $(s_t,a_t)$, return $(s_t,a_t)$ with probability $1-\gamma$.
		\caption{$d^{\pi}$ sampler and $Q^{\pi}$ estimator}
		\EndFunction
		\Function{$Q^\pi$-estimator}{}
		\State  \hspace*{-0.1cm}\textbf{Input}:  current state-action $\sa$, a policy $\pi$
		\State Execute $\pi$ from $(s_0,a_0) = (s, a)$; at step $t$ with $(s_t,a_t)$, terminate with probability $1-\gamma$.
		\State  \hspace*{-0.1cm}\textbf{Return}: $\widehat{Q}^{\pi}\sa = \sum_{i=0}^t r(s_i,a_i)$.
		\caption{$d_{\nu}^\pi$ sampler and $Q^{\pi}$ estimator}
		\EndFunction
		\setcounter{algorithm}{1}
	\end{algorithmic}
{\color{red}[In an adversarial episode, the adversary can hijack the $d_{\nu}^\pi$ sampler to return any $(s,a)$ pair and the $Q^\pi$-estimator to return any $\widehat{Q}^{\pi}\sa\in\R$.]}
\end{algorithm}
\begin{algorithm}[!t]
	\begin{algorithmic}[1]	
		\Require Learning rate $\eta$; number of episodes per iteration $M$
		\State Initialize $\theta^{(0)} = 0$.
		\For{$t=0,1,\ldots,T-1$}
		\State Call Algorithm~\ref{alg:sampler_est} $M$ times with $\pi^{(t)}$ to obtain a dataset that consist of $s_i,a_i\sim d^{(t)}_\nu$ and $\widehat{Q}^{(t)}(s_i,a_i)$, $i\in [M]$.
		\State Solve the linear regression problem 
		\[w^{(t)} = \argmin_{ \|w\|_2\leq W} \sum_{i=1}^M \left(\widehat{Q}^{(t)}(s_i,a_i)-w^\top \nabla_\theta \phi(s_i,a_i)\right)^2\]  
		\State Update $\theta^{(t+1)} = \theta^{(t)} + \eta w^{(t)}$.
		\EndFor
	\end{algorithmic}
	\caption{Natural Policy Gradient (NPG)}
	\label{alg:q_npg_sample}
\end{algorithm}
\begin{algorithm}[!t]
	\caption{Robust Linear Regression via \texttt{SEVER}}
	\label{alg:sever}
	\begin{algorithmic}
		\State {\bf{Input:}} Dataset $\{(x_i,y_i)\}_{i=1:M}$, a standard linear regression solver $\mathcal{L}$, and parameter $\sigma' \in \R_+$.
		\State Initialize $S \gets \{1,\ldots,M\}$, $f_i(w) = \|y_i-w^\top x_i\|^2$.
		\Repeat
		\State ${w} \gets \mathcal{L}(\{(x_i,y_i)\}_{i\in S})$. $\triangleright$ Run learner on $S$.
		\State Let $\widehat{\nabla} = \frac{1}{|S|} \sum_{i\in S} \nabla f_i(w)$.
		\State Let $G = [\nabla f_i({w}) - \widehat{\nabla}]_{i \in S}$ be the $|S| \times d$ matrix of centered gradients.
		\State Let $v$ be the top right singular vector of $G$.
		\State Compute the vector $\tau$ of \emph{outlier scores} defined via
		$\tau_i = \left((\nabla f_i({w}) - \widehat{\nabla}) \cdot v\right)^2$.
		\State $S' \gets S$
	
		\If{$\frac{1}{|S|}\sum_{i\in S} \tau_i \leq c_0 \cdot \sigma'^2$, for some constant $c_0>1$}
		\State $S = S'$ $\triangleright$ We only filter out points if the variance is larger than an appropriately chosen threshold.
		\Else
		\State Draw $T$ from Uniform$[0,\max_i \tau_i]$.
		\State  $S=\{i \in S: \tau_i < T \}$.
		\EndIf
		\Until{$S = S'$.}
		\State Return $w$.
	\end{algorithmic}
\end{algorithm}

\begin{figure*}[th!]
	\begin{subfigure}{0.33\textwidth}
		\centering
		\includegraphics[width=.9\columnwidth]{figures/Swimmer-v3_optimal_reward_plot.pdf}
		\caption{Swimmer-v3}
		\label{fig:Swimmer}
	\end{subfigure}
	\begin{subfigure}{0.33\textwidth}
		\centering
		\includegraphics[width=.9\columnwidth]{figures/Hopper-v3_optimal_reward_plot.pdf}
		\caption{Hopper-v3}
		\label{fig:Hopper}
	\end{subfigure}
	\begin{subfigure}{0.33\textwidth}
		\centering
		\includegraphics[width=.9\columnwidth]{figures/Walker2d-v3_optimal_reward_plot.pdf}
		\caption{Walker2d-v3}
		\label{fig:Walker2d}
	\end{subfigure}
	\begin{subfigure}{0.33\textwidth}
		\centering
		\includegraphics[width=.9\columnwidth]{figures/HalfCheetah-v3_optimal_reward_plot.pdf}
		\caption{HalfCheetah-v3}
		\label{fig:HalfCheetah}
	\end{subfigure}
	\begin{subfigure}{0.33\textwidth}
		\centering
		\includegraphics[width=.9\columnwidth]{figures/Ant-v3_optimal_reward_plot.pdf}
		\caption{Ant-v3}
		\label{fig:Ant}
	\end{subfigure}
	\begin{subfigure}{0.33\textwidth}
		\centering
		\includegraphics[width=.9\columnwidth]{figures/Humanoid-v3_optimal_reward_plot.pdf}
		\caption{Humanoid-v3}
		\label{fig:Humanoid}
	\end{subfigure}
	\caption{Experiment Results on the 6 MuJoTo benchmarks.}
	\label{fig:exp_result}
\end{figure*}



Our second result is the Filtered Policy Gradient (FPG) algorithm, a robust variant of the NPG algorithm \cite{kakade2001natural, agarwal2019optimality} that can be robust against arbitrary and \emph{potentially unbounded} data corruption. Specifically, FPG replace the standard linear regression solver in NPG with a statistically robust alternative. In this work, we use the \texttt{SEVER} algorithm \cite{diakonikolas2019sever}. In practice, one can substitute it with any computationally efficient robust linear regression solver. We show that FPG can find an $O(\epsilon^{1/4})$-optimal policy under $\epsilon$-contamination with a polynomial number of samples.
\begin{theorem}\label{thm:fpg}
	Under assumptions \ref{ass:linearMDP} and \ref{assum:conditioning}, given a desired optimality gap $\alpha$, there exists a set of hyperparameters agnostic to the contamination level $\epsilon$, such that 
	Algorithm \ref{alg:q_npg_sample}, using Algorithm \ref{alg:sever} as the linear regression solver, guarantees with a  $poly(1/\alpha, 1/(1-\gamma), |\A|,W,\sigma,\kappa)$ sample complexity that under $\epsilon$-contamination, we have
	\begin{align}
		\EE&\left[V^{*}(\mu_0) - V^{\hat\pi}(\mu_0)\right]\\
		&\qquad\leq
		\tilde O\left(\max\left[\alpha, \sqrt{ \frac{|\Acal| \kappa \left(W^2+\sigma W\right)}{(1-\gamma)^4}}\epsilon^{1/4}\right]\right).\nonumber
	\end{align}
	where $\hat\pi$ is the uniform mixture of $\pi^{(1)}$ through $\pi^{(T)}$.
\end{theorem}
The proof of Theorem \ref{thm:fpg} relies on a similar result to Lemma \ref{thm:robust_ols}, which shows that if we use Algorithm \ref{alg:sever} as the linear regression subroutine, then $\epsilon_{stat}^{(t)}$ can be bounded by $O(\sqrt{\epsilon^{(t)}})$ when the sample size $M$ is large enough, even under unbounded $\epsilon$-contamination.
\begin{lemma}[Robustness of \texttt{SEVER} under unbounded contamination]\label{thm:sever_result}
	Suppose the adversarial rewards are unbounded, and in a particular iteration $t$, the adversarial contaminate $\epsilon^{(t)}$ fraction of the episodes, then given M episodes, it is guaranteed that if $\epsilon^{(t)}\leq c$, for some absolute constant c, and any constant $\tau\in[0,1]$, we have 
	\begin{align}
		&\EE \left[\EE_{s,a\sim d^{(t)}}\left[\left(Q^{\pi^{(t)}}(s,a)-\phi(s,a)^\top w^{(t)} \right)^2\right]\right]
		\\
		&\leq
		O\left(\left(W^2+\frac{\sigma W}{1-\gamma}\right)\left(\sqrt{\epsilon^{(t)}}+
		f(d,\tau)M^{-\frac{1}{2}} + \tau\right)\right).\nonumber
	\end{align}
	where $f(d,\tau) = \sqrt{d\log d}+\sqrt{\log(1/\tau)}$.
\end{lemma}
In Lemma \ref{thm:sever_result}, $c$ is the break point of \texttt{SEVER} and is an absolute constant that does not depend on the data, and $(1-\tau)$ is the probability that the clean data satisfies a certain stability condition which suffices for robust learning. 

\section{Robust NPG with Exploration via Policy Cover}
The Policy Cover-Policy Gradient (\texttt{PC-PG}) algorithm, defined in Algorithm \ref{alg:pcpg}, is an exploratory policy gradient methods recently developed by \cite{agarwal2020pc}. Intuitively, PC-PG is a spiritually inheritor of the \texttt{RMax} algorithm \cite{brafman2002r}, and encourages exploration by adding reward bonuses in directions of the feature space that past polices (stored in the policy cover) haven't visited sufficiently.
Similar to the NPG algorithm, we show that \texttt{PC-PG} enjoys a (weaker) natural robustness against bounded data corruption. This gives us the following robustness guarantee:
\begin{algorithm}[!t]
	\begin{algorithmic}[1]
		\State \hspace*{-0.1cm}\textbf{Input}: iterations $N$, threshold $\beta$, regularizer $\lambda$
		\State \hspace*{-0.1cm}Initialize $\pi^0(a|s)$ to be uniform.
		\For{episode $n = 0, \dots N-1$}
		
		\State Define the policy cover's state-action distribution $\rho^n_{\text{cov}}$ as
		\begin{equation*}
			\rho_{\text{cov}}^n(s,a) = \sum_{i=0}^{n} d^i(s,a)/(n+1)
			\label{eq:cover_def}
		\end{equation*}
		\State  Sample $\{s_i,a_i\}_{i=1}^K \sim \rho_{\text{cov}}^n(s,a)$ and estimate the covariance of $\pi^n$ as
		\begin{equation*}
			\widehat{\Sigma}^n = (n+1)\left(\sum_{i=1}^K \phi(s_i,a_i)\phi(s_i,a_i)^{\top}/K\right)+\lambda I
		\end{equation*}\label{line:feature_cov}
		\State Set the exploration bonus $b^n$ to reward infrequently visited state-action under $\rho^n_{\text{cov}}$ \label{line:bonus}
		
		\begin{equation*}
			b^n(s,a) = \frac{\one\{\sa~:~ \phi\sa^\top (\widehat{\Sigma}_{\text{cov}}^n)^{-1}\phi\sa \geq \beta\}}{1-\gamma}.
		
		\end{equation*}
		\State Update $\pi^{n+1} = \textrm{Robust-NPG-Update}(\rho^n_{\text{cov}}, b^n)$ [Alg. \ref{alg:npg2} in the appendix, similar to Alg. \ref{alg:q_npg_sample}].
		\EndFor
		\State \Return $\hat\pi \defeq \text{Uniform}\{\pi^0,...,\pi^{N-1}\}$.
	\end{algorithmic}
	\caption{Robust Policy Cover-Policy Gradient (PC-PG)}
	\label{alg:pcpg}
\end{algorithm}

\begin{theorem}[Best hyperparameters, assuming known $\epsilon$]\label{thm:pcpg}
	There exists a set of hyperparameters, such that Algorithm \ref{alg:pcpg} guarantees with probability at least $1-\delta$
	\begin{eqnarray}
	\EE\left[V^{*}(\mu_0) - V^{\hat\pi}(\mu_0)\right]\leq
		\tilde O\left(
		d^{2}\epsilon^{1/7}
		\right)
	\end{eqnarray}
	with $\poly\left(d,W,\sigma,\kappa, |\A|,1/(1-\gamma),1/\alpha\right)$ number of episodes.
\end{theorem}

\begin{remark}[The scaling with dimension $d$]Compared to the guarantee of vanilla NPG, \texttt{PC-PG} alleviate the requirement of a good initial distribution with small relative conditional number. However, this process introduce a dependency on $d$. In particular, the gap in Theorem \ref{thm:pcpg} is on the order of 
	$\tilde O\left(d^{2}\epsilon^{1/7}\right)$
	.
	This implies that for any fixed $\epsilon$, the bound becomes vacuous for high dimensional problems where $d\geq \Omega(\epsilon^{-2/3})$. Intuitively, the dependency on $d$ is introduced because \texttt{PC-PG} is trying to find a initial state-action distribution with good coverage, i.e. a distribution whose covariance matrix has a lower-bounded smallest eigenvalue. Under the assumption that $\|\phi(s,a)\|_2\leq 1$, such a distribution will have a covariance matrix whose eigenvalues are all on the order of $O(1/d)$. and so the value of $\kappa$ will be on the order of $O(d)$, which by Theorem \ref{thm:fpg} will similarly introduce a $d$ dependency. We expect that for a robust RL algorithm to avoid the $d$ dependency, it must gradually find a state-action distribution approaching $d^*$. How to design such an algorithm is left as an open problem. 
\end{remark}

\section{Experiments}
In the theoretical analysis, we rely on the assumption of linear Q function, finite action space and exploratory initial state distribution to prove the robustness guarantees for NPG and FPG. In this section, we present a practical implementation of \texttt{FPG}, based on the \textit{Trusted Region Policy Optimization} (\texttt{TRPO}) algorithm \cite{schulman2015trust}, in which the conjugate gradient step (equivalent to the linear regression step in Alg. \ref{alg:q_npg_sample}) is robustified with \texttt{SEVER}. The pseudo-code and implementation details are discussed in appendix \ref{sec:code}\footnote{A Pytorch Implementation of \texttt{FPG-TRPO} can be found at \url{https://github.com/zhangxz1123/FilteredPolicyGradient}}. In this section, we demonstrate its empirical performance on the MuJoCo benchmarks \cite{todorov2012mujoco}, a set of high-dimensional continuous control domains where both assumptions no longer holds, and show that \texttt{FPG} can still consistently performs near-optimally with and without attack.
\begin{figure*}[th!]
	\centering
	\begin{subfigure}{0.19\textwidth}
		\centering
		\includegraphics[width=0.8\columnwidth]{figures/frame1}
	\end{subfigure}
	\begin{subfigure}{0.19\textwidth}
		\centering
		\includegraphics[width=0.8\columnwidth]{figures/frame2}
	\end{subfigure}
	\begin{subfigure}{0.19\textwidth}
		\centering
		\includegraphics[width=0.8\columnwidth]{figures/frame3}
	\end{subfigure}
	\begin{subfigure}{0.19\textwidth}
		\centering
		\includegraphics[width=0.8\columnwidth]{figures/frame4}
	\end{subfigure}
	\begin{subfigure}{0.19\textwidth}
		\centering
		\includegraphics[width=0.8\columnwidth]{figures/frame5}
	\end{subfigure}
	\\
	\begin{subfigure}{0.19\textwidth}
		\centering
		\includegraphics[width=0.8\columnwidth]{figures/fframe2}
	\end{subfigure}
	\begin{subfigure}{0.19\textwidth}
		\centering
		\includegraphics[width=0.8\columnwidth]{figures/fframe3}
	\end{subfigure}
	\begin{subfigure}{0.19\textwidth}
		\centering
		\includegraphics[width=0.8\columnwidth]{figures/fframe4}
	\end{subfigure}
	\begin{subfigure}{0.19\textwidth}
		\centering
		\includegraphics[width=0.8\columnwidth]{figures/fframe5}
	\end{subfigure}
	\begin{subfigure}{0.19\textwidth}
		\centering
		\includegraphics[width=0.8\columnwidth]{figures/fframe6}
	\end{subfigure}
	\caption{Consecutive Frames of Half-Cheetah trained with TRPO (top row) and FPG (bottom row) respectively under $\delta=100$ attack. The dashed red line serves as a stationary reference object. TRPO was fooled to learn a ''running backward'' policy, contrasted with the normal ''running forward'' policy learned by FPG.}
	\label{fig:cheetah}
\end{figure*}
\begin{figure*}[h!]
	\begin{subfigure}{0.305\textwidth}
		\centering
		\includegraphics[width=1\columnwidth]{figures/Humanoid-v3_TRPO_reward_plot}
		\caption{TRPO Rewards}
		\label{fig:TRPO_humanoid}
	\end{subfigure}
	\begin{subfigure}{0.305\textwidth}
		\centering
		\includegraphics[width=1\columnwidth]{figures/Humanoid-v3_FPG_reward_plot}
		\caption{FPG Rewards}
		\label{fig:FPG_humanoid}
	\end{subfigure}
	\begin{subfigure}{0.39\textwidth}
		\centering
		\includegraphics[width=1\columnwidth]{figures/Humanoid-v3_FPG_detection_plot}
		\caption{FPG Detection Ratio}
		\label{fig:FPG_detection_ratio}
	\end{subfigure}
	\caption{Detailed Results on Humanoid-v3.}
	\label{fig:humanoid_result}
\end{figure*}

\paragraph{Attack mechanism:} While designing and calculating the \textit{optimal} attack strategy against a deep RL algorithm is still a challenging problem and active area of research \cite{ma2019policy,zhang2020adaptive}, here we describe the poisoning strategy used in our empirical evaluation, which, despite being simple, can fool non-robust RL algorithms with ease. Conceptually, policy gradient methods can be viewed as a stochastic gradient ascent method, where each iteration can be simplified as:
\begin{eqnarray}
	\theta^{(t+1)} = \theta^{(t)} + g^{(t)}
\end{eqnarray}
where $g^{(t)}$ is a gradient step that ideally points in the direction of fastest policy improvement. Assuming that $g^{(t)}$ is a good estimate of the gradient direction, then a simple attack strategy is to try to perturb $ g^{(t)}$ to point in the $-g^{(t)}$ direction, in which case the policy, rather than improving, will deteriorate as learning proceed. A straightforward way to achieve this is to flip the rewards and multiply them by a big constant $\delta$ in the adversarial episodes. In the linear regression subproblem of Alg. \ref{alg:q_npg_sample}, this would result in a set of $(x,y)$ pairs whose $y$ becomes $-\delta y$. This in expectation will make the best linear regressor $w$ point to the opposite direction, which is precisely what we want. 

This attack strategy is therefore parameterized by a single parameter $\delta$, which guides the magnitude of the attack, and is \textbf{adaptively tuned} against each learning algorithm in the experiments: Throughout the experiment, we set the contamination level $\epsilon=0.01$, and tune $\delta$ among the values of $[1,2,4,8,16,32,64]$ to find the most effective magnitude against each learning algorithm. All experiments are repeated with 3 random seeds and the mean and standard deviations are plotted in the figures.

\paragraph{Results:} The experiment results are shown in Figure \ref{fig:exp_result}. Consistent patterns can be observed across all environments: vanilla \texttt{TRPO} performs well without attack but fails completely under the adaptive attack (which choose $\delta=64$ in all environments). \texttt{FPG}, on the other hand, matches the performance of vanilla \texttt{TRPO} with or without attack. Figure \ref{fig:cheetah} showcase two half-cheetah control policies learned by \texttt{TRPO} and \texttt{FPG} under attack with $\delta=100$. Interestingly, due to the large negative adversarial rewards, TRPO actually learns the ``running backward'' policy, showing that our attack strategy indeed achieves what it's designed for. In contrast, \texttt{FPG} is still able to learn the ''running forward'' policy despite the attack.

Figure \ref{fig:humanoid_result} shows the detailed performances of \texttt{TRPO} and \texttt{FPG} across different $\delta$'s on the hardest \textit{Humanoid} environment. 
One can observe that \texttt{TRPO} actually learns robustly under attacks of small magnitude ($\delta=1,2,4$) and achieves similar performances to itself in clean environments, verifying our theoretical result in Theorem \ref{thm:npg_natural}.
In contrast, \texttt{FPG} remains robust across all values of $\delta$'s. Figure \ref{fig:FPG_detection_ratio} shows the proportion of adversary data detected and removed by \texttt{FPG}'s filtering subroutine throughout the learning process. One can observe that as the attack norm $\delta$ increases, the filtering algorithm also does a better job detecting the adversarial data and thus protect the algorithm from getting inaccurate gradient estimates. Similar patterns can be observed in all the other environments, and we defer the additional figures to the appendix.

\section{Discussions}
To summarize, in this work we present a robust policy gradient algorithm \texttt{FPG}, and show theoretically and empirically that it can learn in the presence of strong data corruption. Despite our results, many open questions remain unclear and are interesting directions to pursue further:
\begin{enumerate}
	\item \texttt{FPG} does not handle exploration and relies on an exploratory initial distribution. Can we design algorithms that achieve the same \textit{dimension-free} robustness guarantee without such assumptions?
	\item Our $O(\epsilon^{1/4})$ upper-bound and $O(\epsilon)$ lower-bound are not tight. Information theoretically, what is the best robustness guarantee one can achieve under $\epsilon$-contamination?
	\item The \texttt{SEVER} algorithm requires computing the top eigenvalue of an $n\times d$ matrix, which is memory and time consuming when using large neural networks (large $d$). More computationally efficient robust learning method will be extremely valuable to make FPG truly scale.
	\item In the experiment, we focus on TRPO as the closest variant of NPG. Can other policy gradient algorithm, such as PPO and SAC, be robustified in similar fashions and achieve strong empirical performance?
\end{enumerate}
We believe that answering these questions will be important steps towards more robust reinforcement learning. 

\section{Acknowledgements}
We would like to thank Ankit Pensia and Ilias Diakonikolas for valuable discussions on SEVER and other robust statistics techniques. Xiaojin Zhu acknowledges NSF grants 1545481, 1704117, 1836978, 2041428, 2023239 and MADLab AF CoE FA9550-18-1-0166. Xuezhou Zhang is supported in part by NSF Award DMS-2023239.



