# Performative Reinforcement Learning

Debmalya Mandal
MPI-SWS
<EMAIL_ADDRESS>
Stelios Triantafyllou
MPI-SWS
<EMAIL_ADDRESS>Goran Radanovic
MPI-SWS
<EMAIL_ADDRESS>

###### Abstract

We introduce the framework of performative reinforcement learning where the
policy chosen by the learner affects the underlying reward and transition
dynamics of the environment. Following the recent literature on performative
prediction [Per+20], we introduce the concept of performatively stable policy.
We then consider a regularized version of the reinforcement learning problem
and show that repeatedly optimizing this objective converges to a
performatively stable policy under reasonable assumptions on the transition
dynamics. Our proof utilizes the dual perspective of the reinforcement
learning problem and may be of independent interest in analyzing the
convergence of other algorithms with decision-dependent environments. We then
extend our results for the setting where the learner just performs gradient
ascent steps instead of fully optimizing the objective, and for the setting
where the learner has access to a finite number of trajectories from the
changed environment. For both the settings, we leverage the dual formulation
of performative reinforcement learning, and establish convergence to a stable
solution. Finally, through extensive experiments on a grid-world environment,
we demonstrate the dependence of convergence on various parameters e.g.
regularization, smoothness, and the number of samples.

##  1 Introduction

Over the last decade, advances in reinforcement learning techniques enabled
several breakthroughs in AI. These milestones include AlphaGo [Sil+17],
Pluribus [BS19], and AlphaStar [Vin+19]. Such success stories of reinforcement
learning in multi-agent game playing environments have naturally led to the
adoption of RL in many real-world scenarios e.g. recommender systems [Agg+],
and healthcare [Est+19]. However, these critical domains often pose new
challenges including the mismatch between deployed policy and the target
environment.

Existing frameworks of reinforcement learning ignore the fact that a deployed
policy might change the underlying environment (i.e., reward, or probability
transition function, or both). Such a mismatch between the deployed policy and
the environment often arises in practice. For example, recommender systems
often use contextual Markov decision process to model interaction with a user
[Han+20]. In such a contextual MDP, the initial context/user feature is drawn
according a distribution, then the user interacts with the platform according
to the context-specific MDP. However, it has been repeatedly observed that
such recommender systems not only change the user demographics (i.e.
distribution of contexts) but also how they interact with the platforms
[CSE18, Man+20]. Our second example comes from autonomous vehicles (AV). Even
if we ignore the multi-agent aspect of these learning algorithms, a deployed
AV might change how the pedestrians, and other cars behave, and the resulting
environment might be quite different from what the designers of the AV had in
mind [Nik+17].

Recently, [Per+20] introduced the notion of _performative prediction_ , where
the predictions made by a classifier changes the data distribution. However,
in the context of reinforcement learning, the situation is different as the
changing transition dynamics introduces additional complexities. If the
underlying probability transition function changes, then the class of feasible
policies and/or models changes with time. This implies that we need a
framework that is more general than the framework of performative prediction,
and can model policy-dependent outcomes in reinforcement learning.

Our Contributions: In this paper, we introduce the notion of _performative
reinforcement learning_ where the deployed policy not only changes the reward
vector but also the underlying transition probability function. We introduce
the notion of _performatively stable policy_ and show under what conditions
various repeated retraining methods (e.g., policy optimization, gradient
ascent etc.) converges to such a stable solution. Our precise contributions
are the following.

  * •

We consider a regularized version of the reinforcement learning problem where
the variables are long-term discounted state-action occupancy measures. We
show that, when both the probability transition function and the reward
function changes smoothly in response to the occupancy measure, repeated
optimization of regularized reinforcement learning converges to a stable
solution.

  * •

We then show that if the learner performs repeated projected gradient ascent
steps, then also convergence is guaranteed provided that the step-size is
small enough. Compared to the supervised learning setting [Per+20], the
projection step is necessary as the probability transition function, and hence
the space of occupancy measures change with time.

  * •

Next we extend our result to the finite samples setting, where the learner has
access to a collection of samples from the updated environment. For this
setting, we use an empirical version of the Lagrangian of the regularized RL
problem. We show that repeatedly solving a saddle point of this empirical
Lagrangian (max player corresponds to the learner) also converges to a stable
solution provided that the number of samples is large enough.

  * •

Finally, we empirically evaluate the effect of various parameter choices
(regularization, smoothness, number of samples etc.) through extensive
experiments on a two-agent grid-world environment. In this environment, the
first agent performs various types of repeated retraining, whereas the second
agent responds according to a smooth response function.

Our Techniques: At a high level, our theoretical results might look similar to
the results derived by [Per+20]. However, there are many challenges.

  * •

We repeatedly maximize a regularized objective whose feasible region is the
space of feasible occupancy measures. As the probability transition function
changes with time, the feasible region of the optimization problem also
changes with time. So ideas from supervised classification setting [Men+20]
cannot be applied directly. Therefore, we look at the dual problem which is
strongly-convex and mapping from occupancy measure to the corresponding dual
optimal solution turns out to be a contraction. We believe that the dual
perspective on performative prediction might be useful for analyzing the
convergence of other algorithms with decision-dependent outcomes.

  * •

For performative reinforcement learning, the finite sample setting is very
different than the supervised learning setting. This is because we do not have
independent sample access from the new environment. At time-step $t$, we can
only access the new model through the policy $\pi_{t}$ (or occupancy measure
$d_{t}$). In that sense, the learner faces an offline reinforcement learning
problem where the samples are collected from the behavior policy $\pi_{t}$.
This is also the reason we need an additional overlap assumption, which is
often standard in offline reinforcement learning [MS08].

Related Work: [Per+20] introduced the notion of _performative prediction_.
Subsequent papers have considered several aspects of this framework including
optimization [Men+20, MPZ21], multi-agent systems [Nar+22], and population
dynamics [BHK20]. However, to the best of our knowledge, performative
prediction in sequential decision making is mostly unexplored. A possible
exception is [Bel+21] who consider a setting where the transition and reward
of the underlying MDP depend non-deterministically on the deployed policy.
Since the mapping is non-deterministic, it doesn’t lead to a notion of
equilibrium, and the authors instead focus on the optimality and convergence
of various RL algorithms.

Stochastic Stackelberg Games: Our work is also closely related to the
literature on stochastic games [Sha53, FV12], and in particular, those that
study Stackelberg (commitment) strategies [Von10], where a leader commits a
policy to which a follower (best) responds. While different algorithmic
approaches have been proposed for computing Stackelberg equilibria (SE) in
stochastic games or related frameworks [VS12, Let+12, Dim+17], computing
optimal commitment policies has shown to be a computationally intractable (NP-
hard) problem [Let+12]. More recent works have studied learning SE in
stochastic games, both from practical perspective [RMK20, MVV20, Hua+22] and
theoretical perspective [Bai+21, Zho+21]. The results in this paper differ
from this line of work in two ways. Firstly, our framework abstracts the
response model of an agent’s effective environment in that it does not model
it through a rational agency with a utility function. Instead, it is more
aligned with the approaches that learn the response function of the follower
agent [SKT16, Kar+17, Ses+20], out of which the closest to our work is
[Ses+20] that considers repeated games. Secondly, given that we consider
solution concepts from performative prediction rather than SE, we focus on
repeated retraining as the algorithm of interest, rather than bi-level
optimization approaches.

Other related work: We also draw a connection to other RL frameworks.
Naturally, this work relates to RL settings that study non-stationary
environments. These include recent learning-theoretic results, such as [GOA18,
Fei+20, Dom+21, CSZ20, WL21] that allow non-stationary rewards and transitions
provided a bounded number or amount of changes (under no-regret regime), the
extensive literature on learning under adversarial reward functions (e.g.,
[EKM04, NGS12, DH13, RM19]), or the recent works on learning under corrupted
feedback [Lyk+21]. However, the setting of this paper is more structured,
i.e., the environment responds to the deployed policy and does not arbitrarily
change. Our work is also broadly related to the extensive literature on multi-
agent RL literature – we refer the reader to [ZYB21] for a selective overview.
A canonical example of a multi-agent setting that closely relates to the
setting of this paper is human-AI cooperation, where the AI’s policy
influences the human behavior [Dim+17, Nik+17a, Cra+18, Rad+19, Car+19]. In
fact, our experiments are inspired by human-AI cooperative interaction. While
the algorithmic framework of repeated retraining has been discussed in some of
the works on cooperative AI (e.g., see [Car+19]), these works do not provide a
formal treatment of the problem at hand. Finally, this paper also relates to
the extensive literature on offline RL [Lev+20] as the learner faces an
offline RL problem when performing repeated retraining with finite samples.We
utilize the analysis of [Zha+22] to establish finite sample guarantees, under
a standard assumption on sample generation [MS08, FSM10, XJ21], and overlap in
occupancy measure [MS08, Zha+22]. Note that offline RL has primarily focused
on static RL settings in which the policy of a learner does not affect the
model of the underlying environment.

##  2 Model

We are primarily concerned with Markov Decision Processes (MDPs) with a fixed
state space $S$, action set $A$, discount factor $\gamma$, and starting state
distribution $\rho$. The reward and the probability transition functions of
the MDP will be functions of the adopted policy. We consider infinite-horizon
setting where the learner’s goal is to minimize the total sum of discounted
rewards. We will write $s_{k}$ to denote the state visited at time-step $k$
and $a_{k}$ to denote the action taken at time-step $k$. When the learner
adopts policy $\pi$, the underlying MDP has reward function $r_{\pi}$ and
probability transition function $P_{\pi}$. We will write $M(\pi)$ to denote
the corresponding MDP, i.e., $M(\pi)=(S,A,P_{\pi},r_{\pi},\rho)$. Note that
only the reward and the transition probability function change according to
the policy $\pi$.

When an agent adopts policy $\pi$ and the underlying MDP is
$M(\pi^{\prime})=(S,A,P_{\pi^{\prime}},r_{\pi^{\prime}},\rho)$ the probability
of a trajectory $\tau=(s_{k},a_{k})_{k=0}^{\infty}$ is given as
$\mathbb{P}(\tau)=\rho(s_{0})\prod_{k=1}^{\infty}P_{\pi^{\prime}}(s_{k+1}|s_{k},\pi(s_{k}))$.
We will write $\tau\sim\mathbb{P}^{\pi}_{\pi^{\prime}}$ to denote such a
trajectory $\tau$. Given a policy $\pi$ and an underlying MDP
$M(\pi^{\prime})$ we write $V^{\pi}_{\pi^{\prime}}(\rho)$ to define the value
function w.r.t. the starting state distribution $\rho$. This is defined as
follows.

$V^{\pi}_{\pi^{\prime}}(\rho)=\mathbb{E}_{\tau\sim\mathbb{P}^{\pi}_{\pi^{\prime}}}\left[\sum_{k=0}^{\infty}\gamma^{k}r_{\pi^{\prime}}(s_{k},a_{k})\rvert\rho\right]$
(1)

Solution Concepts: Given the definition of the value function eq. 1, we can
now define the solution concepts for our setting. First we define the
performative value function of a policy which is the expected total return of
the policy given the environment changes in response to the policy.

######  Definition 1 (Performative Value Function).

Given a policy $\pi$, and a starting state distribution $\rho\in\Delta(S)$,
the performative value function $V^{\pi}_{\pi}(\rho)$ is defined as
$V^{\pi}_{\pi}(\rho)=\mathbb{E}_{\tau\sim\mathbb{P}^{\pi}_{\pi}}\left[\sum_{t=0}^{\infty}\gamma^{t}r_{\pi}(s_{t},a_{t})\rvert\rho\right]$.

We now define the performatively optimal policy, which maximizes performative
value function.

######  Definition 2 (Performatively Optimal Policy).

A policy $\pi$ is performatively optimal if it maximizes performative value
function, i.e.,
$\pi\in\operatorname*{arg\,max}_{\pi^{\prime}}V^{\pi^{\prime}}_{\pi^{\prime}}(\rho)$.

We will write $\pi_{P}$ to denote the performatively optimal policy. Although,
$\pi_{P}$ maximizes the performative value function, it need not be stable,
i.e., the policy need not be optimal with respect to the changed environment
$M(\pi_{P})$. We next define the notion of performatively stable policy which
captures this notion of stability.

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

A policy $\pi$ is performatively stable if it satisfies the condition
$\pi\in\operatorname*{arg\,max}_{\pi^{\prime}}V^{\pi^{\prime}}_{\pi}(\rho)$.

We will write $\pi_{S}$ to denote the performatively stable policy. The
definition of performatively stable policy implies that if the underlying MDP
is $M(\pi_{S})$ then an optimal policy is $\pi_{S}$. This means after
deploying the policy $\pi_{S}$ in the MDP $M(\pi_{S})$ the environment doesn’t
change and the learner is also optimizing her reward in this stable
environment.We next show that even for an MDP with a single state, these two
solution concepts can be very different.

Example: Consider an MDP with single state $s$ and two actions $a$ and $b$. If
a policy plays arm $a$ with probability $\theta$ and $b$ with probability
$1-\theta$ then we have $r(s,a)=\frac{1}{2}-\epsilon\theta$ and
$r(s,b)=\frac{1}{2}+\epsilon\theta$ for some $\epsilon<\frac{1}{4}$. Note that
if $\theta_{S}=0$ then both the actions give same rewards, and the learner can
just play action $b$. Therefore, a policy that always plays action $b$ is a
stable policy and achieves a reward of $\frac{1}{2(1-\gamma)}$. On the other
hand, a policy that always plays action $a$ with probability $\theta=1/4$ has
the performative value function of

$\frac{\theta(1/2-\epsilon\theta)}{1-\gamma}+\frac{(1-\theta)(1/2+\epsilon\theta)}{1-\gamma}=\frac{1/2+\epsilon/8}{1-\gamma}$

So, for $\epsilon>0$, a performatively optimal policy can achieve higher value
function than a stable policy.

We will mainly consider with the tabular MDP setting where the number of
states and actions are finite. Even though solving tabular MDP in classic
reinforcement learning problem is relatively straight-forward, we will see
that even the tabular setting raises many interesting challenges for the
setting of performative reinforcement learning.

Discounted State, Action Occupancy Measure: Note that it is not a priori clear
if there always exists a performatively stable policy (as defined in (2)).
This is because such existence guarantee is usually established through a
fixed-point argument, but the set of optimal solutions need not be convex. If
both $\pi_{1}$ and $\pi_{2}$ optimizes (2), then their convex combination
might not be optimal. So, in order to find a stable policy, we instead
consider the linear programming formulation of reinforcement learning. Given a
policy $\pi$, its long-term discounted state-action occupancy measure in the
MDP $M(\pi)$ is defined as
$d^{\pi}(s,a)=\mathbb{E}_{\tau\sim\mathbb{P}^{\pi}_{\pi}}\left[\sum_{k=0}^{\infty}\gamma^{k}\mathds{1}\left\\{s_{k}=s,a_{k}=a\right\\}\rvert\rho\right]$.
Given an 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.$
(4)

With this definition, we can pose the problem of finding a performatively
stable occupancy measure. An occupancy measure $d$ is performatively stable if
it is the optimal solution of the following problem.

$\displaystyle d\in$ $\displaystyle\operatorname*{arg\,max}_{d\geq
0}\sum_{s,a}d(s,a)r_{d}(s,a)$ (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$

With slight abuse of notation we are writing $P_{d}$ as $P_{\pi^{d}}$ (as
defined in equation (4)). If either the probability transition function or the
reward function changes drastically in response to the occupancy measure then
the optimization problem 5 need not even have a stable point. Therefore, as is
standard in performative prediction, we make the following sensitivity
assumption regarding the underlying environment.

######  Assumption 1.

The reward and probability transition mappings are
$(\varepsilon_{r},\varepsilon_{p})$-sensitive i.e. the following holds for any
two occupancy measures $d$ and $d^{\prime}$

$\displaystyle\left\lVert
r_{d}-r_{d^{\prime}}\right\rVert_{2}\leq\varepsilon_{r}\left\lVert
d-d^{\prime}\right\rVert_{2},\ \left\lVert
P_{d}-P_{d^{\prime}}\right\rVert_{2}\leq\varepsilon_{p}\left\lVert
d-d^{\prime}\right\rVert_{2}$

Since the objective function of eq. 5 is convex (in fact linear), and the set
of optimal solutions is convex, a simple application of Kakutani fixed point
theorem [Gli52] shows that there always exists a performative stable
solution.111The proof of this result and all other results are provided in the
appendix.

######  Proposition 1.

Suppose assumption 1 holds for some constants
$(\varepsilon_{r},\varepsilon_{p})$, then the optimization problem 5 always
has a fixed point.

##  3 Convergence of Repeated Retraining

Even though the optimization problem (5) is guaranteed to have a stable
solution, it is not clear that repeatedly optimizing this objective converges
to such a point. We now consider a regularized version of the optimization
problem (5), and attempt to obtain a stable solution of the regularized
problem. In subsection (3.3) we will show that such a stable solution
guarantees approximate stability with respect to the original unregularized
objective (5).

$\displaystyle\max_{d\geq 0}\ $
$\displaystyle\sum_{s,a}d(s,a){\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}r_{d}(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){\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}P_{d}(s^{\prime},a,s)}\
\forall s$

Here $\lambda>0$ is a constant that determines the strong-concavity of the
objective. Before analyzing the behavior of repeatedly optimizing the new
objective (6) we discuss two important issues. First, we consider quadratic
regularization for simplicity, and our results can be easily extended to any
strongly-convex regularizer. Second, we apply regularization in the occupancy
measure space, but regularization in policy space is commonly used [Mni+16].
Since the performatively stable occupancy measure $d_{S}$ is not known, a
common strategy adopted is repeated policy optimization. At time $t$, the
learner obtains the occupancy measure $d_{t}$, and deploys the policy
$\pi_{t}$ (as defined in (4)). In response, the environment changes to
$P_{t}=P_{d_{t}}$ and $r_{t}=r_{d_{t}}$, and the learning agent solves the
following optimization problem to obtain the next occupancy measure $d_{t+1}$.

$\displaystyle\max_{d\geq 0}\ $
$\displaystyle\sum_{s,a}d(s,a){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}r_{t}(s,a)}-\frac{\lambda}{2}\left\lVert
d\right\rVert_{2}^{2}$ (7) s.t.
$\displaystyle\sum_{a}d(s,a)=\rho(s)+\gamma\cdot\sum_{s^{\prime},a}d(s^{\prime},a){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P_{t}(s^{\prime},a,s)}\
\forall s$

We next show that repeatedly solving the problem (7) converges to a stable
point.

######  Theorem 1.

Suppose assumption 1 holds with
$\lambda>\frac{12S^{3/2}(2\epsilon_{r}+5S\epsilon_{p})}{(1-\gamma)^{4}}$. Let
$\mu=\frac{12S^{3/2}(2\epsilon_{r}+5S\epsilon_{p})}{\lambda(1-\gamma)^{4}}$.
Then for any $\delta>0$ we have

$\left\lVert d_{t}-d_{S}\right\rVert_{2}\leq\delta\quad\forall t\geq
2(1-\mu)^{-1}\ln\left({2}/{\delta(1-\gamma)}\right)$

Here we discuss some of the main challenges behind the proof of this theorem.

  * •

The primal objective function (7) is strongly concave but the feasible region
of the optimization problem changes with each iteration. So we cannot apply
the results from performative prediction [Per+20], and instead, look at the
dual objective which is $A(1-\gamma)^{2}/\lambda$-strongly convex.

  * •

Although the dual problem is strongly convex, it does not satisfy Lipschitz
continuity w.r.t. $P$. However, we show that the norm of the optimal solution
of the dual problem is bounded by $O\left(S/(1-\gamma)^{2}\right)$ and this is
sufficient to show that the dual objective is Lipschitz-continuous with
respect to $P$ at the dual optimal solution. We show that the proof argument
used in [Per+20] works if we replace global Lipschitz-continuity by such local
Lipschitz-continuity.

  * •

Finally, we translate back the bound about the dual solution to a guarantee
about the primal solution ($\left\lVert d_{t}-d_{S}\right\rVert_{2})$ using
the strong duality of the optimization problem 7. This step crucially uses the
quadratic regularization in the primal.

Here we make several observations regarding the assumptions required by
Theorem 1. First, Theorem 1 suggests that for a given sensitivity
$(\epsilon_{r},\epsilon_{p})$ and discount factor $\gamma$, one can choose the
parameter $\lambda$ so that the convergence to a stable point is guaranteed.
Second, for a given value of $\lambda$ and $\gamma$ if the sensitivity is
small enough, then repeatedly optimizing 7 converges to a stable point.

###  3.1 Gradient Ascent Based Algorithm

We now extend our result for the setting where the learner does not fully
solve the optimization problem 7 every iteration. Rather, the learner takes a
gradient step with respect to the changed environment every iteration. Let
$\mathcal{C}_{t}$ denote the set of occupancy measures that are compatible
with probability transition function $P_{t}$.

$\displaystyle\mathcal{C}_{t}=\bigg{\\{}d:$
$\displaystyle\sum_{a}d(s,a)=\rho(s)+\gamma\sum_{s^{\prime},a}d(s^{\prime},a)P_{t}(s^{\prime},a,s)\
\forall s\textrm{and }d(s,a)\geq 0\ \forall s,a\bigg{\\}}$ (8)

Then the gradient ascent algorithm first takes a gradient step according to
the objective function $r_{t}^{\top}d-\frac{\lambda}{2}\left\lVert
d\right\rVert_{2}^{2}$ and then projects the resulting occupancy measure onto
$\mathcal{C}_{t}$.

$\displaystyle
d_{t+1}=\mathrm{Proj}_{\mathcal{C}_{t}}\left(d_{t}+\eta\cdot\left(r_{t}-\lambda
d_{t}\right)\right)=\mathrm{Proj}_{\mathcal{C}_{t}}\left((1-\eta\lambda)d_{t}+\eta
r_{t}\right)$ (9)

Here $\mathrm{Proj}_{\mathcal{C}}(v)$ finds a point in $\mathcal{C}$ that is
closest to $v$ in $L_{2}$-norm. We next show that repeatedly taking projected
gradient ascent steps with appropriate step size $\eta$ converges to a stable
point.

######  Theorem 2.

Let
$\lambda\geq\max\left\\{4\epsilon_{r},2S,\frac{20\gamma^{2}S^{1.5}(\epsilon_{r}+\epsilon_{p})}{(1-\gamma)^{2}}\right\\}$,
step-size $\eta=\frac{1}{\lambda}$ and
$\mu=\sqrt{\frac{64\gamma^{2}\epsilon_{p}^{2}}{(1-\gamma)^{4}}\left(1+\frac{30\gamma^{4}S^{2}}{(1-\gamma)^{4}}\right)}$.
Suppose assumption 1 holds with $\epsilon_{p}<\min\left\\{\frac{\gamma
S}{3},\frac{(1-\gamma)^{4}}{100\gamma^{3}S}\right\\}$. Then for any $\delta>0$
we have

$\left\lVert d_{t}-d_{S}\right\rVert_{2}\leq\delta\quad\forall
t\geq(1-\mu)^{-1}\ln\left({2}/{\delta(1-\gamma)}\right)$

Proof Sketch: First, the projection step 9 can be computed through the
following convex program.

$\displaystyle\min_{d\geq 0}\ $ $\displaystyle\frac{1}{2}\left\lVert
d-(1-\eta\lambda)d_{t}-\eta r_{t}\right\rVert_{2}^{2}$ (10) 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$

Even though the objective above is convex, its feasible region changes with
time. So we again look at the dual objective which is strongly concave and has
a fixed feasible region. Given an occupancy measure $d_{t}$, let
$\mathrm{GD}_{\eta}(d_{t})$ be the optimal solution of the problem 9. We show
that if the step-size $\eta$ is chosen small enough then the operator
$\mathrm{GD}_{\eta}(\cdot)$ is a contraction mapping by first proving the
corresponding optimal dual solution forms a contraction, and then using strong
duality to transfer the guarantee back to the primal optimal solutions.
Finally, we show that the fixed point of the mapping
$\mathrm{GD}_{\eta}(\cdot)$ indeed coincides with the performatively stable
solution $d_{S}$.

###  3.2 Finite Sample Guarantees

So far we assumed that after deploying the policy corresponding to the
occupancy measure $d_{t}$ we observe the updated environment
$M_{t}=(S,A,P_{t},r_{t},\gamma)$. However, in practice, we do not have access
to the true model but only have access to samples from the updated
environment. Our setting is more challenging than the finite samples setting
considered by [Per+20]. Unlike the supervised learning setting, we do not have
access to independent samples from the new environment. At time $t$ we can
deploy policy $\pi_{t}$ corresponding to the occupancy measure $d_{t}$, and
can access trajectories from the new environment $M_{t}$ only through the
policy $\pi_{t}$. Therefore, at every step, the learner faces an offline
reinforcement learning problem where the policy $\pi_{t}$ is a behavioral
policy.

A standard assumption in offline reinforcement learning is overlap in
occupancy measure between the behavior policy and a class of target policies
[MS08]. Without such overlap, one can get no information regarding the optimal
policy from the trajectories visited by the behavioral policy. We make the
following assumption regarding the overlap in occupancy measure between a
deployed policy and the optimal policy in the changed environment.

######  Assumption 2.

Given an occupancy measure $d$, let $\rho^{\star}_{d}$ be the optimal
occupancy measure maximizing 7, and $\overline{d}$ is the occupancy measure of
$\pi^{d}$ in $P_{d}$. Then there exists $B>0$ so that

$\max_{s,a}\left|\frac{\rho^{\star}_{d}(s,a)}{\overline{d}(s,a)}\right|\leq B\
\quad\forall d$

When there is no performativity, $\overline{d}$ equals $d$ and the assumption
states overlap between the occupancy measure of the deployed policy and the
optimal policy. This is the standard assumption of single policy coverage in
offline reinforcement learning. When there is performativity, $\overline{d}$
can be different than $d$ since the deployed policy $\pi^{d}$ might have
occupancy measure different than $d$ in the changed model $P_{d}$, and in that
case we require overlap between $\overline{d}$ and the optimal occupancy
measure. Assumption (2) is also significantly weaker than the uniform coverage
assumption which requires $\max_{d}\max_{s,a}\overline{d}(s,a)>0$ as it allows
the possibility that $\overline{d}(s,a)=0$ as long as the optimal policy
doesn’t visit state $s$ or never takes action $a$ in state $s$.

Data: We assume the following model of sample generation at time $t$. Given
the occupancy measure $d_{t}$ let the normalized occupancy measure be
$\widetilde{d}_{t}(s,a)=(1-\gamma){d_{t}(s,a)}$. First, sample a state, action
pair $(s_{i},a_{i})$ i.i.d as $(s_{i},a_{i})\sim\widetilde{d}_{t}$, then
reward $r_{i}\sim r_{t}(s_{i},a_{i})$, and finally the next state
$s_{i}^{\prime}\sim P_{t}(\cdot|s_{i},a_{i})$. We have access to $m_{t}$ such
tuples at time $t$ and the data collected at time is given as
$\mathcal{D}_{t}=\left\\{(s_{i},a_{i},r_{i},s_{i}^{\prime})\right\\}_{i=1}^{m_{t}}$.
We would like to point out that this is a standard model of sample generation
in offline reinforcement learning (see e.g. [MS08, FSM10, XJ21]).

With finite samples, the learner needs to optimize an empirical version of the
optimization problem 7, and the choice of such an empirical objective is
important for convergence. We follow the recent literature on offline
reinforcement learning [Zha+22] and consider the Lagrangian of eq. 7.

$\displaystyle\mathcal{L}(d,h;M_{t})=d^{\top}{r}_{t}-\frac{\lambda}{2}\left\lVert
d\right\rVert_{2}^{2}+\sum_{s}h(s)\left(-\sum_{a}d(s,a)+\rho(s)+\gamma\cdot\sum_{s^{\prime},a}d(s^{\prime},a){P}_{t}(s^{\prime},a,s)\right)$
$\displaystyle=$ $\displaystyle-\frac{\lambda}{2}\left\lVert
d\right\rVert_{2}^{2}+\sum_{s}h(s)\rho(s)+\sum_{s,a}d_{t}(s,a)\frac{d(s,a)}{d_{t}(s,a)}\left(r_{t}(s,a)-h(s)+\gamma\sum_{s^{\prime}}P_{t}(s,a,s^{\prime})h(s^{\prime})\right)$

The above expression motivates the following empirical version of the
Lagrangian.

$\displaystyle\hat{\mathcal{L}}(d,h;M_{t})$
$\displaystyle=-\frac{\lambda}{2}\left\lVert
d\right\rVert_{2}^{2}+\sum_{s}h(s)\rho(s)+\sum_{i=1}^{m_{t}}\frac{d(s_{i},a_{i})}{d_{t}(s_{i},a_{i})}\frac{r(s_{i},a_{i})-h(s_{i})+\gamma
h(s_{i}^{\prime})}{m_{t}(1-\gamma)}$ (11)

We repeatedly solve for a saddle point of the objective above.

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

The next theorem provides convergence guarantees of the repeated optimization
procedure (12) provided that the number of samples is large enough.

######  Theorem 3 (Informal Statement).

Suppose assumption 1 holds with
$\lambda\geq\frac{24S^{3/2}(2\epsilon_{r}+5S\epsilon_{p})}{(1-\gamma)^{4}}$,
and assumption 2 holds with parameter $B$. Let
$\mu=\frac{24S^{3/2}(2\epsilon_{r}+5S\epsilon_{p})}{(1-\gamma)^{4}}$. For any
$\delta>0$, and error probability $p$ if we repeatedly solve the optimization
problem (12) with number of samples
$m_{t}\geq\widetilde{O}\left(\frac{A^{2}B^{2}}{\delta^{4}(2\epsilon_{r}+5S\epsilon_{p})^{2}}\ln\left(\frac{t}{p}\right)\right)$222Here
we ignore terms that are logarithmic in $S,A$, and $1/\delta$. then with
probability at least $1-p$ we have

$\left\lVert d_{t}-d_{S}\right\rVert_{2}\leq\delta\ \forall
t\geq(1-\mu)^{-1}\ln\left({2}/{\delta(1-\gamma)}\right)$

Proof Sketch:

  * •

We first show that the empirical version of the Lagrangian
$\hat{\mathcal{L}}(d,h;M_{t})$ is close to the true Lagrangian
$\mathcal{L}(d,h;M_{t})$ with high probability. This is shown using the
Chernoff-Hoeffding inequality and an $\epsilon$-net argument over the
variables. Here we use the fact that for the dual variables we can just
consider the space $\mathcal{H}=\left\\{h:\left\lVert
h\right\rVert_{2}\leq{3S}/{(1-\gamma)^{2}}\right\\}$ as the optimal solution
is guaranteed to exist in this space.

  * •

We then show that an optimal saddle point of the empirical Lagrangian 11 is
close to the optimal solution of the true Largrangian. In particular, if
$\left|\mathcal{L}(d,h;M_{t})-\hat{\mathcal{L}}(d,h;\hat{M}_{t})\right|\leq\epsilon$
then we are guaranteed that $\left\lVert
d_{t+1}-\mathrm{GD}(d_{t})\right\rVert_{2}\leq O(\epsilon)$. Here
$\mathrm{GD}(d_{t})$ denotes the solution obtained from optimizing the exact
function.

  * •

By choosing an appropriate number of samples, we can make the error term
$\epsilon$ small enough, and establish the following recurrence relation:
$\left\lVert d_{t+1}-d_{S}\right\rVert_{2}\leq\beta\delta+\beta\left\lVert
d_{t}-d_{S}\right\rVert_{2}$ for $\beta<1/2$. The rest of the proof follows
the main idea of the proof of Theorem 3.10 from [Men+20]. If $\left\lVert
d_{t}-d_{S}\right\rVert_{2}>\delta$ then we get a contraction mapping. On the
other hand, if $\left\lVert d_{t}-d_{S}\right\rVert_{2}\leq\delta$ then
subsequent iterations cannot move $d_{t}$ outside of the $\delta$-neighborhood
of $d_{S}$.

###  3.3 Approximating the Unregularized Objective

Theorem (1) shows that repeatedly optimizing objective (6) converges to a
stable policy (say $d^{\lambda}_{S}$) with respect to the regularized
objective (6). Here we show that the solution $d^{\lambda}_{S}$ approximates
the performatively stable and performatively optimal policy with respect to
the unregularized objective (5).

######  Theorem 4.

There exists a choice of the regularization parameter ($\lambda$) such that
repeatedly optimizing objective (7) converges to a policy ($d^{\lambda}_{S}$)
with the following guarantee333$C(\widetilde{d})$ denotes the set of occupancy
measures that are feasible with respect to
$\mathcal{P}(\widetilde{d})=P_{\widetilde{d}}$.

$\displaystyle\sum_{s,a}r_{d^{\lambda}_{S}}(s,a)d^{\lambda}_{S}(s,a)\geq\max_{d\in\mathcal{C}(d^{\lambda}_{S})}\sum_{s,a}r_{d^{\lambda}_{S}}(s,a)d(s,a)-O\left({S^{3/2}(\epsilon_{r}+S\epsilon_{p})}/{(1-\gamma)^{6}}\right)$

Note that as $\epsilon=\max\left\\{\epsilon_{r},\epsilon_{p}\right\\}$
converges to zero, the policy $d^{\lambda}_{S}$ also approaches a
performatively stable solution with respect to the original unregularized
objective.

######  Theorem 5 (Informal Statement).

Let $d_{PO}$ be the performatively optimal solution with respect to the
unregularized objective and let
$\varepsilon=\max\left\\{\epsilon_{r},\epsilon_{p}\right\\}$. Then there
exists a value of $\lambda$ such that repeatedly optimizing objective (7)
converges to a policy ($d^{\lambda}_{S}$) with the following guarantee

$\displaystyle\sum_{s,a}r_{d^{\lambda}_{S}}(s,a)d^{\lambda}_{S}(s,a)\geq\sum_{s,a}r_{d_{PO}}(s,a)d_{PO}(s,a)-O\left(\max\left\\{\frac{S^{5/3}A^{1/3}\epsilon^{2/3}}{(1-\gamma)^{14/3}},\frac{\epsilon
S}{(1-\gamma)^{4}}\right\\}\right)$

We again see that as $\epsilon$ converges to zero, $d^{\lambda}_{S}$
approaches a performatively optimal solution with respect to the original
objective. The proof of theorem (5) uses the following bound on the distance
between the performatively stable solution and the optimal
solution.$\left\lVert d^{\lambda}_{S}-d^{\lambda}_{PO}\right\rVert_{2}\leq
O\left(\frac{S^{2}\sqrt{A}}{\lambda(1-\gamma)^{4}}\left(\epsilon_{r}\left(1+\gamma\sqrt{S}\right)+\epsilon_{p}\frac{\gamma{S}}{(1-\gamma)^{2}}\right)\right)$

We believe that the bounds of theorems (5) and (4) can be improved with more
careful analysis. However, the error bound should grow as $\gamma$ decreases.
This is because the diameter (or max $L_{2}$ norm) of occupancy measure is
most $1/(1-\gamma)^{2}$ and even in performative prediction such an
approximation bound grows with the diameter of the model.444For example, see
proposition E.1 [Per+20], which is stated for diameter $1$ and convex loss
function.

##  4 Experiments

Figure 1: RPO $\lambda=1$

Figure 2: RPO $\beta=10$

Figure 3: RGA $\lambda=1$, $\beta=5$

Figure 4: RGA Gap $\lambda=1$, $\beta=5$

Figure 5: ROL FS $\lambda=1$, $\beta=5$

Figure 6: RPO FS $\lambda=1$, $\beta=5$

Figure 7:  Experimental results for Gridworld. All plots were generated with
$\gamma=0.9$ and $1000$ iterations. We normalized the distance between
iterations $t$ and $t+1$ with $c_{t}=\frac{1}{||d_{t}||_{2}}$. RPO stands for
repeated policy optimization, RGA for repeated gradient ascent, ROL for
repeatedly solving (empirical) Lagrangian and FS for finite samples. The
parameters are $\lambda$ (regularization), $\beta$ (smoothness), $\eta$ (step-
size), and $m$ (number of trajectories).

In this section, we experimentally evaluate the performance of various
repeated retraining methods, and determine the effects of various parameters
on convergence. All experiments are conducted on a grid-world environment
proposed by [TSR21].555The original single-agent version of this environment
can be found in [Vol+19]. We next describe how this environment is adapted for
simulating performative reinforcement learning.

Figure 8: Gridworld

Gridworld: We consider the grid-world environment shown in Fig. 8, in which
$n+1$ agents share control over an actor. The agents’ objective is to guide
the actor from some initial state $S$ to the terminal state $G$, while
minimizing their total discounted cost. We will call the first agent the
principal, and the other $n$ agents the followers. In each state, the agents
select their actions simultaneously. The principal agent, $A_{1}$, chooses the
direction of the actor’s next move by taking one of four actions (left, right,
up, and down).

Any other agent, $A_{j}$ decides to either intervene or not in $A_{1}$’s
action. If the majority of the $n$ follower agents choose not to intervene,
then the actor moves one cell towards the direction chosen by $A_{1}$,
otherwise it moves one cell towards the new direction chosen by the majority
of the followers. Note that the principal and the followers’ policies
determine a policy for the actor agent.

The cost at each state is defined according to the grid-world shown in Fig. 8.
If the actor visits a blank or an $S$ cell, then all the agents receive a
small negative reward equal to $-0.01$. If an $F$ cell is visited, then a
slightly more increased cost equal to $-0.02$ is imposed and for $H$ cells a
severe penalty of $-0.5$ is inflicted. Additionally, whenever any $A_{j}$
decides to intervene, it pays an additional cost of $-0.05$.

Response Model: We implement agent $A_{1}$ as a learner who performs repeated
retraining. The initial policy of agent $A_{1}$ is an $\epsilon$-optimal
single-agent policy ($\epsilon=0.1$) assuming that no other agent intervenes.
Subsequently, agent $A_{1}$ performs one type of repeated retraining (e.g.
gradient ascent).The follower agents, on the other hand, always respond to the
policy of $A_{1}$ according to a response model. In particular, given a policy
of $A_{1}$ (say $\pi_{1}$), we first compute an optimal $Q$-value function for
agent $A_{j}$, $Q^{*|\pi_{1}}_{j}$. Note that $Q^{*|\pi_{1}}_{j}$ is computed
w.r.t. a perturbed grid-world, and which was generated by performing a random
cell perturbation on the grid-world of Fig. 8. The perturbed grid-worlds are
different for different agents. Then we compute an average $Q$-function
defined as
$\overline{Q}^{*|\pi_{1}}=\frac{1}{n}\sum_{j=2}^{n+1}\overline{Q}^{*|\pi_{1}}_{j}$.
Then a policy $\pi_{2}$ adopted by the Boltzmann softmax operator with
parameter $\beta$. Then a policy $\pi_{2}$ is determined by the Boltzmann
softmax operator with temperature parameter $\beta$,
$\pi_{2}(a_{i}|s)=\frac{e^{\beta\cdot\overline{Q}^{*|\pi_{1}}(s,a_{i})}}{\sum_{j}e^{\beta\cdot\overline{Q}^{*|\pi_{1}}(s,a_{j})}}$.
Note that the new policy $\pi_{2}$ effectively plays the role of a changing
environment by responding to the majority of the $n$ follower agents.
Additionally, parameter $\beta$ controls the smoothness of the changing
environment, as viewed by $A_{1}$.

Repeated Policy Optimization: We first consider the scenario where agent
$A_{1}$ gets complete knowledge of the updated reward and probability
transition function at time $t$. In our setting, this means that $A_{1}$
decides on $\pi_{1}^{t}$, all the other agents respond according to the
softmax operator and jointly determines $\pi_{2}^{t}$, and then agent $A_{1}$
observes the new policy $\pi_{2}^{t}$. This lets $A_{1}$ to compute new
probability transition function $P_{t}$, and reward function $r_{t}$, and
solve optimization problem 7. The solution is the new occupancy measure
$d_{1}^{t+1}$ for $A_{1}$, and $A_{1}$ computes new policy $\pi^{t+1}_{1}$ for
time $t+1$ by normalization using eq. 4. Plot 7 shows the convergence results
of the repeated policy optimization for different values of $\beta$, with
$\lambda$ fixed to $1$. We see that if the response function of the
environment (i.e., the policy of agent $A_{2}$) is not smooth enough (e.g.,
for $\beta=200$), the algorithm fails to converge to a stable solution. In
Plot 7 we fix $\beta$ to $10$ and vary the value of parameter $\lambda$
(strength of regularization). We can see that the algorithm converges only for
large enough values of the regularization constant $\lambda$. Furthermore, we
observe that the convergence is faster as $\lambda$ increases.

Repeated Gradient Ascent: We now see what happens if agent $A_{1}$ uses
repeated gradient ascent instead of fully optimizing the objective each
iteration. Here also $A_{1}$ fully observes $\pi^{t}_{2}$ (hence $P_{t}$ and
$r_{t}$) at time $t$. However, instead of full optimization, $A_{1}$ performs
a projected gradient ascent step (9) to compute the next occupancy measure
$d^{t+1}_{1}$. Plot 7 shows the performance of repeated gradient ascent for
different values of the step-size $\eta$. We observe that when $\eta$ is small
(e.g,. $\eta\leq O(1/\lambda)$), the learner converges to a stable solution.
But the learner diverges for large $\eta$. Additionally, the convergence is
faster for step-size closer to $1/\lambda$ (as suggested by Theorem 2). Since,
repeated gradient ascent does not fully solve the optimization problem 7, we
also plot the suboptimality gap of the current solution 7. This is measured as
the difference between the objective value for the best feasible solution
(w.r.t. $M_{t}$) and current solution ($d^{t}_{1}$), and then normalized by
the former. As the step-size $\eta$ is varied, we see a trend similar to Plot
7.

Effect of Finite Samples: Finally, we investigate the scenario where $A_{1}$
does not know $\pi_{2}^{t}$ at time $t$, and obtains samples from the new
environment $M_{t}$ by deploying $\pi^{t}_{1}$. In our experiments, instead of
sampling from the occupancy measure, $A_{1}$ directly samples $m$ trajectories
of fixed length (up to $100$) following policy $\pi^{t}_{1}$. We considered
two approaches for obtaining the new policy $\pi^{t+1}_{1}$. First, $A_{1}$
solves the empirical Lagrangian (11) through an iterative method. In
particular, we use an alternate optimization based method (algorithm (1))
where $h_{n}$ is updated through follow the regularized leader (FTRL)
algorithm and $d_{n}$ is updated through best response. 666Since the objective
(11) is linear in $h$ and concave in $d$, following standard arguments [FS96]
it is straightforward to show that algorithm (1) finds an
$\varepsilon$-approximate saddle point in
$O(SAB/(1-\gamma)^{2}\varepsilon^{2})$ iterations.

Algorithm 1 Alternating Optimization for the Empirical Lagrangian

Set $H=\frac{3S}{(1-\gamma)^{2}}$, and $\mathcal{H}=\left\\{h:\left\lVert
h\right\rVert_{2}\leq H\right\\}$.

for $n=1,2,..,N$ do

$h_{n}=\operatorname*{arg\,min}_{h\in\mathcal{H}}\sum_{n^{\prime}=1}^{n-1}\left\langle\nabla_{h}\hat{\mathcal{L}}(d_{n^{\prime}},h;M_{t}),h\right\rangle+\beta\left\lVert
h\right\rVert_{2}^{2}$

$d_{n}=\arg\max_{d\geq 0,\ d(s,a)\leq B\hat{d}_{t}(s,a)\forall
s,a}\hat{\mathcal{L}}(d,h_{n};M_{t})$

end for

Return $\overline{d}=\frac{1}{N}\sum_{n=1}^{N}d_{n}$.

Second, $A_{1}$ computes estimates of probability transition function
($\widehat{P}_{t}$), and reward function ($\widehat{r}_{t}$), and solves eq. 7
with these estimates. For both versions, we ran our experiments with $20$
different seeds, and plots 7 and 7 show the average errors along with the
standard errors for the two approaches. For both settings, we observe that as
$m$ increases, the algorithms eventually converge to a smaller neighborhood
around the stable solution. However, for large number of samples ($m=500$ or
$1000$), directly solving the Lagrangian (figure 7) gives improved result.

##  5 Conclusion

In this work, we introduce the framework of performative reinforcement
learning and study under what conditions repeated retraining methods (e.g.,
policy optimization, gradient ascent) converges to a stable policy. In the
future, it would be interesting to extend our framework to handle high
dimensional state-space, and general function approximation. The main
challenge with general function approximation is that a stable policy might
not exist, so the first step would be to characterize under what conditions
there is a fixed point. Moreover, most RL algorithms with function
approximation work in the policy space. So, another challenge lies in
generalizing optimization problem 7 to handle representations of states and
actions.

Another interesting question is to resolve the hardness of finding stable
policy with respect to the unregularized objective. To the best of our
knowledge, this question is unresolved even for performative prediction with
just convex loss function. It could be interesting to explore connections
between our repeated optimization procedure and standard reinforcement
learning methods, e.g., policy gradient methods [Mni+16, NJG17]. However, we
note that policy gradient methods typically work in the policy space, and
might not even converge to a stable point under changing environments.
Finally, for the finite samples setting, it would be interesting to use
offline reinforcement learning algorithms [Lev+20] for improving the speed of
convergence to a stable policy.

## References

  * [Agg+] Charu C Aggarwal  “Recommender systems”  Springer
  * [Bai+21] Yu Bai, Chi Jin, Huan Wang and Caiming Xiong  “Sample-efficient learning of stackelberg equilibria in general-sum games”  In _Advances in Neural Information Processing Systems_ 34, 2021
  * [Bel+21] James Bell, Linda Linsefors, Caspar Oesterheld and Joar Skalse  “Reinforcement Learning in Newcomblike Environments”  In _Advances in Neural Information Processing Systems_ 34, 2021
  * [Ber09] Dimitri Bertsekas  “Convex optimization theory”  Athena Scientific, 2009
  * [BHK20] Gavin Brown, Shlomi Hod and Iden Kalemaj  “Performative prediction in a stateful world”  In _arXiv preprint arXiv:2011.03885_ , 2020
  * [BS19] Noam Brown and Tuomas Sandholm  “Superhuman AI for multiplayer poker”  In _Science_ 365.6456 American Association for the Advancement of Science, 2019, pp. 885–890
  * [Car+19] Micah Carroll et al.  “On the utility of learning about humans for human-ai coordination”  In _Advances in neural information processing systems_ 32, 2019
  * [Cra+18] Jacob W Crandall et al.  “Cooperating with machines”  In _Nature communications_ 9.1 Nature Publishing Group, 2018, pp. 1–12
  * [CSE18] Allison JB Chaney, Brandon M Stewart and Barbara E Engelhardt  “How algorithmic confounding in recommendation systems increases homogeneity and decreases utility”  In _Proceedings of the 12th ACM Conference on Recommender Systems_ , 2018, pp. 224–232
  * [CSZ20] 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_ , 2020, pp. 1843–1854  PMLR
  * [DH13] Ofer Dekel and Elad Hazan  “Better rates for any adversarial deterministic MDP”  In _International Conference on Machine Learning_ , 2013, pp. 675–683  PMLR
  * [Dim+17] Christos Dimitrakakis, David C Parkes, Goran Radanovic and Paul Tylkin  “Multi-view decision processes: the helper-ai problem”  In _Advances in Neural Information Processing Systems_ 30, 2017
  * [Dom+21] Omar Darwiche Domingues et al.  “A kernel-based approach to non-stationary reinforcement learning in metric spaces”  In _International Conference on Artificial Intelligence and Statistics_ , 2021, pp. 3538–3546  PMLR
  * [EKM04] Eyal Even-Dar, Sham M Kakade and Yishay Mansour  “Experts in a Markov decision process”  In _Advances in neural information processing systems_ 17, 2004
  * [Est+19] Andre Esteva et al.  “A guide to deep learning in healthcare”  In _Nature medicine_ 25.1 Nature Publishing Group, 2019, pp. 24–29
  * [Fei+20] Yingjie Fei, Zhuoran Yang, Zhaoran Wang and Qiaomin Xie  “Dynamic regret of policy optimization in non-stationary environments”  In _Advances in Neural Information Processing Systems_ 33, 2020, pp. 6743–6754
  * [FS96] Yoav Freund and Robert E Schapire  “Game theory, on-line prediction and boosting”  In _Proceedings of the ninth annual conference on Computational learning theory_ , 1996, pp. 325–332
  * [FSM10] Amir-massoud Farahmand, Csaba Szepesvári and Rémi Munos  “Error propagation for approximate policy and value iteration”  In _Advances in Neural Information Processing Systems_ 23, 2010
  * [FV12] Jerzy Filar and Koos Vrieze  “Competitive Markov decision processes”  Springer Science & Business Media, 2012
  * [Gli52] Irving L Glicksberg  “A further generalization of the Kakutani fixed point theorem, with application to Nash equilibrium points”  In _Proceedings of the American Mathematical Society_ 3.1 JSTOR, 1952, pp. 170–174
  * [GOA18] Pratik Gajane, Ronald Ortner and Peter Auer  “A sliding-window algorithm for markov decision processes with arbitrarily changing rewards and transitions”  In _arXiv preprint arXiv:1805.10066_ , 2018
  * [Han+20] Casper Hansen et al.  “Contextual and sequential user embeddings for large-scale music recommendation”  In _Fourteenth ACM conference on recommender systems_ , 2020, pp. 53–62
  * [Hua+22] Peide Huang, Mengdi Xu, Fei Fang and Ding Zhao  “Robust Reinforcement Learning as a Stackelberg Game via Adaptively-Regularized Adversarial Training”  In _arXiv preprint arXiv:2202.09514_ , 2022
  * [Kar+17] Debarun Kar et al.  “Cloudy with a chance of poaching: Adversary behavior modeling and forecasting with real-world poaching data”  ACM, 2017
  * [Let+12] Joshua Letchford et al.  “Computing optimal strategies to commit to in stochastic games”  In _Twenty-Sixth AAAI Conference on Artificial Intelligence_ , 2012
  * [Lev+20] Sergey Levine, Aviral Kumar, George Tucker and Justin Fu  “Offline reinforcement learning: Tutorial, review, and perspectives on open problems”  In _arXiv preprint arXiv:2005.01643_ , 2020
  * [Lyk+21] Thodoris Lykouris, Max Simchowitz, Alex Slivkins and Wen Sun  “Corruption-robust exploration in episodic reinforcement learning”  In _Conference on Learning Theory_ , 2021, pp. 3242–3245  PMLR
  * [Man+20] Masoud Mansoury et al.  “Feedback loop and bias amplification in recommender systems”  In _Proceedings of the 29th ACM international conference on information & knowledge management_, 2020, pp. 2145–2148
  * [Men+20] Celestine Mendler-Dünner, Juan Perdomo, Tijana Zrnic and Moritz Hardt  “Stochastic optimization for performative prediction”  In _Advances in Neural Information Processing Systems_ 33, 2020, pp. 4929–4939
  * [Mni+16] Volodymyr Mnih et al.  “Asynchronous methods for deep reinforcement learning”  In _International conference on machine learning_ , 2016, pp. 1928–1937  PMLR
  * [MPZ21] John P Miller, Juan C Perdomo and Tijana Zrnic  “Outside the echo chamber: Optimizing the performative risk”  In _International Conference on Machine Learning_ , 2021, pp. 7710–7720  PMLR
  * [MS08] Rémi Munos and Csaba Szepesvári  “Finite-Time Bounds for Fitted Value Iteration.”  In _Journal of Machine Learning Research_ 9.5, 2008
  * [MVV20] Rajesh K Mishra, Deepanshu Vasal and Sriram Vishwanath  “Model-free reinforcement learning for stochastic stackelberg security games”  In _2020 59th IEEE Conference on Decision and Control (CDC)_ , 2020, pp. 348–353  IEEE
  * [Nar+22] Adhyyan Narang et al.  “Multiplayer Performative Prediction: Learning in Decision-Dependent Games”  In _arXiv preprint arXiv:2201.03398_ , 2022
  * [NGS12] Gergely Neu, Andras Gyorgy and Csaba Szepesvári  “The adversarial stochastic shortest path problem with unknown transition probabilities”  In _Artificial Intelligence and Statistics_ , 2012, pp. 805–813  PMLR
  * [Nik+17] Stefanos Nikolaidis, Swaprava Nath, Ariel D Procaccia and Siddhartha Srinivasa  “Game-theoretic modeling of human adaptation in human-robot collaboration”  In _Proceedings of the 2017 ACM/IEEE international conference on human-robot interaction_ , 2017, pp. 323–331
  * [Nik+17a] Stefanos Nikolaidis, Swaprava Nath, Ariel D Procaccia and Siddhartha Srinivasa  “Game-theoretic modeling of human adaptation in human-robot collaboration”  In _Proceedings of the 2017 ACM/IEEE international conference on human-robot interaction_ , 2017, pp. 323–331
  * [NJG17] Gergely Neu, Anders Jonsson and Vicenç Gómez  “A unified view of entropy-regularized markov decision processes”  In _arXiv preprint arXiv:1705.07798_ , 2017
  * [Per+20] Juan Perdomo, Tijana Zrnic, Celestine Mendler-Dünner and Moritz Hardt  “Performative prediction”  In _International Conference on Machine Learning_ , 2020, pp. 7599–7609  PMLR
  * [Rad+19] Goran Radanovic, Rati Devidze, David Parkes and Adish Singla  “Learning to collaborate in markov decision processes”  In _International Conference on Machine Learning_ , 2019, pp. 5261–5270  PMLR
  * [RM19] Aviv Rosenberg and Yishay Mansour  “Online convex optimization in adversarial markov decision processes”  In _International Conference on Machine Learning_ , 2019, pp. 5478–5486  PMLR
  * [RMK20] Aravind Rajeswaran, Igor Mordatch and Vikash Kumar  “A game theoretic framework for model based reinforcement learning”  In _International conference on machine learning_ , 2020, pp. 7953–7963  PMLR
  * [Ses+20] Pier Giuseppe Sessa, Ilija Bogunovic, Maryam Kamgarpour and Andreas Krause  “Learning to play sequential games versus unknown opponents”  In _Advances in Neural Information Processing Systems_ 33, 2020, pp. 8971–8981
  * [Sha53] Lloyd S Shapley  “Stochastic games”  In _Proceedings of the national academy of sciences_ 39.10 National Acad Sciences, 1953, pp. 1095–1100
  * [Sil+17] David Silver et al.  “Mastering the game of go without human knowledge”  In _nature_ 550.7676 Nature Publishing Group, 2017, pp. 354–359
  * [SKT16] Arunesh Sinha, Debarun Kar and Milind Tambe  “Learning Adversary Behavior in Security Games: A PAC Model Perspective”  In _Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems_, 2016, pp. 214–222
  * [TSR21] Stelios Triantafyllou, Adish Singla and Goran Radanovic  “On Blame Attribution for Accountable Multi-Agent Sequential Decision Making”  In _Advances in Neural Information Processing Systems_ 34, 2021
  * [Ver10] Roman Vershynin  “Introduction to the non-asymptotic analysis of random matrices”  In _arXiv preprint arXiv:1011.3027_ , 2010
  * [Vin+19] Oriol Vinyals et al.  “Grandmaster level in StarCraft II using multi-agent reinforcement learning”  In _Nature_ 575.7782 Nature Publishing Group, 2019, pp. 350–354
  * [Vol+19] Cameron Voloshin, Hoang M Le, Nan Jiang and Yisong Yue  “Empirical study of off-policy policy evaluation for reinforcement learning”  In _arXiv preprint arXiv:1911.06854_ , 2019
  * [Von10] Heinrich Von Stackelberg  “Market structure and equilibrium”  Springer Science & Business Media, 2010
  * [VS12] Yevgeniy Vorobeychik and Satinder Singh  “Computing stackelberg equilibria in discounted stochastic games”  In _Proceedings of the AAAI Conference on Artificial Intelligence_ 26.1, 2012, pp. 1478–1484
  * [WL21] Chen-Yu Wei and Haipeng Luo  “Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach”  In _Conference on Learning Theory_ , 2021, pp. 4300–4354  PMLR
  * [XJ21] Tengyang Xie and Nan Jiang  “Batch value-function approximation with only realizability”  In _International Conference on Machine Learning_ , 2021, pp. 11404–11413  PMLR
  * [Zha+22] Wenhao Zhan et al.  “Offline reinforcement learning with realizability and single-policy concentrability”  In _arXiv preprint arXiv:2202.04634_ , 2022
  * [Zho+21] 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?”  In _arXiv preprint arXiv:2112.13521_ , 2021
  * [ZYB21] Kaiqing Zhang, Zhuoran Yang and Tamer Başar  “Multi-agent reinforcement learning: A selective overview of theories and algorithms”  In _Handbook of Reinforcement Learning and Control_ Springer, 2021, pp. 321–384

##  Appendix A Additional Information on Experimental Setup and Results

In this section, we provide additional information on the experimental setup
(Section A.1), as well as additional experimental results (Section A.2). We
also provide information regarding the total amount of compute time and the
type of resources that were used (Section A.3).

###  A.1 Additional Information on Experimental Setup

Gridworld: The initial state of the actor in the grid-world is selected
uniformly at random from the cells denoted by $S$. Additionally, the actor
remains at its current cell in case it attempts a move that would lead it
outside the grid-world. Regarding the reward function, all the agents receive
a positive reward equal to $+1$ whenever the actor reaches the terminal state
$G$.

Response Model: The response model of a follower agent is based on a perturbed
grid-world instead of the one in Fig. 8. In other words, each of the $n$
follower agents sees different cell costs than the ones $A_{1}$ sees. As a
result, they might respond to the policy of $A_{1}$, by adopting a policy that
performs unnecessary or even harmful interventions w.r.t. the grid-world of
Fig. 8. A perturbed grid-world is generated from the grid-world of Fig. 8 with
the following procedure. First, $G$ and $S$ cells stay the same between the
two grid-worlds. Then, any blank, $F$ or $H$ cell remains unchanged with
probability $0.7$, and with probability $0.3$ we perturb its type to blank ,
$F$ or $H$ (the perturbation is done uniformly at random).

###  A.2 Additional Experimental Results

In this section, we provide additional insights on the interventional policies
of the follower agents. The repeated retraining method we use in these
experiments is the repeated policy optimization. More specifically, we present
a visual representation of the limiting environment i.e. the majority of the
agents’ policy in the limit, i.e., after the method has converged to a stable
solution. The configurations are set to $\lambda=1$, $\beta=5$, and we vary
discount factor $\gamma$.

As mentioned in Section 4, the policy of the follower agents can be thought of
as a changing environment that responds to the policy updates of $A_{1}$. To
visualize how this environment looks like in the limit, we depict in Figure 11
several limiting policies of the follower agents. From the Figures 11, and 11
we observe that for smaller discount factor, the majority of the follower
agents tend to intervene closer to the goal state.

Figure 9: $\gamma=0.5$

Figure 10: $\gamma=0.9$

Figure 11:  Figures 11, and 11 visualize two instances of the interventional
policy of agent $A_{2}$ in the Gridworld environment. All figures correspond
to the majority of the followers’ policy at convergence for various values of
the discount factor $\gamma$. Empty cells denote states where majority of the
agents’ most probable action is to not intervene. For cells with a red arrow
the (highest probability) action of the majority of the follower agents is to
intervene by forcing the actor to move one cell towards the direction of the
arrow.

###  A.3 Total Amount of Compute and Type of Resources

All experiments were conducted on a computer cluster with machines equipped
with $2$ Intel Xeon E5-2667 v2 CPUs with 3.3GHz (16 cores) and 50 GB RAM.
Table 1 reports the total computation times for our experiments (Section 4).
Note that at each iteration of the repeated gradient ascent experiment, apart
from the gradient step a full solution of the optimization problem 7 was also
computed, in order to report the suboptimality gap.

Repeated Policy Optimization |  $767$ sec
---|---
Repeated Gradient Ascent |  $964$ sec
Repeated Policy Optimization with Finite Samples | 33746 sec
Repeated Gradient Ascent with Finite Samples | 35396 sec
Table 1: Total computation times for the different experiments described in
Section 4.

##  Appendix B Missing Proofs

###  B.1 Proof of Convergence of Repeated Maximization (Theorem 1)

###### Proof.

We first compute the dual of the concave optimization problem 7. The
Lagrangian is given as

$\displaystyle\mathcal{L}(d,h)=d^{\top}r_{t}-\frac{\lambda}{2}\left\lVert
d\right\rVert_{2}^{2}+\sum_{s}h(s)\left(-\sum_{a}d(s,a)+\rho(s)+\gamma\cdot\sum_{s^{\prime},a}d(s^{\prime},a)P_{t}(s^{\prime},a,s)\right)$

At an optimal solution we must have $\nabla_{d}\mathcal{L}(d,h)=0$, which
gives us the following expression for $d$.

$\displaystyle
d(s,a)=\frac{r_{t}(s,a)}{\lambda}-\frac{h(s)}{\lambda}+\frac{\gamma}{\lambda}\sum_{\widetilde{s}}h(\widetilde{s})P_{t}(s,a,\widetilde{s})$
(13)

Substituting the above value of $d$ we get the following dual problem.

$\displaystyle\begin{split}\min_{h\in\mathbb{R}^{S}}\
&-\frac{1}{\lambda}\sum_{s,a}h(s)r_{t}(s,a)+\frac{\gamma}{\lambda}\sum_{s}\sum_{s^{\prime},a}h(s)r_{t}(s^{\prime},a)P_{t}(s^{\prime},a,s)+\sum_{s}h(s)\rho(s)\\\
&+\frac{A}{2\lambda}\sum_{s}h(s)^{2}-\frac{\gamma}{\lambda}\sum_{s,a}h(s)\sum_{\widetilde{s}}h(\widetilde{s})P_{t}(s,a,\widetilde{s})+\frac{\gamma^{2}}{2\lambda}\sum_{s,a}\sum_{\widetilde{s},\hat{s}}h(\widetilde{s})h(\hat{s})P_{t}(s,a,\hat{s})P_{t}(s,a,\widetilde{s})\end{split}$
(14)

Note that the dual objective is parameterized by reward function $r_{t}$ and
probability transition function $P_{t}$ which are the parameters corresponding
to the occupancy measure $d_{t}$. We will write $\mathcal{L}(\cdot;M_{t})$ to
denote this dual objective function.

For a given occupancy measure (i.e. $d_{t}=d$) we will write $\mathrm{GD}(d)$
to denote the optimal solution to the primal problem 7. We first aim to show
that the operator $\mathrm{GD}(\cdot)$ is a contraction mapping. Consider two
occupancy measures $d$ and $\hat{d}$. Let $r$ (resp. $\hat{r}$) be the reward
functions in response to the occupancy measure $d$ (resp. $\hat{d}$).
Similarly, let $P$ (resp. $\hat{P}$) be the probability transition function in
response to the occupancy measure $d$ (resp. $\hat{d}$).

Let $h$ (resp. $\hat{h}$) be the optimal dual solutions corresponding to the
occupancy measures $d$ (resp. $\hat{d}$) i.e.
$h\in\operatorname*{arg\,max}_{h^{\prime}}\mathcal{L}(h^{\prime};M)$ and
$\hat{h}\in\operatorname*{arg\,max}_{h^{\prime}}\mathcal{L}(h^{\prime};\hat{M})$.
Lemma 2 proves that the objective is $A(1-\gamma)^{2}/\lambda$ strongly
convex. Therefore, we have the following two inequalities.

$\displaystyle\mathcal{L}(h;M)-\mathcal{L}(\hat{h};M)\geq\left(h-\hat{h}\right)^{\top}\nabla\mathcal{L}(\hat{h};M)+\frac{A(1-\gamma)^{2}}{2\lambda}\left\lVert
h-\hat{h}\right\rVert_{2}^{2}$ (15)
$\displaystyle\mathcal{L}(\hat{h};M)-\mathcal{L}(h;M)\geq\frac{A(1-\gamma)^{2}}{2\lambda}\left\lVert
h-\hat{h}\right\rVert_{2}^{2}$ (16)

These two inequalities give us the following bound.

$-\frac{A(1-\gamma)^{2}}{\lambda}\left\lVert
h-\hat{h}\right\rVert_{2}^{2}\geq(h-\hat{h})^{\top}\nabla\mathcal{L}(\hat{h};M)$
(17)

We now bound the Lipschitz constant of the term
$(h-\hat{h})^{\top}\mathcal{L}_{d}(\hat{h};M)$ with respect to the MDP $M$.
Lemma 3 gives us the following bound.

$\left\lVert\nabla\mathcal{L}(\hat{h};M)-\nabla\mathcal{L}(\hat{h};\hat{M})\right\rVert_{2}\leq\frac{4S\sqrt{A}}{\lambda}\left\lVert
r-\hat{r}\right\rVert_{2}+\left(\frac{4\gamma\sqrt{SA}}{\lambda}+\frac{6\gamma\sqrt{A}S}{\lambda}\left\lVert\hat{h}\right\rVert_{2}\right)\left\lVert
P-\hat{P}\right\rVert_{2}$

Now notice that the dual variable $\hat{h}$ is actually an optimal solution
and we can use lemma 4 to bound its norm by $\frac{3S}{(1-\gamma)^{2}}$.
Furthermore, under assumption 1, we have $\left\lVert
r-\hat{r}\right\rVert_{2}\leq\epsilon_{r}\left\lVert
d-\hat{d}\right\rVert_{2}$ and $\left\lVert
P-\hat{P}\right\rVert_{2}\leq\epsilon_{p}\left\lVert
d-\hat{d}\right\rVert_{2}$. Substituting these bounds we get the following
inequality.

$\displaystyle\left\lVert\nabla\mathcal{L}(\hat{h};M)-\nabla\mathcal{L}(\hat{h};\hat{M})\right\rVert_{2}\leq\frac{4S\sqrt{A}}{\lambda}\epsilon_{r}\left\lVert
d-\hat{d}\right\rVert_{2}+\left(\frac{4\gamma\sqrt{SA}}{\lambda}+\frac{6\gamma\sqrt{A}S}{\lambda}\frac{3S}{(1-\gamma)^{2}}\right)\epsilon_{p}\left\lVert
d-\hat{d}\right\rVert_{2}$
$\displaystyle\leq\left(\frac{4S\sqrt{A}\epsilon_{r}}{\lambda}+\frac{10\gamma
S^{2}\sqrt{A}\epsilon_{p}}{\lambda(1-\gamma)^{2}}\right)\left\lVert
d-\hat{d}\right\rVert_{2}$

We now substitute the above bound in equation 17.

$\displaystyle-\frac{A(1-\gamma)^{2}}{\lambda}\left\lVert
h-\hat{h}\right\rVert_{2}^{2}\geq(h-\hat{h})^{\top}\nabla\mathcal{L}(\hat{h};M)$
$\displaystyle=(h-\hat{h})^{\top}\left(\nabla\mathcal{L}(\hat{h};M)-\nabla\mathcal{L}(\hat{h};\hat{M})\right)\
\textrm{[As $\hat{h}$ is optimal for $\mathcal{L}(\cdot;\hat{M})$]}$
$\displaystyle\geq-\left\lVert
h-\hat{h}\right\rVert_{2}\left\lVert\nabla\mathcal{L}(\hat{h};M)-\nabla\mathcal{L}(\hat{h};\hat{M})\right\rVert_{2}$
$\displaystyle\geq-\left\lVert
h-\hat{h}\right\rVert_{2}\left(\frac{4S\sqrt{A}\epsilon_{r}}{\lambda}+\frac{10\gamma
S^{2}\sqrt{A}\epsilon_{p}}{\lambda(1-\gamma)^{2}}\right)\left\lVert
d-\hat{d}\right\rVert_{2}$

Rearranging we get the following inequality.

$\displaystyle\left\lVert
h-\hat{h}\right\rVert_{2}\leq\frac{\lambda}{A(1-\gamma)^{2}}\left(\frac{4S\sqrt{A}\epsilon_{r}}{\lambda}+\frac{10\gamma
S^{2}\sqrt{A}\epsilon_{p}}{\lambda(1-\gamma)^{2}}\right)\left\lVert
d-\hat{d}\right\rVert_{2}$

Recall that $\mathrm{GD}(d)$ (resp. $\mathrm{GD}(\hat{d})$) are the optimal
solution corresponding to the primal problem when the deployed occupancy
measure is $d$ (resp. $\hat{d}$). Therefore, we can apply lemma 1 to obtain
the following bound.

$\displaystyle\left\lVert\mathrm{GD}(d)-\mathrm{GD}(\hat{d})\right\rVert_{2}\leq\left(1+\frac{4\epsilon_{r}+6\epsilon_{p}\left\lVert\hat{h}\right\rVert_{2}}{\lambda}\right)\frac{3\sqrt{AS}}{\lambda}\left\lVert
h-\hat{h}\right\rVert_{2}$
$\displaystyle\leq\left(1+\frac{4\epsilon_{r}+6\epsilon_{p}\cdot
3S/(1-\gamma)^{2}}{\lambda}\right)\frac{3\sqrt{AS}}{\lambda}\frac{\lambda}{A(1-\gamma)^{2}}\left(\frac{4S\sqrt{A}\epsilon_{r}}{\lambda}+\frac{10\gamma
S^{2}\sqrt{A}\epsilon_{p}}{\lambda(1-\gamma)^{2}}\right)\left\lVert
d-\hat{d}\right\rVert_{2}$
$\displaystyle\leq\underbrace{\left(1+\frac{4\epsilon_{r}+6\epsilon_{p}\cdot
3S/(1-\gamma)^{2}}{\lambda}\right)\frac{3\sqrt{S}}{\sqrt{A}(1-\gamma)^{2}}\left(\frac{4S\sqrt{A}\epsilon_{r}}{\lambda}+\frac{10\gamma
S^{2}\sqrt{A}\epsilon_{p}}{\lambda(1-\gamma)^{2}}\right)}_{:=\beta}\left\lVert
d-\hat{d}\right\rVert_{2}$

Now it can be easily verified that if
$\lambda>12S^{3/2}(1-\gamma)^{-4}(2\epsilon_{r}+5S\epsilon_{p})$ then
$\beta=\frac{12S^{3/2}(2\epsilon_{r}+5S\epsilon_{p})}{\lambda(1-\gamma)^{4}}<1$.
This implies that the operator $\mathrm{GD}(\cdot)$ is a contraction mapping
and the sequence of iterates $\\{d_{t}\\}_{t\geq 1}$ converges to a fixed
point. In order to determine the speed of convergence let us substitute
$d=d_{t}$ and $\hat{d}=d_{S}$. This gives us
$\left\lVert\mathrm{GD}(d_{t})-d_{S}\right\rVert_{2}\leq\beta\left\lVert
d_{t}-d_{S}\right\rVert_{2}$. As $\mathrm{GD}(d_{t})=d_{t+1}$ we have
$\left\lVert d_{t+1}-d_{S}\right\rVert_{2}\leq\beta\left\lVert
d_{t}-d_{S}\right\rVert_{2}$. After $t$ iterations we have $\left\lVert
d_{t}-d_{S}\right\rVert_{2}\leq\beta^{t}\left\lVert
d_{0}-d_{S}\right\rVert_{2}$. Therefore, if $t\geq\ln\left(\left\lVert
d_{0}-d_{S}\right\rVert_{2}/\delta\right)/\ln(1/\beta)$ we are guaranteed that
$\left\lVert d_{t}-d_{S}\right\rVert_{2}\leq{\delta}$. Since $\left\lVert
d_{0}-d_{S}\right\rVert_{2}\leq\frac{2}{1-\gamma}$, the desired upper bound on
the number of iterations becomes the following.

$\displaystyle\frac{\ln\left(\left\lVert
d_{0}-d_{S}\right\rVert_{2}/{\delta}\right)}{\ln(1/\beta)}\leq
2\left(1-\beta\right)^{-1}\ln\left(\frac{2}{\delta(1-\gamma)}\right)$

∎

######  Lemma 1.

Consider two state-action occupancy measures $d$ and $\hat{d}$. Let
$\lambda\geq
2\left(2\epsilon_{r}+3\epsilon_{p}\left\lVert\hat{h}\right\rVert_{2}\right)$.
Then we have the following bound.

$\left\lVert
d-\hat{d}\right\rVert_{2}\leq\left(1+\frac{4\epsilon_{r}+6\epsilon_{p}\left\lVert\hat{h}\right\rVert_{2}}{\lambda}\right)\frac{3\sqrt{AS}}{\lambda}\left\lVert
h-\hat{h}\right\rVert_{2}$

###### Proof.

Recall the relationship between the dual and the primal variables.

$d(s,a)=\frac{r_{t}(s,a)}{\lambda}-\frac{h(s)}{\lambda}+\frac{\gamma}{\lambda}\sum_{\widetilde{s}}h(\widetilde{s})P(s,a,\widetilde{s})$

This gives us the following bound on the difference
$(d(s,a)-\hat{d}(s,a))^{2}$.

$\displaystyle\left(d(s,a)-\hat{d}(s,a)\right)^{2}$
$\displaystyle\leq\frac{3}{\lambda^{2}}\left(r(s,a)-\hat{r}(s,a)\right)^{2}+\frac{1}{\lambda^{2}}\left(h(s)-\hat{h}(s)\right)^{2}$
$\displaystyle+\frac{3\gamma^{2}}{\lambda^{2}}\left(\sum_{s^{\prime}}h(s^{\prime})P(s,a,s^{\prime})-\sum_{s^{\prime}}\hat{h}(s^{\prime})\hat{P}(s,a,s^{\prime})\right)^{2}\
\textrm{[By Jensen's inequality]}$
$\displaystyle=\frac{3}{\lambda^{2}}\left(r(s,a)-\hat{r}(s,a)\right)^{2}+\frac{1}{\lambda^{2}}\left(h(s)-\hat{h}(s)\right)^{2}$
$\displaystyle+\frac{3}{\lambda^{2}}\left(\sum_{s^{\prime}}\left(h(s^{\prime})-\hat{h}(s^{\prime})\right)P(s,a,s^{\prime})+\hat{h}(s^{\prime})\left(P(s,a,s^{\prime})-\hat{P}(s,a,s^{\prime})\right)\right)^{2}$
$\displaystyle\leq\frac{3}{\lambda^{2}}\left(r(s,a)-\hat{r}(s,a)\right)^{2}+\frac{1}{\lambda^{2}}\left(h(s)-\hat{h}(s)\right)^{2}$
$\displaystyle+\frac{6}{\lambda^{2}}\left(\sum_{s^{\prime}}\left(h(s^{\prime})-\hat{h}(s^{\prime})\right)P(s,a,s^{\prime})\right)^{2}$
$\displaystyle+\frac{6}{\lambda^{2}}\left(\sum_{s^{\prime}}\hat{h}(s^{\prime})\left(P(s,a,s^{\prime})-\hat{P}(s,a,s^{\prime})\right)\right)^{2}\
\textrm{[By Jensen's inequality]}$
$\displaystyle\leq\frac{3}{\lambda^{2}}\left(r(s,a)-\hat{r}(s,a)\right)^{2}+\frac{1}{\lambda^{2}}\left(h(s)-\hat{h}(s)\right)^{2}$
$\displaystyle+\frac{6}{\lambda^{2}}\left\lVert
h-\hat{h}\right\rVert_{2}^{2}+\frac{6}{\lambda^{2}}\left\lVert\hat{h}\right\rVert_{2}^{2}\sum_{s^{\prime}}\left(P(s,a,s^{\prime})-\hat{P}(s,a,s^{\prime})\right)^{2}\
\textrm{[By Cauchy-Schwarz inequality]}$

Now summing over $s$ and $a$ we get the following bound.

$\left\lVert d-\hat{d}\right\rVert_{2}^{2}\leq\frac{3}{\lambda^{2}}\left\lVert
r-\hat{r}\right\rVert_{2}^{2}+\frac{7AS}{\lambda^{2}}\left\lVert
h-\hat{h}\right\rVert_{2}^{2}+\frac{6}{\lambda^{2}}\left\lVert\hat{h}\right\rVert_{2}^{2}\left\lVert
P-\hat{P}\right\rVert_{2}^{2}$

We now use the assumptions $\left\lVert
r-\hat{r}\right\rVert_{2}\leq\epsilon_{r}\left\lVert
d-\hat{d}\right\rVert_{2}$ and $\left\lVert
P-\hat{P}\right\rVert_{2}\leq\epsilon_{p}\left\lVert
d-\hat{d}\right\rVert_{2}$.

$\displaystyle\left\lVert
d-\hat{d}\right\rVert_{2}\leq\frac{2\epsilon_{r}}{\lambda}\left\lVert
d-\hat{d}\right\rVert_{2}+\frac{3\sqrt{AS}}{\lambda}\left\lVert
h-\hat{h}\right\rVert_{2}+\frac{3\epsilon_{p}}{\lambda}\left\lVert\hat{h}\right\rVert_{2}\left\lVert
d-\hat{d}\right\rVert_{2}$

Rearranging we get the following bound.

$\displaystyle\left\lVert
d-\hat{d}\right\rVert_{2}\leq\left(1-\frac{2\epsilon_{r}+3\epsilon_{p}\left\lVert\hat{h}\right\rVert_{2}}{\lambda}\right)^{-1}\frac{3\sqrt{AS}}{\lambda}\left\lVert
h-\hat{h}\right\rVert_{2}\leq\left(1+\frac{4\epsilon_{r}+6\epsilon_{p}\left\lVert\hat{h}\right\rVert_{2}}{\lambda}\right)\frac{3\sqrt{AS}}{\lambda}\left\lVert
h-\hat{h}\right\rVert_{2}$

The last inequality uses the fact that $\lambda\geq
2(2\epsilon_{r}+3\epsilon_{p}\left\lVert\hat{h}\right\rVert_{2})$. ∎

######  Lemma 2.

The dual objective $\mathcal{L}_{d}$ (as defined in 14) is
$\frac{A(1-\gamma)^{2}}{\lambda}$-strongly convex.

###### Proof.

The derivative of the dual objective $\mathcal{L}_{d}$ with respect to $h(s)$
is given as follows.

$\displaystyle\begin{split}\frac{\partial\mathcal{L}_{d}(h)}{\partial
h(s)}&=-\frac{1}{\lambda}\sum_{a}r_{t}(s,a)+\frac{\gamma}{\lambda}\sum_{s^{\prime},a}r_{t}(s^{\prime},a)P_{t}(s^{\prime},a,s)+\rho(s)+\frac{A}{\lambda}h(s)\\\
&-\frac{\gamma}{\lambda}\sum_{\widetilde{s},a}h(\widetilde{s})\left(P_{t}(s,a,\widetilde{s})+P_{t}(\widetilde{s},a,s)\right)+\frac{\gamma^{2}}{\lambda}\sum_{s^{\prime},a,\widetilde{s}}h(\widetilde{s})P_{t}(s^{\prime},a,\widetilde{s})P_{t}(s^{\prime},a,s)\end{split}$
(18)

This gives us the following identity.

$\displaystyle\left(\nabla\mathcal{L}_{d}(h)-\nabla\mathcal{L}_{d}(\widetilde{h})\right)^{\top}(h-\widetilde{h})$
$\displaystyle=\frac{A}{\lambda}\left\lVert
h-\widetilde{h}\right\rVert_{2}^{2}$
$\displaystyle-\frac{\gamma}{\lambda}\sum_{s,\widetilde{s},a}(h(s)-\widetilde{h}(s))\left(P_{t}(s,a,\widetilde{s})+P_{t}(\widetilde{s},a,s)\right)(h(\widetilde{s})-\widetilde{h}(\widetilde{s}))$
$\displaystyle+\frac{\gamma^{2}}{\lambda}\sum_{s^{\prime},a}\sum_{s,\widetilde{s}}(h(s)-\widetilde{h}(\widetilde{s}))P_{t}(s^{\prime},a,\widetilde{s})P_{t}(s^{\prime},a,s)(h(s)-\widetilde{h}(s))$

Let us now define the matrix $M_{a}\in\mathbb{R}^{S\times S}$ with entries
$M_{a}(s,s^{\prime})=P_{t}(s,a,s^{\prime})$.

$\displaystyle\left(\nabla\mathcal{L}_{d}(h)-\nabla\mathcal{L}_{d}(\widetilde{h})\right)^{\top}(h-\widetilde{h})=\frac{A}{\lambda}\left\lVert
h-\widetilde{h}\right\rVert_{2}^{2}$
$\displaystyle-\frac{\gamma}{\lambda}\sum_{a}(h-\widetilde{h})^{\top}\left(M_{a}+M_{a}^{\top}\right)(h-\widetilde{h})+\frac{\gamma^{2}}{\lambda}\sum_{a}(h-\widetilde{h})^{\top}M_{a}^{\top}M_{a}(h-\widetilde{h})$
$\displaystyle=\frac{1}{\lambda}\sum_{a}(h-\widetilde{h})^{\top}\left(\textrm{Id}-\gamma
M_{a}-\gamma M_{a}^{\top}+\gamma^{2}M_{a}^{\top}M_{a}\right)(h-\widetilde{h})$
$\displaystyle\geq\frac{A(1-\gamma)^{2}}{\lambda}\left\lVert
h-\widetilde{h}\right\rVert_{2}^{2}$

The last inequality uses lemma 5. ∎

######  Lemma 3.

The dual function $\mathcal{L}_{d}$ (as defined in eq. 14) satisfies the
following bound for any $h$ and MDP $M,\widehat{M}$.

$\left\lVert\nabla\mathcal{L}_{d}(h,M)-\nabla\mathcal{L}_{d}(h,\widehat{M})\right\rVert_{2}\leq\frac{4S\sqrt{A}}{\lambda}\left\lVert
r-\hat{r}\right\rVert_{2}+\left(\frac{4\gamma\sqrt{SA}}{\lambda}+\frac{6\gamma
S\sqrt{A}}{\lambda}\left\lVert h\right\rVert_{2}\right)\left\lVert
P-\hat{P}\right\rVert_{2}$

###### Proof.

From the expression of the derivative of $\mathcal{L}_{d}$ with respect to $h$
(eq. 18) we get the following bound.

$\displaystyle\left\lVert\nabla\mathcal{L}_{d}(h,M)-\nabla\mathcal{L}_{d}(h,\widehat{M})\right\rVert_{2}^{2}=\sum_{s}\left\\{-\frac{1}{\lambda}\sum_{a}(r(s,a)-\hat{r}(s,a))\right.$
$\displaystyle+\frac{\gamma}{\lambda}\sum_{s^{\prime},a}\left(r(s^{\prime},a)P(s^{\prime},a,s)-\hat{r}(s^{\prime},a)\hat{P}(s^{\prime},a,s)\right)-\frac{\gamma}{\lambda}\sum_{\widetilde{s},a}h(\widetilde{s})(P(\widetilde{s},a,s)-\hat{P}(\widetilde{s},a,s))$
$\displaystyle-\left.\frac{\gamma}{\lambda}\sum_{\widetilde{s},a}h(\widetilde{s})(P(s,a,\widetilde{s})-\hat{P}(s,a,\widetilde{s}))+\frac{\gamma^{2}}{\lambda}\sum_{s^{\prime},a,\widetilde{s}}h(\widetilde{s})\left(P(s^{\prime},a,\widetilde{s})P(s^{\prime},a,s)-\hat{P}(s^{\prime},a,\widetilde{s})\hat{P}(s^{\prime},a,s)\right)\right\\}$
$\displaystyle\leq\frac{5A}{\lambda^{2}}\left\lVert
r-\hat{r}\right\rVert_{2}^{2}+\frac{5\gamma^{2}}{\lambda^{2}}\sum_{s}\left(\sum_{s^{\prime},a}\left(r(s^{\prime},a)P(s^{\prime},a,s)-\hat{r}(s^{\prime},a)\hat{P}(s^{\prime},a,s)\right)\right)^{2}$
$\displaystyle+\frac{5\gamma^{2}}{\lambda^{2}}\sum_{s}\left(\sum_{\widetilde{s},a}h(s)(P(\widetilde{s},a,s)-\hat{P}(\widetilde{s},a,s))\right)^{2}+\frac{5\gamma^{2}}{\lambda^{2}}\sum_{s}\left(\sum_{\widetilde{s},a}h(\widetilde{s})(P(s,a,\widetilde{s})-\hat{P}(s,a,\widetilde{s}))\right)^{2}$
$\displaystyle+\frac{5\gamma^{4}}{\lambda^{2}}\sum_{s}\left(\sum_{s^{\prime},a,\widetilde{s}}h(\widetilde{s})\left(P(s^{\prime},a,\widetilde{s})P(s^{\prime},a,s)-\hat{P}(s^{\prime},a,\widetilde{s})\hat{P}(s^{\prime},a,s)\right)\right)^{2}$

We now use four bounds to complete the proof. The following bounds use
Jensen’s inequality and Cauchy-Schwarz inequality.

$\displaystyle\textrm{Bound
1}:\sum_{s^{\prime},a}\left(r(s^{\prime},a)P(s^{\prime},a,s)-\hat{r}(s^{\prime},a)\hat{P}(s^{\prime},a,s)\right)$
$\displaystyle\leq\sum_{s^{\prime},a}\left|r(s^{\prime},a)-\hat{r}(s^{\prime},a)\right|P(s^{\prime},a,s)+\hat{r}(s^{\prime},a)\left|P(s^{\prime},a,s)-\hat{P}(s^{\prime},a,s)\right|$
$\displaystyle\leq\left\lVert
r-\hat{r}\right\rVert_{1}+\sum_{s^{\prime},a}\left|P(s^{\prime},a,s)-\hat{P}(s^{\prime},a,s)\right|$
$\displaystyle\textrm{Bound
2}:\sum_{s}\left(\sum_{\widetilde{s},a}h(\widetilde{s})(P(\widetilde{s},a,s)-\hat{P}(\widetilde{s},a,s))\right)^{2}\leq
A\sum_{s}\sum_{\widetilde{s}}h(\widetilde{s})^{2}\sum_{\widetilde{s},a}\left(P(\widetilde{s},a,s)-\hat{P}(\widetilde{s},a,s)\right)^{2}$
$\displaystyle\leq A\left\lVert h\right\rVert_{2}^{2}\left\lVert
P-\hat{P}\right\rVert_{2}^{2}$ $\displaystyle\textrm{Bound
3}:\sum_{s}\left(\sum_{\widetilde{s},a}h(\widetilde{s})(P(s,a,\widetilde{s})-\hat{P}(s,a,\widetilde{s}))\right)^{2}\leq
A\sum_{s}\sum_{\widetilde{s}}h(\widetilde{s})^{2}\sum_{\widetilde{s},a}\left(P(s,a,\widetilde{s})-\hat{P}(s,a,\widetilde{s})\right)^{2}$
$\displaystyle\leq A\left\lVert h\right\rVert_{2}^{2}\left\lVert
P-\hat{P}\right\rVert_{2}^{2}$

$\displaystyle\textrm{Bound
4}:\sum_{s}\left(\sum_{s^{\prime},a,\widetilde{s}}h(\widetilde{s})\left(P(s^{\prime},a,\widetilde{s})P(s^{\prime},a,s)-\hat{P}(s^{\prime},a,\widetilde{s})\hat{P}(s^{\prime},a,s)\right)\right)^{2}$
$\displaystyle\leq\sum_{s}\sum_{\widetilde{s}}h(\widetilde{s})^{2}\sum_{\widetilde{s}}\left(\sum_{s^{\prime},a}\left(P(s^{\prime},a,\widetilde{s})P(s^{\prime},a,s)-\hat{P}(s^{\prime},a,\widetilde{s})\hat{P}(s^{\prime},a,s)\right)\right)^{2}$
$\displaystyle\leq SA\left\lVert
h\right\rVert_{2}^{2}\sum_{s,\widetilde{s}}\sum_{s^{\prime},a}\left(P(s^{\prime},a,\widetilde{s})P(s^{\prime},a,s)-\hat{P}(s^{\prime},a,\widetilde{s})\hat{P}(s^{\prime},a,s)\right)^{2}$
$\displaystyle\leq SA\left\lVert
h\right\rVert_{2}^{2}\sum_{s,\widetilde{s}}\sum_{s^{\prime},a}\left(P(s^{\prime},a,\widetilde{s})(P(s^{\prime},a,s)-\hat{P}(s^{\prime},a,s))+\hat{P}(s^{\prime},a,s)(P(s^{\prime},a,\widetilde{s})-\hat{P}(s^{\prime},a,\widetilde{s}))\right)$
$\displaystyle\leq 2SA\left\lVert
h\right\rVert_{2}^{2}\sum_{s,\widetilde{s}}\sum_{s^{\prime},a}\left|P(s^{\prime},a,s)-\hat{P}(s^{\prime},a,s)\right|^{2}+\left|P(s^{\prime},a,\widetilde{s})-\hat{P}(s^{\prime},a,\widetilde{s})\right|^{2}$
$\displaystyle\leq 4S^{2}A\left\lVert h\right\rVert_{2}^{2}\left\lVert
P-\hat{P}\right\rVert_{2}^{2}$

Using the four upper bounds shown above, we can complete the proof.

$\displaystyle\left\lVert\nabla\mathcal{L}_{d}(h,M)-\nabla\mathcal{L}_{d}(h,\widehat{M})\right\rVert_{2}^{2}\leq\frac{5A}{\lambda^{2}}\left\lVert
r-\hat{r}\right\rVert_{2}^{2}+\frac{5\gamma^{2}}{\lambda^{2}}\sum_{s}\left(\left\lVert
r-\hat{r}\right\rVert_{1}+\left\lVert
P(\cdot,\cdot,s)-\hat{P}(\cdot,\cdot,s)\right\rVert_{1}\right)^{2}$
$\displaystyle+\frac{10A\gamma^{2}}{\lambda^{2}}\left\lVert
h\right\rVert_{2}^{2}\left\lVert
P-\hat{P}\right\rVert_{2}^{2}+\frac{20S^{2}A\gamma^{4}}{\lambda^{2}}\left\lVert
h\right\rVert_{2}^{2}\left\lVert P-\hat{P}\right\rVert_{2}^{2}$
$\displaystyle\leq\left(\frac{5A}{\lambda^{2}}+\frac{10S^{2}A\gamma^{2}}{\lambda^{2}}\right)\left\lVert
r-\hat{r}\right\rVert_{2}^{2}+\left(\frac{10\gamma^{2}SA}{\lambda^{2}}+\frac{10A\gamma^{2}}{\lambda^{2}}\left\lVert
h\right\rVert_{2}^{2}+\frac{20S^{2}A\gamma^{4}}{\lambda^{2}}\left\lVert
h\right\rVert_{2}^{2}\right)\left\lVert P-\hat{P}\right\rVert_{2}^{2}$

∎

######  Lemma 4.

The norm of the optimal solution to the dual problem (defined in 14) is
bounded by $\frac{3S}{(1-\gamma)^{2}}$ for any choice of MDP $M$.

###### Proof.

The dual objective $\mathcal{L}_{d}$ is strongly-convex and has a unique
solution. The optimal solution can be obtained by setting the derivative with
respect to $h$ to zero. Rearranging the derivative of the dual objective (18)
we get the following systems of equations.

$\displaystyle
h(s)\left(\frac{A}{\lambda}-\frac{2\gamma}{\lambda}\sum_{a}P_{t}(s,a,s)+\frac{\gamma^{2}}{\lambda}\sum_{s^{\prime},a}P_{t}(s^{\prime},a,s)^{2}\right)$
$\displaystyle+\sum_{\hat{s}\neq
s}h(\hat{s})\left(-\frac{\gamma}{\lambda}\sum_{a}P_{t}(s,a,\hat{s})-\frac{\gamma}{\lambda}\sum_{a}P_{t}(\hat{s},a,{s})+\frac{\gamma^{2}}{\lambda}\sum_{s^{\prime},a}P_{t}(s^{\prime},a,\hat{s})P_{t}(s^{\prime},a,s)\right)$
$\displaystyle=\frac{1}{\lambda}\sum_{a}r_{t}(s,a)-\rho(s)-\frac{\gamma}{\lambda}\sum_{s^{\prime},a}r_{t}(s^{\prime},a)P_{t}(s^{\prime},a,s)$

Therefore let us define a matrix $B\in\mathbb{R}^{S\times S}$ and a vector
$b\in\mathbb{R}^{S}$ with the following entries.

$\displaystyle
B(s,\hat{s})=\left\\{\begin{array}[]{cc}\frac{A}{\lambda}-\frac{2\gamma}{\lambda}\sum_{a}P_{t}(s,a,s)+\frac{\gamma^{2}}{\lambda}\sum_{s^{\prime},a}P_{t}(s^{\prime},a,s)^{2}&\textrm{
if }s=\hat{s}\\\
-\frac{\gamma}{\lambda}\sum_{a}P_{t}(s,a,\hat{s})-\frac{\gamma}{\lambda}\sum_{a}P_{t}(\hat{s},a,{s})+\frac{\gamma^{2}}{\lambda}\sum_{s^{\prime},a}P_{t}(s^{\prime},a,\hat{s})P_{t}(s^{\prime},a,s)&\textrm{
o.w.}\end{array}\right.$ $\displaystyle
b(s)=\frac{1}{\lambda}\sum_{a}r_{t}(s,a)-\rho(s)-\frac{\gamma}{\lambda}\sum_{s^{\prime},a}r_{t}(s^{\prime},a)P_{t}(s^{\prime},a,s)$

Then the optimal solution is the solution of the system of equations $Bh=b$.
We now provide a bound on the $L_{2}$-norm of such a solution. For each $a$,
we define matrix $M_{a}\in R^{S\times S}$ with entries
$M_{a}(s,\hat{s})=P_{t}(s,a,\hat{s})$. Then the matrix $B$ can be expressed as
follows.

$\displaystyle
B=\frac{A}{\lambda}\mathrm{Id}-\frac{\gamma}{\lambda}\sum_{a}\left(M_{a}+M_{a}^{\top}\right)+\frac{\gamma^{2}}{\lambda}\sum_{a}M_{a}^{\top}M_{a}\succcurlyeq\frac{A(1-\gamma)^{2}}{\lambda}\mathrm{Id}$

The last inequality uses lemma 5. Notice that for $\gamma<1$ this also shows
that the matrix is invertible. We can also bound the norm of the vector $b$.

$\displaystyle\left\lVert b\right\rVert_{2}^{2}$
$\displaystyle\leq\sum_{s}\left(\frac{A}{\lambda}+\rho(s)+\frac{\gamma}{\lambda}\sum_{s^{\prime},a}P_{t}(s^{\prime},a,s)\right)^{2}$
$\displaystyle\leq
3\frac{A^{2}S}{\lambda^{2}}+3\left\lVert\rho\right\rVert_{2}^{2}+3\frac{\gamma^{2}}{\lambda^{2}}\sum_{s}\left(\sum_{s^{\prime},a}P_{t}(s^{\prime},a,s)\right)^{2}$
$\displaystyle\leq
3\frac{A^{2}S}{\lambda^{2}}+3+\frac{3SA\gamma^{2}}{\lambda^{2}}\sum_{s}\sum_{s^{\prime},a}P_{t}(s^{\prime},a,s)\leq\frac{9S^{2}A^{2}}{\lambda^{2}}$

Therefore, we have the following bound on the optimal value.

$\displaystyle\left\lVert A^{-1}b\right\rVert_{2}\leq\frac{\left\lVert
b\right\rVert_{2}}{\lambda_{\min}(A)}\leq\frac{3S}{(1-\gamma)^{2}}$

∎

######  Lemma 5.

For each $a$, let the matrix $M_{a}\in\mathbb{R}^{S\times S}$ be defined so
that $M_{a}(s,s^{\prime})=P(s,a,s^{\prime})$.

$\lambda_{\min}\left(\sum_{a}\mathrm{Id}-\gamma(M_{a}+M_{a}^{\top})+\gamma^{2}M_{a}^{\top}M_{a}\right)\geq
A(1-\gamma)^{2}$

###### Proof.

Let $M_{a}=U_{a}\Sigma_{a}U_{a}^{\top}$ be the Eigen-decomposition of the
matrix $M_{a}$. Then we have

$\displaystyle\sum_{a}\mathrm{Id}-\gamma(M_{a}+M_{a}^{\top})+\gamma^{2}M_{a}^{\top}M_{a}=\sum_{a}\left(\mathrm{Id}-\gamma
M_{a}\right)^{\top}\left(\mathrm{Id}-\gamma M_{a}\right)$ $\displaystyle=$
$\displaystyle\sum_{a}\left(U_{a}(\mathrm{Id}-\gamma\Sigma_{a})U_{a}^{\top}\right)^{\top}\left(U_{a}(\mathrm{Id}-\gamma\Sigma_{a})U_{a}^{\top}\right)=\sum_{a}U_{a}\left(\mathrm{Id}-\gamma\Sigma_{a}\right)^{2}U_{a}^{\top}$
$\displaystyle\succcurlyeq$
$\displaystyle\sum_{a}\mathrm{Id}(1-\gamma)^{2}=A(1-\gamma)^{2}\mathrm{Id}$

The last line follows the largest eigenvalue of $M_{a}$ is $1$, and therefore
the smallest diagonal entry of the matrix $(\mathrm{Id}-\gamma\Sigma_{a})^{2}$
is at least $(1-\gamma)^{2}$. ∎

###  B.2 Proof of Convergence of Repeated Gradient Ascent (Theorem 2)

###### Proof.

The dual of the optimization problem 10 is given as follows.

$\displaystyle\begin{split}\max_{h\in\mathbb{R}^{S}}\
&\sum_{s,a}h(s)\left((1-\eta\lambda)d_{t}(s,a)+\eta
r_{t}(s,a)\right)-\sum_{s}h(s)\rho(s)\\\
&-\gamma\cdot\sum_{s}h(s)\sum_{s^{\prime},a}P_{t}(s^{\prime},a,s)\left((1-\eta\lambda)d_{t}(s^{\prime},a)+\eta
r_{t}(s^{\prime},a)\right)-\frac{A}{2}\sum_{s}h(s)^{2}\\\
&+\gamma\cdot\sum_{s}h(s)\sum_{s^{\prime},a}h(s^{\prime})P_{t}(s^{\prime},a,s)-\frac{\gamma^{2}}{2}\sum_{s^{\prime},s^{\prime\prime}}h(s^{\prime})h(s^{\prime\prime})\sum_{s,a}P_{t}(s,a,s^{\prime})P_{t}(s,a,s^{\prime\prime})\end{split}$
(19)

We will consider the equivalent minimization problem.

$\displaystyle\begin{split}\min_{h\in\mathbb{R}^{S}}\
&-\sum_{s,a}h(s)\left((1-\eta\lambda)d_{t}(s,a)+\eta
r_{t}(s,a)\right)+\sum_{s}h(s)\rho(s)\\\
&+\gamma\cdot\sum_{s}h(s)\sum_{s^{\prime},a}P_{t}(s^{\prime},a,s)\left((1-\eta\lambda)d_{t}(s^{\prime},a)+\eta
r_{t}(s^{\prime},a)\right)+\frac{A}{2}\sum_{s}h(s)^{2}\\\
&-\gamma\cdot\sum_{s}h(s)\sum_{s^{\prime},a}h(s^{\prime})P_{t}(s^{\prime},a,s)+\frac{\gamma^{2}}{2}\sum_{s^{\prime},s^{\prime\prime}}h(s^{\prime})h(s^{\prime\prime})\sum_{s,a}P_{t}(s,a,s^{\prime})P_{t}(s,a,s^{\prime\prime})\end{split}$
(20)

Let us call the above objective function $\mathcal{P}(\cdot;M)$ for a given
MDP $M$. Consider two occupancy measures $d$ and $\hat{d}$. Let $r$ (resp.
$\hat{r}$) be the reward functions in response to the occupancy measure $d$
(resp. $\hat{d}$) i.e. $r=\mathcal{R}(d)$ and $\hat{r}=\mathcal{R}(\hat{d})$.
Similarly let $P$ (resp. $\hat{P}$) be the probability transition functions in
response to the occupancy measures $d$ (resp. $\hat{d}$).

We will write $GD(\cdot)$ to denote the projected gradient ascent step defined
in eq. 9. In particular, if we write $\mathcal{C}$ to define the set of
occupancy measures feasible with respect to $P$, then we have

$GD(d)=\mathrm{Proj}_{\mathcal{C}}\left((1-\eta\lambda)d+\eta r\right)$ (21)

Note that $GD_{\eta}(d)$ is the optimal solution to the primal problem 10 with
$d_{t}=d$. Let $h$ be the corresponding dual optimal solution. Similarly let
$\hat{h}$ be the optimal dual solution corresponding to the occupancy measure
$\hat{d}$. Since $h$ is the unique minimizer of $\mathcal{P}(\cdot;M)$ and
$\mathcal{P}(\cdot;M)$ is $A(1-2\gamma)$-strongly convex for any $M$ (lemma 7)
we have the following set of inequalities.

$\displaystyle\mathcal{P}(h;M,d)-\mathcal{P}(\hat{h};M,d)$
$\displaystyle\geq(h-\hat{h})^{\top}\nabla\mathcal{P}(\hat{h};M,d)+A(1-\gamma)^{2}/2\left\lVert
h-\hat{h}\right\rVert_{2}^{2}$
$\displaystyle\mathcal{P}(\hat{h};M,d)-\mathcal{P}(h;M,d)$ $\displaystyle\geq
A(1-\gamma)^{2}/2\left\lVert h-\hat{h}\right\rVert_{2}^{2}$

These two inequalities give us the following bound.

$\displaystyle-A(1-\gamma)^{2}\left\lVert
h-\hat{h}\right\rVert_{2}^{2}\geq(h-\hat{h})^{\top}\nabla\mathcal{P}(\hat{h};M,d)$
(22)

We now apply lemma 8 to bound the Lipschitz constant of the term
$(h-\hat{h})^{\top}\nabla\mathcal{P}(\hat{h};M)$.

$\displaystyle\left\lVert\nabla\mathcal{P}(\hat{h};M,d)-\nabla\mathcal{P}(\hat{h};\hat{M},\hat{d})\right\rVert_{2}^{2}\leq
5A(1-\eta\lambda)^{2}(1+2\gamma^{2}S^{2})\left\lVert
d-\hat{d}\right\rVert_{2}^{2}+5\eta^{2}A\left((1-\eta\lambda)^{2}+2\gamma^{2}S^{2}\right)\left\lVert
r-\hat{r}\right\rVert_{2}^{2}$
$\displaystyle+5\gamma^{2}SA\left(\frac{2(1-\eta\lambda)^{2}}{(1-\gamma)^{2}}+2\eta^{2}+6\gamma^{2}\left\lVert\hat{h}\right\rVert_{2}^{2}\right)\left\lVert
P-\hat{P}\right\rVert_{2}^{2}$
$\displaystyle\leq\left(5A(1-\eta\lambda)^{2}(1+\eta^{2}\epsilon_{r}^{2}+2\gamma^{2}S^{2})+10\eta^{2}\gamma^{2}AS^{2}\epsilon_{r}^{2}\right)\left\lVert
d-\hat{d}\right\rVert_{2}^{2}$
$\displaystyle+5\gamma^{2}SA\left(\frac{2(1-\eta\lambda)^{2}}{(1-\gamma)^{2}}+2\eta^{2}+12\gamma^{2}\left(\frac{(1+2\eta
S)^{2}}{(1-\gamma)^{4}}+4(1-\eta\lambda)^{2}\frac{S^{2}}{A(1-\gamma)^{6}}\right)\right)\epsilon_{p}^{2}\left\lVert
d-\hat{d}\right\rVert_{2}^{2}$
$\displaystyle\leq\left(5A(1-\eta\lambda)^{2}\left(1+\eta^{2}\epsilon_{r}^{2}+2\gamma^{2}S^{2}+\frac{2\gamma^{2}S}{(1-\gamma)^{2}}\epsilon_{p}^{2}+\frac{48\gamma^{4}S^{3}}{A(1-\gamma)^{6}}\epsilon_{p}^{2}\right)\right.$
$\displaystyle+\left.10\eta^{2}\gamma^{2}AS^{2}\epsilon_{r}^{2}+10\eta^{2}\gamma^{2}SA\epsilon_{p}^{2}+60\gamma^{4}SA\epsilon_{p}^{2}\frac{(1+2\eta
S)^{2}}{(1-\gamma)^{4}}\right)\left\lVert d-\hat{d}\right\rVert_{2}^{2}$
$\displaystyle\leq\underbrace{\left(5A(1-\eta\lambda)^{2}\left(1+\eta^{2}\epsilon_{r}^{2}+2\gamma^{2}S^{2}+\frac{50\gamma^{2}S^{3}}{(1-\gamma)^{6}}\epsilon_{p}^{2}\right)+10\eta^{2}\gamma^{2}S^{2}A(\epsilon_{p}^{2}+\epsilon_{r}^{2})+60\gamma^{4}SA\epsilon_{p}^{2}\frac{(1+2\eta
S)^{2}}{(1-\gamma)^{4}}\right)}_{:=\Delta^{2}}\left\lVert
d-\hat{d}\right\rVert_{2}^{2}$

The last inequality uses lemma 9 and assumption 1. Substituting this bound in
equation 22 we get the following inequality.

$\displaystyle-A(1-\gamma)^{2}\left\lVert
h-\hat{h}\right\rVert_{2}^{2}\geq(h-\hat{h})^{\top}\nabla\mathcal{P}(\hat{h};M,d)$
$\displaystyle=(h-\hat{h})^{\top}\nabla\mathcal{P}(\hat{h};M,d)-(h-\hat{h})^{\top}\nabla\mathcal{P}(\hat{h};\hat{M},\hat{d})$
$\displaystyle\geq-\left\lVert
h-\hat{h}\right\rVert_{2}\left\lVert\nabla\mathcal{P}(\hat{h};M,d)-\nabla\mathcal{P}(\hat{h};\hat{M},\hat{d})\right\rVert_{2}\geq-\Delta\left\lVert
h-\hat{h}\right\rVert_{2}\left\lVert d-\hat{d}\right\rVert_{2}$

Rearranging we get the following inequality.

$\displaystyle\left\lVert
h-\hat{h}\right\rVert_{2}\leq\frac{\Delta}{A(1-\gamma)^{2}}\left\lVert
d-\hat{d}\right\rVert_{2}$ $\displaystyle\Rightarrow$
$\displaystyle\left\lVert
h-\hat{h}\right\rVert_{2}^{2}\leq\frac{\Delta^{2}}{A^{2}(1-\gamma)^{4}}\left\lVert
d-\hat{d}\right\rVert_{2}^{2}$ $\displaystyle\Rightarrow$
$\displaystyle\frac{\left\lVert\mathrm{GD}_{\eta}(d)-\mathrm{GD}_{\eta}(\hat{d})\right\rVert_{2}^{2}}{8\gamma^{2}SA}-\frac{4(1-\eta\lambda)^{2}+4\eta^{2}\epsilon_{r}^{2}+8\gamma^{2}\left\lVert\hat{h}\right\rVert_{2}^{2}\epsilon_{p}^{2}}{8\gamma^{2}SA}\left\lVert
d-\hat{d}\right\rVert_{2}^{2}\leq\frac{\Delta^{2}}{A^{2}(1-\gamma)^{4}}\left\lVert
d-\hat{d}\right\rVert_{2}^{2}$

The last line uses lemma 6. After rearranging we get the following inequality.

$\displaystyle\left\lVert\mathrm{GD}_{\eta}(d)-\mathrm{GD}_{\eta}(\hat{d})\right\rVert_{2}^{2}\leq\left(4(1-\eta\lambda)^{2}+4\eta^{2}\epsilon_{r}^{2}+8\gamma^{2}\left\lVert\hat{h}\right\rVert_{2}^{2}\epsilon_{p}^{2}+\frac{8\gamma^{2}\Delta^{2}S}{A(1-\gamma)^{4}}\right)\left\lVert
d-\hat{d}\right\rVert_{2}^{2}$
$\displaystyle\leq\left(4(1-\eta\lambda)^{2}+4\eta^{2}\epsilon_{r}^{2}+\frac{16\gamma^{2}\epsilon_{p}^{2}(1+2\eta
S)^{2}}{(1-\gamma)^{4}}+32(1-\eta\lambda)^{2}\frac{\gamma^{2}\epsilon_{p}^{2}S^{2}}{A(1-\gamma)^{6}}+\frac{8\gamma^{2}\Delta^{2}S}{A(1-\gamma)^{4}}\right)\left\lVert
d-\hat{d}\right\rVert_{2}^{2}$

For $\eta=1/\lambda$ we get the following bound.

$\displaystyle\left\lVert\mathrm{GD}_{\eta}(d)-\mathrm{GD}_{\eta}(\hat{d})\right\rVert_{2}^{2}\leq\left(\frac{4\epsilon_{r}^{2}}{\lambda^{2}}+\frac{16\gamma^{2}\epsilon_{p}^{2}(1+2S/\lambda)^{2}}{(1-\gamma)^{4}}+\frac{80\gamma^{4}S^{3}(\epsilon_{r}^{2}+\epsilon_{p}^{2})}{\lambda^{2}(1-\gamma)^{4}}+\frac{480\gamma^{6}S^{2}\epsilon_{p}^{2}(1+2S/\lambda)^{2}}{(1-\gamma)^{8}}\right)\left\lVert
d-\hat{d}\right\rVert_{2}^{2}$

If we choose
$\lambda\geq\max\left\\{4\epsilon_{r},2S,\frac{20\gamma^{2}S^{1.5}(\epsilon_{r}+\epsilon_{p})}{(1-\gamma)^{2}}\right\\}$
we get the following condition.

$\displaystyle\left\lVert\mathrm{GD}_{\eta}(d)-\mathrm{GD}_{\eta}(\hat{d})\right\rVert_{2}^{2}\leq\left(\frac{1}{2}+\frac{64\gamma^{2}\epsilon_{p}^{2}}{(1-\gamma)^{4}}+\frac{1920\gamma^{6}S^{2}\epsilon_{p}^{2}}{(1-\gamma)^{8}}\right)\left\lVert
d-\hat{d}\right\rVert_{2}^{2}$

For a contraction mapping we need the following condition.

$\frac{64\gamma^{2}\epsilon_{p}^{2}}{(1-\gamma)^{4}}\left(1+\frac{30\gamma^{4}S^{2}}{(1-\gamma)^{4}}\right)<\frac{1}{2}$

We consider two cases. First, if $\frac{30\gamma^{4}S^{2}}{(1-\gamma)^{4}}<1$
then one can show that a sufficient condition is $\epsilon_{p}<\gamma S/3$. On
the other hand, if $\frac{30\gamma^{4}S^{2}}{(1-\gamma)^{4}}\geq 1$ then we
need $\epsilon_{p}<\frac{(1-\gamma)^{4}}{100\gamma^{3}S}$. Combining the two
conditions above a sufficient condition for contraction is the following.

$\epsilon_{p}<\min\left\\{\frac{\gamma
S}{3},\frac{(1-\gamma)^{4}}{100\gamma^{3}S}\right\\}$

Now if we set
$\mu=\sqrt{\frac{1}{2}+\frac{64\gamma^{2}\epsilon_{p}^{2}}{(1-\gamma)^{4}}+\frac{1920\gamma^{6}S^{2}\epsilon_{p}^{2}}{(1-\gamma)^{8}}}$
we get the contraction mapping:
$\left\lVert\mathrm{GD}_{\eta}(d)-\mathrm{GD}_{\eta}(\hat{d})\right\rVert_{2}\leq\mu\left\lVert
d-\hat{d}\right\rVert_{2}$. Let $d^{\star}$ be the fixed point of this
contraction mapping. Using $d=d_{t}$ and $\hat{d}=d^{\star}$ we get the
following sequence of inequalities.

$\left\lVert d_{t+1}-d^{\star}\right\rVert_{2}\leq\mu\left\lVert
d_{t}-d^{\star}\right\rVert_{2}\leq\ldots\leq\mu^{t}\left\lVert
d_{1}-d^{\star}\right\rVert_{2}\leq\mu^{t}\frac{2}{1-\gamma}$

The last inequality uses the fact that for any occupancy measure $d$ we have
$\left\lVert d\right\rVert_{2}\leq\left\lVert
d\right\rVert_{1}\leq\frac{1}{1-\gamma}$. Rearranging we get that as long as
$t\geq\ln\left(\frac{2}{\delta(1-\gamma)}\right)/\ln(1/\mu)$ we have
$\left\lVert d_{t}-d^{\star}\right\rVert_{2}\leq\delta$.

We now show that the fixed point $d^{\star}$ is a stable point. In response to
$d^{\star}$, let the probability transition function (resp. reward function)
be $P^{\star}$ (resp. $d^{\star}$). Let $\mathcal{C}^{\star}$ be the set of
occupancy measures corresponding to $d^{\star}$. Note that
$\mathcal{C}^{\star}$ is a convex set. We consider two cases. First,
$(1-\eta\lambda)d^{\star}+\eta r^{\star}\in\mathcal{C}^{\star}$. Then
$d^{\star}=\mathrm{GD}_{\eta}(d^{\star})=(1-\eta\lambda)d^{\star}+\eta
r^{\star}$ and $r^{\star}-\lambda
d^{\star}=\nabla\mathcal{P}(d^{\star};P^{\star},r^{\star})=0$. Since
$\mathcal{P}(\cdot;P^{\star},r^{\star})$ is a concave function the occupancy
measure $d^{\star}$ is the optimal point and is a stable point.

Second, we consider the case when $(1-\eta\lambda)d^{\star}+\eta
r^{\star}\notin\mathcal{C}^{\star}$. Since
$d^{\star}=\mathrm{Proj}_{\mathcal{C}^{\star}}\left((1-\eta\lambda)d^{\star}+\eta
r^{\star}\right)$. Since $\mathcal{C}^{\star}$ is a convex set, by the
projection theorem (see e.g. [Ber09]) we have the following inequality for any
$d\in\mathcal{C}^{\star}$.

$\displaystyle\left((1-\eta\lambda)d^{\star}+\eta
r^{\star}-d^{\star}\right)^{\top}(d-d^{\star})\leq 0$
$\displaystyle\Rightarrow\ $ $\displaystyle\eta(\lambda
d^{\star}-r^{\star})^{\top}(d-d^{\star})\leq 0$ $\displaystyle\Rightarrow\ $
$\displaystyle\nabla\mathcal{P}(d^{\star};P^{\star},r^{\star})^{\top}(d-d^{\star})\geq
0$

This implies that $d^{\star}$ maximizes the function
$\mathcal{P}(\cdot;P^{\star},r^{\star})$ over the set $\mathcal{C}^{\star}$
and is a stable point. ∎

######  Lemma 6.

Consider two state-action occupancy measures $d$ and $\hat{d}$. Let $h$ (resp.
$\hat{h}$) be the dual optimal solutions to the projection (eq. 20)
corresponding to occupancy measure $d_{t}=d$ (resp. $\hat{d}$). Then we have
the following inequality.

$\left\lVert\mathrm{GD}_{\eta}(d)-\mathrm{GD}_{\eta}(\hat{d})\right\rVert_{2}^{2}\leq\left(4(1-\eta\lambda)^{2}+4\eta^{2}\epsilon_{r}^{2}+8\gamma^{2}\left\lVert\hat{h}\right\rVert_{2}^{2}\epsilon_{p}^{2}\right)\left\lVert
d-\hat{d}\right\rVert_{2}^{2}+8\gamma^{2}SA\left\lVert
h-\hat{h}\right\rVert_{2}^{2}$

###### Proof.

Recall the relationship between the dual and the primal variables.

$\mathrm{GD}_{\eta}(d)(s,a)=(1-\eta\lambda)d(s,a)+\eta
r(s,a)-h(s)+\gamma\sum_{\widetilde{s}}h(\widetilde{s})P(s,a,\widetilde{s})$

This gives us the following bound on the difference
$(\mathrm{GD}_{\eta}(d)(s,a)-\mathrm{GD}_{\eta}(\hat{d})(s,a))^{2}$.

$\displaystyle\left(\mathrm{GD}_{\eta}(d)(s,a)-\mathrm{GD}_{\eta}(\hat{d})(s,a)\right)^{2}\leq
4(1-\eta\lambda)^{2}\left(d(s,a)-\hat{d}(s,a)\right)^{2}+4\eta^{2}\left(r(s,a)-\hat{r}(s,a)\right)^{2}$
$\displaystyle+4\left(h(s)-\hat{h}(s)\right)^{2}+4\gamma^{2}\left(\sum_{s^{\prime}}h(s^{\prime})P(s,a,s^{\prime})-\sum_{s^{\prime}}\hat{h}(s^{\prime})\hat{P}(s,a,s^{\prime})\right)^{2}$
$\displaystyle\leq
4(1-\eta\lambda)^{2}\left(d(s,a)-\hat{d}(s,a)\right)^{2}+4\eta^{2}\left(r(s,a)-\hat{r}(s,a)\right)^{2}$
$\displaystyle+4\left(h(s)-\hat{h}(s)\right)^{2}+4\gamma^{2}\left(\sum_{s^{\prime}}\left(h(s^{\prime})-\hat{h}(s^{\prime})\right)P(s,a,s^{\prime})+\hat{h}(s^{\prime})\left(P(s,a,s^{\prime})-\hat{P}(s,a,s^{\prime})\right)\right)^{2}$
$\displaystyle\leq
4(1-\eta\lambda)^{2}\left(d(s,a)-\hat{d}(s,a)\right)^{2}+4\eta^{2}\left(r(s,a)-\hat{r}(s,a)\right)^{2}$
$\displaystyle+8\gamma^{2}\left(\sum_{s^{\prime}}\left(h(s^{\prime})-\hat{h}(s^{\prime})\right)P(s,a,s^{\prime})\right)^{2}+8\gamma^{2}\left(\sum_{s^{\prime}}\hat{h}(s^{\prime})\left(P(s,a,s^{\prime})-\hat{P}(s,a,s^{\prime})\right)\right)^{2}$
$\displaystyle\leq
4(1-\eta\lambda)^{2}\left(d(s,a)-\hat{d}(s,a)\right)^{2}+4\eta^{2}\left(r(s,a)-\hat{r}(s,a)\right)^{2}$
$\displaystyle+8\gamma^{2}\left\lVert
h-\hat{h}\right\rVert_{2}^{2}+8\gamma^{2}\left\lVert\hat{h}\right\rVert_{2}^{2}\sum_{s^{\prime}}\left(P(s,a,s^{\prime})-\hat{P}(s,a,s^{\prime})\right)^{2}$

Now summing over $s$ and $a$ we get the following bound.

$\left\lVert\mathrm{GD}_{\eta}(d)-\mathrm{GD}_{\eta}(\hat{d})\right\rVert_{2}^{2}\leq
4(1-\eta\lambda)^{2}\left\lVert
d-\hat{d}\right\rVert_{2}^{2}+4\eta^{2}\left\lVert
r-\hat{r}\right\rVert_{2}^{2}+8\gamma^{2}SA\left\lVert
h-\hat{h}\right\rVert_{2}^{2}+8\gamma^{2}\left\lVert\hat{h}\right\rVert_{2}^{2}\left\lVert
P-\hat{P}\right\rVert_{2}^{2}$

We now use the assumptions $\left\lVert
r-\hat{r}\right\rVert_{2}\leq\epsilon_{r}\left\lVert
d-\hat{d}\right\rVert_{2}$ and $\left\lVert
P-\hat{P}\right\rVert_{2}\leq\epsilon_{p}\left\lVert
d-\hat{d}\right\rVert_{2}$.

$\displaystyle\left\lVert\mathrm{GD}_{\eta}(d)-\mathrm{GD}_{\eta}(\hat{d})\right\rVert_{2}^{2}\leq\left(4(1-\eta\lambda)^{2}+4\eta^{2}\epsilon_{r}^{2}+8\gamma^{2}\left\lVert\hat{h}\right\rVert_{2}^{2}\epsilon_{p}^{2}\right)\left\lVert
d-\hat{d}\right\rVert_{2}^{2}+8\gamma^{2}SA\left\lVert
h-\hat{h}\right\rVert_{2}^{2}$

∎

######  Lemma 7.

The objective function $\mathcal{P}(\cdot;M)$ (as defined in 20) is
$A(1-\gamma)^{2}$-strongly convex.

###### Proof.

The derivative of the objective function $\mathcal{P}(\cdot;M)$ with respect
to $h(s)$ is given as follows.

$\displaystyle\begin{split}\frac{\partial\mathcal{P}(h;M_{t})}{\partial
h(s)}&=-\sum_{a}\left((1-\eta\lambda)d_{t}(s,a)+\eta
r_{t}(s,a)\right)+\rho(s)+\gamma\cdot\sum_{s^{\prime},a}P_{t}(s^{\prime},a,s)\left((1-\eta\lambda)d_{t}(s,a)+\eta
r_{t}(s,a)\right)\\\
&+Ah(s)-\gamma\cdot\sum_{\widetilde{s},a}h(\widetilde{s})\left(P_{t}(\widetilde{s},a,s)+P_{t}(s,a,\widetilde{s})\right)+{\gamma^{2}}\sum_{s^{\prime}}h(s^{\prime})\sum_{\widetilde{s},a}P_{t}(\widetilde{s},a,s^{\prime})P_{t}(\widetilde{s},a,s)\end{split}$
(23)

This gives us the following identity.

$\displaystyle\left(\nabla\mathcal{P}(h;M_{t})-\nabla\mathcal{P}(\widetilde{h};M_{t})\right)^{\top}(h-\widetilde{h})$
$\displaystyle=A\left\lVert h-\widetilde{h}\right\rVert_{2}^{2}$
$\displaystyle-\gamma\cdot\sum_{s,s^{\prime},a}(h(s^{\prime})-\widetilde{h}(s^{\prime}))(P_{t}(s^{\prime},a,s)+P_{t}(s,a,s^{\prime}))(h(s)-\widetilde{h}(s))$
$\displaystyle+\gamma^{2}\sum_{s^{\prime},s}(h(s^{\prime})-\widetilde{h}(s^{\prime}))\sum_{\widetilde{s},a}P_{t}(\widetilde{s},a,s^{\prime})P_{t}(\widetilde{s},a,s)(h(s)-\widetilde{h}(s))$

Now for each action $a$, we define the following matrix $M_{a}\in R^{S\times
S}$ with entries $M_{a}(s,s^{\prime})=P_{t}(s,a,s^{\prime})$. Note that matrix
$M_{a}$ is row-stochastic and has eigenvalues bounded between $-1$ and $1$.

$\displaystyle\left(\nabla\mathcal{P}(h;M_{t})-\nabla\mathcal{P}(\widetilde{h};M_{t})\right)^{\top}(h-\widetilde{h})$
$\displaystyle=A\left\lVert
h-\widetilde{h}\right\rVert_{2}^{2}-\gamma\cdot(h-\widetilde{h})^{\top}\left(\sum_{a}M_{a}+M_{a}^{\top}\right)(h-\widetilde{h})$
$\displaystyle+\gamma^{2}(h-\widetilde{h})^{\top}\left(\sum_{a}M_{a}^{\top}M_{a}\right)(h-\widetilde{h})$
$\displaystyle=(h-\widetilde{h})^{\top}\sum_{a}\left(\mathrm{Id}-\gamma(M_{a}+M_{a}^{\top})+\gamma^{2}M_{a}^{\top}M_{a}\right)(h-\widetilde{h})$
$\displaystyle\geq A(1-\gamma)^{2}\left\lVert
h-\widetilde{h}\right\rVert_{2}^{2}$

The last line uses lemma 5. ∎

######  Lemma 8.

The dual function (as defined in 20) satisfies the following guarantee for any
$h$, occupancy measures $d,\hat{d}$, and MDP $M,\hat{M}$.

$\displaystyle\left\lVert\nabla\mathcal{P}(h;M,d)-\nabla\mathcal{P}(h;\widehat{M},\hat{d})\right\rVert_{2}$
$\displaystyle\leq 5A(1-\eta\lambda)^{2}(1+2\gamma^{2}S^{2})\left\lVert
d-\hat{d}\right\rVert_{2}^{2}$
$\displaystyle+5\eta^{2}A\left((1-\eta\lambda)^{2}+2\gamma^{2}S^{2}\right)\left\lVert
r-\hat{r}\right\rVert_{2}^{2}$
$\displaystyle+5\gamma^{2}SA\left(\frac{2(1-\eta\lambda)^{2}}{(1-\gamma)^{2}}+2\eta^{2}+6\gamma^{2}\left\lVert
h\right\rVert_{2}^{2}\right)\left\lVert P-\hat{P}\right\rVert_{2}^{2}t$

###### Proof.

From the expression of the derivative of the function $\mathcal{P}(\cdot;M,d)$
(23) we have the following bound.

$\displaystyle\left\lVert\nabla\mathcal{P}(h;M,d)-\nabla\mathcal{P}(h;\widehat{M},\hat{d})\right\rVert_{2}^{2}=\sum_{s}\left\\{-(1-\eta\lambda)\sum_{a}(d(s,a)-\hat{d}(s,a))\right.$
$\displaystyle+\eta(1-\eta\lambda)\sum_{a}(r(s,a)-\hat{r}(s,a))+\gamma\eta\sum_{s^{\prime},a}\left(P(s^{\prime},a,s)r(s,a)-\hat{P}(s^{\prime},a,s)\hat{r}(s,a)\right)$
$\displaystyle+\gamma(1-\eta\lambda)\sum_{s^{\prime},a}\left(P(s^{\prime},a,s)d(s,a)-\hat{P}(s^{\prime},a,s)\hat{d}(s,a)\right)$
$\displaystyle-\gamma\cdot\sum_{\widetilde{s},a}h(\widetilde{s})\left(P(\widetilde{s},a,s)+P(s,a,\widetilde{s})-\hat{P}(\widetilde{s},a,s)-\hat{P}(s,a,\widetilde{s})\right)$
$\displaystyle+\left.\gamma^{2}\cdot\sum_{s^{\prime}}h(s^{\prime})\sum_{\widetilde{s},a}\left(P(\widetilde{s},a,s^{\prime})P(s,a,\widetilde{s})-\hat{P}(\widetilde{s},a,s^{\prime})\hat{P}(s,a,\widetilde{s})\right)\right\\}^{2}$
$\displaystyle\leq
5(1-\eta\lambda)^{2}\sum_{s}\left(\sum_{a}(d(s,a)-\hat{d}(s,a))\right)^{2}+5\eta^{2}(1-\eta\lambda)^{2}\sum_{s}\left(\sum_{a}(r(s,a)-\hat{r}(s,a))\right)^{2}$
$\displaystyle+5\gamma^{2}\eta^{2}\sum_{s}\left(\sum_{s^{\prime},a}\left(P(s^{\prime},a,s)r(s,a)-\hat{P}(s^{\prime},a,s)\hat{r}(s,a)\right)\right)^{2}$
$\displaystyle+5\gamma^{2}(1-\eta\lambda)^{2}\sum_{s}\left(\sum_{s^{\prime},a}\left(P(s^{\prime},a,s)d(s,a)-\hat{P}(s^{\prime},a,s)\hat{d}(s,a)\right)\right)^{2}$
$\displaystyle+5\gamma^{2}\sum_{s}\left(\sum_{\widetilde{s},a}h(\widetilde{s})\left(P(\widetilde{s},a,s)+P(s,a,\widetilde{s})-\hat{P}(\widetilde{s},a,s)-\hat{P}(s,a,\widetilde{s})\right)\right)^{2}$
$\displaystyle+5\gamma^{4}\sum_{s}\left(\sum_{s^{\prime}}h(s^{\prime})\sum_{\widetilde{s},a}\left(P(\widetilde{s},a,s^{\prime})P(s,a,\widetilde{s})-\hat{P}(\widetilde{s},a,s^{\prime})\hat{P}(s,a,\widetilde{s})\right)\right)^{2}$

We now establish several bounds to complete the proof. The bounds mainly use
the Cauchy-Schwarz inequality and the Jensen’s inequality.

$\displaystyle\textrm{Bound 1}:$
$\displaystyle\sum_{s}\left(\sum_{s^{\prime},a}\left(P(s^{\prime},a,s)d(s,a)-\hat{P}(s^{\prime},a,s)\hat{d}(s,a)\right)\right)^{2}$
$\displaystyle\leq\sum_{s}\left(\sum_{s^{\prime},a}P(s^{\prime},a,s)\left(d(s,a)-\hat{d}(s,a)\right)+\hat{d}(s,a)\left(P(s^{\prime},a,s)-\hat{P}(s^{\prime},a,s)\right)\right)^{2}$
$\displaystyle\leq
2\sum_{s}\left(\sum_{s^{\prime},a}P(s^{\prime},a,s)\left(d(s,a)-\hat{d}(s,a)\right)\right)^{2}+2\sum_{s}\left(\sum_{s^{\prime},a}\hat{d}(s,a)\left(P(s^{\prime},a,s)-\hat{P}(s^{\prime},a,s)\right)\right)^{2}$
$\displaystyle\leq
2\sum_{s}\sum_{s^{\prime},a}\left(d(s,a)-\hat{d}(s,a)\right)^{2}\sum_{s^{\prime},a}\left(P(s^{\prime},a,s)\right)^{2}$
$\displaystyle+2\sum_{s}\sum_{a}(\hat{d}(s,a))^{2}\sum_{a}\left(\sum_{s^{\prime}}P(s^{\prime},a,s)-\hat{P}(s^{\prime},a,s)\right)^{2}$
$\displaystyle\leq 2S\left\lVert
d-\hat{d}\right\rVert_{2}^{2}\sum_{s,a,s^{\prime}}P(s^{\prime},a,s)+\frac{2AS}{(1-\gamma)^{2}}\sum_{s,a,s^{\prime}}\left|P(s^{\prime},a,s)-\hat{P}(s^{\prime},a,s)\right|^{2}$
$\displaystyle\leq 2S^{2}A\left\lVert
d-\hat{d}\right\rVert_{2}^{2}+\frac{2AS}{(1-\gamma)^{2}}\left\lVert
P-\hat{P}\right\rVert_{2}^{2}$

Similarly one can establish the following bound.

$\displaystyle\textrm{Bound 2}:$
$\displaystyle\sum_{s}\left(\sum_{s^{\prime},a}\left(P(s^{\prime},a,s)r(s,a)-\hat{P}(s^{\prime},a,s)\hat{r}(s,a)\right)\right)^{2}\leq
2S^{2}A\left\lVert r-\hat{r}\right\rVert_{2}^{2}+{2AS}\left\lVert
P-\hat{P}\right\rVert_{2}^{2}$ $\displaystyle\textrm{Bound 3}:$
$\displaystyle\sum_{s}\left(\sum_{\widetilde{s},a}h(\widetilde{s})\left(P(\widetilde{s},a,s)+P(s,a,\widetilde{s})-\hat{P}(\widetilde{s},a,s)-\hat{P}(s,a,\widetilde{s})\right)\right)^{2}$
$\displaystyle\leq\sum_{s}\sum_{\widetilde{s}}h(\widetilde{s})^{2}\sum_{\widetilde{s}}\left(\sum_{a}\left(P(\widetilde{s},a,s)+P(s,a,\widetilde{s})-\hat{P}(\widetilde{s},a,s)-\hat{P}(s,a,\widetilde{s})\right)\right)^{2}$
$\displaystyle\leq A\left\lVert
h\right\rVert_{2}^{2}\sum_{s,\widetilde{s},a}\left(P(\widetilde{s},a,s)+P(s,a,\widetilde{s})-\hat{P}(\widetilde{s},a,s)-\hat{P}(s,a,\widetilde{s})\right)^{2}$
$\displaystyle\leq 2A\left\lVert h\right\rVert_{2}^{2}\left\lVert
P-\hat{P}\right\rVert_{2}^{2}$ $\displaystyle\textrm{Bound 4}:$
$\displaystyle\sum_{s}\left(\sum_{s^{\prime}}h(s^{\prime})\sum_{\widetilde{s},a}\left(P(\widetilde{s},a,s^{\prime})P(s,a,\widetilde{s})-\hat{P}(\widetilde{s},a,s^{\prime})\hat{P}(s,a,\widetilde{s})\right)\right)^{2}$
$\displaystyle\leq\sum_{s}\sum_{s^{\prime}}h(s^{\prime})^{2}\sum_{s^{\prime}}\left(\sum_{\widetilde{s},a}\left(P(\widetilde{s},a,s^{\prime})P(s,a,\widetilde{s})-\hat{P}(\widetilde{s},a,s^{\prime})\hat{P}(s,a,\widetilde{s})\right)\right)^{2}$
$\displaystyle=\left\lVert
h\right\rVert_{2}^{2}\sum_{s,s^{\prime}}\left(\sum_{\widetilde{s},a}P(s,a,\widetilde{s})\left(P(\widetilde{s},a,s^{\prime})-\hat{P}(\widetilde{s},a,s^{\prime})\right)+\hat{P}(\widetilde{s},a,s^{\prime})\left(P(s,a,\widetilde{s})-\hat{P}(s,a,\widetilde{s})\right)\right)^{2}$
$\displaystyle\leq 2\left\lVert
h\right\rVert_{2}^{2}\sum_{s,s^{\prime}}\left(\sum_{\widetilde{s},a}P(s,a,\widetilde{s})\left(P(\widetilde{s},a,s^{\prime})-\hat{P}(\widetilde{s},a,s^{\prime})\right)\right)^{2}$
$\displaystyle+2\left\lVert
h\right\rVert_{2}^{2}\sum_{s,s^{\prime}}\left(\sum_{\widetilde{s},a}\hat{P}(\widetilde{s},a,s^{\prime})\left(P(s,a,\widetilde{s})-\hat{P}(s,a,\widetilde{s})\right)\right)^{2}$
$\displaystyle\leq 2\left\lVert
h\right\rVert_{2}^{2}\sum_{s,s^{\prime}}\sum_{\widetilde{s},a}P(s,a,\widetilde{s})\sum_{\widetilde{s},a}\left(P(\widetilde{s},a,s^{\prime})-\hat{P}(\widetilde{s},a,s^{\prime})\right)^{2}$
$\displaystyle+2\left\lVert
h\right\rVert_{2}^{2}\sum_{s,s^{\prime}}\sum_{\widetilde{s},a}\hat{P}(\widetilde{s},a,s^{\prime})\left(P(s,a,\widetilde{s})-\hat{P}(s,a,\widetilde{s})\right)^{2}$
$\displaystyle\leq 2\left\lVert h\right\rVert_{2}^{2}\left\lVert
P-\hat{P}\right\rVert_{2}^{2}\sum_{s,\widetilde{s},a}P(s,a,\widetilde{s})+2\left\lVert
h\right\rVert_{2}^{2}\sum_{s,\widetilde{s},a}\left(P(s,a,\widetilde{s})-\hat{P}(s,a,\widetilde{s})\right)^{2}$
$\displaystyle\leq 4SA\left\lVert h\right\rVert_{2}^{2}\left\lVert
P-\hat{P}\right\rVert_{2}^{2}$

We now substitute the four bounds above to complete the proof.

$\displaystyle\left\lVert\nabla\mathcal{P}(h;M,d)-\nabla\mathcal{P}(h;\widehat{M},\hat{d})\right\rVert_{2}^{2}\leq
5(1-\eta\lambda)^{2}A\left\lVert
d-\hat{d}\right\rVert_{2}^{2}+5\eta^{2}(1-\eta\lambda)^{2}A\left\lVert
r-\hat{r}\right\rVert_{2}^{2}$
$\displaystyle+5\gamma^{2}(1-\eta\lambda)^{2}\left(2S^{2}A\left\lVert
d-\hat{d}\right\rVert_{2}^{2}+\frac{2AS}{(1-\gamma)^{2}}\left\lVert
P-\hat{P}\right\rVert_{2}^{2}\right)$
$\displaystyle+5\gamma^{2}\eta^{2}\left(2S^{2}A\left\lVert
r-\hat{r}\right\rVert_{2}^{2}+{2AS}\left\lVert
P-\hat{P}\right\rVert_{2}^{2}\right)$ $\displaystyle+10\gamma^{2}\left\lVert
h\right\rVert_{2}^{2}\left\lVert
P-\hat{P}\right\rVert_{2}^{2}+20\gamma^{4}SA\left\lVert
h\right\rVert_{2}^{2}\left\lVert P-\hat{P}\right\rVert_{2}^{2}$
$\displaystyle\leq 5A(1-\eta\lambda)^{2}(1+2\gamma^{2}S^{2})\left\lVert
d-\hat{d}\right\rVert_{2}^{2}+5\eta^{2}A\left((1-\eta\lambda)^{2}+2\gamma^{2}S^{2}\right)\left\lVert
r-\hat{r}\right\rVert_{2}^{2}$
$\displaystyle+5\gamma^{2}SA\left(\frac{2(1-\eta\lambda)^{2}}{(1-\gamma)^{2}}+2\eta^{2}+6\gamma^{2}\left\lVert
h\right\rVert_{2}^{2}\right)\left\lVert P-\hat{P}\right\rVert_{2}^{2}$

∎

######  Lemma 9.

For any choice of MDP $M$ and occupancy measure $d$, the $L_{2}$-norm of the
optimal solution to the dual objective (as defined in 20) is bounded by

$\frac{1+2\eta
S}{(1-\gamma)^{2}}+2\left|1-\eta\lambda\right|\frac{S/\sqrt{A}}{(1-\gamma)^{3}}.$

###### Proof.

The objective function $\mathcal{P}$ is strongly-convex and has a unique
solution. We set the derivative with respect to $h$ to zero and get the
following system of equations.

$\displaystyle
h(s)\left(A-2\gamma\sum_{a}P(s,a,s)+\gamma^{2}\sum_{\widetilde{s},a}P(\widetilde{s},a,s)^{2}\right)$
$\displaystyle+\sum_{s^{\prime}\neq
s}h(s^{\prime})\left(-\gamma\sum_{a}(P(s^{\prime},a,s)+P(s,a,s^{\prime}))+\gamma^{2}\sum_{\widetilde{s},a}P(\widetilde{s},a,s^{\prime})P(\widetilde{s},a,s)\right)$
$\displaystyle=\sum_{a}\left((1-\eta\lambda)d(s,a)+\eta
r(s,a)\right)-\rho(s)-\gamma\cdot\sum_{s^{\prime},a}P(s^{\prime},a,s)\left((1-\eta\lambda)d(s,a)+\eta
r(s,a)\right)$

Let us now define matrix $B\in\mathbb{R}^{S\times S}$ and a vector
$b\in\mathbb{R}^{S}$ with the following entries.

$\displaystyle
B(s,s^{\prime})=\left\\{\begin{array}[]{cc}A-2\gamma\sum_{a}P(s,a,s)+\gamma^{2}\sum_{\widetilde{s},a}P(\widetilde{s},a,s)^{2}&\textrm{if
}s^{\prime}=s\\\
-\gamma\sum_{a}(P(s^{\prime},a,s)+P(s,a,s^{\prime}))+\gamma^{2}\sum_{\widetilde{s},a}P(\widetilde{s},a,s^{\prime})P(\widetilde{s},a,s)&\textrm{o.w.}\end{array}\right.$
$\displaystyle b(s)=\sum_{a}\left((1-\eta\lambda)d(s,a)+\eta
r(s,a)\right)-\rho(s)-\gamma\cdot\sum_{s^{\prime},a}P(s^{\prime},a,s)\left((1-\eta\lambda)d(s,a)+\eta
r(s,a)\right)$

Then the optimal solution is the solution to the system of equations $Bx=b$.
We now provide a bound on the $L_{2}$-norm of such a solution. For each action
$a$, we define a matrix $M_{a}\in\mathbb{R}^{S\times S}$ with entries
$M_{a}(s,s^{\prime})=P(s,a,s^{\prime})$. Then the matrix $B$ can be expressed
as follows.

$B=A\cdot\mathrm{Id}-\gamma\sum_{a}(M_{a}+M_{a}^{\top})+\gamma^{2}\sum_{a}M_{a}^{\top}M_{a}\succcurlyeq
A(1-\gamma)^{2}\mathrm{Id}$

The last inequality uses lemma 5. This also implies that for $\gamma<1$ the
matrix $B$ is invertible.

We now bound the norm of the vector $b$. We will use the fact that for any
state $\sum_{s,a}d(s,a)=1/(1-\gamma)$.

$\displaystyle\left\lVert b\right\rVert_{2}$ $\displaystyle\leq\left\lVert
b\right\rVert_{1}\leq\left|1-\eta\lambda\right|\sum_{s,a}d(s,a)+\eta\sum_{s,a}r(s,a)+\sum_{s,a}\rho(s)$
$\displaystyle+\gamma\left|1-\eta\lambda\right|\cdot\sum_{s,s^{\prime},a}P(s^{\prime},a,s)d(s,a)+\eta\gamma\sum_{s,s^{\prime},a}P(s^{\prime},a,s)\left|r(s,a)\right|$
$\displaystyle\leq\frac{\left|1-\eta\lambda\right|}{1-\gamma}+\eta
SA+A+\gamma\left|1-\eta\lambda\right|\sum_{s^{\prime}}\sqrt{\sum_{s,a}P(s^{\prime},a,s)^{2}}\sqrt{\sum_{s,a}d(s,a)^{2}}+\eta\gamma
SA$ $\displaystyle\leq\frac{\left|1-\eta\lambda\right|}{1-\gamma}+\eta
SA+A+\gamma\left|1-\eta\lambda\right|\left\lVert
d\right\rVert_{2}\sum_{s^{\prime}}\sqrt{\sum_{s,a}P(s^{\prime},a,s)}+\eta\gamma
SA$ $\displaystyle\leq\frac{\left|1-\eta\lambda\right|}{1-\gamma}+\eta
SA+A+\gamma\left|1-\eta\lambda\right|\frac{S\sqrt{A}}{1-\gamma}+\eta\gamma
SA\leq A(1+2\eta S)+2\left|1-\eta\lambda\right|\frac{S\sqrt{A}}{1-\gamma}$

The optimal solution to the dual objective is bounded by

$\left\lVert A^{-1}b\right\rVert_{2}\leq\frac{\left\lVert
b\right\rVert_{2}}{\lambda_{\min}(A)}\leq\frac{1+2\eta
S}{(1-\gamma)^{2}}+2\left|1-\eta\lambda\right|\frac{S/\sqrt{A}}{(1-\gamma)^{3}}$

∎

###  B.3 Formal Statement and Proof of Convergence with Finite Samples
(Theorem 3)

######  Theorem 6.

Suppose assumption 1 holds with
$\lambda\geq\frac{24S^{3/2}(2\epsilon_{r}+5S\epsilon_{p})}{(1-\gamma)^{4}}$,
and assumption 2 holds with parameter $B$. For a given $\delta$, and error
probability $p$, if we repeatedly solve the optimization problem 12 with
number of samples

$\displaystyle
m_{t}\geq\frac{64A(B+\sqrt{A})^{2}}{\beta^{4}\delta^{4}(2\epsilon_{r}+5S\epsilon_{p})^{2}}\left(\ln\left(\frac{t}{p}\right)+\ln\left(\frac{4S(B+\sqrt{A})}{\beta\delta(2\epsilon_{r}+5S\epsilon_{p})}\right)\right)$

then we have

$\displaystyle\left\lVert d_{t}-d_{S}\right\rVert_{2}\leq\delta\ \forall
t\geq(1-\mu)^{-1}\ln\left(\frac{2}{\delta(1-\gamma)}\right)\quad\textrm{with
probability at least }1-p$

where $\mu=\frac{24S^{3/2}(2\epsilon_{r}+5S\epsilon_{p})}{(1-\gamma)^{4}}$.

###### Proof.

We will write $\widehat{\mathrm{GD}}(d_{t})$ to denote the occupancy measure
$d_{t+1}$.

$(\widehat{\mathrm{GD}}(d_{t}),\hat{h}_{t+1})=\operatorname*{arg\,max}_{d}\
\operatorname*{arg\,min}_{h}\ \hat{\mathcal{L}}(d,h;M_{t})$

Let us also write $\widehat{\mathrm{GD}}(d_{S})$ to denote the primal solution
corresponding to the stable solution $d_{S}$ i.e.

$(\widehat{\mathrm{GD}}(d_{S}),\hat{h}_{S})=\operatorname*{arg\,max}_{d}\
\operatorname*{arg\,min}_{h}\ \hat{\mathcal{L}}(d,h;M_{S})$

Let us also recall the definition of the operator $\mathrm{GD}(\cdot)$. Given
occupancy measure $d_{t}$, $\mathrm{GD}(d_{t})$ is the optimal solution to the
optimization problem 7 when we use the exact model $M_{t}$. Because of strong-
duality this implies there exists $h_{t+1}$ so that

$({\mathrm{GD}}(d_{t}),{h}_{t+1})=\operatorname*{arg\,max}_{d}\
\operatorname*{arg\,min}_{h}\ {\mathcal{L}}(d,h;M_{t})$

Since $\mathrm{GD}(d_{S})=d_{S}$ there also exists $h_{S}$ so that

$(d_{S},h_{S})=\operatorname*{arg\,max}_{d}\ \operatorname*{arg\,min}_{h}\
{\mathcal{L}}(d,h;M_{S})$

Because of lemma 4 we can assume the $L_{2}$-norms of the dual solutions
$h_{t+1},\hat{h}_{S}$, and $\hat{h}_{S}$ are bounded by
$\frac{3S}{(1-\gamma)^{2}}$. Since there exists a saddle point with bounded
norm, we can just consider the restricted set
$\mathcal{H}=\left\\{h:\left\lVert
h\right\rVert_{2}\leq\frac{3S}{(1-\gamma)^{2}}\right\\}$.777See lemma 3 of
[Zha+22] for a proof of this statement. Moreover, by assumption 2 we know that
$\mathrm{GD}(d_{t})(s,a)/d_{t}(s,a)\leq B$ for any $(s,a)$. Therefore, we can
apply lemma 10 with $\delta_{1}=p/2t^{2}$ and $H=3S/(1-\gamma)^{2}$ to get the
following bound,

$\displaystyle\left|\hat{\mathcal{L}}(d,h;M_{t})-\mathcal{L}(d,h;M_{t})\right|\leq\frac{18S^{1.5}(B+\sqrt{A})\epsilon}{(1-\gamma)^{3}}$
(24)

as long as

$\displaystyle
m_{t}\geq\frac{4A}{\epsilon^{2}}(\ln(t/p)+\ln(S/(1-\gamma)\epsilon))$ (25)

$h\in\mathcal{H}$ and $\max_{s,a}d(s,a)/d_{t}(s,a)\leq B$. Since the event
(24) holds at time $t$ with probability at least $1-\frac{p}{2t^{2}}$, by a
union bound over all time steps, this event holds with probability at least
$1-p$.

Note that the objective $\mathcal{L}(\cdot,h_{t+1};M_{t})$ is
$\lambda$-strongly concave. Therefore, we have

$\mathcal{L}(\widehat{\mathrm{GD}}(d_{t}),{h}_{t+1};M_{t})-\mathcal{L}(\mathrm{GD}(d_{t}),{h}_{t+1};M_{t})\leq-\frac{\lambda}{2}\left\lVert\mathrm{GD}(d_{t})-\widehat{\mathrm{GD}}(d_{t})\right\rVert_{2}^{2}.$

Rearranging and using lemma 12 we get the following bound.

$\displaystyle\left\lVert\mathrm{GD}(d_{t})-\widehat{\mathrm{GD}}(d_{t})\right\rVert_{2}$
$\displaystyle\leq\sqrt{\frac{2\left(\mathcal{L}(\mathrm{GD}(d_{t}),{h}_{t+1};M_{t})-\mathcal{L}(\widehat{\mathrm{GD}}(d_{t}),{h}_{t+1};M_{t})\right)}{\lambda}}$
$\displaystyle\leq\frac{6\sqrt{S^{1.5}(B+\sqrt{A})\epsilon}}{(1-\gamma)^{1.5}}\frac{1}{\sqrt{\lambda}}$

The proof of theorem 1 establishes that the operator $\mathrm{GD}(\cdot)$ is a
contraction. In particular, it shows that

$\left\lVert\mathrm{GD}(d_{t})-d_{S}\right\rVert_{2}\leq\beta\left\lVert
d_{t}-d_{S}\right\rVert_{2}\quad\textrm{for
}\beta=\frac{12S^{3/2}(2\epsilon_{r}+5\epsilon_{p})}{\lambda(1-\gamma)^{4}}\
\textrm{ and }\lambda>12S^{3/2}(1-\gamma)^{-4}(2\epsilon_{r}+5S\epsilon_{p})$

This gives us the following recurrence relation on the iterates of the
algorithm.

$\displaystyle\left\lVert d_{t+1}-d_{S}\right\rVert_{2}$
$\displaystyle=\left\lVert\widehat{\mathrm{GD}}(d_{t})-d_{S}\right\rVert_{2}\leq\left\lVert\widehat{\mathrm{GD}}(d_{t})-{\mathrm{GD}}(d_{t})\right\rVert_{2}+\left\lVert{\mathrm{GD}}(d_{t})-d_{S}\right\rVert_{2}$
$\displaystyle\leq\frac{6\sqrt{S^{1.5}(B+\sqrt{A})\epsilon}}{(1-\gamma)^{1.5}}\frac{1}{\sqrt{\lambda}}+\beta\left\lVert
d_{t}-d_{S}\right\rVert_{2}$

We choose $\lambda=24S^{3/2}(1-\gamma)^{-4}(2\epsilon_{r}+5S\epsilon_{p})$
which ensures $\beta<1/2$ and gives the following recurrence.

$\displaystyle\left\lVert d_{t+1}-d_{S}\right\rVert_{2}\leq
2\sqrt{1-\gamma}\sqrt{\frac{(B+\sqrt{A})\epsilon}{2\epsilon_{r}+5S\epsilon_{p}}}+\beta\left\lVert
d_{t}-d_{S}\right\rVert_{2}\leq\beta\delta+\beta\left\lVert
d_{t}-d_{S}\right\rVert_{2}$ (26)

The last line requires the following bound on $\epsilon$.

$\displaystyle\epsilon\leq\frac{\beta^{2}\delta^{2}(2\epsilon_{r}+5S\epsilon_{p})}{4(1-\gamma)(B+\sqrt{A})}$
(27)

Substituting the bound on $\epsilon$ in equation (25) the required number of
samples at time-step $t$ is given as follows.

$\displaystyle
m_{t}\geq\frac{64A(B+\sqrt{A})^{2}}{\beta^{4}\delta^{4}(2\epsilon_{r}+5S\epsilon_{p})^{2}}\left(\ln\left(\frac{t}{p}\right)+\ln\left(\frac{4S(B+\sqrt{A})}{\beta\delta(2\epsilon_{r}+5S\epsilon_{p})}\right)\right)$

In order to analyze the recurrence relation (26) we consider two cases. First,
if $\left\lVert d_{t}-d_{S}\right\rVert_{2}\geq\delta$ we have

$\displaystyle\left\lVert d_{t+1}-d_{S}\right\rVert_{2}\leq 2\beta\left\lVert
d_{t}-d_{S}\right\rVert_{2}$

Since $\beta<1/2$ this is a contraction, and after $\ln(\left\lVert
d_{0}-d_{S}\right\rVert_{2})/\ln(1/2\beta)$ iterations we are guaranteed that
$\left\lVert d_{t}-d_{S}\right\rVert_{2}\leq\delta$. Since $\left\lVert
d_{0}-d_{S}\right\rVert_{2}\leq\frac{2}{1-\gamma}$, the required number of
iterations for this event to occur is given by the following upper bound.

$\frac{\ln(\left\lVert d_{0}-d_{S}\right\rVert_{2})}{\ln(1/2\beta)}\leq
2(1-2\beta)^{-1}\ln\left(\frac{2}{\delta(1-\gamma)}\right)$

On the other hand, if $\left\lVert d_{t}-d_{S}\right\rVert\leq\delta$,
equation (26) gives us

$\left\lVert d_{t+1}-d_{S}\right\rVert_{2}\leq
2\beta\delta<\delta\quad\textrm{[Since $\beta<1/2$]}$

Therefore, once $\left\lVert d_{t}-d_{S}\right\rVert_{2}\leq\delta$ we are
guaranteed that $\left\lVert d_{t^{\prime}}-d_{S}\right\rVert_{2}\leq\delta$
for any $t^{\prime}\geq t$. ∎

######  Lemma 10.

Suppose
$m\geq\frac{1}{\epsilon^{2}}\left(A\ln(2/\delta_{1})+\ln(4H/\epsilon)+2A\ln(\ln(SABH/\epsilon)/\epsilon)\right)$.
Then for any occupancy measure $d$ satisfying $\max_{s,a}d(s,a)/d_{t}(s,a)\leq
B$ and any $h$ with $\left\lVert h\right\rVert_{2}\leq H$ the following bound
holds with probability at least $1-\delta_{1}$.

$\left|\hat{\mathcal{L}}(d,h;M_{t})-\mathcal{L}(d,h;M_{t})\right|\leq\frac{6H\sqrt{S}(B+\sqrt{A})\epsilon}{1-\gamma}$

###### Proof.

Note that the expected value of the objective above equals
$\mathcal{L}(d,h;M_{t})$.

$\displaystyle\mathbb{E}\left[\hat{\mathcal{L}}(d,h;M_{t})\right]=-\frac{\lambda}{2}\left\lVert
d\right\rVert_{2}^{2}+\sum_{s}h(s)\rho(s)+\frac{1}{m}\sum_{i=1}^{m}\mathbb{E}\left[\frac{d(s_{i},a_{i})}{d_{t}(s_{i},a_{i})}\left(r(s_{i},a_{i})-h(s_{i})+\gamma
h(s_{i}^{\prime})\right)\right]$ $\displaystyle=-\frac{\lambda}{2}\left\lVert
d\right\rVert_{2}^{2}+\sum_{s}h(s)\rho(s)+\sum_{s,a}d_{t}(s,a)\frac{d(s,a)}{d_{t}(s,a)}\left(r(s,a)-h(s)+\gamma\sum_{s^{\prime}}P_{t}(s^{\prime}|s,a)h(s^{\prime})\right)$
$\displaystyle=\mathcal{L}(d,h;M_{t})$

By the overlap assumption 2 and the assumption $\left\lVert
h\right\rVert_{2}\leq H$ the following bound holds for each $i$,

$\frac{1}{1-\gamma}\frac{d(s_{i},a_{i})}{d_{t}(s_{i},a_{i})}\left(r(s_{i},a_{i})-h(s_{i})+\gamma
h(s_{i}^{\prime})\right)\leq\frac{2BH}{1-\gamma}.$

Therefore we can apply the Chernoff-Hoeffding inequality and obtain the
following inequality.

$P\left(\left|\hat{\mathcal{L}}(d,h;M_{t})-\mathcal{L}(d,h;M_{t})\right|\geq\frac{2BH}{1-\gamma}\sqrt{\frac{\ln(2/\delta_{1})}{m}}\right)\leq\delta_{1}$

We now extend this bound to any occupancy measure $d\in\mathcal{D}$ and $h$ in
the set $\mathcal{H}=\left\\{h:\left\lVert h\right\rVert_{2}\leq H\right\\}$.
By lemma 5.2 of [Ver10] we can choose an $\epsilon$-net,
$\mathcal{H}_{\epsilon}$ of the set $\mathcal{H}$ of size at most
$\left(1+\frac{2H}{\epsilon}\right)^{S}$ and for any point $h\in\mathcal{H}$
we are guaranteed to find $h^{\prime}\in\mathcal{H}_{\epsilon}$ so that
$\left\lVert h-h^{\prime}\right\rVert_{2}$.

However, such an additive error bound is not sufficient for the set of
occupancy measures because of the overlap assumption 2. So instead we choose a
multiplicative $\epsilon$-net as follows. For any $(s,a)$ we consider the grid
points $d_{t}(s,a),(1+\epsilon)d_{t}(s,a),\ldots,(1+\epsilon)^{p}d_{t}(s,a)$
for $p=\log(B/d_{t}(s,a))/\log(1+\epsilon)$. Although $d_{t}(s,a)$ can be
arbitrarily small, without loss of generality we can assume that
$d_{t}(s,a)\geq\frac{\epsilon}{4SABH}$. This is because from the expression of
$\mathcal{L}(d,h;M_{t})$ (11), it is clear that ignoring such small terms
introduces an error of at most $\epsilon/4$. Therefore we can choose
$p=2\log(SABH/\epsilon)/\log(1+\epsilon)$. Taking a Cartesian product over the
set of all state, action pairs we see that we can choose an $\epsilon$-net
$\mathcal{D}_{\epsilon}$ so that
$\left|\mathcal{D}_{\epsilon}\right|\leq\left(\frac{2\log(SABH/\epsilon)}{\log(1+\epsilon)}\right)^{SA}\leq\left(\frac{2\log(SABH/\epsilon)}{\epsilon}\right)^{SA}$.
Notice that we are guaranteed that for any $d\in\mathcal{D}$ there exists a
$d^{\prime}\in\mathcal{D}_{\epsilon}$ such that $d(s,a)/d^{\prime}(s,a)\leq
1+\epsilon$.

By a union bound over the elements in $\mathcal{H}_{\epsilon}$ and
$\mathcal{D}_{\epsilon}$ the following bound holds for any
$d\in\mathcal{D}_{\epsilon}$ and $h\in\mathcal{H}_{\epsilon}$ with probability
at least $1-\delta_{1}$.

$\left|\hat{\mathcal{L}}(d,h;M_{t})-\mathcal{L}(d,h;M_{t})\right|\leq\frac{2BH}{1-\gamma}\underbrace{\sqrt{\frac{SA\ln\left(\frac{2}{\delta_{1}}\right)+S\ln\left(\frac{4H}{\epsilon}\right)+2SA\ln(\ln(SABH/\epsilon)/\epsilon)}{m}}}_{:=T_{m}}$

We now extend the bound above for any $d\in\mathcal{D}$ and $h\in\mathcal{H}$
using lemma 11. There exists $\widetilde{d}\in\mathcal{D}_{\epsilon}$ so that
$\max_{s,a}d(s,a)/\widetilde{d}(s,a)\leq\epsilon$. Similarly there exists
$h_{\epsilon}\in\mathcal{H}_{\epsilon}$ so that $\left\lVert
h-\widetilde{h}\right\rVert_{2}\leq\epsilon$. Let
$\mathcal{L}^{0}(d,h;M_{t})=\mathcal{L}(d,h;M_{t})+\frac{\lambda}{2}\left\lVert
d\right\rVert_{2}^{2}-\sum_{s}h(s)\rho(s)$.

$\displaystyle\left|\hat{\mathcal{L}}(d,h;M_{t})-\mathcal{L}(d,h;M_{t})\right|\leq\left|\hat{\mathcal{L}}^{0}(d,h;M_{t})-\hat{\mathcal{L}}^{0}(\widetilde{d},\widetilde{h};M_{t})\right|$
$\displaystyle+\left|\hat{\mathcal{L}}(\widetilde{d},\widetilde{h};M_{t})-{\mathcal{L}}(\widetilde{d},\widetilde{h};M_{t})\right|+\left|{\mathcal{L}}^{0}(\widetilde{d},\widetilde{h};M_{t})-{\mathcal{L}}^{0}({d},{h};M_{t})\right|$
$\displaystyle\leq\frac{2BHT_{m}}{1-\gamma}+\frac{6\sqrt{SA}H\epsilon}{1-\gamma}+\frac{4BH\sqrt{S}\epsilon}{1-\gamma}$

Therefore, if
$m\geq\frac{1}{\epsilon^{2}}\left(A\ln(2/\delta_{1})+\ln(4H/\epsilon)+2A\ln(\ln(SABH/\epsilon)/\epsilon)\right)$
then $T_{m}\leq\sqrt{S}\epsilon$ and we have the following bound.

$\left|\hat{\mathcal{L}}(d,h;M_{t})-\mathcal{L}(d,h;M_{t})\right|\leq\frac{6H\sqrt{S}(B+\sqrt{A})\epsilon}{1-\gamma}$

∎

######  Lemma 11.

Suppose we are guaranteed that $\frac{d(s,a)}{\widetilde{d}(s,a)}\leq
1+\epsilon$ and $\left\lVert h-\widetilde{h}\right\rVert_{2}\leq\epsilon$, and
$\left\lVert h\right\rVert_{2},\left\lVert\widetilde{h}\right\rVert_{2}\leq
H$. Let
$\mathcal{L}^{0}(d,h;M_{t})=\mathcal{L}(d,h;M_{t})+\frac{\lambda}{2}\left\lVert
d\right\rVert_{2}^{2}-\sum_{s}h(s)\rho(s)$ and define
$\hat{\mathcal{L}}^{0}(d,h;M_{t})$ analogously. Then the following
inequalities hold.

$\left|\mathcal{L}^{0}(d,h;M_{t})-\mathcal{L}^{0}(\widetilde{d},\widetilde{h};M_{t})\right|\leq\frac{6\sqrt{SA}H\epsilon}{1-\gamma}\quad\textrm{
and }$
$\left|\hat{\mathcal{L}}^{0}(d,h;M_{t})-\hat{\mathcal{L}}^{0}(\widetilde{d},\widetilde{h};M_{t})\right|\leq\frac{4BH\sqrt{S}\epsilon}{1-\gamma}$

###### Proof.

First note that $\left\lVert
d-\widetilde{d}\right\rVert_{2}^{2}=\sum_{s,a}\left(d(s,a)-\widetilde{d}(s,a)\right)^{2}\leq\sum_{s,a}d(s,a)^{2}\epsilon^{2}\leq\frac{\epsilon^{2}}{(1-\gamma)^{2}}$.

$\displaystyle\left|\mathcal{L}^{0}(d,h;M_{t})-\mathcal{L}^{0}(\widetilde{d},\widetilde{h};M_{t})\right|\leq\sum_{s,a}\left|d(s,a)-\widetilde{d}(s,a)\right|$
$\displaystyle+\underbrace{\left|\sum_{s,a}d(s,a)h(s)-\widetilde{d}(s,a)\widetilde{h}(s)\right|}_{:=T_{1}}+\gamma\underbrace{\sum_{s,a}\left|d(s,a)\sum_{s^{\prime}}P_{t}(s,a,s^{\prime})h(s^{\prime})-\widetilde{d}(s,a)\sum_{s^{\prime}}P_{t}(s,a,s^{\prime})\widetilde{h}(s^{\prime})\right|}_{:=T_{2}}$

We now bound the terms $T_{1}$ and $T_{2}$.

$\displaystyle T_{1}$
$\displaystyle=\left|\sum_{s,a}d(s,a)\left(h(s)-\widetilde{h}(s)\right)+\widetilde{h}(s)\left(d(s,a)-\widetilde{d}(s,a)\right)\right|$
$\displaystyle\leq\left\lVert
h-\widetilde{h}\right\rVert_{1}\sum_{s,a}d(s,a)+\sqrt{\sum_{s}(\widetilde{h}(s))^{2}}\sqrt{\sum_{s}\left(\sum_{a}(d(s,a)-\widetilde{d}(s,a)\right)^{2}}$
$\displaystyle\leq\frac{\sqrt{S}\epsilon}{1-\gamma}+\frac{H\sqrt{A}\epsilon}{1-\gamma}$
$\displaystyle T_{2}$
$\displaystyle=\sum_{s,a}\left|d(s,a)\sum_{s^{\prime}}P_{t}(s,a,s^{\prime})h(s^{\prime})-\widetilde{d}(s,a)\sum_{s^{\prime}}P_{t}(s,a,s^{\prime})\widetilde{h}(s^{\prime})\right|$
$\displaystyle=\sum_{s,a}\left|d(s,a)-\widetilde{d}(s,a)\right|\sum_{s^{\prime}}P_{t}(s,a,s^{\prime})\left|h(s^{\prime})\right|+\sum_{s,a}\widetilde{d}(s,a)\sum_{s^{\prime}}P_{t}(s,a,s^{\prime})\left|h(s^{\prime})-\widetilde{h}(s^{\prime})\right|$
$\displaystyle\leq\left\lVert h\right\rVert_{2}\left\lVert
d-\widetilde{d}\right\rVert_{1}+\left\lVert
h-\widetilde{h}\right\rVert_{1}\sum_{s,a}\widetilde{d}(s,a)$
$\displaystyle\leq\frac{\sqrt{SA}H\epsilon}{1-\gamma}+\frac{\sqrt{S}\epsilon}{1-\gamma}$

Substituting the bounds on $T_{1}$ and $T_{2}$ we get the following bound on
$\left|\mathcal{L}(d,h;M_{t})-\mathcal{L}(\widetilde{d},\widetilde{h};M_{t})\right|$.

$\displaystyle\left|\mathcal{L}^{0}(d,h;M_{t})-\mathcal{L}^{0}(\widetilde{d},\widetilde{h};M_{t})\right|\leq\sqrt{SA}\epsilon+\frac{2\sqrt{S}\epsilon}{1-\gamma}+\frac{2\sqrt{SA}H\epsilon}{1-\gamma}$

We now consider bounding the difference
$\left|\hat{\mathcal{L}}^{0}(d,h;M_{t})-\hat{\mathcal{L}}^{0}(\widetilde{d},\widetilde{h};M_{t})\right|$.

$\displaystyle\left|\hat{\mathcal{L}}^{0}(d,h;M_{t})-\hat{\mathcal{L}}^{0}(\widetilde{d},\widetilde{h};M_{t})\right|\leq$