  We study the sample complexity of reducing reinforcement learning to a
sequence of empirical risk minimization problems over the policy space. Such
reductions-based algorithms exhibit local convergence in the function space, as
opposed to the parameter space for policy gradient algorithms, and thus are
unaffected by the possibly non-linear or discontinuous parameterization of the
policy class. We propose a variance-reduced variant of Conservative Policy
Iteration that improves the sample complexity of producing a
$\varepsilon$-functional local optimum from $O(\varepsilon^{-4})$ to
$O(\varepsilon^{-3})$. Under state-coverage and policy-completeness
assumptions, the algorithm enjoys $\varepsilon$-global optimality after
sampling $O(\varepsilon^{-2})$ times, improving upon the previously established
$O(\varepsilon^{-3})$ sample requirement.
