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

Weaknesses 1: Restate compatible function approximation conclusion in eq. (5) in the form of a proposition and provide the proof.

Thanks for the suggestion. We have added the proof of eq. (5) in the revision. For convenience, we also include the proposition and the proof here.

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

\mathbb E_{D_{\pi_\omega}}[(Q^{\pi_\omega}(s,a)-\phi^\top_\omega(s,a)\bar \theta_\omega^*)\phi_\omega(s,a) ]=0.

Now we consider the policy gradient $\nabla J(\pi_\omega)$, and it can be shown that

Furthermore, for the natural policy gradient, we have that $$\widetilde{\nabla} J(\pi_\omega)= F_{\omega}^{-1} \mathbb E_{D_{\pi_\omega}}[\phi_\omega(s,a)\phi_\omega(s,a)^\top{\bar\theta}^\omega]=F\omega^{-1} \mathbb E_{D_{\pi_\omega}}[\phi_\omega(s,a)\phi_\omega(s,a)^\top ]\bar \theta^\omega=\bar \theta^*\omega.

Weaknesses 2: high-level roadmap of the proof. 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.

Proof Sketch: For simplicity of presentation, we set $\alpha_t=\alpha,\beta_t=\beta,\gamma_t=\gamma$, $\hat t=\lceil \frac{3\log T}{\bar \lambda_{\min}\alpha}\rceil$ and $\widetilde T=\hat t\lceil \frac{T}{\hat t \log T} \rceil$. We denote by $\pi^*$ the global optimal policy and $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:

$

\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 }+ \mathcal{O}\left(\sqrt{\frac{1}{\widetilde T}\sum_{j=t}^{t+\widetilde T-1} M_j}\right)+\mathcal{O}(C_\infty \sqrt{\varepsilon_{\text{actor}}}+ \beta+m\rho^k).

$

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:

$

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

$

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:

$||\theta_{t+1}-\theta_{t+1}^*||^2_2 \leq || \theta_t-\theta_{t}^* ||^2_2+ \alpha^2 ||\delta_t z_t||^2_2+|| \theta_{t}^*-\theta_{t+1}^*||_2^2$

$+ 2 \alpha\langle\theta_t-\theta_{t}^*, \delta_t z_t \rangle + 2\alpha \langle \delta_t z_t, \theta_{t}^* - \theta_{t+1}^* \rangle+ 2 \langle\theta_t-\theta_{t}^*, \theta_{t}^*-\theta_{t+1}^* \rangle.$

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\overset{\pi_t\times P}{\to}...\overset{\pi_t\times P}{\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\overset{\pi_t\times P}{\to}...\overset{\pi_t\times P}{\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)$.

Q1: Why can't one reuse the previous proofs, just replacing the policy gradient bias term by 0?

In previous AC works, e.g., (Wu et al.,2020) (Xu et al., 2020), the error in the critic is bounded by $\varepsilon_{\text{approx.}}=\sqrt{\mathbb E[(Q_{\pi_\omega}(s,a)-\phi^\top(s,a) \theta^*_\omega)^2]},$ where the $\theta_\omega^*$ is the limiting point of the critic under the policy $\pi_\omega$. Their analysis bound the bias in the gradient using the gap between the true $Q$ function and the critic output, $\varepsilon_{\text{approx.}}$, and this gap is typically non-zero. Their analysis are based on the implicit assumption that $\varepsilon_{\text{approx.}}$ will be small, and thus the critic returns an accurate estimation of the true $Q$ function.

We would like to highlight that using compatible function approximation, we do not need $\varepsilon_{\text{approx.}}$ to be small. This term $\varepsilon_{\text{approx.}}$ could be non-zero, however, by eq. (3), the policy gradient will still be unbiased. In other words, we do not need to get the exact $Q$ from the critic, as long as the critic solves eq. (2), the gradient will be unbiased using compatible function approximation. Therefore, the analysis is different, and cannot be obtained by simply letting $\varepsilon_{\text{approx.}}=0$.

Yue Frank Wu, Weitong Zhang, Pan Xu, and Quanquan Gu. "A finite-time analysis of two time-scale actor-critic methods." Advances in Neural Information Processing Systems, 33:17617–17628, 2020

Xu, Tengyu, Zhe Wang, and Yingbin Liang. "Non-asymptotic convergence analysis of two time-scale (natural) actor-critic algorithms." arXiv preprint arXiv:2005.03557 (2020).

Q2: What are the new difficulties due to compatible function approximation?

As we discussed in the proof sketch (provided above), the key challenge lies in the time-varying feature function due to the changing policy. Our key novelty lies in the design of auxiliary Markov chains and auxiliary eligibility trace as in Step 3 in the proof sketch.

Weaknesses and Questions: limitations of the analysis presented in this paper and how to verify the assumptions made in practice

I. As a theoretical analysis work, possible limitation of our work lies in whether the assumptions are reasonable and can be verified.

Assumption 1 of uniform ergodicity is a widely used assumption in RL analysis. A Markov chain is uniformly ergodic if it is irreducible (i.e., possibly get to any state from any state) and aperiodic (Levin & Peres 2017). Now consider an environment for which there exists a policy that can map any state to any state with nonzero probability (i.e., irreducibility holds) and gets back to the same state aperiodically. Such environments are commonly encountered in practice. Then for any $\omega$, as long as the policy explores (i.e., with non-zero probability to take any action at any state), the induced Markov chain remains to be irreducible and aperiodic, and is hence ergodic. Therefore, such an assumption is realistic, and is guaranteed for aforementioned environments. We also agree that if Assumption 1 does not hold, new techniques will be needed to understand the non-asymptotic error bounds of many RL algorithms.

Assumption 2 can be satisfied if we use some popular policy parameterization, such as softmax, neural network with analytic activation functions e.g., logistic, tanh, and softplus. These results can be found in (Du et al., 2019; Miyato et al. 2018; Neyshabur, 2017).

Assumption 3 can be satisfied if we carefully design the policy parameterization so that it is sufficiently explorative, e.g., softmax and $\epsilon$-greedy policy.

II. Another possible limitation in the algorithm and analysis is the use of the projection (Line 9 in Algorithm 1). We conjecture that this projection may not be necessarily needed to guarantee convergence and to derive the non-asymptotic bounds (see e.g., Srikant & Ying 2019). However, this projection helps to simplify the proof, and without which the proof will be rather cumbersome.

David A. Levin and Yuval Peres. Markov chains and mixing times. Vol. 107. American Mathematical Soc., 2017.

Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. "Gradient descent finds global minima of deep neural networks." International conference on machine learning. PMLR, 2019.

Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. "Spectral Normalization for Generative Adversarial Networks." International Conference on Learning Representations. 2018.

Neyshabur, Behnam. "Implicit regularization in deep learning." arXiv preprint arXiv:1709.01953 (2017).

Srikant, Rayadurgam, and Lei Ying. "Finite-time error bounds for linear stochastic approximation andtd learning." Conference on Learning Theory. PMLR, 2019.

Q 2: Importance of eliminating $\varepsilon_{\text{critic}}$ when it can be small in neural function approximation.

One may argue that using a rich (non-linear) function approximation in the critic, e.g., neural network, may also have a small function approximation error in the critic. However, as shown in the literature, e.g., (Cai et.al.,2023), TD with non-linear function approximation may require a strong condition to guarantee convergence. In contrast, using compatible function approximation in the critic has a guaranteed convergence. Moreover, as discussed in eq. (8), there is no need to estimate the inverse Fisher information matrix if we use compatible function approximation in NAC. This could significantly reduce the complexity of implementing the algorithm.

We are currently working on the suggested simulations, and will add them to the final version.

Cai, Q., Yang, Z., Lee, J. D., Wang, Z. (2023). Neural Temporal Difference and Q Learning Provably Converge to Global Optima. Mathematics of Operations Research.

Q 1.b Technical challenges. 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.

Proof Sketch: For simplicity of presentation, we set $\alpha_t=\alpha,\beta_t=\beta,\gamma_t=\gamma$, $\hat t=\lceil \frac{3\log T}{\bar \lambda_{\min}\alpha}\rceil$ and $\widetilde T=\hat t\lceil \frac{T}{\hat t \log T} \rceil$. We denote by $\pi^*$ the global optimal policy and $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:

$

\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 }+ \mathcal{O}\left(\sqrt{\frac{1}{\widetilde T}\sum_{j=t}^{t+\widetilde T-1} M_j}\right)+\mathcal{O}(C_\infty \sqrt{\varepsilon_{\text{actor}}}+ \beta+m\rho^k).

$

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:

$

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

$

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:

$||\theta_{t+1}-\theta_{t+1}^*||^2_2 \leq || \theta_t-\theta_{t}^* ||^2_2+ \alpha^2 ||\delta_t z_t||^2_2+|| \theta_{t}^*-\theta_{t+1}^*||_2^2$

$+ 2 \alpha\langle\theta_t-\theta_{t}^*, \delta_t z_t \rangle + 2\alpha \langle \delta_t z_t, \theta_{t}^* - \theta_{t+1}^* \rangle+ 2 \langle\theta_t-\theta_{t}^*, \theta_{t}^*-\theta_{t+1}^* \rangle.$

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\overset{\pi_t\times P}{\to}...\overset{\pi_t\times P}{\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\overset{\pi_t\times P}{\to}...\overset{\pi_t\times P}{\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)$.

Q 1.a: how the result in the paper compared with other non-asymptotic analyses with compatible function approximation.

The asymptotic convergence of actor-critic using compatible function approximation was derived in (Konda & Tsitsiklis 2003), and later (Peters & Schaal 2008) combined the idea of compatible function approximation with NAC, but did not provide any non-asymptotic convergence proof. Recently, non-asymptotic analysis of compatible function approximation for NAC was developed in (Agarwal et al. 2021) (Cayci et al. 2022) and (Wang et al. 2019). However, in these recent studies, they only employ the advantage that using compatible function approximation eliminates the need to estimate the Fisher information matrix and its inverse (as shown in eq. (8)). However, their critic design fails to obtain a solution to eq. (4), and therefore, their non-asymptotic error bounds still include the critic approximation error $\varepsilon_{\text{critic}}$. Our critic employs the $k$-step TD algorithm so that the critic converges to a solution to eq. (4). In this way, we could achieve a zero critic approximation error. Moreover, these studies are not for the single-loop setting, whereas in our paper, we focus on the single loop setting, which is more challenging to analyze.

Konda, Vijay R., and John N. Tsitsiklis. "Onactor-critic algorithms." SIAM journal on Control and Optimization 42.4 (2003): 1143-1166.

Peters, Jan, and Stefan Schaal. "Natural actor-critic." Neurocomputing 71.7-9 (2008): 1180-1190.

Alekh Agarwal,Sham M Kakade, Jason D Lee, and Gaurav Mahajan. "On the theory of policy gradient methods: Optimality, approximation, and distribution shift." The Journal of Machine Learning Research 22.1 (2021): 4431-4506.

Cayci, Semih, Niao He, and R. Srikant. "Finite-time analysis of entropy-regularized neural natural actor-critic algorithm." arXiv preprint arXiv:2206.00833 (2022).

Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. "Neural Policy Gradient Methods: Global Optimality and Rates of Convergence." International Conference on Learning Representations. 2019.

Qi Cai, Zhuoran Yang, Jason D Lee, and Zhaoran Wang. "Neural Temporal Difference and Q Learning Provably Converge to Global Optima." Mathematics of Operations Research (2023).

Weaknesses1: Details of this paper's novelty. 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.

Proof Sketch: For simplicity of presentation, we set $\alpha_t=\alpha,\beta_t=\beta,\gamma_t=\gamma$, $\hat t=\lceil \frac{3\log T}{\bar \lambda_{\min}\alpha}\rceil$ and $\widetilde T=\hat t\lceil \frac{T}{\hat t \log T} \rceil$. We denote by $\pi^*$ the global optimal policy and $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:

$

\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 }+ \mathcal{O}\left(\sqrt{\frac{1}{\widetilde T}\sum_{j=t}^{t+\widetilde T-1} M_j}\right)+\mathcal{O}(C_\infty \sqrt{\varepsilon_{\text{actor}}}+ \beta+m\rho^k).

$

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:

$

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

$

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:

$||\theta_{t+1}-\theta_{t+1}^*||^2_2 \leq || \theta_t-\theta_{t}^* ||^2_2+ \alpha^2 ||\delta_t z_t||^2_2+|| \theta_{t}^*-\theta_{t+1}^*||_2^2$

$+ 2 \alpha\langle\theta_t-\theta_{t}^*, \delta_t z_t \rangle + 2\alpha \langle \delta_t z_t, \theta_{t}^* - \theta_{t+1}^* \rangle+ 2 \langle\theta_t-\theta_{t}^*, \theta_{t}^*-\theta_{t+1}^* \rangle.$

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\overset{\pi_t\times P}{\to}...\overset{\pi_t\times P}{\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\overset{\pi_t\times P}{\to}...\overset{\pi_t\times P}{\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)$.

Weaknesses 2: Fair comparisons with discounted MDPs, and whether our approach can be generalized to the discounted setting

We agree with the reviewer that the average reward setting and the discounted setting are different. In general, the average MDP setting is more challenging to analyze than the discounted MDP setting due to the lack of the discount factor and thus the contraction property. It is possible to extend our methodology to the discounted MDP setting. For example, in the critic, we could use TD($\lambda$) with a large enough $\lambda$ to solve eq.(4). Our approach of designing auxiliary Markov chain and auxiliary eligibility trace could also be generalized to the discounted setting. It is also of interest to investigate in details the non-asymptotic error bound for the discounted MDP setting.

Q1: Practical and theoretical impact: how can the algorithmic idea and theoretical analysis be useful to develop and analyze other algorithms.

The algorithmic idea of compatible function approximation can be applied to a wide range of AC and NAC type algorithms e.g., in the multi-task, multi-agent and game settings, to get rid of the function approximation error in the critic. One may argue that using a rich (non-linear) function approximation in the critic, e.g., neural network, may also have a small function approximation error in the critic. However, as shown in the literature, e.g., (Cai et.al.,2023), TD with non-linear function approximation may require a strong condition to guarantee convergence. In contrast, using compatible function approximation in the critic has a guaranteed convergence. Moreover, as discussed in eq. (8), there is no need to estimate the inverse Fisher information matrix if we use compatible function approximation in NAC. This could significantly reduce the complexity in extensions to e.g., the multi-agent and distributed setting, where the estimate of the Fisher information matrix may be challenging.

Our theoretical analysis can also be generalized to understand the convergence and sample complexity of various extensions of AC and NAC type algorithms e.g., in the multi-task, multi-agent, distributed and game settings. Our approach of 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 can be used to obtain a tight bound of those generalizations of AC and NAC algorithms.

Cai, Q., Yang, Z., Lee, J. D., Wang, Z. (2023). Neural Temporal Difference and Q Learning Provably Converge to Global Optima. Mathematics of Operations Research.

Q4: Details of this paper's novelty. 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.

Proof Sketch: For simplicity of presentation, we set $\alpha_t=\alpha,\beta_t=\beta,\gamma_t=\gamma$, $\hat t=\lceil \frac{3\log T}{\bar \lambda_{\min}\alpha}\rceil$ and $\widetilde T=\hat t\lceil \frac{T}{\hat t \log T} \rceil$. We denote by $\pi^*$ the global optimal policy and $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:

$

\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 }+ \mathcal{O}\left(\sqrt{\frac{1}{\widetilde T}\sum_{j=t}^{t+\widetilde T-1} M_j}\right)+\mathcal{O}(C_\infty \sqrt{\varepsilon_{\text{actor}}}+ \beta+m\rho^k).

$

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:

$

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

$

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:

$||\theta_{t+1}-\theta_{t+1}^*||^2_2 \leq || \theta_t-\theta_{t}^* ||^2_2+ \alpha^2 ||\delta_t z_t||^2_2+|| \theta_{t}^*-\theta_{t+1}^*||_2^2$

$+ 2 \alpha\langle\theta_t-\theta_{t}^*, \delta_t z_t \rangle + 2\alpha \langle \delta_t z_t, \theta_{t}^* - \theta_{t+1}^* \rangle+ 2 \langle\theta_t-\theta_{t}^*, \theta_{t}^*-\theta_{t+1}^* \rangle.$

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\overset{\pi_t\times P}{\to}...\overset{\pi_t\times P}{\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\overset{\pi_t\times P}{\to}...\overset{\pi_t\times P}{\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)$.

Q1: Clarification on eq. (5) and the statement of no critic function approximation error.

Thanks for the suggestion. We have added the proof of eq. (5) in the revision. For convenience, we also include the proposition and the proof here.

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

\mathbb E_{D_{\pi_\omega}}[(Q^{\pi_\omega}(s,a)-\phi^\top_\omega(s,a)\bar \theta_\omega^*)\phi_\omega(s,a) ]=0.

Now we consider the policy gradient $\nabla J(\pi_\omega)$, and it can be shown that

Furthermore, for the natural policy gradient, we have that $$\widetilde{\nabla} J(\pi_\omega)= F_{\omega}^{-1} \mathbb E_{D_{\pi_\omega}}[\phi_\omega(s,a)\phi_\omega(s,a)^\top{\bar\theta}^\omega]=F\omega^{-1} \mathbb E_{D_{\pi_\omega}}[\phi_\omega(s,a)\phi_\omega(s,a)^\top ]\bar \theta^\omega=\bar \theta^*\omega.