Quasi-Newton policy gradient algorithms
Authors: Haoya Li
Samarth Gupta
Hsiang-Fu Yu
Lexing Ying
Inderjit S Dhillon
Venue: ICLR 2022 Submitted (2022)

Abstract: Policy gradient algorithms have been widely applied to reinforcement learning (RL) problems in recent years. Regularization with various entropy functions is often used to encourage exploration and improve stability. In this paper, we propose a quasi-Newton method for the policy gradient algorithm with entropy regularization. In the case of Shannon entropy, the resulting algorithm reproduces the natural policy gradient (NPG) algorithm. For other entropy functions, this method results in brand new policy gradient algorithms. We provide a simple proof that all these algorithms enjoy the Newton-type quadratic convergence near the optimal policy. Using synthetic and industrial-scale examples, we demonstrate that the proposed quasi-Newton method typically converges in single-digit iterations, often orders of magnitude faster than other state-of-the-art algorithms. 

Under review as a conference paper at ICLR 2022
QUASI-NEWTON POLICY GRADIENT ALGORIHHMS
Anonymous authors Paper under double-bling biind review
ABSTRACT
Policy gradient algorithms have been widely applied reinforcement learning (RL) problems in recent years. Regularization with various entropy functions is often used encourage exploration and improve stability. In this paper, we pro- pose quasi-Newton method for the policy gradient algorithm with entropy regu- larization. In the case of Shannon entropy. the resulting algorithm reproduces the natural policy gradient (NPG) algorithm. For other entropy functions, this method results in brand new policy gradient algorithms. We provide a simple proof that all these algorithms enjoy the Newton-type quadratic convergence near the opti- mal policy. Using synthetic and industrial-scale examples, we demonstrate that the proposed quasi-Newton method typically converges in single-digit iterations, often orders of magnitude faster than other state-of Mfate-of-the-ar algorithms.
INTRODUCTION
Consider infinite-horizon MDP (Bellman 1957 Sutton & Barto 2018 M (.r
where is a set of states of the system studied. Is a set of actions made by the agent, is a transition probability tensor with Pa being the probability of transitioning from state to state t when taking action a, r is a reward tensor with r being the reward obtained when taking action is discount factor. Throughout the paper, the state space S and the action space A are assumed to be finite. A policy π is a randomized rule of action-selection where T denotes the probability of choosing action a at state s. For a given policy x, the value function
state and 0 <
Ux defined as
(v*)s = E
=
k=0
satisfies the Bellman equation:
(I - 7P>u Tx:
where (P=)at = n. Pa. (r+),=E, m2r2. and is the identity operator.
In order to promote exploration and enhance stability, one often regularizes the problem with a function h such the negative Shannon entropy (h=)s Ea # log mg. With h, the original reward ra is replaced with the regularized reward F coefficient and (2) becomes
The where 7 is the regularization
(1 (1- - where we overload the notation for the regularized value function. Other continuously differen- tiable entropy functions be used as well, probability matrix, (I -- >P>) ) is invertible, and
Th
will show later. Since 7 < 1 and P, is transition
Uz = (T 7P) (r= Tha)
(4)
In a policy optimization problem, we seek policy æ that maximizes T U, for some (in fact arbi- trary) positive weight vector E IR.. 91, Using (4), the problem can be stated
max T([ - (P- -h
(5)
This problem can be solved by, for example, the policy gradient (PG) method. However, the vanilla PG method converges quite slowly. In Agarwal et al.) (2020), for example, the vanilla PG method is shown to have 011 convergence rate, where T denotes the number of iterations. For the

---

Under review as a conference paper at ICLR 2022
PG method with entropy regularization and some of its variants, the convergence rate be im- proved to O(e <T), i.e. linear convergence (Mei et al. 2020), which can still be slow since is in general close to 0. It is also demonstrated in numerical examples that these algorithms with linear convergence rate can suffer from slow convergence. For example, in the example in Zhaa et al.) (202T), thousands of iterations are needed for the algorithm to converge, even though the model is relatively small and sparse. Therefore, there is a clear need for designing new methods with faster convergence and one idea is take the geometry of the problem into consideration. The Newton method, for example, preconditions the gradient with the Hessian matrix and obtains second-ored -oddr local convergence. Since the exact Hessian matrix is usually too computationally expensive to ob- tain, the quasi-Newton type methods, which use structurally simpler approximations of the Hessian instead, are more widely used in generic optimization problems, and are known to enjoy superlinear convergence (Rodomanov & Nesterov 2021a b).
1.1 CONTRIBUTIONS
In this paper, we investigate the quasi-Newton approach for solving 55) The main contributions of this paper are the following.
First, we present unified quasi-Newton type method for the policy optimization prob- lem. The main observation is to decompose the Hessian as a sum of a diagonal part and a remainder, where at the optimal solution the remainder part vanishes so that the Hes- sian becomes diagonal. This inspires us to use only the diagonal part in the quasi-Newton method. As a result, the proposed method not only leverage the second order information but also enjoys low computational cost due to the diagonal structure of the preconditioner used. When the negative Shannon entropy is used, this method reproduces the natural pol- icy gradient (NPG) algorithm. For other entropic regularizations, this method results in brand new policy gradient algorithms.
Second, we analyze the convergence property of the proposed quasi-Newter algorithms and demonstrate local quadratic convergence both theoretically and numerically. By leveraging the quasi-Newton framework (Dennis & Moré 1974), we provide simple and straight- forward proof for quadratic convergence near the optimal policy. In the numerical tests, we verify that the proposed method leads to fast quadratic convergence even under small regularization and large discount rate (close to 1). Even for industrial -ize problems with hundreds of thousands states, the quasi- method converges in single-digit iterations and within few minutes on a regular laptop.
1.2 BACKGROUND AND RELATED WORK
A major workhorse behind the recent success in reinforcement learning (RL) is the large family of policy gradient (PG) methods (Williams 1992. Sutton et al.] 1999), for example, the natural policy gradient (NPG) method [Kakade] 20001), the actor-critic method (Konda & Tsitsiklis) (000), the asynchronous advantage actor-critic (A3C) method (Mnih et al.) 2016), the deterministic policy gradient (DPG) method (Silver et al. 2014), the trust region policy optimization (TRPO) (Schulman let al. 2015a), the generalized advantage estimation (GAE) (Schulman et al. 2015b), and proximal policy optimization (PPO) (Schulman et al. 2017). mention but few. The NPG method is
known to be drastically faster than the original PG method, intuitively because in the NPG method the policy gradient is preconditioned by the Fisher information (an approximation of the Hessian of the KL-divergence) matrix and fits the problem geometry better. This idea is extended in TRPO and PPO where the problem geometry is taken into consideration via trust region constraints (in terms of Kl--divergence) and clipping function of the relative ratio of policies in the objective function, respectively. These implicit ways (in the sense that they do not adjust the gradient by an explicit preconditioner) of adjusting the policy gradient is in essence similar to the mirror descent (MD) method (Nemirovskij & Yudin 1983) in generic optimization problems.
This similarity in addressing the inherent geometry of the problem is noticed by a line of recent work including Neu et al. (2017); Geist et al. (2019): Shani et al. ) Tomar et al. (2020); Lan (202T), and the analysis techniques in MD methods have been adapted to the PG setting. The connection was first built explicitly in Neu et al. (2017). The authors consider a linear program formulation where the objective function is the average reward and the domain is the set of stationary state-action
2

---

Under review as a conference paper at ICLR 2022
distributions, in which case the TRPO method can be viewed approximate mirror descent method and the A3C method as an MD method for the dual-averaging (Nesterov) 2009) objective. As a complement, Geist et al. (2019) considers an actor-critic type method where the policy is updated via either regularized greedy step or an MD step and the value function is updated by a regularized Bellman operator, which also includes TRPO as a special case, and error propagation analysis is provided. In |Sann et al. (2020), an adaptive scaling that naturally arises in the policy gradient is applied to the proximity term of the MD formulation, and sublinear convergence result is proved with properly decreasing learning rate. In Tomar et al. (2020), the application to the non- tabular setting is enabled by parameterizing the policy and applying MD to the policy parameters, and the corresponding sublinear convergence result is presented.
Regularization, a strategy that considers the modified objective function with an additional penalty term on the policy, is another crucial component in the development of PG type methods. Intu- itively, regularization is able to encourage exploration in the policy iteration process and thus avoid local minima. It is also suggested (Ahmed et al. 2019) that regularization makes the optimization landscape smoother and thus enables possibly faster convergence. Linear convergence result is then established for regularized PG and NPG methods (Agarwal et al. 2020 Mei et al. 2020 Cen al., 2020). In these relatively earlier works (Agarwal et al.] 2020; Mei et al., 2020; Cen et al. 2020), the regularization usually takes the form of (negative) entropy relative entropy. In the more re- cent work Lan (2021) and (Zhan et al.] (2021) that follow the MD type methods, the regularization extended to general convex functions with the resulting Bregman divergences different from the KL-divergence and linear convergence is guaranteed as well.
However, most of these algorithms are of either sublinear or linear convergence except the entropy regularized NPG with full step length (which is special case of the quasi-Newton method we propose), and even the linear convergence rate O(e=(T) can be slow since e can be close to zero. This motivates us to invent the quasi-Newton policy gradient method to be introduced in Section 2
QUASI-NEWTON METHOD
This section derives the quasi-Newton method for the entropic-regularized policy optimization prob- lems. In this paper, we use more general definition of the term "quasi-Newton method"". Unlike classical quasi-Newton methods where the approximate Hessian matrix is constructed using first- order information, the proposed quasi-Newton method uses second-order information, but the ap- proximate Hessian matrix remains simple and its inverse is easy to obtain. We start with the negative Shannon entropy (hx), En Tÿ log TT.
In what follows, assume that x² is the optimizer of the problem stated in (5. By introducing 2n := I - px, the objective function can be written
F(x) = TT(( (T 7Px) (ra -hha) = e 7 (rx - -Thx) = wi (ra Tha):
(6)
where Wa = Te. e. For any with Ea c = 0. introduce E TRIls| and 2. (Ss) such that
(re)s: = Eara (Ze)st Σ (6 - PPa),
where 8,, = 1 if L and 8,, otherwise.
Let us first outline the main idea of the quasi-Newton method. The gradient of F(T)) in RIS||A| is
aE = (r2 - (log +1 - + co)
(7)
where c2 is the Lagrange multiplier associated with the constraint Σ. x = 1. Our key observation decompose the Hessian matrix ((m) in || into two parts
D² = [T) + HT),),
(8)
where A is a diagonal matrix given by H (sa) = - T5 ((o) (16)) (Mr and H, is a remainder that vanishes n², i.e., H. O(I n= (shown in Theorem With this decomposition,
3

---

Under review as a conference paper at ICLR 2022
approximate the Hessian matrix D²E((T) by H and obtain the following quasi-Newton flow:
dr
aE
- 10 - -HL (Hss)))(ss) Ong
di
mr - 7 ; + 1) |1/ - -p + cc)/T,
By introducing the parameterization 0g = log म and discretizing in time with learning rate we arrive at
0 + -- [[1 y y + c,)/T (1 n)) Writing this update back in terms of .. leads to the following update rule
exp(n(r + (r)))))
This result is summarized in the following theorem with the proof given in Appendix A
Theorem 1. Let h E IRSS be the negative Shannon entropy (ha)s = E. T5 log T.. (a) For any e with E. c 0 and eggl T.. at n
Te - E - Z.Z=' (r Tha) = O,
99)
where D E [RSSIISIIAA] is the gradient matrix of ha with respect to (b) There exists diagonal approximation (T)) of the Hessian matrix 1)2 F.(T)) such that
H(T)) DD- D²) O[| --"
(c) The quasi-Newton flow from H(T) is
dm
T T(log _ + - t.)/
(10)
di
With learning rate T, the gradient update is
exp((n (2P"))))
TT's (1) exp(m(rz +
(11)
Remark 1. The policy update scheme is the same as the entropy regularized natural policy gradient scheme in Cen et al. (2020).
The conclusion in Theorem can be extended to general entropies of the form
(hm)s = Σ Φ
T
Ha:
where & is convex on +00) and d(1) 0, and j is prior distribution over A. The term (hz), is also called the "f--ivergence" between m, and μ (Rényi 1961 Ali & Silvey
1966). In log x,
what follows, we shall use the uniform prior unless otherwise specified. When Φ(z)
mo ( (hx), Ea log
M4 = E. Th log T
log 지 and by omitting the constant log ІА we
recover the regularization used in Theorem When d(x) - (1-1(11-))a0) (a < 1),
4 (h+), LA[(1 - a²) Σa (|AImg)
(12)
the a-divergence. In particular, when -2 -2 V after omitting the constants and dividing by 2, and when - -1 we obtain the 1 reverse-Fe KL divergence (ha)a = i Σ. log .ड after omitting constants.
we obtain the Hellinger divergence (hz))
In the following theorem, we extend the quasi-Newton method in Theorem to the entropy functions described above. The proof of this theorem can be found Appendix B
Theorem 2. Assume that T² is the optimizer of (5) where lor denotes the o-divergence [12.. Then (a) the Hessian matrix 2 E((T) be approximated by diagonal matrix ( near n² such that
4

---

Under review as a conference paper at ICLR 2022
(())) -[]==))))0[[00)0 and (b) the quasi-Newton method from (T) (the policy gradient ascent preconditioned by (T) is
-
1-a ( -
T с (1 (1-)))))))
(13)
where < S 1 is the learning rate and with paramcterization 0% = o' (((AA(=)) the update scheme above can be expressed
8% - 1rr - -1(I - -PP")o + +
(14)
where ((x)) = 1-a= constraint Eo To 1.
x (1+4))22) (a 1) and Cs the Lagrange multiplier introduced by the
Remark 2. When
(the Hellinger divergence), the corresponding update scheme is Teg
WAAl(( - 111 7P unns)/ co -2
which can be obtained by inserting or When -1 (the reverse-KL. divergence), the corresponding updote scheme is TT <-
which can be obtained by inserting = -1 Remark 3. When a different prior μ is used, the corresponding algorithm can be obtained by
(rA - [[I - jonll-/")
inserting 0% = = / in (14)
Remark 4. All the policy update schemes can be extended to the case where = and the MDP has terminal state 8r and the Markov chain irreducible. that case we can remove 8T from S and replace with 1 in the update schemes. For example, the update scheme (T) becomes
TT f (=g)²- + (P)o)))))
(x(=t) + (P"))).))
where P is the submatrix of P with the row and column corresponding to removed.
The remaining problem in the update schemes above the determination of the multipliers c., since
they cannot be solved explicitly as in the case of the negative Shannon entropy (Theorem D The determination of c2 can be done in a similar way as Ying (2020) based on the following lemma.
The proof of this lemma can be found in Appendix C
Lemma 3. Assume that < 0, then for any 21, T2. tion:
Th. there is a unique solution to the equa-
(xc 2 + + (x +2,) =
(15)
such that + xz 2 0. i- 1,2,.... k. Moreover, the solution is the interval
max {- min 24, k a- max Tj Isick
, k 1/6 min x; Isick
(16)
15iSk
By Lemma] and the monotonicity (a + ( + numerical methods (e.g. bisection) for nonlinear equations can be applied to determine the solution for (15). This routine can be used find the multipliers c, as stated Proposition 4 whose proof is given in Appendix]] D
xx) many of the established
Proposition 4. The multipliers Ca in the update scheme (13 can be determined uniquely such that the updated policy x satisfies कद 0 for any (s,a), and T for any
The algorithm proposed in this section is summarized in Algorithm beloow
3 QUADRATIC CONVERGENCE
In this section, we study the quadratic convergence of the quasi-Newton method at learning rate
77 = 1. Our analysis is inspired by the results in Dennis & More (1974); Wang & Yan (202I). The following theorem states the second-order convergence when = 1, with the proof given in Appendix
5

---

Under review as a conference paper at ICLR 2022
Algorithm Quasi-Newton method for the regularized MDP
Require: the MDP model MM- = (S, A, P. 7), initial policy Tinit, convergence threshold étols reg- ularization coefficient learning rate 7), the regularization type (KL, reverse-KL, Hellinger or a-divergencee.
1: Initialize the policy Tinit-
2: Set = 1 Ego and & = [A].
3: while q Etol do
4: Calculate the regularization term 1 by (1x)s = [А] Eo ((A(=2))
5: Calculate P. and n by (P=),t = Ee T Pa. (Tx)s Ee TTr
6: Calculate U, by 4 i..., Ux = (1 >Px) - Thx).
7:
if the KL divergence used then
(x-)²= 1 8: (Toow); )=+ E. m
ux))//) for 1.2.... |A], s ........
(7
9: end if
if the a-divergence used then do
11:
for 8 - 1,2 1,2..... S
Set 2/(a- 1). 2 = (ra Solve for c. with the bisection method the interval described in [66 Update (TTew) +- (c. + x.) for a = 1,2,...,1e |A.
13:
Calculate Ta = (1-)))(T)))))
a 1,..., |4|.
15:
end for
17:
end if
TTow - T//P///// [T|//
q
19:
π Tnew
end while
Theorem 5. Let 1, [(x)aa = -11- ( (0z) )s) and
(x)(T) = Σ T log n. 2.)(((T)
1
log
1
[A
(T) -
(T(T)=
4
Σ (1
1).
A
AA 22)
Denote the k-th policy obtained in Algorithm Algorithm Mean be sunmarized as
by x (k), then for nj = 1 the update scheme in
( (T)()())) ( (+) B c((
(17)
1))+ where we denote by B the bby- x [Al) matrix such that Bij (((i)A((()))115 AAii and Bú = 0 otherwise. Define (B(R) 0 ('(AA (Λ ()), where ((x) the convex function used in the regularization (hx)s [Аm E. ([AA Assume that (1) f Lipschitz on closed subset of
{ BJT 1|s T > 0} and (2) (kk) + 0". Then (K) converges quadratically to x², i.e.
| (b+1) T² (1 T- T=
(18)
for some constant C.
Connection with mirror descent The quasi-Newton algorithm 17) for n has a deep con- nection with mirror descent. The vanilla mirror descent of F((T)) with learning rate 3 and the Bregman divergence associated with d is given by
(k+1) arg min( (
1 (0((T) ((((+)) VD( (())))) arg min (diag(w,,e) (f + (M) (()) + / (0((T) (+(
x(+) -
(19)

---

Under review as a conference paper at ICLR 2022
where (iag(U)())) is the diagonal matrix with the diagonal equal w230) (I > ) & denotes the Kronecker product, and |AA denotes the identity matrix with size |A] by |A]. In the last equality, the terms independent of ι are dropped and the multiplier term in E is canceled out using BT = (T(()) | The first order stationary condition of this minimization problem reads
()(((+)))
(x) =
@ (f))(((=())) (1))
+ ()( B (( (20)
This suggests that 17 can be reinterpreted
accelerated mirror descent method with adaptive learning rates 8,- = (x)00)s that depend on the state and the current iterate (K).
In Zhan al. (2021) variant of mirror descent proposed based on an implicit update scheme
(V se (V)(T())) -B' (f(TT()) + (T(((++))) ea (c(T(())).)
(21)
with a manually tuned learning rate 3¹. the next section, we will compare this variant with our quasi-Newton method (17) in several examples and show that the quasi-Newton method converges orders of magnitudes faster than the ones in Zhan et al. (2021).
4 NUMERICAL EXPERIMENTS
4.1 EXPERIMENT I
We first test the quasi-Newton methods derived in Section on the model in Zhan et al. (2021). For the sake of completeness, we include the model description here. The MDP considered has a state space S of size 200 and an action space A of size 50. For each state and action a, a subset St of S uniformly randomly chosen such that |S = 20, and Pi: = 1/20 for any t' E S.. The reward is given by r U..,, where U and U. independently uniformly chosen on [0, 1]. The discount rate y is set as 0.99 and the regularization coefficient - 0.001.
In the numerical experiment, implement Algorithm 1 with the KI. divergence, the reverse KI. divergence, the Hellinger divergence and the a-divergence with a = -3. We set the initial policy as the uniform policy, the convergence threshold as e = 10-12 and the learning rate 1) as 1. Figure (aa demonstrates that, for these four tests, the quasi-Newton algorithm converges in 7, 7, 7, and iterations, respectively. In comparison, we apply the policy mirror descent (PMD) and the general policy mirror descent (GPMD) method in (Zhan et al. (2021) to the same MDP with the same stopping criterion. As also shown in Figure [[a) many more iterations are needed for GPMD and PMD to reach the same precision: GPMD converges in 14822 iterations, and PMD does not reach the desired precision after x 10. iterations.
In order to verify the quadratic convergence proved in Section we draw the plots of log |log || - - |||| in Figures l(b] I(c) I(d) and [(e] where π is the final policy and the norm used is the Frobenius norm. A green reference line with slope log 2 through the origin is plotted for comparison. If the error converges exactly at quadratic rate, the plot of log [log || - TT" shall be parallel the reference line. The convergence curves approach the reference lines in the end (and are even steeper than the reference lines in the begining), demonstrating clearly a quadratic convergence for all regularizations used here.
4.2 EXPERIMENT II
Next, we apply the quasi-Newton methods derived in Section to an MDP model constructed from the search logs of an online shopping store, with two different ranking strategies. Each issued query is represented as a state in the MDP. In response to query, the search can be done by choosing one of the two ranking strategies (actions) return a ranked list of products shown to the customer. Based on the shown products, the customer can refine update the query, thus entering new state. The reward at each state-action pair is a weighted sum of the clicks and purchases resulting from the action. Based on the data collected from two separate 5-week periods for both ranking strategies, construct an MDP with 135k states, and a very sparse transition tensor P with only 0.01% nonzero entries. The discount rate y is set 0.99 and the regularization coefficient is 0.001.
When calculating Ug by U, = (I >P=) -rx - Thæ). we apply the iterative solver Bi-CGSTAB Van der Vorst 1992), widely used numerical method with high efficiency and robustness for
7

---

Under review as a conference paper at ICLR 2022
0,001
0.001
177
loglog efror
loging erro
error
-
reaered PL Alpg
PMD
Borations
Itarations
norations
(a) Relative change of the policy using Algorithm [ and methods from Zhan al. 2002
(b) The policy error in the process of training using KL-divergence.
(c) The policy error in the pro- cess of training using reverse KL- divergence.
0.001
0.001
teeraions
Borations
(d) The policy error the process of training using Hellinger diver- gence.
(e) The policy error the process training using a-divergence with a = -3.
Figure 1: Figures for the synthetic medium scale MDP. (a): Relative change of the policy =||p/||< || during training of Algorithm I compared with PMD and GPMD in Zhan et al.
Tnew
2022)
with the logarithmic scale used for both axes. Notice that Algorithm D converges in 6-7 iterations
to 10-12 in all cases while PMD and GPMD take more than 10 iterations.
(b) (c): Blue: The
convergence of log |log π n² | in the training process with the KL divergence, the reverse KL divergence, the Hellinger divergence and the a-divergence with a = -3, respectively. Green; A line through the origin with slope log 2. Comparison of the convergence plots with the green reference lines shows a clear quadratic convergence for Algorithm
solving large sparse nonsymmetrie systems of linear equations (Saad 2003 de Pillis 1998). in order to leverage the sparsity of the transition tensor.
In the numerical experiment, we implement Algorithm | with the KL divergence, the reverse KL divergence, the Hellinger divergence and the a-divergence with a -3 We set the initial policy as the uniform policy, the convergence threshold as 10-12 and the learning rate 1) as 1. All the tests end up with fast convergence as shown in Figure 2(a) where logarithmic scale is used for the vertical axis. More specifically, the quasi-Newton algorithm using the KI divergence, the reverse KL divergence, the Hellinger divergence and the a-divergence with = -3 converge in 6, 6, 6, 5 iterations, respectively. It is worth noticing that even though the size of the state space here is some magnitudes larger than the examples in Section 4.1 the number of quasi-Newton iterations used is about the same.
In Table I
we report the number of BiCGSTAB steps used in the algorithm. In each quasi-Newton iteration, less than 20 BiCGSTAB steps are used in order to find us- For all the 4 regularizers used here, altogether only about 100 BiCGSTAB steps needed in the whole training process, thanks to the fast convergence of the quasi-Newton method.
Regularizer
KL
reverse-Ki KL
Hellinger a-divergence (a = -3)
Quasi-Newtor Iterations
6
6
5
Total Bi-CGSTAB steps
110
109
110
83
Average Bi-CGSTAB steps
18.3
18.2
18.3
16.6
Table 1: Number of quasi-Newton iterations and BiCGSTAB steps used in the training process.
8

---

Under review as a conference paper at ICLR 2022
reloiive charge of poley
10-4
loglog arro
loo pplogeoe amor
02-4
KL
moress KI
10-12
H4B sga
v-dveggnne juxd)
Iterations
Itorations
Itorations
(a) Relative change of the policy || Naew T/e /||T|] le in the training
(b) The policy error in the process (c) The policy error in the pro- of training using KL-divergence. cess of training using reverse KL- divergence.
process,
0.001
-31
(d) The policy error process training using Hellinger diver- gence.
(e) The policy error the process training using a-divergence with a = 3.
Figure 2: Figures for the synthetic medium scale MDP. (a): Relative change of the policy Nne π |/ ///////[|// || in the training process of Algorithml | Logarithmic scale is used for the vertical axis. (b) - (e): Blue: The convergence of log log || " |e| in the training process with the KI. divergence, the reverse KL divergence, the Hellinger divergence and the a-divergence with a 33 respectively. Green: A line through the origin with slope 2o
As in the previous numerical example, in Figure 2(b) convergence by comparing the plot of log |log | origin with slope log 2. As the convergence curves are approximately parallel to the reference lines, this verifies that the proposed algorithm converges quadratically with all the regularizations in this example as well.
2
2(
and (
verify the quadratic
with a green reference line through the
DISCUSSION
In this paper, we present fast quasi-Newton method for the policy gradient algorithm that is capable of solving large MDP problems with large (ss 1) discount rate and small (> 0) regularizations, The proposed method includes the well-known natural policy gradient algorithm as a special case, and naturally extends to other regularizers such as the reverse KI. divergence, the Hellinger divergence and the a-divergence.
Theoretically, we show local quadratic convergence of the proposed quasi-Newton method with relatively simple proof. This quadratic convergence confirmed numerically on both medium and large sparse models. In contrast with mirror descent type methods (e.g. Zhan et al. (202I)) that take up to tens of thousands iterations even with manually tuned learning rate, the proposed quasi- Newton algorithms typically converge in less than 10 iterations, despite the large discount rate (close to 1) and small regularization coefficient (7 x 0).
For future work, plan to adapt the technique used here to other gradient based algorithms for solving the MDP problems. Other types of f-divergence can also be included. Another direction to consider continuous MDP problems by leveraging function approximation, effective spatial discretization, or model reduction.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods in Markov decision processes. In Conference on Learning Theory, pp. 64-66. PMLR, 2020.
Zafarali Ahmed, Nicolas Le Roux, Mohammad Norouzi, and Dale Schuurmans. Understanding the impact of entropy on policy optimization. International Conference on Machine Learning, pp. 151-160. PMLR, 2019.
Syed Mumtaz Ali and Samuel D Silvey. A general class of coefficients of divergence of one distri- bution from another. Journal of the Royal Statisticul Society: Series (Methodological), 28(1):
131-142, 1966.
Richard Bellman. A Markovian decision process. Journal of mathematics and mechanics, 6(5): 679-684, 1957.
Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. arXiv preprint arXiv:2007.06558, 2020.
Lisette G de Pillis. comparison of iterative methods for solving nonsymmetric linear systems.
Acta Applicandae Mathematica, 11(2):141-159 1998.
John E Dennis and Jorge J Moré. A characterization of superlinear convergence and its application to quasi-Newton methods. Mathematics of computation. 28(126):549-505 1974.
Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A theory of regularized Markov decision processes. In International Conference on Machine Learning, pp. 2160-2169 PMLR, 2019.
Sham M Kakade. A natural policy gradient. Advances in neural information processing systems, 14, 2001.
Vijay R Konda and John N Tsitsiklis. Actor-critic algorithms. In Advances in neural information processing systems, pp. 1008-1014, 2000.
Guanghui Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. arXiv preprint arXtv:2102.00115, 2021.
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. International Conference on Machine Learning, pp- 6820-6822 PMLR, 2020.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. International conference on machine learning, pp. 1928-1937. PMLR, 2016.
Arkadij Semenović Nemirovskij and David Borisovich Yudin. Problem Complexity and Method Ef- ficiency in Optimization. A Viley-Interscience publication. Wiley, 1983. ISBN 978047 103455.
Yurii Nesterov. Primal-dual subgradient methods for convex problems. Mathematical programming, 120(1):221-259, 2009.
Gergely Neu, Anders Jonsson, and Vicenç Gómez. unified view of entropy-regularized Markov decision processes. arXiv preprint arXiv:1705.07798. 2017.
Alfréd Rényi. On measures of entropy and information. In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume I: Contributions to the Theory of Statistics, pp. 547-561. University of Californi Press, 1961.
Anton Rodomanov and Yurü Nesterov. New results superlinear convergence of classical quasi- Newton methods. Journal of optimization theory and applications, 188(3):744-769, 2021a.
Anton Rodomanov and Yurii Nesterov. Rates of superlinear convergence for classical quasi-Newton methods. Mathematical Programming, pp. 1-32, 2021b.
10

---

Under review as a conference paper at ICLR 2022
Yousef Saad. Iterative methods for sparse linear systems. SIAM, 2003.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897. PMLR, 2015a.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. arXiv preprint arXiv:1506.0244 1500.004388 2015b.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: (X07.06777 2017.
Lior Shani, Yonathan Efroni, and Shie Mannor. Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5668-5675, 2020.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In International conference machine learning, pp- 387-395. PMLR, 2014.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard S Sutton, David A McAllester, Satinder P Singh, Yishay Mansour, et al. Policy gradient methods for reinforcement learning with function approximation. In NIPs, volume 99, pp. 1057- 1063, 1999.
Manan Tomar, Lior Shani, Yonathan Efroni, and Mohammad Ghavamzadeh. Mirror descent policy optimization. arXiv preprint arXiv:2005.098/ 2020.
Henk A Van der Vorst. Bi-cgstab: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems. SIAM Journal scientific and Statistical Computing, 13(2): 631-644, 1992.
Li Wang and Ming Yan. Hessian informed mirror descent. arXiv preprint arXiv:2106.1347, 2021.
Ronald J Williams. Simple statistical followng algorithms for connectionist reinforcement learning. Machine learning, 8(3):229-256, 1992.
Lexing Ying. Mirror descent algorithms for minimizing interacting free energy. Journal of Scientific Computing, 84(3):1-14, 2020.
Wenhao Zhan, Shicong Cen, Baihe Huang, Yuxin Chen, Jason D) Lee, and Yuejie Chi. Policy mirror descent for regularized reinforcement learning: A generalized framework with linear con- vergence, arXiv preprint wxXv:2105.11166. 2021.

---

Under review as a conference paper at ICLR 2022
A PROOF OF THEOREM
Theorem 1. Let h E RRSS be the negative Shannon entropy (h=)s = Eo T log (a) For any
with Ln c 0 and (ell Tg. at n1"
T. TD Z.ZZ Tha) O,
where o E [ISISISI the gradient matrix of h with respect to x. (b) There exists diagonal approximation H (T) of the Hessian matrix 1 (TT) such that
(())) - D2 - - =1),..
(c) The quasi-Newton flow from H(T) is
dx
(r- =log 1) [[I > c.)/T.
(10)
dt
With learning rate 17, the gradient update is
(11)
E. explin))) + (+
Proof. Since π is policy, Ea 1 for any Thus
T Pa Σ (6 -Pa)). (2))st = det - Σ
(22)
a
Now consider a policy ग + e close to nτ, i.., En c = and [e < T. then by 22
Zate 2x Ze,
Cate = Fn tTe
(23)
With 23 we have
E(T +e)
2 (Ta+e - Th(xe)
= (2n + - + Te - -hhxte)
(Z 7,=1 7. + 2 7,7 7- (Tr + &re The - -Dh cT T TD2))() + o(22
ee z (rx -hh)) +e- 1-2=-2.2, 2.2 (rx - Thx) + 2 (r+ -D
+e" T
z (-
1 c h)2 + (- ZF 2. (r -
- T ch+c) + + Z. 1r= - Th,)
2
(24)
where we omit the ([ term and keep the first two orders in the last step, and Dh, is second- order tensor that maps from S S, and D² is third-order tensor that maps from (S A) to S. With this expansion,
see that
OF
(r2
T (log n. 1) - -1= c.)(w=)
(25)
Ong
where Wi - e and c. (w=)s is the Lagrange multiplier. Then at ग == n²"
0E
(r (log o. + 1) [[I - -yP")eul,, + cc))(w))s 0.
dmg
Since w, = (I -
)'e and all elements of e are positive, we also know that all elements of w are positive, thus at n²,
)T) - = e Di= >((PT)
r - 7 (log -. + 1) - [(1 -01->P%)u,,, + c, =
Multiplying the left hand side with e and taking the over a we obtain:
(re TD45 -eva), + Co Σ c = 0, Va, Ve,
12

---

Under review as a conference paper at ICLR 2022
and since Ea Co = 0 for any and 14 Zz (rx Thn), we have
Te - Z 2 Thz) O, Ve,
n², which proves
We can now simplify the second-order term in 24 by approximating ve - -DD -7 (x)) with 0 for near x²'
Z
+ (rr -D) (Z -.27 1.44 (T Than)
2T (- 5t +D2 - 2 (re- ( DDii Z Z. (rx Thxt)
1 Z ( 2 hx)))))= = 2 H(Tee.
(26)
By 9 and the twice continuous differentiability of h, it is clear that the approximate Hessian H
converge the true Hessian converges to ',, and H()) D²F((T) O(I *1)).. The second-order derivatives are approximately given by
(w )
R H(ss))(10) - ((0a
(27)
from which we have shown that H is diagonal.
Using this approximate second-orde derivative as preconditioner, wa is canceled out in the policy gradient algorithm, which becomes
d
(r 7log o 1) 1(I-->"")urle c.)/T
dt
Adopting the parameterization πミ exp( have
dog dt (r -66% + 1) [(T ([T->P")Dull cc)/
(28)
With learning rate n, this becomes
8te + n - - [[I >pa)uzls + co)/T + +(1 (1- n)80.
(29)
which corresponds to
Rg - (π exp (1)(1 - 111 yP")url + ca)/T),
(30)
and C2 determined by the condition that En 73 1 for any s. Equivalently, have
T (xxr)) (xx))~- - [11 >
- -1 (unb))))))
exp(nnr2 + (yP")x)))))
(mg)) exp((n=))) + (x)))x)))/7
where we cancel out the factors independent of a. This is exactly [II] which finishes the proof. 0
B PROOF OF THEOREM 2
Theorem 2. Assume that n² is the optimizer of (5) where by denotes the o-divergence (2). Then (a) the Hessian matrix 2d E((T) can be approximated by diagonal matrix (x)) near x² such that [ D2 ((m) [ _ n² and (b) the quasi-Newton method from H (T)) (the policy gradient ascent preconditioned by (T))
-
T + (1- 2-1 1-a 1-
(r [T 7 PP))ala))))) +.2)
(13)
2
where < 1) < is the learning rate and with parameterization 0% = 6' (((A(==)) the update scheme above can be expressed as:
0a + nrr - -1(1 (1--)l)) + c,)/
1)0".
(14)
where ((x)
I-a2 (1 (1) (a 1) and c2 is the Lagrange multiplier introduced by the
4
constraint Eg TT 1.
13

---

Under review as a conference paper at ICLR 2022
Proof. Since the only difference between the functional E(T)) defined here and the E(T)) in Theo- rem flies in the regularizer h, we still have
Wxx (re - D 6 Ze (rr - rha)) = 00 Ve, n², where ,, (T ) Moreover, also have
0E
(rā - - ((A1))=)) (T- + cx)(W))s
(31)
Org
where Ca (w))), is the Lagrange multiplier. Since Wx + Di=1 (((PTT )'e and all elements of are positive, all elements of w are positive as well. Thus at = π
- (I-~P"))e )rl g + c₂) = 0, (r T (((AATTT)
(32)
which leads to and the approximation:
-Dixc - ZeZT (rx -hhx) = 0, ve,
c) E(T) = w/ (- hD +(1e)) = 2 _ O(le))) + -
1
+ O(Ile)))
(33)
Hence we have proved that D2 E(T H H() O(leel). With this approximation, we have
Oº H ((s)) = (Td(( (wx A (IA|=T),
(34)
Which shows that H is diagonal. Then the policy gradient scheme becomes
d
[[A]o((AA[TT)) (r" T ()( - [[I 7p )xl + c.)/TT
(35)
dt
or equivalently,
d (({()) = (r- - -= - 11T + co)/T.
(36)
dt
Let 0- = ('((A[TT)) then
d0
a (r - TB - [(( -P Jo + co)/T,
dt
With a learning rate n. this becomes
8 n/r2 I(I- + c,)/T (1 17)8
which is exactly (4). We derive the quasi-Newton schemes by direct calculations below.
1. When (ha)a = i E. log To we have 8 = -A|F then 14 corresponds to
(1-- m) (r - [(T 7P pP"))= Dorls + tc)//T
and c, is determined by the condition that En T for any
2. When (ha)s = -2
T we have 6" =
1 then 14
corresponds to -2
nV A [[I pPa w +c2
and c, is determined by the condition that E. T. = for any s.
3. When (ha), = - E. (IA| a ( (a))))) we have 03 -1=-=-aaa- (|A(TT) (1A1() a-1 then
(4] corresponds to
T + (1-))=))
1-a
2 m|Al (1 - [11 - pm +
and c2 is determined by the condition that E. ग. = 1 for any
14

---

Under review as a conference paper at ICLR 2022
C PROOF OF LEMMA 3
Lemma 3. Assume that < 0, then for any 21, .2..... Tbe there is unique solution to the equa-
tion:
(x + 21)"
xx) =1,
(15)
such that x; 2 0, 1, Moreover, the solution is the interval
min Ti k 1sisk
2j
1/11/-- min Isisk
(16)
15iSk
Proof. Let
- +x+ 21)" +... + (xr + xx)";
then f(z) is positive and decreasing on (- min Fi. 0o) since each summand is positive and decreas- 1sisk
ing. When x + min x; from the right, f(x) - +o since at least one of the summand goes to 15$5k
+o0. If k1/0-- max 24 2 1Sick
min Iú, then when = k 1/0 15tsk
max Ti.
15iSk
k
f(x) = Σ
(k: 1/0
max 2j + x;)² 2
(k 1/19o = k x =1
15JSk
1=1
1=1
Moreover, when x -1/
min Zi, 1sick
f(x)
1/a
min zj
+
(k 1/100 = k k 1.
15JSk
1=1
1=1
By the continuity of f, there exists solution to 115 on
max
min
Tz, 1//0
max MOXX2,), 2z), 1-1 18isk
min isik
1SiSk
and the solution is unique by the monotonicity of on (- min Ti, po).
1sisk
D PROOF OF PROPOSITION
Proposition 4. The multipliers Ca in the update scheme the updated policy a satisfies x² for any (8, a), and Ee r for any
13 can be determined uniquely such that
Proof. For all the three update schemes, we apply the routine stated in Lemma with & |A| for
|S] times in each iteration. For the reverse-KL. KL divergence, is the solution to 15 for = -1 and
1- n/A(rr - [(I - -- a= 11122 1.2,.... ..A.........
To
T
For the Hellinger divergence, C₂ the solution for -2 and
1- 17
La
..... IA].
VTG
For the update scheme
13
C2 is the solution to 15 for 2/(a 1) and
1 1-
(1 7) (T
11-
1,2, IA].
2
By Lemma 3 the solution to the multipliers such that the updated /ミ 0 is unique, and the straint Σ. n. 1 satisfied since c, is the solution to [5 (with the 2, defined above) and the right hand side of the (15) is 1.
15

---

Under review as a conference paper at ICLR 2022
E
PROOF OF THEOREM 5
Theorem 5. Let 1, f(T) - - ((I P )ut)s and
(KL(T)= Σ T T (xKI(T)
1
log
1
A
( = |A|
" (a)
4
Ea (1A1xg)
< 1).
[A a2
sa
Denote the k-th policy obtained in Algorithm by x(0,, then for rj the update scheme in Algorithm can be summarized as
V - (6)(())) - (f(
(D) - BJ (TT(((())
(17)
where denote by B the by- x |Al) matrix such that Bij ffr ( |Ali and Bij 0 otherwise. Define (0(k)) ('(I (T())))))))))))) where ((x) is the convex function used in the regularization (hx)s 1 E. ([[A[=]) Assume that (1) V is Lipschitz closed subset of
|A|
{x B 1|s), T > 0} and (2) ((k) + 0- Then 7(6) converges quadratically to x², i.e.
(++++) n"1 s <C||
T -
(18)
for some constant C.
S S |Ali and B,y otherwise, the constraint can be expressed by BT = 1|s The gradient flow (28) can thus be expressed by
Proof. Since Bi for | (041-1++1 1)+
d(V)(=)) (f(()) + v - ( [T(()),
(37)
dt
where c(x) is the Lagrange multiplier. The corresponding discrete scheme used is hence
( 1) (*))(())- ( (V) BT c(zz())))
(38)
With this update scheme, we have
((1()+1)) (() V/((T' (1(+1)) -(())
(39)
=f(z((+1))+ + (+(T(++1)) B c((T(1)) Vf(TT) - x())
Since ((k) (k) converges 0" and the map from 0 to is continuous, have converges
to some n² well. Since ((4) { B π ||s T. 2 0} and { T 1 - क. 0} is closed set, we also have nt {T: B π = 1|s - 2 0}. Moreover, since ( goes to infinity
as any entry T - O, we have (n ) > 0 for any and a. Hence (k) is contained in closed set K
contained in (क B continuous, we have
1|s, m 0} for large enough k. By the assumption that V f Lipschitz
((x(++1)) [(T Vs(T') (T || (b++++ - n (b)
ne (1)) O.
lim
(40)
10000
7a ) which has similar form with E(T), we can Moreover, since f(T) (rr - directly obtain (f(=):
(T(()))sstt (-
(-f(T) 2(T), V
(41)
16

---

Under review as a conference paper at ICLR 2022
where Asa,((1) = Z es and Esa is the s-th row of I I-yP". Notice that at x² we have d(V4(x))
de
so f(xT' ) + ( B c(=t), thus
f ( (++1) )) (x),((=T) (-f(TT)) + ē(TT); (T((T)))) (Teb
(k+1)
)
sb
A (8(x*)) c(a")e) (m/b (k+1)
Axzb (k)
(42)
Σ (boac(tT) (c(= ) - d
Σ
(k+1)
(1k)
zb
=zb
=0, 0,
where the last equality results from the fact that 2b we arrive
(R+1)
En (k)
Tib
1 for any t. With 44 and
42
(( + (1+())))1) - B BT c(((1))
lim 4
O.
(43)
[T(++1] - - (k]
Multiply the fraction above by the unit vector x((+2) (( we obtain
(f(m(k+1)) ( - BT c(= (1)) (x(++2) x (8+1))
[ - T x(()] (| (k- +(++1||
(f(T(++1)) + (M+11)
ct ( (x(++2) - x(*+1))
(44)
(k++1 (k) - (k+2)
x (k+1)]
(V - V ()
(x+2) x(++1))
[|[[++]] 7 (k) (x- (1++
where the second equality uses the constraint Br((+1) Bx (k+2) 11st. Then from 43 we have
I (k++1) (V - (
(T (k+2) ((--1)) = 0.
lim
(45)
(8) (k+2) x (k+1)]
By direct calculation of V2 which is diagonal for all the functions & defined in this theorem, we can see that 4 is lower bounded on K, so is strongly convex. As a result, there is some constant
p > 0 such that
(v - ( (- #) 2 pl| 1|
for any ı and in K. Then
|| (R++2) 112
|| n (1+11)
0 = lim T (k+11
lim A
(46)
((+) (k+2) - +
n (k+1))
T (k)
from which we can conclude that n (b) converges to x' superlinearly. i.e. 50 holds. In fact, for any (assume 1/2 without loss of generality), there is some k(c) such that for any le >>> k(().
( n (x+11)]
(k+1) - x(1] <6
then for any k > k(E)
| (k+1)
x² <
|| (n+1) [()) < D c ( (++1) x (10
12 1++1
4=
(47)
1 || (k+1) - -(a) < (k+1) _ (1)
Then
(A) (k)
n² _ > (+++++ - [(a) || - (k++1) >
1
(48)
2
2 10] (+++1) x"1l-
17

---

Under review as a conference paper at ICLR 2022
For any M > 0, take 1/(2M + 2), then for any lo > f(c),
|| (k) - x 2 2c
1) (k+1)
1)][=((++])
x1 = (M + ([] - x²1| || > M|
- 1²1,, (49)
x (1) wl'll
which shows that lim
too and thus
[
T ( π 0.
lim
(50)
|| x²
10000
Now, from 39 and 42 we have
[( ( - BT BBBBB(rrrt c(
-(( f(T(()) [(((T²) ( T(1)
-
- -(% (T(((()) + ((T (b+1) x(11))= - at) (((tt))=((0
(51)
S 0011=(()) x1||||=(M-)) - (*)
for some constant Ö, where we used (5)) and the Lipschitz contiuity of V. in the last equality. Multiply both sides by x(++2) -((++)) and by (44) and the strong convexity of o we have
(=((+2)-x(v+))) p|| - 12
- (V((T()t2) ( (7(++2) 7 ((1+1))
(52)
( + ( B ((llt)) (x(x+2) - x a(++1)
S - nt - ( ( (((+1)]|
which implies that
(1+22 - n (1+11)] < (8) ग T *1|| xr (1
(53)
From 50
we have
[b] -11+1)||
|| (k+1) - (1++2)
lim 10000
lim #
(54)
[|]((k] m²
[|+(1++) πt
Combine this with
53
we get
(b++)) T² & (l( (1) 11.
(55)
for some constant C, which closes the proof.
18


Reviews:
[{"review_id": "yxY-lS5hAp", "reviewer": "Reviewer_Wec3", "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": "Overall I enjoyed reading this paper. The presentation is clear, but the writing can be improved, as explained in the minor comments.\n\nMajor Comments:\n\n(1) Since using entropy regularization changes the problem, $\\pi^*$ of the modified problem is no longer the true optimal policy of the original problem. To complete the story, it is better to provide a bound on the difference between $\\pi^*$ of the modified problem and the true optimal policy? As a follow-up question, I believe there is a trade-off between the asymptotic error and the convergence rate in choosing the regularization coefficient. Is it possible to make the regularization coefficient time-varying so that we have asymptotic convergence to the true optimal policy, and also have improved convergence rate?\n\n(2) In the statement of Theorem 5, the authors assume that $\\theta^k$ converges to $\\theta^*$. Since $\\theta^k$ is a function of the iterate $\\pi^k$ generated by the algorithm, this assumption seems to be problematic. Is it possible to actually prove the statement instead of assuming it? What is the major difficulty there?\n\n(3) Regarding Eq. (18) of Theorem 5, does it hold for all $k$ or only for $k$ large enough? If it is the latter case, what parameters of the problem does the threshold depend on? Regarding the constant $C$, since it is not a numerical constant, what does it depend on?\n\n(4) Newton's method has been studied extensively in the literature. What is the main technical challenge in extending existing results on using Newton's method to solve optimization problem to the setting of policy gradient algorithm?\n\n(5) The policy gradient method is introduced mostly for solving the reinforcement learning (RL) problem, where the MDP model is unknown. Existing algorithms such as PG and NPG can be easily generalized to the RL setting. For the proposed algorithm in this paper, due to the presence of $P^a$, it is not immediately clear how to actually use it in the RL setting, except to first use the model-based approach to estimate $P^a$. It would be nice to have a paragraph discussing about the possibility of extending the results in this paper to the RL setting.\n\nOther Comments:\n\n(1) About writing: When stating a Theorem (Proposition, Lemma, etc), it is better to introduce all the notation before the result. In that case, the statement of the result is more concise.\n\n------------------After Author Feedback-------------------\n\nSince the author did not provide any feedback, I would like to keep my score and vote for rejection.\n", "summary_of_the_paper": "This paper proposes a quasi-Newton method for policy gradient algorithm with entropy regularization, which is popular in solving the reinforcement learning problem. With various entropy functions, this paper establishes quadratic convergence rate for the proposed algorithm. Such convergence rate is verified using numerical experiments.", "summary_of_the_review": "Overall I think this paper is interesting and has the potential to contribute theoretically to policy gradient method. There is some additional work (see my main review) that needs to be done to make this paper more competitive.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "mmvjtiEalif", "reviewer": "Reviewer_eYzw", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Although, I think this is an interesting paper I have some questions that I would be grateful if answered: \n\n1. I found the exposition of the paper to be a bit confusing and not very clear. Is it possible for the authors to clearly list in a sub-section (even in the appendix) the assumptions used when constructing the proofs?\n2. Can the authors kindly illustrate the novelty conveyed in the proof. In other words, how is this analysis novel compared to standard analysis of quasi-newton methods beyond its application to entropy regularised reinforcement learning? That is not to say that the analysis is not rigorous, I just want to understand if there were any hurdles that needed to be overcome carrying optimisation proofs to RL settings. \n3. Concerning the assumptions, is this analysis assuming convexity? Of course, in discrete cases, this can be met but it is not general. If so, I think there needs to be a section clearly elaborating the limitations of the current proof. \n4. Could the authors report the running time of their algorithm rather than just demonstrating iterations? It would be great if those running times are also compared to standard policy gradients and Natural policy gradients. \n5. Could the authors please show reward learning curves rather than just policy changes or log errors?\n6. What does an eta=1 really mean? I do understand that setting a learning rate that high can lead us to the statement of the proof but what does it mean emprically? \n", "summary_of_the_paper": "In this paper, the authors propose a quasi-Newton method for policy gradient algorithms in reinforcement learning while being entropy regularised. Their method acts as an umbrella of other techniques including Natural policy gradients. Interestingly, upon using different regularisers, the approach yields new policy gradient algorithms. ", "summary_of_the_review": "Please see above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "O-UTBZc9Gz", "reviewer": "Reviewer_QCBv", "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": "As said in the summary section, this paper proposes a quasi-Newton method that uses the diagonal of the Hessian matrix as an approximate to accelerate the convergence of the policy gradient algorithm. It shows that under certain conditions along with close to the optimal initial policy, the quasi-Newton policy gradient algorithm converges quadratically.\n\nIt's really interesting to see the quadratic convergence for the quasi-Newton policy gradient method. But the conditions under which this convergence holds is very unclear. For example, in Theorem 5, the assumptions are the \\nabla f is Lipschitz on a closed subset and \\theta^{k} \\to \\theta^{\\star}. How could we verify that these conditions are met for certain problems? I think answering this question could help quantify the localness definition for this paper. \nFor the first example, the initial policy is uniform. Since based on the theorem, its quadratic convergence holds when the initial policy is very close to the optimal one, is this true for this example as well? Also, for the compared algorithms, do you also use the same initial policy? How about the manually tuned learning rate for GPMD?\nCen et al. (2020) also has quadratic convergence result for close to optimal policy case. How does this paper's result differ from it?", "summary_of_the_paper": "The paper is concerned with infinite horizon discounted (finite state and finite action space) MDP problem with known reward and transition matrices.\nTo solve this problem, it proposes a quasi-Newton method for the policy gradient algorithm with entropy regularization.\nThe main contribution is the it proves that the proposed algorithm has local quadratic convergence property under certain assumptions.\nIt also uses two examples to show that the proposed algorithm(s) is faster than the current policy gradient based algorithms in the literature.\n", "summary_of_the_review": "The quadratic convergence of the proposed quasi-newton algorithm is interesting, but the conditions under which it holds is pretty unclear. Since this is the paper's main contribution, it's a borderline submission for me at this moment. I will wait for the rebuttal to address my concerns.", "strength_and_weaknesses": "", "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": "1ALjUfUAHR5", "reviewer": "Reviewer_RnjS", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The primary strength of this paper is the characterization of the Hessian around the optimal policy for a tabular policy representation. This analysis may be helpful to others who do theoretical analysis on policy gradient methods.\n\nThe biggest issue is with this paper is that it does not offer clear support that this Hessian approximation is close when the policy is not trivially close to the optimal policy. There is no investigation as to what effect this precondition matrix has on the optimization surface. Since the resulting update is simply a diagonalized version of the natural policy gradient method, one would expect further insight into when and why the method is advantageous.\n\nThese experiments have two issues. The first is that the comparison between methods is unfair. The same step size is used for all methods, but they all have different dynamics, and it is not clear that the same hyperparameters for each method provide a meaningful comparison. The second is that the experiments shed no light on the type of problems this method will solve efficiently. The methods are only tested on two MDPs, and there is no discussion as to what characteristics of the policy optimization problem these problems are designed to test.\n\nThe paper also makes it seem like it is addressing policy optimization issues for typical RL settings, but the setting of this paper is not typical in practice. First, it does not acknowledge that these results do not pertain to cases with function approximation, which is the more common case of policy optimization. Second, it assumes full knowledge of the reward function and transition dynamics, which is rarely the case. In this setting, it is not clear that policy gradient methods offer any advantage over value iteration policy iteration techniques.\n\n\nQuestions:\nIs the following a correct interpretation of the approximate Hessian? The approximate Hessian assumes that the dominant terms of the Hessian only depend on the diagonal of the Fisher information matrix (FIM) of the policy parameters. This interpretation implies that off-diagonal components of the FIM and any terms that are influenced by the reward function have little impact on the curvature of the objective function.\n\nHow close does the policy need to be optimal before this Hessian approximation is reasonable?\n\nDoes the approximate Hessian provide a helpful update direction and step length when the policy is not nearly optimal?\n\nWhy would one use this Hessian approximation instead of the diagonal of the Gauss-Newton method?\n\nWhy are the MDPs in the experiments well suited to demonstrate the essential properties of these policy gradient methods? What are the properties of the MDPs in the experiment that make these policy optimization methods converge quickly?\n\n\n\nCorrections:\nSection 1.1 first contribution. The algorithm does not recover the natural gradient algorithm but uses the diagonal of the Fisher information matrix.\n\nSection 2: definition of w_\\pi -- Z_\\pi should have a ^{-1} in the exponent.\n\n\nSuggestions for improving clarity\nPage 1: arbitrary weight vector e. It might be worth mentioning that in most RL problems, this weight vector only covers a small set of possible states, making optimization difficult.\n\nSection 2: r_\\epsilon and Z_\\epsilon are introduced, but it is unclear what role they have or why they are being introduced.\n\nSection 2: Formulation of the policy gradient is not immediately obvious, and no derivation or reference is given for the expression.\n\nSection 2: Measure for O(||\\pi - \\pi^*||) is not given until much later in the paper. It was not clear if this was meant to be a norm or divergence measure from the writing.\n\n\n", "summary_of_the_paper": "This paper develops an approximate second-order policy optimization method to overcome the slow convergence of policy gradient methods. This paper proposes an entropy regularized version policy gradient method that approximates the Newton update using a diagonal preconditioner. Theoretical results a presented that show the convergence rate of the new method near the optimal solution is quadratic. A generalized version of the algorithm is presented for any entropic regularizer. Experiments on two tabular MDPs demonstrate that the algorithm can reach convergence in a single-digit number of iterations.\n\n", "summary_of_the_review": "I do not recommend this paper for acceptance because there are many essential unanswered questions regarding the proposed method. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a nice paper which shows that KL-regularized natural policy gradient (assuming exact access to the MDP, meaning no noise in the reward and Q function estimates), which achieves linear convergence, can use ideas from quasi-newton methods and recover their quadratic convergence.  Given the excitement surrounding policy gradient methods and their convergence rates, this is a valuable direction and family of ideas.  Unfortunately, the reviewers had many concerns about presentation, and also of the exact meaning and relationship of the results to prior work; I'll add to this and note that one issue with quasi-newton methods is that it is unclear how long the "burn-in" phase is, meaning the phase before their quadratic convergence kicks in, and this is still an issue in the present work's theory; another issue, as raised by reviewers, is the difference between the regularized and unregularized optimal policies.  As such, it makes sense for this paper to receive more time and polish.
Decision: Reject