Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation

By Yaqi Duan, Mengdi Wang. 2020

166 citations recorded by the source corpus.

This paper studies the statistical theory of batch data reinforcement learning with function approximation. Consider the off-policy evaluation problem, which is to estimate the cumulative value of a new target policy from logged history generated by unknown behavioral policies. We study a regression-based fitted Q iteration method, and show that it is equivalent to a model-based method that estimates a conditional mean embedding of the transition operator. We prove that this method is information-theoretically optimal and has nearly minimal estimation error. In particular, by leveraging contraction property of Markov processes and martingale concentration, we establish a finite-sample instance-dependent error upper bound and a nearly-matching minimax lower bound. The policy evaluation error depends sharply on a restricted $\chi^2$-divergence over the function class between the long-term distribution of the target policy and the distribution of past data. This restricted $\chi^2$-divergence is both instance-dependent and function-class-dependent. It characterizes the statistical limit of off-policy evaluation. Further, we provide an easily computable confidence bound for the policy evaluator, which may be useful for optimistic planning and safe policy improvement.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

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 Management Science and Operations Research

Citations in the corpus

Offline RL Without Off-Policy Evaluation (2021, background): “Upper bounds generally require very strong assumptions on both the representation and limits on the distribution shift [Wang et al., 2021, Duan et al., 2020, Chen and Jiang, 2019].”
Is Pessimism Provably Efficient for Offline RL? (2020, methodology): “…Jiang, 2019; Tang et al., 2019; Kallus and Uehara, 2019; 2020; Fan et al., 2020; Xie and Jiang, 2020a;b; Jiang and Huang, 2020; Uehara et al., 2020; Duan et al., 2020; Yin et al., 2020; Qu and Wierman, 2020; Li et al., 2020; Liao et al., 2020; Nachum and Dai, 2020; Yang et al., 2020a; Zhang et…”
Reinforcement Learning: Theory and Algorithms (2019, methodology): “With regards to the simpler question of just policy evaluation — estimating the value of a given policy with offline data — [Duan and Wang, 2020] provide minimax optimal rates.”
Statistical Bootstrapping for Uncertainty Estimation in Off-Policy Evaluation (2020, background): “Indeed, the mathematical equivalence of QE and MB, even under certain function approximation schemes, has been recently demonstrated [5].”
Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL (2020, background): “For example, (Jiang & Li, 2016) present lower bounds for tabular RL and (Duan & Wang, 2020; Hao et al., 2020) for the linear setting under additional closure assumptions on the Bellman operator.”
Bellman-consistent Pessimism for Offline Reinforcement Learning (2021, methodology): “Therefore, it is important to carefully characterize the distribution shift, which we measure using the following definition, which generalizes prior definitions specific to linear function approximation [Agarwal et al., 2019; Duan et al., 2020]: Definition 1.”
Off-Policy Evaluation via the Regularized Lagrangian (2020, methodology): “While some approaches are model-based [10], or work by estimating the value function [8], most rely on importance reweighting to transform the off-policy data distribution to the on-policy target distribution.”
Near-Optimal Offline Reinforcement Learning via Double Variance Reduction (2021, background): “One major line of work is concerned with the off-policy evaluation (OPE) problem [Li et al., 2015, Jiang and Li, 2016, Liu et al., 2018, Kallus and Uehara, 2019a,b, Uehara and Jiang, 2019, Xie et al., 2019, Yin and Wang, 2020, Duan and Wang, 2020].”
Instabilities of Offline RL with Pre-Trained Neural Representation (2021, background): “We remark that variants of Lemma 4.2 have been known in the literature (see, e.g., [Duan et al., 2020] for a similar analysis in the ﬁnite-horizon setting).”