# Performance Improvement Bounds for Lipschitz Configurable Markov Decision
Processes

Alberto Maria Metelli
Dipartimento di Elettronica Informazione e Bioingegneria
Politacnico di Milano
32, Piazza Leonardo da Vinci
20133, Milan, Italy
<EMAIL_ADDRESS>

###### Abstract

Configurable Markov Decision Processes (Conf-MDPs) have recently been
introduced as an extension of the traditional Markov Decision Processes (MDPs)
to model the real-world scenarios in which there is the possibility to
intervene in the environment in order to _configure_ some of its parameters.
In this paper, we focus on a particular subclass of Conf-MDP that satisfies
regularity conditions, namely Lipschitz continuity. We start by providing a
bound on the Wasserstein distance between $\gamma$-discounted stationary
distributions induced by changing policy and configuration. This result
generalizes the already existing bounds both for Conf-MDPs and traditional
MDPs. Then, we derive a novel performance improvement lower bound.

##  1 Introduction

The framework of the _Configurable Markov Decision Processes_ (Conf-MDPs,
Metelli et al.,, 2018, 2019, 2022) has been introduced in recent years to
model a wide range of real-world scenarios in which an agent has the
opportunity to alter some environmental parameters in order to improve its
learning experience. Conf-MDPs can be thought to as an extension of the
traditional Markov Decision Processes (MDP, Puterman,, 1994) to account for
scenarios that emerge quite often in the Reinforcement Learning (RL, Sutton
and Barto,, 2018) problems, in which the environment rarely represents an
immutable entity and can, indeed, be subject to partial control. In the Conf-
MDP framework, the activity of altering the environmental parameters is named
_environment configuration_ and serves different purposes.

In the simplest scenario, the configuration is carried out by the agent itself
that acts as a configurator. This might suggest, at a first sight, that
environment configuration can be modeled within the agent actuation. While in
principle this approach is possible, it tends to disregard the domain
peculiarities of environment configuration that usually is performed at a
slower frequency compared to policy learning and might generate notable costs.
The more realistic setting is the one in which an additional entity, the
_configurator_ is present and in charge of the environment configuration
process. The configurator acts on the environment transition model (that we
will call _configuration_ in this setting) and might have an objective that is
different from that of the agent. Thus, we can distinguish between two
scenarios Metelli, (2021, 2022): the _cooperative_ and the _non-cooperative_
settings. In the former, the agent and the configurator share the same
interests, i.e., the have the same reward function. In such a case, the
learning problem is simple as there is no conflict between the two involved
entities and several algorithms have been proposed in the literature Metelli
et al., (2018, 2019). In the non-cooperative setting, instead, agent and
configurator have possibly diverging interests, i.e., they reward function
differ. Here the definition of a solution concept is more challenging and
requires considering game-theoretic equilibria Metelli, (2021). Recently a
regret minimization approach has been proposed to address the learning problem
in general-sum non-cooperative Conf-MDPs Ramponi et al., (2021).

In this paper, we focus on cooperative Conf-MDP111For the sake of brevity, we
will simply use the abbreviation “Conf-MDP” to denote a cooperative Conf-MDP.
and we derive several theoretical results on the performance improvement that
can be obtained as an effect of altering either the policy of the environment
configuration. We start from the theoretical results presented in Metelli et
al., (2018), and further developed in Metelli, (2021), and we generalize them
to a wide class of Conf-MDPs. Specifically, we focus on two kind of results:
(i) bounds on the distance between the $\gamma$-discounted stationary
distributions and (ii) performance improvement lower bounds. The former
quantifies the distance in the state visitation distributions induced when
changing simultaneously the agent policy and the environment configuration;
whereas the latter provides a computable approximated expression of the
minimum performance attained with the selection of a new policy and a new
configuration. As demonstrated by previous works, lower bounds on the
performance improvement represent valuable tools to build a wide variety of
effective learning approaches, including _safe_ Pirotta et al., (2013);
Metelli et al., (2021) and _trust-region_ Schulman et al., (2015); Achiam et
al., (2017) approaches.

More in detail, we focus on a specific class of regular Conf-MDPs that we name
_Lipschitz_ (LC) Conf-MDPs, in analogy with the traditional Lipschitz MDPs
Rachelson and Lagoudakis, (2010); Pirotta et al., (2015). We introduce them in
Section 3. From an intuitive perspective, and with little inaccuracy, we can
think of the LC condition as the existence of the first derivative of the
relevant quantities. Then, in Section 4, we provide the bounds on the
$\gamma$-discounted stationary distributions. We start with a bound that
merges together the effects of the policy and the configuration and then we
move to a looser result that highlights the individual contributions of the
policy and of the configuration. We compare the derived bound with the ones
already present in the literature (even for MDPs only) and we show that,
several of them, can be derived by our result, under specific conditions. In
Section 5, we revise the notion of _advantage function_ for Conf-MDPs, which
quantifies the one-step gain in performance obtained by either modifying the
policy, the configuration, or both. We report the policy, configuration, and
joint advantages and we study their relationships. Finally, in Section 6, we
provide the performance improvement lower bounds. Specifically, we first
derive a general tight bound that is hardly computable as it involves
quantities that are usually unknown in practice. Then, we move to the
derivation of a looser bound that has the advantage of being computable.
Although mainly theoretical, the contributions provided in this paper are of
independent interest, even outside the Conf-MDP field,222Every result we
present can be employed for traditional MPDs as well, by just assuming not to
change the environment configuration. and can be effectively employed as a
starting point for the design of safe and trust region methods. Part of the
results presented in this paper has previously appeared in Metelli et al.,
(2018); Metelli, (2021).

##  2 Preliminaries

In this section, we introduce the necessary background about probability,
Lipschitz continuity, Wasserstien distance (Section 2.1) and Conf-MDPs
(Section 2.2), that will be employed in the following sections.

###  2.1 Mathematical Background

#### Probability

Let $\mathcal{X}$ be a set and $\mathfrak{F}$ be a $\sigma$-algebra over
$\mathcal{X}$. We denote with $\Delta^{\mathcal{X}}$ the set of probability
measures over the measurable space $(\mathcal{X},\mathfrak{F})$. Let
$\mathcal{Y}$ be a set, we denote with $\Delta_{\mathcal{Y}}^{\mathcal{X}}$
the set of functions with signature
$\mathcal{Y}\rightarrow\Delta^{\mathcal{X}}$ and with
$\mathcal{Y}^{\mathcal{X}}$ the set of functions with signature
$\mathcal{X}\rightarrow\mathcal{Y}$. Let $x\in\mathcal{X}$, the Dirac delta
measure is denoted by $\delta_{x}$.

#### Lipschitz Continuity

Let $(\mathcal{X},d_{\mathcal{X}})$ and $(\mathcal{Y},d_{\mathcal{Y}})$ be two
metric spaces, where $d_{\mathcal{X}}:\mathcal{X}\rightarrow[0,+\infty)$ and
$d_{\mathcal{Y}}:\mathcal{Y}\rightarrow[0,+\infty)$ are the corresponding
distance functions. A function $f\in\mathcal{Y}^{\mathcal{X}}$ is _Lipschitz
continuous_ with Lipschitz constant $L_{f}$ ($L_{f}$-LC) if it holds that:

$\displaystyle d_{\mathcal{Y}}\left(f(x),f(\overline{x})\right)\leq
L_{f}d_{\mathcal{X}}\left(x,\overline{x}\right),\qquad\forall
x,\overline{x}\in\mathcal{X}.$ (1)

We define the _Lipschitz semi-norm_ of function $f$ as the smallest $L_{f}>0$
for which Equation (1) holds:

$\displaystyle\|f\|_{L}=\sup_{x,\overline{x}\in\mathcal{X},\,x\neq\overline{x}}\frac{d_{\mathcal{Y}}\left(f(x),f(\overline{x})\right)}{d_{\mathcal{X}}\left(x,\overline{x}\right)}.$

Being a semi-norm, $\|\cdot\|_{L}$ is non-negative and fulfills the triangular
inequality. If $\mathcal{Y}=\mathbb{R}$, i.e., $f$ is a real-valued function,
we typically employ as distance function $d_{\mathcal{Y}}$ the Euclidean
distance, i.e., $d_{\mathcal{Y}}(y,\overline{y})=|y-\overline{y}|$. If
$\mathcal{Y}=\Delta^{\mathcal{Z}}$, i.e., $f$ has values in probability
distributions, we employ as distance function the Wasserstein distance
(Villani,, 2009).

#### Wasserstein Distance

Let $p,q\in\Delta^{\mathcal{X}}$ be two probability measures over the metric
space $(\mathcal{X},d_{\mathcal{X}})$. The $L_{1}$-Wasserstein (or
Kantorovich) distance between $p$ and $q$ is defined as Villani, (2009):

$\displaystyle\mathcal{W}(p,q)=\sup_{f:\left\|f\right\|_{L{}}\leq
1}\left|\int_{\mathcal{X}}\left(p(\mathrm{d}x)-q(\mathrm{d}x)\right)f(x)\right|.$

If the metric $d_{\mathcal{X}}$ is chosen to be the _discrete metric_ , i.e.,
$d_{\mathcal{X}}(x,x^{\prime})=\mathds{1}\\{x\neq x^{\prime}\\}$ for all
$x,x^{\prime}\in\mathcal{X}$, then the $L_{1}$-Wasserstein reduces to the
Total Variation (TV) divergence.

###  2.2 Configurable Markov Decision Processes

A (cooperative) Configurable Markov Decision Process (Conf-MDP, Metelli et
al.,, 2018) is a tuple $\mathcal{C}=(\mathcal{S},\mathcal{A},r,\gamma)$, where
$\mathcal{S}$ is the state space, $\mathcal{A}$ is the action space,
$r\in\mathbb{R}^{\mathcal{S}\times\mathcal{A}\times\mathcal{S}}$ is the reward
function mapping every state-action-next-state triple
$(s,a,s^{\prime})\in\mathcal{S}\times\mathcal{A}\times\mathcal{S}$ to the
reward $r(s,a,s^{\prime})\in\mathbb{R}$, and $\gamma\in[0,1)$ is the discount
factor. The behavior of the configurator is modeled by a configuration (or
transition model) $p\in\Delta^{\mathcal{S}}_{\mathcal{S}\times\mathcal{A}}$
that maps every state-action pair $(s,a)\in\mathcal{S}\times\mathcal{A}$ to
the probability measure $p(\cdot|s,a)\in\Delta^{\mathcal{S}}$ of the next
state. The behavior of the agent is modeled by a policy
$\pi\in\Delta^{\mathcal{A}}_{\mathcal{S}}$ that maps every state
$s\in\mathcal{S}$ to the probability measure
$\pi(\cdot|s)\in\Delta^{\mathcal{A}}$ of the action to be played. We denote
with $p_{\pi}\in\Delta^{\mathcal{S}}_{\mathcal{S}}$ the state-state transition
kernel, defined as:

$\displaystyle
p_{\pi}(\mathrm{d}s^{\prime}|s)=\int_{\mathcal{A}}\pi(\mathrm{d}a|s)p(\mathrm{d}s^{\prime}|s,a),\qquad\forall
s,s^{\prime}\in\mathcal{S}.$

#### Value Functions

Similarly to traditional MDPs, the _value functions_ Sutton and Barto, (2018)
can be define for Conf-MDPs as done in Metelli, (2021). Let
$(\pi,p)\in\Delta^{\mathcal{A}}_{\mathcal{S}}\times\Delta^{\mathcal{S}}_{\mathcal{S}\times\mathcal{A}}$
be a policy-configuration pair, we define the following value functions, for
every $(s,a,s^{\prime})\in\mathcal{S\times A\times S}$:

$\displaystyle
v_{\pi,p}(s)=\int_{\mathcal{A}}\pi(\mathrm{d}a|s)\int_{\mathcal{S}}p(\mathrm{d}s^{\prime}|s,a)\left(r(s,a,s^{\prime})+\gamma
v_{\pi,p}(s^{\prime})\right),$ $\displaystyle
q_{\pi,p}(s,a)=\int_{\mathcal{S}}p(\mathrm{d}s^{\prime}|s,a)\left(r(s,a,s^{\prime})+\gamma
v_{\pi,p}(s^{\prime})\right),$ $\displaystyle
u_{\pi,p}(s,a,s^{\prime})=r(s,a,s^{\prime})+\gamma v_{\pi,p}(s^{\prime}).$

These value functions represent the _expected discounted cumulative reward_
(i.e., the _expected return_) experienced by the agent-configurator when
interacting with the environment with a policy $\pi$ and a configuration $p$.
While $v_{\pi,p}(s)$ (i.e., state value function or V-function) and
$q_{\pi,p}(s,a)$ (i.e., state-action value function or Q-function) are defined
analogously to the case of MDPs, $u_{\pi,p}(s,a,s^{\prime})$ (i.e., state-
action-next-state value function or U-function) is a peculiar value function
for Conf-MDPs Metelli et al., (2018) that turns out to be relevant for
learning optimal configurations. We refer the reader to (Metelli,, 2021,
Chapter 4) for a detailed review of the value function and the Bellman
operators and equations for Conf-MDPs.

####  $\gamma$-discounted Stationary Distributions

A policy-configuration pair
$(\pi,p)\in\Delta^{\mathcal{A}}_{\mathcal{S}}\times\Delta^{\mathcal{S}}_{\mathcal{S}\times\mathcal{A}}$
induces a visitation distribution of the states. The $\gamma$-discounted
stationary distribution accounts the expected discounted number of
visits333“Discounted” means that if a visit to a given state is performed at
step $t$ of interaction it counts $\gamma^{t}$. induced by a policy-
configuration pair
$(\pi,p)\in\Delta^{\mathcal{A}}_{\mathcal{S}}\times\Delta^{\mathcal{S}}_{\mathcal{S}\times\mathcal{A}}$,
starting from an initial state sampled from $\rho\in\Delta^{\mathcal{S}}$, and
it is defined in several equivalent forms Sutton et al., (1999):

$\displaystyle\mu_{\pi,p}^{\gamma,\rho}=(1-\gamma)\rho+\gamma{p}_{\pi}\mu_{\pi,p}^{\gamma,\rho}=(1-\gamma)\sum_{t=0}^{+\infty}\gamma^{t}\rho
p_{\pi}^{t}=(1-\gamma)\rho\left(\mathrm{Id}_{\mathcal{S}}-\gamma
p_{\pi}\right)^{-1}.$ (2)

For the sake of brevity, whenever clear from the context, we omit the
superscripts $\gamma,\rho$, simply employing $\mu_{\pi,p}$.

Given an initial state distribution $\rho\in\Delta^{\mathcal{S}}$, we define
the _expected return_ of a policy-configuration pair
$(\pi,p)\in\Delta^{\mathcal{A}}_{\mathcal{S}}\times\Delta^{\mathcal{S}}_{\mathcal{S}\times\mathcal{A}}$
in two interchangeable ways:

$\displaystyle
J_{\pi,p}=\int_{\mathcal{S}}\rho(\mathrm{d}s)v_{\pi,p}(s)=\frac{1}{1-\gamma}\int_{\mathcal{S}\times\mathcal{A}\times\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)\pi(\mathrm{d}a|s)p(\mathrm{d}s^{\prime}|s,a)r(s,a,s^{\prime}).$

##  3 Lipschitz Configurable Markov Decision Processes

In this section, we introduce the notion of regular Conf-MDPs that we will
employ in the derivation of the theoretical results. We rephrase the
traditional notion of Lipschitz (LC) MDP Rachelson and Lagoudakis, (2010);
Pirotta et al., (2015) to the case of Conf-MDPs.

######  Assumption 3.1 (Lipschitz Configurable Markov Decision Processes
(LC)).

Let $\mathcal{C}=(\mathcal{S},\mathcal{A},r,\gamma)$ be a Conf-MDP, where
$(\mathcal{S},d_{\mathcal{S}})$ and $(\mathcal{A},d_{\mathcal{A}})$ are metric
spaces endowed with the corresponding distance functions $d_{\mathcal{S}}$ and
$d_{\mathcal{A}}$, respectively. $\mathcal{C}$ is $L_{r}$-LC if it holds that:

$\displaystyle\left|r(s,a,s^{\prime})-r(\overline{s},\overline{a},\overline{s}^{\prime})\right|\leq
L_{r}d_{\mathcal{S}\times\mathcal{A}\times\mathcal{S}}\left((s,a,s^{\prime}),(\overline{s},\overline{a},\overline{s}^{\prime})\right),\qquad\forall(s,a,s^{\prime}),(\overline{s},\overline{a},\overline{s}^{\prime})\in\mathcal{S}\times\mathcal{A},$

where
$d_{\mathcal{S}\times\mathcal{A}\times\mathcal{S}}\left((s,a,s^{\prime}),(\overline{s},\overline{a},\overline{s}^{\prime})\right)\coloneqq
d_{\mathcal{S}}(s,\overline{s})+d_{\mathcal{A}}(a,\overline{a})+d_{\mathcal{S}}(s^{\prime},\overline{s}^{\prime})$.

Compared with Rachelson and Lagoudakis, (2010); Pirotta et al., (2015), we
enforce a condition on the reward function only, since the transition model
(i.e., configuration) does not belong to the definition of the Conf-MDP.
Moreover, with negligible loss of generality, as done in Rachelson and
Lagoudakis, (2010); Pirotta et al., (2015), we consider a disjoint metric for
the state and action spaces. We now proceed at introducing the notion of
Lipschitz configuration and policy.

######  Assumption 3.2 (Lipschitz Configuration and Policy (LC)).

Let $\mathcal{C}=(\mathcal{S},\mathcal{A},r,\gamma)$ be a Conf-MDP, where
$(\mathcal{S},d_{\mathcal{S}})$ and $(\mathcal{A},d_{\mathcal{A}})$ are metric
spaces endowed with the corresponding distance functions $d_{\mathcal{S}}$ and
$d_{\mathcal{A}}$, respectively. Let
$p\in\Delta^{\mathcal{S}}_{\mathcal{S}\times\mathcal{A}}$ be a configuration.
$p$ is $L_{p}$-LC if it holds that:

$\displaystyle\mathcal{W}\left(p(\cdot|s,a),p(\cdot|\overline{s},\overline{a})\right)\leq
L_{p}d_{\mathcal{S}\times\mathcal{A}}\left((s,a),(\overline{s},\overline{a})\right),\quad\forall(s,a),(\overline{s},\overline{a})\in\mathcal{S}\times\mathcal{A},$

where
$d_{\mathcal{S}\times\mathcal{A}}\left((s,a),(\overline{s},\overline{a})\right)\coloneqq
d_{\mathcal{S}}(s,\overline{s})+d_{\mathcal{A}}(a,\overline{a})$. Let
$\pi\in\Delta^{\mathcal{A}}_{\mathcal{S}}$ be a policy. $\pi$ is $L_{\pi}$-LC
if it holds that:

$\displaystyle\mathcal{W}\left(\pi(\cdot|s),\pi(\cdot|\overline{s})\right)\leq
L_{\pi}d_{\mathcal{S}}(s,\overline{s}),\quad\forall
s,\overline{s}\in\mathcal{S}.$

The choice of employing the Wasserstein distance over other distributional
divergences, such as the TV divergence Munos and Szepesvári, (2008), is
justified by the fact that the former allows quantifying the distance between
deterministic distributions. Instead, the TV divergence takes its maximum
value whenever the involved distributions have disjoint support. The
Wasserstein distance is a standard choice in the RL literature Pirotta et al.,
(2015); Metelli et al., (2020).

#### Lipschitz semi-norms of the Value functions

Once we enforce the LC conditions on the Conf-MDP and on the policy and
configurations (Assumptions 3.1 and 3.2), it is well-known that the state
value function $v_{\pi,p}$ and state-action value function $q_{\pi,p}$ are LC,
under the assumption that $\gamma L_{p}(1+L_{\pi})<1$ Rachelson and
Lagoudakis, (2010). In particular, their Lipschitz semi-norms (i.e., Lipschitz
constants) are bounded as:

$\displaystyle\left\|{q_{\pi,p}}\right\|_{L}\leq\frac{L_{r}}{1-\gamma
L_{p}(1+L_{\pi})},\qquad\left\|{v_{\pi,p}}\right\|_{L}\leq\left\|{q_{\pi,p}}\right\|_{L}(1+L_{\pi})\leq\frac{L_{r}(1+L_{\pi})}{1-\gamma
L_{p}(1+L_{\pi})}.$

The following result provides a bound on the Lipschitz semi-norm of the state-
action-next-state value function $u_{\pi,p}$, that has been specifically
introduced for the Conf-MDPs.

######  Lemma 3.1.

Let $\mathcal{C}$ be an $L_{r}$-LC Conf-MDP,
$p\in\Delta^{\mathcal{S}}_{\mathcal{S}\times\mathcal{A}}$ be an $L_{p}$-LC
configuration, and $\pi\in\Delta^{\mathcal{A}}_{\mathcal{S}}$ be an
$L_{\pi}$-LC policy. Then, the state-action-next-state value function
$u_{\pi,p}$ is LC, under the assumption that $\gamma L_{p}(1+L_{\pi})<1$, with
Lipschitz semi-norm:

$\displaystyle\left\|{u_{\pi,p}}\right\|_{L}\leq
L_{r}+\gamma\left\|{v_{\pi,p}}\right\|_{L}\leq\frac{L_{r}(2+L_{\pi}-\gamma
L_{p}(1+L_{\pi}))}{1-\gamma L_{p}(1+L_{\pi})}.$

###### Proof.

Let
$(s,a,s^{\prime}),(\overline{s},\overline{a},\overline{s}^{\prime})\in\mathcal{S}\times\mathcal{A}\times\mathcal{S}$,
we have:

$\displaystyle\left|u_{\pi,p}(s,a,s^{\prime})-u_{\pi,p}(\overline{s},\overline{a},\overline{s}^{\prime})\right|$
$\displaystyle=\left|r(s,a,s^{\prime})+\gamma
v_{\pi,p}(s^{\prime})-r(\overline{s},\overline{a},\overline{s}^{\prime})-\gamma
v_{\pi,p}(\overline{s}^{\prime})\right|$
$\displaystyle\leq\left|r(s,a,s^{\prime})-r(\overline{s},\overline{a},\overline{s}^{\prime})\right|+\gamma\left|v_{\pi,p}(s^{\prime})-v_{\pi,p}(\overline{s}^{\prime})\right|$
$\displaystyle\leq
L_{r}d_{\mathcal{S}\times\mathcal{A}\times\mathcal{S}}\left((s,a,s^{\prime}),(\overline{s},\overline{a},\overline{s}^{\prime})\right)+\gamma\left\|{v_{\pi,p}}\right\|_{L}d_{\mathcal{S}}(s^{\prime},\overline{s}^{\prime})$
$\displaystyle\leq\left(L_{r}+\gamma\left\|{v_{\pi,p}}\right\|_{L}\right)d_{\mathcal{S}\times\mathcal{A}\times\mathcal{S}}((s,a,s^{\prime}),(\overline{s},\overline{a},\overline{s}^{\prime}),$

having observed that
$d_{\mathcal{S}\times\mathcal{A}\times\mathcal{S}}\left((s,a,s^{\prime}),(\overline{s},\overline{a},\overline{s}^{\prime})\right)\geq
d_{\mathcal{S}}(s^{\prime},\overline{s}^{\prime})$. ∎

##  4 Bound on the $\gamma$-discounted Stationary Distribution

In this section, we provide a bound for the Wasserstein distance of
$\gamma$-discounted stationary distributions under different policy-
configuration pairs. We start with a result that bounds the Wasserstein
distance of the $\gamma$-discounted stationary distributions in terms of the
Wasserstein distance between the corresponding state-state transition kernels
(Section 4.1) and, then, we provide a looser bound that decouples the
contribution of the policy from that of the transition model (Section 4.2).
Both results are obtained for LC Conf-MDPs, policies, and configurations.
Finally, we provide a comparison with similar results already present in the
literature (Section 4.3).

###  4.1 Coupled Bound

The following theorem provides the coupled bound on the $\gamma$-discounted
stationary distribution, that merges together the contributions of the
configuration and of the policy.

######  Theorem 4.1.

Let $\mathcal{C}$ be a Conf-MDP, let
$(\pi,p),(\pi^{\prime},p^{\prime})\in\Delta^{\mathcal{A}}_{\mathcal{S}}\times\Delta^{\mathcal{S}}_{\mathcal{S}\times\mathcal{A}}$
be two policy-configuration pairs such that $\pi^{\prime}$ is
$L_{\pi^{\prime}}$-LC and $p^{\prime}$ is $L_{p^{\prime}}$-LC. Then, if
$\gamma L_{p^{\prime}}(1+L_{\pi^{\prime}})<1$, it holds that:

$\mathcal{W}\left(\mu_{\pi^{\prime},p^{\prime}},\mu_{\pi,p}\right)\leq\frac{\gamma}{1-\gamma
L_{p^{\prime}}(1+L_{\pi^{\prime}})}\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)\mathcal{W}{\left({p^{\prime}}_{\pi^{\prime}}(\cdot|s),{p}_{\pi}(\cdot|s)\right)}.$

###### Proof.

The derivation presents similarities with the proof of Lemma 2 of Pirotta et
al., (2015). Exploiting the recursive equation of the $\gamma$-discounted
state distribution (Equation 2), we can write the distributions difference as
follows, in operator form:

$\displaystyle\mu_{\pi^{\prime},p^{\prime}}-\mu_{\pi,p}$
$\displaystyle=(1-\gamma)\rho+\gamma\mu_{\pi^{\prime},p^{\prime}}{p^{\prime}}_{\pi^{\prime}}-(1-\gamma)\rho-\gamma\mu_{\pi,p}{p}_{\pi}$
$\displaystyle=\gamma\mu_{\pi^{\prime},p^{\prime}}{p^{\prime}}_{\pi^{\prime}}-\gamma\mu_{\pi,p}{p}_{\pi}\pm\mu_{\pi,p}{p^{\prime}}_{\pi^{\prime}}$
$\displaystyle=\gamma\left(\mu_{\pi^{\prime},p^{\prime}}-\mu_{\pi,p}\right){p^{\prime}}_{\pi^{\prime}}+\gamma\mu_{\pi,p}\left({p^{\prime}}_{\pi^{\prime}}-{p}_{\pi}\right)$
$\displaystyle=\gamma\mu_{\pi,p}\left({p^{\prime}}_{\pi^{\prime}}-{p}_{\pi}\right)\left(\mathrm{Id}_{\mathcal{S}}-\gamma{p^{\prime}}_{\pi^{\prime}}\right)^{-1},$
(3)

where we exploited the recursive definition of
$\mu_{\pi^{\prime},p^{\prime}}-\mu_{\pi,p}$ and recalled that $\gamma<1$. We
proceed by computing the Wasserstein distance:

$\displaystyle{\mathcal{W}}{\left({\mu_{\pi^{\prime},p^{\prime}}},{\mu_{\pi,p}}\right)}$
$\displaystyle=\sup_{f:\left\|f\right\|_{L{}}\leq
1}\left|\int_{\mathcal{S}}\left(\mu_{\pi^{\prime},p^{\prime}}(\mathrm{d}s)-\mu_{\pi,p}(\mathrm{d}s)\right)f(s)\right|$
$\displaystyle=\gamma\sup_{f:\left\|f\right\|_{L{}}\leq
1}\left|\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s^{\prime\prime})\int_{\mathcal{S}}\left({p^{\prime}}_{\pi^{\prime}}(\mathrm{d}s^{\prime}|s^{\prime\prime}),{p}_{\pi}(\mathrm{d}s^{\prime}|s^{\prime\prime})\right)\underbrace{\int_{\mathcal{S}}\left(\mathrm{Id}_{\mathcal{S}}-\gamma{p^{\prime}}_{\pi^{\prime}}\right)^{-1}(\mathrm{d}s|s^{\prime})f(s)}_{\eqqcolon
g_{f}(s^{\prime})}\right|$ (4)
$\displaystyle\leq\gamma\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s^{\prime\prime})\sup_{f:\left\|f\right\|_{L{}}\leq
1}\left|\int_{\mathcal{S}}\left({p^{\prime}}_{\pi^{\prime}}(\mathrm{d}s^{\prime}|s^{\prime\prime}),{p}_{\pi}(\mathrm{d}s^{\prime}|s^{\prime\prime})\right)g_{f}(s^{\prime})\right|$
(5)
$\displaystyle\leq\gamma\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s^{\prime\prime}){\mathcal{W}}{\left({{p^{\prime}}_{\pi^{\prime}}(\cdot|s^{\prime\prime})},{{p}_{\pi}(\cdot|s^{\prime\prime})}\right)}\sup_{f:\left\|f\right\|_{L{}}\leq
1}\left\|{g_{f}}\right\|_{L},$ (6)

where in line (4) we exploited Equation (3), line (5) follows from Jensen’s
inequality, and line (6) comes from the definition of Wasserstein distance. We
now compute the Lipschitz semi-norm $\left\|{g_{f}}\right\|_{L}$. Let us
introduce the distribution
$\mu_{\pi^{\prime},p^{\prime}}^{\gamma,\delta_{s}}=(1-\gamma)\delta_{s}+\gamma{p^{\prime}}_{\pi^{\prime}}\mu_{\pi^{\prime},p^{\prime}}^{\gamma,\delta_{s}}=(1-\gamma)\delta_{s}\left(\mathrm{Id}_{\mathcal{S}}-\gamma{p^{\prime}}_{\pi^{\prime}}\right)^{-1}$,
i.e., the $\gamma$-discounted stationary distribution when the initial state
distribution is the Dirac delta $\delta_{s}$. We observe that
$(1-\gamma)g_{f}(s)=\int_{\mathcal{S}}\mu_{\pi^{\prime},p^{\prime}}^{\gamma,\delta_{s}}(\mathrm{d}s^{\prime})f(s^{\prime})$.
Thus, to compute the Lipschitz semi-norm $\left\|{g_{f}}\right\|_{L}$, we
proceed as follows for $s,\overline{s}\in\mathcal{S}$:

$\displaystyle(1-\gamma)g_{f}(s)$
$\displaystyle-(1-\gamma)g_{f}(\overline{s})=\int_{\mathcal{S}}\left(\mu_{\pi^{\prime},p^{\prime}}^{\gamma,\delta_{s}}(\mathrm{d}s^{\prime})-\mu_{\pi^{\prime},p^{\prime}}^{\gamma,\delta_{\overline{s}}}(\mathrm{d}s^{\prime})\right)f(s^{\prime})\leq{\mathcal{W}}{\left({\mu_{\pi^{\prime},p^{\prime}}^{\gamma,\delta_{s}}},{\mu_{\pi^{\prime},p^{\prime}}^{\gamma,\delta_{\overline{s}}}}\right)}.$

Thus, we have:

$\displaystyle{\mathcal{W}}{\left({\mu_{\pi^{\prime},p^{\prime}}^{\gamma,\delta_{s}}},{\mu_{\pi^{\prime},p^{\prime}}^{\gamma,\delta_{\overline{s}}}}\right)}=\sup_{f:\left\|f\right\|_{L{}}\leq
1}\Bigg{|}(1-\gamma)\int_{\mathcal{S}}\left(\delta_{s}(\mathrm{d}s^{\prime})-\delta_{\overline{s}}(\mathrm{d}s^{\prime})\right)f(s^{\prime})$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\quad+\gamma\int_{\mathcal{S}}\left(\left({p^{\prime}}_{\pi^{\prime}}\mu_{\pi^{\prime},p^{\prime}}^{\gamma,\delta_{s}}\right)(\mathrm{d}s^{\prime})-\left({p^{\prime}}_{\pi^{\prime}}\mu_{\pi^{\prime},p^{\prime}}^{\gamma,\delta_{\overline{s}}}\right)(\mathrm{d}s^{\prime})\right)f(s^{\prime})\Bigg{|}$
(7)
$\displaystyle\qquad\leq(1-\gamma)d_{\mathcal{S}}(s,\overline{s})+\gamma\sup_{f:\left\|f\right\|_{L{}}\leq
1}\left|\int_{\mathcal{S}}\left(\mu_{\pi^{\prime},p^{\prime}}^{\gamma,\delta_{s}}(\mathrm{d}s^{\prime\prime})-\mu_{\pi^{\prime},p^{\prime}}^{\gamma,\delta_{\overline{s}}}(\mathrm{d}s^{\prime\prime})\right)\underbrace{\int_{\mathcal{S}}{p^{\prime}}_{\pi^{\prime}}(\mathrm{d}s^{\prime}|s^{\prime\prime})f(s^{\prime})}_{\eqqcolon
h_{f}(s^{\prime\prime})}\right|$ (8)
$\displaystyle\qquad\leq(1-\gamma)d_{\mathcal{S}}(s,\overline{s})+\gamma\sup_{f:\left\|f\right\|_{L{}}\leq
1}\left\|{h_{f}}\right\|_{L}\sup_{f:\left\|f\right\|_{L{}}\leq
1}\left|\int_{\mathcal{S}}\left(\mu_{\pi^{\prime},p^{\prime}}^{\gamma,\delta_{s}}(\mathrm{d}s^{\prime\prime})-\mu_{\pi^{\prime},p^{\prime}}^{\gamma,\delta_{\overline{s}}}(\mathrm{d}s^{\prime\prime})\right)f(s^{\prime\prime})\right|$
$\displaystyle\qquad=(1-\gamma)d_{\mathcal{S}}(s,\overline{s})+\gamma\sup_{f:\left\|f\right\|_{L{}}\leq
1}\left\|{h_{f}}\right\|_{L}{\mathcal{W}}{\left({\mu_{\pi^{\prime},p^{\prime}}^{\gamma,\delta_{s}}},{\mu_{\pi^{\prime},p^{\prime}}^{\gamma,\delta_{\overline{s}}}}\right)},$

where line (7) follows from the definition of
$\mu_{\pi^{\prime},p^{\prime}}^{\gamma,\delta_{s}}$, line (8) follows from
observing that
$\int_{\mathcal{S}}\left(\delta_{s}(\mathrm{d}s^{\prime})-\delta_{\overline{s}}(\mathrm{d}s^{\prime})\right)f(s^{\prime})=f(s)-f(\overline{s})\leq
d_{\mathcal{S}}(s,\overline{s})$ since $\|f\|_{L}\leq 1$ and by the definition
of
${p^{\prime}}_{\pi^{\prime}}\mu_{\pi^{\prime},p^{\prime}}^{\gamma,\delta_{s}}$.
The Lipschitz semi-norm $\left\|{h_{f}}\right\|_{L}$ is computed in Lemma 9.1,
resulting in $L_{p^{\prime}}(1+L_{\pi^{\prime}})$. Putting all together and
exploiting the recursion, we obtain:

$\displaystyle{\mathcal{W}}{\left({\mu_{\pi^{\prime},p^{\prime}}^{\gamma,\delta_{s}}},{\mu_{\pi^{\prime},p^{\prime}}^{\gamma,\delta_{\overline{s}}}}\right)}\leq\frac{1-\gamma}{1-\gamma
L_{p^{\prime}}(1+L_{\pi^{\prime}})}d_{\mathcal{S}}(s,\overline{s})\quad\implies\quad
g_{f}(s)-g_{f}(\overline{s})\leq\frac{1}{1-\gamma
L_{p^{\prime}}(1+L_{\pi^{\prime}})}d_{\mathcal{S}}(s,\overline{s}),$

that concludes the proof. ∎

Thus, we have bounded the Wasserstein distance between the $\gamma$-discounted
stationary distributions with the Wasserstein distance between the state
transition kernels, averaged over the distribution $\mu_{\pi,p}$. The
resulting multiplicative constant involves the Lipschitz constants of the
policy $\pi^{\prime}$ and of the configuration $p^{\prime}$. Therefore,
remarkably, in order to obtain such a result it is not required that the
policy-configuration pair $(\pi,p)$ is LC.

###  4.2 Decoupled Bound

In some applications, it is useful to decouple the contribution of the
configuration $p$ and that of the policy $\pi$ in the bound of the Wasserstein
distance between the $\gamma$-discounted stationary distributions. Indeed, in
several applicative scenarios of the Conf-MDP, as noted earlier, the
configuration activity (i.e., altering the transition model of the
environment) and the policy learning are carried out by two different
entities, possibly at different time scales. The following corollary provides
a looser bound in which the contribution of policy and configurations are
separated.

######  Corollary 4.2.

Let $\mathcal{C}$ be a Conf-MDP, let
$(\pi,p),(\pi^{\prime},p^{\prime})\in\Delta^{\mathcal{A}}_{\mathcal{S}}\times\Delta^{\mathcal{S}}_{\mathcal{S}\times\mathcal{A}}$
be two policy-configuration pairs such that $\pi^{\prime}$ is
$L_{\pi^{\prime}}$-LC and $p^{\prime}$ is $L_{p^{\prime}}$-LC. Then, if
$\gamma L_{p^{\prime}}(1+L_{\pi^{\prime}})<1$, it holds that:

$\displaystyle\mathcal{W}\left(\mu_{\pi^{\prime},p^{\prime}},\mu_{\pi,p}\right)$
$\displaystyle\leq\frac{\gamma}{1-\gamma
L_{p^{\prime}}(1+L_{\pi^{\prime}})}\int_{\mathcal{S}\times\mathcal{A}}\mu_{\pi,p}(\mathrm{d}s)\pi(\mathrm{d}a|s)\mathcal{W}{\left(p^{\prime}(\cdot|s,a),p(\cdot|s,a)\right)}$
$\displaystyle\quad+\frac{\gamma L_{p^{\prime}}}{1-\gamma
L_{p^{\prime}}(1+L_{\pi^{\prime}})}\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)\mathcal{W}{\left(\pi^{\prime}(\cdot|s),\pi(\cdot|s)\right)}.$

###  4.3 Comparison with Existing Bounds

The bounds presented in the previous sections generalize several existing
results present the literature. In particular, Corollary 4.2 is an extension
of Lemma 3 of Pirotta et al., (2015) for the case of Conf-MDPs in which we
allow for the modification of the configuration (i.e., transition model) too.
Furthermore, even in the non-configurable setting, i.e., when setting
$p=p^{\prime}$ a.s., our result is stronger as it involves the Wasserstein
distance between policies _averaged_ over the $\gamma$-discounted stationary
distribution instead of its _supremum_ over the state space:

$\displaystyle\underbrace{\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)\mathcal{W}{\left(\pi^{\prime}(\cdot|s),\pi(\cdot|s)\right)}}_{\text{Our
Corollay~{}\ref{coroll:BoundDisj}}}\leq\underbrace{\sup_{s\in\mathcal{S}}\mathcal{W}{\left(\pi^{\prime}(\cdot|s),\pi(\cdot|s)\right)}}_{\text{Lemma
3 of~{}\cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{PirottaRB15}{\@@citephrase{(}}{\@@citephrase{)}}}}}.$

A result connected to ours, with a bound involving the modification of the
transition model, appeared in Asadi et al., (2018) for model-based RL.
However, the provided equation holds under a uniform bound on the Wasserstein
distance between transition models
$\sup_{(s,a)\in\mathcal{S}\times\mathcal{A}}{\mathcal{W}}{\left({p^{\prime}(\cdot|s,a)},{p(\cdot|s,a)}\right)}$,
that, instead, we relax considering the Wasserstein distance averaged over the
$\gamma$-discounted stationary distribution, i.e.,
$\int_{\mathcal{S}\times\mathcal{A}}\mu_{\pi,p}(\mathrm{d}s)\pi(\mathrm{d}a|s){\mathcal{W}}{\left({p^{\prime}(\cdot|s,a)},{p(\cdot|s,a)}\right)}$.

Finally, in Saleh et al., (2022) a bound on the Wasserstein distance between
the $\gamma$-discounted stationary distributions, as a function of the
modification of the policy only, is proposed under a different set of
regularity assumptions. In particular, two conditions on the transition kernel
are enforced for every $\pi,\pi^{\prime}\in\Delta^{\mathcal{A}}_{\mathcal{S}}$
and $\nu,\nu^{\prime}\in\Delta^{\mathcal{S}}$:

$\displaystyle{\mathcal{W}}{\left({\int_{\mathcal{S}}\nu(\mathrm{d}s)p_{\pi}(\cdot|s)},{\int_{\mathcal{S}}\nu(\mathrm{d}s)p_{\pi^{\prime}}(\cdot|s)}\right)}\leq\widetilde{L}_{\pi}\sup_{s\in\mathcal{S}}{\mathcal{W}}{\left({\pi(\cdot|s)},{\pi^{\prime}(\cdot|s)}\right)},$
$\displaystyle{\mathcal{W}}{\left({\int_{\mathcal{S}}\nu(\mathrm{d}s)p_{\pi}(\cdot|s)},{\int_{\mathcal{S}}\nu^{\prime}(\mathrm{d}s)p_{\pi}(\cdot|s)}\right)}\leq\widetilde{L}_{\nu}{\mathcal{W}}{\left({\nu},{\nu^{\prime}}\right)},$

where $\widetilde{L}_{\pi}$ and $\widetilde{L}_{\nu}$ are suitable Lipschitz
constants. These conditions, however, are not comparable with the ones
considered in the present paper (Section 3), as they evaluate how fast the
transition kernel changes when altering either the policy or the initial state
distribution. Consequently, it is hard to argue whether of the resulting bound
is tighter than ours. Nevertheless, it is worth noting that ours is the only
one that involves the average Wasserstein distance between policies, rather
than the supremum over the state (or state-action) space.

##  5 Relative Advantage Functions

In this section, we revise the _relative advantage functions_ for Conf-MDPs
that are needed for the derivation of the performance improvement bounds, as
introduced in Metelli et al., (2018); Metelli, (2021). The notion of
_advantage function_ exists in the traditional MDP setting and evaluates the
one-step improvement in executing an action $a\in\mathcal{A}$ compared to
executing the current policy $\pi\in\Delta^{\mathcal{A}}_{\mathcal{S}}$
Puterman, (1994).

We now extend the advantage function notion to the Conf-MDP setting, properly
accounting for the presence of the agent and the configuration. Specifically,
we introduce three notions: the _policy_ advantage function, the
_configuration_ advantage function, and the _coupled_ advantage function,
respectively defined for every
$(s,a,s^{\prime})\in\mathcal{S}\times\mathcal{A}\times\mathcal{S}$ as:

$\displaystyle A_{\pi,p}(s,a)=q_{\pi,p}(s,a)-v_{\pi,p}(s),$ $\displaystyle
A_{\pi,p}(s,a,s^{\prime})=u_{\pi,p}(s,a,s^{\prime})-q_{\pi,p}(s,a),$
$\displaystyle\widetilde{A}_{\pi,p}(s,a,s^{\prime})=u_{\pi,p}(s,a,s^{\prime})-v_{\pi,p}(s)=A_{\pi,p}(s,a,s^{\prime})+A_{\pi,p}(s,a).$

These functions evaluate the one-step performance improvement obtained in
state $s\in\mathcal{S}$ by either playing action $a\in\mathcal{A}$, for the
policy advantage, selecting the next state $s^{\prime}\in\mathcal{S}$ given
that action $a\in\mathcal{A}$ was played, for the model advantage, or both for
the coupled advantage, compared to playing policy $\pi$ and transition model
$p$.

To quantify the one-step improvement in performance attained by a new policy
$\pi^{\prime}$ or transition model $p^{\prime}$ when the current policy is
$\pi$ and the current model is $p$, we introduce the _(decoupled) relative
advantage functions_ (Kakade and Langford,, 2002) defined for every state-
action pair $(s,a)\in\mathcal{S}\times\mathcal{A}$ as:

$\displaystyle
A_{\pi,p}^{\pi^{\prime},p}(s)=\int_{\mathcal{A}}\pi^{\prime}(\mathrm{d}a|s)A_{\pi,p}(s,a),$
$\displaystyle
A_{\pi,p}^{\pi,p^{\prime}}(s,a)=\int_{\mathcal{S}}p^{\prime}(\mathrm{d}s^{\prime}|s,a)A_{\pi,p}(s,a,s^{\prime}),$

and the corresponding expected values under the $\gamma$-discounted
distributions:

$\displaystyle\mathbb{A}_{\pi,p,\rho}^{\pi^{\prime},p}=\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)A_{\pi,p}^{\pi^{\prime},p}(s)$
$\displaystyle\mathbb{A}_{\pi,p,\rho}^{\pi,p^{\prime}}=\int_{\mathcal{S}}\int_{\mathcal{A}}\mu_{\pi,p}(\mathrm{d}s)\pi(\mathrm{d}a|s)A_{\pi,p}^{\pi,p^{\prime}}(s,a).$

In order to account for the combined effect of choosing the action with a new
policy $\pi^{\prime}$ and the next state with the new configuration
$p^{\prime}$, we introduce the _coupled relative advantage function_ defined
for every state $s\in\mathcal{S}$ as:

$A_{\pi,p}^{\pi^{\prime},p^{\prime}}(s)=\int_{\mathcal{S}}\int_{\mathcal{A}}\pi^{\prime}(\mathrm{d}a|s)p^{\prime}(\mathrm{d}s^{\prime}|s,a)\widetilde{A}_{\pi,p}(s,a,s^{\prime}).$

Thus, $A_{\pi,p}^{\pi^{\prime},p^{\prime}}$ evaluates the one-step improvement
obtained by the new policy-configuration pair
$(\pi^{\prime},p^{\prime})\in\Delta^{\mathcal{A}}_{\mathcal{S}}\times\Delta^{\mathcal{S}}_{\mathcal{S}\times\mathcal{A}}$
over the current one
$(\pi,p)\in\Delta^{\mathcal{A}}_{\mathcal{S}}\times\Delta^{\mathcal{S}}_{\mathcal{S}\times\mathcal{A}}$,
i.e., the local gain in performance achieved by selecting an action with
$\pi^{\prime}$ and the next state with $p^{\prime}$. The corresponding
expectation under the $\gamma$-discounted distribution is given by:

$\mathbb{A}_{\pi,p,\rho}^{\pi^{\prime},p^{\prime}}=\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)A_{\pi,p}^{\pi^{\prime},p^{\prime}}(s).$

To lighten the notation, we remove the subscript of the initial state
distribution $\rho$ whenever clear from the context. Thus, we simply write
$\mathbb{A}_{\pi,p}^{\pi^{\prime},p}$, $\mathbb{A}_{\pi,p}^{\pi,p^{\prime}}$,
and $\mathbb{A}_{\pi,p}^{\pi^{\prime},p^{\prime}}$. The following result
relates the coupled relative advantage function with the corresponding
(decoupled) relative advantage functions.

######  Lemma 5.1 (Lemma A.1 of Metelli et al., (2018)).

Let $A_{\pi,p}^{\pi^{\prime},p^{\prime}}$ be the coupled relative advantage
function, $A_{\pi,p}^{\pi^{\prime},p}$ and $A_{\pi,p}^{\pi,p^{\prime}}$ be the
(decoupled) policy and configuration relative advantage functions
respectively. Then, for every state $s\in\mathcal{S}$ it holds that:

$A_{\pi,p}^{\pi^{\prime},p^{\prime}}(s)=A_{\pi,p}^{\pi^{\prime},p}(s)+\int_{\mathcal{A}}\pi^{\prime}(\mathrm{d}a|s)A_{\pi,p}^{\pi,p^{\prime}}(s,a).$

This result has a meaningful interpretation. In order to assess the one-step
performance improvement in state $s\in\mathcal{S}$ obtained moving from
policy-configuration pair $(\pi,p)$ to the new one
$(\pi^{\prime},p^{\prime})$, i.e., $A_{\pi,p}^{\pi^{\prime},p^{\prime}}(s)$,
we can add the contribution of two terms: (i) the one-step performance
improvement due to the policy, i.e., $A_{\pi,p}^{\pi^{\prime},p}(s)$; (ii) the
one-step performance improvement due to the configuration, i.e.,
$A_{\pi,p}^{\pi,p^{\prime}}(s,a)$, with the action sampled from the new policy
$\pi^{\prime}$.

##  6 Bound on the Performance Improvement

In this section, we make use of the results provided in the previous sections,
to derive lower bounds on the performance improvement yielded by changing the
policy and the configuration. We start the section by revising the performance
difference lemma for Conf-MDPs, as derived in Metelli et al., (2018). Then, we
proceed at proving the performance improvement lower bounds. Specifically, in
Section 6.1, we derive a tight lower bound that, unfortunately, is hardly
usable in practice since it involves the presence of non-easily computable
quantities and keeps together the contributions of the policy and the
configuration (coupled). Then, in Section 6.2, we derive a looser bound that
separates the effect of policy and configuration (decoupled) and just requires
the LC property.

######  Theorem 6.1 (Performance Difference Lemma - Theorem 3.1 of Metelli et
al., (2018)).

Let $\mathcal{C}$ be a Conf-MDP. The performance improvement of policy-
configuration pair
$(\pi^{\prime},p^{\prime})\in\Delta^{\mathcal{A}}_{\mathcal{S}}\times\Delta^{\mathcal{S}}_{\mathcal{S}\times\mathcal{A}}$
over
$(\pi,p)\in\Delta^{\mathcal{A}}_{\mathcal{S}}\times\Delta^{\mathcal{S}}_{\mathcal{S}\times\mathcal{A}}$
is given by:

$J_{\pi^{\prime},p^{\prime}}-J_{\pi,p}=\frac{1}{1-\gamma}\int_{\mathcal{S}}\mu_{\pi^{\prime},p^{\prime}}(\mathrm{d}s)A_{\pi,p}^{\pi^{\prime},p^{\prime}}(s).$

This result represents the extension of the well-known performance difference
lemma of Kakade and Langford, (2002) to the case in which we are allowed to
change the transition model (i.e., configuration) too. The meaning of the
result can be summarized as follows. The performance improvement
$J_{\pi^{\prime},p^{\prime}}-J_{\pi,p}$ attained by moving from pair $(\pi,p)$
to pair $(\pi^{\prime},p^{\prime})$ is computed by means of the coupled
relative advantage function $A_{\pi,p}^{\pi^{\prime},p^{\prime}}$, averaged
over the $\gamma$-discounted stationary distribution
$\mu_{\pi^{\prime},p^{\prime}}$, induced by the new pair
$(\pi^{\prime},p^{\prime})$.

###  6.1 Coupled Bound

From a practical perspective, the expression of Theorem 6.1 is an equality but
cannot be directly used since it requires computing (or estimating) an
expectation w.r.t. the $\gamma$-discounted distribution
$\mu_{\pi^{\prime},p^{\prime}}$, depending on the new pair
$(\pi^{\prime},p^{\prime})$ that we have not access to. Instead, we would like
to obtain a performance improvement lower bound that can be estimated by using
the current pair $(\pi,p)$. The following result serves the purpose.

######  Theorem 6.2 (Coupled Bound).

Let $\mathcal{C}$ be a $L_{r}$-LC Conf-MDP, let
$\pi,\pi^{\prime}\in\Delta^{\mathcal{A}}_{\mathcal{S}}$ be two
$L_{\pi},L_{\pi^{\prime}}$-LC policies respectively, and let
$p,p^{\prime}\in\Delta^{\mathcal{S}}_{\mathcal{S}\times\mathcal{A}}$ be two
$L_{p},L_{p^{\prime}}$-LC configurations. The performance improvement of
policy-configuration pair $(\pi^{\prime},P^{\prime})$ over $(\pi,P)$ is lower
bounded as:

$\underbrace{J_{\pi^{\prime},{p}^{\prime}}-J_{\pi,{p}}}_{\begin{subarray}{c}\text{performance}\\\
\text{improvement}\end{subarray}}\geq\underbrace{\frac{1}{1-\gamma}\mathbb{A}_{\pi,{p}}^{\pi^{\prime},{p}^{\prime}}}_{\text{advantage}}-\underbrace{\frac{\gamma}{(1-\gamma)(1-\gamma
L_{p^{\prime}}(1+L_{\pi^{\prime}}))}\,\left\|A_{\pi,p}^{\pi^{\prime},p^{\prime}}\right\|_{L}\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)\mathcal{W}{\left({p^{\prime}}_{\pi^{\prime}}(\cdot|s),{p}_{\pi}(\cdot|s)\right)}}_{\text{dissimilarity
penalization}}.$

###### Proof.

Exploiting the bounds on the $\gamma$-discounted state distributions
difference (Theorem 4.1) we can easily derive the performance improvement
bound:

$\displaystyle J_{\pi^{\prime},p^{\prime}}-J_{\pi,p}$
$\displaystyle=\frac{1}{1-\gamma}\int_{\mathcal{S}}\mu_{\pi^{\prime},p^{\prime}}(\mathrm{d}s)A_{\pi,p}^{\pi^{\prime},p^{\prime}}(s)$
$\displaystyle=\frac{1}{1-\gamma}\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)A_{\pi,p}^{\pi^{\prime},p^{\prime}}(s)+\frac{1}{1-\gamma}\int_{\mathcal{S}}\left(\mu_{\pi^{\prime},p^{\prime}}(\mathrm{d}s)-\mu_{\pi,p}(\mathrm{d}s)\right)A_{\pi,p}^{\pi^{\prime},p^{\prime}}(s)$
(9)
$\displaystyle\geq\frac{\mathbb{A}_{\pi,p}^{\pi^{\prime},p^{\prime}}}{1-\gamma}-\frac{1}{1-\gamma}\bigg{|}\int_{\mathcal{S}}\left(\mu_{\pi^{\prime},p^{\prime}}(\mathrm{d}s)-\mu_{\pi,p}(\mathrm{d}s)\right)A_{\pi,p}^{\pi^{\prime},p^{\prime}}(s)\bigg{|}$
(10)
$\displaystyle\geq\frac{\mathbb{A}_{{\pi,p}}^{\pi^{\prime},p^{\prime}}}{1-\gamma}-\frac{\gamma}{(1-\gamma)(1-\gamma
L_{p^{\prime}}(1+L_{\pi^{\prime}}))}\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s){\mathcal{W}}\left({p^{\prime}}_{\pi^{\prime}}(\cdot|s),{p}_{\pi}(\cdot|s)\right)\left\|A_{\pi,p}^{\pi^{\prime},p^{\prime}}\right\|_{L},$
(11)

where line (10) follows from line (9) by observing that $b\geq-|b|$ for any
$b\in\mathbb{R}$ and line (11) is obtained by using Theorem 4.1 and the
definition of Lipschitz semi-norm. ∎

The resulting bound is made of two terms, as the commonly known bounds in the
literature (Kakade and Langford,, 2002; Pirotta et al.,, 2013; Metelli et
al.,, 2021). The first term, _advantage_ , accounts for the improvement in
performance that can be obtained locally by replacing the pair $(\pi,p)$ with
the new one $(\pi^{\prime},p^{\prime})$. Instead, the second term,
_dissimilarity penalization_ , disincentives a choice of the next pair that is
too dissimilar from the current one. As expected, the multiplicative constant
in front of the Wasserstein distance between the state-state transition
kernels involves the Lipschitz constants of all the constitutive elements of
the Conf-MDP, policy, and configuration.

###  6.2 Decoupled Bound

Despite its generality, the bound of Theorem 6.2 is hardly usable in practice
because of the need for computing the Lipschitz semi-norm
$\|A_{\pi,p}^{\pi^{\prime},p^{\prime}}\|_{L}$. Intuitively, this factor
strictly depends on the similarity between the policy-configuration pairs
$(\pi,p)$ and $(\pi^{\prime},p^{\prime})$. Indeed, when
$(\pi,p)=(\pi^{\prime},p^{\prime})$ a.s., we have that
$A_{\pi,p}^{\pi^{\prime},p^{\prime}}(s)=0$ for all $s\in\mathcal{S}$ and,
consequently, $\|A_{\pi,p}^{\pi^{\prime},p^{\prime}}\|_{L}=0$. Unfortunately,
obtaining a bound on this Lipschitz semi-norm that depends on some form of
distance between the pairs $(\pi,p)$ and $(\pi^{\prime},p^{\prime})$ is
technically challenging and may require additional assumptions. Thus, we defer
this goal to future works, in this section, we focus on a simpler (and looser)
bound that makes use of the LC condition only, accepting to bound
$\|A_{\pi,p}^{\pi^{\prime},p^{\prime}}\|_{L}$ with a constant independent from
the distance between the pairs $(\pi,p)$ and $(\pi^{\prime},p^{\prime})$. The
following result provides such a bound.

######  Theorem 6.3 (Decoupled Bound for Lipschitz Conf-MDPs).

Let $\mathcal{C}$ be a $L_{r}$-LC Conf-MDP, let
$\pi,\pi^{\prime}\in\Delta^{\mathcal{A}}_{\mathcal{S}}$ be two
$L_{\pi},L_{\pi^{\prime}}$-LC policies respectively, and let
$p,p^{\prime}\in\Delta^{\mathcal{S}}_{\mathcal{S}\times\mathcal{A}}$ be two
$L_{p},L_{p^{\prime}}$-LC configurations. The performance improvement of
policy-configuration pair $(\pi^{\prime},P^{\prime})$ over $(\pi,P)$ is lower
bounded as:

$\displaystyle
J_{\pi^{\prime},{p}^{\prime}}-J_{\pi,{p}}\geq\frac{\mathbb{A}_{\pi,{p}}^{\pi^{\prime},{p}}+\mathbb{A}_{\pi,{p}}^{\pi,{p}^{\prime}}}{1-\gamma}-$
$\displaystyle\Bigg{(}c_{1}\int_{\mathcal{S}\times\mathcal{A}}\mu_{\pi,p}(\mathrm{d}s)\pi(\mathrm{d}a|s)\mathcal{W}{\left(p^{\prime}(\cdot|s,a),p(\cdot|s,a)\right)}$
$\displaystyle\qquad+c_{2}\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)\mathcal{W}{\left(\pi^{\prime}(\cdot|s),\pi(\cdot|s)\right)}\Bigg{)},$

where $c_{1}$ and $c_{2}$ are constant whose values are made explicit in the
proof and depend on $\gamma$, $L_{r}$, $L_{\pi}$, $L_{\pi^{\prime}}$, $L_{p}$,
and $L_{p^{\prime}}$.

Some observations are in order. First, in order to obtain this result, we need
to require that the Conf-MDP and both pairs $(\pi,p)$ and
$(\pi^{\prime},p^{\prime})$ to be LC. Indeed, the constants $c_{1}$ and
$c_{2}$ will depend on the Lipschitz semi-norm of the Conf-MDP elements, and
on the Lipschitz constants of both policies and both configurations. Second,
Theorem 6.3 represents an decoupled bound, that separates the effects of the
policy and the configuration. This is made evident in the advantage term too
that is now replaced with the sum of the expected decoupled relative
advantages. Third, and more important, the bound displays a linear dependence
on the Wasserstein distance between the transition models and the policies.
Compared to well-known bounds in the literature in which the square of the
divergence is present (typically TV divergence), such as Pirotta et al.,
(2013), this represents a looser dependence.

##  7 Conclusions

In this paper, we have investigated the performance improvement bounds for
Conf-MDP under Lipschitz regularity. We have first derived bounds on the
Wasserstein distance between $\gamma$-discounted stationary distributions that
generalize existing bounds in the literature. Then, we have provided two
performance improvement lower bounds. Future promising works include the
employment of the derived bounds for devising safe and trust region learning
algorithms.

## References

  * Achiam et al., (2017) Achiam, J., Held, D., Tamar, A., and Abbeel, P. (2017).  Constrained policy optimization.  In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 22–31.
  * Asadi et al., (2018) Asadi, K., Misra, D., and Littman, M. L. (2018).  Lipschitz continuity in model-based reinforcement learning.  In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 264–273.
  * Kakade and Langford, (2002) Kakade, S. M. and Langford, J. (2002).  Approximately optimal approximate reinforcement learning.  In Machine Learning, Proceedings of the Nineteenth International Conference (ICML), pages 267–274. Morgan Kaufmann.
  * Metelli, (2021) Metelli, A. M. (2021).  Exploiting Environment Configurability in Reinforcement Learning.  PhD thesis, Politecnico di Milano.
  * Metelli, (2022) Metelli, A. M. (2022).  Configurable environments in reinforcement learning: An overview.  Special Topics in Information Technology, pages 101–113.
  * Metelli et al., (2019) Metelli, A. M., Ghelfi, E., and Restelli, M. (2019).  Reinforcement learning in configurable continuous environments.  In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 4546–4555.
  * Metelli et al., (2022) Metelli, A. M., Manneschi, G., and Restelli, M. (2022).  Policy space identification in configurable environments.  Mach. Learn., 111(6):2093–2145.
  * Metelli et al., (2020) Metelli, A. M., Mazzolini, F., Bisi, L., Sabbioni, L., and Restelli, M. (2020).  Control frequency adaptation via action persistence in batch reinforcement learning.  In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 6862–6873.
  * Metelli et al., (2018) Metelli, A. M., Mutti, M., and Restelli, M. (2018).  Configurable markov decision processes.  In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 3488–3497.
  * Metelli et al., (2021) Metelli, A. M., Pirotta, M., Calandriello, D., and Restelli, M. (2021).  Safe policy iteration: A monotonically improving approximate policy iteration approach.  J. Mach. Learn. Res., 22:97:1–97:83.
  * Munos and Szepesvári, (2008) Munos, R. and Szepesvári, C. (2008).  Finite-time bounds for fitted value iteration.  J. Mach. Learn. Res., 9:815–857.
  * Pirotta et al., (2015) Pirotta, M., Restelli, M., and Bascetta, L. (2015).  Policy gradient in lipschitz markov decision processes.  Mach. Learn., 100(2-3):255–283.
  * Pirotta et al., (2013) Pirotta, M., Restelli, M., Pecorino, A., and Calandriello, D. (2013).  Safe policy iteration.  In Proceedings of the 30th International Conference on Machine Learning (ICML), pages 307–315.
  * Puterman, (1994) Puterman, M. L. (1994).  Markov Decision Processes: Discrete Stochastic Dynamic Programming.  Wiley Series in Probability and Statistics. Wiley.
  * Rachelson and Lagoudakis, (2010) Rachelson, E. and Lagoudakis, M. G. (2010).  On the locality of action domination in sequential decision making.  In International Symposium on Artificial Intelligence and Mathematics, ISAIM 2010.
  * Ramponi et al., (2021) Ramponi, G., Metelli, A. M., Concetti, A., and Restelli, M. (2021).  Learning in non-cooperative configurable markov decision processes.  In Advances in Neural Information Processing Systems 34 (NeurIPS), pages 22808–22821.
  * Saleh et al., (2022) Saleh, E., Ghaffari, S., Bretl, T., and West, M. (2022).  Truly deterministic policy optimization.  CoRR, abs/2205.15379.
  * Schulman et al., (2015) Schulman, J., Levine, S., Abbeel, P., Jordan, M. I., and Moritz, P. (2015).  Trust region policy optimization.  In Proceedings of the 32nd International Conference on Machine Learning (ICML), pages 1889–1897.
  * Sutton and Barto, (2018) Sutton, R. S. and Barto, A. G. (2018).  Reinforcement learning: An introduction.  MIT press.
  * Sutton et al., (1999) Sutton, R. S., McAllester, D. A., Singh, S. P., and Mansour, Y. (1999).  Policy gradient methods for reinforcement learning with function approximation.  In Advances in Neural Information Processing Systems 12, (NIPS), pages 1057–1063. The MIT Press.
  * Villani, (2009) Villani, C. (2009).  Optimal transport: old and new, volume 338.  Springer.

##  8 Proofs Omitted in the Main Paper

In this appendix, we report the proofs we have omitted in the main paper.

See 4.2

###### Proof.

Let $s\in\mathcal{S}$, we start from Theorem 4.1 and apply triangular
inequality:

$\displaystyle\mathcal{W}{\left({p^{\prime}}_{\pi^{\prime}}(\cdot|s),{p}_{\pi}(\cdot|s)\right)}\leq\mathcal{W}{\left({p^{\prime}}_{\pi^{\prime}}(\cdot|s),{p^{\prime}}_{\pi}(\cdot|s)\right)}+\mathcal{W}{\left({p^{\prime}}_{\pi}(\cdot|s),{p}_{\pi}(\cdot|s)\right)}.$

For the first term, we have:

$\displaystyle\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)\mathcal{W}{\left({p^{\prime}}_{\pi^{\prime}}(\cdot|s),{p^{\prime}}_{\pi}(\cdot|s)\right)}$
$\displaystyle=\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)\sup_{f:\left\|f\right\|_{L{}}\leq
1}\left|\int_{\mathcal{S}}\left({p^{\prime}}_{\pi^{\prime}}(\mathrm{d}s^{\prime}|s)-{p^{\prime}}_{\pi}(\mathrm{d}s^{\prime}|s)\right)f(s^{\prime})\right|$
$\displaystyle=\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)\sup_{f:\left\|f\right\|_{L{}}\leq
1}\left|\int_{\mathcal{A}}\left(\pi^{\prime}(\mathrm{d}a|s)-\pi(\mathrm{d}a|s)\right)\underbrace{\int_{\mathcal{S}}p^{\prime}(\mathrm{d}s^{\prime}|s,a)f(s^{\prime})}_{\eqqcolon
h_{f}(s,a)}\right|$ $\displaystyle\leq\sup_{f:\left\|f\right\|_{L{}}\leq
1}\left\|{h_{f}}\right\|_{L}\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s){\mathcal{W}}{\left({\pi^{\prime}(\cdot|s)},{\pi(\cdot|s)}\right)},$
(12)

where the lats passage follows from the definition of Wasserstein distance and
Lipschitz semi-norm. We now compute the Lipschitz semi-norm
$\left\|{h_{f}}\right\|_{L}$. Let
$(s,a),(\overline{s},\overline{a})\in\mathcal{S}\times\mathcal{A}$:

$\displaystyle
h_{f}(s,a)-h_{f}(\overline{s},\overline{a})=\int_{\mathcal{S}}\left(p^{\prime}(\mathrm{d}s^{\prime}|s,a)-p^{\prime}(\mathrm{d}s^{\prime}|\overline{s},\overline{a})\right)f(s^{\prime})\leq{\mathcal{W}}{\left({p^{\prime}(\cdot|s,a)},{p^{\prime}(\cdot|\overline{s},\overline{a})}\right)}\leq
L_{p^{\prime}}d_{\mathcal{S}\times\mathcal{A}}((s,a),(\overline{s},\overline{a})).$

For the second term, we have:

$\displaystyle\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)\mathcal{W}{\left({p^{\prime}}_{\pi}(\cdot|s),{p}_{\pi}(\cdot|s)\right)}$
$\displaystyle=\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)\sup_{f:\left\|f\right\|_{L{}}\leq
1}\left|\int_{\mathcal{S}}\left({p^{\prime}}_{\pi}(\mathrm{d}s^{\prime}|s)-{p}_{\pi}(\mathrm{d}s^{\prime}|s)\right)f(s^{\prime})\right|$
$\displaystyle=\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)\sup_{f:\left\|f\right\|_{L{}}\leq
1}\left|\int_{\mathcal{A}}\pi(\mathrm{d}a|s)\int_{\mathcal{S}}\left(p^{\prime}(\mathrm{d}s^{\prime}|s,a)-p(\mathrm{d}s^{\prime}|s,a)\right)f(s^{\prime})\right|$
$\displaystyle\leq\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)\int_{\mathcal{A}}\pi(\mathrm{d}a|s)\sup_{f:\left\|f\right\|_{L{}}\leq
1}\left|\int_{\mathcal{S}}\left(p^{\prime}(\mathrm{d}s^{\prime}|s,a)-p(\mathrm{d}s^{\prime}|s,a)\right)f(s^{\prime})\right|$
$\displaystyle=\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)\int_{\mathcal{A}}\pi(\mathrm{d}a|s){\mathcal{W}}{\left({p^{\prime}(\mathrm{d}s^{\prime}|s,a)},{p(\mathrm{d}s^{\prime}|s,a)}\right)},$

where the inequality follows from Jensen’s inequality. Putting all together,
we get the result. ∎

See 5.1

###### Proof.

Let $s\in\mathcal{S}$, let us consider the following derivation:

$\displaystyle A_{\pi,p}^{\pi^{\prime},p^{\prime}}(s)$
$\displaystyle=\int_{\mathcal{A}}\int_{\mathcal{S}}\pi^{\prime}(\mathrm{d}a|s)p^{\prime}(\mathrm{d}s^{\prime}|s,a)u_{\pi,p}(s,a,s^{\prime})-v_{\pi,p}(s)$
$\displaystyle=\int_{\mathcal{A}}\int_{\mathcal{S}}\pi^{\prime}(\mathrm{d}a|s)p^{\prime}(\mathrm{d}s^{\prime}|s,a)u_{\pi,p}(s,a,s^{\prime})-v_{\pi,p}(s)\pm\int_{\mathcal{A}}\int_{\mathcal{S}}\pi^{\prime}(\mathrm{d}a|s)p(\mathrm{d}s^{\prime}|s,a)u_{\pi,p}(s,a,s^{\prime})$
$\displaystyle=\int_{\mathcal{A}}\int_{\mathcal{S}}\pi^{\prime}(\mathrm{d}a|s)p(\mathrm{d}s^{\prime}|s,a)u_{\pi,p}(s,a,s^{\prime})-v_{\pi,p}(s)$
(13)
$\displaystyle\quad+\int_{\mathcal{A}}\int_{\mathcal{S}}\pi^{\prime}(\mathrm{d}a|s)\left(p^{\prime}(\mathrm{d}s^{\prime}|s,a)-p(\mathrm{d}s^{\prime}|s,a)\right)u_{\pi,p}(s,a,s^{\prime})$
$\displaystyle=\int_{\mathcal{A}}\pi^{\prime}(\mathrm{d}a|s)q_{\pi,p}(s,a)\mathrm{d}a-v_{\pi,p}(s)+\int_{\mathcal{A}}\pi^{\prime}(\mathrm{d}a|s)\int_{\mathcal{S}}\left(p^{\prime}(\mathrm{d}s^{\prime}|s,a)-p(\mathrm{d}s^{\prime}|s,a)\right)u_{\pi,p}(s,a,s^{\prime})$
(14)
$\displaystyle=A_{\pi,p}^{\pi^{\prime},p}(s)+\int_{\mathcal{A}}\pi^{\prime}(\mathrm{d}a|s)A_{\pi,p}^{\pi,p^{\prime}}(s,a),$
(15)

where line (14) is obtained by recalling that
$q_{\pi,p}(s,a)=\int_{\mathcal{S}}p(\mathrm{d}s^{\prime}|s,a)u_{\pi,p}(s,a,s^{\prime})$,
the first addendum of line (15) follows from observing that:

$A_{\pi,p}^{\pi^{\prime},p}(s)=\int_{\mathcal{A}}\pi^{\prime}(\mathrm{d}a|s)A^{\pi,p}(s,a)=\int_{\mathcal{A}}\pi^{\prime}(\mathrm{d}a|s)\left(q_{\pi,p}(s,a)-v_{\pi,p}(s)\right),$

and similarly the second addendum of line (15) comes from the identity:

$\displaystyle A_{\pi,p}^{\pi,p^{\prime}}(s,a)$
$\displaystyle=\int_{\mathcal{S}}p^{\prime}(\mathrm{d}s^{\prime}|s,a)A^{\pi,p}(s,a,s^{\prime})=\int_{\mathcal{S}}p^{\prime}(\mathrm{d}s^{\prime}|s,a)\left(u_{\pi,p}(s,a,s^{\prime})-q_{\pi,p}(s,a)\right).$

∎

See 6.1

###### Proof.

Let us start from the definition of $J^{\pi^{\prime},P^{\prime}}$:

$\displaystyle(1-\gamma)J_{\pi^{\prime},p^{\prime}}$
$\displaystyle=\int_{\mathcal{S}}\int_{\mathcal{A}}\int_{\mathcal{S}}\mu_{\pi^{\prime},p^{\prime}}(\mathrm{d}s)\pi^{\prime}(\mathrm{d}a|s)p^{\prime}(\mathrm{d}s^{\prime}|s,a)r(s,a,s^{\prime})$
$\displaystyle=\int_{\mathcal{S}}\int_{\mathcal{A}}\int_{\mathcal{S}}\mu_{\pi^{\prime},p^{\prime}}(\mathrm{d}s)\pi^{\prime}(\mathrm{d}a|s)p^{\prime}(\mathrm{d}s^{\prime}|s,a)r(s,a,s^{\prime})\pm\int_{\mathcal{S}}\mu_{\pi^{\prime},p^{\prime}}(\mathrm{d}s)v_{\pi,p}(s)$
(16)
$\displaystyle=\int_{\mathcal{S}}\int_{\mathcal{A}}\int_{\mathcal{S}}\mu_{\pi^{\prime},p^{\prime}}(\mathrm{d}s)\pi^{\prime}(\mathrm{d}a|s)p^{\prime}(\mathrm{d}s^{\prime}|s,a)r(s,a,s^{\prime})$
(17)
$\displaystyle\quad+\int_{\mathcal{S}}\left((1-\gamma)\rho(\mathrm{d}s^{\prime})+\gamma\int_{\mathcal{S}}\int_{\mathcal{A}}\mu_{\pi^{\prime},p^{\prime}}(\mathrm{d}s)\pi^{\prime}(\mathrm{d}a|s)p^{\prime}(\mathrm{d}s^{\prime}|s,a)\right)v_{\pi,p}(s^{\prime})$
$\displaystyle\quad-\int_{\mathcal{S}}\mu_{\pi^{\prime},p^{\prime}}(\mathrm{d}s)v_{\pi,p}(s)$
$\displaystyle=\int_{\mathcal{S}}\mu_{\pi^{\prime},p^{\prime}}(\mathrm{d}s)\left(\int_{\mathcal{A}}\pi^{\prime}(\mathrm{d}a|s)\int_{\mathcal{S}}p^{\prime}(\mathrm{d}s^{\prime}|s,a)\left(r(s,a,s^{\prime})+\gamma
v_{\pi,p}(s^{\prime})\right)-v_{\pi,p}(s)\right)$
$\displaystyle\quad+\int_{\mathcal{S}}\rho(\mathrm{d}s^{\prime})v_{\pi,p}(s^{\prime})$
$\displaystyle=\int_{\mathcal{S}}\mu_{\pi^{\prime},p^{\prime}}(\mathrm{d}s)A_{\pi,p}^{\pi^{\prime},p^{\prime}}(s)+(1-\gamma)J_{\pi,p},$
(18)

where we have made use of the recursive formulation of
$\mu_{\pi^{\prime},p^{\prime}}$ (Equation 2) to rewrite line (16) into line
(17) and line (18) follows by observing that
$\int_{\mathcal{S}}\rho(\mathrm{d}s^{\prime})v_{\pi,p}(s^{\prime})=J_{\pi,p}$
and using the definition $u_{\pi,p}(s,a,s^{\prime})=r(s,a,s^{\prime})+\gamma
v_{\pi,p}(s^{\prime})$. ∎

See 6.3

###### Proof.

We provide a bound on the Lipschitz semi-norm
$\left\|A_{\pi,p}^{\pi^{\prime},p^{\prime}}\right\|_{L}$. Let
$s,\overline{s}\in\mathcal{S}$:

$\displaystyle
A_{\pi,p}^{\pi^{\prime},p^{\prime}}(s)-A_{\pi,p}^{\pi^{\prime},p^{\prime}}(\overline{s})$
$\displaystyle=\int_{\mathcal{S}\times\mathcal{A}}\pi^{\prime}(\mathrm{d}a|s)p^{\prime}(\mathrm{d}s^{\prime}|s,a)u_{\pi,p}(s,a,s^{\prime})-v_{\pi,p}(s)$
$\displaystyle\quad-\int_{\mathcal{S}\times\mathcal{A}}\pi^{\prime}(\mathrm{d}a|\overline{s})p^{\prime}(\mathrm{d}s^{\prime}|\overline{s},a)u_{\pi,p}(\overline{s},a,s^{\prime})-v_{\pi,p}(\overline{s})$
$\displaystyle=\underbrace{\int_{\mathcal{S}\times\mathcal{A}}\pi^{\prime}(\mathrm{d}a|s)p^{\prime}(\mathrm{d}s^{\prime}|s,a)(u_{\pi,p}(s,a,s^{\prime})-u_{\pi,p}(\overline{s},a,s^{\prime}))}_{\text{(a)}}$
$\displaystyle\quad+\underbrace{\int_{\mathcal{S}\times\mathcal{A}}\left(\pi^{\prime}(\mathrm{d}a|s)p^{\prime}(\mathrm{d}s^{\prime}|s,a)-\pi^{\prime}(\mathrm{d}a|\overline{s})p^{\prime}(\mathrm{d}s^{\prime}|\overline{s},a)\right)u_{\pi,p}(\overline{s},a,s^{\prime})}_{\text{(b)}}$
$\displaystyle\quad+\underbrace{v_{\pi,p}(\overline{s})-v_{\pi,p}(s)}_{\text{(c)}}$

#### Term (a)

Concerning term (a), we exploit the Lipschitz semi-norm of the $u_{\pi,p}$
function, to obtain:

$\displaystyle\int_{\mathcal{S}\times\mathcal{A}}\pi^{\prime}(\mathrm{d}a|s)p^{\prime}(\mathrm{d}s^{\prime}|s,a)(u_{\pi,p}(s,a,s^{\prime})-u_{\pi,p}(\overline{s},a,s^{\prime}))\leq\sup_{(a,s^{\prime})\in\mathcal{A}\times\mathcal{S}}\left\|{u_{\pi,p}(\cdot,a,s^{\prime})}\right\|_{L}d_{\mathcal{S}}(s,\overline{s}).$

#### Term (b)

Concerning term (b), we need to perform further manipulations:

$\displaystyle\int_{\mathcal{S}\times\mathcal{A}}$
$\displaystyle\left(\pi^{\prime}(\mathrm{d}a|s)p^{\prime}(\mathrm{d}s^{\prime}|s,a)-\pi^{\prime}(\mathrm{d}a|\overline{s})p^{\prime}(\mathrm{d}s^{\prime}|\overline{s},a)\right)u_{\pi,p}(\overline{s},a,s^{\prime})=$
$\displaystyle\qquad=\int_{\mathcal{A}}\left(\pi^{\prime}(\mathrm{d}a|s)-\pi^{\prime}(\mathrm{d}a|\overline{s})\right)\underbrace{\int_{\mathcal{S}}p^{\prime}(\mathrm{d}s^{\prime}|\overline{s},a)u_{\pi,p}(\overline{s},a,s^{\prime})}_{\eqqcolon
h(\overline{s},a)}$
$\displaystyle\qquad\quad+\int_{\mathcal{S}\times\mathcal{A}}\pi^{\prime}(\mathrm{d}a|s)\left(p^{\prime}(\mathrm{d}s^{\prime}|s,a)-p^{\prime}(\mathrm{d}s^{\prime}|\overline{s},a)\right)u_{\pi,p}(\overline{s},a,s^{\prime})$

For the first integral, we need to compute the Lipschitz semi-norm of
$h(\overline{s},a)$. Let
$(\overline{s},a),(\overline{s}^{\prime},a^{\prime})\in\mathcal{S}\times\mathcal{A}$:

$\displaystyle h(\overline{s},a)-h(\overline{s}^{\prime},a^{\prime})$
$\displaystyle=\int_{\mathcal{S}}p^{\prime}(\mathrm{d}s^{\prime}|\overline{s},a)u_{\pi,p}(\overline{s},a,s^{\prime})-\int_{\mathcal{S}}p^{\prime}(\mathrm{d}s^{\prime}|\overline{s}^{\prime},a^{\prime})u_{\pi,p}(\overline{s}^{\prime},a^{\prime},s^{\prime})$
$\displaystyle=\int_{\mathcal{S}}\left(p^{\prime}(\mathrm{d}s^{\prime}|\overline{s},a)-p^{\prime}(\mathrm{d}s^{\prime}|\overline{s}^{\prime},a^{\prime})\right)u_{\pi,p}(\overline{s},a,s^{\prime})$
$\displaystyle\quad+\int_{\mathcal{S}}p^{\prime}(\mathrm{d}s^{\prime}|\overline{s}^{\prime},a^{\prime})(u_{\pi,p}(\overline{s},a,s^{\prime})-u_{\pi,p}(\overline{s}^{\prime},a^{\prime},s^{\prime}))$
$\displaystyle\leq\sup_{s,a\in\mathcal{S}\times\mathcal{A}}\left\|{u_{\pi,p}(s,a,\cdot)}\right\|_{L}{\mathcal{W}}{\left({p^{\prime}(\cdot|\overline{s},a)},{p^{\prime}(\cdot|\overline{s}^{\prime},a^{\prime})}\right)}+\sup_{s^{\prime}\in\mathcal{S}}\left\|{u_{\pi,p}(\cdot,\cdot,s^{\prime})}\right\|_{L}d_{\mathcal{S}\times\mathcal{A}}((\overline{s},a),(\overline{s}^{\prime},a^{\prime}))$
$\displaystyle\leq\left(\sup_{s,a\in\mathcal{S}\times\mathcal{A}}\left\|{u_{\pi,p}(s,a,\cdot)}\right\|_{L}L_{p^{\prime}}+\sup_{s^{\prime}\in\mathcal{S}}\left\|{u_{\pi,p}(\cdot,\cdot,s^{\prime})}\right\|_{L}\right)d_{\mathcal{S}\times\mathcal{A}}((\overline{s},a),(\overline{s}^{\prime},a^{\prime})).$

Thus, we have:

$\displaystyle\int_{\mathcal{A}}\left(\pi^{\prime}(\mathrm{d}a|s)-\pi^{\prime}(\mathrm{d}a|\overline{s})\right)h(\overline{s},a)$
$\displaystyle\leq{\mathcal{W}}{\left({\pi^{\prime}(\cdot|s)},{\pi^{\prime}(\cdot|\overline{s})}\right)}\left(\sup_{s,a\in\mathcal{S}\times\mathcal{A}}\left\|{u_{\pi,p}(s,a,\cdot)}\right\|_{L}L_{p^{\prime}}+\sup_{s^{\prime}\in\mathcal{S}}\left\|{u_{\pi,p}(\cdot,\cdot,s^{\prime})}\right\|_{L}\right)$
$\displaystyle\leq
L_{\pi^{\prime}}\left(\sup_{s,a\in\mathcal{S}\times\mathcal{A}}\left\|{u_{\pi,p}(s,a,\cdot)}\right\|_{L}L_{p^{\prime}}+\sup_{s^{\prime}\in\mathcal{S}}\left\|{u_{\pi,p}(\cdot,\cdot,s^{\prime})}\right\|_{L}\right)d_{\mathcal{S}}(s,\overline{s}).$

For the second integral, we can simply proceed as follows:

$\displaystyle\int_{\mathcal{S}\times\mathcal{A}}\pi^{\prime}(\mathrm{d}a|s)$
$\displaystyle\left(p^{\prime}(\mathrm{d}s^{\prime}|s,a)-p^{\prime}(\mathrm{d}s^{\prime}|\overline{s},a)\right)u_{\pi,p}(\overline{s},a,s^{\prime})$
$\displaystyle\leq\sup_{(s,a)\in\mathcal{S}\times\mathcal{A}}\left\|{u_{\pi,p}(s,a,\cdot)}\right\|_{L}\int_{\mathcal{S}\times\mathcal{A}}\pi^{\prime}(\mathrm{d}a|s){\mathcal{W}}{\left({p^{\prime}(\mathrm{d}s^{\prime}|s,a)},{p^{\prime}(\mathrm{d}s^{\prime}|\overline{s},a)}\right)}$
$\displaystyle\leq\sup_{(s,a)\in\mathcal{S}\times\mathcal{A}}\left\|{u_{\pi,p}(s,a,\cdot)}\right\|_{L}L_{p^{\prime}}d_{\mathcal{S}}(s,\overline{s}).$

#### Term (c)

Concerning term (c), it is immediate to verify that
$v_{\pi,p}(\overline{s})-v_{\pi,p}(s)\leq\left\|{v_{\pi,p}}\right\|_{L}d_{\mathcal{S}}(s,\overline{s})$.

Finally, we observe that
$\left\|{u_{\pi,p}}\right\|_{L}\geq\max\left\\{\sup_{s,a\in\mathcal{S}\times\mathcal{A}}\left\|{u_{\pi,p}(s,a,\cdot)}\right\|_{L},\sup_{s^{\prime}\in\mathcal{S}}\left\|{u_{\pi,p}(\cdot,\cdot,s^{\prime})}\right\|_{L}\right\\}$.
Thus,
$\left\|{h}\right\|_{L}\leq(1+L_{p^{\prime}})\left\|{u_{\pi,p}}\right\|_{L}$.
With simple algebraic manipulation, we derive that:

$\displaystyle\left\|A_{\pi,p}^{\pi^{\prime},p^{\prime}}\right\|_{L}$
$\displaystyle\leq\left\|{u_{\pi,p}}\right\|_{L}+\left\|{u_{\pi,p}}\right\|_{L}L_{\pi^{\prime}}(1+L_{p^{\prime}})+L_{p^{\prime}}\left\|{u_{\pi,p}}\right\|_{L}+\left\|{v_{\pi,p}}\right\|_{L}$
$\displaystyle\leq\left\|{u_{\pi,p}}\right\|_{L}(1+(L_{\pi^{\prime}}+1)(L_{p^{\prime}}+1))\leq
2\left\|{u_{\pi,p}}\right\|_{L}(L_{\pi^{\prime}}+1)(L_{p^{\prime}}+1).$

By using Lemma 9.2, we have:

$\displaystyle\mathbb{A}_{\pi,p}^{\pi^{\prime},p^{\prime}}$
$\displaystyle\geq\mathbb{A}_{\pi,p}^{\pi,p^{\prime}}+\mathbb{A}_{\pi,p}^{\pi^{\prime},p}-\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s){\mathcal{W}}{\left({\pi^{\prime}(\cdot|s)},{\pi(\cdot|s)}\right)}\left\|{A_{\pi,p}^{\pi,p^{\prime}}}\right\|_{L}$
$\displaystyle\geq\mathbb{A}_{\pi,p}^{\pi,p^{\prime}}+\mathbb{A}_{\pi,p}^{\pi^{\prime},p}-\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s){\mathcal{W}}{\left({\pi^{\prime}(\cdot|s)},{\pi(\cdot|s)}\right)}\left\|A_{\pi,p}^{\pi^{\prime},p^{\prime}}\right\|_{L}$
$\displaystyle\geq\mathbb{A}_{\pi,p}^{\pi,p^{\prime}}+\mathbb{A}_{\pi,p}^{\pi^{\prime},p}-2\left\|{u_{\pi,p}}\right\|_{L}(L_{\pi^{\prime}}+1)(L_{p^{\prime}}+1)\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s){\mathcal{W}}{\left({\pi^{\prime}(\cdot|s)},{\pi(\cdot|s)}\right)},$

having observed that
$\left\|{A_{\pi,p}^{\pi,p^{\prime}}}\right\|_{L}\leq\left\|A_{\pi,p}^{\pi^{\prime},p^{\prime}}\right\|_{L}$.
By exploiting Corollary 4.2, we get the result, having defined the constants
$c_{1}$ and $c_{2}$ as follows:

$\displaystyle
c_{1}=\left\|{u_{\pi,p}}\right\|_{L}\frac{2\gamma(L_{\pi^{\prime}}+1)(L_{p^{\prime}}+1)}{(1-\gamma)(1-\gamma
L_{p^{\prime}}(1+L_{\pi^{\prime}}))},\qquad
c_{2}=\left\|{u_{\pi,p}}\right\|_{L}\frac{2(1+\gamma
L_{p^{\prime}})(L_{\pi^{\prime}}+1)(L_{p^{\prime}}+1)}{(1-\gamma)(1-\gamma
L_{p^{\prime}}(1+L_{\pi^{\prime}}))}.$

∎

##  9 Technical Lemmas

In this appendix, we provide additional technical results that are employed in
the proofs of the results presented in the main paper.

######  Lemma 9.1.

Let
$h_{f}(s)=\int_{\mathcal{S}}{p^{\prime}}_{\pi^{\prime}}(\mathrm{d}s^{\prime}|s)f(s^{\prime})$
with $\|f\|_{L}\leq 1$. Then, it holds that $\left\|{h_{f}}\right\|_{L}\leq
L_{p^{\prime}}(1+L_{\pi^{\prime}})$.

###### Proof.

For $s,\overline{s}\in\mathcal{S}$, we have:

$\displaystyle h_{f}(s)-h_{f}(\overline{s})$
$\displaystyle=\int_{\mathcal{S}}\left({p^{\prime}}_{\pi^{\prime}}(\mathrm{d}s^{\prime}|s)-{p^{\prime}}_{\pi^{\prime}}(\mathrm{d}s^{\prime}|\overline{s})\right)f(s^{\prime})$
$\displaystyle=\int_{\mathcal{S}}\int_{\mathcal{A}}\left(\pi^{\prime}(\mathrm{d}a|s)p^{\prime}(\mathrm{d}s^{\prime}|s,a)-\pi^{\prime}(\mathrm{d}a|\overline{s})p^{\prime}(\mathrm{d}s^{\prime}|\overline{s},a)\right)f(s^{\prime})$
$\displaystyle=\int_{\mathcal{A}}\pi^{\prime}(\mathrm{d}a|s)\int_{\mathcal{S}}\left(p^{\prime}(\mathrm{d}s^{\prime}|s,a)-p(\mathrm{d}s^{\prime}|\overline{s},a)\right)f(s^{\prime})+\int_{\mathcal{A}}\left(\pi^{\prime}(\mathrm{d}a|s)-\pi^{\prime}(\mathrm{d}a|\overline{s})\right)\underbrace{\int_{\mathcal{S}}p^{\prime}(\mathrm{d}s^{\prime}|s,a)f(s^{\prime})}_{\eqqcolon
l_{f}(s,a)}.$

For the first integral, we simply obtain:

$\displaystyle\int_{\mathcal{A}}\pi^{\prime}(\mathrm{d}a|s)\int_{\mathcal{S}}\left(p^{\prime}(\mathrm{d}s^{\prime}|s,a)-p(\mathrm{d}s^{\prime}|\overline{s},a)\right)f(s^{\prime})\leq\int_{\mathcal{A}}\pi^{\prime}(\mathrm{d}a|s){\mathcal{W}}{\left({p^{\prime}(\cdot|s,a)},{p^{\prime}(\cdot|\overline{s},a)}\right)}\leq
L_{p^{\prime}}d_{\mathcal{S}}(s,\overline{s}).$

For the second integral, we need to compute the Lipschitz semi-norm of
$l_{f}$. Let
$(s,a),(\overline{s},\overline{a})\in\mathcal{S}\times\mathcal{A}$:

$\displaystyle l_{f}(s,a)-l_{f}(\overline{s},\overline{a})$
$\displaystyle=\int_{\mathcal{S}}\left(p^{\prime}(\mathrm{d}s^{\prime}|s,a)-p^{\prime}(\mathrm{d}s^{\prime}|\overline{s},\overline{a})\right)f(s^{\prime})$
$\displaystyle\leq{\mathcal{W}}{\left({p^{\prime}(\cdot|s,a)},{p^{\prime}(\cdot|\overline{s},\overline{a})}\right)}\leq
L_{p^{\prime}}d_{\mathcal{S}\times\mathcal{A}}((s,a),(\overline{s},\overline{a})).$

By plugging this into the second integral we obtain:

$\displaystyle\int_{\mathcal{A}}\left(\pi^{\prime}(\mathrm{d}a|s)-\pi^{\prime}(\mathrm{d}a|\overline{s})\right)l_{f}(s,a)\leq
L_{p^{\prime}}{\mathcal{W}}{\left({\pi^{\prime}(\cdot|s)},{\pi^{\prime}(\cdot|\overline{s})}\right)}\leq
L_{p^{\prime}}L_{\pi^{\prime}}d_{\mathcal{S}}(s,\overline{s}).$

∎

######  Lemma 9.2.

Let $\mathbb{A}_{\pi,p}^{\pi^{\prime},p^{\prime}}$ be the expected coupled
relative advantage function, $\mathbb{A}_{\pi,p}^{\pi^{\prime},p}$ and
$\mathbb{A}_{\pi,p}^{\pi,p^{\prime}}$ be the expected (decoupled) policy and
configuration relative advantage functions respectively. Then, it holds that:

$\displaystyle\left|\mathbb{A}_{\pi,p}^{\pi^{\prime},p^{\prime}}-\left(\mathbb{A}_{\pi,p}^{\pi,p^{\prime}}+\mathbb{A}_{\pi,p}^{\pi^{\prime},p}\right)\right|\leq\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s){\mathcal{W}}{\left({\pi^{\prime}(\cdot|s)},{\pi(\cdot|s)}\right)}\left\|{A_{\pi,p}^{\pi,p^{\prime}}}\right\|_{L}.$

###### Proof.

We can rewrite the expected relative advantage
$\mathbb{A}_{{\pi,p}}^{\pi^{\prime},p^{\prime}}$ using Lemma 5.1:

$\displaystyle\mathbb{A}_{{\pi,p}}^{\pi^{\prime},p^{\prime}}$
$\displaystyle=\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)A_{\pi,p}^{\pi^{\prime},p^{\prime}}(s)$
$\displaystyle=\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)\left(A_{\pi,p}^{\pi^{\prime},p}(s)+\int_{\mathcal{A}}\pi^{\prime}(\mathrm{d}a|s)A_{\pi,p}^{\pi,p^{\prime}}(s,a)\right)$
(19)
$\displaystyle=\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)A_{\pi,p}^{\pi^{\prime},p}(s)+\int_{\mathcal{S}}\int_{\mathcal{A}}\mu_{\pi,p}(\mathrm{d}s)\pi(\mathrm{d}a|s)A_{\pi,p}^{\pi,p^{\prime}}(s,a)$
$\displaystyle\quad+\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)\int_{\mathcal{A}}\left(\pi^{\prime}(\mathrm{d}a|s)-\pi(\mathrm{d}a|s)\right)A_{\pi,p}^{\pi,p^{\prime}}(s,a)$
$\displaystyle=\mathbb{A}_{{\pi,p}}^{\pi^{\prime},p}+\mathbb{A}_{{\pi,p}}^{\pi,p^{\prime}}+\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)\int_{\mathcal{A}}\left(\pi^{\prime}(\mathrm{d}a|s)-\pi(\mathrm{d}a|s)\right)A_{\pi,p}^{\pi,p^{\prime}}(s,a),$
(20)

where line (19) comes from Lemma 5.1. From Equation (20) we can
straightforwardly state the following inequalities:

$\displaystyle\mathbb{A}_{{\pi,p}}^{\pi^{\prime},p^{\prime}}$
$\displaystyle\geq\mathbb{A}_{{\pi,p}}^{\pi^{\prime},p}+\mathbb{A}_{{\pi,p}}^{\pi,p^{\prime}}-\bigg{|}\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)\int_{\mathcal{A}}\left(\pi^{\prime}(\mathrm{d}a|s)-\pi(\mathrm{d}a|s)\right)A_{\pi,p}^{\pi,p^{\prime}}(s,a)\bigg{|},$
$\displaystyle\mathbb{A}_{{\pi,p}}^{\pi^{\prime},p^{\prime}}$
$\displaystyle\leq\mathbb{A}_{{\pi,p}}^{\pi^{\prime},p}+\mathbb{A}_{{\pi,p}}^{\pi,p^{\prime}}+\bigg{|}\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)\int_{\mathcal{A}}\left(\pi^{\prime}(\mathrm{d}a|s)-\pi(\mathrm{d}a|s)\right)A_{\pi,p}^{\pi,p^{\prime}}(s,a)\bigg{|}.$

Then, we bound the absolute value in the right hand side:

$\displaystyle\Big{|}\mathbb{A}_{{\pi,p}}^{\pi^{\prime},p^{\prime}}-\left(\mathbb{A}_{{\pi,p}}^{\pi^{\prime},p}+\mathbb{A}_{{\pi,p}}^{\pi,p^{\prime}}\right)\Big{|}$
$\displaystyle\leq\bigg{|}\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)\int_{\mathcal{A}}\left(\pi^{\prime}(\mathrm{d}a|s)-\pi(\mathrm{d}a|s)\right)A_{\pi,p}^{\pi,p^{\prime}}(s,a)\bigg{|}$
$\displaystyle\leq\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s)\left|\int_{\mathcal{A}}\pi^{\prime}(\mathrm{d}a|s)-\pi(\mathrm{d}a|s)A_{\pi,p}^{\pi,p^{\prime}}(s,a)\right|$
$\displaystyle\leq\int_{\mathcal{S}}\mu_{\pi,p}(\mathrm{d}s){\mathcal{W}}{\left({\pi^{\prime}(\cdot|s)},{\pi(\cdot|s)}\right)}\sup_{s\in\mathcal{S}}\left\|{A_{\pi,p}^{\pi,p^{\prime}}(s,\cdot)}\right\|_{L},$
(21)

where line (21) follows from the definition of Wasserstein distance. The
result is obtained by observing that
$\sup_{s\in\mathcal{S}}\left\|{A_{\pi,p}^{\pi,p^{\prime}}(s,\cdot)}\right\|_{L}\leq\left\|{A_{\pi,p}^{\pi,p^{\prime}}}\right\|_{L}$.
∎

######  Lemma 9.3.

Let $\pi,\pi^{\prime}\in\Delta^{\mathcal{A}}_{\mathcal{S}}$ and
$p,p^{\prime}\in\Delta^{\mathcal{S}}_{\mathcal{S}\times\mathcal{A}}$ be two
policies and configurations for a Conf-MDP. Then, it holds that:

$\displaystyle\left\|{A_{\pi,p}^{\pi^{\prime},p^{\prime}}}\right\|_{L}\leq\left\|{A_{\pi,p}^{\pi^{\prime},p}}\right\|_{L}+(L_{\pi^{\prime}}+1)\left\|A_{\pi,p}^{\pi,p^{\prime}}\right\|_{L}.$

###### Proof.

First of all, we exploit Lemma 5.1 and the fact that
$\left\|{\cdot}\right\|_{L}$ is a semi-norm and, thus, it satisfies the
triangular inequality:

$\displaystyle\left\|{A_{\pi,p}^{\pi^{\prime},p^{\prime}}}\right\|_{L}=\left\|{A_{\pi,p}^{\pi^{\prime},p}+\int_{\mathcal{A}}\pi^{\prime}(\mathrm{d}a|\cdot)A_{\pi,p}^{\pi,p^{\prime}}(\cdot,a)}\right\|_{L}\leq\left\|{A_{\pi,p}^{\pi^{\prime},p}}\right\|_{L}+\left\|{\int_{\mathcal{A}}\pi^{\prime}(\mathrm{d}a|\cdot)A_{\pi,p}^{\pi,p^{\prime}}(\cdot,a)}\right\|_{L}.$

For what concerns the second term, we proceed as follows for
$s,\overline{s}\in\mathcal{S}$:

$\displaystyle\int_{\mathcal{A}}\pi^{\prime}(\mathrm{d}a|s)$ $\displaystyle
A_{\pi,p}^{\pi,p^{\prime}}(s,a)-\int_{\mathcal{A}}\pi^{\prime}(\mathrm{d}a|\overline{s})A_{\pi,p}^{\pi,p^{\prime}}(\overline{s},a)$
$\displaystyle=\int_{\mathcal{A}}\pi^{\prime}(\mathrm{d}a|s)A_{\pi,p}^{\pi,p^{\prime}}(s,a)-\int_{\mathcal{A}}\pi^{\prime}(\mathrm{d}a|\overline{s})A_{\pi,p}^{\pi,p^{\prime}}(\overline{s},a)\pm\int_{\mathcal{A}}\pi^{\prime}(\mathrm{d}a|\overline{s})A_{\pi,p}^{\pi,p^{\prime}}(s,a)$
$\displaystyle=\int_{\mathcal{A}}\left(\pi^{\prime}(\mathrm{d}a|s)-\pi^{\prime}(\mathrm{d}a|\overline{s})\right)A_{\pi,p}^{\pi,p^{\prime}}(s,a)+\int_{\mathcal{A}}\pi^{\prime}(\mathrm{d}a|\overline{s})\left(A_{\pi,p}^{\pi,p^{\prime}}(s,a)-A_{\pi,p}^{\pi,p^{\prime}}(\overline{s},a)\right)$
$\displaystyle\leq\left\|{A_{\pi,p}^{\pi,p^{\prime}}(s,\cdot)}\right\|_{L}{\mathcal{W}}{\left({\pi^{\prime}(\cdot|s)},{\pi(\cdot|s)}\right)}+\int_{\mathcal{A}}\pi^{\prime}(\mathrm{d}a|\overline{s})\left\|{A_{\pi,p}^{\pi,p^{\prime}}(\cdot,a)}\right\|_{L}d_{\mathcal{S}}(s,\overline{s})$
$\displaystyle\leq
L_{\pi^{\prime}}\sup_{s\in\mathcal{S}}\left\|{A_{\pi,p}^{\pi,p^{\prime}}(s,\cdot)}\right\|_{L}d_{\mathcal{S}}(s,\overline{s})+\sup_{a\in\mathcal{A}}\left\|{A_{\pi,p}^{\pi,p^{\prime}}(\cdot,a)}\right\|_{L}d_{\mathcal{S}}(s,\overline{s}).$

Finally, we observe that
$\left\|A_{\pi,p}^{\pi,p^{\prime}}\right\|_{L}\geq\max\left\\{\sup_{a\in\mathcal{A}}\left\|{A_{\pi,p}^{\pi,p^{\prime}}(\cdot,a)}\right\|_{L},\sup_{s\in\mathcal{S}}\left\|{A_{\pi,p}^{\pi,p^{\prime}}(s,\cdot)}\right\|_{L}\right\\}$.
∎