2015 · 62 citations · 17 references
BusinessDecision SciencesDecision TheoryMarkov Decision ProcessesOptimizationOptimal ControlReinforcement LearningReinforcement Learning FoundationsBandit AlgorithmsContextual BanditsMinimax RiskOff-policy EvaluationOff-policy LearningOff-policy Value EstimationOn-policy Value EstimationSmall-sample Properties
This paper studies the off-policy evaluation prob-lem, 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 single-state, or multi-armed bandit case, estab-lish a finite-time minimax risk lower bound, and analyze the risk of three standard estimators. For the so-called regression estimator, we show that while it is asymptotically optimal, for small sam-ple sizes it may perform suboptimally compared to an ideal oracle up to a multiplicative factor that depends on the number of actions. We also show that the other two popular estimators can be ar-bitrarily worse than the optimal, even in the limit of infinitely many data points. The performance of the estimators are studied in synthetic and real problems; illustrating the methods strengths and weaknesses. We also discuss the implications of these results for off-policy evaluation problems in contextual bandits and fixed-horizon Markov decision processes. 1
17
Statistics and Causal Inference
Paul W. Holland · Journal of the American Statistical Association · 1986 · 5.1K citations
Eric R. Ziegel, E. L. Lehmann, George Casella · Technometrics · 1999 · 4.3K citations