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

Policy Gradient Algorithms in Average-Reward Multichain MDPs

NeurIPS 2026 · 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.

Establishes a policy gradient theorem for average-reward multichain MDPs using recurrent and transient visitation measures, and proves convergence and sample-complexity guarantees for alpha-clipped policy mirror ascent with respect to positive policies.

Problem

Policy gradient methods for average-reward MDPs have been analyzed only for ergodic or unichain settings; no policy gradient theorem or convergence guarantees exist for general multichain MDPs.

Approach

Introduces recurrent and transient visitation measures based on the invariant recurrent-transient state classification over positive policies, yielding a policy gradient theorem for multichain MDPs and an alpha-clipped policy mirror ascent with sublinear/linear convergence and generative-model sample complexity.

Key results

• Establishes a policy gradient theorem for average-reward multichain MDPs with recurrent and transient visitation measures, generalizing the unichain result.
• alpha-clipped policy mirror ascent with constant step size achieves an O(1/k) sublinear rate, and with adaptive step sizes a linear rate (1-1/C_alpha)^k.
• Stochastic variant under a generative model yields sample complexity of order epsilon^-6 (constant step) or epsilon^-6 (adaptive step) up to logs and problem constants, giving epsilon-optimality w.r.t. positive policies.

Surprising findings

• The average-reward objective can be discontinuous on the boundary of the policy simplex in multichain MDPs, so optimality is only defined over positive policies.

Limitations

• Guarantees are only for epsilon-optimality relative to positive policies, not the full multichain optimum.
• Sample complexity is polynomial with high exponents (epsilon^-6 or epsilon^-12) and depends on problem-dependent constants such as C_alpha and t_tar.
• Adaptive step size requires knowledge of C_alpha.

Experimental setup

Metrics: epsilon-optimality with respect to positive policies sample complexity convergence rate

Baselines: projected Q-descent multiplicative weights updates

Builds on: policy gradient theorem (unichain average-reward) policy mirror ascent discounted-reward PMA analysis

Closest papers by meaning

• Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs (NeurIPS 2026 · similarity 0.90)
• Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm (NeurIPS 2024 · similarity 0.90)
• Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes (AAAI 2024 · similarity 0.90)
• Faster Fixed-Point Methods for Multichain MDPs (NeurIPS 2025 · similarity 0.90)
• Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward Markov Decision Processes (ICLR 2025 · similarity 0.89)
• Provable Policy Gradient for Robust Average-Reward MDPs Beyond Rectangularity (ICML 2025 · similarity 0.89)