- 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
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.
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:
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→∞ at fixed d, and the constant in its remainder may depend on d and λ. 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 B. 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×105, λ=0.5), local batches are drawn from a fixed reference population of 12,800 transitions, so that the population direction p and the leading coefficient 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∥2∥Ep^PDA−p−c/(NB)∥2, estimated by cross-fitting to remove the Monte Carlo inflation (Figure 11).
Results. For a single worker at B=512, 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 N, the share decreases to roughly 40-45% at N=8 and 16, and stays around this level for B∈[32,512] at N=8. Higher-order terms are therefore comparable to the leading term for N≥8 at these batch sizes.
Nevertheless, the qualitative predictions of the analysis hold in this setting. First, PDA's bias decreases with both N and B, whereas uniform averaging's levels off as N 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 N 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>1 and B 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≥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.