Minimax-optimal off-policy evaluation with linear function approximation

This paper studies the statistical theory of offpolicy policy evaluation with function approximation in batch data reinforcement learning problem. We consider a regression-based fitted Q iteration method, and show that it is equivalent to a modelbased 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 !2-divergence over the function class between the long-term distribution of target policy and the distribution of past data. This restricted !2-divergence characterizes the statistical limit of off-policy evaluation, and is both instance-dependent and function-classdependent. Further, we provide an easily computable confidence bound for the policy evaluator, which may be useful for optimistic planning and safe policy improvement.