Ordering-based Conditions for Global Convergence of Policy Gradient Methods

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.

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. This 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. This 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.

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?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

4 excellent

Limitations

This is a theoretical work so there is no negative societal impact.

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.

Strengths

The 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. **(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. **(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. **(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. **(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.

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. - 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). Khodadadian, 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. **Minor:** - 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. - Please give the precise reference to Theorem 1 when you reference [8] in lines 116 and 123. - $r(a^*)$ introduced in l. 110 does not seem to be defined before (definition of $a^*$ comes later in l. 140). - 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. - Eq. (27): Why is the inequality strict? This (strict) positivity does not seem to be used anyway. - Suggestion: Eq. (102) maybe add $>0$ for clarification. - 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. **Typos:** - l. 446: $\theta’ \in \mathbb{R}^d$ instead of $\mathbb{R}^K$? - l. 474: $a \in [K]$ instead of $i \in [a]$. - l. 481: Eq. (58) instead of (54). - l. 493: Eq. (68) instead of (65). - Eq. (97): Eq. (94) instead of (91). - Eq. (101): Eq. (97) instead of (95). - Eqs. (138) and (139): $\max_a$ instead of $\max_i$. - l. 539, Eq. (144): say there exists $\theta_{\zeta} \in [\theta, \theta']$ such that ...

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: 
 **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 suppose there exists $\theta' \in \mathbb{R}^K$ with $\|\|\theta’\|\|_2 < \infty$ mean? It is proven (by contradiction) that for every $\theta’ \in \mathbb{R}^d$, we have $\frac{d \pi_{\theta’}^T r}{d \theta’} \neq 0$. To 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? **1. (b)** Third part: the general reasoning and the conclusion l. 498 to 501 are not very clear to me. 

(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? 
(ii) Could you also elaborate more on how (60), (69), (71) and (72) are used to conclude? (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. 
(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$. **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? **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? **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.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

4 excellent

Contribution

4 excellent

Limitations

Limitations and opportunities for future work are briefly discussed in the conclusion.

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). **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. **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. Agarwal, 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.

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. - First, the research question itself on the approximation error assumption is important and revolutionary. Challenging the previous pioneering work is always not easy. - 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. - 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. - 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. I 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. - In the figures, the authors can specify that y-axis is the reward / value function. - 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. - 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. Alfano, Carlo, Rui Yuan, and Patrick Rebeschini (2023). A Novel Framework for Policy Mirror Descent with General Parametrization and Linear Convergence.

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). - __(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. - __(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. Can the authors point me specifically to where Agarwal et al. (2021) claim the open problem mentioned right after Corollary 1 in this paper ? Next, I have some more open questions that the authors can decide to include them in the paper or not. - Do the results of softmax PG and NPG in this paper still hold if the optimal action is not unique ? - Same question for entropy regularized bandit case ? - 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) ? - 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. Xiao, Lin (2022). On the Convergence Rates of Policy Gradient Methods. Journal of Machine Learning Research 23.282, pp. 1–36. Li, Yan, Tuo Zhao, and Guanghui Lan (2022). Homotopic Policy Mirror Descent: Policy Convergence, Implicit Regularization, and Improved Sample Complexity. Lan, Guanghui (Apr. 2022). Policy mirror descent for reinforcement learning: linear convergence, new sampling complexity, and generalized problem classes. Mathematical Programming. Yuan, 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. Alfano, Carlo, Rui Yuan, and Patrick Rebeschini (2023). A Novel Framework for Policy Mirror Descent with General Parametrization and Linear Convergence.

Rating

9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

The authors have adequately addressed the limitations.

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.

Strengths

**orginality** - 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. - 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. **quality** - 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. - 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. - 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. **clarity** - The paper is structured well, but it lacks of technical comparisons with existing results. - The visualization is not clearly stated, e.g., axes, error bars, speed. **significance** - 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. - 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. - 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. - 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.

Questions

Please see questions in Strengths and Weaknesses. Here are some other questions. - 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. - 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? - 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? - 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?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

2 fair

Contribution

3 good

Limitations

Yes.

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.

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). 2. The proof strategies and algorithm analysis techniques are novel. 3. Motivating examples in this paper are insightful.

Weaknesses

1. The paper could benefit from constructing a bit more larger-scale experiments. 2. This paper could have some further discussions on the implications of the ordering-based conditions.

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.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

N/A

Response

Thank you for the detailed explanation regarding the generalization to MDPs. It further confirms my belief that this paper has made a significant contribution and could potentially lead the way for a new direction. I have read comments from other reviewers, and none raised any new concerns for me. So I will keep my current positive scores.

Post rebuttal

I thank the authors for their precise and satisfactory answers to my questions and concerns. I believe this is an interesting and solid paper which provides nice and novel insights about the convergence of PG methods in the linear function approximation setting and which has some potential to be extended to the more challenging MDP setting (despite important obstacles), the discussion provided by the authors as a general comment (in the rebuttal) regarding this last point is insightful. I raised my score to 8. Here are some minor additional follow-up comments below. - I read the other reviews and the authors’ responses and I think the discussion regarding the verification of ordering-based conditions following the other reviewers’ comments could be added to the paper. - 1.b I think the proof in the appendix can be revised to reflect the intuition provided in the rebuttal as a response to 1. b. (i) in particular. I find the overall writing of the third part of the proof rather confusing although the treatment of each of the subcases of the partition is rather clear. I refer in particular to the beginning: Why considering the case where the limit of normalized $\theta_t$ sequence converges to a constant vector in (47)? It is not very clearly discussed in the appendix what would happen if the normalized sequence does not converge to a fixed vector but rather rotates indefinitely (spiralling towards $+\infty$). This point was clearer to me after the rebuttal given the responses to 1. b (i) and (ii). - 3. A comment added to the paper regarding this would probably be useful, I guess ordering of the features should not be crucial in examples since feature matrices would induce the same linear space. I think it is relevant to show that examples are not only based on column permutations. - 4. Thank you for the clarification, please update the paper accordingly to clarify this case where there are multiple optimal actions since it is not commented on this.