A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
Authors: Swetha Ganesh
Washim Uddin Mondal
Vaneet Aggarwal
Venue: ICML 2025 poster (2025)
Keywords: Actor-Critic
Multi-level Monte Carlo
Natural Policy Gradient
General Policy Parametrization
Primary area: theory->reinforcement_learning_and_planning
TL;DR: Order-optimal global convergence rate for an actor-critic approach in average reward RL with general policy parametrization

Abstract: This work examines average-reward reinforcement learning with general policy parametrization. Existing state-of-the-art (SOTA) guarantees for this problem are either suboptimal or hindered by several challenges, including poor scalability with respect to the size of the state-action space, high iteration complexity, and a significant dependence on knowledge of mixing times and hitting times. To address these limitations, we propose a Multi-level Monte Carlo-based Natural Actor-Critic (MLMC-NAC) algorithm. Our work is the first to achieve a global convergence rate of $\tilde{\mathcal{O}}(1/\sqrt{T})$ for average-reward Markov Decision Processes (MDPs) (where $T$ is the horizon length), using an Actor-Critic approach. Moreover, the convergence rate does not scale with the size of the state space, therefore even being applicable to infinite state spaces.

A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
Swetha Ganesh 12 Washim Uddin Mondal
Vaneet Aggarwal
Abstract
munication networks (Agarwal et al., 2022), and healthcare (Tamboli et al., 2024). Model-based algorithms (Jaksch et al., 2010; Agrawal & Jia, 2017; Agarwal & Aggarwal, 2023) that Iearn the state transition kernel from Markovian trajectories, are well-known approaches for solving RL prob- lems. However, these methods are typically limited small state spaces. Policy Gradient (PG) methods, a cornerstone of RL, offer model-free alternative that naturally supports function approximation (FA), making them well-suited for large state-action spaces. When the size of the state-action space, 5 S, is large or infinite, the framework of FA (also known as general parameterization) indexes the candidate policies by a d-dimensional parameter, 6, where d << SA. Recently, some works have established global convergence guarantees for the average-reward setting with general pol- icy parametrization, which we discuss below.
This work examines average-reward reinforce- ment learning with general policy parametrization. Existing state-of-the-ard (SOTA) guarantees for this problem are either suboptimal or hindered by several challenges, including poor scalability with respect to the size of the state-action space, high iteration complexity, and a significant de- pendence on knowledge of mixing times and hit- ting times. To address these limitations, we pro- pose a Multi-level Monte Carlo-based Natural Actor-Critic (MLMC-NAC) algorithm. Our work is the first to achieve global convergence rate of ((1/VT) for average-reward Markov Deci- sion Processes (MDPs) (where is the horizon length), using an Actor-Critic approach. More- over, the convergence rate does not scale with the size of the state space, therefore even being applicable to infinite state spaces.
There are two main approaches in this context. The first is the direct PG method, where value functions are estimated directly from sampled trajectories (Bai et al., 2024; Ganesh et al., 2025b). The second is the Temporal Difference (TD)- based policy evaluation approach, commonly known as the Actor-Critic (AC) method (Patel et al., 2024; Wang et al., 2024). Currently, the order-optimal (T-2 convergence rate result, where I' is the horizon length, exists for direct PG method (Ganesh et al., 2025b). However, these methods face key limitations, including poor scalability to large state- action spaces and strong reliance on precise knowledge of mixing and hitting times to decorrelate samples, an as- sumption that is often impractical. In contrast, existing AC algorithms circumvent these issues but are generally more challenging to analyze. More specifically, AC methods em- ploy a TD-based critic to estimate the value function, which helps in reducing the variance. However, this reduction comes the cost of introducing a bias, in addition to the inherent bias arising due to Markovian sampling. Direct PG methods using Markovian sampling leverage knowledge of mixing time to obtain nearly i.i.d. samples, whereas this would not suffice for AC methods due to the additional bias from the critic. As a result, the state-of-the-art bounds for AC is (1/T2/44) which is suboptimal. This raises the following question:
1. Introduction
Reinforcement Learning (RL) is a framework where agent interacts with Markovian environment and maxi- mizes the total reward it receives. The temporal dependence of the state transitions makes the problem of RL much more challenging than ordinary stochastic optimization, where data are selected in an independent and identically dis- tributed (i.i.d.) manner. RL problems are typically analyzed via three setups: episodic, discounted reward with an infi- nite horizon, and average reward with an infinite horizon. The average reward framework is particularly significant for real-world applications, including robotics (Gonzalez et al., 2023), transportation (Al-Abbasi et al., 2019), com-
'School of Industrial Engineering, Purdue University, West Lafayette. USA 'Department of Computer Science and Automa- tion, Indian Institute of Science, Bengaluru, India 'epartmentt of Electrical Engineering, Indian Institute of Technology, Kanpur, In- dia. Correspondence to: Vaneet Aggarwal <vanect@ wwwteepuuuuuuuu.....
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
Algorithm
Infinite States
Global
Model-Free?
Policy
and Actions?
Convergence
Parametrization
UCRL2 (Jaksch et al., 2010)
No
O(1/VT)
No
Tabular
PSRL (Agrawal & Jia, 2017)
No
O(1/VT)
No
Tabular
MDP-OOMD (Wei et al., 2020)(1)
No
O(1/VT)
Yes
Tabular
PPGAE (Bai et al., 2024)
No
O(1/T4/4)
Yes
General
PHPG (Ganesh et al., 2025b)
No
O(1/VT)
Yes
General
NAC-CFA (Wang et al., 2024)
Yes
O(L/T1/4)
Yes
General
MAC (Patel et al., 2024)
Yes
O(1/T1/4)
Yes
General
MLMC-NAC (Algorithm
Yes
O(1/VT)
Yes
General
Table Summary the key results on global convergence guarantees for average reward reinforcement learning. (1) (' work also analyzes another algorithm using the more general weakly-commumicating MDP assumption while achieving higher rate of (5//
Is possible to achieve a state-action space size indepen- dent global convergence rate of Ô (T-1/2) for general parameterized policies in average reward infinite-horizon MDPs, using a practical, Actor-Criie Critic approach?
can remain constant (Nagaraj et al., 2020). (Nagaraj et al., 2020) mitigates this by using one sample every fiix steps. Instead, we leverage MLMC to reduce the bias.
In Theorem 2, we establish a convergence rate for a generic stochastic linear recursion. Given that both the NPG and critic updates
This work answers this question affir- matively. In particular, introduce Multi-level Monte Carlo-based Natural Actor-Critee (MLMC-NAC) algorithm
Our Contribution:
be viewed stochastic linear update, this forms basis for Theorems 3 and 4. that comprises two major components. The first component, referred to as the Natural Policy Gradient (NPG) subroutine, obtains an approximate NPG direction which used to up- date the policy parameter. One sub-task of obtaining the NPG is estimating the advantage function. This is done via the second component, known the Critic subroutine that achieves its desired target via Temporal Difference (TD) learning. Both NPG and critic subroutines apply MLMC- based gradient estimators that eliminate the use of the mix- ing time the algorithm. We establish that MLMC-NAC achieves a global convergence rate of (12) which is optimal in the order of the horizon length T. The key con- tributions in this work summarized follows:
Theorem proves the first Ó(T-1/2) global convergence result for AC methods.
Related works: We will discuss the relevant works in two key areas as stated below. Our discussion primarily focuses works that employ general parameterized policies. A summary of relevant works is available in Table 1.
Discussion on Practicality on direct PG methods: In direct PG methods, value function estimates are nearly un- biased but suffer from high variance, which scales with the size of the action space (Wei al., 2020; Bai al., 2024; Ganesh et al., 2025b). Furthermore, the convergence results depend on the hitting time, which is at least the size of the state space, making the algorithm inapplicable to large or infinite state spaces. Finally, the implementation these algorithms require precise knowledge of mixing and hitting times to decorrelate samples, which can be impractical. In contrast, our algorithm leverages Multi-Level Monte Carlo (MLMC) mitigate bias arising from Markovian sampling.
While existing AC analyses often use relatively loose bounds, we refine the analysis achieve sharper results. Our first step towards this is to show that the global con- vergence error is bounded by terms proportional to the bias and second-order error in NPG estimation (Lemma 1). Since the critic updates underlie the NPG subroutine, the NPG estimation errors are inherently linked to critic estimation errors.
Other recent PG-based works include (Kumar et al.. 2025), which studies the tabular policy parameterization under the assumption of exact gradient access and establishes a conver- gence rate of Ó /T). However, this assumption sidesteps key challenge in PG-based methods, efficient estimation of the policy gradient, which remains significant bottleneck in more practical settings. Another related work is (Murthy et al., 2023), which studies robust average-reward Markov decision processes (MDPs) and establishes convergence guarantees for dynamic programming approaches.
In prior AC works (Wang et al., 2024; Patel et al., 2024), the global convergence bound includes the critic error, E [[E, - -- where &r is the critic estimate at time / and e* is the true value. Instead, using Lemma 1 and Theorem 3, our analysis reñines this term to || [[G]] {*],, which can be significantly smaller than the previous estimate.
Bounding || [[[[]] | still remains challenging due to Markovian noise. The critic update can be interpreted as a linear recursion with Markovian noise. Under i.i.d. noise,
this term decays exponentially, but with Markovian noise,
Average Reward RL with Actor-Critia approaches: The
2

---

A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
authors of (Chen & Zhao, 2023; Panda & Bhatnagar, 2025; Suttle et al., 2023) provided local convergence guarantees for the AC based approaches. Recently, the global conver- gence for the AC methods in average reward setup have been studied in (Wang et al., 2024; Patel et al., 2024), where global sample complexity of (T 114) is shown'.
where E denotes the expectation over the distribution of all reginduced trajectories and 1()) is an indicator function. The above distribution also obeys (P T d d With
this notation in place, we define the mixing time of an MDP.
Definition 1. The mixing time of an MDP M with respect to a policy parameter 0 is defined as
We note that (Suttle al.. 2023; Patel et al., 2024) uses the Multi-Level Monte Carlo (MLMC)-based) AC algorithm combined with AdaGrad (Duchi et al., 2011), inspired by stochastic gradient descent (SGD) related work in (Dorfman & Levy. 2022). Unfortunately, none of these studies lead to an optimal global convergence rate which is the goal of our work. We also note that the current state-of-the- art global convergence rate for AC methods in discounted MDPs is 1/3) (Xu et al., 2020; Gaur et al., 2024), and the approaches proposed in this work have the potential to be applied in that setting.
1 Liix == min { 2 1 (I((()))) 8= ITv S 7 Vs Y
where || I|TV denotes the total variation distance. We define mix = supaee fnix as the the overall mixing time. This paper assumes mix to be finite.
The mixing time of an MDP measures how quickly the MDP approaches its stationary distribution when the same policy exccuted repeatedly. In the average reward setting, we aim to find a policy wo that maximizes the long-term average reward defined below.
2. Setup
J == limm E.o + ((s an) ~ | (2)
In this paper, we explore an infinite horizon reinforcement learning problem with an average reward criterion, modeled tuple
by a Markov Decision Process (MDP) represented M- (S,A,, r, P). Here S indicates the state space, A
For simplicity, we denote J(0) = _ This paper uses an actor-critic approach to optimize J. Before proceeding further, we would like to introduce a few important terms, The action-value (Q) function corresponding to the policy Ty is defined
defines the action space with a size of A, r S x A- + [0, 1] represents the reward function, P: : S x A + (SS) defines the state transition function, where (SS) denotes the probability simplex over S, and o E ASS) signifies the initial distribution of states. A (stationary) policy क. : s + (AA) determines the distribution of the action to be taken given the current state. It induces the following state transition pm : S + A(S) given as PT (s, EeEA P(s'ss, a)T(als), Vs, s' E S. Observe that for any policy æ, the sequence of states yielded by the MDP forms a Markov chain. We assume the following throughout the paper.
(s, 1h.s En (r(si, ](00 8,
(3)
We can further define the state value function as
V (s) = I8 1= (s. as]
(4)
Bellman's 's equation, thus, takes the following form (Puter- man, 2014)
The Markov chain induced by every policy n. {s:]2o, is ergodic.
Assumption 1.
(s. :) r(s ((0) + E(V
(5)
Before proceeding further, we point out that we consider parameterized class of policies II, which consists of all policies Ty such that 0 E O, where θ C IRdd. It is well- established that if M is ergodic, then v0 E +, there exists a unique stationary p-independent distribution, denoted as d E (SS), defined as follows.
where the expectation is over s' ~ P(- a). We define the advantage AT (s, & =Q ( a) V (s). With the notations in place, we express below the well-known policy gradient theorem established by (Sutton et al., 1999).
V
1 (s, (s, a) log logmo(als)
(6)
d (s) +o E.s } Ero 1(s () 80
50) ~p) o)
(L)
where gorithms maximize the average reward by updating 0 along the policy gradient (0) In contrast, Natural Policy Gra- dient (NPG) methods update 0 along the NPG direction wi where
Policy Gradient (PG) al-
While (Wang et al., 2024) shows min minugrer(J'" ((.)) <
O(33)/3), we note that the minimum error is strictly smaller than the average error notion that we consider our work. Substituting the bound in Proposition 5 in their work in their average error decomposition in Step 1 of their Proof Outline yields an average error of Ö(T 1/4).
w/ = -
(7)
3

---

A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
The symbol i denotes the Moore-Penrone pseudoinverse and F(0) is the Fisher matrix defined as
Algorithm Multi-level Monte Carlo-based Natural Actor- Critic (MLMC-NAC)
I: Input:
Initial parameters Op- {w J. and {Sh], policy update stepsize a, parameters for NPG update, y, pa- rameters for critic update, 8, ca. initial state so ~ p. outer loop size K, inner loop size H, Tmax
0)) (o VV log (a(ass Vo log (a]ss]
(8)
where @ symbolizes the outer product. The precoder F(0)
takes the change of the parameterized policy with respect to l into account, thereby preventing overshooting or slow updates of 0. Note that wg can be written as the minimizer of the function Ly (,,0) where
Initialization: T <- 0
3: for k = 0, 1, ... K 1 do
4: for h = 0, H 1 do (Average reward and
critic estimation
Luzo (w.0) 1 Beeaaorr (1)5 w log =(l)s))) (9)
5:
shh +- 80, Qkk ~ Geom(1/2)
Qun +- 2 if uM < max else Qun +- 0
for 0. ..... Quh 1
for all Rd. This essentially a convex optimization that can be iteratively solved utilizing gradient- based method. Invoking (6), one can show that
Take action at T=T,, (+1spt))
Collect next state 8,41
khh
P(-|shh ( a.)
10:
Receive reward r(st), ath)
Viliva (w, 0) F(O) (o)
(10)
11:
end for
12:
TEA + Qun. +-
TTh
kh
Note that Tw (w, 0) is not exactly computable since the transition function P and hence the stationary dis- tribution, d and the advantage function, ( are typically unknown in most practical cases. Recall that A (s, a) = QT (s, a) (s).. Moreover, Bellman's 's equation (5) states that QT (s, a) is determined by J(0) and V Notice that [() can be written solution to the following optimization problem.
13:
Update 5% using (16) and (25)
14:
++T+72 Tah
15:
end for
16:
Ek + ck
17:
for H. 1,, 1.21,.,,HHH1111 -
do (Natural Policy
Gradient (NPG) estimation)
18:
kh +- 80, Qix Geom(1/2)
19:
Qua + 20a if 2 < Timax else Quh +- 0
20:
for t = 0. Qsh - do
min R(0,n) n) MER
ΣΣ aES aEA
3 (n- (11)
21:
Take action kh ~ -TT, (-lathh) Collect next state shh st+1 ~ P(-|s a
22:
23:
Receive reward r(s
kh a.h)
The above formulation allows us to compute J(0) in a gradient-based iterative manner. In particular,
24:
end for
25:
TEn < Quh. 80 Shh
26:
Update w using (17) and (21)
v,,((,,)) Exes Emes ( (n r(s (12)
27:
T T - Tkh
28: end for
29: Wk whn au+1 G₁ + aww (Policy update)
To facilitate the estimation of the advantage function, we assume that V (.) can be approximated by a critic function V(a..) -) (Co) <()) where Co E I denotes a solution to the following optimization problem, and Φ(s) E RT, [|ø(s)]| < 1 a feature vector, Vs S.
30: end for
3. Proposed Algorithm
We propose Multi-level Monte Carlo-based Natural Actor- Critic (MLMC-NAC) algorithm (Algorithm 1) that runs K number of epochs (also called outer loops). The kth loop obtains & = [m,, [&] where V)k denotes an estimate of the average reward J (Oe), and Ç& is an estimate of the critic parameter, Ço.. These estimates are then used to compute the approximate NPG, Wk, which is applied update the policy parameter fz.. akt1 02 + awo
1 Σ TT (Te (s)(vv)))) s)) (13)
min E(8.C)= <
2
SES
The above formulation paves way to compute &o via gradient-based iterative procedure. Note the following.
V C() ΣΣ SES AEA
Te (s, a) (S - (s, a)} ((s)
(14)
(15)
The iterative updates of f, 7,, and Ç, along their associated gradients provided in (10), (12), and (14) form the basis of our algorithm stated next.
where a is learning parameter. The estimate &a. is obtained in H inner loop steps. In particular, vh E (O.... , H we apply the following updates starting from arbitrary E
1},

---

A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach and finally assign ch = Ek-
given as follows.
ch+ = - 5h),, where
V VuLur (whi Ex)
(0k ch) = |ca V, nh, E <t)
T (16)
22 (U9-
if < Tmax (21)
Un +
1
otherwise
where C9 is constant, and f is learning rate. Observe that (0,, <tt has dependence on c = -Iih Shl"T due to the presence of Q-function in (14) while V. V,, m// is dependent only on o/f. (details given later).
= -Aukhh AMIMO (0x) - iMILM Ex)+Ex)
where U = + 2 wfth jE [Q- 1, Q). Tmax 2 2 is
parameter, and A.,.A
6MLMCC (0xx Ex) denote A (0x), and u.
The approximate NPG We is also obtained in H inner loop steps, starting from arbitrary wř, then recursively apply- ing the stochastic gradient descent (SGD) method as stated below Vh E {H, ,22 - 1}, and assigning wis = whn
MI MLMC-based estimates of samples { {Au(O,, ) ) and (0n(Ok, =/th) ) =)= respectively.
The advantage of MLMC is that it generates the same or- der of bias as the empirical average of Tmax samples but requires only Olog T max) samples on an average.
w = wh- - 7 Voll (sh,0s; Ex)
(17)
Using similar method, we will now obtain an estimate of (0,, <f) Following our earlier notations, we denote TEA = {(sbh, at ) as a To, -induced trajectory of length 4A 29ax, where QuA ~ Geom(()) Notice the terms stated below Vt E {0, ... 1A--11
where 7 is a learning parameter, and V.L (w Os, Ek) symbolizes an estimate of V.L,,"% (W 0x). We would like to clarify that the above gradient estimate depends on & because of the presence of the advantage function in the expression of the policy gradient whose estimation needs both 17s. Sk (dctails given later). A process is stated below to calculate the gradient estimates used in (17) and (16).
cB (1/ - -r(shh a H(tt) ((st Tcs - -Qmoa (Eh e/th) Jo(sth) ( (v(=M))) by (=bhit
vea
(22)
Gradient Estimation via MLMC: Consider a Mo, -induced trajectory Ten {(s at sf41)) Mes whose length is given as 4A. 2Qmh where QEA ~ G) We can write the Q estimate as below Vt E (0.... .4n - 1} using Bellman's 's equation (5).
where 2/th = (stth ath sttt), Quo, a (ch 21th) is given by (18) and (z(zh,) ), (z(th) are defined as
(18) where =/th = (sth att 1) This leads to the advan- tage estimate (also called the temporal difference error) as follows VI E {0..... .4u - 13..
TT (Ex: -bh)) = r(s a - mh + Ge (o
(=( =
(o(stih) s(ah)) [o(stth) (( ( -
cB
(23)
cor(sth abty ]
(x(t)) = [r(s hhh aaa (osth)) (hh)
(24)
Based on (12) and (14), the term w can be thought of as a crude approximation of vn sh) obtained using a single transition, kk The final estimate is
A ( )/t) r(stth, atti)) T7
(19)
+ Gt [o(stti)) - c((
2 (Ve - VQ-1), if <Tmax otherwise
Define the following quantity Vt E (0,... .4n - 1}.
(0,, = Vo +
0
with = Au(On, =/th Jw - bu Ck. =/th) where Au(Os, :M)) = Vo log Tox (a (o (oth)) 2 V log To, (ab 1o
(20)
AMIMC A. Sh
MMMMC
(25)
where Vi = -'' v.t . (Q- 1, Q). Moreover, ÂMLMC and (MLMC symbolize MLMC-based estimates of AM
(a Ex. 2hh) ANoa (Ex, 2t Ve log To. (a Mh s/th)
v,R,h (Av(* and (bx(2 (2("))))) 3 respectively.
The term tht can be thought of as crude estimate of VuL,, (wg, 0k), obtained using a single transition afth One naive way to refine this estimate is to calculate 1 empirical average of {u, J In this work, however,
A few remarks are in order. Although the MLMC-based estimates achieve the same order of bias as the empirical average with a lower average sample requirement, its vari- ance is larger. Many existing literature reduce the impact of the increased variance via AdaGrad based parameter up- dates. Though such methods typically work well for general
we resort to the MLMC method where the final estimate is
We initiate from h- H, instead of 0 emphasize that the iteration (17) starts after H iterations of (16).
5

---

A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
non-convex optimization problems, it does not exploit any inherent structure of strongly convex optimization problems, thereby being sub-optimal for both the NPG-finding sub- routine and the average reward and critic updates. In this paper, we resort to a version of the standard SGD to cater to our following needs. First, by judiciously choosing the learning parameters, we prove that it is possible to achieve the optimal rate without invoking AdaGrad-typs updates. Finally, although our gradient estimates suffer from bias due to the inherent error present in the critic approximation, our novel analysis suitably handles these issues.
Assumption 4. For any O. the transferred compatible func- tion approximation error, Toys (wz; f), satisfies the follow- ing inequality.
Les (wg: 0) S ébias
where wp denotes the exact NPG direction at 0 defined by (7), x indicates the optimal policy, and the function L (+.-) is given by (9).
A Assumption 5. For all 8, 1, 82 and (s,a) E S x A, the following statements hold.
(a) V log To (a|s)))]] - G₁
(6) V log na, (als) V log (o,(s) & C2 02
4. Main Results
Assumption 6 (Fisher non-degenerate policy), There exists a constant μ > 0 such that F(0) - pla is positive semidefi- nite where Ia denotes an identity matrix.
We first state some relevant assumptions. Let Ao
Eo {=(=)] and (0) Es [=)] where matrices (x). (z) are described in (23), (24) and the expectation Eg is computed over the distribution of = (s, a, s') where (s, a) ~ v"a, s' ~ P(-|ss a). For arbitrary policy parameter 0, we denote E = [Av (0)) (0) = in Cā]". Using these notations, below we state some assumptions related to the critic analysis.
Comments on Assumptions 4-6: We would like to high- light that all these assumptions are commonly found in PG literature (Liu et al., 2020; Agarwal et al., 2021; Papini et al., 2018; Xu et al., 2019; Fatkhullin et al., 2023). We claborate more on these assumptions below.
The term ébias captures the expressivity of the parameterized policy class. If, for example, the policy class is complete such as in the case of softmax parametrization, Cbiss 0 (Agarwal et al., 2021). However, for restricted parametriza- tion which may not contain all stochastic policies, we have ébias > 0. is known that ébias is insignificant for rich neural parametrization ( (Wang et al., 2019). Note that As- sumption requires that the score function is bounded and Lipschitz continuous. This assumption is widely used in the analysis of PG-based methods (Liu et al., 2020; Agarwal et al., 2021; Papini et al., 2018; Xu et al., 2019; Fatkhullin et al., 2023). Assumption 6 requires that the eigenvalues of the Fisher information matrix can be bounded from be- low and is commonly used in obtaining global complexity bounds for PG-based procedures (Liu et al., 2020; Zhang et al., 2021a; Bai et al., 2022; Fatkhullin et al., 2023). As- sumptions 5-6 were shown to hold for various examples recently including Gaussian policies with linearly parame- terized means and certain neural parametrizations (Liu et al., 2020; Fatkhullin et al., 2023).
Assumption 2.
We assume the critic approximation error, Eapp (defined below) is finite.
app sup F(O, (B)
(26)
9
Assumption 3. There exist A >>> 0 such that AA
(o())))(((s) +(s') XI
(27)
where > is the positive semidefinite inequality and the ex- pectation, Bg is obtained over d s ~ pno (so )
Both Assumptions 2 and 3 are frequently employed in the analysis of actor-critic methods (Suttle et al., 2023; Patel et al., 2024; Wu et al., 2020; Panda & Bhatnagar, 2025). Assumption 2 intuitively relates to the quality of the feature mapping where Eapp measures the quality. Well-designed feature maps may lead to small or even zero Capp. whereas poorly designed features result in higher error.. Assumption 3 is essential for guaranteeing the uniqueness of the solu- tion to the minimization problem (13). Assumption 3 also follows when the set of policy parameters, θ is compact and e & Ws, where e is the vector of all ones and Ws is the space spanned by the feature vectors. To see this, note that if é Wo, there exists Xg for every policy To such o(s')) v dol (Zhang et al., 2021b). Since θ is compact, setting x= infgee Xo 0 satisfies Assumption 3.
With the relevant assumptions in place, we are now ready to state our main result.
Theorem 1. Consider Algorithm I with K = K H
@ log(T)). Let Assumptions 1-6 hold and J be L- smooth. There exists a choice of parameters such that the following holds for a sufficienlly large T.
that IEg ((((()((((
1 K-1
For large enough cs. Assumption 3 implies that Av(0)- (A/2) is positive definite (refer to Lemma 8). It also implies that (8) is invertible. We will now state some assump- tions related to the policy parameterization.
J
Σ
B[J(Ok)] S 0 (V(Cppp + Vibius)
K
0=0
+ δ (13 (mixx T-12) (28)
6

---

A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
where JH is the optimal value of (.).
J is the optimal value of the function J(-), and E&L-] de- notes conditional expectation given the history up to epoch k.
The values of the learning parameters used in the above the- orem can be found in Appendix H. It is to be mentioned that the above bound of (1/V/T) is a significant improvement in comparison to the state-of-the-art bounds of (1 in the average reward general parameterization setting (Bai et al., 2024; Patel et al., 2024). Also, our bounds do not depend on the size of the action space and hitting time un- like that in (Bai et al., 2024). Although (Patel et al., 2024) provides bounds with O (m/im)) dependence, these bounds, unfortunately, depend on the projection radius of the critic updates. Ry, which can be large and scale with mix (Wei et al., 2020). In contrast, our algorithm does not use such projection operators and therefore, does not scale with Rw-
Note that the last term in (30) is (1/K). The term E |wxx| l can be further decomposed as
E ww 1 S 2 ||wx - will 2 + IE |wil|
2E 1| - will + 2 E V
(31)
where (a) follows from Assumption 6 and the definition that a = ((o%)-'VoJll Further, it can be proven that for the choice of a used in Theorem 1, we have
Our analysis assumes L-smoothness of the average reward objective J. a standard assumption in the PG literature. In the average-reward setting, smoothness typically assumed, either explicitly or implicitly via Lipschitz continuity of the value function by appealing to discounted-setting bounds (Chen& & Zhao, 2023; Suttle et al., 2023; Patel et al., 2024; Ganesh et al., 2025a; Wang et al., 2024; Bai et al., 2024; Panda& & Bhatnagar, 2025). A recent result (Ganesh et al., 2025b, Theorem 3) establishes a smoothness-type result under ergodicity in the average-reward, mninite-horizon set- ting, which could be used in our analysis but is omitted here to streamline the presentation. Algorithm assumes knowl- edge of L to set the policy learning rate, and the smoothness upper bound in the cited work depends on mmix. However, the dependence on fmix in Algorithm is much weaker than in existing direct policy gradient methods, which require samples to be spaced (tmmix) apart at each iteration.
1
K
Σ
IV
Jo
32LG4 μ²K
122KK
k=
(32)
(2G 112 +1)
1 K
1 - will
Evidently, one can obtain a global convergence bound by bounding the terms E ||wx - will and E [| [wx] - wg]l These terms define the second-order error and bias of the NPG estimator, Wg. In the next subsections, we briefly describe how to obtain these bounds.
5.2. Analysis of General Linear Recursion
Observe that the NPG finding subroutine (17) and the update of the critic parameter and the average reward (16) can be written in the following form for given k.
5. Proof Outline
Fh+11 = Tip 3(Pror 4n)
(33)
5.1. Policy update analysis
where Ph. 9r are MLMC based estimates of the matrices P RRxx q E R. respectively, and h {0. H 1}.
Lemma 1. Consider any policy update rule of form
Assume that the following bounds hold Vh.
Oc+1 = O2 + Orukk-
(29)
E₁
Ph p
|
27
S of
En
Ph.
pl|
S 8%p
If Assumptions 4 and hold, then the following inequality is satisfied for any K.
(34)
[ gll
S o/ EB [hh)
all²
S 8
and ||E [ūn] g12
2 < 82
K- K
J
B[J(Ox)]
< / bias
where E, denotes conditional expectation given history up to step h. Since [[âg]] E[EA[GN]], we have 5ū s 5g Additionally, assume that
k=0
G
K
aG2
K
E [wp]] will
E
|k>| 1|
K
2K
0 ApT x P. |P]|| S Ap and ||gl| S Ag
(35)
E B [K (-L)s"(-Is] (-1ss)
(30)
aK
The condition that Ap > 0 implies that P is invertible. The goal of recursion (33) is to approximate the term x" = p-1g. We have the following result.
where KL(-Il) is the Kullback-Leibe divergence, wt is the NPG direction F(Ox)- VV J(0k,, n² is the optimal policy,
7

---

A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
Theorem 2. Consider the recursion (33), Assume that the conditions (34), and (35) hold. Also, let öp S Xr/8, and 3 2log H. sufficiently large.
where St. Sö = [AA( byy and By defines the conditional expectation given the history up to the outer loop instant k. Moreover, given Ok. we also have
A. The following relation holds whenever H. is
(e)
Ek
b MMLM u.khh
(0k: 5x0 - -VoJ(ON)
E
100
x11
Ro H
E
[1TH - 2" 2²11"]
+
+ R1
S 0 <0(ou, emix Tmix + +
H²
where 0i, - 0(09 Ex [|Ex|1 and 8 is given as
where Ro - 1o No03 + op'
R = [ A²
6g], and (.) hides logarithmic factors of H. Moreover.
u = O (G? [|Ex -EII? Gleapp)
[[ - x²1
E ro] x²'
(((R)
Combining Lemma 2 and Theorem 2, we arrive at the fol- lowing results.
H²
+0 (Ap26) E 1|100
x= x=1]²] O + +R))))
Theorem 3. Consider the NPG-finding recursion (17) with 2log H. and T maxx = H² If all assumptions in Theorem hold, then for sufficiently large c3, H
y= uH
where R₁ = >
We shall now use Theorem 2 to characterize the estimation errors in the NPG-finding subroutine and average reward and critic updates.
E& [| - will
H² T2 wāll + +
1 mix
/ 1r H
δ Gieglmix 1P
+ 0 EE 115x - E211 + capp)
5.3. Analysis of NPG-Finding Subroutine
Additionally, we also have
In the NPG finding subroutine, the goal is to compute w [
An estimate of F(Os) is given by u,k,h (0x). and that of the policy gradient (Ok) is given by ÍMLMC (0x, Ex) (see (21)). One can establish the following inequalities invoking the properties of the MLMC estimates.
Gitmixx 112112
W will?)
[B - -wßl?=
ÁMLMC(0e)
F 2 c7 o
|IBalEe] -E112 2 + capp
G En
+0
|lEx - -S(IP] p²H2
Lemma 2. Fix an instant of the outer loop in Algorithm
Given (0k. (x), the MLMC estimates defined in (21) satisfy the following bounds Vh E (H.... 2H ,H. 1} provided the assumptions in Theorem hold.
Gffmix
+0
{ir GG + H²H2
5.4. Critic and Average Reward Analysis
Eg,h AMIMO(B (8w) F(Ow) || < 0 (G*tmixTmm T m
(a)
The goal of the recursion (16) is compute the term & [Av (Ox))- (0x). An estimate of (0k))) is given by A. while that of by (0%) is given by ÍMLMC (see (25)). Similar Lemma 2, we have the following result.
(b) Eg,b [MMMM (0x) F(BL)] 1²]
0 (Gi/mix log T max)
(c)
Eenh BMLMC (Os, [x) - (ow)
Lemma 3. Given the parameter Oz, the MLMC estimates defined in (25) obey the following bounds provided the as- sumptions in Theorem 1 hold.
s0 30 Timd max 82
(d) Eg
MMLMC 1LMLMC(0L. (0.,E)) VoJl(h) aukkh
(a) |EE
AMLMC]
Av(0e)) 50 (02g( (cgtmix 7 max
Aow(w) 17
0 (ou, mmix log Tmax + 82 u.k)
(b) Ex,
AMLMC v,k,ts
5 (gllmix log Timax)
where Ea.h defines the conditional expectation given the history up to the inner loop step h (within the kth outer loop instant), of = 0 [R 11 and
(c) E
jMLMC]] - by (Bw) 2
12
00 (c3tmmi Tinix
Pv.k.
(d) EgEh
1MMMMC V.R.A
- by bL 00 50(c)tmns /mix log T Tmaxx)
82 ====0 =0 0 OoR
1lEx-
-E2l1 GREapP)
- where h E 10 .H - 1} and Ex, is interpreted in the same way as in Lemma 2.
8

---

A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
Lemma' 3 and Theorem 2 lead the following.
approximation, and distribution shift. The Journal of Machine Learning Research, 22(1):4431 2021.
Theorem 4. Consider the recursion (25), Let max = H²,
3 4log H If all assumptions of Theorem I hold, then the XH
Agarwal, M. and Aggarwal, V. Reinforcement learning for joint optimization of multiple rewards. Journal of Machine Learning Research, 24(49):1-44 4-1,, 2023.
following is true for sufficiently large cB, H.
E& [[lEx
53
37 1166
EX1l + O
Catmix x
m c H
Calmix
Agarwal, M., Bai, Q. and Aggarwal, V. Concave utility reinforcement learning with zero-constraint violations. Transactions on Machine Learning Research, 2022.
|| [xx]]]] - 12 & O
E21l" + H
Combining Lemma 1, Theorem 3 and 4, we establish Theo- rem 1. We would like to emphasize the importance of the term 0g in Theorem 2. A naive analysis would have resulted in a worse upper bound in Theorem 2 that replaces 83 with 62 Such degradation in Theorem would have resulted in convergence rate of ((3)) opposed to cur- rent bound of (33)) Finally, it is to be mentioned that our convergence bound does not depend on |S), thereby enabling its application to large state space MDPs as long as mix is finite.
Agrawal, S. and Jia, R. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. Ad- vances in Neural Information Processing Systems, 30, 2017.
Al-Abbasi, A. O., Ghosh, A., and Aggarwal, V. Deeppool: Distributed model-free algorithm for ride-sharing using deep reinforcement learning. IEEE Transactions on Intel- ligent Transportation Systems, 472
Bai, Q., Bedi, A. S., Agarwal, M., Koppel, A., and Ag- garwal, V. Achieving zero constraint violation for con- strained reinforcement learning via primal-dual approach. Proceedings of the AAAI Conference on Artificial Intelli- gence, 3663969,,,,, Jun. 2022.
6. Conclusions
This work presents the Multi-Level Monte Carlo-based Nat- ural Actor-Crite (MLMC-NAC) algorithm for addressing average-reward reinforcement learning challenges. The pro- posed method achieves an order-optimal global convergence rate of ((1 (TV significantly surpassing the state-of-the- art results in this domain, particularly for actor-critic ap- proaches with general policy parametrization.
Bai, Q., Mondal, W. U., and Aggarwal, V. Regret analysis of policy gradient algorithm for infinite horizon average reward markov decision processes. In AAAI Conference on Artificial Intelligence, 2024.
Beznosikov, A., Samsonov, S., Sheshukova, M., Gasnikov, A., Naumov, A., and Moulines, E. First order methods with markovian noise: from acceleration to variational inequalities. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Building on this line of work, Xu et al. (2025) investigated the impact of constraints. Our analysis considers a linear critic, a limitation that has been relaxed to neural critics in discounted settings (Gaur et al., 2024; Ganesh et al., 2025a). However, extending this relaxation to the average reward setting remains an open problem.
Chen, X. and Zhao, L. Finite-time analysis of single-timescale actor-critic. In Thirly-seventh Con- ference on Neural Information Processing Systems, 2023. URL https: petttps://pperreeee opw.revieweeeeeeeeeeeeeeee net. forum? id= 3UUSSKUK,
Acknowledgement
This work was supported by the Anusandhan National Re- search Foundation (ANRF), India, through the Overseas Visiting Doctoral Fellowship: the Office of Naval Research under grant N00014-23-1-2532. and Cisco Systems, Inc.
Dorfman, R. and Levy, K. Y. Adapting to mixing time in stochastic optimization with Markovian data. In Proceed- ings of the 39th International Conference on Machine Learning, Jul 2022.
Impact Statement
Duchi, J., Hazan, E., and Singer, Y. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
The goal of this paper is to advance the current understand- ing of the field of Machine Learning. We do not see any potential societal consequences of our work.
Fatkhullin, I., Barakat, A., Kireeva, A., and He, N. Stochas- tic policy gradient methods: Improved sample complexity policies. In International Con-
References
for cahher-oon-eeeeeee ference on Machine Learning. pp. 9827 9869. PMLR, 2023.
Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G. On the theory of policy gradient methods: Optimality,

---

A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
Ganesh, S., Chen, J., Mondal, W. U. and Aggarwal, V. Order-optimal global convergence for actor-critic with general policy and neural critic parametrization. In Pro-
Information Processing Systems, volume 33, pp. 16666- 16676, 2020.
Panda, and Bhatnagar, S. Two-timescale critic-actor for average reward mdps with function approximation. Pro- ceedings of the AAAI Conference on Artificial Intelli- gence, 39(19): (990))19911-119111 Apr. 2025.
ceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), July 2025a.
Ganesh, S., Mondal, W. U., and Aggarwal, V. Order-optimal regret with novel policy gradient approaches in infinite horizon average reward MDPs. In The 28th Interna- tional Conference on Artificial Intelligence and Statistics, 2025b. URL https: http:///pppeeeeeeeieeeeem wwt.:/rrtrotrt 1d=2JwMEQ6WSP.
Papini, M., Binaghi, D., Canonaco, G., Pirotta, M., and
Restelli, M. Stochastic variance-reduced policy gradi- ent. In International conference on machine learning. pp. 4026-4035, 2018.
Patel, B., Suttle, W. A., Koppel, A., Aggarwal, V., Sadler, B. M., Bedi, A. S., and Manocha, D. Global optimal- ity without mixing time oracles in average-reward via multi-level actor-critic. In International Conference on Machine Learning, 2024.
Gaur, M., Bedi, A. S., and Di Wang, V. A. Closing the gap: Achieving global convergence (last iterate) of actor- critic under markovian sampling with neural network parametrization. In International Conference on Machine Learning, 2024.
Puterman, M. L. Markov decision processes: discrete stochastic dynamic programming. John Wiley Sonn, 2014.
Gonzalez, G., Balakuntala, M., Agarwal, M., Low, T., Knoth, B., Kirkpatrick, A. W., McKee, J., Hager, G., Aggarwal, V., Xue, Y., Voyles, R., and Wachs, J. Asap: A comi-autonomous precise system for telesurgery during communication delays. IEEE Transactions on Medical Robotics and Bionics, 5(1):66-78, 2023.
Suttle, W. A., Bedi, A., Patel, B., Sadler, B. M., Koppel, A., and Manocha, D. Beyond exponentially fast mixing in average- reinforcement learning via multi-level monte carlo actor-critic. In International Conference on Machine Learning, pp. 33240-33261 2023.
Jaksch, T, Ortner, R., and Auer, P. Near-optimal regret bounds for reinforcement learning. The Journal of Ma- chine Learning Research, 11:1563-16000 2010.
Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y.
Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
Kumar, N., Murthy, Y., Shufaro, I., Levy, K. Y., Srikant, R., and Mannor, S. Global convergence of policy gra- dient in average reward MDPs. In The Thirteenth In- ternational Conference on Learning Representations, net. forum?
Tamboli, D., Chen, J., Jotheeswaran, K. P., Yu, D., and Aggarwal, V. Reinforced sequential decision-maker for sepsis treatment: The posnegdm framework with mortal- ity classifier and transformer. IEEF Journal of Biomedical and Health Informatics, 2024.
2025. URL /ttttp::/operreete id- 2PRpcmJecx.
Liu, Y., Zhang, K., Basar, T., and Yin, W. An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods. Advances in Neural Information Processing Systems, 33:7624-7636 2020.
Wang. L., Cai. Q. Yang, Z., and Wang. Z. Neural pol- icy gradient methods: Global optimality and rates of convergence. In International Conference on Learning Representations, 2019.
Mondal, W. U. and Aggarwal, V. Improved sample com- plexity analysis of natural policy gradient algorithm with general parameterization for infinite horizon discounted reward markov decision processes. In International Con- ference Artificial Intelligence and Statistics, pp. 3097- 3105. PMLR, 2024.
Wang. Y., Wang. Y., Zhou, Y., and Zou, S. Non-asymptotic analysis for single-loop (natural) actor-critic with compat- ible function approximation. In International Conference on Machine Learning, 2024.
Murthy, Y., Moharrami, M., and Srikant, R. Modified policy iteration for exponential cost risk sensitive mdps. In Learning for Dynamics and Control Conference, pp. 395- 406. PMLR, 2023.
Wei, C.-Y,, Y., Jahromi, M. J., Luo, H., Sharma, H., and Jain, Model-free reinforcement learning infinite-horizon average- markov decision processes. In Interna- tional conference on machine learning, pp. 10170-10180. PMLR, 2020.
Nagaraj, D., WU, X., Bresler, G., Jain, P., and Netrapalli, P. Least squares regression with markovian data: Fun- damental limits and algorithms. In Advances in Neural
Wu, Y. F., Zhang, W. Xu, P., and Gu, Q. A finite-time analysis of two time-scale actor-critic methods. Advances
10

---

A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
in Neural Information Processing Systems, 33:17617- 17628, 2020.
Xu, P., Gao, F., and Gu, Q. Sample efficient policy gradient methods with recursive variance reduction. Interna- tional Conference on Learning Representations, 2019.
Xu, T., Wang, Z., and Liang, Y. Improving sample com- plexity bounds for (natural) actor-critic algorithms. Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Process- ing Systems, volume 33, pp. 4358-4369. Curran Asso- ciates, Inc., 2020.
Xu, Y., Ganesh, S., Mondal, W. U., Bai, Q. and Aggarwal, V. Global convergence for average reward constrained mdps with primal-dual actor critic algorithm. arXiv preprint arXiv:2505. 15138 2025.
Zhang, J., Ni, C., Yu, Z. Szepesvari, C., and Wang, M. On the convergence and sample efficiency of variance- reduced policy gradient method. In Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Ad- vances in Neural Information Processing Systems, 2021a
Zhang, S., Zhang, Z., and Maguluri, S. T. Finite sample analysis of average-reward td learning and leaarrnin. In Advances in Neural Information Processing Systems, volume 34, pp. 1230-1242, 2021b.

---

A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
A. Proof of Lemma 1
The proof of the lemma is inspired by the analysis in (Mondal & Aggarwal, 2024). The major distinction is that the bound derived in (Mondal & Aggarwal, 2024) applies to the discounted reward setting, whereas our derivation pertains to the average-reward case. We begin by stating useful lemma.
Lemma 4 (Lemma 4, (Bai et al., 2024)). The difference in the performance for any policies ne and u is bounded as follows
(( - J(0) = Ex Eawxo(-le) [A (8,
(36)
Continuing with the proof, we have:
E Bxngg [L (=)s)
log (al+) TBe (als)
E Bond (a
(a)
G2
Bendi Bawx Vo log To, (als) (0k+1 - 0x)]
|10k+1 - 1x
2
= =a = Ea (-1b) Vo log no, (als) wis] Gza?
1|as|12
2
G2a²
a B. Ba (-1b) Vo log no, (als) wi] + a Bandr Eawr (1o Vo To (als) (wx - -ww]]
2 || ||
= =aIJ- [(k)) Brndr Baxx (-18) Vo log no, (als) wi] - alJ J(os)]
G2a²
+ a Exndi Eawr (1s) /o log To, (als) (we - wi]] 2
1|wx1
① alj" ](0k)] + Boaa Bann (1sa Ve log no, (als) wh - A ())
+ a Bande Hown" (-16) (-1)) Vo log Te (als) - (wx- - ww]]] G2a² 2
||wx|2 1
2
(c)
2 a[J" - J(Ok]] -ay E Bender Eawo (10) (To log To, (als) w - AT (s)
27
Gza²
+ a Bond' (-)x) Vo log me (als)- (we -
||wx|?
2
(
_ alj" - [(0a] av Ebias Ebias + a a. Eynar Bawr'( (-le) Vo log Te, (als) (wi - ww)] G2a² 2 || 112
Here (a) and (b) follow from Assumption 5(b) and Lemma 4, respectively. Inequality (c) results from the convexity of the
function f(x) = x². Lastly, (d) is a consequence of Assumption 4. By taking expectations on both sides, we derive:
E E Be-ar [L (-1s) (+1s) - KL(T" (-1s) Te, (T.)) (-1s))]]
2 a[j' - [[x a. CCiiu
Gza² 2 E
+ a E E Bard E Ean (1s) Vo log To, (als) (Ex[an) wi]l]
[[[wx] [|]]
2
2 a[J' -Q['-E[J[( [[+{a) Ebias
(37)
Gza² 2
a E go E EawT Vo log Tex (a|s)]ll Ex[wa] [Ill]]
|| [|a]
Gza²
a||* - (0,)]] abiis aG1 E || wl)ll
E
2
where (a) follows from Assumption 5(a). Rearranging the terms, we get,
J [[)(( S V + G1 E [Ex[wu]] - wl)l + G2a E w1
(38)
1 + E [E (< (O. (-1s)) - KL((=' (-1s) (TLE (-1s))]
12

---

A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
Adding the above inequality from k 0 to K 1, using the non-negativity of KL divergence, and dividing the resulting expression by K, obtain the final result.
B. Proof of Theorem 2
Let 9h~ = PR 9h- To prove the first statement, observe the following relations.
| x= 2²1
22h Bgh- x²1
1T x²1 x²112 23 x², ghh) + 3- llgh 1|2
| - x #112 - (3 - -x',PP' P(rn - x²') x²)) - -23(zn - xx, 9h - P(x x²)) + 1 19n
| x² 112 - 23Ap|110 x² --2- 23(21 x², P(ann x²))
2.3 11gn P(xn x²") x²²)1² + 2 P( - x²)) x12
(6)
11 - x= 1|2 - -2332 1: - x² 1²1 23( - x²' 9h - P(an - x²))
+ 1,939llnn P( x x²)11 + 2A || x=1 1²?
where (a) and (b) follow from ApI + and ||||| S Ap. Taking conditional expectation Es, on both sides, we obtain
En | - ==-11 < 2BXp + 22 )| x=112-2,3 -23(tnn - xx,,, En Jgn - P(æn x²)}}
+ 2 En |19h P(un x1))1
(39)
Observe that the third term in (39) can be bounded as follows.
11gh P(xn-
-² = [(p,, (In x²) + (Pr P)'* + (g - 91
< P - 111 x²11 + + Ph, - || 112 + 311g 4: 1|?
< P Pl[/|1z3 x²1 + +3A,²^,1117, A311 -PI2 + 311g q
where the last inequality follows from ||001] = |||||~1yp ua|l - Ap 2A3 Taking expectation yields
EA l1gb P( - =x')1² < 3 E, PPn 11| x 33 P P11 + 3 EA 1l.. - -gll2
S 3 2 ||
- x 112 +3Ap221005 + 30
(40)
The second term in (39) can be bounded as
Ap || - -x=1' 112 + Ap
- (2h x,, En Ion - P( - =)')]> -
| 19t. - P( - x² 211
4
Ap
1
{ [EnlPP]] P] xn { En [in]
| x0'l" 112 +
Ap
XP
28%
|| 1|2 + +252
|| - 2011 +
4
Ap
Ap
48% || - x² 1|2 + 488Ap" 22 28
| x= 112 +
(41)
4
Xp
where the last inequality follows from
||=11|2 || ||
< xp² 233
Substituting the above bounds in (39).
EA [||= - =111 < (1
33Ap
8367
43 213 + +6,
+
+ 6. + 23 || == +
[20
2
Ap
Ap
+ 6 [X 2>² 2200 2
13

---

A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
For 8p Ap/8, and B S Ap/(4(603) + 22 we can modify the above inequality to the following.
48 Ap
Ball x² x s (1 -3p) || - ==I
[263^p?A,] + +5 + 633 [Xp A2p + t
Taking expectation on both sides and unrolling the recursion yields
E||lH - x=11
H
4
< (1 - 32p) E 1-00-=111-- 2²12+
+
Σ
(1-
3xp)*
A2+ + + [AP A222 +o2
Ap
h=0
1
4,3
I <exp (-H3Ap)
B Io x= 11 +
120 13 69 + 63 P1 1703 + +
BAp
Ap
exp (-H3Xp)
B B 1²2
+
4
[28
21² + 80 6 1
Set 21og to obtain the following result. ApH
E [1|xz--x'1 s
1 E [|
=0
+0
log
Ap Apt + xp
+ +Xp
+
A
(42)
H
Ro
R.
Note that, for consistency, we must have log H/H S X2/18(602 + 2A To prove the second statement, observe that we have the following recursion.
|| E [[ || - x² 1| = || [[ 3 B[mn] - x 11
= E[rx] - 1=1 23(E [ - x², E[gh.] + 33
= || [[rx] 1=2 - (3 - x²" P(E[zy) - x²)) 23(E - x², E(gn] - P(E[xr] - =x") + +B E[gh]1
|| [[ax)] - 11 23 |1 1-1 23 x", B[gn] P(E[2 - xx))
+ 2,33 [[gh] - -[[[==]== + - x111
(6)
< [[xn) 11 23Ap - - xx,, B[gg] - P(E[Er)] - x²))
+ + [[gn [[]]mm)=>'']+++2))) |B(ra]] 101
$ (1 2 2 || [[rx]] - 23 - -x","" R(gn]] - P(E[TN) - x²))
+ 2.3² [[ - P(E(xr) )²?
(43)
where (a) and (b) follow from Ap1 I < P and ||||| S Ap. The third term in the last line of (43) can be bounded as follows.
E [[gh]
P(E[xa] x²) 2²)11 E (Ph, P) (x) - = + (B[P)) P)x + (q E(q.1)
$ 3
[pr] P1| - =11 +3E [Ar P||2]
||01|2 + 3 114
EEq.
$ 3663
|||08
x= -01 + +3>=²1300 + 38%
(x)
K 359
E [1 x |1] O (Ro R1)
+3Pp 22226 + +33
where (a) follows from (42). The second term in the last line of (43) can be bounded as follows.
[E[ra] - x", En [B[o]] P(E[æz] x²) }}}
[[ - 12 +
|E[gu] - P(E[ - x²)ll
Ap
>p
[[ -x=" 11
82 E
|| - 211 + (Ro +Ri) A + +88
4
Ap
14

---

A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
Substituting the above bounds in (43), we obtain the following recursion.
3
[[ -x11 <
+
|| |[ x=1
2
+ 63
57
IE [1:0 x011 + + R1) + +
Xp
B (p/(4))), the above bound implies the following.
[[ ==1 1 - (1 BBp)
||
[ x² x=11
+ 63 B Ap
E 10000 - ==11 + Ri) +2p2A303 + + 5%
Unrolling the above recursion, we obtain
[[rm] 21 > - (Ap) E[zoo] x²11
H-1
+ Σ
6 61 - B\p) 3 3+ Ap
1
08
[| - 0
+ + Ri) AP==A303 + 82)
h=0
< exp (-HBXp) [[xo]]] - x²1' + Ap
87.
E [||000 - O =10) + R1)) + ~ク +
Ar
Substituting 3 = 2og H/ (Ap we finally arrive at the following result.
E[ x² x= 12= 2 B 1²1 + 6 (1 + 2 H
1
/1
[ |xp0%
E [1 x11 + 0 + Ri) Ri) } +
where R₁ = 2p218p2pp2 2 + 82] This concludes the result.
C. Properties of the MLMC Estimates
This section provides some guarantees the error of the MLMC estimator. This is similar to the results available in (Dorfman & Levy, 2022; Suttle et al., 2023; Beznosikov et al., 2023), although (Dorfman & Levy, 2022; Beznosikov et al., 2023) consider the case of unbiased estimates while our results deal with biased estimates.
Lemma 5. Consider a time homo-homogeneous, ergodic Markov chain (Ze)z20 with a unique stationary distribution dz and a mixing time tmixx Assume that Fz)) an arbitrary gradient and F(x, Z) denotes an estimate of F Let
Baz F(r 2)] [F(x))1 < 82 and |VF(F Zi) -EAt Par Z) 1 o² for all 2 1fQ Geom(1/2), then
the following MLMC estimator
29 g0-1) if28 S Tmax
9MLMC = =g" +
where g¹ 2 Σ VF Z.)
(44)
0,
otherwise
satisfies the inequalities stated below.
(a) EigMLMe] = Eig loo Ll TmnaJ]
(b) [()) - 90LMC [2] < 5 (02tmix log, Tmax + 62)
(c) [VF()) - E[gMLMc]]| < O (o2tmixTml mix + 62)
Before proceeding the proof, we state useful lemma.
Lemma 6 (Lemma 1, (Beznosikov et al., 2023)). Consider the same setup as in Lemma 5. The following inequality holds.
F(r, Z.) Edz [VF(r, Z)1 23!l [1|]]
Citmix o²
E
(45)
N
N
where N is a constant, C1 = 16(1 + 1, and the expectation is over the distribution of ( emanating from any arbitrary initial distribution.
15

---

A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
Proof of Lemma 5. The statement (a) can be proven as follows.
Looga Tiax
[[gMIMc] = Elgg) +
- Elg" g--1|
==1
[log Tmax
= [la") +
Elg' - -² = Elyy 1ogs Tmax
For the proof of (6), notice that
V F (2,, 2)] 9MLMel
2E
Edz [F 9 001
+ 22E 19MLMC - 90]]]]
2
Edz VF(x)] o 111
2 Σ
11oRa Timan
Pr[Q = j} 42 E |10s - -1-1
i=1
= 2
Bdz (x:))) 9 =1]
2 Σ
[loga Timnel
2 |1" 9و 111
< 2E
Bdx [F)(1))]
+
Logg Tmaa
2 I
F.,
FF(x, 7)] 8² 112
Baz IV 2)]1 +B |110
(0)
LioRa Tamall
2)-1 + 1 )
2 O
2
2
= o (02 logg Tmax)
where (a) follows from Lemma 6. Using this result, we obtain the following.
E [VF(())
9MLMC| []] 2 [VF(x) Ed, F 2)]1[] + 2E [Bd, VF(x. 2)] 9MMLMC1 [2]
0 to tmix log, Tiax + 8²)
This completes the proof of statement (b). For part (c), we have
FF(()= - E [9MLMC]l|
s 22[[=F(r) Edz [F 2)11 + [Bddz [V 2)1 - [MMLMM]1
< 28 +2 Edz F 2 loge T Fmox)) ||
20 o²
(46)
282 +
T Tiax
where (a) follows from Lemma 6. This concludes the proof of Lemma 5.
D. Proof of Lemma 2
Fix an outer loop instant and an inner loop instant h E (H.... .... .2. - 11. Recall the definition of Áu(Os,) .) from (20).
The following inequalities hold for any Og and Ah E x A S.
Eeg Auu(kk: 2)
(a) F(Ox), and Au Aa 2.h)) Ed Au((ks,)) 2) ? 2G
where Ea, denotes the expectation over the distribution of = (8, s') where (s, a) UTx s' ~ P(-Is, a). The equality (a) follows from the definition of the Fisher matrix, and (b) is a consequence of Assumption 5. Statements (a) and (b), therefore, directly follow from Lemma 5.
To prove the other statements, recall the definition of i (0z, : from (20). Observe the following relations for arbitrary
16

---

A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
OK Ek-
Esc (bu(Ox: (b) (Bx) = Eo [[r(s,a) mm - (Ø(s') - o(s), (k) Vor logno, (als) Vo.((R))
E8x { Mi
(a)
The + (0(s') o(s), Sa (E) Vox log (als) +
(m))((s) - (o(s), (t) + (6(5') - VTox(s') Von logno, (als)
E0
72
{ yaa (s') - mh + r(s.a) vana (5)
/oo Vo, logTo, (als) (oJ((Bk)
Eag
12
In (a), have used the notation that E% [nke GRl Observe that
I 2 (a)
o GG [[Ex - E2I1*) 1 ( o (Crtapp), and T2 (c)
(47)
where (a) follows from Assumption 5 and the boundedness of the feature map, while (b) is consequence of Assumption 5 and 2. Finally, (c) is application of Bellman's 's equation. We get,
Ee [u (Ox: Ek. 2)] (Bh) S Li, = O 1lEx -xll + Gicspp)
(48)
Moreover, observe that, for arbitrary thth AXS
| EA. 2th) Eoo
Eox (un(0k) Cu. 21) || (a) = -
(49)
where (a) follows from Assumption 5 and the boundedness of the feature map, ø. We can, therefore, conclude statements (c) and (d) by applying (48) and (49) in Lemma 5. To prove the statement (e), note that
(Oxs Sk. ])]]
(Oz) = EEg (rissoo - Ea[Tn] + (ō(s') ((s), [En[Sa]) Von log (als) Vol(Ox)
Eg
(a)
{
Ex (na) + (o(6') - (()), Ex - (Z) Vo, logno, (als) +
Edg
T1e
To
(o(s). + (o(s)), v (6) (67 logto, (a|s)
Ti
{ (ymes (s') mh r(s, -(s v (s)
+ Eøg
Vol log (a|s) voo((N))
T2
Observe the following bounds.
Toll 2 (a)
O
G [E [ -EII))
||Ti|] ( o (GeEap)) and T2 (c)
(50)
where (a) follows from Assumption 5 and the boundedness of the feature map, while (b) is consequence of Assumption
5 and 2. Finally, (c) is an application of Bellman's 's equation. We get,
Eo,
Es
Bu(Ok, Ex. Ex.2)) s)]l vo.( < 82 =o = (G
[[ Et' GREapP)
(51)
17

---

A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
Using the above bound, deduce the following.
Ex
BMLMC a.k,h (Ok, 5x)] (0x(
Es (oukk (0%, EN)] Eox Bx (ul(Ba Ek. 2) I]] + Bo.
Ex
Bu(Ok: Eas 2]] Vg. (0x)
(a)
1 2 En
BMMLMC (Oxs [x.] n,,kk
- Egg (o Sxs 2e, ||
+ + (
(M) I
(tmix + k..
where (a) follows from (51), Moreover, (b) follows from Lemma 5(a), 6, and the definition of ". This concludes the proof of Lemma
E. Proof of Lemma 3
Recall the definitions of (-) and (-) given in (23) and (24) respectively. Note that the following equalities hold for any 4z_
Es, (x) = (Ok). and Es, [Bu(2)] (0x)
(52)
where Ea,, denotes the expectation over the distribution of (s, a, 8') where (s ~ v s' P(-(s,a). Also, for any
2 = s') E S x A x S, we have the following.
|v(2) - Ical + [[((s) + ( -
- ca +3 =3+3=O(ca))
(53)
| 1 (csr(s. (s)))))(ss) (1) 1 ca + +1 Occa(c
(54)
where (a), (b) hold since [r(s; a)] s 1 and ||{()|| 11, E A. Hence, for any 2/th 8 A x S, we have
| - Es, [Av(=)]] (O()). and |(a(et*) Eo, [Bv())] s 50(3))
Combining the above results with Lemma 5 establishes the result.
F. Proof of Theorem 3
We first state an important result regarding ergodic MPDs. Lemma 7. Lemma 14, (Wei al., 2020) For any ergodic MDP with mixing time tmix the following holds for any policy
(A" a) = O (fmix), V(s,a)
If follows from Assumptions 5, 6, and Lemma 7 that
pl < F(0), ||F(O)] s GJ and |V) S O (Gitmix)
(55)
where 0 is any arbitrary policy parameter. Combining the above results with Lemma and invoking Theorem 2, arrive the following.
Ex ||W - will31 S
1
| w
+ (
-0
Ro H
R1
H
H | will + O(Ri) + ( Gitmix {llut - will" + + (22H2
(Ro + m)))
|R [wx] - will <
where the terms Ru; R1, Ri are defined as follows.
Ro 0 n 1 Cf + f4 GGtttin E& [|6a|1]] + G Ex [1E - -6211] 1 G
R1 0
[ (H-2 "G H -122 -2 Ex [1E6
1 - " Ex
[l[E - = + 1 CReapD)
R1 = 0
H
GG H -22 -2 Ex
[1
- |[E
- 1 H -2 R
18

---

A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach Moreover, note that
Es [1Ex|]]] s 2x [IEs=
- <tIl²] + + Ex
[|EE||]
(a)
EE1l + x -2 203 S o Ek ||Ex (Ex
where (a) follows from (57) for sufficiently large ca and the definition that E% [Av (0x1))0-11b -b (0k).. Hence,
Ex |lwx - wxll - H2 - - will +
1 H
G9 mix + 2 G2 })
+ c Ex [1Ex - =x1i] + +u G
[B [xx] - will & o G | [5x] - =ill + μi 2 Gapp
Gi/mnxx
{| will + u + bii 1xx [15E - E211" + + + + })
+ 112
This concludes the proof.
G. Proof of Theorem 4
We start with an important result on (0).
Lemma 8. For large enough cp, Assumption 3 implies that Av(0) = (A/2)/ where 1 is an identity matrix of appropriate dimension and 0 is an arbitrary policy parameter.
Proof of Lemma 8. Recall that (0) Eo [2)()] where Es denotes expectation over the distribution of (s, s')
where (8, a) u=0 8 ~ P(-(s,a) a). Hence, for any & [m, S]. we have
AA)( camp + +n5 Eg [o(s)] C Es -(''))
(a) 2 ca72 - |1I1 + A I|
(56)
||11 min czu Vu(1- u) + A(1 u) (A/2) 115l [E[(0_]]
where (a) is a consequence Assumption and the fact that ||x())] S 1, E S. Finally, (b) is satisfied when C9 2 x - 1. This concludes the proof of Lemma 8.
Combining Lemma 8 with (52), (53), and (54), we can, therefore, conclude that the following inequalities hold for arbitrary & whenever ca 2 A + V x
1.
< (0,)l S Oca)), and ((6 S O(cs)
(57)
Utilizing the above result with Lemma and invoking Theorem we arrive at the following.
Es [IEA =211]] <
- H2
| - Ei 1| + +
Ro H
+ Rτ R.).
Es En [Ea] - [2ll?]
$ - ||S =|| + (RR)) +
Cgtmix
H² [|56 E 12 +
0 O (R)++R))))
where the terms Ro, R1, Rí are defined follows.
Ro = δ (Y (x- + 20 c2tmix) = Ō (A--3a) -33
Ri = 0 -H-22 x1 M mmix + 2-2 = O (H-2x cglmmx))
Ri 0 H x cot mix
2 22 0 (H-2 - c/ mnix))
19

---

A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach Hence, we have the following results.
Eg |1Ex
521??
1
1158
EEll
+0
cstmix X+H
H²
E [Ea] EEIl 2 o
EEl??
+ 0
\ 112
This concludes the proof of Theorem 4.
H. Proof of Theorem
Recall that the global convergence of any update of form ox+1 = O2 + awn can be bounded as
G
aG2 [1I [wx] wFll
K
J E[J(O+))
S Ebiis +
Σ
E
1la - will
K
K
k=
(58)
Opp 2
K-1
+
E VoJ
+
aK E Bondi [K[(T" (+|ss'' (+|s))].
K
km0
We shall now derive a bound for
K [0x()
K-1
Given that the function J is L-smooth, we obtain:
L
J(Ox+1) J(0e) + (VoJ(0s) 0x11 - 0k)
|0 - 0x11
2
-((b)) (V a²L
|up1?
2
= -((x) + a (Vo wB) +a (VeJ(Ok), -Wh) a²L | wt + will
(0)
2 ((0+) + ( (0+), F(O)) - voJ(ON)) + (Ve)(Os), - -wf)
a² L/LW wfll a² 2!
( J(Ok) + a [ +a (V [(x) w w/) a²Illux wBll2 a² a²[||Wi|12
G7
-((O))+ + 2G
VoJ(0,))]
2G [o))) 12 2G (VoJ(OE), - wk) Gill - - (59)
021.)
1l18 -22 221111111
2
/aG2 2
-((()) + a
a [oJ((1))12
[oJ((E) + GR(u - w2)11
+ aZI ||l - will
2G
20
a² L ||
aG?
2(Ok) + 2G
V VoJ(0.)]1
+ +a²l
||w2 - -wll
2
(c)
TZT.) 2 J(8k) + 2G 12
+ +o2l. (a0d) 2
(oGf
[[o](())122
| -w8l?
where (a) use the Cauchy-Schward inequality and the definition that wt = F( Relations (b), and (c) are consequences of Assumption 5(a) and respectively. Summing the above inequality over (0..... K - 1), rearranging
20

---

A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
the terms and substituting a
we obtain
nº2
J(Ok) - -J(00)
-12
112
16GHL )
K-1
Σ
[o
1
+
Σ
1ook
will?
L
K
K
8L
K
==
==0
(60)
(0)
2
122
K
+
+
||wk - will
K
8L
16G
K
k=
where (a) uses the fact that J.) is absolutely bounded above by 1. Inequality (60) can be simplified as follows.
K K-1
32LG4 K
(2GH
K- 1
[VoJ(0))13)
+
+1
w
(61)
122
K
Now all that is left is bound EE ||we - w and [[Wx[ will Assume St
0, wk. From Theorem 4, we have
caglmix X
Cg/mmx X
Ex
[1Ex [t10] - H²
||E%]1
+
(a)
O
(62)
|[ - Et1l s o
m2/mxx
1|E211
+ o
LB 22
mix
(b)
O
CB mix
12
(63)
X²
H2
16
00 () 10(0002 22))) (1,00)))0000000''==000000000)000
The relations (a). (b) are due to the fact that ||=]|| = [IA)0)))]))
where the last inequality is
consequence of (57). Assume w = O, Vk. We have the following from Theorem 3.
Ek [|L4 - will" - 2
1
|
+ +
G
+
-GHc - }) + # GHO
Ex
||Ex - -Ex1?)
+ capp)
H
(a)
G9Pmmi
1
})
G9
cl/mix
122
+ +
H
G9 + ki 22 -2 GR 2
c3 fmix
+
112
0
A+H
+ Capp
- })
G7 0 (Capp)
G343 Giig mix +
x
Ghoftmmix moncstms))
(64)
H
12
(m- where the last inequality follows from Assumption 5, 6, and Lemma 7. We also apply (62) to prove (a) whereas (b) is established by retaining only the dominant terms. Theorem 3 also states that
Inequality (a) utilizes the fact that || = ||
S 50
[w]] wIll S O (M (M ( [IENEEN E012 + μ (REapp)
Gilmix
+
+
[|wg|| + 1 -2 GGPlmix Es [|LA - -5213)
+ p G mix + + - 222--22cglmi
12
G G
G2 112 tapp )
+ 1 1u-60 mnxx + 1 22 29 mix 1)
+ +
H2 11 GG
In3
1 H2
1 GG10 mix + xx 6 G9
mix + +
mix 1)
+
Gi 0
((app)
(65)
112
where (a) is a consequence of (62), (63), and the upper bound || < 0 (p-
(p-2G derived carlier. Incquality (b)
retains only the dominant terms. Combining (58), (61), (64), and (65), we arrive at the following.
K
( 1
G?
J K
[[)(O=)) S Veblae +
G + - Gfestt mix + x2xxxricptmix
0 (VEap))
H
/
K=
n G²
1
1)
G T.
+ 1
G
G2
H
m
mix
+
412
0 (Eupp)
+
1u2KK
(66)
21

---

A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
We get the desired result by substituting the values of H, K stated in the theorem. We want to emphasize that the Gi factor with the Capp term is standard component in actor-critic results with linear critic (Suttle et al., 2023; Patel et al., 2024). However, this factor is often not explicitly mentioned in previous works, whereas we have included it here.
22


Reviews:
[{"review_id": "y26eOhJPdL", "reviewer": "Reviewer_EoWh", "summary": "This work considers the average-reward RL setting with general policy parametrization. The authors improve over the state-of-the-art global convergence guarantee from a rate of $T^{-1/4}$ to $T^{-1/2}$ without requiring knowledge of the mixing or hitting times. This is done by adopting a multi-level MC procedure to estimate the relevant quantities and through a tighter analysis of the derived estimates.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Concerning the table, the authors state that their approach works for infinite states and actions, and similar claims are made for some of the related works. However, by inspecting those works, it appears that their results are defined with respect to large but finite spaces. Can the authors comment on this?\n\nWe agree that some related works (NAC-CFA and MAC) assume large but finite state spaces, and we have mistakenly given them more credit by stating that their conclusions extend to infinite state spaces. We will make changes in the revised paper accordingly. In this context, we want to emphasize that our work does apply to infinite states and action spaces, and there is no mistake in that claim. \n\n\n> Concerning the weaknesses, the authors do not properly highlight the technical novelty in terms of theoretical analysis. Indeed, this work shares many similarities both in terms of assumptions and in terms of methods with the one of Patel et al. (2024). I believe that the work may benefit from a clearer comparison between the current work and the one just mentioned.\n\n\nThe assumptions used in this work are commonly used in the literature and thus are similar to those used in multiple works including (Patel et al., 2024). \n\n Although our methods bear *some* similarities with that of (Patel et al., 2024), there are multiple novel components in the analysis that allow us to establish an order-optimal convergence rate of $\\tilde{O}(T^{-1/2})$ for average reward MDPs without the knowledge of mixing time, a feat achieved by no other work in the literature. While existing AC analyses (including that in the cited paper) apply relatively loose bounds, we refine the analysis to get sharper results. The first step towards this goal is to establish that the global convergence error is bounded by terms proportional to the bias and second-order error in the NPG estimation (Lemma 1). In prior AC works (including the cited paper), a coarser bound was used instead of the NPG bias that led to an error of the form $\\mathbb{E} ||\\xi_t - \\xi^\\star||$ in the global convergence bound where $\\xi_t$ is the critic estimate at time $t$ and $\\xi^\\star$ denotes the true value. Utilizing Lemma 1 and Theorem 3, our analysis refines this term to $||\\mathbb{E}[\\xi_t] - \\xi^\\star ||$, which can be significantly smaller than the previous estimate. It is to be noted that bounding $||\\mathbb{E}[\\xi_t] - \\xi^\\star||$ remains challenging due to Markovian sampling.  Interestingly, we observe that both critic and NPG updates can be interpreted as linear recursions with Markovian noise.  Efficient analysis of such a linear recursion is another novelty of our paper. In Theorem 2, we obtain a convergence rate for a generic stochastic linear recursion. This, along with the improved error estimates, form a basis for Theorems 3 and 4, which finally leads to our desired result in Theorem 1. \n\nIn summary, improving the error estimates, recognizing the NPG and critic updates as linear recursions, and performing a sharp convergence analysis of a general stochastic linear recursion are the novel cornerstones of our analysis. \n\n>Another weakness is the absence of numerical simulations.\n\nThe focus of the paper is obtaining the first theoretical result for a state-action space size independent global convergence rate of $\\tilde{\\mathcal{O}}\\left(T^{-1/2}\\right)$ for general parameterized policies in average reward infinite-horizon MDPs, using a practical algorithm that does not require the knowledge of mixing times. Evaluation of this work on some practical applications is left as future work.", "claims_and_evidence": "The claims made in the submission are clear and supported by theoretical results.\n\nConcerning the table, the authors states that their approach works for infinite state and actions, and similar claims are made for some of the related works. However, by inspecting those works, it appears that their results are defined with respect to large but finite spaces. Can the authors comment on this?", "methods_and_evaluation_criteria": "No experiments were presented in the work.", "theoretical_claims": "I checked the proof outline in Section 5 which seems correct to me.", "experimental_designs_or_analyses": "No experiments.", "relation_to_broader_scientific_literature": "The paper presents an improvement in terms of global convergence guarantees with respect to state-of-the-art approaches. A similar convergence result was achieved in Ganesh et al. (2024) but in a slightly different setting with finite state and actions and knowledge of the mixing time. \nA work closer in terms of assumptions and setting is the one from Patel et al. (2024) but achieves a worse convergence rate of $T^{-1/4}$.", "essential_references_not_discussed": "In my opinion, the related literature has been thoroughly discussed.", "other_strengths_and_weaknesses": "Among the strengths of the work, I mention the newly achieved result in terms of convergence for the considered setting without knowledge of the mixing time and with infinite state and actions.\n\nConcerning the weaknesses, the authors do not properly highlight the technical novelty in terms of theoretical analysis. Indeed, this work shares many similarities both in terms of assumptions and in terms of methods with the one of Patel et al. (2024). I believe that the work may benefit from a clearer comparison between the current work and the one just mentioned.  \n\nAnother weakness is the absence of numerical simulations.", "other_comments_or_suggestions": "See above", "questions_for_authors": "See Sections above", "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": "fV48CKdrrN", "reviewer": "Reviewer_8Gaz", "summary": "This paper studies the convergence of Actor-Critic algorithm in average reward setting of reinforcement learning. The paper proposed a multi-level Monte-Carlo based natural actor critic algorithm which achieves a $\\tilde{O}(1/\\sqrt{T})$ global convergence rate to a neighborhood of the optimal policy, where $T$ is the horizon length of the sampled trajectory.\n\n### Update after rebuttal: I appreciate the authors’ effort in rebuttal. Although some of my concerns have been addressed, the remaining concern is with regard to the trajectory length. Throughout the paper and most of the rebuttal it seems to be $\\max\\(2^{Q_{kh}}, T_{\\max}\\)$. However, it was pointed out in the last reply to rebuttal comment that it was a typo. Various places (line 6, 11, 23) of algorithm 1 in the paper used max operator rather than min operator. It appears the paper can benefit from greater clarity in conveying the idea.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**(a) Sample Complexity**: We note that there is a misunderstanding here. The convergence rate and the sample complexity are two faces of the same coin, and one can be derived from the other, as long as the error metric is taken to be the same. For example, consider our algorithm that uses a trajectory of length $\\max\\\\{2^{Q_{kh}}, T_{\\max}\\\\}$ where $Q_{kh}\\sim \\mathrm{Geo}(1/2)$ for each $k, h$. It is easy to check that $$\\mathbf{E}[\\max\\\\{2^{Q_{kh}}, T_{\\max}\\\\}]\\leq \\mathcal{O}(\\log T_{\\max})$$\n\nSince we have taken the number of iterations of $k, h$ to be $K=\\Theta(\\sqrt{T})$ and $H=\\tilde{\\Theta}(\\sqrt{T})$, and $T_{\\max} = H^2 = \\tilde{\\Theta}(T)$, the expected number of state transition samples used by our algorithm is $\\mathcal{O}(KH\\log T_{\\max}) = \\tilde{\\Theta}(T)$. Theorem 1 exhibits that for such choices of parameters, our algorithm achieves $\\tilde{\\mathcal{O}}(1/\\sqrt{T})$ global error (up to some additive factors of $\\epsilon_{\\mathrm{bias}}$ and $\\epsilon_{\\mathrm{app}}$). This establishes the convergence rate of our algorithm. Alternatively, if we want to ensure a global error of $\\epsilon$ (up to the additive factors stated before), the expected number of state transition samples required would be $\\tilde{\\mathcal{O}}(\\epsilon^{-2})$. This expresses the same result in terms of sample complexity.\n\nAlthough both notions are the same, the literature on average-reward MDP typically expresses the results in terms of the convergence rate, while the literature on discounted-reward MDP  typically adopts the sample complexity framework. The cited paper [A] analyzes a discounted-reward setup where the common metric is the sample complexity. The same article has also been cited in our paper (line 118), where we mention its global convergence rate to be $\\mathcal{O}(T^{-1/3})$. This is obtained from their equivalent sample complexity result of $\\mathcal{O}(\\epsilon^{-3})$. It is to be noted that even in the discounted MDP setup, there is no actor-critic algorithm that achieves $\\mathcal{O}(\\epsilon^{-2})$ sample complexity for general parameterization. \n\n\n**(b) Typo**: Thanks for pointing out the typo. We will correct it in the revised version.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Proposed method makes sense. However, there’s no empirical evaluations for the current version.", "theoretical_claims": "The reviewer didn’t check the correctness of the proofs.", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "The key contributions relate to the convergence performance of actor-critic algorithmic framework in RL, especially in the average reward setting. The paper proposed the model-free approach with order-wise comparable convergence result as the model-based approach.", "essential_references_not_discussed": "The work lacks the discussion of a very important branch of sample efficiency literature for example A and references within. Instead of convergence rate, which seems to only measure critic estimation and NPG estimation, the sample complexity is a more practical measure of complexity of as it represents the true resource consumption from the sample necessity. In the context of the current paper, the paper should include the policy update component. \n\n[A] Xu T, Wang Z, Liang Y. Improving sample complexity bounds for (natural) actor-critic algorithms[J]. Advances in Neural Information Processing Systems, 2020, 33: 4358-4369.", "other_strengths_and_weaknesses": "Strength: The paper studied the challenging average reward setting with finite-time convergence result. The analysis for this setting is in general non-trivial.\n\nWeakness: \n\nSample complexity perspective: it seems to measure the sample trajectory length for each pair of $k, h$ values. But in fact, the algorithm relies on $KH$ number of trajectories for the entire NAC algorithm to work. Based on Theorem 1, $KH = O(T)$ is large as well. This potentially poses sample inefficiency. Please elaborate or correct if the reviewer misunderstood.", "other_comments_or_suggestions": "Potential typo: Line 320, left column, left hand side of the inequality, subscript $d^{\\pi*}$ should be $\\nu^{\\pi*}$?", "questions_for_authors": "Please see the weakness point.", "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": "2WLUUhxCzE", "reviewer": "Reviewer_nDZw", "summary": "The paper establishes $O(\\epsilon^{-2})$ sample complexity for MLMC-NAC algorithm, claims to significantly improve existitng result of $O(\\epsilon^{-4})$.\n\nState-space independent result is not surpring as NAC (in exact gradient NAC case) is also state-independant.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**(a) Related Works**: Thanks for mentioning references [1] and [2]. We will include them in the revised version of our paper. In addition to [1], we will also include some other works on robust MDPs.\n\n\n**(b) Message for Practitioners**: Our algorithm is designed for large state and action spaces, with parameterized representations for both the actor and critic, making it well-suited for large-scale problems. While there are multiple practical insights, we highlight a few key ones below.\n\n1. **Sampling**: Many existing policy gradient-type algorithms assume access to a simulator capable of generating independent trajectories at will from a given state distribution (e.g., see [1], [2]). Typically called the i.i.d sampling, the procedure of generating independent and identically distributed trajectories greatly simplifies the algorithm design and analysis. However, for many practical applications, building an accurate simulator is itself a difficult problem. Fortunately, our algorithm works on a single trajectory, eliminating the need for a simulator.\n\n\n2. **Dependence on Unknown Parameters**: As stated in the paper, many previous works assume knowledge of mixing time and hitting time [3], [4], which are difficult to obtain for most applications. Our algorithm does not require the knowledge of the above parameters, thereby making it easier to adopt in practice.\n\n3. **Memory/Space Complexity**: Our algorithm is memory-efficient. One can verify that the memory complexity of our algorithm is $\\mathcal{O}(\\max\\\\{\\mathrm{d}, m\\\\})$ where $\\mathrm{d}, m$ are the sizes of the policy parameter, $\\theta$, and the critic parameter, $\\zeta$ respectively. It is to be noted that although the Fisher matrix, $F(\\theta)$ (and its estimates) require $\\mathcal{O}(\\mathrm{d}^2)$ space, one only needs to store quantities of the form $F(\\theta)\\omega$, $\\omega\\in\\mathbb{R}^{\\mathrm{d}}$, which need $\\mathcal{O}(\\mathrm{d})$ space.\n\n4. **Computational Complexity**: One way of computing the natural policy gradient (NPG) $\\omega_\\theta^* = [F(\\theta)]^{-1}\\nabla_{\\theta}J(\\theta)$ is first obtaining an estimate of the Fisher matrix $F(\\theta)$, and then directly using its pseudo-inverse to compute $\\omega_{\\theta}^*$. Such a method was adopted in [5]. We, instead, pose the problem of computing the NPG as a stochastic least square problem with Markovian noise. This eliminates the computationally expensive process of inverting a regularized Fisher matrix estimate (whose computational complexity is $\\mathcal{O}(\\mathrm{d}^3)$ where $\\mathrm{d}$ denotes the size of the policy parameter). It can be checked that the computational complexity of our algorithm for a given iteration instance $(k, h)$ is $\\mathcal{O}(\\mathrm{d}^2+m^2)$ where $m$ is the size of the critic parameter.\n\n5. **Convergence Rate**: Finally, the convergence rate of our algorithm is optimal in the horizon length, $T$. Practically, it indicates that our algorithm takes a relatively small number of training iterations to reach a certain accuracy. \n\n[1] Liu, Y., et al., An improved\nanalysis of (variance-reduced) policy gradient and natural\npolicy gradient methods. Advances in Neural Information\nProcessing Systems, 33:7624–7636, 2020.\n\n[2] Mondal, W. U. and Aggarwal, V. Improved sample complexity analysis of natural policy gradient algorithm with general parameterization for infinite horizon discounted reward Markov decision processes. International Conference on Artificial Intelligence and Statistics, 2024.\n\n[3] Bai, Q., et al., Regret analysis of policy gradient algorithm for infinite horizon average reward Markov decision processes. Proceedings of the AAAI Conference on Artificial Intelligence, 2024.\n\n[4] Ganesh, S. et al., Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite Horizon Average Reward MDPs. In The 28th International Conference on Artificial Intelligence and Statistics, 2025.\n\n[5] Xu, T., et al., Improving sample complexity bounds for (natural) actor-critic algorithms. Advances in Neural Information Processing Systems, 2020.", "claims_and_evidence": "Yes, seems so.", "methods_and_evaluation_criteria": "Yes, seems so.", "theoretical_claims": "I didn't verify the proofs.", "experimental_designs_or_analyses": "No.", "relation_to_broader_scientific_literature": "In my personal opinion, this NAC algorithm guanrantees are of theoretical and conceptual interests. I am not sure, this flavour of NAC algorithms are used in large scale problems.", "essential_references_not_discussed": "The paper doesn't cite  [2], establishing 1/T convergence rate for average reward case (for exact gradient case).\n\nThis recent work [1] also addresses the convergence of dynamic programming techniques in robust average reward MDPs and thus should be included in the related works literature.\"\n\n\n\n[1] @inproceedings{murthy2023modified,\n  title={Modified policy iteration for exponential cost risk sensitive mdps},\n  author={Murthy, Yashaswini and Moharrami, Mehrdad and Srikant, R},\n  booktitle={Learning for Dynamics and Control Conference},\n  pages={395--406},\n  year={2023},\n  organization={PMLR}\n}\n\n[2] @inproceedings{\nkumar2025global,\ntitle={Global Convergence of Policy Gradient in Average Reward {MDP}s},\nauthor={Navdeep Kumar and Yashaswini Murthy and Itai Shufaro and Kfir Yehuda Levy and R. Srikant and Shie Mannor},\nbooktitle={The Thirteenth International Conference on Learning Representations},\nyear={2025},\nurl={https://openreview.net/forum?id=2PRpcmJecX}\n}", "other_strengths_and_weaknesses": "Strengths:  Good theoretical result.", "other_comments_or_suggestions": "Suggestion: Presentation can be improved.", "questions_for_authors": "Question: How this MLMC NAC algorithm can be used in large scale problems.  Does this paper has any message for the practioners?", "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": "0nmEeEQUvt", "reviewer": "Reviewer_en8p", "summary": "This paper investigates average-reward reinforcement learning with general policy parametrization. The authors propose a Multi-level Monte Carlo-based Natural Actor-Critic (MLMC-NAC) algorithm and provide a finite-sample analysis.\n\nUpdate after rebuttal:\n\nThe authors have satisfactorily addressed all of my concerns in the rebuttal, including the clarification regarding the single-loop versus double-loop structure. Based on their responses, I am increasing my score to 3.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Markovian Noise**: We agree that applying projections or invoking the assumption of finite action space is common in the literature. For example, the MAC algorithm derives bounds using MLMC estimates from (Dorfman and Levy 2022), which assume a finite state space and a bounded domain, thereby necessitating a projection step in the critic update. Our analysis models the NPG and critic updates as stochastic linear recursions with Markovian noise, which we show to converge without invoking the above preconditions. A similar result can be found in (Beznosikov et al. 2023). However, their update differs from ours since we deal with biased estimates, which are not considered in the cited paper. \n\n**(Q1) Lipschitz Property**: Lipschitz continuity and smoothness of the function $J$ can be easily proven within the framework of discounted-reward MDPs (Lemma 2, Mondal and Aggarwal 2024). In this case, $L$ depends only on the discount factor. However, to the best of our knowledge, no such result is known in the average-reward case. We want to emphasize that nearly *all* papers analyzing general parameterized policy gradient methods for average-reward MDPs assume the stated properties of the $J$ function. These properties are expected to hold in practice since they ensure that a slight change in the parameter does not result in a large change in the $J$ function. In our assumption, $L$ is a constant that does not depend on other model-specific parameters.\n\n**(Q2) Step Sizes**: The values of the step sizes $\\beta$ and $\\gamma$ are given in Theorems 3 and 4, respectively: $\\beta = \\frac{4\\log H}{\\lambda H}$, and $\\gamma = \\frac{2\\log H}{\\mu H}$. Moreover, the value of $\\alpha$ is mentioned at the top of Page 20, line 1045: $\\alpha = \\frac{\\mu^2}{4G_1^2L}$. Observe that none of these parameters depend on the mixing time, $t_{\\mathrm{mix}}$, which is consistent with our claim that our algorithm does not require the knowledge of $t_{\\mathrm{mix}}$. In the revised version, we will explicitly state the values of these parameters in Theorem 1.\n\n **(Q3) Regarding $\\Lambda_P$ and $\\Lambda_Q$**: The terms $\\Lambda_P$ and $\\Lambda_q$ in (35) are parts of Theorem 2 that analyzes the convergence of a general stochastic linear recursion (SLR). Specifically, Eq. (35) forms a precondition for Theorem 2. We recognize that both NPG and critic updates can be formulated as SLRs. Moreover, these updates satisfy a precondition similar to (35). In particular, (53) and (54) allow us to choose $\\Lambda_P=c_\\beta+3$ and $\\Lambda_q=c_\\beta+1$ for the critic update while (55) dictates $\\Lambda_P = G_1^2$ and $\\Lambda_q = \\mathcal{O}(G_1t_{\\mathrm{mix}})$ for the NPG update. Note that, although $\\Lambda_q$ for the NPG update is dependent on $t_{\\mathrm{mix}}$, it is not used as an input to our algorithm, thereby maintaining the claim that our algorithm does not require knowledge of the mixing time. \n\n**(Q4) On Two-Timescale Approach**: We emphasize that no algorithm (be it single- or two-timescale) exists in the literature that achieves the optimal convergence rate of $\\mathcal{O}(1/\\sqrt{T})$ for average-reward MDPs with general parameterized policies via Markovian sampling. Our natural actor-critic-based algorithm achieves this goal, and that itself is a contribution worth highlighting.\n\nSecondly, the algorithms mentioned by the reviewer are not single timescale. We note that the paper NAC-CFA (https://arxiv.org/pdf/2406.01762) mentions (page 5) that ``Here, the AC and NAC algorithms in Algorithm 1 are single-loop, single sample trajectory and two timescale.\" Similarly, the MAC algorithm is also two timescale since the critic loop has an order-larger step size which makes the algorithm two timescale. Thus, we note that both the mentioned algorithms are two timescale. We will mention this in the paper and enlist designing a one-scale algorithm as a future work.\n\n**(Q5) Novelty**: Our main contribution is designing an algorithm for average-reward MDPs that achieves the optimal $\\mathcal{O}(1/\\sqrt{T})$ rate for general parameterized policies with Markovian sampling. This is a contribution worth highlighting because no algorithm, be it single- or two-timescale, achieves this feat. Moreover, as previously pointed out, all known actor-critic algorithms on average-reward MDPs with general parameterized policies are all, to the best of our knowledge, two-timescale. In summary, we respectfully disagree with the reviewer's stance that not being a single-timescale algorithm is a good enough reason to discount the merit of our work. \n\nThe optimization literature teaches us that single-timescale algorithms typically develop based on the intuitions provided by two-timescale algorithms. We are, therefore, hopeful that the intuitions provided by our algorithm will pave the way to designing the first single-timescale actor-critic algorithm for average reward MDPs with general parameterized policies. We will mention this as a future work in the revised paper.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths:\nThe authors propose a Multi-level Monte Carlo-based Natural Actor-Critic algorithm that achieves a global convergence rate of $\\tilde{O}(1/\\sqrt{T})$. The algorithm eliminates the need for knowledge of mixing times. In addition, the finite-sample analysis provided in the paper extends to infinite state and action spaces. \n\nWeaknesses:\nPlease refer to Question section.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "My main concern is about the high-level idea. Typically, addressing Markovian noise requires either a projection step or the assumption of a finite action space. However, it is unclear to me how the authors handle Markovian noise without either of these approaches. Could the authors provide a high-level explanation of their methodology?\n\nBesides, some other concerns are:\n\n1. To establish Theorem 1, the objective function $J$ must be $L$-Lipschitz w.r.t. $\\theta$. Can this property be directly inferred from existing assumptions? If not, this constitutes an additional assumption, and the authors should justify its reasonableness. Additionally, does $L$ depend on $|S|$, $|A|$ or $t_{\\rm mix}$? \n\n2. What step-size is used in Theorem 1? Is it a constant or decaying step size?  Furthermore, how does the step size scale with $T$ and the mixing time? This is a crucial aspect and should be explicitly stated in or before the theorem.\n\n3. What are the definitions of $\\Lambda_p$ and $\\Lambda_q$ in Eq.(35)? Can they take arbitrary values?\n\n4. The proposed algorithm operates on a two-timescale framework, as evident from Algorithm 1, where multiple critic updates (update on $\\zeta$ in line 12) occur before a single actor update (update on $\\theta$ in line 27). Two-timescale methods are generally easier to analyze since the outer loop can proceed after the inner loop converges. However, prior works such as NAC-CFA and MAC already focus on single-timescale algorithm, which are more commonly used in practice. In the comparison table, I suggest adding a column indicating whether each method follows a single- or two-timescale approach.\n\n5. Given the previous point, the novelty of this work may be questionable unless the authors can demonstrate that the sample complexity analysis remains valid for a single-timescale version of Algorithm 1.", "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:

Meta-review: This manuscript identifies the main issue of the previous analysis on natural policy gradient via actor-critic approach, and proposes new technical tools that view both the critic update and natural policy gradient finding as a stochastic linear recursion, to overcome the issue and obtain minimax optimal convergence rate in terms of $T$. Although most of the theoretical analysis does not deviate away from the existing work, most of the reviewers do find that the proposed technical improvement is solid. 

As multiple reviewers pointed out, the presentation should be further improved. The authors should highlight the key component of the technical improvements that can let the reader easily separate the manuscript with other existing works. There are also some other typos which make one of the reviewer confused about the total sample complexity. I do hope the authors can make the necessary adjustments based on reviewers' comments.
Decision: Accept (poster)