Distributed Natural Policy Gradients with Poissonized Determinantal Averaging

Natural Policy Gradients (NPG) can exploit the low-rank structure of the empirical Fisher via the Woodbury identity, replacing a parameter-space solve with a sample-space system. While computationally attractive, this formulation incurs $\mathcal{O}(Bd)$ memory for $B$ samples and $d$ parameters. Data parallelism can reduce this cost, but naively averaging local empirical NPG directions does not recover the pooled-batch estimator due to finite-sample bias from Fisher inversion and Fisher–gradient coupling. We propose Poissonized Determinantal Averaging (PDA), a communication-efficient distributed NPG method based on Poissonized local sampling and determinant-weighted aggregation. PDA communicates only one parameter-sized direction and one scalar per worker. We show that, for any fixed number of workers $N$, PDA matches the full $1/(NB)$ leading-order bias term of pooled Poissonized NPG as the expected local batch size $B$ grows, leaving an ${\mathcal{O}}_N(B^{-2})$ gap in expectation. For fixed $B$, PDA also converges to the population damped NPG direction as $N\to \infty$. Across eight MuJoCo and Procgen tasks, PDA more closely matches pooled NPG than uniform averaging while retaining favorable compute and memory scaling.