Non-Asymptotic Analysis for Single-Loop
(Natural) Actor-Critic with Compatible Function Approximation

Yudan Wangub
Yue Wangucf
Yi Zhouutah
Shaofeng Zouub,xxx

ubElectrical Engineering, University of Buffalo
ucfElectrical and Computer Engineering, University of Central Florida
utahElectrical and Computer Engineering, University of Utah
xxxComputer Science & Engineering, University at Buffalo

Shaofeng<EMAIL_ADDRESS>
Machine Learning, ICML

Actor-critic (AC) is a powerful method for learning an optimal policy in reinforcement learning, where the critic uses algorithms, e.g., temporal difference (TD) learning with function approximation, to evaluate the current policy and the actor updates the policy along an approximate gradient direction using information from the critic. This paper provides the tightest non-asymptotic convergence bounds for both the AC and natural AC (NAC) algorithms. Specifically, existing studies show that AC converges to an $\epsilon+\varepsilon_{\text{critic}}$ neighborhood of stationary points with the best known sample complexity of $\mathcal{O}(\epsilon^{-2})$ (up to a log factor), and NAC converges to an $\epsilon+\varepsilon_{\text{critic}}+\sqrt{\varepsilon_{\text{actor}}}$ neighborhood of the global optimum with the best known sample complexity of $\mathcal{O}(\epsilon^{-3})$, where $\varepsilon_{\text{critic}}$ is the approximation error of the critic and $\varepsilon_{\text{actor}}$ is the approximation error induced by the insufficient expressive power of the parameterized policy class.  This paper analyzes the convergence of both AC and NAC algorithms with compatible function approximation. Our analysis eliminates the term $\varepsilon_{\text{critic}}$ from the error bounds while still achieving the best known sample complexities. Moreover, we focus on the challenging single-loop setting with a single Markovian sample trajectory. Our major technical novelty lies in analyzing the stochastic bias due to policy-dependent and time-varying compatible function approximation in the critic, and handling the non-ergodicity of the MDP due to the single Markovian sample trajectory. Numerical results are also provided in the appendix.

§ INTRODUCTION

Actor-Critic (AC) [Barto et al., 1983, Konda & Tsitsiklis, 2003] is a reinforcement learning algorithm that combines the advantages of actor-only methods and critic-only methods by alternatively performing policy gradient update (actor) and action-value function estimation (critic) in an online fashion. Specifically, the critic uses a parameterized function to estimate the value function of the current policy, e.g., temporal difference (TD) [Sutton, 1988] and Q-learning [Watkins & Dayan, 1992]. Then the actor updates the policy along an approximate gradient direction based on the estimate from the critic using approaches such as policy gradient [Sutton et al., 1999] and natural policy gradient [Kakade, 2001]. In contrast to critic-only methods, AC methods, which are gradient based, usually have desirable convergence properties when combined with the approach of function approximation. However, critic-only methods may not converge or even diverge when applied together with function approximation [Baird, 1995, Gordon, 1996]. Moreover, AC methods also enjoy a reduced variance due to the  critic, and thus their convergence is typically more stable and faster than actor only methods.

While the asymptotic convergence for AC and NAC has been well understood in the literature, e.g., [Bhatnagar et al., 2009, Kakade, 2001, Konda & Tsitsiklis, 2003, Suttle et al., 2023], its non-asymptotic convergence analysis has been largely open until very recently. The non-asymptotic analysis is of great practical importance as it answers the questions that how many samples are needed and how to appropriately choose the different learning rates for the actor and the critic. Existing studies show that AC converges to an $\epsilon+\varepsilon_{\text{critic}}$ neighborhood of stationary points with the best known sample complexity of $\mathcal{O}\brac{\epsilon^{-2}}$ [Chen et al., 2021, Olshevsky & Gharesifard, 2022, Xu et al., 2020], and NAC converges to an $\epsilon+\varepsilon_{\text{critic}}+\sqrt{\varepsilon_{\text{actor}}}$ neighborhood of the global optimum with the best known sample complexity of $\mathcal{O}(\epsilon^{-3})$ [Chen et al., 2022, Xu et al., 2020], where $\varepsilon_{\text{critic}}$ is the approximation error of the critic and $\varepsilon_{\text{actor}}$ is the approximation error induced by the insufficient expressive power of the parameterized policy class. In this paper, when presenting sample complexity, we omit the log factors.
In these studies, the critic employs a fixed class of parameterized functions (typically linear function approximation with fixed feature), which may not satisfy the compatible condition [Sutton et al., 1999] (see <Ref> for details). This will result in a non-diminishing bias in the policy gradient estimate, and therefore, an additional error term $\varepsilon_{\text{critic}}$ is incurred in the overall error bound. Several works [Cayci et al., 2022, Wang et al., 2019] propose to use overparameterized neural networks in the critic to mitigate this issue, where $\varepsilon_{\text{critic}}$ diminishes as the network size increases. However, the convergence of the critic requires stringent conditions that are hard to verify [Cayci et al., 2022, Wang et al., 2019], and large neural network introduces expensive computational and memory costs. Actually, if the critic employs the approach of compatible function approximation, which is linear, then $\varepsilon_{\text{critic}}$ vanishes without introducing additional computational and memory costs [Sutton et al., 1999] (see details in <Ref>).
Moreover, for NAC applied with fixed function approximation in the critic, one needs to explicitly estimate the Fisher information matrix and compute its inverse, which will be computationally and memory expensive. Another advantage of compatible function approximation when applied with NAC is that the inverse of the Fisher information in the natural gradient will cancel out with the policy gradient (see <Ref>), and thus there is no need to estimate the Fisher information matrix anymore.

§.§ Challenges and Contributions

Comparison of sample complexity of AC

Reference         Single-loop        Sample size    Error    Comments

[Wang et al., 2019]   $\times$     $\mathcal{O}\brac{\epsilon^{-6}}$    $\epsilon+ \varepsilon_{\text{critic}}$    Critic: neural

[Zhou & Lu, 2022]   $\surd$      $\mathcal{O}\brac{\epsilon^{-1}}$    $\epsilon$    LQR

[Chen et al., 2023]   $\surd$      $\mathcal{O}\brac{\epsilon^{-2.5}}$

[Zhang et al., 2020]   $\surd$     Asymptotic

[Qiu et al., 2021]    $\times$    $\mathcal{O}\brac{\epsilon^{-4}}$

[Kumar et al., 2023]     $\times$      $\mathcal{O}(\epsilon^{-3})$        non-linear, smooth

[Kumar et al., 2023]
[Xu et al., 2020]   $\times$     $\mathcal{O}\brac{\epsilon^{-2.5}}$
$\epsilon+ \varepsilon_{\text{critic}} $
Critic: linear

[Xu et al., 2020, Suttle et al., 2023]    $\times$     $\mathcal{O}\brac{\epsilon^{-2}}$
function approx.

[Barakat et al., 2022]
[Wu et al., 2020]   $\surd$     $\mathcal{O}\brac{\epsilon^{-2.5}}$

[Olshevsky & Gharesifard, 2022]
[Chen et al., 2021]   $\surd$     $\mathcal{O}\brac{\epsilon^{-2}}$

Our Work     $\surd$      $\mathcal{O}(\epsilon^{-2})$   $\epsilon$

Though AC and NAC with compatible function approximation enjoy no approximation error from the critic and no need of estimating the Fisher information matrix (for NAC), their non-asymptotic convergence analyses are much more challenging than the ones with fixed function approximation. To the best of the authors' knowledge, this paper develops the tightest non-asymptotic error bounds for AC and NAC algorithms, and our analyses are for the challenging case of single Markovian sample trajectory. We prove that AC with compatible function approximation converges to an $\epsilon $ stationary point with sample complexity $\mathcal O(\epsilon^{-2})$, and NAC with compatible function approximation converges to an $\epsilon+\sqrt{\varepsilon_{\text{actor}}}$ neighborhood of the globally optimal policy with sample complexity $\mathcal O(\epsilon^{-3})$. Our non-asymptotic error bounds outperform the best known AC and NAC bounds in the literature by a constant $\varepsilon_{\text{critic}}$ and achieve the same sample complexity: $\mathcal O(\epsilon^{-2})$ for AC and $\mathcal O(\epsilon^{-3})$ for NAC (see <Ref>). We note that this constant $\varepsilon_{\text{critic}}$ is due to the approximation error of the function class used by the critic, and does not diminish with time.

One of the biggest challenges in the analysis is due to the time-varying critic feature function. Specifically, the critic with compatible function approximation employs an $\omega$-dependent linear function class, where $\omega$ is the policy parameter. As the actor updates the policy, the feature function of the critic also changes with $\omega$. Therefore, the critic is using a linear function with time-varying $\omega$-dependent feature to track the value function of the current policy $\pi_\omega$, which is also time varying. This makes the analysis of the tracking error, i.e., the error between the ideal limit of the critic given the current policy and its current estimate, challenging. In this paper, we design a novel approach to explicitly bound this error. The central idea is to construct an auxiliary eligibility trace with fixed feature to approximate the eligibility trace with time-varying feature (in the critic, we use $k$-step TD with compatible function approximation).

In this paper, we focus on the challenging single-loop setting with a single Markovian sample trajectory.
Some studies tried to decouple the updates of the actor and the critic using approaches, e.g., nested loop [Qiu et al., 2021, Agarwal et al., 2021, Chen et al., 2022, Xu et al., 2020, Suttle et al., 2023], and to further develop the non-asymptotic analysis.  Specifically, after the actor updates the policy, then the policy is fixed and the critic starts an inner loop to iterate sufficient number of steps until it gets a perfect evaluation of the current policy. This decoupling approach makes it easier to analyze as there is no need to analyze the interaction between the actor and the critic. However, this decoupling approach does not enjoy benefits from the two time-scale structure in the original AC and NAC algorithms [Konda & Tsitsiklis, 2003, Bhatnagar et al., 2009], e.g., algorithmic simplicity and statistical efficiency, and techniques therein cannot be generalized to analyze the single-loop single-trajectory two time-scale AC and NAC algorithms. Moreover, analyses therein require some kind of i.i.d. assumptions or require trajectories starting from any arbitrary state, which might be difficult to guarantee in practice.

To develop the tightest bound, we develop a novel approach that bounds the tracking error as a function of the policy gradient norm (for AC) and the optimality gap (for NAC). We also note that our analysis for NAC does not need the smoothness assumption on the parameterized policy, which is typically required in existing NAC and AC analyses [Chen et al., 2021, Olshevsky & Gharesifard, 2022].

§.§ Related Work

In this section, we review recent relevant works on non-asymptotic analyses on reinforcement learning algorithms with function approximation.  We provide a detailed comparison between our results and existing studies on AC and NAC in <Ref>. The "Sample complexity" in the table is the one needed to guarantee the gradient norm/optimality gap less than or equal to the "Error".

Comparison of sample complexity of NAC

Reference         Single-loop        Sample size    Error    Comments

[Khodadadian et al., 2022]   $\surd$     $\mathcal{O}\brac{\epsilon^{-6}}$

[Khodadadian et al., 2021]   $\times$     $\mathcal{O}\brac{\epsilon^{-3}}$    $\epsilon$
Tabular case

[Wang et al., 2019]   $\times$     $\mathcal{O}\brac{\epsilon^{-6}}$   $\epsilon+ \varepsilon_{\text{critic}}$

[Cayci et al., 2022]   $\times$     $\mathcal{O}\brac{\epsilon^{-3}}$   $+\sqrt{\varepsilon_{\text{actor}}} $    Critic: neural

[Agarwal et al., 2021]
$\times$   $\mathcal{O}\brac{\epsilon^{-6}}$

[Xu et al., 2020]    $\times$     $\mathcal{O}\brac{\epsilon^{-3}}$
$\epsilon+ \varepsilon_{\text{critic}} $
non-linear, smooth

[Xu et al., 2020]   $\times$     $\mathcal{O}\brac{\epsilon^{-4}}$
$+\sqrt{\varepsilon_{\text{actor}}} $
Critic: linear

[Chen et al., 2022]        $\times$     $\mathcal{O}\brac{\epsilon^{-3}}$
function approx.

Our Work     $\surd$      $\mathcal{O}(\epsilon^{-3})$   $\epsilon+\sqrt{\varepsilon_{\text{actor}}}$

Actor-critic analyses.
We list recent works on non-asymptotic analyses for AC in <Ref>. Based on whether the updates of actor and critic are decoupled, the results can be grouped into "single-loop" and "nested-loop/decoupling" approaches. For a general MDP, the best known sample complexity for both single-loop and nested-loop approaches is $\mathcal O(\epsilon^{-2})$ [Chen et al., 2021, Olshevsky & Gharesifard, 2022, Xu et al., 2020, Suttle et al., 2023]. The only exception is [Zhou & Lu, 2022], which is due to  the special structure of the LQR problem. These studies all use a fixed function class in the critic, and therefore,  the convergence error consists of a non-diminishing constant term of $\varepsilon_{\text{critic}}$. In this paper, we analyze the AC with compatible function approximation, and we obtain a strictly tighter error bound without $\varepsilon_{\text{critic}}$. Our analysis is also much more challenging than the ones in the literature, which is mainly due to that the function class in the critic varies with the policy in the actor.

Natural actor-critic analyses.

We list recent works on non-asymptotic analyses for NAC in <Ref>. The best sample complexity for single-loop NAC is $\mathcal{O}\brac{\epsilon^{-6}}$ and it is for the tabular case [Khodadadian et al., 2022], whereas the best sample complexity for nested-loop/decoupling NAC is $\mathcal{O}\brac{\epsilon^{-3}}$ with an error of $\epsilon+\varepsilon_{\text{critic}}+\sqrt{\varepsilon_{\text{actor}}}$ [Chen et al., 2022, Xu et al., 2020]. There exists a gap of $\mathcal{O}\brac{\epsilon^{-3}}$ between these two approaches, which is mainly due to the challenge in bounding the tracking error for NAC in the single-loop setting.  In this paper, we close this gap and show that NAC in the single-loop setting can also achieve the sample complexity of $\mathcal{O}(\epsilon^{-3})$, and more importantly with a reduced error of $\epsilon+\sqrt{\varepsilon_{\text{actor}}}$.

Actor/critic only analyses.
Non-asymptotic analyses for critic only methods have been extensively studied recently, e.g., TD [Srikant & Ying, 2019, Lakshminarayanan & Szepesvari, 2018, Bhandari et al., 2018, Cai et al., 2019, Sun et al., 2019, Xu & Gu, 2020], SARSA [Zou et al., 2019], gradient TD (GTD) method [Dalal et al., 2018, Xu et al., 2019, Wang et al., 2021, Wang et al., 2017, Liu et al., 2015, Gupta et al., 2019, Kaledin et al., 2020, Ma et al., 2020, Ma et al., 2021, Wang & Zou, 2020]. There are also non-asymptotic analyses for actor only method, e.g., [Bhandari & Russo, 2021, Bhandari & Russo, 2019, Agarwal et al., 2021, Mei et al., 2020, Li et al., 2021, Laroche & des Combes, 2021, Zhang et al., 2021, Cen et al., 2021, Zhang et al., 2020, Lin, 2022]. In this paper, we focus on AC and NAC algorithms, where  how the errors in the actor and the critic affects the other  needs to be analyzed.

§ PRELIMINARIES

Markov Decision Processes
Consider a general reinforcement learning setting, where an agent interacts with a stochastic environment modeled as a Markov decision process (MDP). An MDP can be represented by a tuple
$\vbrac{\mathcal{S}, \mathcal{A}, P, R}$,
where $\mathcal{S}$ denotes the state space, $\mathcal{A}$ denotes the discrete finite action space,
$R(\cdot,\cdot): \mathcal{S}\times \mathcal{A}\to [0, R_{\max}]$ is the reward function.
The transition kernel $P\brac{\cdot|s, a}$ denotes the distribution of the next state if taking action $a$ at state $s$, $\forall s\in\mcs,a\in\mca$.

A stationary policy $\pi$ maps a state $s\in \mathcal{S}$ to a probability distribution $\pi\brac{\cdot|s}$ over the action space $\mathcal{A}$.
the expected long term average reward for a policy $\pi$ is defined as follows:

\begin{align}
J\brac{\pi}&= \lim_{N\to \infty }\frac{1}{N}\E\bigg[\sum _{t=0}^{N-1}  R(s_t,a_t)\large|\pi\bigg ]\nn\\&=\E_{s\sim d_\pi, a\sim \pi(\cdot|s)}\Fbrac{ R(s,a)}
\end{align}

where we denote by $d_{\pi}$ the stationary distribution

$$d_{\pi}(s)=\lim_{N\to \infty}\frac{1}{N} \sum _{t=0}^{N-1} \Prob\brac{s_t=s|  \pi}.$$
Denote by $D_\pi= d_\pi \times \pi $  the state-action stationary distribution.
We rewrite $R_t:= R(s_t,a_t)$.
For a given policy $\pi$ and an initial  state
$s$, the relative value function is defined as

$$V^\pi(s)=\E\bigg[\sum_{t=0}^\infty  R_t -J(\pi)|s_0=s, \pi \bigg] ,\forall s\in \mathcal{S}.$$

Given initial state $s$ and action $a$, the  relative action value function ($Q$ function) for a given policy $\pi$ is defined as

\begin{align*}
Q^\pi(s,a)=\E\bigg[\sum_{t=0}^\infty  R_t-J(\pi)|&s_0=s,a_0=a, \pi  \bigg], \\ &\forall (s,a) \in \mathcal{S}\times \mathcal{A}.\nonumber
\end{align*}

The relative advantage function is defined as

A^π(s,a)=Q^π(s,a)-V^π(s),∀(s,a) ∈𝒮×𝒜.

The goal is to find the optimal policy $\pi^*$ that maximizes the long term average reward:
\max_\pi J(\pi).$

(Natural) Actor-Critic with Compatible Function Approximation
Consider a parameterized policy class $\Pi_\omega=\varbrac{\pi_\omega:\omega\in \mathcal{W}}$, where $\mathcal{W}\subseteq \mathbb{R}^d$. Then the problem in <Ref> can be solved by optimizing over the parameter space $\mathcal{W}$. Specifically, the actor updates the policy via the approach of (natural) policy gradient, where the policy gradient is given by [Sutton et al., 1999]

\begin{align}
\nabla J(\pi)&= \E_{D_{\pi_\omega}}\Fbrac{Q^{\pi_\omega}\brac{s,a}\phi_\omega(s,a)}
\end{align}

where $\phi_\omega (s,a)=\nabla_\omega \log \pi_\omega(a|s)$. We further let $\Phi_\omega$ denote the feature matrix, which is the stack of all feature vectors. Specifically, $\Phi_\omega\in \mathbb{R}^{|\mathcal{S}||\mathcal{A}|\times d}$ and the $(s,a)$-row of $\Phi_\omega$ is $\phi_\omega^\top(s,a)$.
On the other hand, the critic estimates the $Q$ function in <Ref> via the approach of TD learning, and the $Q$ function is usually parameterized using linear function approximation in the existing literature, i.e., $\mathcal Q=\{Q_\theta(s,a)=\phi(s,a)^\top \theta, \theta\in\Theta\}$ where $\phi$ denotes the feature vector and $\Theta\subseteq\mathbb{R}^d$. However, as summarized in <Ref>, using a fixed $\phi$ introduces an additional

non-vanishing error term $\varepsilon_{\text{critic}}$ to the gradient estimate.

To avoid the critic's function approximation error,  [Sutton et al., 1999, Konda & Tsitsiklis, 2003] proposed a smart idea of compatible function approximation, which
uses the compatible feature vector $\phi_\omega$ that depends on the policy parameter $\omega$. To explain,
in order to approximate the value function $Q^{\pi_\omega}$ associated with policy $\pi_\omega$, we can set the feature vector as $\phi_\omega (s,a):=\nabla_\omega \log \pi_\omega(a|s)$ and solve for the best linear approximation parameter $\bar\theta^*_\omega$ via the following optimization problem.

\begin{align}\label{eq:thetabar}
\bar\theta^*_\omega \in \arg \min _{\theta} \E_{D_{\pi_\omega} }\Fbrac{\brac{Q^{\pi_\omega}(s,a)-\phi_\omega^\top(s,a)\theta}^2}.
\end{align}

With compatible function approximation, the policy gradient $\nabla J(\pi_\omega)$ can be rewritten as:

∇J(π_ω)    =_D_π_ω ∇logπ_ω(a|s)Q^π_ω(s,a)

This implies that as long as we can solve the finite dimensional problem <Ref>, linear function approximation with the compatible feature $\phi_\omega$ and parameter $\bar\theta^*_\omega$ does not induce any function approximation error.
This approach is referred to as compatible function approximation [Sutton et al., 1999], i.e., estimating $Q^{\pi_\omega}$ using an $\omega$-dependent linear function class: $\mathcal Q_\omega=\{\phi^\top_\omega(s,a) \theta, \theta\in\Theta\}.$

To solve <Ref> for the compatible function approximation parameter, we use the $k$-step  TD algorithm with compatible feature $\phi_\omega$
[Sutton et al., 1999].

The actor can also use the following natural policy gradient to update the policy [Kakade, 2001]:

\widetilde{\nabla} J(\pi_\omega)=F_\omega ^{-1}\nabla J(\pi_\omega),

where the matrix $F_\omega$ denotes the Fisher information matrix:

F_\omega=\E_{D_{\pi_\omega}}\Fbrac{ \nabla  \log \pi_\omega(a|s)\brac{\nabla \log \pi_\omega(a|s)}^\top }.

With compatible function approximation, natural policy gradient is reduced to:

\widetilde{\nabla} J(\pi_\omega)=\bar \theta^*_\omega. $$

That is, there is no need to estimate the Fisher information matrix and compute its inverse, which is typically computationally expensive.

§ MAIN RESULTS

(Natural) Actor-Critic with Compatible Function Approximation

[1]
Initialization:  $k$, $\eta_0$, $ \omega_0, \pi_0=\pi_{\omega_0},\theta_0,$ $\phi_0=\nabla \log\pi_{0},$
$s_0,a_0\sim \pi_0(\cdot|s_0),z_0=0$
Observe $R_t$; Sample $s_{t+1}\sim  P(\cdot|s_t,a_t)$;

$a\tit\sim \pi_t(\cdot|s\tit) $

$\phi_t(s,a)=\nabla_\omega \log\pi_{t}(a|s)$

Critic: $\delta_t(\theta_t)=R_t-\eta_t+ \phi_t^\top(\sa)\theta_t-\phi_t^\top(s_t,a_t)\theta_t $

$z_t=\sum_{j=t-k}^t \phi_j(s_j,a_j)$

$\eta_{t+1}=\eta_t+ \gamma_t(R_t-\eta_t)$

$\theta_{t+1}=\Pi_{2,B}(\theta_t+\alpha_t \delta_t(\theta_t)z_t)$
Option I: $\omega_{t+1}=\omega_t+\beta_t \phi_t^\top(s_t,a_t)\theta_t \phi_t(s_t,a_t)$
Option II: $\omega_{t+1}=\omega_t+\beta_t \theta_t $

The detailed AC and NAC algorithms with compatible function approximation is summarized in <Ref>.

In the critic update, $\alpha_t$ is the stepsize, and denote by

$\Pi_{2,B}(v)=\arg\min_{\twonorm{\omega}\leq B}\twonorm{v-\omega} $ for any $v\in\mathbb R^d$ the project operator, and $B$ is the radius.
Next, we present the non-asymptotic bounds for the AC and NAC with compatible function approximation in <Ref>.

(Uniform Ergodicity) Consider the MDP with policy $\pi_\omega$ and transition kernel $P$, there exists constants $m>0$, and
$\rho\in (0,1)$ such that

\sup_{s\in\mcs}\tvnorm{\mathbb{P}\brac{s_t\in \cdot|s_0=s}-D_{\pi_\omega}(\cdot)}\leq m \rho^{t}.

Here $\tvnorm{\cdot}$ denotes the total variation distance between two distributions.

Assumption <ref> is widely used in the literature to handle the Markovian noise, e.g., [Srikant & Ying, 2019, Zou et al., 2019, Bhandari et al., 2018].
We further assume that the $d$ feature functions, $\phi_{\omega,i}, i=1,...,d$, are linearly independent, i.e., the feature matrix $\Phi_\omega$ is full rank when $|\mcs||\mca|\geq d$. This is also commonly used in the literature of analyzing RL algorithms with linear function approximation [Srikant & Ying, 2019, Zou et al., 2019, Bhandari et al., 2018].

§.§ Critic:$k$-step TD

Consider the critic update, where the TD method is used to learn the relative value function under the average-reward setting. It is known that the feature function needs to satisfy certain condition (Assumption 2 in [Tsitsiklis & Van Roy, 1999]) so that the limit of the TD method is unique.   In the following proposition, we show that compatible function approximation automatically satisfy the assumption needed in [Tsitsiklis & Van Roy, 1999], and therefore guarantees the convergence of the critic without the need of any additional assumptions.

For any $\omega\in \mathcal{W}$ and $\theta \in \Theta$,
$\Phi_\omega \theta \neq \mathbf{e},$
where  $\mathbf e\in \mathbb R^d$ is an all-one vector.

We note that the results in [Wu et al., 2020] use a different assumption from the one in [Tsitsiklis & Van Roy, 1999] to guarantee the convergence of the critic in the average-reward setting (Assumption 4.1 in [Wu et al., 2020]): the matrix
$\mathbb E[\phi(s)(\phi(s')-\phi(s))^{\top}]$ is negative
definite, where $\phi$ is the fixed feature function, $s$ is the current state and $s'$ is the subsequent state.

As discussed in <Ref>, we would like the critic to find the solution of <Ref>. However, the objective in <Ref> requires the knowledge of $Q^{\pi_\omega}$, which is unavailable. Therefore, in the critic, we propose to use the method of $k$-step TD, so that as $k$ enlarges, the solution from the $k$-step TD converges to the solution of <Ref>. We present the $k$-step TD algorithm in <Ref>. Here, the AC and NAC algorithms in <Ref> are single-loop, single sample trajectory and two time-scale. We introduce the $k$-step TD algorithm in <Ref> only to illustrate the basic idea.

Based on <Ref>, Assumption <ref>, and the assumption that $\Phi_\omega$ is full rank, from <cit.>, we can show that the $k$-step TD algorithm in <Ref> has a unique solution, denoted by $\theta_{\omega}^*$:

ϕ_ω^⊤(s,a)𝒯_π_ω^(k) ϕ^⊤_ω(s,a) θ^*_ω -ϕ^⊤_ω(s,a) θ^*_ω

$ \mathcal{T}_{\pi_\omega}^{(k)}(Q (s,a))=\E\big[\sum_{j=0}^{k-1} (R_j- J(\pi_\omega)) + Q (s_k,a_k) |s_0=s,a_0=a,\pi_\omega \big].$

Assume that $\E_{D_w}\Fbrac{\phi_w(s,a)\phi^\top_w(s,a)}$ is positive definite with the minimum eigenvalue $\lambda_{\min}>0$. This is to guarantee that the solution to <Ref> is unique. We can remove this assumption by adding a regularizer $\lambda\|\theta\|_2^2$ to <Ref> to guarantee the solution to the regularized <Ref> is unique, and bounding the difference.

Then we bound the difference between the solution to <Ref> and the solution to the $k$-step TD algorithm in the following proposition.

For any $\omega\in \mathcal{W}$, the difference between $\theta_{\omega}^*$ and $\bar{\theta}_{\omega}^*$ can be bounded as follows:

\twonorm{\theta_{\omega}^*-\bar{\theta}_{\omega}^*}\leq
\frac{C_{\text{gap}}m\rho^k}{\lambda_{\min}},
where $C_{\text{gap}}$ is a constant defined in <Ref>.

It can be seen that the bound diminishes exponentially with $k$. Therefore by picking a large $k$, the $k$-step TD is expected to solve <Ref> to a desired accuracy.

Compatible $k$-step TD Algorithm

Initialization: $k$,  $\eta, \theta_0,$ $\phi=\nabla \log\pi_{\omega},$
$s_0,a_0\sim \pi_\omega(\cdot|s_0),z_0=0$
Observe $R_t$
$s_{t+1}\sim  P(\cdot|s_t,a_t)$;

$a\tit\sim \pi_\omega(\cdot|s\tit) $
$\delta(\theta_t)=R_t-\eta+ \phi^\top(\sa)\theta_t-\phi^\top(s_t,a_t)\theta_t $

$z_t=\sum_{j=t-k}^t \phi(s_j,a_j)$

$\eta=\eta+ \gamma_t(R_t-\eta)$

$\theta_{t+1}=\Pi_{2,B}(\theta_t+\alpha_t \delta(\theta_t)z_t)$

§.§ Non-asymptotic Bound for AC

(Smoothness and Boundedness)
For any $\omega,\omega'\in \mathbb{R}^d$ and any state-action pair $(s,a)\in \mathcal{S}\times \mathcal{A}$,
there exist positive constants
$L_\phi,C_\phi,C_\pi$ and $L_\delta$ such that

\begin{align}
&   \text{1)} \twonorm{\phi_\omega(s,a)-\phi_{\omega'}(s,a)}\leq L_\phi \twonorm{\omega-\omega'};\nonumber
\\&\text{2)}\tvnorm{\pi_\omega(\cdot|s)-\pi_{\omega'}(\cdot|s)}\leq C_\pi \twonorm{\omega-\omega'};\nonumber
\\& \text{3)} \twonorm{\phi_\omega(s,a)}\leq C_\phi;\nonumber
\\&\text{4)}
\twonorm{\nabla^2 \pi_\omega(a|s) }\leq C_\delta;\nonumber
\\
\lbrac{\partial_{\omega_i}\partial_{\omega_j}\partial_{\omega_l}\pi_{\omega}(a|s) }\leq L_\delta \text{, for } 1\leq i,j,l\leq n.\qquad\qquad\nn
\end{align}

The first three assumptions in Assumption <ref> assume the policy and feature function $\phi_\omega$ is smooth and bounded.
The fourth and fifth assumptions in Assumption <ref> are only needed for the AC analysis. For the NAC analysis, it is not necessary.
We note that these assumptions can be easily satisfied by choosing a proper policy parameterization.
For example,
if the policy is parameterized using neural network, then these assumptions can be satisfied [Du et al., 2019, Miyato et al., 2018, Neyshabur, 2017] if the activation functions are analytic functions and have bounded each-order derivative, (e.g. logistic, hyperbolic tangent and softplus). With these proper policy parameterizations, the fifth one in Assumption <ref> can be deduced by $\twonorm{\nabla^2 \pi_\omega(a|s)-\nabla^2 \pi_{\omega'}(a|s)} \leq L_{\delta} \twonorm{\omega-\omega'}$.

We first present the bound on the tracking error, which measures how the critic tracks its ideal limit:

$$\frac{1}{T}\sum _{t=0}^{T-1} \E\Fbrac{\twonormsq{\theta^*_t-\theta_t}}.$$

Here, $\theta_t$ is the critic parameter at time $t$ of <Ref>, and we rewrite  $\theta^*_t=\theta^*_{\omega_t}$ and $J(\omega_t)=J(\pi_{\omega_t})$   for convenience. In the AC algorithm,

we set $\alpha_t=\alpha$,
$\beta_t=\beta$, $\gamma_t=\gamma$, and $k = \mathcal{O}\brac{\log T}$ such that $\gamma\geq  \alpha\geq   \beta\geq m \rho^k.$
Note that we use a projection in Line 8 in <Ref>.  In order for convergence and optimality, we require that all $\|\theta_\omega^*\|\leq B$. A sufficient condition to guarantee this is to set $B=\frac{m R_{\max}C_\phi}{(1-\rho)\brac{\lambda_{\min}-C_\phi^2 d m \rho^k }}$ (see Appendix <ref> for the proof).

The tracking error of the AC algorithm in  <Ref> can be bounded as follows:

\begin{align}
&\frac{1}{T}\sum _{t=0}^{T-1} \E\Fbrac{\twonormsq{\theta^*_t-\theta_t}} \nn
\\ &\leq  \brac{\frac{c_\alpha\beta}{\alpha}+\frac{c_\eta \beta}{\gamma}}\frac{1}{T}\sum _{t=0}^{T-1} \E \ftwonormsq{\gradj}
+\mathcal{O}\brac{\frac{1}{T \alpha}}\nn
\\ & +\mathcal{O}\brac{\frac{\log^2 T}{T \gamma}}\nn
+\mathcal{O}\brac{\alpha\log^2 T }
+\mathcal{O}\brac{\beta\log^3 T }
\\& + \mathcal{O}\brac{\gamma\log^3 T }+\mathcal{O}\brac{\frac{\beta^2\log^2 T}{\alpha}}
+\mathcal{O}\brac{\frac{\beta^2\log T}{\gamma }}\nn
\\& +\mathcal{O}\brac{\frac{\beta}{\alpha}(m\rho^k)}
+\mathcal{O}\brac{(m\rho^k)\log^2 T}
\end{align}

where $c_\alpha$ and $ c_\eta$ is a positive constant defined in
Set $\gamma=\mathcal{O}(\frac{1}{\sqrt{T}})$,  $  \alpha=\mathcal{O}(\frac{1}{\sqrt{T}\log ^2 T})$, $ \beta =\mathcal{O}(\frac{1}{\sqrt{T}\log ^2 T})$, we have

\begin{align}
\frac{1}{T} &\sum_{t=0}^{T-1}\E[\twonormsq{\theta^*_t-\theta_t}]\nn\\&\leq
\frac{1}{4C^4_\phi T}\sum_{t=0}^{T-1}\E [\twonormsq{\gradj}]+\mathcal{O}\brac{\frac{{\log^3 T}}{\sqrt{T}} }.
\end{align}

For simplicity, we only present the order of the bound here, and the detailed non-asymptotic bound can be found in the <Ref>. The key novelty in the analysis is that we bound the tracking error as a function of the policy gradient, and we also bound the policy gradient as a function of the tracking error. By applying the bound recursively, we get a tight bound on the tracking error in <Ref>. Many existing studies in the two time-scale analysis upper bound the policy gradient in the tracking error using its maximum norm, which is constant-level. However, as we see in the following theorem, the policy gradient shall also decrease to zero. Therefore, the above approach does not obtain the tightest bound, and leads to a higher-order sample complexity.

Consider the AC algorithm in  <Ref>. It can be shown that

\begin{align}
\frac{1}{T}& \sum _{t=0}^{T-1} \E \Fbrac{\twonormsq{\gradj}}
\leq  \frac{2 C_\phi^4}{T} \sum _{t=0}^{T-1} \E \Fbrac{\twonormsq{\thestar-\theta_t}}\nn
\\&+\mathcal{O}\brac{\frac{1}{T \beta}}
+\mathcal{O}\brac{\beta \log^2 T }+\mathcal{O}(m\rho^k).\nonumber
\end{align}

Set $\gamma=\mathcal{O}(\frac{1}{\sqrt{T}}),  \alpha,  \beta =\mathcal{O}(\frac{1}{\sqrt{T}\log^2 T})$, then

\frac{1}{T} \sum _{t=0}^{T-1} \E \Fbrac{\twonormsq{\gradj}}
\leq\mathcal{O}\brac{\frac{{\log^3 T}}{\sqrt{T}}}.

<Ref> implies that the AC algorithm with compatible function approximation converges to an $\epsilon$-stationary point with sample complexity $\epsilon^{-2}$. This improves the best known error bound by a constant $\varepsilon_{\text{critic}}$
[Wang et al., 2019, Zhang et al., 2020, Qiu et al., 2021, Kumar et al., 2023, Xu et al., 2020, Barakat et al., 2022, Wu et al., 2020, Chen et al., 2021, Olshevsky & Gharesifard, 2022, Xu et al., 2020], and matches the best known sample complexity [Chen et al., 2021, Olshevsky & Gharesifard, 2022, Xu et al., 2020, Suttle et al., 2023].

§.§ Non-asymptotic Bound for NAC

In this section, we present the non-asymptotic bound for the NAC algorithm in <Ref>.
It was shown in [Agarwal et al., 2021] that due to the parameter invariant property of the natural  policy gradient update, natural  policy gradient is able to converge to the globally optimal policy with a gap that depends on the capacity of the policy class. Define the compatible linear function approximation error

\varepsilon_{\text{actor}}=\max_{\omega\in \mathcal{W}}\varbrac{\min_{\theta}\E_{D_{\pi_\omega}}\Fbrac{\twonormsq{A^{\pi_\omega}(s,a)-\phi_\omega ^\top(s,a) \theta}}}.

This  error represents the approximation error due to the insufficient expressive power of the policy parameterization, and shall decrease if a large neural network is used.

Using the same idea as the one in AC, we can also develop a tight bound on the tracking error: $\mathcal{O}\brac{{T^{-\frac{1}{3}}}}$, where now we bound the tracking error as a function of the optimality gap instead of the gradient norm. We then also develop bound of the optimality gap as a function of the tracking error. Applying them recursively, we obtain the tightest bound on the tracking error and the tightest bound on the optimality gap in the following theorem.

We set $\alpha_t=\alpha$,
$\beta_t=\beta$, $\gamma_t=\gamma$, and $k=\mathcal{O}\brac{\log T}$ such that $\gamma\geq \alpha\geq  \beta\geq m \rho^k.$

There exist a constant $C_\infty< \infty$ such that
\sup_{\omega\in\mathcal{W}}  \mynorm{\frac{D_{\pi^*}(s,a)}{D_{\pi_\omega}(s,a)}}_\infty\leq C_\infty.

Assumption <ref> guarantees that the policy is sufficiently exploratory, and is commonly used in NAC analyses, e.g.,  [Cayci et al., 2022, Xu et al., 2020, Agarwal et al., 2021]. Approaches to guarantee this assumption were also studied in [Khodadadian et al., 2021, Khodadadian et al., 2022].

Consider the NAC algorithm in  <Ref>. Then,
we have that

min_t≤T  J(π^*)-J(ω_t)

+ 𝒪γ√(logT) /√(α)
+ 𝒪√(αlog^3 T )

+ 𝒪√(log^3T)/T√(αβ)

+ 𝒪√(γβ)logT /√(α)
+ 𝒪√(βlog^3 T)

+ 𝒪√((mρ^k)β/α) + 𝒪mρ^k/√(αβ)
+ 𝒪√((mρ^k)γ/α)

+𝒪√((mρ^k) logT)

If we set $\gamma=\mathcal{O}(T^{-\frac{2}{3}}\log T),  \alpha=\mathcal{O}(T^{-\frac{2}{3}}\log^{-1}T),  \beta =\mathcal{O}(T^{-\frac{2}{3}}\log^{-1}T)$, we have

\begin{align}
\min_{t\leq T } \E[J(\pi^*)-J(\omega_t)]\leq \mathcal{O}\brac{{T^{-\frac{1}{3}}}\log ^3T}
+ \mathcal{O}\brac{\sqrt{\varepsilon_{\text{actor}}}}.\nonumber
\end{align}

Unlike the results for AC in <Ref>, <Ref> for NAC only needs the first three assumptions in Assumption <ref>. This is one advantage of using compatible function approximation in NAC. As we can see from Line 11 in <Ref> and <Ref>, the inverse of the Fisher information matrix is cancelled out. Therefore, there is no stochastic noise from using $\phi_{\omega}(s_t,a_t)\phi^\top_{\omega}(s_t,a_t)$ in the analysis of NAC. However, in AC, we need to handle this noise, and therefore, the fourth assumption in Assumption <ref> is needed for the AC algorithm.

<Ref> implies that NAC with compatible function approximation  converges to an $\epsilon+\sqrt{\varepsilon_{\text{actor}}}$-neighborhood of the globally optimal policy $\pi^*$ with sample complexity $\mathcal O(\epsilon^{-3})$.
Compared to existing studies, our work eliminate the approximation error of the critic, $\varepsilon_{\text{critic}}$, from the overall error bound [Wang et al., 2019, Cayci et al., 2022, Agarwal et al., 2021, Xu et al., 2020, Xu et al., 2020, Chen et al., 2022]. Moreover, as summarized in <Ref>,  the best known sample complexity of NAC is $\epsilon^{-3}$, which however is for the nested-loop NAC variant [Xu et al., 2020, Chen et al., 2022]. Our results achieves this sample complexity, and is for the challenging single-loop NAC algorithm with a single Markovian sample trajectory.

Here we provide a proof sketch for the NAC algorithm to highlight major challenges and our technical novelties. The analysis of NAC contains of most major technical novelty in the AC analysis.

For simplicity of presentation, we set $\hat t=\mathcal{O}\brac{\frac{\log T}{\alpha}}$ and
$\widetilde T=\hat t\lceil \frac{T}{\hat t \log T} \rceil$.
We denote by
$$M_t=\mathbb E[||\theta_{t}-\theta^*_{t}||^2_2]+ \mathbb E[(\eta_t-J(\omega_t))^2]$$
the sum of the tracking error and the estimation error of the average reward. Denote by $\D(\omega_t)=KL(\pi^*|\pi_t)$ the KL divergence between policy $\pi^*$ and $\pi_t$.

Step 1 (Error decomposition):
According to the smoothness property of $\D(\omega)$ with respect to $\omega$, we bound the performance gap between the current policy and the optimal policy (optimality gap) as follows:

\begin{align}
&\frac{1}{\widetilde T}\sum_{j=t}^{t+\widetilde T-1}\mathbb E[J(\pi^*)-J(\omega_j)]\leq \frac{\D(\omega_{t+\widetilde T})-\D(\omega_t)}{\widetilde T \beta }\nn\\
&+ \mathcal{O}\left(\sqrt{\frac{1}{\widetilde T}\textstyle\sum_{j=t}^{t+\widetilde T-1} M_j}\right)+\mathcal{O}(C_\infty \sqrt{\varepsilon_{\text{actor}}}+ \beta+m\rho^k).\nn
\end{align}

Step 2 (Estimation error in the average reward): In this step, we analyze estimation error in the average reward:
$\eta_t-J(\omega_t)$. We provide a tight characterization of this error:

\begin{align}
\mathbb E& [(\eta_{t+1}-J(\omega_{t+1}))^2] \nn\\&\leq (1-\gamma)\mathbb E[(\eta_{t}-J(\omega_{t}))^2]
+\mathcal{O}(\beta \mathbb E[||\nabla J(\omega_t)||_2^2])
\nn\\&\quad+ \mathcal{O}( m\rho^k\gamma +k^2 \gamma^2 +k^2 \gamma\beta +\beta^2).\nn
\end{align}

One of our key novelties lies in that we bound this estimation error using the gradient norm $\mathbb E[||\nabla J(\omega_t)||_2^2]$. The above bound itself is tighter than the existing one in (Wu et al., 2020).

Step 3 (Tracking error):
In this step, we bound the tracking error in the critic: $||\theta_t-\theta_t^*||_2^2$.
By the TD error step in Algorithm 1, we decompose the term $||\theta_{t+1}-\theta_{t+1}^*||^2_2$ as follows:

\begin{align}
||\theta&_{t+1}-\theta_{t+1}^*||^2_2 \nn\\&\leq || \theta_t-\theta_{t}^* ||^2_2+|| \theta_{t}^*-\theta_{t+1}^*||_2^2 + \alpha^2 ||\delta_t z_t||^2_2 \nn\\&\quad+ 2 \alpha\langle\theta_t-\theta_{t}^*, \delta_t z_t \rangle+ 2\alpha \langle \theta_{t}^* - \theta_{t+1}^* , \delta_t z_t\rangle
\nn\\&\quad+2 \langle\theta_t-\theta_{t}^*, \theta_{t}^*-\theta_{t+1}^* \rangle.\nn
\end{align}

Another key challenge lies in  how to bound the term
$\mathbb E[\langle \theta_t-\theta_t^*, \delta_t z_t\rangle ] $.  We develop a novel technique of auxiliary Markov chain to decompose this error into two parts: 1) error due to time-varying feature function and 2) error due to time-varying policy. Specifically, consider the first Markov chain generated from the algorithm:

$$s_0,a_0 \overset{\pi_0\times P}{\to} s_1,a_1\to...\to s_t,a_t \overset{\pi_t\times P}{\to}s_{t+1},a_{t+1},$$
where at each time $j$, the action is chosen according to $\pi_j$ and the transition kernel is $P$. Here $z_t=\sum_{j=t-k}^t \phi_j(s_j,a_j)$ is the eligibility trace used in the algorithm. It can be seen that in $z_t$, the feature $\phi_j$ changes with $j$, and the distribution of $s_j,a_j$ depends on the time-varying policy $\pi_j$. We then design an auxiliary eligibility trace $\hat z_t=\sum_{j=t-k}^t \phi_t(s_j,a_j)$, where the feature is fixed to be $\phi_t$, and only the the distribution of $s_j,a_j$ depends on the time-varying policy $\pi_j$. To further handle the time-varying distribution of  $s_j,a_j$, we design an auxiliary Markov chain (denoted by $A1$) as follows:

$$A1: ( s_0,\widetilde  a_0 )\sim \pi_t\overset{\pi_t\times P}{\to} \widetilde s_1,\widetilde a_1{\to}...\widetilde  s_t,\widetilde a_t \overset{\pi_t\times P}{\to}\widetilde s_{t+1},\widetilde a_{t+1},$$
where the action at each time $j$ is always chosen according to a fixed policy $\pi_t$. Based on this auxiliary Markov chain, we introduce another auxiliary eligibility trace $\widetilde  z_t=\sum_{j=t-k}^t \phi_t(\widetilde s_j,\widetilde a_j)$, where it uses a fixed feature $\phi_t$, and samples from this auxiliary Markov chain. Lastly, we design a second auxiliary Markov chain (denoted by $A2$):

$$A2: (\bar s_0,\bar  a_0)\sim D_t \overset{\pi_t\times P}{\to} \bar s_1,\bar a_1{\to}...\bar  s_t,\bar a_t \overset{\pi_t\times P}{\to}\bar s_{t+1},\bar a_{t+1},$$

where the only difference between A2 and A1 lies in the initial state distribution. Then we define the last auxiliary eligibility trace as $\bar  z_t=\sum_{j=t-k}^t \phi_t(\bar s_j,\bar a_j)$.

The difference between $z_t $ and $\hat z_t$ measures the error due to the time-varying compatible feature function. We bound this error using the Lipschitz continuity of the feature function.  The difference between $\hat z_t $ and $\widetilde z_t$ measures the error due to the  time-varying sampling policy.   The difference between $\widetilde z_t $ and $\bar z_t$ measures the error due to the difference between the stationary distribution and the actual distribution of the samples, which can be bounded based on Assumption 1. By such a error decomposition, we can show that

\begin{align}
\mathbb E&[||\theta_{t+1}-\theta^*_{t+1}||^2_2] \leq (1-\bar \lambda_{\min}\alpha /2)\mathbb E[||\theta_{t}-\theta^*_{t}||^2_2]
\nn\\
&+\mathcal{O}(k^2 \alpha \mathbb E[(\eta_t-J(\omega_t))^2] )+\mathcal{O}(\beta\mathbb E [||\nabla J(\omega_t)||_2^2])\nn\\
&+ \mathcal{O}\brac{k^3 \alpha^2+k^3\alpha\beta+\beta^2+m\rho^k\alpha+\frac{(m\rho^k)^2}{\beta} } .\nn
\end{align}

Step 4 (Bound on gradient): As we can see from Steps 2 and 3, we bound the estimation error of the average reward and the tracking error using the gradient norm $\|\nabla J(\omega_t)\|_2^2$. Therefore,  in order to derive the tightest bound, we further develop a novel bound on the gradient norm $\|\nabla J(\omega_t)\|_2^2$. Note that the idea is novel as it serves as a pivotal link connecting the analysis of the tracking error/estimation error in the average reward and the optimality gap. Specifically, we bound the gradient norm using
the estimation error in the average reward and tracking error. By the smoothness of $J(\omega)$, we have that

\begin{align}
\sum_{j=t}^{t+\widetilde T-1}&\frac{\mathbb E [ ||\nabla J(\omega_j) ||_2^2]}{\widetilde T}\leq 2C^2_\phi \frac{J(\omega^*)- E [J(\omega_{t})]}{\beta \widetilde T}\nn
\\& + \mathcal O\bigg(\frac{1}{\widetilde T}\sum_{j=t}^{t+\widetilde T-1}\mathbb E[||\theta_j-\theta_j^*||_2^2]\bigg) +\mathcal{O}(m\rho^k+\beta).\nn
\end{align}

We also note that we bound the gradient norm using the optimality gap, and this is of great importance to establish the tight bound in this paper. In previous works, this  term $\mathbb E [J(\omega_{t+\widetilde T})]- E [J(\omega_{t})] $ is bounded by a constant, and thus the overall complexity is not as tight.

Step 5: Combining steps 1-4, we conclude the proof.

§ CONCLUSION

In this paper, we develop the tightest non-asymptotic convergence bounds for
both the AC and NAC algorithms with compatible function approximation. For the AC algorithm, our results achieve the best sample complexity of $\epsilon^{-2}$ with a reduced error from $\epsilon+\varepsilon_{\text{critic}}$ to $\epsilon$, where $\varepsilon_{\text{critic}}$ is a non-diminishing constant. For the NAC algorithm, our results is the first one in the literature that analyze the single-loop NAC with a single Markovian trajectory, and we achieve the best known sample complexity of $\epsilon^{-3}$ also with a reduced error of $\epsilon+\sqrt{\varepsilon_{\text{actor}}}$. Our results demonstrate the advantage of compatible function approximation when applied in AC and NAC algorithms, including relaxed technical condition to guarantee convergence, no need of estimating Fisher information matrix, and no approximation error from the critic. Our technical novelty lies in analyzing the error due to use of a  time-varying and policy dependent feature in the critic.

[Agarwal et al., 2021]
Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G.
On the theory of policy gradient methods: Optimality, approximation, and distribution shift.
The Journal of Machine Learning Research, 220 (1):0 4431–4506, 2021.

[Baird, 1995]
Baird, L.
Residual algorithms: Reinforcement learning with function approximation.
In Machine Learning Proceedings, pp.  30–37. Elsevier, 1995.

[Barakat et al., 2022]
Barakat, A., Bianchi, P., and Lehmann, J.
Analysis of a target-based actor-critic algorithm with linear function approximation.
In International Conference on Artificial Intelligence and Statistics, pp.  991–1040. PMLR, 2022.

[Barto et al., 1983]
Barto, A. G., Sutton, R. S., and Anderson, C. W.
Neuronlike adaptive elements that can solve difficult learning control problems.
IEEE Transactions on Systems, Man, and Cybernetics, SMC-130 (5):0 834–846, 1983.

[Bhandari & Russo, 2019]
Bhandari, J. and Russo, D.
Global optimality guarantees for policy gradient methods.
arXiv e-prints, pp.  arXiv–1906, 2019.

[Bhandari & Russo, 2021]
Bhandari, J. and Russo, D.
On the linear convergence of policy gradient methods for finite MDPs.
In Proc. International Conference on Artifical Intelligence and Statistics (AISTATS), pp.  2386–2394. PMLR, 2021.

[Bhandari et al., 2018]
Bhandari, J., Russo, D., and Singal, R.
A finite time analysis of temporal difference learning with linear function approximation.
In Proc. Annual Conference on Learning Theory (CoLT), pp.  1691–1692, 2018.

[Bhatnagar et al., 2009]
Bhatnagar, S., Sutton, R. S., Ghavamzadeh, M., and Lee, M.
Natural actor–critic algorithms.
Automatica, 450 (11):0 2471–2482, 2009.

[Cai et al., 2019]
Cai, Q., Yang, Z., Lee, J. D., and Wang, Z.
Neural temporal-difference learning converges to global optima.
In Proc. Advances in Neural Information Processing Systems (NeurIPS), pp.  11312–11322, 2019.

[Cayci et al., 2022]
Cayci, S., He, N., and Srikant, R.
Finite-time analysis of entropy-regularized neural natural actor-critic algorithm.
arXiv preprint arXiv:2206.00833, 2022.

[Cen et al., 2021]
Cen, S., Cheng, C., Chen, Y., Wei, Y., and Chi, Y.
Fast global convergence of natural policy gradient methods with entropy regularization.
Operations Research, 2021.

[Chen et al., 2021]
Chen, T., Sun, Y., and Yin, W.
Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems.
Advances in Neural Information Processing Systems, 34:0 25294–25307, 2021.

[Chen et al., 2023]
Chen, X., Duan, J., Liang, Y., and Zhao, L.
Global convergence of two-timescale actor-critic for solving linear quadratic regulator.
In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp.  7087–7095, 2023.

[Chen et al., 2022]
Chen, Z., Khodadadian, S., and Maguluri, S. T.
Finite-sample analysis of off-policy natural actor–critic with linear function approximation.
IEEE Control Systems Letters, 6:0 2611–2616, 2022.

[Dalal et al., 2018]
Dalal, G., Szörényi, B., Thoppe, G., and Mannor, S.
Finite sample analysis of two-timescale stochastic approximation with applications to reinforcement learning.
Proceedings of Machine Learning Research, 75:0 1–35, 2018.

[Du et al., 2019]
Du, S., Lee, J., Li, H., Wang, L., and Zhai, X.
Gradient descent finds global minima of deep neural networks.
In International conference on machine learning, pp.  1675–1685. PMLR, 2019.

[Gordon, 1996]
Gordon, G. J.
Chattering in SARSA ($\lambda$).
CMU Learning Lab Technical Report, 1996.

[Gupta et al., 2019]
Gupta, H., Srikant, R., and Ying, L.
Finite-time performance bounds and adaptive learning rate selection for two time-scale reinforcement learning.
In Proc. Advances in Neural Information Processing Systems (NeurIPS), pp.  4706–4715, 2019.

[Heidergott & Hordijk, 2003]
Heidergott, B. and Hordijk, A.
Taylor series expansions for stationary markov chains.
Advances in Applied Probability, 350 (4):0 1046–1070, 2003.

[Kakade, 2001]
Kakade, S. M.
A natural policy gradient.
In Proc. Advances in Neural Information Processing Systems (NIPS), volume 14, pp.  1531–1538, 2001.

[Kaledin et al., 2020]
Kaledin, M., Moulines, E., Naumov, A., Tadic, V., and Wai, H.-T.
Finite time analysis of linear two-timescale stochastic approximation with Markovian noise.
In Proc. Annual Conference on Learning Theory (CoLT), pp.  2144–2203, 2020.

[Khodadadian et al., 2021]
Khodadadian, S., Chen, Z., and Maguluri, S. T.
Finite-sample analysis of off-policy natural actor-critic algorithm.
In International Conference on Machine Learning, pp.  5420–5431. PMLR, 2021.

[Khodadadian et al., 2022]
Khodadadian, S., Doan, T. T., Romberg, J., and Maguluri, S. T.
Finite sample analysis of two-time-scale natural actor-critic algorithm.
IEEE Transactions on Automatic Control, 2022.

[Konda & Tsitsiklis, 2003]
Konda, V. R. and Tsitsiklis, J. N.
On actor-critic algorithms.
SIAM Journal on Control and Optimization, 420 (4):0 1143–1166, 2003.

[Kumar et al., 2023]
Kumar, H., Koppel, A., and Ribeiro, A.
On the sample complexity of actor-critic method for reinforcement learning with function approximation.
Machine Learning, pp.  1–35, 2023.

[Lakshminarayanan & Szepesvari, 2018]
Lakshminarayanan, C. and Szepesvari, C.
Linear stochastic approximation: How far does constant step-size and iterate averaging go?
In Proc. International Conference on Artificial Intelligence and Statistics, pp.  1347–1355, 2018.

[Laroche & des Combes, 2021]
Laroche, R. and des Combes, R. T.
Dr jekyll & mr hyde: the strange case of off-policy policy updates.
In Proc. Advances in Neural Information Processing Systems (NeurIPS), 2021.

[Li et al., 2021]
Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y.
Softmax policy gradient methods can take exponential time to converge.
arXiv preprint arXiv:2102.11270, 2021a.

[Li et al., 2021]
Li, T., Guan, Z., Zou, S., Xu, T., Liang, Y., and Lan, G.
Faster algorithm and sharper analysis for constrained markov decision process.
arXiv preprint arXiv:2110.10351, 2021b.

[Lin, 2022]
Lin, X.
On the convergence rates of policy gradient methods.
arXiv preprint arXiv:2201.07443, 2022.

[Liu et al., 2015]
Liu, B., Liu, J., Ghavamzadeh, M., Mahadevan, S., and Petrik, M.
Finite-sample analysis of proximal gradient td algorithms.
In Proc. International Conference on Uncertainty in Artificial Intelligence (UAI), pp.  504–513, 2015.

[Ma et al., 2020]
Ma, S., Zhou, Y., and Zou, S.
Variance-reduced off-policy TDC learning: Non-asymptotic convergence analysis.
In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 33, pp.  14796–14806, 2020.

[Ma et al., 2021]
Ma, S., Chen, Z., Zhou, Y., and Zou, S.
Greedy-gq with variance reduction: Finite-time analysis and improved complexity.
In Proc. International Conference on Learning Representations (ICLR), 2021.

[Mei et al., 2020]
Mei, J., Xiao, C., Szepesvari, C., and Schuurmans, D.
On the global convergence rates of softmax policy gradient methods.
In Proc. International Conference on Machine Learning (ICML), pp.  6820–6829, 2020.

[Miyato et al., 2018]
Miyato, T., Kataoka, T., Koyama, M., and Yoshida, Y.
Spectral normalization for generative adversarial networks.
In International Conference on Learning Representations, 2018.

[Neyshabur, 2017]
Neyshabur, B.
Implicit regularization in deep learning.
arXiv preprint arXiv:1709.01953, 2017.

[Olshevsky & Gharesifard, 2022]
Olshevsky, A. and Gharesifard, B.
A small gain analysis of single timescale actor critic.
arXiv preprint arXiv:2203.02591, 2022.

[Peters & Schaal, 2008]
Peters, J. and Schaal, S.
Natural actor-critic.
Neurocomputing, 710 (7-9):0 1180–1190, 2008.

[Qiu et al., 2021]
Qiu, S., Yang, Z., Ye, J., and Wang, Z.
On finite-time convergence of actor-critic algorithm.
IEEE Journal on Selected Areas in Information Theory, 20 (2):0 652–664, 2021.

[Srikant & Ying, 2019]
Srikant, R. and Ying, L.
Finite-time error bounds for linear stochastic approximation and TD learning.
In Proc. Annual Conference on Learning Theory (CoLT), pp.  2803–2830, Jun. 2019.

[Sun et al., 2019]
Sun, J., Wang, G., Giannakis, G. B., Yang, Q., and Yang, Z.
Finite-sample analysis of decentralized temporal-difference learning with linear function approximation.
arXiv preprint arXiv:1911.00934, 2019.

[Suttle et al., 2023]
Suttle, W. A., Bedi, A., Patel, B., Sadler, B. M., Koppel, A., and Manocha, D.
Beyond exponentially fast mixing in average-reward reinforcement learning via multi-level monte carlo actor-critic.
In International Conference on Machine Learning, pp.  33240–33267. PMLR, 2023.

[Sutton, 1988]
Sutton, R. S.
Learning to predict by the methods of temporal differences.
Machine learning, 30 (1):0 9–44, 1988.

[Sutton, 1995]
Sutton, R. S.
Generalization in reinforcement learning: Successful examples using sparse coarse coding.
Advances in neural information processing systems, 8, 1995.

[Sutton et al., 1999]
Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y.
Policy gradient methods for reinforcement learning with function approximation.
Advances in neural information processing systems, 12, 1999.

[Tsitsiklis & Van Roy, 1999]
Tsitsiklis, J. N. and Van Roy, B.
Average cost temporal-difference learning.
Automatica, 350 (11):0 1799–1808, 1999.

[Wang et al., 2019]
Wang, L., Cai, Q., Yang, Z., and Wang, Z.
Neural policy gradient methods: Global optimality and rates of convergence.
arXiv preprint arXiv:1909.01150, 2019.

[Wang & Zou, 2020]
Wang, Y. and Zou, S.
Finite-sample analysis of Greedy-GQ with linear function approximation under Markovian noise.
In Proc. International Conference on Uncertainty in Artificial Intelligence (UAI), volume 124, pp.  11–20, 2020.

[Wang et al., 2017]
Wang, Y., Chen, W., Liu, Y., Ma, Z.-M., and Liu, T.-Y.
Finite sample analysis of the gtd policy evaluation algorithms in Markov setting.
In Proc. Advances in Neural Information Processing Systems (NIPS), pp.  5504–5513, 2017.

[Wang et al., 2021]
Wang, Y., Zou, S., and Zhou, Y.
Non-asymptotic analysis for two time-scale tdc with general smooth function approximation.
Advances in Neural Information Processing Systems, 34:0 9747–9758, 2021.

[Watkins & Dayan, 1992]
Watkins, C. J. and Dayan, P.
Machine learning, 80 (3-4):0 279–292, 1992.

[Wu et al., 2020]
Wu, Y. F., Zhang, W., Xu, P., and Gu, Q.
A finite-time analysis of two time-scale actor-critic methods.
Advances in Neural Information Processing Systems, 33:0 17617–17628, 2020.

[Xu & Gu, 2020]
Xu, P. and Gu, Q.
A finite-time analysis of Q-learning with neural network function approximation.
In Proc. International Conference on Machine Learning (ICML), pp.  10555–10565, 2020.

[Xu et al., 2019]
Xu, T., Zou, S., and Liang, Y.
Two time-scale off-policy TD learning: Non-asymptotic analysis over Markovian samples.
In Proc. Advances in Neural Information Processing Systems (NeurIPS), pp.  10633–10643, 2019.

[Xu et al., 2020]
Xu, T., Wang, Z., and Liang, Y.
Improving sample complexity bounds for (natural) actor-critic algorithms.
In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020a.

[Xu et al., 2020]
Xu, T., Wang, Z., and Liang, Y.
Non-asymptotic convergence analysis of two time-scale (natural) actor-critic algorithms.
arXiv preprint arXiv:2005.03557, 2020b.

[Zhang et al., 2020]
Zhang, J., Koppel, A., Bedi, A. S., Szepesvari, C., and Wang, M.
Variational policy gradient method for reinforcement learning with general utilities.
In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 33, pp.  4572–4583, 2020a.

[Zhang et al., 2020]
Zhang, S., Liu, B., Yao, H., and Whiteson, S.
Provably convergent two-timescale off-policy actor-critic with function approximation.
In International Conference on Machine Learning, pp.  11204–11213. PMLR, 2020b.

[Zhang et al., 2021]
Zhang, S., Tachet, R., and Laroche, R.
Global optimality and finite sample analysis of softmax off-policy actor critic under state distribution mismatch.
arXiv preprint arXiv:2111.02997, 2021.

[Zhou & Lu, 2022]
Zhou, M. and Lu, J.
Single time-scale actor-critic method to solve the linear quadratic regulator with convergence guarantees.
arXiv preprint arXiv:2202.00048, 2022.

[Zou et al., 2019]
Zou, S., Xu, T., and Liang, Y.
Finite-sample analysis for SARSA with linear function approximation.
In Proc. Advances in Neural Information Processing Systems (NeurIPS), pp.  8665–8675, 2019.

§ IMPACT STATEMENT
This paper presents work whose goal is to advance the field of Reinforcement Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.

§ ACKNOWLEDGMENTS

The work of Yudan Wang and Shaofeng Zou is supported by the National Science Foundation under Grants CCF-2007783, CCF-2106560 and ECCS-2337375 (CAREER). Yi Zhou’s work is supported by the National Science Foundation under grants CCF-2106216, DMS-2134223, ECCS-2237830 (CAREER).

This material is based upon work supported under the AI Research Institutes program by National Science Foundation and the Institute of Education Sciences, U.S. Department of Education through Award # 2229873 - National AI Institute for Exceptional Education. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation, the Institute of Education Sciences, or the U.S. Department of Education.

[Agarwal et al., 2021]
Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G.
On the theory of policy gradient methods: Optimality, approximation, and distribution shift.
The Journal of Machine Learning Research, 220 (1):0 4431–4506, 2021.

[Baird, 1995]
Baird, L.
Residual algorithms: Reinforcement learning with function approximation.
In Machine Learning Proceedings, pp.  30–37. Elsevier, 1995.

[Barakat et al., 2022]
Barakat, A., Bianchi, P., and Lehmann, J.
Analysis of a target-based actor-critic algorithm with linear function approximation.
In International Conference on Artificial Intelligence and Statistics, pp.  991–1040. PMLR, 2022.

[Barto et al., 1983]
Barto, A. G., Sutton, R. S., and Anderson, C. W.
Neuronlike adaptive elements that can solve difficult learning control problems.
IEEE Transactions on Systems, Man, and Cybernetics, SMC-130 (5):0 834–846, 1983.

[Bhandari & Russo, 2019]
Bhandari, J. and Russo, D.
Global optimality guarantees for policy gradient methods.
arXiv e-prints, pp.  arXiv–1906, 2019.

[Bhandari & Russo, 2021]
Bhandari, J. and Russo, D.
On the linear convergence of policy gradient methods for finite MDPs.
In Proc. International Conference on Artifical Intelligence and Statistics (AISTATS), pp.  2386–2394. PMLR, 2021.

[Bhandari et al., 2018]
Bhandari, J., Russo, D., and Singal, R.
A finite time analysis of temporal difference learning with linear function approximation.
In Proc. Annual Conference on Learning Theory (CoLT), pp.  1691–1692, 2018.

[Bhatnagar et al., 2009]
Bhatnagar, S., Sutton, R. S., Ghavamzadeh, M., and Lee, M.
Natural actor–critic algorithms.
Automatica, 450 (11):0 2471–2482, 2009.

[Cai et al., 2019]
Cai, Q., Yang, Z., Lee, J. D., and Wang, Z.
Neural temporal-difference learning converges to global optima.
In Proc. Advances in Neural Information Processing Systems (NeurIPS), pp.  11312–11322, 2019.

[Cayci et al., 2022]
Cayci, S., He, N., and Srikant, R.
Finite-time analysis of entropy-regularized neural natural actor-critic algorithm.
arXiv preprint arXiv:2206.00833, 2022.

[Cen et al., 2021]
Cen, S., Cheng, C., Chen, Y., Wei, Y., and Chi, Y.
Fast global convergence of natural policy gradient methods with entropy regularization.
Operations Research, 2021.

[Chen et al., 2021]
Chen, T., Sun, Y., and Yin, W.
Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems.
Advances in Neural Information Processing Systems, 34:0 25294–25307, 2021.

[Chen et al., 2023]
Chen, X., Duan, J., Liang, Y., and Zhao, L.
Global convergence of two-timescale actor-critic for solving linear quadratic regulator.
In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp.  7087–7095, 2023.

[Chen et al., 2022]
Chen, Z., Khodadadian, S., and Maguluri, S. T.
Finite-sample analysis of off-policy natural actor–critic with linear function approximation.
IEEE Control Systems Letters, 6:0 2611–2616, 2022.

[Dalal et al., 2018]
Dalal, G., Szörényi, B., Thoppe, G., and Mannor, S.
Finite sample analysis of two-timescale stochastic approximation with applications to reinforcement learning.
Proceedings of Machine Learning Research, 75:0 1–35, 2018.

[Du et al., 2019]
Du, S., Lee, J., Li, H., Wang, L., and Zhai, X.
Gradient descent finds global minima of deep neural networks.
In International conference on machine learning, pp.  1675–1685. PMLR, 2019.

[Gordon, 1996]
Gordon, G. J.
Chattering in SARSA ($\lambda$).
CMU Learning Lab Technical Report, 1996.

[Gupta et al., 2019]
Gupta, H., Srikant, R., and Ying, L.
Finite-time performance bounds and adaptive learning rate selection for two time-scale reinforcement learning.
In Proc. Advances in Neural Information Processing Systems (NeurIPS), pp.  4706–4715, 2019.

[Heidergott & Hordijk, 2003]
Heidergott, B. and Hordijk, A.
Taylor series expansions for stationary markov chains.
Advances in Applied Probability, 350 (4):0 1046–1070, 2003.

[Kakade, 2001]
Kakade, S. M.
A natural policy gradient.
In Proc. Advances in Neural Information Processing Systems (NIPS), volume 14, pp.  1531–1538, 2001.

[Kaledin et al., 2020]
Kaledin, M., Moulines, E., Naumov, A., Tadic, V., and Wai, H.-T.
Finite time analysis of linear two-timescale stochastic approximation with Markovian noise.
In Proc. Annual Conference on Learning Theory (CoLT), pp.  2144–2203, 2020.

[Khodadadian et al., 2021]
Khodadadian, S., Chen, Z., and Maguluri, S. T.
Finite-sample analysis of off-policy natural actor-critic algorithm.
In International Conference on Machine Learning, pp.  5420–5431. PMLR, 2021.

[Khodadadian et al., 2022]
Khodadadian, S., Doan, T. T., Romberg, J., and Maguluri, S. T.
Finite sample analysis of two-time-scale natural actor-critic algorithm.
IEEE Transactions on Automatic Control, 2022.

[Konda & Tsitsiklis, 2003]
Konda, V. R. and Tsitsiklis, J. N.
On actor-critic algorithms.
SIAM Journal on Control and Optimization, 420 (4):0 1143–1166, 2003.

[Kumar et al., 2023]
Kumar, H., Koppel, A., and Ribeiro, A.
On the sample complexity of actor-critic method for reinforcement learning with function approximation.
Machine Learning, pp.  1–35, 2023.

[Lakshminarayanan & Szepesvari, 2018]
Lakshminarayanan, C. and Szepesvari, C.
Linear stochastic approximation: How far does constant step-size and iterate averaging go?
In Proc. International Conference on Artificial Intelligence and Statistics, pp.  1347–1355, 2018.

[Laroche & des Combes, 2021]
Laroche, R. and des Combes, R. T.
Dr jekyll & mr hyde: the strange case of off-policy policy updates.
In Proc. Advances in Neural Information Processing Systems (NeurIPS), 2021.

[Li et al., 2021]
Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y.
Softmax policy gradient methods can take exponential time to converge.
arXiv preprint arXiv:2102.11270, 2021a.

[Li et al., 2021]
Li, T., Guan, Z., Zou, S., Xu, T., Liang, Y., and Lan, G.
Faster algorithm and sharper analysis for constrained markov decision process.
arXiv preprint arXiv:2110.10351, 2021b.

[Lin, 2022]
Lin, X.
On the convergence rates of policy gradient methods.
arXiv preprint arXiv:2201.07443, 2022.

[Liu et al., 2015]
Liu, B., Liu, J., Ghavamzadeh, M., Mahadevan, S., and Petrik, M.
Finite-sample analysis of proximal gradient td algorithms.
In Proc. International Conference on Uncertainty in Artificial Intelligence (UAI), pp.  504–513, 2015.

[Ma et al., 2020]
Ma, S., Zhou, Y., and Zou, S.
Variance-reduced off-policy TDC learning: Non-asymptotic convergence analysis.
In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 33, pp.  14796–14806, 2020.

[Ma et al., 2021]
Ma, S., Chen, Z., Zhou, Y., and Zou, S.
Greedy-gq with variance reduction: Finite-time analysis and improved complexity.
In Proc. International Conference on Learning Representations (ICLR), 2021.

[Mei et al., 2020]
Mei, J., Xiao, C., Szepesvari, C., and Schuurmans, D.
On the global convergence rates of softmax policy gradient methods.
In Proc. International Conference on Machine Learning (ICML), pp.  6820–6829, 2020.

[Miyato et al., 2018]
Miyato, T., Kataoka, T., Koyama, M., and Yoshida, Y.
Spectral normalization for generative adversarial networks.
In International Conference on Learning Representations, 2018.

[Neyshabur, 2017]
Neyshabur, B.
Implicit regularization in deep learning.
arXiv preprint arXiv:1709.01953, 2017.

[Olshevsky & Gharesifard, 2022]
Olshevsky, A. and Gharesifard, B.
A small gain analysis of single timescale actor critic.
arXiv preprint arXiv:2203.02591, 2022.

[Peters & Schaal, 2008]
Peters, J. and Schaal, S.
Natural actor-critic.
Neurocomputing, 710 (7-9):0 1180–1190, 2008.

[Qiu et al., 2021]
Qiu, S., Yang, Z., Ye, J., and Wang, Z.
On finite-time convergence of actor-critic algorithm.
IEEE Journal on Selected Areas in Information Theory, 20 (2):0 652–664, 2021.

[Srikant & Ying, 2019]
Srikant, R. and Ying, L.
Finite-time error bounds for linear stochastic approximation and TD learning.
In Proc. Annual Conference on Learning Theory (CoLT), pp.  2803–2830, Jun. 2019.

[Sun et al., 2019]
Sun, J., Wang, G., Giannakis, G. B., Yang, Q., and Yang, Z.
Finite-sample analysis of decentralized temporal-difference learning with linear function approximation.
arXiv preprint arXiv:1911.00934, 2019.

[Suttle et al., 2023]
Suttle, W. A., Bedi, A., Patel, B., Sadler, B. M., Koppel, A., and Manocha, D.
Beyond exponentially fast mixing in average-reward reinforcement learning via multi-level monte carlo actor-critic.
In International Conference on Machine Learning, pp.  33240–33267. PMLR, 2023.

[Sutton, 1988]
Sutton, R. S.
Learning to predict by the methods of temporal differences.
Machine learning, 30 (1):0 9–44, 1988.

[Sutton, 1995]
Sutton, R. S.
Generalization in reinforcement learning: Successful examples using sparse coarse coding.
Advances in neural information processing systems, 8, 1995.

[Sutton et al., 1999]
Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y.
Policy gradient methods for reinforcement learning with function approximation.
Advances in neural information processing systems, 12, 1999.

[Tsitsiklis & Van Roy, 1999]
Tsitsiklis, J. N. and Van Roy, B.
Average cost temporal-difference learning.
Automatica, 350 (11):0 1799–1808, 1999.

[Wang et al., 2019]
Wang, L., Cai, Q., Yang, Z., and Wang, Z.
Neural policy gradient methods: Global optimality and rates of convergence.
arXiv preprint arXiv:1909.01150, 2019.

[Wang & Zou, 2020]
Wang, Y. and Zou, S.
Finite-sample analysis of Greedy-GQ with linear function approximation under Markovian noise.
In Proc. International Conference on Uncertainty in Artificial Intelligence (UAI), volume 124, pp.  11–20, 2020.

[Wang et al., 2017]
Wang, Y., Chen, W., Liu, Y., Ma, Z.-M., and Liu, T.-Y.
Finite sample analysis of the gtd policy evaluation algorithms in Markov setting.
In Proc. Advances in Neural Information Processing Systems (NIPS), pp.  5504–5513, 2017.

[Wang et al., 2021]
Wang, Y., Zou, S., and Zhou, Y.
Non-asymptotic analysis for two time-scale tdc with general smooth function approximation.
Advances in Neural Information Processing Systems, 34:0 9747–9758, 2021.

[Watkins & Dayan, 1992]
Watkins, C. J. and Dayan, P.
Machine learning, 80 (3-4):0 279–292, 1992.

[Wu et al., 2020]
Wu, Y. F., Zhang, W., Xu, P., and Gu, Q.
A finite-time analysis of two time-scale actor-critic methods.
Advances in Neural Information Processing Systems, 33:0 17617–17628, 2020.

[Xu & Gu, 2020]
Xu, P. and Gu, Q.
A finite-time analysis of Q-learning with neural network function approximation.
In Proc. International Conference on Machine Learning (ICML), pp.  10555–10565, 2020.

[Xu et al., 2019]
Xu, T., Zou, S., and Liang, Y.
Two time-scale off-policy TD learning: Non-asymptotic analysis over Markovian samples.
In Proc. Advances in Neural Information Processing Systems (NeurIPS), pp.  10633–10643, 2019.

[Xu et al., 2020]
Xu, T., Wang, Z., and Liang, Y.
Improving sample complexity bounds for (natural) actor-critic algorithms.
In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020a.

[Xu et al., 2020]
Xu, T., Wang, Z., and Liang, Y.
Non-asymptotic convergence analysis of two time-scale (natural) actor-critic algorithms.
arXiv preprint arXiv:2005.03557, 2020b.

[Zhang et al., 2020]
Zhang, J., Koppel, A., Bedi, A. S., Szepesvari, C., and Wang, M.
Variational policy gradient method for reinforcement learning with general utilities.
In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 33, pp.  4572–4583, 2020a.

[Zhang et al., 2020]
Zhang, S., Liu, B., Yao, H., and Whiteson, S.
Provably convergent two-timescale off-policy actor-critic with function approximation.
In International Conference on Machine Learning, pp.  11204–11213. PMLR, 2020b.

[Zhang et al., 2021]
Zhang, S., Tachet, R., and Laroche, R.
Global optimality and finite sample analysis of softmax off-policy actor critic under state distribution mismatch.
arXiv preprint arXiv:2111.02997, 2021.

[Zhou & Lu, 2022]
Zhou, M. and Lu, J.
Single time-scale actor-critic method to solve the linear quadratic regulator with convergence guarantees.
arXiv preprint arXiv:2202.00048, 2022.

[Zou et al., 2019]
Zou, S., Xu, T., and Liang, Y.
Finite-sample analysis for SARSA with linear function approximation.
In Proc. Advances in Neural Information Processing Systems (NeurIPS), pp.  8665–8675, 2019.

§ SUPPORTING LEMMAS AND PROOFS FOR  <REF>

In this section, we provide a number of supporting lemmas, and proofs for <Ref>. In the following proofs, $\|x\|_2$ denotes the $\ell_2$ norm if $x$ is a vector; and $\|X\|_2$ denotes the operator norm if $X$ is a matrix.

§.§ Supporting Lemmas

For convenience, we denote $J(\omega)=J(\pi_\omega)$. We first prove a lemma showing that both $J(\omega)$ and $\nabla J(\omega)$ are Lipschitz in $\omega$.

Under Assumptions  <ref> and <ref>, for any $\omega, \omega'\in\mathcal W$, we have that

where $C_J=   C^2_\phi \brac{B+ \frac{C_{\text{gap}} m \rho^k}{\lambda_{\min}}}$, and

∇J(ω)-∇J(ω')≤L_J ω-ω'
, where $L_J= \frac{m R_{\max}}{1-\rho}\brac{4L_\pi C_\phi+L_\phi}$ and
\frac{1}{2}C_\pi
\brac{1+\myceil{\log m^{-1}}+\frac{1}{1-\rho}}$.

Recall <Ref>. The solution $\bar \theta_\omega^*$ given the feature function satisfies that

We show that the solution $\bar \theta^*_\omega$ is   Lipschitz in $\omega$ in the following lemma.

For any  $\omega, \omega' \in\mathcal{W}$, it holds that

where $C_\Theta=\frac{C_J}{\lambda^2_{\min}}
\brac{2 C_\phi L_\phi+C^2_\phi L_\pi }+ \frac{L_J}{\lambda_{\min}}$.

For any $\omega\in \mathcal{W}$, let

\begin{align}\label{eq:aw}
H_{\omega}(s,a)&=\E\Fbrac{\phi_{\omega}(s_0,a_0)\brac{\phi_{\omega}(s_k,a_k)-\phi_{\omega}(s_0,a_0) }^\top |s_0=s,a_0=a,\pi_\omega},\nn\\
\end{align}

For $ k>\myceil{\frac{\log( md C^2_\phi)-\log \lambda_{\min} }{1-\rho}}$, it holds that

$$\lambda_{\max}\brac{\frac{H_\omega+H_\omega^\top}{2}}\leq C_\phi^2 d m\rho^k-\lambda_{\min}=-\bar \lambda_{\min}<0, $$

where $\lambda_{\max}\brac{X}$ is the largest eigenvalue of symmetric matrix $X$.

When $ k>\myceil{\frac{\log( md C^2_\phi)-\log \lambda_{\min} }{1-\rho}}$, we have that

λ̅_min   =λ_min-C_ϕ^2 d mρ^k

> λ_min-C_ϕ^2 d m e^-k(1-ρ)

≥λ_min-C_ϕ^2 d m e^-logmdC^2_ϕ/λ_min=0,

and therefore $\bar \lambda_{\min}$ is positive.

The following lemma bounds the distance between the stationary distribution induced by $\pi_t$ and the distribution of $s_t,a_t$ in <Ref>. Define $\mathcal{F}_j$ to be $\sigma$-field generated by all the randomness until the $j$-th time-step. For simplicity, we write $D_{\pi_t}$ as $D_t$.

For any $0\leq k\leq t$, it can be shown that

s_t,a_t|ℱ_t-k-D_t≤C_π∑_j=t-k^t-1 ω_t-ω_j+ mρ^k.

We rewrite $\thestar=\theta^*_{\omega_t} $, where $\theta^*_{\omega}$ is the solution to <Ref>.

Consider the term $\E \fvbrac{\theta_t-\thestar, \delta_t z_t} $. It can be shown that

θ_t-, δ_t z_t
≤    - λ̅_min/2 θ_t-

+(k+1)^2 C^2_ϕ/2λ̅_minJ(ω_t)-η_t+G^δ_t

where $U_\delta =R_{\max}+2 C_\phi B$. For AC,

G^δ_t    =2B^2 C^2_ϕU_δC_π∑_j=t-k^t ∑_i=j^t-1 β_i
+4  B C_ϕU_δ∑_j=t-k^t
B C^2_ϕC_π∑_i=j-k^j-1 ∑_ι=i^j-1 β_ι+ mρ^k+ BC^2_ϕL_π∑_i=j^t-1 β_i

+  2(k+1) C_ϕU_δ(k+1) C_ϕU_δ∑_j=t-2k^t-1 α_j+ C_ΘC^2_ϕB ∑_j=t-2k^t-1 β_j+2C_gapm ρ^k/λ_min,

and for NAC,

G^δ_t    =2B^2 U_δC_π∑_j=t-k^t ∑_i=j^t-1 β_i+4  B C_ϕU_δ∑_j=t-k^t
B C_π∑_i=j-k^j-1 ∑_ι=i^j-1 β_ι+ mρ^k+B L_π∑_i=j^t-1 β_i

+2(k+1) C_ϕU_δ(k+1) C_ϕU_δ∑_j=t-2k^t-1 α_j+ C_ΘB ∑_j=t-2k^t-1 β_j+2C_gapm ρ^k/λ_min

In the following, we prove that $\theta^*_\omega$ defined in
<Ref>  is bounded.

The solution $\theta^*_\omega$ to <Ref>  is bounded:

\begin{align}
\|\theta^*_\omega\|_2\leq \frac{1}{\lambda_{\min}-d C_\phi^2 m \rho^k }\frac{m C_\phi R_{\max}}{1-\rho}=\frac{m C_\phi R_{\max}}{\bar \lambda_{\min}\brac{1-\rho}}.
\end{align}

Under Assumption <ref> and <ref>, for any  $\omega, \omega'\in\mathcal{W}$,

∇^2 J(ω)-∇^2J(ω')≤L_Θω-ω',

where $L_\Theta= d^2 \brac{ \frac{6 C^3_\phi m^3 e^{4R_{\max}}}{(1-\rho)^3}+\frac{6 m^2 C_\phi C_\delta e^{3R_{\max}}}{(1-\rho)^2}+\frac{m L_\delta e^{2R_{\max}}}{1-\rho}}$.

The proof of above Lemmas could be found in <Ref>.

§.§ Proofs for <Ref>

We include the proof of <Ref> and <Ref> for completeness.

By the <Ref>, $\bar \theta^*_\omega$ satisfies that

_D_π_ω(Q^π_ω(s,a)-ϕ^⊤_ω(s,a)θ̅_ω^*)ϕ_ω(s,a) =0.

Since $ \phi_\omega^\top(s,a) \bar\theta^*_\omega$ is a scalar, we can get that

_D_π_ωQ^π_ω(s,a)ϕ_ω(s,a) =_D_π_ωϕ_ω(s,a)ϕ^⊤_ω(s,a)θ̅_ω^*

For the policy gradient $\nabla J(\pi_\omega)$, we get that

∇J(π_ω) =_D_π_ω ∇logπ_ω(a|s)Q^π_ω(s,a)=

Furthermore, we have that

\begin{align}
\widetilde{\nabla} J(\pi_\omega)&= F^{-1}_\omega
\E_{D_{\pi_\omega}}\Fbrac{\phi_\omega(s,a)\phi_\omega(s,a)^\top \bar \theta^*_\omega  }
\nn\\
\E_{D_{\pi_\omega}}\Fbrac{\phi_\omega(s,a)\phi_\omega(s,a)^\top   }\bar \theta^*_\omega=\bar \theta^*_\omega. \end{align}

This conclude the proof.

We present the proof of <Ref>.
(Restatement of <Ref>)

For any $\omega\in \mathcal{W}$ and $\theta \in \Theta$,
$\Phi_\omega \theta \neq \mathbf{e},$
where  $\mathbf e\in \mathbb R^{|\mathcal{S}||\mathcal{A}|}$ is an all-one vector.

Assume that there exists $\theta_c\in\Theta$ such that $\Phi_\omega \theta_c=\mathbf{e}$, then $\E_{D_{\pi_\omega}}\Fbrac{\phi_\omega^\top(s,a)\theta_c}=1$.

However, note that

_D_π_ωϕ_ω^⊤(s,a)θ_c   =
∑_sd_π_ω(s)∑_aπ_ω(a|s) ϕ_ω^⊤(s,a)θ_c

∑_sd_π_ω(s)∑_aπ_ω(a|s) ∇logπ_ω(a|s)^⊤θ_c

∑_sd_π_ω(s)∑_aπ_ω(a|s) ∇_ω π_ω(a|s)^⊤/π_ω(a|s)θ_c

∑_sd_π_ω(s)∑_a  ∇_ωπ_ω(a|s)^⊤θ_c

=∑_sd_π_ω(s)  ∇_ω(∑_a  π_ω(a|s) )^⊤θ_c

where the last equation is from the fact that $\sum_a \pi_\omega(a|s)=1$, and hence the gradient of it is $0$.
This hence results in a contradiction, which completes the proof.

We then present the proof of <Ref>.
(Restatement of <Ref>)
For any $\omega\in \mathcal{W}$, denote the fixed point of $k$-step TD operator by $\theta_{\omega}^*$, and the solution to <Ref> by $\bar{\theta}_{\omega}^*$, then

where $C_{\text{gap}}=C^2_\phi B  + \frac{C_\phi R_{\max}}{1-\rho}$.

From the definition, it holds that

Thus, we have that

≤ 1/λ_min

= 1/λ_min
∑_j=0^k-1 R_j-J(ω)+ϕ_ω(s_k,a_k)^⊤θ^*_ω|s_0=s,a_0=a, π_ω

= 1/λ_min
∑_j=0^k-1 R_j-J(ω)+ϕ_ω(s_k,a_k)^⊤θ^*_ω|s_0=s,a_0=a, π_ω

∑_j=0^∞R_j-J(ω)|s_0=s,a_0=a, π_ω

= 1/λ_min
∑_j=k^∞R_j-J(ω)+ϕ_ω(s_k,a_k)^⊤θ^*_ω | s_0=s,a_0=a, π_ω

ϕ_ω(s_k,a_k)^⊤θ^*_ω| (s_k,a_k)∼D_π_ω

C^2_ϕB _D_π_ωs_k,a_k|s_0=s,a_0=a,π_ω-D_π_ω

≤b 1/λ_min

ϕ_ω(s_k,a_k)^⊤θ^*_ω| (s_k,a_k)∼D_π_ω

C_ϕB m ρ^k +∑_j=k^∞R_max m ρ^j

C_ϕB m ρ^k +∑_j=k^∞R_max m ρ^j

1/λ_minC^2_ϕB m ρ^k + C_ϕR_maxm ρ^k/1-ρ

=  C_gapm ρ^k/λ_min,

where $C_{\text{gap}}= C^2_\phi B  + C_\phi R_{\max}\frac{1}{1-\rho}$, $(a)$ follows from the triangular inequality and the fact that for any probability distribution $P_1 $ and $P_2$, and any random variable $X$, s.t.
$\lbrac{X}\leq X_{\max}$,  $ \lbrac{\E_{P_1}\Fbrac{X}-\E_{P_2}\Fbrac{X}}\leq X_{\max} \tvnorm{ P_1-P_2}$, $(b)$ follows from Assumption <ref>, $(c)$ follows from $J(\omega)=\E _{D_{\pi_\omega}}[R(s,a)]$,  and $(d)$ follows from $\E_{D_{\pi_\omega}}\Fbrac{\phi_{\omega}(s,a)\brac{\E_{D_{\pi_\omega}}\Fbrac{
\phi_{\omega}(s,a)^\top \theta^*_{\omega}}}}=0 $.

§ AC SAMPLE COMPLEXITY ANALYSIS

In this section, we provide the sample complexity analysis for our single-loop AC algorithm.

§.§ Bound on Gradient Norm in AC

In this section, we first present a preliminary bound on the gradient norm $\|\nabla J(\omega)\|$.

It holds that

≤J(ω)- J(ω_t)
+C_ϕ^4 β_t θ_t-+ G^ω_t,

G^ω_t=   L_J C_ϕ^4 B^2 β_t^2/2 +C_ϕ^4 C^2_gapmρ^k/λ^2_min+C_J C^2_ϕBβ_t m ρ^k
+ 2 C^4_ϕB^2 L_J β_t∑_j=t-k^t-1 β_j

+ C_J C^4_ϕB^2C_πβ_t∑_j=t-k^t-1 ∑_i=j^t-1 β_i.

Recall that in the update of AC algorithm,  $\omega\tit-\omega_t=\beta_t\phi^\top_t(s_t,a_t)\theta_t\phi_t(s_t,a_t)$.  Following <Ref>, it can be shown that

J   (ω)≥J(ω_t)+ , ω-ω_t-L_J/2 ω-ω_t

= J(ω_t)+ β_t, ϕ_t^⊤(s_t,a_t)θ_tϕ_t(s_t,a_t)- L_Jβ_t^2/2 ϕ_t^⊤(s_t,a_t)θ_tϕ_t(s_t,a_t)

= J(ω_t)+ β_t, ϕ_t^⊤(s_t,a_t)θ_tϕ_t(s_t,a_t)

+β_t , _D_tϕ^⊤_t(s,a)
+β_t ,

+β_t , _D_tϕ_t^⊤(s,a)ϕ_t(s,a)-
- L_Jβ_t^2/2 ϕ_t^⊤(s_t,a_t)θ_tϕ_t(s_t,a_t)

≥J(ω_t)+ β_t, ϕ_t^⊤(s_t,a_t)θ_tϕ_t(s_t,a_t)

-β_t  _D_tϕ^⊤_t(s,a)

-β_t/4 -β_t  _D_tϕ_t^⊤(s,a)ϕ_t(s,a)-
- L_J C^4_ϕB^2/2 β_t^2

J(ω_t)+ β_t, ϕ_t^⊤(s_t,a_t)θ_tϕ_t(s_t,a_t)
-_D_tϕ^⊤_t(s,a)θ_tϕ_t(s,a)_part I

-β_t  _D_tϕ^⊤_t(s,a)
θ_t-ϕ_t(s,a)- L_J C^4_ϕB^2/2 β_t^2

-β_t  _D_tϕ_t^⊤(s,a)(-)ϕ_t(s,a),
where we write $ \bar \theta^*_{\omega_t}$ as $\thebar$ for convenience, $(a)$ follows from <Ref> that
$\nabla J(\omega_t)= \E_{D_t}\Fbrac{\phi_t^\top(s,a)\thebar\phi_t(s,a)} $.

We then bound part I in <Ref>. Note that

|   , ϕ_t^⊤(s_t,a_t)θ_tϕ_t(s_t,a_t)

≤-∇J(ω_t-k), ϕ_t^⊤(s_t,a_t)θ_tϕ_t(s_t,a_t)

+∇J(ω_t-k), ϕ_t^⊤(s_t,a_t)θ_tϕ_t(s_t,a_t)

≤-∇J(ω_t-k) ϕ_t^⊤(s_t,a_t) θ_tϕ_t(s_t,a_t)-_D_tϕ^⊤_t(s,a)θ_tϕ_t(s,a)

+  ∇^⊤J(ω_t-k) ϕ_t^⊤(s_t,a_t)θ_tϕ_t(s_t,a_t)

2 C^2_ϕB L_J ω_t-ω_t-k
+ C_J s_t,a_t|ℱ_t-k-D_t

≤b 2 C^4_ϕB^2 L_J ∑_j=t-k^t-1 β_j
+ C_J C^2_ϕBC_π∑_j=t-k^t-1 ω_t-ω_j+ mρ^k

≤2 C^4_ϕB^2 L_J ∑_j=t-k^t-1 β_j
+ C_J C^2_ϕBC_πC^2_ϕB ∑_j=t-k^t-1 ∑_i=j^t-1 β_i+ mρ^k ,
where $(a)$ is from the $L_J$-smoothness of $J$, and $(b)$ is from <Ref>.
On the other hand, from <Ref>, we can show that

≤C_ϕ^4 - ≤C_ϕ^4 C_gapmρ^k/λ_min^2.

Thus, combining <Ref>,<Ref> and <Ref> completes the proof,

J(ω)   ≥J(ω_t)
+ β_t/2
-L_J C_ϕ^4 B^2/2  β_t^2-C_ϕ^4 β_t θ_t-

C_ϕ^4 β_t C_gapmρ^k/λ_min^2
-2 C^4_ϕB^2 L_J β_t∑_j=t-k^t-1 β_j- C_J C^2_ϕBβ_tC_πC^2_ϕB ∑_j=t-k^t-1 ∑_i=j^t-1 β_i+ mρ^k .

§.§ Bound on $|\eta_t-J(\omega_t)|$ in AC

In this section, we bound the error between $\eta_t$ and $J(\omega_t)$, where $J(\omega_t)=\lim_{N\to\infty }\E\Fbrac{\frac{1}{N} \sum_{t=0}^{N-1}R_t|\pi_{\omega_t}}$ is the average-reward for policy $\pi_{\omega_t}$.

If $\gamma_t-\gamma^2_t\geq  {\beta_t} $, then it holds that

+C_ϕ^4 B^2 β_t+ G^η_t,

G^η_t    = 2γ_t R_max^2 C_πC^2_ϕB  ∑_j=t-k^t-1 ∑_i=j^t-1 β_j
+  R^2_max m ρ^k+ R_max^2 ∑_j=t-k^t-1γ_j
+ R_maxC_J C_ϕ^2 B β_t+  R_maxC_J C_ϕ^2 B ∑_j=t-k^t-1β_j

+ R_max^2 γ^2_t + C_J^2 C_ϕ^4 B^2 β_t^2
+ 2R_maxL_J C^4_ϕB^2 β_t^2.

Recall the update rule in <Ref>. Then  we have that

η-J(ω_t+1) =η_t+ γ_t R_t-η_t-J(ω_t)
+J(ω_t) -J(ω_t+1).

It then follows that

≤    1-γ_t^2η_t-J(ω_t)
+γ_t^2 R_t-J(ω_t) +J(ω_t)-J(ω_t+1)

+2   γ_tR_t-J(ω_t)J(ω_t)-J(ω_t+1)_I
+ 2γ_t1-γ_t
η_t-J(ω_t) R_t-J(ω_t)_II

+2   1-γ_t
η_t-J(ω_t) J(ω_t)-J(ω_t+1)_III.

The term $\brac{J(\omega_t)-J(\omega_{t+1})}^2$ can be bounded by <Ref>:

≤C_J C^2_ϕB β_t .

Term I in <Ref> can be bounded as follows:

≤R_maxC_J C_ϕ^2 B β_t.

Term II in <Ref> can be bounded as follows:

≤η_t-k-J(ω_t-k) R_t-J(ω_t)
+η_t-η_t-k-J(ω_t)+J(ω_t-k) R_t-J(ω_t)

≤a η_t-k-J(ω_t-k)R_t-J(ω_t)|ℱ_t-k-_D_tη_t-k-J(ω_t-k)R(s,a)-J(ω_t)

+  η_t-η_t-k-J(ω_t)+J(ω_t-k)R_t-J(ω_t)

≤b  R^2_maxℙs_t,a_t|ℱ_t-k,D_t
+ R_maxη_t-η_t-k +J(ω_t)-J(ω_t-k)

+ R_maxR_max∑_j=t-k^t-1γ_j+C_J ω_t-ω_t-k

≤R_max^2 C_πC^2_ϕB  ∑_j=t-k^t-1 ∑_i=j^t-1 β_j
+  R^2_max m ρ^k+ R_max^2∑_j=t-k^t-1γ_j
+  R_maxC_J C_ϕ^2 B∑_j=t-k^t-1β_j,

where $(a)$ follows from $\E_{D_t}\Fbrac{R(s,a)-J(\omega_t)}=0 $, $(b)$ follows from that $0\leq\eta_t\leq R_{\max}$, $0\leq J(\omega_t)\leq R_{\max}$,  $0\leq R_t\leq R_{\max}$ and

$(c)$ follows from  <Ref>.

Term III in <Ref> can be bounded as follows:

|    η_t-J(ω_t)J(ω_t)-J(ω_t+1)|

η_t-J(ω_t)∇^⊤J(ω_t) (ω-ω_t)

=β_t η_t-J(ω_t) ∇^⊤J(ω_t) (ϕ_t^⊤(s_t,a_t) θ_t ϕ_t(s_t,a_t))

β^2_tη_t-J(ω_t)ϕ_t^⊤(s_t,a_t) θ_t ϕ_t(s_t,a_t)^⊤∇^2J(ω̂_t)/2ϕ_t^⊤(s_t,a_t) θ_t ϕ_t(s_t,a_t)

+ R_maxL_J C^4_ϕB^2 β_t^2 ,

where $(a)$ follows from the Lagrange's Mean Value Theorem and <Ref>
for some $ \hat \omega_t=\lambda \omega_t+(1-\lambda)\omega_{t+1}$ with $\lambda\in [0,1]$;
$(b)$ follows from $\langle a, b\rangle \leq \frac{\|a\|^2+\|b\|^2}{2}$ and <Ref>.

Combining <Ref>, <Ref>, <Ref> and <Ref> implies

≤(1-γ_t)^2+ β_tη_t-J(ω_t)
+β_t C_ϕ^4 B^2

+ 2 γ_t R_max^2 C_πC^2_ϕB  ∑_j=t-k^t-1 ∑_i=j^t-1 β_i
+  R^2_max m ρ^k+ R_max^2∑_j=t-k^t-1γ_j
+ R_maxC_J C_ϕ^2 B β_t

+ R_max^2 γ^2_t + C_J^2 C_ϕ^4 B^2 β_t^2
+ 2  R_maxC_J C_ϕ^2 B γ_t∑_j=t-k^t-1β_j
+ 2 R_maxL_J C^4_ϕB^2 β_t^2,

which completes the proof.

§.§ Tracking Error Analysis of AC

In this section, we bound the tracking error $\|\theta_t-\thestar\|_2$.
Recall that we write $\theta^*_t=\theta^*_{\omega_t} $ and
$ \theta^*_\omega $ is the solution to <Ref>, i.e.,

ϕ_ω^⊤(s,a)𝒯_π_ω^(k) ϕ^⊤_ω(s,a) θ^*_ω -ϕ^⊤_ω(s,a) θ^*_ω

We then present a recursive bound on the tracking error in the following lemma.

Set the step sizes such that

λ̅_min α_t/2≥B C^3_ϕC_ϕL_π+2L_ϕ+λ_min(L_J+ 2 C_ϕ)+2λ^2_min/λ^2_minβ_t, then it holds that

+L_Jλ_min+B C^3_ϕC_ϕL_π+2L_ϕ/λ^2_minβ_t

+ (k+1)^2C^2_ϕ/λ̅_minα_t η_t-J(ω_t)

G^θ_t   = (k+1)^2 U_δ^2 C^2_ϕα_t^2+ 4(k+1) B C^3_ϕU_δL_J/λ_minβ_t∑_j=t-k^t-1α_t
+2(k+1) C^3_ϕB U_δC_Θα_tβ_t

+ 2B C_ϕL_J(C_ϕL_π+2L_ϕ)+ 2 B L_Θλ_min+ C_Θλ_min  4 B^2 C^4_ϕ/λ^2_minβ_t∑_j=t-k^t β_j+ 2 C^4_ϕB^2 C_Θ^2 β_t^2

+4B C^2_ϕL_J  3 C_gap+  λ_min /λ^2_min m ρ^kβ_t  + 4(k+1) C_ϕU_δC_gapmρ^k/λ_minα_t+2/β_t+8C_gapmρ^k/λ_min ^2

+4B^3 C_πC^4_ϕL_J/λ_minβ_t ∑_j=t-k^t-1 ∑_i=j^t-1 β_i+ 2 α_t G^δ_t.

From <Ref>, it holds that

θ-   =
Π_Bθ_t+α_t δ_t z_t-

≤a θ_t+α_t δ_t z_t-

= θ_t+α_t δ_t z_t-+-

= θ_t-+ α_t^2 δ_t z_t+ -
+ 2 α_tθ_t-, δ_t z_t

+ 2α_t δ_t z_t, -
+ 2 θ_t-, -,

where $(a)$ follows from the fact $\twonorm{\Pi_B(x)-y}\leq \twonorm{x-y} $ when $\twonorm{y}\leq B $ and $\twonorm{\theta^*_{t+1}}\leq B$.

Taking expectations on both sides further implies that

θ-  ≤θ_t-+ α_t^2 δ_t z_t+ -

+ 2 α_tθ_t-, δ_t z_t_I
+ 2α_t δ_t z_t, -_II
+ 2 θ_t-, -_III.

Firstly, we can get that

α_t^2 δ_t z_t≤α_t^2 (k+1)^2 C_ϕ^2 U^2_δ.

The term $\twonorm{\thestar-\thestara}$ can be bounded as follows:

=-+ --+

≤-+ -+ -

≤a -+C_gapmρ^k/λ_min
+C_gap mρ^k/λ_min

≤b C_Θω_t-ω+2C_gapmρ^k/λ_min

= β_t C_Θϕ_t^⊤(s_t,a_t)θ_t ϕ_t(s_t,a_t)  +2C_gapmρ^k/λ_min

≤C_ΘC_ϕ^2 B β_t+2C_gapmρ^k/λ_min,

where $(a)$ follows from <Ref>; and $(b)$ follows from Lemma <ref>.
<Ref> further implies that

≤2C^2_ΘC_ϕ^4 B^2 β^2_t+8 C^2_gapm^2ρ^2k/λ^2_min.

By Lemma <ref>, we can bound  term I in <Ref> as follows:

θ_t-, δ_t z_t
≤- λ̅_min/2 θ_t-
+(k+1)^2 C^2_ϕ/2λ̅_minJ(ω_t)-η_t+G^δ_t.

For term II in <Ref>, we have that

δ_t z_t, -
≤δ_t z_t  -

≤δ_t z_t   -+ -+ -

≤(k+1) C_ϕU_δC_ΘC_ϕ^2 B β_t+2C_gapmρ^k/λ_min

= (k+1) C^3_ϕB U_δC_Θβ_t
+ 2(k+1) C_ϕU_δC_gapmρ^k/λ_min,

where the last inequality is from <Ref> and <Ref>.

To convenience, we rewrite $F_t=F_{\omega_t}$. To bound term III in <Ref>, note that

θ_t-, -

= θ_t-, - +θ_t-, -
+θ_t-, -

≤θ_t-, F_t^-1-F_t+1^-1∇J(ω_t+1)
+β_t/2  θ_t-
+1/2β_t  -

+β_t/2  θ_t-
+1/2β_t  -

≤a θ_t-,F_t+1^-1∇J(ω_t)-∇J(ω_t+1) +θ_t-, F_t^-1-F^-1_t+1

+β_t θ_t- +1/β_tC_gapmρ^k/λ_min ^2

=b θ_t-,F_t+1^-1∇^2 J(ω̂_t)ω_t-ω_t+1 +θ_t-, F_t^-1-F^-1_t+1

+β_t θ_t- +1/β_tC_gapmρ^k/λ_min ^2

≤c θ_t-,F_t+1^-1∇^2 J(ω̂_t)ω_t-ω_t+1 +1/λ_min^2θ_t-F_t-F_t+1

+β_t θ_t- +1/β_tC_gapmρ^k/λ_min ^2

≤d-β_tθ_t-,F_t+1^-1∇^2 J(ω̂_t)ϕ_t^⊤(s_t,a_t)θ_tϕ_t(s_t,a_t)
+B C^3_ϕC_ϕL_π+2L_ϕ/2λ^2_minβ_tθ_t-

+ B C^3_ϕC_ϕL_π+2L_ϕ/2λ^2_minβ_t+β_t θ_t- +1/β_tC_gapmρ^k/λ_min ^2

=-β_tθ_t-,F_t+1^-1∇^2 J(ω̂_t)_D_tϕ_t^⊤(s,a)ϕ_t(s,a)  _(i)

-β_tθ_t-,F_t+1^-1∇^2 J(ω̂_t)_D_tϕ_t^⊤(s,a)(-)ϕ_t(s,a)  _(ii)

-β_tθ_t-,F_t+1^-1∇^2 J(ω̂_t)_D_tϕ_t^⊤(s,a)(θ_t-)ϕ_t(s,a)  _(iii)

-β_tθ_t-,F_t+1^-1∇^2 J(ω̂_t)ϕ_t^⊤(s_t,a_t)θ_tϕ_t(s_t,a_t)-_D_tϕ_t^⊤(s,a)θ_tϕ_t(s,a)  _(iv)

+B C^3_ϕC_ϕL_π+2L_ϕ/2λ^2_minβ_t+B C^3_ϕC_ϕL_π+2L_ϕ+2λ^2_min/2λ^2_minβ_t θ_t-

+1/β_tC_gapmρ^k/λ_min ^2.

where $(a)$ follows from <Ref>, $(b)$ follows from Lagrange's Mean Value for some $\lambda\in[0,1]$, such that $\hat\omega_t =\lambda \omega_t+(1-\lambda)\omega_{t+1}$, $(c)$
follows from the facts that for positive definite matrices $X$ and $Y$,

X^-1-Y^-1    ≤X^-1X-Y Y^-1

≤X^-1X-Y Y^-1 ,

and $(d)$ is from that

F_t+1-F_t   = _D_t+1ϕ_t+1(s,a)ϕ^⊤_t+1(s,a)-_D_tϕ_t(s,a)ϕ^⊤_t(s,a)

≤    _D_t+1ϕ_t+1(s,a)ϕ^⊤_t+1(s,a)-_D_tϕ_t+1(s,a)ϕ^⊤_t+1(s,a)

+ _D_tϕ_t+1(s,a)ϕ^⊤_t+1(s,a)-_D_tϕ_t(s,a)ϕ^⊤_t(s,a)

≤   C^2_ϕD_t+1-D_t +  ϕ_t(s,a)+ ϕ_t+1(s,a)ϕ_t(s,a)-ϕ_t+1(s,a)

≤a    C^2_ϕL_πω_t+1-ω_t+ 2C_ϕL_ϕω_t+1-ω_t

=    C^2_ϕL_π+ 2C_ϕL_ϕ β_tϕ^⊤_t(s_t,a_t)θ_tϕ_t(s_t,a_t)

≤    B C^3_ϕC_ϕL_π+2L_ϕβ_t
,where $(a)$ follows from [Zou et al., 2019] and Theorem 1 in [Li et al., 2021], where $ L_\pi=\frac{1}{2}C_\pi
\brac{1+\myceil{\log m^{-1}}+\frac{1}{1-\rho}} $, and

D_t+1-D_t ≤L_πω_t+1-ω_t .

We then consider the term $(i)$,

(i)   ≤β_tθ_t-F_t+1^-1 ∇^2 J(ω̂_t)

≤L_Jβ_t/λ_min 1/2θ_t- +1/2,
where the last inequality follows from <Ref>.

Next, we consider the term $(ii)$,

(ii)   ≤β_tC^2_ϕθ_t-F_t+1^-1 ∇^2 J(ω̂_t)  -
≤2 B C^2_ϕC_gapL_J mρ^kβ_t/λ^2_min,
where the last inequality follows from <Ref> and <Ref>.

Then, consider the term $(iii)$,

(iii)   ≤β_t C^2_ϕθ_t-F_t+1^-1 ∇^2 J(ω̂_t)  θ_t-

Consider the term $(iv)$,

(iv)= -β_t(F_t+1^-1∇^2 J(ω̂_t) )^⊤(θ_t-), ϕ_t^⊤(s_t,a_t)θ_tϕ_t(s_t,a_t)-_D_tϕ_t^⊤(s,a)θ_tϕ_t(s,a)

= -β_t[(F_t+1^-1∇^2 J(ω̂_t) )^⊤(θ_t-)-(F_t-k^-1∇^2 J(ω̂_t-k-1) )^⊤(θ_t-k-θ^*_t-k),

ϕ_t^⊤(s_t,a_t)θ_tϕ_t(s_t,a_t)-_D_tϕ_t^⊤(s,a)θ_tϕ_t(s,a) ⟩]

- β_t(F_t-k^-1∇^2 J(ω̂_t-k-1) )^⊤(θ_t-k-θ^*_t-k), ϕ_t^⊤(s_t,a_t)θ_tϕ_t(s_t,a_t)-_D_tϕ_t^⊤(s,a)θ_tϕ_t(s,a)

≤2C^2_ϕBβ_t  (F_t+1^-1∇^2 J(ω̂_t) )^⊤(θ_t-)-(F_t-k^-1∇^2 J(ω̂_t-k-1) )^⊤(θ_t-k-θ^*_t-k)

+ β_t [⟨(F_t-k^-1∇^2 J(ω̂_t-k-1) )^⊤(θ_t-k-θ^*_t-k), ϕ_t^⊤(s_t,a_t)θ_tϕ_t(s_t,a_t)-_D_tϕ_t^⊤(s,a)θ_tϕ_t(s,a)⟩]

≤a 2C^2_ϕB β_t  (F_t+1^-1∇^2 J(ω̂_t) )^⊤(θ_t-)-(F_t-k^-1∇^2 J(ω̂_t-k-1) )^⊤(θ_t-k-θ^*_t-k)

+ β_t 2B^2 C^2_ϕL_J/λ_mins_t,a_t|ℱ_t-k -D_t

≤b2C^2_ϕB β_t  (F_t+1^-1∇^2 J(ω̂_t) )^⊤(θ_t-)-(F_t-k^-1∇^2 J(ω̂_t-k-1) )^⊤(θ_t-k-θ^*_t-k)

+  2 B^2 C^2_ϕL_Jβ_t/λ_min C_π∑_j=t-k^t-1 ω_t-ω_j+ mρ^k

≤2C^2_ϕB β_t  (F_t+1^-1∇^2 J(ω̂_t) )^⊤(θ_t-)-(F_t-k^-1∇^2 J(ω̂_t-k-1) )^⊤(θ_t-k-θ^*_t-k)

+  2 B^2 C^2_ϕL_Jβ_t/λ_min C_πC^2_ϕB ∑_j=t-k^t-1 ∑_i=j^t-1 β_i+ mρ^k,
where $(a)$ follows from <Ref> and $(b)$ follows from <Ref>.

Consider the first term in <Ref> and  we have that

(F_t+1^-1∇^2 J(ω̂_t) )^⊤(θ_t-)-(F_t-k^-1∇^2 J(ω̂_t-k-1) )^⊤(θ_t-k-θ^*_t-k)

≤F_t+1^-1-F_t-k^-1  ∇^2 J(ω̂_t) )^⊤(θ_t-)+F_t-k^-1  ∇^2 J(ω̂_t)-∇^2 J(ω̂_t-k-1)(θ_t-)

+ (F_t-k^-1∇^2 J(ω̂_t-k-1) )^⊤θ_t-θ_t-k - θ^*_t+θ^*_t-k

≤2B L_J F_t+1^-1-F_t-k^-1 + 2B/λ_min∇^2 J(ω̂_t)-∇^2 J(ω̂_t-k-1)

+L_J/λ_minθ_t-θ_t-k +θ^*_t-θ^*_t-k

≤a 2 B^2 L_J C^3_ϕC_ϕL_π+2L_ϕ/λ^2_min∑_j=t-k^tβ_j+ 2B/λ_min∇^2 J(ω̂_t)-∇^2 J(ω̂_t-k-1)

+L_J/λ_minθ_t-θ_t-k +θ̅^*_t-θ̅^*_t-k +θ̅^*_t-θ^*_t +θ^*_t-k-θ̅^*_t-k

≤b 2 B^2 L_J C^3_ϕC_ϕL_π+2L_ϕ/λ^2_min∑_j=t-k^tβ_j+ 2B L_Θ/λ_min ω̂_t- ω̂_t-k-1

+L_J/λ_minθ_t-θ_t-k +C_Θω_t-ω_t-k +2C_gapmρ^k/λ_min

≤2 B^2 L_J C^3_ϕC_ϕL_π+2L_ϕ/λ^2_min∑_j=t-k^tβ_j+ 2B^2 C^2_ϕL_Θ/λ_min ∑_j=t-k^tβ_t

+L_J/λ_min(k+1) C_ϕU_δ∑_j=t-k^t-1α_j + B C^2_ϕC_Θ∑_j=t-k^t-1β_j+2C_gapmρ^k/λ_min

= (k+1) C_ϕU_δL_J/λ_min∑_j=t-k^t-1α_j + 2C_gapL_J mρ^k/λ^2_min

+ B C^2_ϕ/λ^2_min2B C_ϕL_J(C_ϕL_π+2L_ϕ)+ 2 B L_Θλ_min+C_Θλ_min  ∑_j=t-k^t β_j,
where $(a)$ follows from <Ref> and <Ref> and $(b)$ follows from <Ref>.

Therefore, the term $(iv)$ can be bounded as:

(iv)    ≤2(k+1) B C^3_ϕU_δL_J/λ_minβ_t∑_j=t-k^t-1α_j

+ 2B C^2_ϕL_J2C_gap+Bλ_min /λ^2_minmρ^kβ_t

+2B^3 C_πC^4_ϕL_J/λ_minβ_t ∑_j=t-k^t-1 ∑_i=j^t-1 β_i

+ 2 B^2 C^4_ϕ/λ^2_min2B C_ϕL_J(C_ϕL_π+2L_ϕ)+ 2 B L_Θλ_min+C_Θλ_min  β_t∑_j=t-k^t β_j.

Combining the above bounds on terms $(i),(ii),(iii)$ and $(iv)$,
we have that

θ_t-, -
≤B C^3_ϕC_ϕL_π+2L_ϕ+λ_min(L_J+ 2 C_ϕ)+2λ^2_min/2λ^2_minβ_t θ_t-

+L_Jλ_min+B C^3_ϕC_ϕL_π+2L_ϕ/2λ^2_minβ_t
+ 2B C^2_ϕL_J  3 C_gap+  λ_min /λ^2_min m ρ^kβ_t

+2(k+1) B C^3_ϕU_δL_J/λ_minβ_t∑_j=t-k^t-1α_j  +2B^3 C_πC^4_ϕL_J/λ_minβ_t ∑_j=t-k^t-1 ∑_i=j^t-1 β_i+1/β_tC_gapmρ^k/λ_min ^2

+ 2 B^2 C^4_ϕ/λ^2_min2B C_ϕL_J(C_ϕL_π+2L_ϕ)+ 2 B L_Θλ_min+C_Θλ_min  β_t∑_j=t-k^t β_j.

This bounds term III in <Ref>.

Plugging bounds on terms I, II, III in <Ref> further implies that

E   θ- ≤ 1-λ̅_minα_t+ B C^3_ϕC_ϕL_π+2L_ϕ+λ_min(L_J+ 2 C_ϕ)+2λ^2_min/λ^2_minβ_tθ_t-

+L_Jλ_min+B C^3_ϕC_ϕL_π+2L_ϕ /λ^2_minβ_t
+ (k+1)^2C^2_ϕ/λ̅_minα_t η_t-J(ω_t)

+ (k+1)^2 U_δ^2 C^2_ϕα_t^2+ 4(k+1) B C^3_ϕU_δL_J/λ_minβ_t∑_j=t-k^t-1α_j
+2(k+1) C^3_ϕB U_δC_Θα_tβ_t

+ 2B C_ϕL_J(C_ϕL_π+2L_ϕ)+ 2 B L_Θλ_min+ C_Θλ_min  4 B^2 C^4_ϕ/λ^2_minβ_t∑_j=t-k^t β_j+ 2 C^4_ϕB^2 C_Θ^2 β_t^2

+4B C^2_ϕL_J  3 C_gap+  λ_min /λ^2_min m ρ^kβ_t  + 4(k+1) C_ϕU_δC_gapmρ^k/λ_minα_t+2/β_t+8C_gapmρ^k/λ_min ^2

+4B^3 C_πC^4_ϕL_J/λ_minβ_t ∑_j=t-k^t-1 ∑_i=j^t-1 β_i+ 2 α_t G^δ_t.

Set the stepsize such that $\frac{\bar \lambda_{\min} \alpha_t}{2}\geq \frac{B C^3_\phi\brac{C_\phi L_\pi+2L_\phi }+\lambda_{\min}(L_J+ 2 C_\phi)+2\lambda^2_{\min}}{\lambda^2_{\min}}\beta_t$, and the proof ends.

§.§ Sample Complexity of AC

We first present our proof of <Ref>. For convenience, we set $\alpha_t=\alpha$,
$\beta_t=\beta$, $\gamma_t=\gamma$ in following.

(Restatement of <Ref>)
With the constant step sizes such that $k = \mathcal{O}\brac{\log T}$ and $\gamma\geq  \alpha\geq   \beta$, the tracking error of the AC algorithm in  <Ref> can be bounded as follows:

1/T∑_t=0^T-1 θ^*_t-θ_t
≤    c_αβ/α+c_ηβ/γ1/T∑_t=0^T-1
+𝒪1/T α
+𝒪log^2 T/T γ

+𝒪αlog^3 T
+𝒪βlog^3 T
+ 𝒪γlog^3 T +𝒪β^2log^2 T/α
+𝒪β^2log^2 T/γ

+𝒪(mρ^k)log^2 T

where $c_\alpha=\frac{2L_J\lambda_{\min}+2B C^3_\phi\brac{C_\phi L_\pi+2L_\phi } }{\lambda^2_{\min} \bar \lambda_{\min}}$ and $c_\eta=\frac{2B^2 (k+1)^2 C^6_\phi}{(\bar\lambda_{\min})^2}  $.

Recall that in <Ref>, we showed

≤1-λ̅_min α/2
+L_Jλ_min+B C^3_ϕC_ϕL_π+2L_ϕ/λ^2_minβ

+ (k+1)^2C^2_ϕ/λ̅_minαη_t-J(ω_t)

Apply this inequality recursively and we have that

≤1-λ̅_min α/2 ^t
+L_Jλ_min+B C^3_ϕC_ϕL_π+2L_ϕ /λ^2_minβ∑_j=0^t-1 1-λ̅_min α/2 ^t-j-1∇J(ω_j)

+(k+1)^2 C^2_ϕ/λ̅_minα∑_j=0^t-1 1-λ̅_min α/2 ^t-j-1J(ω_j)-η_j +∑_j=0^t-1 1-λ̅_min α/2 ^t-j-1G^θ_j

= 1-q ^t
+L_Jλ_min+B C^3_ϕC_ϕL_π+2L_ϕ /λ^2_minβ∑_j=0^t-1 1-q ^t-j-1∇J(ω_j)

+(k+1)^2 C^2_ϕ/λ̅_minα∑_j=0^t-1 1-q^t-j-1J(ω_j)-η_j +∑_j=0^t-1 1-q ^t-j-1G^θ_j,

where we let $q= \frac{\bar \lambda_{\min} \alpha}{2}$.

Summing the inequality in <Ref> above w.r.t. $t$ from $0$ to $T-1$ further implies that

≤1/T∑_t=0^T-1 1-q ^t
+ L_Jλ_min+B C^3_ϕC_ϕL_π+2L_ϕ /λ^2_minβ/T∑_t=0^T-1∑_j=0^t-1 1-q ^t-j-1∇J(ω_j)

+(k+1)^2 C^2_ϕ/λ̅_minα1/T∑_t=0^T-1∑_j=0^t-1 1-q^t-j-1J(ω_j)-η_j
+1/T∑_t=0^T-1∑_j=0^t-1 1-q ^t-j-1G^θ_j

≤4B^2 /Tq+ L_Jλ_min+B C^3_ϕC_ϕL_π+2L_ϕ /λ^2_minβ/Tq∑_j=0^T-1∇J(ω_j)
+(k+1)^2 C^2_ϕ/λ̅_minα/Tq∑_j=0^T-1 J(ω_j)-η_j

+ 1/Tq∑_t=0^T-1 G^θ_t,

where the last inequality is from the double-sum trick: $\sum^{T-1}_{t=0}\sum^{t-1}_{j=0} y^{t-j-1}X_j\leq (\sum^{T-1}_{t=0}X_t)(\sum^{T-1}_{t=0}y^t)\leq \frac{\sum^{T-1}_{t=0}X_t}{1-y}$ for $X_j\geq 0,  j=0,1,2,...,T-1$ and $y \in (0,1)$.

Recall that we showed in <Ref> that

+C_ϕ^4 B^2β + G_t^η.

Recursively applying this inequality implies that

≤1-γ^t η_0-J(ω_0)
+ C_ϕ^4 B^2β∑_j=0^t-1 1-γ^t-j-1∇J(ω_j)
+ ∑_j=0^t-1 1-γ^t-j-1 G_j^η
≤R^2_max 1-γ^t+ C_ϕ^4 B^2 β∑_j=0^t-1 1-γ^t-j-1∇J(ω_j)
+ ∑_j=0^t-1 1-γ^t-j-1 G_j^η.

We then sum the above inequality w.r.t. $t$ from 0 to $T-1$, and have that

1/T   ∑_t=0^T-1 η_t-J(ω_t)

≤R^2_max/T∑_t=0^T-1   1-γ^t
+ C_ϕ^4 B^2 β/T ∑_t=0^T-1∑_j=0^t-1 1-γ^t-j-1∇J(ω_j)
+ 1/T∑_t=0^T-1∑_j=0^t-1 1-γ^t-j-1 G_j^η

=R^2_max/Tγ+C_ϕ^4 B^2 β/Tγ∑_t=0^T-1∇J(ω_t)
+ 1/Tγ∑_t=0^T-1 G_t^η,

where we use the double-sum trick below <Ref> again.

Plugging <Ref> in <Ref> further implies that

≤a 8B^2 /λ̅_minT α+2L_Jλ_min+2B C^3_ϕC_ϕL_π+2L_ϕ /λ^2_min λ̅_min β/Tα∑_t=0^T-1∇J(ω_t)

+2 (k+1)^2 C^2_ϕ/(λ̅_min)^21/T∑_t=0^T-1 J(ω_t)-η_t
+2/λ̅_minT α∑_t=0^T-1 G^θ_t

≤2L_Jλ_min+2B C^3_ϕC_ϕL_π+2L_ϕ /λ^2_min λ̅_min  β/α+ 2(k+1)^2B^2 C^6_ϕβ/(λ̅_min)^2γ  1/T∑_t=0^T-1∇J(ω_t)
+ 8B^2 /λ̅_minT α+ 2/λ̅_minT α∑_t=0^T-1 G^θ_t
+2 (k+1)^2 C^2_ϕR^2_max/(λ̅_min)^2 Tγ
+2 (k+1)^2 C^2_ϕ/(λ̅_min)^21/Tγ∑_t=0^T-1 G_t^η
=c_αβ/α+c_ηβ/γ  1/T∑_t=0^T-1∇J(ω_t)+ 8B^2 /λ̅_minT α+ 2/λ̅_minT α∑_t=0^T-1 G^θ_t

+2 (k+1)^2 C^2_ϕR^2_max/(λ̅_min)^2 Tγ
+2 (k+1)^2 C^2_ϕ/(λ̅_min)^2  1/Tγ∑_t=0^T-1 G_t^η,

where $(a)$ follows from that $q=\frac{\bar\lambda_{\min}\alpha}{2}$, $c_\alpha=\frac{2L_J\lambda_{\min}+2B C^3_\phi\brac{C_\phi L_\pi+2L_\phi } }{\lambda^2_{\min} \bar \lambda_{\min}}$ and $c_\eta=\frac{ 2(k+1)^2B^2 C^6_\phi}{(\bar\lambda_{\min})^2}  $.
By <Ref>, if we set the stepsize $\beta=\min\varbrac{ \frac{\lambda^2_{\min} \bar \lambda_{\min}\alpha}{16 C^4_\phi\brac{L_J\lambda_{\min}+B C^3_\phi\brac{C_\phi L_\pi+2L_\phi } }}, \frac{(\bar\lambda_{\min})^2\gamma}{16(k+1)^2 C^{10}_\phi B^2} }$, then we can get that $\brac{\frac{c_\alpha \beta}{\alpha}+\frac{c_\eta \beta}{\gamma} } \leq \frac{1}{4 C^4_\phi} $. This completes the proof of <Ref>.

We are now ready to prove <Ref>.

(Restatement of <Ref>)
Consider the AC algorithm in  <Ref> with constant step sizes $\alpha_t=\alpha,\beta_t=\beta,\gamma_t=\gamma$. Then, it holds that

\begin{align}
\frac{1}{T} \sum _{t=0}^{T-1} \E \Fbrac{\twonormsq{\gradj}}
& \leq 2C_\phi^4 \frac{1}{T} \sum _{t=0}^{T-1} \E \Fbrac{\twonormsq{\thestar-\theta_t}} +\mathcal{O}\brac{\frac{1}{T \beta}}
+\mathcal{O}\brac{\beta \log^2 T}+\mathcal{O} (m\rho^k) .
\end{align}

If we further set $k=\myceil{\frac{\log T}{1-\rho}}, \gamma=\mathcal{O}(\frac{1}{\sqrt{T}}),  \alpha=\mathcal{O}(\frac{1}{\sqrt{T}\log^2 T}),  \beta =\mathcal{O}(\frac{1}{\sqrt{T}\log^2 T})$, then we have that

\begin{align}
\frac{1}{T} \sum _{t=0}^{T-1} \E \Fbrac{\twonormsq{\gradj}}
\leq\mathcal{O}\brac{\frac{{\log^3 T}}{\sqrt{T}}}.
\end{align}

Recall <Ref>, and we have that

≤2J(ω_T)-J(ω_0)/T β
+  2 C^4_ϕ/T∑_t=0^T-1 θ_t-
+   2/Tβ∑_t=0^T-1G_t^ω.

Plug <Ref> in <Ref>, and we have that

≤1/4C^4_ϕ 1/T∑_t=0^T-1∇J(ω_t)+ 8B^2 /λ̅_min Tα+ 2/λ̅_min Tα∑_t=0^T-1 G^θ_t
+2 (k+1)^2 C^2_ϕR^2_max/(λ̅_min)^2 Tγ
+2 (k+1)^2 C^2_ϕ/(λ̅_min)^2  1/Tγ∑_t=0^T-1 G_t^η

= 1/2 C^4_ϕTβJ(ω_T)-J(ω_0)
+  1/2T∑_t=0^T-1 θ_t-
+ 8B^2 /λ̅_min Tα+ 1/2 C^4_ϕTβ∑_t=0^T-1G^ω_t

+2 (k+1)^2 C^2_ϕ/(λ̅_min)^2R^2_max/Tγ+ 1/Tγ∑_t=0^T-1 G_t^η+2/λ̅_min Tα∑_t=0^T-1 G^θ_t

This further implies that

≤1/ C^4_ϕT βJ(ω_T)-J(ω_0)

+ 16B^2 /λ̅_min Tα+ 1/ C^4_ϕTβ ∑_t=0^T-1G^ω_t
+4 (k+1)^2 C^2_ϕ/(λ̅_min)^2 R^2_max/Tγ+ 1/Tγ∑_t=0^T-1 G_t^η+4/λ̅_min Tα∑_t=0^T-1 G^θ_t.

Next, we choose the stepsizes to minimize the tracking error and the gradient norm.
We choose $\gamma=\frac{1}{\sqrt{T}}$ and  $k= \myceil{\frac{\log T}{1-\rho}}$. Consider $T\geq \frac{2C^2_\phi d m}{\lambda_{\min}}$, then we can get that $\bar \lambda_{\min}\geq \frac{\lambda_{\min}}{2}$.
We set $\alpha$ and $\beta$ such that $\alpha=  \frac{1}{(k+1)^2  }\gamma$ and $\beta= \min \varbrac{\frac{\lambda^3_{\min} }{4\brac{L_J\lambda_{\min}+B C^3_\phi\brac{C_\phi L_\pi+2L_\phi } +2\lambda^2_{\min}}}\alpha,\frac{\lambda^3_{\min} }{32C^4_\phi\brac{L_J\lambda_{\min}+B C^3_\phi\brac{C_\phi L_\pi+2L_\phi } }}\alpha,\frac{\lambda^2_{\min}}{64 (k+1)^2 C^6_\phi B^2 }\gamma}  $. It holds that

γ=𝒪1/√(T),  α=𝒪1/√(T)log^2 T,  β=𝒪1/√(T)log^2 T,q =𝒪1/√(T)log^2 T.

According to <Ref>, <Ref> and <Ref>, the orders of the following terms are as follows:

1/T∑_t=0^T-1G_t^ω=𝒪 (mρ^k)β+ k^2 β^2 =𝒪1/T log^2 T;

1/T∑_t=0^T-1G_t^η= 𝒪(mρ^k)γ+β^2+k^2βγ+k γ^2=𝒪logT/T;

1/T∑_t=0^T-1 G_t^θ=𝒪k (mρ^k)α+(mρ^k)β+(m ρ^k)^2/β+k^3α^2+k^3 αβ+k^2β^2 =𝒪1/T logT.

Then <Ref> can be bounded as follows:

= 𝒪 log^3 T/√(T) .

Plugging <Ref> in <Ref> implies that

≤32 C^4_ϕB^2 /λ̅_min Tα+ 8 (k+1)^2 C^6_ϕ/(λ̅_min)^2R^2_max/Tγ+ 1/Tγ∑_t=0^T-1G_t^η+ 8C^4_ϕ/λ̅_min Tα∑_t=0^T-1G_t^θ
+ 4/TβJ(ω_T)-J(ω_0)+

Plugging in the step-sizes above, we have that

= 𝒪 log^3 T/√(T) ,

which completes the proof.

§ NAC SAMPLE COMPLEXITY ANALYSIS

In this section, we provide the sample complexity analysis for NAC.

§.§ Bound on Gradient Norm in NAC

Recall that in <Ref>, NAC updates the policy parameter as follows:
$\omega\tit-\omega_t=\beta_t\theta_t $, which directly implies that

≤β_t θ_t
≤B β_t.

Consider the largest eigenvalue of the matrix
$F_t=\E_{D_t}\Fbrac{\phi_t(s,a)\phi^\top_t(s,a)} $. Note that for any vector $x\in \mathbb{R}^d$

F_t x= _D_tϕ_t(s,a)ϕ^⊤_t(s,a)x
≤ϕ_t(s,a) ϕ_t(s,a) x
Thus, $\lambda_{\max}\brac{F_t }\leq C^2_\phi $.
Then, by <Ref>, we can show that

J   (ω)≥J(ω_t)+ , ω-ω_t-L_J/2 ω-ω_t

≥J(ω_t)+ β_t, θ_t- β_t^2 L_J/2 θ_t

≥J(ω_t)+β_t, + β_t, θ_t-
+ β_t, -
- L_J B^2β_t^2/2

J(ω_t)+β_t, _D_tϕ_t(s,a)ϕ^⊤_t(s,a)^-1-β_t/4C^2_ϕ-C^2_ϕβ_tθ_t-

- L_J B^2β_t^2/2

≥b J(ω_t)+β_t/C^2_ϕ -β_t/2C^2_ϕ-C^2_ϕβ_tθ_t-- C_gapC^2_ϕm ρ^kβ_t/λ_min
- L_J B^2β_t^2/2

= J(ω_t)+β_t/2C^2_ϕ
-C^2_ϕβ_tθ_t-- C_gapC^2_ϕm ρ^kβ_t/λ_min- L_J B^2β_t^2/2 ,

where $(a)$ follows from that $\vbrac{\gradj, \theta_t-\thestar} \geq-\frac{1}{4C^2_\phi}\twonormsq{\gradj}-C^2_\phi\twonormsq{\theta_t-\thestar}  $ and $(b)$ follows from that $\lambda_{\max}(F_t)\leq C^2_\phi$, $\vbrac{\gradj, \brac{\E_{D_t}\Fbrac{\phi_t(s,a)\phi^\top_t(s,a)}}^{-1}\gradj}= \gradj^\top \brac{F_t}^{-1}\gradj\geq \frac{1}{C^2_\phi}\twonormsq{\gradj},$  and <Ref>.

Taking the expectation on both sides of <Ref>,
we have that

≤2C^2_ϕJ(ω)- J(ω_t)/β_t
+ 2 C_ϕ^4 θ_t-+ 2C^4_ϕC_gap m ρ^k/λ_min
+ L_J B^2 C^2_ϕβ_t.

§.§ Bound on $|\eta_t-J(\omega_t)|$ in NAC

In this section, we bound the term $\eta_t-J(\omega_t)$ for the NAC algorithm.

If we denote

G^η_t    = 2γ_t   BR_max^2 C_π∑_j=t-k^t-1 ∑_i=j^t-1 β_i
+  R^2_max m ρ^k+ R_max^2 ∑_j=t-k^t-1γ_j
+  BC_JR_max   ∑_j=t-k^t-1β_j

+ R_max^2 γ^2_t + C_J^2  B^2 β_t^2
+   2 BC_J R_max  β_tγ_t
+ R_maxL_J  B^2 β_t^2,

and set $\gamma_t-\gamma^2_t\geq \beta_t$,
then it holds that

+β_tB^2 + G^η_t.

Similar to the AC analysis in <Ref> in <Ref>, we have that

= 1-γ_t^2η_t-J(ω_t)
+γ_t^2 R_t-J(ω_t) +J(ω_t)-J(ω_t+1)

+ 2γ_t1-γ_t

The term $\lbrac{J(\omega_t)-J(\omega_{t+1})}$ can be bounded using its Lipschitz smoothness in <Ref>:

≤C_J  B β_t .

Term I in <Ref>  can be bounded as follows:

≤BC_J R_max  β_t.

Term II in <Ref> can be bounded as follows:

≤(η_t-k-J(ω_t-k))( R_t-J(ω_t))
+(η_t-η_t-k-J(ω_t)+J(ω_t-k))( R_t-J(ω_t))

+  η_t-η_t-k-J(ω_t)+J(ω_t-k)R_t-J(ω_t)

+  η_t-η_t-k-J(ω_t)+J(ω_t-k)R_t-J(ω_t)

≤b    R^2_max ℙ(s_t,a_t)|ℱ_t-k,D_t
+ R_maxη_t-η_t-k +J(ω_t)-J(ω_t-k)

R_max^2 C_π∑_j=t-k^t-1 ω_t-ω_j+mρ^k

+ R_maxR_max∑_j=t-k^t-1γ_j+C_J ω_t-ω_t-k

≤B R_max^2 C_π∑_j=t-k^t-1 ∑_i=j^t-1 β_i
+  R^2_max m ρ^k+ R_max^2∑_j=t-k^t-1γ_j
+  R_max C_J  B ∑_j=t-k^t-1β_j,

where $(a)$ follows from $\E_{(s,a)\sim D_t}\Fbrac{R(s,a)-J(\omega_t)|\mathcal{F}_t}=0 $, $(b)$ follows from  $0\leq\eta_t\leq R_{\max}$, $0\leq J(\omega_t)\leq R_{\max}$,  $0\leq R_t\leq R_{\max}$, and

$(c)$ follows from  <Ref>.

We then bound  term III as follows:

=(η_t-J(ω_t)) -∇^⊤J(ω_t) (ω-ω_t)+ ω-ω_t^⊤∇^2J(ω̂_t)/2ω-ω_t

≤(η_t-J(ω_t)) ∇^⊤J(ω_t) (ω-ω_t)

=β_t (η_t-J(ω_t)) ∇^⊤J(ω_t) θ_t
+β^2_tη_t-J(ω_t)  ∇^2J(ω̂_t)/2θ_t

+ R_maxL_J  B^2/2 β_t^2,

where the first equation is from the Lagrange's Mean Value theorem for some $\hat{\omega}_t=\lambda\omega_t+(1-\lambda)\omega_{t+1}$, $\lambda\in(0,1)$.

Plug  <Ref>, <Ref>, and <Ref> in <Ref>, and we have that

≤(1-γ_t)^2+ β_tη_t-J(ω_t)
+ B^2β_t

+ 2γ_t   B R_max^2 C_π∑_j=t-k^t-1 ∑_i=j^t-1 β_i
+  R^2_max m ρ^k+ R_max^2 ∑_j=t-k^t-1γ_j
+  R_maxC_J  B ∑_j=t-k^t-1β_j

+ R_max^2 γ^2_t + C_J^2  B^2 β_t^2
+ 2BC_J R_max  β_tγ_t
+R_maxL_J B^2 β_t^2.
In <Ref>, we use the fact that $1-\gamma_t\leq 1$.
This completes the proof.

§.§ Tracking Error Analysis of NAC

In this section, we bound the tracking error $\theta_t-\thestar$ for NAC.  Define

G^θ_t =
8  + 2 /β_t+ β_t C_ΘC_gapmρ^k/λ_min^2

+ (k+1)^2U_δ^2 C_ϕ^2 α_t^2
+4(k+1) C_ϕU_δC_gapmρ^k/λ_minα_t

+2(k+1) C_ϕB U_δC_Θα_tβ_t
+ 2α_t G_t^δ+2 C_Θ^2  B^2 β_t^2

If we set the step size satisfies that $\beta_t\leq \frac{\bar\lambda_{\min}}{4(2C_\Theta+1)}\alpha_t$, then it holds that

+  C_Θ/λ^2_min β_t
+(k+1)^2 C^2_ϕ/λ̅_minα_tJ(ω_t)-η_t +G_t^θ.

From the update rule of <Ref>, we have that

θ-   =
Π_Bθ_t+α_t δ_t z_t-

≤a θ_t+α_t δ_t z_t-

≤θ_t+α_t δ_t z_t-+-

= θ_t-+ α_t^2 δ_t z_t+ -
+ 2 α_tθ_t-, δ_t z_t

+ 2α_t δ_t z_t, -
+ 2 θ_t-, -,

where $(a)$ follows from the fact $\twonorm{\Pi_B(x)-y}\leq \twonorm{x-y} $ when $\twonorm{y}\leq B $ and $\twonorm{\theta^*_{t+1}}\leq B$.

Taking expectations on both sides of <Ref>, we have that

θ-  ≤θ_t-+ α_t^2 δ_t z_t+ -

+ 2 α_tθ_t-, δ_t z_t_I
+ 2α_t δ_t z_t, -_II
+ 2 θ_t-, -_III.

For the term $\twonorm{\thestar-\thestara}$, we have that

=-+ --+

≤-+ -+ -

= β_t C_Θθ_t +2C_gapmρ^k/λ_min

≤C_ΘB β_t+2C_gapmρ^k/λ_min,

where $(a)$ follows from <Ref> and  <Ref>. Hence we have that

≤2 C^2_ΘB^2 β^2_t+8C^2_gapm^2ρ^2k/λ^2_min.

By Lemma <ref>,  term I in <Ref> can be bounded as

θ_t-, δ_t z_t
≤    - λ̅_min/2 θ_t-
+(k+1)^2 C^2_ϕ/2λ̅_minJ(ω_t)-η_t+G^δ_t.

For  term II in <Ref>, we have that

δ_t z_t, -
≤δ_t z_t  -

≤(k+1) C_ϕU_δ-+ -+-

≤a (k+1) C_ϕU_δC_Θω-ω_t + 2(k+1) C_ϕU_δC_gapmρ^k/λ_min

≤(k+1) C_ϕB U_δC_Θβ_t
+ 2(k+1) C_ϕU_δC_gapmρ^k/λ_min,
where $(a)$ follows from <Ref> and  <Ref>.

For term III in <Ref>, we have  that

θ_t-, -

= θ_t-, - +θ_t-, -
+θ_t-, -

≤θ_t--   +θ_t--

≤a C_Θθ_t- ω-ω_t  + β_t/2θ_t-+ 1/2β_t-

+ β_t/2θ_t-+ 1/2β_t-

≤bC_Θθ_t-  ω-ω_t + β_t θ_t- +1/β_tC_gapmρ^k/λ_min ^2

=C_Θβ_t θ_t- θ_t
+ β_t θ_t- +1/β_tC_gapmρ^k/λ_min ^2

≤C_Θβ_t  θ_t-
+ C_Θβ_t  θ_t-+ C_Θβ_t  θ_t-  -

+ β_t θ_t- +1/β_tC_gapmρ^k/λ_min ^2

≤1/2 C_Θβ_t θ_t- +1/2 C_Θβ_t
+C_Θβ_t θ_t-
+1/2 C_Θβ_t θ_t-

+1/2 C_Θβ_t -  + β_t θ_t- +1/β_tC_gapmρ^k/λ_min ^2

≤c 1/2 C_Θβ_t θ_t-
+ 1/2 C_Θβ_t   F_t^-1
+ C_Θβ_t θ_t-

+C_Θ/2β_t  θ_t-  + C_Θβ_t/2 C_gapmρ^k/λ_min ^2+β_t θ_t-
+1/β_tC_gapmρ^k/λ_min ^2

≤d 2C_Θ+1 β_tθ_t-
+ C_Θ/2 λ_min^2β_t

+β_t C_Θ/2 +1/β_tC_gapmρ^k/λ_min ^2
where $(a)$ follows from <Ref>; $(b)$ follows from <Ref>; $(c)$ follows from <Ref>, <Ref>, and <Ref>; $(d)$ follows from that $\twonorm{F_t^{-1}}\leq \frac{1}{\lambda_{\min}}$.

Plugging the above bounds   in <Ref>, we have  that

≤1-λ̅_minα_t  +4C_Θ+2β_t
+ C_Θ/λ^2_min β_t

+(k+1)^2 C^2_ϕ/λ̅_minα_tJ(ω_t)-η_t
+ 8  + 2 /β_t+ β_t C_ΘC_gapmρ^k/λ_min^2

+ (k+1)^2U_δ^2 C_ϕ^2 α_t^2

+4(k+1) C_ϕU_δC_gapmρ^k/λ_minα_t
+2(k+1) C_ϕB U_δC_Θα_tβ_t
+ 2α_t G_t^δ+2 C_Θ^2  B^2 β_t^2

This hence completes the proof.

§.§ Sample Complexity of NAC

In the following, we set $\alpha_t=\alpha$, $\beta_t=\beta$, and $\gamma_t=\gamma$ for any $t\geq 0$. We denote by $\D(\omega_t)=-\E_{D_{\pi^*}}\Fbrac{ \log\frac{\pi_{\omega_t}(a|s)}{\pi^*(a|s)}}$. Recall that $\hat t =\lceil \frac{3\log T}{\bar \lambda_{\min} \alpha}\rceil$. We first have the following lemma.

Denote by $\widetilde T={\myceil{\frac{T}{\hat t\log T}}}\hat t\geq \frac{T}{\log T}$, then for any $t'\leq T-\widetilde T$, it holds that

min_t≤T    J(π^*)-J(ω_t)

≤(ω_t')-(ω_t'+T) /βT
+ C_ϕC_gap m ρ^k /λ_min
+2 C_∞√(ε_actor )
+√(2)C_ϕ2e C_ϕ^3 C_M  t̂/T + √(2)C_ϕ√(4 B^2+  R_max^2/T )

+√(2)C_ϕ√( 1/T∑_t=t'^t'+T-1  ∑_j=t-t̂^t-1 (1-q)^t-j-1G^ω_j +G_j^θ+  G_j^η )
+2C_ϕ√( C_ϕ^2 C_Me t̂/T(ω_t')-(ω_t'+T) /βT

+2C_ϕ√(e t̂ C_ϕ^2 C_M /T  C_ϕC_gap m ρ^k /λ_min
+B^2L_ϕ/2β )

Recall that $\pi^*=\arg\max_\pi J(\pi)$ and $A^{\pi_t}=Q^{\pi_t}(s,a)-V^{\pi_t}(s)$. We first have that

= _D_π^*logπ(a|s)-logπ_t (a|s)

≥a _D_π^*∇^⊤logπ_t (a|s)

= β_D_π^*ϕ_t^⊤(s,a)θ_t- L_ϕβ^2/2θ_t

+β_D_π^* ϕ_t^⊤(s,a)-A^π_t(s,a)
+β_D_π^* ϕ_t^⊤(s,a)(θ_t-)
- B^2L_ϕβ^2/2

=b βJ(π^*)-J(π_t)
+β_D_π^* ϕ_t^⊤(s,a)-A^π_t(s,a) _I
+β_D_π^* ϕ_t^⊤(s,a)(θ_t-)_II
- B^2L_ϕβ^2/2,

where $(a)$ follows from that

≤_D_π^*[L_ϕω-ω']= L_ϕω-ω',

and $(b)$ follows from the fact that

_D_π^*A^π_t(s,a)   = _D_π^*Q^π_t(s,a)-V^π_t(s)

=_D_π^*R(s,a)-J(π_t) + V^π_t(s') -V^π_t(s)

=_D_π^*R(s,a)-J(π_t)+ _(s,a)∼D_π^*, s∼P(·|s,a)V^π_t(s')-_D_π^*V^π_t(s)

=J(π^*)-J(π_t)+ _ D_π^*V^π_t(s')-_D_π^*V^π_t(s)

To bound Term I, we first have that

_D_π^* ϕ_t^⊤(s,a)-A^π_t(s,a)

≤_D_π^* ϕ_t^⊤(s,a)-A^π_t(s,a) +
_D_π^* ϕ_t^⊤(s,a)(-)

≤D_π^*/D_t_∞_D_t  ϕ_t^⊤(s,a)-A^π_t(s,a)  + C_ϕ-

≤a D_π^*/D_t_∞√(_D_tϕ_t^⊤(s,a)- A^π_t(s,a)  ) + C_ϕC_gap m ρ^k /λ_min

≤b D_π^*/D_t_∞√(ε_actor )
+ C_ϕC_gap m ρ^k /λ_min,

where $(a)$ follows from that <ref>,
and $(b)$ follows from the definition of  $\thebar$ in <Ref>,  the definition of  $\varepsilon_{\text{actor}}$ and the facts that

For term II, we  have that

_D_π^* ϕ_t^⊤(s,a)(θ_t-)

Plug the two bounds on terms I and II in <Ref>, and we have that

≥    βJ(π^*)-J(ω_t)
-βD_π^*/D_t_∞√(ε_actor )
-βC_ϕC_gap m ρ^k /λ_min

-L_ϕ/2β^2 B^2,

which implies

≤   (ω_t)-(ω)
+βD_π^*/D_t_∞√(ε_actor )
+βC_ϕC_gap m ρ^k /λ_min

+B^2L_ϕ/2β^2 .

Set $M\tit= \E\ftwonormsq{ \theta\tit-\thestara} +   \E \flnormsq{\eta\tit-J(\omega_{t+1})}  $, and we now aim to bound $M_t$. Combine the bounds we obtained in <Ref> and <Ref>, and we have that

+  C_Θ/λ^2_min β
+(k+1)^2 C^2_ϕ/λ̅_minαJ(ω_t)-η_t

+  1-γη_t-J(ω_t)
+ B^2β+G_t^θ+  G_t^η
=  1-1/2λ̅_minα
+(k+1)^2 C^2_ϕ/λ̅_minαJ(ω_t)-η_t
+  1-γJ(ω_t)-η_t

+ C_Θ/λ^2_min+ B^2 β+G_t^θ+  G_t^η

(a)≤  1-1/2λ̅_minα
+(k+1)^2 C^2_ϕ/λ̅_minαJ(ω_t)-η_t
+  1-γJ(ω_t)-η_t

+ C_Θ/λ^2_min+ B^2β  2C_ϕ^2 /β J(ω)- J(ω_t)
+ 2 C^4_ϕθ_t-

+  C_Θ/λ^2_min+ B^2 2C_gap C_ϕ^4  m ρ^kβ/λ_min
+L_J C^2_ϕB^2β^2+G_t^θ+  G_t^η

≤1-1/2λ̅_minα+ 2 C_ϕ^4 C_Mβ
+  2C_ϕ^2 C_M J(ω)- J(ω_t)

+ 1-γ+ (k+1)^2 C^2_ϕ/λ̅_minαJ(ω_t)-η_t
+ C_M  2C_gap C_ϕ^4  m ρ^kβ/λ_min
+L_J C^2_ϕB^2β^2

+G_t^θ+  G_t^η,

where $(a)$ is obtained by  <Ref>, and $C_M= \frac{C_\Theta}{\lambda^2_{\min}}+ B^2 $.
For convenience, we set

G^ω_t=C_M  2C_gap C_ϕ^4  m ρ^kβ/λ_min
+ L_J C^2_ϕB^2β^2.

We set $k=\lceil\frac{\log T}{1-\rho}\rceil$ and $T\geq \frac{2C^2_\phi dm}{\lambda_{\min}}$ such that $\bar \lambda_{\min}\geq \frac{1}{2} \lambda_{\min}$. Furthermore, we set the step sizes such that $\frac{1}{6}\bar \lambda_{\min} \alpha \geq 2 C_\phi^4 C_M\beta $ and  $\frac{\gamma}{2}\geq \max\varbrac{\frac{1}{3}\bar \lambda_{\min}\alpha, \frac{(k+1)^2 C^2_\phi}{\bar \lambda_{\min}}\alpha }$. Let $q=\frac{1}{3}\bar \lambda_{\min}\alpha$ and $\frac{\gamma}{2}\geq q$. Then the inequality in <Ref> can be written as

M   ≤1-q  M_t
+  2C_ϕ^2 C_M J(ω)- J(ω_t)
+ G^ω_t +G_t^θ+  G_t^η.

Recall that $\hat t=\myceil{ \frac{1}{q}\log T}=\myceil{ \frac{3 \log T}{\bar \lambda_{\min}\alpha}}$.
For $t\geq 2k+ \hat t$, we recursively apply <Ref> for $\hat t$ times, and we have that

M_t≤    1-q^t̂ M_t-t̂+
2C_ϕ^2 C_M∑_j=t-t̂^t-1 (1-q)^t-j-1
J(ω_j+1)- J(ω_j)

+ ∑_j=t-t̂^t-1 (1-q)^t-j-1G^ω_j +G_j^θ+  G_j^η

≤a  4 B^2+ R_max^2/T+ 2C_ϕ^2 C_M∑_j=t-t̂^t-1 (1-q)^t-j-1
J(ω_j+1)- J(ω_j)

+∑_j=t-t̂^t-1 (1-q)^t-j-1G^ω_j +G_j^θ+  G_j^η,

where $(a)$ follows from $(1-q)^{\hat t}\leq e^{-q\hat t}\leq e^{-\log T}= \frac{1}{T} $ and $M_i= \E\ftwonormsq{ \theta_i-\theta_i^*} +   \E \flnormsq{\eta_i-J(\omega_{i})}\leq 4 B^2+R^2_{\max}$ for $i=0,1,...,T$.

Denote the time length $\widetilde T={\myceil{\frac{T}{\hat t\log T}}}\hat t\geq \frac{T}{\log T}$. For any $t'\leq T-\widetilde T$, together with <Ref> we have that

1/T∑_t=t'^t'+T-1 J(π^*)-J(ω_t)

≤(ω_t')-(ω_t'+T) /βT
+ C_ϕC_gap m ρ^k /λ_min
+1/T∑_t=t'^t'+T-1D_π^*/D_t_∞√(ε_actor )

+C_ϕ1/T∑_t=t'^t'+T-1 θ_t-

(ω_t')-(ω_t'+T) /βT
+ C_ϕC_gap m ρ^k /λ_min
+1/T∑_t=t'^t'+T-1D_π^*/D_t_∞√(ε_actor )

+C_ϕ√(1/T∑_t=t'^t'+T-1 θ_t-)
(ω_t')-(ω_t'+T) /βT
+ C_ϕC_gap m ρ^k /λ_min
+  C_∞√(ε_actor )

+C_ϕ√(1/T∑_t=t'^t'+T-1 M_t)
where $(a)$ follows from the rearrangement inequality and the fact for any random variable $X$, $\twonormsq{\E\Fbrac{X} }\leq \E \ftwonormsq{X} $ and $(b)$ follows from Assumption <ref>.

Moreover, for $2k+ \hat t \leq t'\leq T-\widetilde T$, summing <Ref> w.r.t. $t$ from $t'$ to $t'+\tilde{T}-1$ implies

≤2C_ϕ^2 C_M1/T∑_t=t'^t'+T-1 ∑_j=t-t̂^t-1 (1-q)^t-j-1
J(ω_j+1)- J(ω_j)

+ 4 B^2+  R_max^2/T+   1/T∑_t=t'^t'+T-1  ∑_j=t-t̂^t-1 (1-q)^t-j-1G^ω_j +G_j^θ+  G_j^η

2C_ϕ^2 C_M1/T∑_i=0^t̂-1 ∑_t=t̂-i ^t'+T-1 (1-q)^i
J(ω_t-i)- J(ω_t-i-1)

+ 4 B^2+  R_max^2/T+1/T∑_t=t'^t'+T-1  ∑_j=t-t̂^t-1 (1-q)^t-j-1G^ω_j +G_j^θ+  G_j^η

2 C_ϕ^2 C_M1/T∑_i=0^t̂-1  (1-q)^i
J(ω_t'+T-i-1)- J(ω_t'-i-1)

+ 4 B^2+  R_max^2/T+1/T∑_t=t'^t'+T-1  ∑_j=t-t̂^t-1 (1-q)^t-j-1G^ω_j +G_j^θ+  G_j^η

2C_ϕ^2 C_M1/T∑_i=0^t̂-1  (1-q)^i
J(π^*)- J(ω_t'-i-1)

+ 4 B^2+  R_max^2/T+1/T∑_t=t'^t'+T-1  ∑_j=t-t̂^t-1 (1-q)^t-j-1G^ω_j +G_j^θ+  G_j^η

≤2C_ϕ^2 C_M1/T∑_i=0^t̂-1
J(π^*)- J(ω_t'-i-1)

+ 4 B^2+  R_max^2/T+1/T∑_t=t'^t'+T-1  ∑_j=t-t̂^t-1 (1-q)^t-j-1G^ω_j +G_j^θ+  G_j^η,
where $(a)$ follows from that we set $i=t-j-1$, $(b)$
follows from the fact that $\sum_{t=\hat t-i }^{t'+\widetilde T-i-1}  \brac{\E \Fbrac{J(\omega_{t-i})}- \E \Fbrac{J(\omega_{t-i-1})} }= \E\Fbrac{J(\omega_{t'+\widetilde T-i-1}) }- \E \Fbrac{J(\omega_{t'-i-1})}$ and $(c)$ follows from $J(\pi^*)\geq J(\pi_{t'+\widetilde T-i-1}) $.

We denote by  $X_{t'}= \frac{1}{\hat t}\sum_{t=t'-\hat t}^{t'-1} \brac{J(\pi^*)- \E \Fbrac{J(\omega_t)} } $ and  $Y_{t'}=\frac{1}{\widetilde T}\sum_{t=t'}^{t'+\widetilde T-1} \brac{J(\pi^*)- \E \Fbrac{J(\omega_t)} } $.
We have that
there must exist $t'+\hat{t}\leq t''\leq t'+\widetilde T$ s.t.
$X_{t''}\leq Y_{t'} $.

We prove the lemma by contraction.  Assume that there does not exist $t'+\hat{t}\leq t''\leq t'+\widetilde T$ s.t.
$X_{t''}\leq Y_{t'} $. Then, for any $t'+\hat{t}\leq t''\leq t'+\widetilde T$, $X_{t''}> Y_{t'} $.

Next, recall $\widetilde T={\myceil{\frac{T}{\hat t\log T}}}\hat t$, then we have that

Y_t'   = 1/T∑_t=t'^t'+T-1 J(π^*)- J(ω_t)
= 1/T/t̂logT∑_τ=1^T/t̂logT1/t̂∑_t=t'+(τ-1) t̂^t'+τt̂-1J(π^*)- J(ω_t)

= 1/T/t̂logT∑_τ=1^T/t̂logT X_t'+τt̂>a 1/T/t̂logT∑_τ=1^T/t̂logT Y_t'=Y_t',
where $(a)$ follows from $t'+\hat{t}\leq t'+\tau \hat t\leq t'+\widetilde T$, $X_{t+\tau \hat t}> Y_{t'}  $ for $\tau=1,...,\myceil{\frac{T}{\hat t\log T}}$. This hence results in a contradiction, which completes the proof.

We then discuss the following two cases.

§.§.§ Case 1:
[For any $2k+ \hat t \leq  t' \leq   T -\widetilde T$, it holds that $ e Y _{ t'}<  X_{ t'}$.]

Then, for $\widetilde t_0=2k+ \hat t$, we have
$X_{\widetilde t_0}> e Y _{\widetilde t_0} $.  Recall that $\widetilde T={\myceil{\frac{T}{\hat t\log T}}}\hat t\leq \brac{\frac{T}{\hat t\log T}+1}\hat t\leq \frac{T}{ \log T}+\hat t\leq \frac{2T}{ \log T}$ for large $T$. Then, $\frac{T}{\widetilde T}\geq \frac{\log T}{2} \geq \lfloor \frac{\log T}{2} \rfloor$.

Thus, there  exist $\widetilde t_0+\hat{t} \leq  \widetilde t_1\leq \widetilde t_0 +\widetilde T$, s.t.
$X_{\widetilde t_1}\myineq{\leq}{a} Y _{\widetilde t_0}\myineq{<}{b} \frac{1}{e} X _{\widetilde t_0}$, where $(a)$ follows from <Ref> and $(b)$ follows from the condition of case 1.
Recursively applying the above argument, we have that for $j=0,1,...,\lfloor \frac{\log T}{2} \rfloor$, there exists $\widetilde t_j+\hat t\leq \widetilde t_{j+1}\leq \widetilde t_j +\widetilde T$, such that $X_{\widetilde t_{j+1}}\leq Y _{\widetilde t_j}< \frac{1}{e} X _{\widetilde t_j}$. This further implies that

X _t_0> e Y _t_0
≥e X _t_1> e^2
Y _t_1≥...≥e^j Y _t_j> e^j+1Y _t_j≥...≥e ^⌊logT/2 ⌋X_t_⌊logT/2 ⌋ > e^⌊logT/2 ⌋+1Y_t_⌊logT/2 ⌋.

Then, by <Ref>, we can conclude that
Y_t_⌊logT/2 ⌋:
=1/T∑_t=t_⌊logT/2 ⌋^t_⌊logT/2 ⌋+T-1 J(π^*)- J(ω_t)
≤1/√(T)X _t_0.

Note that $X_{\widetilde t}\leq J(\pi ^*)\leq R_{\max}$, hence we have that

= 1/T∑_t=t_⌊logT/2⌋^t_⌊logT/2⌋+T-1 J(π^*)- J(ω_t)

This further implies that

min_t≤T J(π^*)-J(ω_t)  ≤R_max/√(T).

This hence completes the proof of <Ref> under Case 1.

§.§.§ Case 2:
[There exists some $2k+ \hat t \leq  t' \leq T -\widetilde T $ s.t. $ X _{ t '}\leq e Y_{ t'}$.]

Define $Z_{t'}=\frac{1}{\widetilde T}\sum_{t=t'}^{t'+\widetilde T-1} M_t$. From <Ref>, we obtain that

Z_t'   = 1/T∑_t=t'^t'+T-1
M_t  ≤2 C_ϕ^2 C_M1/T∑_i=0^t̂-1
J(π^*)- J(ω_t'-i-1)

+ 4 B^2+  R_max^2/T+1/T∑_t=t'^t'+T-1  ∑_j=t-t̂^t-1 (1-q)^t-j-1G^ω_j +G_j^θ+  G_j^η

2C_ϕ^2 C_Mt̂/TX_t'
+ 4 B^2+  R_max^2/T+1/T∑_t=t'^t'+T-1  ∑_j=t-t̂^t-1 (1-q)^t-j-1G^ω_j +G_j^θ+  G_j^η

2C_ϕ^2 C_Me t̂/TY_t'
+ 4 B^2+  R_max^2/T+1/T∑_t=t'^t'+T-1  ∑_j=t-t̂^t-1 (1-q)^t-j-1G^ω_j +G_j^θ+  G_j^η,
where $(a)$ follows from the condition of Case 2.

Next, from <Ref>, we have that

Y_t'   =1/T∑_t=t'^t'+T-1 J(π^*)-J(ω_t)

≤(ω_t')-(ω_t'+T) /βT
+ C_ϕC_gap m ρ^k /λ_min
+ C_∞√(ε_actor )
+C_ϕ√(1/T∑_t=t'^t'+T-1 M_t)
=(ω_t')-(ω_t'+T) /βT
+ C_ϕC_gap m ρ^k /λ_min
+ C_∞√(ε_actor )

Plug <Ref> in <Ref>, and we have that

Z_t'    =1/T∑_t=t'^t'+T-1

≤4 B^2+  R_max^2/T+1/T∑_t=t'^t'+T-1  ∑_j=t-t̂^t-1 (1-q)^t-j-1G^ω_j +G_j^θ+  G_j^η+2e  C_ϕ^2 C_Mt̂/T  C_ϕC_gap m ρ^k /λ_min+B^2L_ϕ/2β

+ 2C_ϕ^2 C_Me t̂/T(ω_t')-(ω_t'+T) /βT
+ C_∞√(ε_actor )

≤a  4 B^2+  R_max^2/T + 1/T∑_t=t'^t'+T-1  ∑_j=t-t̂^t-1 (1-q)^t-j-1G^ω_j +G_j^θ+  G_j^η+ 2e  C_ϕ^2 C_M t̂/T  C_ϕC_gap m ρ^k /λ_min

+ 2e C_ϕ^3 C_M  t̂/T^2+1/2 Z_t'
+ C^2_∞ε_actor/2 C^2_ϕ
+ 2C_ϕ^2 C_Me t̂/T(ω_t')-(ω_t'+T) /βT
where $(a)$ follows from $ xy\leq \frac{x^2+y^2}{2}$

Thus, it follows that

≤8 B^2+  2R_max^2/T + 2/T∑_t=t'^t'+T-1  ∑_j=t-t̂^t-1 (1-q)^t-j-1G^ω_j +G_j^θ+  G_j^η
+ 22e C_ϕ^3 C_M  t̂/T^2+  C^2_∞ε_actor/C^2_ϕ

+ 4C_ϕ^2 C_Me t̂/T(ω_t')-(ω_t'+T) /βT
+ 4e  C_ϕ^2 C_M t̂/T  C_ϕC_gap m ρ^k /λ_min

Then, we get that

Y_t'   ≤(ω_t')-(ω_t'+T) /βT
+ C_ϕC_gap m ρ^k /λ_min
+ C_∞√(ε_actor )
+C_ϕ√(1/T∑_t=t'^t'+T-1 M_t)
≤(ω_t')-(ω_t'+T) /βT
+ C_ϕC_gap m ρ^k /λ_min
+2 C_∞√(ε_actor )
+C_ϕ√(2)2 e C_ϕ^3 C_M  t̂/T

+C_ϕ√(2)√( 1/T∑_t=t'^t'+T-1  ∑_j=t-t̂^t-1 (1-q)^t-j-1G^ω_j +G_j^θ+  G_j^η )
+ C_ϕ√(2)√(4 B^2+  R_max^2/T )

+2C_ϕ√( C_ϕ^2 C_Me t̂/T(ω_t')-(ω_t'+T) /βT
+2C_ϕ√(e t̂ C_ϕ^2 C_M /T  C_ϕC_gap m ρ^k /λ_min
+B^2L_ϕ/2β )

which proves the claim under Case 2.

Thus, combine the Case 1 result in  <Ref> and the Case 2 result in <Ref>,  we have that

min_t≤T    J(π^*)-J(ω_t)

≤(ω_t')-(ω_t'+T) /βT
+ C_ϕC_gap m ρ^k /λ_min
+2 C_∞√(ε_actor )
+C_ϕ√(2)2e C_ϕ^3 C_M  t̂/T + C_ϕ√(2)√(4 B^2+  R_max^2/T )

+C_ϕ√(2)√( 1/T∑_t=t'^t'+T-1  ∑_j=t-t̂^t-1 (1-q)^t-j-1G^ω_j +G_j^θ+  G_j^η )
+2 C_ϕ√( C_ϕ^2 C_Me t̂/T(ω_t')-(ω_t'+T) /βT

+2C_ϕ√(e t̂ C_ϕ^2 C_M /T  C_ϕC_gap m ρ^k /λ_min
+B^2L_ϕ/2β )

which completes the proof.

Next, we prove <Ref>.
(Restatement of <Ref>)
Consider the NAC algorithm in  <Ref> with constant step sizes that $\gamma\geq\alpha\geq\beta $, then it holds that

min_t≤T     J(π^*)-J(ω_t)

+ 𝒪√(log^3T)/T√(αβ)

+ 𝒪√(γβlog^2T) /√(α)
+ 𝒪γ√(logT) /√(α)
+ 𝒪√(αlog^3 T )
+ 𝒪√(βlog^3 T)

+𝒪√((mρ^k) logT)
+ 𝒪√((mρ^k)β/α)
+ 𝒪√((mρ^k)γ/α)
+ 𝒪mρ^k/√(αβ) +

If we set $\gamma=\mathcal{O}(T^{-\frac{2}{3}}\log T),  \alpha=\mathcal{O}(T^{-\frac{2}{3}}\log^{-1}T),  \beta =\mathcal{O}(T^{-\frac{2}{3}}\log^{-1}T)$, we have

min_t≤T  J(π^*)-J(ω_t)≤𝒪T^-1/3log^3T
+ 𝒪√(ε_actor).

From <Ref>, we have that

min_t≤T    J(π^*)-J(ω_t)

≤(ω_t')-(ω_t'+T) /βT
+ C_ϕC_gap m ρ^k /λ_min
+2 C_∞√(ε_actor )
+C_ϕ√(2)2e C_ϕ^3 C_M  t̂/T + C_ϕ√(2)√(4 B^2+  R_max^2/T )

+C_ϕ√(2)√( 1/T∑_t=t'^t'+T-1  ∑_j=t-t̂^t-1 (1-q)^t-j-1G^ω_j +G_j^θ+  G_j^η )
+2C_ϕ√( C_ϕ^2 C_Me t̂/T(ω_t')-(ω_t'+T) /βT

+2C_ϕ√(e t̂ C_ϕ^2 C_M /T  C_ϕC_gap m ρ^k /λ_min
+B^2L_ϕ/2β )

We then set the stepsize as follows:

γ   =T^-2/3logT;

α   = minλ̅_min/(k+1)^2 C^2_ϕγ,3/2λ̅_min=𝒪T^-2/3log^-1 T ;

β   =minλ̅_min/4(2C_Θ+1)α,  λ̅_min/12 C_ϕ^4 C_Mα =𝒪T^-2/3log^-1 T .

Recall that

q= λ̅_min α/2 =𝒪α;

t̂= 1/qlogT=𝒪logT/α ;
T=T/t̂logTt̂=𝒪T/logT .

Applying the above stepsizes in <Ref>, for $t\leq T $, we can have that

G^η_t=𝒪(mρ^k)γ+β^2+k^2βγ+k γ^2  =𝒪T^-4/3 log^3 T ;

G_t^θ=𝒪k (mρ^k)α+(m ρ^k)^2/β+k^3α^2+k^3 αβ+β^2 =𝒪T^-4/3 logT ;

G_t^ω=𝒪(mρ^k)β+β^2=𝒪T^-4/3log^-2 T.

Besides,  we have that $\D (\omega_i)=\E_{D_{\pi^*}}\Fbrac{\log\brac{\frac{\pi^*(a|s)}{\pi_{\omega_i}(a|s)}
}}\leq \E_{D_{\pi^*}}\Fbrac{\log\brac{\frac{D_{\pi^*}(s,a)}{D_{\pi_{\omega_i}}(s,a)}}}\myineq{\leq}{a}\log C_\infty$,
where $(a)$ follows from Assumption <ref>.

Thus, it holds that

√( 1/T∑_t=t'^t'+T-1  ∑_j=t-t̂^t-1 (1-q)^t-j-1G^ω_j +G_j^θ+  G_j^η )=𝒪T^-1/3 log^2 T.

Plugging the above equations to <Ref>
, we have that

min_t≤T J(π^*)-J(ω_t)
≤T^-1/3log^3 T+𝒪√(ε_actor) .

This concludes the proof.

§ PROOF OF LEMMAS

Recall the definition of $\nabla J(\omega)$ in <Ref>:

∇J(ω)= _D_π_ω Q^π_ω(s,a) ϕ_ω(s,a),

which implies that

=   _D_π_ω Q^π_ω(s,a)ϕ_ω(s,a)

_D_π_ωϕ^⊤_ω(s,a) θ̅^*_ωϕ_ω(s,a)

≤C_ϕ^2  θ^*_ω+θ̅^*_ω-θ^*_ω

≤b   C^2_ϕB+ C_gap m ρ^k/λ_min=C_J,

where $(a)$ follows from <Ref> and $(b)$ follows from <Ref>.
It hence proves the first claim.
The second claim is proved in Lemma A.1 in [Wu et al., 2020].

Recall that $F_{\omega} = \E_{D_{\pi_\omega}}\Fbrac{\phi_{\omega}(s,a) \phi^\top_{\omega}(s,a) }$. From the definition of $ \bar \theta^*_\omega$ in <Ref>, it can be verified that

θ̅^*_ω=F_ω^-1 ∇J(ω).

θ̅^*_ω- θ̅^*_ω'

= F_ω^-1 ∇J(ω)- F_ω'^-1 ∇J(ω')

≤F_ω^-1∇J(ω)- F_ω'^-1 ∇J(ω) +
F_ω'^-1 ∇J(ω)- F_ω'^-1 ∇J(ω')

≤aF_ω^-1  F_ω'^-1  F_ω-F_ω' ∇J(ω)
+ (F_ω')^-1 ∇J(ω)-∇J(ω') ,

where $(a)$ follows from <Ref>.

Note that  $F_{\omega}$ can be shown to be Lipschitz as follows:

F_ω-F_ω'    =
_D_π_ωϕ_ω(s,a) ϕ^⊤_ω(s,a) -_D_π_ω'ϕ_ω'(s,a) ϕ^⊤_ω'(s,a)

≤_D_π_ωϕ_ω(s,a) ϕ^⊤_ω(s,a) -_D_π_ωϕ_ω'(s,a) ϕ^⊤_ω'(s,a)

_D_π_ωϕ_ω'(s,a) ϕ^⊤_ω'(s,a) -_D_π_ω'ϕ_ω'(s,a) ϕ^⊤_ω'(s,a)

≤2 C_ϕL_ϕω'-ω
+ C^2_ϕD_π_ω-D_π_ω'

2 C_ϕL_ϕω'-ω
+ C^2_ϕL_πω-ω' ,

where $(a)$ follows from [Zou et al., 2019] and Theorem 1 in [Li et al., 2021], that

D_π_ω-D_π_ω' ≤L_πω-ω' .

Hence combining <Ref>, <Ref> and Lemma <ref>, we obtain that

θ̅^*_ω-θ̅^*_ω'    ≤C_J/λ^2_min
2 C_ϕL_ϕ+C^2_ϕL_π+ L_J/λ_minω-ω'.

This completes the proof.

From the definition of $H_\omega$ in <Ref>, we first have that

H_ω   =
_D_π_ω ϕ_ω(s_0,a_0)ϕ_ω(s_k,a_k)-ϕ_ω(s_0,a_0) ^⊤|s_0=s,a_0=a,π_ω

_D_π_ω ϕ_ω(s,a) ϕ_ω^⊤(s_k,a_k)|s_0=s,a_0=a,π_ω-_D_π_ωϕ_ω^⊤(s,a)

-_D_π_ω ϕ_ω(s,a)ϕ_ω^⊤(s,a),

where $(a)$ follows from $ \phi_\omega(s,a)=\nabla \log \pi_\omega(a|s)$  and $\E_{D_{\pi_\omega}}\Fbrac{\phi_\omega^\top(s,a) f(s)}=0 $, where $f(s)$ is the function which is not determined by action $a$.

Define $\Delta H_\omega= \E_{D_{\pi_\omega}} \Fbrac{\phi_\omega(s,a)\brac{\E \Fbrac{ \phi_\omega^\top(s_k,a_k)|s_0=s,a_0=a,\pi_\omega}-\E_{D_{\pi_\omega}}\Fbrac{\phi_\omega^\top(s,a)} }}$. Thus,

H_ω+H_ω^⊤/2=ΔH_ω+ ΔH_ω^⊤/2-_D_π_ω ϕ_ω(s,a)ϕ_ω^⊤(s,a).

For any symmetric matrices $X$ and $Y$, $ \lambda_{\max}\brac{X+Y }\leq \lambda_{\max}\brac{X}+\lambda_{\max}\brac{Y} $.
Thus,   we have that

λ_maxH_ω+H_ω^⊤/2      ≤λ_maxΔH_ω+ ΔH_ω^⊤/2
+λ_max-_D_π_ω ϕ_ω(s,a)ϕ_ω^⊤(s,a)

P(s_k,a_k|s_0=s,a_0=s,π_ω), D_π_ω-λ_min

≤d C_ϕ^2 m ρ^k -λ_min=-λ̅_min ,
where last inequality follows from Assumption <ref>.

Conditioned on $(s_{t-k},a_{t-k})$, the sample trajectory in <Ref> is generated according to the following Markov chain:

(s_t-k,a_t-k)π_t-k ×P(s_t-k+1,a_t-k+1)π_t-k+1 ×P
...(s_t,a_t)π_t ×P(s,a).

Using the technique in  [Zou et al., 2019], we construct an auxiliary Markov chain as follows. Before time $t-k$, the states and actions are generated according to <Ref>; and after time $t-k$, all the subsequent state-action pairs, denoted by $(\widetilde s_l,\widetilde a_l)$, are generated according to a fixed policy $\pi_t$ and transition kernel $P$:

(s_t-k,a_t-k)π_t ×P(s_t-k+1,a_t-k+1)π_t ×P...(s_t,a_t)π_t ×P(s,a).

Denote by $\widetilde {\mathcal{F}}_{t}$ the filtration corresponding to the auxiliary Markov chain designed in <Ref>.

Then follow steps similar to those in <cit.> and <cit.>, it can be shown that

≤mρ^k+ ∑_j=t-k^t C_πω_t-ω_j.

Define the sum of the feature along the trajectory as follows:

\begin{align}
z_t= \sum_{j=t-k}^t \phi_j(s_j,a_j),\quad
\hat{z}_t=\sum_{j=t-k}^t \phi_t(s_j,a_j)
\text{ and } \widetilde{z_t}=\sum_{j=t-k}^t \phi_t(\widetilde s_j,\widetilde a_j).
\end{align}

For every policy $\pi_t$, we construct another auxiliary Markov chain, denoted by $\{\brac{\bar s_j,\bar a_j} \}_{j=0}^\infty$, which is under the stationary distribution induced by policy $\pi_t$ and transition kernel $P$, i.e.,

and all the subsequent actions are generated by $\pi_t$. Define z̅_t=∑_j=t-k^t ϕ_t(s̅_j,a̅_j).

Denote by $\bar \delta_t(\bar s_t,\bar a_t;\theta_t,\omega_t)=R(\bar s_t,\bar a_t)-J(\omega_t)+\phi_t^\top(\bar s\tit,\bar a\tit)\theta_t-\phi_t^\top(\bar s_t,\bar a_t)\theta_t $.

It holds that

From the definition in <Ref>, $\thestar$ is the fixed point of the $k$-step TD operator $\mathcal{T}_{\pi_t}^{(k)}$.  Then, it follows that

_ D_t ϕ^⊤_t(s,a)𝒯_π_t^(k)ϕ_t^⊤(s,a) -ϕ_t^⊤(s,a)

Together with Lemma <ref>, we have that

z̅_t δ̅_t(s̅_t,a̅_t;,ω_t)=0.

Thus we have that

θ_t-, z̅_t δ̅_t(s̅_t,a̅_t;θ_t, ω_t)
=θ_t-, z̅_t δ̅_t(s̅_t,a̅_t;θ_t, ω_t)-z̅_t δ̅_t(s̅_t,a̅_t;, ω_t)

θ_t-,H_ω_t θ_t-

≤λ_max H_ω_t+H_ω_t^⊤/2 θ_t-

≤a  -λ̅_min  θ_t-,

where $(a)$ follows from <Ref>.

Then, recall $\hat{z}_t=\sum_{j=t-k}^t \phi_t(s_j,a_j)$. Denote by $\hat \delta_t= R(s_t,a_t)-J(\omega_t)+ \phi^\top_t(s\tit,a\tit)\theta_t -\phi^\top_t(s_t,a_t)\theta_t$, we have that

θ_t-, δ_t z_t
θ_t-, z̅_tδ̅_t(s̅_t,a̅_t;θ_t, ω_t)
+θ_t-, z_t δ̂_t- z̅_tδ̅_t(s̅_t,a̅_t;θ_t, ω_t)

θ_t-,z_t  δ_t- ẑ_tδ̂_t

+ θ_t-, z_tδ̂_t- z̅_tδ̅_t(s̅_t,a̅_t;θ_t)

+θ_t-,z_t  J(ω_t)-η_t

+ θ_t-, z_tδ̂_t- z̅_tδ̅_t(s̅_t,a̅_t;θ_t)

+λ̅_min/2θ_t-+ (k+1)^2 C^2_ϕ/2λ̅_minJ(ω_t)-η_t,

where  $(a)$ follows from <Ref>.

Consider the term
$\E\fvbrac{\theta_t-\thestar,z_t \hat \delta_t- \bar z_t\bar \delta_t(\bar s_t,\bar a_t;\theta_t, \omega_t)} $, and we have that

θ_t-,z_tδ̂_t- z̅_tδ̅_t(s̅_t,a̅_t;θ_t, ω_t)

= θ_t-θ_t-2k-+θ^*_t-2k,z_tδ̂_t- z̅_tδ̅_t(s̅_t,a̅_t;θ_t, ω_t)

+θ_t-2k-θ^*_t-2k,z_tδ̂_t- z̅_tδ̅_t(s̅_t,a̅_t;θ_t, ω_t)

≤ θ_t-θ_t-2k+-θ^*_t-2k  z_tδ̂_t+z̅_tδ̅_t(s̅_t,a̅_t;θ_t, ω_t) _(i)

+ θ_t-2k-θ^*_t-2k,z_tδ̂_t- ẑ_tδ̂_t _(ii)

+θ_t-2k-θ^*_t-2k,ẑ_tδ̂_t- z̅_t δ̅_t(s̅_t,a̅_t;θ_t, ω_t) _(iii).

In AC algorithm, recall $U_\delta =R_{\max}+2 C_\phi B$. Then, consider  $ \twonorm{\theta_t-\theta_{t-2k}}$ and $ \twonorm{\thestar-\theta^*_{t-2k}}$,  we have that

θ_t-θ_t-2k≤∑_j=t-2k^t-1 α_j δ_j z_j
≤∑_j=t-2k^t-1 α_j δ_j z_j
≤a (k+1) C_ϕU_δ∑_j=t-2k^t-1 α_j ,
where $(a)$ follows from the fact that $\twonorm{z_t}\leq (k+1) C_\phi$.

Then, it can be shown that

= -θ̅^*_t-2k+ -+θ̅^*_t-2k-θ^*_t-2k

≤-θ̅^*_t-2k + -+θ̅^*_t-2k-θ^*_t-2k

≤C_Θω_t-ω_t-2k +  C_gapm ρ^k/λ_min
+ C_gapm ρ^k/λ_min

≤C_Θ ∑_j=t-2k^t-1 β_j ϕ_j^⊤(s_j,a_j)θ_j ϕ_j(s_j,a_j) + 2C_gapm ρ^k/λ_min

≤C_ΘC^2_ϕB ∑_j=t-2k^t-1 β_j+
2C_gapm ρ^k/λ_min.

Thus, from <Ref>, the term $(i)$ in <Ref> can be bounded as follows:

(i)≤2(k+1) C_ϕU_δ(k+1) C_ϕU_δ∑_j=t-2k^t-1 α_j+ C_ΘC^2_ϕB ∑_j=t-2k^t-1 β_j +2C_gapm ρ^k/λ_min.

Then, for term $(ii)$ in <Ref>, it can be bounded as follows:

(ii)   ≤ θ_t-2k-θ^*_t-2k
≤2B U_δ∑_j=t-k^t ϕ_j(s_j,a_j)-ϕ_t(s_j,a_j)

≤2BU_δ∑_j=t-k^t C_πω_t-ω_j
≤2B U_δC_π∑_j=t-k^t ∑_i=j^t β_i ϕ_i^⊤(s_i,a_i)θ_i ϕ_i(s_i,a_i)

≤2B^2 C^2_ϕU_δC_π∑_j=t-k^t ∑_i=j^t β_i .

Next, for term $(iii)$ in <Ref>, we can show that

(iii)    =θ_t-2k-θ^*_t-2k, ẑ_t δ̂_t-z̅_tδ̅_t(s̅_t,a̅_t;θ_t)

=θ_t-2k-θ^*_t-2k,ẑ_t δ̂_t-z̅_tδ̅_t(s̅_t,a̅_t;θ_t)|ℱ_t-2k

≤4B   C_ϕU_δ∑_j=t-k^t s_j,a_j|ℱ_t-2k-D_t

≤4  B C_ϕU_δ∑_j=t-k^t s_j,a_j|ℱ_t-2k-D_j+ D_j-D_t

≤4  B C_ϕU_δ∑_j=t-k^t
C_π∑_i=j-k^j-1 ω_i-ω_j+ mρ^k+L_πω_t-ω_j

≤4  B C_ϕU_δ∑_j=t-k^t
C_π∑_i=j-k^j-1 ∑_ι=i^j-1 β_ιC^2_ϕB + mρ^k+L_π∑_i=j^t-1 β_i C^2_ϕB .

Thus, combining <Ref>, <Ref> and <Ref>, we can bound  term  as follows:

θ_t-, δ_t z_t
≤- λ̅_min/2 θ_t-
+(k+1)^2 C^2_ϕ/2λ̅_minJ(ω_t)-η_t

+2B^2 C^2_ϕU_δC_π∑_j=t-k^t ∑_i=j^t β_i
+4  B C_ϕU_δ∑_j=t-k^t
B C^2_ϕC_π∑_i=j-k^j-1 ∑_ι=i^j-1 β_ι+ mρ^k+ BC^2_ϕL_π∑_i=j^t-1 β_i

+  2(k+1) C_ϕU_δ(k+1) C_ϕU_δ∑_j=t-2k^t-1 α_j+ C_ΘC^2_ϕB ∑_j=t-2k^t-1 β_j+2C_gapm ρ^k/λ_min.

In NAC algorithm,

terms $ \twonorm{\theta_t-\theta_{t-2k}}$ and $ \twonorm{\thestar-\theta^*_{t-2k}}$ can be bounded as follows:

θ_t-θ_t-2k≤∑_j=t-2k^t-1 α_j δ_j z_j
≤(k+1) C_ϕU_δ∑_j=t-2k^t-1 α_j ,

= -θ̅^*_t-2k+ -+θ̅^*_t-2k-θ^*_t-2k

≤-θ̅^*_t-2k + -+θ̅^*_t-2k-θ^*_t-2k

≤C_Θω_t-ω_t-2k +  C_gapm ρ^k/λ_min
+ C_gapm ρ^k/λ_min

≤C_Θ ∑_j=t-2k^t-1 β_j θ_j  + 2C_gapm ρ^k/λ_min

≤C_ΘB ∑_j=t-2k^t-1 β_j+
2C_gapm ρ^k/λ_min.

Thus, using <Ref> and <Ref>, term $(i)$ in <Ref> can be bounded as

(i)≤2(k+1) C_ϕU_δ(k+1) C_ϕU_δ∑_j=t-2k^t-1 α_j+ C_ΘB ∑_j=t-2k^t-1 β_j +2C_gapm ρ^k/λ_min.

Next, we bound the term $(ii)$ in <Ref> as follows:

(ii)   ≤θ_t-2k-θ^*_t-2k
≤2B U_δ∑_j=t-k^t ϕ_j(s_j,a_j)-ϕ_t(s_j,a_j)

≤2BU_δ∑_j=t-k^t C_πω_t-ω_j
≤2B U_δC_π∑_j=t-k^t ∑_i=j^t-1 β_i θ_i
≤2B^2  U_δC_π∑_j=t-k^t ∑_i=j^t-1 β_i .

Term $(iii)$ in <Ref> can be bounded as

(iii)    =θ_t-2k-θ^*_t-2k, ẑ_t δ_t(θ_t)-z'_tδ'_t(θ_t)

=θ_t-2k-θ^*_t-2k, ẑ_t δ_t(θ_t)-z'_tδ'_t(θ_t) |ℱ_t-2k

≤2B 2  C_ϕU_δ∑_j=t-k^t s_j,a_j|ℱ_t-2k-D_t

≤4  B C_ϕU_δ∑_j=t-k^t s_j,a_j|ℱ_t-2k-D_j+ D_j-D_t

≤4  B C_ϕU_δ∑_j=t-k^t
C_π∑_i=j-k^j-1 ω_i-ω_j+ mρ^k+L_πω_t-ω_j

≤4  B^2 C_ϕU_δ∑_j=t-k^t
C_π∑_i=j-k^j-1 ∑_ι=i^j-1 β_ι+ mρ^k+L_π∑_i=j^t-1 β_i  .

Combining the above bounds on terms $(i),(ii),(iii)$,  term can be bounded as

θ_t-, δ_t z_t

≤    - λ̅_min/2 θ_t-
+(k+1)^2 C^2_ϕ/2λ̅_minJ(ω_t)-η_t
+2B^2 U_δC_π∑_j=t-k^t ∑_i=j^t-1 β_i

+ 2(k+1) C_ϕU_δ(k+1) C_ϕU_δ∑_j=t-2k^t-1 α_j+ C_ΘB ∑_j=t-2k^t-1 β_j+2C_gapm ρ^k/λ_min

+4  B C_ϕU_δ∑_j=t-k^t
B C_π∑_i=j-k^j-1 ∑_ι=i^j-1 β_ι+ mρ^k+B L_π∑_i=j^t-1 β_i  .

This completes the proof.

From $\nabla^2 J(\omega)= \sum_{s,a}\nabla^2 D_{\pi_\omega}(s,a) R(s,a) $, we can get that for any $\omega,\omega'\in \mathbb R^d$

∇^2 J(ω)-∇^2 J(ω')    =  ∑_s,a∇^2 D_π_ω(s,a) R(s,a)-∇^2 D_π_ω'(s,a) R(s,a)

Denote by $\boldsymbol{\sigma}(A)$ the spectral radius of matrix $A\in \mathbb R^{n\times n}$.
Recall the fact that
\boldsymbol{\sigma}(A)\leq \mynorm{A}_\infty= \max_i\varbrac{\sum_j\lbrac{a_{ij}}}.
If $A$ is symmetric matrix, $\twonorm{A}=\boldsymbol{\sigma}(A)$, and thus
\twonorm{A}\leq \max_i\varbrac{\sum_j\lbrac{a_{ij}}}.

It is clear that $\nabla^2 D_{\pi_\omega}(s,a)$ is symmetric, and therefore $\sum_{s,a}(\nabla^2 D_{\pi_\omega}(s,a)-\nabla^2 D_{\pi_{\omega'}}(s,a))R(s,a)$ is also symmetric. It then follows that

∑_s,a∇^2 D_π_ω(s,a)-∇^2 D_π_ω'(s,a)R(s,a)

≤max_i∑_j ∑_s,a ∂_ω_i∂_ω_jD_π_ω(s,a) -∂_ω_i∂_ω_jD_π_ω'(s,a) R(s,a)

=amax_i∑_j ∇_ω∑_s,a ∂_ω_i∂_ω_jD_π_ω̂(s,a)R(s,a)^⊤(ω-ω')

≤max_i∑_j ∇_ω∑_s,a ∂_ω_i∂_ω_jD_π_ω̂(s,a)R(s,a)ω-ω'

≤b max_i∑_j ∑_l  ∑_s,a ∂_ω_i∂_ω_j∂_ω_lD_π_ω̂(s,a)R(s,a)ω-ω'

≤max_i,j,l d^2 ∑_s,a∂_ω_i∂_ω_j∂_ω_lD_π_ω̂(s,a)R(s,a) ω-ω',
where $(a)$ follows from the fact that $D_{\pi_\omega}$ is $n$ times differentiable as long as the Theorem 4 in [Heidergott & Hordijk, 2003] and the Lagrange's Mean Value Theorem for some $\hat \omega =\lambda_{ij} \omega+(1-\lambda_{ij})\omega'$ with $\lambda_{ij}\in [0,1]$, and $(b)$ follows from that for a vector $a$, $\twonorm{a}\leq \mynorm{a}_1$.

Define a function $v: \mathcal{S}\times\mathcal{A}\to \mathbb R$, denote by $\mynorm{f}_v=\sup_{s,a}\frac{\lbrac{f(s,a)}}{\lbrac{v(s,a)}} $ the finite $v$-norm of function $f$. Set $v(s,a)=e^{R(s,a)}$ and we can get that

sup_s,aR(s,a) /v(s,a) ≤1.
Moreover,  $v(s,a)=e^{R(s,a)}\leq e^{R_{\max}}$ and $v(s,a)\geq 1$. If $\mynorm{f}_v\leq 1 $, it implies that

sup_s,a |f(s,a)|≤e^R_max.

For a (signed) measure $\mu$, the associated norm is

μ_v=sup_f_v≤1 ∑_s,a μ(s,a) f(s,a) .

For a kernel $P(s',a'|s,a)$, its associated norm is

∑_s',a'f(s',a') P(s',a'|s,a)  /v(s,a).

From the fact that  $\sup_{s,a}\frac{\lbrac{R(s,a)} }{\lbrac{v(s,a) }}\leq 1$, we can get that $||R||_v\leq 1$. This further implies that

∑_s,a ∂_ω_i∂_ω_j∂_ω_lD_π_ω̂(s,a)R(s,a)   ≤sup_f_v≤1∑_s,a ∂_ω_i∂_ω_j∂_ω_lD_π_ω̂(s,a)f(s,a)
=∂_ω_i∂_ω_j∂_ω_lD_π_ω̂ _v.

Furthermore, we define $\mathcal{K}^{(1)}_{\omega_i}(s,a)$, $\mathcal{K}^{(2)}_{\omega_{i,j}}(s,a)$ and $\mathcal{K}^{(3)}_{\omega_{i,j,l} }(s,a)$ as follows:

𝒦^(1)_ω_i(s,a|s',a')= ∑_ι=0^∞∂_ω_iπ_ω(a|s) s_ι=s,a_ι=a|s_0=s',a_0=a',π_ω-D_π_ω(s,a);

𝒦^(2)_ω_i,j(s,a|s',a')= ∑_ι=0^∞∂_ω_i∂_ω_jπ_ω(a|s) s_ι=s,a_ι=a|s_0=s',a_0=a',π_ω-D_π_ω(s,a);

𝒦^(3)_ω_i,j,l(s,a|s',a')= ∑_ι=0^∞∂_ω_i∂_ω_j∂_ω_lπ_ω(a|s) s_ι=s,a_ι=a|s_0=s',a_0=a',π_ω-D_π_ω(s,a).