  Policy gradient methods can solve complex tasks but often fail when the
dimensionality of the action-space or objective multiplicity grow very large.
This occurs, in part, because the variance on score-based gradient estimators
scales quadratically. In this paper, we address this problem through a factor
baseline which exploits independence structure encoded in a novel action-target
influence network. Factored policy gradients (FPGs), which follow, provide a
common framework for analysing key state-of-the-art algorithms, are shown to
generalise traditional policy gradients, and yield a principled way of
incorporating prior knowledge of a problem domain's generative processes. We
provide an analysis of the proposed estimator and identify the conditions under
which variance is reduced. The algorithmic aspects of FPGs are discussed,
including optimal policy factorisation, as characterised by minimum biclique
coverings, and the implications for the bias-variance trade-off of incorrectly
specifying the network. Finally, we demonstrate the performance advantages of
our algorithm on large-scale bandit and traffic intersection problems,
providing a novel contribution to the latter in the form of a spatial
approximation.
