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

By Qiang Liu, Lihong Li, Ziyang Tang, Dengyong Zhou. 2018

396 citations recorded by the source corpus.

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.

Subfields: Computer Networks and Communications, Electrical and Electronic Engineering, Management Science and Operations Research, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Electrical and Electronic Engineering

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems (2020, background): “Alternatively, Liu et al. (2018) propose to use an adversarial approach to obtain the state-marginal importance ratios.”
Conservative Q-Learning for Offline Reinforcement Learning (2020, background): “Recent approaches [36, 17, 40, 60] use marginalized importance sampling by directly estimating the state-distribution importance ratios via some form of dynamic programming [34] and typically exhibit less variance than per-action importance sampling at the cost of bias.”
Black-box Off-policy Estimation for Infinite-Horizon Reinforcement Learning (2020, methodology): “• inverse propensity score (IPS) baseline introduced by [21].”
Batch Stationary Distribution Estimation (2020, methodology): “The target and behavior policies are set as in Liu et al. (2018).”
GenDICE: Generalized Offline Estimation of Stationary Values (2020, methodology): “In this specific setting, our methods achieve better results compared to IS, IPS and the model-based method.”
GradientDICE: Rethinking Generalized Offline Estimation of Stationary Values (2020, methodology): “Inspired by Hallak & Mannor (2017); Liu et al. (2018), Gelada & Bellemare (2019); Uehara & Jiang (2019) pro-pose different estimators for learning density ratios, either with semi-gradient updates (Sutton, 1988) or by restricting the function class to Reproducing Kernel Hilbert Space.”
AlgaeDICE: Policy Gradient from Arbitrary Experience (2019, background): “We will show in Theorem 6 that the optimal ζ∗ in Fenchel AlgaeDICE automatically satisfies the constraint ζ ∈ Z := {ζ ≥ 0,EdD [ζ (s, a)] = 1}, avoiding the nontrivial self-normalization step in Liu et al. (2018).”
Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learning (2019, methodology): “…policy, for a sequential decision-making problem using data generated by the log of another policy, known as the behavior policy (Jiang and Li, 2016; Li et al., 2015; Liu et al., 2018; Mahmood et al., 2014; Munos et al., 2016; Precup et al., 2000; Thomas and Brunskill, 2016; Xie et al., 2019).”
DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections (2019, methodology): “The ones that are most relevant to our work are a suite of recent techniques [16, 18, 27], which are all essentially based on the following steady-state property of stationary Markov processes: where we have simpliﬁed the identity by restricting to discrete state and action spaces.”
Intrinsically Efficient, Stable, and Bounded Off-Policy Evaluation for Reinforcement Learning (2019, background): “[9] Q.”
Learning When-to-Treat Policies (2019, methodology): “In observational studies treatment probabilities need to be estimated from data, and it is known that the variant of (6) with estimated weights γ̂ (i)t (π) can perform poorly with even mild estimation error (see, e.g., Y. Liu et al. 2018).”
Generalized Off-Policy Actor-Critic (2019, methodology): “Liu et al. (2018) prove that ¯ c is the unique solution for a minimax problem, which involves maximization over a function set F .”
Information-Theoretic Considerations in Batch Reinforcement Learning (2019, background): “, that T̂F being a contraction (Gordon, 1995; Szepesvári & Smart, 2004; Lizotte, 2011; Pires & Szepesvári, 2016)), and can instead take the form of requiring another function class to realize other objects of interest, such as state distributions (Chen et al., 2018; Liu et al., 2018).”
Hyperparameter Selection for Offline Reinforcement Learning (2020, methodology): “More recently, marginal importance sampling methods have been developed that directly estimate the stationary state distribution ratio under the two policies (Liu et al., 2018; Nachum et al., 2019). The method proposed in Liu et al. (2018) require knowledge of the behavior policy.”
Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes (2019, background): “While previously it was just shown to be a limitation specifically of IS and DR estimators (Liu et al., 2018; Xie et al., 2019), this result shows it must plague any estimator that targets the NMDP model and that it is insurmountable without leveraging additional structure that further narrows the m”
Off-Policy Policy Gradient with Stationary Distribution Correction (2019, methodology): “Some authors consider model-based approaches to OPPE (Farajtabar et al., 2018; Liu et al., 2018b), which usually perform better than importance sampling approaches empirically in policy evaluation settings.”
Batch Policy Learning under Constraints (2019, background): “In general, off-policy policy evaluation in longhorizon domains is known to be challenging (Liu et al., 2018; Guo et al., 2017).”