Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPs

arXiv:2509.16586 · cs.LG, stat.ML · Submitted 2026-08-16 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPs".

Jane: The paper was written by Yukuan Wei, Xudong Li and Lin F. Yang from Fudan University and University of California, Los Angeles.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: Alright, welcome back to the show, everyone. Today we're digging into a fresh paper from the arXiv listing, and the title is a mouthful — "Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPs." Jane, I'm going to need you to translate that for me.

Jane: Happy to, Tom. So "average-reward" means we're looking at systems that run forever, and we care about the long-run reward per step, not a one-shot outcome. And "constrained" means there's a rule — like a budget on cost, or a safety limit — that the policy has to respect while it maximizes that reward.

Tom: So it's like a robot that has to maximize how much work it does per day, but it's not allowed to exceed a power budget. That's the constraint.

Jane: Exactly. And the paper is about how many samples — how many times you need to poke the environment to learn a good policy — when you only have a simulator, a generative model. That's the sample complexity question.

Tom: And the authors are Yukuan Wei and Xudong Li from Fudan, plus Lin Yang from UCLA. This is a theory paper, so we're talking about guarantees and bounds, not benchmarks.

Jane: Right. And the big deal here is that this is the first time anyone has nailed down the near-optimal sample complexity for this constrained average-reward setting. Before this, we had bounds for the unconstrained case, and we had bounds for the constrained case but only in the discounted setting. This paper closes that gap.

Tom: So they're saying, "we now know exactly how hard this problem is, up to log factors."

Jane: Yes, and they prove it both ways — they give an algorithm that achieves the bound, and they prove a lower bound showing you can't do better. That's the gold standard in this kind of work.

Tom: And that's a big deal because it means future researchers can stop trying to beat these numbers and instead focus on other questions, like making the algorithms practical.

Jane: Exactly. It sets the ceiling and the floor. Now everyone knows where the game is played.

Tom: So what's the catch? There's always a catch.

Jane: The catch is that the bounds depend on some problem-specific parameters — like how long the system takes to mix, and how much slack you have in the constraint. If those are bad, the sample complexity blows up. But that's not a flaw; that's the reality of the problem.

Tom: So it's a precise answer to a hard question. I love it. Let's get into the details of how they actually achieve these bounds.

Jane: Let's do it.

Summary: Tom: So we've got the title sorted. Now let's talk about what the paper actually does. Jane, give us the summary.

Jane: So the paper studies a constrained average-reward MDP, which is a fancy way of saying a system that runs forever, has a reward you want to maximize, and a constraint you have to satisfy. The authors propose a model-based algorithm — meaning they first estimate the transition probabilities by sampling, and then they plan on top of that estimate.

Tom: And the key trick is that they convert the constrained problem into a sequence of unconstrained ones, right?

Jane: Exactly. They use a primal-dual approach. You have a Lagrange multiplier that penalizes constraint violations, and you alternate between optimizing the policy for a fixed multiplier and updating the multiplier based on how much the constraint is violated. It's a classic idea, but making it work in the average-reward setting is nontrivial.

Tom: Because in average-reward, you don't have the nice contraction properties you get with discounting.

Jane: Right. With discounting, future rewards are geometrically weighted, which makes the math easier. In average-reward, every step counts equally, so you have to deal with bias functions and mixing times. The paper handles this by carefully choosing a discount factor that's close to one solving the discounted problem, and then showing the solution transfers back to the average-reward setting.

Tom: And they do this under two different settings — relaxed feasibility and strict feasibility.

Jane: Yes. Relaxed means you're allowed to violate the constraint by a tiny bit, like ε. Strict means zero violation — the policy has to satisfy the constraint exactly. The sample complexity for relaxed is roughly SA(B+H)/ε2, and for strict it's SA(B+H)/(ε2ζ2), where ζ is the Slater constant, which measures how much slack you have in the constraint.

Tom: So the strict case is harder by a factor of one/ζ2. That makes sense — if you have very little slack, it's much harder to guarantee you won't violate the constraint.

Jane: Exactly. And the paper proves a matching lower bound for the strict case, so they know it's not just an artifact of their algorithm. It's genuinely harder.

Tom: That's the kind of result that makes a theorist's day.

Jane: And it's also practically useful. If you know the strict case is inherently harder, you can make an informed choice about whether you need zero violation or can tolerate a small one.

Tom: So the summary is: they give tight bounds, they prove them, and they show the strict case is fundamentally harder. That's a complete story.

Jane: It is. But there's more — the way they handle the general case, where the MDP isn't just weakly communicating, is clever too. Let's talk about that.

Improvements: Tom: So we've covered the main results. Now let's talk about what this paper improves on. Jane, what was the state of the art before this?

Jane: Before this, we had near-optimal bounds for unconstrained average-reward MDPs — that was done by Zurek and Chen. And we had bounds for constrained MDPs, but only in the discounted setting — that was Vaswani and colleagues. This paper is the first to bring those two lines together.

Tom: So it's a unification.

Jane: Exactly. And they also handle the general case, not just the "nice" case where all states communicate. They introduce a parameter B, the transient time bound, which measures how long the system can linger in transient states before hitting a recurrent class. That lets them handle multichain MDPs, which are messier.

Tom: And they prove a lower bound that includes that B parameter too, right?

Jane: Yes. The lower bound for the general case is SA(B+H)/(ε2ζ2), and for the weakly communicating case it's SAH/(ε2ζ2). So they show that the transient time B is not just an artifact of their analysis — it's genuinely needed.

Tom: That's a strong result. But what does this mean for people who actually want to build systems?

Jane: Good question. Let me bring in Meng, who's our engineer in residence.

Meng: Thanks, Jane. From an engineering standpoint, the practical takeaway is that you now know exactly what you're paying for. If you're building a system that must never violate a safety constraint, you know the sample complexity grows like one/ζ2. So if your safety margin is small, you need a lot more data. That's not a surprise, but now it's quantified.

Tom: So you can budget your data collection accordingly.

Meng: Right. And the algorithm itself is modular — it uses a black-box planner for the unconstrained MDPs. So if you have a good planner already, you can plug it in. That's a big practical advantage.

Lu: And I'd add that the theoretical framework here is likely to be useful beyond just this specific problem. The way they handle the average-reward setting with bias functions and transient times is quite general. I can see this being adapted to other constrained problems, like multi-objective RL or safe RL with multiple constraints.

Tom: So it's not just a single result; it's a toolkit.

Lu: Exactly. And the lower bound techniques — using Fano's method on carefully constructed hard instances — those are also reusable. They show how to build hard instances for constrained average-reward problems, which is a contribution in itself.

Jane: And that's what makes this paper important. It's not just the numbers; it's the methods. They're giving the community new tools to attack related problems.

Tom: So the improvements are: unification of two lines of work, handling the general case, and providing reusable techniques. That's a lot.

Jane: It is. And it sets the stage for future work on more complex constrained problems.

Conclusion: Tom: Alright, we've covered the title, the summary, and the improvements. Let's wrap this up. Jane, give us the final word on "Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPs."

Jane: The bottom line is that this paper settles a fundamental question. It tells us exactly how many samples you need to learn a near-optimal policy in a constrained average-reward MDP, both when you can tolerate a small constraint violation and when you can't. And it proves that the strict case is genuinely harder by a factor related to the Slater constant.

Tom: And they did it with matching upper and lower bounds, which is the gold standard.

Jane: Yes. The algorithm is model-based and uses a primal-dual approach, and the lower bounds are based on carefully constructed hard instances. Both contributions are significant on their own.

Meng: From my side, the practical value is that you now know what you're paying for. If you need zero constraint violation, you need roughly one/ζ2 more data. That's a concrete number you can use in system design.

Lu: And I'd say the theoretical framework — handling average-reward with bias functions and transient times — is likely to be influential beyond this specific paper. It gives the community new tools for constrained RL problems.

Lalam: I'd add that this work has cultural implications too. As we deploy AI systems in high-stakes domains like healthcare and energy management, knowing the true cost of safety is essential. This paper gives us a principled way to think about that cost, which helps build trust in AI systems.

Tom: That's a great note to end on. So, "Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPs" — a complete story, tight bounds, and practical implications. Thanks to the authors for this one.

Jane: And thanks to all of you for listening. We'll be back with the next paper soon. Until then, keep learning.

Tom: Take care, everyone.

Yukuan Wei, Xudong Li, Lin F. Yang

Fudan University · University of California, Los Angeles

cs.LG, stat.ML

Submitted: 2026-08-16

Updated: 2026-08-18

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 92/100

Key concepts

Constrained Average-Reward MDPs
These are systems designed to run indefinitely, aiming to maximize the long-run reward per step. A 'constrained' system must also adhere to a specific rule or safety limit, such as a budget on cost or a power restriction.
Sample Complexity
This concept addresses how many times you need to interact with an environment (or simulator) in order to learn a good policy. The paper focuses on finding the minimum number of samples required for convergence.
Primal-Dual Approach
The authors use this technique to convert the constrained problem into a series of unconstrained problems. This involves using a Lagrange multiplier, which penalizes any violations of the safety constraints.
Strict vs. Relaxed Feasibility
These terms define how strictly the constraint must be met. Strict feasibility requires zero violation, while relaxed feasibility allows for a small, tolerable violation (epsilon), which affects the required sample complexity.

Terminology

Summary

Summary

This paper establishes the first near-optimal (minimax-optimal) sample complexity bounds for learning in constrained average-reward Markov decision processes (CAMDPs) under a generative model. The authors propose a model-based primal-dual algorithm that operates under two settings: relaxed feasibility, which allows small constraint violations, and strict feasibility, where the output policy must satisfy the constraint exactly.

Problem formulation. The paper studies an infinite-horizon CAMDP denoted by the tuple ⟨S, A, P, r, c, b, s⟩, where the objective is to maximize the primary reward function r subject to a constraint c. The goal is to find a policy solving: max ρ π r(s) s.t. ρ π c(s) ≥ b. The complexity parameters include the span bound of the bias function H, the transient time parameter B, and the Slater constant ζ:= max π ρ π c(s) − b, which measures the feasibility margin.

Algorithm. The proposed model-based algorithm (Algorithm 1) collects N independent samples from P(·s,a) for each state-action pair, forms an empirical transition matrix P̂, and solves a sequence of unconstrained average-reward MDPs using black-box planners. The algorithm uses a primal-dual approach with dual updates projected onto an epsilon-net, and outputs a mixture policy π̂ = (1/T)Σ t=0 T-1 π̂ t. The primal update at iteration t requires solving an unconstrained MDP with reward r̃ + λ t c̃, where r̃ is a perturbed reward.

Main results.

  1. Relaxed feasibility (Theorem 2): For a fixed ε ∈ (0,1], δ ∈ (0,1), Algorithm 1 with N = Õ(SA(B+H)/ε2) samples, b′ = b − 3ε/8, ω = ε(1−γ)/8, U = O(1/ε(1−γ)), ε l = O(ε2(1−γ)2), T = O(1/(1−γ)4ε4) and γ = 1 − ε opt/(4(B+H)) returns a policy π̂ satisfying ρ π̂ r(s) ≥ ρ* r(s) − ε and ρ π̂ c(s) ≥ b − ε with probability at least 1 − 4δ.

  2. Strict feasibility (Theorem 3): For a fixed ε ∈ (0,1/(1−γ)] and δ ∈ (0,1), Algorithm 1 with N = Õ(SA(B+H)/(ε2ζ2)) samples, b′ = b + ε(1−γ)ζ/20, ω = ε(1−γ)/10, U = 4(1+ω)/(ζ(1−γ)), ε l = O(ε2(1−γ)4ζ2), T = O(1/(1−γ)6ζ4ε2) and γ = 1 − ε opt/(4(B+H)) returns a policy π̂ satisfying ρ π̂ r(s) ≥ ρ* r(s) − ε and ρ π̂ c(s) ≥ b with probability at least 1 − 4δ.

  3. Lower bounds: The paper establishes a matching lower bound of Ω̃(SA(B+H)/(ε2ζ2)) for the strict feasibility case (Theorem 5 for general CAMDPs), and a specialized lower bound of Ω̃(SAH/(ε2ζ2)) for weakly communicating CAMDPs (Theorem 4). These are the first lower bounds for strict feasibility in CAMDPs, establishing a provable separation between the relaxed and strict regimes.

Key technical contributions. The proof relies on several lemmas: Lemma 6 bounds the optimal dual variable under both relaxed and strict feasibility settings; Lemma 9 decomposes the suboptimality in the relaxed setting; Lemma 10 decomposes the suboptimality in the strict setting; Lemma 11 converts concentration errors from discounted to average-reward settings; Lemmas 13 and 14 provide concentration bounds for the empirical value functions. The lower bound constructions use Fano's method with carefully designed hard instances involving tree structures and component MDPs that induce separation in policy behavior across instances.

Conclusion. The paper states: "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 Õ(SA(B+H)/ε2) and Õ(SA(B+H)/(ε2ζ2)), respectively. Complementing these results, we derive a matching lower bound of Ω̃(SA(B+H)/(ε2ζ2)) for the strict feasibility setting, together with a specialized lower bound of Ω̃(SAH/(ε2ζ2)) 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 ε."

Improvements for AI systems

Based on the scientific paper, here are the specific improvements I can make to AI systems and what the improved system can do:

Improvement: Integrate a primal-dual optimization layer that handles long-run average constraints (not just discounted or finite-horizon constraints) with provable sample-complexity guarantees.

What the improved system can do:

  • Optimize policies for sustained operations (e.g., data centers, energy grids, wireless networks) where the objective is average throughput over infinite time, subject to average power or cost constraints.

  • Guarantee that constraint violations are bounded by ε (relaxed) or zero (strict), even when the environment model is learned from limited samples.

  • Automatically balance exploration (sampling transitions) and exploitation (policy optimization) using the model-based approach with empirical transition matrices.

Improvement: Add a strict feasibility mode that uses a tightened constraint (b′ = b + Δ) in the learned model, with sample complexity scaling as Õ(SA(B+H)/(ε2ζ2)).

Improvement: Implement a sample-complexity-aware planner that allocates samples based on structural parameters (bias span H, transient time B, Slater constant ζ).

Improvement: Design the algorithm to use any existing unconstrained AMDP solver as a black-box (via the primal update step), rather than requiring a custom solver.

Improvement: Provide a relaxed mode that allows small constraint violations (ε) in exchange for lower sample complexity (Õ(SA(B+H)/ε2), independent of ζ).

Improvement: Implement the algorithm with provably optimal sample complexity (matching lower bounds), ensuring no wasted samples.

Improvement: Support general MDPs (not just communicating or weakly communicating) by incorporating the transient time parameter B in both upper and lower bounds.

The improved AI system will be a sample-optimal constrained reinforcement learning engine that:

  • Solves infinite-horizon average-reward problems with long-run constraints

  • Guarantees either relaxed (ε-violation) or strict (zero-violation) constraint satisfaction

  • Adapts its sample budget to the problem's intrinsic difficulty (H, B, ζ)

  • Integrates with any existing unconstrained MDP solver

  • Provides formal minimax-optimal performance certificates

  • Works for general MDPs, including multichain and non-mixing systems

This is particularly valuable for applications like network resource allocation, sustainable energy management, long-term medical treatment planning, and safe autonomous systems where decisions must be optimal over long horizons while respecting hard constraints.

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 (S A (B+H) over epsilon squared) and (S A (B+H) over epsilon squared zeta squared) 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 (S A (B+H) over epsilon 2 zeta squared) 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.

Sources

Related papers