🤖 machine learning

Second-Order Actor-Critic Methods for Discounted MDPs via Policy Hessian Decomposition

This paper proposes a stable and computationally efficient second-order actor-critic method for discounted MDPs that utilizes Hessian-vector products by leveraging a two-timescale framework to justify treating the action-value function as locally constant during actor updates.

Original authors: Sanjeev Manivannan, Shuban V

Published 2026-05-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sanjeev Manivannan, Shuban V

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 trying to teach a robot how to walk, drive a car, or balance a pole. In the world of Artificial Intelligence, this is called Reinforcement Learning. The robot (the "agent") tries different actions, gets rewards for doing well, and learns from its mistakes to get better over time.

The paper you shared is about a new, smarter way to teach these robots. It tackles a specific problem: How do we make learning faster and more stable without getting overwhelmed by the math?

Here is the breakdown using simple analogies:

1. The Problem: The "Blind Hiker" vs. The "Map Reader"

Most current methods (called First-Order methods) are like a blind hiker trying to find the top of a mountain.

How they work: They take a step, feel if the ground is going up or down, and take another step in that direction.
The flaw: They don't know the shape of the mountain. Is it a gentle slope? Is it a sharp cliff? Is there a valley right next to them? Because they only feel the immediate slope, they often zigzag, take tiny steps, or get stuck in small dips, making the journey very slow.

Second-Order methods are like a map reader.

How they work: They look at the curvature of the land. They know, "Ah, this is a steep valley; I should take a big, straight step to the top." This usually gets them to the finish line much faster.
The flaw: Calculating the exact shape of the entire mountain is incredibly expensive and slow. It requires so much computing power that it's often impossible to do in real-time. Plus, if the map is slightly wrong (due to noisy data), the robot might take a giant step off a cliff.

2. The Solution: The "Two-Speed Team"

The authors propose a clever trick to get the benefits of the "Map Reader" without the heavy cost or the danger of falling off cliffs. They use a Two-Timescale Actor-Critic framework.

Think of this as a team of two people working together:

The Critic (The Fast Learner): This person is very quick. They constantly watch the robot and instantly say, "That move was good!" or "That move was bad!" They update their opinion very fast.
The Actor (The Slow Learner): This is the robot making the actual moves. They change their strategy slowly.

The Magic Insight: Because the Critic updates so fast, by the time the Actor makes a move, the Critic's opinion is already "settled." The Critic is so stable that, for a split second, we can pretend the Critic's opinion doesn't change just because the Actor moved.

This allows the math to ignore a very messy, complicated part of the equation (called the "interaction term") that usually causes the "Map Reader" to crash. It simplifies the map, making it safe and fast to use.

3. The Two New Methods: ACGN1 and ACGN2

Using this "Two-Speed Team" idea, the authors created two specific ways to calculate the "Map":

ACGN1 (The "Full Picture" Approach): This method tries to use all the available curvature information. It looks at the slope and the shape of the hill.
- Pros: It has a lot of information.
- Cons: It's a bit noisy and computationally heavy. It's like trying to read a map while it's shaking in the wind.
ACGN2 (The "Pure Shape" Approach): This method is more conservative. It ignores the "slope" part of the math and focuses only on the intrinsic shape of the policy (the curvature).
- Pros: It is much more stable and reliable. It's like looking at a steady, clear map.
- Cons: It might miss a tiny bit of detail, but it rarely makes a catastrophic mistake.

4. What Did They Find?

The authors tested these methods on various video-game-like tasks (like balancing a pole on a cart or landing a spaceship).

The Result: Both new methods (ACGN1 and ACGN2) learned faster and used fewer training attempts (samples) than the old "blind hiker" methods.
The Trade-off: The new methods take a little more computer time per step to calculate the map, but because they learn so much faster, they finish the whole job much sooner.
The Winner: In simple tasks, ACGN2 was the star. It was the most stable and converged the quickest. In very complex, high-dimensional tasks (like a humanoid robot walking), both methods worked well, though ACGN2 showed a bit more variation, while ACGN1 was very steady.

Summary

The paper says: "We found a way to give robots a 'curvature-aware' map (Second-Order) that helps them learn faster. We made it safe and efficient by using a 'fast critic' to stabilize the math. This allows robots to learn complex skills with fewer mistakes and less wasted time."

They didn't claim this fixes medical issues or controls real-world traffic yet; they just proved it works better on standard robot simulation benchmarks than the old methods.

Technical Summary: Second-Order Actor-Critic Methods for Discounted MDPs via Policy Hessian Decomposition

Problem Statement

Reinforcement learning (RL) in large-scale settings faces two primary challenges: the curse of dimensionality rendering tabular methods intractable, and the limitations of first-order policy search methods. While actor-critic approaches mitigate value approximation variance, they rely on first-order updates that ignore the curvature of the objective function. This leads to slow convergence and sensitivity to policy parameterization. Conversely, second-order optimization offers curvature-aware updates that accelerate convergence but are rarely applied in RL due to the prohibitive computational complexity ( $O(d^3)$ ) of Hessian estimation and the instability caused by high-variance interaction terms in the policy Hessian decomposition.

Existing literature typically addresses value estimation and curvature incorporation independently. This paper identifies a gap: second-order approximations are often unstable due to high-variance curvature components, and there is a lack of a unified framework that stabilizes these approximations while maintaining computational efficiency in discounted Markov Decision Processes (MDPs).

Methodology

The authors propose a Second-Order Two-Timescale Actor-Critic (SOTTAC) framework that leverages the full curvature information of the objective function through a structured approximation of the Policy Hessian.

1. Policy Hessian Decomposition

The objective function $J(\theta)$ is analyzed via its second-order derivative. The Hessian $H(\theta)$ is decomposed into four components (Theorem 1):

$H_1$ (Outer-product term): A Fisher-like term involving the outer product of the policy gradient.
$H_2$ (Intrinsic curvature): The Hessian of the log-policy, capturing the intrinsic geometry of the policy distribution.
$H_{12}$ and $H_{12}^\top$ (Interaction terms): Terms involving the gradient of the state-action value function $Q$ with respect to policy parameters ( $\nabla_\theta Q$ ).

The authors identify that $H_{12}$ introduces significant variance and computational coupling, making direct second-order updates unstable.

2. Two-Timescale Insight and Approximation

To stabilize the Hessian, the method employs a two-timescale actor-critic framework:

The critic (estimating $Q$ ) evolves on a faster timescale than the actor (policy $\pi_\theta$ ).
Under this framework, the critic is treated as quasi-stationary during actor updates. Consequently, the gradient of the critic with respect to the actor parameters is approximated as zero ( $\nabla_\theta Q_c \approx 0$ ).
This approximation effectively eliminates the high-variance interaction term $H_{12}$ , simplifying the Hessian to $\tilde{H} \approx H_1 + H_2$ .

3. Efficient Implementation via Hessian-Vector Products (HVP)

To avoid explicit Hessian construction ( $O(d^3)$ ), the method utilizes Hessian-Vector Products (HVP). The update direction is derived by maximizing a local quadratic model using the approximate Hessian. Two specific approximations are formulated:

ACGN1 (Advantage-based Gauss-Newton): Replaces the state-action value $Q$ with the advantage function $A$ in the curvature terms ( $H_1 + H_2 \approx A_1 + A_2$ ). This reduces variance and leverages the outer-product term while retaining intrinsic curvature.
ACGN2 (Intrinsic Curvature): Discards the outer-product term $H_1$ entirely, retaining only the intrinsic curvature $H_2$ . This is theoretically justified for log-concave policies (e.g., softmax), where $H_2$ is negative semi-definite, ensuring a stable maximization direction without the convex bias introduced by $H_1$ .

The update rule involves an inner-loop optimization to solve for the displacement $\Delta$ using HVPs, followed by a policy update $\theta \leftarrow \theta + \Delta$ .

Key Contributions

Theoretical Unification: The paper establishes a connection between two-timescale actor-critic stability and second-order optimization. It demonstrates that the quasi-stationary assumption of the critic in a two-timescale framework justifies the approximation $\nabla_\theta Q \approx 0$ , thereby removing the unstable interaction term $H_{12}$ .
Stable Second-Order Updates: By eliminating $H_{12}$ , the authors formulate stable second-order updates that incorporate full curvature information without the computational burden of full Hessian estimation.
Structured Approximations: The introduction of ACGN1 and ACGN2 provides two distinct strategies for handling curvature: ACGN1 balances outer-product and intrinsic terms for variance reduction, while ACGN2 prioritizes structural stability by relying solely on intrinsic curvature.
Convergence Analysis: The paper provides a convergence proof for the damped second-order actor update, showing convergence to a stationary point up to approximation errors (critic tracking, curvature, and damping).

Experimental Results

The methods were evaluated on discrete control tasks (CartPole, LunarLander) and continuous control domains (Reacher, Humanoid) from MuJoCo.

Discrete Action Spaces: ACGN2 consistently demonstrated faster convergence and improved sample efficiency compared to first-order (REINFORCE) and Natural Gradient (NGA) baselines. This is attributed to ACGN2's reliance on the negative semi-definite intrinsic curvature, which aligns well with the log-concave policy parameterization used. ACGN1 also outperformed baselines but converged slightly slower due to the convex bias introduced by the outer-product term.
Continuous Action Spaces: In high-dimensional environments (Humanoid), ACGN1 and NGA exhibited more stable convergence, while ACGN2 showed comparable performance with slightly higher variance due to sensitivity to noisy curvature estimates. However, all second-order methods outperformed REINFORCE, confirming the benefit of curvature information even with non-log-concave Gaussian policies.
Computational Trade-offs: While second-order methods incur higher wall-clock time per iteration due to HVP computations, they achieve faster convergence in terms of training episodes. ACGN2 offers a favorable balance between computational cost and curvature quality, whereas ACGN1 is the most computationally expensive due to the inclusion of both curvature components.

Significance and Claims

The paper claims that its primary contribution is resolving the instability of second-order RL methods by leveraging the two-timescale actor-critic framework to justify the neglect of high-variance interaction terms. This allows for the practical application of curvature-aware updates that are both computationally efficient (via HVPs) and stable.

The authors assert that their approach improves convergence and sample efficiency over first-order and natural gradient baselines across diverse control tasks. They emphasize that while the method does not guarantee positive definiteness of the curvature matrix in all cases (particularly for ACGN1), the use of damping and the specific structural properties of the approximations (especially ACGN2) yield well-behaved updates in the vicinity of local optima. The work suggests that accurate capture of intrinsic curvature is critical for efficient policy optimization, particularly in discrete action spaces.

Future work, as noted by the authors, will focus on extending these curvature approximations to trust-region methods (TRPO) and proximal policy optimization (PPO), and developing scalable approximations for larger-scale problems.