Breaking the Curse of Horizon in Policy Evaluation

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2247 papers318 conceptsfrozen 2026-10-04

Off-Policy Evaluation (OPE) is the "holy grail" of data-driven decision-making: it allows us to predict how a new strategy (the target policy) will perform using only historical data collected by a different strategy (the behavior policy). In high-stakes domains like healthcare or autonomous driving, where testing a bad idea in the real world is catastrophic, OPE is essential.

However, OPE faces a fundamental mathematical wall known as the Curse of Horizon. As the length of the decision-making sequence grows, the variance of our estimates typically explodes exponentially. Researchers have spent the last decade developing structural "brakes" to stop this explosion.

The Exponential Explosion of Importance Sampling

The traditional tool for OPE is Importance Sampling (IS). To estimate the value of a new policy, IS weights each trajectory in the historical data by the ratio of the probability of that trajectory occurring under the new policy versus the old one.

The problem, as noted by Zhaohan Daniel Guo, Philip S. Thomas, and Emma Brunskill in Using Options for Long-Horizon Off-Policy Evaluation, is that this weight is a product of action probabilities across every time step. If a trajectory has 100 steps, and the target policy is even slightly different from the behavior policy at each step, the resulting weight is a product of 100 ratios. This leads to "vanishing" or "exploding" weights, making the final estimate either zero or infinitely noisy.

This instability is particularly acute in longitudinal studies. Roy J. Adams and Michael G. Rosenblum show in The Impact of Time Series Length and Discretization on Longitudinal Causal Estimation Methods that even increasing the frequency of data collection (discretization) can trigger this variance explosion, as it artificially lengthens the sequence of decisions.

Breaking the Curse with Markovianity

The key to breaking the curse is realizing that we don't always need to weight entire trajectories. If the environment is Markovian—meaning the future depends only on the current state, not the path taken to get there—we can "marginalize" the weights.

Instead of calculating the probability of a whole path, we calculate the Marginal Density Ratio: the ratio of how often a specific state-action pair $(s, a)$ is visited under the target policy versus the behavior policy. Masatoshi Uehara, Jiawei Huang, and Nan Jiang demonstrate in Minimax Weight and Q-Function Learning for Off-Policy Evaluation that this shift from trajectory-level to state-level weights transforms the variance growth from exponential to polynomial.

Nathan Kallus and Masatoshi Uehara further formalize this in Efficiently Breaking the Curse of Horizon, proving that by leveraging time-invariant Markov structures, we can achieve the theoretical efficiency bound for policy evaluation even in infinite-horizon settings.

Pooling and Truncation: Why TD Learning Works

Another way to fight the horizon is to stop looking so far into the future. Temporal Difference (TD) learning achieves this by "bootstrapping"—updating a state's value based on the estimated value of the next state, rather than waiting for the final reward.

In On the Statistical Benefits of Temporal Difference Learning, David Cheikhi and Daniel Russo provide the intuition: TD learning "pools" data across different trajectories that pass through the same state. This effectively "truncates" the horizon because the variance of the distant future cancels out when comparing two actions that eventually lead to the same state distribution.

Similarly, Riccardo Poiani and Alberto Maria Metelli argue in Truncating Trajectories in Monte Carlo Reinforcement Learning that for discounted rewards, the distant future matters very little for the current update. By strategically cutting trajectories short, we can trade a tiny amount of bias for a massive reduction in variance.

Representation and Hierarchy

When the state space is too complex for simple marginalization, researchers turn to representation learning and hierarchy.

  • Balanced Representations: Yao Liu and Omer Gottesman introduced Representation Balancing MDPs (RepBM) in Representation Balancing MDPs for Off-policy Policy Evaluation. They learn a state representation that minimizes the discrepancy between the behavior and evaluation distributions, making the importance weights more stable.
  • Hierarchical Decomposition: For extremely long tasks, Bo Jin proposes Hierarchical Diffusion (HDMI) in Hierarchical Diffusion for Offline Decision Making. By breaking a long-range task into subgoals, the agent only needs to solve several short-horizon problems, preventing the accumulation of errors that usually plagues "flat" RL methods.

Summary of the Shift

The research direction across these 182 papers is a move away from "black-box" trajectory estimation toward structural exploitation. By assuming Markovianity (Chengchun Shi), using marginalized weights (Nan Jiang), or decomposing the value function (Hongyao Tang), the field is transforming OPE from a high-variance gamble into a reliable statistical tool for long-term decision-making.

Papers in this version

Showing 60 of 247 papers.

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 1, frozen text):

@misc{lacuna_breaking_the_curse_of_horizon_in_policy__4d1da8b2_v1,
  title = {Breaking the Curse of Horizon in Policy Evaluation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/breaking-the-curse-of-horizon-in-policy-evaluation/rdr_4d1da8b23d9f46399cd46f367188e594/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}