In classical reinforcement learning (RL) theory, we often treat the environment as a playground where every mistake can be undone. If an agent wanders into a suboptimal corner of the state space, standard proofs assume it can always find its way back. This mathematical safety blanket is known as the ergodicity assumption.
While ergodicity makes proving convergence and regret bounds elegant, it creates a massive gap between theory and reality. In the real world, environments have one-way streets, fragile hardware, and permanent failures. If an autonomous drone crashes into a wall, it cannot simply "explore" its way back to the starting pad.
To deploy RL safely and reliably in complex systems, researchers are moving beyond ergodicity, developing algorithms that can operate under relaxed reachability constraints.
The Comfort of Ergodicity
To understand why erasing the ergodicity assumption is difficult, we must first understand why theorists rely on it.
In an infinite-horizon setting, an agent aims to maximize its long-term average reward. If the underlying Markov Decision Process (MDP) is ergodic, every stationary policy ensures that the environment is fully mixing. This means that from any starting state, the agent will eventually visit every other state infinitely often, settling into a steady-state distribution.
This property provides two massive theoretical advantages:
- Initial states do not matter: The long-term average reward is a single, constant value across the entire environment, regardless of where the agent begins its trajectory.
- Bounded mixing times: The time it takes for the state distribution to converge to its steady state (the mixing time) is finite. This allows algorithms to quickly smooth out the noise of early exploration.
As noted by Ching-An Cheng et al. in A Reduction from Reinforcement Learning to No-Regret Online Learning, assuming every state is reachable under any policy bypasses the fundamental challenge of managing complex state-action distributions. It guarantees that the agent will naturally stumble upon the optimal path given enough time.
The Reality of Irreversible Transitions
In practice, ergodicity is routinely violated. Real-world environments are filled with irreversible state transitions, which can be categorized into a spectrum of reachability:
[ Ergodic ] ------------> [ Communicating ] ------------> [ Weakly Communicating ] ------------> [ Non-Communicating / Traps ]
All policies visit Some policy can get Some states are transient; Irreversible dead-ends;
all states. from any state to any other. others form a communicating set. agent can get permanently stuck.
- Communicating MDPs: Any state can be reached from any other state under some policy, but not necessarily every policy. A bad policy can get an agent stuck in a loop, but the environment itself doesn't contain permanent dead ends.
- Weakly Communicating MDPs: The state space contains a set of states that are communicating, alongside a set of transient states that the agent can leave but never re-enter. As Vaneet Aggarwal et al. demonstrate in Constrained Reinforcement Learning with Average Reward Objective: Model-Based and Model-Free Algorithms, in these environments, the average reward becomes highly sensitive to the initial state and the specific transition paths chosen early on.
- Traps and Absorbing States: Certain actions lead to permanent state changes. In Universal Approximation Theorem of Deep Q-Networks, Qian Qi highlights that environments with irreversible states or dead ends violate basic convergence assumptions, causing standard deep reinforcement learning solutions to fail to find optimal control policies.
When an agent encounters a bottleneck or a trap, the mixing time effectively becomes infinite. If an algorithm relies on uniform mixing, its performance guarantees collapse because it cannot recover from early exploratory mistakes.
Algorithmic Strategies for Relaxed Reachability
How do we design algorithms that learn efficiently when the environment refuses to cooperate? Recent work focuses on replacing global ergodicity assumptions with localized or structural constraints.
1. Controlling the Span of the Value Function
Instead of assuming the agent can easily travel between any two states, we can bound the maximum variance of the optimal value function across the state space. This bound is known as the span.
In their seminal work, REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs, Peter Bartlett et al. introduced a regularization framework that explicitly penalizes policies with excessively large value spans. By keeping the span bounded, the algorithm prevents the agent from over-indexing on highly isolated, high-reward states that are practically impossible to return to, providing sublinear regret guarantees even in weakly communicating environments.
2. Bridging Average and Discounted Rewards
Another powerful intuition is to approximate the infinite-horizon average reward using a sequence of discounted reward problems with a carefully tuned discount factor $\gamma$.
The authors of Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes leverage this approach in their algorithm, UCB-AVG. By combining variance-reduction techniques with this discounted approximation, they achieve time-optimal regret bounds ($\sqrt{T}$) for general, weakly communicating environments without requiring the environment to be ergodic. This allows model-free agents to balance exploration and exploitation without fearing that a single step will permanently ruin their average reward metrics.
3. Function Approximation Under Finite Span
When moving to massive or continuous state spaces, agents cannot visit every state individually, necessitating function approximation.
In Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation, Dongruo Zhou et al. prove that near-optimal regret can be achieved using linear models without relying on restrictive "uniform mixing" assumptions. Instead, they operate under a finite span assumption, demonstrating that as long as the underlying linear features can represent the value transitions smoothly, the agent can navigate around bottlenecks and avoid getting trapped in suboptimal regions.
4. Explicit Safety and Return Mechanisms
If the environment contains catastrophic dead ends, the agent must actively manage its ability to return home.
In Safe Exploration in Markov Decision Processes, Teodor Mihai Moldovan formalizes this by introducing a mathematical framework based on ergodicity restoration. Before executing an exploratory action, the agent computes the probability that it can return to a known "safe" distribution of states. If the return probability falls below a threshold, the action is flagged as unsafe, explicitly preventing the agent from entering irreversible, unrecoverable states.
[ Current State ] ---> Propose Action ---> Calculate Return Probability ---> > Threshold? ---> Execute
|
---> < Threshold? ---> Reject (Stay Safe)
Why This Shift Matters
Moving away from the ergodicity assumption shifts reinforcement learning from an idealized mathematical abstraction to a practical engineering discipline. By acknowledging that environments contain bottlenecks, transient states, and irreversible traps, these frameworks allow us to provide formal performance and safety guarantees for systems operating in the real world. Whether managing supply chains, controlling autonomous vehicles, or optimizing power grids, understanding state reachability is the key to building truly robust agents.