Abstract: A central object of study in Reinforcement Learning (RL) is the Markovian policy, in which an agent's actions are chosen from a memoryless probability distribution, conditioned only on its current state. The family of Markovian policies is broad enough to be interesting, yet simple enough to be amenable to analysis. However, RL often involves more complex policies: ensembles of policies, policies over options, policies updated online, etc. Our main contribution is to prove that the occupancy measure of any non-Markovian policy, i.e., the distribution of transition samples collected with it, can be equivalently generated by a Markovian policy. This result allows theorems about the Markovian policy class to be directly extended to its non-Markovian counterpart, greatly simplifying proofs, in particular those involving replay buffers and datasets. We provide various examples of such applications to the field of Reinforcement Learning.
Introduction
In Reinforcement Learning (RL), the "Markovian" assumption is a cornerstone of theoretical analysis. A Markovian policy is memoryless, selecting actions based solely on the current state. While this simplicity facilitates elegant mathematical proofs, modern RL practice frequently deviates from this ideal. Real-world algorithms often employ non-Markovian strategies, such as using replay buffers that sample from a history of policies, ensemble models, or hierarchical structures where an agent switches between sub-policies.
Bridging the gap between the theoretical convenience of Markovian policies and the practical reality of non-Markovian ones is critical. This paper establishes a powerful theoretical bridge: for almost any complex, history-dependent policy, there exists a functionally equivalent Markovian policy that generates the exact same distribution of state-action visits, or occupancy measure.
The Occupancy Equivalence Theorem
The core contribution of this work is Theorem 3 (State-action occupancy equivalence). The researchers focus on the occupancy measure—a distribution representing how frequently an agent visits specific state-action pairs over time. Using the Radon-Nikodym derivative from measure theory, they construct a Markovian policy $\tilde{\pi}$ from any non-Markovian policy $\pi$.
In a discrete setting, this equivalent policy is defined as: $$\tilde{\pi}(a|s) = \frac{\mu^\pi_\gamma(s, a)}{\mu^\pi_\gamma(s)}$$ where $\mu^\pi_\gamma(s, a)$ is the expected discounted number of times the non-Markovian policy visits state $s$ and takes action $a$. Unlike previous "folk theorems," this formal proof extends to infinite state and action spaces and covers cases without discounting ($\gamma=1$), provided the occupancy measure satisfies the technical condition of $\sigma$-finiteness.
Illustrative Example
To demonstrate this equivalence, the authors utilize minimal, hand-crafted Markov Decision Processes (MDPs). A simple looping MDP, as shown in Figure 1, serves to illustrate how a time-dependent or history-dependent policy can be reduced to a state-dependent one without altering the average behavior.
While the average distribution of states remains identical between the non-Markovian policy and its Markovian counterpart, the specific trajectories may differ. For instance, a non-Markovian policy might be designed to always terminate after exactly ten steps, whereas its Markovian equivalent might follow a geometric distribution that averages ten steps.
Key Insights and Applications
The equivalence theorem provides a "theoretical free lunch" for RL researchers. Because the expected return of a policy depends solely on its occupancy measure, any non-Markovian policy has a Markovian twin with identical performance. This allows researchers to extend theoretical guarantees originally intended for Markovian policies to complex systems like those using offline datasets or experience replay.
Safe Policy Improvement (SPIBB)
The authors demonstrate that the Safe Policy Improvement with Baseline Bootstrapping (SPIBB) framework, which previously required a Markovian behavior policy, now formally extends to non-Markovian data sources.
Advantage-Weighted Regression (AWR)
The derivation for AWR, which originally required complex justifications for its use of replay buffers, can be significantly simplified using the occupancy equivalence theorem. This result confirms that Markovian policies are a representative subset of all possible behaviors regarding occupancy measures.
Limitations and Future Outlook
While powerful, the theorem has specific boundaries. It applies to policies that reset their memory at the start of each episode, meaning it does not directly cover agents that maintain memory across episodes. Furthermore, for trajectory-based models like Decision Transformers that explicitly model sequences rather than just distributions, occupancy equivalence may not capture the full behavioral nuance.
Ultimately, the existence of a Markovian equivalent does not negate the utility of non-Markovian policies. Structures like options or ensembles are often more intuitive to design for specific tasks. However, this work provides the necessary mathematical foundation to analyze these complex structures with the same rigor applied to simpler Markovian models.
Summary updated