A Stochastic Linearized Augmented Lagrangian Method for Decentralized Bilevel Optimization
Authors: Songtao Lu
Siliang Zeng
Xiaodong Cui
Mark S. Squillante
Lior Horesh
Brian Kingsbury
Jia Liu
Mingyi Hong
Venue: NeurIPS 2022 Accept (2022)
Keywords: Decentralized bilevel optimization
stochastic linearized augmented Lagrangian method (SLAM)
multi-agent actor-critic algorithm

Abstract: Bilevel optimization has been shown to be a powerful framework for formulating multi-task machine learning problems, e.g., reinforcement learning (RL) and meta-learning, where the decision variables are coupled in both levels of the minimization problems. In practice, the learning tasks would be located at different computing resource environments, and thus there is a need for deploying a decentralized training framework to implement multi-agent and multi-task learning. We develop a stochastic linearized augmented Lagrangian method (SLAM) for solving general nonconvex bilevel optimization problems over a graph, where both upper and lower optimization variables are able to achieve a consensus. We also establish that the theoretical convergence rate of the proposed SLAM to the Karush-Kuhn-Tucker (KKT) points of this class of problems is on the same order as the one achieved by the classical distributed stochastic gradient descent for only single-level nonconvex minimization problems. Numerical results tested on multi-agent RL problems showcase the superiority of SLAM compared with the benchmarks.

A Stochastic Linearized Augmented Lagrangian Method for Decentralized Bilevel Optimization
Songtao Lut
Siliang Zeng'
Xiaodong Cui
Mark Squillante" Mingyi Hong*
Lior Horesh Brian Kingsbury Jia Liu"
'IBM Research, Thomas J. Watson Research Center, Yorktown Heights, NY 10598 songtao@i bm. com, {cuix, mss, lhoresh, bedk)@us bmm com $ Dept.. of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455 {zeng0176 mwoom) 0ummn. edu DDept. of Electrical and Computer Engineering, The Ohio State University, Columbus, OH 43210 1 liu@ece. osu. edu
Abstract
Bilevel optimization has been shown to be powerful framework for formulating multi-task machine learning problems, e.g., reinforcement learning (RL. and meta- learning, where the decision variables are coupled in both levels of the minimization problems. In practice, the learning tasks would be located at different computing resource environments, and thus there is need for deploying decentralized training framework to implement multi-agent and multi-task learning. We develop stochastic linearized augmented Lagrangian method (SLAM) for solving general nonconvex bilevel optimization problems over graph, where both upper and lower optimization variables able to achieve consensus. We also establish that the theoretical convergence rate of the proposed SLAM to the Karush- Kuhhn-KKK----- Kuhn-Tucker (KKT) points of this class of problems is the same order the achieved by the classical distributed stochastic gradient descent for only single-level nonconvex minimization problems. Numerical results tested multi-agent RL problems showcase the superiority of SLAM compared with the benchmarks.
Introduction
In this paper, consider the following general decentralized bilevel optimization (DBO) framework with applications to machine learning problems. Suppose that there are n nodes over connected graph G = {E, V}. where & and V represent the edges and vertices. Let N₁ denote the set of neighboring nodes for node i. Then the goal of DBO is to have these nodes jointly minimize two levels of optimization problems, More formally, DBO is expressed
min Xn
1
Σ
f( (x))....... y (x:))
(la)
71
1=1
s.t.
x; = x E Ni, Vi E [m]
(1b)
12
vi(x) = arg
min
Σ (x.. s.t. YEA Yy j N₁, Vk [m], (1c)
where vector x; is the upper level (UL) optimization variable at each node i, vector Yı. denotes the lower level (LL.) decision variable for the keth learning task at node i, fi(:) ) is (smooth) UL loss function and possibly nonconvex with respect to (w.r.t.) both the UL and LL variables, gi, denotes the LL objective function of the kth task node i, represents the total number of LL
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

N,, Vi [n], Ak E [m]] optimization problems, the consensus constraints x, Vi, =YAA.
enforce the model agreements at each level of the problems and for each LL learning task, and y (y. yn,k, I is the optimal solutions of the kth L.I problem under the consensus constraints.
Applications of Bilevel Optimization. Many machine learning problems can be formulated math- ematically form of bilevel optimization or, more precisely, special case of problem ( e.g.. meta-learning or meta reinforcement learning (RL), actor-critic (AC) schemes in RL, hyperparameter optimization (HPO), and on.
Classical bilevel optimization is referred to as the case where there is no consensus constraint but with only two levels of the minimization subproblems, i.e., miny / f(x. (x.y"(( (x)), s.t. y"(x) = arg miny g(x, y), which is also known as Stackelberg games [ with the UL. decision variable as the leader and the LL decision variable as the follower. It turns out that this class of optimization problems is useful in formulating a wide range of hierarchical or nested structured machine learning problems. For example, one of the most popular domain adaption learning models, model-agnostic meta-learning (MAML) 2 3) can be written as a special case of bilevel programming [4], where the UL model provides good initialization for accelerating learning procedures by implementing the LL algorithms. The idea behind the model design is that the UL model is considered as the meta learner that searches for a permutation-invarian subspace over multiple task-specific leamers the L.I so that the performance of the MAMI. model can be generalized well for unseen or testing data samples. The theoretical analysis of the generalization performance of this class of bilevel problems has shown that MAML can indeed decrease the generalization error as the number of tasks increases, least for strongly convex loss functions (5). Subsequently, a thorough ablation study from the latent representation perspective shows that feature reuse is the actual dominant factor in improving the generalization performance of MAML [6), and the authors propose a neural network-oriented algorithm with almost no inner loop (ANIL) that splits the neural network parameters into two parts corresponding to the UL and LL optimization problems, respectively. Extensive numerical experiments illustrate that ANIL achieves almost the same accuracy as the classical MAML but with significant computational savings. This example further strengthens the necessity of variable splitting in the learning structure by optimizing two levels of objective functions to enhance the generalization performance. Beyond the traditional supervised meta-learning scenarios, MAML. has also been applied to increasing the generalization ability of agents in RL problems by replacing the (stochastic) gradient with the (natural) policy gradient (PG) [3] under the same two-level structure.
Besides meta-learning problems, AC structure in RL is another class of common learning frameworks that can be formulated by a bilevel optimization problem in nature 7 the UL aims at optimizing the policy while the critic step at the LL is responsible for value function evaluation. In addition, as the expressiveness of neural networks increased sharply over the past decades, the reuse of large models with adaptation to multi-task learning problems presents promising solutions by leveraging the pre-train and fine-tune strategy, such as in applications of HPO [00 [1] where the hyperparameters are trained at the UL problem so that the downstream learning tasks are learned with low costs including the expense of both computation and memory.
where the actor step at
Applications of Multi-agent Settings. When multiple computational resources are available and connected, it is well motivated that exploring them solves distributed large-scale problems with a reduced amount of training time or performs multi-task learning. The bilevel structure of the meta-learning (ML) is a good fit in this scenario as either UL/LL or both levels may need to access the networked data samples rather than local ones. For example, a federated learning setting of K have been built up over multiple nodes recently, where the meta/UL. learner finds an initial shared model while the local/I.1. learners leverage it for adapting data distributions of individual users. In such a way, the federated MAMI. model can realize personalized learning without sharing heterogeneous data over numerous clients. Once there is no central controller for coordinating the model aggregation, a diffusion-based MAML (Dif-MAML) [14] is proposed by spreading the model parameters over network, where the UL parameter is updated by one step of stochastic gradient descent (SGD) based on a combination of the parameters of neighbors as the initialization for local model updates.
MAML 12 and bilevel optimization
Decentralized hierarchical structured learning is even more stringent in the multi-agent RL (MARL) setting [15 as the learning tasks are essentially located at scattered sensors and/or controllers. Under this setting, MARL problem becomes a multi-objective optimization problem under provided (approximate) value functions, where the policy of each agent needs to be learned locally by certain
2

---

efficient iterative methods, such as multi-agent deep deterministic policy gradient (MADDPG) [[]] trust region methods [T7] optimal baseline based variance reduced policy gradient [8] and/or improved by more advanced techniques, e.g., constrained policy optimization [19 and large sequence models [20] In such a way, the total reward can be maximized over the distributed agents through optimizing the networked policy. In fully collaborative setting, the cam-baseed value function is even required to be shared over all the agents such that each agent is able to improve its policy based the estimated total reward. For example, the decentralized AC (DAC) scheme has been investigated widely [15 21 [22]. where each agent uses the actor step to optimize its policy while the critic step performs one step [3]] multiple steps of temporal difference learning with mini-batch sampling (MDAC) [22 24 and communications so that the team- team-based reward over the network is obtained by each agent. It turns out that DAC can be formulated as a special case of problem (I) as there is no consensus at the UL.. Recently, it has been revealed that if there exists homogeneity of the state and action spaces, decentralized policy consensus (or partial policy parameter sharing strategy) provides significant merits to the centralized training and decentralized execution paradigm in terms of learning scalability and efficiency 23 25 which motivates the consensus process at both UL and LL DBO problems.
Related Theoretical Works. Given the fruitful results across these many applications, the corre- sponding theoretical analysis has been developing very fast as well for variants of bilevel optimization problems. For example, the convergence behaviors of classical inexact MAML (iMAML) methods have been quantified for both convex [26] (7 and nonconvex (28) cases of the UL loss function, where the LL algorithm only performs one step of stochastic gradient descent (SGD) based on the LL objective functions as the adaptation step. Moreover, the iteration complexity of ANIL with multiple iterations for minimizing the LL problems have been studied in [29]. which justifies the significant computational advantages of ANIL compared with MAML. in theory. Furthermore, the finite-time analysis of AC algorithms has shown [30) that, once the learning rates at both the actor and critic sides are chosen properly, a two timescale AC algorithm can achieve an ( (c-55) iteration complexity for finding the first-order stationary points (FOSPs) of general nonconvex reward functions.
Besides these theoretical analyses in a specific learning setting, the algorithm design and correspond- ing convergence analysis for general bilevel optimization solvers have been recently advancing at rapid pace under certain assumptions that the UL objective function is general nonconvex while the LL objective functions strongly convex, which covers the existing convergence results shown for AC algorithms. The typical algorithms include those with double-loop structure, those with two timescale or single timescale but single-loop, and those with error-correction or To be more specific, double-loop algorithms, such as bilevel stochastic approximation (BSA) methods 31 and stochastic bilevel optimizers (stoBiO) 32]. mainly request an inner loop to solve the LL problem up to a certain error tolerance or with a certain number of iterations and then switch back to optimize the UL problem, which can achieve an O convergence rate to the e-FOSPs. In practice, single-loop algorithms are implemented more efficiently in terms of computational com- plexity and hyperparameter tuning compared to double-loop algorithms. A two-timescale stochastic approximation (TTSA) was analyzed in [33], but it is shown that TTSA needs O(e 2.5) number of iterations to achieve the c-FOSPs. Later, an error correction method, named the Single-Timen Timesclee stochAstic BiLevEl optimization (STABLE) method [34, improves the convergence rate of the single-loop algorithm to Oc-22) and a tighter analysis for ALternating Stochastic gradient dEscen' (ALSET) shows that the single-loop algorithm can also achieve a convergence of O(E without the error correction technique. When more advanced momentum-assisted or variance reduction methods are adopted in the algorithm design, the subsequent works, such as the momentum-base recursive bilevel optimizer (MRBO) (35) and the single-timesen
stochastic approximation
(SUSTAIN) (36] and the variance reduced BiAdam (VR-BiAdam) (37, can sharpen the convergence rate of bilevel algorithms to O(E -155).
For the theoretical works on MAML/MARL, it is shown in 22 24 that when the critic side is allowed the consensus step at each agent to approximate the networked rewards, MDAC algorithms can achieve an (c)2)) convergence rate to FOSPs, but both of them require an inner loop procedure for the LL problem which makes the algorithms double loop. Dif-MAML [14] is able to perform the UL consensus-based meta learning, but iMAML considered in Dif-MAML is only very special case of bilevel. Thus, the applicability of Dif-MAML is restrictive. One of the closest works to ours is coordinated AC (CAC) (23), which can realize the consensus on both UL and LL problems with O(e 2.5) number of iterations and is only for DAC problems. A thcoretical comparison between our
3

---

Table I: A comparison with closely related prior work (decentralized) bilevel optimization learning. "Comm." refer to whether the algorithm only needs one round of communication at either UL or LL per iteration; "Alg." ref' to the types of the basic stochastic algorithms adopted in the method.
Prior work
Consensus UL
Method
Rate
Comm.
Alg.
Setting
LL
Ghadimi al.
3
BSA
0(1/2))
SGD
bilevel
Hong et al. 33
TTSA
011/29)
SGD
bilevel
Chen et al.
43
ALSET
0(1/2)
SGD
bilevel
Khanduri
36
SUSTAIN
0(1/c15)
Momentum
bilevel
Kayaalp et al.
14
Dif-MAML
0(1/2)
/
SGD
iMAML
Kaiqing al.
DAC
V
PG
MARL
Chen et al.
222
MDAC
011C2)
PG
MARL
Hairi et al.
24
MDAC
0(1/2)
PG
MARL
Zeng et al.
CAC
O(1/22)
PG
MARL
This work
SLAM
((1((ne))
SGD/PG
bilevel
work and closely related previous works on bilevel programming shown in Table There is a line of independent work decentralized optimization. But the existing works only suitable for single-level minimization of only nonconvex problems, such as distributed SGD [38 39], stochastic gradient tracking [40 41 and stochastic primal dual algorithm 42 which achieve ((1/(ne²))
convergence rate to FOSPs for general nonconvex objective function optimization problems.
Main Contributions of This Work. In this work, we consider very general DBO setting, where both UL. and L.L. problems can include a consensus constraint for model parameter sharing and there would be multiple LL problems coupled with the UL problem. To solve this problem efficiently in fully decentralized way, we propose Stochastic Linearized Augmented Lagrangian Method (SLAM) for dealing with both of the two levels of the optimization processes and the consensus constraints at each level. Leveraging the linearized augmented Lagrangian function as a surrogate, the design of SLAM is simple and easily implemented as it is single-loop algorithm with only step sizes to be tuned for convergence. We make the standard assumptions on Lipschitz continuity and convexity for both the UL and LL optimization problems shown in the existing literature. We establish the conditions of SL.AM w.r.t. convergence to e-Karush-Kuff Kuhn-Tuukkee (KKT) points of problem (1) at a rate of (11 / (nc²)) matching the standard convergence rate achieved by decentralized SGD type of algorithm to FOSPs for only single-level nonconvex minimization problems. Remarkably, through numerical experiments MARL problems, it observed that SLAM converge faster than the existing MARL methods and even achieve higher rewards in most cases.
To summarize, the main contributions of this work are highlighted as follows:
Our proposed SLAM algorithm is generic, and thus generalizes the single agent- based bilevel algorithms to the multi-agent setting and is amnable to be specialized to solve multiple consensus- based DBO problems.
SLAM is single-timescale and single-loop algorithm that can find the r-KKT points at a rate of ((1((ne)), which shows a linear speedup w.r.t. the number of nodes. To the best of our knowledge, this is the first work that shows decentralized stochastic algorithm can achieve this rate under the constraints where any level or both levels of the DBO problem requires the consensus process.
Numerical results that illustrate the proposed SLAM outperforms the state-of-the-art MARL algorithms over heterogeneous networks in terms of both convergence speed and achievable rewards.
Due to space limitations, all technical proofs are deferred to the supplement.
2 Decentralized Bilevel Optimization Framework
Problem formulation of DBO. One of the main motivations for performing decentralized joint learning is dealing with large-scale dataset scattered data samples. At each node, the loss func- tion can be written fi yi, (x:). . (x:) e Ig Xf where DU denotes the local data distributions at the UI. optimization problem, and F. Fx vi, (x:). vi, (xx): represents the estimation error of the UL learning model
(x:):<)]

---

data $ E D.D Similarly, the LL learning tasks also include randomly sampled data from local distribution D for task k. so the LL cost function at each node can be expressed as (e,a(xi, Yi.k) EeEDy, [GLa yzi [)], Vk, where Gi denotes the estimation error of the LL learning model over Yi,i on data Ç E DI It is well known that SGD is one of the most efficient algorithms for tackling large amounts data samples. Before showing the algorithm design, we first reformulate problem ① in concise and compact way from global view of the variables. Let
- ( xn,'' and yk [yi,k:-... : :..kk). Then, problem TT can be rewritten by concatenated variables as
min f(x,y((x))
(2a)
s.t.
Ax 0.
(2b)
vi(x) = arg min Io (x, yk) yk
Σ (i, s.t. Aya = 0, Vk E [m]]
(2c)
where denotes the kth LL loss function, A E BlE)x" represents the incidence matri and fx(,, (xx)) abbreviates fx yi, (x,), Vi. (x.)) for notational brevity.
Algorithm Design. Towards this end, it is straightforward to construct variant of the classical augmented Lagrangian function for the UL optimization problem as
(x, fxx 7A,, Ax) + P7 Ax|],
2
where A denotes the dual variable (Lagrangian multiplier) for the consensus constraint, p > 0, and a scaling factor (which will be determined later).
Motivated by the primal- dual optimization framework [44]. one step of gradient descent based on the linearized objective function with following gradient ascent step sufficient for the minimization of the general nonconvex loss function under the linear constraints, which means that there is no need to solve an inner optimization problem before updating the Lagrangian multiplier is done in the classical augmented Lagrangian method.
When both the UL and LL objective functions are differentiable and the inverse of the Hessian matrix at the LL problem exists, i.e., V yay, Ih V
(x)) is invertible, then there exists a closed form for V [f(,,, (x:))) Following the existing works on bilevel algorithm designs, replacing (x;) by Vi.k in the gradient of fx (x,( w.r.t x; can serve as an efficient surrogate for the stochastic gradient estimate. However, in the decentralized setting, only individual loss functions are observable at each agent, therefore, the local UL implicit gradient is computed through replacing 9k yk) by gr,k (X,, kt, denoted as V (x,, Yr.k). Let h² and h; respectively denote the distributed stochastic gradient estimate of the LL and UL objective functions at points (x", y and (x", (x",yf+1 yf wk, w.r.t and x, where represents the index of iterations. Thus, our proposed SLAM can be expressed as
2 llve yill, #22
yk ++1 arg min (h
9. + + + pAy)). - yt)
Vk:
(4a)
Y
w = + P PAy Vk,
(4b)
x +1 = arg orgminnhe (h; + AAAAX + ,Ax'), xxx+ a |x x1
(4c)
1+ X +1 +1
(4d)
where wi is the dual variable for ensuring the LL consensus process for each learning task, and are the parameters of the quadratic penalization terms, and p/7 here is the step-size for the updates of the dual variables.
Implementation of SLAM. Noting that the objective functions in each subproblem, i.e., 44a and
4c
are quadratic, we can easily have the updates of both UL and LL optimization variables as
HHere assume the problem dimension is 1, without loss of generality, to simplify the notation.
5

---

Yk ++
=Yh (h + + + Ay vk,
(5a)
x"
+
(5b)
where 1/xx and 1/3 serve as the step-sizes of updating both UL and LL learning models. Subtracting the equality with the same one from the previous iteration for both (5a) and 5b ends up with efficient model updates of both the UL and LL learning problems as follows:
yk =2 gykk y 1--
3 h - bigh
Ak,
(6a)
2W 2Wxxx - W x'x"11 hh hi hi/t).
(6b)
where the mixing matrices, with Tg 3/7 and Ty = a/% are defined as
W 4 (1+9-t) ATA, W I AAA
(7a)
5
2Tg
Tg
w A I-- (1+y 10
A'A,
W 2 I
A'A.
(7b)
27y
According to (6a) and (6b). it can be readily observed that SLAM is amenable to fully decentralized implementation. The detailed algorithm description provided in Algorithm from local view of the model update, where [Wi; denotes the ijth entry of matrix W, [hil.. is the gradient estimate
of ( (i.e.. b = [bb]IAA..... bgl,,ll") and similarly [b7], is the local gradient estimate of (x( 1 (i.e., hy [hr]...... [hy,,"")
Algorithm Decentralized implementation of SLAM
Initialization: a. (8, x yi.ee Vi, k, and set X = w 0, Ak; 1: for r = =1,2.... ,T do
2: for i
1.. in parallel over the network do Estimate gradient V (x), yf,)) for each task and V [x( yi,k r+1 locally
3:
4:
y EEN, W ol - [Wr Wolbstt - 3-1 (hij).. - [hg- LL models
5:
x = 2 JEN,
W f652 [Wy Wyyos a (ht): (b7-11)) UL model
6: end for
7: end for
Besides, if there is a consensus requirement at only one level the optimization problem, then the problem the other level becomes with multiple objective functions. Our proposed SLAM can also be applied for solving any these problems by a minor revision of the generic SLAM formulation. To be more specific, we provide the following discussion.
Special Case of DBO TT (with only consensus in the LL problems). If there is only need for consensus of LL model parameters, then problem (2) reduces to the following DBO problem. For example, in solving multi-agent actor-critic RL problems, the UL optimization problem consists of improving the policy for each agent while the LL problem requires all the agents to jointly evaluate the value function over the whole network. The DBO problem then expressed as
min M(xx,
E [n]
(8a)
s.t. <2((x)= = arg min (x.
Σ Dr.k (x;, s.t. Ay: = 0, vk E [m].
(8b)
The major difference between problem and {8) is that the UL optimization problem includes multiple objectives over the model parameters x,, Vi [n]. In this case, the updating rule of variable x in (6b) reduces to *+1 = x" h2/a by forgoing the dual update w.n.. A. The detailed implementation summarized in Algorithm [ where we name this special case of SLAM by SLAM-L the LL consensus process the main feature in this setting.

---

Algorithm/ 2 Decentralized implementation of SLAM-L
Initialization: a, 8,137, x,, Yi,e, Vi, k, and set w O, Vk; for == -1,2. ... 1,,,,.... Estimate gradient (x), for each task and V , vi,k 1 locally
do
2: for --
in parallel over the network do
3:
4:
Vikk JEN, [ oloyy, [W "llyy" 3-1 (hh]l, - [h [1,)) LL models
5:
x2 = - a b7
UL models
6: end for
7:
end for
Special Case DBO ① (with only consensus in the UL problem). The other special is analogous to the first one with the difference being the absence of the LL consensus process in comparison to (), which is written as follows:
- 1 Σ T
n
min f(x,)((x)
(9a)
S.t. Ax (x,) arg min Ii.k Ji,N VI,k), E [n]], Ak [m].
(9b)
where there are multiple objectives in the LL optimization problems. Problem (9) also covers a wide range of applications in machine learning, e.g., multi-task and/or personalized learning. and so on. In this case, the update of variable Yą shown in (5a) is changed to y y h there is no consensus constraint involved. Analogous to the previous case, the implementation of this algorithm presented in Algorithm and termed as SLAM-U,
Algorithm 3 Decentralized implementation of SLAM-U
Initialization: a, B, y, x,, yl,u, Vi, k, and set X 0, Vk: 1: for 1,2, 2.. ,T do
2: for 1,2, ...... in parallel over the network do
Estimate gradient (x for each task and (x( yiit") locally
4: yi, -Y, B [gylie
LL models
5:
x x 2 EjEN [W - a-1 (IhT)e - h, 1b,
UL model
6: end for
7: end for
3 Theoretical Convergence Results
Before showing the theoretical results about the convergence guarantees of SLAM, we first need five main classes assumptions used showing the descent of some quantifiable function so SLAM reach the kKK points of the DBO problems. More detailed definitions and properties regarding these assumptions are deferred to the supplement.
3.1 Assumptions
Our theoretical results based on the following assumptions on the properties of the loss functions in both the UL and LL optimization problems, which are mainly related to the continuity of the objective function and stochasticity of the gradient estimates.
A1. (Lipschitz continuity of both UL and LL objective functions) Assume that functions f.(-), (-), V (+),, Vi, are (block-wise) Lipschitz continuous with constants L L,11 Lg.1. Ly for both x and yk, Vk, and V2 (i.te, Vi are bounded by Czy-
A2. (Connectivity of graph G) The communication graph G is assumed to be well-connected, i.e., IF == where L A A, and the second-smallest eigenvalue of L is assumed be strictly positive, i.c., 7min (A" A) > 0.
7

---

A3. (Quality of the stochastic gradient estimate) The stochastic estimates of ( Vi,e),
(x,, Vi, ki are unbiased and their variances are bounded by o². og
A4. Assume that the UL objective functions (x (T,, Vi, & are lower bounded.
A5. (Strong convexity of gr)(()) w.r.t yr,k) Function gr,(+)) is Hn-Strongly convex w.I.t Yi,k: Vi,k. k.
Note that these assumptions are commonly used in the convergence analysis for bilevel and decen- tralized optimization algorithms. Given these assumptions, we are now in position provide the following theoretical convergence guarantees.
3.2 Convergence Rates of SLAM
Theorem 1. (Convergence rate of SLAM to e-KKT points) Suppose that Al-A5 hold and assume IV V.,,.1..( - -n- Di= (t,. S T.glly; Yil. Vi if V 95.k (.), Vi, k are re- quired in computing the UL implicit gradient. When step-sizes are chosen as 1/a 1/3 ((vn/T), TJ: Ty (ppomaax (A (ATA) A),, the mini-batch size hf is ((log(TT)), then the iterates fx", X3, yk: wk. Vk, r} generated by SLAM satisfy
T
T 1[[ 0(1/VTT), (10a)
UL:
B f ,i((x"))) . (1X1
T
1 T T B[IAA|ll
LL:
T EllVy - )X('D)11~~
Σ
Vk,
(10b)
where x = n 11 x, and T denotes the total number of iterations.
Remark 1. It is noted in Theorem D that the convergence rate achieved by SLAM to find the c- approximate KKT points of (T) (including both the first-order stationarity of the solutions and the violation of constraints) is on the order of 1/ (nc²). Therefore, it follows that linear speedup w.r.t. the number of learners can be achieved by SLAM for DBO, matching the classical results of distributed SGD for only single-level general nonconvex problems.
Remark 2. In comparison with existing bilevel algorithms, SLAM is single timescale algorithm since the learning rates can be chosen as 1/a 1/3, which is consistent with ALSET (43).
Remark 3. The major novelty of obtaining these theoretical results relies on the developed variant of the augmented Lagrangian function and subsequently derived recursion of the successive dual variables, which quantify well the consensus errors resulting from both UL and LL optimization processes in terms of primal variables. Note that this is distinct from the existing theoretical analysis of stochastic algorithms, such distributed SGD 38 39], stochastic gradient tracking 44 41).
stochastic primal-dual algorithms [42 45), etc.
Corollary 1. (Convergence rate of SLAM-L to K-KT points) Suppose that AI-A5 hold and assume VIVe N.y. (x,, - V (5y9k(x,y)) (x) S T.glly: y'll, Vi, k if 4 (.), Vi, k are required in com-
puting the UL implicit gradient. When step-sizes are chosen as 1 1/a O(1/V()))))))) 1/3 Ol O(Vn/T), To 2 Opp (A" A)). P 2 the mini-batch size of hy is Ollog(TT)) the iterates {x" P.k wh, Wk,r) generated by SLAM-L satisfy
UL: T I BIIVAA(X
1
y (x))11) (,) O(/VVT)
and LL:
10b)
Remark& 4. Different from Theorem I the stationarity of the UL model parameters requires the so there is
shrinkage of the gradient size over each individual UL problem as shown in Corollary I no speedup on the convergence rate guarantee UL.
Corollary 2. (Convergence rale of SLAM-U e-KKT points) Suppose that A1-A5 hold. Given the conditions on 1/o,1/ 1/3, TJ, Tg and the mini-batch size hy shown in Theorem 7 the iterates
{x", N, Yk. Yk, r generated by SLAM-U satisfy
UL:
10ah
and
LL:
Ellly yx(x))] O(1/VNT),
T
8

---

Navigation (5 Agents)
Navigation Agents)
Average Reward
Average Reward
SLAW-AC
SLAM-AC DAC
160
150 Episodes
230
152 Episodes
260
250
Figure 1: The averaged reward versus the learning process the cooperative navigation lask.
Pursult (4 Agents)
Pursuit (6 Agents)
0.202
6,250
2.122
0.175
Reward
2.355
Average Reward
6,130
4.255
6.125
SLAM-AC
8.050
SLAM-AC
2022
CAC
0.025
3.002
0.000
Episodes
Episades
Figure 2: The averaged reward versus the learning process on the vursuit-cvasion game. (Consensus with one layer of the actor neural nets and all layers of the critic neural nets.)
Numerical Results
In this section, evaluate our proposed algorithm using MARLenvironmennt 1) the cooperative navigation task [16], which is built on the OpenAl Gym platform [46]; and 2) the pursuit-evasion game [47. which built the PettingZoo platform (48). Detailed experimental settings and additional numerical results are provided in the supplement.
Cooperative Navigation Task. In this game, consider that the agents aiming to jointly reach n different landmarks as soon as possible, where the Erdos Renyi Graph is used. We assume that cach agent can observe the global state and has 5 possible actions: stay, left, right, up, and down. This task consists shared common goal avoiding collision among the agents while they navigate to the targeting landmarks. In the simulations, each agent locally maintains two fully connected neural networks as the actor network (at UL w.r.t. x₂) and the critic network (at LL w.r.t. y:). respectively. Moreover, each agent shares its critic network with its neighbors cooperatively estimate the global value function and independently train its actor network to complete its local task.
We compare the performance of our proposed SLAM with application to the DAC setting, named SLAM-AC, with two benchmark algorithms: DAC (15) and mini-batch DAC (MDAC) [22]. Theoret- ically, MDAC needs O In e batch size in its inner loop update critic parameters before each update in policy parameters, which is not practical. Here, we set a small batch = 10 in the inner loop for MDAC to achieve fast convergence. The simulation results this coordination game are presented Figureq] where the performance is averaged over 5 independent Monte Carlo (MC) trials for each algorithm.
Pursuit-Evasion Game. the pursuit-evasion game, there are two groups of nodes: pursuers (agents) and evaders. The agents are connected through ring graph. Pursuers could observe the global state of the video game, evader considered caught if two pursuers simultaneously arrive at the evader's ' location. As each pursuer should learn to cooperate with other pursuers to catch the

---

evaders, the pursuers share certain similarities with each other since they need to follow similar strategies achieve their local tasks: simultaneously catching an evader with other pursuers.
We follow the experimental set up in [23]. where all agents partially share their actor networks with
neighbors for collaborations in their policy spaces and fully share their critic network cooperatively learn the global value function. In Figure 2 we compare SLAM-AC with two benchmarks, CAC [23
and MDAC [22], with 5 MC trials again. To ensure a fair comparison, all algorithms use the same parameter sharing scheme mentioned above. Note that CAC (3 is a variant of DAC [3] and the
only difference that CAC can partially share its policy parameters while the policy parameters are not shared in DAC. In the experiment, each agent maintains two convolutional neural networks, one
for the actor and one for the critic (Please refer to the supplement for detailed structures).
Concluding Remark
In this paper, studied generic form of the DBO problem, which is shown to have three major variants that formulate multiple hierarchical machine learning problems. Targeting these DBO problems, we proposed SLAM a simple and elegant algorithm to solve DBO in fully decentralized way. Under mild conditions, we establish theoretical results showing that our proposed SLAM is able to find the T-T points with a convergence rate of ((1/(ne²)) which matches the standard convergence rate achieved by the classical distributed SGD algorithms for solving only single-level general nonconvex optimization problems. We tested the performance of SLAM numerically MARL scenario and found that SLAM outperformed the traditional AC algorithms w.r.t. convergence speed and (in most cases) achievable rewards.
Societal impact. To the best of our knowledge, we do not see any ethical or negative immediate societal consequence of this work.
Acknowledgments
M. Hong and Zeng are partially supported by NSF grants CIF-1910385 and CCMMI-172773
References
[1] V. Stackelberg, Heinrich, Von, and Heinrich, The Theory of the Market Economy. Oxford University Press, 1952.
[2] C. Finn, P. Abheel, and S. Levine, "Model-agnostic meta-learning for fast adaptation of deep networks," in Proceedings of International Conference on Machine Learning (ICMLJ, pp. 1135-1135, 2017.
[3] H. Liu, R. Socher, and C. Xiong, "Taming MAML: Efficient unbiased meta-rriinforcement learning," in Proceedings of International Conference on Machine Learning (ICML), pp. 4061-4071,
[4] A. Rajeswaran, C. Finn, S. M. Kakade, and S. Levine, "Meta-learning with implicit gradients," in Proceedings of Advances in Neural Information Processing Systems (NeurIPS), vol. 32, 2019.
[5] A. Fallah, A. Mokhtari, and A. Ozdaglar, "Generalization of agnos-ag leatnlc algorithms: Recurring and unseen tasks," in Proceedings of Advances in Neural Information Processing Systems (NeurIPS), 2021.
[6] A. Raghu, M. Raghu, Bengio. and O. Vinyals. "Rapid learning or feature reuse? towards understanding the effectiveness MAMI."" in Proceedings of International Conference on Learning Representations (ICLR), 2020.
[7] R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction. MIT Press, 2018
[8] Z. Yang. Y. Chen, M. Hong, and Z. Wang. "Provably global convergence of actor-critic: case linear quadratic regulator with ergodic cost," in Proceedings of Advances in Neural Information Processing
Systems (NeurIPS), vol. 32, 2019.
[9] T. Xu, Z. Wang. and Y. Liang. "Improving sample complexity bounds for (natural) actor-critic algorithms." in Proceedings of Advances Neural Information Processing Systems (NeurIPS), vol. 33, pp. 4358 4369, 2020.
[10] A. Shaban, C.-A. Cheng, N. Hatch, and B. Boots, "Truncated back- propagation for bilevel optimization." in Proceedings of International Conference on Artiffcial Intelligence and Statistics (AISTATS), pp. 1 1723- 1732, 2019.
[11] R. Ranjan, V. M. Patel, and R. Chellappa, "Hyperface: A deep multi task learning framework for face detection, landmark localization, pose estimation, and gender recognition," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 41, 1, pp. 121-135, 2017.
10

---

[12] A. Fallah, A. Mokhtari, and A. Ozdaglar, "Personalized federated learning with theoretical guarantees: A model-agnostic meta-learning approach." in Proceedings of Advances in Neural Information Processing Systems (NeurIPS), 2020.
[13] J. Li, F. Huang, and H. Huang. "Local stochastic bilevel optimization with momentum-based variance reduction," arXiv preprint arXiv:2205. 00000, 2022.
[14] M. Kayaalp. S. Vlaski, and A. H. Sayed, "Dif-MAML: Decentralized multi-agent meta-learning." IEEE Open Journal of Signal Processing, vol. 3, pp. 71-93, 2022.
[15] K. Zhang, Z. Yang. H. Liu, T. Zhang, and T. Basar, "Fully decentralized multi-agent reinforcement learning with networked agents," in Proceedings of International Conference Machine Learning (ICML), pp. 5872-5881, PMLR, 2018.
[16] R. Lowe, I. Wu, A. Tamar, J. Harb, O. Pieter Abbeel, and I. Mordatch, "Multi-agent actor-critic for mixed cooperativeecooppciiive environments," in Proceedings of Advances in Neural Information Processing Systems (NeurlPS), vol. 30, 2017.
[17] J. G. Kuba, R. Chen, M. Wen, Y. Wen, F. Sun, J. Wang, and Y. Yang. "Trust region policy optimisation in multi-agent reinforcement learning," arXiv preprint arXiv:2109, 1251, 2021.
[18] J. G. Kuba, M. Wen, L. Meng, H. Zhang, D. Mguni, J. Wang, and Y. Yang. "Settling the variance of multi-agent policy gradients," in Proceddings of Advances in Neural Information Processing Systems (NeurIPS), pp. 13458-13470, 2021.
[19] S. Gu, J. G. Kuba, M. Wen, R. Chen, Z. Wang. Z. Tian, J. Wang. A. Knoll, and Y. Yang. "Multi-agent constrained policy optimisation." arXiv preprint wxXiv22100002790 2021.
[20] M. Wen, G. Kuba, R. Lin, W. Zhang, Y. Wen, J. Wang, and Y. Yang. "Multi-agent reinforcement learning is sequence modeling problem." arXiv preprint arXiv:2205. 14953, 2022.
[21] Y. Lin, K. Zhang, Z. Yang. Z. Wang, T. Başar, Sandhu, and J. Liu, "A cotmuumicaation-fffiieeeee multi-agent actor-critic algorithm for distributed reinforcement Icarning," in Proceedings of IEEE 58th Conference on Decision and Control (CDC), pp. 5562-5567, 2019.
[22] Z. Chen, Y. Zhou, R.-R. Chen, and S. Zou, "Sample and communication-effiieee decentralized actor-critic algorithms with finite-time analysis," " in Proceedings of International Conference on Machine Learning (ICML). pp. 3794-3834, 2022.
[23] S. Zeng, T. Chen, A. Garcia, and M. Hong, "Learning to coordinate in multi-agent systems: A coordinated actor-critic algorithm and finite-time guarantees," in Proceedings of the 4th Annual Learning for Dynamics and Control Conference, pp. 278-290, 2022.
[24] F. Hairi, J. Liu, and S. Lu, "Finite-time convergence and sample complexity of multi-agent actor-critic reinforcement learning with average reward," in Proceedings of International Conference on Learning Representattions (ICLR), 2022.
[25] D. Chen, Y. Li, and Q. Zhang, "Commmniiationn-effccenn actor-critic methods for homogeneous markov games," in Proceedings of International Conference on Learning Representations (ICLR), 2022.
[26] C. Finn, A. Rajeswaran, S. Kakade, and S. Levine, "Online meta-lcamingg" in Proceedings of International Conference on Machine Learning (ICML), pp. 1920-1930, 2019.
[27] M.-F. Balcan, M. Khodak, and A. Talwalkar, "Provable guarantees for gradient-based meta-learning." in Proceedings of International Conference Machine Learning (ICML), pp. 424 433, 2019.
[28] A. Fallah, A. Mokhtari, and A. Ozdaglar, "On the convergence theory gradient- model-agnostic meta-lcarning algorithms," in Proceedings of International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1082-1092, 2020.
[29] K. Ji, J. D. Lee, Liang, and H. V. Poor, "Convergence meta-lcarning with task-specific adaptation over partial parameters," in Proceedings of Advances in Neural Information Processing Systems (NeurIPS), vol. 33, pp. 11490- 14490-11500, 11500, 2020.
[30] Y. F. Wu, W. Zhang, P. Xu, and Q. Gu, "A finite-time analysis of two time-scale actor-critic methods." in Proceedings of Advances Neural Information Processing Systems (NeurIPS), vol. 33, pp. 17617-17628 2020.
[31] S. Ghadimi and M. Wang, "Approximation methods for bilevel programming." arXiv preprint
arXiv: 1802.02246 2018
[32] K. Ji, J. Yang. and Y. Liang. "Bilevel optimization: Convergence analysis and enhanced design," in Proceedings of International Conference on Machine Learning (ICML), pp. 4882-4892 2021. 2021.
[33] M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. "A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic," arXiv preprint arXiv:2007.05/70 2020.
[34] T. Chen, Y. Sun, and W. Yin, "Tighter analysis of alternating stochastic gradient method for stochastic nested problems," in Proceedings of Advances Neural Information Processing Systems (NeurIPS), 2021.
11

---

[35] J. Yang, K. Ji, and Y. Liang, "Provably faster algorithms for bilevel optimization." in Proceedings of Advances in Neural Information Processing Systems (NeurIPS), vol. 34, 2021.
[36] P. Khanduri, S. Zeng, M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. "A near-optimal algorithm for stochastic bilevel optimization via
in Proceedings of Advances in Neural Information Processing
Systems (NeurIPS), 2021.
[37] F. Huang and H. Huang. "Biadam: Fast adaptive bilevel optimization methods." arXiv preprint arXiv: 106. / 1336, 2021.
[38] X. Lian, C. Zhang, Zhang, C.-J. Hsich, W. Zhang, and Liu, "Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent," in Proceedings of Advances in Neural Information Processing Systems (NewrIPS), vol. 30, 2017.
[39] H. Tang, X. Lian, M. Yan, C. Zhang, and J. Liu, "D>: Decentralized training over decentralized data," in Proceedings of International Conference on Machine Learning (ICML.), pp. 4848-4856, 2018.
[40] S. Lu, X. Zhang, H. Sun, and M. Hong. "GNSD: madient-tracking based nonconvex stochastic algorithm for decentralized optimization." " Proceedings of IEEE Data Science Workshop (DSW), pp. 315-321, 2019.
[41] A. Koloskova, T. Lin, and S. U. Stich, "An improved analysis of gradient tracking for decentralized machine learning." in Proceedings of Advances in Neural Information Processing Systems (NeurIPS), vol. 34, 2021.
[42] X. Yi. S. Zhang. T. Yang. T. Chai, and K. H. Johansson, "A primal-dual SGD algorithm for distributed nonconvex optimization." IEEE/CAA Journal of Automatica Sinica, vol. 9, no. 5, pp. 812-833, 2022.
[43] T. Chen, Y. Sun, and W. Yin, "Tighter analysis alternating stochastic gradient method stochastic nested problems," in Proceedings of Advances in Neural Information Processing Systems (NewrIPS), 2021.
[44] J. Nocedal and S. Wright, Numerical Optimization. Springer Science & Business Media, 2006.
[45] G. Lan, S. Lee, and Y. Zhou, "Communicationn-efiiieee algorithms for decentralized and stochastic optimization," Mathematical Programming, vol. 180, no. 1, pp. 237-284, 2020.
[46] G. Brockman, Cheung, Pettersson, J. Schneider, Schulman, Tang, and W. Zaremba, "OpenAI Gym." arXiv preprint arviv: 604001540, 2016.
[47] J. K. Gupta, M. Egorov, and M. Kochenderfer, "Cooperative multi-agent control using deep reinforcement learning," in Proceedings of International Conference on Autonomous Agents and Multiagent Systems, pp. 66-83, Springer, 2017.
[48] J. Terry, B. Black, N. Grammel, M. Jayakumar, A. Hari, R. Sullivan, L. S. Santos, C. Dieffendahl, C. Horsch, Vicente, Perez-Vicente, al., "PettingZoo: Gym for multi-agent reinforcement learning," " in Proceedings of Advances in Neural Information Processing Systems (NeurlPS), vol. 34, pp. 15032-15043, 2021.
R. Perez-
[49] Y. Nesterov, Introductory Lectures Convex Optimization: A Basic Course, vol. 87. Springer Science & Business Media, 2003.
[50] R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour, "Policy gradient methods for reinforcement learning with function approximation," in Proceedings of Advances in Neural Information Processing Systems (NeurIPS), vol. 12, 1999.
12

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] [Yes]. [No] [N/A] You
strongly encouraged include justification your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See
Did you include the license to the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do nol modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do main claims made the abstract and introduction accurately reflect the paper's 's contribu- tions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theorctical results...
(a) Did you state full set of assumptions of theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as URL)? [No]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect to the random seed after running experiments multiple times)? [Yes]
(d) Did you include total amount of compute and the type resources used (e.g.. type GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent obtained from people whose data you're us- ing/curating? [N/A]
Did you discuss whether the data you are using/curating contains personally identifiable informa- tion or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable?
[N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "xaKJz6Twz9", "reviewer": "Reviewer_wDpj", "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.", "questions": "- Could you comment more on practical considerations to aid judging the efficiency improvement? [** post-rebuttal ** : partially addressed in rebuttal via new experiments]\n- Could you give some more intuition on what leads to higher rewards in existing experiments? [** post-rebuttal ** : addressed]\n- 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]\n\n- 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.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- paper is clear\n- inclusion of empirical behavior is nice\n- the problem studied is very relevant to current trends in other subfields of ML (e.g. multi-agent RL, multi-task learning)\n\nWeaknesses:\n- 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]", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "vZCSwizdsUH", "reviewer": "Reviewer_a2eA", "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.", "questions": "Please see the comments in Strengths And Weaknesses.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\n1. 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. \n\n2. The authors provide a theoretical analysis on the proposed algorithm. \n\nCons:\n1. 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? \n2. 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. \n\n3. 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? \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "nYx7XcYmeO8", "reviewer": "Reviewer_r52d", "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)).", "questions": "No Question.", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nStrength 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.\n\nStrength 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.\n\nWeakness. 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.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4ZQbC-fxp4", "reviewer": "Reviewer_6ivX", "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.", "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?\n2. 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] ?\n3. 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.\n\n[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.\n\n[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.\n\n[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.\n\n[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.\n", "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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Update after Rebuttal\n\nI appreciate the authors' detail replies, and I have become largely persuaded by the authors and have raised my rating from 5 to 6.\n\nStrengths: The theoretical part and the algorithms are good and sound solid.\n\nWeaknesses:\n1. In Page 4, line 167 and Page 7, line 253, the writing of the function may be not right, please check them. \n2. 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. \n3. Please explain the meaning of $g_{k}\\left(\\mathbf{x}^{r}, \\mathbf{y}_{k}^{r}\\right)$, currently, it's not clear.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept