# Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm

Sajad Khodadadianlabel=e2 [<EMAIL_ADDRESS>Zaiwei Chenlabel=e1 [
<EMAIL_ADDRESS>Siva Theja Magulurilabel=e3 [
<EMAIL_ADDRESS>Geogia Institute of Technology,

###### Abstract

In this paper, we provide finite-sample convergence guarantees for an off-
policy variant of the natural actor-critic (NAC) algorithm based on Importance
Sampling. In particular, we show that the algorithm converges to a global
optimal policy with a sample complexity of
$\mathcal{O}(\epsilon^{-3}\log^{2}(1/\epsilon))$ under an appropriate choice
of stepsizes. In order to overcome the issue of large variance due to
Importance Sampling, we propose the $Q$-trace algorithm for the critic, which
is inspired by the V-trace algorithm [24]. This enables us to explicitly
control the bias and variance, and characterize the trade-off between them. As
an advantage of off-policy sampling, a major feature of our result is that we
do not need any additional assumptions, beyond the ergodicity of the Markov
chain induced by the behavior policy.

, , and

††Equal contribution between Zaiwei Chen and Sajad Khodadadian

##  1 Introduction

Reinforcement Learning (RL) is a paradigm where an agent aims at maximizing
its cumulative reward by searching for an optimal policy, in an environment
modeled as a Markov Decision Process (MDP) [64]. RL algorithms have achieved
tremendous successes in a wide range of applications such as self-driving cars
with Deep Deterministic Policy Gradient (DDPG) [45], and AlphaGo in the game
of Go [61]. The algorithms in RL can be categorized into value space methods,
such as $Q$-learning [73], TD-learning [63], and policy space methods, such as
actor-critic (AC) [37]. Despite great empirical successes [72, 3], the finite-
sample convergence of AC type of algorithms are not completely characterized
theoretically.

An AC algorithm can be thought as a generalized policy iteration [57], and
consists of two phases, namely actor and critic. The objective of the actor is
to improve the policy, while the critic aims at evaluating the performance of
a specific policy. A step of the actor can be thought as a step of Stochastic
Gradient Ascent [16] with preconditioning. An identity pre-conditioner
corresponds to regular AC, while a pre-conditioning with fisher information
results in natural actor-critic (NAC) [54]. As for the critic, to perform a
policy evaluation step, it usually uses the TD-learning method and its
variants, such as TD$(0)$, or more generally, $n$-step TD [63]. Moreover, such
learning process can be done in an on or off-policy manner [23].

Off-policy Actor-Critic. In on-policy AC, the data samples are generated in an
online manner, always sampling based on the current policy at hand. In
contrast, in this paper, we focus on the off-policy AC, where the algorithm
updates the policy based on the data collected (possibly in the past) by a
fixed policy, called the behavior policy. Off-policy learning is inevitable in
high-stakes applications such as healthcare [22], education [49], robotics
[31] and clinical trials [47, 30]. The agent there may not have direct access
to the environment in order to perform online sampling, and one has to work
with limited historical data that is collected under a fixed behavior policy.
Moreover, off-policy AC enables off-line learning by decoupling data
collection from learning, and is observed to extract the maximum possible
utility out of limited available data [43].

To account for the difference between the behavior policy and the target
policy [28] in off-policy algorithms, a popular approach is to use Importance
Sampling (IS). The IS ratio, however, can be large in some cases, which might
result in high variance [29, 56]. This phenomenon will be illustrated in
detail in Section 2.3. In order to avoid such high variance, one idea is to
truncate the IS ratio [33], which leads to off-policy TD-learning algorithms
such as Retrace$(\lambda)$ [52] and V-trace [24].

Table 1: Summary of the results in the literature 1

Algorithm | Reference |  Sample  Complexity 2 |  Single trajectory | Comments
---|---|---|---|---
AC | [71] | $\tilde{\mathcal{O}}(\epsilon^{-6})$ | ✗ | Function Approx: Sample complexity to ensure $\mathbb{E}[\|\nabla V^{\pi_{t}}\|^{2}]\leq\epsilon+\mathcal{E}_{\text{bias}}$
[58] | $\tilde{\mathcal{O}}(\epsilon^{-4})$ | ✗
[38] | $\tilde{\mathcal{O}}(\epsilon^{-4})$ | ✗
NAC | [71] | $\tilde{\mathcal{O}}(\epsilon^{-14})$ | ✗ | Function Approx: Sample complexity to ensure $V^{\pi^{*}}-V^{\pi_{t}}\leq\epsilon+\mathcal{E}_{\text{bias}}$
[1] | $\tilde{\mathcal{O}}(\epsilon^{-6})$ | ✗
[36] | $\tilde{\mathcal{O}}(\epsilon^{-4})$ | ✓ | Tabular RL: Convergence to global optimum $V^{\pi^{*}}-V^{\pi_{t}}\leq\epsilon$
Off-Policy NAC | Our work | $\tilde{\mathcal{O}}(\epsilon^{-3})$ | ✓

1 There are two other related works [76] and [77]. [76] claims a sample
complexity of $\tilde{\mathcal{O}}(\epsilon^{-2})$ for NAC. [77] claims a
sample complexity of $\tilde{\mathcal{O}}(\epsilon^{-2.5})$ for AC and
$\tilde{\mathcal{O}}(\epsilon^{-4})$ for NAC. In our opinion, the
interpretation of the convergence results in terms of sample complexity in
both papers is incorrect. In case one accepts the interpretation in [76, 77],
our results imply a sample complexity of
$\tilde{\mathcal{O}}(\epsilon^{-1/N})$ for an arbitrary $N\in\mathbb{Z}^{+}$.
See Appendix C.1 for a detailed explanation. 2 In this table,
$\tilde{O}(\cdot)$ ignores all the logarithmic terms. See Appendix C.4 for
detailed calculations and comments regarding the sample complexities presented
here.

###  1.1 Main Contributions

In this paper, we study finite-sample convergence guarantees of an off-policy
variant of the NAC algorithm. Our main contributions are threefold.

$Q$-Trace for Off-Policy TD-Learning: Algorithm and Finite-Sample Bounds. To
estimate the $Q$-function for the critic, we propose an off-policy TD-learning
algorithm called $Q$-trace. This is inspired by the V-trace algorithm [24] to
estimate the $V$-function. We establish the finite-sample convergence bounds
of $Q$-trace, and show how the truncated IS ratios can be used to explicitly
trade-off the truncation bias and the variance.

Finite-Sample Bounds for Off-Policy NAC. Based on the $Q$-trace algorithm for
the critic, we propose an off-policy NAC algorithm, which uses only a single
trajectory of samples. To the best of our knowledge, we establish the first
known finite-sample convergence guarantees of an off-policy NAC algorithm.
Based on that, we show that in order to obtain an $\epsilon$-optimal policy,
the amount of samples required is of the size
$\mathcal{O}(\epsilon^{-3}\log^{2}(1/\epsilon))$. This shows that the off-
policy NAC outperforms even the best known theoretical convergence bounds of
on-policy NAC algorithms. See Table 1 for more details.

Exploration through Off-Policy Sampling. While off-policy learning is
primarily motivated by practical constraints, in this paper, we demonstrate
that off-policy sampling leads to natural exploration. By exploiting off-
policy sampling, we do not require either hard-to-verify assumptions made in
the literature to ensure exploration [76, 75], or additional exploration steps
in the algorithm that slow down the convergence [36].

###  1.2 Related Work

Two popular algorithms for finding the optimal policy of an MDP are value
iteration and policy iteration, which corresponds to $Q$-learning and AC in
Reinforcement Learning when the underlying model is unknown.

The $Q$-learning algorithm, first proposed in [73] is one of the most
celebrated value space methods for solving the RL problem [64]. Since the
proposal, there has been a long line of work to establish the convergence
properties of $Q$-learning. In particular, [67, 34, 9, 15, 13] characterize
the asymptotic convergence of $Q$-learning, [7, 8, 70, 18, 19] study the
finite-sample convergence bound in the mean-square sense, and [26, 44, 59]
study the high-probability convergence bounds.

In AC framework, usually the actor uses Policy Gradient (PG) to perform policy
update, and the critic uses TD-learning method to perform policy evaluation.

The PG method was shown to converge in [65, 6, 55, 32]. Natural PG, which is a
PG method with preconditioning, was proposed in [35]. More recently, there has
been a line of work to establish finite-sample convergence bound of (natural)
PG algorithm [25, 2, 27, 1, 71, 46, 60, 50, 17, 10].

TD-learning method, originally proposed in [63], represents a family of policy
evaluation algorithms in RL. The asymptotic convergence of TD-learning has
been established in [67, 34, 15]. Furthermore, the finite-sample convergence
bounds of TD-learning have been studied in [21, 39, 11, 62] in the on-policy
setting. Off-policy variants of TD-learning such as Retrace$(\lambda)$, Tree-
backup, and V-trace were studied in [52, 56, 24] respectively. Finite-sample
bounds for V-trace are quantified in [18, 19].

Actor-critic, as a stochastic variant of policy iteration, was proposed in [5,
14], and later it has extended to function approximation setting [37] and NAC
[54, 51, 66, 12]. Asymptotic convergence of AC algorithms was studied in [74,
37, 14, 13, 48, 78, 79]. Furthermore, there has been a flurry of recent work
studying the finite-sample convergence of AC and NAC [58, 38, 60, 71, 77, 76,
75, 36]. The results are summarized in Table 1. Concurrent work [41] studies a
variant of NAC with on-policy sampling and time-varying inverse temperature,
and obtains an $\tilde{\mathcal{O}}(\epsilon^{-2})$ sample complexity.

The rest of this paper is organized as follows. In Section 2, we first present
the $Q$-trace algorithm for off-policy TD-learning. We then use it with the
Natural Policy Gradient to get the off-policy NAC algorithm, and present the
finite-sample convergence bounds and sample complexity analysis. In Section 3,
we present the proof sketch of our main results, and conclude in Section 4.

##  2 Off-Policy Natural Actor-Critic: Algorithm and Finite-Sample Bounds

###  2.1 Background on Reinforcement Learning

We model our RL problem with an MDP which consists of a tuple of 5 elements
$(\mathcal{S},\mathcal{A},\mathcal{R},\mathcal{P},\gamma)$. Here $\mathcal{S}$
and $\mathcal{A}$ are finite sets of states and actions,
$\mathcal{R}:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ is the reward
function,
$\mathcal{P}:\mathcal{S}\times\mathcal{A}\rightarrow\Delta^{|\mathcal{S}|}$
(where $\Delta^{|\mathcal{S}|}$ is the probability simplex on
$\mathbb{R}^{|\mathcal{S}|}$) is the collection of transition probabilities
that are unknown, and $\gamma\in(0,1)$ is the discount factor.

The dynamics of an MDP is as follows. At each time step $k$, the system is at
some state $S_{k}$ of the environment. The agent chooses an action $A_{k}$
based on a policy $\pi$ at hand, $A_{k}\sim\pi(\cdot|S_{k})$, and the system
moves to a new state based on the transition probabilities
$\mathbb{P}(S_{k+1}=\cdot|S_{k},A_{k})$, and induces a one-step reward
$\mathcal{R}(S_{k},A_{k})$. The goal of the agent to find an optimal policy
which maximizes the cumulative reward. Specifically, the value function of a
policy $\pi$ is defined by
$V^{\pi}(\mu)=\mathbb{E}[\sum_{k=0}^{\infty}\gamma^{k}\mathcal{R}(S_{k},A_{k})|S_{0}\sim\mu,A_{k}\sim\pi(\cdot|S_{k})]$,
where $\mu$ is an initial distribution over states. Then the goal is to find
an optimal policy $\pi^{*}$ s.t.

$\displaystyle\pi^{*}\in\operatorname*{arg\,max}_{\pi\in\Pi}V^{\pi}(\mu),$ (1)

where $\Pi$ represents the set of all policies.

###  2.2 Natural Policy Gradient

Policy gradient algorithms aim at solving the optimization problem (1) by
using gradient ascent or its variants in the policy space. In particular, a
Mirror Descent (MD) [53] update of policy with stepsize $\beta$ reads as:

$\displaystyle\pi_{t+1}=\operatorname*{arg\,max}_{\pi\in\Pi}\left\\{\beta\langle\nabla
V^{\pi_{t}}(\mu),\pi-\pi_{t}\rangle-B(\pi,\pi_{t})\right\\},$ (2)

where $B(\cdot,\cdot)$ is an appropriately chosen Bregman divergence between
two policies. If we replace the Bregman divergence with
$B(\pi,\pi_{t})=\sum_{s}d_{\mu}^{\pi_{t}}(s)\mathcal{KL}(\pi(\cdot|s)|\pi_{t}(\cdot|s))$
in Eq. (2), we get the Natural Policy Gradient (NPG) algorithm for MDPs. Here
$d_{\mu}^{\pi}(s)=(1-\gamma)\sum_{j=0}^{\infty}\gamma^{j}\mathbb{P}^{\pi}(S_{j}=s\mid
S_{0}\sim\mu)$ is the discounted state visitation distribution [1], and
$\mathcal{KL}(\cdot\mid\cdot)$ stands for the KL-Divergence [20]. It has been
shown in [1] that the update equation (2) can be equivalently written as

$\displaystyle\pi_{t+1}(a|s)=\frac{\pi_{t}(a|s)\exp(\beta
Q^{\pi_{t}}(s,a))}{\sum_{a^{\prime}}\pi_{t}(a^{\prime}|s)\exp(\beta
Q^{\pi_{t}}(s,a^{\prime}))},\forall\;s,a,$ (3)

where
$Q^{\pi}(s,a)=\mathbb{E}_{\pi}[\sum_{k=0}^{\infty}\gamma^{k}\mathcal{R}(S_{k},A_{k})|S_{0}=s,A_{0}=a]$
is the $Q$-function for policy $\pi$ [57]. The update rule (3) can be
equivalently derived using the preconditioned gradient ascent (with the
Moore–Penrose inverse of the Fisher information matrix as the pre-conditioner)
on the dual space of the policy $\pi$. This interpretation of (3) was
presented in [35, 1]. Furthermore, an interpretation of (3) in terms of Mirror
Descent Modified Policy Iteration (MD-MPI) was presented in [27]. An important
result about the NPG is that, although the objective function of (1) is not
concave, it has been shown in [1] that the policies achieved by the MD update
of (3) converges to an optimal policy with rate $\mathcal{O}(1/t)$.

Algorithm 1 $Q$-Trace

1: Input: $K$, $\alpha$, $Q_{0}$, $\pi$, $\bar{\rho}$, and $\bar{c}$,
$\\{(S_{k},A_{k})\\}_{0\leq k\leq K+n}$ (generated by the behavior policy
$\pi_{b}$)

2: for $k=0,1,\cdots,K-1$ do

3: $\alpha_{k}(s,a)=\alpha\mathbb{I}_{\\{(s,a)=(S_{k},A_{k})\\}}$ for all
$(s,a)$

4:
$\Delta_{k,i}=\mathcal{R}(S_{i},A_{i})+\gamma\rho_{\pi}(S_{i+1},A_{i+1})Q_{k}(S_{i+1},A_{i+1})-Q_{k}(S_{i},A_{i})$
for all $k\leq i\leq k+n-1$

5:
$Q_{k+1}(s,a)=Q_{k}(s,a)+\alpha_{k}(s,a)\sum_{i=k}^{k+n-1}\gamma^{i-k}\prod_{j=k+1}^{i}c_{\pi}(S_{j},A_{j})\Delta_{k,i}$
for all $(s,a)$

6: end for

7: Output: $Q_{K}$

Although the convergence result in [1] is promising to find the optimal policy
in an MDP, since we do not have access to the transition probabilities and so
the $Q$-function in RL, we cannot update the policy according to Eq. (3).
Natural Actor-Critic (NAC) algorithm, which is a sample-based variant of the
update (3), proceeds as follows. In each iteration, first the critic generates
an estimate $Q_{t}$ of the $Q$-function $Q^{\pi_{t}}$. Then the actor updates
the policy according to Eq. (3) with $Q^{\pi_{t}}$ replaced by the estimate
$Q_{t}$.

###  2.3 The Q-Trace Algorithm for Off-Policy Prediction

In this section, we focus on the critic sub-problem, and develop the $Q$-trace
algorithm to estimate $Q^{\pi_{t}}$. $Q$-trace is an off-policy variant of TD-
learning based on Importance Sampling. Crucially, we introduce two different
truncation levels for the IS ratios in order to explicitly control the trade-
off between truncation bias and the variance. This is inspired by the V-trace
algorithm in [24].

We next introduce our notations to describe the $Q$-trace algorithm. Let $\pi$
be the target policy (i.e., we want to evaluate $Q^{\pi}$) and $\pi_{b}$ be
the behavior policy (i.e., we use $\pi_{b}$ to collect samples). We assume
that the behavior policy $\pi_{b}$ satisfies $\pi_{b}(a|s)>0$ for any $(s,a)$.
This is typically necessary in off-policy setting. Let $\bar{\rho}$ and
$\bar{c}$ be two truncation levels satisfying $\bar{\rho}\geq\bar{c}\geq 1$.
Define $c_{\pi}(s,a)=\min(\bar{c},\frac{\pi(a|s)}{\pi_{b}(a|s)})$ and
$\rho_{\pi}(s,a)=\min(\bar{\rho},\frac{\pi(a|s)}{\pi_{b}(a|s)})$ for all
$(s,a)$, which are the truncated IS ratios.

The off-policy $Q$-trace algorithm is presented in Algorithm 1. To better
understand Algorithm 1, consider the following special cases. Suppose we use
on-policy sampling, that is, $\pi_{b}=\pi$. Set $\bar{\rho}=\bar{c}=1$.
Observe that in this case we have $c_{\pi}(s,a)=\rho_{\pi}(s,a)=1$ for all
$(s,a)$. Then Algorithm 1 reduces to the regular $n$-step TD, which is known
to converge to $Q^{\pi}$ [67, 64].

In the off-policy setting (i.e., $\pi_{b}\neq\pi$), suppose we choose
$\bar{\rho}=\bar{c}\geq\max_{(s,a)}\frac{\pi(a|s)}{\pi_{b}(a|s)}$. Then we
have $c_{\pi}(s,a)=\rho_{\pi}(s,a)=\frac{\pi(a|s)}{\pi_{b}(a|s)}$, hence there
is essentially no truncation. In this case, Algorithm 1 corresponds to the
standard $n$-step TD using off-policy sampling, and therefore converges to
$Q^{\pi}$ [56].

A fundamental problem in off-policy TD is that the variance in the estimate
can be very large or even infinity [29, 52]. This is mainly because of the
product of IS ratios
$\prod_{j=k+1}^{i}\frac{\pi(A_{j}|S_{j})}{\pi_{b}(A_{j}|S_{j})}$. To have
control on the variance of the estimate, we introduce the truncation levels
$\bar{\rho}$ and $\bar{c}$. However, due to the truncation, the IS ratios are
now biased, and hence the algorithm no longer converges to the target value
function $Q^{\pi}$. In fact, Algorithm 1 converges to a biased limit point,
denoted by $Q^{\bar{\rho},\pi}$, which need not necessarily be the value
function of any policy.

Importantly, the limit point $Q^{\bar{\rho},\pi}$ depends only on the target
policy $\pi$ and the truncation level $\bar{\rho}$, but not on the truncation
level $\bar{c}$. Therefore, we can heavily truncate the IS ratio
$c_{\pi}(s,a)$ by using small $\bar{c}$ without affecting the limit point of
the $Q$-trace algorithm. In fact, as we will see in Section 2.5, this is
exactly what we should do. To quantify the truncation bias of Algorithm 1, we
have the following result.

######  Lemma 2.1.

For any $\bar{\rho}\geq 1$ and policy $\pi$, we have (1)
$\|Q^{\bar{\rho},\pi}-Q^{\pi}\|_{\infty}\leq\frac{\max_{(s,a)}\max(\pi(a|s)-\bar{\rho}\pi_{b}(a|s),0)}{(1-\gamma)^{2}}$,
and (2) $\|Q^{\bar{\rho},\pi}\|_{\infty}\leq\frac{1}{1-\gamma}$.

Observe from Lemma 2.1 (1) that when
$\bar{\rho}\geq\max_{s,a}\frac{\pi(a|s)}{\pi_{b}(a|s)}$, we have
$Q^{\bar{\rho},\pi}=Q^{\pi}$. This makes intuitive sense in that when
$\bar{\rho}$ is large, there is essentially no truncation in the IS ratio
$\rho_{\pi}(s,a)$, and we should not expect any truncation bias.

Comparison to Related Algorithms. There are two algorithms in the literature
that are closely related to our $Q$-trace algorithm, namely the
Retrace$(\lambda)$ in [52] and the V-trace in [24]. The Retrace$(\lambda)$
algorithm in [52] is proposed to evaluate the $Q$-function, but uses a single
truncation level. In contrast, we have two truncation levels $\bar{c}$ and
$\bar{\rho}$, which enables us to trade-off the truncation bias and variance.

V-trace, an off-policy variant of TD to estimate the $V$-function, first
introduced the idea of using two truncation levels. However, there are several
differences between $Q$-trace and V-trace. First, the product of the IS ratios
$c_{\pi}(S_{j},A_{j})$ starts from $j=k+1$ rather than $j=k$ in V-trace. This
simple but important modification enables us to get a convergence bound in
Theorem 2.1 which does not dependent on the target policy $\pi$. This is
essential for us to use the $Q$-trace algorithm in the AC framework, as after
each iteration of the actor, the critic receives a different policy $\pi_{t}$
to evaluate. Second, as opposed to V-trace, where the limit point is a value
function of some policy, the limit point $Q^{\bar{\rho},\pi}$ of $Q$-trace is
not necessarily the $Q$-function of any policy. Finally, due to the structure
of the $Q$-function, the IS ratio $\rho_{\pi}(S_{i+1},A_{i+1})$ is multiplied
with only one of the three terms in the temporal difference $\Delta_{k,i}$
(Algorithm 1 line 4), as opposed to all the three terms in V-trace.

In summary, we propose the off-policy $Q$-trace algorithm to evaluate the
$Q$-function in the critic. Moreover, the flexibility of choosing the
truncation levels in $Q$-trace enables us to explicitly trade-off the
truncation bias and the variance.

###  2.4 Off-Policy Natural Actor-Critic Algorithm

We are now ready to present our off-policy NAC algorithm 2. In iteration $t$,
the critic first estimates the $Q$-function $Q^{\pi_{t}}$ using the $Q$-trace
algorithm, which itself runs over $K$ iterations. Then the actor uses the
estimate $Q_{t+1}$ in Eq. (3) to perform a policy update. Thus, we have a two-
loop algorithm.

Algorithm 2 Off-Policy Natural Actor-Critic

1: Input: $T$, $K$, $\alpha$, $\beta$, $Q_{0}=\bm{0}$, $\pi_{0}$,
$\bar{\rho}$, $\bar{c}$, and $\\{(S_{k},A_{k})\\}_{0\leq k\leq T(K+n)}$ (a
single trajectory generated by the behavior policy $\pi_{b}$)

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

3: Critic update:

4: $\text{DataSet}=\\{(S_{i},A_{i})\\}_{t(K+n)\leq i\leq(t+1)(K+n)}$

5:
$Q_{t+1}=Q\text{-Trace}(K,\alpha,Q_{0},\pi_{t},\bar{c},\bar{\rho},\text{DataSet})$

6: Actor update:

7: $\pi_{t+1}(a|s)=\frac{\pi_{t}(a|s)\exp(\beta
Q_{t+1}(s,a))}{\sum_{a^{\prime}}\pi_{t}(a^{\prime}|s)\exp(\beta
Q_{t+1}(s,a^{\prime}))}$ $\forall\;(s,a)$

8: end for

9: Output: $\\{\pi_{t}\\}_{0\leq t\leq T-1}$

In Algorithm 2, due to off-policy sampling, the sampling process and the
learning process are decoupled, which allows the agent to learn in an off-line
manner [43]. Moreover, note that we are using a single trajectory of samples
$\\{(S_{k},A_{k})\\}_{0\leq k\leq T(K+n)}$ to perform the update. In related
literature [77, 76, 71], sampling needs to be often restarted with an
arbitrary initial state, which is not practical in many real-world
applications. See Appendix C.2 for more details.

###  2.5 Finite-Sample Convergence Guarantees

In this section, we present our main results about the finite-sample
convergence bounds of the $Q$-trace algorithm 1 for off-policy TD-learning,
and the off-policy NAC Algorithm 2. We begin by stating our one and only
assumption.

######  Assumption 2.1.

The Markov chain $\\{S_{k}\\}$ induced by $\pi_{b}$ is irreducible and
aperiodic.

Assumption 2.1 is commonly made in related work about RL algorithms with
Markovian sampling [68, 69, 48, 79], and it implies that the Markov chain
$\\{S_{k}\\}$ has a unique stationary distribution
$\mu_{b}\in\Delta^{|\mathcal{S}|}$. Moreover, since the state space
$\mathcal{S}$ is finite, there exist $C>0$ and $u\in(0,1)$ such that

$\|P^{k}(s,\cdot)-\mu_{b}(\cdot)\|_{\text{TV}}\leq Cu^{k}$

for any $k\geq 0$ and $s\in\mathcal{S}$, where $\|\cdot\|_{\text{TV}}$ is the
total variation distance [42].

A major issue in the design of AC algorithms is to ensure enough exploration
to all state-action pairs $(s,a)$. It was demonstrated in [36] that the
algorithm can get stuck in a local optimum if there is not enough exploration.
Sampling from a fixed policy that leads to an ergodic Markov chain naturally
ensures exploration, and so we do not need any additional assumptions. In
contrast, prior literature on the analysis of on-policy AC either makes
additional assumptions that are hard to satisfy [76, 75] or introduce an
additional exploration step in the algorithm [36] that slows the convergence.
See Appendix C.3 for more details.

To state our result, we need the following notation. Let
$\tau_{\alpha}=\min\\{k\geq
0:\max_{s\in\mathcal{S}}\|P^{k}(s,\cdot)-\mu_{b}(\cdot)\|_{\text{TV}}\leq\alpha\\}$,
where $\alpha$ is the constant stepsize used in the critic step of Algorithm
2. The quantity $\tau_{\alpha}$ can be viewed as the mixing time of the Markov
chain $\\{S_{k}\\}$ with accuracy $\alpha$. Furthermore, under the geometric
mixing property (implied by Assumption 2.1), the mixing time $\tau_{\alpha}$
can be bounded by $L(\log(1/\alpha)+1)$ for some constant $L>0$. Let
$f(\bar{c},\gamma)=\frac{1-(\gamma\bar{c})^{n}}{1-\gamma\bar{c}}$ when
$\gamma\bar{c}\neq 1$, and $=n$ when $\gamma\bar{c}=1$. Suppose the constant
stepsize $\alpha$ within the critic is properly chosen. The explicit condition
is given in Appendix A.3. Then we have the following result.

######  Theorem 2.1.

Consider $\\{Q_{k}\\}$ of Algorithm 1. Suppose that (1) Assumption 2.1 is
satisfied, (2) $Q_{0}$ is initiated at $\bm{0}$, and (3) the constant stepsize
$\alpha$ is chosen such that
$\alpha(\tau_{\alpha}+n+1)\leq\min\left(\frac{1}{12(\bar{\rho}+1)f(\bar{c},\gamma)},\frac{(1-\gamma_{c})^{2}}{8208(\bar{\rho}+1)^{2}f(\bar{c},\gamma)^{2}\log(|\mathcal{S}||\mathcal{A}|)}\right)$,
where $\gamma_{c}\in(0,1)$ (defined in Proposition 3.1 (3) (b)) does not
depend on the target policy $\pi$, Then we have for all
$k\geq\tau_{\alpha}+n+1$:

$\displaystyle\mathbb{E}[\|Q_{k}-Q^{\bar{\rho},\pi}\|_{\infty}^{2}]\leq\;$
$\displaystyle\underbrace{\frac{c_{1}}{(1-\gamma)^{2}}\left(1-\frac{1-\gamma_{c}}{2}\alpha\right)^{k-(\tau_{\alpha}+n+1)}}_{T_{1}:\text{Convergence
Bias}}$
$\displaystyle+\underbrace{\frac{c_{2}\log(|\mathcal{S}||\mathcal{A}|)}{(1-\gamma_{c})^{2}(1-\gamma)^{2}}(\bar{\rho}+1)^{2}f(\bar{c},\gamma)^{2}\alpha(\tau_{\alpha}+n+1),}_{T_{2}:\text{Convergence
Variance}}$

where $c_{1}$ and $c_{2}$ are numerical constants.

Observe that the RHS of the convergence bound does not depend on the target
policy $\pi$. This is important for us to later use Theorem 2.1 to show the
finite-sample guarantees of off-policy NAC algorithm 2.

This result characterizes the rate of convergence of $Q$-trace algorithm to
its stationary point, $Q^{\bar{\rho},\pi}$. The error on the RHS has two
terms, which are called bias and variance respectively in the SA literature
[18]. To contrast this with the bias due to truncation, we call it the
convergence bias. The second error term is simply called the variance. Theorem
2.1 implies that under an appropriate constant stepsize $\alpha$, while the
$Q$-trace algorithm achieves exponentially decaying convergence bias, it leads
to a constant variance that cannot be eliminated, and is of the size
$\mathcal{O}(\alpha\log(1/\alpha))$. The logarithmic factor is due to the
mixing time $\tau_{\alpha}$, which arises as a consequence of performing
Markovian sampling of $\\{(S_{k},A_{k})\\}$.

The following corollary provides the error of the estimate $Q_{k}$ with
respect to the true $Q$-function $Q^{\pi}$.

######  Corollary 2.1.1.

Under the same assumptions of Theorem 2.1, we have for all
$k\geq\tau_{\alpha}+n+1$

$\mathbb{E}\left[\|Q_{k}-Q^{\pi}\|_{\infty}\right]\leq\sqrt{T_{1}}+\sqrt{T_{2}}+\frac{\max(1-\bar{\rho}\min_{s,a}\pi_{b}(a|s),0)}{(1-\gamma)^{2}}$,
where the terms $T_{1}$ and $T_{2}$ are given in Theorem 2.1.

The proof of Corollary 2.1.1 immediately follows by combining Lemma 2.1 with
Theorem 2.1 and using Jensen’s inequality. We next present the finite-sample
bound of the off-policy NAC algorithm 2.

######  Theorem 2.2.

Consider $\\{\pi_{t}\\}$ generated by Algorithm 2. Suppose that Assumption 2.1
is satisfied, and $K\geq\tau_{\alpha}+n+1$. Then we have the following
performance bound:

$\displaystyle V^{\pi^{*}}(\mu)-\max_{0\leq t\leq
T-1}\mathbb{E}\left[V^{\pi_{t}}(\mu)\right]\leq\;$
$\displaystyle\underbrace{\frac{24}{(1-\gamma)^{3}}\left(1-\frac{1-\gamma_{c}}{2}\alpha\right)^{\frac{1}{2}(K-(\tau_{\alpha}+n+1))}}_{E_{1}:\text{Convergence
bias in the Critic}}$
$\displaystyle+\underbrace{\frac{1200\log^{1/2}(|\mathcal{S}||\mathcal{A}|)}{(1-\gamma)^{3}(1-\gamma_{c})}(\bar{\rho}+1)f(\bar{c},\gamma)[\alpha(\tau_{\alpha}+n+1)]^{1/2}}_{E_{2}:\text{Variance
in the Critic}}$
$\displaystyle+\underbrace{\frac{4\max(0,1-\bar{\rho}\min_{s,a}\pi_{b}(a|s))}{(1-\gamma)^{4}}}_{E_{3}:\text{Truncation
bias}}$
$\displaystyle+\underbrace{\frac{\log(e|\mathcal{A}|)}{(1-\gamma)^{2}\beta
T}}_{E_{4}:\text{Convergence error in the Actor}},$

The terms $E_{1}$ and $E_{2}$ correspond to the two terms on the RHS of the
convergence bounds in Theorem 2.1, and capture the convergence bias and the
variance in the critic estimate. We now focus on the terms $E_{3}$ and
$E_{4}$, and the trade-off between the variance $E_{2}$ and the truncation
bias $E_{3}$.

Error Due to Truncated IS Ratio. The term $E_{3}$ accounts for the error due
to introducing the truncation level $\bar{\rho}$ in the critic (i.e., the
$Q$-trace Algorithm 1). Recall that because of $\bar{\rho}$, the limit point
of the critic is $Q^{\bar{\rho},\pi_{t}}$ instead of $Q^{\pi_{t}}$. Note that
when $\bar{\rho}\geq 1/\min_{s,a}\pi_{b}(a|s)$ (which implies
$\bar{\rho}\geq\max_{s,a}\frac{\pi_{t}(a|s)}{\pi_{b}(a|s)}$ for any $t$),
there is essentially no truncation in the IS ratio $\rho_{\pi_{t}}(s,a)$, and
hence we have $E_{3}=0$, which agrees with Lemma 2.1.

Error Bound of the Actor. The term $E_{4}$ is due to the error in the actor
update. That is, $E_{4}$ would be the only error term we have if we can
directly use $Q^{\pi_{t}}$ in the actor update of Algorithm 2. Observe that
$E_{4}=\mathcal{O}(\frac{1}{T})$, which agrees with results in [1] [Theorem
5.3].

Bias-Variance Trade-Off. Recall that the motivation for introducing the
truncation levels $\bar{\rho}$ and $\bar{c}$ is to control the variance in the
critic estimate. We first consider the impact of $\bar{\rho}$. Observe that
the term $E_{3}$ is in favor of large $\bar{\rho}$ while the term $E_{2}$
grows linearly with respect to $\bar{\rho}$. Therefore, there is an explicit
trade-off between the variance and the truncation bias in choosing
$\bar{\rho}$. As a result, if we want to have convergence to the global
optimal, by choosing $\bar{\rho}=1/\min_{s,a}\pi_{b}(a|s)$, we introduce an
additional $1/\min_{s,a}\pi_{b}(a|s)$ factor in the variance term $E_{2}$.

The truncation level $\bar{c}$ appears only in the variance term $E_{2}$. In
view of the expression of $f(\bar{c},\gamma)$ (defined before Theorem 2.1), we
should choose $\bar{c}$ such that $\bar{c}\gamma<1$ to avoid an exponential
factor in the variance term. These observations are similar to [24, 18, 19],
where the V-trace algorithm is studied.

One drawback with Theorem 2.2 is that the error bound is stated in terms of
$\max_{0\leq t\leq T-1}\mathbb{E}[V^{\pi_{t}}(\mu)]$, while in practice we do
not know which policy among $\\{\pi_{t}\\}_{0\leq t\leq T-1}$ has the best
performance. To overcome this problem, using standard techniques in
optimization [40], we can obtain the following refined performance bound of
Algorithm 2.

######  Corollary 2.2.1.

Let $T^{\prime}$ be a random sample uniformly drawn from $\\{0,1,...,T-1\\}$.
Then we have the following performance guarantee on $\pi_{T^{\prime}}$:

$\displaystyle
V^{\pi^{*}}(\mu)-\mathbb{E}\left[V^{\pi_{T^{\prime}}}(\mu)\right]\leq
E_{1}+E_{2}+E_{3}+E_{4},$

where the terms $\\{E_{i}\\}_{1\leq i\leq 4}$ are given in Theorem 2.2.

The convergence guarantee in in Corollary 2.2.1 holds for the policy attained
by Algorithm 2 at a random point between $0$ and $T-1$. However, in practice
one usually takes the last policy achieved by the algorithm as the output.
Numerical experiments of off-policy NAC algorithm 2 in Figure 1 shows that in
expectation, the algorithm can converges almost monotonically. Theoretically
showing a performance bound for
$V^{\pi^{*}}(\mu)-\mathbb{E}\left[V^{\pi_{T-1}}(\mu)\right]$ is a future
direction of this work.

Figure 1: Convergence of Algorithm 2 on a 5 state, 3 action MDP. Each dashed
line is for one sample path of the algorithm, and the solid line is the
average of the 4 sample paths. See Appendix D for more details.

###  2.6 Sample Complexity Analysis

With Theorem 2.2 at hand, we now analyze the sample complexity of off-policy
NAC algorithm 2.

Sample Complexity for Global Optimum. Suppose that $\bar{\rho}\geq
1/\pi_{b,\min}$, where $\pi_{b,\min}:=\min_{s,a}\pi_{b}(a|s)$. In this case,
we have $E_{3}=0$, i.e., the bias due to truncation is eliminated, and hence
we have convergence to a global optimum. Theorem 2.2 implies the following
sample complexity result, whose proof is presented in Appendix B.3.

######  Corollary 2.2.2.

In order to obtain an $\epsilon$-optimal policy, the total number of samples
required (i.e., $TK$) is of the size

$\displaystyle\mathcal{O}(\epsilon^{-3}\log^{2}(1/\epsilon))\tilde{\mathcal{O}}((1-\gamma)^{-11}M_{\min}^{-3}\pi_{b,\min}^{-2}),$

where $M_{\min}=\min_{s,a}\mu_{b}(s)\pi_{b}(a|s)$.

The $\mathcal{O}(\epsilon^{-3}\log^{2}(1/\epsilon))$ dependence on the
accuracy $\epsilon$ advances the state of the art results in on-policy NAC.
See Table 1 for more details. The dependence on the state-action space is at
least $|\mathcal{S}|^{3}|\mathcal{A}|^{5}$, which is achieved when
$\pi_{b}(a|s)=\frac{1}{|\mathcal{A}|}$ for all $a$ and
$\mu_{b}(s)=\frac{1}{|\mathcal{S}|}$ for all $s$ (i.e., uniform exploration).
The $\mathcal{\tilde{O}}((1-\gamma)^{-11})$ dependence on the discount factor
while seemingly loose, agrees with known results about NPG in [1] (Corollary
6.3). See Appendix C.4 for more details about the comparison to [1].

Note that in off-policy TD-learning, one set of samples can be used multiple
times to evaluate different policies. Therefore, it is natural to consider
repeatedly using the same set of samples in the critic (the $Q$-trace
algorithm) in the off-policy NAC algorithm. In that case, the sample
complexity is reduced from $KT=\tilde{\mathcal{O}}(\epsilon^{-3})$ to only
$K=\tilde{\mathcal{O}}(\epsilon^{-2})$. Although this approach seems
reasonable, numerical experiments suggest that it may lead to the divergence
of Algorithm 2. See Appendix D for more details.

##  3 Proof Sketch of Our Main Results

In this section, we present the key steps in proving Theorems 2.1 and 2.2.

###  3.1 Proof Sketch of Theorem 2.1

To prove Theorem 2.1, we begin by introducing some notations. For any $k\geq
0$, let $X_{k}=(S_{k},A_{k},...,S_{k+n})$. It is clear that $\\{X_{k}\\}$ is a
Markov chain, whose state-space is denoted by $\mathcal{X}$. Moreover, under
Assumption 2.1, the Markov chain $\\{X_{k}\\}$ has a unique stationary
distribution, denoted by $\mu_{X}$. Let
$\mathcal{T}:\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}\times\Pi\times\mathcal{X}\mapsto\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$
be an operator defined by

$\displaystyle[\mathcal{T}(Q,\pi,x)](s,a)=[\mathcal{T}(Q,\pi,s_{0},a_{0},...,s_{n})](s,a)$
$\displaystyle=\;$
$\displaystyle\mathbb{I}_{(s,a)=(s_{0},a_{0})}\sum_{i=0}^{n-1}\gamma^{i}\prod_{j=1}^{i}c_{\pi}(s_{j},a_{j})(\mathcal{R}(s_{i},a_{i})+\gamma\rho_{\pi}(s_{i+1},a_{i+1})Q(s_{i+1},a_{i+1})-Q(s_{i},a_{i}))+Q(s,a)$

for all $(s,a)$. We further define
$\mathcal{T}_{e}:\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}\times\Pi\mapsto\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$
by $\mathcal{T}_{e}(Q,\pi)=\mathbb{E}_{X\sim\mu_{X}}\mathcal{T}(Q,\pi,X)$,
which can be viewed as the expected version of the operator $\mathcal{T}$.

Using the notation given above, the $Q$-trace update equation (Algorithm 1
line 5) can be equivalently written by

$\displaystyle Q_{k+1}=\;$ $\displaystyle
Q_{k}+\alpha(\mathcal{T}(Q_{k},\pi,X_{k})-Q_{k})$ (4) $\displaystyle=\;$
$\displaystyle
Q_{k}+\alpha(\mathcal{T}_{e}(Q_{k},\pi)-Q_{k})+\alpha(\mathcal{T}(Q_{k},\pi,X_{k})-\mathcal{T}_{e}(Q_{k},\pi))$
($*$)

The above update equation can be viewed as a stochastic approximation
algorithm for solving the fixed-point equation $\mathcal{T}_{e}(Q,\pi)=Q$ with
Markovian noise. To see this, assume for the moment that the term ($*$) is
identically zero. Then the Algorithm is the fixed-point iteration for solving
the equation $\mathcal{T}_{e}(Q,\pi)=Q$, and it is known to converge when the
operator $\mathcal{T}_{e}(\cdot,\pi)$ is a contraction mapping [4]. Now in the
presence of the term $(*)$, the algorithm becomes a Markovian stochastic
approximation algorithm for solving $\mathcal{T}_{e}(Q,\pi)=Q$.

Intuitively, once we show the desired contraction property of the operator
$\mathcal{T}_{e}(\cdot,\pi)$ and have control on the error caused by the
Markovian noise $(*)$, we should be able to establish the convergence bounds
of Algorithm (4). In order to show such properties, we need the following
notation.

  1. (1)

Let $\pi_{\bar{c}}$ and $\pi_{\bar{\rho}}$ be two policies defined by

$\displaystyle\pi_{\bar{c}}(a|s)=\frac{\min(\bar{c}\pi_{b}(a|s),\pi(a|s))}{\sum_{a^{\prime}}\min(\bar{c}\pi_{b}(a^{\prime}|s),\pi(a^{\prime}|s))}\quad\text{and}\quad\pi_{\bar{\rho}}(a|s)=\frac{\min(\bar{\rho}\pi_{b}(a|s),\pi(a|s))}{\sum_{a^{\prime}}\min(\bar{\rho}\pi_{b}(a^{\prime}|s),\pi(a^{\prime}|s))},\;\forall\;(s,a).$

  2. (2)

Let
$C_{\pi},D_{\pi}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|\times|\mathcal{S}||\mathcal{A}|}$
be diagonal matrices s.t.
$C_{\pi}((s,a),(s,a))=\sum_{a}\min(\bar{c}\pi_{b}(a|s),\pi(a|s))$ and
$D_{\pi}((s,a),(s,a))=\sum_{a}\min(\bar{\rho}\pi_{b}(a|s),\pi(a|s))$ for all
$(s,a)$. Let $C_{\min}=\bar{c}\min_{s,a}\pi_{b}(a|s)$. Note that we have
$C_{\min}I\leq C_{\pi}\leq D_{\pi}\leq I$ (component-wise).

  3. (3)

Let
$P_{\pi}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|\times|\mathcal{S}||\mathcal{A}|}$
be a stochastic matrix defined by
$P_{\pi}((s,a),(s^{\prime},a^{\prime}))=P_{a}(s,s^{\prime})\pi(a^{\prime}|s^{\prime})$,
i.e., the probability of transition from $(s,a)$ to $(s^{\prime},a^{\prime})$
under policy $\pi$. Let $R$ be a vector in
$\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$ such that $R(s,a)=\mathcal{R}(s,a)$
for all $(s,a)$.

  4. (4)

Let
$M\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|\times|\mathcal{S}||\mathcal{A}|}$
be a diagonal matrix such that $M((s,a),(s,a))=\mu_{b}(s)\pi_{b}(a|s)$, which
is the steady-state probability of visiting $(s,a)$. Let
$M_{\min}=\min_{s,a}\mu_{b}(s)\pi_{b}(a|s)$. Note that $0<M_{\min}<1$ under
Assumption 2.1.

Now we are ready to establish the desired properties of Algorithm (4) in the
following proposition, whose proof is presented in Appendix A.1.

######  Proposition 3.1.

The following properties hold regarding the operators $\mathcal{T}(\cdot)$,
$\mathcal{T}_{e}(\cdot)$, and the Markov chain $\\{X_{k}\\}$.

  1. (1)

The operator $\mathcal{T}(\cdot)$ satisfies
$\|\mathcal{T}(Q_{1},\pi,x)-\mathcal{T}(Q_{2},\pi,x)\|_{\infty}\leq
2(\bar{\rho}+1)f(\bar{c},\gamma)\|Q_{1}-Q_{2}\|_{\infty}$ and
$\|\mathcal{T}(\bm{0},\pi,x)\|_{\infty}\leq f(\bar{c},\gamma)$ for any
$Q_{1},Q_{2}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$, $\pi\in\Pi$, and
$x\in\mathcal{X}$.

  2. (2)

For all $k\geq 0$, it holds that

$\displaystyle\max_{x\in\mathcal{X}}\|P^{k+n+1}(x,\cdot)-\mu_{X}(\cdot)\|_{\text{TV}}\leq
Cu^{k},$

where $\|\cdot\|_{\text{TV}}$ is the total variation distance.

  3. (3)

The operator $\mathcal{T}_{e}(\cdot)$ has the following properties:

    1. (a)

$\mathcal{T}_{e}(\cdot,\pi)$ is a linear operator given by
$\mathcal{T}_{e}(Q,\pi)=AQ+b$, where
$A=I-\sum_{i=0}^{n-1}\gamma^{i}M(P_{\pi_{\bar{c}}}C_{\pi})^{i}(I-\gamma
P_{\pi_{\bar{\rho}}}D_{\pi})$ and
$b=\sum_{i=0}^{n-1}\gamma^{i}M(P_{\pi_{\bar{c}}}C_{\pi})^{i}R$.

    2. (b)

$\mathcal{T}_{e}(\cdot,\pi)$ is a contraction mapping with respect to
$\|\cdot\|_{\infty}$, with contraction factor

$\displaystyle\gamma_{c}=1-\frac{M_{\min}(1-\gamma)(1-(\gamma
C_{\min})^{n})}{1-\gamma C_{\min}}.$

    3. (c)

$\mathcal{T}_{e}(\cdot,\pi)$ has a unique fixed-point $Q^{\bar{\rho},\pi}$,
which is the unique solution to the modified Bellman’s equation $Q=R+\gamma
P_{\pi_{\bar{\rho}}}D_{\pi}Q$.

Several remarks are in order. First, using Proposition 3.1 (1), we have by
triangle inequality that

$\displaystyle\|\mathcal{T}(Q,\pi,x)\|_{\infty}\leq
2f(\bar{c},\gamma)((\bar{\rho}+1)\|Q\|_{\infty}+1)$

for any $Q$, $\pi$ and $x$. This is important to control the Markovian noise
as it implies that the noisy operator
$\|\mathcal{T}(Q_{k},\pi,X_{k})\|_{\infty}$ is at most an affine function of
$\|Q_{k}\|_{\infty}$.

Proposition 3.1 (2) implies that the Markov chain $\\{X_{k}\\}$ mixes
geometrically fast, which is also an important property we need to control the
Markovian noise.

Proposition 3.1 (3) establishes all the desired properties for the expected
operator $\mathcal{T}_{e}(\cdot)$. First of all, $\mathcal{T}_{e}(\cdot,\pi)$
is a contraction operator, with a contraction factor $\gamma_{c}$ independent
of the target policy $\pi$. This uniform contraction property is necessary for
us to combine the critic with the actor later in Section 3.2.2, as the policy
$\pi_{t}$ is time-varying.

Note that from Proposition 3.1 (3) (c) we see that when
$\bar{\rho}\geq\max_{s,a}\frac{\pi(a|s)}{\pi_{b}(a|s)}$, such modified
Bellman’s equation becomes the regular Bellman’s equation for $Q^{\pi}$, and
hence we have $Q^{\bar{\rho},\pi}=Q^{\pi}$, which agrees with Lemma 2.1.

The above proposition enables us to interpret Eq. (4) as a Markovian
Stochastic Approximation involving a contraction mapping. Theorem 2.1 then
follows from using finite-sample bounds on Markovian Stochastic Approximation
established in [19]. See Appendix A.3 for the detailed proof.

###  3.2 Proof Sketch of Theorem 2.2

The high level idea of proving Theorem 2.2 is as follows. We first analyze the
iterates $\\{\pi_{t}\\}$ updated by the actor in Algorithm 2. The performance
bound of $\pi_{t}$ would involve the error in the critic estimate, i.e., the
difference between $Q_{t+1}$ and $Q^{\pi_{t}}$. We then use Corollary 2.1.1 of
the $Q$-trace algorithm 1 to control the critic estimation error and finish
the proof of Theorem 2.2.

####  3.2.1 Analysis of the Actor

By analyzing the update of the actor, we obtain the performance bound of
$\\{\pi_{t}\\}$ in the following proposition.

######  Proposition 3.2.

Consider iterates $\\{\pi_{t}\\}$ of Algorithm 2. We have for any $T\geq 1$:

$\displaystyle V^{\pi^{*}}(\mu)-\max_{0\leq t\leq
T-1}\mathbb{E}\left[V^{\pi_{t}}(\mu)\right]\leq\underbrace{\frac{\log(e|\mathcal{A}|)}{(1-\gamma)^{2}\beta
T}}_{\text{Error in the
actor}}+\underbrace{\frac{4}{(1-\gamma)^{2}T}\sum_{t=0}^{T-1}\mathbb{E}[\|Q^{\pi_{t}}-Q_{t+1}\|_{\infty}]}_{\text{Error
in the Critic}}.$

The proof of Proposition 3.2 is inspired by that of Theorem 5.3 in [1], and is
presented in Appendix B.1. The main difference is that in [1] they assume
access to the dynamics of the underlying MDP. Hence they can directly use the
$Q$-function $Q^{\pi_{t}}$ in the policy update. Here in the RL setting, we
can only use the noisy estimate $Q_{t}$ to perform the policy update. As a
consequence, when compared to Theorem 5.3 of [1], we have the critic error
term
$\frac{4}{(1-\gamma)^{2}T}\sum_{t=0}^{T-1}\mathbb{E}[\|Q^{\pi_{t}}-Q_{t+1}\|_{\infty}]$
on the RHS of the resulting inequality of Proposition 3.2.

####  3.2.2 Combining the Actor and the Critic

In view of Proposition 3.2, what remains to do in proving Theorem 2.2 is to
apply Corollary 2.1.1 to control the error term
$\mathbb{E}[\|Q^{\pi_{t}}-Q_{t+1}\|_{\infty}]$ for any $0\leq t\leq T-1$.
However, there is a challenge in doing this. Corollary 2.1.1 and Theorem 2.1
are stated for a fixed target policy $\pi$, while in Algorithm 2 the policies
$\pi_{t}$ are stochastic. We overcome this challenge by using a conditioning
argument and exploiting Markovian nature of the samples. The full details are
presented in Appendix B.2.

##  4 Conclusion and Future Work

In this work, we study the convergence bounds of NAC, where the critic uses
the $Q$-trace algorithm to perform off-policy learning. Such off-policy NAC
algorithm enables us to overcome the difficulty of exploration in on-policy
NAC, and establish the convergence bounds under minimal assumptions. A future
direction is to extend our results to the case where function approximation is
used. Note that off-policy TD with function approximation can be unstable in
general [64]. The first step in this direction is to modify the algorithm to
achieve convergence.

## References

  * [1] [author] Agarwal, AlekhA., Kakade, Sham MS. M., Lee, Jason DJ. D. and Mahajan, GauravG. (2019). On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Preprint arXiv:1908.00261.
  * [2] [author] Azar, Mohammad GheshlaghiM. G., Gómez, VicençV. and Kappen, Hilbert JH. J. (2012). Dynamic policy programming. The Journal of Machine Learning Research 13 3207–3245.
  * [3] [author] Bahdanau, DzmitryD., Brakel, PhilemonP., Xu, KelvinK., Goyal, AnirudhA., Lowe, RyanR., Pineau, JoelleJ., Courville, AaronA. and Bengio, YoshuaY. (2016). An actor-critic algorithm for sequence prediction. Preprint arXiv:1607.07086.
  * [4] [author] Banach, StefanS. (1922). Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales. Fund. math 3 133–181.
  * [5] [author] Barto, A. G.A. G., Sutton, R. S.R. S. and Anderson, C. W.C. W. (1983). Neuronlike adaptive elements that can solve difficult learning control problems. IEEE Transactions on Systems, Man, and Cybernetics SMC-13 834-846. 10.1109/TSMC.1983.6313077
  * [6] [author] Baxter, JonathanJ. and Bartlett, Peter LP. L. (2001). Infinite-horizon policy-gradient estimation. Journal of Artificial Intelligence Research 15 319–350.
  * [7] [author] Beck, Carolyn LC. L. and Srikant, RayadurgamR. (2012). Error bounds for constant step-size $Q$-learning. Systems & control letters 61 1203–1208.
  * [8] [author] Beck, Carolyn LC. L. and Srikant, RayadurgamR. (2013). Improved upper bounds on the expected error in constant step-size $Q$-learning. In 2013 American Control Conference 1926–1931. IEEE.
  * [9] [author] Bertsekas, Dimitri PD. P. and Tsitsiklis, John NJ. N. (1996). Neuro-dynamic programming. Athena Scientific.
  * [10] [author] Bhandari, JalajJ. and Russo, DanielD. (2020). A note on the linear convergence of policy gradient methods. Preprint arXiv:2007.11120.
  * [11] [author] Bhandari, JalajJ., Russo, DanielD. and Singal, RaghavR. (2018). A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation. In Conference On Learning Theory 1691–1692.
  * [12] [author] Bhatnagar, ShalabhS., Sutton, Richard SR. S., Ghavamzadeh, MohammadM. and Lee, MarkM. (2009). Natural actor–critic algorithms. Automatica 45 2471–2482.
  * [13] [author] Borkar, Vivek SV. S. (2009). Stochastic approximation: a dynamical systems viewpoint 48\. Springer.
  * [14] [author] Borkar, Vivek SV. S. and Konda, Vijaymohan RV. R. (1997). The actor-critic algorithm as multi-time-scale stochastic approximation. Sadhana 22 525–543.
  * [15] [author] Borkar, Vivek SV. S. and Meyn, Sean PS. P. (2000). The ODE method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization 38 447–469.
  * [16] [author] Bottou, LéonL., Curtis, Frank EF. E. and Nocedal, JorgeJ. (2018). Optimization methods for large-scale machine learning. Siam Review 60 223–311.
  * [17] [author] Cen, ShicongS., Cheng, ChenC., Chen, YuxinY., Wei, YutingY. and Chi, YuejieY. (2020). Fast global convergence of natural policy gradient methods with entropy regularization. Preprint arXiv:2007.06558.
  * [18] [author] Chen, ZaiweiZ., Maguluri, Siva ThejaS. T., Shakkottai, SanjayS. and Shanmugam, KarthikeyanK. (2020). Finite-Sample Analysis of Contractive Stochastic Approximation Using Smooth Convex Envelopes. Advances in Neural Information Processing Systems 33\.
  * [19] [author] Chen, ZaiweiZ., Maguluri, Siva ThejaS. T., Shakkottai, SanjayS. and Shanmugam, KarthikeyanK. (2021). A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous $Q$-Learning and TD-Learning Variants. Preprint arXiv:2102.01567.
  * [20] [author] Cover, Thomas MT. M. (1999). Elements of information theory. John Wiley & Sons.
  * [21] [author] Dalal, GalG., Szörényi, BalázsB., Thoppe, GuganG. and Mannor, ShieS. (2018). Finite sample analysis for TD$(0)$ with function approximation. In Thirty-Second AAAI Conference on Artificial Intelligence.
  * [22] [author] Dann, ChristophC., Li, LihongL., Wei, WeiW. and Brunskill, EmmaE. (2019). Policy certificates: Towards accountable reinforcement learning. In International Conference on Machine Learning 1507–1516. PMLR.
  * [23] [author] Degris, ThomasT., White, MarthaM. and Sutton, RichardR. (2012). Off-Policy Actor-Critic. In International Conference on Machine Learning.
  * [24] [author] Espeholt, LasseL., Soyer, HubertH., Munos, RemiR., Simonyan, KarenK., Mnih, VladV., Ward, TomT., Doron, YotamY., Firoiu, VladV., Harley, TimT., Dunning, IainI. et al. (2018). IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures. In International Conference on Machine Learning 1407–1416.
  * [25] [author] Even-Dar, EyalE., Kakade, Sham MS. M. and Mansour, YishayY. (2009). Online Markov decision processes. Mathematics of Operations Research 34 726–736.
  * [26] [author] Even-Dar, EyalE. and Mansour, YishayY. (2003). Learning rates for $Q$-learning. Journal of Machine Learning Research 5 1–25.
  * [27] [author] Geist, MatthieuM., Scherrer, BrunoB. and Pietquin, OlivierO. (2019). A theory of regularized markov decision processes. In International Conference on Machine Learning 2160–2169. PMLR.
  * [28] [author] Geweke, JohnJ. (1989). Bayesian inference in econometric models using Monte Carlo integration. Econometrica: Journal of the Econometric Society 1317–1339.
  * [29] [author] Glynn, Peter WP. W. and Iglehart, Donald LD. L. (1989). Importance sampling for stochastic simulations. Management science 35 1367–1392.
  * [30] [author] Gottesman, OmerO., Futoma, JosephJ., Liu, YaoY., Parbhoo, SonaliS., Celi, LeoL., Brunskill, EmmaE. and Doshi-Velez, FinaleF. (2020). Interpretable off-policy evaluation in reinforcement learning by highlighting influential transitions. In International Conference on Machine Learning 3658–3667. PMLR.
  * [31] [author] Gu, ShixiangS., Holly, EthanE., Lillicrap, TimothyT. and Levine, SergeyS. (2017). Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates. In 2017 IEEE international conference on robotics and automation (ICRA) 3389–3396. IEEE.
  * [32] [author] Haarnoja, TuomasT., Tang, HaoranH., Abbeel, PieterP. and Levine, SergeyS. (2017). Reinforcement learning with deep energy-based policies. In International Conference on Machine Learning 1352–1361. PMLR.
  * [33] [author] Ionides, Edward LE. L. (2008). Truncated importance sampling. Journal of Computational and Graphical Statistics 17 295–311.
  * [34] [author] Jaakkola, TommiT., Jordan, Michael IM. I. and Singh, Satinder PS. P. (1994). Convergence of stochastic iterative dynamic programming algorithms. In Advances in neural information processing systems 703–710.
  * [35] [author] Kakade, Sham MS. M. (2001). A natural policy gradient. Advances in neural information processing systems 14\.
  * [36] [author] Khodadadian, SajadS., Doan, Thinh T.T. T., Maguluri, Siva ThejaS. T. and Romberg, JustinJ. (2021). Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithm. Preprint arXiv:2101.10506.
  * [37] [author] Konda, Vijay RV. R. and Tsitsiklis, John NJ. N. (2000). Actor-critic algorithms. In Advances in neural information processing systems 1008–1014. Citeseer.
  * [38] [author] Kumar, HarshatH., Koppel, AlecA. and Ribeiro, AlejandroA. (2019). On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximation. Preprint arXiv:1910.08412.
  * [39] [author] Lakshminarayanan, ChandrashekarC. and Szepesvari, CsabaC. (2018). Linear Stochastic Approximation: How Far Does Constant Step-Size and Iterate Averaging Go? In International Conference on Artificial Intelligence and Statistics 1347–1355.
  * [40] [author] Lan, GuanghuiG. (2020). First-order and Stochastic Optimization Methods for Machine Learning. Springer.
  * [41] [author] Lan, GuanghuiG. (2021). Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. arXiv preprint arXiv:2102.00135.
  * [42] [author] Levin, David AD. A. and Peres, YuvalY. (2017). Markov chains and mixing times 107\. American Mathematical Soc.
  * [43] [author] Levine, SergeyS., Kumar, AviralA., Tucker, GeorgeG. and Fu, JustinJ. (2020). Offline reinforcement learning: Tutorial, review, and perspectives on open problems. Preprint arXiv:2005.01643.
  * [44] [author] Li, GenG., Wei, YutingY., Chi, YuejieY., Gu, YuantaoY. and Chen, YuxinY. (2020). Sample Complexity of Asynchronous $Q$-Learning: Sharper Analysis and Variance Reduction. Preprint arXiv:2006.03041.
  * [45] [author] Lillicrap, Timothy PT. P., Hunt, Jonathan JJ. J., Pritzel, AlexanderA., Heess, NicolasN., Erez, TomT., Tassa, YuvalY., Silver, DavidD. and Wierstra, DaanD. (2015). Continuous control with deep reinforcement learning. Preprint arXiv:1509.02971.
  * [46] [author] Liu, BoyiB., Cai, QiQ., Yang, ZhuoranZ. and Wang, ZhaoranZ. (2019). Neural proximal/trust region policy optimization attains globally optimal policy. Preprint arXiv:1906.10306.
  * [47] [author] Liu, YaoY., Gottesman, OmerO., Raghu, AniruddhA., Komorowski, MatthieuM., Faisal, Aldo AA. A., Doshi-Velez, FinaleF. and Brunskill, EmmaE. (2018). Representation Balancing MDPs for Off-policy Policy Evaluation. Advances in Neural Information Processing Systems 31 2644–2653.
  * [48] [author] Maei, Hamid RezaH. R. (2018). Convergent actor-critic algorithms under off-policy training and function approximation. arXiv preprint arXiv:1802.07842.
  * [49] [author] Mandel, TravisT., Liu, Yun-EnY.-E., Levine, SergeyS., Brunskill, EmmaE. and Popovic, ZoranZ. (2014). Offline policy evaluation across representations with applications to educational games. In AAMAS 1077–1084.
  * [50] [author] Mei, JinchengJ., Xiao, ChenjunC., Szepesvari, CsabaC. and Schuurmans, DaleD. (2020). On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning 6820–6829. PMLR.
  * [51] [author] Morimura, TetsuroT., Uchibe, EijiE., Yoshimoto, JunichiroJ. and Doya, KenjiK. (2009). A generalized natural actor-critic algorithm. In Advances in neural information processing systems 1312–1320.
  * [52] [author] Munos, RémiR., Stepleton, ThomasT., Harutyunyan, AnnaA. and Bellemare, Marc GM. G. (2016). Safe and efficient off-policy reinforcement learning. In Proceedings of the 30th International Conference on Neural Information Processing Systems 1054–1062.
  * [53] [author] Nemirovskij, Arkadij SemenovičA. S. and Yudin, David BorisovichD. B. (1983). Problem complexity and method efficiency in optimization. Chichester: John Wiley.
  * [54] [author] Peters, JanJ. and Schaal, StefanS. (2008). Natural actor-critic. Neurocomputing 71 1180–1190.
  * [55] [author] Pirotta, MatteoM., Restelli, MarcelloM. and Bascetta, LucaL. (2015). Policy gradient in lipschitz markov decision processes. Machine Learning 100 255–283.
  * [56] [author] Precup, DoinaD. (2000). Eligibility traces for off-policy policy evaluation. Computer Science Department Faculty Publication Series 80\.
  * [57] [author] Puterman, Martin LM. L. (1995). Markov decision processes: Discrete stochastic dynamic programming. Journal of the Operational Research Society 46 792–792.
  * [58] [author] Qiu, ShuangS., Yang, ZhuoranZ., Ye, JiepingJ. and Wang, ZhaoranZ. (2019). On the finite-time convergence of actor-critic algorithm. In Optimization Foundations for Reinforcement Learning Workshop at Advances in Neural Information Processing Systems (NeurIPS).
  * [59] [author] Qu, GuannanG. and Wierman, AdamA. (2020). Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning. In Conference on Learning Theory 3185–3205. PMLR.
  * [60] [author] Shani, LiorL., Efroni, YonathanY. and Mannor, ShieS. (2020). Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs. In Proceedings of the AAAI Conference on Artificial Intelligence 34 5668–5675.
  * [61] [author] Silver, DavidD., Huang, AjaA., Maddison, Chris JC. J., Guez, ArthurA., Sifre, LaurentL., Van Den Driessche, GeorgeG., Schrittwieser, JulianJ., Antonoglou, IoannisI., Panneershelvam, VedaV., Lanctot, MarcM. et al. (2016). Mastering the game of Go with deep neural networks and tree search. nature 529 484\.
  * [62] [author] Srikant, RR. and Ying, LeiL. (2019). Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning. In Conference on Learning Theory 2803–2830.
  * [63] [author] Sutton, Richard SR. S. (1988). Learning to predict by the methods of temporal differences. Machine learning 3 9–44.
  * [64] [author] Sutton, Richard SR. S. and Barto, Andrew GA. G. (2018). Reinforcement learning: An introduction. MIT press.
  * [65] [author] Sutton, Richard SR. S., McAllester, David AD. A., Singh, Satinder PS. P., Mansour, YishayY. et al. (1999). Policy gradient methods for reinforcement learning with function approximation. In NIPs 99 1057–1063. Citeseer.
  * [66] [author] Thomas, Philip SP. S., Dabney, WilliamW., Mahadevan, SridharS. and Giguere, StephenS. (2013). Projected natural actor-critic. In Proceedings of the 26th International Conference on Neural Information Processing Systems-Volume 2 2337–2345.
  * [67] [author] Tsitsiklis, John NJ. N. (1994). Asynchronous stochastic approximation and $Q$-learning. Machine learning 16 185–202.
  * [68] [author] Tsitsiklis, John NJ. N. and Van Roy, BenjaminB. (1997). Analysis of temporal-difference learning with function approximation. In Advances in neural information processing systems 1075–1081.
  * [69] [author] Tsitsiklis, John NJ. N. and Van Roy, BenjaminB. (1999). Average cost temporal-difference learning. Automatica 35 1799–1808.
  * [70] [author] Wainwright, Martin JM. J. (2019). Stochastic approximation with cone-contractive operators: Sharp $\ell_{\infty}$-bounds for ${Q}$-learning. Preprint arXiv:1905.06265.
  * [71] [author] Wang, LingxiaoL., Cai, QiQ., Yang, ZhuoranZ. and Wang, ZhaoranZ. (2019). Neural policy gradient methods: Global optimality and rates of convergence. Preprint arXiv:1909.01150.
  * [72] [author] Wang, ZiyuZ., Bapst, VictorV., Heess, NicolasN., Mnih, VolodymyrV., Munos, RemiR., Kavukcuoglu, KorayK. and de Freitas, NandoN. (2016). Sample efficient actor-critic with experience replay. Preprint arXiv:1611.01224.
  * [73] [author] Watkins, Christopher JCHC. J. and Dayan, PeterP. (1992). $Q$-learning. Machine learning 8 279–292.
  * [74] [author] Williams, Ronald JR. J. and Baird, Leemon CL. C. (1990). A mathematical analysis of actor-critic architectures for learning optimal controls through incremental dynamic programming. In Proceedings of the Sixth Yale Workshop on Adaptive and Learning Systems 96–101. Citeseer.
  * [75] [author] Wu, YueY., Zhang, WeitongW., Xu, PanP. and Gu, QuanquanQ. (2020). A Finite Time Analysis of Two Time-Scale Actor Critic Methods. Preprint arXiv:2005.01350.
  * [76] [author] Xu, TengyuT., Wang, ZheZ. and Liang, YingbinY. (2020). Improving sample complexity bounds for (natural) actor-critic algorithms. Advances in Neural Information Processing Systems 33\.
  * [77] [author] Xu, TengyuT., Wang, ZheZ. and Liang, YingbinY. (2020). Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms. Preprint arXiv:2005.03557.
  * [78] [author] Zhang, KaiqingK., Koppel, AlecA., Zhu, HaoH. and Başar, TamerT. (2019). Convergence and iteration complexity of policy gradient method for infinite-horizon reinforcement learning. In 2019 IEEE 58th Conference on Decision and Control (CDC) 7415–7422. IEEE.
  * [79] [author] Zhang, ShangtongS., Liu, BoB., Yao, HengshuaiH. and Whiteson, ShimonS. (2020). Provably convergent two-timescale off-policy actor-critic with function approximation. In International Conference on Machine Learning 11204–11213. PMLR.

##  Appendix A The Q-Trace Algorithm

###  A.1 Proof of Proposition 3.1

  1. (1)

Using the definition of the operator $\mathcal{T}(\cdot)$, we have for any
$Q_{1},Q_{2}$, $\pi$, $x=(s_{0},a_{0},...,s_{n},a_{n})\in\mathcal{X}$, and
state-action pairs $(s,a)$:

$\displaystyle|[\mathcal{T}(Q_{1},\pi,x)](s,a)-[\mathcal{T}(Q_{2},\pi,x)](s,a)|$
$\displaystyle=\;$
$\displaystyle\bigg{|}\mathbb{I}_{\\{(s,a)=(s_{0},a_{0})\\}}\sum_{i=0}^{n-1}\gamma^{i}\left(\prod_{j=1}^{i}c_{\pi}(s_{j},a_{j})\right)\left(\gamma\rho_{\pi}(s_{i+1},a_{i+1})[Q_{1}-Q_{2}](s_{i+1},a_{i+1})-[Q_{1}-Q_{2}](s_{i},a_{i})\right)$
$\displaystyle+[Q_{1}-Q_{2}](s,a)\bigg{|}$ $\displaystyle\leq\;$
$\displaystyle\sum_{i=0}^{n-1}\gamma^{i}\left(\prod_{j=1}^{i}c_{\pi}(s_{j},a_{j})\right)\left(\gamma\rho_{\pi}(s_{i+1},a_{i+1})+1\right)\|Q_{1}-Q_{2}\|_{\infty}+\|Q_{1}-Q_{2}\|_{\infty}$
$\displaystyle\leq\;$
$\displaystyle\sum_{i=0}^{n-1}(\gamma\bar{c})^{i}(\bar{\rho}+1)\|Q_{1}-Q_{2}\|_{\infty}+\|Q_{1}-Q_{2}\|_{\infty}$
($c_{\pi}(s,a)\leq\bar{c}$ and $\rho_{\pi}(s,a)\leq\bar{\rho}$ for any
$(s,a)$) $\displaystyle\leq\;$
$\displaystyle\begin{dcases}2n(\bar{\rho}+1)\|Q_{1}-Q_{2}\|_{\infty},&\gamma\bar{c}=1,\\\
\frac{2(\bar{\rho}+1)(1-(\gamma\bar{c})^{n})}{1-\gamma\bar{c}}\|Q_{1}-Q_{2}\|_{\infty},&\gamma\bar{c}\neq
1.\end{dcases}$

It follows that
$\|\mathcal{T}(Q_{1},\pi,x)-\mathcal{T}(Q_{2},\pi,x)\|_{\infty}\leq
2f(\bar{c},\gamma)(\bar{\rho}+1)\|Q_{1}-Q_{2}\|_{\infty}$. Similarly, for any
$\pi\in\Pi$ and $x=(s_{0},a_{0},...,s_{n},a_{n})\in\mathcal{X}$, we have for
any $(s,a)$:

$\displaystyle|[\mathcal{T}(\bm{0},\pi,x)](s,a)|$
$\displaystyle=\left|\mathbb{I}_{\\{(s,a)=(s_{0},a_{0})\\}}\sum_{i=0}^{n-1}\gamma^{i}\left(\prod_{j=1}^{i}c_{\pi}(s_{j},a_{j})\right)\mathcal{R}(s_{i},a_{i})\right|$
$\displaystyle\leq\sum_{i=0}^{n-1}\gamma^{i}\left(\prod_{j=1}^{i}c_{\pi}(s_{j},a_{j})\right)$
($\mathcal{R}(s,a)\in[0,1]$ for any $(s,a)$)
$\displaystyle\leq\sum_{i=0}^{n-1}(\gamma\bar{c})^{i}$
($c_{\pi}(s,a)\leq\bar{c}$ for any $(s,a)$)
$\displaystyle=\begin{dcases}n,&\gamma\bar{c}=1,\\\
\frac{1-(\gamma\bar{c})^{n}}{1-\gamma\bar{c}},&\gamma\bar{c}\neq
1.\end{dcases}$

Hence we have $\|\mathcal{T}(\bm{0},\pi,x)\|_{\infty}\leq f(\bar{c},\gamma)$.

  2. (2)

Since the Markov chain $\\{S_{k}\\}$ induced by the behavior policy $\pi_{b}$
is irreducible and aperiodic, there exists $C>0$ and $u\in(0,1)$ such that
$\max_{s\in\mathcal{S}}\|P^{k}(s,\cdot)-\mu_{b}(\cdot)\|_{\text{TV}}\leq
Cu^{k}$ for all $k\geq 0$ [42], where $P^{k}$ represents the $k$-step
transition probability matrix. Now consider the Markov chain $\\{X_{k}\\}$. We
have for all $k\geq 0$:

$\displaystyle\max_{x\in\mathcal{X}}\left\|P^{k+n+1}(x,\cdot)-\mu_{X}(\cdot)\right\|_{\text{TV}}$
$\displaystyle=\;$
$\displaystyle\frac{1}{2}\max_{s_{0},a_{0},...,s_{n},a_{n}}\sum_{s_{0}^{\prime},a_{0}^{\prime},...,s_{n}^{\prime},a_{n}^{\prime}}\left|\sum_{s}P_{a_{n}}(s_{n},s)P^{k}(s,s_{0}^{\prime})-\mu_{b}(s_{0}^{\prime})\right|\pi_{b}(a_{0}^{\prime}|s_{0}^{\prime})\prod_{i=0}^{n-1}P_{a_{i}^{\prime}}(s_{i}^{\prime},s_{i+1}^{\prime})\pi_{b}(a_{i+1}^{\prime}|s_{i+1}^{\prime})$
($P_{a}$ is the transition probability matrix under action $a$)
$\displaystyle\leq\;$
$\displaystyle\frac{1}{2}\max_{s_{n},a_{n}}\sum_{s_{0}^{\prime}}\left|\sum_{s}P_{a_{n}}(s_{n},s)P^{k}(s,s_{0}^{\prime})-\mu_{b}(s_{0}^{\prime})\right|$
$\displaystyle=\;$
$\displaystyle\frac{1}{2}\max_{s_{n},a_{n}}\sum_{s}P_{a_{n}}(s_{n},s)\sum_{s_{0}^{\prime}}\left|P^{k}(s,s_{0}^{\prime})-\mu_{b}(s_{0}^{\prime})\right|$
$\displaystyle\leq\;$
$\displaystyle\frac{1}{2}\max_{s}\sum_{s_{0}^{\prime}}\left|P^{k}(s,s_{0}^{\prime})-\mu_{b}(s_{0}^{\prime})\right|$
$\displaystyle=\;$
$\displaystyle\max_{s\in\mathcal{S}}\left\|P^{k}(s,\cdot)-\mu_{b}(\cdot)\right\|_{\text{TV}}$
$\displaystyle\leq\;$ $\displaystyle Cu^{k}.$

  3. (3)

    1. (a)

We first compute $\mathcal{T}_{e}(Q,\pi)$ in the following. For any
$Q\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$ and $\pi\in\Pi$, we have for any
$(s,a)$:

$\displaystyle[\mathcal{T}_{e}(Q,\pi)](s,a)$ $\displaystyle=\;$
$\displaystyle\mathbb{E}_{S_{0}\sim\mu_{b}}\Bigg{[}\mathbb{I}_{\\{(s,a)=(S_{0},A_{0})\\}}\sum_{i=0}^{n-1}\gamma^{i}\left(\prod_{j=1}^{i}c_{\pi}(S_{j},A_{j})\right)(\mathcal{R}(S_{i},A_{i})+\gamma\rho_{\pi}(S_{i+1},A_{i+1})Q(S_{i+1},A_{i+1})$
$\displaystyle-Q(S_{i},A_{i}))\Bigg{]}+Q(s,a).$

For any $0\leq i\leq n-1$, we have

$\displaystyle\mathbb{E}_{S_{0}\sim\mu_{b}}\left[\mathbb{I}_{\\{(s,a)=(S_{0},A_{0})\\}}\gamma^{i}\left(\prod_{j=1}^{i}c_{\pi}(S_{j},A_{j})\right)\left(\mathcal{R}(S_{i},A_{i})+\gamma\rho_{\pi}(S_{i+1},A_{i+1})Q(S_{i+1},A_{i+1})-Q(S_{i},A_{i})\right)\right]$
$\displaystyle=\;$
$\displaystyle\mathbb{E}_{S_{0}\sim\mu_{b}}\Bigg{[}\mathbb{I}_{\\{(s,a)=(S_{0},A_{0})\\}}\gamma^{i}\left(\prod_{j=1}^{i}c_{\pi}(S_{j},A_{j})\right)(\mathcal{R}(S_{i},A_{i})$
$\displaystyle+\gamma\mathbb{E}[\rho_{\pi}(S_{i+1},A_{i+1})Q(S_{i+1},A_{i+1})\mid
S_{0}\sim\mu_{b},A_{0},...,S_{i},A_{i}]-Q(S_{i},A_{i}))\Bigg{]}$
$\displaystyle=\;$
$\displaystyle\mathbb{E}_{S_{0}\sim\mu_{b}}\Bigg{[}\mathbb{I}_{\\{(s,a)=(S_{0},A_{0})\\}}\gamma^{i}\left(\prod_{j=1}^{i}c_{\pi}(S_{j},A_{j})\right)(\mathcal{R}(S_{i},A_{i})$
$\displaystyle+\gamma\sum_{s^{\prime},a^{\prime}}P_{A_{i}}(S_{i},s^{\prime})\pi_{b}(a^{\prime}|s^{\prime})\min\left(\bar{\rho},\frac{\pi(a^{\prime}|s^{\prime})}{\pi_{b}(a^{\prime}|s^{\prime})}\right)Q(s^{\prime},a^{\prime})-Q(S_{i},A_{i}))\Bigg{]}$
$\displaystyle=\;$
$\displaystyle\mathbb{E}_{S_{0}\sim\mu_{b}}\Bigg{[}\mathbb{I}_{\\{(s,a)=(S_{0},A_{0})\\}}\gamma^{i}\left(\prod_{j=1}^{i}c_{\pi}(S_{j},A_{j})\right)(\mathcal{R}(S_{i},A_{i})$
$\displaystyle+\gamma\sum_{s^{\prime},a^{\prime}}P_{A_{i}}(S_{i},s^{\prime})\min\left(\bar{\rho}\pi_{b}(a^{\prime}|s^{\prime}),\pi(a^{\prime}|s^{\prime})\right)Q(s^{\prime},a^{\prime})-Q(S_{i},A_{i}))\Bigg{]}$
$\displaystyle=\;$
$\displaystyle\mathbb{E}_{S_{0}\sim\mu_{b}}\Bigg{[}\mathbb{I}_{\\{(s,a)=(S_{0},A_{0})\\}}\gamma^{i}\left(\prod_{j=1}^{i}c_{\pi}(S_{j},A_{j})\right)(\mathcal{R}(S_{i},A_{i})$
$\displaystyle+\gamma\sum_{s^{\prime},a^{\prime}}P_{A_{i}}(S_{i},s^{\prime})D_{\pi}(s^{\prime},a^{\prime})\frac{\min\left(\bar{\rho}\pi_{b}(a^{\prime}|s^{\prime}),\pi(a^{\prime}|s^{\prime})\right)}{\sum_{a^{\prime}}\min\left(\bar{\rho}\pi_{b}(a^{\prime}|s^{\prime}),\pi(a^{\prime}|s^{\prime})\right)}Q(s^{\prime},a^{\prime})-Q(S_{i},A_{i}))\Bigg{]}$
$\displaystyle=\;$
$\displaystyle\mathbb{E}_{S_{0}\sim\mu_{b}}\Bigg{[}\mathbb{I}_{\\{(s,a)=(S_{0},A_{0})\\}}\gamma^{i}\left(\prod_{j=1}^{i}c_{\pi}(S_{j},A_{j})\right)(\mathcal{R}(S_{i},A_{i})$
$\displaystyle+\gamma\sum_{s^{\prime},a^{\prime}}P_{A_{i}}(S_{i},s^{\prime})D_{\pi}(s^{\prime},a^{\prime})\pi_{\bar{\rho}}(a^{\prime}|s^{\prime})Q(s^{\prime},a^{\prime})-Q(S_{i},A_{i}))\Bigg{]}$
$\displaystyle=\;$
$\displaystyle\mathbb{E}_{S_{0}\sim\mu_{b}}\Bigg{[}\mathbb{I}_{\\{(s,a)=(S_{0},A_{0})\\}}\gamma^{i}\left(\prod_{j=1}^{i}c_{\pi}(S_{j},A_{j})\right)(\mathcal{R}(S_{i},A_{i})$
$\displaystyle+\gamma\sum_{s^{\prime},a^{\prime}}P_{\pi_{\bar{\rho}}}((S_{i},A_{i}),(s^{\prime},a^{\prime}))D_{\pi}(s^{\prime},a^{\prime})Q(s^{\prime},a^{\prime})-Q(S_{i},A_{i}))\Bigg{]}$
$\displaystyle=\;$
$\displaystyle\mathbb{E}_{S_{0}\sim\mu_{b}}\left[\mathbb{I}_{\\{(s,a)=(S_{0},A_{0})\\}}\gamma^{i}\left(\prod_{j=1}^{i}c_{\pi}(S_{j},A_{j})\right)(\mathcal{R}(S_{i},A_{i})+\gamma[P_{\pi_{\bar{\rho}}}D_{\pi}Q](S_{i},A_{i})-Q(S_{i},A_{i}))\right]$
$\displaystyle=\;$
$\displaystyle\mathbb{E}_{S_{0}\sim\mu_{b}}\Bigg{[}\mathbb{I}_{\\{(s,a)=(S_{0},A_{0})\\}}\gamma^{i}\left(\prod_{j=1}^{i-1}c_{\pi}(S_{j},A_{j})\right)\times$
$\displaystyle\mathbb{E}\left[c_{\pi}(S_{i},A_{i})(\mathcal{R}(S_{i},A_{i})+\gamma[P_{\pi_{\bar{\rho}}}D_{\pi}Q](S_{i},A_{i})-Q(S_{i},A_{i}))\mid
S_{0}\sim\mu_{b},A_{0},...,S_{i-1},A_{i-1}\right]\Bigg{]}$ $\displaystyle=\;$
$\displaystyle\mathbb{E}_{S_{0}\sim\mu_{b}}\Bigg{[}\mathbb{I}_{\\{(s,a)=(S_{0},A_{0})\\}}\gamma^{i}\left(\prod_{j=1}^{i-1}c_{\pi}(S_{j},A_{j})\right)\times$
$\displaystyle\left(\sum_{s^{\prime},a^{\prime}}P_{A_{i-1}}(S_{i-1},s^{\prime})\pi_{b}(a^{\prime}|s^{\prime})\min\left(\bar{c},\frac{\pi(a^{\prime}|s^{\prime})}{\pi_{b}(a^{\prime}|s^{\prime})}\right)[R+\gamma
P_{\pi_{\bar{\rho}}}D_{\pi}Q-Q](s^{\prime},a^{\prime})\right)\Bigg{]}$
$\displaystyle=\;$
$\displaystyle\mathbb{E}_{S_{0}\sim\mu_{b}}\Bigg{[}\mathbb{I}_{\\{(s,a)=(S_{0},A_{0})\\}}\gamma^{i}\left(\prod_{j=1}^{i-1}c_{\pi}(S_{j},A_{j})\right)\times$
$\displaystyle\left(\sum_{s^{\prime},a^{\prime}}P_{A_{i-1}}(S_{i-1},s^{\prime})\min\left(\bar{c}\pi_{b}(a^{\prime}|s^{\prime}),\pi(a^{\prime}|s^{\prime})\right)[R+\gamma
P_{\pi_{\bar{\rho}}}D_{\pi}Q-Q](s^{\prime},a^{\prime})\right)\Bigg{]}$
$\displaystyle=\;$
$\displaystyle\mathbb{E}_{S_{0}\sim\mu_{b}}\Bigg{[}\mathbb{I}_{\\{(s,a)=(S_{0},A_{0})\\}}\gamma^{i}\left(\prod_{j=1}^{i-1}c_{\pi}(S_{j},A_{j})\right)\times$
$\displaystyle\left(\sum_{s^{\prime},a^{\prime}}P_{A_{i-1}}(S_{i-1},s^{\prime})C_{\pi}(s^{\prime},a^{\prime})\pi_{\bar{c}}(a^{\prime}|s^{\prime})[R+\gamma
P_{\pi_{\bar{\rho}}}D_{\pi}Q-Q](s^{\prime},a^{\prime})\right)\Bigg{]}$
$\displaystyle=\;$
$\displaystyle\mathbb{E}_{S_{0}\sim\mu_{b}}\left[\mathbb{I}_{\\{(s,a)=(S_{0},A_{0})\\}}\gamma^{i}\left(\prod_{j=1}^{i-1}c_{\pi}(S_{j},A_{j})\right)[P_{\pi_{\bar{c}}}C_{\pi}(R+\gamma
P_{\pi_{\bar{\rho}}}D_{\pi}Q-Q)](S_{i-1},A_{i-1})\right]$ $\displaystyle=\;$
$\displaystyle\cdots$ $\displaystyle=\;$
$\displaystyle\mathbb{E}_{S_{0}\sim\mu_{b}}\left[\mathbb{I}_{\\{(s,a)=(S_{0},A_{0})\\}}\gamma^{i}[(P_{\pi_{\bar{c}}}C_{\pi})^{i}(R+\gamma
P_{\pi_{\bar{\rho}}}D_{\pi}Q-Q)](S_{0},A_{0})\right]$ $\displaystyle=\;$
$\displaystyle\gamma^{i}\mu_{b}(s)\pi_{b}(a|s)\left[(P_{\pi_{\bar{c}}}C_{\pi})^{i}(R+\gamma
P_{\pi_{\bar{\rho}}}D_{\pi}Q-Q)\right](s,a)$ $\displaystyle=\;$
$\displaystyle\gamma^{i}\left[M(P_{\pi_{\bar{c}}}C_{\pi})^{i}(R+\gamma
P_{\pi_{\bar{\rho}}}D_{\pi}Q-Q)\right](s,a).$

It follows that

$\displaystyle\mathcal{T}_{e}(Q,\pi)$ $\displaystyle=\sum_{i=0}^{n-1}M(\gamma
P_{\pi_{\bar{c}}}C_{\pi})^{i}(R+\gamma P_{\pi_{\bar{\rho}}}D_{\pi}Q-Q)+Q$ (5)
$\displaystyle=\underbrace{\left(I-\sum_{i=0}^{n-1}M(\gamma
P_{\pi_{\bar{c}}}C_{\pi})^{i}(I-\gamma
P_{\pi_{\bar{\rho}}}D_{\pi})\right)}_{A}Q+\underbrace{\sum_{i=0}^{n-1}M(\gamma
P_{\pi_{\bar{c}}}C_{\pi})^{i}R}_{b}.$ (6)

    2. (b)

We now show the desired contraction property. For any $Q_{1},Q_{2}$ and $\pi$,
we have

$\displaystyle\|\mathcal{T}_{e}(Q_{1},\pi)-\mathcal{T}_{e}(Q_{2},\pi)\|_{\infty}\leq\|A\|_{\infty}\|Q_{1}-Q_{2}\|_{\infty}.$

Consider the matrix $A$, we can rewrite it by

$\displaystyle A$
$\displaystyle=\sum_{i=1}^{n}\gamma^{i}M(P_{\pi_{\bar{c}}}C_{\pi})^{i-1}(P_{\pi_{\bar{\rho}}}D_{\pi})-\sum_{i=0}^{n-1}\gamma^{i}M(P_{\pi_{\bar{c}}}C_{\pi})^{i}+I$
$\displaystyle=\gamma^{n}M(P_{\pi_{\bar{c}}}C_{\pi})^{n-1}(P_{\pi_{\bar{\rho}}}D_{\pi})+\sum_{i=1}^{n-1}\gamma^{i}M(P_{\pi_{\bar{c}}}C_{\pi})^{i-1}(P_{\pi_{\bar{\rho}}}D_{\pi}-P_{\pi_{\bar{c}}}C_{\pi})+(I-M).$
(7)

Since

$\displaystyle\left[P_{\pi_{\bar{\rho}}}D_{\pi}-P_{\pi_{\bar{c}}}C_{\pi}\right]((s,a),(s^{\prime},a^{\prime}))=P_{a}(s,s^{\prime})\left(\min(\bar{\rho}\pi_{b}(a^{\prime}|s^{\prime}),\pi(a^{\prime}|s^{\prime}))-\min(\bar{c}\pi_{b}(a^{\prime}|s^{\prime}),\pi(a^{\prime}|s^{\prime}))\right)\geq
0$

for any $(s,a)$ and $(s^{\prime},a^{\prime})$, the matrix $A$ has non-negative
entries. Therefore, we have

$\displaystyle\|A\|_{\infty}$ $\displaystyle=\|A\bm{1}\|_{\infty}$
($\bm{1}=(1,1,...,1)^{\top}$)
$\displaystyle=\left\|\bm{1}-\sum_{i=0}^{n-1}M(\gamma
P_{\pi_{\bar{c}}}C_{\pi})^{i}(I-\gamma
P_{\pi_{\bar{\rho}}}D_{\pi})\bm{1}\right\|_{\infty}$ $\displaystyle\leq
1-M_{\min}\sum_{i=0}^{n-1}(\gamma C_{\min})^{i}(1-\gamma)$
$\displaystyle=1-\frac{M_{\min}(1-\gamma)(1-(\gamma C_{\min})^{n})}{1-\gamma
C_{\min}},$

where in the first inequality we used $C_{\min}\bm{1}\leq C_{\pi}\bm{1}\leq
D_{\pi}\bm{1}\leq\bm{1}$ (component-wise). It follows that
$\mathcal{T}_{e}(\cdot,\pi)$ is a contraction mapping with respect to
$\|\cdot\|_{\infty}$, with contraction factor

$\displaystyle\gamma_{c}=1-\frac{M_{\min}(1-\gamma)(1-(\gamma
C_{\min})^{n})}{1-\gamma C_{\min}}.$

    3. (c)

The existence and uniqueness of the fixed-point of
$\mathcal{T}_{e}(\cdot,\pi)$ follows from Banach fixed-point theorem [4]. To
characterize the fixed-point, it is enough to show the modified Bellman’s
equation

$\displaystyle R+\gamma P_{\pi_{\bar{\rho}}}D_{\pi}Q-Q=0$

has a unique solution, i.e., the matrix $I-\gamma P_{\pi_{\bar{\rho}}}D_{\pi}$
is invertible. This is followed from

$\displaystyle\|P_{\pi_{\bar{\rho}}}D_{\pi}\|_{\infty}=\|P_{\pi_{\bar{\rho}}}D_{\pi}\bm{1}\|_{\infty}\leq\|P_{\pi_{\bar{\rho}}}\bm{1}\|_{\infty}=1.$

###  A.2 Proof of Lemma 2.1

  1. (1)

We begin with the Bellman’s equation for $Q^{\pi}$: $Q^{\pi}=R+\gamma
P_{\pi}Q^{\pi}$, and the modified Bellman’s equation for $Q^{\bar{\rho},\pi}$:
$Q^{\bar{\rho},\pi}=R+\gamma P_{\pi_{\bar{\rho}}}D_{\pi}Q^{\bar{\rho},\pi}$.
Take the difference between these two equations and we obtain:

$\displaystyle Q^{\bar{\rho},\pi}-Q^{\pi}$ $\displaystyle=\gamma
P_{\pi_{\bar{\rho}}}D_{\pi}Q^{\bar{\rho},\pi}-\gamma P_{\pi}Q^{\pi}$
$\displaystyle=\gamma P_{\pi_{\bar{\rho}}}D_{\pi}Q^{\bar{\rho},\pi}-\gamma
P_{\pi_{\bar{\rho}}}D_{\pi}Q^{\pi}+\gamma
P_{\pi_{\bar{\rho}}}D_{\pi}Q^{\pi}-\gamma P_{\pi}Q^{\pi}$
$\displaystyle=\gamma
P_{\pi_{\bar{\rho}}}D_{\pi}(Q^{\bar{\rho},\pi}-Q^{\pi})+\gamma(P_{\pi_{\bar{\rho}}}D_{\pi}-P_{\pi})Q^{\pi}.$

Therefore, we have

$\displaystyle\left\|Q^{\bar{\rho},\pi}-Q^{\pi}\right\|_{\infty}$
$\displaystyle=\left\|(I-\gamma
P_{\pi_{\bar{\rho}}}D_{\pi})^{-1}\gamma(P_{\pi_{\bar{\rho}}}D_{\pi}-P_{\pi})Q^{\pi}\right\|_{\infty}$
$\displaystyle\leq\gamma\left\|(I-\gamma
P_{\pi_{\bar{\rho}}}D_{\pi})^{-1}\right\|_{\infty}\left\|P_{\pi_{\bar{\rho}}}D_{\pi}-P_{\pi}\right\|_{\infty}\left\|Q^{\pi}\right\|_{\infty}$
$\displaystyle\leq\frac{1}{1-\gamma}\left\|(I-\gamma
P_{\pi_{\bar{\rho}}}D_{\pi})^{-1}\right\|_{\infty}\left\|P_{\pi_{\bar{\rho}}}D_{\pi}-P_{\pi}\right\|_{\infty}.$

Since

$\displaystyle[P_{\pi_{\bar{\rho}}}D_{\pi}-P_{\pi}]((s,a),(s^{\prime},a^{\prime}))$
$\displaystyle=P_{a}(s,s^{\prime})(\min(\bar{\rho}\pi_{b}(a^{\prime}|s^{\prime}),\pi(a^{\prime}|s^{\prime}))-\pi(a^{\prime}|s^{\prime}))$
$\displaystyle=P_{a}(s,s^{\prime})\min(\bar{\rho}\pi_{b}(a^{\prime}|s^{\prime})-\pi(a^{\prime}|s^{\prime}),0)$
$\displaystyle=-P_{a}(s,s^{\prime})\max(\pi(a^{\prime}|s^{\prime})-\bar{\rho}\pi_{b}(a^{\prime}|s^{\prime}),0)$
$\displaystyle\leq 0,$

we have

$\displaystyle\left\|P_{\pi_{\bar{\rho}}}D_{\pi}-P_{\pi}\right\|_{\infty}=\left\|(P_{\pi}-P_{\pi_{\bar{\rho}}}D_{\pi})\bm{1}\right\|_{\infty}\leq\max_{(s,a)}\max(\pi(a|s)-\bar{\rho}\pi_{b}(a|s),0).$

As for the term $\left\|(I-\gamma
P_{\pi_{\bar{\rho}}}D_{\pi})^{-1}\right\|_{\infty}$, note that for any
invertible matrix $G$ we have

$\displaystyle\left\|G^{-1}\right\|_{\infty}$ $\displaystyle=\max_{x\neq
0}\frac{\left\|G^{-1}x\right\|_{\infty}}{\|x\|_{\infty}}$
$\displaystyle=\max_{y\neq 0}\frac{\|y\|_{\infty}}{\|Gy\|_{\infty}}$ (Change
of variable)
$\displaystyle=\max_{y:\|y\|_{\infty}=1}\frac{1}{\|Gy\|_{\infty}}$
$\displaystyle=\frac{1}{\min_{y:\|y\|_{\infty}=1}\|Gy\|_{\infty}}.$

Therefore, we obtain

$\displaystyle\|(I-\gamma P_{\pi_{\bar{\rho}}}D_{\pi})^{-1}\|_{\infty}$
$\displaystyle=\frac{1}{\min_{y:\|y\|_{\infty}=1}\|(I-\gamma
P_{\pi_{\bar{\rho}}}D_{\pi})y\|_{\infty}}$
$\displaystyle\leq\frac{1}{1-\gamma\max_{y:\|y\|_{\infty}=1}\|P_{\pi_{\bar{\rho}}}D_{\pi}y\|_{\infty}}$
$\displaystyle\leq\frac{1}{1-\gamma}.$

It follows that

$\displaystyle\|Q^{\bar{\rho},\pi}-Q^{\pi}\|_{\infty}$
$\displaystyle\leq\frac{1}{1-\gamma}\|(I-\gamma
P_{\pi_{\bar{\rho}}}D_{\pi})^{-1}\|_{\infty}\|P_{\pi_{\bar{\rho}}}D_{\pi}-P_{\pi}\|_{\infty}$
$\displaystyle\leq\frac{1}{(1-\gamma)^{2}}\max_{(s,a)}\max(\pi(a|s)-\bar{\rho}\pi_{b}(a|s),0).$

  2. (2)

Similarly, we have

$\displaystyle\|Q^{\bar{\rho},\pi}\|_{\infty}=\|(I-\gamma
P_{\pi_{\bar{\rho}}}D_{\pi})^{-1}R\|_{\infty}\leq\|(I-\gamma
P_{\pi_{\bar{\rho}}}D_{\pi})^{-1}\|_{\infty}\|R\|_{\infty}\leq\frac{1}{1-\gamma}.$

###  A.3 Proof of Theorem 2.1

We begin by restating Theorem 2.1 in full details:

######  Theorem A.1.

Consider $Q_{k}$ of Algorithm 1. Suppose Assumption 2.1 is satisfied and the
constant stepsize $\alpha$ is chosen such that
$\alpha(\tau_{\alpha}+n+1)\leq\min\left(\frac{1}{12(\bar{\rho}+1)f(\bar{c},\gamma)},\frac{(1-\gamma_{c})^{2}}{8208(\bar{\rho}+1)^{2}f(\bar{c},\gamma)^{2}\log(|\mathcal{S}||\mathcal{A}|)}\right)$.
Then we have for all $k\geq\tau_{\alpha}+n+1$:

$\displaystyle\mathbb{E}[\|Q_{k}-Q^{\bar{\rho},\pi}\|_{\infty}^{2}]\leq\;$
$\displaystyle
3\left(\|Q_{0}-Q^{\bar{\rho},\pi}\|_{\infty}+\|Q^{\bar{\rho},\pi}\|_{\infty}+1\right)^{2}\left(1-\frac{1-\gamma_{c}}{2}\alpha\right)^{k-(\tau_{\alpha}+n+1)}$
$\displaystyle+\frac{8208e\log(|\mathcal{S}||\mathcal{A}|)}{(1-\gamma_{c})^{2}}(\bar{\rho}+1)^{2}f(\bar{c},\gamma)^{2}(\|Q^{\bar{\rho},\pi}\|_{\infty}+1)^{2}\alpha(\tau_{\alpha}+n+1).$

###### Proof of Theorem A.1.

To prove Theorem A.1, we will apply the results in [19]. For self-
containedness, we here restate Theorem 2.1 of [19] in the following.

######  Theorem A.2 (Theorem 2.1 in [19]).

Consider $\\{x_{k}\\}$ generated by the following stochastic approximation
algorithm: $x_{k+1}=x_{k}+\epsilon(F(x_{k},Y_{k})-x_{k})$. Suppose that

  1. (1)

The random process $\\{Y_{k}\\}$ is a Markov chain with finite state-space
$\mathcal{Y}$. Moreover, $\\{Y_{k}\\}$ has a unique stationary distribution
$\mu_{Y}$ and there exist $C_{1}>0$ and $u_{1}\in(0,1)$ such that
$\max_{y\in\mathcal{Y}}\|P^{k}(y,\cdot)-\mu_{Y}(\cdot)\|_{\text{TV}}\leq
C_{1}u_{1}^{k}$ for all $k\geq 0$.

  2. (2)

The operator $F:\mathbb{R}^{d}\times\mathcal{Y}\mapsto\mathbb{R}^{d}$
satisfies $\|F(x_{1},y)-F(x_{2},y)\|_{\infty}\leq
A_{1}\|x_{1}-x_{2}\|_{\infty}$ and $\|F(\bm{0},y)\|_{\infty}\leq B_{1}$ for
any $x_{1},x_{2}\in\mathbb{R}^{d}$ and $y\in\mathcal{Y}$.

  3. (3)

The expected operator $\bar{F}:\mathbb{R}^{d}\mapsto\mathbb{R}^{d}$ defined by
$\bar{F}(x)=\mathbb{E}_{Y\sim\mu_{Y}}[F(x,Y)]$ is a $\gamma_{c}^{\prime}$ –
contraction mapping with respect to $\|\cdot\|_{\infty}$. Denote the unique
fixed-point of $\bar{F}(\cdot)$ by $x^{*}$.

  4. (4)

The constant stepsize $\epsilon$ is chosen such that $\epsilon
t_{\epsilon}\leq\min\left(\frac{1}{4(A_{1}+1)},\frac{(1-\gamma_{c}^{\prime})^{2}}{912(A_{1}+1)^{2}\log(d)}\right)$,
where $t_{\epsilon}=\min\\{k\geq
0\;:\;\max_{y\in\mathcal{Y}}\|P^{k}(y,\cdot)-\mu_{Y}(\cdot)\|_{\text{TV}}\leq\epsilon\\}$.

Then the following inequality holds for all $k\geq t_{\epsilon}$:

$\displaystyle\mathbb{E}[\|x_{k}-x^{*}\|_{\infty}^{2}]\leq$ $\displaystyle
3\left(\|x_{0}-x^{*}\|_{\infty}+\|x_{0}\|_{\infty}+\frac{B_{1}}{A_{1}+1}\right)^{2}\left(1-\frac{1-\gamma_{c}^{\prime}}{2}\epsilon\right)^{k-t_{\epsilon}}$
$\displaystyle+\frac{912e\log(d)}{(1-\gamma_{c}^{\prime})^{2}}((A_{1}+1)\|x^{*}\|_{\infty}+B_{1})^{2}\epsilon
t_{\epsilon}.$

Proposition 3.1 enables us to apply Theorem A.2 to the $Q$-trace algorithm.
Therefore, when the constant stepsize $\alpha$ is chosen such that
$\alpha(\tau_{\alpha}+n+1)\leq\min\left(\frac{1}{12(\bar{\rho}+1)f(\bar{c},\gamma)},\frac{(1-\gamma_{c})^{2}}{8208(\bar{\rho}+1)^{2}f(\bar{c},\gamma)^{2}\log(|\mathcal{S}||\mathcal{A}|)}\right)$
(which is always possible since
$\alpha(\tau_{\alpha}+n+1)=\mathcal{O}(\alpha\log(1/\alpha))\rightarrow 0$ as
$\alpha\rightarrow 0$), we have for all $k\geq\tau_{\alpha}+n+1$:

$\displaystyle\mathbb{E}[\|Q_{k}-Q^{\bar{\rho},\pi}\|_{\infty}^{2}]\leq\;$
$\displaystyle
3\left(\|Q_{0}-Q^{\bar{\rho},\pi}\|_{\infty}+\|Q^{\bar{\rho},\pi}\|_{\infty}+1\right)^{2}\left(1-\frac{1-\gamma_{c}}{2}\alpha\right)^{k-(\tau_{\alpha}+n+1)}$
$\displaystyle+\frac{8208e\log(|\mathcal{S}||\mathcal{A}|)}{(1-\gamma_{c})^{2}}(\bar{\rho}+1)^{2}f(\bar{c},\gamma)^{2}(\|Q^{\bar{\rho},\pi}\|_{\infty}+1)^{2}\alpha(\tau_{\alpha}+n+1).$

∎

To go from Theorem A.1 to Theorem 2.1, notice that $Q_{0}=\bm{0}$ in the
$Q$-trace algorithm 1, and
$\|Q^{\bar{\rho},\pi}\|_{\infty}\leq\frac{1}{1-\gamma}$ for any
$\bar{\rho}\geq 1$ and $\pi\in\Pi$ (Lemma 2.1). Therefore, we have from
Theorem A.1 that for all $k\geq\tau_{\alpha}+n+1$:

$\displaystyle\mathbb{E}[\|Q_{k}-Q^{\bar{\rho},\pi}\|_{\infty}^{2}]\leq\;$
$\displaystyle
3\left(\|Q_{0}-Q^{\bar{\rho},\pi}\|_{\infty}+\|Q^{\bar{\rho},\pi}\|_{\infty}+1\right)^{2}\left(1-\frac{1-\gamma_{c}}{2}\alpha\right)^{k-(\tau_{\alpha}+n+1)}$
$\displaystyle+\frac{8208e\log(|\mathcal{S}||\mathcal{A}|)}{(1-\gamma_{c})^{2}}(\bar{\rho}+1)^{2}f(\bar{c},\gamma)^{2}(\|Q^{\bar{\rho},\pi}\|_{\infty}+1)^{2}\alpha(\tau_{\alpha}+n+1)$
$\displaystyle=\;$ $\displaystyle
3\left(2\|Q^{\bar{\rho},\pi}\|_{\infty}+1\right)^{2}\left(1-\frac{1-\gamma_{c}}{2}\alpha\right)^{k-(\tau_{\alpha}+n+1)}$
$\displaystyle+\frac{8208e\log(|\mathcal{S}||\mathcal{A}|)}{(1-\gamma_{c})^{2}}(\bar{\rho}+1)^{2}f(\bar{c},\gamma)^{2}(\|Q^{\bar{\rho},\pi}\|_{\infty}+1)^{2}\alpha(\tau_{\alpha}+n+1)$
($Q_{0}=\bm{0}$) $\displaystyle\leq\;$
$\displaystyle\frac{27}{(1-\gamma)^{2}}\left(1-\frac{1-\gamma_{c}}{2}\alpha\right)^{k-(\tau_{\alpha}+n+1)}$
$\displaystyle+\frac{32832e\log(|\mathcal{S}||\mathcal{A}|)}{(1-\gamma_{c})^{2}(1-\gamma)^{2}}(\bar{\rho}+1)^{2}f(\bar{c},\gamma)^{2}\alpha(\tau_{\alpha}+n+1)$
($\|Q^{\bar{\rho},\pi}\|_{\infty}\leq\frac{1}{1-\gamma}$) $\displaystyle=\;$
$\displaystyle\frac{c_{1}}{(1-\gamma)^{2}}\left(1-\frac{1-\gamma_{c}}{2}\alpha\right)^{k-(\tau_{\alpha}+n+1)}$
$\displaystyle+\frac{c_{2}\log(|\mathcal{S}||\mathcal{A}|)}{(1-\gamma_{c})^{2}(1-\gamma)^{2}}(\bar{\rho}+1)^{2}f(\bar{c},\gamma)^{2}\alpha(\tau_{\alpha}+n+1),$

where $c_{1}=27$ and $c_{2}=32832e$ are numerical constants.

###  A.4 Proof of Corollary 2.1.1

Under the same condition of Theorem 2.1, we have for all
$k\geq\tau_{\alpha}+n+1$:

$\displaystyle\mathbb{E}[\|Q_{k}-Q^{\pi}\|_{\infty}]$
$\displaystyle\leq\mathbb{E}[\|Q_{k}-Q^{\bar{\rho},\pi}\|_{\infty}]+\|Q^{\bar{\rho},\pi}-Q^{\pi}\|_{\infty}$
(Triangle inequality)
$\displaystyle\leq\mathbb{E}[\|Q_{k}-Q^{\bar{\rho},\pi}\|_{\infty}]+\frac{\max(0,1-\bar{\rho}\min_{s,a}\pi_{b}(a|s))}{(1-\gamma)^{2}}$
(Lemma 2.1)
$\displaystyle\leq\left(\mathbb{E}[\|Q_{k}-Q^{\bar{\rho},\pi}\|_{\infty}^{2}]\right)^{1/2}+\frac{\max(0,1-\bar{\rho}\min_{s,a}\pi_{b}(a|s))}{(1-\gamma)^{2}}$
(Jensen’s inequality)
$\displaystyle\leq(T_{1}+T_{2})^{1/2}+\frac{\max(0,1-\bar{\rho}\min_{s,a}\pi_{b}(a|s))}{(1-\gamma)^{2}}$
(Theorem 2.1)
$\displaystyle\leq\sqrt{T_{1}}+\sqrt{T_{2}}+\frac{\max(0,1-\bar{\rho}\min_{s,a}\pi_{b}(a|s))}{(1-\gamma)^{2}},$
($a^{2}+b^{2}\leq(a+b)^{2}$ for any $a,b\geq 0$)

where $T_{1}$ and $T_{2}$ are given in Theorem 2.1.

##  Appendix B Off-Policy Natural Actor-Critic Algorithm

###  B.1 Proof of Proposition 3.2

To prove this proposition, it is more convenient to write the update equation
for $\pi_{t}$ in Algorithm 2 as

$\displaystyle\pi_{t+1}(a|s)=\pi_{t}(a|s)\frac{\exp(\beta(Q_{t+1}(s,a)-V^{\pi_{t}}(s)))}{\sum_{a^{\prime}\in\mathcal{A}}\pi_{t}(a^{\prime}|s)\exp(\beta(Q_{t+1}(s,a^{\prime})-V^{\pi_{t}}(s)))}$

for all $(s,a)$. Denote
$Z_{t}(s)=\sum_{a\in\mathcal{A}}\pi_{t}(a|s)\exp(\beta(Q_{t+1}(s,a)-V^{\pi_{t}}(s)))$.
We first present a sequence of lemmas. The proofs are presented in Appendices
B.4.1, B.4.2, and B.4.3. Throughout the paper, given an initial distribution
$\mu$, we denote $d^{t}\equiv d_{\mu}^{\pi_{t}}$ and $d^{*}\equiv
d_{\mu}^{\pi^{*}}$, where we omit $\mu$ for the ease of notation.

######  Lemma B.1.

The following inequality holds for all $t\geq 0$ and $s\in\mathcal{S}$:

$\displaystyle\log(Z_{t}(s))\geq\beta\sum_{a\in\mathcal{A}}\pi_{t}(a|s)(Q_{t+1}(s,a)-Q^{\pi_{t}}(s,a)).$

######  Lemma B.2.

Consider the iterates $\\{\pi_{t}\\}$ in Algorithm 2. The following inequality
holds for any starting distribution $\mu$:

$\displaystyle V^{\pi_{t+1}}(\mu)-V^{\pi_{t}}(\mu)\geq\;$
$\displaystyle\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{t+1}}\sum_{a\in\mathcal{A}}(\pi_{t}(a|s)-\pi_{t+1}(a|s))(Q_{t+1}(s,a)-Q^{\pi_{t}}(s,a))$
$\displaystyle-\mathbb{E}_{s\sim\mu}\sum_{a\in\mathcal{A}}\pi_{t}(a|s)(Q_{t+1}(s,a)-Q^{\pi_{t}}(s,a))+\frac{1}{\beta}\mathbb{E}_{s\sim\mu}\log
Z_{t}(s).$

######  Lemma B.3.

For any starting distribution $\mu$, we have for any $t\geq 0$:

$\displaystyle V^{\pi^{*}}(\mu)-V^{\pi_{t}}(\mu)=\;$
$\displaystyle\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{*}}\sum_{a\in\mathcal{A}}\pi^{*}(a|s)(Q^{\pi_{t}}(s,a)-Q_{t+1}(s,a))+\frac{1}{(1-\gamma)\beta}\mathbb{E}_{s\sim
d^{*}}\log(Z_{t}(s))$
$\displaystyle+\frac{1}{(1-\gamma)\beta}\mathbb{E}_{s\sim
d^{*}}\left[\mathcal{KL}(\pi^{*}(\cdot|s)\mid\pi_{t}(\cdot|s))-\mathcal{KL}(\pi^{*}(\cdot|s)\mid\pi_{t+1}(\cdot|s))\right].$

Now we proceed to prove Proposition 3.2. Letting $\mu=d^{*}$, we have by Lemma
B.2 that

$\displaystyle V^{\pi_{t+1}}(d^{*})-V^{\pi_{t}}(d^{*})\geq\;$
$\displaystyle\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{t+1}_{d^{*}}}\sum_{a\in\mathcal{A}}(\pi_{t}(a|s)-\pi_{t+1}(a|s))(Q_{t+1}(s,a)-Q^{\pi_{t}}(s,a))$
$\displaystyle-\mathbb{E}_{s\sim
d^{*}}\sum_{a\in\mathcal{A}}\pi_{t}(a|s)(Q_{t+1}(s,a)-Q^{\pi_{t}}(s,a))+\frac{1}{\beta}\mathbb{E}_{s\sim
d^{*}}\log Z_{t}(s).$

It follows that

$\displaystyle\frac{1}{\beta}\mathbb{E}_{s\sim d^{*}}\log Z_{t}(s)\leq
V^{\pi_{t+1}}(d^{*})-V^{\pi_{t}}(d^{*})+\frac{3}{1-\gamma}\|Q_{t+1}-Q^{\pi_{t}}\|_{\infty}.$
(8)

Now for any $T\geq 1$, we have

$\displaystyle\sum_{t=0}^{T-1}(V^{\pi^{*}}(\mu)-V^{\pi_{t}}(\mu))$
$\displaystyle=\;$
$\displaystyle\frac{1}{1-\gamma}\sum_{t=0}^{T-1}\mathbb{E}_{s\sim
d^{*}}\sum_{a\in\mathcal{A}}\pi^{*}(a|s)(Q^{\pi_{t}}(s,a)-Q_{t+1}(s,a))+\frac{1}{(1-\gamma)\beta}\sum_{t=0}^{T-1}\mathbb{E}_{s\sim
d^{*}}\log(Z_{t}(s))$
$\displaystyle+\frac{1}{(1-\gamma)\beta}\sum_{t=0}^{T-1}\mathbb{E}_{s\sim
d^{*}}\left[\mathcal{KL}(\pi^{*}(\cdot|s)\mid\pi_{t}(\cdot|s))-\mathcal{KL}(\pi^{*}(\cdot|s)\mid\pi_{t+1}(\cdot|s))\right]$
$\displaystyle\leq\;$
$\displaystyle\frac{1}{1-\gamma}\sum_{t=0}^{T-1}\|Q^{\pi_{t}}-Q_{t+1}\|_{\infty}+\frac{1}{1-\gamma}\sum_{t=0}^{T-1}\left[V^{\pi_{t+1}}(d^{*})-V^{\pi_{t}}(d^{*})+\frac{3}{1-\gamma}\|Q^{\pi_{t}}-Q_{t+1}\|_{\infty}\right]$
(Eq. (8))
$\displaystyle+\frac{1}{(1-\gamma)\beta}\sum_{t=0}^{T-1}\mathbb{E}_{s\sim
d^{*}}\left[\mathcal{KL}(\pi^{*}(\cdot|s)\mid\pi_{t}(\cdot|s))-\mathcal{KL}(\pi^{*}(\cdot|s)\mid\pi_{t+1}(\cdot|s))\right]$
$\displaystyle\leq\;$
$\displaystyle\frac{1}{1-\gamma}\sum_{t=0}^{T-1}\|Q^{\pi_{t}}-Q_{t+1}\|_{\infty}+\frac{1}{1-\gamma}(V^{\pi_{T}}(d^{*})-V^{\pi_{0}}(d^{*}))+\frac{3}{(1-\gamma)^{2}}\sum_{t=0}^{T-1}\|Q^{\pi_{t}}-Q_{t+1}\|_{\infty}$
$\displaystyle+\frac{1}{(1-\gamma)\beta}\mathbb{E}_{s\sim
d^{*}}\left[\mathcal{KL}(\pi^{*}(\cdot|s)\mid\pi_{0}(\cdot|s))-\mathcal{KL}(\pi^{*}(\cdot|s)\mid\pi_{T}(\cdot|s))\right]$
$\displaystyle\leq\;$
$\displaystyle\frac{4}{(1-\gamma)^{2}}\sum_{t=0}^{T-1}\|Q^{\pi_{t}}-Q_{t+1}\|_{\infty}+\frac{1}{(1-\gamma)^{2}}+\frac{\log(\mathcal{A})}{(1-\gamma)\beta}.$

Therefore, we have from the previous inequality:

$\displaystyle V^{\pi^{*}}(\mu)-\max_{0\leq t\leq
T-1}\mathbb{E}\left[V^{\pi_{t}}(\mu)\right]$ $\displaystyle\leq
V^{\pi^{*}}(\mu)-\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[V^{\pi_{t}}(\mu)\right]$
$\displaystyle\leq\frac{1}{(1-\gamma)^{2}T}+\frac{\log(|\mathcal{A}|)}{(1-\gamma)\beta
T}+\frac{4}{(1-\gamma)^{2}T}\sum_{t=0}^{T-1}\mathbb{E}[\|Q^{\pi_{t}}-Q_{t+1}\|_{\infty}]$
$\displaystyle\leq\frac{\log(e|\mathcal{A}|)}{(1-\gamma)^{2}\beta
T}+\frac{4}{(1-\gamma)^{2}T}\sum_{t=0}^{T-1}\mathbb{E}[\|Q^{\pi_{t}}-Q_{t+1}\|_{\infty}]$

###  B.2 Proof of Theorem 2.2

Our goal is to combine Proposition 3.2 with Corollary 2.1.1. The only
challenge remains is that Corollary 2.1.1 is stated for a fixed target policy
$\pi$ while $\pi_{t}$ is stochastic. To overcome this difficulty, observe that
$\pi_{t}$ is determined by $\\{(S_{k},A_{k})\\}_{0\leq k\leq t(K+n)}$ while
$Q_{t+1}$ is determined by $\pi_{t}$ and $\\{(S_{k},A_{k})\\}_{t(K+n)\leq
k\leq(t+1)(K+n)}$. Therefore, by the Markov property and the tower property of
conditional expectation, we have for any $0\leq t\leq T-1$:

$\displaystyle\mathbb{E}[\|Q_{t+1}-Q^{\bar{\rho},\pi_{t}}\|_{\infty}]$
$\displaystyle=\;$
$\displaystyle\mathbb{E}\left[\mathbb{E}[\|Q_{t+1}-Q^{\bar{\rho},\pi_{t}}\|_{\infty}\mid
S_{0},A_{0},...,S_{t(K+n)}.A_{t(K+n)}]\right]$ $\displaystyle\leq\;$
$\displaystyle\sqrt{T_{1}}+\sqrt{T_{2}}+\frac{\max(0,1-\bar{\rho}\min_{s,a}\pi_{b}(a|s))}{(1-\gamma)^{2}}$
$\displaystyle\leq\;$
$\displaystyle\frac{\sqrt{c_{1}}}{1-\gamma}\left(1-\frac{1-\gamma_{c}}{2}\alpha\right)^{\frac{1}{2}[K-(\tau_{\alpha}+n+1)]}+\frac{\sqrt{c_{2}}\log^{1/2}(|\mathcal{S}||\mathcal{A}|)}{(1-\gamma_{c})(1-\gamma)}(\bar{\rho}+1)f(\bar{c},\gamma)[\alpha(\tau_{\alpha}+n+1)]^{1/2}$
$\displaystyle+\frac{\max(0,1-\bar{\rho}\min_{s,a}\pi_{b}(a|s))}{(1-\gamma)^{2}}$
$\displaystyle\leq\;$
$\displaystyle\frac{6}{1-\gamma}\left(1-\frac{1-\gamma_{c}}{2}\alpha\right)^{\frac{1}{2}[K-(\tau_{\alpha}+n+1)]}+\frac{300\log^{1/2}(|\mathcal{S}||\mathcal{A}|)}{(1-\gamma_{c})(1-\gamma)}(\bar{\rho}+1)f(\bar{c},\gamma)[\alpha(\tau_{\alpha}+n+1)]^{1/2}$
$\displaystyle+\frac{\max(0,1-\bar{\rho}\min_{s,a}\pi_{b}(a|s))}{(1-\gamma)^{2}}$
(9)

where in the last line we used $c_{1}=27$ and $c_{2}=32832e$.

Using Eq. (9) in Proposition 3.2, we have for all $T\geq 1$:

$\displaystyle V^{\pi^{*}}(\mu)-\max_{0\leq t\leq
T-1}\mathbb{E}\left[V^{\pi_{t}}(\mu)\right]$ $\displaystyle\leq\;$
$\displaystyle
V^{\pi^{*}}(\mu)-\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[V^{\pi_{t}}(\mu)\right]$
$\displaystyle\leq\;$
$\displaystyle\frac{\log(e|\mathcal{A}|)}{(1-\gamma)^{2}\beta
T}+\frac{4}{(1-\gamma)^{2}T}\sum_{t=0}^{T-1}\mathbb{E}[\|Q^{\pi_{t}}-Q_{t+1}\|_{\infty}]$
$\displaystyle\leq\;$
$\displaystyle\frac{\log(e|\mathcal{A}|)}{(1-\gamma)^{2}\beta
T}+\frac{4\max(0,(1-\bar{\rho}\min_{s,a}\pi_{b}(a|s)))}{(1-\gamma)^{4}}+\frac{24}{(1-\gamma)^{3}}\left(1-\frac{1-\gamma_{c}}{2}\alpha\right)^{\frac{1}{2}[K-(\tau_{\alpha}+n+1)]}$
$\displaystyle+\frac{1200\log^{1/2}(|\mathcal{S}||\mathcal{A}|)}{(1-\gamma)^{3}(1-\gamma_{c})}(\bar{\rho}+1)f(\bar{c},\gamma)[\alpha(\tau_{\alpha}+n+1)]^{1/2}.$

This proves Theorem 2.2.

###  B.3 Proof of Corollary 2.2.2

We begin with the result of Theorem 2.2 when
$\bar{\rho}=\frac{1}{\min_{s,a}\pi_{b}(a|s)}$ (which ensures $E_{3}=0$):

$\displaystyle V^{\pi^{*}}(\mu)-\max_{0\leq t\leq
T-1}\mathbb{E}\left[V^{\pi_{t}}(\mu)\right]\leq\;$
$\displaystyle\underbrace{\frac{24}{(1-\gamma)^{3}}\left(1-\frac{M_{\min}(1-\gamma)(1-(\gamma
C_{\min})^{n})}{2(1-\gamma
C_{\min})}\alpha\right)^{\frac{1}{2}(K-(\tau_{\alpha}+n+1))}}_{E_{1}}$
$\displaystyle+\underbrace{\frac{1200(1-\gamma
C_{\min})\log^{1/2}(|\mathcal{S}||\mathcal{A}|)}{M_{\min}(1-\gamma)^{4}(1-(\gamma
C_{\min})^{n})}(\bar{\rho}+1)f(\bar{c},\gamma)[\alpha(\tau_{\alpha}+n+1)]^{1/2}}_{E_{2}}$
$\displaystyle+\underbrace{\frac{\log(e|\mathcal{A}|)}{(1-\gamma)^{2}\beta
T}}_{E_{4}},$

where we used the explicit expression of $\gamma_{c}$ in Proposition 3.1 (3)
(b). Our goal is to obtain an $\epsilon$-optimal policy, i.e.,
$V^{\pi^{*}}(\mu)-\max_{0\leq t\leq
T-1}\mathbb{E}\left[V^{\pi_{t}}(\mu)\right]\leq\epsilon$.

We begin with the term $E_{4}$. It is clear that in order for
$E_{4}\leq\epsilon$, we need to have
$T=\mathcal{O}(\epsilon^{-1}(1-\gamma)^{-2})$. Now consider the term $E_{2}$.
Since $\tau_{\alpha}\leq L(\log(1/\alpha)+1)$ for some $L>0$, the inequality
$E_{2}\leq\epsilon$ implies

$\displaystyle\alpha\sim\tilde{\mathcal{O}}\left(\frac{(1-\gamma)^{8}M_{\min}^{2}}{\bar{\rho}^{2}}\right)\mathcal{O}\left(\frac{\epsilon^{2}}{\log(1/\epsilon)}\right)$

Finally, using $\alpha$ in the term $E_{1}$ and the inequality that $e^{x}\geq
1+x$ for all $x\in\mathbb{R}$, then we have $E_{1}\leq\epsilon$ when

$\displaystyle
K=\mathcal{O}(\epsilon^{-2}\log^{2}(1/\epsilon))\tilde{\mathcal{O}}((1-\gamma)^{-9}M_{\min}^{-3}\bar{\rho}^{2})$

It follows that the sample complexity is

$\displaystyle
TK=\mathcal{O}(\epsilon^{-3}\log^{2}(1/\epsilon))\tilde{\mathcal{O}}((1-\gamma)^{-11}M_{\min}^{-3}\bar{\rho}^{2})$

To determine the dependence on the size of the state-action space, observe
that

$\displaystyle
M_{\min}=\min_{s,a}\mu_{b}(s)\pi_{b}(a|s)\leq\frac{1}{|\mathcal{S}||\mathcal{A}|}\quad\text{and}\quad\bar{\rho}=\frac{1}{\min_{s,a}\pi_{b}(a|s)}\geq|\mathcal{A}|,$

where the equalities are attained when $\mu_{b}(s)=\frac{1}{|\mathcal{S}|}$
for all $s$ and $\pi_{b}(a|s)=\frac{1}{|\mathcal{A}|}$ for all $a$. Therefore,
we have at least $\mathcal{O}(|\mathcal{S}|^{3}|\mathcal{A}|^{5})$ dependence
on the state and action space.

###  B.4 Proof of All Technical Lemmas

####  B.4.1 Proof of Lemma B.1

Using the update rule of $\pi_{t}$ in Algorithm 2 and we have for any $t\geq
0$ and $s\in\mathcal{S}$:

$\displaystyle\log(Z_{t}(s))$
$\displaystyle=\log\left[\sum_{a\in\mathcal{A}}\pi_{t}(a|s)\exp(\beta(Q_{t+1}(s,a)-V^{\pi_{t}}(s))\right]$
$\displaystyle\geq\beta\sum_{a\in\mathcal{A}}\pi_{t}(a|s)(Q_{t+1}(s,a)-V^{\pi_{t}}(s))$
(Jensen’s inequality)
$\displaystyle=\beta\sum_{a\in\mathcal{A}}\pi_{t}(a|s)(Q_{t+1}(s,a)-Q^{\pi_{t}}(s,a)).$

####  B.4.2 Proof of Lemma B.2

For any starting distribution $\mu$, we have

$\displaystyle V^{\pi_{t+1}}(\mu)-V^{\pi_{t}}(\mu)=\;$
$\displaystyle\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{t+1}}\sum_{a\in\mathcal{A}}\pi_{t+1}(a|s)A^{\pi_{t}}(s,a)$ (Performance
Difference Lemma) $\displaystyle=\;$
$\displaystyle\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{t+1}}\sum_{a\in\mathcal{A}}\pi_{t+1}(a|s)(Q^{\pi_{t}}(s,a)-Q_{t+1}(s,a)+Q_{t+1}(s,a)-V^{\pi_{t}}(s))$
$\displaystyle=\;$ $\displaystyle\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{t+1}}\sum_{a\in\mathcal{A}}\pi_{t+1}(a|s)(Q^{\pi_{t}}(s,a)-Q_{t+1}(s,a))$
$\displaystyle+\frac{1}{(1-\gamma)\beta}\mathbb{E}_{s\sim
d^{t+1}}\sum_{a\in\mathcal{A}}\pi_{t+1}(a|s)\log\left(\frac{\pi_{t+1}(a|s)}{\pi_{t}(a|s)}Z_{t}(s)\right)$
(Algorithm 2) $\displaystyle=\;$
$\displaystyle\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{t+1}}\sum_{a\in\mathcal{A}}\pi_{t+1}(a|s)(Q^{\pi_{t}}(s,a)-Q_{t+1}(s,a))$
$\displaystyle+\frac{1}{(1-\gamma)\beta}\mathbb{E}_{s\sim
d^{t+1}}\mathcal{KL}(\pi_{t+1}(\cdot|s)\mid\pi_{t}(\cdot|s))+\frac{1}{(1-\gamma)\beta}\mathbb{E}_{s\sim
d^{t+1}}\log Z_{t}(s)$ $\displaystyle\geq\;$
$\displaystyle\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{t+1}}\sum_{a\in\mathcal{A}}\pi_{t+1}(a|s)(Q^{\pi_{t}}(s,a)-Q_{t+1}(s,a))+\frac{1}{(1-\gamma)\beta}\mathbb{E}_{s\sim
d^{t+1}}\log Z_{t}(s)$ $\displaystyle=\;$
$\displaystyle\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{t+1}}\sum_{a\in\mathcal{A}}\pi_{t+1}(a|s)(Q^{\pi_{t}}(s,a)-Q_{t+1}(s,a))$
$\displaystyle+\frac{1}{(1-\gamma)\beta}\mathbb{E}_{s\sim d^{t+1}}\left[\log
Z_{t}(s)-\beta\sum_{a\in\mathcal{A}}\pi_{t}(a|s)(Q_{t+1}(s,a)-Q^{\pi_{t}}(s,a))\right]$
$\displaystyle+\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{t+1}}\sum_{a\in\mathcal{A}}\pi_{t}(a|s)(Q_{t+1}(s,a)-Q^{\pi_{t}}(s,a))$
$\displaystyle\geq\;$ $\displaystyle\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{t+1}}\sum_{a\in\mathcal{A}}(\pi_{t}(a|s)-\pi_{t+1}(a|s))(Q_{t+1}(s,a)-Q^{\pi_{t}}(s,a))$
$\displaystyle+\frac{1}{\beta}\mathbb{E}_{s\sim\mu}\left[\log
Z_{t}(s)-\beta\sum_{a\in\mathcal{A}}\pi_{t}(a|s)(Q_{t+1}(s,a)-Q^{\pi_{t}}(s,a))\right]$
($d^{t+1}\geq(1-\gamma)\mu$ and Lemma B.1) $\displaystyle=\;$
$\displaystyle\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{t+1}}\sum_{a\in\mathcal{A}}(\pi_{t}(a|s)-\pi_{t+1}(a|s))(Q_{t+1}(s,a)-Q^{\pi_{t}}(s,a))$
$\displaystyle-\mathbb{E}_{s\sim\mu}\sum_{a\in\mathcal{A}}\pi_{t}(a|s)(Q_{t+1}(s,a)-Q^{\pi_{t}}(s,a))+\frac{1}{\beta}\mathbb{E}_{s\sim\mu}\log
Z_{t}(s).$

####  B.4.3 Proof of Lemma B.3

Using the update rule of $\pi_{t}$ in Algorithm 2 and we have for any $t\geq
0$ and $s\in\mathcal{S}$:

$\displaystyle V^{\pi^{*}}(\mu)-V^{\pi_{t}}(\mu)=\;$
$\displaystyle\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{*}}\sum_{a\in\mathcal{A}}\pi^{*}(a|s)A^{\pi_{t}}(s,a)$ (Performance
Difference Lemma) $\displaystyle=\;$
$\displaystyle\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{*}}\sum_{a\in\mathcal{A}}\pi^{*}(a|s)(Q^{\pi_{t}}(s,a)-Q_{t+1}(s,a)+Q_{t+1}(s,a)-V^{\pi_{t}}(s))$
$\displaystyle=\;$ $\displaystyle\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{*}}\sum_{a\in\mathcal{A}}\pi^{*}(a|s)(Q^{\pi_{t}}(s,a)-Q_{t+1}(s,a))$
$\displaystyle+\frac{1}{(1-\gamma)\beta}\mathbb{E}_{s\sim
d^{*}}\sum_{a\in\mathcal{A}}\pi^{*}(a|s)\log\left(\frac{\pi_{t+1}(a|s)}{\pi_{t}(a|s)}Z_{t}(s)\right)$
(Algorithm 2) $\displaystyle=\;$
$\displaystyle\frac{1}{1-\gamma}\mathbb{E}_{s\sim
d^{*}}\sum_{a\in\mathcal{A}}\pi^{*}(a|s)(Q^{\pi_{t}}(s,a)-Q_{t+1}(s,a))+\frac{1}{(1-\gamma)\beta}\mathbb{E}_{s\sim
d^{*}}\log(Z_{t}(s))$
$\displaystyle+\frac{1}{(1-\gamma)\beta}\mathbb{E}_{s\sim
d^{*}}\left[\mathcal{KL}(\pi^{*}(\cdot|s)\mid\pi_{t}(\cdot|s))-\mathcal{KL}(\pi^{*}(\cdot|s)\mid\pi_{t+1}(\cdot|s))\right]$

##  Appendix C Related Literature

###  C.1 Interpretation of Convergence Rate in terms of Sample Complexity

Suppose we have a stochastic approximation algorithm that arises in RL, which
has the following convergence bound:

$\displaystyle\text{Error}\leq\frac{1}{T}+E_{0},$ (10)

where $T$ is the number of iterations, and $E_{0}$ represents certain error
that cannot be eliminated asymptotically. For example, when studying TD-
learning with function approximation, $E_{0}$ represents the approximation
error, i.e., the gap between the true value function and the best value
function offered by the approximating function space.

####  C.1.1 Global Convergence

Consider the case where $E_{0}=0$. In this case, sample complexity is well-
defined, and it stands for the number of samples required to make the
appropriately defined error $\epsilon$. In the TD-learning example, this
corresponds to using a tabular representation. Specifically, in view of Eq.
(10), the convergence rate is $\mathcal{O}(1/T)$. Moreover, suppose every
iteration requires one sample. Then to obtain $\epsilon$ accuracy, the amount
of sample required is $\mathcal{O}(\epsilon^{-1})$.

####  C.1.2 Convergence in the Presence of a Bias

Now consider the case where $E_{0}\neq 0$. We argue that the definition of
sample complexity in unclear, and needs careful consideration. In the TD-
learning example, this corresponds to using function approximation, which
induces an unbeatable error due to the limitation of the approximating
function space. A similar situation arises in off-policy NAC algorithm studied
in this paper if the IS ratios are truncated to a certain level.

Suppose we apply the AM-GM inequality
$\frac{1}{N}\sum_{i=1}^{N}x_{i}\geq(\prod_{i=1}^{N}x_{i})^{1/N}$ ($x_{i}\geq
0$ for all $i$ and $N\in\mathbb{Z}^{+}$) to the RHS of Eq. (10). Then we
obtain for any $a>0$ and $N\geq 1$:

Error $\displaystyle\leq\frac{1}{T}+E_{0}$
$\displaystyle=\left(\frac{1}{T^{N}a^{N-1}}\times a^{N-1}\right)^{1/N}+E_{0}$
$\displaystyle\leq\frac{1}{N}\left(\frac{1}{T^{N}a^{N-1}}+\underbrace{a+a+\cdots+a}_{N-1}\right)+E_{0}$
$\displaystyle=\frac{1}{Na^{N-1}}\frac{1}{T^{N}}+\left(1-\frac{1}{N}\right)a+E_{0}.$
(11)

Now if we choose $a=E_{0}$, then the previous inequality can be written as

Error
$\displaystyle\leq\frac{1}{NE_{0}^{N-1}}\frac{1}{T^{n}}+\left(2-\frac{1}{N}\right)E_{0}$
(12)
$\displaystyle=\mathcal{O}\left(\frac{1}{T^{N}}\right)+\mathcal{O}(E_{0}).$
(13)

While the derivation in (12) is correct, it leads to the following misleading
interpretation:

We have a sample complexity of $\mathcal{O}(\epsilon^{-1/N})$ with an
asymptotic error of size $\mathcal{O}(E_{0})$ for any $N\geq 1$.

Clearly, this interpretation is incorrect. By using the AM-GM trick, we
obtained a better rate of convergence, but with a worse asymptotic error.
Therefore, as long as one does not have global convergence (i.e., $E_{0}\neq
0$), it is not entirely clear how to define sample complexity. One possible
way out of this confusion is to define sample complexity only when the
asymptotic error is exactly $E_{0}$ (instead of the weakened
$\mathcal{O}(E_{0})$). An alternate way is to define sample complexity in
terms of convergence to the exact solution of a modified problem, and then
separately characterize the error between the solution of the original problem
and the modified problem. This was the approach taken in the classic paper on
TD with linear function approximation [68].

####  C.1.3 The results in [76] and [77]

Convergence of AC type algorithms was studied in [76] and [77] under linear
function approximation. A special case of linear function approximation is the
tabular setting, where the feature vectors are chosen to be the canonical
basis vectors. However, in this case, the results in [76] and [77] do not
guarantee global convergence because of the presence of additive constants in
the error (for any choice of $\lambda$ as defined in [76, 77]).

Now, consider the case of linear function approximation. We believe that the
sample complexity of $\tilde{\mathcal{O}}(\epsilon^{-2.5})$ for AC and
$\tilde{\mathcal{O}}(\epsilon^{-4})$ sample complexity for NAC claimed in [77]
and $\tilde{\mathcal{O}}(\epsilon^{-2})$ sample complexity for NAC claimed in
[76] are misleading because they were essentially obtained in the manner
described in Section C.1.2. We present more details below.

However, if one agrees with the interpretation of the sample complexity
results in [76, 77], then our sample complexity results can also be “improved”
in the same sense as those in [76, 77] to $\mathcal{O}(\epsilon^{-1/N})$ for
any $N>0$ by doubling the asymptotic error from $E_{3}$ to $2E_{3}$ (where the
term $E_{3}$ is the truncation error given in Theorem 2.2). This can be done
by applying the AM-GM inequality described in Section C.1.2 to the result of
Theorem 2.2. In fact, for any convergence bounds of the form (10) in the
literature, one can use the same technique to obtain arbitrarily good
convergence rate and sample complexity.

##### The paper [76]:

Now we illustrate how [76] uses the AM-GM trick described above implicitly. In
Algorithm 1 (Actor-critic (AC) and natural actor-critic (NAC) online
algorithms), the parameter $\lambda$ (line 19 of Algorithm 1) is introduced.
In the statement of their main result (Eq. (31) of Theorem 6 in Appendix G),
the parameter $\lambda$ appears both in the denominator of the $1/T$ terms
(which is not revealed in Theorem 3 of their main paper) and the numerator of
the constant terms. We see that the role of the parameter $\lambda$ is
essentially equivalent to the tunable constant $a$ introduced in Eq. (11) of
our above derivation. Later the parameter $\lambda$ is set to be equal to
$\sqrt{\zeta^{critic}_{approx}}$ (where $\zeta^{critic}_{approx}$ is the
unbeatable error due to function approximation in TD-learning) so that the
additive constant terms are absorbed into the
$\mathcal{O}(\sqrt{\zeta^{critic}_{approx}})$ term, which eventually leads to
their claim of obtaining $\tilde{\mathcal{O}}(\epsilon^{-2})$ sample
complexity of NAC. This is analogous to going from Eq. (11) to Eq. (13) of our
derivation in Section C.1.2 by setting $a=E_{0}$.

##### The paper [77]:

Now we illustrate how the proof in [77] is essentially equivalent to using the
AM-GM trick described above. In Algorithm 1 (Two Time-scale AC and NAC), the
parameter $\lambda$ is introduced to perform the critic update. Later in the
third bullet point on the same page of Algorithm 1, the parameter $R_{\theta}$
is set to be $\mathcal{O}(\lambda^{-1})$.

Consider the resulting bounds in all 5 cases in step 3 of the proof of Theorem
2 (Appendix C). The parameter $\lambda$ appears in the numerator of the
constant term while the parameter $R_{\theta}=\mathcal{O}(\lambda^{-1})$
appears quadratically in the $1/t^{1-\sigma}$ term (which is not revealed in
the statement of Theorem 2 in the main paper). This leads to the claim of
$\mathcal{O}(\epsilon^{-2.5})$ sample complexity for AC with asymptotic error
$\mathcal{O}(\lambda)$. We believe this is analogous to Eq. (11) of our above
derivation.

Consider the resulting bounds in all 5 cases in step 2 of the proof of Theorem
3 (Appendix D). The parameter $\lambda$ appears in the numerator of the
constant term while the parameter $R_{\theta}=\mathcal{O}(\lambda^{-1})$
appears quadratically in the $1/t^{1-\sigma}$ term (which is not revealed in
the statement of Theorem 3 in the main paper). In Theorem 3, the parameter
$\lambda$ is set to be $\mathcal{O}(\sqrt{\xi_{approx}^{\prime}})$, which
eventually leads the claim of $\mathcal{O}(\epsilon^{-4})$ sample complexity
for NAC with asymptotic accuracy $\mathcal{O}(\sqrt{\xi_{approx}^{\prime}})$.
We believe this is analogous to Eqs. (12) and (13) of our above derivation.

###  C.2 Single Trajectory

The AC and NAC algorithms presented in [77] and [76] appear to be based on a
single trajectory, at first glance. The single sample path is not from the
original transition matrix $P$, but is from a modified transition matrix,
$\tilde{P}(\cdot\mid s,a)=\gamma P(\cdot\mid s,a)+(1-\gamma)\xi(\cdot)$, where
$\xi(\cdot)$ is the initial distribution. Now, in order to sample from the
modified transition matrix $\tilde{P}$, one has to sample from the original
matrix $P$ with probability $\gamma$ and reset to a state sampled from
$\xi(\cdot)$ with probability $(1-\gamma)$. Thus, in reality, the algorithms
in [77, 76] are not based on a single trajectory. This is made explicitly
clear in [71] (Section 3.2.1. Actor Update: Sampling From Visitation Measure),
where the same modified transition matrix $\tilde{P}$ was used.

###  C.3 The Issue of Exploration

A major issue with on-policy AC and NAC is exploration. In related literature,
to establish convergence bounds, usually it requires either hard-to-satisfy
assumptions to ensure exploration, or additional exploration steps which slow
down the convergence rate.

####  C.3.1 Hard-to-Satisfy Assumptions

The convergence of AC type methods have been established in several previous
work. Each of these results require some regularity assumptions on the
underlying system. However, in the simple tabular setting, one can show that
these assumptions fail to hold. In particular, Assumption 4.1 in [75],
Assumption 1 in [76, 77, 38], and Assumption 3.3 in [58] in the tabular
setting imply the sequence of policies $\\{\pi_{t}\\}$ generated by the
algorithm satisfy $\pi_{t}(a|s)\geq\delta>0$, for all $s,a$ and $t$. This
assumption in conjunction with the irreducibility assumption of the underlying
Markov chain under all the policies, one can show that all the state and
actions will be visited infinitely often as the AC algorithm proceeds.

The above mentioned assumption means that all the elements of the policy table
must attain at least positive value $\delta$ uniformly over time. However, a
well known result shows that, for every MDP there always exist an optimal
deterministic policy [57]. In particular, one can construct MDPs with a unique
deterministic optimal policy. In such examples, some of the elements of
$\pi_{t}$ should converge to zero as the AC algorithm proceeds, and this
violates the aforementioned assumptions. For more information, look at Section
4 in [36] where an experimental implementation of NAC shows that $\pi_{t}$
indeed converges to a deterministic policy.

####  C.3.2 Additional Exploration Steps

One way of avoiding the assumption mentioned in the previous subsection is to
artificially introduce additional exploration. This was done in [36] where
$\epsilon$-greedy NAC was proposed under which, at each time, actions are
sampled from $\epsilon$-greedy policy
$\hat{\pi}_{t}=(1-\epsilon_{t})\pi_{t}+\frac{\epsilon_{t}}{|\mathcal{A}|}$.
Sampling from this policy ensures that all actions will be visited with
probability at least $\frac{\epsilon_{t}}{|\mathcal{A}|}$, which ensures
exploration of all state-action pairs. However, this sampling policy will
result in a slower rate of convergence as stated in [36].

###  C.4 Sample Complexity Calculation in Related Literature

In this section, we compute the sample complexity of each related work listed
in Table 1, based on the convergence bounds provided in the corresponding
paper. We will use the same notation as was used in the corresponding paper.

####  C.4.1 [71]

##### AC, Theorem 4.7:

In order the obtain an $\epsilon$-optimal stationary point, we need
$T=\mathcal{O}(\epsilon^{-2/3})$, which implies
$m=\mathcal{O}(\epsilon^{-16/3})$. Since $T_{TD}=\Omega(m)$, the total sample
complexity $T\times T_{TD}$ is at least $\mathcal{O}(\epsilon^{-6})$.

##### NAC, Corollary 4.14:

In order to obtain an $\epsilon$-optimal policy, we need
$T=\mathcal{O}(\epsilon^{-2})$, which implies $m=\Omega(\epsilon^{-14})$.
Since $T_{TD}=\Omega(m)$, the total sample complexity $T\times T_{TD}$ is at
least $\mathcal{O}(\epsilon^{-14})$.

####  C.4.2 [38]

AC, Theorem 1: The result in this paper assumes a convergence rate of
$\mathcal{O}(1/k^{b})$ for the critic. It was shown in [62] that a rate of
$\mathcal{O}(1/\sqrt{k})$ is achievable, and so we use this to evaluate sample
complexity. In order to obtain $\epsilon$-close stationary point, we need
$\mathcal{O}(1+2+\dots+\epsilon^{-2})=\mathcal{O}(\epsilon^{-4})$ number of
samples, which implies $\mathcal{O}(\epsilon^{-4})$ sample complexity.

####  C.4.3 [1]

NAC, Corollary 6.2: In order to obtain an $\epsilon$-optimal policy, we need
to have $\frac{1}{1-\gamma}\frac{1}{\sqrt{T}}\leq\mathcal{O}(\epsilon)$ and
$\frac{1}{(1-\gamma)^{2}}\frac{1}{N^{1/4}}\leq\mathcal{O}(\epsilon)$. This is
equivalent to $T\geq\mathcal{O}((1-\gamma)^{-2}\epsilon^{-2})$ and
$N\geq\mathcal{O}((1-\gamma)^{-8}\epsilon^{-4})$. Hence, the total sample
complexity is
$\frac{2TN}{1-\gamma}=\mathcal{O}((1-\gamma)^{-11}\epsilon^{-6})$. Note that
although [1, Corollary 6.2] is stated for the function approximation setting,
the result would be the same even in the tabular setting.

####  C.4.4 [36]

NAC, Corollary 1.1: As stated in Corollary 1.1 of this paper, to obtain an
$\epsilon$ optimal policy, we have $T\geq\mathcal{O}(\epsilon^{-4})$ sample
complexity.

####  C.4.5 [58]

AC, Theorem 4.6: As stated in Theorem 4.6 of this paper, in order to an
$\epsilon$-optimal stationary point, we need $T\geq\epsilon^{-2}$ number of
outer loops, and in each outer loop we need $\mathcal{O}(T)$ inner loops.
Hence, the total sample complexity is $T\times T=\mathcal{O}(\epsilon^{-4})$.

##  Appendix D Experimental Results

###  D.1 Details of the Experimental Results

Figure 1 shows the convergence behavior of off-policy NAC 2. The underlying
process is a MDP with 5 states and 3 actions $\\{a_{1},a_{2},a_{3}\\}$ and
$\gamma=0.9$. The state transition probabilities over the states are

$\displaystyle P_{a_{1}}=\begin{bmatrix}0&1&0&0&0\\\ 0&0&1&0&0\\\ 0&0&0&1&0\\\
0&0&0&0&1\\\
1&0&0&0&0\end{bmatrix},~{}~{}~{}~{}~{}~{}P_{a_{2}}=\begin{bmatrix}1&0&0&0&0\\\
0&1&0&0&0\\\ 0&0&1&0&0\\\ 0&0&0&1&0\\\
0&0&0&0&1\end{bmatrix},~{}~{}~{}~{}~{}~{}P_{a_{3}}=\begin{bmatrix}0&0&0&0&1\\\
1&0&0&0&0\\\ 0&1&0&0&0\\\ 0&0&1&0&0\\\ 0&0&0&1&0\end{bmatrix},$

and the reward functions are $\mathcal{R}(s,a_{1})=1$,
$\mathcal{R}(s,a_{2})=0.5$, and $\mathcal{R}(s,a_{3})=0$ for all
$s\in\mathcal{S}$. In this setting, clearly the optimal policy is to take
action $a_{1}$ in all states. In addition, the behavior policy has uniform
distribution, i.e. $\pi_{b}(a|s)=1/3~{}\forall a,s$. The parametters of the
algorithm are chosen as follows:
$n=6,T=100,K=1000,\alpha=0.05,\beta=0.1,\bar{\rho}=3,\bar{c}=1,\pi_{0}(a|s)=\frac{1}{3}\forall
a,s$. In addition, for $Q_{0}$ input of the $Q$-trace, we use the previously
learned $Q$ table as the input to enhance the convergence. An implementation
of the code is available at https://github.com/gt-coar/off_policy-
NAC/blob/main/off-policy_NAC.py. It is clear that algorithm converges in
Figure 1.

###  D.2 Using Repeated Samples in the Critic

Using the same setup as above, we executed Algorithm 2 with repeated samples
used for each iteration of the $Q$-trace. Figure 2 shows the result. It is
clear that we do not have convergence in this case.

Figure 2: behavior of off-policy NAC when the critic updates are performed
using a fixed number of samples. The straight lines are
$V^{\pi^{*}}(\mu)-V^{\pi_{t}}(\mu)$ values for 5 different sample paths, and
the dashed lines are the corresponding critic errors
$\|Q^{t+1}-Q^{\pi_{t}}\|_{\infty}$ of each sample path. It is clear that the
algorithm does not converge.

###  D.3 The Effect of the Truncation Levels

In order to evaluate the effect of the truncation of the importance sampling
in the behavior of the off-policy NAC, we run Algorithm 2 for different levels
of $\bar{\rho}$ and $\bar{c}$ for an MDP with the same setting as in section
D.1. The result is shown in Figure 3. In this figure, for each choice of the
$\bar{\rho}$ and $\bar{c}$ we run the Algorithm 2 for 6 number of times. The
dashed lines represent the average of these 6 sample paths, and the area
around the dashed lines represent the standard deviation of these 6
trajectories. It is clear that the choice of $\bar{\rho}=3,\bar{c}=1$ results
in the best convergence with the lowest standard deviation. Reducing
$\bar{\rho}=3$ to $\bar{\rho}=2.5$ is worsening the convergence bahaviour, and
further increasing $\bar{c}=1$ to $\bar{c}=1.5$ increases the standard
deviation.

Figure 3: The convergence behavior of off-policy NAC with different levels of
truncation. For each choice of the truncation level, we run Algorithm 2 6
times, and we plot the mean with the dashed line, and the standard deviation
with the colored area.