Is this the same as the curse of dimensionality?

No. Here the focus is sequence length and its effect on evaluation difficulty.

Does per-decision weighting always solve it?

No, particularly when important rewards occur late.

Can alternative methods help?

Yes, but their benefits depend on structure, coverage and estimation quality.

AI Glossary / Reinforcement learning and robotics / Advanced

Curse of horizon in off-policy evaluation

Definition

The curse of horizon in off-policy evaluation refers to the difficulty of estimating a policy's performance from another policy's data as decision sequences become long. One example is growing variance of trajectory importance-sampling estimators, whose weights multiply action-probability ratios across many steps. The difficulty depends on the estimator and problem conditions; it is not an assertion that every long-horizon evaluation is impossible.

What it means

Off-policy evaluation uses experience collected by a behavior policy to estimate the expected return of a different target policy. The two policies can favor different actions, causing them to generate different trajectories. Importance sampling corrects this mismatch by assigning greater weight to trajectories that are relatively more likely under the target.
Over many steps, even moderate differences can compound. Most observed trajectories may receive tiny weights while a few receive enormous weights. An estimator can be correct on average over repeated datasets yet be unreliable on the dataset actually available. Unbiasedness differs from precision.

How it works

For a trajectory of H decisions, ordinary importance sampling uses a weight equal to the product of pi(a_t|s_t) / mu(a_t|s_t), where pi is the target policy and mu is the behavior policy. Multiplying the observed return by this weight corrects the trajectory distribution under suitable support and data-generation assumptions.
The behavior policy must assign positive probability to actions needed by the target in relevant situations. A zero denominator where the target has support is a coverage failure, not just a large-variance problem. Accurate behavior probabilities also matter.
Per-decision importance sampling avoids weighting early rewards by actions that occurred afterward. Other methods use marginal state-action or stationary distribution ratios, model estimates or combinations of components. These approaches can reduce horizon-related difficulties under appropriate conditions, but no single method has uniformly smaller variance in every finite-horizon problem. Estimated ratios and models introduce their own errors, so a claim of improvement needs more than a method name.

Three practical examples

Simulated navigation: evaluating a new route-selection policy from old trajectories becomes difficult when the new policy favors action sequences rarely present in the logs.
Sequential recommendation research: a candidate policy changes several decisions within an interaction. Evaluation must account for how earlier choices affect later observations and choices.
Estimator diagnostics: analysts inspect the distribution of importance weights and sensitivity to a few trajectories, rather than treating the raw number of logged records as the effective amount of information.

Think of it this way

Imagine using old travel diaries to evaluate a traveler who follows a very particular itinerary. Matching one choice is common, but matching twenty consecutive choices may be rare. Giving the few matching diaries large influence can correct an average mathematically while making the answer depend heavily on whether any such diary appears.

Worked example

Consider H decisions. At every step, the behavior policy independently chooses A or B with probability one-half each. The target policy always chooses A. Every complete trajectory receives terminal reward 1, regardless of its actions, and there are no other rewards. Return is undiscounted.
For an observed A, the action ratio is 1 divided by 0.5, or 2. For an observed B, it is zero divided by 0.5, or zero. Thus a trajectory containing any B has total weight zero. The all-A trajectory has weight 2^H and occurs under the behavior policy with probability 2^(-H).
The ordinary trajectory importance-sampling estimate from one trajectory is therefore 2^H with probability 2^(-H), and zero otherwise. Its expectation is 2^H times 2^(-H) = 1, correctly matching the target's expected return.
Its second moment is (2^H) squared times 2^(-H) = 2^H. Subtracting the squared mean gives variance 2^H - 1. At H = 5, the nonzero weight is 32 and variance is 31. At H = 10, they become 1,024 and 1,023. At H = 20, they become 1,048,576 and 1,048,575. The all-A trajectory then appears with probability about one in a million.
For the average of N independent trajectories, variance is (2^H - 1)/N. Holding this variance at the same level as H increases can therefore require exponentially more trajectories for this estimator and example.
Constant reward isolates the weighting problem. If that reward structure were known, no elaborate estimator would be needed to discover that the target return is 1. This is not an impossibility result for every estimator: it demonstrates how ordinary trajectory weighting can waste available structure. Per-decision weighting does not shorten the weight attached to the final reward here because it comes after all H decisions.

Illustrative case study

Fictional company Cedar Analytics evaluates a simulated sequential policy using logged trajectories. Its team compares estimates across horizon lengths and plots how much influence individual trajectories receive. It checks whether apparently stable results remain stable when unusually large weights are examined.
The analysts compare suitable alternative estimators and document the assumptions behind each. They avoid treating a large log as sufficient evidence when target behavior has weak coverage. This fictional workflow reports no measured results.

Common misconceptions and mistakes

Long horizon does not automatically cause exponential variance in every problem. Policy similarity, rewards, dynamics and estimator structure all matter. The example establishes one exponential case.
Unbiasedness does not mean a small dataset produces a close answer. Clipping weights can reduce variability but generally changes bias, while self-normalization has different finite-sample properties from ordinary importance sampling. Neither should be silently substituted into a calculation. Finally, low reported variance can be misleading if important target behaviors are absent or the model assumptions are wrong.

Business use

The concept helps explain why evaluating a new sequential decision policy from existing logs can require more evidence than evaluating isolated decisions. Teams should record behavior probabilities when appropriate, assess target-policy coverage and report uncertainty and sensitivity. Evaluation requires assumptions and data that support the intended decision.

Check your understanding

Why did any B make the example weight zero?

Answer: The target policy never chooses B.

Why was the estimator still unbiased?

Answer: The rare large weight balanced its low probability in expectation.

Why did variance grow exponentially?

Answer: The second moment grew as 2^H while the mean stayed one.

Related terms

Importance sampling
Effective sample size
Off-policy evaluation
Per-decision importance sampling
Distribution ratio
Coverage
Doubly robust estimation

Learn next

Compare ordinary trajectory weighting with an estimator that uses the problem's structure, and examine both bias and variance rather than only average estimates.

Sources

Liu, Bacon and Brunskill, Understanding the Curse of Horizon in Off-Policy Evaluation via Conditional Importance Sampling, ICML 2020: https://proceedings.mlr.press/v119/liu20a/liu20a.pdf . The binary-action calculation and company scenario are original illustrations.

Previous: Curse of dimensionality Next: Curve fitting