Ordering-based Conditions for Global Convergence of Policy Gradient Methods
Authors: Jincheng Mei
Bo Dai
Alekh Agarwal
Mohammad Ghavamzadeh
Csaba Szepesvari
Dale Schuurmans
Venue: NeurIPS 2023 oral (2023)
Keywords: reinforcement learning
policy gradient
policy optimization
function approximation
global convergence
TL;DR: PG method converges whenever there exists an adequate linear function that ranks actions in the same order as the ground-truth reward function.

Abstract: We prove that, for finite-arm bandits with linear function approximation, the global convergence of policy gradient (PG) methods depends on inter-related properties between the policy update and the representation. textcolor{blue}{First}, we establish a few key observations that frame the study: \textbf{(i)} Global convergence can be achieved under linear function approximation without policy or reward realizability, both for the standard Softmax PG and natural policy gradient (NPG). \textbf{(ii)} Approximation error is not a key quantity for characterizing global convergence in either algorithm. \textbf{(iii)} The conditions on the representation that imply global convergence are different between these two algorithms. Overall, these observations call into question approximation error as an appropriate quantity for characterizing the global convergence of PG methods under linear function approximation. \textcolor{blue}{Second}, motivated by these observations, we establish new general results: \textbf{(i)} NPG with linear function approximation achieves global convergence \emph{if and only if} the projection of the reward  onto the representable space preserves the optimal action's rank, a quantity that is not strongly related to approximation error. \textbf{(ii)} The global convergence of Softmax PG occurs if the representation satisfies a non-domination condition and can preserve the ranking of rewards, which goes well beyond policy or reward realizability. We provide experimental results to support these theoretical findings.

Ordering-based Conditions for Global Convergence of Policy Gradient Methods
Jincheng Mei Google DeepMind j cmee@google com
Bo Dai Google DeepMind bodai@google, e. com
Alekh Agarwal Google Research
alezhagarkal@@oogge..com
Mohammad Ghavamzadeh
Csaba Szepesvári Google DeepMind University of Alberta szepi srep@ggooge..o com
Dale Schuurmans
Amazon* ghavamza@amazon.. com
Google DeepMind University of Alberta daes@ualberta.co
Abstract
We prove that, for finite-arm bandits with linear function approximation, the global convergence of policy gradient (PG) methods depends on inter-related properties between the policy update and the representation. First, we establish few key observations that frame the study: (i) Global convergence can be achieved under linear function approximation without policy reward realizability, both for the standard Softmax PG and natural policy gradient (NPG). (ii) Approximation error is not a key quantity for characterizing global convergence in either algorithm. (iii) The conditions on the representation that imply global convergence are differ- ent between these two algorithms. Overall, these observations call into question approximation еrrоr an appropriate quantity for characterizing the global conver- gence of PG methods under linear function approximation. Second, motivated by these observations, we establish new general results: (i) NPG with linear function approximation achieves global convergence if and only if the projection the reward onto the representable space preserves the optimal action's rank, a quantity that is not strongly related to approximation error. (ii) The global convergence of Softmax PG occurs if the representation satisfies non-domination condition and can preserve the ranking of rewards, which goes well beyond policy or reward realizability. We provide experimental results to support these theoretical findings.
Introduction
Policy gradient (PG) a foundational concept in reinforcement learning (RL), centrally used both policy-based and actor-critic methods (25] Despite the non-convexity of the policy optimization objective (4, global convergence of PG methods has been recently established in the tabular case for standard configurations such as the softmax parameterization 4 22 and stochastic on-policy sampling [20). In practice. when an RL agent is faced with a problem with large state and/or action spaces, function approximation is needed to generalize across related states and actions. The behavior this paper, we study this question for
of PG methods these settings relatively under-explored. the case of linear function approximation, and establish surprising result that
the classicul Softmax PG method converges whenever there exists an adequate linear function that ranks actions in the same order the ground ground-truth reward function.
"The work done prior joining Amazon, while the author Google Research. 37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Understanding the behavior of PG methods under function approximation is crucial for describing the behavior of RL in practice, since one rarely faces domains small enough to explicitly enumerate over states and actions in parameterizing the policy. It is well known that, standard Softmax PG converges to stationary points if "compatible" function approximation is used [25;; i.e., one that able to exactly represent policy value functions. However, when exact policy values are non-realizable, "approximation error" is typically considered to be the key quantity for characterizing how well a function approximation captures relevant problem quantities, including transition dynamics, rewards and policy values. This paper shows that such an approximation error perspective is overly demanding when attempting to characterize the conditions that lead to global convergence of PG methods.
Using the concept of approximation error, global convergence results for PG methods have been recently established in an additive form,
(I) implying that if the approximation error is small, a diminishing optimization error implies small sub-optimality gap. A representative result is the global convergence of natural policy gradient (NPG) 44 Table 2]. where the optimization error will diminish as the algorithm updates. There have also been global convergence results for other PG variants under linear function approximation that
sub-optimality gap < optimization enror + approximation error,
follow similar approximation error analysis g 28 5 2. However, an additive bound like Eq. T1) has the inherent weakness that the approximation error will never be zero if the function approximation is not able to perfectly represent the desired quantities. This prevents such a strategy from establishing global convergence in cases where the approximation error is non-zero but PG method still reaches the best representable solution.
Therefore, in spite of this recent progress, using approximation error in PG global convergence with function approximations has left two major gaps in the literature. First, it has not been investigated whether small approximation error is necessary to achieve convergence to an optimal representable policy (4. diverting attention from feature designs that achieve useful properties beyond small approximation error. Second, it is not clear if standard Softmax PG (other than NPG) converges globally under small approximation errors. In particular, NPG contains a least squares regression step [4, Eq. (17)) that can be naturally characterized with an approximation error quantity. However, standard Softmax PG does not have such a projection step [2). and the results in 4 do not apply to this update. Whether standard Softmax PG can achieve global convergence with even linearly realizable rewards (zero approximation error) is still an open problem.
In this paper, we address the above questions and contribute the following results. First, we provide negative answers questions on the role of approximation error in determining global convergence of PG methods:
(i) Global convergence can be achieved under linear function approximation with non-zero approxi- mation error, for both the standard Softmax PG and natural policy gradient (NPG) updates. Approximation error is not key quantity for characterizing global convergence in either case.
(ii)
(iii)
The conditions that imply global convergence are different between these two algorithms.
Second, these results lead us to question whether approximation error is an appropriate quantity to consider the global convergence of PG methods under linear function approximation. We establish new general results that characterize the conditions for global convergence of PG methods:
(i) NPG with log-linear function approximation achieves global convergence if and only if the projection of the reward onto the representable space preserves the optimal action's 's rank. This result significantly extends previous results that use approximation error the analysis 4 3) since preserving the rank of the optimal action is not strongly related to approximation error (except in the realizable limit).
(ii) We show that the global convergence of Softmax PG follows if the representation satisfies non-domination condition and can preserve the ranking of rewards, which goes well beyond policy or reward realizability. As a byproduct, we resolve an open question by showing that even for linearly realizable reward function, Softmax PG cannot always converge to globally optimal policies when the non-domination condition for representation is violated.
2

---

2 Settings
We study the policy optimization problem under one state with K actions. Given reward vector r E R the problem to find parametric policy aa to maximize the expected reward.
sup To
(2)
BERd
where 0 E Rd with d < K is the parameter, and To softmax(X6) (X0) is called "log- longelinear policy" 28 such that for all action a E [K] == {1, .... K).
exp (x)
(a) [ exp (x)
(3)
where X RKxdd the feature matrix with full column rank d < K. There are two major difficulties with the policy optimization problem. First, Eq. 2 is a non-concave maximization w.r.t. 0, due to the softmax transform [22] Proposition 1]. Second, the policy and reward can be unrealizable, the sense that the parametric log-linear policy Ti softmax(XX)) cannot well approximate every policy ı in the K K-dimensional probability simplex, and the score X0 E R cannot well approximate the true mean reward R Such limitations arise in the linear function approximation case because Ty and X8 are restricted to low-dimensional manifolds via 8 E Rd for <<< K.
To solve Eq. 2 we consider the standard Softmax PG 225 and NPG [3] 4 methods, shown in Algorithms Jann] Softmax PG is an instance of gradient ascent, obtained by the chain rule,
d - d0, d0,
dX0e
TTe
d TT.
x x (diag(Te.) - Te, To.)
(4)
dx00, diØ,
On the other hand, NPG conducts updates using least squares regression (i.e., projection),
(xTx) x arg min |Xw (ww-rlp r
(5)
wERd
As representative policy-based methods, in their general forms, Softmax PG and NPG lay
foundation for widely used RL methods, including REINFORCE (26), actor-critic [16 [2]. TRPO
and PPO 23 24]. The above Eqs. 44) and (5) are their updates applied to the one-state setting.
Algorithm Softmax policy gradient (PG)
Algorithm Natural policy gradient (NPG)
Input: Learning rate 17 >> 0.
Input: Learning rate 17 > 0.
Output: Policies Te, = softmax (X0;).
Output: Policies Ne. = softmax(XX0
Initialize parameter 01 E IRd.
Initialize parameter 01 E IRd
while Z do
while > 1 do
0.+1 + 0,+m--X (ddiam- TT, D.,
0c+1 + 02 + (X x)
end while
end while
To understand the difficulty of the optimization problem in Eq. work that has analyzed the convergence of PG methods.
2 it is helpful to consider previous
In the tabular setting, where = K. X Id. and Te softmax () with 0 E K both the rewards and optimal policy can be arbitrarily well approximated. In this case it is known that NPG enjoys (11/t) global convergence rate 44] Table 1]. which has been recently improved to O(e-et) 14 20 17 27). For the case of function approximation, such results have subsequently been extended to log- linear policies, where approximation error is used to characterize the projection step of Eq. (5) In particular, NPG achieves the following sub-optimality gap for all 2 [4] Table 2],
(T" T.,) < c/Vi+ 02 Expprox>
(c: > 0, 02 > 0)
where C and 02 are problem specific constants, n² is the globally optimal policy, no, is produced by
NPG, and éapprox is the approximation error, i.c., the minimum error with which the policy values can be approximated using the features [4] Table 2]. The "optimization error" term / V in Eq. (6)
has since been improved to O(e-ca-t with c3 > 0 in 28 5. Note that if capprox >> 0 then Eq. (6)
insufficient for establishing nz."" r(a") ) = max r(a) as + xo even when such global
convergence is achieved.
The understanding for the standard Softmax PG is even less clear. the tabular case, it known that Softmax PG achieves global convergence asymptotically, i.e., NØ, - r(a") as / - oo 44, with an ((Itt) rate of convergence that exhibits undesirable problem and initialization dependent constants

---

Directly extending this global convergence result to the case of function approximation, Le., log-linear policies, impossible without any additional assumptions on the features, since there can be exponentially many sub-optimal local maxima in the worst case [9. In fact, even with linearly realizable rewards (zero approximation error), whether standard Softmax PG achieves global convergence still remains unsolved [ One intuitive reason why this is difficult result to establish that standard Softmax PG uses the gradient Eq. 4 rather than projection (regression) to perform updates, which is less directly connected to the concept of approximation error.
18].
3 The Limitations of Approximation Error in Characterizing Convergence
is known that there exist representations E R with d < K and R that create expo- nentially many sub-optimal local maxima in Eq. ( 1 Theorem 1J. which makes it impossible to ensure global convergence of PG methods without imposing any structure on the function approxi- mation. Before identifying specific conditions that ensure global convergence, we first explain how approximation error cannot be a useful structural measure for this purpose, by demonstrating that zero approximation error is not a necessary condition for global convergence, and illustrating problem instances with comparable approximation error that render starkly different convergence behaviors across different PG methods. Specifically, we illustrate these points with a set of concrete scenarios, each with 4 actions and 2-dimensional feature vectors describing each action. Since d < K, not every policy can be expressed in these representations, hence the problem instances are unrealizable.
3.1 Global Convergence is Achievable with Non-zero Approximation Error
The results of ( Theorem 1] do not imply that sub-optimal local maxima always appear, as shown in the following.
-1 0 2
Example 1. K 4, d
2, T
and (9,8,7,6) The approximation X r112 /202.6 ~ 14.2338.
-2 0
error is Capprox
min wERd
| r|[2 X (x(XXX)
Note that the approximation error is larger than any sub-optimality gap, i.e., for any policy n,
(T" T) S 3 < Eapprox:
hence the bound in Eq. (6) does not imply global convergence for NPG in this example. Yet, despite the non-7ero approximation error and the inability of existing results including Eq. (6 to establish global convergence on Example [
[and] be shown to reach global maximum. Proposition 1. Denote a" = arg max r(a). With constant 1) > and any initialization 01- E IRd, both Algorithms and guarantee TØ. ~ r(a") as t + oo on Example 7
both Algorithms [
All proofs can be found in the appendix due to space limits. The fact that Softmax PG achieves global convergence in Example is much harder to establish than for NPG, since Eq. 4 involves a complex non-linearity given the presence of the softmax, unlike the linear least squares Eq. (5) used in NPG.
To illustrate the intuition behind Proposition I we use a visualization of the optimization landscape.
A visualization of the optimization landscape of Example I is shown in Figure [a). The bottom -oodemmnsiooal plane the parameter space Ed where d = For each 0 E R. we
Visualization.
calculate To using Eq. 3 and xg using Eq. (). and use Tg r as the vertical axis value of O.
8
7.7
7
7
0
23
20
20
20
20
Esomple
(b) Destpple
(c) Exompee
Figure 1: Visualizing the landscapes in the example problem instances.
To verify Proposition we run Softmax PG and NPG on Example with the same 01 = (6,8) R22
In Figure [a), the optimization trajectories show 85 iterations of NPG and 8.5 x 10th iterations of

---

Softmax PG, both with learning rate 17 0.2. It can be clearly seen that both Softmax PG and NPG eventually achieve expected reward Tg." + r(a*), demonstrating global convergence (Figure c) later shows that the sub-optimality gap (x* - To,) approaches 0).
In summary, Example shows on unrealizable problem instances with non-zero approximation error. This raises the question:
shows that both Softmax PG and NPG are able to achieve global convergence
Iy non-zero approximation error useful for churacterizing global convergence?
3.2 Global Convergence is Irrelevant to Non-zero Approximation Error
We answer the above question negatively. By comparing alternative problem instances with similar approximation errors but different convergence behaviors, we illustrate how approximation error is not able to distinguish between scenarios where global versus local convergence obtained.
-1
2 E [ and (9,8,7,6)* ERK, The
Example K 4, d X
0 (x r r112 200 ~ 14.3178.
-2
approximation error is
The only difference between Examples 1 and 2 that the second and third columns of X have been exchanged. The approximation error remains similar to that of Example || Using the upper bound of Eq. ( one might therefore expect similar sub-optimality gaps (л* TT,) to be demonstrated by the algorithms, since the r.h.s. contains similar approximation errors. However, as shown in Figure (b, using the same initialization and learning rate, Softmax PG obtains ,ø,"" 8 = r(2) < sub-optimal deterministic policy, while NPG continues succeed.
r(a") as it converges
Lest one believe that NPG is globally convergent, the following example, where the first and second columns of X are swapped, illustrate an analogous failure for NPG but not Softmax PG.
0
Example K = 4, d X
E dRdx and r = (9,8,7,6) E R The
-2 1 0 X r11 221 14.5602.
approximation error
X xx
Here again the approximation error is close to that of Example Yet, Figure [c) shows that NPG achieves TØ. - < r(a*) as converges to sub-optimal solution, while Softmax PG succeeds.
In summary, the Examples 1, and all have similar approximation errors, yet Softmax PG achieves global convergence on Example | but reaches bad local maxima Example 2 while NPG succeeds on Example and fails on Example 3 Note that these examples can be re-scaled to have exactly the same approximation errors while demonstrating the same convergence behavior of the algorithms. From these findings we conclude that, if there is any quantity that can predict whether global versus local convergence is obtained by Softmax PG NPG, that the quantity cannot be approximation error alone. This motivates to investigate the question: what is the right quantity to characterize global convergence for unrealizable problems?
3.3 Global Convergence Characterization is Algorithm Dependent
make one more key point. From Tib) and Figure Tc). NPG achieves global convergence on Example but fails on Example while, conversely, Softmax PG succeeds on Example and fails on Example 2 This difference indicates that whatever condition characterizes global convergence, it must be algorithu dependent, even for the closely related algorithms Softmax PG and NPG. Therefore, one has to study the conditions for Softmax PG and NPG respectively (rather than one condition for both algorithms), which motivates the refined question:
What conditions characterize global convergence of Softmax PG and NPG in unrealizable problems?
New Characterizations of Global Convergence for PG Methods
From these observations, it is clear that whatever quantity characterizes the global convergence of methods, it cannot be based solely on approximation error and must be algorithm dependent. Therefore, study distinct global convergence conditions for Softmax PG and NPG respectively.
5

---

4.1 Reward Order Preservation with Adequate Features is Sufficient for PG Convergence
We now investigate a global convergence condition for Softmax PG under log-linear policies.
Intuition. Consider Example where Softmax PG achieves global convergence. From the land- scape shown in Figure there appears to be monotonic path from any initialization point that allows gradient ascent to reach the optimal plateau with reward r(a") = 9. Intuitively, this arises be- cause the actions' rewards seem to be nicely "ordered". For example, starting from f2 = (6.8) E Rd such that no,"" r R 6, Softmax PG is able to improve its expected reward eventually to = r 7, since there exists sub-optimal plateau with a higher reward 7 right beside the lowest plateau with reward 6. Next, Softmax PG continues to improve its expected reward eventually to Te r & 8 by "climbing" toward another neighboring plateau with a higher reward. Finally, this process ends with Softmax PG successfully arriving at the optimal plateau with reward r(a") = 9.
By contrast, in Example 2 as shown in Figure bb), Softmax PG gets stuck on a bad plateau with a local maximum reward of 8. Visually, Softmax PG stops improving its expected reward on this sub- cul-oopimalppp plateau, because it is "surrounded" by two lower plateaus with rewards 6 and 7, which breaks the nice "ordering" of the expected reward landscape and traps the gradient ascent trajectory on a sub-optimal plateau from which there is no monotonic ascent to global optimality.
Verifying reward order preservation. Based on the above intuition and observations, we conjec- ture that the ordering structure between the different rewards is a key property behind the global convergence of Softmax PG. We can verify this conjecture in each of the Examples 3o deter- mining whether the feature matrix X E IR xd allows the same action ordering as the reward vector r E R-K to be realized. For Example 1 note that with w (-1,-1) E IRd, we have
r' Xw = 1, 22) RRK
(8)
which preserves the ordering of RKK such that for all j, E [K], r(1) r(f) if and only if r'()) > r((). Similarly, for Example 3 if we let w = (-3, -1) then we have r' = Xw
(3,2, (3, which also preserves the order of over actions. Softmax PG converges to globally optimal reward in both of these examples.
By contrast, for Example 2 it is impossible to find any Rd such that Xw preserves the order of the rewards r. To see why, consider any w = (wo(1), =2)) T and note that
,' xx = (-2 (2), (2). - -w(1, w())
(9)
To preserve the reward order, we require both -2 22) > w(2) (which would imply w2)) < 0)
and (1) > 2- w(1) (which would imply w(1) < 0), but these two conditions imply w(2) < 0 <
(1,,), which must reverse the order of the second and third actions. This is an example where PG
can fail to reach global optimum.
Main Softmax PG result. We formalize the above intuition by proving the following main result, which establishes that reward order preservation with adequate representations is a sufficient condition for the global convergence of Softmax PG under log-lineat function approximation.
Theorem (Reward order preservation, non-domination features). Given any reward r E R-K and feature matrix X E RKxd Denote x; E Rd as the i-th row vector of X. If x. > x. 2z for all j + i, and (ii) there exists at least one w E Rdd, s.t., r' == Xw preserves the order of i.e. for all i [K], r(i) > r(j) if and only rf > (j), then for any initialization 0, E Rdd Algorithhm ! with constant learning rate 17 achieves global convergence of nD. - r(a²) as t + co.
A few remarks about this theorem are in order.
Examples to 3 all satisfy the non-domination condition (i) on X, and their differences lie in satisfying reward order preservation or not. However, the following example shows that if the condition (i) on X is removed, then global convergence is not always achievable for even linearly realizable rewards (with zero approximation error).
0
- 10 0
Proposition 2. Let K 3, d 2, T
E
Rdd and r Xw = 22)
-2
4
1
where w = (-1, -T) E Rd. With initialization 0 (- 2n2, In T,T, Algorithm does not achieve global convergence, i.e. Te, (1) A 1 as o0.

---

Generalization of tabular and linear realizability. When d = K and X = Id, i.e. the softmax tabular parameterization 7g = softmax(0), it is always true that Xr r preserves the order of r. Consequently, Theorem recovers the global convergence result for PG in the softmax tabular setting 22 as a special case. More generally, for non-domination features, when the reward linearly realizable, such that Xw = r for some w E Rd, the global convergence of Softmax PG also follows since r preserves its own order when the approximation error is zero.
from Theorem !
Corollary (Linearly realizable rewards, non-domination features). Given any reward r E RR and feature matrix X E ggxd Denote 2; E I as i-th row vector of X. If (i) x 0; x7 x2 for all i * i, and (ii) there exists RR s.t., Xw then for any initialization 01 E R Algorithm 1 with a constant learning rate > achieves global convergence of Tg. + r(a") as t + cc.
It is worth mentioning that Proposition 2nn Corollary Tacillrrrttgggheee together answer a question which still remain unsolved in PG literature []: with linearly realizable rewards (zero approximation error), whether standard Softmax PG achieves global convergence? Proposition X shows that linearly realizable reward on its own is not enough to guarantee global convergence, while Corollary [ shows that with adequate features, linearly realizable reward implies global convergence. Note that the NPG global convergence result in 4 such as Eq. (6) does not apply to standard Softmax PG.
Ordering does not determine approximation. As already illustrated in Section 3 approximation error is not adequate for capturing the global convergence of Softmax PG. It is important to emphasize that the existence of an order preserving reward r' is very different from having a small approximation eπror. When the approximation error is zero, then an order preserving reward (equal to r) always exists. However, in general, r' can take very different values than r. and hence have very large approximation error, yet still enable global convergence as shown in Examples and
Proof idea. The idea behind the proof of the main theorem consists of three parts. We provide a sketch of the proof here; the full proof is given in Appendix A First, starting from any initialization 0, E IRd, Algorithm guarantees that To, will approach (generalized) one-hot policy as t + co. To
see why, first note that TH r is 3-smooth over 0 E Rd with some B >> 0 (Lemma 3 in Appendix B).
since the softmax transform is smooth [4] 22] and the feature matrix X has bounded values. This
implies that using sufficiently small constant learning rate 0 17 2/B we obtain,
d F r d0,
No. 2
2 0.
(10)
Note that xo r is upper bounded by r(a"). According to the monotone convergence, &o.r - e S r(a") ) as oo. This fact combined with Eq. 10 implies
Te. 0 co. Next, special
db.
x.. r
co-variance structure of softmax PG (Lemma 4 shows that and To. approaches a (generalized) one-hot policy as t + Do.
- O implies that ||0e||2 + oo
dB.
1
Lemma 1. Under the same conditions as Theorem 7 and r(i) F r(j) for all i + j (unique action reward), Algorithm assures |0:112 cc and To, (i) for an action i [K]
oo.
Remark 1. Removing the unique action reward condition in Lemma 7 makes Te, approach generalized one-hot policy (rather than strict one-hot in Lemma 7 as t xc as result.
According to Lemma I
0, grows unboundedly. Intuitively, this can be seen in Figure a), where there are no stationary points in finite region.
Second, for any vector r' that preserves the order of r. we establish the following key lemma.
Lemma 2 (Non-negative covariance of order preservation). If E && preserves the order of E RK, for all i,j E [K], r(i) > r(j) iff r (1) r' rj), then for any policy E A(K).
(diag(m) नम T) Cov (r', r) 0.
(11)
Now consider the direction w E Rd such that r' = Xww preserves the order of w 0.41
r. We have,
w T 02 17- w X (diag(TT.)) To, TT. r
(by Algorithm []]
(12)
w T 0, + n r' (diag(TT.)) - -TO,
me.) To, 1r)r (r' ==== Xw)
(13)
2 w
T 0.
(by Lemma 2
(14)
7

---

Third, take sub-optimal action i E [K] with r(1) < r(a"), and we show that the assumption To, (i) + 1 as + do leads to a contradiction.
To that end, first observe that this assumption implies that for all large enough time 2 1,
X0 ||0:||2_ (a):
(i)
max ae K]]
(15)
|
which means that the sub-optimal action E
[K] always has the largest score (since its probability Te. (i) + is always the largest). Moreover, differences between actions' scores are unbounded, due to Fe. (1) exp (1 - [X0,1())
for all other actions j +
Te, (d)
Consider Example I for illustration. The top view of Figure 0 a) is shown in Figure 2 a). Take i = 2 and r(t) - 8, and assume T0.
20
stays in the green (sub-optimal) region of Fig-
10
ure a). excluding its boundaries. This green
0
region is partitioned in Figure 2bb,, where the
10
dark sub-region contains U/ E Rd such that
[2 (a*) is the second largest component among all a + 2, and the light sub-region is the remaining.
-20
-30
-20
(a) Top of Exsuppee
(b) Illustastion the third part.
The argument completed by addressing the two cases: (i) If |0+112 stays in the dark sub-
Figure 2: Idea illustration.
region where on Rd belongs to, then ~0,r r(i) 8 must occur in finite t << co, implying To,
(o) (i) A 1, contradicting the assumption. Intuitively, the contradiction occurs because the dark sub-region closer to higher plateau with reward 9, and scaling up 0, 's magnitude in this sub-region eventually ensures n > r(i) 8. (ii) If
8. [[ stays the light sub-region which contains V2 E Rd.
then w OTO0= uTo 0g must occur in finite time l < xc, implying that T0:112 will enter the dark sub- region, reducing to the first case. This argument depends on Eq. [12 and key observation showing that u 0c+1 < u. 6,, where is a "worse" direction such that [X (a max.e(K] [Xu] (a) for some a E [K] with r(a < r()).
0, To summarize, e. cannot always stay in the green sub-optimal region in Figure a)), which implies must eventually enter the optimal region that contains w and stay in that region. By Lemma then obtain (e,(a)) (a*) 1 and nT. r r(a") as & + oo (see appendix).
that
Pe 1.
4.2 Optimal Action Preservation is Necessary and Sufficient for NPG Convergence
Next, we investigate the global convergence conditions for NPG under log-linear policies. Unlike Softmax PG, the key property for determining global convergence of NPG is whether the projection of the rewards r onto the feature representation X preserves the top ranking of the optimal action.
Intuition and demonstration. First consider Example D where NPG successfully converges to global maximum. From Algorithm 2
simple calculation shows,
X0 X0; X(x - X0, +
-4,-4-11 12,)
(16)
which implics that the optimal action a 1 always receives the largest update to its score [X0][(a)) in each iteration. Next, take sub-optimal action a = 2, as an example, and observe that,
To (a")
no. (a") Toa (a)
no. (a") To.
T8 (a)
exp {n (f(a") f(a)))
exp
5
(17)
by Eq. (3), where F = X(X X) - Using constant learning rate 7) 0 and applying Eq. 17
we have that TØ, (a") grows exponentially with f, indicating that ne, (a*) - 1 as t + 0o since the same argument works for any sup-optimal action * a". Moreover, the rate is O(e since
(7* - no. r |||| oo (1 =a, (a")). The (e--et) rate matches the results softmax tabular
settings [14 20 17 27
8

---

Second, consider Example 2 where NPG fails to converge to global maximum. Using similar calculations to Eq. (T6) we obtain,
1
X0.+1 X0, + π- X0, + + 3 --,-6
(18)
which implies that a sub-optimal action always receives the largest update on its score [X0,, each iteration. The failure in Figure Tb) is then verified by similar arguments around Eq. (77
Main NPG result. Based these observations, it is evident that for NPG converge globally, it important for the optimal action to eventually always receive the largest update to its score, which makes it critical that the least square projection X (X"X))' X '", preserves the top ranking of the optimal action. We formalize this intuition by establishing the following main result.
Theorem (Optimal action preservation condition). For a constant learning rate 17 > 0, a necessary and sufficient condition for Algorithm 2 to achieve global convergence ng." r(a") as t + 0o from any initialization 01 E Rddd that f(a") > f(a) for all + a", succ that a" = arg max r(a), and f == X (x (XTx)= T the least squares projection of r onto the column space of X. If the for some 0.
condition is satisfied, then the rate of convergence is (T² To.)² "ree)re T
Proof idea. When the optimal action preservation satisfied, similar arguments to Eqs. (6)) and (1
guarantee that TT, (a") grows exponentially with indicating that TT. (a") ) + + 00.
The constant > 0 in Theorem depends on the gap of f. i.c., f(a*) maxaşa f(a), which finds similarities to NPG results tabular settings [14 [5]. The main difference is that the gap of true reward r in tabular cases is replaced with the gap of least square projection f in function approximation settings in Theorem This similarity is an evidence for improving the rate to super-linear by using geometrically increasing step sizes, as in tabular settings
28 6
One-sided Approximation Error. For NPG, Lemma 6.2] introduces a "one-sided approxima- tion error" quantity, which aims to overestimate the advantage of the optimal action a', (xa. TTr-=" X xo.) r(a") _ r (f(a") -T
G == r==())
(19)
This quantity relaxes the notion of approximation error and still guarantees the global convergence of NPG, since if Et= & E o(T), then NPG with E O(1/v achieves global convergence [4] Lemma 6.2]. We note however that Eq. (19) has two limitations: (i) Eq. (19) depends the entire update trajectory {6s h22. which hard to verify. By contrast, the optimal action preservation condition in Theorem 2 only involves problem quantities X and r. (ii) It not clear whether Eq. (19)
a necessary condition for global convergence, while optimal action preservation is proved above to be both necessary and sufficient.
Simulation Study
We conducted additional simulations to check the theoretical results. First, we check whether the strict inequality of i(a") > F(a) for all A a" in Theorem
2 is required for NPG global convergence.
-1
1
Example 4. K = 4, = 2
E BRdx and r = (9,8,7,6)7 E RR The
-1 0
1 0
best for r is = X (x r- (1,1,-1,-1)
Example has f(a") = f(1) f(), which violates the strict inequality condition of f(a") > f(a) for all A a² The consequence that NPG guarantees makes it impossible for ne. (a*) - 1 as t cc. This is observed in Figure Bl a), supporting that the strictly inequality condition in Theorem is indeed necessary. The initialization is 61 = 10)
ne, (a)) ne, (a")
Te (2) for all 1, which
Te,
and r) = 0.2. We run 150 iterations for NPG and 1.5 10" iterations for Softmax PG.
As shown in Figure Bib), the quantity log (TT - - is linear function of time I, implying that (xx TØ, Tr E Ole-st) with 0. This supports the convergence rate results in Theorem 2 Here 01 and are the same as in Figure aa].
Second, we rum 150 iterations of NPG on Example [
Third, we check whether the condition in Theorem is required for Softmax PG global convergence.

---

PQ
NPG
83
190
log
8888888
(a) Example
(b) log (5"
m6.
(c)
log(""
(s*
<o,)
(d) Example
Figure 3: Simulations for verifying theoretical results.
0
-
0 1
Example 5. K == 6, 2, x
1 1 and r 7,,,,,,),),
Similar to Eq. 9 it impossible to find any RR such that ra:rr'== X preserves the order of in Example However, as shown Figure Softmax PG achieves To. - rr(aaa)) 9, indicating that the reward order preservation condition in Theorem is sufficient but not necessary for PG to achieve global convergence. The initialization is 0 = (10, -2) and = 0.2. We run 100 iterations for NPG and 2 10th iterations for Softmax PG. Note that NPG behaves erratically Example
(which does not satisfy its global convergence conditions), by first entering then leaving the optimal platcau, eventually approaching sub-optimal solution.
Finally, we run 10 iterations of Softmax PG on Example using the same 1) and 01 as in Figure I a).
Figure 3 c) shows that the slope of log (T* xg,)² over log approaches 1, indicating that the
global convergence rate is (x* - ) E O11(t, matching the softmax tabular setting results (2]
Discussions
Checking ordering-based conditions. Checking the existence of w E IR in Theorem is known linear feasibility in literature (Н.. i.e., determining whether intersection. In particular, suppose X E IR xx and r E IR is sorted, i.e., r(1) 2 r(2) 2
inequalities has a non-empty
r(K). Denote z; E R as the i-th row vector of X. The linear feasibility problem in this case is to check if there exists w E Rd, such that for all i [K 1]. x w 2 x;+1 w. Linear feasibility can be cast as linear programming (LP) using dummy objective and keeping the constraints, hence any LP technique, such as the ellipsoid method, can be used to solve it ΑЛО. On the other hand, checking the optimal action preservation in Theorem Saveemm@eeque requires the same information in calculating approximation error || - rll2 min
| - rlly, since arg max [K] f(a) = arg max [E(K] r(a)
weRd
can be immediately verified after calculating the projection F X (XTxx) -
Generalization to Markov decision processes (MDPs). Our work provides some new and useful insights for understanding more complex settings, but it requires further investigation resolve this highly non-trivial problem for general MDPs. See Appendix C for detailed discussions.
Conclusions and Future Work
We believe this work opens new directions for understanding PG-based methods under function approximation, going well beyond the conventional approximation error based analysis. The major technical findings involve ordering-based conditions and relevant techniques (covariance and global convergence). Identifying exact necessary and sufficient conditions for the global convergence of Softmax PG remains future work. Extending the results and techniques to general MDPs is another important and challenging next step. Combining function approximation with recent results on stochastic on-policy sampling (20] is another interesting direction for agnostic learning. Investigating whether these new global convergence conditions might be used to achieve better representation learning is of great interest for algorithm design. Generalizing the proof techniques to other scenarios where non-linear transforms (activation functions) interact with low-dimensional features through gradient descent, such as in neural networks, is another lofty ambition.
10

---

Acknowledgments and Disclosure of Funding
The authors would like to thank anonymous reviewers for their valuable comments. CS, DS gratefully acknowledge funding from the Canada CIFAR Al Chairs Program, Amii and NSERC.
References
[1] Yasin Abbasi-Yadkori, Peter Bartlett, Kush Bhatia, Nevena Lazic, Csaba Szepesvari, and Gellért Weisz. Politex: Regret bounds for policy itcration using expert prediction. In International Conference on Machine Learning, pages 3692-3702. PMLR, 2019.
[2] Yasin Abbasi-Yadkort Nevena Lazie, Csaba Szepesvari, and Gellert Weisz. Exploration -eniraatooo-ehhnneeed politex. arXiv preprint arXiv:/908 10479, 2019.
[3] Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun, PC-PG: Policy cover directed exploration for provable policy gradient learning. Advances in neural information processing systems, 33:13399-13411 2020.
[4] Alckh Agarwal, Sham M Kakade, Jason D Lec, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-76, 2021.
[5] Carlo Alfano and Patrick Reheschini. Linear convergence for natural policy gradient with log-linear policy paramctrization. arXiv preprint arXiv:2209. 15382, 2022.
[6] Carlo Alfano, Rui Yuan, and Patrick Rebeschini. A novel framework for policy mirror descent with general paramctrization and linear convergence. arXiv preprint arXiv:2301. 131.1199.11 2023.
[7] Shalabh Bhatnagar, Richard S Sutton, Mohammad Ghavamzadeh, and Mark Lec. Natural actor- critic algorithms. Automatica, 45(1 1):471122482, 2009.
[8] Semih Cayci, Niao Hc, and Rayadurgam Srikant. Linear convergence of regulie-r natural policy gradient with linear function approximation. arXiv preprint arXiv:2 2021.
[9] Minmin Chen, Ramki Gummadi, Chris Harris, and Dale Schuurmans. Surrogate objectives for batch policy optimization in one-step decision making. Advances in Neural Information Processing Systems, 32, 2019.
[10] Zaiwei Chen, Sajad Khodadadian, and Siva Theja Maguluri. Finite-sample sample analysis of off off-policy natural actor critic with linear function approximation. IEEE Control Systems Letters, 6:2611-22 1-16,, 2022.
[11] Martin Grötschel. László Lovász, and Alexander Schrijver. Geometric algorithms and combinatorial optimization, volume 2. Springer Science & Business Media, 2012.
[12] Tuomas Haamoja, Aurick Zhou, Pieter Abbecl, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International conference on machine learning, pages 1861-1870, PMLR, 2018.
[13] Sham M Kakade. A natural policy gradient. In Advances in neural information processing systems, pages 1531-1538, 2002.
[14] 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, 2021.
[15] Sajad Khodadadian, Prakint Raj Jhunjhunwala. Sushil Mahavir Varma, and Siva Theja Maguluri. On linear and super-linear convergence of natural policy gradient algorithm. Systems & Control Letters, 164:105214, 2022.
[16] Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999.
[17] Guanghui Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. Mathematical programming, 198(1): 1059-1106, 2023.
[18] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Softmax policy gradient methods can take exponential time to converge. In Conference on Learning Theory, pages 11107-1118 PMLR, 2021.
[19] Yan Li, Guanghui Lan, and Tuo Zhao. Homotopic policy mirror descent: Policy convergence, implicit regularization, and improved sample complexity. arXiv preprint arXiv:2201 09457, 2022.
[20] Jincheng Mci, Wesley Chung, Valentin Thomas, Bo Dai, Csaba Szepesvari, and Dale Schuurmans. The role of basclines in policy gradient optimization. Advances in Neural Information Processing Systems, 35:17818 17830, 2022.
[21] Jincheng Mei, Chenjun Xiao, Bo Dai, Lihong Li, Csaba Szepesvári, and Dale Schuurmans, Escaping the gravitational pull of softmax. Advances in Neural Information Processing Systems, 04221130-21444 2020.
11

---

[22]
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schaurmans. On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning, pages 6820-6829. PMLR, 2020.
[23] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference machine learning, pages 1889-1897, 2015.
[24] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint
2017.
[25] Richard Sutton, David A McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, pages 1057-1063, 2000.
[26] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3):229-256, 1992.
[27] Lin Xiao. On the convergence rates of policy gradient methods. Journal of Machine Learning Research, 23(28)):1-36, 2022.
[28] Rui Yuan, Simon S Du, Robert M Gower, Alessandro Lazaric, and Lin Xiao. Linear convergence of natural policy gradient methods with log-linear policies. arXiv preprint arX0v:2110.01400, 2022.
12


Reviews:
[{"review_id": "ekbmAzhv2l", "reviewer": "Reviewer_hbxK", "summary": "This paper considered the problem of global convergence condition of policy gradient (PG) methods with linear function approximation motivated by three observations: i) global convergence under linear function approximation can be achieved without policy or reward realizability; 2) approximation error is not a critical factor for global convergence; and 3) conditions for characterizing global conference should be algorithm-dependent. Based on these observations, the authors developed new ordering-based conditions for global convergence of PG methods: i) For Softmax PG, a sufficient condition for global convergence to occur is that the representation preserves the ranking of the rewards; and ii) For natural PG (NPG), the necessary and sufficient condition of global convergence is that the projection of the reward onto the representation space preserves the optimal action’s rank.\n", "questions": "I appreciate the new findings and fresh insights of the ordering-based global convergence conditions for PG methods with linear function approximation. One immediate question that comes to my mind after reading this paper is how restrictive (or non-restrictive) these ordering-based conditions are. For example, for the Softmax PG method, it appears to me that given $r$ and $X$, checking the existence of a $w$ that preserves the reward ranking may not be a simple task. Is there a systematic way to check the existence of such a $w$? Is there any other condition equivalent to order-preserving but easier to identify and check? Could the authors discuss how large the subspace of $X$ in $\\mathbb{R}^{d}$ that satisfies the order-preserving condition is? The same questions can also be asked for NPG.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. This paper develops a new set of global convergence conditions for PG methods with linear function approximation, which advances the state of the art of understanding PG methods (Softmax PG in particular).\n\n2. The proof strategies and algorithm analysis techniques are novel.\n\n3. Motivating examples in this paper are insightful.\n", "weaknesses": "1. The paper could benefit from constructing a bit more larger-scale experiments.\n\n2. This paper could have some further discussions on the implications of the ordering-based conditions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate that the reviewer understands and recognizes the contributions of this work. We address the main concerns as follows.\n\n>**Is there a systematic way to check the existence of such a $w$ given $r$ and $X$:** \n\nYes, checking the existence of $w$ is known as **linear feasibility** in the literature (Grötschel et al., 2012), i.e., determining whether a set of inequalities has a non-empty intersection. In particular, suppose $X \\in \\mathbb{R}^{K \\times d}$ and $r \\in \\mathbb{R}^K$ are given and that $r$ is sorted, i.e., $r(1) \\ge r(2) \\ge \\cdots \\ge r(K)$. Denote $x_i \\in \\mathbb{R}^d$ as the $i$th row vector of $X$. The linear feasibility problem in this case is to check if there exists a $w \\in \\mathbb{R}^d$, such that, for all $i \\in [K-1]$,\n\\begin{align}\n    x_i^\\top w \\ge x_{i+1}^\\top w.\n\\end{align}\nLinear feasibility can be cast as linear programming using a dummy objective and keeping the constraints, hence any LP technique, such as the ellipsoid method, can be used to solve it (Grötschel et al., 2012).\n\n>**How large the subspace of $X$ that satisfies the order-preserving condition is? The question could also be asked for NPG.**\n\n That is an interesting question. **First**, this work shows that the space is strictly larger than the set of $X$s that satisfy linear realizability / zero approximation error (i.e., the set of $X$ such that there exists $w \\in \\mathbb{R}^d$ to satisfy $X w = r$). From Line 232 in the paper, we know that zero approximation error implies order preservation, but **not vice versa** (Examples 1 and 3). **However**, determining how much larger the space is would require choosing a metric, such that we can compare space sizes. This needs further investigation.\n\n[1] Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combinatorial\noptimization, volume 2. Springer Science & Business Media, 2012."}, {"review_id": "jaG23lS8B3", "reviewer": "Reviewer_m2vF", "summary": "The paper studies softmax policy gradient and natural policy gradient methods for multi-arm bandits problems using linear function approximation. The authors provide examples to illustrate the global convergence of these methods when the standard function approximation error is not zero. To better characterize the global convergence, the authors provide the ordering-based conditions on rewards. Some numerical examples are provided to verify the proposed conditions. ", "questions": "Please see questions in Strengths and Weaknesses. \n\nHere are some other questions.\n\n- Why is it fair to compare function approximation error with ordering-based conditions or optimal action gap conditions? The function approximation error is a general quantity that does not depend on MDP structures, while ordering-based conditions depend on the MDPs. In a basic tabular case, ordering-based conditions do not necessarily hold, e.g., equal rewards at any action, but the softmax function approximation error is zero. Hence, such conditions do not explain the basic case.\n\n- The convergence rate seems to be vague in the main paper, which has a dependence on the gap between optimal action and second optimal action, which is known in the tabular case [12, 18]. How much does your rate analysis go beyond the existing analysis? any rate improvement? \n\n- For softmax PG, reference [15] shows that it can take exponential time to converge in a hard MDP instance. How does ordering-based condition rule out the hard MDP instance? \n\n- The setup is limited to deterministic algorithms with exact gradients, which is an ideal setting. Can the authors apply them to practical stochastic bandit problems? ", "limitations": "Yes. ", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "**orginality**\n\n- The studied deterministic policy gradient methods are well-known in the literature. The authors re-revisit the convergence of these methods for multi-arm bandits with linear function approximation. Such convergence hasn't been studied directly. \n\n- The authors show necessary (and sufficient) conditions for two policy gradient methods to converge in the linear function approximation setting. The analysis generalizes some similar analysis, e.g., reference [18] to linear function approximation. Technical comparisons with the existing analysis are not very clear. \n\n**quality**\n\n- It seems that the global convergence is abused in some way, since the existing convergence studies in the linear function approximation investigate different sub-optimality gaps, e.g., [4] is based on the regret analysis while [24] utilizes the mirror descent analysis. \n\n- It is not clear how to interpret 'Approximation error is not a key quantity for characterizing global convergence in either algorithm'. The reference [24] shows that zero approximation error leads to global convergence. Although this result does not show necessity, approximation error is still an important quantity we use in practice.\n\n-  Compared with approximation error, it is less clear how to check optimal action perseveration condition, especially when the action space is large. So, weaknesses haven't been clearly stated. \n\n**clarity**\n\n- The paper is structured well, but it lacks of technical comparisons with existing results. \n\n- The visualization is not clearly stated, e.g., axes, error bars, speed. \n\n**significance**\n\n- Since the function approximation is widely used in reinforcement learning, this work is important. It provides new understandings of policy gradient methods in bandit cases. ", "weaknesses": "- Technical comparisons with existing results are not detailed, sometimes vague. For instance, in line 96 why (4) and (5) for bandits can be used as RL methods; in line 102 which work provides $1/\\sqrt{t}$ rate; line 121, why 'insufficiency'; line 152, how to check global convergence; line 191, what of algorithms the quantity must depend on? Please state claims with concrete justifications. \n\n- Optimal action perseveration generalizes the analysis in reference [18]. It is similar to the gap of optimal action and second optimal action used in literature, e.g., reference [12] and the paper: Regret Analysis of a Markov Policy Gradient Algorithm for Multiarm Bandits. These quantities seem to be known important for global convergence and the authors generalize them to linear function approximation. Therefore, it is important to clarify the connections and position the work in the literature properly. \n\n- The usefulness of proposed ordering-based conditions is still questionable. First, the generalization to MDPs is not provided. Second, it is not clear how to check such conditions when state/action spaces are large, even infinite. \n\n- The paper focuses on multi-arm bandits and deterministic policy gradient methods, which have a large gap with reinforcement learning. This work seems to be still in progress and significant effort is needed to generalize this work for serious publication. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The review seems to focus on issues arising from misunderstanding or miscommunication. We hope the following can help clarify matters.\n\n>**global convergence is abused ...**\n\n**First**, global convergence simply means $\\pi_{\\theta_t}^\\top r \\to r(a^*)$, i.e., policy's reward approaching that of the optimal policy, as mentioned in Lines 230 and 316. It is hard to imagine a more straightforward definition. **Second**, alternative analyses do not change the meaning of global convergence. Sub-linear regret implies that the averaged performance approaches $r(a^*)$. Our global convergence results are for last-iterate, which implies sub-linear regret.\n\n>**... not clear how to interpret Approximation error ...** \n\nWe have explained this clearly in Section 3. **First**, Softmax PG and NPG can still achieve global convergence on Example 1 with non-zero approximation errors. This does not contradict \"zero approximation error leads to global convergence\". **Second**, Examples 1 and 2 have similar non-zero approximation errors but different algorithm behaviors, which makes it impossible to use non-zero approximation error to discriminate the two examples (global convergence or not). **Finally**, we agree that \"approximation error is still an important quantity\", but our observations also clearly show that non-zero approximation errors are not enough to characterize global convergence.\n\n>**... less clear how to check optimal action preservation condition**\n\nChecking the condition for NPG is no harder than checking the approximation error. To determine approximation error $\\\\| \\hat{r} - r \\\\|_2 =  \\min\\_{w \\in \\mathbb{R}^d} \\\\| X w - r \\\\|_2 $ one needs to calculate projection $\\hat{r} := X^\\top (X^\\top X)^{-1} X^\\top r$. Optimal action preservation $\\text{argmax}\\_{a \\in [K]}{\\hat{r}(a)} = \\text{argmax}\\_{a \\in [K]}{r(a)}$ can be immediately verified from the same calculation. Checking the condition for PG requires a linear feasibility check (i.e., a special case of an LP), as discussed in the response to Reviewer hbxK. Note that checking conditions both PG and NPG only requires the same problem information ($X$, r, and $\\hat{r}$) as checking approximation error.\n\n>**in line 96, (4) and (5) ...** \n\nIt is well known that general Softmax PG and NPG methods are foundations of the standard RL methods mentioned. Eqs. (4) and (5) are their updates applied to the one-state setting. \n\n>**in line 102, $1/\\sqrt{t}$ ...** \n\nSorry for the typo. [4, Table 1] contains the correct result of an $O(1/t)$ rate.\n\n>**line 121, insufficiency...**\n\nAs Section 3 shows, small approximation error is neither necessary nor sufficient for the global convergence of PG or NPG.\nZero approximation error (i.e., linear realizability) is not necessary in either case, although it is sufficient for NPG, and proved sufficient for softmax PG for the first time in this paper. We could consider replacing \"insufficiency of\" with \"limitations of\".\n\n>**line 152, check global convergence...**\n\nAs shown in Figure 3(c), we use sub-optimality gap $(\\pi^* - \\pi_{\\theta_t})^\\top r$ to ascertain global convergence.\n\n>**line 191, algorithm dependent ...**\n\nSection 3.3 already demonstrated that the condition must depend on the specific update considered (e.g., Softmax PG vs. NPG). Therefore, one has to study the conditions for Softmax PG and NPG **separately** (rather than one condition for both algorithms).\n\n>**... generalizes the analysis of references [18,12] ...**\n\nOur new results for function approximation are not covered by any of those papers. The gap we consider is for $\\hat{r}$, which is different than the reward gap of $r$ in those papers.\n\n>**The usefulness ... large, even infinite.**\n\n**First**, the common author response provides a detailed discussion of the MDP case, illustrating how the ideas provide useful initial insights for MDPs. **Second**, for large action spaces, checking new conditions are no harder than approximation error, as explained above. **Third**, for infinite action spaces, it is also infeasible to exactly determine the approximation error in general.\n\n>**... serious publication.**\n\nUnderstanding the one-state and deterministic settings are necessary first steps before understanding the more involved MDP and stochastic settings. The significance of our findings seem to be well recognized by the other reviewers.\n\n>**Why is it fair to compare function approximation error ...**\n\nTo our knowledge, approximation error (and its variants) has been the only quantity considered for characterizing function approximation quality in PG analysis. It is therefore necessary to discuss approximation error when studying the convergence of PGs with function approximation. \n\n>**approximation error ... does not depend on MDP ...**\n\nThe approximation error $\\min\\_{w \\in \\mathbb{R}^d}{ \\\\| X w - r \\\\|_2}$ clearly depends on the problem quantity $r$, as do the order-based conditions.\n\n>**... do not explain the basic case.**\n\nConsider $r = \\mathbf{1} \\in \\mathbb{R}^K$ as mentioned. Consider $w = \\mathbf{0} \\in \\mathbb{R}^d$, such that $r^\\prime = X w = \\mathbf{0}$. Note that $r^\\prime$ preserves the order of $r$ by definition (for all $i, j \\in [K]$, $r(i) > r(j)$ if and only if $r^\\prime(i) > r^\\prime(j)$ as in Line 229).\n\n>**... any rate improvement?**\n\nOur results address the function approximation case, which is well beyond tabular analyses [12,18]. Improving rates for the tabular setting is not a focus of this work. It is certainly possible to consider increasing stepsizes [23] for improvement, which is beyond the scope of this paper.\n\n>**... hard MDP instance?**\n\nIt is not possible to rule out hard MDP instances in general. The tabular case is recovered as a special case (Line 232). If hard MDP instances were avoided, they would be avoided in the tabular case, which would contradict [15]. \n\n>**... stochastic bandit problems?**\n\nThis is mentioned in the conclusion as future work, and we are working to obtain  results in this direction.\n"}, {"review_id": "7NgFWPgehI", "reviewer": "Reviewer_P4aQ", "summary": "This paper challenges (arguably) the current best known policy gradient (PG) convergence analysis, which is the conventional approximation error based analysis originally proposed by the seminal work of Agarwal et al. (2021). To this end, the authors consider the finite-arm bandits with log-linear policy and study the conditions of the global convergence of PG and natural policy gradient (NPG). \n\n**First**, by carefully designing numerical simulations, the authors show that global convergence can be achieved even if the parameterized policy space can not cover the full policy space, or the approximation error is not zero. Consequently, the approximation error is not a key quantity for characterizing global convergence in either algorithm under linear function approximation.\n\n**Second**, the authors establish new conditions of the global convergence of PG and NPG for the same setting, separately. For NPG, the necessary and sufficient condition of the global convergence is whether the projection of the reward vector onto the feature map strictly preserves the top ranking of the optimal action. For PG, the sufficient but not necessary condition of the global convergence is whether there exists a point in the image of the feature map such that it preserves the entire ranking of the reward vector. These conditions are again well supported by numerical simulations.\n\n\n\nAgarwal, Alekh, Sham M. Kakade, Jason D. Lee, and Gaurav Mahajan (2021). On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift. Journal of Machine Learning Research 22.98, pp. 1–76.", "questions": "First, I have a clarification question. The authors claim that they solve an open problem left by Agarwal et al. (2021). If I understand correctly, the authors refer to this one: _if zero approximation error holds, does softmax PG achieve global convergence ?_ However, I couldn't find this claim in Agarwal et al. (2021). Instead, I found two open problems left by Agarwal et al. (2021). \n\n- __(1)__ In their Remark 11 (journal version) / Remark 5.1 (arxiv version), the first open problem is that, whether or not softmax PG will converge globally if the initial state distribution is not state-wise strictly positive. Since this paper only considers bandit problems with one single state, the initial state distribution is constant 1 with that state. The paper does not resolve this open problem. \n- __(2)__ In their Remark 14 (journal version / Remark 5.2 (arxiv version), the second open problem is whether a polynomial global convergence rate is achievable for softmax PG with the entropy regularizer. This problem envolves entropy regularization, which is outside the scope of the paper. Thus, the paper dose not resolve this problem neither.\n\nCan the authors point me specifically to where Agarwal et al. (2021) claim  the open problem mentioned right after Corollary 1 in this paper ?\n\nNext, I have some more open questions that the authors can decide to include them in the paper or not.\n\n- Do the results of softmax PG and NPG in this paper still hold if the optimal action is not unique ?\n- Same question for entropy regularized bandit case ?\n- Do the results for NPG with non-adaptive geometrically increasing step size still hold ? Note that NPG and variants with non-adaptive geometrically increasing step size have been studied extensively recently (Lan, 2022; Xiao, 2022; Li et al., 2022; Yuan et al., 2023; Alfano et al., 2023). Can we obtain superlinear convergence as discussed in Xiao (Section 4.3, 2022) and Li et al. (2022) ?\n- As for the general MDP, one can think about the compatible function approximation framework of Agarwal et al. (2021). By similarity, the ranking condition of the reward vector for the softmax PG becomes the ranking condition of the advantage function / Q-function. And the projection of the reward vector onto the image of the feature map for NPG becomes the projection of the advantage function / Q-function onto the image of the matrix $[\\nabla_\\theta \\log \\pi_{\\theta}(a \\mid s)]_{s, a}$. What do you think about this idea ? Can this idea and the techniques used in this paper be enough to be extended to general MDP ? If not, what is the missing factor here and what is the challenging obstacle ? For simplicity, one can consider the exact NPG instead of stochastic NPG.\n\nXiao, Lin (2022). On the Convergence Rates of Policy Gradient Methods. Journal of Machine Learning Research 23.282, pp. 1–36.\n\nLi, Yan, Tuo Zhao, and Guanghui Lan (2022). Homotopic Policy Mirror Descent: Policy Convergence, Implicit Regularization, and Improved Sample Complexity.\n\nLan, Guanghui (Apr. 2022). Policy mirror descent for reinforcement learning: linear convergence, new sampling complexity, and generalized problem classes. Mathematical Programming.\n\nYuan, Rui, Simon Shaolei Du, Robert M. Gower, Alessandro Lazaric, and Lin Xiao (2023). Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies. In International Conference on Learning Representations.\n\nAlfano, Carlo, Rui Yuan, and Patrick Rebeschini (2023). A Novel Framework for Policy Mirror Descent with General Parametrization and Linear Convergence.", "limitations": "The authors have adequately addressed the limitations.", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is revolutionary and the results are surprising. This paper may have the same impact on the theoretical RL community as that of Agarwal et al. (2021). The strengths of the paper can be summarized as follows.\n\n- First, the research question itself on the approximation error assumption is important and revolutionary. Challenging the previous pioneering work is always not easy.\n- However, the argumentation of the paper is impeccable. Readers will probably be surprised at first, but will quickly be convinced by several simple but sophisticated numerical simulations.\n- Not only the authors are able to find negative answers to questions about the role of approximation error for the global convergence of PG methods, they also establish new results characterizing the conditions for the global convergence of PG methods and draw the connection between the new conditions and the approximation error assumption. The novelty of the paper is significant.\n- In addition, the paper is very well written. The research question is well formulated. The new conditions are well presented. And the reasoning is detailed with intuitive explanations, figures, many examples and the proof sketch.\n\nI agree with the authors that this work will open many new directions for understanding PG-based methods in the function approximation regime, especially considering the general Markov decision processes (MDPs).", "weaknesses": "Although the paper is well written, I still find some minor points for improvement.\n\n- In the figures, the authors can specify that y-axis is the reward / value function.\n- Line 52-53: \"... approximation error ..., diverting attention from feature designs that achieve useful properties beyond small approximation error.\" Although one goal of the paper is to claim that approximation error is not necessary, I find this sentence to be a little too dismissive of approximation error. It may leave the reader with the impression that approximation error is rarely useful outside of the tabular case where the approximation error is zero. It is true that, zero approximation error does not fit well with linear function approximation in general, which is the original motivation for the paper. However, when the approximation error is zero, the conventional approximation error based analysis becomes useful. For instance, another interesting case of zero approximation error is the use of neural networks, recently studied by Alfano et al. (2023) in Section 4.2. That is, a sufficiently wide and shallow ReLU network can infinitely approximate the Q-function such that the approximation error is zero. Consequently, their approximation error based analysis leads to a new SOTA sample complexity of PG method under neural network parameterization.\n- Line 361-362: \"Extending the results and techniques to general Markov decision processes (MDPs) is another important and challenging next step.\" The authors can use an extra page in the revised version to discuss the intuition of possible obstacles to such an extension. See also my question below.\n\nAlfano, Carlo, Rui Yuan, and Patrick Rebeschini (2023). A Novel Framework for Policy Mirror Descent with General Parametrization and Linear Convergence.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate that the reviewer understood and recognized the contribution of the work. We answer the questions as follows.\n\n>**figures ... y-axis**\n\nWe mentioned that $\\pi_{\\theta}^\\top r$ is used as the vertical axis value in Line 148, and will add this to the figure.\n\n>**Line 52-53 ... approximation error ... Alfano et al. (2023)**\n\nThank you for pointing out the work on PG using overparameterized NNs. We will cite it and mention that zero function approximation error results are useful in this setting, as suggested.\n\n>**Line 361-362**\n\nThank you for the suggestions. We present our current understanding and evidences. Also, please check the common feedback for details.\n\n>**Clarification question ... open problem**\n\nThank you for checking Agarwal et al. (2021) very carefully. It is not explicitly mentioned in that paper **if Softmax PG achieves global convergence with zero approximation error** is an open problem. However, to the best of our knowledge and after extensive communication with the authors of Agarwal et al. (2021), the common understanding is that this problem has remained open in the sense that it has not been solved before. We will clarify in revised versions.\n\n>**optimal action is not unique** \n\nYes, $\\pi_{\\theta_t}^\\top r \\to r(a^*)$ will hold. Consider if there are two optimal actions $a_1^*$ and $a_2^*$ with $r(a_1^*) = r(a_2^*)$. If the plateaus for those two actions are separated on the landscape in Figure 1 (this is an intuitive statement), it will follow that either $\\pi_{\\theta_t}(a_1^*) \\to 1$ or $\\pi_{\\theta_t}(a_2^*) \\to 1$ depending on where $\\theta_1$ is initialized (the arguments are almost identical as the unique optimal action case). Otherwise,  if the plateaus for those two actions are connected on the landscape (neighborhoods of one another), then we will have $\\pi_{\\theta_t}(a_1^*) + \\pi_{\\theta_t}(a_2^*) \\to 1$, since the current analysis only asserts that $\\theta_t$ approaches the ``joint'' optimal plateau formed by $a_1^*$ and $a_2^*$.\n\n>**entropy regularized bandit case**\n\nThank you for asking this question. Our speculation is that the answer is yes. In particular, we believe that when the temperature is small enough (entropy does not have much weight comparing to reward), the landscape is modified so that the stationary point is \"moved\" from a one-hot policy to a finite stationary point, hence the nice \"ordered\" landscape is still preserved by adding entropy. Further study is required to rigorously show or disprove this speculation.\n\n>**NPG with non-adaptive geometrically increasing step size still hold**\n\nThank you for pointing this out. We have checked and do not see any difficulty that prevents this generalization.\n\n>**As for the general MDP ... advantage function / Q-function ... challenging obstacle**\n\nThank you for bringing up this idea, which seems to be very reasonable. As mentioned in the common feedback, considering the advantage function / Q-function is also the idea we were looking at. Difficulties are also explained in the common feedback.  We believe additional efforts are needed to make this idea work in MDPs."}, {"review_id": "J3Wnu93GXI", "reviewer": "Reviewer_WYfH", "summary": "This work studies the global convergence of standard softmax policy gradient and natural policy gradient for finite-arm bandits with linear function approximation (i.e., considering a log-linear policy). It is shown that the approximation error is not crucial for characterizing global convergence since the latter can be achieved even with non-zero approximation error. Ordering-based conditions are provided instead to guarantee the global convergence of softmax PG and natural PG while the approximation error is non-zero. More precisely, this paper establishes that both NPG and softmax PG converge globally when (a)  for NPG, the optimal action’s rank is preserved by the projection of the true reward onto the space of representable rewards and (b) for softmax PG, there exists a linear function preserving the ranking of actions provided by the true reward function. The case of a linearly realizable reward function is a particular case of the aforementioned reward rank preservation condition. Numerical examples illustrate all these results throughout the paper.  \n", "questions": "About the proof of Theorem 1, I have the following technical questions (1. (a)-(b)) which constitute my main concerns and that I would like to be addressed for clarification before updating my evaluation:  \n\n**1. (a)** Second part/Lemma 1 (l. 455): Why does the fact $\\|\\| \\frac{d \\pi_{\\theta_t}^T r}{d \\theta_t}\\| \\|_2 \\to 0$ imply that $\\|\\|\\theta_t\\|\\| \\to \\infty$? I understand that there is no stationary point for any $\\theta \\in \\mathbb{R}^d$ following the proof but how do you conclude properly that then $\\|\\|\\theta_t\\|\\| \\to \\infty$? In particular in the proof, l. 446: what does the assumption \nsuppose there exists $\\theta' \\in \\mathbb{R}^K$ with $\\|\\|\\theta’\\|\\|_2 < \\infty$ mean? \n\nIt is proven (by contradiction) that for every $\\theta’ \\in \\mathbb{R}^d$, we have $\\frac{d \\pi_{\\theta’}^T r}{d \\theta’} \\neq 0$. \nTo conclude that $\\|\\|\\theta_t\\|\\| \\to \\infty$, I would expect that the proof assumes that the sequence $(\\theta_t)$ is bounded and then finds a contradiction. Could you please clarify the reasoning here? \n\n**1. (b)** Third part: the general reasoning and the conclusion l. 498 to 501 are not very clear to me.\n\n   (i) It is proven by contradiction that every suboptimal action $i$ s.t. (47) is satisfied, $\\pi_{\\theta_t}(i)$ does not converge to 1. How does this help concluding that for the optimal action $a$ (or any optimal action if non unique) we have $\\pi_{\\theta_t}(a)$ converges to 1? Could you clarify the reasoning and the guiding intuition? \n\n (ii) Could you also elaborate more on how (60), (69), (71) and (72) are used to conclude? \n\n(iii) Is the third case $j \\in \\mathcal{A}(i)$ (i.e., $i,j$ are mapped to the same reward value) handled in the proof? If trivial, maybe a word about it can be added. \n\n (iv) Minor: what do you mean by $X$ and $u$ are bounded in l. 492? $X$ is the feature matrix and $u$ is a fixed vector in $\\mathbb{R}^d$. \n\n**2.** Could you clarify why the possibility of having exponentially many suboptimal local maxima renders global convergence (to the optimal reward) impossible without further structure on function approximation as stated in l. 123-124? Is it because there is more chance to be stuck at a local suboptimal local maxima? How does the ordering-based condition preclude such a case in Theorem 1? \n\n**3.** Do the examples of section 3 allude to the fact that the ordering of the features matters since the examples only differ between them by column permutations? \n\n**4.** In proposition 1 (and more generally in the paper), do you assume that there exists a unique optimal action? If there are many, I guess any optimal action would work. You may want to add a comment regarding this.  \n", "limitations": "Limitations and opportunities for future work are briefly discussed in the conclusion. \n", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "\nThe main results of this paper provide very interesting insights on the global convergence of some PG methods under the function approximation setting for finite-arm bandits. The paper provides strong and solid contributions.\n\n**(a) Originality**: the paper challenges common existing analysis featuring the approximation error as a natural limit when considering function approximation. Results are new to the best of my knowledge.\n\n**(b) Significance**: as also highlighted by the paper in the conclusion, the results are likely to inspire further important developments for function approximation in the more general setting of MDPs, nonlinear approximation and representation learning. \n\n**(c) Correctness**: To the best of my knowledge, except for the proof of Theorem 1 which is more involved and may deserve some clarifications in my opinion (see my comments below), the proofs in the appendix are correct, complete and relatively easy to follow. I checked the appendix in details. \n\n**(d) Clarity and writing**: This paper is very well-written, the structure is clear, the exposition is progressive, the story line is very nice and the illustrations are insightful. This is a solid body of work. \n", "weaknesses": "- While the proof of Theorem 2 is very clear to me, some parts of the proof of Theorem 1 (and its sketch l. 266 to 293) deserve some clarifications in my opinion. Please see my comments in the questions section. \n\n- Comment: The proof of Theorem 2 seems to follow similar lines to the proofs in Khodadadian et al. 2022 even if the latter work does not consider linear function approximation nor does it propose ordering-based conditions (while it applies however to MDPs).  The main difference seems in replacing the  true gap $\\Delta$ by the gap induced by the linear approximation $\\hat{\\Delta}$. For similarities, see for e.g., Appendix C in Khodadadian et al. 2022 for the bandits case or the main part of the paper (Theorem 1, Lemma 1, Proposition 1 p. 3-4 and their proofs). \n\nKhodadadian, S., Jhunjhunwala, P. R., Varma, S. M., & Maguluri, S. T. (2022). On linear and super-linear convergence of Natural Policy Gradient algorithm. Systems & Control Letters, 164, 105214.\n\n**Minor:**\n\n-  It is not very clear what is $v_2$ in l. 278-279 (especially that there is also $v$ in l. 278) and what is $v_1$ in l. 283 and how do they relate to $v$ in l. 268, I find the notations and the formulation a bit confusing in l. 266-293. \n\n- Please give the precise reference to Theorem 1 when you reference [8] in lines 116 and 123. \n\n- $r(a^*)$ introduced in l. 110 does not seem to be defined before (definition of $a^*$ comes later in l. 140).  \n\n- Numerical legends in all the figures are almost invisible in a printed format (although visible when zooming on a computer), it would be nice to increase the size of the numerical characters (and save the figure in pdf format if not already done) to ease the reading. \n\n- Eq. (27): Why is the inequality strict? This (strict) positivity does not seem to be used anyway. \n\n- Suggestion: Eq. (102) maybe add $>0$ for clarification. \n\n- Suggestion: Eq. (149) to Eq. (150) maybe add the splitting sum steps with the order summing exchange to detail a bit more for the convenience of the reader. \n\n**Typos:** \n- l. 446: $\\theta’ \\in \\mathbb{R}^d$ instead of $\\mathbb{R}^K$?\n\n- l. 474: $a \\in [K]$ instead of $i \\in [a]$. \n\n- l. 481: Eq. (58) instead of (54).  \n\n- l. 493: Eq. (68) instead of (65). \n\n- Eq. (97): Eq. (94) instead of (91). \n\n- Eq. (101): Eq. (97) instead of (95). \n\n- Eqs. (138) and (139): $\\max_a$ instead of $\\max_i$. \n\n- l. 539, Eq. (144): say there exists $\\theta_{\\zeta} \\in [\\theta, \\theta']$ such that ...\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for carefully reading and checking the results. The main concerns are addressed as follows.\n\n>**Comment on Khodadadian et al. 2022**\n\nThank you for pointing this out. We will add a remark to mention the similarities and differences between Theorem 2 and Khodadadian et al. 2022.\n\n>**1. (a)**\n\nSuppose there exists $C < \\infty$, s.t. for all $t \\ge 1$, $\\theta_t \\in S_C := \\\\{ \\theta \\in \\mathbb{R}^d: \\\\| \\theta \\\\|_2 \\le C \\\\}$.\n\nFor all $\\theta \\in S_C$, $\\Big\\\\| \\frac{d \\pi\\_{\\theta}^\\top r}{d \\theta} \\Big\\\\|_2 > 0$ (no finite stationary points). Since $S_C$ is compact, we have, $\\inf\\_{\\theta \\in S_C}{ \\Big\\\\| \\frac{d \\pi\\_{\\theta}^\\top r}{d \\theta} \\Big\\\\|_2 } \\ge \\epsilon$ for some $\\epsilon > 0$.\n\nTherefore, for all $t \\ge 1$, $\\Big\\\\| \\frac{d \\pi\\_{\\theta_t}^\\top r}{d \\theta_t} \\Big\\\\|_2 \\ge \\epsilon > 0$, contradicting Eq. (28).\n\n>**1. (b)**\n\n(i) The whole $\\theta_t \\in \\mathbb{R}^d$ space is partitioned into at most $K$ sub-regions (Figure 2). Since the existence of $w \\in \\mathbb{R}^d$, $a^*$ has one sub-region (yellow in Figure 2) which satisfies (by order-preservation),\n\\begin{equation*}\n    \\[ X \\theta_t \\](a^*) = \\max\\_{a \\in [K]} \\[ X \\theta_t \\](a)\n\\end{equation*}\n\nSince $\\\\| \\theta_t \\\\|_2 \\to \\infty$, if **$\\theta_t$ always stays in the above region as $t \\to \\infty$**, then softmax transform gives $\\pi\\_{\\theta_t}(a^*) \\to 1$. We proved that for all $i \\in [K]$ with $r(i) < r(a^*)$, $\\theta_t$ cannot stay in sub-optimal regions forever.\n\nIn addition, $\\theta_t$ cannot switch between different regions. As $\\\\| \\theta \\\\|_2 \\to \\infty$, $\\pi\\_{\\theta}^\\top r \\approx r(i)$ in a region, and switching regions contradicts $\\pi\\_{\\theta\\_{t+1}}^\\top r \\ge \\pi\\_{\\theta_t}^\\top r $ in Eq. (10). Moreover, $\\theta_t$ cannot approach region boundaries, since it makes $\\pi\\_{\\theta_t}$ approach non one-hot policies, such as $(0, 0.5, 0.5, 0)$ in Figure 2, which gives non-zero inner product in Eq. (33), contradicting Eq. (28).\n\n**In summary**, $\\\\| \\theta \\\\|_2 \\to \\infty$ and $\\theta_t$ can only stay in one region, and we proved that $\\theta_t$ cannot stay in any sub-optimal regions, which implies that $\\theta_t$ eventually stays in the optimal region, indicating that $\\pi\\_{\\theta_t}(a^*) \\to 1$.\n\n(ii) Eqs. (69) and (71) give $w^\\top \\theta_t  \\gg 0 \\ge u^\\top \\theta_t$ (the former is unbounded and the later is decreasing), which holds if scaling $w$ and $u$ by constants to get $w'$ and $u'$. For a large enough $t \\ge 1$, there exists $w'$ such that $x_{a^*}^\\top \\theta_t \\ge {w'}^\\top \\theta_t > {u'}^\\top \\theta_t \\ge x_{a^-}^\\top \\theta_t$ (geometry argument, $u$ can be arbitrarily close to region boundaries). The direction of $\\theta_t$ approaches $v$ implies $x_{a^*}^\\top v > x_{a^-}^\\top v$, meaning that $\\theta_t$ enters the region in Case 1, contradicting the assumption of Case 2.\n\nFor example, take $u \\propto (-0.9, 1)^\\top$ and $w \\propto (-0.9, -1)^\\top$ in Example 1 (Figure 2), $w^\\top \\theta_t > u^\\top \\theta_t$ implies $\\theta_t(2) < 0$, entering the dark green region (reducing to Case 1). Another example is if $\\\\| x_a \\\\|_2 = 1$ for all $a$ (features are on unit ball), then $u' = x\\_{a^-}$ satisfies the inequalities.  \n\n(iii) If $j \\in \\mathcal{A}(i)$, then consider the third largest component and discuss the two cases again. If $j \\in \\mathcal{A}(i)$ for all components, then $\\pi_{\\theta_t}$ approaches uniform policy $\\text{softmax}(X v) = \\text{softmax}(\\mathbf{1})$, contradicting $\\theta = \\mathbf{1}$ cannot be a stationary point (unless $ r = \\mathbf{1}$ according to Eq. (33), which is trivial since every policy is optimal).\n\n(iv) This means there exists $C < \\infty$, such that $\\max_{i \\in [K], j \\in [d]} | X_{i,j} | \\le C$ and $\\max_{j \\in [d]} | u(j) | < C$. The result of this is for $y$ in Line 492, $\\max_{i \\in [K]} | y(i) | $ is also bounded since $y := X u$ in Line 489.\n\n>**2.**\n\nIn [1, Thm 1], if $\\theta_1$ is close enough (in a basin of attraction) to one bad local maximum, then gradient ascent will make $\\theta_t$ approach that bad local maximum.\n\nThe ordering-based condition preclude such a case since **first**, Lemma 1 shows that there is no stationary point in any finite region. **Second**, the landscape is \"ordered\" such that any sub-optimal one-hot policy is not a bad local maximum (rigorously speaking they are not even stationary points by being infinitely far). They are \"saddle-point-like\", in the sense of being surrounded by a higher and a lower plateau. This creates a situation that any sub-optimal one-hot is not attracting gradient trajectories, and the optimal plateau is the only \"local-maximum-like stationary point\" in Figure 1(a).\n\n>**3.**\n\nThis is partially correct. If we change the numbers in Example 1 and use the same Examples 2 and 3, the same conclusion still holds, e.g., use $r = (9.2, 7.8, 7.1, 6.3)^\\top$ and $X^\\top = \\[ -0.2, -1.1, 0.1, 2.1 ; -1.9, 0.2, 0.8, 0.1 \\]$ as Example 1.\n\n>**4.**\n\nHaving multiple optimal actions does not change the conclusion of $\\pi_{\\theta_t}^\\top r \\to r(a^*)$. The difference is that the behaviour of optimal actions' probabilities needs to be discussed in a case by case manner, depending on whether different optimal actions' plateaus are connected or separated on landscape.\n\nConsider if $a_1^*$ and $a_2^*$ with $r(a_1^*) = r(a_2^*)$. If the plateaus for those two actions are separated on the landscape in Figure 1 (this is an intuitive statement), then we will have either $\\pi_{\\theta_t}(a_1^*) \\to 1$ or $\\pi_{\\theta_t}(a_2^*) \\to 1$ depending on where the initialization $\\theta_1$. Otherwise,  If the plateaus for those two actions are connected on the landscape (neighborhoods of one another), then we will have $\\pi_{\\theta_t}(a_1^*) + \\pi_{\\theta_t}(a_2^*) \\to 1$, since the current analysis only gives $\\theta_t$ approach the \"joint\" optimal plateau formed by $a_1^*$ and $a_2^*$.\n\n>**Typos and Minor comments**\n\nThank you for catching typos and minor issues.  We will ensure these are fixed."}, {"review_id": "3GoBvAZahU", "reviewer": "Reviewer_BpdK", "summary": "The paper theoretically proves that, for finite-arm bandits with linear function approximation, the global convergence of policy gradient (PG) methods is not dependent on approximation error, but rather, on the ordering properties of the reward representation. The global convergence is achievable for both standard Softmax PG and natural policy gradient (NPG) under linear function approximation. This result is also verified using simple examples and empirical experiments.", "questions": "The single-state MDP is a very special MDP; the proposed idea may or may not work for a more general senario. How this work will be generalized to a multi-state MDP? Is there any simulation results on that? ", "limitations": "This is a theoretical work so there is no negative societal impact.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "This paper provides a completely new understanding on the convergence of policy gradient method, that is, the global convergence only depends on the specific ordering-based condtions instead of some classical approximation requirements. To my own knowledge, I have not seen such result before. \n\nThis novel insight is also significant. There are many situations where the approximation error could never be sufficiently small. This work provides a key to understand the covnergence of PG-based algorithms. And as the author claims, I agree with that this paper will open a new directions for PG-based methods under function approximation. \n\nThis work is well-written. I can clearly understand which problem this paper is solving; especially, examples given in Section 3 are very helpful to understand the motivation of proposing the ordering-based conditions. This paper also has rigorously defined two new preservation condtions on the ordering, and proved the necessarity or sufficiency for those proposed conditions. ", "weaknesses": "The studied case only contains one state, so it is a simple bandit optimization problem. Though the main result of this paper is inspiring and interesting, this paper lacks of (1) persuading evidence showing that these understandings will also be valid for more general cases, and (2) sufficient discussions on how to generalize this result in a more general Markov decision process. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate that the reviewer recognized the contribution of the work. We answer the questions as follows.\n\n>**discussion of how to generalize the results to MDPs**\n\nGeneralizing the results to MDPs is an important and challenging next step, as we mentioned in the conclusions. Since other reviewers (P4aQ, m2vF) also asked this question, we present the discussions for MDPs in the common feedback, and please check that for details. Thank you."}]

Author rebuttal:
We thank the reviewers for their careful reading, valuable comments, and recognition of the contributions. This first, common feedback answers a question raised by multiple reviewers.

>**Generalization to MDPs (Reviewers m2vF, P4aQ, BpdK)**

Extending the results of this work to MDPs is an important and challenging next step as mentioned in the conclusion, and our work provides a new direction as the first step. Here we discuss some research plans, considering Softmax PG for illustration. The discussion provides some new ideas, but resolving this problem is highly non-trivial and requires further investigation.

According to the policy gradient theorem [21, Theorem 1], we have, for all $\theta_t \in \mathbb{R}^d$,
\begin{equation*}
    \theta_{t+1} = \theta_t + \eta \cdot \sum_{s \in \mathcal{S}} d^{\pi_{\theta_t}}(s) \sum_{a \in \mathcal{A}} \frac{\partial \pi_{\theta_t}(s, a)}{\partial \theta_t} Q^{\pi_{\theta_t}}(s, a)
\end{equation*}
\begin{equation*}
    = \theta_t + \eta \cdot \sum_{s \in \mathcal{S}} d^{\pi_{\theta_t}}(s) \cdot X_s^\top ( \text{diag}{(\pi_{\theta_t}(\cdot | s))} - \pi_{\theta_t}(\cdot | s)\pi_{\theta_t}(\cdot | s)^\top ) \ Q^{\pi_{\theta_t}}(s, \cdot),
\end{equation*}
where $X_s \in \mathbb{R}^{|\mathcal{A}| \times d}$ is the feature matrix under state $s \in \mathcal{S}$ and can be shared across multiple states. Comparing with Eq. (4), for all $s \in \mathcal{S}$, the reward vector $r \in \mathbb{R}^K$ is replaced by $Q^{\pi_{\theta_t}}(s, \cdot) \in \mathbb{R}^{|\mathcal{A}|}$, as mentioned also by Reviewer P4aQ. This fact provides some new ideas as well as difficulties. 

**First**, if for all state $s \in \mathcal{S}$, the feature matrix can preserve the order of $Q^{\pi_{\theta_t}}(s, \cdot)$ for **all policies**, i.e., for all $t \ge 1$, there exists $w_t \in \mathbb{R}^d$, such that for all $s \in \mathcal{S}$, $X_s w_t \in \mathbb{R}^{|\mathcal{A}|}$ preserves the order of $Q^{\pi_{\theta_t}}(s, \cdot)$, then we have,
\begin{equation*}
    \theta_{t+1}^\top w_t = \theta_t^\top w_t + \eta \cdot \sum_{s \in \mathcal{S}} d^{\pi_{\theta_t}}(s) \cdot w_t^\top X_s^\top ( \text{diag}{(\pi_{\theta_t}(\cdot | s))} - \pi_{\theta_t}(\cdot | s)\pi_{\theta_t}(\cdot | s)^\top ) \ Q^{\pi_{\theta_t}}(s, \cdot)
\end{equation*}
\begin{equation*}
    \ge \theta_t^\top w_t,
\end{equation*}
generalizing Eq. (12), a key argument in the one-state setting. However, $w_t$ is  changing over time, since in the update $r \in \mathbb{R}^K$ is replaced by $Q^{\pi_{\theta_t}}(s, \cdot)$, which is changing over $\theta_t$. Comparing with fixed $r$ and $w$ in Eq. (12), using the above inequality with $\theta_t$ and $w_t$ both changing over time is more challenging and manifests the major technical difficulty.

**Second**, another speculation is that preserving the order of $Q^*(s, \cdot)$ (value of the optimal policy $\pi^*$) might be enough to achieve global convergence (if true, there would be no need to preserve the values of all policies). Here we show a local convergence when $\text{softmax}(X_s \theta_t)$ is close enough to $\pi^*( \cdot | s)$. Suppose that there exists $w^* \in \mathbb{R}^d$, such that for all $s \in \mathcal{S}$, $X_s w^* \in \mathbb{R}^{|\mathcal{A}|}$ preserves the order of $Q^*(s, \cdot)$. Then for any $\theta_t$ such that $Q^{\pi_{\theta_t}}(s, \cdot)$ preserves the order of $Q^*(s, \cdot)$, we have,
\begin{equation*}
    \theta_{t+1}^\top w^* = \theta_t^\top w^* + \eta \cdot \sum_{s \in \mathcal{S}} d^{\pi_{\theta_t}}(s) \cdot {w^*}^\top X_s^\top ( \text{diag}{(\pi_{\theta_t}(\cdot | s))} - \pi_{\theta_t}(\cdot | s)\pi_{\theta_t}(\cdot | s)^\top ) \ Q^{\pi_{\theta_t}}(s, \cdot)
\end{equation*}
\begin{equation*}
    \ge \theta_t^\top w^*,
\end{equation*}
based on which we can show that $\theta_t$ eventually approaches the direction of $w^*$, implying that $\pi_{\theta_t}(a^* | s) = \text{softmax}(X_s \theta_t)(a^*) \to \pi^*(a^* | s) = 1$ (in combination with Lemma 1). This means that preserving the order of $Q^*(s, \cdot)$ is enough for $\pi^*$ to be a local attractor of gradient updates within its neighbourhood. One challenge here is to generalize the arguments for arbitrary initialization $\theta_1 \in \mathbb{R}^d$ rather than $\theta_t$ close enough to optimal solution, and the difficulty is that $Q^{\pi_{\theta_t}}(s, \cdot)$ does not necessarily preserve the order of $Q^*(s, \cdot)$, and the last inequality above does not necessarily hold.

**In summary**, this discussion illustrates how the paper provides some new and useful insights for understanding more complex settings, but it requires further investigation to resolve this highly non-trivial problem for general MDPs. We will use an additional page in subsequent versions to present this discussion, as Reviewer P4aQ suggested.

Meta-review: In this paper, the authors identify a new set of conditions that guarantee global convergence of policy gradient methods in the presence of linear function approximation. The results and the analysis strategy developed in this paper make solid contributions to this topic, which could help advance our understanding about the performance of this widely used policy optimization method. Note that the proof of the main results might require substantial writing in order to improve readability and clarity, which I hope the authors can do in the final version of this paper.
Decision: Accept (oral)