acceptodds
Under review as a conference paper at ICLR 2027

Distributed Natural Policy Gradients with Poissonized Determinantal Averaging

Abstract

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 memory for samples and 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 , PDA matches the full leading-order bias term of pooled Poissonized NPG as the expected local batch size grows, leaving an gap in expectation. For fixed , PDA also converges to the population damped NPG direction as . Across eight MuJoCo and Procgen tasks, PDA more closely matches pooled NPG than uniform averaging while retaining favorable compute and memory scaling.

Primary area:
reinforcement learning
Keywords:
Natural Policy Gradient, Reinforcement Learning, Distributed Optimization

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_rGRwOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes a distributed method for natural policy gradient called Poissonized Determinantal Averaging (PDA) in order to reduce the bias arising from averaging locally computed NPG. In the setting with N number of workers and local batch size of B, the paper shows that uniform averaging retains an O(1/B) bias, while the proposed method PDA matches the leading-order bias of non-distributed NPG, which is O(1/NB). They also show the consistency of the proposed method as N increases. They also evaluate their method on eight MuJoCo and Procgen benchmarks and show that their method outperforms uniform averaging along with less computational complexity.

Critical strengths

Well-motivated problem: The paper studies an important issue arising in distributed NPG: the increased bias that results from averaging locally computed directions due to the nonlinearity of Fisher matrix inversion. The paper proposes a distributed method that achieves the leading-order bias of non-distributed NPG while at the same time it maintains low communication costs and low per-worker memory.

Theoretical and empirical validation: The paper mathematically analyzes the bias-reduction property of the proposed PDA method. Furthermore, it shows the consistency of the proposed method as the number of workers increases. Moreover, it provides empirically evaluates the proposed method across eight RL tasks which demonstrate improvements over existing methods.

Critical weaknesses

Limited theoretical novelty: The paper's method is heavily based on the following two papers: 1) Dereziński and Mahoney, 2019 2) Dereziński et al., 2020. Dereziński and Mahoney (2019) in the setting of distributed optimization, proposed a determinantal averaging method in order to reduce the bias arising from the inversion of locally estimated matrices. Dereziński et al. (2020) by using a Poisson sampling method developed determinant-preserving identities. Authors only combine these results and apply them to natural policy gradients.

Furthermore, Theorem 5.4 is based on the asymptoric setting where B goes to infinity and d is fixed. In the experiments, the paper uses approximately d=938,719 (Page 9 Figure 4) and B=512. Here, the number of parameters is much larger than the local batch size. This could be problematic in practice, since the constant in O_N(B^{-2}) in Theorem 5.4 might depend on d.

Questions for authors

How does the determinant-weighted expectation identities in Prop B.4 differ from the results in Dereziński and Mahoney (2019) and Dereziński et al. (2020)? Beyond just applying the results of these two papers to NPG, what are the novelties of this paper?

2 comments
AuthorsOpenReview ↗

Response to Reviewer rGRw Comments

We sincerely thank the reviewer for their detailed feedback on our paper. We have revised the draft accordingly, with changes highlighted in blue. We added three new appendix sections: the bias-variance trade-off of PDA (Appendix J), the same-batch distance between PDA and the pooled estimator (Appendix K), and the accuracy of the leading-order bias at the experimental scale (Appendix L). Below, we address the weaknesses and questions raised in the review.

Weakness 1 and Question 1

Please see our general response on novelty for the full answer. In brief:

  • How Proposition B.4 differs. The reviewer is right that it does not differ in substance. It can indeed be derived from DLM20's identities for jointly sampled pairs. We now attribute it accordingly, together with Lemma B.1 to Corollary B.3 and the consistency result Corollary 5.5 in the revised draft.
  • Beyond applying the two papers. We agree that PDA combines DM19's aggregation with DLM20's sampling model, but beyond them, we still make contributions in three aspects. Methodologically, making this combination valid and practical for on-policy NPG requires Poisson collection in place of standard fixed-size minibatches, which break exact centering (Appendix F.1), and computing the weights in sample space and in log space, since at 10510^5 to 10610^6 parameters they cannot be computed in parameter space. Theoretically, neither paper compares a distributed estimator with the pooled estimator at a finite number of workers. Our bias analysis identifies the local bias coefficient, including a Fisher-gradient coupling component not covered by either paper, and shows that PDA matches the pooled estimator at every fixed NN, whereas uniform averaging does not. Empirically, this is, to our knowledge, the first evaluation of determinantal averaging with neural-network models and in reinforcement learning.

DM19: M. Dereziński and M. W. Mahoney. Distributed estimation of the inverse Hessian by determinantal averaging. NeurIPS 2019. DLM20: M. Dereziński, F. T. Liang, and M. W. Mahoney. Exact expressions for double descent and implicit regularization via surrogate random design. NeurIPS 2020.

Weakness 2

It is true that Theorem 5.4 is an expansion as B→∞B \to \infty at fixed dd, and the constant in its remainder may depend on dd and λ\lambda. Theorem 5.4 therefore serves as an analytical tool characterizing the mechanism and the limiting behaviour of PDA's bias, rather than a quantitative description at a given finite BB. To examine how accurately the leading terms describe the actual biases at our experimental scale, we have added Appendix L in the revised draft.

Setup. At the StarPilot checkpoint of Figure 3 (d≈9.4×105d \approx 9.4\times10^5, λ=0.5\lambda = 0.5), local batches are drawn from a fixed reference population of 12,800 transitions, so that the population direction p\mathbf{p} and the leading coefficient c\mathbf{c} can be computed exactly in sample space. We then measure the share of PDA's squared bias explained by the leading term,

S(N,B)=1−∥Ep^PDA−p−c/(NB)∥2∥Ep^PDA−p∥2,S(N,B) = 1 - \frac{\lVert\mathbb{E}\hat{\mathbf{p}}_{\mathrm{PDA}} - \mathbf{p} - \mathbf{c}/(NB)\rVert^2}{\lVert\mathbb{E}\hat{\mathbf{p}}_{\mathrm{PDA}} - \mathbf{p}\rVert^2}, estimated by cross-fitting to remove the Monte Carlo inflation (Figure 11).

Results. For a single worker at B=512B = 512, c/B\mathbf{c}/B accounts for about 90% of the squared bias, so the local bias, and hence the bias floor of uniform averaging (Corollary 5.3), is well described at this scale. However, for larger NN, the share decreases to roughly 40-45% at N=8N = 8 and 1616, and stays around this level for B∈[32,512]B \in [32, 512] at N=8N = 8. Higher-order terms are therefore comparable to the leading term for N≥8N \ge 8 at these batch sizes.

Nevertheless, the qualitative predictions of the analysis hold in this setting. First, PDA's bias decreases with both NN and BB, whereas uniform averaging's levels off as NN grows (Figure 3). Second, on the same batches, the systematic gap between PDA and the pooled estimator is much smaller than uniform averaging's and becomes negligible as NN grows (see Appendix K.2 for more details), so the conclusion of Theorem 5.4 that PDA's expected update matches the pooled estimator's holds even though the leading term alone does not describe PDA's bias accurately. Third, the correction points in a direction that improves the return, as the first-order return effect of PDA over uniform averaging is positive at every N>1N > 1 and BB tested (see Appendix J.2 for details).

In summary, Theorem 5.4 characterizes why determinant weighting removes the leading-order bias that Uniform Averaging cannot, and which target PDA approaches. At our batch sizes, it does not quantitatively describe the bias for N≥8N \ge 8, while its qualitative predictions and its conclusion about matching the pooled estimator in expectation hold. We have added this into the limitations in Section 7.

Dear Reviewer rGRw,

We hope you are doing well.

As the discussion period approaches the end, we would like to kindly follow up on our response to your questions. We would be grateful to know if it addresses your concerns and if there are remaining questions, we are happy to clarify.

Thank you very much for your time.

Reviewer_G5LyOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Poissonized Determinantal Averaging (PDA) for distributed Natural Policy Gradients (NPG), aiming to reduce the finite-sample bias caused by local Fisher inversion and Fisher–gradient coupling. By combining Poissonized sampling with determinant-weighted aggregation, the method approximates pooled NPG while requiring only vector-level communication. The authors establish leading-order bias matching with pooled NPG and many-worker consistency. Experiments on eight MuJoCo and Procgen tasks demonstrate improvements over uniform averaging and FedNPG-ADMM.

Critical strengths

The paper addresses a meaningful challenge in distributed NPG, where averaging local natural-gradient directions fails to recover the pooled estimator. The finite-worker bias analysis provides a useful theoretical characterization of the proposed method.

The experiments cover eight reinforcement learning tasks and include bias–variance analysis, ablation studies, and computational measurements. The reported results show consistent improvements over the considered distributed baselines.

Critical weaknesses

The methodological novelty appears limited relative to existing determinantal averaging literature. The proposed method largely builds on the determinant-weighted aggregation of Dereziński and Mahoney (2019) and the Poisson determinant-preserving framework of Dereziński et al. (2020). In particular, the shared-sample identity can be derived from existing jointly sampled-pair results, leaving the finite-worker leading-bias analysis as the principal additional theoretical contribution.

The experimental results do not sufficiently establish that the performance improvements arise from the proposed bias correction. PDA exhibits higher estimator variance, while the main training experiments use different sampling schemes across methods. Without a Poissonized Uniform Averaging training baseline, it remains unclear whether the improvements primarily result from determinant weighting, Poissonization, or the additional stochasticity introduced by their combination.

Questions for authors

Could the authors clarify the main technical novelty beyond the existing determinantal averaging and Poisson random-design results, particularly regarding Proposition B.4 and Theorem 5.4?

Could the authors provide a training comparison with Poissonized Uniform Averaging under identical sampling budgets and optimization settings to isolate the contribution of determinant weighting?

Given that PDA exhibits higher estimator variance, could the authors further explain why its bias reduction leads to better training performance despite the unfavorable bias–variance tradeoff observed in Figure 3?

3 comments
AuthorsOpenReview ↗

Response to Reviewer G5Ly Comments

We sincerely thank the reviewer for their detailed feedback on our paper. We have revised the draft accordingly, with changes highlighted in blue. We added three new appendix sections: the bias-variance trade-off of PDA (Appendix J), the same-batch distance between PDA and the pooled estimator (Appendix K), and the accuracy of the leading-order bias at the experimental scale (Appendix L). Below, we address the weaknesses and questions raised in the review.

Weakness 1 and Question 1

Please see our general response on novelty for the full answer. In brief:

  • Proposition B.4. As the reviewer notes, the shared-sample identity can be derived from DLM20's jointly sampled-pair results. We have now attributed it accordingly in the revised draft, in Sections 2 and 5, and in Appendix B, and we keep our Poisson-Mecke proof only as an alternative derivation.
  • Theorem 5.4. The exact centering follows from the prior identities, and it yields the consistency of PDA as N→∞N\to\infty (Corollary 5.5). However, it does not by itself determine PDA's bias at a finite number of workers. Theorem 5.4 establishes that, for every fixed NN, PDA's leading bias is c/(NB)\mathbf{c}/(NB), matching the pooled estimator, whereas uniform averaging retains the full local bias. Together with the identification of the local coefficient c\mathbf{c}, including its Fisher-gradient coupling component (Proposition 5.1), this finite-NN comparison is our main theoretical contribution. Additionally in the revised draft, we now also examine at the experimental scale how accurately the leading term describes the bias (Appendix L).
  • Method. Beyond the existing results from prior works, PDA makes determinantal averaging valid and practical for on-policy NPG with neural-network policies, through sample-space curvature estimation, sample-space log-domain weights, same-sample local directions, and Poisson collection (Appendix F.1).

DLM20: M. Dereziński, F. T. Liang, and M. W. Mahoney. Exact expressions for double descent and implicit regularization via surrogate random design. NeurIPS 2020.

Weakness 2 and Question 2

In Figure 1, uniform averaging indeed uses the fixed-batch sampling scheme, which is the conventional implementation. We agree that this does not rule out the sampling scheme as a potential reason for PDA's improvement over uniform averaging. We now added the full ablation of the sampling scheme (Poissonized or fixed-batch) and the aggregation rule (uniform or determinant weighting) in Appendix I.1, Figure 5 of the revised draft.

The results separate the three factors raised by the reviewer. First, Poissonized uniform averaging performs worse than or comparably to fixed-batch uniform averaging in 7 out of 8 tasks, the exception being HumanoidStandup. This is consistent with our analysis, that Poissonization alone does not reduce uniform averaging's bias as NN grows while it adds variance. The additional stochasticity introduced by Poissonization is therefore not by itself a source of improvement. Second, under the same sampling scheme, determinant weighting improves on uniform averaging. In particular, PDA outperforms Poissonized uniform averaging in all 8 tasks. Since the two differ only in the aggregation weights, this isolates the effect of determinant weighting. Together, Poissonization harms uniform averaging but, combined with determinant weighting, PDA performs better than or comparably to fixed-batch DA in all 8 tasks, with the clearest gains in HumanoidStandup, BossFight and StarPilot.

(to be continued in part 2)

AuthorsOpenReview ↗

Response to Reviewer G5Ly Comments (Part 2)

Question 3

For the bias-variance trade-off, we emphasize why bias matters more than variance for the training performance, rather than why variance matters less. We added Appendix J for this analysis in the revised draft.

From the empirical results in Section 6, we observed that uniform averaging has lower variance but higher bias than PDA (Figure 3), yet PDA consistently outperforms it in training (Figure 1). Another comparison points the same way. Since E[p^avg]=E[p^i]\mathbb{E}[\hat{\mathbf{p}}_{\mathrm{avg}}] = \mathbb{E}[\hat{\mathbf{p}}_i] for any i.i.d. local estimators, uniform averaging reduces the variance of a single worker roughly NN-fold without reducing its bias, yet it improves on Single NPG, whose bias is of the same order 1/B1/B, in only a few tasks. In other words, reducing variance at fixed bias yields little, whereas reducing bias yields consistent gains.

To explain this observation, we investigate the interaction between the bias and the return. Expanding the expected return of an update θ+αp^\boldsymbol{\theta} + \alpha\hat{\mathbf{p}} around the population update θ+αp\boldsymbol{\theta} + \alpha\mathbf{p}, the first-order term is linear in p^\hat{\mathbf{p}} and evaluated at a deterministic point, so zero-mean fluctuations cancel in it and only the bias remains. The variance enters only through the curvature, at order α2\alpha^2. Making this rigorous for PDA and uniform averaging computed from the same batches, with Theorem 5.4 and Corollary 5.3 we show (see details in Appendix J.2)

lim⁡B→∞BαE[J(θ+αp^PDA)−J(θ+αp^avg)]=−N−1N∇J(θ+αp)⊤c.\lim_{B\to\infty}\frac{B}{\alpha}\mathbb{E}\big[J(\boldsymbol{\theta} + \alpha\hat{\mathbf{p}}_{\mathrm{PDA}}) - J(\boldsymbol{\theta} + \alpha\hat{\mathbf{p}}_{\mathrm{avg}})\big] = -\frac{N-1}{N}\nabla J(\boldsymbol{\theta} + \alpha\mathbf{p})^\top\mathbf{c} .

At large BB, the effect of PDA's higher variance is of higher order, so only the bias remains on the right-hand side. Consequently, PDA has the higher expected one-step return whenever uniform averaging's bias opposes the ascent direction, i.e., ∇J⊤c<0\nabla J^\top\mathbf{c} < 0. When the bias happens to be aligned with ascent, uniform averaging can have the higher one-step return. Since PDA's leading bias c/(NB)\mathbf{c}/(NB) has the same direction as uniform averaging's c/B\mathbf{c}/B but is NN times smaller, PDA attenuates the effect of the bias in either direction, following the intended NPG direction more faithfully.

To verify whether uniform averaging's bias opposes ascent and whether PDA improves the return, we conducted an empirical analysis in the same setting as Figure 3. The estimated ∇J(θ)⊤c\nabla J(\boldsymbol{\theta})^\top\mathbf{c} is negative (≈−0.063\approx -0.063, 95% CI [−0.075,−0.052][-0.075, -0.052]), so the leading-order prediction of the return effect is positive. Using ∇J(θ)\nabla J(\boldsymbol{\theta}) as the first-order approximation of ∇J(θ+αp)\nabla J(\boldsymbol{\theta} + \alpha\mathbf{p}), the measured first-order return effect ∇J(θ)⊤E[p^PDA−p^avg]\nabla J(\boldsymbol{\theta})^\top\mathbb{E}[\hat{\mathbf{p}}_{\mathrm{PDA}} - \hat{\mathbf{p}}_{\mathrm{avg}}] is positive at every N>1N > 1 and BB tested (Appendix J.2, Figure 9). Relative to its leading-order prediction, it is smaller at small NN and small BB, and increases towards the prediction as either grows: at B=512B = 512 it reaches about 60% of the prediction at N=8N = 8, 80% at N=16N = 16, and nearly 100% at N=210N = 2^{10}.

In summary, to leading order the return difference between PDA and uniform averaging is determined by their difference in bias rather than in variance, which provides a mechanism by which PDA's lower bias can outweigh its higher variance.

Thank you for the detailed response and the additional theoretical analysis and experimental results. The rebuttal has satisfactorily addressed my main concerns and strengthened the paper. I appreciate the authors' efforts and will increase my rating accordingly.

Reviewer_vnUmOpenReview ↗
Rating
3
Confidence
2
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

The paper analyses whether a distributed approach based on averaging local empirical natural policy gradients can recover the expected behaviour of the pooled-batch estimator. They propose sampling a local batch size Ki∼Poisson(B)K_i\sim Poisson(B), where BB is the expected batch size, and define the worker-wise empirical NPG direction using Poissonized empirical Fisher and policy gradient estimates formed from KiK_i samples and normalized by BB. The distributed NPG direction is formulated using determinantal weights, and the method is called Poissonized Determinantal Averaging (PDA). PDA aims to obtain the statistical benefit of computing NPG on a large pooled batch while allowing each worker to solve a smaller local problem. The paper shows that, for a fixed number of workers and as BB grows, PDA matches the leading-order bias of pooled Poissonized NPG, whereas uniform averaging retains the bias of a single local empirical NPG estimator. For fixed BB, the PDA also converges to the population-damped NPG direction as the number of workers grows. Experimental results show that PDA generally approaches the training performance of pooled NPG, while exhibiting higher estimator variance than uniform averaging. It also reduces per-worker memory requirements by keeping the Woodbury sample-space solves local.

Critical strengths

Theorem 5.4 and Corollary 5.3 together show the impact of the aggregation strategy with Poissonized sampling: determinantal aggregation matches the leading-order bias of pooled NPG, whereas uniform averaging retains the bias of a single local estimator. Figure 3 further empirically investigates the impact of the aggregation strategy. PDA results in lower relative bias across both sets of experiments in Figure 3 compared to uniform averaging, but it results in a higher variance. PDA approaches pooled NPG performance while reducing per-worker memory requirements by communicating only one parameter-sized direction and one scalar per worker.

Critical weaknesses
  1. The research question of approximating pooled NPG through distributed local aggregation appears narrow, and its significance could be motivated more convincingly. In particular, the practical implications of matching PDA’s leading-order bias in Theorem 5.4 to the pooled-estimator bias characterized in Corollary 5.2 could be explained more clearly.
  2. Although the paper is polished, it provides insufficient background for readers less familiar with the area. The introduction moves quickly to the technical issues, and the paper offers limited intuition about the roles of identities such as Woodbury and Poisson–Mecke in the proposed method. Explaining why these identities are relevant and how they support the approach would improve accessibility.
  3. The appendix proofs are highly compressed. Several intermediate calculations, as well as the connections between the lemmas and the main results, could be explained more explicitly. Additional explanation would make the arguments easier to follow and verify.
  4. The comparison with Single NPG requires careful interpretation because the methods use different sample budgets. Single NPG uses an expected BB samples per update, whereas PDA and pooled NPG use an expected total of NBNB samples. Improvements over Single NPG alone therefore do not establish improved sample efficiency. Although pooled NPG provides a centralised baseline with the same expected sample budget as PDA, reporting training performance against total environment interactions, in addition to rollout count, would clarify the comparison.
Questions for authors

Theorem 5.4 establishes leading-order bias matches for pooled NGD and PDA. Can the authors provide a bound on E[∥p^PDA,N−p^pool∥22]\mathbb E\left[\left\|\hat p_{\mathrm{PDA},N}-\hat p_{\mathrm{pool}}\right\|_2^2\right] when both are computed from the same samples? This bound would more accurately clarify how PDA approximates the pooled update at each iteration. The higher variance of Poisson/DA in Figure 3 is potentially attributed to determinantal weights; the same is responsible for the lower relative bias. Can the authors quantify how variability in these weights affects the variance?

3 comments
AuthorsOpenReview ↗

Response to Reviewer vnUm Comments

We sincerely thank the reviewer for their detailed feedback on our paper. We have revised the draft accordingly, with changes highlighted in blue. We added three new appendix sections: the bias-variance trade-off of PDA (Appendix J), the same-batch distance between PDA and the pooled estimator (Appendix K), and the accuracy of the leading-order bias at the experimental scale (Appendix L). Below, we address the weaknesses and questions raised in the review.

Weakness 1

Uniform averaging leaves the bias at the single-worker level c/B\mathbf{c}/B for every NN (Corollary 5.3), whereas the pooled estimator's bias decreases as c/(NB)\mathbf{c}/(NB) (Corollary 5.2). Therefore, data parallelism aims to match an update computed from the pooled NBNB samples. Theorem 5.4 shows that PDA's leading bias matches the pooled estimator's, so additional workers act like a larger batch in expectation.

This matters for optimization because unlike zero-mean noise, the bias does not cancel in the first-order effect of an update on the return, and it systematically deflects the updates from the NPG direction (Appendix J). Empirically, uniform averaging improves on Single NPG in only a few tasks despite its lower variance, whereas PDA yields consistent gains (Figure 1), and on the same batches, PDA's expected update closely matches the pooled estimator's (Appendix K.2). We have added this motivation to the introduction and a remark after the main theorem in the revised draft.

Weakness 2

We agree that the introduction of the original draft moves to fast from background to technical issues. In the revised draft, we have moved the identities that serves mainly as proof mechanics to the appendix, such as the Poisson-Mecke identity, and only keep the most direct identities in the introduction, such as the Woodbury identity, for better readability.

Here is the intuition of the main identities mentioned in the paper:

  • Woodbury identity. Since the empirical Fisher is a sum of KiK_i rank-one terms, by Woodbury identity, the damped NPG direction can be obtained by solving a Ki×KiK_i\times K_i system in sample space instead of a d×dd\times d system in parameter space. By Sylvester's determinant identity, the same factorization also yields the worker's determinant weight, so neither the Fisher nor its determinant is ever formed in parameter space. The intuition has been added to the end of Introduction, and the details are provided in Section 4.
  • Poissonization. Its role is to make the determinant-weighted local directions exactly centered, E[Di(p^i−p)]=0\mathbb{E}[D_i(\hat{\mathbf{p}}_i - \mathbf{p})] = 0, which is the basis of the bias analysis. Intuitively, each order-kk term of the determinant expansion contains the normalization B−kB^{-k} together with the factorial moment E[(Ki)k]\mathbb{E}[(K_i)_k], which equals BkB^k for Ki∼Poisson(B)K_i \sim \mathrm{Poisson}(B), so the two cancel. With fixed-size batches, E[(Ki)k]=(B)k≠Bk\mathbb{E}[(K_i)_k] = (B)_k \ne B^k for k≥2k \ge 2, and exact centering is lost. The full proof is in Appendix B.
  • Poisson-Mecke formula. It is only a tool in our proof of the shared-sample identity (Proposition B.4), which can also be derived from the results of Dereziński et al. (2020b). We have therefore moved it to the appendix, where we keep it as an alternative derivation, so that it does not distract from the main argument.

Weakness 3

We thank the reviewer for this comment. We agree that several proofs are compressed. Given the limited time of the rebuttal period, we will make the proofs more detailed in the camera-ready version.

Weakness 4

Indeed, Single NPG uses an expected BB samples per update, whereas the distributed estimators and the pooled estimator use an expected NBNB samples. In this work, sample efficiency is not the main concern. Since sampling happens in parallel across workers, using around NN times more samples does not cost around NN times more wall-clock time, but a wall-clock time similar to Single NPG's (plus the communication overhead). As a result, the per-rollout, or equivalently per-update, plots of Figure 1 compare the methods at a similar wall-clock cost. The purpose of Single NPG is a minimum performance reference for the distributed estimators, i.e., a distributed estimator should perform at least as well as Single NPG to be effective, as stated at the beginning of Section 6.

Nevertheless, we provide a separate figure that replots the results of Figure 1 against the number of environment steps, shown in Figure 7, Appendix I.3. In terms of environment steps, Single NPG is indeed more sample-efficient. However, this comparison hides the frequency of updates. For the same number of environment steps, Single NPG performs NN times more updates than the distributed estimators, which contributes to this pattern.

(to be continued in part 2)

AuthorsOpenReview ↗

Response to Reviewer vnUm Comments (Part 2)

Question Part 1: the expected squared gap between PDA and the pooled estimator

Theorem 5.4 implies that, in expectation, PDA matches the pooled estimator to leading order as BB grows, but this does not necessarily mean that it has a small mean squared gap to the pooled estimator computed from the same samples. To address this, we added Appendix K in the revised draft, which examines the gap between PDA and the pooled estimator both on a single batch, giving the requested bound, and in expectation. The findings are summarized below.

Let q\mathbf{q} be any aggregated direction computed from the same NN local batches as the pooled estimator, such as p^PDA\hat{\mathbf{p}}_{\mathrm{PDA}}. Define its pooled residual rq:=(λI+Fˉ)q−gˉ\mathbf{r}_{\mathbf{q}} := (\lambda\mathbf{I} + \bar{\mathbf{F}})\mathbf{q} - \bar{\mathbf{g}}, where Fˉ=1N∑iF^i\bar{\mathbf{F}} = \frac1N\sum_i \hat{\mathbf{F}}_i and gˉ=1N∑ig^i\bar{\mathbf{g}} = \frac1N\sum_i \hat{\mathbf{g}}_i are the pooled Fisher and gradient. The residual vanishes exactly at q=p^pool\mathbf{q} = \hat{\mathbf{p}}_{\mathrm{pool}}. Using the local systems (F^i+λI)p^i=g^i(\hat{\mathbf{F}}_i + \lambda\mathbf{I})\hat{\mathbf{p}}_i = \hat{\mathbf{g}}_i, the pooled residual is the average of the local residuals,

rq=1N∑i=1N(F^i+λI)(q−p^i),\mathbf{r}_{\mathbf{q}} = \frac1N\sum_{i=1}^N(\hat{\mathbf{F}}_i + \lambda\mathbf{I})(\mathbf{q} - \hat{\mathbf{p}}_i),

and since the eigenvalues of λI+Fˉ\lambda\mathbf{I} + \bar{\mathbf{F}} lie in [λ,λ+∥Fˉ∥][\lambda, \lambda + \lVert\bar{\mathbf{F}}\rVert], on every batch

\qquad\text{hence}\qquad \mathbb{E}\lVert\mathbf{q} - \hat{\mathbf{p}}_{\mathrm{pool}}\rVert^2 \le \frac{1}{\lambda^2}\mathbb{E}\lVert\mathbf{r}_{\mathbf{q}}\rVert^2 .$$ The bound holds for any $d$, $N$ and $B$. However, since the bound holds for any aggregated direction, it does not by itself show whether PDA is closer to the pooled estimator than uniform averaging is. We therefore measure the gap empirically in the setting of Figure 3. We additionally measure the systematic gap $\lVert\mathbb{E}[\mathbf{q} - \hat{\mathbf{p}}_{\mathrm{pool}}]\rVert^2$, which connects to the expected squared gap as follows, $$\mathbb{E}\lVert\mathbf{q} - \hat{\mathbf{p}}_{\mathrm{pool}}\rVert^2 = \lVert\mathbb{E}[\mathbf{q} - \hat{\mathbf{p}}_{\mathrm{pool}}]\rVert^2 + \mathbb{E}\big\lVert(\mathbf{q} - \hat{\mathbf{p}}_{\mathrm{pool}}) - \mathbb{E}[\mathbf{q} - \hat{\mathbf{p}}_{\mathrm{pool}}]\big\rVert^2 .$$ For the systematic part, Theorem 5.4 gives $\mathbb{E}[\hat{\mathbf{p}}_{\mathrm{PDA}}] - \mathbb{E}[\hat{\mathbf{p}}_{\mathrm{pool}}] = O_N(B^{-2})$, whereas by Corollaries 5.2 and 5.3, $\mathbb{E}[\hat{\mathbf{p}}_{\mathrm{avg}}] - \mathbb{E}[\hat{\mathbf{p}}_{\mathrm{pool}}] = (1 - \frac1N)\mathbf{c}/B + O(B^{-2})$, which does not vanish as $N$ grows. In the setting of Figure 3 ($B = 512$), we compute the pooled estimator exactly on the same batches as the distributed estimators, and estimate the systematic part by cross-fitting to remove the Monte Carlo inflation (Appendix K.2, Figure 10). PDA's systematic gap is smaller than uniform averaging's at every $N \ge 2$ and becomes negligible as $N$ grows, whereas uniform averaging's grows and then levels off, consistent with $(1 - \frac1N)\mathbf{c}/B$. This requires both determinant weighting and Poissonization: with fixed-size batches, determinant weighting leaves a systematic gap that also levels off, only slightly below uniform averaging's. On a single batch, however, PDA deviates more from the pooled estimator than uniform averaging does, because of its larger fluctuation, although this gap also decreases with $N$. This is consistent with our variance analysis (see the newly added Appendix J in the revised draft), which attributes PDA's additional fluctuation mainly to the dispersion of its weights. In summary, PDA closely approximates the pooled update in expectation, removing the systematic gap that uniform averaging retains. However, this matching does not occur on every single batch, where its gap is dominated by the fluctuation from its weight dispersion. (to be continued in part 3)
AuthorsOpenReview ↗

Response to Reviewer vnUm Comments (Part 3)

Question part 2: The source of PDA's higher variance

We added Appendix J.1 in the revised draft to quantify how the variability of the weights produces PDA's higher variance than uniform averaging, and show that the extra variance and the bias correction come from different properties of the weights. The findings are summarized below.

We show the variance difference between PDA and uniform averaging by comparing them to a permuted estimator, in which the PDA weights are randomly reassigned to the local directions instead of each staying with its own worker. Let wi=Di/∑jDjw_i = D_i/\sum_j D_j be the PDA weights and σ\sigma a uniformly random permutation of the NN workers, independent of the data, and define p^perm=∑iwσ(i)p^i\hat{\mathbf{p}}_{\mathrm{perm}} = \sum_i w_{\sigma(i)}\hat{\mathbf{p}}_i. This estimator has exactly the same weights as PDA, and hence the same weight variability. However, since each worker receives each weight with probability 1/N1/N, it has the same expected value as uniform averaging, E[p^perm]=E[p^avg]\mathbb{E}[\hat{\mathbf{p}}_{\mathrm{perm}}] = \mathbb{E}[\hat{\mathbf{p}}_{\mathrm{avg}}]. Writing Var⁡(x):=E∥x−Ex∥2\operatorname{Var}(\mathbf{x}) := \mathbb{E}\lVert\mathbf{x} - \mathbb{E}\mathbf{x}\rVert^2, the variance gap splits into a weight-dispersion term and a pairing term,

= \big[\operatorname{Var}(\hat{\mathbf{p}}_{\mathrm{perm}}) - \operatorname{Var}(\hat{\mathbf{p}}_{\mathrm{avg}})\big] + \big[\operatorname{Var}(\hat{\mathbf{p}}_{\mathrm{PDA}}) - \operatorname{Var}(\hat{\mathbf{p}}_{\mathrm{perm}})\big],$$ where the first bracket is the weight dispersion and the second is the pairing. Weight dispersion: averaging over random permutations gives the exact identity, for any $N > 1$ and $B$, $$\operatorname{Var}(\hat{\mathbf{p}}_{\mathrm{perm}}) - \operatorname{Var}(\hat{\mathbf{p}}_{\mathrm{avg}}) = \mathbb{E}\left[\frac{1}{N-1}\sum_j\Big(w_j - \frac1N\Big)^2 \sum_i \big\lVert\hat{\mathbf{p}}_i - \hat{\mathbf{p}}_{\mathrm{avg}}\big\rVert^2\right] \ge 0 .$$ This nonnegative term directly quantifies the effect of weight variability. It is the product of how unequal the weights are and how much the local directions differ, and it vanishes only if the weights are uniform or all local directions coincide. Pairing: writing PDA as uniform averaging plus a correction, $\hat{\mathbf{p}}_{\mathrm{PDA}} = \hat{\mathbf{p}}_{\mathrm{avg}} + \mathbf{C}$ with $\mathbf{C} = \sum_i (w_i - \frac1N)(\hat{\mathbf{p}}_i - \hat{\mathbf{p}}_{\mathrm{avg}})$, and likewise $\hat{\mathbf{p}}_{\mathrm{perm}} = \hat{\mathbf{p}}_{\mathrm{avg}} + \mathbf{C}_\sigma$, $$\operatorname{Var}(\hat{\mathbf{p}}_{\mathrm{PDA}}) - \operatorname{Var}(\hat{\mathbf{p}}_{\mathrm{perm}}) = \big[\operatorname{Var}(\mathbf{C}) - \operatorname{Var}(\mathbf{C}_\sigma)\big] + 2\operatorname{tr}\operatorname{Cov}\big(\hat{\mathbf{p}}_{\mathrm{avg}}, \mathbf{C}\big).$$ This term depends on whether large determinants accompany directions that deviate from the consensus, or directions whose correction cancels the uniform average's own fluctuation, and it can have either sign. We analyzed PDA's variance decomposition in the same setting as Figure 3 ($B = 512$), and the results are shown in Appendix J.1, Figure 8. Weight dispersion accounts for around 90% of the variance gap between PDA and uniform averaging at every $N$, while pairing accounts for the remaining 10% and is positive. As a share of PDA's total variance, the uniform-averaging baseline falls from around 70% at $N = 2$ to around 20% at $N = 2^{10}$, while weight dispersion rises from around 25% to around 75%. Importantly, since $\mathbb{E}[\hat{\mathbf{p}}_{\mathrm{perm}}] = \mathbb{E}[\hat{\mathbf{p}}_{\mathrm{avg}}]$, the bias correction of PDA comes entirely from pairing, i.e., from the correlation between each weight and its own direction, and in this setting pairing contributes only a small part of the extra variance. Most of the extra variance is the generic cost of unequal weights.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General response to the novelty concerns

The novelty concerns relate to two works:

  • DM19: M. Dereziński and M. W. Mahoney. Distributed estimation of the inverse Hessian by determinantal averaging. NeurIPS 2019.
  • DLM20: M. Dereziński, F. T. Liang, and M. W. Mahoney. Exact expressions for double descent and implicit regularization via surrogate random design. NeurIPS 2020.

In short, the determinant identities and the resulting N→∞N\to\infty consistency are due to prior work, which we now fully attribute. Our contributions are a method that makes determinantal averaging valid and practical for data-parallel on-policy NPG with neural-network policies; a bias analysis comparing PDA, uniform averaging, and the pooled estimator at finite NN; and an empirical evaluation at deep-RL scale. The details are below.

What we take from prior work

The identities

E[Di]=D,E[adj⁡(F^i+λI)]=adj⁡(F+λI)\mathbb{E}[D_i] = D, \qquad \mathbb{E}\big[\operatorname{adj}(\hat{\mathbf{F}}_i + \lambda\mathbf{I})\big] = \operatorname{adj}(\mathbf{F} + \lambda\mathbf{I})

(Lemma B.1 to Corollary B.3) specialize DLM20, Lemma 5, as cited in our original draft. As Reviewers G5Ly and rGRw note, and as we have verified, the shared-sample identity E[Dip^i]=Dp\mathbb{E}[D_i\hat{\mathbf{p}}_i] = D\mathbf{p} (Proposition B.4) can also be derived from DLM20's results for jointly sampled pairs. This answers Reviewer rGRw's Q1: Proposition B.4 does not differ in substance from these results. We have revised the paper to attribute it, in Sections 2 and 5, and in Appendix B, and keep our Poisson-Mecke proof only as an alternative derivation. Together, these identities give exact centering, E[Di(p^i−p)]=0\mathbb{E}[D_i(\hat{\mathbf{p}}_i - \mathbf{p})] = 0, and hence the consistency of PDA as N→∞N\to\infty for any BB (Corollary 5.5), as in DM19, Corollary 3. We credit this result to them, in Section 5.

How our setting differs

DM19 introduces determinantal averaging for distributed Newton's methods, to correct the inversion bias when aggregating local Hessian inverses applied to the full-batch gradient, where the local Hessians are formed by Bernoulli sampling from a fixed finite dataset. Its main results related to our work are the exact identity between the determinantally averaged Hessian inverse and the population Hessian inverse in expectation (Theorem 1), the consistency of the determinantally averaged Newton step as the number of workers grows (Corollary 3), and a finite-sample high-probability bound under a condition on the expected local batch size (Corollary 4). Its experiments concern linear regression on LIBSVM datasets, and its conclusion (NeurIPS version, Section 4) leaves open whether determinantal averaging works in more practical settings, such as when both the Hessian and the gradient are local. DLM20 establishes determinant-preserving identities for jointly sampled pairs (Lemma 5) to study surrogate random designs. It does not study averaging of local estimators.

Our work focuses on data-parallel distributed NPG for deep RL, which differs from both setups in several aspects. First, there is no fixed dataset in on-policy RL. The samples come from a policy-induced distribution, and the population gradient is generally infeasible to obtain. Second, standard implementations estimate the Fisher and the policy gradient from the same samples, which induces an additional coupling component in the bias (Equation 14). DLM20's identities hold for jointly sampled pairs, so they capture this coupling in determinant-weighted expectations, but neither DLM20 nor DM19 analyzes this component. Third, the scale differs significantly. We consider neural-network policies with about 10510^5 to 10610^6 parameters, at which the determinant weights can no longer be computed in parameter space as in DM19. We have clarified this distinction in Section2 of the revised draft.

In this setting, the practical benefit is substantial. In its sample-space form, pooled NPG over NBNB samples requires O(NBd)\mathcal{O}(NBd) memory on a single device, which quickly becomes infeasible for neural-network policies. PDA keeps the per-device memory at O(Bd)\mathcal{O}(Bd), remains roughly the single-worker per-device compute (Figure 4), and communicates only one dd-vector and one scalar per worker, while it approximately matches the training performance of pooled NPG (Figure 1), where uniform averaging fails to do so.

(to be continued in part 2)

AuthorsOpenReview ↗

General response to the novelty concerns (Part 2)

Our contributions

Method. Beyond combining the determinant-weighted aggregation of DM19 with the Poisson sampling model of DLM20, PDA makes it valid and practical for data-parallel on-policy NPG.

  • Local same-sample NPG. Each worker locally estimates the NPG direction in sample space with Woodbury formulation, using a gradient estimated from the same samples as its Fisher as in standard implementations. The directions are aggregated directly, with no separate gradient aggregation step, so each worker communicates one dd-vector and one scalar weight per update.
  • Sample-space determinantal weights. In the Woodbury regime, Sylvester's identity allows computing the determinantal weights in sample space (Equation 8), so each weight is a by-product of the Ki×KiK_i\times K_i factorization used to solve the sample-space NPG system, and the explicit Fisher is never formed. Computing the weights in log space is necessary for numerical stability (Equation 9).
  • Poisson sampling in on-policy collection. Following DLM20's sampling model and, as in DM19, normalizing by the expected rather than the realized sample size, we draw Poisson minibatch counts during on-policy data collection (Appendix H). Standard implementations, which use fixed-size minibatches and normalize by the realized minibatch size, break exact centering (Appendix F.1). Empirically, Poissonization improves determinantal averaging, whereas it does not help uniform averaging (Figure 3, Appendix I.1).

Theory. DM19's results concern the estimation error relative to the exact Newton step. Our central question is how, at a finite number of workers NN, PDA's bias compares with that of the pooled estimator, the centralized reference computed from the same expected NBNB samples. Neither DM19 nor DLM20 addresses this. Our bias analysis (Section 5) is asymptotic in BB:

  • Local bias (Proposition 5.1). The leading bias of Poissonized empirical NPG is c/B\mathbf{c}/B, consisting of an inversion component and a Fisher-gradient coupling component (Equation 14). The latter is not covered by DM19 or DLM20.
  • Pooled bias (Corollary 5.2). By Poisson superposition, the pooled estimator is distributed exactly as a single Poissonized estimator of intensity NBNB, so its leading bias is c/(NB)\mathbf{c}/(NB). This is the target to match.
  • Uniform averaging bias (Corollary 5.3). Uniform averaging has exactly the same expectation as a local estimator, so its bias stays at c/B\mathbf{c}/B for every NN.
  • PDA bias (Theorem 5.4). For every fixed NN, PDA's leading bias is c/(NB)\mathbf{c}/(NB), matching the pooled estimator, whereas uniform averaging retains the full local bias c/B\mathbf{c}/B. Exact centering yields consistency as N→∞N\to\infty (Corollary 5.5), but does not by itself determine PDA's bias at a finite NN.

These results identify the leading bias coefficients. Their remainder constants may depend on dd and λ\lambda, and we do not quantify the batch size beyond which the expansion is accurate. We therefore examine PDA's bias directly in the d≫Bd \gg B regime (Appendix L): the leading term accounts for most of the local bias at B=512B = 512 but for roughly half of PDA's bias at N≥8N \ge 8, while the qualitative predictions hold, including that PDA's expected update closely matches the pooled estimator's computed from the same samples (Appendix K.2). We have stated this scope explicitly in the revised draft, Section 7.

Experiments. To our knowledge, this is the first evaluation of determinantal averaging with neural-network models and in reinforcement learning. With policies of about 7×1047\times10^4 (MuJoCo) and 9×1059\times10^5 (Procgen) parameters and N=8N = 8 workers, PDA most closely matches pooled NPG among the distributed methods on four MuJoCo and four Procgen tasks (Figure 1), improves further as workers are added (Figure 2), and retains roughly single-worker per-device cost (Figure 4, Appendix I.2). An ablation over the sampling scheme and the aggregation rule shows that PDA outperforms Poissonized uniform averaging in all eight tasks (Appendix I.1). In the estimator study at d≈9.4×105≫Bd \approx 9.4\times10^5 \gg B (Figure 3), PDA's bias decreases with BB at fixed NN and keeps decreasing with NN at fixed BB, where uniform averaging plateaus. On the same batches, PDA's systematic gap to the pooled estimator becomes negligible as NN grows (Appendix K), and the bias it removes opposes the ascent direction, so PDA improves the first-order one-step return over uniform averaging (Appendix J).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.