📊 statistics

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

This paper establishes near-optimal sample complexity bounds for learning $\epsilon$ -optimal policies in constrained average-reward MDPs under a generative model by proposing a model-based algorithm that achieves minimax-optimal rates for both relaxed and strict feasibility settings, thereby closing a significant theoretical gap in the field.

Original authors: Yukuan Wei, Xudong Li, Lin F. Yang

Published 2026-08-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yukuan Wei, Xudong Li, Lin F. Yang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of artificial intelligence, machines learn to make decisions by interacting with an environment, much like a child learning to navigate a room. They receive rewards for good actions and penalties for bad ones, gradually building a strategy to maximize their long-term success. This process, known as reinforcement learning, has powered breakthroughs in everything from playing complex games to controlling robotic arms. However, real-world applications demand more than just high scores; they require safety and fairness. A delivery drone must not only reach its destination quickly but also stay within a specific battery budget. A medical AI must recommend treatments that are effective without exceeding a patient's risk tolerance. These scenarios are modeled as constrained decision-making problems, where an agent must find the best possible path while strictly adhering to rules about resources, risk, or time.

For decades, researchers have struggled to teach machines how to learn these safe strategies efficiently, especially when the environment is complex and the rules apply to the long run rather than just the next few steps. The challenge lies in balancing the drive for high rewards with the need to stay within strict limits, all while the machine has no prior map of the world and must learn by trial and error. A new study by researchers at Fudan University and the University of California, Los Angeles, tackles this head-on by establishing the precise limits of how much information a machine needs to learn a safe, optimal strategy. They have determined the exact amount of data required to solve these problems, proving that the difficulty depends on two specific characteristics of the environment: how long it takes for the system to settle into a stable pattern and how sensitive the long-term rewards are to small changes in strategy.

The researchers focused on a setting where the learning agent has access to a simulator, a tool that allows it to ask, "If I take this action in this situation, what happens next?" and receive an immediate answer without having to wait for a real-world event to unfold. This setup, known as a generative model, removes the need for risky exploration in the real world and lets the researchers focus purely on the mathematical efficiency of the learning process. They investigated a specific type of problem where the goal is to maximize the average reward over an infinite future, rather than just a short, fixed period. This is crucial for applications like managing a power grid or a fleet of vehicles, where the goal is steady, long-term performance rather than a quick, one-off win.

The team developed a new algorithm that acts as a guide for the learning agent. This algorithm works by constantly adjusting a balance between the desire for reward and the need to obey constraints. It does this by solving a series of simplified, discounted versions of the problem, where future rewards are slightly less valuable than immediate ones, and then translating those solutions back to the long-term average. A key innovation in their work is a method to control the statistical noise that inevitably arises when learning from a finite number of samples. They proved that by carefully selecting which strategies to test and how to combine them, the algorithm can avoid the pitfalls of overfitting to random fluctuations in the data.

The study's most significant finding is a precise calculation of the sample complexity, which is the number of data points required to guarantee a near-perfect solution. The researchers found that the amount of data needed is directly tied to the size of the state and action spaces, multiplied by a factor that represents the "span" of the system's behavior and the time it takes to reach a stable state. They distinguished between two scenarios: one where the agent is allowed to slightly violate the rules, and another where it must obey them exactly. In the relaxed scenario, the data requirement grows with the square of the desired accuracy. However, in the strict scenario, where the agent must never break the rules, the data requirement increases significantly, depending on a specific measure of how much "wiggle room" exists in the feasible region.

To prove that their algorithm is as efficient as possible, the researchers constructed a series of difficult, hypothetical environments designed to trick any learning algorithm. These hard cases showed that no method could possibly learn faster than their algorithm without failing on some problems. They demonstrated that the extra data required for strict safety is not just a flaw in their method, but a fundamental law of learning under constraints. The results establish a clear boundary: if an agent needs to be perfectly safe, it must pay a higher price in terms of data collection, and this cost is unavoidable.

This work provides the first complete picture of the statistical limits for learning safe, long-term strategies. It confirms that while it is possible to learn these complex behaviors efficiently, the cost of strict safety is real and quantifiable. The findings offer a roadmap for developers building AI systems for high-stakes environments, telling them exactly how much data they need to gather to ensure their agents are both effective and safe. By defining these limits, the study moves the field from guessing about feasibility to knowing the precise requirements for success, ensuring that future intelligent systems can be deployed with confidence in the real world.

Technical Summary: Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPs

Problem Formulation
This paper investigates the sample complexity of learning $\epsilon$ -optimal policies for Constrained Average-Reward Markov Decision Processes (CAMDPs) under a generative model. A CAMDP is defined by a tuple $\mathcal{M} = \langle S, A, P, r, c, b, s \rangle$ , where the agent seeks to maximize the steady-state average reward $\rho^\pi_r(s)$ subject to an average constraint $\rho^\pi_c(s) \geq b$ . The benchmark policy $\pi^*$ is an external mixture of stationary deterministic policies. The authors consider two feasibility regimes:

Relaxed Feasibility: The output policy may violate the constraint by at most $\epsilon$ (i.e., $\rho^{\hat{\pi}}_c(s) \geq b - \epsilon$ ).
Strict Feasibility: The output policy must satisfy the constraint exactly (i.e., $\rho^{\hat{\pi}}_c(s) \geq b$ ).

The analysis relies on structural parameters: $S$ and $A$ (state and action counts), $H$ (a uniform upper bound on the bias spans of reward and constraint functions), $B$ (a uniform bound on the transient time), and $\zeta$ (a lower bound on the Slater margin, characterizing the size of the feasible region). The work assumes a policy-wise discounted variance condition (Assumption 1).

Methodology
The authors propose a model-based primal-dual algorithm (Algorithm 1) that operates by solving a sequence of perturbed empirical discounted MDPs. Key methodological components include:

Primal-Dual Framework: The algorithm maintains a Lagrange multiplier $\lambda_t$ and updates it based on the constraint violation of the current policy. The primal step solves for a deterministic policy $\hat{\pi}_t$ that maximizes a Lagrangian reward $r_p + \lambda_t c$ in an empirical discounted setting.
Perturbation and Rounding: To ensure uniqueness of optimal actions and facilitate concentration analysis, the reward signal is perturbed by a random variable $Z$ . The Lagrange multipliers are discretized on a grid $\Lambda$ .
Cross-Signal Concentration: A central technical contribution is a new concentration theorem (Theorem 2) for the finite family of empirical Lagrangian oracle policies. Unlike standard uniform concentration over the entire policy class, this result controls the estimation error for the specific policies generated by the algorithm. It utilizes a "state-action absorbing construction" to decouple rows and employs a conditional Bernstein hierarchy to retain instance-dependent variance terms.
Transfer to Average Reward: The guarantees derived for the perturbed discounted problems are transferred to the original average-reward problem using bridge lemmas that relate discounted values to average rewards via the bias span $H$ .

Key Contributions and Results
The paper establishes the first near-optimal sample complexity bounds for CAMDPs in the average-reward setting, distinguishing between relaxed and strict feasibility:

Relaxed Feasibility Upper Bound: The algorithm achieves an $\epsilon$ -optimal policy with relaxed constraint satisfaction using $\tilde{O}\left(\frac{SA(B + H)}{\epsilon^2}\right)$ samples. Notably, this rate is independent of the Slater margin $\zeta$ .
Strict Feasibility Upper Bound: For strict constraint satisfaction, the sample complexity increases to $\tilde{O}\left(\frac{SA(B + H)}{\epsilon^2 \zeta^2}\right)$ . The dependence on $\zeta^{-2}$ reflects the difficulty of ensuring exact feasibility without violation.
Lower Bounds:
- For weakly communicating CAMDPs, the authors construct a hard family with diameter $D$ (where $H = \Theta(D)$ ) proving an adaptive minimax lower bound of $\tilde{\Omega}\left(\frac{SAH}{\epsilon^2 \zeta^2}\right)$ for strict feasibility.
- For general CAMDPs, a separate transient hard family yields a lower bound of $\tilde{\Omega}\left(\frac{SAB}{\epsilon^2 \zeta^2}\right)$ under balanced sampling.
- Combining these subfamilies, the worst-case lower bound for balanced algorithms is $\tilde{\Omega}\left(\frac{SA(B + H)}{\epsilon^2 \zeta^2}\right)$ , which matches the strict-feasibility upper bound up to logarithmic factors.

Significance and Claims
The authors claim this work provides the first sample complexity characterization for CAMDPs in the average-reward setting. The results reveal that the statistical difficulty of learning under long-run constraints is jointly determined by the bias span ( $H$ ), transient behavior ( $B$ ), and the feasible-region margin ( $\zeta$ ).

The paper explicitly states that while relaxed and strict feasibility have been studied in discounted CMDPs (e.g., Vaswani et al., 2022), the average-reward setting presents unique challenges because properties like Bellman contraction do not hold. By establishing matching upper and lower bounds, the work demonstrates that the additional $\zeta^{-2}$ dependence required for strict feasibility is unavoidable and establishes a provable separation between the relaxed and strict regimes. The proposed algorithm and analysis framework are presented as the first to achieve near-minimax optimality for constrained average-reward reinforcement learning under a generative model.

Technical Summary: Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPs

More like this