# Twice regularized MDPs and the equivalence between robustness and
regularization

Esther Derman
Technion &Matthieu Geist
Google Research, Brain Team &Shie Mannor
Technion, NVIDIA Research Contact author<EMAIL_ADDRESS>
###### Abstract

Robust Markov decision processes (MDPs) aim to handle changing or partially
known system dynamics. To solve them, one typically resorts to robust
optimization methods. However, this significantly increases computational
complexity and limits scalability in both learning and planning. On the other
hand, regularized MDPs show more stability in policy learning without
impairing time complexity. Yet, they generally do not encompass uncertainty in
the model dynamics. In this work, we aim to learn robust MDPs using
regularization. We first show that regularized MDPs are a particular instance
of robust MDPs with uncertain reward. We thus establish that policy iteration
on reward-robust MDPs can have the same time complexity as on regularized
MDPs. We further extend this relationship to MDPs with uncertain transitions:
this leads to a regularization term with an additional dependence on the value
function. We finally generalize regularized MDPs to twice regularized MDPs (R2
MDPs), i.e., MDPs with both value and policy regularization. The corresponding
Bellman operators enable developing policy iteration schemes with convergence
and robustness guarantees. It also reduces planning and learning in robust
MDPs to regularized MDPs.

##  1 Introduction

MDPs provide a practical framework for solving sequential decision problems
under uncertainty [30]. However, the chosen strategy can be very sensitive to
sampling errors or inaccurate model estimates. This can lead to complete
failure in common situations where the model parameters vary adversarially or
are simply unknown [22]. Robust MDPs aim to mitigate such sensitivity by
assuming that the transition and/or reward function $(P,r)$ varies arbitrarily
inside a given _uncertainty set_ $\mathcal{U}$ [17, 27]. In this setting, an
optimal solution maximizes a performance measure under the worst-case
parameters. It can be thought of as a dynamic zero-sum game with an agent
choosing the best action while Nature imposes it the most adversarial model.
As such, solving robust MDPs involves max-min problems, which can be
computationally challenging and limits scalability.

In recent years, several methods have been developed to alleviate the
computational concerns raised by robust reinforcement learning (RL). Apart
from [23, 24] that consider specific types of coupled uncertainty sets, all
rely on a rectangularity assumption without which the problem can be NP-hard
[2, 40]. This assumption is key to deriving tractable solvers of robust MDPs
such as robust value iteration [2, 11] or more general robust modified policy
iteration (MPI) [18]. Yet, reducing time complexity in robust Bellman updates
remains challenging and is still researched today [15, 11].

At the same time, the empirical success of regularization in policy search
methods has motivated a wide range of algorithms with diverse motivations such
as improved exploration [12, 20] or stability [34, 13]. Geist et al. [10]
proposed a unified view from which many existing algorithms can be derived.
Their regularized MDP formalism opens the path to error propagation analysis
in approximate MPI [33] and leads to the same bounds as for standard MDPs.
Nevertheless, as we further show in Sec. 3, policy regularization accounts for
reward uncertainty only: it does not encompass uncertainty in the model
dynamics. Despite a vast literature on _how_ regularized policy search works
and convergence rates analysis [36, 5], little attention has been given to
understanding _why_ it can generate strategies that are robust to external
perturbations [13].

To our knowledge, the only works that relate robustness to regularization in
RL are [6, 16, 9]. Derman & Mannor [6] employ a distributionally robust
optimization approach to regularize an empirical value function.
Unfortunately, computing this empirical value necessitates several policy
evaluation procedures, which is quickly unpractical. Husain et al. [16]
provide a dual relationship with robust MDPs under uncertain reward. Their
duality result applies to general regularization methods and gives a robust
interpretation of soft-actor-critic [13]. Although these two works justify the
use of regularization for ensuring robustness, they do not enclose any
algorithmic novelty. Similarly, Eysenbach & Levine [9] specifically focus on
maximum entropy methods and relate them to either reward or transition
robustness. We shall further detail on these most related studies in Sec. 7.

The robustness-regularization duality is well established in statistical
learning theory [41, 35, 19], as opposed to RL theory. In fact, standard
setups such as classification or regression may be considered as single-stage
decision-making problems, i.e., one-step MDPs, a particular case of RL
setting. Extending this robustness-regularization duality to RL would yield
cheaper learning methods with robustness guarantees. As such, we introduce a
regularization function $\Omega_{\mathcal{U}}$ that depends on the uncertainty
set $\mathcal{U}$ and is defined over both policy and value spaces, thus
inducing a _twice regularized_ Bellman operator (see Sec. 5). We show that
this regularizer yields an equivalence of the form
$v_{\pi,\mathcal{U}}=v_{\pi,\Omega_{\mathcal{U}}}$, where
$v_{\pi,\mathcal{U}}$ is the robust value function for policy $\pi$ and
$v_{\pi,\Omega_{\mathcal{U}}}$ the regularized one. This equivalence is
derived through the objective function each value optimizes. More concretely,
we formulate the robust value function $v_{\pi,\mathcal{U}}$ as an optimal
solution of the robust optimization problem:

$\displaystyle\max_{v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}}\langle
v,\mu_{0}\rangle\text{ s. t.
}v\leq\inf_{(P,r)\in\mathcal{U}}T_{(P,r)}^{\pi}v,$ (RO)

where $T_{(P,r)}^{\pi}$ is the evaluation Bellman operator [30]. Then, we show
that $v_{\pi,\mathcal{U}}$ is also an optimal solution of the convex (non-
robust) optimization problem:

$\displaystyle\max_{v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}}\langle
v,\mu_{0}\rangle\text{ s. t. }v\leq
T_{(P_{0},r_{0})}^{\pi}v-\Omega_{\mathcal{U}}(\pi,v),$ (CO)

where $(P_{0},r_{0})$ is the _nominal model_. This establishes equivalence
between the two optimization problems. Moreover, the inequality constraint of
(CO) enables to derive a _twice regularized_ (R2) Bellman operator defined
according to $\Omega_{\mathcal{U}}$, a policy and value regularizer. For ball-
constrained uncertainty sets, $\Omega_{\mathcal{U}}$ has an explicit form and
under mild conditions, the corresponding R2 Bellman operators are contracting.
The equivalence between the two problems (RO) and (CO) together with the
contraction properties of R2 Bellman operators enable to circumvent robust
optimization problems at each Bellman update. As such, it alleviates robust
planning and learning algorithms by reducing them to regularized ones, which
are known to be as complex as classical methods.

To summarize, we make the following contributions: (i) We show that
regularized MDPs are a specific instance of robust MDPs with uncertain reward.
Besides formalizing a general connection between the two settings, our result
enables to explicit the uncertainty sets induced by standard regularizers.
(ii) We extend this duality to MDPs with uncertain transition and provide the
first regularizer that recovers robust MDPs with $s$-rectangular balls and
arbitrary norm. (iii) We introduce twice regularized MDPs (R2 MDPs) that apply
both policy and value regularization to retrieve robust MDPs. We establish
contraction of the corresponding Bellman operators. This leads us to proposing
an R2 MPI algorithm with similar time complexity as vanilla MPI, thus opening
new perspectives towards practical and scalable robust RL.

Notations.  We designate the extended reals by
$\overline{\operatorname{\mathbb{R}}}:=\\{-\infty,\infty\\}$. Given a finite
set $\operatorname{\mathcal{Z}}$, the class of real-valued functions (resp.
probability distributions) over $\operatorname{\mathcal{Z}}$ is denoted by
$\operatorname{\mathbb{R}}^{\operatorname{\mathcal{Z}}}$ (resp.
$\Delta_{\operatorname{\mathcal{Z}}}$), while the constant function equal to 1
over $\operatorname{\mathcal{Z}}$ is denoted by
$\mathbbm{1}_{\operatorname{\mathcal{Z}}}$. Similarly, for any set
$\mathcal{X}$, $\Delta_{\operatorname{\mathcal{Z}}}^{\mathcal{X}}$ denotes the
class of functions defined over $\operatorname{\mathcal{X}}$ and valued in
$\Delta_{\operatorname{\mathcal{Z}}}$. The inner product of two functions
$\operatorname{\mathbf{a}},\operatorname{\mathbf{b}}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{Z}}}$
is defined as
$\langle\operatorname{\mathbf{a}},\operatorname{\mathbf{b}}\rangle:=\sum_{z\in\operatorname{\mathcal{Z}}}\operatorname{\mathbf{a}}(z)\operatorname{\mathbf{b}}(z)$,
which induces the $\ell_{2}$-norm
$\lVert\operatorname{\mathbf{a}}\rVert:=\sqrt{\langle\operatorname{\mathbf{a}},\operatorname{\mathbf{a}}\rangle}$.
The $\ell_{2}$-norm coincides with its dual norm, i.e.,
$\lVert\operatorname{\mathbf{a}}\rVert=\max_{\lVert\operatorname{\mathbf{b}}\rVert\leq
1}\langle\operatorname{\mathbf{a}},\operatorname{\mathbf{b}}\rangle=:\lVert\operatorname{\mathbf{a}}\rVert_{*}$.
Let a function
$f:\operatorname{\mathbb{R}}^{\operatorname{\mathcal{Z}}}\to\overline{\operatorname{\mathbb{R}}}$.
The Legendre-Fenchel transform (or convex conjugate) of $f$ is
$f^{*}(\operatorname{\mathbf{y}}):=\max_{\operatorname{\mathbf{a}}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{Z}}}}\\{\langle\operatorname{\mathbf{a}},\operatorname{\mathbf{y}}\rangle-f(\operatorname{\mathbf{a}})\\}.$
Given a set
$\mathfrak{Z}\subseteq\operatorname{\mathbb{R}}^{\operatorname{\mathcal{Z}}}$,
the characteristic function
$\delta_{\mathfrak{Z}}:\operatorname{\mathbb{R}}^{\operatorname{\mathcal{Z}}}\to\overline{\operatorname{\mathbb{R}}}$
is $\delta_{\mathfrak{Z}}(\operatorname{\mathbf{a}})=0$ if
$\operatorname{\mathbf{a}}\in\mathfrak{Z}$; $+\infty$ otherwise. The Legendre-
Fenchel transform of $\delta_{\mathfrak{Z}}$ is the support function
$\sigma_{\mathfrak{Z}}(\operatorname{\mathbf{y}})=\max_{\operatorname{\mathbf{a}}\in\mathfrak{Z}}\langle\operatorname{\mathbf{a}},\operatorname{\mathbf{y}}\rangle$
[3, Ex. 1.6.1].

##  2 Preliminaries

This section describes the background material that we use throughout our
work. Firstly, we recall useful properties in convex analysis. Secondly, we
address classical discounted MDPs and their linear program (LP) formulation.
Thirdly, we briefly detail on regularized MDPs and the associated operators
and lastly, we focus on the robust MDP setting.

#### Convex Analysis.

Let $\Omega:\Delta_{\operatorname{\mathcal{Z}}}\to\operatorname{\mathbb{R}}$
be a strongly convex function. Throughout this study, the function $\Omega$
plays the role of a policy and/or value regularization function. Its Legendre-
Fenchel transform $\Omega^{*}$ satisfies several smoothness properties, hence
its alternative name "smoothed max operator" [25]. Our work makes use of the
following result [14, 25].

######  Proposition 2.1.

Given $\Omega:\Delta_{\operatorname{\mathcal{Z}}}\to\operatorname{\mathbb{R}}$
strongly convex, the following properties hold:
(i) $\nabla\Omega^{*}$is Lipschitz and satisfies
$\nabla\Omega^{*}(\operatorname{\mathbf{y}})=\arg\max_{\operatorname{\mathbf{a}}\in\Delta_{\operatorname{\mathcal{Z}}}}\langle\operatorname{\mathbf{a}},\operatorname{\mathbf{y}}\rangle-\Omega(\operatorname{\mathbf{a}}),\forall\operatorname{\mathbf{y}}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{Z}}}$.
(ii) For any
$c\in\operatorname{\mathbb{R}},\operatorname{\mathbf{y}}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{Z}}}$,
$\Omega^{*}(\operatorname{\mathbf{y}}+c\mathbbm{1}_{\operatorname{\mathcal{Z}}})=\Omega^{*}(\operatorname{\mathbf{y}})+c.$
(iii) The Legendre-Fenchel transform $\Omega^{*}$ is non-decreasing.

#### Discounted MDPs and LP formulation.

Consider an infinite horizon MDP
$(\operatorname{\mathcal{S}},\operatorname{\mathcal{A}},\mu_{0},\gamma,P,r)$
with $\operatorname{\mathcal{S}}$ and $\operatorname{\mathcal{A}}$ finite
state and action spaces respectively,
$0<\mu_{0}\in\Delta_{\operatorname{\mathcal{S}}}$ an initial state
distribution and $\gamma\in(0,1)$ a discount factor. Denoting
$\operatorname{\mathcal{X}}:=\operatorname{\mathcal{S}}\times\operatorname{\mathcal{A}}$,
$P\in\Delta_{\operatorname{\mathcal{S}}}^{\operatorname{\mathcal{X}}}$ is a
transition kernel mapping each state-action pair to a probability distribution
over $\operatorname{\mathcal{S}}$ and
$r\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}$ is a reward
function. A policy
$\pi\in\Delta_{\operatorname{\mathcal{A}}}^{\operatorname{\mathcal{S}}}$ maps
any state $s\in\operatorname{\mathcal{S}}$ to an action distribution
$\pi_{s}\in\Delta_{\operatorname{\mathcal{A}}}$, and we evaluate its
performance through the following measure:

$\displaystyle\rho(\pi):=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})\biggm{|}\mu_{0},\pi,P\right]=\langle
v_{(P,r)}^{\pi},\mu_{0}\rangle.$ (1)

Here, the expectation is conditioned on the process distribution determined by
$\mu_{0},\pi$ and $P$, and for all $s\in\operatorname{\mathcal{S}},$
$v_{(P,r)}^{\pi}(s)=\mathbb{E}[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})|s_{0}=s,\pi,P]$
is the _value function_ at state $s$. Maximizing (1) defines the standard RL
objective, which can be solved thanks to the Bellman operators:

$\begin{split}T^{\pi}_{(P,r)}v&:=r^{\pi}+\gamma P^{\pi}v\quad\forall
v\in\mathbb{R}^{\operatorname{\mathcal{S}}},\pi\in\Delta_{\operatorname{\mathcal{A}}}^{\operatorname{\mathcal{S}}},\\\
T_{(P,r)}v&:=\max_{\pi\in\Delta_{\operatorname{\mathcal{A}}}^{\operatorname{\mathcal{S}}}}T^{\pi}_{(P,r)}v\quad\forall
v\in\mathbb{R}^{\operatorname{\mathcal{S}}},\\\
\mathcal{G}_{(P,r)}(v)&:=\\{\pi\in\Delta_{\operatorname{\mathcal{A}}}^{\operatorname{\mathcal{S}}}:T^{\pi}_{(P,r)}v=T_{(P,r)}v\\}\quad\forall
v\in\mathbb{R}^{\operatorname{\mathcal{S}}},\end{split}$

where
$r^{\pi}:=[\langle\pi_{s},r(s,\cdot)\rangle]_{s\in\operatorname{\mathcal{S}}}$
and
$P^{\pi}=[P^{\pi}(s^{\prime}|s)]_{s^{\prime},s\in\operatorname{\mathcal{S}}}$
with $P^{\pi}(s^{\prime}|s):=\langle\pi_{s},P(s^{\prime}|s,\cdot)\rangle.$
Both $T^{\pi}_{(P,r)}$ and $T_{(P,r)}$ are $\gamma$-contractions with respect
to (w.r.t.) the supremum norm, so each admits a unique fixed point
$v^{\pi}_{(P,r)}$ and $v^{*}_{(P,r)}$, respectively. The set of greedy
policies w.r.t. value $v$ defines $\mathcal{G}_{(P,r)}(v)$, and any policy
$\pi\in\mathcal{G}_{(P,r)}(v^{*}_{(P,r)})$ is optimal [30]. For all
$v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}$, the associated
function $q\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}$ is given
by $q(s,a)=r(s,a)+\gamma\langle
P(\cdot|s,a),v\rangle\quad\forall(s,a)\in\operatorname{\mathcal{X}}$. In
particular, the fixed point $v^{\pi}_{(P,r)}$ satisfies
$v^{\pi}_{(P,r)}=\langle\pi_{s},q^{\pi}_{(P,r)}(s,\cdot)\rangle$ where
$q^{\pi}_{(P,r)}$ is its associated $q$-function.

The problem in (1) can also be formulated as an LP [30]. Given a policy
$\pi\in\Delta_{\operatorname{\mathcal{A}}}^{\operatorname{\mathcal{S}}}$, we
characterize its performance $\rho(\pi)$ by the following $v$-LP [30, 26]:

$\min_{v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}}\langle
v,\mu_{0}\rangle\text{ subject to (s.t.) }v\geq r^{\pi}+\gamma P^{\pi}v.$ (Pπ)

This primal objective provides a policy view on the problem. Alternatively,
one may take a state visitation perspective by studying the dual objective
instead:

$\displaystyle\max_{\mu\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}}\langle
r^{\pi},\mu\rangle\text{ s. t. }\mu\geq 0\text{ and
}(\mathbf{Id}_{\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}}-\gamma
P_{*}^{\pi})\mu=\mu_{0},$ (Dπ)

where $P_{*}^{\pi}$ is the _adjoint policy transition operator_ 111It is the
adjoint operator of $P^{\pi}$ in the sense that $\langle
P^{\pi}v,v^{\prime}\rangle=\langle v,P_{*}^{\pi}v^{\prime}\rangle\quad\forall
v,v^{\prime}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}$.:
$[P_{*}^{\pi}\mu](s):=\sum_{\bar{s}\in\operatorname{\mathcal{S}}}P^{\pi}(s|\bar{s})\mu(\bar{s})\quad\forall\mu\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}},$
and $\mathbf{Id}_{\operatorname{\mathcal{S}}}$ is the identity function in
$\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}$. Let
$\mathbf{I}(s^{\prime}|s,a):=\delta_{s^{\prime}=s}\quad\forall(s,a,s^{\prime})\in\operatorname{\mathcal{X}}\times\operatorname{\mathcal{S}}$
the trivial transition matrix and define its _adjoint transition operator_ as
$\mathbf{I}_{*}\mu(s):=\sum_{(\bar{s},\bar{a})\in\operatorname{\mathcal{X}}}\mathbf{I}(s|\bar{s},\bar{a})\mu(\bar{s},\bar{a})\quad\forall
s\in\operatorname{\mathcal{S}}$. The correspondence between occupancy measures
and policies lies in the one-to-one mapping
$\mu\mapsto\frac{\mu(\cdot,\cdot)}{\mathbf{I}_{*}\mu(\cdot)}=:\pi_{\mu}$ and
its inverse $\pi\mapsto\mu_{\pi}$ given by

$\mu_{\pi}(s,a):=\sum_{t=0}^{\infty}\gamma^{t}\mathbb{P}\left(s_{t}=s,a_{t}=a\biggr{|}\mu_{0},\pi,P\right)\quad\forall(s,a)\in\operatorname{\mathcal{X}}.$

As such, one can interchangeably work with the primal LP (Pπ) or the dual
(Dπ).

#### Regularized MDPs.

A regularized MDP is a tuple
$(\operatorname{\mathcal{S}},\operatorname{\mathcal{A}},\mu_{0},\gamma,P,r,\Omega)$
with
$(\operatorname{\mathcal{S}},\operatorname{\mathcal{A}},\mu_{0},\gamma,P,r)$
an infinite horizon MDP as above, and
$\Omega:=(\Omega_{s})_{s\in\operatorname{\mathcal{S}}}$ a finite set of
functions such that for all $s\in\operatorname{\mathcal{S}}$,
$\Omega_{s}:\Delta_{\operatorname{\mathcal{A}}}\to\operatorname{\mathbb{R}}$
is strongly convex. Each function $\Omega_{s}$ plays the role of a policy
regularizer $\Omega_{s}(\pi_{s})$. With a slight abuse of notation, we shall
denote by
$\Omega(\pi):=(\Omega_{s}(\pi_{s}))_{s\in\operatorname{\mathcal{S}}}$ the
family of state-dependent regularizers.222In the formalism of Geist et al.
[10], $\Omega_{s}$ is initially constant over $\operatorname{\mathcal{S}}$.
However, later in the paper [10, Sec. 5], it changes according to policy
iterates. Here, we alternatively define a family $\Omega$ of state-dependent
regularizers, which accounts for state-dependent uncertainty sets (see Sec. 5
below). The regularized Bellman evaluation operator is given by

$\displaystyle[T^{\pi,\Omega}_{(P,r)}v](s):=T^{\pi}_{(P,r)}v(s)-\Omega_{s}(\pi_{s})\quad\forall
v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}},s\in\operatorname{\mathcal{S}},$

and the regularized Bellman optimality operator by
$T^{*,\Omega}_{(P,r)}v:=\max_{\pi\in\Delta_{\operatorname{\mathcal{A}}}^{\operatorname{\mathcal{S}}}}T^{\pi,\Omega}_{(P,r)}v\quad\forall
v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}$ [10]. The unique
fixed point of $T^{\pi,\Omega}_{(P,r)}$ (respectively $T^{*,\Omega}_{(P,r)}$)
is denoted by $v^{\pi,\Omega}_{(P,r)}$ (resp. $v^{*,\Omega}_{(P,r)}$) and
defines the _regularized value function_ (resp. _regularized optimal value
function_). Although the regularized MDP formalism stems from the
aforementioned Bellman operators in [10], it turns out that regularized MDPs
are MDPs with modified reward. Indeed, for any policy
$\pi\in\Delta_{\operatorname{\mathcal{A}}}^{\operatorname{\mathcal{S}}}$, the
regularized value function is
$v^{\pi,\Omega}_{(P,r)}=(\mathbf{I}_{\operatorname{\mathcal{S}}}-\gamma
P^{\pi})^{-1}(r^{\pi}-\Omega(\pi)),$ which corresponds to a non-regularized
value with expected reward $\tilde{r}^{\pi}:=r^{\pi}-\Omega(\pi)$. Note that
the modified reward $\tilde{r}^{\pi}(s)$ is no longer linear in $\pi_{s}$
because of the strong convexity of $\Omega_{s}$. Also, this modification does
not apply to the reward function $r$ but only to its expectation $r^{\pi}$, as
we cannot regularize the original reward without making it policy-independent.

#### Robust MDPs.

In general, the MDP model is not explicitly known but rather estimated from
sampled trajectories. As this may result in over-sensitive outcome [22],
robust MDPs reduce such performance variation. Formally, a robust MDP
$(\operatorname{\mathcal{S}},\operatorname{\mathcal{A}},\mu_{0},\gamma,\mathcal{U})$
is an MDP with uncertain model belonging to
$\mathcal{U}:=\mathcal{P}\times\mathcal{R}$, i.e., uncertain transition
$P\in\mathcal{P}\subseteq\Delta_{\operatorname{\mathcal{S}}}^{\operatorname{\mathcal{X}}}$
and reward
$r\in\mathcal{R}\subseteq\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}$
[17, 40]. The uncertainty set $\mathcal{U}$ typically controls the confidence
level of a model estimate, which in turn determines the agent’s level of
robustness. It is given to the agent, who seeks to maximize performance under
the worst-case model $(P,r)\in\mathcal{U}$. Although untractable in general,
this problem can be solved in polynomial time for _rectangular_ uncertainty
sets, i.e., when
$\mathcal{U}=\times_{s\in\operatorname{\mathcal{S}}}\mathcal{U}_{s}=\times_{s\in\operatorname{\mathcal{S}}}(\mathcal{P}_{s}\times\mathcal{R}_{s})$
[40, 23]. For any policy
$\pi\in\Delta_{\operatorname{\mathcal{A}}}^{\operatorname{\mathcal{S}}}$ and
state $s\in\operatorname{\mathcal{S}},$ the _robust value function_ at $s$ is
$v^{\pi,\mathcal{U}}(s):=\min_{(P,r)\in\mathcal{U}}v_{(P,r)}^{\pi}(s)$ and the
_robust optimal value function_
$v^{*,\mathcal{U}}(s):=\max_{\pi\in\Delta_{\operatorname{\mathcal{S}}}^{\operatorname{\mathcal{A}}}}v^{\pi,\mathcal{U}}(s)$.
Each of them is the unique fixed point of the respective robust Bellman
operators:

$\displaystyle[T^{\pi,\mathcal{U}}v](s)$
$\displaystyle:=\min_{(P,r)\in\mathcal{U}}T_{(P,r)}^{\pi}v(s)\quad\forall
v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}},s\in\operatorname{\mathcal{S}},\pi\in\Delta_{\operatorname{\mathcal{S}}}^{\operatorname{\mathcal{A}}},$
$\displaystyle[T^{*,\mathcal{U}}v](s)$
$\displaystyle:=\max_{\pi\in\Delta_{\operatorname{\mathcal{A}}}^{\operatorname{\mathcal{S}}}}[T^{\pi,\mathcal{U}}v](s)\quad\forall
v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}},s\in\operatorname{\mathcal{S}},$

which are $\gamma$-contractions. For all
$v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}$, the associated
robust $q$-function is given by
$q(s,a)=\min_{(P,r)\in\mathcal{U}}\\{r(s,a)+\gamma\langle
P(\cdot|s,a),v\rangle\\}\quad\forall(s,a)\in\operatorname{\mathcal{X}}$, so
that $v^{\pi,\mathcal{U}}=\langle\pi_{s},q^{\pi,\mathcal{U}}(s,\cdot)\rangle$
where $q^{\pi,\mathcal{U}}$ is the robust $q$-function associated to
$v^{\pi,\mathcal{U}}$.

##  3 Reward-robust MDPs

This section focuses on reward-robust MDPs, i.e., robust MDPs with uncertain
reward but known transition model. We first show that regularized MDPs
represent a particular instance of reward-robust MDPs, as both solve the same
optimization problem. This equivalence provides a theoretical motivation for
the heuristic success of policy regularization. Then, we explicit the
uncertainty set underlying some standard regularization functions, thus
suggesting an interpretable explanation of their empirical robustness.

We first show the following proposition 3.1, which applies to general robust
MDPs and random policies. It slightly extends [17], as Lemma 3.2 there focuses
on uncertain-transition MDPs and deterministic policies. For completeness, we
provide a proof of Prop. 3.1 in Appx. Proposition.

######  Proposition 3.1.

For any policy
$\pi\in\Delta_{\operatorname{\mathcal{A}}}^{\operatorname{\mathcal{S}}}$, the
robust value function $v^{\pi,\mathcal{U}}$ is the optimal solution of the
robust optimization problem:

$\displaystyle\max_{v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}}\langle
v,\mu_{0}\rangle\text{ s. t. }v\leq T_{(P,r)}^{\pi}v\text{ for all
}(P,r)\in\mathcal{U}.$ (PU)

In the robust optimization problem (PU), the inequality constraint must hold
over the whole uncertainty set $\mathcal{U}$. As such, a function
$v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}$ is said to be
_robust feasible_ for (PU) if $v\leq T_{(P,r)}^{\pi}v$ for all
$(P,r)\in\mathcal{U}$ or equivalently, if
$\max_{(P,r)\in\mathcal{U}}\\{v(s)-T_{(P,r)}^{\pi}v(s)\\}\leq 0$ for all
$s\in\operatorname{\mathcal{S}}.$ Therefore, checking robust feasibility
requires to solve a maximization problem. For properly structured uncertainty
sets, a closed form solution can be derived, as we shall see in the sequel. As
standard in the robust RL literature [32, 15, 1], the remaining of this work
focuses on uncertainty sets centered around a known _nominal model_. Formally,
given $P_{0}$ (resp. $r_{0}$) a nominal transition kernel (resp. reward
function), we consider uncertainty sets of the form
$(P_{0}+\mathcal{P})\times(r_{0}+\mathcal{R})$. The size of
$\mathcal{P}\times\mathcal{R}$ quantifies our level of uncertainty or
alternatively, the desired degree of robustness.

#### Reward-robust and regularized MDPs: an equivalence.

We now focus on reward-robust MDPs, i.e., robust MDPs with
$\mathcal{U}=\\{P_{0}\\}\times(r_{0}+\mathcal{R}).$ Thm. 3.1 establishes that
reward-robust MDPs are in fact regularized MDPs whose regularizer is given by
a support function. Its proof can be found in Appx. A.2. This result brings
two take-home messages: (i) policy regularization is equivalent to reward
uncertainty; (ii) policy iteration on reward-robust MDPs has the same
convergence rate as regularized MDPs, which in turn is the same as standard
MDPs [10].

######  Theorem 3.1 (Reward-robust MDP).

Assume that $\mathcal{U}=\\{P_{0}\\}\times(r_{0}+\mathcal{R}).$ Then, for any
policy
$\pi\in\Delta_{\operatorname{\mathcal{A}}}^{\operatorname{\mathcal{S}}}$, the
robust value function $v^{\pi,\mathcal{U}}$ is the optimal solution of the
convex optimization problem:

$\displaystyle\max_{v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}}\langle
v,\mu_{0}\rangle\text{ s. t. }v(s)\leq
T_{(P_{0},r_{0})}^{\pi}v(s)-\sigma_{\mathcal{R}_{s}}(-\pi_{s})\text{ for all
}s\in\operatorname{\mathcal{S}}.$

Thm. 3.1 clearly highlights a convex regularizer
$\Omega_{s}(\pi_{s}):=\sigma_{\mathcal{R}_{s}}(-\pi_{s})\quad\forall
s\in\operatorname{\mathcal{S}}$. We thus recover a regularized MDP by setting
$[T^{\pi,\Omega}v](s)=T_{(P_{0},r_{0})}^{\pi}v(s)-\sigma_{\mathcal{R}_{s}}(-\pi_{s})\quad\forall
s\in\operatorname{\mathcal{S}}$. In particular, when $\mathcal{R}_{s}$ is a
ball of radius $\alpha_{s}^{r}$, the support function (or regularizer) can be
written in closed form as
$\Omega_{s}(\pi_{s}):=\alpha_{s}^{r}\lVert\pi_{s}\rVert$, which is strongly
convex. We formalize this below (see proof in Appx. A.3).

######  Corollary 3.1.

Let $\pi\in\Delta_{\operatorname{\mathcal{A}}}^{\operatorname{\mathcal{S}}}$
and $\mathcal{U}=\\{P_{0}\\}\times(r_{0}+\mathcal{R})$. Further assume that
for all $s\in\operatorname{\mathcal{S}}$, the reward uncertainty set at $s$ is
$\mathcal{R}_{s}:=\\{r_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}:\lVert
r_{s}\rVert\leq\alpha_{s}^{r}\\}$. Then, the robust value function
$v^{\pi,\mathcal{U}}$ is the optimal solution of the convex optimization
problem:

$\displaystyle\max_{v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}}\langle
v,\mu_{0}\rangle\text{ s. t. }v(s)\leq
T_{(P_{0},r_{0})}^{\pi}v(s)-\alpha_{s}^{r}\lVert\pi_{s}\rVert\text{ for all
}s\in\operatorname{\mathcal{S}}.$

While regularization induces reward-robustness, Thm. 3.1 and Cor. 3.1 suggest
that, on the other hand, specific reward-robust MDPs recover well-known policy
regularization methods. In the following section, we explicit the reward-
uncertainty sets underlying some of these regularizers.

#### Related Algorithms.

Consider a reward uncertainty set of the form
$\mathcal{R}:=\times_{(s,a)\in\operatorname{\mathcal{X}}}\mathcal{R}_{s,a}$.
This defines an $(s,a)$-rectangular $\mathcal{R}$ (a particular type of
$s$-rectangular $\mathcal{R}$) whose rectangles $\mathcal{R}_{s,a}$ are
independently defined for each state-action pair. For the regularizers below,
we derive appropriate $\mathcal{R}_{s,a}$-s that recover the same regularized
value function. Detailed proofs are in Appx. A.4. There, we also include a
summary table that reviews the properties of some RL regularizers, as well as
our R2 function which we shall introduce later in Sec. 5. Note that the reward
uncertainty sets here depend on the policy. This is due to the fact that
standard regularizers are defined over the policy space and not at each state-
action pair. It similarly explains why the reward modification induced by
regularization does not apply to the original reward function, as already
mentioned in Sec. 2.

Negative Shannon entropy. Let
$\mathcal{R}_{s,a}^{\textsc{NS}}(\pi):=\left[\ln\left(\nicefrac{{1}}{{\pi_{s}(a)}}\right),+\infty\right)\quad\forall(s,a)\in\operatorname{\mathcal{X}}$.
The associated support function enables to write:

$\displaystyle\sigma_{\mathcal{R}_{s}^{\textsc{NS}}(\pi)}(-\pi_{s})=\max_{\begin{subarray}{c}r(s,\cdot):r(s,a^{\prime})\in\mathcal{R}_{s,a^{\prime}}^{\textsc{NS}}(\pi),a^{\prime}\in\operatorname{\mathcal{A}}\end{subarray}}\sum_{a\in\operatorname{\mathcal{A}}}-r(s,a)\pi_{s}(a)=\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)\ln(\pi_{s}(a)),$

where the last equality comes from maximizing $-r(s,a)$ over
$\left[\ln\left(\nicefrac{{1}}{{\pi_{s}(a)}}\right),+\infty\right)$ for each
$a\in\operatorname{\mathcal{A}}$. We thus recover the negative Shannon entropy
$\Omega(\pi_{s})=\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)\ln(\pi_{s}(a))$
[13].

Kullback-Leibler divergence. Given an action distribution
$0<d\in\Delta_{\operatorname{\mathcal{A}}}$, let
$\mathcal{R}_{s,a}^{\textsc{KL}}(\pi):=\ln\left(d(a)\right)+\mathcal{R}_{s,a}^{\textsc{NS}}(\pi)\quad\forall(s,a)\in\operatorname{\mathcal{X}}$.
It amounts to translating the interval $\mathcal{R}_{s,a}^{\textsc{NS}}$ by
the given constant. Similarly writing the support function yields
$\Omega(\pi_{s})=\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)\ln\left(\nicefrac{{\pi_{s}(a)}}{{d(a)}}\right)$,
which is exactly the KL divergence [34].

Negative Tsallis entropy. Letting
$\mathcal{R}_{s,a}^{\textsc{T}}(\pi):=\left[\nicefrac{{(1-\pi_{s}(a))}}{{2}},+\infty\right)\quad\forall(s,a)\in\operatorname{\mathcal{X}}$,
we recover the negative Tsallis entropy
$\Omega(\pi_{s})=\frac{1}{2}(\lVert\pi_{s}\rVert^{2}-1)$ [20].

#### Policy-gradient for reward-robust MDPs.

The equivalence between reward-robust and regularized MDPs leads us to wonder
whether we can employ policy-gradient [37] on reward-robust MDPs using
regularization. The following result establishes that a policy-gradient
theorem can indeed be established for reward-robust MDPs (see proof in Appx.
A.5).

######  Proposition 3.2.

Assume that $\mathcal{U}=\\{P_{0}\\}\times(r_{0}+\mathcal{R})$ with
$\mathcal{R}_{s}=\\{r_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}:\lVert
r_{s}\rVert\leq\alpha_{s}^{r}\\}$. Then, the gradient of the reward-robust
objective $J_{\mathcal{U}}(\pi):=\langle v^{\pi,\mathcal{U}},\mu_{0}\rangle$
is given by

$\displaystyle\nabla
J_{\mathcal{U}}(\pi)=\mathbb{E}_{(s,a)\sim\mu_{\pi}}\left[\nabla\ln\pi_{s}(a)\left(q^{\pi,\mathcal{U}}(s,a)-\alpha_{s}^{r}\frac{\pi_{s}(a)}{\lVert\pi_{s}\rVert}\right)\right],$

where $\mu_{\pi}$ is the occupancy measure under the nominal model $P_{0}$ and
policy $\pi$.

Although Prop. 3.2 is an application of [10, Appx. D.3] for a specific
regularized MDP, its reward-robust formulation is novel and suggests another
simplification of robust methods. Indeed, previous works that exploit policy-
gradient on robust MDPs involve the occupancy measure of the worst-case model
[21], whereas our result sticks to the nominal. In practice, Prop. 3.2 enables
to learn a robust policy by sampling transitions from the nominal model
instead of all uncertain models. This has a twofold advantage: (i) it avoids
an additional computation of the minimum as done in [29, 21, 7], where the
authors sample next-state transitions and rewards based on all parameters from
the uncertainty set, then update a policy based on the worst outcome; (ii) it
releases from restricting to finite uncertainty sets. In fact, our regularizer
accounts for robustness regardless of the sampling procedure, whereas the
parallel simulations of [29, 21, 7] require the uncertainty set to be finite.
Technical difficulties are yet to be addressed for generalizing our result to
transition-uncertain MDPs, because of the interdependence between the
regularizer and the value function (see Secs. 4-5). We detail more on this
issue in Appx. A.5.

##  4 General robust MDPs

Now that we have established policy regularization as a reward-robust problem,
we would like to study the opposite question: can any robust MDP with both
uncertain reward and transition be solved using regularization instead of
robust optimization? If so, is the regularization function easy to determine?
In this section, we answer positively to both questions for properly defined
robust MDPs. This greatly facilitates robust RL, as it avoids the increased
complexity of robust planning algorithms while still reaching robust
performance.

The following theorem establishes that similarly to reward-robust MDPs, robust
MDPs can be formulated through regularization (see proof in Appx. B.1).
Although the regularizer is also a support function in that case, it depends
on both the policy and the value objective, which may further explain the
difficulty of dealing with robust MDPs.

######  Theorem 4.1 (General robust MDP).

Assume that $\mathcal{U}=(P_{0}+\mathcal{P})\times(r_{0}+\mathcal{R})$. Then,
for any policy
$\pi\in\Delta_{\operatorname{\mathcal{A}}}^{\operatorname{\mathcal{S}}}$, the
robust value function $v^{\pi,\mathcal{U}}$ is the optimal solution of the
convex optimization problem:

$\displaystyle\max_{v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}}\langle
v,\mu_{0}\rangle\text{ s. t. }v(s)\leq
T_{(P_{0},r_{0})}^{\pi}v(s)-\sigma_{\mathcal{R}_{s}}(-\pi_{s})-\sigma_{\mathcal{P}_{s}}(-\gamma
v\cdot\pi_{s})\text{ for all }s\in\operatorname{\mathcal{S}},$ (2)

where
$[v\cdot\pi_{s}](s^{\prime},a):=v(s^{\prime})\pi_{s}(a)\quad\forall(s^{\prime},a)\in\operatorname{\mathcal{X}}$.

The upper-bound in the inequality constraint (2) is of the same spirit as the
regularized Bellman operator: the first term is a standard, non-regularized
Bellman operator on the nominal model $(P_{0},r_{0})$ to which we subtract a
policy and value-dependent function playing the role of regularization. This
function reminds that of [6, Thm. 3.1] also coming from conjugacy. This is the
only similarity between both regularizers: in [6], the Legendre-Fenchel
transform is applied on a different type of function and results in a
regularization term that has no closed form but can only be bounded from
above. Moreover, the setup considered there is different since it studies
distributionally robust MDPs. As such, it involves general convex
optimization, whereas we focus on the robust formulation of an LP.

The support function further simplifies when the uncertainty set is a ball, as
shown below. Yet, the dependence of the regularizer on the value function
prevents us from readily applying the tool-set of regularized MDPs. We shall
study the properties of this new regularization function in Sec. 5.

######  Corollary 4.1.

Assume that $\mathcal{U}=(P_{0}+\mathcal{P})\times(r_{0}+\mathcal{R})$ with
$\mathcal{P}_{s}:=\\{P_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}:\lVert
P_{s}\rVert\leq\alpha_{s}^{P}\\}$ and
$\mathcal{R}_{s}:=\\{r_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}:\lVert
r_{s}\rVert\leq\alpha_{s}^{r}\\}$ for all $s\in\operatorname{\mathcal{S}}$.
Then, the robust value function $v^{\pi,\mathcal{U}}$ is the optimal solution
of the convex optimization problem:

$\displaystyle\max_{v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}}\langle
v,\mu_{0}\rangle\text{ s. t. }v(s)\leq
T_{(P_{0},r_{0})}^{\pi}v(s)-\alpha_{s}^{r}\lVert\pi_{s}\rVert-\alpha_{s}^{P}\gamma\lVert
v\rVert\lVert\pi_{s}\rVert\text{ for all }s\in\operatorname{\mathcal{S}}.$ (3)

One can actually take two different norms for the reward and the transition
uncertainty sets. Similarly, Cor. 4.1 can be rewritten with an arbitrary norm,
which would reveal a dual norm $\lVert\cdot\rVert_{*}$ instead of
$\lVert\cdot\rVert$ in Eq. (3) (see proof in Appx. B.2). Here, we restrict our
statement to the $\ell_{2}$-norm for notation convenience only, the dual norm
of $\ell_{2}$ being $\ell_{2}$ itself. Thus, our regularization function
recovers a robust value function independently of the chosen norm, which
extends previous results from [15, 11]. Indeed, Ho et al. [15] lighten
complexity of robust planning for the $\ell_{1}$-norm only, while Grand-
Clément & Kroer [11] focus on KL and $\ell_{2}$ ball-constrained uncertainty
sets. Both works rely on the specific structure induced by the divergence they
consider to derive more efficient robust Bellman updates. Differently, our
method circumvents these updates using a generic, problem-independent
regularization function while still encompassing $s$-rectangular uncertainty
sets as in [15, 11].

##  5 R2 MDPs

In Sec. 4, we showed that for general robust MDPs, the optimization constraint
involves a regularization term that depends on the value function itself. This
adds a difficulty to the reward-robust case where the regularization only
depends on the policy. Yet, we provided an explicit regularizer for general
robust MDPs that are ball-constrained. In this section, we introduce R2 MDPs,
an extension of regularized MDPs that combines policy and value
regularization. The core idea is to further regularize the Bellman operators
with a value-dependent term that recovers the support functions we derived
from the robust optimization problems of Secs. 3-4.

######  Definition 5.1 (R2 Bellman operators).

For all $v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}$, define
$\Omega_{v,\textsc{r\textsuperscript{2}}}:\Delta_{\operatorname{\mathcal{A}}}\to\operatorname{\mathbb{R}}$
as
$\Omega_{v,\textsc{r\textsuperscript{2}}}(\pi_{s}):=\lVert\pi_{s}\rVert(\alpha_{s}^{r}+\alpha_{s}^{P}\gamma\lVert
v\rVert)$. The R2 Bellman evaluation and optimality operators are defined as

$\displaystyle[T^{\pi,\textsc{r\textsuperscript{2}}}v](s)$
$\displaystyle:=T_{(P_{0},r_{0})}^{\pi}v(s)-\Omega_{v,\textsc{r\textsuperscript{2}}}(\pi_{s})\quad\forall
s\in\operatorname{\mathcal{S}},$
$\displaystyle[T^{*,\textsc{r\textsuperscript{2}}}v](s)$
$\displaystyle:=\max_{\pi\in\Delta_{\operatorname{\mathcal{A}}}^{\operatorname{\mathcal{S}}}}[T^{\pi,\textsc{r\textsuperscript{2}}}v](s)=\Omega_{v,\textsc{r\textsuperscript{2}}}^{*}(q_{s})\quad\forall
s\in\operatorname{\mathcal{S}}.$

For any function $v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}$,
the associated unique greedy policy is defined as

$\pi_{s}=\arg\max_{\pi_{s}\in\Delta_{\operatorname{\mathcal{A}}}}T^{\pi,\textsc{r\textsuperscript{2}}}v(s)=\nabla\Omega_{v,\textsc{r\textsuperscript{2}}}^{*}(q_{s}),\quad\forall
s\in\operatorname{\mathcal{S}},$

that is, in vector form,
$\pi=\nabla\Omega_{v,\textsc{r\textsuperscript{2}}}^{*}(q)=:\mathcal{G}_{\Omega_{\textsc{r\textsuperscript{2}}}}(v)\iff
T^{\pi,\textsc{r\textsuperscript{2}}}v=T^{*,\textsc{r\textsuperscript{2}}}v$.

The R2 Bellman evaluation operator is not linear because of the functional
norm appearing in the regularization function. Yet, under the following
assumption, it is contracting and we can apply Banach’s fixed point theorem to
define the R2 value function.

######  Assumption 5.1 (Bounded radius).

For all $s\in\operatorname{\mathcal{S}}$, there exists $\epsilon_{s}>0$ such
that

$\alpha_{s}^{P}\leq\min\left(\frac{1-\gamma-\epsilon_{s}}{\gamma\sqrt{\lvert\operatorname{\mathcal{S}}\rvert}};\min_{\begin{subarray}{c}\mathbf{u}_{\operatorname{\mathcal{A}}}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}_{+},\lVert\mathbf{u}_{\operatorname{\mathcal{A}}}\rVert=1\\\
\mathbf{v}_{\operatorname{\mathcal{S}}}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}_{+},\lVert\mathbf{v}_{\operatorname{\mathcal{S}}}\rVert=1\end{subarray}}\mathbf{u}_{\operatorname{\mathcal{A}}}^{\top}P_{0}(\cdot|s,\cdot)\mathbf{v}_{\operatorname{\mathcal{S}}}\right).$

Asm. 5.1 requires to upper bound the ball radius of transition uncertainty
sets. The first term in the minimum is needed for establishing contraction of
R2 Bellman operators (item (iii) in Prop. 5.1), while the second one is used
for ensuring monotonicity (item (i) in Prop. 5.1). We remark that the former
depends on the original discount factor $\gamma$: radius $\alpha_{s}^{P}$ must
be smaller as $\gamma$ tends to $1$ but can arbitrarily grow as $\gamma$
decreases to $0$, without altering contraction. Indeed, larger $\gamma$
implies longer time horizon and higher stochasticity, which explains why we
need tighter level of uncertainty then. Otherwise, value and policy
regularization seem unable to handle the mixed effects of parameter and
stochastic uncertainties. The additional dependence on the state-space size
comes from the $\ell_{2}$-norm chosen for the ball constraints. In fact, for
any $\ell_{p}$-norm of dual $\ell_{q}$,
$\lvert\operatorname{\mathcal{S}}\rvert^{\frac{1}{q}}$ replaces
$\sqrt{\lvert\operatorname{\mathcal{S}}\rvert}$ in the denominator, so it
becomes independent of $\lvert\operatorname{\mathcal{S}}\rvert$ as $(p,q)$
tends to $(1,\infty)$ (see Appx. C.1). Although we recognize a generalized
Rayleigh quotient-type problem in the second minimum [28], its interpretation
in our context remains unclear. Asm. 5.1 enables the R2 Bellman operators to
admit a unique fixed point, among other nice properties. We formalize this
below (see proof in Appx. C.1).

######  Proposition 5.1.

Suppose that Asm. 5.1 holds. Then, we have the following properties:
(i) Monotonicity: For all
$v_{1},v_{2}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}$ such
that $v_{1}\leq v_{2}$, we have
$T^{\pi,\textsc{r\textsuperscript{2}}}v_{1}\leq
T^{\pi,\textsc{r\textsuperscript{2}}}v_{2}$ and
$T^{*,\textsc{r\textsuperscript{2}}}v_{1}\leq
T^{*,\textsc{r\textsuperscript{2}}}v_{2}$.
(ii) Sub-distributivity: For all
$v_{1}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}},c\in\operatorname{\mathbb{R}}$,
we have
$T^{\pi,\textsc{r\textsuperscript{2}}}(v_{1}+c\mathbbm{1}_{\operatorname{\mathcal{S}}})\leq
T^{\pi,\textsc{r\textsuperscript{2}}}v_{1}+\gamma
c\mathbbm{1}_{\operatorname{\mathcal{S}}}$ and
$T^{*,\textsc{r\textsuperscript{2}}}(v_{1}+c\mathbbm{1}_{\operatorname{\mathcal{S}}})\leq
T^{*,\textsc{r\textsuperscript{2}}}v_{1}+\gamma
c\mathbbm{1}_{\operatorname{\mathcal{S}}}$, $\forall
c\in\operatorname{\mathbb{R}}$.
(iii) Contraction: Let
$\epsilon_{*}:=\min_{s\in\operatorname{\mathcal{S}}}\epsilon_{s}>0$. Then, for
all $v_{1},v_{2}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}$,
$\lVert
T^{\pi,\textsc{r\textsuperscript{2}}}v_{1}-T^{\pi,\textsc{r\textsuperscript{2}}}v_{2}\rVert_{\infty}\leq(1-\epsilon_{*})\lVert
v_{1}-v_{2}\rVert_{\infty}$ and $\lVert
T^{*,\textsc{r\textsuperscript{2}}}v_{1}-T^{*,\textsc{r\textsuperscript{2}}}v_{2}\rVert_{\infty}\leq(1-\epsilon_{*})\lVert
v_{1}-v_{2}\rVert_{\infty}$.

We should note that the contracting coefficient in Prop. 5.1 is different from
the original discount factor $\gamma$, since here we have $1-\epsilon^{*}$.
Yet, as Asm. 5.1 suggests it, an intrinsic dependence between $\gamma$ and
$\epsilon^{*}$ makes the R2 Bellman updates similar to the standard ones: when
$\gamma$ tends to $0$, the value of $\epsilon^{*}$ required for Asm. 5.1 to
hold increases, which makes the contracting coefficient $1-\epsilon^{*}$ tend
to 0 as well, i.e., the two contracting coefficients behave similarly. The
contraction of both R2 Bellman operators finally leads us to introduce the R2
value functions.

######  Definition 5.2 (R2 value functions).

(i) The R2 value function $v^{\pi,\textsc{r\textsuperscript{2}}}$ is defined
as the unique fixed point of the R2 Bellman evaluation operator:
$v^{\pi,\textsc{r\textsuperscript{2}}}=T^{\pi,\textsc{r\textsuperscript{2}}}v^{\pi,\textsc{r\textsuperscript{2}}}$.
The associated $q$-function is
$q^{\pi,\textsc{r\textsuperscript{2}}}(s,a)=r_{0}(s,a)+\gamma\langle
P_{0}(\cdot|s,a),v^{\pi,\textsc{r\textsuperscript{2}}}\rangle$.  (ii) The R2
optimal value function $v^{*,\textsc{r\textsuperscript{2}}}$ is defined as the
unique fixed point of the R2 Bellman optimal operator:
$v^{*,\textsc{r\textsuperscript{2}}}=T^{*,\textsc{r\textsuperscript{2}}}v^{*,\textsc{r\textsuperscript{2}}}$.
The associated $q$-function is
$q^{*,\textsc{r\textsuperscript{2}}}(s,a)=r_{0}(s,a)+\gamma\langle
P_{0}(\cdot|s,a),v^{*,\textsc{r\textsuperscript{2}}}\rangle$.

The monotonicity of the R2 Bellman operators plays a key role in reaching an
optimal R2 policy, as we show in the following. A proof can be found in Appx.
C.2.

######  Theorem 5.1 (R2 optimal policy).

The greedy policy
$\pi^{*,\textsc{r\textsuperscript{2}}}=\mathcal{G}_{\Omega_{\textsc{r\textsuperscript{2}}}}(v^{*,\textsc{r\textsuperscript{2}}})$
is the unique optimal R2 policy, i.e., for all
$\pi\in\Delta_{\operatorname{\mathcal{A}}}^{\operatorname{\mathcal{S}}},v^{\pi^{*},\textsc{r\textsuperscript{2}}}=v^{*,\textsc{r\textsuperscript{2}}}\geq
v^{\pi,\textsc{r\textsuperscript{2}}}$.

######  Remark 5.1.

An optimal R2 policy may be stochastic. This is due to the fact that our R2
MDP framework builds upon the general $s$-rectangularity assumption. Robust
MDPs with $s$-rectangular uncertainty sets similarly yield an optimal robust
policy that is stochastic [40, Table 1]. Nonetheless, the R2 MDP formulation
recovers a deterministic optimal policy in the more specific
$(s,a)$-rectangular case, which is in accordance with the robust MDP setting
(see proof in Appx. C.3). 333The stochasticity of an optimal entropy-
regularized policy as in the examples of Sec. 3 is not contradicting. Indeed,
even though the corresponding uncertainty set is $(s,a)$-rectangular there, it
is policy-dependent.

Result: $\pi_{k+1},v_{k+1}$

Initialize $v_{k}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}$;

while  _not converged_ do

$\pi_{k+1}\leftarrow\mathcal{G}_{\Omega_{\textsc{r\textsuperscript{2}}}}(v_{k})$;

$v_{k+1}\leftarrow(T^{\pi_{k+1},\textsc{r\textsuperscript{2}}})^{m}v_{k}$;

end while

Algorithm 1 R2 MPI

All of the results above ensure convergence of MPI in R2 MDPs. We call that
method R2 MPI and provide its pseudo-code in Alg. 1. The convergence proof
follows the same lines as in [30]. Moreover, the contracting property of the
R2 Bellman operator ensures the same convergence rate as in standard and
robust MDPs, i.e., a geometric convergence rate. On the other hand, R2 MPI
reduces the computational complexity of robust MPI by avoiding to solve a max-
min problem at each iteration, as this can take polynomial time for general
convex programs. Advantageously, the only optimization involved in R2 MPI lies
in the greedy step: it amounts to projecting onto the simplex, which can
efficiently be performed in linear time [8]. Still, such projection is not
even necessary in the $(s,a)$-rectangular case: as mentioned in Rmk. 5.1, it
then suffices to choose a greedy action in order to eventually achieve an
optimal R2 value function.

##  6 Numerical Experiments

We aim to compare the computing time of R2 MPI with that of MPI [30] and
robust MPI [18]. The code is available at
https://github.com/EstherDerman/r2mdp. To do so, we run experiments on an
Intel(R) Core(TM) i7-1068NG7 CPU @ 2.30GHz machine, which we test on a
$5\times 5$ grid-world domain. In that environment, the agent starts from a
random position and seeks to reach a goal state in order to maximize reward.
Thus, the reward function is zero in all states but two: one provides a reward
of 1 while the other gives 10. An episode ends when either one of those two
states is attained.

The partial evaluation of each policy iterate is a building block of MPI. As a
sanity check, we evaluate the uniform policy through both R2 and robust policy
evaluation (PE) sub-processes, to ensure that the two value outputs coincide.
For simplicity, we focus on an $(s,a)$-rectangular uncertainty set and take
the same ball radius $\alpha$ (resp. $\beta$) at each state-action pair for
the reward function (resp. transition function). Parameter values and other
implementation details are deferred to Appx. D. We obtain the same value for
R2 PE and robust PE, which numerically confirms Thm. 4.1. On the other hand,
both are strictly smaller than their non-robust, non-regularized counterpart,
but as expected, they converge to the standard value function when all ball
radii tend to 0 (see Appx. D). More importantly, R2 PE converges in $0.02$
seconds, whereas robust PE takes $54.8$ seconds to converge, i.e., $2740$
times longer. This complexity gap comes from the minimization problems being
solved at each iteration of robust PE, something that R2 PE avoids thanks to
regularization. R2 PE still takes $2.5$ times longer than its standard, non-
regularized counterpart, because of the additional computation of
regularization terms. Table 1 shows the time spent by each algorithm until
convergence.

Table 1: Computing time (in sec.) of planning algorithms using vanilla, R2 and robust approaches. Each cell displays the mean $\pm$ standard deviation obtained from 5 running seeds. | Vanilla | R2 | Robust
---|---|---|---
PE | $0.008\pm 0.$ | $0.02\pm 0.$ | $54.8\pm 1.2$
MPI ($m=1$) | $0.01\pm 0.$ | $0.03\pm 0.$ | $118.6\pm 1.3$
MPI ($m=4$) | $0.01\pm 0.$ | $0.03\pm 0.$ | $98.1\pm 4.1$

We then study the overall MPI process for each approach. We know that in
vanilla MPI, the greedy step is achieved by simply searching over
deterministic policies [30]. Since we focus our experiments on an
$(s,a)$-rectangular uncertainty set, the same applies to robust MPI [40] and
to R2 MPI, as already mentioned in Rmk. 5.1. We can see in Table 1 that the
increased complexity of robust MPI is even more prominent than its PE thread,
as robust MPI takes 3953 (resp. $3270$) times longer than R2 MPI when $m=1$
(resp. $m=4$). Robust MPI with $m=4$ is a bit more advantageous than $m=1$, as
it needs less iterations (31 versus 67), i.e., less optimization solvers to
converge. Interestingly, for both $m\in\\{1,4\\}$, progressing from PE to MPI
did not cost much more computing time to either the vanilla or the R2 version:
both take less than one second to run.

##  7 Related Work

Connections between regularization and robustness have been established in
standard statistical learning settings such as support vector machines [41],
logistic regression [35] or maximum likelihood estimation [19]. As stated in
Sec. 1, these represent particular RL problems as they concern a single-stage
decision-making process. In that regard, the generalization of robustness-
regularization duality to sequential decision-making has seldom been studied
in the RL literature.

Two works that view policy regularization from a robustness perspective are
[16] and [9]. In [16], regularization is applied on the dual objective instead
of the primal. This has two shortcomings: (i) It prevents from deriving
regularized Bellman operators and dynamic programming methods; (ii) The
feasible set is that of occupancy measures, so the connection with standard
policy regularization remains unclear. Furthermore, their work focuses on
reward robustness. Differently, Eysenbach & Levine [9] address both reward and
transition uncertainty by showing that policies with maximum entropy
regularization solve a particular type of robust MDP. Yet, their analysis
separately treats the uncertainty on $P$ and $r$, which questions the
robustness of the resulting policy when the whole model $(P,r)$ is
adversarial. Moreover, the dual relation they establish between entropy
regularization and transition-robust MDPs is weak and applies to specific
uncertainty sets. Both of these works treat robustness as a side-effect of
regularization more than an objective on its own, whereas we aim to do the
opposite, namely, use regularization to solve robust RL problems.

Derman & Mannor [6] similarly use regularization as a tool for achieving
robust policies. Through distributionally robust MDPs, they show upper and
lower bounds between transition-robustness and regularization. There again,
duality is weak and reward uncertainty is not addressed. Moreover, since the
exact regularization term has no explicit form, it is usable through its upper
bound only. Finally, regularization is applied on the mean of several value
functions $v^{\pi}_{(\hat{P}_{i},r)}$, where each $\hat{P}_{i}$ is a
transition model estimated from an episode run. Computing this quantity
requires as many policy evaluations as the number of model estimates
available, which results in a linear complexity blowup at least.

Previous studies analyze robust planning algorithms to provide convergence
guarantees. The works [2, 27] propose robust value iteration, while [17, 40]
introduce robust policy iteration. Kaufman & Schaefer [18] generalize both
schemes by proposing a robust MPI and determine the conditions under which it
converges. The polynomial time within which all these works guarantee a robust
solution is often insufficient, as the complexity of a Bellman update grows
cubically in the number of states [15].

In order to reduce the time complexity of robust planning algorithms, Ho et
al. [15] propose two algorithms that compute robust Bellman updates in
$\mathcal{O}(\lvert\operatorname{\mathcal{S}}\rvert\lvert\operatorname{\mathcal{A}}\rvert\log(\lvert\operatorname{\mathcal{S}}\rvert\lvert\operatorname{\mathcal{A}}\rvert))$
operations for $\ell_{1}$-constrained uncertainty sets. Advantageously, our
regularization approach reduces each such update to its standard, non-robust
complexity of
$\mathcal{O}(\lvert\operatorname{\mathcal{S}}\rvert\lvert\operatorname{\mathcal{A}}\rvert)$.
Moreover, although Ho et al. [15] address both $(s,a)$ and $s$-rectangular
uncertainty sets, they focus on transition uncertainty, whereas we tackle both
reward and transition uncertainties in the general $s$-rectangular case.
Finally, their contribution relies on LP formulations that necessitate
restricting to the $\ell_{1}$-norm while our method applies to any norm. This
may come from the fact that our main Theorems (Thms. 3.1 and 4.1) use Fenchel-
Rockafellar duality [31, 4], a generalization of LP duality (see Appx. A.2 and
B.1). More recently, Grand-Clément & Kroer [11] propose a first-order method
to accelerate robust value iteration under $s$-rectangular uncertainty sets
that are either ellipsoidal or KL-constrained. To our knowledge, our study is
the first one reducing the time complexity of robust planning when the
uncertainty set is $s$-rectangular and constrained with an arbitrary norm.

##  8 Conclusion and future work

In this work, we established a strong duality between robust MDPs and twice
regularized MDPs. This revealed that the regularized MDPs of [10] are in fact
robust MDPs with uncertain reward, which enabled us to derive a policy-
gradient theorem for reward-robust MDPs. When extending this robustness-
regularization duality to general robust MDPs, we found that the regularizer
depends on the value function besides the policy. We thus introduced R2 MDPs,
a generalization of regularized MDPs with both policy and value
regularization. The related R2 Bellman operators lead us to propose a
converging R2 MPI algorithm that achieves the optimal robust value function
within similar computing time as standard MPI.

This study settles the theoretical foundations for scalable robust RL. We
should note that our results naturally extend to continuous but compact action
spaces in the same manner as standard MDPs do [30]. Extension to infinite
state-space would be more involved because of the state-dependent regularizer
in R2 MDPs. In fact, it would be interesting to study the R2 MDP setting under
function approximation, as such approximation would have a direct effect on
the regularizer. Similarly, one could analyze approximate dynamic programming
for R2 MDPs in light of its robust analog [38, 1]. Although our theory focused
on planning, the R2 Bellman operators and their contracting properties open
the path to learning algorithms that can (i) use existing RL algorithms and
robustify them by simply changing the regularizer; (ii) scale to deep learning
settings. Apart from its practical effect, we believe our work opens the path
to more theoretical contributions in robust RL. For example, extending R2 MPI
to the approximate case [33] would be an interesting problem to solve because
of the R2 evaluation operator being non-linear. So would be a sample
complexity analysis for R2 MDPs with a comparison to robust MDPs [42]. Another
line of research is to extend policy-gradient to R2 MDPs, as this would avoid
parallel learning of adversarial models [7, 39] and be very useful for
continuous control.

## Acknowledgements

We would like to thank Raphael Derman for his useful suggestions that improved
the clarity of the text. Thanks also to Stav Belogolovsky for reviewing a
previous version of this paper. Funding in direct support of this work: ISF
grant.

## References

  * Badrinath & Kalathil [2021] Badrinath, K. P. and Kalathil, D.  Robust reinforcement learning using least squares policy iteration with provable performance guarantees.  In _International Conference on Machine Learning_ , pp. 511–520. PMLR, 2021.
  * Bagnell et al. [2001] Bagnell, J. A., Ng, A. Y., and Schneider, J. G.  Solving uncertain Markov decision processes.  2001\.
  * Bertsekas [2009] Bertsekas, D. P.  _Convex optimization theory_.  Athena Scientific Belmont, 2009.
  * Borwein & Lewis [2010] Borwein, J. and Lewis, A. S.  _Convex analysis and nonlinear optimization: theory and examples_.  Springer Science & Business Media, 2010.
  * Cen et al. [2020] Cen, S., Cheng, C., Chen, Y., Wei, Y., and Chi, Y.  Fast global convergence of natural policy gradient methods with entropy regularization.  _arXiv preprint arXiv:2007.06558_ , 2020.
  * Derman & Mannor [2020] Derman, E. and Mannor, S.  Distributional robustness and regularization in reinforcement learning.  _ICML Workshop_ , 2020.
  * Derman et al. [2018] Derman, E., Mankowitz, D., Mann, T., and Mannor, S.  Soft-robust actor-critic policy-gradient.  _AUAI press for Association for Uncertainty in Artificial Intelligence_ , pp. 208–218, 2018.
  * Duchi et al. [2008] Duchi, J., Shalev-Shwartz, S., Singer, Y., and Chandra, T.  Efficient projections onto the l 1-ball for learning in high dimensions.  In _Proceedings of the 25th international conference on Machine learning_ , pp. 272–279, 2008.
  * Eysenbach & Levine [2021] Eysenbach, B. and Levine, S.  Maximum entropy RL (provably) solves some robust RL problems.  _arXiv preprint arXiv:2103.06257_ , 2021.
  * Geist et al. [2019] Geist, M., Scherrer, B., and Pietquin, O.  A theory of regularized Markov decision processes.  In _International Conference on Machine Learning_ , pp. 2160–2169. PMLR, 2019.
  * Grand-Clément & Kroer [2021] Grand-Clément, J. and Kroer, C.  Scalable first-order methods for robust mdps.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pp. 12086–12094, 2021.
  * Haarnoja et al. [2017] Haarnoja, T., Tang, H., Abbeel, P., and Levine, S.  Reinforcement learning with deep energy-based policies.  In _International Conference on Machine Learning_ , pp. 1352–1361. PMLR, 2017.
  * 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_ , pp. 1861–1870. PMLR, 2018.
  * Hiriart-Urruty & Lemaréchal [2004] Hiriart-Urruty, J.-B. and Lemaréchal, C.  _Fundamentals of convex analysis_.  Springer Science & Business Media, 2004.
  * Ho et al. [2018] Ho, C. P., Petrik, M., and Wiesemann, W.  Fast Bellman updates for robust MDPs.  In _International Conference on Machine Learning_ , pp. 1979–1988. PMLR, 2018.
  * Husain et al. [2021] Husain, H., Ciosek, K., and Tomioka, R.  Regularized policies are reward robust.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 64–72. PMLR, 2021.
  * Iyengar [2005] Iyengar, G. N.  Robust dynamic programming.  _Mathematics of Operations Research_ , 30(2):257–280, 2005.
  * Kaufman & Schaefer [2013] Kaufman, D. L. and Schaefer, A. J.  Robust modified policy iteration.  _INFORMS Journal on Computing_ , 25(3):396–410, 2013.
  * Kuhn et al. [2019] Kuhn, D., Esfahani, P. M., Nguyen, V. A., and Shafieezadeh-Abadeh, S.  Wasserstein distributionally robust optimization: Theory and applications in machine learning.  In _Operations Research & Management Science in the Age of Analytics_, pp. 130–166. INFORMS, 2019.
  * Lee et al. [2018] Lee, K., Choi, S., and Oh, S.  Sparse Markov decision processes with causal sparse Tsallis entropy regularization for reinforcement learning.  _IEEE Robotics and Automation Letters_ , 3(3):1466–1473, 2018.
  * Mankowitz et al. [2018] Mankowitz, D., Mann, T., Bacon, P.-L., Precup, D., and Mannor, S.  Learning robust options.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Mannor et al. [2007] Mannor, S., Simester, D., Sun, P., and Tsitsiklis, J. N.  Bias and variance approximation in value function estimates.  _Management Science_ , 53(2):308–322, 2007.
  * Mannor et al. [2012] Mannor, S., Mebel, O., and Xu, H.  Lightning does not strike twice: Robust MDPs with coupled uncertainty.  _ICML_ , 2012.
  * Mannor et al. [2016] Mannor, S., Mebel, O., and Xu, H.  Robust MDPs with k-rectangular uncertainty.  _Mathematics of Operations Research_ , 41(4):1484–1509, 2016.
  * Mensch & Blondel [2018] Mensch, A. and Blondel, M.  Differentiable dynamic programming for structured prediction and attention.  In _International Conference on Machine Learning_ , pp. 3462–3471. PMLR, 2018.
  * Nachum & Dai [2020] Nachum, O. and Dai, B.  Reinforcement learning via Fenchel-Rockafellar duality.  _arXiv preprint arXiv:2001.01866_ , 2020.
  * 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.
  * Parlett [1974] Parlett, B. N.  The Rayleigh quotient iteration and some generalizations for nonnormal matrices.  _Mathematics of Computation_ , 28(127):679–693, 1974.
  * Pinto et al. [2017] Pinto, L., Davidson, J., Sukthankar, R., and Gupta, A.  Robust adversarial reinforcement learning.  In _International Conference on Machine Learning_ , pp. 2817–2826. PMLR, 2017.
  * Puterman [2014] Puterman, M. L.  _Markov decision processes: discrete stochastic dynamic programming_.  John Wiley & Sons, 2014.
  * Rockafellar [1970] Rockafellar, R. T.  _Convex analysis_ , volume 36.  Princeton university press, 1970.
  * Roy et al. [2017] Roy, A., Xu, H., and Pokutta, S.  Reinforcement learning under model mismatch.  _NIPS_ , 2017.
  * Scherrer et al. [2015] Scherrer, B., Ghavamzadeh, M., Gabillon, V., Lesner, B., and Geist, M.  Approximate modified policy iteration and its application to the game of Tetris.  _J. Mach. Learn. Res._ , 16:1629–1676, 2015.
  * 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.
  * Shafieezadeh-Abadeh et al. [2015] Shafieezadeh-Abadeh, S., Esfahani, P. M., and Kuhn, D.  Distributionally robust logistic regression.  _NIPS_ , 2015.
  * Shani et al. [2020] Shani, L., Efroni, Y., and Mannor, S.  Adaptive trust region policy optimization: Global convergence and faster rates for regularized MDPs.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pp. 5668–5675, 2020.
  * Sutton et al. [1999] Sutton, R. S., McAllester, D. A., Singh, S. P., Mansour, Y., et al.  Policy gradient methods for reinforcement learning with function approximation.  In _NIPs_ , volume 99, pp. 1057–1063. Citeseer, 1999.
  * Tamar et al. [2014] Tamar, A., Mannor, S., and Xu, H.  Scaling up robust MDPs using function approximation.  In _International Conference on Machine Learning_ , pp. 181–189. PMLR, 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_ , pp. 6215–6224. PMLR, 2019.
  * Wiesemann et al. [2013] Wiesemann, W., Kuhn, D., and Rustem, B.  Robust Markov decision processes.  _Mathematics of Operations Research_ , 38(1):153–183, 2013.
  * Xu et al. [2009] Xu, H., Caramanis, C., and Mannor, S.  Robustness and regularization of support vector machines.  _Journal of machine learning research_ , 10(7), 2009.
  * Yang & Zhang [2021] Yang, W. and Zhang, Z.  Non-asymptotic performances of Robust Markov Decision Processes.  _arXiv preprint arXiv:2105.03863_ , 2021.

## Checklist

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes]  The main contributions are
consistently listed in the abstract and introduction. These are: Showing that
regularized MDPs are a particular instance of robust MDPs with uncertain
reward (Sec. 3); Extending this relationship to MDPs with uncertain
transitions (Sec. 4); Generalizing regularized MDPs to R2 MDPs (Sec. 5).

    2. (b)

Did you describe the limitations of your work? [Yes]  These are described when
discussing Prop. 3.2 and Asm. 5.1, near the corresponding statements.

    3. (c)

Did you discuss any potential negative societal impacts of your work? [N/A]

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [Yes]
Assumptions are introduced by "Assume that…" or "If…" in each theoretical
result.

    2. (b)

Did you include complete proofs of all theoretical results? [Yes]  All proofs
can be found in the Appendix. At each theoretical statement in the text body,
we precisely refer to the corresponding proof.

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [Yes]
The code is available at https://github.com/EstherDerman/r2mdp, which includes
all instructions needed to reproduce the results.

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [Yes]  These are included in the experiments section
(Sec. 6) and detailed in Appx. D.

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [Yes]  Table 1 displays mean $\pm$ standard
deviation for each type of experiment. The figure plots in Appx. D also
include error bars.

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]  See Sec. 6.

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [N/A]

    2. (b)

Did you mention the license of the assets? [N/A]

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [N/A]

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [N/A]

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [N/A]

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A]

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A]

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A]

## Appendix: Twice regularized MDPs and the equivalence between robustness and
regularization

This appendix provides proofs for all of the results stated in the paper. We
first recall the following theorem used in the sequel and referred to as
Fenchel-Rochafellar duality [4, Thm 3.3.5].

######  Theorem (Fenchel-Rockafellar duality).

Let $X,Y$ two Euclidean spaces, $f:X\to\overline{\operatorname{\mathbb{R}}}$
and $g:Y\to\overline{\operatorname{\mathbb{R}}}$ two proper, convex functions,
and $A:X\to Y$ a linear mapping such that
$0\in\mathrm{core}(\mathrm{dom}(g)-A(\mathrm{dom}(f)))$.444Given
$C\subseteq\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}$, we say
that $x\in\mathrm{core}(C)$ if for all
$d\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}$ there exists a
small enough $t\in\operatorname{\mathbb{R}}$ such that $x+td\in C$ [4]. Then,
it holds that

$\displaystyle\min_{x\in X}f(x)+g(Ax)=\max_{y\in Y}-f^{*}(-A^{*}y)-g^{*}(y).$
(4)

##  Appendix A Reward-Robust MDPs

###  A.1 Proof of Proposition 3.1

######  Proposition.

For any policy
$\pi\in\Delta_{\operatorname{\mathcal{A}}}^{\operatorname{\mathcal{S}}}$, the
robust value function $v^{\pi,\mathcal{U}}$ is the optimal solution of the
robust optimization problem:

$\displaystyle\max_{v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}}\langle
v,\mu_{0}\rangle\text{ s. t. }v\leq T_{(P,r)}^{\pi}v\text{ for all
}(P,r)\in\mathcal{U}.$ (PU)

###### Proof.

Let $v^{*}$ an optimal point of (PU). By definition of the robust value
function,
$v^{\pi,\mathcal{U}}=T^{\pi,\mathcal{U}}v^{\pi,\mathcal{U}}=\min_{(P,r)\in\mathcal{U}}T_{(P,r)}^{\pi}v^{\pi,\mathcal{U}}$.
In particular, $v^{\pi,\mathcal{U}}\leq T_{(P,r)}^{\pi}v^{\pi,\mathcal{U}}$
for all $(P,r)\in\mathcal{U}$, so the robust value is feasible and by
optimality of $v^{*}$, we get $\langle v^{*},\mu_{0}\rangle\geq\langle
v^{\pi,\mathcal{U}},\mu_{0}\rangle.$ Now, we aim to show that any feasible
$v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}$ satisfies $v\leq
v^{\pi,\mathcal{U}}.$ Let an arbitrary $\epsilon>0$. Then, there exists
$(P_{\epsilon},r_{\epsilon})\in\mathcal{U}$ such that

$\displaystyle
T^{\pi,\mathcal{U}}v^{\pi,\mathcal{U}}+\epsilon>T_{(P_{\epsilon},r_{\epsilon})}^{\pi}v^{\pi,\mathcal{U}}.$
(5)

This yields:

$\displaystyle v-v^{\pi,\mathcal{U}}$
$\displaystyle=v-T^{\pi,\mathcal{U}}v^{\pi,\mathcal{U}}$
$\displaystyle[v^{\pi,\mathcal{U}}=T^{\pi,\mathcal{U}}v^{\pi,\mathcal{U}}]$
$\displaystyle<v+\epsilon-
T_{(P_{\epsilon},r_{\epsilon})}^{\pi}v^{\pi,\mathcal{U}}$
$\displaystyle[\text{By Eq.~{}\eqref{eq: epsilon inf}}]$ $\displaystyle\leq
T^{\pi,\mathcal{U}}v+\epsilon-
T_{(P_{\epsilon},r_{\epsilon})}^{\pi}v^{\pi,\mathcal{U}}$
$\displaystyle[v\text{ is feasible for }\eqref{eq: iyengar ro primal}]$
$\displaystyle\leq
T^{\pi,\mathcal{U}}v+\epsilon-T^{\pi,\mathcal{U}}v^{\pi,\mathcal{U}}$
$\displaystyle[T^{\pi,\mathcal{U}}u=\min_{(P,r)\in\mathcal{U}}T_{(P,r)}^{\pi}u\leq
T_{(P_{\epsilon},r_{\epsilon})}^{\pi}u\quad\forall
u\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}]$
$\displaystyle=T^{\pi,\mathcal{U}}(v-v^{\pi,\mathcal{U}})+\epsilon.$

Thus, $v-v^{\pi,\mathcal{U}}\leq
T^{\pi,\mathcal{U}}(v-v^{\pi,\mathcal{U}})+\epsilon$, which we iteratively
apply as follows:

$\displaystyle v-v^{\pi,\mathcal{U}}$ $\displaystyle\leq
T^{\pi,\mathcal{U}}(v-v^{\pi,\mathcal{U}})+\epsilon$ $\displaystyle\leq
T^{\pi,\mathcal{U}}(T^{\pi,\mathcal{U}}(v-v^{\pi,\mathcal{U}})+\epsilon)+\epsilon$
$\displaystyle[\text{By \cite[cite]{[\@@bibref{Number}{nilim2005robust}{}{}]},
}u\leq w\implies T^{\pi,\mathcal{U}}u\leq T^{\pi,\mathcal{U}}w]$
$\displaystyle=(T^{\pi,\mathcal{U}})^{2}(v-v^{\pi,\mathcal{U}})+\gamma\epsilon+\epsilon$
$\displaystyle\leq(T^{\pi,\mathcal{U}})^{2}(T^{\pi,\mathcal{U}}(v-v^{\pi,\mathcal{U}})+\epsilon)+\gamma\epsilon+\epsilon$
$\displaystyle\quad\vdots$
$\displaystyle\leq(T^{\pi,\mathcal{U}})^{n+1}(v-v^{\pi,\mathcal{U}})+\sum_{k=0}^{n}\gamma^{k}\epsilon$
$\displaystyle=(T^{\pi,\mathcal{U}})^{n+1}v-v^{\pi,\mathcal{U}}+\sum_{k=0}^{n}\gamma^{k}\epsilon.$
$\displaystyle[v^{\pi,\mathcal{U}}=T^{\pi,\mathcal{U}}v^{\pi,\mathcal{U}}]$

Setting $n\to\infty$ yields
$v-v^{\pi,\mathcal{U}}\leq\frac{\epsilon}{1-\gamma}$. Since both $\epsilon>0$
and $v$ were taken arbitrarily, $v^{*}\leq v^{\pi,\mathcal{U}}$, while we have
already shown that $\langle v^{*},\mu_{0}\rangle\geq\langle
v^{\pi,\mathcal{U}},\mu_{0}\rangle.$ By positivity of the probability
distribution $\mu_{0}$, it results that $\langle v^{*},\mu_{0}\rangle=\langle
v^{\pi,\mathcal{U}},\mu_{0}\rangle$, and since $\mu_{0}>0$, we obtain
$v^{\pi,\mathcal{U}}=v^{*}$. ∎

###  A.2 Proof of Theorem 3.1

######  Theorem (Reward-robust MDP).

Assume that $\mathcal{U}=\\{P_{0}\\}\times(r_{0}+\mathcal{R}).$ Then, for any
policy
$\pi\in\Delta_{\operatorname{\mathcal{A}}}^{\operatorname{\mathcal{S}}}$, the
robust value function $v^{\pi,\mathcal{U}}$ is the optimal solution of the
convex optimization problem:

$\displaystyle\max_{v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}}\langle
v,\mu_{0}\rangle\text{ s. t. }v(s)\leq
T_{(P_{0},r_{0})}^{\pi}v(s)-\sigma_{\mathcal{R}_{s}}(-\pi_{s})\text{ for all
}s\in\operatorname{\mathcal{S}}.$

###### Proof.

For all $s\in\operatorname{\mathcal{S}}$, define:
$F(s):=\max_{(P,r)\in\mathcal{U}}\left\\{v(s)-r^{\pi}(s)-\gamma
P^{\pi}v(s)\right\\}$. It corresponds to the robust counterpart of (PU) at
$s\in\operatorname{\mathcal{S}}$. Thus, the robust value function
$v^{\pi,\mathcal{U}}$ is the optimal solution of:

$\displaystyle\max_{v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}}\langle
v,\mu_{0}\rangle\text{ s. t. }F(s)\leq 0\text{ for all
}s\in\operatorname{\mathcal{S}}.$ (6)

Based on the structure of the uncertainty set
$\mathcal{U}=\\{P_{0}\\}\times(r_{0}+\mathcal{R})$, we compute the robust
counterpart:

$\displaystyle F(s)$ $\displaystyle=\max_{r^{\prime}\in
r_{0}+\mathcal{R}}\left\\{v(s)-r^{\prime\pi}(s)-\gamma
P_{0}^{\pi}v(s)\right\\}$
$\displaystyle=\max_{r^{\prime}:r^{\prime}=r_{0}+r,r\in\mathcal{R}}\left\\{v(s)-r^{\prime\pi}(s)-\gamma
P_{0}^{\pi}v(s)\right\\}$
$\displaystyle=\max_{r\in\mathcal{R}}\left\\{v(s)-(r_{0}^{\pi}(s)+r^{\pi}(s))-\gamma
P_{0}^{\pi}v(s)\right\\}$
$\displaystyle[(r_{0}+r)^{\pi}=r_{0}^{\pi}+r^{\pi}\quad\forall\pi\in\Delta_{\operatorname{\mathcal{A}}}^{\operatorname{\mathcal{S}}}]$
$\displaystyle=\max_{r\in\mathcal{R}}\left\\{v(s)-r^{\pi}(s)-r_{0}^{\pi}(s)-\gamma
P_{0}^{\pi}v(s)\right\\}$
$\displaystyle=\max_{r\in\mathcal{R}}\left\\{v(s)-r^{\pi}(s)-T_{(P_{0},r_{0})}^{\pi}v(s)\right\\}$
$\displaystyle[T_{(P_{0},r_{0})}^{\pi}v(s)=r_{0}^{\pi}(s)+\gamma
P_{0}^{\pi}v(s)]$
$\displaystyle=\max_{r\in\mathcal{R}}\\{-r^{\pi}(s)\\}+v(s)-T_{(P_{0},r_{0})}^{\pi}v(s)$
$\displaystyle=\max_{r\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}}\\{-r^{\pi}(s)-\delta_{\mathcal{R}}(r^{\prime})\\}+v(s)-T_{(P_{0},r_{0})}^{\pi}v(s)$
$\displaystyle=-\min_{r\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}}\\{r^{\pi}(s)+\delta_{\mathcal{R}}(r)\\}+v(s)-T_{(P_{0},r_{0})}^{\pi}v(s)$
$\displaystyle=-\min_{r\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}}\\{\langle
r_{s},\pi_{s}\rangle+\delta_{\mathcal{R}}(r)\\}+v(s)-T_{(P_{0},r_{0})}^{\pi}v(s).$
$\displaystyle[r^{\pi}(s)=\langle r_{s},\pi_{s}\rangle]$

By the rectangularity assumption,
$\mathcal{R}=\times_{s\in\operatorname{\mathcal{S}}}\mathcal{R}_{s}$ and for
all
$r:=(r_{s})_{s\in\operatorname{\mathcal{S}}}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}$,
we have
$\delta_{\mathcal{R}}(r)=\sum_{s^{\prime}\in\operatorname{\mathcal{S}}}\delta_{\mathcal{R}_{s^{\prime}}}(r_{s^{\prime}})$.
As such,

$\displaystyle F(s)$
$\displaystyle=-\min_{r\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}}\\{\langle
r_{s},\pi_{s}\rangle+\sum_{s^{\prime}\in\operatorname{\mathcal{S}}}\delta_{\mathcal{R}_{s^{\prime}}}(r_{s^{\prime}})\\}+v(s)-T_{(P_{0},r_{0})}^{\pi}v(s)$
$\displaystyle=-\min_{r\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}}\\{\langle
r_{s},\pi_{s}\rangle+\delta_{\mathcal{R}_{s}}(r_{s})\\}+v(s)-T_{(P_{0},r_{0})}^{\pi}v(s),$

where the last equality holds since the objective function is minimal if and
only if $r_{s}\in\mathcal{R}_{s}$.

We now aim to apply Fenchel-Rockafellar duality to the minimization problem.
Let the function
$f:\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}\to\operatorname{\mathbb{R}}$
defined as $r_{s}\mapsto\langle r_{s},\pi_{s}\rangle$, and consider the
support function
$\delta_{\mathcal{R}_{s}}:\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}\to\overline{\operatorname{\mathbb{R}}}$
together with the identity mapping
$\mathbf{Id}_{\operatorname{\mathcal{A}}}:\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}\to\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}$.
Clearly,
$\mathrm{dom}(f)=\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}$,
$\mathrm{dom}(\delta_{\mathcal{R}_{s}})=\mathcal{R}_{s}$, and
$\mathrm{dom}(\delta_{\mathcal{R}_{s}})-\mathbf{Id}_{\operatorname{\mathcal{A}}}(\mathrm{dom}(f))=\mathcal{R}_{s}-\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}=\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}$.
Therefore,
$\mathrm{core}(\mathrm{dom}(\delta_{\mathcal{R}_{s}})-A(\mathrm{dom}(f)))=\mathrm{core}(\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}})=\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}$
and $0\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}$. We can thus
apply Fenchel-Rockafellar duality: noting that
$\mathbf{Id}_{\operatorname{\mathcal{A}}}=(\mathbf{Id}_{\operatorname{\mathcal{A}}})^{*}$
and $(\delta_{\mathcal{R}_{s}})^{*}(y)=\sigma_{\mathcal{R}_{s}}(y)$, we get

$\displaystyle\min_{r_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}}\\{f(r_{s})+\delta_{\mathcal{R}_{s}}(r_{s})\\}$
$\displaystyle=-\min_{y\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}}\\{f^{*}(-y)+(\delta_{\mathcal{R}_{s}})^{*}(y)\\}=-\min_{y\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}}\\{f^{*}(-y)+\sigma_{\mathcal{R}_{s}}(y)\\}.$

It remains to compute

$\displaystyle
f^{*}(-y)=\max_{r_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}}-\langle
r_{s},y\rangle-\langle
r_{s},\pi_{s}\rangle=\max_{r_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}}\langle
r_{s},-y-\pi_{s}\rangle=\begin{cases}0\text{ if }-y-\pi_{s}=0\\\ +\infty\text{
otherwise}\end{cases},$

and obtain

$\displaystyle F(s)$
$\displaystyle=\min_{y\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}}\\{f^{*}(-y)+\sigma_{\mathcal{R}_{s}}(y)\\}+v(s)-T_{(P_{0},r_{0})}^{\pi}v(s)=\sigma_{\mathcal{R}_{s}}(-\pi_{s})+v(s)-T_{(P_{0},r_{0})}^{\pi}v(s).$

We can thus rewrite the optimization problem (6) as:

$\displaystyle\max_{v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}}\langle
v,\mu_{0}\rangle\text{ s. t.
}\sigma_{\mathcal{R}_{s}}(-\pi_{s})+v(s)-T_{(P_{0},r_{0})}^{\pi}v(s)\leq
0\text{ for all }s\in\operatorname{\mathcal{S}},$

which concludes the proof. ∎

###  A.3 Proof of Corollary 3.1

######  Corollary.

Let $\pi\in\Delta_{\operatorname{\mathcal{A}}}^{\operatorname{\mathcal{S}}}$
and $\mathcal{U}=\\{P_{0}\\}\times(r_{0}+\mathcal{R})$. Further assume that
for all $s\in\operatorname{\mathcal{S}}$, the reward uncertainty set at $s$ is
$\mathcal{R}_{s}:=\\{r_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}:\lVert
r_{s}\rVert\leq\alpha_{s}^{r}\\}$. Then, the robust value function
$v^{\pi,\mathcal{U}}$ is the optimal solution of the convex optimization
problem:

$\displaystyle\max_{v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}}\langle
v,\mu_{0}\rangle\text{ s. t. }v(s)\leq
T_{(P_{0},r_{0})}^{\pi}v(s)-\alpha_{s}^{r}\lVert\pi_{s}\rVert\text{ for all
}s\in\operatorname{\mathcal{S}}.$

###### Proof.

We evaluate the support function:

$\displaystyle\sigma_{\mathcal{R}_{s}}(-\pi_{s})$
$\displaystyle=\max_{r_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}:\lVert
r_{s}\rVert\leq\alpha_{s}^{r}}\langle
r_{s},-\pi_{s}\rangle\overset{(1)}{=}\alpha_{s}^{r}\lVert-\pi_{s}\rVert=\alpha_{s}^{r}\lVert\pi_{s}\rVert,$

where equality $(1)$ holds by definition of the dual norm. Applying Thm. 3.1,
the robust value function $v^{\pi,\mathcal{U}}$ is the optimal solution of:
$\max_{v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}}\langle
v,\mu_{0}\rangle\text{ s. t.
}\alpha_{s}^{r}\lVert\pi_{s}\rVert+v(s)-T_{(P_{0},r_{0})}^{\pi}v(s)\leq
0\text{ for all }s\in\operatorname{\mathcal{S}},$ which concludes the proof.

Ball-constraint with arbitrary norm. In the case where reward ball-constraints
are defined according to an arbitrary norm $\lVert\cdot\rVert_{a}$ with dual
norm $\lVert\cdot\rVert_{a^{*}}$, the support function becomes:

$\displaystyle\sigma_{\mathcal{R}_{s}}(-\pi_{s})$
$\displaystyle=\max_{r_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}:\lVert
r_{s}\rVert_{a}\leq\alpha_{s}^{r}}\langle
r_{s},-\pi_{s}\rangle=\alpha_{s}^{r}\lVert-\pi_{s}\rVert_{a^{*}}=\alpha_{s}^{r}\lVert\pi_{s}\rVert_{a^{*}}.$

∎

###  A.4 Related Algorithms: Uncertainty sets from regularizers

Table 2: Summary table of existing policy regularizers and generalization to our R2 function.  |  Negative Shannon |  KL divergence |  Negative Tsallis |  R2 function
---|---|---|---|---
Regularizer $\Omega$ |  ∑_s∈Sπ_s(a)ln(π_s(a)) |  ∑_s∈Sπ_s(a)ln(πs(a)d(a)) |  12(∥π_s∥^2-1) |  ∥π_s∥ (α_s^r + α_s^P γ∥v∥)
Conjugate $\Omega^{*}$ |  ln(∑_a∈Ae^q_s(a)) |  ln(∑_a∈Ad(a)e^q_s(a)) |  12 \+ 12∑_a∈A (q_s(a)^2 - τ(q_s)^2) |  Not in closed-form
Gradient $\nabla\Omega^{*}$ |  π_s(a) = eqs(a)∑b∈Aeqs(b) |  π_s(a)= eqs(a)∑b∈Aeqs(b) |  π_s(a) = (q_s(a) - τ(q_s))_+ |  Not in closed-form
Reward Uncertainty |  $(s,a)$-rectangular |  $(s,a)$-rectangular |  $(s,a)$-rectangular |  $s$-rectangular
|  $\mathcal{R}_{s,a}^{\textsc{NS}}(\pi)=$ $\left[\ln\left(\frac{1}{\pi_{s}(a)}\right),+\infty\right)$ |  ln(d(a)) \+ R_s,a^NS(π) |  [1-πs(a)2, +∞) |  B_∥⋅∥(r_0_s, α_s^r)
Transition Uncertainty |  $(s,a)$-rectangular |  $(s,a)$-rectangular |  $(s,a)$-rectangular |  $s$-rectangular
|  {P_0(⋅|s,a)} |  {P_0(⋅|s,a)} |  {P_0(⋅|s,a)} |  B_∥⋅∥(P_0_s, α_s^P)

Negative Shannon entropy. Each $(s,a)$-reward uncertainty set is
$\mathcal{R}_{s,a}^{\textsc{NS}}(\pi):=\left[\ln\left(\nicefrac{{1}}{{\pi_{s}(a)}}\right),+\infty\right)$.
We compute the associated support function:

$\displaystyle\sigma_{\mathcal{R}_{s}^{\textsc{NS}}(\pi)}(-\pi_{s})$
$\displaystyle=\max_{r_{s}\in\mathcal{R}_{s}^{\textsc{NS}}(\pi)}\langle
r_{s},-\pi_{s}\rangle$
$\displaystyle=\max_{\begin{subarray}{c}r(s,a^{\prime}):r(s,a^{\prime})\in\mathcal{R}_{s,a^{\prime}}^{\textsc{NS}}(\pi),a^{\prime}\in\operatorname{\mathcal{A}}\end{subarray}}\sum_{a\in\operatorname{\mathcal{A}}}-r(s,a)\pi_{s}(a)$
$\displaystyle=\max_{\begin{subarray}{c}r(s,a^{\prime}):r(s,a^{\prime})\geq\ln\left(\nicefrac{{1}}{{\pi_{s}(a)}}\right),a^{\prime}\in\operatorname{\mathcal{A}}\end{subarray}}-\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)r(s,a)$
$\displaystyle=\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)\ln(\pi_{s}(a)),$
(7)

where the last equality results from the fact that $\pi_{s}\geq 0,$ and
$-r(s,a)\pi_{s}(a)$ is maximal when $r(s,a)$ is minimal. We thus obtain the
negative Shannon entropy.

KL divergence. Similarly, given $d\in\Delta_{\operatorname{\mathcal{A}}}$, let
$\mathcal{R}_{s,a}^{\textsc{KL}}(\pi):=\ln(d(a))+\mathcal{R}_{s,a}^{\textsc{NS}}(\pi)\quad\forall(s,a)\in\operatorname{\mathcal{X}}$.
Then

$\displaystyle\sigma_{\mathcal{R}_{s}^{\textsc{KL}}(\pi)}(-\pi_{s})$
$\displaystyle=\max_{\begin{subarray}{c}r(s,a^{\prime}):r(s,a^{\prime})\in\mathcal{R}_{s,a^{\prime}}^{\textsc{KL}}(\pi),a^{\prime}\in\operatorname{\mathcal{A}}\end{subarray}}\sum_{a\in\operatorname{\mathcal{A}}}-r(s,a)\pi_{s}(a)$
$\displaystyle=\max_{\begin{subarray}{c}r(s,a^{\prime})+\ln(d(a)):\\\
r(s,a^{\prime})\in\mathcal{R}_{s,a^{\prime}}^{\textsc{NS}}(\pi),a^{\prime}\in\operatorname{\mathcal{A}}\end{subarray}}\sum_{a\in\operatorname{\mathcal{A}}}-r(s,a)\pi_{s}(a)$
$\displaystyle=\max_{\begin{subarray}{c}r(s,a^{\prime}):\\\
r(s,a^{\prime})\in\mathcal{R}_{s,a^{\prime}}^{\textsc{NS}}(\pi),a^{\prime}\in\operatorname{\mathcal{A}}\end{subarray}}\sum_{a\in\operatorname{\mathcal{A}}}-(r(s,a)+\ln(d(a))\pi_{s}(a)$
$\displaystyle=\max_{\begin{subarray}{c}r(s,a^{\prime}):\\\
r(s,a^{\prime})\in\mathcal{R}_{s,a^{\prime}}^{\textsc{NS}}(\pi),a^{\prime}\in\operatorname{\mathcal{A}}\end{subarray}}\\{-\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)r(s,a)\\}-\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)\ln(d(a))$
$\displaystyle=\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)\ln(\pi_{s}(a))-\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)\ln(d(a)),$

where the last equality uses Eq. (A.4). We thus recover the KL divergence
$\Omega(\pi_{s})=\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)\ln\left(\nicefrac{{\pi_{s}(a)}}{{d(a)}}\right)$.

Negative Tsallis entropy. Given
$\mathcal{R}_{s,a}^{\textsc{T}}(\pi):=\left[\frac{1-\pi_{s}(a)}{2},+\infty\right)\quad\forall(s,a)\in\operatorname{\mathcal{X}}$,
we compute:

$\displaystyle\sigma_{\mathcal{R}_{s}^{\textsc{T}}(\pi)}(-\pi_{s})$
$\displaystyle=\max_{\begin{subarray}{c}r(s,a^{\prime}):r(s,a^{\prime})\in\mathcal{R}_{s,a^{\prime}}^{\textsc{T}}(\pi),a^{\prime}\in\operatorname{\mathcal{A}}\end{subarray}}\sum_{a\in\operatorname{\mathcal{A}}}-r(s,a)\pi_{s}(a)$
$\displaystyle=\max_{\begin{subarray}{c}r(s,a^{\prime}):r(s,a^{\prime})\in\left[\frac{1-\pi_{s}(a^{\prime})}{2},+\infty\right),a^{\prime}\in\operatorname{\mathcal{A}}\end{subarray}}\sum_{a\in\operatorname{\mathcal{A}}}-r(s,a)\pi_{s}(a)$
$\displaystyle=\sum_{a\in\operatorname{\mathcal{A}}}-\frac{1-\pi_{s}(a)}{2}\pi_{s}(a)$
(8)
$\displaystyle=-\frac{1}{2}\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)+\frac{1}{2}\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)^{2}=-\frac{1}{2}+\frac{1}{2}\lVert\pi_{s}\rVert^{2},$

where Eq. (A.4) also comes from the fact that $\pi_{s}\geq 0,$ and
$-r(s,a)\pi_{s}(a)$ is maximal when $r(s,a)$ is minimal. We thus obtain the
negative Tsallis entropy
$\Omega(\pi_{s})=\frac{1}{2}(\lVert\pi_{s}\rVert^{2}-1)$.

The reward uncertainty sets associated to both KL and Shannon entropy are
similar, as the former amounts to translating the latter by a negative
constant (translation to the left). As such, both yield reward values that can
be either positive or negative. This is not the case of the negative Tsallis,
as its minimal reward is $0$, attained for a deterministic action policy,
i.e., when $\pi_{s}(a)=1$.

Table 2 summarizes the properties of each regularizer. For the Tsallis
entropy, we denote by
$\tau:\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}\to\operatorname{\mathbb{R}}$
the function
$q_{s}\mapsto\frac{\sum_{a\in\mathfrak{A}(q_{s})}q_{s}(a)-1}{\lvert\mathfrak{A}(q_{s})\rvert}$,
where $\mathfrak{A}(q_{s})\subseteq\operatorname{\mathcal{A}}$ is a subset of
actions:
$\mathfrak{A}(q_{s})=\\{a\in\operatorname{\mathcal{A}}:1+iq_{s}(a_{(i)})>\sum_{j=0}^{i}q_{s}(a_{(j)}),i\in\\{1,\cdots,\lvert\operatorname{\mathcal{A}}\rvert\\}\\}$,
and $a_{(i)}\text{ is the action with the }i\text{-th maximal value }$[20].

###  A.5 Proof of Proposition 3.2

######  Proposition.

Assume that $\mathcal{U}=\\{P_{0}\\}\times(r_{0}+\mathcal{R})$ with
$\mathcal{R}_{s}=\\{r_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}:\lVert
r_{s}\rVert\leq\alpha_{s}^{r}\\}$. Then, the gradient of the reward-robust
objective $J_{\mathcal{U}}(\pi):=\langle v^{\pi,\mathcal{U}},\mu_{0}\rangle$
is given by

$\displaystyle\nabla
J_{\mathcal{U}}(\pi)=\mathbb{E}_{(s,a)\sim\mu_{\pi}}\left[\nabla\ln\pi_{s}(a)\left(q^{\pi,\mathcal{U}}(s,a)-\alpha_{s}^{r}\frac{\pi_{s}(a)}{\lVert\pi_{s}\rVert}\right)\right],$

where $\mu_{\pi}$ is the occupancy measure under the nominal model $P_{0}$ and
policy $\pi$.

We prove the following more general result. To establish Prop. 3.2, we then
set $\alpha_{s}^{P}=0$ and apply Thm. 4.1 to replace
$v^{\pi,\textsc{r\textsuperscript{2}}}=v_{\pi,\mathcal{U}}$ and
$q^{\pi,\textsc{r\textsuperscript{2}}}=q^{\pi,\mathcal{U}}$.

######  Theorem.

Set
$\Omega_{v,\textsc{r\textsuperscript{2}}}(\pi_{s}):=\lVert\pi_{s}\rVert(\alpha_{s}^{r}+\alpha_{s}^{P}\gamma\lVert
v\rVert)$. Then, the gradient of the R2 objective
$J_{\textsc{r\textsuperscript{2}}}(\pi):=\langle
v_{\pi,\textsc{r\textsuperscript{2}}},\mu_{0}\rangle$ is given by

$\displaystyle\nabla J_{\textsc{r\textsuperscript{2}}}(\pi)=\mathbb{E}_{s\sim
d_{\mu_{0},\pi}}\left[\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)\nabla\ln\pi_{s}(a)q^{\pi,\textsc{r\textsuperscript{2}}}(s,a)-\nabla\Omega_{v,\textsc{r\textsuperscript{2}}}(\pi_{s})\right],$

where
$d_{\mu_{0},\pi}:=\mu_{0}^{\top}(\mathbf{I}_{\operatorname{\mathcal{S}}}-\gamma
P_{0}^{\pi})^{-1}$, with
$\mu_{0}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}\times 1}$ the
initial state distribution.

###### Proof.

By linearity of the gradient operator, $\nabla
J_{\textsc{r\textsuperscript{2}}}(\pi)=\langle\nabla
v^{\pi,\textsc{r\textsuperscript{2}}},\mu_{0}\rangle.$ We thus need to compute
$\nabla v^{\pi,\textsc{r\textsuperscript{2}}}.$ Using the fixed point property
of $v^{\pi,\textsc{r\textsuperscript{2}}}$ w.r.t. the R2 Bellman operator
yields:

$\displaystyle\nabla v^{\pi,\textsc{r\textsuperscript{2}}}(s)$
$\displaystyle=$ $\displaystyle\nabla\left(r_{0}^{\pi}(s)+\gamma
P_{0}^{\pi}v^{\pi,\textsc{r\textsuperscript{2}}}(s)-\Omega_{v,\textsc{r\textsuperscript{2}}}(\pi_{s})\right)$
$\displaystyle=$
$\displaystyle\nabla\left(\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)(r_{0}(s,a)+\gamma\langle
P_{0}(\cdot|s,a),v^{\pi,\textsc{r\textsuperscript{2}}}\rangle)-\Omega_{v,\textsc{r\textsuperscript{2}}}(\pi_{s})\right)$
$\displaystyle=$
$\displaystyle\sum_{a\in\operatorname{\mathcal{A}}}\nabla\pi_{s}(a)\left(r_{0}(s,a)+\gamma\langle
P_{0}(\cdot|s,a),v^{\pi,\textsc{r\textsuperscript{2}}}\rangle\right)$
$\displaystyle\qquad+\gamma\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)\langle
P_{0}(\cdot|s,a),\nabla
v^{\pi,\textsc{r\textsuperscript{2}}}\rangle-\nabla\Omega_{v,\textsc{r\textsuperscript{2}}}(\pi_{s})$
$\displaystyle[\text{Linearity of gradient and product rule}]$
$\displaystyle=$
$\displaystyle\sum_{a\in\operatorname{\mathcal{A}}}\nabla\pi_{s}(a)q^{\pi,\textsc{r\textsuperscript{2}}}(s,a)+\gamma\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)\langle
P_{0}(\cdot|s,a),\nabla
v^{\pi,\textsc{r\textsuperscript{2}}}\rangle-\nabla\Omega_{v,\textsc{r\textsuperscript{2}}}(\pi_{s})$
$\displaystyle[q^{\pi,\textsc{r\textsuperscript{2}}}(s,a)=r_{0}(s,a)+\gamma\langle
P_{0}(\cdot|s,a),v^{\pi,\textsc{r\textsuperscript{2}}}\rangle]$
$\displaystyle=$
$\displaystyle\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)(\nabla\ln\pi_{s}(a)q^{\pi,\textsc{r\textsuperscript{2}}}(s,a)+\gamma\langle
P_{0}(\cdot|s,a),\nabla
v^{\pi,\textsc{r\textsuperscript{2}}}\rangle)-\nabla\Omega_{v,\textsc{r\textsuperscript{2}}}(\pi_{s})$
$\displaystyle[\nabla\pi_{s}=\pi_{s}\nabla\ln(\pi_{s})]$ $\displaystyle=$
$\displaystyle\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)(\nabla\ln\pi_{s}(a)q^{\pi,\textsc{r\textsuperscript{2}}}(s,a)-\nabla\Omega_{v,\textsc{r\textsuperscript{2}}}(\pi_{s})+\gamma\langle
P_{0}(\cdot|s,a),\nabla v^{\pi,\textsc{r\textsuperscript{2}}}\rangle).$

Thus, the components of $\nabla v^{\pi,\textsc{r\textsuperscript{2}}}$ are the
non-regularized value functions corresponding to the modified reward
$R(s,a):=\nabla\ln\pi_{s}(a)q^{\pi,\textsc{r\textsuperscript{2}}}(s,a)-\nabla\Omega_{v,\textsc{r\textsuperscript{2}}}(\pi_{s})$.
By the fixed point property of the standard Bellman operator, it results that:

$\displaystyle\nabla v^{\pi,\textsc{r\textsuperscript{2}}}(s)$
$\displaystyle=(\mathbf{I}_{\operatorname{\mathcal{S}}}-\gamma
P_{0}^{\pi})^{-1}\left(\sum_{a\in\operatorname{\mathcal{A}}}\pi_{\cdot}(a)(\nabla\ln\pi_{\cdot}(a)q^{\pi,\textsc{r\textsuperscript{2}}}({\cdot},a)-\nabla\Omega_{v,\textsc{r\textsuperscript{2}}}(\pi_{\cdot}))\right)(s)$

and

$\displaystyle\nabla J_{\textsc{r\textsuperscript{2}}}(\pi)$
$\displaystyle=\sum_{s\in\operatorname{\mathcal{S}}}\mu_{0}(s)\nabla
v^{\pi,\textsc{r\textsuperscript{2}}}(s)$
$\displaystyle=\sum_{s\in\operatorname{\mathcal{S}}}\mu_{0}(s)(\mathbf{I}_{\operatorname{\mathcal{S}}}-\gamma
P_{0}^{\pi})^{-1}\left(\sum_{a\in\operatorname{\mathcal{A}}}\pi_{\cdot}(a)(\nabla\ln\pi_{\cdot}(a)q^{\pi,\textsc{r\textsuperscript{2}}}({\cdot},a)-\nabla\Omega_{v,\textsc{r\textsuperscript{2}}}(\pi_{\cdot}))\right)(s)$
$\displaystyle=\sum_{s\in\operatorname{\mathcal{S}}}d_{\mu_{0},\pi}(s)\left(\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)\nabla\ln\pi_{s}(a)q^{\pi,\textsc{r\textsuperscript{2}}}(s,a)-\nabla\Omega_{v,\textsc{r\textsuperscript{2}}}(\pi_{s})\right),$

by definition of $d_{\mu_{0},\pi}$. ∎

The subtraction by $\nabla\Omega_{v,\textsc{r\textsuperscript{2}}}(\pi_{s})$
also appears in [10]. However, here, the gradient includes partial derivatives
that depend on both the policy and the value itself. Let’s try to compute the
gradient of the double regularizer
$\Omega_{v,\textsc{r\textsuperscript{2}}}(\pi_{s})=\lVert\pi_{s}\rVert(\alpha_{s}^{r}+\alpha_{s}^{P}\gamma\lVert
v^{\pi,\textsc{r\textsuperscript{2}}}\rVert)$. By the chain-rule we have that:

$\displaystyle\nabla\Omega_{v,\textsc{r\textsuperscript{2}}}(\pi_{s})$
$\displaystyle=\sum_{a\in\operatorname{\mathcal{A}}}\frac{\partial\Omega_{v,\textsc{r\textsuperscript{2}}}}{\partial\pi_{s}(a)}\nabla\pi_{s}(a)+\sum_{s\in\operatorname{\mathcal{S}}}\frac{\partial\Omega_{v,\textsc{r\textsuperscript{2}}}}{\partial
v^{\pi,\textsc{r\textsuperscript{2}}}(s)}\nabla
v^{\pi,\textsc{r\textsuperscript{2}}}(s)$
$\displaystyle=\sum_{a\in\operatorname{\mathcal{A}}}(\alpha_{s}^{r}+\alpha_{s}^{P}\gamma\lVert
v^{\pi,\textsc{r\textsuperscript{2}}}\rVert)\frac{\pi_{s}(a)}{\lVert\pi_{s}\rVert}\nabla\pi_{s}(a)+\sum_{s\in\operatorname{\mathcal{S}}}\alpha_{s}^{P}\gamma\lVert\pi_{s}\rVert\frac{v^{\pi,\textsc{r\textsuperscript{2}}}(s)}{\lVert
v^{\pi,\textsc{r\textsuperscript{2}}}\rVert}\nabla
v^{\pi,\textsc{r\textsuperscript{2}}}(s)$
$\displaystyle=\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)\left(\frac{\alpha_{s}^{r}+\alpha_{s}^{P}\gamma\lVert
v^{\pi,\textsc{r\textsuperscript{2}}}\rVert}{\lVert\pi_{s}\rVert}\nabla\pi_{s}(a)+\sum_{s\in\operatorname{\mathcal{S}}}\alpha_{s}^{P}\gamma\lVert\pi_{s}\rVert\frac{q^{\pi,\textsc{r\textsuperscript{2}}}(s,a)}{\lVert
v^{\pi,\textsc{r\textsuperscript{2}}}\rVert}\nabla
v^{\pi,\textsc{r\textsuperscript{2}}}(s)\right).$

We remark here an interdependence between
$\nabla\Omega_{v,\textsc{r\textsuperscript{2}}}(\pi_{s})$ and $\nabla
v^{\pi,\textsc{r\textsuperscript{2}}}(s)$: computing the gradient
$\nabla\Omega_{v,\textsc{r\textsuperscript{2}}}(\pi_{s})$ requires to know
$\nabla v^{\pi,\textsc{r\textsuperscript{2}}}(s)$ and vice versa. There may be
a recursion that still enables to compute these gradients, which we leave for
future work.

##  Appendix B General robust MDPs

###  B.1 Proof of Theorem 4.1

######  Theorem (General robust MDP).

Assume that $\mathcal{U}=(P_{0}+\mathcal{P})\times(r_{0}+\mathcal{R})$. Then,
for any policy
$\pi\in\Delta_{\operatorname{\mathcal{A}}}^{\operatorname{\mathcal{S}}}$, the
robust value function $v^{\pi,\mathcal{U}}$ is the optimal solution of the
convex optimization problem:

$\displaystyle\max_{v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}}\langle
v,\mu_{0}\rangle\text{ s. t. }v(s)\leq
T_{(P_{0},r_{0})}^{\pi}v(s)-\sigma_{\mathcal{R}_{s}}(-\pi_{s})-\sigma_{\mathcal{P}_{s}}(-\gamma
v\cdot\pi_{s})\text{ for all }s\in\operatorname{\mathcal{S}},$

where
$[v\cdot\pi_{s}](s^{\prime},a):=v(s^{\prime})\pi_{s}(a)\quad\forall(s^{\prime},a)\in\operatorname{\mathcal{X}}$.

###### Proof.

The robust value function $v^{\pi,\mathcal{U}}$ is the optimal solution of:

$\displaystyle\max_{v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}}\langle
v,\mu_{0}\rangle\text{ s. t. }F(s)\leq 0\text{ for all
}s\in\operatorname{\mathcal{S}},$ (9)

where $F(s):=\max_{(P,r)\in\mathcal{U}}\left\\{v(s)-r^{\pi}(s)-\gamma
P^{\pi}v(s)\right\\}$ is the robust counterpart of (PU) at
$s\in\operatorname{\mathcal{S}}$. Let’s compute it based on the structure of
the uncertainty set
$\mathcal{U}=(P_{0}+\mathcal{P})\times(r_{0}+\mathcal{R})$:

$\displaystyle F(s)$
$\displaystyle=\max_{(P^{\prime},r^{\prime})\in(P_{0}+\mathcal{P})\times(r_{0}+\mathcal{R})}\left\\{v(s)-r^{\prime\pi}(s)-\gamma
P^{\prime\pi}v(s)\right\\}$
$\displaystyle=\max_{\begin{subarray}{c}P^{\prime}:P^{\prime}=P_{0}+P,P\in\mathcal{P}\\\
r^{\prime}:r^{\prime}=r_{0}+r,r\in\mathcal{R}\end{subarray}}\left\\{v(s)-r^{\prime\pi}(s)-\gamma
P^{\prime\pi}v(s)\right\\}$
$\displaystyle=\max_{P\in\mathcal{P},r\in\mathcal{R}}\left\\{v(s)-(r_{0}^{\pi}(s)+r^{\pi}(s))-\gamma(P_{0}^{\pi}+P^{\pi})v(s)\right\\}$
$\displaystyle[(P_{0}+P)^{\pi}=P_{0}^{\pi}+P^{\pi},$
$\displaystyle(r_{0}+r)^{\pi}=r_{0}^{\pi}+r^{\pi}]$
$\displaystyle=\max_{P\in\mathcal{P},r\in\mathcal{R}}\left\\{v(s)-r_{0}^{\pi}(s)-r^{\pi}(s)-\gamma
P_{0}^{\pi}v(s)-\gamma P^{\pi}v(s)\right\\}$
$\displaystyle=\max_{P\in\mathcal{P},r\in\mathcal{R}}\left\\{v(s)-T_{(P_{0},r_{0})}^{\pi}v(s)-r^{\pi}(s)-\gamma
P^{\pi}v(s)\right\\}$
$\displaystyle[T_{(P_{0},r_{0})}^{\pi}v(s)=r_{0}^{\pi}(s)+\gamma
P_{0}^{\pi}v(s)]$ $\displaystyle=\max_{P\in\mathcal{P}}\\{-\gamma
P^{\pi}v(s)\\}+\max_{r\in\mathcal{R}}\\{-r^{\pi}(s)\\}+v(s)-T_{(P_{0},r_{0})}^{\pi}v(s)$
$\displaystyle=-\min_{P\in\mathcal{P}}\\{\gamma
P^{\pi}v(s)\\}-\min_{r\in\mathcal{R}}\\{r^{\pi}(s)\\}+v(s)-T_{(P_{0},r_{0})}^{\pi}v(s)$
$\displaystyle=-\min_{P\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}\times\operatorname{\mathcal{S}}}}\\{\gamma
P^{\pi}v(s)+\delta_{\mathcal{P}}(P)\\}-\min_{r\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}}\\{r^{\pi}(s)+\delta_{\mathcal{R}}(r)\\}$
$\displaystyle\qquad+v(s)-T_{(P_{0},r_{0})}^{\pi}v(s)$
$\displaystyle=-\min_{P\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}\times\operatorname{\mathcal{S}}}}\\{\gamma\langle
P^{\pi}_{s},v\rangle+\delta_{\mathcal{P}}(P)\\}-\min_{r\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}}\\{\langle
r_{s},\pi_{s}\rangle+\delta_{\mathcal{R}}(r)\\}$
$\displaystyle\qquad+v(s)-T_{(P_{0},r_{0})}^{\pi}v(s).$
$\displaystyle[P^{\pi}v(s)=\langle P^{\pi}_{s},v\rangle,r^{\pi}(s)=\langle
r_{s},\pi_{s}\rangle]$

As shown in the proof of Thm. 3.1,
$\min_{r\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}}\\{\langle
r_{s},\pi_{s}\rangle+\delta_{\mathcal{R}}(r)\\}=\min_{r_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}}\\{\langle
r_{s},\pi_{s}\rangle+\delta_{\mathcal{R}_{s}}(r_{s})\\}$ thanks to the
rectangularity assumption. Similarly, by rectangularity of the transition
uncertainty set, for all
$P:=(P_{s})_{s\in\operatorname{\mathcal{S}}}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}$,
we have
$\delta_{\mathcal{P}}(P)=\sum_{s^{\prime}\in\operatorname{\mathcal{S}}}\delta_{\mathcal{P}_{s^{\prime}}}(P_{s^{\prime}})$.
As such,

$\displaystyle\min_{P\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}\times\operatorname{\mathcal{S}}}}\\{\gamma\langle
P^{\pi}_{s},v\rangle+\delta_{\mathcal{P}}(P)\\}$
$\displaystyle=\min_{P\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}\times\operatorname{\mathcal{S}}}}\\{\gamma\langle
P^{\pi}_{s},v\rangle+\sum_{s^{\prime}\in\operatorname{\mathcal{S}}}\delta_{\mathcal{P}_{s^{\prime}}}(P_{s^{\prime}})\\}$
$\displaystyle=\min_{P_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}}\\{\gamma\langle
P^{\pi}_{s},v\rangle+\delta_{\mathcal{P}_{s}}(P_{s})\\},$

where the last equality holds since the objective function is minimal if and
only if $P_{s}\in\mathcal{P}_{s}$. Finally,

$\displaystyle F(s)$
$\displaystyle=-\min_{P_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}}\\{\gamma\langle
P^{\pi}_{s},v\rangle+\delta_{\mathcal{P}_{s}}(P_{s})\\}-\min_{r_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}}\\{\langle
r_{s},\pi_{s}\rangle+\delta_{\mathcal{R}_{s}}(r_{s})\\}+v(s)-T_{(P_{0},r_{0})}^{\pi}v(s).$

Referring to the proof of Thm. 3.1, we know that
$-\min_{r\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}}\\{\langle
r_{s},\pi_{s}\rangle+\delta_{\mathcal{R}}(r)\\}=\sigma_{\mathcal{R}_{s}}(-\pi_{s})$,
so

$\displaystyle F(s)$
$\displaystyle=-\min_{P_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}}\\{\gamma\langle
P^{\pi}_{s},v\rangle+\delta_{\mathcal{P}_{s}}(P_{s})\\}+\sigma_{\mathcal{R}_{s}}(-\pi_{s})+v(s)-T_{(P_{0},r_{0})}^{\pi}v(s).$

Let the matrix
$v\cdot\pi_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}$
defined as $[v\cdot\pi_{s}](s^{\prime},a):=v(s^{\prime})\pi_{s}(a)$ for all
$(s^{\prime},a)\in\operatorname{\mathcal{X}}$. Further define
$\varphi(P_{s}):=\gamma\langle P^{\pi}_{s},v\rangle$, which we can rewrite as
$\varphi(P_{s})=\gamma\langle P_{s},v\cdot\pi_{s}\rangle.$ Then, we have that:

$\displaystyle\min_{P_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}}\\{\gamma\langle
P^{\pi}_{s},v\rangle+\delta_{\mathcal{P}_{s}}(P_{s})\\}=\min_{P_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}}\\{\varphi(P_{s})+\delta_{\mathcal{P}_{s}}(P_{s})\\}=-\min_{\operatorname{\mathbf{B}}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}}\\{\varphi^{*}(-\operatorname{\mathbf{B}})+\sigma_{\mathcal{P}_{s}}(\operatorname{\mathbf{B}})\\},$

where the last equality results from Fenchel-Rockafellar duality and the fact
that $(\delta_{\mathcal{P}_{s}})^{*}=\sigma_{\mathcal{P}_{s}}$. It thus
remains to compute the convex conjugate of $\varphi$:

$\displaystyle\varphi^{*}(-\operatorname{\mathbf{B}})$
$\displaystyle=\max_{P_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}}\left\\{\langle
P_{s},-\operatorname{\mathbf{B}}\rangle-\varphi(P_{s})\right\\}$
$\displaystyle=\max_{P_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}}\left\\{\langle
P_{s},-\operatorname{\mathbf{B}}\rangle-\gamma\langle
P_{s},v\cdot\pi_{s}\rangle\right\\}$
$\displaystyle=\max_{P_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}}\langle
P_{s},-\operatorname{\mathbf{B}}-\gamma v\cdot\pi_{s}\rangle$
$\displaystyle=\begin{cases}0\text{ if }-\operatorname{\mathbf{B}}-\gamma
v\cdot\pi_{s}=0\\\ +\infty\text{ otherwise},\end{cases}$

which yields
$\min_{\operatorname{\mathbf{B}}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}}\\{\varphi^{*}(-\operatorname{\mathbf{B}})+\sigma_{\mathcal{P}_{s}}(\operatorname{\mathbf{B}})\\}=\sigma_{\mathcal{P}_{s}}(-\gamma
v\cdot\pi_{s})$. Finally, the robust counterpart rewrites as:
$F(s)=\sigma_{\mathcal{P}_{s}}(-\gamma
v\cdot\pi_{s})+\sigma_{\mathcal{R}_{s}}(-\pi_{s})+v(s)-T_{(P_{0},r_{0})}^{\pi}v(s),$
and plugging it into the optimization problem (9) yields the desired result. ∎

###  B.2 Proof of Corollary 4.1

######  Corollary.

Assume that $\mathcal{U}=(P_{0}+\mathcal{P})\times(r_{0}+\mathcal{R})$ with
$\mathcal{P}_{s}:=\\{P_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}:\lVert
P_{s}\rVert\leq\alpha_{s}^{P}\\}$ and
$\mathcal{R}_{s}:=\\{r_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}:\lVert
r_{s}\rVert\leq\alpha_{s}^{r}\\}$ for all $s\in\operatorname{\mathcal{S}}$.
Then, the robust value function $v^{\pi,\mathcal{U}}$ is the optimal solution
of the convex optimization problem:

$\displaystyle\max_{v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}}\langle
v,\mu_{0}\rangle\text{ s. t. }v(s)\leq
T_{(P_{0},r_{0})}^{\pi}v(s)-\alpha_{s}^{r}\lVert\pi_{s}\rVert-\alpha_{s}^{P}\gamma\lVert
v\rVert\lVert\pi_{s}\rVert\text{ for all }s\in\operatorname{\mathcal{S}}.$

###### Proof.

As we already showed in Cor. 3.1, the support function of the reward
uncertainty set is
$\sigma_{\mathcal{R}_{s}}(-\pi_{s})=\alpha_{s}^{r}\lVert\pi_{s}\rVert.$ For
the transition uncertainty set, we similarly have:

$\displaystyle\sigma_{\mathcal{P}_{s}}(-\gamma v\cdot\pi_{s})$
$\displaystyle=\max_{\begin{subarray}{c}P_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}:\\\
\lVert P_{s}\rVert\leq\alpha_{s}^{P}\end{subarray}}\langle P_{s},-\gamma
v\cdot\pi_{s}\rangle$ $\displaystyle=\alpha_{s}^{P}\lVert-\gamma
v\cdot\pi_{s}\rVert$ $\displaystyle=\alpha_{s}^{P}\gamma\lVert
v\cdot\pi_{s}\rVert$ $\displaystyle=\alpha_{s}^{P}\gamma\lVert
v\rVert\lVert\pi_{s}\rVert.$ $\displaystyle[\lVert
v\cdot\pi_{s}\rVert^{2}=\sum_{(s^{\prime},a)\in\operatorname{\mathcal{X}}}(v(s^{\prime})\pi_{s}(a))^{2}$
$\displaystyle=\sum_{s^{\prime}\in\operatorname{\mathcal{S}}}v(s^{\prime})^{2}\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)^{2}=\lVert
v\rVert^{2}\lVert\pi_{s}\rVert^{2}]$

Now we apply Thm. 3.1 and replace each support function by their explicit form
to get that the robust value function $v^{\pi,\mathcal{U}}$ is the optimal
solution of:

$\displaystyle\max_{v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}}\langle
v,\mu_{0}\rangle\text{ s. t. }v(s)\leq
T_{(P_{0},r_{0})}^{\pi}v(s)-\alpha_{s}^{r}\lVert\pi_{s}\rVert-\alpha_{s}^{P}\lVert\pi_{s}\rVert\cdot\gamma\lVert
v\rVert\text{ for all }s\in\operatorname{\mathcal{S}}.$

Ball-constraints with arbitrary norms. As seen in the proof of Thm. 3.1 and
Cor. 3.1, for ball-constrained rewards defined with an arbitrary norm
$\lVert\cdot\rVert_{a}$ of dual $\lVert\cdot\rVert_{a^{*}}$, the corresponding
support function is
$\sigma_{\mathcal{R}_{s}}(-\pi_{s})=\alpha_{s}^{r}\lVert\pi_{s}\rVert_{a^{*}}.$
Similarly, for ball-constrained transitions based on a norm
$\lVert\cdot\rVert_{b}$ of dual $\lVert\cdot\rVert_{b^{*}}$, we have:

$\displaystyle\sigma_{\mathcal{P}_{s}}(-\gamma v\cdot\pi_{s})$
$\displaystyle=\max_{\begin{subarray}{c}P_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}}:\\\
\lVert P_{s}\rVert_{b}\leq\alpha_{s}^{P}\end{subarray}}\langle P_{s},-\gamma
v\cdot\pi_{s}\rangle=\alpha_{s}^{P}\lVert-\gamma v\cdot\pi_{s}\rVert_{b^{*}},$

in which case the robust value function $v^{\pi,\mathcal{U}}$ is the optimal
solution of:

$\displaystyle\max_{v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}}\langle
v,\mu_{0}\rangle\text{ s. t. }v(s)\leq
T_{(P_{0},r_{0})}^{\pi}v(s)-\alpha_{s}^{r}\lVert\pi_{s}\rVert_{a^{*}}-\alpha_{s}^{P}\lVert-\gamma
v\cdot\pi_{s}\rVert_{b^{*}}\text{ for all }s\in\operatorname{\mathcal{S}}.$

∎

##  Appendix C R2 MDPs

###  C.1 Proof of Proposition 5.1

######  Proposition.

Suppose that Asm. 5.1 holds. Then, we have the following properties:
(i) Monotonicity: For all
$v_{1},v_{2}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}$ such
that $v_{1}\leq v_{2}$, we have
$T^{\pi,\textsc{r\textsuperscript{2}}}v_{1}\leq
T^{\pi,\textsc{r\textsuperscript{2}}}v_{2}$ and
$T^{*,\textsc{r\textsuperscript{2}}}v_{1}\leq
T^{*,\textsc{r\textsuperscript{2}}}v_{2}$.
(ii) Sub-distributivity: For all
$v_{1}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}},c\in\operatorname{\mathbb{R}}$,
we have
$T^{\pi,\textsc{r\textsuperscript{2}}}(v_{1}+c\mathbbm{1}_{\operatorname{\mathcal{S}}})\leq
T^{\pi,\textsc{r\textsuperscript{2}}}v_{1}+\gamma
c\mathbbm{1}_{\operatorname{\mathcal{S}}}$ and
$T^{*,\textsc{r\textsuperscript{2}}}(v_{1}+c\mathbbm{1}_{\operatorname{\mathcal{S}}})\leq
T^{*,\textsc{r\textsuperscript{2}}}v_{1}+\gamma
c\mathbbm{1}_{\operatorname{\mathcal{S}}}$, $\forall
c\in\operatorname{\mathbb{R}}$.
(iii) Contraction: Let
$\epsilon_{*}:=\min_{s\in\operatorname{\mathcal{S}}}\epsilon_{s}>0$. Then, for
all $v_{1},v_{2}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}$,
$\lVert
T^{\pi,\textsc{r\textsuperscript{2}}}v_{1}-T^{\pi,\textsc{r\textsuperscript{2}}}v_{2}\rVert_{\infty}\leq(1-\epsilon_{*})\lVert
v_{1}-v_{2}\rVert_{\infty}$ and $\lVert
T^{*,\textsc{r\textsuperscript{2}}}v_{1}-T^{*,\textsc{r\textsuperscript{2}}}v_{2}\rVert_{\infty}\leq(1-\epsilon_{*})\lVert
v_{1}-v_{2}\rVert_{\infty}$.

###### Proof.

Proof of (i).  Consider the evaluation operator and let
$v_{1},v_{2}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}$ such
that $v_{1}\leq v_{2}$. For all $s\in\operatorname{\mathcal{S}}$,

$\displaystyle[T^{\pi,\textsc{r\textsuperscript{2}}}v_{1}-T^{\pi,\textsc{r\textsuperscript{2}}}v_{2}](s)$
$\displaystyle=T_{(P_{0},r_{0})}^{\pi}v_{1}(s)-\alpha_{s}^{r}\lVert\pi_{s}\rVert-\alpha_{s}^{P}\gamma\lVert
v_{1}\rVert\lVert\pi_{s}\rVert$
$\displaystyle\qquad-(T_{(P_{0},r_{0})}^{\pi}v_{2}(s)-\alpha_{s}^{r}\lVert\pi_{s}\rVert-\alpha_{s}^{P}\gamma\lVert
v_{2}\rVert\lVert\pi_{s}\rVert)$
$\displaystyle=T_{(P_{0},r_{0})}^{\pi}v_{1}(s)-T_{(P_{0},r_{0})}^{\pi}v_{2}(s)+\alpha_{s}^{P}\gamma\lVert\pi_{s}\rVert(\lVert
v_{2}\rVert-\lVert v_{1}\rVert)$ $\displaystyle=\gamma
P_{0}^{\pi}(v_{1}-v_{2})(s)+\alpha_{s}^{P}\gamma\lVert\pi_{s}\rVert(\lVert
v_{2}\rVert-\lVert v_{1}\rVert)$
$\displaystyle=\gamma\langle\pi_{s},{P_{0}}_{s}(v_{1}-v_{2})\rangle+\alpha_{s}^{P}\gamma\lVert\pi_{s}\rVert(\lVert
v_{2}\rVert-\lVert v_{1}\rVert)$ $\displaystyle[\forall
v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}},P_{0}^{\pi}v(s)=\sum_{(s^{\prime},a)\in\operatorname{\mathcal{X}}}\pi_{s}(a)P_{0}(s^{\prime}|s,a)v(s^{\prime})$
$\displaystyle=\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)[{P_{0}}_{s}v](a)=\langle\pi_{s},{P_{0}}_{s}v\rangle]$
$\displaystyle=\gamma\lVert\pi_{s}\rVert\left(\left\langle\frac{\pi_{s}}{\lVert\pi_{s}\rVert},{P_{0}}_{s}(v_{1}-v_{2})\right\rangle+\alpha_{s}^{P}(\lVert
v_{2}\rVert-\lVert v_{1}\rVert)\right)$
$\displaystyle\leq\gamma\lVert\pi_{s}\rVert\left(\left\langle\frac{\pi_{s}}{\lVert\pi_{s}\rVert},{P_{0}}_{s}(v_{1}-v_{2})\right\rangle+\alpha_{s}^{P}(\lVert
v_{2}-v_{1}\rVert)\right)$ $\displaystyle[\forall
v,w\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}},\lVert
v\rVert-\lVert w\rVert\leq\left\lvert\lVert v\rVert-\lVert
w\rVert\right\rvert\leq\lVert v-w\rVert].$

By Asm. 5.1, we also have

$\displaystyle\alpha_{s}^{P}$
$\displaystyle\leq\min_{\begin{subarray}{c}\mathbf{u}_{\operatorname{\mathcal{A}}}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}_{+},\lVert\mathbf{u}_{\operatorname{\mathcal{A}}}\rVert=1\\\
\mathbf{v}_{\operatorname{\mathcal{S}}}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}_{+},\lVert\mathbf{v}_{\operatorname{\mathcal{S}}}\rVert=1\end{subarray}}\mathbf{u}_{\operatorname{\mathcal{A}}}^{\top}P_{0}(\cdot|s,\cdot)\mathbf{v}_{\operatorname{\mathcal{S}}}$
$\displaystyle=\min_{\begin{subarray}{c}\mathbf{u}_{\operatorname{\mathcal{A}}}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}}_{+},\lVert\mathbf{u}_{\operatorname{\mathcal{A}}}\rVert=1\\\
\mathbf{v}_{\operatorname{\mathcal{S}}}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}_{+},\lVert\mathbf{v}_{\operatorname{\mathcal{S}}}\rVert=1\end{subarray}}\left\langle\mathbf{u}_{\operatorname{\mathcal{A}}},P_{0}(\cdot|s,\cdot)\mathbf{v}_{\operatorname{\mathcal{S}}}\right\rangle$
$\displaystyle\leq\left\langle\frac{\pi_{s}}{\lVert\pi_{s}\rVert},P_{0}(\cdot|s,\cdot)\frac{(v_{2}-v_{1})}{\lVert
v_{2}-v_{1}\rVert}\right\rangle,$

so that

$\displaystyle[T^{\pi,\textsc{r\textsuperscript{2}}}v_{1}-T^{\pi,\textsc{r\textsuperscript{2}}}v_{2}](s)$
$\displaystyle\leq\gamma\lVert\pi_{s}\rVert\left(\left\langle\frac{\pi_{s}}{\lVert\pi_{s}\rVert},{P_{0}}_{s}(v_{1}-v_{2})\right\rangle+\left\langle\frac{\pi_{s}}{\lVert\pi_{s}\rVert},P_{0}(\cdot|s,\cdot)\frac{(v_{2}-v_{1})}{\lVert
v_{2}-v_{1}\rVert}\right\rangle\lVert v_{2}-v_{1}\rVert\right)$
$\displaystyle=\gamma\lVert\pi_{s}\rVert\left(\left\langle\frac{\pi_{s}}{\lVert\pi_{s}\rVert},{P_{0}}_{s}(v_{1}-v_{2})\right\rangle+\left\langle\frac{\pi_{s}}{\lVert\pi_{s}\rVert},P_{0}(\cdot|s,\cdot)(v_{2}-v_{1})\right\rangle\right)=0,$

where we switch notations to designate
$P_{0}(\cdot|s,\cdot)={P_{0}}_{s}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{A}}\times\operatorname{\mathcal{S}}}$.
This proves monotonicity.

Proof of (ii).  We now prove the sub-distributivity of the evaluation
operator. Let
$v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}},c\in\operatorname{\mathbb{R}}$.
For all $s\in\operatorname{\mathcal{S}}$,

$\displaystyle[T^{\pi,\textsc{r\textsuperscript{2}}}(v+c\mathbbm{1}_{\operatorname{\mathcal{S}}})](s)$
$\displaystyle=$
$\displaystyle[T_{(P_{0},r_{0})}^{\pi}(v+c\mathbbm{1}_{\operatorname{\mathcal{S}}})](s)-\alpha_{s}^{r}\lVert\pi_{s}\rVert-\alpha_{s}^{P}\gamma\lVert
v+c\mathbbm{1}_{\operatorname{\mathcal{S}}}\rVert\lVert\pi_{s}\rVert$
$\displaystyle=$ $\displaystyle T_{(P_{0},r_{0})}^{\pi}v(s)+\gamma
c-\alpha_{s}^{r}\lVert\pi_{s}\rVert-\alpha_{s}^{P}\gamma\lVert
v+c\mathbbm{1}_{\operatorname{\mathcal{S}}}\rVert\lVert\pi_{s}\rVert$
$\displaystyle[T_{(P_{0},r_{0})}^{\pi}(v+c\mathbbm{1}_{\operatorname{\mathcal{S}}})=T_{(P_{0},r_{0})}^{\pi}v+\gamma
c\mathbbm{1}_{\operatorname{\mathcal{S}}}]$ $\displaystyle\leq$ $\displaystyle
T_{(P_{0},r_{0})}^{\pi}v(s)+\gamma
c-\alpha_{s}^{r}\lVert\pi_{s}\rVert-\alpha_{s}^{P}\gamma\lVert\pi_{s}\rVert(\lVert
v\rVert+\lVert c\mathbbm{1}_{\operatorname{\mathcal{S}}}\rVert)$
$\displaystyle=$ $\displaystyle T_{(P_{0},r_{0})}^{\pi}v(s)+\gamma
c-\alpha_{s}^{r}\lVert\pi_{s}\rVert-\alpha_{s}^{P}\gamma\lVert\pi_{s}\rVert\lVert
v\rVert$ $\displaystyle\qquad-\alpha_{s}^{P}\gamma\lVert\pi_{s}\rVert\lVert
c\mathbbm{1}_{\operatorname{\mathcal{S}}}\rVert$ $\displaystyle=$
$\displaystyle[T^{\pi,\textsc{r\textsuperscript{2}}}v](s)+\gamma
c-\alpha_{s}^{P}\gamma\lVert\pi_{s}\rVert\lVert
c\mathbbm{1}_{\operatorname{\mathcal{S}}}\rVert$ $\displaystyle\leq$
$\displaystyle[T^{\pi,\textsc{r\textsuperscript{2}}}v](s)+\gamma c.$
$\displaystyle[\gamma>0,\alpha_{s}^{P}>0,\lVert\cdot\rVert\geq 0]$

Proof of (iii).  We prove the contraction of a more general evaluation
operator with $\ell_{p}$ regularization, $p\geq 1$. This will establish
contraction of the R2 operator $T^{\pi,\textsc{r\textsuperscript{2}}}$ by
simply setting $p=2$. Define as $q$ the conjugate value of $p$, i.e., such
that $\frac{1}{p}+\frac{1}{q}=1$. As seen in the proof of Thm. 4.1, for balls
that are constrained according to the $\ell_{p}$-norm $\lVert\cdot\rVert_{p}$,
the robust value function $v^{\pi,\mathcal{U}}$ is the optimal solution of:

$\displaystyle\max_{v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}}\langle
v,\mu_{0}\rangle\text{ s. t. }v(s)\leq
T_{(P_{0},r_{0})}^{\pi}v(s)-\alpha_{s}^{r}\lVert\pi_{s}\rVert_{q}-\alpha_{s}^{P}\lVert-\gamma
v\cdot\pi_{s}\rVert_{q}\text{ for all }s\in\operatorname{\mathcal{S}},$

because $\lVert\cdot\rVert_{q}$ is the dual norm of $\lVert\cdot\rVert_{p}$,
and we can define the R2 operator accordingly:

$\displaystyle[T^{\pi,\textsc{r\textsuperscript{2}}}_{q}v](s):=T_{(P_{0},r_{0})}^{\pi}v(s)-\alpha_{s}^{r}\lVert\pi_{s}\rVert_{q}-\alpha_{s}^{P}\gamma\lVert
v\cdot\pi_{s}\rVert_{q}\quad\forall
v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}},s\in\operatorname{\mathcal{S}}.$

We make the following assumption:

######  Assumption (Aq).

For all $s\in\operatorname{\mathcal{S}}$, there exists $\epsilon_{s}>0$ such
that
$\alpha_{s}^{P}\leq\frac{1-\gamma-\epsilon_{s}}{\gamma\lvert\operatorname{\mathcal{S}}\rvert^{\frac{1}{q}}}.$

Let $v_{1},v_{2}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}$.
For all $s\in\operatorname{\mathcal{S}}$,

$\displaystyle\left\lvert[T_{q}^{\pi,\textsc{r\textsuperscript{2}}}v_{1}](s)-[T_{q}^{\pi,\textsc{r\textsuperscript{2}}}v_{2}](s)\right\rvert$
$\displaystyle=$ $\displaystyle\mid
T_{(P_{0},r_{0})}^{\pi}v_{1}(s)-\alpha_{s}^{r}\lVert\pi_{s}\rVert_{q}-\alpha_{s}^{P}\gamma\lVert
v_{1}\cdot\pi_{s}\rVert_{q}$
$\displaystyle\qquad-(T_{(P_{0},r_{0})}^{\pi}v_{2}(s)-\alpha_{s}^{r}\lVert\pi_{s}\rVert_{q}-\alpha_{s}^{P}\gamma\lVert
v_{2}\cdot\pi_{s}\rVert_{q})\mid$ $\displaystyle=$ $\displaystyle\left\lvert
T_{(P_{0},r_{0})}^{\pi}v_{1}(s)-T_{(P_{0},r_{0})}^{\pi}v_{2}(s)\right\rvert+\left\lvert\alpha_{s}^{P}\gamma(\lVert
v_{2}\cdot\pi_{s}\rVert_{q}-\lVert v_{1}\cdot\pi_{s}\rVert_{q})\right\rvert$
$\displaystyle=$ $\displaystyle\left\lvert
T_{(P_{0},r_{0})}^{\pi}v_{1}(s)-T_{(P_{0},r_{0})}^{\pi}v_{2}(s)\right\rvert+\alpha_{s}^{P}\gamma\left\lvert\lVert
v_{2}\cdot\pi_{s}\rVert_{q}-\lVert v_{1}\cdot\pi_{s}\rVert_{q}\right\rvert$
$\displaystyle\leq$ $\displaystyle\left\lvert
T_{(P_{0},r_{0})}^{\pi}v_{1}(s)-T_{(P_{0},r_{0})}^{\pi}v_{2}(s)\right\rvert+\alpha_{s}^{P}\gamma\lVert
v_{2}\cdot\pi_{s}-v_{1}\cdot\pi_{s}\rVert_{q}$
$\displaystyle[\forall\operatorname{\mathbf{A}},\operatorname{\mathbf{B}}\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{X}}},\left\lvert\lVert\operatorname{\mathbf{A}}\rVert_{q}-\lVert\operatorname{\mathbf{B}}\rVert_{q}\right\rvert\leq\lVert\operatorname{\mathbf{A}}-\operatorname{\mathbf{B}}\rVert_{q}]$
$\displaystyle\leq$ $\displaystyle\gamma\left\lVert
v_{1}-v_{2}\right\rVert_{\infty}+\alpha_{s}^{P}\gamma\lVert
v_{2}\cdot\pi_{s}-v_{1}\cdot\pi_{s}\rVert_{q}$ $\displaystyle[\lVert
T_{(P_{0},r_{0})}^{\pi}v_{1}-T_{(P_{0},r_{0})}^{\pi}v_{2}\rVert_{\infty}\leq\gamma\left\lVert
v_{1}-v_{2}\right\rVert_{\infty}]$ $\displaystyle=$
$\displaystyle\gamma\left\lVert
v_{1}-v_{2}\right\rVert_{\infty}+\alpha_{s}^{P}\gamma\lVert(v_{2}-v_{1})\cdot\pi_{s}\rVert_{q}$
$\displaystyle[\forall
v,w\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}},v\cdot\pi_{s}-w\cdot\pi_{s}=(v-w)\cdot\pi_{s}]$
$\displaystyle\leq$ $\displaystyle\gamma\left\lVert
v_{1}-v_{2}\right\rVert_{\infty}+\alpha_{s}^{P}\gamma\lVert
v_{2}-v_{1}\rVert_{q}$ $\displaystyle[\forall
v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}},\lVert
v\cdot\pi_{s}\rVert_{q}\leq\lVert v\rVert_{q}]$ $\displaystyle\leq$
$\displaystyle\gamma\left\lVert
v_{1}-v_{2}\right\rVert_{\infty}+\alpha_{s}^{P}\gamma\lvert\operatorname{\mathcal{S}}\rvert^{\frac{1}{q}}\left\lVert
v_{1}-v_{2}\right\rVert_{\infty}$ $\displaystyle[\forall
v,w\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}},\lVert
v-w\rVert_{q}\leq\lvert\operatorname{\mathcal{S}}\rvert^{\frac{1}{q}}\lVert
v-w\rVert_{\infty}]$ $\displaystyle=$
$\displaystyle\gamma(1+\alpha_{s}^{P}\lvert\operatorname{\mathcal{S}}\rvert^{\frac{1}{q}})\left\lVert
v_{1}-v_{2}\right\rVert_{\infty}$ $\displaystyle\leq$
$\displaystyle\gamma\left(1+\frac{1-\gamma-\epsilon_{s}}{\gamma}\right)\lVert
v_{1}-v_{2}\rVert_{\infty}$
$\displaystyle[\alpha_{s}^{P}\leq\frac{1-\gamma-\epsilon_{s}}{\gamma\lvert\operatorname{\mathcal{S}}\rvert^{\frac{1}{q}}}\text{
by Asm.~{}(A${}_{q}$)}]$ $\displaystyle=$ $\displaystyle(1-\epsilon_{s})\lVert
v_{1}-v_{2}\rVert_{\infty}$ $\displaystyle\leq$
$\displaystyle(1-\epsilon_{*})\lVert v_{1}-v_{2}\rVert_{\infty},$

where $\epsilon_{*}:=\min_{s\in\operatorname{\mathcal{S}}}\epsilon_{s}$.
Setting $q=2$ and remarking that: (i) the first bound in Asm. 5.1 recovers
Asm. (Aq); (ii)
$T_{2}^{\pi,\textsc{r\textsuperscript{2}}}=T^{\pi,\textsc{r\textsuperscript{2}}}$,
establishes contraction of the R2 evaluation operator. For the optimality
operator, the proof is exactly the same as that of [10, Prop. 3], using Prop.
2.1. ∎

###  C.2 Proof of Theorem 5.1

######  Theorem (R2 optimal policy).

The greedy policy
$\pi^{*,\textsc{r\textsuperscript{2}}}=\mathcal{G}_{\Omega_{\textsc{r\textsuperscript{2}}}}(v^{*,\textsc{r\textsuperscript{2}}})$
is the unique optimal R2 policy, i.e., for all
$\pi\in\Delta_{\operatorname{\mathcal{A}}}^{\operatorname{\mathcal{S}}},v^{\pi^{*},\textsc{r\textsuperscript{2}}}=v^{*,\textsc{r\textsuperscript{2}}}\geq
v^{\pi,\textsc{r\textsuperscript{2}}}$.

###### Proof.

By strong convexity of the norm, the R2 function
$\Omega_{v,\textsc{r\textsuperscript{2}}}:\pi_{s}\mapsto\lVert\pi_{s}\rVert(\alpha_{s}^{r}+\alpha_{s}^{P}\gamma\lVert
v\rVert)$ is strongly convex in $\pi_{s}$. As such, we can invoke Prop. 2.1 to
state that the greedy policy $\pi^{*,\textsc{r\textsuperscript{2}}}$ is the
unique maximizing argument for $v^{*,\textsc{r\textsuperscript{2}}}$.
Moreover, by construction,

$\displaystyle
T^{\pi^{*,\textsc{r\textsuperscript{2}}},\textsc{r\textsuperscript{2}}}v^{*,\textsc{r\textsuperscript{2}}}=T^{*,\textsc{r\textsuperscript{2}}}v^{*,\textsc{r\textsuperscript{2}}}=v^{*,\textsc{r\textsuperscript{2}}}.$

Supposing that Asm. 5.1 holds, the evaluation operator
$T^{\pi^{*,\textsc{r\textsuperscript{2}}},\textsc{r\textsuperscript{2}}}$ is
contracting and has a unique fixed point
$v^{\pi^{*,\textsc{r\textsuperscript{2}}},\textsc{r\textsuperscript{2}}}$.
Therefore, $v^{*,\textsc{r\textsuperscript{2}}}$ being also a fixed point, we
have
$v^{\pi^{*,\textsc{r\textsuperscript{2}}},\textsc{r\textsuperscript{2}}}=v^{*,\textsc{r\textsuperscript{2}}}$.
It remains to show the last inequality: the proof is exactly the same as that
of [10, Thm. 1], and relies on the monotonicity of the R2 operators. ∎

###  C.3 Proof of Remark 5.1

######  Remark C.1.

An optimal R2 policy may be stochastic. This is due to the fact that our R2
MDP framework builds upon the general $s$-rectangularity assumption. Robust
MDPs with $s$-rectangular uncertainty sets similarly yield an optimal robust
policy that is stochastic [40, Table 1]. Nonetheless, the R2 MDP formulation
recovers a deterministic optimal policy in the more specific
$(s,a)$-rectangular case, which is in accordance with the robust MDP setting.

###### Proof.

In the $(s,a)$-rectangular case, the uncertainty set is structured as
$\mathcal{U}=\times_{(s,a)\in\operatorname{\mathcal{X}}}\mathcal{U}(s,a)$,
where $\mathcal{U}(s,a):=P_{0}(\cdot|s,a)\times
r_{0}(s,a)+\mathcal{P}(s,a)\times\mathcal{R}(s,a)$. The robust counterpart of
problem (PU) is:

$\displaystyle F(s)$
$\displaystyle=\max_{(P,r)\in\mathcal{U}}\left\\{v(s)-r^{\pi}(s)-\gamma
P^{\pi}v(s)\right\\}$
$\displaystyle=\max_{(P(\cdot|s,a),r(s,a))\in\mathcal{P}(s,a)\times\mathcal{R}(s,a)}\left\\{v(s)-r_{0}^{\pi}(s)-r^{\pi}(s)-\gamma
P_{0}^{\pi}v(s)-\gamma P^{\pi}v(s)\right\\}$
$\displaystyle=\max_{(P(\cdot|s,a),r(s,a))\in\mathcal{P}(s,a)\times\mathcal{R}(s,a)}\left\\{-r^{\pi}(s)-\gamma
P^{\pi}v(s)\right\\}+v(s)-r_{0}^{\pi}(s)-\gamma P_{0}^{\pi}v(s)$
$\displaystyle=\max_{r(s,a)\in\mathcal{R}(s,a)}\left\\{-r^{\pi}(s)\right\\}+\gamma\max_{P(\cdot|s,a)\in\mathcal{P}(s,a)}\left\\{-P^{\pi}v(s)\right\\}+v(s)-T_{(P_{0},r_{0})}^{\pi}v(s)$
$\displaystyle=\max_{r(s,a)\in\mathcal{R}(s,a)}\left\\{-\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)r(s,a)\right\\}+\gamma\max_{P(\cdot|s,a)\in\mathcal{P}(s,a)}\left\\{-\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)\langle
P(\cdot|s,a),v\rangle\right\\}$
$\displaystyle\qquad+v(s)-T_{(P_{0},r_{0})}^{\pi}v(s)$
$\displaystyle=\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)\left(\max_{r(s,a)\in\mathcal{R}(s,a)}\left\\{-r(s,a)\right\\}+\gamma\max_{P(\cdot|s,a)\in\mathcal{P}(s,a)}\left\\{\langle
P(\cdot|s,a),-v\rangle\right\\}\right)+v(s)-T_{(P_{0},r_{0})}^{\pi}v(s).$

In particular, if we have ball uncertainty sets
$\mathcal{P}(s,a):=\\{P(\cdot|s,a)\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}:\lVert
P(\cdot|s,a)\rVert\leq\alpha_{s,a}^{P}\\}$ and
$\mathcal{R}(s,a):=\\{r(s,a)\in\operatorname{\mathbb{R}}:\lvert
r(s,a)\rvert\leq\alpha_{s,a}^{r}\\}$ for all
$(s,a)\in\operatorname{\mathcal{X}}$, then we can explicitly compute the
support functions:

$\displaystyle\max_{r(s,a):\lvert
r(s,a)\rvert\leq\alpha_{s,a}^{r}}-r(s,a)=\alpha_{s,a}^{r}\text{ and
}\max_{P(\cdot|s,a):\lVert P(\cdot|s,a)\rVert\leq\alpha_{s,a}^{P}}\langle
P(\cdot|s,a),-v\rangle=\alpha_{s,a}^{P}\lVert v\rVert.$

Therefore, the robust counterpart rewrites as:

$\displaystyle F(s)$
$\displaystyle=\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)(\alpha_{s,a}^{r}+\gamma\alpha_{s,a}^{P}\lVert
v\rVert)+v(s)-T_{(P_{0},r_{0})}^{\pi}v(s),$

and the robust value function $v^{\pi,\mathcal{U}}$ is the optimal solution of
the convex optimization problem:

$\displaystyle\max_{v\in\operatorname{\mathbb{R}}^{\operatorname{\mathcal{S}}}}\langle
v,\mu_{0}\rangle\text{ s. t. }v(s)\leq
T_{(P_{0},r_{0})}^{\pi}v(s)-\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)(\alpha_{s,a}^{r}+\gamma\alpha_{s,a}^{P}\lVert
v\rVert)\text{ for all }s\in\operatorname{\mathcal{S}}.$

This derivation enables us to derive an R2 Bellman evaluation operator for the
$(s,a)$-rectangular case. Indeed, the R2 regularization function now becomes
$\Omega_{v,\textsc{r\textsuperscript{2}}}(\pi_{s}):=\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)(\alpha_{s,a}^{r}+\gamma\alpha_{s,a}^{P}\lVert
v\rVert)$, which yields the following R2 operator:

$\displaystyle[T^{\pi,\textsc{r\textsuperscript{2}}}v](s):=T_{(P_{0},r_{0})}^{\pi}v(s)-\Omega_{v,\textsc{r\textsuperscript{2}}}(\pi_{s}),\quad\forall
s\in\operatorname{\mathcal{S}}.$

We aim to show that we can find a deterministic policy
$\pi^{d}\in\Delta_{\operatorname{\mathcal{A}}}^{\operatorname{\mathcal{S}}}$
such that
$[T^{\pi^{d},\textsc{r\textsuperscript{2}}}v](s)=[T^{*,\textsc{r\textsuperscript{2}}}v](s)$
for all $s\in\operatorname{\mathcal{S}}$. Given an arbitrary policy
$\pi\in\Delta_{\operatorname{\mathcal{A}}}^{\operatorname{\mathcal{S}}}$, we
first rewrite:

$\displaystyle[T^{\pi,\textsc{r\textsuperscript{2}}}v](s)$
$\displaystyle=r_{0}^{\pi}(s)+\gamma
P_{0}^{\pi}v(s)-\Omega_{v,\textsc{r\textsuperscript{2}}}(\pi_{s})$
$\displaystyle=\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)r_{0}(s,a)+\gamma\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)\langle
P_{0}(\cdot|s,a),v\rangle-\left(\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)(\alpha_{s,a}^{r}+\gamma\alpha_{s,a}^{P}\lVert
v\rVert)\right)$
$\displaystyle=\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)\biggr{(}r_{0}(s,a)-\alpha_{s,a}^{r}+\gamma(\langle
P_{0}(\cdot|s,a),v\rangle-\alpha_{s,a}^{P}\lVert v\rVert)\biggr{)}$

By [30, Lemma 4.3.1], we have that:

$\displaystyle\sum_{a\in\operatorname{\mathcal{A}}}\pi_{s}(a)\biggr{(}r_{0}(s,a)-\alpha_{s,a}^{r}+\gamma(\langle
P_{0}(\cdot|s,a),v\rangle-\alpha_{s,a}^{P}\lVert v\rVert)\biggr{)}$
$\displaystyle\leq\max_{a\in\operatorname{\mathcal{A}}}\biggr{\\{}r_{0}(s,a)-\alpha_{s,a}^{r}+\gamma(\langle
P_{0}(\cdot|s,a),v\rangle-\alpha_{s,a}^{P}\lVert v\rVert)\biggr{\\}},$

and since the action set is finite, there exists an action
$a^{*}\in\operatorname{\mathcal{A}}$ reaching the maximum. Setting
$\pi^{d}(a^{*})=1$ thus gives the desired result. We just derived a
regularized formulation of robust MDPs with $(s,a)$-rectangular uncertainty
set and ensured that the corresponding R2 Bellman operators yield a
deterministic optimal policy. In that case, the optimal R2 Bellman operator
becomes:

$\displaystyle[T^{*,\textsc{r\textsuperscript{2}}}v](s)=\max_{a\in\operatorname{\mathcal{A}}}\biggr{\\{}r_{0}(s,a)-\alpha_{s,a}^{r}+\gamma(\langle
P_{0}(\cdot|s,a),v\rangle-\alpha_{s,a}^{P}\lVert v\rVert)\biggr{\\}}.$

∎

##  Appendix D Numerical experiments

Table 3: Hyperparameter set to obtain the results from Table 1 Number of seeds per experiment | $5$
---|---
Discount factor $\gamma$ | 0.9
Convergence Threshold $\theta$ | 1e-3
Reward Radius $\alpha$ | 1e-3
Transition Radius $\beta$ | 1e-5

In the following experiment, we play with the radius of the uncertainty set
and analyze the distance of the robust/R2 value function to the vanilla one
obtained after convergence of MPI. Except for the radius parameters of Table
3, all other parameters remain unchanged. In both figures 2 and 2, we see that
the distance norm converges to 0 as the size of the uncertainty set gets
closer to 0: this sanity check ensures an increasing relationship between the