Abstract
An important problem that arises in reinforcement learning and Monte Carlo methods is estimating quantities defined by the stationary distribution of a Markov chain. In many real-world applications, access to the underlying transition operator is limited to a fixed set of data that has already been collected, without additional interaction with the environment being available. We show that consistent estimation remains possible in this challenging scenario, and that effective estimation can still be achieved in important applications. Our approach is based on estimating a ratio that corrects for the discrepancy between the stationary and empirical distributions, derived from fundamental properties of the stationary distribution, and exploiting constraint reformulations based on variational divergence minimization. The resulting algorithm, GenDICE, is straightforward and effective. We prove its consistency under general conditions, provide an error analysis, and demonstrate strong empirical performance on benchmark problems, including off-line PageRank and off-policy policy evaluation.
Introduction
In fields ranging from reinforcement learning (RL) to web search, researchers often need to estimate the "stationary distribution"—the steady state a system settles into over time. For instance, PageRank determines a website's importance based on where a random surfer eventually ends up. However, traditional algorithms typically require a perfect model of the system or the ability to interact with it repeatedly. In practice, we often only have access to a "frozen" log of past data collected by an unknown process.
Estimating long-term averages from this static, "off-policy" data is notoriously difficult because the empirical distribution of the data rarely matches the target stationary distribution. Previous attempts to bridge this gap often suffered from instability, particularly when calculating true long-term averages (the undiscounted case). GenDICE (Generalized stationary DIstribution Correction Estimation) addresses these challenges by providing a stable, consistent framework for offline estimation.
Methodology
The core of GenDICE is the estimation of a correction ratio ($\tau$) that mathematically adjusts for the discrepancy between the available data and the desired stationary distribution. Key innovations include:
- Stationary Distribution Corrector: Rather than modeling the entire environment, GenDICE directly estimates the ratio of the target distribution to the data distribution.
- Divergence Minimization with Constraints: To prevent degenerate solutions (e.g., the ratio collapsing to zero), the authors introduce a penalty constraint that guarantees a unique, correct solution.
- Dual Embedding: By applying Fenchel duality, the complex optimization is transformed into a "min-max" saddle point problem. This allows for training via standard stochastic gradient descent (SGD) using neural networks, ensuring scalability.
- $\chi^2$-Divergence: While the framework is flexible, the authors found that $\chi^2$-divergence offers superior stability compared to alternatives like KL-divergence, which can be erratic due to exponential terms.
Experimental Evaluation
The authors evaluated GenDICE across diverse benchmarks, including graph ranking (PageRank) on synthetic BA graphs and real-world citation networks (Cora, Citeseer), as well as RL tasks in OpenAI Gym (Cartpole, Reacher, HalfCheetah).
Sample Efficiency in PageRank
In PageRank tasks, GenDICE demonstrated significant sample efficiency compared to traditional model-based methods. As shown in the graph ranking experiments, GenDICE achieves lower KL-divergence with fewer samples, particularly on larger graphs where reconstructing the full transition matrix is computationally expensive or data-intensive.
Stability and Policy Evaluation
A critical advantage of GenDICE is its stability at the limit. Traditional importance sampling suffers from variance that grows exponentially with trajectory length (the "curse of horizon"). By focusing on the stationary distribution, GenDICE maintains low variance even as the discount factor $\gamma$ approaches 1.0. In RL benchmarks like Reacher and HalfCheetah, GenDICE consistently outperformed baselines like DualDICE and Importance Sampling in terms of Mean Squared Error (MSE).
Conclusion and Future Work
GenDICE represents a significant step forward in offline estimation, offering a behavior-agnostic approach that remains robust even in undiscounted scenarios. While the algorithm is proven to be consistent, future research is needed to quantify optimization errors when using deep neural networks and to scale the method for large-scale industrial applications like recommendation engines. Despite these open questions, GenDICE provides a practical and theoretically grounded tool for long-term value estimation from static datasets.
Summary updated