Source-linked AI summary
Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation
Qiang Liu, Lihong Li, Ziyang Tang, Dengyong Zhou
TL;DR
Off-policy evaluation must estimate a target policy’s reward from behavior-policy data, while importance sampling becomes unreliable as horizons lengthen. The paper estimates stationary state-visitation density ratios directly with a mini-max objective, and experiments show improved behavior for longer trajectories and larger discount factors. The method assumes an ergodic finite-state Markov chain for its average-reward guarantee.
Problem
Off-policy estimation requires estimating a target policy’s expected reward from behavior-policy samples, while importance-sampling variance can grow exponentially with horizon.
Method
The paper directly estimates the stationary state-visitation density ratio between target and behavior policies from behavior trajectories using a mini-max objective.
Results
In experiments, the density-ratio method performs almost as well as the on-policy oracle in Taxi, while outperforming other methods and remaining robust as trajectory length and discount factor increase.
Takeaways & Limitations
Applying importance weighting to stationary visitation distributions avoids cumulative trajectory products, reducing horizon dependence for long- or infinite-horizon estimation.
Takeaways & Limitations
The average-reward theoretical characterization assumes a finite-state ergodic Markov chain with a unique invariant distribution.
Abstract
from arXiv · showhide
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.
1 Introduction
Off-policy evaluation estimates a target policy’s expected reward from behavior-policy samples, but long trajectories make importance sampling unreliable. The paper addresses this curse of horizon by estimating stationary visitation-distribution ratios with a mini-max approach.
- Off-policy estimation evaluates a target policy using samples collected under a different behavior policy.
- Importance-sampling weights multiply across trajectory steps, causing variance to grow exponentially with horizon.
- Ad hoc trajectory modifications can introduce hard-to-control bias into the final estimate.
- The paper calls this long-horizon instability the “curse of horizon” in off-policy learning.
- The proposed method applies importance sampling to average state-action visitation distributions rather than whole trajectories, avoiding cumulative time products.
- A mini-max loss estimates stationary density ratios using only behavior-distribution trajectories despite unavailable environment transition probabilities.
2 Background
The background formalizes infinite-horizon policy evaluation and reviews trajectory-wise and per-decision importance sampling. It explains why multiplicative trajectory weights create the curse of horizon, especially for infinite-horizon problems.
- Infinite-horizon evaluation estimates a target policy’s expected reward from observed trajectories without termination.
- The paper distinguishes average reward, with γ = 1, from discounted reward, with 0 < γ < 1.
- The Bellman equations provide fixed-point characterizations for value functions under both average and discounted reward criteria.
- Trajectory-wise importance sampling changes measure using a trajectory density ratio, while weighted IS self-normalizes those weights.
- Per-decision importance sampling applies prefix weights to each reward and can reduce variance relative to trajectory-wise estimators.
- The trajectory weight is a product of T density ratios, so its variance can grow exponentially with T and may be undefined at infinite horizon.
- A circular-state example illustrates that importance-sampling estimators can suffer exponentially in long-horizon settings.
3 Off-Policy Estimation via Stationary State Density Ratio Estimation
The paper replaces trajectory-level importance sampling with state-visitation density-ratio estimation, enabling off-policy evaluation without cumulative horizon-dependent weighting. It characterizes the ratio through stationary-distribution equations and estimates it using a mini-max objective, with theoretical reward-error guarantees.
- State-space importance sampling uses average visitation distributions rather than whole trajectories, removing cumulative time-product ratios and horizon dependence.The estimator operates on state-action pairs and can substantially reduce variance in long- or infinite-horizon problems.
- The state-visitation ratio wπ/π0(s) = dπ(s)/dπ0(s) reweights behavior-policy state-action samples alongside the action ratio π(a|s)/π0(a|s).The visitation ratio is unknown and must be estimated from behavior-distribution data.
- 3.1 Average Reward Case: In the average-reward case, under a unique invariant target distribution and positive behavior visitation, the density ratio is characterized by Theorem 1 up to a constant factor.The theorem relies on the target transition chain having a unique invariant distribution and dπ0(s) > 0 for every state.
- A mini-max loss over discriminator functions estimates the visitation ratio from behavior transition pairs, while normalization prevents the trivial zero solution.Neural networks and RKHS unit balls are proposed as discriminator classes; the RKHS case yields a closed-form solution.
- 3.2 Discounted Reward Case: The discounted case represents visitation through a restart-induced Markov chain, and its loss characterizes the exact ratio for 0 < γ < 1.For γ = 1, the characterization determines the ratio only up to scale, so practical pre-normalization is used.
- 3.3 Further Theoretical Analysis: When Vπ belongs to the discriminator class and w is normalized, the mini-max loss bounds reward-estimation error through |Rπ[w] − Rπ| ≤ maxf∈F L(w, f).At the true value function, the loss equals the difference between the true and estimated rewards.
4 Related Work
Prior work largely addresses short-horizon or model-based settings, while infinite-horizon off-policy estimation remains less developed. The paper distinguishes its behavior-only stationary-ratio approach from value-function learning and traditional two-sample density-ratio estimation.
- Off-policy value estimation targets a single scalar policy value, whereas off-policy value-function learning estimates value functions; the proposed idea may extend to the latter as future work.The paper notes that estimated density ratios could weight observed transitions for value-function estimation.
- Long-horizon importance-sampling methods face exponential variance growth, and worst-case mean squared error can depend exponentially on horizon.Variance-reduction techniques improve estimators but do not generally remove the exponential horizon dependence.
- Few prior methods directly target infinite-horizon problems; simulation-based approaches require a reliable model, while COP-TD reports asymptotic consistency but may be difficult to extend to continuous spaces.These constraints distinguish the paper’s behavior-only density-ratio setting from nearby approaches.
- Traditional two-sample density-ratio estimators are inapplicable because the setting provides samples only from the behavior visitation distribution, not the target distribution.The proposed method exploits the temporal structure of Markov decision processes.
5 Experiment
Experiments compare the proposed method with importance-sampling baselines across Taxi, Pendulum, and SUMO settings. The method performs favorably in long-horizon and discounted-reward experiments, while standard IS methods deteriorate as horizon or discount factor increases.
- Experimental setup: Experiments compare the proposed method with trajectory-wise and step-wise IS/WIS, on-policy oracle, naive averaging, and other baselines across multiple environments.The environments include discrete Taxi, continuous-state Pendulum, and the SUMO traffic simulator.
- Taxi: In Taxi average-reward experiments, the proposed method performs almost as well as the on-policy oracle and outperforms the other methods.The estimated state distribution also matches the true distribution at convergence, according to the reported total-variation and scatter-plot analyses.
- Taxi: In Taxi discounted-reward experiments, standard IS methods deteriorate as truncated length T and discount factor γ increase, whereas the density-ratio method improves with T and remains robust as γ increases.Figure 2 varies trajectory count, policy difference, truncated length, and discount factor under the stated default settings.
- Pendulum: In Pendulum, the proposed method generally outperforms trajectory-wise and step-wise WIS and performs favorably in long-horizon settings.The experiments vary behavior-policy mixing, truncated length, and discount factor for average- and discounted-reward cases.
- SUMO: On SUMO, the reported results again find the proposed method consistently better than standard IS methods.The study varies the number of trajectories, behavior policies, and truncation size in an average-reward traffic-control setting.
6 Conclusions
The paper studies infinite-horizon off-policy estimation and proposes direct estimation of the stationary state density ratio between target and behavior policies. It presents a mini-max objective with theoretical properties and identifies future work in scaling, value-function estimation, and policy optimization.
- Conclusion: The paper develops an algorithm for infinite-horizon off-policy estimation based on the stationary state density ratio between target and behavior policies.The conclusion states this as the paper’s central approach.
- Conclusion: The mini-max objective has theoretical properties and connects the estimation problem with Bellman equations.The paper describes this connection as an avenue for further investigation.
- Conclusion: Future directions include scaling to larger problems, estimating value functions, and leveraging off-policy data for policy optimization.These are explicitly identified as future work.
A Several Variants of IS- and WIS-based Estimators
The section contrasts trajectory-wise and step-wise IS/WIS estimators with the proposed estimator’s additional Rao-Blackwellization. Replacing trajectory-prefix weights with state-action-level weights is presented as a route to lower variance, subject to density-ratio estimation error.
- Step-wise estimators: Step-wise IS replaces the full-trajectory weight with a prefix weight for each reward, reducing variance without changing the expectation.This follows from conditioning the full weight on the trajectory prefix, making step-wise estimation a Rao-Blackwellization of trajectory-wise IS.
- Weighted estimators: Self-normalized trajectory-wise and step-wise WIS estimators introduce bias but often have lower variance than their unnormalized counterparts.The section notes that Step-wise WIS often performs best among these variants.
- Estimator variants: When normalization constants equal the sample count, trajectory-wise and step-wise IS provide unbiased estimates; self-normalization instead yields weighted estimators.The distinction is determined by whether Zt equals m for every t.
- Proposed estimator: The proposed method is described as a further Rao-Blackwellization of the step-wise estimators.It replaces the prefix weight w0:t with a state-action-level weight wt:t.
- Proposed estimator: Ignoring estimation error in wt:t, the proposed estimator is expected to have smaller variance than trajectory-wise and step-wise estimators.The comparison concerns variance from the weighting scheme rather than error in estimating the new density ratio.
B A motivating example
The motivating example contrasts horizon-dependent trajectory-wise importance sampling with stationary density-ratio weighting, showing why the latter can avoid variance growth in long-horizon settings.
- MDP setting: The circular MDP uses n odd states, left and right actions, and deterministic rewards of 0 for left and 1 for right.The behavior and target policies choose right with probabilities ρ and 1 −ρ, respectively, while analysis focuses on average reward.
- Stationary ratio: The stationary state distributions under the behavior and target policies are identical and uniform, so dπ(s)/dπ0(s) = 1.Ergodicity follows from the odd number of states and symmetric policy structure.
- Stationary ratio: The stationary density ratios for both actions are independent of trajectory length and have zero variance.For the left action, the corresponding ratio is (1 −ρ)/ρ; the right-action ratio is given analogously.
- Trajectory-wise variance: Trajectory-wise importance weights have variance that grows exponentially with the horizon T when ρ ≠ 1/2.The variance grows in the order of Aρ^T, with Aρ > 1 for ρ ≠ 1/2; ρ = 1/2 is the on-policy case.
- Estimator analysis: The example’s moments establish unbiasedness for the trajectory weight and show why self-normalization does not remove exponential horizon dependence.The expected weight is 1, and the weighted reward expectation equals the target-policy expected reward; WIS remains exponentially dependent on T.
C Proofs
The proofs characterize when the mini-max objective identifies the stationary density ratio and establish uniqueness properties for discounted and average-reward settings.
- RKHS foundations: The RKHS construction uses positive-definite kernels and the reproducing property to express functions and the mini-max loss through inner products.The reproducing property is f(s) = ⟨f(·), k(s, ·)⟩H.
- Density-ratio identification: The mini-max loss vanishes for every test function exactly when the weighted behavior distribution is proportional to the target stationary distribution.For discounted problems, this identifies w(s) with wπ/π0(s); for average reward, the ratio is identified up to proportionality.
- Discounted versus average reward: The discounted and average-reward cases differ because the next-state marginal under the stationary transition joint distribution is not generally the same as the current-state stationary marginal.The distinction is explicit for discounted visitation distributions and average-reward stationary distributions.
- Operator properties: Under irreducibility, solutions to the average-reward Poisson equation are unique up to an additive constant, while the discounted solution is unique.The proof derives this from the transition operator and rules out nonconstant functions in its null space.
- Reward and value relations: The proofs connect the operator formulation to value functions and show that the target-policy reward representation can be written using behavior-policy samples and single-step policy ratios.The relevant relation defines rπ(s) through βπ/π0(a|s) and invokes average- or discounted-reward Bellman equations.
D Algorithm Details
The algorithms estimate the density ratio with neural-network parameterization and empirical mini-max losses, using different data augmentation and sampling schemes for average and discounted rewards.
- Average reward: Algorithm 1 approximates the average-reward mini-max loss by empirical averaging over observed transition data.The density ratio is parameterized as wθ and updated by gradient descent on the empirical objective.
- Discounted reward: The discounted algorithm augments the data with a dummy transition to absorb the additional initial-state term in the discounted loss.The dummy transition is assigned a loss contribution involving 1 −w(s0)f(s0), producing a form analogous to the average-reward objective.
- Mini-max objective: For an RKHS function class, the squared mini-max objective becomes an expectation of paired temporal-difference terms multiplied by a kernel.This closed-form expression applies when the function class is an RKHS ball with kernel k(s′, ¯s′).
- Discounted reward: Discounted minibatches sample time steps with probability proportional to γ^(t+1), while the dummy transition is selected with probability 1 −γ.This sampling scheme approximates the augmented discounted visitation distribution.
E Information on SUMO Traffic Simulator
The SUMO experiments formulate traffic-light control with lane-count states, simplified phase actions, vehicle-count-based rewards, and policies trained across successive iterations.
- States: SUMO states count vehicles on lanes around each traffic-light intersection to provide control-relevant but imperfect information.This replaces a more complex image-like representation of surrounding traffic.
- Actions: The traffic-light action space simplifies four signal phases, with each reinforcement-learning step representing six simulator time steps.Three additional yellow-light steps buffer transitions between different actions.
- Rewards: Rewards approximate the negative aggregate travel-time objective using six times the current total vehicle count.The stated goal is to minimize total travelling time for all vehicles.
- Policy: A linear softmax policy is trained with cross-entropy for 10 iterations and used as the target policy.Policies from training iterations 6 through 9 serve as behavior policies and correspond to x-ticks 1–4 in Figure 4(c).
- Environment generation: Vehicle routes are constrained to at most one turn and generated with fixed route-specific probabilities to create a randomized environment.Routes connect pairs of exit nodes in the network.