Global Convergence of Policy Gradient in Average Reward MDPs
Authors: Navdeep Kumar
Yashaswini Murthy
Itai Shufaro
Kfir Yehuda Levy
R. Srikant
Shie Mannor
Venue: ICLR 2025 Poster (2025)
Keywords: Policy Gradient
Reinforcement Learning
Average Reward MDPs
Primary area: reinforcement learning

Abstract: We present the first comprehensive finite-time global convergence analysis of policy gradient for infinite horizon average reward Markov decision processes (MDPs). Specifically, we focus on ergodic tabular MDPs with finite state and action spaces. Our analysis shows that the policy gradient iterates converge to the optimal policy at a sublinear rate of $O(\frac{1}{T})$, where $T$ represents the number of iterations. Performance bounds for discounted reward MDPs cannot be easily extended to average reward MDPs as the bounds grow proportional to the fifth power of the effective horizon. Recent work on such extensions makes a smoothness assumption that has not been verified. Thus, our primary contribution is in providing the first complete proof that the policy gradient algorithm converges globally for average-reward MDPs, without such an assumption. We also obtain the corresponding finite-time performance guarantees. In contrast to the existing discounted reward performance bounds, our performance bounds have an explicit dependence on constants that capture the complexity of the underlying MDP. Motivated by this observation, we reexamine and improve the existing performance bounds for discounted reward MDPs. We also present simulations that empirically validate the result.

Published as a conference paper at ICLR 2025
GLOBAL CONVERGENCE OF POLICY GRADIENT IN Av- ERAGE REWARD MDPs
Navdeep Kumar"
Yashaswini Murthy" ECE CSL
Electrical and Computer Engincering Technion Israel Institute of Technology
University of Illinois Lrrana-Champaign
navdeepkumar@eee campus. techni on ac il
ymurthy2@illinon .deu
Itai Shufaro
Kfir Y. Levy
Electrical and Computer Engineering Technion Israel Institute of Technology itai, shufaro@campus technion. .ac. il
Electrical and Computer Engineering Technion Israel Institute of Technology k efirylent weyylley@@eechiioo.
R. Srikant
Shie Mannor
ECE & CSL
Electrical Engineering
University of Illinois Urbana Urbana-Champann Champaign rsrikant Mellllline iiliiniiii.iiiiii edu
Technion Israel Institute of Technology
NVIDIA Research
shi shieêee. technion. aac...iiin...................... i1
ABSTRACT
We present the first comprehensive finite-time global convergence analysis policy gradient for infinite horizon average reward Markov decision processes (MDPs). Specifically, we focus on ergodic tabular MDPs with finite state and action spaces. Our analysis shows that the policy gradient iterates converge the optimal policy at a sublinear rate O (2), where T represents the number of iterations. Performance bounds for discounted reward MDPs cannot be easily extended average reward MDPs as the bounds grow proportional to the fifth power of the effective horizon. Recent work on such extensions makes smoothness assumption that has not been verified. Thus, our primary contribution is in providing the first complete proof that the policy gradient algorithm converges globally for average- reward MDPs, without such an assumption. We also obtain the corresponding finite-time performance guarantees. contrast to the existing discounted reward performance bounds, performance bounds have explicit dependence on constants that capture the complexity of the underlying MDP. Motivated by this observation, reexamine and improve the existing performance bounds for discounted reward MDPs. We also present simulations that empirically validate the result.
INTRODUCTION
Average reward Markov Decision Processes (MDPs) find applications in domains where decisions are made over time to optimize long-term performance. Some of these applications include resource
allocation, portfolio management finance, healthcare, and robotics (Ghalme al. 202T Bielecki
et al. 1999 Patrick & Begen 2011 Mahadevan 1996] Tadepalli & Ok 1998). Approaches for
determining the optimal policy can broadly categorized into dynamic programming algorithms
(such as value and policy iteration (Murthy et al. 2024 Abbasi- Yadkori et al. 2019 Gosavi 2004))
and gradient-baas
algorithms. Although gradient-basee algorithms are heavily used practice (Schulman et al. 2015 Baxter & Bartlett 2000), the theoretical analysis of their global convergence a relatively recent undertaking.
"Equal contribution

---

Published as a conference paper at ICLR 2025
While extensive research has been conducted on the global convergence of policy gradient methods in the context of discounted reward MDPs (Agarwal et al. 2020] Khodadadian et al. (021), compara- tively less attention has been given to its average reward counterpart. Contrary to average reward MDPs, the presence of discount factor (7 < 1) serves as a source of contraction that alleviates the technical challenges involved in analyzing the performance of various algorithms in the context of discounted reward MDPs. Consequently, many algorithms designed for average reward MDPs are evaluated using the framework of discounted MDPs, where the discount factor approaches one Grand Clément & Petrik 2024).
In the context of discounted reward MDPs, the projected policy gradient (PPG) algorithm converges as
1
- th 0 (1 (1-7)8
where is is the discount factor, Ty is the policy obtained at the k-th iteration of the PPG algorithm, p"ay represents the optimal value function, and pry** represents the value function iterates obtained through projected gradient ascent (Xiao 2022b). Let p" denote the average reward associated with some policy π. It is well known that pa lim, -1 (1 11--1 >?pp under some mild conditions (Puterman we observe the upper bound tends to infinity the limit y - Hence, it is necessary to devise an alternate approach to study the convergence of policy gradient in the context of average reward MDPs.
1994 Bertsekas 2007). Utiizzig this relationship in equation [I]
1.1 RELATED WORK
There is wealth of literature on discounted reward MDPs. Fazel al. (2018) among the first to establish the global convergence of policy gradients, specifically within the domain of linear quadratic regulators. Bhandari & Russo (2024) established connection between the policy gradient and policy iteration objectives, determining conditions under which policy gradient algorithms converge to the globally optimal solution. Agarwal al. (2020) offer convergence bounds of Oz(1-1J))) ) for
policy gradient and O 0(71--3= for natural policy gradient, where represents the suboptimality. It is noteworthy that while their convergence bounds for policy gradient rely on the cardinality of the state and action space, the convergence bounds for natural policy gradient are independent of them. Xiao (2022b) enhance the O ( policy gradient bounds by refining the dependency on the discount
factor, yielding improved bounds of O O(ZI-Tz)) Zhang et al. 2021 prove that variance-reduced versions of stochastic policy gradient also converge to the global optimal solution. They achieve this through a gradient truncation mechanism. Mei et al. (2020) analyze global convergence of softmax-based gradient methods and prove exponential rejection of suboptimal policies.
The global convergence of policy gradient methods has been extensively studied in the context of planning for average reward Markov Decision Processes (MDPs). Even-Dar al. (2009) and Murthy & Srikant 2023) provide foundational results for natural policy gradient methods, proving their global convergence for finite state and action spaces. Extending this work, Grosof et al. (2024) analyze the more challenging case of infinite state spaces, establishing theoretical guarantees for convergence in this general setting. critical contribution of our work lies in proving that the smoothness of the average reward holds for large class of MDPs in the tabular setting. This smoothness property allows us to establish the first global convergence bounds for policy gradient methods in average reward MDPs, climinating the need for previously unverified and restrictive smoothness assumptions.
In the learning context, actor-critic and gradient-based methods have been a central focus for analyzing average reward MDPs. Konda & Tsitsiklis (1999) investigate two-time-scale actor-critic algorithms, employing linear function approximation for value functions and demonstrating asymptotic local convergence to a stationary point. Similarly, [Bhatnagar et al. (2009) analyze four gradient- crasient-based methods, including natural policy gradients, and establish asymptotic local convergence using an ODE-based framework. Addressing global convergence, BBii al. (2023) study policy gradient methods under the assumption that the average reward is smooth with respect to the policy parameters, achieving a regret bound of 1/4). Ganesh et al. (2024) consider the average reward natural actor- critic algorithm which does not rely knowledge of mixing time, and provide regret bound of
OVT. However, the results in both of these works rely on unverified smoothness assumptions, leaving
2

---

Published as a conference paper at ICLR 2025
open questions about their upplicabilitt to general MDPs. Our contributions further strengthen the understanding of when these assumptions might indeed be true.
1.2 CONTRIBUTIONS
In this subsection, we outline the key contributions of this paper.
Unlike previous work which assumes the un- derlying average cost function is smooth, prove its smoothness by introducing new analysis technique. This technique addresses the key difficulty of the lack of uniqueness of the value function in average-reward problems. We overcome this challenge by using projection technique to ensure uniqueness and leveraging the properties of the projection to prove smoothness. This removes significant assumption and strengthens the theoretical foundations of policy gradient methods in average reward MDPs.
Elimination of Smoothness Assumption:
Expression for Smooth Average Cost:
We derive an explicit expression for the average cost that is shown to be smooth in the policy æ. This contribution is critical as it provides a deeper understanding and new insights into the behaviour of average reward MDPs under policy gradient methods.
Sublinear Convergence Bounds:
Using the above smoothness property, we present finite time bounds on the optimality gap over time, showing that the iterates approach the optimal policy with an overall regret of O (log (T") In contrast, the regret bounds in Bai et al. (2023)
are atleast O Th without learning error and with tabular parametrization. In place the discount factor and the cardinality of the state and action spaces in the discounted setting, our finite-time performance bounds involves a different parameter which characterizes the complexity of the underlying MDP.
Extension to Discounted Reward MDPs: Our analysis can also be applied to the discounted reward MDP problem provide stronger results than the state of the art. particular, we show that our performance bounds for discounted MDPs can be expressed in terms of problem complexity parameter, which can be independent of the size of the state and action spaces in some problems.
Experimental Validation: We simulate the performance of policy gradient across a simple class of MDPs empirically evaluate its performance. The simulations illustrate the impact of MDP complexity on convergence rates. Unlike previous results, where the bounds depend solely the size of the state and action spaces, these simulations demonstrate how the underlying structure of the MDP can result in significantly different convergence rates, even with fixed state and action spaces. These observations further validate the theoretical bounds derived for the convergence of projected policy gradient in average reward MDPs.
PRELIMINARIES
In this section, introduce our model, address the limitations of applying the optimality gap bounds from discounted reward MDPs to the average reward scenario, present the gradient ascent update, and discuss the assumptions underlying analysis.
2.1 AVERAGE REWARD MDP FORMULATION
We consider the class of infinite horizon average reward MDPs with finite state space S and finite action space A. The environment is modeled as a probability transition kernel denoted by IP. We consider class of randomized policies IT {ir S ((A)), where policy æ maps each state to a probability vector over the action space. The transition kernel corresponding to a policy и represented by 1T S + S, where P (s'sss = EasA (()ss))Pss()s a) denotes the single step probability of moving from state to s' under policy Let r(s, a) denote the single step reward obtained by taking action E A in state E S. The single-step reward associated with a policy л at state S is defined as (*((s) EaSA T(a)s)r(s,a).
3

---

Published as a conference paper at ICLR 2025
The infinite horizon average reward objective p" associated with a policy is defined as:
Em
DN-1 r" (88)
lim
(2)
N
where the expectation is taken with respect to Pr. The average reward is independent of the initial state distribution under some mild conditions (Ross] 1983 Bertsekas 2007) and can be alternatively expressed as p" Eees d (s)r" (s), where ds the stationary measure corresponding to state under the transition kernel _Px ensuring that dm satisfies the equation d d Associated with a
policy is a relative state value function vx E gell that satisfies the following average reward Bellman equation
where is the all ones vector (Puterman 1994 Bertsekas 2007). Note that v is unique up to an additive constant. Setting E.es d' ( 0 imposes an additional constraint over v", providing a unique value function vector denoted by v/ known the basic differential reward function (Tsitsiklis & Van Roy, 1999). It can be shown that Vn can alternatively expressed as vg (s) E [2== (r"(sn) p 880- s]. Hence any element in the set {v] + cl c E IR] is
solution o" to the Bellman equation equation 3
The relative state action value function Q" SxS associated with policy is defined as:
(ss = + Σ ((d
p" V(s,
(4)
eEES
d'eA
Similar to n", Q" is also unique up equation can be expressed as an element in the set {QT (s, + :l:ce E R} where (5 a) = E, (sn) p²) 180 8, ao a). Upon averaging equation with policy æ, it follows that n" dEA (aa (" (s, a). The average reward policy gradient theorem (Sutton & Barto 2018)
additive constant. Analogously, every solution Q" of
for policies parameterized by 0 is given by:
Op
Σ d SES
(T a) 00
(s.
(5)
00
aEA
As we focus on tabular policies in this paper, our parametcrization aligns with the tabular policy, where 0 is equivalent π. The policy gradient update considered defined below.
0pm
Projn
This + 17
Vk 2 0,
(6)
8T
where Projm denotes the orthogonal projection in the Euclidean norm onto the space of randomized policies II and 17 denotes the step size of the update. In the following subsection, we recall the policy gradient result within the framework of discounted reward MDPs and address why it cannot be directly applied the average reward scenario.
2.2 RELATIONSHIP TO DISCOUNTED REWARD MDPS
Let P7. TT (1-PP=)-1p>* represent the discounted reward value function associated with policy π. under the initial distribution μ E AS and where 7 represents the discount factor (Bertsekas 2007). Consider the projected policy gradient update given below.
Op
Tk+1 = Proju
Th +
Vk 2 0.
(7)
8m
When the step size 7) satisfy the following equation:
(1 (
the iterates ma generated from projected gradient ascent equation
2-| Al
d= 1 /
256 A|
Puny - P <
(8)
k(1
7)5
4

---

Published as a conference paper at ICLR 2025
where PK,y represents the optimal value function under initial distribution μ4, and d (1 r) "p""" - represents the state occupancy measure under optimal policy x (iiao 2022b Under some mild conditions the average reward p" associated with policy and the value function Pwn (s) are related as below:
p lim [1 - (s)
99)
Note that the above relation (Bertsekas) 2007 Ross 1983) holds for all E S and all Ja E AS since the average reward is independent of the initial state distribution. Upon leveraging the relation in equation 9 and multiplying equation 8 with - () is apparent that the upper bound of equation in the limit of y + tends to infinity. This is due to (1 -1) that remains the denominator of equation 8 upon multiplying with (1 7). Therefore is necessary devise an alternative proof technique in order to analyze the global convergence of policy gradient in the context of average reward MDPs. Prior presenting the main result and its proof, state the assumption used in our analysis.
Assumption 1. For every policy π. E I1, the transition matrix IpT associated with the induced Markov chain is irreducible and aperiodic. This assumption also means that there exist constants Ce < and X E [0, 1) such that for any 1 E N and any π E II, the Markov chain corresponding to IP" is geometrically ergodic i.e,, (IP*)* - (dm)² T 11 S Ceaa.
3 MAIN RESULTS
Let p be the average reward corresponding to the policy iterates obtained through the policy gradient update equation Let p² represent the optimal average reward, that is, p² max p². There exist constants L and CpL, determined by the underlying MDP, such that when the step size < Lg. the following holds:
Theorem 1.
For all MDPs is true that,
p
p <
Vk 2 0.
(10)
p--p-0 + vk'
(1 1144
where = 332 T.
320
For simple MDPs (i.e. L << 1) we obtain exponential convergence, that is
p² - p** sc (0* p00 )
Wk 120 0
(11)
where 1 с 32 L.
Remark: It is worth noting that the above bounds correspond to a regret of (log(T)). While regret is typically a concept associated with online learning settings, we present it here to facilitate the development of learning algorithms inspired by the findings of this work. All previous results on convergence for discounted MDPs are of the form EF (Agarwal et al. 2020 Mei et al. 2022 Xiao 2022a), where a a large constant. However, since the worst sub-optmallty is 1, the bound Er p- is meaningful from the very first iteration. The maximum sub-optimality is p at k = 0, and it decreases monotonically thereafter.
becomes less meaningful for initial k. contrast, our bound
Our second result, an observation that is novel to this work, shows that simple MDPs exhibit much faster (linear) convergence rates. This explains why techniques like reward shaping. which simplify the MDP, can be highly effective.
3.1 KEY IDEAS AND PROOF OUTLINE
similar result was proved for discounted reward MDPs in Agarwal et al. 2020); An important property pivotal to the global convergence analysis of the projected policy gradient
; Xiao (202aa).
5

---

Published as a conference paper at ICLR 2025
is the smoothness of the discounted reward value function. Demonstrating the smoothness of the discounted reward value function is relatively straightforward due to the contractive properties of the discount factor. However, this poses significant challenge in the context of average reward MDPs. Here, the absence of a discount factor as a source of contraction, coupled with the lack of uniqueness in the average reward value function, complicates the task of proving the smoothness of the average reward. Therefore, the first important property we prove is the smoothness of average reward.
3.1.1 SMOOTHNESS OF AVERAGE REWARD
differentiable function f + IR is called L-smooth if it satisfies
[v](v) V ((x)] Lyy 2z|2
Vy, EC.
(12)
where C is some subset of R". Further if the function is L-smooth, it satifies the following property.
L llv x|1 ((0) f(x) (VI(z), - s) $ 2
Vy. E C,
(13)
From the above definition, it is apparent that f is L-smooth then ef is Lmmooohh for any e E R. It can be shown that the infinite horizon discounted reward M4y is 271 result in equation 9, one the smoothness of the discounted reward cannot be leveraged show the smoothness of the average reward.
(1-7)3 -mooth. Leveraging the
that the smoothness constant of pt is lim (1-7}² oo. Hence,
2:141
In this paper, we establish the smoothness of the infinite horizon average reward by first establishing the smoothness of the associated relative value function. We then leverage the average reward to to establish the smoothness of the average reward in terms of the smoothness of the relative value function. However, since the relative value function is unique up to an additive constant, we consider the projection of the value function onto the subspace orthogonal to the vector. This provides us with an unique representation of the value function whose smoothness can be evaluated.
Bellman Equation
Let & E IR x||| be the projection matrix that maps any vector to its orthogonal projection in the Euclidean norm onto the subspace perpendicular to the 1 vector. Then the following lemma holds. Lemma 1. Let be the identity matrix and be the all ones vector, both of dimension |8]. Then the orthogonal projection matrix is given by + = (1 as a solution to the following fixed point equation,
117) (1- The unique value fanction vž is obtained
1ST
= + (r + 1pT 13 1²1)
(14)
and can be alternatively represented as
2 = - Tr
(15)
Since 1a has 1 as its Perron Frobenius eigenvalue, (T PP)) is singular matrix. It can be verified that 11 = 0, hence 1 is an eigenvector of hp"r for all π with a corresponding eigenvalue of 0. It can subsequently be proven that the rest of the eigenvalues of &pp are all less than one in terms of their absolute value and hence equation 15 is well defined.
With a unique closed form for the average reward value function established, the subsequent task is to determine its smoothness constant. Given that the smoothness constant of a function f corresponds to the largest eigenvalue of its Hessian. we adopt an analytical approach similar to that presented in Agarwal et al. (200)). This involves utilizing directional derivatives and evaluating the maximum rate of change of derivatives across all directions within the policy space. It's important to note that since we are maximizing over directions expressible as differences between any two policies within the policy space, the resulting Lipschitz and smoothness constants are referred to as the restricted Lipschitz and smoothness constants, respectively. The restricted smoothness of the average reward value function stated below.
Lemma 2. For any policy n E II, there exist constants Cm, Cp, Cr, Kip BB+ which are determined by the underlying MDP, such that the value function 1g is 4 (2C3 CP CRRy i C2

---

Published as a conference paper at ICLR 2025
Since the average reward value function is Lipschitz and smooth with respect to its policy, directly utilize this property to establish the Lipschitzness and smoothness of the average reward. These results are characterized in the following lemmas.
Lemma 3. For any policy π E II, there exist constants Cmn Cps Cr, Kr E Rt which are determined by the underlying MDP, such that the average reward p" is I. Lipschitt.
<
x)) S 1 1|'
n --x)/)
|| 1l|2,
Vn, E ETI,
(16)
where LI = 2(C + C,Cmmir + 2(C Cytr + C..
The restricted Lipschitzness of the average reward is utilized to prove its restricted smoothness. Lemma 4. For any policy a E II, there exist constants C.n, Cp. Cr, Kip RR+ which are determined by the underlying MDP, such that the average reward p" is L2 L smooth.
82 p" ( (e(-m)) mi) 1 n, dT
1
| T12
VT, VT
(17)
2
where L 4(C2 + C,C,m C. + (Cp + C) Cpsx+ + Cm
Note that the restricted Lipschitz constant of the average reward is upper bounded by its general Lipschitz constant:
Op" On : - 1) +){
1pp Ox "1
max T'ETI last
MAX WERS A
(18)
By confining our analysis of the smoothness constants to the policy class, we introduce a dependency of our convergence bounds on MDP-specific constants, including Cr, Cp, Cm, Ce and k,. These constants capture the complexity of the underlying MDP and are exclusive to the analysis presented in this paper, as there appears to be no such dependency observed in the global convergence bounds of Agarwal al. (2020). A more detailed description of these constants can be found in Table T where h and 22 represent MDP HDP-independent numeric constants. These constants, which rely on the characteristics of the MDP, suggest that the projected policy gradient may achieve faster convergence in MDPs with lower complexity opposed to those with higher complexity. The range of these constants can found in Appendix A. We now proceed to analyze the convergence of projected policy gradient utilizing the smoothness of the average reward.
3.1.2 CONVERGENCE OF POLICY GRADIENT
Using the smoothness property of the average reward, it is possible to show that the improvement in the successive average reward iterates is bounded from below by the product of the smoothness constant and the difference in the policy iterates, as described in the lemma below.
Lemma Let p be the average reward corresponding the policy iterate Ty obtained from equation
Let L be as in Lemma 4 Then,
I 1T Th
Th+1 I
V.
(19)
Successively increasing iterates not sufficient guarantee finite time global convergence bounds. is therefore necessary to bound the suboptimality associated with each iterate. We do so by leveraging the performance difference lemma stated below.
Lemma 6. Let p" be the globally optimal average reward. Then for any π E II, the suboptimality of pa can be expressed as:
0" p
Σ d=' (8) Σ QT ax) (als) [
(20)
Proof. The proof can be found in Cao 1999).
In the next lemma, we upper bound the right-hand side of equation 20 in terms of the gradient of p*.
7

---

Published as a conference paper at ICLR 2025
Table 1: Constants capturing the MDP Complexity
Definition
Range
Remark
2C [S]
Cm
max (PP*)-11
See Assumption for definition of C. and
1
Lowest rate of mixing
||8" P
Cp
max s1, 'Elll -
[0, / A
Diameter of transition kernel
| -r-
C,
max nT | -
[0 AA
Diameter of reward function
max, |r 10000
(0,2)
Variance of reward function
C, 2(C2, CpR. C.
C,Cnter
+
[0, k / |
Restricted Lipschitz constant
47
Ki C 1)(C CpK + C,) + AlCm + C,C,,,
0, k2
Restricted smoothness constant
Cpp Cm are defined using operator norm w.r.t. Too norm. Precisely,
[|(p=' - po)
Cm max, max| s1 |I(1 4 - bolooo and Cp = maX s'Ell |r
||
Lemma 7, The suboptimality of any π E II satisfies:
0p"
p" pp" pm < CpL max 7'Ell
n' nT, Oπ
VI 11,
(21)
where CPL = max d' (+)
Note that OpL is constant that is proportional to the size of the state space. We do not know if the appearance of such a constant inevitable not; however, it should be noted such a constant appears in prior works on discounted reward problems as well (Agarwal et al. 2020 Xiao 2022a).
is possible further upper bound the expression in Lemma using the smoothness property the average reward.
Lemma 8. Let Thk be the policy iterates generated by equation 6 Then for all xe E it is true that,
Opmett n² -T++1) 4v |m41 -mkll,
(22)
dmpt1
Lemmas 5 and are combined to prove the result Theorem
3.2 EXTENSION TO DISCOUNTED REWARD MDPs
Existing performance bounds in the context of discounted reward MDPs require an iteration
plexity of O [SILA to achieve policies with suboptimality of (Xiao, 2022a). These bounds are independent of the hardness the underlying MDP. Our approach improves on this bound, yield- C,O,m.C (C, (CC+11)(C; Cpk, ing an O $14") iteration complexity, where I!! C Ō2 Ky,
(1->)')
Cm. + 4(C Č2 C. C,Crr) Č, [1(1 >P*)-11| It is straightforward to see that Om 5 - Hence, the iteration complexity improves O LS as the constants satisfy (1->)
H, < 2 and Cp. C, < VIAJ. Further, the approach considered this paper provides faster conver- gence rates for MDPs with low complexity, i.e., MDPs that have low values of C, or C,. The exact
8

---

Published as a conference paper at ICLR 2025
0.99
Meann reware
0.6
Mear roword
0.97
0.4
0.35
Low Variance
0.2
High Variance
Max Variance
0.93
0.0
250
1750
250
750
1250
lterations
Iterations
(a) Convergence as function of space cardi-
(b) Convergence function reward variance
nality
Figure 1: Improvement in average reward function of MDP complexity
performance bounds can be obtained from an approach similar to the one outlined in Kumar et al. (2023), where LA represents the restricted smoothness constant of the discounted return p This constant can be derived through a process analogous to the one described in this paper.
For instance, consider trivial MDP for which Cp MDP where the transition kernel independent of the action enacted. For this trivial MDP every policy is an optimal policy. The state of the art convergence guarantees (Xiao) 2022a), still requires S[ Ale iterations for close optimal policy. Whereas, the performance bounds presented in this paper predict O(SS)=1) iterations for convergence. Thus the constant L captures the hardness of the MDP. Therefore, MDPs with lower complexity, i.e., lower values of L converge faster than MDPs with higher complexity, thus improving on current complexity-independea bounds.
Hr 0 (implies C, 0). i.e.,
SIMULATIONS
Here, we present simulations corresponding two MDP complexity measures. In order to study the convergence of projected policy gradient in the context of average reward MDPs and its dependence on the underlying MDP complexity, we present simulation results corresponding to two complexity measures: the cardinality of state and action spaces, and the diameter of the reward function.
Figure ((a) considers MDPs with ((S), AA) {(3, 3), (9, 9). (81, (1)) We construct the transition kernel and the reward function in the same manner for all MDPs, which discuss in the appendix. Projected policy gradient was implemented for 2000 iterations and the overall average reward plotted function of iteration number. As expected, the convergence rate is slower when (|S). |A] l) are larger due to the fact that the reward smoothness constant larger. This reduction stems from small values of Cas, Cr, Cp. which are characteristic of MDPs with smaller state and action space cardinalities when the transition kernel and reward structures are similar. A less obvious result is that, even for MDPs with fixed cardinality of state and action spaces, the rate of convergence can be considerably different as shown in Figure [(b). For this simulation, we fix the state and action space cardinality ([S), AI) = (16, 16). We randomly generate a transition kernel, which remains constant across different single-step reward functions corresponding to varying reward variances. In particular, we consider four different reward variances no variance, low, high and maximal variance. We recall the definition of C, found in Table I We see that C, scales with reward variance. Specifically, C, is large when small changes to the policy result significant modifications to the mean reward. Therefore, slower convergence. Additional details are found in the appendix. The observed convergence trend aligns with the theoretical bounds obtained, indicating that MDPs with small values of C, tend to converge relatively faster.
anticipate that higher reward variance will lead to
Next, discuss the impact of Cp convergence of policy gradient. We consider MDPs of size 16, ie., ([S), AA] = (16, 16). We generate three different transition kernels. The first is uniform, so the actions do not change the transition probabilities, the second is deterministic (i.e., there exists

---

Published as a conference paper at ICLR 2025
Overall charge in moaan roward
0.05
0.90
0.85
0.75
Uniform
Non-unifomm
0.70
Deterministic
500
1000
1500
2003
2500
3003
Iherations
Figure 2: Convergence function of Cp
some 8' S such that P(s'ls, a) for all (s,a) E AS) and the last is non-uniform but stochastic transition kernel. We recall the definition of Cp from Table We see that Cp is larger when the transition probabilities change by a greater amount with small changes to the policy. Thus, deterministic MDPs should have higher Cp values then ones that are more stochastic. Additional details are provided in the appendix. We run the policy gradient algorithm considered in this paper for each MDP setting and plot the overall change in average reward as a function of iterations, for 3000 iterations. Figure 2 indicates that policy gradient in MDPs corresponding to small values of C, converges relatively faster than for MDPs corresponding to large values of Cp. Hence, the performance bounds obtained in Theorem 1 are in some sense. more representative of the empirical convergence trend of the policy gradient algorithm.
Note on Limitations and Future Work: be generalized to parametric class policies. This study uses the exact value of the gradient and does not account for learning errors in the analysis. Nonetheless, we highlight that this is the first comprehensive proof of global convergence for policy gradient methods in average reward MDPs. Future work will focus on incorporating learning errors into this framework.
Although we study tabular policies, this approach can
CONCLUSION
In this paper, presented the first comprehensive finite-time global convergence analysis of policy gradient for infinite horizon average reward MDPs. Key contributions include eliminating the smoothness assumption from previous work, deriving explicit expression for the smooth average cost, and proving sublinear convergence with a regret of Olog (T)). Our findings offer a more general and robust understanding of policy gradient methods in average reward MDPs, addressing long-standing challenges such as the lack of uniqueness in value functions. We also extended our analysis discounted reward MDPs, providing stronger performance bounds by incorporating complexity parameter beyond state and action space sizes. The theoretical results were further supported by simulations that highlighted how the structure of the underlying MDP influences convergence rates. These insights open avenues for refining performance bounds and exploring real-world applications in both average and discounted reward MDPs
ACKNOWLEDGEMENTS
Research conducted by Y.M. and R.S. was supported in part by NSF Grants CNS 23-12714, CCF 22-07547, CNS 21-06801, and AFOSR Grant FA9550-24-1-0002.
This research was also supported by the Israel Science Foundation (Grants No. 2199/20 and 3109/24).
REFERENCES
Yasín Abbasi-Yadkori, Peter Bartlett, Kush Bhatia, Nevena Lazic, Csaba Szepesvari, and Gellért Weisz. Politex: Regret bounds for policy iteration using expert prediction. In International
10

---

Published as a conference paper at ICLR 2025
Conference Machine Learning, pp.
PMLR, 2019.
Alekh Agarwal, Sham M. Kakade, Jason Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift, 2020.
Qinbo Bai, Washim Uddin Mondal, and Vancet Aggarwal. Regret analysis of policy gradient algorithm for infinite horizon average reward markov decision processes. arXiv preprint arXiv:2309.01922, 2023.
Jonathan Baxter and Peter L Bartlett. Direct gradient-based reinforcement learning. In 2000 JEEE International Symposium on Circuits and Systems (ISCAS), volume 3, pp. 271-274. IEEE, 2000.
Amir Beck. Introduction to nonlinear optimization: Theory, algorithms, and applications with MATLAB. SIAM, 2014.
Dimitri P. Bertsekas. Dynamic Programming and Optimal Control, Vol. II. Athena Scientific, 3rd edition, 2007. ISBN 1886529302.
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. Opera- tions Research, 2024.
Shalabh Bhatnagar, Richard Sutton, Mohammad Ghavamzadeh, and Mark Lee. Natural actor-critic algorithms. Automatica, 45(11):2471-2482 2009.
Tomasz Bielecki, Daniel Hernandez- Haapnndzz--rrnndzzz.r and Stanley R Pliska. Value iteration for controlled markov chains with risk sensitive cost criterion. In Proceedings of the 38th IEEE Conference on Decision and Control (Cat. No. 99CH36304), volume I, pp. 126-130. IEEE, 1999.
Xi-Ren Cao. Single sample path-based optimization of markov chains. Journal of Optimization Theory and Applications, 100:527-548, 1999. doi: 10.1023/A:102223442444.
Eyal Even-Dar, Sham M Kakade, and Yishay Mansour. Online markov decision processes. Mathe- matics of Operations Research, 34(3):726-776) 2009.
Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. In International conference on machine learning, pp. 1467-1476. PMLR, 2018
Swetha Ganesh, Washim Uddin Mondal, and Vaneet Aggarwal. Order-optimal global convergence for average reward reinforcement learning via actor-critic approach. arXiv preprint arXiv:2407.1888 18878 2024.
Ganesh Ghalme, Vineet Nair, Vishakha Patil, and Yilun Zhou. Long-term resource allocation faimesss in average markov decision process (amdp) environment. arXiv preprint arXiv:2102.077 000000000712, 2021.
Abhijit Gosavi. A reinforcement learning algorithm based on policy iteration for average reward: Empirical results with yield management and convergence analysis. Machine Learning, 55:5-29, 2004.
Julien Grand-Clémest and Marek Petrik. Reducing blackwell and average optimality to discounted mdps via the blackwell discount factor. Advances in Neural Information Processing Systems, 36, 2024.
Isaac Grosof, Siva Theja Maguluri, and R Srikant. Convergence for natural policy gradient on infinite-state average-reward markov decision processes. arXiv preprint arXiv:2402.05274 2024.
Emmeran Johnson, Ciara Pike-Burke, and Patrick Rebeschini. Optimal convergence rate for exact policy mirror descent in discounted markov decision processes, 2023. URL https://axxxv
org erg/abs/ 2302. 11381
Sajad Khodadadian, Prakirt Raj Jhunjhunwala, Sushil Mahavir Varma, and Siva Theja Maguluri. On the linear convergence of natural policy gradient algorithm. In 2027 60th IEEE Conference on Decision and Control (CDC), pp. 3794-3799. IEEE, 2021.
11

---

Published as a conference paper at ICLR 2025
Vijay R. Konda and John N. Tsitsiklis. Actor-critic algorithms. Neural Information Processing Systems, 1999. URL
Navdeep Kumar, Inura Usmanova, Kfir Yehuda Levy, and Shie Mannor. Towards faster global convergence of robust policy gradient methods. In Sixteenth European Workshop on Reinforcement Learning, 2023. URL httpss://ppereeiiiiiieeee
net forum? w dww.:dddwwwwwBx
Navdeep Kumar, Priyank Agrawal, Giorgia Ramponi, Kfir Yehuda Levy, and Shie Mannor. Improved sample complexity for global convergence of actor-critic algorithms, 2024. URL https://
wxxiv.org/abae 2410 08868
Jiacai Liu, Wenye Li, and Ke Wei. Elementary analysis of policy gradient methods, 2024. URL
httts::/arxiv.cr org/ http://wwwww..rr/////////./00 a05/2404. 03372
Sridhar Mahadevan. Average reward reinforcement learning: Foundations, algorithms, and empirical results. Machine learning, 22(1):159-115, 1996.
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In International conference on machine learning, pp- 6820-6829. PMLR, 2020.
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods, 2022.
Yashaswini Murthy and R Srikant. On the convergence of natural policy gradient and mirror descent- like policy methods for average-reward mdps. In 2023 62nd IEEE Conference on Decision and Control (CDC), pp. 1979-1984 IEEE, 2023.
Yashaswini Murthy, Mehrdad Moharrami, and R Srikant. Performance bounds for policy-based average reward reinforcement learning algorithms. Advances in Neural Information Processing Systems, 36, 2024.
Jonathan Patrick and Mehmet A Begen. Markov decision processes and its applications in healthcare. Handbook of healthcare delivery systems. CRC, Boca Raton, 2011.
Martin L. Puterman. Markov decision processes: Discrete stochastic dynamic programming. In Wiley
Series Probability and Statistics, 1994.
Sheldon M. Ross. Introduction to Stochastic Dynamic Programming: Probability and Mathematical.
Academic Press, Inc., USA, 1983. ISBN 0125984200.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897. PMLR, 2015.
Richard S. Sutton and Andrew G. Barto. Reinforccement Learninn An Introduction. The MIT Press, second edition, 2018 URL http:ppp//nncooptteeeeeeessss/sa www.ttteee--oeeeeeeeeeeee 2nd html
Prasad Tadepalli and DoKyeong Ok. Model-based average reward reinforcement learning. Artificial intelligence, (00(1-2):177-2)))) 1998.
John N Tsitsiklis and Benjamin Van Roy. Average cost temporal-difference learning. Automatica, 35 (11):1799-1808. 1999.
Lin Xiao. On the convergence rates of policy gradient methods, 2022a. URL htttttss///axii arq/abs/2an 0ttp/2201.0744.
Lin Xiao. On the convergence rates of policy gradient methods. Journal of Machine Learning Research, 23(282):1-36, 2022b.
Junyu Zhang, Chengzhuo Ni, Csaba Szepesvari. Mengdi Wang, et al. On the convergence and sample efficiency of variance-reduced policy gradient method. Advances in Neural Information Processing Systems, 34:2228-2248 2021.
12

---

Published as a conference paper at ICLR 2025
A
SMOOTHNESS OF AVERAGE REWARD
A.1 PROOF OF LEMMA 1
Consider the subspace orthogonal E the all ones vector 1 RR| defined below:
E = span {0 R 0 = 0.}
(23)
The orthogonal projection Up of a vector v in the Euclidean norm onto the subspace E is defined as:
Vs
arg min
||v- ull2
(24)
ueB
It can be checked that the closed form expression for os is given by:
11 [
UΦ
v
(25)
where / E IR |SS|S|S is the identity matrix.
Consider the projection of the vector nd + pd - p= onto E for any policy π E II. The above projection is identical to the projection of nd + yp onto E, since p² 1 lies in the nullspace of t.
1
D(r p= 1 + 1) = (r" p² + v) (1, p=1 +
(26)
S
(r" 1 (1, p. + pT
(27)
- (rT 1)
+ 1p v - (4, PT
(28)
8
[
1
1
(r" 1)
1P
(1 T 1PT v)
(29)
[
S
11T
11
=(1
)r*
(I
)P=
(30)
S
|
=$ 1r"
PT w).
(31)
Consider the average reward Bellman equation corresponding to policy n E
p01 0'1+ + = - PT
(32)
Imposing an additional constraint xx T 1 = 0 yields a unique average reward value function denoted by eg. Moreover, it is true that,
D + 4p 1 x + 6P"
(33)
Duy -b + + TTT o.
(34)
2 -b + P wi
(35)
:n" nx Thus the projected value function with an where (a) is true because ".' T = 0
unique representation is given by:
I 4p" Tr
(36)
An alternate expression for 2h where D E [|S)x|S|| is diagonal matrix whose entries correspond to the stationary measure over the states associated with policy æ. See Tsitsiklis & Van Roy (1999) for more details.
and the existence of the inverse is proven in Subsection A.2 Lemma 12
the projected value function is given by: v (1 + 11 D
A.2 PROOF THAT EIGENVALUES OF (T hP") ARE NON-ZERO
In this subsection, we introduce the lemmas required to establish the proof of the eigenvalues of (T 11 pa being nonzero. We use the following notation:
RR represents the all ones vector
[ST
and I R is the identity matrix.
13

---

Published as a conference paper at ICLR 2025
Lemma 9. Let A E R be stochastic matrix. It is true that
(
11
A
(I-
[--
11 T
A
(37)
n
Proof. For any l E N, consider,
1 A (1
11
11
T
11
11
=
A
AR
A
A
(38)
11
11
11
11T
A
A
A
A
A
A
(39)
11T
11T
11
11
8
K+1
A
A+
A,
(40)
T1
Y1
T1
Y
11
11
11
K41
A k+1
A
A,
(41)
11
A
A+1
A
(42)
n
11
=
A 1++1
(43)
where (a) true because A 1 and (b) follows from the fact that 1 induction it thus follows that,
1. From mathematical
11
A k
1((1-
11 n
=
AR
V.EN.
(44)
72
Lemma 10. For any irreducible and aperiodic stochastic matrix A E Ru it is true that
((T-1)
11
lim R=+00
A =0
(45)
12
Proof. From Lemma 9 we have,
(1-
- -1-#
A b
A
V
(46)
Since A is irreducible and aperiodic, the following limit converges to the stationary distribution d E R7 associated with A.
lim A 1d
(47)
400
Consider the following,
((T-1) 11
A)
11
lim 80000
lim
I
(48)
11
lim A
(49)
k-+00
11
ldT
(from Equation equation 47
(50)
n
11
11
dd
(51)
n
1dd
1d
(52)
=0.
(53)
where (a) is true because
1.
1
14

---

Published as a conference paper at ICLR 2025
Lemma 11. Let A R be matrix such that limg A = 0. Then (I - A)-
E k= A&
Proof. For any K E N, consider the following,
a1
- A)
A#
1 AK+1,
(54)
k=
-I- A)
lim
lim K-000
(T- 1K+1) (
(55)
K-000
k=0
where (a) follows from the fact that limg-+oo A ===00 0. Hence the inverse of (T A) can be expressed as (I A)- = Lk=o A
Lemma 12. Let Rxx= be an irreducible and aperiodic stochastic matrix. Then the matrix
[ [ 11 A) is invertible and its inverse is given by:
11 (1-(1-
11
A
A
(56)
71
Proof. Let A be cigenvalues of
11
A.
Then X represents the eigenvalues of
11 A) &
But from Lemma
10 we know that
(1-
11
lim k+0
A
(57)
Since eigenvalues are continuous functions of their corresponding matrices and all eigenvalues of zero matrix are zero, we thus have,
lim 10000
X = O
Vi E (1.....n]
(58)
(1-((1- 11
A))
Equation 58 thus implies that [A,- < 1, E (1....,n) Hence the matrix
has all non zero eigenvalues and is thus invertible. From Lemma
II
we know that
AI-A) -)-1= Σ A
(59)
when limg-so A 0. Since, lime-+00 following result,
((1-22) 22
A
0 from Lemma 10 we have the
I (1-(1- (1-
T1
-1
8
11
A
Σ
A
(60)
n
m
From definition we have Φ = 11 and is well defined æ E
Hence the inverse (1 - +11)~1
Eee k= T (PT)**
exists
A.3 SMOOTHNESS OF THE AVERAGE REWARD VALUE FUNCTION
In order to prove the smoothness of the average reward value function and the infinite horizon average reward, we consider analysis inspired by Agarwal et al. (2020). where instead of computing the maximum eigenvalue of the associated Hessian matrices, we consider the maximum value of the directional derivative across all directions within the policy class.
15

---

Published as a conference paper at ICLR 2025
Let TT E II be any policies within the policy class. Then define Na convex combination of policies x and x'. That is
Ta : (1 - a)T + aur''
(61)
π. - a(=²²= - x)
(62)
π + auu
(63)
where u = T²' - n.
Since Ta is linear in a, it is true that
Va d(k ac)
u,
and
V Ta
O.
(64)
da
This thus implies,
Vo 1l
||u||2 I || - πT S 28, and a = 0,
(65)
Thus, Ta is both tull2-Lipsccitz and O-smooth with respect a, for all u that can be represented as the difference of any two policies.
From the definition of IP", we have
aa (s'1s) Σ (s((ss))(s((s.o)
(66)
aEA
Σ [T(als) [ou(a)))(
(67)
aEd
0.
(s'(s)
Σ u(als))P(((ssa))
(68)
da
aEA
That is,
V.P pu
consequently
Vpp.. O.
(69)
From the definition rM we have
(s) Σ Ta(als)r(s;a)
(70)
aEA
Σ
[m(ass + (((ass))((ssa))
(71)
aEA
aa (s)
u(als)r(s.a).
(72)
da
aEA
That
Var
consequently
= 0.
(73)
Hence the policy To, the associated reward Th and the transition kernel pas are all Lipschitz and smooth with respect to a.
Lemma 13. Let A(a) E Rux* be matrix such that (1 A(a)(a)) is invertible for all a E [].
Define M = (I A(ai)) Then it is true that,
Ma) (a) 0A(a) M(a)) + M(a)
82 A(a()) M(a) + M(a)
0A(a) dM
(74)
da2
do: Oa
da²
da da
Proof.
M(a) (1 A(a)) =
(75)
(a(a)
(I - A(a)))) - (a) dA(a) -0
(76)
da
da
(a)
M(a) dA(a) M(a)
(77)
da
da M()))
8 M())
à (M(a) 0A(a)
(78)
da
da
@M(a) dA(a) M(a) + M(a) da?
A(a))
0A(a) @M
M(a) M(a)
da da
do
Oa
(79)
16

---

Published as a conference paper at ICLR 2025
Consider the following definition utilized in the proofs of the upcoming lemmas.
M [I 6P=-1-1
(80)
Lemma 14. Recall the definition of the projected average reward value function vz in Equation equa- Value function vz is 2C,, Cptr + 2Cm C.-Csihhpst in that is
tion 36
Ou
n
2 ( CpKr CTCr) || T/22 Vn, 11.
(81)
Proof.
M Tp
(82)
TM
da M0 3r
(83)
da
da
da
P4PTM = Tr ad 2r MMa
(from Lemmal 13
(84)
da -==00F M Th M TM "r
da
(from equation 69 and equation 73
(85)
=
| "o M 1l
(86)
da
|M TM 11 |1 |o PM
1o | 1lo0 +
1 1ox ||
100
(87)
2C, Cptir + Cr.
(88)
The constants Cm, Cp, Cr and Hi are characterized in Table with their respective bounds in Lemma
g
We can now build on the previous lemma to prove the smoothness of the average reward value function.
Lemma 15. The value function og 8 C2 Ky + Che
in IT. That is,
82 (
(TT' - T) $8 CpC,), || - 1 El, S (89)
n
Proof. From Lemma 14 is true that
a
"a
da
g
θ MM to Ta
da
da
0M
ppu AM
upu M $ T da
Tp Md To + R0
To + Ro
da
da
0M
+ da
4p
=M* Fm 0
0DpT.
no dr
Oa
da
ODP=.
TT Ta
Ta.
M To Tr
(from Lemma 13
da
da
=M=
,/ + TT T To + Th Tp" Th nh
T M 2
(from equation 69 and equation 73
17

---

Published as a conference paper at ICLR 2025
Considering the Loe norm,
8 x
= |t
0a?
<
s 8(C C Kr + CpC,).
Hence, obtain,
8 (s)
(T' -T)
+ || = Wl, (90)
C
T
A.4 LIPSCHITZNESS OF THE INFINITE HORIZON AVERAGE REWARD P"
The Lipschitzness and smoothness of the projected value function u is leveraged through the average reward Bellman equation to prove the Lipschitzness and smoothness of the infinite horizon average reward.
Lemma 16. Recall the average reward Bellman Equation corresponding to a policy π and projected value function vz in Equation equation 32 The average reward p" is L -ipschhit
Op dm
xx)
< L T112,
VT, E ElI,
(91)
where I = 2(C + CpCmiy + 2(C + Cr)
Proof. From Equation equation 32
=1=r== P 1gg
(92)
Taking derivative with respect to a.
0p"0
To
0
Or To
1
+
FFa
(93)
0a
da
dc
da
da
(94)
" + " + (p
{)M MM + ")
(from Lemma
14
(95)
th + 4 M + (p*
T)
TT. M Th + "r
(96)
(from equation and equation 69
Considering the Loe norm of the above expression,
3p da
"r " + (F I) "PM" + "T
(98)
|| "" + ||1 11| (
11
||
TM Dy
(loo),
(99)
2|/|r" + 21 M" |1x0 + | 7 - boo);
(100)
2C, + +C, + 2(20 Cpk, + Cx).
(101)
18

---

Published as a conference paper at ICLR 2025
A.5 SMOOTHNESS THE INFINITE HORIZON AVERAGE REWARD P
Lemma 17. The average reward p" is Li -smooth.
(
T,
8 p" ( n)) S | 21 Om
LE
VT, ETT,
(102)
where 1. 4(C2
C2 Ky + CpCm Cr + (Cp + 1) Cpti + CmC,)) + 4 C C. CpC.))
Proof. From Lemma 16
we have
0p"
1 4r D1" M + (PF
I)(M** "F"" "M + M
(103)
da
Taking the derivative again, and repeatedly invoking Equations equation 69 equation 73 and Lemma 13 it follows that,
p²p=a
a
1 1
( ((P I) M"a M**
da?
da
da
(104)
-pP" p " fr " (P" (M* """"""""""""""""""""M"""""""""" + = x)
(105)
+ eall) - l] ( M -. 6 MP' + M TP" 6P 27
(106)
+ M hp - + - 1P M (r"
(107)
mad" M um M n. क. pp - "h M
R Φr
(108)
+ 2(P
M (109)
Considering the Loo norm of the above expression,
8ppTu da²
<100P" nd 41 M Ad 20 1loc + || M" + (M "" Tp
+ 5 1c + (P 1 I) M "F -P
+ M 4P - 4r lloo
< <40 + C, + +Cp + () Cpri
C2 + C C,C,)).
The smoothness and Lipschitz constant analysis of both the average reward value functions and the infinite horizon average reward are constrained all directions u, such that every u π x' can be expressed as a difference of any two policies T' E II. Hence the smoothness and Lipschitz constants derived are restricted the directions that can expressed as this difference and hence are referred to as restricted pnootthnes/L.iischhtzeess
Remark:
A.6 TABLE OF CONSTANTS CAPTURING MDP COMPLEXITY
We restate the table of constants and their description here for the sake of convenience.
19

---

Published as a conference paper at ICLR 2025
Table 2: Constants capturing the MDP Complexity
Definition
Range
Remark
Cm
max
2C, [S]
Lowest rate of mixing
1-X
|| PP
Cp
maXn,a'E11
<
[0, VA
Diameter of transition kemnll
-r-'-r" 1000
C,
max
[0, V
Diameter of reward function
max hr 1000
[0,
Variance of reward function
4
+ C. + + 2(C C
[0 ki ACA]
Restricted Lipschitz constant
Restricted smoothness constant
C, + (0 Og + C,C,,,
Lemma 18. The constants Cp. Cr, Cms in Table and other operator norms are bounded as
below:
1. | == max | ~ @uull0 S 2.
2. |PT]| max|| <1 PTulooo S maxpoll
3. mmaxa tr 10 2
4. Cm < 2C.5 T-X
5. Cp = max
wila mell max F/lo Si P I VA.
6. C, max
R S VA.
Proof.
1. Consider the projection matrix 4
|
max
/
pr 1oc
max
(110)
S1
Eees v(s)
max #ES
m(())
(111)
S
Eves v(s) S
< max |u(s)| + #ES
(112)
< 2||u||oo = 2
(113)
2. The operator norm of 1PTt is bounded as below:
max || olloo
||oooloc
(114)
b $1
max ||viloo
(115)
|| billo
< 1.
(116)
Equality is attained by the vector 1.
20

---

Published as a conference paper at ICLR 2025
3. is bounded below:
K, max 17 100
(117)
Eess T
max sell
(118)
[|]
Eses r (8)
(8)
max
|r 11 +
1
(119)
[
2
(120)
Kr, in some sense, captures the variance of the single step reward function across the class of policies. Greater the variation of the across different actions, greater the value of Ky,
4. Cm is the maximum of the operator norm of the matrix (I +FP)" across all policies
π E II. It determined as follows:
(1
(OPT
Σ + (PT)*
(from Lemma 12
(121)
k=
k=0
D (PTT) k - 1 (dm) ))
(as &1 (d*)² = 0)
(122)
k=
Let v E TRIS| such that ||0| S 1. Then,
|I(I - 4P" -1 00 100 I
)
| ((P))) - (d') (d"))))) ")lloo
(123)
kmm
| ((P=)) (dr) (dr)T)ulls> Tuull
(124)
| [S]] (dd) (10 (dr))))) 11
(125)
2/8/CeA*||ollee
(126)
k=0
2C. [S] 1 X
(127)
where dl represents the stationary measure associated with the transition kernel PT, (a) follows from the fact that the projection matrix & projects vectors onto subspace orthogonal to the subspace spanned by the all ones vector 1l and (b) is a consequence the irrducibiliiyy and aperiodicity assumption of the Markov chain induced under all policies. More precisely, for any irreducible and aperiodic stochastic matrix A, it is true that:
1An- - 1100 S C.X".
(128)
for some constants À E [0, 1), C. co, where d is stationary distribution of A. À is the coefficient of mixing and captures the rate of geometric mixing of the Markov Chain. Hence, higher the value of X, lower the rate of mixing.
21

---

Published as a conference paper at ICLR 2025
5. Cp represents the diameter of the transition kernel function of the policy class and can be bound as below.
Cp
max
max 51
|P
(129)
N
max m',nE]]] nll
(130)
|| π 7//2
((P" v)) (P)))(s))
max n',eell, vlloo 11 #ES
max
|| 1 12
(131)
((P=' (s) (P*&))
(since || - =sll2 S 1| - ==122)
max n',eEll, 51 SES
max
| T
(132)
TPx (TT,) TIP
max
max
(where P,(a, = P(5''s, (a(a) = ((. a)).
n'l = SES
||-/ - T Tzll2
(133)
ITT, nt T P.ul
max
max
(134)
'1,0Ell. vil 51 $E8
|// TTg l12
||
T [1.
<
a1 villo S1 SES
max
max
1| TT 2/2
(from Holder's inequality)
(135)
|TT n
max max rell #ES
(136)
AA
(137)
6. C, represents the diameter of the single step reward function as a function of the policy class and can be bound as below.
C₂
max
30
(138)
EE
H' mEll
max
||
(139)
7 (s) r (s)
n' mllmell SES
max max
|| . 12
(140)
I (s) - r (s)
<. max max x' "ell sES
(as ||T Talle S || π 1112),
(141)
||' T
(mT)) T r. (mx) ra
maxx max
(where (.(a)er.(a)-a = r(5, (a(a) = <(s a)),
n² n',mEll SES
|| n 1|2
(142)
( TT) r
C, max max x' ell sES
(143)
||' xx 12
Tr' n.
|rr 10
< max max n'm sES
(from Holder's inequality)
(144)
|T/ TT 112
mT' TT
max max
(145)
n' nell sES
|T' T
A
(146)
Since the directional derivatives considered are all within the policy class, the analysis gives rise to constants such as Cр and C,, which are functions of the underlying policy class. These constants capture the MDP complexity by the virtue of their definition and are an artifact of this proof technique.
22

---

Published as a conference paper at ICLR 2025
B CONVERGENCE OF AVERAGE REWARD PROJECTED POLICY GRADIENT
Lemma 19. For any convex set C IR, any point a E X, and any update direction E RR, let b Proj x + u)) be the projection of onto X. It is true that
1. {u, - a} 2 bbb - al12.
2. (c b, u (6 - a)) 00 0.
VCE
Proof. The formal proof can be found in Beck (2014).
However, the proof follows trivially from the geometrical representation of projection (see Figure
3 Kumar al. (2023),, and the fact that the hyperplane separates convex from point in the
set.
D + 4
u
L
Figure 3: Convex Projection
Intuitively, the proof of the lemma can be interpreted as below.
1. Since the angle between vectors (a and ((a u) is greater than 90 degrees, is
true that (a b, (a + u) - b) s 0, which then directly implies ||b alli S (u, b - a).
2. The angle between vectors (c b) and ((a + u) b) is greater than 90 degrees Ve E N. therefore (c b, (b a)) 0.
B.1 PROOF OF LEMMA 5
Lemma 20. The average reward iterates pT* generated from projected policy gradient satisfy the following,
L ITl
T
Th
Tx+1
Vk 0.
2
where T. is the restricted smoothness constant associated with averuge reward p"
Proof. From the restricted smoothness of the average cost, we have
dp"
I
nh+s 2 kh +
dr
Tk++1
Th
2
[ - TTl1?
dp
L
pTH
-
LJ dm
Tk+1
Thk
|
L
Th
+ 1
TT
-TTll'
[T
TR. 11
2
23

---

Published as a conference paper at ICLR 2025
The last inequality follows from the projected gradient ascent policy update rule and item 1 of Lemma 19, Note that the proof only relies on the convexity of the projection set and the smoothness of the objective function.
B.2
PROOF OF LEMMA 7
Lemma 21. The suboptimality of policy x can be bounded from above as:
3pp
p- p" S CrL
max T'Ell
-'-T,,
nt
Vx II,
(147)
OT
ar (4) and p" is the optimal average reward. where CrL maxx,s (5(z)
Proof. Average Reward Performance Difference Lemma states that
d'
[(a)))
(148)
#ES
< m18x
Σ d" (s. T[als)]
(149)
SES
d"d (s)
max (s T(ass)
(150)
d (8)
868
d (8)
d
Q (s, a)) m(ass)
(151)
d= (s)
20, 0 when n3 m.)
d" (s)
max (s)
d s max (* (5, [(ass)
(152)
SES
PCr max
ds) (8, (f ((ls))
(153)
BES
dp"
CpL max
T)
(154)
dm
where (a) follows from the average reward policy gradient theorem.
B.3 PROOF OF LEMMA 8
Lemma 22, Let Th+1 represent the policy iterates obtained through projected policy gradient. For any policy x' II, is true that,
0
x' - -mat1) $
///5S/11 | Tk+1 - Txl12,
(155)
Proof. For all y E C. we have:
10pm 1 nt' Tk+1
0p
Tpm
0p
+
T' -T++1
(156)
θTK+1
0Ts+1
0Tk
0p
18pt n Tk+1
n Tk+1
(157)
0TK+1
θTk
ÔTK
Tp
1p
|| Tktill
OT n Tk+1
(158)
0TK+1
18pt m Tk++1
|
Tx Txlll
Tktill
(159)
24

---

Published as a conference paper at ICLR 2025
where (a) uses smoothness of average reward. Thus, may continue the chain of inequalities
0p
equalion
159
12 [
TE+Il +
L2 (T++1 TT), nt' -T++1 L2 (T++1 Tk, n/' TT++1
OTk
0pm Lig (TR+1 -Tk), TR++
s 2L T =MlllT Tktill || +
OtT
1 8pTH
s 222 TT41 - Fulll= T + L2
(Th+1 Tk), a/' Th++1
L OTk
50.
(From item 2 of Lemma 19
- 21.2 Tk+1 +x|l| x+i
- 212
11 Tk+1 nx. dIlm
The diameter of the policy class IT, can be upper bounded as
diam max x,
IT'S T2l12
< max
48.
(160)
This yields the result.
Lemma 23. The scaled sub-optimality aş == p² - Ps follows the recursion
ca + ax+1 as S 0
(161)
where c 32 Oz
Proof. From Lemma 21 we know that,
0p
1 CCLL Mk+1: 0T&+1
Va' E II,
(162)
From Lemma 22
know that,
0p
- Th+t ) $ 4V/1S || Txll2-
(163)
From Lemma 20
know that,
2 (p -
FK-1 Tk m2ll22 S
Ak 2 0.
(164)
L
Combining the above equations yields,
P p Th s 32C?
2r,111 L 10th+i--FF)
(165)
This thus yields,
(p" p
+ 1p- pm - (p" -pmc) 50.
-
(166)
3 pz S
more detailed interpretation of this Lemma can be found in Kumar et al. 2023
B.4 RECURSION BOUND
In this subsection, consider the sequence defined
02+1 2 oz.
where p 2 0 and 0 < oo < 1. Let f be linear interpolation of the sequence {ax (ax0 formally defined as
f(x) = (1 a)ax + cast1.
where k = |x] and a [xx].
Let g()) = ao and
dg(x) -ggx)? and = g (ax)-
dr
Observe that 9 is strietly decreasing function.
25

---

Published as a conference paper at ICLR 2025
Proposition 1. Th 2 k then
g(0) 2 [(x),
Vo E [k, + 1|.
Proof. We have f(k) = g(Tx) as and for E (0,
dg( + a))
- + aa), (by definition)
(167)
dr
z g(Tx)
(g is decreasing function)
(168)
-(k)?
(as f(k) = g(Tx))
(169)
= -ak
(by definition of f)
(170)
at+1 ak!
(by definition of ax+1)
(171)
df (k + a)
(by definition of f).
(172)
dr
Above together with continuity of f and g. for all a E [0,1]] 1], we have
f(k + a) S g(T + aa, g(k k + a),
(173)
(as 7 2 k and g is decreasing function).
(174)
Hence claim proved. Proposition 2. For all l 0, we have
Tk 2 k:
Proof. Note that To by definition g(0) ag. Now let Th 2 k. then from Proposition
we have
g(x) 2 f(x),
Vz E kk, +1]
(175)
g(k + 1) 2 f(k 1)
(176)
0*+1
(177)
k+ 2 h: 1,
(as is decreasing function).
(178)
Hence, by induction the claim is established.
Lemma 24. |Recursion Upper Bound] For p 2 2, and 0 < ao S 1, sequence {au] satisfying the recursion aę- ax+1 2 ar. follows
ak S
Wk 1.
+
Proof. From Proposition 2. we get 2 k. Combining it with Proposition we get
g(z) 2 f(x),
Vr 2 0.
Now, we solve the o.d.e. to get
(g(
g(x))
(179)
dr
x=
dg(w)
da
(180)
x==
m0
g2 (x)
k g(k)
(181)
(())
9
((k)
(182)
+ (()a
f(k) <
ao
(as f(x) s g(x))
(183)
agk
ag
(184)
+ k
This proves the claim.
26

---

Published as a conference paper at ICLR 2025
Lemma 25. af ax+1 2 caf then
0k S 1
+
ck
0g
Proof. We have
ag 0k+1
2 cO 2
(185)
Cok 00
2 (cax)
(186)
1
c0. S
(from Lemma 24
(187)
1
+
k
000
(188)
ck
This subsection (proving the recursion upper bound) inspired by a technique from Kumar al. (2024). However, while their result is similar, it is not applicable to our case. Their result assumes that e is upper bounded by a constant, which does not hold our setting. In our case, the smoothness constant (or hardness coefficient) can approach zero, causing the constant to diverge to infinity. Our result more general, and the proof technique we use is distinct.
Lemma 26. Given ak+1 2 co 1 we have
ak <
1
+
ck
0g
where v = c(1 + ) - and 32C S
Proof. We have
ca + ax+1 - 03 S 0
a1+1 5 -1 + 11 + 4eas
2c
-1+ + f'( + (b) (4cax)²
(where f(x) v1+ x,b [0, 4cax)
2c
2cax - -2c2 + b)
(1 + b) 3
(putting
- {a)
2c
2cax
- -2c² 2c²az(1 + (cca))
(as b < 4ca and -(1 + y) # is a increasing function
2c
ca
ag.
(basic algebra)
(1 + 4cax))
2
(as a < 1 and v v:= c(1 + 4))
ag
We get the desired result from Lemma 25
Lemma 27. If S < 1 that is MDP very easy (i.e. L << 1) then the policy
gradient converges exponentially fast, that is
ag <
a 24
27

---

Published as a conference paper at ICLR 2025
Proof. From the above discussion, we have
cak+1 S ak
-k+1
(189)
ak:
(as ax+1 2 0 by definition)
(190)
ak
as+t
S
(191)
c
1
d0
gk+2
(192)
B.5 PROOF OF THEOREM 1
We restate the theorem for the sake of convenience.
Theorem 2. Let pa be the average reward corresponding to the policy iterates obtained through the policy gradient update equation 6 Let p² represent the optimal average reward, that is, p" max p². There exist constants Li and Cpt. which are determined by the underlying MDP such that:
For all MDPs it is true that,
1
P
Th
Wk 0.
(193)
pp0 + vk'
where (3203) USiLy (1+4
For simple MDPs (i.e. Li << 1) we obtain exponential convergence, that is
p² -ー pm sc p0 v4z0 20 0
(194)
where = 32 < 1.
Proof. Using Gradient Domination Lemma and Sufficient Increase Lemma shown in Lemma 23 we get the following recursion
a&++ ca 1
(195)
where dx = J - T and c= 32C py, LT is a small constant. Then we get the desired result by solving the above recursion in Lemma 26 and Lemma 27 for complex MDPs and simple MDPs respectively.
C SIMULATION DETAILS
C.I CONVERGENCE WITH DIFFERENT ACTION AND STATE SPACE SIZE
In the first experiment, we compare the convergence of PG for tabular MDP with (S. {(3, 3), (9. 9), (81, 81)}. We set the reward kernel to be with maximal variance as described above. For the transition kernel, we use the following matrix:
1 3
1 [Ixx++
p(-1s.))
so P(ils, i) 1+ the actions 1 and the rest 11, for every state
2 and P(i) s.j) = Is for i + j. For the reward kernel we set the rewards of half
28

---

Published as a conference paper at ICLR 2025
C.2 CONVERGENCE WITH DIFFERENT REWARD FUNCTIONS
In the second experiment, we compare the convergence of PG for a tabular MDP with S 16 and 16. We set r(s, a) for any and except for one state which denote by 8n- We the same randomly generated transition kernel and use the following procedure to generate the reward function:
No variance: We assign each (so, a) pair a reward of 1.
Low variance: We assign 8 of the actions for so reward of 1, and otherwise.
High variance: We assign 1 of the actions for Su a reward -1, and otherwise.
4
Max variance: We assign of the actions for reward of 11, and 1 otherwise.
C.3 CONVERGENCE WITH DIFFERENT TRANSITION KERNELS
In the third experiment, we compare the convergence of PG for a tabular MDP with 16 and A = 16. We create three different MDPs with the same (S, A) values and the same reward function that is generated according to the process described above for high variance reward function. We then generate three different transition kernels:
Uniform: We assign for all values of 8, ú, P(8
8, a) = 5
Non-uniform: We assign P(i 8, = 25 + and P(i 8, 25 for + j.
Deterministic: We look P(- s. as an S matrix, and assign it random permutation of the identity matrix. In this way the result MDP is deterministic but not trivial (so every state leads a different one).
D ADDITIONAL DISCUSSION AND FUTURE WORK
Extension to Discounted Reward Setting. In the discounted reward setting, the return p" and the value function oF is defined as
p² = (1=(1=-"*)
-1- (1-
(196)
where 7 E [0, 1) is the discount factor Sutton & Barto 2018). The return p is proven to be (I-7)s- smooth (Agarwal al. (022)). Note that an MDP-agnostie bound. We can achieve MDP restance-dependeed bound with a very minor change in the smoothness analysis of the average-reward
Let us define,
n. == (1 - PP=
(197)
Observe that Lemma 13 holds for A(a) = y pma which yields us 8 M(a) d where ((a is shorthand for M
+ aM(a) A((a), M(a) + M(a) AAa()) da
OA(a) @M(a)
(198)
da da
da
da
Table 3: Constants capturing the MDP Complexity for Discounted reward
Definition
Range
Remark
Cm
max+enII(T -ypa)-1)
Cp
? max x'El ell
||
pprl |
[0, (VA)
Diameter of transition kernel
||+ -
C,
max,,
|| 1
0, A Diameter reward function
Ky
max; |r ||00
[0, Variance of reward function
29

---

Published as a conference paper at ICLR 2025
Lemma 28. The value function og is 8 C2 + C CpCr.) in II. That is.
(5)
n² n,
dx (T' m)) 8 C2 + CpCr) || =11
E (199)
Proof.
Py =Maagp"M " + M " M"
th Ma M " MMaaP" M (from equation 69 and equation 73p.
da
Considering the Loe norm.
= 7P =T 1o
0a²
< MM + || r"
< 88(C C,C,T)
Hence, we obtain,
8 n' - nτ dπ
(T' - n)
<8 $8 C - EI, E (200)
The above result implies the return p² is 1.7 SCC + C C,C. This establishes the convergence of the projected policy gradient algorithm with an iteration complexity similar to that stated in Theorem I for the average reward case.
Follow up/concurrent work in discounted reward case: The work Liu et al. (2024) improved
the iteration complexity of the policy gradient (discounted reward case method O from the
previous state-of-the -fet--rrttttttttt iteration complexity of O SA) Xiao (022a)) : Mei al, 2022 Liu al.
(2024) does not use smoothness of the return to establish sufficient increase lemma, instead leverages the performance difference lemma in novel way.
Our instance-dependent bound for the MDP stems from the smoothness of the return. As result, unclear how the two approaches can be effectively combined to achieve tighter bounds, leaving this avenue for future research.
However, the bound in Liu et al. (2024) can be asymptotically improved by a factor of 1.
1-7' and more meaningful bounds for initial iterates can be obtained using the enhanced
recursion-solving techniques presented in Kumar et al. (2024).
Our work can provide improved, alternative, suboptimal results (depending on the parameters) for the discounted reward case. However, it remains the first to establish the global convergence of policy gradient methods for the average reward setting.
All existing works (Agarwal et al. 2020 Bhandari & Russo 2024 Mei et al. 2022 Xiao 2022a) on the discounted reward case have an iteration complexity that scales with the cardina lities of the state space S and the action space A, with the exception of the recent work by Liu et al. (2024), which the size of the action space poses significant challenges
depends only A. This dependence when attempting to generalize to infinite state-action spaces.
Infinite Action Space. Our work (for both average and discounted reward case) has the MDP
instance bounded bound of SL. where I.]l is the smoothness constant that encodes the hardness of the MDP. This hardness coefficients that makes up L!! may be small/finite for even large/infinite action-space MDPs. However, requires more careful study to determine the conditions for this to happen, which we leave for the future work.
30

---

Published as a conference paper at ICLR 2025
Infinite State Space For the discounted reward setting, Liu al. (2024) provides state- independent bound of (( The approach taken in their work is fundamentally different from ours, and extending this technique to the average reward case presents intriguing direction for future research.
In work, which continues the line of research from Agarwal et al. (2020); Bhandari & Russo (2024); Mei et al. (2022) : Xiao (2022a), the bound exhibits state dependence. This dependence arises from the diameter of the policy class, defined as diam(1I)² -T, . || 11 S S. While this quantity is inherently tied to the state space. it can potentially be bounded for infinite state spaces under certain structures, such as low-rank policy classes. Exploring this direction greater detail is an intriguing avenue for future research. Another challenge is to eircumvent the dependence Crr constant which captures the suboptimality of policy, Cpt can be oo when the state space is infinite, necessitating different approach to characterizing the suboptimality policy.
D.1 PARAMETRIZED POLICY CLASS LOWER BOUNDS
Parametrized policy class. Our work can also be extended to parameterized policy classes, such as softmax policies. For parameterized policy classes, the smoothness coefficient can be derived by augmenting our analysis with the chain and product rules, which is straightforward extension. However, this may result in different hardness coefficients, making it an interesting direction for further exploration. We leave this investigation for future work.
Lower Bounds for policy gradient for average reward case. For the discounted reward setting, Mei et al. (2022) establishes a lower bound O(c-1) for policy gradient methods. Specifically, Theorem 9 of Mei et al. (2022) derives this lower bound using a bandit problem as counterexample. Since bandit
special case of an MDP with a single state, serves as an example for both discounted reward and average reward MDPs. Consequently, the same lower bound of O(e-)) also applies to average reward MDPs, as implied by Theorem 9 of Mei al. (2022).
Linear Rates of Policy Gradient with aggressively increasing step sizes. Policy gradient can be interpreted as a form of soft policy iteration, assuming all states are visited or updated by the policy. Specifically, the learning rate increases, policy gradient behavior increasingly resembles policy iteration. Since policy iteration is known to converge linearly, which is significantly faster than natural expect linear convergence bounds for policy gradient with aggressively increasing learning rates. This has been established in several works, including Xiao| 2022a); Johnson et al. (2023): Liu al. (2024).
the typical convergence rates policy gradient methods,
In most cases, the model is not known, and the exact gradient cannot be computed, requiring the use of stochastic gradient descent. such noisy settings, using aggressive step sizes can lead to instability in the algorithm.
However, in Theorem [ we demonstrated linear convergence rates for simple MDPs with constant step sizes. It may also be possible to achieve similar rates for the average reward case by employing aggressively increasing step sizes, which we leave as an interesting direction for future work.
31


Reviews:
[{"review_id": "YgUiwEofOe", "reviewer": "Reviewer_cy7G", "summary": "This paper presents a comprehensive global convergence analysis for policy gradient in infinite-horizon average-reward MDPs. It proposes a novel proof framework for the smoothness of the average reward objective, which settles the intrinsic challenge of divergence face by the standard analysis technique that regards the average-reward setting as a limiting case of the discounted-reward setting (as $\\gamma \\to 1$). Based on the smoothness results, it further analyzes the convergence properties of policy gradient in the average-reward setting, and concludes with an instance-specific bound convergence bound. Simulation results are presented to justify the analysis and reveal the influence of instance-related constants.", "questions": "1. It is briefly touched upon in *Notes on Limitations and Future Work* that the approach can be generalized to \"parametric classes of policies\". I wonder if the authors have any rough ideas on how this could be done, and further, if it is also doable to extend the tabular MDP setting to generic MDPs with infinite state-action spaces (probably with function approximation, like linear/low-rank MDPs).\n2. The relationship with discounted-reward MDPs is discussed in Section 3.2, where it's written that \"the constants can be derived through an *analogous* process\". Is it possible to (at least) sketch how the final results should look like in the appendix?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper is overall well-written, and the flow is friendly to first-time readers. \n2. The research problem is of theoretical interest and importance, which is sufficiently motivated and justified by a thorough review of literature.\n3. The technical contributions are solid, rigorous, and clearly articulated (as summarized in Section 1.2). The proofs are checked to be correct and are largely self-contained.\n4. Table 1 is especially appreciated since it gives a high-level yet clear idea of the instance-related constants involved in the bound.\n5. I like the discussion presented in Section 3.2 that relates the new results to existing results in the classical discounted-reward setting, as well as a brief hint on the reason why instant-specific bounds may be tighter and thus more useful in applications.", "weaknesses": "1. The simulation results do help to promote the understanding of the instance-related constants, but it can be improved to include more direct and more convincing evidence under the principle of controlled variables. E.g., exemplary MDP families might be explicitly constructed with certain constant(s) varying and all the others fixed, so that the curves clearly reflect how the performance depends on the varying constant(s).\n2. There are a few typesetting issues: (a) Use $\\verb|\\citep|$ and $\\verb|\\citet|$ correctly for the author-year format, and avoid using $\\verb|\\cite|$ — specifically, only use $\\verb|\\citet|$ when it's a part of the sentence. (b) On line 223 and below, use $\\verb|\\ll|$ ($\\ll$) instead of $<<$. (3) There are a few typos and grammatical issues (e.g., the inconsistency of tenses used in the literature review, where I would recommend the use of present tenses only).", "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": "NsXXNf7BFi", "reviewer": "Reviewer_Z6Q6", "summary": "This paper studies convergence of Policy Gradient (PG) in average-reward MDPs and present non-asymptotic bounds on the global convergence of an error function defined in terms of gains of the optimal policy and the output policy by PG. For the class of unichain MDPs (cf. Assumption 1), the authors present convergence rate to the globally optimal solution (of the reward maximization problem in the long run), but without any assumption on the smoothness of the value functions involved. Such smoothness assumptions were key in the analysis in discounted MDPs. The presented convergence rates decay as $O(1/k)$ where the involved constants depend on MDP-dependent quantities. These results also lead to improved convergence analysis of discounted MDPs.", "questions": "See above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Policy Gradient (PG) and its variants are among interesting and important algorithms in RL. Their convergence properties for the class of discounted MDPs are very well-studied and by now well-understood. However, their counterparts for average-reward MDPs are less explored, especially when the interest lies in globally optimal solution. This is mostly due to the challenges involved in the average-reward setting, rather than the interest in the problem. \n\nOne strength of the approach taken in the paper is to depart from the classical approach of using a discounted MDP as a proxy, which further leads to sub-optimal bounds. This way the authors eliminate the smoothness assumption that is typically made in the convergence analysis of PG in the context of discounted MDPs. \n\nThe paper admits a good organization. Its technical part is written mostly clearly and precisely, apart from some inconsistent or undefined notations (see comments below). However, there are some inconsistencies in the presentation and advertisement of the results between the introductory part and the main technical part; further on this below. The writing quality is overall fine, but some parts could still benefit from a more careful polishing.  \n\nAs a positive aspect, the paper delivers a good and accurate review of related literature, to my best knowledge. Yet another positive aspect is reporting numerical results, albeit on toy problems.", "weaknesses": "Key Comments and Questions:\n-\n- The opening of the paper (Abstract and Introduction) talk about regret bounds for PG (scaling as $O(\\log(T))$). Figuratively speaking, these are cumulative measures of error incurred by the algorithm. But they are not defined anywhere – or do I miss something? – and the core part of the paper only deals with per-step error measures. Please clarify. \n- Despite some interesting results, one key limitation of the paper is the restriction to the class of unichain MDPs (cf. Assumption 1). They are far easier to deal with and are much less relevant in modeling practical RL tasks when compared to the more interesting class of communicating MDPs. Without this assumption, one will not get a closed-form value function in Lemma 1, which is key to establish the results. In other words, it renders unlikely, in my opinion, that the technical tools developed or promoted here could be used beyond the restricted class of MDPs satisfying Assumption 1.   \n- A key question is how bad the MDP-dependent constant $C_{PL}$ could be. Even though a convergence rate of $O(1/k)$ is superior to those decaying as $O(1/k^p)$ for some $p<1$, the involved MDP-constants (e.g., in Theorem 1) could be prohibitively large in some MDPs (that are not necessarily pathological). More precisely, I expect it could be exponentially large in the size of state-space $|\\mathcal S|$.\n- In the first paragraph of Section 1, you discuss approaches for determining the optimal policy (i.e., planning algorithms) for average-reward MDPs. Yet you mostly cite papers dealing with the learning problem. Could you clarify, or correct if relevant?  \n\nMinor Comments:\n-\n- In line 50, you use $\\pi_k$ but it is not defined yet. \n- Regarding refs: Please check formatting guidelines. In many places you must use \\citep or \\citet instead of \\cite so that you get (A & B, year) instead of A & B (year); for instance, in the first paragraph of Section 1. But they are correctly used in Section 1.1. This issue renders rather distracting when reading the paper. \n- The work (Lin Xiao, 2022) is cited twice. Is there any difference between them? \n- Line 133 (and elsewhere): Using $\\Delta(\\mathcal A)$ instead of $\\Delta \\mathcal A$ could make things more readable.  \n- Inconsistent notations: In Eq. (8) you used $d_\\mu(\\pi^*)$ whereas later you used $d_{\\mu,\\gamma}^{\\pi^*}$ to denote essentially the same thing. \n- Unless I am missing something, the textbook (Boyd and Vandenberghe, 2004) does not include definition of $L$-smoothness, etc.  \n- Table 1: Make precise the norms used for $C_p$ and $C_m$.\n\nTypos:\n-\n- Line 82: is , Bai et al. ==> remove “,”\n- Line 198: … relationBertsekas …. ==> … relation (Bertsekas, …)\n- Line 251: Further is the function is ==> Further if … \n- Line 269: euclidean norm ==> Euclidean norm ---- to be consistent with an earlier use of this term. \n- Line 346: in the Lemma below ==> … lemma …\n- Line 384 and elsewhere in Section 3.2: To be consistent with notations used elsewhere, use $|\\mathcal S|$ instead of $S$ since the latter is not defined. \n- Line 398: By $L$, did you mean $L_2^{\\Pi}$?\n- Line 388: a verb might be missing.", "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": "pDfxtfPQYn", "reviewer": "Reviewer_D3ZP", "summary": "The author show that Project Policy Gradient ascent for average reward MDPs can achieve an $O(\\frac{1}{\\eps})$ rate to the optimal policy.  To attain this rate, the authors prove the smoothness property of the objective. Additional experiments are conducted to validate the proposed rates.", "questions": "- When presenting the convergence rates of the related works, why was the dependence of $\\epsilon$ omitted?\n- Could the remark of Theorem 1 be clarified. Why is the bound $$\\frac{\\sigma}{k^p}$$ less meaningful for the inital $k$? Isn't $k$ the number of iterations? Also note that for softmax policies, there exists faster convergence rates shown in [1] compared to [2].\n- Is it possible to show that the $O(\\frac{1}{\\epsilon})$ bound is tight? \n\n\n[1] Liu, J., Li, W., & Wei, K. (2024). Elementary analysis of policy gradient methods.\n[2] Mei, J., Xiao, C., Szepesvari, C., & Schuurmans, D. (2020, November). On the global convergence rates of softmax policy gradient methods.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- First proof of global convergence of Project Policy Gradient for average reward MDPs.", "weaknesses": "- Missing comparison to [1]. This work improves the convergence rate of [2] and show the rate of Policy Mirror Descentt is linear. Projected Policy Gradient is an instance of Policy Mirror Descent when the squared Eucliden distance is used as the mirror map.\n- The clarity of the writing could be improved, \n - The precise definition of $d^\\pi(s)$ should be given\n - It's not clear what the step-size used in Thereom 1 Is\n- A reference / proof for Eq. 8 should be given. \n- Formatting errors: 155: Bellman equation equation 3, 181: discount factorBertsekas (2007), 202: \\textit{equation 8}\n\n\n[1] Johnson, E., Pike-Burke, C., & Rebeschini, P. (2023). Optimal convergence rate for exact policy mirror descent in discounted markov decision processes.\n[2] Xiao, L. (2022). On the convergence rates of policy gradient methods.", "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": "MpYpDieVeQ", "reviewer": "Reviewer_WdYp", "summary": "The paper presents the convergence rate analysis of the projected policy gradient algorithm for tabular average reward Markov decision processes (MDPs). Assuming access to the exact gradient, the authors proved a convergence rate of $\\mathcal{O}(1/T)$ where $T$ is the number of iterations. To prove the result, they established the smoothness property of the value function for ergodic MDPs, which is of separate interest.", "questions": "1. Since a linear convergence rate is already available in the discounted setup (Xiao 2022b), is it possible to achieve the same in the average reward setup? What are the fundamental challenges to obtain it?\n\n2. Please mention in Table 1 that the constants $C_e$ and $\\lambda$ are taken from Assumption 1. It will help the reader.\n\n3. Is the smoothness result only valid for ergodic MDPs or is it possible to extend it to a larger class?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. New state-of-the-art convergence rate of $\\mathcal{O}(1/T)$ for projected gradient descent algorithm for average reward MDPs.\n2. New smoothness result of the value function for the same setting.\n3. Despite some weaknesses stated below, the paper is overall nicely written.", "weaknesses": "1. The authors should rewrite the related works and put their work in context. First, they should separate the related works into two groups: ones that use exact gradients (and hence, are more of a planning problem), and others that use gradient estimates (and therefore, are more of a learning problem). Authors should note that some papers explicitly fall into the second group while many others discuss problems of both kinds. The work of the authors falls into the first group. This should be highlighted both in the abstract as well as in the introduction.\n\n2. While mentioning the convergence rate established by earlier works, the authors only focused on the $1-\\gamma$ factors while completely ignoring the $\\epsilon$ related factor. For example, equation (1) does not show any dependence on $\\epsilon$. Is there any specific reason for that? I think it makes the comparison quite confusing.\n\n3. Although one of the results of (Xiao 2022b) proves a convergence rate of $\\mathcal{O}\\left((1-\\gamma)^{-5}\\epsilon^{-1}\\right)$, in the same paper, they also provide a better result. Specifically, using policy mirror descent, which can be thought of as a generalization of the policy gradient, they establish a linear convergence rate of $\\mathcal{O}\\left((1-\\gamma)^{-1}\\log\\left((1-\\gamma)^{-1}\\epsilon^{-1}\\right)\\right)$. I am surprised that the authors failed to mention the linear convergence rate.\n\n4. Some of the state-of-the-art results mentioned are outdated. For example, (Bai et. al. 2023) is no longer the only work that establishes a regret bound for average reward MDP. A recent paper [1] supersedes their result.\n\n5. To my understanding, the concept of regret makes sense only for a learning problem, not for a planning problem. In my opinion, the author should solely stick to the convergence rate result.\n\n[1] Ganesh, S. and Aggarwal, V., 2024. An accelerated multi-level Monte Carlo approach for average reward reinforcement learning with general policy parametrization. arXiv preprint arXiv:2407.18878.", "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)