  Off-policy learning in dynamic decision problems is essential for providing
strong evidence that a new policy is better than the one in use. But how can we
prove superiority without testing the new policy? To answer this question, we
introduce the G-SCOPE algorithm that evaluates a new policy based on data
generated by the existing policy. Our algorithm is both computationally and
sample efficient because it greedily learns to exploit factored structure in
the dynamics of the environment. We present a finite sample analysis of our
approach and show through experiments that the algorithm scales well on
high-dimensional problems with few samples.
