  Direct optimization is an appealing framework that replaces integration with
optimization of a random objective for approximating gradients in models with
discrete random variables. A$^\star$ sampling is a framework for optimizing
such random objectives over large spaces. We show how to combine these
techniques to yield a reinforcement learning algorithm that approximates a
policy gradient by finding trajectories that optimize a random objective. We
call the resulting algorithms "direct policy gradient" (DirPG) algorithms. A
main benefit of DirPG algorithms is that they allow the insertion of domain
knowledge in the form of upper bounds on return-to-go at training time, like is
used in heuristic search, while still directly computing a policy gradient. We
further analyze their properties, showing there are cases where DirPG has an
exponentially larger probability of sampling informative gradients compared to
REINFORCE. We also show that there is a built-in variance reduction technique
and that a parameter that was previously viewed as a numerical approximation
can be interpreted as controlling risk sensitivity. Empirically, we evaluate
the effect of key degrees of freedom and show that the algorithm performs well
in illustrative domains compared to baselines.
