Breaking the Curse of Horizon in Off Policy Evaluation

256 concepts143 papers1 proposal

In reinforcement learning, evaluating a new strategy using historical data—known as Off-Policy Evaluation (OPE)—is essential for safely deploying AI in high-stakes domains like medicine, finance, and robotics. The standard mathematical tool for this is Importance Sampling (IS), which re-weights historical outcomes to match what a new target policy would have done.

However, when applied to long sequences of decisions, vanilla importance sampling fails catastrophically. This failure mode is widely known as the curse of horizon: the variance of the evaluation grows exponentially with the length of the time horizon, rendering estimates completely unstable.

To understand why this happens and how modern machine learning breaks this curse, we must look at how trajectory-based weights compound, and how we can bypass them entirely by shifting our perspective from paths to states.

The Anatomy of the Curse

The root cause of the curse of horizon lies in how traditional importance sampling handles sequential data. When evaluating a target policy $\pi$ using data generated by a behavior policy $\beta$, a trajectory-based estimator computes the product of action probability ratios at every single time step:

$$w_T = \prod_{t=1}^T \frac{\pi(a_t | s_t)}{\beta(a_t | s_t)}$$

As noted by Păduraru et al. in their empirical analysis of discrete Markov Decision Processes (MDPs), this compounding product causes the variance of the estimator to grow exponentially with the decision horizon $T$. Metelli demonstrated that even minor step-wise mismatches between the two policies compound over long sequences, leading to an explosive variance growth.

To build intuition, imagine a 100-step sequence where the target policy $\pi$ is only slightly more likely to take a chosen action than the behavior policy $\beta$ at each step—say, a ratio of $1.1$. Over 100 steps, this minor difference compounds into a massive weight: $1.1^{100} \approx 13,780$. Conversely, if the ratio is slightly lower ($0.9$), the weight vanishes to $0.9^{100} \approx 0.000026$.

As a result, the vast majority of historical trajectories receive a weight of zero, while a tiny fraction receive astronomical weights. This variance explosion makes it incredibly difficult to provide a reliable training signal for long-term tasks like multi-turn dialogues, as shown by Zhang et al., or lifetime medical treatments, as explored by Shi et al..

From Trajectories to Stationary Distributions

To bypass this exponential explosion, we must stop tracking how an agent arrived at a specific state (the trajectory path) and instead look at how often the agent occupies that state in the long run.

Qiang Liu et al. introduced a fundamental paradigm shift to solve this: instead of calculating the probability of an entire trajectory, we can estimate the density ratio of the stationary state-visitation distributions (or discounted state-visitation distributions) between the target and behavior policies:

$$d(s, a) = \frac{d^\pi(s, a)}{d^\beta(s, a)}$$

If we can accurately estimate this single, time-independent ratio for each state-action pair, we can weight the immediate rewards directly at that state. This completely avoids multiplying step-by-step action ratios over time, collapsing the variance growth from exponential to bounded or polynomial.

This core insight laid the foundation for the DICE (Distribution Correction Estimation) family of algorithms. For instance, Dai et al. developed DualDICE, which leverages Fenchel duality to estimate these stationary distribution corrections directly from logged data. Crucially, DualDICE is behavior-agnostic; it does not even need to know the original behavior policy $\beta$ that collected the data. By optimizing a stable dual objective, it bypasses per-step importance weights entirely.

This framework was subsequently expanded by Zhang et al. with GenDICE to handle generalized stationary values, while CoinDICE, developed by Dai et al., uses empirical likelihood to extract tight, reliable confidence intervals rather than just point estimates.

Minimax Optimization and Duality

Directly estimating distribution corrections can still be challenging in complex state spaces. To make OPE robust, researchers frame the problem as a minimax optimization game based on Bellman residuals.

Instead of explicitly computing high-variance importance weights, methods like MWL (Minimax Weight Learning) and MQL (Minimax Q-Function Learning), introduced by Uehara et al., solve a zero-sum game between a weight or value estimator and an adversarial evaluator. This formulation ensures that the evaluation remains stable even if the behavior policy is completely unknown.

Furthermore, Jiang et al. unified these approaches into a minimax value interval. They proved a new form of double robustness: the value interval remains valid if either the value-function class or the importance-weight class is well-specified. By optimizing against the worst-case Bellman error, these minimax frameworks prevent errors from accumulating over extended horizons.

Exploiting Markovian Structure and Representation Balancing

Another powerful weapon against the curse of horizon is the structure of the environment itself. Trajectory-based importance sampling treats every path as a unique string of events, ignoring the fact that Markov Decision Processes (MDPs) are memoryless.

Kallus et al. demonstrated that by explicitly utilizing the Markov property, Double Reinforcement Learning (DRL) can collapse variance growth from exponential to polynomial relative to the time horizon. This allows the model to pool data across different paths that intersect at the same state.

As Cheikhi et al. proved, this "pooling" capability is precisely why Temporal Difference (TD) methods statistically outperform direct Monte Carlo trajectory estimation—they effectively truncate the effective time horizon by leveraging shared state values across overlapping trajectories.

Taking this a step further, researchers have borrowed insights from causal inference to balance the data distribution itself. Instead of re-weighting raw data, Yao Liu et al. proposed learning a balanced state representation that explicitly minimizes the discrepancy between the behavior and target policy distributions.

When combined with stationary distribution corrections, as in the RepB-SDE framework by Lee et al., this approach eliminates the distribution shift at its root. By aligning the latent state representations with the target policy's discounted stationary distribution, the model can perform highly accurate offline policy evaluation over long durations without risking variance explosion.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 157 papers
  2. Version 1 · 2026-10-04 · 247 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_curse_of_horizon_4d1da8b2,
  title = {curse of horizon},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/curse-of-horizon/rdr_4d1da8b23d9f46399cd46f367188e594},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_curse_of_horizon_4d1da8b2_v2,
  title = {curse of horizon},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/curse-of-horizon/rdr_4d1da8b23d9f46399cd46f367188e594/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake