Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation

Qiang Liu, Lihong Li, Ziyang Tang, Dengyong Zhou

In Reinforcement Learning (RL), off-policy estimation (OPE) is the critical task of predicting how well a "target policy" will perform using only data collected by a different "behavior policy." This capability is essential in real-world scenarios—such as healthcare, robotics, or autonomous driving—where deploying and testing a new, unproven policy in the real world is either too risky or prohibitively expensive.

The standard statistical tool for OPE is Importance Sampling (IS). However, IS suffers from a fatal flaw in sequential decision-making: it calculates weights as a product of importance ratios for every single step in an agent's trajectory. As the trajectory length (the "horizon") grows, the variance of these weights grows exponentially. In infinite-horizon problems, this variance can become unbounded, rendering the estimator entirely useless. The authors of this paper refer to this exponential variance explosion as the "curse of horizon."

Bypassing the Curse: A Shift in Perspective

To solve this problem, the authors propose a novel method that shifts the focus away from full trajectories and instead looks at stationary state-visitation distributions. Rather than weighting the entire history of an agent's path, their method weights individual states and actions based on how much more (or less) likely the target policy is to visit them compared to the behavior policy.

Key Technical Contributions

  1. Density Ratio Estimation: The core of the method is defining a density ratio $w(s) = d_\pi(s) / d_{\pi_0}(s)$, where $d$ represents the stationary distribution of states under the target policy $\pi$ and the behavior policy $\pi_0$.
  2. Mini-Max Loss Function: Because the underlying transition probabilities of the environment are unknown, $w(s)$ cannot be calculated directly. To overcome this, the authors derive a mini-max objective based on the Bellman equation. They seek a ratio $w$ that minimizes the "violation" of the stationary property, tested against a "discriminator" function $f$ that attempts to find where the ratio is incorrect.
  3. RKHS Integration: By selecting the discriminator function from a Reproducing Kernel Hilbert Space (RKHS), the authors derive a closed-form solution for the inner maximization step. This makes the optimization process significantly more tractable and stable.
  4. Unified Framework: The proposed approach is versatile, working seamlessly for both average reward settings (where the discount factor $\gamma = 1$) and discounted reward settings ($0 < \gamma < 1$).

Theoretical Insights

The authors note that their approach can be viewed as a form of Rao-Blackwellization. By "averaging out" the specific, high-variance paths taken to reach a state and focusing solely on the state-visitation frequency, they drastically reduce variance without introducing bias.

Furthermore, a major theoretical connection is established with the Bellman equation. If the discriminator function $f$ perfectly matches the true value function $V^\pi$, the mini-max loss directly represents the estimation error of the total reward. By using the ratio of stationary distributions, the estimator's variance no longer depends on the length of the trajectory, effectively "breaking" the exponential dependence on the horizon.

Experimental Validation

The authors evaluated their method across three distinct environments of increasing complexity: a discrete Taxi Environment modified for infinite horizons, a continuous Pendulum control task, and the SUMO Traffic Simulator (a complex, open-source simulator used to model traffic light control).

Comprehensive performance metrics showing the stability of the proposed method (red) compared to traditional WIS methods as trajectory length increases.

Key Results

  • Variance Reduction: In the Taxi environment, as the trajectory length $T$ increased, the Mean Squared Error (MSE) of traditional Weighted Importance Sampling (WIS) exploded. In stark contrast, the proposed method remained completely stable and accurate, empirically proving its immunity to the curse of horizon.
  • Robustness to Discounting: As the discount factor $\gamma$ approached 1—a regime that typically breaks traditional IS methods—the proposed estimator maintained a low error rate.
  • Continuous Success: In the Pendulum task, the method successfully scaled to continuous state and action spaces. By utilizing neural networks to model the density ratio $w$ and Gaussian RBF kernels for the discriminator space, it significantly outperformed trajectory-based baselines.
Further evaluation demonstrating that the proposed method maintains a low, stable logMSE across extended truncated lengths, avoiding the variance explosion seen in baseline methods.

Limitations and Future Work

While the RKHS approach provides an elegant closed-form solution for the discriminator, the overall performance still relies heavily on the choice of kernel or the capacity of the neural network used to represent the density ratio. Additionally, scaling this density ratio estimation to extremely high-dimensional state spaces remains an open challenge.

Looking forward, because this work focuses primarily on estimation (evaluating a fixed policy), a natural and exciting next step is to integrate this stable density ratio estimator into policy optimization algorithms. Doing so could enable off-policy gradient methods to train better agents much more reliably in infinite-horizon settings.

Summary updated

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 in 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.
BibTeX
@inproceedings{liu2018breaking,
  author = {Qiang Liu and Lihong Li and Ziyang Tang and Dengyong Zhou},
  title = {{Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=jUv1I7CPsGy},
}
Figure