Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling

By Tengyang Xie, Yifei Ma, Yu-Xiang Wang. 2019

199 citations recorded by the source corpus.

Motivated by the many real-world applications of reinforcement learning (RL) that require safe-policy iterations, we consider the problem of off-policy evaluation (OPE) -- the problem of evaluating a new policy using the historical data obtained by different behavior policies -- under the model of nonstationary episodic Markov Decision Processes (MDP) with a long horizon and a large action space. Existing importance sampling (IS) methods often suffer from large variance that depends exponentially on the RL horizon $H$. To solve this problem, we consider a marginalized importance sampling (MIS) estimator that recursively estimates the state marginal distribution for the target policy at every step. MIS achieves a mean-squared error of $$ \frac{1}{n} \sum\nolimits_{t=1}^H\mathbb{E}_{\mu}\left[\frac{d_t^\pi(s_t)^2}{d_t^\mu(s_t)^2} \mathrm{Var}_{\mu}\left[\frac{\pi_t(a_t|s_t)}{\mu_t(a_t|s_t)}\big( V_{t+1}^\pi(s_{t+1}) + r_t\big) \middle| s_t\right]\right] + \tilde{O}(n^{-1.5}) $$ where $\mu$ and $\pi$ are the logging and target policies, $d_t^{\mu}(s_t)$ and $d_t^{\pi}(s_t)$ are the marginal distribution of the state at $t$th step, $H$ is the horizon, $n$ is the sample size and $V_{t+1}^\pi$ is the value function of the MDP under $\pi$. The result matches the Cramer-Rao lower bound in \citet{jiang2016doubly} up to a multiplicative factor of $H$. To the best of our knowledge, this is the first OPE estimation error bound with a polynomial dependence on $H$. Besides theory, we show empirical superiority of our method in time-varying, partially observable, and long-horizon RL environments.

Subfields: Artificial Intelligence, Computer Networks and Communications, Statistics and Probability, 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 Artificial Intelligence

In Computer Networks and Communications

In Statistics and Probability

In Reinforcement Learning

Citations in the corpus

Black-box Off-policy Estimation for Infinite-Horizon Reinforcement Learning (2020, methodology): “Importance reweighting, or inverse propensity scoring, has been used for off-policy RL (e.g., Precup et al., 2001; Murphy et al., 2001; Munos et al., 2016; Hanna et al., 2017; Xie et al., 2019).”
Batch Stationary Distribution Estimation (2020, background): “Assumption 2 follows previous work (Liu and Lee, 2017; Nachum et al., 2019), and is common in density ratio estimation (Sugiyama et al., 2008; Gretton et al., 2009) and off-policy evaluation (Wang et al., 2017; Xie et al., 2019).”
Minimax Weight and Q-Function Learning for Off-Policy Evaluation (2019, methodology): “A related method for finite horizon problems has been developed by Xie et al. (2019).”
Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimation (2019, background): “A recent work (Xie et al., 2019) has also explored the idea of tracking marginal state distribution shifts at every single time step in an episode, instead of the stationary state distribution across all time steps (Liu et al., 2018a).”
Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learning (2019, background): “…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).”
Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes (2019, background): “Speciﬁcally, The ﬁrst term on the ﬁrst line corresponds to the marginalized IPW estimator of Xie et al. (2019).”
Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning (2019, methodology): “Among the ideas that use marginalized state distribution [58] to improve over standard IPS, [27, 28] analyze double reinforcement learning estimator that makes use of both estimates for Q function and state density ratio.”
What are the Statistical Limits of Offline RL with Linear Function Approximation? (2020, background): “…2015, Li et al., 2015, Jiang and Li, 2016, Thomas and Brunskill, 2016, Guo et al., 2017, Wang et al., 2017, Liu et al., 2018, Farajtabar et al., 2018, Xie et al., 2019, Kallus and Uehara, 2019, Liu et al., 2019, Uehara and Jiang, 2019, Kallus and Uehara, 2020, Jiang and Huang, 2020, Feng et al.,…”
Efficiently Breaking the Curse of Horizon: Double Reinforcement Learning in Infinite-Horizon Processes (2019, background): “Off-policy evaluation (OPE) is the problem of estimating mean rewards of a given decision policy, known as the target 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., 201”
Efficient Evaluation of Natural Stochastic Policies in Offline Reinforcement Learning (2020, methodology): “Kallus and Uehara (2019a) show that the efficiency bound in the TMDP case is actually polynomial in H, O(CC ′R2maxH2/n), and give an estimator achieving it by combining marginalized IS (Xie et al., 2019) and q-modeling using cross-fold estimation.”
Near-Optimal Offline Reinforcement Learning via Double Variance Reduction (2021, methodology): “We also used a ﬁctitious estimator technique that originates from the OPE literature[Xie et al., 2019, Yin and Wang, 2020], but extended it to the stationary-transition case, and to the policy optimization problem.”
Flexible Option Learning (2021, methodology): “A possible solution would be to estimate this quantity by making use of recent approaches [Hallak and Mannor, 2017, Xie et al., 2019, Zhang et al., 2020].”
Statistically Efficient Off-Policy Policy Gradients (2020, unknown): “The estimation of q j is covered by Chen and Jiang (2019); Munos and Szepesv´ari (2008) and the estimation of µ j by Kallus and Uehara (2019a); Xie et al. (2019).”
Is Pessimism Provably Efficient for Offline RL? (2020, unknown): “See, e.g., (Jiang and Li, 2016; Thomas and Brunskill, 2016; Farajtabar et al., 2018; Liu et al., 2018; Xie et al., 2019; Nachum et al., 2019a;b; Tang et al., 2019; Kallus and Uehara, 2019; 2020; Jiang and Huang, 2020; Uehara et al., 2020; Duan et al., 2020; Yin and Wang, 2020; Yin et al., 2020;…”
Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation (2020, background): “On the theoretical side, the sharpest OPE error bound to our best knowledge is given by Xie et al. (2019) and Yin & Wang (2020), which applies to time-inhomogeneous, tabular MDP. Jiang & Li (2016) provided a Cramer-Rao lower bound for discrete-tree MDP.”
Minimax Confidence Interval for Off-Policy Evaluation and Policy Optimization (2020, methodology): “[6] Tengyang Xie, Yifei Ma, and Yu-Xiang Wang.”
Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL (2020, methodology): “However, methods to reduce the variance exist (Jiang & Li, 2016; Thomas & Brunskill, 2016; Liu et al., 2018; Xie et al., 2019).”
Harnessing Inﬁnite-Horizon Off-Policy Evaluation: Double Robustness via Duality (2019, background): “A recent work (Xie et al., 2019) has also explored the idea of tracking marginal state distribution shifts at every single time step in an episode, instead of the stationary state distribution across all time steps (Liu et al., 2018a).”