Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm
Authors: Yang Xu
Swetha Ganesh
Washim Uddin Mondal
Qinbo Bai
Vaneet Aggarwal
Venue: NeurIPS 2025 poster ()
Keywords: Reinforcement Learning
Actor-Critic Methods
Constrained Markov Decision Processes
Policy Gradient
Global Convergence
Primary area: theory
TL;DR: Global Convergence with Order-Optimal rate for Average Reward Constrained MDPs with Primal-Dual Natural Actor Critic Algorithm

Abstract: This paper investigates infinite-horizon average reward Constrained Markov Decision Processes (CMDPs) under general parametrized policies with smooth and bounded policy gradients. We propose a Primal-Dual Natural Actor-Critic algorithm that adeptly manages constraints while ensuring a high convergence rate. In particular, our algorithm achieves global convergence and constraint violation rates of $\tilde{\mathcal{O}}(1/\sqrt{T})$ over a horizon of length $T$ when the mixing time, $\tau_{\mathrm{mix}}$, is known to the learner. In absence of knowledge of $\tau_{\mathrm{mix}}$, the achievable rates change to $\tilde{\mathcal{O}}(1/T^{0.5-\epsilon})$ provided that $T \geq \tilde{\mathcal{O}}\left(\tau_{\mathrm{mix}}^{2/\epsilon}\right)$. Our results match the theoretical lower bound for Markov Decision Processes and establish a new benchmark in the theoretical exploration of average reward CMDPs.

Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm
Yang X
Swetha Ganesh"
Purdue University, USA xu1720@purdue, edu
Purdue University, USA
Indian Institute Science, Bengaluru, India swethaganesh@lisc.eee ac.in
Washim Uddin Mondal Indian Institute of Technology Kanpur wmondal @1 Qiitk ac .n
Qinbo Bai
Vaneet Aggarwal Purdue University, USA vaneet@purdue.cm edu
Purdue University, USA bai 1 1131purduue edu
Abstract
This paper investigates anfinitehhorizo average reward Constrained Markov De- cision Processes (CMDPs) under general parametrized policies with smooth and bounded policy gradients. We propose Primal-Dual Natural Actor-Critie Criii algo- rithm that adeptly manages constraints while ensuring a high convergence rate. particular, our algorithm achieves global convergence and constraint violation rates of ( ((/vT)) over horizon of length T when the mixing time, Tmix, is known to the learner. In absence of knowledge of Tmixx the achievable rates change ((1/70.5-c) provided that T Ö
2/c Our results match the theoretical Tmix
lower bound for Markov Decision Processes and establish a new benchmark in the theoretical exploration of average reward CMDPs.
Introduction
Reinforcement Learning (RL) is a paradigm where an agent learns to maximize its average reward in an unknown environment through repeated interactions. RL finds applications in diverse domains
such transportation, communication networks, robotics, and epidemic control [ 28 32 14 29].
Among various RL settings, the infinite horizon average reward setup is of particular significance for modeling long-term objectives in practical scenarios. This setting is critical it aligns with real-world applications requiring persistent and consistent performance over time.
In many applications, agents must operate under certain constraints. For instance, in transportation networks, delivery times must adhere to specified windows; in communication networks, resource allocations must stay within budget limits. Constrained Markov Decision Processes (CMDPs) effectively incorporate these constraints by introducing a cost function alongside the reward function. In average reward CMDPs, agents aim to maximize the average reward while ensuring that the average cost does not exceed a predefined threshold, making them crucial for scenarios where safety, budget, or resource constraints are paramount.
Finding optimal policies for average reward CMDPs is challenging, especially if the environment is unknown. The efficiency of solution to the CMDP is measured by the rate which the average global optimality error and the constraint violation diminish as a function of the length of the horizon T. Although many existing works focus the tabular policies (4 R apply to real-life scenarios where the state space large or infinite.
2 15 these solutions do not
Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Algorihi
Global Convergence
Violation
Mixing Time Unknown
Model-free
Sennin
Algorithm in 3
1/v7
1/v7
No
No
Tabular
Algurilhm 3 in 15
1/24//
1//44/3
Yes
No
Tabular
UC-CURL and PS-CURL
1/VT
0
Yes
No
Tabular
Algorithm 2 in 2
1/T4/4
1/TT/4
Yes
Linear MDP
Algorithm
ō 1/v7
11//
Linear MDP
Triple-QA 2
1///1//
0
Yos
Yos
Tabulor
Algorithm in
1/TV/
6 1/T1//
No
Yes
General Parameterization
This paper (Theorem
1/vT
o
No
Yes
General Parameterizattin
This paper (Theorem 4.10
1/200--
o 0117003-
Yos
Yos
General Parameterization
0 1/VT
Table This table summarizes the different model-based and model-free free state-of sattt--of-hee-et the--hherrt art algorithms available in the literature for average reward CMDPs and their results for global convergence rate and average constraint violation. The bounds of global convergence describe convergence to best performance permitted by the chosen features and policy class; the residual approximation floor fixed (independent of T), and the listed rates govern how fast the statistical gap decays toward that floor. General parameterization refers to parameterizations whose policy score Ve log (a(s)) is uniformly bounded and Lipschitz 0, together with a Fisher non-degeneracy condition.
General parametrization offers a useful approach for dealing with such scenarios. It indexes policies via minee-dimensionl parameters, which makes them suitable for large state space CMDPs. However, as exhibited in Table 1, the current state-of-the tet-hherrr art algorithms for average reward CMDPs with general parametrization achieve a convergence rate of (5) (10). which far from the theoretical lower bound of S2(1/ (1//VT)) This significant gap highlights the need for improved algorithms that can achieve theoretical optimality.
Challenges and contributions: In this paper, we propose a Hrimal-dual-baseed natural actor-critic algorithm that achieves global convergence and constraint violation rates of ((1/vT over horizon of length 7' if the mixing time, Tmix, is known. On the other hand, in the absence of knowledge of Tmixx the achievable rates change to (11/T0.5-- Therefore, even with unknown Tmix. the achieved rates can be driven arbitrarily close to the optimal one by choosing small enough e, albeit the cost of large T. Both results significantly improve upon the state-of-the-art convergence rate of ((1/T2/5) in 10 for general policy parametrization and match the theoretical lower bound.
provided that the horizon length T 2 (7
Since CMDP does not have strong convexity in the policy parameters with general parametrization, directly applying the primal-dual approach does not lead to optimal guarantees. The lack of strong convexity prevents the convergence result for the dual problem from automatically translating to the primal problem. This issue is reflected in the current state of art convergence rate in average reward CMDPs in [10], which (55/ using primal-dual approach, whereas the unconstrained counterpart in on which the above is built upon achieves convergence rate of (1/T2//4) Thus, the previous literature for CMDP in general parametrized setups shows a gap in the results of the unconstrained and constrained setups.
is evident that directly adding a primal-dual structure to an existing actor-critic algorithm, such as in 233, does not result in ((//VT) convergence rate for CMDP with general parametrization. This is specifically due to the existence of dual learning rate 3, which eventually becomes one of the dominant terms in the convergence rate of the Lagrange function. If the dual learning rate is too low, the constraint violation converges very slowly. However, if 3 is too high, the primal updates may
The convergence result holds under the condition that
Ô [Tiix)
where Tmix is the mixing time.

---

exhibit high variance, slowing down convergence to the optimal policy. To navigate this tradeoff, it is crucial to carefully tune the problem parameters.
Our algorithm has a nested loop structure where the outer loop of length K updates the primal-dual parameters, and the inner loops of length H run the natural policy gradient (NPG) and optimal critic parameter finding subroutines. We show that, to achieve the optimal rates, the parameter H should be nearly constant while K should be ( This adjustment makes our algorithm resemble single- timescale algorithm. In contrast, for unconstrained MDPs, K and H are typically set to 6 ((vT) (23)
Achieving (1/vTT) convergence in our setting requires ensuring that the bias remains sufficiently small despite a significantly low value of H. Achieving this challenging goal made possible due to the use of Multi-level Monte Carlo (MLMC)- a sharper analysis of these updates. One benefit of using MLMC-based estimates that it allows us to design an algorithm that achieves near-optimal global convergence and constraint violation rates without knowledge of the mixing time. Related unconstrained average-reward results have also used ML.C to avoid mixing-time oracles [8 34 23]; here we apply this idea to CMDPs via primal-dus dual natural actor-critic approach and provide global-rate and iverage-violation guarantecs. We would like to emphasize that our work is the first in the general parameterized CMDP literature to achieve this feat.
estimates in the inner loop subroutines and
2 Formulation
Consider an infinite-horizon average reward constrained Markov Decision Process (CMDP) denoted as MM = (S, A, r, P) where S is the state space, AA is the action space of size A, r S x A > [0, represents the reward function, e x A [-1, denotes the constraint cost function, P: S x A - (SS) is the state transition function where (SS) denotes the probability simplex over S, and E A (S)) indicates the initial distribution of states. A policy π : S - A (AA) maps a state to an action distribution. The average reward and average constraint cost of policy, æ, denoted as J and Jh respectively, are defined
Js 2 lim T-M
Eg ax) 80 ~ p ,9 e (r.c)
(1)
The expectations computed are the distribution of all r-induced trajectories {(.,, ae) ] where For simplifying the notation, we drop the
az ~ (8t), and 81+1 ~ P(st, at), 11 E (,..,...) }- dependence p when there is confusion. We aim to maximize the average reward while ensuring that the average cost exceeds a given threshold. Without loss of generality, we can formulate this as:
max J. s.t. J 20
When the underlying state space, S is large, the above problem becomes difficult to solve because the search space of the policy, increases exponentially with |S AI. We, therefore, consider class of parametrized policies. [Te )} that indexes the policies by d-dimensional parameter, 0 E IR where d < |A] The original problem in (2) can then be reformulated as follows.
J #50
JT
In the remaining article, we use = for E {r,c} for simplifying the notation. We assume the optimization problem (3) obeys the Slater condition, which ensures the existence of an interior point solution. This assumption is commonly used in model-free average-reward CMDPs [42]
Assumption 2.1 (Slater condition). There exists a 8 e (0, 1) and Ø e θ such that ( 2
We now make the following assumption on the CMDP. Assumption 2.2. The CMDP M is ergodic, i.e., the Markov chain, (5c)e20. induced under every policy म, is irreducible and aperiodic.
Note that most works on average reward MDPs and CMDPs with general parameterizations, to the best of our knowledge, assume ergodicity 110 22 I.I. If CMDP M is ergodic, then v0 E θ there exists a p-independent unique stationary distribution tH E ASS), that obeys p d where pr (s, EaEA To (a(ass) (s')) a), Vs, s' E S. Since VıT, J E.a ((, ( (s), the assumption of ergodicity also ensures that g independent of p. Vg E (r,c). Next, we define the mixing time of an ergodic CMDP.
3

---

Definition 2.3. The mixing time of a CMDP M with respect to policy parameter & is defined as, Tmix = min
(()))) - d S 4 Vs s). We also define Tmix = supoge T as
the overall mixing time. In this paper, Tmix is finite due ergodicity.
The mixing time of an MDP measures how fast the MDP reaches its stationary distribution when executing a fixed policy. We use primal-dual actor-critic approach to solve (3) Before proceeding further, we define few terms. The action-value function corresponding to a policy To is given as
g(st, p(ss, ai) - J,( ]
}1.00
(s, = E.
(4)
where g E (r,c} and (s,a) E A. We further write their corresponding state value function as
g (n (s, a)]
(5)
The Bellman's equation can be expressed as follows 35 V(s, E S A, and g E fr.c).
Qg (s, g(s a) (0) P(sa)) [V
(6)
We define the advantage term for the reward and cost functions as follows A (s, a) A 1 (s, a) - V (s) where E {rr c), (s,a) E SxA. With the above notations, we now present the commonly-used policy gradient theorem es-
Algorithm 1 Primal-Dual Natural Actor-Criti (PDNAC)
1:
Input: Initial parameters 6g. wy = 0, Eo = 0, Ào O. policy update stepsize a, dual update stepsize NPG update stepsize "uu critic up- date stepsize " initial state 8q ~ p()), outer loop size K, inner loop size H, Tiax
tablished by [39] for E (r.c).
Volg (0) = sno
A50 V. log To (a|s)
2:
for k: 0,.,,, K 1 do
a
3:
who +- wh. E). + Eo Vg E (r,c);
4:
Ia Critic Subroutine
5:
for h = 0, H - do
6:
sh t 8p, pk Geom(1/2)
The above term is useful policy gradient-type algorithms where the learning direction of the parameter is given by ( (e this paper, however, will be interested in the Natural Policy Gradients (w bujjohyete (e(re)) defined as follows.
[Ah + n2 - 1)1(2 < Tmax) +
7:
8:
for 1 0, .,..., ,
do Take action axhn ~ To, (-1s)))
In
9:
10:
1+1 P(.1shh aleh) Observe skh Observe gl ann E {r,c)
11:
end for
" A =
13:
80 + Skh
lus
14:
Update Sghh using end for
18 and 20
where F(0) E Rdxd is the Fisher information matrix, which is formally defined as: F(0) (x.a))uor (Vo log (a(a))) ( & Ve lolog [a(a[s)] where 5T (s, a) A d (s)ra(a)))
15:
1 Actor Subroutine
17:
for h = 0, ... H do
V(s, a). and @ defines the outer product. Note that NPG is similar to PG except modulated by the Fisher matrix, which accounts for the rate of change of policies with 0. The NPG direction " can also be expressed as a solution to the following strongly convex optimization problem.
18:
5th t 50, Qt: (eom(1/2) 4Ah + (20% - 12 < Tmax) +
19:
20:
for O,..., 4rn do
21:
Take action an ~ To, To, (-1s)h)
22:
Observe skh !+1 ~ P(- agr))
23:
Observe gl ahr) 9 E (r,c)
end for
1 ww F(O)W (0)
25:
+ SKA dun So
min WER
[,(0,w) =
26:
Update wy using 21 and 23
27:
end for
28:
S Sy wh wit g.H. 9 E (r.c)
The above formulation allows one to calculate the NPG in gradient-based iterative procedure. In particular, the gradient of (0, -) is obtained as Vw F(O)w~ (O).
29: Wk f- wh + Anw
30: Update (0 dx) using
12
31: end for

---

3 Algorithm
We solve 3 via a primal-duaa algorithm based on the following saddle point optimization.
max min A) (, + XJc(0) 6E A20
(10)
The term -(:--) is defined as the Lagrange function, and À is the Lagrange multiplier. Our algorithm aims updating (0, A) by the policy gradient iteration Ak E {0,..... 1 as shown below from an arbitrary initial point (Oo, do 0).
8k+1 0g + Vo AR), AR+1 = -P0031 [A+ (Ox(
(11)
where a and 9 denote primal and dual learning rates respectively, and 5 indicates the Slater parameter introduced in Assumption 2.1 Moreover, for any C IR, PA indicates the projection onto A. Since (oL(Ok, Aς), F(6g), and Jo(Ox) ) are not exactly computable due to lack of knowledge of the exact transition kernel, P. and thus, that of the occupancy measure, y "* in most RL scenarios, we use the following approximate updates.
B = 02 + oww. Au+1 = Pro.aila 3mm1
(12)
where wi is the estimate of the NPG F(O)) VoC(Ox. As), while of estimates Jc(O)). Below, we discuss the detailed procedure to compute these estimates.
3.1 Estimation Procedure
We formally characterize our detailed algorithm in Algorithm [ which utilizes Multi-Level Monte Carlo (MLMC)-based Actor-Critic algorithm to compute the estimates stated above. For the exposi- tion of our algorithm, it is beneficial to first discuss the critic estimation procedure, where the goal is to estimate the value functions and the average reward and cost functions. These estimates are then further used to obtain the NPG estimates, which are, in turn, used to update the policy parameter. The algorithm runs K epochs (also called outer loops). At the start of kth epoch, the primal and dual parameters are denoted Oz, d respectively.
3.1.1 Critic Estimation
At the kth epoch, one of the tasks in critic estimation is to obtain an estimate of Jg g E (r.e). Note that (0x) can be written as a solution to the following optimization.
min Rg (Ok. m7) WER
1 Σ 2
Σ
Via 5uh (s, a) (n g(s
(13)
SES aEA
The second task to estimate the value function V, To facilitate this objective, it assumed that, Vig E {r. c). the value function T/Th (-) is appl-apppo by a linear critic function Vg :) = (+)()), cff)) where oy S > IR' is feature mapping with the property that (s) < 1, Vs E S and cft Thm is solution of the following optimization.
min E, = Σ
d (V) (s) VV(,s)))
(14)
CERm
SES
Note that the gradients of the functions (0k0)))) :), Eg (0k, -) can be obtained as follows.
V v (2 11)
ΣΣ
Vi Te
(s) (n g(s, ()s, An RR
(15)
eESOEA
VeE,(On, ΣΣ
Jon (s, (s (T))((s) Q₂ T (s, a) (5()), VCEE"
Vg
8ES aEA
ΣΣ SESaEA A
1/
Ron (s, a) (c (g)))s) gg(s a) (0k)) Ex-P(s,iiVV T0 (d)1) (s(s)
(16)
5

---

where (a) results from Bellman's 's equation
(6). Since the above gradients cannot be exactly obtained due to lack of knowledge of the transition model P. and thus that of Vig **t we execute the following H inner loop steps to compute approximations of Jg ((kkk) and 5hh from ng.0 = 0 and $ = O.
&
Nigh+1 = Hggh - 7/ R (yx0, n,,, +h = Snn 76 Fg Sgih))
(17)
where Cy is a constant, "1g defines learning parameter, and h E {0...., H 1}. Moreover, the terms R, (g.h) and "EE((s, ck indicate estimates of (0, ((gn)) and Eg (Kk: (g,h) respectively where Sg.h A Ing (SH,n) JT. Because the expression of V (0,, (g.n)) comprises Sy.h and (Ok) (refer (16)), its estimate is a function of Hlgh and Sy.h- At the end inner loop iterations, obtain n and S which estimates of Jg (8x) and C² respectively. It remains to see how the gradient estimates used in (17 can be obtained. Note that (17 can be compactly written
<h ch Sg.4+1 = Eg.h - 78 (00k Sg.::: Vg(0s, - lc V Rg (k, ( N), (.) TT (18)
For a given pair (k, h), let Tea = (s ain. 1+1 )om indicate ne, -induced trajectory of length kh
4s 20% where Qh Geom(1/2) Following (15) and (T6). an estimate of (o (g.n) based on
single state transition sample zhe (s ann s can be obtained
Vg (Ok, ck =kh)
cyoloper aaare ( aen (s
By (Kka) (h ( 2 (0 (1)
Sg.h
(19)
A by10
Applying MLMC-based estimation, the term v vo(0k, (g,nn) is finally computed as 2t 120
08-2)) a.hh
if 2 < Tmax otherwise
(o Eg.hn) ghhh + (0.
(20)
where max a constant, v 9. = -2 2/
ck 2t=o (0,, Sg.ki Shd.. E 10, -1, 143. Note that the maximum number of state transition samples utilized the MLMC estimate is Tmax- Moreover, can be demonstrated that the samples used on average is Ó(log T.ax). The advantage of the MLMC estimator is that it achieves the same bias as averaging Tmax samples, but requires only Ö m samples. addition, since drawing from geometric distribution does not require knowledge of the mixing time,
eliminate the mixing time knowledge assumption used in previous works II 22 10 Furthermore, these previous works utilize policy gradient methods and require saving the trajectories of length H for gradient estimations, while approach does not. Therefore, our algorithm reduces the memory complexity by a factor of H, which is significant since the choice of H in these works scales with mixing and hitting times of the MDP.
3.1.2 Natural Policy Gradient (NPG) Estimator
Recall that the outcome of the critic estimation at the keth epoch is C². -
(C, where
n Ng. 5q estimate Jg(02) and the critic parameter 5o respectively. For simplicity, we will denote ck
ck
Sg.H E [ng TCT We estimate the NPG wr.0,, (refer to the definition (8) using H step inner loop as stated below Yh E {0. .0........ H 1} starting from w O.
w g.h+1 WA 7 V (Op, w g 5
(21)
where Vulf wiy Et) is an MLMC-based estimate of V V (0,, whi..) where So is given in 9
To obtain this estimate, a To. -induced trajectory Ten. = (sk., abn is considered where Pl Geomm1/2). For certain transition 2/1 (5 ag shh ), define the
1+1 1 of length 4t = 2k
8kh 1 j+l

---

following estimate.
(0n. g.ht Sg: =/h)) (0x: 2 Je. VoJ sg: ska) where
(22)
F(Oz; =na) = Volog To, k s0 Vo log no, (aa (ok ct: =han) = Ag (50: a Vo log mo, (ata (khnlshh)
(a) [o( a n c (0)()))))) 0y (p(skh)) Ve log Toe (akn (h)
where the advantage estimate used in (a) is essentially temporal difference (TD) error. Notice that the estimate of the policy gradient ( depends on < obtained in the critic estimation process. The MLMC-based estimate, therefore, can be obtained as follows.
2 00
Pt gu
px u
- 2,hh
2 S Tmax otherwise
w (0k, w g,h: 5
12 g.hh
(23)
w where u. = - 2/ Vulg (Ox, g.h. Sgi =kn) E (0, -K P.). The above estimate is 99.h applied in (2I). which finally yields the NPG estimate w g. For simplicity, we denote H. H as w
3.2 Primal and Dual Updates
The estimates w g fr, e) obtained in section 3.1.2 can be combined to compute wis w Aau Moreover, section 3.1.1 provides v/ which is an estimate of Jo(Os). At the kth epoch, these estimates can be used to update the policy parameter 0g and the dual parameter A5 following (12).
4 Global Convergence Analysis
We first state some assumptions that we will be using before proceeding to the main results. Define A, (0) Eg A (0; z) where the expectation is over the distribution of = = (s, a, s') where (s. a) ~ og s' ((s, a). and the term Ag(0; z) is defined in [9). Similarly, (0) - EE [b, =)]. Let (0) A (0) by (0) [ng (0), (0)) With these notations, we are ready to state the following assumptions regarding critic approximations.
Assumption 4.1. For E {r,c}, we define the worst-case critic approximation error to be cp
sup, Esnd' [(C (s) V (s)] 3. We assume e"PP - max (.PP) to be finite.
Assumption 4.2. There exists > 0 such that Eold (dg(s) og XT is positive semi- definite v0 O and g cr.
Both Assumptions 4.1 aad 4.2 are frequently used in analyzing actor-critic methods
13
38 Assumption 4.1 intuitively relates the quality of the feature mapping where Eapp serves as measure of this quality: well-crafted features result in small éxpp. whereas poorly designed features lead to a larger worst-case error. On the other hand, Assumption 4.2 is essential for ensuring the convergence of the critic updates. It can be shown that Assumption
4.2 ensures that the matrix Ag (0)
invertible for sufficiently large e, (details in the appendix).
Assumption 4.3. Define the following function for 0, w E Rdd AR., 0, and v E A(S x A).
= ( log mo(als) (s, (00(),a)-AA0((s.000 ()) )
(24)
Let wi, = arg minwerd Luno (w, 0, A). It is assumed that L,- (wā 0, A) < Ebias for 0 E θ and [0, where x² is the solution to the optimization 2 and ébias is positive constant. The LHS of the above inequality is called the transferred compatible function approximation error. Note that it can be easily verified that w is the NPG update direction w - X)-
Assumption 4.4. For all 0, 0,, O2 E θ and (s,a)
x A, the following holds for some G1, G2 > 0.
(a) | log (e(a)s)] < G1
(b) V log n., (als) - V log To, (a|s)] < G2 - 021-
7

---

Assumption 4.5 (Fisher non-degenerate policy), There exists a constant >> 0 such that F(0) pla positive semidefinite, where La denotes an identity matrix of dimension d.
Comments on Assumptions 4.3 We emphasize that these assumptions are commonly applied in the policy gradient (PG) literature 30 33 43 [9].
The term ébias reflects the parametrization capacity of wy. For my using the softmax parametrization, we directly have éhias 0 (]. However, when We employs restricted parametrization that does not encompass all stochastic policies, ébia is greater than zero. It is known that Cbiss remains very small when utilizzig rich neural parametrizations
[40]. Assumption 4.4 4.quuuss that the score function is both bounded and Lipschitz continuous, which
is a condition frequently assumed in the analysis of PG-based methods [30 33 43 19] Assumption
4.5 ensures that the function fo -) is j-strongly convex by mandating that the eigenvalues of the Fisher information matrix are bounded from below. This is also a standard assumption for deriving
global complexity bounds for PG based algorithms 30 46 7 [9]. Recent studies have shown
that Assumptions 44.4 hold true in various examples, including Gaussian policies with linearly
parameterized means and certain neural parametrizations 30 19
Before proving results for the convergence rate, we first provide the following lemma to associate the global convergence rate of the Lagrange function to the convergence of the actor and critic parameters. Similar ideas have been explored in [23 [0].
Lemma 4.6. If the policy parameters, {(Op, { are updated via 112 and assumptions 4.3 4.5
hold, then the following inequality satisfied
1
E
K
C(TT",a)) - c(0ss>a)) S <v VEbias +
G
E
Ex [wx]] - wfll
K
(25)
GG2
Σ k=0
K-1
+
aK ll (-(s)l(- (+1s))]-
2K
where K L(-II-) is the Kullback-Leith divergence, x² is the optimal policy for and w == wo Ar). Finally, En denotes conditional expectation given
is the exact NPG direction F history up to the kth iteration.
Observe the presence of Eblas in 25 It dictates that due to the incompleteness of the policy class, the global convergence bound cannot be driven to zero. Note that the last term in (55 is ((1((a)) because the term Ennd- [K L(T " (+1s)][To (-]ss] is a constant. The term related to B||wie| ||2 can be further decomposed as follows.
B B
Bl|wx - will K
E E|
K
(26)
K
Blwa - -w 2
ajt
E| VoL Ax)1
K
K
where (a) follows from Assumption and the definition that wi F(Ox) -V As). We can obtain a global convergence bound by bounding the terms Bllla, - w 12 [B ww [0x] wi)l and V ((0k. )x) The first two terms are the variance and bias of the NPG estimator, wk. and the third term indicates the local convergence rate. Further, E|] (, >x 2l can be upper bounded by a constant (Lemma G.2 in the appendix). We now provide the convergence result for the actor and critic parameters. For brevity, we use X to denote S Ö(-)
Theorem 4.7. Consider Algorithm 1 and let Assumptions 2.2 4.5 hold. If Jg is L-smooth, g E fr.ch
To = To is such that Ttu S 4(6)) Timx log Tmax +
mize log T'ma] and T max obeys T Tmax 2 smir
μH
where μ is defined in Assumption 4.5 the following inequalities hold Wk E {0.... KK - 1}.
[x wg.e
S capp
Tuix
T2
+ T Tmax
Ex
[|k5 - Eg (0w)))
+ xix
+ || - (0,))
(27)
Eg [1|@
x1 S Eapp +
1
Tmix
Tmix
-i + Ex
||s -c(00)]
(28)
72
H
T Tmax
8

---

where a. k. is the NPG direction F(8x)--VoJJ((e) ( (0k) is defined in section 4 and Eg denotes conditional expectation given history up to the kth iteration.
Theorem 4.7 bounds the NPG bias | [ug]] - and the second-order error ExIllug W l| in terms of the critic approximation error Eapp. and the bias [[ 5g (0x)ll and the second-order error Eg || S (0x))l in the critic parameter estimation. The following theorem provides bounds on these latter quantities.
Theorem 4.8. Consider Algorithm I and let Assumptions 2.2 4.5 hold and g E (r,c). If we choose 7
2log such that "ig S 24c4 Timee log Tiax while maxx obeys Tmax the following inequalities hold 4k {0, ... K 1}.
Sc. Timix
where À is defined
XH in Assumption 4.2
| E7 (0x)l
2 7 +
(29)
Tmax"
E Sg (000)
+
Tmix
Tmix
(30)
7
H
Tmax
where (0x) is defined in section 4 and E3 denotes conditional expectation given history up the kth iteration.
Invoking the bounds provided by Theorem 4.7 and 4.8 into Lemma 4.6
obtain convergence
rate the Lagrange function. Our next goal is to segregate the objective convergence and constraint violation rates from this Lagrange error. This achieved by the following theorems. Depending on whether we have access to the mixing time, two similar but slightly different results can be obtained.
Theorem 4.9. Consider the same setup and parameters as in Theorem 4.8 and Theorem 4.7 and set 111/2, 3 T 1/2 If mii is known, set H ( with K T7 H. We have:
1
J,(0a)] 2 V + Vapp + B[J
(31)
K
VT
K
Σ k==
[[-Jo(Oua] S Veblas + Eaap + E8|
1
(32)
K
VT
Theorem 4.10. Consider the same setup and parameters as Theorem 4.8 and Theorem 4.7 and set T- 3 T 1/2
H T and K = T With T ((Fmix)) we have:
K-1
BJJ - (,(0)]] S v Vbllas + Eapp + T(0.--c)
(33)
K
K
E E[-J((0A)
Vebins + Capp + T(0.5-e)
(34)
K
K=
Theorem 4.9 dictates that one can achieve both the objective convergence and the constraint violation rates O 1/2) up some additive factors of ébias and Eapp where T is the length of the horizon. However, knowledge of the mixing time, Tmix, is needed in this case to set some parameters. On the other hand, Theorem 4.10 states that, if knowledge of Tmix unavailable, one can achieve objective convergence and constraint violation rates as (TT-1/2+e as long as the horizon T' exceeds 2/e) Note that one can get arbitrarily close to the optimal rate of ((1-1/2) by choosing arbitrarily small The caveat is that the smaller the e, the larger the horizon length needed reach the desired rates.
which can be large for slowly mixing problems. In such a scenario, one can switch to the parameter setting of Theorem 4.9 which does not impose any such restriction on T. However, since this setup requires the knowledge Tiiix one can treat Tmix as one of the unknown hyperparameters of the algorithm, and fine-tune it during the training phase. This is in line with other RI algorithms in the literature that also require fine-tuning of several unknown hyperparameters, such as the Lipschitz constant or hitting time μ. Despite these practical solutions, acknowledge that a systematic theoretical investigation is
In the setting of Theorem 4.10 for small e, the horizon requirement becomes T Z 2/c
mix

---

needed to improve the requirement of the horizon length, T (in the absence of knowledge of Tmix), which is left as one of the future works.
also worth highlighting that due to the presence <hiss and app- the average objective error and constraint violation cannot be guaranteed to be zero, for large T. However, for rich policy parameterization and good critic approximation, the effects of these quantities are negligibly small.
5
Conclusion
In this paper, investigate the infinite-horizei average reward Constrained Markov Decision Processes (CMDPs) with general policy parametrization. We propose a novel algorithm, the "Primal- dual natural actor-critic," which efficiently manages constraints while achieving global convergence rate of
aligning with the theoretical lower bound for Markov Decision Processes (MDPs). We also extend our analysis to the setting with unknown mixing time. Future directions include narrowing the performance gap in this setting, parameterizing the critic using neural networks in 25 21, and relaxing the ergodicity assumption following (20)
6
Acknowledgment
The work supported in part by the National Science Foundation under grant CCF-2149588, Office Naval Research under grant N00014-23-1-2533 and Cisco Systems, Inc.
References
[1] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. The Journal of Machine Learning Research, 22(1):4431-4500 2021.
[2] Mridul Agarwal, Qinbo Bai, and Vaneet Aggarwal. Concave Utility Reinforcement Learning with Zero Conrsrrnnnt Violations. Transactions on Machine Learning Research, 2022.
[3] Mridul Agarwal, Qinbo Bai, and Vaneet Aggarwal. Regret guarantees for model-based rein- forcement learning with long-term average constraints. In Uncertainty in Artificial Inielligence, pages 22-31, 2022.
[4] Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. Advances in Neural Information Processing Systems, 30, 2017.
[5] Abubakr O Al-Abbasi, Arnob Ghosh, and Vaneet Aggarwal. Deeppool: Distributed model-free algorithm for ride-sharing using deep reinforcement learning. IEEE Transactions on Intelligent Transportation Systems, 20(12):4714-4771 2019.
[6] Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008
[7] Qinbo Bai, Amrit Singh Bedi, Mridul Agarwal, Alec Koppel, and Vaneet Aggarwal. Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal- -uall Approach. Proceedings of the AAAI Conference on Artificial Intelligence, 36:3682-366 36899 Jun. 2022.
[8] Qinbo Bai, Amrit Singh Bedi, Mridul Agarwal, Alec Koppel, and Vaneet Aggarwal. Achieving zero constraint violation for constrained reinforcement learning via primal-dual approach. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 3682-3689, 2022.
[9] Qinbo Bai, Amrit Singh Bedi, and Vaneet Aggarwal. Achieving zero constraint violation for constrained reinforcement learning via conservative natural policy gradient primal-dual algorithm. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 6737-6744, 2023.
10

---

[10] Qinbo Bai, Washim Mondal, and Vaneet Aggarwal. Learning general parameterized policies for infinite horizon average reward constrained MDPs via primal-dual policy gradient algorithm. Advances in Neural Information Processing Systems, 37:108566-108555 2024.
[11] Qinbo Bai, Washim Uddin Mondal, and Vaneet Aggarwal. Regret analysis of policy gradient algorithm for infinite horizon average reward Markov decision processes. In AAAI Conference on Artificial Intelligence, 2024.
[12] Aleksandr Beznosikov, Sergey Samsonov, Marina Sheshukova, Alexander Gasnikov, Alexey Naumov, and Eric Moulines. First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[13] Jalaj Bhandari, Daniel Russo, and Raghay Singal. A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation. CoRR, het//8006025555 2018.
[14] Jiayu Chen, Tian Lan, and Vaneet Aggarwal. Option-aware adversarial inverse reinforcement learning for robotic control. In 2023 IEEE International Conference Robotics and Automation (ICRA), pages 5902-5908. IEEE, 2023.
[15] Liyu Chen, Rahul Jain, and Haipeng Luo. Learning infinite-horizon average-reward Markov decision process with constraints. In International Conference on Machine Learning, pages 9246-3270 PMLR, 2022.
[16] Dongsheng Ding, Kaiqing Zhang, Tamer Basar, and Mihailo Jovanovie. Natural policy gradient primal-dual method for constrained Markov decision processes. Advances in Neural Information Processing Systems, 33:8378-8883 2020.
[17] Dongsheng Ding, Kaiqing Zhang, Jiali Duan, Tamer Başar, and Mihailo R Jovanovié. Conver- gence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs. arXiv preprint arXiv:2206. 2244022200.0 2022.
[18] Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploottion in constrained MDPs. arXiv preprint 18Xiv:2003.02/88, 2020.
[19] lyas Fatkhullin, Anas Barakat, Anastasia Kireeva, and Niao He. Stochastic policy gradient methods: Improved sample complexity for fisher-non-degeeerat policies. In International Conference on Machine Learning, pages 9827-9869. PMLR, 2023.
[20] Swetha Ganesh and Vaneet Aggarwal. Regret analysis of average-reward unichain mdps via an actor-critic approach. In Advances in Neural Information Processing Systems, 2025.
[21] Swetha Ganesh, Jiayu Chen, Washim Uddin Mondal, and Vaneet Aggarwal. Order-optimal global convergence for actor-critic with general policy and neural critic parametrization. In The slst Conference on Uncertainty in Artificial Intelligence 2025.
[22] Swetha Ganesh, Washim Uddin Mondal, and Vaneet Aggarwal. 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.
[23] Swetha Ganesh, Washim Uddin Mondal, and Vaneet Aggarwal. A sharper global convergence analysis for average reward reinforcement learning via an actor-critic approach. International Conference on Machine Learning. 2025.
[24] Ather Gattami, Qinbo Bai, and Vaneet Aggarwal. Reinforcement learning for constrained markov decision processes. In International Conference on Artificial Intelligence and Statistics, pages 2656-2664 PMLR, 2021.
[25] Mudit Gaur, Amrit Bedi, Di Wang, and Vaneet Aggarwal. Closing the gap: Achieving global con- vergence (last iterate) of actor-critic under markovian sampling with neural network parametriza- tion. In International Conference on Machine Learning, pages
PMLR, 2024.
[26] Jacopo Germano, Francesco Emanuele Stradi, Gianmarco Genalti, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. A Best- Bott--othhhhleee Algorithm for Constrained MDPs with Teng-Termoe Constraints. arXiv preprint axXiv:2304.14326 2023,

---

[27] Arnob Ghosh, Xingyu Zhou, and Ness Shroff. Achieving Sub-linear Regret in Infinite Horizon Average Reward Constrained MDP with Linear Function Approximation. In The Eleventh International Conference on Learning Representations, 2023.
[28] Marina Haliem, Ganapathy Mani, Vaneet Aggarwal, and Bharat Bhargava. A distributed model- free ride-sharing approach for joint matching, pricing, and dispatching using deep reinforcement learning. IEEE Transactions on Intelligent Transportation Systems,
2021.
[29] Lu Ling, Washim Uddin Mondal, and Satish V Ukkusuri. Cooperating graph neural networks with deep reinforcement learning for vaccine prioritization. IEEE Journal of Biomedical and Health Informatics, 2024.
[30] Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (variance- reduced) policy gradient and natural policy gradient methods. Advances in Neural Information Processing Systems, 33:7624-7636, 2020.
[31] Washim Mondal and Vaneet Aggarwal. Sample-efficient constrained reinforcement learning with general parameterization. Advances in Neural Information Processing Systems, 37:68380- 68405, 2024.
[32] Mahadesh Panju, Ramkumar Raghu, Vinod Sharma, Vaneet Aggarwal, and Rajesh Ramachan- dran. Queueing theoretic models for uncoded and coded multicast wireless networks with caches. IEEE Transactions Wireless Communications, 21(2):1257-1277 2021.
[33] Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. Stochastic variance-reduced policy gradient. In International conference on machine learning, pages 4026 4035, 2018.
[34] Bhrij Patel, Wesley A Suttle, Alec Koppel, Vaneet Aggarwal, Brian M Sadler, Dinesh Manocha, and Amrit Bedi. Towards global optimality for practical average reward reinforcement learning without mixing time oracles. In Forty-first International Conference on Machine Learning, 2024.
[35] Martin I. Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
[36] Shuang Qiu, Xiaohan Wei, Zhuoran Yang, Jieping Ye, and Zhaoran Wang. Upper confidence primal-dual reinforcement learning for CMDP with adversarial loss. Advances in Neural Information Processing Systems, 13:15277-15287, 2020.
[37] Shuang Qiu, Zhuoran Yang, Jieping Ye, and Zhaoran Wang. On finite-time convergence of actor-critic algorithm. IEEE Journal on Selected Areas in Information Theory, 2(2):652-664, 2021.
[38] Wesley A Suttle, Amrit Bedi, Bhrij Patel, Brian M Sadler, Alec Koppel, and Dinesh Manocha. Beyond Exponentially Fast Mixing in Average- Reward Reinforcement Learning via Multi- Level Monte Carlo Actor-Critic. In International Conference on Machine Learning, pages 33240-33267 2023.
[39] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
[40] Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural Policy Gradient Meth- ods: Global Optimality and Rates of Convergence. In International Conference on Learning Representations, 2019.
[41] Chen- Yu Wei, Mehdi Jafarnia Jahromi, Haipeng Luo, Hiteshi Sharma, and Rahul Jain. Model- free reinforcement learning in infinite-horizon average-reward Markov decision processes. In International conference machine learning, pages 10170-10180, 80. PMLR, 2020.
[42] Honghao Wei, Xin Liu, and Lei Ying. A provably-efficient model-free algorithm for infinite- horizon average-reward constrained Markov decision processes. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 3868-3876, 2022.
12

---

[43] Pan Xu, Felicia Gao, and Quanquan Gu. Sample Efficient Policy Gradient Methods with Recursive Variance Reduction. In International Conference on Learning Representations, 2019.
[44] Pan Xu, Felicia Gao, and Quanquan Gu. An improved convergence analysis of stochastic variance-reduced policy gradient. In Uncertainty in Artificial Intelligence, pages 541-551, 2020.
[45] Tengyu Xu, Yingbin Liang, and Guanghui Lan, CRPO: A new approach for safe reinforcement learning with convergence guarantee. In International Conference Machine Learning, pages 1 11480-1 1491. PMLR, 2021.
[46] Junyu Zhang, Chengzhuo Ni, Zheng Yu, Csaba Szepesvari, and Mengdi Wang. On the Conver- gence and Sample Efficiency of Variance-Reduced Policy Gradient Method. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[47] Shaofeng Zou, Tengyu Xu, and Yingbin Liang. Finite-sample analysis for SARSA with linear function approximation. Advances in neural information processing systems, 32, 2019.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We point out the limitations of our work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification:
We provide the full set of assumptions and complete proof for each theoretical
result.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: Our paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer:
[NA]
Justification:
Our paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ lttipp.cc/pulli//guiice. http://pibbppcuuuuee//eeeeeitiia /CodeSubmeiiiccec corbbbmsssioww ssisnnsonoooos seiocyylccy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Our paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Our paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
16

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Our paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: wtw.rripscccc/aeeeee
Answer: [Yes]
Justification: Our paper conforms, in every respect, with the NeurIPS code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is potential societal impact of work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
17

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Our paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperssittcooe com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
18

---

Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper involves neither crowdsourcing nor human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper neither involves crowdsourcing human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
19

---

Justification:
We do not use LLM in our paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our L.MM policy htteas////eerrpppocc////oeeeeeee for what should or should not be described.
20

---

A Related Works
The constrained reinforcement learning problem has been widely explored for both infinite horizon discounted reward and episodic MDPs. Recent studies have examined discounted reward CMDPs in various contexts, including the tabular setting M with softmax parameterization [6 451 and with general policy parameterization setting 16,
Additionally, episodic CMDPs have been Recent research has also focused on infinite horizon average reward CMDPs, examining various approaches including model based setups [ B 2]. tabular model-free settings [42]. linear CMDP setting [27] and general policy parametrization setting introduced algorithms leveraging posterior sampling and the optimism principle, achieving a convergence rate of (1/VT) with zero constraint violations. For tabular model-free approach, 42 attains a convergence rate of Ö(T 1/6) with zero constraint viola- tions. In linear CMDP, (27) obtains (77-1/2) convergence rate with zero constraint violation. Note that linear CMDP assumes a linear structure in the transition probability based on a known feature map, which is not realistic. Finally, [10] studied the infinite horizon average reward CMDPs with general parametrization and achieved a global convergence rate of (51/T)/55. Table summarizes all relevant works on average reward CMDPs.
45 31].
explored in the tabular setting by [8] 36 26
10.. In model-based CMDP setups, 2
In unconstrained average reward MDPs, both model-based and model-free tabular setups have been widely studied. For instance, the model-based algorithms by 4 6 obtain the optimal convergence rate of (11 / /T). Similarly, the model-free algorithm proposed by 41 achieves ((1/ convergence
rate for tabular MDP. Average reward MDP with general parametrization has been recently studied
in [23 222 where global convergence rates of Ô /TTVT) are achieved. In particular, [23 leverages Actor-Critic methods and achieves global convergence without knowledge of mixing time.
B Preliminary Results for Global Convergence Analysis
To prove Theorem 4.8 and 4.7 we first discuss a more general case of linear recursion with biased estimators.
Theorem B.1. Consider the stochastic linear recursion that aims to approximate I- = -P-lg. qg
Ph+1 2/. -B(Phan -
(35)
where Pho qn are estimates of the matrices P E 1x q IR." respectively, and h E [.,.... 11 13. Assume that the following bounds hold vTh
Ph
27
S 2
En
Ph
P S 8
(36)
E₁ ||ân
=1 < o ER [qh] - g1l2 < 8, and E 1/nl - = 5²
where Er, denotes conditional expectation given history up step h. Since Elân] EIE [Qn]], we have 82 < 82. Additionally, assume that
0 Ap S ||||| S Ap and ||qll S.a, The condition that Xp > O implies that P is invertible. The goal of recursion (35 is to approximate the term x² -P11 q. 8p S Xp/8, and 3 < Ap/[A(607 + 2A7}],, the following relation holds.
(37)
E || 1²1 < exp (-H3Xp) E1 x²1 111 + +
[ R1
(38)
where Ro = + Ap oz Ri Ap=
18 2 62) and Ö(-) hides logarithmic factors of
H. Moreover,
B[zn| - x² 1²1 < exp (-H3Xr)
|| - 211
1
83 E [1:00 - 11] + + 08RO + R1) R1) }+ Ri
+ A
8 -+
(39)
Ap
where Rí = -P.Ap2 A
+ 82
21

---

Proof. Let gh Phizh - 9n. To prove the first statement, observe the following relations.
[ai+1 - xx" =x²1²== || 3gh- - x=1
| - xx" =12 - -z xxhhh) + 119
|| x²1 1² - 23 xx, P( x²)) - 23 g9h P(mn- x²)) + 31 gl
(a) | x²112 2,2 1 2²11 - -23(5n xx, 9h P( x²))
2-12- P(un - x² )12 + 2,3 P| - x 2²1
+ +232
|a x ==112-2Bxpp 1 x²12- - -28rn - -x",
9hh - P( - x²)) 1,3 P(zn - x²") )| + 227,.31112, - x12
where (a), (b) follow from Ap ~ |||| S Ap. Taking the conditional expectation E, on both sides,
Ex [1r4411 - x" 2²11"] s < (1-2,Xp 2A 32) || x x²1
(0====²' En 19n- - P(In- xx })>>> + +,33 En 119n - P(Ira x²)1 (40)
Observe that the third term in 40 can be bounded as follows.
llan P( x²)ll
= II(P; - P) x²) + (Ph - P)* + (q- - 11)1
s 3/1 P1l - 2=11² 3 - 11121 || 311q on 1|
S 3/ - P11d1122 - 112 + 3Ap²A²11 - P| + 311q - 11.
where the last inequality follows from
=| 'gll s Ap 2 A3 Taking the expectation yields
Eallon P(rn xx") =²1
$ 33E, Pn - P1| - x 112 1 +32p A EM Pr, - P11 + +3E l0: - -gl2
< f0 | - x0 112 + +3 3300"\003 30
(41)
The second term in 40 can be bounded as
Xp | x=11² +
1 |n[gn P( - x= x11
-(1% xx, EA Ioh- P(æn- x²)1] S
4
Ap
AP 1..7 - -a*112 1
[B [Rn[P[]] - p] Iih + {1--
E2 [6m] 2
dp
XP || - x=1 +
207 || 1| 1++ +222
4
dr
Ap s Im
45% - x² 1/2 + 16 72 2 252
x=1|
(42)
Ap
where the last inequality follows from in (40), we arrive at the following.
||=1|== = ||p||-1p 1g1? S Ap= A₂ Substituting the above bounds
11- 333pp
8,303
E. [||a+11 - -111|] s
+ +63 07. +28AA3) || x21
2
Ap
4
[28 [203
+ 632 13~^^303 + +J
+
Ap
For 8p S Ar/88, and / < Ar/(4(60 + 2A we can modify the above inequality to the following.
4.3
Ea - < (1 - 3>p) ||اا - 11 +
[20 + 82 + 6 [A 73 + =
Ap
22

---

Taking the expectation on both sides and unrolling the recursion yields
B = x²1 x=1 - (1
- [Xp) B1 x=
+ Σ (1 - 3Ap) h
#-1
4
[20PApp2 A + +6] +63 [X A3p + ogj
Ap
h=0
1 {
43 |203Ap²A3 12 6 632
<exp (- 1-H3Ap) E 20 x²112
t 63 1323 + ogl
BAp
Ap
= exp (- (-H3Ap) E 11 4xp² 22p2>p"??
+
8/
To prove the second statement, observe that we have the following recursion.
[[ 1 - 1|2 [[[[ ] - |E[gn] - 12
= [[[aa]] - =1 (3 x², E[gh)) + B
||B[a>>] - ==2 23(E[mm] x², P(E[zn] x²))
2.3(B[zn] x", E[gh] P(B[xk] =²") 3 ||[g1111
(a)
[[B(xx>] - xx 2 2/Ar||B(r>) - x x11 2.3 [. x², Elga] ((T[2x)) x x²)}
+ 2.32 2 [[ [gn] P(B[ar]] - x")" + P - x² x²
(b)
< [|B[[z]] x x² 2,8 p
[B - x11 - - x", Elgn] - P(E[xn] - xx"))
+ 2.33
=111
$ (1 23Ap + 2* [|[[a]] 21 23 (E [ x0', P(E[zn) x²))
+ 2 [|[n]] - [[ - 2
(43)
where (a) and (b) are consequences of A - ||||| S Ap. The third term in the last line of be bounded follows.
43 can
[[gh. [(E[ZA] x² x²)11== E (Ph - P)( =z*) + (E[PA) P)x* + (q- E(
3E
[IEM -11 1|llaan==1'1 x²113] 3E
[Ba[PP] P p1[ ||0 + 3 311 Elg.. ||
35%.1
- x²'1 [|00-=2
+ +35
(a) 368 E [[|:00 - 11 (3Ro + R2)
} + 3x, 2255 35
where (a) follows from 38
The second term in the last line of (43 can be bounded as follows.
(B[xy) x=, E, E [9n]
P(E[œy] x²)]}
Ap
1
|| x=1l" 11
+ Ar
[B|yn] - P([[(r)] - =²*)
4
$ Ap [B[
- x 112 +
3
8%
E [|000 x" x013 + +0 (3Rg + +Bi) + +Ap2A,07 + +52
4
Ap
Substituting the above bounds in (43 we obtain the following recursion.
3/3Pp
[[ =11 <
1
+
21
| [[ x=1
2
1
E || x |13| + (3Rl RR)) } + +50
+ 63
3 +
83
Ap
If B Ap/()))) the above bound implies the following.
[[[x++]] x= 11 S (1 11255
3AP) |[[m]]] - x 112
+ (3Ro + R1) } -xp2
+ 63 (8+ Ap
8% 11 - x =
+xp2A233 -
23

---

Unrolling the above recursion, we obtain
| - x" = (1- - 32p) H
|| x²11
H
6 \1-1
' 3 (++
(3+
1 Xp
oz
R 1 O O RI) ) A +
h=0
$ exp
(- (-H3Xp)
|| x211
6
3 Xp
83.
E [00 211 0 ( + Ri) R
Ap
where R2 = kp>p215 + 8 This concludes the result.
We now provide some bounds MLMC estimates.
Lemma B.2. Consider a homeeenooge,uuss, ergodic Markov chain (Z))r20 with a unique invariant
distribution dz and mixing time Tmix- Assume that V (a,, 7) is an estimate of the gradient V (x)).
Let E V Fxx Z Fz))l1 S. 8² and F[V Z.) Edz [V 2)] S o² for all 2
Q Geom 1/2), then the following MLMC estimator
[2 (g) - 9- if29 S Tmax otherwise
where g¹ = = 2 2'
9MLMC = g"
VF Zi) (44)
0,
satisfies the inequalities stated below.
(a) [[GMLMM]] 1E[g Dog T Tmax.)
(b) E V Fx)) - 9MLMC 1'] S 0 (0" log, Timax + 82)
(c) (z) - |igMLMc]| & O TmoxTiixmmi max + 62)
Before proceeding to the proof, we state a useful lemma.
Lemma B.3 (Lemma I, [22.. Consider the same setup in Lemma B.2
The following holds.
--1 V Ze) - Edz VF(x, 2)
Citmix o².
E
(45)
N
N
t=
where N is constant, C1 16 + and the expectation is over the distribution of { Zz \ emanating from any arbitrary initial distribution.
Proof of Lemma
B.2
The statement (a) can be proven follows.
Dlog, Tmaa.
E [[MLMM]]
+
Pr[Q = j} - 22' g²
Dlog Tmax.
Elgg² r Elg 1log Tmax
1=1
For the proof of (b), notice that
[Ea
F (xx, Z
9MLMC |
2E
Edz [VF(2))] 0013] 2E 11MMLMC
-991" 90|1"]
2E
Eaz
V F [2x)) g0 !12
222
blogz T'aax
Pr(Q = = 4'1 [199 g -0-111
2F
FF [2x+)
9 |2]
2
boog2 Timax
2 "||a - -11
2E
Edz
V F(()))
g0 [1]]
4
[log, Tiax
2d [
Bid,
FF( 2)] -1-1 + [110 Eag F 2)]1(3)
1=1
(0)
[lona TmaaJ 20
1
1 )
2 2+4 O2
+
O (o2 log, Tmax)
1=1
2--1
21
24

---

where (a) follows from Lemma B.3
Using this result, we obtain the following.
E [(VF(())
9MLMel 11] S 2E
[VF()) Ed, [VF(x, =)]l + 2T [iEd, [VF(s, 2)] 9MLMC|l
f (m'x log, maa + 6²)
This completes the proof of statement (b). For part (c), we have
[V))) E [IMLMC]]|
S 2 22 Eiz [F Z)]1| +2 B [VF(x, 2) - [gMuMc]ll
(46)
|||
(0)
2C1tmix o²
< 28 + Edz VF 2)] E[gllos, llog T Tmux]]
3 282
Taax
where (a) follows from Lemma
B.3
This concludes the proof of Lemma B.2
C Proof of Lemma 4.6
We begin by stating useful lemma:
Lemma C.1 (Lemma 4, [I]. The performance difference between two policies Te, Wer bounded as follows where E cJ.
J(0) [(6') = Eewar (-)) (A (s.a)].
(47)
Continuing with the proof of Lemma 4.6 start with the definition of KL divergence. For notational simplicity, shall use A,4 to denote A A
To (als) log To. (a.s) 8)
Ea-a- (+]s) (11)) KL(x ([s) (+18)] Exaaamenn
(4)
G2 110411 - 0x11
2 (sa))
Vo no, (alss (0x+1 - 0x)]
Te, (als) wx] Gza²
V Vo (B,0,))
||
2
2za²
aB (B,))))) V log no (a wil + a:E (s.a Vo Volog mo, (als) (we - w[]]
| 11
alC(x", Ax) [(O), Ax) + aB (..0)~u''
V log Te, (als) wil
Vo logog To, (als) (wi - wx]] G2az
a([(TT, AA)) [(O,, Ax)) + arl (s.))
||wa
2
( a[[(TT, Aa) L(0x, Ax)1 + aEE aLE (s,a)~rr*
Ve log To. (a|s) wh - A A7thec(s,00
Gza?
+ +all Tog To. (als) (wi - whll
||wx| 11
2
(c)
27
2 a|L(TT" ,A,) L(Ok, Ax)) - o/ B(saaven
Vo log To, (als) wt - A Tip (
G2a²
+ aiE (s.) V4 log no, (als) (wx - wxll
||w
(d)
Gza²
2 a[L(T" Ab) _(0,, Ax) - a a Ebias + aE (s.))arr [ log næ, (als) (wk wf)l
||
2
where L(TT" Ax) J J + AeJT the relations (a), (b) result from Assumption 4.4 b) and Lemma
C.I respectively. Inequality (c) arises from the convexity of the function f(x) x² Lastly, (d) is
25

---

consequence of Assumption 4.3 By taking expectations on both sides, we derive:
E [ Bond (- mo, (-1s) KT("=" (+55)] (+1))]]
2 al(((T' Ax) ([k As)ll Ebiie
2
+ aB [B BBad Bext (11a) Vo log To, (als) (Blwn)Ok) wfll
E [|[
2
2 aa(((T' Au) - (I Ax)]] Ebiss
(48)
G2a²
- aE [((,,a)Nun [1 Vo log To, (a]s)]l[[[[l00)) - w
E [||wx11 11
(a)
a|[(m" A1) B[ Ax)]]
avibias
G2a²
aGi B [B Os] will
||]
2
where (a) follows from Assumption 4.4 a.) Rearranging the terms, we get,
G2a [( An) (n))-E(((0n,, Aa)] S Vehias + G - wfll + 2 Bl
(49)
+ E [Bana [
(-|s) [+ (-1s)
KL (-1s) (+1)))]
Adding the above inequality from to K 1, using the non-negativity KL. divergence and dividing the resulting expression by K, obtain the final result.
D Proof of Theorem 4.8
Recall that (0) = Eg (0; 2)]. (0( Eg By(b,( 2)}, and (g()) ( where Eg denotes the expectation over the distribution to section[4] 4
(s, a, s') where (s,a) D== P(s, a) (refer
Lemma D.1. For large Cp, Assumption 4.2 limplies that (0())) (A/2) positive semi-definite for both g cr,c] and for all lo where T is identity matrix, i.e., E (0x))) 2 A/2 11E12 for all &.
Proof of Lemma D.I Note that for any 5 = [17,5]. we have
< (O)(( c + n Es, [+)] + STIE,, Ea,, (s)
cn2² |K|| + A 1|51
(50)
||<||
min Cy V u(1 u0 w [<[[0.]
A(1
(1) (A/2) |E|
where (a) is a consequence of Assumption 4.2 and the fact that [166 S 1. vs E S. Finally, (b)
holds when Cy x x 1. This completes the proof.
Let A MLMC and b kA be the MLMC estimators of (0n Haa and (by(0s) (h g. respectively (see ) i.c.
2
(A o 9.hh
- A
24-1 g.hh
2 < Tmax otherwise
A
MLMC g.h
A. +
(51)
0,
where A
1 2 (0kik; 2hhn and
9.hh
20
(b
bb -h 9.hh
if 2 < Tmax otherwise
MLMC 9.hh
b
9.hh +
9.
(52)
0,
where g.
by (0z: z
2
We can bound the bias and variance of A MLMC
g.hh and b MLMC follows.
26

---

Lemma D.2. Consider Algorithun 7 with policy parameter 8% and assume assumptions 2.2 4.5 MLMC obey the following bounds. g,
hold. The MLMC estimators A ML.C and b
g.kh
(a) [ [A
MLMC
A (0x < O (c Tmix max)
9,8h
(b) [| & P
MLMC g.hh
- b,,( - Tmix
(c) A [
MLMC
(0w)]] 2 0 (GG Tmix mix log T mmax)
(d) ER [ [IbLII (0x)l S O (ci log T maxx
where h E {0,... ,H H-111 11 and E defines the conditional expectation given the history up to the inner loop step of the critic within the kth outer loop instant.
Proof. Recall from (99 the definitions of (9 and b(Os; 2) for any Exx
We have the following inequalities.
(0)
(0ss I| - |c,1 + (10, (s) o,''))))
S e, +3 +3
(53)
[lby (0,5 m) S |c,9(1 a)l + (1(( (+) S G -
(54)
where (a), (6) hold since 19(s, a)l < and (ل)اا S 1, v(s, 8 x A. Ag fr,c) Hence, for
any 2 E A x S, we have the inequalities stated below.
A0(0)) s O(2)), and by ( by (0)) - (
Combining the above results with Lemma B.2 and using the definitions that Ag) = Eo (A (0; (0) = E.l (b,( =)]. we establish the result.
Combining Lemma D.1 with 53
54
we obtain the following for any 0% with cy 2 A + V x 1.
A
S
A (0x) s O(e)), and [bb (0x) s O(c))
(55)
2
Combining the above results with Lemma D.I along with Theorem B.1 we then obtain the following inequalities given that Tmax
8c Timix and Yg 24c Triix log Tmax"
Es |1 1..H (0)))) S sexp (-H 1|5o (0,)l + (re + Ri),
Ex
| m1
Ey (0w)) s exp (-H+rE ||50 (0,))
Arg +
O Tmxx)
Frmn if ||5o ((w) + o (yę RRi) } +R1
Rı
X²
where the terms Ro, R1, Ri are defined follows.
Ro = θ (X Tmix + x=11GTTmx)) = Ô (X~3 (G
R1 O (Tm- A -4 cn Taix T mixxs O (Tmml X -1
R = O (ImLe) Imix + Tmbbe 2,tmmx) = =0 (Tmmk c Fmix)
we further set Y:-
2log XH
while ensuring
2log AA
< 24c Time log Tine
we have the following results.
| - (0 + + (x- (x-c2 Fmix 1 + Tmax
)
E₁ ||55 (Bx)))
< T
H
E& Isl. - (5(())11 s0 ((
Tmix
G
T72 AmTmax
1|5u (BWW)
+ Ö
16T
27

---

We used the fact that H H + max = ((1) in the last inequality. Utilizing E
Sg. Eo = 0, and
[157 (0x) (0x)] (by( -(1-²c²) (via (55),
conclude:
Es
|| <5( 1272
c
+0
+
^ 2 Tmix
1 Tima
(56)
Tmix
5 T
C
T mix
6
|| Eg (0w)) s
=
(57)
T
X²T max
X max
1272
mmax
This completes the proof.
E Proof of Theorem 4.7
To prove Theorem 4.7 follow a proof structure similar that of Theorem 4.8 MMLMC Jg,hh denote the MLMC estimators defined follows.
Let FMLMC and kh
20%
Q - Eh
if 2 < 7max otherwise
MLMC kb
F.
(58)
0.
with FJ
1
Lt F(Bu: (see
(2) and
kh 23
VMLMC Jg.hn VoJg.hr +
20
(V
Jg.kh
Tah-JJgght Jg,hhl,
2 < Tmax otherwise
(59)
0,
where VoJg,th = 2- Ei' J (0 Et: 2/.)) (see
22
Using the above inequalities, we can bound the bias and variance the ML estimators as follows. Lemma E.1. Consider Algorithm 7 with given policy parameter 8x. Under the assumptions 2.2 the following statements hold.
4.5
(a) [R D. F(0 < O (G1 miix max
kh
Tmie (b) [[ MMLMC gg (oJg(0e)) O ( mmiee T-1 + 8k.
(c) E. [[ MLLMC F(O < O Tmix log ToggTmi mmax)
(d) E E. [II V MIMMC J J. VoJ,(0a)]13] 50 (0 mix log Tmax + kk.0
(e) E& MLMMC Jg.unl (o < O (0 Tmix max 8Z.0)
where Ex h. defines the conditional expectation given the history up to the inner loop step h of the actor within the kthh outer loop instant, while E5 the conditional expectation given the history up to the kth outer loop instant. Moreover,
22 = 0
GP ())
2 kg o
(CREal || 121)
22 o
(G -(0h)) + Gf Gleupp)
8 o
G Ea [5t] -0(0))) Gheppp)
for h E H0.1,...,H1
-1
Proof of Lemma E.I Fix an outer loop instant & and inner loop instant h E {o.... - 1) of the actor subroutine. Recall the definition of F(Ox;-) from (22) The following inequalities hold for any O2 and 2 Ax
Eg [F(0x; z)] (a) F(Ox), and || | (0x Eo, [P(0k; 22 2G
28

---

where Es, denotes the expectation over the distribution 2 = (s, s') where (s, ~ vaa,, s ~ P(-|s. a). The equality (a) follows from the definition of the Fisher matrix, and (b) is consequence of assumption 4.4 Statements (a) and (c), therefore, directly follow from Lemma B.2
To prove the other statements, recall the definition of VeJg(On, )) from 22 Note the following relations for arbitrary 0k. E
Ing. Sgl.
Eo, [VoJ (Ok, 50: +0:z)
(Ok)
-1/ + (s') (5') - ,g(t), (t Vo log To (albs) - Voda(
= En,
g((,a)
(a) Box
(n)(Oh) ni + (5') 6g(s), 5 -(0(0)) Vo log Te (als)
To
+ Bes
Vi - (0,()), (0, Cg(w))
Vi2h (6)) Vo log no, (als)
7i
+ Egg
Vilon (s) ( + g(s,a) a) V/ (s)
Vo log no, (als)
VoJg(Ok)
T2
We will use the notation that (0x) = (0x), Sy (0x) Observe that
|Tol? o I| || (0.) I²) | 2 o (CREapp), and T3 (c)
(60)
where (a) follows from Assumption 4.4 and the boundedness of the feature map, é while (b) is consequence of Assumption 4.4 and 4.1 Finally, (c) is an application of Bellman's 's equation and the fact that ng (0x) J which can be easily verified. We get,
Egg (Ox: 2)] - (oJg(
- ok = o 115
+ Gfcapp)
(61)
Moreover, observe that, for arbitrary z ES x Ax8
Vodg < = Ee, VoJ, c5
-
(62)
where (a) results from Assumption 4.4 and the boundedness of d. We can, thus, conclude statements (c) and (d) by applying (61) and in Lemma B.2 To prove the statement (e), note that
Eou
Es
(0k, ch:
(Ox)
{ (o(s,a) En + (0g('') - (o)()), Ex Vo log To, (a/ss) (n),(0n)
Eo,
(a) Edp
{ (n((0))
Enlrğ] + (s) (s). EA (j(Oa)) Vo log To, (als)
To
+ Esg
Vinu (s) (0, + (0) (7(W))
Viaa (( V log Toe (als)
Ti
{ to (5)) + ((s) a) vith (s)
+ Egg
V
Vo log To. (a|s) - VoJ)((k))
22
Observe the following bounds.
|Tol (a) o (G) -
- =5(00)) ||T,11 (b) o (GReapp): and T2 (c) 0
(63)
29

---

where (a) follows from Assumption 4.4 and the boundedness of the feature map, & while (b) is consequence of Assumption 4.4 and Finally, (c) is an application of Bellman's 's equation. We get.
(0 E 2) Volg(0w) ||
- 82.g o (G+ |E (0x GiEap))
Ed
E
(64)
Using the above bound, we deduce the following.
E&
V
p (
g.hh
S 2 Ex
J. Jg.An]
- Boe
Ex [o (0xx Eg:
Eg:
ck: z)
+ |50
Ex (ody c5: <3:²) - (00)
w
2E Esnn (VLLMC Jg, - Esn VoJ $ 2) || + +0 (
0
(Tmix Taaxe o + k2.g)
where (a) follows from 644. (b) follows from Lemma B.2 a),
B.3
and the definition of o
Combining Lemma G.1 with Assumptions 4.4 and 4.5 we obtain the following for a given policy parameter 0 and Vig (r.c).
P [(0 S Gf, and [V 5 S (mix))
(65)
Combining the above results with Lemma 1 and invoking Theorem B.1
we then obtain given that
Tmax 2 8G and Tw I Tiix log Tiaa + 20 mir log Tmax)
ER [1ug w I exp (- H (w/l4) |l:00 , 1| + + + R1).
E& [ug] wg.b 1 S exp (- Hw |1:00 w 1
+ Pow +
O maxe G Tmax) { - wighll + + +
+Ra) R2) } + R2
112
where the terms Ro, R1, Rí are defined as follows.
Rg = ① (M -GGG + + G Es [|15*11 + 1 G9Ex [| - (0))))))) + p Cheapp)
R1 = p2- O (Imbatt G + Tim Tx |||=t11 "]
+ Ex [|I - {/ 11²] + Capp
R1 = O (Imdect+ 20%70 + T TaaaaG Gf E& [|ca51 [1]
Gf [ - ()(5 1² Gi(ppp)
Moreover, note that
Ex ||***|]]] < 2
[|ss (0)))) + 2 [12)011)]]]
(4)
2 Ex [|E (0x))) X +
where (a) uses (55) for sufficiently large e, and the definition that (Ga)) = (0,) by (Ox).
we set Yiu = 2lg T mH
I(6Gf Tani log I max 2207Tii
Tanis log Temax] we get
ER [|w@ wg.b 11]]
5 (())
1
(u
GG9-3 + 10 2x 2-22222-20 222
T Tiax
1
Ex |||5 - <5((0)1]]] + Eapp 1): WwO - - 112 + (n (u=30R/
+ 72
G mixx
EB [w/] wig.ell ? S pp =G0 (|Ealet] (Ba)) + cap
1l00 whuell
T2
12Tmax
TmTTmax 1 (R ||E -=((0))) + r GG T mix + 4 22 G2RGGR })
Girmix
+ +
30

---

Substituting wo = 0, I
G1Tmm G2Tm)) (follows from Lemma
=
and assumptions 4.4and 4.5)
we can simplify the above bounds as follows.
((
Girmix 1272
Ex |1u5 -W wg,1ll
2 G
+
+
H
Tinax
Gt
(0(())1 + capp }).
||E$)
+
(66)
122
1
Girmix 12T
GiT
||B W6gh wg
Eg (0x))11
tapp)
+
+
T
112
Girmis 1
EE
||55 (0+))
+ Gt mix
(67)
This completes the proof of Theorem
4.7
F
Proof of Main Theorems (Theorem 4.9 and Theorem 4.10)
F.0.1 Rate of Convergence of the Objective
Combining (6).
57 and (66) and
67
we obtain the following results.
G G
G mix
G
G Tmix
+ rappe) ))
Ex
||0 wigh
12222
112
227
2
G2
Gf mix
=
Capp
(68)
112
1A
Ex
wigk| | S
G2 Ö
12
X2T2
2
X
6 mix
Cppp
T2
1
1t [PTaxxx
Girmix
Gi 112
G4 GiG-Tin mix
+ Ō
Tiix
# T
X272
12222
G
G10 G mix
112
Eapp
12a2722
1 16A6Tmax
(69)
We can decompose (E [w]] - wlll and E wu
will ll using the definition that w/ = wa + Anat.. Using (88) and (69). and the fact that Au E [0, 2/0]. we obtain
2
G
GicyTmix
G9
(EE& [w>] wf)ll
1
Capp
+
(70)
μXT
G2
G9ctTa mix
Bllwa - will
1
δ
Capp
(71)
Setting Tmax = in 70 and 71p. and using Lemma G.2 and 26 in 25 would obtain
C(T",, L(Ok, Ne) s /Cbias ak Eandy [KL( [-I(="(-ss) (-|s) (-1s))
k=0
2 ④
G
G
+ +GG2 (
4
G
G9 mix
+ (1+
8
Vapp +
33A3//T
1
82
1ta
Capp
+
1 X4
((1+
G -i
+a0
gz
212
31

---

Using the definition of the Lagrange function, the above inequality can be equivalently written as
K
1
1
E
J
(1x) S Vbius +
E Band= [KL(
(-1s) (-1ss( To, (-1s))
K
ak
G2
G9 VT
+ +aG2 (1+ 82
Gi
GictTmis 3
mix
+
1+ 81
0
Eapp
+
Eapp +
112
+
a
((++
Gi miix n1
Σ
dk
(Jo - Jc(Oka)]
(72)
K
R=0
We will now extract the objective convergence rate from the convergence rate of the Lagrange function stated above. Note that,
0 S (Ax)² W
(AR41)2-(N)))
Piu.i1Ae - -Snt - (2x)²
K
[A B1/11 - -Axx)2
k=
(73)
K-1
K-1
23
AAR 32 Σ )
(a)
K-1
K-1 1
28
Au(JT - + 2,3
(n))²²
k=
k=
K-1
K
23
Σ
Au Jo(0w)) + 2,
Σ
Au (1)(((0)) vTa) + 2,3
(n
k=
k=
k=
Inequality (a) holds because 0 is feasible solution to the constrained optimization problem. Rearranging items and taking the expectation, we have
E Au - -.((0e)
S
1 K
Σ E
-ntt (J.()((k))
+
B K
B[n
(74)
K
Note that, unlike the discounted reward case, the average reward estimate of is no longer unbiased. and
However, by Theorem 4.8 and the facts that |c(s, a)) 1, V(s a) E S x A. and ni (0x) = J.(O... we get the following inequality.
K-1
E2
Aa(J= - Jc(0h))
<
E
d
(2()) - Edlrz() ) + B
K
K=0
k=0
K-1
Σ
I..
|
(((())))) Bx(r(() + (75)
K
A=0
+.3
X38VT
32

---

where the last inequality utilizes (57, the fact that A E [0,2/6], and Tmax T. Combining with we arrive at the following result.
K
1
1 aK
E
J
(0((
S Ebias +
E Bxndr [K
K
G2
G9 mix 1T
G ur²
Gict
mix
+
1+
Capp
+
+ aG2
|+
Fapp +
82
1d
a
((1
Girmix 11a
mix
+ Ô
Tmix
+ B
x²
138VT
VEbius +
Eapp + a + +
mix
(76)
aK
F.0.2 Rate of Constraint Violation
Given the dual update in algorithm
I we have
2 (a)
Ae 3Jo(0n) - 21
Ax+1
S
2 2
(Nx- 2
(8w)((%)
(77)
2
(Xe 2
A
(.k.((Ok)
+ 822
8
where (a) is because of the non-expansiveness of projection PA. Averaging the above inequality over k = O,.... K- yields
1 0 s K
AK-
2
1
Ao
2
28 K-1
Σ
(0x)
AAs
2 32
+
(78)
K
5
K
k=
Taking expectations on both sides,
K-1
2)
2)
2 2
2
B
Σ E Ja(As)
8
s
233
Ao
2
828K
2
(79)
where the last inequality utilizes Ao = O. Notice that A 2 0, Vk. Using the above inequality to therefore have,
K
E
J
(.((0))
K-1 Σ k=D
EE K
Jo(Ox)
5 Ebiaa +
2
+
B
K
8233K
k=0
2
G
G9c T
G
G9ct Tiix 1
I+
8
0
μ1
Vaapp
+
V3
aG2
1+ 82
112
app
a
((1
4
GiT n12
aK E
[KT
(T (-1s))
(80)
g²
We define a new policy से which uniformly chooses the policy no for E [K] By the occupancy measure method, Jy (0k) is linear in terms of occupancy measure induced by policy ne,- Thus,
Ā-1 Σ J.(0)) J3 ge fr.c)
(81)
K k=
33

---

Injecting the above relation to 80
we have
2
8 2
E
J
J
+
E
J
S Vebias
+
+
82,3K
2
G7
G9G Tmix
G
4 82
G
G9C 1 10111
+
1
0
v Capp
+ +aG2
1
0
Eppp +
8
13A3VT
+a0
((1+
I1
4
Gi mmix
1
E
snnd
[KL(T* (<[ssl() (+1s)]]
8²
n2
ak
By Lemma G.6 arrive at,
1
83 2
J
I 8 Chias +
+
83K
8)
G7
G9 mix
2 ( +2+
09
G9c4 mix
+
1+
2)
0
CCpp
n v
+GG2
2 (2 8
δ
u²
Capp
+
Timi 112
+
a
E
[KL(T* [-L()((-1>|] To (-o(s)]]
2
2a
Vebius + Vapp + + B
1
+
mix
2
(82)
aK
3K
VT
F.0.3 Optimal Choice of a, 8, K, and
If Tmix is unknown, we can take T 3 = T for some a, b E (0,1), and H = T K = T for (0, 1) then following (6) and (82. we can write,
K
J - J.(OW) - Ô (Vobias + Capp + T + T-b + T05 + T-1tcta),
E
K
0=
Σ Jo(Ok)
< 5 + Eapp = + +7 +7 l + I
Clearly, the optimal values of a and b can be obtained by solving the following optimization.
(a) min {a, b, - c ---,
(83)
By choosing (a, b) = (1/2, 1/2), this would obtain the solution of the above optimization problem. Thus, the convergence rate and constraint violation would both become:
K
E
J - J,(0z)
00
Vebias + /EapP + ((0.5-e)
(84)
K
k=U
E
(c(())
0 (Vesius + VEapp" + T(0.5-c)
1
(85)
k==
Recall that the above result holds when the conditions for Theorem 4.8 and Theorem 4.7 are satisfied.
2 log T
2
1
+
(86)
H
24c2 Tmix log Tmax
Tmix log T
log T
2
(87)
4(6G) Tmix log Trax T log Tmax)
T log
In light of the above conditions, and
85
hold if H = r ( If Tmix is known, we can Moreover, can take K O Thus, by following
set H = 2 that satisfies (86) and
87
34

---

the same analysis as above, we can obtain:
K
J
J.((ss)
Véhias + /eapp +
1
(88)
K
VT
0=
K
1
Jc(O%)
5 Vebiae + Eapp
(89)
K
vT)
k=0
This concludes the proof of Theorem
4.9 and Theorem 4.10
G Some Auxiliary Lemmas for the Proofs
Lemma G.1. 41 Lemma 14] For any ergodic MDP with mixing time Tmix, the following holds ((s S A. any policy and Vg {r,ch
(a) (+) S 5Tmix: (b) S 6Tmix;
-
Lemma G.2. For any ergodic MDP with mixing time Tmix, the following holds ((s, a) E S A any policy Te with 0g satisfying Assumption 4.4 the dual parameter 2ς E 2/6), and E (r,
12 σ Tmix G1
a Ved, S 61m (b)]V Ax)ll s (6
Proof. Using the policy gradient theorem
we have the following relation.
V (0k) (e Th
Qg * (s, a) V log Te, (als)
(90)
Applying Lemma G.I b) and Assumption 4.4 (),, we get
(o
B (sss)>= 2
Qg (s, Vo log no, (als)
Gr
(91)
Combining the above result with the definition of the Lagrange function and the bound that d S 2 we arrive at the following result.
VaL(Ox. Ax)I = (VJ,, A (ox)(
12
Ve., Au VoJo (6
8 Gi
(92)
This concludes the proof Lemma G.2
Lemma G.3 (Strong duality).
Lemma 3]
We restate the problem
below for convenience.
max J S.I. J 2 0 xell
(93)
where IT is the set of all policies. Define xt" an optimal solution to the above optimization problem. Define the associated dual function as
JB ma +J
(94)
TEll
and denote X = arg minx J. We have the following strong duality property for the unparame- terized problem.
J = JD
(95)
Lemma G.4 (Lemma 16. I0]. Consider the parameterized problem all parameters. Under Assumption 2.1 the optimal dual variable, X arg minx maXage J XJ for the parameterized problem can be bounded as follows.
where θ is the collection of
J J.
(96)
where n² an optimal solution the unparameterized problem 93 and 0 is a feasible parameter mentioned in Assumption 2.1
35

---

Notice that in Eq. [12) the dual update is projected onto the set [0, 3 because the optimal dual variable for the parameterized problem is bounded Lemma G.4 We note that our dual updating technique remains the same [00, however we were able to achieve an improvement of global convergence rate due the use of natural policy gradient and more prudent choice of stepsizes (),
Lemma G.S. Assume that the Assumption 2.1 holds. Define u(r) (J T where II the set of all policies. The following holds for any for the umparameterized problem as stated in Lemma G.3
where X is the optimal dual parameter
(0) - 2 (T)
(97)
Proof. Using the definition of ((T), we get v00) = J where x² is solution to the unparameterized problem (3). Denote [(TT, A) = J + AJ By the strong duality stated in Lemma G.3 we have the
following for any E II.
Def
[ X²) S max [IT,, X²) xell
v(0)
(98)
Thus, for any E t E III J 2 J). we can deduce the following.
v(0) - - > X1), - = J + (- - 2 J
(99)
Maximizing the right-hand side of this inequality over { E M 2 +} yields
(0) - - (T))
(100)
This completes the proof of Lemma G.5
Lemma G.6. Let Assumption 2.1 hold and (m",x* ,X) be the optimal primal and dual parameters for
the unparameterized problem (93). For any constant C 2 2X", there exist a π E II and Ç > 0 such that J - JØ + CI-Jal S. then
-J- $ 2C/C
(101)
Proof. Let = J We have the following inequality following the definition of v(T) provided in Lemma G.5
s(()
(102)
Combining Eq. 100) and (102 and using the fact that v(0) J we have the following inequality.
J - J. u(() v(0) - -
(103)
Using the condition in the Lemma, we have
(C x²)(-)) = + C(-r) -
(104)
Since C X C/2> finally have the following inequality.
S-
2
(-T) C- $
(105)
This completes the proof of Lemma G.6
36


Reviews:
[{"review_id": "RhnCDM4s8D", "reviewer": "Reviewer_srxr", "summary": "This paper studies the problem of learning optimal policies for infinite-horizon average-reward Constrained Markov Decision Processes (CMDPs) under general policy parameterizations. The authors propose a Primal-Dual Natural Actor-Critic (PDNAC) algorithm designed to manage constraints effectively while achieving global convergence guarantees. The algorithm reaches $\\tilde{O}(1/\\sqrt{T})$ rates for both optimality gap and constraint violation when the mixing time $\\tau_{\\text{mix}}$ is known. When without this knowledge, the algorithm achieves rates arbitrarily close to the theoretical lower bound, improving significantly over the previous best $\\tilde{O}(1/T^{1/5})$ rate. The results derive from a multi-timescale nested-loop design, careful tuning of learning rates, and an application of Multi-Level Monte Carlo (MLMC) methods.", "questions": "see weakness", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths\n1. The paper presents a model-free algorithm that achieves a convergence rate of $\\tilde{O}(1/\\sqrt{T})$ in both reward suboptimality and constraint violation. This matches the known information-theoretic lower bound for average-reward CMDPs and substantially improves upon existing results, which only attain rates like $\\tilde{O}(1/T^{1/5})$.\n2. Even when the mixing time $\\tau_{\\text{mix}}$ is unknown, the algorithm still achieves a near-optimal rate of $\\tilde{O}(1/T^{0.5 - \\epsilon})$, under mild assumptions on the time horizon. This makes the method more practically applicable, as $\\tau_{\\text{mix}}$ is rarely known in real-world settings.\n3. The analysis is conducted under general policy parameterization, as opposed to the more tractable linear or tabular cases considered in prior work. This broadens the applicability of the results to large-scale or continuous-state environments and makes the theoretical contributions more meaningful.\n\nWeaknesses\n1. The proposed method primarily combines existing components—natural actor-critic updates, primal-dual optimization, and MLMC estimation—without introducing fundamentally new algorithmic primitives.\n2. The algorithm requires prior knowledge of the Slater constant $\\delta$ to project the dual variable $\\lambda$ into a bounded region $[0, 2/\\delta]$. This is a relatively strong assumption in practice.\n3. The paper assumes the cost function is bounded in $[-1, 1]$, while the reward function may differ in scale. Could the authors explain it?\n4. Some typos: Line 101: $\\bcancel{the}. Line 141: “occupation” -> “occupancy”. Line 180: “utilizes” -> “utilize”.", "was_revised": true, "final_justification": "The paper is well-written, well-motivated and has a strong theoretical result. Therefore, I believe this paper should be accepted.", "rebuttal": "We thank the reviewer for the constructive review. Please find our responses below. \n\n**Algorithmic novelty**: Our primary novelty lies in achieving an optimal-order convergence rate for average reward Constrained Markov Decision Processes (CMDPs) with general policy parameterization, which was previously unresolved in the literature.\n\nWe indeed leverage the natural actor-critic framework in conjunction with the MLMC-based estimation technique, which recently has obtained an order-optimal convergence rate in the unconstrained setup [1]. However, directly applying these techniques to constrained MDPs by integrating a primal-dual approach does not yield the same optimal convergence rate. The key challenge arises from introducing the dual variable, which significantly complicates the convergence analysis. Specifically, as highlighted in Eq. (79,82) in our paper, the dual learning rate $\\beta$ appears in both the numerator and denominator of the convergence bounds. Therefore, merely following the unconstrained setting by choosing $\\beta$ inversely proportional to $T$ fails to replicate the optimal convergence rate achieved in the unconstrained case.\n\nThis fundamental challenge has also been observed in the literature. For example, [2] addresses the unconstrained average reward RL and achieves a convergence rate of $ \\tilde{O}(T^{-1/4}) $, while [3] deals with the constrained counterpart, achieving a slower rate of $ \\tilde{O}(T^{-1/5})$.\n\nOur work addresses these critical challenges through a sharper and more refined analytical approach. We specifically modify both the primal and dual learning rate to scale inversely with the square root of $T$, a significant departure from the constant primal learning rate used in the unconstrained analyses ([1] and [2]). Additionally, we introduce a refined error bound for the Lagrangian (last expression on Page 30) and strategically set the inner-loop complexity to be nearly logarithmic in $T$. These innovative technical modifications enable us to overcome the identified challenges and achieve the first optimal-order convergence rate for the average reward constrained RL setting.\n\n**Knowledge of Slater's constant:** We would like to point out that almost all primal-dual algorithms in the literature, to the best of our knowledge, assume access to Slater's constant $\\delta$ (see, e.g., [3], [4]) to define the dual projection operator. Nevertheless, we agree with the reviewer's concern that the value of $\\delta$ might be unknown for most practical scenarios. In such a case, $\\delta$ can be taken as a hyperparameter of the algorithm, which needs to be fine-tuned during the training period. This is in line with many RL algorithms in the literature that also require fine-tuning of several unknown hyperparameters, such as the Lipschitz constant, mixing time, or hitting time for effective implementation [2]. In other words, the issue of fine-tuning is not unique to $\\delta$, but common across the RL literature. Since $\\delta$ is such that $J_c^{\\pi}\\geq \\delta$ for $\\textit{some}$ policy $\\pi$, a coarse estimate of $\\delta$ can be obtained by computing an estimate of $J_c^{\\pi}$ for some arbitrarily chosen policy $\\pi$.\n\n**Scaling of reward and cost functions:** The reward function is typically assumed to be bounded, which allows us to choose $[0, 1]$ as its range without loss of generality. Note that the constraint in our optimization problem is of the form $J_c^{\\pi}\\geq 0$. Therefore, if the range of the cost function is chosen as either $[0, 1]$ or $[-1, 0]$, then the constraint would either be obeyed by all policies or no policies at all. Both of these cases would lead to trivial solutions. To avoid this problem, we have chosen the range of the cost function to be $[-1, 1]$. \n\n**Typos:** Thank you for pointing out the typos. We will correct those in the revised manuscript.\n\n**References:**\n    \n[1] \"A sharper global convergence analysis for average reward reinforcement learning via an actor-critic approach.\" ICML 2025.\n\n[2] \"Regret analysis of policy gradient algorithm for infinite horizon average reward Markov decision processes.\" AAAI 2024.\n\n[3] \"Learning general parameterized policies for infinite horizon average reward constrained MDPs via primal-dual policy gradient algorithm.\" NeurIPS 2024.\n\n[4] \"Sample-efficient constrained reinforcement learning with general parameterization.\" NeurIPS 2024."}, {"review_id": "kHHLYEJPRZ", "reviewer": "Reviewer_R19r", "summary": "The paper introduces Primal-Dual Natural Actor-Critic (PDNAC), a model-free algorithm for infinite-horizon average-reward constrained MDPs (CMDPs) with general policy parametrisation. By combining natural policy gradients with a carefully tuned primal-dual update and multi-level Monte-Carlo (MLMC) estimators, PDNAC attains a global convergence and constraint-violation rate of $\\tilde{O}(T^{-1/2})$ when the mixing time is known, and $\\tilde{O}(T^{-0.5+\\varepsilon})$ otherwise, matching the information-theoretic lower bound and outperforming the previous $\\tilde{O}(T^{-1/5})$ state of the art. Key ingredients are (i) a nested loop that behaves like a single-timescale update, (ii) MLMC critics that keep the bias low even with very short inner loops, and (iii) a tight finite-time analysis that isolates approximation error terms ($\\varepsilon_{bias}, \\varepsilon_{app}$) so they do not dominate asymptotics.", "questions": "How sensitive is PDNAC to mis-specifying the inner-loop length $H$ when $\\tau_{mix}$ is unknown?", "limitations": "The authors did not create Limitations section", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Strengths\n- Rigorous finite-time proofs that reach the lower bound for both objective gap and constraint violation (Theorems 4.9-4.10).\n- Clear comparison against a wide range of baselines (Table 1).\n- Solid justification of why naïve primal-dual tuning fails and how natural gradients fix the $\\beta$-variance trade-off.\n- Closes the long-standing gap between achievable and optimal rates for general-param CMDPs.\n- Removes the need for mixing-time knowledge at only $\\varepsilon$-slack cost—important for large, unknown environments.\n- Techniques (nested MLMC + natural gradients) could influence broader safe-RL literature.\n\n# Weaknesses\n- When $\\tau_{mix}$ is unknown, the horizon requirement $T \\gtrsim \\tilde{O}(\\tau_{mix}^{2/\\varepsilon})$ can be prohibitive.\n- Assumes ergodicity and a linear critic with bounded approximation error; real tasks may violate these.", "was_revised": false, "final_justification": "", "rebuttal": "**On prohibitive horizon length:** We agree that, for small $\\epsilon$ and unknown $\\tau_{\\mathrm{mix}}$, the length of the required horizon length $T$, as stated in Theorem 4.10, can indeed be very large. In such a scenario, one can switch to the parameter setting of Theorem 4.9, which does not impose any such restriction on $T$. However, since this setup requires the knowledge of $\\tau_{\\mathrm{mix}}$, one can treat $\\tau_{\\mathrm{mix}}$ as one of the unknown hyperparameters of the algorithm, and fine-tune it during the training phase. This is in line with other RL algorithms in the literature that also require fine-tuning of several unknown hyperparameters, such as the Lipschitz constant or hitting time [1]. Despite these practical solutions, we acknowledge that a systematic theoretical investigation is needed to improve the requirement of the horizon length, $T$ (in the absence of knowledge of $\\tau_{\\mathrm{mix}}$). We will include it as one of the future works in the revised paper. \n\n**On the assumption of ergodicity:** The assumption of ergodicity ensures that any state of the MDP is achievable from any other state via some policy. This ensures that a well-designed algorithm can sufficiently explore the state space and obtain a near-optimal policy exploiting the convergence of the policy-induced Markov chain to a stationary distribution. Therefore, it is no surprise that ergodicity is one of the most commonly employed assumptions in the RL literature (see the discussion following Assumption 2.2 in our paper). Extending the analysis to beyond-ergodic MDPs is extremely difficult, and a few works that are available in this direction primarily target tabular policies in the unconstrained setup. Designing algorithms achieving optimal convergence rates for beyond-ergodic CMDPs with general parameterized policies is currently an open question.\n\n**On the linear critic approximation error:** Bounded linear critic approximation error is one of the commonly employed assumptions in the actor-critic literature. Please refer to the discussion following Assumption 2.2 for an overview of the relevant works. Apart from being important from a theoretical perspective, such a framework also yields good numerical results in experiments, as demonstrated in [2]. Despite these successes, we acknowledge that it is important to extend the analysis to non-linear critic to widen the applicability of the algorithm. Although some recent results are available in this direction [3], they primarily target unconstrained discounted reward setups. Moreover, their algorithms and analysis techniques are vastly different from ours. Whether similar analyses can be performed for constrained average reward settings is currently an open question.\n\n**Sensitivity of PDNAC to misspecifying $H$ with unknown $\\tau_{\\mathrm{mix}}$:** Theorem 4.10 states that if $\\tau_{\\mathrm{mix}}$ is unknown, then one can choose $H=T^{\\epsilon}$ for some $\\epsilon>0$ which results in objective convergence and constraint violation rates of $\\tilde{\\mathcal{O}}(T^{-1/2+\\epsilon})$ for sufficiently large $T$. Hence, if $H$ is misspecified as $H=T^{\\epsilon+\\Delta \\epsilon}$ for some small error $\\Delta\\epsilon$, then the convergence rates are modified by a factor of $\\tilde{\\mathcal{O}}(T^{\\Delta\\epsilon})$.\n\n**References:**\n\n[1] ``Regret analysis of policy gradient algorithm for infinite horizon average reward Markov decision processes'', AAAI 2024.\n\n[2] ``Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Critic'', ICML 2023.\n\n[3] ``Order-optimal global convergence for actor-critic with general policy and neural critic parametrization'', UAI 2025."}, {"review_id": "mLSnMhOjAE", "reviewer": "Reviewer_Wxi5", "summary": "This paper studies infinite-horizon average reward Constrained Markov Decision Processes (CMDPs) with a smooth policy with bounded gradients. It proposes Primal-Dual Natural Actor-Critic with the global convergence rate of $1/\\sqrt{T}$, which significantly improves the existing convergence rates for the considered setting and matches the lower bound.", "questions": "It is not clear what is a technical novelty beyond tuning the problem parameters and a sharper analysis. Would you elaborate on it?", "limitations": "It is nice to discuss the constraint violation of the proposed method. Currently, the proposed method violates the constraint, and it is not practical to directly use this method for safety critical applications.\n\nAlso, by \"general\" policies, the paper refers to a policy with smooth and bounded gradients. It would be nice to be more specific and call the considered policy class as smooth policies with bounded gradients in the title and abstract.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "# Strength\n\nThe paper provides a solid theoretical result in safe RL with flexible policy parameterization. The proposed algorithm has a significantly better global convergence rate compared to existing results in terms of the number of steps $T$.\n\n# Weakness\n\nIt is not clear what is a technical novelty beyond tuning the problem parameters and and a sharper analysis. For example, it is written that \"Achieving this challenging goal is made possible due to the use of Multi-level Monte Carlo (MLMC)-based estimates in the inner loop subroutines and a sharper analysis of these update\", but is there any technical novelty or challenges in the sharper analysis? Current techniques seem to be mainly borrowed from Ganesh et al. 2024.\n\nFurthermore, although the convergence rate is much better than previous results, it is still unclear how close the obtained results are to a lower bound.\n\nBecause of these points, the significance of the paper is difficult to evaluate for me.", "was_revised": true, "final_justification": "While the paper provides a theoretically solid analysis and algorithm, the analysis is not fully convincing to me in that it uses the definition of constraint violation not really appropriate for safety critical situation. Therefore, I keep my score of 4.", "rebuttal": "**Technical novelty:** Our primary novelty lies in achieving an optimal-order convergence rate for average reward Constrained Markov Decision Processes (CMDPs) with general policy parameterization, which was previously unresolved in the literature.\n\nWe indeed leverage the natural actor-critic framework in conjunction with the MLMC-based estimation technique, which recently has obtained an order-optimal convergence rate in the unconstrained setup [1]. However, directly applying these techniques to constrained MDPs by integrating a primal-dual approach does not yield the same optimal convergence rate. The key challenge arises from introducing the dual variable, which significantly complicates the convergence analysis. Specifically, as highlighted in Eq. (79,82) in our paper, the dual learning rate $\\beta$ appears in both the numerator and denominator of the convergence bounds. Therefore, merely following the unconstrained setting by choosing $\\beta$ inversely proportional to $T$ fails to replicate the optimal convergence rate achieved in the unconstrained case.\n\nThis fundamental challenge has also been observed in the literature. For example, [2] addresses the unconstrained average reward RL and achieves a convergence rate of $ \\tilde{O}(T^{-1/4}) $, while [3] deals with the constrained counterpart, achieving a slower rate of $ \\tilde{O}(T^{-1/5})$.\n\nOur work addresses these critical challenges through a sharper and more refined analytical approach. We specifically modify both the primal and dual learning rate to scale inversely with the square root of $T$, a significant departure from the constant primal learning rate used in the unconstrained analyses ([1] and [2]). Additionally, we introduce a refined error bound for the Lagrangian (last expression on Page 30) and strategically set the inner-loop complexity to be nearly logarithmic in $T$. These innovative technical modifications enable us to overcome the identified challenges and achieve the first optimal-order convergence rate for the average reward constrained RL setting.\n\n**Relation to lower bound:** As mentioned in Table 1 in the paper, the theoretical lower bound on the global convergence rate is $\\Omega(T^{-1/2})$ where $T$ indicates the horizon length. Theorems 4.9 and 4.10 in our paper establish convergence rates of $\\tilde{\\mathcal{O}}(T^{-1/2})$ and $\\tilde{\\mathcal{O}}(T^{-1/2+\\epsilon})$ for arbitrarily small $\\epsilon$. Therefore, not only do our results vastly improve upon the state-of-the-art convergence rates, but they nearly match the theoretical lower bound as well.\n\n**On constraint violation:** Our algorithm can achieve a small average constraint violation, provided that the horizon length $T$ is sufficiently large and the errors due to policy and critic approximations are negligible. That being said, we agree with the reviewer that in some safety-critical applications, even a small constraint violation is undesirable. To force the constraint violation to zero, we can resort to a standard ``trick'' commonly used in constrained RL literature. The main idea is to consider a stringent constraint of the form $J_c^{\\pi}\\geq \\eta>0$ in the algorithm, instead of the formulated constraint $J_c^{\\pi}\\geq 0$. Now, the hyperparameter $\\eta$ can be appropriately chosen so that our desired constraint violation is forced to zero. Please see section H.5 of [4] for a detailed exposition. Similar ideas are also discussed in [5]. Hence, one can extend a small constraint violation result to a zero one with some additional assumption, and we leave it as future work. \n\n**On general policies:** The class of policies considered in the paper is called ``general'' because it contains various commonly used policy classes such as tabular, softmax, log-linear, neural, etc., as special cases. This terminology is common across the RL literature [6], [7]. We believe that renaming the general policy class as policies with smooth and bounded gradients would de-emphasize the generic applicability of our results. Therefore, instead of renaming it in the title, we will mention the smoothness and boundedness properties of the policy gradients in the abstract and introduction of the revised paper.\n\n**References:**\n    \n[1] \"A sharper global convergence analysis for average reward reinforcement learning via an actor-critic approach\", ICML 2025.\n\n[2] \"Regret analysis of policy gradient algorithm for infinite horizon average reward Markov decision processes\", AAAI 2024.\n    \n[3] \"Learning general parameterized policies for infinite horizon average reward constrained MDPs via primal-dual policy gradient algorithm\", NeurIPS 2024.\n\n[4] ''Achieving sub-linear regret in infinite horizon average reward constrained MDP with linear function approximation'', ICLR 2023.\n\n[5] ''Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approach'', AAAI 2022.\n\n[6] ''Sample-Efficient Constrained Reinforcement Learning with General Parameterization'', NeurIPS 2024.\n\n[7] ''A novel framework for policy mirror descent with general parameterization and linear convergence'', NeurIPS 2023."}, {"review_id": "1UniYieQap", "reviewer": "Reviewer_HvUC", "summary": "This paper studies infinite-horizon average reward constrained MDPs with general parametrization. It proposes a primal-dual natural actor-critic approach that achieves global convergence and constraint violation of $\\tilde{O}(1/\\sqrt{T})$ if the mixing time is known, and $\\tilde{O}(1/T^{0.5-\\epsilon})$ it the mixing time is unknown, improving the SoTA for general policy parametrization in both cases.", "questions": "Minor issues and clarifications:\n\n* In equation (13), why does $\\nu_g^{\\pi_{\\theta_k}}$ depend on $g$? Isn’t this just the state-action distribution under policy $\\pi_{\\theta_k}$? \n* Page 5, line 158: \"feaure\" → \"feature\"\n* Page 7, line 223, item (b): $\\pi_\\theta$ → $\\pi_{\\theta_1}$", "limitations": "yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n* The paper is well-written, and the problem is well-motivated\n* This result improves upon previous bounds in the same setting and is the first to propose and analyze an approach for the infinite-horizon average-reward C-MDP problem when the mixing time is unknown.\n* The paper does a good job on discussing the difficulties of applying a primal-dual actor-critic approach in a setting with constraints, in particular the difficulties in estimating the critic parameters. \n\n**Weaknesses**:\n* The final regret and constraint bounds depend on $\\epsilon_{\\text{bias}}$, which reflects the expressiveness of the policy class $\\pi_\\theta$, and on $\\epsilon_{\\text{app}}$, which captures the quality of the feature map. Both terms contribute linearly in $T$ to the bounds due to this dependency. While the authors argue that $\\epsilon_{\\text{bias}}$ can be made small with sufficiently expressive neural networks, the assumption that $\\epsilon_{\\text{app}}$ is negligible appears less justified. It would be helpful if the authors explicitly noted in Table 1 or in the main text that the quality of the regret bounds has this dependency that may be linear in $T$ if the feature map is not good, otherwise the claims are a little misleading. This raises two important questions that I think should be addressed in the paper:\n  * How realistic is it to obtain a good feature map in practice?\n  * If the linear value function approximation is relaxed, can similar bounds still be obtained?\n\n* Another claim of the paper is that the one of the proposed approaches does not require prior knowledge of the mixing time and is the first to address this challenge in the context of infinite-horizon average-reward C-MDPs. This is achieved through the use of Multi-Level Monte Carlo (MLMC). However, the analysis closely resembles that of [31] and Patel et al. (2024), yet neither is recognized. This omission gives the impression that the authors are the first to introduce these ideas for handling unknown mixing times.\nUnless I am mistaken, I strongly recommend that the authors cite these related works when discussing MLMC and clearly explain how their analysis is extended or adapted to address the constrained setting.\n\n*Patel et al., Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles, 2024*", "was_revised": true, "final_justification": "I decided to maintain my positive score, as the authors have addressed all my concerns regarding the dependence of the regret bound on $\\epsilon_\\text{bias}$ and $\\epsilon_\\text{app}$, and I hope they will consider including these dependencies in Table 1. They also responded to my comments on related work, and I trust they will incorporate this discussion to help clarify the comparison for future readers.", "rebuttal": "**Dependence of the bounds on $\\epsilon_{\\mathrm{bias}}$ and $\\epsilon_{\\mathrm{app}}$:** Thank you for pointing this out. We will mention the dependence of the convergence rates on $\\epsilon_{\\mathrm{bias}}$ and $\\epsilon_{\\mathrm{app}}$ in the main text as well as in Table 1 in the revised manuscript.\n\n**On good feature maps:** We would like to emphasize that the concept of linear function approximation is not only a common assumption for the actor-critic algorithms, but it is also central to the rich literature of linear MDPs [1]. Although there is no consensus, to the best of our knowledge, on how to build feature maps for a generic task, several task-dependent features have been reported in the literature [2], [3] that perform well in experiments. Hence, it is quite practical to assume that the learner has access to a good feature map.\n\n**On nonlinear value function approximation:** The benefit of linear critic approximation is that both the NPG and the critic updates can be described as stochastic linear recursions (SLRs). This allows us to utilize Theorem B.1, which is crucial in obtaining the optimal convergence rates. Extending these results to non-linear critic approximation is extremely challenging since the convergence analysis of SLRs can no longer be applied. Very recently, [4] has provided a regret analysis with non-linear critic approximation in the unconstrained discounted reward setup. However, they introduce a data-drop technique and do not use the MLMC-based estimation, which is central to our work. Whether their approach can be extended to the constrained average reward scenario is currently an open question.\n\n**Relation to [31] and (Patel et al.):** We agree that there are some similarities between our algorithm and that proposed by the cited papers. For example, MLMC-based estimation and linear critic approximation are central to all of these papers. Despite these apparent similarities, there are some crucial differences. For example, both of the cited papers analyze unconstrained setups, liberating them from the nuances of dual projection and its parameter optimization. Secondly, unlike our paper, [31] merely guarantees convergence to a first-order stationary point. Although (Patel et al.) guarantees global convergence, their established rate $\\tilde{\\mathcal{O}}(T^{-1/4})$ is nowhere near the theoretical lower bound $\\Omega(T^{-1/2})$. Thirdly, the set of assumptions used in [31] is different than ours. For example, Assumption 4.2(3) used in [31] is not needed in our analysis. Finally, the analysis of stochastic linear recursions (SLRs), which is central in our paper (Theorem B.1), is present in neither of the cited papers. Hence, although we are not the first to remove dependence on the knowledge of $\\tau_{\\mathrm{mix}}$ using MLMC (though we are the first to do so in the CMDP setup), our analysis is not an adopted version of that presented in either of the cited papers. We will include a summary of the above comparison in the revised manuscript.\n\n**Typos:** Thank you for pointing out the typos. We will correct those in the revised manuscript.\n\n**References:**\n\n[1] ''Provably efficient reinforcement learning with linear function approximation'', COLT 2020.\n\n[2] ''Making Linear MDPs Practical via Contrastive Representation Learning'', ICML 2022.\n\n[3] ''Achieving sub-linear regret in infinite horizon average reward constrained MDP with linear function approximation'', ICLR 2023.\n    \n[4] ''Order-optimal global convergence for actor-critic with general policy and neural critic parametrization'', UAI 2025."}]

Author rebuttal:

Meta-review: This paper proposes Primal-Dual Natural Actor-Critic (PDNAC) for infinite-horizon average-reward CMDPs, achieving order-optimal convergence rates for both optimality gap and constraint violation. Reviewers agreed it is technically solid, closes a key gap in constrained RL, and improves substantially over prior work. Concerns about novelty, assumptions (e.g., Slater constant, ergodicity, linear critic approximation), and the definition of constraint violation were partly resolved in rebuttal. Overall, the work makes a nice theoretical advance and is recommended for acceptance.
Decision: Accept (poster)