📊 statistics

Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis

This paper introduces Robust Halpern Iteration (RHI), a model-free algorithm for robust average-reward reinforcement learning that utilizes a novel multi-level Monte-Carlo estimator to achieve state-of-the-art finite sample complexity for finding $\varepsilon$ -optimal policies under various uncertainty models.

Original authors: Zachary Roch, George Atia, Yue Wang

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zachary Roch, George Atia, Yue Wang

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

The Big Picture: The "Sim-to-Real" Problem

Imagine you are training a robot to walk. You teach it in a perfect, frictionless video game simulation. In the game, it learns to walk perfectly. But when you put it in the real world, the floor is slippery, the wind blows, and the robot falls over.

This is the Sim-to-Real gap. The robot's training environment (the simulation) doesn't match the real world.

Most standard AI training assumes the world is exactly as it was taught. This paper tackles a different approach: Robust Reinforcement Learning. Instead of hoping the world stays the same, this method teaches the AI to prepare for the worst-case scenario. It asks: "What is the worst possible version of this environment, and how do I perform best even then?"

The Specific Challenge: The "Long Game"

The paper focuses on a specific type of reward called Average-Reward.

Discounted Reward (The Old Way): Imagine a video game where points you get today are worth 100%, but points you get tomorrow are worth 99%, and the day after that 98%. This makes the AI "myopic" (short-sighted). It cares more about immediate points than long-term survival.
Average Reward (The New Way): This is for the "long game." Think of a taxi driver. They don't care if they make \ $100 in the first hour and \$ 0 in the second; they care about their average earnings over a whole year. This paper teaches the AI to maximize that long-term average, even if the environment is chaotic.

The Problem with Previous Methods

The authors point out two major issues with existing solutions:

They need a map (Model-Based): Many methods require the AI to build a perfect map of the world first. If the map is wrong, the plan fails.
They are slow and theoretical: Some methods work in theory but take forever to learn, or they only guarantee success after infinite time (asymptotic), which isn't helpful when you have limited data.

The Solution: Robust Halpern Iteration (RHI)

The authors propose a new algorithm called Robust Halpern Iteration (RHI). Here is how it works, broken down into three simple concepts:

1. The "Black-Box" Oracle (The Magic Taste-Tester)

In the real world, the AI doesn't know the exact rules of the game. It only has a "generative model"—a simulator it can ask questions to.

The Challenge: To be robust, the AI needs to know the worst-case outcome of a move. But the simulator only shows the average outcome.
The Fix: The authors created a "Black-Box Oracle" (a tool they call R-SAMPLE). Think of this as a super-taste tester. If you give it a recipe (a move), it doesn't just taste the average flavor; it simulates thousands of variations (spicy, bland, burnt) and tells you the flavor of the worst possible version. This allows the AI to learn without needing to know the exact rules of the world beforehand.

2. The "Quotient Space" (Ignoring the Noise)

The math behind average rewards is tricky because there are two unknowns: the value of the move and the long-term average score. It's like trying to solve an equation with two missing numbers.

The Fix: The authors use a mathematical trick called a Quotient Space. Imagine you are measuring the height difference between two mountains. It doesn't matter if you measure from sea level or from the center of the earth; the difference is the same. They ignore the "absolute height" (the unknown average) and focus only on the "difference" (the relative value). This simplifies the math enough to solve the puzzle.

3. The "K-Order Multi-Level Monte-Carlo" (The Smart Estimator)

This is the paper's biggest technical innovation. To get that "worst-case" flavor from the taste tester, you need to run many simulations.

The Old Way: Previous methods were like trying to guess the average height of a crowd by measuring one person, then two, then three. They were slow and often had a "bias" (a systematic error), like always guessing slightly too tall.
The New Way: The authors created a K-Order Multi-Level Monte-Carlo (MLMC) estimator.
- Analogy: Imagine you want to know the average temperature of a lake.
  - Level 1: You take a quick, rough dip with your hand (low cost, high error).
  - Level 2: You take a more precise measurement with a thermometer (medium cost, medium error).
  - Level K: You use a high-tech satellite sensor (high cost, low error).
- The "K-Order" method cleverly combines these different levels. It takes the cheap, rough guesses and subtracts the errors they share with the expensive, precise guesses. The result? A super-accurate estimate that costs very little. This reduces the "bias" (error) significantly, allowing the AI to learn much faster.

The Results: Fast and Efficient

The paper proves that their new method (RHI) is incredibly efficient.

Sample Complexity: This is a fancy way of saying "how many times does the AI need to ask the simulator for help?"
The Claim: Their method needs roughly the same number of samples as the best possible theoretical methods that do have a perfect map of the world.
Why it matters: They achieved this without a map (Model-Free). They learned the worst-case scenario directly from data, using their smart "K-Order" estimator to clean up the noise.

Summary in One Sentence

The authors invented a new way to teach AI to play the "long game" in uncertain environments by using a smart, bias-correcting estimator that lets the AI learn the worst-case scenarios directly from data, without needing to build a perfect map of the world first.

Technical Summary: Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis

1. Problem Formulation

The paper addresses the challenge of Robust Reinforcement Learning (RL) under the average-reward criterion. While RL has achieved success in controlled environments, real-world deployment often suffers from the "Sim-to-Real" gap due to model mismatches, environmental perturbations, or adversarial attacks. Robust RL mitigates this by optimizing for the worst-case performance within an uncertainty set of transition dynamics.

The specific focus is on Distributionally Robust Average-Reward MDPs (RAMDPs). Unlike discounted reward settings, the average-reward criterion is essential for long-term steady-state performance in applications like queuing control and portfolio optimization. However, robust average-reward RL is significantly more challenging than its discounted counterpart due to:

Non-contractive operators: The robust Bellman operator is generally non-expansive rather than contractive, invalidating standard iterative convergence guarantees.
Dual unknowns: The robust Bellman equation involves two unknown variables: the value function (or bias) $Q$ and the optimal average reward $g^*_P$ .
Non-linearity: Estimating the worst-case expectation (support function) from nominal samples introduces bias, particularly in model-free settings.

Existing literature largely relies on asymptotic guarantees, model-based approaches requiring prior knowledge of problem parameters (like the bias span $H$ ), or reduction-based methods that suffer from sub-optimal sample complexity or require strong structural assumptions (e.g., irreducibility with specific contraction coefficients).

2. Methodology: Robust Halpern Iteration (RHI)

The authors propose Robust Halpern Iteration (RHI), a model-free algorithm designed to solve the robust Bellman equation without requiring prior knowledge of the MDP parameters.

2.1. Algorithmic Core

The RHI algorithm is inspired by Halpern Iteration from optimization literature, adapted to handle the specific challenges of robust average-reward RL:

Quotient Space Formulation: To address the "curse of dual variables" (the unknown $g^*_P$ ), the authors embed the problem into a quotient space $\mathbb{R}^{SA} / \sim$ , where vectors differing only by a constant shift are equivalent. This allows the algorithm to solve the proximal equation $T_P(Q) - Q = ce$ without explicitly knowing $g^*_P$ .
Halpern Update: Instead of standard value iteration, RHI uses a convex combination of the initialization and the operator update:
$[Q_{k+1}] = [(1 - \beta_{k+1})Q_0 + \beta_{k+1} T_P(Q_k)]$
where $\beta_k = k/(k+2)$ . This approach provides convergence guarantees for non-expansive operators without relying on contraction coefficients.

2.2. Black-Box Sampling Oracle (R-SAMPLE)

Since the robust operator $T_P$ is non-linear and involves a worst-case expectation, the authors introduce a black-box sampling oracle, R-SAMPLE. This oracle estimates the difference between robust support functions at consecutive iterations using only samples from the nominal kernel.

The oracle returns a random increment $D_k$ such that its expectation approximates the difference in the robust Bellman operator values.
The algorithm's sample complexity is derived based on the properties of this oracle (Lipschitz constant, bias, and sample cost).

2.3. K-Order Multi-Level Monte-Carlo (MLMC) Estimator

To concretely implement the R-SAMPLE oracle with low bias, the authors propose a K-order MLMC estimator.

Motivation: Standard plug-in estimators and vanilla MLMC estimators for robust support functions suffer from an $O(1/N)$ bias, leading to a sample complexity of $\tilde{O}(\epsilon^{-3})$ .
Mechanism: The K-order estimator constructs a linear combination of single-level estimators at different sample sizes ( $N_\ell = 2^\ell N_0$ ). By carefully choosing weights $w^{(K)}_\ell$ , the estimator cancels out the first $K$ terms of the bias expansion.
Result: This reduces the bias to $\tilde{O}(N_0^{-(K+1)})$ , allowing for a much tighter overall sample complexity.

3. Key Contributions

A Universal Model-Free Algorithm: RHI is the first model-free algorithm for robust average-reward RL that does not require prior knowledge of the robust optimal span $H$ or the mixing time, bypassing the limitations of reduction-based approaches.
K-Order MLMC Estimator: The authors design a novel estimator that significantly reduces bias compared to prior MLMC methods. This is crucial for achieving near-optimal sample complexity in the presence of non-linear robust support functions.
Finite Sample Complexity Analysis: The paper provides a rigorous finite-sample analysis for RHI under a generative model setting.
- For KL and $\chi^2$ divergence uncertainty sets, the sample complexity to find an $\epsilon$ -optimal policy is $\tilde{O}\left(SAH^2 \epsilon^{-(2+o(1))}\right)$ .
- For $\ell_p$ -norm and contamination sets, the complexity is $\tilde{O}\left(SAH^2 \epsilon^{-2}\right)$ .
- Here, $S$ and $A$ are the number of states and actions, and $H$ is the robust optimal bias span.
Parameter-Free Variant (PF-RHI): The authors propose a variant of RHI that uses a doubling trick to determine the number of iterations dynamically, removing the need to pre-specify the horizon based on the unknown parameter $H$ , while maintaining the same sample complexity.

4. Results and Theoretical Guarantees

Convergence: The exact RHI algorithm is proven to converge asymptotically, with the span of the Bellman residual and the sub-optimality gap vanishing as iterations increase.
Sample Complexity: The derived sample complexity for KL and $\chi^2$ sets asymptotically matches the best-known bounds for model-based approaches (e.g., Roch et al., 2025; Chen et al., 2025). The $o(1)$ term in the exponent represents a sub-polynomial penalty that vanishes as $\epsilon \to 0$ , distinguishing it from the $\epsilon^{-3}$ complexity of methods using standard MLMC.
Experimental Validation: Numerical experiments on the Garnet problem and various uncertainty sets (contamination, $\ell_\infty$ , $\ell_2$ ) demonstrate that RHI converges to the optimal robust average reward and that the K-order MLMC estimator effectively reduces bias compared to standard methods.

5. Significance and Claims

The paper claims to establish RHI as the state-of-the-art model-free algorithm for robust average-reward RL. Its significance lies in:

Bridging the Gap: It closes the gap between asymptotic guarantees and finite-sample analysis in robust average-reward RL.
Practicality: By being model-free and not requiring prior knowledge of $H$ , the algorithm is more practical for real-world deployment where such parameters are unknown.
Optimality: The sample complexity asymptotically matches the tightest bounds known for model-based methods, demonstrating that model-free approaches can achieve similar efficiency without the overhead of model construction.
Bias Reduction: The K-order MLMC design offers a fundamental improvement over previous robust RL estimators, resolving the issue of high sample complexity caused by unmitigated bias in non-linear function estimation.

The authors note that their analysis assumes a generative model (access to a simulator) to isolate statistical complexity. Extensions to online (exploration-exploitation) or offline (dataset-driven) settings are identified as future work. Additionally, the sub-polynomial gap in the sample complexity for KL/ $\chi^2$ sets is attributed to the inherent bias-variance tradeoff in estimating non-linear functionals, which remains an open challenge to fully eliminate in model-free settings.