Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPs
Authors: Yukuan Wei
Xudong Li
Lin F. Yang
Venue: ICLR 2026 Poster (2026)
Keywords: Constrained Average-Reward Markov Decision Process
Minimax-Optimal Bounds
Sample Complexity
Primary area: learning theory

Abstract: Recent advances have significantly improved our understanding of the sample complexity of learning in average-reward Markov decision processes (AMDPs) under the generative model. However, much less is known about the constrained average-reward MDP (CAMDP), where policies must satisfy long-run average constraints. In this work, we address this gap by studying the sample complexity of learning an $\epsilon$-optimal policy in CAMDPs under a generative model. We propose a model-based algorithm that operates under two settings: (i) relaxed feasibility, which allows small constraint violations, and (ii) strict feasibility, where the output policy satisfies the constraint. 
We show that our algorithm achieves sample complexities of $\tilde{O}\left(\frac{S A (B+H)}{ \epsilon^2}\right)$ and $\tilde{O} \left(\frac{S A (B+H)}{\epsilon^2 \zeta^2} \right)$ under the relaxed and strict feasibility settings, respectively. Here, $\zeta$ is the Slater constant indicating the size of the feasible region, $H$ is the span bound of the bias function, and $B$ is the transient time bound. Moreover, a matching lower bound of $\tilde{\Omega}\left(\frac{S A (B+H)}{ \epsilon^2\zeta^2}\right)$ for the strict feasibility case is established, thus providing the first minimax-optimal bounds for CAMDPs. Our results close the theoretical gap in understanding the complexity of constrained average-reward MDPs.

Published as a conference paper at ICLR 2026
NEAR-OPTIMAL SAMPLE COMPLEXITY BOUNDS FOR CONSTRAINED AVERAGE-REWARD MDPS
Yukuan Wei
Xudong Li
School of Mathematical Sciences
School of Data Science
Fudan University
Fudan University 1 1 xuxdonge fudan, hadanneuu......ddddd... cn.
223001 00000080045mm wudanneeeeee edu. cn
Lin F. Yang
Electrical and Computer Engineering Computer Science University of California, Los Angeles i dinyangeee, ucl edu
ABSTRACT
Recent advances have significantly improved understanding of the sample complexity of learning in average-reward Markov decision processes (AMDPs) under the generative model. However, much less known about the constrained average-reward MDP (CAMDP), where policies must satisfy long-run average constraints. In this work, we address this gap by studying the sample complexity of learning an e-optimal policy in CAMDPs under a generative model. We propose a model-based algorithm that operates under two settings: (i) relaxed feasibility, which allows small constraint violations, and (ii) strict feusibility, where the out- put policy satisfies the constraint. We show that our algorithm achieves sample
complexities of Ô (SA(B+ and Ö (SA(B+H)) under the relaxed and strict c²C²
feasibility settings, respectively. Here, Ç is the Slater constant indicating the size of
the feasible region, the span bound of the bias function, and B is the transient
=²ç² time bound. Moreover, matching lower bound of ② (SA(B+ for the strict
feasibility case is established, thus providing the first minimax--ptimme bounds for CAMDPs. Our results close the theoretical gap in understanding the complexity of constrained average-reward MDPs.
INTRODUCTION
Reinforcement learning (RL) (Sutton & Barto, 1998) provides a powerful framework for sequential decision-making under uncertainty, with successes in domains such game playing (Mnih et al., 2015; Silver et al., 2016), robotic control (Tan et al., 2018; Zeng et al., 2020), clinical decision- making (Schaefer al., 2005), and aligning large language models with human preferences (Shao et al., 2024; Ouyang et al., 2022). Most classical RL algorithms optimize a single reward signal without additional constraints. Yet in many high-stakes applications, agents must also be safe, fair, and
in addition to being efficient in practice. This leads to constrained Markov decision processes (CMDPs) (Altman, 1999), which maximize expected reward subject an auxiliary cost constraint. A representative example arises in wireless sensor networks (Buratti et al., 2009; Julian et al., 2002), balaneing high throughput with average power constraints.
A growing body of work investigates constrained reinforcement learning in unknown environ- ments (Efroni et al., 2020; Zheng & Ratliff, 2020; Qiu et al., 2020; Brantley et al., 2020; Kalagarla et al., 2021; Yu et al., 2021; Ding et al., 2021; Gattami et al., 2021; Miryoosefi & Jin, 2022). These efforts focus on the online learning setting. aiming to minimize both regret and constraint violation under exploration, estimation, and policy optimization challenges in finite-state, finite-action CMDPs. In contrast, recent work (HasanzadeZonuzy et al., 2021; Wei et al., 2021; Bai et al., 2021; Vaswani et al., 2022) studies the generative model (Kearns & Singh, 1999; Kakade, 2003: Agarwal et al.,

---

Published as a conference paper at ICLR 2026
2020; Sidford et al., 2018; Yang & Wang. 2019), i.e., simulator that provides sample transitions and rewards for any queried state state-action pair, removing the need for exploration.
Most prior work centers on kiite-horizon or discounted MDPs, where either the horizon is fixed to T steps or future rewards are geometrically discounted by y². While analytically convenient, these for- mulations can limit long-term performance: finite-horizon methods impose cutoff, while discounting attenuates future rewards. To address this, the average-reward MDP (AMDP) framework (Puterman, 2014) seeks to maximize steady-state long-run average reward.
Although planning in AMDPs is relatively well-understood (Altman, 1999; Borkar, 2005; Borkar & Jain, 2014), sample complexity for learning s-optimal policies was challenging due the lack of episode resets and the need to reason about long-term behavior without discounting. Recent advances in the generative model setting establish near-optimal bounds depending on the optimal bias span H and the mixing transient time B, yielding rates θ [S([++H] H) (Zurek & Chen, 2024), where S is
22
the number of states and A the number of actions.
Despite this progress for unconstrained AMDPs, the constrained MDPs (CAMDPs)-remattee poorly understood. In CAMDPs, the agent must maximize steady-state average reward while satisfying an average constraint cost, risk, or resource usage, capturing long-term fairness, sustainability, and safe deployment. While discounted CMDPs have seen progress in both relaxed and strict feasibility regimes (Vaswani et al., 2022), there are still no known sample complexity bounds for learning in CAMDPs, and the fundamental statistical limits in relaxed or strict feasibility settings remain open.
average-reward
This gap motivates our work. We initiate the study of the sample complexity of learning s-optimal policies CAMDPs under the generative model. We develop a model-based primal-dual algorithm handling both relaxed feasibility, where the returned policy may violate the constraint by at most and strict feasibility, where the policy must satisfy it exactly. We establish matching near-optimal upper and lower bounds in terms of the bias span, the transient time, and the Slater constant Ç. While relaxed and strict feasibility have been studied in discounted CMDPs (Vaswani et al., 2022), our work provides the first sample complexity characterization for CAMDPs in the average-reward setting. Below, we summarize our contributions in more detail.
Our contributions. We present the first oear-optimal sample-complexity bounds for learning in CAMDPs with access to generative model:
We design model-bases algorithm that returns an e-optimal policy for CAMDPs under both relaxed and strict feasibility. Our method relies on solving a sequence of unconstrained average- reward MDPs using black-box planners.
In the relaxed feasibility setting, we prove that our algorithm requires at most Ô (SA(B+H) samples, where 5 and are the number of states and actions, H is the span bound of the bias function, B is transient time bound, and is the Slater constant characterizing the size of the feasible region.
In the strict feasibility setting, the sample complexity increases to Ô [S((+H)) E²Q²
and we show that
These are the first lower bounds for strict feasibility in CAMDPs, establishing a provable separation between the relaxed and strict regimes.
this dependence on Ç is necessary by proving a matching lower bound of ñ
SA(B+
e"c"
Together, our results provide the first near minimax-optimal sample complexity bounds for constrained average-reward reinforcement learning with respect to S, A, B and and reveal fundamental insights into how long-run constraints affect the hardness of planning under uncertainty.
1.1 RELATED WORKS
There is a large body of research on the sample complexity of learning in unconstrained Markov decision processes (MDPs); see the monograph by Agarwal et al. (2019) for a comprehensive overview. In parallel, substantial progress has been made in constrained reinforcement learning under unknown dynamics (Efroni et al., 2020; Zheng & Ratliff, 2020; Qiu et al., 2020; Brantley et al., 2020; Kalagarla et al., 2021; Yu et al., 2021; Ding et al., 2021; Gattami et al., 2021; Miryoosefi & Jin, 2022), particularly in fnite-horizon settings. Another line of work addresses discounted constrained MDPs
2

---

Published as a conference paper at ICLR 2026
(CMDPs) with access to a generative model (HasanzadeZonuzy et al., 2021; Wei et al., 2021; Bai et al., 2021; Vaswani et al., 2022), yielding sample-efficient algorithms under both relaxed and strict constraint satisfaction.
In contrast, the average-reward setting is less explored. For unconstrained average-reward MDPs, Zurek& & Chen (2024) established nearly minimax-optimal bounds under a generative model, showing that Ô (SAH/E* / samples suffice for weakly communicating MDPs, where H is the span of the optimal bias function. They further introduced a transient time parameter B to handle general multichain MDPs, proving matching bound of Ô (SA(B + H))=²). However, their analysis does not incorporate constraints, and extending their framework to constrained average-reward MDPs (CAMDPs) remains open.
Among works on CMDPs, Vaswani et al. (2022) provided the first minimax-optimall sample com- plexity bounds for the discounted setting via dual linear programming. Yet their techniques do not extend to average-reward problems, where key properties like Bellman contraction no longer hold. In separate effort, Bai et al. (2024) studied CAMDPs in online model-free setting with general policy classes, establishing sublinear regret for constraint violation and the duality gap. Their results, however, focus on asymptotic behavior and do not provide near-optimal finite-sample guarantees under a generative model.
To our knowledge, this work is the first establish near-optimal sample complexity bounds for CAMDPs under both relaxed and strict feasibility in the generative model setting. We propose a primal-dual algorithm that achieves minimax-optimal rates in terms of the number of states, actions, bias span, transient time, and the Slater constant, thereby unifying and extending existing results from both the unconstrained and discounted settings.
2 PROBLEM FORMULATION AND PRELIMINARIES
We study an horizon constrained average-reward Markov decision process (CAMDP), denoted by M and specified by the tuple (S, A. P,r, r, b, s). Here, S and A denote the sets of states and actions; P S A + As the transition probability kernel; and E As represents the initial state distribution. The objective is to maximize the primary reward function r S x A -> [0, 1]. subject to a constraint
8 x A- [0, 1]. Given that A denotes the probability simplex over actions, the expected average reward under stochastic stationary policy π : S + A is defined as (s) lim + E. I r(s,, az)]. where so 8, at (( 8t). and 81+1 ~ P(- Se, ae))
The bias function of a stationary policy π is hT( == C-limy-=oo E Σ 1== 2 (r. (S.)) where C-lim denotes the Cesàro limit. When the Markov chain induced by P. is aperiodic, the Cesàro limit coincides with the standard limit. For any policy æ. the pair (p",h*) h²) satisfies the Bellman-like relations p. Pap7 and pf + h2 Tx + Pzh.. Similarly, define the constraint value function and constraint bias function of π as P and h. The objective in CAMDP is to find a policy solving the following optimization problem:
max P (s)
P. (s) b.
We denote the optimal stochastic policy by n", and its corresponding reward value by (s).
Weakly communicating setting A Markov decision process (MDP) is weakly communicating if its state space S can be partitioned into two disjoint subsets S S U U2, such that states in S₁ are transient under any stationary policy, and for any 8, s' S2 there exists stationary policy making s' reachable from s. In such MDPs the average reward vector p" is constant, i.c., p"(s) = pp for all E S. Consequently, (p", h²) satisfies the average-reware optimality equation:
+ h" (s) = max max(r(s,
(r(s,a) ()) Σ P(s') (aaah"""s")) E.
a
We occasionally abuse notation and treat p" as scalar. A stationary policy is multichain if it induces multiple closed irreducible recurrent classes, and an MDP is multichain if it admits least one such policy. While general MDPs may only possess multichain gain-optimal policies with non-constant p*, any weakly communicating MDP admits at least one unichain gain-optimar policy under which p" is uniform. Moreover, every uniformly mixing MDP is weakly communicating. A stronger assumption communicating, which excludes transient states and requires every state be reachable from every other under every stationary policy.
3

---

Published as a conference paper at ICLR 2026
Complexity parameters We introduce several wroblem-deppnnees parameters characterizing the complexity of constrained average-reward MDPs. The diameter D is == m ming E,,, [aa] where Ts2 is the first hitting time to $2 under The span bound of the bias function is H := max, ||A|| with [ellspan == max, v(s) - ming v(s), capturing cumulative reward range and long-term difficulty. We also introduce the transient time parameter B. Let II be the set of stationary deterministic policies. For E II, define recurrent states R and transient states T = =S) RD under Pa. and let TR- = inf( 2 0 S. E } be the first hitting time to a recurrent state. An MDP satisfies the bounded transient time properly with parameter B if IE [TR=] S B for all π E II and 8 E S, ensuring uniformly bounded time in transient states. Finally, the Slater constant is < :: max; P. (s) (Ding al., 2021; Bai et al., 2021), measuring the feasibility margin and how difficult it is to satisfy the constraint.
Blackwellooptimal policy policy it is Blackwell-optimal if there exists some discount factor y (0, 1) such that for all 7 2 5 we have V. > V. for all policies æ. Henceforth we let x² denote some fixed Blackwell-optimal policy, which is guaranteed to exist when S and A are finite (Puterman, 2014). We define the optimal gain p* E TRS by (0((s) = sup, pa (s) and note that we have p" = p" For all E S, p" (s) max PeaP", or equivalently p" (s) 2 Papp" for all policies æ (and this maximum is achieved by π*). We also define h²* hT (and we note that this definition does not depend on which Blackwell-optimal x² is used, if there are multiple). For all E S, p² and h** satisfy p" p'r(s) + (s) maxae APp.""""""" Tsa + Psah", known as the (unmodified) Bellman equation.
Learning framework For clarity of exposition, we assume that the reward functions and c are known, while the transition dynamics P are unknown and must be learned. This assumption does not affect the leading- -rder sample complexity, as estimating rewards is generally easier than estimating the transition matrix (Azar et al., 2013; Sidford al., 2018). We further assume access to generative model (simulator), which allows the agent to draw samples from P(- a) for any state-action pair (8, a). Under this setting, our objective is to characterize the sample complexity required to compute an approximately optimal policy स for the CAMDP M. Given a desired accuracy level e >> 0, we consider two distinct notions of settings:
Relaxed feasibility We require the returned policy गे to achieve near-optimal reward, allowing for small violation of the constraint. Formally, we seek such that:
(s) 2 (s) -,, and (=(s) 2 b-e.
(2)
Strict feasibility We require Å to achieve near-optimal reward while exactly satisfying the constraint, ie., zero constraint violation:
(x) (s) s, and (s) 2 b.
In the following sections, we describe a general model-based algorithm that can handle both the relaxed and strict feasibility settings, and we instantiate appropriately for each case.
3 METHODOLOGY
We will use a model-based approach for achieving the objectives in Eq. (2) and Eq. (3). In particular, for each (s, a) pair, we collect N independent samples from P(-|s, a) and form empirical transition matrix P such that ((s'|ssa) transitions from (s,a) to s'. These estimated transition probabilities are used to form series of empirical discounted MDPs, the result of which will be used as the near optimal solution for a series of corresponding AMDPs. In particular. for each E S and A, we define the perturbed rewards (p,ss a) == r(s, a) + Z(s, a) where ((s a) ~ 2100 w] are i.i.d. uniform random variables and we set other parameters, such as E B + H, 7 the empirical AMDPs. Finally, compared to Eq. (1), we will require solving the CAMDP with constraint right-hand side equal to b' Note that setting b' < b corresponds to loosening the constraint, while b' > b corresponds to tightening the constraint. This completes the specification of a series of empirical AMDPs (M., } that are defined by the tuple (S, AA, P. + d s). Furthermore, will compute the optimal policy for the empirical CAMDP M introduced by the generative model as follows:
N(s'Is.e) where (68'|s, a) is the number of samples that have N
Sopt and w (1 7)E/6 to specify
4r
f* E arg max p7, (s) s.t. p.). 2
4

---

Published as a conference paper at ICLR 2026
Algorithm 1: Model-based Algorithm for CAMDPs with Generative Model
Input:
S (state space), .A (action space), r (rewards), c (constraint rewards), Ç (Slater constant), N (number of samples), D' (constraint RHS), U (projection upper bound),e, (epsilon-net resolution), T (number of iterations), Ag = 0 (initialization), Cupt (target accuracy), y (discount factor).
For each (s, a) E S x A, collect n samples S s,a...., S from P(-|s,a)
Form P: P(s'|s,, ss a) = -;= 1(5 = s'}; Vs' E S.
Set discount factor 7 = 4[++H]
Perturb the rewards to form (p(s, a) r(s a) + ((s a) where ((s Un)
Form the epsilon-net A = {0, c, ....... U}.
for t <- 0 to T do
Update the Blackwell-optime policy at by solving the empirical unconstrained AMDP (Prr, + Açc).
Update the dual variable:de41 RA [Po,y [de 17 (p. -b]]].
end for
11 Output the mixture policy:i = + Ei= nr.
We will require solving Eq. (4) using a specific primal-dual approach that we outline next. Using this algorithm enables us to prove optimal sample complexity bounds under both relaxed and strict feasibility.
First, observe that Eq. (4) can be written an equivalent saddle-point problem max, minx>0 (x) + X (s) - U)], where E R corresponds to the Lagrange multiplier for the constraint. The solution this saddle-poin soille-pointtti problem is x*) where A* is the optimal policy for M' and X is the optimal Lagrange multiplier. We solve the above saddle-poin problem iteratively, by alternatively updating the policy (primal variable) and the Lagrange multiplier (dual variable). If is the total number of iterations of the primal-dua algorithm, we define म and X to be the primal and dual iterates for E [2] = (I...., The primal update at iteration t given as:
n. = arg max pr, + Xepo arg max P.
Hence, iteration t of the algorithm requires solving an unconstrained MDP with reward equal to Tp + czc. This can be done using any black-box MDP solver such as policy iteration. The algorithm updates the Lagrange multipliers using a gradient descent step and requires projecting. In particular, the dual variables are projected onto the [0. U] interval, where U is chosen to be an upper-bound on [*%
The dual update at iteration / is given as:
A RA P 0. [A: 1n (p. 8']]
(6)
where Pooui||l] [A] arg pijoe | p projects À onto the [0, UJ interval. Finally, r in Eq. (6) corresponds to the step-size for the gradient descent update. The above primal-dual updates are similar to the dual-descent algorithm proposed in Vaswani et al. (Vaswani et al., 2022). The pseudo-code summarizing the entire model-based algorithm is given in Algorithm I. We note that although Algorithm requires the knowledge of Ç, this is not essential and we can instead estimate of Ç. Next, show that the primal-dual updates in Algorithm can be used to solve a reference CAMDP. Specifically, we prove the following theorem that bounds the average optimality gap (in the reward value function) and constraint violation for the mixture policy returned by Algorithm 1.
Theorem 1 (Guarantees for the primal-dual algorithm). For a target eттоr Eopt
> 0, consider the -ー
primal-dual updates given in Eq. (5)-Eq. (6) with parameters U > |\* T
U2 +
Spp (U-A*) and 17 VT then the resulting mixture policy म Σ ne satisfies
U
E
p (s) 2 PTp (s)
Eopt and (= > b' Eopt.
5

---

Published as a conference paper at ICLR 2026
Hence, with T that of the optimal empirical policy #", while violating the constraint by at most Eoge- Hence, with sufficient number of iterations T. we use the above primal-dual algorithm to approximately solve the problem in Eq. (4). In order to completely instantiate the primal-dual algorithm, we require setting U > | We will subsequently do this for the relaxed and strict feasibility settings in Section 4.
O((emp), the algorithm outputs policy स that achieves reward Eopt close to
4 UPPER-BOUND UNDER RELAXED FEASIBILITY
In order to achieve the objective in Eq. (2) for a target error E > 0, we require setting N 35 and w = s(2-1), This completely specifies the empirical CMDP A/ and the problem Eq. (4). In order to specify the primal-dual algorithm, we set U O (1/s (1-7)),
Ô
SA(B+H) 8' e²
8
é = 0 ( 7)) T' = (4/(1>)²=") and y = T)+ With these choices, we prove the following theorem in Appendix B and provide proof sketch below.
Exp
Theorem 2. For a fixed E (0, 1), E (0, 1) and a general CAMDP, suppose the corresponding
AMDPs (P.r) and (P,c) c) have bias functions bound H. and satisfy the bounded transient time
assumption with parameter B. Algorithm with N Ô (A(B+H)) samples, R b 3e
w ماااك U = O (1-x)) - O (s² 7)) T = O (4/(1)))+))) and yy = T[+HH
Cxn
returns policy स that satisfies the objective in Eq. (2) with probability at least 1 - 45.
Proof Sketch: We prove the result for a general primal-dual error E < and V/ = 5-5 and subsequently specify Eup and hence 6', In Lemma 9 (proved in Appendix B), we show that if the constraint value functions are sufficiently concentrated (the empirical value function is close to the ground truth value function) for both the optimal policy n² in M and the mixture policy A returned by Algorithm 1, i.e.,
2
le. (s) S E Eopt
po (s) p.. (s)
E opt
(7)
2
2
then (i) policy á violates the constraint in M by at most i.e., pe (8) 2 h-c, e, and (ii) its suboptimality in M (compared to π be decomposed as:
pf (s) p (s) 2w Eapt PE, (s) PT (s) + (s p.. (s)
(8)
In order to instantiate the primal-dual algorithm, we require concentration result for policy T that maximizes the constraint value function, i.e. if म. = arg max pf (s), then we require
p p7) E E Case 1 of Lemma (proved in Appendix A), we show that if this
(e+t With these results in hand, we can instantiate all the algorithm parameters except N (the number of samples required for each state-action pair). In particular, we set E.qs & and hence b' = b - g and
concentration result holds, then can upper-bound the optimal dual variable X-| by 2(++w)
35
w = =(1-?) < 1. Setting U = 5e (1-7) ensures that the U > [X*| condition required by Theorem 1 holds. To guarantee that the primal-dual algorithm outputs an ş-approximate policy, we use Theo-
32
8
rem 1 to set T 0 (-- iterations and Ej (=2 (1) Eq. (8) can then be simplified as,
of (8) (s) - pf (8) 2
p.
(s) ,.. (s) (s, - -00ppP...0 (s)
Putting everything together, in order to guarantee an e-reward suboptimality for म,, we require that:
5z
35 : | (s) P.. (s) S 8
3s
p p : (s) S
(p:)ss -
<
8
p., (s) p., (s)
p.. p.
(9)
We control such concentration terms for both the constraint and reward value functions in Appendix B, and bound the terms in Eq. (9). In particular, prove that for fixed E (0, 1/1 -/) using

---

Published as a conference paper at ICLR 2026
N 2 120 - 2²
samples ensures that the statements in Eq. (9) hold with probability 1 - 46.
This guarantees that PT (s) (s) S and P= 26
UPPER-BOUND UNDER STRICT FEASIBILITY
Unlike Section 4, since the strict feasibility setting does not allow any constraint violations, it necessitates using stricter constraint the empirical CMDP to account for the estimation error in the transition probabilities. Algorithmicllly, we require setting '' > b. Specifically, in order to
achieve the objective in Eq. (3) for target error > O, we require setting N = (S((+H))
e²c²
b+ =(1-7)6 and =(2->), This completely specifies the empirical CMDP NY and the problem in Eq. (4). To specify the primal-dual algorithm, set U 4(1+w)
20
<(1->)) E O - (==((1-))$²)
T = O (4((11)) and 7 = 1 Fun ाB.H) With these choices, we prove the following theorem in Appendix C, and provide proof sketch below.
Theorem 3. For a fixed e E 10,1/1-)) and (0, 1), Algorithm 1, with 6 (A(B+H) 401+)) <(1->) 5 O (cc((1))(3)) (1/-
c²5²
samples, b' = b+ <(1-7){ w <(1->)
U U
10
and Cape 1 46.
H) returns policy म that satisfies the objective in Eq. (3), with probability at least
Proof Sketch: We prove the result for general D' b for >> O and primal-dual error Eapt < 4, and subsequently specify A (and hence 1/) and Eapt- In Lemma 10 (proved in Appendix C), prove that if the constraint value functions are sufficiently concentrated (the empirical value function is close to the ground truth value function) for both the optimal policy x in M and the mixture policy f returned by Algorithm i.c. if
p. (s) pf (s) - Eope
De (s) P (s)
SA S
(10)
then (i) policy satisfies the constraint in M i.e. (3) 2 b, and (ii) its suboptimality in M (compared to π ") can be decomposed as:
p.: (s) p² (s) S 2w + Egp + 21|211 + (s) pT (s) (s) In order upper-bound [A*), we require concentration result for policy TH arg max p
(s) - p., (s)
(11)
that maximizes the constraint value function. In particular, we require A (0. and
- A. A. In Case 2 of Lemma 6 (proved in Appendix A), we show that if this concentration result holds, then we can upper-bound the optimal dual variable [ by 2(1+w) ((1-7))
Pe (s) p:
Using the above bounds to simplify Eq. (11),
(s) Df 1-7
2w
+ Eop
4A(1 + w) <(1 7)
Dr (s) + +10000,0000 pf, (8)
or, (s)
With these results in hand, we can instantiate all the algorithm parameters except N (the number of samples required for each ataten pair). In particular, we set A {1 {, Eqps = (1-7)5 < 5. and w = s(1-v) 1. We set U マाा for the primal-dual algorithm, ensuring 200
10
that the U > | condition required by Theorem 1 holds. In order to guarantee that the primal-dual algorithm outputs an =(1=7)5 approximate policy, we use Theorem I to set T = O (,-न)रष
200
iterations and = 0 (s2 22).
With these values, we can further simplify Eq. (11),
of (s) (s) < 35
10 (s) Dr, (s) + p (s) pr, (s)
7

---

Published as a conference paper at ICLR 2026
Putting everything together, in order to guarantee e-reward suboptimality for ft, require the following concentration results hold for A s(1->)5
40
4A
19A A: po (6) Po (s) - 5
(oE(s) - (+)) v /7 - Rr (s) - pr (8) Pr.
Pe (8)
Pe (+)
(s)
(12)
We control such concentration terms for both the constraint and reward value functions in Appendix C, and bound the terms Eq. (12). In partieular, we prove that for fixed & (0, 1/1-sJ. using
N 2
SA(B+H) ensures that the statements in Eq. (12) hold with probability 1 - 46. This PC
guarantees that Pf (s) P (s) S and P. (s) 2
LOWER-BOUND FOR WEAKLY COMMUNICATING CAMDPS
Theorem 4 (Lower-bound for communicating CAMDP). For any sufficiently small s, any sufficiently large S, A, and any D 2 maxfc} (where c1, C2 2 0 is some universal constant), for any algorithm promising return an 24
E opttimll policy with probability at least on any communicating CAMDP problem, there is CAMDP such that the expected total samples on all
state-action pairs, when running this algorithm, is at least 52 SAH 22
X
Figure 1: A Hard Communicating CAMDP
Figure 2: Component Communi- cating CAMDP.
when A 5, 19.
Proof Sketch: We construct family of hard CAMDP instances with parameters S, A, and diameter D. Define A' == A --1 1, D' == D//8 and K = [S/4], and assume standard bounds: A 2 3. 8 S 1/16, D 2 max (oo 163.
We first design primitive component MDP with three states (x, (I) each having A' actions partitioned into subsets according to transition and reward structure (Figure 2). These components are embedded the leaves of an A' -'-ary tree with S - -3 internal nodes and depth at most [log S + 1. The full MDP Mo (Figure 1) connects components via deterministic transitions with diameter bounded by D. A collection of instances (Mr.} is constructed by perturbing action rewards at selected Ja states. Optimal policies must distinguish between actions 01 and dj at these states to satisfy the constraint. The divergence in occupancy measures under different instances implies statistical gap. This separation in policy behavior across instances will be used to derive lower bound. This separation arises from the amplification effect of the constraint reward c, which is necessary to ensure feasibility with respect to the objective defined in Eq. (1).
Finally, applying Fano's method Wainwright (2019) yields a minimax lower bound of Ω
which translates for full proof.
SAH 6<
under the bound H < D (Bartlett & Tewari, 2009). See Appendix G
8

---

Published as a conference paper at ICLR 2026
7 LOWER-BOUND FOR GENERAL CAMDPS
Theorem 5 (Lower-bound for general CAMDP). For any sufficiently small e, 6, any sufficiently large S, A, for any algorithm promising return an & -pptimal policy with probability at least & on any communicating CAMDP problem, there is a CAMDP such that the expected total samples on all state-action pairs, when running this algorithm, is at least 52 (A
226²
4
c b C
2(b=(-e()
1-26C
29
2
p=
p 20
0
p-1- A
1+25
3
5
0
c= 0
r= 0
c=b+C
1-2c5
Figure 3: A Component MDP Used in the Hard Instance for CAMDP.
Proof Sketch: To establish the lower bound, we construct a family of hard instances in which achieving E /224-average optimality requires significantly different policy behaviors across carefully designed environments. In particular, we show that a policy must choose action a = 1 in designated subset of states with occupancy measure at most 2/3 in one instance, while the same action must be selected with occupancy measure at least 2/3 in another. This separation in policy behavior across instances will be used to derive lower bound. This separation arises from the amplification effect of the constraint reward which is necessary to ensure feasibility with respect to the objective defined Eq. (1). The design of our hard instance is motivated by the construction used for average-reward MDPs in Zurek & Chen (2024). Finally, applying Fano's incquality Wainwright (2019) to these
instances yields lower bound on the sample complexity of ② SAB
Finally, by combining this
p(
result with Theorem 4, we obtain the general lower bound for weakly communicating CAMDPs:
á SA(B+H) See Appendix F for full proof.
8 CONCLUSION
In conclusion, we establish the first minimax-optimal sample complexity bounds for learning
in CAMDPs under a generative model. Our algorithm operates under both relaxed and strict feasibility regimes, achieving tight upper bounds of (S((++)) and Ô
(SA(++
respectively. e²ç²
22
Complementing these results, we derive matching lower bound of á (S((+H)) for the strict
e²ç²
feasibility setting, together with specialized lower bound of Ô SAH 2ACT
for the class of weakly
communicating CAMDPs. Taken together, these results constitute the first alignment of upper and lower bounds in all key problem parameters namely, the span bound of the bias function H, the transient time bound B, and the target accuracy s. Our analysis therefore not only resolves the minimax sample complexity of CAMDPs for the first time, but also sheds new light on the fundamental complexity of constrained average-reward reinforcement learning, tightly connecting it the structural properties of average-rewart MDPs.

---

Published as a conference paper at ICLR 2026
9 ACKNOWLEDGEMENTS
The research of Xudong Li was supported in part by the National Key R&D Program of China [Grant 0023YFA1009300 and the National Natural Science Foundation of China [Grants 12271107 and 12531014].
REFERENCES
Alekh Agarwal, Nan Jiang, Sham M. Kakade, and Wen Sun. Reinforcement Learning: Theory and Algorithms. CS Dept., University of Washington, 2019. URL https: htttps://ritheorybbos.
g github.. 1o/. Version 1, October 27, 2019.
Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with a generative model is minimax optimal. In Conference on Learning Theory, pp. 67-83. PMLR, 2020.
Eitan Altman. Constrained Markov Decision Processes, volume 7. CRC Press, 1999.
Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J. Kappen. Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model. Machine Learning, 91 (3):325 349, 2013, doi: 10.1007/510994-13-55366 URL https: http:::://doooooooo http:///o...ooo.../00/0 110994-013-53633
Qinbo Bai, Amrit Singh Bedi, Mridul Agarwal, Alec Koppel, and Vaneet Aggarwal. Achieving zero constraint violation for constrained reinforcement learning via primal-dual approach. arXiv preprint arXiv:2 (0t.::/0090033222 2021.
Qinbo Bai, Washim Uddin Mondal, and Vaneet Aggarwal. Learning general parameterized policies for infinite horizon average reward constrained MDPs via primal-dual policy gra- dient algorithm. ume 37, 2024. URL htttttts//ppee c4 c46c759677 2ww.///00eacceeeeeeeee2222eaaae.
Advances in Neural Information Processing Systems (NeurIPS), vol- nips oc wttprrttlleespppeeeeeeeee
Paper- wonferonceeeepcccooccooo
Peter Bartlett and Ambuj Tewari. Regal: regularization based algorithm for reinforcement learning in weakly communicating MDPs. In Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence (UAI), pp. 35 42, Arlington, Virginia, USA, 2009, AUAI Press. URL
https: arxivv.vvvvvv org/ abs 120..2661..11.1111
Vivek Borkar and Rahul Jain. constroent Markov decision processes. IEEE Transactions on Automatic Control, (9(9)225442277) 2014.
Vivek S Borkar. An critic algorithm for constrained Markov decision processes. Systems & control letters, 54(3):207-213, 2005.
Kianté Brantley, Miroslav Dudik, Thodoris Lykouris, Sobhan Miryoosefi, Max Simchowitz, Alcksan- drs Slivkins, and Wen Sun. Constrained episodic reinforcement learning in concave-convex and knapsack settings. arXiv preprint arXiv:2006. 05051, 2020.
Chiara Buratti, Andrea Conti, Davide Dardari, and Roberto Verdone. An overview on wireless sensor networks technology and evolution. Sensors, 99))68699666 6896, 2009.
Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo Jovanovic. Provably efficient safe exploration via primal-dual policy optimization. International Conference on Artificial Intelligence and Statistics, pp. 3304 3312. PMLR, 2021.
Yonathan Efroni, Shie Mannor, and Matteo Pirotta. arXiv preprint arXiv:2003.02/88 2020.
in constrained MDPs.
Ather Gattami, Qinbo Bai, and Vaneet Aggarwal. Reinforcement learning for constrained Markov decision processes. In International Conference on Artificial Intelligence and Statistics, pp. 2656-2664. PMLR, 2021.
10

---

Published as a conference paper at ICLR 2026
Aria HasanzadeZZnuuzy Dileep M. Kalathil, and Srinivas Shakkottai. Model-based reinforcement learning for infinite-horizon discounted constrained Markov decision processes. In Zhi-Huu Zhou (ed.), Proceedings of the Thirtieth International Joint Conference Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, pp. 2519-2525. ijcai.org, 2021.
D. Julian, Mung Chiang, D. O' D'Niil,, and S. Boyd. Qos and faimess constrained convex optimization of resource allocation for wireless cellular and ad hoc networks. In Seereeddins.Twwenyy Annual Joint Conference of the IEEE Computer and Communications Societies, volume 2, pp.
477-486, 2002. doi: 10.1 10900N0C.....0022...... 1019292..
Sham Machandranath Kakade. On the sample complexity of reinforcement learning. University of London, University College London (United Kingdom), 2003.
Krishna Chaitanya Kalagarla, Rahul Jain, and Pierluigi Nuzzo. A sample-efficiett algorithm for episodic finite-hore horizonn MDP with constraints. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI, pp. 8030-8037. AAAI Press, 2021.
Michael Kearns and Satinder Singh. Finite-sample convergence rates for Q-learning and indirect algorithms. Advances in neural information processing systems, pp. 996-1002, 1999.
Sobhan Miryoosefi and Chi Jin. A simple reward-fres approach to constrained reinforeement learning. In International Conference on Machine Learning, pp. 15666-15698, PMLR, 2022.
Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(75500)559--333 2015.
Long Ouyang, Jeffrey Wu, Xu Jiang. Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feed- back. In S. Koyejo. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Ad- vances in Neural Information Processing Systems, volume 35, pp. 27730-27744, Curran Asso- ciates, Inc., 2022. URL httpppss//prrcceeenggggg.. neur ec httpee//ppppeeeeeeeeeeeeeeeeeeee files/ wtt.s/feaeeeee////eeee/era 2022/file /btbbbleeee
wtw.p//ooooee.eo.....o.ooo.ppppp Paperrre-ePpper-CCofeeeeeeeee pdf..
Santiago Paternain, Luiz FO Chamon, Miguel Calvo-Fullana, and Alejandro Ribeiro. Constrained reinforcement learning has zero duality gap. arXiv preprint arXiv: 2019.
Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John
Wiley & Sons, 2014. ISBN 978-1-118-62558
Shuang Qiu, Xiaohan Wei, Zhuoran Yang. Jieping Ye, and Zhaoran Wang. Up- per confidence primal-dual reinforcement learning for cMDP with adversarial loss. In Advances in Neural Information Processing Systems, volume 33, 2020. URL
https: http:///peeeiiiieeere.p..ppcpppp ae9529 a29526622771T6555111c222262333
Abstractt....................... html.
Andrew J Schaefer, Matthew D Bailey, Steven M Shechter, and Mark S Roberts. Modeling medical treatment using Markov decision processes. In Operations research and health care, pp. 593-612. Springer, 2005.
Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang Mingchuan Zhang. Y. K. Li, Y. Wu, and Daya Guo. Deepseekmath: Pushing the limits of mathematical reasoning in open language models, 2024. URL /tattps://axiv.... org. abs/ 2402. 03300.
Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving Markov decision processes with a generative model. In Advances in Neural Information Processing Systems, volume 31. Curran Asso- ciates, Inc., 2018 URL https: httppp/:////cceeeeen//eeeo neurips hww../pp.cccppppee/22..3. /hahhhhhhhhhhh/// 2eceee44aaaaeeeeaaaeeeee44466663
html.
11

---

Published as a conference paper at ICLR 2026
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of Go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, USA, 1998. ISBN 978-0262193986. URL net/book/the-BBe book. html.
Jie Tan, Tingnan Zhang, Erwin Coumans, Atil Iscen, Yunfei Bai, Danijar Hafner, Steven Bohez, and Vincent Vanhoucke. Sim-to-real: Learning agile locomotion for quadruped robots. arXiv preprint 1rXiv:1804. /0332, 2018.
Sharan Vaswani, Lin Yang, and Csaba Szepesvári. Near-optimal sample complexity bounds for constrained MDPs. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, pp. 3110-1122, October 2022. URL https: / /aa.aaivvv.o...................a abs 2206606276
Martin J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint.
Cambridge University Press, 1 edition, 2019. ISBN 978-1-108-62777-1.
doi:
10.101779781108627771. URL https: // htwp:/wwwtbrttttt/t/tttt//wt.t idge wtt.:/e.....g.oooooooo.....
Jinghan Wang, Mengdi Wang, and Lin F. Yang. Near sample-optimal reduction- policy learning
for average reward MDP. arXiv preprint arXiv:2212.00603 2022. URL http:::///axvvooooooe
abs/ 22122 60603.
Honghao Wei, Xin Liu, and Lei Ying. A provably-efficient model-free algorithm for constrained Markov decision processes. arXiv preprint arXiv:2106.01577, 2021.
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pp. 6995-7004. PMLR, 09-15 Jun 2019, URL https: hwtph:ttspppcceeeeeeeeeee /ttpe////cccceceesspoooooo www.mpress.//111. yangl 9b. html.
Tiancheng Yu, Yi Tian, Jingzhao Zhang, and Suvrit Sra. Provably efficient algorithms for multi- objective competitive RL. In International Conference on Machine Learning, pp. 12167-12176. PMLR, 2021.
Andy Zeng, Shuran Song, Johnny Lee, Alberto Rodriguez, and Thomas Funkhouser. Tossingbot: Learning to throw arbitrary objects with residual physics. IEEE Transactions on Robotics, 36(4): 1307-1319, 2020.
Liyuan Zheng and Lillian Ratliff. Constrained upper confidence reinforcement learning. In Learning for Dynamics and Control, pp. 620-629. PMLR, 2020.
Matthew Zurek and Yudong Chen. weakly communicating and general average reward MDPs.
Span-based optimal sample complexity for
Advances in
Neural Information Processing Systems (NeurIPS). volume 37, 2024. URL www.uuisssccppaaaeo
https:://prceee www.gss..er....... cctp.per..pp..eeeeeeeeeee httpe///ssseaapee//////iii 3acbe9dc3a1leBd4ee - Corrr==aaae--Coffeeeeee....p
12

---

Published as a conference paper at ICLR 2026
A PROOFS FOR PRIMAL-DUAL ALGORITHM
Theorem (Guarantees for the primal-dual algorithm). For a target error Eapt > consider the
primal-dual updates given Eq. (5)-Eq. (6) with parameters > |^7 T
1
1 + -o-x
q
U Cupt (U-X", and 11 VT then the resulting mixture policy म 2t= Te satisfies
60
Pr (9) 2 Pr, (s)
Eupt and p 2 b' Eppt
Proof. We will define the dual regret w.r.t as the following quantity:
T-1 (A,
(13)
t=
Using the primal update in Eq. (5), for any n.
(s) + Xep (s) pT, + Asp%(s).
Substituting x = A², we have,
# Pr, (8) - (s) S de - p.)
Since A" is solution to the CAMDP, p:: 2 b', we get
Pry (s)
ā (s) - Ae Pe (s) 6']. Prp
(14)
Starting from the definition of the dual regret in Eq. (13), using Eq. (14) and dividing by T gives
T
I + Σ o. t=
< RA T) T
(r) (8)
Prp
pf; (s)
(15)
T
1=0
Recall that A = - Σ ne. Then, by the definition of this 'mixture', we have
TT- (s)
=
P7, (5) and + 2. pet (s) = (s). Combining this with the last inequality, we get
- p., (s) + - (()) - (A,)) T
(16)
Lemma 7 show that the following inequality holds for any A E [0,0]:
(A, T -t 2E
+ UUT.
(17)
2U
This combined with the previous inequality (and the "right" choice of T, the number of updates) gives the desired bounds. In particular, for the reward optimality gap, since À = 0 e [0,U],
0T, (s) VT o + 2E
U VT
36 <T
U
(since U)
20
2
VT
For the constraint violation, there are two cases. The first case when D' p² (s) S In this case, also holds that b' Eape p (+) S 0, which is what we wanted to show. The second case is when b' p (p) > 0. In this case, using the notation [x]+ = max( 0} and Lemma 6, we have
pr, (6) + [U (+)] < (U,()))
[0 (s)
(18)
T
13

---

Published as a conference paper at ICLR 2026
Because by assumption it holds that U > X², Lemma 8 is applicable and gives that
(U, T(U -²)
[8' - (3)]
(19)
Hence, since U E [0, U). combining the above display with Eq. (19) gives
1 - [c) s 6 -E(( S VT +
U
(20)
20 (U-
(U -U-x)) -T)
3a
U
VT
(since < U)
2(U x+)
(U (U-X
Now, set such that the second term in both quantities is bounded from above by Eopt/2. This gives
To
U2
1
1 (U - x+)
(21)
ops
Now, set Ej such that the first term in both quantities is also bounded from above by Eape For this, choose
2g (U x*)
6U
With these values, the algorithm ensures that
Prg (a)
Prp (8)
S Sppt
and D' - po (s) S Cott-
(22)
To further ensure the success of our primal-dual algorithm, we need to make sure is Sounded.So we obtains Lemma 6 as follows.
Lemma (Bounding the dual variable). The objective Eq. (4) satisfies strong duality. Deftning
nेa arg max Pe (s). We consider two cases: (1) If V/ = b è' for gx O and event &
{
(x)
< 2 holds, then X < 2((+w)) and (2) IfV = b + A for ArA E (0. and event
Eg
--= =- (s) .c=
pe
- }} holds, then X < 2(1+2)
Proof. Writing the empirical CAMDP in Eq. (4) in its Lagrangian form. D., (s) max min 07, (s)+ + (s) b']
X20
Using the linear programming formulation of CMDPs in terms of the state-occupancy measures μ. we know that both the objective and the constraint are linear functions of and strong duality holds w.r. μ. Since y and ı have one-one mapping, we can switch the min and the max (Paternain et al., 2019), implying.
min max Pr, (s) + Alp. (s) - b7 X
Since X the optimal dual variable for the empirical CMDP in Eq. (4),
max PT, (s) X" [PT b']
x
Define T. = arg max PT (s) and मे = arg max PT (s)
2 ( (s) X po (s) - b9]
(x) + x [ th (s) - -z (x)) + (p)= bb) -)+ + (b - [6-b)]
By definition, - vC: (s) b
#
+X"
[ pe (s) po. (s)) + (p= (s) p.. (s) + + + (b -b))
14

---

Published as a conference paper at ICLR 2026
By definition of t.. 0o (s) p (s) 20 0
0 (o) Prp + X² | + (b 1)) - (s)
- pE- (+)
1) = b E' for E' > 0. Hence,
0r, (8) 2 Pry (8) + + {s+ - (x) -p (s)
#
If the event & holds, Pe (s) - Pe
r (b)
S implying, pe (s) - pē= (s) < << 5. then,
# 2 Pry (8) +
2
2 p (s) - piy [s]] 5
w(1+w)
X < 5
e¹
2) 6f b+ A for A (0.$) Hence,
Prp (s) 2 p (s) +\ | - - pe (s) - p.. (s)
+1**
If the event & holds,
pe (s) x: (0) S f for A S. then,
2 p (s) + {
2
x S p (s) #: p (+) S 2(1 + w)
S
Lemma 7 (Bounding the dual regret). For the dual regret defined in Eq. (13), we have
(*, < 3/2 ot + 2E
+ +UVT.
20
Proof. First, fix an arbitrary x E U). Defining X41 := Plo.oy/1 - (s) - (b)).
So we have,
|A++1 A/ |RA|1441 - A/ A/= = [ X411 + M441 Al S [RAN4+1 M441 + 11441 A|
S + 1N - 2/.
(since IA - RAlA S E for all X E [0, U] because of the epsilon-net.)
Squaring both sides,
D - 212 = =/ + |1t11 - 212 + 25, N1 - A| $ E + 2E + 12 - A12
(since X, X E [0, UJ.
S = + 20 + 1^ - 17 (p= (s) - -b)- - 212 (since projections are non-expansive)
= -² - 2, + 1A - 2/2 - 2ny (h: A) ( (s) - b') + (p. b))
< + 2& + IAe - 2n (Ae x) (0 b') + +r²
where the last inequality follows because b' and the constraint value are in the [0. 1] interval. Rear- ranging and dividing by 2n,, we get
o² 25,U
1 11 A12 + 7
(Ac- - A) (0 (s) b') <
+
2n
2n
2
Summing from = to T - and using the definition of the dual regret,
R (A, ot + 2
T-1
11 - 212 |de41 - x12 + n)
2m
2n
2
t=
Telescoping, bounding Ao Al by U and dropping a negative term gives
e² + 2
U
nT
(d (A T) <T
211
21
2
C Setting 1) VT
(A) < T3/2 o +
22
+ U
UVT
(23)
20
which finishes the proof.
15

---

Published as a conference paper at ICLR 2026
Lemma (Bounding the positive constraint value). For any > X and any & s.t. Pf (8)
(s) + Ci6' Eopt Po. (s)]+ S B, we have [b' Eopt - Pe (s)l+ S с-
Proof. Define v(r) = max+ {x% P: (s) 2 cpp + 7 and note that by definition, v/()
P (s) and that v is decreasing function for its argument.
Let Pi (s) (s) + (s) V Eopt). Then, for any policy s.t. P (s) 2 b' Eopt +
have
Pi x.A'
(b) S max of 'A' (8)
o (s)
(by strong duality)
= (0)
(from above relation)
v(0) -X-= 2 Pi (8) -xX* (s) + + V' Eopt
Non-negative
v(0) - TX 2 (p7 PE(s) 2 - Copt + =())
= T\ S u(0) - ((T).
(24)
Now we choose -(V' Eopt (s))+
(C |1 7 + C
(since 7 S 0)
S v(0) - C
(Eq. (24))
P3 (s) (s) + + (s) -(())
(definition of (0))
,/ (8) (s) + +C( Eppt -p. (5))+ P v(f)
$ 3 + Pf (s) - v(F).
Now let us bound uff):
v(F) = max { p² (s) (5) 2 - Eopt - (b' Eopt - (s))+
max (p (8) (x) 2 (s))
(tightening the constraint)
B
( (C-1a) < (b' - Eapt (s)) s
C-
16

---

Published as a conference paper at ICLR 2026
B PROOF OF THEOREM 2
Theorem For a fixed E (0, 1], E (0, and general CAMDP, suppose the corresponding AMDPs (P,r) and c) have bias functions bound H and satisfy the bounded transient time
assumption with parameter B. Algorithm with N = Ô ( (A(B+H)) samples, D' b 3e
w &
=1--21,1000 = O (1-n)) & - (s2(1 ())) T
(1/11))) and 7 = 3(+HH)
Exp
returns policy स that satisfies the objective in Eq. (2) with probability at least - 46.
Proof. We fill the details required for the proof sketch in the main paper. Proceeding according to the proof sketch, we first detail the computation of T and E for the primal-dum algorithm. Recall that
5c (1-1) and Exp 4. Using Theorem we need to set
40
64
1
T
1+ x E²(1 7)3
1+
op (1 - 7)²
(U - x²
Recall that 1
and U 2C. Simplifying.
5e (1-1)
256
[C2 +1]
512
C²
512
256
(1 7)2
e²11 7)2
E²
7)2 25c (1 7))
+ T= 0 (1/6(1-7)))
Using Theorem 1, we need to set El,
Sup (1 7) (U - X*)
=2 - (U X²)
E =² - 7)
6U
960
96
& 0 (s 7)))
For bounding the concentration terms for â in Eq. (9), we first use Lemma 11 to convert them to discounted setting, then use Lemma 13 with U = 5e (1-9), w = <(1-7) and & = =²(1~)² this
32
96
w 6 (1--) O (6* SA²
(1=2)*) and in order satisfy the concentration bounds for â, we
case, 30 8) A/2
require that
N N SA(B+ H)
(
22 We use the Lemma 14 to bound the remaining concentration terms for x² and x.. in Eq. (9). In this
case, for (6) = 72 log 488 Ing(e/1
we require that,
SA(B + H) E2
N 2 Ō
Hence, N 2 (SSAA the bounds Eq. (9) are satisfied, completing the proof.
Lemma 9 (Decomposing the suboptimality). For Vo following conditions are satisfied,
é-Enpt
if (i) Sops E, and (ti) the
1e (s) -0 (s) <
E E
Eopt
(s) (s) De: (5) - Eam
where म. := arg max p: (s), then (a) policy violates the constraint by at most s i.e. p.. 2 b-e
and (b) its optimality gap can be bounded
pT (s) (s) < 2w Eopr pr, (s) p., (s) + (s) p" (s)
Proof. From Theorem we know that,
pz 2 6' Eept - (²(s) 2 P. (s) (5) + -Ex -l(2(ss) (s)) + Exp
17

---

Published as a conference paper at ICLR 2026
Since require á to violate the constraint in the true CMDP by at most require p b From the above equation, a sufficient condition for ensuring this is, (e) Pa (s) + b' - Em 2 b.
meaning that we require
1 (8) - p: (+) - (8' -) - Cape + Plugging in the value of b' that this sufficient condition indeed holds, by assumption that |P - (=)) E-
Let be the solution to Eq. (I). Our next goal is to show that n² is feasible for the constrained
problem in Eq. (4), i.e., P. (s) 2 b'. We have
Pe (s) 2 b = Pe (s) 2 b P. PT (s)
Since we require Pe (s) 2 D, using the above equation, a sufficient condition ensure this
- p0 (s) - p. (s) z b' d'meaning that we require p² (s) - p (s) s b-
Since = Eap we require that
pe (s) pe (s)
Eup.
2
Given that the above statements hold, we can decompose the suboptimality in the reward value function as follows:
pr (s) (8)
p. (s) p (s) + PT, (s) (s)
x5" l0, (s) pr, (8) + Pip (s) Pr, (s) pr, (8) (s)
s T0, (s) pr, (s)] + Ir, (s) pr, (s) + pr, (s) - (s)
(By optimality of 4" and since we have ensured that x² is feasible for Eq. (4))
10, (8) pr (8)] + I0T, (8) P (s)
(5) 0f, (s))
(s) pf (s)] Ip, (s))
10 (s) pr, (s) I (5) P.. (s) p (s) p., (s) p
Perturatiinn Error For perturbation magnitude equal to w, we can bound both perturbation errors by w. Using Theo- rem to bound the primal-dual error by Expt.
Concentration Error
Primal-Dual Ervrr
Consentration Error
Perturbation Error
o (s) pf(s) (s) < 2w + Ecpe 10", (s) pr (s)
(s) Pr, (s)
Conceniration Firor
Concentration Error
18

---

Published as a conference paper at ICLR 2026
C PROOF OF THEOREM 3
Theorem 3. For a fixed E E (0, 1/1->l and (0, 1), Algorithm 1, with N Ö s
c²5²
samples, D' = b+ <(1-7)C w <(1-1) U 401+)) <(1-7) G O (c2 ()) 0 (4/1->))(*²2)
and 7 Sape H( returns policy that satisfies the objective in Eq. (3), with probability at least 1 46.
Proof. We fill the details required for the proof sketch in the main paper. Proceeding according to the proof sketch, first detail the computation of T and 6, for the primal-dual algorithm. Recall that
[( A
s(1-2)< and
Eap
5 Using Theorem I, we need to set
40
4
100
T
1+
1+
op (1
7)2
(U - x1 -2(1-7)²
(U - x
Recall that || C
[[1ー] and = =C.. Simplifying,
400
800
800
16
< (1 7)
[C² +1]
C2
A1 7)2
A - 7)3 <2 7)
800 1600
16
T
= 01/222 00 (11-))))
$² (1 7)4 (² - 7)
Using Theorem we need to set Es,
Lqu 7)² (U X²)
A - ((11~)}(( (U - X*)
A1(1-1))
60
1500'
150
2 22
7)
0 (s² 2² (1- (1-7)*).
150 1600
For bounding the concentration terms for & in Eq. (12), first use Lemma 11 to convert them to discounted setting, then use Lemma 13 with
द1-7プ s(1- and E 150-160m
2² <2 (1-2) In this
10
case, L w)(1=7) 30 =
(=-<"(1--)7 and order to satisfy the concentration bounds for म, we 54"
require that
δ SA(B E2C²
( + H)
We use the Lemma 14 to bound the remaining concentration terms for x² and क. in Eq. (12). In this
case, for (6) = 72 log 4S [og(e/1->)
we require that,
SA(B + 11)
E²C2
Hence, N 2 Ô
SA(B+H) 2²
the bounds in Eq. (12) are satisfied, completing the proof.
Lemma 10 (Decomposing the suboptimality). For a fixed A 0 and Expt < A. if = b A. then the following conditions are satisfied,
(pE(s) - pº (s)] s E Pe (8) pe (s) SA
then (a) policy & satisfies the constraint i.e. (x) 2 and (b) its optimality gap can be bounded as:
P (s) (s) S 2w + Eapr 24X* + pT. PT (s) + p0,
pf, (s)
Proof. Compared to Eq. (4), we define a slightly modified CMDP problem by changing the constraint RHS to 6" for some 6" to be specified later. We denote its corresponding optimal policy as म*. In particular,
#* E arg max PT, (s) s.l. (s) 8"
(25)
From Theorem 1, we know that, e (s) 2 b'
Exp (=)) > (s() (3) 6 - Eux -p((((s) -p. (s) + Eup.
19

---

Published as a conference paper at ICLR 2026
Since we require to satisfy the constraint in the true CMDP, we require (3 2 From the above equation, sufficient condition for ensuring this is,
(s) p. [s) + Eup 2
meaning that we require (x) Po (s) S (b' Sage-
In the subsequent analysis, we will require π to be feasible for the constrained problem Eq, (25).
This implies that we require Pe (s) 2 1/" Since the solution Eq. (1), we know that,
Pe (s) 26
P (8) 2 p (s) P. (s)
Since require it (s) 2 8", using the above equation, sufficient condition ensure this is
b- p0- (s) Pe (s) ス b" meaning that we require p (s) - (s) - b". Hence we require the following statements hold:
(P) - p. (s) (b' b) Eupt pe (s) P. (s) b 6"
Given that the above statements hold, we can decompose the suboptimality in the reward value function as follows:
pr (s) (5) = p.: (s) pr, (s) + pr - (s)
10_ (8) "h (s)] + 10,, (8) 07 [
Ip_ (s) p. (0, (s)] + Ip,, (s) p., (s) + P P5
(By optimality of #* and since we have ensured that nT feasible for Eq. (25))
10 (s) p7 (5)] + (s) pr, (s)] (s)]
D (s) pr (s)] + pr (s) (s)
i0, (s) -. (s)] + 10,, 07, (s) p (s) - pr, (s)] + p (s) (s)
Lo (s) prp (s)] + 10,, (s) - -0,
(s) p (s) p., (s)] 1 (s) p., (s)
p., (s) (6)
p (8) p7p (8)] + 10F, (8) Pr, (s)
(8) 1r (8)
(8) 1 (8)
Perturbation
Concentration Error
Scositivity Error
Primal-Dual Error
(5) p. (s)++ p
Concentration Error
Perturbation Error
For perturbation magnitude equal to we can bound both perturbation errors by w. Using Theo- rem to bound the primal-dual error by Expts
2w
Eoge
IP" (s) P., (s) pr PT (s)] (s) (s)
(s)
Sensitivity Error Since = b + and setting 8" = A. we use Lemma 15 to bound the sensitivity error term,
Concentration Eiror
Concentration Enror
07 (s) p. < 2w + Epps + 2AA* + lp" p (s) -
(s) (s) 1o,, (s) P (s)
Concentration Firor
Concentration Frro
With these values of b' and 6", we require the following statements to hold,
p (s) p (s)] < A Eage
Pe (8) Pe (s) A.
20

---

Published as a conference paper at ICLR 2026
D CONCENTRATION PROOFS
Lemma 11 (From AMDP to DMDP). Set 7 = 1 Exge
4B4HY If the concentration error for the
discounted MDP satisfies V| lo - B + H, then it follows that l|p" -0" 1lo0 I Eppt.
Proof. We begin by decomposing the error term:
1p ~0
IV V mo +
VT --
+ +1127
1-10- 00
(26)
The first term in (26) is bounded by assumption:
B + H. The second term can be bounded using Lemma 12, which yields
|V V cl
VT
H.
Similarly, can bound the empirical error between average and discounted setting by
1 p- 2H,,
with only sample complexity independent of c. Combining these bounds, obtain
1-7 11
101 S SB H) + H +H B + 4H.
Now, setting
Eopt
7
4(B + H)
implies that
110" 1=1100 S Eppt.
which concludes the proof.
Lemma 12. We have
1V
p² 10c H.
Proof. We begin by observing that æ satisfies
p" + ht =r + PPhh"
Therefore, it holds that
V = (1-ppa)) Txx
7P- (p= h² Prhh')
-1I-7p pp + (I (I-7Pa) -1 (I (--Pa)) PT)
Since Pap" = =p- we can calculate that
(1 (1->P=) =
x pp
Σn' 21'0"
p"
220
120
It also holds that
(1->P=) (1 P7) = Σ 7 'ppp - Pr)
pl.
1pt+1
120
120
= Px +
(
H1
(27)
t20
and [+1 -=1'==10 matrices, and so it follows that
(7 ((1-11) (1)== E'20 = 11 Therefore (27) is the difference of two stochastic
7P,) -1 (I (I- 1b) 100 H.
21

---

Published as a conference paper at ICLR 2026
Lemma 13 (Theorem 6 of Vaswani al. (2022)). For d (0. S 1 and C(6)
72 log
+6)++t+w) SA log(7/>-)) where 1 -
300|5|1 if N 2 4C
then for it ouiput by Algo- I-7"
(1-7)- co
rithm 1, with probability at least - 8/5,
C())
C(0)
V (s) - (s)
2 V N (1 (13
Vc S
(1-7)3
Lemma 14 (Lemma 7 of Vaswani et al. (2022)). For ô E (0, 1), w S 1 and C²
(.) 4|8] log(e/1 7) if N N I-7 and (6,, N) V (1-7)aN. then with probability
(²(8)
72 log
least
30,
V
(8)
V (8) ry
< 2B( N); V. (6) Ve (b) S N); Vo (6) (x) S B(6, N
E SUPPORTING LEMMAS FOR THE UPPER BOUND
Lemma 15 (Bounding the sensitivity enror). Ifb' = b + A such that,
A E arg max Pf (s) P 2 b+ A
π n" E arg max P (8) P (8) bb,
then the sensitivity error term can be bounded by:
(s) p (s) I A..
Proof. Writing the reference CAMDP in Eq. (4) in its Lagrangian form,
p (s) = max min pf (s) + (s (b + A)
X
min max p. (8) (p (b+ A)]
(By strong duality Lemma 6)
X20
Since X is the optimal dual variable for the empirical CMDP in Eq. (4),
max (T)) + X (s) - (b+ A)]
Pr (8) + (s) (b+ A)
(The relation holds for æ x²
Since P (s) b.
p (8) 2 pf (8) X
pr (s) pf (s) < AA
Since the CAMDP with 1' is less constrained problem than the one in Eq. (4) (with V = b A),
D7 (8) 2 Pf (s). and hence,
p (s) p. (s) < 2AX
Lemma 16 (Bounding the optimal bias function and the transient time). If the AMDPs (P,r) r) and (P,c) c) admit bias functions bound with parameter H and satisfy the bounded transient time assumption with parameter B, then the combined AMDP (P, r Xe), where X is defined in Eq. (6), also satisfee the bounded bias functions assumption with parameter H and the bounded transient time assumption with parameter B, after normalizing the reward values.
Proof. Based on the bounded transient time assumption, for all æ II and s E S, we have E [TR=] S B, where TR- := inf 2 0: E R*). Since the transient time parameter B is determined solely by the transition dynamics of the AMDP and is independent of the reward function, it follows that the combined AMDP (P.r + Ac) also satisfies the bounded transient time assumption.
22

---

Published as a conference paper at ICLR 2026
We now turn to bounding the span of the optimal bias function under the combined reward + Ac. Let x denote the optimal policy for this reward. By linearity of the bias operator with respect to reward and the definition of span, have
C-lim E 7-000
(re+ det - Pr ->pE
1+1 A
span
(|iin
T-1
Σ rr pr )
T Σ
C-lim E 7-00
+ +
C-lim E
P%:
1 X
7
1span
0
span
+ XH
1+
s H,
Lemma 17 (Sample Complexity to Estimate Bias Span). Let H denote the bias-span parameter H max, ||h" Ilspan max (max, h (s) min, h² (8)) Then, under access to a generative model, the quantity H can be estimated to constant-factor accuracy using O(SAD) samples.
Proof. Fix a reference state sn recurrent class of and normalize the bias so that h (sp) For any state 8, consider the trajectory obtained by starting from following and stopping when the chain hits so for the first time. Let T, this hitting time and define the random variable
To
Z. = Σ (r(st, (s:)) p.
==
where P.. is the (state-dependent) average reward vector under n. By standard average-reward theory, have E E[Z.] h"d (s) h-" h=((s)) h² (s).
Each trajectory length T, is at most D in expectation, and every increment r(t, 7 (T&))())))))) (8 is bounded in [-1,1] Thus Z. has magnitude and variance the order of 1 and D22 respectively. To estimate [[22.] up to additive error oH for some fixed small constant a E (0, 1), Bernstein-type concentration inequalities imply that a constant number n, O(1) of independent trajectories starting from suffice: the target accuracy aH is of the same order as the typical size of Z,, only (11) samples are needed obtain constant-factor estimate. Each such trajectory requires Ō(D) environment interactions expectation, so the sample cost per state is O(D).
Repeating this construction for all SA state- state-action pairs) and applying union bound, we obtain an estimator hT such that
max]h=((3 - hT((s) aH
with high probability. Consequently, the empirical bias span A : max, | satisfies | - H < 2aH, and hence
A < (1 + 2a) so Hr a constant-facto upper bound on Hg The total number of environment interactions used is O(SAD).
Lemma 18 (Sample Complexity to Estimate Transient Time Bound). Let be the transient time bound defined as Vn, s, [T'R]] < B, where TR= is the first hitting time to a recurrent state under policy æ. Then, under access to a generative model or an environment where episodes can be reset to any state-action pair, the transient time bound B can be estimated up to constant-facto accuracy using O(SBB) samples.
Proof. To estimate the expected hitting time E. [TR=] from each state under fixed policy sample full trajectories until they reach the recurrent class R" Each trajectory is a random variable T E N with expectation at most B and variance Var(T) O(3)).
23

---

Published as a conference paper at ICLR 2026
To estimate E[T] up additive error ((B), standard concentration inequalities (e.g., Bernstein's inequality) imply that
(5 e2
[3' [ =0(1 Ō(1)
O
trajectories suffice.
Each trajectory requires ( environment interactions in expectation, the sample cost per state- action pair is Ó(B). Summing over all SA state-action pairs yields total sample complexity of
Ö(SAB).
F PROOFS FOR LOWER-BOUS FOR GENERAL CAMDPS
Theorem 5 (Lower-bound for general CAMDP). For any sufficiently small any sufficiently
large S, A, for any algorithm promising to return an 21 optimal policy with probability at least on any communicating CAMDP problem, there is CAMDP such that the expected total samples all state-action pairs, when running this algorithm, is at least 5 (S)(H+B)
e²ç²
4
2(6-(-90)
1-M6
1-266
2B
2
p=
14:2st
20
0
p-1 à
28
3
5
F 0
r= 0 c= b
Figure 4: A Component MDP Used in the Hard Instance for CAMDP.
Proof. We begin by introducing a family of MDP instances Ma- indexed by E f1...., A}. depicted in Figure Fig. 4. In all these instances, states 2, 4,5 are absorbing, while states 0 and are transient. Among them, state distinct actions. Taking action a 1 from state 1 deterministically leads to state 4. For action a = 2, the transition probabilities are defined as P(1 1,2) 1, |1,2) reward and constraint values r and e are shown Figure 4, and are the only quantities that vary across the different instances M... Note that all actions not in state can only lead one state.
the only one with multiple actions, supporting A
P(2 1,2) = P2, and 1- P(1 2, P(2 1, 2). The specific values of P(2 a), P(3 1, a). and the
P(3
In instance Mi, the optimal policy selects action a = 1, achieving an average reward of 1/2. Choosing any other action results a suboptimal average reward of 1-2eC For instances M with a' E (,, A}, the optimal action is a", yielding average reward of 1+2sC, while action a = 1 returns }, and all remaining actions incur a reward 1-2cς In all such cases, the span of the bias function under the optimal policy satisfies || 0. An analogous construction holds for the constraint rewards Furthermore, any action # leads the agent to remain in state 1 for expected B steps before transitioning to either state or 3, thus ensuring that the bounded transient time condition is met with parameter B.
2
24

---

Published as a conference paper at ICLR 2026
We then define set of (4--))57 master MDPs denoted M aa, indexed by s* E {1,... S/6} and a" E {2...., A}. Each master MDP consists of S/6 independent copies of the sub-MDPs described above, which are all connected to initial state. The s"-th sub-MDP is set to be Ma while all remaining sub-MDPs are instantiated as M, To ensure non-overlapping state spaces, the states of the s-th sub-MDP are relabeled 6s, 6s ...... 6s + 5, corresponding states 0, ,....,5 -5 in Figure 4. We also define Mo composed of S/6 independent M1 As a result, each master MDP has exactly S states and A actions, satisfies the bounded transient time condition with parameter B, and possesses an optimal policy with bias span zero.
We further fix the constraint threshold b = _ in the construction of our hard CAMDP instances. Based on the structure depicted in Fig. 4, we directly compute the expected reward and constraint
values as follows: in states of the form 68 + 1, choosing action d1 yields reward r 1 and constraint
2
value c = b- Ç, while selecting any action a E AA } results in reward r = 2 - EÇ and constraint
= b EÇ.
At the special state 6s + 1, the designated optimal action a" yields reward r = 1/ + EÇ, and the corresponding constraint value is given by (b-c=e)((+22)) b ( eC +o
1-2c
Let 8n denote the initial state that connects all branches 6s, and define the following occupancy measures:
No S/6-1 p(su, 6s)
p(s, 6s + 5).
= Σn p( 6s) p(Gs, 6s + 1) p(6s + 1,01).
8/6-1
12
Σ
p(so, Gs) p(6s, 6s + 1). p(6s + L, for e A {ai}.
==0
We now formulate the linear program (LP) for solving the average-reward objective in Mo:
1
max
2 TM
+
112
(28)
2
s.t.
+ #1 + P2 = 1, (b+ () + (b ()1 + (b (b---- (2-(-E())e 2 b.
po: M1, M2 2 0.
The unique optimal solution Eq. (28) is pn 2 111 3, and μ12 0, yielding average reward p" (su) 4.
Next, we aim to show that for any 244 optimal policy, the normalized occupancy μá := 1- satisfy p N Suppose, for contradiction, that μ < 2 The modified LP becomes:
must
1
max
2 5P1 + 2 =( 42
(29)
s.t. No + 11 + 02 1,
1¹ < 3'
(b+ () + (b () + (b- - (b- E() 2 b,
Po: M1, P2 2 0.
direct calculation shows that the optimal reward for Eq. (29) is p(so) = - violates the 24 optimaalitt condition. Therefore, the assumption μ < 3 must be false, and it follows s that any 24 -potimal policy must satisfy p1 2 3-
<5
6: which
2
For CAMDP Ma ,a*, we define the two new occupancy measures:
ng = l22 - p(sa, 6s*) p(6s", 6s* + 1) p(6s" + 1, 1, 14 p(so, 68*) p(6s", 6s* + +1) p(6s* + 1,
25

---

Published as a conference paper at ICLR 2026
We now formulate the LP for solving the average-reward objective in Ma
1
[ <c) 1b ( + Ec us
1
max
2
(30)
(40 + μn + 11 μ43 =
(b mo (b {) + (b - EQ)ug + _b (+ 4eg² + +(e)]uu 2 b,
|4o, 222 13 2 0.
The unique optimal solution to Eq. (30) is μi 1t5- + o(e), p = n2 0. μzs 2-0+e( + d()) --
yielding an average reward p² (50) 1 + $ + 8
35C o(s).
& optimal policy, the normalized occupancy 1 must satisfy Next, we aim to show that for any 27
r $ 5. Suppose, for contradiction, that μ4 > The modified LP becomes:
1 max 2 + 2 <c) 12
1
(2
1
+
Ps
(31)
2
s.t. Po + + 11 + μs = 1,11 >
3
- 4=5² + o{E)]μa 2 b, (b ()H (b - 5) + (b E{) + [b- -5
[40 Ho, 12: M4 2 O.
A direct calculation shows that the optimal reward for Eq. (31) is p(so) = 1 क + ols), which violates the Σ4 optiimaliyy condition. Therefore, the assumption vú must be false, and it follows that any 24 optiimal policy must satisfy p1 S
In short, for any 21 opttimal policy, μ must satisfy p1 S for M and μ 2 3/ for Mo.
So we can use the Fano's method to lower bound the failure probability. We have:
2Ec 1 2
PM 6s* + +1,a") Cat 1
Q1,
B'
2B
:
2B
1 1 2eC 1 1-2a(
PMo ( Gs* + 1,aa) Cat
Q2,
B
2B
2B
where Cat(pi,P2,PP) P2,Pal denotes the categorical distribution with event probabilities p.'s. 's
Now we use Fano's 's method lower bound this failure probability. This is inspired by the proof of lower-bound for AMDP in Zurek & Chen (2024). Choose index J/ uniformly at random from the set J := {I,.... .,. S/6} x {2....,44 A} and suppose that we draw n iid samples = (XI..... Xa) from the master MDP M,; note that under the generative model, each random variable X, represents an (S x A)-by-S transition matrix with exactly one nonzero entry in each row. Letting I(J; X) denote the mutual information between J and X, Fano's inequality yields that the failure probability is lower bounded by
I(J:X) log 2 log((A- (A- 1)5/6)
We can calculate using the fact that the Pt's are i.i.d., the chain rule of mutual information, and the form of the construction that
X);:x) nI(J; X1)
S n max DKI. (PM
PMO
(8 JET
= =nDr Q2). (Q)).
26

---

Published as a conference paper at ICLR 2026
By direct calculation, have
1-2EÇ log
2
+ 1 2
1 2
(xl(11 = 2B
log
1 + 2=
2B
1 2
1 25c - 48c
1 2cC
48
2z,
2B
+ 2
2B
2sc
16=25²
B(1 + (1 28()
32
E $
Therefore the failure probability is at least
32
I(J; Pm) log 2
log 2
log((A - 1)5/6)
log((A A 1)5/6)
32=*5²
2 2 log( (A 1)5/6)
where in the second inequality we assumed and S are at least a sufficiently large constant.
above RHS to be smaller than 1/4, we therefore require n 2 Š2( B Bog((AA) Finally, by combining this
result with Theorem we obtain the general lower bound for general CAMDPs: á (A(B+H))
G PROOFS FOR LOWER-BOUND FOR WEAKLY COMMUNICATING CAMDPS
Theorem 4 (Lower-bound for communicating CAMDP). For any sufficiently small c, 5, any sufficiently large S, A, and any D 2 max o2) (where Cı, C2 2 0 is some universal constant), for any algorithm promising return 24 -optimal policy with probability at least any communicating CAMDP problem, there is CAMDP such that the expected total samples on all
state-action pairs, when running this algorithm, is at least á
SAH 6
Z
Figure 5: A Hard Communicating CAMDP when A = 4, S = 19.
Figure 6: Component Communi- cating CAMDP.
Proof. To construct family of hard MDP instances with parameters S, and diameter at most D, begin by introducing key components and associated notation. Define A' == A - 1. D' D D/8, and = [S/4]. We assume that A 2 3, e < 1/16, and D > max 16 log, 87. 16), which are standard parameter ranges in this construction.
We first define primitive component MDP consisting of three states x, y. 2, each equipped with A' actions and parameterized by D'. The action space partitioned into three subsets based on their transition and reward behavior. This component MDP serves as a key building block in the lower bound construction and is illustrated in Figure 6.
27

---

Published as a conference paper at ICLR 2026
Next, assemble K' identical copies of the component MDP into larger structure Mu. which serves as the base instance for constructing the lower bound family. We begin by constructing an A'-ary rooted tree with exactly S 3K non-leaf nodes and K leaves. It is known that such a tree exists with depth at most [log, 51 + 1. Fach leaf of this tree is replaced by component MDP: the node corresponding to the leaf becomes state while its two children mapped states y and The final MDP Mo is thus formed by embedding the component MDPs into the leaf' structure of the tree, as illustrated in Figure 5.
Transitions in the tree are defined deterministically: every internal node (including x-nodes) has actions that lead to each of its children and its parent (if applicable); all remaining actions correspond to self-loops with zero reward. For each y-state in the embedded components, one designated action also a deterministic self-loop with zero reward. By construction, K 2 S/4, and the overall D, given the definition D' == D/8 and
diameter of Mn is bounded 2
n 148e + log S 1) the assumed bound log, S f D/8.
We then define a collection of hard instances To distinguish among these instances, note that policy must favor action at the zę states in Mo. while selecting at in the corresponding M2.1- Specifically, to be e/24-optimal in Ma the policy must assign occupancy measure most 2/3 to action aj state 2g, while in Mo. the same state must have occupancy measure at least 2/3 on 01 This divergence in action distributions under different instances forms the basis of our lower bound. The design of our hard instance motivated by the construction used for average-reward MDPs in Wang et al. (2022).
2<1<A' based on perturbations Mo-
We further fix the constraint threshold b in the construction of our hard CAMDP instances (Figure 5). Building on the analysis in Appendix F, we leverage a carefully designed reward and constraint structure induce separation in policy behavior across different MDP instances.
Under our construction, we can show that any policy that is 24 --toiimall must satisfy distinct oc- cupancy conditions across instances: in the base instance Mo, the normalized occupancy measure we-representing the fraction of trajectories where action @1 is selected must satisfy μá 2 3. in contrast, for any perturbed instance Ma,1 the same quantity must satisfy n1 I 3. This divergence in occupancy thresholds arises due to the amplification effect in the constraint values, and ensures that policies achieving small regret in one instance must necessarily incur significant suboptimality in others.
This behavioral separation enables us apply Fano's 's method to formally lower bound the probability of misidentifying the underlying instance. Following the same framework as in Appendix F, we derive lower bound on the sample complexity of learning e-optimal policy under strict feasibility:
SAD Furthermore, by noting that the bias span H is always bounded above by the diameter
D, this implies corresponding lower bound of 9 SAH
which holds for the class of weakly
communicating constrained average-reward MDPs.
STATEMENT OF LLM USAGE
This manuscript used large language models solely to assist with language editing and improving the clarity of writing. All technical content, analysis, and conclusions were conceived, implemented, and verified entirely by the authors.
28


Reviews:
[{"review_id": "Ud9nnqyOzO", "reviewer": "Reviewer_c8D3", "summary": "This paper studies the sample complexity of learning in constrained average-reward Markov decision processes (CAMDPs) under the generative model setting. The goal is to determine how many samples are required to compute an \\varepsilon-optimal policy that satisfies a long-run average constraint.\n\nFormally, each policy \\pi has a steady-state average reward \\rho^\\pi_r(s) and a constraint value \\rho^\\pi_c(s), and the learner aims to solve\n\\max_{\\pi}\\;\\rho^\\pi_r(s)\\quad \\text{s.t.}\\quad \\rho^\\pi_c(s)\\ge b.\nThe analysis distinguishes two regimes: relaxed feasibility (where the constraint can be violated by at most \\varepsilon) and strict feasibility (where it must be satisfied exactly).\n\nThe authors propose a model-based primal–dual algorithm that iteratively solves empirical unconstrained MDPs of the form r + \\lambda c while updating the dual variable \\lambda using projected stochastic gradient descent. This construction allows them to derive both upper and lower sample-complexity bounds.\n\nThe main results can be summarized as follows:\n\t•\tRelaxed feasibility:\nN = \\tilde{O}\\!\\left(\\frac{SA(B+H)}{\\varepsilon^2}\\right)\nsamples suffice to compute an \\varepsilon-optimal policy.\n\t•\tStrict feasibility:\nN = \\tilde{O}\\!\\left(\\frac{SA(B+H)}{\\varepsilon^2\\zeta^2}\\right),\nwhere \\zeta is the Slater constant, measuring the size of the feasible region.\n\t•\tMatching lower bound:\nThe authors prove \\tilde{\\Omega}(SA(B+H)/(\\varepsilon^2\\zeta^2)) for strict feasibility, giving the first minimax-optimal characterization of sample complexity in CAMDPs.\n\nHere S and A denote the number of states and actions, H the span of the bias function, and B a bound on transient time. The results extend prior analyses for (i) unconstrained average-reward MDPs (Zurek & Chen, '24) and (ii) discounted constrained MDPs (Vaswani et al., '22).\n\nThe proof builds on Lagrangian duality, strong duality for average-reward MDPs, and confidence bounds for the bias function estimated from the generative model. A Fano-style construction is used to obtain the lower bound. No experiments are provided; this is a purely theoretical paper.", "questions": "1.\tNovelty relative to Vaswani et al. (2022) and Zurek & Chen (2024).\n\t•\tWhat is genuinely new in the analysis beyond extending those frameworks to the average-reward case?\n\t•\tAre there any technical hurdles specific to the average-reward setting (e.g., lack of contraction) that required new ideas?\n\t2.\tUnderstanding the constants.\n\t•\tCan you provide intuition for how the bias-span H, transient time B, and Slater constant \\zeta control the complexity?\n\t•\tIn practice, how might one estimate or bound these quantities?\n\t3.\tAlgorithm design.\n\t•\tWhy is reward perturbation needed in the primal–dual algorithm?\n\t•\tHow sensitive is the performance or convergence to the step size and to the discretization of the dual variable?\n\t4.\tBroader applicability.\n\t•\tCan your results be extended to settings without a generative model — e.g., online learning or policy-gradient approaches?\n\t•\tWould similar rates hold if only sample trajectories were available?\n\t5.\tClarity and structure.\n\t•\tConsider reorganizing the exposition so that the notation is introduced before use, and include a brief intuitive overview of the proof strategy. This would substantially improve readability.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "1.\tTechnically solid.\nThe analysis is mathematically careful and connects several strands of recent work — unconstrained average-reward sample complexity, constrained discounted MDPs, and primal–dual analysis — into one coherent framework.\n\t2.\tCloses a theoretical gap.\nThe paper provides, for the first time, tight upper and lower bounds for CAMDPs. This completes the theoretical landscape for sample complexity under the generative model.\n\t3.\tClear separation between regimes.\nThe dependence on the Slater constant \\zeta elegantly captures how strict feasibility increases sample complexity, mirroring known results in convex optimization and constrained RL.\n\t4.\tMethodologically sound.\nThe primal–dual approach is principled and aligns well with the structure of constrained reinforcement learning.", "weaknesses": "1.\tDifficult presentation.\nThe exposition is unnecessarily dense. Key symbols are introduced before being defined (\\tilde{c}, M’, \\hat{M}), and the algorithmic steps (e.g., the reason for reward perturbations or the \\epsilon-net projection for \\lambda) are not well motivated. The reader has to reconstruct much of the reasoning from context.\n\t2.\tIncremental novelty.\nThe core ideas extend known results from discounted CMDPs and unconstrained AMDPs rather than introducing new analytical techniques. The adaptation to the average-reward case is nontrivial but conceptually straightforward.\n\t3.\tLimited intuition.\nThe paper would benefit from more discussion of how the constants H, B, and \\zeta influence learning difficulty, or how they compare to analogous quantities in the discounted setting. At present, the results are formal but not deeply interpretable.\n\t4.\tLimited to no empirical or illustrative validation.\nEven a small numerical experiment illustrating the scaling with \\zeta or comparing relaxed and strict feasibility would have improved readability and intuition.\n\t5.\tAccessibility.\nThe technical writing assumes significant familiarity with the literature on bias-span bounds and average-reward MDPs. Without this background, it’s very hard to follow.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JZ173KsF4H", "reviewer": "Reviewer_dT8C", "summary": "This paper establishes the first minimax-optimal sample complexity bounds for learning in Constrained Average-Reward MDPs (CAMDPs) under a generative model. The authors propose a model-based primal-dual algorithm that operates under both relaxed feasibility (allowing $\\varepsilon$ constraint violation) and strict feasibility (zero violation) settings. The main results show sample complexities of $\\tilde{O}(SA(B+H)/\\varepsilon^2)$ for relaxed feasibility and $\\tilde{O}(SA(B+H)/(\\varepsilon^2\\zeta^2))$ for strict feasibility, where $\\zeta$ is the Slater constant. The paper also provides matching lower bounds, establishing the first minimax-optimal characterization for CAMDPs.\n\nThe paper is technically sound with rigorous theoretical analysis:\nStrengths:\n⦁\tThe primal-dual algorithm design is well-motivated and properly analyzed\n⦁\tThe proof technique cleverly reduces AMDP concentration to DMDP concentration via Lemma 11\n⦁\tBoth upper and lower bounds are carefully constructed with matching dependencies on key parameters\n⦁\tThe treatment of relaxed vs. strict feasibility is thorough and reveals fundamental differences ($1/\\zeta^2$ factor)\nMinor concerns:\n⦁\tThe assumption that reward functions $r$ and $c$ are known (lines 184-186) simplifies the problem, though the authors correctly note this doesn't affect leading-order complexity\n⦁\tSome proof steps rely heavily on prior work (e.g., Vaswani et al. 2022 for discounted concentration), which is acceptable but limits novelty in techniques\n\nFinally, I am familiar with the relevant literature on constrained MDPs and average-reward RL. I carefully checked the main proof techniques and they appear sound, though I did not verify every detail in the appendix. There is a possibility I may have missed some subtle technical issues in the lengthy appendix proofs.", "questions": "See above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Presentation: The paper is generally well-written and organized:\nStrengths:\n⦁\tClear problem formulation with helpful notation\n⦁\tGood use of proof sketches in main text with details deferred to appendix\n⦁\tFigures 1-3 effectively illustrate the hard instance constructions\n⦁\tThe progression from methodology to upper bounds to lower bounds is logical\nAreas for improvement:\n⦁\tThe paper is dense with heavy notation that could benefit from a notation table\n⦁\tAlgorithm 1 could be more clearly presented with clearer separation of initialization vs. iteration\n⦁\tThe connection between discount factor $\\gamma$ and the transient time/bias span could be explained more intuitively before diving into technical details\n⦁\tSome key quantities (e.g., the perturbation $\\omega$) appear in Algorithm 1 before being properly motivated\n\nContributions: This is a solid theoretical contribution to constrained RL:\nOriginality:\n⦁\tFirst work to establish sample complexity for CAMDPs in the average-reward setting\n⦁\tNovel lower bound constructions specific to the constrained setting\n⦁\tThe separation between relaxed and strict feasibility via the $\\zeta^2$ factor is new and insightful\nSignificance:\n⦁\tCloses an important theoretical gap between unconstrained AMDPs and constrained settings\n⦁\tThe Slater constant $\\zeta$ appears naturally and its role is well-characterized\n⦁\tResults unify understanding across different MDP formulations (finite-horizon, discounted, average-reward)\nLimitations:\n⦁\tPrimarily theoretical with no empirical validation\n⦁\tThe gap between relaxed and strict feasibility (factor of $\\zeta^2$) is proven tight, but practical implications are unclear\n⦁\tLimited discussion of when the bounded transient time assumption holds in practice\n\nStrength:\n1.\tTheoretical completeness: First work to provide matching upper and lower bounds for CAMDPs, establishing minimax optimality with respect to all key parameters ($S$, $A$, $B$, $H$, $\\varepsilon$, $\\zeta$)\n2.\tTechnical rigor: The proofs are careful and detailed, with novel techniques for handling constraints in the average-reward setting\n3.\t**Clear problem formulation**: The paper precisely defines two distinct feasibility settings and shows fundamental computational differences between them\n4.\tComprehensive treatment: Both weakly communicating and general (multichain) MDPs are addressed with appropriate lower bounds for each class", "weaknesses": "1.\tNo empirical validation: The paper is purely theoretical with no experiments demonstrating the algorithm's practical performance or validating the constants hidden in $\\tilde{O}$ notation\n2.\tKnown rewards assumption: While not affecting asymptotic rates, assuming known $r$ and $c$ is somewhat restrictive and simplifies the learning problem\n3.\tLimited practical guidance:\n⦁\tNo discussion of how to estimate unknown parameters ($B$, $H$, $\\zeta$) in practice\n⦁\tNo computational complexity analysis of the algorithm\n⦁\tUnclear how tight the constants are in practice\n4.\tPresentation density: The paper packs substantial technical content that may be challenging for readers not deeply familiar with average-reward MDPs and concentration inequalities\n5.\tScope limitations:\n⦁\tOnly single constraint case studied (extension to multiple constraints not discussed)\n⦁\tNo discussion of function approximation or large state spaces\n⦁\tThe gap between the generative model setting and online/model-free learning remains unaddressed. It would be valuable to discuss how these theoretical insights might extend to practical applications involving resource-constrained online decision-making, such as LLM inference scheduling under memory constraints [1] or dynamic pricing with capacity limitations [2]\n6.\tMinor technical gaps:\n⦁\tThe assumption $\\varepsilon \\in (0, 1/(1-\\gamma)]$ appears in theorems without clear justification of why this range is natural\n⦁\tThe relationship between the empirical bias span $\\hat{H}$ and true $H$ could be made more explicit.\n\nReferences\n[1] Ao, R., Luo, G., Simchi-Levi, D., & Wang, X. Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraints. arXiv preprint arXiv:2504.11320.\n[2] Ao, R., Jiang, J., & Simchi-Levi, D. Learning to Price with Resource Constraints: From Full Information to Machine-Learned Prices. arXiv preprint arXiv:2501.14155.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gwMKA8wilE", "reviewer": "Reviewer_4Q3K", "summary": "This paper provides sample complexity bounds on learning constrained average-reward MDPs under the generative model setting. The authors propose a primal-dual framework that works for the relaxed feasibility and strict feasibility regimes. The algorithm achieves near-optimal sample complexity in both settings. Furthermore, the paper characterizes a matching lower bound for the strict feasibility setting that incorporates the Slater parameter. This shows that the sample complexity upper bound for the setting is (nearly) minimax optimal.", "questions": "I have listed my questions in the weakness part above.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The theoretical contributions, if correct, are clearly significant. Learning infinite-horizon average-reward constrained MDPs seems a harder problem than learning CMDPs in the finite-horizon setting or the discounted-reward setting. The lower bound that incorporates Slater's constant is novel, and it is very interesting that the lower bound matches the complexity upper bound.\n- The proofs are based on novel ideas, not repeating existing analysis techniques. Their arguments are carefully prepared based on the theory of average-reward MDPs.", "weaknesses": "I have two concerns that, I hope, can be addressed or clarified by the authors. Let us discuss them as below.\n- In each iteration, the algorithm requires solving an unconstrained average-reward MDP. Theoretically, as claimed in the paper, the part can be dealt with by a black-box MDP solver such as a linear programming-based method. However, it seems to important to incorporate errors incurred from the black-box MDP solver and to discuss its complexity. \n- I think that the most subtle part is about arguing that the average-reward of approximate MDPs is bounded. However, I had hard time understanding the proof of Lemma 17. It is not clear why the bias function of an approximate MDP is bounded. Moreover, the average-reward of an approximate MDP remains constant for all states? I also have the following more specific questions about the proof. \n\n&ensp; Why is it that (Lemma 8.6.4, Puterman 1994) implies $|\\rho^\\star - \\hat \\rho^\\star|_\\infty\\leq O(\\varepsilon)$?\n\n&ensp; Why does $|| \\hat h||_\\infty\\leq H$ hold?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1I8vcJFKpP", "reviewer": "Reviewer_6HuV", "summary": "This paper introduce a minimax-optimal primal-dual method for constrained AMDPs under the generative setting.", "questions": "See above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The analysis is solid and close the gap in the current literature of constrained average-reward MDPs. The approach used makes sense, converting to a MDP and update the dual variable, following the standard primal-dual setup. it is impressive to see that the proposed algorithm match the lower bound, which is also presented in this paper. Overall I find this work substantial and the paper is nicely written.", "weaknesses": "1. As this paper proposes to use a generative model, a natural question would be, how feasible is it to extend to the markovian model setting? Oftentimes, e.g. in robotics, we cannot sample arbitrary state-action pairs even given a simulator. Thus the generative model assumption does not hold here. \n2. Although the approach of reducing the AMDP to DMDP with Blackwell-optimality appears in other works, I wonder if one can solve the AMDP directly. Experience shows that large discount factor pose instability to the algorithm, limiting the applicability of the proposed framework. As such, the contribution of the work is limited to algorithm analysis. \n3. I am not familiar with the field of constrained MDPs so I encourage the authors to present related work's results, even in discounted setting (as this work use some sort of discounted setup) to give a fair comparison.\n4. I find the use of model-based approach failing to attract my interest, as real life problems are unlikely be handled through world model learning. In addition, for large state or action spaces, function approximation seems to be unavoidable, in which this work does not address either. \nNevertheless, I think this is solid work, for which I lean positively.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)