Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPs

Swetha Ganesh, Washim Uddin Mondal, Vaneet Aggarwal

TL;DR

This paper closes a critical theoretical gap in reinforcement learning by introducing two new policy gradient algorithms for infinite-horizon average reward Markov Decision Processes (MDPs) with general policy parametrization. Notably, their Hessian-aided approach achieves an order-optimal expected regret of $\tilde{\mathcal{O}}(\sqrt{T})$, matching the theoretical lower bound and significantly improving upon the previous state-of-the-art.

What Problem Does This Paper Address?

In reinforcement learning (RL), agents often operate in infinite-horizon settings where the goal is to maximize the long-term average reward. To evaluate an algorithm's performance over time, researchers measure regret—the difference between the rewards earned by an optimal policy and those earned by the learning agent.

While tabular methods can achieve the optimal theoretical regret bound of $\tilde{\mathcal{O}}(\sqrt{T})$, they do not scale to real-world problems with massive state and action spaces. To handle large spaces, practitioners use general policy parametrization (like neural networks). However, analyzing average-reward RL under general parametrization is notoriously difficult because standard tricks from discounted RL (like resetting the environment using a simulator) are impractical or unavailable. Prior parameterized methods only achieved a suboptimal regret of $\tilde{\mathcal{O}}(T^{3/4})$ and relied on an unverified assumption: that the average-reward function is smoothly varying ($L$-smooth) with respect to the policy parameters.

This paper addresses two major challenges: bridging the gap to the optimal $\tilde{\mathcal{O}}(\sqrt{T})$ regret bound under general parametrization, and formally proving the smoothness of the average-reward objective.

Methods

The authors propose two model-free, policy gradient-based algorithms that utilize advanced variance-reduction techniques to handle the lack of environment resets:

  1. Algorithm 1 (Implicit Gradient Transport - IGT): A first-order method that uses momentum-based variance reduction. It requires no second-order curvature information or importance sampling and achieves an expected regret of $\tilde{\mathcal{O}}(T^{2/3})$.
  2. Algorithm 3 (Hessian-aided Policy Gradient): A second-order method that incorporates Hessian estimates to achieve the optimal $\tilde{\mathcal{O}}(\sqrt{T})$ regret bound. Crucially, it computes matrix-vector products rather than full Hessians, keeping memory and computational overhead low.

To overcome the unverified smoothness assumption of the true reward function $J$, the authors introduce a novel mathematical framework. They construct an auxiliary function $\bar{J}$ that acts as a close, strictly $L$-smooth approximation of $J$, allowing them to build unbiased gradient and Hessian estimators from single-trajectory rollouts.

Datasets

Not discussed in the paper. This work is purely theoretical and focuses on proving mathematical convergence and regret bounds rather than evaluating on empirical benchmarks.

Key Insights and Ideas

  • Proving Smoothness via Approximation: Instead of assuming the objective function is smooth, the authors prove an approximate smoothness property. By showing that the true reward function $J$ stays close to their newly constructed, provably smooth auxiliary function $\bar{J}$, they validate the mathematical foundations of policy gradient methods in average-reward settings.
  • Overcoming Trajectory Bias: Without environment resets, sampling data sequentially along a single trajectory introduces bias because consecutive states are highly correlated. The authors solve this by introducing a delayed estimation trick: they estimate the policy gradient at a slightly later point along the trajectory, giving the underlying Markov chain time to "mix" and effectively shrinking the bias.
  • Hessian Efficiency: Second-order optimization methods are traditionally avoided in deep RL due to the $O(d^2)$ memory cost of storing a Hessian matrix for $d$ parameters. Algorithm 3 circumvents this by recursively computing only the matrix-vector product $B(\theta, \tau)(\theta_k - \theta_{k-1})$, preserving the benefits of curvature information at a fraction of the cost.

Key Results

The paper's main contributions are theoretical breakthroughs that match or beat existing algorithms across tabular and parameterized settings.

  • Algorithm 1 achieves a regret of $\tilde{\mathcal{O}}(T^{2/3})$, improving on the previous first-order parameterized state-of-the-art.
  • Algorithm 3 achieves a regret of $\tilde{\mathcal{O}}(\sqrt{T})$, which is order-optimal as it matches the theoretical lower bound $\Omega(\sqrt{T})$ for average-reward MDPs.

The table below outlines how these results compare to prior literature:

Table 1: Summary of policy-based algorithms for infinite-horizon average reward MDPs.

Limitations and Future Work

  • Ergodicity Assumption: The proofs rely heavily on the assumption that the MDP is ergodic (meaning every state can eventually be reached from any other state under any policy). Extending these optimal bounds to weakly-communicating or general MDPs remains an open challenge.
  • Dependence on Mixing Time Oracles: The algorithms require explicit knowledge of the environment's mixing time ($t_{mix}$) to set the epoch lengths and step sizes. In practice, mixing times are rarely known beforehand. Developing "parameter-free" or adaptive algorithms that learn without mixing-time oracles is a vital next step for practical deployment.

Summary updated

Abstract

We present two Policy Gradient-based algorithms with general parametrization in the context of infinite-horizon average reward Markov Decision Process (MDP). The first one employs Implicit Gradient Transport for variance reduction, ensuring an expected regret of the order $\tilde{\mathcal{O}}(T^{2/3})$. The second approach, rooted in Hessian-based techniques, ensures an expected regret of the order $\tilde{\mathcal{O}}(\sqrt{T})$. These results significantly improve the state-of-the-art $\tilde{\mathcal{O}}(T^{3/4})$ regret and achieve the theoretical lower bound. We also show that the average-reward function is approximately $L$-smooth, a result that was previously assumed in earlier works.
BibTeX
@inproceedings{ganesh2025order,
  author = {Swetha Ganesh and Washim Uddin Mondal and Vaneet Aggarwal},
  title = {{Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPs}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2025},
  url = {https://openreview.net/forum?id=ejCe2rs9QT},
}
Figure