Research map / Reinforcement learning / Policy gradient and actor-critic

On the Second-Order Convergence of Biased Policy Gradient Algorithms

ICML 2024 · Reinforcement learning › Policy gradient and actor-critic · approach: Variance-reduced policy gradients · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows biased policy gradient (vanilla GPOMDP-style and double-loop actor-critic with linear TD(0) critic) reaches epsilon-second-order stationary points in Õ(ε^-6.5) iterations, and proves TD(0) convergence on nonstationary Markov chains.

Problem

Policy gradient is biased in practice (finite-horizon truncation of discounted infinite-horizon reward, and critic approximation in actor-critic), and existing second-order escape-from-saddle guarantees only cover unbiased estimators or vanilla PG, not actor-critic.

Approach

Extends perturbed/stochastic-gradient saddle-escape analysis to biased gradient estimators by decomposing bias into truncation and critic-approximation terms and bounding each via moment conditions; for actor-critic it adds a finite-time TD(0) analysis that does not assume the Markov chain starts in its stationary distribution.

Key results

• Vanilla biased policy gradient reaches an epsilon-second-order stationary point in Õ(ε^-6.5) iterations, improving on Õ(ε^-9) of prior second-order PG but weaker than Õ(ε^-4.5) for unbiased estimators.
• Double-loop actor-critic with TD(0) critic reaches epsilon-second-order stationary point in Õ(ε^-6.5) outer iterations with Õ(ε^-8) inner TD(0) steps.
• TD(0) on nonstationary Markov chains achieves O(1/sqrt K)+O(1/K) rate with alpha=1/sqrt K, versus O(1/sqrt K) when starting from the stationary distribution.

Limitations

• Results are purely theoretical with no empirical experiments.
• Assumes linear critic realizability and linear TD(0) critic with projection onto a bounded set.
• Sample complexity is weaker than the unbiased-estimator bound Õ(ε^-4.5); second-order guarantees rely on correlated negative curvature noise assumption, achieved by adding isotropic noise.

Experimental setup

Metrics: sample complexity (iterations to epsilon-second-order statio

Baselines: Zhang et al. 2020 second-order policy gradient (Õ(ε^-9)) Yang et al. 2019 unbiased second-order policy gradient (Õ(ε^-4.5)) Ge et al. perturbed SGD Chen et al. federated second-order convergence

Builds on: GPOMDP stochastic gradient descent escapes saddle points (Ge et al.) perturbed gradient descent (Jin et al.) linear TD(0) finite-time analysis (Bhandari et al.) federated learning second-order convergence

Closest papers by meaning

• Variational Policy Gradient Method for Reinforcement Learning with General Utilities (NeurIPS 2020 · similarity 0.89)
• Convergence and Optimality of Policy Gradient Methods in Weakly Smooth Settings (AAAI 2022 · similarity 0.89)
• Breaking the Bias Barrier in Concave Multi-Objective Reinforcement Learning (NeurIPS 2026 · similarity 0.88)
• Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles (ICML 2024 · similarity 0.88)
• Actor-Critics Can Achieve Optimal Sample Efficiency (ICML 2025 · similarity 0.88)
• Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation (ICML 2024 · similarity 0.88)