Research map / Reinforcement learning / MDPs and planning

Global Convergence of Policy Gradient in Average Reward MDPs

ICLR 2025 · Reinforcement learning › MDPs and planning · approach: Average-reward and regularized MDPs

Read the paperCheck your idea against 108,967 papers

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

Gives the first finite-time global convergence analysis of policy gradient for ergodic tabular average-reward MDPs, showing O(1/T) sublinear convergence to the optimal policy.

Problem

Finite-time global convergence of policy gradient methods for infinite-horizon average-reward MDPs, which had not been comprehensively analyzed.

Approach

Provides a comprehensive finite-time global convergence analysis of policy gradient iterates for ergodic tabular average-reward MDPs, showing convergence to the optimal policy at rate O(1/T).

Key results

• Policy gradient iterates converge to the optimal policy at a sublinear rate of O(1/T) for ergodic tabular average-reward MDPs.

Closest papers by meaning

• Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes (AAAI 2024 · similarity 0.93)
• Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm (NeurIPS 2025 · similarity 0.92)
• Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm (NeurIPS 2024 · similarity 0.92)
• Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs (NeurIPS 2026 · similarity 0.92)
• Policy Gradient Algorithms in Average-Reward Multichain MDPs (NeurIPS 2026 · similarity 0.92)
• Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward Markov Decision Processes (ICLR 2025 · similarity 0.91)