🤖 machine learning

Finite-Time Analysis of the Natural Policy Gradient in Finite-Horizon Markov Decision Processes

This paper establishes the first finite-time convergence guarantees for exact Natural Policy Gradient in finite-horizon Markov Decision Processes with known dynamics, demonstrating sublinear convergence with constant step sizes and linear convergence with specific increasing step sizes.

Original authors: Asha Barua, Sajad Khodadadian

Published 2026-07-28

📖 9 min read🧠 Deep dive

CC BY 4.0

Original authors: Asha Barua, Sajad Khodadadian

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 a world where you are teaching a robot to navigate a maze, a video game character to master a boss fight, or an AI to write a perfect story. This is the realm of Reinforcement Learning (RL), a branch of artificial intelligence where an agent learns by trial and error, trying to maximize its "score" or reward. Think of it like a dog learning tricks: it gets a treat for a good move and a gentle "no" for a bad one. Over time, the dog figures out the best sequence of actions to get the most treats.

In this world, there are two main ways to set up the game. Sometimes, the game goes on forever, and the goal is to get the best average score over an infinite amount of time. But often, the game has a strict finish line—a specific number of steps, like a 100-level dungeon or a 30-second sprint. This is called a finite-horizon setting. The challenge here is that the "best move" changes depending on how much time is left. If you have 100 steps left, you might take a risky shortcut; if you only have 5 steps left, you play it safe. This makes the math much trickier because the rules of the game shift as the clock ticks down. Scientists have long known how to teach agents in the "forever" games, but figuring out the exact speed at which they learn in these "countdown" games has been a missing piece of the puzzle.

This paper steps into that gap to analyze a specific, powerful learning method called Natural Policy Gradient (NPG). You can think of NPG as a very smart, cautious coach. Unlike a basic coach who just says, "Do more of what worked, less of what didn't," NPG understands the "shape" of the learning space. It knows that some directions in the learning process are steeper or more curved than others, so it adjusts its steps to avoid wobbling or overshooting the goal. This method is the secret sauce behind some of the most famous AI successes in gaming and robotics today.

The authors of this paper asked a simple but difficult question: How fast does this smart coach actually learn when the game has a hard stop? They didn't just guess; they did the heavy mathematical lifting to prove exactly how the error shrinks over time. They found that if the coach takes steady, unchanging steps, the learning speed is decent but slows down over time, following a specific pattern related to the length of the game. However, if the coach is allowed to take bigger and bigger steps as it gets closer to the finish line, the learning speed explodes into a rapid, geometric sprint. They proved these speeds mathematically for simple, perfect-world scenarios and showed through simulations that real-world tests match their predictions.

The Story of the Countdown Coach

Let's dive into the details of this research, which focuses on Finite-Horizon Markov Decision Processes. In plain English, this is just a fancy name for a game with a fixed number of turns, a set of possible states (like positions on a board), and a set of actions (like moving left or right). The "horizon" is simply the total number of turns before the game ends.

The researchers studied an algorithm called Natural Policy Gradient (NPG). Imagine you are trying to find the highest peak in a foggy mountain range. A standard approach might be to take a step in the direction that feels steepest. But NPG is like having a map that knows the terrain is bumpy; it takes a step that accounts for the curvature of the ground, ensuring you don't slip or take a step that is too big for the terrain. This method is the foundation for popular tools like TRPO and PPO, which have helped AI beat humans at complex games.

The big problem the paper tackles is that most previous math proofs for NPG only worked for games that go on forever. But in the real world, many tasks have a deadline. When the game ends after $H$ steps, the "best move" isn't the same at step 1 as it is at step $H-1$ . This creates a domino effect: changing your strategy for step 1 changes where you end up at step 2, which changes the best move for step 2, and so on. It's a tangled web of dependencies that makes the math very hard.

The Two Speeds of Learning

The paper provides the first "finite-time" guarantees for this algorithm in these countdown scenarios. This means they didn't just say, "It will eventually get there." They said, "Here is exactly how close it will be after $t$ steps." They discovered two distinct ways the algorithm can behave, depending on how the "step size" (the size of the learning step) is chosen.

1. The Steady Walker (Constant Step Size)
First, the authors looked at what happens if the coach takes the same size step every single time, no matter how close it is to the finish. They proved that in this scenario, the algorithm converges sublinearly.

What does that mean? Imagine you are walking toward a wall. In the beginning, you take big strides. As you get closer, you slow down. The error (the distance between your current score and the perfect score) shrinks, but it gets slower and slower. The paper proves that after $t$ iterations, the error is roughly proportional to $O(H^2/t)$ .

Here, $H$ is the length of the game (the horizon), and $t$ is the number of steps the algorithm has taken. The $H^2$ part is crucial: it means that if your game is twice as long, the learning gets four times harder (or slower) to master with this steady approach. The authors showed that for a game of length $H$ , you need roughly $2(H-h+1)^2/\epsilon$ steps to get within a tiny error margin $\epsilon$ of the perfect score at a specific point $h$ in the game. They also extended this proof to "Linear MDPs," a more complex setting where the game rules are described by a mathematical formula rather than a giant lookup table, showing the same slow-but-steady speed applies there too, provided you have a perfect "oracle" (a magical helper) to calculate the values exactly.

2. The Sprinter (Increasing Step Size)
Next, the authors asked: "What if we let the coach take bigger steps as it gets closer to the end?" This is where things get exciting. They proved that if you increase the step size in a specific way, the algorithm switches from a slow walk to a geometric (linear) convergence.

Geometric convergence is like a rocket ship. Instead of slowing down, the error gets cut in half (or by a fixed percentage) with every single step. The paper proves that with the right schedule, the error shrinks at a rate of $O((1 - 1/\vartheta_\rho)^t)$ .

The term $\vartheta_\rho$ is a "mismatch coefficient" that depends on how the game is set up and how the starting positions are distributed. In the best-case scenario, where the game is perfectly balanced, this coefficient equals the horizon length $H$ . This means the error shrinks by a factor of $(1 - 1/H)$ every step.

To make this practical, the authors proposed a "horizon-only robust schedule." This is a rule for how to increase the step size that only depends on the length of the game ( $H$ ), not on the messy details of the specific game. The rule is:
$\eta_t = \eta_0 \left( \frac{H}{H-1} \right)^t$
This formula tells the coach exactly how much to grow its step size at every turn. The paper proves that using this rule guarantees the fast, geometric speed, even without knowing the specific details of the game's "mismatch."

The Simulation Proof

Math proofs are great, but do they hold up in practice? The authors ran computer simulations to check their theories.

In the first experiment, they created a random game with 15 locations, 4 actions, and a 7-step horizon. They let the algorithm run with a constant step size. The results matched their theory perfectly: the error dropped steadily, following the $O(1/t)$ curve. When they looked at different points in the game (horizons), the error was smaller for later steps, just as the math predicted, because there was less "future" to mess up.

In the second experiment, they set up a game where they knew the "mismatch coefficient" was exactly equal to the horizon length ( $H=7$ ). They used the increasing step size schedule. The results were dramatic. The error didn't just drop; it plummeted geometrically. The graph showed the error shrinking by a factor of roughly $(1 - 1/7)$ every step, confirming the "sprinter" behavior. They also tested this on different starting points in the game, and the math held up every time.

Why This Matters

This paper is a foundational step. It doesn't claim to have solved every problem in AI, nor does it claim to work with messy, real-world data where you don't know the rules perfectly (that's a job for future research). Instead, it provides the theoretical bedrock. It proves that for the "perfect world" version of these countdown games, we know exactly how fast the Natural Policy Gradient learns.

It tells us that if we want fast results in short games, we shouldn't just take steady steps; we need to be brave and increase our step size as we go. It also highlights a trade-off: the longer the game, the harder it is to learn quickly with a steady pace, but the "sprinter" strategy can overcome that difficulty if tuned correctly.

By establishing these rates, the authors have given future researchers a baseline. Now, when someone builds a new AI that learns from imperfect data (where they have to guess the rules), they can compare their new method against these proven "perfect world" speeds to see how much they are losing due to the noise and uncertainty. It's a map of the territory, showing us exactly how fast the smartest coaches can run when the path is clear.

Technical Summary: Finite-Time Analysis of the Natural Policy Gradient in Finite-Horizon Markov Decision Processes

1. Problem Statement

This paper addresses the lack of finite-time convergence guarantees for the Natural Policy Gradient (NPG) algorithm in finite-horizon Markov Decision Processes (MDPs) with known dynamics. While NPG and its variants (e.g., TRPO, PPO) are empirically successful, existing theoretical analyses primarily focus on infinite-horizon discounted MDPs.

The finite-horizon setting presents two specific structural challenges that complicate standard analysis:

Non-stationarity: Optimal policies are generally non-stationary, consisting of a sequence of horizon-dependent decision rules. Updating a decision rule at horizon $h$ alters state distributions at subsequent horizons ( $h+1, \dots, H$ ), creating coupling across the horizon.
Absence of Contraction: Unlike infinite-horizon settings where a discount factor induces strict contraction, finite-horizon MDPs lack an analogous discount-induced contraction mechanism. Policies, transition kernels, and value functions depend explicitly on the horizon index.

The authors study exact NPG in this setting, assuming known, horizon-dependent transition kernels and non-stationary policies.

2. Methodology

The paper analyzes two distinct step-size regimes for the NPG update, which is formulated equivalently as a KL-based Policy Mirror Descent (PMD) update.

2.1 Constant Step Size Regime

Setting: Tabular MDPs and Linear MDPs (under an exact population-projection oracle).
Update Rule: The policy is updated using a constant step size $\eta > 0$ via the multiplicative form:
$\pi_{t+1}^h(a|s) = \frac{\pi_t^h(a|s) \exp(\eta Q_{\pi_t, h}(s, a))}{Z_t^h(s)}$
Analysis Tools:
- Performance Difference Lemma: Used to relate value differences to advantage functions.
- Lower Bound on Improvement: Establishes that the value function is non-decreasing along the policy sequence.
- Potential Function: A value potential bounded by quadratic terms in the horizon length is used to derive the convergence rate.
Linear MDP Extension: The authors define an exact oracle regime where the linear Q-NPG update induces the exact same policy-space dynamics as the tabular NPG update, provided the projection distribution has full support.

2.2 Increasing Step Size Regime

Setting: Tabular MDPs.
Update Rule: The update uses an iteration-dependent step size $\eta_t > 0$ , analyzed via the variational (KL-based) form of PMD.
Key Technical Innovation: To address the lack of policy-independent lower bounds on visitation distributions for $h > 1$ $h > 1$ , the authors introduce a global multi-start objective $J(\pi)$ $J (π)$ .
- This objective averages returns over random starting horizons $H_0 \sim \text{Unif}\{1, \dots, H\}$ .
- This construction ensures a policy-independent lower bound on visitation measures, analogous to the role of the discount factor in infinite-horizon settings.
Convergence Analysis:
- Defines a multi-start distribution mismatch coefficient $\vartheta_\rho$ dependent on the initial state distribution $\rho$ and the optimal policy $\pi^\star$ .
- Derives a recurrence relation for the optimality gap involving $\vartheta_\rho$ and the step size growth condition.
- Proposes a horizon-only robust step size schedule $\eta_t = \eta_0 (H/(H-1))^t$ that satisfies the required growth condition without requiring knowledge of the problem-dependent constant $\vartheta_\rho$ .

3. Key Contributions and Results

3.1 Sublinear Convergence (Constant Step Size)

Tabular MDPs: The paper proves that NPG with a constant step size achieves an optimality gap of order $O(H^2/t)$ after $t$ iterations. Specifically, for a fixed horizon $h$ , the gap is bounded by:
$V^{\pi^\star, h}(s) - V^{\pi_T, h}(s) \leq \frac{(H-h+1)\log|A|}{\eta T} + \frac{(H-h+1)^2}{T}$
Linear MDPs: Under an exact population-projection oracle with a full-support distribution, the linear Q-NPG update induces the same policy-space dynamics as the tabular case, recovering the same $O(H^2/t)$ rate.

3.2 Geometric (Linear) Convergence (Increasing Step Size)

Convergence Rate: With increasing step sizes, the algorithm achieves a geometric convergence rate of $O((1 - 1/\vartheta_\rho)^t)$ , where $\vartheta_\rho > 1$ is a problem-dependent distribution-mismatch coefficient.
Robust Schedule: The authors demonstrate that the horizon-only schedule $\eta_t = \eta_0(H/(H-1))^t$ satisfies the growth condition required for geometric convergence.
Best-Case Rate: In the best case where $\vartheta_\rho = H$ , the rate becomes $O((1 - 1/H)^t)$ .
Scope: This geometric bound specifically controls the suboptimality at the initial horizon ( $h=1$ ), derived via the multi-start objective reduction.

3.3 Numerical Illustration

Simulations on randomly generated and structured finite-horizon MDPs validate the theoretical bounds:

Constant Step Size: Empirical error decreases monotonically and follows the predicted $O(1/t)$ scaling, staying below the theoretical upper bound.
Increasing Step Size: Empirical error exhibits geometric decay consistent with the theoretical contraction factor, particularly in instances where the mismatch coefficient matches the theoretical lower bound.

4. Significance and Claims

The paper claims to provide the first finite-time convergence guarantees for exact NPG in finite-horizon MDPs with known, horizon-dependent dynamics.

Theoretical Baseline: By establishing sublinear and geometric rates for the exact (tabular/oracle) setting, the work provides a necessary baseline for future research into regularized and sample-based finite-horizon extensions.
Addressing Structural Difficulties: The analysis explicitly tackles the non-stationarity and lack of contraction inherent to finite-horizon problems, introducing the multi-start objective as a novel tool to decouple horizon dependencies for convergence analysis.
Practical Relevance: While the analysis assumes known dynamics (tabular) or exact oracles (linear), the results clarify the theoretical behavior of the update rules underlying practical algorithms like TRPO and PPO in sequential planning and robotic manipulation contexts.

The authors note that the $H^2$ factor in the sublinear rate and the $H$ -factor losses in the geometric reduction are derived from their proof techniques; whether these dependencies are unavoidable remains an open problem. Furthermore, the paper explicitly states that it does not establish end-to-end computational guarantees for linear MDPs (as oracle implementation may still require full model access) and leaves sample-based finite-time guarantees for future work.