# AN APPROXIMATE POLICY ITERATION VIEWPOINT OF
ACTOR-CRITIC ALGORITHMS

Zaiwei Chen1 and Siva Theja Maguluri2
1Caltech CMS<EMAIL_ADDRESS>
2Georgia Tech ISyE<EMAIL_ADDRESS>
###### Abstract

In this work, we consider policy-based methods for solving the reinforcement
learning problem, and establish the sample complexity guarantees. A policy-
based algorithm typically consists of an actor and a critic. We consider using
various policy update rules for the actor, including the celebrated natural
policy gradient. In contrast to the gradient ascent approach taken in the
literature, we view natural policy gradient as an approximate way of
implementing policy iteration, and show that natural policy gradient (without
any regularization) enjoys geometric convergence when using increasing
stepsizes. As for the critic, we consider using TD-learning with linear
function approximation and off-policy sampling. Since it is well-known that in
this setting TD-learning can be unstable, we propose a stable generic
algorithm (including two specific algorithms: the $\lambda$-averaged $Q$-trace
and the two-sided $Q$-trace) that uses multi-step return and generalized
importance sampling factors, and provide the finite-sample analysis. Combining
the geometric convergence of the actor with the finite-sample analysis of the
critic, we establish for the first time an overall
$\tilde{\mathcal{O}}(\epsilon^{-2})$ sample complexity for finding an optimal
policy (up to a function approximation error) using policy-based methods under
off-policy sampling and linear function approximation.

## 1 Introduction

In recent years, reinforcement learning (RL) has demonstrated impressive
performance in solving practical problems, such as the game of Go [44], power
systems [62], city navigation [35], and nuclear plasma control [17]. An RL
problem in its nature is a sequential decision-making problem, and is usually
modeled as a Markov decision process (MDP). To solve an MDP, the two most
well-known methods are value iteration (VI) and policy iteration (PI).
However, compared to MDPs, a main feature of RL is that the parameters of the
environmental model, such as the transition probabilities and the reward
function, are unknown to the agent. Therefore, due to the lack of knowledge
about the model, either VI or PI is not directly implementable. To overcome
this challenge, data-driven versions of VI and PI were developed. The
resulting algorithms are called $Q$-learning, which is the RL-counterpart of
VI, and approximate policy iteration (API), which is the RL-counterpart of PI.
The analysis of either $Q$-learning or API mostly relies on the properties of
the Bellman operator, such as the contraction property and the monotonicity
property [4].

On the other hand, an MDP at its heart is a continuous optimization problem in
the space of policies, and a natural approach to solve a continuous
optimization problem is to use gradient ascent/descent and its variants. Based
on this viewpoint, the policy gradient algorithm was developed, the
counterpart of which in RL is the popular actor-critic. Unlike the analysis of
VI or PI, the analysis of policy gradient is largely based on the policy
gradient theorem, and machineries from continuous optimization, such as the
mirror descent analysis [28]. In contrast to the geometric convergence of VI
or PI, policy gradient in general does not achieve geometric convergence. A
variant of policy gradient, known as natural policy gradient, was recently
shown to enjoy geometric convergence after being regularized. See Section 1.1
for a more detailed discussion about related work in this field.

In this work, we provide a different viewpoint on natural policy gradient.
Specifically, we show that with properly chosen stepsizes, natural policy
gradient can be viewed as an approximate version of PI, which enables us to
establish the geometric convergence without requiring any regularization. To
use the result in an actor-critic framework, we design a single time-scale TD-
learning variant for policy evaluation that successfully overcomes the deadly
triad. After combining the analysis of the actor and the critic, we establish
an overall $\tilde{\mathcal{O}}(\epsilon^{-2})$ sample complexity for finding
an optimal policy up to a function approximation error. The more detailed
contributions of this work are summarized in the following.

Geometric Convergence of Natural Policy Gradient. We show that when using
either large enough constant stepsize or geometrically increasing time-varying
stepsizes, natural policy gradient is approximately PI. Therefore, by using
the contraction property and the monotonicity property of the Bellman
operator, we establish geometric convergence of natural policy gradient.
Importantly, unlike in existing literature, our result does not require using
any kind of regularization techniques in the algorithm design.

Stable Single Time-Scale Off-Policy TD-Learning under Linear Function
Approximation. To use our result for natural policy gradient in an actor-
critic framework, we also need to specify the algorithm used for policy
evaluation (i.e., the critic) and establish the finite-sample guarantees. To
overcome the curse of dimensionality and to avoid the risk and/or expense in
online sampling, we will incorporate our critic algorithm with linear function
approximation and off-policy learning. When both function approximation and
off-policy learning are employed in TD-learning (which is essentially a
bootstrapped stochastic iterative algorithm), the resulting algorithm can be
unstable. As a result, function approximation, off-policy learning, and
bootstrapping together are characterized as the “deadly triad” [47]. To
overcome the deadly triad in the critic, we design a single time-scale TD-
learning algorithm that uses multi-step return and generalized importance
sampling factors. The proposed algorithm is provably stable and does not
suffer from the high variance from using importance sampling. In addition, the
mean-square error achieves the optimal $\mathcal{O}(1/k)$ convergence rate.

Establishment of the $\tilde{\mathcal{O}}(\epsilon^{-2})$ Sample Complexity
for General Policy-Based Methods. After combining the geometric convergence of
the actor and the $\mathcal{O}(1/k)$ convergence of the critic, we obtain an
overall $\tilde{\mathcal{O}}(1/\epsilon^{2})$ sample complexity for a general
policy-based algorithm (which includes natural actor-critic as a special case)
under off-policy sampling and linear function approximation. The sample
complexity matches with that of typical value-based algorithms such as
$Q$-learning [31]. Even in the tabular setting, which is a special case of
linear function approximation, this is the first time that an
$\tilde{\mathcal{O}}(\epsilon^{-2})$ sample complexity is achieved for off-
policy natural actor-critic, thereby advancing previous art in the literature.

### 1.1 Related Literature

Analogous to VI and PI for solving MDPs, RL algorithms can be divided into two
categories: value-based method and policy-based method. Popular value-space
methods include $Q$-learning [56] and variants of TD-learning [46], both of
which achieve the $\tilde{\mathcal{O}}(\epsilon^{-2})$ sample complexity [31,
13, 42]. Popular policy-based methods include actor-critic [25], its variant
natural actor-critic [21], and API [3]. A policy-based algorithm usually
consists of an actor for policy improvement and a critic for policy
evaluation.

TD-Learning. The policy evaluation sub-problem is usually solved with TD-
learning and its variants [46]. The asymptotic convergence of TD-learning was
established in [52, 16, 5]. Finite-sample analysis of various TD-learning
algorithms using on-policy sampling was performed in [13], and using off-
policy sampling in [23, 14]. In the function approximation setting, TD-
learning with linear function approximation was studied in [53, 29, 45, 6]
when using on-policy sampling. In the off-policy linear function approximation
setting, due to the presence of the deadly triad, TD-learning algorithms can
diverge [47]. Variants of TD-learning algorithms such as TDC [48], GTD [51],
emphathic TD [49], and $n$-step TD (with a large enough $n$) [12] were used to
resolve the divergence issue, and the finite-sample bounds were studied in
[34, 55, 12]. Note that TDC, GTD, and emphatic TD are two time-scale
algorithms, while vanilla $n$-step TD is single time-scale, it suffers from a
high variance due to the cumulative product of the importance sampling
factors. See Appendix B of this work for a detailed discussion.

(Natural) Policy Gradient. The policy gradient method was proposed and was
shown to converge in [50, 2, 1]. natural policy gradient, proposed in [21], is
a variant of policy gradient method where the inverse of the fisher
information matrix was used as a pre-conditioner. The $O(1/k)$ convergence of
natural policy gradient was shown in [1]. Later, by introducing
regularization, geometric convergence of natural policy gradient was shown in
[28, 11, 10]. A recent paper [59] 111[59] is subsequent to this work. shows
geometric convergence of natural policy gradient without regularization.
Beyond geometric convergence, [24] shows that asymptotically natural policy
gradient converges at a super-linear rate. However, the natural policy
gradient algorithm studied in [24] uses adaptive stepsizes that depend on
model parameters, and hence cannot be used in an actor-critic framework where
the model is unknown to the agent. In this paper, we take a different
perspective and view natural policy gradient as an approximate version of PI,
which enables us to show the geometric convergence of natural policy gradient
using only the properties (i.e., contraction and monotonicity) of the Bellman
operator. Importantly, we do not require regularization, and our result can be
directly used to establish an overall $\mathcal{O}(\epsilon^{-2})$ sample
complexity of natural actor-critic.

Approximate Policy Iteration. PI has been a popular method to solve MDPs [40].
In the RL setting, PI has to be implemented in an approximate manner due to
the lack of knowledge about the environmental model. The convergence rate and
asymptotic error bound of API have been studied in [43, 36]. A convergent form
of API with Lipschitz continuous policy update was proposed in [38]. Other
variants of API such as least square PI and rollout sampling API schemes were
proposed and studied in [27] and [18], respectively. See [3, 39] for detailed
surveys about API methods.

(Natural) Actor-Critic. The asymptotic convergence of on-policy actor-critic
was established in [57, 8, 9] when using a tabular representation, and in [25,
7] when using function approximation. In recent years, there has been an
increasing interest in understanding the finite-sample behavior of (natural)
actor-critic algorithms. Here is a non-exhaustive list: [28, 23, 61, 41, 26,
32, 54, 33, 58, 10]. The state-of-the-art sample complexity of on-policy
natural actor-critic is $\tilde{\mathcal{O}}(\epsilon^{-2})$ [28]. However,
only tabular RL was considered in [28]. In the off-policy setting, finite-
sample analysis of natural actor-critic was studied in [22] when using a
tabular representation, and in [12] when using linear function approximation,
and the sample complexity in both cases is
$\tilde{\mathcal{O}}(\epsilon^{-3})$. In this work, we advance previous art by
establishing an $\tilde{\mathcal{O}}(\epsilon^{-2})$ sample complexity of
policy-based algorithms in the off-policy function approximation setting.

### 1.2 Background on Reinforcement Learning

We consider modeling the RL problem as an infinite horizon MDP, which is
defined in the following.

######  Definition 1.1.

An infinite horizon MDP is composed by a $5$-tuple
$(\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma)$, where
$\mathcal{S}$ is the finite state-space, $\mathcal{A}$ is the finite action-
space,
$\mathcal{P}=\\{P_{a}\in\mathbb{R}^{|\mathcal{S}|\times|\mathcal{S}}\mid
a\in\mathcal{A}\\}$ is a set of transition probability matrices, and
$P_{a}(s,s^{\prime})$ is the probability of going from state $s$ to state
$s^{\prime}$ under action $a$,
$\mathcal{R}:\mathcal{S}\times\mathcal{A}\mapsto\mathbb{R}_{+}$ is the reward
function, i.e., $\mathcal{R}(s,a)$ is the reward of taking action $a$ at state
$s$, $\gamma\in(0,1)$ is the discount factor, which captures how much weight
we assign to future reward.

We assume without loss of generality that $\max_{s,a}\mathcal{R}(s,a)\leq 1$.
The goal is to find an optimal policy $\pi^{*}$ of selecting actions so that
the long term reward is maximized. Formally, define the state-action value
function associated with a policy $\pi$ at state-action pair $(s,a)$ as
$Q^{\pi}(s,a)=\mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty}\gamma^{k}\mathcal{R}(S_{k},A_{k})\;\middle|\;S_{0}=s,A_{0}=a\right]$,
where we use the notation $\mathbb{E}_{\pi}[\,\cdot\,]$ to indicate that the
actions are chosen according to the policy $\pi$. Then the goal is to find an
optimal policy $\pi^{*}$ such that $Q^{*}:=Q^{\pi^{*}}$ is maximized uniformly
for all $(s,a)$. A popular approach to solve the RL problem is to use policy-
based methods, where the agent iteratively performs a critic step to estimate
the value function of the current policy iterate, and an actor step to update
the policy.

## 2 The Actor for Policy Improvement

In this section we study various policy-based algorithms (including natural
policy gradient) and establish their convergence rates.

### 2.1 Policy Update Rules

We begin by presenting a generic policy-based algorithm in the following.

Algorithm 1 A Generic Policy-Based Algorithm

1: Input: Integer $T$ and initial policy $\pi_{0}(\cdot\mid
s)\sim\text{Unif}(\mathcal{A})$ for all $s\in\mathcal{S}$

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

3: Critic estimates $Q^{\pi_{t}}$, and outputs $Q_{t}$$\triangleright$ Policy
Evaluation

4: Actor updates the policy according to $\pi_{t+1}=G(Q_{t},\pi_{t})$
$\triangleright$ Policy Improvement

5: end for

6: Output: $\pi_{T}$

In Algorithm 1, the function $G(\cdot,\cdot)$ represents the policy update
rule, which takes the current policy iterate $\pi_{t}$ and the $Q$-function
estimate $Q_{t}$ as inputs, and outputs the next policy $\pi_{t+1}$. Many
existing policy update rules fit into this framework, as elaborated below.

##### Natural Policy Gradient.

A popular approach for updating the policy is to use the natural policy
gradient, which can be viewed as a variant of policy gradient where the fisher
information matrix is introduced as a pre-conditioner. Alternatively, natural
policy gradient is a mirror descent update with the Bregman divergence being
replaced by the $\mathcal{K}\mathcal{L}$ divergence. See [1] for more details.
Mathematically, natural policy gradient updates the policy in an
multiplicative manner according to

$\displaystyle\pi_{t+1}(a|s)=\frac{\pi_{t}(a|s)\exp(\beta_{t}Q_{t}(s,a))}{\sum_{a^{\prime}\in\mathcal{A}}\pi_{t}(a^{\prime}|s)\exp(\beta_{t}Q_{t}(s,a))},\quad\forall\;(s,a),$
(1)

where $\\{\beta_{t}\\}$ is a positive sequence of real numbers, and $Q_{t}$ is
the estimate of the value function $Q^{\pi_{t}}$. Note that the next policy
$\pi_{t+1}$ is uniquely determined by the previous policy $\pi_{t}$ and its
$Q$-function estimate $Q_{t}$. Therefore, natural policy gradient is a special
case of Algorithm 1.

##### Approximate Policy Iteration.

A classical approach for policy improvement is to use API. In practice, the
following two policy update rules are frequently used:

$\displaystyle\text{(1)}\quad\quad\pi_{t+1}(a|s)=\;$
$\displaystyle\frac{\exp(\beta_{t}Q_{t}(s,a))}{\sum_{a^{\prime}\in\mathcal{A}}\exp(\beta_{t}Q_{t}(s,a^{\prime}))},\quad\forall\;(s,a).$
(Boltzmann Softmax Update)
$\displaystyle\text{(2)}\quad\quad\pi_{t+1}(a|s)=\;$
$\displaystyle\begin{dcases}\frac{\beta_{t}}{|\mathcal{A}|},&a\neq\arg\max_{a^{\prime}\in\mathcal{A}}Q_{t}(s,a^{\prime}),\\\
\frac{\beta_{t}}{|\mathcal{A}|}+1-\beta_{t},&a=\arg\max_{a^{\prime}\in\mathcal{A}}Q_{t}(s,a^{\prime}),\end{dcases}$
($\epsilon$-Greedy Update)

where $\\{\beta_{t}\\}$ in either case is a positive sequence of real
numbers222While the update rule in (2) does not involve $\epsilon$, we use the
terminology “$\epsilon$-greedy” for consistency with existing literature.. In
(2), when the maximizer
$\arg\max_{a^{\prime}\in\mathcal{A}}Q_{t}(s,a^{\prime})$ is not unique, we
break tie with an arbitrary but fixed tie-breaking rule. For simplicity of
notation, we will denote
$a_{t,s}=\arg\max_{a^{\prime}\in\mathcal{A}}Q_{t}(s,a^{\prime})$. Unlike
natural policy gradient, in both of the API update rules, the next policy
$\pi_{t+1}$ depends only on $Q_{t}$ and not on $\pi_{t}$. This is important
when we use function approximation, in which case as long as the $Q$-function
is parametrized, we do not need to parametrize the policy.

### 2.2 Finite-Time Analysis

In this section, we present the convergence rate analysis of Algorithm 1 for
using either natural policy gradient update or API update. We first specify
how to choose $\\{\beta_{t}\\}$, which we view as stepsizes. In particular, we
consider using either constant stepsize, or geometrically increasing
stepsizes. Let $\beta>0$ be a tunable parameter.

######  Condition 2.1 (Constant Stepsize).

The sequence $\\{\beta_{t}\\}$ satisfies the following requirements.

  1. (1)

Natural Policy Gradient: The parameter $\beta_{t}$ satisfies
$\beta_{t}\geq\gamma\beta\log(1/\min_{s\in\mathcal{S}}\pi_{t}(a_{t,s}|s))$ for
all $t$.

  2. (2)

Boltzmann Softmax Update: The parameter $\beta_{t}$ satisfies
$\beta_{t}\geq\gamma\beta\log(|\mathcal{A}|)$ for all $t\geq 0$.

  3. (3)

$\epsilon$-Greedy Update: The parameter $\beta_{t}$ is state-dependent, and
satisfies $\beta_{t,s}\geq 2\gamma\beta\max_{a\in\mathcal{A}}|Q_{t}(s,a)|$ for
all $s$ and $t$.

######  Condition 2.2 (Geometrically Increasing Stepsizes).

The sequence $\\{\beta_{t}\\}$ satisfies the following requirements.

  1. (1)

Natural Policy Gradient: The parameter $\beta_{t}$ satisfies
$\beta_{t}\geq\log(\frac{1}{\min_{s\in\mathcal{S}}\pi_{t}(a_{t,s}|s)})/\gamma^{2t-1}$
for all $t$.

  2. (2)

Boltzmann Softmax Update: The parameter $\beta_{t}$ satisfies
$\beta_{t}\geq\log(|\mathcal{A}|)/\gamma^{2t-1}$ for all $t$.

  3. (3)

$\epsilon$-Greedy Update: The parameter $\beta_{t}$ is state-dependent, and
satisfies $\beta_{t,s}\geq 2\max_{a\in\mathcal{A}}|Q_{t}(s,a)|/\gamma^{2t-1}$
for all $s$ and $t$.

Next, we state the result for the finite-time analysis of Algorithm 1.

######  Theorem 2.1.

Consider $\\{\pi_{t}\\}$ generated by Algorithm 1 for using either natural
policy gradient update or API update.

  1. (1)

Suppose that $\\{\beta_{t}\\}$ is chosen according to Condition 2.1. Then we
have

$\displaystyle\mathbb{E}[\|Q^{*}-Q^{\pi_{T}}\|_{\infty}]\leq\;$
$\displaystyle\underbrace{\gamma^{T}\|Q^{*}-Q^{\pi_{0}}\|_{\infty}}_{N_{1}}+\underbrace{\frac{2\gamma}{1-\gamma}\sum_{t=0}^{T-1}\gamma^{T-1-t}\mathbb{E}[\|Q^{\pi_{t}}-Q_{t}\|_{\infty}]}_{N_{2}}+\underbrace{\frac{2\gamma}{\beta(1-\gamma)^{2}}}_{N_{3}}.$
(2)

  2. (2)

Suppose that $\\{\beta_{t}\\}$ is chosen according to Condition 2.2. Then we
have

$\displaystyle\mathbb{E}[\|Q^{*}-Q^{\pi_{T}}\|_{\infty}]\leq\;$ $\displaystyle
N_{1}+N_{2}+\underbrace{\frac{2\gamma^{T}}{(1-\gamma)^{2}}}_{N_{3}^{\prime}}.$
(3)

On the RHS of Eq. (2), the term $N_{1}$ represents the convergence bias of the
actor, and goes to zero geometrically fast as $T$ goes to infinity. The term
$N_{2}$ represents the error in the critic, and vanishes in the MDP tabular
setting where we can (in principle) exactly compute $Q^{\pi_{t}}$. In the RL
with function approximation setting, the term $N_{2}$ involves the stochastic
error due to sampling and the error due to function approximation, both of
which will be exactly characterized in Section 4, where we present the sample
complexity of actor-critic. The term $N_{3}$ captures the error introduced to
the algorithm by the policy update rule $G(\cdot,\cdot)$. To elaborate, recall
that for a discounted MDP there always exists a deterministic optimal policy.
Suppose that the optimal policy is unique, and we use $\epsilon$-greedy update
in Algorithm 1 line 4 with a constant stepsize; see Condition 2.1. Then we can
never truly find the optimal policy $\pi^{*}$ because of the deterministic
nature of $\pi^{*}$ and the stochastic nature of our policy iterates
$\\{\pi_{t}\\}$. As a result, the difference between $Q^{*}$ and $Q^{\pi_{t}}$
will always be above some threshold, which depends on the choice of $\beta$ in
Condition 2.1, and is captured by $N_{3}$. Observe that $N_{3}$ can be made
arbitrarily small by using large enough $\beta$. Alternatively, we can use
geometrically increasing stepsizes as suggested in Condition 2.2, in which
case the term $N_{3}^{\prime}$ in Eq. (3) goes to zero at a geometric rate.

### 2.3 Geometric Convergence of Natural Policy Gradient

Theorem 2.1 implies the geometric convergence of natural policy gradient, due
to the popularity of which, we present the result as a corollary in the
following.

Algorithm 2 Natural Policy Gradient under Softmax Policy and Tabular
Representation

1: Input: Integer $T$ and initial policy
$\pi_{0}(\cdot|s)\sim\text{Unif}(\mathcal{A})$ for all $s\in\mathcal{S}$

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

3:
$\pi_{t+1}(a|s)=\frac{\pi_{t}(a|s)\exp(\beta_{t}Q^{\pi_{t}}(s,a))}{\sum_{a^{\prime}\in\mathcal{A}}\pi_{t}(a^{\prime}|s)\exp(\beta_{t}Q^{\pi_{t}}(s,a^{\prime}))}$
for all $(s,a)$.

4: end for

5: Output: $\pi_{T}$

######  Corollary 2.1.1.

Consider $\\{\pi_{T}\\}$ generated by Algorithm 2. Suppose that
$\beta_{t}\geq\log(1/\min_{s\in\mathcal{S}}\pi_{t}(a_{t,s}\mid
s))/\gamma^{2t-1}$ for all $t=0,\cdots,T-1$. Then we have
$\mathbb{E}[\|Q^{*}-Q^{\pi_{T}}\|_{\infty}]\leq\frac{3\gamma^{T}}{(1-\gamma)^{2}}$.

The proof of Corollary 2.1.1 follows directly from Theorem 2.1 Eq. (3) and the
following two observations: (1) $N_{2}$ vanishes as we directly use
$Q^{\pi_{t}}$ for updating the policy in Algorithm 2, and (2)
$N_{1}\leq\frac{\gamma^{T}}{1-\gamma}$ since
$\|Q^{*}-Q^{\pi_{0}}\|_{\infty}\leq\frac{1}{1-\gamma}$.

### 2.4 Proof Sketch of Theorem 2.1

In this section, we present the high level ideas in proving Theorem 2.1. The
detailed proof is deferred to Section 5.1. We first introduce some notation.
Let
$\mathcal{H}:\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}\mapsto\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$
be the Bellman optimality operator defined as

$\displaystyle[\mathcal{H}(Q)](s,a)=\mathcal{R}(s,a)+\gamma\mathbb{E}\left[\max_{a^{\prime}\in\mathcal{A}}Q(S_{k+1},a^{\prime})\;\middle|\;S_{k}=s,A_{k}=a\right],\quad\forall\;Q\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|},\;\forall\;(s,a),$

and let
$\mathcal{H}_{\pi}:\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}\mapsto\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$
be the Bellman operator associated with some policy $\pi$ defined as

$\displaystyle[\mathcal{H}_{\pi}(Q)](s,a)=\mathcal{R}(s,a)+\gamma\mathbb{E}_{\pi}[Q(S_{k+1},A_{k+1})\mid
S_{k}=s,A_{k}=a],\quad\forall\;Q\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|},\;\forall\;(s,a).$

The proof is divided into two steps. In the first step we bound the difference
between $Q^{\pi_{T}}$ and $Q^{*}$ in terms of $\|Q^{\pi_{t}}-Q_{t}\|_{\infty}$
and $\|\mathcal{H}_{\pi_{t+1}}(Q_{t})-\mathcal{H}(Q_{t})\|_{\infty}$,
$t=0,\cdots,T-1$. The term $\|Q^{\pi_{t}}-Q_{t}\|_{\infty}$ can be viewed as
the critic error and the term
$\|\mathcal{H}_{\pi_{t+1}}(Q_{t})-\mathcal{H}(Q_{t})\|_{\infty}$ can be viewed
as the actor error (for not using PI). The proof technique in this step was
inspired by [4, Section 6.2]. However, only asymptotic error bound of API was
established in [4], while we establish finite-sample bounds for various policy
update rules. In the second step, we further bound
$\|\mathcal{H}_{\pi_{t+1}}(Q_{t})-\mathcal{H}(Q_{t})\|_{\infty}$ using our
conditions (cf. Conditions 2.1 and 2.2) on choosing the stepsizes
$\\{\beta_{t}\\}$.

## 3 The Critic for Policy Evaluation

So far we have been focusing on the analysis of the actor. In this section, we
switch our focus to the critic, i.e., how to obtain an estimate of
$Q^{\pi_{t}}$ in Algorithm 1 line 3.

Consider estimating the $Q$-function $Q^{\pi}$ of a given target policy $\pi$
using TD-learning. Depending on whether the policy $\pi_{b}$ used to collect
samples (called the behavior policy) is equal to the target policy $\pi$ or
not, there are on-policy TD-learning (i.e., $\pi_{b}=\pi$) and off-policy TD-
learning (i.e., $\pi_{b}\neq\pi$). Compared to on-policy sampling, off-policy
sampling is sometimes more preferred in practice as it does not require
collecting new samples, which often come at a risk and/or cost. In addition,
off-policy sampling enables data reuse so that the agent can learn in an off-
line manner using historical data.

It is known that TD-learning becomes computationally intractable when the size
of the state-action space is large, which is referred to as the curse of
dimensionality. This motivates the use of function approximation. In linear
function approximation, we choose a set of basis vectors
$\phi_{i}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$, $1\leq i\leq d$, and try
to approximate the target value function $Q^{\pi}$ using linear combinations
of the basis vectors. Specifically, let
$\Phi\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|\times d}$ be a matrix defined
by $\Phi=[\phi_{1},\cdots,\phi_{d}]$, and let
$\phi(s,a)=[\phi_{1}(s,a),\phi_{2}(s,a),\cdots,\phi_{d}(s,a)]^{\top}\in\mathbb{R}^{d}$
be the $(s,a)$-th row of the matrix $\Phi$, which can be viewed as the feature
vector associated with the state-action pair $(s,a)$. Then, the goal is to
find from the linear sub-space $\mathcal{Q}=\\{\tilde{Q}_{w}=\Phi w\mid
w\in\mathbb{R}^{d}\\}$ the “best” approximation of the $Q$-function $Q^{\pi}$,
where $w\in\mathbb{R}^{d}$ is the weight vector.

When TD-learning is used along with off-policy sampling and linear function
approximation, the deadly triad is formed and the algorithm can be unstable.
We next propose a generic framework of TD-learning algorithms (including two
specific algorithms: the $\lambda$-averaged $Q$-trace and the two-sided
$Q$-trace), which provably converge in the presence of the deadly triad, and
do not suffer from the high variance issue in off-policy learning. Since we
work with MDPs with finite state-action spaces, we assume without loss of
generality that the matrix $\Phi$ has linearly independent columns, and is
normalized so that $\|\Phi\|_{\infty}=\max_{s,a}\|\phi(s,a)\|_{1}\leq 1$.

### 3.1 Algorithm Design

We present in Algorithm 3 a generic TD-learning algorithm using off-policy
sampling and linear function approximation. The two most important steps in
Algorithm 3 are line 3, where the temporal differences are computed, and line
4, where we update the weight vector $w_{t}$ using discounted multi-step
return. Both steps involve the use of the generalized importance sampling
factors $c(\cdot,\cdot)$ and $\rho(\cdot,\cdot)$, the choices of which are of
vital importance to the behavior of the algorithm. We next present two
specific choices, resulting in two novel algorithms called $\lambda$-averaged
$Q$-trace and two-sided $Q$-trace.

Algorithm 3 A Generic Multi-Step Off-Policy TD-Learning with Linear Function
Approximation

1: Input: Integer $K$, bootstrapping parameter $n$, stepsize sequence
$\\{\alpha_{k}\\}$, initialization $w_{0}$, target policy $\pi$, behavior
policy $\pi_{b}$, generalized importance sampling factors
$c,\rho:\mathcal{S}\times\mathcal{A}\mapsto\mathbb{R}_{+}$, and a single
trajectory of samples $\\{(S_{k},A_{k})\\}_{0\leq k\leq K+n-1}$ generated by
the behavior policy $\pi_{b}$.

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

3:
$\Delta_{i}(w_{k})=\mathcal{R}(S_{i},A_{i})+\gamma\rho(S_{i+1},A_{i+1})\phi(S_{i+1},A_{i+1})^{\top}w_{k}-\phi(S_{i},A_{i})^{\top}w_{k}$,
for all $i\in\\{k,k+1,\cdots,k+n-1\\}$

4:
$w_{k+1}=w_{k}+\alpha_{k}\phi(S_{k},A_{k})\sum_{i=k}^{k+n-1}\gamma^{i-k}\prod_{j=k+1}^{i}c(S_{j},A_{j})\Delta_{i}(w_{k})$

5: end for

6: Output: $w_{K}$

The $\lambda$-Averaged $Q$-Trace Algorithm. Let
$\lambda\in\mathbb{R}^{|\mathcal{S}|}$ be a vector-valued tunable parameter
satisfying $\lambda\in[\bm{0},\bm{1}]$. Then the generalized importance
sampling factors are chosen as
$c(s,a)=\rho(s,a)=\lambda(s)\frac{\pi(a|s)}{\pi_{b}(a|s)}+1-\lambda(s)$ for
all $(s,a)$. Observe that when $\lambda=\bm{1}$, we have
$c(s,a)=\rho(s,a)=\frac{\pi(a|s)}{\pi_{b}(a|s)}$, and Algorithm 3 reduces to
the convergent multi-step off-policy TD-learning algorithm presented in [12],
which however suffers from an exponential large variance due to the cumulative
product of the importance sampling factors. See Appendix B for more details.
On the other hand, when $\lambda=\bm{0}$, we have $c(s,a)=\rho(s,a)=1$, and
hence the product of the generalized importance sampling factors is
deterministically equal to one, resulting in no variance at all. However in
this case, we are essentially performing policy evaluation of the behavior
policy $\pi_{b}$ instead of the target policy $\pi$, hence there will be an
asymptotic bias in the limit of Algorithm 3. More generally, when
$\lambda\in(\bm{0},\bm{1})$, there is a trade-off between the variance in the
stochastic iterates $\\{w_{k}\\}$ and the bias in the limit point. Such trade-
off will be studied quantitatively in Section 3.3.

The Two-Sided $Q$-Trace Algorithm. To introduce the algorithm, we first define
the two-sided truncation function. Given upper and lower truncation levels
$a,b\in\mathbb{R}$ satisfying $0<a<b$, we define
$g_{a,b}:\mathbb{R}\mapsto\mathbb{R}$ as $g_{a,b}(x)=a$ when $x<a$,
$g_{a,b}(x)=x$ when $a\leq x\leq b$, and $g_{a,b}(x)=b$ when $x>b$. Let
$\ell,u\in\mathbb{R}^{|\mathcal{S}|}$ be two vector-valued tunable parameters
satisfying $\bm{0}\leq\ell\leq\bm{1}\leq u$. Then, for the two-sided $Q$-trace
algorithm, the generalized importance sampling factors are chosen as
$c(s,a)=\rho(s,a)=g_{\ell(s),u(s)}\left(\frac{\pi(a|s)}{\pi_{b}(a|s)}\right)$
for all $(s,a)$. The idea of truncating the importance sampling factors from
above was already employed in existing algorithms such as Retrace$(\lambda)$
[37], $V$-trace [19], and $Q$-trace [23], and is used to control the high
variance in off-policy learning. However, none of them were shown to converge
in the function approximation setting. The main reason is that truncating the
importance sampling factors from above undermines the impact of using multi-
step return, which is crucial for us to overcome the deadly triad. Therefore,
we introduce the lower truncation level as a compensation to maintain the
degree of bootstrapping. This will be illustrated in detail in Section 3.3.

### 3.2 The Generalized Projected Bellman Equation

We next theoretically analyze Algorithm 3. Specifically, in this section, we
formulate Algorithm 3 as a stochastic approximation algorithm for solving a
generalized projected Bellman equation (PBE) and study its properties. We
begin by stating our assumption.

######  Assumption 3.1.

The behavior policy $\pi_{b}$ satisfies $\pi_{b}(a|s)>0$ for all $(s,a)$, and
induces an irreducible and aperiodic Markov chain $\\{S_{k}\\}$.

Assumption 3.1 was commonly imposed in existing work [53, 6] to ensure that
the behavior policy has sufficient exploration, which is known to be a
necessary component for learning. Under Assumption 3.1, the Markov chain
$\\{S_{k}\\}$ induced by $\pi_{b}$ has a unique stationary distribution
$\mu\in\Delta^{|\mathcal{S}|}$. Moreover, there exist $C\geq 1$ and
$\sigma\in(0,1)$ such that
$\max_{s\in\mathcal{S}}\|P^{k}_{\pi_{b}}(s,\cdot)-\mu(\cdot)\|_{\text{TV}}\leq
C\sigma^{k}$ for all $k\geq 0$, where $P_{\pi_{b}}$ is the transition
probability matrix of the Markov chain $\\{S_{k}\\}$ under $\pi_{b}$ [30].

For simplicity of notation, denote $c_{i,j}=\prod_{k=i}^{j}c(S_{k},A_{k})$.
Algorithm 3 can be viewed as a stochastic iterative algorithm for solving the
following system of equations (in terms of $w$):

$\displaystyle\mathbb{E}_{S_{0}\sim\mu}\left[\phi(S_{0},A_{0})\sum_{i=0}^{n-1}\gamma^{i}c_{1,i}\Delta_{i}(w)\right]=\bm{0},$
(4)

where $A_{i}\sim\pi_{b}(\cdot|S_{i})$ and $S_{i+1}\sim
P_{A_{i}}(S_{i},\cdot)$. The following lemma formulates Eq. (4) in the form of
a generalized PBE.

To present the lemma, we need to introduce more notation. Let
$\mathcal{K}_{SA}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|\times|\mathcal{S}||\mathcal{A}|}$
be a diagonal matrix with diagonal entries
$\\{\mu(s)\pi_{b}(a|s)\\}_{(s,a)\in\mathcal{S}\times\mathcal{A}}$, and let
$\mathcal{K}_{SA,\min}$ be the minimal diagonal entry. Let
$\|\cdot\|_{\mathcal{K}_{SA}}$ be the weighted $\ell_{2}$-norm with weights
$\\{\mu(s)\pi_{b}(a|s)\\}_{(s,a)\in\mathcal{S}\times\mathcal{A}}$, and denote
$\text{Proj}_{\mathcal{Q}}$ as the projection operator onto the linear sub-
space $\mathcal{Q}$ with respect to $\|\cdot\|_{\mathcal{K}_{SA}}$. Let
$\mathcal{T}_{c},\mathcal{H}_{\rho}:\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}\mapsto\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$
be two operators defined as

$\displaystyle[\mathcal{T}_{c}(Q)](s,a)$
$\displaystyle=\sum_{i=0}^{n-1}\mathbb{E}_{\pi_{b}}[\gamma^{i}c_{1,i}Q(S_{i},A_{i})\mid
S_{0}=s,A_{0}=a]$ $\displaystyle[\mathcal{H}_{\rho}(Q)](s,a)$
$\displaystyle=\mathcal{R}(s,a)+\gamma\mathbb{E}_{\pi_{b}}[\rho(S_{1},A_{1})Q(S_{1},A_{1})\mid
S_{0}=s,A_{0}=a]$

for any $Q\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$ and state-action pair
$(s,a)$.

######  Lemma 3.1.

Eq. (4) is equivalent to:

$\displaystyle\Phi w=\text{Proj}_{\mathcal{Q}}\mathcal{B}_{c,\rho}(\Phi w),$
(5)

where $\mathcal{B}_{c,\rho}(\cdot)$ is the generalized Bellman operator
defined as
$\mathcal{B}_{c,\rho}(Q)=\mathcal{T}_{c}(\mathcal{H}_{\rho}(Q)-Q)+Q$ for any
$Q\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$.

The generalized Bellman operator $\mathcal{B}_{c,\rho}(\cdot)$ was previously
introduced in [14] to study off-policy TD-learning algorithms in the tabular
setting (i.e., $\Phi=I_{SA}$), where the contraction property of
$\mathcal{B}_{c,\rho}(\cdot)$ (as well as its asynchronous variant) was shown.
However, $\mathcal{B}_{c,\rho}(\cdot)$ alone being a contraction is not enough
to guarantee the convergence of Algorithm 3 because of the use of function
approximation, which adds an additional projection operator
$\text{Proj}_{\mathcal{Q}}$. What we truly need for the stability and accuracy
of Algorithm 3 is that (1) the composed operator
$\text{Proj}_{\mathcal{Q}}\mathcal{B}_{c,\rho}(\cdot)$ is a contraction
mapping, and (2) the solution $w_{c,\rho}^{\pi}$ of Eq. (5) is such that $\Phi
w_{c,\rho}^{\pi}$ is a valid approximation of the $Q$-function $Q^{\pi}$. We
next provide sufficient conditions on the choices of the generalized
importance sampling factors $c(\cdot,\cdot)$ and $\rho(\cdot,\cdot)$, and the
bootstrapping parameter $n$ so that the above two requirements are satisfied.

Let
$D_{c},D_{\rho}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|\times|\mathcal{S}||\mathcal{A}|}$
be two diagonal matrices such that
$D_{c}((s,a),(s,a))=\sum_{a^{\prime}\in\mathcal{A}}\pi_{b}(a^{\prime}|s)c(s,a^{\prime})$
and
$D_{\rho}((s,a),(s,a))=\sum_{a^{\prime}\in\mathcal{A}}\pi_{b}(a^{\prime}|s)\rho(s,a^{\prime})$
for all $(s,a)$. Let $D_{c,\max}$ and $D_{\rho,\max}$ ($D_{c,\min}$ and
$D_{\rho,\min}$) be the maximam (minimum) diagonal entries of the matrices
$D_{c}$ and $D_{\rho}$, respectively.

######  Condition 3.1.

The generalized importance sampling factors $c(\cdot,\cdot)$ and
$\rho(\cdot,\cdot)$ satisfy (1) $c(s,a)\leq\rho(s,a)$ for all $(s,a)$, (2)
$D_{\rho,\max}<1/\gamma$, and (3)
$\frac{\gamma(D_{\rho,\max}-D_{c,\min})}{(1-\gamma
D_{c,\min})\sqrt{\mathcal{K}_{SA,\min}}}<1$.

Condition 3.1 (1) and (2) were previously introduced in [14], and were used to
show the contraction property of the operator $\mathcal{B}_{c,\rho}(\cdot)$.
In particular, it was shown that the generalized Bellman operator
$\mathcal{B}_{c,\rho}(\cdot)$ is a contraction mapping with respect to
$\|\cdot\|_{\infty}$, with contraction factor
$\tilde{\gamma}(n)=1-f_{n}(\gamma D_{c,\min})(1-\gamma D_{\rho,\max})$, where
$f_{n}:\mathbb{R}\mapsto\mathbb{R}$ is defined as
$f_{n}(x)=\sum_{i=0}^{n-1}x^{i}$ for any $x\geq 0$. It is clear that
$\tilde{\gamma}(n)\in(0,1)$, and is a decreasing function of $n$.

As illustrated earlier, $\mathcal{B}_{c,\rho}(\cdot)$ being a contraction
mapping is not sufficient to guarantee the stability of Algorithm 3. We need
the composed operator $\text{Proj}_{\mathcal{Q}}\mathcal{B}_{c,\rho}(\cdot)$
to be contraction mapping with appropriate choice of $n$. This is guaranteed
by Condition 3.1 (3). To see this, first note that we have the following
lemma, which is obtained by using the contraction property of
$\mathcal{B}_{c,\rho}(\cdot)$ and the “equivalence” between norms in finite-
dimensional spaces.

######  Lemma 3.2.

Under Condition 3.1, it holds for any
$Q_{1},Q_{2}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$ that

$\displaystyle\|\text{Proj}_{\mathcal{Q}}\mathcal{B}_{c,\rho}(Q_{1})-\text{Proj}_{\mathcal{Q}}\mathcal{B}_{c,\rho}(Q_{2})\|_{\mathcal{K}_{SA}}\leq\frac{\tilde{\gamma}(n)}{\sqrt{\mathcal{K}_{SA,\min}}}\|Q_{1}-Q_{2}\|_{\mathcal{K}_{SA}}.$

In view of Lemma 3.2, the composed operator
$\text{Proj}_{\mathcal{Q}}\mathcal{B}_{c,\rho}(\cdot)$ can be made a
contraction mapping with an appropriate choice of $n$ as long as
$\lim_{n\rightarrow\infty}\tilde{\gamma}(n)/\sqrt{\mathcal{K}_{SA,\min}}<1$,
which after some algebra is equivalent to Condition 3.1 (3).

We next show that the generalized importance sampling factors designed for the
$\lambda$-averaged $Q$-trace and the two-sided $Q$-trace satisfy Condition 3.1
(3). First consider the $\lambda$-averaged $Q$-trace algorithm. Since both
$D_{c}$ and $D_{\rho}$ are identity matrices (which implies
$D_{\rho,\max}=D_{c,\min}=1$), Condition 3.1 (3) is always satisfied. Next
consider the two-sided $Q$-trace algorithm. For any choice of the upper
truncation level $u\geq\bm{1}$, we can always choose the lower truncation
level $\bm{0}\leq\ell\leq\bm{1}$ appropriately to satisfy Condition 3.1 (3).
Specifically, for any $s\in\mathcal{S}$ and $u(s)\geq 1$, choosing
$\ell(s)\leq 1$ such that
$\sum_{a\in\mathcal{A}}\pi_{b}(a|s)g_{\ell(s),u(s)}(\pi(a|s)/\pi_{b}(a|s))=1$
satisfies Condition 3.1 (3). However, suppose we only truncate the importance
sampling factors from above as in existing off-policy TD-learning algorithms
such as Retrace$(\lambda)$ [37], $Q^{\pi}(\lambda)$ [20], $V$-trace [19], and
$Q$-trace [22]. It is not clear if we can make $D_{\rho,\max}$ and
$D_{c,\min}$ arbitrarily close to satisfy Condition 3.1 (3). That is technical
reason for us to introduce the lower truncation levels.

In the next lemma, we show that under Condition 3.1, with properly chosen $n$,
the composed operator $\text{Proj}_{\mathcal{Q}}\mathcal{B}_{c,\rho}(\cdot)$
is a contraction mapping, which ensures that Eq. (5) has a unique solution,
denoted by $w_{c,\rho}^{\pi}$. Moreover, we provide performance guarantees on
the solution $w_{c,\rho}^{\pi}$ in terms of an upper bound on the difference
between the target value function $Q^{\pi}$ and our estimate $\Phi
w_{c,\rho}^{\pi}$. Let $Q_{c,\rho}^{\pi}$ be the solution of generalized
Bellman equation $Q=\mathcal{B}_{c,\rho}(Q)$, which is guaranteed to exist and
is unique since $\mathcal{B}_{c,\rho}(\cdot)$ itself is a contraction mapping
under Condition 3.1 (1) and (2) [14].

######  Lemma 3.3.

Under Condition 3.1, suppose that the parameter $n$ is chosen such that
$\gamma_{c}:=\tilde{\gamma}(n)/\sqrt{\mathcal{K}_{SA,\min}}<1$. Then the
composed operator $\text{Proj}_{\mathcal{Q}}\mathcal{B}_{c,\rho}(\cdot)$ is a
$\gamma_{c}$-contraction mapping with respect to
$\|\cdot\|_{\mathcal{K}_{SA}}$. In this case, the unique solution
$w_{c,\rho}^{\pi}$ of the generalized PBE (cf. Eq. (5)) satisfies

$\displaystyle\|Q^{\pi}-\Phi
w_{c,\rho}^{\pi}\|_{\mathcal{K}_{SA}}\leq\frac{\|Q_{c,\rho}^{\pi}-\text{Proj}_{\mathcal{Q}}Q_{c,\rho}^{\pi}\|_{\mathcal{K}_{SA}}}{\sqrt{1-\gamma_{c}^{2}}}+\frac{\gamma\max_{s\in\mathcal{S}}\|\pi(\cdot|s)-\pi_{b}(\cdot|s)\rho(s,\cdot)\|_{1}}{(1-\gamma)(1-\gamma
D_{\rho,\max})}.$ (6)

The first term on the RHS of Eq. (6) captures the error due to function
approximation, which is in the same spirit to Theorem 1 (4) of the seminal
paper [53], and vanishes in the tabular setting. The second term on the RHS of
Eq. (6) arises because of the use of generalized importance sampling factors,
which are introduced to overcome the high variance in off-policy learning.
Note that the second term vanishes when $\rho(s,a)=\pi(a|s)/\pi_{b}(a|s)$ for
all $(s,a)$, which corresponds to choosing $\lambda=\bm{1}$ in
$\lambda$-averaged $Q$-trace or choosing
$\ell(s)\leq\min_{s,a}\pi(a|s)/\pi_{b}(a|s)$ and
$u(s)\geq\max_{s,a}\pi(a|s)/\pi_{b}(a|s)$ for all $s$ in two-sided $Q$-trace.
However, in these cases, the cumulative product of importance sampling factors
leads to a high variance in Algorithm 3. The trade-off between the variance
and the bias in $w_{c,\rho}^{\pi}$ (i.e., second term on the RHS of Eq. (6))
will be illustrated in detail in the next subsection where we present the
finite-sample bound of Algorithm 3.

### 3.3 Finite-Sample Analysis

With the contraction property of the generalized PBE established, when the
stepsize sequence is non-summable but squared-summable, the almost sure
convergence of Algorithm 3 directly follows from standard stochastic
approximation results in the literature [4, 8]. In this section, we perform
finite-sample analysis of Algorithm 3. For ease of exposition, we here only
present the finite-sample bounds of $\lambda$-averaged $Q$-trace and two-sided
$Q$-trace, where $c(\cdot,\cdot)$ and $\rho(\cdot,\cdot)$ are explicitly
specified. For the finite-sample guarantees of Algorithm 3 with more general
choices of $c(\cdot,\cdot)$ and $\rho(\cdot,\cdot)$ (as long as Condition 3.1
is satisfied), please see Section 5.2.

For any $\delta>0$, let $t_{\delta}=\min\\{k\geq
0:\max_{s\in\mathcal{S}}\|P_{\pi_{b}}^{k}(s,\cdot)-\mu(\cdot)\|_{\text{TV}}\leq\delta\\}$
be the mixing time of the Markov chain $\\{S_{k}\\}$ induced by $\pi_{b}$ with
precision $\delta$. Note that Assumption 3.1 implies that
$t_{\delta}=\mathcal{O}(\log(1/\delta))$. Let $\lambda_{\min}$ be the mininum
eigenvalue of the positive definite matrix $\Phi^{\top}\mathcal{K}_{SA}\Phi$.
Let $L=1+(\gamma\rho_{\max})^{n}$, where $\rho_{\max}=\max_{s,a}\rho(s,a)$. We
next present finite-sample guarantees of the $\lambda$-averaged $Q$-trace
algorithm.

######  Theorem 3.1.

Consider $\\{w_{k}\\}$ of the $\lambda$-averaged $Q$-trace Algorithm. Suppose
that (1) Assumption 3.1 is satisfied, (2) $\lambda\in[\bm{0},\bm{1}]$, (3) the
parameter $n$ is chosen such that
$\gamma_{c}:=\gamma^{n}/\sqrt{\mathcal{K}_{SA,\min}}<1$. Then, when using
constant stepsize $\alpha$ satisfying
$\alpha(t_{\alpha}+n+1)\leq\frac{(1-\gamma_{c})\lambda_{\min}}{130L^{2}}$, we
have for all $k\geq t_{\alpha}+n+1$:

$\displaystyle\mathbb{E}[\|w_{k}-w_{c,\rho}^{\pi}\|_{2}^{2}]\leq
c_{1}(1-(1-\gamma_{c})\lambda_{\min}\alpha)^{k-(t_{\alpha}+n+1)}+c_{2}\frac{\alpha
L^{2}(t_{\alpha}+n+1)}{(1-\gamma_{c})\lambda_{\min}},$ (7)

where $c_{1}=(\|w_{0}\|_{2}+\|w_{0}-w_{c,\rho}^{\pi}\|_{2}+1)^{2}$ and
$c_{2}=130(\|w_{c,\rho}^{\pi}\|_{2}+1)^{2}$. Moreover, we have

$\displaystyle\|Q^{\pi}-\Phi
w_{c,\rho}^{\pi}\|_{\mathcal{K}_{SA}}\leq\frac{\|Q_{c,\rho}^{\pi}-\text{Proj}_{\mathcal{Q}}Q_{c,\rho}^{\pi}\|_{\mathcal{K}_{SA}}}{\sqrt{1-\gamma_{c}^{2}}}+\frac{\gamma\max_{s\in\mathcal{S}}(1-\lambda(s))\|\pi(\cdot|s)-\pi_{b}(\cdot|s)\|_{1}}{(1-\gamma)^{2}}.$
(8)

Following the common terminology in stochastic approximation literature, we
call the first term on the RHS of Eq. (7) convergence bias, and the second
term variance. When constant stepsize is used, the convergence bias goes to
zero at a geometric rate while the variance is a constant roughly proportional
to $\alpha t_{\alpha}$. Since $\lim_{\alpha\rightarrow 0}\alpha t_{\alpha}=0$
under Assumption 3.1, the variance can be made arbitrarily small by using
small $\alpha$.

The parameter $L=1+(\gamma\rho_{\max})^{n}$ plays an important role in the
finite-sample bound. In fact, $L$ appears quadratically in the variance term
of Eq. (7), and captures the impact of the cumulative product of the
importance sampling factors. To overcome the high variance in off-policy
learning (i.e., to make sure that the parameter $L=1+(\gamma\rho_{\max})^{n}$
does not grow exponentially fast with respect to $n$), we choose
$\lambda\in\mathbb{R}^{|\mathcal{S}|}$ such that
$\rho_{\max}=\max_{s}\lambda(s)(\max_{a}\pi(a|s)/\pi_{b}(a|s)-1)+1\leq
1/\gamma$. However, as long as $\lambda\neq\bm{1}$, the limit point of the
$\lambda$-averaged $Q$-trace algorithm involves an additional bias term (i.e.,
the second term on the RHS of Eq. (8)) that does not vanish even in the
tabular setting. Suppose that the target policy $\pi$ is close to the behavior
policy $\pi_{b}$ in the sense that $\max_{s,a}\pi(a|s)/\pi_{b}(a|s)$ is not
too large ($\max_{s,a}\pi(a|s)/\pi_{b}(a|s)\leq 1/\gamma$ to be precise), we
can still choose $\lambda$ close to $\bm{1}$ to avoid the high variance while
also produce a relatively accurate estimate to $Q^{\pi}$. If that is not the
case, then there is a trade-off between the variance in the algorithm and the
bias in the limit point in choosing the parameter $\lambda$. Specifically,
large $\lambda$ leads to large $\rho_{\max}$ and hence large $L$ and large
variance, but in this case the second term on the RHS of Eq. (6) is smaller,
implying that we have a smaller bias in the limit point.

The previous discussion also justifies using soft versions of argmax for the
actor in updating the policies (as presented in Section 2). Recall that in the
on-policy setting, API with hardmax policy update suffers from exploration
issues as deterministic policies have no exploration components. In the off-
policy setting, while in principle hardmax policy update can be used as the
behavior policy has taken care of the exploration, it is still not a
preferable choice. The reason is that there will be either a large variance or
a large bias because $\pi_{t}$ and $\pi_{b}$ are in some sense most different
because $\pi_{t}$ is a deterministic policy but $\pi_{b}$ should guarantee
sufficient exploration for all actions.

Next, we present the finite-sample bounds of the two-sided $Q$-trace
algorithm.

######  Theorem 3.2.

Consider $\\{w_{k}\\}$ of the two-sided $Q$-trace Algorithm. Suppose that (1)
Assumption 3.1 is satisfied, (2) the upper and lower truncation levels
$\ell,u\in\mathbb{R}^{|\mathcal{S}|}$ are chosen such that
$\sum_{a\in\mathcal{A}}\pi_{b}(a|s)g_{\ell(s),u(s)}(\pi(a|s)/\pi_{b}(a|s))=1$
for all $s$, (3) the parameter $n$ is chosen such that
$\gamma_{c}:=\gamma^{n}/\sqrt{\mathcal{K}_{SA,\min}}<1$, and (4) the stepsize
$\alpha$ is chosen such that
$\alpha(t_{\alpha}+n+1)\leq\frac{(1-\gamma_{c})\lambda_{\min}}{130L^{2}}$.
Then, we have for all $k\geq t_{\alpha}+n+1$ that

$\displaystyle\mathbb{E}[\|w_{k}-w_{c,\rho}^{\pi}\|_{2}^{2}]\leq
c_{1}(1-(1-\gamma_{c})\lambda_{\min}\alpha)^{k-(t_{\alpha}+n+1)}+c_{2}\frac{\alpha
L^{2}(t_{\alpha}+n+1)}{(1-\gamma_{c})\lambda_{\min}},$ (9)

where $c_{1}=(\|w_{0}\|_{2}+\|w_{0}-w_{c,\rho}^{\pi}\|_{2}+1)^{2}$ and
$c_{2}=130(\|w_{c,\rho}^{\pi}\|_{2}+1)^{2}$. Moreover, we have

$\displaystyle\|Q^{\pi}-\Phi w_{c,\rho}^{\pi}\|_{\mathcal{K}_{SA}}\leq\;$
$\displaystyle\frac{1}{\sqrt{1-\gamma_{c}^{2}}}\|Q_{c,\rho}^{\pi}-\Phi
w_{c,\rho}^{\pi}\|_{\mathcal{K}_{SA}}$
$\displaystyle+\frac{\gamma\max_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}}(u_{\pi,\pi_{b}}(s,a)-\ell_{\pi,\pi_{b}}(s,a))}{(1-\gamma)^{2}},$
(10)

where $u_{\pi,\pi_{b}}(s,a)=\max(\pi(a|s)-\pi_{b}(a|s)u(s),0)$ and
$\ell_{\pi,\pi_{b}}(s,a)=\min(\pi(a|s)-\pi_{b}(a|s)\ell(s),0)$.

The finite-sample bound of the two-sided $Q$-trace algorithm is qualitatively
similar to that of the $\lambda$-averaged $Q$-trace algorithm. To overcome the
high variance issue in off-policy learning, we choose the upper truncation
level such that $\gamma u(s)\leq 1$ for all $s$, which ensures that the
parameter $L=1+(\gamma\rho_{\max})^{n}$ is upper bounded by
$1+(\gamma\max_{s}u(s))^{n}$, hence does not grow exponentially with respect
to $n$. Then we choose the lower truncation level accordingly to satisfy
requirement (2) stated in Theorem 3.2. However, as long as there exists
$s\in\mathcal{S}$ such that $u(s)<\max_{s,a}\pi(a|s)/\pi_{b}(a|s)$ or
$\ell(s)>\min_{s,a}\pi(a|s)/\pi_{b}(a|s)$, the second term on the RHS of Eq.
(3.2) is in general non-zero, hence adding an additional bias term to the
limit point even in the tabular setting. As a result, the trade-off between
the variance and the bias in the limit point is also present in the two-sided
$Q$-trace algorithm.

In view of Theorems 3.1 and 3.2, one limitation of this work is that the
choice of $n$ to make $\gamma_{c}<1$ (which is needed for the stability of
Algorithm 3) depends on the unknown parameter $\mathcal{K}_{SA,\min}$ of the
problem. In practice, one can start with a specific choice of $n$ and then
gradually tune $n$ to achieve the convergence of the $\lambda$-averaged
$Q$-trace algorithm or the two-sided $Q$-trace algorithm.

The proof of Theorems 3.1 and 3.2 are presented in Section 5.2. In fact, we
will prove a more general theorem for Algorithm 3 with generalized importance
sampling factors satisfying Condition 3.1, which covers $\lambda$-averaged
$Q$-trace and two-sided $Q$-trace as its special cases. In Section 5.2, we
will also present the finite-sample bound for using linearly diminishing
stepsizes, as opposed to using only constant stepsize in Theorems 3.1 and 3.2.

## 4 The Sample Complexity of Policy-Based Methods

To this end, we have established the finite-time bound of the actor for using
various policy update rules and finite-sample bound of the critic under off-
policy sampling and linear function approximation. In this section, we combine
the actor and the critic together and present the overall sample complexity
bounds of policy-based methods.

Algorithm 4 A Generic Policy-Based Algorithm: Off-Policy Sampling and Linear
Function Approximation

1: Input: Integers $T,K$, initialization
$\pi_{0}(\cdot|s)\sim\text{Unif}(\mathcal{A})$ for all $s\in\mathcal{S}$,
$\theta_{0}=\bm{0}$, and a sample trajectory $\\{(S_{t},A_{t})\\}_{0\leq t\leq
T(K+n)}$ collected under the behavior policy $\pi_{b}$.

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

3:
$w_{t+1}=\text{ALG}(\bm{0},\pi_{t},\pi_{b},\alpha,K,\\{(S_{k},A_{k})\\}_{t(K+n)\leq
k\leq(t+1)(K+n)-1})$

4: Option I: Natural Policy
Gradient:$\theta_{t+1}=\theta_{t}+\beta_{t}w_{t+1}$ Compute
$\pi_{t+1}(a|s)=\frac{\exp(\phi(s,a)^{\top}\theta_{t+1})}{\sum_{a^{\prime}\in\mathcal{A}}\exp(\phi(s,a^{\prime})^{\top}\theta_{t+1})}$
at $(s,a)=(S_{i},A_{i})$ for all $i=(t+1)(K+n),\cdots,(t+2)(K+n)-1$.

5: Option II: Boltzmann Softmax Update:Compute
$\pi_{t+1}(a|s)=\frac{\exp(\beta_{t}\phi(s,a)^{\top}w_{t+1})}{\sum_{a^{\prime}\in\mathcal{A}}\exp(\beta_{t}\phi(s,a^{\prime})^{\top}w_{t+1})}$
at $(s,a)=(S_{i},A_{i})$ for all $i=(t+1)(K+n),\cdots,(t+2)(K+n)-1$.

6: Option III: $\epsilon$-Greedy Update:Compute
$\displaystyle\pi_{t+1}(a|s)=\begin{dcases}\beta_{t}/|\mathcal{A}|,&a\neq{\arg\max}_{a^{\prime}\in\mathcal{A}}\phi(s,a^{\prime})^{\top}w_{t+1},\\\
\beta_{t}/|\mathcal{A}|+1-\beta_{t},&a={\arg\max}_{a^{\prime}\in\mathcal{A}}\phi(s,a^{\prime})^{\top}w_{t+1},\end{dcases}$
at $(s,a)=(S_{i},A_{i})$ for all $i=(t+1)(K+n),\cdots,(t+2)(K+n)-1$.

7: end for

8: Output: $\pi_{T}$

We begin by presenting the algorithm design for general policy-based methods
in Algorithm 4, which can be viewed as an extension of Algorithm 1 to the case
where off-policy sampling and linear function approximation are used. Note
that Algorithm 4 line 3 corresponds to Algorithm 1 line 3, where the critic
implements Algorithm 3 for policy evaluation with off-policy data. For
simplicity of notation, for a given target policy $\pi$, behavior policy
$\pi_{b}$, constant stepsize $\alpha$, initialization $w_{0}$, and samples
$\\{(S_{k},A_{k})\\}_{0\leq k\leq K+n-1}$, we have denoted the output of
Algorithm 3 after $K$ iterations by
$w=\text{ALG}(w_{0},\pi,\pi_{b},\alpha,K,\\{(S_{k},A_{k})\\}_{0\leq k\leq
K+n-1})$.

Algorithm 4 lines 4, 5, 6 correspond to Algorithm 1 line 4, where we update
the policy. Note that ideally we would like to perform $\pi_{t+1}=G(\Phi
w_{t},\pi_{t})$ for policy improvement, where $\Phi w_{t}$ is the $Q$-function
estimate associated with the weight vector $w_{t}$, and $G(\cdot,\cdot)$ is
the policy update rule. However, directly implementing $\pi_{t+1}=G(\Phi
w_{t},\pi_{t})$ violates the purpose of using function approximation as it
requires to compute $\Phi w_{t}$, $\pi_{t}$, and the the output of
$G(\cdot,\cdot)$, which are all $|\mathcal{S}||\mathcal{A}|$-dimensional
objects. Algorithm 4 lines 4,5,6 can be viewed as an equivalent way of
implementing Algorithm 1 line 4 without working with
$|\mathcal{S}||\mathcal{A}|$-dimensional objects. We next elaborate on such
equivalence.

Let us first look at the case of using natural policy gradient. Recall in Eq.
(1) that natural policy gradient updates the policy according to

$\displaystyle\pi_{t+1}(a|s)=\frac{\pi_{t}(a|s)\exp(\beta_{t}Q_{t}(s,a))}{\sum_{a^{\prime}\in\mathcal{A}}\pi_{t}(a^{\prime}|s)\exp(\beta_{t}Q_{t}(s,a^{\prime}))},\quad\forall\;(s,a),$

where $\pi_{t}$ is the previous policy and $Q_{t}$ is $\pi_{t}$’s $Q$-function
estimate. Therefore, to use function approximation, parametrizing only the
$Q$-function as in Section 3 is not sufficient, we also need to keep track of
the policies. Inspired by [1], we use compatible linear function approximation
to parametrize the policy, i.e., we approximate policies using
$\pi_{\theta}(a|s)=\frac{\exp(\phi(s,a)^{\top}\theta)}{\sum_{a^{\prime}\in\mathcal{A}}\exp(\phi(s,a^{\prime})^{\top}\theta)}$,
where $\phi(s,a)$ is the same feature we used in approximating the
$Q$-functions, and $\theta\in\mathbb{R}^{d}$ is the weight vector. It has been
shown in [12, Lemma 3.1] that with the weight vector being updated according
to $\theta_{t+1}=\theta_{t}+\beta_{t}w_{t}$ (which involves only
$d$-dimesional objects), the corresponding policy is equivalently updated
according to

$\displaystyle\pi_{t+1}(a|s)=\frac{\pi_{t}(a|s)\exp(\beta_{t}\phi(s,a)^{\top}w_{t})}{\sum_{a^{\prime}\in\mathcal{A}}\pi_{t}(a^{\prime}|s)\exp(\beta_{t}\phi(s,a^{\prime})^{\top}w_{t})},\quad\forall\;(s,a),$

which is exactly the natural policy gradient update.

Next we consider API with either Boltzmann softmax update or $\epsilon$-greedy
update. Recall that in these two cases the next policy $\pi_{t+1}$ depends
only on the estimate of the $Q$-function $Q_{t}$, and not on the previous
policy. Since we already parametrized the $Q$-function, there is no need to
parametrize the policy. Moreover, since implementing the policy evaluation
algorithm (cf. Algorithm 3) requires only the target policy value at state-
action pairs that are visited by the sample trajectory generated by the
behavior policy, we do not need to work with
$|\mathcal{S}||\mathcal{A}|$-dimensional objects in either the actor or the
critic in Algorithm 4.

We next present the finite-sample bounds of Algorithm 4. For ease of
exposition, in Algorithm 3 for policy evaluation, we consider using the
generalized importance sampling factors according to $\lambda$-averaged
$Q$-trace. For two sided $Q$-trace or more general importance sampling factors
(as long as Condition 3.1 is satisfied), the results are straight forward
extensions.

######  Theorem 4.1.

Consider $\pi_{T}$ generated by Algorithm 4. Suppose that the assumptions for
applying Theorem 3.1 are satisfied. Then under Condition 2.1, we have

$\displaystyle\mathbb{E}[\|Q^{*}-Q^{\pi_{T}}\|_{\infty}]\leq\;$
$\displaystyle\underbrace{\gamma^{T}\|Q^{*}-Q^{\pi_{0}}\|_{\infty}}_{N_{1}:\text{
Convergence bias in the
actor}}+\underbrace{\frac{2\gamma\mathcal{E}_{\text{approx}}}{(1-\gamma)^{2}}}_{N_{2,1}}+\underbrace{\frac{2\gamma^{2}\mathcal{E}_{\text{bias}}}{(1-\gamma)^{4}}}_{N_{2,2}}+$
$\displaystyle+\underbrace{\frac{6(1-(1-\gamma_{c})\lambda_{\min}\alpha)^{\frac{1}{2}[K-(t_{\alpha}+n+1)]}}{(1-\gamma)^{3}(1-\gamma_{c})^{1/2}\lambda_{\min}^{1/2}}}_{N_{2,3}:\text{
Convergence bias in the
critic}}+\underbrace{\frac{70L[\alpha(t_{\alpha}+n+1)]^{1/2}}{\lambda_{\min}(1-\gamma_{c})(1-\gamma)^{3}}}_{N_{2,4}:\text{
Critic variance}}$
$\displaystyle+\underbrace{\frac{2\gamma\beta}{(1-\gamma)^{2}}}_{N_{3}},$ (11)

where $\mathcal{E}_{\text{approx}}=\sup_{\pi}\|Q_{c,\rho}^{\pi}-\Phi
w_{c,\rho}^{\pi}\|_{\infty}$ and $\mathcal{E}_{\text{bias}}=\max_{0\leq t\leq
T}\max_{s\in\mathcal{S}}(1-\lambda(s))\|\pi_{t}(\cdot|s)-\pi_{b}(\cdot|s)\|_{1}$.
Under Condition 2.2, we have

$\displaystyle\mathbb{E}[\|Q^{*}-Q^{\pi_{T}}\|_{\infty}]\leq
N_{1}+\sum_{i=1}^{4}N_{2,i}+\underbrace{\frac{2\gamma^{T}}{(1-\gamma)^{2}}}_{N_{3}^{\prime}}.$

Notably on the LHS, our finite-sample guarantees are stated for the last
policy iterate $\pi_{T}$, while in many existing literature it was stated for
the best policy among $\\{\pi_{t}\\}_{0\leq t\leq T}$ [1], or a uniform sample
from $\\{\pi_{t}\\}_{0\leq t\leq T-1}$ [22, 60].

The terms $N_{1}$ and $N_{3}$ (or $N_{3}^{\prime}$) are the same terms
appeared in Theorem 2.1, and together capture the error in the actor update.
This was illustrated right after Theorem 2.1. The terms $\\{N_{2,i}\\}_{1\leq
i\leq 4}$ correspond to the term $N_{2}$ in Theorem 2.1, and represent the
error in the critic. Specifically, $N_{2,1}$ is the function approximation
error, and is equal to zero when we use a complete basis (i.e., tabular
setting). A term of similar form is present in all existing work studying RL
with function approximation, see for example the inherent Bellman error in
[36], and the transfer error in [1]. The term $N_{2,2}$ represents the bias
introduced to the algorithm by using generalized importance sampling factors
$c(\cdot,\cdot)$ and $\rho(\cdot,\cdot)$. Note that we have $N_{2,2}=0$ when
$c(s,a)=\rho(s,a)=\pi(a|s)/\pi_{b}(a|s)$, which corresponds to using
$\lambda=\bm{1}$ in the $\lambda$-averaged $Q$-trace algorithm, and using
$u(s)\geq\max_{s,a}\pi(a|s)/\pi_{b}(a|s)$ and
$\ell(s)\leq\min_{s,a}\pi(a|s)/\pi_{b}(a|s)$ for all $s$ in the two-sided
$Q$-trace algorithm. However, this choice of $\lambda$ (or $u$ and $\ell$)
might lead to a high variance. In particular, the parameter $L$ within the
term $N_{2,4}$ could be large. Such bias-variance trade-off was illustrated in
Section 3. The term $N_{2,3}$ represents the convergence bias in the critic,
and goes to zero geometrically fast as the inner loop iteration index $K$ goes
to infinity. The term $N_{2,4}$ represents the variance in the critic, and is
proportional to $\sqrt{\alpha
t_{\alpha}}=\mathcal{O}(\sqrt{\alpha\log(1/\alpha)})$. Therefore, $N_{2,4}$
can be made arbitrarily small by using small enough stepsize $\alpha$.

Based on Theorem 4.1, we next derive the sample complexity of Algorithm 4. To
enable fair comparison with existing literature, we choose $\lambda=\bm{1}$ to
eliminate the error due to using generalized importance sampling factors. Note
that $\lambda=\bm{1}$ implies $\mathcal{E}_{\text{bias}}=0$ (and hence
$N_{2,2}=0$) in Theorem 4.1.

######  Corollary 4.1.1.

For a given accuracy level $\epsilon>0$, to achieve
$\mathbb{E}[\|Q^{*}-Q^{\pi_{T}}\|_{\infty}]\leq\epsilon+N_{2,1}$, the number
of samples (i.e., the integer $TK$) required is of the size
$\mathcal{O}\left(\frac{\log^{3}(1/\epsilon)}{\epsilon^{2}}\right)\tilde{\mathcal{O}}\left(\frac{L^{2}n}{(1-\gamma)^{7}(1-\gamma_{c})^{3}\lambda_{\min}^{3}}\right)$.

Notably, we obtain $\tilde{\mathcal{O}}(\epsilon^{-2})$ sample complexity for
policy-based methods, which matches with the sample complexity of value-based
algorithms such as $Q$-learning [31]. In the case of natural actor-critic, to
our knowledge, [10, 28, 11] establish the $\tilde{\mathcal{O}}(\epsilon^{-2})$
sample complexity of on-policy natural actor-critic under regularization, and
[12] establishes the $\tilde{\mathcal{O}}(\epsilon^{-3})$ sample complexity of
a variant of off-policy natural actor-critic. We improve the sample complexity
in [12] by a factor of $\epsilon^{-1}$, and we do not use any regularization.

In addition to the dependence on $\epsilon$, the dependence on $1/(1-\gamma)$
(which is usually called the effective horizon) is also improved by a factor
of $1/(1-\gamma)$ compared to existing work [1, 12]. The bootstrapping
parameter $n$ appears linearly in our sample complexity bound. This matches
with the results for $n$-step TD-learning in the on-policy tabular setting
[13].

The proof of Theorem 4.1 follows from combining the convergence rate analysis
of the actor in Section 2 and the critic in Section 3, and is presented in
Section 5.3.

## 5 Proof of the Main Results

In this section, we present the proof of Theorems 2.1, 3.1, 3.2, and 4.1.

### 5.1 Proof of Theorem 2.1

Following the proof sketch presented in Section 2.4, we next carry out the
details.

####  5.1.1 Step One.

For simplicity of notation, denote
$\delta_{t}=\max_{s,a}(Q^{\pi_{t}}(s,a)-Q^{\pi_{t+1}}(s,a))$ and
$\zeta_{t}=\max_{s,a}(Q^{*}(s,a)-Q^{\pi_{t}}(s,a))=\|Q^{*}-Q^{\pi_{t}}\|_{\infty}$
for all $t=0,1,\cdots,T$. Note that we have by definition that
$Q^{\pi_{t+1}}\geq Q^{\pi_{t}}-\delta_{t}\bm{1}$. Using the monotonicity of
the Bellman operator [4, Lemma 2.1 and Lemma 2.2] and we have

$\displaystyle
Q^{\pi_{t+1}}=\mathcal{H}_{\pi_{t+1}}(Q^{\pi_{t+1}})\geq\mathcal{H}_{\pi_{t+1}}(Q^{\pi_{t}}-\delta_{t}\bm{1})=\mathcal{H}_{\pi_{t+1}}(Q^{\pi_{t}})-\gamma\delta_{t}\bm{1}.$

It follows that

$\displaystyle Q^{\pi_{t}}-Q^{\pi_{t+1}}$ $\displaystyle\leq\;$ $\displaystyle
Q^{\pi_{t}}-\mathcal{H}_{\pi_{t+1}}(Q^{\pi_{t}})+\gamma\delta_{t}\bm{1}$
$\displaystyle=\;$ $\displaystyle
Q^{\pi_{t}}-\mathcal{H}_{\pi_{t+1}}(Q^{\pi_{t}})+\mathcal{H}_{\pi_{t+1}}(Q_{t})-\mathcal{H}_{\pi_{t+1}}(Q_{t})+\mathcal{H}(Q_{t})-\mathcal{H}(Q_{t})+\gamma\delta_{t}\bm{1}$
$\displaystyle\leq\;$
$\displaystyle\mathcal{H}_{\pi_{t}}(Q^{\pi_{t}})-\mathcal{H}_{\pi_{t}}(Q_{t})-\mathcal{H}_{\pi_{t+1}}(Q^{\pi_{t}})+\mathcal{H}_{\pi_{t+1}}(Q_{t})-\mathcal{H}_{\pi_{t+1}}(Q_{t})+\mathcal{H}(Q_{t})+\gamma\delta_{t}\bm{1}$
$\displaystyle\leq\;$ $\displaystyle
2\gamma\|Q^{\pi_{t}}-Q_{t}\|_{\infty}\bm{1}+\|\mathcal{H}_{\pi_{t+1}}(Q_{t})-\mathcal{H}(Q_{t})\|_{\infty}\bm{1}+\gamma\delta_{t}\bm{1}.$

Therefore, we have $\delta_{t}\leq
2\gamma\|Q^{\pi_{t}}-Q_{t}\|_{\infty}+\|\mathcal{H}_{\pi_{t+1}}(Q_{t})-\mathcal{H}(Q_{t})\|_{\infty}+\gamma\delta_{t}$,
which implies

$\displaystyle\delta_{t}\leq\frac{2\gamma\|Q^{\pi_{t}}-Q_{t}\|_{\infty}+\|\mathcal{H}_{\pi_{t+1}}(Q_{t})-\mathcal{H}(Q_{t})\|_{\infty}}{1-\gamma}.$
(12)

Using the monotonicity of the Bellman operator and we have

$\displaystyle Q^{\pi_{t+1}}$
$\displaystyle=\mathcal{H}_{\pi_{t+1}}(Q^{\pi_{t+1}})$
$\displaystyle\geq\mathcal{H}_{\pi_{t+1}}(Q^{\pi_{t}}-\max_{s,a}(Q^{\pi_{t}}(s,a)-Q^{\pi_{t+1}}(s,a))\bm{1})$
$\displaystyle=\mathcal{H}_{\pi_{t+1}}(Q^{\pi_{t}})-\gamma\max_{s,a}(Q^{\pi_{t}}(s,a)-Q^{\pi_{t+1}}(s,a))\bm{1}$
$\displaystyle\geq\mathcal{H}_{\pi_{t+1}}(Q^{\pi_{t}})-\frac{2\gamma^{2}\|Q^{\pi_{t}}-Q_{t}\|_{\infty}+\gamma\|\mathcal{H}_{\pi_{t+1}}(Q_{t})-\mathcal{H}(Q_{t})\|_{\infty}}{1-\gamma}\bm{1},$
(13)

where the last line follows from Eq. (12). We next control
$\mathcal{H}_{\pi_{t+1}}(Q^{\pi_{t}})$ from below in the following. Again by
monotonicity of the Bellman operator we have

$\displaystyle\mathcal{H}_{\pi_{t+1}}(Q^{\pi_{t}})$
$\displaystyle\geq\mathcal{H}_{\pi_{t+1}}(Q_{t}-\|Q_{t}-Q^{\pi_{t}}\|_{\infty}\bm{1})$
$\displaystyle=\mathcal{H}_{\pi_{t+1}}(Q_{t})-\gamma\|Q_{t}-Q^{\pi_{t}}\|_{\infty}\bm{1}$
$\displaystyle=\mathcal{H}_{\pi_{t+1}}(Q_{t})-\mathcal{H}(Q_{t})+\mathcal{H}(Q_{t})-\gamma\|Q_{t}-Q^{\pi_{t}}\|_{\infty}\bm{1}$
$\displaystyle\geq\mathcal{H}_{\pi_{t+1}}(Q_{t})-\mathcal{H}(Q_{t})+\mathcal{H}(Q^{\pi_{t}}-\|Q_{t}-Q^{\pi_{t}}\|_{\infty}\bm{1})-\gamma\|Q_{t}-Q^{\pi_{t}}\|_{\infty}\bm{1}$
$\displaystyle=\mathcal{H}_{\pi_{t+1}}(Q_{t})-\mathcal{H}(Q_{t})+\mathcal{H}(Q^{\pi_{t}})-2\gamma\|Q_{t}-Q^{\pi_{t}}\|_{\infty}\bm{1}$
$\displaystyle\geq\mathcal{H}_{\pi_{t+1}}(Q_{t})-\mathcal{H}(Q_{t})+\mathcal{H}(Q^{*}-\zeta_{t}\bm{1})-2\gamma\|Q_{t}-Q^{\pi_{t}}\|_{\infty}\bm{1}$
$\displaystyle=\mathcal{H}_{\pi_{t+1}}(Q_{t})-\mathcal{H}(Q_{t})+\mathcal{H}(Q^{*})-\gamma\zeta_{t}\bm{1}-2\gamma\|Q_{t}-Q^{\pi_{t}}\|_{\infty}\bm{1}$
$\displaystyle\geq-\|\mathcal{H}_{\pi_{t+1}}(Q_{t})-\mathcal{H}(Q_{t})\|_{\infty}\bm{1}+Q^{*}-\gamma\zeta_{t}\bm{1}-2\gamma\|Q_{t}-Q^{\pi_{t}}\|_{\infty}\bm{1}.$

Using the previous inequality in Eq. (13) and we have

$\displaystyle Q^{\pi_{t+1}}-Q^{*}$
$\displaystyle\geq-\gamma\zeta_{t}\bm{1}-\frac{2\gamma\|Q^{\pi_{t}}-Q_{t}\|_{\infty}+\|\mathcal{H}_{\pi_{t+1}}(Q_{t})-\mathcal{H}(Q_{t})\|_{\infty}}{1-\gamma}\bm{1},$

which implies

$\displaystyle\zeta_{t+1}\leq\gamma\zeta_{t}+\frac{2\gamma\|Q^{\pi_{t}}-Q_{t}\|_{\infty}+\|\mathcal{H}_{\pi_{t+1}}(Q_{t})-\mathcal{H}(Q_{t})\|_{\infty}}{1-\gamma}.$

Repeatedly using the previous inequality and we obtain

$\displaystyle\zeta_{T}\leq\;$
$\displaystyle\gamma^{T}\zeta_{0}+\frac{2\gamma}{1-\gamma}\sum_{t=0}^{T-1}\gamma^{T-1-t}\|Q^{\pi_{t}}-Q_{t}\|_{\infty}$
$\displaystyle+\frac{2\gamma}{1-\gamma}\sum_{t=0}^{T-1}\gamma^{T-1-t}\|\mathcal{H}_{\pi_{t+1}}(Q_{t})-\mathcal{H}(Q_{t})\|_{\infty}.$
(14)

####  5.1.2 Step Two.

We now bound the term
$\|\mathcal{H}_{\pi_{t+1}}(Q_{t})-\mathcal{H}(Q_{t})\|_{\infty}$,
$t=0,\cdots,T-1$, in Eq. (5.1.1). We first consider using natural policy
gradient in Algorithm 1 line 4.

##### Natural Policy Gradient.

For any $0\leq t\leq T-1$ and state-action pair $(s,a)$, using the definition
of the Bellman operators $\mathcal{H}(\cdot)$ and $\mathcal{H}_{\pi}(\cdot)$
and we have

$\displaystyle 0$
$\displaystyle\leq[\mathcal{H}(Q_{t})](s,a)-[\mathcal{H}_{\pi_{t+1}}(Q_{t})](s,a)$
$\displaystyle=\gamma\sum_{s^{\prime}}P_{a}(s,s^{\prime})\left(\max_{a^{\prime}\in\mathcal{A}}Q_{t}(s^{\prime},a^{\prime})-\sum_{a^{\prime}\in\mathcal{A}}\frac{\pi_{t}(a^{\prime}|s^{\prime})\exp(\beta_{t}Q_{t}(s^{\prime},a^{\prime}))}{\sum_{a^{\prime\prime}\in\mathcal{A}}\pi_{t}(a^{\prime\prime}|s^{\prime})\exp(\beta_{t}Q_{t}(s^{\prime},a^{\prime\prime})}Q_{t}(s^{\prime},a^{\prime})\right).$
(15)

To proceed and bound the RHS of the previous inequality, observe that that for
any policy $\pi$, $Q\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$, and $(s,a)$,
we have

$\displaystyle\lim_{\beta\rightarrow\infty}\frac{\pi(a|s)\exp{(\beta
Q(s,a))}}{\sum_{a^{\prime}\in\mathcal{A}}\pi(a^{\prime}|s)\exp(\beta
Q(s,a^{\prime}))}=\;$
$\displaystyle\lim_{\beta\rightarrow\infty}\frac{\pi(a|s)\exp{(\beta(Q(s,a)-Q_{s,\max}))}}{\sum_{a^{\prime}\in\mathcal{A}}\pi(a^{\prime}|s)\exp(\beta(Q(s,a^{\prime})-Q_{s,\max}))}$
$\displaystyle=\;$
$\displaystyle\begin{dcases}\frac{1}{|\\{a\in\mathcal{A}\mid
Q(s,a)=Q_{s,\max}\\}|},&Q(s,a)=Q_{s,\max},\\\
0,&Q(s,a)<Q_{s,\max},\end{dcases}$

where $Q_{s,\max}=\max_{a^{\prime}\in\mathcal{A}}Q(s,a)$, and hence

$\displaystyle\lim_{\beta\rightarrow\infty}\sum_{a^{\prime}\in\mathcal{A}}\frac{\pi_{t}(a^{\prime}|s^{\prime})\exp(\beta
Q_{t}(s^{\prime},a^{\prime}))}{\sum_{a^{\prime\prime}\in\mathcal{A}}\pi_{t}(a^{\prime\prime}|s^{\prime})\exp(\beta
Q_{t}(s^{\prime},a^{\prime\prime})}Q_{t}(s^{\prime},a^{\prime})=\max_{a^{\prime}\in\mathcal{A}}Q_{t}(s^{\prime},a^{\prime}),\quad\forall\;s^{\prime},t.$

Therefore, natural policy gradient is an approximate version of PI when
$\beta$ is large. To explicitly bound the difference between natural policy
gradient and PI for using a finite stepsize, the following lemma is needed,
the proof of which is presented in Appendix A.1.

######  Lemma 5.1.

Let $x\in\mathbb{R}^{d}$ be arbitrary and $y\in\Delta^{d}$ satisfying
$y_{i}>0$ for all $i$. Denote $i_{\max}=\arg\max_{1\leq i\leq d}x_{i}$. Then
we have $\max_{1\leq i\leq d}x_{i}-\frac{\sum_{i=1}^{d}x_{i}y_{i}e^{\beta
x_{i}}}{\sum_{j=1}^{d}y_{j}e^{\beta
x_{j}}}\leq\frac{1}{\beta}\log\left(\frac{1}{y_{i_{\max}}}\right)$ for any
$\beta>0$.

Using Lemma 5.1 to bound the RHS of Eq. (15) and we have

$\displaystyle 0$
$\displaystyle\leq[\mathcal{H}(Q_{t})](s,a)-[\mathcal{H}_{\pi_{t+1}}(Q_{t})](s,a)$
$\displaystyle=\gamma\sum_{s^{\prime}}P_{a}(s,s^{\prime})\left(\max_{a^{\prime}\in\mathcal{A}}Q_{t}(s^{\prime},a^{\prime})-\sum_{a^{\prime}\in\mathcal{A}}\frac{\pi_{t}(a^{\prime}|s^{\prime})\exp(\beta_{t}Q_{t}(s^{\prime},a^{\prime}))}{\sum_{a^{\prime\prime}\in\mathcal{A}}\pi_{t}(a^{\prime\prime}|s^{\prime})\exp(\beta_{t}Q_{t}(s^{\prime},a^{\prime\prime})}Q_{t}(s^{\prime},a^{\prime})\right)$
$\displaystyle\leq\gamma\sum_{s^{\prime}}P_{a}(s,s^{\prime})\left(\frac{1}{\beta_{t}}\log\left(\frac{1}{\pi_{t}(a_{t,s^{\prime}}\mid
s^{\prime})}\right)\right)$ $\displaystyle\leq\begin{dcases}\beta,&\text{Under
Condition \ref{condition:stepsize}},\\\ \gamma^{2t},&\text{Under Condition
\ref{condition:increasing_stepsize}}.\end{dcases}$

Therefore, under Condition 2.1, we have from Eq. (5.1.1) that

$\displaystyle\|Q^{*}-Q^{\pi_{T}}\|_{\infty}\leq\;$
$\displaystyle\gamma^{T}\|Q^{*}-Q^{\pi_{0}}\|_{\infty}\\!+\\!\frac{2\gamma}{1-\gamma}\sum_{t=0}^{T-1}\gamma^{T-1-t}\|Q^{\pi_{t}}-Q_{t}\|_{\infty}\\!+\\!\frac{2\gamma}{1-\gamma}\sum_{t=0}^{T-1}\gamma^{T-1-t}\beta$
$\displaystyle=\;$
$\displaystyle\gamma^{T}\|Q^{*}-Q^{\pi_{0}}\|_{\infty}\\!+\\!\frac{2\gamma}{1-\gamma}\sum_{t=0}^{T-1}\gamma^{T-1-t}\|Q^{\pi_{t}}-Q_{t}\|_{\infty}\\!+\\!\frac{2\gamma\beta}{(1-\gamma)^{2}}.$

Under Condition 2.2, we have from Eq. (5.1.1) that

$\displaystyle\|Q^{*}-Q^{\pi_{T}}\|_{\infty}\leq\;$
$\displaystyle\gamma^{T}\|Q^{*}-Q^{\pi_{0}}\|_{\infty}+\frac{2\gamma}{1-\gamma}\sum_{t=0}^{T-1}\gamma^{T-1-t}\|Q^{\pi_{t}}-Q_{t}\|_{\infty}+\frac{2\gamma}{1-\gamma}\sum_{t=0}^{T-1}\gamma^{T-1+t}$
$\displaystyle=\;$
$\displaystyle\gamma^{T}\|Q^{*}-Q^{\pi_{0}}\|_{\infty}+\frac{2\gamma}{1-\gamma}\sum_{t=0}^{T-1}\gamma^{T-1-t}\|Q^{\pi_{t}}-Q_{t}\|_{\infty}+\frac{2\gamma^{T}}{(1-\gamma)^{2}}.$

##### Boltzmann Softmax Update.

We next consider using Boltzmann softmax update for Algorithm 1 line 4. For
any $0\leq t\leq T-1$ and state-action pair $(s,a)$, we have from the update
rule that

$\displaystyle 0$
$\displaystyle\leq[\mathcal{H}(Q_{t})](s,a)-[\mathcal{H}_{\pi_{t+1}}(Q_{t})](s,a)$
$\displaystyle=\gamma\sum_{s^{\prime}}P_{a}(s,s^{\prime})\left(\max_{a^{\prime}\in\mathcal{A}}Q_{t}(s^{\prime},a^{\prime})-\sum_{a^{\prime}\in\mathcal{A}}\frac{\exp(\beta_{t}Q_{t}(s^{\prime},a^{\prime}))}{\sum_{a^{\prime\prime}\in\mathcal{A}}\exp(\beta_{t}Q_{t}(s^{\prime},a^{\prime\prime})}Q_{t}(s^{\prime},a^{\prime})\right)$
$\displaystyle=\gamma\sum_{s^{\prime}}P_{a}(s,s^{\prime})\left(\max_{a^{\prime}\in\mathcal{A}}Q_{t}(s^{\prime},a^{\prime})-\sum_{a^{\prime}\in\mathcal{A}}\frac{\exp(\beta_{t}Q_{t}(s^{\prime},a^{\prime}))/|\mathcal{A}|}{\sum_{a^{\prime\prime}\in\mathcal{A}}\exp(\beta_{t}Q_{t}(s^{\prime},a^{\prime\prime})/|\mathcal{A}|}Q_{t}(s^{\prime},a^{\prime})\right)$
$\displaystyle\leq\frac{\gamma}{\beta_{t}}\log(|\mathcal{A}|)$ (Lemma 5.1)
$\displaystyle\leq\begin{dcases}\beta,&\text{Under Condition
\ref{condition:stepsize}},\\\ \gamma^{2t},&\text{Under Condition
\ref{condition:increasing_stepsize}},\\\ \end{dcases}$

The result then follows from using the previous inequality in Eq. (5.1.1).

#####  $\epsilon$-Greedy Update.

Finally, we consider using $\epsilon$-greedy update in Algorithm 1 line 4. For
any $0\leq t\leq T-1$ and state-action pair $(s,a)$ that

$\displaystyle 0$
$\displaystyle\leq[\mathcal{H}(Q_{t})](s,a)-[\mathcal{H}_{\pi_{t+1}}(Q_{t})](s,a)$
$\displaystyle=\gamma\mathbb{E}\left[\max_{a^{\prime}\in\mathcal{A}}Q_{t}(S_{1},a^{\prime})-Q_{t}(S_{1},A_{1})\;\middle|\;S_{0}=s,A_{0}=a\right]$
($A_{1}\sim\pi_{t+1}(\cdot|S_{1})$)
$\displaystyle=\gamma\sum_{s^{\prime}}P_{a}(s,s^{\prime})\left(\left(\frac{1}{\beta(t,s^{\prime})}-\frac{1}{|\mathcal{A}|\beta(t,s^{\prime})}\right)Q_{t}(s^{\prime},a_{t,s^{\prime}})-\sum_{a^{\prime}\neq
a_{t,s^{\prime}}}\frac{1}{|\mathcal{A}|\beta(t,s^{\prime})}Q_{t}(s^{\prime},a^{\prime})\right)$
$\displaystyle\leq\gamma\sum_{s^{\prime}}P_{a}(s,s^{\prime})\frac{2}{\beta(t,s^{\prime})}\max_{a^{\prime}\in\mathcal{A}}|Q_{t}(s^{\prime},a^{\prime})|$
$\displaystyle\leq\begin{dcases}\beta,&\text{Under Condition
\ref{condition:stepsize}},\\\ \gamma^{2t},&\text{Under Condition
\ref{condition:increasing_stepsize}}.\end{dcases}$

The result follows from using the previous inequality in Eq. (5.1.1). The
proof of Theorem 2.1 is now complete.

### 5.2 Proof of Theorem 3.1 and Theorem 3.2

Instead of proving Theorems 3.1 and 3.2, we will state and prove finite-sample
bounds for Algorithm 3 with $c(\cdot,\cdot)$ and $\rho(\cdot,\cdot)$
satisfying Condition 3.1, which subsumes Theorems 3.1 and 3.2 as its special
cases. In this more general setup where we do not necessarily have
$c(\cdot,\cdot)=\rho(\cdot,\cdot)$, we define $L$ as

$\displaystyle
L=\begin{dcases}(1+(\gamma\rho_{\max})^{n}),&c(\cdot,\cdot)=\rho(\cdot,\cdot),\\\
(1+\gamma\rho_{\max})f_{n}(\gamma
c_{\max}),&c(\cdot,\cdot)\neq\rho(\cdot,\cdot),\end{dcases}$ (16)

where $c_{\max}=\max_{s,a}c(s,a)$ and $\rho_{\max}=\max_{s,a}\rho(s,a)$.
Moreover, in addition to using constant stepsize $\alpha_{k}\equiv\alpha$, we
also consider using diminishing stepsizes of the form
$\alpha_{k}=\frac{\alpha}{k+h}$, where $\alpha,h>0$. In this case, for
simplicity of notation, we write $t_{k}$ for $t_{\alpha_{k}}$, which is the
mixing time of the Markov chain $\\{S_{k}\\}$ (induced by $\pi_{b}$) with
precision $\alpha_{k}$.

######  Theorem 5.1.

Consider $\\{w_{k}\\}$ of Algorithm 3. Suppose that (1) Assumption 3.1 is
satisfied, (2) the generalized importance sampling factors satisfy Condition
3.1, (3) the parameter $n$ is chosen such that
$\gamma_{c}:=\tilde{\gamma}(n)/\sqrt{\mathcal{K}_{SA,\min}}<1$. Then, when
using constant stepsize $\alpha_{k}\equiv\alpha$, where $\alpha$ is chosen
such that
$\alpha(t_{\alpha}+n+1)\leq\frac{(1-\gamma_{c})\lambda_{\min}}{130L^{2}}$, we
have for all $k\geq t_{\alpha}+n+1$:

$\displaystyle\mathbb{E}[\|w_{k}-w_{c,\rho}^{\pi}\|_{2}^{2}]\leq
c_{1}(1-(1-\gamma_{c})\lambda_{\min}\alpha)^{k-(t_{\alpha}+n+1)}+c_{2}L^{2}\frac{\alpha(t_{\alpha}+n+1)}{(1-\gamma_{c})\lambda_{\min}},$
(17)

where $c_{1}=(\|w_{0}\|_{2}+\|w_{0}-w_{c,\rho}^{\pi}\|_{2}+1)^{2}$ and
$c_{2}=130(\|w_{c,\rho}^{\pi}\|_{2}+1)^{2}$. When using diminishing stepsizes
of the form $\alpha_{k}=\frac{\alpha}{k+h}$ with
$\alpha>\frac{1}{(1-\gamma_{c})\lambda_{\min}}$ and $h$ chosen such that
$\sum_{i=k-(t_{k}+n+1)}^{k-1}\alpha_{i}\leq\frac{(1-\gamma_{c})\lambda_{\min}}{130L^{2}}$
for all $k\geq t_{k}+n+1$, we have

$\displaystyle\mathbb{E}[\|w_{k}-w_{c,\rho}^{\pi}\|_{2}^{2}]\leq
c_{1}\frac{k_{0}+h}{k+h}+c_{2}\frac{8e\alpha^{2}}{(1-\gamma_{c})\lambda_{\min}\alpha-1}\frac{t_{k}+n+1}{k+h}$

for all $k\geq k_{0}$, where $k_{0}:=\min\\{k\;:\;k\geq t_{k}+n+1\\}$.

To prove Theorem 5.1, we first rewrite Algorithm 3 as a stochastic
approximation algorithm. Let $\\{X_{k}\\}$ be a finite-state Markov chain
defined as $X_{k}=(S_{k},A_{k},...,S_{k+n},A_{k+n})$ for any $k\geq 0$. Denote
the state-space of $\\{X_{k}\\}$ by $\mathcal{X}$. It is clear that under
Assumption 3.1, the Markov chain $\\{X_{k}\\}$ also admits a unique stationary
distribution, which we denote by $\nu\in\Delta^{|\mathcal{X}|}$. Let
$F:\mathbb{R}^{d}\times\mathcal{X}\mapsto\mathbb{R}^{d}$ be an operator
defined as

$\displaystyle
F(w,x)=\phi(s_{0},a_{0})\sum_{i=0}^{n-1}\gamma^{i}c_{1,i}\Delta_{i}(w)$

for any $w\in\mathbb{R}^{d}$ and
$x=(s_{0},a_{0},...,s_{n},a_{n})\in\mathcal{X}$. Let
$\bar{F}:\mathbb{R}^{d}\mapsto\mathbb{R}^{d}$ be the “expected” version of
$F(\cdot,\cdot)$ defined by $\bar{F}(w)=\mathbb{E}_{X\sim\nu}[F(w,X)]$. Using
the notation above, the update equation in line 4 of Algorithm 3 can be
compactly written as

$\displaystyle w_{k+1}$ $\displaystyle=w_{k}+\alpha_{k}F(w_{k},X_{k}),$ (18)

which is a stochastic approximation algorithm for solving the equation
$\bar{F}(w)=0$ with Markovian noise. Note that $\bar{F}(w)=0$ is equivalent to
the generalized PBE (5) (cf. Lemma 3.1). We next establish the properties of
the operators $F(\cdot,\cdot)$, $\bar{F}(\cdot)$, and the Markov chain
$\\{X_{k}\\}$ in the following proposition, which enables us to use standard
stochastic approximation results in the literature to derive finite-sample
bounds of Algorithm 3.

######  Proposition 5.1.

The following statements hold:

  1. (1)

$\|F(w_{1},x)-F(w_{2},x)\|_{2}\leq L\|w_{1}-w_{2}\|_{2}$ for any
$w_{1},w_{2}\in\mathbb{R}^{d}$ and $x\in\mathcal{X}$, and
$\|F(\bm{0},x)\|_{2}\leq f_{n}(\gamma c_{\max})$ for any $x\in\mathcal{X}$,

  2. (2)

$\max_{x\in\mathcal{X}}\left\|P_{X}^{k+n+1}(x,\cdot)-\nu(\cdot)\right\|_{\text{TV}}\leq
C\sigma^{k}$ for all $k\geq 0$, where $P_{X}$ is the transition probability
matrix of the Markov chain $\\{X_{k}\\}$,

  3. (3)

$(w-w_{c,\rho}^{\pi})^{\top}\bar{F}(w)\leq-(1-\gamma_{c})\lambda_{\min}\|w-w_{c,\rho}^{\pi}\|_{2}^{2}$
for any $w\in\mathbb{R}^{d}$.

###### Proof of Proposition 5.1.

  1. (1)

We first rewrite the operator $F(\cdot,\cdot)$ in the following equivalent
way. For any $w\in\mathbb{R}^{d}$ and
$x=(s_{0},a_{0},...,s_{n},a_{n})\in\mathcal{X}$, we have

$\displaystyle F(w,x)$ $\displaystyle=\;$
$\displaystyle\phi(s_{0},a_{0})\sum_{i=0}^{n-1}\gamma^{i}\prod_{j=1}^{i}c(s_{j},a_{j})(\mathcal{R}(s_{i},a_{i})\\!+\\!\gamma\rho(s_{i+1},a_{i+1})\phi(s_{i+1},a_{i+1})^{\top}w\\!-\\!\phi(s_{i},a_{i})^{\top}w)$
$\displaystyle=\;$
$\displaystyle\phi(s_{0},a_{0})\sum_{i=0}^{n-1}\gamma^{i}\prod_{j=1}^{i}c(s_{j},a_{j})\mathcal{R}(s_{i},a_{i})-\phi(s_{0},a_{0})\sum_{i=0}^{n-1}\gamma^{i}\prod_{j=1}^{i}c(s_{j},a_{j})\phi(s_{i},a_{i})^{\top}w$
$\displaystyle+\phi(s_{0},a_{0})\sum_{i=0}^{n-1}\gamma^{i+1}\prod_{j=1}^{i}c(s_{j},a_{j})\rho(s_{i+1},a_{i+1})\phi(s_{i+1},a_{i+1})^{\top}w$
$\displaystyle=\;$
$\displaystyle\phi(s_{0},a_{0})\sum_{i=0}^{n-1}\gamma^{i}\prod_{j=1}^{i}c(s_{j},a_{j})\mathcal{R}(s_{i},a_{i})-\phi(s_{0},a_{0})\sum_{i=0}^{n-1}\gamma^{i}\prod_{j=1}^{i}c(s_{j},a_{j})\phi(s_{i},a_{i})^{\top}w$
$\displaystyle+\phi(s_{0},a_{0})\sum_{i=1}^{n}\gamma^{i}\prod_{j=1}^{i-1}c(s_{j},a_{j})\rho(s_{i},a_{i})\phi(s_{i},a_{i})^{\top}w$
$\displaystyle=\;$
$\displaystyle\phi(s_{0},a_{0})\sum_{i=0}^{n-1}\gamma^{i}\prod_{j=1}^{i}c(s_{j},a_{j})\mathcal{R}(s_{i},a_{i})-\phi(s_{0},a_{0})\phi(s_{0},a_{0})^{\top}w$
$\displaystyle+\phi(s_{0},a_{0})\sum_{i=1}^{n-1}\gamma^{i}\prod_{j=1}^{i-1}c(s_{j},a_{j})(\rho(s_{i},a_{i})-c(s_{i},a_{i}))\phi(s_{i},a_{i})^{\top}w$
$\displaystyle+\phi(s_{0},a_{0})\gamma^{n}\prod_{j=1}^{n-1}c(s_{j},a_{j})\rho(s_{n},a_{n})\phi(s_{n},a_{n})^{\top}w.$

We now proceed and show the Lipschitz property. For any
$w_{1},w_{2}\in\mathbb{R}^{d}$ and
$x=(s_{0},a_{0},...,s_{n},a_{n})\in\mathcal{X}$, using the fact that
$\|\phi(s,a)\|_{2}\leq\|\phi(s,a)\|_{1}\leq\|\Phi\|_{\infty}\leq 1$, we have

$\displaystyle\|F(w_{1},x)-F(w_{2},x)\|_{2}$ $\displaystyle\leq\;$
$\displaystyle\|\phi(s_{0},a_{0})\phi(s_{0},a_{0})^{\top}(w_{1}-w_{2})\|_{2}$
$\displaystyle+\left\|\phi(s_{0},a_{0})\sum_{i=1}^{n-1}\gamma^{i}\prod_{j=1}^{i-1}c(s_{j},a_{j})(\rho(s_{i},a_{i})-c(s_{i},a_{i}))\phi(s_{i},a_{i})^{\top}(w_{1}-w_{2})\right\|_{2}$
$\displaystyle+\left\|\phi(s_{0},a_{0})\gamma^{n}\prod_{j=1}^{n-1}c(s_{j},a_{j})\rho(s_{n},a_{n})\phi(s_{n},a_{n})^{\top}(w_{1}-w_{2})\right\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\|w_{1}-w_{2}\|_{2}+\sum_{i=1}^{n-1}\gamma^{i}c_{\max}^{i-1}\max_{s,a}|\rho(s,a)-c(s,a)|\|w_{1}-w_{2}\|_{2}$
$\displaystyle+\gamma^{n}c_{\max}^{n-1}\rho_{\max}\|w_{1}-w_{2}\|_{2}$
$\displaystyle=\;$
$\displaystyle\left(1+\gamma\max_{s,a}|\rho(s,a)-c(s,a)|\frac{1-(\gamma
c_{\max})^{n-1}}{1-\gamma
c_{\max}}+\gamma^{n}c_{\max}^{n-1}\rho_{\max}\right)\|w_{1}-w_{2}\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\begin{dcases}(1+(\gamma\rho_{\max})^{n})\|w_{1}-w_{2}\|_{2},&c(\cdot,\cdot)=\rho(\cdot,\cdot)\\\
(1+\gamma\rho_{\max})f_{n}(\gamma
c_{\max})\|w_{1}-w_{2}\|_{2},&c(\cdot,\cdot)\neq\rho(\cdot,\cdot).\end{dcases}$

This proves that

$\displaystyle\|F(w_{1},x)-F(w_{2},x)\|_{2}\leq
L\|w_{1}-w_{2}\|_{2},\quad\forall\;w_{1},w_{2}\in\mathbb{R}^{d}.$

Similarly, for any $x=(s_{0},a_{0},...,s_{n},a_{n})\in\mathcal{X}$, we have

$\displaystyle\|F(\bm{0},x)\|_{2}$
$\displaystyle=\left\|\phi(s_{0},a_{0})\sum_{i=0}^{n-1}\gamma^{i}\prod_{j=1}^{i}c(s_{j},a_{j})\mathcal{R}(s_{i},a_{i})\right\|_{2}\leq\sum_{i=0}^{n-1}\gamma^{i}c_{\max}^{i}\leq
f_{n}(\gamma c_{\max}).$

  2. (2)

Under Assumption 3.1, it is clear that the stationary distribution $\nu$ of
the Markov chain $\\{X_{k}\\}$ is given by

$\displaystyle\nu(s_{0},a_{0},...,s_{n},a_{n})=\mu(s_{0})\left(\prod_{i=0}^{n-1}\pi_{b}(a_{i}|s_{i})P_{a_{i}}(s_{i},s_{i+1})\right)\pi_{b}(a_{n}|s_{n})$

for all $(s_{0},a_{0},...,s_{n},a_{n})\in\mathcal{X}$. Moreover, for any
$x=(s_{0},a_{0},...,s_{n},a_{n})\in\mathcal{X}$, we have for any $k\geq 0$
that

$\displaystyle\left\|P_{X}^{k+n+1}(x,\cdot)-\nu(\cdot)\right\|_{\text{TV}}=\;$
$\displaystyle\frac{1}{2}\sum_{s_{0}^{\prime},a_{0}^{\prime},\cdots,s_{n}^{\prime},a_{n}^{\prime}}\left|\sum_{s}P_{a_{n}}(s_{n},s)P^{k}_{\pi_{b}}(s,s_{0}^{\prime})-\mu(s_{0}^{\prime})\right|$
$\displaystyle\times\left[\prod_{i=0}^{n-1}\pi_{b}(a_{i}^{\prime}\mid
s_{i}^{\prime})P_{a_{i}^{\prime}}(s_{i}^{\prime},s_{i+1}^{\prime})\right]\pi_{b}(a_{n}^{\prime}\mid
s_{n}^{\prime})$ $\displaystyle=\;$
$\displaystyle\frac{1}{2}\sum_{s_{0}^{\prime}}\left|\sum_{s}P_{a_{n}}(s_{n},s)P^{k}_{\pi_{b}}(s,s_{0}^{\prime})-\mu(s_{0}^{\prime})\right|$
$\displaystyle\leq\;$
$\displaystyle\frac{1}{2}\sum_{s}P_{a_{n}}(s_{n},s)\sum_{s_{0}^{\prime}}\left|P^{k}_{\pi_{b}}(s,s_{0}^{\prime})-\mu(s_{0}^{\prime})\right|$
$\displaystyle\leq\;$
$\displaystyle\max_{s\in\mathcal{S}}\|P^{k}_{\pi_{b}}(s,\cdot)-\mu(\cdot)\|_{\text{TV}}$
$\displaystyle\leq\;$ $\displaystyle C\sigma^{k}.$

Since the RHS of the previous inequality does not depend on $x$, we in fact
have

$\displaystyle\max_{x\in\mathcal{X}}\left\|P^{k+n+1}_{X}(x,\cdot)-\nu(\cdot)\right\|_{\text{TV}}\leq
C\sigma^{k},\quad\forall\;k\geq 0.$

  3. (3)

Using the fact that $\mathcal{B}_{c,\rho}(\cdot)$ is a linear operator, we
have for any $w\in\mathbb{R}^{d}$ that

$\displaystyle(w-w_{c,\rho}^{\pi})^{\top}\bar{F}(w)$ $\displaystyle=\;$
$\displaystyle(w-w_{c,\rho}^{\pi})^{\top}\Phi^{\top}\mathcal{K}_{SA}\left(\mathcal{B}_{c,\rho}(\Phi
w)-\Phi w\right)$ $\displaystyle=\;$
$\displaystyle(w-w_{c,\rho}^{\pi})^{\top}\Phi^{\top}\mathcal{K}_{SA}\left(\mathcal{B}_{c,\rho}(\Phi
w)-\mathcal{B}_{c,\rho}(\Phi
w_{c,\rho}^{\pi})\right)-(w-w_{c,\rho}^{\pi})^{\top}\Phi^{\top}\mathcal{K}_{SA}\Phi(w-w_{c,\rho}^{\pi})$
$\displaystyle=\;$
$\displaystyle(w-w_{c,\rho}^{\pi})^{\top}\Phi^{\top}\mathcal{K}_{SA}\Phi(\Phi^{\top}\mathcal{K}_{SA}\Phi)^{-1}\Phi^{\top}\mathcal{K}_{SA}\mathcal{B}_{c,\rho}(\Phi(w-w_{c,\rho}^{\pi}))$
$\displaystyle-(w-w_{c,\rho}^{\pi})^{\top}\Phi^{\top}\mathcal{K}_{SA}\Phi(w-w_{c,\rho}^{\pi})$
$\displaystyle=\;$
$\displaystyle(w-w_{c,\rho}^{\pi})^{\top}\Phi^{\top}\mathcal{K}_{SA}\Phi(\Phi^{\top}\mathcal{K}_{SA}\Phi)^{-1}\Phi^{\top}\mathcal{K}_{SA}\mathcal{B}_{c,\rho}(\Phi(w-w_{c,\rho}^{\pi}))$
$\displaystyle-(w-w_{c,\rho}^{\pi})^{\top}\Phi^{\top}\mathcal{K}_{SA}\Phi(w-w_{c,\rho}^{\pi})$
$\displaystyle\leq\;$
$\displaystyle\|\Phi(w-w_{c,\rho}^{\pi})\|_{\mathcal{K}_{SA}}\|\Phi(\Phi^{\top}\mathcal{K}_{SA}\Phi)^{-1}\Phi^{\top}\mathcal{K}_{SA}\mathcal{B}_{c,\rho}(\Phi(w-w_{c,\rho}^{\pi}))\|_{\mathcal{K}_{SA}}$
$\displaystyle-\|\Phi(w-w_{c,\rho}^{\pi})\|_{\mathcal{K}_{SA}}^{2}$
$\displaystyle=\;$
$\displaystyle\|\Phi(w-w_{c,\rho}^{\pi})\|_{\mathcal{K}_{SA}}\|\text{Proj}_{\mathcal{Q}}\mathcal{B}_{c,\rho}(\Phi(w-w_{c,\rho}^{\pi}))\|_{\mathcal{K}_{SA}}-\|\Phi(w-w_{c,\rho}^{\pi})\|_{\mathcal{K}_{SA}}^{2}$
$\displaystyle\leq\;$
$\displaystyle\gamma_{c}\|\Phi(w-w_{c,\rho}^{\pi})\|_{\mathcal{K}_{SA}}\|\Phi(w-w_{c,\rho}^{\pi})\|_{\mathcal{K}_{SA}}-\|\Phi(w-w_{c,\rho}^{\pi})\|_{\mathcal{K}_{SA}}^{2}$
$\displaystyle=\;$
$\displaystyle-(1-\gamma_{c})\|\Phi(w-w_{c,\rho}^{\pi})\|_{\mathcal{K}_{SA}}^{2}$
$\displaystyle\leq\;$
$\displaystyle-(1-\gamma_{c})\lambda_{\min}\|w-w_{c,\rho}^{\pi}\|_{2}^{2}.$

∎

Proposition 5.1 (1) establishes the Lipschitz continuity of the operator
$F(\cdot,\cdot)$, Proposition 5.1 (2) establishes the geometric mixing of the
auxiliary Markov chain $\\{X_{k}\\}$, and Proposition 5.1 (3) essentially
guarantees that the ODE $\dot{x}(t)=\bar{F}(x(t))$ associated with stochastic
approximation algorithm (18) is globally geometrically stable. The rest of the
proof follows by applying Theorem 2.1 of [15] to Algorithm 3. In particular,
when using constant stepsize (i.e., $\alpha_{k}\equiv\alpha$) with $\alpha$
chosen such that
$\alpha(t_{\alpha}+n+1)\leq\frac{(1-\gamma_{c})\lambda_{\min}}{130L^{2}}$, we
have for all $k\geq t_{\alpha}+n+1$ that

$\displaystyle\mathbb{E}[\|w_{k}-w_{c,\rho}^{\pi}\|_{2}^{2}]\leq
c_{1}(1-(1-\gamma_{c})\lambda_{\min}\alpha)^{k-(t_{\alpha}+n+1)}+c_{2}\frac{\alpha
L^{2}(t_{\alpha}+n+1)}{(1-\gamma_{c})\lambda_{\min}},$

where $c_{1}=(\|w_{0}\|_{2}+\|w_{0}-w_{c,\rho}^{\pi}\|_{2}+1)^{2}$ and
$c_{2}=130(\|w_{c,\rho}^{\pi}\|_{2}+1)^{2}$.

When using diminishing stepsizes of the form $\alpha_{k}=\frac{\alpha}{k+h}$
with $\alpha>\frac{1}{(1-\gamma_{c})\lambda_{\min}}$ and $h$ chosen such that
$\sum_{i=k-(t_{k}+n+1)}^{k-1}\alpha_{i}\leq\frac{(1-\gamma_{c})\lambda_{\min}}{130L^{2}}$
for all $k\geq t_{k}+n+1$, we have

$\displaystyle\mathbb{E}[\|w_{k}-w_{c,\rho}^{\pi}\|_{2}^{2}]\leq
c_{1}\frac{k_{0}+h}{k+h}+c_{2}\frac{8e\alpha^{2}}{(1-\gamma_{c})\lambda_{\min}\alpha-1}\frac{t_{k}+n+1}{k+h}$

for all $k\geq k_{0}$, where $k_{0}=\min\\{k\;:\;k\geq t_{k}+n+1\\}$.

The finite-sample bounds of $\lambda$-averaged $Q$-trace and two-sided
$Q$-trace directly follow from Theorem 5.1. To show the performance guarantee
(i.e. Eqs. (8) and (3.2)) on the limit point $w_{c,\rho}^{\pi}$, we apply
Lemma 3.3. Note that when
$c(s,a)=\rho(s,a)=\lambda(s)\frac{\pi(a|s)}{\pi_{b}(a|s)}+1-\lambda(s)$ for
all $(s,a)$, we have for any $s\in\mathcal{S}$ that

$\displaystyle\sum_{a\in\mathcal{A}}|\pi(a|s)-\pi_{b}(a|s)\rho(s,a)|=\;$
$\displaystyle(1-\lambda(s))\sum_{a\in\mathcal{A}}|\pi(a|s)-\pi_{b}(a|s)|$
$\displaystyle=\;$
$\displaystyle(1-\lambda(s))\|\pi(\cdot|s)-\pi_{b}(\cdot|s)\|_{1}.$

When $c(s,a)=\rho(s,a)=g_{\ell(s),u(s)}(\pi(a|s)/\pi_{b}(a|s))$ for all
$(s,a)$, we have

$\displaystyle\sum_{a\in\mathcal{A}}|\pi(a|s)-\pi_{b}(a|s)\rho(s,a)|$
$\displaystyle\leq\;$
$\displaystyle\sum_{a\in\mathcal{A}}|(\pi(a|s)-\pi_{b}(a|s)\ell(s))\mathds{1}\\{\pi(a|s)<\ell(s)\pi_{b}(a|s)\\}|$
$\displaystyle+\sum_{a\in\mathcal{A}}|(\pi(a|s)-\pi_{b}(a|s)u(s))\mathds{1}\\{\pi(a|s)>u(s)\pi_{b}(a|s)\\}|$
$\displaystyle=\;$
$\displaystyle\sum_{a\in\mathcal{A}}\max(\pi(a|s)-\pi_{b}(a|s)u(s),0)-\min(\pi(a|s)-\pi_{b}(a|s)\ell(s),0)$
$\displaystyle=\;$
$\displaystyle\sum_{a\in\mathcal{A}}(u_{\pi,\pi_{b}}(s,a)-\ell_{\pi,\pi_{b}}(s,a)).$

This completes the proof.

### 5.3 Proof of Theorem 4.1

In view of Theorem 2.1, it remains to control the term $N_{2}$ using Theorem
5.1. Using triangle inequality and we have for any $0\leq t\leq T-1$:

$\displaystyle\mathbb{E}[\|Q^{\pi_{t}}-\Phi w_{t}\|_{\infty}]$ (19)
$\displaystyle\leq\;$ $\displaystyle\mathbb{E}[\|Q^{\pi_{t}}-\Phi
w_{c,\rho}^{\pi_{t}}\|_{\infty}]+\mathbb{E}[\|\Phi(w_{c,\rho}^{\pi_{t}}-w_{t})\|_{\infty}]$
$\displaystyle\leq\;$ $\displaystyle\mathbb{E}[\|Q^{\pi_{t}}-\Phi
w_{c,\rho}^{\pi_{t}}\|_{\infty}]+\|\Phi\|_{\infty}\mathbb{E}[\|w_{c,\rho}^{\pi_{t}}-w_{t}\|_{\infty}]$
$\displaystyle\leq\;$ $\displaystyle\mathbb{E}[\|Q^{\pi_{t}}-\Phi
w_{c,\rho}^{\pi_{t}}\|_{\infty}]+\mathbb{E}[\|w_{c,\rho}^{\pi_{t}}-w_{t}\|_{\infty}]$
($\|\Phi\|_{\infty}\leq 1$) $\displaystyle\leq\;$
$\displaystyle\mathbb{E}[\|Q_{c,\rho}^{\pi_{t}}-\Phi
w_{c,\rho}^{\pi_{t}}\|_{\infty}]+\mathbb{E}[\|Q_{c,\rho}^{\pi_{t}}-Q^{\pi_{t}}\|_{\infty}]+\mathbb{E}[\|w_{c,\rho}^{\pi_{t}}-w_{t}\|_{\infty}]$
$\displaystyle\leq\;$
$\displaystyle\mathcal{E}_{\text{approx}}+\frac{\gamma}{(1-\gamma)^{2}}\max_{s\in\mathcal{S}}(1-\lambda(s))\|\pi_{t}(\cdot|s)-\pi_{b}(\cdot|s)\|_{1}+\mathbb{E}[\|w_{c,\rho}^{\pi_{t}}-w_{t}\|_{\infty}]$
(Apply Eq. (26)) $\displaystyle\leq\;$
$\displaystyle\mathcal{E}_{\text{approx}}+\frac{\gamma}{(1-\gamma)^{2}}\mathcal{E}_{\text{bias}}+\mathbb{E}[\|w_{c,\rho}^{\pi_{t}}-w_{t}\|_{\infty}].$
(20)

To control $\mathbb{E}[\|w_{c,\rho}^{\pi_{t}}-w_{t}\|_{\infty}]$, using
Theorem 3.1 and we have for all $t=0,\cdots,T-1$ that

$\displaystyle\mathbb{E}[\|w_{c,\rho}^{\pi_{t}}-w_{t}\|_{\infty}]\leq\;$
$\displaystyle\mathbb{E}[\|w_{c,\rho}^{\pi_{t}}-w_{t}\|_{2}]$
$\displaystyle\leq\;$
$\displaystyle(\mathbb{E}[\|w_{c,\rho}^{\pi_{t}}-w_{t}\|_{2}^{2}])^{1/2}$
(Jensen’s Inequality) $\displaystyle\leq\;$ $\displaystyle
c_{1,i}(1-(1-\gamma_{c})\lambda_{\min}\alpha)^{\frac{1}{2}[K-(t_{\alpha}+n+1)]}+c_{2,i}\frac{[\alpha(t_{\alpha}+n+1)]^{1/2}}{\sqrt{1-\gamma_{c}}\sqrt{\lambda_{\min}}},$

where $c_{1,t}=\|w^{\pi_{t}}_{c,\rho}\|_{2}+1$ and
$c_{2,t}=11.5L(\|w_{c,\rho}^{\pi_{t}}\|_{2}+1)$. Note that the last line of
the previous inequality follows from $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for any
$a,b\geq 0$. To further control the constants $c_{1,t}$ and $c_{2,t}$, note
that we have for any policy $\pi$ that

$\displaystyle\|w_{c,\rho}^{\pi}\|_{2}$
$\displaystyle\leq\frac{1}{\sqrt{\lambda_{\min}}}\|\Phi
w_{c,\rho}^{\pi}\|_{\mathcal{K}_{SA}}$
$\displaystyle\leq\frac{1}{\sqrt{\lambda_{\min}}}\left(\|Q_{c,\rho}^{\pi}\|_{\mathcal{K}_{SA}}+\frac{1}{\sqrt{1-\gamma_{c}^{2}}(1-\gamma)}\right)$
(Eq. (27))
$\displaystyle\leq\frac{1}{\sqrt{\lambda_{\min}}}\left(\frac{1}{1-\gamma}+\frac{1}{\sqrt{1-\gamma_{c}^{2}}(1-\gamma)}\right)$
$\displaystyle\leq\frac{2}{\sqrt{\lambda_{\min}}(1-\gamma)\sqrt{1-\gamma_{c}}}.$

Therefore we have
$c_{1,t}\leq\frac{3}{\sqrt{\lambda_{\min}}(1-\gamma)\sqrt{1-\gamma_{c}}}$ and
$c_{2,t}\leq\frac{35L}{\sqrt{\lambda_{\min}}(1-\gamma)\sqrt{1-\gamma_{c}}}$
for any $0\leq t\leq T-1$. Substituting the upper bound we obtained for
$\mathbb{E}[\|w_{c,\rho}^{\pi_{t}}-w_{t}\|_{\infty}]$ into Eq. (20) and we
have for any $0\leq i\leq T-1$:

$\displaystyle\mathbb{E}[\|Q^{\pi_{t}}-\Phi w_{t}\|_{\infty}]\leq\;$
$\displaystyle\mathcal{E}_{\text{approx}}+\frac{\gamma\mathcal{E}_{\text{bias}}}{(1-\gamma)^{2}}+\frac{3(1-(1-\gamma_{c})\lambda_{\min}\alpha)^{\frac{1}{2}[K-(t_{\alpha}+n+1)]}}{\sqrt{\lambda_{\min}}(1-\gamma)\sqrt{1-\gamma_{c}}}$
$\displaystyle+\frac{35L[\alpha(t_{\alpha}+n+1)]^{1/2}}{(1-\gamma)(1-\gamma_{c})\lambda_{\min}}.$

Finally, using the previous inequality and we obtain the following bound on
the term $N_{2}$ in Theorem 2.1:

$\displaystyle N_{2}=\;$
$\displaystyle\frac{2\gamma}{1-\gamma}\sum_{t=0}^{T-1}\gamma^{T-1-t}\mathbb{E}[\|Q^{\pi_{t}}-\Phi
w_{t}\|_{\infty}]$ $\displaystyle\leq\;$
$\displaystyle\frac{2\gamma\mathcal{E}_{\text{approx}}}{(1-\gamma)^{2}}+\frac{2\gamma^{2}\mathcal{E}_{\text{bias}}}{(1-\gamma)^{4}}+\frac{6(1-(1-\gamma_{c})\lambda_{\min}\alpha)^{\frac{1}{2}[K-(t_{\alpha}+n+1)]}}{(1-\gamma)^{3}(1-\gamma_{c})^{1/2}\lambda_{\min}^{1/2}}$
$\displaystyle+\frac{70L[\alpha(t_{\alpha}+n+1)]^{1/2}}{\lambda_{\min}(1-\gamma_{c})(1-\gamma)^{3}}.$

The rest of the proof follows by using the upper bound we obtained for the
term $N_{2}$ in Theorem 2.1.

## 6 Conclusion

In this work, we study finite-sample guarantees of general policy-based
algorithms (especially natural policy gradient) under off-policy sampling and
linear function approximation. By viewing natural policy gradient as an
approximate version of PI, we establish its geometric convergence without
requiring any regularization. As for the critic, to overcome the deadly triad
and the high variance in off-policy learning, we design a convergent framework
of single time-scale TD-learning algorithms, including two specific algorithms
called $\lambda$-averaged $Q$-trace and two-sided $Q$-trace. After combining
the actor and the critic, we obtain an overall sample complexity bound of
$\tilde{\mathcal{O}}(\epsilon^{-2})$.

## References

  * Agarwal et al., [2021] Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G. (2021).  On the theory of policy gradient methods: Optimality, approximation, and distribution shift.  Journal of Machine Learning Research, 22(98):1–76.
  * Baxter and Bartlett, [2001] Baxter, J. and Bartlett, P. L. (2001).  Infinite-horizon policy-gradient estimation.  Journal of Artificial Intelligence Research, 15:319–350.
  * Bertsekas, [2011] Bertsekas, D. P. (2011).  Approximate policy iteration: A survey and some new methods.  Journal of Control Theory and Applications, 9(3):310–335.
  * Bertsekas and Tsitsiklis, [1996] Bertsekas, D. P. and Tsitsiklis, J. N. (1996).  Neuro-dynamic programming.  Athena Scientific.
  * Bertsekas and Yu, [2009] Bertsekas, D. P. and Yu, H. (2009).  Projected equation methods for approximate solution of large linear systems.  Journal of Computational and Applied Mathematics, 227(1):27–50.
  * Bhandari et al., [2018] Bhandari, J., Russo, D., and Singal, R. (2018).  A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation.  In Conference On Learning Theory, pages 1691–1692.
  * Bhatnagar et al., [2009] Bhatnagar, S., Sutton, R. S., Ghavamzadeh, M., and Lee, M. (2009).  Natural actor–critic algorithms.  Automatica, 45(11):2471–2482.
  * Borkar, [2009] Borkar, V. S. (2009).  Stochastic approximation: a dynamical systems viewpoint, volume 48.  Springer.
  * Borkar and Konda, [1997] Borkar, V. S. and Konda, V. R. (1997).  The actor-critic algorithm as multi-time-scale stochastic approximation.  Sadhana, 22(4):525–543.
  * Cayci et al., [2021] Cayci, S., He, N., and Srikant, R. (2021).  Linear convergence of entropy-regularized natural policy gradient with linear function approximation.  Preprint arXiv:2106.04096.
  * Cen et al., [2021] Cen, S., Cheng, C., Chen, Y., Wei, Y., and Chi, Y. (2021).  Fast global convergence of natural policy gradient methods with entropy regularization.  Operations Research.
  * [12] Chen, Z., Khodadadian, S., and Maguluri, S. T. (2022a).  Finite-Sample Analysis of Off-Policy Natural Actor–Critic With Linear Function Approximation.  IEEE Control Systems Letters, 6:2611–2616.
  * [13] Chen, Z., Maguluri, S. T., Shakkottai, S., and Shanmugam, K. (2021a).  A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous $Q$-Learning and TD-Learning Variants.  Preprint arXiv:2102.01567.
  * [14] Chen, Z., Maguluri, S. T., Shakkottai, S., and Shanmugam, K. (2021b).  Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman Operators.  Advances in Neural Information Processing Systems, 34.
  * [15] Chen, Z., Zhang, S., Doan, T. T., Clarke, J.-P., and Maguluri, S. T. (2022b).  Finite-sample analysis of nonlinear stochastic approximation with applications in reinforcement learning.  Automatica, 146:110623.
  * Dayan and Sejnowski, [1994] Dayan, P. and Sejnowski, T. J. (1994).  TD($\lambda$) converges with probability $1$.  Machine Learning, 14(3):295–301.
  * Degrave et al., [2022] Degrave, J., Felici, F., Buchli, J., Neunert, M., Tracey, B., Carpanese, F., Ewalds, T., Hafner, R., Abdolmaleki, A., de Las Casas, D., et al. (2022).  Magnetic control of tokamak plasmas through deep reinforcement learning.  Nature, 602(7897):414–419.
  * Dimitrakakis and Lagoudakis, [2008] Dimitrakakis, C. and Lagoudakis, M. G. (2008).  Rollout sampling approximate policy iteration.  Machine Learning, 72(3):157–171.
  * Espeholt et al., [2018] Espeholt, L., Soyer, H., Munos, R., Simonyan, K., Mnih, V., Ward, T., Doron, Y., Firoiu, V., Harley, T., Dunning, I., et al. (2018).  IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures.  In International Conference on Machine Learning, pages 1407–1416.
  * Harutyunyan et al., [2016] Harutyunyan, A., Bellemare, M. G., Stepleton, T., and Munos, R. (2016).  $Q(\lambda)$ with Off-Policy Corrections.  In International Conference on Algorithmic Learning Theory, pages 305–320. Springer.
  * Kakade, [2001] Kakade, S. M. (2001).  A natural policy gradient.  Advances in neural information processing systems, 14.
  * Khodadadian et al., [2021] Khodadadian, S., Chen, Z., and Maguluri, S. T. (2021).  Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm.  The 38th International Conference on Machine Learning, 139:5420–5431.
  * [23] Khodadadian, S., Doan, T. T., Romberg, J., and Maguluri, S. T. (2022a).  Finite sample analysis of two-time-scale natural actor-critic algorithm.  IEEE Transactions on Automatic Control.
  * [24] Khodadadian, S., Jhunjhunwala, P. R., Varma, S. M., and Maguluri, S. T. (2022b).  On linear and super-linear convergence of natural policy gradient algorithm.  Systems & Control Letters, 164:105214.
  * Konda and Tsitsiklis, [2000] Konda, V. R. and Tsitsiklis, J. N. (2000).  Actor-critic algorithms.  In Advances in neural information processing systems, pages 1008–1014. Citeseer.
  * Kumar et al., [2019] Kumar, H., Koppel, A., and Ribeiro, A. (2019).  On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximation.  Preprint arXiv:1910.08412.
  * Lagoudakis and Parr, [2003] Lagoudakis, M. G. and Parr, R. (2003).  Least-squares policy iteration.  The Journal of Machine Learning Research, 4:1107–1149.
  * Lan, [2021] Lan, G. (2021).  Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes.  Mathematical programming.
  * Lazaric et al., [2012] Lazaric, A., Ghavamzadeh, M., and Munos, R. (2012).  Finite-sample analysis of least-squares policy iteration.  Journal of Machine Learning Research, 13:3041–3074.
  * Levin and Peres, [2017] Levin, D. A. and Peres, Y. (2017).  Markov chains and mixing times, volume 107.  American Mathematical Soc.
  * Li et al., [2020] Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2020).  Sample complexity of asynchronous $Q$-learning: Sharper analysis and variance reduction.  Advances in neural information processing systems, 33:7031–7043.
  * Liu et al., [2019] Liu, B., Cai, Q., Yang, Z., and Wang, Z. (2019).  Neural proximal/trust region policy optimization attains globally optimal policy.  Advances in Neural Information Processing Systems, 32.
  * Liu et al., [2020] Liu, Y., Zhang, K., Basar, T., and Yin, W. (2020).  An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods.  Advances in Neural Information Processing Systems, 33.
  * Ma et al., [2020] Ma, S., Zhou, Y., and Zou, S. (2020).  Variance-reduced off-policy TDC learning: Non-asymptotic convergence analysis.  Advances in Neural Information Processing Systems, 33:14796–14806.
  * Mirowski et al., [2018] Mirowski, P., Grimes, M., Malinowski, M., Hermann, K. M., Anderson, K., Teplyashin, D., Simonyan, K., Zisserman, A., Hadsell, R., et al. (2018).  Learning to navigate in cities without a map.  In Advances in Neural Information Processing Systems, pages 2419–2430.
  * Munos, [2003] Munos, R. (2003).  Error bounds for approximate policy iteration.  In ICML, volume 3, pages 560–567.
  * Munos et al., [2016] Munos, R., Stepleton, T., Harutyunyan, A., and Bellemare, M. G. (2016).  Safe and efficient off-policy reinforcement learning.  In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 1054–1062.
  * Perkins and Precup, [2002] Perkins, T. and Precup, D. (2002).  A convergent form of approximate policy iteration.  Advances in neural information processing systems, 15.
  * Powell and Ma, [2011] Powell, W. B. and Ma, J. (2011).  A review of stochastic algorithms with continuous value function approximation and some new approximate policy iteration algorithms for multidimensional continuous applications.  Journal of Control Theory and Applications, 9(3):336–352.
  * Puterman, [1995] Puterman, M. L. (1995).  Markov decision processes: Discrete stochastic dynamic programming.  Journal of the Operational Research Society, 46(6):792–792.
  * Qiu et al., [2021] Qiu, S., Yang, Z., Ye, J., and Wang, Z. (2021).  On finite-time convergence of actor-critic algorithm.  IEEE Journal on Selected Areas in Information Theory, 2(2):652–664.
  * Qu and Wierman, [2020] Qu, G. and Wierman, A. (2020).  Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning.  In Conference on Learning Theory, pages 3185–3205. PMLR.
  * Scherrer, [2014] Scherrer, B. (2014).  Approximate policy iteration schemes: a comparison.  In International Conference on Machine Learning, pages 1314–1322. PMLR.
  * Silver et al., [2016] Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. (2016).  Mastering the game of go with deep neural networks and tree search.  nature, 529(7587):484.
  * Srikant and Ying, [2019] Srikant, R. and Ying, L. (2019).  Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning.  In Conference on Learning Theory, pages 2803–2830.
  * Sutton, [1988] Sutton, R. S. (1988).  Learning to predict by the methods of temporal differences.  Machine learning, 3(1):9–44.
  * Sutton and Barto, [2018] Sutton, R. S. and Barto, A. G. (2018).  Reinforcement learning: An introduction.  MIT press.
  * Sutton et al., [2009] Sutton, R. S., Maei, H. R., Precup, D., Bhatnagar, S., Silver, D., Szepesvári, C., and Wiewiora, E. (2009).  Fast gradient-descent methods for temporal-difference learning with linear function approximation.  In Proceedings of the 26th Annual International Conference on Machine Learning, pages 993–1000.
  * Sutton et al., [2016] Sutton, R. S., Mahmood, A. R., and White, M. (2016).  An emphatic approach to the problem of off-policy temporal-difference learning.  The Journal of Machine Learning Research, 17(1):2603–2631.
  * Sutton et al., [1999] Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y. (1999).  Policy gradient methods for reinforcement learning with function approximation.  In Proceedings of the 12th International Conference on Neural Information Processing Systems, pages 1057–1063.
  * Sutton et al., [2008] Sutton, R. S., Szepesvári, C., and Maei, H. R. (2008).  A convergent $\mathcal{O}(n)$ algorithm for off-policy temporal-difference learning with linear function approximation.  Advances in neural information processing systems, 21(21):1609–1616.
  * Tsitsiklis, [1994] Tsitsiklis, J. N. (1994).  Asynchronous stochastic approximation and $Q$-learning.  Machine learning, 16(3):185–202.
  * Tsitsiklis and Van Roy, [1997] Tsitsiklis, J. N. and Van Roy, B. (1997).  An analysis of temporal-difference learning with function approximation.  IEEE transactions on automatic control, 42(5):674–690.
  * Wang et al., [2019] Wang, L., Cai, Q., Yang, Z., and Wang, Z. (2019).  Neural Policy Gradient Methods: Global Optimality and Rates of Convergence.  In International Conference on Learning Representations.
  * Wang et al., [2021] Wang, Y., Zou, S., and Zhou, Y. (2021).  Finite-Sample Analysis for Two Time-scale Non-linear TDC with General Smooth Function Approximation.  Advances in Neural Information Processing Systems, 34.
  * Watkins and Dayan, [1992] Watkins, C. J. and Dayan, P. (1992).  $Q$-learning.  Machine learning, 8(3-4):279–292.
  * Williams and Baird, [1990] Williams, R. J. and Baird, L. 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, pages 96–101. Citeseer.
  * Wu et al., [2020] Wu, Y. F., Zhang, W., Xu, P., and Gu, Q. (2020).  A finite-time analysis of two time-scale actor-critic methods.  Advances in Neural Information Processing Systems, 33:17617–17628.
  * Xiao, [2022] Xiao, L. (2022).  On the convergence rates of policy gradient methods.  Preprint arXiv:2201.07443.
  * Xu et al., [2020] Xu, T., Wang, Z., and Liang, Y. (2020).  Improving sample complexity bounds for (natural) actor-critic algorithms.  Advances in Neural Information Processing Systems, 33.
  * [61] Zhang, K., Koppel, A., Zhu, H., and Başar, T. (2019a).  Convergence and iteration complexity of policy gradient method for infinite-horizon reinforcement learning.  In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 7415–7422. IEEE.
  * [62] Zhang, Z., Zhang, D., and Qiu, R. C. (2019b).  Deep reinforcement learning for power system applications: An overview.  CSEE Journal of Power and Energy Systems, 6(1):213–225.

Appendices

##  Appendix A Proof of All Technical Lemmas

### A.1 Proof of Lemma 5.1

For any $\beta>0$, consider the function
$h_{\beta}:\mathbb{R}^{d}\mapsto\mathbb{R}$ defined by

$\displaystyle
h_{\beta}(x)=\frac{1}{\beta}\log\left(\sum_{i=1}^{d}y_{i}e^{\beta
x_{i}}\right).$

Assume without loss of generality that $i_{\max}=1$. Then it is clear that
$h_{\beta}(x)\leq x_{1}$. On the other hand, we have

$\displaystyle
x_{1}\leq\frac{1}{\beta}\log\left(\sum_{i=1}^{d}\frac{y_{i}}{y_{1}}e^{\beta
x_{i}}\right)=h_{\beta}(x)+\frac{1}{\beta}\log\left(\frac{1}{y_{1}}\right).$
(21)

Since it is well-known that $h_{\beta}(x)$ is a convex differentiable
function, we have for any $x\in\mathbb{R}^{d}$ that
$h_{\beta}(\bm{0})-h_{\beta}(x)\geq\langle\nabla h_{\beta}(x),-x\rangle$,
which implies

$\displaystyle\langle\nabla
h_{\beta}(x),x\rangle=\frac{\sum_{i=1}^{d}x_{i}y_{i}e^{\beta
x_{i}}}{\sum_{j=1}^{d}y_{j}e^{\beta x_{j}}}\geq
h_{\beta}(x)-h_{\beta}(0)=h_{\beta}(x).$ (22)

Using Eqs. (21) and (22) and we finally obtain

$\displaystyle\max_{1\leq i\leq d}x_{i}-\frac{\sum_{i=1}^{d}x_{i}y_{i}e^{\beta
x_{i}}}{\sum_{j=1}^{d}y_{j}e^{\beta x_{j}}}\leq
x_{1}-h_{\beta}(x)\leq\frac{1}{\beta}\log\left(\frac{1}{y_{1}}\right).$

### A.2 Proof of Lemma 3.1

We begin by introducing some notation. Let $\pi_{c}$ and $\pi_{\rho}$ be two
policies defined by

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

Let $P_{\pi_{c}}$ and $P_{\pi_{\rho}}$ be the transition probability matrices
of the Markov chain $\\{S_{k}\\}$ induced by the policies $\pi_{c}$ and
$\pi_{\rho}$, respectively. Then, Eq. (4) can be compactly written in vector
form as

$\displaystyle\Phi^{\top}\mathcal{K}_{SA}\sum_{i=0}^{n-1}(\gamma
P_{\pi_{c}}D_{c})^{i}(R+\gamma P_{\pi_{\rho}}D_{\rho}\Phi w-\Phi w)=0,$

where $R\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$ is defined by
$R(s,a)=\mathcal{R}(s,a)$ for all $(s,a)$. Observe that the above equation is
further equivalent to

$\displaystyle\Phi(\Phi^{\top}\mathcal{K}_{SA}\Phi)^{-1}\Phi^{\top}\mathcal{K}_{SA}\sum_{i=0}^{n-1}(\gamma
P_{\pi_{c}}D_{c})^{i}(R+\gamma P_{\pi_{\rho}}D_{\rho}\Phi w-\Phi w)=0.$ (23)

To see this, note that the matrix $\Phi$ has full column-rank, and the matrix
$\Phi^{\top}\mathcal{K}_{SA}\Phi$ is positive definite and hence invertible.
Therefore, we have $x=\bm{0}$ if and only if
$\Phi(\Phi^{\top}\mathcal{K}_{SA}\Phi)^{-1}x=\bm{0}$. To rewrite Eq. (23) in
the desired form of the generalized PBE (5), we use the following three
observations.

  1. (1)

The projection operator $\text{Proj}_{\mathcal{Q}}(\cdot)$ is explicitly given
by
$\text{Proj}_{\mathcal{Q}}(\cdot)=\Phi(\Phi^{\top}\mathcal{K}_{SA}\Phi)^{-1}\Phi^{\top}\mathcal{K}_{SA}(\cdot)$.

  2. (2)

The operator $\mathcal{T}_{c}(\cdot)$ is explicitly given by
$\mathcal{T}_{c}(\cdot)=\sum_{i=0}^{n-1}(\gamma P_{\pi_{c}}D_{c})^{i}(\cdot)$.

  3. (3)

The operator $\mathcal{H}_{\rho}(\cdot)$ is explicitly given by
$\mathcal{H}_{\rho}(\cdot)=R+\gamma P_{\pi_{\rho}}D_{\rho}(\cdot)$.

Therefore, Eq. (23) is equivalent to

$\displaystyle\text{Proj}_{\mathcal{Q}}[\mathcal{T}_{c}(\mathcal{H}_{\rho}(\Phi
w)-\Phi w)]=0.$ (24)

Finally, adding and subtracting $\Phi w$ on both sides of the previous
inequality and we obtain the desired generalized PBE:

$\displaystyle\Phi w$
$\displaystyle=\text{Proj}_{\mathcal{Q}}[\mathcal{T}_{c}(\mathcal{H}_{\rho}(\Phi
w)-\Phi w)]+\Phi w$
$\displaystyle=\text{Proj}_{\mathcal{Q}}[\mathcal{T}_{c}(\mathcal{H}_{\rho}(\Phi
w)-\Phi w)+\Phi w]$
$\displaystyle=\text{Proj}_{\mathcal{Q}}\mathcal{B}_{c,\rho}(\Phi w),$

where the second equality follows from (1) $\Phi w\in\mathcal{Q}$ and (2)
$\text{Proj}_{\mathcal{Q}}(\cdot)$ is a linear operator.

### A.3 Proof of Lemma 3.2

For any $Q_{1},Q_{2}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$, using the
fact that $\text{Proj}_{\mathcal{Q}}$ is non-expansive with respect to
$\|\cdot\|_{\mathcal{K}_{SA}}$, we have

$\displaystyle\|\text{Proj}_{\mathcal{Q}}\mathcal{B}_{c,\rho}(Q_{1})-\text{Proj}_{\mathcal{Q}}\mathcal{B}_{c,\rho}(Q_{2})\|_{\mathcal{K}_{SA}}\leq\;$
$\displaystyle\|\mathcal{B}_{c,\rho}(Q_{1})-\mathcal{B}_{c,\rho}(Q_{2})\|_{\mathcal{K}_{SA}}$
$\displaystyle\leq\;$
$\displaystyle\|\mathcal{B}_{c,\rho}(Q_{1})-\mathcal{B}_{c,\rho}(Q_{2})\|_{\infty}$
($\|\cdot\|_{\mathcal{K}_{SA}}\leq\|\cdot\|_{\infty}$) $\displaystyle\leq\;$
$\displaystyle\tilde{\gamma}(n)\|Q_{1}-Q_{2}\|_{\infty}$ $\displaystyle\leq\;$
$\displaystyle\frac{\tilde{\gamma}(n)}{\sqrt{\mathcal{K}_{SA,\min}}}\|Q_{1}-Q_{2}\|_{\mathcal{K}_{SA}},$
($\|\cdot\|_{\infty}\leq\frac{1}{\sqrt{\mathcal{K}_{SA,\min}}}\|\cdot\|_{\mathcal{K}_{SA}}$)

where the third inequality follows from $\mathcal{B}_{c,\rho}(\cdot)$ being a
$\tilde{\gamma}(n)$-contraction operator with respect to $\|\cdot\|_{\infty}$
[14] 333[14] works with an asynchronous variant of the generalized Bellman
operator, which is shown to be a contraction mapping with respect to
$\|\cdot\|_{\infty}$ with contraction factor
$1-\mathcal{K}_{SA,\min}f_{n}(\gamma D_{c,\min})(1-\gamma D_{\rho,\max})$. In
this paper we work with the synchronous generalized Bellman operator
$\mathcal{B}_{c,\rho}(\cdot)$. In this case, one can easily verify that the
corresponding contraction factor can be obtained by simply dropping the factor
$\mathcal{K}_{SA,\min}$..

### A.4 Proof of Lemma 3.3

We first show that under Condition 3.1 (3), we have
$\lim_{n\rightarrow\infty}\tilde{\gamma}(n)/\sqrt{\mathcal{K}_{SA,\min}}<1$.
Using the explicit expression of $\tilde{\gamma}(n)$, we have

$\displaystyle\lim_{n\rightarrow\infty}\frac{\tilde{\gamma}(n)}{\sqrt{\mathcal{K}_{SA,\min}}}$
$\displaystyle=\lim_{n\rightarrow\infty}\frac{1-f_{n}(\gamma
D_{c,\min})(1-\gamma D_{\rho,\max})}{\sqrt{\mathcal{K}_{SA,\min}}}$
$\displaystyle=\lim_{n\rightarrow\infty}\frac{1-\frac{1-(\gamma
D_{c,\min})^{n}}{1-\gamma D_{c,\min}}(1-\gamma
D_{\rho,\max})}{\sqrt{\mathcal{K}_{SA,\min}}}$
($f_{n}(x)=\sum_{i=0}^{n-1}x^{i}$ and $\gamma D_{c,\min}<1$)
$\displaystyle=\frac{\gamma(D_{\rho,\max}-D_{c,\min})}{(1-\gamma
D_{c,\min})\sqrt{\mathcal{K}_{SA,\min}}}$ $\displaystyle<1.$ (Condition 3.1
(3))

Therefore, when $n$ is chosen such that
$\gamma_{c}=\frac{\tilde{\gamma}(n)}{\sqrt{\mathcal{K}_{SA,\min}}}<1$, we have
by Lemma 3.2 that

$\displaystyle\|\text{Proj}_{\mathcal{Q}}\mathcal{B}_{c,\rho}(Q_{1})-\text{Proj}_{\mathcal{Q}}\leq\gamma_{c}\|Q_{1}-Q_{2}\|_{\mathcal{K}_{SA}},\quad\forall\;Q_{1},Q_{2}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}.$

It follows that the composed operator
$\text{Proj}_{\mathcal{Q}}\mathcal{B}_{c,\rho}(\cdot)$ is a contraction
mapping with respect to $\|\cdot\|_{\mathcal{K}_{SA}}$, with contraction
factor $\gamma_{c}$.

Next consider the difference between $Q^{\pi}$ and $\Phi w_{c,\rho}^{\pi}$.
First of all, we have by triangle inequality that

$\displaystyle\|Q^{\pi}-\Phi w_{c,\rho}^{\pi}\|_{\mathcal{K}_{SA}}$
$\displaystyle=\|Q^{\pi}-Q_{c,\rho}^{\pi}+Q_{c,\rho}^{\pi}-\Phi
w_{c,\rho}^{\pi}\|_{\mathcal{K}_{SA}}$
$\displaystyle\leq\|Q^{\pi}-Q_{c,\rho}^{\pi}\|_{\mathcal{K}_{SA}}+\|Q_{c,\rho}^{\pi}-\Phi
w_{c,\rho}^{\pi}\|_{\mathcal{K}_{SA}}.$ (25)

We next bound each term on the RHS of the previous inequality. For the first
term, it was already established in Proposition 2.1 of [14] that

$\displaystyle\|Q^{\pi}-Q_{c,\rho}^{\pi}\|_{\mathcal{K}_{SA}}\leq\|Q^{\pi}-Q_{c,\rho}^{\pi}\|_{\infty}$
$\displaystyle\leq\frac{\gamma\max_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}}|\pi(a|s)-\pi_{b}(a|s)\rho(s,a)|}{(1-\gamma)(1-\gamma
D_{\rho,\max})}.$ (26)

Now consider the second term on the RHS of Eq. (25). First note that

$\displaystyle\|Q_{c,\rho}^{\pi}-\Phi
w_{c,\rho}^{\pi}\|_{\mathcal{K}_{SA}}^{2}$ $\displaystyle=\;$
$\displaystyle\|Q_{c,\rho}^{\pi}-\text{Proj}_{\mathcal{Q}}Q_{c,\rho}^{\pi}+\text{Proj}_{\mathcal{Q}}Q_{c,\rho}^{\pi}-\Phi
w_{c,\rho}^{\pi}\|_{\mathcal{K}_{SA}}^{2}$ $\displaystyle=\;$
$\displaystyle\|Q_{c,\rho}^{\pi}-\text{Proj}_{\mathcal{Q}}Q_{c,\rho}^{\pi}\|_{\mathcal{K}_{SA}}^{2}+\|\text{Proj}_{\mathcal{Q}}Q_{c,\rho}^{\pi}-\Phi
w_{c,\rho}^{\pi}\|_{\mathcal{K}_{SA}}^{2}$ ($*$) $\displaystyle=\;$
$\displaystyle\|Q_{c,\rho}^{\pi}-\text{Proj}_{\mathcal{Q}}Q_{c,\rho}^{\pi}\|_{\mathcal{K}_{SA}}^{2}+\|\text{Proj}_{\mathcal{Q}}\mathcal{B}_{c,\rho}(Q_{c,\rho}^{\pi})-\text{Proj}_{\mathcal{Q}}\mathcal{B}_{c,\rho}(\Phi
w_{c,\rho}^{\pi})\|_{\mathcal{K}_{SA}}^{2}$ $\displaystyle\leq\;$
$\displaystyle\|Q_{c,\rho}^{\pi}-\text{Proj}_{\mathcal{Q}}Q_{c,\rho}^{\pi}\|_{\mathcal{K}_{SA}}^{2}+\gamma_{c}^{2}\|Q_{c,\rho}^{\pi}-\Phi
w_{c,\rho}^{\pi}\|_{\mathcal{K}_{SA}}^{2},$

where Eq. ($*$) follows from the Babylonian–Pythagorean theorem (observe that
$Q_{c,\rho}^{\pi}-\text{Proj}_{\mathcal{Q}}Q_{c,\rho}^{\pi}\perp\mathcal{Q}$
and $\text{Proj}_{\mathcal{Q}}Q_{c,\rho}^{\pi}-\Phi
w_{c,\rho}^{\pi}\in\mathcal{Q}$). Rearrange the previous inequality and we
have

$\displaystyle\|Q_{c,\rho}^{\pi}-\Phi w_{c,\rho}^{\pi}\|_{\mathcal{K}_{SA}}$
$\displaystyle\leq\frac{1}{\sqrt{1-\gamma_{c}^{2}}}\|Q_{c,\rho}^{\pi}-\text{Proj}_{\mathcal{Q}}Q_{c,\rho}^{\pi}\|_{\mathcal{K}_{SA}}.$
(27)

Substituting Eqs. (26) and (27) into the RHS of Eq. (25) and we finally obtain

$\displaystyle\|Q^{\pi}-\Phi w_{c,\rho}^{\pi}\|_{\mathcal{K}_{SA}}\leq\;$
$\displaystyle\frac{\gamma\max_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}}|\pi(a|s)-\pi_{b}(a|s)\rho(s,a)|}{(1-\gamma)(1-\gamma
D_{\rho,\max})}$
$\displaystyle+\frac{1}{\sqrt{1-\gamma_{c}^{2}}}\|Q_{c,\rho}^{\pi}-\text{Proj}_{\mathcal{Q}}Q_{c,\rho}^{\pi}\|_{\mathcal{K}_{SA}}.$

##  Appendix B The High Variance in [12]

Consider Theorem 2.1 of [12]. The constant $c_{2}$ on the second term is
proportional to
$\sum_{i=0}^{n-1}(\gamma\max_{s,a}\frac{\pi(a|s)}{\pi_{b}(a|s)})^{i}$ (which
appears as $f(\gamma\zeta_{\pi})$ using the notation of [12]). When
$\frac{\pi(a|s)}{\pi_{b}(a|s)}>1/\gamma$ (which can usually happen in
practice), the parameter $c_{2}$ grows exponentially fast with respect to the
bootstrapping parameter $n$. Moreover, since $n$ needs to be chosen large
enough for the results in [12] to hold, the variance term on the finite-sample
bound of the $n$-step off-policy TD-learning algorithm with linear function
approximation is exponentially large.