Linear convergence for natural policy gradient with log-linear policy parametrization
Authors: Carlo Alfano
Patrick Rebeschini
Venue: Submitted to ICLR 2023 (2023)

Abstract: We analyze the convergence rate of the \emph{unregularized} natural policy gradient algorithm with log-linear policy parametrizations in infinite-horizon discounted Markov decision processes. In the deterministic case, when the Q-value is known and can be approximated by a linear combination of a known feature function up to a bias error, we show that a geometrically-increasing step size yields a linear convergence rate towards an optimal policy. We then consider the sample-based case, when the best representation of the Q-value function among linear combinations of a known feature function is known up to an estimation error. In this setting, we show that the algorithm enjoys the same linear guarantees as in the deterministic case up to an error term that depends on the estimation error, the bias error, and the condition number of the feature covariance matrix. Our results build upon the general framework of policy mirror descent and extend previous findings for the softmax tabular parametrization to the log-linear policy class.

Under review as a conference paper at ICLR 2023
LINEAR CONVERGENCE FOR NATURAL POLICY GRADI- ENT WITH LOG-LINEAR POLICY PARAMETRIZATION
Anonymous authors Paper under double-bling review
ABSTRACT
We analyze the convergence rate of the unregularized natural policy gradient algorithm with log-lineat policy parametrizations in aafinite-horizon discounted Markov decision processes. In the deterministic case, when the Q-value is known and can be approximated by a linear combination of a known feature function up to bias error, we show that geometricalll-incresss convergence rate towards an optimal policy. We then consider the sample-based case, when the best representation of the Q-value function among linear combi- nations of a known feature function is known up to an estimation error. In this setting, show that the algorithm enjoys the same linear guarantees in the deterministic case up to an error term that depends on the estimation error, the bias error, and the condition number of the feature covariance matrix. Our results build upon the general framework of policy mirror descent and extend previous findings for the softmax tabular parametrization the log-linear policy class.
step size yields linear
INTRODUCTION
Sequential decision-making represents framework of paramount importance in modern statistics and machine learning. In this framework, an agent sequentially interacts with an environment to maximize notions of reward. In these interactions, agent observes its current state S, takes an action A according to policy that associates to each state a probability distribution over actions, receives reward, and transitions the case where the agent does not have complete knowledge of the environment dynamics.
new state. Reinforcement Learning (RL) focuses on
One of the most widely-used classes of algorithms for RL is represented by policy optimization. In policy optimization algorithms, an agent iteratively updates a policy that belongs to a given parametrized class with the aim of maximizing the expected sum of discounted rewards, where the expectation is taken over the trajectories induced by the policy. Many types of policy optimiza- tion techniques have been explored in the literature, such as policy gradient methods (Sutton et al,) 1999), natural policy gradient methods (Kakade 2002), trust region policy optimization (Schulman ct al.), and proximal policy optimization (Schulman et al. 2017). Thanks to the versatility the pol- icy parametrization framework, in particular the possibility of incorporating flexible approximation schemes such as neural networks, these methods have been successfully applied in many settings. However, a complete theoretical justification for the success of these methods is still lacking.
The simplest and most understood setting for policy optimization is the tabular case, where both the state space S and the action space are finite and the policy has direct parametrization. i.e. it assigns a probability to each state-action pair. This setting has received a lot of attention in recent years and has seen several developments (Agarwal al. 202T Xiao 2022). Its analysis is particularly convenient due to the decoupled nature of the parametrization, where the probability distribution over the action space that the policy assigns to each state can be updated and analyzed separately for each state. This leads to a simplified analysis, where it is often possible to drop discounted visitation distribution terms in the policy update and take advantage of the contractivity property typical of value and policy iteration methods. Recent results involve, in particular, natural policy gradient (NPG) and, more generally, policy mirror descent, showing how specific choices of learning rates yield linear convergence to the optimal policy for several formulations and variations
of these algorithms (Cen et al.) 2021: Zhan et al. 2021: Khodadadian et al., Xiao 2022
et al.
2022
Lan 2022
Bhandari and Russo 2021 Mei et al.) 2020)

---

Under review as a conference paper at ICLR 2023
Two of the main shortfalls of these methods are their computational and sample complexities, which depend polynomially on the cardinality of the state and action spaces, even in the case of linear convergence. Indeed, by design, these algorithms need to update at each iteration a parameter probability for all state-action pairs, which has an operation cost proportional to ||]| Further- more, in order to preserve linear convergence in the sample-based case, the aforementioned works assume that the worst estimate (fxa norm) of Q* (s, - is the expected sum of discounted rewards starting from the state-action pair (s, a) and following policy x-is exact up given error threshold. Without further assumptions, meeting this threshold requires a number of samples that depends polynomially on |S||||
A promising approach to deal with large and high- sigh-dmmensionll spaces that is recently being explored that of assuming that the environment has a low-rank structure and that, as a consequence, it can be described or approximated by a lower dimensional representation. In particular, a popular frame- work is that of linear function approximation, which consists in assuming that quantities of interest in the problem formulation, such the transition probability (Linear MDPs) or the action- value function QT of a policy т can be approximated by a linear combination of a certain d-dimentional feature function ø S x A + Rd up bias error Ebias- This linear assumption reduces the di- mensionality of the problem to that of the feature function. In this setting, many researchers have proposed methods to learn the best representation (Agarwal et al. 2020; Modi al. [202] Uehara et al. 2021 Zhang et al. (022) and to exploit it to design efficient vairations of the upper confidence bound (UCB) algorithm, for instance (Jin et al. 2020 Li al.
2021, Wagenmaker et al.) 2022).
When applying the framework of linear approximation to policy optimization, researchers typically adopt the log-linear policy class, where policy Te parametrized by 0 I2d is defined as propor- tional to exp(0' 6). For this policy class, several works have obtained improvements in terms of computational and sample complexity, as the policy update requires a number of operations that scales only with the feature dimension d and the estimation assumption to retain convergence rates in the sample-based setting is weaker than the tabular counterpart. In fact, theoretical guarantees for these algorithms only assume the expectation of Q" over a known distribution on the state and action spaces to be exact up to a statistical error Estat- In the linear function approximation setting meeting this assumption typically requires number of samples that is only function of d and it does not depend on |S] and |A|| Telgarsky| (2022). However, a complete understanding of the con- vergence rate of policy optimization methods in this setting is still missing. Recent results include sublinear convergence rates for unregularized NPG (Agarwal et al. 220T) Qiu et al., 2021 Zanette al. 2021 Huu et al. (02T)) and linear convergence rates for entropy-regularicn NPG with bounded updates (Cayci et al. 202T
Our work fills the gap between the aforementioned findings and it extends the analysis and results of the tabular setting to the linear function approximation setting. In particular, we show that, under the standard assumptions on the (Estat, Ehins) lapproximaiininnn of Q* mentioned above, a choice of commerrccally-ncceassnn step-sizes leads to linear convergence of NPG for the log-lineat policy class in both deterministic and sample-basee -asple settings. Our result directly improves upon the sub- linear iteration complexity of NPG previously established for the log-linear policy class by Agarwal jet al. (202T) and Hu et al.] (202T) and it removes the need for entropy regularization and bounded step-sizes used by Cayci et al. (02T), under the same assumptions on the linear approximation of QT. Moreover, we have that the number of operations needed for the policy update and the number of samples needed to preserve the convergence rate in the sample-based setting depend on the dimension d of Φ6, as opposed to the tabular setting where the same quantities depend on |S [.A]. By extending the linear convergence rate of NPG from the tabular softmax parametrization to the setting of log-linear policy parametrizations, our result directly addresses the research direction outlined in the conclusion of Xiao (2022), and it overcomes the aforementioned limitations of the tabular settings.
Our analysis is based on the equivalence of NPG and policy mirror descent with KL diver- gence (Raskutti and Mukherjee 2015), which has been exploited for applying mirror-descent-tyy analysis to NPG by several works, such as Agarwal et al. (20TT): Hu et al. (202I): Cayci et al. (202T). The advantages of this equivalence are twofold. Firstly. NPG crucially ensures a simple update rule, i.e. log 7 (als) log o, (als) + (= a) which in the particular case of the log-linear policy class translates into (s,)) = 0, o(s, a) + 1) T (8, a). Secondly, the mirror descent setup is particularly useful to iteratively control the updates and the approximation errors,
2

---

Under review as a conference paper at ICLR 2023
e.g. through tools like the three-pont point descent lemma (see 3 below), and to induce telescopic sums or recursions that are often used to analyze the converge rate the last iterate.
In our work, show how to exploit these advantages to use the linear approximation of Q2 in the analysis and, consequently, make weaker assumptions on the accuracy of the estimation of Q w.r.t the tabular setting. While previous results for the tabular setting (Cen et al. 2021 Zhan al. 2021
Xiao 2022) require an &o norm bound on the estimation error, i.e. 11 Q" cc S T, our conver- gence guarantee depends on the expected error the estimate, i.e. (B( a) (s, < Sstats
where the expectation is taken w.r.t. the discounted state visitation distribution induced by the policy a and the uniform distribution over the action space. This allows us to employ sample-efficiem pol-
icy evaluation algorithms, such as temporal difference learning (Hu al. [022] Telgarsky 2022)
and to remove the cardinality of the state and action spaces S| from the sample complexity of the algorithm.
The paper is organized as follows. Section 2 introduces the main setting of RL, and Section 3 introduces the algorithm framework we consider. Section and our main result. Section presents the analysis of our main result, with the conclusions outlined in Section 6
Sectioncoontaii contains the linear approximation set-up
SETTING
Consider an agent that acts in a discounted Markov Decision Process (MDP) M (S,,,,Prr,y
where: S is the possibly infinite state space and A is the finite action space; P(s'|s ([s')8, a) is the transi- tion probability: r(s, a) E [o, 1] is the reward function: y the discount factor; and ş is the starting state distribution. A policy π S x A - E is probability distribution over A that represents the probability that an agent takes action when in state 8. At time denote the current state and action by 8t and Oç.
For policy x, let V S IR be the respective value function, which is defined as the expected discounted cumulative reward with starting state 50 8, namely,
V = E
Σ (r((s)))))))) rT, s0 =
where af x-1(s) and 8111 P(-(se, Let (*(1) Banny The agent aims to find an optimal policy n' E argmax, V (14).
For policy n, let Q" S x A + be the respective defined as the expected discounted cumulative reward with starting state so = and starting action ag = a, namely,
function, or Q-function, which is
20
Q =
Σ
7'r(ss, ai) aI 5.a0
where a ~ (-1ss) and 8441 P(-1s,,a))
Define the discounted state visitation distribution (Sutton et al. 1999)
(s) = (1 - 7)))) Eog
2 P(st s/
t=0
and the discounted state-action visitation distribution
d" (s, a) = (1 7) 90, s0.ap
7 = s|, an).
1=0
where the trajectory (st, 0t)120 is generated by the MDP following policy x and is a distribution over S A. Then we can formulate the performance difference lemma (Kakade and Langfor 2002).
tool that will prove useful in our analysis,
V=(M) - V ())
1
Eg-dz
Σ (s, - a(als))
DEA
3

---

Under review as a conference paper at ICLR 2023
2.1 NOTATION
We make the following definitions for ease of exposition. to the policy, let == IT(s, and x² := To, For two functions f and g, denote (ʃ g) (x, v) = f(x))g(y). As to the action-value function, let Q = (= -) and (s) == (s, a). As to the discounted visitation distributions, let dy di de d, e Unif and d² = di UnifA. Lastly, denote KL; Es ( mT).
3 NATURAL POLICY GRADIENT AND MIRROR DESCENT
Policy class In this work, we consider the log-linear policy parametrization (Agarwal et al. 2021 Let E R. be parameter vector and Φ A Rd be feature function. Then the policy class consists of all policies of the form:
exp(0" ((s, a)) Ed'ed exp(0 ( o(s.a'))
Ta(a
Natural Policy Gradient
We formulate NPG through mirror descent. The update at time t + 1 is
Vh(m+t1)= = Vh(=)) + + E
(2)
where h(T,)) E M(ass) log π (als), is the entropy mirror map. This is equivalent to the update 7441(8, a) x कe (5 ().
Vs,
or, as in Algorithm to requiring that 0.41 is such that
01410(8, a) 0, d(s a) (s) As,a E S,A.
In the tabular setting, we have |I|AA|, o(s, a) is vector of all zeros except one in the position assigned to (s, a), and the update is equivalent to the one analyzed by (Agarwal et al. 2002). This mirror descent setup allows us to use standard mirror descent tools in the analysis (Bubeck 2015 Hu et al. 2021 Xiao 2022), such as three-poin descent lemma
Da(ms, 7
(T, +
(n ++1 m (Vh(=²) Vh(m)+1), m nx) Vass (3)
which in this setting can be expressed as
n.41 KL( m.) KL (T,, + KL( T = (n. m TT)
VTT..
(4)
These tools, along with the performance difference lemma (I), ensure that we can control the in- crease of the value function for each policy update. When we only have access to an approximation Q" of Q these tools allow controlling the emror of this approximation by means of simple trian- gle inequality arguments, making possible the incorporation of the linear function approximation framework where Q is approximated by linear combination of the feature function
MAIN RESULT
In this section, we present our main result on the linear convergence of NPG. We start by introducing and discussing the assumptions and the algorithm.
4.1 ALGORITHM AND LINEAR FUNCTION APPROXIMATION
We make the following two assumptions on the linear approximation of Q", which are standard in the literature (Agarwal al. 2021 Cayci et al. 2021)
4

---

Under review as a conference paper at ICLR 2023
Assumption 4.1. (Bias error) Define the loss function
L(w, 0. v) Es,ave (s) w o))
and let
Wy E argmin L(w, Oc, dy)).
(5)
Assume that Vt < T we have
Lwwr O2 d") S Ebiass
L(w,, Oc, d+1 o UnifA) <
Ebios-
In order to better understand the implications of Assumption 4.1 (Agarwal al. 2021
we consider the trivial upper bound
L(we Oc, dd) S d' d'
d"
L(we, Oc. d2) S
L(we, Oz, dz).
This bound allows think of éhins in Assumption 4.1 as controlling quantities of interest. The first quantity is the loss incurred by the minimizer of L(w, Or, d)). that is the best approximation Q' = W. of Q' with respect to the squared error averaged over the distribution d" The second quantity is the shift in distribution from d' to d' in the loss function. A similar conclusion for Assumption 4.1 can be drawn for the the distribution d+t1 UnifA.
Assumption 4.2. (Statistical error) Assume that our estimate wn of we is such that
Es [(ur - üit, ((s, Estar
Assumption concerns the statistical error incurred when solving the minimization problem in (5) and it can be used to describe the sample complexity the algorithm. Let " (",s a) = wi o(s, be the sample-based estimate of @", Then Assumption 4.2 is equivalent to assuming that
Eg Eg (("(s,,)=
< Ettat
Several algorithms have been shown satisfy Assumption 4.2 with number of samples that de- pends only on the dimension d of & and not on [S or |.A), such as temporal difference learning Tel-- garsky 2022). This represent an improvement over the sample complexity of tabular algorithms,
where the typical assumption || IQ" 1 S Estat (Xiao 2022 Li al. 2022) causes the sample
complexity to depend on A.
With this set-up, we can formulate NPG with linear function approximation as in Algorithm At time step t, let D(t, p) be an oracle such that w. D(t, p) satisfies Assumption 4.2
Algorithm 1: NPG with linear function approximation
Input: Learning rate schedule (nx)220 number of iterations T; initialized policy ()): distribution P oracle D. for t O...., do
Obtain w; = (t, p). Update
0.11 0, + n Wr-
end for
Remark 4.3. (Tabular setting) It is possible to recover the tabular case by setting d = |S||AA and b(s, a) to a vector of all zeros except a one in the position assigned to (s, a). In this case, we recover the same update as the labular setting and we have that Ebaas = 0, as by setting = Q'
obtain Ea-v,a-Uiff (Q'(s, - -w T ((8 ((s,a)) = 0 for any distribution v.
5

---

Under review as a conference paper at ICLR 2023
Remark 4.4. (Linear MDPs) Another setting for which the bias error Ebius is equal to 0 is that of Linear MDPs (Jin et al. 2020), where it is assumed that the transition probability distribution and the reward function there exist two feature maps Φ SSS. x A
be expressed
linear function of the feature function 6. Namely, assume TR and μr S + R.d and vector Ur E TR. such that
a() = (m(s, p(s)))
r(s,a) = (Ur,
Vs, ES
this assumption is satisfied, then we have that vts E E,
(((o,a) + + V V* (=())a(o'dddd) ("( r(s,a) + (
which means that at each time step there exists wy IRd such that (s( (Wi, (0 and L(w, Oc d'y)) = O.
4.2 LINEAR CONVERGENCE
order to present the main result of our work, we need two additional assumptions on the distribu- tion mismatch coefficient and the feature covariance matrix.
Assumption 4.5. Assume that the distribution mismatch coefficient
is finite, Lee. Up < co.
Assumption 4.5 standard assumption in the policy optimization literature (Agarwal et al. 2021 Xiao 2022). As we will see in Theorem [4.7] the iteration complexity of Algorithm 1 depends poly- nomially on this term, meaning that the convergence rate faster when the starting state distribution covers the whole state space.
Assumption 4.6. (Relative condition number) With respect to a distribution define
Σ By.anv [6(8, a))
and assume that there exists a K < 00 such that
w Ex. W w Epw
w (Ed )ur Enw Sk V.
sup WER!
S K,
sup WE Rd w
Assumption 4.6 is a standard assumption in the linear function approximation literature and high- lights the importance of choosing a state-action distribution p with good coverage over the feature space, as it can be enforced by choosing the appropriate p. In fact, if Φ = {Ø(s. a)ls S, a E A} a compact set, there always exists state-actis Mate-action distribution p such that K S (see Lemma 23 in Agarwal et al. (2021) )). In general, if [s a)ll < B for all E S, a E A, we have the crude bound B/o min Ep). where min (A) is the minimum eigenvalue of matrix A.
We are now ready to state the following theorem on the linear convergence of Algorithm D
Theorem 4.7. (Linear convergence of NPG with log-linear parametrization) Consider NPG as in Algorithm 7 and let Assumptions 4.1
4.2
4.5 and 4.6 hold. If the step-size schedule satisfies
Up
M++1
2
n
Vt,
1/4
1
and no 2 1_XKL;, then for every T we have
V*(m)-VTHL VT)) <
(1-
1
1 Up
2
+ 2m
A Ksstta
+ +u
VAAEmaa
1 1-7
7)3
To the best our knowledge, Theorem 4.7 represents the first result establishing linear convergence rates for NPG with unbounded updates and without entropy regularization for the log-linear policy

---

Under review as a conference paper at ICLR 2023
class. The convergence rate has explicit dependence the cardinality of the state and action spaces, with the exception of the two [A] terms which, as already highlighted by [Agawwal et al. (022T, can be removed with path-dependent bound. In the case where Ehias = 0 and Esta = 0, the theorem recovers the same convergence rate as Theorem 10 in Xiao (2022).
To obtain the sample complexity of the algorithm, take advantage of the theory for temporal difference learning developed by Telgarssy (2022). In particular, we have that in order to satisfy As-
sumption 4.2 for all T iterations with high probability we need Ö Ti will (1={)=))
samples. Combining
this quantity with the iteration complexity from Theorem of
4.7
obtain total sample complexity
2
d
- 7)10
Remark 4.8. (Different policy parametrizations) While our work focuses on the log-linear policy class, it is possible to extend our framework and our analysis to general function approximation schemes. Let fo S x A R be parameterized function and define the policy class { E }} as
exp(fo(s,a)) To(als) = ex
Let Iw be parametrized operator of fo. define the loss function
L(w,0,v) = Bewn,anUnll [10=0 a) gw (fee
and let
We argmin L(w, Or, d'..)
Then, Assumption 4.1 becomes
Ilur, O2 dr.) S Ebnas The NPG update 2 can then be formulated requiring Oct1 to be such that
vt < T.
Sonn (8. = So, (s, a) + 7e9u, (Jo, (8, a))
Vs E S E A.
Finding methods to solve this system of equations is beyond the scope of this work.
ANALYSIS
In order to prove Theorem 4.7 need some intermediate results. The first one regards the decom- position of the statistical and the bias errors.
Lemma 5.1. The expected error of the estimate Q' of Q2 can be bounded as follows
A KE mar + +221A AA
s 2 for both di+1 7! and v di
EmnoQ' Q2, -Ta)
-
Vt < T,
Proof of Lemma 5.1 We start by adding and subtracting Q
Es D'e ni - x < (Q: - Q' n. - > + E Q2 T -T>)
We then bound the two terms on the right-hand side separately. For the first term, we have that
( - Qt o. nz)
Eswnana: [(we- we (o) + Bsneraws, [ww - -w))o(s, (a)(((s)))] a)ll
V Esweaans [(wrr wh w.))(s, a))?] + / //trr))) [((us - -aa--weeee w)))(s a))²
< 2/ |||Esn,,aUUitA [(w., [(w @.))((,)))) -2V1A1 llwe @eg 1 1
7

---

Under review as a conference paper at ICLR 2023
where ||wl| w
wT Ew. Using Assumption and the fact that (1 (1-7)p d% we have
we Wh l1
A
S k.
We Well2,,
S 1 A
1 Wh WellEi. S
sttt
Similarly, for the second term we have
(Q Q'a ma) s v A Al ((os,a)-(((ss))) 22V|Alebinss
For ease exposition, in the rest of this section denote
A AlnEs 2 Ebias.
2
The next lemma regards the quasi-monotonic improvements of Algorithm Let Q' i, o(s,)). Lemma 5.2. The updates of Algorithm satisfy, for all E S,
(Q's m -m²) 20
and
(1) vL+1()) - (' 2 2-1-2
7
1-
Proof of Lemma 5.2 By I-strong convexity of on (0, 1), we have Vs S
n = 2 & (Vh(= -Wh())) # x Q2,, m n²))
As to the second inequality.
the performance difference lemma and Lemma 5.1 to obtain (1 (1-2)(v(+)))) (1) - (')) snd (Q',
oT ++1
++1 -m²)
E gedtt @ n
mT) B 10's +t m
T
1 1
The last result we need the following lemma, which can be straightforwardly proven by induction. Lemma 5.3. Suppose < a < 1,b and nonnegative sequence {ax} satisfies
a&+1 S aap +
Wk N 0.
Then for all k
b a S a ag
+ 1- a
With these results in place, we are ready to prove Theorem 4.7
Proof of Theorem 4.7 Let
d"
dhi
and consider the equality in (4)
(L(T,,, m!)) KL(TTs, (: (+2) KL(m 1+1 m²))
(1,
1+1 Te)
Vns.
Then, for n. n. we have that
Eand; (2: 1/. n: 1111 + Bewdy Q #3 =²') < KL; KL
8

---

Under review as a conference paper at ICLR 2023
We bound the two terms on the left-hand side separately. For the first one, have that
Bandy (Q's
T3-
1+1
d
E Bo @ m3 - -
2
dxt1
1000
= =K+1(11 7) (n) (n)) + B (Q) Q2 x3. - -
2 1 11-1111)) 7) (V'(H) v(+ (p)) 1K+1T,
where the first inequality is due to Lemma 5.2 the equality is due to the performance difference lemma 4 and the second inequality is due to Lemma 5.I We use Lemma 5.1 again to bound the second term in the left-hand side of (6)
Ex-d; @ Th.
وt) Eswdj (Q o - -m²) + Londy (Q 2 m - m²))
2 (1 (V* (u) v'())) -.
Plugging the two bounds (6) we obtain
KL;
KL
Mk++ Ac+1 A.
+ < (1 7)
(1 7))
1 7¹
where A, (*())= - V'(N), From Lemma 5.2 we have that De+1
D.
T-7
-
S 0, so, since
Pe-1 $ Vus we can replace 2441 with V/ and write
KL;
KL
(1+T
Up (Au+1 A,) + A.
(1
7)7
(1- (1-7)9%
1-7
Rearranging and dividing by Up we obtain
KL
S (1 (1- 1) ( A +
7) (vp - 13 ) ) (1
KLŞ
A4+1 + (1 7unme
V/j
(1
Vp
1-
If the step sizes satisfy 1/4 (y/- - 1) 2 M/. then
KL
1
KLJ
2T
Ao+1 + (1 7- (vz, 1) < 1 (1-
A 7) (u 1)
+
U/
where we used that 1 2 1. The proof of the theorem follows by applying Lemma 5.3
6 CONCLUSION
We show how unregularized NPG can be tuned to achieve linear convergence for the log-linear policy class up to error floor that depends on the statistical error of our estimates of Q' and the bias error of the best linear approximation of Q'. Our results fill the gap between the findings in the tabular setting and the log-lineat policy setting, taking advantage of mirror-descent type analysis, and address research directions outlined in previous works (Xiao) 2022). The main future direction that of extending our framework and results general policy parametrizations, as we suggest in Remark 4.8
REFERENCES
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy. and Wen Sun. Flambe: Structural complex- ity and representation learning of low rank mdps. arXiv preprint arXiv:2006. 10814, 2020.
Alekh Agarwal, Sham Kakade, Jason Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. J. Mach. Learn. Res., 22 (98):1-76, 2021.
Jalaj Bhandari and Daniel Russo. On the linear convergence of policy gradient methods for finite mdps, 2021.

---

Under review as a conference paper at ICLR 2023
Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning. 2015.
Semih Cayci, Niao He, and R Srikant, Linear convergence of entropy-regularizze natural policy gradient with linear function approximation. arXiv preprint arXiv:2106. 04096, 2021.
Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 2021.
Yuzheng Hu, Ziwei Ji, and Matus Telgarsky. Actor-critic is implicitly biased towards high entropy optimal policies. arXiv preprint arXiv:21 10. 12800 2021.
Chi Jin, Zhuoran Yang, Zhaoran Wang. and Michael I. Jordan. Provably efficient reinforcement learning with linear function approximation. In Abernethy Jacob and Agarwal Shivani. editors, Conference on Learning Theory, pages 2137-2143, 2020.
Sham Kakade and John Langfor. Approximately optimal approximate reinforcement learning. Pro- ceedings of the 19th International Conference on Machine Learning, 2002.
Sham M. Kakade. A natural policy gradient. Advances in Neural Information Processing Systems, 2002.
Sajad Khodadadian, Prakirt Raj Jhunjhunwala, Sushil Mahavir Varma, and Siva Theja Maguluri. On the linear convergence of natural policy gradient algorithm. In 202/ 60th IEEE Conference on Decision and Control (CDC), pages 3794-3799. IEEE. ISBN 166543659X.
Guanghui Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. Mathematical programming, pages 1-48, 2022. ISSN 1436-4646.
Gen Li, Yuxin Chen, Yuejie Chi, Yuantao Gu, and Yuting Wei. Sample-efficient reinforce- ment learning feasible for linearly realizable mdps with limited revisiting. arXiv preprint 1r5.v:2/05.08024, 2021.
Yan Li, Tuo Zhao, and Guanghui Lan. Homotopic policy mirror descent: Policy convergence, implicit regularization, and improved sample complexity. arXiv preprint (iXXv:2201.0945711 2022.
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning, pages 6820-6829. PMLR, 2020. ISBN 2640-3498.
Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free representation learning and exploration in low-rank mdps. arXiv preprint arXiv:2102.07035, 2021.
Shuang Qiu, Zhuoran Yang. Jieping Ye, and Zhaoran Wang. On finite-time convergence of actor- critic algorithm. IEEE Journal on Selected Areas in Information Theory, 2(2):652-664, 2021. ISSN 2641-8770.
Garvesh Raskutti and Sayan Mukherjee. The information geometry of mirror descent. IEEE Trans- actions on Information Theory, pages 1451-1457, 2015.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889-1897. PMLR.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.0m 077770667777777. 2017.
Richard S. Sutton, David A. McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Infor- mation Processing Systems, pages 1057-1063, 1999.
Matus Telgarsky. Stochastic linear optimization never overfits with cettrratiiaaly-ooudddd losses on general data. arXiv preprint 27Xiv:2202.069/5, 2022.
10

---

Under review as a conference paper at ICLR 2023
Masatoshi Uehara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline rl in low-rank mdps. arXiv preprint arXiv:2110.04652, 2021.
Andrew Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson. First- order regret in reinforcement learning with linear function approximation: robust estimation approach. In International Conference on Machine Learning, pages 22384-22429, PMLR, 2022. ISBN 2640-3498.
Lin Xiao. On the convergence rates of policy gradient methods. arXiv preprint arXiv:2201004443, 2022.
Andrea Zanette, Ching-An Cheng, and Alekh Agarwal. Cautiously optimistic policy optimization and exploration with linear function approximation. In Conference on Learning Theory, pages 4473 4525. PMLR, 2021. ISBN 2640-3498.
Wenhao Zhan, Shicong Cen, Baihe Huang, Yuxin Chen, Jason mirror descent for regularized reinforcement learning: A generalized framework with linear con- vergence. arXiv preprint arXiv:2105./1066 2021.
Lee, and Yuejie Chi. Policy
Tianjun Zhang, Tongzheng Ren, Mengjiao Yang, Joseph Gonzalez, Dale Schuurmans, and Bo Dai. Making linear mdps practical via contrastive representation learning, 2022.


Reviews:
[{"review_id": "p3ee1t1zBy", "reviewer": "Reviewer_XCzT", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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 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 with an increasing step size result in exponential convergence to a ball around the global optimum. This ball is proportional to these function approximation errors. ", "summary_of_the_review": "I believe the contribution of the paper is limited, and is a straightforward extension of the prior work. \nAlso the paper is not well written. Some parts are not clear. There is a sample complexity which is not clear corresponds to what. \n\n---------------------------------------------------------------------------------\n\nUpdate: After looking at the response by the authors, I would like to still keep my score. I believe the paper is a simple extension of the Xiao (2022) to the function approximation setting. ", "strength_and_weaknesses": "Strength: \nThe paper extends the linear convergence rate shown for tabular setting in Xiao (2022) to a more general function approximation setting. \nWeakness:\n- In the bound, v_\\mu can be in general state and action dependent. Also it depends on 1/(1-\\gamma). The authors do not specify the dependency of this parameter on state, action and 1/(1-\\gamma). Since this parameter appears in an exponential manner in the upper bound, this can result in a very bad dependency on the upper bound.\n- The contribution of the paper is limited compared to the prior work, specially Xiao (2022).\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).", "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": "fkWLTyQaDnr", "reviewer": "Reviewer_VEtG", "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": "", "summary_of_the_paper": "This paper analyzes the convergence rate of the natural policy gradient (PG) algorithm with log-linear policy parametrizations in infinite-horizon discounted MDPs. The paper shows that under standard function approximation assumption about the Q-value functions, with an increasing stepsize, a linear convergence rate of the natural PG method can be obtained for log-linear policy class in both deterministic and sample-based settings. The results strictly improve the existing results along this direction, which can only have either sublinear convergence rate, or require regularization and bounded iterate assumptions. In the sample-based setting, the results do not depend on the cardinality of the spaces, but on the dimension of the features, which is favorable for large-scale cases. The paper is clearly written in general, and the results are of interest to the community.", "summary_of_the_review": "In sum, the paper presented some interesting results about natural policy gradient for log-linear policy classes. The techniques and idea about the algorithm (increasing the stepsize specifically), are based on several most related literature, making the novelty and orginality of the work a bit limited to make the cut.", "strength_and_weaknesses": "Strength: The paper developed new results on natural PG method with log-linear parameterization, and is well-written generally (up to some small errors). The motivation is clear, and the manuscript is concise and easy to follow.\n\nWeakness: As a pure theory paper, I am a bit uncertain about the technical novelty and solidness of the results. It seems that it strongly relies on the analysis in previous works, e.g., Agarwal et al, 2021, Xiao 2022, and Telgarsky et al., 2022. The idea of increasing the stepsize also follows from Xiao 2022. I skimmed through the proof, which reinforces my feeling as well.\n\nOther Comments:\n1. As it is a theory paper with new technical results, it would be helpful to summarize the novelty of the \"Techniques\" in the front, e.g., in introduction, so that the readers can better understand it and compare it with the literature.\n2. It would be better if some simple experiments can be provided to corroborate the theoretical findings: how does the stepsize affect the convergence rates, how does it compare with the existing PG algorithms, and any ablation study about the algorithm parameters (stpesize, feature vector, etc.).\n3. It was claimed in the abstract and intro multiple times that the results do not depend on |S|, |A| but only on d. However, in the main results in Theorem 4.7, there is still dependence on |A|. It was argued that \"can be removed with a path-dependent bound\". It was not very convincing to me to claim this without a valid statement. It is better to either give a formal statement here, or modify the claims in the beginning. \n4. Errors and typos:\n1) Definition of $d_\\rho^\\pi(s,a)$ on page 3 is not correct. \n2) Some notation abbreviation in sec. 2.1 is not consistent with later sections, e.g., $\\pi^t$ v.s. $\\pi_t$. Where is $d_\\mu^*$ defined? Since it is a theory paper, being rigorous about notation would be important and affect the credential of the paper. \n3) There is an additional \"the\" in the sentence right before Assumption 4.2.\n4) Definition of linear MDP in Remark 4.4 is not correct: P and r should be sharing the same feature $\\phi$.\n\n\n**Post-rebuttal:**\n\nThank the authors for the rebuttal. I have read it, and also read other reviewers' comments. Now I get that the mirror descent reformulation of the NPG update in the linear function approximation case is new. But I am still a bit unsure if the overall novelty clears the bar of ICLR. I recommend the authors to maybe add the results regarding neural network and even general function parameterization more formally, to make the results more complete and stronger. I will hence stick to my previous evaluation. Thank you.", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "cBky6puA0c", "reviewer": "Reviewer_SUKm", "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": "", "summary_of_the_paper": "This work studies policy optimization in single-agent RL with log-linear policy parameterization by focusing on natural policy gradient (NPG) method. In particular, this work demonstrates a linear converging error bound of NPG with increasing step sizes to the optimal policy, up to some statistical and approximation errors.", "summary_of_the_review": "This work makes interesting contribution towards policy optimization with log-linear policy optimization, by extending the insight of [Xiao, 2022] which focused on the tabular setting. This work establishes a linear converging upper bound up to an error floor determined by $\\epsilon_{stat}$ and $\\epsilon_{bias}$, by deploying NPG updates with increasing step sizes. However, the magnitude of the error floor is worse than that of Theorem 6.1 in [Agarwal et al., 2021], despite introducing additional assumptions. Therefore, the reviewer vote for \"5: marginally below the acceptance threshold\".", "strength_and_weaknesses": "Strength:\n\n- This work investigates the problem of policy optimization with log-linear policy parameterization, which is a fundamental problem of the policy optimization theory. \n- This work extends the insight of [Xiao, 2022] from the tabular setting to the regime of linear function approximation and manages to achieve a linear converging error bound (up to some statistical and approximation errors) without introducing entropy regularization [Cayci et al., 2021].\n\nWeaknesses:\n\n- Assumption 4.6 imposes additional bound on the relative condition number for all iterations (compared to Assumption 6.2 in [Agarwal et al., 2021]), which is somewhat undesirable. It would be great if the authors can make this clearer when making a comparison and provide a justification.\n- The claim \"convergence towards an optimal policy\" appears to lack some support. In particular, it remains unclear if the bound established in Theorem 4.7 is tight when compared with an optimal policy. In addition, the bound introduce a factor $\\nu_\\mu$ in the dependency on $\\epsilon_{stat}$ and $\\epsilon_{bias}$ (which is at least $1/(1-\\gamma)$) compared with Theorem 6.1 in [Agarwal et al., 2021]. This makes the linear converging bound less appealing.", "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": "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": "_Eiorqgb5N", "reviewer": "Reviewer_vAhQ", "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 focuses on the NPG in softmax policy with linear function approximation. By proposing a new updating strategy, in which the stepsize increases at a designed rate, this paper is able to show that the NPG enjoys a per-iteration geometry convergence rate w.r.t a factor $1-1/\\nu_\\mu$. Since previous works of NPG in the similar setting mostly focus on establishing sublinear convergence rate, the result established in this paper is interesting.", "summary_of_the_review": "Overall this paper provide a very interesting result of NPG. However, the result is more like provide a different formulation of the sample complexity result of NPG instead of establishing a more tighter bound (for detail see my comment in weakness in previous section).\n\n\n============ post rebuttal ============\n\n\nAfter reviewing author's response, I will raise my score to 6. The contribution in this paper is not strong enough given the state-of-the-art. The linear convergence rate of PG without entropy regularization has been explored in previous work. For example, in [1], when adopting l2 regularization in their mirror descent update, the result in [1] naturally implies a linear convergence rate for PG algorithm. However, since this paper explore a new technique for analyzing the PG type algorithm, it might be interesting to the community.\n\n[1] Lan, G. (2022). Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. Mathematical programming, 1-48.", "strength_and_weaknesses": "Strength:\n(1) This paper is well-written and easy to follow\n(2) The technique proof is solid and clear\n(3) The result established in this paper is different from all previous works in the same setting, which is interesting.\n\nWeakness:\n(1) The major technique contribution of this paper is in exploring how the incremental increasing stepsize with the special RL optimization nature can provide a linear convergence rate, which is interesting but not strong enough.\n(2) The linear convergence rate in this paper may not be very useful in most of the case. The major reason is that the contraction factor $(1-1/\\nu_\\mu)$ is significantly larger than \\gamma (or very close to 1 as $\\nu_\\mu$ is usually very large. With a given sample complexity $\\epsilon$, if $\\nu_\\mu$ scale as $\\mathcal{O}(\\exp(1/\\epsilon))$ then the sample complexity in this paper may actually looser than standard NPG complexity results established in many previous works. Thus, the linear convergence rate established in this paper only improves the real sample complexity of NPG within a very limited scenario. ", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "M8E-7QTM1X", "reviewer": "Reviewer_5t57", "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": "", "summary_of_the_paper": "This work proposes to use increasing stepsize in Xiao, 2022, as shown in Theorem 4.7, in natural policy gradient with log-linear policy parametrization, and the main result is that the convergence rate is linear plus approximation errors, improving the $O(1/\\sqrt{T})$ rate plus approximation error terms in Agarwal et al, 2021.\n", "summary_of_the_review": "Overall, this work combines two existing techniques of Agarwal et al., 2021 and Xiao, 2022, and obtains a new linear convergence rate for natural policy gradient with log-linear parametrization. The results are correct and new. However, to my understanding, the technical difficulty and novelty of this work are limited.\n\n\n====Update====\n\nThank you for the comments. However, after reading the authors' feedback and other reviewers' comments, I would keep my score.\n\nAs mentioned by the authors in the feedback, the main introduced technique is \"the mirror descent formulation of Natural Policy Gradient for non-tabular settings\", which \"is substantially different from the analysis in [Agarwal et al., 2021]\".\n\nThe \"mirror descent formulation of Natural Policy Gradient\" is actually not new. For example, the Q-NPG method in Agarwal2021 is similar to Eq. (2) and Algorithm 1 in this paper. \n\nMy understanding of the authors' claim is that the authors used the analysis in Xiao2022 to the settings in Agarwal2021. The analysis of this paper (performance difference lemma and the three point descent lemma) contains also widely used techniques in mirror decent proofs. The authors' feedback still confirms my impression of incremental technical contribution. \n\nIf the authors wanted to emphasize more the technical innovation, I suggest comparing and illustrating the difference and difficulty more directly, such that the audience can better understand the contributions of this work. ", "strength_and_weaknesses": "**Strength**\n\nThe linear convergence rate was previously shown in softmax tabular parametrization, and this work shows that the same rate can be achieved with log-linear parametrization, which was not known before.\n\n**Weaknesses**\n\n1. The above mentioned results are new, but the novelty and technical contributions of this work are very limited to my knowledge for the following reasons.\n    - The main analysis is based on decomposing $V^*(\\mu) - V^T(\\mu)$ into two parts of optimization error and biases, which has already been shown by Agarwal et al., 2021. This work adopted the same assumptions in Agarwal et al., 2021, i.e., Assumptions 4.1, 4.2, 4.5, and 4.6.\n    - Using the decomposition of $V^*(\\mu) - V^T(\\mu)$, stepsize in Xiao, 2022 is then used.\n    - The analyses also look very similar to those two works to me.", "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": {}}]

Author rebuttal:

Decision: Reject