$\phi$-Update: A Class of Policy Update Methods with Policy Convergence Guarantee

Thank you for pointing out the typo. We will fix it in the revision.

Response to W1 & Q1: The convergence rate $\rho(\varepsilon)$ is the maximum of two rates, $\rho_1$ and $\kappa(\varepsilon)$ from two phases of the iterations. The first rate $\rho_1(\eta, \Delta,\varepsilon)$ comes from the local convergence phase (Theorem 3.2), which can be explicitly expressed in terms of $\phi$, $\eta$, $\Delta$ and $\varepsilon$. For the second rate $\kappa(\varepsilon)$, it comes from the global dynamic convergence (Theorem 3.5) for the initial finite number of iterations and depends on $D_t$. As we have provided a bandit example in Appendix E.4 to show that the error bound in Theorem 3.5 is tight, the global convergence necessarily depends on the term $D_t$, which cannot be explicitly described by model parameters.
Consider again the bandit problem in Appendix E.4, where the value error of this problem is explicitly shown in Line 1334. If one set the initial policy $\pi^0_{a_1}$ to be very close to $0$, the convergence rate in the early iterations will be extremely small, so the global convergence rate $\rho(\varepsilon)$ will be close to $1$. Noting that the value error in Line 1334 is exact, it is impossible to improve $\rho(\varepsilon)$ for such policy initialization.
Despite that $\rho(\varepsilon)$ cannot be explicitly expressed in term of the model parameters, the global convergence result is still interesting in our opinion. In optimization, global linear convergence usually can only be established for strongly-convex (or strongly-concave) functions, with the convergence rate relying on the parameter controlling the strongly convex property. For problems without this property, it is typically difficult to establish the global linear convergence. However, we show that for the RL problem (even non-convex and non-concave), the establishment of linear convergence is possible by leveraging the particular MDP structure even though it is difficult to give a concise expression for the convergence rate due to the lack of certain uniform property. It is worth noting that most of the existing global linear convergence results are either based on entropy regularization or using exponentially increasing step sizes.

Response to W2 & W3: We agree that the analysis under stochastic setting is interesting which is left in the future work. In this paper, we focus on the theory for the exact gradient setting, especially having established the policy convergence (without regularization) and the exact asymptotic convergence rate which are totally new, to the best of our knowledge.
The $\phi$-update can be implemented with general parameterizations under the stochastic setting. We have tentatively conducted some preliminary numerical experiments under parameterizations with neural networks, and results are presented in the table in our general response to all reviewers above. The experiment results show that $\phi$-update indeed works with some specific $\phi$ under stochastic applications. Because there are still a lot work to do to comprehensively evaluate the empirical performance of $\phi$-update (e.g., how to choose $\phi$ for difference problems), we prefer to focus on the theory in this paper, and not to include related numerical results.

Response to Q2: Since the purpose of these experiments is to empirically verify the results in Theorem 3.3 and Theorem 3.4, the simulations in Figure 2 and 3 are conducted under the exact gradient setting, and we use the transition probabilities to calculate the exact advantage functions.

Thank you for addressing my concerns and for providing such a detailed response. I sincerely appreciate the effort you put into clarifying key aspects of the work.

I fully agree that advancing the theoretical understanding of the convergence properties of policy gradient methods is both important and valuable to the community. While I still support the novelty and contributions of your paper, I would like to explain why I maintain my original score rather than raising it.

• Numerical Examples: I appreciate the inclusion of numerical examples demonstrating the practical feasibility of your method. I strongly encourage you to include these examples in the appendix of the final version, along with an explanation (similar to what you provided in the response) that these examples are intended to illustrate implementation feasibility rather than serve as comprehensive performance benchmarks. Additionally, open-sourcing the code would further enhance the accessibility and utility of your work for the broader research community.
• Discussion of Imprecise Numerical Rates: While the numerical convergence rates presented are tight, they lack precision, and I believe it is essential to discuss the implications of this imprecision in the paper. For example, the impreciseness of the constant "c" derived by Mei et al. (2020) in vanilla policy gradient methods is not explicitly addressed, and I suspect this may lead to a lack of awareness in the community about potential issues arising from this (as noted in Li et al. (2023) in my review). Though such issues might be rare in practice, they are still meaningful and merit discussion. I also suggest referencing recent work, such as Klein et al. (2024), which proposes new algorithms to address similar challenges, to contextualize your contribution in light of ongoing developments.

In conclusion, I continue to value the originality of the $\phi$-update approach and its potential impact, and I support accepting the paper to ICLR. I would raise my score to 7, but since 7 is not an option and due to the constant issue, which is often swept under the rug and not precisely addressed, I cannot give it an 8.

S. Klein, X. Zhang, T.Başar, S. Weissmann, L. Döring, „Structure Matters: Dynamic Policy Gradient“, 2024.

Thank you for the detailed reading and pointing out the typos. We will fix them in the revision.

About the relation to the escort transform based work: When $p=2$, policy gradient under the escort parameterization is an instance of $\phi$-update, which is not true for $p\ne 2$. However, a class of $\phi$-update (namely polynomial update in Appendix F.2) can be implemented under the escort parameterization, which has been briefly discussed in Remark F.1.

About the parameterization and prove techniques: Thank you for suggesting the formulation of $\phi$-update under softmax parameterization, which does provide an interesting intuition for condition (III).
Even though $\phi$-update (with any $\phi$) can be implemented under the softmax parameterization, for the global convergence, we note that the proof carried out in the parameter space in [1] still cannot be applied to $\phi$-update with such softmax policy parameterizations. One of the key ingredients in establishing the global convergence of softmax PG in [1] is the property of $\sum_a\theta^k_{s,a}=\sum_{a}\theta^0_{s,a},\forall k$. It comes from the fact of $\sum_a\frac{\partial V^\pi(s)}{\partial\theta_{s,a}}=0$ and the parameter update form of $\theta^{k+1}_{s,a}=\theta^k\_{s,a}+\eta\frac{\partial V^k(s)}{\partial \theta^k\_{s,a}}$. In general, such property is not satisfied for $\phi$-update under the same softmax parameterization. Instead, our proof is completely conducted in the policy space. Thank you again for raising this helpful question, and we may add a remark after the global convergence result.
The other convergence results (such as policy convergence and exact asymptotic convergence rate) are new, to the best of our knowledge. Currently, we are now aware whether they can be proved in the parameter space or not.

About the global linear convergence: We agree that the global linear convergence result is not neat enough since the rate $\rho(\varepsilon)$ is the maximum of two rates from two phases of the iterations. That being said, we still think they are interesting to some extend. For instance, in optimization, global linear convergence usually can only be established for strongly-convex (or strongly-concave) functions, with the convergence rate relying on the parameter controlling the strongly convex property. For problems without this property, it is typically difficult to establish the global linear convergence. However, we show that for the RL problem (even non-convex and non-concave), the establishment of linear convergence is possible by leveraging the particular MDP structure even though it is difficult to give a concise expression for the convergence rate due to the lack of certain uniform property. It is worth noting that most of the existing global linear convergence results are either based on entropy regularization or using exponentially increasing step sizes.

About how to choose $\phi$ and the step-size: In Appendix F.1, we provide some variants of softmax NPG, which show $p<q$ is preferred since the ''stretch intensity'' around $t=0$ becomes stronger as $p/q$ is smaller. The experiment presented in Figure 4(a) verifies that such $\phi$-update enjoys a better tail convergence than softmax NPG. We also provide a family of polynomial updates in Appendix F.2, and larger $p$ gives a better convergence rate in this case as shown in Figure 4(b). For the step size, Theorem 3.4 implies that larger step size yields a better tail convergence in the exact gradient setting. We have also tentatively conducted some preliminary numerical experiments under neural network parameterization to test the softmax NPG variants, see our general response to all reviewers. Despite this, how to choose $\phi$ and the step size in the practical scenarios still remains a good direction to explore in the future.

About the exact convergence rate: The exact asymptotic rate only explicitly depends on $\Delta$, and it is true that $\Delta$ may rely on $\gamma$. For instance, it can be verified that the $\Delta$ of the Grid World in Figure 2 is $(1-\gamma)\cdot\gamma^{H+W-3}$, where $H$ and $W$ are the height and width of the Grid World. The fact that the exact asymptotic rate does not rely on $\gamma$ explicitly can be interpreted intuitively as follows. When the policy and value are close to optimal ones, we have $A^k\approx A^*$. In such case, the problem can be roughly viewed as a bandit problem. That is, on each state, we just need to find the actions with largest optimal advantage, i.e. $\arg\max_a\\,A^*(s,a)$. As the bandit problem can be viewed as a MDP with $\gamma=0$, it is natural that the local convergence rate does not (explicitly) depend on $\gamma$. We can give a short discussion after the exact asymptotic rate result.

References:

[1] Agarwal, Alekh, et al. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 2021.

About the proof novelty: Even though softmax NPG can be viewed as an instance of PMD with KL divergence, for a general $\phi$, it is difficult to find a corresponding Bregman divergence such that $\phi$-update can fit into the PMD framework, for example consider the sigmoid function. Therefore, the existing analysis for PMD does not apply for general $\phi$-update. Instead we carry out the proofs by computing the Bellman improvement and establishing the contraction of the probability of non-optimal actions, which are substantially different from the analysis based on smoothness and gradient domination (e.g. softmax PG in [1]) or three point lemma (e.g. PMD in [2]). Based on our analysis, we have established two totally new convergence results: policy convergence (without regularization) and exact asymptotic convergence rate.

About the general parameterization and its implementation: First it should be pointed out that $\phi$ is a scaling function on advantage functions. We didn't mean that $\phi$ is induced by a neural network in Section 4.2, but that the policy can be parameterized by a neural network. The assumptions on $\phi$ can be easily verified and there are a broad class of functions that satisfy these conditions.
It is worth pointing out that even focusing on the tabular and the exact gradient settings in this paper, there are still convergence results which have not appeared previously, i.e. the policy convergence and exact aysmptotic convergence. It is not clear how to extend the analysis to general policy parameterizations or neural networks, which is too general for us to answer currently. To study this question, we may start from for example log-linear policies or some non-degenerate policies in the future.
As demonstrated in Section 4.2, $\phi$-update can be implemented together with neural networks. We have tentatively conducted some preliminary numerical experiments, and results are presented in the table in our general response to all reviewers above. However, comprehensive evaluations of the empirical performance of $\phi$-update is beyond the scope of this paper. Thus we prefer to focus on the theory in this paper, and not to include related numerical results.

References:

[1] Mei, Jincheng, et al. On the global convergence rates of softmax policy gradient methods. International Conference on Machine Learning, 2020.

[2] Lan, Guanghui. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. Mathematical Programming, 2021.

Dear Reviewer 29J3:

Since the discussion period has been extended, we are wondering whether there are further issues you have for us to address.

Best regards,

Authors

About the exact gradient setting: Though the convergence of policy gradient methods with access to exact policy have been extensively studied in the last few years, there are still fundamental problems to be addressed. For instance, the convergence of policy still remains unclear for most of the policy gradient methods. To the best of our knowledge, the only policy convergence result was established in [1] for a homotopic PMD method based on entropy regularization. In contrast, we first show that the policy produced by $\phi$-update converges even without regularization (Theorem 3.3), which indeed implies the policy convergence of the classical softmax NPG method. Moreover, the exact asymptotic convergence rate (Theorem 3.4) has not appeared previously as far as we know. In order to establish these new results, new proof techniques have been developed. For instance, to establish the policy convergence result, we bound the policy ratio on optimal actions and utilize the local linear convergence result to show that $\\{ \log \pi^k(a^*|s) \\}, a^* \in \mathcal{A}^*_s$ is a Cauchy sequence.

About the motivation of using alternative $\phi$ transforms and the experimental results: In Appendix F.1, we have indeed provided some variants of softmax NPG, which show $p < q$ is preferred since the ''stretch intensity'' around $t=0$ becomes stronger as $p/q$ is smaller. The experiment presented in Figure 4(a) verifies that such $\phi$-update enjoys a better tail convergence than softmax NPG. We also provide a family of polynomial updates in Appendix F.2, and larger $p$ gives a better convergence rate in this case as shown in Figure 4(b).
We have tentatively conducted some preliminary numerical experiments under parameterizations with neural networks, and results are presented in the table in our general response to all reviewers above. Because there are still a lot work to do to comprehensively evaluate the empirical performance of $\phi$-update (e.g., how to choose $\phi$ for difference problems), we prefer to focus on the theory in this paper, and not to include related numerical results.

About the concern of the extension to neural networks: We don't quite understand why the scaling function $\phi$ should be related to the logits output of neural networks, especially how the property $\phi(a) \cdot \phi(b) = \phi(a+b)$ is obtained. For example, let the logits output by neural network at $(s,a)$ be $f_\theta(s,a)$, where $\theta$ is the parameter of the neural network. Then the neural network policy is $\pi_\theta(a|s) = \frac{\exp(f_\theta(s,a))}{\sum_{a^\prime\in\mathcal{A}}\exp(f_\theta(s,a^\prime))}.$ Given current parameter $\theta_k$, to implement $\phi$-update, one can seek a new parameter $\theta_{k+1}$ such that $\forall \\, s\in\mathcal{S}, \\, a\in\mathcal{A}: \quad f_{\theta_{k+1}}(s,a) = f_{\theta_k}(s,a) + \log(\phi(\eta_k A^{\pi_k}(s,a))).$ Since the above equality might not be achieved, we propose to consider the following update in Section 4.2: $\theta_{k+1} \in \underset{\theta}{\arg\min} \\; \Bbb{E} [\\,\mathrm{KL}(\pi_\theta(\cdot|s) \\, || \\, \pi^k_\phi(\cdot|s))\\,],$ where $\pi_\phi^k$ is policy obtained by applying one step of $\phi$-update on $\pi^k$.

References:

[1] Li, Yan, et al. Homotopic policy mirror descent: Policy convergence, algorithmic regularization, and improved sample complexity. Mathematical Programming, 2023.

Dear Reviewer rtXi:

Since the discussion period has been extended, we are wondering whether there are further issues you have for us to address.

Best regards,

Authors