Introduction
In reinforcement learning (RL), a fundamental assumption is that running a policy for a sufficiently long duration will result in a stable average reward. This assumption generally holds in finite-state systems, such as grid worlds or board games, where mathematical guarantees ensure the system eventually reaches a "steady state." However, many real-world applications are better modeled as infinite-state systems. In these complex environments, standard policy evaluation methods can fail because a policy might cause the system to "drift" indefinitely—a phenomenon known as transience. When a system never settles, the running average of rewards may oscillate forever, making it impossible to calculate a reliable long-term value.
This paper addresses this challenge by leveraging Ergodic theory to define the conditions under which policy evaluation is reliable in partially observable, infinite-state systems. The authors introduce the concept of "absolutely AMS" systems to provide a rigorous mathematical framework for identifying stable environments.
Theoretical Framework: AMS Processes
The researchers propose using Asymptotically Mean Stationary (AMS) processes as a foundation. An AMS system is one that, while perhaps not stationary from the outset, eventually converges to stationary behavior in the long run.
Key theoretical contributions include:
- Transience Analysis: A formal proof that any transient Markov chain—one that can move toward infinity without returning to its origin—is fundamentally non-AMS. This confirms that empirical averages in such systems are inherently unreliable.
- Absolutely AMS Systems: A new classification for controllable systems where any finite-memory policy is guaranteed to result in an AMS process.
- The Reset Mechanism: For systems that allow a "reset" action to a known starting state, the authors prove that accurate policy evaluation is possible by averaging multiple independent trajectories, even if the individual trajectories are unstable.
Synthetic Stress Tests
To validate their theories, the authors developed three synthetic dynamical systems designed to test the limits of average reward convergence. One primary example is the Infinite Queue, a random walk on non-negative integers where specific policies can cause the queue length to grow without bound.
Other test cases include the Infinite Binary Graph, where the state space width grows exponentially with depth, and the Fully Connected Infinite Queue, which demonstrates that even high connectivity between states does not guarantee the AMS property.
Key Results and Taxonomy
The paper establishes several critical results for the RL community:
- Proposition 2 & Theorem 4: These results formally link transience to the failure of the AMS condition and provide the "green light" for comparing policies when the AMS and ergodic conditions are met.
- Theorem 5: This theorem provides a concrete algorithm for policy evaluation using resets and convergence tests, ensuring accurate long-term value estimates with high probability.
- System Taxonomy: The research clarifies the relationship between different modeling frameworks. Notably, it shows that systems representable by Linear Predictive State Representations (PSRs) are always "absolutely AMS," providing a safety net for their use. In contrast, non-linear PSRs can model non-AMS systems, and some AMS systems fall outside the reach of current PSR models.
Conclusion and Future Directions
This work provides a vital theoretical bridge for RL in infinite-state spaces. By identifying the "transience trap" and defining the "absolutely AMS" property, the authors offer a roadmap for reliable policy evaluation. While this paper focuses on evaluation, future work is needed to extend these findings to policy improvement (e.g., policy gradient methods) and to determine general convergence rates for these complex systems. The intersection of AMS properties and information theory remains a promising area for further exploration.
Summary updated