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

Authors: Wenye Li, Jiacai Liu, Ke Wei
Primary area: reinforcement learning
Keywords: reinforcement learning, policy optimization, policy convergence, linear convergence

Abstract:
Inspired by the similar update pattern of softmax natural policy gradient and Hadamard policy gradient, we propose to study a general policy update rule called $\phi$-update, where $\phi$ refers to a scaling function on advantage functions. Under very mild conditions on $\phi$, the global asymptotic state value convergence of $\phi$-update is firstly established. Then we show that the policy produced by $\phi$-update indeed converges, even when there are multiple optimal policies.  This is in stark contrast to existing results where explicit   regularizations  are required to guarantee the convergence of the policy.  Since softmax natural policy gradient is an instance of $\phi$-update, it provides an affirmative answer to the question whether the policy produced by softmax natural policy gradient converges. The exact asymptotic convergence rate of state values is further established based on the policy convergence. Lastly, we establish the global linear convergence of $\phi$-update.

Decision: accept (poster)
Reviewer scores: 6, 6, 8, 6

Reviews and discussion:
<thread>
creation date:
1729580081632

thread_type:
official_review

<thread_object>
creator: reviewer_ngsf

<content>
summary:
This paper introduces a general policy update, called the $\phi$-update, inspired by softmax NPG and Hadamard PG. Under the assumption of exact gradients, convergence is analyzed in the tabular setting. First, global asymptotic convergence is shown for the value function, as well as for the policy itself. Then, a linear rate of convergence is established. The authors provide a tabular numerical toy example to verify the tight theoretical convergence rate under exact gradients and describe how to extend the theory of $\phi$-updates to general non-tabular parameterizations.

strengths:
**S1:**	Well-motivated new policy update.

**S2:**	Solid theoretical analysis in the exact gradient setting, both asymptotic and non-asymptotic, although I have a question regarding the linear convergence rate (see below).

**S3:**	The exact gradient rates are tight, which is verified in numerical examples.

weaknesses:
**W1:** The constant $\rho(\epsilon)$ is not exactly stated in terms of model parameters. How close is this constant to $1$?

**W2:** Analysis limited to exact gradient case, stochastic analysis would be interesting. 

**W3:** The authors present examples in the tabular case. It would be nice to also analyse the generalised variant presented in Sec. 4.2. It remains unclear if this version works in practical applications. 

Although I understand that this is a theoretical paper which leaves stochastic analysis and experiments to future work, it would be nice to have at least one (toy) stochastic application that verifies practical performance

**Minors:**

Typo in the definition of $\kappa(\epsilon)$? It should be $\max_{t\leq T(\epsilon)}$ as there is no $k$ apprearing within the max.

questions:
**Q1:** Can you give a more precise description of the constant $\rho(\epsilon)$, in terms of model parameters like $\gamma$, $|\mathcal S|$ or $|\mathcal A|$? You stated yourself that in (Mei et al., 2020b) a constant $c$ appears in the softmax convergence rate which can be extremely small. (Mei et al., 2020b) state a sublinear convergence rate which can have very poor performance with respect to the discount factor (see [1]) and it would be nice to know if such a counter example can also appear for your algorithm. The term in the definition of $D_t$ looks very similar to the "bad" constant $c$ in (Mei et al., 2020b).

**Q2:** The error curves in the simulations in Fig. 2 and 3. look very smooth. Did you use the transition probabilities to calculate the exact $\phi$-updates or did you use simulations? 



[1] *Li, Gen, Yuting Wei, Yuejie Chi, and Yuxin Chen. “Softmax Policy Gradient Methods Can Take Exponential Time to Converge.” Mathematical Programming 201, no. 1–2 (September 2023): 707–802. https://doi.org/10.1007/s10107-022-01920-6.*
</content>
</thread_object>

</thread>
<thread>
creation date:
1730699654490

thread_type:
official_review

<thread_object>
creator: reviewer_7x97

<content>
summary:
phi-update

Summary: The paper proposes a new "general" class of update rules for "policy optimization" to find optimal policies in Markov Decision Processes. The new update rules takes the form $\pi'(a|s) \propto \pi(a|s) \phi( \eta(s)A^\pi(s,a))$, where $\pi'$ is the new policy, $\pi$ is the previous policy and $A^\pi$ is the advantage function of $\pi$, while $\eta(s)$ is a step-size that may depend on the state (but not on the actions), and $\phi$ is a "transfer" function that maps reals to reals. By choosing $\phi(t)=\exp(t)$ we get back the update of the "natural policy gradient" method, while $\phi(t) = (1+2t)^2 we get back the update rule of what is known as "Hadamard PG" (which is related to the "escort transform" based updates of some other previous work). In a nutshell, the new update rule unifies some previous update rules. The main result in the paper is the convergence of policies to some optimal policy and the exact asymptotic rate of value subotimality, while the stepsizes are allowed to be very general (as long as they are bounded away from zero; including adaptive stepsizes). 

Significance: There is considerable interest in the community to gain a deeper understanding of how to design effective and efficient algorithms and one line of active research looks at variations of "policy gradient" methods, or, as done in this paper, at variations of policy update rules. The contribution of this paper should thus be interpreted in this context. I think the question asked is reasonable and it deepens our understanding of policy update rule design. The results go beyond previous results in the area in a number of ways: The authors manage to remove the (annoying and, as it turns out, unnecessary) condition that the optimal actions are unique at all states. The asymptotic convergence rate result is also a nice contribution.

Soundness: I looked at the proofs at various places and did not find any problems with them and the results do look reasonable to me. I believe the results are sound.

Related work: The authors do a good job at discussing related work, except for two things: (1) the relation to the escort transform based work remains a bit unclear. (2) I feel that maybe the novelty of the proof techniques is overclaimed on the basis that the update is not given in the parameter space. However, this was only because the authors chose not to consider the parameter space updates. With a softmax parameterization, an equivalent form for the update is $\theta'(s,a)=\theta(s,a) + \log \phi( \eta(s) A^\pi(s,a))$. This also shows that the function $\psi(t) = \log(\phi(t))$ is perhaps even more fundamental to these update rules (condition (III) in the paper is indeed a condition on the rate of growth of this function in the vicinity of zero, which I feel demistifies this condition quite a bit).

Presentation: There are quite a few typos, grammatical problems (I will add a list to the end of my review in the coming days to help the authors correct the ones I found). There are also symbols used in the main text (e.g., $A^k$, $\mathcal{A}_s^k$ used in line 322, ..) with no definitions given for them as far as I could see (line 133 was maybe an attempt to define all these quantities; but it did not..). Nevertheless, these problems are relatively minor  and can be fixed in a revision easily. Also, I found that some results added little if anything. E.g., Theorems 3.5, and 3.6 are full of algorithm dependent parameters and thus have no clear interpretation (other than they also state an asymptotic rate). Thus, should they be part of the main text?

strengths:
Interesting problem, interesting results, new insightful proofs (avoiding uniqueness of optimal action!, generalization of previous arguments, showing what was really important about the updates)

weaknesses:
Presentation.

questions:
So what $\phi$ should we choose and how to set the step-size? It is not very clear we gained too much by the end of the paper other than seeing that there is a whole set of new update rules one could study.

I was surprised that the exact asymptotic rate does not depend on $\gamma$. But I guess $\gamma$ creeps back in through $\Delta$? Perhaps this should be discussed?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730720254350

thread_type:
official_review

<thread_object>
creator: reviewer_29j3

<content>
summary:
This paper studies policy parameterization for tabular MDPs using a scaling function  $\phi$, which serves as a systematic generalization of the softmax NPG method. Convergence rate proofs are provided and numerical simulations are illustrated to validate the theoretical claims.

strengths:
The paper addresses a gap in the literature by extending policy parameterizations of tabular MDPs beyond traditional methods like softmax and escort transformations. By applying a general scaling function  $\phi $ in the policy update step, it potentially contributes to the broader understanding of policy gradient methods analyzed through the mirror descent framework given more discussion of distinction is provided.

weaknesses:
- While the paper claims to offer a novel analysis of general policy updates without relying on standard regularization methods such as softmax NPG, it does not clearly distinguish its approach from existing methods. Given that softmax NPG is equivalent to policy mirror descent with a Kullback-Leibler (KL) divergence regularizer (Shani et al., 2020), the paper needs to clearly explain how the proposed  $\phi $-update differs from or improves upon established mirror descent techniques. Without this distinction, the originality and necessity of the proposed analysis approach remain unclear if current theory literature can already encapsulate such approaches with a general regularize used in the mirror descent policy update step (Lan 2023).

- The paper briefly mentions the application of the proposed method in function approximation settings where  $\phi$  is induced by a neural network in Section 4.2. However, it lacks a concrete implementation example or discussion on how the necessary assumptions can be verified in practice. Including such an implementation would enhance the practical relevance and demonstrate the method’s applicability despite potentially unverifiable assumptions.

Shani, Lior, Yonathan Efroni, and Shie Mannor. “Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs.” Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, no. 04, 2020.

Lan, Guanghui. "Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes." Mathematical programming 198.1 (2023): 1059-1106.

questions:
In the context of implementing general policy parameterizations with neural networks (Section 4.2), how can the underlying assumptions of the proposed method be verified or satisfied? Specifically, is the approach compatible with input-convex neural networks (or other popular parametrization scheme for finite MDP with function approximation), and if so, how does it ensure the validity of the theoretical guarantees presented?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730729370938

thread_type:
official_review

<thread_object>
creator: reviewer_rtxi

<content>
summary:
This paper studies the convergence of $\phi$-Update, which modifies the exp in softmax of natural policy gradient method to another $\phi$ function, which is positive and monotonically increasing.

The authors studies several convergence results with exact gradient updates, including asymptotic convergence, rate of convergence, and policy convergence, and also verified the results using simulations.

strengths:
The proposed $\phi$-update is sort of different but connected with existing methods.

The analysis is comprehensive and theoretical results are fine.

The paper is well written and easy to follow.

weaknesses:
I am a bit concerned with the exact gradient setting. Although it is a slightly different update than softmax PG/NPG variants, it is also fair to say that the exact PG is a well understood and studied setting since Agarwal2019 and many papers after that as noted in the paper.

questions:
I understand that this is mainly theoretical work. However, one suggestion might be that some promising experimental results might show that there is a real motivation of using alternative $\phi$ transforms than standard softmax (also comparisons with existing alternatives should be included).

In terms of extending the work to neural networks, I am a bit concerned this $\phi$ transform is not easy to be extended. The proposed update is multiplicative in policy space (Line 100), and to make that compatible with NNs (say there are logits outputed for actions, and the some transforms of logits will give probabilities over actions), the $\phi$ transform needs to satisfy $\phi(a) \cdot \phi(b) = \phi(a+b)$, which  reduces back to the exp function (softmax transform). Given this, it is hard to see how the $\phi$ transform will be a very promising direction to study in function approximation settings.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731836253301

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response to All Reviewers

comment:
We want to thank all the reviewers for their time and helpful comments. In this paper, we have presented several new theoretical results for a general policy update rule called $\phi$-update, especially the policy convergence and the exact asymtotic convergence rate, which are also applicable  and new for the classical softmax NPG method.

In this general response, we would like to point out that $\phi$-update can be implemented with general parameterization including neural networks, as sketched in Section~4.2. We have tentatively conducted some preliminary numerical experiments (for the exponential family presented in Section F.1 combined with artificial neural networks) on several environments from MuJoCo, and results are presented in the following table. For each experiment, we compute the mean and the standard deviation of the final accumulative reward accross 10 different random seeds. The policy neural network is a two-layers MLP with 64 units per layer, and the timesteps are 5 millions for each experiment. 

Note that the numerical results here only serve as an illustration, are not used to claim the SOTA results of $\phi$-update. In fact, comprehensive empirical evaluations  of $\phi$-update is beyond the
scope of this paper, especially on how to choose $\phi$ for different problems. Thus we focus on the theory in this paper, and intend not to include these preliminary results. 


|    | HalfCheetah-v2 | $~~~$Hopper-v2 | Walker2d-v2 |
|:-----:|:-----:|:-----:|:-----:|
| PPO | $3184(\pm 65)$ | $3010(\pm1106)$ | $\mathbf{3041(\pm881)}$ |
| Exp($p=1, q=5, \delta=0.5$) | $\mathbf{3323(\pm484)}$ | $\mathbf{3607(\pm1217)}$ | $2598(\pm845)$ |
| Softmax NPG (i.e. Exp($p=1, q=1$)) | $2764\pm(129)$ | $3362(\pm1335)$ | $2047(\pm913)$ |
| Exp($p=5, q=3$) | $2262(\pm351)$ | $1888(\pm830)$ | $1246(\pm470)$ |
</content>
</thread_object>

</thread>
<thread>
creation date:
1732265668249

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
As suggested by reviewer NGsf, we have included the preliminary numerical results  (in terms of plots instead of table for more clarity)
on $\phi$-update under the neural network parameterization in Appendix G.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper considers a general policy update framework for discounted MDP, called $\phi$-update, which includes but not limited to several popular policy gradient updates such as softmax PG, softmax NPG and and Hardamard PG. In this framework, the new $\pi(a|s)$ takes a multiplicative form of the old $\pi(a|s)$ and a scaling factor of the advantage function. The authors proposed a set of conditions on the scaling function under which desirable convergence results can be obtained, which provides a common framework for the convergence analysis of a class of policy updating schemes. Moreover, as the update scheme goes beyond the policy gradient descent (or mirror descent) framework, it provides us a deeper understanding of how the current policy optimization method works. Based on the contribution of the paper, we decide to accept the paper.