Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation

Abstract

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.

References in corpus (5)

• Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling
• Off-Policy Policy Gradient with State Distribution Correction
• Modelling transition dynamics in MDPs with RKHS embeddings
• Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
• Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learning

Cited by in corpus (8)

• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
• Off-Policy Evaluation via the Regularized Lagrangian
• Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL
• Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
• Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning
• Statistical Bootstrapping for Uncertainty Estimation in Off-Policy Evaluation
• Nearly Horizon-Free Offline Reinforcement Learning
• A maximum-entropy approach to off-policy evaluation in average-reward MDPs