# Performative Reinforcement Learning in Gradually Shifting Environments

Ben Rank Max Planck Institute for Software Systems
Saarbrücken, Germany  Stelios Triantafyllou  Max Planck Institute for Software
Systems
Saarbrücken, Germany  Debmalya Mandal∗† Department of Computer Science
University of Warwick, UK  Goran Radanovic† Max Planck Institute for Software
Systems
Saarbrücken, Germany

###### Abstract

When Reinforcement Learning (RL) agents are deployed in practice, they might
impact their environment and change its dynamics. Ongoing research attempts to
formally model this phenomenon and to analyze learning algorithms in these
models. To this end, we propose a framework where the current environment
depends on the deployed policy as well as its previous dynamics. This is a
generalization of Performative RL (PRL) [Mandal et al., 2023]. Unlike PRL, our
framework allows to model scenarios where the environment gradually adjusts to
a deployed policy. We adapt two algorithms from the performative prediction
literature to our setting and propose a novel algorithm called _Mixed Delayed
Repeated Retraining_ (MDRR). We provide conditions under which these
algorithms converge and compare them using three metrics: number of
retrainings, approximation guarantee, and number of samples per deployment.
Unlike previous approaches, MDRR combines samples from multiple deployments in
its training. This makes MDRR particularly suitable for scenarios where the
environment’s response strongly depends on its previous dynamics, which are
common in practice. We experimentally compare the algorithms using a
simulation-based testbed and our results show that MDRR converges
significantly faster than previous approaches.

$\dagger$$\dagger$footnotetext: Co-supervision.**footnotetext: Work done while
at Max Planck Institute for Software Systems.

###  1 Introduction

When machine learning (ML) models are deployed in practice, they can affect
the prediction target itself, causing a distribution shift. This problem has
received significant attention in supervised learning and is termed as
_performative prediction_ [Perdomo et al., 2020]. In practice, it is often
approached with repeated retraining: a practical solution for finding a
(performatively) stable model, which does not suffer from further distribution
shift.

Recently, Mandal et al. [2023] considered a reinforcement learning (RL)
variant of this problem setting. In RL, performativity manifests itself as a
shift in the environment, depending on the policy which was deployed by the
learner. For example, the environment can model users of an online platform
(e.g., recommender system or a chatbot), who adapt to the changes in the
policy of the RL agent that controls the platform.

Mandal et al. [2023] formalizes this setting with a framework called
_performative RL_ , where the dynamics of a Markov decision process (MDP)
$M_{t}$ depend on the current policy $\pi_{t}$. To find an approximately
stable policy, they propose repeated retraining over the space of occupancy
measures $\mathcal{C}(M_{t})$ and the regularized objective

$\max_{d\in\mathcal{C}(M_{t})}\sum_{s,a}r_{t}(s,a)\cdot
d(s,a)-\lambda\|d\|_{2},$

where $r_{t}$ is the reward function of $M_{t}$, the sum goes over all
possible states $s$ and actions $a$, and $\lambda$ is a regularization factor.

However, this framework assumes that the environment only depends on the
deployed policy and is independent of the previous environment. In many
practical scenarios, this assumption does not hold. Going back to our examples
from before, users are likely to manifest a learning behavior when interacting
with the platform, and thus adapt their behavioral patterns gradually to any
changes made in the platform, instead of adapting immediately after every
change. Thus we consider an extension of the performative RL framework where
the underlying MDP $M_{t}$ is gradually changing over time.

Table 1: Overview of Our Results. Convergence criteria for computing a
$\delta$-approximate stable policy. $\lambda$ is a factor of the
regularization, $\epsilon<1$ indicates the dependence of the current
environment on the previous environment, $\iota<1$ indicates the dependence of
the current environment on the deployed policy, $i$ denotes the current
retraining iteration, $1-p$ is the probability of achieving said approximate
stable policy in the finite sample setting, $k$ denotes the number of repeated
deployments of the same policy in MDRR, $|S|$ is the number of states, $|A|$
the number of actions, and $\gamma$ is the discount factor of the MDP.

Algorithm | $\bm{\lambda}$ | #retrainings | $\genfrac{}{}{0.0pt}{0}{\textbf{\\#samples}}{\textbf{per deployment}}$
---|---|---|---
RR[exact] | ${\mathcal{O}}\left(\frac{|S|^{5/2}}{(1-\epsilon)(1-\gamma)^{4}}\right)$ | $\frac{\ln\left(\left(\frac{2}{1-\gamma}+\left(1+\sqrt{2}\right)\sqrt{|S||A|}\right)/\delta\right)}{\ln\left(2/(1+\epsilon)\right)}$ | N\A
DRR[exact] | ${\mathcal{O}}\left(\frac{\iota\cdot|S|^{5/2}}{(1-\epsilon)(1-\gamma)^{4}}\right)$ | $\ln\left(\left(\frac{2}{1-\gamma}\right)/\delta\right)$ | N\A
RR[fin] | $\mathcal{O}\left(\frac{\epsilon(|S|+\gamma|S|^{5/2})}{(1-\epsilon)(1-\gamma)^{4}}\right)$ | $\frac{\ln\left(\frac{\frac{2}{1-\gamma}+\left(1+\sqrt{2}\right)\sqrt{|S||A|}}{\delta}\right)}{\ln\left(4/\left(3+\epsilon\right)\right)}$ |  $\tilde{{\mathcal{O}}}\left(\frac{|A|\psi}{\lambda^{2}(1-\epsilon)^{4}}\ln\left(\frac{i}{p}\right)\right)$[a]
DRR[fin] | $\mathcal{O}\left(\frac{\iota(|S|+\gamma|S|^{5/2})}{(1-\epsilon)(1-\gamma)^{4}}\right)$ | $\frac{\ln\left(\frac{2}{1-\gamma}/\delta\right)}{\ln\left(4/\left(3+\epsilon\right)\right)}$ |  $\tilde{{\mathcal{O}}}\left(\frac{|A|\psi}{\lambda^{2}}\ln\left(\frac{i}{p}\right)\right)$[a]
MDRR[fin] | as for DRR | as for DRR |  $\frac{(v-1)v^{k-1}}{v^{k}-1}\tilde{{\mathcal{O}}}\left(\frac{|A|\psi}{\lambda^{2}}\ln\left(\frac{i}{p}\right)\right)$[a,b]

  * [a]

Here
$\psi={\mathcal{O}}\left(\frac{|S|^{3}\left(B+\sqrt{|A|}\right)^{2}}{\delta^{4}(1-\gamma)^{6}}\right)$
and we ignore all terms which are logarithmic in $|S|$, $|A|$ and $1/\delta$.

  * [b]

$v>\frac{1}{\epsilon}$ is a hyperparamter of MDRR

  * [exact]

results when the learner knows current environment $(P_{t},r_{t})$

  * [fin]

results when the learner gets a finite set of samples from the current
environment $(P_{t},r_{t})$

##### Contributions

Following a similar line of work on performative prediction that considers
gradual shifts in the distribution [Brown et al., 2022, Li and Wai, 2022, Ray
et al., 2022, Izzo et al., 2022], we model this scenario by assuming that the
underlying MDP $M_{t}$ is dependent on both the deployed policy $\pi_{t}$ and
the MDP from the previous round, i.e., $M_{t-1}$. Our overall goal is to
analyze different repeated retraining approaches and provide characterization
results that compare these approaches along the following three measures: a)
attainable approximation quality (i.e., the minimum value of $\lambda$ for
which the convergence is guaranteed), b) the number of retrainings which
guarantees the convergence (signifying the the compute needed to converge),
and c) the sample complexity per deployment (signifying the number of data
points that need to be collected). Our main contributions are as follows:

  * •

_Framework:_ An extension of the performative RL framework that can model
gradual environment shifts, and an extension of the DRR algorithm from Brown
et al. [2022], suitable for our framework.

  * •

_Algorithm:_ A novel repeated retraining algorithm, called MDRR, which
compared to repeated retraining (RR) and DRR uses samples from multiple rounds
of deployment, thereby reducing the number of samples needed per round.

  * •

_Characterization results:_ A characterization of three repeated retraining
approaches: a canonical RR, DRR, and MDRR. Our analysis is a non-trivial
combination of the proof techniques used by Mandal et al. [2023] and Brown et
al. [2022] and brings additional insights about regularization in performative
RL. The overview of the results can be found in Table 1. At a high-level, our
theoretical results suggest that DRR and MDRR fare better than RR in terms of
the number of retrainings and sample complexity, as well as in terms of
attainable approximation quality when the environment depends weakly on the
current policy. When the environment depends strongly on the previous
environment, MDRR fares better than RR and DRR in terms of samples per round.
These results shed light on regularization in performative RL, and the
importance of utilizing historic data to reduce it, thus obtaining better
approximation quality.

  * •

_Experiments:_ Finally, we compare the algorithms in an experimental
evaluation. In our experiments, MDRR outperforms RR and DRR in terms of the
convergence speed and the quality of the solution obtained.

####  1.1 Related Work

We relate our work to four lines of research: Performative Prediction, Markov
Games, Adversarial Markov Decision Processes, and Reinforcement Learning. The
latter two are discussed in Appendix A.

Performative Prediction.  The study of performative prediction was initiated
by Perdomo et al. [2020]. They investigate conditions under which repeated
retraining converges to a performatively stable point. This study was extended
in various ways, including stochastic optimization [Mendler-Dünner et al.,
2020], finding performatively optimal points [Miller et al., 2021, Izzo et
al., 2021], multi-agent scenarios [Narang et al., 2023, Li et al., 2022] and
using performativity to measure the power of firms [Hardt et al., 2022].
Mofakhami et al. [2023] use a different set of assumptions and provide
convergence guarantees also in cases where the loss is not strongly convex in
the parameters of the model. Most related to our setting are works that
consider performative prediction under gradual shifts in the distribution
[Brown et al., 2022, Li and Wai, 2022, Ray et al., 2022, Izzo et al., 2022],
commonly known as _stateful_ performative prediction [Brown et al., 2022]. All
of the above works study performativity in supervised learning. In contrast,
we consider reinforcement learning. However, we emphasize that some of our
results are extensions of or inspired by those that appear in [Brown et al.,
2022]. Most notably, we extend delayed repeated retraining, an algorithm
proposed by [Brown et al., 2022], to our RL setting, and analyze its
convergence guarantees. Furthermore, we introduce a novel algorithm inspired
by delayed repeated retraining.

Markov Games. Our work is also related to the literature on stochastic or
Markov games [Shapley, 1953] and multi-agent reinforcement learning [Zhang et
al., 2021]. Much of the focus in multi-agent RL have been on computational and
statistical aspects of learning Nash or correlated equilibria [Daskalakis et
al., 2023, Wei et al., 2017, Bai et al., 2020, Jin et al., 2022]. Our setting
is more related to multi-agent RL frameworks that consider Stackelberg or
commitment policies [Letchford et al., 2012, Vorobeychik and Singh, 2012,
Dimitrakakis et al., 2017, Zhong et al., 2021], where a principal agent
commits a policy to which one or more followers best responds. Computing
optimal commitment policies is in general computationally intractable
Letchford et al. [2012]. Hence, some restrictions on followers’ response
models are needed to enable computationally efficient learnability Zhong et
al. [2021]. Similarly, no-regret learning in a two-agent principal-follower
setting where the follower independently learns or changes its policy over
time is also in general computationally intractable [Radanovic et al., 2019,
Bai et al., 2020]. However, if the dynamics of the follower’s policy updates
is not adversarial, tractable no-regret algorithms exist [Radanovic et al.,
2019]. These restrictions on the follower are similar in spirit to the setting
and the assumptions we consider in this paper, however, our setting is
technically quite different: whereas these works focus on no-regret learning,
we focus on performative RL and repeated retraining approaches.

###  2 Preliminaries

We follow Perdomo et al. [2020], Brown et al. [2022] and Mandal et al. [2023]
in defining the formal setting.

##### Markov Decision Processes

We consider tabular Markov Decision Processes (MDPs), which consist of a
finite state space $S$, finite action space $A$, discount factor $\gamma$ and
initial state distribution $\rho$. We assume that the reward and transition
probability functions change over time, as a response to the policy which the
learner deploys. The learner deploys policy $\pi_{t}$ in round $t$ and the
previous probability transition and reward function are $P_{t-1}$ and
$r_{t-1}$. They then change to to $P_{t}=\mathcal{P}(\pi_{t},P_{t-1},r_{t-1})$
and $r_{t}=\mathcal{R}(\pi_{t},P_{t-1},r_{t-1})$ respectively, according to
the _response models_ $\mathcal{P}$ and $\mathcal{R}$. Thus, the MDP in round
$t$ is $M_{t}=(S,A,P_{t},r_{t},\rho)$.

When the learner deploys policy $\pi_{t+1}$, the probability of a trajectory
$\tau=(s_{k},a_{k})_{k=0}^{\infty}$ to be realized in round $t$ is given by
$\mathbb{P}_{t}^{\pi_{t+1}}(\tau)=\rho(s_{0})\prod_{k=1}^{\infty}\pi_{t+1}(a_{k}|s_{k})P_{t}(s_{k},a_{k},s_{k+1})$.

Given policy $\pi$ and initial state distribution $\rho$, we denote the value
function at round $t$ as $V_{t}^{\pi}(\rho)$. It is defined as

$V_{t}^{\pi}(\rho)=\mathbb{E}_{\tau\sim\mathbb{P}_{t}^{\pi}}\left[\sum_{k=0}^{\infty}\gamma^{k}r_{t}(s_{k},a_{k})|\rho\right].$

The learner in round $t$ has access to the past MDPs $M_{0},\dots,M_{t-1}$, or
a finite number of samples thereof.

##### Solution Concept

We assume that when the learner deploys $\pi$ in every round, the MDP
converges to the _limiting MDP_ $M_{\pi}=(S,A,P_{\pi},r_{\pi},\rho)$, which is
independent of the initial MDP. Using this, we can define the _performative
value function_ as

$V_{\pi^{\prime}}^{\pi}(\rho)=\lim_{t\rightarrow\infty}V_{t}^{\pi}(\rho|\pi_{i}=\pi^{\prime}\
\forall i)\ .$

It is the value function of MDP $M_{\pi}$.

On common solution concept in this setting is to find a _performatively stable
policy_ , defined as follows.

######  Definition 1 (Performatively Stable Policy).

We call a policy $\pi$ _performatively stable_ , if it is the best response to
the MDP $M_{\pi}$. That is,
$\pi\in\operatorname*{arg\,max}_{\pi^{\prime}}V_{\pi}^{\pi^{\prime}}$.

Given two performatively stable policices $\pi_{1}$ and $\pi_{2}$, their
convex combination might not be performatively stable. Because of this, it is
hard to use the standard formulation of RL. This problem is alleviated by
using the linear programming formulation of RL. To describe this, we define
the long term-state occupancy measure of a policy $\pi$ in MDP $M_{t}$ as
$d_{t}^{\pi}(s,a)=\mathbb{E}_{\tau\sim\mathbb{P}_{t}^{\pi}}\left[\sum_{k=0}^{\infty}\gamma^{k}\mathds{1}\\{s_{k}=s,a_{k}=a\\}\right]$.
When given occupancy measure $d$, one can consider the following policy
$\pi^{d}$, which has occupancy measure $d$.

$\displaystyle\pi^{d}(a|s)=\left\\{\begin{array}[]{cc}\frac{d(s,a)}{\sum_{b}d(s,b)}&\textrm{
if }\sum_{a}d(s,a)>0\\\ \frac{1}{|A|}&\textrm{ otherwise }\end{array}\right.$
(3)

We consider that the learner parameterizes its policy by the occupancy measure
and calculates the policy via (3).

In an unregularized setting, we would say that a occupancy measure $d_{S}$ is
performatively stable if it is the optimal solution to the following linear
program.

$\displaystyle d_{S}^{*}\in\operatorname*{arg\,max}_{d\geq
0}\sum_{s,a}d(s,a)r_{d_{S}^{*}}(s,a)$ (4) s.t.
$\displaystyle\sum_{a}d(s,a)=\rho(s)+\gamma\cdot\sum_{s^{\prime},a}d(s^{\prime},a)P_{d_{S}^{*}}(s^{\prime},a,s)\
\forall s$

where we denote $P_{d}=P_{\pi_{d}}$ and $r_{d}=r_{\pi_{d}}$ . This describes
an occupancy measure which is itself the best response against the current
MDP.

But, similar to prior work, to make the theoretical analysis feasible, we
assume the following regularized version of optimization problem (4). A stable
occupancy measure $d_{S}$ is defined by

$\displaystyle d_{S}\in\operatorname*{arg\,max}_{d\geq 0}\
\sum_{s,a}d(s,a)r_{d}(s,a)-\frac{\lambda}{2}\left\lVert d\right\rVert_{2}^{2}$
(5) s.t.
$\displaystyle\sum_{a}d(s,a)=\rho(s)+\gamma\cdot\sum_{s^{\prime},a}d(s^{\prime},a)P_{d}(s^{\prime},a,s)\
\forall s.$

Here $\lambda$ is a constant regularization factor which describes the strong-
concavity of the objective. This describes an occupancy measure which is
itself the best response against a regularized objective of the current MDP.
If a learner updates their occupancy measure using the best response against a
$L2$-regularized objective, (5) describes an occupancy measure which would not
change under such an update, i.e. be stable.

In our results, we provide lower bounds for how small $\lambda$ can be to
guarantee convergence. Furthermore, in Appendix C.2 we show that (5)
approximates the unregularized objective (4).

##### Sensitivity Assumption

We overload the notation to write the response models in the following form.
For every occupancy measure $d$, let
$\mathcal{P}(d,P,r)=\mathcal{P}(\pi_{d},P,r)$ and
$\mathcal{R}(d,P,r)=\mathcal{R}(\pi_{d},P,r)$.

For the learner to make use of this past information, we use the following
sensitivity assumption, which are commonly used in performative prediction.

######  Assumption 1 (sensitivity).

Consider some
$\iota_{p},\iota_{r},\epsilon_{p,p},\epsilon_{p,r},\epsilon_{r,p},\epsilon_{r,r}\geq
0$ with $\iota=\iota_{p}+\iota_{r}<1$,
$\epsilon_{p}=\epsilon_{p,p}+\epsilon_{r,p}<1$ and
$\epsilon_{r}=\epsilon_{p,r}+\epsilon_{r,r}<1$. Assume

$\displaystyle\|\mathcal{P}(d,P,r)-\mathcal{P}(d^{\prime},P^{\prime},r^{\prime})\|_{2}$
$\displaystyle\leq\iota_{p}\|d-d^{\prime}\|_{2}+\epsilon_{p,p}\|P-P^{\prime}\|_{2}+\epsilon_{p,r}\|r-r^{\prime}\|_{2}\text{
and}$
$\displaystyle\|\mathcal{R}(d,P,r)-\mathcal{R}(d^{\prime},P^{\prime},r^{\prime})\|_{2}$
$\displaystyle\leq\iota_{r}\|d-d^{\prime}\|_{2}+\epsilon_{r,p}\|P-P^{\prime}\|_{2}+\epsilon_{r,r}\|r-r^{\prime}\|_{2}$

for any occupancy measures $d,d^{\prime}$, reward functions $r,r^{\prime}$ and
probability transition functions $P,P^{\prime}$.

Assumption 1 ensures that when the learner deploys a new policy, the new MDP
does not drift too far from the old MDP.

When $\epsilon_{p},\epsilon_{r}<1$, the mapping from $(P,r)$ to
$(\mathcal{P}(d,P,r),\mathcal{R}(d,P,r))$ is a contraction for any occupancy
measure $d$ (Proof in Appendix C.3). Therefore, if the learner deploys the
same policy $\pi$ in every round, $P_{t}$ and $r_{t}$ asymptotically converge
to some $P_{\pi}$ and $r_{\pi}$ respectively and we don’t need to assume this
explicitly.

To simplify the exposition of the results in the main paper, we assume that
the following assumption holds, without explicitly stating it in the results.

######  Assumption 2.

For the results in the main part of the paper, we assume that
$\epsilon_{p,p}=\epsilon_{p,r}=\epsilon_{r,p}=\epsilon_{r,r}=\frac{\epsilon}{2}$,
$\iota_{p},\iota_{r}\leq\frac{\epsilon}{2}$ for some $\epsilon<1$ and
$\frac{9\gamma|S|}{(1-\gamma)^{2}}\geq 1$ .

Assumption 2 is not critical – as we show in the appendix, our results easily
generalize when we do not assume it.

##### Sample Generation Model

We also consider finite-sample versions of the algorithms we propose. For this
we use the following sample generation model. In round $t$, let
$\overline{d}_{t}$ be the occupancy measure of $\pi_{t}$ under dynamics
$P_{t}$. Note that this is different than the occupancy measure which the
learner uses to calculate its policy $\pi_{d_{t}}$, since this was calculated
using different dynamics. We then define the normalized occupancy measure
$\tilde{d}_{t}(s,a)=(1-\gamma)\overline{d}_{t}(s,a)$. Each sample in round $t$
is a tuple $(s,a,r,s^{\prime})$ and is generated in the following way. First a
state, action pair is sampled i.i.d. according to $(s,a)\sim\tilde{d}_{t}$,
then reward as $r=r_{t}(s,a)$ and then the next state $s^{\prime}\sim
P_{t}(\cdot|s,a)$. This is a standard model of sample generation in offline RL
[Munos and Szepesvári, 2008, Farahmand et al., 2010, Xie and Jiang, 2021,
Mandal et al., 2023].

###  3 Repeated Retraining (RR)

One common approach in performative prediction is _repeated retraining (RR)_ ,
where the learner updates its policy at every round, by best responding to the
current environment. In this section, we explore guarantees for when this
approach converges to a stable occupancy measure.

In RR we assume that the learner updates its policy every round in such a way
that it is optimal for the regularized objective of the current MDP $M_{t}$.
In particular, we define $d_{t+1}$ to be a solution to the following
optimization problem.

$\displaystyle\max_{d\geq 0}$ $\displaystyle\
\sum_{s,a}d(s,a)r_{t}(s,a)-\frac{\lambda}{2}\left\lVert d\right\rVert_{2}^{2}$
(6) s.t.
$\displaystyle\sum_{a}d(s,a)=\rho(s)+\gamma\cdot\sum_{s^{\prime},a}d(s^{\prime},a)P_{t}(s^{\prime},a,s)\
\forall s$

We go on to show that RR converges to a stable occupancy measure.

######  Theorem 1 (informal, details in Appendix D.2).

Assume that Assumption 1 holds and
$\lambda={\mathcal{O}}\left(\frac{|S|^{5/2}}{(1-\epsilon)(1-\gamma)^{4}}\right)$.
Then for any $\delta>0$ we have,

$\left\lVert d_{t}-d_{S}\right\rVert_{2}\leq\delta,$

for all
$t\geq\frac{\ln\left(\left(\frac{2}{1-\gamma}+\left(1+\sqrt{2}\right)\sqrt{|S||A|}\right)/\delta\right)}{\ln\left(2/\left(1+\epsilon\right)\right)}\
.$

The bound on $\lambda$ in Theorem 1 is comparable to the one required in
standard Performative RL, there are only differences in the constants and the
$\epsilon$ factors. The bound on the number of rounds $t$ in standard
Performative RL is
$2\ln\left(\frac{2}{\delta(1-\gamma)}\right)/\left(1-\frac{|S|^{5/2}\epsilon}{\lambda(1-\gamma)^{4}}\right)$,
which is comparable to the bound here, when only considering the $\delta$
parameter. We note that the bound on $t$ in Theorem 1 does depend on
$\lambda$, but for the simplicity of the exposition it is swapped by the lower
bound on $\lambda$ instead. The full theorem is found in Appendix D.2.

The proofs of this paper are found in the appendix. In general, the proofs
rely on a non-trivial combination of adapting arguments from Brown et al.
[2022] to the RL setting and using results from Mandal et al. [2023].
Additionally, we extend the analysis by introducing a distinction between the
parameter $\iota$ indicating how the environment adapts to a deployed policy,
and $\epsilon$ indicating how strongly the environment depends on the previous
environment. We therefore view our main contribution in this section and
Section 4 as bridging the gap between the theoretical findings of Mandal et
al. [2023] and the often more realistic assumptions made by history-
dependence, as in Brown et al. [2022]. In section 5 we will introduce a novel
algorithm.

####  3.1 Finite Sample Guarantees

Theorem 1 assumes that the learner knows the exact environment when updating
its policy. In practice, this is usually too strong of an assumption, since
the learner typically has access to only a finite number of samples drawn via
the deployed policy on the adopted environment. In this subsection, we first
discuss some general considerations for this new setting and then show that RR
also converges here.

##### Update rule for RR

The learner has access to i.i.d. drawn set of samples $F_{t}$ for each round
$t$. In round $t$, let $m_{t}:=\left|F_{t}\right|$ be the number of samples.

As prior work, we use the following _empirical Lagrangian_ to devise an
optimization problem in the finite sample setting [Mandal et al., 2023].

$\displaystyle\begin{split}\hat{{\mathcal{L}}}(d,h;t)=-\frac{\lambda}{2}\left\lVert
d\right\rVert_{2}^{2}+\sum_{s}h(s)\rho(s)\\\ +\sum_{(s,a,r,s^{\prime})\in
F_{t}}\frac{d(s,a)}{\overline{d}_{t}(s,a)}\cdot\frac{r-h(s)+\gamma
h(s^{\prime})}{m_{t}(1-\gamma)}\end{split}$ (7)

The empirical Lagrangian is defined in such a way that when we take its
expectation over samples, we obtain the exact Lagrangian ${\mathcal{L}}$ of
optimization (6). One can show that the empirical Lagrangian
$\hat{{\mathcal{L}}}$ lies in a neighborhood of the true Lagrangian
${\mathcal{L}}$ almost certainly. The learner repeatedly solves

$\displaystyle(d_{t+1},h_{t+1})=\operatorname*{arg\,max}_{d}\
\operatorname*{arg\,min}_{h}\hat{{\mathcal{L}}}(d,h;t)\ .$ (8)

We need a further assumption, which ensures an overlap in the occupancy
measure between the behavioral policy and the target policy space. This
assumption is standard in offline RL [Munos and Szepesvári, 2008, Zhan et al.,
2022, Mandal et al., 2023]. Without such an overlap, it is unclear how the
learner would compute an optimal policy.

######  Assumption 3.

Assume we are given an integer $k$. Given occupancy measure $d$, initial
transition probability function $P_{0}$ and initial reward function $r_{0}$,
let $P_{t}$ and $r_{t}$ be the result after the learner deploys $\pi_{d}$ for
$t$ rounds. Let $d_{t}^{*}$ be the solution to optimization problem (6). Let
$\overline{d}_{t}$ be the occupancy measure of $\pi^{d}$ in $P_{t}$. Then
there exists $B>0$ such that for all $d$ and $t\leq k$ it holds that

$\max_{s,a}\left|\frac{d_{k}^{*}(s,a)}{\overline{d}_{t}(s,a)}\right|\leq B\ .$

Note that we only need overlap for state-action pairs where the optimal policy
$d^{*}_{t}$ is non-zero. So values where $d_{k}^{*}(s,a)$ is $0$ are allowed
iff $\overline{d}_{t}(s,a)$ is $0$ for all $t\leq k$.

We can then show the following guarantee for RR.

######  Theorem 2 (informal, details in Appendix D.3).

Suppose that overlap Assumption 3 holds for $k=1$ with parameter $B$ and
Assumption 1 holds. Let $p>0$. Then for
$\lambda=\mathcal{O}\left(\frac{\epsilon(|S|+\gamma|S|^{5/2})}{(1-\epsilon)(1-\gamma)^{4}}\right)$,
$m_{t}=\tilde{{\mathcal{O}}}\left(\frac{|A||S|^{3}\left(B+\sqrt{|A|}\right)^{2}}{\delta^{4}(1-\gamma)^{6}\lambda^{2}(1-\epsilon)^{4}}\ln\left(\frac{t}{p}\right)\right)$111Here
we ignore all terms which are logarithmic in $|S|$, $|A|$ and $1/\delta$ and
for any $\delta>0$, with probability at least $1-p$,

$\left\lVert d_{t}-d_{S}\right\rVert_{2}\leq\delta\text{\ \ for all
}t\geq\frac{\ln\left(\frac{\frac{2}{1-\gamma}+\left(1+\sqrt{2}\right)\sqrt{|S||A|}}{\delta}\right)}{\ln\left(4/\left(3+\epsilon\right)\right)}+1\
.$

The bounds here are similar to the bounds in standard Performative RL. For
$\lambda$, there is no $\gamma$ in the numerator and the $\epsilon$ parameters
are a bit different in the standard setting. The number of retrainings also
has a factor of $\ln(1/((1-\gamma)\delta))$ in standard Performative RL.

###  4 Delayed Repeated Retraining

A different approach inspired by work from Brown et al. [2022], is to not
update the policy every round, but wait a number of $k$ rounds before each
update. Then the policy is updated using only the environment from the last
round of the $k$ deployments. Algorithm 1 illustrates this approach, called
_Delayed Repeated Retraining_ (DRR).

The advantage of DRR is that during the rounds of repeatedly deploying the
same policy, the MDP can somewhat stabilize and the learner might need a lower
amount of retrainings and therefore less compute.

For the result, we use the following definition.

######  Definition 2.

Let $\operatorname{d}_{P,r}$ be the maximal distance between any environment
and its successive environment, i.e.

$\operatorname{d}_{P,r}:=\max_{P,r,d}\left(\|\mathcal{P}(P,r,d)-P\|_{2}+\|\mathcal{R}(P,r,d)-r\|_{2}\right).$

######  Theorem 3 (informal, details in Appendix E.1).

Let $d_{i}$ be computed by DRR with
$k=\ln^{-1}\left(\frac{1}{\epsilon}\right)\ln\left(\frac{\operatorname{d}_{P,r}}{\delta\iota}\right)$.
Suppose Assumption 1 holds and
$\lambda={\mathcal{O}}\left(\frac{\iota\cdot|S|^{5/2}}{(1-\epsilon)(1-\gamma)^{4}}\right)$.
Then for any $\delta>0$, we have

$\left\lVert d_{i}-d_{S}\right\rVert_{2}\leq\delta\text{\quad for all
}i\geq\ln\left(\left(\frac{2}{1-\gamma}\right)/\delta\right)\ .$

The regularization parameter $\lambda$ has an $\iota$ factor in DRR, but not
in RR (see Theorem 1). The factor $\iota$ is close to $0$, if the MDP does not
react strongly to the current policy. In such settings, the conditions for
$\lambda$ in DRR are substantially relaxed. In addition, the number of
retrainings required for DRR is much smaller than for RR. However, RR may
require fewer total rounds than DRR.

1: Input: radius $\delta$, initial transition probability $P_{0}$ and reward
function $r_{0}$, initial occupancy measure ${d_{0}}$, number of deployments
$k$

2: for $i=0,1,2,\dots$ do

3: for $t=1,\dots,k$ do

4: // deploy $\pi_{d_{i}}$:

5: $P_{i\cdot k+t}\leftarrow\mathcal{P}(d_{i},P_{i\cdot k+t-1},r_{i\cdot
k+t-1})$

6: $r_{i\cdot k+t}\leftarrow\mathcal{R}(d_{i},P_{i\cdot k+t-1},r_{i\cdot
k+t-1})$

7: Update policy to $\pi_{d_{i+1}}$

Algorithm 1 Delayed Repeated Retraining

####  4.1 Finite Sample Guarantees

In DRR with finite samples, the learner again applies the same policy for
several rounds. After that it updates its policy using samples drawn from the
most recent environment. For this, the learner uses optimization problem (8).

######  Theorem 4 (informal, details in Appendix E.2).

Let $d_{i}$ be computed by finite sample DRR with
$k=\ln^{-1}\left(\frac{1}{\epsilon}\right)\ln\left(\frac{5\cdot\operatorname{d}_{P,r}}{\delta\iota}\right)$.
Suppose the Assumption 1 holds and Assumption 3 holds for $k$ and parameter
$B$. Let $p>0$. Furthermore assume
$\lambda=\mathcal{O}\left(\frac{\iota(|S|+\gamma|S|^{5/2})}{(1-\epsilon)(1-\gamma)^{4}}\right)$.
Then for
$m_{i}=\tilde{{\mathcal{O}}}\left(\frac{|A||S|^{3}\left(B+\sqrt{|A|}\right)^{2}}{\delta^{4}(1-\gamma)^{6}\lambda^{2}}\ln\left(\frac{i+1}{p}\right)\right)$1,
and any $\delta>0$, with probability at least $1-p$,

$\left\lVert d_{i}-d_{S}\right\rVert_{2}\leq\delta\quad\text{\quad for all
}i\geq\frac{\ln\left(\frac{2}{1-\gamma}/\delta\right)}{\ln\left(4/\left(3+\epsilon\right)\right)}+1.$

In this result, $\lambda$ has a factor of $\iota$, whereas RR has a factor of
$\epsilon$ (see Theorem 2). In prior work, the difference of $\epsilon$ and
$\iota$ was ignored and the two were assumed to be the same [Brown et al.,
2022]. As we see here however, interesting properties emerge when we
explicitly assume that they are not the same. In settings where the
environment does not respond strongly to the current policy, but strongly
depends on the previous environment, $\epsilon$ is larger than $\iota$,
substantially relaxing the conditions on $\lambda$ for DRR. DRR also requires
less samples, by a factor of $(1-\epsilon)^{4}$ when assuming equal $\lambda$.
The number of retrainings also is less for DRR. Still, RR may need fewer
rounds of retraining overall because DRR only retrains every $k$th round.
Assumption 3 is stricter for DRR, because it has a larger $k$-parameter than
RR. The $k$ parameter in Assumption 3 indicates how far into future rounds the
overlap of occupany measures has to reach.

###  5 Mixed Delayed Repeated Retraining (MDRR)

Consider a scenario where in each round the learner gets a limited number of
samples from the MDP. In this scenario, in each training step DRR would use
samples from one round only. But using samples from multiple rounds would
allow the learner to use more samples overall, reducing variance and
potentially improving convergence.

However, it is challenging to determine how the learner should combine samples
from multiple rounds. Should they optimize using all available samples
collectively, or should they use more samples from recent rounds and less from
older ones? Additionally, it is uncertain whether such a method would converge
and, if so, whether it would offer any benefits. To address these questions,
we present a novel algorithm that:

  * •

Uses samples from multiple rounds.

  * •

Allows for prioritizing recent samples while still incorporating older ones.

  * •

If the response of the environment depends strongly on the previous MDP,
achieves convergence with fewer samples per round. If additionally the number
of provided samples per deployment is low, it provides better approximation
guarantees.

The algorithm uses a new optimization problem, which can be viewed as an
extension of the previous empirical Lagrangian (7) to multiple rounds:

$\displaystyle\begin{split}&\hat{{\mathcal{L}}}^{M}(d,h,i)=-\frac{\lambda}{2}\left\lVert
d\right\rVert_{2}^{2}+\sum_{s}h(s)\rho(s)\\\
&+\sum_{t=1}^{k}\sum_{\genfrac{}{}{0.0pt}{}{(s,a,r,s^{\prime})}{\in F_{i\cdot
k+t}}}\frac{1}{U_{i}}\frac{d(s,a)}{\overline{d}_{i\cdot
k+t}(s,a)}\frac{r-h(s)+\gamma h(s^{\prime})}{1-\gamma}\end{split}$ (9)

Here we define by $\overline{d}_{i\cdot k+t}$ the occupancy measure of policy
$\pi_{d_{i}}$ under dynamics $P_{i\cdot k+t}$. $U_{i}$ denotes the total
number of samples, i.e. $U_{i}:=\sum_{t=1}^{k}\left|F_{i\cdot k+t}\right|$.
The learner thus optimizes over samples from multiple rounds of deployment.

But there is an inherent trade-off: recent samples contain more information
about the current environment, but using earlier samples allows the total set
of samples to be larger.

To balance this trade-off, the approach here is to use more samples from
recent rounds and less samples from early rounds. For illustration, let’s
assume that the learner didn’t update its policy since MDP $M_{i\cdot
k}=(S,A,P_{i\cdot k},r_{i\cdot k},\rho)$ and updates every $k$ rounds. Then
they might take $m$ samples from $M_{i\cdot k+1}$, $mv$ samples from
$M_{i\cdot k+2}$ (for $v>1$), $mv^{2}$ samples from $M_{i\cdot k+3}$, …, and
$mv^{k-1}$ samples from $M_{i\cdot k+k}$. If $v$ is close to $1$, the learner
takes approximately equal number of samples from all rounds. If $v$ is large,
and $m$ small, the learner focuses more on recent rounds. The pseudocode for
this approach is shown in Algorithm 2, we call it _Mixed Delayed Repeated
Retraining_ (MDRR).

1: Input: radius $\delta$, initial $P_{0}$ and $r_{0}$, initial occupancy
measure ${d_{0}}$, hyperparameters $v$ and $k$, total number of samples for
each round $U_{i}$

2: for $i=0,1,2,\dots$ do

3: for t = $1,\dots,k$ do

4: $P_{i\cdot k+t}\leftarrow\mathcal{P}(d_{i},P_{i\cdot k+t-1},r_{i\cdot
k+t-1})$

5: $r_{i\cdot k+t}\leftarrow\mathcal{R}(d_{i},P_{i\cdot k+t-1},r_{i\cdot
k+t-1})$

6: $F_{i\cdot k+t}\leftarrow$ draw $\frac{v-1}{v^{k}-1}v^{t-1}U_{i}$ samples
from $(P_{i\cdot k+t},r_{i\cdot k+t})$

7: Update occupancy measure
$d_{i+1}\leftarrow\operatorname{arg}\max_{d}\min_{h}\hat{{\mathcal{L}}}^{M}(d,h,i)$

Algorithm 2 Mixed DRR (MDRR)

In MDRR the learner uses $m_{i\cdot k+t}=\frac{v-1}{v^{k}-1}v^{t-1}U_{i}$
samples from environment $(P_{i\cdot k+t},r_{i\cdot k+t})$ (for each
$t=1,\dots,k$), where $U_{i}$ denotes the total number of samples used to
compute $d_{i+1}$.

######  Theorem 5 (informal, details in Appendix F.2).

Let $d_{i}$ be computed by MDRR with
$k\geq\frac{\ln\left(\frac{\epsilon(v-1)}{v\epsilon-1}\right)+\ln\left(\frac{5(1-\epsilon)\operatorname{d}_{P,r}}{\iota\delta}\right)}{\ln\left(1/\epsilon\right)}$.
Suppose the Assumption 1 holds and the overlap Assumption 3 holds for $k$ and
parameter $B$. Let $p>0$. Also assume that
$\lambda=\mathcal{O}\left(\frac{\iota(|S|+\gamma|S|^{5/2})}{(1-\epsilon)(1-\gamma)^{4}}\right)$.
Further let
$U_{i}=\tilde{{\mathcal{O}}}\left(\frac{|A||S|^{3}\left(B+\sqrt{|A|}\right)^{2}}{\delta^{4}(1-\gamma)^{6}\lambda^{2}}\ln\left(\frac{i+1}{p}\right)\right)$1
be the total number of samples in retraining-round $i$ and
$v>\frac{1}{\epsilon}$. Then for any $\delta>0$, with probability at least
$1-p$,

$\left\lVert d_{i}-d_{S}\right\rVert_{2}\leq\delta\text{\quad for all
}i\geq\frac{\ln\left(\frac{2}{1-\gamma}/\delta\right)}{\ln\left(4/\left(3+\epsilon\right)\right)}+1\
.$

The proof of this result involves showing that the empirical Lagrangian (9)
approximates an exact Lagrangian of the optimization problem where the MDP is
a mixture of MDPs from different rounds. We then show that the solution to
this optimization problem approximates the solution of an exact one-step
update with the limiting MDP (i.e. the MDP which the environment converges to
if the learner repeatedly applies the current policy). In a last step we apply
arguments similar to the proof of convergence for DRR.

To compare MDRR to RR and DRR, let’s first consider the case when $\epsilon$
is close to $1$. This holds when the environment responds strongly to the old
environment, for example when the new environment after one step is a slight
alteration of the old environment. We expect this property to hold in many
applications, because the environment shift typically happens only slowly over
time. We anticipate that MDRR performs particularly well in those settings,
because it uses samples from old environments, and if those environments are
close to the current environment, those samples are more informative. And
indeed, this is what we observe. The number of samples required in line 6 of
MDRR is smaller by a factor of $\frac{v^{k}-v^{k-1}}{v^{k}-1}$, which
converges to $(v-1)/v$ for large $k$. When $\epsilon$ is close to $1$, we can
set $v$ close to $1$, resulting in a significant decrease in the required
number of samples.

(a) Here $w=0.5$

(b) Here $w=0.15$

(c) MDRR with $v=1.1$

(d) MDRR with $k=5$

Figure 1:  The figures show the distance of the current occupancy measure from
the average of the last 10 in that run (after 11990 deployments). The data
represent means computed over 20 trials, along with their 95% confidence
intervals. Unless otherwise noted, the settings are $k=3$ for DRR and MDRR,
$v=1.1$ for MDRR, 1000 trajectories per iteration, $B=10$, $\lambda=0.1$ and
$w=0.5$ Figure 1(a) and 1(b) compare the three algorithms to one another,
while Figure 1(c) compares MDRR with different values for the hyperparameter
$k$ and Figure 1(d) compares MDRR with different values for the hyperparameter
$v$.

The regularization parameter $\lambda$ is the same as for DRR and has a factor
of $\iota$ compared to RR which has a factor of $\epsilon$. But note that the
number of samples has a factor of $1/\lambda^{2}$ in all three algorithms,
therefore in settings where there are few samples, one needs larger $\lambda$
to guarantee convergence. However, because MDRR requires less samples per
round than RR and DRR in those settings, it requires smaller values of
$\lambda$. The number of retrainings is similar to DRR and significantly less
than for RR.

In general, we see that MDRR performs particularly well in settings where the
environment responds strongly to the previous environment in a given round,
which likely is a scenario often present in practice.

###  6 Experiments

##### Environment

In order to compare the three algorithms in a fair and tractable experimental
setup, we use a variation of the experimental testbed from Mandal et al.
[2023], with two agents controlling an actor in a grid-world. In our testbed,
agent $A_{1}$ proposes a control policy for the actor and $A_{2}$ responds by
overriding some of the actions taken by the control policy. Hence, $A_{1}$’s
effective environment is performative. More information about this
experimental setup can be found Appendix B.1.

To simulate a slow response, $A_{2}$ plays a weighted combination of its last
policy and a softmax of its optimal $Q$-values. Specifically, the policy of
$A_{2}$ in round $i$ is

$\pi_{i}^{2}(a|s)=w\cdot\frac{e^{Q_{2}^{*|\pi_{1}}(s,a)}}{\sum_{a^{\prime}\in
A}e^{Q_{2}^{*|\pi_{1}}(s,a^{\prime})}}+(1-w)\cdot\pi_{i-1}^{2}(a|s)$ (10)

Here $Q_{2}^{*|\pi_{1}}(s,a)$ are the optimal $Q$-values for $A_{2}$, while
$w$ describes the responsiveness of the environment towards the deployed
policy of $A_{1}$. For small $w$, the environment responds strongly to the
current policy, while for large $w$ the environment is less responsive to the
current policy.

##### Implementation

We study the finite sample setting, and sample trajectories instead of taking
single samples from occupancy measures. The learner solves the min-max-problem
(8) using a follow-the-regularized-leader algorithm described in Appendix B.3.
To evaluate the speed at which the algorithms reach a stable occupancy
measure, we evaluate how the occupancy measure at each round compares to the
average of the last $10$ occupancy measures, which we denote by
$d_{\operatorname{last}}$.222Code to reproduce the experiments is available at
https://github.com/bsen/performative-rl-gradually-shifting-envs

##### Performance

In Figures 1(a) and 1(b) we see that MDRR converges the fastest to
$d_{\operatorname{last}}$. This is true both for the setting where the
environment changes faster ($w=0.5$, Figure 1(a)) and when it changes more
slowly ($w=0.15$, Figure 1(b)). This is the case even though MDRR uses less
retrainings than RR. But MDRR uses more samples per retraining, and this seems
to lead to better convergence properties in the exposed settings. This also
means that MDRR has lower variance, as indicated by the smaller confidence
intervals.

##### Ablation study

As we can see in Figure 1(c), the convergence properties of MDRR for different
values of $k$ are similar. As we can see in Figure 1(d), in the range of
$v=1.1$ to $v=1.8$, there does not seem to be much difference in speed of
convergence. The results indicate that MDRR is robust to the choice of its
hyperparameters.

##### Compute details

The experiments were conducted on a compute cluster with each machine having 4
Intel Xeon E7-8857 v2 CPUs and 1.5 TB of RAM. It took approximately 80 to 100
hours per algorithm to complete each experiment.

###  7 Conclusion

This work initiates the study of performative RL in scenarios where the
environment changes gradually. We introduce different algorithms in this
setting and compare them extensively both theoretically and experimentally.
Our results suggest that our novel MDRR algorithm performs particularly well
in this setting, and it would be interesting to investigate similar algorithms
in performative prediction.

###### Acknowledgements.

This research was, in part, funded by the Deutsche Forschungsgemeinschaft
(DFG, German Research Foundation) – project number 467367360.

### References

  * Abbasi Yadkori et al. [2013] Yasin Abbasi Yadkori, Peter L Bartlett, Varun Kanade, Yevgeny Seldin, and Csaba Szepesvári.  Online learning in markov decision processes with adversarially chosen transition probability distributions.  _Advances in neural information processing systems_ , 26, 2013.
  * Bai et al. [2020] Yu Bai, Chi Jin, and Tiancheng Yu.  Near-optimal reinforcement learning with self-play.  _Advances in neural information processing systems_ , 33:2159–2170, 2020.
  * Bell et al. [2021] James Bell, Linda Linsefors, Caspar Oesterheld, and Joar Skalse.  Reinforcement learning in newcomblike environments.  _Advances in Neural Information Processing Systems_ , 34:22146–22157, 2021.
  * Brown et al. [2022] Gavin Brown, Shlomi Hod, and Iden Kalemaj.  Performative prediction in a stateful world.  In _International Conference on Artificial Intelligence and Statistics_ , pages 6045–6061. PMLR, 2022.
  * Cheung et al. [2020] Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu.  Reinforcement learning for non-stationary markov decision processes: The blessing of (more) optimism.  In _International Conference on Machine Learning_ , pages 1843–1854. PMLR, 2020.
  * Daskalakis et al. [2023] Constantinos Daskalakis, Noah Golowich, and Kaiqing Zhang.  The complexity of markov equilibrium in stochastic games.  In _The Thirty Sixth Annual Conference on Learning Theory_ , pages 4180–4234. PMLR, 2023.
  * Dimitrakakis et al. [2017] Christos Dimitrakakis, David C Parkes, Goran Radanovic, and Paul Tylkin.  Multi-view decision processes: the helper-ai problem.  _Advances in neural information processing systems_ , 30, 2017.
  * Even-Dar et al. [2004] Eyal Even-Dar, Sham M Kakade, and Yishay Mansour.  Experts in a markov decision process.  _Advances in neural information processing systems_ , 17, 2004.
  * Even-Dar et al. [2009] Eyal Even-Dar, Sham M Kakade, and Yishay Mansour.  Online markov decision processes.  _Mathematics of Operations Research_ , 34(3):726–736, 2009.
  * Farahmand et al. [2010] Amir-massoud Farahmand, Csaba Szepesvári, and Rémi Munos.  Error propagation for approximate policy and value iteration.  _Advances in Neural Information Processing Systems_ , 23, 2010.
  * Hardt et al. [2022] Moritz Hardt, Meena Jagadeesan, and Celestine Mendler-Dünner.  Performative power.  _Advances in Neural Information Processing Systems_ , 35:22969–22981, 2022.
  * Izzo et al. [2021] Zachary Izzo, Lexing Ying, and James Zou.  How to learn when data reacts to your model: performative gradient descent.  In _International Conference on Machine Learning_ , pages 4641–4650. PMLR, 2021.
  * Izzo et al. [2022] Zachary Izzo, James Zou, and Lexing Ying.  How to learn when data gradually reacts to your model.  In _International Conference on Artificial Intelligence and Statistics_ , pages 3998–4035. PMLR, 2022.
  * Jin et al. [2022] Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu.  V-learning–a simple, efficient, decentralized algorithm for multiagent rl.  In _ICLR 2022 Workshop on Gamification and Multiagent Solutions_ , 2022.
  * Letchford et al. [2012] Joshua Letchford, Liam MacDermed, Vincent Conitzer, Ronald Parr, and Charles Isbell.  Computing optimal strategies to commit to in stochastic games.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 26, pages 1380–1386, 2012.
  * Levine et al. [2020] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu.  Offline reinforcement learning: Tutorial, review, and perspectives on open problems.  _arXiv preprint arXiv:2005.01643_ , 2020.
  * Li and Wai [2022] Qiang Li and Hoi-To Wai.  State dependent performative prediction with stochastic approximation.  In _International Conference on Artificial Intelligence and Statistics_ , pages 3164–3186. PMLR, 2022.
  * Li et al. [2022] Qiang Li, Chung-Yiu Yau, and Hoi-To Wai.  Multi-agent performative prediction with greedy deployment and consensus seeking agents.  _Advances in Neural Information Processing Systems_ , 35:38449–38460, 2022.
  * Mandal et al. [2023] Debmalya Mandal, Stelios Triantafyllou, and Goran Radanovic.  Performative reinforcement learning.  In _International Conference on Machine Learning_ , pages 23642–23680. PMLR, 2023.
  * Mendler-Dünner et al. [2020] Celestine Mendler-Dünner, Juan Perdomo, Tijana Zrnic, and Moritz Hardt.  Stochastic optimization for performative prediction.  _Advances in Neural Information Processing Systems_ , 33:4929–4939, 2020.
  * Miller et al. [2021] John P Miller, Juan C Perdomo, and Tijana Zrnic.  Outside the echo chamber: Optimizing the performative risk.  In _International Conference on Machine Learning_ , pages 7710–7720. PMLR, 2021.
  * Mofakhami et al. [2023] Mehrnaz Mofakhami, Ioannis Mitliagkas, and Gauthier Gidel.  Performative prediction with neural networks.  In _International Conference on Artificial Intelligence and Statistics_ , pages 11079–11093. PMLR, 2023.
  * Mohammadi et al. [2023] Mohammad Mohammadi, Jonathan Nöther, Debmalya Mandal, Adish Singla, and Goran Radanovic.  Implicit poisoning attacks in two-agent reinforcement learning: Adversarial policies for training-time attacks.  _arXiv preprint arXiv:2302.13851_ , 2023.
  * Munos and Szepesvári [2008] Rémi Munos and Csaba Szepesvári.  Finite-time bounds for fitted value iteration.  _Journal of Machine Learning Research_ , 9(5), 2008.
  * Narang et al. [2023] Adhyyan Narang, Evan Faulkner, Dmitriy Drusvyatskiy, Maryam Fazel, and Lillian J Ratliff.  Multiplayer performative prediction: Learning in decision-dependent games.  _Journal of Machine Learning Research_ , 24(202):1–56, 2023.
  * Perdomo et al. [2020] Juan Perdomo, Tijana Zrnic, Celestine Mendler-Dünner, and Moritz Hardt.  Performative prediction.  In _International Conference on Machine Learning_ , pages 7599–7609. PMLR, 2020.
  * Radanovic et al. [2019] Goran Radanovic, Rati Devidze, David Parkes, and Adish Singla.  Learning to collaborate in markov decision processes.  In _International Conference on Machine Learning_ , pages 5261–5270. PMLR, 2019.
  * Rajeswaran et al. [2020] Aravind Rajeswaran, Igor Mordatch, and Vikash Kumar.  A game theoretic framework for model based reinforcement learning.  In _International conference on machine learning_ , pages 7953–7963. PMLR, 2020.
  * Ray et al. [2022] Mitas Ray, Lillian J Ratliff, Dmitriy Drusvyatskiy, and Maryam Fazel.  Decision-dependent risk minimization in geometrically decaying dynamic environments.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 36, pages 8081–8088, 2022.
  * Rosenberg and Mansour [2019] Aviv Rosenberg and Yishay Mansour.  Online convex optimization in adversarial markov decision processes.  In _International Conference on Machine Learning_ , pages 5478–5486. PMLR, 2019.
  * Shapley [1953] Lloyd S Shapley.  Stochastic games.  _Proceedings of the national academy of sciences_ , 39(10):1095–1100, 1953.
  * Vershynin [2010] Roman Vershynin.  Introduction to the non-asymptotic analysis of random matrices.  _arXiv preprint arXiv:1011.3027_ , 2010.
  * Vorobeychik and Singh [2012] Yevgeniy Vorobeychik and Satinder Singh.  Computing stackelberg equilibria in discounted stochastic games.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 26, pages 1478–1484, 2012.
  * Wei and Luo [2021] Chen-Yu Wei and Haipeng Luo.  Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach.  In _Conference on learning theory_ , pages 4300–4354. PMLR, 2021\.
  * Wei et al. [2017] Chen-Yu Wei, Yi-Te Hong, and Chi-Jen Lu.  Online reinforcement learning in stochastic games.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Xie and Jiang [2021] Tengyang Xie and Nan Jiang.  Batch value-function approximation with only realizability.  In _International Conference on Machine Learning_ , pages 11404–11413. PMLR, 2021.
  * Yu and Mannor [2009] Jia Yuan Yu and Shie Mannor.  Online learning in markov decision processes with arbitrarily changing rewards and transitions.  In _2009 international conference on game theory for networks_ , pages 314–322. IEEE, 2009.
  * Zhan et al. [2022] Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee.  Offline reinforcement learning with realizability and single-policy concentrability.  In _Conference on Learning Theory_ , pages 2730–2775. PMLR, 2022\.
  * Zhang et al. [2021] Kaiqing Zhang, Zhuoran Yang, and Tamer Başar.  Multi-agent reinforcement learning: A selective overview of theories and algorithms.  _Handbook of reinforcement learning and control_ , pages 321–384, 2021.
  * Zhong et al. [2021] Han Zhong, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan.  Can reinforcement learning find stackelberg-nash equilibria in general-sum markov games with myopic followers?  _arXiv preprint arXiv:2112.13521_ , 2021.

## Appendix

##  Part I Appendix

###  Appendix A Additional Related Work

In this section we present some more related work on Adversarial MDPs and
Reinforcement Learning (RL).

Adversarial MDPs. More broadly, our framework is related to the literature on
adversarial and non-stationary MDPs, which extensively studied online learning
under adversarial and non-stationary rewards and transitions[Even-Dar et al.,
2004, 2009, Abbasi Yadkori et al., 2013, Yu and Mannor, 2009, Rosenberg and
Mansour, 2019, Cheung et al., 2020, Wei and Luo, 2021]. The positive results
therein, in particular, no-regret guarantees when both rewards and transitions
evolve over time, often assume budget constraints on how many times and by how
much the underlying MDP model can change [Abbasi Yadkori et al., 2013, Cheung
et al., 2020, Wei and Luo, 2021]. We instead rely on sensitivity assumptions
(Assumption 1), introduced in Section 2.

Reinforcement Learning. We also mention the recent work on RL in Newcomb-like
environments [Bell et al., 2021], whose framework is similar to the original
performative RL framework of Mandal et al. [2023]. There, the focus is on the
convergence of value-based RL algorithms; we focus on repeated retraining and
allow the environment response model to gradually change over time. From a
practical point of view, repeated retraining is similar to alternating
optimization for game-theoretic bi-level optimization problems in RL(e.g.,
[Rajeswaran et al., 2020, Mohammadi et al., 2023]). The latter can be thought
of as a training framework for finding optimal commitment policies in Markov
games, whereas the former repeatedly deploys a policy, collects data, and
trains a new policy using offline RL. In that regard, we also relate this
paper to the vast literature on offline RL [Levine et al., 2020]. From a
technical point of view, the most relevant aspects are coverage assumptions
and data generation process: we consider the ones from [Mandal et al., 2023],
which are based on [Zhan et al., 2022, Munos and Szepesvári, 2008].

###  Appendix B Additional Experimental Details

Figure 2: The grid-world.

This section discusses more details on the experiments. Subsection B.1
explains the environment further, subsections B.2 and B.3 discuss further
algorithmic details, subsection B.4 discusses the type and amount of compute
used, and in subsection B.5 we sanity-check if the comparison presented in the
main paper is fair.

####  B.1 Explanation of the Environment

The experimental setting is an adapted version of the one from Mandal et al.
[2023]. We consider the grid world environment depicted in figure 2. There is
one actor in this grid-world environment, which is controlled by two agents,
agent $A_{1}$ and agent $A_{2}$. The actor starts randomly in one of the $S$
states, with uniform probability. $A_{1}$ can decide where the actor goes by
choosing one of the directions left, right, up or down. $A_{2}$ can decide to
intervene on the direction which $A_{1}$ chose. The actions of $A_{2}$ are
not-intervene, left, right, up or down. In case $A_{2}$ chooses not-intervene,
the direction chosen by $A_{1}$ is used. Otherwise, the direction chosen by
$A_{2}$ gets used.

Both agents are reinforcement learners with different goals. $A_{1}$ optimizes
according to the grid-world in figure 2. $A_{2}$ optimizes according to a
perturbed grid-world, where each blank, $F$ or $H$ cell is the same as for
$A_{1}$ with probability $0.7$. With probability $0.3$, it gets changed to
either blank, $F$ or $H$ (chosen uniformely at random).

$A_{1}$ and $A_{2}$ get a negative reward of $-0.01$ if the actor visits a
blank or an $S$ cell, a slightly increased negative reward of $-0.02$ if
visiting a $F$ cell and a large negative reward of $-0.5$ for $H$ cells.
Additionally, when $A_{2}$ decides to intervene, an additional cost of $-0.05$
is inflicted on it.

$A_{1}$ is the main learner which performs RR, DRR or MDRR. $A_{2}$ models the
response of the environment.

$A_{2}$ starts by playing the policy which does never intervene. In each
iteration, first $A_{1}$ optimizes its policy, and then $A_{2}$ responds to
the policy played by $A_{1}$. $A_{2}$ slowly adapts to the current played
policy by agent 1 in each round, by using a mixture between the last played
policy of $A_{2}$ and the softmax over the current optimal $Q$-values, as
described in equation (10) in the main paper.

Furthermore, we use $\gamma=0.9$ for both $A_{1}$ and $A_{2}$ and a maximum
trajectory length of $50$, i.e. after $50$ steps, the trajectory is cut off.
Instead of using the exact occupancy measures $\overline{d}_{i}$ in the
optimization, we approximate them using the trajectories.

####  B.2 Computing Sample Lists for MDRR

In this subsection we describe a practical way to compute samples from MDRR.

Recall that MDRR uses $m_{ik+t}=w_{t}U_{i}$ samples in iteration $i$ from
round $t$, where $w_{t}=\frac{(v-1)v^{t-1}}{v^{k}-1}$ and $U_{i}$ is the total
number of samples used in for the $i$-th retraining. In practice, we assume
that the learner is given some samples for each round.

In practice, we use a slightly different algorithm to compute the number of
samples MDRR uses, because of two reasons. The first reason is that
$w_{t}U_{i}$ could be non-integral. The second reason is that even though MDRR
needs $m_{t}$ samples in round $t$, samples from rounds after $t$ could also
count towards this, if the same policy was applied in the rounds between. This
is because those samples are collected after more repeated applications of the
same policy. Therefore the environment at this point is closer to the limiting
environment than in round $t$ and using additional samples from higher rounds
would increase performance more than using samples from round $t$.

To calculate the number of samples MDRR uses from each round, we propose
Algorithm 3, which we explain in the following. In the following we use the
terms _list_ and _sequence_ somewhat loosely to refer to linked lists of
samples and linked lists of linked lists of samples respectively.

Algorithm 3 takes as input a sequence of lists of samples $S_{1},\dots,S_{k}$
and weights $w_{1},\dots,w_{k}\in\mathbb{R}^{+}$. We can think of $S_{1}$ to
be the number of samples in step $ik+1$ for some $i$, $S_{2}$ to be the number
of samples in step $ik+2$, etc. . Algorithm 3 fulfills the following property.

######  Theorem 6.

Algorithm 3 outputs a sequence ${\mathcal{F}}=[F_{1},\dots,F_{k}]$, which
contains the maximal number of samples $|{\mathcal{F}}|$ such that

  1. 1.

$F_{t}\subseteq S_{t}$ for all $t\in\\{1,\dots,k\\}$ and

  2. 2.

$\left|[F_{t},\dots,F_{k}]\right|\geq\sum_{t^{\prime}=t}^{k}w_{t^{\prime}}|{\mathcal{F}}|$
for all $t\in\\{1,\dots,k\\}$ .

where we denote by $\left|[F_{t},\dots,F_{k}]\right|$ the number of samples in
total in $F_{t},\dots,F_{k}$. Similarly $\left|{\mathcal{F}}\right|$ is the
number of samples in ${\mathcal{F}}$.

Item 1 guarantees that $F_{t}$ only contains samples from $S_{t}$. Item 2
guarantees that for each round $t$, there is a sufficient number of samples
assigned to this step either by samples from rounds greater than $t$, which
are not yet assigned to any round or directly from round $t$. To see this,
notice that the total number of samples in this iteration is
$U_{i}=\left|{\mathcal{F}}\right|$. Therefore, for round $t$, we need at least
$w_{t}|{\mathcal{F}}|$ samples. Those samples have to be from
$F_{t},F_{t+1},\dots,F_{k}$ and must not be assigned to another round
$t^{\prime}\neq t$. Assume that this already holds for all
$t^{\prime\prime}>t$. Then we only need to ensure that the amount of samples
which are not yet assigned to any round plus the samples from round $t$ are
greater equal $w_{i}|{\mathcal{F}}|$. This amount of not yet assigned samples
plus the samples from round $t$ is equal to
$\left|[F_{t+1},\dots,F_{k}]\right|-\sum_{t^{\prime}=t+1}^{k}w_{t^{\prime}}|{\mathcal{F}}|+|F_{t}|$.
Item 2 follows from assuming that this is bigger than $w_{t}|{\mathcal{F}}|$.

1: Input: A sequence $S_{1},\dots,S_{k}$ of lists of samples and corresponding
weights $w_{1},\dots,w_{k}\in\mathbb{R}^{+}$ such that $\sum_{t=1}^{k}w_{t}=1$

2: Output: A sequence ${\mathcal{F}}=[F_{1},\dots,F_{k}]$ of lists of samples
such that $F_{t}\subseteq S_{t}$,
$\left|[F_{t},\dots,F_{k}]\right|\geq\sum_{t^{\prime}=t}^{k}w_{t^{\prime}}|{\mathcal{F}}|$
and $\left|{\mathcal{F}}\right|$ is maximal.

3: $M^{\prime}\leftarrow+\infty$

4: Let ${\mathcal{F}}$ be a sequence of $k$ empty lists

5: for $t=k,\dots,1$ do

6: if $M^{\prime}-\left|{\mathcal{F}}\right|\leq\left|S_{t}\right|$ then

7: Append $M^{\prime}-\left|{\mathcal{F}}\right|$ samples from $S_{t}$ to
$F_{t}$

8: Return ${\mathcal{F}}$

9: $F_{t}\leftarrow S_{t}$

10: $W\leftarrow\sum_{t^{\prime}=t}^{k}w_{t^{\prime}}$

11:
$M^{\prime}\leftarrow\left\lfloor\min\left(\frac{\left|{\mathcal{F}}\right|}{W},M^{\prime}\right)\right\rfloor$

Algorithm 3 Practical algorithm to compute the samples used by MDRR

We now prove Theorem 6 via a loop-invariant argument.

###### Proof of Theorem 6.

Item 1 trivially holds, since only samples from $S_{t}$ are added to $F_{t}$.

We now show that item 2 also holds and that $\left|{\mathcal{F}}\right|$ is
maximal. We define the following proposition $B_{t}$ for every
$t\in\\{1,\dots,k\\}$. $B_{t}$ holds iff for every $j\geq t$, it holds that

$\displaystyle F_{j}\subseteq S_{j}\text{ and
}\left|[F_{j},\dots,F_{k}]\right|\geq\sum_{t^{\prime}=j}^{k}w_{t^{\prime}}\left|{\mathcal{F}}\right|$
(11)

We define the following loop invariant $C_{t}$. $C_{t}$ holds iff after
iteration $t$ of the loop, $M^{\prime}$ is the maximum integer such that
$B_{t}$ holds and using $M^{\prime}-\left|{\mathcal{F}}\right|$ samples for
$F_{1},\dots,F_{t}$ does not lead to a violation of $B_{t}$.

If $C_{t}$ holds for every $t\in\\{1,\dots,k\\}$, the theorem is shown.

We prove that $C_{t}$ holds via induction. $C_{k+1}$ holds before the loop
starts, since we can think of $t$ to be equal to $k+1$ at this time,
$M^{\prime}$ is infinity and ${\mathcal{F}}$ empty.

The induction step goes from $t+1$ to $t$. Assume $C_{t+1}$ holds. The if-
statement in line 6 then ensures that if there are more samples in $S_{t}$
than are still possible, $F_{t}$ is set equal to this number of samples and
the algorithm returns. We know this is correct, since $M^{\prime}$ is maximal.
Otherwise $F_{t}$ is set to $S_{t}$, because this capacity is still there for
samples from $S_{t}$.

Then in line 11, the $\min\left(\frac{|{\mathcal{F}}|}{W},M^{\prime}\right)$
defines the number of samples which can maximally be taken in total. The first
argument of the minimum ensures that (11) holds for $j=t$. The second argument
of the minimum, $M^{\prime}+\left|{\mathcal{F}}\right|$ ensures that $B_{t+1}$
holds via the induction hypothesis. Then $B_{t}$ holds and the induction step
is shown. ∎

####  B.3 Solving the Min-Max Optimization Problem

In this subsection we describe how the learner solves the min-max problem (8)
and the min-max problem in line 7 of Algorithm 2 in the experiments.

To solve the min-max problem of the empirical Lagrangians in equation (8) we
use Algorithm 1 from Mandal et al. [2023].

To solve the min-max problem for MDRR (line 7 of Algorithm 2), we use
Algorithm 4. It works the same as Algorithm 1 of Mandal et al. [2023], the
only difference is in the conditions on $d$ in line 8, where we condition
$d(s,a)/\overline{d}_{t}(s,a)\leq B$ for all steps since the last update of
the policy. We use parameters, $N=10$ and $\beta=\frac{\lambda}{2}=0.05$.

1: Input: regularizing factor $\beta$, occupancy measures since the last
update of the policy $\overline{d}_{t}$ for $t\in\\{1,\dots,k\\}$

2: $d_{0}\leftarrow\bm{0}$

3: for $j=0,1,\dots,N-1$ do

4: if $j=0$ then

5:
$h_{j}\leftarrow\operatorname*{arg\,min}_{h}\hat{\mathcal{L}}^{M}(d_{0},h)+\beta\left\lVert
h\right\rVert_{2}^{2}$ s.t. $\|h\|_{2}\leq\frac{3|S|}{(1-\gamma)^{2}}$

6: else

7:
$h_{j}\leftarrow\operatorname*{arg\,min}_{h}\sum_{j^{\prime}=1}^{j}\hat{\mathcal{L}}^{M}(d_{j^{\prime}},h)+\beta\left\lVert
h\right\rVert_{2}^{2}$ s.t. $\|h\|_{2}\leq\frac{3|S|}{(1-\gamma)^{2}}$

8:
$d_{j+1}\leftarrow\operatorname*{arg\,max}_{d}\hat{\mathcal{L}}^{M}(d,h_{j})$
s.t. $\max_{s,a}d(s,a)/\overline{d}_{t}(s,a)\leq B$ for all
$t\in\\{1,\dots,k\\}$

9: Return $\sum_{j=1}^{N}d_{j}/N$

Algorithm 4 FTRL algorithm to calculate an approximization for the finite sample optimization problem ((8) and (47)) Table 2: Compute Times of the Experiments Algorithm | $\bm{k}$ | $\bm{w}$ | $\bm{v}$ | time (rounded)
---|---|---|---|---
RR | N\A | $0.5$ | N\A |  $\sim 94$ hrs
DRR | $3$ | $0.5$ | N\A |  $\sim 78$ hrs
MDRR | $3$ | $0.5$ | $1.1$ |  $\sim 90$ hrs
RR | N\A | $0.15$ | N\A |  $\sim 105$ hrs
DRR | $3$ | $0.15$ | N\A |  $\sim 88$ hrs
MDRR | $3$ | $0.15$ | $1.1$ |  $\sim 100$ hrs
MDRR | $5$ | $0.5$ | $1.1$ |  $\sim 85$ hrs
MDRR | $5$ | $0.5$ | $1.5$ |  $\sim 77$ hrs
MDRR | $5$ | $0.5$ | $1.8$ |  $\sim 78$ hrs
MDRR | $10$ | $0.5$ | $1.1$ |  $\sim 83$ hrs

####  B.4 Total Amount of Compute and Type of Resources

The experiments were run on a compute cluster with each machine having 4 Intel
Xeon E7-8857 v2 CPUs (4 times 12 cores) and 1.5 TB of RAM.

In Table 2, we detail how long each experiment took to complete on these
machines.

####  B.5 Sanity-Check the Fairness of the Comparison

By only presenting Figures 1(a) and 1(b) in the main paper, we can not rule
out that some of the algorithms converge to very suboptimal solutions. In this
case the comparison would be unfair.

Therefore, in order to sanity-check the fairness of the comparison, we also
investigate the expected value, $V^{d_{t}}_{t}$. This is not directly
associated to finding a stable occupancy measure, but should rather be seen as
a check to see if the algorithms we propose reach similar solutions. We
compute $V^{d_{t}}_{t}$ using the rewards derived from the training sample
trajectories. In other words, when $\operatorname{Tr}_{t}$ is the set of
trajectories sampled in round $t$, and for each trajectory $\tau$, the reward
in step $k$ is $r_{t}(\tau_{k})$, then
$V^{d_{t}}_{t}=\sum_{\tau\in\operatorname{Tr}_{t}}\sum_{k=0}^{l(\tau)}\gamma^{k}\cdot
r_{t}(\tau_{k})$. Here $l(\tau)$ is the length of trajectory $\tau$.

We see the expected values of the algorithms in Figure 3. As we see, after
they settled down, the three algorithms have rather close expected values. We
believe that the differences stem from the initialization of the environment
of the second agent rather than from some inherent differences in the
algorithms.

(a) Here $w=0.5$

(b) Here $w=0.15$

Figure 3: A sanity check if the algorithms reach valid solutions. Since the
values of the three algorithms are close to one another, we assert that none
of them reaches a much less optimal solution than another one, thereby
validating all three approaches.

###  Appendix C Additional Theoretical Results

####  C.1 Existence of Stable Points

Using arguments similar to Mandal et al. [2023], we show that there exists a
stable point.

######  Proposition 1.

If Assumption 1 holds, optimization problem (4) has a fixed point.

###### Proof.

This proposition is very similar to Proposition 1 from Mandal et al. [2023].
The proof follows theirs, and we don’t repeat the arguments made in their
proof. However in order to make use of their arguments, we need to show that
$P_{d}$ and $r_{d}$ are continuous in $d$, which is not immediately clear.
Recall that $P_{d}$ and $r_{d}$ map from occupancy measure $d$ to the
environment the process converges to, if the learner always deploys $\pi_{d}$.
We now prove that $P_{d}$ and $r_{d}$ are continuous in $d$.

We define $\epsilon:=\max(\epsilon_{p},\epsilon_{r})$. Then we see that

$\displaystyle\begin{split}&\|P_{d}-P_{d^{\prime}}\|_{2}+\|r_{d}+r_{d^{\prime}}\|_{2}\leq\iota\left\lVert
d-d^{\prime}\right\rVert_{2}+\epsilon\left(\left\lVert
P_{d}-P_{d^{\prime}}\right\rVert_{2}+\left\lVert
r_{d}-r_{d^{\prime}}\right\rVert_{2}\right)\\\
&\leq\dots\leq\sum_{i=0}^{\infty}\iota\epsilon^{i}\left\lVert
d-d^{\prime}\right\rVert_{2}=\frac{\iota}{1-\epsilon}\left\lVert
d-d^{\prime}\right\rVert_{2}\end{split}$ (12)

The inequalities follow from Assumption 1. Thus $P_{d}$ and $r_{d}$ are
continuous in $d$ and the rest of the proof follows from the same arguments as
the proof of Proposition 1 from Mandal et al. [2023]. ∎

####  C.2 Approximating the Unregularized Objective

Using arguments similar to Mandal et al. [2023], we can show the following
approximation guarantee for the regularized objective.

######  Theorem 7.

For each setting RR, DRR and MDRR, when they approximate a stable policy
$d_{S}$ with respect to the regularized objective (5), the following guarantee
holds:

$\displaystyle\sum_{s,a}r_{d_{S}}(s,a)\cdot
d_{S}(s,a)\geq\max_{d\in\mathcal{C}(d_{S})}\sum_{s,a}r_{d_{S}}(s,a)\cdot
d(s,a)-{\mathcal{O}}\left(\frac{\lambda}{(1-\gamma)^{2}}\right)$

Here $\mathcal{C}(d_{S})$ denotes the set of occupancy measures which are
feasible with respect to $P_{d_{S}}$.

###### Proof.

Since $d_{S}$ is a stable point with respect to objective (5), it holds that

$\sum_{s,a}r_{d_{S}}(s,a)\cdot d_{S}(s,a)-\frac{\lambda}{2}\left\lVert
d_{S}\right\rVert_{2}^{2}\geq\max_{d\in\mathcal{C}(d_{S})}\sum_{s,a}r_{d_{S}}(s,a)\cdot
d(s,a)-\frac{\lambda}{2}\left\lVert d\right\rVert_{2}^{2}$

Therefore,

$\displaystyle\sum_{s,a}r_{d_{S}}(s,a)\cdot d_{S}(s,a)$
$\displaystyle\geq\max_{d\in\mathcal{C}(d_{S})}\sum_{s,a}r_{d_{S}}(s,a)\cdot
d(s,a)-\frac{\lambda}{2}\left\lVert d\right\rVert_{2}^{2}$
$\displaystyle\geq\max_{d\in\mathcal{C}(d_{S})}\sum_{s,a}r_{d_{S}}(s,a)\cdot
d(s,a)-\frac{\lambda}{2(1-\gamma)^{2}}$

The last inequality uses $\left\lVert
d\right\rVert_{2}^{2}=\sum_{s,a}d(s,a)^{2}=(1-\gamma)^{-2}\sum_{s,a}\left((1-\gamma)d(s,a)\right)^{2}\leq(1-\gamma)^{-2}\sum_{s,a}(1-\gamma)d(s,a)=(1-\gamma)^{-2}$.
∎

####  C.3 Contraction

In contrast to the main paper, in the appendix $\epsilon$ refers to
$\epsilon:=\max(\epsilon_{p},\epsilon_{r})$, which signifies the dependency of
the environment on the previous environment.

We define the following distances.

######  Definition 3.

For any occupancy measures $d,d^{\prime}$, probability transition functions
$P,P^{\prime}$ and reward functions $r,r^{\prime}$, we define the distance
between $(d,P,r)$ and $(d^{\prime},P^{\prime},r^{\prime})$ to be equal to

$\operatorname{dist}((d,P,r),(d^{\prime},P^{\prime},r^{\prime})):=\left\lVert
d-d^{\prime}\right\rVert_{2}+\left\lVert
P-P^{\prime}\right\rVert_{2}+\left\lVert r-r^{\prime}\right\rVert_{2}\ .$

We overload notation to also define

$\operatorname{dist}((P,r),(P^{\prime},r^{\prime})):=\left\lVert
P-P^{\prime}\right\rVert_{2}+\left\lVert r-r^{\prime}\right\rVert_{2}\ .$

As described in section 2, show that the mapping from $(P,r)$ to the successor
environment $(\mathcal{P}(d,P,r),\mathcal{R}(d,P,r))$ is a contraction.

######  Proposition 2.

Let $d$ be some occupancy measure. When Assumption 1 holds, in particular
$\epsilon_{p},\epsilon_{r}<1$, the mapping
$g_{d}(P,r):=(\mathcal{P}(d,P,r),\mathcal{R}(d,P,r))$ is a contraction with
Lipschitz coefficient $\epsilon$.

###### Proof.

Let $P,P^{\prime}$ be arbitrary probability transition functions and
$r,r^{\prime}$ arbitrary reward functions.

Then

$\displaystyle\operatorname{dist}(g_{d}(P,r)-g_{d}(P^{\prime},r^{\prime}))=\left\lVert\mathcal{P}(d,P,r)-\mathcal{P}(d,P^{\prime},r^{\prime})\right\rVert_{2}+\left\lVert\mathcal{R}(d,P,r)-\mathcal{R}(d,P^{\prime},r^{\prime})\right\rVert_{2}$
$\displaystyle\leq\epsilon_{p,p}\left\lVert
P-P^{\prime}\right\rVert_{2}+\epsilon_{p,r}\left\lVert
r-r^{\prime}\right\rVert_{2}+\epsilon_{r,p}\left\lVert
P-P^{\prime}\right\rVert_{2}+\epsilon_{r,r}\left\lVert
r-r^{\prime}\right\rVert_{2}$ $\displaystyle\leq\epsilon\left\lVert
P-P^{\prime}\right\rVert_{2}+\epsilon\left\lVert
r-r^{\prime}\right\rVert_{2}=\epsilon\cdot\operatorname{dist}((P,r),(P^{\prime},r^{\prime}))\
.$

Where the first inequality follows from Assumption 1 and the second one
follows from the defintion of $\epsilon_{p}$, $\epsilon_{r}$ and $\epsilon$.
From this the proposition follows. ∎

###  Appendix D Proofs for Repeated Retraining (RR) (Section 3)

####  D.1 Definitions

We define the following numbers

######  Definition 4.

We define

$\displaystyle\alpha$
$\displaystyle:=\sqrt{3}+\frac{\sqrt{7}|S|\sqrt{|S|}}{(1-\gamma)^{2}}\text{
and}$ $\displaystyle\beta$
$\displaystyle:=\frac{(4\sqrt{7}\gamma+3\sqrt{6})|S|}{(1-\gamma)^{2}}+\frac{18\sqrt{7}\gamma|S|^{2}\sqrt{|S|}}{(1-\gamma)^{4}}\
.$

######  Definition 5.

Let $\operatorname{GD}(P,r)$ be the solution to the regularized optimization
problem, with probability transition function $P$ and reward function $r$,
i.e.

$\displaystyle\operatorname{GD}(P,r):=\operatorname*{arg\,max}_{d\geq 0}$
$\displaystyle\ \sum_{s,a}d(s,a)r(s,a)-\frac{\lambda}{2}\left\lVert
d\right\rVert_{2}^{2}$ s.t.
$\displaystyle\sum_{a}d(s,a)=\rho(s)+\gamma\cdot\sum_{s^{\prime},a}d(s^{\prime},a)P(s^{\prime},a,s)\
\forall s\ .$

####  D.2 RR in the Exact Setting (Theorem 1)

We show the following more general version of Theorem 1.

######  Theorem 8.

Assume that Assumption 1 holds and

$\lambda>\max\left\\{(1-\epsilon_{p})^{-1}\beta,(1-\epsilon_{r})^{-1}\alpha\right\\}$

Then for any $\delta>0$, we have

$\left\lVert d_{t}-d_{S}\right\rVert_{2}\leq\delta\text{\quad for all
}t\geq\frac{\ln\left(\frac{\left\lVert d_{0}-d_{S}\right\rVert_{2}+\left\lVert
P_{0}-P_{S}\right\rVert_{2}+\left\lVert
r_{0}-r_{S}\right\rVert_{2}}{\delta}\right)}{\ln\left(\left(\max\left\\{\iota,\epsilon_{p}+\frac{\beta}{\lambda},\epsilon_{r}+\frac{\alpha}{\lambda}\right\\}\right)^{-1}\right)}+1,$

with $\alpha$ and $\beta$ defined in Definition 4.

We first discuss how to obtain Theorem 1 from Theorem 8. Assumption 2 ensures
that $\beta\geq\alpha$, $\epsilon_{p}=\epsilon_{r}=\epsilon$ and
$\iota\leq\epsilon$. We further bound $\left\lVert
d_{0}-d_{S}\right\rVert_{2}\leq\frac{2}{1-\gamma}$, $\left\lVert
P_{0}-P_{S}\right\rVert_{2}\leq\sqrt{2|S||A|}$ and $\left\lVert
r_{0}-r_{S}\right\rVert_{2}\leq\sqrt{|S||A|}$. Choosing
$\lambda=2\beta(1-\epsilon)^{-1}$ then provides the desired bounds.

The proof of Theorem 8 has a similar structure to the proof of Theorem 4 in
Brown et al. [2022].

###### Proof of Theorem 8.

We define by $f$ the mapping from $(d_{t-1},P_{t-1},r_{t-1})$ to
$(d_{t},P_{t},r_{t})$, i.e.

$f(d,P,r):=(\operatorname{GD}(P,r),\mathcal{P}(d,P,r),\mathcal{R}(d,P,r))\ .$

We analyze
$\operatorname{dist}(f(d,P,r),f(d^{\prime},P^{\prime},r^{\prime}))$.

$\begin{split}\operatorname{dist}(f(d,P,r),f(d^{\prime},P^{\prime},r^{\prime}))=&\|\operatorname{GD}(P,r)-\operatorname{GD}(P^{\prime},r^{\prime})\|_{2}\\\
&+\|\mathcal{P}(d,P,r)-\mathcal{P}(d^{\prime},P^{\prime},r^{\prime})\|_{2}\\\
&+\|\mathcal{R}(d,P,r)-\mathcal{R}(d^{\prime},P^{\prime},r^{\prime})\|_{2}\end{split}$
(13)

The last two terms of this sum can be bounded by using Assumption 1 :

$\begin{split}&\|\mathcal{P}(d,P,r))-\mathcal{P}(d^{\prime},P^{\prime},r^{\prime}))\|_{2}+\|\mathcal{R}(d,P,r))-\mathcal{R}(d^{\prime},P^{\prime},r^{\prime}))\|_{2}\\\
\leq&\
(\iota_{p}+\iota_{r})\|d-d^{\prime}\|_{2}+(\epsilon_{p,p}+\epsilon_{r,p})\|P-P^{\prime}\|_{2}+(\epsilon_{p,r}+\epsilon_{r,r})\|r-r^{\prime}\|_{2}\end{split}$
(14)

We now bound the first term of (13), i.e.
$\|\operatorname{GD}(P,r)-\operatorname{GD}(P^{\prime},r^{\prime})\|_{2}$.

From Lemma 1, we get

$\displaystyle\|\operatorname{GD}(P,r)-\operatorname{GD}(P^{\prime},r^{\prime})\|_{2}\leq\frac{\alpha}{\lambda}\|r-r^{\prime}\|_{2}+\frac{\beta}{\lambda}\|P-P^{\prime}\|_{2}$
(15)

Combining (13), (14) and (15) we get

$\displaystyle\begin{split}&\operatorname{dist}(f(d,P,r),f(d^{\prime},P^{\prime},r^{\prime}))\leq\iota_{d}\|d-d^{\prime}\|_{2}\\\
&+\left(\epsilon_{p}+\frac{\beta}{\lambda}\right)\|P-P^{\prime}\|_{2}+\left(\epsilon_{r}+\frac{\alpha}{\lambda}\right)\|r-r^{\prime}\|_{2}\end{split}$
(16)

We define
$q:=\max\left(\iota_{d},\epsilon_{p}+\frac{\beta}{\lambda},\epsilon_{r}+\frac{\alpha}{\lambda}\right)$.
From (16) and the definition of $q$, it follows that

$\displaystyle\operatorname{dist}((d_{t},P_{t},r_{t}),(d_{S},P_{S},r_{S}))=\operatorname{dist}(f(d_{t-1},P_{t-1},r_{t-1}),f(d_{S},P_{S},r_{S}))$
$\displaystyle\leq$ $\displaystyle
q\operatorname{dist}((d_{t-1},P_{t-1},r_{t-1}),(d_{S},P_{S},r_{S}))\leq
q^{t}\left(\left\lVert d_{0}-d_{S}\right\rVert_{2}+\left\lVert
P_{0}-P_{S}\right\rVert_{2}+\left\lVert r_{0}-r_{S}\right\rVert_{2}\right),$

where the first equality follows from the fact that $(d_{S},P_{S},r_{S})$ is a
fixed point of $f$.

Note that by the conditions on $\lambda,\iota,\epsilon_{p}$ and
$\epsilon_{r}$, it holds that $q<1$.

Therefore, if we set
$t\geq\ln(\operatorname{dist}((d_{1},P_{0},r_{0}),(d_{S},P_{S},r_{S}))/\delta)/\ln(1/q)+1$,
then we get that

$\operatorname{dist}((d_{t},P_{t-1},r_{t-1}),(d_{S},P_{S},r_{S}))\leq\delta.$

Then also $\left\lVert d_{t}-d_{S}\right\rVert_{2}\leq\delta$. ∎

######  Lemma 1 (similar to lemma 2 of Brown et al. [2022]).

Let $P,\hat{P}$ be two probability transition functions and $r,\hat{r}$ be two
reward functions. Then

$\|\operatorname{GD}(P,r)-\operatorname{GD}(\hat{P},\hat{r})\|_{2}\leq\frac{\alpha}{\lambda}\|r-\hat{r}\|_{2}+\frac{\beta}{\lambda}\|P-\hat{P}\|_{2}$

with $\alpha$ and $\beta$ from Definition 4.

###### Proof.

Let $M$ and $\hat{M}$ be two MDPs and $r$ and $\hat{r}$ be the corresponding
reward functions and $P$ and $\hat{P}$ be the corresponding transition
probability functions.

In the following we use some arguments from Mandal et al. [2023]. Those
arguments apply here as well, since we use the same optimization problem as
they do.

Let $h$ and $\hat{h}$ be the optimal solution to the dual objective (12) in
Mandal et al. [2023] to $M$ and $\hat{M}$ respectively.

From Mandal et al. [2023] we get that (page 16, after “We now substitute the
above bound in equation 15.”)

$\displaystyle-\frac{|A|(1-\gamma)^{2}}{\lambda}\left\|h-\hat{h}\right\|_{2}^{2}\geq-\left\|h-\hat{h}\right\|_{2}\left\|\nabla\mathcal{L}(\hat{h};M)-\nabla\mathcal{L}(\hat{h},\hat{M})\right\|_{2}$
(17)

and also from Mandal et al. [2023]

$\displaystyle\left\|\nabla\mathcal{L}(\hat{h};M)-\nabla\mathcal{L}(\hat{h},\hat{M})\right\|_{2}$
$\displaystyle\leq\frac{4|S|\sqrt{|A|}}{\lambda}\left\|r-\hat{r}\right\|_{2}+\left(\frac{4\gamma\sqrt{|S||A|}}{\lambda}+\frac{6\gamma\sqrt{|A|}|S|}{\lambda}\left\|\hat{h}\right\|_{2}\right)\left\|P-\hat{P}\right\|_{2}$
$\displaystyle\leq\frac{4|S|\sqrt{|A|}}{\lambda}\left\|r-\hat{r}\right\|_{2}+\left(\frac{4\gamma\sqrt{|S||A|}}{\lambda}+\frac{6\gamma\sqrt{|A|}|S|}{\lambda}\frac{3|S|}{(1-\gamma)^{2}}\right)\left\|P-\hat{P}\right\|_{2}$
(18)

The first inequality is due to lemma 3 of Mandal et al. [2023] and the second
inequality is due to lemma 4 in Mandal et al. [2023].

Combining (17) and (18) we get:

$\displaystyle\left\|h-\hat{h}\right\|_{2}\leq$
$\displaystyle\frac{\lambda}{|A|(1-\gamma)^{2}}\left\|\nabla\mathcal{L}(\hat{h};M)-\nabla\mathcal{L}(\hat{h},\hat{M})\right\|_{2}$
$\displaystyle\leq$
$\displaystyle\frac{\lambda}{|A|(1-\gamma)^{2}}\Biggl{(}\frac{4|S|\sqrt{|A|}}{\lambda}\left\|r-\hat{r}\right\|_{2}+\left(\frac{4\gamma\sqrt{|S||A|}}{\lambda}+\frac{6\gamma\sqrt{|A|}|S|}{\lambda}\frac{3|S|}{(1-\gamma)^{2}}\right)\left\|P-\hat{P}\right\|_{2}\Biggr{)}$
(19)

Another result from Mandal et al. [2023], which is found in the proof of lemma
1 is:

$\displaystyle\left\|\operatorname{GD}(P,r)-\operatorname{GD}(\hat{P},\hat{r})\right\|_{2}^{2}\leq\frac{3}{\lambda^{2}}\|r-\hat{r}\|_{2}^{2}+\frac{7|A||S|}{\lambda^{2}}\left\|h-\hat{h}\right\|_{2}^{2}+\frac{6}{\lambda^{2}}\left\|\hat{h}\right\|_{2}^{2}\left\|P-\hat{P}\right\|_{2}^{2}$
(20)

Combining (19) and (20) it follows that

$\displaystyle\left\|\operatorname{GD}(P,r)-\operatorname{GD}(\hat{P},\hat{r})\right\|_{2}\leq$
$\displaystyle\frac{\sqrt{3}}{\lambda}\|r-\hat{r}\|_{2}+\frac{\sqrt{7|A||S|}}{\lambda}\left\|h-\hat{h}\right\|_{2}+\frac{\sqrt{6}}{\lambda}\left\|\hat{h}\right\|_{2}\left\|P-\hat{P}\right\|_{2}$
$\displaystyle\leq$
$\displaystyle\frac{\sqrt{3}}{\lambda}\|r-\hat{r}\|_{2}+\frac{\sqrt{7|A||S|}}{\lambda}\left\|h-\hat{h}\right\|_{2}+\frac{\sqrt{6}}{\lambda}\frac{3|S|}{(1-\gamma)^{2}}\left\|P-\hat{P}\right\|_{2}$
(21)

where the last inequality follows from lemma 4 of Mandal et al. [2023].

Combining (19) and (21) we get:

$\displaystyle\left\|\operatorname{GD}(P,r)-\operatorname{GD}(\hat{P},\hat{r})\right\|_{2}\leq\frac{\sqrt{3}}{\lambda}\|r-\hat{r}\|_{2}+\frac{\sqrt{7|A||S|}}{\lambda}\frac{\lambda}{|A|(1-\gamma)^{2}}\Biggl{(}\frac{4|S|\sqrt{|A|}}{\lambda}\left\|r-\hat{r}\right\|_{2}$
$\displaystyle+\left(\frac{4\gamma\sqrt{|S||A|}}{\lambda}+\frac{6\gamma\sqrt{|A|}|S|}{\lambda}\frac{3|S|}{(1-\gamma)^{2}}\right)\left\|P-\hat{P}\right\|_{2}\Biggr{)}+\frac{\sqrt{6}}{\lambda}\frac{3|S|}{(1-\gamma)^{2}}\left\|P-\hat{P}\right\|_{2}$
$\displaystyle=$
$\displaystyle\Biggl{(}\frac{\sqrt{3}}{\lambda}+\frac{\sqrt{7|A||S|}}{\lambda}\frac{\lambda}{|A|(1-\gamma)^{2}}\frac{4|S|\sqrt{|A|}}{\lambda}\Biggr{)}\|r-\hat{r}\|_{2}$
$\displaystyle+\Biggl{(}\frac{\sqrt{7|A||S|}}{\lambda}\frac{\lambda}{|A|(1-\gamma)^{2}}\Biggl{(}\frac{4\gamma\sqrt{|S||A|}}{\lambda}+\frac{6\gamma\sqrt{|A|}|S|}{\lambda}\frac{3|S|}{(1-\gamma)^{2}}\Biggr{)}+\frac{\sqrt{6}}{\lambda}\frac{3|S|}{(1-\gamma)^{2}}\Biggr{)}\left\|P-\hat{P}\right\|_{2}$
$\displaystyle=$
$\displaystyle\Biggl{(}\frac{\sqrt{3}}{\lambda}+\frac{\sqrt{7}|S|\sqrt{|S|}}{(1-\gamma)^{2}\lambda}\Biggr{)}\|r-\hat{r}\|_{2}+\Biggl{(}\frac{(4\sqrt{7}\gamma+3\sqrt{6})|S|}{(1-\gamma)^{2}\lambda}+\frac{18\sqrt{7}\gamma|S|^{2}\sqrt{|S|}}{(1-\gamma)^{4}\lambda}\Biggr{)}\left\|P-\hat{P}\right\|_{2}$

∎

####  D.3 RR with Finite Samples (Theorem 2)

In general we note that using our sample generation model, it is easy to get
an estimate of the current occupancy measure $\overline{d}$, by comparing how
many samples were drawn for each pair $(s,a)$ and how many samples were drawn
overall. It is also straightforward to bound those estimates using standard
methods such as Hoeffding’s inequality. For simplicity, we implicitly assume
that those occupancy measures are provided. More concretely, in Lagrangians
(7) and (9) we assume that $\overline{d}_{j}$ is given.

######  Definition 6.

We denote by $\widehat{\operatorname{GD}}(d_{t},F)$ the solution to
optimization problem corresponding to $\hat{\mathcal{L}}$, i.e.

$\displaystyle\widehat{\operatorname{GD}}(d_{t},F):=\operatorname*{arg\,max}_{d}\min_{h}\underbrace{\left(-\frac{\lambda}{2}\left\lVert
d\right\rVert_{2}^{2}+\sum_{s}h(s)\rho(s)+\sum_{(s,a,r,s^{\prime})\in
F}\frac{d(s,a)}{\overline{d}_{t}(s,a)}\cdot\frac{r-h(s)+\gamma
h(s^{\prime})}{\left|F\right|(1-\gamma)}\right)}_{=\hat{{\mathcal{L}}}}$

We use the following result from Mandal et al. [2023].

######  Lemma 2.

Given an arbitrary occupancy measure $d$, probability transition function $P$
and reward function $r$, suppose that
$\operatorname{GD}(P,r)(s,a)/\overline{d}(s,a)\leq B$ for all $(s,a)\in
S\times A$, where $\overline{d}$ is the occupancy measure of $\pi_{d}$ in an
environment with transition probabilities $P$. Furthermore, let $F$ be a set
of samples drawn according to the occupancy measure $\overline{d}$ with $r$
being the reward function. We assume

$\displaystyle\left|F\right|\geq\frac{1}{\mu^{2}}\left(|A|\ln\left(\frac{2}{\delta_{1}}\right)+\ln\left(\frac{12|S|}{\mu(1-\gamma)^{2}}\right)+2|A|\ln\left(\frac{\ln\left(\frac{3|S|^{2}|A|B}{\mu(1-\gamma)^{2}}\right)}{\mu}\right)\right),$

for arbitrary $\mu,\delta_{1}>0$. Then the following bound holds with
probability at least $1-\delta_{1}$.

$\displaystyle\|\operatorname{GD}(P,r)-\widehat{\operatorname{GD}}(d,F)\|_{2}$
$\displaystyle\leq\frac{6\sqrt{|S|^{1.5}(B+\sqrt{|A|})\mu}}{(1-\gamma)^{1.5}}\frac{1}{\sqrt{\lambda}}$

This lemma follows from the equation which comes second after equation (23) in
the work from Mandal et al. [2023] on page 30, after the text “Rearranging and
using lemma 12 we get the following bound”. The conditions follow from the
conditions under which this equation holds in the work from Mandal et al.
[2023]. Note that we write $\mu$ instead of $\epsilon$, which is the variable
name used in Mandal et al. [2023]. The same arguments as in Mandal et al.
[2023] hold, since they also look at the one step updates optimizing
${\mathcal{L}}$ and $\hat{\mathcal{L}}$, which are the same in this work.

We can then show a more general version of Theorem 2.

######  Theorem 9.

Suppose that overlap Assumption 3 holds for $k=1$ and parameter $B$ and
Assumption 1 holds. Let
$(x_{p},x_{r})\in\\{(\iota_{p},\iota_{r}),(\epsilon_{p,p},\epsilon_{r,p}),(\epsilon_{p,r},\epsilon_{r,r})\\}$
be the pair maximizing
$\left(\frac{\alpha}{\lambda}+1\right)x_{r}+\left(\frac{\beta}{\lambda}+1\right)x_{p}$.
We then assume that

$\lambda>\max\left\\{(1-\epsilon_{p})^{-1}\beta,(1-\epsilon_{r})^{-1}\alpha,\frac{\alpha
x_{r}+\beta x_{p}}{1-\zeta-x_{r}-x_{p}}\right\\}.$

Furthermore assume that

$\displaystyle m_{t}\geq$
$\displaystyle\left(\frac{\xi}{\lambda\zeta^{2}}\right)^{2}\left(|A|\ln\left(\frac{4t^{2}}{p}\right)+\ln\left(\frac{12|S|\xi}{\lambda\zeta^{2}(1-\gamma)^{2}}\right)+2|A|\ln\left(\frac{\xi\ln\left(\frac{3|S||A|B\xi}{\lambda\zeta^{2}(1-\gamma)^{2}}\right)}{\lambda\zeta^{2}}\right)\right)\
,$

with $\xi=\frac{36|S|^{1.5}(B+\sqrt{|A|})}{\delta^{2}(1-\gamma)^{3}}$. Then
for any $\delta>0$, we have

$\left\lVert d_{t}-d_{S}\right\rVert_{2}\leq\delta\text{\quad for all
}t\geq\frac{\ln\left(\frac{\left\lVert d_{1}-d_{S}\right\rVert_{2}+\left\lVert
P_{0}-P_{S}\right\rVert_{2}+\left\lVert
r_{0}-r_{S}\right\rVert_{2}}{\delta}\right)}{\ln\left(1/\left(\zeta+\Big{(}\frac{\alpha}{\lambda}+1\Big{)}x_{r}+\Big{(}\frac{\beta}{\lambda}+1\Big{)}x_{p}\right)\right)}+1.$

Here $\zeta$ can be chosen to be an arbitrary value between $0$ and
$1-x_{r}-x_{p}$. It defines a trade-off between the conditions on the
regularization parameter $\lambda$ and on the number of samples $m_{t}$.

Theorem 2 follows from Theorem 9 in the following way. We set
$\zeta=(1-\epsilon)/2$, and
$\lambda=\frac{2\epsilon(\alpha+\beta)}{1-\epsilon}$.

Then for the denominator of the number of retrainings, we derive

$\displaystyle\zeta+\Big{(}\frac{\alpha}{\lambda}+1\Big{)}\frac{\epsilon}{2}+\Big{(}\frac{\beta}{\lambda}+1\Big{)}\frac{\epsilon}{2}=\frac{1}{2}+\frac{\epsilon}{2}+\frac{\epsilon(\alpha+\beta)}{2\lambda}=\frac{1}{2}+\frac{\epsilon}{2}+\frac{1-\epsilon}{4}=\frac{3}{4}+\frac{\epsilon}{4}$

We can bound $\left\lVert d_{1}-d_{S}\right\rVert_{2}$, $\left\lVert
P_{0}-P_{S}\right\rVert_{2}$ and $\left\lVert r_{0}-r_{S}\right\rVert_{2}$
like above, to obtain

$\displaystyle
t\geq\frac{\ln\left(\frac{\frac{2}{1-\gamma}+\left(1+\sqrt{2}\right)\sqrt{|S||A|}}{\delta}\right)}{\ln\left(1/\left(\frac{3}{4}+\frac{\epsilon}{4}\right)\right)}+1$

###### Proof of Theorem 9.

From lemma 2, we get that with probability $1-\delta_{1}$

$\displaystyle\|\operatorname{GD}(P_{t},r_{t})-\widehat{\operatorname{GD}}(d_{t},F_{t})\|_{2}$
$\displaystyle\leq\frac{6\sqrt{|S|^{1.5}(B+\sqrt{|A|})\mu}}{(1-\gamma)^{1.5}}\frac{1}{\sqrt{\lambda}},$
(22)

as long as

$\displaystyle
m_{t}\geq\frac{1}{\mu^{2}}\left(|A|\ln\left(\frac{2}{\delta_{1}}\right)+\ln\left(\frac{12|S|}{\mu(1-\gamma)^{2}}\right)+2|A|\ln\left(\frac{\ln\left(\frac{3|S|^{2}|A|B}{\mu(1-\gamma)^{2}}\right)}{\mu}\right)\right).$

If we set $\delta_{1}=p/2t^{2}$ in step $t$, we get that event (22) holds with
probability at least $1-p/2t^{2}$ in round $t$. Via a union bound over all
rounds, we get that event (22) holds with probability at least $1-p$ in all
rounds.

Let $\hat{g}(d_{t+1},P_{t},r_{t})$ be the result after one round, i.e.

$\hat{g}(d_{t+1},P_{t},r_{t})=(\widehat{\operatorname{GD}}(d_{t+1},F_{t+1}),{\mathcal{P}}(d_{t+1},P_{t},r_{t}),{\mathcal{R}}(d_{t+1},P_{t},r_{t}))\
.$

I.e. it holds that $(d_{t+2},P_{t+1},r_{t+1})=\hat{g}(d_{t+1},P_{t},r_{t})$.

We analyze

$\displaystyle\operatorname{dist}(\hat{g}(d_{t+1},P_{t},r_{t}),(d_{S},P_{S},r_{S}))=$
$\displaystyle\ \ \
\|\widehat{\operatorname{GD}}(d_{t+1},F_{t+1})-d_{S}\|_{2}$
$\displaystyle+\|{\mathcal{P}}(d_{t+1},P_{t},r_{t})-{\mathcal{P}}(d_{S},P_{S},r_{S})\|_{2}+\|{\mathcal{R}}(d_{t+1},P_{t},r_{t})-{\mathcal{R}}(d_{S},P_{S},r_{S})\|_{2}$
$\displaystyle\begin{split}\leq&\ \ \
\|\widehat{\operatorname{GD}}(d_{t+1},F_{t+1})-d_{S}\|_{2}\\\
&+\iota_{d}\|d_{t+1}-d_{S}\|_{2}+\epsilon_{p}\|P_{t}-P_{S}\|_{2}+\epsilon_{r}\|r_{t}-r_{S}\|_{2}\end{split}$
(23)

where the last inequality is due to Assumption 1.

It remains to analyze
$\|\widehat{\operatorname{GD}}(d_{t+1},F_{t+1})-d_{S}\|_{2}$. Using equation
(22), we see that

$\displaystyle\|\widehat{\operatorname{GD}}(d_{t+1},F_{t+1})-d_{S}\|_{2}$
$\displaystyle\leq\|\widehat{\operatorname{GD}}(d_{t+1},F_{t+1})-\operatorname{GD}(P_{t+1},r_{t+1})\|_{2}+\|\operatorname{GD}(P_{t+1},r_{t+1})-d_{S}\|_{2}$
$\displaystyle\leq\frac{6\sqrt{|S|^{1.5}(B+\sqrt{|A|})\epsilon}}{(1-\gamma)^{1.5}}\frac{1}{\sqrt{\lambda}}+\|\operatorname{GD}(P_{t+1},r_{t+1})-\operatorname{GD}(P_{S},r_{S})\|_{2}$
(24)

Furthermore we can derive

$\displaystyle\|\operatorname{GD}(P_{t+1},r_{t+1})-\operatorname{GD}(P_{S},r_{S})\|_{2}\leq\frac{\alpha}{\lambda}\|r_{t+1}-r_{S}\|_{2}+\frac{\beta}{\lambda}\left\lVert
P_{t+1}-P_{S}\right\rVert_{2}$ $\displaystyle=$
$\displaystyle\frac{\alpha}{\lambda}\|{\mathcal{R}}(d_{t+1},P_{t},r_{t})-{\mathcal{R}}(d_{S},P_{S},r_{S})\|_{2}+\frac{\beta}{\lambda}\left\|{\mathcal{P}}(d_{t+1},P_{t},r_{t})-{\mathcal{P}}(d_{S},P_{S},r_{S})\right\|_{2}$
$\displaystyle\begin{split}\leq&\frac{\alpha}{\lambda}(\iota_{r}\|d_{t+1}-d_{S}\|_{2}+\epsilon_{r,p}\|P_{t}-P_{S}\|_{2}+\epsilon_{r,r}\|r_{t}-r_{S}\|_{2})\\\
&+\frac{\beta}{\lambda}(\iota_{p}\|d_{t+1}-d_{S}\|_{2}+\epsilon_{p,p}\|P_{t}-P_{S}\|_{2}+\epsilon_{p,r}\|r_{t}-r_{S}\|_{2})\end{split}$
(25)

where the first inequality follows from lemma 1, in the equality we use the
fact that $P_{t+1}={\mathcal{P}}(d_{t+1},P_{t},r_{t})$,
$r_{t+1}={\mathcal{R}}(d_{t+1},P_{t},r_{t})$,
$P_{S}={\mathcal{P}}(d_{S},P_{S},r_{S})$,
$r_{S}={\mathcal{R}}(d_{S},P_{S},r_{S})$ and Assumption 1.

Inserting (25) into (24) and the result into (23), we get

$\displaystyle\begin{split}\operatorname{dist}(\hat{g}(d_{t+1},P_{t},r_{t}),(d_{S},P_{S},r_{S}))\leq&\frac{6\sqrt{|S|^{1.5}(B+\sqrt{|A|})\mu}}{(1-\gamma)^{1.5}}\frac{1}{\sqrt{\lambda}}\\\
&+\left(\left(\frac{\alpha}{\lambda}+1\right)\iota_{r}+\left(\frac{\beta}{\lambda}+1\right)\iota_{p}\right)\|d_{t+1}-d_{S}\|_{2}\\\
&+\left(\left(\frac{\alpha}{\lambda}+1\right)\epsilon_{r,p}+\left(\frac{\beta}{\lambda}+1\right)\epsilon_{p,p}\right)\|P_{t}-P_{S}\|_{2}\\\
&+\left(\left(\frac{\alpha}{\lambda}+1\right)\epsilon_{r,r}+\left(\frac{\beta}{\lambda}+1\right)\epsilon_{p,r}\right)\|r_{t}-r_{S}\|_{2}\end{split}$
(26)

We now introduce a new parameter $\zeta\in(0,1-x_{r}-x_{p})$, which is
mentioned in the theorem. We set
$\mu=\frac{\zeta^{2}\delta^{2}\lambda(1-\gamma)^{3}}{36|S|^{1.5}(B+\sqrt{|A|})}$.

This allows us to rewrite (26) into

$\displaystyle\operatorname{dist}(\hat{g}(d_{t+1},P_{t},r_{t}),(d_{S},P_{S},r_{S}))\leq$
$\displaystyle\zeta\delta$
$\displaystyle+\left(\left(\frac{\alpha}{\lambda}+1\right)\iota_{r}+\left(\frac{\beta}{\lambda}+1\right)\iota_{p}\right)\|d_{t+1}-d_{S}\|_{2}$
$\displaystyle+\left(\left(\frac{\alpha}{\lambda}+1\right)\epsilon_{r,p}+\left(\frac{\beta}{\lambda}+1\right)\epsilon_{p,p}\right)\|P_{t}-P_{S}\|_{2}$
$\displaystyle+\left(\left(\frac{\alpha}{\lambda}+1\right)\epsilon_{r,r}+\left(\frac{\beta}{\lambda}+1\right)\epsilon_{p,r}\right)\|r_{t}-r_{S}\|_{2}$
$\displaystyle\begin{split}\leq&\zeta\delta+\left(\left(\frac{\alpha}{\lambda}+1\right)x_{r}+\left(\frac{\beta}{\lambda}+1\right)x_{p}\right)\\\
&\cdot\left(\|d_{t+1}-d_{S}\|_{2}+\|P_{t}-P_{S}\|_{2}+\|r_{t}-r_{S}\|_{2}\right)\end{split}$
(27)

Where we select
$(x_{p},x_{r})\in\\{(\iota_{p},\iota_{r}),(\epsilon_{p,p},\epsilon_{r,p}),(\epsilon_{p,r},\epsilon_{r,r})\\}$
to be the pair maximizing
$\left(\frac{\alpha}{\lambda}+1\right)x_{r}+\left(\frac{\beta}{\lambda}+1\right)x_{p}$.

Note that by this formulation of $\mu$, the bound on $m_{t}$ becomes

$\displaystyle m_{t}\geq$
$\displaystyle\left(\frac{36|S|^{1.5}(B+\sqrt{|A|})}{\zeta^{2}\delta^{2}\lambda(1-\gamma)^{3}}\right)^{2}\Bigg{(}|A|\ln\left(\frac{4t^{2}}{p}\right)+\ln\left(\frac{432|S|^{2.5}(B+\sqrt{|A|})}{\zeta^{2}\delta^{2}\lambda(1-\gamma)^{5}}\right)$
$\displaystyle+2|A|\ln\left(\frac{36|S|^{1.5}(B+\sqrt{|A|})\ln\left(\frac{108|S|^{3.5}|A|B(B+\sqrt{|A|})}{\zeta^{2}\delta^{2}\lambda(1-\gamma)^{5}}\right)}{\zeta^{2}\delta^{2}\lambda(1-\gamma)^{3}}\right)\Bigg{)}$

We now apply lemma 3 on the sequence
$\\{(d_{t+1},P_{t},r_{t})\\}_{t\in\mathbb{N}}$ using (27). We can do this,
because by our assumption, we know that $\lambda>\frac{\alpha x_{r}+\beta
x_{p}}{1-\zeta-x_{r}-x_{p}}$ and $1>\zeta+x_{r}+x_{p}$, so

$\displaystyle\zeta+\Big{(}\frac{\alpha}{\lambda}+1\Big{)}x_{r}+\Big{(}\frac{\beta}{\lambda}+1\Big{)}x_{p}$
$\displaystyle<$ $\displaystyle\zeta+x_{r}+x_{p}+\frac{\alpha x_{r}(1-\zeta-
x_{r}-x_{p})}{\alpha x_{r}+\beta x_{p}}+\frac{\beta x_{p}(1-\zeta-
x_{r}-x_{p})}{\alpha x_{r}+\beta x_{p}}=1\ .$

The bound stated in the Theorem follows by the application of lemma 3 and the
fact that $\left\lVert
d_{t+1}-d_{S}\right\rVert_{2}\leq\operatorname{dist}((d_{t+1},P_{t},r_{t}),(d_{S},P_{S},r_{S}))$.
∎

We use of the following argument, which is often used in the performative
prediction setting [Perdomo et al., 2020, Brown et al., 2022, Mandal et al.,
2023].

######  Lemma 3.

Let $(\mathcal{M},\operatorname{dist})$ be a metric space and $x_{1},x_{2}\geq
0$ with $x_{1}+x_{2}<1$. Assume that $\\{p_{i}\\}_{i\in\mathbb{N}}$ is a
sequence of points in $\mathcal{M}$ such that there exists a unique
$p_{S}\in\mathcal{M}$ with

$\operatorname{dist}(p_{i+1},p_{S})\leq
x_{1}\delta+x_{2}\operatorname{dist}(p_{i},p_{S})\ \ \ \text{ for all }i\geq
0\ .$

Then for
$n\geq\frac{\ln\left(\operatorname{dist}(p_{0},p_{S})/\delta\right)}{\ln(1/(x_{1}+x_{2}))}$,
it holds that $\operatorname{dist}(p_{n},p_{S})\leq\delta$.

###### Proof.

We see this via the following case distinction. Let $i\geq 0$ be arbitrary.

Case 1: _$\operatorname{dist}(p_{i},p_{S})\geq\delta$._
Then

$\operatorname{dist}(p_{i+1},p_{S})\leq\operatorname{dist}(p_{i},p_{S})(x_{1}+x_{2})\
.$

Case 2: _$\operatorname{dist}(p_{i},p_{S}) <\delta$._
Then

$\operatorname{dist}(p_{i+1},p_{S})\leq\delta(x_{1}+x_{2})\ .$

By this case distinction, via induction we get that
$\operatorname{dist}(p_{i},p_{S})\leq\max((x_{1}+x_{2})^{i}\operatorname{dist}(p_{0},p_{S}),\delta)$.
In particular for
$n=\frac{\ln\left(\operatorname{dist}(p_{0},p_{S})/\delta\right)}{\ln(1/(x_{1}+x_{2}))}$
it holds that

$\operatorname{dist}(p_{n},p_{S})\leq\max((x_{1}+x_{2})^{n}\operatorname{dist}(p_{0},p_{S}),\delta)\leq\delta\
.$

∎

###  Appendix E Proofs for Delayed Repeated Retraining (DRR) (Section 4)

####  E.1 DRR in the Exact Setting (Theorem 3)

We show a more general version of the Theorem 3.

######  Theorem 10.

Suppose Assumption 1 holds and $\lambda>\frac{2\iota\phi}{1-\epsilon}$, where
$\phi:=\max(\alpha,\beta)$ and $\alpha,\beta$ as in Definition 4. Then with
$d_{i}$ being calculated by DRR in the exact setting, with
$k=\ln^{-1}\left(\frac{1}{\epsilon}\right)\ln\left(\frac{\operatorname{d}_{P,r}}{\delta\iota}\right)$,
it holds that

$\left\lVert d_{i}-d_{S}\right\rVert_{2}\leq\delta\text{\quad for all
}i\geq\ln\left(\frac{\left\lVert
d_{0}-d_{S}\right\rVert_{2}}{\delta}\right)/\ln\left(\frac{\lambda(1-\epsilon)}{2\phi\iota}\right)\
.$

We first discuss how Theorem 3 follows from Theorem 10. Assumption 2 ensures
that $\beta\geq\alpha$, $\epsilon_{p}=\epsilon_{r}=\epsilon$ and
$\iota\leq\epsilon$. We bound $\left\lVert
d_{0}-d_{S}\right\rVert_{2}\leq\frac{2}{1-\gamma}$. Choosing
$\lambda=2e\iota\beta(1-\epsilon)^{-1}$ then provides the desired bounds.

For proving Theorem 10, we use arguments similar to the ones Brown et al.
[2022] use for proving Theorem 8.

###### Proof of Theorem 10.

Let $P_{0}$ and $r_{0}$ be some arbitrary initial probability transition and
reward function respectively. Denote by $(\tilde{P}_{d},\tilde{r}_{d})$ the
transition probability and reward function after $k$ repeated deployments of
$d$.

Note that $d_{i+1}=\operatorname{GD}(\tilde{P}_{d_{i}},\tilde{r}_{d_{i}})$ and
$d_{S}=\operatorname{GD}(P_{S},r_{S})$.

lemma 1 gives

$\displaystyle\|d_{i+1}-d_{S}\|_{2}$
$\displaystyle=\|\operatorname{GD}(\tilde{P}_{d_{i}},\tilde{r}_{d_{i}})-\operatorname{GD}(P_{S},r_{S})\|_{2}\leq\frac{\alpha}{\lambda}\|\tilde{r}_{d_{i}}-r_{S}\|_{2}+\frac{\beta}{\lambda}\|\tilde{P}_{d_{i}}-P_{S}\|_{2}$
$\displaystyle\leq\frac{\phi}{\lambda}(\operatorname{dist}((\tilde{P}_{d_{i}},\tilde{r}_{d_{i}}),(P_{S},r_{S}))$
(28)

We can decompose

$\displaystyle\operatorname{dist}((\tilde{P}_{d_{i}},\tilde{r}_{d_{i}}),(P_{S},r_{S}))\leq\operatorname{dist}((\tilde{P}_{d_{i}},\tilde{r}_{d_{i}}),(P_{d_{i}},r_{d_{i}}))+\operatorname{dist}((P_{d_{i}},r_{d_{i}}),(P_{S},r_{S}))$
(29)

The first term of 29 can be bounded by lemma 5, the second term by lemma 4:

$\displaystyle\operatorname{dist}((\tilde{P}_{d_{i}},\tilde{r}_{d_{i}}),(P_{S},r_{S}))\leq\frac{\iota}{1-\epsilon}\delta+\frac{\iota}{1-\epsilon}\|d_{i}-d_{S}\|_{2}$
(30)

Using 28 and 30 we get

$\|d_{i+1}-d_{S}\|_{2}\leq\frac{\phi\iota}{\lambda(1-\epsilon)}\delta+\frac{\phi\iota}{\lambda(1-\epsilon)}\|d_{i}-d_{S}\|_{2}$
(31)

We can apply lemma 3 on $\\{d_{i}\\}_{i\in\mathbb{N}}$, since
$\frac{2\phi\iota}{\lambda(1-\epsilon)}<1$ holds due to the assumptions on
$\lambda$. Lemma 3, bounds the number of iterations until $d_{i}$ converges to
a $\delta$ radius around $d_{S}$ and the statement of the theorem follows from
this bound. ∎

We now describe and prove the lemmas used in the proof of Theorem 10.

######  Lemma 4 (similar to lemma 3 of Brown et al. [2022]).

Suppose Assumption 1 holds.

Let $d,d^{\prime}\in D$ be arbitrary occupancy measures and let
$P:=P_{d},r:=r_{d}$ (and respectively
$P^{\prime}:=P_{d^{\prime}},r^{\prime}:=r_{d^{\prime}}$) be the probability
transition and reward functions to which the system asymptotically converges,
if $d$ (respectively $d^{\prime}$) is applied repeatedly. It holds that

$\displaystyle\|P-P^{\prime}\|_{2}+\|r-r^{\prime}\|_{2}\leq\frac{\iota}{1-\max(\epsilon_{p},\epsilon_{r})}\|d-d^{\prime}\|_{2}$
(32)

###### Proof.

Because of Assumption 1, it holds that

$\displaystyle\|P-P^{\prime}\|_{2}+\|r-r^{\prime}\|_{2}$
$\displaystyle=\|\mathcal{P}(d,P,r)-\mathcal{P}(d^{\prime},P^{\prime},r^{\prime})\|_{2}+\|\mathcal{R}(d,P,r)-\mathcal{R}(d^{\prime},P^{\prime},r^{\prime})\|_{2}$
$\displaystyle\leq\iota\|d-d^{\prime}\|_{2}+\epsilon_{p}\|P-P^{\prime}\|_{2}+\epsilon_{r}\|r-r^{\prime}\|_{2}$
$\displaystyle\leq\iota\|d-d^{\prime}\|_{2}+\max(\epsilon_{p},\epsilon_{r})(\|P-P^{\prime}\|_{2}+\|r-r^{\prime}\|_{2})$

Where the equality holds because $(P,r)$ and $(P^{\prime},r^{\prime})$ are the
long-term transition probabilities and reward functions for $d$ and
$d^{\prime}$ respectively. The inequality holds because of Assumption 1.

The statement of the lemma follows from this equation. ∎

######  Lemma 5 (similar to lemma 4 of Brown et al. [2022]).

Assume Assumption 1 holds with $\epsilon_{p},\epsilon_{r}<1$. Given a policy
$\pi$, denote by $(\tilde{P}_{\pi},\tilde{r}_{\pi})$ the transition
probability and reward function after
$k=\ln^{-1}(\frac{1}{\epsilon})\ln\left(\frac{\operatorname{dist}((P_{0},r_{0}),(P_{1},r_{1}))}{\nu}\right)$
deployments of $\pi$, for any initial probability transition function $P_{0}$
and reward function $r_{0}$. It holds that

$\left\lVert P_{\pi}-\tilde{P}_{\pi}\right\rVert_{2}+\left\lVert
r_{\pi}-\tilde{r}_{\pi}\right\rVert_{2}\leq\frac{\nu}{1-\epsilon}\ .$

###### Proof.

Using Proposition 2, we see that

$\displaystyle\operatorname{dist}((\tilde{P}_{\pi},\tilde{r}_{\pi}),(P_{\pi},r_{\pi}))(1-\epsilon)\leq\epsilon^{k}\operatorname{dist}((P_{0},r_{0}),(P_{\pi},r_{\pi}))(1-\epsilon)$
$\displaystyle\leq$
$\displaystyle\epsilon^{k}\operatorname{dist}((P_{0},r_{0}),(P_{\pi},r_{\pi}))-\epsilon^{k}\operatorname{dist}((P_{1},r_{1}),(P_{\pi},r_{\pi}))$
$\displaystyle\leq$
$\displaystyle\epsilon^{k}\operatorname{dist}((P_{0},r_{0}),(P_{1},r_{1})).$

Therefore

$\displaystyle\operatorname{dist}((\tilde{P}_{\pi},\tilde{r}_{\pi}),(P_{\pi},r_{\pi}))\leq\frac{\epsilon^{k}}{1-\epsilon}\operatorname{dist}((P_{0},r_{0}),(P_{1},r_{1})).$
(33)

Using
$k\geq\ln^{-1}\left(\frac{1}{\epsilon}\right)\ln\left(\frac{\operatorname{dist}((P_{0},r_{0}),(P_{1},r_{1}))}{\nu}\right)$,
we get
$\epsilon^{k}\leq\frac{\nu}{\operatorname{dist}((P_{0},r_{0}),(P_{1},r_{1}))}$.
If we insert this into 33, we get the desired bound. ∎

####  E.2 DRR with Finite Samples (Theorem 4)

We show a more general version of the Theorem 4.

######  Theorem 11.

Let $d_{i}$ be computed by finite sample DRR with
$k=\ln^{-1}\left(\frac{1}{\epsilon}\right)\ln\left(\frac{5\operatorname{d}_{P,r}}{\delta\iota}\right)$.
Suppose Assumption 1 holds and Assumption 3 holds for $k$ and parameter $B$.
Furthermore assume
$\lambda>\max\left(5.76\xi\mu,\xi\mu+\frac{\iota\phi}{(1-\epsilon)}\left(1+\frac{1}{4.8\xi\mu}\right)\right),$
with $\xi$ as defined above. Furthermore assume that

$\displaystyle m_{i}\geq\frac{1}{\mu^{2}}\Bigg{(}$
$\displaystyle|A|\ln\left(\frac{4i^{2}}{p}\right)+\ln\left(\frac{12|S|}{(1-\gamma)^{2}\mu}\right)$
$\displaystyle+2|A|\ln\left(\frac{\ln\left(\frac{3|S|^{2}|A|B}{(1-\gamma^{2})\mu}\right)}{\mu}\right)\Bigg{)}\
.$

Then for any $\delta>0$, we have

$\left\lVert d_{i}-d_{S}\right\rVert_{2}\leq\delta$ $\quad\text{\quad for all
}i\geq\frac{\ln\left(\frac{\left\lVert
d_{1}-d_{S}\right\rVert_{2}}{\delta}\right)}{\ln\left(\left(\sqrt{\frac{\xi\mu}{\lambda}}+\frac{1.2\iota\phi}{\lambda(1-\epsilon)}\right)^{-1}\right)}+1.$

Here $\mu>0$ can be chosen arbitrarily and defines a trade-off between the
conditions on the number of samples $m_{i}$ and on the regularization factor
$\lambda$.

We first show how Theorem 4 follows from Theorem 11. Assumption 2 ensures that
$\beta\geq\alpha$, $\epsilon_{p}=\epsilon_{r}=\epsilon$, $\iota\leq\epsilon$
and $\beta\geq\alpha$

For Theorem 4, we use $\mu=\frac{\lambda}{10\xi}$. We bound

$\displaystyle\lambda>\max\left(1,\frac{40\iota\beta}{9(1-\epsilon)},\frac{1.2\iota\beta}{(1-\epsilon)\left(\frac{\epsilon}{4}+\frac{3}{4}-\frac{1}{\sqrt{10}}\right)}\right)$

We then derive the bound on $i$ in the following way. For the denominator of
the bound on $i$, we can then derive
$\sqrt{\frac{\xi\mu}{\lambda}}+\frac{1.2\iota\phi}{\lambda(1-\epsilon)}=\frac{1}{\sqrt{10}}+\frac{1.2\iota\beta}{\lambda(1-\epsilon)}\leq\frac{\epsilon+3}{4}$.
For the numerator of the bound on $i$, we use $\left\lVert
d_{1}-d_{S}\right\rVert_{2}\leq\frac{2}{1-\gamma}$.

The bound on the number of samples follows from the fact that
$\frac{1}{\mu^{2}}=\frac{100\xi^{2}}{\lambda^{2}}={\mathcal{O}}\left(\frac{|S|^{3}(B+\sqrt{|A|})^{2}}{\delta^{4}(1-\gamma)^{6}\lambda^{2}}\right)$.

###### Proof of Theorem 11.

In general, we bound

$\displaystyle\|d_{i+1}-d_{S}\|_{2}\leq\underbrace{\|d_{i+1}-d_{i+1}^{*}\|_{2}}_{T_{1}}+\underbrace{\|d_{i+1}^{*}-d_{S}\|_{2}}_{T_{2}}$
(34)

where $d_{i+1}^{*}$ is the occupancy measure optimizing the exact Lagrangian
after $k$ deployments of $\pi_{d_{i}}$, i.e.
$d_{i+1}^{*}=\operatorname{GD}(P_{(i+1)\cdot k},r_{(i+1)\cdot k})$.

We can apply lemma 2, since Assumption 3 holds. Let $F_{t}$ be the samples of
round $t$. By setting $\delta_{1}=p/2i^{2}$ we get with probablility at least
$1-p/2i^{2}$ in step $i$,

$\displaystyle
T_{1}=\left\lVert\widehat{\operatorname{GD}}(d_{i},F_{(i+1)\cdot
k})-\operatorname{GD}(P_{(i+1)\cdot k},r_{(i+1)\cdot
k})\right\rVert_{2}\leq\frac{6\sqrt{|S|^{1.5}(B+\sqrt{|A|})\mu}}{(1-\gamma)^{1.5}}\frac{1}{\sqrt{\lambda}},$
(35)

if

$\displaystyle\left|F_{(i+1)\cdot
k}\right|\geq\frac{1}{\mu^{2}}\left(|A|\ln(4i^{2}/p)+\ln(12|S|/((1-\gamma)^{2}\mu))+2|A|\ln(\ln(3|S|^{2}|A|B/((1-\gamma^{2})\mu))/\mu)\right)$

By a union bound over all rounds, we get that (35) holds with probability
$1-p$ for every $i\in\mathbb{N}$.

To bound $T_{2}$, we can apply lemma 7 with parameter $\nu$, to get

$\displaystyle T_{2}=\left\lVert
d_{i+1}^{*}-d_{S}\right\rVert_{2}\leq\frac{\phi\nu}{\lambda(1-\epsilon)}+\frac{\phi\iota}{\lambda(1-\epsilon)}\left\lVert
d_{i}-d_{S}\right\rVert_{2}\ .$

We determine $\nu$ later in the proof.

Inserting those bounds on $T_{1}$ and $T_{2}$ into (34), we get

$\displaystyle\|d_{i+1}-d_{S}\|_{2}$
$\displaystyle\leq\frac{6\sqrt{|S|^{1.5}(B+\sqrt{|A|})\mu}}{(1-\gamma)^{1.5}}\frac{1}{\sqrt{\lambda}}+\frac{\phi\nu}{\lambda(1-\epsilon)}+\frac{\phi\iota}{\lambda(1-\epsilon)}\left\lVert
d_{i}-d_{S}\right\rVert_{2}=x_{1}\delta+x_{2}\left\lVert
d_{i}-d_{S}\right\rVert_{2}$ (36)

where we define
$x_{1}:=\frac{6\sqrt{|S|^{1.5}(B+\sqrt{|A|})\mu}}{(1-\gamma)^{1.5}\sqrt{\lambda}\delta}+\frac{\phi\nu}{\lambda(1-\epsilon)\delta}$
and $x_{2}:=\frac{\phi\iota}{\lambda(1-\epsilon)}$.

Note that we can write $x_{1}+x_{2}$ as follows

$\displaystyle x_{1}+x_{2}$
$\displaystyle=\frac{6\sqrt{|S|^{1.5}(B+\sqrt{|A|})\mu}}{(1-\gamma)^{1.5}\sqrt{\lambda}\delta}+\frac{(\frac{\nu}{\delta}+\iota)\phi}{\lambda(1-\epsilon)}$
(37)

We now derive conditions on $\lambda$ for when $x_{1}+x_{2}<1$, because then
we can apply lemma 3 to bound the iterations until which the sequence of
$\\{d_{i}\\}_{i\in\mathbb{N}_{\geq 1}}$ converges. To this end, we can apply
lemma 6 with $x=\lambda$,
$a=\frac{6\sqrt{|S|^{1.5}(B+\sqrt{|A|})\mu}}{(1-\gamma)^{1.5}\delta}$,
$b=\frac{(\frac{\nu}{\delta}+\iota)\phi}{1-\epsilon}$ and $y=2.4$, to get that
$x_{1}+x_{2}<1$ holds, if

$\lambda>\max\left(5.76a^{2},a^{2}+\frac{(\frac{\nu}{\delta}+\iota)\phi}{1.2(1-\epsilon)}+\frac{(\frac{\nu}{\delta}+\iota)\phi}{2.4^{2}(1-\epsilon)a^{2}}\right)\
.$

We get the bound for $\lambda$ stated in the Theorem by setting
$\nu=0.2\delta\iota$.

Thus we can apply lemma 3 on the sequence $\\{d_{i}\\}_{i\in\mathbb{N}_{\geq
1}}$, to see that if $i\geq\ln\left(\frac{\left\lVert
d_{1}-d_{S}\right\rVert_{2}}{\delta}\right)/\ln\left(1/(x_{1}+x_{2})\right)+1$,
it holds that $\left\lVert d_{i}-d_{S}\right\rVert_{2}\leq\delta$. The Theorem
then follows from substituting $x_{1}+x_{2}$ using equation (37) and
$\nu=0.2\delta\iota$. ∎

For the proof, we used the following lemmas.

######  Lemma 6.

Let $a,b,x\geq 0$ and $y>0$ be arbitrary. If
$x>\max(y^{2}a^{2},a^{2}+\frac{2b}{y}+\frac{b}{y^{2}a^{2}})$, it holds that

$\displaystyle 1>\frac{a}{\sqrt{x}}+\frac{b}{x}\ .$ (38)

###### Proof.

When we multiply both sides of (38) with $\sqrt{x}$ and square the resulting
term, we see that (38) is equivalent to

$\displaystyle x>a^{2}+2\frac{ab}{\sqrt{x}}+\frac{b}{x}\ .$ (39)

If we assume that $x>y^{2}a^{2}$, we get

$a^{2}+2\frac{ab}{\sqrt{x}}+\frac{b}{x}<a^{2}+\frac{2b}{y}+\frac{b}{y^{2}a^{2}}<x,$

This shows that equation 39 and thus also equation 38 hold. ∎

######  Lemma 7.

Suppose Assumption 1 holds with $\iota_{d},\epsilon_{p},\epsilon_{r}<1$. Let
$d$ be some occupancy measure and $P_{0},r_{0}$ be some initial probability
transition and reward functions. Let $P_{t},r_{t}$ be the probability
transition and reward function after $t>0$ deployments of $\pi_{d}$. Then for
$d^{\prime}=\operatorname{GD}(P_{k},r_{k})$ with
$k=\ln^{-1}\left(\frac{1}{\epsilon}\right)\ln\left(\frac{\operatorname{dist}((P_{0},r_{0}),(P_{1},r_{1}))}{\nu}\right)$,
it holds that

$\left\lVert
d^{\prime}-d_{S}\right\rVert\leq\frac{\phi\nu}{\lambda(1-\epsilon)}+\frac{\phi\iota}{\lambda(1-\epsilon)}\left\lVert
d-d_{S}\right\rVert_{2}\ ,$

where $\phi=\max(\alpha,\beta)$ and $\alpha,\beta$ from Definition 4.

###### Proof.

Note that

$\displaystyle\left\lVert d^{\prime}-d_{S}\right\rVert_{2}\leq\left\lVert
d^{\prime}-\operatorname{GD}(P_{d},r_{d})\right\rVert_{2}+\left\lVert\operatorname{GD}(P_{d},r_{d})-d_{S}\right\rVert_{2}$
(40)

Using lemmas 1 and 5, we can bound

$\displaystyle\left\lVert
d^{\prime}-\operatorname{GD}(P_{d},r_{d})\right\rVert_{2}\leq\frac{\phi}{\lambda}\operatorname{dist}((P_{k},r_{k}),(P_{d},r_{d}))\leq\frac{\phi\nu}{\lambda(1-\epsilon)}\
.$ (41)

Furthermore, by lemmas 1 and 4 we see that

$\displaystyle\left\lVert\operatorname{GD}(P_{d},r_{d})-d_{S}\right\rVert_{2}\leq\frac{\phi}{\lambda}\operatorname{dist}((P_{d},r_{d}),(P_{S},r_{S}))\leq\frac{\phi\iota}{\lambda(1-\epsilon)}\left\lVert
d-d_{S}\right\rVert_{2}\ .$ (42)

Inserting (41) and (42) into (40) gives the desired bound. ∎

###  Appendix F Proof for MDRR (Theorem 5)

####  F.1 Preparations for the Proof

For our derivations, we need an exact version of the empirical Lagrangian (9).
To this end, consider the following optimization problem, which works with
multiple reward and probability transition functions from different rounds.

$\displaystyle\max_{d\geq 0}\ $
$\displaystyle\sum_{s,a}d(s,a)\overline{r}_{i}(s,a)-\frac{\lambda}{2}\left\lVert
d\right\rVert_{2}^{2}$ (43) s.t.
$\displaystyle\sum_{a}d(s,a)=\rho(s)+\gamma\cdot\sum_{s^{\prime},a}d(s^{\prime},a)\overline{P}_{i}(s^{\prime},a,s)\
\forall s$

where we define
$\overline{r}_{i}:=\sum_{t=1}^{k}\frac{m_{ik+t}}{U_{i}}r_{ik+t}$ and
$\overline{P}_{i}:=\sum_{t=1}^{k}\frac{m_{ik+t}}{U_{i}}P_{ik+t}$ where
$m_{ik+t}\geq 0$ is arbitrary and $U_{i}=\sum_{t=1}^{k}m_{ik+t}$. Equation
(43) defines an objective for a mixture of probability transition and reward
functions of the rounds in which the learner repeatedly deployed
$\pi_{d_{i}}$. Each reward and probability transition is weighted by a weight
$\frac{m_{ik+t}}{U_{i}}$. This optimization problem does not use finite
samples, but the true reward and probability transition functions.

We can now show that the Lagrangian of (43) looks similar to the empirical
Lagrangian (9) of MDRR.

$\displaystyle{\mathcal{L}}^{M}(d,h,i)=d^{\top}\overline{r}_{i}-\frac{\lambda}{2}\left\lVert
d\right\rVert_{2}^{2}+\sum_{s}h(s)\bigg{(}-\sum_{a}d(s,a)+\rho(s)+\gamma\cdot\sum_{s^{\prime},a}d(s^{\prime},a)\overline{P}_{i}(s|s^{\prime},a)\bigg{)}$
$\displaystyle=d^{\top}\sum_{t=1}^{k}\frac{m_{ik+t}}{U_{i}}{r}_{i}^{t}-\frac{\lambda}{2}\left\lVert
d\right\rVert_{2}^{2}+\sum_{s}h(s)\bigg{(}-\sum_{a}d(s,a)+\rho(s)+\gamma\cdot\sum_{s^{\prime},a}d(s^{\prime},a)\sum_{t=1}^{k}\frac{m_{ik+t}}{U_{i}}{P}_{i\cdot
k+t}(s|s^{\prime},a)\bigg{)}$ $\displaystyle=-\frac{\lambda}{2}\left\lVert
d\right\rVert_{2}^{2}+\sum_{s}h(s)\rho(s)+\sum_{t=1}^{k}\sum_{s,a}\frac{m_{ik+t}}{U_{i}}d(s,a)\bigg{(}r_{ik+t}(s,a)-h(s)+\gamma\sum_{s^{\prime}}P_{i\cdot{}k+t}(s^{\prime}|s,a)h(s^{\prime})\bigg{)}$
$\displaystyle\begin{split}&=-\frac{\lambda}{2}\left\lVert
d\right\rVert_{2}^{2}+\sum_{s}h(s)\rho(s)+\sum_{t=1}^{k}\sum_{s,a}\overline{d}_{ik+t}(s,a)\frac{m_{ik+t}}{U_{i}}\frac{d(s,a)}{\overline{d}_{ik+t}(s,a)}\bigg{(}r_{ik+t}(s,a)-h(s)+\gamma\sum_{s^{\prime}}P_{i\cdot{}k+t}(s^{\prime}|s,a)h(s^{\prime})\bigg{)}\end{split}$
(44)

We then show a kind of closeness of ${\mathcal{L}}^{M}$ and
$\hat{{\mathcal{L}}}^{M}$ in the following lemma. The lemma is a more general
version of lemma 10 from Mandal et al. [2023]. The proof ideas follow theirs.

######  Lemma 8.

Suppose we are given an occupancy measure $d$ with
$\max_{s,a}d(s,a)/\overline{d}_{ik+t}(s,a)\leq B$ for all $t\in[k]$, an
$\left\lVert h\right\rVert_{2}\leq H$ and $m_{ik+t}=w_{t}U_{i}$ with
$U_{i}\geq\frac{1}{\eta^{2}}\left(|A|\ln\left(\frac{2\ln(|S||A|BH/\eta)}{\eta}\right)+\ln\left(1+\frac{2H}{\eta}\right)+\frac{\ln\left(2/\delta_{1}\right)}{|S|}\right)$.
Furthermore assume $w_{t}\geq 0$ and $\sum_{t=1}^{k}w_{t}=1$. Then the
following bound holds with probability at least $1-\delta_{1}$.

$\displaystyle\left|\hat{{\mathcal{L}}}^{M}(d,h;i)-{\mathcal{L}}^{M}(d,h;i)\right|\leq\frac{6(H+1)\sqrt{|S|}(B+\sqrt{|A|})\eta}{1-\gamma}\
.$

for any $\eta>0$.

###### Proof.

For this proof to simplify notation, we drop the ‘$i\cdot k$’ in the
subscript, and only use $t$, since we always consider the same iteration $i$.

Note that $\frac{m^{t}}{M}=w_{t}$.

We see that the expected value of the $\hat{{\mathcal{L}}}^{M}$ equals
${\mathcal{L}}^{M}$ as follows

$\displaystyle\mathbb{E}[\hat{{\mathcal{L}}}^{M}(d,h,i)]$ $\displaystyle=$
$\displaystyle-\frac{\lambda}{2}\left\lVert
d\right\rVert_{2}^{2}+\sum_{s}h(s)\rho(s)+\sum_{t=1}^{k}\sum_{l=1}^{\left|F_{t}\right|}\frac{1}{\left|F_{t}\right|}w_{t}\mathbb{E}_{(s,a,s^{\prime})\sim
M^{t}}\left[\frac{d(s,a)}{\overline{d}_{t}(s,a)}\cdot\frac{r_{t}(s,a)-h(s)+\gamma
h(s^{\prime})}{1-\gamma}\right]$ $\displaystyle=$
$\displaystyle-\frac{\lambda}{2}\left\lVert
d\right\rVert_{2}^{2}+\sum_{s}h(s)\rho(s)+\sum_{t=1}^{k}\sum_{s,a}\overline{d}_{t}(s,a)w_{t}\frac{d(s,a)}{\overline{d}_{t}(s,a)}\left(r_{t}(s,a)-h(s)+\gamma\sum_{s^{\prime}}P_{t}(s^{\prime}|s,a)h(s^{\prime})\right)$
$\displaystyle=$ $\displaystyle{\mathcal{L}}^{M}(d,h,i)$

where we use the notation $(s,a,s^{\prime})\sim M^{t}$ to indicate that the
tuple $(s,a,s^{\prime})$ is distributed via the MDP in round $t$ of this
iteration.

By the assumptions of this lemma, we see that

$\displaystyle\left|\frac{1}{1-\gamma}\frac{d(s,a)}{\overline{d}_{t}(s,a)}(r_{t}(s,a)-h(s)+\gamma
h(s^{\prime}))\right|\leq\frac{B(H(1+\gamma)+1)}{1-\gamma}$

By this, we can apply Hoeffding’s inequality to get

$\displaystyle\mathbb{P}\left(\left|\hat{\mathcal{L}}(d,h,i)-{\mathcal{L}}(d,h,i)\right|\geq\frac{2B(H(1+\gamma)+1)}{1-\gamma}\sqrt{\sum_{t=1}^{k}\frac{w_{t}^{2}}{m_{t}}\frac{\ln(2/\delta_{1})}{2}}\right)\leq\delta_{1}$

We now extend this bound to any occupancy measure $d$ and
$h\in\mathcal{H}=\\{h:\left\lVert h\right\rVert_{2}\leq H\\}$. In order to do
this, we first construct an $\eta$-net for the set of possible $h$s,
$\mathcal{H}:=\\{h\in\mathbb{R}^{|S|}:\left\lVert h\right\rVert_{2}\leq H\\}$
and for the set of possible occupancy measures $\mathcal{D}$ which formally
equals $\mathcal{D}=\left\\{d:\frac{d(s,a)}{\overline{d}_{t}(s,a)}\leq B\ \
\text{for all}\ (s,a,t)\in|S|\times|A|\times[k]\right\\}$.

For $\mathcal{H}$, we can use lemma 5.2 from Vershynin [2010] to get a set
$\mathcal{H}_{\eta}$ of size at most $\left(1+\frac{2H}{\eta}\right)^{|S|}$,
such that for all $h\in\mathcal{H}$, there exists an
$h_{\eta}\in\mathcal{H}_{\eta}$ for which it holds that $\left\lVert
h-h_{\eta}\right\rVert_{2}\leq\eta$.

For $\mathcal{D}$ we choose a multiplicative $\eta$-net as follows. For each
pair $(s,a)$ we choose grid points $\overline{d}_{t}(s,a)$,
$(1+\eta)\overline{d}_{t}(s,a)$, …, $(1+\eta)^{p}\overline{d}_{t}(s,a)$ with
$p=\frac{\ln(B/\overline{d}_{t}(s,a))}{\ln(1+\eta)}$. Note that
$\overline{d}_{t}$ could be arbitrarily small, but without loss of generality,
we can assume that $\overline{d}_{t}(s,a)\geq\frac{\eta}{4|S||A|BH}$. This is
because if we ignore all $(s,a,t)$ tuples in the sum in the second line of
term (44), the error we introduce to ${\mathcal{L}}^{M}$ is at most $\eta/4$.
Using this insight, we can thus choose
$p=\frac{2\ln(|S||A|BH/\eta)}{\ln(1+\eta)}$. So we can choose an $\eta$-net
$\mathcal{D}_{\eta}$ of size at most
$\left(\frac{2\ln(|S||A|BH/\eta)}{\ln(1+\eta)}\right)^{|S||A|}\leq\left(\frac{2\ln(|S||A|BH/\eta)}{\eta}\right)^{|S||A|}$,
such that for every $d\in\mathcal{D}$, there exists an
$\tilde{d}\in\mathcal{D}_{\eta}$ such that $\frac{d(s,a)}{\tilde{d}(s,a)}\leq
B$.

With a union bound over the elements of $\mathcal{H}_{\eta}$ and
$\mathcal{D}_{\eta}$, we have that for all $d\in{\mathcal{D}}_{\eta}$ and
$h\in{\mathcal{H}}_{\eta}$,

$\displaystyle\begin{split}&\mathbb{P}\Bigg{(}\left|\hat{\mathcal{L}}^{M}(d,h,i)-{\mathcal{L}}^{M}(d,h,i)\right|\\\
&\geq\frac{B(H(1+\gamma)+1)}{1-\gamma}\sqrt{\sum_{t=1}^{k}\frac{w_{t}^{2}}{m_{t}}\left(|S||A|\ln\left(\frac{2\ln(|S||A|BH/\eta)}{\eta}\right)+|S|\ln\left(1+\frac{2H}{\eta}\right)+\ln\left(\frac{2}{\delta_{1}}\right)\right)}\Bigg{)}\leq\delta_{1}\end{split}$
(45)

We next extend this bound to all elements in ${\mathcal{D}}$ and
${\mathcal{H}}$. For every $d\in{\mathcal{D}}$ and $h\in{\mathcal{H}}$ there
exits $\tilde{d}\in{\mathcal{D}}_{\eta}$ and
$\tilde{h}\in{\mathcal{H}}_{\eta}$ such that
$\max_{s,a}d(s,a)/\tilde{d}(s,a)\leq\eta$ and $\left\lVert
h-\tilde{h}\right\rVert_{2}\leq\eta$. Let
${\mathcal{L}}^{M}_{0}(d,h;i)={\mathcal{L}}^{M}(d,h;i)+\frac{\lambda}{2}\left\lVert
d\right\rVert_{2}^{2}-\sum_{s}h(s)\rho(s)$ and
$\hat{\mathcal{L}}_{0}^{M}(d,h;i)$ analogously.

Then

$\displaystyle\begin{split}&\left|\hat{{\mathcal{L}}}^{M}(d,h;i)-{\mathcal{L}}^{M}(d,h;i)\right|\leq\left|\hat{{\mathcal{L}}}_{0}^{M}(d,h;i)-\hat{{\mathcal{L}}}^{M}_{0}(\tilde{d},\tilde{h};i)\right|\\\
&+\left|\hat{{\mathcal{L}}}^{M}(\tilde{d},\tilde{h};i)-{\mathcal{L}}^{M}(\tilde{d},\tilde{h};i)\right|+\left|{{\mathcal{L}}}_{0}^{M}(\tilde{d},\tilde{h};i)-{{\mathcal{L}}}_{0}^{M}({d},{h};i)\right|\end{split}$
(46)

Using lemma 11 from Mandal et al. [2023] we can bound

$\displaystyle\left|\hat{{\mathcal{L}}}^{M}_{0}(d,h;i)-\hat{{\mathcal{L}}}^{M}_{0}(\tilde{d},\tilde{h};i)\right|=$
$\displaystyle\sum_{t=1}^{k}w_{t}\Bigg{|}\Bigg{(}\sum_{(s,a,r,s^{\prime})\in
F_{t}}\frac{d(s,a)}{\overline{d}_{t}(s,a)}\frac{r-h(s)+\gamma\sum_{s^{\prime}}h(s^{\prime})}{m^{t}(1-\gamma)}$
$\displaystyle-\sum_{(s,a,r,s^{\prime})\in
F_{t}}\frac{\tilde{d}(s,a)}{\overline{d}_{t}(s,a)}\frac{r-\tilde{h}(s)+\gamma\sum_{s^{\prime}}\tilde{h}(s^{\prime})}{m^{t}(1-\gamma)}\Bigg{)}\Bigg{|}$
$\displaystyle\leq$ $\displaystyle\frac{4BH\sqrt{|S|}\eta}{1-\gamma}$

and

$\displaystyle\left|{{\mathcal{L}}}_{0}^{M}(d,h;i)-{{\mathcal{L}}}_{0}^{M}(\tilde{d},\tilde{h};i)\right|=$
$\displaystyle\Bigg{|}\sum_{s,a}d(s,a)\Bigg{(}\underbrace{\sum_{t=1}^{k}w_{t}r_{t}(s,a)}_{=\overline{r}(s,a)}-h(s)+\gamma\sum_{s^{\prime}}h(s^{\prime})\underbrace{\sum_{t=1}^{k}w_{t}P_{t}(s^{\prime}|s,a)}_{=\overline{P}(s^{\prime}|s,a)}\Bigg{)}$
$\displaystyle-\sum_{s,a}\tilde{d}(s,a)\Bigg{(}\underbrace{\sum_{t=1}^{k}w_{t}r_{t}(s,a)}_{=\overline{r}(s,a)}-\tilde{h}(s)+\gamma\sum_{s^{\prime}}\tilde{h}(s^{\prime})\underbrace{\sum_{t=1}^{k}w_{t}P_{t}(s^{\prime}|s,a)}_{=\overline{P}(s^{\prime}|s,a)}\Bigg{)}\Bigg{|}$
$\displaystyle\leq$ $\displaystyle\frac{6\sqrt{|S||A|}H\eta}{1-\gamma}\ .$

Inserting these bounds and the bound from (45) into (46), we get

$\displaystyle\left|\hat{{\mathcal{L}}}^{M}(d,h;i)-{\mathcal{L}}^{M}(d,h;i)\right|\leq$
$\displaystyle\frac{B(H(1+\gamma)+1)}{1-\gamma}\sqrt{\sum_{t=1}^{k}\frac{w_{t}^{2}}{m_{t}}\left(|S||A|\ln\left(\frac{2\ln(|S||A|BH/\eta)}{\eta}\right)+|S|\ln\left(1+\frac{2H}{\eta}\right)+\ln\left(\frac{2}{\delta_{1}}\right)\right)}$
$\displaystyle+\frac{4BH\sqrt{|S|}\eta}{1-\gamma}+\frac{6\sqrt{|S||A|}H\eta}{1-\gamma}$

In particular, if we use $m_{ik+t}=U_{i}w_{t}$, we get

$\displaystyle\left|\hat{{\mathcal{L}}}^{M}(d,h;i)-{\mathcal{L}}^{M}(d,h;i)\right|\leq$
$\displaystyle\frac{2B(H+1)}{1-\gamma}\sqrt{\frac{1}{U_{i}}\left(|S||A|\ln\left(\frac{2\ln(|S||A|BH/\eta)}{\eta}\right)+|S|\ln\left(1+\frac{2H}{\eta}\right)+\ln\left(\frac{2}{\delta_{1}}\right)\right)}$
$\displaystyle+\frac{4BH\sqrt{|S|}\eta}{1-\gamma}+\frac{6\sqrt{|S||A|}H\eta}{1-\gamma}$

If we now choose
$U_{i}\geq\frac{1}{\eta^{2}}\left(|A|\ln\left(\frac{2\ln(|S||A|BH/\eta)}{\eta}\right)+\ln\left(1+\frac{2H}{\eta}\right)+\frac{\ln\left(2/\delta_{1}\right)}{|S|}\right)$,
we get

$\displaystyle\left|\hat{{\mathcal{L}}}^{M}(d,h;i)-{\mathcal{L}}^{M}(d,h;i)\right|\leq\frac{6(H+1)\sqrt{|S|}(B+\sqrt{|A|})\eta}{1-\gamma}\
.$

∎

We need some further definitions and then go on to show the theorem on MDRR.

######  Definition 7.

We define $\operatorname{MR}_{\bm{w}}^{k}\left(d_{i},P_{i\cdot k},r_{i\cdot
k}\right)$ to be the solution to (43).

Furthermore we define
$\widehat{\operatorname{MR}}_{\bm{w}}^{k}\left(d_{i},P_{i\cdot k},r_{i\cdot
k}\right)$ to be the occupancy measure $d$ optimizing the empirical Lagrangian
for MDRR, i.e.

$\displaystyle\max_{d}\min_{h}\hat{{\mathcal{L}}}^{M}(d,h,i)\ .$ (47)

After deploying $\pi_{d_{i}}$ for $k$ rounds, the learner updates its
occupancy measure by
$d_{i+1}=\widehat{\operatorname{MR}}_{\bm{w}}^{k}\left(d_{i},P_{i\cdot
k},r_{i\cdot k}\right)$.

####  F.2 Formal Statement and Proof of Theorem 5 (MDRR)

We now show a more general version of the Theorem 5.

######  Theorem 12.

Let $d_{i}$ be computed by MDRR with
$k\geq\frac{\ln\left(\frac{\epsilon(v-1)}{v\epsilon-1}\right)+\ln\left(\frac{5(1-\epsilon)\operatorname{d}_{P,r}}{\iota\delta}\right)}{\ln\left(1/\epsilon\right)}$.
Suppose Assumption 1 holds and Assumption 3 holds for $k$ and parameter $B$.
Furthermore assume that
$\lambda>\max\left(6.08\xi\eta,\frac{19}{18}\xi\eta+\frac{\phi\iota}{1-\epsilon}\left(1+\frac{1}{5.0\overline{6}\xi\eta}\right)\right)$
with $\xi$ being defined as above.

Further let
$U_{i}\geq\frac{1}{\eta^{2}}\bigg{(}|A|\ln\bigg{(}\frac{2\ln(|S||A|BH/\eta)}{\eta}\bigg{)}+\ln\bigg{(}1+\frac{2H}{\eta}\bigg{)}+\frac{\ln(4i^{2}/p)}{|S|}\bigg{)}$
be the total number of samples in round $i$, where the number of samples is
given by $m_{ik+t}=w_{t}U_{i}$ with $w_{t}=\frac{v-1}{v^{k}-1}v^{t-1}$ and
$v>\frac{1}{\epsilon}$. Then for any $\delta>0$ and $p>0$, with probability at
least $1-p$,

$\left\lVert d_{i}-d_{S}\right\rVert_{2}\leq\delta$ $\text{\quad for all
}i\geq\frac{\ln(\left\lVert
d_{1},d_{S}\right\rVert_{2}/\delta)}{\ln\left(1/\left(\sqrt{\frac{19\xi\eta}{18\lambda}}+\frac{1.2\phi\iota}{\lambda(1-\epsilon)}\right)\right)}+1\
.$

Here $\eta>0$ and $v>\frac{1}{\epsilon}$ can be chosen arbitrarily.

The parameter $\eta>0$ defines a trade-off between the number of samples,
number of iterations and the conditions on $\lambda$. The parameter
$v>\frac{1}{\epsilon}$ defines a trade-off between the number of deployments
per retraining and the required number of samples per deployment.

We first explain how Theorem 5 follows from Theorem 12. Assumption 2 ensures
that $\beta\geq\alpha$, $\epsilon_{p}=\epsilon_{r}=\epsilon$,
$\iota\leq\epsilon$ and $\beta\geq\alpha$. For Theorem 5, we use
$\eta=\frac{\lambda}{10\xi}$ and
$\lambda>\max\left(1,3.6\frac{\beta\iota}{1-\epsilon},\frac{1.2\beta\iota}{(1-\epsilon)\left(\frac{\epsilon+3}{4}-\sqrt{\frac{19}{180}}\right)}\right)$.
We now bound
$\sqrt{\frac{19\xi\eta}{18\lambda}}+\frac{1.2\phi\iota}{\lambda(1-\epsilon)}$
in order to bound the number of retrainings $i$. We see that

$\displaystyle\sqrt{\frac{19\xi\eta}{18\lambda}}+\frac{1.2\beta\iota}{\lambda(1-\epsilon)}=\sqrt{\frac{19}{180}}+\frac{1.2\beta\iota}{\lambda(1-\epsilon)}<\frac{\epsilon+3}{4}\
.$

where in the inequality, we use
$\lambda>\frac{1.2\beta\iota}{(1-\epsilon)\left(\frac{\epsilon+3}{4}-\sqrt{\frac{19}{180}}\right)}$.

Inserting the bounds on $\lambda$ and $\eta$, we get the results described in
Theorem 5.

###### Proof of Theorem 12.

In general, we bound

$\displaystyle\left\lVert d_{i+1}-d_{S}\right\rVert_{2}\leq$
$\displaystyle\underbrace{\left\lVert\widehat{\operatorname{MR}}_{\bm{w}}^{k}(d_{i},P_{ik},r_{ik})-\operatorname{MR}_{\bm{w}}^{k}(d_{i},P_{ik},r_{ik})\right\rVert_{2}}_{T_{1}}$
$\displaystyle+\underbrace{\left\lVert\operatorname{MR}_{\bm{w}}^{k}(d_{i},P_{ik},r_{ik})-\operatorname{GD}(P_{d_{i}},r_{d_{i}})\right\rVert_{2}}_{T_{2}}+\underbrace{\left\lVert\operatorname{GD}(P_{d_{i}},r_{d_{i}})-d_{S}\right\rVert_{2}}_{T_{3}}$

where $d_{S}$ is some stable occupancy measure.

We begin by bounding $T_{1}$. For this we argue similarly to the proof of
Theorem 3 in Mandal et al. [2023].

Let $\hat{h}_{i+1}$ be the dual solution to $\hat{{\mathcal{L}}}^{M}$
corresponding to
$\widehat{\operatorname{MR}}_{\bm{w}}^{k}(d_{i},P_{ik},r_{ik})$. I.e.

$(\widehat{\operatorname{MR}}_{\bm{w}}^{k}(d_{i},P_{ik},r_{ik}),\hat{h}_{i+1})=\operatorname*{arg\,max}_{d}\operatorname*{arg\,min}_{h}\hat{{\mathcal{L}}}^{M}(d,h;i)$

By strong duality, there has to exist a $h_{i+1}$ such that

$(\operatorname{MR}_{\bm{w}}^{k}(d_{i},P_{ik},r_{ik}),h_{i+1})=\operatorname*{arg\,max}_{d}\operatorname*{arg\,min}_{h}{\mathcal{L}}^{M}(d,h;i)$

Using lemma 4 of Mandal et al. [2023], we can bound the $L_{2}$-norms of the
dual solutions $\hat{h}_{i+1}$ and $h_{i+1}$ by $\frac{3|S|}{(1-\gamma)^{2}}$.
We can thus consider the restricted set ${\mathcal{H}}=\left\\{h:\left\lVert
h\right\rVert_{2}\leq\frac{3|S|}{(1-\gamma)^{2}}\right\\}$. Then because
Assumption 3 holds, we can apply lemma 8 with $\delta_{1}=p/2i^{2}$ and
$H=3|S|/(1-\gamma)^{2}$ to get,

$\displaystyle\left|\hat{\mathcal{L}}^{M}(d_{i+1},h_{i+1};i)-{\mathcal{L}}^{M}(d_{i+1},h_{i+1};i)\right|\leq\frac{19|S|^{1.5}(B+\sqrt{|A|})\eta}{(1-\gamma)^{3}}$
(48)

if

$U_{i}\geq\frac{1}{\eta^{2}}\left(|A|\ln\left(\frac{2\ln(|S||A|BH/\eta)}{\eta}\right)+\ln\left(1+\frac{2H}{\eta}\right)+\frac{\ln\left(4i^{2}/p\right)}{|S|}\right)\
.$

Note that event (48) holds with probability at least $1-\frac{p}{2i^{2}}$. By
a union bound over all rounds, the event holds with probability at least $1-p$
for all rounds.

The objective ${\mathcal{L}}^{M}(\cdot,h_{i+1},i)$ is $\lambda$-strongly
concave. Therefore, we have

$\displaystyle{\mathcal{L}}^{M}(\widehat{\operatorname{MR}}_{\bm{w}}^{k}(d_{i},P_{ik},r_{ik}),h_{i+1};i)-{\mathcal{L}}^{M}(\operatorname{MR}_{\bm{w}}^{k}(d_{i},P_{ik},r_{ik}),h_{i+1})$
$\displaystyle\leq$
$\displaystyle-\frac{\lambda}{2}\left\lVert\widehat{\operatorname{MR}}_{\bm{w}}^{k}(d_{i},P_{ik},r_{ik})-\operatorname{MR}_{\bm{w}}^{k}(d_{i},P_{ik},r_{ik})\right\rVert_{2}^{2}$

We therefore find by rearranging and using lemma 12 from Mandal et al. [2023],

$\displaystyle
T_{1}=\left\lVert\widehat{\operatorname{MR}}_{\bm{w}}^{k}(d_{i},P_{ik},r_{ik})-\operatorname{MR}_{\bm{w}}^{k}(d_{i},P_{ik},r_{ik})\right\rVert_{2}$
$\displaystyle\leq$
$\displaystyle\sqrt{\frac{2\left({\mathcal{L}}^{M}({\operatorname{MR}}_{\bm{w}}^{k}(d_{i},P_{ik},r_{ik}),h_{i+1};i)-{\mathcal{L}}^{M}(\widehat{\operatorname{MR}}_{\bm{w}}^{k}(d_{i},P_{ik},r_{ik}),h_{i+1};i)\right)}{\lambda}}$
$\displaystyle\leq$
$\displaystyle\frac{\sqrt{38|S|^{1.5}(B+\sqrt{|A|})\eta}}{(1-\gamma)^{1.5}}\frac{1}{\sqrt{\lambda}}$

We now bound $T_{2}$ using lemma 1

$\displaystyle T_{2}$
$\displaystyle=\left\lVert\operatorname{MR}_{\bm{w}}^{k}(d_{i},P_{ik},r_{ik})-\operatorname{GD}(P_{d_{i}},r_{d_{i}})\right\rVert_{2}=\left\lVert\operatorname{GD}(\overline{P}_{i},\overline{r}_{i})-\operatorname{GD}(P_{d_{i}},r_{d_{i}})\right\rVert_{2}$
$\displaystyle\leq\frac{\phi}{\lambda}\operatorname{dist}((\overline{P}_{i},\overline{r}_{i}),(P_{d_{i}},r_{d_{i}}))$

with $\phi=\max(\alpha,\beta)$, with $\alpha$ and $\beta$ from Definition 4.

We can further bound this using lemma 9.

$\displaystyle\frac{\phi}{\lambda}\operatorname{dist}((\overline{P}_{i},\overline{r}_{i}),(P_{d_{i}},r_{d_{i}}))\leq\frac{\phi}{\lambda}\frac{v^{k}\epsilon^{k+1}(v-1)-v\epsilon+\epsilon}{v^{k}(v\epsilon-1)-v\epsilon+1}\operatorname{dist}((P_{ik},r_{ik}),(P_{ik+1},r_{ik+1}))$

We can now bound $T_{3}$ using lemmas 1 and 4.

$\displaystyle
T_{3}=\left\lVert\operatorname{GD}(P_{d_{i}},r_{d_{i}})-d_{S}\right\rVert_{2}\leq\frac{\phi}{\lambda}\operatorname{dist}((P_{d_{i}},r_{d_{i}}),(P_{S},r_{S}))\leq\frac{\phi\iota}{\lambda(1-\epsilon)}\|d_{i}-d_{S}\|_{2}$

In total we get

$\displaystyle\left\lVert
d_{i+1}-d_{S}\right\rVert_{2}\leq\frac{\sqrt{38|S|^{1.5}(B+\sqrt{|A|})\eta}}{(1-\gamma)^{1.5}}\frac{1}{\sqrt{\lambda}}+\frac{\phi}{\lambda}\operatorname{dist}((\overline{P}_{i},\overline{r}_{i}),(P_{d_{i}},r_{d_{i}}))+\frac{\phi\iota}{\lambda(1-\epsilon)}\left\lVert
d_{i}-d_{S}\right\rVert_{2}$ $\displaystyle\leq$
$\displaystyle\frac{\sqrt{38|S|^{1.5}(B+\sqrt{|A|})\eta}}{(1-\gamma)^{1.5}}\frac{1}{\sqrt{\lambda}}+\frac{\phi}{\lambda}\frac{v^{k}\epsilon^{k+1}(v-1)-v\epsilon+\epsilon}{v^{k}(v\epsilon-1)-v\epsilon+1}\operatorname{dist}((P_{ik},r_{ik}),(P_{ik+1},r_{ik+1}))+\frac{\phi\iota}{\lambda(1-\epsilon)}\left\lVert
d_{i}-d_{S}\right\rVert_{2}$ $\displaystyle=$ $\displaystyle
x_{1}\delta+x_{2}\left\lVert d_{i}-d_{S}\right\rVert_{2}$

Where we define
$x_{1}=\frac{\sqrt{38|S|^{1.5}(B+\sqrt{|A|})\eta}}{(1-\gamma)^{1.5}\sqrt{\lambda}\delta}+\frac{\phi}{\lambda\delta}\frac{v^{k}\epsilon^{k+1}(v-1)-v\epsilon+\epsilon}{v^{k}(v\epsilon-1)-v\epsilon+1}\operatorname{dist}((P_{ik},r_{ik}),(P_{ik+1},r_{ik+1}))$
and $x_{2}=\frac{\phi\iota}{\lambda(1-\epsilon)}$.

We now prove that after a certain number of update iterations $i$, the
occupancy measure $d_{i}$ is in a $\delta$ radius around a stable occupancy
measure $d_{S}$. For this we can apply lemma 3, if we know that
$x_{1}+x_{2}<1$.

So we first derive criteria under which $x_{1}+x_{2}<1$ holds.

From the conditions of the Theorem if follows that $v\epsilon>1$. Using this
we can derive that for any $z>0$, if
$k>\frac{\ln\left(\frac{\epsilon(v-1)}{v\epsilon-1}\right)+\ln\left(1/z\right)}{\ln\left(1/\epsilon\right)}$,
then
$\frac{v^{k}\epsilon^{k+1}(v-1)-v\epsilon+\epsilon}{v^{k}(v\epsilon-1)-v\epsilon+1}<z$.

We now bound