🤖 machine learning

Bridging the Gap between Newton-Raphson Method and Regularized Policy Iteration

This paper establishes that Regularized Policy Iteration is formally equivalent to the Newton-Raphson method applied to smoothed Bellman equations, thereby proving its local quadratic convergence (which is dimension-free for Shannon entropy) and enabling the development of a new third-order convergent algorithm for regularized Markov decision processes.

Original authors: Zeyang Li, Chuxiong Hu, Yunan Wang, Guojian Zhan, Jie Li, Yao Lyu, Shengbo Eben Li

Published 2026-07-17

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Zeyang Li, Chuxiong Hu, Yunan Wang, Guojian Zhan, Jie Li, Yao Lyu, Shengbo Eben Li

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 computers learn to make decisions by playing a never-ending game of trial and error. This is the heart of Reinforcement Learning (RL), a branch of artificial intelligence that powers everything from video game bots to self-driving cars. At its core, RL is about an agent trying to figure out the best move to make in any given situation to get the most reward over time. To solve this, mathematicians use a famous rule called the Bellman equation, which acts like a map showing the value of every possible move. However, this map has a tricky, jagged edge: it involves a "max" function that picks the single best option, making the math sharp and difficult to smooth out for computers to solve quickly.

To fix this jagged edge, researchers often add a "regularizer." Think of this as a gentle nudge or a soft constraint that encourages the computer to explore different options rather than just blindly sticking to the one it thinks is best right now. It's like telling a student, "Don't just memorize the answer; try to understand the logic behind a few different solutions." This technique, known as Regularized Policy Iteration, has been incredibly successful in practice, leading to powerful algorithms used today. But while these algorithms work great in the real world, scientists have been scratching their heads trying to understand exactly why they work so well and how fast they should theoretically converge to the perfect solution.

This paper steps in to clear up that mystery. The authors discovered a hidden bridge connecting these modern, "soft" learning algorithms to a classic, old-school math tool called the Newton–Raphson method. You can think of the Newton–Raphson method as a super-fast way to find the bottom of a valley by using the slope of the ground to take giant, precise steps. The paper proves that when you add those "soft" regularizers to the Bellman equation, the resulting algorithm is mathematically identical to this powerful Newton method. This isn't just a vague similarity; it's a strict, formal equivalence. Because of this discovery, the authors can prove that these algorithms zoom toward the solution with quadratic convergence, meaning the error shrinks incredibly fast (like squaring a tiny number to make it even tinier) once they get close enough. They also showed that if you don't solve every step perfectly (which is common in real life), the algorithm still works, just at a slightly slower, predictable speed. Finally, inspired by this connection, they built a brand-new, even faster algorithm that takes a "third-order" leap, converging even quicker than the standard methods, and proved through computer simulations that it actually saves time in practice.

The Story of the Smoothed Path

Let's dive deeper into the adventure. Imagine you are trying to find the lowest point in a vast, foggy landscape (the optimal solution). The terrain is tricky because it has sudden cliffs and sharp peaks (the "max" operator in the Bellman equation). Traditional methods, like Policy Iteration, are like a hiker who stops at every spot, looks around, and decides to walk in a straight line toward the best visible direction. This works, but it can be slow and jerky.

The paper introduces a twist: Regularization. This is like pouring a layer of soft, smooth gel over the entire landscape. The sharp cliffs become gentle slopes. Suddenly, the "max" operator, which used to be a jagged cliff edge, becomes a smooth curve. This is the Smoothed Bellman Equation.

The authors' big "Aha!" moment was realizing that navigating this smooth, gel-covered landscape is exactly what the Newton–Raphson method does. In the world of math, Newton's method is famous for its speed. If you are close to the solution, it doesn't just take a step; it takes a step that is perfectly calculated to land you much closer, doubling the number of correct digits with every move. The paper proves that when you use Regularized Policy Iteration (RPI), you are secretly doing exactly this. You aren't just guessing; you are performing a precise Newton step on a smoothed version of the problem.

The Speed of the Solution

Why does this matter? Because speed is everything in computing. The authors proved that RPI enjoys local quadratic convergence. In plain English, this means that once the algorithm gets "close enough" to the right answer, it doesn't just get better slowly; it gets better explosively fast. If you are off by a tiny bit, the next step makes you off by a tiny bit squared, which is practically zero.

The paper also tackled a very real-world problem: what if you can't calculate the perfect step every time? In the real world, computers are busy, and sometimes you have to stop the calculation early. This is called inexact policy evaluation. The authors showed that even if you take a shortcut and only do a few calculation steps (let's call this number $M$ ) instead of the full infinite loop, the algorithm still works. It behaves like an inexact Newton method. They proved that the speed of this shortcut depends on how many steps you take ( $M$ ). The more steps you take, the faster you get, with the error shrinking at a rate of $\gamma^M$ (where $\gamma$ is a discount factor between 0 and 1). This explains why doing a little bit more work in each step pays off significantly.

The New Super-Algorithm

But the authors didn't stop at explaining the old ways. They asked, "If Newton's method is so great, can we make it even better?" In the world of math, there are "higher-order" Newton methods that use even more information to take even bigger, smarter leaps.

Inspired by this, they designed a new algorithm called Third-Order Regularized Policy Iteration (T-RPI). Imagine that while the standard method takes one giant step, T-RPI takes a step, checks its footing, and then takes a second, refining step using the same information before moving on. This allows it to achieve third-order convergence. This is a fancy way of saying it gets to the solution even faster than the quadratic method. The error doesn't just square; it cubes, vanishing almost instantly once you are in the right neighborhood.

The Proof in the Pudding

The paper doesn't just rely on math on a whiteboard; they tested it. They ran numerical experiments with a simulated environment involving 100 states and 20 actions.

They confirmed that the standard RPI algorithm indeed speeds up quadratically, matching their theoretical predictions.
They confirmed that the RMPI (the version with shortcuts) speeds up linearly, but the speed depends exactly on how many steps ( $M$ ) they took, validating the $\gamma^M$ rule.
Most excitingly, they tested their new T-RPI algorithm. They found that it reached the same level of accuracy in fewer steps than the standard method. Even better, because they were clever about how they reused calculations (solving two equations with the same "skeleton" at once), the new algorithm actually finished the job faster in real-world clock time, beating the standard method by about 1.3 times.

What This Means

This paper is a bridge between two worlds: the practical, "soft" algorithms that power modern AI and the rigorous, "hard" math of numerical analysis. By proving that these modern algorithms are just Newton's method in disguise, the authors have given us a powerful new lens to understand them. They showed us why they are fast, how to make them even faster, and provided a blueprint for building the next generation of decision-making AI. It's a reminder that sometimes, the most advanced technology is just a classic idea wearing a new, smoother coat.

Technical Summary: Bridging the Gap between Newton–Raphson Method and Regularized Policy Iteration

Problem Statement
Regularization has become a cornerstone of modern reinforcement learning (RL), with Regularized Policy Iteration (RPI) serving as a fundamental scheme for solving Regularized Markov Decision Processes (RMDPs). While algorithms like Soft Actor-Critic (SAC) have demonstrated empirical success, the theoretical underpinnings of RPI remain unclear. Specifically, the connection between RPI and classical numerical optimization techniques, such as the Newton–Raphson (NR) method, has not been formally established. Furthermore, existing convergence analyses for RPI are often limited to global linear convergence or rely on specific assumptions (e.g., nondegeneracy conditions) that restrict their applicability to general strongly convex regularizers. There is a need for a unified theoretical framework that explains the convergence behavior of RPI and inspires the design of accelerated algorithms.

Methodology
The paper establishes a formal equivalence between RPI and the standard Newton–Raphson method applied to a smoothed Bellman equation. The core methodology involves the following steps:

Smoothing the Bellman Equation: The authors utilize the Legendre–Fenchel transform to replace the non-smooth $\max$ operator in the Bellman equation with a smoothed $\max$ operator induced by a strongly convex regularizer $\Omega$ . This results in a smooth, differentiable system of equations, $F_\Omega(q) = 0$ .
Jacobian Analysis: The paper derives the Jacobian of this smoothed Bellman equation, proving that its inverse always exists, is negative, and is bounded. Crucially, the Jacobian is shown to be Lipschitz continuous.
Equivalence Proof: By decomposing the smoothed Bellman equation into an affine transformation involving its Jacobian, the authors prove that a single step of RPI is mathematically identical to a single step of the Newton–Raphson method applied to $F_\Omega(q)$ .
Extension to Inexact Evaluation: The analysis is extended to Regularized Modified Policy Iteration (RMPI), where policy evaluation is performed via truncated iterations. This is shown to be equivalent to an inexact Newton method where the Newton step is solved with a specific error term dependent on the number of operator steps $M$ .
Higher-Order Algorithm Design: Leveraging the NR perspective, the authors propose a "Third-Order Regularized Policy Iteration" (T-RPI). This algorithm reuses the Jacobian from the current iterate to perform an additional correction step, aiming for third-order local convergence.

Key Contributions and Results

Formal Equivalence: The paper proves that RPI is strictly equivalent to the standard Newton–Raphson method applied to the smoothed Bellman equation. This is the first result to reveal this formal connection, providing a unified framework for analyzing RPI.
Local Quadratic Convergence: The authors prove that RPI enjoys local quadratic convergence in a neighborhood of the optimal value.
- For general $\mu$ -strongly convex regularizers, the convergence rate depends on the Lipschitz constant of the Jacobian.
- Notably, for Shannon entropy (where $\mu=1$ ), the convergence guarantee is dimension-free. This represents a substantial improvement over prior results for soft policy iteration, which relied on nondegeneracy assumptions and yielded bounds dependent on the state space dimension.
Asymptotic Linear Convergence for RMPI: The paper establishes that RMPI is equivalent to an inexact Newton method. It derives an asymptotic linear convergence rate of $\gamma^M$ , where $\gamma$ is the discount factor and $M$ is the number of operator steps used in policy evaluation. This result theoretically quantifies the benefit of performing more evaluation steps, a nuance missed by previous global linear convergence analyses (which only showed a rate of $\gamma$ ).
Third-Order Algorithm (T-RPI): Inspired by higher-order Newton schemes, the authors propose T-RPI. Theoretical analysis demonstrates that T-RPI achieves local cubic convergence.
- The algorithm reuses the LU decomposition of the shared coefficient matrix, making the additional computational cost per iteration negligible compared to standard RPI.
- Numerical experiments confirm that T-RPI achieves faster wall-clock time convergence than standard RPI.

Significance and Claims
The paper claims to advance the theoretical understanding of regularization in RL by unifying RPI with classical numerical analysis. By framing RPI as a Newton method, the authors provide a rigorous explanation for the fast local convergence observed in practice.

The significance of these results lies in:

Unification: Providing a single theoretical lens to analyze diverse regularized algorithms.
Stronger Guarantees: Offering dimension-free quadratic convergence guarantees for Shannon entropy without requiring nondegeneracy assumptions, addressing limitations in prior work.
Algorithmic Innovation: Motivating and validating the design of T-RPI, which offers practical speedups by leveraging higher-order convergence properties without significant computational overhead.

The authors conclude that their results open new avenues for efficient algorithm design in reinforcement learning, moving beyond ad-hoc analyses to a principled, optimization-theoretic foundation.

The Story of the Smoothed Path

The Speed of the Solution

The New Super-Algorithm

The Proof in the Pudding

What This Means

More like this