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}$).
- 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.
- 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.
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