# Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality

Tengyu Xu  Zhuoran Yang  Zhaoran Wang  Yingbin Liang

###### Abstract

Designing off-policy reinforcement learning algorithms is typically a very
challenging task, because a desirable iteration update often involves an
expectation over an on-policy distribution. Prior off-policy actor-critic (AC)
algorithms have introduced a new critic that uses the density ratio for
adjusting the distribution mismatch in order to stabilize the convergence, but
at the cost of potentially introducing high biases due to the estimation
errors of both the density ratio and value function. In this paper, we develop
a doubly robust off-policy AC (DR-Off-PAC) for discounted MDP, which can take
advantage of learned nuisance functions to reduce estimation errors. Moreover,
DR-Off-PAC adopts a single timescale structure, in which both actor and
critics are updated simultaneously with constant stepsize, and is thus more
sample efficient than prior algorithms that adopt either two timescale or
nested-loop structure. We study the finite-time convergence rate and
characterize the sample complexity for DR-Off-PAC to attain an
$\epsilon$-accurate optimal policy. We also show that the overall convergence
of DR-Off-PAC is doubly robust to the approximation errors that depend only on
the expressive power of approximation functions. To the best of our knowledge,
our study establishes the first overall sample complexity analysis for a
single time-scale off-policy AC algorithm.

Reinforcement Learning, Off-Policy Policy Optimization, Global Convergence

##  1 Introduction

In reinforcement learning (RL) (Sutton & Barto, 2018), policy gradient and its
variant actor-critic (AC) algorithms have achieved enormous success in various
domains such as game playing (Mnih et al., 2016), Go (Silver et al., 2016),
robotic (Haarnoja et al., 2018), etc. However, these successes usually rely on
the access to on-policy samples, i.e., samples collected online from on-policy
visitation (or stationary) distribution. However, in many real-world
applications, online sampling during a learning process is costly and unsafe
(Gottesman et al., 2019). This necessitates the use of off-policy methods,
which use dataset sampled from a behavior distribution. Since the policy
gradient is expressed in the form of the on-policy expectation, it is
challenging to estimate the policy gradient with off-policy samples. A common
approach to implement actor-critic algorithms in the off-policy setting is to
simply ignore the distribution mismatch between on- and off-policy
distributions (Degris et al., 2012; Silver et al., 2014; Lillicrap et al.,
2016; Fujimoto et al., 2018; Wang et al., 2016; Houthooft et al., 2018;
Meuleau et al., 2001) but it has been demonstrated that such distribution
mismatch can often result in divergence and poor empirical performance (Liu et
al., 2019).

Several attempts have been made to correct the distribution mismatch in off-
policy actor-critic’s update by introducing a reweighting factor in policy
update (Imani et al., 2018; Zhang et al., 2019b; Liu et al., 2019; Zhang et
al., 2019c; Maei, 2018), but so far only COF-PAC (Zhang et al., 2019c) and
OPPOSD (Liu et al., 2019) have been theoretically shown to converge without
making strong assumptions about the estimation quality. Specifically, COF-PAC
reweights the policy update with emphatic weighting approximated by a linear
function, and OPPOSD reweights the policy with a density correction ratio
learned by a method proposed in (Liu et al., 2018). Although both COF-PAC and
OPPOSD show much promise by stabilizing the convergence, the convergence
results in (Zhang et al., 2019c) and (Liu et al., 2019) indicate that both
algorithms may suffer from a large bias error induced by estimations of both
reweighting factor and value function.

The doubly robust method arises as a popular technique to reduce such a bias
error, in which the bias vanishes as long as some (but not necessarily the
full set of) estimations are accurate. Such an approach has been mainly
applied to the off-policy evaluation problem (Tang et al., 2019; Jiang & Li,
2016; Dudík et al., 2011, 2014), and the development of such a method for
solving the policy optimization problem is rather limited. (Huang & Jiang,
2020) derives a doubly robust policy gradient for finite-horizon Markov
Decision Process (MDP) and only for the on-policy setting. (Kallus & Uehara,
2020) proposed a doubly robust policy gradient estimator for the off-policy
setting, but only for infinite-horizon averaged MDP, which does not extend
easily to discounted MDP. Moreover, model-free implementation of such doubly
robust policy gradient estimators typically requires the estimation of several
nuisance functions via samples, but previous works proposed only methods for
critic to estimate those nuisances in the finite-horizon setting, which cannot
extend efficiently to the infinite-horizon setting.

Thus, our first goal is to propose a novel doubly robust policy gradient
estimator for infinite-horizon discounted MDP, and further design efficient
model-free critics to estimate nuisance functions so that such an estimator
can be effectively incorporated to yield a doubly robust off-policy actor-
critic algorithm.

On the theory side, previous work has established only the doubly robust
estimation, i.e., the policy gradient estimator is doubly robust (Huang &
Jiang, 2020; Kallus & Uehara, 2020). However, it is very unclear that by
incorporating such a doubly robust estimator into an actor-critic algorithm,
whether the overall convergence of the algorithm remains doubly robust, i.e.,
enjoys doubly robust optimality gap. Several reasons may eliminate such a nice
property. For example, the alternating update between actor and critic does
not allow critics’ each estimation to be sufficiently accurate, so that doubly
robust estimation may not hold at each round of iteration. Furthermore, the
optimality gap of the overall convergence of an algorithm depends on
interaction between critics’ estimation error and actor’s update error as well
as other sampling variance errors, so that the double robust estimation does
not necessarily yield the doubly robust optimality gap.

Thus, our second goal is to establish a finite-time convergence guarantee for
our proposed algorithm, and show that the optimality gap of the overall
convergence of our algorithm remains doubly robust.

###  1.1 Main Contributions

Doubly Robust Estimator: We propose a new method to derive a doubly robust
policy gradient estimator for an infinite-horizon discounted MDP. Comparing
with the previously proposed estimators that adjust only the distribution
mismatch (Liu et al., 2019; Imani et al., 2018; Zhang et al., 2019b, c), our
new estimator significantly reduces the bias error when two of the four
nuisances in our estimator are accurate (and is hence doubly robust). We
further propose a new recursive method for critics to estimate the nuisances
in the infinite-horizon off-policy setting. Based on our proposed new
estimator and nuisance estimation methods, we develop a model-free doubly
robust off-policy actor-critic (DR-Off-PAC) algorithm.

Doubly Robust Optimality Gap: We provide the finite-time convergence analysis
for our DR-Off-PAC algorithm with single timescale updates. We show that DR-
Off-PAC is guaranteed to converge to the optimal policy, and the optimality
gap of the overall convergence is also doubly robust to the approximation
errors. This result is somewhat surprising, because the doubly robust policy
gradient update suffers from both non-vanishing optimization error and
approximation error at each iteration, whereas the double robustness of the
optimality gap is independent of the optimization error. This also indicates
that we can improve the optimality gap of DR-Off-PAC by adopting a powerful
function class to estimate certain nuisance functions.

Our work is the first that characterizes the doubly robust optimality gap for
the overall convergence of off-policy actor-critic algorithms, for which we
develop new tools for analyzing actor-critic and critic-critic error
interactions.

###  1.2 Related Work

The first off-policy actor-critic algorithm is proposed in (Degris et al.,
2012) as Off-PAC, and has inspired the invention of many other off-policy
actor-critic algorithms such as off-policy DPG (Silver et al., 2014), DDPG
(Lillicrap et al., 2016), TD3 (Fujimoto et al., 2018), ACER (Wang et al.,
2016), and off-policy EPG (Houthooft et al., 2018), etc, all of which have the
distribution mismatch between the sampling distribution and visitation (or
stationary) distribution of updated policy, and hence are not provably
convergent under function approximation settings.

In one line of studies, off-policy design adopts reward shaping via entropy
regularization and optimizes over a different objective function that does not
require the knowledge of behaviour sampling (Haarnoja et al., 2018; O’Donoghue
et al., 2016; Dai et al., 2018; Nachum et al., 2017, 2018; Schulman et al.,
2017; Haarnoja et al., 2017; Tosatto et al., 2020). Although the issue of
distribution mismatch is avoided for this type of algorithms, they do not have
convergence guarantee in general settings. The distribution mismatch issue is
also avoided in a gradient based algorithm AlgaeDICE (Nachum et al., 2019), in
which the original problem is reformulated into a minimax problem. However,
since nonconvex minimax objective is in general difficult to optimize, the
convergence of AlgaeDICE is not clear.

In another line of works, efforts have been made to address the issue of
distribution mismatch in Off-PAC. (Imani et al., 2018) developed actor-critic
with emphatic weighting (ACE), in which the convergence of Off-PAC is
ameliorated by using emphatic weighting (Sutton et al., 2016). Inspired by ACE
and the density ratio in (Gelada & Bellemare, 2019), (Zhang et al., 2019b)
proposed Geoff-PAC to optimize a new objective. Based on Geoff-PAC, (Lyu et
al., 2020) further applied the variance reduction technique in (Cutkosky &
Orabona, 2019) to develop a new algorithm VOMPS/ACE-STORM. However, since the
policy gradient estimator with emphatic weighting is only unbiased in
asymptotic sense and emphatic weighting usually suffers from unbounded
variance, the convergence of ACE, Geoff-PAC and VOMPS/ACE-STORM are in general
not clear. So far, only limited off-policy actor-critic algorithms have been
shown to have guaranteed convergence. (Zhang et al., 2019c) proposed a
provably convergent two timescale off-policy actor-critic via learning the
emphatic weights with linear features, and (Liu et al., 2019) proposed to
reweight the off-PAC update via learning the density ratio with the approach
in (Liu et al., 2018). However, both convergence results in (Liu et al., 2019)
and (Zhang et al., 2019c) suffer from bias errors of function approximation,
and the two timescale update and the double-loop structure adopted in (Zhang
et al., 2019c) and (Liu et al., 2019), respectively, can cause significant
sample inefficiency. Recently, (Kallus & Uehara, 2020) proposed an off-policy
gradient method with doubly robust policy gradient estimator. However, they
also adopted an inefficient double-loop structure and the overall convergence
of the algorithm with such an estimator was not shown to have the doubly
robust property. In contrast to previous works, we develop a new doubly robust
off-policy actor-critic that provably converges with the overall convergence
also being doubly robust to the function approximation errors. Our algorithm
adopts a single-timescale update scheme, and is thus more sample efficient
than the previous methods (Liu et al., 2019; Zhang et al., 2019c; Kallus &
Uehara, 2020).

##  2 Background and Problem Formulation

In this section, we introduce the background of Markov Decision Process (MDP)
and problem formulation. We consider an infinite-horizon MDP described by
$(\mathcal{S},\mathcal{A},\mathsf{P},r,\mu_{0},\gamma)$, where $\mathcal{S}$
denotes the set of states, $\mathcal{A}$ denotes the set of actions, and
$\mathsf{P}(s^{\prime}|s,a)$ denotes the transition probability from state
$s\in\mathcal{S}$ to state $s^{\prime}$ with action $a\in\mathcal{A}$. Note
that $\left|\mathcal{S}\right|$ and $\left|\mathcal{A}\right|$ can be infinite
such that $\mathsf{P}(s^{\prime}|s,a)$ is then a Markov kernel. Let
$r(s,a,s^{\prime})$ be the reward that an agent receives if the agent takes an
action $a$ at state $s$ and the system transits to state $s^{\prime}$.
Moreover, we denote $\mu_{0}$ as the distribution of the initial state
$s_{0}\in\mathcal{S}$ and $\gamma\in(0,1)$ as the discount factor. Let
$\pi(a|s)$ be the policy which is the probability of taking action $a$ given
current state $s$. Then, for a given policy $\pi$, we define the state value
function as
$V_{\pi}(s)=\mathbb{E}[\gamma^{t}r(s_{t},a_{t},s_{t+1})|s_{0}=s,\pi]$ and the
state-action value function as
$Q_{\pi}(s,a)=\mathbb{E}[\gamma^{t}r(s_{t},a_{t},s_{t+1})|s_{0}=s,a_{0}=a,\pi]$.
Note that $V_{\pi}(s)=\mathbb{E}_{\pi}[Q_{\pi}(s,a)|s]$ and $Q_{\pi}(s,a)$
satisfies the following Bellman equation:

$\displaystyle Q_{\pi}(s,a)=R(s,a)+\gamma\mathcal{P}_{\pi}Q_{\pi}(s,a),$ (1)

where $R(s,a)=\mathbb{E}[r(s,a,s^{\prime})|s,a]$ and

$\displaystyle\mathcal{P}_{\pi}Q_{\pi}(s,a)\coloneqq\mathbb{E}_{s^{\prime}\sim\mathsf{P}(\cdot|s,a),a^{\prime}\sim\pi(\cdot|s^{\prime})}[Q_{\pi}(s^{\prime},a^{\prime})].$

We further define the expected total reward function as
$J(\pi)=(1-\gamma)\mathbb{E}[\gamma^{t}r(s_{t},a_{t},s_{t+1})|s_{0}\sim\mu_{0},\pi]=\mathbb{E}_{\mu_{0}}[V_{\pi}(s)]=\mathbb{E}_{\nu_{\pi}}[r(s,a,s^{\prime})]$,
where
$\nu_{\pi}(s,a)=(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}\mathsf{P}(s_{t}=s,a_{t}=a|s_{0}\sim\mu_{0},\pi)$
is the visitation distribution. The visitation distribution satisfies the
following “inverse” Bellman equation:

$\displaystyle\nu_{\pi}(s^{\prime},a^{\prime})$
$\displaystyle=\pi(a^{\prime}|s^{\prime})[(1-\gamma)\mu_{0}(s^{\prime})$
$\displaystyle+\gamma\int_{(s,a)}\mathsf{P}(s^{\prime}|s,a)\nu_{\pi}(s,a)dsda].$
(2)

In policy optimization, the agent’s goal is to find an optimal policy
$\pi^{*}$ that maximizes $J(\pi)$, i.e.,
$\pi^{*}=\operatorname*{argmax}_{\pi}J(\pi)$. We consider the setting in which
policy $\pi$ is parametrized by $w\in\mathbb{R}^{d}$. Then, the policy
optimization is to solve the problem $\max_{w}J(\pi_{w})$. In the sequel we
write $J(\pi_{w}):=J(w)$ for notational simplicity. A popular approach to
solve such a maximization problem is the policy gradient method, in which we
update the policy in the gradient ascent direction as
$w_{t+1}=w_{t}+\alpha\nabla_{w}J(w_{t})$. A popular form of $\nabla_{w}J(w)$
is derived by (Sutton et al., 2000) as

$\displaystyle\nabla_{w}J(w)=\mathbb{E}_{\nu_{\pi_{w}}}[Q_{\pi_{w}}(s,a)\nabla_{w}\log\pi_{w}(a|s)].$
(3)

In the on-policy setting, many works adopt the policy gradient formulation in
eq. 3 to estimate $\nabla_{w}J(w)$, which requires sampling from the
visitation distribution $\nu_{\pi_{w}}$ and Monte Carlo rollout from policy
$\pi_{w}$ to estimate the value function $Q_{\pi_{w}}(s,a)$ (Zhang et al.,
2019a; Xiong et al., 2020).

In this paper we focus on policy optimization in the behavior-agnostic off-
policy setting. Specifically, we are given access to samples from a fixed
distribution $\\{(s_{i},a_{i},r_{i},s^{\prime}_{i})\\}\sim\mathcal{D}_{d}$,
where the state-action pair $(s_{i},a_{i})$ is sampled from an unknown
distribution $d(\cdot):\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$, the
successor state $s^{\prime}_{i}$ is sampled from
$\mathsf{P}(\cdot|s_{i},a_{i})$ and $r_{i}$ is the received reward. We also
have access to samples generated from the initial distribution, i.e.,
$s_{0,i}\sim\mu_{0}$. In the behavior-agnostic off-policy setting, it is
difficult to estimate $\nabla_{w}J(w)$ directly with the form in eq. 3, as
neither $\nu_{\pi_{w}}$ nor Monte Carlo rollout sampling is accessible. Thus,
our goal is to develop an efficient algorithm to estimate $\nabla_{w}J(w)$
with off-policy samples from $\mathcal{D}_{d}$, and furthermore, establish the
convergence guarantee for our proposed algorithm.

##  3 DR-Off-PAC: Algorithm and Convergence

In this section, we first develop a new doubly robust policy gradient
estimator and then design a new doubly robust off-policy actor-critic
algorithm.

###  3.1 Doubly Robust Policy Gradient Estimator

In this subsection, we construct a new doubly robust policy gradient estimator
for an infinite-horizon discounted MDP. We first denote the density ratio as
$\rho_{\pi_{w}}=\nu_{\pi_{w}}(s,a)/d(s,a)$, and denote the derivative of
$Q_{\pi_{w}}$ and $\rho_{\pi_{w}}$ as $d^{q}_{\pi_{w}}$ and
$d^{\rho}_{\pi_{w}}$, respectively.

Previous constructions (Kallus & Uehara, 2020) for such an estimator directly
combine the policy gradient with a number of error terms under various
filtrations to guarantee the double robustness. Such a method does not appear
to extend easily to the discounted MDP. Specifically, the method in (Kallus &
Uehara, 2020) considers finite-horizon MDP with $\gamma=1$, and further
extends their result to infinite-horizon average-reward MDP. Their extension
relies on the fact that the objective function $J(w)$ in average-reward MDP is
independent of the initial distribution $\mu_{0}$. In contrast, $J(w)$ in
discounted-reward MDP depends on $\mu_{0}$. Any direct extension necessarily
results in a bias due to the lack of the initial distribution, which is
unknown a priori, and hence loses the doubly robust property.

To derive a doubly robust gradient estimator in the discounted MDP setting, we
first consider a bias reduced estimator of the objective $J(w)$ with off-
policy sample $(s,a,r,s^{\prime})$ and $s_{0}$, and then take the derivative
of such an estimator to obtain a doubly robust policy gradient estimator. The
idea behind this derivation is that as long as the objective estimator has
small bias, the gradient of such an estimator can also have small bias. More
detailed discussion can be referred to the supplement material.

Given sample $s_{0}\sim\mu_{0}(\cdot)$ and
$(s,a,r,s^{\prime})\sim\mathcal{D}_{d}$ and estimators $\hat{Q}_{\pi_{w}}$,
$\hat{\rho}_{\pi_{w}}$, $\hat{d}^{q}_{\pi_{w}}$ and
$\hat{d}^{\rho}_{\pi_{w}}$, our constructed doubly robust policy gradient
error is given as follows.

$\displaystyle G_{\text{DR}}(w)$
$\displaystyle=(1-\gamma)\Big{(}\hat{Q}_{\pi_{w}}(s_{0},a_{0})\nabla_{w}\log\pi_{w}(a_{0}|s_{0})+\hat{d}^{q}_{\pi_{w}}(s_{0},a_{0})\Big{)}$
$\displaystyle+\hat{d}^{\rho}_{\pi_{w}}(s,a)\left(r(s,a,s^{\prime})-\hat{Q}_{\pi_{w}}(s,a)+\gamma\hat{Q}_{\pi_{w}}(s^{\prime},a^{\prime})\right)$
$\displaystyle+\hat{\rho}_{\pi_{w}}(s,a)\Big{[}-\hat{d}^{q}_{\pi_{w}}(s,a)$
$\displaystyle+\gamma\Big{(}\hat{Q}_{\pi_{w}}(s^{\prime},a^{\prime})\nabla_{w}\log\pi_{w}(a^{\prime}|s^{\prime})+\hat{d}^{q}_{\pi_{w}}(s^{\prime},a^{\prime})\Big{)}\Big{]},$
(4)

where $a_{0}\sim\pi_{w}(\cdot|s_{0})$ and
$a^{\prime}\sim\pi_{w}(\cdot|s^{\prime})$. The following theorem establishes
that our proposed estimator $G_{\text{DR}}$ satisfies the doubly robust
property.

######  Theorem 1.

The bias error of estimator $G_{\text{DR}}(w)$ in eq. 4 satisfies

$\displaystyle\mathbb{E}[G_{\text{DR}}(w)]-\nabla_{w}J(w)$
$\displaystyle=-\mathbb{E}[\varepsilon_{\rho}(s,a)\varepsilon_{d^{q}}(s,a)]-\mathbb{E}[\varepsilon_{d^{\rho}}(s,a)\varepsilon_{q}(s,a)]$
$\displaystyle\quad+\gamma\mathbb{E}[\varepsilon_{\rho}(s,a)\varepsilon_{q}(s^{\prime},a^{\prime})\nabla_{w}\log(a^{\prime}|s^{\prime})]$
$\displaystyle\quad+\gamma\mathbb{E}[\varepsilon_{\rho}(s,a)\varepsilon_{d^{q}}(s^{\prime},a^{\prime})]+\gamma\mathbb{E}[\varepsilon_{\rho}(s,a)\varepsilon_{q}(s^{\prime},a^{\prime})],$

where the estimation errors are defined as

$\displaystyle\varepsilon_{\rho}=\rho_{\pi_{w}}-\hat{\rho}_{\pi_{w}},\quad\varepsilon_{q}=Q_{\pi_{w}}-\hat{Q}_{\pi_{w}},$
$\displaystyle\varepsilon_{d^{\rho}}=d^{\rho}_{\pi_{w}}-\hat{d}^{\rho}_{\pi_{w}},\quad\varepsilon_{d^{q}}=d^{q}_{\pi_{w}}-\hat{d}^{q}_{\pi_{w}}.$

Theorem 1 shows that the estimation error of $G_{\text{DR}}(w)$ takes a
multiplicative form of pairs of individual estimation errors rather than the
summation over all errors. Such a structure thus exhibits a three-way doubly
robust property. Namely, as long as one of the three pairs
$(\hat{\rho}_{\pi_{w}},\hat{d}^{\rho}_{\pi_{w}})$,
$(\hat{Q}_{\pi_{w}},\hat{d}^{q}_{\pi_{w}})$,
$(\hat{\rho}_{\pi_{w}},\hat{Q}_{\pi_{w}})$ are accurately estimated, our
estimator $G_{\text{DR}}(w)$ is unbiased, i.e.,
$\mathbb{E}[G_{\text{DR}}(w)]-\nabla_{w}J(w)=0$. There is no need for all of
the individual errors to be small.

###  3.2 Estimation of Nuisance Functions

In order to incorporate the doubly robust estimator eq. 4 into an actor-critic
algorithm, we develop critics to respectively construct efficient estimators
$\hat{Q}_{\pi_{w}}$, $\hat{\rho}_{\pi_{w}}$, $\hat{d}^{q}_{\pi_{w}}$,
$\hat{d}^{\rho}_{\pi_{w}}$ in $G_{\text{DR}}(w)$ in the linear function
approximation setting.

Critic I: Value function $\hat{Q}_{\pi_{w}}$ and density ratio
$\hat{\rho}_{\pi_{w}}$. In the off-policy evaluation problem, (Yang et al.,
2020) shows that the objective function $J(w)$ can be expressed by the
following primal linear programming (LP):

$\displaystyle\min_{Q_{\pi_{w}}}\quad(1-\gamma)\mathbb{E}_{\mu_{0}\pi_{w}}[Q_{\pi_{w}}(s,a)]$
$\displaystyle\text{s.t.,}\quad
Q_{\pi_{w}}(s,a)=R(s,a)+\gamma\mathcal{P}_{\pi}Q_{\pi_{w}}(s,a),$

with the corresponding dual LP given by

$\displaystyle\max_{\nu_{\pi_{w}}}\quad\mathbb{E}_{\nu_{\pi_{w}}}[R(s,a)]$
$\displaystyle\text{s.t.,}\quad\nu_{\pi}(s^{\prime},a^{\prime})=(1-\gamma)\mu_{0}(s^{\prime})\pi(a^{\prime}|s^{\prime})+\gamma\mathcal{P}^{*}_{\pi}\nu_{\pi}(s,a).$

Then, the value function $Q_{\pi_{w}}(s,a)$ and the distribution correction
ratio $\rho_{\pi_{w}}(s,a)$ can be learned by solving the following
regularized Lagrangian:

$\displaystyle\quad\min_{\hat{\rho}_{\pi_{w}}\geq
0}\max_{\hat{Q}_{\pi_{w}},\eta}L(\hat{\rho}_{\pi_{w}},\hat{Q}_{\pi_{w}},\eta)$
$\displaystyle\coloneqq(1-\gamma)\mathbb{E}_{\mu_{0}}[\hat{Q}_{\pi_{w}}(s,a)]+\mathbb{E}_{\mathcal{D}_{d}}[\rho_{\pi_{w}}(s,a)(r(s,a,s^{\prime})$
$\displaystyle\quad+\gamma\hat{Q}_{\pi_{w}}(s^{\prime},a^{\prime})-\hat{Q}_{\pi_{w}}(s,a))]-\frac{1}{2}\mathbb{E}_{\mathcal{D}_{d}}[\hat{Q}_{\pi_{w}}(s,a)^{2}]$
$\displaystyle\quad+\mathbb{E}_{\mathcal{D}_{d}}[\eta\hat{\rho}_{\pi_{w}}(s,a)-\eta]-0.5\eta^{2}.$
(5)

We construct $\hat{\rho}_{\pi_{w}}$ and $\hat{Q}_{\pi_{w}}$ with linearly
independent feature $\phi(s,a)\in\mathbb{R}^{d_{1}}$:
$\hat{\rho}_{\pi_{w}}(s,a)=\phi(s,a)^{\top}\theta_{\rho}$ and
$\hat{Q}_{\pi_{w}}(s,a)=\phi(s,a)^{\top}\theta_{q}$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$. In such a case,
$L(\rho_{\pi_{w}},Q_{\pi_{w}},\eta)$ is strongly-concave in both $\theta_{q}$
and $\eta$, and convex in $\theta_{\rho}$. We denote the global optimum of
$L(\theta_{\rho},\theta_{q},\eta)$ as $\theta^{*}_{\rho,w}$,
$\theta^{*}_{q,w}$ and $\eta^{*}_{w}$. The errors of approximating
$Q_{\pi_{w}}$ and $\rho_{\pi_{w}}$ with estimators
$\hat{Q}_{\pi_{w}}(s,a,\theta^{*}_{q,w})=\phi(s,a)^{\top}\theta^{*}_{q,w}$ and
$\hat{\rho}_{\pi_{w}}(s,a,\theta^{*}_{q,w})=\phi(s,a)^{\top}\theta^{*}_{\rho,w}$,
respectively, are defined as

$\displaystyle\epsilon_{q}$
$\displaystyle=\max\Big{\\{}\max_{w}\sqrt{\mathbb{E}_{\mathcal{D}}[(\hat{Q}_{\pi_{w}}(s,a,\theta^{*}_{q,w})-{Q}_{\pi_{w}}(s,a))^{2}]},$
$\displaystyle\max_{w}\sqrt{\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w}}[(\hat{Q}_{\pi_{w}}(s^{\prime},a^{\prime},\theta^{*}_{q,w})-{Q}_{\pi_{w}}(s^{\prime},a^{\prime}))^{2}]}\Big{\\}},$
$\displaystyle\epsilon_{\rho}$
$\displaystyle=\max_{w}\sqrt{\mathbb{E}_{\mathcal{D}}[(\hat{\rho}_{\pi_{w}}(s,a,\theta^{*}_{\rho,w})-{\rho}_{\pi_{w}}(s,a))^{2}]}.$

To solve the minimax optimization problem in eq. 5, we adopt stochastic
gradient descent-ascent method with mini-batch samples
$\mathcal{B}_{t}=\\{(s_{i},a_{i},r_{i},s^{\prime}_{i})\\}_{i=1\cdots
N}\sim\mathcal{D}_{d}$, $a^{\prime}_{i}\sim\pi_{w_{t}}(\cdot|s^{\prime}_{i})$
and $\mathcal{B}_{t,0}=\\{(s_{0,i})\\}_{i=1\cdots N}\sim\mu_{0}$,
$a_{0,i}\sim\pi_{w_{t}}(\cdot|s^{\prime}_{0,i})$, which update parameters
recursively as follows

$\displaystyle\delta_{t,i}$
$\displaystyle=(1-\gamma)\phi_{0,i}+\gamma\phi_{i}^{\top}\theta_{\rho,t}\phi^{\prime}_{i}-\phi_{i}^{\top}\theta_{\rho,t}\phi_{i}$
$\displaystyle\eta_{t+1}$
$\displaystyle=\theta_{\rho,t}+\beta_{1}\frac{1}{N}\sum_{i\in\mathcal{B}_{t}}(\phi_{i}^{\top}\theta_{\rho,t}-1-\eta_{t})$
$\displaystyle\theta_{q,t+1}$
$\displaystyle=\Gamma_{R_{q}}\Big{[}\theta_{q,t}+\beta_{1}\frac{1}{N}\sum_{i\in\mathcal{B}_{t},\mathcal{B}_{t,0}}(\delta_{t,i}-\phi^{\top}_{i}\theta_{q,t}\phi_{i})\Big{]}$
$\displaystyle\theta_{\rho,t+1}$
$\displaystyle=\Gamma_{R_{\rho}}\Big{[}\theta_{\rho,t}-\beta_{1}\frac{1}{N}\sum_{i\in\mathcal{B}_{t}}(r_{i}\phi_{i}+\gamma\phi^{\prime\top}_{i}\theta_{q,t}\phi_{i}$
$\displaystyle\qquad\qquad\qquad-\phi_{i}^{\top}\theta_{q,t}\phi_{i}+\eta_{t}\phi_{i})\Big{]},$
(6)

where $\Gamma_{R}$ indicates the projection onto a ball with radius $R$. Such
a projection operator stabilizes the algorithm (Konda & Tsitsiklis, 2000;
Bhatnagar et al., 2009). Note that the iteration in eq. 6 is similar to but
difference from the GradientDICE update in (Zhang et al., 2020b), as
GradientDICE can learn only the density ratio $\rho_{\pi_{w}}$, while our
approach in eq. 6 can learn both the value function $Q_{\pi_{w}}$ and the
density ratio $\rho_{\pi_{w}}$.

Critic II: Derivative of value function $\hat{d}^{q}_{\pi_{w}}$. Taking
derivative on both sides of eq. 1 yields

$\displaystyle d^{q}_{\pi_{w}}(s,a)$
$\displaystyle=\gamma\mathbb{E}[d^{q}_{\pi_{w}}(s^{\prime},a^{\prime})|s,a]$
$\displaystyle+\gamma\mathbb{E}[Q_{\pi_{w}}(s^{\prime},a^{\prime})\nabla_{w}\log\pi_{w}(a^{\prime}|s^{\prime})|s,a],$
(7)

We observe that eq. 7 takes a form analogous to the Bellman equation in eq. 1,
and thus suggests a recursive approach to estimate $d^{q}_{\pi_{w}}$,
similarly to temporal difference (TD) learning. Specifically, suppose we
estimate $d^{q}_{\pi_{w}}$ with a feature matrix
$x(s,a)\in\mathbb{R}^{d_{3}\times d}$, i.e.,
$\hat{d}^{q}_{\pi_{w}}(s,a)=x(s,a)^{\top}\theta_{d_{q}}$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$. Replace $Q_{\pi_{w}}(s,a)$ with its
estimator $\hat{Q}_{\pi_{w}}(s,a)=\phi(s,a)^{\top}\theta_{q}$ in eq. 7. The
temporal difference error is then given as

$\displaystyle\delta_{d_{q}}$ $\displaystyle(s,a,\theta_{q})=\gamma
x(s^{\prime},a^{\prime})^{\top}\theta_{d_{q}}$
$\displaystyle+\gamma\phi(s^{\prime},a^{\prime})^{\top}\theta_{q}\nabla_{w}\log\pi_{w}(a^{\prime}|s^{\prime})-x(s,a)^{\top}\theta_{d_{q}}$

and $\theta_{d^{q}}$ can be updated with the TD-like semi-gradient

$\displaystyle\theta_{d^{q},t+1}=\theta_{d^{q},t}+\beta_{2}x(s,a)\delta_{d^{q}}(s,a,\theta_{d^{q},t}).$
(8)

However, in the off-policy setting, the iteration in eq. 8 may not converge
due to the off-policy sampling. To solve such an issue, we borrow the idea
from gradient TD (GTD) and formulate the following strongly convex objective

$\displaystyle H(\theta_{d_{q}},\theta_{q})$
$\displaystyle=\mathbb{E}[x(s,a)\delta_{d_{q}}(s,a,\theta_{q})]^{\top}\mathbb{E}[x(s,a)\delta_{d_{q}}(s,a,\theta_{q})].$

We denote the global optimum of $H(\theta_{d_{q}},\theta^{*}_{q,w})$ as
$\theta^{*}_{d_{q},w}$, i.e., $H(\theta^{*}_{d_{q},w},\theta^{*}_{q,w})=0$.
The approximation error of estimating $d^{q}_{\pi_{w}}$ with estimator
$\hat{d}^{q}_{\pi_{w}}(s^{\prime},a^{\prime},\theta^{*}_{d_{q},w})=x(s,a)^{\top}\theta^{*}_{d_{q},w}$
is defined as

$\displaystyle\epsilon_{d_{q}}=\max\Big{\\{}\max_{w}\sqrt{\mathbb{E}_{\mathcal{D}}\left[\left\|\hat{d}^{q}_{\pi_{w}}(s,a,\theta^{*}_{d_{q},w})-{d}^{q}_{\pi_{w}}(s,a)\right\|_{2}^{2}\right]},$
$\displaystyle\max_{w}\sqrt{\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w}}\left[\left\|\hat{d}^{q}_{\pi_{w}}(s^{\prime},a^{\prime},\theta^{*}_{d_{q},w})-{d}^{q}_{\pi_{w}}(s^{\prime},a^{\prime})\right\|_{2}^{2}\right]}\Big{\\}}.$

Similarly to GTD, we introduce an auxiliary variable $w_{d^{q}}$ to avoid the
issue of double sampling when using gradient based approach to minimize
$H(\theta_{d_{q}},\theta_{q})$. With mini-batch samples
$\mathcal{B}_{t}=\\{(s_{i},a_{i},s^{\prime}_{i})\\}_{i=1\cdots
N}\sim\mathcal{D}_{d}$, we have the following update for $\theta_{d_{q}}$.

$\displaystyle\theta_{d_{q},t+1}$
$\displaystyle=\theta_{d_{q},t}+\beta_{3}\frac{1}{N}\sum_{i\in{\mathcal{B}}_{t}}(x_{i}-\gamma
x^{\prime}_{i})x^{\top}_{i}w_{d_{q},t},$ $\displaystyle w_{d_{q},t+1}$
$\displaystyle=w_{d_{q},t}+\beta_{3}\frac{1}{N}\sum_{i\in{\mathcal{B}}_{t}}(x_{i}\delta_{d_{q},i}(\theta_{q,t})-w_{d_{q},t}).$
(9)

Critic III: Derivative of density ratio $\hat{d}^{\rho}_{\pi_{w}}$. We denote
$\psi_{\pi_{w}}(s,a):=\nabla_{w}\log(\nu_{\pi_{w}}(s,a))$, and construct an
estimator for ${d}^{\rho}_{\pi_{w}}$ as
$\hat{d}^{\rho}_{\pi_{w}}(s,a)=\hat{\rho}_{\pi_{w}}(s,a)\hat{\psi}_{\pi_{w}}(s,a)$,
where $\hat{\rho}_{\pi_{w}}$ and $\hat{\psi}_{\pi_{w}}$ are approximation of
$\rho_{\pi_{w}}$ and $\psi_{\pi_{w}}$, respectively. Note that section 2 can
be rewritten in the following alternative form

$\displaystyle\nu_{\pi_{w}}(\tilde{s}^{\prime},a^{\prime})=\int\pi_{w}(a^{\prime}|\tilde{s}^{\prime})\tilde{\mathsf{P}}(\tilde{s}^{\prime}|s,a)\nu_{\pi_{w}}(s,a)dsda,$
(10)

where
$\tilde{\mathsf{P}}(\cdot|s,a)=(1-\gamma)\mu_{0}+\gamma\mathsf{P}(\cdot|s,a)$.
Taking derivative on both sides of eq. 10 and using $\nabla
g(w)=g(w)\nabla\log g(w)$, we obtain

$\displaystyle\textstyle\nu_{\pi_{w}}(\tilde{s}^{\prime},a^{\prime})\psi_{\pi_{w}}(\tilde{s}^{\prime},a^{\prime})$
$\displaystyle\textstyle=\nabla_{w}\log(\pi_{w}(a^{\prime}|\tilde{s}^{\prime}))\cdot\Big{[}\pi_{w}(a^{\prime}|\tilde{s}^{\prime})$
$\displaystyle\quad\int_{s,a}\tilde{\mathsf{P}}(\tilde{s}^{\prime}|s,a)\nu_{\pi_{w}}(s,a)dsda\Big{]}$
$\displaystyle\textstyle\quad+\int_{s,a}\Big{[}\pi_{w}(a^{\prime}|\tilde{s}^{\prime})\tilde{\mathsf{P}}(\tilde{s}^{\prime}|s,a)\nu_{\pi_{w}}(s,a)\Big{]}\psi_{\pi_{w}}(s,a)dsda$
$\displaystyle\textstyle=\nabla_{w}\log(\pi_{w}(a^{\prime}|\tilde{s}^{\prime}))\cdot\nu_{\pi_{w}}(\tilde{s}^{\prime},a^{\prime})$
$\displaystyle\textstyle\quad+\int_{s,a}\Big{[}\pi_{w}(a^{\prime}|\tilde{s}^{\prime})\tilde{\mathsf{P}}(\tilde{s}^{\prime}|s,a)\nu_{\pi_{w}}(s,a)\Big{]}\psi_{\pi_{w}}(s,a)dsda$
$\displaystyle\textstyle=\nabla_{w}\log(\pi_{w}(a^{\prime}|\tilde{s}^{\prime}))\cdot\nu_{\pi_{w}}(\tilde{s}^{\prime},a^{\prime})$
$\displaystyle\textstyle\quad+\int_{s,a}\nu_{\pi_{w}}(\tilde{s}^{\prime},a^{\prime})P\left(s,a|\tilde{s}^{\prime},a^{\prime}\right)\psi_{\pi_{w}}(s,a)dsda$

where the second equality follows because
${\pi_{w}(a^{\prime}|\tilde{s}^{\prime})\int_{s,a}\tilde{\mathsf{P}}(\tilde{s}^{\prime}|s,a)\nu_{\pi_{w}}(s,a)dsda}=\nu_{\pi_{w}}(\tilde{s}^{\prime},a^{\prime})$,
and the third equality follows because if $(s,a)\sim\nu_{\pi_{w}}(\cdot)$,
then $(\tilde{s}^{\prime},a^{\prime})\sim\nu_{\pi_{w}}(\cdot)$, and Bayes’
theorem implies that
$\frac{\pi_{w}(a^{\prime}|\tilde{s}^{\prime})\tilde{\mathsf{P}}(\tilde{s}^{\prime}|s,a)\nu_{\pi_{w}}(s,a)}{\nu_{\pi_{w}}(\tilde{s}^{\prime},a^{\prime})}=P\left(s,a|\tilde{s}^{\prime},a^{\prime}\right)$.
Then, dividing both sides by $\nu_{\pi_{w}}(\tilde{s}^{\prime},a^{\prime})$
yields

$\displaystyle\psi_{\pi_{w}}(\tilde{s}^{\prime},a^{\prime})$
$\displaystyle=\nabla_{w}\log(\pi_{w}(a^{\prime}|\tilde{s}^{\prime}))+\int_{s,a}P(s,a|\tilde{s}^{\prime},a^{\prime})\psi_{\pi_{w}}(s,a)dsda.$
(11)

With linear function approximation, we estimate $\psi_{\pi_{w}}(s,a)$ with
feature matrix $\varphi(s,a)\in\mathbb{R}^{d_{2}\times d}$ i.e.,
$\hat{\psi}_{\pi_{w}}(s,a)=\varphi(s,a)^{\top}\theta_{\psi}$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$. The temporal difference error is given
as

$\displaystyle\delta_{\psi}(\tilde{s}^{\prime},a^{\prime})$
$\displaystyle=\nabla_{w}\log\pi_{w}(a^{\prime}|\tilde{s}^{\prime})+\varphi(s,a)^{\top}\theta_{\psi}-\varphi(\tilde{s}^{\prime},a^{\prime})^{\top}\theta_{\psi},$
(12)

Note that in eq. 12, we require
$\tilde{s}^{\prime}\sim\tilde{\mathsf{P}}(\cdot|s,a)$. To obtain a sample
triple $(s,a,\tilde{s}^{\prime})$ from such a “hybrid” transition kernel, for
a given sample $(s,a,s^{\prime})$, we take a Bernoulli choice between
$s^{\prime}$ and $s_{0}\sim\mu_{0}$ with probability $\gamma$ and $1-\gamma$,
respectively, to obtain a state $\tilde{s}^{\prime}$ that satisfies the
requirement. Then, similarly to how we obtain the estimator
$\hat{d}^{q}_{\pi_{w}}$, we adopt the method in GTD to formulate the following
objective

$\displaystyle
F(\theta_{\psi})=\mathbb{E}[\varphi(s^{\prime},a^{\prime})\delta_{\psi}(\tilde{s}^{\prime},a^{\prime})]^{\top}\mathbb{E}[\varphi(s^{\prime},a^{\prime})\delta_{\rho}(\tilde{s}^{\prime},a^{\prime})].$
(13)

We denote the global optimum of $F(\theta_{\psi})$ as $\theta^{*}_{\psi,w}$,
i.e., $F(\theta^{*}_{\psi,w})=0$, and define the approximation error of
estimating $d^{\rho}_{\pi_{w}}$ with estimator
$\hat{d}^{\rho}_{\pi_{w}}(s,a,\theta^{*}_{\rho,w},\theta^{*}_{\psi,w})=\phi(s,a)^{\top}\theta^{*}_{\rho,w}\varphi(s,a)^{\top}\theta^{*}_{\psi,w}$
as

$\displaystyle\epsilon_{d_{\rho}}=\max_{w}\sqrt{\mathbb{E}_{\mathcal{D}}\left[\left\|\hat{d}^{\rho}_{\pi_{w}}(s,a,\theta^{*}_{\rho,w},\theta^{*}_{\psi,w})-{d}^{\rho}_{\pi_{w}}(s,a)\right\|_{2}^{2}\right]}.$

Given mini-batch samples
$\mathcal{B}_{t}=\\{(s_{i},a_{i},s^{\prime}_{i})\\}_{i=1\cdots
N}\sim\mathcal{D}_{d}$, $a^{\prime}_{i}\sim\pi_{w_{t}}(\cdot|s^{\prime}_{i})$
and $\mathcal{B}_{t,0}=\\{(s_{0,i},a_{0,i})\\}_{i=1\cdots N}\sim\mu_{0}$, we
have the following update for $\theta_{\psi}$:

$\displaystyle\theta_{\psi,t+1}$
$\displaystyle=\theta_{\psi,t}+\beta_{2}\frac{1}{N}\sum_{i\in\tilde{\mathcal{B}}_{t}}(\varphi^{\prime}_{i}-\varphi_{i})\varphi^{\prime\top}_{i}w_{\psi,t},$
$\displaystyle w_{\psi,t+1}$
$\displaystyle=w_{\psi,t}+\beta_{2}\frac{1}{N}\sum_{i\in\tilde{\mathcal{B}}_{t}}(\varphi^{\prime}_{i}\delta_{\psi,i}-w_{\psi,t}),$
(14)

where $w_{\psi,t}$ is the auxiliary variable that we introduce to avoid the
double sampling issue.

DR-Off-PAC Estimator. Given parameters $\theta_{\rho,t}$, $\theta_{q,t}$,
$\theta_{\psi,t}$ and $\theta_{d_{q},t}$, the doubly robust policy gradient
can be obtained as follows

$\displaystyle\quad G^{i}_{\text{DR}}(w_{t})$
$\displaystyle=(1-\gamma)\left(\phi_{0,i}^{\top}\theta_{q,t}\nabla_{w}\log\pi_{w}(s_{0,i},a_{0,i})+x_{0,i}^{\top}\theta_{d_{q},t}\right)$
$\displaystyle+\psi_{i}^{\top}\theta_{\psi,t}(r(s_{i},a_{i},s^{\prime}_{i})-\phi_{i}^{\top}\theta_{q,t}+\gamma\mathbb{E}_{\pi_{w_{t}}}[\phi^{\prime\top}_{i}\theta_{q,t}])$
$\displaystyle+\phi_{i}^{\top}\theta_{\rho,t}(-x_{i}^{\top}\theta_{d_{q},t}$
$\displaystyle\qquad\quad+\gamma\phi_{i}^{\top}\theta_{q,t}\nabla_{w}\log\pi_{w}(s_{t,i},a_{t,i})+x_{i}^{\top}\theta_{d_{q},t}).$
(15)

Algorithm 1 DR-Off-PAC

Initialize: Policy parameter $w_{0}$, and estimator parameters $\theta_{q,0}$,
$\theta_{\rho,0}$, $\theta_{d_{q},0}$ and $\theta_{\psi,0}$.

for $t=0,\cdots,T-1$ do

Obtain mini-batch samples $\mathcal{B}_{t}\sim\mathcal{D}_{d}$ and
$\mathcal{B}_{t,0}\sim\mu_{0}$

Critic I: Update density ratio and value function estimation via eq. 6:
$\theta_{q,t},\theta_{\rho,t}\rightarrow\theta_{q,t+1},\theta_{\rho,t+1}$

Critic II: Update derivative of value function estimation via eq. 9:
$\theta_{d_{q},t}\rightarrow\theta_{d_{q},t+1}$

Critic III: Update derivative of density ratio estimation via eq. 14:
$\theta_{\psi,t}\rightarrow\theta_{\psi,t+1}$

Actor: Update policy parameter via eq. 15

$w_{t+1}=w_{t}+\alpha\frac{1}{N}\sum_{i}G^{i}_{\text{DR}}(w_{t})$

end for

Output: $w_{\hat{T}}$ with $\hat{T}$ chosen uniformly in $\\{0,\cdots,T-1\\}$

DR-Off-PAC Algorithm. We now propose a doubly robust off-policy actor-critic
(DR-Off-PAC) algorithm as detailed in Algorithm 1. The stepsizes $\beta_{1}$,
$\beta_{2}$, $\beta_{3}$, and $\alpha$ are set to be $\Theta(1)$ to yield a
single-timescale update, i.e., all parameters are updated equally fast. At
each iteration, critics I, II, and III perform one-step update respectively
for parameters $\theta_{q}$, $\theta_{\rho}$, $\theta_{\psi}$, and
$\theta_{d_{q}}$, and then actor performs one-step policy update based on all
critics’ return. Note that Algorithm 1 is inherently a tri-level optimization
process, as the update of $w$ depends on $\theta_{\rho}$, $\theta_{q}$,
$\theta_{\psi}$, and $\theta_{d_{q}}$, in which the update of $\theta_{d_{q}}$
depends on $\theta_{q}$. Thus the interactions between actor and critics and
between critic and critic are more complicated than previous actor-critic
algorithms that solve bilevel problems (Konda & Tsitsiklis, 2000; Bhatnagar,
2010; Xu et al., 2020b). Due to the single timescale scheme that Algorithm 1
adopts, actor’s update is based on inexact estimations of critics, which can
significantly affect the overall convergence of the algorithm. Interestingly,
as we will show in the next section, Algorithm 1 is guaranteed to converge to
the optimal policy, and at the same time attains doubly robust optimality gap
with respect to approximation errors.

##  4 Convergence Analysis of DR-Off-PAC

In this section, we establish the local and global convergence rate for DR-
Off-PAC in the single-timescale update setting.

###  4.1 Local Convergence

We first state a few standard technical assumptions, which have also been
adopted in previous studies (Xu et al., 2020b, 2019; Zhang et al., 2020a, b;
Wu et al., 2020)

######  Assumption 1.

For any $(s,a)\in\mathcal{S}\times\mathcal{A}$ and $w\in\mathbb{R}^{d}$, there
exists a constant $C_{d}>0$ such that $\rho_{\pi_{w}}(s,a)>C_{d}$.

######  Assumption 2.

For any $(s,a)\in\mathcal{S}\times\mathcal{A}$, there exist positive constants
$C_{\phi}$, $C_{\varphi}$, $C_{\psi}$, and $C_{x}$ such that the following
hold: (1) $\left\|\phi(s,a)\right\|_{2}\leq C_{\phi}$; (2)
$\left\|\varphi(s,a)\right\|_{2}\leq C_{\varphi}$; (3)
$\left\|\psi(s,a)\right\|_{2}\leq C_{\psi}$; (4)
$\left\|x(s,a)\right\|_{2}\leq C_{x}$.

######  Assumption 3.

The matrices
$A=\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w}}[(\phi-\gamma\phi^{\prime})\phi^{\top}]$,
$B=\mathbb{E}_{\tilde{\mathcal{D}}_{d}\cdot\pi_{w}}[(\varphi-\varphi^{\prime})\varphi^{\prime\top}]$
and $C=\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w}}[(\gamma
x^{\prime}-x)x^{\top}]$ are nonsingular.

######  Assumption 4.

For any $w,w^{\prime}\in\mathbb{R}^{d}$ and any
$(s,a)\in\mathcal{S}\times\mathcal{A}$, there exist positive constants
$C_{sc}$, $L_{sc}$, and $L_{\pi}$ such that the following hold: (1)
$\left\|\nabla_{w}\log\pi_{w}(a|s)\right\|_{2}\leq C_{sc}$; (2)
$\left\|\nabla_{w}\log\pi_{w}(a|s)-\nabla_{w}\log\pi_{w^{\prime}}(a|s)\right\|_{2}\leq
L_{sc}\left\|w-w^{\prime}\right\|_{2}$; (3)
$\left\|\pi_{w}(\cdot|s)-\pi_{w^{\prime}}(\cdot|s)\right\|_{TV}\leq
L_{\pi}\left\|w-w^{\prime}\right\|_{2}$, where $\left\|\cdot\right\|_{TV}$
denotes the total-variation norm.

The following theorem characterizes the convergence rate of Algorithm 1, as
well as its doubly robust optimality gap.

######  Theorem 2 (Local convergence).

Consider the DR-Off-PAC in Algorithm 1. Suppose 1 \- 4 hold. Let the stepsize
$\alpha,\beta_{1},\beta_{2},\beta_{3}=\Theta(1)$. We have

$\displaystyle\mathbb{E}[\left\|\nabla_{w}J(w_{\hat{T}})\right\|_{2}]$
$\displaystyle\leq\Theta\left(\frac{1}{\sqrt{T}}\right)+\Theta\left(\frac{1}{\sqrt{N}}\right)+\Theta(\epsilon_{\rho}\epsilon_{d_{q}}+\epsilon_{d_{\rho}}\epsilon_{q}+\epsilon_{\rho}\epsilon_{q}).$

Theorem 2 shows that Algorithm 1 is guaranteed to converge to a first-order
stationary point (i.e., locally optimal policy). In particular, the optimality
gap (i.e., the overall convergence error) scales as
$(\epsilon_{\rho}\epsilon_{d_{q}}+\epsilon_{d_{\rho}}\epsilon_{q}+\epsilon_{\rho}\epsilon_{q})$.
Thus, the optimality gap of Algorithm 1 is 3-way doubly robust with respect to
the function approximation errors, i.e., the optimality gap is small as long
as one of the three pairs $(\epsilon_{\rho},\epsilon_{q})$,
$(\epsilon_{\rho},\epsilon_{d_{\rho}})$, $(\epsilon_{q},\epsilon_{d_{q}})$ is
small.

There are two key differences between the doubly robust properties
characterized in Theorem 2 and Theorem 1. (a) At the high level, Theorem 1
characterizes the doubly robust property only for the policy gradient
estimator, and such a property has been characterized in the previous work for
other estimators. In contrast, Theorem 2 characterizes the doubly robust
property for the optimality gap of the overall convergence of an algorithm,
which has not been characterized in any of the previous studies. (b) At the
more technical level, the estimation error $\varepsilon$ defined in Theorem 1
captures both the optimization error $\epsilon_{opt}$ determined by how well
we solve the nuisances estimation problem, and the approximation error
$\epsilon_{approx}$ determined by the representation power of approximation
function classes. Thus, Theorem 1 shows that $G_{\text{DR}}(w)$ is doubly
robust to the per-iteration estimation errors that depend on both the
optimization process and the approximation function class. As a comparison,
Theorem 2 indicates that the optimality gap of DR-Off-PAC is doubly robust
only to approximation errors determined by the approximation function class,
which implies that the doubly robust property of the overall convergence of
DR-Off-PAC is not affected by the optimization process.

Now in order to attain an optimization target accuracy $\epsilon$ (besides the
doubly robust optimality gap), we let $T=\Theta(1/\epsilon^{2})$ and
$B=\Theta(1/\epsilon^{2})$. Then Theorem 2 indicates that Algorithm 1
converges to an $\epsilon$-accurate stationary point with the total sample
complexity $NT=\Theta(1/\epsilon^{4})$. This result outperforms the best known
sample complexity of on-policy actor-critic algorithm by an factor of
$\mathcal{O}(\log(1/\epsilon))$ in (Xu et al., 2020b). Such an improvement is
mainly due to the single-loop structure that we adopt in Algorithm 1, in which
critics inherit the most recently output from the last iteration as actor
updates in order to be more sample efficient. But critic in the nested-loop
algorithm in (Xu et al., 2020b) always restarts from an random initialization
after each actor’s update, which yields more sample cost.

###  4.2 Global Convergence

In this subsection, we establish the global convergence guarantee for DR-Off-
PAC in Algorithm 1. We first make the following standard assumption on the
Fisher information matrix induced by the policy class $\pi_{w}$.

######  Assumption 5.

For all $w\in\mathbb{R}^{d}$, the Fisher information matrix induced by policy
$\pi_{w}$ and initial state distribution $\mu_{0}$ satisfies

$\displaystyle
F(w)=\mathbb{E}_{\nu_{\pi_{w}}}[\nabla_{w}\log\pi_{w}(a|s)\nabla_{w}\log\pi_{w}(a|s)^{\top}]\succeq\lambda_{F}\cdot
I_{d},$

for some constant $\lambda_{F}>0$.

5 essentially states that $F(w)$ is well-conditioned. This assumption can be
satisfied by some commonly used policy classes. More detailed justification of
such an assumption can be referred to Appendix B.2 in (Liu et al., 2020).

We further define the following compatible function approximation error as

$\displaystyle\epsilon_{compat}$
$\displaystyle=\max_{w\in\mathbb{R}^{d}}\sqrt{\mathbb{E}_{\nu_{\pi^{*}}}\left[(A_{\pi_{w}}(s,a)-(1-\gamma)\chi^{*\top}_{\pi_{w}}\nabla_{w}\log\pi_{w}(a|s))^{2}\right]},$

where $A_{\pi_{w}}(s,a)=Q_{\pi_{w}}(s,a)-V_{\pi_{w}}(s)$ is the advantage
function and $\chi^{*\top}_{\pi_{w}}=F(w)^{-1}\nabla_{w}J(w)$. Such an error
$\epsilon_{compat}$ captures the approximating error of the advantage function
by the score function. It measures the capacity of the policy class $\pi_{w}$,
and takes small or zero values if the expressive power of the policy class is
large (Wang et al., 2019; Agarwal et al., 2019).

The following theorem establishes the global convergence guarantee for
Algorithm 1.

######  Theorem 3 (Global convergence).

Consider the DR-Off-PAC update in Algorithm 1. Suppose 1, 2, 3 and 5 hold. For
the same parameter setting as in Theorem 2, we have

$\displaystyle J(\pi^{*})-J(w_{\hat{T}})$
$\displaystyle\leq\frac{\epsilon_{compat}}{1-\gamma}+\Theta\left(\frac{1}{\sqrt{T}}\right)+\Theta\left(\frac{1}{\sqrt{N}}\right)$
$\displaystyle\quad+\Theta(\epsilon_{\rho}\epsilon_{d_{q}}+\epsilon_{d_{\rho}}\epsilon_{q}+\epsilon_{\rho}\epsilon_{q})$

Theorem 3 shows that Algorithm 1 is guaranteed to converge to the global
optimum at a sublinear rate, and the optimality gap is bounded by
$\Theta(\epsilon_{compat})+\Theta(\epsilon_{\rho}\epsilon_{d_{q}}+\epsilon_{d_{\rho}}\epsilon_{q}+\epsilon_{\rho}\epsilon_{q})$.
Note that the error term $\Theta(\epsilon_{compat})$ is introduced by the
parametrization of policy and thus exists even for exact policy gradient
algorithm (Liu et al., 2020; Wang et al., 2019). The global convergence of DR-
Off-PAC in Theorem 3 also enjoys doubly robust optimality gap as in Theorem 2.
By letting $T=\Theta(1/\epsilon^{2})$ and $N=\Theta(1/\epsilon^{2})$,
Algorithm 1 converges to an $\epsilon$-level global optimum (besides the
approximation errors) with a total sample complexity
$NT=\Theta(1/\epsilon^{4})$. This result matches the global convergence rate
of single-loop actor-critic in (Xu et al., 2020c; Fu et al., 2020).

##  5 Experiments

We conduct empirical experiments to answer the following two questions: (a)
does the overall convergence of DR-Off-PAC doubly robust to function
approximation errors as Theorem 2 & 3 indicate? (2) how does DR-Off-PAC
compare with other off-policy methods?

Figure 1: A variant of Baird’s counterexample.

We consider a variant of Baird’s counterexample (Baird, 1995; Sutton & Barto,
2018) as shown in Figure 1. There are two actions represented by solid line
and dash line, respectively. The solid action always leads to state 7 and a
reward $0$, and the dash action leads to states 1-6 with equal probability and
a reward $+1$. The initial distribution $\mu_{0}$ chooses all states $s$ with
equal probability $\frac{1}{7}$ and the behavior distribution chooses all
state-action pairs $(s,a)$ with equal probability $\frac{1}{14}$. We consider
two types of one-hot features for estimating the nuisances: complete feature
(CFT) and incomplete feature (INCFT), where CFT for each $(s,a)$ lies in
$\mathbb{R}^{14}$ and INCFT for each $(s,a)$ lies in $\mathbb{R}^{d}$ with
$(d<14)$. Note that CFT has large enough expressive power so that the
approximation error is zero, while INCFT does not have enough expressive
power, and thus introduces non-vanishing approximation errors. In our
experiments, we consider fixed learning rates $0.1$, $0.5$, $0.1$, $0.05$,
$0.01$ for updating $w$, $\theta_{q}$, $\theta_{\psi}$, $\theta_{dq}$, and
$\theta_{d\rho}$, respectively, and we set the mini-batch size as $N=5$. All
curves are averaged over 20 independent runs.

Doubly Robust Optimality Gap: We first investigate how the function
approximation error affects the optimality gap of the overall convergence of
DR-Off-PAC. In this experiment, we set the dimension of INCFTs as $0$, which
results in trivial critics that always provide constant estimations.

Figure 2: DR-Off-PAC under difference feature settings.

We consider the following four feature settings for critics to estimate the
nuisance functions $(Q,\rho,d^{q},d^{\rho})$: (I) all nuisances with CFTs.
(II) $(Q,\rho)$ with CFTs and $(d^{\rho},d^{q})$ with INCFTs; (III)
$(Q,d^{q})$ with CFTs and $(\rho,d^{\rho})$ with INCFTs; (IV)
$(\rho,d^{\rho})$ with CFTs and $(Q,d^{q})$ with INCFTs. The results are
provided in Figure 2. We can see that DR-Off-PAC with all nuisances estimated
by CFTs (red line) enjoys the fastest convergence speed and smallest
optimality gap, and DR-Off-PAC with only two nuisances estimated with CFTs can
still converge to the same optimal policy as the red line, validating the
doubly robust optimality gap in the overall convergence characterized by
Theorem 2 and Theorem 3.

Comparison to AC-DC: As we have mentioned before, previous provably convergent
off-policy actor-critic algorithms introduce an additional critic to correct
the distribution mismatch (Liu et al., 2019; Zhang et al., 2019c). Such a
strategy can be viewed as a special case of DR-Off-PAC when both
$\theta_{{d}^{q}}$ and $\theta_{\psi}$ equal zero. Here we call such a type of
algorithms as actor-critic with distribution correction (AC-DC). In this
experiment, we set the dimension of INCFTs as 4 and compare the convergence of
DR-Off-AC and AC-DC in the settings considered in our previous experiment.

Figure 3: Comparison between DR-Off-PAC and AC-DC.

The learning curves of DR-Off-PAC and AC-DC are reported in Figure 3. We can
see that the overall convergence of DR-Off-PAC (each solid line) outperforms
that of AC-DC (dash line with the same color) for all feature settings (where
each color corresponds to one feature setting). Specifically, In (III) or
(IV), when either $Q$ or $\rho$ is estimated with incomplete features, the
performance of AC-DC is significantly impeded by the approximation error and
thus has lower accuracy, whereas DR-Off-PAC has better convergence performance
by mitigating the effect of such approximation errors via the doubly robust
property. Interestingly, even in the settings where both $Q$ and $\rho$ are
estimated with complete features ($S_{1}$ and $S_{2}$) so that AC-DC is
expected to achieve zero optimality gap, our DR-Off-PAC still converges faster
and more accurately than AC-DC, demonstrating that DR-Off-PAC can improve the
convergence of AC-DC even when both $\rho$ and $Q$ are estimated with a
complete approximation function class.

##  6 Conclusion

In this paper, we first develop a new doubly robust policy gradient estimator
for an infinite-horizon discounted MDP, and propose new methods to estimate
the nuisances in the off-policy setting. Based on such an estimator, we
propose a doubly robust off-policy algorithm called DR-Off-PAC for solving the
policy optimization problem. We further study the finite-time convergence of
DR-Off-PAC under the single timescale update setting. We show that DR-Off-PAC
provably converges to the optimal policy, with the optimality gap being doubly
robust to approximation errors that depend only on the expressive power of
function classes. For future work, it is interesting to incorporate variance
reduction technique (Xu et al., 2020a; Cutkosky & Orabona, 2019) to DR-Off-PAC
to improve its convergence performance.

## Acknowledgements

The work of T. Xu and Y. Liang was supported in part by the U.S. National
Science Foundation under the grants CCF-1761506 and CCF-1900145. Z. Wang
acknowledges National Science Foundation (Awards 2048075, 2008827, 2015568,
1934931), Simons Institute (Theory of Reinforcement Learning), Amazon, J.P.
Morgan, and Two Sigma for their supports. Z. Yang acknowledges Simons
Institute (Theory of Reinforcement Learning).

## References

  * Agarwal et al. (2019) Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G.  Optimality and approximation with policy gradient methods in Markov decision processes.  _arXiv preprint arXiv:1908.00261_ , 2019.
  * Baird (1995) Baird, L.  Residual algorithms: reinforcement learning with function approximation.  In _Machine Learning Proceedings_ , pp. 30–37. 1995.
  * Bhatnagar (2010) Bhatnagar, S.  An actor–critic algorithm with function approximation for discounted cost constrained Markov decision processes.  _Systems & Control Letters_, 59(12):760–766, 2010.
  * Bhatnagar et al. (2009) Bhatnagar, S., Sutton, R. S., Ghavamzadeh, M., and Lee, M.  Natural actor–critic algorithms.  _Automatica_ , 45(11):2471–2482, 2009.
  * Cutkosky & Orabona (2019) Cutkosky, A. and Orabona, F.  Momentum-based variance reduction in non-convex SGD.  In _Proc. Advances in Neural Information Processing Systems (NeurIPS)_ , pp. 15236–15245, 2019.
  * Dai et al. (2018) Dai, B., Shaw, A., Li, L., Xiao, L., He, N., Liu, Z., Chen, J., and Song, L.  SBEED: convergent reinforcement learning with nonlinear function approximation.  In _Proc. International Conference on Machine Learning (ICML)_ , pp. 1125–1134, 2018.
  * Degris et al. (2012) Degris, T., White, M., and Sutton, R. S.  Off-policy actor-critic.  In _Proc. International Conference on Machine Learning (ICML)_ , pp. 179–186, 2012.
  * Dudík et al. (2011) Dudík, M., Langford, J., and Li, L.  Doubly robust policy evaluation and learning.  In _Proc. International Conference on Machine Learning (ICML)_ , pp. 1097–1104, 2011.
  * Dudík et al. (2014) Dudík, M., Erhan, D., Langford, J., Li, L., et al.  Doubly robust policy evaluation and optimization.  _Statistical Science_ , 29(4):485–511, 2014.
  * Fu et al. (2020) Fu, Z., Yang, Z., and Wang, Z.  Single-timescale actor-critic provably finds globally optimal policy.  _arXiv preprint arXiv:2008.00483_ , 2020.
  * Fujimoto et al. (2018) Fujimoto, S., Hoof, H., and Meger, D.  Addressing function approximation error in actor-critic methods.  In _Proc. International Conference on Machine Learning (ICML)_ , pp. 1587–1596, 2018.
  * Gelada & Bellemare (2019) Gelada, C. and Bellemare, M. G.  Off-policy deep reinforcement learning by bootstrapping the covariate shift.  In _Proc. AAAI Conference on Artificial Intelligence (AAAI)_ , volume 33, pp. 3647–3655, 2019.
  * Gottesman et al. (2019) Gottesman, O., Johansson, F., Komorowski, M., Faisal, A., Sontag, D., Doshi-Velez, F., and Celi, L. A.  Guidelines for reinforcement learning in healthcare.  _Nature medicine_ , 25(1):16–18, 2019.
  * Haarnoja et al. (2017) Haarnoja, T., Tang, H., Abbeel, P., and Levine, S.  Reinforcement learning with deep energy-based policies.  In _Proc. International Conference on Machine Learning (ICML)_ , pp. 1352–1361, 2017.
  * Haarnoja et al. (2018) Haarnoja, T., Zhou, A., Abbeel, P., and Levine, S.  Soft actor-critic: off-policy maximum entropy deep reinforcement learning with a stochastic actor.  In _Proc. International Conference on Machine Learning (ICML)_ , pp. 1861–1870, 2018.
  * Houthooft et al. (2018) Houthooft, R., Chen, Y., Isola, P., Stadie, B., Wolski, F., Ho, O. J., and Abbeel, P.  Evolved policy gradients.  In _Proc. Advances in Neural Information Processing Systems (NeurIPS)_ , pp. 5400–5409, 2018.
  * Huang & Jiang (2020) Huang, J. and Jiang, N.  From importance sampling to doubly robust policy gradient.  In _Proc. International Conference on Machine Learning (ICML)_ , pp. 4434–4443, 2020.
  * Imani et al. (2018) Imani, E., Graves, E., and White, M.  An off-policy policy gradient theorem using emphatic weightings.  In _Proc. Advances in Neural Information Processing Systems (NeurIPS)_ , pp. 96–106, 2018.
  * Jiang & Li (2016) Jiang, N. and Li, L.  Doubly robust off-policy value evaluation for reinforcement learning.  In _Proc. International Conference on Machine Learning (ICML)_ , pp. 652–661, 2016.
  * Kallus & Uehara (2020) Kallus, N. and Uehara, M.  Statistically efficient off-policy policy gradients.  _arXiv preprint arXiv:2002.04014_ , 2020.
  * Konda & Tsitsiklis (2000) Konda, V. R. and Tsitsiklis, J. N.  Actor-critic algorithms.  In _Proc. Advances in Neural Information Processing Systems (NeurIPS)_ , pp. 1008–1014, 2000.
  * Lillicrap et al. (2016) Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D.  Continuous control with deep reinforcement learning.  In _Proc. International Conference on Learning Representations (ICLR)_ , 2016.
  * Liu et al. (2018) Liu, Q., Li, L., Tang, Z., and Zhou, D.  Breaking the curse of horizon: Infinite-horizon off-policy estimation.  In _Proc. Advances in Neural Information Processing Systems (NeurIPS)_ , pp. 5356–5366, 2018.
  * Liu et al. (2019) Liu, Y., Swaminathan, A., Agarwal, A., and Brunskill, E.  Off-policy policy gradient with state distribution correction.  In _Proc. International Conference on Learning Representations (ICLR)_ , 2019.
  * Liu et al. (2020) Liu, Y., Zhang, K., Basar, T., and Yin, W.  An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods.  _In Proc. Advances in Neural Information Processing Systems (NeurIPS)_ , 33, 2020.
  * Lyu et al. (2020) Lyu, D., Qi, Q., Ghavamzadeh, M., Yao, H., Yang, T., and Liu, B.  Variance-reduced off-policy memory-efficient policy search.  _arXiv preprint arXiv:2009.06548_ , 2020.
  * Maei (2011) Maei, H. R.  _Gradient temporal-difference learning algorithms_.  PhD thesis, University of Alberta, 2011.
  * Maei (2018) Maei, H. R.  Convergent actor-critic algorithms under off-policy training and function approximation.  _arXiv preprint arXiv:1802.07842_ , 2018.
  * Meuleau et al. (2001) Meuleau, N., Peshkin, L., and Kim, K.-E.  Exploration in gradient-based reinforcement learning.  2001\.
  * Mnih et al. (2016) Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap, T., Harley, T., Silver, D., and Kavukcuoglu, K.  Asynchronous methods for deep reinforcement learning.  In _Proc. International Conference on Machine Learning (ICML)_ , pp. 1928–1937, 2016.
  * Morimura et al. (2010) Morimura, T., Uchibe, E., Yoshimoto, J., Peters, J., and Doya, K.  Derivatives of logarithmic stationary distributions for policy gradient reinforcement learning.  _Neural computation_ , 22(2):342–376, 2010.
  * Nachum et al. (2017) Nachum, O., Norouzi, M., Xu, K., and Schuurmans, D.  Bridging the gap between value and policy based reinforcement learning.  In _Proc. Advances in Neural Information Processing Systems (NeurIPS)_ , pp. 2775–2785, 2017.
  * Nachum et al. (2018) Nachum, O., Norouzi, M., Xu, K., and Schuurmans, D.  Trust-PCL: An off-policy trust region method for continuous control.  In _Proc. International Conference on Learning Representations (ICLR)_ , 2018.
  * Nachum et al. (2019) Nachum, O., Dai, B., Kostrikov, I., Chow, Y., Li, L., and Schuurmans, D.  Algaedice: policy gradient from arbitrary experience.  _arXiv preprint arXiv:1912.02074_ , 2019.
  * O’Donoghue et al. (2016) O’Donoghue, B., Munos, R., Kavukcuoglu, K., and Mnih, V.  Combining policy gradient and q-learning.  In _Proc. International Conference on Learning Representations (ICLR)_ , 2016.
  * Schulman et al. (2017) Schulman, J., Chen, X., and Abbeel, P.  Equivalence between policy gradients and soft q-learning.  _arXiv preprint arXiv:1704.06440_ , 2017.
  * Silver et al. (2014) Silver, D., Lever, G., Heess, N., Degris, T., Wierstra, D., and Riedmiller, M.  Deterministic policy gradient algorithms.  In _Proc. International Conference on Machine Learning (ICML)_ , pp. 387–395, 2014.
  * Silver et al. (2016) Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al.  Mastering the game of Go with deep neural networks and tree search.  _nature_ , 529(7587):484–489, 2016.
  * Sutton & Barto (2018) Sutton, R. S. and Barto, A. G.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Sutton et al. (2000) Sutton, R. S., McAllester, D. A., Singh, S. P., and Mansour, Y.  Policy gradient methods for reinforcement learning with function approximation.  In _Proc. Advances in Neural Information Processing Systems (NeurIPS)_ , pp. 1057–1063, 2000.
  * Sutton et al. (2016) Sutton, R. S., Mahmood, A. R., and White, M.  An emphatic approach to the problem of off-policy temporal-difference learning.  _The Journal of Machine Learning Research_ , 17(1):2603–2631, 2016.
  * Tang et al. (2019) Tang, Z., Feng, Y., Li, L., Zhou, D., and Liu, Q.  Doubly robust bias reduction in infinite horizon off-policy estimation.  _arXiv preprint arXiv:1910.07186_ , 2019.
  * Tosatto et al. (2020) Tosatto, S., Carvalho, J., Abdulsamad, H., and Peters, J.  A nonparametric off-policy policy gradient.  In _Proc. International Conference on Artificial Intelligence and Statistics_ , pp. 167–177. PMLR, 2020.
  * Wang et al. (2019) Wang, L., Cai, Q., Yang, Z., and Wang, Z.  Neural policy gradient methods: Global optimality and rates of convergence.  _arXiv preprint arXiv:1909.01150_ , 2019.
  * Wang et al. (2016) Wang, Z., Bapst, V., Heess, N., Mnih, V., Munos, R., Kavukcuoglu, K., and de Freitas, N.  Sample efficient actor-critic with experience replay.  In _Proc. International Conference on Learning Representations (ICLR)_ , 2016.
  * Wu et al. (2020) Wu, Y., Zhang, W., Xu, P., and Gu, Q.  A finite time analysis of two time-scale actor critic methods.  _arXiv preprint arXiv:2005.01350_ , 2020.
  * Xiong et al. (2020) Xiong, H., Xu, T., Liang, Y., and Zhang, W.  Non-asymptotic convergence of Adam-type reinforcement learning algorithms under Markovian sampling.  _arXiv preprint arXiv:2002.06286_ , 2020.
  * Xu et al. (2020a) Xu, P. T., Wang, Z., Zhou, Y., and Liang, Y.  Reanalysis of variance reduced temporal difference learning.  In _Proc. International Conference on Learning Representations (ICLR)_ , 2020a.
  * Xu et al. (2019) Xu, T., Zou, S., and Liang, Y.  Two time-scale off-policy TD learning: Non-asymptotic analysis over markovian samples.  In _Proc. Advances in Neural Information Processing Systems (NeurIPS)_ , pp. 10633–10643, 2019.
  * Xu et al. (2020b) Xu, T., Wang, Z., and Liang, Y.  Improving sample complexity bounds for (natural) actor-critic algorithms.  _In Proc. Advances in Neural Information Processing Systems (NeurIPS)_ , 33, 2020b.
  * Xu et al. (2020c) Xu, T., Wang, Z., and Liang, Y.  Non-asymptotic convergence analysis of two time-scale (natural) actor-critic algorithms.  _arXiv preprint arXiv:2005.03557_ , 2020c.
  * Yang et al. (2020) Yang, M., Nachum, O., Dai, B., Li, L., and Schuurmans, D.  Off-policy evaluation via the regularized lagrangian.  _arXiv preprint arXiv:2007.03438_ , 2020.
  * Zhang et al. (2019a) Zhang, K., Koppel, A., Zhu, H., and Başar, T.  Global convergence of policy gradient methods to (almost) locally optimal policies.  _arXiv preprint arXiv:1906.08383_ , 2019a.
  * Zhang et al. (2020a) Zhang, R., Dai, B., Li, L., and Schuurmans, D.  Gendice: generalized offline estimation of stationary values.  _arXiv preprint arXiv:2002.09072_ , 2020a.
  * Zhang et al. (2019b) Zhang, S., Boehmer, W., and Whiteson, S.  Generalized off-policy actor-critic.  In _Proc. Advances in Neural Information Processing Systems (NeurIPS)_ , pp. 2001–2011, 2019b.
  * Zhang et al. (2019c) Zhang, S., Liu, B., Yao, H., and Whiteson, S.  Provably convergent off-policy actor-critic with function approximation.  _arXiv preprint arXiv:1911.04384_ , 2019c.
  * Zhang et al. (2020b) Zhang, S., Liu, B., and Whiteson, S.  GradientDICE: rethinking generalized offline estimation of stationary values.  In _Proc. International Conference on Machine Learning (ICML)_ , pp. 11194–11203, 2020b.

Supplementary Materials

##  Appendix A Derivation of Doubly Robust Policy Gradient Estimator

In this section, we introduce how to derive the doubly robust policy gradient
$G_{\text{DR}}(w)$ in eq. 4

Consider the setting of off-policy sampling specified in Section 2. Note that
$J(w)$ has the following alternative form:

$\displaystyle J(w)=$
$\displaystyle(1-\gamma)\mathbb{E}_{\mu_{0}}\big{[}V_{\pi_{w}}(s_{0})\big{]}+\mathbb{E}_{d}\big{[}\rho_{\pi_{w}}(s,a)(r(s,a,s^{\prime})-Q_{\pi_{w}}(s,a)+\gamma\mathbb{E}\big{[}V_{\pi_{w}}(s^{\prime})|s,a\big{]})\big{]},$
(16)

where $\rho_{\pi_{w}}(s,a)=\nu_{\pi_{w}}(s,a)/d(s,a)$ denotes the distribution
correction ratio. With a sample
$(s,a,r,s^{\prime},a^{\prime})\sim\mathcal{D}_{d}\cdot\pi_{w}(\cdot)$ and a
sample $(s_{0},a_{0})\sim\mu_{0}\cdot\pi_{w}(\cdot)$, we can formulate the
following stochastic estimator of $J(w)$:

$\displaystyle\hat{J}(w)=\underbrace{(1-\gamma)V_{\pi_{w}}(s_{0})}_{\text{unbiased
estimator}}+\underbrace{\rho_{\pi_{w}}(s,a)(r(s,a,s^{\prime})-Q_{\pi_{w}}(s,a)+\gamma
V_{\pi_{w}}(s^{\prime}))}_{\text{baseline}}.$ (17)

Note that the first term in eq. 17 is an unbiased estimator of $J(w)$ and the
second term in eq. 17 is the baseline that can help to reduce the variance
(Jiang & Li, 2016; Huang & Jiang, 2020). Note that if we replace the value
functions $V_{\pi_{w}}$, $Q_{\pi_{w}}$ and the density ratio $\rho_{\pi_{w}}$
with their estimators $\hat{V}_{\pi_{w}}$ $\hat{Q}_{\pi_{w}}$, and
$\hat{\rho}_{\pi_{w}}$, respectively, we can obtain a doubly robust bias
reduced value function estimator (Tang et al., 2019). Next, we take the
derivative of $\hat{J}(w)$ to obtain an unbiased estimator of $\nabla{J}(w)$
which takes the following form:

$\displaystyle\nabla_{w}\hat{J}(w)$
$\displaystyle=(1-\gamma)d^{v}_{\pi_{w}}(s_{0})+d^{\rho}_{\pi_{w}}(s,a)(r(s,a,s^{\prime})-Q_{\pi_{w}}(s,a)+\gamma
V_{\pi_{w}}(s^{\prime}))$
$\displaystyle\quad+\rho_{\pi_{w}}(s,a)(-d^{q}_{\pi_{w}}(s,a)+\gamma
d^{v}_{\pi_{w}}(s^{\prime}))$
$\displaystyle=(1-\gamma)\mathbb{E}_{\pi_{w}}[{Q}_{\pi_{w}}(s_{0},a_{0})\nabla_{w}\log\pi_{w}(s_{0},a_{0})+{d}^{q}_{\pi_{w}}(s_{0},a_{0})]$
$\displaystyle\quad+d^{\rho}_{\pi_{w}}(s,a)(r(s,a,s^{\prime})-Q_{\pi_{w}}(s,a)+\gamma\mathbb{E}_{\pi_{w}}[Q_{\pi_{w}}(s^{\prime},a^{\prime})])$
$\displaystyle\quad+\rho_{\pi_{w}}(s,a)(-d^{q}_{\pi_{w}}(s,a)+\gamma\mathbb{E}_{\pi_{w}}[{Q}_{\pi_{w}}(s^{\prime}_{i},a^{\prime}_{i})\nabla_{w}\log\pi_{w}(s^{\prime}_{i},a^{\prime}_{i})+{d}^{q}_{\pi_{w}}(s^{\prime}_{i},a^{\prime}_{i})]),$
(18)

where $d^{v}_{\pi_{w}}$, $d^{q}_{\pi_{w}}$, $d^{\rho}_{\pi_{w}}$ denote
$\nabla_{w}V_{\pi_{w}}$, $\nabla_{w}Q_{\pi_{w}}$, $\nabla_{w}\rho_{\pi_{w}}$,
respectively. Given samples $s_{0}\sim\mu_{0}(\cdot)$,
$a_{0}\sim\pi_{w}(\cdot|s_{0})$ and $(s,a,r,s^{\prime})\sim\mathcal{D}_{d}$,
$a^{\prime}\sim\pi_{w}(\cdot|s^{\prime})$, and replace ${Q}_{\pi_{w}}$,
${\rho}_{\pi_{w}}$, ${d}^{\rho}_{\pi_{w}}$ and ${d}^{q}_{\pi_{w}}$ with
estimators $\hat{Q}_{\pi_{w}}$, $\hat{\rho}_{\pi_{w}}$,
$\hat{d}^{\rho}_{\pi_{w}}$ and $\hat{d}^{q}_{\pi_{w}}$, respectively, we can
obtain the following doubly robust estimator $G_{\text{DR}}(w)$:

$\displaystyle G_{\text{DR}}(w)$
$\displaystyle=(1-\gamma)\Big{(}\hat{Q}_{\pi_{w}}(s_{0},a_{0})\nabla_{w}\log\pi_{w}(a_{0}|s_{0})+\hat{d}^{q}_{\pi_{w}}(s_{0},a_{0})\Big{)}+\hat{d}^{\rho}_{\pi_{w}}(s,a)\left(r(s,a,s^{\prime})-\hat{Q}_{\pi_{w}}(s,a)+\gamma\hat{Q}_{\pi_{w}}(s^{\prime},a^{\prime})\right)$
$\displaystyle\quad+\hat{\rho}_{\pi_{w}}(s,a)\Big{[}-\hat{d}^{q}_{\pi_{w}}(s,a)+\gamma\Big{(}\hat{Q}_{\pi_{w}}(s^{\prime},a^{\prime})\nabla_{w}\log\pi_{w}(a^{\prime}|s^{\prime})+\hat{d}^{q}_{\pi_{w}}(s^{\prime},a^{\prime})\Big{)}\Big{]}.$
(19)

Connection with other off-policy gradient estimators: Our doubly robust
estimator $G_{\text{DR}}$ can recover a number of existing off-policy policy
gradient estimators as special cases by deactivating certain estimators, i.e.,
letting those estimators be zero.

(1) Deactivating $\hat{d}^{q}_{\pi_{w}}$ and $\hat{d}^{\rho}_{\pi_{w}}$: In
this case, $G_{\text{DR}}(w)$ takes the following form

$\displaystyle{G}^{I}_{\text{DR}}(w)$
$\displaystyle=(1-\gamma)\hat{Q}_{\pi_{w}}(s_{0},a_{0})\nabla_{w}\log\pi_{w}(a_{0}|s_{0})+\gamma\hat{\rho}_{\pi_{w}}(s,a)\Big{(}\hat{Q}_{\pi_{w}}(s^{\prime},a^{\prime})\nabla_{w}\log\pi_{w}(a^{\prime}|s^{\prime})+\hat{d}^{q}_{\pi_{w}}(s^{\prime},a^{\prime})\Big{)}$
$\displaystyle=\hat{\rho}_{\pi_{w}}(s,a)\mathbb{E}_{s^{\prime}\sim\tilde{\mathsf{P}}(\cdot|s,a),\tilde{a}^{\prime}\sim\pi_{w}(\cdot|\tilde{s}^{\prime})}\left[\hat{Q}_{\pi_{w}}(\tilde{s}^{\prime},\tilde{a}^{\prime})\nabla_{w}\log\pi_{w}(\tilde{a}^{\prime}|\tilde{s}^{\prime})\right],$
(20)

where $(\tilde{s}^{\prime},\tilde{a}^{\prime})$ is generated using the method
in the discussion of Critic III in Section 3.2. Note that the policy gradient
$\nabla_{w}J(w)$ has the following equivalent form

$\displaystyle\nabla_{w}J(w)=\mathbb{E}_{(s,a)\sim\mathcal{D}}\left[{\rho}_{\pi_{w}}(s,a)\mathbb{E}_{s^{\prime}\sim\tilde{\mathsf{P}}(\cdot|s,a),\tilde{a}^{\prime}\sim\pi_{w}(\cdot|\tilde{s}^{\prime})}\left[{Q}_{\pi_{w}}(\tilde{s}^{\prime},\tilde{a}^{\prime})\nabla_{w}\log\pi_{w}(\tilde{a}^{\prime}|\tilde{s}^{\prime})\big{|}(s,a)\right]\right].$

Thus, ${G}^{I}_{\text{DR}}(w)$ can be viewed as an off-policy policy gradient
estimator with only approximations of $\rho_{\pi_{w}}$ and $Q_{\pi_{w}}$. Such
an estimator has been adopted in the previous studies of provably convergent
off-policy actor-critic (Zhang et al., 2019c; Liu et al., 2019), which is
referred as AC-DC in our experiment in Section 5. Such an estimator has also
been adopted by many off-policy actor-critic algorithms such as ACE (Imani et
al., 2018), Geoff-PAC (Zhang et al., 2019b), OPPOSD (Liu et al., 2019) and
COF-PAC (Zhang et al., 2019c).

(2) Deactivating $\rho_{\pi_{w}}$ and $\hat{d}^{\rho}_{\pi_{w}}$: In this
case, $G_{\text{DR}}(w)$ has the following form

$\displaystyle{G}^{II}_{\text{DR}}(w)=(1-\gamma)\Big{(}\hat{Q}_{\pi_{w}}(s_{0},a_{0})\nabla_{w}\log\pi_{w}(a_{0}|s_{0})+\hat{d}^{q}_{\pi_{w}}(s_{0},a_{0})\Big{)}.$
(21)

Such an estimator ${G}^{II}_{\text{DR}}(w)$ can be viewed as the one adopted
by off-policy DPG/DDPG (Silver et al., 2014; Lillicrap et al., 2016) when the
policy $\pi_{w}$ converges to a deterministic policy.

(3) Deactivting $\hat{Q}_{\pi_{w}}$ and $\hat{d}^{q}_{\pi_{w}}$: In this case,
$G_{\text{DR}}(w)$ has the following form

$\displaystyle{G}^{III}_{\text{DR}}(w)=\hat{d}^{\rho}_{\pi_{w}}(s,a)r(s,a,s^{\prime}).$
(22)

This off-policy policy gradient estimator has been adopted in (Morimura et
al., 2010) for averaged MDP setting.

##  Appendix B Proof of Theorem 1

Without specification, the expectation is taken with respect to the randomness
of samples $(s,a,r(s,a,s^{\prime}),s^{\prime})$ and $s_{0}$, in which
$(s,a)\sim d(\cdot)$, $s^{\prime}\sim\mathsf{P}(\cdot|s,a)$ and
$s_{0}\sim\mu_{0}(\cdot)$. If $a^{\prime}$ or $a_{0}$ appears, then the
expectation is taken with respect to the the policy i.e.,
$a^{\prime}\sim\pi_{w}(\cdot|s^{\prime})$ and $a_{0}\sim\pi_{w}(\cdot|s_{0})$.
We compute the bias of $G_{\text{DR}}(w)$ as follows.

$\displaystyle\mathbb{E}[G_{\text{DR}}(w)]-\nabla_{w}J(w)$
$\displaystyle=(1-\gamma)\mathbb{E}[\hat{d}^{v}_{\pi_{w}}(s_{0})]+\mathbb{E}[\hat{d}^{\rho}_{\pi_{w}}(s,a)(r(s,a,s^{\prime})-\hat{Q}_{\pi_{w}}(s,a)+\gamma\hat{V}_{\pi_{w}}(s^{\prime}))]+\mathbb{E}[\hat{\rho}_{\pi_{w}}(s,a)(-\hat{d}^{q}_{\pi_{w}}(s,a)+\gamma\hat{d}^{v}_{\pi_{w}}(s^{\prime}))]$
$\displaystyle\quad-(1-\gamma)\mathbb{E}[{d}^{v}_{\pi_{w}}(s_{0})]-\mathbb{E}[{d}^{\rho}_{\pi_{w}}(s,a)(r(s,a,s^{\prime})-{Q}_{\pi_{w}}(s,a)+\gamma{V}_{\pi_{w}}(s^{\prime}))]-\mathbb{E}[{\rho}_{\pi_{w}}(s,a)(-{d}^{q}_{\pi_{w}}(s,a)+\gamma{d}^{v}_{\pi_{w}}(s^{\prime}))]$
$\displaystyle=\mathbb{E}[(\hat{\rho}_{\pi_{w}}(s,a)-{\rho}_{\pi_{w}}(s,a))(-\hat{d}^{q}_{\pi_{w}}(s,a)+{d}^{q}_{\pi_{w}}(s,a))]+\mathbb{E}[(-\hat{d}^{\rho}_{\pi_{w}}(s,a)+{d}^{\rho}_{\pi_{w}}(s,a))(-\hat{Q}_{\pi_{w}}(s,a)+{Q}_{\pi_{w}}(s,a))]$
$\displaystyle\quad+\gamma\mathbb{E}[(\hat{\rho}_{\pi_{w}}(s,a)-{\rho}_{\pi_{w}}(s,a))(\hat{d}^{v}_{\pi_{w}}(s)-{d}^{v}_{\pi_{w}}(s))]+\gamma\mathbb{E}[(\hat{d}^{\rho}_{\pi_{w}}(s,a)-{d}^{\rho}_{\pi_{w}}(s,a))(\hat{V}_{\pi_{w}}(s^{\prime})-{V}_{\pi_{w}}(s^{\prime}))]$
$\displaystyle\quad+\mathbb{E}[{d}^{\rho}_{\pi_{w}}(s,a)(-\hat{Q}_{\pi_{w}}(s,a)+Q_{\pi_{w}}(s,a))]+\mathbb{E}[\rho_{\pi_{w}}(s,a)(-\hat{d}^{q}_{\pi_{w}}(s,a)+{d}^{q}_{\pi_{w}}(s,a))]$
$\displaystyle\quad+\gamma\mathbb{E}[{d}^{\rho}_{\pi_{w}}(s,a)(\hat{V}_{\pi_{w}}(s^{\prime})-V_{\pi_{w}}(s^{\prime}))]+\gamma\mathbb{E}[\rho_{\pi_{w}}(s,a)(\hat{d}^{v}_{\pi_{w}}(s^{\prime})-{d}^{v}_{\pi_{w}}(s^{\prime}))]+(1-\gamma)\mathbb{E}[\hat{d}^{v}_{\pi_{w}}(s_{0})-{d}^{v}_{\pi_{w}}(s_{0})]$
$\displaystyle\quad+\mathbb{E}[(\hat{\rho}_{\pi_{w}}(s,a)-{\rho}_{\pi_{w}}(s,a))(-d^{q}_{\pi_{w}}(s,a)+\gamma
d^{v}_{\pi_{w}}(s^{\prime}))]$
$\displaystyle\quad+\mathbb{E}[(\hat{d}^{\rho}_{\pi_{w}}(s,a)-{d}^{\rho}_{\pi_{w}}(s,a))(r(s,a,s^{\prime})-Q_{\pi_{w}}(s,a)+\gamma
V_{\pi_{w}}(s^{\prime}))]$
$\displaystyle=-\mathbb{E}[\varepsilon_{\rho}(s,a)\varepsilon_{d^{q}}(s,a)]-\mathbb{E}[\varepsilon_{d^{\rho}}(s,a)\varepsilon_{q}(s,a)]+\gamma\mathbb{E}[\varepsilon_{\rho}(s,a)\varepsilon_{d^{v}}(s^{\prime})]+\gamma\mathbb{E}[\varepsilon_{\rho}(s,a)\varepsilon_{v}(s^{\prime})]$
$\displaystyle\quad+S_{1}+S_{2}+S_{3},$ (23)

where

$\displaystyle S_{1}$
$\displaystyle=\mathbb{E}[{d}^{\rho}_{\pi_{w}}(s,a)(-\hat{Q}_{\pi_{w}}(s,a)+Q_{\pi_{w}}(s,a))]+\mathbb{E}[\rho_{\pi_{w}}(s,a)(-\hat{d}^{q}_{\pi_{w}}(s,a)+{d}^{q}_{\pi_{w}}(s,a))]$
$\displaystyle\quad+\gamma\mathbb{E}[{d}^{\rho}_{\pi_{w}}(s,a)(\hat{V}_{\pi_{w}}(s^{\prime})-V_{\pi_{w}}(s^{\prime}))]+\gamma\mathbb{E}[\rho_{\pi_{w}}(s,a)(\hat{d}^{v}_{\pi_{w}}(s^{\prime})-{d}^{v}_{\pi_{w}}(s^{\prime}))]+(1-\gamma)\mathbb{E}[\hat{d}^{v}_{\pi_{w}}(s_{0})-{d}^{v}_{\pi_{w}}(s_{0})],$
$\displaystyle S_{2}$
$\displaystyle=\mathbb{E}[(\hat{\rho}_{\pi_{w}}(s,a)-{\rho}_{\pi_{w}}(s,a))(-d^{q}_{\pi_{w}}(s,a)+\gamma
d^{v}_{\pi_{w}}(s^{\prime}))],$ $\displaystyle S_{3}$
$\displaystyle=\mathbb{E}[(\hat{d}^{\rho}_{\pi_{w}}(s,a)-{d}^{\rho}_{\pi_{w}}(s,a))(r(s,a,s^{\prime})-Q_{\pi_{w}}(s,a)+\gamma
V_{\pi_{w}}(s^{\prime}))].$

We then proceed to show that $S_{1}=S_{2}=S_{3}=0$. First consider $S_{1}$.
Following from the definitions of $\hat{d}^{v}_{\pi_{w}}$ and
${d}^{v}_{\pi_{w}}$, we have

$\displaystyle S_{1}$
$\displaystyle=\mathbb{E}[{d}^{\rho}_{\pi_{w}}(s,a)(-\hat{Q}_{\pi_{w}}(s,a)+Q_{\pi_{w}}(s,a))]+\mathbb{E}[\rho_{\pi_{w}}(s,a)(-\hat{d}^{q}_{\pi_{w}}(s,a)+{d}^{q}_{\pi_{w}}(s,a))]+\gamma\mathbb{E}[{d}^{\rho}_{\pi_{w}}(s,a)(\hat{V}_{\pi_{w}}(s^{\prime})-V_{\pi_{w}}(s^{\prime}))]$
$\displaystyle\quad+\gamma\mathbb{E}[\rho_{\pi_{w}}(s,a)(\mathbb{E}[\hat{Q}_{\pi_{w}}(s^{\prime},a^{\prime})\nabla_{w}\log\pi_{w}(s^{\prime},a^{\prime})+\hat{d}^{q}_{\pi_{w}}(s^{\prime})|s^{\prime}]-\mathbb{E}[{Q}_{\pi_{w}}(s^{\prime},a^{\prime})\nabla_{w}\log\pi_{w}(s^{\prime},a^{\prime})+{d}^{q}_{\pi_{w}}(s^{\prime})|s^{\prime}])]$
$\displaystyle\quad+(1-\gamma)\mathbb{E}[\mathbb{E}[\hat{Q}_{\pi_{w}}(s_{0},a_{0})\nabla_{w}\log\pi_{w}(s_{0},a_{0})+\hat{d}^{q}_{\pi_{w}}(s_{0})|s_{0}]-\mathbb{E}[{Q}_{\pi_{w}}(s_{0},a_{0})\nabla_{w}\log\pi_{w}(s_{0},a_{0})+{d}^{q}_{\pi_{w}}(s_{0})|s_{0}]]$
$\displaystyle=\mathbb{E}[\rho_{\pi_{w}}(s,a)(d^{q}_{\pi_{w}}(s,a)-\hat{d}^{q}_{\pi_{w}}(s,a))]-\gamma\mathbb{E}[\mathbb{E}[d^{q}_{\pi_{w}}(s^{\prime},a^{\prime})-\hat{d}^{q}_{\pi_{w}}(s^{\prime},a^{\prime})|(s,a)\sim\nu_{\pi_{w}}(s,a)]]$
$\displaystyle\quad-(1-\gamma)\mathbb{E}[d^{q}_{\pi_{w}}(s_{0},a_{0})-\hat{d}^{q}_{\pi_{w}}(s_{0},a_{0})]$
$\displaystyle\quad+\mathbb{E}[d^{\rho}_{\pi_{w}}(s,a)(Q_{\pi_{w}}(s,a)-\hat{Q}_{\pi_{w}}(s,a))]-\gamma\mathbb{E}[d^{\rho}_{\pi_{w}}(s,a)(V_{\pi_{w}}(s^{\prime})-\hat{V}_{\pi_{w}}(s^{\prime}))]$
$\displaystyle\quad-\gamma\mathbb{E}[\rho_{\pi_{w}}(s,a)\mathbb{E}[(Q_{\pi_{w}}(s^{\prime},a^{\prime})-\hat{Q}_{\pi_{w}}(s^{\prime},a^{\prime}))\nabla_{w}\log\pi_{w}(s^{\prime},a^{\prime})|s,a]]$
$\displaystyle\quad-(1-\gamma)\mathbb{E}[(Q_{\pi_{w}}(s_{0},a_{0})-\hat{Q}_{\pi_{w}}(s_{0},a_{0}))\nabla_{w}\log\pi_{w}(s_{0},a_{0})].$
(24)

For the first three terms in eq. 24, we have

$\displaystyle\mathbb{E}$
$\displaystyle[\rho_{\pi_{w}}(s,a)(d^{q}_{\pi_{w}}(s,a)-\hat{d}^{q}_{\pi_{w}}(s,a))]-\gamma\mathbb{E}[\mathbb{E}[d^{q}_{\pi_{w}}(s^{\prime},a^{\prime})-\hat{d}^{q}_{\pi_{w}}(s^{\prime},a^{\prime})|(s,a)\sim\nu_{\pi_{w}}(s,a)]]$
$\displaystyle\qquad\qquad-(1-\gamma)\mathbb{E}[d^{q}_{\pi_{w}}(s_{0},a_{0})-\hat{d}^{q}_{\pi_{w}}(s_{0},a_{0})]$
$\displaystyle=\mathbb{E}_{(s,a)\sim\nu_{\pi_{w}}}[d^{q}_{\pi_{w}}(s,a)-\hat{d}^{q}_{\pi_{w}}(s,a)]-\gamma\mathbb{E}_{(s,a)\sim\nu_{\pi_{w}}}[\mathbb{E}[d^{q}_{\pi_{w}}(s^{\prime},a^{\prime})-\hat{d}^{q}_{\pi_{w}}(s^{\prime},a^{\prime})|s,a]]$
$\displaystyle\quad-(1-\gamma)\mathbb{E}[d^{q}_{\pi_{w}}(s_{0},a_{0})-\hat{d}^{q}_{\pi_{w}}(s_{0},a_{0})]$
$\displaystyle\overset{(i)}{=}\mathbb{E}_{(s,a)\sim\nu_{\pi_{w}}}[d^{q}_{\pi_{w}}(s,a)-\hat{d}^{q}_{\pi_{w}}(s,a)]-\mathbb{E}_{(s,a)\sim\nu_{\pi_{w}}}[\mathbb{E}[d^{q}_{\pi_{w}}(s^{\prime},a^{\prime})-\hat{d}^{q}_{\pi_{w}}(s^{\prime},a^{\prime})|s^{\prime}\sim\tilde{\mathsf{P}}(\cdot|s,a),a^{\prime}\sim\pi_{w}(\cdot|s^{\prime})]]$
$\displaystyle\overset{(ii)}{=}\mathbb{E}_{(s,a)\sim\nu_{\pi_{w}}}[d^{q}_{\pi_{w}}(s,a)-\hat{d}^{q}_{\pi_{w}}(s,a)]-\mathbb{E}_{(s^{\prime},a^{\prime})\sim\nu_{\pi_{w}}}[d^{q}_{\pi_{w}}(s^{\prime},a^{\prime})-\hat{d}^{q}_{\pi_{w}}(s^{\prime},a^{\prime})]$
$\displaystyle=0,$

where $(i)$ follows from the definition
$\tilde{\mathsf{P}}(\cdot|s,a)=\gamma\mathsf{P}(\cdot|s,a)+(1-\gamma)\mu_{0}(\cdot)$,
and $(ii)$ follows from the fact that $\nu_{\pi_{w}}$ is the stationary
distribution of MDP with the transition kernel $\tilde{\mathsf{P}}(\cdot|s,a)$
and policy $\pi_{w}$, i.e.,
$\pi_{w}(a^{\prime}|s^{\prime})\sum_{(s,a)}\nu_{\pi_{w}}(s,a)\tilde{\mathsf{P}}(s^{\prime}|s,a)=\nu_{\pi_{w}}(s^{\prime},a^{\prime})$.
For the last four terms in eq. 24, note that for any function $f(s,a)$, we
have the following holds

$\displaystyle\mathbb{E}$
$\displaystyle[d^{\rho}_{\pi_{w}}(s,a)f(s,a)]-\gamma\mathbb{E}[d^{\rho}_{\pi_{w}}(s,a)\mathbb{E}[f(s^{\prime},a^{\prime})|s^{\prime}]]-\gamma\mathbb{E}[\rho_{\pi_{w}}(s,a)\mathbb{E}[f(s^{\prime},a^{\prime})\nabla_{w}\log\pi_{w}(s^{\prime},a^{\prime})|s,a]]$
$\displaystyle\quad\quad-(1-\gamma)\mathbb{E}[f(s_{0},a_{0})\nabla_{w}\log\pi_{w}(s_{0},a_{0})]$
$\displaystyle=\nabla_{w}\mathbb{E}[\rho_{\pi_{w}}(s,a)f(s,a)]-\gamma\nabla_{w}\mathbb{E}[\rho_{\pi_{w}}(s,a)\mathbb{E}[f(s^{\prime},a^{\prime})|s^{\prime}]]-(1-\gamma)\nabla_{w}\mathbb{E}[\mathbb{E}[f(s_{0},a_{0})|s_{0}]]$
$\displaystyle=\nabla_{w}(\mathbb{E}[\rho_{\pi_{w}}(s,a)f(s,a)]-\gamma\mathbb{E}[\rho_{\pi_{w}}(s,a)\mathbb{E}[f(s^{\prime},a^{\prime})|s^{\prime}]]-(1-\gamma)\nabla_{w}\mathbb{E}[\mathbb{E}[f(s_{0},a_{0})|s_{0}]])$
$\displaystyle\overset{(i)}{=}\nabla_{w}(\mathbb{E}_{(s,a)\sim\nu_{\pi_{w}}}[f(s,a)]-\mathbb{E}_{(s^{\prime},a^{\prime})\sim\nu_{\pi_{w}}}[f(s^{\prime},a^{\prime})])$
$\displaystyle=0,$

where $(i)$ follows from the reasons similar to how we proceed eq. 24. Letting
$f(s,a)=Q_{\pi_{w}}(s,a)-\hat{Q}_{\pi_{w}}(s,a)$, we can then conclude that
the summation of the last four terms in eq. 24 is $0$, which implies
$S_{1}=0$.

We then consider the term $S_{2}$. Note that for any function $f(s,a)$, we
have

$\displaystyle\mathbb{E}$ $\displaystyle[f(s,a)(-d^{q}_{\pi_{w}}(s,a)+\gamma
d^{v}_{\pi_{w}}(s^{\prime}))]$
$\displaystyle=\nabla_{w}\mathbb{E}[f(s,a)(r(s,a,s^{\prime})+\gamma
V_{\pi_{w}}(s^{\prime})-Q_{\pi_{w}}(s,a))]$
$\displaystyle=\nabla_{w}\mathbb{E}[f(s,a)(\mathbb{E}[r(s,a,s^{\prime})|s]+\gamma\mathbb{E}[V_{\pi_{w}}(s^{\prime})|s,a]-Q_{\pi_{w}}(s,a))]$
$\displaystyle=0.$ (25)

Letting $f(s,a)=\hat{\rho}_{\pi_{w}}(s,a)-{\rho}_{\pi_{w}}(s,a)$, we can then
conclude that $S_{2}=0$. To consider $S_{3}$, we proceed as follows:

$\displaystyle S_{3}$
$\displaystyle=\mathbb{E}[(\hat{d}^{\rho}_{\pi_{w}}(s,a)-{d}^{\rho}_{\pi_{w}}(s,a))(r(s,a,s^{\prime})-Q_{\pi_{w}}(s,a)+\gamma
V_{\pi_{w}}(s^{\prime}))]$
$\displaystyle=\mathbb{E}[(\hat{d}^{\rho}_{\pi_{w}}(s,a)-{d}^{\rho}_{\pi_{w}}(s,a))(\mathbb{E}[r(s,a,s^{\prime})|s,a]-Q_{\pi_{w}}(s,a)+\gamma\mathbb{E}[V_{\pi_{w}}(s^{\prime})|s,a])]$
$\displaystyle=0.$

Since we have shown that $S_{1}=S_{2}=S_{3}=0$, eq. 23 becomes

$\displaystyle\mathbb{E}$ $\displaystyle[G_{\text{DR}}(w)]-\nabla_{w}J(w)$
$\displaystyle=-\mathbb{E}[\varepsilon_{\rho}(s,a)\varepsilon_{d^{q}}(s,a)]-\mathbb{E}[\varepsilon_{d^{\rho}}(s,a)\varepsilon_{q}(s,a)]+\gamma\mathbb{E}[\varepsilon_{\rho}(s,a)\varepsilon_{d^{v}}(s^{\prime})]+\gamma\mathbb{E}[\varepsilon_{\rho}(s,a)\varepsilon_{v}(s^{\prime})],$

which completes the proof.

##  Appendix C Supporting Lemmas for Theorem 2

In order to develop the property for Critic I’s update in eq. 6, we first
introduce the following definitions.

Given a sample from mini-batch $(s_{i},a_{i},r_{i},s^{\prime}_{i})$,
$a^{\prime}_{i}\sim\pi_{w_{t}}(\cdot|s^{\prime}_{i})$ and a sample
$s_{0,i}\sim\mu_{0}$, we define the following matrix
$M_{i,t}\in\mathbb{R}^{(2d_{1}+1)\times(2d_{1}+1)}$ and vector
$m_{i,t}\in\mathbb{R}^{2d_{1}+1\times 1}$

$\displaystyle M_{i,t}$
$\displaystyle=\left[\begin{array}[]{ccc}-\phi_{i}^{\top}\phi_{i}&-(\phi_{i}-\gamma\phi^{\prime}_{i})\phi^{\top}_{i}&0\\\
\phi_{i}(\phi^{\top}_{i}-\gamma\phi^{\prime\top}_{i})&0&-\phi_{i}\\\
0&\phi^{\top}_{i}&-1\end{array}\right],\qquad
m_{i,t}=\left[\begin{array}[]{c}(1-\gamma)\phi_{0,i}\\\ -r_{i}\phi_{i}\\\
-1\end{array}\right].$ (32)

Moreover, consider the matrix $M_{i,t}$. We have the following holds

$\displaystyle\left\|M_{i,t}\right\|_{F}^{2}$
$\displaystyle=\left\|\phi_{i}^{\top}\phi_{i}\right\|_{F}^{2}+2\left\|(\phi_{i}-\gamma\phi^{\prime}_{i})\phi^{\top}_{i}\right\|_{F}^{2}+2\left\|\phi_{i}\right\|_{2}^{2}+1$
$\displaystyle\leq C^{4}_{\phi}+2(1+\gamma)^{2}C^{4}_{\phi}+2C^{2}_{\phi}+1,$
(33)

which implies $\left\|M_{i,t}\right\|_{F}\leq C_{M}$, where
$C_{M}=\sqrt{9C^{4}_{\phi}+2C^{2}_{\phi}+1}$. For the vector $m_{i,t}$, we
have

$\displaystyle\left\|m_{i,t}\right\|_{2}^{2}\leq(1-\gamma)^{2}\left\|\phi_{i}\right\|_{2}^{2}+r^{2}_{\max}\left\|\phi_{i}\right\|_{2}^{2}+1\leq[(1-\gamma)^{2}+r^{2}_{\max}]C^{2}_{\phi}+1,$
(34)

which implies $\left\|m_{i,t}\right\|_{2}\leq C_{m}$, where
$C_{m}=\sqrt{(1+r^{2}_{\max})C^{2}_{\phi}+1}$.

We define the semi-stochastic-gradient as
$g_{i,t}(\kappa)=M_{i,t}\kappa+m_{i,t}$. Then the iteration in eq. 6 can be
rewritten as

$\displaystyle\kappa_{t+1}=\kappa_{t}+\beta_{1}\hat{g}_{t}(\kappa_{t}),$ (35)

where $\hat{g}_{t}(\kappa_{t})=\frac{1}{N}\sum_{i}g_{i,t}(\kappa_{t})$. We
also define $M_{t}=\mathbb{E}_{i}[M_{i,t}]$ and
$m_{t}=\mathbb{E}_{i}[m_{i,t}]$, i.e.,

$\displaystyle M_{t}$
$\displaystyle=\left[\begin{array}[]{ccc}-\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{t}}}[\phi^{\top}\phi]&-\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{t}}}[(\phi-\gamma\phi^{\prime})\phi^{\top}]&0\\\
\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{t}}}[\phi(\phi^{\top}-\gamma\phi^{\prime\top})]&0&-\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{t}}}[\phi]\\\
0&\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{t}}}[\phi^{\top}]&-1\end{array}\right],\qquad
m_{t}=\left[\begin{array}[]{c}(1-\gamma)\mathbb{E}_{\mu_{0}\cdot\pi_{w_{t}}}[\phi]\\\
-\mathbb{E}_{\mathcal{D}}[r\phi]\\\ -1\end{array}\right],$

and semi-gradient $g_{t}(\kappa)=M_{t}\kappa+m_{t}$. We further define the
fixed point of the iteration eq. 35 as

$\displaystyle\kappa^{*}_{t}=M^{-1}_{t}m_{t}=[\theta^{*\top}_{q,t},\theta^{*\top}_{\rho,t},\eta^{*}_{t}]^{\top}.$
(36)

######  Lemma 1.

Consider one step update in eq. 6. Define
$\kappa_{t}=[\theta^{\top}_{q,t},\theta^{\top}_{\rho,t},\eta_{t}]^{\top}$ and
$\kappa^{*}_{t}$ in eq. 36. Let
$\beta_{1}\leq\min\\{1/\lambda_{M},\lambda_{m}/52C^{2}_{M}\\}$, we have

$\displaystyle\mathbb{E}\left[\left\|\kappa_{t+1}-\kappa^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]\leq\left(1-\frac{1}{2}\beta_{1}\lambda_{M}\right)\left\|\kappa_{t}-\kappa^{*}_{t}\right\|_{2}^{2}+\frac{C_{1}}{N},$

where $C_{1}=24\beta^{2}_{1}(C^{2}_{M}R^{2}_{\kappa}+C^{2}_{m})$.

###### Proof.

It has been shown in (Zhang et al., 2020b) that $M_{t}$ is a Hurwitz matrix
which satisfies
$(\kappa_{t}-\kappa^{*}_{t})^{\top}M_{t}(\kappa_{t}-\kappa^{*}_{t})\leq-{\lambda_{M}}\left\|\kappa_{t}-\kappa^{*}_{t}\right\|_{2}^{2}$,
where $\lambda_{M}>0$ is a constant. We then proceed as follows:

$\displaystyle\left\|\kappa_{t+1}-\kappa^{*}_{t}\right\|_{2}^{2}$
$\displaystyle=\left\|\kappa_{t}+\beta_{1}\hat{g}_{t}(\kappa_{t})-\kappa^{*}_{t}\right\|_{2}^{2}$
$\displaystyle=\left\|\kappa_{t}-\kappa^{*}_{t}\right\|_{2}^{2}+\beta_{1}\hat{g}_{t}(\kappa_{t})^{\top}(\kappa_{t}-\kappa^{*}_{t})+\beta^{2}_{1}\left\|\hat{g}_{t}(\kappa_{t})\right\|_{2}^{2}$
$\displaystyle=\left\|\kappa_{t}-\kappa^{*}_{t}\right\|_{2}^{2}+\beta_{1}{g}_{t}(\kappa_{t})^{\top}(\kappa_{t}-\kappa^{*}_{t})+\beta_{1}(\hat{g}_{t}(\kappa_{t})-{g}_{t}(\kappa_{t}))^{\top}(\kappa_{t}-\kappa^{*}_{t})+\beta^{2}_{1}\left\|\hat{g}_{t}(\kappa_{t})-g_{t}(\kappa_{t})+g_{t}(\kappa_{t})\right\|_{2}^{2}$
$\displaystyle\overset{(i)}{\leq}(1-\beta_{1}\lambda_{M})\left\|\kappa_{t}-\kappa^{*}_{t}\right\|_{2}^{2}+\beta_{1}(\hat{g}_{t}(\kappa_{t})-{g}_{t}(\kappa_{t}))^{\top}(\kappa_{t}-\kappa^{*}_{t})+2\beta^{2}_{1}\left\|\hat{g}_{t}(\kappa_{t})-g_{t}(\kappa_{t})\right\|_{2}^{2}+2\beta^{2}_{1}\left\|g_{t}(\kappa_{t})\right\|_{2}^{2}$
$\displaystyle\overset{(ii)}{\leq}(1-\beta_{1}\lambda_{M}+2\beta^{2}_{1}C^{2}_{M})\left\|\kappa_{t}-\kappa^{*}_{t}\right\|_{2}^{2}+\beta_{1}(\hat{g}_{t}(\kappa_{t})-{g}_{t}(\kappa_{t}))^{\top}(\kappa_{t}-\kappa^{*}_{t})+2\beta^{2}_{1}\left\|\hat{g}_{t}(\kappa_{t})-g_{t}(\kappa_{t})\right\|_{2}^{2},$
(37)

where $(i)$ follows because
$g_{t}(\kappa_{t})=M_{t}(\kappa_{t}-\kappa^{*}_{t})$ and $(ii)$ follows
because$\left\|M\right\|_{F}\leq C_{M}$. Taking the expectation on both sides
of eq. 37 conditional on $\mathcal{F}_{t}$ yields

$\displaystyle\mathbb{E}\left[\left\|\kappa_{t+1}-\kappa^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]\leq(1-\beta_{1}\lambda_{M}+\beta^{2}_{1}C^{2}_{M})\left\|\kappa_{t}-\kappa^{*}_{t}\right\|_{2}^{2}+2\beta^{2}_{1}\mathbb{E}\left[\left\|\hat{g}_{t}(\kappa_{t})-g_{t}(\kappa_{t})\right\|_{2}^{2}|\mathcal{F}_{t}\right].$
(38)

Next we bound the term
$\mathbb{E}\left[\left\|\hat{g}_{t}(\kappa_{t})-g_{t}(\kappa_{t})\right\|_{2}^{2}|\mathcal{F}_{t}\right]$
as follows

$\displaystyle\mathbb{E}\left[\left\|\hat{g}_{t}(\kappa_{t})-g_{t}(\kappa_{t})\right\|_{2}^{2}|\mathcal{F}_{t}\right]$
$\displaystyle=\mathbb{E}\left[\left\|(\hat{M}_{t}-M_{t})\kappa_{t}+(\hat{m}_{t}-m_{t})\right\|_{2}^{2}|\mathcal{F}_{t}\right]$
$\displaystyle=\mathbb{E}\left[\left\|(\hat{M}_{t}-M_{t})(\kappa_{t}-\kappa^{*}_{t})+(\hat{M}_{t}-M_{t})\kappa^{*}_{t}+(\hat{m}_{t}-m_{t})\right\|_{2}^{2}|\mathcal{F}_{t}\right]$
$\displaystyle\leq
3\mathbb{E}\left[\left\|\hat{M}_{t}-M_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]\left\|\kappa_{t}-\kappa^{*}_{t}\right\|_{2}^{2}+3R^{2}_{\kappa}\mathbb{E}\left[\left\|\hat{M}_{t}-M_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]+3\mathbb{E}\left[\left\|\hat{m}_{t}-m_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right].$
(39)

Recall that $\left\|M_{i,t}\right\|_{F}\leq C_{M}$ and
$\left\|m_{i,t}\right\|_{2}\leq C_{m}$. We then have

$\displaystyle\mathbb{E}\left[\left\|\hat{M}_{t}-M_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]$
$\displaystyle\leq\mathbb{E}\left[\left\|\hat{M}_{t}-M_{t}\right\|_{F}^{2}|\mathcal{F}_{t}\right]=\mathbb{E}\left[\left\|\frac{1}{N}\sum_{i}M_{i,t}-M_{t}\right\|_{F}^{2}|\mathcal{F}_{t}\right]$
$\displaystyle\leq\frac{1}{N^{2}}\sum_{i}\sum_{j}\mathbb{E}\left[\langle
M_{i,t}-M_{t},M_{j,t}-M_{t}\rangle|\mathcal{F}_{t}\right]$
$\displaystyle=\frac{1}{N^{2}}\sum_{i}\mathbb{E}\left[\left\|M_{i,t}-M_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]\leq\frac{4C^{2}_{M}}{N}.$
(40)

Similarly, we can obtain

$\displaystyle\mathbb{E}\left[\left\|\hat{m}_{t}-m_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]\leq\frac{4C^{2}_{m}}{N}.$
(41)

Substituting eq. 40 and eq. 41 into eq. 39 yields

$\displaystyle\mathbb{E}\left[\left\|\hat{g}_{t}(\kappa_{t})-g_{t}(\kappa_{t})\right\|_{2}^{2}|\mathcal{F}_{t}\right]\leq\frac{12C^{2}_{M}}{N}\left\|\kappa_{t}-\kappa^{*}_{t}\right\|_{2}^{2}+\frac{12(C^{2}_{M}R^{2}_{\kappa}+C^{2}_{m})}{N}.$
(42)

Substituting eq. 42 into eq. 38 yields

$\displaystyle\mathbb{E}\left[\left\|\kappa_{t+1}-\kappa^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]\leq(1-\beta_{1}\lambda_{M}+26\beta^{2}_{1}C^{2}_{M})\left\|\kappa_{t}-\kappa^{*}_{t}\right\|_{2}^{2}+\frac{24\beta^{2}_{1}(C^{2}_{M}R^{2}_{\kappa}+C^{2}_{m})}{N}.$
(43)

Letting $\beta_{1}\leq\frac{\lambda_{m}}{52C^{2}_{M}}$, we have

$\displaystyle\mathbb{E}\left[\left\|\kappa_{t+1}-\kappa^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]\leq\left(1-\frac{1}{2}\beta_{1}\lambda_{M}\right)\left\|\kappa_{t}-\kappa^{*}_{t}\right\|_{2}^{2}+\frac{24\beta^{2}_{1}(C^{2}_{M}R^{2}_{\kappa}+C^{2}_{m})}{N},$

which completes the proof. ∎

We next develop the property for Critic II’s update in eq. 9. We first
introduce the following definitions.

Given a sample from mini-batch $(s_{i},a_{i},r_{i},s^{\prime}_{i})$,
$a^{\prime}_{i}\sim\pi_{w_{t}}(\cdot|s^{\prime}_{i})$, we define the following
matrix $U_{i,t}\in\mathbb{R}^{2d_{3}\times 2d_{3}}$ and vector
$u_{i,t}\in\mathbb{R}^{2d_{3}\times 1}$ as

$\displaystyle U_{i,t}=\left[\begin{array}[]{cc}0&(\gamma
x^{\prime}_{i}-x_{i})x^{\top}_{i}\\\ x_{i}(\gamma
x^{\prime}_{i}-x_{i})^{\top}&-I\end{array}\right],\qquad
u_{i,t}(\theta_{q,t})=\left[\begin{array}[]{c}0\\\
\phi^{\prime\top}_{i}\theta_{q,t}x_{i}\nabla_{w}\log\pi_{w_{t}}(a^{\prime}_{i}|s^{\prime}_{i})\end{array}\right].$
(48)

Moreover, consider the matrix $U_{t}$ and the vector $u_{t}$. Following the
steps similar to those in appendix C and eq. 34, we obtain
$\left\|U_{i,t}\right\|_{F}\leq C_{U}$ and $\left\|u_{i,t}\right\|_{2}\leq
C_{u}$, where $C_{U}=\sqrt{8C^{4}_{x}+d_{3}}$ and $C_{u}=C_{\phi}R_{q}C_{sc}$.

We also define the semi-stochastic-gradient as
$\ell_{i,t}(\zeta,\theta_{q})=U_{i,t}\xi+u_{i,t}(\theta_{q})$. Then the
iteration in eq. 14 can be rewritten as

$\displaystyle\zeta_{t+1}=\zeta_{t}+\beta_{3}\hat{\ell}_{t}(\zeta_{t},\theta_{q,t}),$
(49)

where
$\hat{\ell}_{t}(\zeta_{t},\theta_{q,t})=\frac{1}{N}\sum_{i}\ell_{i,t}(\zeta_{t},\theta_{q_{t}})$.
We define $U_{t}=\mathbb{E}_{i}[U_{i,t}]$ and
$u_{t}(\theta^{*}_{q,t})=\mathbb{E}_{i}[u_{i,t}(\theta^{*}_{q,t})]$, i.e.,

$\displaystyle
U_{t}=\left[\begin{array}[]{cc}0&\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{t}}}[(\gamma
x^{\prime}-x)x^{\top}]\\\
\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{t}}}[x(\gamma
x^{\prime}-x)^{\top}]&-I\end{array}\right],\qquad
u_{t}(\theta^{*}_{q,t})=\left[\begin{array}[]{c}0\\\
\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{t}}}[\phi^{\prime\top}\theta^{*}_{q,t}x\nabla_{w}\log\pi_{w_{t}}(a^{\prime}|s^{\prime})]\end{array}\right].$

We define the semi-gradient as
$\ell_{t}(\zeta_{t},\theta^{*}_{q,t})=U_{t}\zeta_{t}+u_{t}(\theta^{*}_{q,t})$,
and the fixed point of the iteration eq. 59 as

$\displaystyle\zeta^{*}_{t}=U^{-1}_{t}u_{t}(\theta^{*}_{q,t})=[\theta^{*\top}_{d_{q},t},0^{\top}]^{\top}.$
(50)

where $\theta^{*\top}_{d_{q},w_{t}}=A^{d_{q}-1}_{w_{t}}b^{d_{q}}_{w_{t}}$,
with $A^{d_{q}}_{w}=\mathbb{E}_{{\mathcal{D}}_{d}\cdot\pi_{w}}[(\gamma
x^{\prime}-x)x^{\prime\top}]$ and
$b^{d_{q}}_{w}=\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w}}[\phi^{\prime\top}\theta^{*}_{q,w}x\nabla_{w}\log\pi_{w}(a^{\prime}|s^{\prime})]$.

######  Lemma 2.

Consider one step update in eq. 9. Define
$\zeta_{t}=[\theta^{\top}_{d_{q},t},w^{\top}_{d_{q}.t}]^{\top}$ and
$\zeta^{*}_{t}$ in eq. 50. Let
$\beta_{3}\leq\min\\{1/\lambda_{U},\lambda_{U}/16C^{2}_{U}\\}$ and
$N\geq\frac{192C^{2}_{U}}{\lambda_{U}}\left(\frac{2}{\lambda_{U}}+2\beta_{3}\right)$,
we have

$\displaystyle\mathbb{E}\left[\left\|\zeta_{t+1}-\zeta^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]\leq\left(1-\frac{1}{4}\beta_{3}\lambda_{U}\right)\left\|\zeta_{t}-\zeta^{*}_{t}\right\|_{2}^{2}+C_{3}\beta_{3}\left\|\theta_{q,t}-\theta^{*}_{q,t}\right\|_{2}^{2}+\frac{C_{4}}{N},$

where
$C_{3}=\left(\frac{4}{\lambda_{U}}+4\beta_{3}\right)C^{2}_{\phi}C^{2}_{x}C^{2}_{\pi}$
and
$C_{4}=\left(\frac{48\beta_{3}}{\lambda_{U}}+48\beta^{2}_{3}\right)(C^{2}_{U}R^{2}_{\zeta}+C^{2}_{\phi}R^{2}_{\theta_{q}}C^{2}_{x}C^{2}_{\pi})$.

###### Proof.

Following the steps similar to those in the proof of Theorem 1 in Chapter 5 of
(Maei, 2011), we can show that $U_{t}$ is a Hurwitz matrix which
$(\zeta_{t}-\zeta^{*}_{t})^{\top}U_{t}(\zeta_{t}-\zeta^{*}_{t})\leq-{\lambda_{U}}\left\|\zeta_{t}-\zeta^{*}_{t}\right\|_{2}^{2}$,
where $\lambda_{U}>0$ is a constant. Following steps similar to those in the
proof of Theorem 4 in (Xu et al., 2020b), we can obtain

$\displaystyle\mathbb{E}\left[\left\|\zeta_{t+1}-\zeta^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]$
$\displaystyle=\left\|\zeta_{t}+\beta_{3}\hat{\ell}_{t}(\zeta_{t},\theta_{q,t})-\zeta^{*}_{t}\right\|_{2}^{2}$
$\displaystyle\leq\left(1-\frac{1}{2}\beta_{3}\lambda_{U}+2C^{2}_{U}\beta^{2}_{3}\right)\left\|\zeta_{t}-\zeta^{*}_{t}\right\|_{2}^{2}+\left(\frac{2\beta_{3}}{\lambda_{U}}+2\beta^{2}_{3}\right)\mathbb{E}\left[\left\|\hat{\ell}_{t}(\zeta_{t},\theta_{q,t})-\ell_{t}(\zeta_{t},\theta^{*}_{q,t})\right\|_{2}^{2}\Big{|}\mathcal{F}_{t}\right].$
(51)

Next we bound the term
$\mathbb{E}\left[\left\|\hat{\ell}_{t}(\zeta_{t},\theta_{q,t})-\ell_{t}(\zeta_{t},\theta^{*}_{q,t})\right\|_{2}^{2}\Big{|}\mathcal{F}_{t}\right]$
as follows:

$\displaystyle\mathbb{E}$
$\displaystyle\left[\left\|\hat{\ell}_{t}(\zeta_{t},\theta_{q,t})-\ell_{t}(\zeta_{t},\theta^{*}_{q,t})\right\|_{2}^{2}\Big{|}\mathcal{F}_{t}\right]$
$\displaystyle=\mathbb{E}\left[\left\|\hat{\ell}_{t}(\zeta_{t},\theta_{q,t})-\hat{\ell}_{t}(\zeta_{t},\theta^{*}_{q,t})+\hat{\ell}_{t}(\zeta_{t},\theta^{*}_{q,t})-\ell_{t}(\zeta_{t},\theta^{*}_{q,t})\right\|_{2}^{2}\Big{|}\mathcal{F}_{t}\right]$
$\displaystyle=2\mathbb{E}\left[\left\|\hat{\ell}_{t}(\zeta_{t},\theta_{q,t})-\hat{\ell}_{t}(\zeta_{t},\theta^{*}_{q,t})\right\|_{2}^{2}\Big{|}\mathcal{F}_{t}\right]+2\mathbb{E}\left[\left\|\hat{\ell}_{t}(\zeta_{t},\theta^{*}_{q,t})-\ell_{t}(\zeta_{t},\theta^{*}_{q,t})\right\|_{2}^{2}\Big{|}\mathcal{F}_{t}\right]$
$\displaystyle=2\mathbb{E}\left[\left\|\frac{1}{N}\sum_{i}(\ell_{i,t}(\zeta_{t},\theta_{q_{t}})-\ell_{i,t}(\zeta_{t},\theta^{*}_{q_{t}}))\right\|_{2}^{2}\Big{|}\mathcal{F}_{t}\right]+2\mathbb{E}\left[\left\|\hat{\ell}_{t}(\zeta_{t},\theta^{*}_{q,t})-\ell_{t}(\zeta_{t},\theta^{*}_{q,t})\right\|_{2}^{2}\Big{|}\mathcal{F}_{t}\right]$
$\displaystyle\leq\frac{2}{N}\sum_{i}\mathbb{E}\left[\left\|(\ell_{i,t}(\zeta_{t},\theta_{q_{t}})-\ell_{i,t}(\zeta_{t},\theta^{*}_{q_{t}}))\right\|_{2}^{2}\Big{|}\mathcal{F}_{t}\right]+2\mathbb{E}\left[\left\|\hat{\ell}_{t}(\zeta_{t},\theta^{*}_{q,t})-\ell_{t}(\zeta_{t},\theta^{*}_{q,t})\right\|_{2}^{2}\Big{|}\mathcal{F}_{t}\right]$
$\displaystyle=\frac{2}{N}\sum_{i}\mathbb{E}\left[\left\|\phi^{\prime\top}_{i}(\theta_{q,t}-\theta^{*}_{q,t})x_{i}\nabla_{w}\log\pi_{w_{t}}(a^{\prime}_{i}|s^{\prime}_{i})\right\|_{2}^{2}\Big{|}\mathcal{F}_{t}\right]+2\mathbb{E}\left[\left\|\hat{\ell}_{t}(\zeta_{t},\theta^{*}_{q,t})-\ell_{t}(\zeta_{t},\theta^{*}_{q,t})\right\|_{2}^{2}\Big{|}\mathcal{F}_{t}\right]$
$\displaystyle=2C^{2}_{\phi}C^{2}_{x}C^{2}_{\pi}\left\|\theta_{q,t}-\theta^{*}_{q,t}\right\|_{2}^{2}+2\mathbb{E}\left[\left\|\hat{\ell}_{t}(\zeta_{t},\theta^{*}_{q,t})-\ell_{t}(\zeta_{t},\theta^{*}_{q,t})\right\|_{2}^{2}\Big{|}\mathcal{F}_{t}\right].$
(52)

To bound the term
$\mathbb{E}\left[\left\|\hat{\ell}_{t}(\zeta_{t},\theta^{*}_{q,t})-\ell_{t}(\zeta_{t},\theta^{*}_{q,t})\right\|_{2}^{2}\Big{|}\mathcal{F}_{t}\right]$,
we follow the steps similar to those in the proof of bounding the term
$\mathbb{E}\left[\left\|\hat{g}_{t}(\kappa_{t})-g_{t}(\kappa_{t})\right\|_{2}^{2}|\mathcal{F}_{t}\right]$
in Lemma 1 to obtain

$\displaystyle\mathbb{E}\left[\left\|\hat{\ell}_{t}(\zeta_{t},\theta^{*}_{q,t})-\ell_{t}(\zeta_{t},\theta^{*}_{q,t})\right\|_{2}^{2}|\mathcal{F}_{t}\right]\leq\frac{12C^{2}_{U}}{N}\left\|\zeta_{t}-\zeta^{*}_{t}\right\|_{2}^{2}+\frac{12(C^{2}_{U}R^{2}_{\zeta}+C^{2}_{\phi}R^{2}_{\theta_{q}}C^{2}_{x}C^{2}_{\pi})}{N},$
(53)

Substituting eq. 53 and eq. 52 into eq. 51 yields

$\displaystyle\mathbb{E}$
$\displaystyle\left[\left\|\zeta_{t+1}-\zeta^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]$
$\displaystyle\leq\left(1-\frac{1}{2}\beta_{3}\lambda_{U}+2C^{2}_{U}\beta^{2}_{3}\right)\left\|\zeta_{t}-\zeta^{*}_{t}\right\|_{2}^{2}$
$\displaystyle\quad+\left(\frac{2\beta_{3}}{\lambda_{U}}+2\beta^{2}_{3}\right)\left(2C^{2}_{\phi}C^{2}_{x}C^{2}_{\pi}\left\|\theta_{q,t}-\theta^{*}_{q,t}\right\|_{2}^{2}+\frac{24C^{2}_{U}}{N}\left\|\zeta_{t}-\zeta^{*}_{t}\right\|_{2}^{2}+\frac{24(C^{2}_{U}R^{2}_{\zeta}+C^{2}_{\phi}R^{2}_{\theta_{q}}C^{2}_{x}C^{2}_{\pi})}{N}\right)$
$\displaystyle=\left[1-\frac{1}{2}\beta_{3}\lambda_{U}+2C^{2}_{U}\beta^{2}_{3}+\left(\frac{2\beta_{3}}{\lambda_{U}}+2\beta^{2}_{3}\right)\frac{24C^{2}_{U}}{N}\right]\left\|\zeta_{t}-\zeta^{*}_{t}\right\|_{2}^{2}$
$\displaystyle\quad+\left(\frac{4\beta_{3}}{\lambda_{U}}+4\beta^{2}_{3}\right)C^{2}_{\phi}C^{2}_{x}C^{2}_{\pi}\left\|\theta_{q,t}-\theta^{*}_{q,t}\right\|_{2}^{2}+\left(\frac{2\beta_{3}}{\lambda_{U}}+2\beta^{2}_{3}\right)\frac{24(C^{2}_{U}R^{2}_{\zeta}+C^{2}_{\phi}R^{2}_{\theta_{q}}C^{2}_{x}C^{2}_{\pi})}{N}.$

Letting $\beta_{3}\leq\min\\{1/\lambda_{U},\lambda_{U}/16C^{2}_{U}\\}$ and
$N\geq\frac{192C^{2}_{U}}{\lambda_{U}}\left(\frac{2}{\lambda_{U}}+2\beta_{3}\right)$,
we have

$\displaystyle\mathbb{E}\left[\left\|\zeta_{t+1}-\zeta^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]\leq\left(1-\frac{1}{4}\beta_{3}\lambda_{U}\right)\left\|\zeta_{t}-\zeta^{*}_{t}\right\|_{2}^{2}+C_{3}\beta_{3}\left\|\theta_{q,t}-\theta^{*}_{q,t}\right\|_{2}^{2}+\frac{C_{4}}{N},$

where
$C_{3}=\left(\frac{4}{\lambda_{U}}+4\beta_{3}\right)C^{2}_{\phi}C^{2}_{x}C^{2}_{\pi}$
and
$C_{4}=\left(\frac{48\beta_{3}}{\lambda_{U}}+48\beta^{2}_{3}\right)(C^{2}_{U}R^{2}_{\zeta}+C^{2}_{\phi}R^{2}_{\theta_{q}}C^{2}_{x}C^{2}_{\pi})$.
∎

We next develop the property for Critic III’s update. We first introduce the
following definitions.

Given a sample $(s_{i},a_{i},r_{i},\tilde{s}^{\prime}_{i})$ generated as we
discuss in Section 3 and
$a^{\prime}_{i}\sim\pi_{w_{t}}(\cdot|s^{\prime}_{i})$. We define the following
matrix $P_{i,t}\in\mathbb{R}^{2d_{1}\times 2d_{2}}$ and vector
$p_{i,t}\in\mathbb{R}^{2d_{2}\times 1}$ as

$\displaystyle
P_{i,t}=\left[\begin{array}[]{cc}0&(\varphi_{i}-\tilde{\varphi}^{\prime}_{i})\tilde{\varphi}^{\prime\top}_{i}\\\
\tilde{\varphi}^{\prime}_{i}(\varphi_{i}-\tilde{\varphi}^{\prime}_{i})^{\top}&-I\end{array}\right],\qquad
p_{i,t}=\left[\begin{array}[]{c}0\\\
\tilde{\varphi}^{\prime}_{i}\nabla_{w}\log\pi_{w_{t}}(a^{\prime}_{i}|\tilde{s}^{\prime}_{i})\end{array}\right].$
(58)

Consider the matrix $P_{i,t}$ and the vector $p_{i,t}$. Following the steps
similar to those in appendix C and eq. 34, we obtain
$\left\|P_{i,t}\right\|_{F}\leq C_{P}$ and $\left\|p_{i,t}\right\|_{2}\leq
C_{p}$, where $C_{P}=\sqrt{8C^{4}_{\varphi}+d_{2}}$ and
$C_{p}={C_{\varphi}C_{sc}}$.

We also define the semi-stochastic-gradient as
$h_{i,t}(\xi)=P_{i,t}\xi+p_{i,t}$. Then the iteration in eq. 14 can be
rewritten as

$\displaystyle\xi_{t+1}=\xi_{t}+\beta_{2}\hat{h}_{t}(\xi_{t}),$ (59)

where $\hat{h}_{t}(\xi_{t})=\frac{1}{N}\sum_{i}h_{i,t}(\xi_{t})$. We define
$P_{t}=\mathbb{E}_{i}[P_{i,t}]$ and $p_{t}=\mathbb{E}_{i}[p_{i,t}]$, i.e.,

$\displaystyle
P_{t}=\left[\begin{array}[]{cc}0&\mathbb{E}_{\tilde{\mathcal{D}}_{d}\cdot\pi_{w_{t}}}[(\varphi-\varphi^{\prime})\varphi^{\prime\top}]\\\
\mathbb{E}_{\tilde{\mathcal{D}}_{d}\cdot\pi_{w_{t}}}[\varphi^{\prime}(\varphi-\varphi^{\prime})^{\top}]&-I\end{array}\right],\qquad
p_{t}=\left[\begin{array}[]{c}0\\\
\mathbb{E}_{\tilde{\mathcal{D}}_{d}\cdot\pi_{w_{t}}}[\varphi^{\prime}\nabla_{w}\log\pi_{w_{t}}(a^{\prime}|{s}^{\prime})]\end{array}\right].$

We further define the fixed point of the iteration eq. 59 as

$\displaystyle\xi^{*}_{t}=P^{-1}_{t}p_{t}=[\theta^{*\top}_{\psi,w_{t}},0^{\top}]^{\top},$
(60)

where $\theta^{*\top}_{\psi,w_{t}}=A^{\xi-1}_{w_{t}}b^{\xi}_{w_{t}}$, with
$A^{\xi}_{w}=\mathbb{E}_{\tilde{\mathcal{D}}_{d}\cdot\pi_{w}}[(\varphi-\varphi^{\prime})\varphi^{\prime\top}]$
and
$b^{\xi}_{w}=\mathbb{E}_{\tilde{\mathcal{D}}_{d}\cdot\pi_{w}}[\varphi^{\prime}\nabla_{w}\log\pi_{w}(a^{\prime}|\tilde{s}^{\prime})]$.

######  Lemma 3.

Consider one step update in eq. 14. Define
$\xi_{t}=[\theta^{\top}_{\psi,t},w^{\top}_{\psi,t}]^{\top}$ and $\xi^{*}_{t}$
in eq. 60. Let $\beta_{2}\leq\min\\{1/\lambda_{P},\lambda_{P}/52C^{2}_{P}\\}$,
we have

$\displaystyle\mathbb{E}\left[\left\|\xi_{t+1}-\xi^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]\leq\left(1-\frac{1}{2}\beta_{2}\lambda_{P}\right)\left\|\xi_{t}-\xi^{*}_{t}\right\|_{2}^{2}+\frac{C_{2}}{N},$

where $C_{2}=24\beta^{2}_{2}(C^{2}_{P}R^{2}_{\xi}+C^{2}_{p})$.

###### Proof.

Following the steps similar to those in the proof of Theorem 1 in Chapter 5 of
(Maei, 2011), we can show that $P_{t}$ is a Hurwitz matrix that satisfies
$(\xi_{t}-\xi^{*}_{t})^{\top}P_{t}(\xi_{t}-\xi^{*}_{t})\leq-{\lambda_{P}}\left\|\xi_{t}-\xi^{*}_{t}\right\|_{2}^{2}$,
where $\lambda_{P}>0$ is a constant. Then letting
$\beta_{2}\leq\min\\{\frac{\lambda_{p}}{52C^{2}_{P}},1/\lambda_{P}\\}$,
following the steps similar to those in the proof of bounding the term
$\mathbb{E}\left[\left\|\hat{g}_{t}(\kappa_{t})-g_{t}(\kappa_{t})\right\|_{2}^{2}|\mathcal{F}_{t}\right]$
in Lemma 1, we can obtain

$\displaystyle\mathbb{E}\left[\left\|\xi_{t+1}-\xi^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]\leq\left(1-\frac{1}{2}\beta_{2}\lambda_{P}\right)\left\|\xi_{t}-\xi^{*}_{t}\right\|_{2}^{2}+\frac{24\beta^{2}_{2}(C^{2}_{P}R^{2}_{\xi}+C^{2}_{p})}{N}.$

∎

######  Lemma 4.

Consider policy $\pi_{w_{1}}$ and $\pi_{w_{2}}$, respectively, with the fixed
points
$\kappa^{*}_{1}=[\theta^{*\top}_{q,w_{1}},\theta^{*\top}_{\rho,w_{1}},\eta^{*}_{w_{1}}]^{\top}$
and
$\kappa^{*}_{2}=[\theta^{*\top}_{q,w_{1}},\theta^{*\top}_{\rho,w_{1}},\eta^{*}_{w_{1}}]^{\top}$
as defined in eq. 60. We have

$\displaystyle\left\|\theta^{*\top}_{q,w_{1}}-\theta^{*\top}_{q,w_{2}}\right\|_{2}$
$\displaystyle\leq L_{q}\left\|w_{1}-w_{2}\right\|_{2},$
$\displaystyle\left\|\theta^{*\top}_{\rho,w_{1}}-\theta^{*\top}_{\rho,w_{2}}\right\|_{2}$
$\displaystyle\leq L_{\rho}\left\|w_{1}-w_{2}\right\|_{2},$
$\displaystyle\left\|\eta^{*}_{w_{1}}-\eta^{*}_{w_{2}}\right\|_{2}$
$\displaystyle\leq L_{\eta}\left\|w_{1}-w_{2}\right\|_{2},$

where
$L_{q}=\frac{L^{\kappa}_{C}(C^{\kappa}_{E}+C^{\kappa}_{A}R_{\rho})+\lambda^{\kappa}_{C}(L^{\kappa}_{E}+C^{\kappa}_{A}L\rho+L^{\kappa}_{A}R_{\rho})}{(\lambda^{\kappa}_{C})^{2}}$,
$L_{\rho}=\frac{C^{\kappa}_{G}L^{\kappa}_{F}+\lambda^{\kappa}_{F}L^{\kappa}_{G}}{(\lambda^{\kappa}_{F})^{2}}$,
and $L_{\eta}=C^{\kappa}_{D}L_{\rho}+L^{\kappa}_{D}R_{\rho}$, which further
implies that

$\displaystyle\left\|\kappa^{*}_{1}-\kappa^{*}_{2}\right\|_{2}\leq
L_{\kappa}\left\|w_{1}-w_{2}\right\|_{2},$

where $L_{\kappa}=\sqrt{L^{2}_{q}+L^{2}_{p}+L^{2}_{\eta}}$.

###### Proof.

Define
$A^{\kappa}_{w}=\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w}}[(\phi-\gamma\phi^{\prime})\phi^{\top}]$,
$C^{\kappa}_{w}=\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{t}}}[\phi^{\top}\phi]$,
$D^{\kappa}_{w}=\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{t}}}[\phi]$ and
$E^{\kappa}_{w}=(1-\gamma)\mathbb{E}_{\mu_{0}\cdot\pi_{w_{t}}}[\phi]$. (Zhang
et al., 2020b, a) showed that

$\displaystyle\theta^{*}_{\rho,w}$
$\displaystyle=-F^{\kappa\,-1}_{w}G^{\kappa}_{w},$
$\displaystyle\theta^{*}_{q,w}$
$\displaystyle=C^{\kappa-1}_{w}(E^{\kappa}_{w}-A^{\kappa}_{w}\theta^{*}_{\rho,w}),$
$\displaystyle\eta^{*}_{w}$
$\displaystyle=D^{\kappa}_{w}\theta^{*}_{\rho,w}-1,$

where

$\displaystyle F^{\kappa}_{w}$
$\displaystyle=A^{\kappa\top}_{w}C^{\kappa\,-1}_{w}A^{\kappa}_{w}+D^{\kappa}_{w}D^{\kappa\top}_{w},$
$\displaystyle G^{\kappa}_{w}$
$\displaystyle=A^{\kappa\top}_{w}C^{\kappa\,-1}_{w}E^{\kappa}_{w}+D^{\kappa}_{w}.$

We first develop the Lipschitz property for the matrices $A^{\kappa}_{w}$,
$C^{\kappa}_{w}$, $D^{\kappa}_{w}$, and $E^{\kappa}_{w}$. For
$A^{\kappa}_{w}$, we obtain the following

$\displaystyle\left\|A^{\kappa}_{w_{1}}-A^{\kappa}_{w_{2}}\right\|_{2}$
$\displaystyle=\left\|-\mathbb{E}_{\tilde{\mathcal{D}}_{d}\cdot\pi_{w_{1}}}[(\gamma\phi^{\prime}-\phi)\phi^{\top}]+\mathbb{E}_{\tilde{\mathcal{D}}_{d}\cdot\pi_{w_{2}}}[(\gamma\phi^{\prime}-\phi)\phi^{\top}]\right\|_{2}$
$\displaystyle=\left\|\int\gamma\phi(s^{\prime},a^{\prime})\phi(s,a)^{\top}(\pi_{w_{2}}(da^{\prime}|s^{\prime})-\pi_{w_{1}}(da^{\prime}|s^{\prime}))\tilde{\mathsf{P}}(ds^{\prime}|s,a)\mathcal{D}(ds,da)\right\|_{2}$
$\displaystyle\quad+\left\|\int\phi(s,a)\phi(s,a)^{\top}(\pi_{w_{1}}(da^{\prime}|s^{\prime})-\pi_{w_{2}}(da^{\prime}|s^{\prime}))\tilde{\mathsf{P}}(ds^{\prime}|s,a)\mathcal{D}(ds,da)\right\|_{2}$
$\displaystyle\leq\int\left\|\gamma\phi(s^{\prime},a^{\prime})\phi(s,a)^{\top}\right\|_{2}\left|(\pi_{w_{1}}(da^{\prime}|s^{\prime})-\pi_{w_{2}}(da^{\prime}|s^{\prime}))\right|\tilde{\mathsf{P}}(ds^{\prime}|s,a)\mathcal{D}(ds,da)$
$\displaystyle\quad+\int\left\|\phi(s,a)\phi(s,a)^{\top}\right\|_{2}\left|(\pi_{w_{2}}(da^{\prime}|s^{\prime})-\pi_{w_{1}}(da^{\prime}|s^{\prime}))\right|\tilde{\mathsf{P}}(ds^{\prime}|s,a)\mathcal{D}(ds,da)$
$\displaystyle\leq
2C^{2}_{\phi}\int\left|\pi_{w_{1}}(da^{\prime}|s^{\prime})-\pi_{w_{2}}(da^{\prime}|s^{\prime})\right|\tilde{\mathsf{P}}(ds^{\prime}|s,a)\mathcal{D}(ds,da)$
$\displaystyle\leq
2C^{2}_{\phi}\left\|\pi_{w_{1}}(\cdot)-\pi_{w_{2}}(\cdot)\right\|_{TV}$
$\displaystyle\leq 2C^{2}_{\phi}L_{\pi}\left\|w_{1}-w_{2}\right\|_{2}.$ (61)

For $C^{\kappa}_{w}$, $D^{\kappa}_{w}$, and $E^{\kappa}_{w}$, following the
steps similar to those in eq. 61, we obtain

$\displaystyle\left\|C^{\kappa}_{w_{1}}-C^{\kappa}_{w_{2}}\right\|_{2}$
$\displaystyle\leq
C^{2}_{\phi}L_{\pi}\left\|w_{1}-w_{2}\right\|_{2}=L^{\kappa}_{C}\left\|w_{1}-w_{2}\right\|_{2},$
$\displaystyle\left\|D^{\kappa}_{w_{1}}-D^{\kappa}_{w_{2}}\right\|_{2}$
$\displaystyle\leq
C_{\phi}L_{\pi}\left\|w_{1}-w_{2}\right\|_{2}=L^{\kappa}_{D}\left\|w_{1}-w_{2}\right\|_{2},$
$\displaystyle\left\|E^{\kappa}_{w_{1}}-E^{\kappa}_{w_{2}}\right\|_{2}$
$\displaystyle\leq(1-\gamma)C_{\phi}L_{\pi}\left\|w_{1}-w_{2}\right\|_{2}=L^{\kappa}_{E}\left\|w_{1}-w_{2}\right\|_{2},$
(62)

where $L^{\kappa}_{C}=C^{2}_{\phi}L_{\pi}$, $L^{\kappa}_{D}=C_{\phi}L_{\pi}$,
and $L^{\kappa}_{E}=(1-\gamma)C_{\phi}L_{\pi}$. We then proceed to bound the
two terms $\left\|F^{\kappa}_{w_{1}}-F^{\kappa}_{w_{2}}\right\|_{2}$ and
$\left\|G^{\kappa}_{w_{1}}-G^{\kappa}_{w_{2}}\right\|_{2}$. For
$\left\|F^{\kappa}_{w_{1}}-F^{\kappa}_{w_{2}}\right\|_{2}$, we obtain the
following bound:

$\displaystyle\left\|F^{\kappa}_{w_{1}}-F^{\kappa}_{w_{2}}\right\|_{2}$
$\displaystyle=\left\|A^{\kappa\top}_{w_{1}}C^{\kappa\,-1}_{w_{1}}A^{\kappa}_{w_{1}}-A^{\kappa\top}_{w_{2}}C^{\kappa\,-1}_{w_{2}}A^{\kappa}_{w_{2}}+D^{\kappa}_{w_{1}}D^{\kappa\top}_{w_{1}}-D^{\kappa}_{w_{2}}D^{\kappa\top}_{w_{2}}\right\|_{2}$
$\displaystyle\leq\left\|A^{\kappa\top}_{w_{1}}C^{\kappa\,-1}_{w_{1}}A^{\kappa}_{w_{1}}-A^{\kappa\top}_{w_{2}}C^{\kappa\,-1}_{w_{2}}A^{\kappa}_{w_{2}}\right\|_{2}+\left\|D^{\kappa}_{w_{1}}D^{\kappa\top}_{w_{1}}-D^{\kappa}_{w_{2}}D^{\kappa\top}_{w_{2}}\right\|_{2}$
$\displaystyle=\left\|A^{\kappa\top}_{w_{1}}C^{\kappa\,-1}_{w_{1}}(C^{\kappa}_{w_{2}}-C^{\kappa}_{w_{1}})C^{\kappa\,-1}_{w_{2}}A^{\kappa}_{w_{1}}+(A^{\kappa}_{w_{1}}-A^{\kappa}_{w_{2}})^{\top}C^{\kappa\,-1}_{w_{2}}A^{\kappa}_{w_{1}}+A^{\kappa}_{w_{2}}C^{\kappa\,-1}_{w_{2}}(A^{\kappa}_{w_{1}}-A^{\kappa}_{w_{2}})\right\|_{2}$
$\displaystyle\quad+\left\|D^{\kappa}_{w_{1}}(D^{\kappa}_{w_{1}}-D^{\kappa}_{w_{2}})^{\top}+(D^{\kappa}_{w_{1}}-D^{\kappa}_{w_{2}})D^{\kappa\top}_{w_{2}}\right\|_{2}$
$\displaystyle\leq\left\|A^{\kappa\top}_{w_{1}}C^{\kappa\,-1}_{w_{1}}(C^{\kappa}_{w_{2}}-C^{\kappa}_{w_{1}})C^{\kappa\,-1}_{w_{2}}A^{\kappa}_{w_{1}}\right\|_{2}+\left\|(A^{\kappa}_{w_{1}}-A^{\kappa}_{w_{2}})^{\top}C^{\kappa\,-1}_{w_{2}}A^{\kappa}_{w_{1}}\right\|_{2}+\left\|A^{\kappa}_{w_{2}}C^{\kappa\,-1}_{w_{2}}(A^{\kappa}_{w_{1}}-A^{\kappa}_{w_{2}})\right\|_{2}$
$\displaystyle\quad+\left\|D^{\kappa}_{w_{1}}(D^{\kappa}_{w_{1}}-D^{\kappa}_{w_{2}})^{\top}\right\|_{2}+\left\|(D^{\kappa}_{w_{1}}-D^{\kappa}_{w_{2}})D^{\kappa\top}_{w_{2}}\right\|_{2}$
$\displaystyle\leq\left(\frac{L^{\kappa}_{C}(C^{\kappa}_{A})^{2}+2C^{\kappa}_{A}\lambda^{\kappa}_{C}L^{\kappa}_{C}}{(\lambda^{\kappa}_{C})^{2}}+C^{\kappa}_{D}L^{\kappa}_{D}\right)\left\|w_{1}-w_{2}\right\|_{2}$
$\displaystyle=L^{\kappa}_{F}\left\|w_{1}-w_{2}\right\|_{2},$ (63)

where

$\displaystyle
L^{\kappa}_{F}=\frac{L^{\kappa}_{C}(C^{\kappa}_{A})^{2}+2C^{\kappa}_{A}\lambda^{\kappa}_{C}L^{\kappa}_{C}}{(\lambda^{\kappa}_{C})^{2}}+C^{\kappa}_{D}L^{\kappa}_{D}.$

For $\left\|G^{\kappa}_{w_{1}}-G^{\kappa}_{w_{2}}\right\|_{2}$, we have

$\displaystyle\left\|G^{\kappa}_{w_{1}}-G^{\kappa}_{w_{2}}\right\|_{2}$
$\displaystyle=\left\|A^{\kappa\top}_{w_{1}}C^{\kappa\,-1}_{w_{1}}E^{\kappa}_{w_{1}}-A^{\kappa\top}_{w_{2}}C^{\kappa\,-1}_{w_{2}}E^{\kappa}_{w_{2}}+D^{\kappa}_{w_{1}}-D^{\kappa}_{w_{2}}\right\|_{2}$
$\displaystyle\leq\left\|A^{\kappa\top}_{w_{1}}C^{\kappa\,-1}_{w_{1}}E^{\kappa}_{w_{1}}-A^{\kappa\top}_{w_{2}}C^{\kappa\,-1}_{w_{2}}E^{\kappa}_{w_{2}}\right\|_{2}+\left\|D^{\kappa}_{w_{1}}-D^{\kappa}_{w_{2}}\right\|_{2}$
$\displaystyle=\left\|A^{\kappa\top}_{w_{1}}C^{\kappa\,-1}_{w_{1}}(C^{\kappa}_{w_{2}}-C^{\kappa}_{w_{1}})C^{\kappa\,-1}_{w_{2}}E^{\kappa}_{w_{1}}+(A^{\kappa}_{w_{1}}-A^{\kappa}_{w_{2}})^{\top}C^{\kappa\,-1}_{w_{2}}E^{\kappa}_{w_{1}}+A^{\kappa}_{w_{2}}C^{\kappa\,-1}_{w_{2}}(E^{\kappa}_{w_{1}}-E^{\kappa}_{w_{2}})\right\|_{2}+\left\|D^{\kappa}_{w_{1}}-D^{\kappa}_{w_{2}}\right\|_{2}$
$\displaystyle\leq\left(\frac{L^{\kappa}_{C}C^{\kappa}_{A}C^{\kappa}_{E}+C^{\kappa}_{E}\lambda^{\kappa}_{C}L^{\kappa}_{A}+C^{\kappa}_{A}\lambda^{\kappa}_{C}L^{\kappa}_{E}}{(\lambda^{\kappa}_{C})^{2}}+L^{\kappa}_{D}\right)\left\|w_{1}-w_{2}\right\|_{2}$
$\displaystyle=L^{\kappa}_{G}\left\|w_{1}-w_{2}\right\|_{2},$ (64)

where

$\displaystyle
L^{\kappa}_{G}=\frac{L^{\kappa}_{C}C^{\kappa}_{A}C^{\kappa}_{E}+C^{\kappa}_{E}\lambda^{\kappa}_{C}L^{\kappa}_{A}+C^{\kappa}_{A}\lambda^{\kappa}_{C}L^{\kappa}_{E}}{(\lambda^{\kappa}_{C})^{2}}+L^{\kappa}_{D}.$

We next prove the Lipschitz property for $\theta^{*}_{\rho}$. To bound
$\left\|\theta^{*\top}_{\rho,w_{1}}-\theta^{*\top}_{\rho,w_{2}}\right\|_{2}$,
we proceed as follows.

$\displaystyle\theta^{*\top}_{\rho,w_{1}}-\theta^{*\top}_{\rho,w_{2}}=F^{\kappa-1}_{w_{1}}G^{\kappa}_{w_{1}}-F^{\kappa-1}_{w_{2}}G^{\kappa}_{w_{2}}=(F^{\kappa-1}_{w_{1}}-F^{\kappa-1}_{w_{2}})G^{\kappa}_{w_{1}}+F^{\kappa-1}_{w_{2}}(G^{\kappa}_{w_{1}}-G^{\kappa}_{w_{2}})$
$\displaystyle=(F^{\kappa-1}_{w_{1}}F^{\kappa}_{w_{2}}F^{\kappa-1}_{w_{2}}-F^{\kappa-1}_{w_{1}}F^{\kappa}_{w_{1}}F^{\kappa-1}_{w_{2}})G^{\kappa}_{w_{1}}+F^{\kappa-1}_{w_{2}}(G^{\kappa}_{w_{1}}-G^{\kappa}_{w_{2}})$
$\displaystyle=F^{\kappa-1}_{w_{1}}(F^{\kappa}_{w_{2}}-F^{\kappa}_{w_{1}})F^{\kappa-1}_{w_{2}}G^{\kappa}_{w_{1}}+F^{\kappa-1}_{w_{2}}(G^{\kappa}_{w_{1}}-G^{\kappa}_{w_{2}}),$
(65)

which implies

$\displaystyle\left\|\theta^{*\top}_{\rho,w_{1}}-\theta^{*\top}_{\rho,w_{2}}\right\|_{2}$
$\displaystyle\leq\left\|F^{\kappa-1}_{w_{1}}\right\|_{2}\left\|F^{\kappa}_{w_{2}}-F^{\kappa}_{w_{1}}\right\|_{2}\left\|F^{\kappa-1}_{w_{2}}\right\|_{2}\left\|G^{\kappa}_{w_{1}}\right\|_{2}+\left\|F^{\kappa-1}_{w_{2}}\right\|_{2}\left\|G^{\kappa}_{w_{1}}-G^{\kappa}_{w_{2}}\right\|_{2}$
$\displaystyle\leq\frac{C^{\kappa}_{G}}{(\lambda^{\kappa}_{F})^{2}}\left\|F^{\kappa}_{w_{1}}-F^{\kappa}_{w_{2}}\right\|_{2}+\frac{1}{\lambda^{\kappa}_{F}}\left\|G^{\kappa}_{w_{1}}-G^{\kappa}_{w_{2}}\right\|_{2}$
$\displaystyle\leq\frac{C^{\kappa}_{G}L^{\kappa}_{F}+\lambda^{\kappa}_{F}L^{\kappa}_{G}}{(\lambda^{\kappa}_{F})^{2}}\left\|w_{1}-w_{2}\right\|_{2}=L_{\rho}\left\|w_{1}-w_{2}\right\|_{2},$
(66)

where
$L_{\rho}=\frac{C^{\kappa}_{G}L^{\kappa}_{F}+\lambda^{\kappa}_{F}L^{\kappa}_{G}}{(\lambda^{\kappa}_{F})^{2}}$.

We then consider the Lipschitz property of $\theta^{*}_{q}$. To bound
$\left\|\theta^{*}_{q,w_{1}}-\theta^{*\top}_{q,w_{2}}\right\|_{2}$, we proceed
as follows.

$\displaystyle\theta^{*}_{q,w_{1}}-\theta^{*}_{q,w_{2}}$
$\displaystyle=C^{\kappa-1}_{w_{1}}(E^{\kappa}_{w_{1}}-A^{\kappa}_{w_{1}}\theta^{*}_{\rho,w_{1}})-C^{\kappa-1}_{w_{2}}(E^{\kappa}_{w_{2}}-A^{\kappa}_{w_{2}}\theta^{*}_{\rho,w_{2}})$
$\displaystyle=(C^{\kappa-1}_{w_{1}}-C^{\kappa-1}_{w_{2}})(E^{\kappa}_{w_{1}}-A^{\kappa}_{w_{1}}\theta^{*}_{\rho,w_{1}})+C^{\kappa-1}_{w_{2}}(E^{\kappa}_{w_{1}}-E^{\kappa}_{w_{2}}+A^{\kappa}_{w_{2}}\theta^{*}_{\rho,w_{2}}-A^{\kappa}_{w_{1}}\theta^{*}_{\rho,w_{1}})$
$\displaystyle=C^{\kappa-1}_{w_{1}}(C^{\kappa}_{w_{2}}-C^{\kappa}_{w_{1}})C^{\kappa-1}_{w_{2}}(E^{\kappa}_{w_{1}}-A^{\kappa}_{w_{1}}\theta^{*}_{\rho,w_{1}})$
$\displaystyle\quad+C^{\kappa-1}_{w_{2}}\left[(E^{\kappa}_{w_{1}}-E^{\kappa}_{w_{2}})+A^{\kappa}_{w_{2}}(\theta^{*}_{\rho,w_{2}}-\theta^{*}_{\rho,w_{1}})+(A^{\kappa}_{w_{2}}-A^{\kappa}_{w_{1}})\theta^{*}_{\rho,w_{1}}\right],$

which implies

$\displaystyle\left\|\theta^{*}_{q,w_{1}}-\theta^{*}_{q,w_{2}}\right\|_{2}$
$\displaystyle\leq\left\|C^{\kappa-1}_{w_{1}}\right\|_{2}\left\|C^{\kappa}_{w_{2}}-C^{\kappa}_{w_{1}}\right\|_{2}\left\|C^{\kappa-1}_{w_{2}}\right\|_{2}\left(\left\|E^{\kappa}_{w_{1}}\right\|_{2}+\left\|A^{\kappa}_{w_{1}}\right\|_{2}\left\|\theta^{*}_{\rho,w_{1}}\right\|_{2}\right)$
$\displaystyle\quad+\left\|C^{\kappa-1}_{w_{2}}\right\|_{2}\left[\left\|E^{\kappa}_{w_{1}}-E^{\kappa}_{w_{2}}\right\|_{2}+\left\|A^{\kappa}_{w_{2}}\right\|_{2}\left\|\theta^{*}_{\rho,w_{2}}-\theta^{*}_{\rho,w_{1}}\right\|_{2}+\left\|A^{\kappa}_{w_{2}}-A^{\kappa}_{w_{1}}\right\|_{2}\left\|\theta^{*}_{\rho,w_{1}}\right\|_{2}\right]$
$\displaystyle\leq\left[\frac{L^{\kappa}_{C}(C^{\kappa}_{E}+C^{\kappa}_{A}R_{\rho})+\lambda^{\kappa}_{C}(L^{\kappa}_{E}+C^{\kappa}_{A}L\rho+L^{\kappa}_{A}R_{\rho})}{(\lambda^{\kappa}_{C})^{2}}\right]\left\|w_{1}-w_{2}\right\|_{2}=L_{q}\left\|w_{1}-w_{2}\right\|_{2},$

where
$L_{q}=\frac{L^{\kappa}_{C}(C^{\kappa}_{E}+C^{\kappa}_{A}R_{\rho})+\lambda^{\kappa}_{C}(L^{\kappa}_{E}+C^{\kappa}_{A}L\rho+L^{\kappa}_{A}R_{\rho})}{(\lambda^{\kappa}_{C})^{2}}$.

Finally, we consider the Lipschitz property of $\eta^{*}$. To bound
$\left\|\eta^{*}_{w_{1}}-\eta^{*}_{w_{2}}\right\|_{2}$, we proceed as follows

$\displaystyle\left\|\eta^{*}_{w_{1}}-\eta^{*}_{w_{2}}\right\|_{2}$
$\displaystyle=\left\|D^{\kappa}_{w_{1}}\theta^{*}_{\rho,w_{1}}-D^{\kappa}_{w_{2}}\theta^{*}_{\rho,w_{2}}\right\|_{2}$
$\displaystyle=\left\|D^{\kappa}_{w_{1}}(\theta^{*}_{\rho,w_{1}}-\theta^{*}_{\rho,w_{2}})+(D^{\kappa}_{w_{1}}-D^{\kappa}_{w_{2}})\theta^{*}_{\rho,w_{2}}\right\|_{2}$
$\displaystyle\leq\left\|D^{\kappa}_{w_{1}}(\theta^{*}_{\rho,w_{1}}-\theta^{*}_{\rho,w_{2}})\right\|_{2}+\left\|(D^{\kappa}_{w_{1}}-D^{\kappa}_{w_{2}})\theta^{*}_{\rho,w_{2}}\right\|_{2}$
$\displaystyle\leq(C^{\kappa}_{D}L_{\rho}+L^{\kappa}_{D}R_{\rho})\left\|w_{1}-w_{2}\right\|_{2}=L_{\eta}\left\|w_{1}-w_{2}\right\|_{2},$
(67)

where $L_{\eta}=C^{\kappa}_{D}L_{\rho}+L^{\kappa}_{D}R_{\rho}$. ∎

######  Lemma 5.

Consider the policies $\pi_{w_{1}}$ and $\pi_{w_{2}}$, respectively, with the
fixed points $\xi^{*}_{1}$ and $\xi^{*}_{2}$ defined in eq. 60. We have

$\displaystyle\left\|\xi^{*}_{1}-\xi^{*}_{2}\right\|_{2}\leq
L_{\xi}\left\|w_{1}-w_{2}\right\|_{2},$

where
$L_{\xi}=\frac{2C^{2}_{\varphi}C^{\xi}_{b}L_{\pi}+\lambda^{\xi}_{A}C_{\varphi}(C_{sc}L_{\pi}+L_{sc})}{(\lambda^{\xi}_{A})^{2}}$.

###### Proof.

Recall that for $k=1$ or $2$, we have
$\xi^{*}_{k}=P^{-1}_{k}p_{k}=[\theta^{*\top}_{\psi,w_{k}},0^{\top}]^{\top}$,
where $\theta^{*\top}_{\psi,w_{k}}=A^{\xi-1}_{w_{k}}b^{\xi}_{w_{k}}$, with
$A^{\xi}_{w}=\mathbb{E}_{\tilde{\mathcal{D}}_{d}\cdot\pi_{w}}[(\varphi-\varphi^{\prime})\varphi^{\prime\top}]$
and
$b^{\xi}_{w}=\mathbb{E}_{\tilde{\mathcal{D}}_{d}\cdot\pi_{w}}[\varphi^{\prime}\nabla_{w}\log\pi_{w}(a^{\prime}|{s}^{\prime})]$,
which implies that

$\displaystyle\left\|\xi^{*}_{1}-\xi^{*}_{2}\right\|_{2}=\left\|\theta^{*\top}_{\psi,w_{1}}-\theta^{*\top}_{\psi,w_{2}}\right\|_{2}.$

To bound
$\left\|\theta^{*\top}_{\psi,w_{1}}-\theta^{*\top}_{\psi,w_{2}}\right\|_{2}$,
following the steps similar to those in eq. 65 and eq. 66, we obtain

$\displaystyle\left\|\theta^{*\top}_{\psi,w_{1}}-\theta^{*\top}_{\psi,w_{2}}\right\|_{2}\leq\frac{C^{\xi}_{b}}{(\lambda^{\xi}_{A})^{2}}\left\|A^{\xi}_{w_{1}}-A^{\xi}_{w_{2}}\right\|_{2}+\frac{1}{\lambda^{\xi}_{A}}\left\|b^{\xi}_{w_{1}}-b^{\xi}_{w_{2}}\right\|_{2}.$
(68)

We first bound the term $\left\|A^{\xi}_{w_{2}}-A^{\xi}_{w_{1}}\right\|_{2}$.
Following the steps similar to those in eq. 61, we obtain

$\displaystyle\left\|A^{\xi}_{w_{2}}-A^{\xi}_{w_{1}}\right\|_{2}\leq
2C^{2}_{\varphi}L_{\pi}\left\|w_{1}-w_{2}\right\|_{2}.$ (69)

We then bound the term $\left\|b^{\xi}_{w_{1}}-b^{\xi}_{w_{2}}\right\|_{2}$.
Based on the definition of $b^{\xi}_{w}$, we have

$\displaystyle\left\|b^{\xi}_{w_{1}}-b^{\xi}_{w_{2}}\right\|_{2}$
$\displaystyle=\left\|\mathbb{E}_{\tilde{\mathcal{D}}_{d}\cdot\pi_{w_{1}}}[\varphi^{\prime}\nabla_{w}\log\pi_{w_{1}}(a^{\prime}|{s}^{\prime})]-\mathbb{E}_{\tilde{\mathcal{D}}_{d}\cdot\pi_{w_{2}}}[\varphi^{\prime}\nabla_{w}\log\pi_{w_{2}}(a^{\prime}|{s}^{\prime})]\right\|_{2}$
$\displaystyle\leq\left\|\mathbb{E}_{\tilde{\mathcal{D}}_{d}\cdot\pi_{w_{1}}}[\varphi^{\prime}\nabla_{w}\log\pi_{w_{1}}(a^{\prime}|{s}^{\prime})]-\mathbb{E}_{\tilde{\mathcal{D}}_{d}\cdot\pi_{w_{2}}}[\varphi^{\prime}\nabla_{w}\log\pi_{w_{1}}(a^{\prime}|{s}^{\prime})]\right\|_{2}$
$\displaystyle\quad+\left\|\mathbb{E}_{\tilde{\mathcal{D}}_{d}\cdot\pi_{w_{2}}}[\varphi^{\prime}\nabla_{w}\log\pi_{w_{1}}(a^{\prime}|{s}^{\prime})]-\mathbb{E}_{\tilde{\mathcal{D}}_{d}\cdot\pi_{w_{2}}}[\varphi^{\prime}\nabla_{w}\log\pi_{w_{2}}(a^{\prime}|{s}^{\prime})]\right\|_{2}$
$\displaystyle=\left\|\int\varphi(s^{\prime},a^{\prime})\nabla_{w}\log\pi_{w_{1}}(a^{\prime}|{s}^{\prime})(\pi_{w_{1}}(da^{\prime}|s^{\prime})-\pi_{w_{2}}(da^{\prime}|s^{\prime}))\tilde{\mathsf{P}}(ds^{\prime}|s,a)\mathcal{D}(ds,da)\right\|_{2}$
$\displaystyle\quad+\left\|\int\varphi(s^{\prime},a^{\prime})(\nabla_{w}\log\pi_{w_{1}}(a^{\prime}|{s}^{\prime})-\nabla_{w}\log\pi_{w_{2}}(a^{\prime}|{s}^{\prime}))\pi_{w_{2}}(da^{\prime}|s^{\prime})\tilde{\mathsf{P}}(ds^{\prime}|s,a)\mathcal{D}(ds,da)\right\|_{2}$
$\displaystyle=\int\left\|\varphi(s^{\prime},a^{\prime})\nabla_{w}\log\pi_{w_{1}}(a^{\prime}|{s}^{\prime})\right\|_{2}\left|\pi_{w_{1}}(da^{\prime}|s^{\prime})-\pi_{w_{2}}(da^{\prime}|s^{\prime})\right|\tilde{\mathsf{P}}(ds^{\prime}|s,a)\mathcal{D}(ds,da)$
$\displaystyle\quad+\int\left\|\varphi(s^{\prime},a^{\prime})\right\|_{2}\left\|\nabla_{w}\log\pi_{w_{1}}(a^{\prime}|{s}^{\prime})-\nabla_{w}\log\pi_{w_{2}}(a^{\prime}|{s}^{\prime})\right\|_{2}\pi_{w_{2}}(da^{\prime}|s^{\prime})\tilde{\mathsf{P}}(ds^{\prime}|s,a)\mathcal{D}(ds,da)$
$\displaystyle\leq
C_{\varphi}C_{sc}\int\left|\pi_{w_{1}}(da^{\prime}|s^{\prime})-\pi_{w_{2}}(da^{\prime}|s^{\prime})\right|\tilde{\mathsf{P}}(ds^{\prime}|s,a)\mathcal{D}(ds,da)+C_{\varphi}L_{sc}\left\|w_{1}-w_{2}\right\|_{2}$
$\displaystyle\leq
C_{\varphi}(C_{sc}L_{\pi}+L_{sc})\left\|w_{1}-w_{2}\right\|_{2}.$ (70)

Substituting eq. 69 and eq. 70 into eq. 66 yields

$\displaystyle\left\|\theta^{*\top}_{\psi,w_{1}}-\theta^{*\top}_{\psi,w_{2}}\right\|_{2}\leq\frac{2C^{2}_{\varphi}C^{\xi}_{b}L_{\pi}+\lambda^{\xi}_{A}C_{\varphi}(C_{sc}L_{\pi}+L_{sc})}{(\lambda^{\xi}_{A})^{2}}\left\|w_{1}-w_{2}\right\|_{2}=L_{\xi}\left\|w_{1}-w_{2}\right\|_{2}.$

Thus, we have $\left\|\xi^{*}_{1}-\xi^{*}_{2}\right\|_{2}\leq
L_{\xi}\left\|w_{1}-w_{2}\right\|_{2}$, which completes the proof. ∎

######  Lemma 6.

Consider the policies $\pi_{w_{1}}$ and $\pi_{w_{2}}$, respectively, with the
fixed points $\zeta^{*}_{1}$ and $\zeta^{*}_{2}$ defined in eq. 50. Then, we
have

$\displaystyle\left\|\zeta^{*}_{1}-\zeta^{*}_{2}\right\|_{2}\leq
L_{\zeta}\left\|w_{1}-w_{2}\right\|_{2},$

where
$L_{\zeta}=\frac{2C^{2}_{x}L_{\pi}C^{\zeta}_{b}+\lambda^{\zeta}_{A}C_{\phi}C_{x}(R_{q}L_{sc}+L_{q}C_{sc})+\lambda^{\zeta}_{A}C_{\phi}R_{q}C_{x}C_{sc}L_{\pi}}{(\lambda^{\zeta}_{A})^{2}}$.

###### Proof.

Recall that for $k=1$ or $2$, we have
$\zeta^{*}_{k}=U^{-1}_{k}u_{k}(\theta^{*}_{q,k})=[\theta^{*\top}_{d_{q},k},0^{\top}]^{\top}$,
where $\theta^{*\top}_{d_{q},w_{k}}=A^{\zeta-1}_{w_{k}}b^{\zeta}_{w_{k}}$,
with $A^{\zeta}_{w}=\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w}}[(\gamma
x(s^{\prime},a^{\prime})-x(s,a))x(s,a)^{\top}]$ and
$b^{\zeta}_{w}=\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w}}[\phi(s^{\prime},a^{\prime})^{\top}\theta^{*}_{q,w}x(s,a)\nabla_{w}\log\pi_{w}(a^{\prime}|s^{\prime})]$,
which implies that

$\displaystyle\left\|\zeta^{*}_{1}-\zeta^{*}_{2}\right\|_{2}=\left\|\theta^{*\top}_{d_{q},1}-\theta^{*\top}_{d_{q},2}\right\|_{2}.$

To bound
$\left\|\theta^{*\top}_{d_{q},1}-\theta^{*\top}_{d_{q},2}\right\|_{2}$,
following the steps similar to those in eq. 65 and eq. 66, we obtain

$\displaystyle\left\|\theta^{*\top}_{d_{q},1}-\theta^{*\top}_{d_{q},2}\right\|_{2}\leq\frac{C^{\zeta}_{b}}{(\lambda^{\zeta}_{A})^{2}}\left\|A^{\zeta}_{w_{1}}-A^{\zeta}_{w_{2}}\right\|_{2}+\frac{1}{\lambda^{\zeta}_{A}}\left\|b^{\zeta}_{w_{1}}-b^{\zeta}_{w_{2}}\right\|_{2}.$
(71)

We first bound the term
$\left\|A^{\zeta}_{w_{1}}-A^{\zeta}_{w_{2}}\right\|_{2}$. Following the steps
similar to those in eq. 61, we obtain

$\displaystyle\left\|A^{\zeta}_{w_{1}}-A^{\zeta}_{w_{2}}\right\|_{2}\leq
2C^{2}_{x}L_{\pi}\left\|w_{1}-w_{2}\right\|_{2}.$ (72)

We then bound the term
$\left\|b^{\zeta}_{w_{1}}-b^{\zeta}_{w_{2}}\right\|_{2}$. Based on to the
definition of $b^{\zeta}_{w}$, we have

$\displaystyle\left\|b^{\zeta}_{w_{1}}-b^{\zeta}_{w_{2}}\right\|_{2}$
$\displaystyle=\left\|\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{1}}}[\phi(s^{\prime},a^{\prime})^{\top}\theta^{*}_{q,w_{1}}x(s,a)\nabla_{w}\log\pi_{w_{1}}(a^{\prime}|s^{\prime})]-\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{2}}}[\phi(s^{\prime},a^{\prime})^{\top}\theta^{*}_{q,w_{2}}x(s,a)\nabla_{w}\log\pi_{w_{2}}(a^{\prime}|s^{\prime})]\right\|_{2}$
$\displaystyle\leq\left\|\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{1}}}[\phi(s^{\prime},a^{\prime})^{\top}\theta^{*}_{q,w_{1}}x(s,a)\nabla_{w}\log\pi_{w_{1}}(a^{\prime}|s^{\prime})]-\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{2}}}[\phi(s^{\prime},a^{\prime})^{\top}\theta^{*}_{q,w_{1}}x(s,a)\nabla_{w}\log\pi_{w_{1}}(a^{\prime}|s^{\prime})]\right\|_{2}$
$\displaystyle\quad+\left\|\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{2}}}[\phi(s^{\prime},a^{\prime})^{\top}\theta^{*}_{q,w_{1}}x(s,a)\nabla_{w}\log\pi_{w_{1}}(a^{\prime}|s^{\prime})]-\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{2}}}[\phi(s^{\prime},a^{\prime})^{\top}\theta^{*}_{q,w_{2}}x(s,a)\nabla_{w}\log\pi_{w_{2}}(a^{\prime}|s^{\prime})]\right\|_{2}$
$\displaystyle\leq\left\|\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{2}}}[\phi(s^{\prime},a^{\prime})^{\top}\theta^{*}_{q,w_{1}}x(s,a)\nabla_{w}\log\pi_{w_{1}}(a^{\prime}|s^{\prime})]-\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{2}}}[\phi(s^{\prime},a^{\prime})^{\top}\theta^{*}_{q,w_{2}}x(s,a)\nabla_{w}\log\pi_{w_{2}}(a^{\prime}|s^{\prime})]\right\|_{2}$
$\displaystyle\quad+C_{\phi}R_{q}C_{x}C_{sc}L_{\pi}\left\|w_{1}-w_{2}\right\|_{2}.$
(73)

Consider the term

$\displaystyle\left\|\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{2}}}[\phi(s^{\prime},a^{\prime})^{\top}\theta^{*}_{q,w_{1}}x(s,a)\nabla_{w}\log\pi_{w_{1}}(a^{\prime}|s^{\prime})]-\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{2}}}[\phi(s^{\prime},a^{\prime})^{\top}\theta^{*}_{q,w_{2}}x(s,a)\nabla_{w}\log\pi_{w_{2}}(a^{\prime}|s^{\prime})]\right\|_{2},$

we have

$\displaystyle\left\|\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{2}}}[\phi(s^{\prime},a^{\prime})^{\top}\theta^{*}_{q,w_{1}}x(s,a)\nabla_{w}\log\pi_{w_{1}}(a^{\prime}|s^{\prime})]-\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{2}}}[\phi(s^{\prime},a^{\prime})^{\top}\theta^{*}_{q,w_{2}}x(s,a)\nabla_{w}\log\pi_{w_{2}}(a^{\prime}|s^{\prime})]\right\|_{2}$
$\displaystyle\leq\left\|\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{2}}}[\phi(s^{\prime},a^{\prime})^{\top}\theta^{*}_{q,w_{1}}x(s,a)(\nabla_{w}\log\pi_{w_{1}}(a^{\prime}|s^{\prime})-\nabla_{w}\log\pi_{w_{2}}(a^{\prime}|s^{\prime}))]\right\|_{2}$
$\displaystyle\quad+\left\|\mathbb{E}_{\mathcal{D}_{d}\cdot\pi_{w_{2}}}[\phi(s^{\prime},a^{\prime})^{\top}(\theta^{*}_{q,w_{1}}-\theta^{*}_{q,w_{2}})x(s,a)\nabla_{w}\log\pi_{w_{2}}(a^{\prime}|s^{\prime})]\right\|_{2}$
$\displaystyle\overset{(i)}{\leq}C_{\phi}C_{x}(R_{q}L_{sc}+L_{q}C_{sc})\left\|w_{1}-w_{2}\right\|_{2},$
(74)

where $(i)$ follows from the Lipschitz property of $\theta^{*}_{q,w}$ given in
Lemma 4. Combining eq. 61, eq. 73, eq. 74 and eq. 71 yields

$\displaystyle\left\|\theta^{*\top}_{d_{q},w_{1}}-\theta^{*\top}_{d_{q},w_{2}}\right\|_{2}\leq\frac{2C^{2}_{x}L_{\pi}C^{\zeta}_{b}+\lambda^{\zeta}_{A}C_{\phi}C_{x}(R_{q}L_{sc}+L_{q}C_{sc})+\lambda^{\zeta}_{A}C_{\phi}R_{q}C_{x}C_{sc}L_{\pi}}{(\lambda^{\zeta}_{A})^{2}}\left\|w_{1}-w_{2}\right\|_{2}=L_{\zeta}\left\|w_{1}-w_{2}\right\|_{2}.$

Thus we have $\left\|\zeta^{*}_{1}-\zeta^{*}_{2}\right\|_{2}\leq
L_{\zeta}\left\|w_{1}-w_{2}\right\|_{2}$, which completes the proof. ∎

######  Lemma 7.

Define
$\Delta_{t}=\left\|\kappa_{t}-\kappa_{t}^{*}\right\|_{2}^{2}+\left\|\xi_{t}-\xi^{*}_{t}\right\|_{2}^{2}+\left\|\zeta_{t}-\zeta^{*}_{t}\right\|_{2}^{2}$.
Then, we have

$\displaystyle\mathbb{E}[\Delta_{t+1}|\mathcal{F}_{t}]\leq\left(1-\frac{1}{2}\varrho\right)\Delta_{t}+\frac{2}{\varrho}(L^{2}_{\kappa}+L^{2}_{\xi}+L^{2}_{\zeta})\mathbb{E}[\left\|w_{t+1}-w_{t}\right\|_{2}^{2}|\mathcal{F}_{t}]+\frac{C_{5}}{(1-\varrho)N},$

where
$\varrho=\frac{1}{4}\min\\{\beta_{1}\lambda_{M},\beta_{2}\lambda_{P},\beta_{3}\lambda_{U}\\}$
and $C_{5}=C_{1}+C_{2}+C_{4}$, where $C_{1}$, $C_{2}$ and $C_{4}$ are defined
in Lemma 1, Lemma 2, and Lemma 3.

###### Proof.

Following from the iteration property developed in Lemma 1, Lemma 2, and Lemma
3, we have

$\displaystyle\mathbb{E}\left[\left\|\kappa_{t+1}-\kappa^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]$
$\displaystyle\leq\left(1-\frac{1}{2}\beta_{1}\lambda_{M}\right)\left\|\kappa_{t}-\kappa^{*}_{t}\right\|_{2}^{2}+\frac{C_{1}}{N},$
(75)
$\displaystyle\mathbb{E}\left[\left\|\xi_{t+1}-\xi^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]$
$\displaystyle\leq\left(1-\frac{1}{2}\beta_{2}\lambda_{P}\right)\left\|\xi_{t}-\xi^{*}_{t}\right\|_{2}^{2}+\frac{C_{2}}{N},$
(76)
$\displaystyle\mathbb{E}\left[\left\|\zeta_{t+1}-\zeta^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]$
$\displaystyle\leq\left(1-\frac{1}{4}\beta_{3}\lambda_{U}\right)\left\|\zeta_{t}-\zeta^{*}_{t}\right\|_{2}^{2}+C_{3}\beta_{3}\left\|\theta_{q,t}-\theta^{*}_{q,t}\right\|_{2}^{2}+\frac{C_{4}}{N}$
$\displaystyle\leq\left(1-\frac{1}{4}\beta_{3}\lambda_{U}\right)\left\|\zeta_{t}-\zeta^{*}_{t}\right\|_{2}^{2}+C_{3}\beta_{3}\left\|\kappa_{t}-\kappa^{*}_{t}\right\|_{2}^{2}+\frac{C_{4}}{N}.$
(77)

Summarizing eq. 75, eq. 76 and eq. 77, we obtain

$\displaystyle\mathbb{E}\left[\left\|\kappa_{t+1}-\kappa^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]+\mathbb{E}\left[\left\|\xi_{t+1}-\xi^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]+\mathbb{E}\left[\left\|\zeta_{t+1}-\zeta^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]$
$\displaystyle\leq\left(1-\frac{1}{2}\beta_{1}\lambda_{M}+C_{3}\beta_{3}\right)\left\|\kappa_{t}-\kappa^{*}_{t}\right\|_{2}^{2}+\left(1-\frac{1}{2}\beta_{2}\lambda_{P}\right)\left\|\xi_{t}-\xi^{*}_{t}\right\|_{2}^{2}+\left(1-\frac{1}{4}\beta_{3}\lambda_{U}\right)\left\|\zeta_{t}-\zeta^{*}_{t}\right\|_{2}^{2}+\frac{C_{1}+C_{2}+C_{4}}{N}.$

Let $\beta_{3}\leq\frac{\beta_{1}\lambda_{M}}{4C_{3}}$ and define
$\varrho=\frac{1}{4}\min\\{\beta_{1}\lambda_{M},\beta_{2}\lambda_{P},\beta_{3}\lambda_{U}\\}$,
$C_{5}=C_{1}+C_{2}+C_{4}$. Then, we have

$\displaystyle\mathbb{E}\left[\left\|\kappa_{t+1}-\kappa^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]+\mathbb{E}\left[\left\|\xi_{t+1}-\xi^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]+\mathbb{E}\left[\left\|\zeta_{t+1}-\zeta^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]$
$\displaystyle\leq(1-\varrho)\left(\left\|\kappa_{t}-\kappa^{*}_{t}\right\|_{2}^{2}+\left\|\xi_{t}-\xi^{*}_{t}\right\|_{2}^{2}+\left\|\zeta_{t}-\zeta^{*}_{t}\right\|_{2}^{2}\right)+\frac{C_{5}}{N}.$
(78)

We then proceed to investigate the iteration of $\Delta_{t}$. By Young’s
inequality, we have

$\displaystyle\Delta_{t+1}$
$\displaystyle\leq\left(\frac{2-\varrho}{2-2\varrho}\right)\left(\mathbb{E}\left[\left\|\kappa_{t+1}-\kappa^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]+\mathbb{E}\left[\left\|\xi_{t+1}-\xi^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]+\mathbb{E}\left[\left\|\zeta_{t+1}-\zeta^{*}_{t}\right\|_{2}^{2}|\mathcal{F}_{t}\right]\right)$