# Combining Pessimism with Optimism for Robust and Efficient
Model-Based Deep Reinforcement Learning

Sebastian Curi  Ilija Bogunovic  Andreas Krause

###### Abstract

In real-world tasks, reinforcement learning (RL) agents frequently encounter
situations that are not present during training time. To ensure reliable
performance, the RL agents need to exhibit robustness against worst-case
situations. The robust RL framework addresses this challenge via a worst-case
optimization between an agent and an adversary. Previous robust RL algorithms
are either sample inefficient, lack robustness guarantees, or do not scale to
large problems. We propose the _Robust Hallucinated Upper-Confidence_ RL (RH-
UCRL) algorithm to provably solve this problem while attaining near-optimal
sample complexity guarantees. RH-UCRL is a model-based reinforcement learning
(MBRL) algorithm that effectively distinguishes between epistemic and
aleatoric uncertainty, and efficiently explores both the agent and adversary
decision spaces during policy learning. We scale RH-UCRL to complex tasks via
neural networks ensemble models as well as neural network policies.
Experimentally, we demonstrate that RH-UCRL outperforms other robust deep RL
algorithms in a variety of adversarial environments.

##  1 Introduction

A central challenge when deploying Reinforcement Learning (RL) agents in real
environments is their robustness (Dulac-Arnold et al., 2019). As a motivating
example, consider designing a braking system on an autonomous car. As this is
a highly complex task, we want to _learn_ a policy that performs this
maneuver. Even if various real-world conditions can be simulated during the
training time, it is infeasible to consider _all_ possible ones such as road
conditions, brightness, tire pressure, laden weight, or actuator wear, as
these can all vary over time in potentially unpredictable ways. The main goal
is then to learn a policy that _provably_ brakes in a _robust_ fashion so
that, even if faced with new conditions, it performs reliably. Borrowing from
the robust control perspective (e.g, as considered in $\mathcal{H}_{\infty}$
control Başar & Bernhard (2008)), we model robustness with an adversary that
is allowed to perform the worst-case disturbance for the given policy.

While there are theoretical approaches for robust RL that offer sample
complexity guarantees (see Section 2), the existing algorithms are highly
impractical. On the other hand, there are empirically motivated heuristic
approaches that lack provable robustness. We bridge this gap by proposing an
algorithm that simultaneously enjoys rigorous theoretical guarantees, yet can
be applied to complex tasks.

We develop the _Robust Hallucinated Upper-Confidence Reinforcement Learning_
(RH-UCRL) algorithm for obtaining robust RL policies. It relies on a
probabilistic model that can distinguish between epistemic uncertainty (that
arises from the lack of data) and aleatoric uncertainty (stochastic noise)
(Der Kiureghian & Ditlevsen, 2009). A key algorithmic principle behind RH-UCRL
is _hallucination_ : In particular, the agent hallucinates an additional
control input to maximize an optimistic estimate of the robust performance
whereas the adversary hallucinates an additional control input to minimize a
pessimistic estimate of the robust performance. The amount of “hallucination”
is limited by the epistemic uncertainty of the model and it decreases as the
learning algorithm collects more data. In a number of experiments, we show
that our algorithm exhibits robust performance and outperforms previous
approaches on various popular RL benchmarks. In Figure 1, we demonstrate how
RH-UCRL outperforms baselines in a pendulum swing-up control task. In
particular, our main observations are: (i) Robust baselines specifically
designed for different settings do not explore sufficiently and fail to find a
swing-up maneuver; (ii) Non-robust algorithm finds the swing-up strategy, but
as adversarial power increases its performance significantly deteriorates,
whereas RH-UCRL exhibits higher robustness to worst-case perturbations.

Figure 1:  Performance of RH-UCRL (this work), H-UCRL (Curi et al., 2020a),
and a baseline with no exploration in adversarial-, action-, and parameter-
robust settings on a pendulum swing-up task. The baseline never learns a
successful swing-up strategy due to insufficient exploration. RH-UCRL and
H-UCRL learn a swing-up strategy but RH-UCRL outperforms H-UCRL as the
perturbation increases.

Main contributions. We design RH-UCRL, the first practical _provably_ robust
RL algorithm that is: (i) _sample-efficient_ , (ii) compatible with _deep
models_ , and (iii) simulator-free as it addresses exploration on a real
system. We establish rigorous general sample-complexity and regret guarantees
for our algorithm, and we specialize them to Gaussian Process models, hence
obtaining sublinear robust regret guarantees. While previous robust RL works
have focused on different individual settings, we gather and summarize them
all for the first time, and show particular instantiations of our algorithm in
each of them: (i) Adversarial-robust RL, (ii) Action-robust RL, and (iii)
Parameter-robust RL. Finally, we provide experiments that include different
environments and settings, and we empirically demonstrate that RH-UCRL
outperforms or successfully competes with the state-of-the-art deep robust RL
algorithms and other baselines.

##  2 Related Work

Robust RL. Robust Reinforcement Learning (Iyengar, 2005; Nilim & El Ghaoui,
2005; Wiesemann et al., 2013) typically uses the Zero-Sum Markov Games
formalism introduced by Littman (1994); Littman & Szepesvári (1996). From a
control engineering perspective, this is known as $\mathcal{H}_{\infty}$
control (Başar & Bernhard, 2008), and Bemporad et al. (2003) solve this
problem for known linear systems where the optimal robust policy is an affine
function of the state. For Markov Games with unknown systems, Lagoudakis &
Parr (2002) introduce approximate value iteration whereas Tamar et al. (2014)
and Perolat et al. (2015) present an approximate policy iteration scheme.
Although these works present error propagation schemes restricted to the
linear setting, they do not address the problem of exploration explicitly, and
instead assume access to a sampling distribution that has sufficient state
coverage. Zhang et al. (2020) propose a model-based algorithm for finding
robust policies assuming access to a simulator that is able to sample at
arbitrary state-action pairs. Finally, Bai & Jin (2020) recently introduce an
algorithm that provably and efficiently outputs a policy, but it is limited to
the tabular setting. Instead, our approach does not require a generative model
and considers the full exploration problem in a finite horizon scenario.
Furthermore, our algorithm does not require tabular nor linear function
approximation and it is compatible with deep neural networks dynamical models.

Minimax Optimization Algorithms. Pinto et al. (2017) propose to solve the
minimax optimization via a stochastic gradient descent approach for both
players for adversarial-robust RL algorithms. Tessler et al. (2019) introduce
action-robust RL and policy and value iteration algorithms to solve these
problems. Rajeswaran et al. (2017) introduce the EPOpt to solve parameter-
robust problems. Finally, Kamalaruban et al. (2020) propose to use a
Stochastic-Gradient Langevin Dynamics algorithm to solve such problems via
sampling instead of optimization. These algorithms are generally sample-
inefficient as they do not explicitly explore but, given a model, they could
be used to optimize a policy.

Provable Model-Based RL. Model-Based RL has better empirical sample-efficiency
than model-free variants (Deisenroth & Rasmussen, 2011; Chua et al., 2018).
Furthermore, the celebrated UCRL algorithm by Auer et al. (2009) has provable
sample-efficiency guarantees, albeit being intractable for non-tabular
environments. Recently, Curi et al. (2020a) instantiate the UCRL algorithm in
continuous control problems using hallucinated control to explore. We build
upon their H-UCRL algorithm and strictly generalize it to the robust RL
setting. Our robust policy search strategy is inspired by the work in the
related bandit setting with Gaussian Processes, where Stable-OPT (Bogunovic et
al., 2018) combines pessimism with optimism to similarly generalize the non-
robust GP-UCB (Srinivas et al., 2010) algorithm and provably discover robust
designs.

##  3 Problem Statement

We consider a stochastic environment with states
$\mathbf{s}\in\mathcal{S}\subseteq\mathbb{R}^{p}$, agent actions
$\mathbf{a}\in\mathcal{A}\subset\mathbb{R}^{q}$, adversary actions
$\bar{\mathbf{a}}\in\bar{\mathcal{A}}\subset\mathbb{R}^{\bar{q}}$, and i.i.d.
additive transition noise vector $\bm{\omega}_{h}\in\mathbb{R}^{p}$. Both
action sets are assumed to be compact, and the dynamics are given by:

$\mathbf{s}_{h+1}=f(\mathbf{s}_{h},\mathbf{a}_{h},\bar{\mathbf{a}}_{h})+\bm{\omega}_{h}$
(1)

with
$f\colon\mathcal{S}\times\mathcal{A}\times\bar{\mathcal{A}}\to\mathcal{S}$. We
assume the true dynamics $f$ are _unknown_ and consider the episodic setting
over a finite time horizon $H$. After every episode (i.e., every $H$ time
steps), the system is reset to a known state $\mathbf{s}_{0}$. In this work,
we make the following assumptions regarding the stochastic environment and
unknown dynamics:

######  Assumption 1.

The dynamics $f$ in Eq. 1 are $L_{f}$-Lipschitz continuous and, for all
$h\in\\{0,\dots,H-1\\}$, the individual entries of the noise vector
$\bm{\omega}_{h}$ are i.i.d. $\sigma$-sub-Gaussian.

At every time-step, the system returns a deterministic reward
$r(\mathbf{s}_{h},\mathbf{a}_{h},\bar{\mathbf{a}}_{h})$, where
$r:\mathcal{S}\times\mathcal{A}\times\bar{\mathcal{A}}\to\mathbb{R}$ is
assumed to be known to the agent. We consider time-homogeneous agent policies
$\pi\in\Pi$, $\pi\colon\mathcal{S}\to\mathcal{A}$, that select actions
according to $\mathbf{a}_{h}=\pi(\mathbf{s}_{h})$. Similarly, we consider
adversary policies $\pi\in\bar{\Pi}$ on the common state space, i.e.,
$\bar{\pi}\colon\mathcal{S}\to\bar{\mathcal{A}}$, that select actions as
$\bar{\mathbf{a}}_{h}=\bar{\pi}(\mathbf{s}_{h})$. For the sake of simplicity,
we omit straightforward extensions such as initial-state distributions,
unknown reward functions, or time-indexed policies that can be adressed using
standard techniques (Chowdhury & Gopalan, 2019). For now, we leave both $\Pi$
and $\bar{\Pi}$ unspecified, but in Section 5, we parameterize them via neural
networks.

The performance of a pair of policies $(\pi,\bar{\pi})$ on a given dynamical
system $\tilde{f}$ is the episodic expected sum of returns:

$\displaystyle J(\tilde{f},\pi,\bar{\pi})$
$\displaystyle\coloneqq\mathbb{E}_{\tau_{\tilde{f},\pi,\bar{\pi}}}\mathopen{}\left[\sum_{h=0}^{H}r(\mathbf{s}_{h},\mathbf{a}_{h},\bar{\mathbf{a}}_{h})\,\bigg{|}\,\mathbf{s}_{0}\right]\mathclose{},$
(2) $\displaystyle\text{s.t. }\;\mathbf{s}_{h+1}$
$\displaystyle=\tilde{f}(\mathbf{s}_{h},\mathbf{a}_{h},\bar{\mathbf{a}}_{h})+\bm{\omega}_{h},$

where
$\tau_{\tilde{f},\pi,\bar{\pi}}=\left\\{(\mathbf{s}_{h-1},\mathbf{a}_{h-1},\bar{\mathbf{a}}_{h-1}),\mathbf{s}_{h}\right\\}_{h=0}^{H}$
is a random trajectory induced by the stochastic noise $\bm{\omega}$, the
dynamics $\tilde{f}$, and the policies $\pi$ and $\bar{\pi}$.

We use $\pi^{\star}$ to denote the optimal deterministic _robust_ policy from
set $\Pi$ in case of true dynamics $f$, i.e.,

$\pi^{\star}\in\arg\max_{\pi\in\Pi}\min_{\bar{\pi}\in\bar{\Pi}}J(f,\pi,\bar{\pi}).$
(3)

Even when the true system dynamics are known, finding a robust policy is
generally a challenging task for arbitrary policy sets, reward and transition
functions. In the rest, we make an assumption that Eq. 3 can be solved for a
given dynamics, and in Section 4.3, we propose a concrete problem
instantiation and algorithmic solution.

Learning protocol. We consider the episodic setting in which, at every episode
$t$, the learning algorithm selects both the agent’s $\pi_{t}$ and a
fictitious adversary’s $\bar{\pi}_{t}$ policies. The pair of policies
($\pi_{t}$, $\bar{\pi}_{t}$) is then deployed on the true system $f$, and a
single realization of the trajectory $\tau_{f,\pi_{t},\bar{\pi}_{t}}$ is
observed and used to update the underlying statistical model. We summarize the
general learning protocol in Algorithm 1. In the braking system example, this
learning protocol implies that during training we are allowed to execute
braking maneuvers as well as possible adversarial policies, e.g., changing the
braking surface. The execution of both policies during training is crucial to
guarantee robust performance: The learner can actively look for the _worst-
case_ adversarial policies that it might encounter during deployment and learn
what to do when faced upon them.

Algorithm 1 Robust Model-based Reinforcement Learning

1: Require: Calibrated dynamical model, reward function
$r(\mathbf{s}_{h},\mathbf{a}_{h},\bar{\mathbf{a}}_{h})$, horizon $H$, initial
state $\mathbf{s}_{0}$

2: for $t=1,2,\dots$ do

3: Select ($\pi_{t}$,$\bar{\pi}_{t}$) using the current dynamical model

4: for $h=1,\dots,H-1$ do

5:
$\mathbf{s}_{h,t}=f(\mathbf{s}_{h-1,t},\pi_{t}(\mathbf{s}_{h-1,t}),\bar{\pi}_{t}(\mathbf{s}_{h-1,t}))+\bm{\omega}_{h,t}$

6: end for

7: Update statistical dynamical model with the $H$ observations
$\left\\{(\mathbf{s}_{h-1,t},\mathbf{a}_{h-1,t},\bar{\mathbf{a}}_{h-1,t}),\mathbf{s}_{h,t}\right\\}_{h=0}^{H}$

8: Reset the system to $\mathbf{s}_{0,t+1}=\mathbf{s}_{0}$

9: end for

Performance metric. For a small fixed $\epsilon>0$, the goal is to output a
robust policy $\pi_{T}$ after $T$ episodes such that:

$\min_{\bar{\pi}\in\bar{\Pi}}J(f,\pi_{T},\bar{\pi})\geq\min_{\bar{\pi}\in\bar{\Pi}}J(f,\pi^{\star},\bar{\pi})-\epsilon,$
(4)

where $\pi^{\star}$ is defined as in Eq. 3. Hence, we consider the task of
near-optimal robust policy identification, but we note that one can also
measure the performance in terms of the robust cumulative regret as discussed
in Section 4.4. Thus, the goal is to output the agent’s policy with near-
optimal robust performance when facing its own _worst-case_ adversary, and the
adversary selects $\bar{\pi}$ _after_ the agent selects $\pi_{T}$. Note that
this is a strong er robustness notion than just considering the worst-case
adversary of the optimal policy, since, by letting
$\bar{\pi}^{*}\in\operatorname*{arg\,min}_{\bar{\pi}\in\bar{\Pi}}J(f,\pi^{\star},\bar{\pi})$,
we have
$J(f,\pi_{T},\bar{\pi}^{*})\geq\min_{\bar{\pi}\in\bar{\Pi}}J(f,\pi_{T},\bar{\pi})$.

Statistical Model. In this work, we take a model-based reinforcement learning
(MBRL) approach. That is, to learn the dynamics and discover a near-optimal
robust policy, we consider algorithms that model and sequentially learn about
$f$ from noisy state observations. The agent makes use of the observed data
(collected within an episode) to simultaneously improve its estimate of the
true dynamics $f$.

We use statistical estimation to probabilistically reason about dynamical
models $\tilde{f}$ that are compatible with the observed data
$\mathcal{D}_{1:t}=\left\\{\tau_{f,\pi_{t^{\prime}},\bar{\pi}_{t^{\prime}}}\right\\}_{t^{\prime}=1}^{t}$.
This can be done, e.g., by frequentist estimation of mean
$\bm{\mu}_{t}(\mathbf{s},\mathbf{a},\bar{\mathbf{a}})$ and confidence
$\bm{\Sigma}^{2}_{t}(\mathbf{s},\mathbf{a},\bar{\mathbf{a}})$ estimators, or
by taking a Bayesian perspective and considering the posterior distribution
$p(\tilde{f}\,|\,\mathcal{D}_{1:t})$ over dynamical models that leads to
$\bm{\mu}_{t}(\mathbf{s},\mathbf{a},\bar{\mathbf{a}})=\mathbb{E}_{\tilde{f}\sim
p(\tilde{f}\,|\,\mathcal{D}_{1:t})}[\tilde{f}(\mathbf{s},\mathbf{a},\bar{\mathbf{a}})]$
and
$\bm{\Sigma}_{t}^{2}(\mathbf{s},\mathbf{a},\bar{\mathbf{a}})=\mathrm{Var}[\tilde{f}(\mathbf{s},\mathbf{a},\bar{\mathbf{a}})]$.
In any case, we require the model to be calibrated:

######  Assumption 2 (Calibrated model).

The statistical model is calibrated w.r.t. $f$ in Eq. 1, so that with
$\bm{\sigma}_{t}(\cdot)=\mathrm{diag}(\bm{\Sigma}_{t}(\cdot))$ and a non-
decreasing sequence of parameters $\\{\beta_{t}\\}_{t\geq
1}\in\mathbb{R}_{>0}$, each depending on $\delta\in(0,1)$, it holds jointly
for all $t\geq 1$ and
$\mathbf{s},\mathbf{a},\bar{\mathbf{a}}\in\mathcal{S}\times\mathcal{A}\times\bar{\mathcal{A}}$
that
$|f(\mathbf{s},\mathbf{a},\bar{\mathbf{a}})-\bm{\mu}_{t-1}(\mathbf{s},\mathbf{a},\bar{\mathbf{a}})|\leq\beta_{t}\bm{\sigma}_{t-1}(\mathbf{s},\mathbf{a},\bar{\mathbf{a}})$
element-wise, with probability at least $1-\delta$.

This assumption is important for exploration: if the model is not calibrated,
then using the epistemic uncertainty of such a model will not _provably_ guide
exploration. For dynamics with finite norm in a known RKHS space, Assumption 2
is satisfied (Srinivas et al., 2010; Chowdhury & Gopalan, 2017). In case of
neural network models, we can recalibrate one-step ahead predictions (Malik et
al., 2019).

##  4 The Robust H-UCRL Algorithm (RH-UCRL)

We now develop our RH-UCRL algorithm that can be used in Algorithm 1 (at Line
3), for selecting policies $\pi_{t}$ and $\bar{\pi}_{t}$. RH-UCRL takes the
sequence of confidence parameters $\\{\beta_{t}\\}_{t\geq 1}$ from Assumption
2 as input. The main idea is to use our probabilistic model of $f$ to
optimistically select $\pi_{t}$ and pessimistically select $\bar{\pi}_{t}$
w.r.t. all plausible dynamics.

###  4.1 Optimistic and Pessimistic Policy Evaluation

For any two policies $\pi$ and $\bar{\pi}$, we provide the (o)ptimistic and
(p)essimistic estimate of $J(f,\pi,\bar{\pi})$ at time $t$, and we denote them
with $J_{t}^{(o)}(\pi,\bar{\pi})$ and $J_{t}^{(p)}(\pi,\bar{\pi})$,
respectively. Hereby, the optimistic estimate is given by:

$\displaystyle J_{t}^{(o)}(\pi,\bar{\pi})$
$\displaystyle\coloneqq\max_{{\eta^{(o)}}}J(f^{(o)},\pi,\bar{\pi}),$ (5a) s.t.
$\displaystyle{f^{(o)}}(\mathbf{s},\mathbf{a},\bar{\mathbf{a}})=\mu_{t-1}\big{(}\mathbf{s},\mathbf{a},\bar{\mathbf{a}})$
$\displaystyle\quad+\beta_{t}{\eta^{(o)}}(\mathbf{s},\mathbf{a},\bar{\mathbf{a}})\Sigma_{t-1}^{1/2}(\mathbf{s},\mathbf{a},\bar{\mathbf{a}}).$
(5b)

Similarly, the pessimistic estimate is given by:

$\displaystyle J_{t}^{(p)}(\pi,\bar{\pi})$ $\displaystyle\
\coloneqq\min_{{\eta^{(p)}}}J(f^{(p)},\pi,\bar{\pi})$ (6a) s.t.
$\displaystyle{f^{(p)}}(\mathbf{s},\mathbf{a},\bar{\mathbf{a}})=\mu_{t-1}\big{(}\mathbf{s},\mathbf{a},\bar{\mathbf{a}})$
$\displaystyle\quad+\beta_{t}{\eta^{(p)}}(\mathbf{s},\mathbf{a},\bar{\mathbf{a}})\Sigma_{t-1}^{1/2}(\mathbf{s},\mathbf{a},\bar{\mathbf{a}}).$
(6b)

We note that $J_{t}^{(o)}$ and $J_{t}^{(p)}$ represent upper and lower bounds
on the performance of the policies $\pi$, $\bar{\pi}$ in case of the true
dynamics $f$. These estimates are computed by finding the most optimistic
(pessimistic) dynamics compatible with the data. Note that the
optimistic/pessimistic outcome is selected via decision variables
${\eta^{(o)}}/{\eta^{(p)}}:\mathcal{S}\times\mathcal{A}\times\bar{\mathcal{A}}\to[-1,1]^{p}$,
which are functions of the state as well as actions of both players. These
select among all plausible outcomes of the dynamics bounded within the
epistemic uncertainty over $f$. When the policies are fixed and clear from
context, with slight abuse of notation we write
$\eta(\mathbf{s},\mathbf{a},\bar{\mathbf{a}})=\eta(\mathbf{s},\pi(\mathbf{s}),\bar{\pi}(\mathbf{s}))=\eta(\mathbf{s})$.
A crucial observation is that both Eqs. 5 and 6 can be viewed as two optimal
control problems, where the decision variables ${\eta^{(o)}}/{\eta^{(p)}}$ are
hallucinated control policies, whose effect is bounded by the model epistemic
uncertainty. We can use optimal control algorithms (Camacho & Alba, 2013) to
maximize/minimize the sum of rewards following the reparameterized dynamics
${f^{(o)}}/{f^{(p)}}$.

###  4.2 The RH-UCRL lgorithm

Given both the pessimistic and optimistic performance estimates from the
previous section, we are now ready to state our algorithm. At each episode
$t$, RH-UCRL selects the agent and adversary policies as follows:

$\displaystyle\pi_{t}$
$\displaystyle\in\operatorname*{arg\,max}_{\pi\in\Pi}\min_{\bar{\pi}\in\bar{\Pi}}J_{t}^{(o)}(\pi,\bar{\pi}),$
(7a) $\displaystyle\bar{\pi}_{t}$
$\displaystyle\in\operatorname*{arg\,min}_{\bar{\pi}\in\bar{\Pi}}J_{t}^{(p)}(\pi_{t},\bar{\pi}).$
(7b)

Thus, RH-UCRL selects the most optimistic robust policy for the agent player
in Eq. 7a. The adversary player picks the most pessimistic policy given the
selected agent policy in Eq. 7b. When the adversarial policy space $\bar{\Pi}$
is a singleton, RH-UCRL reduces to the H-UCRL algorithm.

Finally, after a total of $T$ episodes, the algorithm outputs an agent policy
$\hat{\pi}_{T}$ given by:

$\hat{\pi}_{T}=\pi_{t^{\star}}\;\text{ s.t.
}\;t^{\star}\in\operatorname*{arg\,max}_{t\in\\{1,\ldots,T\\}}J_{t}^{(p)}(\pi_{t},\bar{\pi}_{t}).$
(8)

There is no extra computational cost in identifying the output policy as
$J_{t}^{(p)}(\pi_{t},\bar{\pi}_{t})$ is already computed by the learner in Eq.
7b in every episode $t$. Thus, the algorithm simply returns the encountered
agent policy with maximum pessimistic robust performance.

###  4.3 Practical Implementation

To implement RH-UCRL, we parameterize $\pi$, $\bar{\pi}$, and $\eta$ using
neural network policies and train them using actor-critic algorithms. We
remark that $\bar{\pi}$ in the agent optimization (7a) and $\bar{\pi}$ in the
adversary optimization (7b) are different, as are the pessimistic and
optimistic hallucination policies ${\eta^{(p)}}$ and ${\eta^{(o)}}$. In
particular, we learn a critic via fitted Q-iteration (Perolat et al., 2015;
Antos et al., 2008) and then differentiate through the critic using pathwise
gradients (Mohamed et al., 2019; Silver et al., 2014) using stochastic
gradient ascent for the agent and stochastic gradient descent for the
adversary.

###  4.4 Theoretical Analysis

In this section, we theoretically analyze the performance of the RH-UCRL
algorithm. First, we use the notion of _robust cumulative regret_ 111Similar
notions of robust cumulative regret have been analyzed before in bandit
optimization (see, e.g., Kirschner et al., 2020).

$R_{T}=\sum_{t=1}^{T}\min_{\bar{\pi}\in\bar{\Pi}}J(f,\pi^{\star},\bar{\pi})-\min_{\bar{\pi}\in\bar{\Pi}}J(f,\pi_{t},\bar{\pi}),$

which measures the difference in performance between the optimal robust policy
and the sequence of agent’s policies $\\{\pi_{1},\dots,\pi_{T}\\}$ selected at
every episode in Eq. 7a. Below (see Theorem 1) we establish that RH-UCRL
achieves sublinear regret, i.e., $R_{T}/T\to 0$ for $T\to\infty$. In addition
to the robust regret notion, we also analyze the recommendation rule of RH-
UCRL via Eq. 8, and the number of episodes $T$ required to output a near-
optimal robust policy (see Corollary 1). We start by analyzing a general
robust model-based RL framework, and later on, we demonstrate the utility of
the obtained results by specializing them to the important special case of
Gaussian Process dynamics models. We defer all the proofs from this section to
Appendix B. Before stating our main theoretical results, we introduce some
additional assumptions:

######  Assumption 3 (Lipschitz continuity).

At every episode $t$, the functions $\bm{\sigma}_{t}$, any agent’s and
adversary’s policies $\pi_{t}\in\Pi$, $\bar{\pi}_{t}\in\bar{\Pi}$, and the
reward $r(\cdot,\cdot,\cdot)$ are Lipschitz continuous with respective
constants $L_{\sigma}$, $L_{\pi}$, $L_{\bar{\pi}}$ and $L_{r}$.

The previous assumption is mild and has been used in non-robust model-based
RL, see, e.g., Curi et al. (2020a), where it is noted that neural networks
with Lipschitz-continuous non-linearities (or GPs with Lipschitz continuous
kernels) output Lipschitz-continuous predictions. Furthermore, the policy
classes $\Pi$ and $\bar{\Pi}$, as well as the reward functions, are typically
known and designed in a way that is compatible with the previous assumption.

Both the robust regret and sample complexity rates that we analyze depend on
the difficulty of learning the underlying statistical model. Models that are
easy to learn typically require fewer samples and allow algorithms to make
better decisions sooner. To express the difficulty of learning the imposed
calibrated model class, we use the following model-based complexity measure:

$\Gamma_{T}\coloneqq\max_{\tilde{\mathcal{D}}_{1:T}}\sum_{t=1}^{T}\sum_{(\mathbf{s},\mathbf{a},\bar{\mathbf{a}})\in\tilde{\mathcal{D}}_{t}}\|\bm{\sigma}_{t-1}(\mathbf{s},\mathbf{a},\bar{\mathbf{a}})\|^{2}_{2}$
(9)

where each
$\tilde{\mathcal{D}}_{t}\subset\\{\mathcal{S}\times\mathcal{A}\times\bar{\mathcal{A}}\\}^{H}$.
This quantity has a worst-case flavor as it considers the data (collected
during $T$ episodes by any algorithm) that lead to maximal total predictive
uncertainty of the model. For the special case of RKHS/GP dynamics models, we
show below that this quantity can be effectively bounded, and the bound is
sublinear (in the number of episodes $T$) for most commonly used kernel
functions.

Figure 2:  Worst-case and average return of different algorithms in the
Adversarial-Robust Setting in Mujoco tasks. RH-UCRL outperforms the other
algorithms in terms of worst-case return. The non-robust baseline, H-UCRL, has
good average performance but poor worst-case performance (e.g., Inverted
Pendulum). The deep robust RL baselines have worse sample complexity and often
underperform. Our ablations are also non-robust, since exploration of both
agent and adversary is crucial here to achieve robust performance.

General results. Now, we can state the main result of this section. In the
following theorem, we bound the robust cumulative regret incurred by the
policies from Eq. 7a.

######  Theorem 1.

Under Assumptions 1, 3, 3, 2 and 3, let
$C=(1+L_{f}+2L_{\sigma})(1+L_{\pi}^{2}+L_{\bar{\pi}}^{2})^{1/2}$ and let
$\mathbf{s}_{t,h}\in\mathcal{S}$, $\mathbf{a}_{t,h}\in\mathcal{A}$,
$\bar{\mathbf{a}}_{t,h}\in\bar{\mathcal{A}}$ for all $t,h>0$. Then, for any
fixed $H\geq 1$, with probability at least $1-\delta$, the robust cumulative
regret of RH-UCRL is upper bounded by:

$R_{T}=\mathcal{O}\mathopen{}\left(L_{r}C^{H}\beta_{T}^{H}H^{3/2}\sqrt{T\,\Gamma_{T}}\right)\mathclose{}.$

This regret bound shows that RH-UCRL achieves sublinear robust regret when
$\beta_{T}^{H}\sqrt{\Gamma_{T}}=o(\sqrt{T})$. Below, we show a concrete
example of GP models where this is indeed the case. The obtained bound also
depends on the Lipschitz constants from Assumption 3, as well as the episode
length $H$ that we assume is constant. The dependency of the regret bound on
the problem dimension is hidden in $\Gamma_{T}$, while $\beta_{T}$ depends
also on $\delta$ (see Assumption 2).

Next, we characterize the number of episodes (samples) required by RH-UCRL to
output $\epsilon$-optimal robust policy. Our analysis upper bounds the optimal
robust performance according to the confidence bounds from Assumption 2, but
also addresses the challenge of characterizing the impact of exploring
different adversary policies in Eq. 7b.

######  Corollary 1.

Consider the assumptions and setup of Theorem 1, and suppose that

$\frac{T}{\beta_{T}^{2H}\Gamma_{T}}\geq\frac{16L_{r}^{2}H^{3}C^{2H}}{\epsilon^{2}},$
(10)

for some fixed $\epsilon>0$ and $H\geq 1$. Then, with probability at least
$1-\delta$ after $T$ episodes, RH-UCRL achieves:

$\min_{\bar{\pi}\in\bar{\Pi}}J(f,\hat{\pi}_{T},\bar{\pi})\geq\min_{\bar{\pi}\in\bar{\Pi}}J(f,\pi^{\star},\bar{\pi})-\epsilon,$
(11)

where $\hat{\pi}_{T}$ is the output of RH-UCRL, reported according to Eq. 8,
and $\pi^{\star}$ is the optimal robust policy given in Eq. 3.

Gaussian Process Models. We specialize the regret bound obtained in Theorem 1
to the case of Gaussian Process (GP) models. GPs are popular statistical
models that are frequently used to model unknown dynamics (Deisenroth &
Rasmussen, 2011; Kamthe & Deisenroth, 2018; Curi et al., 2020b). These models
are very expressive due to a versatility of possible kernel functions, and can
naturally differentiate between aleatoric noise and epistemic uncertainty.
Moreover, GPs are known to be provably well-calibrated when the unknown
dynamics $f$ are $B_{f}$-smooth as measured by the GP kernel.

In Appendix C, we recall the GP maximum information gain (MIG) which is a
kernel-dependent quantity (first introduced by Srinivas et al. (2010)), that
is frequently used in various GP optimization works to characterize complexity
of learning a GP model. Sublinear upper bounds for MIG are known (c.f.
Srinivas et al. (2010)) for most popularly used kernels (e.g., linear,
squared-exponential, etc.), as well as for their compositions, e.g., additive
kernels (Krause & Ong, 2011). We recall the known results and use MIG to
express $\beta_{T}$ and upper bound $\Gamma_{T}$ in Theorem 1. For example,
when we use independent GP models with either (i) linear or (ii) squared-
exponential kernels, for every component, we obtain the following _sublinear_
(in $T$) regret bounds
$O(H^{3/2}p\left[(p+q+{\bar{q}})\ln(pTH)\right]^{(H+1)/2}\sqrt{T})$ and
$O(H^{3/2}p\left[\ln(pTH)\right]^{(p+q+{\bar{q}})(H+1)/2}\sqrt{T})$,
respectively.

Finally, we note that the previously used MIG bounds require $\mathcal{S}$ to
be compact, which does not hold under the considered noise model in Assumption
3. By bounding the domain w.h.p., Curi et al. (2020a) show that this only
increases the MIG bounds (e.g., in case of the squared-exponential kernel) by
at most a $\text{polylog}(T)$ factor.

##  5 Robust RL Applications and Experiments

We now discuss concrete instantiations of RH-UCRL for three important robust
RL scenarios: (i) adversarial-robustness, (ii) action-robustness, and (iii)
parameter-robustness. In all of the above scenarios, we experimentally
demonstrate that RH-UCRL outperforms or successfully competes with the state-
of-the-art variants designed specifically for these settings. In Appendix D,
we present experimental details and additional results.

Experimental Environments. We use the Mujoco suite (Todorov et al., 2012) to
demonstrate the effectiveness of our algorithms in all the considered robust-
RL settings. In particular, we use the Half Cheetah, Hopper, Inverted
Pendulum, Reacher, Swimmer, and Walker robots.

Figure 3:  Average and worst-case return of different algorithms in the Noisy
Action-Robust Setting in Mujoco tasks. RH-UCRL mostly outperforms other
algorithms in terms of worst-case return. The non-robust baseline, H-UCRL, has
good average performance but has an extreme drop in worst-case performance.
Overall, the ablations perform better here than in the Adversarial-Robust
setting.

Baselines. Besides the specific algorithms designed for each setting, we use
H-UCRL (Curi et al., 2020a) as a non-robust baseline and three ablations
derived from RH-UCRL, namely MiniMax, MiniMaxMF and BestResponse. The MiniMax
algorithm is:

$(\pi_{t},\bar{\pi}_{t})\in\operatorname*{arg\,max}_{\pi\in\Pi}\min_{\bar{\pi}\in\bar{\Pi}}J^{(e)}_{t}(\pi,\bar{\pi}),$
(12)

where $J^{(e)}_{t}(\pi,\bar{\pi})$ corresponds to the expected performance,
where the expectation is taken with respect to the aleatoric and epistemic
uncertainty, i.e., none of the players actively explore. Next, the MiniMaxMF
algorithm is a model-free implementation of Eq. 12 that uses SAC (Haarnoja et
al., 2018) as the optimizer for each player. The BestResponse algorithm is:

$\displaystyle\pi_{t}$
$\displaystyle\in\operatorname*{arg\,max}_{\pi\in\Pi}\min_{\bar{\pi}\in\bar{\Pi}}J_{t}^{(o)}(\pi,\bar{\pi}),$
(13a) $\displaystyle\bar{\pi}_{t}$
$\displaystyle\in\operatorname*{arg\,min}_{\bar{\pi}\in\bar{\Pi}}J_{t}^{(e)}(\pi_{t},\bar{\pi}).$
(13b)

Thus, the agent is the same as in RH-UCRL, whereas the adversary simply plays
the best-response to the agent’s policy and does not perform exploration with
pessimism. The goal of BestResponse is to analyze if exploration of the
adversary through pessimism is empirically important, of MaxiMin-MB is to
analyze if any exploration is empirically important, and of MaxiMin-MF is to
analyze if using a model of the dynamics is beneficial.

###  5.1 Adversarial-Robust Reinforcement Learning

This setting is the most general one that we also consider in Section 4. The
agent and the adversary can have distinct action spaces, which can also be
seen as a particular instance of multi-agent RL with two competing agents. In
the braking system motivating example, this can be used to model an
adversarial state-dependent friction coefficient, e.g., icy roads. Having good
robust performance in this setting implies braking robustly even with changing
conditions.

The deep robust RL algorithms that we compare with are RARL (Pinto et al.,
2017) and RAP (Vinitsky et al., 2020), and we use the adversarial action space
proposed by Pinto et al. (2017). We train all algorithms for 200 episodes
except for RARL and RAP; since they are on-policy algorithms, we train them
for 1000 episodes. To evaluate robust performance (recall Eq. 4), we freeze
the output policy and train only its adversary by using SAC for 200 episodes.

In Figure 2, we show the worst-case and average returns on the different
environments. In terms of average performance, there is no algorithm that
performs better than others in all of the environments. On the other hand,
comparing worst-case performance, RH-UCRL clearly outperforms the robust
ablations, deep robust RL and non-robust baselines. For example, in the
Inverted Pendulum stabilization task, RH-UCRL is the only algorithm that
discovers a robust policy while all other algorithms severely fail.
BestResponse and RAP manage to learn a policy that stabilizes the pendulum
even when they learn with an adversary. However, when facing a worst-case
adversary, they fail to complete the task.

Comparing RH-UCRL with non-robust H-UCRL, we see that in most environments it
has comparable or better worst-case and average performance. This indicates
that RH-UCRL is not only robust, but using an adversary during training
practically helps with exploration. Pinto et al. (2017) also report similar
findings regarding robust training. Comparing RH-UCRL with the ablations, we
see that RH-UCRL achieves higher robust performance. From here, we conclude
that exploring with both the agent and the adversary during training is
crucial to achieve high robust performance in this setting. Finally, we see
that both RARL and RAP have poor robust performance when trained for 1000
episodes, which demonstrates their sample inefficiency.

Figure 4:  Returns of different algorithms in the Parameter-Robust Setting in
Mujoco tasks for different masses during evaluation. Although RH-UCRL
optimizes for the worst-case relative mass in this setting, it also performs
well over different value of mass parameters.

###  5.2 Action-Robust Reinforcement Learning

Tessler et al. (2019) introduce the action-robust setting, where both the
agent and the adversary share the action space $\mathcal{\mathcal{A}}$ and
jointly execute a single action in the environment. This is useful, e.g., to
model robustness to changes in the actuator dynamics, e.g., due to tire wear
or incorrect pressure in a braking system. The action is sampled from a
mixture policy
$\mathbf{a}^{\text{mix}}\sim\pi^{\text{mix}}=\Gamma_{\alpha}(\pi,\bar{\pi})$,
where $\alpha\in[0,1]$ is a known parameter that controls the mixture
proportion. The system evolves according to
$\mathbf{s}_{h+1}=f^{\prime}(\mathbf{s}_{h},\mathbf{a}^{\text{mix}}_{h})+\bm{\omega}_{h}$.

Besides the previous baselines, we compare to AR-DDPG (Tessler et al., 2019),
and show the results of the experiment in Figure 3. Here, RH-UCRL is also
comparable or better than the baselines in terms of average and worst-case
returns. However, the ablations perform better than in the adversarial-robust
setting. This is possibly due to the agent and adversary sharing the action
space: The agent injects “enough” exploration to successfully learn both
policies.

###  5.3 Parameter-Robust Reinforcement Learning

The goal in this setting is to be robust to changes in parameters, such as
mass or friction, that can occur between training and test time. Being robust
to a fixed parameter is equivalent to considering a stateless adversary policy
in the RH-UCRL algorithm (7), i.e.,
$\bar{\Pi}:\varnothing\to\mathcal{\mathcal{A}}$. Common benchmarks in this
setting are domain randomization (Peng et al., 2018; Tobin et al., 2017) and
EP-OPT (Rajeswaran et al., 2017). The former randomizes the parameters in the
simulation and uses the average over these parameters as a surrogate of the
maximum. The latter also randomizes the parameters but considers the CVaR as a
surrogate of the maximum. As they are on-policy procedures, we train them
using data for 1000 episodes. Finally, we evaluate the policies in different
environments by varying the corresponding mass parameters.

We show the results of this setting in Figure 4. Although RH-UCRL optimizes
for the worst-case parameter, it performs well over different mass parameter
values, and, except in the Walker environment, its performance remains robust
and nearly constant for different values of the mass parameter. H-UCRL is
trained with nominal mass only (relative mass = 1), and it suffers in
performance when varying the mass. This is most notable in the Half Cheetah
environment (see Fig. 4). The robust variants, instead, can alter the mass
during training and often perform better than H-UCRL. A particular case
happens with the BestResponse algorithm in the Inverted Pendulum, where the
adversary is greedy and so it swiftly chooses a small mass and never changes
it during training. The agent learns only for this small mass and, when
evaluated with different ones, it performs poorly. We also observe that in the
Hopper, the MaxiMin-MF outperforms the MaxiMin-MB. The reason for this might
be due to early stopping of the environment, as it is possible that the
transitions collected in 200 episodes are not sufficient for learning the
model, but allow for learning a policy in a model-free way.

##  6 Conclusion

We introduced the RH-UCRL algorithm, a practical algorithm for deep model-
based robust RL. It uses optimistic and pessimistic estimates of the robust
performance to efficiently explore both the agent and fictitious adversary
decision spaces during policy learning. We showed that RH-UCRL is provably
robust and we established sample-complexity and regret guarantees. We
instantiated our algorithm in important robust-RL settings such as
adversarial-robust RL, parameter-robust RL, and action-robust RL. Empirically,
RH-UCRL outperforms state-of-the-art deep robust RL algorithms. Perhaps
surprisingly, its discovered robust policies often attain better non-robust
performance than the ones found by non-robust algorithms, indicating benefits
of RH-UCRL for exploration.

## Acknowledgments and Disclosure of Funding

This project has received funding from the European Research Council (ERC)
under the European Unions Horizon 2020 research and innovation program grant
agreement No 815943. It was also supported by a fellowship from the Open
Philanthropy Project.

## References

  * Antos et al. (2008) Antos, A., Szepesvári, C., and Munos, R.  Fitted Q-iteration in continuous action-space MDPs.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , pp. 9–16, 2008.
  * Auer et al. (2009) Auer, P., Jaksch, T., and Ortner, R.  Near-optimal regret bounds for reinforcement learning.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , pp. 89–96, 2009.
  * Bai & Jin (2020) Bai, Y. and Jin, C.  Provable self-play algorithms for competitive reinforcement learning.  In _International Conference on Machine Learning (ICML)_ , pp. 551–560, 2020.
  * Başar & Bernhard (2008) Başar, T. and Bernhard, P.  _H-infinity optimal control and related minimax design problems: a dynamic game approach_.  Springer Science & Business Media, 2008.
  * Bemporad et al. (2003) Bemporad, A., Borrelli, F., and Morari, M.  Min-max control of constrained uncertain discrete-time linear systems.  _IEEE Transactions on automatic control_ , 48(9):1600–1606, 2003.
  * Bogunovic et al. (2018) Bogunovic, I., Scarlett, J., Jegelka, S., and Cevher, V.  Adversarially robust optimization with Gaussian processes.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , pp. 5760–5770, 2018.
  * Camacho & Alba (2013) Camacho, E. F. and Alba, C. B.  _Model predictive control_.  Springer science & business media, 2013.
  * Chowdhury & Gopalan (2017) Chowdhury, S. R. and Gopalan, A.  On kernelized multi-armed bandits.  In _International Conference on Machine Learning (ICML)_ , pp. 844–853, 2017.
  * Chowdhury & Gopalan (2019) Chowdhury, S. R. and Gopalan, A.  Online learning in kernelized Markov decision processes.  In _Conference on Artificial Intelligence and Statistics (AISTATS)_ , pp. 3197–3205, 2019.
  * Chua et al. (2018) Chua, K., Calandra, R., McAllister, R., and Levine, S.  Deep reinforcement learning in a handful of trials using probabilistic dynamics models.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , pp. 4754–4765, 2018.
  * Cover & Thomas (1991) Cover, T. M. and Thomas, J. A.  Entropy, relative entropy and mutual information.  _Elements of information theory_ , 2(1):12–13, 1991.
  * Curi et al. (2020a) Curi, S., Berkenkamp, F., and Krause, A.  Efficient model-based reinforcement learning through optimistic policy search and planning.  _Conference on Neural Information Processing Systems (NeurIPS)_ , 33, 2020a.
  * Curi et al. (2020b) Curi, S., Melchior, S., Berkenkamp, F., and Krause, A.  Structured variational inference in partially observable unstable gaussian process state space models.  In _Learning for Dynamics and Control_ , pp. 147–157, 2020b.
  * Deisenroth & Rasmussen (2011) Deisenroth, M. and Rasmussen, C. E.  Pilco: A model-based and data-efficient approach to policy search.  In _International Conference on machine learning (ICML)_ , pp. 465–472, 2011.
  * Der Kiureghian & Ditlevsen (2009) Der Kiureghian, A. and Ditlevsen, O.  Aleatory or epistemic? does it matter?  _Structural safety_ , 31(2):105–112, 2009.
  * Desautels et al. (2014) Desautels, T., Krause, A., and Burdick, J. W.  Parallelizing exploration-exploitation tradeoffs in Gaussian process bandit optimization.  _Journal of Machine Learning Research (JMLR)_ , 15:3873–3923, 2014.
  * Dulac-Arnold et al. (2019) Dulac-Arnold, G., Mankowitz, D., and Hester, T.  Challenges of real-world reinforcement learning.  _arXiv preprint arXiv:1904.12901_ , 2019.
  * Durand et al. (2018) Durand, A., Maillard, O.-A., and Pineau, J.  Streaming kernel regression with provably adaptive mean, variance, and regularization.  _The Journal of Machine Learning Research (JMLR)_ , 19(1):650–683, 2018.
  * Haarnoja et al. (2018) Haarnoja, T., Zhou, A., Abbeel, P., and Levine, S.  Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor.  In _International Conference on Machine Learning (ICML)_ , pp. 1861–1870, 2018.
  * Iyengar (2005) Iyengar, G. N.  Robust dynamic programming.  _Mathematics of Operations Research_ , 30(2):257–280, 2005.
  * Kamalaruban et al. (2020) Kamalaruban, P., Huang, Y.-T., Hsieh, Y.-P., Rolland, P., Shi, C., and Cevher, V.  Robust reinforcement learning via adversarial training with Langevin dynamics.  _Conference on Neural Information Processing Systems (NeurIPS)_ , 33, 2020.
  * Kamthe & Deisenroth (2018) Kamthe, S. and Deisenroth, M.  Data-efficient reinforcement learning with probabilistic model predictive control.  In _Conference on Artificial Intelligence and Statistics (AISTATS)_ , pp. 1701–1710, 2018.
  * Kingma & Ba (2014) Kingma, D. P. and Ba, J.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Kirschner et al. (2020) Kirschner, J., Bogunovic, I., Jegelka, S., and Krause, A.  Distributionally robust Bayesian optimization.  In _Conference on Artificial Intelligence and Statistics (AISTATS)_ , pp. 2174–2184, 2020.
  * Krause & Ong (2011) Krause, A. and Ong, C. S.  Contextual Gaussian process bandit optimization.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , pp. 2447–2455, 2011.
  * Lagoudakis & Parr (2002) Lagoudakis, M. G. and Parr, R.  Value function approximation in zero-sum Markov games.  In _Conference on Uncertainty in artificial intelligence (UAI)_ , pp. 283–292, 2002.
  * Littman (1994) Littman, M. L.  Markov games as a framework for multi-agent reinforcement learning.  In _Machine learning proceedings_ , pp. 157–163. Elsevier, 1994\.
  * Littman & Szepesvári (1996) Littman, M. L. and Szepesvári, C.  A generalized reinforcement-learning model: Convergence and applications.  In _International Conference on Machine Learning (ICML)_ , pp. 310–318, 1996.
  * Malik et al. (2019) Malik, A., Kuleshov, V., Song, J., Nemer, D., Seymour, H., and Ermon, S.  Calibrated model-based deep reinforcement learning.  In _International Conference on Machine Learning (ICML)_ , pp. 4314–4323, 2019.
  * Mohamed et al. (2019) Mohamed, S., Rosca, M., Figurnov, M., and Mnih, A.  Monte Carlo gradient estimation in machine learning.  _arXiv preprint arXiv:1906.10652_ , 2019.
  * Nilim & El Ghaoui (2005) Nilim, A. and El Ghaoui, L.  Robust control of Markov decision processes with uncertain transition matrices.  _Operations Research_ , 53(5):780–798, 2005.
  * Osband et al. (2016) Osband, I., Blundell, C., Pritzel, A., and Roy, B. V.  Deep exploration via bootstrapped DQN.  _Conference on Neural Information Processing Systems (NeurIPS)_ , pp. 4033–4041, 2016.
  * Peng et al. (2018) Peng, X. B., Andrychowicz, M., Zaremba, W., and Abbeel, P.  Sim-to-real transfer of robotic control with dynamics randomization.  In _IEEE international conference on robotics and automation (ICRA)_ , pp. 1–8. IEEE, 2018.
  * Perolat et al. (2015) Perolat, J., Scherrer, B., Piot, B., and Pietquin, O.  Approximate dynamic programming for two-player zero-sum Markov games.  In _International Conference on Machine Learning (ICML)_ , pp. 1321–1329, 2015.
  * Pinto et al. (2017) Pinto, L., Davidson, J., Sukthankar, R., and Gupta, A.  Robust adversarial reinforcement learning.  In _International Conference on Machine Learning (ICML)_ , pp. 2817–2826, 2017.
  * Rajeswaran et al. (2017) Rajeswaran, A., Ghotra, S., Ravindran, B., and Levine, S.  Epopt: Learning robust neural network policies using model ensembles.  In _International Conference on Learning Representations (ICLR)_ , 2017.
  * Schulman et al. (2015) Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P.  Trust region policy optimization.  In _International conference on machine learning_ , pp. 1889–1897. PMLR, 2015.
  * Schulman et al. (2017) Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_ , 2017.
  * Silver et al. (2014) Silver, D., Lever, G., Heess, N., Degris, T., Wierstra, D., and Riedmiller, M.  Deterministic policy gradient algorithms.  In _International Conference on Machine Learning (ICML)_ , pp. 387–395, 2014.
  * Srinivas et al. (2010) Srinivas, N., Krause, A., Kakade, S., and Seeger, M.  Gaussian process optimization in the bandit setting: no regret and experimental design.  In _International Conference on Machine Learning (ICML)_ , pp. 1015–1022, 2010.
  * Sutton & Barto (2018) Sutton, R. S. and Barto, A. G.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Tamar et al. (2014) Tamar, A., Mannor, S., and Xu, H.  Scaling up robust MDPs using function approximation.  In _International Conference on Machine Learning (ICML)_ , pp. 181–189, 2014.
  * Tessler et al. (2019) Tessler, C., Efroni, Y., and Mannor, S.  Action robust reinforcement learning and applications in continuous control.  In _International Conference on Machine Learning (ICML)_ , pp. 6215–6224, 2019.
  * Tobin et al. (2017) Tobin, J., Fong, R., Ray, A., Schneider, J., Zaremba, W., and Abbeel, P.  Domain randomization for transferring deep neural networks from simulation to the real world.  In _International Conference on Intelligent Robots and Systems (IROS)_ , pp. 23–30. IEEE, 2017.
  * Todorov et al. (2012) Todorov, E., Erez, T., and Tassa, Y.  Mujoco: A physics engine for model-based control.  In _Conference on Intelligent Robots and Systems_ , pp. 5026–5033. IEEE, 2012.
  * Valko et al. (2013) Valko, M., Korda, N., Munos, R., Flaounas, I., and Cristianini, N.  Finite-time analysis of kernelised contextual bandits.  In _Uncertainty in Artificial Intelligence (UAI)_ , pp. 654, 2013\.
  * van Hasselt et al. (2016) van Hasselt, H., Guez, A., Hessel, M., Mnih, V., and Silver, D.  Learning values across many orders of magnitude.  _Conference on Neural Information Processing Systems (NeurIPS)_ , pp. 4294–4302, 2016.
  * Vinitsky et al. (2020) Vinitsky, E., Du, Y., Parvate, K., Jang, K., Abbeel, P., and Bayen, A.  Robust reinforcement learning using adversarial populations.  _arXiv preprint arXiv:2008.01825_ , 2020.
  * Wiesemann et al. (2013) Wiesemann, W., Kuhn, D., and Rustem, B.  Robust Markov decision processes.  _Mathematics of Operations Research_ , 38(1):153–183, 2013.
  * Zhang et al. (2020) Zhang, K., Kakade, S., Basar, T., and Yang, L.  Model-based multi-agent rl in zero-sum markov games with near-optimal sample complexity.  _Conference on Neural Information Processing Systems (NeurIPS)_ , 33, 2020.

Supplementary Material

Combining Pessimism with Optimism for
Robust and Efficient Model-based Deep Reinforcement Learning
Submitted to ICML 2021

##  Appendix A Relevant Definitions and Results

######  Lemma 1 (Adapted from Corollary 1 in Curi et al. (2020a)).

Based on Assumptions 1 and 3, for every
$\mathbf{s},\mathbf{s}^{\prime}\in\mathcal{S}$, it holds:

$\|f(\mathbf{s},\pi(\mathbf{s}),\bar{\pi}(\mathbf{s}))-\tilde{f}(\mathbf{s}^{\prime},\pi(\mathbf{s}^{\prime}),\bar{\pi}(\mathbf{s}^{\prime}))\|_{2}\leq
L_{f}\sqrt{1+L^{2}_{\pi}+L^{2}_{\bar{\pi}}}\|\mathbf{s}-\mathbf{s}^{\prime}\|_{2}.$
(14)

###### Proof.

$\displaystyle\|f(\mathbf{s},\pi(\mathbf{s}),\bar{\pi}(\mathbf{s}))-\tilde{f}(\mathbf{s}^{\prime},\pi(\mathbf{s}^{\prime}),\bar{\pi}(\mathbf{s}^{\prime}))\|_{2}$
$\displaystyle\leq
L_{f}\sqrt{\|\mathbf{s}-\mathbf{s}^{\prime}\|_{2}^{2}+\|\pi(\mathbf{s})-\pi(\mathbf{s}^{\prime})\|_{2}^{2}+\|\bar{\pi}(\mathbf{s}^{\prime})-\bar{\pi}(\mathbf{s})\|_{2}^{2}}$
(15a)
$\displaystyle\leq\sqrt{\|\mathbf{s}-\mathbf{s}^{\prime}\|_{2}^{2}+L^{2}_{\pi}\|\mathbf{s}-\mathbf{s}^{\prime}\|_{2}^{2}+L^{2}_{\bar{\pi}}\|\mathbf{s}-\mathbf{s}^{\prime}\|_{2}^{2}}$
(15b)
$\displaystyle=L_{f}\sqrt{1+L^{2}_{\pi}+L^{2}_{\bar{\pi}}}\|\mathbf{s}-\mathbf{s}^{\prime}\|_{2}.$
(15c)

Eq. 15a holds due to Lipschitz continuity of $f$ and Eq. 15b is due to
Lipschitz continuity of $\pi$ and $\bar{\pi}$, which we assume in Assumptions
1 and 3. ∎

######  Lemma 2 (Adapted from Lemma 3 in Curi et al. (2020a)).

Based on Assumptions 1 and 3, it holds:

$|J(f,\pi,\bar{\pi})-J(\tilde{f},\pi,\bar{\pi})|\leq
L_{r}\sqrt{1+L^{2}_{\pi}+L^{2}_{\bar{\pi}}}\sum_{h=0}^{H}\mathbb{E}\mathopen{}\left[\|\mathbf{s}_{h}-\tilde{\mathbf{s}}_{h}\|_{2}\right]\mathclose{},$
(16)

where $\tilde{\mathbf{s}}_{h}$ for $h=0,\ldots,H$ is the trajectory generated
by the dynamics $\tilde{f}$, starting from
$\tilde{\mathbf{s}}_{0}=\mathbf{s}_{0}$ with $\omega_{h}=\tilde{\omega}_{h}$.

###### Proof.

$\displaystyle|J(f,\pi,\bar{\pi})-J(\tilde{f},\pi,\bar{\pi})|$
$\displaystyle=\left|\mathbb{E}\mathopen{}\left[\sum_{h=0}^{H}r(\mathbf{s},\mathbf{a},\bar{\mathbf{a}})-\sum_{h=0}^{H}r(\tilde{\mathbf{s}},\tilde{\mathbf{a}},\tilde{\bar{\mathbf{a}}})\right]\mathclose{}\right|$
(17a)
$\displaystyle=\left|\sum_{h=0}^{H}\mathbb{E}\mathopen{}\left[r(\mathbf{s},\mathbf{a},\bar{\mathbf{a}})-r(\mathbf{s},\mathbf{a},\bar{\mathbf{a}})\right]\mathclose{}\right|$
(17b) $\displaystyle\leq
L_{r}\sqrt{1+L^{2}_{\pi}+L^{2}_{\bar{\pi}}}\sum_{h=0}^{H}\mathbb{E}\mathopen{}\left[\|\mathbf{s}_{h}-\tilde{\mathbf{s}}_{h}\|_{2}\right]\mathclose{}.$
(17c)

Eq. 17a follows by definition of $J$, Eq. 17b from linearity of expectation,
and Eq. 17c from Lipschitzness of the policy and the reward function, which we
assume in Assumption 1.

∎

The following lemma bounds the deviation between the optimistic/pessimistic
and the true trajectory in a single episode.

######  Lemma 3 (Adapted from Lemma 4 in (Curi et al., 2020a)).

Under Assumptions 1, 2 and 3, for all episodes $t\geq 1$, any $\eta\in[-1,1]$,
$h\in\\{1,\dots,H\\}$, $\pi\in\Pi$ and $\bar{\pi}\in\bar{\Pi}$ it holds:

$\|\mathbf{s}_{h,t}-\tilde{\mathbf{s}}_{h,t}\|_{2}\leq
2\beta_{t-1}\Big{(}1+(L_{f}+2\beta_{t-1}L_{\sigma})\sqrt{1+L_{\pi}^{2}+L_{\bar{\pi}}^{2}}\Big{)}^{h-1}\sum_{h^{\prime}=0}^{h-1}\|\bm{\sigma}_{t-1}(\mathbf{s}_{h^{\prime},t},\pi_{t}(\mathbf{s}_{h^{\prime},t}),\bar{\pi}_{t}(\mathbf{s}_{h^{\prime},t}))\|_{2},$
(18)

where $\tilde{\mathbf{s}}_{h,t}$ is generated by any system
$\tilde{f}\in\mathcal{M}_{t}\coloneqq\left\\{\tilde{f}\text{ s.t.
}|\tilde{f}(\mathbf{s},\mathbf{a},\bar{\mathbf{a}})-\bm{\mu}_{t-1}(\mathbf{s},\mathbf{a},\bar{\mathbf{a}})|\leq\beta_{t}\bm{\sigma}_{t-1}(\mathbf{s},\mathbf{a},\bar{\mathbf{a}})\right\\}$.
We refer to $\mathcal{M}_{t}$ as the set of plausible models at the beginning
of episode $t$.

###### Proof.

To avoid notational clutter, we denote the closed-loop dynamics as
$f^{\pi,\bar{\pi}}(\mathbf{s})=f(\mathbf{s},\pi(\mathbf{s}),\bar{\pi}(\mathbf{s}))$
and the closed-loop epistemic uncertainty as
$\bm{\sigma}^{\pi,\bar{\pi}}(\mathbf{s})=\bm{\sigma}(\mathbf{s},\pi(\mathbf{s}),\bar{\pi}(\mathbf{s}))$.
Likewise, we use the following Lipschitz constants shorthands $L_{f,\pi}\equiv
L_{f}\sqrt{1+L_{\pi}^{2}+L_{\bar{\pi}}^{2}}$ and $L_{\sigma,\pi}\equiv
L_{\sigma}\sqrt{1+L_{\pi}^{2}+L_{\bar{\pi}}^{2}}$.

We first prove by induction that

$\|\mathbf{s}_{h,t}-\tilde{\mathbf{s}}_{h,t}\|_{2}\leq
2\beta_{t-1}\sum_{h^{\prime}=0}^{h-1}\left(L_{f,\pi}+2\beta_{t-1}L_{\sigma,\pi}\right)^{h-1-h^{\prime}}\|\bm{\sigma}_{t-1}^{\pi_{t},\bar{\pi}_{t}}(\mathbf{s}_{h^{\prime},t})\|$
(19a)

For $h=0$, clearly $\mathbf{s}_{0,t}=\tilde{\mathbf{s}}_{0,t}$, while the
right-hand-side of Eq. 19a is always non-negative. We assume that for $h$ the
inductive hypothesis (19a) holds. For $h+1$ we have:

$\displaystyle\|\mathbf{s}_{h+1,t}-\tilde{\mathbf{s}}_{h+1,t}\|_{2}$
$\displaystyle=\|f^{\pi_{t},\bar{\pi}_{t}}(\mathbf{s}_{h,t})-\tilde{f}^{\pi_{t},\bar{\pi}_{t}}(\tilde{\mathbf{s}}_{h,t})\|_{2}$
(19b)
$\displaystyle=\|f^{\pi_{t},\bar{\pi}_{t}}(\mathbf{s}_{h,t})-\tilde{f}^{\pi_{t},\bar{\pi}_{t}}(\tilde{\mathbf{s}}_{h,t})+f^{\pi_{t},\bar{\pi}_{t}}(\tilde{\mathbf{s}}_{h,t})-f^{\pi_{t},\bar{\pi}_{t}}(\tilde{\mathbf{s}}_{h,t})\|_{2}$
(19c)
$\displaystyle\leq\|f^{\pi_{t},\bar{\pi}_{t}}(\mathbf{s}_{h,t})-f^{\pi_{t},\bar{\pi}_{t}}(\tilde{\mathbf{s}}_{h,t})\|_{2}+\|f^{\pi_{t},\bar{\pi}_{t}}(\tilde{\mathbf{s}}_{h,t})-\tilde{f}^{\pi_{t},\bar{\pi}_{t}}(\tilde{\mathbf{s}}_{h,t})\|_{2}$
(19d) $\displaystyle\leq
L_{f,\pi}\|\mathbf{s}_{h,t}-\tilde{\mathbf{s}}_{h,t}\|_{2}+\|f^{\pi_{t},\bar{\pi}_{t}}(\tilde{\mathbf{s}}_{h,t})-\tilde{f}^{\pi_{t},\bar{\pi}_{t}}(\tilde{\mathbf{s}}_{h,t})\|_{2}$
(19e) $\displaystyle\leq
L_{f,\pi}\|\mathbf{s}_{h,t}-\tilde{\mathbf{s}}_{h,t}\|_{2}+2\beta_{t-1}\|\bm{\sigma}^{\pi_{t},\bar{\pi}_{t}}_{t-1}(\tilde{\mathbf{s}}_{h,t})\|_{2}$
(19f)
$\displaystyle=L_{f,\pi}\|\mathbf{s}_{h,t}-\tilde{\mathbf{s}}_{h,t}\|_{2}+2\beta_{t-1}\|\bm{\sigma}^{\pi_{t},\bar{\pi}_{t}}_{t-1}(\tilde{\mathbf{s}}_{h,t})+\bm{\sigma}^{\pi_{t},\bar{\pi}_{t}}_{t-1}(\mathbf{s}_{h,t})-\bm{\sigma}^{\pi_{t},\bar{\pi}_{t}}_{t-1}(\mathbf{s}_{h,t})\|_{2}$
(19g) $\displaystyle\leq
L_{f,\pi}\|\mathbf{s}_{h,t}-\tilde{\mathbf{s}}_{h,t}\|_{2}+2\beta_{t-1}\left(\|\bm{\sigma}^{\pi_{t},\bar{\pi}_{t}}_{t-1}(\tilde{\mathbf{s}}_{h,t})-\bm{\sigma}^{\pi_{t},\bar{\pi}_{t}}_{t-1}(\mathbf{s}_{h,t})\|_{2}+\|\bm{\sigma}^{\pi_{t},\bar{\pi}_{t}}_{t-1}(\mathbf{s}_{h,t})\|_{2}\right)$
(19h)
$\displaystyle\leq\left(L_{f,\pi}+2\beta_{t-1}L_{\sigma,\pi}\right)\|\mathbf{s}_{h,t}-\tilde{\mathbf{s}}_{h,t}\|_{2}+2\beta_{t-1}\|\bm{\sigma}^{\pi_{t},\bar{\pi}_{t}}_{t-1}(\mathbf{s}_{h,t})\|_{2}$
(19i) $\displaystyle\leq
2\beta_{t-1}\sum_{h^{\prime}=0}^{(h+1)-1}\left(L_{f,\pi}+2\beta_{t-1}L_{\sigma,\pi}\right)^{(h+1)-1-h^{\prime}}\|\bm{\sigma}_{t-1}^{\pi_{t},\bar{\pi}_{t}}(\mathbf{s}_{h^{\prime},t})\|_{2}$
(19j)

Here, Eq. 19b holds by applying the transition dynamics
$f^{\pi_{t},\bar{\pi}_{t}}$ and $\tilde{f}^{\pi_{t},\bar{\pi}_{t}}$ with the
same noise realization $\omega_{h}=\tilde{\omega}_{h}$; Eq. 19c holds by
adding and subtracting $f^{\pi_{t},\bar{\pi}_{t}}(\tilde{\mathbf{s}}_{h,t})$;
Eq. 19d follows from the triangular inequality; Eq. 19e comes from Lemma 1;
Eq. 19f holds due to both $f$ and $\tilde{f}$ belonging to the set of
plausible models $\mathcal{M}_{t}$ (see Lemma 3 for its definition); Eq. 19g
holds by adding and substracting
$\bm{\sigma}^{\pi_{t},\bar{\pi}_{t}}(\mathbf{s}_{h,t})$; Eq. 19h is by
applying the triangular inequality once more; Eq. 19i is due to the Lipschitz
continuity of $\bm{\sigma}$ as per assumption 3; and (19j) holds by replacing
the inductive hypothesis from (19a).

Finally, we notice that
$\left(L_{f,\pi}+2\beta_{t-1}L_{\sigma,\pi}\right)^{h-1-h^{\prime}}<\left(1+L_{f,\pi}+2\beta_{t-1}L_{\sigma,\pi}\right)^{h-1-h^{\prime}}\leq\left(1+L_{f,\pi}+2\beta_{t-1}L_{\sigma,\pi}\right)^{h-1}$
and the main result follows by combining this with Eq. 19j.

∎

##  Appendix B Proofs from Section 4.4

We start the analysis of the performance of RH-UCRL, by first bounding its
instantaneous robust-regret by the difference between optimistic and
pessimistic performance estimates.

######  Lemma 4.

Let $\pi^{\star}$ be the benchmark policy from Eq. 3, and let $\pi_{t}$ and
$\bar{\pi}_{t}$ be the policies selected by RH-UCRL at time $t$. Under the
callibrated model Assumption 2, the following holds with probability at least
$1-\delta$:

$\min_{\bar{\pi}\in\bar{\Pi}}J(f,\pi^{\star},\bar{\pi})-\min_{\bar{\pi}\in\bar{\Pi}}J(f,\pi_{t},\bar{\pi})\leq
J_{t}^{(o)}(\pi_{t},\bar{\pi}_{t})-J^{(p)}(\pi_{t},\bar{\pi}_{t}).$ (20)

###### Proof.

We refer to the considered quantity
$\min_{\bar{\pi}\in\bar{\Pi}}J(f,\pi^{\star},\bar{\pi})-\min_{\bar{\pi}\in\bar{\Pi}}J(f,\pi_{t},\bar{\pi})$
as the robust instantaneous regret of the selected policy $\pi_{t}$, and we
proceed by providing its upper bound:

$\displaystyle\min_{\bar{\pi}\in\bar{\Pi}}J(f,\pi^{\star},\bar{\pi})-\min_{\bar{\pi}\in\bar{\Pi}}J(f,\pi_{t},\bar{\pi})$
$\displaystyle\leq\min_{\bar{\pi}\in\bar{\Pi}}J_{t}^{(o)}(\pi^{\star},\bar{\pi})-\min_{\bar{\pi}\in\bar{\Pi}}J(f,\pi_{t},\bar{\pi})$
(21a)
$\displaystyle\leq\min_{\bar{\pi}\in\bar{\Pi}}J_{t}^{(o)}(\pi_{t},\bar{\pi})-\min_{\bar{\pi}\in\bar{\Pi}}J(f,\pi_{t},\bar{\pi})$
(21b) $\displaystyle\leq
J_{t}^{(o)}(\pi_{t},\bar{\pi}_{t})-\min_{\bar{\pi}\in\bar{\Pi}}J(f,\pi_{t},\bar{\pi})$
(21c) $\displaystyle\leq
J_{t}^{(o)}(\pi_{t},\bar{\pi}_{t})-\min_{\bar{\pi}\in\bar{\Pi}}J^{(p)}(\pi_{t},\bar{\pi})$
(21d)
$\displaystyle=J_{t}^{(o)}(\pi_{t},\bar{\pi}_{t})-J^{(p)}(\pi_{t},\bar{\pi}_{t}).$
(21e)

Here, inequality (21a) holds by definition of the optimistic estimate in Eq.
5a; inequality (21b) holds by definition of protagonist policy in the RH-UCRL
algorithm (7a); and inequality (21d) holds by definition of the pessimistic
estimate in Eq. 6a; finally, equality (21e) holds by definition of the
antagonist policy in the RH-UCRL algorithm (7b). ∎

######  Lemma 5.

Under Assumptions 1, 2 and 3, let $\pi_{t}$ and $\bar{\pi}_{t}$ be the
policies selected by RH-UCRL at episode $t$. Then, the following holds for the
difference between its optimistic and pessimistic performance:

$J_{t}^{(o)}(\pi_{t},\bar{\pi}_{t})-J^{(p)}(\pi_{t},\bar{\pi}_{t})\leq
4L_{r}\beta_{T}^{H}C^{H}\sum_{h=0}^{H}\mathbb{E}\mathopen{}\left[\sum_{h^{\prime}=0}^{h-1}\|\bm{\sigma}_{t-1}(\mathbf{s}_{h^{\prime},t},\pi_{t}(\mathbf{s}_{h^{\prime},t}),\bar{\pi}_{t}(\mathbf{s}_{h^{\prime},t}))\|_{2}\right]\mathclose{},$
(22)

where $C=(1+L_{f}+L_{\sigma})(1+L_{\pi}^{2}+L_{\bar{\pi}}^{2})^{1/2}$.

###### Proof.

$\displaystyle
J_{t}^{(o)}(\pi_{t},\bar{\pi}_{t})-J^{(p)}(\pi_{t},\bar{\pi}_{t})$
$\displaystyle\leq\left|J_{t}^{(o)}(\pi_{t},\bar{\pi}_{t})-J(f,\pi_{t},\bar{\pi}_{t})\right|+\left|J_{t}^{(p)}(\pi_{t},\bar{\pi}_{t})-J(f,\pi_{t},\bar{\pi}_{t})\right|$
(23a) $\displaystyle\leq
L_{r}\sqrt{1+L^{2}_{\pi}+L^{2}_{\bar{\pi}}}\sum_{h=0}^{H}\left(\mathbb{E}\mathopen{}\left[\|\mathbf{s}_{h,t}-\mathbf{s}_{h,t}^{(o)}\|_{2}\right]\mathclose{}+\mathbb{E}\mathopen{}\left[\|\mathbf{s}_{h,t}-\mathbf{s}_{h,t}^{(p)}\|_{2}\right]\mathclose{}\right)$
(23b) Here, Eq. 23a holds by the triangle inequality and Eq. 23b follows from
Lemma 2.

We proceed to upper bound terms
$\|\mathbf{s}_{h,t}-\mathbf{s}_{h,t}^{(o)}\|_{2}$ and
$\|\mathbf{s}_{h,t}-\mathbf{s}_{h,t}^{(p)}\|_{2}$. From Lemma 3, it follows
that both terms can be bounded in the same way as follows:

$\|\mathbf{s}_{h,t}-\mathbf{s}_{h,t}^{(o)}\|_{2}\leq
2\beta_{t-1}\Big{(}(1+L_{f}+2\beta_{t-1}L_{\sigma})\sqrt{1+L_{\pi}^{2}+L_{\bar{\pi}}^{2}}\Big{)}^{h-1}\sum_{h^{\prime}=0}^{h-1}\|\bm{\sigma}_{t-1}(\mathbf{s}_{h^{\prime},t},\pi_{t}(\mathbf{s}_{h^{\prime},t}),\bar{\pi}_{t}(\mathbf{s}_{h^{\prime},t}))\|_{2},$
(23c)

as $f^{(o)}$ and $f^{(p)}$ belong to the set of plausible models
$\mathcal{M}_{t}$ (from Lemma 3).

By applying the previous bound twice in Eq. 23b, and by denoting

$C\coloneqq(1+L_{f}+2L_{\sigma})(1+L_{\pi}^{2}+L_{\bar{\pi}}^{2})^{1/2},$

we arrive at:

$J_{t}^{(o)}(\pi_{t},\bar{\pi}_{t})-J^{(p)}(\pi_{t},\bar{\pi}_{t})\leq
4L_{r}\beta_{T}^{H}C^{H}\sum_{h=0}^{H}\mathbb{E}\mathopen{}\left[\sum_{h^{\prime}=0}^{h-1}\|\bm{\sigma}_{t-1}(\mathbf{s}_{h^{\prime},t},\pi_{t}(\mathbf{s}_{h^{\prime},t}),\bar{\pi}_{t}(\mathbf{s}_{h^{\prime},t}))\|_{2}\right]\mathclose{},$
(23d)

where we used $t\leq T$ and $1\leq\beta_{t}$ is non-decreasing in $t$.

∎

See 1

###### Proof of Theorem 1.

We bound the robust cumulative regret as follows:

$\displaystyle R_{T}$
$\displaystyle=\sum_{t=1}^{T}\underbrace{\min_{\bar{\pi}\in\bar{\Pi}}J(f,\pi^{\star},\bar{\pi})-\min_{\bar{\pi}\in\bar{\Pi}}J(f,\pi_{t},\bar{\pi}_{t})}_{\coloneqq
r_{t}}$ (24a) $\displaystyle\leq\sqrt{T\sum_{t=1}^{T}r_{t}^{2}}$ (24b)
$\displaystyle\leq\sqrt{T\sum_{t=1}^{T}(4L_{r}\beta_{T}^{H}C^{H})^{2}\Bigg{(}\sum_{h=0}^{H}\mathbb{E}\mathopen{}\left[\sum_{h^{\prime}=0}^{h-1}\|\bm{\sigma}_{t-1}(\mathbf{s}_{h^{\prime},t},\pi_{t}(\mathbf{s}_{h^{\prime},t}),\bar{\pi}_{t}(\mathbf{s}_{h^{\prime},t}))\|_{2}\right]\mathclose{}\Bigg{)}^{2}}$
(24c)
$\displaystyle=4L_{r}\beta_{T}^{H}C^{H}\sqrt{T}\sqrt{\sum_{t=1}^{T}\Bigg{(}\sum_{h=0}^{H}\mathbb{E}\mathopen{}\left[\sum_{h^{\prime}=0}^{h-1}\|\bm{\sigma}_{t-1}(\mathbf{s}_{h^{\prime},t},\pi_{t}(\mathbf{s}_{h^{\prime},t}),\bar{\pi}_{t}(\mathbf{s}_{h^{\prime},t}))\|_{2}\right]\mathclose{}\Bigg{)}^{2}}$
(24d) $\displaystyle\leq
4L_{r}\beta_{T}^{H}C^{H}H\sqrt{T}\sqrt{\sum_{t=1}^{T}\Bigg{(}\mathbb{E}\mathopen{}\left[\sum_{h^{\prime}=0}^{H}\|\bm{\sigma}_{t-1}(\mathbf{s}_{h^{\prime},t},\pi_{t}(\mathbf{s}_{h^{\prime},t}),\bar{\pi}_{t}(\mathbf{s}_{h^{\prime},t}))\|_{2}\right]\mathclose{}\Bigg{)}^{2}}$
(24e) $\displaystyle\leq
4L_{r}\beta_{T}^{H}C^{H}H\sqrt{T}\sqrt{\sum_{t=1}^{T}\mathbb{E}\mathopen{}\left[\Bigg{(}\sum_{h^{\prime}=0}^{H}\|\bm{\sigma}_{t-1}(\mathbf{s}_{h^{\prime},t},\pi_{t}(\mathbf{s}_{h^{\prime},t}),\bar{\pi}_{t}(\mathbf{s}_{h^{\prime},t}))\|_{2}\Bigg{)}^{2}\right]\mathclose{}}$
(24f) $\displaystyle\leq
4L_{r}\beta_{T}^{H}C^{H}H^{3/2}\sqrt{T}\sqrt{\sum_{t=1}^{T}\mathbb{E}\mathopen{}\left[\sum_{h^{\prime}=0}^{H}\|\bm{\sigma}_{t-1}(\mathbf{s}_{h^{\prime},t},\pi_{t}(\mathbf{s}_{h^{\prime},t}),\bar{\pi}_{t}(\mathbf{s}_{h^{\prime},t}))\|_{2}^{2}\right]\mathclose{}}$
(24g) $\displaystyle\leq 4L_{r}\beta_{T}^{H}C^{H}{H}^{3/2}\sqrt{T\Gamma_{T}},$
(24h)

where Eq. 24b is due to the Cauchy-Schwarz’s inequality; Eq. 24c is due to
Lemma 4 and Lemma 5. Finally, Eq. 24f follows from the Jensen’s inequality,
Eq. 24g follows from Cauchy-Schwarz’s inequality, and Eq. 24h follows from the
definition of $\Gamma_{T}$.

∎

See 1

###### Proof of Corollary 1.

We start the proof by recalling some of the previously obtained results. The
instantaneous regret $r_{t}(\pi_{t})$ of a policy $\pi_{t}$ selected at
episode $t$ in Eq. 7a is given by:

$r_{t}(\pi_{t})=\min_{\bar{\pi}\in\bar{\Pi}}J(f,\pi^{\star},\bar{\pi})-\min_{\bar{\pi}\in\bar{\Pi}}J(f,\pi_{t},\bar{\pi}).$
(25)

From Lemma 4 and Lemma 5, it follows that

$r_{t}(\pi_{t})\leq
4L_{r}\beta_{T}^{H}C^{H}\sum_{h=0}^{H}\mathbb{E}\mathopen{}\left[\sum_{h^{\prime}=0}^{h-1}\|\bm{\sigma}_{t-1}(\mathbf{s}_{h^{\prime},t},\pi_{t}(\mathbf{s}_{h^{\prime},t}),\bar{\pi}_{t}(\mathbf{s}_{h^{\prime},t}))\|_{2}\right]\mathclose{}.$
(26)

We also define

$\bar{r}(\pi_{t})\coloneqq\min_{\bar{\pi}\in\bar{\Pi}}J(f,\pi^{\star},\bar{\pi})-\min_{\bar{\pi}\in\bar{\Pi}}J^{(p)}(\pi_{t},\bar{\pi}),$
(27)

and note that $r(\pi_{t})\leq\bar{r}(\pi_{t})$ for every $\pi_{t}$, since
$\min_{\bar{\pi}\in\bar{\Pi}}J^{(p)}(\pi_{t},\bar{\pi})\leq\min_{\bar{\pi}\in\bar{\Pi}}J(f,\pi_{t},\bar{\pi})$.
Another useful observation is that the same bound obtained in Equation 26 also
holds in case of $\bar{r}(\pi_{t})$, i.e.,

$r(\pi_{t})\leq\bar{r}(\pi_{t})\leq
4L_{r}\beta_{T}^{H}C^{H}\sum_{h=0}^{H}\mathbb{E}\mathopen{}\left[\sum_{h^{\prime}=0}^{h-1}\|\bm{\sigma}_{t-1}(\mathbf{s}_{h^{\prime},t},\pi_{t}(\mathbf{s}_{h^{\prime},t}),\bar{\pi}_{t}(\mathbf{s}_{h^{\prime},t}))\|_{2}\right]\mathclose{}.$
(28)

Recall, that the reported policy $\hat{\pi}_{T}$ from Eq. 8 is chosen among
the previously selected episodic policies $\\{\pi_{1},\dots,\pi_{T}\\}$, such
that

$\hat{\pi}_{T}=\operatorname*{arg\,min}_{\pi\in\\{\pi_{1},\dots,\pi_{T}\\}}\bar{r}(\pi).$
(29)

It follows that:

$\displaystyle r(\hat{\pi}_{T})$ $\displaystyle\leq\bar{r}(\hat{\pi}_{T})$
(30a) $\displaystyle\leq\frac{1}{T}\sum_{t=1}^{T}\bar{r}(\pi_{t})$ (30b)
$\displaystyle\leq\frac{1}{T}\sum_{t=1}^{T}4L_{r}\beta_{T}^{H}C^{H}\sum_{h=0}^{H}\mathbb{E}\mathopen{}\left[\sum_{h^{\prime}=0}^{h-1}\|\bm{\sigma}_{t-1}(\mathbf{s}_{h^{\prime},t},\pi_{t}(\mathbf{s}_{h^{\prime},t}),\bar{\pi}_{t}(\mathbf{s}_{h^{\prime},t}))\|_{2}\right]\mathclose{}$
(30c)
$\displaystyle\leq\frac{1}{T}4L_{r}\beta_{T}^{H}C^{H}H\sum_{t=1}^{T}\mathbb{E}\mathopen{}\left[\sum_{h^{\prime}=0}^{H}\|\bm{\sigma}_{t-1}(\mathbf{s}_{h^{\prime},t},\pi_{t}(\mathbf{s}_{h^{\prime},t}),\bar{\pi}_{t}(\mathbf{s}_{h^{\prime},t}))\|_{2}\right]\mathclose{}$
(30d)
$\displaystyle\leq\frac{1}{T}4L_{r}\beta_{T}^{H}C^{H}H\sqrt{T}\sqrt{\sum_{t=1}^{T}\mathbb{E}\mathopen{}\left[\left(\sum_{h^{\prime}=0}^{H}\|\bm{\sigma}_{t-1}(\mathbf{s}_{h^{\prime},t},\pi_{t}(\mathbf{s}_{h^{\prime},t}),\bar{\pi}_{t}(\mathbf{s}_{h^{\prime},t}))\|_{2}\right)^{2}\right]\mathclose{}}$
(30e)
$\displaystyle\leq\frac{1}{T}4L_{r}\beta_{T}^{H}C^{H}H\sqrt{T}\sqrt{\sum_{t=1}^{T}\mathbb{E}\mathopen{}\left[\sum_{h^{\prime}=0}^{H}\|\bm{\sigma}_{t-1}(\mathbf{s}_{h^{\prime},t},\pi_{t}(\mathbf{s}_{h^{\prime},t}),\bar{\pi}_{t}(\mathbf{s}_{h^{\prime},t}))\|_{2}^{2}\right]\mathclose{}}$
(30f)
$\displaystyle\leq\frac{4L_{r}\beta_{T}^{H}C^{H}H^{3/2}\sqrt{T\Gamma_{T}}}{T}$
(30g)

where Eq. 30a follows from Eq. 28, and Eq. 30b follows from the policy
reporting rule in Eq. 29 and by upper bounding minimum with average. Finally,
Eq. 30c is due to Eq. 28, and Eqs. 30d, 30e, 30f and 30g follow the same
argument as in the proof of Theorem 1.

To achieve $r(\hat{\pi}_{T})\leq\epsilon$ for some given $\epsilon>0$, we
require that

$\frac{4L_{r}\beta_{T}^{H}C^{H}H^{3/2}\sqrt{T\Gamma_{T}}}{T}\leq\epsilon.$

By simple inversion it follows that we require the following number of
episodes $T$:

$\frac{T}{\beta_{T}^{2H}\Gamma_{T}}\geq\frac{16L_{r}^{2}H^{3}C^{2H}}{\epsilon^{2}}$

to achieve $r(\hat{\pi}_{T})\leq\epsilon$. ∎

##  Appendix C Gaussian Process Dynamical Models

In this section, we formalize the setting in which the true dynamics $f$ in
Eq. 1 has bounded norm in an RKHS induced by a continuous, symmetric positive
definite kernel function $k:\mathcal{Z}\times\mathcal{Z}\to\mathbb{R}$, with
$\mathcal{Z}=\mathcal{S}\times\mathcal{A}\times\bar{\mathcal{A}}$. We denote
by $\mathcal{K}$ the corresponding RKHS. Having a norm
$\|f\|_{\mathcal{K}}\leq B_{f}$ for some finite $B_{f}>0$ means that the RKHS
is well-suited for capturing $f$ (Durand et al., 2018).

Due to the episodic nature of the problem, we follow the batch analysis from
Desautels et al. (2014) and generalize it to the MDP setting with multiple
outputs. In particular, we observe $H$ transitions per episode and at the
beginning of each episode we use the model to make decisions for other $H$
steps. To extend to multiple outputs we build $p$ copies of the dataset such
that
$\mathcal{D}_{1:t,i}=\left\\{(\mathbf{s}_{t^{\prime},h},\mathbf{a}_{t^{\prime},h},\bar{\mathbf{a}}_{t^{\prime},h}),\mathbf{s}_{t^{\prime},h+1,i}\right\\}_{h=0,t^{\prime}=1}^{H-1,t}$,
each with $tH$ transitions. I.e., the $i$-th dataset has as covariates the
state-action-adversarial action and as target the $i$-th coordinate of the
next-state. We denote the covariates
$z_{t,h}\equiv(\mathbf{s}_{t,h},\mathbf{a}_{t,h},\bar{\mathbf{a}}_{t,h})$ and
the targets as $y_{t,h,i}\equiv\mathbf{s}_{t^{\prime},h+1,i}$. Finally, we
build $p$ models as

$\displaystyle\mu_{t}(z,i)$ $\displaystyle=k_{t}(z)^{\top}(K_{t}+\lambda
I)^{-1}y_{1:Ht,i},$ (31a) $\displaystyle k_{t}(z,z^{\prime},i)$
$\displaystyle=k(z,z^{\prime})-k_{t}(z)^{\top}(K_{t}+\lambda
I)^{-1}k_{t}(z^{\prime}),$ (31b) $\displaystyle\sigma_{t}^{2}(z,i)$
$\displaystyle=k_{t}(z,z),$ (31c) where $\mathbf{s}^{\prime}_{1:Ht,i}$ is the
column vector of the $i$-th coordinate of all the next-states in the dataset,
$K_{t}$ is the kernel matrix, $I$ is the identity matrix of appropriate
dimensions and we use $\lambda=pH$ as the same data is used in all the $p$
models.

Stacking together the posterior mean and variance into column vectors we get:

$\displaystyle\bm{\mu}_{t}(z)$
$\displaystyle=\left[\mu_{t}(z,1),\ldots,\mu_{t}(z,p)\right]^{\top},$ (31d)
$\displaystyle\bm{\sigma}_{t}(z)$
$\displaystyle=\left[\sigma_{t}^{2}(z,1),\ldots,\sigma_{t}^{2}(z,p)\right]^{\top}.$
(31e)

A key quantity that we consider in this work is the _(maximum) information
gain_ that measures the information about the true dynamics $f$ by observing
$n$ transitions.

######  Definition 1 (Information Gain (Cover & Thomas, 1991; Srinivas et al.,
2010; Durand et al., 2018)).

The information gain is the mutual information between the true function $f$
and a set of observations at locations $Z$ and is the difference between the
entropy of such observations and the conditional entropy of the observations
given the funciton values i.e.,

$I(f_{Z};y_{Z})=H(y_{Z})-H(y_{Z}|f_{Z}),$ (32a)

where $f_{Z}$ is the noise-free evaluation of $f$ at $Z$ and $y_{Z}$ is the
noisy observation. In the case of GP models as in Eq. 31, the information gain
is:

$I(f_{Z};y_{Z})=\frac{1}{2}\sum_{k=1}^{n}\ln(1+\lambda^{-1}\sigma^{2}_{k-1}(z_{k})).$
(32b)

Next, we introduce the maximum information gain, which is a parameter that
quantifies how hard the learning problem is and tightly upper bounds the
effective-dimensionality of the problem (Valko et al., 2013).

######  Definition 2 (Maximum Information Gain (Srinivas et al., 2010)).

The maximum information gain is the maximum of the information gain, taken
over all datasets with a fixed size $n$, i.e.,

$\gamma_{n}(k;Z)\coloneqq\max_{Z\subset\mathcal{Z},|Z|=n}I(f_{z};y_{z}).$
(33a) In the particular case of GP models, this reduces to:
$\gamma_{n}(f;Z)=\max_{\left\\{z_{1},\ldots,z_{n}\right\\}\subset\mathcal{Z}}\frac{1}{2}\sum_{k=1}^{n}\ln(1+\lambda^{-1}\sigma^{2}_{k-1}(z_{k})).$
(33b)

(Srinivas et al., 2010) show that the Maximum Information Gain (MIG) is sub-
linear in the number of observations for commonly used kernels. The main idea
now is to bound the complexity measure $\Gamma_{T}$ defined in Equation 9 in
terms of the MIG and, for commonly used kernels, we achieve no-regret
algorithms. Towards this end, we recall two results related to GP-models in
Lemma 6.

######  Lemma 6.

Posterior variance bound (Chowdhury & Gopalan, 2019) Let
$k:\mathcal{Z}\times\mathcal{Z}\to\mathbb{R}$ be a symmetric positive semi-
definite kernel with bounded variance, i.e., $k(z,z)\leq 1,\forall
z\in\mathcal{Z}$ and $f\sim GP_{\mathcal{Z}}(0,k)$ be a sample from the
associated Gaussian process, then for all $n\geq 1$ and $z\in\mathcal{Z}$:

$\displaystyle\sigma_{n-1}^{2}(z)$
$\displaystyle\leq(1+\lambda^{-1})\sigma_{n}^{2}(z),$ (34a)
$\displaystyle\sum_{k=1}^{n}\sigma_{k-1}^{2}(z_{k})$
$\displaystyle\leq(1+2\lambda)\sum_{k=1}^{n}\frac{1}{2}\ln\left[1+\lambda^{-1}\sigma_{k-1}(z_{k})\right]=(1+2\lambda)I(f_{Z};y_{Z}).$
(34b)

###### Proof.

See (Chowdhury & Gopalan, 2019, Lemma 2) ∎

Although the left-hand-side in Eq. 34b has the flavor of the complexity
measure $\Gamma_{T}$ defined in Equation 9 it is not exactly the same as we
only update the posterior once every $Hp$ observations. This is related to the
batch setting analyzed in Desautels et al. (2014). The next lemma bounds the
sum of posterior variances in terms of the information gain.

######  Lemma 7.

Complexity measure $\Gamma_{T}$ is upper bounded by MIG Let
$k:\mathcal{Z}\times\mathcal{Z}\to\mathbb{R}$ be a symmetric positive semi-
definite kernel with bounded variance, i.e., $k(z,z)\leq 1,\forall
z\in\mathcal{Z}$ and $f\sim GP_{\mathcal{Z}}(0,k)$ be a sample from the
associated Gaussian process, then for all $t\geq 1$ and $z\in\mathcal{Z}$ for
the GP-model given in Eq. 31 with $\lambda=Hp$ we have that:

$\Gamma_{t}\leq 2epH\gamma_{pHt}(k,\mathcal{Z})$ (35)

###### Proof.

The proof is based on Chowdhury & Gopalan (2019, Lemma 11) and adapted to our
setting.

$\displaystyle\sum_{t=1}^{T}\sum_{(\mathbf{s},\mathbf{a},\bar{\mathbf{a}})\in\tilde{\mathcal{D}}_{t}}\|\bm{\sigma}_{t-1}(\mathbf{s},\mathbf{a},\bar{\mathbf{a}})\|^{2}_{2}$
$\displaystyle=\sum_{t^{\prime}=1}^{t}\sum_{h=0}^{H-1}\sum_{i=1}^{p}\sigma^{2}_{(t^{\prime}-1)Hp}(z_{t^{\prime},h,i})$
(36a)
$\displaystyle\leq\sum_{t^{\prime}=1}^{t}\sum_{h=0}^{H-1}\sum_{i=1}^{p}(1+\lambda^{-1})^{ph+i-1}\sigma^{2}_{(t^{\prime}-1)Hp+hp+i}(z_{t^{\prime},h,i})$
(36b)
$\displaystyle\leq(1+\lambda^{-1})^{p(H-1)+p-1}\sum_{t^{\prime}=1}^{t}\sum_{h=0}^{H-1}\sum_{i=1}^{p}\sigma^{2}_{(t^{\prime}-1)Hp+hp+i}(z_{t^{\prime},h,i})$
(36c) $\displaystyle\leq(1+\lambda^{-1})^{pH-1}(2\lambda+1)I(f_{Z};y_{Z})$
(36d) $\displaystyle\leq 2epHI(f_{Z};y_{Z})$ (36e)

Here, equality (36a) is the definition of the 2-norm; inequality (36b) is due
to Eq. 34a in Lemma 6; inequality (36c) is due to $1+\lambda^{-1}\geq 1$;
inequality (36d) is due to Eq. 34b in Lemma 6; finally the last inequality
(36e) is due to $(1+\lambda^{-1})^{\lambda}\leq e$ and
$(1+\lambda^{-1})^{-1}(2\lambda+1)\leq 2\lambda$. The statement follows by
taking the maximum over data sets. ∎

Next, we will show that GP models are calibrated and satisfy Assumption 2.

######  Lemma 8.

Concentration of an RKHS member (Durand et al., 2018, Theorem 1) Given
Assumption 1, $\|f\|_{\mathcal{K}}\leq B_{f}$, and $k(\cdot,\cdot)\leq 1$,
then, for all $\delta\in[0,1]$, which probability at least $1-\delta$, it
holds simultaneously over all $z\in Z$ and $t\geq 0$,

$|f(z)-\mu_{t}(z)|\leq\left(B_{f}+\frac{\sigma}{\lambda}\sqrt{2\ln(1/\delta)+2\gamma_{t}}\right)\sigma_{t}(z),$
(37)

where $\mu_{t}(z)$ and $\sigma_{t}(z)$ are given by Eq. 31a and Eq. 31c.

Thus we know that, using
$\beta_{t}=\left(B_{f}+\frac{\sigma}{\lambda}\sqrt{2\ln(1/\delta)+2\gamma_{t}}\right)$,
Assumption 1 holds for a single dimension. The extension to multiple
dimensions is straightforward and has been done by (Chowdhury & Gopalan, 2019,
Lemma 10) and (Curi et al., 2020a, Lemma 11), using $\lambda\leftarrow Hp$ and
$t\leftarrow tHp$.

Putting together results of the previous sections, we know by Lemma 8 that,
under Assumption 1 and $\|f\|_{\mathcal{K}}$, GP models satisfy Assumption 2.
Furthermore, by Lemma 13 in Appendix G of Curi et al. (2020a), we now that
such models also satisfy Assumption 3. The remaining condition is that the
results in previous sections assume that the domain is bounded. However, under
Assumption 1 this is not true. Fortunately, Curi et al. (2020a) prove in
Appendix I that the domain is bounded with high-probability. Furthermore, they
prove that the MIG of kernels only increases poly-logarithmically, which does
not affect the regret bounds in this paper.

##  Appendix D Extended Experimental Results

In this section, we detail the experimental procedures for completeness. We
first detail how we learn the dynamical model using an ensemble of neural
networks in Section D.1 as it is common to all experiments. We then detail the
inverted pendulum experiment from Section 1 in Section D.2. We describe the
adversarial-robust experiment in Section D.3, the action-robust experiment in
Section D.4, and the parameter-robust experiment in Section D.5. All
experiments where run with 18-core Intel Xeon E5-2697v4 processors.

###  D.1 Model Learning and Calibration

To learn the dynamics, we use a probabilistic ensemble with five heads as in
Chua et al. (2018). The model predicts the change in state, i.e,
$\delta_{h}=\mathbf{s}_{h+1}-\mathbf{s}_{h}$ and we normalize the states,
actions and change in next-states, with the running mean and standard
deviation, similar in nature to van Hasselt et al. (2016). After each episode,
we split the data into a train and validation set with a 0.9/0.1 ratio. For
each ensemble member, we also sample a weight to simulate bootstrapping as in
Osband et al. (2016). Finally, each model is trained minimizing the negative
log-likelihood of a Gaussian distribution. We train for 20 epochs and early
stop if the prediction mean-squared-error when the epoch-loss on a validation
set is $10\%$ larger than the minimum epoch-loss in the same validation set.
After training, we recalibrate on the validation set using temperature
scaling. In particular, we use binary search to find the best parameter in the
interval $[0.01,100]$ that minimizes the expected calibration error (Malik et
al., 2019).

###  D.2 Inverted Pendulum Swing-Up Task

The pendulum swing up task has a reward function given by
$r(\mathbf{s},\mathbf{a})=-(\theta^{2}+0.1*\dot{\theta}^{2})$, where $\theta$
is the angle and $\dot{\theta}$ is the angular velocity. The Pendulum always
starts from $\theta=\pi$ in the bottom down position and the goal is to swing
the pendulum to the top-up position at $\theta=0$. Crucially, the initial
distribution is a dirac-distribution located at $\theta=\pi$, i.e., it does
not have enough coverage for algorithms to explore with it.

#### Adversarial-Robust.

In this setting, the adversary can change the relative gravity and the
relative mass of the environment at every episode between
$[1-\alpha,1+\alpha]$, for varying $\alpha$. We train RH-UCRL for 200
episodes, H-UCRL with the nominal gravity and mass for 200 episodes, and the
baseline in this setting is RARL, which we train for 1000 episodes. To
evaluate the robust performance, we train SAC for 200 episodes, fixing the
agent policy of the algorithms.

#### Action-Robust.

In this setting, the action is a mixture sampled with probability $\alpha$ of
the learner and the adversary, i.e., the adversary only affects the input
torque to the pendulum. The training and evaluation procedure is the same as
in the adversarial robust setting. The baseline in this setting is AR-DDPG,
which we train for 200 episodes.

#### Parameter-Robust.

In this setting, we consider robustness to mass change. Compared to the
adversarial-robust setting, here the adversary is only allowed to change the
mass once per episode. In this setting, H-UCRL is trained for 200 episodes
with the nominal mass, and then it is evaluated for varying masses. RH-UCRL
and the baseline, EP-Opt are allowed to change the mass also during training.
In this setting, there is no worst-case adversary during evaluation.

###  D.3 Adversarial-Robust RL

Next we detail the environments, the training and evaluation procedure, and
the hyper-parameters in different paragraphs.

#### Environments.

For the Half-Cheetah environment, the adversary acts on the torso, the front
foot and the back foot. For the Hopper environment, the adversary acts on the
torso. For the Inverted Pendulum, the adversary acts on the pole. The Inverted
Pendulum task is different here as it starts from a perturbation of the top-up
position and the task is to stabilize the pendulum. For the Reacher2d
environment, the adversary acts on the body0 link. For the Swimmer, the
adversary acts on the torso. For the Walker, the adversary acts on the torso.
For all environments, we use the adversarial input magnitude
$\bar{\mathcal{A}}=[-10,10]^{{\bar{q}}}$, where ${\bar{q}}$ is environment
dependent.

#### Training and Evaluation.

We train RH-UCRL, BestResponse, MaxiMin-MB, MaxiMin-MF with in an adversarial
environment for 200 episodes. We train RARL and RAP for 1000 episodes in an
adversarial environment. Finally, we train H-UCRL for 200 episodes in a
standard environment.To evaluate the robust performance of each algorithm, we
freeze the output policy of the training step and train an adversary using SAC
for 200 episodes. We perform five independent runs and report the mean and
standard deviation over the runs.

#### Algorithm Hyper-Parameters.

For RH-UCRL and its variants, we fix $\beta=1.0$, we train every time step and
do two gradient steps with Adam (Kingma & Ba, 2014) with learning rate
$=3\times 10^{-4}$. To compute a policy gradient, we take pathwise derivatives
of a learned critic using the learned model for 3 time steps and weight each
estimates using td-$\lambda$, with $\lambda=0.1$ (Sutton & Barto, 2018). We
also add entropy regularization with parameter $0.2$. We did not do hyper
parameter search, but rather use the software default values. For RARL and
RAP, we use the PPO algorithm from Schulman et al. (2017) as this performed
better than TRPO from Schulman et al. (2015). We train PPO after collecting a
batch of 4 episodes, for 80 gradient steps, using early stopping once the KL
divergence between the initial and the current policy is more than $0.0075$.

###  D.4 Action-Robust RL

We use the noisy robust setting from Tessler et al. (2019) with mixture
parameter $\alpha=0.3$. The training and evaluation procedures, as well as the
hyperparameters, are identical to the adversarial-robust experiment. The
baseline is AR-DDPG that Tessler et al. (2019) propose.

###  D.5 Parameter-Robust

In this setting, we are robust to a relative mass change, i.e., when the
relative mass equals one, then the environment has the nominal mass. For all
environments except for the Swimmer, the relative mass is bounded in the
interval $[0.001,2]$. For the Swimmer, there were numerical errors due to ill-
conditioned mass in the simulator, so we limit the range to $[0.5,1.5]$.

We train RH-UCRL, BestResponse, MaxiMin-MB, MaxiMin-MF with in an adversary
that is allowed to select the worst-case mass from within the range for 200
episodes. We train the baselines, DomainRandomization and EPOpt for 1000
episodes as they were also based on PPO. Finally, we train H-UCRL for 200
episodes in a standard environment. To evaluate the performance of each
algorithm, we evaluate the different relative masses in the interval and do
five independent runs. We report the mean and standard deviation over the
runs.