Research map / Bandits and online learning / RL theory and MDPs
Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes
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 an epoch-based vanilla policy gradient algorithm with sub-trajectory advantage estimation for ergodic average-reward MDPs with general parameterization, proving O(T^{-1/4}) global convergence and O~(T^{3/4}) regret.
Problem
Sublinear regret for policy gradient methods with general policy parameterization in infinite-horizon average-reward MDPs, where prior regret results were limited to tabular or linear MDPs.
Approach
Epoch-based policy gradient where epoch length H grows as sqrt(T) and advantages are estimated from well-separated sub-trajectories (at least N apart), so the gradient estimator variance decays with T; combined with a global convergence analysis to bound regret.
Key results
- Proposed policy gradient algorithm achieves average optimality error O~(T^{-1/4}) (plus sqrt(epsilon_bias)) under ergodicity and general parameterization.
- Expected regret bounded by O~(T^{3/4}) + T*sqrt(epsilon_bias), the first sublinear regret for general parameterized PG in average reward setting.
- Matches the T^{-1/4} rate of discounted-reward general-parameterization PG sample complexity bounds.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed general-parameterized vanilla policy-gradient algorithm | Policy Gradient · Infinite-horizon average-reward ergodic MDPs | expected regret: \tilde{\mathcal{O}}(T^{\frac{3}{4}}+T\sqrt{\epsilon_{\mathrm{bias}}}) | Helped |
| Use the proposed general-parameterized vanilla policy-gradient algorithm | Policy Gradient · Infinite-horizon average-reward ergodic MDPs | average optimality error: \mathcal{O}(T^{-1/4}+\sqrt{\epsilon_{\mathrm{bias}}}) | Helped |
Limitations
- Requires ergodic MDP assumption; weakly communicating case left open.
- Regret includes an unavoidable T*sqrt(epsilon_bias) term from policy class incompleteness.
- Requires knowledge of T, mixing time and hitting time (doubling trick mentioned for T).
Experimental setup
Metrics: regret optimality error
Baselines: UCRL2 PSRL Optimistic Q-learning MDP-OOMD FOPO OLSVI.FH MDP-EXP2
Builds on: Policy gradient theorem (average reward) Sample-based PG analysis of Yuan et al. (Algorithm 2) UCRL2 MDP-EXP2
Closest papers by meaning
- Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm (NeurIPS 2024 · similarity 0.95)
- Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach (NeurIPS 2025 · similarity 0.92)
- Achieving Tractable Minimax Optimal Regret in Average Reward MDPs (NeurIPS 2024 · similarity 0.92)
- Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm (NeurIPS 2025 · similarity 0.90)
- Policy Gradient Algorithms in Average-Reward Multichain MDPs (NeurIPS 2026 · similarity 0.90)
- Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation (ICLR 2024 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.