On the Global Convergence of Natural Actor-Critic with Neural Network Parametrization

Weaknesses

• With regards to the paper Cayci et.al (2022), thank you for pointing it out. Since the paper is on archive, it did not come across in our literature review. However, having gone through it, we can see that in this paper, the actor and critic are both restricted to a two layer neural network, this is in contrast to our work which allows for a multi layer actor and critic. Additionally, note that this work achieves a sample complexity of $\epsilon^{-6}$ which is worse than our result or $\epsilon^{-4}$ even in this restricted setting. We will add this paper in our related works.

• Secondly with respect to the the non-i.i.d analysis in Xu et al.(2020), the ergodicity assumption is used to bound the difference between the estimate of the advantage function obtained form the Markovian data and that which would have been obtained from i.i.d data. This can be seen in Page 23 equation 25. For our case we account for the Markovian dependence in the critic samples by splitting the critic optimization as given in Equation (25), here the corresponding term is $\epsilon^{3}_{k,j}$. This term is bounded using the theory in Bertail and Porter (2019). Additionally, since we calculate the natural gradient update through the optimization given in equation (29), we account for the Markovian dependence of its samples through the result of Doan (2022). Note that by using this optimization we avoid having to invert our estimate of the fisher information matrix as is the case for Xu et al.(2020).

Questions

• With regards to the architecture of the network, the results we have used from Zhu (2019), were proven for a fully connected feed-forward neural network with ReLU activation layers. This result also holds for a smooth activation function (the author states that the results can be made sharper for a smooth activation function), this result would also apply for a conventional neural network as well as a residual neural network. For our case we can assume the case of a fully connected neural network with $L$ layers, at least $m$ neurons per layer and with an ReLU activation function for each layer.

• With regards to Equation (110), the set $\Theta$ here does not represent the class of all possible neural networks but only the two neural networks corresponding to the parameters $\theta_{k,j}^2$ and $\theta_{k,j}^3$, this is a typo on our part, we will rename it to $\Theta^{'}$ and state that it is the set of only two parameters $\theta_{k,j}^2$ and $\theta_{k,j}^3$. This is because we only need this bound for the two mentioned parameters as shown in Equation (112) and (113). We will make that change in the final version. With regards to the property of the function class, Bertail and Porter mentions that the function class has to be uniformly bounded. This condition is satisfies for the set $\Theta^{'}$ as it has only two elements and the state action pairs are defined on a bounded space.

• Thank you for pointing out this result, this was an over-site on our part. The term that you mentioned $\left(1-\frac{1}{n^{2}}\right)^{n}$ does indeed converge to $1$ and hence the term on the right you have pointed out will be non-decaying. However, we can resolve this by a minor modification. In lines $7-11$ of Algorithm 1 we perform stochastic gradient descent with data sample of size $n$ and also putting the number of iterations equal to $n$. We did not consider the edge case which you have mentioned where the error term becomes non-decaying. However this can be remedied with a minor modification. Instead of lines $7-11$ of Algorithm 1 we will have the following.

  • Sample and store $n$ state action pairs and the resulting rewards using policy $\pi^{\lambda_{k}}$
  • Then randomly sample the tuple $(s_{i},a_{i},r(s_{i},a_{i}),s_{i+1})$ from the stored data, calculate $y_{i}$ and preform the gradient descent step as in line 9 and 10 of Algorithm 1 respectively. This random sampling and update will be performed for $T_{k,j}$ iterations.

This will result in the superscript in the term to be $T_{k,j}$ instead of $n$. This can be seen from Equation 13.2 on page 34 of Zhu (2019) (please note that for some reason, the supplementary part of this paper is not available on the PMLR website, but is available on the archive version). Now using the result of Theorem 2 of Zhu (2019), for $T_{k,j} = \Theta\left(poly(n,L)\cdot{\log\frac{1}{\epsilon}}\right)$ the term inside the summation will be upper bounded by epsilon.

• The term $\mu_{k}$ represents the strong convexity parameter in Equation (9), since the function in Equation (9) is the expectation of a square loss function, we have to consider its strong convexity parameter.

Minor Questions

• When we are implementing the natural actor critic, if the critic parameterization is non-convex (as is the case for a neural network parametrization) the estimation of the critic at an iteration of the natural actor critic algorithm becomes a non-convex problem. This is the reason why prior works such as (Xu et al. 2020) used a linear parameterization of the critic. Natural Policy Gradient algorithms do not have this issue as they take a sample based estimate of the critic at each iteration. The reason that they avoid this problem is because they do not account for the error incurred due to sample estimate of the critic.
• Thank you for pointing out these works. We will incorporate them in the related works, the reason we did not focus on the case of Linear Quadratic regulators is because we were focusing on existing literature where linear critic is used. A linear quadratic regulator would be a further simplification and hence not our focus.
• They stationary distribution as you have pointed out does indeed not depend upon the starting distribution if the Markov chain is ergodic, we will make the required change. However, we do not know of any rigorous proof to show that the visitation distribution will not depend upon the initial distribution.
• Yes the dagger notation should not be present in Equation (7), thank you for pointing this out. We will add that the dagger notation represents the pseudo inverse.
• We will rename it to Deep Q Networks algorithm.
• This is a typo. The paper were referring to here was Liu et al. (2020). The assumption we referred to can be seen in Assumption 4.4 on page 7.
• Thank you pointing out these mistakes. We will correct them in the final version. We will also add discussions about the $|\log(\mathcal{A})|$ term that you mentioned.

Bibliograpahy

Munos, Rémi. "Error bounds for approximate policy iteration." ICML. Vol. 3. 2003.

Farahmand, Amir-massoud, Csaba Szepesvári, and Rémi Munos. "Error propagation for approximate policy and value iteration." Advances in Neural Information Processing Systems 23 (2010)

Sutton, Richard S., et al. "Policy gradient methods for reinforcement learning with function approximation." Advances in neural information processing systems 12 (1999).

Diddigi, Raghuram Bharadwaj, Prateek Jain, and Shalabh Bhatnagar. "Neural network compatible off-policy natural actor-critic algorithm." 2022 International Joint Conference on Neural Networks (IJCNN). IEEE, 2022.

Allen-Zhu, Zeyuan, Yuanzhi Li, and Zhao Song. "A convergence theory for deep learning via over-parameterization." International conference on machine learning. PMLR, 2019

Agarwal, Alekh, et al. "On the theory of policy gradient methods: Optimality, approximation, and distribution shift." The Journal of Machine Learning Research 22.1 (2021)

Xu, Tengyu, Zhe Wang, and Yingbin Liang. "Improving sample complexity bounds for (natural) actor-critic algorithms." Advances in Neural Information Processing Systems 33 (2020).

Liu, Yanli, et al. "An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods." Advances in Neural Information Processing Systems 33 (2020).

Major Questions

• We apologise for the error in the definition of $T^{\pi}Q(s,a)$. It should have been defined as $T^{\pi}Q^{\pi}(s,a) = \mathbb{E}(r(s,a)) + {\gamma}{\int}Q(s^{'},\pi(s^{'}))P(ds^{'}|s,a)$, where $\mathbb{E}(r(s,a))$ is the expected reward given the state action pair $(s,a)$. This would make $T^{\pi}Q(s,a)$ a fixed value and not a random variable. With regards to our comment about about the result in Munos (2003), we referenced that result as a result similar to that was used in Faharmand (2010), which we used for our analysis. As for the result we used (in Equations 74-77), it depends upon the property $T^{\pi}Q^{\pi}(s,a)=Q^{\pi}(s,a)$. This property will hold even for a random reward function. This is shown as follows.

  \begin{eqnarray} Q^{\pi}(s,a) &=& \mathbb{E}\left[ \sum_{t=0}^{\infty}{\gamma}^{t}r(s_{t},a_{t})|s_{0}=s,a_{0}=a\right] \\ &=& \mathbb{E}(r(s,a)) + \gamma \mathbb{E} \left[\sum_{t=1}^{\infty} {\gamma}^{t-1}r(s_{1},a_{1})|s_{0}=s,a_{0}=a \right] \\ &=& \mathbb{E}(r(s,a)) + {\gamma}{\int}Q(s^{'},\pi(s^{'}))P(ds^{'}|s,a) \\ &=& T^{\pi}Q^{\pi} \end{eqnarray}

  We will define $r^{'}(s,a)$ as the realisation of the random reward at the state action pair. We will also replace $r^{'}(s,a)$ in Equation (27) and replace $r(s,a)$ with $r^{'}(s,a)$ in Equation (28). Additionally, in Algorithm 1, $r(s,a)$ will be replaced by $r^{'}(s,a)$.

• With regards to the reference of Sutton (1999), we would like to point out that before it states that a linear parameterization of the critic is required, in the line just above this statement (at the bottom of page 3), the author assumes that the policy is being parameterised using a linear function. It is for this reason that a linear parametrization of the critic is required. In our case where we assume that the policy parametrization is smooth and not necessarily linear, restricting the critic to be a linear function would also require us to restrict the policy class to be linear. This is not something that is done typically in practice. As for the piratical feasibility of using a neural network for the critic, it is shown in Bharadwaj (2022), natural actor critic with a neural parameterization does converge.

• Thank you for pointing this out. We agree that we should have added an additional assumption in order to ensure the constant appearing on the loss function is independent ok $K$. Thus the additional assumption will be as follows.

  • There exists a constant $\\mu$ such that for any policy $\pi_{\lambda}, \lambda \in \Lambda$ we have

    \begin{eqnarray} \mathbb{E}_{s,a \sim \zeta^{\lambda}} \left(\nabla{\log}(\pi(a|s))\nabla{\log}(\pi(a|s))^{T}\right) \succeq
    \mu{\cdot}I_d \end{eqnarray}

    Where $\zeta^{\lambda}$ is the stationary state distribution corresponding to the policy $\pi_{\lambda}$, $I_d$ is the identity matrix of dimension $d$ which is the dimensionality of $\Lambda$.

• The randomness in Equation (50) is as you suggested because of the random initialization of the neural network parameters during the critic step. With regards to the architecture of the network, the results we have used from Zhu (2019), which were proven for a fully connected feed-forward neural network with ReLU activation layers. The results also holds for a smooth activation function (the author states that the results can be made sharper for a smooth activation function). The result would also apply for a conventional neural network as well as a residual neural network. For our case we can assume the case of a fully connected neural network with $L$ layers, at least $m$ neurons per layer and with an ReLU activation function for each layer.

• Thank you for pointing this out. We need to change the natural policy update is given by $\lambda_{k+1} = \lambda_{k} + {\eta}w_{k}$. This is in keeping with the analysis in Agarwal, (2020). We explain in Appendix $E$ how our analysis extends upon the work done for the natural policy gradient to that of a natural actor critic.

Weaknesses

• We remark that our current work is theoretical in nature where we establish the global optimality of already existing natural actor critic algorithm. A rigorous theoretical understand of global convergence was missing from the literature and our paper fills that gap. Regarding the empirical study, we believe that it would not add any additional value to our contributions because it has already been widely shown in the literature that the natural actor-critic algorithm with neural network parameterization works very well in practice as in Bharadwaj (2022) and has real world applications such as Wang (2021). The focus of our work is establishing that theoretically.

• With regard to the two papers mentioned, we respectfully disagree with the reviewer. Let us consider them individually.

  1. First, Wang (2019), establishes an upper bound only for the case where both the actor and critic are restricted to a two-layer network with ReLU activation. Furthermore, if we look at the convergence result for the neural policy gradient in Theorem A.4. We see that while the iteration complexity of the result is $\mathcal{O}(T^{-\frac{1}{2}})$ the sample complexity required for the to achieve an $\epsilon$ error bound is $\epsilon^{-8}$. Additionally, we see that the extra error due to neural network architecture, note the $\mathcal{O}(m^{-\frac{1}{8}})$ term in Theorem A.4, which means that the minimum width in the neural network required is of the order $\mathcal{O}(\epsilon^{-\frac{1}{8}})$. For our result, we achieve a sample complexity of $\mathcal{O}(\epsilon^{-\frac{1}{4}})$ and the minimum width in the neural network required is of the order $\mathcal{O}(\epsilon^{-\frac{1}{2}})$.
  2. Secondly, in Fu et al. (2020), while the requirement for a two layer actor and critic is extended to a multi layer actor and critic, the sample complexity even in the asymptotic limit is $\mathcal{O}(\epsilon^{-\frac{1}{6}})$, this can be seen in the discussion below theorem C.5. Also, the minimum width in the neural network required is of the order $\mathcal{O}(T^{-\frac{1}{6}})$, where $T$ is the number of iterations of the algorithm. Since the iteration complexity is given by $\mathcal{O}(\epsilon^{-\frac{1}{2}})$, the minimum width in the neural network required is of the order $\mathcal{O}(\epsilon^{-\frac{1}{12}})$. Thus both in terms of sample complexity as well as the minimum width of the neural network, our result improves upon the results mentioned.

Other novelties in our work We would also like to point out that both these works assume that sample can independently sampled from the stationary state distribution of a given policy, something which is not possible in practice. Our work does not have this restriction. Also, both prior works require the use of energy based policies, our analysis is more general, which includes energy based policies but is not restricted to them. Finally, we would like to point out that these results also do not have any empirical studies.

Questions

• Thank you for pointing this out, we will correct this typo.

• With regards to the architecture of the network, the results we have used from Zhu (2019), which were proven for a fully connected feed-forward neural network with ReLU activation layers. The results also holds for a smooth activation function (the author states that the results can be made sharper for a smooth activation function). The results in Zhu (2019) would also apply for a conventional neural network as well as a residual neural network. For our case we can assume the case of a fully connected neural network with $L$ layers, at least $m$ neurons per layer and with an ReLU activation function for each layer.

• It seems we have cited the version of this paper published in COLT and not the one in JMLR. We will cite the JMLR version in the final version of our paper.

• We will add the stated reference in the related works section of our final paper.

Bibliography

Diddigi, Raghuram Bharadwaj, Prateek Jain, and Shalabh Bhatnagar. "Neural network compatible off-policy natural actor-critic algorithm." 2022 International Joint Conference on Neural Networks (IJCNN). IEEE, 2022.

R. Wang, J. Li, K. Wang, X. Liu and X. Lit, "Service Function Chaining in NFV-Enabled Edge Networks with Natural Actor-Critic Deep Reinforcement Learning," 2021 IEEE/CIC International Conference on Communications in China (ICCC), Xiamen, China, 2021

Wang, Lingxiao, et al. "Neural policy gradient methods: Global optimality and rates of convergence." In International Conference on Learning Representations, 2019.

Fu, Zuyue, Zhuoran Yang, and Zhaoran Wang. "Single-timescale actor-critic provably finds globally optimal policy." In International Conference on Learning Representations, 2020.

Allen-Zhu, Zeyuan, Yuanzhi Li, and Zhao Song. "A convergence theory for deep learning via over-parameterization." International conference on machine learning. PMLR, 2019.

Weaknesses

• With regards to your comment about combining NTK analysis with for the work of Xu et al. (2020a), we would like to point out a key deficiency in that approach. In Xu et al. (2020a), while the policy class is non linear, the critic class has been restricted to a linear function. Now note that in Sutton(1999) on page 5, it is stated that a critic is restricted to be linear only when the policy class is also parameterized by a linear function for the compatible function approximation to hold. Thus in order for the compatible function approximation to hold, in the limit of the of the infinite width, both the actor and critic should converge to a linear kernel. If such a result is achieved, we will not recover the result of Xu et al. (2020), where the policy is still non-linear and the critic is linear. As Xu et al. (2020a) itself notes, the term $\zeta^{actor}_{approx}$ (which is the term Sutton (1999) references) can be said to be small for an overparameterized neural policy according to Wang (2019). This is mentioned in page 8 just before Theorem 3. However, Wang (2019) states that both actor and critic are represented by a neural network for this error to be small, something that is not possible in Xu et al. (2020a) as the critic has to be linear.

  However, results achieving convergence for the natural actor critic in the infinite width limit have been proven and our result improves upon them.

  Indeed, Wang (2019), mentioned in Xu et al. (2020a) is such a work. It establishes an upper bound only for the case where both the actor and critic are restricted to a two layer network with ReLU activation. If you look at the convergence result in Theorem A.4. We see that while the iteration complexity of the result is $\mathcal{O}(T^{-\frac{1}{2}})$ the sample complexity required for the to achieve an $\epsilon$ error bound is $\epsilon^{-8}$. additionally, we see that the extra error due to neural network architecture, note the $\mathcal{O}(m^{-\frac{1}{8}})$ term in Theorem A.4, means that the minimum width in the neural network required is of the order $\mathcal{O}(\epsilon^{-\frac{1}{8}})$. For our result, we achieve a sample complexity of $\mathcal{O}(\epsilon^{-\frac{1}{4}})$ and the minimum width in the neural network required is of the order $\mathcal{O}(\epsilon^{-\frac{1}{2}})$.

  Similarly for the result in Fu et al. (2020), while the requirement for a two layer actor and critic is extended to a multi layer actor and critic, the sample complexity even in the asymptotic limit is $\mathcal{O}(\epsilon^{-\frac{1}{6}})$ as can be seen in Theorem C.5. Additionally the minimum width in the neural network required is of the order $\mathcal{O}(T^{-\frac{1}{6}})$, where $T$ is the number of iterations of the algorithm. Since the iteration complexity is given by $\mathcal{O}(\epsilon^{-\frac{1}{2}})$, the minimum width in the neural network required is of the order $\mathcal{O}(\epsilon^{-\frac{1}{12}})$. Thus both in terms of sample complexity as well as the minimum width of the neural network, our result improves upon it.

  We would also like to point out that both these works assume that sample can independently sampled from the stationary state distribution of a given policy, something which is not possible in practice. Our work does not have this restriction. Additionally, both prior works require the use of energy based policies, our analysis is more general, which includes energy based policies but is not restricted to them. Finally, we would like to point out that these results also do not have any empirical studies.

• As per the reviewers suggestion, we will add more references related to NTK theory.

Bibliography

Xu, Tengyu, Zhe Wang, and Yingbin Liang. "Improving sample complexity bounds for (natural) actor-critic algorithms." Advances in Neural Information Processing Systems 33 (2020).

Sutton, Richard S., et al. "Policy gradient methods for reinforcement learning with function approximation." Advances in neural information processing systems 12 (1999).

Wang, Lingxiao, et al. "Neural policy gradient methods: Global optimality and rates of convergence." In International Conference on Learning Representations, 2019.

Fu, Zuyue, Zhuoran Yang, and Zhaoran Wang. "Single-timescale actor-critic provably finds globally optimal policy." In International Conference on Learning Representations, 2020.

Allen-Zhu, Zeyuan, Yuanzhi Li, and Zhao Song. "A convergence theory for deep learning via over-parameterization." International conference on machine learning. PMLR, 2019.

Thank you for bringing this work to our notice. As you said, this work deals with an actor critic algorithm which is slightly different from our natural actor setup. We would also like to point out that the results here have been proven for a finite state space, an assumption that can be violated even for a simple problem such as the cartpole in OpenAI Gym. Nonetheless, we will add a discussion of this in our final version as a concurrent work.