📊 statistics

Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions

This paper establishes the minimax-optimal sample complexity for learning $\varepsilon$ -optimal policies in distributionally robust average-reward Markov decision processes, revealing a regime-dependent complexity bound that transitions from nominal to robust behavior based on the perturbation scale $\sigma H_0$ , and achieves these rates through novel span-informed and span-agnostic plug-in reduction procedures.

Original authors: Yuepeng Yang, Yuxin Chen, Yuejie Chi

Published 2026-08-10

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Yuepeng Yang, Yuxin Chen, Yuejie Chi

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

Imagine you are training a robot to navigate a maze. In the perfect world of a video game, the walls stay put, the floor is always dry, and the robot knows exactly where every step will land. But in the real world, things are messy. A floor might be slippery, a door might be slightly stuck, or a gust of wind might push the robot off course. If you train your robot only on the "perfect" map, it might crash the moment it hits a real-world wobble. This is the heart of a field called Reinforcement Learning, where agents learn by trial and error to make the best decisions.

Usually, these agents try to maximize their total score over a long time, like a marathon runner aiming for the best average speed. But here's the catch: what if the map they learned from isn't the map they're running on? This is where Distributionally Robust thinking comes in. Instead of assuming the world is exactly as it looks, the agent prepares for the "worst-case" scenario within a reasonable range of errors. It asks, "What if the floor is a little slippery? What if the door is a little heavier?" It learns a strategy that works well even when things go slightly wrong. The big question scientists have been asking is: How much practice (data) does a robot actually need to learn this kind of "safe" strategy? Is it a little extra practice, or does it require a massive amount of data to be truly robust?

This paper, titled "Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions," dives deep into that question. The authors, researchers from Yale and Penn, act like detectives trying to figure out the exact "price" of safety. They discovered that the amount of data needed depends on two main things: how "wiggly" or unpredictable the environment is (the uncertainty), and how much the robot's performance varies depending on where it starts (the "bias span").

They found that there are two distinct "zones" of learning. In the High-Tolerance Zone, the robot is allowed to be a little imperfect. Here, the data needed is relatively low, similar to what you'd need to learn a normal, non-robust strategy. It's like learning to ride a bike on a flat, calm day; you don't need to worry too much about the wind. However, in the Low-Tolerance Zone, the robot must be perfect even when the wind is howling. Here, the data requirement jumps up significantly. The authors proved that to be this safe, the robot needs extra data that scales with the square of the uncertainty. It's a steep price to pay for absolute safety, but they proved it's the minimum necessary cost—you cannot bypass the math.

The paper also introduces a clever "plug-in" method. Imagine you have a recipe for a cake. Sometimes, you just need to bake the cake as written (the "nominal" approach). Other times, you need to add extra stabilizers to make sure it doesn't collapse if the oven temperature fluctuates (the "robust" approach). The authors created a smart system that looks at the situation and decides: "Do I just follow the recipe, or do I need the stabilizers?" If the robot knows the "span" (how much its performance varies), it can choose the most efficient path. If it doesn't know the span, the system has a backup plan that learns from the data itself to make the right choice.

In short, this paper doesn't just guess; it provides a mathematical proof of exactly how many samples are needed to learn a robust policy. They showed that previous methods were sometimes using too much data or not enough, and they provided the "Goldilocks" solution: just the right amount of data for the job, whether the environment is calm or chaotic. Their findings were backed up by both rigorous mathematical proofs and computer simulations that confirmed their theories hold true in practice.

Technical Summary: Robust Average-Reward Markov Decision Processes

Problem Formulation
This work investigates the statistical complexity of learning an $\epsilon$ -optimal policy for Distributionally Robust Average-Reward Markov Decision Processes (AMDPs) under a generative model setting. The agent operates within a nominal environment defined by a transition kernel $P^0$ and a reward function $r$ . However, the true environment dynamics are uncertain and may lie within a prescribed uncertainty set $\mathcal{P}$ centered at $P^0$ . Specifically, the paper considers $(s, a)$ -rectangular total-variation (TV) uncertainty sets with a radius of at most $\sigma$ .

The objective is to maximize the robust average reward, defined as the worst-case long-run average reward over all transition kernels in $\mathcal{P}$ :
$\rho^{\pi, \sigma} := \inf_{P \in \mathcal{P}} \lim_{T \to \infty} \mathbb{E}^\pi_P \left[ \frac{1}{T} \sum_{t=0}^{T-1} r(s_t, a_t) \right]$
The learning goal is to compute a policy $\hat{\pi}$ using $N$ samples per state-action pair such that $\rho^{\star, \sigma} - \rho^{\hat{\pi}, \sigma} \leq \epsilon$ , where $\rho^{\star, \sigma}$ is the optimal robust average reward.

Key Parameters and Structural Assumptions
The analysis relies on two critical structural parameters:

Nominal Optimal Bias Span ( $H_0$ ): The span of the bias function satisfying the nominal Bellman optimality equation.
Robust Optimal Bias Span ( $H_\sigma$ ): The span of the bias function satisfying the robust Bellman optimality equation.

The paper establishes that $H_0$ and $H_\sigma$ are generally independent; neither controls the other. A crucial perturbation scale is identified as $\sigma H_0$ , which separates the learning problem into two distinct regimes:

High-Tolerance Regime ( $\epsilon \gtrsim \sigma H_0$ ): The perturbation caused by uncertainty is small relative to the target accuracy.
Low-Tolerance Regime ( $\epsilon \lesssim \sigma H_0$ ): The perturbation is significant, and nominal optimization alone is insufficient to guarantee robust optimality.

Methodology: Reduction-Based Plug-in Procedures
The core methodological contribution is a reduction framework that transforms the difficult robust average-reward problem into a more tractable robust discounted MDP (DMDP) problem. The authors propose two algorithms based on this reduction:

Span-Informed Procedure (Algorithm 1): Assumes $H_0$ and $H_\sigma$ are known. It adaptively selects between a nominal reduction (solving a standard DMDP with the empirical kernel) and a robust reduction (solving a DMDP over the uncertainty set). The choice depends on the ordering of $H_0$ and $H_\sigma$ and the tolerance regime. The discount factor $\gamma$ is calibrated based on the relevant span parameter (e.g., $\gamma = 1 - \epsilon/(3H_\sigma)$ ).
Span-Agnostic Procedure (Algorithm 2): Operates without knowledge of $H_0$ or $H_\sigma$ . It constructs a set of candidate policies from both nominal and robust reductions across a dyadic grid of discount factors. It then selects the best policy using a lower-confidence bound (LCB) on the robust average reward, derived from an "anchor certificate" computed from a separate data batch. This allows the algorithm to adaptively choose the correct reduction and discount factor based on the data.

The analysis leverages three key technical refinements to achieve tight bounds:

Comparing the robust discounted problem with a nominal reference solution (anchor) to tighten variance terms.
Controlling discounted value functions via their spans ( $H_\sigma$ ) rather than the effective horizon.
Using localized concentration bounds governed by these spans.

Main Results: Minimax Sample Complexity
The paper provides matching upper and lower bounds for the minimax sample complexity $N_{SA}$ (samples per state-action pair), up to logarithmic factors. The complexity is characterized by a four-regime summary based on the ordering of $H_0$ and $H_\sigma$ and the tolerance regime:

$N_{SA} \asymp \frac{SA}{\epsilon^2} \times \begin{cases} \min\{H_0, H_\sigma\} & \text{if } \epsilon \gtrsim \sigma H_0 \quad (\text{High Tolerance}) \\ \min\{H_0, H_\sigma\} + \sigma H_\sigma^2 & \text{if } \epsilon \lesssim \sigma H_0 \quad (\text{Low Tolerance}) \end{cases}$

High-Tolerance Regime: The complexity is dominated by the linear span term $\min\{H_0, H_\sigma\}$ . If $H_\sigma \leq H_0$ , the robust reduction yields a tighter bound than the nominal one.
Low-Tolerance Regime: An additional "robustness-specific" term $\sigma H_\sigma^2$ appears, representing the cost of handling distributional uncertainty when high precision is required.
Lower Bound: The authors prove a minimax lower bound that matches the upper bound, establishing that the term $\sigma H_\sigma^2$ is fundamental and cannot be avoided in the low-tolerance regime. This is the first lower bound characterizing the statistical limits of distributionally robust AMDPs.

Significance and Claims
The paper claims to provide the first minimax-optimal characterization of sample complexity for distributionally robust AMDPs. Key contributions include:

Resolution of the Sample Complexity Gap: Previous robust upper bounds (e.g., Roch et al., 2025, 2026) depended quadratically on robust span parameters ( $H_{Roch}^2$ or $H_{RHI}^2$ ) without distinguishing between high and low tolerance. This work refines the dependence to $\min\{H_0, H_\sigma\}$ in the high-tolerance regime and identifies the precise $\sigma H_\sigma^2$ cost in the low-tolerance regime.
Adaptive Algorithms: The proposed span-agnostic procedure (Algorithm 2) achieves these optimal rates without prior knowledge of the span parameters, automatically adapting to the regime and the relative magnitudes of $H_0$ and $H_\sigma$ .
Generality: The results hold even if only the robust span $H_\sigma$ is assumed bounded, yielding a complexity of $\tilde{\Theta}(SA(H_\sigma + \sigma H_\sigma^2)\epsilon^{-2})$ .

Experimental results on controlled simulations verify the predicted linear dependence on $\min\{H_0, H_\sigma\}$ and the quadratic dependence on $\sigma H_\sigma^2$ in the low-tolerance regime, as well as the adaptivity of the span-agnostic algorithm. The authors note that future work could explore coupled uncertainty structures and online (regret-based) settings, but the current work focuses strictly on the generative model setting.

Technical Summary: Robust Average-Reward Markov Decision Processes

More like this