Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Critic

Wesley A. Suttle, Amrit Singh Bedi, Bhrij Patel, Brian M. Sadler, Alec Koppel, Dinesh Manocha

In the world of Reinforcement Learning (RL), theory often relies on a convenient but fragile assumption: fast mixing. We assume that the temporal dependencies in our data—the "Markovian" nature of an agent's trajectory—vanish exponentially fast. But in the real world, agents get stuck in corners, rewards are few and far between, and state spaces are massive. In these scenarios, mixing is slow, and standard algorithms can stumble or require impossible-to-know parameters to function.

A new paper, "Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Critic," introduces a way to break free from these restrictive assumptions.

TL;DR

The authors propose Multi-level Actor-Critic (MAC), a new algorithm for average-reward RL that works even when environment dynamics converge slowly to a steady state. By leveraging Multi-Level Monte Carlo estimators and adaptive step sizes, MAC achieves state-of-the-art convergence rates without needing prior knowledge of the environment's "mixing time."

What Problem Does This Paper Address?

Most RL algorithms are analyzed under the assumption that the data-generating process "mixes" exponentially fast. Quantitatively, this is measured by mixing time ($\tau_{mix}$)—the time it takes for the agent's current state distribution to become independent of its starting point.

In practice, this assumption is frequently violated. Think of a robot navigating a complex maze or a self-driving car in heavy traffic; the agent might linger in certain regions for a long time, leading to slow (e.g., polynomial) mixing. Furthermore, standard convergence proofs often require setting the algorithm's step size based on $\tau_{mix}$. Since $\tau_{mix}$ is almost never known in advance, practitioners are left guessing, which can lead to instability.

The gap is clear: we need RL methods that are robust to slow mixing and "oblivious" to the specific mixing time of the environment.

Methods

The authors introduce the Multi-level Actor-Critic (MAC) algorithm, which features three key innovations:

  1. Multi-Level Monte Carlo (MLMC) Estimators: Instead of using a single sample to update the model, MAC uses a clever combination of "rollouts" of varying lengths. By sampling rollout lengths from a geometric distribution, the algorithm can construct estimators for the actor (policy), the critic (value function), and the average reward that have significantly lower bias than standard single-sample methods, without the variance exploding.
  2. Two-Timescale Architecture: MAC maintains the classic Actor-Critic structure but applies MLMC updates to all three components simultaneously: reward tracking, critic estimation (via TD learning), and actor updates (via policy gradients).
  3. Adaptive Learning Rates: The algorithm employs a modified Adagrad step size for the actor. This is a crucial technical choice that allows the algorithm to achieve a high-quality convergence rate ($\tilde{\mathcal{O}}(\epsilon^{-2})$) despite the complexities of having two different update speeds (timescales) for the actor and critic.

Datasets

The paper evaluates MAC using controlled Grid-World environments designed to simulate slow-mixing conditions:

  • $6 \times 6$ and $10 \times 10$ Grids: The agent starts at the top-left and must reach a goal at the bottom-right.
  • Sparse Rewards: The agent receives a $+1$ reward only upon reaching the goal and $0$ otherwise. This sparsity, combined with the grid structure, naturally leads to slower mixing as the agent explores.

Key Insights and Ideas

  • Bias vs. Variance Trade-off: The core "aha" moment is that MLMC can effectively "wash away" the bias introduced by Markovian data dependencies. It allows the algorithm to behave as if it were receiving independent (i.i.d.) samples, even when the data is highly correlated.
  • Mixing-Time Obliviousness: Unlike previous state-of-the-art methods, MAC's parameter selection does not depend on $\tau_{mix}$. This makes it far more practical for real-world engineering where environment dynamics are a black box.
  • Breaking the Complexity Floor: Standard two-timescale Actor-Critic analyses often hit a sample complexity wall of $\tilde{\mathcal{O}}(\epsilon^{-2.5})$. By using an adaptive Adagrad step size, the authors improve this to $\tilde{\mathcal{O}}(\epsilon^{-2})$, matching the best-known rates for simpler settings while using much weaker assumptions.

Key Results

The authors provide both theoretical guarantees and experimental proof-of-concept:

  • Theoretical Superiority: As shown in the comparison table below, MAC is the first average-reward AC algorithm that does not require "Fast Mixing" while maintaining competitive sample complexity.
Table 1: Comparison of AC algorithms. MAC matches the best complexity without requiring fast mixing.
  • Faster Convergence: In grid-world experiments, MAC reached the maximum reward significantly faster than "Vanilla" Actor-Critic. For example, in a $10 \times 10$ grid, MAC converged in roughly half the iterations required by the baseline.
Figure 1. (a) Mean Rewards over 3 million samples with Tmax = 8 for MAC and rollout = 3 for Vanilla AC with 6 × 6 grid. (b) Mean Rewards over 4 million samples with Tmax = 16 for MAC and rollout = 4 for Vanilla AC with 10 × 10 grid.

Limitations and Future Work

While a major step forward, the authors note a few areas for improvement:

  • Sharpness of Mixing Dependence: The current theoretical bound depends on $\tau_{mix}$ linearly or quadratically. Future research could aim to make this dependence "sublinear," further tightening the theory.
  • Function Approximation: The current work focuses on linear function approximation for the critic. Extending these MLMC techniques to deep neural networks (non-linear approximation) is a natural next step for scaling to even more complex tasks.
  • Broader Benchmarking: While the grid-world results are promising, testing MAC on high-dimensional robotics simulators or financial time-series data would further demonstrate its real-world utility.

Summary updated

Abstract

Many existing reinforcement learning (RL) methods employ stochastic gradient iteration on the back end, whose stability hinges upon a hypothesis that the data-generating process mixes exponentially fast with a rate parameter that appears in the step-size selection. Unfortunately, this assumption is violated for large state spaces or settings with sparse rewards, and the mixing time is unknown, making the step size inoperable. In this work, we propose an RL methodology attuned to the mixing time by employing a multi-level Monte Carlo estimator for the critic, the actor, and the average reward embedded within an actor-critic (AC) algorithm. This method, which we call \textbf{M}ulti-level \textbf{A}ctor-\textbf{C}ritic (MAC), is developed especially for infinite-horizon average-reward settings and neither relies on oracle knowledge of the mixing time in its parameter selection nor assumes its exponential decay; it, therefore, is readily applicable to applications with slower mixing times. Nonetheless, it achieves a convergence rate comparable to the state-of-the-art AC algorithms. We experimentally show that these alleviated restrictions on the technical conditions required for stability translate to superior performance in practice for RL problems with sparse rewards.
BibTeX
@inproceedings{suttle2023beyond,
  author = {Wesley A. Suttle and Amrit Singh Bedi and Bhrij Patel and Brian M. Sadler and Alec Koppel and Dinesh Manocha},
  title = {{Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Critic}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=DVinvfAvIB},
}
Figure