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

Swetha Ganesh, Vaneet Aggarwal

Abstract

Theoretical guarantees for Actor-Critic reinforcement learning often rely on the restrictive "ergodicity" assumption, which requires environments to mix quickly and lack transient states. This paper introduces NAC-B (Natural Actor-Critic with Batching), an algorithm that achieves optimal $\tilde{O}(\sqrt{T})$ regret under the significantly weaker "unichain" assumption. By utilizing a batching strategy to stabilize gradient estimates in the presence of periodicity and transient states, NAC-B bridges the gap between the practical success of policy gradient methods and their theoretical foundations in realistic, non-ergodic environments.

Introduction

In Reinforcement Learning (RL), the infinite-horizon average-reward setting is crucial for continuous tasks like traffic management or resource allocation. While Policy Gradient (PG) and Actor-Critic methods are widely used in practice with function approximation, their theoretical convergence proofs typically assume ergodicity. Ergodicity implies the environment settles into a steady state exponentially fast, ignoring real-world complexities like transient states (visited once and never again) or periodic cycles. This work addresses whether Actor-Critic methods can achieve optimal regret under the "unichain" assumption, where the environment contains a single recurrent class but may include transient states and periodic behavior.

The NAC-B Algorithm

The proposed algorithm, Natural Actor-Critic with Batching (NAC-B), utilizes a general parameterized policy for the actor and linear function approximation for the critic. A key innovation is the "Batching" trick: instead of single-step updates, NAC-B collects large batches of samples ($B = \Theta(\sqrt{T})$) before performing an update. This time-averaging approach smooths out oscillations caused by periodic Markov chains and stabilizes gradient estimates, allowing the algorithm to operate entirely online from a single trajectory without needing a simulator.

Theoretical Insights

The analysis of NAC-B moves away from traditional "mixing times" and instead utilizes "hitting times"—specifically the expected time to reach the recurrent class from a transient state ($C_{hit}$) and the expected time to reach a target state ($C_{tar}$).

  1. Handling Periodicity: In periodic chains, state distributions do not converge to a single limit. Batching allows the empirical distribution to converge to the stationary distribution at a rate of $O(1/t)$, bypassing the need for exponential mixing.
  2. Managing Transient States: Transient states often complicate the analysis of the critic's learning accuracy. The authors demonstrate that NAC-B enters the recurrent class quickly enough that the impact of transient states on the overall regret is negligible.

Comparison and Results

NAC-B achieves an expected regret of $\tilde{O}(\sqrt{T})$, assuming expressive function approximators. This is the first regret guarantee for parameterized PG methods in average-reward MDPs under the unichain setting.

Comparison of NAC-B with existing algorithms in average-reward MDPs.

As shown in the comparison table, NAC-B is the only algorithm that simultaneously achieves order-optimal regret, operates without ergodicity assumptions, and supports general policy parameterization.

Conclusion

NAC-B represents a significant step in aligning RL theory with practice. While the unichain assumption is a major relaxation of ergodicity, future work may explore even broader classes, such as "weakly communicating" MDPs, and extend the analysis to non-linear function approximation for the critic.

Summary updated

Abstract

Actor-Critic methods are widely used for their scalability, yet existing theoretical guarantees for infinite-horizon average-reward Markov Decision Processes (MDPs) often rely on restrictive ergodicity assumptions. We propose NAC-B, a Natural Actor-Critic with Batching, that achieves order-optimal regret of \$\tilde{O}(\sqrt{T})\$ in infinite-horizon average-reward MDPs under the unichain assumption, which permits both transient states and periodicity. This assumption is among the weakest under which the classic policy gradient theorem remains valid for average-reward settings. NAC-B employs function approximation for both the actor and the critic, enabling scalability to problems with large state and action spaces. The use of batching in our algorithm helps mitigate potential periodicity in the MDP and reduces stochasticity in gradient estimates, and our analysis formalizes these benefits through the introduction of the constants $C_{\text{hit}}$ and $C_{\text{tar}}$, which characterize the rate at which empirical averages over Markovian samples converge to the stationary distribution.
BibTeX
@inproceedings{ganesh2025regret,
  author = {Swetha Ganesh and Vaneet Aggarwal},
  title = {{Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=rl2aAyJfQz},
}
Figure