Data-Efficient Policy Evaluation Through Behavior Policy Search
  We consider the task of evaluating a policy for a Markov decision process
(MDP). The standard unbiased technique for evaluating a policy is to deploy the
policy and observe its performance. We show that the data collected from
deploying a different policy, commonly called the behavior policy, can be used
to produce unbiased estimates with lower mean squared error than this standard
technique. We derive an analytic expression for the optimal behavior policy ---
the behavior policy that minimizes the mean squared error of the resulting
estimates. Because this expression depends on terms that are unknown in
practice, we propose a novel policy evaluation sub-problem, behavior policy
search: searching for a behavior policy that reduces mean squared error. We
present a behavior policy search algorithm and empirically demonstrate its
effectiveness in lowering the mean squared error of policy performance
estimates.
