🤖 machine learning

Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process

This paper establishes the first finite sample complexity guarantees for learning policies from a single trajectory in weakly communicating average-reward MDPs by introducing novel model-free methods that achieve $\widetilde{O}(1/\varepsilon^2)$ and $\widetilde{O}(1/\varepsilon^4)$ bounds without requiring restrictive assumptions like ergodicity or a generative model.

Original authors: Jongmin Lee, Ernest K. Ryu, Vaneet Aggarwal

Published 2026-06-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jongmin Lee, Ernest K. Ryu, Vaneet Aggarwal

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: Navigating a Maze Without a Map

Imagine you are trying to find the best route through a massive, endless maze. Your goal isn't just to get to the exit quickly (which is like a "discounted" reward where the future matters less), but to maximize your average speed over a very long, perhaps infinite, journey. This is what researchers call an Average-Reward Markov Decision Process (MDP).

In the past, figuring out the best strategy for these mazes usually required one of two things:

A "God Mode" Simulator: A magical tool that lets you teleport to any spot in the maze and see exactly what happens next (called a "generative model").
A Perfectly Mixed Maze: A maze where no matter where you start, you are guaranteed to eventually visit every single corner (called "ergodicity").

The Problem: Real life isn't a perfect maze, and we rarely have a "God Mode" simulator. Usually, we just have one single path we walked through the maze. We don't know the layout, and we might get stuck in a dead-end area (a "transient" state) before finally finding the main loop where the action happens.

The Paper's Breakthrough:
This paper says, "We can solve this using only that single path you walked, even if the maze is messy and has dead ends." They developed two new methods (one based on values, one based on policies) that can learn the best strategy just by analyzing that one journey, without needing a map or a simulator.

Key Concepts & Analogies

1. The "Transient" vs. "Recurrent" States

Imagine the maze has two types of areas:

Transient States (The Hallway): You walk through here once and never come back. It's a dead end or a one-way street.
Recurrent States (The Main Loop): Once you enter this area, you get stuck in a loop. You will keep visiting these spots over and over again forever.

The Challenge: If you start in the "Hallway," you might wander around for a while before you finally stumble into the "Main Loop." Previous methods struggled because they didn't know how to handle that initial wandering time or how to distinguish the loop from the dead ends.

The Paper's Solution:
The authors created a clever "scout" algorithm (Algorithm 1). It says: "Walk for a while. If you haven't seen a new spot in a long time, you've likely entered the Main Loop. Let's start taking notes only on the spots in that loop."
They mathematically proved that after a certain amount of walking, you are almost guaranteed to be in the Main Loop, and you can ignore the initial hallway wandering.

2. The "Anchoring" Technique (SAVIC)

The first method they propose is called SAVIC (Stochastic Anchored Value Iteration).

The Analogy: Imagine you are trying to find the center of a room by taking steps. If you just keep walking forward based on your last step, you might get dizzy and spin in circles.
The Trick: The "Anchoring" technique is like tying a rope to the spot where you started. Every time you take a new step, you pull yourself slightly back toward your starting point.
Why it works: This prevents the algorithm from going crazy or drifting too far off course. It keeps the learning process stable and ensures that, even with noisy data from a single path, the algorithm converges to the correct answer efficiently.

3. The "No-Map" Method (SAVIC+)

For mazes where every spot is part of the Main Loop (called "communicating" MDPs), the authors created SAVIC+.

The Innovation: Previous methods needed to know specific numbers about the maze beforehand (like "how long does it take to walk around the loop?").
The Paper's Claim: SAVIC+ is the first method that doesn't need to know these numbers in advance. It figures out the right amount of walking and learning as it goes, using a "doubling trick" (it tries a little, then twice as much, then twice that, until it's sure it has enough data).

4. The Policy Mirror Ascent (SCPMA)

The second method is SCPMA, which focuses on changing the strategy (the "policy") rather than just calculating values.

The Analogy: Imagine you are a chef trying to perfect a recipe. Instead of just tasting the soup (value), you are adjusting the ingredients (policy).
The "Clipping" Trick: To make sure the chef doesn't accidentally remove an essential ingredient (which would break the recipe), the algorithm "clips" the changes. It ensures that every ingredient has at least a tiny amount in the mix. This mathematical safety net guarantees that the learning process doesn't crash, even in messy mazes.

What Did They Actually Prove?

The paper provides mathematical guarantees (proofs) about how much "walking" (data) is needed to find a near-perfect strategy.

For the Value Method (SAVIC): They proved that to get a strategy that is very close to perfect (within a tiny error margin $\epsilon$ ), you need roughly $1/\epsilon^2$ steps of data.
For the Policy Method (SCPMA): They proved you need roughly $1/\epsilon^4$ steps.

Why is this a big deal?
Before this paper, no one had proven that you could get these specific guarantees using only one single trajectory in a messy, weakly-communicating maze. Most previous work assumed you had a magic simulator or a perfectly mixed maze. This paper removes those "magic" requirements and says, "Here is how you learn from a single, real-world walk."

Summary

This paper is like a guidebook for learning the best route through a complex, unpredictable maze using only the path you just walked. It introduces new mathematical tools (Anchoring, Clipping, and Stopping Times) to handle the messiness of real-world data, proving that you don't need a map or a simulator to learn effectively—you just need to know how to analyze the single journey you took.

Technical Summary: Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process

Problem Statement

The paper addresses the challenge of finding an $\epsilon$ -optimal policy in average-reward Markov Decision Processes (MDPs) using finite sample complexity guarantees derived from a single trajectory.

While extensive literature exists on the sample complexity of discounted cumulative-reward MDPs, analyses for average-reward MDPs have historically relied on restrictive assumptions. Existing works typically require either:

Generative models (access to a simulator that can reset to any state).
i.i.d. offline data.
Strong structural assumptions, such as ergodicity (where every policy induces a single recurrent class) or specific coverage conditions on the behavior policy.

The specific gap this work targets is the weakly communicating setting. In weakly communicating MDPs, the state space decomposes into a single recurrent class and a set of transient states under any "well-behaved" policy, but the system is not necessarily ergodic (transient states exist). Prior to this work, finite sample complexity analysis for average-reward RL from a single trajectory in this setting was unexplored.

Methodology

The authors develop a theoretical framework and novel model-free algorithms that leverage the structural properties of weakly communicating MDPs, specifically the recurrent-transient classification of states.

1. Structural Analysis of Single Trajectories

The core technical contribution is a stochastic analysis of a single trajectory generated by a behavior policy $\pi_b$ . The authors establish that:

Recurrent-Transient Invariance: For policies in the interior of the policy space ( $\Pi_+$ ), the classification of states into a single recurrent class ( $R$ ) and a transient set ( $T$ ) is invariant and determined solely by the transition kernel $P$ , not the specific policy choice.
Escaping Transient States: Using Markov's inequality and the strong Markov property, they prove that a trajectory starting in a transient state will reach the recurrent class $R$ within a finite hitting time ( $t_{hit}$ ) with high probability.
Covering the Recurrent Class: Once in $R$ , the trajectory covers all states in $R$ within a finite covering time ( $t_{cov}$ ).
i.i.d. Sampling via Stopping Times: By utilizing stopping times (specifically, the times at which the trajectory returns to a specific state $s$ ), the authors show that samples from a single trajectory can be treated as independent and identically distributed (i.i.d.) for the purpose of concentration inequalities (Lemma 2.3). This resolves the dependency issues inherent in single-trajectory analysis without requiring mixing time assumptions.

2. Value-Based Method: SAVIC

Stochastic Anchored Value Iteration (SAVIC) is a model-free value-based algorithm designed for weakly communicating MDPs. It operates in three stages:

Recurrent State Identification: The agent runs a behavior policy to escape transient states and collect a list of all recurrent states ( $R$ ) using Algorithm 1 (RECUR).
Anchored Iteration with Variance Reduction: Within the recurrent class, the algorithm performs Anchored Value Iteration (Anc-QI). Unlike standard VI, Anc-QI computes the next iterate as a convex combination of the Bellman update and the initial point ( $Q_0$ $Q_{0}$ ). This "anchor" term ensures non-asymptotic convergence.
- To achieve efficient sample complexity, the method employs a recursive sampling technique. Instead of estimating the full Bellman operator $T(Q_k)$ at each step, it estimates the difference $T(Q_k) - T(Q_{k-1})$ using variance-reduced sampling.
Policy Perturbation: Since the algorithm only optimizes over the recurrent class $R$ , the final policy is perturbed to ensure it is $\epsilon$ -optimal over the entire state space $S$ , including transient states.

3. Model-Free Method without Prior Knowledge: SAVIC+

For communicating MDPs (where $S=R$ , i.e., no transient states), the authors introduce SAVIC+.

This variant eliminates the need for prior knowledge of problem-dependent constants (such as $t_{hit}$ , $t_{cov}$ , or the minimum stationary distribution probability $d_{min}$ ).
It employs a doubling trick and an explicit stopping rule based on the empirical Bellman residual error ( $\|Q - TQ\|_{sp}$ ).
It uses Algorithm 4 (SAMPLE+) to automatically collect samples until a sufficient count is reached for every state-action pair.

4. Policy-Based Method: SCPMA

Stochastic $\alpha$ -clipped Policy Mirror Ascent (SCPMA) is a policy gradient method for weakly communicating MDPs.

It utilizes a novel policy evaluation algorithm (SAVIPE) that approximates the state-action value function using the same anchoring and variance-reduction mechanisms as SAVIC.
The policy update follows the Policy Mirror Ascent framework but applies $\alpha$ -clipping to ensure the policy remains in the interior of the policy space ( $\Pi_\alpha$ ). This clipping is crucial for bounding the coefficients in the sample complexity analysis.
The method supports both constant and adaptive step sizes.

Key Results

The paper establishes the first finite sample complexity guarantees for average-reward MDPs from a single trajectory in weakly communicating settings.

SAVIC (Value-Based):
- Achieves a sample complexity of $\tilde{O}(1/\epsilon^2)$ for finding an $\epsilon$ -optimal policy.
- The bound depends on the hitting time ( $t_{hit}$ ), covering time ( $t_{cov}$ ), the span of the optimal value function ( $\|Q^*\|_{sp}$ ), and the inverse of the minimum stationary distribution probability ( $1/d_{min}^\pi$ ).
SAVIC+ (Model-Free, No Prior Knowledge):
- For communicating MDPs, SAVIC+ achieves $\tilde{O}(1/\epsilon^2)$ sample complexity.
- Crucially, it requires no prior knowledge of problem-dependent quantities (like $t_{cov}$ or $d_{min}$ ) to set parameters.
SCPMA (Policy-Based):
- Achieves a sample complexity of $\tilde{O}(1/\epsilon^4)$ (with constant step size) or improved rates with adaptive step sizes.
- This represents the first finite sample complexity guarantee for policy gradient methods in weakly communicating MDPs from a single trajectory.

Significance and Claims

The authors claim that this work provides the first finite sample complexity guarantees for learning in average-reward MDPs from a single trajectory in the weakly communicating setting.

Breaking Ergodicity Assumptions: Unlike prior works that required ergodicity (where all states are recurrent), this work handles the more general weakly communicating case where transient states exist.
Single Trajectory Realism: The results move beyond the unrealistic generative model or i.i.d. data assumptions, providing guarantees for the standard online learning setting where an agent interacts with the environment sequentially.
Model-Free Efficiency: The proposed methods are model-free and, in the case of SAVIC+, do not require prior knowledge of the MDP's mixing properties or stationary distribution, making them more practical for unknown environments.
Theoretical Machinery: The paper introduces novel theoretical tools, including the use of stopping times and strong Markov properties to generate i.i.d. samples from a single trajectory in weakly communicating MDPs, which enables the application of concentration inequalities previously reserved for i.i.d. settings.

The paper concludes by noting that while the value-based method achieves a tighter $\tilde{O}(1/\epsilon^2)$ bound compared to the policy-based method's $\tilde{O}(1/\epsilon^4)$ , closing this gap and extending these results to parameterized function approximation settings remain open future directions.