Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper proposes an algorithm for decentralized bilevel optimization, that converges to $\epsilon$-KKT points at a rate of $\mathcal{O}(1/(n\epsilon^2))$, where $n$ is the number of nodes. This is a linear speedup in $n$ compared to prior work. The algorithm is evaluated empirically on a navigation task and a pursuit-evasion game.
strengths_and_weaknesses: Strengths:
- paper is clear
- inclusion of empirical behavior is nice
- the problem studied is very relevant to current trends in other subfields of ML (e.g. multi-agent RL, multi-task learning)

Weaknesses:
- it is unclear to me in general how much of a difference the linear speed-up w.r.t. $n$ makes. Since this is a main novel contribution, I think it would be nice to have more in-depth discussion (with concrete examples), as well as a discussion of how tight the hidden rate dependencies of the proposed algorithm are. [** post-rebuttal ** : partially addressed: two new experiments added]
questions: - Could you comment more on practical considerations to aid judging the efficiency improvement? [** post-rebuttal ** : partially addressed in rebuttal via new experiments]
- Could you give some more intuition on what leads to higher rewards in existing experiments? [** post-rebuttal ** : addressed]
- It somewhat seems to me that the pursuit experiment shows faster convergence, while the navigation experiment shows convergence to better reward. Is this correct? If so, could you explain more what the intuition is behind the distinction in behavior? [** post-rebuttal ** : addressed]
limitations: - I believe the paper would benefit from more numerical experiments so as to capture wider range of behavior. [** post-rebuttal ** : addressed via two new experiments -- see rebuttal + new version of paper]

- Small comment: formatting of paragraph "Applications of Bilevel Optimization" (lines 28-63) is unpolished in my opinion.  Especially "RL:" after the introductory sentence on 53-55 feels a bit out of place/abrupt, similarly "Meta-learning:" after first sentence in 28-31.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper extends the bilevel optimization to the decentralized setting to include the popular problems in the multi-task learning and multi-agent reinforcement learning. In particular, the upper and lower optimization variable in the bilevel optimization problem need to achieve a consensus currently and each node (agent) can just communicate with its neighbors (w.r.t to the graph). Comparing with previous work with two timescales and two loops, the author derive a single timescale and one loop algorithm inspired by the augmented lagrangian method developed in the single-level optimization (and its decentralized version). Under some standard assumption (generally the assumption in single-level decentralized optimization and centralized bilevel-optimization ), the author provides the theoretical guarantee of the algorithm, in particularly, the convergence to the \epsilon-KKT points.  At last, the authors provide an empirical study on MARL problem including cooperative navigation task and pursuit-evasion game.
strengths_and_weaknesses: Pros:

1. The formulation of the decentralized bilevel optimization problem may cover several interesting problem in machine learning community. I guess this work may provide some insights to the meta-learning and reinforcement learning. 

2. The authors provide a theoretical analysis on the proposed algorithm. 

Cons:
1. I am sorry to say that I do not check every detail of the proof. One of my concern is that the proof technique may just combine the existing results, e.g., the result on single-level decentralized optimization and single-agent bilevel optimization. Can authors elaborate the novelty of their proof? 
2. The empirical result is not that convincing. For instance, SLAM-AC in figure 1 and figure 2 does not outperform the baseline a lot (the shaded areas in some figure are even overlapped. ). In addition, the baseline is not strong enough, although I think it may be OK for a theoretical paper. 

3. g in the assumption is strongly convex. It seems that in the experiment the author use neural networks to approximate the actor and critic (in the appendix).  Does this assumption limit the applicability of the algorithm? 

questions: Please see the comments in Strengths And Weaknesses.
limitations: Yes
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper has studied a generic form of the DBO (Decentralized Bilevel Optimization) problem, which has three major variants (constraints on upper level consensus, lower level consensus and both) that encompass several popular machine learning problems, such as MAML and MARL. For this problem, the paper proposes SLAM (a stochastic linearized augmented Lagrangian method), a single-timescale and single-loop algorithm that can find the ϵ-KKT points at a rate of O(1/(nϵ^2)).
strengths_and_weaknesses: Strength 1. This paper studies an important machine learning problem, whose formulation is generic enough to have MARL and MAML as its special cases.

Strength 2. Theoretically, the major novelty is an augmented-Lagrangian variant. The authors have derived recursion of the successive dual variables to quantify the consensus errors (in terms of primal variables) from both UL and LL optimizations. The proof results are shown in a compact manner, with sufficient explanation, which presents good readability.

Strength 3. On the emparical side, the authors tested the performance of SLAM numerically on a MARL scenario and found that SLAM outperformed the traditional MARL algorithms w.r.t. convergence speed and achievable rewards.

Weakness. The numerical results are gained from toy examples. Thus, for real scenarios, the scalability (in terms of the number of agents, the action space, etc.) of this method is questionable.  
questions: No Question.
limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In the study, the bilevel optimization framework is provided based on the linearized augmented lagrangian method, the detailed algorithms are provided, and the experimental results indicate the effectiveness of the method.
strengths_and_weaknesses: ### Update after Rebuttal

I appreciate the authors' detail replies, and I have become largely persuaded by the authors and have raised my rating from 5 to 6.

Strengths: The theoretical part and the algorithms are good and sound solid.

Weaknesses:
1. In Page 4, line 167 and Page 7, line 253, the writing of the function may be not right, please check them. 
2. In Page 5, line 198, line 199, the coefficient $\alpha$, $\beta$, $\rho$, $\gamma$ for the method's performance may need to be further investigated, ablation experiments may be necessary for the study. 
3. Please explain the meaning of $g_{k}\left(\mathbf{x}^{r}, \mathbf{y}_{k}^{r}\right)$, currently, it's not clear.


questions: 1. In Page 6, Algorithm 1, how do the coefficient factors $\boldsymbol{\lambda}=\omega_{k}$ improve the performance? Could the study provide the analysis?
2. Can the study be extended to some strong baselines, e.g. MACPO and MAPPO-L [Gu, et al., 2021], HATRPO and HAPPO algorithms [Kuba, et al., 2021a], MAT [Wen, et al., 2022] ? More importantly, could the study provide the comparison experiments with HATRPO and HAPPO algorithms [Kuba, et al., 2021a], MAT [Wen, et al., 2022] ?
3. In the experimental section, Why is the performance of parameter sharing algorithms better than that of parameter non sharing? According to the the references [Kuba, et al., 2021a] and [Kuba, et al., 2021b], the the parameter sharing setting could be detrimental to the experimental performance.

[Gu, et al., 2021] Gu, S., Kuba, J. G., Wen, M., Chen, R., Wang, Z., Tian, Z., ... & Yang, Y. (2021). Multi-agent constrained policy optimisation. arXiv preprint arXiv:2110.02793.

[Wen, et al., 2022] Wen, M., Kuba, J. G., Lin, R., Zhang, W., Wen, Y., Wang, J., & Yang, Y. (2022). Multi-Agent Reinforcement Learning is a Sequence Modeling Problem. arXiv preprint arXiv:2205.14953.

[Kuba, et al., 2021a] Kuba, J. G., Chen, R., Wen, M., Wen, Y., Sun, F., Wang, J., & Yang, Y. (2021). Trust region policy optimisation in multi-agent reinforcement learning. arXiv preprint arXiv:2109.11251.

[Kuba, et al., 2021b] Kuba, J. G., Wen, M., Meng, L., Zhang, H., Mguni, D., Wang, J., & Yang, Y. (2021). Settling the variance of multi-agent policy gradients. Advances in Neural Information Processing Systems, 34, 13458-13470.

limitations: The code is not found in the study, if it can be provided to examine the effectiveness of the method, that would be better.
review_title: null

Meta-review: metareview: This paper proposes a new algorithm for distributed bilevel optimization with solid theoretical results and empirical validation in multi-agent RL examples. During the rebuttal/discussion period, authors were able to provide additional experiments and addressed most of reviewers' concerns. All are in favor for acceptance and appreciate the combination of theory and strong experiments.
confidence: Certain
Decision: Accept