Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies
Authors: Rui Yuan
Simon Shaolei Du
Robert M. Gower
Alessandro Lazaric
Lin Xiao
Venue: ICLR 2023 poster (2023)
Keywords: Discounted Markov decision process
natural policy gradient
policy mirror descent
log-linear policy
sample complexity

Abstract: We consider infinite-horizon discounted Markov decision processes and study the convergence rates of the natural policy gradient (NPG) and the Q-NPG methods with the log-linear policy class. Using the compatible function approximation framework, both methods with log-linear policies can be written as approximate versions of the policy mirror descent (PMD) method. We show that both methods attain linear convergence rates and $\tilde{\mathcal{O}}(1/\epsilon^2)$ sample complexities using a simple, non-adaptive geometrically increasing step size, without resorting to entropy or other strongly convex regularization. Lastly, as a byproduct, we obtain sublinear convergence rates for both methods with arbitrary constant step size.

Published as a conference paper at ICLR 2023
LINEAR CONVERGENCE OF NATURAL POLICY GRADIENT METHODS WITH LOG-LINEAR POLICIES
Rui Yuan
Simon S. Du
FAIR, Meta AI
University of Washington
LTCI, Télécom Paris and Institut Polytechnique de Paris yy42606rr gma i com
asduêcs washi washington..o edu
edu
Robert M. Gower
Alessandro Lazaric FAIR, Meta AI
Lin Xiao
CCM, Flatiron Institute gowerrobert @gmaii..........
FAIR, Meta Al 1 linx@meta. com
lazaric9meta.com com
ABSTRACT
We consider infinite-horizon discounted Markov decision processes and study the convergence rates of the natural policy gradient (NPG) and the Q-NPG methods with the log-linear policy class. Using the compatible function approximation framework, both methods with log-linear policies can be written as inexact ver- sions of the policy mirror descent (PMD) method. We show that both methods attain linear convergence rates and ((1/e²) sample complexities using a simple, non-adaptive geometrically increasing step size, without resorting to entropy other strongly convex regularization. Lastly, as a byproduct, we obtain sublinear convergence rates for both methods with arbitrary constant step size.
INTRODUCTION
Policy gradient (PG) methods have emerged popular class of algorithms for reinforcement learning. Unlike classical methods based on (approximate) dynamic programming (e.g., Puterman, 1994; Sutton Barto, 2018), PG methods update directly the policy and its parametrization along the gradient direction of the value function (e.g., Williams, 1992; Sutton et al., 2000; Baxter & Bartlett, 2001). An important variant of PG is the natural policy gradient (NPG) method (Kakade, 2001). NPG uses the Fisher information matrix of the policy distribution as a preconditioner to improve the policy gradient direction, similar to quasi-Newton methods classical optimization. Variants of NPG with policy parametrization through deep neural networks were shown to have impressive empirical successes (Schulman et al., 2015; Lillicrap et al., 2016; Mnih et al., 2016; Schulman et al., 2017).
Motivated by the success of NPG in practice, there is theories for the NPG method. Neu et al. (2017) provide the first interpretation of NPG as a mirror descent (MD) method (Nemirovski & Yudin, 1983; Beck & Teboulle, 2003). By leveraging different techniques for analyzing MD, it has been established that NPG converges to the global optimum in the tabular case (Agarwal al., 2021: Khodadadian al., 202 Xiao, 2022) and some more general settings (Shani et al., 2020; Vaswani et al., 2022; Grudzien et al., 2022). In order to get a fast linear convergence rate for NPG, several recent works consider the regularized NPG methods, such as the regularzee NPG (Cen et al., 2021) and other convex regularized NPG methods (Lan, 2022; Zhan et al., 2021). By designing appropriate step sizes, Khodadadian et al. (2021b) and Xiao (2022) obtain linear convergence of NPG without regularization. However, all these linear convergence results are limited in the tabular setting with a direct parametrization. It remains unclear whether this same linear convergence rate can be established in function approximation settings.
concerted effort to develop convergence
In this paper we provide an affirmative answer to this question for the log-linear policy class. Our approach is based on the framework of compatible function approximation (Sutton et al., 2000; Kakade, 2001), which was extensively developed by Agarwal et al. (2021). Using this framework, variants of NPG with log-linear policies can be written policy mirror descent (PMD) methods with inexact evaluations of the advantage function or O-function (giving rise to NPG or Q-NPG respec- tively). Then by extending recent analysis of PMD (Xiao, 2022), obtain non-asymptotic linear

---

Published as a conference paper at ICLR 2023
convergence of both NPG and Q-NPG with log-linear policies. A distinctive feature of this approach the use of a simple, non-adaptive geometrically increasing step size, without resorting to entropy or other (strongly) convex regularization. The extensions are highly nontrivial and require quite different techniques. This linear convergence leads to the (1/(22 sample complexities for both methods. In particular, our sample complexity analysis also fixes errors of previous work. Lastly, as a byprod- uct, we obtain sublinear convergence rates for both methods with arbitrary constant step size. See Appendix A for a thorough review. In particular, Table provides a complete overview of our results.
2 PRELIMINARIES ON MARKOV DECISION PROCESSES
We consider an MDP denoted as MM- (S.A.P..c)) where S finite state space, AA is a finite action space, P S x A + S is Markovian transition model with P(s' a) being the transition probability from state 8 to s' under action a, e a cost function with c(s, [0, 1] for all (8, a) E S x A, and y E [0, 1) is discounted factor. Here we use cost instead of reward to better align with the minimization convention in the optimization literature.
The agent's behavior is modeled a stochastic policy π A(A)IS), where म, E ((A) is the probability distribution over actions A in state $ E S. At each time f. the agent takes an action a E A given the current state s, E S, following the policy æ, i.e., ag T..- Then the MDP transitions into the next state 81+1 with probability P(8++1 | 8t, (8,aa)) and the agent encounters the cost c = c(5t, dt). Thus, a policy induces distribution over trajectories (st: 0t, Ct (220 In the infinite-horizon discounted setting, the cost function of π with initial state is defined as
(T) Eai (81) (-P(()
7ec(s,, ax) so = s]
(1)
1=
Given an initial state distribution A(S), the goal of the agent is to find policy π that minimizes
(T) Ex-p [V.(T)) E.es PoVa(T) = (V(=).
more granular characterization of the performance of a policy is the state-action cost function (Q-function). For any pair (s, E x A, it defined as
(
def Beir Pm1
12 7'c(se, ax) 8n = 8, ag a].
(2)
Let Q+ RI-M1 denote the vector [Q.o]EEA Then we have V₂(T) = BaNT, [Qaa(T)] (T (x())) The advantage function! is a centered version of the Q-function:
=
As.a(1) del (T) VI(,,, which satisfies Eawa, [As,a (Tr) 0 for all S.
Visitation probabilities. Given a starting state distribution p E ASS), we define the state visitation distribution dn (p) E A(S), induced by policy n,
d
def (1 7) Exo E 7t Pr (s: [o)]
where (s su) is the probability that st is equal to by following the trajectory generated by и starting from sg. Intuitively, the state visitation distribution measures the probability of being at state across the entire trajectory. We define the state-action visitation distribution x (p) ASS A) as def (p)
21 E
Pr s,
so)]
(3)
In addition, we extend the definition of d (p) by specifying the initial state-action distribution 1/ i... d'a(( def E E(s0-
E.00t 7" Pr Pr = s,a, =aa Su. ag)]
(4)
The difference in the last two definitions is that for the former, the initial action ag is sampled directly
from n, whereas for the latter, it is prescribed by the initial state-action distribution P. We use d compared to d to better distinguish the cases with v and p. Without specification, we even omit the argument // or p throughout the paper to simplify the presentation as they are self-evident. From these definitions, we have for all (s, a) E S A,
2 (1 7)s,,
d 2 (1 7)..
d 2 (1 100--70 7)
An advantage function should measure how much hetter is compared to while here A is positive when is worse than æ,. We keep calling A advantage function better align with the convention in the RI. literature.
2

---

Published as a conference paper at ICLR 2023
Policy parametrization. In practice, both the state and action spaces S and A can be large and some form of function approximation is needed to reduce the dimensions and make the computation feasible. In particular, the policy is often parametrized x0)) with 0 R", where is much smaller than [S] and |A|. In this paper, we focus on the log-linear policy class. Indeed, we assume that for each state-action pair (s, a), there is feature mapping Øs.a IR and the policy takes the form
explo 8)
Ta (0) E exp(ó
(6)
This setting is important since it is the simplest instantiation of the widely-used neural policy parametrization. To simplify notations the rest, we use the shorthand V (0) for V (T)) and simi- larly Qs (0) for Qs,a (m()). As.a (0) for As.a ( de for d= dg for dz,a?) and d for dz,())
Natural Policy Gradient (NPG) Method. Using the notations defined above, the parametrized policy optimization problem is to minimize the function (0) over 0 E Rm.. The policy gradient given by (see, e.g., Williams, 1992; Sutton et al., 2000)
VoV = 1- Rendd amm (0) iQ ( (0) Vo log a. (())
(7)
For parametrizations that are differentiable and satisfy EGEA s.sa (0) 1, including the log-linear class defined in (6), can replace Q..a (0) by (0) in the above expression (Agarwal et al., 2021).
The NPG method (Kakade, 2001) takes the form
g(++1) ((k) mh F (B(k)) (O()))
(8)
where ?p is scalar step size, (0) the Fisher information matrix
()( def Egnde (0) [o log s. (0) (Vo log x..a (0)) J..
and (0)t denotes the Moore-Penrose pseudoinverse of (0).
3 NPG WITH COMPATIBLE FUNCTION APPROXIMATION
The parametrized value function (0) is non-convex in general (see, e.g., Agarwal et al., 2021). Despite being a non-convex optimization problem, there still additional structure we can leverage to ensure convergence. Following Agarwal et al. (2021), 1), we adopt the framework of compatible function approximation (Sutton et al., 2000; Kakade, 2001), which exploits the MDP structure and leads to tight convergence rate analysis.
For any w, E R.m and state-action distribution Ç, define compatible function functiioo approximation error as
LA 0, def E<ssa)<<(( (w Vo oo log (.. (0)
(10)
Kakade (2001) showed that the NPG update (8) is equivalent to (up to constant scaling of m))
((++1) (k)) M] w (k)
Wc E argmninwer LA LA(w, (()) d(()),
(11)
where (k) is a shorthand for the state-action visitation distribution d=(((())
(p) defined in (3). A
derivation of (11) provided Appendix B (Lemma 1) for completeness. In other words, wo!h) is the solution to regression problem that tries to approximate (0(k)) using V log Jz (0(k) as features. This is where the term "compatible function approximation error" comes from. For the log-linear policy class defined in (6), have
Vo log
(0) def ós.a En'es Ts (O)osn òs.a (a) [ox,r), (12)
where Hs (0) are called centered features vectors.
In practice we cannot minimize L exactly; instead, sample-based regression problem is solved to obtain an approximate solution (k), This leads to the following inexact NPG update rule:
(k++) = ((k) (k),
(k) argmin LA (w, (K0) (d())).
(13)
3

---

Published as a conference paper at ICLR 2023
The inexact NPG updates require samples of unbiased estimates of As,, the corresponding sampling procedure is given in Algorithm 4, and sample-based based regression solver to minimize LA is given in Algorithm 5 in the Appendix.
Alteratively, as proposed by Agarwal et al. (2021), we can define the compatible function approxi- mation error
Lo 0, def
B(s [ òs,a - Qa,a(()))))))) (0))
(14)
and use it to derive variant of the inexact NPG update called Q-NPG:
( 1) 0(*) m))
w(()) argmin (w ((0,00,,,, a
(15)
For Q-NPG, the sampling procedure for estimating Qa.a (0) is given in Algorithm 3 and a sample- based regression solver for (A) is proposed in Algorithm in the Appendix.
The sampling procedure and the regression solver of NPG are less efficient than those of Q-NPG.
Indeed, the sampling procedure for Ag.a( (0) in Algorithm 4 not only estimates (0), but also requires an additional estimation of V, (0), and thus doubles the amount of samples as compared to Algorithm 3. Furthermore, the stochastic gradient estimator of LQ in Algorithm only computes on a single action of the feature map Φa.a- Whereas the one of LA in Algorithm computes on the centered feature map a (0) defined in (12), which needs to go through the entire action space, thus is |A] times more expensive run. See Appendix C for more details.
Following Agarwal et al. (2021), we consider slightly different variants of NPG and Q-NPG, where ((h) in (13) and (15) is replaced by more general state-action visitation distribution d(k) = d= (=(0(t)))) (v) defined in (4) with E A(S x A). The advantage of using d is that it allows better exploration than d (A) as can be chosen to be independent to the policy T (0(()). For example, it can be seen from (5) that the lower bound of d is independent to æ, which is not the case for d=. This property is crucial in the forthcoming convergence analysis.
3.1 FORMULATION AS INEXACT POLICY MIRROR DESCENT
Given an approximate solution w(() for minimizing LQ (w, ((8), o(()) d((k)), the Q-NPG update rule ((++1) = ((h) mp (k), when plugged the log-linear parametrization (6), results a new policy (k+1) Thhh) exp (- TIk o5, (A))) /2
V V E A,
where x (8) is shorthand for Te.a (0(+) and 21 is normalization factor to ensure EGEA Ta.a 1, for each S. We note that the above (k++1) can also be obtained by a mirror descent update: (k+1) arg min Thk (0,w(k)..) P) + D(p, m!!a) PEA(A)
(k+1)
E
(16)
where d, E | is matrix with rows (T E Rx for E A, and D(p,g) q) denotes the Kullback-Leibler (KI.) divergence between two distributions p,q A(A), i.e., D(p,g)
EaEA Pa log( P.). A derivation of (16) is provided in Appendix B (Lemma 2) for completeness.
we replace & (k)) in (16) by the vector [T))( ae E R then it becomes the policy mirror descent (PMD) method in the tabular setting studied by, for example, Shani et al. (2020), Lan (2022) and Xiao (2022). In fact, the update rule (16) can be viewed as an inexact PMD method where Q, (x) is linearly approximated by Φb (k) through compatible function approximation (14). Similarly, we can write the inexact NPG update rule as
(k+1) arg min PEA(A)
(k) ()) .D) + ((Pp= Vs E S,
(17)
where (k) is an inexact solution for minimizing (w,, Q(k), (d0)) defined in (10), and ((())
R| Xm is a matrix whose rows consist of the centered feature maps (o..a T as defined in (12).
Reformulating Q-NPG and NPG into the mirror descent forms (16) and (17), respectively, allows us to adapt the analysis of PMD method developed in Xiao (2022) to obtain sharp convergence rates. In particular, show that with an increasing step size 77 2* both NPG and Q-NGG with log-ling linelinear policy parametrization converge linearly up to an error floor determined by the quality of the compatible function approximation.
4

---

Published as a conference paper at ICLR 2023
4 ANALYSIS OF Q-NPG WITH LOG-LINEAR POLICIES
In this section, we provide the convergence analysis of the following inexact Q-NPG method
g(++1) g(k)
7/ (k))
(k) argmin,, L (w, , a(
(18)
where ((k) is shorthand for d
(v) and v E A x A) is an arbitrary state-action distribution
that does not depend on p. The exact minimizer is denoted as w!!) argmin Lg (w, ((k), d (())).
Following Agarwal et al. (2021), the compatible function approximation error can be decomposed as
La (w(k), g(h) (())) = Lu( ((0))(())) _00) (w," ( g(k), .dth)) + La [u( g(k) ((K)), d ddi)).
Statistical error (excess risk)
Approximation error
The statistical error measures how accurate is our solution the regression problem, i.e., how good w((A) is compared with (²( The approximation error measures the best possible solution for approximating Qa.a (0(k) using Φ,.a as features in the regression problem (modeling error). One way to proceed with the analysis is to assume that both the statistical error and the approximation error are bounded for all iterations, which is the approach we take in Section 4.2 and is also the approach we take later in Section 5 for the analysis of the NPG method.
However, in Section 4.1, we first take an alternative approach proposed by Agarwal et al. (2021), )), where the assumption of bounded approximation error is replaced by bounded transfer error. The transfer error refers to Lo( (w. g(h), dd). where the iteration -deetdend visitation distribution d (R) is shifted to a fixed one d' (defined in Section 1.
These two approaches require different additional assumptions and result slightly different conver- gence rates. Here we first state the common assumption the bounded statistical error.
Assumption 1 (Bounded statistical error, Assumption 6.1.1 in Agarwal et al. (2021)). There exists fstat such that for all iterations k 2 0 of the Q-NPG method (18), we have
E (t) g(k) g(k))_" _ Lo (K) ( ]d0)]] < Cstat-
(w
(19)
By solving the regression problem with sampling based approaches, we can expect estat O(1/VT) (Agarwal et al., 2021) or 6stat O(1/T) (see Corollary 1) where is the number of iterations used to find the inexact solution (kk)
4.1 ANALYSIS WITH BOUNDED TRANSFER ERROR
Here we introduce some additional notations. For any state distributions E A(S), we define
the distribution mismatch coefficient of relative to q as llp/gllae def maxxes Ps/qs- Let x' be an arbitrary comparator policy, which is not necessarily an optimal policy and does not need to belong to
the log-linear policy class. Fix a state distribution E ASS). We denote d (p) as d' and (o(()))) (p)
as (k),, and define the following distribution mismatch coefficients:
0x def
1
d'
and
def
(20)
k(k)
Thus, for all & > 0, have 92 I pp- We assume that 0, < cc, which is the case, for example, if P. > for all E S. This commonly used in the literature on policy gradient methods (e.g., Zhang et al., 2020; Wang et al., 2020) and the NPG convergence analysis (e.g., Cayci et al., 2021; Xiao, 2022). We further relax this condition in Appendix H.
Given a state distribution and a comparator policy π², we define a state-action measure d' as
d del d Uniff((a) del d2/1Ab,
(21)
(k), and use it to express the transfer emorr as To (w (K)) dd).
5

---

when x(() is the softmax Published as a conference paper at ICLR 2023
Assumption (Bounded transfer error, Assumption 6.1.2 in Agarwal et al. (2021)). There exists Cbiss such that for all iterations 2 0 of the Q-NPG method (18), we have
E (w
(K) O(k) dd)]
éhias-
(22)
The Cbias is often referred to the transfer error, since it is the error due to replacing the relevant distribution d(() by d This transfer error bound characterizes how well the Q-values can be linearly approximated by the feature maps a It can be shown that ébias tabular policy (Agarwal et al., 2021) or the MDP has certain low-rank structure (Jiang et al., 2017; Yang & Wang, 2019; Jin et al., 2020). For rich neural parametrizations, Cbias be made small (Wang et al., 2020).
The next assumption concerns the relative condition number between two covariance matrices of 6s,0 defined under different state-action distributions.
Assumption (Bounded relative condition number, Assumption 6.2 in Agarwal al. (2021)). Fix state distribution a state-action distribution and comparator policy x Let
Σj- def (s (0a00
and
Ev
def
E(,,)) [da
(23)
where d" is specified in (21). We define the relative condition number between Eg- and E,
W T -
def
Ky
max WER
(24)
W Σyw"
and assume that By is finite.
The Ky is referred the relative condition number, since the ratio is between two different matrix induced norm. Assumption 3 benefits from the use of v. In fact, is shown Agarwal et al. (2021, Remark 22 and Lemma 23) that Ky be reasonably small (e.g., Ky m is always possible) and independent to the size of the state space by controlling v.
Our analysis also needs the following assumption, which does not appear in Agarwal et al. (2021).
Assumption (Concentrability coefficient for state visitation). There exists a finite Cp >> 0 such that for all iterations ls 2 0 of the Q-NPG method (18), holds that
(A)
27
E Exwud
dx
I CCP
(25)
d;
The concentrability coefficient is studied in the analysis of approximate dynamic programming algorithms (Munos, 2003; 2005; Munos & Szepesvári, 2008). It measures how much p can get amplified in k steps as compared to the reference distribution d". Let Pmin = min,es Pe. A sufficient condition for Assumption 4 to hold that Punin Indeed,
(k) (
(
1
d
Bowd
(26)
d"
d'
P
(1-7)) PPmin
In reality, Cpp can be much smaller than the pessimistic bound shown above. This is especially the case if we choose x² to be the optimal policy and (d4) + d' We further replace Cp by C, defined Section 4.2 that is independent to p and thus more easily satisfied.
Now we present our first main result.
Theorem 1. Fix state distribution p. an state-action distribution and a comparator policy T". We consider the Q-NPG method (18) with the uniform initial policy and the step sizes satisfying Noo 2 1-7 log A and Ma+1 2 1 Suppose that Assumptions 1, 2, 3 and 4 all hold. Then we have for all k O,
E [V Vx(TT) (1-
2/ Al(dev/(+t)) (Viz Cotat + v Cbias
1-7
For simplicity, present all our results with the uniform initial policy in the main paper. See Theorem 5, and 8 in the Appendix for more general results with any initial policy.

---

Published as a conference paper at ICLR 2023
The main differences between our Theorem 1 and Theorem 20 of Agarwal et al. (2021), which is their corresponding result on the inexact Q-NPG method, are summarized as follows.
The convergence rate of Agarwal et al. (2021, Theorem 20) is O(1/Vk) up to an error floor determined by Estat and biass We have linear convergence up to an error floor that also depends on Estat and Obias. However, the magnitude of our error floor is worse (larger) by factor of I, /Cp due the concentrability and the distribution mismatch coefficients used in our proof. A very pessimistic bound on this factor is large as [S|2/(1-7))
In terms of required conditions, both results use Assumptions 1, 2 and Agarwal al. (2021, Theorem 20) further assume that the norms of the feature maps Φs.a are uniformly bounded and (*() has bounded norm (e.g.. obtained by a projected stochastic gradient descent). Due to different analysis techniques referred next, we avoid such boundedness assumptions but rely on the concentrability coefficient C, defined in Assumption 4.
Agarwal et al. (2021, Theorem 20) uses diminishing step size 1/vl where k is the total number of iterations, but we use a geometrically increasing step size TJs x 7h for all & 2 O. This discrepancy reflects the different analysis techniques adopted. The key analysis tool in Agarwal ct al. (2021) is a NPG Regret Lemma (their Lemma 34) which relies on the smoothness of the functions log (0) (thus the boundedness of (!
and the boundedness of [|)] and thus the classical (1/vk) diminishing step size in the optimization literature. Our analysis exploits the thiet-point descent lemma (Chen & Teboulle, 1993) and the performance difference lemma (Kakade & Langford, 2002), without reliance on smoothness parameters. As consequence, we can take advantage of exponentially growing step sizes and avoid assuming the boundedness of || || or ||
The reason of using increasing step size can be interpreted approximate policy iteration. See Appendix H the connection with policy iteration for more details.
As by product, we also obtain sublinear (1/k) convergence result while using arbitrary constant step size.
Theorem 2. Fix state distribution p. state-action distribution v and optimal policy n*.
We consider the Q-NPG method (18) with the uniform initial policy and any constant step size T = O. Suppose that Assumptions 1, 2, and 4 all hold. Then we have for all k 0.
log Al + 20,) + (MAA (v (1-7)6
Vo(TT) S
Ry E-EEstar v VEbias).
4.2 ANALYSIS WITH BOUNDED APPROXIMATION ERROR
In this section, instead of assuming bounded transfer error, we provide a convergence analysis based on the usual notion of approximation error and weaker concentrability coefficient. Assumption (Bounded approximation error). There exists Capprox > such that for all iterations
k 2 0 of the Q-NPG method (18), it holds that
E [o (wi (k) g(k) , ]001]]
Capprox-
(27)
As mentioned in Agarwal al. (2021), Assumption is stronger than Assumption 2 (bounded transfer error). Indeed,
(w( 000) d²) d (k)
ā= v La(w! (k) 0(()) _(0)..
(k) g(h) a Lo(w!
Assumption 6 (Concentrability coefficient for state-action visitation). There exists C, < oo such that for all iterations of the Q-NPG method (18), we have
(k)
27
hara
E (( (k)
C.
(28)
76)
where had represents all of the following quantities: glk+1) nI (k+1)
((*+1),,(0
T
d
and T
(29)
7

---

Published as a conference paper at ICLR 2023
Since are free to choose independently to p. can choose Ve.a > 0 for all (s. a) E S x for Assumption to hold. Indeed, with Vmin denoting (i.(x.)) V2,as we have
As.a
1
max (a.A)E5XA
(30)
(1-i)mmi
where the upper bound can be smaller than that in (26) if Pmin is smaller than Vmin-
Theorem 3. Fix a state distribution p. an state-action distribution u and a comparator policy n², We
consider Q-NPG method (18) with uniform initial policy and step sizes satisfying тι 2 1-1 log (A]
7
and 16+11 2 1 7 M/-- Suppose that Assumptions 1, 5 and hold. Then we have for all k 2 0,
(IV,(T((0) (1))) -V,(T - (1 (1- ) R
2VC,(0==1)
(V'sstat + /Eapprox)
Compared to Theorem 1, while the approximation error assumption is stronger than the transfer error assumption, we do not require the assumption on relative condition number R2 and the error floor does not depends on Ki nor explicitly on |A]. Besides, can always choose v so that C. is finite even if Cp is unbounded. However, it is not clear if Theorem 3 is better than Theorem 1.
Remark 1. Note that Theorems 1, 2 and 3 benefit from using the visitation distribution (k) instead of d (i.e., benefit from using v instead of p). In particular, from (5), d(t) has a lower bound that independent to the policy T (K) or p. This property allows us to define weak notion of relative condition number (Assumption 3) that is independent to the iterates, and also allows us to get a finite upper bound of C, (Assumption and (30)) that is independent to p.
4.3 SAMPLE COMPLEXITY OF Q-NPG
Here we establish the sample complexity results, i.c., total number of samples of single-step in- teraction with the environment, of a sample-based Q-NPG method (Algorithm 2 in Appendix C). Combined with simple SGD solver, Q-NPG-SGD in Algorithm 6, the following corollary shows that Algorithm converges globally by further assuming that the feature map is bounded and has non-singular covariance matrix (31). The explicit constants of the bound can be found in the appendix.
Corollary 1. Consider the setting of Theorem 3. Suppose that the sample-based Q-NPG Algorithm 2 is run for K iterations, with T gradient steps of Q-NPG- SGD (Algorithm 6) per iteration. Further- more, suppose that for all (s,a) E S A, we have || S B with >> O, and we choose the step size a 2Bt and the initialization Wn 0 0.for 2-NPG SGD. for all 0 E R the covariance matrix of the feature map followed by the initial state-action distribution satisfies
En 2 plm:
(31)
where Im E mm is the identity matrix and p > 0, then
BIV, [K)] - (T(TT) S J.
2 T- 0 /Eapprox//////ee (1 7)) + (0
In Q-NPG-SGD, each trajectory has the expected length 1/(1 - 7) (see Lemma 4). Consequently,
with K = (logg(1//4000 (og(1/(1 1 7))) and T = O ( Q-NPG requires K * T - 7)
Ó ( samples such that E [V, (+())] -V,
(approo I-7 ). The Ō(L/E²) sample
complexity matches with the one of value-based algorithms such as Q-learning (Li et al., 2020).
Compared to Agarwal et al. (2021, Corollary 26) for the sampled based Q-NPG Algorithm 2, their sample complexity is O (1->))12)) with K [1-7)== and T [1->}æс>- Despite the improvement
on the convergence rate for K, they use the optimization results of Shalev-Shwartz & Ben-David
(2014, Theorem 14.8) to obtain éstat = ((11 while we use the one of Bach & Moulines (2013, Theorem 1) (see Theorem 12 as well) to establish faster stat (11/T). Besides, they use the projected SGD method and require that the stochastic gradient is bounded which is incorrectly verified in their proof 3 In contrast, to apply Theorem 12, the boundedness of the stochastic gradient is not necessary. Alternatively, we require a different condition (31). A proof sketch of our corollary and a discussion of the condition (31) are provided in Appendix D.5 for more details.
Indeed, the stochastic gradient of TiQ is unbounded, since the estimate Q.. (9) of Q..a (0) is unbounded. This is because each single sampled trajectory has unhounded length. See Appendix D.5 for more explanations.
8

---

Published as a conference paper at ICLR 2023
5 ANALYSIS OF NPG WITH LOG-LINEAR POLICIES
We now return to the convergence analysis of the inexact NPG method, specifically,
(b++1) ((6) Mh wh
(() argmin LA (w, 0(4), a d(()).
(32)
Again, let wt E -argmin,,. LA w. ((x), d(()) denote the minimizer. Our analysis of NPG is anal- ogous to that of Q-NPG shown in the previous section. That is, we again exploit the inexact PMD formulation (17) and use techniques developed in Xiao (2022). The set of assumptions we use for NPG is analogous to the assumptions used in Section 4.2. In particular, we assume bounded approximation eπror instead of transfer error (c.f., Assumption 2) in minimizing LA and do not need the assumption on relative condition number.
Assumption 7 (Bounded statistical eπror, Assumption 6.5.1 in Agarwal et al. (2021)). There exists such that for all iterations k 2 0 of the NPG method (32), we have
Estat.
E[LA
E LA (w((k) , LA [u( g(k) a d()))] S Cstat-
(33)
Assumption (Bounded approximation error). There exists Eapprox > 0 such that for all iterations k 2 0 of the NPG method (32), we have
BLLA (wi (k) (00) d(0)]] I Capprox
(34)
Assumption 9 (Concentrability coefficient for state-action visitation). There exists Cv < 00 such that for all iterations k 2 0 of the NPG method (32), we have
deja (d(ttt
)
d
E (ssaa)dd (A))
S SCv and
B (((aa)ad (8)
S C..
(35)
7(k)
Under the above assumptions, we have the following result.
Theorem 4. Fix state distribution p. a stale-action distribution v, and comparator policy n², We consider the NPG method (32) with uniform initial policy and step sizes satisfying тoo 2 1-7 log AA]
and 1|++1 2 Ml-- Suppose that Assumptions 7, 8 and hold. Then we have for all k 2 0,
(T (2) VO(TT) S (1 0, 1-7 +
2
(0p++)
(VEstat
v /approx)
1-7
Now we compare Theorem 4 with Theorem 29 in Agarwal et al. (2021) for the NPG analysis. The main differences are similar to those for Q-NPG as summarized right after Theorem I: Their convergence rate is sublinear while ours is linear; they assume uniformly bounded &..a and (k) while we require bounded concentrability coefficient C, due to different proof techniques; they use diminishing step sizes and we use geometrically increasing ones. Moreover, Theorem 4 requires bounded approximation error, which is stronger assumption than the bounded transfer error used by their Theorem 29, but we do not need the assumption on bounded relative condition number. In particular, such bounded relative condition number must hold for the covariance matrix of Φ (B(()) for all & 2 0 which depends on the iterates g(k), This is in contrast to our Assumption 3, where we use single fixed covariance matrix for Q-NPG that is independent to the iterates, as defined in (23).
In addition, the inequalities (35) only involve half of the state-action visitation distributions listed in (29), i.e., the first and the fourth terms. Thus, C in (35) can share the same upper bound in (30) independent to the use of the algorithm Q-NPG or NPG. Consequently, our concentrability coefficient C, in (35) is weaker than Assumption 2 in Cayci et al. (2021) which studies the linear convergence of NPG with entropy regularization for the log-linear policy class. The reason is that the bound on
C, in (30) does not depend on the policies throughout the iterations thanks to the use of di (A) instead of d (R) (see Remark as well). See Appendix H for a thorough discussion on the concentrability coefficient C..
As a by product, we also obtain a sublinear rate for NPG while using an unconstrained constant step size in Theorem 9 in Appendix F. By further assuming that the feature map is bounded and the Fisher information matrix (9) is singsing,,a,, as for Q-NPG and fix the errors occurred in the NPG sample complexity proofs of Agarwal et al. (2021) and Liu et al. (2020) in Appendix G.
also provide Ó(1/e?) sample complexity result of NPG

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
We gratefully acknowledge Daniel Russo who pointed out that we did cite properly Bhandari Russo (2021) in the literature review in the previous version.
We acknowledge the helpful discussion with Yanli Liu on the sample complexity analysis of both Q-NPG and NPG.
We would also like to thank the anonymous reviewers for their helpful comments.
REFERENCES
Alekh Agarwal, Sham M. Kakade, Jason D. Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-76, 2021. (Cited on pages 1, 3, 4, 5, 6, 8. 16, 17, 18, 19, 21, 23, 26, 34, 36, 43, 44, 45, 46, and 48.)
Carlo Alfano and Patrick Rebeschini. Linear convergence for natural policy gradient with log-linear policy parametrization, 2022. (Cited on pages 17, 18, and 19.)
Francis Bach and Eric Moulines. Non-strongly-coowe
smooth stochastic approximation with convergence rate of olIn)). Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013. (Cited on pages 8, 25, 36, 37, 48, and 50.)
Baxter and P. L. Bartlett. aninite-horizon policy-gradient estimation. Journal of Artificial Intel- ligence Research, 15:319-350, Nov 2001. ISSN 1076-9757. doi: 10.1613/jain. (Cited page 1.)
A Beck and M Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 3773);167-175, 2003. (Cited on page 1.)
Amir Beck. First-Order Methods in Optimization. SIAM-Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2017. ISBN 161 1974984. (Cited on pages 48 and 49.)
D. Bertsekas. Dynamic Programming and Optimal Control: Volume II; Approximate Dynamic Programming. Athena Scientific optimization and computation series. Athena Scientifie, 2012. (Cited on page 48.)
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods, 2019. (Cited on page 18.)
Jalaj Bhandari and Daniel Russo. On the linear convergence of policy gradient methods for finite mdps. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 2386 -2944, PMLR, 13-15 Apr 2021. (Cited on pages 10, 17, and 18.)
Shalabh Bhatnagar, Richard Sutton, Mohammad Ghavamzadeh, and Mark Lee. Natural actor-critic algorithms. Automatica, 45(1 1):24))-22222 1-442, 2009. ISSN 0005-1098. (Cited on page 45.)
L.M. Bregman. The relaxation method finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Computational Mathematics and Mathematical Physics, 7(3):200-217, 1967. ISSN 0041-5553. (Cited on page 49.)
R. H. Byrd, S. L. Hansen, Jorge Nocedal, and Y. Singer. A stochastic quasi-newton method for large-scale optimization. SIAM Journal on Optimization, 26(2): 2016. doi: 10.1 140954362. (Cited page 45.)
Semih Cayci, Niao He, and R. Srikant. Linear convergence of entropy-regularizee natural policy gradient with linear function approximation, 2021. (Cited pages 5, 9, 17, 18, 19, 47, and 48.)
Semih Cayci, Niao He, and R. Srikant. Finite-time analysis of entropy-regullrizze neural natural actor-critic algorithm, 2022. (Cited pages 17 and 18.)
10

---

Published as a conference paper at ICLR 2023
Shicong Cen, Chen Cheng. Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. In Operations Research, 2021. (Cited pages and 16.)
Y. Censor and S.A. Zenios. Parallel Optimization: Theory, Algorithms, and Applications. Oxford University Press, USA, 1997. (Cited on page 49.)
Gong Chen and Mare Teboulle. Convergence analysis of a proximal-like minimization algorithm using bregman functions. SIAM Journal on Optimization, 3(3):538-545, 1993. (Cited on pages and 49.)
Zaiwei Chen and Siva Theja Maguluri. Sample complexity of policy-based methods under off-policy sampling and linear function approximation. Proceedings The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 11195-11214, PMLR, 28-30 Mar 2022. (Cited on pages 17, 18, 19, 47, and 48.)
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, 6:2611- 2616, 2022. (Cited on pages 17 and 18.)
Yuhao Ding, Junzi Zhang, and Javad Lavaei. On the global optimum convergence of momentum- policy gradient. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 1910-1934, PMLR, 28-30 Mar 2022. (Cited on page 45.)
Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep rein- forcement learning for continuous control. In Proceedings of the 33rd International Conference on International Conference on Machine Learning Volume 48, ICML; pp. 1329-1338. JMLR.org. 2016. (Cited page 45.)
Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. In Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1467-1476. PMLR, 10-15 Jul 2018. (Cited on page 18.)
Robert Gower, Donald Goldfarb, and Peter Richtarik. Stochastic block BFGS:
Squeezing more curvature out of data. In Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 1869-1878, New York, New York, USA, 20-22 Jun 2016. PMLR. (Cited on page 45.)
Jakub Grudzien, Christian A Schroeder De Witt, and Jakob Foerster. Mirror learning: A unifying framework of policy optimisation. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 7825-7844. PMLR, 17-23 Jul 2022. (Cited on page 1.)
Daniel Hsu, Sham M. Kakade, and Tong Zhang. Random design analysis of ridge regression. In Shie Mannor, Nathan Srebro, and Robert C. Williamson (eds.), Proceedings of the 25th Annual Conference on Learning Theory, volume 23 of Proceedings of Machine Learning Research, pp. 9.1-9.24, Edinburgh, Scotland, 25-27 Jun 2012. PMLR. (Cited on page 36.)
Yuzheng Hu, Ziwei Ji, and Matus Telgarsky. Actor-critic is implicitly biased towards high entropy optimal policies. In Intermational Conference on Learning Representations, 2022. (Cited on pages 17 and 18.)
Feihu Huang, Shangqian Gao. Jian Pei, and Heng Huang. Momentum bonset based policy gradient meth- ods. Proceedings of the 37th International Conference on Machine Learning, volume 1 119 of Proceedings of Machine Learning Research, pp. 4422-442244442 4433. PMLR, 13-18 Jul 2020. (Cited on page 45.)
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. Con- textual decision processes with low Bellman rank are PAC-learaabl. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1704-1713, PMLR, 06-11 Aug 2017. (Cited page 6.)
11

---

Published as a conference paper at ICLR 2023
Chi Jin, Zhuoran Yang, Zhaoran Wang. and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp- 2137-2143. PMIR, 09-12 Jul 2020. (Cited on pages 6 and 17.)
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning, In Proceedings of 19th International Conference on Machine Learning, pp. 267-277274, 2002. (Cited on pages 7, 19, and 21.)
Sham M Kakade. A natural policy gradient. In Advances in Neural Information Processing Systems, volume 14. MIT Press, 2001. (Cited on pages 1, 3, 20, and 45.)
Sajad Khodadadian, Zaiwei Chen, and Siva Theja Maguluri. Finite-sample analysis of off-policy natural actor-critic algorithm. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 5420-5431, PMLR, 18 24 Jul 2021a. (Cited on page 16.)
Sajad Khodadadian, Prakirt Raj Jhunjhunwala, Sushil Mahavir Varma, and Siva Theja Maguluri. On the linear convergence of natural policy gradient algorithm. In 2021 60th IEEE Conference Decision and Control (CDC), pp. 3794-3799. IEEE Press, 2021b. (Cited on pages and 17.)
Sajad Khodadadian, Thinh T. Doan, Justin Romberg, and Siva Theja Maguluri. Finite sample analysis of two-time-scale natural actor-critic algorithm. IEEE Transactions on Automatic Control, pp. 1-16, 2022a. (Cited page 16.)
Sajad Khodadadian, Prakirt Raj Jhunjhunwala, Sushil Mahavir Varma, and Siva Theja Maguluri. On linear and super-linear convergence of natural policy gradient algorithm. Systems Control Letters, 10511, 2022b. ISSN 0167-6911. (Cited on page 17.)
Guanghui Lan. Policy mirror descent for reinforcement learning: linear convergence, new sampling complexity, and generalized problem classes. Mathematical Programming, Apr 2022. ISSN 1436-4646. (Cited on pages 1, 1, 16, 17, 19, 47, and 48.)
Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Sample complexity of asynchronous q-learning: Sharper analysis and variance reduction. In Advances in Neural Information Processing Systems, volume 33, pp. 7031-7043, 2020. (Cited on page 8.)
Tianjiao Li, Feiyang Wu, and Guanghui Lan. Stochastic first-order methods for average-reward markov decision processes, 2022a. (Cited on pages 16 and 19.)
Yan Li, Tuo Zhao, and Guanghui Lan. Homotopic policy mirror descent: Policy convergence, implicit regularization, and improved sample complexity, 2022b. (Cited on page 17.)
Timothy Lillicrap. Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. 6. (Cited page 1.)
Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (variance-reducee policy gradient and natural policy gradient methods. In Advances in Neural Information Processing Systems, volume 33, pp. 7624-7636. Curran Associates, Inc., 2020. (Cited on pages 9, 16, 17, 18, 43, and 45.)
Stanislaw Lojasiewicz. Une propriété topologique des sous-ensembles analytiques réels. Equ. Derivees partielles, Paris 1962, Colloques internat. Centre nat. Rech. sci. 117, 87-89 (1963)., 1963. (Cited on page 18.)
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In Proceedings of the 37th International Conference Machine Learning, volume 1 119 of Proceedings of Machine Learning Research, pp. 6820-6829, PMLR, 13-18 Jul 2020. (Cited page 18.)
12

---

Published as a conference paper at ICLR 2023
Jincheng Mei, Yue Gao, Bo Dai, Csaba Szepesvari, and Dale Schuurmans. Leveraging non-uniformity in first-order non-convex optimization. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 7555-7564. PMLR, 18-24 Jul 2021. (Cited on page 18.)
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 Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 1938-193,,00 New York, New York, USA. 20-22 Jun 2016. PMLR. (Cited on page 1.)
Rémi Munos. Error bounds for approximate policy iteration. In Proceedings of the Twentieth Inter- national Conference on International Conference on Machine Learning, ICML'03, pp. 560-567.
AAAI Press, 2003. ISBN 157735 18 1894. (Cited on page 6.)
Rémi Munos. Error bounds for approximate value iteration. In Proceedings of the 20th National Conference on Artificial Intelligence Volume 2, AAAT0S,, pp. 1006-1011, AAAI Press, 2005. ISBN 157735236x. (Cited page 6.)
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(27):815-855 857, 2008. (Cited on page 6.)
A Nemirovski and D Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley Interscience, 1983. (Cited page 1.)
Gergely Neu, Anders Jonsson, and Vicenç Gómez. A unified view of entropy-reeuularized markov decision processes, 2017. (Cited on page 1.)
Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. Stochas- tic serrance-reduceed policy gradient. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pp.
PMLR, 2018. (Cited on page 45.)
Jan Peters and Stefan Schaal, Natural actor-critic. Neurocomputing, 71(7-9): 11111100-111 1190, mar 2008. ISSN 0925-2312. (Cited on page 45.)
B.T. Polyak. Gradient methods for the minimisation of functionals. USSR Computational Mathematics and Mathematical Physics, 3(4):864-878, 1963. ISSN 0041-5553, (Cited on page 18.)
Martin L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons, Inc., USA, 1994. ISBN 0471619779. (Cited on pages and 48.)
R. Tyrrell Rockafellar. Convex analysis. Princeton Mathematical Series. Princeton University Press, Princeton, N. J., 1970. (Cited on page 49.)
Bruno Scherrer. Approximate policy iteration schemes: A comparison. In Proceedings of the 31st International Conference on International Conference on Machine Learning Volume 32, ICML' 14, pp. 11-1314-11-1322. JMLR.org, 2014. (Cited on page 48.)
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 1889-1897, Lille, France, 07-09 Jul 2015. PMLR. (Cited on page 1.)
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms, 2017. (Cited on page 1.)
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning From Theory to Algorithms. Cambridge University Press, 2014. ISBN 978-1-10-705713-5 (Cited on pages 8
and 36.)
Lior Shani, Yonathan Efroni, and Shie Mannor. Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps. In The Thirty-Fourth AAAI Conference Artificial Intelligence, AAAI 2020, New York, NY, USA, February 7-12, 2020, pp. 5668-5675, 2020. (Cited on pages 1, 4, and 16.)
13

---

Published as a conference paper at ICLR 2023
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018. (Cited on page 1.)
Richard S Sutton, David A. McAllester, Satinder P. Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems 12, pp. 1057-1063. MIT Press, 2000. (Cited on pages 1, 3, and 20.)
Matus Telgarsky. Stochastic linear optimization never overfits with quadratically-boundedr losses on general data. In Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 5488. PMLR, 02-05 Jul 2022. (Cited on page 19.)
Sharan Vaswani, Olivier Bachem, Simone Totaro, Robert Müller, Shivam Garg, Matthieu Geist, Marlos C. Machado, Pablo Samuel Castro, and Nicolas Le Roux. A general class of surrogate functions for stable and efficient reinforcement learning. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 8619-8649. PMLR, 28 30 Mar 2022. (Cited on page 1.)
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence, In International Conference on Learning Representations, 2020. (Cited pages 5, 6, 17, and 18.)
Xiao Wang, Shiqian Ma, Donald Goldfarb, and Wei Liu. Stochastic quasi-newton methods for nonconvex stochastic optimization. SIAM Journal on Optimization, 27(2):927-956, 2017. doi: 10.1137/15M10531111 (Cited on page 45.)
R. Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning. 8:229-255 2222,,56,,1 1992. (Cited on pages and 3.)
Lin Xiao. On the convergence rates of policy gradient methods. Journal of Machine Learning Research, 23(282):1-36, 2022. (Cited on pages 1, 5, 9, 15, 16, 17, 19, 27, 47, 48, 49, and 50.)
Tengyu Xu, Zhe Wang, and Yingbin Liang. Improving sample complexity bounds for (natural) actor-critic algorithms. In Advances in Neural Information Processing Systems, volume 33, pp. 4358-4369. Curran Associates, Inc., 2020. (Cited on pages 17 and 18.)
Lin Yang and Mengdi Wang. Sample-Optimal Parametric Q- Q-Lemning Using Linearly Additive Features. In Proceedings of the 36th International Conference on Machine Learning, pp. 6995- 7004. PMLR, 2019. (Cited on page 6.)
Rui Yuan, Robert M. Gower, and Alessandro Lazaric. A general sample complexity analysis of vanilla policy gradient. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 3332-3380 PMLR, 28-30 Mar 2022. (Cited on pages 18 and 45.)
Andrea Zanette, Ching-An Cheng, and Alekh Agarwal. Cautiously optimistic policy optimization and exploration with linear function approximation. In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pp. 45255. PMLR, 15-19 Aug 2021. (Cited on pages 17 and 18.)
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, 2021. (Cited on pages 1 and 16.)
Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang. Variational policy gradient method for reinforcement learning with general utilities. In Advances in Neural Information Processing Systems, volume 33, pp. 4572-4583. Curran Associates, Inc., 2020. (Cited on pages and 18.)
Junyu Zhang, Chengzhuo Ni, Zheng Yu, Csaba Szepesvari, and Mengdi Wang. On the conver- gence and sample efficiency of variance-reduced policy gradient method. In Advances in Neural Information Processing Systems, 2021. (Cited on page 18.)
14

---

Published as a conference paper at ICLR 2023
Appendix
Table of Contents
A Related Work
15
Standard Reinforcement Learning Results
C Algorithms
21
D Proof of Section 4
27
E Proof of Section
39
F Sublinear Convergence of NPG with Constant step size
43
Sample Complexity of NPG
Discussion on the Distribution Mismatch Coefficients, the Concentrability Coeffi- cients and the Increasing Step Size
46
Standard Optimization Results
48
Here we provide the related work discussion, the missing proofs from the main paper and some additional noteworthy observations made in the main paper.
A RELATED WORK
We provide an extended discussion for the context of our work, including a discussion comparing the technical novelty of the paper the analysis of NPG with softmax tabular policies in Xiao (2022) and a comparison of the convergence theories of NPG in the literature. Furthermore, we discuss future work, such as extending our analysis other RL settings.
A.1 TECHNICAL CONTRIBUTION AND NOVELTY COMPARED TO XIAO (2022)
Our technical novelty compared to Xiao (2022) is summarized as follows.
Our linear convergence results (i.c., Theorem 1, and 4) are not direct applications of Theorem 10 in Xiao (2022). Indeed, Xiao (2022) establishes the connection between NPG and specific form of policy mirror descent (PMD) with the use of the weighted Bregman divergence for the tabular setting, while we show that this connection can also be established for the function approximation setting via the compatible function approximation framework (10). We also modify the PMD framework of Xiao (2022) with the linear approximation of the advantage function in (17), inspired from the compatible function approximation framework. Thus, the approaches of deriving the PMD form update are different. Without this work using the compatible function approximation framework to bridge NPG and PMD, it was not clear at all that the analysis of Xiao (2022) could be extended in the log-linear policy setting. So our work the first step showing that the proof techniques used in Xiao (2022) can be extended in function approximation regime. In fact, the extension is highly nontrivial and requires significant innovation (see details below). As for future work,
extend our work to other function approximation setting through similar compatible function approximation framework. See Appendix A.3 for more details about the future work.
15

---

Published as a conference paper at ICLR 2023
Besides, our linear convergence results only consider the inexact NPG update. Compared to Theorem 14 in Xiao (2022), which is their corresponding result on the inexact PMD method, we improve their analysis by making much weaker assumptions the accuracy of the estimation Q(T). Xiao (2022) requires an Too supremum norm bound on the estimation error of Q. i.e. (=) Q( S Estat, whereas our convergence guarantee depends on the expected L2 error of the estimate, i.e., Assumption and 7. For instance, Assumption
from equation (62) can be written EE (0 (k) - w. ". y Estat, which can be
interpreted as E (Ô(T) ( S Estat under the linear approximation setting. The techniques for handling I.e and T-2 errors are very different. Not only our assumption is weaker, also benefits from the sample complexity analysis that we explain next.
Consequently, when considering the sample complexity results we derived for sample-base (Q)-NPG in Corollary and 3, the difference between our work and Theorem 16 in Xiao (2022), which corresponds to their sample complexity results, is even more significant. Corollary with Algorithm Q-NPG- SGGG (Algorithm 6) satisfies Assumption 1 with number of samples that depends only on the feature dimension m of Φ and does not depend on the cardinality of state space |S| or action space |A]. In contrast, the assumption
I S Cstat with the Loe norm in Xiao (2022, Theorem 16) causes the sample complexity to depend on |S||A]]
Furthermore, Xiao (2022) uses a Monte-Carlo approach with multiple independent rollouts per iteration, while our sample-based (Q)-NPG uses one single rollout (Algorithm 3 and 4) combined with regression solvers; Xiao (2022) derives high probability sample complexity result, while we derive the convergence of the optimality gap E [V,(=(())
V2(TT) which can guarantee that the variance of V, (x((k) converges to zero. Thus, our sample-based algorithms had not been considered in Xiao (2022) and our proofs of Corollary 1 and require a different approach.
In particular, our sample complexity analysis regarding to the policy evaluation is novel. Although our sample-based algorithms had been considered previously in Agarwal et al. (2021) and Liu et al. (2020), none of their analysis on the sample complexity was correct. Indeed, Agarwal et al. (2021) required the boundedness of the stochastic gradient estimator, which might not hold as we extensively discussed in Appendix D.5. We fixed this by showing that [Q.a (0)) is bounded. See Appendix D.5 for all the subtleties, including a proof sketch of Corollary 1. Liu et al. (2020) also incorrectly used an inequality where the random variables are correlated. See the detailed explanation (Footnote 7) in Appendix G.I. We fixed this error with a careful conditional expectation argument. Please refer to Appendix G.1 for all the details, including proof sketch of Corollary 3. These dimensions are where an important part of the technical work was done. Therefore, outside of the tabular setting, and considering NPG methods that make use of regression solver, our complexity analysis is currently the only analysis that is entirely correct that we are aware of.
Finally we not only extend the work of Xiao (2022) to NPG for log-linear policy, but also consider the Q-NPG method and establish its linear convergence analysis. This is method that is unique to log-linear policy and again had not been considered in Xiao (2022).
A.2 FINITE-TIME ANALYSIS OF THE NATURAL POLICY GRADIENT
NPG for the softmax tabular policies. For the softmax tabular policies, Shani et al. (2020) show that the unregularized NPG has a O(1/Vk) convergence rate and the regularized NPG has a faster O(1/k) (k) convergence rate by using decaying step size. Agarwal et al. (2021) improve the convergence rate of the unregularized NPG to O(1) (1)) with constant step sizes. Further, Khodadadian et al. (2021a) also achieves (1/k)) convergence rate for the off off-policy natural actor-critic (NAC), and slower sublinear result is established by Khodadadian et al. (2022a) for the two-time-scale NAC.
By using the entropy regularization, Cen et al. (2021) achieve linear convergence rate for NPG. A similar linear convergence result has been obtained by rewriting the NPG update under the PMD framework with the Kullback-Leible (KL) divergence (Lan, 2022) with more general convex regularizer (Zhan et al., 2021). Such approach is also applied in the averaged MDP setting to achieve linear convergence for NPG (Li al., 2022a). However, adding regularization might induce bias
16

---

Published as a conference paper at ICLR 2023
for the solution. Thus, Lan (2022) considers exponentially diminishing regularization to guarantee unbiased solution. Furthermore, by considering both the KL divergence and the diminishing entropy regularization, Li et al. (2022b) establish the linear convergence rate not only for the optimality gap but also for the policy. That is, the policy will converge to the fixed high entropy optimal policy. Consequently, Li et al. (2022b) show a local super-linear convergence of both the policy and optimality gap, as discussed in Xiao (2022, Section 4.3).
Recently, Bhandari & Russo (2021), Khodadadian al. (2021b; 2022b) and Xiao (2022) show that regularization is unnecessary for obtaining linear convergence, and it suffices to use appropriate step sizes for NPG. In particular, Bhandari Russo (2021) propose to use an exact line search for the step size (Theorem 1 (a)) or to choose an adaptive step size (Theorem 1 (c)). Similar adaptive step size is proposed by Khodadadian et al. (2021b; 2022b). Notice that such adaptive step size requires complete knowledge about the environmental model. Instead, sufficiently large step size might be enough. In this paper, we extend the results of Xiao (2022) from the tabular setting to the log-linear policies, using non-adaptive geometrically increasing step size and obtaining linear convergence rate for NPG without regularization.
NPG with function approximation. In the function approximation regime, there have been many works investigating the convergence rate of the NPG or NAC algorithms from different perspec- tives. Wang al. (2020) establish the O convergence rate for two-layer neural NAC with projection step. The sublinear convergence results are also established by Zanette et al. (2021) and Hu et al. (2022) for the linear MDP (Jin et al., 2020). Agarwal et al. (2021) obtain the same O(1/VK) convergence rate for both projected NPG with smooth policies and projected Q-NPG with log- log-linear policies. This was later improved to (1/kk) by Liu et al. (2020) by replacing the projection step with a strong regularity condition on the Fisher information matrix, and was also improved to (1/k)) by Xu et al. (2020) with NAC under Markovian sampling. The same (1/kk) convergence rate is established for log-linear policies by Chen et al. (2022) when considering the off-policy NAC.
With entropy regularization and a projection step, Cayci et al. (2021) obtain a linear convergence for log- ligliiner policies. Same entropy regularization and a projection step are applied by Cayci et al. (2022) for the neural NAC to improve the ((I/V)) convergence rate of Wang et al. (2020) to ((1kk). In contrast, we show that by using a simple geometrically increasing step size, fast linear convergence can be achieved for log- lonearn policies without any additional regularization nor a projection step. We notice that Chen & Theja Maguluri (2022, Theorem 3.4)* also uses increasing step size and achieves linear convergence for log-linear policies without regularization. The main differences between our result and Theorem 3.4 in Chen & Theja Maguluri (2022) are fourfold. First, they rely on the contraction property of the generalized Bellman operator, while we consider the PMD analysis approach. So the proof techniques are completely different. Second, their parameter update results in the off-policy multi-step temporal difference learning, whereas we require to solve a linear regression problem to minimize the function approximation error. Third, their step size still depends on the iterates which is thus an adaptive step size and is proportional to the total number of iterations K, while ours is independent to the iterates nor to K. Finally, their assumption on the
modeling error requires an Loo supremum norm, i.e., (o(k)) <p (k) 1lo0 S Ebias for all states s of the state space, our convergence guarantee depends on the expected error (e.g., Assumption 2, or 8) which is much weaker assumption. After our submission. we are aware of the concurrent work of Alfano & Rebeschini (2022). They only analyze the Q-NPG method and achieve similar linear convergence results as our Theorem 1. In particular, their result in Theorem 4.7 has better concentrability coefficient compared to our Theorem 1. However, their Assumption 4.6 assumes that the relative condition number upper bounds a tame-vgyying ratio which depends the iterates, while our Assumption is independent to the iterates, as defined in (24). Furthermore, they only consider the case when the initial state distribution is the same as the target state distribution, while our analysis generalizes with any target state distribution, which is extensively discussed on the distribution mismatch coefficients in Appendix H. See Table complete overview of NPG in the function approximation regime.
"This result appears after conference proceedings and is available on 03247. 2.277.p6f.
/2200
17

---

Published as a conference paper at ICLR 2023
Table 1: Overview of different convergence results for NPG methods in the function approximation regime. The darker cells contain our new results. The light cells contain previously known results for NPG or Q-NPG with log- log-linear policies that we have direct comparison to our new results. White cells contain existing results that do not have the same setting as ours, so that we could not make direct comparison among them.
Setting
Rate
Reg.
C.S.
L.S.
Pros/cons compared to our work
Linear convergence
Regularized NPG with log-linear (Cayci et al., 2021)
Linear
Better concentrability coefficients C,
Weaker assumptions the approximation error with Lz norm instead of L norm;
Off-policy NAC with log-linear (Chen & Theja Maguluri, 2022)
Linear
They use adaptive increasing stepsize, while we use non-adaptive increasing stepsize Their relative condition number depends on l, while ours independent to
Q-NPG with log-lincar
Linear
(Alfano Rebeschini, 2022)
Q-NPG/NPG with lincaincar
Linear
(this work)
Sublinear convergence
PMD for linear MDP
O (+)
(Zanette et al., 2021; Hu al., 2022)
Two-layer neural NAC
0 ((t))
(Wang et al., 2020)
Two-layer neural NAC
(())
(Cayci al., 2022)
NPG with smooth policies
(Agarwal et al., 2021)
NAC under Markovian sampling with smooth policies
o())
(Xu et al., 2020)
NPG with smooth and
Fisher-non-degeneratt policies (I-iu et al., 2020)
((2)
Q-NPG with log-lincar
(
They have better floor than
(Agarwal et al., 2021)
Weaker assumptions the approximation error with Le norm instead of Loo norm; They use adaptive increasing stepsize, while we use non -on-addptive increasing stepsize
Off-policy NAC with log-lineat (Chen et al., 2022)
(
Q-NPG/NPP with log- linear (this work)
(
Reg.: regularization; C.S.: constant stepsize; L.S.; increasing stepsize.
Fast linear convergence of other policy gradient methods. Different to the PMD analysis ap- proach, by leveraging a gradient dominance property (Polyak, 1963; Lojasiewicz, 1963), fast linear convergence results have also been established for the PG methods under different settings, such as the linear quadratic control problems (Fazel et al., 2018) and the exact PG method with softmax tabular policy and entropy regularization (Mei et al., 2020; Yuan et al., 2022). Such gradient domination property widely explored by Bhandari Russo (2019) to identify more general structural MDP settings. Linear convergence of PG can also be obtained through exact line search (Bhandari & Russo, 2021, Theorem (a)) or by exploiting non-uniform smoothness (Mei et al., 2021).
Alternatively, by considering general strongly-concave utility function of the state-action occupancy measure and by exploiting the hidden convexity of the problem. Zhang et al. (2020) also achieve the linear convergence of variational PG method. When the object is relaxed to general concave utility function, Zhang et al. (2021) still achieve the linear convergence by leveraging the hidden convexity of the problem and by adding variance reduction the PG method.
18

---

Published as a conference paper at ICLR 2023
A.3 FUTURE WORK
The main focus of this paper was the theoretical analysis of NPG method. The results we have obtained open up several experimental questions related parameter settings for NPG and Q-NPG. We leave such questions as an important future work to further support our theoretical findings.
An interesting application from our work is to investigate the sample complexity of natural actor- critic with our PMD analysis. Indeed, our paper obtains w.(k) by a regression solver. One can also use temporal difference (TD) learning (e.g., Cayci et al. (2021); Chen & Theja Maguluri (2022); Telgarsky (2022)) with Markovian sampling achieve similar (11/e2) sample complexity result. The performance analysis of TTD learning will be expressed for estat, which directly imply the total sample complexity results through our theorems.
One natural question is whether we can extend our analysis to the general policy classes. Here we provide one possible way. It can be extended by using similar compatible function approximation framework. Concretely, consider the parameterized policy
Ts. (0) exp(Js.((0)
exp(Js,a (0))
where (0) is parameterized by 0 E T and is differential. As Agarwal et al. (2021) mentioned, the gradient can be written as
o log T.. (0) Ia.a (0) where Is.0 (0) (,)) (0)) [Vols (0)]
The NPG update is equivalent to the following compatible function approximation framework
[ (Abaa(((t)) w (e.(((())))
g(++ = ( new!
W. E min E (s.a))ad
As Alfano & Rebeschini (2022, Remark 4.8) mentioned, if we assume that for all (s, a) E S x A. function f() satisfies
)o.((0(++))== fa,a((())) Th (w: (zo TT (B(*),
which is the case for the log- linear policies, then one can easily verify that the NPG update resulted new policy is also equivalent to the policy mirror descent update
(k+1) arg min PEA(A)
{TH ( (c)) D)) + D(p, D(p, ). Vs E S
π
where ( R A|xx is matrix with rows (gs.a ()(K))) RIxm for a E A. Consequently, one can extend our work naturally in this general setting to derive linear convergence analysis for NPG.
Perhaps one can consider the exponential tilting, a generalization of Softmax to more general probability distributions. Another interesting venue of investigation is to consider the generalized linear model instead of linear function approximation for the Q function and the advantage function.
One interesting open question is that is there way to increase stepsize when the discount factor unknown. So far the PMD proof techniques used in Lan (2022); Xiao (2022) and ours require that the discount factor is known. Perhaps the work of Li et al. (2022a) can help to find a way to increase stepsize when the discount factor is unknown. Indeed, Li et al. (2022a) consider the averaged MDP setting. So there is no discount factor. They achieve linear convergence for NPG by increasing the stepsize with some regularization parameters. It will interesting to investigate if the way of increasing stepsize in Li et al. (2022a) can be applied in our setting.
B STANDARD REINFORCEMENT LEARNING RESULTS
In this section, prove the standard reinforcement learning results used in our main paper, including
the NPG updates written through the compatible function approximation (11) and the NPG updates formalized as policy mirror descent ((16) and (17)). Then, prove the performance difference lemma (Kakade & Langford, 2002), which is the first key ingredient for our PMD analysis. The three-point descent lemma (Lemma 1 11) is the second key ingredient for PMD analysis.
19

---

Published as a conference paper at ICLR 2023
Lemma 1 (NPG updates via compatible function approximation, Theorem 1 in Kakade (2001)). Consider the NPG updates (8)
0(++1) 9(h) - T/x FT VoVo(0
and the updates using the compatible function approximation (11)
gl++1) = -g(k) T) T)/.
where wht E argmin LA d.))). If the parametrized policy is differentiable for all E Imm then the two updates are equivalent up to a constant scaling (1 (1 of Tj
Proof. Indeed, using the policy gradient (7) and the fact that EaEA VTs,a (0) 0 for all É S, as r (0) is differentiable on and DeEA Ta,a 1, we have the policy gradient theorem (Sutton et al., 2000)
(o)) = Ex am~m [A (0) Vo log aa (0)]-
(36)
Furthermore, consider the optima !* By the first-order optimality condition, have VWLA(W. (k) ((() (dk))=
E (s,a)dd()))
(w: (k) Vo log m
(0(a()())) Vo log π (A)
=0
Vo log log 7 w// (s,andd
(s
Vo log To ssa
(1)
( log क (k)
(o(((k)) (k)
VoV
Thus, we have
wx (1 -1,,))(0),,,,0
which yields the update (8) up constant scaling -) of T7--
Lemma 2 (NPG updates policy mirror descent). The closed form solution to (16) is given by
Th 2.4()(k)))
(k+1)
n
(k)
AEA
exp
No.a exp
(k)
(- -,
(37)
(b (k)
exp
ny
(k)
(38)
EaEd Tza exp
(k)
-17] (0(,0())))) w((()
(To (1() (k))) p)) + D(p, D(p, m(bi)} Vs E S,
arg min PEΔ(A)
(39)
where 3 is the element-wise product between vectors, and (h)) E Ill is defined (17), i.e.
(b(h) 5,0
def
(0(k)
(12)
2s.a - E Ba'na! (1) [0s.rr).
Such policy update coincides the inexact NPG updates (32) of the log-linear policy, if((k+1) = ((k) Th (k) with (k) z argmin,.. LA [a(w, g(k), )i and coincides the inexact Q-NPG updates (18) of the log-linear policy, if ((k+)) = ((k) T (k) with (k) so argmin Lo(w, 013) ((()).
Proof. For shorthand, let &, (k), Thus, (16) fits the format of Lemma 10 in Appendix where Consequently, the closed form solution is given by (99), that is
q = ne (R)
(k) nT ④ m2
(K)
3 e nA (1))
π (k-1)
EnEA Teld-mmas na9a
En Ted
Th mo ml(4)
exp mmm (h( (O(N))
((A)
(40)
EnEA exp
mmhh (0 (0(k))) T w(())
20

---

Published as a conference paper at ICLR 2023
where the last equality is obtained
(s 2s.a E Batwast) [ Ds.a
Cas
with C2 R some constant independent a.
Similarly, by applying Lemma 10 with g = o w((), the closed form solution to (39) is (40).
As for the closed form updates of the policy for NPG (32) and Q-NPG (18) with the parameter updates ((++1) o(k) (4, it is straightforward verify that it coincides (37) and (38) given
the specific structure of the log-linear policy (6), which concludes the proof.
Lemma 3 (Performance difference lemma (Kakade & Langford, 2002)). For any policy x, n' A (Aa and E (SS).
1
Vo(T)-V,(rt) V2((T))
1- (e.aa)d (
(41)
1- Eendr [(Q((T'), Ts - n m/)],
(42)
where (T) is the shorthand (Qa,a ( (o) E RIAl for any policy æ.
Proof.
From Lemma Agarwal al. (2021), we have
1
V₂(T) - (=(T)) 1-7 (a.a)aaä [A),a(=')]
= I- Exnar [A,((T)), m+))),
where (T( is the shorthand for [Aa,a(T))as (T]]aSA E IR Al for any policy æ. To show (42), it suffices to show
(A.(a)), )))) (Q.(('). n. -T'). for all E S and ,, n' E A(A)).
Let 1n denote a vector in R" with coordinates equal to element-wisely Indeed, using the definition of the advantage function
Ana(TT) = Qx,a(T) - V2(T),
we have
(A,(T'), = (Qo(T') Vo(T') 1|11, To) (Q((T'), (V.(T') 1|A,, Ts)
(Qa(1'), V.(TT)
(Q²(T'), -
from which we conclude the proof.
C ALGORITTM
C.I NPG AND Q-NPG ALGORITHM
Algorithm combined with the sampling procedure (Algorithm 4) and the averaged SGD procedure, called NPG-SGD (Algorithm 5), provide the sample-based NPG methods.
Similarly, Algorithm 2 combined with the sampling procedure (Algorithm 3) and the averaged SGD procedure, called Q-NPG-SCC (Algorithm 6), provide the sample-based Q-NPG methods.
C.2 SAMPLING PROCEDURES
In practice, we cannot compute the true minimizer wi (k) of the regression problem in either (32) or (18), since computing the expectation LA or LQ requires averaging over all state-action pairs
(8, a) (()) and averaging over all trajectories (8o, on, <D, .., to compute the values of ( and (k) So instead, we provide a sampler which is able to obtain unbiased estimates of Q (8) (or As.a (0) with (s, a) do (v) for any n (0).
21

---

Published as a conference paper at ICLR 2023
Algorithm 1: Natural policy gradient
Input: Initial state-action distribution v, policy π (100, discounted factor y E [0, 1), step size
7lo 0 for NPG update, step size 0 for NPG- SGD update, number of iterations ' for NPG-SCD
for k = 0 to K - do
Compute w((h) of (32) by NPG-SGD, ie., Algorithm 5 with inputs (T, (hh), 7 a)
Update ((++1) g(k) (k) and Ti
Output: (K)
Algorithm 2: Q-Natural policy gradient
Input: Initial state-action distribution v, policy T("), discounted factor 7 E [0, 1), step size
T/o for Q-NPG update, step size for Q-NPG-SGN SGD update, number of iterations T for Q DP-GGG
do for k 0 to (h) of (18) by NPG SGD, i.e., Algorithm 6 with inputs (T, 7k)) Tr o.)
Compute
Update ((k-1) ((k) maw (8) and T/k
Output: T((K)
Algorithm 3: Sampler for: (s. dv(v) and unbiased estimate a.. (f) of Qs,a(0)
Input: Initial state-action distribution policy T00), discounted factor [0, 1) Initialize (Sg. 0n) ~ v, the time step h, 0, the variable X
while X = do
With probability 7: Sample 81+1 P( 1 an)
Sh, Sample 04+1 ~ Teati (0)
- h +1
Otherwise with probability (1 71-
X =0 0
> Accept (sh, an)
==1
10 the estimate Qu, (0) = c(sn; un)
Start to estimate Q
1 = h
12 while X do
With probability 7: Sample 8t+1 ~ P() 88, (8,0t))
14
Sample de+1 TT (8)
Qenaan (0) x- 2 (0) + 0(88+1, 0441)
16
17
1+
Otherwise with probability (1 7)
x
Accept Q (0)
19
Output: (sh, an) and a (0)
22

---

Published as a conference paper at ICLR 2023
To solve (18), we sample (s, a) (k) and Q%,d by standard rollout, formalized in Algorithm 3. This sampling procedure is commonly used, for example in Agarwal et al. (2021, Algorithm 1).
It is straightforward to verify that (sh, an) and 2a. (0) obtained in Algorithm 3 are unbiased for any (0). The expected length of the trajectory is r We provide its proof here for completeness.
Lemma 4. Consider the output (sh, an) and Qon.on (0) of Algorithm 3. It follows that
1
I hh + 1 7
Pr(sh- = 5, ab =a) = d= (v),
E Qen.on (0) Shc an = Qonian (0).
Proof. The expected length (h + 1) of sampling (s, a) is
E 1] Σ Pr(h - k) 1)
Σ
7 (k +1
1
The probability of the state-action pair (s.a) a) being sampled by Algorithm 3 is
Pr(sh- = 8, = a)
Σ
Vop ap Σ
Pr(h- kc) (r s, h k, so. Qo)
(E0,0))ESxA
Σ
V0 (1 7)
# Pr (0)
(sk (0)
av = a su. 0o) dv.a(v).
(S0,00)ESXA
k=
Now verify that Qen,en (0) obtained from Algorithm 3 is an unbiased estimate of Q as (0). Indeed, from Algorithm 3, we have
H
Q an (0) = Σ c(
(43)
where (H 1) the length of the horizon executed between lines and in Algorithm 3 for calculating a.,.., (0). To simplify notation, we consider the estimate of Qs.e for any (s, a) E S x A following the same procedure starting from line 10 in Algorithm 3. Taking expectation, have
E (0)
s,a
E
c(s
a+)
so s,
1=0
Pr(H K>
Σ c(sr, az) 50 =, =0
k=
Σ (1 - AT
Σ
c(SE, at) 80 = 8,400 =
k=0
1=0
(1 E/E
c(st, oz)
7
k
Su = 8,
kmt
E
* ce(ss, az) 800 8, 0g000
@ Qu.a (0).
The desired result is obtained by setting s = 8n. and ap.
Similar to Algorithm 3, to solve (32), we sample (s, a) ~ (b) by the same procedure and estimate (k) with slight modification, namely Algorithm (also Agarwal et al., 2021, Algorithm 3).
23

---

Published as a conference paper at ICLR 2023
Algorithm 4: Sampler for: (s.a) (v) and unbiased estimate ( of (s,
Input: Initial state-action distribution v, policy (0), discounted factor 7 E 10, Initialize (so, dg) ~ the time step h, = O, the variable X =
while X do
With probability 7:
Sample 81+11 ~ Pp( 8h, as)
Sample 04+1 TsAtI (0)
h 1- h+1
Otherwise with probability (1 -y): X
b Accept (sh, an)
X
Set the estimate Toy.an (0) = c(8n, un)
Start to estimate a (0)
11 1 h
while 1
13
With probability 7:
Sample 8t+1 P(- St, az)
Sample ae+1 ~ Tl x (0)
15
Qunnen (0) 2 (0) c(8++1,041)
17
1+1+1
18
Otherwise with probability (1 (1=
x
Accept Qan.as (0)
19
20
X =
Set the estimate V2,
Start to estimate Va, (0)
22 1 = h
23
while X 1 do
24
Sample ae Te, (0)
V., (0) V., (0) + c(st, ac)
25
26
With probability
27
Sample 88+1 P(: 8t, at)
29
Otherwise with probability (1 (1-7):
X
> Accept Va, (0)
Output: (sh, an) and Asn.an (0) = Qus.an (0) - V., (0)
24

---

Published as a conference paper at ICLR 2023
Notice that the sampling procedure for estimating (0) in Algorithm 3 is simpler than that for estimating (..(()) (0) in Algorithm 4, since Algorithm 4 requires an additional estimation (0) and thus doubles the number of samples to estimate As,a (0). As in Lemma 4, we verify in the following lemma that the output (sh, an) is sampled from the distribution do and Asn,on (0) Algorithm an unbiased estimator of As,.as (0) for all policy (0).
Lemma 5. Consider the output (8h: an) and Asn,au an (0) of Algorithm 4. It follows that
1
E h
Pr(sh 0, a) dgga(())
E Ann (0) sk. ap Ash,on (0).
Proof. Since the procedure of sampling (sh, .4) in Algorithm is identical the one in Algorithm
from Lemma the first two results are verified. It remains to show that As, (0) is unbiased.
The estimation of A (0) is decomposed into the estimations of Qu. (0) and V., (0). The procedure of estimating Qsn,as (0) is also identical to the one in Algorithm 3. Thus, from Lemma 4, we have
Q Qaa.an (0) 8h, an an, (0).
By following the similar arguments of Lemma 4, one can verify that
E V2, (0) 8h, an = Voa (0).
Combine the above two equalities and obtain that
Amn (0) |
E @Qn..a i (0) Vap (0) 8h, ah Qanian (0) (0) VV,,, Aon (0).
S/c aih.
C.3
SGD PROCEDURES FOR SOLVING THE REGRESSION PROBLEMS OF NPG AND Q-NPG
Once we obtain the sampled (s, a) and (0(k)) from Algorithm 4, we can apply the averaged SGD algorithm as in Bach & Moulines (2013) to solve the regression problem (32) of NPG for every iteration k.
Here suppress the superscript (k). For any parameter 0 E R", recall the compatible function approximation LA in (32)
LA (w, 0, 0,d") (e.a)ad
A,,))))
With the output (s, a) _ and (9) from Algorithm (here we suppress the subscript h), we compute the stochastic gradient estimator of the function LA in (32) by
LAw 0, 0, def )0, (0) (0).
(44)
Next, we show that (44) is an unbiased gradient estimator of the loss function LA-
Lemma 6. Consider the output (s, and (s) of Algorithm 4 and the stochastic gradient (44). It follows that
E (.LLlw 0.) V 0w
where the expectation is with respect to the randomness the sequence of the sampled So, 0g. " , 81, 04 from Algorithm 4.
25

---

Published as a conference paper at ICLR 2023
Proof. The total expectation of the stochastic gradient is given by
E VuLa( 0, d
(44
B (0) (2 (w "s,a(0) - ( )s,( (s.a)rid (o))(0) (2(ww) (0,(()) (0) A., )e s (45)
(w)
where the second line is obtained by (s,a) ~ d0 from Lemma 5. From Lemma 5, we have
Exg 51 [Asa (0) 60 8, 0,000 =a] (s)
(46)
Combining the above two equalities yield
V LLwW 0 dd)
(45)
((saa)ddo
2 (2(w0 Tsa( - Ar.a {s )sa(()]
(2 Ta, As,a (0, 0.))
Fula(w,,,d"
as desired.
Since (44) is unbiased shown in Lemma 6, we can use for the averaged SGD algorithm to minimize L. called NGG-SGD in Algorithm (also see Agarwal et al., 2021, Algorithm 4).
Algorithm 5: NPG-SGD
Input: Number of iterations T, step size >> 0, initialization wo E R". initial state-action
measure 1/, policy π (d). discounted factor E [0,1)
for i to T do
Call Algorithm with the inputs (0), 7) to sample (s, a) do and (0)
Update W1++1 W/ - a (w,, 0, d by using (44)
Output:
Wout
E We
Similar to Algorithm 5, once we obtain the sampled (s, a) and (.) from Algorithm 3, we can apply the averaged SGD algorithm to solve (18) of Q-NPG.
Recall the compatible function approximation LQ in (18)
Lo(w, 0, dd) E (s,aaad (w Øs.a Qa. (0))
With the output (s, a) d and (0) from Algorithm 3, compute the stochastic gradient estimator the function Lo in (18) by
To 0, ) def Tw.. 2ea( De,e:
(47)
and use for the averaged SGD algorithm to minimize L.p, called Q-NPG-SCO in Algorithm (also Agarwal et al., 2021, Algorithm 2). Compared (44), the cost of computing (47) is [A| times cheaper than that of computing (47). Indeed, to compute (47), we only need one single action for
as.a. while to compute (44), needs to go through all the actions to compute (f). Thus, the computational cost of Q-NPG- SCD is A times cheaper than that of NPG-SGD.
The estimator (wLo( 0, dd)) is also unbiased following the similar argument of the proof of Lemma 6. We formalize this in the following and omit the proof.
Lemma 7, Consider the output (s, a)) and (0) of Algorithm 3 and the stochastic gradient (47). follows that
E V Iw dd]] Vw 0,"),
where the expectation is with respect to the randomness the sequence of the sampled So, ".. , 81, 04 from Algorithm 3.
26

---

Published as a conference paper at ICLR 2023
Algorithm 6: Q-NPG-SGD
Input: Number of iterations T, step size 0, initialization wo E R",, initial state-action
measure v. policy ((). discounted factor E [0, 1)
for f 0 do
Call Algorithm with the inputs (v, (O), 7) to sample (s, ~ d and Qa,a(
Update W1+1 Wy a w.w 0, d by using (47)
Output: Wout = 7 Li=1 We
D PROOF OF SECTION
Throughout this section and the next, we use the shorthand V/(k) for (0(K)) and similarly, Q.ad for
( and and for A (0()). We also use the shorthand Q! (k) for the vector Q (k)
E TR|A
and A for the vector
A
RIA!
aEA
We also introduce weighted KI. divergence given by
D def Egnd' (m
we choose the uniform initial policy, i.e., ns.a 1/|A| for all (x, E A (or ( =0), then
(0)
D log [A].
(48)
for all p E (SS) and for any x' E ((A)..
We first provide the step analysis of the Q-NPG update, which will be helpful for proving Theorem and and the sublinear convergence result of Theorem 2 further in Appendix D.3.
D.1 THE ONE STEP Q-NPG LEMMA
The following one step analysis of Q-NPG is based on the mirror descent approach Xiao (2022). Lemma (One step Q-NPG lemma). Fix state distribution an initial state-action distribution v; arbitrary comparator policy πτ" Let w!! argmin,, LQ(w,, ((k) dd()) denote the exact minimizer. Consider the (k) and Te given in (18) and (16) respectively. We have that
21(1 - 7) (((++)) -v(x) (1 (1 (V,0) Vo((T))
0p
( (1++) (k++1 10. (wo(t) -10())))))))
ΣΣ
1(++1) (k++1 (0), (bTaw! ! -2(1)
sES
aES
ΣΣ
1++ (k)
x
2,0 Paa
(w+ ((()))
+
Σ
(k++1) (k)
(Q!!)
T w
#ESaEd
sESaEA
d' do D
(k) w((h))
&e,a
w ((A)
8,0
(s,4)ESXA
(3,))E5XA
Wx w(()
d' ((()) T
(s,a)ESxA
(x.))ESxA
1
D
Diat'
(49)
1]
n
27

---

Published as a conference paper at ICLR 2023
Proof. In the context of the PMD method (16), apply the three-point descent lemma (Lemma 11)
with C = (A), I is the linear function ye (F,w () and h ((A) - IR is the negative entropy with h(p) = Encal A Pa log Thus, h is of Legendre type with rint dom A nc = rint ((A) & and (;(;,)) is the KL divergence -...)). From Lemma 11, we obtain that for any p E (AA,, we have
?) ( , (((t1)) + D(TT ,,,) S mh (2, (t,w(t)))) + D(p, - D(p, 1
Rearranging terms and dividing both sides by Th. we get
DD x (k+1) 1) D(== (x+1) xx S
D(p (4))
D(p, = m((+tl)).
(50)
77
Letting p = (b) yields
$ ( 2 (k+1) (1))
1 ((
xk)))
1 D , ( SO.
(51)
Letting p = n.. and subtract and add as
(2)
within the inner product term in (50) yields
(1ww(h n (k+1) xx(R)) + (
33 T/K
D(
x(()))
1 - D( m ((++)))..
7]
Note that we dropped the nonnegative term
D (k+1) 1) n. on the left hand side to the inequality.
Taking expectation with respect to the distribution d", we have
Band" (0,,0(() x (1++1) (00 + Exnat
( (00 (0, mT(h) -m=aa
1
1
DI
D Di+1 (52)
7k
For the first expectation in (52), we have
Bynd ( (0.20(()) x (k++1) x
(A)
Σ dz (Daw)()) (1+11] =/(
(2.w(t) ,T (k+1) (k) de (k+1)
Σ
(k+1)
0 k+1
((++1) ( 1D (D22((k) ,
- ((++1) x (K))
sES
Σ (k+1) / (k) , (k++)) - xka))
0
SES
d (k+1) (Q!(), , (k+11) -m((k) + U, Σ d(k+1) ( (D.wil)) (R()) , (k+1) x(())
= 0,(1 7) (v( -v(h) + 1, Σ ((k++) (D.w(() ( (R))), T (k+1) xx(1)
(53)
#ES
where the last equality is due to the performance difference lemma (42) in Lemma 3 and the two inequalities above are obtained by the negative sign of o D (M), Ta (k+1) ((4) shown (51) and by using the following inequality
d'
(20)
22)
S
x+
S
d!
(k+1)
Ij
28

---

Published as a conference paper at ICLR 2023
The second term of (53) be decomposed into four terms. That is,
Σ SES
(k+1)
D (. Q!a,, T (k+1)
mT!))
Σ>>
x (k+1)
(0) w(()) -QU
ΣΣ
d(k+1) (Q
oo k0
RESREA
Σ
((++1)
(k+1)
Dan (w)lt) -w
Σ> Σ
( 1) n
(k+1)
( w
Q
n1 s,
5.a
#ES
aES
+
1(++1)
(k) ( (w) - wl(i)
"sa 8,0
+
[k++ 1) m(
3,0
(k)
(
22,0
(K)
aEA
#ES aEA
1+
(54)
where 1 2. 3 and 4 are defined in (49).
For the second expectation in (52), by applying again the performance difference lemma (42), we have
Egnd' D (D,w(k) -T! TT;)
Exwd'
(Q0th) [ 18 (k) -tti + EsSnt
- (+(²) 2 {( (Q) - ((1,, m (K) m3
(0
(R) mz
(1->) (R) Vo(TT) + Bond'
(55)
Similarly, we decompose the second term of (55) into four terms. That is,
{( (0,
, Tr -0:-)
Egnd
Σ
Σ
df d ( -Q! +
(k)
ΣΣ
di (ota -o t0
sES aEA
#ES
sESdEd aed
Σ
di o (20 - w/
(A)
(k)
(p w/) -Q(k)
(s,
(s.a)ESxA
Σ
da oo (K) mo(t)) +
Σ
dy (Q!)) -55a w
(x,0)ESxA
(s.a)ESXA
@ + b +
(56)
where @ (b. and ( are defined in (49).
Plugging (53) with the decomposition (54) and (55) with the decomposition (56) into (52) concludes the proof.
Consequently, the convergence analysis of Q-NPG (Theorem 1, 3 and Theorem further in Ap- pendix D.3) will be obtained by upper bounding the absolute values of ( 2 3 in (49) with different set of assumptions (assumptions Theorem 1 or assumptions Theorem 3) and with different step size scheme (geometrically increasing step size for Theorem and 3 or constant step size for Theorem 2).
4
@ b. C. d
D.2 PROOF OF THBOREM 1
Here we provide the general Q-NPG convergence analysis with any initial policy, which is in contrast to Theorem I with the uniform initial policy.
Theorem 5. Fix state distribution p. state-action distribution and a comparator policy n².
We consider the Q-NPG method (18) with the step sizes satisfying no 2 1-1 Dū and M 2 1 mk-
Suppose that Assumptions 1, 2, 3 and 4 all hold. Then we have for all l 2 0,
[1)] Vo(TT) < (1- 1 k 0, 1 1-7 +
(1-),)
2/12 (0,/C, 1)
(
Ri
Estat + V
1-7
I 1-7
29

---

Published as a conference paper at ICLR 2023
Remark. A deviation from the setting of Theorem is that here require the step sizes satisfying 7
Yo 2 1-2 D instead of Y/o 2 1-1 log |A|. This is because when using uniform initial policy in
7
Theorem 1, from (48), we know that 1/o 2 1- log |A| is a sufficient condition for % 2 1-2 Dö-
Consequently, to prove Theorem 1, it suffices to prove the more general Theorem 5.
Proof. From (49) Lemma 8, we will upper bound ! and (3) by the statistical error assump- tion (19) and upper bound (2) and [ by using the transfer error assumption (22).
Indeed, to upper bound [0), by Sauchh-Schwartz's 's inequality, we have
((++1) n aaa
11++)
S2.a (w)(k)
#ES aEA
(d(tt) 2
(
Ta
Σ (s.))ESAA
dz Unifa(a) (05 (wit)) w )²
dg . (nniff((a
(s,0)ESXA
(
Ta.a ?
23)
[w(k) w
(1) 2
d3 - (a)
Ez
(s.0)ESXA
de (lk+1) 27
[A] wo(k) w! (
Exnd
dz
125-
IAB
CplA1|
(x()) - =
(1))
(57)
Σz-
where the second inequality is obtained by SchwartSchwartz's inequality, and the third inequality is obtained by the following inequality
Σ
((+1)) s.a
2
A 8,0
(k+1)
1.
(58)
a
aEAA
Then, by using Assumption with the definition of Ky. (57) is upper bounded by
AA
ColAAln (wokks w.
D
V
E.
(k)
12
(59)
1 1-7
1z(4)
where we use the shorthand
Eza def (
(60)
Besides, by the first-order optimality conditions for the optima w(()) argmin,, Lo ((k),
d(0)).
we have
(w (1)) T V ( (k) (00)))))00 (0,000) 2 0.
for all w e R..
(61)
Therefore, for all RT,
[o ((k)
j(0)) -o (R) 0(()) ((k))
(oTa w - JTaw( ((k) + To (k) QQth) 27
!o(w!! (eo g(() _(())
E ((
Ss w To w. [()))]]]] + 2( - (k) TT (sa)aaa (10Ta Q())) )
E ((g.))d(1))
(k)
+ (w ) V. (k) 0(0)) 2((0)
W w
(6)
(k)
2
w W.
(62)
Σ Ez(0
30

---

Published as a conference paper at ICLR 2023
Define
(k)
def
(o(w!k), _(k)) - _ ,0(k) (l()) d(.))
Stat
Note that from (19), we have
(k) stat
I
Cstat-
(63)
Plugging (62) into (59), have
CpIAIti (k) 1-7
Estat
(64)
Similar to (57), we get the same upper bound for 3 by just replacing Tss
(k+1) into ns.0- That is,
(k)
Cpl (A) 1-γ Sttt
3 S
(65)
To upper bound [2] and (4) we introduce the following term
(k) bias
def
LQ(w! ,0(k), ,d)).
Note that from (22), we have
E
bias
(k)
S
Ebias.
(66)
By Cauchy-Schwarde inequality, we have
Σ
Σ
(+++1) m
(1++1)
(K)
(A)
"8,0
aEA
de 1
(1+1))
18.0
Σ
Σ
dz Unif (DIa QQ.d)
dz Uni
(s.a)ESxA
(s.0)ESxA
(
(1+1))2
Ts,a
(k) bias
d; (Unifa(()
(s,)eSxx
(k++1) 27
(58)
Bend"
(k) hias
V (olAAle (8)
(67)
dz
Similar to (67), we get the same upper bound for 4 by just replacing Ts.a (k-1) into Ne.a-
(R)
That is,
4 S
(k) AlclA bias
(68)
Next, we will upper bound the absolute values of @. c and @ of (49) separately by using again the statistical error (19) and by using the transfer eтror assumption (22).
Indeed, to upper bound (0), by Cauchy-Schward
inequality, we have
Σ
1h) 02.0 (k) -w, (k)
(k)
(N)
(s,a)E5xA
(2) 2 (d Nec
d; Unif (oT (w(k) w. w())))
dy (a) (x.0)SxAA
(A.)ESXA
(K) (dg)
2
[wo(k) [R(
(A d Unif
Ez.
|A||
(k()) w (k) 1ig-
31

---

Published as a conference paper at ICLR 2023
From the definition of Ky, further obtain
(w(l))
(2) 55+
(2)
w.
IA3
|A/rs (w(h)) w// (k)
1
12(k)
Aliiy (k) Sttat
(69)
Similar to (69), we get the same upper bound for ( by just replacing (k) into T.. That is,
A Niv (k) statt
C S
(70)
To upper bound [D) by
inequality, we have
Σ
d² x
(o..a (R) Q.:2)
(s.a)ESxA
(dz)
(k)
Σ
Ta.a
E
d; Uniff(aa (05, ( QQ!/d
(K)
dz (a) (Ka))SxA
(M,a)ESxA
(d:)² (R)
(k) bias
d3 (a)
(aa)sSa
(Al (k)
(71)
Similar to (71), we get the same upper bound for ( by just replacing Ts,a into vg... That
(k)
A
(k) hias
(72)
Plugging all the upper bounds (64) of [ (67) of (2, (65) of (3) (68) of (4), (69) of @), (71) of
( (70) of C and (72) of (d) into (49) yields
D
Di+1
0p (5++1 6x) 8x <
(1 7)
(1 - 7mm
2 2/Al (0,VC, +1)
( (1-7
Kip
(k) Stat
+
V
Cias
(k)
(73)
1-7
where 6g def v(()) V,(T"). Dividing both sides by U and rearranging terms, we get
8x41 + (1- 7)mo - 1 ) 8x (1- (1-))m((1, -
Di+1
D
2 AA
CCpp + 1
Ft)
(V
(
Ky Ky
(k) bbas
stat +
V
?
32

---

Published as a conference paper at ICLR 2023
If the step sizes satisfy (1+ 1) m= which is implied by Mo+11 nx/7 and (20), then
Di++
dR+1 +
7)111++1 (0p -1)
(1
1.)
D
0
6x + (1-7)mm(,, (Up 1)
2 |
(VC + +,2)
(V (1-1>
1iv (k)
(k) bbis
+
Coeat + V
1 1-7
-
k+1
80 + (1 - 11)000000p-10 -
0p/
k-t 2vIA (v + 2.))
+
1
(v
Ky
(8) seat
+
V
Ve00
(t)
1-y
1
0=0
Finally, by choosing 7o
1-1 Di and using the fact that
(00
( (1-7-1 -1)-
(1 (1- - 1) 2 (1-
=7
we obtain
Dj
5k S 6% +
(1 -
7)
$ 1 2
0p/
1 1-7
2 A (VC, +
+. Jpp)
(1-
Σ
k-1
--1-t
(VI-,
Ni Stat +
V (t)
Cbae
1-y
t=0
Taking the total expectation with respect to the randomness in the sequence of the iterates (()) (k-11,, we have
E (1)) -Vo(TT)
}
1
k
1 1-7
p
2
A
1-7
(Vp+
+
1
1
8p
1
k-1-t
E
Ki
7
Stat
(t)
E
(4) bias
1=
(1
1
2
<
U,
1-7
2v
A
1-7
CCp +
k-1
1
0p
1 1
k-1-t
(v
1
Ky
E
Sstat
(1)
+
(e) Bias
(63)+(66)
(1
1
2
1 1-7
AA
(Vo++
k-1
k-1-t
+
0e
Σ
(v I 1-7 Estat + /biias
Kiu
1-7
J,
1=0
11-
1
1
k
2v|A (1,
(V1
Ki 11-x Cstat + Chius
+
0,
1-7
1-7
where the second inequality is obtained by Jensen's 's inequality. This concludes the proof.
n
33

---

Published as a conference paper at ICLR 2023
D.3 PROOF OF THEOREM 2
Similar to Theorem 5, to prove Theorem 2, it suffices to prove the following sublinear convergence of Q-NGG with any initial policy.
Theorem 6. Fix a state distribution p. an state-action distribution v and an optimal policy π². We consider the Q-NPG method (18) with any constant step size Th " Suppose that Assumptions 1, 2, and all hold. Then we have for all k 2 O,
E t=0
[o([T10) V(((T))
1
+ 20,)
7)k
19
2 2VI COp +1)
(V
(VI-7 Escat + +V
Ky
Ebias
1-7
Remark. A deviation from the setting of Theorem is that here we require x to be an optimal policy 5. Compared to Theorem 20 in Agarwal et (2021), our convergence rate is also sublinear, but with an improved convergence rate of O (1//k), as opposed to ((I/V)). Moreover, they use diminishing step size of order (LIVV)) while our constant step size unconstrained.
Proof. By (73) and using constant step size 17, have
0, (8u+1 - 0x) + 6a <
Di+1 (1 7)- (1-?)9
Dr
+ 2 AIA (0 (DpVC++1) -
(V1
Ki (k)
(k) Cbias
1 1-7
Stat
Taking the total expectation with respect to the randomness in the sequence of the iterates (()), ,u(k-1), summing up from to k - and rearranging terms, we have
O [&)
Σ
[6.]
(1 7)n 0,00 t 2 (Dpv C +1)
Dj
1-7
(V1
1-
Riy
Cstat + Vbbas
where we the following inequalities
(63)
E
CCtttt>
stat
stat
(e)
(66)
E
Cisa
biss
V
Ebiss.
Finally, dropping the positive term [ōx] on the left hand side as म² is the optimal policy and dividing both side by k yields
D
20,
E t=
+
(1 7)nk
(1-7)k
2 |Al (0pvCp- +1)
(v
By
Cseat + /
Ebias
1-
(1-
D.4 PROOF OF THEOREM 3
Similar to Theorem to prove Theorem suffices to prove the following Q-NPG result with any initial policy.
Theorem 7. Fix state distribution p. an state-action distribution and a comparator policy n². We consider the Q-NPG method (18) with the step sizes satisfying 17o 2 1-x Dū and πc+1 7k- Suppose that Assumptions 1, and 6 hold. Then we have for all l N
2 2/C, (0p + 1) 1-7
E (+)) Va(TT)
(Vestat (iapprox)
0,
1-7
In our analysis, need to drop the positive term B[V,(0(())] - Vo(Tm) obtain lower bound, thus require x² he an optimal policy.
34

---

Published as a conference paper at ICLR 2023
Proof. Similar to the proof of Theorem 1, by Lemma 8, upper bound the absolute values of O 2. 3.
a. c.
i introduced (49), separately, with the set of assumptions in Theorem 3.
In comparison with the proof of Theorem I, will also upper bound | 3
and | by the
statistical error assumption (19) as the proof of Theorem 1. However, we will upper bound (2)
( O and (d) by using the approximation error assumption (27) instead of the transfer error assumption (22).
To upper bound [ by Cauchy-Schwance inequality, we get
ΣΣ
1 (k++1)
&2,n (2r(k) w
aEA
[k+1j)
(k+1)
d(k)
(o,a (wo(h) w. )
d(k)
(sa)ESXA
(s,))SXA
d (k+1) (k+1)
| Wx
(1)
E (s.))a(())
ds,a
Co 10(k)) - w
[1
V Coe
Similar to [ by using Assumption 6 and (l++1) into (k) or .- and replacing d(++1) into d', we obtain the same upper bound of (3), @@) and
inequality, and by simply replacing
[0], that is
3,
@
C
Next, we define
(k) approx
def
Le (8) ((k) _(())
By Assumption 5, we know that
E
(k) aapprox
I
Eapprox
To upper bound (2), by Cauchy-Schwand inequality, we have
(lk+1)
(k+1) n
T (((
(k) n.a
3,a
REA
(k+1)
2
(k+1)
d's
Ts.a
d
0 w - Q2.
(K)
T(k)
(s,a)ESXA
(s,a)ESxA
d (k+1) (k+1)
27
B(xa)-ais)
nsa (k)
(k) Capprox
dg
VC
Similar to (2 by using Assumption and (k+11 into π (k) or n² and replacing +1)+1 into d², we obtain the same upper bound for ( and (0), that is
's inequality, and by simply replacing
6
1
V Cueapprox
35

---

Published as a conference paper at ICLR 2023
Consequently, plugging all these upper bounds into (49) leads to the following recurrent inequality
D++1 0p (6x+1 - 6k) + db - (1 7m (1-7)Tk
D
+ 2vC (0p+1)
Vestue +
(k) Capprox
1-7
By using the same increasing step size as in Theorem 5 and following the same arguments in the proof of Theorem after (73), we obtain the final performance bound with the linear convergence rate
E [o(T(()))] Vo(TT)
2
2vCo (0, +1) (Vestat Veapprox)
1 1-9 +
1p
1-9
D.5 PROOF OF COROLLARY
In this section, we aim to prove Corollary presented in Section 4.3.
Corollary (Corollary 1). Consider the setting of Theorem Q-NPG Algorithum 2 is run for K iterations, with T gradient steps of Q-NPG-SGD (Algorithm 6) per iteration. Furthermore, suppose that for all (s, a) E S x A, we have [ S B with B > 0, and we choose the step size a = 2 and the initialization wo = 0.for QPNGG SGD. for all R"" the covariance matrix of the feature map followed by the initial state-action distribution satisfies
Suppose that the sumple-bused
Ey 2 pmm:
where Im E mm m is the identity matrix and μ O. then
- -Vv(()
)
2
+
2(0p + Dotapprro
0, 1 1-7
1 1-7
AVC,
+1)
B²
+ (1 (1-))3VT
14 (
(V2m
+ +1) -))
In order to better understand our proof, we first identify an issue appeared in the sample complexity analysis of Q-NPG in Agarwal et al. (2021, Corollay 26). Agarwal al. (2021) adopts the optimiza- tion results of Shalev-Shwartz & Ben-David (2014, Theorem 14.8) where the stochastic gradient L (w, 0, dd in (47) needs to be bounded 6 However, although they consider projection step for the iterate we and assume that the feature map Φ..a bounded, VLo(w, 0, dd still not guaranteed to be bounded. Indeed, recall the stochastic gradient of the function LQ in (47)
V LoLow (, 0, d) = Twoer De.a Qua((0) Ós.a.
They incorrectly use the argument that w, 2s and Q are bounded to imply that 6 Io 0 dd)] is bounded. fact, Qs.a (0) can be unbounded even though E [Qaa(() =
(0) E 00 -
is bounded. see this, we can rewrite @e.((0) from (43) as
Qo)((() = Σ c(ss) at).
with (Sg, ag) = (s, a) d0 and H is the length of the sampled trajectory for estimating Qs. (0) in Algorithm 3. From Algorithm 3 and from the proof of Lemma 4, we know that the probability of H is that
Pr(H = k 1) (1 /
So. with exponentially decreasing low probability, H can be unbounded. Consequently, 1Q., (0) upper bounded by H is not guaranteed to be bounded.
'We are aware that Agarwal et al. (2021, Corollary 6. 6.10) also use Bach & Moulines (2013, Theorem 1) in an early version https:/ / /aziiv. org/ org/pdf/ /1908.99..00 00261v2, pdd to obtain 6etat = O(1/T). With further regularity (31), Agarwal et al. (2021) mentioned that fstat ((1/T) can also he achieved through Hsu et al. (2012, Theorem 16).
36

---

Published as a conference paper at ICLR 2023
Proof sketch. Instead, adopt the optimization results of Bach & Moulines (2013, Theorem 1) (see also Theorem 12), which does not require the boundedness the stochastic gradient. However, in our following proof, we can verify that E (0)) is bounded even though (0) is unbounded. As to verify the condition (vi) in Theorem 12 in our proof, i.e., the covariance of the stochastic gradient at the optimum upper bounded by the covariance of the feature map up to a finite constant, we use a conditional expectation argument to separate the correlated random variables (s, a) d and a (0) appeared in the stochastic gradient.
Non-singularity of the covariance matrix Eg.. As for the condition (31), is shown in Cayci et al. (2021, Proposition 3) that with v chosen as uniform distribution over S x AA and Φ..0 ~ (0, Im) sampled as Gaussian random features, (31) is guaranteed with high probability. More generally, with m < | it is easy to find m linearly independent ós,a among all |S||||] features such that the covariance matrix Eg has full rank.
Proof. From Theorem 3, it remains to upper bound the statistical error Estat produced from the Q-NPG-SGE SGD procedure (Algorithm 6) for each iteration We suppress the superscript (k)). Let Wout be the output T steps Q M--PPGGSSS SGD with the constant step size 2 and the initialization wo = O, and let w. E argmin,,. LQ(u (w, 0, d be the exact minimizer. To upper bound estat from (19), we aim apply the standard analysis for the averaged SGD, i..., Theorem 12. Now verify all the assumptions in order for C-NDG-SCD.
First, (i) is verified by considering the Euclidean space H R
The observations (Da.a. : (0))()) E IR" x I are independent and identically distributed,
sampled from Algorithm 3. Thus, (ii) verified with on 2a.a Rn and žn (0..((0)d R..
As the feature map ||os,a || I B, we have E ||l I?] finite. From (31), know that the covariance
E. [ is invertible. To verify (iii), it remains to verify that E [|0
|| is finite.
Indeed, by using || < B, we have
E 10.
|]]
B Q (0)²
Thus, it remains to show IE (Qaa(())²
27
finite for (iii). From (43), we rewrite (0) as
Q..a
Σ c(ss. 1=U
with (so, ao) = (8, ~ d and H is the length of the trajectory for estimating Qa.a (0). Thus, (iii)
is verified the variance of (0) is upper bounded by
E (Q...()))
E (e.a)=d
Σ Pr(H= -
Σ c(st, at)
H k. 80 8,000
(e,))dd
7)
Σ "
c(s an)
H = k. 80 8,00
k=
1=0
2
< E (
(1
7)
* 1)²
<
(74)
(1
k=0
where the first inequality is obtained [o(se, 4z)l E [0, for all (st, a:) S A.
Next, we introduce the residual
< (Qa.e (0) w. (aa)) @s.0
(47
1 v WwL 0,d%)
(75)
2
37

---

Published as a conference paper at ICLR 2023
From Lemma 7, we know that
ve Lo 0, d.)))
VuTlquw 0, 0,d
So, we have that
E [ V...o(W,,, =
where the last equality is obtained as w, the exact minimizer of the loss function Lq. Thus, (iv) is verified with that f is 2/2 LQ. En is and is w in our context.
From Q-NPG-SGD update 47, we have (v) verified with step size a/2 in our context.
Finally, for (vi), from the boundedness of the feature map ||0,,al| B, we take B such that E | 11 0s
I B [, It remains to find > 0 such that
[EE S 2F [do.at...]
We rewrite the covariance of & as
E
[sc
(75)
E
(Qaa(()) - w. (T)aaa)) 00,00%0 00
(Qaia()) - -00 0e.0) 2
E ((,a)nnd'
ds si I s
E [(Qra(0)) - w 2msa u.)oaa) )2 1 8, dea0
(e,aa)va
Thus, it suffices to find O such that (Qeal()) - w )s.a s, a
(Qaal()) 3, -2Q,,a()) da + (w. )oa)) S 0²
(76)
for all (8, E A to verify (vi). Besides, know that
E (Q...(()) We also know that (Q,,a(0) S + and |1 < B. Now we need to bound ||w.]]- Again, since w, is the exact minimizer, we have WoLo@ M,LL(w,,,,. ,, 0,d") = That is
(4) 2
8,
(1-
Be [ww] Dn.a Qu.a dna] = 0,
which implies
[ (())))) ( B (Qna(0)0s,a)
w.
(Baaaavv (0., Bl (Q.aa (0)os,a)
By the boundness of the feature map || S B and the Q-function [Q).(()) S 1-y- condition (31), we have the minimizer us bounded by
1 and the
(31) B
||..
p(1 7)2
(Qo.a
2
By using the upper bounds of E of (76) can be upper bounded by
3
1Qa. (0)). ||..|| and || the left hand side
E (Q).a(0)
_ 00,0
)2
2
2B²
B*
s, a
(1
7)2
111 7)13
1=2 - 7)
1
B2
2
+
+1
(1 7)2
[1(1 7))
2
B2
#41 - 7) +1
(1 7)²
38

---

Published as a conference paper at ICLR 2023
Thus, in order satisfy (76), choose
1-7 (1(1 (1(1-))) + +1).
V2
B²
Now all the conditions (i) (vi) Theorem are verified. With step size zBz the initialization wo 0 and 7 steps of M- 10-NPG-S00 SGD updates (47), we have
E Wout 0, ] aaqww,0,d0 - T
(ovm + B Bll
4 T
2m
B
B 1el
11l 7)) (1(1-))+1)
1 1-7
7)2
Consequently, Assumption is verified by
2
B
(V2m + 1) + /2m
v Estat S
(1 11-r)vT
111 -)
The proof is completed by replacing the above upper bound of VEstat in the results of Theorem 3.
E PROOF OF SECTION 5
E.1 THE ONE STEP NPG LEMMA
To prove Theorem 4 and the sublinear convergence result of Theorem 9 further in Appendix F, we start from providing the one step analysis of the NPG update.
Lemma (One step NPG lemma). Fix state distribution p; an initial state-action distribution v; an arbitrary comparator policy π². At the k-th iteration, let w argmin L LA(w, g(h), à d()) denote the exact minimizer. Consider the (h) and ((k) NPG iterates given in (32) and (17) respectively. Note
(k) def (x(w(()) _0(k),(00) (0(0)) - La(w! (k) ,000), d(0))
(77)
Sstat
(k) (((k), ( (k) def [A(w approx
(78)
8y def v(()) V²(=*).
p
Assumptions 8 and hold for all K 2 then have that
O (6x41 5x) + 5x
Dj 7)
Dist
VC, (0p (0p 11)
Stat
V
Capprox
(k)
(79)
(1-7)m
1 1-7
Proof. From the three-point descent lemma (Lemma 11) and (17), obtain that for any A(A).
we have
(k))
(b++1)))
D(T ((())) S me (h) (w)) p) D(p, (b)) - D(p, TT (k+1))).
7h
Rearranging terms and dividing both sides by Thk we get
(k) (b) m
(k+1)
-D)
1 D( (k-1) (1)) - -
1
D(p, D(p, (10))
1
D(p, ((p,+((+11) (1++1))..
T/k
Letting = ns (b)
and knowing that
T (k)) (()))
for all l: 0,
which is due to (12), have
())))))))))))) n ((+11) S
D(T (k+1) x1))) (m T (, (((+1))) S 0.
(80)
17k
m
39

---

Published as a conference paper at ICLR 2023
Letting nे yields
( (1+1)
mī) -m;) D(== (b))
1
D " _ ((+1)).
9)
T/s
Note that we dropped the nonnegative term 1 DTTT n
( on the left hand side to the inequality.
Taking expectation with respect to the distribution d², we have
Eg
( ( (R)
(())
(8) Te )|
Bawdt { ( w (k).
T2 -
D D
(81)
For the first expectation in (81), we have
Band
{ w(() T
Σ
(((+t)))
Σ
dz
(1) n (k+1))
de
(k+1)
#ES
(20)
k+1
d
(k+1)
(k) ())) o (k+1)
#ES
(20)4
(k+1)
(8) (1() TT (k+1))
2
EES
LE
(s,a)~d(k11)
( (k)
1 (aa)
A(hi)
+ O (a.. 5.0
(obtt) T wn!k) - A(k))
5,0
-1-)-)
(v(++1)- v(h) + 1 (e
(o(t)) with)
(A)
(82)
2,0
where the last line is obtained by the performance difference lemma (41), and we use the shorthand ((k as (O(k)).
The second term of (82) can be lower bounded. To do it, we first decompose it into two terms. That is,
B((,a)dd(tt)) (o(t)) T (k) AA = E (s.a)
[ (w)(k) - -w!+))
(obtt) T (k) - [A)
+ E (s.a)nd(
(83)
We will upper bound the absolute values of the above two terms 10 and 2 separately. More precisely, similar to the proof of Theorem 3, we will upper bound the first term ① by the statistical error assumption (33) and upper bound the second term |2] by using the approximation error assumption (34).
To upper bound L, we first define the following covariance matrix of the centered feature map
(k) def
T (A) [
(
(84)
2(0)
Here we use the superscript (k) for (k)
to distinguish the covariance matrix of the feature map (k)
d(e)
Ege defined in (60) in the proof of Theorem I, as the centered feature map depends on the iterates ((b)
40

---

Published as a conference paper at ICLR 2023
By Muuchy-Schwarte inequality, we have
!
Σ
[(k+t)
(w)l)) - -w! )
3,0
(s.0)E5xA
I(k+1))
E
((k
((osaa ( -oo---=))) w(()))
dahh
(s.))SXA
(a,a)SSA
dllett)
27
(84)
E (s,a)dd())
(o(N) w (8)
de
(00)
By further using the concentrability assumption 9, we have
C, (o(()) w: 2
|
xy(k)
(A4)
C, (La(w)k), 0(x), - La( ,0(k), _(k))
(85)
(6) Cuestat
(86)
where (85) uses that w. is minimizer of LA and w (k) is feasible (see the same arguments of (62)
(k)
in the proof Theorem l).
For the second term ② in (83), by Gauchy-Schwanl ' inequality, we have
((++1)
(k) T (R) s.a)
A
w
(x.))SxAA
[(k++1) 2 ds
[kk
(4s.a) Wx
A!.ad
((k)
(5,0)E8x.A
(5.0)ESxAA
I)++1 27
E ((
L La(w!*) (k)
,00k), _(0))
iik)
(58+
Cocapprox
(87)
Plugging (86) and (87) into (82) yields
Eged' (o - ( ) 2 01 -)) (vintt)) v2()
- - -ppC, (Velte VCatat +
(k) Capprox
(88)
Now for the second expectation in (81), by using the performance difference lemma (41) in Lemma 3, we have
Eyynd (o(())((()) ,x:)
-B(a.a)-n=> [A(t]] + E( [aSt] - (T(hh) (t)
=(1 7) -1)))))(()-vvleee -v(())))((7' + B(ssa)aan [A! (o(k) wo
(89)
41

---

Published as a conference paper at ICLR 2023
The second term of (89) be lower bounded. We first decompose it into two terms. That is,
B ((aaa)dd [A(t) (dg.d) ww()) R (e.a)add
[A (6
w
6,0
(T(t)) T Tw. (()))
((,,a)ddd"
(90)
Now we will upper bound the absolute values of the above two terms @ and
bb)
separately.
For the first one (+). by Cauchy-Schwarle inequality, we have
dxa 2,a
A
(o w!! (k)
@
(s
(xx
Σ
2,0
Σ
(os,a) Tw
(K)
A2,00
((b
(s,a)
(s.a)ESxA
d
27
E (ssa)
La(w!*) (8)
(al), ,000),
(8)+
Cycapprox
(91)
For the second term b in (90), by Beuchy-Schwarre 's inequality, we have
b
Σ
d'y
(o(t))
( (w! - w(())
(a.0)ESxA
(d
(kk (Bo.d) ((w(k) )
(s,a)ESXA
(Ma)ESXA
ds-- 8.0 [(k]
(84)
B(s,a)dd())
w(()) (())
w
(2)
2(k)
Cr [w(k)
[1)]
(85)
Cv (La(wo(t), 01k), d()) LA (K) 000) d(i)))
V Coeetel
922
Thus, we lower bound (90) by
-Ea-d" (0 (R) (1),),m)))))))))))))
(1))(92)
2
(1 (1-)) (v. (v -V)('))))) Vc, (Vett)
Sead +
V
(k) Capprox
(93)
Substituting (88) and (93) into (81), dividing both side by 1 1- 7y and rearranging terms, we get
Op (5x+1 5x) + 8x 5 (1 7)
Dj
Dit1
VC, (0p 11
(V VVste +
(k) V Capprox
(1 7)=
1-?
42

---

Published as a conference paper at ICLR 2023
E.2 PROOF OF THEOREM 4
To prove Theorem 4, we prove the following general result with any initial policy by knowing that D I log [A| when using the uniform initial policy in (48).
Theorem 8. Fix a state distribution a state-action distribution U, and comparator policy π², We
consider the NPG method (32) with the step sizes satisfying du 2 1-2 Dū and T]+11 2 7k. Suppose
that Assumptions and hold. Then we have for all le 2 0.
E V2((T()) (2(TT) - (1-1) )
2
VC, (U, +1)
+
(v Estat
+v EEaprrox
0p 1 -
1 1-7
Proof. From (79) in Lemma 9, by using the same increasing step size as in Theorem 5, i.e. Y/o 2 7 1- Dj and 7h+1 2 m//7, and following the same arguments in the proof of Theorem 5 after (73), we obtain the final performance bound with the linear convergence rate
E (T)) (i(TT) (1- (1- 8p I --7
1 2
VC, (0p +1) (Vesta + Capprox)
+
1-7
F SUBLINEAR CONVERGENCE OF NPG WITH CONSTANT STEP SIZE
In this section, we provide the sublinear convergence of NPG with arbitrary constant step size. Theorem 9. Fix state distribution p. an state-action distribution u and an optimal policy x². consider the NPG method (32) with any constant step size The 1) >> O. Suppose that Assumptions 7, and hold. Then we have for all 2 0,
Vo(T())) [ -V,(7)))-((7))) - 71
1
VC (Op (O +1) (V + /Eapprxx) DG + +20p)
1-7
Compared to Theorem 2, again here we require n" to be an optimal policy for the same reason as indicated in Footnote 5. Furthermore our sublinear convergence guarantees for both Q-NPG and NPG are the same. Compared to Theorem 29 in Agarwal et al. (2021), the main differences also similar to those for Q-NPG as summarized right after Theorem 2: our convergence rate improves from (L)VV)) to (11kk); they use a diminishing step size of order O(L/Vk) while we can take any constant step size we want.
Despite the difference of using (k) instead of (A) for the compatible function approximation (k(w()) g(k), / (,))),, notice that same sublinear convergence rate ((1/k) /)) is established by Liu et al.
(2020) for NPG with constant step size, while their step size is bounded by the inverse of a smoothness constant and they further require that the feature map is bounded and the Fisher information matrix (9)
strictly lower bounded for all parameters E R (see this condition later in (94)). With such
additional conditions, we are able to provide Ö ((=))))) Appendix G.
sample complexity result of NPG in
Proof. From (79) in Lemma 9 with the constant step size, we have
0p (5t-1 5k) 0g < (1- (1 11-29 7)
D Ditt
Vo (0,
(1p+1)
(V
(K) Stat
V
(k) Capprox
1-7
43

---

Published as a conference paper at ICLR 2023
Taking the total expectation with respect to the randomness in the sequence of the iterates w((), (((11) yields
E D
E
D
0, (E [0x+1] [6x]) + 10 [6&]
7)n
(1
7)17
VC (0p + 1)
(A)
V
(A) Eapprox
E
+ E
Estat
E [
E D
7)m
(1 (1-7)m
Vo (0p +1
I (k)
stat
+
Capprox
1-Y
(3)++))
E [D
E [D(
(1 7/1
(1-98 (1-7)m
v To (0p + 1)
(Vestat
Capprox
1-7
By summing up from 0 to ks get
D
VC (0, (0p +1)
[
+ 0,00 k.
(Vestat +
Veapprox)
(1 (1-3)n
1 1-7
Finally, dropping the positive term E [6x] on the left hand side as n² is the optimal policy and dividing both side by & yields
[o)] Vo((T) S (1 7)nk (1 (1-7)) 7)k
D
20p
VC, +1p+1) (VEsta + VEapprox).
E
+
+
k
1-7
G SAMPLE COMPLEXITY OF NPG
Combined with a regression solver, NPG-SGD Algorithm 5, which uses a slight modification of Q-NPG- SGD for the unbiased gradient estimates of LA. consider sampled-based NPG Algorithm proposed in Appendix and show its sample complexity result in the following corollary.
Corollary 3. Consider the setting of Theorem 8. Suppose that the sample-based NPG Algorithm I is run for K iterations, with T gradient steps of NPG-SGD (Algorithm 5) per iteration. Furthermore, suppose that for all (s, a) E S x A, we have [ ll S B with B > 0, and we choose the step size zhz and the initialization Wo = 0 for NPG-SGD, ffr all 0 E R", the covariance matrix of the centered feature map induced by the policy T0) and the initial state-action distribution v satisfies
E E(s.))=á T (f)(o,,a 2 pmm.
(94)
where Im E |Rmx is the identity matrix and p 0, then
E [[ - Vx(T))
K
2
(0, + 1) Vreapprox
+
1/
1-y
1
1-?
4vC,
(1,+
+ 1)
(2B2
(v2m+1) + 22m
(1 (1=2)2VT
/1
Now compare Corollary 3 with Corollary 33 in Agarwal et al. (2021), which is their corre- sponding sample complexity results for NPG. The main differences between Corollary 3 and Corollary 33 in Agarwal al. (2021) are similar to those for Q-NPG as summarized right after Corollary 1:
Their sample complexity is O (1.)) while ours is Ō (1-1)² ); they consider projection
44

---

Published as a conference paper at ICLR 2023
step for the iterates and incorrectly bound the stochastic gradient due to similar enror indicated in Footnote (and see Appendix G.1 for more details), while we assume Fisher-non noader-non-deeeeracyy (94).
Compared to Corollary 1, the sample complexities for both Q-NPG and NPG the same. The assumption (94) on the Fisher information matrix is much stronger than (31), as (31) is independent to the iterates. However, despite the difference of using instead of p. the
(94) is
commonly used in the optimization literature (Byrd et al., 2016; Gower et al., 2016; Wang et al., 2017) and in the RL literature (Liu al., 2020; Ding et al.. 2022; Yuan al., 2022). It characterizes that the Fisher information matrix behaves well as a preconditioner in the NPG update (8). Indeed, (94) directly assumed to be positive definite in the pioneering NPG work (Kakade, 2001) and in the follow-up works on natural actor-critic algorithms (Peters & Schaal, 2008; Bhatnagar et al., 2009). It satisfied by a wide families of policies, including the Gaussian policy (Duan et al., 2016; Papini et al., 2018 8; Huang et al., 2020) and certain neural policy with log-linear policy as a special case. We refer to Liu et al. (2020, Section B.2) and Ding et al. (2022, Section 8) for more discussions on the Fisher-non-degeneerat setting.
To prove Corollary 3, our approach is inspired from the proof of the sample complexity analysis of Liu et al. (2020, Theorem 4.9). That is, we require the Fisher-non-degeneraay (94) and apply Theorem 12 to the minimization of function (w 0 d without relying the boundedness of
the stochastic gradient. A proof sketch is provided in Appendix G.I. Compared to their result, they obtain worse O
(1(11)))))) ( sample complexity for NPG due to slower (11/k) convergence rate.
G.1 PROOF OF COROLLARY
There is similar remark for the proof of Corollary 3 to the one right before the proof of Corollary 1 in Appendix D.5. We notice that there the same error occurred for the proof of NPG sample complexity analysis in Agarwal et al. (2021). Recall the stochastic gradient of LA in (44)
@ A. 0, dd) 2 (w" (wTT (0,a(0) A,,a(0)) Φs.a(0). (0).
turns out that L. 8, dd) is unbounded, since the estimate As, of As.a can be un- bounded due to the unbounded length of the trajectory sampled in the sampling procedure, Algo- rithm 4. Thus, Agarwal et al. (2021) incorrectly verify VL 0 dd) bounded by claiming that As, is bounded by 1-yy
Proof sketch. Despite the difference of using either do or d in the loss function LA, we use the same assumptions of Liu et al. (2020), i.e., the Fisher-non-degennracc (94) and the boundedness of the feature map, and verify all the conditions of Theorem 12 without relying on the boundedness of the stochastic gradient. In particular, similar to the proof of Corollary 1, we verify that EE [A... (
is bounded even though A.. (0) is unbounded. To verify the condition (vi) in Theorem 12 in our proof, we use the same conditional expectation argument as in the proof of Corollary I to separate the correlated random variables As,a (0) and a (f) with (s, a) d appeared in the stochastic gradient. Thanks to this argument, we fix flaw in the previous proof of Liu et al. (2020, Proposition G.1)? 7,
Proof. Similar to the proof of Corollary 1, we suppress the subscript k. First, the centered feature map is bounded by ()..a())) (0)ll s 2B. In order to apply Theorem 12, it remains to upper bound
In previous version of the proof in Section G, Liu et al. (2020, Proposition G. I) use the incquality
E[(ā... w, Tz.a (0))² S..a (0) (o..a & E[( (0) w. á..a (0)) (0) J]
which is incorrect since A. (8) and (9) are correlated random variables. To fix it, we use the following conditional expectation computation argument
(0) w. δ..a (0)) (Ā..a (0)) 1 (A, -w. (.))) 8, a] Φ..a (O) (0)) J.
and bound the term I (A.... (0) w. T. (0)) | s, in (95).
45

---

Published as a conference paper at ICLR 2023
E - H (0) 8, E (0) 8,a
and ||oe|l with w, E argmin LA(w: 0, and find such that (Aea(() - w.
(95)
2 2A,,a(0)un 2s.a (0) + (w. (o))()))² 0²
(96)
holds for all (8,a) E S x A and 0 E R
Similar to the proof of Corollary the closed form solution of wi can be written as
W. (E(oaa)nd (0=a(0))..0(0) E (eaano [0,,a (0))
From (94), we have
2B
|w+1l 5 H(l -7)"
Now we need to upper bound IE
(A)ra(0)
3,a
from (95). Indeed, by using Ae,
Q.)(()) (0) Vo))), we have
())aa()) 1 8,a
(Qna(0))
18.0 + 2F (Prac()) 8,
2E
(74)
(97)
(1 7)-
where the last line is obtained, as (Pesa(0) 8, shares the same upper bound (74) of
(Qaa(o)) s, a by using the similar argument.
From (97) and (0) & 2B, we verify || (0))a00)))) bounded as well.
2 By using the upper bounds of ( (Ae.a (0) the left hand side of (95) is upper bounded by
|lw.ll. aA)a 2 and (0)] s $2B,
8,
(Aa.a w. Ten (0)) 18
8
16B2
16Ba
E
x
+
(1
7)2
M1
7)2
112
7)2
4
2BB
+
+1
(1 7)2
11
(BB +1
2
(1 7)2
Thus, choose
2 2
+1
7
Now all the conditions (vi) in Theorem 12 are verified. The reminder of the proof follows that of Corollary 1.
H DISCUSSION ON THE DISTRIBUTION MISMATCH COEFFICIENTS, THE CONCENTRABILITY COFFFICIENTS AND THE INCREASING STEP SIZE
We have already mentioned in the comparison with Agarwal et al. (2021) right after Theorem that, although we have linear convergence rates, the magnitude of our enror floor worse (larger) by factor of 0, / (9,VC, for Theorem 3 and 4), due the concentrability C, and the distribution
46

---

Published as a conference paper at ICLR 2023
mismatch coefficients v. used in our proof. Such difference comes from different nature of the proof techniques. Here the distribution mismatch coefficients 1 and the concentrability coefficients Cp and C2 are potentially large in our convergence theories. We give extensive discussions them, respectively. We also provide further noteworthy observations about the connection between the use of the increasing step size and the policy iteration.
Distribution mismatch coefficients Dr. Our distribution mismatch coefficient 10p in (20) is the same the one in Xiao (2022). contains both an upper bound and lower bound. The linear convergence rate in our theories is 7 > O. Thus, the smaller d is, the faster the resulting linear convergence rate. The best linear convergence rate is achieved when 8, achieves its lower bound. Here our analysis is general that it includes all the distribution mismatch coefficient 8, induced by any target state distribution p. Our results generalizes and sometimes also improves with respect to prior results.
very pessimistic and trivial upper bound on 0p is
1
0r S (1 (1-7)Pmin
However, if the target state distribution P E A(S) does not have full support, i.e., Ps 0 for some 8 E S, then dp might infinite from this upper bound. Xiao (2022) just assumes that 1) is finite. We further propose solution to this particular issue. Indeed, if does not have full support, consider x² as an optimal policy. We can always convert the convergence guarantees for some state distribution p' E A(S) with full support, ie., p'a > 0 for all S as follows:
(x(m(()) VO(T')) = Σn Ps
(1)(T(())
V.(TT))
Σ
Ps #ES Pg
Ps (V)( Vo(Ttt)
SES
d p
Σ ps (va(=(+)) -V((+())-V/((T))) = dES
(vo( - (x*)) pz
p
$
Then only need convergence guarantees of Vp (x) (T(")) for arbitrary p' obtained from all our convergence analysis above. In this case, the linear convergence rate depends on
1
d
p
OX.
1
Equation (20) provides the lower bound --y for 0p- Such lower bound can be achieved when the
target state distribution P satisfies that p d= (p) where n² is optimal policy. The advantage of this case is that, not only it implies the best linear convergence rate, more importantly, the fast
linear convergence rate is known be 7. So know the convergence rate explicitly without any estimation, even though the optimal policy or the policy iterates are unknown before training. Hence, we know when to stop running the algorithm. Lan (2022) only considers the case when p = d (p) and able recover the same linear convergence rate y in their result.
Furthermore, the convergence performance (x))) Vx(T*) depends on the target state distribution
p. If the optimal policy n" independent to the target state distribution p which is usually the case RL problems, then we are always allowed to fix p = d= (p) for the analysis without knowing and x² and derive this best linear convergence performance with rate y, because we use the initial state-action distribution y/ in training which is independent to p.
Finally, from (20), if ((() converges to d', then Dg converges to This might imply superlinear convergence results as Section 4.3 in Xiao (2022). In this case, the notion of the distribution mismatch coefficients 9, no longer exists for the superlinear convergence analysis. In other words, it is no longer concerned.
Concentrability coefficients C.. The issue of having (potentially large) concentrability coefficients is unavoidable in all the fast linear convergence analysis of the inexact NPG that we aware of, including even the tabular setting (c.g.. Lan (2022) and Xiao (2022)) and the log-linear policy setting (Cayci et al. (2021), Chen & Theja Maguluri (2022) and ours).
47

---

Published as a conference paper at ICLR 2023
First, in the fast linear convergence analysis of inexact NPG, the concentrability coefficients appear from the errors, including the statistical error and the approximation error. Thus, one way to avoid having the concentrability coefficients appear is to consider the exact NPG in the tabular setting (See Theorem 10 in Xiao (2022)) Because the tabular setting makes no approximation error and the exact NPG makes no statistical error. We consider the inexact NPG with the log-linea policy. Consequently, we have the concentrability coefficients multiplied by both the statistical error Estat and the approximation error (Ebias in Assumption Eapprox in Assumption 5 and 8).
To remove the concentrability coefficients, one has to make strong assumptions on the errors with the To supremum norm. In the tabular setting, Lan (2022) and Xiao (2022) assume that [[{( Q(T)]loo S Cstat- The cons of such strong assumption requires high sample complexity and already explained in Appendix A.I. In the log-linear policy setting, Chen & Theja Maguluri (2022) assume that (0(k)) uu. ( se S <bias for the approximation error, which is very strong assumption in the function approximation regime. Due to the supremum norm, 6bias is unlikely to be small, especially for large action spaces. Under this strong assumption, Lan (2022), Xiao (2022) and Chen & Theja Maguluri (2022) are able to eliminate the concentrability coefficients. To avoid assuming such strong assumptions, Cayci et al. (2021) and our paper consider the expected L2 errors in the log-linear policy setting, which are much weaker assumptions, especially much more reasonable for the approximation error Cbias compared to the one in Chen & Theja Maguluri (2022). The tradeoff is that, the concentrability coefficients can not be eliminated in this case both in Cayci et al. (2021) and our results.
Furthermore, as mentioned right after Theorem 4, under the expected error assumptions (Assumption 7 and 8), our concentrability coefficient C₁ is better presented than the one in Assumption 2 in Cayci al. (2021) in the sense that it is independent the policies throughout the iterations thanks to the use of (R) instead of (R) (which is mentioned in Remark I as well) and controllable to be finite by v, while the one in Cayci et al. (2021) depends on the iterates, thus is unknown and is not guaranteed be finite.
Finally, like the distribution mismatch coefficient, the upper bound of C2 in (30) is very pessimistic. By the definition of C2 in (28), one can expect that Cp is closed to 1, when n. (k) and 7 (6+1) converge to n² with n² the optimal policy.
So our concentrability coefficient Cp is the "best" one among all concentrability coefficients in the sense that, it takes the weakest assumptions on errors compared Lan (2022), Xiao (2022) and Chen & Theja Maguluri (2022), it does not impose any restrictions on the MDP dynamics compared to Cayci et al. (2021) and it can be controlled to be finite by v when other concentrability coefficients are infinite (Scherrer, 2014).
It is still an open question whether we can obtain fast linear convergence results of the inexact NPG in the log-linear policy setting, with small error floor and a much improved concentrability coefficient, e.g. as the same magnitude as the one in Agarwal et al. (2021).
Increasing step size and the connection with policy iteration. As for the use of the increasing step size, intuitively, the reason is that both NPG in (17) and Q-NPG in (16) behave more and more like policy iteration. For instance, when Te - oo and we replace the linear approximation t &.ud (k) by Q, (0(%)), (16) becomes
(k+1) arg min pEA(A) ((0.(00)))) p)) As E,
which is exactly the classical Policy Iteration method (e.g., Puterman, 1994; Bertsekas, 2012). We refer to Xiao (2022, Section 4.4) for more discussion on the connection with policy iteration.
I STANDARD OPTIMIZATION RESULTS
In this section, we present the standard optimization results from Beck (2017); Xiao (2022); Bach & Moulines (2013) used in our proofs.
First, we present the closed form update of mirror descent with KL divergence on the simplex. We provide its proof for the completeness.
48

---

Published as a conference paper at ICLR 2023
Lemma 10 (Mirror descent the simplex, Example 9.10 in Beck (2017)). Let g R" which will often be a gradient and let rj > O. For p. in the unit n-simplex A", the mirror descent step with respect the KL divergence
min PEA"
7 (g.p) D(p,9)
(98)
is given by
9
(99)
E 9:0 79
where O is the element-wise product between vectors.
Proof. The Lagrangian of (98) is given by
L(, A) - (9. D(p.g) p(1 Σ p.)
XpPs
where 1 E and X e R" with non-negative coordinates are the Lagrangian multipliers. Thus the Karush-Kuhn-Tuckee conditions are given by
79 + log(p/g) //) + 1, pln + X,
1, p 1,
X; = or p; = 0,
for all i 1, 1,...
where the division p/q is element-wise. Isolating p in the top equation gives
p = q c 1)1, + n0 e= q 3 e ng
Using the second constraint 1, gives that
1
1 = ct-
q: n9:
E qie n88
Consequently, by plugging the above term into p, have that
p 9 e n9
E 9-. 79
remains to determine A. If q: = then pj = and thus X > 0. Conversely, q. > 0 then pt > and thus In either of these cases, have that the solution given by (99).
Now we present the three-point descent lemma on proximal optimization with Bregman divergences, which is another key ingredient for PMD analysis. Following Xiao (2022, Lemma 6), adopt slight variation of Lemma 3.2 in Chen Teboulle (1993). First, we need some technical conditions.
Definition 10 (Legendre function, Section 26 Rockafellar (1970)). We say a function is of Legendre type Legendre function if the following properties satisfied:
(i) h is strictly convex in the relative interior of dom h, denoted as rint dom h.
(ii) h is essentially smooth, i.e., h is differentiable in rint dom h and, for any boundary point Tbb of rint dom h, lim [[)(2)] + oo where I E rint dom h.
Definition 11 (Bregman divergence (Bregman, 1967; Censor & Zenios, 1997)). Let h dom h IR
be a Legendre function and assume that rint dom is nonempty. The Bregman divergence Dj (---) dom h x rint dom h [0, oo) generated by a distance-like function defined as
D'(p.p') def h()) - Mp') - (Vh(p'.pp-
(100)
Under the above conditions, we have the following result. We also provide its proof for self- containment. (Xiao (2022) does provide formal proof.)
49

---

Published as a conference paper at ICLR 2023
Lemma 11 (Three-poile prrree-ppintteeo decent lemma, Lemma 6 in Xiao (2022)). Suppose that C T is closed convex set. f - R is a proper. closed convex function, Da(:.-) is the Bregman divergence generated by function h of Lengendre type and rint dom h nc 0. For any rint dom h, let
xt
arg
min dom
{f((u) + Dn(u,x)).
Then xt rint dom h NC and for any E domh nc,
[(**) + Da(x* .x) S f(u) + Dx(u, Dn(u,=*).
Proof. First, we prove that for any a, rint dom and E dom h, the following identity holds:
(a(c, + Da b) Dj, (c, () (Vh(b) c a)
(101)
Indeed, using the definition of D (100), we have
(Vh(a), a) h(c) h(a) Dn(c,)) a),
(102)
(Vh(b), b) = =((a) h(b) Dn(a,
(103)
(Vh(b).c -h(c) h(b) (n(c,
(104)
Subtracting (102) and (103) from (104) yields (101).
Next, since is of Legendre type, we have x+ E rint dom n C. Otherwise, x is boundary point of dom h. From the definition of Legendre function, (> )I = which not possible, x is also the minimum point of fu) + Dx x). By the first-order optimality condition, we have
(u-rt.g* V Da(u x)((x=))g==++)) 0,
where 9** E 0f(=*) the subdifferential at * From the definition of Dj. the above inequality is equivalent to
xt Vh(x+) Vh(=)) 2 (x u.g*).
(105)
Besides, plugging e = u, a = + and = x into (101), we obtain
(105)
(u su-x*, Vh(x - Vh(x)) = Da (u, x) Da(u, Du(xt xx) 2 (x - ungtt g+
Rearranging terms and adding [u) on both sides, we have
(,(u, D2 (1, + f(u) f(u)+ (xt u, u ) Dn(xt f(x+) + Du(x=
which concludes the proof. The last inequality is obtained by the convexity of f and g E 0f(xt).
Finally, we use the following linear regression analysis for the proof of our sample complexity results, ie.. Corollary I and 3.
Theorem 12 (Theorem 1 in Bach & Moulines (2013)), Consider the following assumptions:
(i) H. is m-dimenssional Euclidean space.
(ii) The observations (Ins zn) H H are independent and identically distributed.
(ii)
E
|m.1111 and || are finite. The covariance IE [ is assumed invertible.
(iv) The global minimum of f(0) = LE (0, xn. (0, zn) is attained at a certain 0,, E H.
Let En 2n (n) Fy denote the residual. We have EE [E,] 0.
AA convex function is proper if dom f is nonempty and for all dom f. f(x) > -00. A convex function is closed, if it is lower semi-contimnous.
50

---

Published as a conference paper at ICLR 2023
(v) Consider the stochastic gradient recursion defined as
0, = 0n-1 - 11, In 2n),
started from 0g E H. and also consider the averaged iterates dout n+1 Ek= Ok.
1
(vi) There exists R > and > such that [SnST]] I a E T and E ||l 1? annt -
Rº [
When 1) TR we have
2 E (f(ou)) f(0.)) (ovm + R R16 0.11)²
(106)
51


Reviews:
[{"review_id": "vkPNsqXubL8", "reviewer": "Reviewer_Cu4x", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies the geometric convergence of NPG and Q-NPG parametrized by log linear function. The authors assume that approximation of Q-functions by linear function, and approximation of policy with log-linear function has some error bound, and they show that employing NPG or Q-NPG with a geometrically increasing step size results in exponential convergence to a ball around the global optimum. This ball is proportional to these function approximation errors. For the Q-NPG algorithm, the authors state their result under two different set of assumptions, and for NPG, the authors consider one set of assumption. Furthermore, by a standard sample based analysis of their result, the authors show 1/epsilon^2 sample complexity of their algorithm, which matches the best known result for Q-learning. ", "summary_of_the_review": "I believe the paper is a minor extension of the prior work. The different set of assumptions that the authors consider are not all that different. \n---------------------------------------------------------------------------------------------------------------- \nAfter reviewing the rebuttal, I believe there are interesting points compared to the prior works. Specifically, the extension of this work compared to Xiao (2022) is not direct, specifically for the sample complexity analysis. I am increasing my score.", "strength_and_weaknesses": "Strength: \n- The authors consider a wide range of assumptions. \n- For these settings the authors establish a geometric rate of convergence, which is superior to the prior work with function approximation\n- The authors establish a tight 1/epsilon^2 sample complexity\nWeakness: \n- Some of the constants, such as C_v, can be arbitrary bad, and might be in the cardinality of state*action space. Appearance of this constant in the upper bound besides the 1/(1-\\gamma), can result in a very poor bound. \n- The contribution of the paper is limited compared to the prior work, specially Xiao (2022). It seems just a direct extension of Xiao (2022) theorem 10 to the linear function approximation, where we through all the errors due to function approximation to a big constant in the upper bound.\n- The error terms appearing on the upper bound of Theorem 4.7 can be very loose. In particular, we have a very bad dependency in terms of 1/(1-\\gamma). Can the authors comment on (possible) lower bounds of NPG or Q-NPG in terms of 1/(1-\\gamma)?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "s2q-TCYy0F5", "reviewer": "Reviewer_sgtm", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper considers infinite-horizon discounted Markov decision process with finite state and action space. By re-formulating the natural policy gradient (NPG) and the Q-NPG methods as approximate versions of the policy mirror descent (PMD) method, the paper shows that both methods enjoy linear convergence rates and \\tilt{O}(1/{\\epsilon}^2) sample complexities with the help of the compatible function approximation. ", "summary_of_the_review": "The paper has improvement in terms of demonstrating the linear convergence rate of the natural policy gradient (NPG) and the Q-NPG methods with the log-linear policy for the linear function approximation setup in the infinite-horizon discounted Markov decision processes. However, the efforts are incremental considering the previous works on the policy mirror descent result on tabular setting as well as the linear function approximation used in similar settings.", "strength_and_weaknesses": "Strength:\n  The paper shows the both the natural policy gradient (NPG) and the Q-NPG methods have linear convergence rate and \\tilt{O}(1/{\\epsilon}^2) sample complexities, which is an improvement to the limited tabular setting shown in the previous works.\n\nWeakness:\n  Although the result is new and is an improvement to the existing literature, the technics it uses are very incremental to the existing tabular setting one. By using linear function approximation and reformulating the resulted update rules as approximate versions of the policy mirror descent (PMD) method, it's very incremental to demonstrate the linear convergence rate results in this paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "8eK1PwpIJl", "reviewer": "Reviewer_yaHy", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper studies the analysis improvement of existing policy gradient methods. The authors apply the recent new analysis of policy mirror descent to natural policy gradient methods ( and its Q-based version ) under log-linear policy class. The provided convergence results improve the state-of-the-art rates, using either adaptively increasing stepsize or constant stepsize. The authors also present a sample-based algorithm and sample complexity which improves previously-known results in the same setting. ", "summary_of_the_review": "The paper studies the natural policy gradient methods ( and its Q-based version ) under log-linear policy class by applying the recent new analysis of policy mirror descent. The established convergence rates improve the state-of-the-art rates using either adaptively increasing stepsize or constant stepsize. However, due to the problem/algorithm-dependence, it is not very clear how useful these convergence rates are in practice. The authors also present a sample-based algorithm and sample complexity which improves previously-known results in the same setting. The paper hasn't supplied empirical evidence to demonstrate the practical use of the provided theory. \n\n============================\n\nPOST-REBUTTAL. Thank you for your response. Since my concerns are addressed in the new draft, I am inclined to recommend acceptance. The score has been updated. ", "strength_and_weaknesses": "**Strengths**\n\n- The paper studies log-linear policy class for natural policy gradient methods. This linear function approximation setting is important since it is a basic case of widely-used policy gradient methods using general neural policy parametrization\n\n- The authors employ the policy mirror descent analysis from Xiao, 2022 in the tabular case to analyze the log-linear version of natural policy gradient methods in the function approximation setting. This optimization perspective is meaningful to practical RL methods since it offers a more careful characterization of problem-dependent parameters and algorithm stepsizes. \n\n- The established convergence results improve the results from Agarwarl et al. 2021 from sublinear convergence to linear convergence (both up to some errors), with new choices of algorithm stepsizes. Achieving fast convergence is beneficial to training RL algorithms with better efficiency.\n\n\n**Weaknesses**\n\n- The established convergence rates depend on the distribution mismatch coefficients and the concentrability coefficients. Since these coefficients either depend on the optimal policy or the policy iterates that are unknown before training, it is hard to estimate them. It is not very clear how useful these convergence rates are in practice. It is useful to discuss how bad the rate could be, e.g., all these coefficients are chosen in the worst way. \n\n- The distribution mismatch coefficient can be very large in large MDPs even when the initial state distribution is uniform. Large distribution mismatch coefficients lead to poor convergence rates and dependence on function approximation errors, simultaneously. It is useful to discuss the reason for this limitation, and the possibility to address it.\n\n- The established theory seems to be unique to the log-linear policy class. It is more useful if the authors could discuss its extension to the general policy class.  \n\n- The paper hasn't supplied empirical evidence to demonstrate the practical use of the suggested theory. Since function approximation is ubiquitously employed in RL, it is useful to provide experimental results as additional support. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "4BaOz3UkhJ", "reviewer": "Reviewer_NuUP", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes linearly converging variants of NPG and Q-NPG methods, with log-linear policy class and compatible function approximation. The convergence results bare a similar spirit as the recent development of policy gradient methods in the tabular setting. In the stochastic setting, the authors establish an $O(1/\\epsilon^2)$ sample complexity by showing an $O(1/T)$ convergence rate for the policy evaluation. Both of these results seem to improve upon previous results on policy gradient (NPG) method in the linear function approximation setting. ", "summary_of_the_review": "I appreciate the technical effort this paper puts into developing new understandings of how natural policy gradient converges with compatible function approximation, yielding a linearly converging policy optimization error and $O(1/\\epsilon^2)$ sample complexity. The analysis bears certain novelty in terms of two perspectives. First, the analysis of policy optimization with compatible and linear function approximation is established, while accounting for both the error in policy evaluation and function approximation error. Second, the policy evaluation analysis exploits a sharper result than the one used in prior literature, which is needed for establishing the $O(1/\\epsilon^2)$ sample complexity. \n\nI believe the paper contains enough new results to the field of policy gradient methods. ", "strength_and_weaknesses": "Strength:\nThe paper is technically correct, and addresses the existing literature sufficiently. In addition to showing an improved convergence rate for the policy optimization, the paper also exploits a faster convergence result for the policy evaluation procedure, which seems the crucial factor in obtaining the final $O(1/\\epsilon^2)$ complexity.\n\nWeakness:\nThe only comment and suggestion that I have is the presentation of assumptions. There are some assumptions that seem less clearly motivated (e.g. Assumptions 3 and 4). Although some of these appear also in prior literature, it would be beneficial to provide some more context on why/where certain assumptions are needed.\n\nMinor comment: The policy evaluation (e.g., Algorithm 6) seems to require the state-action pairs (Line 2, Algorithm 6) to be independent for different timesteps. Can the author comment on the feasibility of using Markovian sampling?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster