Abstract
We consider the off-policy estimation problem of estimating the expected reward of a target policy using samples collected by a different behavior policy. Importance sampling (IS) has been a key technique to derive (nearly) unbiased estimators, but is known to suffer from an excessively high variance in long-horizon problems. In the extreme case of infinite-horizon problems, the variance of an IS-based estimator may even be unbounded. In this paper, we propose a new off-policy estimation method that applies IS directly on the stationary state-visitation distributions to avoid the exploding variance issue faced by existing estimators. Our key contribution is a novel approach to estimating the density ratio of two stationary distributions, with trajectories sampled from only the behavior distribution. We develop a mini-max loss function for the estimation problem, and derive a closed-form solution for the case of RKHS. We support our method with both theoretical and empirical analyses.
Introduction
In reinforcement learning (RL), Off-Policy Estimation (OPE) is the task of evaluating a target policy $\pi$ using data generated by a different behavior policy $\pi_0$. This is critical for real-world applications where deploying a new policy is risky or expensive. However, traditional OPE methods based on Importance Sampling (IS) face a significant challenge known as the "Curse of Horizon."
Standard IS weights observed trajectories by the ratio of their probabilities under the target versus behavior policies. For a trajectory of length $T$, this weight is a product of $T$ step-wise ratios. This product often leads to variance that grows exponentially with the horizon $T$, rendering the estimator unusable for long-term or infinite-horizon tasks.
Methods
To overcome the Curse of Horizon, we propose shifting the focus from entire trajectories to stationary state-visitation distributions. Instead of path-wise weights, we estimate the stationary density ratio: $$w(s) = \frac{d_\pi(s)}{d_{\pi_0}(s)}$$ where $d_\pi(s)$ is the long-term frequency of visiting state $s$ under policy $\pi$.
Mini-max Loss and RKHS Solution
Estimating $w(s)$ is non-trivial as the transition dynamics are unknown. We derive a mini-max objective based on the Bellman equation. By introducing a discriminator function $f$ to identify inconsistencies in the estimated ratio, we formulate a loss that, when minimized, yields an accurate density ratio. By restricting $f$ to a Reproducing Kernel Hilbert Space (RKHS), we obtain a closed-form solution for the inner maximization, simplifying the optimization process. This approach can be viewed as a form of Rao-Blackwellization, reducing variance by conditioning on states rather than specific trajectory realizations.
Empirical Evaluation
We evaluated our method against several baselines, including Naive Average, Weighted Importance Sampling (WIS), and Model-based approaches, across three environments: a discrete Taxi grid-world, a continuous Pendulum task, and the high-dimensional SUMO traffic simulator.
Taxi Environment
In the Taxi environment, we tested robustness against trajectory length and behavior policy mismatch. As shown in Figure 1, standard WIS methods suffer from skyrocketing error as the truncated length $T$ increases. In contrast, our method remains stable, closely tracking the performance of an on-policy oracle.
Pendulum and Discount Factor Sensitivity
The Pendulum task highlights the impact of the discount factor $\gamma$. As $\gamma$ approaches 1, the effective horizon becomes infinite. Traditional IS methods typically fail in this regime. However, our density-ratio approach maintains low Mean Squared Error (MSE), demonstrating its suitability for near-infinite horizon problems as seen in Figure 2.
Conclusion
By directly estimating stationary density ratios, our method effectively breaks the Curse of Horizon in off-policy estimation. It provides a stable, low-variance alternative to trajectory-based importance sampling, enabling reliable evaluation in complex, long-horizon domains. Future work will explore scaling these techniques to high-dimensional visual inputs and integrating them into full off-policy optimization loops.
Reference: Liu, Q., Li, L., Tang, Z., & Zhou, D. (2018). Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation. 32nd Conference on Neural Information Processing Systems (NIPS 2018).
Summary updated