Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm
Authors: Qinbo Bai
Washim Uddin Mondal
Vaneet Aggarwal
Venue: NeurIPS 2024 poster (2024)
Keywords: Average Reward MDP
Constraint Violation
Regret.
Primary area: reinforcement_learning
TL;DR: Regret and constraint violation analysis of infinite horizon average reward constraint MDP.

Abstract: This paper explores the realm of infinite horizon average reward Constrained Markov Decision Processes (CMDPs). To the best of our knowledge, this work is the first to delve into the regret and constraint violation analysis of average reward CMDPs with a general policy parametrization. To address this challenge, we propose a primal dual-based policy gradient algorithm that adeptly manages the constraints while ensuring a low regret guarantee toward achieving a global optimal policy. In particular, our proposed algorithm achieves $\tilde{\mathcal{O}}({T}^{4/5})$ objective regret and $\tilde{\mathcal{O}}({T}^{4/5})$ constraint violation bounds.

Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm
Qinbo Bai Purdue University West Lafayette, IN 47906 bai1130purdue.co edu
Washim Uddin Mondal Indian Institute Technology Kanpur Kanpur, UP, India 208016 wmondal Setaaaliiiii... ac.
Vaneet Aggarwal Purdue University West Lafayette, IN 47906 vaneet edu
Abstract
This paper explores the realm of infinite horizon average reward Constrained Markov Decision Processes (CMDPs). To the best of our knowledge, this work is the first to delve into the regret and constraint violation analysis of average reward CMDPs with general policy parametrization. To address this challenge, we propose primal dual-based policy gradient algorithm that adeptly manages the constraints while ensuring a low regret guarantee toward achieving a global optimal policy. In particular, our proposed algorithm achieves (TT4/5) objective regret and ((r4/5) constraint violation bounds.
Introduction
The framework of Reinforcement Learning (RL) is concerned with class of problems where an agent learns to yield the maximum cumulative reward in unknown environment via repeated interaction. RL finds applications diverse areas, such as wireless communication, transportation, and epidemic control 2 3. RL problems are mainly categorized into three setups: episodic, infinite horizon discounted reward, and infinite horizon average reward. Among them, the infinite horizon average reward setup particularly significant for real-world applications. It aligns with most of the practical scenarios and captures their long-term goals. Some applications in real life require the learning procedure respect the boundaries of certain constraints. In an epidemic control setup, for example, vaccination policies must take the supply shortage (budget constraint) into account. Such restrictive Docision-making routines are described by constrained Markov Decision Processes (CMDP) 5 Existing papers on CMDPs utilize either tabular or a linear MDP structure. This work provides the first algorithm for an infinite horizon average reward CMDP with general parametrization and proves its sub-linear regret and constraint violation bounds.
There two primary ways solve CMDP problem in the infinite horizon average reward setting. The first one, known as the model-based approach, involves constructing estimates of the transition probabilities of the underlying CMDP, which are subsequently utilized derive policies (6] 7 5).
The caveat of this approach is the large memory requirement to store the estimated parameters. which effectively curtails its applicability to CMDPs with large state spaces. The alternative strategy, known as the model-free approach, either directly estimates the policy function or maintains an estimate of the function, which is subsequently used for policy generation (8) Model-free algorithms typically demand lower memory and computational resources than their model- counterparts. Although the CMDP has been solved in a model- -reee manner in the tabular [8) and linear 9 setups, its exploration with the general parameterization is still open and is the goal of this paper.
General parameterization indexes the policies by finieeddimensional parameters (e.g., weights of neural networks) to accommodate large state spaces. The learning is manifested by updating these
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Algorithm
Regret
Violation Õ(vT)
Model-free
Setting
Algorithm 1 in 6
((VT)
No
Tabular
Algorithm 2 in 6
O(T2/S)
O(T2/S)
No
Tabular
UC-CURL and PS-CURL. [5]
Ö(VT)
0
No
Tabular
Algorithm 2 in 9
((dT))//4)
((dT)3//4
No
Linear MDP
Algorithm 3 in 9
Õ(VT)
Õ(VT)
No
Linear MDP
Triple-QA 8
Ö(T5/6)
0
Yes
Tabular
This paper
Ō(T+)
Ö
Yes
General Parameterization
Table 1: This table summarizes the different model- based and mode-fre free-frre sfate-of-the-art algorithms available in the literature for average reward CMDPs. We note that proposed algorithm is the first to analyze the regret and constraint violation for average reward CMDP with general parametrization. Here, the parameter refers to the dimension of the feature map for linear MDPs.
parameters using policy gradient (PG)-type algorithms. Note that PG algorithms are primarily studied in discounted reward setups. For example, [IO] characterizes the sample complexities of the PG and the Natural PG (NPG) algorithms with softmax and direct parameterization. Similar results for general parameterization are obtained by 11 The regret analysis of a PG algorithm with the general parameterization has been recently performed for an infinite horizon average reward MDP without constraints [13. Similar regret and constraint violation analysis for the average reward CMDP still missing in the literature. In this paper. we bridge this gap.
Challenges and Contribution: We propose a PG-hased algorithm with general parameterized policies for the average reward CMDP and establish its sublinear regret and constraint violation bounds. In particular, assuming the underlying CMDP to be ergodic, we demonstrate that our PG algorithm achieves an average optimality rate of Ō(T- and average constraint violation rate of B( Invoking this convergence result, we establish that our algorithm achieves regret and constraint violation bounds of + Apart from providing the first sublinear regret guarantee for the average reward CMDP with general parameterization, our work also improves the state-of-the-art regret guarantee, ((T6/6) in the model-free tabular setup g
Despite the availability of sample complexity analysis of PG algorithms with constraints in the discounted reward setup [4| 4 and PG algorithms without constraint average reward setup [3]. obtaining sublinear regret and constraint violation bounds for their average reward counterpart is challenging.
[14 solely needs an estimate of the value function V while we additionally need the estimate of the gain function, J.
assume access to a simulator to generate unbiased value estimates. In contrast, our algorithm uses a sample trajectory of length H to estimate the values and gains and does not assume the availability of a simulator.
The first-order convergence analysis (Lemma 6) differs from that in [13. Note that both of these papers use an ascent-like inequality. In [33, this bounds the term 10 - (Ox). The final result is obtained by calculating a sum over k which cancels the intermediate terms and leaves us with J(0x) ) (01). We would like to emphasize that the cancellation of the intermediate terms is crucial to establishing the result. However, a similar effort in our case only leads to a bound of (0x+11 Ax) - JL (Ok, >z). Note that directly performing a sum over this difference does not lead to the cancellation of intermediate terms. We had to take a different route and apply the bounds of the Lagrange multipliers and the estimate of the constraint function to achieve that goal.
After solving the problems mentioned above, we prove O convergence rate of the Lagrange function. Unfortunately, the strong duality property, which is central to proving convergence results of CMDPs for tabular and softmax policies, does not hold under the general parameterization. As result, the convergence result for the dual problem does not automatically translate to that for the primal problem. which is a main difference from [3). We overcome this barrier by introducing a novel constraint violation analysis and a series of intermediate results (Lemma I8] that help disentangle the regret and constraint violation rates from the Lagrange convergence. It is important to mention that although the techniques applied are inspired by the (14), those techniques cannot be directly adopted for average reward MDPs. This is primarily because the estimate (Ox)) ) is biased in the average case. To the best of our knowledge, constraint violation analysis with a biased estimate of the cost value is not available in the literature and is performed for the first time in our paper.

---

Due to the presence of the Lagrange multiplier, the convergence amalysis of CMDP much more convoluted than its unconstrained counterpart. The learning rate the Lagrange update, 3. turns out to be pivotal in determining the growth rate of regret and constraint violation. Low values of / push the regret down while simultaneously increasing the constraint violation. Finding the optimal value of (3 that judiciously balances these two competing goals is one of the comnestones of our analysis.
Related work for unconstrained average reward RL: In the absence of constraints, both model- based and model-free tabular setups have been widely studied for infinite horizon average reward MDPs. For example, the model- algorithms proposed by [5]] 16 achieve the optimal regret bound of OVVT). Similarly, the model-free algorithm proposed by 17 for tabular MDP results in ((VT)) regret. Regret analysis for average reward MDP with general parametrization has been recently studied in [3], where regret bound of Ó(T3/1) is derived.
The constrained reinforcement learning problem has been extensively studied both for infinite horizon discounted reward and episodic MDPs. For example. discounted reward CMDPs have been recently studied in the tabular setup 18 with both softmax investigated
Related work for constrained RL:
and general policy parameterization episodic CMDPs in the tabular setting.
14 19
12
Moreover, 20
Recently, the infinite horizon average reward CMDPs have been investigated in model-based setups 6 7) tabular model-free setting [ and linear CMDP setting (9. For model-based CMDP setup, 6 proposed model-based online mirror descent algorithm in the ergodic setting which achieves ((VT) for regret and violation at the same time. 7 proposed algorithms based on the posterior sampling and the optimism principle that achieve (V'T)) regret with zero constraint violations in the ergodic setting. However, the above model- basee algorithms cannot be extended to large state space. In the tabular model-free setup, the algorithm proposed by K achieves regret of (TT5/9) with zero constraint violations. Finally, in the linear CMDP setting, [9] achieves Ó( (VTT) regret bound with zero constraint violation. Note that the linear CMDP setting assumes that the transition probability has certain linear structure with known feature map which is not realistic. Table [ summarizes all relevant works. Unfortunately, none of these papers study the infinite horizon average reward CMDPs with general parametrization which is the main focus of our article.
Additionally, for the weakly communicating setting, 6 proposed a model-based algorithm achieving O(T2/3) for both regret and violation in tabular case. [ further extends such result to linear MDP setting with ((73/44 regret and violation. In general, it is difficult to propose a model-free algorithm with provable guarantees for Constrained MDPs (CMDPs) without considering the ergodic model. (6) pointed out several extra challenges in Weakly communicating MDP compared to the ergodic case. For example, there is no uniform bound for the span of the value function for all stationary policies. It is also unclear how to estimate a policy's bias function accurately without the estimated model, which is an important step for estimating the policy gradient.
2 Formulation
This paper analyzes infinite- horizze average reward constrained Markov Decision Process (CMDP) denoted as M = (S, A,,,,,
c, P) [0, 1] is the reward function, S A 1, 1] is the constraint cost function, P:S x A A [S] is the state transition function where A (s denotes probability simplex with dimension [S]. and E AS is the initial distribution of states. A policy π E II: S + A maps the current state to an action distribution. The average reward and cost of a policy, n, is,
where denotes the state space. A is the action space of size
A S x A
J
lim T
Σ
g( az) 1=0
8o ~ P
where g = r, c for average reward and cost respectively. The expectation is calculated over the distribution of all sampled trajectories ((s), where a, T(s),, $141 ~ P(-ls,, az), Vt e {0, ). For notational convenience, we shall drop the dependence on p whenever there is no confusion. Our goal is to maximize the average reward function while ensuring that the average cost is above given threshold. Without loss of generality, we can mathematically write this problem as,
}.
max JH s.t. J 2 0 *ell
(2)
3

---

However, the above problem becomes difficult to handle when the underlying state space, S is large. Therefore, we consider class of parametrized policies, { & E )) whose elements are indexed by d-dimensional parameter, 0 E _ where < [S||A]] Thus, the original problem in Eq 2 can be
reformulated as the following parameterized problem.
max J S.t. J 20 0 dg
(3)
We denote J - [ g E (r for notational convenience. Let, P : + A be transition function induced by тe and defined as, (s, = Ensa P(s'|s (s, a)mz(als)) Vs, If M is such
that for every policy n, the function, pr is irreducible and aperiodic, then M is called ergodic.
Assumption 1. The CMDP M is ergodic.
Ergodicity a common assumption in the literature 23 24 unique stationary distribution, d A given follows.
If M is ergodic, then VO, there exists
T-1
d (s) = lim Σ t=0
Pr(s: = ~ p.
(4)
T-0
T
Ergodicity implies that d is independent of the initial distribution, and obeys p = d=a Hence, the average reward and cost functions can be expressed as,
(0( = E anno(t))lgss a)] = (d 9
(5)
CEAA9(s. where (s) - Ege g(s. ( (a|s), g E (r. c}. Note that the functions (0), g E (r, are also independent of the initial distribution, p. Furthermore, V0, there exist a function Q : A R such that the following Bellman equation is satisfied V(s, a) S x A.
2ee a) = g(s. a) JG(0) + Es-m(()).)) [s")(s"))
where g E fr, c} and V S + R is given as (s) = EuEs To(a|s) (s, a), ss E E. Note that if Q5 satisfies (6) then it is also satisfied by Q + c for any arbitrary. c. To uniquely define the value functions, we assume that >Es d= (s) (z) (s) = 0. In this case, Vi (s) is given by,
(s) Σ
[(PTO) d (5') 9Th (8)
E [[g(st, az) - (0)) 0s =]
(7)
where the expectation is computed over all oæ rininuue trajectories. similar way, V(s, a), one can uniquely define Q59 (s,a), a). g E {r,c} as follows.
(5 (s, a) = Σ E [g(s,, an) - Jg(0)}/ss an = a]
(8)
Moreover, the advantage function ATo S x A RR is defined such that A (s. & Q (s, vi (s), V(s, a). Vg E (r,c). c). Assumption also implies the existence of a finite mixing time. Specifically, for an ergodic MDP, M,, the mixing time is defined as follows.
Definition 1. The mixing time, thiixe of the CMDP M for a parameterized policy, Ta. is defined as, t fiix - min {t 2 (P=s (s..) d || I 1 Vs}. The overall mixing time fmi e supace mmxx In this paper, mix is finite due to ergodicity.
Mixing time characterizes how fast CMDP converges to its stationary state distribution, doo under a given policy, Ty. We also define the hitting time as follows.
Definition 2. The hitting time of an ergodic CMDP M with respect to policy, ne. is defined as Lh A max.es 1d (s)]-1 The overall hitting time is defined as Iii A supree L In this paper,
Init is finite due to ergodicity as well.
Define F' as the optimal solution to the unparameterized problem (). For a given CMDP M, and time horizon T, the regret and constraint violation of any algorithm & is defined as follows.
T-1
Regr (A, M)
Σ 1=
J -r(s) Vio a
Σ c(st, az)
(9)

---

where the algorithm, A, executes the actions, {ar}, t {0,1,.... based on the trajectory observed up time, and the state, 8t+1 is decided according the state transition function, P. For simplicity, we shall denote the regret and constraint violation Regr and Vior respectively. Our goal is to design an algorithm A that achieves low regret and constraint violation bounds.
Proposed Algorithm
We solve 3 via primal-dual algorithm based on the following problem.
max min A), 850 A20
(10)
where (0, _ J,(0) XJc(0). The function, JL. :), called the Lagrange function and the Lagrange multiplier. Our algorithm updates the pair (6, X) following the policy gradient iteration as
shown below vk {1.... }} with an initial point (01, )1), d1
0k+1 02 + VaJr (Os, An), AR+1 Plo.g 3Jc(0w)
(11)
where a and 3 are learning parameters and the Slater parameter introduced the following assumption. Finally, for any set, A, xx denotes projection onto A. The assumption stated below
ensures that we have at least one feasible interior point solution to (2).
Assumption (Slater condition). There exists a (0, 1) and
θ such that Jc(0) 2 6.
Note that in 11 the dual update is projected onto the set [0, 3 because the optimal dual variable for the parameterized problem bounded Lemma [6 The gradient of (,, can be computed by invoking variant of the well-known policy gradient theorem (25].
Lemma 1. The gradient of Ju(,, X) is computed as,
V Vo X) Eg [e (x)
[A (8. a) Vo log [alss]]
Algorithm Primal-Dual Parameterized Policy Gradient
1: Input: Episode length H, learning rates a, B. initial parameters 0,, A1 initial state so p(.).
2: = T/H
3: for k {1, K} do
4: To x
5:
for E {(k: 1)H, K,H 1} do
6:
Execute an To, (.18e)
7: Observe r(s), at); c(8t; 0e) and 8141
8:
To + U (((,,))))))
9:
end for
10: for t {(K - 1)HI,.. ..H 1} do
11:
Obtain A (st, (4) via Algorithm 2 and Tr
12:
end for
Compute we using 15)
14:
Update the parameters:
0 = 0% + owk:
(12)
AR+1 P/.. Ii BO.
kH
where j.(Ox) = H. N
Σ
c(5t, 0t)
(=(K
15: end for
where v(s. a), A (s. & corresponding to reward and cost. In typical RI. scenarios, learners do not have access the state transition function, P. and thereby to the functions a and A This makes computing the exact
XAT (s, a). and {A (re(r.)) are the advantage functions
5

---

gradient difficult task. In Algorithm the gradient using sampled trajectories.
1 we demonstrate how one can still obtain good estimates of the advantage value for given pair (s, a). This can be accomplished via Algorithm 2
Algorithm runs K epochs, each duration H = /iix T (log T) where E (0, 1) defines a constant whose value is specified later. Clearly, K T/ P/H. Note that the learner is assumed know the horizon length, 7'. This can be relaxed utilizing the well-known doubling trick [26]. Additionally, is assumed that the algorithm aware the mixing time and the hitting time. This assumption
is common in the literature 13 17 The first step in obtaining a gradient estimate is estimating
At the kth ( is obtained and subsequently passed to 2 that searches for subtrajectories within it that start with a given state s, are of length N mix (log T), and are at least N distance apart from each other. Assume that there M such subtrajectories. Let the total reward and cost the ith subtrajectory be fra, C respectively and т₃ be its starting time. The value function estimates for the kth epoch are
epoch, To, -induced trajectory. Tx {s,, at) )
kH-1
Algorithm
2 Tok (8,0) 0)
1 M
Σ g:l(a, a)
Vg (6)
Σ yo, Vg (r,c)
(13)
To, (a(s)
This leads to the following advantage estimator.
Ar, (s,a) Ar (s, + AxA a),
(14)
where Ag (s, Q3 20 (8,a) - rg (s), E cr, Finally, the gradient estimator is,
1++1-1
wk (O,, Ax)=
H Σ
A (st, at) Vo log no, (aolss)
(15)
where 4 = (k= H) is the starting time of the kth epoch. The parameters are updated following (12). To update the Lagrange multiplier, we need estimation of (Ox)), which is obtained as the average cost of the kth epoch. should be noted that we remove the first N samples from the kth epoch because we require the state distribution emanating from the remaining samples to be close enough to the stationary distribution d which is the key to make (0x) close to Je(Os). The following lemma demonstrates that AT, (s, a) a good estimator of AT, (s, a).
Algorithm 2 Advantage Estimation
1: Input: Trajectory (8t, 0t1 Stg atz), state 8, action a, Lagrange multiplier X, and parameter 0
2: Initialize: M +- 0, + t
3: Define: N mix log, T.
4: while r 5/ N do
5: if s, = s then
6:
M + M + 1, TM T
- g(st,a)), or), Vg E (r.c)
7:
9M + 2
8:
+ T 2N.
9:
else
T f- +11.
11: end if end while
13: if IM 0 then
Compute as) (s))) via B Vg e (n.c}
15: else
Va(s) = 0, (8, a) 0, Vg (r.e)
17: end if
return -Q)(s, XQQ v.(ss)
Lemma 2. The following inequality holds Vk. V(s, a) and sufficiently large T.
A A (s, a) -A, (9.0))
27
V3 log
+2 f (log T)
E
0
82 H (a
=
T TT (als))
(16)

---

Lemma 2 shows that the L2 error of our proposed advantage estimator can be bounded above as ( We later utilize the above result to prove the goodness of the gradient estimator. It is to be clarified that our Algorithm is inspired by Algorithm of 17 However, while the authors of [77 choose H (1), we adapt Ó(T)). This subtle change is important in proving a sublinear
regret for general parametrization.
Global Convergence Analysis
This section first shows that the sequence {0k, > produced by Algorithm | is such that their associated Lagrange sequence (Ji,(Ok, )=) converges globally. By expanding the Lagrange function, then exhibit convergence of each of its components [Jg(Ox, } 1+ {r, c}. This later used for regret and constraint violation analysis. Before delving into the details, we would like to state few necessary assumptions.
Assumption 3. The score function (stated below) is G-Lipschitz and B-smooth. Specifically, v0, 1 02 + and V(ss, a), the following inequalities hold.
V e log (e(a|s)]l - G, V log ne, (als) Ve log me, (a|s)] - B||0: - 02ll
Remark 1. The Lipschitz and smoothness properties of the score function are commonly assumed for policy gradient analyses [27 28, 29 These assumptions hold for simple parameterization classes such as Gaussian policies.
Note that by combining Assumption 3 with Lemma and using the gradient estimator as given in (15,, one can deduce the following result.
Lemma 3. The following inequality holds vk provided that assumptions 7 and are true.
E
| (9, >+]] < ő ( mix 5)
(17)
Lemma claims that the gradient estimation error can be bounded as O). We will use this result later to prove the global convergence of our algorithm. Assumption 4. Let the transferred compatible function approximation error be defined as follows.
[
(Vo log To (als)) wa.x A7% (s. )
Lari (w A)
Exadrr East (s)
(18)
where मt the optimal solution of unparameterized problem in and
( (vo lo (alls) (7, (s.
27
WHA arg min WERU
Egnaro Ea)TT(s)
(19)
We assume that L . 0,A) S Ebias X e [0,
parameterized policy class. We can show that bbas [ and 0 e θ where ébias is positive constant.
Remark 2. The transferred compatible function approximation error quantifies the expressivity of the for softmax parameterization (10) and linear MDPs [30]. If the policy class is restricted, i.e., it does not contain all stochastic policies, ébias turns out to be strictly positive. However, if the policy class is parameterized by a rich neural network, then
ébias can be assumed to be negligibly small [3I]. Such assumptions are common 29 [0].
Remark 3. Note that W defined in (19) be written as,
w F₂ Ba En))y(s) V log To (alas)) (s.a)
where is the Moore-Penrose pseudoinverse and (0) the Fisher information matrix defined as, Fp E End E V log (a)ss) (s) (o(g)))())s))
Assumption 5. There exists a constant oF > such that (,) pala is positive semidefinite where la is an identity matrix of dimension, d.
Assumption 5 is also called fisher-oo-deeeeerce policy assumption and is quite common in the
literature 29 32 33
the policy gradient analysis. [29] Assumpiin 2.1] provided a detailed
discussion on the requirement of policy class to satisfy the assumption 5 Moreover, (34] describes class of policies that obeys assumptions 3 simultaneously. The Lagrange difference lemma stated
below is important in establishing global convergence.
7

---

Lemma 4. With slight abuse of notation. let JL(T, X) = J. + XJ For any two policies π, T', the following result holds AY > O.
J Ex E (s))(()) [ALA(s,
We now present general framework for the convergence analysis of Algorithm
Lemma 5. If the policy parameters, {0x. Ag )a are updated via and assumptions hold, then we have the following inequality for any K,
and
K
G K K
K
1
E
J - (L(Ox22k) -
VV Vbias +
Σ
Ell(wk will +
Ba 2K
E
wy
1
K
1
+ aK
E Band [K (XT((T((+sslll (+1s))
where wi == Whe Wb defined (19). and n² the optimal solution to the problem (2)
Lemma proves that the optimality error of the Lagrange sequence can be bounded by the average first-order and second-order norms of the intermediate gradients. Note the presence of (bias in the result. If the policy class is severely restricted, the optimality bound loses its importance. Consider the expectation of the second term 20p. Note that,
K
2
1
K
K
E Bl|W - will) v
E
1aws - wF1?
look F)(Ok) (P))) Ac)
K
K
K
k=1
E ||wk (O
As)11 (
+ E
VoJ (0ks Ax) (0 (0
Aw))
K
k=1
(
K
2
K
||:x - VO... Ax)11
1
K
PF
k=1
where (a) follows from Assumption
The expectation of the third term
20 can be bounded as
K
K
K
Σ
w
S
Ax)1
VoJi.Ou. )x))
K
K
K
In both 4 and 20 E We VoJL (0x, Ax 1| is bounded above by Lemma 3
To bound the term,
El VoJL lI the following lemma is applied.
Lemma 6. Let J-(-) be L-smooth, Vg {r, c} and 1111+3
Then the following holds.
1
K
288L 82K
K
VoLL(0
Vo))(O -
1 -
(20)
K
K
Note the presence / in 20 To ensure convergence, 3 must he a function of T. Invoking Lemma get the following relation under the same set of assumptions and the choice of parameters in Lemma 6
AG mix
Liiuis
E
VoJi Ax] < Ö
(21)
K
827'
8271-E
Applying Lemma and (21 in 20 we arrive at,
|| 1
s sō
(ACCP
AG 2uix
Ltmixthit 52T1-
+
(22)
8.7
Similarly, using
4 we deduce the following.
K
V VAGimii 87
VLtmixthi
E We will <
VB+
1
(23)
K
87
PF
PF
1=1
Incqualities
and 23 lead to the following global convergence of the Lagrange function.

---

Lemma 7. Let (0x) be as described in Lemma 5 If assumptions hold, gg are L-smooth functiins, 41(1+3)' K
T and H 1it T (log2 T)?, then
K
(V88t VAGt VLluixtuit 87
Σ
E
JL( (AA) - (Ok. Ab.)) S G
1
VB+
K
MF
87(1-6)/2
km
B
AG mix 62T
Ltmixthi
Ltmixthit E Fenagn [KL( (-1s) (-s))) + VEblas
(-1ss
+
827--5 +3) + 0
L
T1-58
Lemma 7 establishes that the average difference between JL(TT, ( As) and (O,, Ax.) is O(VB
T- + T- Expanding the function, Jr, and utilizing the update rule of the Lagrange multiplier, we achieve the global convergence for the objective and the constraint in Theorem || (stated below). In its proof, Lemma [8] (stated in the appendix) serves as an important tool in disentangling the convergence rates of regret and constraint violation. Interestingly, Lemma 18 is built upon the strong duality property of the unparameterized optimization (2)
and has no apparent direct connection
with the parameterized setup.
Theorem 1. Consider the same parameters as Lemma 7 and sei T-215 g 2/5. We have,
1
K
E
J
- -,,(0)) S v VEbias
VAG
tmix
1
(T-1/S)
K
6
HFF
1=1
Σ
E
Jo(Da)
< Sōvebiaa + + (fmixtra
88115
VAG Imix
(1+
-
Ö (T-1/5)
K
pr
where is a solution to (2. In the above bounds, we write only the dominating terms of
Theorem establishes Ö(T 1/5) convergence rates for both the objective and the constraint violation.
5 Regret and Violation Analysis
In this section, we use the convergence result of the previous section to bound the expected regret and constraint violation of Algorithm Note that the regret and constraint violation decompose as,
K
Regr Σ
JF - r((se.a))
H
J - ((0k))
+
(J(0x) - r(s at))
k=1
k= EEI
Vior Σ
(-c(st) H
(cke))))) +
Σ (Je(Ok) a:)) A=1
where I A ((k-1(1))) 1)H, ... .KH 1}. Observe that the expectation of the first terms in regret and violation can be bounded by Theorem [ The expectation the second term in regret and violation can be expanded as follows,
K
(Jo(0k) ((s).a)))
(a)
E
Σ
Eg Eg 1x (s')] Q (Se, ae)
(
I.
TE
K
(
E
V Top (8e+1) -io (st)
E
V (SKH1) Vo (8(2
(24)
TETx
K
E
Vg To (SKH)
- Vi The (SKH)
+ E
Tow (ST) - v, (so)
where g E cJ. Equality (a) uses the Bellman equation and (b) follows from the definition of Qg- The first term in the last line of Eq. (44 can be upper bounded by Lemma 8 stated below). On the other hand, the second term can be upper bounded (ttmix) using Lemma

---

Lemma 8. If assumptions I and 3 hold, then for K = T where H 16 hit Tā (log2 TY?. the
H
following inequalities hold Vk, v(s.a) and sufficiently large T:
(a) Tous (als) Tea (a|s) Gl|0K+1 0xll
K
E ( -g(0)) Jg(0k)] So
[AAG Ötnit
[[VAGtmix + +5) T + + v Vilmidtii
k=1
K
[(VAGtmix + +6) r +0) + V Limixtnne l
(c)
E Vg n (sk) Vggh (sx)) S
öthit
where g c), and { is an arbitrary sequence of states.
Lemma 8 states that the obtained policy parameters are such that the average consecutive difference in the sequence (0=))) E (r:e) decreases with time horizon, T. We would like to emphasize that Lemma 8 works for both reward and constraint functions. Hence, we can prove our regret guarantee and constraint violation as shown below.
Theorem If assumptions
hold, J-(+)'s 's are L-smooth, Vg E {r, e} and are sufficiently large, then our proposed Algorithm achieves the following expected regret and constraint violation bounds and 2/5
with learning rates
41(1+3) 3)
E Regrl T LTV Ebiae O(T4/6) + (ffmix)
(25)
[Vir]] S TT Tô /éiaas éhins + O(T4/5) + (bmix)
(26)
The detailed expressions of these bounds are provided in the Appendix. Here, we keep only those terms that emphasize the order of T. Note that our result outperforms the state-of-the-art model-free tabular result in average-rewand reward CMDP (8. However, our regret bound is worse than that achievable in average reward unconstrained MDP with general parameterization [33.. Interestingly, the gap between the convergence results of constrained and unconstrained setups is common observation across the literature. For example, in the tabular model-free average reward MDP, the state-of-the-art regret bound for unconstrained setup, 1/2)/2 [17, is better than that in the constrained setup, (T75/6)
Conclusions
This paper establishes the first sublinear regret and constraint violation bounds in the average reward CMDP setup with general parametrization (and do not assume the underlying constrained Markov Decision Process (CMDP) to be tabular or linear). We show that our proposed algorithm achieves O(T4/5) regret and constraint violation bounds where art in unconstrained counterpart is O(T3/1). Closing this gap by designing more efficient algorithms open question in the average reward CMDP literature with the general parametrization. Morcover, our current algorithm requires the knowledge of mixing time. Relaxing such assumptions is another important future direction in realistic settings. For further discussions on future work directions, the readers are referred to 335
the time horizon. Note that the state of the
Acknowledgement
This research was supported in part by the National Science Foundation under grant CCF-2149588 and Cisco, Inc.
References
[1] Liu, C., Geng, et al. Cmix: Deep multi-agent reinforcement learning with peak and average constraints. In Machine Learning and Knowledge Discovery in Databases. Research Truck: European Conference, ECML PKDD 2021, Bilbao, Spain, September 13-17, 2021, Proceedings. Part I 21, pages 157-173, Springer, 2021.
10

---

[2] Al-Abbasi, A. O., A. Ghosh, V. Aggarwal. Deeppool: Distributed model-free algorithm for ride- sharing using deep reinforcement learning. IEEE Transactions on Intelligent Transportation Systems, 20 20(12):41144727,, 2019.
[3] Ling, L., W. U. Mondal, S. V. Ukkusuri. Cooperating graph neural networks with deep reinforcement learning for vaccine prioritization. arXiv preprint (rxiiv2305.05/66 2023.
[4] Bai, Q., A. S. Bedi, V. Aggarwal. Achieving zero constraint violation for constrained reinforce- ment learning via conservative natural policy gradient primal-dual algorithm. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 6737-6744. 2023.
[5] Agarwal, M., Q. Bai, V. Aggarwal. Concave utility reinforcement learning with zero-constraint violations. Transactions on Machine Learning Research, 2022.
[6] Chen, L.,, R. Jain, H. Luo. Learning infinite-horizon average-reward markov decision process with constraints. In International Conference on Machine Learning, pages 3246-3270. PMLR, 2022.
[7] Agarwal, M., Q. Bai, V. Aggarwal. Regret guarantees for model-based reinforcement learning with long-term average constraints. In Uncertainty in Artificial Intelligence, pages 22-31. PMLR, 2022.
[8] Wei, H., X. Liu, L. Ying. A provably-efficient model-free algorithm for infinite-horizon average- reward constrained markov decision processes. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 3868-3876. 2022.
[9] Ghosh, A., X. Zhou, N. 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.
[10] Agarwal, A., S. M. Kakade, J. D. Lee, G. Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. The Journal of Machine Learning Research, 22(1):4431-4506 2021.
[11] Mondal, W. U., V. Aggarwal. Improved sample complexity analysis of natural policy gradient algorithm with general parameterization for infinite horizon discounted reward markov decision processes. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2024.
[12] Sample-efficient constrained reinforcement learning with general parameterization. arXiv preprint ArXiv:2405. 10624, 2024.
[13] Bai, Q., W. U. Mondal, V. Aggarwal. Regret analysis of policy gradient algorithm for infinite horizon average reward markov decision processes. Proceedings of the AAAI Conference on Artificial Intelligence. 2024.
[14] Ding, D., K. Zhang, T. Basar, M. Jovanovic. Natural policy gradient primal-dual method for constrained markov decision processes. Advances in Neural Information Processing Systems, 33:8378 8390, 2020.
[15] Agrawal, S., R. Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. Advances in Neural Information Processing Systems, 30, 2017.
[16] Auer, P., T. Jaksch, R. Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008
[17] Wei, C.-Y., M. J. Jahromi, H. Luo, H. Sharma, R. Jain. Model-free reinforcement learning in infinite-horizon average-reward markov decision processes. In International conference on machine learning, pages 00170-10180 PMLR, 2020.
[18] Bai, Q., A. S. Bedi, M. Agarwal, A. Koppel, V. Aggarwal. Achieving zero constraint violation for constrained reinforcement learning via primal-dual approach. In Proceedings of the AAAI Conference Artificial Intelligence, pages 3682-3689, 2022.
[19] Xu, T., Y. Liang, G. Lan. Crpo: A new approach for safe reinforcement learning with con- vergence guarantee. In International Conference on Machine Learning, pages 1480--11911. PMLR, 2021.
[20] Efroni, Y. Mannor, M. Pirotta. Exploration-exxplotaaion in constrained mdps. arXiv preprint vrXiv:2003.02189 2020.

---

[21] Qiu, S., X. Wei, Z. Yang. J. Ye, Z. Wang. Upper confidence primal-dual reinforcement learning for cmdp with adversarial loss. Advances in Neural Information Processing Systems, 33:15277- 15287, 2020.
[22] Germano, J., F. E. Stradi, G. Genalti, M. Castiglioni, A. Marchesi, N. Gatti. A best-of- both-worlds algorithm for constrained mdps with long-term constraints. arXiv preprini 1rXiv:23041443200 2023.
[23] Pesquerel, F., O.-A. Maillard. Imed-rl: Regret optimal learning of ergodic markov decision processes. In NeurlPS 2022- 102--Thitt--ixxie Conference on Neural Information Processing Systems. 2022.
[24] Gong, H., M. Wang. duality approach for regret minimization in average-award ergodic markov decision processes. In Learning for Dynamics and Control, pages 862-882 PMLR, 2020.
[25] Sutton, R. S., D. McAllester, S. Singh, Y. Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
[26] Lattimore, T., C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[27] Agarwal, A., S. M. Kakade, J. D. Lee, G. Mahajan. Optimality and approximation with policy
gradient methods markov decision processes. In Conference on Learning Theory, pages 64-66. PMLR, 2020.
[28] Zhang, J., C. Ni, C. Szepesvari, M. Wang. On the convergence and sample efficiency of rediuce policy gradient method. Advances Neural Information Processing Systems, 34:2228-225 2240,, 2021.
[29] Liu, Y., K. Zhang, T. Basar, W. Yin. An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods. Advances in Neural Information Processing Systems, 33:7624-7636, 2020.
[30] Jin, C., Z. Yang. Z. Wang, M. Jordan. Provably efficient reinforcement learning with linear function approximation. In J. Abernethy, S. Agarwal, eds., Proceedings of Thirty Third Conference on Learning Theory, vol. 125 of Proceedings of Machine Learning Research, pages 2137-2143. PMLR, 2020.
[31] Wang, L., Q. Cai, Z. Yang, Z. Wang. Neural policy gradient methods: Global optimality and rates of convergence. In International Conference on Learning Representations. 2019.
[32] Yuan, R., R. M. Gower, A. Lazaric. A general sample complexity analysis of vanilla policy gradient. In International Conference on Artificial Intelligence and Statistics, pages 3332-333223 3380. PMLR, 2022.
[33] Fatkhullin, I., A. Barakat, A. Kireeva, N. He. Stochastic policy gradient methods: Improved sample complexity for fisher-non-degeneraa policies. In International Conference on Machine Learning, pages 9827-9869. PMLR, 2023.
[34] Mondal, W. U. V. Aggarwal, S. V. Ukkusuri. Mean-field control based approximation of multi-agent reinforcement learning in presence of a non-decomposable shared global state. Transactions Machine Learning Research, 2023.
[35] Aggarwal, V., W. U. Mondal, Q. Bai. Constrained reinforcement learning with average reward objective: Model-based and model-free algorithms. Found. Trends Optim., 634):193-229, 2024.
[36] Dorfman, R., K. Y. Levy. Adapting mixing time in stochastic optimization with markovian data. In International Conference on Machine Learning, pages 5429-5446. PMIR, 2022.
[37] Ding, D., K. Zhang. J. Duan, T. Başar, M. R. Jovanović. Convergence and sample com- plexity of natural policy gradient primal-dual methods for constrained mdps. arXiv preprint arXiv:2206.0 02346, 2022.
[38] Bai, Q. V. Aggarwal, A. Gattami. Provably sample-efficient model-free algorithm for mdps with peak constraints. Journal of Machine Learning Research, 24(60): 1-25, 2023.
12

---

A Proofs for Lemmas in Section 3
A.1 Proof of Lemma
Since the first step of the proof works the same way for functions J, and Jes we use the generic notations J gg Qg where g r, and derive the following.
VOVA' 2 (5) Vo Σ
Σ Vomo(als)
(s, (5
Σ To(a
(a) Σ (als))
(Vllogm(aass) ) (s, (s,()))) To(als)Vo ( (((s,a)-Jgh + P((5))))))7001))
Σ (a(as) VVllogmoal33) (s, Σ Ta(als) Σ [(((1.a))V (oJz(0)
(27)
where the step (a) is consequence of Vo log xg sides by a (s), taking a sum over E S, and rearranging the terms, we obtain the following.
Vae and the Bellman equation. Multiplying both me
(0)g(0) Σ To (S)
Σ T (s) Ta(a (vologT((ass) (s,a) (s,a) Ed (() Σ To(als) Σ
Σ
(s)Vo
Eg amatl(11s)
Q (s, Vo
+ Σ ( Σ p (10 [s)
(0) E E a (:15)
27 (s, logllog (alls)
Ed (d'Vv (5') - [d
Vo
(28)
where (a) uses the fact that th is stationary distribution. Note that,
Exnd am)))))ss)
TT (s) log (a(ss)
E
VTTe
(s)
(29)
LaEAA
E
(s)
Σ mo((ass) LaEd
Exnaro
(s)
Vi
=0
We can, therefore, replace the function Q in the policy gradient with the advantage function Age (s, Q (8,a) a) Vi V(s a) E A. Thus,
( Ex-ado (-1))) A7 (s. a) log To(a)s)
(30)
The proof is completed using the definitions of JL.A and AL,
A.2 Proof of Lemmal 2
Proof. The proof similar the proof of [17 Lemma 6]. Consider the kth epoch and assume that Te, is denoted as for notational convenience. Let, M be the number of disjoint sub-trajectories of
13

---

length N that start with the state and are at least N distance apart (found by Algorithm Let, a be the sum of rewards or constraint (g- = r, accordingly) observed in the ith sub-trajectory and т denote its starting time. The advantage function estimate is,
A) = T(abb) [M E. 9k (aT, =a)]
Σ M M
1
Ei=1 Ik.
if M >
(31)
if M
Note the following,
+
E Ih. ST, 8, ar, = ((s +E
Σ
glsr, ar) Sr, = 8, 07:
1=
g(s,a) + Σ a(s'|s,a)
Σ
g(s; az)
9-++110 = o
(
N-1
= =)(8,a) + Σ P(s'ss,a)
Σ (PT)((S)))
g"
1=0
T
N-1
= -((s,))+ Σ P(s'|s,a)
Σ (PT)(()))) - dm
9" g"
1=
T
@ g(s,a) + Σ P(s)(s.a)
Σ (PT)(S')) - d=
9" + +JJJ Σ a(
Σ
P (s',))
d=
g"
(BF().
( g(8,0)+ + (( (s 12) (5,(s + (N+ 1)JØ ()
(32)
where (a) follows from the definition of J as given in 5). (b) is an application of the definition of VE given in and (c) follows from the Bellman equation. Define the following quantity.
8T (T,, T) &
[I(PT)((s)) - d where N 4fmix 7)
(33)
t=N
Using Lemma
10 get 8t (s, T) S fox which implies, (s) S 7 Observe that,
E
T(ass) Dh. Maa,, =a) g
ST.
= s,a, of
9k.t S7: 8 Σ E
9k.t 9k. TTalls)
07(s, a) + (N + 1)53 (s, a) - Σ (s, + (N + 1)J3 - E7 a)] (34)
a'
()) (8) ET(s, Σ ((((s)))7((
= =s,(s,a) as)
where (7, A Ey (s. a) Ew ((d(ss) Using the bound on ET a), we derive,
( a) < H.. which implies,
2 [ ([als) Ih. 1 (az, = a) - gk.i ST. - (5 S $1A7(s,0))
E
T (35)
14

---

Note that (35) cannot be directly used to bound the bias of (7, a). This is because the random variable M is correlated with the variables { =- To decorrelate them, imagine CMDP where the state distribution resets to the stationary distribution, d" after exactly N time steps since the completion of sub-trajectory. In other words, if sub-trag trajeerjyy starts Tı, and ends 7; + N, then the system 'rests" for additional N steps before rejuvenating with the state distribution, d at T + 2N. Clearly, the wait time between the reset after the (i 1)th sub-trajectory and the start of the ith sub-trajectory is, Wi = T (T:-1 + 2N), > 1. Let wi be the difference between the start time of the kth epoch and the start time of the first sub- sub-trajectory. Note that,
(a) wi only depends on the initial state, 1(H and the induced transition function, P7,
(b) w;, where i 1, depends on the stationary distribution, dx, and the induced transition function, P"
(c) M only depends on {11, W2 }
} as other segments of the epoch have fixed length, 2.V.
Clearly, in this imaginary CMDP, the sequence, {wi, u2...... }, and hence, M is independent of {9k.1 9k.2, ... J. Let, E' denote the expectation operation and Pr denote the probability of events in this imaginary system. Define the following.
Ik. (ar; = a)
A
9k.s - (5 (8,
(36)
π (alss)
where (7 a) is given in [34] Note that we have suppressed the dependence on T, s, a, and π while defining A, to remove clutter. Using (34). one can write E' (w:)) = 0. Moreover,
(s, 4)(
E'
E'
(Ag(s, A3)
M > 0
PT > 0) PP =0)
E'
Σ A, (7(),))
|M>0
*)
Pr =0)
M
(37)
< 2E
E'
M Σ A
{wu}}
w1 S H - N x P -
+ + a))² + (A7 (s, a))²
x PP =0)
(0)
2E (wi)
wi S H N Pr S H - N) E' AA [w:1]]
M
8 (s) 2 x (M
+ T6
where (a) uses the bound ( a)l S # derived in 35 and the fact that {A,} } are zero mean independent random variables conditioned on {w,). Note that [gk.al $ N almost surely, | (s, a) <
(tmix via Lemma and As a)l I 7s shown 35 Combining, we get, E [w; <
O(N2 (als)) (see the definition of A, 36)). Invoking this bound into (37) we get the following result.
- E' (A) A7 a) )
27
N2
8
< 2E
M wi H
O
(aass)
+
T66
(38)
+ ( x Pr > H N)
Note that, one can use Lemma I1 to bound the following violation probability.
(r'( > H - N) < (1 3d (x)
4 (log2))1 (a)
< (1
(s)
d d=(ss)
(log
(39)
4
T3
15

---

where (a) is consequence of the fact that 4hmn (log2 T) 17-12 (=()) T. Finally, note that, if M < Mo. where Mo is defined as,
4
log, T for sufficiently large
H N
Mo
(40)
4N log T (s)
2N
then there exists at least one w; that exceeds 4N log2 T/d (s) which can happen with the following maximum probability according to Lemma
3dt (s)
Pr (M < Mo) -
S 73
(41)
4
The above probability bound can be used to obtain the following result,
Pr = m)
Pr S Mo) + Pr > Mo)
1 M
Mo
E
M
>
0
m Pr 0)
Pr 0)
4N log
2N
(42)
d (s)s)
T
H
N
N log
S
1
Hdt
73
Injecting 139
and
42
into 38
we finally obtain the following.
E' [A](es,0) -)) (.5o))))(888a)
N log T
s so
Hd (s)
(43)
9 log T (m(aas)
fiix (log T)² T TT
0
Eq. 43 demonstrates that our desired inequality is obeyed in the imaginary system. We now need a mechanism to translate this result to our actual CMDP. Note that (A, a) - (s, f(x) where = (M, T2, TI, ... TMI, Tas), and T, = (aTe S74+1, Ar.+1. Sr.N ax++)). We have,
E[f(X)] ((X)x((X S max Pr(() EXX Σx f(X)Pr(X)
Pr(X)
(44)
The last inequality uses the non-negativity of f().. Observe that, for fixed sequence, X, we have, Pr(X) Pr(n)) Pr(Ti(m) Pr(12/11, Ti) Pr(T2 12) x...
x Pr([MM|MM-1, (MM TM (T( x Pr(s, # V. E [TM + 2N, kH N]|TM. TM),
(45)
Pr((X= Pr(n)) x P Ti) x Pr(T2 T2) x
x (PP'(TM|TMM-)) TM-1) x Pr(TulTTM) Pr(st + Vt E |TM + 2N, kH NN]TT Tas)
(46)
The difference between Pr(X) and (X) arises because Pr(Ti+1/T, Ta) * PT To), Vi {1. M 1}. Note that the ratio of these two terms can be bounded as follows.
Pr(te [T, TT)
Pr (T411/T7777 Ti)
Exto Pr(s = S'|T,, Ti) x Pr(s: ss [T. + 2N, T1 - 8T,. = s/97,2N = =s)
Eoso Pr P7(7:422 = 8'|T,, Ti) x Pr(st F V + 2N, T41 1], 87,11 = 8|87++2N = 87)
= 7)
< max Pr PT' 8'|Te, Tr)
max 1 + Pr(St,42N = 8 s', Ti) d (8') (a)
Uhit
1
max 1
Ted $1
< 1
(s')
73
T
(47)
16

---

where (a) is consequence of Lemma 10
We have,
Pr(X) (X) _
(0) S er o ser
1+ (1+
e
(48)
72
where (a) uses the fact that M T. Combining
44
and 48
we get,
E ( (A)(s,a) (3 15().0)))
A7 (7 (8 27
S 0
E'
T
(49)
W
fmxx (log T) T (s)
where (a) follows from
43
Using the definition of AL, we get,
E
Af (s, a) AT,
- ((A -(((s))))))(())))))))))))))))))) - AE(s,a)) 2E (A)(), - ()) 21 / + (AE().0) A3(0,a))² ((((s,))-{((..))) 0 <
E ((A)((s))) A3(s,
2 (log 1)
827 3 (a|ss)
This concludes the proof.
B Proofs for the Section of Global Convergence Analysis
B.1 Proof of Lemma 3
Proof. Recall from Eq. 15 that,
1++1-1
Wik
a)) log
(50)
H
t=
Define the following quantity,
1 f6-1-1
wk = H
Σ
A (st, at
V V log ne, (acls))
(51)
where ts = (I: - H)H the starting time of the ktt epoch. Note that the true gradient is given by,
VoJ1, "e lamto, (11)) AL (s, a) Ve log (a(a)))
(52)
Using Assumption Lemma 9 and X E [0, 2. one can exhibit that AA (s, a) Vo log T (a|s) O( (fmiz))) ), Y(s, a) therefore, arrives
<
E S x A which implies (VoJL. & O (bmi G Applying Lemma 14 one,
|10x - (00))) s so C logT)
mix log T H
)
G mix
= -0
(53)
82
Finally, the difference, El(wx - @xll can be bounded as follows.
E Wk
Wk
1241
14+1-1
E
1 (St, Vo) no, (arlse)
Σ
ATt (8t, ao) log To, (acls:)
H
H
t=t
t=
(0)
22
E
A (s
Jop (sc.
H
1=
G
44111
E
Σ
Te (als))E
(AT (s) - A (s,,
81
(t)
x o
(AG (log T)2
mix
8274
1=
(54)
17

---

where (a) follows from Assumption 3 and Jensen's inequality whereas (b) follows from Lemma Combining,
53 and 54h. we conclude the result.
B.2 Proof of Lemma
Proof. Using the Lemma
12 it is obvious to see that
J J
ΣΣ d' (s)((T()))) - (alss)) (8,a)
9
Σ
Σ
(1)) (s.a) - Ed(()) (s)
(55)
ΣΣ ()) (8, - (1) (s)
ΣΣ (5) (s,a) Vÿ [s)] Eg (o)) [Ag (s,
We conclude the lemma using the definition of JL, and AL,A-
B.3 Proof of Lemma
Proof. We start with the definition of KL divergence.
E gnnd [KL (-1s) (o,, (-1s) KL(m" (+s))
Ex Eawo (1a) log (a)+)(ulo) To (als)
(0)
B
E Eenge Eawr (-1s) Vo log no, (als) (0t+1 - 0k)]
|10++1 - 0x
Ba²
aE Eant' (11) V log ne, (als) wk] 2
||wx|1
Ba²
aE Eass' (-18) V log ne (als) will + aEE
and E (+ VV Te, (als) (wx wk)]
||
=a(Ji(m AR) - J1. As)] + aE end Bawr (V log Te, (als) will alJi(TT,, ( (1 Av)
Ba²
a.E BaNT (-1+) V log ne. (als) (w* wk)l
1 1|
2
( a[Ji(TT" An) 11, Ax)] aF E (-1s)
Vo log no. (als) w A (s.a)
Ba²
+ E EanT-(11) log To, (als) (wx - ww]]
||wk|l 1|
2
(0)
- a[J_(TT,, Aa) (1( Ax) a1 E Exnatr E Eawr (110)
Vo log To, (als) wh - ALi (0,,a)
Ba²
-EE Eawn (-16) log To, (a]=)]la]([ux - -
|ww 1|2
2
(1)
Ba²
2 af]i( An) (Ox, Ax)] - / aGll(wk wx)l
| 1|
2
(56)
where the step (a) holds by Assumption and step (b) holds by Lemma Step (c) uses the convexity of the function fxx = x.2 Finally, step (d) comes from the Assumption Rearranging items, have
Ba
Jr.(m", ()) J1.(02, Ao) S Vehias + G]] wi)l +
ww 12
2
(57)
1 E (T (-1s)) KL(m" (((rr(((sss((a))) (-15)]| (-1s))
Summing from 1: K, using the non-negativity of KI. divergence and dividing the resulting expression by K, get the desired result.
18

---

B.4 Proof of Lemma 6
Proof. By the ssmoohh property of the objective function and constraint function, we know that JL(,, A) is a L(1 + A)-smooth function. Thus,
L(1 + Xx)
JL(Ok+1, Ax) 2 (1k, As) + JL Ab), 0x+1 0k)
1|x+11
0xl1
2
(a) [L,(0,, Ax)) +
Ax) 2 L(1 Xx)
||wx|
2
Jr.(On, Ax) Jr. Ax]1 Jr. (Oke, AR) - Wh. (o,, Ac))
T.(1 + 22 VJL Ax) - Wk VOk 1x)11
(6)
a 2 (1,, AR) + all (Ok,, Ab)1 - 0 |VJL Ax) - - VJLL Ax)1
2
-1(1+ Ax)a² [J (0%x Ax) - wxll - L(1+ + Ax)a A+)1
AL((0)AA)) + 6 L(1 + )x)a²) [/V.L Ax)1 2 + L(1 + Aw)a²) J As) - 11
a
(58)
where step (a) follows from the fact that Oc+1 02 + own and inequality (b) holds due to the Cauchy-Sehwarz inequality. Now, adding (Ox+1, Ak+1) on both sides, we have
( L(1 x+)aa))a))))))))))())))))))))) [V, A+)
JL(OR+I, A 2 (1 11 ARt1)= (1(++11 + (OA. Ac) +
G + L(1+ Ax)a²) (0k, Au) wwll2
(0)
(A++1 - -N) + JL(O,, + 1 L(1 + Ax) [V. Ax)11
( + L(1+ xx)a²)
[V As) - 22
38+ (1b,)Aa))
10(11+ ++++aa)a))))))))))))))))) [[ 1x)1
1 6 + L(1 \x)a²) J Av) - w/ll
(59)
where (a) holds by the definition of (0, and step (b) is true because [Ja(0) < 1, and
De++1 Au < (0s) < B where the last inequality uses the fact that [Ox(O)] < 1. Summinn over à E (1, KK,, we have,
Σ (1(04)2,4411) (L(O Ne0 2 -33- +
Σ k=
( L(1 + ++)+aaa)) [V.L Ax)1l
(60)
a
LL(1 + +x)a2)
[IV Ao) wall2
2
which leads to the following.
11(0041,AHH) - -1
-3K +
Σ
L(1 + An)a²) [V
2
k=1
(61)
K
Σ
+ L(1+ xx)aa) (V, wxll 1
Rearranging the terms and using 5 d 2 due to the dual update, arrive the following.
VJL < JL(OK11, Ax+1) JL X1) + 3K + (g + L(1 + Ek
[J Ax) wall
2 L(1 ))0²
(62)
19

---

Choosing = 4L(1+3) and dividing both sides by K, we conclude the result.
K
16L(1 ())
(Ok. Aw)1
(L(0K+1:Ax+1) - JL A1)
K
(63)
3 K
+
A+) - -wxl?+
K
Recall that =
=
8 44
θ K Thus,
288L
A,,, -
VJz, As) - -xxl2+
(64)
K
k=1
This completes the proof.
B.5
Proof of Theorem T
B.5.1
Rate of Convergence of the Objective
Recall the definition of J1 (0, = (+) + AJc(O). Using Lemmal
7 arrive the following.
S SC ( (1
PF 1 O VB+
VAGlmix 8T5/2
Almixliit
E
J - Jr((k))
K
87(1-5)/2
Ltmixthit 82T1-E
+ + Ö
Limixtho Exnder [KL( (+1s)]| (-18)]] (65)
+
L
827
E8
1
J= - -Jo(0w)
E
Ak
+ Ciis
K
k=1
Thus, we need to find a bound for the last term in the above equation.
0 < (2
(2e+1)2- (Ax))2
-(ta)))
1Po.3 -BFc(8h)12 -(xb)2)
[Aee 2 (640) (Ax6)3
<
A=1
(66)
23
Jc + + Σ )c()
(1)
K
K
23
Ae -j.(0x) + 13 Σ jo()))²
k=1
k=1
K
< 23
Ax -c((k)) +23
je(Ow)²
k=1
Rm
23
Σ
A (c(()) +23
(J j.((k)) + 2 Σ J.(O))²
20

---

where (a) uses Y1 0 and inequality (b) holds because 0* is a feasible solution to the constrained optimization problem. Rearranging items and taking the expectation, we have.
K
B K
E An (J= -o((Ow))
2
1 K
E
Ae(J.((x) - -a(Ja(()--<((.a))) J.(Ow))
+ BO)((
K
k=1
(a)
Ax (Je(0n)- - -d((0))] +
E
K
K
(6)
(Jo(Ok) - E [_((0))000 0z 1)
Ak
+
K
k=1
1
- -E |c(00]]0x |]
(c) 2
E
d
Jc(Ok)
+ S
8T 3
K
k=1
(67)
where (a) results from (0)2 < 1, V0 E
O and (b) uses the fact that (0,) and 0 conditionally independent given 0g. Finally, (c) is a consequence of Lemma 13 Combining (67) with (65). deduce,
K
J - -.((k))
K
1=
S Ebias +
(1(1111
V3+ +
VAGtmix 8T8/2
Ltmmittuit 81(1-81/2
O 87 + +33)
HF
(68)
B
1G
Llmixhhit
Llmixehiee Exnar [KL( (TT, (-18))]
+ L
8277
6272-8
+ + +
T2-60
S Ebias +G
VAGtmix Vitmixtuut 8TE/2
VB++
+
87(1-5)/2
MF
The last inequality presents only the dominant terms of 3 and T.
B.5.2
Rate of Constraint Violation
Since
(Ax -= are derived by applying the dual update in Algorithm we have,
2 2 (a)
2
E
Ak+1
E
3Jc(0x)
E
2
AA
+ 8'E
[P((w))
8
(b)
<
Ak
2
2
23E
Jc(OK)
2
8 )
2
(Jo(0L) (7(0))-J(((a))) Jo(Ow)) (>x - 2)
5)
+ 32
0
(c)
E
A
2
2
23E
Je(Ow) Ae
2 8
23
E [..(0.) 02 J.((K))
(>e
2 }
2
B2
8
E
4
2
(.() AA )
+ 28E
E [_.(B)) [A Jc(OL))
A
2
+
82
8
2
4/3
E
Aa
23E
Jo(Ow) AA
+ 32
8T
(69)
where (a) is due to the non-expansiveness of the projection Pio.3) and (b) holds because J.(0) |0, 1]. and
40 E θ according its definition in Algorithm |
Finally, (c) is consequence of the fact that (0%)
21

---

and d are conditionally independent given 0g whereas (d) applies A - 31 Averaging 669 over & {l..... K}. we get,
and Lemma
Dx 2
A1 2 AK+1
2
3 (a)
2
2
E Jo(Os)
23K
5T
828K
8T
2
(70)
where (a) uses A1 Note that Ac-o we, therefore, have,
2 wk. Adding the above inequality to
65 at both sides,
J
(0s)
E
1
Jo(On)
S <Ebias +
+
2
+
823K
T25
2
k=1
VAGtmix
thi 87/1-
AGG
fmxx
Ltmix
1+
O VB+
+ Ō
+
3
PF
8TE/2
827
8272-5
Ltmixthit E Bandr [KL(T" (+|s) (T,,
+ Ö
T2-58
(71)
Since the functions (0,(0))), ,0..... -K-KK1 1K11,9 1,g E fr. c} are linear in occupancy measure, there exists policy such that the following holds Vg E (r,c).
1
1g(0k)= = J
(72)
K
1=1
Injecting the above relation to 71). we have
2
2
2
8
E
J
+
E
J
I Vebias
+
+
82,3K
T25
VAGtmix
Ltmmittnit
+G
1+
VB
+
(73)
8T5/2
871(1-3112
pF
B
[AG
mix
Lhmixhhit
+3) + Ö { [..mishhie Exnde [KT(T" (+ss]( (15))]] T1-68
+
0
827
82T1-E
By Lemma
18
we arrive at,
E
< 8 /Cias
2
2
+
83
+
G
1
1
8 888++
VAGtmix Te/2
Ltmixttnl 71122)/2
83K
T
2
HF
(74)
B δ
1G
Ltuiixhiit 87115
Lluiis Uiit E Bxnugn" [KI((=(-|s)] (-1s)][ (-1x)]
+
mix
+03)
+
L
8T
T1-5
< 8 /bbis
+
22 this
5
+ (1+
+
1 pF
(8/++
VAGtmix T8/2
Ltmixthan his 7(1-2)/2
The last inequality presents only the dominant terms of 3 and T.
B.5.3 Optimal Choice of 3 and &
we choose 3 = T- for some E (0, 1), then following 68 and 74, we can write,
K
Jr J.((0))
S Vebins + + + 8/2 0152 T (1- 1)22)
(75)
1=1
K
E
-c((m)
< S + (T- + n/2 + 2/2 (T-())))
(76)
K
A=1
22

---

Clearly, the optimal values of 77 and & can be obtained by solving the following optimization.
(ax(n.)) min { 1 -75
11 1 1- E - 2'
(77)
One can easily verify that (5,7) = 22/5 is the solution of the above optimization. Therefore, the convergence rate of the objective function can be written as follows.
K K 1=1
E
J - (02)
$ Vhhia +G (G(1= pr
VAGt 871/5
Vilmix 8T3311
71/5
+ o
87
+
T2/5
(78)
+ 3
B
8² + AG22
Limistiit 8273/5
Ltmixthit Exran
[KL( [KI(T"(||s]]TT]
(115))
mix
+
L
8272/5
T3/58
VAG Iuiix
(1+
1
(T-1//6
S Chias
+
PF
The last expression only considers the dominant terms of T. Similarly, the constraint violation rate can be computed as,
K K
E
Imixtiit
1 +
1
+ VAGtmix
VL
< 8 8 /bias +
+ T2
+G
1+
871/5
T2/5
HF
T1/5
T3/10
B
δ 82 + 12
mix
Limixbait 8133/5
Limisciiit E Bend
[KL (-1s)][TOL (-1))]]
+ T,
+
8/2/55
73/5
< @8 +
(imixtalt 871133
+ VAGttmix
(1+
(751/5)
(79)
where the last expression contains only the dominant terms of T.. This concludes the theorem.
C Proofs for the Regret and Violation Analysis
C.1 Proof of Lemma g
Proof. Using Taylor's expansion, we can write the following V(s,a) S A, Vk.
To, (als) -TO, (als))
[0k=+ 02)² "o (a|s)
=mg, (a|s) (0x+1 - 0z) V T log nT. (a|s)
(80)
(a)
Sma, (als))l(k+1
0 V log n. (a|s)] < G| - 0al
23

---

where 0g is some convex combination of 0g and 0x+1 and (a) results from Assumption
This
concludes the first statement. Applying 80) and Lemma 12 we obtain the following for (r.
K
K
E 1g(0x+1)- -g((=))()]
Σ
E
d= (s) (S)
Tax (als)) 1o (s,a)
1=1
1=1
8,0
1 (8) m0 (a|s) - nv, (a|s)] Qg th (0.4a)
E
d (s) 0s noh (s, m))l
G
E
(81)
Ga
E
Σ d (s)
|kxl|| 6tmix
6.AGatmix
E
B
K
6AGalmix V
Σ
Elluxel 1?2
(:AG
(VAGtmiix
b) T + v ti
Inequality (a) uses Lemma and the update rule 0x+1 = 02 + oar. Step (b) holds by the Cauchy
inequality and Jensen inequality whereas (c) can be derived using (22) and substituting K = T/H.
This establishes the second statement. Next, recall from (5) that for any policy Te. g (s) -
E. (o(aas)g(s, a). Note that, for any policy parameter and any state s S, the following holds.
(s) Σ ((Pro) d g00
Σ 1=
(1,
-N(())
Σ ((PT0) do g00)
t=
(82)
Define the following quantity.
nT (s, 7)
A
Σ 1=
(s
- -d where N 4mixx(lg T)
(83)
Lemma 10 states that for sufficiently large T, we have (s, < # for any policy To and state s. Combining this result with the fact that the g function absolutely bounded [0, 1]. we obtain,
K
mok+1 (sk) Vz Tox (sk)
k=1
K
K E
E
10 ((K,,)) - (pro0 To
( 1,9 M04t gm
(
k=1
t=
K
2K
N
E| E|J, (0++1) - J002)l
T3
K N
K N
E (PFoN+2) (p u 1lo0 +
Ellg To - -m 11
1=
t=0
km 1 t=0
+ ④
(AGGtmxx
(VAGlmix + 6) T + v LImiie T
öthit
(84)
Note that, in general, 0g is dependent on (s.a).
24

---

where (a) follows from 81 and substituting N = (fmix(log) T). For the first term, note that,
[1((P*0)1)) (p )9)g =0 oo
< | ((p yz-1 (pmoz) )d- "I9 00 oo + (( - p (P (--mas)-1l g ol
( ((( - (p (-1)gmar 1o + max | (s, -) - pmo p
(85)
Inequality (a) holds since every row of p sums to 1 and [[ 1 g 11 00 I 1. Moreover,
invoking (80). and the parameter update rule 0x+1 = 0g + awk,, we get.
max p (8, pr (s, = max Σ
(T (als) To, (als))
S G|| 0k+1
0kl
max ΣΣ P(s)ls
I <aAG|wal|
Plugging the above result into 85 and using recursive argument, we get,
[[((P00=1)) (p=0z) )' 1-+1 10 5
max | (s,-) - -oo .11
aAG||ull S atAG|lon!!
Finally, we have
K N
E
((P00(1) (p =0 11:0
k=
K N-1
stAG||wil
1=
< <oGAGN?
E |k|l
(86)
1
K < O(AAGN*VK)
E El|w Σ
(a) Ö
aAAGtmix
[(VAGlmix + 6) T o)r² + / [lmixchnet
8bhit
where (a) follows from
22 Moreover, notice that,
K N
N-
E g
nh
Iax
E
max
Σ
TBess (als) - Te, (a) a)
1=1
t=
K
aAGN
E
|
(87)
< <aAGNVK
Σ
E 1wwkll
&AG 5thit
[VVGGmmix + 5) r + V LLmix To0
where (a) follows from 80 and the update rule 0x+1 = Og + own whereas (b) is a consequence of
22 Combining (84). 16). and (87 we establish the third statement.
25

---

C.2
Proof of Theorem 2
Proof.
Recall the decomposition of the regret in section 5 and take the expectation.
E
Regrl
Σ
J
r((),
H
E
J
J.(Oz))
(J,(0R) ((s):
t=
k=1
k=1dEI=
K
K-1
H
J - J.((k)
+ E
Vr
noot! (SKH) - Vr th (SKH)
+ E
Vr Tou (ST)
Vr-
(50)
(88)
Using the result in 78 Lemma
and Lemma 9 we get,
E Regrl & T Chias +
G
1+
1 MF
T O
VAGtmix T +
Vilmixchite 7
+0
(
+T
6
8
T
0
B
8 + A
mix
T
Ltmixchie 9p
+ ④
Ltmixthit [KL( (-1s)
| Tog
(11)))
L
82
82
/AAGtmix
r [VAGGmix + + [mmisshheeT + O (lmix)
+
ötait
(89)
Similarly, for the constraint violation, we have
Eiiior]
Σ
c(c 0t))
H
Je(Ox)
(Ja(0k) (()),a)))
t=
k=11EI
K (o(O))
K
= H
+
Ve
To (SEH) V (SKH)
+ E Vo Thx (ST) - Vc T0 (so)
k=1
(90)
Using the result in 79).. Lemma and Lemma 9 we get,
E (ior] < T8 T8 ebins + +
+c(1
δ
([
8 AGImix T + v Tdlmii T
PF
+ Amixxhiity 7
+ 5T
1
+ 8T
+
7
B Ō
52 52 + +GG mix + Lmmixthit T
8
(91)
Ltmixthit Eewnr [KL( (0LL(xx(11)) (T (1s)))
Ö (
/AAGlmix [VVAGtmix 8) T + / It 1) O(tmix)
8thit
This concludes the theorem.
D Some Auxiliary Lemmas for the Proofs
Lemma 9. 177 Lemma 14] For any ergodic MDP with mixing time tmix the following holds (ss A. any policy and Vig {r.c).
(a)lV² (s)1 < 5tmix, (b)1 (s, a)l S 6f
Lemma 10. 117 Corollary 13.2] Let 8T (',T)) be defined as written below for an arbitrary policy m.
8t (s. 4
(P*))(ss)) - d" d'1 Vs E where N 4tmmix (log2 T)
(92)
If tmix < T/4, we have the following inequality Vs e S: (s, T8.
26

---

Lemma 11. 17 Lemma 16] Let I = {t1 + +,, 22, .t, ) be certain period of epoch k of Algorithm 2 with length N. Then for any s, the probability that the algorithm never visits I upper bounded by
121
(1_ 3d (1_3d%%(8) (8)
(93)
Lemma 12.
17 Lemma 15] The difference of the values of the function Jg E fr. at policies π
and n',
J -I
[a(ss)) (s.o)
(94)
Lemma 13. 16 Lemma 7] The term Je(0) any E is a good estimator of Jc(O), which means
E[J.(0) - J.(0))
(95)
T2
Lemma 14. 136 Lemma A.6] Let E θ be a policy parameter. Fix a trajectory
(St, des Tt, 814 heN generated by following the policy me starting from some initial state so p. Let, (()) be the gradient that we wish to estimate over 2, and 1(0,-) is a function such that
Egnd"o .no 1(0 2) ((0). Assume that [I((0, 2)1l. [V][[) S GL. 40 O, V2 S Ax R x S.
Define 10 Σ 1= 110, 2.). If P = mix log T, then the following holds as long as Q $ T,
11ze - VV = (cH (PQ) -
(96)
Lemma 15 (Strong duality). 137 Lemma 3] For convenience, we rewrite the umparameterized problem
max J #ell
(97)
J 2 0
Define x² as the optimal solution the above problem. Define the associated dual function as
JA
max
J
+ AJ
(98)
FEll
and denote X = arg minx JD. We have the following strong duality property for the unparame- terized problem whenever Assumption 2 holds.
J
(99)
Although the strong duality holds for the unparameterized problem, the same is not true for parame- terized class {To] θ). To formalize this statement, define the dual function associated with the parameterized problem as follows.
J JD max (f) (f)
(100)
and denote X = arg minx20 JD.e. The lack of strong duality states that, in general, J + (0*) where 0* is solution of the parameterized constrained optimization 3 However, the parameter Xie as we demonstrate below, must obey some restrictions.
Lemma 16. Under Assumption the optimal dual variable for the parameterizedd problem is bounded as
J
(, 1
0
X
(101)
8
8
Proof. The proof follows the approach in 37 Lemma 3], but is revised to the general parameterization
setup. Let A, A {A 2 0| J/Jee I a} be a sublevel set the dual function for a E IR. A, is non-empty, then for any À E Aa:
a a 1b 2 (,(0) + ( 2 (+) + X6
(102)
where 0 is a Slater point Assumption 2 Thus, s (a - J,(0)) If we take
J <
JE S JD" J then we have XB E Aa, which proves the Lemma. The last inequality holds since J [0, 1] for any policy,
27

---

Since the above inequality holds for arbitrary θ, we also have, 0 < X < Define v(T) - max [Jā J 2 T}. Using the strong duality property of the umparameterized problem (9 we establish the following property of the function, v(.).
Lemma 17. Assume that the Assumption 2 holds, we have for any E R
(0) - - 2 v(T)
(103)
Proof. By the definition of v(T), we have v(0) = J With a slight abuse notation, denote (L X) = J AJZ. By the strong duality stated in Lemma 15 we have the following for any
T IT.
AT) & max JL, X²) Def J
J = c(0)
(104)
Een
Thus, for any a E (nr E J 27}
e(0) -x* Σ [T, X²) TX
(105)
= J. + (Je - -T) 2 J
Maximizing the right-hand side of this inequality over { S 2 r yields
(0)) - - 2 (T)
(106)
This completes the proof of the lemma.
We note that similar result was shown in 38 Lemma 15]. However, the setup of the stated paper is different from that of ours. Specifically, (38] considers a tabular setup with peak constraints. Note that Lemma 17 has direct connection with the parameterized setup since its proof uses strong duality and the function, v(.), is defined via a constrained optimization over the entire policy set, II, rather than the parameterized policy set. Interestingly, however, the relationship between u(r) and v() leads to the lemma stated below which turns out to be pivotal in establishing regret and constraint violation bounds in the parameterized setup.
Lemma 18. Let Assumption 2 hold. For any constant C 2 2X", if there exists E II and Ç <>( 0
such that J - J. + CI-J < S. then
(107)
Proof. Let T J Using the definition of v(T), one can write,
J S v(T)
(108)
Combining Eq. (106) and (008), we obtain the following.
J
J uv(T) v(0) < -
(109)
The condition in the Lemma leads to,
(C - (C= + C(-T) S J - J. +C-J 5c
(110)
Finally, we have,
2
5 C X X C
(111)
which completes the proof.
28

---

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]
The contribution and challenges are clearly described at the end of the intro- duction.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We add all the assumptions in the work, list the gap with lower bound in Table 1, and give future work direction.
Guidelines:
The answer NA means that the paper has 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 in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). ). The authors should reflect on 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 low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
29

---

Answer: [Yes]
Justification: All the assumptions are clearly stated with a remark to discuss. All the proof are given in the appendix in details. 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 the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to 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 be properly referenced.
4. Experimental Result Reproducibility
Question: 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 whether the code and data are provided or not)?
Answer: [NA]
Justification: the paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a 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 submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) 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., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
30

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification: the paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /oti:///gu.deeeoooouuuuumbbbbi ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to 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. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as 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 (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: the 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 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: the 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, or statistical significance tests, at least for the experiments that support the 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, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
31

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
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 errors 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 of range (e.g. negative emrr 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 reproduce the experiments?
Question:
Answer: [NA]
Justification: the 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 httpp:////hrrrppsccppplblleeeeee httprrpp...ccpuuoo....hhhhsseees
Answer: [Yes]
Justification: the research conducted in the paper satisfies the NeurlPS 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 circumstances 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 no societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact 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.
32

---

The conference expects that many papers will be foundational research and not tied 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 an improvement in the quality of generative models could be used to 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 to 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
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: the paper poses no such risks
Guidelines:
The answer NA means that the paper poses 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 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or 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: the paper does not use existing assets
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.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, paperswi thcode. com 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 it has changed) should be provided.
33

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: the paper does not release new assets
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl 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 is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an 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: the paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in 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 in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 NeurlPS 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.
34


Reviews:
[{"review_id": "yA64WwUFHg", "reviewer": "Reviewer_dyHb", "summary": "The paper presents a primal-dual policy gradient algorithm for infinite horizon average-reward Constrained Markov Decision Processes with general policy parametrization. It uniquely addresses minimizing regret and managing constraints simultaneously, providing the first analysis showing sub-linear bounds of O(T^{4/5}) for both regret and constraint violations. This approach extends the applicability of reinforcement learning to complex, large-scale decision-making problems under practical constraints.", "questions": "- Can you explain in more detail the dependence of the mixing time on the state space  S  and action space  A  is critical, especially in large-scale problems. Clarification on how  t_{\\text{mix}}  scales with  S  and  A  and its impact on the algorithm’s performance would provide a better understanding of the method’s applicability to complex environments.\n- Error propagation for estimated  t_{\\text{mix}} : Information on the numerical performance of the algorithm, particularly how  t_{\\text{mix}}  influences runtime and convergence in practical scenarios, would substantiate the theoretical claims. Experimental results or simulations that highlight these dynamics could significantly enhance the manuscript.", "limitations": "The authors touched upon future work/limitations on theoretical complexity", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is the first to apply a primal-dual policy gradient framework to this particular setting of CMDPs, addressing a gap in the literature.\n- The problem is well-motivated.\n- The paper offers theoretical sub-linear bounds for both regret and constraint violations.", "weaknesses": "- The assumption of ergodicity is quite strong and may limit the applicability of the proposed algorithm in practical scenarios where such conditions are not met. This contrasts with the Upper Confidence Reinforcement Learning (UCRL) framework, which operates under the more relaxed condition of weakly communicating MDPs.\n- The literature review table omits the MDP modeling assumptions. Specifically, the regret bound offered by the proposed algorithm is O(T^{4/5}), while tabular constrained RL algorithms under more general multichain MDP (communicating/weakly communicating) assumptions in [6] achieve O(T^{2/3}). Related facts were not mentioned in the paper.\n- The mixing time, t_{\\text{mix}}, tends to depend unfavorably on the state space S and action space A, reflecting in the overall diameter of the MDPs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Response to **Weakness 1**: Note that the framework of UCRL that works for Weakly Communicating (WC) MDPs is a model-based method that cannot be extended to large state space. Designing model-free algorithms, especially for Constrained MDPs (CMDPs), is an extremely difficult problem. This is evident from the fact that no model-free algorithms are available in the literature that yield provable guarantees for WC CMDPs. Only a single paper in the literature (ref. [8] in the paper) provides a model-free algorithm that works for ergodic CMDPs. Unfortunately, this paper has a worse $\\tilde{\\mathcal{O}}(T^{5/6})$ regret compared to our result and adopts the tabular setup. In contrast, our paper provides the first regret bound for ergodic CMDPs with general parameterization (that subsumes the tabular case) and improves the regret to $\\tilde{\\mathcal{O}}(T^{4/5})$. Extension of our result to the WC case will be considered in the future.\n\nResponse to **Weakness 2**:  Thanks for providing the suggestion. We will add an extra column in the table that states the model assumptions used in the associated works for a fairer comparison between the algorithms.\n\nResponse to **Weakness 3**: Intuitively, $t_{\\mathrm{mix}}$ indicates how fast the $t-$step transition probability converges to the stationary distribution. To the best of our knowledge, there is no known lower bound of $t_{\\mathrm{mix}}$ in terms of $S$ and $A$. Therefore, it is theoretically possible that, even in an MDP with infinite states, $t_{\\mathrm{mix}}$ could be finite.\n\nResponse to **Question 1**: Please refer to weakness 3.\n\nResponse to **Question 2**: We agree that empirical evaluations will help characterize the impact of $t_{\\mathrm{mix}}$ estimation on the performance of the algorithm. However, since ours is a theory-oriented paper, our main goal is to establish provable guarantees for the proposed algorithm. A detailed evaluation will be the subject of future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vgcQgCECp7", "reviewer": "Reviewer_nhM4", "summary": "This paper propose a primal dual policy gradient method for solving average reward constrained MDPs. The primal problem is minimizing the usual RL objective with a averaged reward, plus a penalty induced constraint violation term. The dual problem is to find appropriate Lagrangian multiplier that balances the two objectives to reach equilibrium. The proposed method has reached the claimed regret bound and constraint violation bounds with general policy parameterization.", "questions": "It seems uniform ergodicity is crucial in the paper. I wonder one can relax the assumption for the MDP to be unichain.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written and components are clearly explained. The presentation is good and easy to understand. The investigated topic is interesting and important for real life applications, and average reward is harder to study in general w.r.t to its discounted counterparts due to the absence of contraction of the Bellman operator under the infinity norm. \nThe analysis is easy to follow and plainly laid out. The basic flow of thought is easy to follow and nicely connected. The analysis itself is solid  in terms of its assumptions made in the paper.", "weaknesses": "There are a few points that made this paper limited in its technical contribution.\n1. The claimed the general parameterization seems to rely on an accurate policy model such as neural network. In the paper the authors assumes somehow we can obtain an accurate policy for free. In reality, this is far from the truth. In this sense, the claimed contribution is not much of importance.\n2. Also related to the first point, it seems that for policy evaluation (algorithm 2), the values functions are still in tabular form. Additionally, this is closely following the proposed policy evaluation method in [17] referred in the paper, which seems to the hardest part in average-reward MDPs. Existing literature shows that for policy optimization alone, it is not so different from discounted setup. See\n\nLi, Tianjiao, Feiyang Wu, and Guanghui Lan. \"Stochastic first-order methods for average-reward markov decision processes.\" arXiv preprint arXiv:2205.05800 (2022).\n\n3. There is no numerical experiments to validate the proposed algorithm. There is a growing important for RL researcher to bridge the gap between theories and practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Response to **Weakness 1**: We would like to clarify that we do not assume access to an accurate knowledge of the optimal policy since that would contradict our learning objective. We merely assume that the policy belongs to a class where each member is indexed by a parameter $\\theta$. The goal is to find the parameter $\\theta^*$ that corresponds to the optimal policy. In reality, such a parameterized class can be modeled via a neural network where its weights can act as the index parameter. We start with an arbitrary $\\theta_0$ (which can be far away from $\\theta^*$) and slowly move towards the optimality using our proposed primal-dual steps.\n\nResponse to **Weakness 2**: We agree with the reviewer that the policy evaluation part is inspired by [17]. However, we would like to point out some major differences.\n\n(1) The value estimation (Algorithm 2) is not tabular in the sense that it need not be evaluated for all state-action pairs. This routine only needs to be invoked for the pairs that are encountered by Algorithm 1 on the go.\n \n(2) The parameter $H$ in Algorithm 2 differs from that in [17]. With the same parameter choice, our proposed policy gradient algorithm would diverge.\n\nAdditionally, the overall approach in our paper differs significantly from that of [17]. \n\n(3) In particular, our paper considers a constrained setting, which includes a primal-dual approach that is not included in [17].\n\n(4) Finally, [17] considers a tabular setting which enjoys the strong duality. However, the general parameterization setting considered in our paper does not have the same benefit. The convergence result for the dual problem, therefore, does not automatically translate to that for the primal problem. Our novel introduction of Theorem 1 allows us to separate the objective and constraint violation rates. \n\nResponse to **Weakness 3**: We agree that empirical evaluations will be a nice corroboration of our established results. However, considering this is a theory-oriented paper, our goal is to propose a policy gradient-type algorithm in an infinite horizon average reward setting and establish its theoretical guarantees. A detailed evaluation will be the subject of future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FMTMRtP0Kq", "reviewer": "Reviewer_g5Lw", "summary": "This paper studies learning in constrained MDPs with the long-run average-reward objective. \nIt gives the first sample complexity, regret bound and constraint violation bound in this setting with general parameterization, whereas all prior work is restricted to either tabular or linear parameterizations.", "questions": "See my questions in the weaknesses section.", "limitations": "There is no negative social impact. There are some discussion of limitation in the conclusion section, but not sufficient.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The result and analysis look solid. The presentation is also clear.", "weaknesses": "1 \nThe assumption that all policies induce aperiodic irreducible Markov chain is a bit strong. To what extend can you weaken the assumptions such that the current analysis in the paper still go through? Is it enough if we only assume the Markov chain is weakly-communicating?\n\n2 \nClaiming that the regret is O(T^{4/5}) in table 1 is a bit misleading, because in the regret and constraint violation bounds in Theorem 2, there are actually terms linear in T whose coefficients depend on the transfer error \\epsilon_{bias}. \nI understand that the linear-in-T error terms due to the transfer error are common in the analysis of RL with general parameterizations, and the transfer error is zero when the parameterization is tabular.  \nHowever, it is still worth discussing whether the coefficients of the linear-in-T terms in Theorem 2 are tight and optimal, how they compare to the prior work, and whether they are truly negligible when the policy is parameterized by a neural net of a reasonable scale. \nAt the very least, how the regret and constraint violation are actually calculated should be clarified in a prominent part of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Response to **Weakness 1**: Unfortunately, the proposed algorithm may not be extended to the weakly communicating (WC) setting. In general, it is difficult to propose a model-free algorithm with provable guarantees for Constrained MDPs (CMDPs) without considering the ergodic model. WC CMDPs impose extra challenges in learning compared to the ergodic case. For example, there is no uniform bound for the span of the value function for all stationary policies. It is also unclear how to estimate a policy’s bias function accurately without the estimated model, which is an important step for estimating the policy gradient. The above-stated difficulty is evident from the fact that no model-free algorithm is available in the literature that works for WC CMDPs with provable guarantees. Moreover, only a single model-free algorithm (ref. [8] in the paper) is available for ergodic CMDPs. In other words, all existing algorithms that work for WC CMDPs are model-based in nature. These approaches cannot be extended to the large state space scenario which is the premise of our paper.\n\nResponse to **Weakness 2**: Thanks for providing the suggestion. We will modify the table to point out the dependence on the linear term $T\\sqrt{\\epsilon_{\\mathrm{bias}}}$. The transferred compatible function approximation error is a common assumption in policy-based algorithms (see ref. [10], [11] in the paper). From the sample complexity result (Theorem 1), we can see that the proposed algorithm converges to the neighborhood of the global optima within a distance of $\\sqrt{\\epsilon_{\\mathrm{bias}}}$, which is the same result as in the literature.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bgKk789MDg", "reviewer": "Reviewer_waAx", "summary": "This paper tackles the infinite horizon average reward Constrained MDP setting and proposes an analysis of regret and constraint violation under a general policy parametrization. They devise a primal-dual policy gradient algorithm achieving global optimality while ensuring sublinear bounds on the regret and constraint violation.", "questions": "See the weakness section.", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is interesting and well-written and places itself well in the related literature by filling the gap about infinite horizon average reward constraint MDPs under general parametrized policies. \nThey employ similar techniques that can be found in the related unconstrained setting but also highlight and overcome the challenges encountered while facing the constrained and average reward setting. In particular, they take inspiration from already existing techniques developed for the discounted setting and adapt them to cope with the average reward MDP.", "weaknesses": "From the theoretical perspective, I do not recognize specific weaknesses. \n\nHowever, I would like to highlight that the authors assume the knowledge of the mixing and hitting time of the MDP. I recognize that this is a standard assumption in this type of work, however, I wonder if they are necessary to achieve these results or if the authors are aware of similar techniques that can provide sublinear guarantees without this knowledge. Recently, the work of [1] highlighted some techniques that allow achieving global convergence results without this knowledge. Would it be possible to apply these techniques to this setting as well?\n\nFrom the simulation perspective, I believe that some experimental results showing the validity of the presented approach may be beneficial for the presented work.\n\n\n\n[1] Patel B. et al., Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles, ICML 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Response to **Weakness 1**: Thank you for suggesting the paper by Patel et. al. where the algorithm works without the knowledge of $t_{\\mathrm{mix}}$.  We would like to point out that such a feat is achieved by introducing an additional assumption and weakening the convergence result. In particular, the paper solves the average (unconstrained) MDP problem via an actor-critic approach where the value function of the critic is taken to be a linear function of a feature vector. No such assumption is needed in our paper. Secondly, their approach introduces an additional critic error $T\\sqrt{\\epsilon_{\\mathrm{critic}}}$ in the final regret, in addition to the usual approximation error $T\\sqrt{\\epsilon_{\\mathrm{bias}}}$. Despite these drawbacks, we agree that their approach is worth exploring in the future. However, we believe that if the linear critic assumption in this paper is relaxed, the regret bounds will become even worse (a similar effect has been recently shown in the sample complexity result of discounted MDPs). We are currently not sure about the applicability of this technique to our CMDP problem.\n\nWe would also like to mention that the suggested paper became public on arXiv on March 18th for the first time, which is within two months of the NeurIPS 2024 abstract submission deadline, and thus could be considered as concurrent research. We will cite this work in the final version, and suggest extending its approaches to CMDPs as a future work. \n\nResponse to **Weakness 2**: We agree that empirical evaluations will be a nice corroboration of our established results. However, considering this is a theory-oriented paper, our goal is to propose a policy gradient-type algorithm in an infinite horizon average reward setting and establish its theoretical guarantees. A detailed evaluation will be the subject of future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kTWEZRNdSh", "reviewer": "Reviewer_UyCM", "summary": "The paper explores RL in Infinite-horizon Ergodic Average-reward constrained \nMDPs under general policy parametrization. In this setting, the authors propose \na primal-dual based policy gradient algorithm that simultaneously optimizes the \npolicy parameter and a constraint violation penalty term $\\lambda$. They also \nequip their method with techniques to address challenges due to the \naverage-reward MDP setup, constraints on the MDP and general policy \nparametrization. They prove global convergence of their resulting method in \nterms of the Lagrange function and from this derive bounds on the expected \nregret as well as constraint violation. Furthermore, when the policy class is expressive enough to approximately contain an optimal policy of the constrained MDP so that the un-expressivity parameter $\\varepsilon_{bias}$ is zero or negligibly small, the authors prove that the \nexpected average regret and constraint violation of their method decreases at a rate of $O(T^{-1/5})$.", "questions": "1. In Lines 243-246, the authors claim that there are scenarios under \n\twhich the un-expressivity parameter $\\varepsilon_{bias}$ is zero or \n\tnegligible. I could reason about this claim when $\\pi^{\\*}$ is an optimal \n\tpolicy in the unconstrained MDP, but unsure that the same holds when \n\t$\\pi^{*}$ is an optimal policy in the constrained MDP (see Line 240). Can \n\tthe authors kindly provide exact pointers in the referenced \n\tpapers that verify this claim, or a proof in the appendix?\n\n2. In Lines 323 and 324, the authors claim that the primal-dual approach to policy optimization\n\tis known to give worse results than in the unconstrained version, even for \n\tthe discounted setting. Could this be related to the fact that the method is policy, rather than value based? In the offline setting, [1] takes a value-based primal-dual approach and their result implicitly highlights that the constrained setting may not be worse off than the unconstrained setting.\n\n3. Can the authors kindly elaborate on the bias of single \n\ttrajectory-based estimations in this setting? Reference [13] in the paper seems to \n\tachieve better performance even with this biased estimation strategy.\n\n4.  How strong is Assumption 5?\n\n[1] Hong, K., \\& Tewari, A. (2024). A Primal-Dual Algorithm for Offline \nConstrained Reinforcement Learning with Low-Rank MDPs. arXiv preprint \narXiv:2402.04493.\n\n**Comments**\n1. Line 265 makes reference to equation 21 twice rather than the \n\texpressions after lines 263 and 264.\n2. Expectation is sometimes expressed without the parenthesis. For \n\texample, see Equations 20, 22, as well as Lines 265, 266 e.t.c.", "limitations": "None. This is a purely theory paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors consider the task of reinforcement learning \n\tin average-reward constrained MDPs and propose novel techniques to address \n\tunderlying challenges.\n2. This is a complete piece of work that explores provably \n\tefficient RL in average reward constrained MDPs. Their claims are backed by \n\ttheoretical analysis, and they highlight the strength as well as weaknesses \n\tof their work.\n3. This submission is clearly written. The authors highlight \n\tthe required assumptions and adequately discuss the nature of most relevant \n\tparameters.\n4. This work significantly contributes to existing theory \n\ton reinforcement learning when it is more desirable to optimize the average \n\treturn, rather than the typical discounted return, and in addition to \n\treturn optimization, the policy is required to adequately adhere to \n\tadditional constraints on the MDP.", "weaknesses": "See questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Response to **Question 1**: Note that a constrained MDP can be considered as an unconstrained MDP where the (equivalent) reward function is $r+\\lambda c$ and the optimization is performed over all policies $\\pi\\in \\Pi$ and $\\lambda\\geq 0$. In other words, the original constrained optimization is equivalent to the following primal formulation: $\\max\\_{\\pi\\in\\Pi}\\min\\_{\\lambda\\geq 0} J^{\\pi}\\_{r+\\lambda c}$. Note that the solution to this max-min problem, $\\pi^*$ is precisely the solution to the original CMDP. Therefore, it is natural that $\\epsilon_{\\mathrm{bias}}$, in this case, is defined via $\\pi^*$ and $A_{\\mathrm{L}, \\lambda}$ where $A_{\\mathrm{L}, \\lambda}=A_r+\\lambda A_c$ denotes the advantage function corresponding to $r+\\lambda c$. A similar definition of $\\epsilon_{\\mathrm{bias}}$ can also be found in earlier works (e.g., see Assumption 4 in ref. [4])\n\nResponse to **Questions 2 and 3**: The remark that the primal-dual approach performs worse than the unconstrained setup was mainly targeted for general parameterization. Table 1 in the paper shows that a similar conclusion does not hold for either tabular or linear MDPs. The paper by Hong and Tewari cited by the reviewer assumes a linear MDP setup and thus is not a focus of this discussion. To understand why a gap arises between a constrained and an unconstrained case in general parameterization, one can take a look at Lemma 6.  An extra $\\beta$ term (dual learning rate) appears in the convergence of the first-order stationary result which is accompanied by an $\\mathcal{O}(\\beta^{-1})$ term during the segregation of objective optimality gap and constraint violation rate (Theorem 1). Note that the second $\\mathcal{O}(\\beta^{-1})$ term is absent in unconstrained case which allows us to choose $\\beta = 0$ and obtain a convergence rate of $\\tilde{\\mathcal{O}}(T^{-1/4})$ as in [13]. However, such a choice is infeasible for the constrained case, leading to a worsening of the final result.\n\nResponse to **Question 4**:\nFor Assumption 5: Assumption 5 is also common (Liu et al., 2020) in the policy\ngradient analysis. This is not a very restrictive assumption. We corroborate this claim by quoting (Liu et al., 2020) (where this assumption is Assumption 2.1):\n\n``This is a common (and minimal) requirement for the convergence of preconditioned algorithms in both convex and nonconvex settings in the optimization realm, for example, the quasi-Newton algorithms [40, 41, 42, 43], and their stochastic variants [44, 45, 46, 47, 36]. In the RL realm, one common example of policy parametrizations that can satisfy this assumption is the Gaussian policy [2, 48, 19, 21], where $\\pi_\\theta(\\cdot| s) = N(\\mu_\\theta(s), \\Sigma)$ with mean parametrized linearly as $\\mu_\\theta(s) = \\phi(s)^T\\theta$,\nwhere $\\phi(s)$ denotes some feature matrix of proper dimensions, $\\theta$ is the coefficient vector, and $\\Sigma >0$\nis some fixed covariance matrix. In this case, the Fisher information matrix at each $s$ becomes\n$\\phi(s)\\Sigma^{-1}\\phi(s)^T$, independent of $\\theta$, and is uniformly lower bounded (positive definite sense) if $\\phi(s)$\nis full-row-rank, namely, the features expanded by $\\theta$ are linearly independent, which is a common\nrequirement for linear function approximation settings [49, 50, 51]. \n\nFor $\\mu_\\theta(s)$ being nonlinear functions of $\\theta$, e.g., neural networks, the positive definiteness can still be\nsatisfied, if the Jacobian of $\\mu_\\theta(s)$ at all $\\theta$ uniformly satisfies the aforementioned conditions of $\\phi(s)$\n(the Jacobian in the linear case). In addition, beyond Gaussian policies, with the same conditions\nmentioned above on the feature $\\phi(s)$ or the Jacobian of $\\mu_\\theta(s)$, Assumption 2.1 also holds more\ngenerally for any full-rank exponential family parametrization with mean parametrized by $\\mu_\\theta(s)$,\nas the Fisher information matrix, in this case, is also positive definite, in replace of the covariance\nmatrix $\\phi(s)\\Sigma^{-1}\\phi(s)^T$ in the Gaussian case [11]. \n\n\nIndeed, the Fisher information matrix is positive definite for any regular statistical model [28].\nIn the pioneering NPG work [24], $F(\\theta)$ is directly assumed to be positive definite. So is in the\nfollow-up works on natural actor-critic algorithms [39, 7]. In fact, this way, $F_\\rho(\\theta)$ will define a\nvalid Riemannian metric on the parameter space, which has been used for interpreting the desired\nconvergence properties of natural gradient methods [3, 32]. In sum, the positive definiteness on the\nFisher preconditioning matrix is common and not restrictive. \"\n\nWe will expand on this in the revision to explain Assumption 5.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a primal-dual-based policy gradient method for solving infinite-horizon average-reward CMDPs with general function approximation. The paper proves that the proposed algorithm achieves an $O(T^{4/5})$ bound on the regret and constraint violation. 
 
The reviewers unanimously agree that the paper's contributions merit acceptance. Please incorporate the reviewers' feedback. In particular, addressing the following concerns will help strengthen the paper:
- Included a fairer comparison between algorithms especially those that achieve a stronger $O(T^{2/3})$ regret (response to Rev. dyHb)
- Mention the limitation of the derived results - $t_{mix}$ is typically unknown and in some cases, it may have a bad dependence on the size of the state space. 
- Include the appropriate reference to [17], and explain why the assumption can/cannot be relaxed to handle unichain/weakly-communicating MDPs. 
- Justification for Assumption 5 (response to Rev. UyCM)
Decision: Accept (poster)