Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithm
Authors: Semih Cayci
Niao He
R. Srikant
Venue: Accepted by TMLR ()

Abstract: Natural actor-critic (NAC) and its variants, equipped with the representation power of neural networks, have demonstrated impressive empirical success in solving Markov decision problems with large (potentially infinite) state spaces. In this paper, we present a finite-time analysis of NAC with neural network approximation, and identify the roles of neural networks, regularization and optimization techniques (e.g., gradient clipping and weight decay) to achieve provably good performance in terms of sample complexity, iteration complexity and overparametrization bounds for the actor and the critic. In particular, we prove that (i) entropy regularization and weight decay ensure stability by providing sufficient exploration to avoid near-deterministic and strictly suboptimal policies and (ii) regularization leads to sharp sample complexity and network width bounds in the regularized MDPs, yielding a favorable bias-variance tradeoff in policy optimization. In the process, we identify the importance of uniform approximation power of the actor neural network to achieve global optimality in policy optimization due to distributional shift.

Published in Transactions on Machine Learning Research (04/2024)
Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithm
Semih Cayci
cayctemathee.rubb-cchhn.
Deportment of Mathematics RWTH Aochen University
Niao He
niao.heWinff.e efw.e.fff...hc.......
Department of Computer Science
ETH Zurich
R. Srikant
rerikant@iliioois edu
ECE and CSL
University of Ilimois Trrana-Champpine
Reviewed on OpenReview: https: openreview. net/ mett forum? id- BkEqk7pp1I
Abstract
Natural actor-critic (NAC) and its variants, equipped with the representation power of neu- ral networks, have demonstrated impressive empirical success in solving Markov decision problems with large (potentially infinite) state spaces. In this paper, we present a finite- time analysis NAC with noural network approximation, and identify the rolcs of noural nelworks, regularization and optimization lechniques (e.g., gradient clipping and weight decay) to achieve provably good performance in terms of sample complexity, iteration com- plexity and overparametrization bounds for the actor and the critic. In particular, we prove that (i) entropy regularization and weight decay ensure stability by providing sufficient ex- ploration to avoid near-determiniticc and strictly suboptimal policies and (ii) regularization leads to sharp sample complexity and network width bounds in the regularized MDPs, yield- ing favorable bias-variance tradcoff in policy optimization. In the process, we identify the importance of uniform approximation power of the actor neural network to achieve global optimality in policy optimization due distributional shift.
1 Introduction
In reinforccment learning (RL), agent aims find optimal policy that maximizes the expected total reward in Markov decision process (MDP) by interacting with unknown and dynamical environment (Sutton & Barto, 2018; Szepesvári, 2010; Bertsekas & Tsitsiklis, 1996). Policy gradient methods, which em- ploy first-order optimization methods to find the best policy within a parametric policy class, have demon- strated impressive success in numerous complicated RL problems (Williams, 1992; Sutton et al., 1999; Konda & Tsitsiklis, 2000). The success largely benefits from the versatility of policy gradient methods accommo- dating a rich class of function approximation schemes as demonstrated by Mnih al. (2016); Silver et al. (2016); Nachum al. (2017); Duan al. (2016).
Natural policy gradient (NPG), natural actor-critic (NAC) and their variants, which use Fisher information matrix as pre-conditioner for the gradient updates (Amari, 1998; Kakade, 2001; Bhatnagar et al., 2007: Peters & Schaal, 2008), are particularly popular because of their emprriaa performance in practical applications. practice, NPG/NAC methods are further combined with (a) neural network approximation for high representation power of both the actor and the critic, and (b) entropy regularization for stability and sufficient exploration, leading remarkable performance in complicated control tasks that involve large state-action spaces (Haarnoja et al., 2018; Nachum et al., 2017; Ahmed et al., 2019).

---

Published in Transactions on Machine Learning Research (04/2024)
Despite the empirical successes, strong theoretical understanding of policy gradient methods, especially when boosted with function approximation and entropy regularization, appears to be in a nascent stage. Recently, there has been a plethora of theoretical attempts to understand the convergence properties of policy gradient methods and the rolc of entropy regularization; see; c.g., Agarwal et al. (2020); Bhandari & Russo (2019); Lan (2021); Cen et al. (2020); Mei al. (2020), just to name a few. These works predominantly si study the tabular setting, where a parallelism between the well-known policy iteration and policy gradient methods can be exploited to establish the convergence results. But for the more intriguing function approximation regime, especially with neural network approximation, little theory is known. Two of the main challenges come from the highly nonconvex nature of the problem when using neural network approximation for both the actor and the critic, and the complex exploration dynamics.
In this paper, we provide the first non-asymptotic analysis of an (NAC) method which we use two separate two-layer neural networks for the actor and critic, and employ a learning scheme based on approximate natural policy gradient updates to achieve optimality. We show that the expressive power of these neural networks provide the ability to achieve optimality within a broad class of policies.
natural actor-critic
1.1 Main Contributions
We elaborate some of our contributions below.
Sharp somple complezity, converyence rate and overporamicterization bounds: We prove sharp con- vergence guarantees in terms of sample complexity, iteration complexity and network width. Par- ticularly, we prove that the NAC method with an adaptive step-size achieves sharp Ó(1/e) iteration complexity and ((1/e²) sample complexity to achieve an c-gap with the optimal policy of the reg- ularized MDP under mildest distribution mismatch conditions to the best of our knowledge. The required network width for both the actor and critic are O(1/c²) and Ó(1/2), respectively. Under the standard distribution mismatch assumption as used by Wang et al. (2019), our sample complexity bound for the unregularized MDP is Ó(1/E"), which improves the existing bounds significantly.
Stable policy optimization in the overporameterized regime: Existing works on neural policy gradient methods with neural network approximation assume that the policies perform sufficient exploration to avoid instability, i.c., convergence to dear-determnnistic.. and strictly suboptimal stationary policies. In this paper, we prove that policy optimization is stabilized by incorporating (i) overparameteri- zation, (ii) entropy regularization, (iii) gradient clipping, and (iv) weight-decay. In particular, we show that the combination of these mothods Icads to "persistence of excitation" condition, which ensures sufficient exploration to avoid near-deterministic and strictly suboptimal stationary policies. Consequently, we prove convergence to the globally optimal policy under the mildest concentrability coefficient assumption for on-policy NAC to the best of our knowledge.
Understanding the dynamics of neural network approzimation in policy optimization: Our analysis reveals that the uniform approximation power of the actor network to approximate Q-functions throughout, policy optimization steps is crucial to ensure global (near-)optimnlltty which is a specific feature of reinforcement learning that induces distributional shift over time in contrast to static supervised learning problem. To that end, we establish high-probability bounds for a two-layer feedforward actor neural network to uniformly approximate Q-functions of the policy iterates during the training.
1.2 Related Work
Policy gradient and aclor-crilic: Policy gradient methods use a gradient-based scheme to find the optimal policy (Williams, 1992; Sutton et al., 1999). Kakade (2001) proposed the natural gradient method, which uses the Fisher information matrix as pre-conditioner to fit the problem geometry better. Actor-critic method, which learns approximations to both state-action value functions and policies for variance reduction, was introduced by Konda & Tsitsiklis (2000).
2

---

Published in Transactions on Machine Learning Research (04/2024)
Neural actor-critic methods: Recently, there has been a surge of interest in direct policy optimization methods for solving MDPs with large state spaces by exploiting the representation power of deep neural networks. Particularly, deterministic policy gradient (Silver et al., 2014), trust region policy optimization (TRPO) (Schulman et al., 2015), proximal policy optimization (PPO) (Schulman et al., 2017), soft actor-critic (SAC) (Haarnoja et al., 2018; Lee al., 2020) achieved impressive empirical success in solving complicated control tasks.
Role of regularization: Entropy regularization is an essential part of policy optimization algorithms (e.g.. TRPO, PPO and SAC) to encourage exploration and achieve fast and stable convergence. It has been numerically observed that entropy regularization leads to smoother optimization landscape, which leads to improved convergence properties in policy optimization (Ahmed et al., 2019). For tabular reinforcement learning, the impact of entropy regularization was studied by Agarwal et al. (2020); Cen et al. (2020); Mei et al. (2020). On the other hand, the function approximation regime leads to considerably different dynamics compared to the tabular sctting mainly because of the generalization over a large state space, complex exploration dynamics and rinatiiaannaal shift. As such, the role of regularization is very different in the function approximation regime, which study in this paper.
Theoretical analysis of policy optimization methods: Despite the vast literature on the practical performance of PG/AC/NAC type algorithuss, their theoretical understanding has remained elusive until recently. In the tabular setting, global convergence rates for PG methods were established by Agarwal et al. (2020); Bhandari & Russo (2019); Khodadadian et al. (2021b). By incorporating entropy regularization, was shown that the convergence rate can be improved significantly in the tabular setting (Shani et al., 2020; Lan, 2021; Cen et al., 2020; Zhan et al., 2021). Recently, finite-time performances of off-poliey actor-critic methods in the tabular and linear function approximation regimes were investigated; see e.g., the works by Khodadadian et al. (2021a); Chen et al. (2022). In our paper, we consider neural network approximation under entropy regularization with on-policy sampling.
On the other hand, when the controller employs a function approximator for the purpose of generalization to a large state-action space; the convergence properties of policy optimization methods radically change due to more complicated optimization landscape and distribution mismatch phenomenon in reinforcement learning (Agarwal et al., 2020). Under strong assumptions on the exploratory behavior of policies throughout lcarning iterations, global optimality of NPG with linear function approximation up to function approximation error was established by Agarwal et al. (2020). For actor-critic and natural actor-critic methods with linear function approximation, there are finite-time analyses by Chen et al. (2021); Xu et al. (2020); Zhang et al. (2021). For general actor schemes with linear critic, convergence to stationary points was investigated by Kumar et al. (2019); Wu et al. (2020); Qiu et al. (2021).
By incorporating entropy regularization, it was shown that improved convergence rates under much weaker conditions on the underlying controlled Markov chain can be established by Cayci et al. (2021) with lin- car function approximation. Our paper uses results from the drift analysis in that work, but addresses the significantly challenging complications due to using neural networks with ReLU activation functions in the overparameterized regime, and establishes global convergence to the optimal policies. The neural network approximation eliminates the function approximation error, which is a constant in linear function approximation, by employing a sufficiently wide actor neural network.
Newral network analysis: The empirical success of neural networks, which have more parameters than the data points, has been theoretically explained by Jacot et al. (2018); Du et al. (2018); Arora et al. (2019), where it was shown that overparameterized neural networks trained by using first-order optimization methods achieve good generalization properties. The need for massive overparameterization was addressed by Ji et al. (2019); Oymak& & Soltanolkotabi (2020), and it was shown that considerably smaller network widths can suffice to achieve good training and generalization results in structured supervised learning problems. Our analysis in this work is mainly inspired by the work of Ji et al. (2019). On the other hand, reinforcement learning problem has significantly different and more challenging dynamics than the supervised learning sctting as have a dynamic optimization problem in actor-critic, where distributional shift occurs as the policies are updated. As such, uniform approximation power of the actor network in approximating various functions through policy optimization steps becomes critical, different from the supervised learning setting
3

---

Published in Transactions on Machine Learning Research (04/2024)
(Ji & Telgarsky, 2019). Our analysis utilizes tools from the works Ji & Telgarsky (2019) and Ji et al. (2019): (i) we consider max-norm geometry to achieve mild overparameterriatioon (ii) we bound the distance bet ween the neural tangent kernel (NTK) function class and the class of functions realizable by a finite-width neural network by extending the RcLU analysis by Ji et al. (2019); Cayci et al. (2023). The distribution shift in the system due to the dynamical RL setting also yields a significant challenge compared to the previous works, which we address this paper.
The most relevant work in the literature is Wang et al. (2019), where the convergence of NAC with two-layer neural network was studied without entropy regularization. It was shown that, under strong assumptions on the exploratory behavior of policies throughout the trajectory, neural-NPG achieves c-optimality with O(1/e19) sample complexity and O(1/c1)) network width bounds. In this paper, we incorporate widely-used algorithmic techniques (entropy regularization, weight decay and gradient clipping) to NAC with neural net- work approximation, and prove significantly improved sample complexity and overparameteeriation bounds under weaker assumptions on the concentrability coefficients. Additionally, our analysis reveals that the uniform approximation power of the actor neural network is critically important establish global opti- mality, where distributional shift plays crucial role. In another relevant work, Fu et al. (2020) considers a single-timescale actor-critic with neural network approximation, but the function approximation error was not investigated due to the realizability assumption, which assumes that all policies throughout the policy optimization steps are realizable by the neural network. One of the main goals of our work is to study the benefits employing neural networks in policy optimization, and we explicitly characterize the function class and approximation error that stems from the use of finite-width neural networks.
1.3 Notation
For sequence of numbers {a+: i E T} where T is an index set, [ra]ier denotes the vector obtained by concatenation of r;, i E I. For a set A, |A] denotes its cardinality. For two distributions P. Q defined over the same probability space, Kullback-Leibler divergence is denoted as follows: (KI(PIIQ) = Es- log P(s)
Qia)
For a convex set C C Id and I E IRd, Po(x) denotes the projection of x onto C: Pe(x) = arg min 11æ2
For n E Z+, [n] = {1, (1,2,....,1) nJ. For d, m E N,, R > 0 and E mxd we denote
Bdd (v) = {(u
E IR mxd_ sup
||e villa S
R vm! S
[m(m]
where denotes the 5th row of v. 1 denotes the indicator function for any event A.
2
Background and Problem Setting
In this section, we introduce basic backgrounds of the problem setting, the natural actor critic method, as well as entropy regularization and neural network approximation that we consider.
2.1 Markov Decision Processes
We consider a discounted Markov decision process (S,,,P,,,y)) where S and A are the state and action spaces, P is a (unknown) transition kernel, r S x - [0, Tmarl: 0 < Tmaz < cc is the reward function, and E (0, 1) is the discount. factor. Tn this work, we consider a state space S and a finite action space A such that S x A C Idd Also, we assume that, by appropriate representation of the state and action variables, the following bound holds: [[(,, a)lla < 1, throughout the paper.
Value function:
Under a randomized policy S - A, an action A is taken at given state E S with probability <[]ss) A policy introduces trajectory by specifying a ~ (-1(s) and 8411 P(.ss,,a)) For any 80 E S, the corresponding value function of policy is as follows:
(TT(s) = E
Σ
> rr( az)
(1)
t=
4

---

Published in Transactions on Machine Learning Research (04/2024)
where or ~ x(-(st) and 81+1 P(-)st,a))
Entropy regularization: In order to avoid hear-deterministic suboptimal policies in policy optimization by encouraging exploration, entropy regularization is commonly used in practice (Silver et al., 2016; Haarnoja et al., 2018; Nachum et al., 2017; Ahmed et al., 2019). For a policy म, let
(s0) =
Σ (=(()())))) t=
(2)
where [((x(-1s) = -aed ((as) log (T((as)) is the entropy functional. Then, for the regularization param- eter A3 > 0, the reguaae-regullarieed value function is defined as follows:
(s)) = V* + AH (so).
(3)
The max-entropy policy, which assigns probability 1/|A| to each action in each state, maximizes the reg- ularizer H" (so) for any 80 E Thus, the regularizer H (8o) term in equation encourages exploration, controlled by À >>0.
Entropy-rregularized objective: For given initial state distribution j and for a given regularization parameter À > 0, the objective in this paper is to maximize the entropy-regularized value function
max VX (u),
(4)
where VT()) = Beown (so). We denote the optimal policy for the regularized MDP as n' throughout the paper.
Q-function and advantage function:
The (entropy-regulariiee) Q-function (8, a) defined as:
> (r(sk, as) A logs(aa(sk)) 80 00,=8,00 8,00 =a].
(8, a) E
(5)
k=0
Note that xx is the fixed point of the Bellman equation q(s. = (( a) where the Bellman operator T is defined as:
(s, a) = r(s, a) -alei-lloogann Allg + (1 a')].
(6)
As will see, for NAC algorithms, the following function, called the soft Q-function under a policy n, turns out to be useful quantity (Cen et al,, 2020):
(*),,a) = r(s,a) a) P(Pe)) (V))
(7)
Note that the two Q-functions are related as follows:
(s, a) = (x a) - Alog (als).
The advantage function under a policy defined as follows:
A7 a) (s, (s).
(8)
Similarly, the soft advantage function is defined follows:
(s, a) (s, Σ
a(a'ls) ((ssss)Q
(9)
a'EA
Lastly, we bound the entropy-regularized value function as follows:
Tmaz + A Aoog [A]
0 < (T( <
(10)
1-7
for any À >> 0, n since [0, Tmaz] and H(pp log |A] for any distribution p over A (Cen al., 2020).
5

---

Published in Transactions on Machine Learning Research (04/2024)
2.2 Natural Policy Gradient under Entropy Regularization
For given randomized policy ze parameterized by @ where θ is given parameter space, policy gradient methods maximize (**()) by using the policy gradient VoVTT (w). Natural policy gradient, quasi-Newton method, adjusts the gradient update to fit problem geometry by using the Fisher information matrix as a pre-conditioner (Kakade, 2001; Cen et al., 2020).
Let
G (1) = Bendff (-1))
Ve log (a(a)) log no(ass)]
be the Fisher information matrix under policy where (-) = (1 Ex=o P'((s E -1su ~ n)) is the discounted state visitation distribution under a policy æ. Then, the update rule under NPG can be expressed as
0 n 17- [ (1)) (v)
(11)
where 17 > 0 is the step-size. Equivalently, the NPG update can be written as follows:
0+ E arg max BER
V VA(TO-) 0-) _ 0 27)
- (w)(0 (000))0--(00000)
(12)
The above update schome is closcly related to gradient ascent and policy mirror ascent. Note that the gradient ascent. for policy optimization performs the following update:
0+ E arg max GER
V (2 0 21
12
(13)
The update in equation 13 leads to the policy gradient algorithm (Willians, 1992). Compared to equa- tion 13, the natural policy gradient uses a generalized Mahalanobis distance (i.e., weighted-fz distance) as the Bregman divergence instead of l distance (Cen et al., 2020; Lan, 2021; Agarwal et al., 2020).
In the following, we provide necessary tools to compute the policy gradient and the update rule in equation 11 based on Cayci et al. (2021).
Proposition (Policy gradient). For any 0 and O, we have:
VOVT
1- E Eand amxo(11)) V Volo (s.
(14)
Based on Proposition 1, the gradient update of natural policy gradient can be computed by the following lemma, which is extension of the works by Kakade (2001); Agarwal et al. (2020); Cayci et al. (2021).
Lemma Let
(vo log (ogs)() 05 (s,)))) {
O) = Eanay (m)
(15)
be the error for given policy parameter 0. Define
" E aargnn min L(w, 0).
(16)
Then, we have:
(") = (1-7) (N),
(17)
where T is the Fisher information matria.
The above results for general policy parameterization will provide basis for the entroy-rrgularized natural actor-critic (NAC) with neural network approximation that we will introduce the following section, with certain modifications for variance reduction and stability that we will describe; see Remark 2 later.

---

Published in Transactions on Machine Learning Research (04/2024)
3 Natural Actor-Critic with Neural Network Approximation
In this section, we introduce the retropy-regullrizee natural actor critic algorithm formally, where both the actor and critic are represented by single-hidden-layer neural networks.
Throughout this paper; we make the following assumption on the sampling process, which standard policy optimization (Agarwal al., 2020).
Assumption 1 (Sampling oracle). For given initial state distribution Pt and policy x, we assume that the controller is able to obtain an independent sample from d7, at any time.
The sampling process involves a resctting mechanism and a simulator, which are available in many important application scenarios, and sampling from state visitation distribution di can be performed by using the sampler in Algorithm 4 without the knowledge of dz (Agarwal et al., 2020; Konda & Tsitsikkis, 2003). For further discussion the sampling and its impacts on the analysis, please see Section B.
3.1 Actor Network and Natural Policy Gradient
For network width m E E+ and E R, 0; E IRd for i E [m]] the actor network is given by the single- hidden-layer neural network:
f(s, (c, vm
Go (10,, (s,a))),
(18)
where e [c))k [0],)(m)) a(x) m0) is the ReLU activation function. As common practice (Ji et al., 2019; Oymak & Soltanolkotabi, 2020; Arora et al., 2019), we fix the output layer after random initialization, and only train the weights of hidden layer, namely, 0 E θ C Rmxxd We note that training the output layer с would lead to an additional additive kernel term in the neural tangent kernel, resulting in a function class that is at least as rich as the original one (Cucker & Zhou, 2007). We consider a fixed output layer in this work for the sake of simplicily.
Given (possibly random) parameter 0 E R a design parameter R > 0, regularization parameter À and network width m Z+, the parameter space that consider is as follows:
θ = {o E pmxdd x max 100 - 0.112 S A/m
(19)
(E[m)
For this parameter space O the policy class that we consider is {To : E θ), where the policy that corresponds to 0 E ④ as follows:
(c. To(als) EveA (x)
(20)
We randomly initialize the actor neural network by using the symmetric initialization in Algorithm 1, (c. 6(0) ~ sym_iniii aom__nnt(mmmdd d) (Bai & Lee, 2019). Later, we will employ a similar symmetric initialization scheme for the critic neural network.
Algorithm 1: sym init(m,d) d) Symmetric Initialization inputs: m: network width, d: ambient dimension; for i 1.,..... mm/2 do
G C+m/2 Rodemacher;
0: 424m/2 ~ (O, Ta);
return network weights (c, 8)
We denote the policy at iteration 1 < T' as ग. = To()) and neural network output as fi a) a (()))))))) In the absence of the prior knowledge of = and di we construct a stochastic estimate of
(())).
u
min BE
E Exnay a [VV 1o o (als)u - E (s, (s,)))))
(21)
(0)

---

Published in Transactions on Machine Learning Research (04/2024)
by using samples from the system via the following actor-critic meta-algorithm:
Temporal difference learning algorithm (Algorithm 3 in Section 3.2), which employs a critic neural network, returns set of neural network weights that yield a sample-based estimate for the soft advantage function { (s (s,a) E 8 x A).
Critic:
Policy update: Given this, we construct a stochastic estimate of un by using stochastic gradient descent (SGD) with N iterations and step-size aA > 0. To that end, starting with 20th) = 0, an iteration of SGD is as follows
142 = un - an Vg log Te (an/sn )u Ex an) Vo log Ne (a((l)8))
(0)
(22)
U n+1 = P PBd (U)
(2+112))
(t)
(23)
where Sn ~ di and on (e(()sp) for 0, .......N 1, 1, is the output of the critic. Then, the final estimate ut = En= un (t) By using ut, we perform the following update:
0(L 1) 0(1) + 7/ We,
where we ne- x((()) 0(0))
The natural actor-critic algorithm summarized as a mela-algorithm Algorithun Below, we summarize the modifications in the algorithm that we consider in this paper with respect to the NPG described in the previous section.
Remark 1 (Weight decay and projection). The update in each iteration of the NAC algorithm described in Algorithm 2 can be equivalently written follows:
O(t +t - 0(0) = (1 1--mmp mA) (0(t) - 0(0)) + (1 m7)ue
(24)
where is an approximate solution to the optimization problem (21). As we will see, the projection of u, onto Bd (0)) (which can be considered as gradient clipping since this operation clips the natural policy gradient update ue to ensure maxigism ||u,,||22 < R/)m), in conjunction with the weight decay in the policy update (24) enables us to control max,g[m) (t( - (:0)ll2 while taking (natural) gradient steps towards the optimal policy. Controlling maxse[m] [10,(t) (0)ll2 is critical for two reasons: (i) to ensure sufficient exploration to achieve global optimality (see Proposition 2), and (ii) to establish the so-called kernel regime, which holds near the random initialization (see Lemma 3 and Theorem 1).
Alternatively, one may be tempted to project O()) onto a ball around 0(0) in the lg-geometry control max; []0((() (0) However, as the algorithm follows the natural policy gradient, which uses different Bregman divergence than || l12, projection of ((t) with respect to the fz-norm may not result in mov- ing the policy in the direction of improvement. Similarly, since we paramcterize the policies by using a lower-dimensionall vector 0 E mmdd to avoid storing and computing S x Al-dimensional policies, Bregman projection in the probability simplex, which is commonly used in direct parameterization, is not a feasible option for policy optimization with function approximation. As such, simultaneous use of weight decay and projection of the update u, are critical to control the network weights and policy improvement.
Remark 2 (Baseline). Note that the update of in equation 21 uses the soft-advantage function EX rather than the state-action value function qx. The soft-advantage function uses Eo-T, ==(a (s, a) as baseline for variance reduction, which is common practice in policy gradient methods (Sutton & Barto, 2018).
In the following subsection, we describe the critic algorithm in detail.
3.2 Critic Network and Temporal Difference Learning
We estimate EX by using the neural TD learning algorithm with max-norm regularization (Cayci et al., 2023). Note that Ex can be directly obtained from xx via Q (s, a) xx (s,a) Allog no (a(s)) and equation 9.
8

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm 2: retropy-rreullriized Neural NAC
initialize (c, (()) ~ sym init(m,d))
for t= U......TT-.. do
Critic: Ex MN-NTD(T,, R. m', (T,,aa // See Alg. 3 for details; Initialize: u0" (t) 0;
NN for n = 0, 1, I....,N do
Sampling: 8n ~ dx an ~ (e(-(sn)
(t)
Vg log (anls)))) - - (sn an) Vo Volog ti (anls,)
1n+1/2 Un a^
nnt1
(t)
PBe (0)
11 (211/2):
Up = N Σn=
un
(t)
01 + 1) = 0(1) + Th
- nh (((() 0(0));
Since 9x is the fixed point of the Bellman equation (5), it can be approximated by using temporal difference (TD) learning algorithms.
For the critic, we use two-layer neural network of width m', which is defined as follows:
1
(ss a: (b, W))
b (s,a))
(25)
m
The critic network is initialized according to the symmetric initialization scheme in Algorithm 1. Let (b, (0) denote the initialization.
To estimate the value function, we aim to solve the following problem:
E Bandf aw)a((ls)) (1s, a; (b, ()) - (i J
W = arg min W
(26)
where T is the Bellman operator in equation 6. Particularly, we consider max-norm regularization in the updates of the critic, which was shown to effective in supervised learning and reinforcement learning (see
Goodfellow et al. (2016; 2013); Srivastava et al. (2014); Cayci al. (2023)). For a given wo E Rd and R 0,
let.
GR(wo)= {w Rd ||w wall2 S R/ R/VmL).
(27)
Under max-norm regularization, each hidden unit's weight vector is confined within the set GR(W.(0)) for a given projection radius R.
The critic update for a given policy ne, 0 E θ summarized in Algorithm 3, which we call MN-NTD. At each iteration of MN-NTD, we perform the update:
Wi(k: 1) (SR(W,(O) (W.(k) + ark + 7 (5k,, d()) (sk ax)) Ww, qr (Sk, ax)) Vi E [m'].
r(sk, - A log (ax (sx) and Pe is the projection operator onto set C C Rd. For = I,.,, 1, we assume that (sk, ax) is sampled from di', i.e. St d me(-)s)). Upon obtaining (Sk, 4x), the next state-action pair is obtained by following тh: S ~ P(-Isk, an), d ~ (+())) One can replace the i.id. sampling here with Markovian sampling at the cost a more complicated analysis as shown by Bhandari al. (2021). However, since experience replay is used practice the actual sampling procedure is neither purely Markovian or ii.d., and here for simplicity of the analysis, choose to model it as ii.d. sampling.
where The (8, a) = 7(8 (b, W (k))),
The output of the critic, which approximates oh is then obtained as:
1 1 (s) = q (s a; (b, T
Σ W()))). (8, ESA.
9

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm 3: MN-NTD Max-Norm Regularized Neural TD Learning
Inputs: Policy proj. radius R, network width m', sample size T", step-size ac; Initialization: (b, (()) = sym init(m', d); for T -1 do
Observe (8k, (1)) d o no( (x)), 5/ P(.lsk. ax) d/ ~ To(-166);
Observe reward: Th == r(8k 0x) - Alog To sx)
Compute semi-gradient: Ik (rk + 7 (5 d/)) - (Sk; (x)) a (Sk. A#);
Take a semi-gradient step: WKk + 1/2) = (kk) + acgii
acci:
Max-nons norm regularization: Wi(k + 1) = (()( ( + 1/2)) vi E [m']
return ( a) = q ((s, s, a; (b, + E ((K)) for all (s, E S A
where T' is the number of iterations of MN-NTD. We obtain an approximation of the soft Q-function as xx = (s. a) - A log (a)s))
The corresponding estimate for the soft ad advantage function is the following:
(s, (x,0s,)) - Σ
( (s,a')
(28)
d'EA
4
Sample Complexity and Overparameterization Bounds for Neural NAC
In this section, we analyze the convergence of the entropy-regularize neural NAC algorithm and provide sample complexity and overparameterization bounds for both the actor and the critic.
4.1
Regularization and Persistence of Excitation under Neural NAC
The persistence of excitation, which broadly refers to a strictly positive exploration probability of each action at each state, an important general condition to guarantee the convergence stochastic control problems (Kumar Varaiya, 2015). The following important proposition states that the persistence of excitation condition is satisfied by the entropy-regilarized Neural NAC, which implies sufficient exploration is achieved to ensure convergence to global optimality.
Proposition 2 (Persistence of excitation under overparameetrrization).. For any regularization parameter X >> 0, projection radius R, the entropy-regularrzedd NAC satisfies the following:
Rx X/m
max [|0,(t) - 0,(0)l12 - [m]
(29)
where
1,
24
X(+TJ E (0, })
(30)
1 1- (1-1-10 -1-mph nd)s
for all 122 00 0 almost surely. Consequently,
exp (-2R/A- - 2pa Rey
m, .m,))))))))))))))))) 8))
Tmin
T
inf <e(als) 2 (s.
[A]
>
(31)
for all 2 O with probability at least - 8 over the random imitialization of the actor network, where the function Pu is given by
16Rg m
Po(Ro.m, m,
Ro + / log 7 + / ldlog(m))
(32)
10

---

Published in Transactions on Machine Learning Research (04/2024)
Proposition 2 has two critical implications:
(i) Any action a E A is explored with strictly positive probability at any given state 8 E S, which implies that all policies throughout the policy optimization steps satisfy the "persistence of excitation' condition with high probability over the random initialization. As will see in the convergence analysis, this property implies sufficient exploration, which ensures that wear-determnnistic suboptimal policies are avoided. Sufficient exploration is achieved by the combination of (i) entropy regularization, (ii) weight decay, (iii) max-norm projection of 1h, and (iv) large network width m for the actor network.
(ii) We can control the deviation of the actor network weights by R, À and m. This property is key for the neural network analysis in the lazy-training regime.
4.2 Transportation Mappings and Function Classes
We first present a brief discussion on kernel approximations of neural networks, which will be useful to state our convergence results. Consider the following space of mappings:
Hs fo IR + Rdd sup [|o(w)ll2 S
(33)
wERd
and the function class:
F3 = ((() = E ((aaol) -) ((wo.)>>0))) v Ho).
(34)
Note that Fe is a provably rich subset of the reproducible kernel Hilbert space (RKHS) induced by the neural tangent kernel, which is dense the space of continuous functions on a compact set as shown by et al. (2019). For a given class of transportation maps V {iy Ho k [K]] for K 1, we also consider the following space of functions:
FKP,Y {0()) = -K Σ
< [(0)))) ||a]| s $1..
(35)
kE[K]
Note that the above set depends on the choice of {uk hu]]k][]] but these maps can be arbitrary. Any separable subspace of continuous functions f Rd + over a compact domain has a countable basis {yx : 0, L... (Kreyszig, 1991). There exist t E Hp such that gu(s, a) E[va(ws) (s, a) ((32)))))))))) approximates y well by the universal approximation results (Ji et al., 2019). As such, FK.,y is able to approximate any separable subspace of continuous functions over a compact space as K + oo for sufficiently large v and an appropriate V.
4.3 Convergence of the Critic
We make the following realizability assumption for the Q-function.
Assumption 2 (Realizability of the Q-function). For any 2 O, we assume that 9x E Fp for some 0.
Assumption 2 is condition on the class of realizable functions that can be approximated by the critic network, which is dense in the space of continuous functions over Zh (see Section 4.2). One can also replace the above condition by slightly stronger condition which states that dx E Fu, vO E O. Note that the class of functions F, is deterministic and its approximation properties are well-known (Ji et al., 2019). Wang et al. (2019) assumed that the state-action value functions lie in a random function class, which is obtained by shifting F, with a Gaussian process. By employing a symmetric initialization, we eliminate this Gaussian process noise, and therefore the realizable class of functions is deterministic and provably rich.
Lemma 2 (Convergence of the Critic, Theorem 2, Cayci et al. (2023)). Under Assumption 2, for any error probability 5 E (0, 10, let I(m', 5) 4 4 + Aogg(T/5))
11

---

Published in Transactions on Machine Learning Research (04/2024)
and R> V. Then, for any target error 0, number of iterations T N, network width
16(0 ū + (R + {(ml 63) ( + 11) R
m'
- ?
and step-size
c²(1 -
ac (1 + 2R)2
the crilic yields the following bound:
B Band amm (-1)))))) (g (8, xx (s,))))
2 (1+2R)²
E
aann
s(1 - >)=") + 3e,
where A2 holds with probability at least 1 8 over the random initializations of the critic network.
Note that in order to achieve a target error less than 0, network width of m' Ō E and iteration complexity T' = -0( (1++2)²)² suffice. The analysis of TD learning algorithm by Cayci et al. (2023) uses results from Ji & Telgarsky (2019), which was given for classification (supervised lcarning) problems with logistic loss. On the other hand, TD learning requires a significantly more challenging analysis because of bootstrapping in the updates (i.e., using stochastic semi-gradient instead of true gradient) and quadratic loss function. Furthermore, for improved sample complexity and overparameterization bounds, max-norm regularization is employed instead of early stopping (Cayci et al., 2023).
4.4 Global Optimality and Convergence of Neural NAC
In this section, we provide the main convergence result for the entropy-regularizes NAC with neural network approximation.
Assumption 3 (Realizability). For K 2 1, we assume that for all 0 E e,, Q E FR,,V where the function class FK defined in Section 4.2.
Note that FK approximates a rich class of functions over a compact space well for large K (soe Section 4.2). Also, Assumption implies that there is a structure among the soft Q-functions in the policy class O since each Q can be written linear combination of K functions that correspond to the transportation maps fg. Thus, by the discussion in Section 4.2, if Q% for the constrained parameter set 0 E B (#(O) lies in a separable subspace of continuous functions, then the assumption holds for sufficiently large K and D for some V.
Remark 3 (Realizability assumption for the actor). The main results in this work (t.e., Theorem 1) can be established without the renlizability assumptions in Assumptions 2-3, which would bring function approzima- tion errors ecritic and eactor in both the critic and the actor, respectively. For the convergence results without the realizabilily assumplions, see Corollary 2.
The approrimation error for the critic can be easily characterized by the infinite-width timit Fu, which was shown. to be universal approrimator (Ji et al., 2019). Unlike the critic network, which learns only one function al each ileration of policy oplimization, the actor network requires to approzimale Q for all = 0, 0.1...,,T T by a shared random initialization. This causes a significant challenge in characterizing the class of soft-Q functions that can be learned by using the actor network. To that end, the structure among Q is assumed in Assumption 3, which enables us to establish uniform approzimation error bounds to handle the dynamic structure of the policy optimization over time steps. For further discussion on these uniform approzimation results, see Section A.4 (particularly Remark 8).
4.4.1 Performance Bounds under Weak Distribution Mismatch Condition
First, we establish sample complexity and overparameterization bounds under weak distribution mismatch condition, which is provided below. This condition is significantly weaker compared to the existing literature
12

---

Published in Transactions on Machine Learning Research (04/2024)
(sce, c.g., Wang et al. (2019); Liu et al. (2019); Agarwal et al. (2020)) proved that the policies achieve sulficient exploration by Proposition 2 (see Remark 4 for details).
Assumption 4 (Weak distribution mismatch condition). There cxists constant Coo oo such that
E B ((
1
(8)
9
2
Co.
sup 120
Remark (Weak distribution mismatch condition). Note that sufficient condition for Assumption 4 an exploratory initial state distribution Ji, which covers the support of the state visitation distribution of dy
d (s)
sup dd ") (s))
00,
(36)
since V Bo
4r (8) dr (x)
Hence, if the initial distribution has sulficiently large support
set, then Assumption 4 is satisfied without any assumptions on (* : 2 0}- Together with Proposition 2, it ensures stability of the policy optimization with minimal assumptions on as Bhandari & Russo (2019) indicates that the condition ||d] /plloc < oo is indeed necessary for convergence.
The following theorem one of the main results in this paper, which establishes the convergence bounds of the NAC algorithm.
Theorem (Global Optimality and Convergence). Let m' = T' = specified in Lemma 2. Under Assumptions 1-4, Algorithm 2 with R > & and regularization coefficient X > 0 satisfies the following bounds:
(1) with step-size T1 x(F+IJ 12 0, we have
(1 71-7) min B[(VT' (p) - V (1)) LE|T)
2R + log T)
+ 2R 4po Moc (0r +
Rymax N1/4
XT
(2) with siep-size 71 E 1/A), we have
(1-?) min [E[T]
B((V (
-A log IAI
1-E- Po
(pL+s+
Rqmaz
+2
N1/4
for any 5 E (0, 1/3) where P(4) 2 1 35 over the random initialization of the actor and critic networks.
where MR. = Coc (1 π ) Po
162 /lg((10) +
(/l/))+/lloomm) /dlog(m)).
Vm (ddoog(m)) Vlog(K//g K/8))
168
X/m
and Imar = 4(2R - Alog T.
Below we characterize the sample complexity, iteration complexity and overparameterizztion bounds based on Thcorem 1.
Corollary (Sample Complexity and Overparameetrizzatoon Bounds). For any and 5 E (0, 1/3).
Algorithm 2 with R > D satisfies:
min
E[VV (n) (w)
EE(T]
where PP(4) 2 1 - 38 over the random initialization of the actor-critic networks for the following parameters:
iteration complerity: T = Ö
(1-7))))
n²
aclor network width: m = Ō
R log(1/))
M.. 52 log K/
X1-
<1(10) ")
13

---

Published in Transactions on Machine Learning Research (04/2024)
ar2 R² critic sample complexity: T = O
(1-T)Rct
critic network width: m' Ō M. 1t log(1/4)
(1-3)902
Mr nt actor sample complexity: N 0
c((--))*
Hence, the overall sample complexity of the Neural NAC algorithm is (()).
Remark 5 (Bias-variance tradeoff in policy optimization). By Proposition 2, the network parameters evolve such that
R
sup max |0,(0) (t)l A/m 120 mm(m]
Hence, the NAC always performs a policy search within the class of randomized policies, which leads to fast and stable convergence under minimal regularity conditions. In particular, Assumption 4 is the mildest distributional mismatch condition in on-policy NPG/NAC settings to the best of our knowledge, and it suffices to establish convergence results in Theorem 1. On the other hand, entropy regularization introduces a bias term controlled by X, hence the convergence in the regularized MDP. Another way to see this that deterministic policies, which require lim; [|0(t)]lz = oc, may not achieved for À 0 since (tt is always contained within a compact set. Letting À climinates the bias, but the same time reduces the convergence speed and may lead to instability due lack of exploration. Hence, there is bias-variance tradeoff in policy optimization, controlled by 0.
and suP120 su Te (als)
Remark 6 (Different network widths for actor and critic). Corollary indicates that the actor network requires ((1/e4) neurons while the critic network requires Ó(1/e²) although both approximate (soft) state- action value functions. This difference is because the actor network is required to uniformly approximate all state-action value functions over the trajectory, while the critic norw approximates (pointwise) a single state-action value function at each iteration.
Remark (Fast initial convergence rate under constant step-sizes). The second part of Theorem 1 indicates that the convergence rate e-9(T) under constant step-size n7 E (0, 1/A), while there an additional error term Rn This justifies the common practice of "halving the step-size" in optimization (see, e.g., Karimi et al. (2016)) for the specific case of natural actor-critic that investigate: one achieves fast convergence rate with a constant step-size until the optimization stalls, then the process is repeated after halving the step-size.
The convergence bounds in Theorem 1 avoid the approximation errors that stem from the use of neural networks in the actor and the critic by Assumptions 2-3. In the following, we characterize the impact of these approximation errors on the performance of the algorithm. To that end, let
critic
max IE min V (Bal((((s ox (s, a))]
(37)
Capp
ost<T JEJo
actor
max E min
V /eaa(VV a)u - (s)a))))
(38)
app
OSKT
wEB wEB (0)
be the approximation errors for the critic and the actor, respectively, where the outer expectation is over the parameter ((t) given the random initialization. Note that Vf((s, a)u is the linear approximation of f(s, a; (c, u + (())) around the initialization (see Prop. 3). We have the following result.
Corollary 2 (Global Optimality and Convergence). Let m' Ō (14 T o (1+20)²0*) Under Assump-
tions and 4, Algorithm with R > v, >> 0 and step T)c = x(++1 satisfies
7) min B[(VT' (n) (1) 2R + log T) + 22 4po
XI
Rgmax
+ 4M
(accoor
critic app
+ + NI/4
14

---

Published in Transactions on Machine Learning Research (04/2024)
where Mx C20 + k and Po =
16R R + Vlog(1/6) + + Vdlog(m)) for any E (0, where Aym
P(A) 2 36 over the random initialization of the actor and critic networks.
Corollary 2 explicitly shows the impact of the approximation errors for the actor and the critic.
4.4.2 Performance Bounds under Strong Distribution Mismatch Condition
In the following, we consider the standard distribution mismatch condition (e.g., Liu et al. (2019); Wang et al. (2019)) and establish sample complexity and overparameterization bounds based on Theorem 1, for the unregularized MDP.
Assumption 4' (Strong distribution mismatch condition). There erists a constant Coc < 00 such that
2 ) 9
sup 120
((.a))ad
d (5)
C2
(39)
Note that Assumption 4' implies Assumption 4, and a cousiderably stronger assumption that necessitates
our policies (Ne 0, o.,...., T - 1} being sufficiently exploratory throughout policy optimization.
Corollary 3. Under Assumptions 1-3 and 4, for any e > 0 and å E (0, Algorithm with R v and = 0(///)) satisfics:
min [Imxx V*(n) V (W))LA) S. EE(T]
where P(A) 2 1 1-38 38 over the random initialization of the actor-critic networks for the following parameters:
iteration complerity: T = 0
(1--)(²))
R²
actor network width: = Ö
R
R log(1/8)
Co 62 (K/8)
(1-7)423
11-7)420
+
c21 7)²
critic sample complerity: T = 0
Ar2 Rd
(1-7)-E+
critic network width: m' = 0 M3 R² (og(1/5)
(1-))222
actor sample complerity: N = 0
Mi 11' aunguu ((11-))
where Mcc 01 + π ).
Hence, the overall sample complexity of Neural NAC for finding an e-optimal policy of the unregularized MDP δ
4.5 Comparison With Prior Work
Among the existing work that theoretically investigate policy gradient methods, the most related one is Wang et al. (2019), which considers Neural PG/NPG methods equipped with two-layer neural network. We point key differences between our work and prior work:
Prior work do incorporate entropy regularization. As result, they need a stronger concentra- bility coefficient. assumption like Assumption 4' instead of the weaker Assumption under which we are able to prove main results.
In the proofs Appendix A, we will observe that one needs uniform function approximation bounds for the linearized actor network finite-width in approximating soft Q-functions throughout policy optimization steps. We show that the problem structure, which will impose shared features among
15

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm
Width of actor, critic
Sample comp.
Error
Condition Strong
Objective
Neural NPG (Wang et al., 2019)
0(1/4))
0(1/24)
6 +
Unregularized
Neural NAC (ours) Neural NAC (ours)
0(1/c), 0(1/2) (1/6))001//)
O(1/c)) Ó(1/69)
c
Weak
Regularized
6
Strong
Unregularized
The overparameterization and sample complexity bounds for variants of natural policy gradient with neural network approximation.
Table 1:
soft Q-functions throughout policy optimization steps, will be of critical importance to achieve good performance. To address this challenge, which was not addressod in the prior work, we devise new techniques.
While our algorithm similar in spirit to the algorithms analyzed in the prior works, we also incorpo- rate number of important algorithmic idcas that are used in practice (e.g., entropy regularization, weight decay, gradient clipping). As a result, we have to use different analysis techniques. As a consequence of these algorithmic and analytical techniques, we obtain considerably sharper sample complexity and overparameteriiaation bounds (see Table 1). Interestingly, all of these algorithmic improvements to the original NAC algorithms seem to be important to obtain the sharper bounds.
We employ a symmetric initialization scheme proposed by Bai Lee (2019) to ensure that fo(s, a) = for all 8, a despite the random initialization. As a consequence of symmetric initialization, we eliminate the impact of fo in the infinite width limit, which is effectively noise term eg in the performance bounds (Wang et al., 2019; Liu et al., 2019; Cai et al., 2019).
5 Conclusion
In this paper, we established global convergence of the two-timescale autropy-regularin NAC algorithm with neural network approximation. We observed that entropy regularization, combination with max-norm gradient clipping and weight-decay, led to significantly improved sample complexity and overparameteriza- tion bounds under weaker conditions since it (i) encourages exploration, (ii) controls the movement of the neural network parameters. We characterized the bias due to function approxination and sample-based estimation, and showed that overparameterization and increasing sample-size eliminates bias. Our analysis revealed the significant. difference between the actor and critic in terms of the approximation and statistical errors, as the actor network to approximate all soft-Q functions throughout the policy optimization steps, requiring larger sample complexity and representation power. To that end, the extension of our work with finer characterization of the uniform approximation error for the actor network, which would potentially lead to larger hypothesis class than FK, is interesting direction for neural policy optimization.
In practice, single-timescale natural policy gradient methods are predominantly used in conjunction with entropy regularization and off-policy sampling (Haarnoja et al., 2018). The analysis techniques that we develop in this paper can be used to analyze these algorithms.
In supervised learning, softmax parameterization predominantly used for multiclass classification problems, where natural gradient descent is employed for a better adjustment to the problem geometry (Goodfellow et al., 2016; Pascanu & Bengio, 2013; Zhang et al., 2019). The techniques that we developed in this paper can be useful in establishing convergence results and understanding the role of entropy regularization well.
Acknowledgments
Niao He acknowledges support from Swiss National Science Foundation (SNSF) Project Funding No. 200021- 207343 and SNSF Starting Grant. R. Srikant's research was supported in part by AFOSR Grant FA9550- 24-1-0002, ONR Grant 400014-1--1-2566 and NSF Grants CNS 23-12714, CNS 21-06801, CCF 19-34986,
Eo is error that stems from the infinite-width limit of the neural network random initialization, which non- vanishing with T.
16

---

Published in Transactions on Machine Learning Research (04/2024)
and CCF 22-07547. S. Cayci would like to thank Siddhartha Satpathi for discussions the proof of Lemma 7.
References
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods in markov decision processes. In Conference on Learning Theory, pp. 64-66. PMLR, 2020.
Zafarali Ahmed, Nicolas Le Roux, Mohammad Norouzi, and Dale Schuurmans. Understanding the impact of entropy policy optimization. In International Conference Machine Learning, pp. 151-160. PMLR, 2019.
Shun-Ichi Amari. Natural gradient works efficiently in learning. Nearal computation, 10(2):251-270) 1998.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang, Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332.222 PMLR, 2019.
Yu Bai and Jason D Lec. Beyond lincarization: On quadratic and higher-order approximation of wide neural networks. Xiviv preprinl urXic:1910.01111 2019.
Dimitri P Bertsekas and John Tsitsiklis. Neuro-dynamic programming. Athena Scientific, 1996.
Jalaj Bhandari and Danicl Russo. Global optimality guarantces for policy gradient methods. arXiv preprint drXiv:1906.0179 2019.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. Operations Research, 69(3)9950-99) 973, 2021.
Shalabh Bhatnagar, Mohammad Ghavamzadeh, Mark Lee, and Richard S Sutton. Incremental natural actor-critic algorithms. Advances neural information processing systems, 10:1 2007.
Qi Cai, Zhuoran Yang, Jason D Lee, and Zhaoran Wang. Neural cinporal-differenee learning converges to global optima. Advances in Neural Information Processing Systems, 32, 2019.
Semih Cayei, Niao He, and R Srikant. Linear convergence of entropy-regularized natural policy gradient with linear function approximation. Xi preprint arXiv:2106.004 04096, 2021.
Semih Cayci, Siddhartha Satpathi, Niao He, and R. Srikant. Sample complexity and overparameteriza- tion bounds for -ifporal-diiference learning with neural network approximation. IEEE Transactions on Aulomatic Control, 68(5):2891 2905, 2023. doi: N0.1109/TAC.2023..
Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. arXiv preprint arXiv:2007, 06558, 2020.
Zaiwei Chen, Sajad Khodadadian, and Siva Theja Maguluri. Finite-sample analysis of off- natural actor-critic with lincar function approximation. arXiv preprint arXiv:2105. 12540, 2021.
Zaiwei Chen, Sajad Khodadadian, and Siva Theja Maguluri. Finite-sample analysis of off-policy natural actor-critic with linear function approximation. IEEE Control Systems Letters, 2022.
Thomas M Cover and Joy A Thomas. Elements of information theory (wiley series in telecommmications and signal processing), 2006.
Felipe Cucker and Ding Xuan Zhou. Learning theory: approcimation theory viewpoint, volume 24. Cambridge University Press, 2007.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over- parameterized neural networks. In International Conference Learning Representations, 2018.
17

---

Published in Transactions on Machine Learning Research (04/2024)
Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In International conference on machine learning, pp. 1329 1338. PMT.R, 2016.
Zuyue Fu, Zhuoran Yang, and Zhaoran Wang. Single-timescale actor-critic provably finds globally optimal policy. In International Conference on Learning Represenlations, 2020.
lan Goodfellow, David Warde-Farley, Mehdi Mirza, Aaron Courville, and Yoshua Bengio. Maxout networks. In International conference on machine learning, pp. 1319 1327. PMLR, 2013.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International Conference on Machine Learning, pp. 1870. PMLR, 2018
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. arXiv preprint or arXiv:1806.07577 07572, 2018.
Ziwei and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks. arXiv preprint arXiv: 12292, 2019.
Ziwei Ji, Matus Telgarsky, and Ruicheng Xian. Neural tangent kernels, transportation mappings, and universal approximation. In International Conference on Learning Representations, 2019.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In In Proc.
19th International Conference on Machine Learning. Citeseer, 2002.
Sham M Kakade. A natural policy gradient. Advances in newral information processing systems, 14, 2001.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal-gradient methods under the polyak-lojasiowiez condition. Joint European Conference on Machine Learning and Knowledge Discovery in Dalabases, pp. 795 811. Springer, 2016.
Sajad Khodadadian, Zaiwei Chen, and Siva Theja Maguluri. Finite-sample analysis of off-policy natural actor-critic algorithm. In International Conference on Machine Learning, pp. 5420-5431 PMLR, 2021a.
Sajad Khodadadian, Prakirt Raj Jhunjhunwala, Sushil Mahavir Varma, and Siva Theja Maguluri. On the linear convergence of natural policy gradient algorithm. arXiv preprint ar Xrv::21005001. 2021b.
Vijay R Konda and John N Tsitsiklis. Actor-critic algorithms. In Advances in neural information processing systems, pp. 1008 1014. Citeseer, 2000.
Vijay R Konda and John N Tsitsiklis. Onactor-critic algorithms. SIAM journal on Control and Optimization, 42(4)):1443 1166, 2003.
Erwin Kreyszig. Introductory functional analysis with applications, volume 17. John Wiley & Sons, 1991.
Harshat Kumar, Alec Koppel, and Alejandro Ribeiro. On the sample complexity of actor-critic method for reinforcement learning with function approximation. aiv preprint arXim:1910.08, 12, 2019.
Panqanamala Ramana Kumar and Pravin Varaiya. Stochastic systems: Estimation, identification, and adaptive control. STAM, 2015.
Guanghui Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sampling com- plexity, and generalized problem classes. arXiv preprint arXiv:2122.00135, 00135, 2021.
Alex X Loc, Amusha Nagabandi, Picter Abbeel, and Sergey Levine. Stochastic latent actor-critic: Deep reinforcement learning with latent variable model. Advonces in Neural Information Processing Systems, 33:741-755 2020.
18

---

Published in Transactions on Machine Learning Research (04/2024)
Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural proximal/ /trust region policy optimization attains globally optimal policy. arxiv preprint orxi 10306, 2019.
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning, pp. 6820-6829. PMLR, 2020.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In Inter- national conference machine learning, pp. 1938-1937. PMLR, 2016.
Ofir Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans. Trust-pel: An off- trust region method for continuous control. arXiv preprinl Xin: (an::7700018,, 2017.
JR Norris, Markov Chains, volume 2. Cambridge University Press, 1998.
Samet Oymak and Mahdi Soltanolkotabi. Toward moderate overparameterization:: Global convergence guarantecs for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 1(1):84-10 2020.
Razvan Pascanu and Yoshua Bengio. Revisiting natural gradient for deep networks. arXi::1301.958, 2013.
arXiv preprint
Jan Peters and Stefan Schaal. Natural actor-critic. Neurocomputing, 71(7-9):1180-11199 2008.
Shuang Qiu, Zhuoran Yang, Jieping Ye, and Zhaoran Wang. On finite-time convergence of actor-critic algorithm. IEEE Journal on Selected Areas in Information Theory, 2(2):652-664, 2021.
Siddhartha Satpathi, Harsh Gupta, Shiyu Liang, and R Srikant. The role of regularization in overparame- terized neural networks. In 2020 59th IEEE Conference on Decision and Control (CDC), pp. 4683-4685 IEEE, 2020.
John Schulman, Sergey Levine, Picter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889 1899. PMLR, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimiza- tion algorithms. arXiv preprint Xio::707.06337" 2017.
Shai Shaley-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Lior Shani, Yonathan Efroni, and Shie Mannor. Adaptive trust region policy optimization: Global con- vergence and faster rates for regularized mdps. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5668-5675, 2020.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Determin- istic policy gradient algorithms. In International conference on machine learning, pp. 387-395. PMLR, 2014.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Dricssche, Julian Schrittwieser, Ioannis Antonoglon, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of with deep neural networks and tree search. nature, 529(7557):484 489, 2016.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15(1): 1929-1958, 2014.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
19

---

Published in Transactions on Machine Learning Research (04/2024)
Richard S Sutton, David A McAllester, Satinder P Singh, Yishay Mansour, et al. Policy gradient methods for reinforcement learning with function approximation. In NIPs, volume 99, pp. 1057-1063 Citeseer, 1999.
Csaba Szepesvári. Algorithms for reinforcement learning. Synthesis lectures artificial intelligence and machine learning, 4(1):1-103, 2010.
VN Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Measures of Complezity, 16(2):11, 1971.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global opti- mality and rates of convergence. aiv preprint ArX::11909.01 2019.
Ronald Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-25) 1992.
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.
Tengyu Xu, Zhe Wang, and Yingbin Liang, Improving sample complexity bounds for actor-critic algorithms. arXiv preprint arXic:2004.1120 12956, 2020.
Wenhao Zhan, Shicong Cen, Baihe Huang, Yuxin Chen, Jason D Lee, and Yuejie Chi. Policy mirror descent for regularized reinforcement learning: A generalized framework with linear convergence, ar preprint arXiu:2105.11066 2021.
Guodong Zhang, James Martens, and Roger Grosse. Fast convergence of natural gradient deseent for over- parameterized neural networks. arXio preprinl arXio: 10961, 2019.
Junyu Zhang, Chengzhuo Ni, Csaba Szepesvari, Mengdi Wang, et al. On the convergence and sample efficiency of variance-reduced policy gradient method. Advances in Newral Information Processing Systems, 34, 2021.
A Finite-Time Analysis of Neural NAC
In this section, we provide the convergence analysis of the algorithm.
A.1 Analysis of Neural Network at Initialization
For 8 (0, 1) and any Ro 0, let
16R1 Vm
Do m, 8)
Ro + Vlog(1/5) + Volog(m)
(40)
and define
Ao
sup #:|1 m Σ
m Ro
1 10 (0)x)
s Po(Ro, Po(Romm,6)) vml
Ro
(41)
The following Jemma bounds the deviation of the neural network from its linear approximation around the initialization, and it will be used throughout the convergence analysis.
20

---

Published in Transactions on Machine Learning Research (04/2024)
Lemma 3. Let (0) /V(0, Id) for all i E [m]] 0 B no (f(0)) and 0' Bo (0) for some Ro 0. Then,
sup
(1 [[00=200] - 1 (0)=0))))) 0 (0)x S m. 8),
(42)
*ER* 51 V
("10T=20) - 1 10 (0)00))20)) 0, )/T= s Ro m, m, 6),
sup
(43)
=1 vm
m
Σ (1
TTT200 (0T (0))20)) xTT0/ TT Po(Ro, m. m, 6),
sup BER-II
(44)
V m
under the event Ao defined in equation 41, which holds with probability at least - 5 over the random initialization of the actor.
Proof. Let Pr = for E Bd | S 11. For x E Sa. let
S(x,0) = {i E [m]] 1 10, =20} * 1 (0) (0)
For any i E (ax 0), the following is true:
10. (0)a - (0)z - 21 ø1 S 10, - (0))l2
(45)
where the first inequality is true since s0g (0)x) * (0 x) and the second inequality follows from Cauchy-Schward inequality and x E Qg. Therefore,
S(x,0) c fie [m] 10. (0)= s 100, (0)l2))
Since
(110T=20) - (100(0)200)) )o (0)z (0)z
Σ (ES(x.0)
|0_ (0)a).
m
mm
we have:
m
m
x20) (1000220)
1 100
-1 (00
S
Σ
1 (100 500 10, 0.(0)]l.
m
Vm
Since max;g[m] ||0: - (,(0))12 S Rs.
vm + the above inequality leads to the following:
10TT2200 107 (0T (0))20)) 00 (0)z
Ro
<
[ie, (0)= \s8o//m)"
Taking supremum over x E Pa, and using Lemma 4 in Satpathi et al. (2020) on the RHS of the above inequality concludes the proof.
In order to prove equation 43, similar to equation 45, we have the following incquality:
0 œ < 10_ 0, (0)zl ||0, 0,(0)]22
Using this, the proof follows from exactly the same steps.
Note that Lemma 3 is an extension of the concentration bounds in Ji & Telgarsky (2019); Du et al. (2018); Salpathi et al. (2020) for neural networks. On the other hand, our concentration result provides uniform convergence over S2t = {a E Rd : ||ж||| < 1} rather than finitely many points, thus is a stronger con- centration bound compared Telgarsky, 2019; Du al., 2018). We need these uniform concentration inequalities to address the challenges due to the dynamics policy optimization, e.g., distributional shift.
the ones the literature, which are used to analyze neural networks (Ji &
21

---

Published in Transactions on Machine Learning Research (04/2024)
A.2 Impact of Entropy Regularization
First, we analyze the impact of entropy regularization, which will yield key results in the convergence analysis.
Proof of Proposition 2. Recall from Line 2 in Algorithm 3 that the policy update is as follows:
0( + 1) = (() + "h - ()((((())))))))))))))))))>>))) - (()))
Let B(t) = 8(t) 8(0) for all t 2 0. Then, the update rule can be written as:
1) (1) 7) + u/.
Since the step-size is n. 1+1 we have:
O(t 1) = X(t 1)
Uks
k=0
by induction. Hence, by triangle inequality:
0. + 1)l12 110, + 0, (0)1l2
|uz,ul22
(46)
A(t 1)
for any (m]. Note that us E B (0) E [m]. Hence, by equation 46, we conclude that
(() as consequence of projection, therefore || S R/vm for all
max [t0((t) (,)ll S A/m' (E[m)
(47)
for any 2 0. Also, since we = u - ((e(t) - 8(0)), we have:
sup
|u, ll2 < || l| + All(() 0(0)l2 s 2R.
(48)
120
Under a constant step-size v) E (0, 1/A), we can expand the parameter movement for any / 2 as follows: 0,(l + 1) = 0,()) - (1-1)A) + 1 úi
= 0, 1)- (1 2/ + n - A4) + mu
= 01( - ,/ + Σ (1 - (1-mAA" 17 Σ (1 - u
k=
k=0
for any neuron i E [m). Then, we have:
R
(0,(t+ 0.0))l2 S (1 11) aa-
(1 (1 - )))++),,
X/m
k=
S R
(49)
A/m
which follows from triangle inequality, ||u, S R/ Vm due to the projection, and the fact that (1 - (1 ())))) < for any 2
In order prove the lower bound for inf (alss, first recall that ne(a(s) & exp(Je(s, a)). Hence, uniform upper bound on [f((s, a)) over all t 2 0 and a) S x A suffices to lower bound m. (als). By symmetric initialization, fo(s.a) a) 0 for all a) E S x A. Hence,
1 m c (1i(t)) (p.(t))(((0)) (s) 10, (0)(..)20)) Vm Σ
f)(s
ca (1T 1,00 (0)0.))0))) (1))))) (50)
22

---

Published in Transactions on Machine Learning Research (04/2024)
First, we bound the first summand the RHS of equation 50 by using equation 47 and triangle inequality:
c (0.(00) (()) (s, a) (o) (0()))20)) )
R
sup
X²
(51)
8,0
since |c:1 (o) (0(s,))20) (s. a)l < 1. For the last term in equation 50, first note that maxie(m] [10,(t) (1 (0) Aym so we can use Lemma 3. By using triangle inequality and Lemma 3:
-
R (,.
(1 [oT (s.a)20) 1l (oT (0(s.))))))) )0 (t) a S Po
with probability at least 1 over the random initialization of the actor network. Hence, with probability at least 1 - 6,
sup [pp]f(ss, a)l & R/A+ + po ( (. mm.6) 6).
8,0
and n.(ass) 2 e x 2po & m.m.)
A.3 Lyapunov Drift Analysis First, present key lemma which will be used throughout the analysis. Lemma 4 (Log-linear approximation error). Let
exp fo(s, a)o(t))
(a(s))
En'es exp V ())))
be log-linear approzimation of the policy Te Talas)). Then, for any d (0, 1), we have:
(als)) Tx. (a)
R (m.m.))
sup
sup
log
s 3po
(52)
120 5,a
over Ag-
Proof. Note that (s (f((s)))0))) for a ReLU neural network. By using this, we can write the log-linear approximation error as follows:
Vioos,aa)) log (a(s)) < (() - fols,, (l),,a)) - log Eve v fo(s)d' (V) ( To()) (53)
Te (a)s)
Ew So(o,0')((1)
By log-sum incquality (Theorem 2.7.1 in Cover Thomas (2006)), for any Fas yo O,
log
En Ia
Σ
Ha
log Ia
En
ya
Fea
ya
Setting za VT and ya = V V Tolcs00t0/.//ccco))77///aaa))
we have:
En V (0().d))(())
log Ex V folaaa000)0))
(54)
Setting 8a ve V fo(ssa)((1) and x vv V
To(1) we have:
log E. v feleaa))(0))
En VT (olo,a))))) $ [Vd(s))( ())
(55)
23

---

Published in Transactions on Machine Learning Research (04/2024)
Using equation 54 and equation 55 to bound the last term in equation 53, we obtain:
#1(a]s) log {a(as))
$ (VV((()))) - VJo(s,a)) + Σ
VJo(s, 0(1) (56)
By Lemma 3, under the event Ag, ((V Hence, under the event Ao, we have:
Vfo(s, To(t) S (o(R m. 8) for all t 0,8 S, E E..
#r(als) (<(a
sup
sup
log
(R/2
which concludes the proof.
The following result standard in the analysis of policy gradient methods (Kakade & Langford, 2002; Cayci et al., 2021). Lemma 5 (Lemma 5, (Cayci et al., 2021)). For any 0, E Rd and μl, we have:
Te Tg (a|s) To(a|s)
(A) - V To (1) = y- E d. (-)))()))) AA (s, + Alog
(57)
where A is the adventage function defined in equation 8.
Lemma 5 is an extension of the performance difference lemma in Kakade & Langford (2002), and the proof can be found in Cayci et al. (2021). In the following, we provide the main Lyapunov drift, which is central to the proof. This Lyapunov function widely used in the analysis of natural gradient descent algorithms (Peters & Schaal, 2008; Agarwal et al., 2020; Wang et al., 2019; Cayci et al., 2021).
Definition 1 (Potential function). For any policy π E II, the potential function W is defined as follows
((T) = -Eandy' (xx((T(1s))
(58)
Lemma 6 (Lyapunov drift). For any 12 0, let A, = Vx (4) - V (V). Then,
((T+1)) (TT)) mAV((T)))) (1 7) + 2
+ n E.aa (-19(
V fols, a)u Q (s
(59)
n B.ary a~- (118
V fo(s, - Q (s,
+ (mA 6) R2/ X, 5) 21, RV pa (R/ m.
in the event Ao which holds with probability at least - 8 over the random initialization of the octor.
Proof. First, note that the log-lincar approximation of no is smooth (Agarwal et al., 2020):
|| Tolls) V log To S ||0 -
(60)
for any 8, since [VSo(s,))]2 $11 1. Also,
Te (a(as)
(((+1)) - (TT)) E Eewas' art (H1s) log
Te+ (a|s)
To use the smoothness of log-linear approximation, we use a telescoping sum and obtain:
(TT+1) V(T.)) Fondz" _a-a log (a(as))
log (a(s)) (als) (als)
(a
log
(tt1(a)s))
24

---

Published in Transactions on Machine Learning Research (04/2024)
By Lemma the last two terms are bounded by Po(R/), m, 6). Let
Dj B a (-1+) log (a(ss) To+i (a|s)
Then, by the smoothness of the log-linear approximation, we have:
Dr S - -Tlle am- (-1a) V log (a(as)) + vi w 1
2
Recall A, = -V (1) - V (1)). Using Lemma 5 and the definition the advantage function, we obtain:
D (AL me(1 7) Be (a) 1Q (s, a) A log ({(sss)]
T/e Te B (-1s) V log tee (als)um ox (8, a)]
(61)
Since we have Vlog#e(als) = V E - Vfo(s, we have the following inoquality:
Dt S (AX(((T)) 70(1 - 7)4,
+ M Snd (a)ss) V fo (0(s,a)u, au
(s, (s,a) af) QT'
Ti E B arm (11) V fo(s, -o(s,a)): (8, + Afe(s, a)]
(ar(s) ma fo(ss a)w! + n || wx
+ T/, "
aeA
By the definition of we u4 10(()) ((0) and the fact that fo(s, a) 0 due to the symmetric initialization, we have:
V fo(s,a)w: V fols, a)u, A fo(s,a)0(t).
Substituting this identity to the above inequality, we have:
D, < (A.((TT)) - n - 7)4,
MeBnnd (a)))) V fo(s; a)w 0%*
Be sa> (11)) V fo(s, (s)
(62)
27t RE and
Te(als) (alss)
(als) - (a(ss) (V/(s, - Vlo(s,a)) To(0] + 21 n2,
acd
where we used equation 48 to bound
||, Il2. Furthermore, note that
1 m
(Vf((s,a) - o)) mm Σ (H10T020) (00 (1000000)))))) 07 (T)(z) (t)z )(
for any TT e Rd. Thus, by Lemma 3,
sup (V Vlo(s,,)))0000 S m)) 8.a
This bounds the penultimate term in equation 62. Finally, in order to bound the fifth term in equation 62, we use Pinsker's inequality and then Lemma 4:
(a(s))
sup
Te( Te (-(+))] < sup ES
Σ
(e(s))) log (a(ss) S (o((R/A,
#
Substituting these into equation 62 and then into equation 59, the desired result follows.
25

---

Published in Transactions on Machine Learning Research (04/2024)
A.4 Analysis of the Function Approximation Error: How Do Neural Networks Address Distributional Shift in Policy Optimization?
As specific feature of reinforcement learning, policy optimization in particular, the probability distribution of the underlying system changes over time as a function the control policy. Consequently, the function approximator (i.e., the actor network in our case) needs to adapt to this distributional shift throughout the policy optimization steps. In this subsection, we analyze the function approximation error, which sheds light on how neural networks in the NTK regime address the distributional shift challenge.
Now we focus on the error term in Lemma 6:
bios
B
Σ
- (m((ds)-
(V ( a)u, Q (s, a))
(63)
aEA
Note that bias can be equally expressed as follows:
bias = B (T(aas)) - (als)) (V log (a(ass), - Ex (s, a))
aEA
(T((a)s) ' (als)) (((ssa)) v.
E Eon
where EX is the soft advantage function. The above identity provides intuition about the choice of sample- based gradient update us Algorithm 2, which we will investigate detail later.
Let
Lo(u, = E fo(s, ((ss,a)u a) QT
In the following, we answer the following question: given the perfect knowledge of the soft Q-function Q what is min, (u, ((t))
Proposition 3 (Approximation Error). Under symmetric initialization of the actor network, we have the following results:
Pointwrise approzimation error: For any 0 E A and 2 F
Lo(u, 0) s
4v2
E
min
(64)
ueRmxd
m
where the expectation is over the random initialization of the actor network.
Uniform approrimation error: Let
A1 = sup min V fo(s,a)u- (7
(ldlog(m))+ + Vlog vm
20
K ))}
s.a
AE0
Then, under Assumption 3, A holds with probability at least 1 1-5 5 over the random inétialization of the actor
nelwork. Furthermore,
E L sup min Lo(u, 07] <
min
402 = ((dlog(m)) + Vlog log
( ))
K
(65)
Proof. For given policy parameter E O let the transportation mapping of Q be vg and let (,, oo (O,(0))ss 1 1(07 (0)(s))20) i e [m].
Note that (s, (s. a)] = Q (s, a) for any (s, a) E S x A. Also, let
1
w/ u (0.
kE(m)
26

---

Published in Transactions on Machine Learning Research (04/2024)
Since up (0) for all I ④ projected risk minimization within B ne for R 2 D' suffices for optimality. We have
fo(s, a)uz = m Σ (s,
1
and
min Lo(u, 0) S E Bo a (155
(= Σ
-
(66)
1. Pointwise approximation error: First we consider a given fixed 0 θ. Taking the expectation in equation 66 and using Fubini's theorem,
E[min (o, 0)] S E.a.
(
Σ i=1
!
m,/2
m/2
2E,
Var(Y, (s,
+
4 m
Σ
Cou(Y) ()) (s.
(67)
m
4,7
(8)))
4lB,,a
(68)
m²
m² Es
(X a))
(69)
where the identity equation 67 is due to the symmetric initialization, equation 68 holds because {Y a) = 1......, m/2} is independent (since {0,(0) : E [m/2]} is independent). By Cauchy-Schwarz incquality
and the fact that vg E Ho: we have:
(s, S (0))ll so.
Hence, using this in equation 69, we obtain:
4v²
E Lo(u, 0)
(70)
m²
2. Uniform approximation error: For any E O since Q
FK,Y, there exists a (a ag. .........0 aak E RKK such that ||a < 1 and Uo Σ. x uh... We consider the following error:
(e) = sup
sup BEB
Σ -EV(
(71)
(
m
Then, we have the following identity from the definition of 0p:
K
Rm ( sup sup s.a 8
Σ
a
(72)
k=1
where (s, ( (0.(0))(s (0)(s, a) 0}. Then, by triangle inequality,
Rm (0) < sup 8.0
sup
max k
Σ - a)]| I|a 1=1
- 1 m
max
sup 8
- (s,
(73)
KE[K]
m
By using union bound and equation 73, for any
0, have the following:
K
P(Rm (0) > 2)
P
sup
LELT (s, a)] > z).
(74)
k=1
8,0
T=1
We utilize the following to obtain uniform bound for Em (8, El a)]l over all (8, E A
27

---

Published in Transactions on Machine Learning Research (04/2024)
Lemma 7. For any & [K], for any ò E 1), the following holds:
4
48 1og(1/8)
sup 6,0
Σ
-
S
(75)
vm
v Vm
i=1
with probability at least 1 6. 6.
Hence, using Lemma 7 and equation 74 with 2 4odd 1/4
4u [og((/4)
we conclude that
V/n
vm
45 4 48 4B//lo((K/0)
Rm (+) v
Vm
vm
with probability at least 1- 8. The expectation result follows from this incquality.
0
Now, we have the following result for the approximation error under ne.
Corollary 4. Under Assumption we have:
1652
(ldlog(m)) + log ( ( 5 )
E E[LADnA min Lo(u, 0(t)) -
m
where the event A1, defined in Proposition 3, holds with probability at least 1 over the random initialization of the octor.
Remark 8 (Why do we need uniform approximation error bound?). Note that for a given fixed policy na, 0 E θ, Proposition 3 provides a sharp pointwise approximation error bound as long as Q E F, with a corresponding transportation map ug. In order for this result to hold, vg (0, (ep ()) is required to be iid for i E [m/2], which is the main idea behind the random initialization schemes for the NTK analysis. On the other hand, in policy optimization, 0(t) depends on the initialization A(0), therefore "ott (0, (O)))s, a) [(T (0)s,a)20) () is not independent - hence, in equation 67. Furthermore, the distribution of (s,a) at time 1 > 0 also depends on To- Therefore, the pointwise approximation error cannot be used to provide approximation bound for Q under the entropy-regularized NAC. In the existing works, this important issuc regarding the temporal correlation and its impact on the NTK analysis was not addressed. In this work, we utilize the uniform approximation error bound provided in Proposition 3 to address this issue for K functions to define the function class, while it may be possible to extend this to infinitely- many basis functions by using more general statistical complexity concepts.
(s, (s, a)) # 0 for i i j
In the absence of QTe the critic yields noisy estimate Øx" Additionally, the samples {(sn, an) d <e(+ss) n 2 0} are used to obtain the update ue. These two factors are the sources of error in the natural actor-critic method: min, (u(u, O(t)) S Lo(u,, O(t)). In the following, we quantify this error and show that:
1. Increasing number of SGD iterations, N,
2. Increasing representation power of the actor network in terms of the width m,
3. Low mean-squared Bellman error in the critic (by large m², TT),
lead to vanishing error.
First, we study the error introduced by using SGD for solving:
Σ (s, ). E Bd (0),
(u,
(u, (tt) E Esway (+1))
T log (als) -
(76)
Note that the auxiliary objective in equation 76 is Lipschitz continuous with modulus qmaz = 4(2R A log mmn)) due to ||u||2 5 R for u E Bd (0), | log (a|s)] S 2/ a)]l S for ReLU networks, and the bound on (5, a)l s 2 (s, a) < 2/7 (s, a) - A log म (a|s)) < 2(R - A Alog mmn)) that follows from <<(als) Mnin by Proposition and (s, a) & R from the max-norm projection with radius R for MN-NTD.
28

---

Published in Transactions on Machine Learning Research (04/2024)
Proposition (Theorem 14.8, Shalev-Shwarte & Ben-David (2014)). Algorithm (Lines 2-2) with step-size OA = RRV Vimaw N yields the following resull:
Rqmar
(u, min Lu 0(t)) _
(77)
VN
for any R21 v where the expectation is over the rondom samples {(s,. an) n [M]]
The following proposition provides an error bound in terms the statistical error for finding the optimum "y via SGD as well as TD-learning error in estimating the soft Q-function. Let
Le(u, = (a (vo ( - - Ex, (s.a)) a)) 9
(-13)
(78)
Proposition 5. Let A Ao A1 A2, hence P(A) 35. We have the following inequality:
ELL ((t)) 8min (ILLO(u, ( Vs((s, a)] ul u 2Rqma
VN + + 1 ( (x,a))) (79)
where the expectation is over the samples for crilic (TD learning) and actor (SGD) updates. Consequenlly, we have:
2v TVRggax
Le 0(t)) S 3 EE| min V
Lo(u, 0(t))
+ 3-0 (R/2,, m,
"EB m. (0)
N
+ 3E Ex,a (8,
Q (s. (80)
under the event A.
Proof. We extensively use the inequality (r + +) s 2x + 2y² for r, E R. First, note that
Lu 0(t) & (u, 0tt) + 2B, 11 (s, (s,
(81)
for any u Bd R (0). Hence, under A Ao A A2, we have:
(,, O(t)) s 2E(L. ((t)) + 21 Q (s, Q (3.
(82)
2Rqmas
2 min wEBd (0)
(u, 0(1) + 2I [1Tx (s, - (s,
(83)
N1/2
2Rgmaz
min WBBd R (0)
Lu, 0()) + 6IE,, 10 (5, T5hh (s, {
(84)
N1/2
where the second line follows from Prop. and the last line follows from equation 81. Consequently, we have:
E EIL,(u,
< 8 min wEBd m, (0)
EE(V fo(s, (3 fo(s, Jul?}
-
2Rqmar
6E. + -.) (c,
(85)
N1/2
where we use (a y) < 2x + 2y² and the following incquality:
T log (als)u E (s, a)) Bandft Var(V fi(s, -5
< (V fe(8, a)u (s,
Using equation 85 and Theorem in Cayei et al. (2023) together with the inequality Vz+y+25 V2 Vy + V2 for x, v, 0, obtain equation 80.
29

---

Published in Transactions on Machine Learning Research (04/2024)
Hence, we obtain the following bound on the approximation error biass Corollary 5 (Approximation Error). Under Assumption 1-4, we have the following bound on the approzi- malion error:
80 vm
(dlog((m)) : + log k)
2v Kqmax
B[1A- bias S Mo
+ 45
N
where A Ao AonAnnAp m' = 0
(ा-
0t and T" 0 ( (1 and P(A)
1-36.
38.
Proof. In order to prove Corollary 5, we substitute the results of Corollary 4 and Lemma. 2 into equation 80. 7
The main message of Corollary 5 is as follows: in order to eliminate the bias introduced by using (i) function approximation, (ii) sample-based estimation for actor and critic, one should employ more representation power in both actor and critic networks (via m and m'), and also use more samples in actor and critic updates (via N and T). Furthermore, Corollary quantifies the required network widths and sample complexities achieve a desired bias e> 0.
In the following subscction, finally prove Theorem by using the Lyapunov drift result (Lemma 6) and the approximation error bound (Corollary 5).
A.5 Convergence of Reguua--Reg Natural Actor-Critic
Proof of Theorem 1. In the following, prove the first part of Theorem 1, where the second part follows identical steps with constant step size v E 1/A). First, note that Lemma 6 implies the following bound:
L (TT+1)) [(me)] s -nA (T (e A) 2n R2 + (md + ()) + 2n, RV Pa R X, m)
me A bios
(86)
By Corollary 5,
2v 2/Raaaz
E A S Ms0 p1
+ 4 =: Chias:
N1/4
where
16 (dlog(m)) Vlog(K/0))
P1 mm
Let v. = (.)(TT)) Then,
Mo+1 1, S Ab ((AAAA 2n R² + ThEbias
+ m. 5) + 2n, R Po
Po (R/A, m)
Since Wh = x041y'
1_ by induction,
F $ (1 T, + m6 A + RR²
+ (Ehios + 2R Po PO x,, m, + (Ppo[R/A,m,.
(1 - 7)
Σ E[1 X { (Ahiass + +2R (u(R/A. +
2R log(t + +1)
A(t + 1)
x2(++11
RSt
+ 4(t + ()),
Hence,
2R + log
4TA
min E(1 < 1- 0ST<T which concludes the proof.
Obias +R Po( R/X,m,
(1 - pol
pal (R/2, 6),
(87)
X(1 - 7)
30

---

Published in Transactions on Machine Learning Research (04/2024)
Proof of Corollary 2. Note that, without the realizability assumptions, have
E
min WEB ma (0)
Lo(u, (())) S Capp
and
3E Bs,a (s, (s. S $3v2 Bly (2.. (x,
(s. a)l
Cpp
where Q5 (s, a) arg min, Bs,a (f(, (s, a))². Substituting these inequalities into equation 80 and replacing ébios accordingly, the proof follows from the same steps the proof of Theorem 1. ]
B Sampling from the Discounted State-Action Visitation Distribution
Given an initial state distribution μ and policy म, under generative model that enables obtaining an independent and identically distributed s from the initial state distribution μ, the procedure summarized in Algorithm 4 yields an iid sample (s. a) such that ~ df and ~ xx1ss) (Konda & Tsitsiklis, 2003; Agarwal et al., 2020).
Algorithm 4: Sampler from dz @ under a generative model
inputs: μc: initial state distribution, æ: policy, 7: discount factor; Set 80 ~ and ag ~ x-110)); for k 0, 1...... do
i Ber(?);
if then
kt1 P(-|s (f-]st,at) at);
s+1 x x-1ls+t1);
else
return (s, a) (s a+
The generative model enables the controller to access iid samples from the state-action visitation distribution ds. by resetting from the initial state distribution Algorithu that we analyzed in this paper. In the absence of such a generative model, the sampling procedure in an on-policy RL setting is performed by using a single Markovian trajectory (Sutton & Barto, 2018). Ergodicity is required in this case, which always satisfied for irredueible and aperiodic Markov chains with finite state space, where the verification of ergodicity for Markov chains with infinite state space is more complicated (Norris, 1998). Under Markovian sampling procedure in the ergodic setting, the distribution mismatch that led to the concentrability coefficient assumptions (Assumption 4') needs to be replaced by the stationary distribution {E**), under policies {T1}. as
which critical in the actor-critic framework in
dz (s) (a)s) (s, co.
0EtET (s,0)SSXA
Furthermore, a finite-time analysis the Markovian sampling would introduce new terms that depend on the mixing-times analyze the transient behavior under each policy (Bhandari et al., 2021: Cayci et al., 2023).
31

---

Published in Transactions on Machine Learning Research (04/2024)
C Proof of Lemma 7
Consider 9 E FB with a corresponding transportation map v E Hz. Using Cauchy-Schwarz incquality,
m
(0:(0))=1 (0)z 0)
E sup x:||a||251
g(x)
m
s E sup #
v(,( (0) (07 (0)20)
E[c(0:(0)) (o] (0=22))]
Define b; = L00( (o] (0)=20)- Define class B containing all possible values taken by b = ) over {o ||æ||2 I } for a fixed (0). Further, using Sauchy-Schwaard inequality,
E sup a:||a||a511
g(x))
(0:((0))=1 (0] (0)220}
m
(b: Eb,) T(b Eby) + 40
sup BEB m
Using the symmetrization argument with Rademacher random variables Jiy 's,
E
sup =
g((x)
1 1 Σ c (0000))) (0)20)) 4Bo E, sup be B m
Σ Eagb
402
Note that given 8(0), B a finite set. We apply Massart's Finite Class lemma to have,
B (0, 6,10(0)) < |100000)111(000000)1111 2 log B
E
sup Σ b m
m²
$$
We calculate [B] using VC-theory. Each element b, of b, partitions the space [||=||| 1} Rd into two half planes where one half takes value v(f:(0)) and another half takes value O. Hence all possible values taken by in space [||=]|| }} is equal to the number of components in the partition made by m half planes {b.)m The number of such components bounded by d++1 + using the growth function defined by Vapnik Chervonenkis (1971). Hence [B] S md and the following holds:
1 77
125 Vdlogm
E sup #
g(z))
J (0
m
The result. follows from Jensen's inequality.
32


Reviews:
[{"review_id": "rywyU0o2Mh", "reviewer": "Reviewer_Qxav", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, as far as I could check, the analyses are correct. I particularly found the persistence of excitation discussion interesting as it validated existing techniques. My main concerns lie in 1) the strength and reasonableness of the assumptions made, and 2) what can be taken away from the work? To elaborate:\n\n**Strengths**:\n1. The paper is nicely structured and written.\n2. They characterize trade-offs in the analyzed algorithm, and provide some understanding around existing techniques in the literature. While it's intuitive that entropy-regularization has implications for exploration, it was interesting to see the projection radius and network width's role in it characterized.\n3. They provide sharp bounds on sample complexity, iteration complexity, and network width. As far as I was able to check, the analyses appear correct.\n\n**Weaknesses**:\n1. Assumptions 2 and 3 on realizability seem strong- particularly Assumption 3. Can the authors elaborate on the necessity of these assumptions, and whether or not they can be weakened? Is there any analyses or empirical evidence validating that such inherent structure can be reasonably expected, i.e., are they realistic?\n2. The work is purely theoretical, largely contributing characterizations and understanding of an algorithm. However, it's unclear if more can be concluded from the results as the algorithm and the specific modifications to it are relatively widespread already. To clarify, I see value in the theoretical contribution presented, and in the analysis techniques adopted, but are there any concrete take-aways for someone looking to use some form of entropy-regularized neural actor-critic on some problem? e.g., the network width bounds and discussion around the critic only needing to approximate the value for a single policy at a given moment vs the actor needing to approximate the policies corresponding with the sequence of critics (Remark 5), could be emphasized as some practical consideration in the conclusion.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers an entropy-regularized natural actor-critic algorithm with neural network function approximation, and provides a finite-time analysis. Specifically, they provide sharp bounds on sample complexity, convergence rate, and network width. They introduce this notion of \"persistence of excitation\" to suggest that the combination of over-parametrization, entropy regularization, gradient clipping, and averaging leads to sufficient exploration without the need to assume this as done in previous analyses.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would like more discussion/treatment around the weaknesses raised above included in the main text. A minor note, Equations 5 and 7 were both referred to as a \"soft Q-function\", despite being different (as acknowledged in the text)- this may cause confusion and should be emphasized.\n\nThat said, these are points that would simply strengthen the work in my view, and I am overall positive about the work in its current state.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "x8FvikwhKC", "reviewer": "Reviewer_8Z4o", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Main Argument\n\nAlthough I am not an expert on policy gradient theory nor natural actor-critic algorithms, I believe that this paper provides ample theoretical proof to support the claims made therein. Compared to current works, the paper provides sharper sample and iteration complexity bounds for natural actor-critic algorithms. Further, the paper provides convergence guarantees in an entropy regularized setting with weaker assumptions than current works. In an entropy un-regularized setting, the paper improves upon current sample complexity bounds with standard distribution mismatch conditions. Finally, the theoretical analysis considers practices which are common in implementation, such as gradient clipping, weight decay, and entropy regularization -- things not often discussed in similar works. Nevertheless, the paper suffers from a number of issues which complicates the paper evaluation process:\n\nIn section 2, there are a number of errors. First, when discussing policies, the paper defines a policy as a function $\\pi : \\mathcal{S} \\to \\mathcal{A}$. Following, the paper states that a policy\n\n> assigns some probability of taking an action $a \\in \\mathcal{A}$ at a given state $s \\in \\mathcal{S}$\n\nThese two definitions contradict each other. The first definition indicates that $\\pi$ _deterministically_ selects an action in a given state (i.e. policy $\\pi$ is a mapping from states to actions), whereas the second definition indicates that $\\pi$ is a mapping from states to probability distributions over actions. Later, softmax distributions are used for policies, indicating that the first definition above is incorrect.\n\n\nNext, in section 2.1, paragraph **Entropy-regularized objective**, the paper doubly defines _soft Q-functions_ as\n\n\\begin{equation}\nq_\\lambda^\\pi(s, a) = \\mathbb{E}_\\pi \\left[ \\sum^\\infty\\_{k=0} \\gamma^k (r(s_k, a_k) - \\lambda \\log \\pi(a_k \\mid s_k)) \\mid s_0 = s, a_0 = a \\right]\n\\end{equation}\n\nand\n\n$$\nQ_\\lambda^\\pi(s, a) = r(s, a) + \\gamma \\mathbb{E}\\_{s' \\sim P(\\cdot \\mid s, a)} \\left[ V\\_\\lambda^\\pi (s') \\right]\n$$\n\nThese two functions are **not** equal -- there is a difference of $\\lambda \\log \\pi(a \\mid s)$ between the two. When the term _soft Q-function_ is used later, it is not clear which of these functions are referred to since both of these functions are defined as being the _soft Q-function_. Commonly, the second function is taken as the definition of the soft Q-function [1, 2, 3].\n\n\nNext, in section 3.1, the optimization problem to estimate the natural gradient is defined as \n\n\\begin{equation}\nu^*_t = \\min\\_{u \\in \\mathcal{B}^d\\_{m, R}(0)} \\mathbb{E} \\left[ (\\nabla^\\top \\log \\pi_t (a \\mid s) u - \\Xi\\_\\lambda^{\\pi_t}(s, a))^2 \\right]\n\\end{equation}\n\nThis optimization problem resulted in a number of questions for me. First, what is the expectation with respect to? Judging based on Equation (15) from the paper, it appears that the expectation should be with respect to both $\\pi_\\theta$ and $d\\_\\mu^{\\pi\\_\\theta}$. But, the paper indicates that this optimization problem is approximately solved _in the absence_ of $d\\_\\mu^{\\pi_t}$ and $\\Xi\\_\\lambda^{\\pi_t}$, which makes me think that the expectation is not with respect to $d\\_\\mu^{\\pi_t}$ at all. Later though, both in-text and in algorithm 2, the policy update uses samples $s_n \\sim d\\_\\mu^{\\pi_t}$ when solving this optimization problem. Are samples from $d\\_\\mu^{\\pi_t}$ utilized or not? What does it mean to solve this optimization problem _in the absence of_ $d\\_\\mu^{\\pi_t}$ when samples from $d\\_\\mu^{\\pi_t}$ are used? Further, in this section, $\\lambda$ is introduced as the _regularization parameter_, which is confusing since in preceding sections it was defined as the _entropy regularization scale parameter_. In section 3.1, is $\\lambda$ the entropy regularization scale or is it a new parameter?\n\nNext, the presented natural actor-critic algorithm seems to be theoretically justifiable, but many of the theoretical choices are not practically implementable. For example, in many real-world scenarios we cannot generate samples from $d\\_\\mu^{\\pi_t}$, or else generating such samples is possible yet prohibitively expensive. Since no empirical justification is given for the algorithm, I am wondering if it would be possible to discuss such practical limitations in the paper, perhaps only in the appendix. For example, based on the convergence, sample complexity, and iteration complexity results, how large of a neural network might be usually needed in practice? Do the results extend to continuous action spaces? What ramifications exist if samples from $d\\_\\mu^{\\pi_t}$ cannot be generated?\n\nNext, the paper consistently makes the claim that the actor network learns a state-action value function. The actor network is outlined in equation (18):\n\n\\begin{equation}\nf(s, a; (c, \\theta)) = \\frac{1}{\\sqrt m} \\sum\\limits\\_{i=1}^{m} c_i \\sigma( \\langle \\theta, (s, a) \\rangle)\n\\end{equation}\n\nand the output of the actor networks is passed through a softmax function to generate a categorical policy distribution. To me, this looks like learning action preferences [7], and not action values. What exactly is meant in the paper by statements such as \n\n> the uniform approximation power of the actor network to approximate Q-functions throughout policy optimization steps (pg 2)\n\nHow is the actor approximating a state-action value function? \n\nFinally, some notation is confusing or undefined:\n- In theorem 1 (and in multiple locations in the appendix), the notation $q\\_{max}$ is undefined. What does it mean?\n- The notations $\\mathbb{1}\\_{A}$, $\\mathbb{1}\\_{A_0 \\cap A_1}$, $\\mathbb{1}\\_{A_2}$ _etc_. are used but left undefined. I believe this is the indicator function for the subscript argument. But, what exactly is the subscript? I could not find any indication in the main text of what the subscripts meant. I assume the subscripts refer to the corresponding equations in the appendix. This notation is used in Lemma 2, Theorem 1, Corollary 1, Corollary  2, and multiple locations in the appendix.\n- Given the above point, it is confusing that $\\mathbb{1}_A$ is the indicator function since the notation $\\mathbb{1}${$A$} is used elsewhere, which also seems to be the indicator function for $A$. Are both of these notations referring to the indicator function? Can a single notation be used for the indicator function?\n\n\n# Small Things\n\n**These did not affect the scoring of this paper** \n\nThe **Neural network analysis** paragraph on page 3 has a discussion on first-order optimization methods for overparameterized neural networks. An important class of first-order optimization algorithms here are those related to mirror descent, which is closely related to natural gradient descent [5,6]. The current paper indicates that overparameterized neural networks trained using first-order optimization methods have a bias toward the minimum norm solution, but this phenomenon is actually a bit more general. Overparameterized neural networks trained using mirror descent optimization methods have a bias toward the minimum Bregman divergence (in mirror map) solution [4]. \n\nA number of grammatical errors exist in the paper:\n\n- \"On of the main goals of...\" -> \"On**e** of the main goals of...\"\n- Many times, references are used as nouns. For example \"PG methods were established in (Agarwal et al., 2020).\" Instead, this would be better written as \"Agarwal et al. (2020) established PG methods\".\n- In section 1.1, it is noted that the _policy optimization is stabilized by incorporating ... averaging_, but it is not clear from context what is being averaged.\n \n\n# References\n\n[1] Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, Sergey Levine. Soft Actor-Critic Algorithms and Applications. 2019.\n\n[2] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, Sergey Levine. Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor. ICML. 2018.\n\n[3] Matthieu Geist, Bruno Scherrer, Olivier Pietquin. A Theory of Regularized Markov Decision Processes. ICML. 2019.\n\n[4] Navid Azizan, Sahin Lale, Babak Hassibi. Stochastic Mirror Descent on Overparameterized Nonlinear Models: Convergence, Implicit Regularization, and Generalization. IEEE Transactions on Neural Networks and Learning Systems. 2022.\n\n[5] Garvesh Raskutti, Sayan Mukherjee. The Information Geometry of Mirror Descent. IEEE Transactions on Information Theory. 2015.\n\n[6] Suriya Gunasekar, Blake Woodworth, Nathan Srebro. Mirrorless Mirror Descent: A Natural Derivation of Mirror Descent. Proceedings of The 24th International Conference on Artificial Intelligence and Statistics. 2021.\n\n[7] Richard Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. 2nd Edition. MIT Press. 2018.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "# Summary \n\nThe paper _Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithm_ presents a finite-time analysis of the natural actor-critic algorithm with neural network function approximation. The paper outlines how the natural actor-critic algorithm can attain provably good performance -- in terms of convergence, iteration complexity, sample complexity, _etc_. -- using entropy regularization and a number of implementation tricks including gradient clipping, weight decay, and averaging. The paper demonstrates that these methods are sufficient for avoiding policy collapse and convergence to sub-optimal policies. The paper also provides sample and iteration complexity bounds which improve on the existing bounds in the literature.\n\nIn particular, the paper results are proven for the natural actor-critic algorithm with single-hidden-layer neural network function approximation for both actor and critic.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "To secure my recommendation for acceptance, all issues presented in my **Main Argument** above would need to be addressed.", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "VYHS2o3SQM", "reviewer": "Reviewer_GATe", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength:**  \nThe paper provide a sound technical analysis on a popular (entropy-regularized) algorithm that might be interesting for some TMLR's audience. The claims appear correct, although the proofs in the appendix were not thoroughly verified.\n\n**Weakness:**  \nThe paper's main limitations are its clarity and might seem lack of novelty (although novelty isn't a primary criterion for TMLR evaluation):\n- The paper misses some technical details, for example, why is the projection in (23) can be considered as gradient clipping?. \n- The presentation order is sometimes confusing. For example, the authors mention MN-NTD in algorithm but MN-NTD is introduced in the next page. Another example is that the author mention that we want to control the max norm in Remark 1 but I guess the reason we want this is for Proposition 2? I think the order to present these can be improved. \n- The paper isn't self-contained, often borrowing settings/assumptions/conditions from other works without adequate explanation. One example is the excitation condition (what is the original condition, what modification you made to make it appliable to your setting? What is the condition exactly?). \n- Related to the previous comment, the paper does not provide sufficient justification for some assumptions and settings. For example, in section 3.1: “As a common practice, we fix the output layer c after a random initialization, and only train the weights of hidden layer”. It is totally reasonable, but the paper should still justify why it follows this practice. \n- The current paper reads like a report that borrows tools from various sources, rather than a novel contribution. Elaboration on the new analysis techniques would enhance its novelty and impact. For example, the paper mention that “As a result, we have to use different analysis techniques”. Maybe the authors can follow up the sentence and explain potential questions such as what techniques are new?  Why previous work did not use these? Why did the authors use this particular condition? \n\nIn summary, I would suggest to accept the paper due to its technical merit and relevance. However, to improve its impact and clarity, I would suggest the authors to edit the paper. \n\nOther question: \n- In conclusion, the paper claims that “entropy regularization led to significantly improved sample complexity”, but I think the conclusion from the analysis is that we need overparameterization, entropy regularization, gradient clipping, and averaging?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies an entropy-regularized natural actor critic algorithm, utilizing two separate single-hidden-layer neural networks for the actor and critic, with a softmax parametrized policy. The paper provides a finite sample analysis of the proposed algorithms, and claims that it (1) provides a sample complexity result under mildest distribution mismatch conditions and a sharper sample complexity under a stronger distribution condition compared to prior work, and (2) shows that the combination of overparameterization, entropy regularization, gradient clipping, and averaging leads to the “persistence of excitation\" condition, which then results in improved sample complexity.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I suggest some changes to the paper:\n- (critical) Justification for the assumptions and setting (see my comments in the previous part) and make sure all important details are covered in the paper. \n- (nice to add) Discuss the novelty of the paper, highlighting new approaches or techniques used.\n- (minor formatting fix) Citation style: please use \\citet for citations within the text.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Generally the reviewers were positive on the paper and had detailed reviews, many questions and suggestions for clarifications. The authors responded in detail.
Decision: Accept (poster)