Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach
Authors: Swetha Ganesh
Vaneet Aggarwal
Venue: NeurIPS 2025 poster ()
Keywords: Actor-Critic
Regret
Policy Gradient
Average-reward MDP
Unichain MDP
Primary area: reinforcement_learning

Abstract: Actor-Critic methods are widely used for their scalability, yet existing theoretical guarantees for infinite-horizon average-reward Markov Decision Processes (MDPs) often rely on restrictive ergodicity assumptions. We propose NAC-B, a Natural Actor-Critic with Batching, that achieves order-optimal regret of \$\tilde{O}(\sqrt{T})\$ in infinite-horizon average-reward MDPs under the unichain assumption, which permits both transient states and periodicity. This assumption is among the weakest under which the classic policy gradient theorem remains valid for average-reward settings. NAC-B employs function approximation for both the actor and the critic, enabling scalability to problems with large state and action spaces. The use of batching in our algorithm helps mitigate potential periodicity in the MDP and reduces stochasticity in gradient estimates, and our analysis formalizes these benefits through the introduction of the constants $C_{\text{hit}}$ and $C_{\text{tar}}$, which characterize the rate at which empirical averages over Markovian samples converge to the stationary distribution.

Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach
Swetha Ganesh Purdue University, USA ganesh490purdue.. edu
Vaneet Aggarwal Purdue University, USA vaneet@purdue. edu
Abstract
Actor-Critic methods are widely used for their scalability, yet existing theoretical guarantees for infinite-horizon average-reward Markov Decision Processes (MDPs) often rely on restrictive ergodicity assumptions. We propose NAC-B, Natural Actor-Critic with Batching, that achieves order-optimal regret Ö(VT) in infinite- horizon average-reward MDPs under the unichain assumption, which permits both transient states and periodicity. This assumption is among the weakest under which the classic policy gradient theorem remains valid for average-reward settings. NAC-B employs function approximation for both the actor and the critic, enabling scalability to problems with large state and action spaces. The use of batching in our algorithm helps mitigate potential periodicity in the MDP and reduces stochasticity in gradient estimates, and analysis formalizes these benefits through the introduction of the constants Cыt and Cur. which characterize the rate at which empirical averages over Markovian samples converge to the stationary distribution.
Introduction
Reinforcement Learning (RL) involves an agent interacting with an unknown environment to maxi- mize long-term rewards. has been successfully applied to diverse areas such as traffic engineering, resource allocation, and ride-sharing [1851. (]. RL problems commonly framed as episodic, discounted, or (infinite- horiiteee average-reward; the average-reward setting is especially suited to real-world tasks due its ability to better capture long-term behavior.
Our focus is on the average-reward Markov Decision Process (MDP) setting, where key measure of algorithmic performance is expected regret. [7] established that for broad class of MDPs, any algorithm incurs expected regret lower bounded by 22( D(V where T is the time horizon. Many existing regret analyses in this setting assume ergodicity, a strong assumption that simplifies analysis by ensuring fast mixing to a stationary distribution, but is often difficult to verify or justify in practice.
In the absence of ergodicity, existing algorithms are typically designed for model-based or tabular settings, with computational complexity that scales with |S] and |A], the cardinalities of the state and action spaces, respectively. These requirements are prohibitive for environments with large or continuous state and action spaces. Although linear MDPs reduce improves dependence on |S they still rely on strong structural assumptions, namely, linearity of the transition dynamics and reward functions. Moreover, value-based methods in such settings often remain computationally expensive due to the need to maximize over all actions at each iteration.
To overcome these limitations, a promising alternative is the use of Policy Gradient (PG) methods, which directly optimize parameterized policies, often modeled by neural networks, via gradient descent. While PG methods have shown strong empirical performance, most theoretical analyses assume ergodicity. In contrast, our work develops PG methods that do not rely on ergodicity.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Algorithm
Regret
Ergodicity-free
General Policy
MDP-OOMD 38
Õ(VT)
No
No
Optimistic Q-learning
38
O(T4/3)
Yes Yes(1)
No
MDP-EXP2
O(VT)
No
No
UCB-AVG 45
O(VT)
Yes(1)
No
PPG 99
O(T
No
Yes
PHAPG [17
O(VT)
No
Yes
Optimistic Q-learning
3
O(VT)
Yes
No
7-DC-LSCVI-UCB 20
O(VT)
Yes (1)
No
This work (Algorithm
Ö(VT)
Yes
Yes
Table I: A comparison of regret bounds for model-free RI algorithms in infinite- -hriiznn average- reward MDPs. By "General Policy," we refer to algorithms that employ a parameterized, policy- approach where the parameter vector 0 E Rd, possibly with d < |S] (1) These analyses consider the more general setting of weakly communicating MDPs or Bellman optimality.
Specifically, we make only minimal assumption: each policy induces unichain MDP, i.c., it has single recurrent class. This relaxation enables analysis in more general and realistic environments.
1.1 Related works
Value-Based Approaches:
Model-based algorithms like those in model-free methods, achieve the optimal O(VT) regret. However, most tabular and value- based, maintaining Q-values for each state action pair, an approach that scales poorly to large continuous spaces. Examples include optimistic Q-learning methods [8 45). The y-DC- LSCVI-UCB algorithm (20) improves scalability with respect to |S| but requires maximization each iteration, which is still computationally expensive for large |A]]. Furthermore, its analysis assumes linear MDP with known feature representations, whereas our setting is considerably more general and does not rely on such structural knowledge or assumptions.
21
46). as well as recent
over the entire action
Direct Policy Gradient Approaches: Unlike value-based based methods, policy gradient (PG) approaches well-suited to environments with large continuous state and action spaces, and relatively easy to implement. Despite their empirical success, theoretical analysis of PG methods has largely focused ergodic MDPs. This is due to favorable properties in the ergodic setting, such bounded hitting times and fast mixing, which simplify analysis and enable near-optimal regret bounds. These properties ensure that samples collected fmix steps apart approximate independent draws from the stationary distribution. Algorithms like MDP-OOMD (8). PPG (9, and PHAPG [17] exploit these characteristics construct low-bias value estimates. However, to the best of our knowledge, no prior work provides regret guarantees for PG methods in the more general unichain setting, where such strong mixing assumptions do not hold.
Actor-Critic Approaches: In contrast to direct policy gradient methods that estimate gradients from sampled trajectories, Actor-Critic (AC) methods use Temporal Difference (TD) based critics to aid policy gradient through bootstrapped value estimates. Further, direct methods scale poorly and rely access to mixing hitting times, typically unknown in practice. AC methods are more sample-efficient but introduce addtional bias, making theoretical analysis harder. Regret results for AC methods are limited and focus on global convergence (pseudo-regret),
in 29 37 [6].
The MLMC-NAC algorithm in [16] achieves order-optimal convergence using multi-level Monte Carlo reduce bias, but still assumes fast mixing. Extending such results to unichain MDPs, which lack exponential mixing, requires fundamentally different techniques and is the focus of this paper.
The Optimistic Q-learning algorithm BJ, discussed earlier, is value-based. The SPMD method in 23 takes a policy-based approach with order-optimal sample complexity but uses tabular policy, leading to poor scalability with large action spaces. It also assumes access to a simulator (generator), which is often unrealistic. Moreover, both works rely stronger assumptions than the classical unichain condition used in our analysis (see Remark
Unichain Analyses: A few recent works explicitly address the unichain setting 3 23
Discounted to Average Techniques: The most common strategy for relaxing ergodicity assumptions in reinforcement learning is to reduce the average-reward problem to discounted MDP. This reduction is widely adopted in works addressing weakly communicating Bellman optimality

---

settings [38 45 20 46), where the discounted problem is solved with discount factor close to In particular, these works select ? satisfying 1/(1 -7) ~ T for some > Notably, this approach requires very sharp bounds in DMDPs in terms of 1/(1 - -) whereas, existing guarantees for policy gradient methods the discounted setting exhibit very poor dependence on this term, resulting in much weaker performance bounds if such Discounted to Average Techniques are used (see Appendix A). Additionally, these approaches require access to a simulator that allows sampling from given distribution P at each iteration, which can be impractical.
1.2 Main contributions
We propose an actor-critic algorithm in Algorithm T Natural Actor Critic with Batching (NAC-B), that achieves order-optimal regret of Ö(vT) in average-reward Markov decision processes (MDPs) under the unichain assumption. Our key contributions are summarized as follows:
First Regret Guarantees for General Policy Gradients Beyond Ergodicity: While policy gradient (PG) methods with general parameterizations have been analyzed under the restrictive ergodicity assumption, we extend this to the weaker unichain condition. This aligns with the assumption used in the foundational policy gradient theorem for average-reward MDPs [33. Our work provides the first regret guarantees for parameterized PG methods under this setting.
Online Learning Without Simulator Access: Unlike discounted-MDP reductions that require simulator to reset to arbitrary initial distributions at each iteration, our algorithm operates entirely online in unichain MDPs. This enables learning in environments where simulator access is unavailable or costly (e.g., real-time network traffic engineering, robotics).
Analyses in the ergodic setting rely crucially on the property of exponen- tially fast mixing. In contrast, the classical unichain setting does not generally admit analogous results. For example, a periodic Markov decision process, the quantity lim (P=9)((s))))))) may not even exist. To address this challenge arising from periodicity, we employ large-batch averaging.
Technical Challenges:
Specifically, we show that the time-averaged distribution
(Pre)
d= ()) con- TV
verges to the stationary distribution at a rate of (1/Lt) (see Lemma Dp. This averaging approach enables to show that the bias and variance of our estimators decay a sufficiently fast rate, albeit not exponentially (see Lemma 3). An additional consequence of these results is that they facilitate the derivation of bounds on the value and Q-functions.
Despite the reduction in bias and variance, transient states continue to pose analytical challenges. Intuitively, this is because they do not contribute meaningful long-term information. A more technical explanation is provided in Section 4.2 To isolate the impact of transient states, we prove a rapid entry into the recurrent class (Lemma 1O). Combined with the strong Markov property, this allows us to restrict our analysis to the recurrent class.
2 Problem Formulation and Preliminaries
We study an infinite-horizon reinforcement learning problem with an average reward criterion, mod- eled as Markov Decision Process (MDP). The MDP represented by the tuple M = AS,A, P, p). where S denotes the finite state space and A represents the finite action space. The reward function r: x A- + [0. 1] assigns bounded reward to each state-action pair. The state transition function S:S x A- + A ISi determines the probability distribution over the next state given the current state and action, where A denotes the probability simplex over S. The initial state distribution given by p:: + [0, 1]. A policy : S + A specifies probability distribution over actions for each state. Given policy ग, the long-term average reward is defined as
J
E
r(st, az)
80 10000p0
where the expectation is taken over trajectories generated by executing actions according to a, ~ T(|[s;) and transitioning states via St+1 P(- at), for all t > 0. For simplicity, we drop the dependence on P whenever it is clear from the context. We focus on a parametrized policy class III where each policy is indexed by parameter 0 E ll., with II C Rd. Our goal is to solve the optimization problem: maxeglle _ & (()..
3

---

A policy To E II induces a transition function p S + Alsi, given as (s, s') Eaea ())o(l)) Vs, s' e S. The conresonningg stationary distribution defined as:
Definition 1. Let t given by
A Alsl denote the stationary distribution of the Markov chain induced by πτ.
de (=)
lim T-+00
E
Pr(st = = po)
T
t=
We assume the following property for the MDP, which defined as a unichain MDP:
Assumption 1. The MDP M is such that, for every policy π E II, the induced Markov chain has single recurrent class.
Remark 1. An MDP M satisfying this property is referred to unichain MDP (30]. This assumption does not require irreducibility, as transient states may be present, nor does it impose aperiodicity. Consequently, it is strictly weaker than the standard ergodicity assumptions.
Under this condition, the stationary distribution du is well-defined, independent of the initial distribution p. and satisfies the balance equation: (Pme)) J do = d=
This assumption forms the basis of the foundational policy gradient theorem for average-reward MDPs [33]. Although various alternative definitions of umichain MDPs appear in the literature, the notion employed here is classical and, in fact, weaker than several recent formulations. For example, 3 assume the existence of state Su that is recurrent under all policies, stronger condition than ours. Similarly, [23] adopt a mixing unichain assumption, which additionally requires aperiodicity. In contrast, our analysis does not depend on either of these stronger conditions.
Since we cannot rely on the mixing time commonly used in the analysis of ergodic MDPs, we consider two alternative quantities, C and Ct which are more appropriate in the unichain setting. These are defined with respect the Markov chain induced by stationary policy follows:
Let S% SS denote the recurrent class under policy Ty. and let Te = inf 2 0: 8t E S denote the first hitting time of the recurrent class. Then define
Chit == max [T]].
#ES
as the worst-case expected time to enter the recurrent class when starting from any state S. Note that if there are no transient states, then Ct 0.
Similarly, for any s, s S, let To infft 2 we define
0: 8,
s'3 be the first hitting time state s'. Then
ch
Σ d" d'('')E e'ES
(4)
as the expected time to reach a state drawn from d starting from a fixed state E St. Notably, by the Random Hitting Target lemma (Corollary 2.14, (6), this quantity is independent of the choice of We define Chit sup, C and Ctar == sup, C and C' = Chit + Otar.
We write the average reward
(() _andro aa (11)) a)] (d T0, where (=) & Σ (r(s,a)To(alo) e (5)
aEA
The average reward (0) is also independent of the initial distribution, p. Furthermore, vO E Ile. there exist a function QT S x A - R such that the following Bellman equation satisfied v(s.a) E S A.
as, = r(s, a) ((0) + Ev-P(()sa)) [s*)(s')]
(6)
where the state value function, V S + R is defined as (** = Ene no =a(a)s) (s, a), Vs 30). Note that if is satisfied by t then it is also satisfied by QT + e for any arbitrary constant, C.
Additionally, define the advantage function A5 a) A (se a) holds, it is known that the policy gradient at 8, oo can be expressed as follows 33
(s) If Assumption
( ( [A (s, a) Vo log (a)ss))

---

where y (s, a) == d (s) This is commonly referred to as the Policy Gradient theorem and while the proof can be found [33, we include it in Appendix for completeness.
Natural Policy Gradient (NPG) methods update A along the NPG direction wg defined as
w = Vo
(8)
where j denotes the
pseudoinverse and F(0) is the Fisher matrix defined as
F(Ø) = E Vo log () Vo log mo(a)s) where the expectation is taken over (s, a) vaa This yields the NPG update
0k+1 O2 + owd..
Let J A su J0). For given MDP M and a time horizon T, the regret of an algorithm A is defined as follows.
Algorithm 1 Natural Actor-Critic with Batching
1: Input: Initial parameters Oo, {wo), and {ck policy stepsize a, critic parameters (3, cp). NPG stepsize 7, initial state Sg ~ p. outer loop size
Regr(A, M)
Σ
(10)
K, inner loop size H, batch-size B do Average reward and critic estimation do
2:
for 1,,
where the action, ags E (0, (0. is cho- sen by following the algorithm A based the trajectory up to time, i, and the state, 9 is obtained by following the state transition func-
3:
4:
for 0, 1, ...
5:
s2 -- 80
6:
for b 1, 2, B. do
7:
Take action af no,
kb) Collect next state 6--1
tion, P. Wherever there is no confusion, we shall simplify the notation of regret to Regy.
8:
Ph
0
3 Proposed Algorithm
9:
Receive reward r(s ( agth)
10:
end for
Update the combined average reward and critic estimate < = =In Sh] using (22
We propose a Natural Actor-Critic with Batch- ing algorithm (Algorithm[I) I]. which runs for K outer iterations (or epochs) of natural policy gradient updates. Each outer iteration includes H inner iterations estimate the average re- ward and value function, followed by another H iterations to estimate the NPG direction. We first present the necessary preliminaries, fol- lowed by the detailed description of the algo- rithm.
12:
8 kh
13:
end for
14:
& <- ck
SH
15:
D Natural Policy Gradient estimation
16:
for h 0, H. do
17:
8k < 50
18:
for b 1, ... do ~ To,
19:
Take action ag thh
(-1sph)) kh) kh s b-1
20:
Collect next state
Preliminaries: For any fixed 0₁. it is known that wg the solution the optimization prob- lem
P(
kh kh
21:
Receive reward r(shh ,
22:
end for
23:
Update NPG estimate wf using 25
29
wt = arg min To (w, 0x),
24:
sp + kd s
25:
end for
where TupTo (w, 0) is defined follows
26:
> Policc update
27:
sR + so
Lupoo (w,
28:
Update policy parameter 0μ using 0x+1 +
1
E (ATO w
0g + awk
29:
8p < 8B
(11)
30:
end for
where the expectation taken over (s, a) ~ 1e It can be seen that Lyve (w, (f) is quadratic function in with gradient given F(l) (()).. Since neither F(Ox.) nor v. ) is available in closed form, we estimate them from samples and perform stochastic gradient descent on L, (w, 0x) to obtain approximate NPG direction wi.
We estimate F(Ox) using the outer product [V log ne, (als) V log ne, (als) computed from samples (s, a) no. However, estimating (.)( ) is more challenging, as requires access to the advantage
5

---

function, which is not directly observable. We note that A (s.a) a) can be expressed using J(O)) and V as follows from the definition of A (s, a) and Bellman's equation. Consequently, we focus next on estimating these quantities.
Notice that 7) (Ok) is the solution the following equation:
Re (m)) where
Re, (17 ((aa))= 5h (1)
r(s, a)].
(12)
Given access to Ra, (1). the solution to the above can be computed via the following iterative update:
m = Th - co (Th).
(13)
where 33 and Cg are step-size parameters.
To approximate the value function V (-), we employ a linear critic )) Co, o()), where So, E R denotes the critic parameter and (0s) E I a feature mapping satisfying [ø[s]] < 1
for all 8 E S. We also assume that the feature vectors (5() are linearly independent. The parameter
Sa, E IR' is obtained by solving the following optimization problem:
min ElO,, () = 2 CE
E Band" (V)))s)))((ss)))
(14)
This formulation enables the use of a gradient- gradient-based iterative procedure to compute Sox- Specifically, the gradient of E(Ok: () is given by:
[(vTe) V()(())) V. (cV((.
VeB(On:
()
E o0
(15)
E o [(VR0) (8) - ((s)) [(s)
The above quantity can be approximated as follows
Vc Fe () B [(V (8) (T)()))(()))
(16)
(s th s P() [(r(s, - j(0k) + (5) - 55 (()) d(s)]
(17)
Bss " s(mP())).)) [(((s,a) J(0z) +5 ((() <T<(sT))) o(s)) (ss]
(18)
F( ()
(19)
Using this gradient, Ço. can be computed iteratively via: ch 1 = c EV,E (t).
(20)
The updates in and 20 can be combined into one update for ch = [nn)T (ch) T as follows
ch+ = <x - (v E(Or TIT
(21)
The joint update rule for v/h and c in (21) forms the basis of the critic step in Algorithm 1 where sample averages from the trajectory are used in place of the intractable expectations.
Algorithm I operates using a single trajectory of total length T = 2K B. For each outer iteration k. the algorithm collects contiguous segment of 2BH samples by following the current policy THL, starting from the final state of the previous iteration. The first BH samples from TØ are used to perform H iterations of the critic update subroutine, and the next BH samples are used for H iterations of the NPG update.
Critic subroutine: For each h E O,..., H 1, we sample averaged version of 21 to obtain the update
ch+1 ch
Σ
ux ox(2 shi)
(22)
b=1
where 3 is the critic learning rate, B is the batch size, =//hhh and o(=f%,, Rh. <k) is given by:
( a skh ,) is sampled transition,
(2 kh, eth = (,,,,, shich - by (1a, 2bh,,
(23)

---

where the matrices are defined as
A. =(th)
CB (
0 (( ( ( 7)
(0k,,,
car(s a rrs8 ob a )o(s)
(24)
The resulting update follows standard constructions in Temporal Difference learning (e.g., [44 After H critic updates, we take Th = TH and Ço == Sh as the final estimates of the average reward and critic parameters, giving (Gk. -) Sk c(-) as the value estimate.
Natural Policy Gradient estimation: The advantage estimate at sample kh is computed from the Bellman equation using T7s and ((kk,) -) as follows
T (=b kh: Ex) r(sb" abth) 7 + Ck ( (bbb))]
(25)
Based on the above estimate, we construct an approximate policy gradient:
by (6x, Ex. 25 = n (=h" Vx log To, (ag shhh)
(26)
and refine the natural gradient estimate wi via H iterations of the update:
w w ?
1 [
(x(== kh Ex)
(27)
where y is the NPG learning rate. The update direction ux(=t"; Ek) is given by
uu (2b kh. Ex) = (Ox, 2b Ju - bu(0 Ek. )
(28)
with
Au(O,, kb) = Vo log Toz (a kh Vo log To, (a, ((b") (h)T.
(29)
Set W/ == wht. The policy is updated as: 0x+1 = 0g + owk, where a is the policy learning rate.
4 Regret Guarantee for Unichain MDP
4.1
Assumptions
Let (0) == E. (0, and (0) Eg (0, =)] where (9, 2). (0, defined in
24
and and (26) and the expectation Esg is computed over the distribution of = (s, a, s') where (s, a) ~ 1
~ P(-|s, a). For arbitrary policy parameter 6 we denote E [0) = Ina cpl Using these notations, below state some assumptions related to the critic analysis.
Definition 2. We define the critic approximation error, Capp as follows.
Capp sup inf { < (2 Eondro (v V(C. (
(30)
The definition 2 is widely adopted in the literature 132
16
29 12], although there may be
minor variations notation, such as the inclusion of square root. This definition closely linked to the representational capacity of the chosen feature map, with fapp characterizing the resulting approximation eиror. A well-constructed feature map can yield small or even vanishing capp-
Assumption 2. Let Me Ee (o(s) (o(s))
where the expectation Egg is taken over ~ d and s' ~ (s..). Then, for all 0, there exists constant X > 0 such that for all x E ker(Ma)+ (i.e., the subspace orthogonal to the kernel of Mo), the following inequality holds:
x MMa 2 2|
(31)
Comments on Assumption 2: We emphasize that this condition is substantially weaker than the commonly imposed requirement strict positive- Dositive-definiteness of Mg, which appears in nearly all Actor-Critic works [16] 29 37 28 32). In Section 4.2, explain why the strict positive definiteness of the critic matrix cannot be guaranteed in the unichain case, as opposed to the ergodic case, and discuss the resulting analytical challenges.
We will now state some assumptions related the policy parameterization. Before proceeding, we define the policy approximation error.
7

---

Definition 3. Define Ebias as the least upper bound on the transferred compatible function approxi- mation evror, Ly (wg; f), i.e.
Obiss == suu L (wig;))
where wi denotes the exact Natural Policy Gradient direction at indicates the optimal policy, and Lu is defined in (II).
The term ébias is a standard quantity in the literature parameterized PG methods 14 26
37 16 17 40 and reflects the expressivity of the chosen policy class. For example, when the policy class is expressive enough to represent any stochastic policy, such with softmax parameterization, we have Cbias = [ In contrast, under more restrictive parameterizations that do not cover all stochastic policies, we may have ébias
0. Nevertheless, this bias is often negligible when using rich neural network parameterizations [36].
Assumption 3. For all 0, 0,, 02 and (s,a) E S x A. the following statements hold.
(a) Ve log (a{a))) & G₁ (b) I[ log ne, (als) - Ve log Te, (a|s)]l S 11 02ll Assumption 4 (Fisher non-degenerate policy). There exists constant μa > 0 such that F(0) ula is positive semidefinite where Ia denotes an identity matrix.
Comments on Assumptions 3 We emphasize that these are standard the PG literature 24 14 26 [5] 32,
Stiiuuaa that the score function is both bounded and 37 [6] [7]. Assumption stipulates
coabbitz-ccntinuousu an assumption frequently used in error decomposition and in bounding the policy gradient. Assumption 4 requires that the eigenvalues of the Fisher information matrix uniformly bounded away from zero, a condition commonly employed to establish global complexity guarantees for PG methods. Notably, Assumptions - have recently been verified for range of policy classes, including Gaussian and Cauchy distributions having parameterized means with
clipping [24 14]
4.2
Main Result
The following theorem gives the regret bound for the proposed algorithm.
Theorem (Main Result). Consider Algorithm 7 and suppose Assumptions A Let be L. smooth and set K = (VVT Co(VT/(log /log T)), = O (TVT) and H = (log T). Then, for a suitable choice of learning parameters, the expected regret satisfies
[[Regr] 5 20T(( (T(Vebias + /Eapp) VT(C + Crai)).
(32)
where C= Crar + Chit-
The choice of learning rates along with the regret bound containing all problem-speciie constants is provided in Appendix H We now provide brief overview of the proof. We first begin with regret decomposition obtained using standard techniques:
Lemma 1. Consider the setting in Theorem
Then, the expected regret of Algorithm 7 satisfies
K
K
B[Regr] < T /ebins + HBG
Σ
E [[
will + GGHH
E
Wk will
k=
k=U
HG2HB
K-1
HB
E (O +
E Egdd
(+1s)) + 2C(K + 1).
(33)
112
k=
The proof of the above is given in Appendix G This regret decomposition crucially depends on the bias, E (EE, [w]] - wI and second-order error of the NPG estimate, E ||w, - w These in turn dependent on the quality of the critic estimates. Hence the main focus our proof consists of bounding these terms. The analysis of remaining terms then follows from these bounds; details are provided in Appendix
Properties of Markovian Sample Average: Analyses in the ergodic setting often rely on the property of exponentially fast mixing. contrast, even irreducible but periodic Markov chains do not exhibit analogous exponential mixing behavior. A common strategy to address periodicity is to apply time- averaging, for which convergence results are available the literature for irreducible, periodic chains 31]. In what follows, we extend such results to Markov chains with single recurrent class.
8

---

Lemma 2. Let Assumption 7 hold and consider any 0 E Il Then, the following bound holds:
pd ( (()())
S
Vsa E S.
(34)
Using the result above, we show in the following lemma that employing a batch size of reduces both the bias and variance of the estimate by factor of 1/B. Accordingly, in Algorithm | we choose a large batch size B = (VVT) to obtain an order-optimal dependence on T in the regret bound.
Lemma 3. Let Assumption 7 hold, and let f S + R satisfy [s) Cy for all S, for some constant Cj > Then, the following bounds hold:
(i)
E
1 B
Σ
- S
Vdcio (ii)
EE
1
B
- l'
+9+2Vac3C
99
B
B
where E denotes the expectation of the Markov chain {si} induced by ne starting from any so E and μ = Eanaaa [s])]
Another consequence of Lemma 2 in providing bounds for the value and Q functions. In the ergodic case, it is known that the functions V and Q are Otmiix). In the unichain case, using the above result, we show that these functions are still bounded, by ((C) instead. The proof these results are given in Appendix C We next describe the error analysis of the critic and NPG subroutines in Algorithm|] !
Challenges due to transient states: We observe that the critic and NPG updates can be interpreted as stochastic linear updates with Markovian noise. From the preceding lemmas, follows that the bias and variance of the noise in these averaged update directions can be made sufficiently small. Nevertheless, the analysis still presents certain challenges.
We show that the kernel of the critic matrix A, (0) can change depending on the policy. More specifically, the kernel will depend the set of transient states (see Lemma 13]. This is unlike in the ergodic case, where the kernel remains the same for all policies. As a result, strict positive
definiteness of the critic matrix cannot, in general, be ensured by using carefully selected set of feature vectors.
Although prior work in the ergodic case has considered the case where the critic matrix is singular [4]. our approach differs significantly, in addition to incorporating the sample averaging analysis regret guarantees require sharp bias bound for the critic updates. [[[c]] 5" []. in addition to the standard second-order error bound [[ [?]
discussed in the previous section. In particular,
The analysis in [4 only addresses the second-order error. Furthermore, to establish our convergence guarantees, we require the following condition:
ker(A,(0) (e,
(35)
holds in the ergodic case, even if the critic matrix is singular, but generally does not hold unichain settings (see Appendix D However, it satisfied when the Markov chain is restricted to its recurrent class. To address this, we show that, with high probability, the chain induced by Te, enters the recurrent class, Sht very early, allowing to focus the recurrent class.
Equation 335
More specifically, recall that in each outer iteration k. Algorithm Daaiimm@eeee collects contiguous segment of 2BH samples under To,- We define the event E = (To, S B). where To, is the first hitting time of 5h for this segment. Lemma 10 shows that Pr((E)) ) s 2 [n/2Cia which implies that the chain reaches the recurrent class within the first steps with overwhelmingly high probability. We perform analysis conditioned this event.
Let Eg 1==1 Ed-- We decompose the expected regret based whether Eg holds:
E [[egg]] = E[Regy|Ent Pr(En) + E[Regr|Eg] Pr(Eg).
Since the instantaneous regret at most 1, the total regret is bounded above by T. and applying union bound over K yields
E[Reg]] < E[[egr Ep] TK2 [1/2Can)

---

This decomposition allows us to isolate the high-preg probbabbyyy event Eg, under which all policies quickly enter their recurrent classes. By choosing B vT, the second term becomes negligible for large T, and we may therefore restrict our analysis to the case where εB holds.
Analysis under event E By standard Markov chain theory, Tp is a stopping time hence, the Strong Markov Property (Theorem 1.2.5 of (27]) applies at Tg. In particular, conditioned sT, the post-Té trajectory is independent of the pre-Ta path and evolves as a Markov chain initialized at sT under the original kernel pms As a result, suffices analyze the critic and NPG subroutines with the samples restricted to the irreducible class. In Appendix D we analyze a generic stochastic linear recursion and show that these subroutines can be viewed as special cases of this recursion.
Theorem 2. Consider Algorithm 7 E,, the critic estimate &n satisfies
under the ussumptions of Theorem 7
Conditioned the event
B [[]T((E [2)1191En] s 5 c- - --11
Crar C m X
and
C [1(B)( e 10
e-ciH11Es
A 16 52 = [A.(0.)) (0,) = [nt <t] and denotes the projection onto the space b.
where C1
ker( (er(AA(()))
The details regarding the verification of all conditions of the generic linear recursion used in Theorem for the critic update is provided in Appendix E
Theorem 3. Consider Algorithm 7
under the assumptions of Theorem 7 ε. the NPG estimate wb satisfies
Conditioned on the event
E [[lax - w [1 00
(c-22 - w
Ca BBB
G ET 1
G capp
1
and
|| [[[][[B]] -ill s O
dGf (- wtll2
tar
G GT
-
Gpe
n
where 4(1+
Similar to the critic update, the details regarding the verification of all conditions of the generic linear recursion used in Theorem for the NPG update is provided Appendix
Conclusion
We have presented NAC-B, Natural Actor-Crite algorithm with batching, that achieves Ö(VT) regret in infinite-horizon average-reward MDPs under the unichain assumption. Unlike prior work that relies stronger ergodicity conditions, NAC-B operates under weaker structural assumption that allows for both transient states and periodic behavior, thereby broadening the applicability of policy gradient methods in average-reward settings. Our approach leverages function approximation for scalability and introduces batching to mitigate issues arising from periodicity and high variance in gradient estimates. Future works include extending this analysis to other settings such constrained MDPs g [22, neural critics [15] and relaxing the unichain assumption, though we anticipate this to be challenging task (See Remark
References
[1] A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan. Optimality and approximation with policy gradient methods markov decision processes. In Conference on Learning Theory, pages 64-66, 2020.
10

---

[2] A. Agarwal. S. M. Kakade, J. D. Lee, and G. Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. The Journal of Machine Learning Research, 22(1):4431
2021.
[3] P. Agrawal and S. Agrawal. Optimistic q-leamnng for average reward and episodic reinforcement learning. arXiv preprini 1rXiv:2407.137433 2024.
[4] S. Agrawal and R. Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. Advances in Neural Information Processing Systems, 30, 2017.
[5] A. O. Al-Abbasi, A. Ghosh, and V. Aggarwal. Deeppool: Distributed model-free freee algorithm for ride-sharing using deep reinforcement learning. IEEE Transactions on Intelligent Transportation
Systems, 20(12):477 1): 2019.
[6] D. Aldous and J. A. Fill. Reversible Markov Chains and Random Walks Graphs. 2002. URL
https://www stat. berkeley.edu/ aed/ealdousuaussssa.aaaaaa RWG/book. .ttml
[7] Auer, T. Jaksch, and R. Ortner. Near-optimal regret bounds for reinforcement learning. In
D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, Advances in Neural Information Processing Systems, volume 21, 2008.
[8] Q Bai, W. Mondal, and V. Aggarwal. Learning general parameterized policies for infinite horizon average reward constrained mdps via primal-dual policy gradient algorithm. Advances in Neural Information Processing Systems, 37: 17:106666-188599 2024.
[9] Q Bai, W. U. Mondal, and V. Aggarwal. Regret analysis of policy gradient algorithm for infinite horizon average reward markov decision processes. In AAAI Conference on Artificial Intelligence, 2024.
[10] R. Bhatia. Matrix Analysis, volume 169 of Graduate Texts in Mathematics. Springer- Verlag, New York, 1997.
[11] C.-L. Chen, H. Zhou, J. Chen, M. Pedramfar, T. Lan, Z. Zhu, C. Zhou, P. Mauri Ruiz, N. Kumar, H. Dong, and V. Aggarwal. Leamnin-basse two-tiered online optimization of region-wide datacenter resource allocation. IEEE Transactions on Network and Service Management, 22(1): 572-581, 2025.
[12] X. Chen and L. Zhao. Finite-time analysis of timesali actor-critic. In shirth Conference on Neural Information Processing Systems, 2023.
[13] Y. Ding, Zhang, and J. Lavaci. On the global optimum convergence of momentum-basee policy gradient. In International Conference on Artificial Intelligence and Statistics, pages 1910-1934, 2022.
[14] I. Fatkhullin, A. Barakat, A. Kireeva, and N. He. Stochastic policy gradient methods: Improved sample complexity for fisher-nonddee non-degenerate policies. In International Conference on Machine Learning, pages 9827-9869, 2023.
[15] S. Ganesh, J. Chen, W. U. Mondal, and V. Aggarwal. Order-optimal global convergence for actor-critic with general policy and neural critic parametrization. In The 4 4sst Conference on Uncertainty in Artificial Intelligence, 2025.
[16] S. Ganesh, W. U. Mondal, and V. Aggarwal. Order-optimal global convergence for average reward reinforcement learning via actor-critic approach. In The 42nd International Conference on Machine Learning (ICML), 2025.
[17] S. Ganesh, W. U. Mondal, and Aggarwal. Order-optimal regret with novel policy gradient approaches in infinite horizon average reward MDPs. In The 28th International Conference on Artificial Intelligence and Statistics, 2025.
[18) N. Geng, T. Lan, V. Aggarwal, Y. Yang, and M. Xu. A multi-agent reinforcement learning perspective on distributed traffic engineering. In 2020 IEEE 28th International Conference on Network Protocols (ICNP), pages 1-11. IEEE, 2020.
[19] G. H. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins University Press, Baltimore, MD, edition, 2013.
[20] K. Hong and A. Tewari. A computationally efficient algorithm for infinite-horizon average- reward linear MDPs. In Forty-second International Conference on Machine Learning, 2025.
[21] Jaksch, R. Ortner, and P. Auer. Near-optimal regret bounds for reinforcement learning. The Journal of Machine Learning Research, 11:1563-1600, 2010.

---

[22] D. A. Levin and Y. Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
[23] Li, Wu, and G. Lan. Stochastic first-order methods for average-reward markov decision processes. Mathematics of Operations Research, 0(0), 2024. doi: 10.1287/moo:.2223.12.. To appear.
[24] Y. Liu, K. Zhang, T. Basar, and W. Yin. An improved analysis of (variance-reducee)) policy gradient and natural policy gradient methods. Advances in Neural Information Processing Systems, 33:7624-7636, 2020.
[25] S. Masiha, S. Salehkaleybar, N. He, N. Kiyavash, and P. Thiran. Stochastic second-order meth- ods provably beat sgd for gradient-dominater functions, arXiv preprint 128.:: 2022.
[26] W. U. Mondal and 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, pages 3097-3105, 2024.
[27] J. Norris. Markov Chains. Cambridge University Press, 1998.
[28] P. Panda and S. Bhatmagar. Two-timescale critic-actor for average reward mdps with function approximation. In Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI), 2025.
[29] B. Patel, W. A. Suttle, A. Koppel, V. Aggarwal, B. M. Sadler, A. S. Bedi, and D. Manocha. Global optimality without mixing time oracles in average-reward rl via multi-level actor-critic. In International Conference on Machine Learning, 2024.
[30] M. L. Puterman. Markov decision processes: Wiley & Sons, 2014.
discrete stochastic dynamic programming. John
[31] G. O. Roberts and J. S. Rosenthal. Shift-coupling and convergence rates of ergodic av- erages. Communications Statistics. Stochastic Models, 13(1):147-165, 1997. doi: 10. 10.1880/15326344708877777777
[32] W. A. Suttle, A. Bedi, B. Patel, B. M. Sadler, A. Koppel, and D. Manocha. Beyond exponentially fast mixing in average-reward reinforcement learning via multi-level monte carlo actor-critic. In International Conference on Machine Learning, pages 33240-3320 2023.
[33] R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour. Policy gradient methods for reinforce- ment learning with function approximation. Advances neural information processing systems, 12, 1999.
[34] J. Tsitsiklis and B. Van Roy. An analysis of temporal-differeen learning with function approxi- mation. JEEE Transactions on Automatic Control, (76)))6776660 1997. doi: 10.
[35] Wang, M. Wang, and L. Yang. Near sample-optimal reduction-basee policy learning for average reward mdp. arXiv preprint arXiv:22
2022.
[36] L. Wang, Q Cai, Z. Yang, and Z. Wang. Neural policy gradient methods: Global optimality and rates of convergence. In International Conference on Learning Representations, 2019.
[37] Y. Wang, Y. Wang, Y. Zhou, and S. Zou. Non-asymptotic analysis for single-loop (natural) actor-critic with compatible function approximation. In International Conference on Machine Learning, 2024.
[38] C.-Y. Wei, M. J. Jahromi, H. Luo, H. Sharma, and R. Jain. Model-free reinforcement learning average-reward markov decision processes. In International conference on machine learning, pages 10170- (0170-10180 10180, 2020.
in
[39] C.-Y. Wei, M. J. Jahromi, H. Luo, and R. Jain. Learning infinite-horizon werage-reward mdps with linear function approximation. In International Conference on Artificial Intelligence and Statistics, pages 3007-3015, 2021.
[40] P. Xu, F. Gao, and Q. Gu. Sample efficient policy gradient methods with recursive variance reduction. In International Conference on Learning Representations, 2019.
[41] Xu, F. Gao, and Q Gu. An improved convergence analysis of stochastic variance-reduced policy gradient. In Uncertainty in Artificial Intelligence, pages 541-551, 2020.
12

---

[42] Y. Xu, S. Ganesh, W. U. Mondal, Q. Bai, and V. Aggarwal. Global convergence for average re- ward constrained mdps with primal-dual actor critic algorithm. Advances Neural Information Processing Systems, 2025.
[43] R. Yuan, R. M. Gower, and A. Lazaric. A general sample complexity analysis of vanilla policy gradient. In Proceedings of The 25th International Conference Artificial Intelligence and Statistics, volume 151, pages 3332-3380, 2022.
[44] S. Zhang, Z. Zhang, and S. T. Maguluri. Finite sample analysis average-reward td learning and q-learning. In Advances in Neural Information Processing Systems, volume 34, pages 1230-1242, 2021.
[45] 7. Zhang and Q. Xie. Sharper model-free reinforcement learning for average-reward markov decision processes. In Proceedings of Thirrty Sixth Conference on Learning Theory, volume
195, pages 5476-5477, 12-15 Jul 2023.
[46] M. Zurek and Y. Chen. Span-based optimal sample complexity for weakly communicating and general average reward MDPs. In The ehirty- Annual Conference on Neural Information Processing Systems, 2024.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims are demonstrated in the key results (mainly in Section 4.2 which match the description in the abstract and introduction.
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: The assumptions given in the paper give the limitations of this work. Further, future work direction in the conclusions describe another limitation of this work.
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 sell-speciiiatiinn 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?
14

---

Answer: [Yes]
Justification: We have provided the assumptions used the work in Section 4.1 or referenced in the theorem statements. All claims are backed with complete proofs in the Appendix. Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' 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 encouraged 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
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: The experimental results are not provided, since the focus of the paper is on theoretical sample complexity analysis.
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 novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either 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 reprodueibility may be tricky in some cases, in which authors are welcome to 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 be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
15

---

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 requiring code.
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 to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /tte:///uuddde/oooSuuubbmiibia 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: Our work is theoretical, and hence there are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: 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.)
16

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state 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 eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU 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 as 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 http://pp..aaoass....//pp//////a
Answer: [Yes]
Justification: All the points mentioned in the NeurlPS Code Ethics are taken into consid- eration.
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 a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in 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 are no specific societal impacts of this work beyond that the algorithms may have impact in the reinforcement learning algorithms in different applications.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

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: There is no release of data models.
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: There is code, data, models, etc. involved.
Guidelines:
The answer NA means that the paper does not 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.
18

---

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:
There is no code, data, models, etc. involved in the paper.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/coddemmodel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create 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 participants and screenshots, if applicable, as well as 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 involve crowdsourcing 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 Bthies, 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 neither involve crowd-sourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending 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, not include any information that would break anonymity (if applicable), such the institution conducting the review.
19

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification:
We do not use LLM in our paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy hattaa/:/eaaarrsssec////oeeeeere for what should or should not be described.
20

---

A Discussion on the Discounted to Average Method
We note that while there are several sample complexity analyses for discounted policy gradient methods, most treat the term (1 - -- as a constant. As result, most results exhibit an overly pessimistic dependence on this factor, since it is not the main focus of these works. However, achieving an optimal dependence on (1 7) is essential to obtain optimal regret or convergence guarantees when using the discounted-to- tov-eeaee reduction. This reduction is particularly sensitive to the (1 - ->)- factor.
We now compare the sample complexity, closely related notion regret, of existing policy gradient algorithms when applied to the average-reward MDP (AMDP) setting. We focus on sample complexity since it aligns with the typical form of guarantees in the discounted setting and facilitates direct comparison. To translate results from the discounted MDP (DMDP) to the AMDP setting, we use Theorem 1 from [35], which was also employed in [46] to establish optimal sample complexity for average-reward MDPs under generative model. This reduction bound shows that if the DMDP with discount factor y is solved to an accuracy of e, - ((1 - 7) -te), the resulting policy will be of (c) accuracy in the original AMDP.
Table 2 summarizes the sample complexity bounds for discounted policy gradient methods. The best guarantee among these is (ce-)), which remains significantly worse than the optimal O(+-²) rate. This is akin to a regret bound of order O(T4/5). Although some actor-critic methods, such as that of 41, offer improved sample complexity guarantees in terms of (1 -) they assume ergodicity even in the discounted setting and are therefore not considered.
Table Overview global optimality convergence for discounted PG algorithms. DMDP Sample ++ /Ebias
Complexity: Number of samples to achieve J E (0r) S
AMDP Sample Complexity:
Number of samples to achieve J E ((T)) S V
Algorithm
DMDP Sample Complexity
AMDP Sample Complexity
Vanilla-PG [3
(1 -
Natural-PG 24
[1 ?) -2
SRVR-PG 24
(1 (1- -2.5g g-
5.5
STORM-PG [13]
(1 7) v
E
SCRN [25]
(1 7) 5
e-
N-PG-IGT [4]
(1 7) 3 20
e 7.u
(N)-HARPG [4]
7) -2--
e 6
ANPG [26
7) 4
E
B Policy Gradient Theorem
Lemma 4 (Policy Gradient theorem, (31) Let Assumption Toold and assume differentiable policy paraneterization. Then, the following holds for all parameters 0 E e.
VJ(I)= = -(a.a)=nt (s, mog
(36)
Proof of Lemma
We begin by noting that
VTa (s) = Σ (s..)))
(37)
By differentiating both sides of the above equation with respect to 8, we obtain
VV Σ V=o(als)(** (s(
(38)
Recall that
(= = r(s,a) + Σ P(s ((s J(B)
(39)
21

---

In similar manner to 38 gives
taking the derivative of both sides of the above equation with respect to
(s,)a E (()
(40)
Substituting (40) in 38
yields
-
VV (6)
V T A [a] (t) (s) (a(as)
(41)
Re- Re-arranging the above equation, we arrive at the following expression for VJ((O)
VJ(0) Σ (s) + Σ To(alss (ll - (s)
(42)
Taking expectation
a on both sides, obtain
VJ(0)= = Σ d (To(dlss) + Σ Em000maappp(lsss////0//
(43)
Σ dm (s)
Since E, (s) PT (s, d=a (s'), , we arrive at the following expression.
J((0) Σ (d (=Vooaaaas))))"
(44)
C General Properties of Unichain Markov Decision Processes
In this section, we provide detailed proofs of Lemmas and 3 from the main paper, along with bounds on the value functions (Lemma) 7 and show that the hitting time of the recurrent class remains bounded by B with a high-probability (Lemma We begin with a few useful preliminary results. Lemma (Strong Markov Property. Theorem 1.2.5 of (271). Let {8t be discrete-time Markov chain on a countable state space with transition kernel P. If is a (possibly infinite) stopping time, then for all E S and any bounded measurable, function
E [(((s++))
Frl E [f(ss)
sT]
a.s. on {T' [c), for all 2 0.
The following intermediate result provides a bound on the convergence rate of the empirical state distribution the stationary distribution when restricted to the recurrent class.
Lemma 6. Let Assumption hold and consider any E Q. Then, the following bound holds:
Ctar
( - d=e(.)
I
Vsg E Sh.
(45)
TV
Proof. Since 5% is closed and communicating, the Markov chain restricted to S.. remains a Markov chain and is. in fact, irreducible. The result then follows from Corollary 3 of [31), which applies to (possibly periodic) irreducible Markov chains.
C.1 Proof of Lemma
Note that
Σ pxo (p00)
p (mo d=)
TV
Σ (pto)i(s0))) -
(46)
27
22

---

Thus, it suffices to show that the quantity
(((PToP(so:))) d=
bounded by C, for all 2 1. Note that this term can be broken down in the following manner.
P ( ( -d
(Pno) (100) ds)
sES
( (s0:) - (s)
Σ (sto) xE(S))
Σ
(47)
SESA nt
T3
where (a) follows since d=d (+) for all E (. Let E denote expectation over the Markov chain generated from ma starting from state 8p- Consider term T2 and observe that
Σ *E(S)) J
Σ
p (600)
E 80
Σ
Σ
1(8 = 8)
E Σ 1((s E (s21
(48)
1=1
(S)))
E
[min (t, To 1HI < Eo, [To] S Chit.
We adopt the convention that the sum Σx= 8; is defined be zero whenever j > regardless of the values of the summands 8.. The term T2 can be bounded as follows.
Σ
(PPT)'
(s) = Σ
Σ [1(: = =) d (s)
SESt 1=1
SES
1=1
< Eg
ETg
Σ [[s: =) d (s)]
TT-1
$ Eg
ET
Σ
[ss = 5) - dd
Σ #ES,
Erg
Σ Li
[1ss = 5) - d (s)]
LES
where Ey,, denotes the conditional expectation given the hitting time To. and Eg denotes the expecta- tion over the random variable Tg. Finally, consider term T3
To-1
To
Ep
ET
I = () s) (s)
d= - -
(s))
Ea
Σ ET
Σ d (s)
Eo[To] s Chits
SES
LESA
where (a) follows since, by definition, no state
S is visited before To. Ta be bounded
T-T611
Eg
Σ
ET,
E11(s = 5) d (s)
(a) Eg
((Ts))))))))))))) -d d= (dd
SESE
L==T
2Ctar:
where (a) follows from the Strong Markov property and (b) follows from the fact that sT, E S and using Lemma 6 Combining the bounds on Ti, T2, Tg. and Ta gives
( d= d=)(
S 2(Crar + Cha),
(49)
which yields the desired result using (46)
23

---

C.2
Value function bounds
Recall that the value function V and the action-valle function Q are not uniquely defined for average-reward infinite-horizz MDPs, even in the ergodic case. We therefore consider V such that
Σ L (s) O.
(50)
Under this condition, vao and Q (8, a) are given by
V lim
E8g
(r(se, az) J(0)) =
(51)
N
T
(8, lim N00
Σ (r(se, [(0)) 80 = 8, 0g
N
T=1
where [g[-] denotes expectation with respect to trajectories generated by the policy m0- These definitions employ the Cesàro limit to account for potential periodicity, which was absent in the ergodic case.
An equivalent expression V*8 (8)
V**(s)
N
1
(s)
lim +000
-s.-) 70
(52)
N
[==
We now provide bounds for V Q", and the advantage function A =Q- - V under the condition in (50)
Lemma 7. For all 0 E O and (8,a) a) E S x A. the following bounds hold:
(i) TH (s) s 2(hhi + Crar)
(ii) QT (s, a) $ (1 + 2(Cnit + Ctar))
(iii) AT (s, a) < (1 + 4(Chit + Crar))
Proof. Using Hölder's inequality and the bound on the reward function, we obtain the following
T
Σ (1,T))()))) -d r
d=a1]
< > ((P (t
d'u
|| 1o0 S
Σ (p d=u
Combining the above bound with 49 concludes (t). Parts (ii) and (iit) now follow easily, since both r(s, a) and, consequently, J are confined to the interval [0, 1]. which gives
(s, r(s,a) J + E E (V=e (8') S (1 2(Chin + Ctar))
(53)
and
(T (s) (s) S (1 4(Chi + Crar)).
(54)
C.3 Proof of Lemma 3
For clarity and ease reference, we re-state and prove parts (i) and (ii) of Lemma 3 separately, We also provide sharper bound for the case where the Markov chain is restricted to the irreducible class. Lemma (Bias of Markovian Sample Average). Let Assumption hold, and let f S -+ Rd satisfy [s) < C5 for all E S. some constant Cg O. Then, the following bound holds:
B
Vac,c B
E
f(:)
B
t=1
24

---

where E denotes the expectation of the Markov chain {si} induced by starting from any E S
and J = R [+)] Furthermore, if $1
E Stt then
B
vdC,Ctar
E
(8)))
B
B
Proof. Let fj: 8 R denote the jth co-ordinate of f. i.e. (()) = [81(8), 126)) [a()))
We
express the j co-ordinate of E
B Di
i=
(s::)
E
B
1
f5(:t)
E
Σ (s))
=
Pd
(55)
B
Similarly, My can be written as
Mi Bgnd [f}{{] (d
(d J3-
(56)
Then, by using Hölder's 's inequality for each j
Expo
E
B
19
P
B
P
(d
11,s
(0)
S
C7
(57)
where (a) follows from Lemma
2
If St. then Lemma 6 can be applied instead, replacing C
with Otar- The result then follows by noting that
B
B - Hí
2
Bsrap
Σ
f(si)
Egg mp
Σ 1=1
fs(s)
(58)
B
B
1=1
Lemma 9 (Variance of Markovian Sample Average). Let Assumption hold, and let f S + Rdd
satisfy [s) I Cj for all E for some constant Cj 0. Then, the following bounds hold:
9 -3+ 2V023C
1 B
E
B
where E denotes the expectation of the Markov chain {si} induced by starting from any E S and μ = Ex [s)]]. Furthermore, if $1 E S.p. then
B
2
O² + 22d07
(88)
<
B 1=1
B
Observe that
2
Var
1(s))
f(s))
E
f (s:: -1
B
B
DB 1
E (8:) 1112 + ΣΣ i=
Σ
- - 11)
B²
B
(sss) 111 2 B
- 11 B(f(ss)
E.
(f(s,) n]])
i=1
B2
E E
(f()s)) 211 +2 8
1 E
Elff(s:)
H E, E (f((s) P)ll
B2
EB
E (l((s))) 1 + + ytar
E ( - -
B²
O + +2+2VCC30
B
(59)
25

---

where E, denotes the conditional expectation given and (a) follows from Lemma then C' can be replaced by Ctar-
s1 E Sk.
C.4 Bound on the Hitting time of the Recurrent Class
Lemma 10. Let Assumption 7 hold, and let {8ele2o be the state sequence induced by policy zs- Then, for any B 2 1, the probability of hitting Sh within B steps satisfies
Pr(To B) 2- LB/20ma]
Proof. By Markov's s inequality,
T 1
Pr(To > 20hit)
2Chic
2
so Pr(To= & 2Chit) 2 1
[B/2Chir disjoint intervals length 2Chis By the Markov property and the uniform bound the expected hitting time, the probability of not hitting Sk each interval is at most 2, regardless of the starting state. Therefore,
Now partition the time horizon [0, B] into :=
Pr(To > B)
1 2
2 .3/20mal.
Taking the complement gives the desired bound:
Pr(To s B) 2- 2-1-211B/-0 LB/2Cmm]]
D Analysis of a General Linear Recursion
Recall that the Critic and NPG subroutines in the algorithm can be viewed as instances of stochastic linear recursions. To analyze their behavior in unified framework, we consider a general stochastic linear recursion that captures the essential structure of both subroutines. This approach allows us to derive bounds that apply to each case as special instance. Specifically, we study the recursion form:
1h+1 24 - -(Pr - Tn..
(60)
where Pr, and qh are noisy estimates of P Rax and q IR", respectively, and h {o...., Assume that the following bounds hold for all h:
..., H -
(A1)
EA | p|6]
s oz.
(A2)
EA Ph
P1 - 82.
(As)
EN [|@. a||
- 20 (A4)
En [m - al $ 5²-
and
(As) E 9 g|l
<
82
Here, E, denotes the conditional expectation given the history up to step h. Since Elgal E[E,, we have 02 < 52. Additionally, assume:
(Aa) | (Ar) |lall S Ag:
and
(As) x Px > /2 (Ag) ker(P) C ker(Ph)
for all x E k and 2 1. Let x- = pig. where pt is the Moore Penrose pseudoinverse of P and II denote the projection operator onto the space kcr(P) i.e., the orthogonal complement the kernel (null space) of P.
While a general linear analysis was conducted 16), our approach differs significantly due to fact that the critic matrix is not strictly positive definite. This necessitates the additional condition (Ag), which was not required in the ergodic setting. Despite the lack of strict positive definiteness, still achieve the same convergence rate.
26

---

Theorem 4. Consider the recursion (60) and suppose (A1) (Ag) hold. Further, let óp S Xp/8
and B Ap Then, the following bounds hold for all H 2 1: Ap
(a) [ - x1)] 5o exp (-
HA IAg -A,
Rg
+ opp 2 A
+ 6ppp tp +2p202
and
(b) [[[[[[+ - x²)112 50
exp
(-IA,
HX IA,
Rg
5p RO²P 8213Ap"
+ t0xpp?
where Ro = ||][(20 - xx)ll
D.1 Proof of Theorem 4(a)
Before proceeding, provide some useful results with their proofs.
Lemma 11. Consider a matrix A such that x² Ar 2 A | for all æ E (ker(A))* Then, we have
1
||A S X
Proof. It is known that the operator norm of A is ||| 1/ar, where 0, is the smallest nonzero singular value of A (see Theorem 5.5.1 in [19]
Note that x Ax x_ TAA A x. which in turn implies x T Ax = (1/2)x² (A + A Aax.. The condition xT Ax 2 1||=||2 implies that x (A+AT), 2 \||=||² for all (kke(())= Since (A+AT) is
symmetric matrix, this implies that all non-zero eigenvalues of (A+AT) are bounded below by Now using Prop. 111.5.1 in (10), it follows that 2 À which concludes the proof.
2
Lemma 12. Let 11 denote the projection operator onto the space ker(P)t, i.e., the orthogonal complement of the kernel (null space) of P. Then the following properties hold:
(i) II 11
(ii) If P is such that ker(P) C kPr(P), then PII P.
Proof. The first property holds since II is a projection operator onto linear subspace. Such operators are both symmetric and idempotent, which implies II and II2 II, hence II
For the second property, let II' denote the projection operator onto ker(P). By the orthogonal decomposition of the space, we have
11 1I = I, where 7 is the identity operator. For any x, it follows that
P P(Ix + II ===== PIIx,
where the last equality holds since H ker P) C ker(P) and thus PII+x 0. This establishes the result.
Coming back the proof, consider 60 and apply the projection operator II to both sides. Using the linearity of II, we obtain the following:
II - x²) =
Tb - x= 3(PrIr am))
II (Tp x² 3(Pxn - + M1+1))
(61)
II (Ih x² -pP(xn - -x)) + (,Mx+1)
I[(x x²) SIIP(EA -x") - -BI
27

---

where Mh+1 = (Pa-P)aN - - -)--
Taking the square on both sides of the above equation and then taking expectation we obtain
E [Ix+1 - =²=
E [[[(ar) - -x") --IIP(22 =x") BILM 1+11
E [[( xx*) 3T (2ra xx 311 11 + B E
(62)
+ 2 [((I - xx") BIIP( - x²), 311M++1
T3
We now analyze term 7i
E [[T x²) - 311 x²1
= E || - x "12 (T x² [1 - + [1 x² x²)
E [||TT(an - x ")12 23( - xx) ITP - =²) 8 TTP (ar x x²)11
(4) IE [|[T(>>> - x²) =² 23(Tn x²)T IT PIT Thh x²) 3 (TT - =-
(63)
= E [I - x² 2²1 23(TT( - x) (( - x²))
ITP - x²)
(6) (1 (1-Ap3 A)) ) E |11( -x²)11
where (a) follows from (Aa) and Lemma I2 (b) follows from (As) and (As). Now, consider
term T3
[II - x²) (m x²), 3I1MM11)
-[(II x²) -11P(a x²) x²), [1IMa++1e
(64)
(a) 3Ap [1I - =²) 31IP a =1)
23
Ap
where (a) follows from the linearity of II, which allows it to be exchanged with the conditional expectation, and from applying Young's inequality. Adding Ti and Ta gives
E [[
xx) 3II =²) + E(II(ZA x²) -IIP x²) 31LM++1)
3Ap
2/3
1
E [1( -x") 3IIP(I x 111
2
Ap
3Ap
28
(65)
1
1p-3p BBpp) E (1 -x)xx"" 22 +
-
[I
Ap
3dp
B2(2Ap {7)
APAP
28
+
E E|lll< - x x²) +
|
2
2
2
Ap
Consider the term 11 [1 [xn]] in the above sum.
TE[MA+1Ia) [ P,,- P) (Th. 2)(2)))
= [E,, P)] 10n [E - -0
I1 E((; P))xn] (Ira xx)=xx)) IT TE P)) I 9) [r
- IE [E, - 2 [[( - x²) + [E - - mn|
where (a) follows from (Ag) and Lemmal 12 Using the above bound, we obtain the following using triangle inequality
E [II M [x]]
< 3 3 - ())[=)][[( x' M1 + 3 E (E P)
+
1)12
<3E (P, >)]==]11 | 2' + [(PP, P)]xx]1?||=*1]
+ [|ll E ( -|]11
(0)
< 35%, E ||| x') + 382
28

---

where, (a) follows from (A2) and (A1). Similarly, we analyze the term T2 below.
82 E 11M 1l1
S F E. MM+111
B E [P - p)zy- (Th 9)l
3d E [P(p, P)II(Zn - x²) (Pr, P)II=* -(hh- - -
(66)
3,3a (B P1| pm [1 x= |[ + E Pr 11121100 E 11 all²)
- 33 BII - x' >I + + 3
where (a) follows from (A1) and (As). Combining bounds obtained for Tı, T2 and T3 with 662). we
obtain the following bound.
E [[T (1h+1 x²
1 3(Ap 1202A2
1262App)
P(303 + 2Ap X2)
A
E [|[[22
x")1? (67)
2
2
2
+ 33 "pp0"ppp>> N3 + +33 0/ + 6385AAp" 66
Suppose 1263, S X and small enough such that B < 1 and 3 S Then, the above bound gives us
dp
-
E [ x²)l (1 (1- 3Ap E 11(AA - teh En.
(68)
where
c = 33 33=3oo +3300g + 6383AA 63A
(69)
Unrolling the recursion yields
E [[] =x))|| s (1
BAp
H-h+1
E [IT x²1 +
(70)
h=1
HBAP
S exp
E [|] - =1')11 +
(71)
3BP
Setting 3 = Ag in the above equation yields the final result.
Ap
D.2 Proof of Theorem 4(b)
We analyze the squared bias term [[][E[[)]] - x =1 where vy denotes the iterate at step h, x" is the optimal solution, and II is a projection operator. Recall that the update rule for 2h+1 is can be written as:
2/ 3P(zk x²) + 3M++1.
#h+1
Taking expectation and applying the projection operator on both sides, we obtain: [[E[==+1] - x" x1 = [B[[AT - x"' Par xx) + 3M++ 1112.
Expanding the norm using the properties of inner products yields:
[T( - x²) 12 = [ - x²) PP(m x =]]] + 3 M 2 TTE ( - x²) 3P(xn M1
(72)
Using Young's 's inequality, we bound the cross-term as follows:
3AP
IIE x²) - -BP(x x²)], BIE <
|I x²) 3P(xn x"]]11
2,
[1
Ap
29

---

Substituting this bound back, we find
BAP)
Ap (xx 8r)
23
x _ [1+ 2
x I|1
| .1I
Next, we analyze the term |[TE| we have
x²) - 3P x²) |11?. Using the linearity of expectation,
IT x²) - 3a x" "]]] [[T(([([)) -²)> (TP(((())))) xx "11
Expanding this norm
[I[[E[>]] - x²) -3P(B(x =x)]1² | - (B)))( - x=" 2²2
-28(II(E - x²) PI( x²)).
Since [1(E[[a]- xx) E ker(P)= we can use Ag and As to obtain
[E[pa]]] x²) 3P(E[r)] - x²) I| - (1 - pBp + 8 [I - -r))l
Finally, we bound the noise term ITE M 1||2. Using the conditional expectation property, we expand
II = | [rA]l1
Decomposing M
into its components
Mh+1 = (Pr, () - x²) + (Pr - P)x* + (Th - -q)
we bound each term separately. Using A2 and As. we find
[| I]l? <. 36 307.A3.2.5 38,
where R2 = - x - [[
Combining all results, the squared bias term satisfies the recurrence:
3Ap
[[[[[2++1) x²) s +
(1 - (1-BAp + 3AAp [[(E[(N)] x²)11 + En.
32p +
p²(2Ap - XXp)
3'Apde)
[T[(E(r)] - x1)11 En
2
2
where
2,3
+ 32
(352 R3 + 357 + +30%))
Ap
Suppose 3 is such that 3 < 12Ap)-1 Then, the above bound gives
[[[[<<++1] - 2²) [
3Ap
[[[[[=]] x²)) x²1|1 Eい
(73)
Unrolling this recursion over steps, we obtain:
31p) H - -x0)==+++++ En
[ - >² -
(74)
4
BAP
Setting
Ae in the above equation yields the final result. Ar
E
Proof of Theorem 2
Recall the definition of Zp
Zo = fz ( = (x2(() Vi.j E }
(75)
We now state and prove few useful results for the critic analysis. Recall that Me = Eg (ss) (Ø(s) o(s')) constitutes submatrix of the critic matrix A.)) We begin by charac- terizing the kernel of Mg in Lemma B
30

---

Lemma 13. Let Assumption 7 hold, and suppose o is full rank. Then ker (Ma) Zo.
Proof. Let f S + R be arbitrary function. Consider the quantity
E [(f(s) - {()))²
where the expectation is over 8 t and s' ~ (. }) is the next state under the transition kernel induced by policy Te. This expression captures the expected squared one-step difference in the values of along the Markov chain.
It is known that if the chain is irreducible and f is non non-constant, then Esnar ((f(s) - f( > 0 34 We extend this result to the setting where the chain induced by No has single recurrent class (possibly with transient states).
Suppose / non-constant this recurrent class. Then, we claim that By (((s))(())))))) 0. It suffices to show that there exist states s, s' within the recurrent class such that (s. 0 and f(s) # f(s'). Suppose, for the sake of contradiction, that no such pair exists. Then, the recurrent class could be partitioned into disjoint subsets, each corresponding to distinct constant value of f. with no transitions between subsets. This, however, contradicts the fact that the recurrent class is closed and all states within it communicating. Hence, such pair (s.s') must exist, which implies that the expected squared difference is strictly positive since
E [(f($) f((')) 2 d= (s) (F8 (s, s')((s)) - f(s)))² > O.
(76)
Separately, note that E [(f(s) - f(5))) can also be written as follows
E [(f(s)
- f(s')) Es -f(s))((ss(()))) f(s')
(77)
2 2E (f()) -f(=)()))))(()))) f(s')))
where (a) follows since Ejes d (s) PT) (s, Exwdd [[{=]((s) - [+=](> = Maz, which concludes the proof.
(s') Taking f d2 it follows that
The following result provides a lower bound on _ A.(()ç using Assumption 2
Lemma 14. For large enough c3. Assumption implies that & Ao) (A/2)]l<11 for all = [= such that Ç kee(MM)) " all 0 O.
Proof of Lemma 74 Recall that (0) Eo[A, (z)] where Eg denotes expectation over the distri-
bution of = (s, a, 8') where (s,a) ~ 1 8 ~ P(-|s, a). Hence, for any & [n, {] such that
S E + we have
T Ao)E can2 + t Es [ó(s)] + ST Es [s)) - 0(6'11]s
(0) 2 c In| + 1|/111
(78)
|| min Cgu V /u(1 - w)+ + X(1 m) [u[(0.1)
(6)
2 (A/2) ||E|
where (a) is a consequence of Assumption 2 and the fact that [[((s)] < 1, Vs e S. Finally, (b) is
satisfied when ca > A x 1. This concludes the proof of Lemma 14
Given event εg, it follows that all states visited after the critic update, kh where h 2 1, s E S For s E Stt we have the following result.
Lemma 15. Let s E Sh and s' ~ - (- s) is the next state under the transition kernel induced by policy ny. Then ker (0)) ker (0, 2)), where (8,0,8) s').
Proof. Let ker( (e)(). Then [0, ST where Ç E ker(Ale) Zo. It follows that
31

---

A.(0)= -(671)
By the definition of Zo. have
((s)(((s) -(6))) -0))(((()()))))))))))))))))))))) (66)
since s, s' E S
In particular, (As) and (Ag) for the critic update with h 2 1 follow from Lemmas 14 and 15 respectively. For any 2 = (s,a, s') E S S. we have the following.
(a)
(A, 2)11 1esl -
+ [10(s - =(s'))
& c O(cs),
(79)
(0, < car(s, a) [)({)))((})) c9 1= 0(cp)
(80)
where (a). (b) hold since |r(s, a)l < and ||o())] - 1, v( E E x A. This verifies (As) and
(A7). Using Lemmas and with the above bounds, we obtain
B
\VmcgCus
E
(0, 21)
(o)
0o
(81)
B
B
and
( cg + /mc2 Ctar
E
1
A (8, 21)
50 A.(0)
(82)
B
Similarly,
1
B
(vmcg Ctar
E
60
b.(l)
50
(83)
B
B
and
B
2
C + Vmicz
1
E
by (0, zi)
bb(0)
50
(84)
B
B
1=1
These yield conditions (A1)-(AA) for the critic update, and condition (As) follows by setting 5, 6g Since all conditions (A1)-(Ag) are now verified, we can apply Theorem 4 with the critic learning
A + 1 and B 1a to obtain the following bounds.
rates
CB
'YT E [III - 50 exp (-HA²)
I|5. -E"112
Otarm XB
+ Ctarmm
+ Clam
B2 + C2, m
XB
X2 B2
and
C2 ma 1 12
C2 m B
C2 m B2
[[[[]] - 2²) s
exp (-
Hx3 16
|151
2
X²B²
32

---

Proof of Theorem 3
We note that condition (Ag) holds trivially for the NPG update, since ker (A, {0). Further- condition (As) is readily satisfied with Ap = μ.. Finally, from Assumption 3
more, by Assumption 4
we have
(O, =)]l = V mo ( log (ala))
T S V log (a))))] < G7
(85)
for all
(+, a, 8)) Combining this bound with Lemmas and it follows that
ValaCtar
An(
E
(0, 21)
0o
(86)
B
B
and
B
Gf + vdGa
(0, zi) - Ac(
50
(87)
B
The above bounds yield (As). (Ag) and (A1), respectively. To obtain (AA)), combine the bound on the Advantage function from Lemma 7 with Assumption bound the policy gradient as follows
|[V]( ||AA TM (s, a) V log me(a|s)]] < ||A* (s, a) log me(a|s)] $ (1 4(Chit + G1.
(88)
To prove the other statements, recall the definition of b,, (Ox, Eke :) from 28 Let Eu, denote the expectation over {=:]/ given the entire history prior to (including Ex), Er be denote the expectation given the entire history prior to 21 with 81 d and E., denote the expectation over the entire history prior to 21- Observe the following relations for arbitrary Cx
Er,
by (O,, Sk. 2i) - (o)(Ok)
B
1=1
E,,
r(;; a:) Th + (0($++1) -((s))) Vo logtu, (ails:)
voJ(Ok)
B
B
(a)
Em
lk nh + (6(8)+1) - (b8)), (ki Va Vo logne, (ailss) +
16
B
+ Ex
((o(s)), To (s:)) + (VTen (81+1) 1) Vo logro,
Volorro (aslss)
B
n
B
+
Ey
r(s;, a:) - Th + v (8:) - yooe (Bc41) Vo logno, (arlss) VoJ(Ox)
B
We have T2 = as consequence of the Bellman's equation 6 Whereas,
| 2,,,, ((((s)), (X) 5 (s:)) s 4Greapp
Finally, note that
B
1
To = En
mie - 7h + - Se - (k) Vo log (a:1ss)
B
i=1
B
1
= E.,
mi + (0(8441) ((s;), -s21) Vo Volog (ails;)
B
33

---

which yields
|Toil1 S 02 (llme
1l + |[TT(CR [2)1l
GillTTEE Et)1
(89)
Moreover, from Lemmas g and 9
we have
1
1
VVda
|
Eu,
E
bu (Ok: Sk. 2i)
Eu
bu (Ok: Eks 2i)
50
(90)
B
B
B
1=1
and
1
vdG?
115
11
||
Eu,=
Σ
by
(0x, Ex. 2i)
E,
(Op Ex. 2i)
00
(91)
B
B
B
follows that
B
E
ba (O Eh. 2.) (tt(
VdG9 E TTE Ctar
0
G. E [[T
-1)1 + G9eap
(92)
and
B
En,
by (Ox. ER. 2i)
$ dG E |IIIER
Clar
=ill + Gicapp + G. E [I
(93)
B²
Conditions (As) and (A4) now follow. contrast to the critic analysis, we employ sharper bound for (As), which is necessary to obtain order-optimal regret. We derive this below.
B
bu (Ok, Sk. 2x) 21)
E
(o.(
B
B
E,
E
ba (0 Ek. zi)
VoJ(Ok)
B
i=1
B
E,
[ytel + (0(8++1) ((s)), R.l[Cd] (t) vo Voggo (ailss)
To
En
(1b(s)), (oN -v + TV (8141) (0(8441) Vo Vologn (arlsi)
B
Ti
+ En
1
r(sisa)) Th 2 Vao (si) V ($141) Vo log (ails)) VoJ(Ow).
B
T3
(94)
With the above decomposition, we obtain
B
E
ba (0x, Ex, zi) - voJ(OR)
B
dGt
I. | C2
tar
([
-2) + Gfcapp
(95)
B²
34

---

This concludes the verification of condition (As). Note that the bound involves the term [[[( & rather than [[ <3)ll making it significantly sharper. We can now invoke Theorem by setting the NPG step-size 7 = of to derive bounds on both the second-order error and the bias of the NPG estimate wP, as follows.
E [10x =
S 0
exp [x1H1o)a.)
(-
2n²
1w00 wfll+
VdG
+
[I[EE E + capp
1
VddaCtar
O2
dC1c2
dGiCr
+ + E I| Etll + G7P 2 2
1²B
B²
p²B²²
(a)
0
( eex (- Hy²
(-a1+40TG))
1lwb 1 wfll?
VddfCrar n²B
G2u eepp (- ||5 - 11
Grarmm
GGn Cmar Cmarv + +GHu
Ctarm 1
Caa A2
+ Ghip
+ GGH
+ Gip - Capp
X+B
AB
VaCaCran
dGttc dGACkar p²B²
+ G22 2Eap))
B²B
B²
(96)
where (a) follows using the second-order bound in Theorem and
dG dG
dG tar
dG tar 1²B²²
[[wa]
- 00 exp (
Ha² 4[1+40]6
1|w0 - wtll?
far
BBB2
1²B2
+
G7 2
=2)11 + G2n 2cap
(6)
dGAcl lar B²B
dG tar
dG. far
3 0 exp [
11:0 2 +
+
1. B2
11 B2
|15 12 2 + G2 Caamllss - =
+ G7 2 2exp
H2a (-16) 16
(-
X²B²
+ G2 2 Cla
+ Gip -2 Pla m
X²B² + G2p 2p ((ppp)
B
(97)
where (b) follows using the bias bound in Theorem and
G Proof of Lemma 1
The regret can be decomposed as follows, following the standard approach used in
38 9
Reg,
(J - a())
1=
HBB
Σ -J=-)(Wm) +
(J(O+) r(se, ai)
ET
K
= HB
- + E
x (SK#) V (*KH)
+ E [V Tox (ST)
V (so)
(98)
35

---

Since 0 $ (*()) I 2C' for all π E II and s S from Lemma 7 it follows that
B[Regr] & HB
(J +[J(04)))+ 2C 1).
(99)
We now decompose the Σ ( -[][[ There several existing results for this. We use Lemma from [6], re-stated below, since it is sharper than most existing results.
Lemma 16. Consider any policy update rule of form
0k+1 = 8% + Ookk
(100)
If 3 hoolds, then the following inequality is satisfied for any K.
K
G K K-1
aG2
K
J K
B[J(O+)) S Ebias
E
(Ex [Wm]] - wfll
Σ
E ||wa 1?
K
2K
==
k=0
+ aK
Exndor [KL(T (+1s)|TTT
(101)
where KL(-II-) is the Kullbuck-Leibler divergence, w is the NPG direction F(0L)-IVJ(()) n the optimal policy, J is the optimal value of the function J(),, and Bxl denotes conditional expectation given the history up epoch k.
Using the above result, we obtain the following.
K
BHG
K-1
aG²BH K-1
HB
Σ (J k=0
B[J(Oa)))
ST chins +
E
( [a]]
wf)ll
E
||
K
K
k=
BH
+
E
[L(TT((|s)
(e)
(102)
The term containing E. || can be further decomposed as
oG2BH K
2aGzBB (a)
2aGrBH
E|WWa|? <
E Bllwk - will +
E ||
K
K
(103)
2aG
BH
20G²BH BH
E Ilw - 2
E
(o)(()))
K2K
where (a) follows from Assumption and the definition that w -V The result now follows by substituting 102) and [03 in 999)
36

---

H Proof of Theorem 1
We shall now derive bound for Kk= obtain:
((=))) Given that the function J is L-smooth, we
10x+1)
L
2 2(0z) + (0,)(0)), 0z)
110++1 0x11
2
- =J(O + + (VoJ(O)), L²L 1wi11
-(())
Wk - w[]
1 wk + wfll
2
[8 ((0)) + (V. (1)) vo. + a (VoJ(0s), - w/)
- L/WA w/1l - 2/2L
(
2 ((0z) + (o a (V (oJ(())), - w() a² L|ww wEl1 --- a²L #L|WWR1?
aaGa + +a²L) 1wwe wAll
-(00)) 2G
[oJ(0=)]1
Vo + Gp(ux (wx w/)l1
20
a² 1|
2 2(0h))+ + 2G
| [o
(2
+ t
- -
2
(2)
a²I [[o]((())1
(009
2 J(0%)+ + 2209 12
+ a221)) 1|0 will
2
(104)
where (a) use the Cauchy-Schward inequality and the definition that w = F(Ox) -V Relations (b), and (c) are consequences of Assumption and and respectively. Summing the above
inequality over & E {0.... "0,..KKKK K - 1), rearranging the terms and substituting 1C7L we obtain
n² L6G VoJ(OL)1
(1e
112 +
As
s J(OK) J((b) +
1609L)
Σ
1 wEll?)
k=
(105)
(0)
2² + 8L
[
[K-1
I 2
16C7L)
Σ
||w0- - wfll
where (a) uses the fact that J(.) is absolutely bounded above by 1. Inequality (05) can be simplified as follows.
K
Σ [
3
K-1
+ (2G) + x?)
[E
E 1w will
4²
hm0
32
+ (2G + 1²2) K
exp (-114t10)a)
11:0 - 11:0- will
(106)
Cra
C m AB
+ G2p
exp
(- HA* ||E1 11- + G2u
+ +G7
AB
VdCACuar rrar
C²
dG2c²
dC
Feapp) -eapp
1BB
11
12
37

---

Furthermore, using
ز² 4G
find that HB E
k==
3 (J
K-1
E [(,))
can be written as follows.
[[ger]]
G²
S T V Chias + TG1 E (B [wx] - w
E |
4
E Bendr (-|))=== (.1s))
122
G2
G²T
1 T Cbias + TG1 E (B [wx] - will +
2 |amt will
E ( 2G
LGgLVTlog T
B [KL( [l (-I=( |))] + C(K + +
Using the bound on V 2 derived earlier, along with the second-order error and bias of the NPG estimates, including all constants, from (96) and (97). we obtain the following regret bound, omitting all non-dominant terms.
E Regrl
122
G2VT GRL
G.Crarvm 122x
VdG C2
0
C2OGVT(logT)
12L
(107)
VddaCrar
Ca
GiCrarVm
Tapp
+ VT
T Vebias
The regret bound above is obtained by setting the learning rates as follows: policy update rate and NPG estimation rate M G7-
n² 4G9T. critic learning rates (3, ca) = /
Remark 2 (Scalability of Chi and Crar). The constants Cuit and Ctar reflect the difficulty of exploration under a given policy class and may scale with structural properties the MDP such as state-space size or connectiviry. Such dependence is inherent. as any algorithm must visit all states to avoid constant per-iteration regret, and even in ergodic MDPs the mixing time tmix can scale with the state space. Our result extends existing ergodic-MDD guarantees to the more general unichain setting without degrading these constants. Specifically, while state-of-the-art actor-critic methods achieve complexity O VT) [16]. our bound 3 vT) involves constant C that characterizes the Cesàro mixing time (22) Sec. 6.6], which satisfies C S Ttmixxfr ergodic chains [22] Ex. 6.11]. In certain Markov chains, such as the biased random walk the n-cycle [22) Ex. 24.2], the Cesàro mixing time is only (n) versus the standard mixing time which is O illustrating that averaging distributions over time accelerates convergence compared single-step mixing.
Remark 3 (On the Unichain Assumption). To the best of our knowledge, no existing policy gradient methods (with general policy parametrization) have theoretical guarantees for average-reward. infinite-horizon MDPs beyond the unichain case. Our work is the first to establish such guarantees under the general unichain assumption, which is the weakest known condition under which the policy gradient theorem holds (33]. While value-based methods admit guarantees beyond this setting, policy gradient approaches require fundamentally different analyses, making existing techniques inapplicable. A possible, though still conjectural, direction for relaxing the unichain assumption is to restrict policy search to unichain unichain-inducing policies by maintaining strong exploration initially and annealing it the algorithm converges. Notably, weakly communicating MDPs, the most general class solvable from a single stream of experience, always admit an optimal unichain policy (30).
38


Reviews:
[{"review_id": "WbExZqAWM4", "reviewer": "Reviewer_KMVK", "summary": "This paper presents the natural actor-critic algorithm for infinite-horizon average-reward Markov Decision Processes (MDPs) under the unichain assumption, which allows for both periodicity and transient states. Unlike prior works that rely on ergodicity for theoretical analysis, this paper derives an $\\tilde{O}(\\sqrt{T})$ regret bound under substantially weaker assumptions. Key technical innovations include the use of batching to mitigate variance and periodicity, and the introduction of constants $C_{\\text{hit}}$ and $C_{\\text{tar}}$ to characterize convergence behavior. The algorithm employs general function approximation for both actor and critic components, enhancing scalability.", "questions": "See weakness.", "limitations": "A theoretical work may not pose the societal impact as a high priority.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\nNovelty: The paper makes a novel and substantial contribution by analyzing regret for actor-critic methods under the unichain assumption—this represents a significant step forward in understanding policy gradient methods in more general settings.\nAnalysis: The regret bound is carefully derived under general function approximation, with comprehensive proofs and clear articulation of assumptions. The techniques used to handle the challenges of periodicity and transient states are thoughtful and well-executed.\nClarity: Despite the technical depth, the writing is generally clear, and the theoretical insights are well-motivated.\n\nWeaknesses:\nWhile I do not consider the absence of experiments a major concern for a theoretical paper, it would still be valuable to evaluate the practical behavior of NAC-B—particularly its sensitivity to function approximation quality, step sizes, and batch sizes. For instance, although the use of large batches is theoretically well-justified, it could be costly in practice. A discussion or guidance on batch size selection in practical settings would help strengthen the paper.\nIn addition, although the unichain assumption is more general than the commonly studied ergodic setting, the paper would benefit from a more detailed discussion of its practical relevance. Specifically, it would be helpful to clarify in what types of real-world applications this assumption is likely to hold, as many practical environments may not satisfy the unichain condition.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and feedback. We address the weaknesses raised below.\n\n\n**Regarding experimental evaluation**: While empirical validation is valuable, our focus here is on establishing theoretical guarantees, which remain limited for policy gradient methods beyond ergodicity. However, we would like to clarify the rationale for using large batch sizes in policy gradient estimation. In our algorithm, large batches are theoretically justified: collecting a substantial number of samples per iteration improves the accuracy of both the critic estimate and the resulting natural policy gradient direction. This leads to fewer policy updates and ultimately enables order-optimal regret. \n\nTo further illustrate the practicality of using a large number of samples per policy update, consider Trust Region Policy Optimization (TRPO), which is based on the Natural Actor Critic framework. Although TRPO differs from our method, for instance by being formulated in the discounted reward setting, it reflects standard design choices in practice. It is typical for TRPO to use thousands of samples per policy iteration, with values commonly ranging from 2,000 to 20,000 depending on the environment. For instance, the Spinning Up implementation sets the default number of samples per iteration to 4,000, as specified in both their documentation and source code. Although the notion of \"batch size\" differs due to how gradients are computed in both works, this is to highlight that even TRPO relies on large number of state-action samples to estimate the natural policy gradient direction. \n\n**Regarding the unichain assumption**: We present two examples below: one in which the MDP is periodic and another in which it is reducible. In both cases, the optimal policy does not induce an ergodic chain, implying that one cannot restrict the search to policies that induce ergodic chains. This demonstrates that periodicity and transient states may be unavoidable. Nonetheless, the underlying themes in these examples are commonly encountered in practice.\n\nAn autonomous drone operates in three modes: active delivery ($s_1$), standby hovering ($s_2$) and low‑battery shutdown ($s_3$). At each step it may choose to continue deliveries (action $a_1$) or return to standby (action $a_2$). In state $s_1$, action $a_1$ leads to $s_1$ with probability $0.8$, to $s_2$ with probability $0.15$ and to $s_3$ with probability $0.05$. In $s_2$, action $a_1$ returns deterministically to $s_1$ while action $a_2$ keeps the drone in $s_2$ with probability $0.9$ and moves it to $s_3$ with probability $0.1$. Once in $s_3$, the drone remains there indefinitely. Rewards are $1$ in $s_1$, $0.5$ in $s_2$ and $0$ in $s_3$. All policies induce a single recurrent class, either the cycle $\\{s_1,s_2\\}$ or the absorbing state $\\{s_3\\}$, so the MDP is unichain but not ergodic.\n\n\nIn robotic gait control, particularly for bipedal or quadrupedal robots, the system transitions through discrete movement phases such as left stance, right stance, or flight. States include these phases along with joint configurations and velocities, while actions correspond to motor commands. The dynamics are stochastic yet controllable, and most policies lead to all phases being visited, making the system irreducible. However, optimal locomotion, minimizing energy or maximizing stability, relies on repeating a fixed sequence of movements, such as alternating stances, inducing a periodic policy. This reflects the inherent cyclic nature of locomotion, where balance and rhythm are essential for efficient and stable motion. More broadly, periodic optimal policies can naturally arise in other settings where the environment or reward structure strongly incentivizes strict alternation or repetition over a fixed cycle, such as traffic signal control, task scheduling, or maintenance operations."}, {"review_id": "N8N9frKypu", "reviewer": "Reviewer_dNcD", "summary": "This paper investigates average-reward Markov decision processes under the unichain assumption. The authors introduce a model-free, policy-gradient algorithm called Natural Actor-Critic with Batching. A regret bound of $\\tilde{O}(\\sqrt{T})$ is proved with two parameters identified, $C_{hit}$ the worst-case expected time to enter the recurrent class, and $C_{tar}$ the expected time to reach a state drawn from stationary distribution.", "questions": "Please refer to the weakness", "limitations": "This manuscript omits a societal impact discussion, but this is not a blocking issue since this paper’s theoretical focus and negligible immediate societal risk.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n1. This paper proposes the algorithm NAC-B and provides the first order-optimal regret analysis for general PG in non-ergodic MDPs, which allows transient states and periodicity, for the average-reward RL problem.\n2. With the large-batch averaging, they novelly prove the total-variation bound for the time-averaged state distribution (Lemma 2).\n3. The authors propose the new techniques of building a “hit-the-recurrent-class” high-probability event and projecting updates onto the orthogonal complement of the shifting kernel to handle singular critics.\n\nWeakness:\n1. This paper comes with no experiment, especially considering the very large batch $B=O(\\sqrt{T})$ in their algorithm, which needs to be stored before performing the NPG update. Experiments are needed to verify the practical feasibility of this design.\n2. Two properties of the unichain MDP $C_{hit}$ and $C_{tar}$ might be very large. In large or poorly connected MDPs, these may scale with the size of the state space or the intermediate policies. A more detailed analysis and comparison with prior work would clarify their impact on sample complexity.", "was_revised": true, "final_justification": "I think this paper's contribution is great in case of providing the first order-optimal regret analysis for general PG in non-ergodic MDPs. The writing is clear and theoretical contribution is obvious while the only concern is the lack of real life empirical experiment, so I will keep my original assessment.", "rebuttal": "We thank the reviewer for their feedback and comments. We hope to clarify and address the points raised.\n\n**Regarding experiments and practicality of large-batch sizes**: As noted in the manuscript, this work focuses on establishing theoretical regret guarantees, with detailed experimental evaluations left for future work. \n\nWhile our algorithm makes use of a large batch size $ B = \\mathcal{O}(\\sqrt{T}) $, this does not require storing all $ \\sqrt{T} $ samples. In fact, we only need to maintain an online average of the policy gradient estimate, which can be updated incrementally as new samples are collected. This design avoids the need for storing the entire batch, making the implementation efficient and scalable in practice.\n\n\nIn our algorithm, large batches are theoretically justified: collecting a substantial number of samples per iteration improves the accuracy of both the critic estimate and the resulting natural policy gradient direction. This leads to fewer policy updates and ultimately enables order-optimal regret. \n\nTo further illustrate the practicality of using a large number of samples per policy update, consider Trust Region Policy Optimization (TRPO), which is based on the Natural Actor Critic framework. Although TRPO differs from our method, for instance by being formulated in the discounted reward setting, it reflects standard design choices in practice. It is typical for TRPO to use thousands of samples per policy iteration, with values commonly ranging from 2,000 to 20,000 depending on the environment. For instance, the Spinning Up implementation sets the default number of samples per iteration to 4,000, as specified in both their documentation and source code. Although the notion of \"batch size\" differs due to how gradients are computed in both works, this is to highlight that even TRPO relies on large number of state-action samples to estimate the natural policy gradient direction. \n\n**On the Scalability of $ C_{\\text{hit}} $ and $ C_{\\text{tar}} $**: We appreciate the reviewer’s concern regarding the constants $ C_{\\text{hit}} $ and $ C_{\\text{tar}} $, which capture the difficulty of exploration under a given policy class. We agree that these constants may scale with structural properties of the MDP such as its connectivity or the number of states. However, we note that some dependence on state-space size or connectivity in discrete state MDPs is unavoidable in general since any algorithm must visit all states to avoid incurring constant regret at each iteration. We note that even the mixing time, $t_{mix}$ in ergodic MDPs can scale with the size of the state space. \n\n\n\nWe emphasize that our result extends existing guarantees from ergodic MDPs to the more general unichain setting without any degradation in the underlying constants. For instance, the state-of-the-art complexity for actor-critic methods in ergodic MDPs is $O(t_{\\text{mix}}^3 \\sqrt{T})$ \\[14]. Although this result does not provide a regret bound, it may be interpreted as a pseudo-regret guarantee. In contrast, our result achieves a bound of $O(C^3 \\sqrt{T})$, where the constant $C$, defined in our paper, can be viewed as a characterization of the Cesàro mixing time as established in Lemma 2. The Cesàro mixing time (Section 6.6 in [A]) captures time-averaged convergence behavior and is at most $7 t_{\\text{mix}}$ in ergodic chains (see Exercise 6.11 in \\[A]).\n\n\nFurthermore, in certain ergodic Markov chains, the Cesàro mixing time can be substantially smaller than the standard mixing time. For instance, in the biased random walk on the $n$-cycle (Example 24.2 in [A]), the standard mixing time is of order $n^2$ (see Section 5.3.2 in [A]), whereas the Cesàro mixing time is only $O(n)$ (see Example 24.2 in [A]). This improvement arises from bounds on the expected stopping time to reach a randomly chosen state from the stationary distribution, which scales linearly with $n$. By averaging the distributions over the first $t$ steps, Cesàro mixing mitigates the effects of periodicity and accelerates convergence to the stationary distribution compared to relying on the distribution at a single time step.\n\n\n\nIn addition, we note that the computational complexity of our algorithm is independent of the cardinalities of the state and action spaces, offering a substantial advantage over tabular or value-based approaches. While our algorithm is applicable to continuous state and action spaces, our theoretical analysis presently focuses on the finite setting.\n\n\n\nWe will revise the paper to clarify the interpretation of these constants and include further discussion comparing them with mixing-time-based assumptions used in prior work.\n\n---\n[A] Levin, D.A., & Peres, Y. (2017). Markov Chains and Mixing Times (2nd ed.). American Mathematical Society."}, {"review_id": "2hLyysIhEa", "reviewer": "Reviewer_otcy", "summary": "The authors study infinite-horizon average-reward reinforcement learning under the assumption that the learner has access to a policy class and a feature mapping that enables linear approximation of the value functions for all policies in the class. A closely related prior work proposed an actor-critic algorithm for this setting but relied on a strong ergodicity assumption. This paper relaxes that requirement to a weaker unichain assumption by introducing a novel batch algorithm for gradient estimation and providing the associated analysis. The key to the analysis is handling the set of transient states.", "questions": "Q1) The proposed algorithm resembles MLMC-NAC [14], with a difference in how the inner loop size is determined. Specifically, MLMC-NAC samples the inner loop size from 2^Geom(1/2) while the proposed algorithm in this submission fixes the size to B. What is the intuition behind the difference? Is the difference necessary for the analysis?\n\nQ2) How challenging would it be to extend this work to settings where only the Bellman optimality equation is assumed? Since not all policies are exploratory under this weaker assumption, I would expect that some non-trivial algorithmic techniques are required to ensure sufficient exploration. Have there been any prior attempts to address this within the class of policy gradient algorithms?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThe paper presents its contributions clearly. The proposed batching strategy for gradient estimation, along with the accompanying analysis under the unichain assumption, is novel and well-articulated.\n\nWeaknesses:\n- While the paper offers a novel contribution, its overall novelty and significance appear limited, as the algorithmic structure closely resembles that of MLMC-NAC ([14], ICML 2025).\n- The exposition could be improved for clarity. Understanding the proposed algorithm currently requires substantial prior knowledge of policy gradient methods in the average-reward setting. In particular, elaborating on the phrase \"follows standard constructions in Temporal Difference\" (Line 201) and incorporating relevant content from Appendix B into the main text would enhance accessibility.", "was_revised": true, "final_justification": "Authors have addressed my major concern on the novelty of the submission. As clarified in their response to my question, although the algorithm may appear similar to prior work at a surface level, they introduced necessary modifications without increasing its complexity and provided accompanying analysis that removes the need for the strong ergodicity assumption required by previous studies.\n\nGenerally, relaxing the assumption on ergodicity requires significant work under the average-reward setting, and I believe this submission is a good step toward to relaxing this assumption under the policy-based algorithm class.", "rebuttal": "We thank the reviewer for their feedback. Below we address the points raised.\n\n**Response to Weakness 1/Question 1**: While our algorithm shares surface-level similarity with MLMC-NAC in the use of nested sampling, there are critical differences in both methodology and analysis objectives.\n\nFirst, we intentionally adopt a simpler design in which the inner loop size is fixed to a batch size $ B $ rather than being sampled from a geometric distribution as in MLMC-NAC. This choice is deliberate: our goal is to demonstrate that even a simple averaging scheme, without elaborate techniques such as MLMC, can achieve order-optimal regret guarantees. We believe this yields a stronger statement, as it shows that optimal performance can be guaranteed only using simple sample averaging even without ergodicity.\n\nMore specifically, MLMC-NAC in [14] uses multilevel Monte Carlo to achieve an $O(1/T)$ bias with only $O(\\log T)$ samples in expectation, leveraging exponential mixing of the MDP. Since we do not assume such fast mixing, we resort to simple averaging, which requires $\\Theta(\\sqrt{T})$ samples to control bias. However, the reduced variance from averaging allows us to limit the number of outer iterations to \\$O(\\log T)\\$, preserving order-optimal complexity through a more refined analysis.\n\nFinally, while the reviewer only mentions the algorithm comparison and not the analysis - our analysis is significantly different from [14]. In addition to the differences arising from the algorithmic  since the bulk of our analysis is in handling challenges arising due to the unichain assumption vs the well-studied ergodic case. Analyses in the ergodic setting typically rely on exponentially fast mixing, a property that does not generally hold in the classical unichain setting. For example, in periodic MDPs, the limit $\\lim_{t \\to \\infty}(P_{\\pi_\\theta})^t(s_0, \\cdot)$ may not exist. To overcome this, we introduce a large-batch averaging technique and show that the time-averaged distribution converges to the stationary distribution at a rate of $O(1/t)$ (Lemma 2), even without exponential mixing. This averaging approach is a key novelty that enables us to prove decay rates for the bias and variance of our estimators (Lemma 3), which in turn facilitates bounds on value and Q-functions. Another technical contribution is our treatment of transient states, which remain problematic due to their limited long-term relevance. To isolate their effect, we establish a rapid entry time into the recurrent class (Lemma 10), allowing the use of the strong Markov property to restrict the analysis to the recurrent component.\n\n**Response to Weakness 2:** Thank you for pointing this out. We will move the details of the TD learning procedure from the appendix to the main paper. \n\n**Response to Question 2:** When only the Bellman optimality equation is assumed, the classic policy gradient theorem is not applicable, as it relies on the unichain assumption. To the best of our knowledge, no policy gradient methods with guarantees exist for average-reward, infinite-horizon settings beyond this case. Our work is the first to establish such guarantees under the general unichain assumption, the weakest condition under which the policy gradient theorem is known to hold.\n\nWhile value-based methods achieve regret bounds under only the Bellman optimality assumption, policy gradient methods require fundamentally different analysis. Policy gradient methods scale far better with large state and action spaces, making it the practical default. Given their empirical success, extending theoretical guarantees to more general MDPs is a compelling goal. One possible direction, though purely conjectural at this stage and which may require significant effort, is to restrict policy search to unichain-inducing policies by maintaining strong exploration early and then annealing it as the algorithm converges. Weakly communicating MDPs, the most general class solvable with a single stream of experience, always admit an optimal unichain policy. This conjectured approach could bridge the gap between theory and practice but remains to be rigorously investigated. We will point to this future work direction in the final version."}, {"review_id": "6bTGsT8vOp", "reviewer": "Reviewer_i9Td", "summary": "This work proposes a natural actor critic algorithm with batching for average-reward Markov Decision Processes, and for the first time weakens the existing strong ergodicity assumptions to the unichain assumption and still preserves the order-optimal regret.", "questions": "(1) Why are some actor-critic algorithms [26, 34, 14] and unichain settings [3, 20] excluded from Table 1? You could mention the properties of these works that do not fit the caption of Table 1, such as \"model-free\", \"infinite-horizon\" and \"average-reward\". \n\n(2) At the beginning of Section 4.1, is $b_v(\\theta, z)$ defined in (14)? (16) defines $b_u$ with 3 inputs. \n\n(3) Is the outer product defined as $a\\times b=ab^{\\top}$ or $ba^{\\top}$? You could define in the paper to be more clear. \n\n(4) In the proof of Lemma 2, should $T_{\\theta}$ be replaced with $T_{\\theta}-1$ since $s_{T _ {\\theta}}\\in\\mathcal{S} _ {\\mathcal{R}}^{\\theta}$? $\\mathbb{E} _ {\\theta}$ be conditioned on $\\mathcal{F} _ {T_{\\theta}}$ based on strong Markov property?", "limitations": "Linear function approximation of critic is assumed, which could be extended to more general function approximation. Also, the conclusion section mentions future directions to extending this analysis to other useful settings such as constrained MDPs, multi-agent RL etc. These indicate the limitation that the current analysis only focuses on very basic setting.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths: This work studies average-reward Markov Decision Processes, an important problem, and makes a fundamental breakthrough in the regret analysis by reducing the existing strong ergodicity assumptions to the unichain assumption while still preserving the order-optimal regret. The non-trivial challenges of transient states are solved by their novel proof techniques, such as using the convergence rate of transition kernel running average (Lemma 2) and conditioning on high probability event of bounded stopping time (Theorem 2). The general proof outline looks reasonable (I did not check details). The presentation is in general very clear. \n\nWeaknesses: A few points may need clarification or correction as shown in the questions below. This work could be stronger using experimental comparison with existing algorithms for average-reward MDPs.", "was_revised": true, "final_justification": "I just found every reviewers are satisfied with the authors' rebuttal.\nI would like to keep my current rating.\nReviewer  i9Td", "rebuttal": "We sincerely thank the reviewer for their thoughtful feedback and comments. Below we address the questions raised.\n\n**Response to Question 1**: We agree that providing more context on the works both within and outside the table would help improve the clarity of our paper, which we will make sure to do. For the specific papers mentioned:\n\n* [26] Provides only local convergence, giving a bound on the norm of the policy gradient rather than the suboptimality in average reward relative to the optimal policy.\n\n* [34] Based on a model-based approach using a generative model, whereas our setting is entirely model-free.\n\n* [14] Does not provide a regret bound, but establishes a closely related global convergence guarantee. We will include it in the table for completeness. A regret bound may not follow directly from this result due to the use of varying trajectory lengths across iterations.\n\n* [3] This is already included in the table. If you are referring to the other unichain work [21], it is because the unichain result in this work assumes access to a simulator, unlike the other works listed in the table.\n\n\n* [20] Assumes access to exact gradients, which significantly simplifies the setup and enables the authors to obtain a logarithmic regret bound.\n\nWe will definitely expand details on these related works in the final version. \n\n**Response to Question 2**: Yes that is correct, the reason $b_v$ is defined with 2 inputs and $b_u$ with 3 is that $b_u$ depends additionally on the estimate of value function parameter $\\xi$ as well so that it can form an estimate of the policy gradient. Thus, $b_v$ and $b_u$ are different functions. \n\n**Response to Question 3**: Thank you for pointing this out. In the context of our paper, either definition is acceptable, as we only use it to define the Fisher information matrix where we take $a = b = \\nabla \\log \\pi_\\theta(a|s)$. We will revise the expression to omit the outer product notation and simply write it as $[\\nabla \\log \\pi_\\theta (a|s)\\nabla \\log \\pi_\\theta(a|s)^\\top]$.\n\n\n**Response to Question 4**: Thank you for pointing this out. We will update $T_\\theta$ to $T_\\theta - 1$ accordingly.\n\n\n**Response to Limitations**: We note that this work provides the first order-optimal regret analysis for general policy gradient methods in non-ergodic MDPs under the average-reward setting. By showing that unichain MDPs can be effectively handled within the policy gradient framework, we open several promising research directions outlined in the future work section. While empirical validation is valuable and planned for future work, our focus here is on establishing provable guarantees for policy gradient methods, which are widely used in practice but lack comparable theoretical guarantees in this setting."}]

Author rebuttal:

Meta-review: This paper develops a NAC with batching algorithm for infinite-horizon average-reward Markov Decision Processes (MDPs) under the unichain assumption. The reviewers are all positive about this paper, and its techniques to dealing with the unichain case are of potential interest for analyzing other settings in the future. It is recommended to be accepted.
Decision: Accept (poster)