On Minimax Optimal Offline Policy Evaluation

Abstract

This paper studies the off-policy evaluation problem, where one aims to estimate the value of a target policy based on a sample of observations collected by another policy. We first consider the multi-armed bandit case, establish a minimax risk lower bound, and analyze the risk of two standard estimators. It is shown, and verified in simulation, that one is minimax optimal up to a constant, while another can be arbitrarily worse, despite its empirical success and popularity. The results are applied to related problems in contextual bandits and fixed-horizon Markov decision processes, and are also related to semi-supervised learning.

References in corpus (3)

• Unbiased Offline Evaluation of Contextual-bandit-based News Article Recommendation Algorithms
• PEGASUS: A Policy Search Method for Large MDPs and POMDPs
• Analysis of Kernel Mean Matching under Covariate Shift

Cited by in corpus (7)

• Causal Bandits: Learning Good Interventions via Causal Inference
• An Asymptotically Optimal Policy for Uniform Bandits of Unknown Support
• Evaluating stochastic seeding strategies in networks
• Autoregressive Dynamics Models for Offline Policy Evaluation and Optimization
• Normal Bandits of Unknown Means and Variances: Asymptotic Optimality, Finite Horizon Regret Bounds, and a Solution to an Open Problem
• A comparative study of counterfactual estimators
• Asymptotically Optimal Sequential Experimentation Under Generalized Ranking