$\phi$-Update: A Class of Policy Update Methods with Policy Convergence Guarantee
Authors: Wenye Li
Jiacai Liu
Ke Wei
Venue: ICLR 2025 Poster (2025)
Keywords: reinforcement learning
policy optimization
policy convergence
linear convergence
Primary area: reinforcement learning
TL;DR: We study a general policy update rule called $\phi$-update and establish the convergence results of it.

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.

Published as a conference paper ICLR 2025
Φ- UPDATE: A CLASS OF POLICY UPDATE METHODS WITH POLICY CONVERGENCE GUARANTEE
Wenye Li", Jiacai Liu', Ke Weit School of Data Science, Fudan University
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 ø-update, where é refers to scaling function advantage functions. Under very mild conditions ø, the global asymptotic state value convergence of é-update is firstly established. Then we show that the policy produced by o-update indeed converges, even when there are multiple optimal policies. This is in stark contrast to existing results where explicit regularizations are required guarantee the convergence of the policy. Since softmax natural policy gra- dient is an instance of é-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 ş-update.
1 INTRODUCTION
As basis model, Markov Decision Process (MDP) has been widely studied and applied in reinforcement learning (RL). More precisely, an MDP model can represented as a tuple M (S, A, P,r, where the state space, A is the action space, P is the state-transition model, r S A - R is the reward function, and y E [0, 1) is the discounted factor. With policy æ, after selecting an action a₂ ~ x x--(st) at a state st, the agent receives reward r; r(st, 4z) and then transfers to another state 81+11 based on the transition model P(-|9,, 4z). The state value function is defined as the expected discounted cumulative reward over random trajectories induced by n
VO (s) - Σ
80 s,
The target RL to find an optimal policy which maximizes the following objective function
max (T)
where (T()) == == (s)) for some initial state distribution μz.
Policy optimization refers to family of effective algorithms to solve []] Compared with the classic dy- namic programming approaches such value iteration (VI) and policy iteration (PI) (Puterman) 1994 Sut- ton & Barto 2018), policy optimization searches in the policy space based on policy parameterization. Policy gradient (PG (Sutton et al., 1999)) method is a basic policy optimization method which updates policy parameter by gradient ascent directly. Some other important variants of PG include natural policy
"Equal contribution.
'Corresponding author (Email: kewei @ fudan.edu.cn)

---

Published as a conference paper ICLR 2025
gradient (NPG (Kakade 2001) )) policy mirror descent (PMD Xiao 2022 ) trust region policy optimiza-
tion (TRPO (Shani et al. 2020)), proximal policy optimization (PPO (Schulman et al. 2017) ) and deep
deterministic policy gradient (DDPG (Lillicrap et al. (015)).
1.1 RELATED WORKS
Recently, the analysis of policy optimization methods has received intensive investigations, especially in the tabular setting. An exhaustive review towards this line of research is beyond the scope of this paper. Here we only summarize the results of the exact policy gradient methods that are mostly related to our work.
Softmax PG In Agarwal et al. (2021). the asymptotic global convergence of softmax PG with sufficiently small step-size is established, which is generalized to the case of any positive step-size in Liu et al. (2024b). For non-asymptotic error bounds, the O(1/k) sublinear upper and lower bounds under small constant step-
size are provided in Mei et al. 2020b) by leveraging the smoothness and the gradient domination property of
the value function. These results also extended to arbitrary step-size in Liu et al. (2024b). In addition, the linear convergence softmax PG under adaptive step-size is established in Mei et al. (2021) Liu et al.
(024b).
Escort PG and Hadamard PG Escort PG is proposed in Mei et al. (2020a) to overcome the limitation of softmax PG. It shown that with some adaptive step-size, escort PG converges at the rate of O(1/k) which enjoys better constant dependence of c² 2-2/pp than c² for softmax PG (Mei et al. 2020b). where
can be extremely small. As a specific instance of escort PG, Hadamard PG is studied in Liu et al. (023) and proved to have local linear convergence.
Softmax NPG and PMD As shown Agarwal et al. (2021), softmax NPG enjoys a dimension-free O(1kk) sublinear convergence rate. The local linear convergence rate of softmax NPG is established Khodadadian et al. (202T) by leveraging the contraction of non-optimal probability. The global linear convergence is established for geometrically increasing step-sizes in Xiao (2022) and for adaptive step-sizes in Khodadadian et al. (20TT); : Johnson et al. (2023). In [Lu et al. (024b). the global linear convergence of softmax NPG under any constant step-size is established.
PMD can be viewed as an extension of softmax NPG. The O(1/k) sublinear convergence rate of softmax NPG in AAgawal al. (202T) is generalized PMD in Xiao (2022), while the global linear convergence with geometrically increasing step-sizes is also provided therein. PMD with regularization has been studied in Lan [2021); ; Li al. (2023b); Zhan al. (2023), while PMD) with function approximations has been
provided in Tomar et al. 2020 Yuan et al. (2023) ; Alfano et al. (2023).
1.2 MOTIVATION AND CONTRIBUTION
As already mentioned, softmax PG admits strict O(1/k) sublinear convergence rate. In contrast, Hadamard PG and softmax NPG can break this limitation and achieve linear convergence. The policy update rules of these algorithms are listed below:
(Softmax PG)
n (als) x a(als) exp exp (M))))
(Softmax NPG)
x (als) i(als) exp (nA7 (s. a)).
न (als) & t(als) (1+
(Hadamard PG)
where + is the updated policy, 1) the step-size, the visitation measure di is defined
Vs S::::
(3))) = (1 - 7) Σ
> Pr (st = 0/30 ~ P),
t=
2

---

Published as a conference paper ICLR 2025
the advantage function A defined as
= ==(s.a)=(("ssd.)) Q"(
and Q" a) := r(s + +P,,,) [V*(s') the state-action value function. From the update rules above, can be observed that the policy update direction of softmax PG is influenced by the term (als), which slows down the convergence rate as shown in Li et al. (2023a). By contrast, the policy update direc- tions of both softmax NPG and Hadamard PG are aligned with A (s (s,a), which motivates us study a class of policy update methods called ø-update, taking the form of
(d-update) V E S, E A: T (als) x T(ass) @ (s,
Here ni is the step-size that can vary with the policy and state s, and Φ is some real-valued function.
The goal of this paper is conduct systematic convergence analysis of é-update given the access to exact policy gradients under the tabular setting. The main contributions of this paper are summarized as below:
Global convergence of é-update We first show that d-update converges globally the optimal value under very mild conditions on á (Theorem 3.1 It is noted that the existing global convergence analysis is not applicable for é-update. For instance, the global convergence analysis of sofmax PG in Agarwal al. (202T) and Hadamard PG in Liu et al. (2023) explicitly utilizes the policy parameterization which is not available for é-update. In addition, the global convergence analysis of NPG and PMD in Xiao (2022) relies on the three point descent lemma while ø-update does not enjoy such property in general. Therefore, new techniques have been developed.
Policy convergence and exact asymptotic convergence rate A key contribution of this paper is the estab- lishment of the policy convergence of @-update even when there are multiple optimal policies (Theorem As an instance of duuudate, this implies that softmax NPG (without any regularizations) converges in the policy domain, which is a new result for softmax NPG. To the best of our knowledge, this is the first policy convergence result for vanilla policy gradient methods without regularizations. Based on the convergence of the policy, the exact asymptotic convergence rate of state values is further established (Theorem 3.4). which is also applicable for softmax NPG.
Global linear convergence By combining the local linear convergence result (Theorem 3.2) and the dy- namic convergence result (Thcorem 3.5). the global linear convergence of d-update is also established (The- orem 3.6
2 NOTATIONS, SETTINGS AND ØUUPDATE
2.1 NOTATIONS AND SETTINGS
Recall that MDP represented as a tuple M(S,A,,,r In this paper, we focus on the finite MDPs, i.e., [S]. |A| < oc. Without loss of generality, we assume the reward function is bounded in [0, 1], i.e., r(s, a) E [0, 1] for all and a.
Let ((A) be the probabilistic simplex on A. Given policy : S - A(A), the value function (*(s), action value function Q" (s, a), and advantage function (s,s,a) a) are defined above. In this work, we consider the setting where the exact policy evaluation can be accessed. When policy sequence {Λ*} is given, we use V Q*, and A to represent y** Q=*, and A= respectively.
We let 1 {-) be the indicator function. For arbitrary vector V E R|S), the Bellman operator induced by is defined as
(*V(s)
(r( +s)(s)
3

---

Published as conference paper ICLR 2025
As common in the analysis of policy optimization methods, we assume the initial distribution p is bounded away from zero (i.e., ji == min,es (u()) > 0). It follows immediately that d (s) 0 for all E S.
It is well known that there exists an optimal policy which maximizes V* (s) (e.g. in Puterman 1994) denoted n² (may be non-unique). The corresponding optimal value function denoted as V The optimal action and advantage values Q" and A are similarly defined.
Define the o-optiaal action state 9,
A := arg max A (²(saa) a);
a
and let na (Ag) Exere Talss) Similarly, when policy sequence is given A represent A When nT, let A A be the optimal action set at state Let A be the optimal advantage function gap. That is,
A
min (s, aES,agA;
where S = 1s S: A₃ + A} is assumed to be non-emply.
2.2 Ø-UPDATE AND ASSUMPTIONS
this section, we give the formal definition of şi-update, as well as the assumptions required in the conver- gence analysis.
Definition 2.1 (d-update). Let do (-I, + R be continuous scaling function, where 0 < I. S +oo. In
the k-th iteration, given step-size Th > 0 such that |n A ( [s,a]] < L, the é-update takes the form of
(als) (als)
AkEN, RES,aEAA
z
where -a o (n (s, a)) is the normalization factor.
Without further specification, we assume x (a|s) > 0, Vs E S, throughout this paper. Then easy to verify that there holds Tー (als) > for any finite time k.
Assumptions. The following assumptions will be made on Φ
(I) ò is strictly monotonically increasing, i.., d(x) d(y) for all x y.
(II) δ is strictly positive, i.c., <(x) >> 0 for all x,
(III) ó differentiable around 0 and there exists some small and < c < +oo such that
d
Φ (1) ((t)
log ((t)
dt
holds when & E (-5, 6).
The first two assumptions are sufficient for us establish the global asymptotic convergence and global linear convergence of é-update, but we further need the third one to establish the policy convergence and the exact asymptotic convergence rate. These three assumptions are indeed very mild and can even be satisfied by non-convex functions such @(t) (1 exp(-t))- (sigmoid function) and (t)) tan(t) + satisfy all the three assumptions. In particular, softmax NPG is an instance of é-update with x(t) = exp(t) and
L +00, and Hadamard PG is is an instance of é-update with ((t) (1 26) L 1/2.
4

---

Proposition 3.1. Suppose the assumptions ( hold. For any positive step-size nj > O, é-update has (als) (s, 2 ffr any and k. Furthermore, we Published as a conference paper ICLR 2025
3 CONVERGENCE ANALYSIS OF 6-UPDATE
this section we give a detailed analysis of d-update. The main results and their relations are summarized Figure We would like emphasize again, in addition to the common convergence results such the global asymptotic convergence and local and global linear convergence, the policy convergence (without any regularizations) and the exact asymptotic convergence rate have been established in this paper. The proof details of this section are presented Appendices C D and
For simplicity. here we only present the convergence results under the constant step size, i.e. 72 !J O. It is worth noting that the convergence results can be easily generalized to adaptive step sizes, with related results being presented in Appendix H
Alymplosy Convergence
(Theorem 3.1)
Exact ExactAsympiotiz Linear Convergence (Theorem 3.4)
Policy Convergence (Theorem 3.3)
Local Linear Convergence (Theorem 3.2)
Global Linear Convergence heeorm 3.6)
Dynamic Convergence
(Theorem 3.5)
Figure 1: Main convergence results of éduuddate and their relations.
3.1 GLOBAL ASYMPTOTIC CONVERGENCE
The key ingredient in the analysis the improvement at each state s in each iteration k represented as ThtV (*( k+ (s.s)
We start from the following ascent property of é-update. It can be proved by a direct computation, see Appendix C.I
non-negative improvement at every state, i.e.,
La n
have (++1(s)) (8) 2 (*()s) for every 8 E S.
As the value function is bounded (Lemma A.I in the appendix), Proposition 3.1 implics that V*( = limg-soc V (s) exists for all E S. The following theorem establishes the global convergence of é-update, L.e. 1 (s) = (x), Vs S.
Theorem 3.1 (Global Asymptotic Convergence). Suppose the assumptions ( (II hold. For a positive step-size 1) > 0, the value function generated by ó-update method converges to the optimal value, i.e. (8) = V*(ss) for all the states.
Remark 3.1. It is worth noting that under the softmax policy parameterization, ó-update can be formulated 0 0k + log Φ01 A (s,s))) a)). Despite this, the proof carried out in the parameter space Agarwal et al. (2027) cannot be applied to @-update with this parameter formulation. One of the key ingredients
therein for the proof is the property E. Ok Ea 00 a Vk, which comes from the fact Ea (V) 0 and
80,
5

---

Published as conference paper ICLR 2025
the parameter update form of 6,0 = 0%. +1 under the same softmax parameterization. Instead, our proof conducted completely the policy space.
(s)
In general, such property is not satisfied for é-update
00
As already mentioned, the existing techniques (e.g. Agarwal et al. 2021 Liu et al. 2023
Xiao 2022
not applicable since we only require very few assumptions on Φ and there are no particular structures to use. contrast, our proof leverages the explicit policy update formula of d-update discuss the behavior of the policy on different actions and compute the improvement. A contradiction is further constructed by showing that the improvement strictly positive based the statistical decoupling technique. See Appendix C.2 for the proof details.
3.2 POLICY CONVERGENCE AND EXACT ASYMPTOTIC LINEAR CONVERGENCE
Here we first establish the policy convergence the é-update, and then present the exact asymptotic con- vergence rate. To this end, we need to first study the local convergence of o-update. Note that, by the global convergence result (Theorem 3. for an arbitrarily small & O, there exists a time T(s) such that
k 2 T(s):
- v*I ||V'
S E.
such an e-sub-optimal region, we establish the following local linear convergence. Theorem 3.2 (Local Linear Convergence). Suppose the assumptions
(II) hold. Define
Pi A. o (- =))
(1-1)
Φ (-nEE
A
Let O be constant such that p (n, C) 1. Then the values generated by é-update method satisfy
|| V - 1l 5 (T,, A, ()
T
(1 2)
The proof is inspired by Khodadadian et al. (2021) ) which considers the policy ratio on sub-optimal actions. Lemma B.I in Appendix B shows that (a' [s)/= (a')s) S Pi (n, A),E). Combining it with the per- formance difference lemma (Lemma A.4 in Appendix A gives the result. See Appendix D.I for the proof details.
Based on the global asymptotic convergence (Theorem 3.1 and the local linear convergence (Theorem) 3.2 can establish the convergence of é-updatt in the policy domain with additional mild condition Φ.
Theorem 3.3 (Policy Convergence). Suppose the assumptions
(II) (III) hold. Then the policy generated by é-update converges to some optimal policy n", i.e. the sequence {nT [a }) converges to some π (als)
(T)
for any S and a E A.
It suffices to show that (a*)ss converges for all the optimal actions a' E A:; as (a'ls) vanishes for all & A by the global convergence result (Theorem 3.1.. This can be achieved by showing that (log x [s) J. is Cauchy sequence. To this end, we first bound the policy ratio on the optimal actions in Lemma B. (see Appendix B). Further utilizing the local linear convergence result (Theorem 3.2) can show loggrr * (a*1s)] e.
that Σm -k-T() log n -
See Appendix D.2 for the proof details.
Remark 3.2. For softmax NPG, one has (tt) = exp(t). Thus, it easy to see that o satisfies the assump- In addition, there holds
tions (1)
o'
= 1, VIER. (())
6

---

Published as a conference paper at ICLR 2025
Remark 3.3. In et al. (2023)), is shown that the policy produced by the homotopic policy mirror descent method converges to a uniform policy when there are multiple optimal policies. However, it should be noted that the analysis therein relies on the explicit entropy regularization in the algorithm. For vanilla policy gradient methods without regularizations, Theorem 3.3 is the first policy convergence guarantee result, to the best of our knowledge.
Based the convergence of the policy, the following result can be further established. Theorem 3.4 (Exact Asymptotic Linear Convergence), Suppose the assumptions
IIII
hold. Then
one has
x-- (*(n) V*(n) ((0)
(n)
lim k00
The key of the proof is the observation that the policy probability on non-optimal actions concentrates on the action set A',, where 8o E arg min, A., and the proof is to verify that the value error ratio is asymptotically equal to the policy ratio on Ale, See Appendix D.3 for the proof details.
Remark 3.4. It can be observed that the exact asymptotic rate does not depend on y explicitly (but y may affect A). To interpret it intuitively, first note that we have A z A' when the policy generated by o-update is nearly optimal. In such case, the problem can be roughly viewed as a bandit problem. That is, at each state, we just need to find the actions with the largest advantage, i.e. arg max, A A* o). As the bandit problem is an MDP with 7 = 0, it is natural that the asymptotic rate does not explicitly rely on 7,
consider a bandit problem (i.e. only one state and 7 = 0) where there are only two actions a1, a2 Assume r(s, 01) = > 0, r(s,a2) = O. Then is clear that the optimal action is 01, the non-optimal action is a2 and A r. By the performance difference lemma and the explicit formula of é-update there holds
Remark 3.5. To obtain a more intuitive understanding of 6(-n
(n(n) - vk+1(u) * (agls) (²)
① (s,
x² (azls)
x (
a1) T (ogls) (nA*(s
By the global convergence (Theorem 3.1 we have n² (agls) - 1, n (ag s) - 0, A (s. 01) - A (8,
O and A (s, + (s, - A. Hence the asymptotic rate of ( is observed.
Remark 3.6. Theorem 3.4 shows that the exact asymptotic convergence rate of softmax NPG is exp(-nA) which is also a new result for softmax NPG. Note that the O(e-(1-1/AMA) upper bound and and the ((e-n(++e) lower bound for local linear convergence of softmax NPG have been established in Kho- dadadian al.) (202]) and Liu et al.) (202bb respectively, where X and e are certain constants. It is worth noting that the exact asymptotic rate in this paper cannot be obtained directly from these two local bounds, but requires a different technique for proof.
3.3 GLOBAL LINEAR CONVERGENCE
Finally, we present the global linear convergence of the value function generated by ó-upddate The overall analysis idea is inspired by Liu et al. 2004bb). First the following lemma in Liu et al. (2024b) shows linear contraction can be achieved when the improvement has an I(max, A a)) lower bound.
Lemma 3.1 (Lemma 2.12 Liu et al. 2024b)). Assume En x kt1 for some C2 E [0, 1] and all s S, then
> C2 max, (t1s, a) holds
V - v++1|| 11:0 51 - (1 - (1-7)Ckk -V
7

---

Published as conference paper ICLR 2025
The following improvement lower bound can be established for d-update. Lemma 3.2 (Improvement Lower Bound). Suppose the assumptions (I) ") > O, the o-update improvement state satisfies
hold. With positive step-size
1 Σ n + (a|s) (s.0))
max (s,
1+ THE (A5) ( (bb.(())
where
① mn A ()) (-1s) 1ø (n a with (aass) ( { x1
ifa E A
A (1)
ifa o A
This lower bound is established by direct computation. See Appendix E.2 for the proof details.
Remark 3.7. The A can be seemed as dynamic measure of the d-scaled advaniage function gup at k-th iteration, as gh the policy value conditioned on the non-optimal action set.
Together with Lemma 3.1 the following dynamic convergence result of ø-update can be obtained directly. See Appendix E.3 for the proof.
Theorem 3.5 (Global Dynamic Convergence). Suppose the assumptions (1) 1) > O, the value function generated by o-update satisfies
hold. With positive step-size
1 (1 7) [ 1 ( -..))
VKEN: ||V* - V*
s <IIv*
voll
II 1=0
where Dj = min { TT. (At) (n) - and (s A + A}.
Remark 3.8. There exists bandit example which shows the error bound in Theorem 3.5 is tight, see Appendix(E.< Note that D2 likely be very small. Indeed,
interesting to see whether there is a worst case example which shows Dr can be exponentially small, as in Li el al. (2023a). It is also interesting to see whether we can use the techniques in a recent work (Klein et al. 2024) to address this issue.
We are now ready to establish the global linear convergence of é-update by combining Theorem Theorem 3.5 See Appendix for the proof details. Theorem 3.6 (Global Linear Convergence). Suppose the assumptions (I) (II) hold. Define
3.2 and
1
p(s) = max (M(s), #1 (n, [)), where x(s)
max (T)(()
(1 - 7)
- Dr
There exists E > 0 such that p(E) and
V Vo b
VkENt:
||V* - V*11 <
(1 - 7) p(E)**
4 EMPIRICAL VALIDATIONS AND DISCUSSION
4.1 EMPIRICAL VALIDATIONS
We empirically validate Theorems 3.3 and Luiig ((t) exp(t) (corresponding softmax NPG), o(t)
can be easily verified the last two scaling functions also satisfy the assumptions = 0.1, respectively.
(1 + exp(-t))-1 and ((t) = ttn + 1. The step size is set to 1, 17 = 1, and
8

---

Published as a conference paper ICLR 2025
we use a simple 5 X 5 Grid World problem to the policy convergence of d-update. The computational results are presented in Figure 2 The policy corresponding to the last iterate of upudde (denoted last) " presented in the second row of Figure 2 The plots in the first row display || π Jast ||, against the number of iterations which clearly show the convergence of the policy for the three tested db
For Theorem 3.3
For Theorem 3.4 we use random MDP to valid the exact asymptotic rate. The computational results are presented in Figure 3 It can be observed from the plots that the theoretical asymptotic rate match the empirical one very well.
In addition, more examples of ø-update have been tested, including extensions of softmax NPG and family polynomial update, see Appendix
4.2 IMPLEMENTATION UNDER GENERAL POLICY PARAMETERIZATIONS
Though we focus on the convergence analysis of é-update given the access to exact policy gradients in the tabular setting, it is worth pointing out that d-update can be implemented under general policy parameteri- zations (e.g.. artificial neural networks). As inspired by Tomar et al. (2020), we provide overall idea of the supervised learning implementation. More precisely, given a distribution over state space S and policy parameters 8 (or equivalently the policy n²) in the k-th iteration, denote by TH the target policy generated
by é-update given n² and 1/K. One can solve for the new parameters gk+1 by minimizing the KL divergence with 3.
gk+1 arg min Eawy [KL (To (-1s) || 1 (-1s))
0
no (als) x (als)
log To (a|s) Th (als)
log & (n (s)
]]]-
arg min E (1
It is worth noting that the normalization factor of d-update an issue in this supervised learning frame- work.
This idea be implemented in both on-policy and off-policy scenarios for real problems. For instance, one can use a critic network with parameter w to fit the value function. Collecting on-policy rollouts D = {ss, ag r2, ==> from current policy π², methods such as GAE (Schulman al. 2020) can be performed estimate the advantages A and the value targets Vinrg- Then the actor parameter and critic parameter are updated simultaneously by optimizing the policy objective loss (Eq (2) plus a value loss term. It is also feasible to extend this procedure the off-policy scenario by collecting reply buffer D, updating the critic parameters with methods like Temporal-Differen and optimizing Eq ( to update the actor parameter 9 with the estimated advantages. Some preliminary results about the implementation of é-update under the neural network parameterization have been reported Appendix
learning (see [Sutton & Barto (2018) for instance)
5 CONCLUSION AND FUTURE WORK
this paper, we have investigated class of policy optimization methods called é-update. For wide family of scaling functions, we have presented a series of convergence results for ø-update. In particular, the convergence of the policy is established even when the optimal policy is not unique. The exact asymptotic linear convergence rate is further established based on this result.
It should be noted that this work has been primarily concerned with the case of exact policy evaluation. under stochastic settings, the generalization to the analysis of inexact
As most of the RL applications é-update one of the future works. Additionally, is interesting to seek for more efficient & in practice and implement d-update for real problems via deep neural networks.
9

---

Published as a conference paper ICLR 2025
1.-
1.2
1.0
04
66-
100
200
100
930
500
230
593
631
3992
1866
2000
aee
1003
\
(a) (()) exp(()
(b) o(t) (1+exp(-t)
(c) @(1) (an(t) +
The simulation results on the simple 5 Grid World test policy convergence. For each grid except the green one, the agent can choose five actions (up, down, left, right, and stay) with no rewards. The green grid is the terminal state. Once the agent steps in, receives a reward and the game is terminated. The discount factor is set to 0.9, and we use a uniform policy as the initial policy. Note that there exists multiple optimal policies for this Grid World problem. Indeed, except the first row and the first column, there are two optimal actions for each grid (up and left). The é-update is run for a sufficiently number of iterations such that (p) - (p(p)= S. 10-16 16 (p is the uniform distribution over S), and the policy corresponding to the last iterate (denoted n maatt is presented in the second row. The oblique arrows in the plot essentially mean that the optimal policy produced by the ø-update has non-zero probability on every optimal action. The plots in the first row display ||TT" n Inst against the number of iterations.
Figure 2:
Convergrto
Canvergoic
COPNETRACE
2306
5000
7503
22000
5006
30303
15606
20000
10000
23000
30003
40060
(a) ((1) = exp(t))
(b) (tt) = (1 + expl -1 =1 (c) ((1) = (1) + 1,
Figure 3: The simulation results on the random MDP with |S] 50, |A| 10 and y 0.7. The reward r(s, a) and transition probability P(s'|s, a) are uniformly generated from [0, 1] (P is further normalized to be probability matrix). The initial state distribution μ is uniform on S. Blue curve is the log-value-error and the red line corresponds to the thcoretical convergence rate in Theorem 3.4
10

---

Published as conference paper ICLR 2025
ACKNOWLEDGEMENTS
Ke Wei partially supported by the National Key R&D Program of China (No. 2023YFA 1009300), Na- tional Natural Science Foundation China (No. 92370105), Natural Science Foundation of Shanghai (No. 23ZRI406400), and Science and Technology Commission of Shanghai Municipality (No. 23IC1401000).
REFERENCES
Alekh Agarwal, Sham M. Kakade, Jason Lee, 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.
Carlo Alfano, Rui Yuan, and Patrick Rebeschini. A novel framework for policy mirror descent with general parameterization and linear convergence. In Advances in Neural Information Processing Systems, 2023.
Emmeran Johnson, Ciara Pike-Burke, and Patrick Rebeschini. Optimal convergence rate for exact policy mirror descent in discounted markov decision processes. In Sixteenth European Workshop on Reinforce- ment Learning, 2023.
Sham Kakade. A natural policy gradient. In Advances in Neural Information Processing Systems, pp. 1531-1538, 2001.
Sham M. Kakade and John Langford. Approximately optimal approximate reinforcement learning. In International Conference on Machine Learning, pp. 267-274, 2002.
Sajad Khodadadian, Prakirt Raj Jhunjhunwala, Sushil Mahavir Varma, and Siva Theja Maguluri. On the linear convergence of natural policy gradient algorithm. IEEE Conference on Decision and Control, pp. 3794-3799, 2021.
Sara Klein, Xiangyuan Zhang, Tamer Başar, Simon Weissmann, and Leif Döring. Structure matters: Dy- namic policy gradient. arXiv:2411 11:/2241..444 1.0491,, 2024.
Guanghui Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sampling com-
plexity, and generalized problem classes. Mathematical Programming, 198(1):1099-1106, 2021.
Gen Li, Yuting Wei, Yuejie Chi, and Yuxin Chen. Softmax policy gradient methods can take exponential time to converge. Mathematical Programming, 201:707-802, 2023a.
Yan Li, Guanghui Lan, and Tuo Zhao. Homotopic policy mirror descent: Policy convergence, algorithmic regularization, and improved sample complexity. Mathematical Programming. 2023b.
Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv:1509.02977, 2015.
Jiacai Liu, Jinchi Chen, and Ke Wei. On the linear convergence of policy gradient under Hadamard param- eterization. arXiv:2305.19555 2023.
Jiacai Liu, Wenye Li, Dachao Lin, Ke Wei, and Zhihua Zhang. On the convergence of projected policy gradient for any constant step sizes. 2.0002211.00104, 2024a.
Jiacai Liu, Wenye Li, and Ke Wei. Elementary analysis of policy gradient methods, arxiv:2404.03372. 2024b.
11

---

Published as conference paper ICLR 2025
Jincheng Mei, Chenjun Xiao, Bo Dai, Lihong Li, Csaba Szepesvári, and Dale Schuurmans. Escaping the gravitational pull of softmax. In Advances in Neural Information Processing Systems, 2020a.
Jincheng Mei, Chenjun Xiao, Csaba Szepesvári, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning, pp. 6820-6829, 2020b.
Jincheng Mei, Yue Gao, Bo Dai, Csaba Szepesvári, and Dale Schuurmans. Leveraging non-uniformity in first-order non-convex optimization. International Conference on Machine Learning, 2021.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. Wiley Series in Probability and Statistics, 1994.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy opti- mization algorithms. (Tfi::770700347,, 2017.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High-dimensional continuous control using generalized advantage estimation. arxiv:150.002433, 2020.
Lior Shani, Yonathan Efroni, and Shie Mannor. Adaptive trust region policy optimization: Global conver- gence and faster rates for regularized MDPs. In AAAI Conference on Artifical Intelligence, 2020.
Richard Sutton and Andrew Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, 2018.
Richard S. Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for inforcement learning with function approximation. Advances in neural information processing systems, 1999.
Manan Tomar, Lior Shani, Yonathan Efroni, and Mohammad Ghavamzadeh. Mirror descent policy opti- mization. arxiv:2005.0988 09914, 2020.
Lin Xiao. On the convergence rates of policy gradient methods. Journal of Machine Learning Research, 23 (282):1-36, 2022.
Rui Yuan. Simon S. Du, Robert M. Gower, Alessandro Lazaric, and Lin Xiao. Linear convergence of natural policy gradient methods with log-linear policies. In The Eleventh International Conference Learning Representations, 2023.
Wenhao Zhan, Shicong Cen, Baihe Huang, Yuxin Chen, Jason D. Lee, and Yuejic Chi. Policy mirror descent for regularized reinforcement learning: generalized framework with linear convergence. SIAM Journal on Optimization, 33(2): 1061-1999,,,,, 2023.
12

---

Published as conference paper ICLR 2025
Appendix
Useful lemmas
13
B
Bounds of policy ratio
14
Proofs of results in Section
17
Proof of Proposition 3.1
17
Proof of Thhorem 3.1
17
Proofs of results in Section
20
D.I Proof of Theorem 3.2
20
D.2 Proof of Theorem
21
D.3 Proof of Theorem 3,4
24
Proofs of results in 3.ction3.3
27
Proof of Lemma 3.1
27
Proof of Lemma
27
Proof of Thherrm 3.5
28
bandit example for the tightness of Theorem 3.5
28
E.5
Proof of Theorem 3.6
29
F
More examples of o-update
29
Variants of softmax NPG
29
F22
Polynomial update
30
Preliminary numerical results on ø-update under neural network parameterization
30
H Convergence results for non-constant step size
32
A
USEFUL LEMMAS
In this section introduce several lemmas which useful in further analysis. The proofs omitted as these lemmas can be verified easily or can be found in previous works.
Lemma A.I. Under the assumption of (rrsss a) E [0, 1], for arbitrary x E 11, s S. a E A we have
1
(*(() 1 (*(s,
AT(
1- 1-71
13

---

Published as conference paper ICLR 2025
Lemma A.2. For any policy
- - A" 1 $ - - Vo
In this paper we use two metrics for the value error, (M) V= and I - V lemma says that these two metrics can be bounded by each other.
The following
Lemma A.3. For any policy
e 1 - 1 S (H) & I V=
Lemma A.4 (Performance difference lemma (Kakade & Langford 2002 ) Let A(S) be the probabilistic simplex S. Given two policies π and ω2 and arbitrary p ((S), there holds
maL (p) - (p) = 1 Ean
[T (s) V (s)
Σ (aaas)
g T
7
LaEA
Denoting by bg the probability on non-optimal actions
6 := T. (A
A
(als))
the following lemma from Liu (2024a)
provides lower bound of the value error based on b
Lemma A.5 (Lemma 2.5 (Liu et al.
2024a)). For any policy and p A(S),
V'(p) (p)
Bgnp [
A
At last we invoke two useful results from Liu et al. (2024b).
function Lemma A.6. For any random variable X and two real-valued functions f. 9. there holds
1 Ex,y [(f(X) f(Y)) (g(X) - -
Cov (f()),((x)) =
where Y is an i.i.d. copy of X. Lemma A.7. For any random variable X and two monotonically increasing functionn f and g. there holds
Cov (f(X), g(X)) 2 0.
B BOUNDS OF POLICY RATIO
This section provides bounds for the policy ratio
π +++
(a)
n (a|s)
14

---

Published as a conference paper ICLR 2025
We first provide bounds for policy ratio over non-optimal actions. Let A², := arg m A a) and
A, == minagA; (A" a) for E S. For an arbitrarily small e > 0, recall that T(s) is the time such that
V - |*] I e for all h 2 T(e). In such an e-sub-optimal local region, we give the following bounds for non-optimal actions.
Lemma B.1. Suppose the assumptions
(I) III
hold. For small enough & > O, when & 2 T(E) we have
VsEδ, 8, d' c##40 A
a (a'ss) ① (-n(A, -e)) <<(1l))
(1 (1-2) E 2 = (n) 8)
$ (-n1))
and
(d'ls) (dd18)
((-n(A,+e)) (2 A.,e)
V d' E Ay:
(4)
Φ (ne)
Remark B.1. The action set A' represents "the best non-optimal actions at state s". Eq ( shows that the policy on all non-optimal actions converges to zero with rate of Pr after k 2 T(e), and Eq gives the lower bound of the convergence rate of policy A',
Remark B.2. For softmax NPG, there has been dimension-free convergence results (see Agarwal et al. ( Xiao (2022) for instance) due to the good property of its mirror descent form. Thus a concise upper bound of T(E) can be computed (Khodadadian et al. 2022]. However, it is difficult to estimate T(s) for general o-updates, since such concise convergence result does not hold.
Proof. From || one has
1* S we have | -A Se by Lemma
A.2
Recalling the definition of A..
Ya' $ A;:
(s, s A3, d') + -,, +E, A d') 2 As, d') - = -A,- - -,,
Va' E A'
Va E A -s -s as) SE,
- < max (s, a) Se.
Note that
Tt (d'ls) x (a'ls)
o (nA" d'))
Va':
E Ba) @ (n744(s, a))]
By Lemma A.5 for any P E A(S) and 8 S.
A E.-plb S V - vo1l SE.
Considering as the one-point distribution on 8, one has
(5)
Hence for sufficiently small 8,
E Eaw [6 (n (s, 2 Σ x (nAs)
aeA:
2 Φ (-ne)
*² (als)
acA;
(1 - (%) Φ ( (-ME)
[1 A
Φ (-nE),
15

---

Published as conference paper ICLR 2025
and for any a' $ A
$ (v, (s,a)) s < -s)
which yields the result. On the other hand, it evident that
x ++1
* (d'ls)
Φ (-,) +s))
Va' E A
Th (a'(s)
(nE)
which completes the proof.
Next, we derive bounds for policy ratio over optimal actions.
Lemma B.2. Suppose the assumptions ( (II)
hold. Denote 6k:- = 1| - V
For any E S and the
optimal action a" E Ar when Ek A we have
π (a*ls)
d(-NER)
x (a*
Φ(E))) + Ek 66 66 Ex))
A
and
x k+ (a'ls)
S ((TEK)
nk (a (s)
(1 Ek
(17xkk)
Proof. By the formular of ø-update:
x x (a*ls)
(s,aa)
Th (a"(s)
B (s,a)
Exees; (a)a))))(AA ((nA"ssaa))
(6)
En'es ((((()))((14((3))))
We have
||- 1-*1llle 1:
V Vbll Ek. thus by the monotonicity of d there holds
o(-nEw) S (s, S((EE))
(1 (1-b))6 < Σ ~((a\s))((n*((s s (1 -1-1 ((nne))
a'Ed;
and
5 Σ =(d())))(14 <(-n(A Ek)). a'
Plugging them into Eq (6 and using 0 0 و < E A (Eq 5 yield the results.
16

---

Published as conference paper ICLR 2025
C PROOFS OF RESULTS IN SECTION 3.1
C.I PROOF PROPOSITION 3.1
The first claim follows directly from (we use A to represent ( a) for short)
Σ (5. = (a [A (1
Bxn (11s) (o(nA%
Cov aoWantt' (118) (1# (114 + Baw [A Baws*( [
Bewa [6(1A,,
Cov Covana (-1a) (4 (nA 2 O,
(Lemma A.7
E (aws)())s)) (6())...))
where the last line leverages the monotonicity and strict positivity assumptions of é. The second claim follows directly from the performance difference lemma (Lemma A.4)
C.2 PROOF OF THEOREM 3.1
Additional notations By Proposition 3.1, we know that the value function V is monotonically increasing. Since V is bounded (Lemma it's easy to know that limit value function exists. We define
(1) 1>=== ==
lim Vk
(2) 12)
=
lim Q+,
(3) 1 = lim 4
+0+
k-++00
For any state E S, we follow| Agarwal et al. 2021 to define the following three sets:
(1) {a E A 0 (8,a) > 0},
(2) = {a E A A (s = 0}.
(3) T (a A 00 (s,a) < 0)
Finally, for some action set Á
{I+ 10 1, }, define
1 A Σ オ (als) & (11A (s,a)),
a
and
d AA) =
n (als).
GEA
Proof sketch Similar to Agarwal et al. 2021 , the overall proof idea is to show that max, A < 0 for all S, then the global convergence given by the performance difference lemma (Lemma A.4). By the definition of I,, it suffices to prove that I,* is empty for any E S.
We use contradiction and assume there exists state Sq where I+ is not empty. We prove lemma to show that infş _ (Im)) > and inf - (I,,) > (Lemma
Noting that Vk+1 (1)) V -> 0, one can show that Σ,, n * k+ (als) ( (s, a) + 0 for all state
a direct computation shows that there exists a time To such that En x+++ (als) (8,0) a) with some positive constant holds for all k > To- It contradicts
With Lemma
xk+1 (als) A) (s
0 so the proof is completed.
17

---

Published as a conference paper ICLR 2025
Agarwal et al. (2021). the contradiction is performed by discussing the limits of softmax parameters. Hence the proof cannot directly apply in our case, where ø-update is performed in the policy space.
Lemma C.1. For any s E S, if is non-empty, then inf T. (1+)) > and inf T. (15) 0.
k
&
Proof. According to the definition of Φ-update, one has
Φ (nA* (s)
x ++1
(1+)= = Σ
nx (a|s)
Ev'E * (a'ls) Φ (n (s,d')
a
(1+)
By the definitions of 1t 1 and I5. is obvious that there exists time To E N and constant s >> 0 such that for all k 2 To (A is short for ((sa)))
(1) E 1 A >,
(2) |A
e 2'
(3) : A < -6.
(8)
By the monotonicity assumption of & and equation
1 (r!) > - (
15 (1.) S क (I.) Φ ( e
n (I9) o (NE),
(1,) S क (4.) o (-nE) < के (1,) o (1)))
Plugging it into yields that
~ Φ (ne) Φ (17) 1h (I + 1k (Iz)
k+1
(++t
o (It)
T (I+) Φ (TE))
( (It)
क (T)) + Th (I Φ (ME)
(I!+)
Thus the sequence (T (T+): k 2 To} is monotonically increasing, and one has
inf - (1+)
min
min * (I+) > 0
KSTo
T" (als) > 0 for any finite k. It's obvious that inf के (I.) 0. If not, as (a|s) 0, one has
lim inf m5 (T, O and then
t0000
lim inf
Σ nhe A (s.a)
inf
Σ A* (s, (s,o))
> I (5.0)
k t-00000
aert
aEIo
ac
lim inf
Σ
th A (5.0)
t00000
aext
0
which contradicts Ak e E. (a(s)) (s, = 0.
18

---

Published as a conference paper ICLR 2025
Proof of Theorem 3.7 As V monotonically increasing and V lim V exists, we have
lim ()+ V (n) = 0.
k-20
By the performance difference lemma (Lemma A.4).
Vk+1 (4) (u) Σ (5) Σ x k+l (als))A
As (s) > 0 and E. nt (als) a) 2 0, can be verified that equation 9 implies
YsES: : Σ (sls) +
(10)
the following, we will show that if there exists state so E S such that /+ is non-empty, then the condition equation (10) is violated, hence there must be I = Ø for all s.
By Lemma C.I we know that
C1 inf T (1++) 0 and
C2 inf T (1m)) O.
Recalling the definition of To. e and 1i,- for all k: 2 To.
π k+ (also)A* (so, a) =
z Banat(100) @ (11A* (su, a)) A (su. a)l
aEA
1
Z aov (0 (1AA* (s0, a)) A a)).
Let a' be an i.i.d. copy of a. Then by Lemma A.6
Σ BEAA
Exttle (a(sa)) (s).a)
1
E ( (1og)) [(At (so: a) - At (8)) (ø (nA* (so. - (nA* (so,d')))
2
1
Σ
(also) th (a'Iso) [A* (su, a) - A (so, a')) (Ø (n^* (su, (n^* (so, a')))
2Z
dEti, d'Elip
1
Σ
Σ
* (also) th (d'(so) [(e (-s)) (o (n1* (s0, - 2 (-ne))
27 30 aEIn, d'Elup
Z Σ
Σ
π (alsa) TM (a))s)) (o (n^* a)) - $ (-nE))
=
aELin d'Elm
Σ n (alsu) (o (n^* (5o. a)) o( (-n=)) x (Im)
Z
aE
C2E
Σ
π (a) (0) (Φ (1 (so, a)) (-r1E)
7
6
k (T+) Φ (-ne))
k
80
19

---

Published as a conference paper ICLR 2025
In the derivation above (AR (so, a) A (so, a')) (o (nA* (so, a)) o (nA* (50, 2 for any a, a'
by the monotonicity of Φ. Now notice that
=
1s (T+t) + 100 (Too) + 1 (Foo)
Thus for k 2 To.
T (1+t Ø (-ME)
1 (12))
Σ x
++1 (also) (50, (ah,a)26. 22-02
t (19)
+ 15 (1
1/ (Tz.)
1/ (T%))
k (1+)
Ø (-nE)
1
80
(It))
@ (ME)
-8.02
1 (T0
15 (I
1+
+
1h
(It)
15 (I
Φ (-T1))
(m))
k
(10
Φ (n
T (Im) @ (n
1
so
50
x sg
1
Φ (n)E)
a (I+b) ø (n!E)
(-nE)
① (nE)
= -E.02
70
k
1+
80
so
(mo)
50
I
-2202 T5
(I++)
1
Φ (-nE)
n18)
Φ (17E)
(1
Φ (-ne)
2 2..01.0 .02
> 0,
o (nE)
which contradicts equation (00). Thus for all 8 E S, one has max
(8, a) S and the global convergence
5,a
can be obtained by Lemma A.4 easily.
D PROOFS OF RESULTS IN SECTION 3.2
D.1 PROOF OF THEOREM 3.2
Combining Theorem 3.1 and Lemma B.I we know that there exists a time T(s) E N such that
TT))(),, SE S, A (als) < (1, A., E) (als)
< p (n. A, E) (a|s)
< ...
SP (n. A (t- -T() (als).
20

---

Published as a conference paper at ICLR 2025
By Lemma A.4 for all k 1 T(s),
V (4) - vk (4) -
d (s) Σ क
(als) |A (s,a)
SES
a
(s)
Σ (A
(A"(s, = for E 5)
$ES
aEA;
P1 (17, A,
(K (K=))
Σd
d (s) Σ T (als) 14" (s.a)
SES
a#A;
Pi (17, A. E) (K-)))))
d (s)
(T))
x T() (als) |A" (s,a)
1-7
T())
SES
ag
Pi (17 A. (K-)()))
(e)
(s)
Σ
π
Te) (als) |A (s.
1-7
(1 70 it
#
a4A;
P1 (17, A, (0)C-T(66 (TT)))
V* (w) -V((e) (w))
(1 (1-7) 7) 1
Pi (17 A,E (1-
E, (c))
V vT(e)
(1 (1-7) it
By Lemma A.3
TE):
V| - 1
S 1
(V* (4) - v* (R)
0 (1, A, 5)(² (Te))
VTe)
(11)
(1 7) 112
P1 (1), A,E) e): (Te))
(1- p?2
D.2 PROOF OF THEOREM 3.3
Proof sketch By the global asymptotic convergence result (Theorem 3.1 the policy value of sub-optimal actions vanish, i.e. (a'ss) + 0 for all s and a' & A Thus it suffices to show that n² (a" converges for any state 8 E S and optimal action a" E Ag. Denote e == || Vk]
Recall that Lemma B.2 characterizes the contraction rate of n² (a*1s) in the local region (i.e. E is small). It is shown that
o(-nEx)
x (a"1s) Φ(nEx) d(MEL) π (a*ss)
ő(-
The crucial part is to show that {log x (a" [s) } is a Cauchy sequence. Fix a sufficiently small E. By Lemma B.2 and the assumption for o, it can be shown that
log n T(s)+++1 (a*)s) log x (a*))(())))) $ ET())+
21

---

Published as conference paper ICLR 2025
By the local linear convergence we have et(e)+ & p E. Basing it show that
log π + (aa)) log क' (a*ls) SE
(=)
which verifies the Cauchy property.
As log n (a*ls) converges, we know that log nH (a*ls) > -co, thus x (a*ls) also converges. For the sub-optimal actions a' Ag there holds n (a'ls) + indeed. Hence the policy convergence is established.
Proof. As we have established the global asymptotic convergence (i.e. V + V*, Theorem 3.1 conclude that (a'lss) + 0 for all 8 E S and a' & A Thus it suffices show that x (*("l>>) converges for all 8 E S and optimal actions a² E A
we can
First note that n* (als) > 0 for all k. Thus, log log=* (als) is properly defind. Additionally, is not hard see that pi (n, E) decreases as decreases, thus there exists so such that for any 0 < Eo we have (1 A) S (n, Eu) < 1. Now we are going to show that {log x" (a"(ss) is Cauchy sequence. For arbitrary& & > 0 which is small enough to satisfy & S min {6/1) A/2, Ea), there exists a time ((e) such that
W 2 :()):
Ek ==
|
v 1l SE.
Furthermore, by the local convergence rate result (Eq we have
v T(e) Ek S (1 7) PI (n, A
(12)
Now we consider summation
log π ++1 (a*ss) - log (a'1ss)
Jo 7(s)
By Lemma B.2 for any k 2 T(E) one has
log x (**((aaas)) log
(((EE)) + Ek o( o(-n(A Ek))
((TE))
< log max
n)x))
(1
Ek
Φ(-NEK)
A
d(NEx) 0b (1-n -Ex)
(1(TEE)
< log
+ log
((-1Ec)
[1 A
Ek
Φ( (()))E))
22

---

Published as a conference paper at ICLR 2025
For the first term, noting EN I - 4/2 one has
Φ(TE)) + Ek 6- Ex))
Φ(TEx) Φ5 -TE))
+ Ek A
log
log
T=)(c)
k=T(=)
OC
1 + 8k
d(NEx)
log
Φ( - -nex))
T=T(c)
5k +
<(TEK)
log
log
A
(1-
T=T())
k= T=T((c)
80
8
((NEk) o( (
Ek
log
km ((c)
Am ((3)
By the assumption (III and E S 8/17, we have
(1T5x)
log Φ (1)))x) log ((ME)) - log () = (2nEx) log x(Ex) S 2cTEx
(13)
dt
where Ex E [--nER, nEX]. [EN] Using Eq 10) and Eq 12 we get (noting that ((1), A, E) < 1)
((Ex)) Ek p
( (-
Ex))
log x--nEx)
+ 2c7
Σ Ek
A
k=)(e)
k=T(s)
+ 201
<
(1
7)12
- p1 (11 A,
For the second term, one has
((TEK)
8
((TEE)
8
8k
log
log
log
(1 A
8k
@1 ((-1)E))
(-TEE)
A
T=T(c)
k=T(c)
T=T(c)
Φ(TEK)
log
+
EK
x( -)))
k= T=
T())
+ 2en
E
<
(1 7i7
1 p1 (,)
where the first inequality uses éμ < A/2 and the fact that
A < < 1/2: - log(1 - -x) =x) Sx.
Putting them together yields
3 + 2Cg
28
log k+1 (a"ls")s) - log * <aa1ss)|
<
(1 7) 1 - Pr (1) A,
(=)
3
1 + 2cg
2
Coe.
(1 7) 1 P1 (17, so)
Therefore, after a variable substitution, has shown that flog n (a*1)))) xx (a*Is) converges for any s S and a" A
Cauchy sequence. Hence
23

---

Published as conference paper ICLR 2025
D.3 PROOF THEOREM 3.4
Proof sketch We can assume that S == S without loss of generality. Recall the state set So arg min, A, and action set A., = arg max, EA; (s,
We first prove Lemma D.1 which tells that when A + +oo, the policy probability on the non- optimal actions concentrated on n² (0o)(s) where so E Su and do E A
Then we directly expand (*) (p) and (*) (*) to the weighted summation of A (s, a)l by the performance difference lemma (Lemma A.4p.
We consider the case that d: A and n* are all in local regions, which can be acheived by large enough By direct calculation, we show that the convergence rate is bounded by Ç1 and (2. As well the local convergence rate.
k - +oc, both Çi and {2 converge to o( ((-nA)/ (00),
Lemma D.1. Consider the q-update with constant step size n 1 O. For any E S,a E A such that |A* (s, a)l > A, one has
x (als)
lim 20000
0.
EegeSo Encedt T² (ag(s))
Proof. Using the same procedure as in the proof of Lemma B. one can easily show that for sufficiently
small O, there exists a time (c)) such that for all & 2 T(c):
n (als)
(--n (3,
VsES, $ A;
Sc.
(als)
Φ (0)
Then for all k 2 T(c).
x T(c) (aol8o) (d(-n)1-(saa)) ((0)
(1 + c) k-T(c)
x² (a|s)
Engeoon x (0ols0)
Σ EegESoravEd x T(()) (aulso) ((-nd)
(1 c))
k-T(()
+10)
(s-))d"(s.a)
k-T(c)
TT() (aolso)
6(0)
1 C
Em $ T(c) (ao|50)
o (--AA)
6(0)
T(c) (oolsu)
④ 6--n |A" (s, (s,a))) 1 1+c) k-T(c)
EenESo.nnE1 [C(c (aolso)
Φ (-nA)
1-c
For any s E S and a E A such that |A* (s, > A, one has @ (-nnAA (s,a)))/0 (-n < Thus it's
trivial that
n (a|s)
lim k
Enn E00 x (aols0)
by sufficiently small
24

---

Published as a conference paper at ICLR 2025
Proof of Theorem 3.4 By Theorem
3.3 we have x² + π² for some optimal policy x², therefore d + dz.
Now, for arbitrary & 0,8 0,a > 0, there exists time T(s, o, σ) > 0 such that
(s)
(5)
E S, k2 T(E,
S 6,
1
S 6,
(s)
d (s)
(s)
x (aas) s)
| - 141l E,
C2
where (s,0) E a(s,a): (A" a)l > A}. By the performance difference lemma (Lemma A.4.
- (++)(()
2 (8) En' x * (s,
V*(N) - (k(1))
Σ, (b) EEA T **al(s)
A (s, a')l
E. ( La'EA;
(a'ls))))) Ch
A (0, a')l
E, d/ Ed'gAt KEA
* Cx
|A (s a')l
By Lemma B.1
V'(n) (x+
V*(n) - (*(()
-1 E. (s) Edee:
(s)
*'a'llo) C (A*
(in(-A,+e) n(-
< (1 8
EA;
A
(5) {
=ta'(ss
(s'()))))
C2
By expanding the summation on numerator and dropping out some summation terms in denominator we get
(*(w) (K+
(*(H) - (=(H))
Eogs det (s) Es)ss
*t(lle Ca
|A*(s, (6(((-.+ts)
((-
1
Ap
EmEES (1(())) Eaged
AA (s)) *=(gg100)
Cn
-1
EnEEs d (10) Eare(As, u.r
(s,
d(n(-A+e))
E
O
+
AT
ExeES, (2%(0)) EnsEds
(*ool0)))
A (A0 (s);
Ci
EegEs, ditt((s) Enses, T"(aul |A (80. an)
(1 (1-
8
Hb[[( ( +
+
A
o( o(-nE)
Eeoeso (H( Eagest n (aolso) |A* (8o, an)
25

---

Published as a conference paper at ICLR 2025
Noting that (5o, ao)l = A, (s0) S (50) + + (d'ss/a I o, and (s,(), & 1/(1- - -7), it follows that:
('())= - (1)
(=(n) (m)
-1 Eneso d (s) Em'ga; RA;; 1-7
8
((-nE)
Ap/
E EneES (2)) Eagedho
(anlee))
Ch
(11
8
-1
Exneso of d (s0) Ee'e( U(b,))
1-7
div( At))
-(-
+
A
ExoEso d2((00 Enpedi
*>(00180)
Ck
1
E
-1 (0(((-A
EooEso (4%(60) + 5) Eosedt *² (ao(so)) A EnoEsO (5())) EonEr. I² (hooos0)) A
+
A
((-1E)
Noting that
r" (aols0)) Ck
E ExoEs d4(50) EapeA, {cols00 Eosesh Enseti I (aolso))
Σ (
A
E {(1--))AA,4]
So
D0 000
one has,
(n())= - (1)
E
)
-1
pn(( - A +e))
a|A1|
8A E. SOeEs Engedi ~² (aglso)
S
1
+
A Σ Eeges, d2((0) E Eeces I (aolss)) +1
V=(n)= - (k(
A
(--1E)
71-7)<AA
E
ø(n( - A +e))
g|AA|
+ (1- 7)u (1-7);² +1)
8
<
A
Φ(-1E)
(1-
== o).
On the other hand, we have
V*(() - (M)
E. dett Ex'
[A" a')l
C.
V*(H) - (w)
E. d (s) Em'ga
st(al())
(A*(s,
Cx
The denominator can be bounded as,
(a'ls)
(a'ss)
Ed((s) Σ
A" = Σ (5)))
|
Ck
Ck
a'RA;
$g
*² (a'(so)
(30)
E
A
80
a' UAi))
+
ak (so)
Σ
A
Ck
8g
ao GOEAA
7 A|A
* (anl80)) Cx
d (80)
A.
1
26

---

Published as conference paper ICLR 2025
For the numerator, there holds
++1 (a'l8)
(atl00)))))
Σ t (s)
(s
Σ
(so) Σ
Ck
#
50ESp
p + =])
n" (anlso)
Σ
(d -8)
A.
Φ(1)))
Cn
#0
Go RoEA
Consequently,
(H) - (x+
V*(n) vK(
0 71 ((-nn(+ +
Exoeso (d)) - 8) E EooEAl
Ct
A
o(nE)
d|A 1-y + EnsEs d)() E EnoEdi *
A
Ci
((--n(A+ +
Enoeso (50) Engerho
['(nnlop) Ck
8 E Enoed x=(ool00)
C
A
6(TE)
Exees (5) EnDEsh
(aglaa)
o|A + Emes, d2((0) Ensess x (aulso)
Ck
Cx
pl p(-n(A +E))
8A
2
ó(TE)
GLAl
I-7 (1 - 7)
PA
= 6,)
As - 0,5 - 0, - 0, there holds 61 + ((-n)a//(()) and Ca(e, - ((-r)\//((), We
finally have
V*(H) 1K+1 (H) o(-1A)
lim A=000 (*( (4(1) x(0)
which completes the proof.
E PROOFS OF RESULTS IN SECTION 3.3
E.1 PROOF OF LEMMA 3.1
The proof of Lemma 3.1 can be found in Lemma 2.12 of Liu al. (2024b), so we omit the details here.
E.2 PROOF OF LEMMA 3.2
According to the definition of é-update, is obvious that
Σ k+1 b+ (als) Bawxi(-la) [A ())(nA)(sssA) a))]
(x)x+(1)) (
27

---

Published as conference paper ICLR 2025
From (1 [A a)] 0 and the definition of (-1s) in Lemma 3.2, we get
n" (A*)) max A (s, (1- -. (At)) Ba Ber [A (A =0.
(14)
For the numerator (we use A = (s, a) for short).
(1s))()))) [A (nA
= = (on max A max A 9,a + (1 - n. (At)) Be (et [o(n 2,00 )
2 n. (on max A max A (1 x (At)) B (e [o(n E Bei [4
(A*) max A & mmx A (t (6b (114t,a)
where the second inequality is from Lemma A.7 and the last line comes from the equation denominator,
14 For the
(a (11s) ( (1
n (A.)) @ (1) mmax A + (1 2 (Att) Bainer [& (nA5
n (At) (n Abaa) (-(n) 1 (n [ Ba' [d (n
Hence
Σ (c)s)))))
max A A (s.
o (n max, (t(s (aingst(lo) (o (n
1 + n (AA))
max (s)
1 n (At)
(A) 11))-11))
E.3 PROOF OF THEOREM 3.5
Combining Lemma 3.1 and Lemmal
3.2 together yields this result.
E.4 A BANDIT EXAMPLE FOR THE TIGHTNESS OF THEOREM 3.5
Consider the following bandit problem:
S = (s), A= (a1, a1) 1, ((8,02) 0.
Under this problem setting, it is clear that for any (Ta, is short for ((a(s))
(s(()a1) = 1, (" = 0. V V"((s) 'Ta A" (s 01) = Ray. A (s, 02) -Ta
It is also clear that a is the optimal action and V (s((s)
28

---

Published as a conference paper ICLR 2025
The d-update on action 01 is given by (the subscript s in 1/ is also omitted)
n ++1 T Φ (1f (1 m. ))
7
where
2 = -. 2 (17 (1 - )) + (1 # ) (-1f T
It can be verified directly that
(1
x(-rtt -11 ))
(V) vkk+((s)
1 1 Tua
H5 -mai)) -1) 1
(1 - nart)
(s) - (s).
Consequently,
k-1
- x0.1)
(s) V* (V* r (s)
II
6(-n""
Noting that y 0 and (A{) n. it shows that the bound in Theorem 3.5 holds with equality for this example.
E.5 PROOF OF THEOREM 3.6
For sufficiently small > 0, by Theorem 3.5 we have
1
[
1 1
A k < T(s): ||V* - v*l -
- voll -
II
1 1- (1-
1-14D.)
1=0
$ <|Iv* - voll k(E)*,
By Theorem 3.2 Ssee Eq
we have
Vk 2 T()): V vk
S
1
V+ VT())
PI (n. A, E) (TT()
(1 7)
Combining them we get
V' - -vo
VkENT: - 1+1 S
mmax (n((), Pi (n. A,))
(1 - pp²
V' V0ll
7)1r² -(E))*
F. MORE EXAMPLES OF --UPDATE
F.1 VARIANTS OF SOFTMAX NPG
Recall that softmax NPG is a ø-update instance with á = exp(-). It is natural to generalize it to an exponen- tial family of ó. For instance, it is direct to consider the following exponential family 6:
((t) exp( (t)p
29

---

Published as a conference paper ICLR 2025
for some positive and odd p. I When p q, it is clear o(t) satisfies the assumptions (I) p < (tt) is not differentiable around 0, so we consider the following piece-wise variant:
11I)
IIII
When
- 1exp(6p/9-1 t)
[exp( (t)P
i [-00,-0] +x,c,,
((t)
(15)
if (-6,6)
d di
with some small constant ò It can be easily verified that the assumptions (1)
log @11) 8P/9 when / (-6, 6,68 6), thus
hold.
The convergence results é-update for difference p and q (when p 9. we use (15) are presented in Figure ((a) The theoretical results of Theorem 3..4 3.6 imply that the convergence rate becomes smaller when ((() changes rapidly around / = O. Noting that when
q and 5 small, ((t) in the O-neighbourhood is "stretched",, and the stretch intensity becomes stronger as p/q and d are smaller. The simulations show that under the exact gradient, é-update enjoys a better tail convergence than softmax NPG when < q.
F.2 POLYNOMIAL UPDATE
Recall the policy update form of Hadamard PG, which special case é-update with d(t) (1 + 21) Thus it is natural to generalize it to family of é-updates (coined as polynomial update here and denoted by (ply(p) for different p E ++) with ø being given by
(t)) = + pt).
It is clear that (tt) satisfies L stretches around as p increases.
with L = 1/p. It can also be observed that ((t) = (1 + pt)²
Remark F.1. Recall the escort parameterization in Mei et al. (020a)
with hyperparameter p.
10
10.a
TT(als)
Ea 12,0l
110.11p
Escort PG updates the parameters by
@V*(p)
g 0 + 100110111 11081
A S, a
(16)
00k
Under escort parameterization, be verified that (ply(p) can be implemented by modifying (16
SsES, A
gh++1
2,a +
110%11 (6) -(p-2) (egn(Ot.)))
(v*
OAk
where sgn(-) ) is the sign fignctinioon In Figure 4(b) we compare Poly (p) and escort PG with different selections p.
G PRELIMINARY NUMERICAL RESULTS ON Ó-UPDATE UNDER NEURAL NETWORK PARAMETERIZATION
We have conducted some preliminary numerical experiments on d-update under the neural network parame- terization for the exponential family presented in Section F.I Three environments from MuloCo tested,
We use V(-)² instead of (-)P/9 avoid the ambiguity of the power function. instance p 3, q = and p
q 10 different under V(-)² but equivalent under (-)//3
30

---

Published as conference paper ICLR 2025
softmax NPG (p=1.
p=3,4=5,8=000
p=3,q=7,8=0.01
p-5.q-3
log value error
p=7.q=5
-6
log value
Poly(2)
-12
Escort(4)
Poly(4)
-14
-8
Escort(6)
Paly(6)
400
800
1200
1600
8000
16600
24000
iters
(a) Variants softmax NPG
(b) Polynomial update
Figure 4: Simulation results on random MDP problem (with the same setting the experiments presented
in Figure 3.. The step-size is set to be 17 1 for (a). For (b), the step-size is state-dependent following Mei
(2020a) and to be 0.01 |0_1| for escort PG, and is be 0.01 for Poly(p). Note that Poly(2) is equivalent Hadamard PG or escort PG with p= 2.
ppp
PB
Ndtan the
(a) HalfCheetah-v2
(b) Hopper-v2
(c) Walker-v2
Figure 5: Preliminary numerical results on é-update under neural network parameterization.
and results are presented Figure 5 For each experiment, compute the mean and the standard deviation of the final accumulative reward across 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 are only intended to illustrate implementation feasibility of é-update, rather than claim its state-of-the-art results. In fact, comprehensive empirical evaluations of é-uudate is beyond the scope of this paper, especially on how to choose é for different problems, which will be left for future work.
31

---

Published as a conference paper ICLR 2025
H CONVERGENCE RESULTS FOR NON-CONSTANT STEP SIZE
In the following, we present the convergence results for the adaptive step size sequence {n, The proofs are overall similar to the case of constant step size (Appendix C D Thus, we do not provide complete proof details, but only point out the proof differences.
hold. For any positive step-size sequence {1²) > O, é-update has non non-negative improvement at every state, i.e., E. ( (als) 2 0 for any and k. Furthermore, we have (s) 2 (s) every E E.S.
Proposition H.1. Suppose the assumptions
(I) (II)
Proof. The proof is the same with that for Proposition 3.1 as v > O.
Theorem H.1 (Global Convergence). Suppose the assumptions (1) (II) hold. For a step-size sequence { such that inf of > 0, the value function generated by ø-update method converges to the optimal value, i.e, (*) (s) = (s) for all state s.
Proof. First note that the proof of Lemma C.1 remains unchanged for non-constant step-sizes {n/}-
Let C3 == io, n. > where so is the state such that It is non-empty. By the same computation,
Σ
x k+1 (a) (0) (s)
rEA
2
Σ
x (also) Th (d'1so) [(A* (s0, a) - A (s0. d') (0 (1 A (5o, a)) - (ver A (80, (o))
27k
aetiy a'Elop
Σ
Σ
x (also) nh (a'1so) [(E- (-+)) (0 (1t Al (so, o ((c3E))
2Zk 50
oEth d'Elep
C25
Σ * (also) (o (v A (su, o (-c3E)
Z
aELi
C2E
(1
(I+t)
Tea (Ttt.) a (-ccE))
7h
Similarly, one has
(1- (-CoE) Φ (cyE)
Σ h+t (alsu)A* (su, a) 2 8. C2
> 0,
aEAA
which also raises an contradiction. Hence the proof of Theorem 3.1 can be proceeded for the non-constant step-sizes provided inf a, 1/ O.
Lemma H.1 Suppose the assumptions
(II) hold. For small enough > when l 2 T(=) we have
vS S, a' A
x k+ (a'
(A.-
(1 E = =pi(n. A,,E),
(17)
n (a'ls)
(-ntE)
A
and
(a'ls)
$ (-n +e))
vs S, d' E AA:
= p2( Es,
(18)
(a'lss
1 (nte) c)
32

---

Published as conference paper ICLR 2025
Proof. The proof remains the same with that for Lemma B.1
Lemma H.2. Suppose the assumptions I
III
hold. Denote ek = =I 1l For any S and the
optimal action a' E Az when < A we have
x*+1(a" (a'ls)
o( =x)
n& (a
ck <( +
1// (A - Ex))
A
and
x+ (a'ls)
1
(a
1
Φ =k)
A
Proof. The proof remains the same with that for Lemma
B.2
Theorem H.2 (Local Linear Upper Bound). Suppose the assumptions (
II hold. Assume that inf a ny
O. Then there exists small enough > 0 such that sups,k P1(1% A, and a time T(e) such that the values generated by é-update method satisfy
ssup, PI (1/², A, e)] (k=)()))
vk Te):
V - V I
(1-
Proof. By Lemma H.I
have
Ak 2 (c), s SE S, a A:: x² (a|s) & pı(n ,,,,-,,A,E)) -, (als)
Pa A e) x T(e) (als)
(sup,,e Pi (v A =)] (h-r))))) T(te) (als).
Then the proof in Theorem 3.2 can be proceeded similarly the constant step size case.
Theorem H.3 (Policy Convergence). Suppose the assumptions quence (T 3 satisfying inf,,k n. > and sup..k nt < +00, the policy generated by é-update converges to some optimal policy x", iee. the sequence (a/s)) converges for any E S and E A.
hold. With the step-size
Proof. Following the same procedure of the proof for Theorem 3.3 by selecting small enough e and Eg such that sups,k P1 (1r A) < sup,.k Pi (1/ A, Eo) 1, one can get
1/2 2csups,, 1/
2e
Σ log n. + (a*1s) - log xh (a (a*1s) A=)(e)
<
1 1- I-sup,,a PI (n A, A,E = Coe.
(1 ?)
Hence flog "h (s) is still Cauchy sequence, implying that (a*)s) converges.
33

---

Published as a conference paper ICLR 2025
Theorem H.4 (Exact Asymptotic Linear Convergence), Suppose the assumptions 1
III III
hold. Assume
"h = lim of exists for all E S. Then
(*()) - (b+ ob- mins,a (
1 (s,
lim R-+00 (=(p) ((())-((pp)
((0)
Proof. One follow the same procedure in the proof of Theorem 3.4 get this result by further considering the local region of n.. That is, consider the following local region:
As 233 S k T(s,
(s)
d (s)
6,
8,
(*)
di (s)
x² <alss)
- - Ss
S o,
|1/2 1/3
SE
Ck
where e, ó, o, are all sufficiently small constants.
Lemma H.3 (Improvement Lower Bound). Suppose the assumptions sequence (n²), the d-update improvement of state satisfies
(I)
11I
hold. With positive step-size
Σ (als) (s,
max A (8,
1 Th (At) (1,0
where
@ (1 max, A A a)) Eg Ea' (-Is) 1 (n)g (s, a'))]
10
ifa Ab, if & A
with (*(as)
TTM (als)/(1 (a()))((1=+(())))
Proof.
The proof remains the same with that for Lemma 3.2
Theorem H.5. Suppose the assumptions (I) (II) hold. With positive step-size sequence {n/ the value function generated by é-update satisfies
VKEN
||V* - V*
1 - 111 roll
II 1=0
1 (1 (1--) 11---D.)
where D, == min seS. (T) ( (1)) and St = {s E S Ab *
Proof. The proof remains the same with that for Theorem 3.5
Theorem H.6 (Global Linear Convergence). Suppose the assumptions
11) hold.
Assume that
infe Th > O. Define
p(e) = max {N(E), supa. P (n.: }
where
{ {1- (1-) k<)(s))
1
<(E) = max
Dr
There exists E > 0 such that p(s) < and
V r
VkENt: ||V*-V VR <
p(s)*
- 7)
Proof.
Similar to the proof of Theorem 3.6 but instead use Theorem
H.2 and Theorem HS
34


Reviews:
[{"review_id": "7aYfD7WkgG", "reviewer": "Reviewer_rtXi", "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.\n\nThe 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.", "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).\n\nIn 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.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed $\\phi$-update is sort of different but connected with existing methods.\n\nThe analysis is comprehensive and theoretical results are fine.\n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xUA32pXYaM", "reviewer": "Reviewer_29J3", "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.", "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?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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).\n\n- 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.\n\nShani, 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.\n\nLan, Guanghui. \"Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes.\" Mathematical programming 198.1 (2023): 1059-1106.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "llFzUUqo0q", "reviewer": "Reviewer_7X97", "summary": "phi-update\n\nSummary: 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). \n\nSignificance: 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.\n\nSoundness: 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.\n\nRelated 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).\n\nPresentation: 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?", "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.\n\nI 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?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FYIlobOIl7", "reviewer": "Reviewer_NGsf", "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.", "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).\n\n**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? \n\n\n\n[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.*", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**S1:**\tWell-motivated new policy update.\n\n**S2:**\tSolid theoretical analysis in the exact gradient setting, both asymptotic and non-asymptotic, although I have a question regarding the linear convergence rate (see below).\n\n**S3:**\tThe 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$?\n\n**W2:** Analysis limited to exact gradient case, stochastic analysis would be interesting. \n\n**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. \n\nAlthough 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\n\n**Minors:**\n\nTypo in the definition of $\\kappa(\\epsilon)$? It should be $\\max_{t\\leq T(\\epsilon)}$ as there is no $k$ apprearing within the max.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)