Research map / Reinforcement learning / MDPs and planning

Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach

NeurIPS 2025 · Reinforcement learning › MDPs and planning · approach: Average-reward and regularized MDPs · 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.

Proposes NAC-B, a natural actor-critic with batching and linear function approximation, achieving Õ(√T) regret in average-reward MDPs under the unichain assumption without ergodicity or simulator access.

Problem

Regret of policy-gradient / actor-critic methods for infinite-horizon average-reward MDPs without ergodicity assumptions, where the chain may have transient states and periodicity.

Approach

Uses large batch averaging over single-trajectory Markovian samples (batch size ~sqrt(T)) to mitigate periodicity, combined with a linear critic and natural policy gradient updates, and conditions analysis on rapid entry into the recurrent class.

Key results

• NAC-B achieves expected regret Õ(T(√ε_bias + √ε_app) + √T(C²C_tar + C_tar)) under the unichain assumption, with K=Θ(√T/log T), B=Θ(√T), H=Θ(log T).
• Lemma shows time-averaged distribution converges to stationary distribution at rate O(1/t) in total variation under unichain assumption.
• Discounted-to-average reductions with existing PG methods yield at best ε^-5 sample complexity (≈T^{4/5} regret), worse than the proposed √T regret.

Measured effects reported in the paper

Surprising findings

• Kernel of the critic matrix can change with policy due to transient states, so strict positive definiteness cannot be guaranteed in the unichain setting.

Limitations

• Relies on linear critic with approximation error ε_app and policy bias ε_bias; regret bound scales with these terms.
• Requires Fisher non-degeneracy and score-function smoothness assumptions.
• Unichain relaxation of the critic-matrix kernel condition is not fully general; analysis conditioned on early entry into recurrent class.

Experimental setup

Metrics: regret

Baselines: MDP-OOMD Optimistic Q-learning MDP-EXP2 UCB-AVG PPG PHAPG gamma-DC-LSCVI-UCB SPMD

Builds on: natural policy gradient policy gradient theorem MLMC-NAC MDP-OOMD

Closest papers by meaning

• A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach (ICML 2025 · similarity 0.92)
• Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes (AAAI 2024 · similarity 0.92)
• Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm (NeurIPS 2025 · similarity 0.91)
• Achieving Tractable Minimax Optimal Regret in Average Reward MDPs (NeurIPS 2024 · 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)
• Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs (NeurIPS 2026 · similarity 0.89)