Learning Multi-agent Behaviors from Distributed and Streaming Demonstrations
Authors: Shicheng Liu
Minghui Zhu
Venue: NeurIPS 2023 poster (2023)
Keywords: inverse reinforcement learning; distributed online bi-level optimization

Abstract: This paper considers the problem of inferring the behaviors of multiple interacting experts by estimating their reward functions and constraints where the distributed demonstrated trajectories are sequentially revealed to a group of learners. We formulate the problem as a distributed online bi-level optimization problem where the outer-level problem is to estimate the reward functions and the inner-level problem is to learn the constraints and corresponding policies. We propose a novel ``multi-agent behavior inference from distributed and streaming demonstrations" (MA-BIRDS) algorithm that allows the learners to solve the outer-level and inner-level problems in a single loop through intermittent communications. We formally guarantee that the distributed learners achieve consensus on reward functions, constraints, and policies, the average local regret (over $N$ online iterations) decreases at the rate of $O(1/N^{1-\eta_1}+1/N^{1-\eta_2}+1/N)$, and the cumulative constraint violation increases sub-linearly at the rate of $O(N^{\eta_2}+1)$ where $\eta_1,\eta_2\in (1/2,1)$.

Learning Multi-agent Behaviors from Distributed and Streaming Demonstrations
Shicheng Liu & Minghui Zhu School of Electrical Engineering and Computer Science
Pennsylvania State University
University Park, PA 16802, USA {sf15539, muz16)00uuuu edu
Abstract
This paper considers the problem of inferring the behaviors of multiple interacting experts by estimating their reward functions and constraints where the distributed demonstrated trajectories are sequentially revealed to a group of learners. We formulate the problem as distributed online bi-level optimization problem where the outer-level problem to estimate the reward functions and the inner-level problem is to learn the constraints and corresponding policies. We propose novel "multi-agent behavior inference from distributed and streaming demonstrations" (MA-BIRDS) al algorithm that allows the learners to solve the outer-level and inner- level problems in single loop through intermittent communications. We formally guarantee that the distributed learners achieve consensus on reward functions, con- straints, and policies, the average local regret (over online iterations) decreases at the rate of O(1/N1-7 + 11N1I-1 +1/N), and the cumulative constraint violation increases sub-linearly at the rate of O(N + where 7/, 7/2 E (1/2, 1).
1 Introduction
Multi-agent systems (MASs) are an effective tool to model networked systems where multiple entities interact with each other to reach certain goals. Due to the lack of centralized authority, the data in MASs is usually distributed [ 2] Therefore, distributed learning is desired for MASs where machine learning models are trained over distributed data sets. Current works distributed learning include distributed supervised learning [ 4. distributed unsupervised learning [5] 6 distributed reinforcement learning 7 g etc. Recently, distributed learning is applied learn the behaviors in
MASs from distributed experts' demonstrations via inverse reinforcement learning (IRL) 9
learner aims to learn policy that imitates the expert behaviors in the extends IRL to MASs where the reward functions and policies of group of experts are learned. However, current works on multi-agent IRL have the following two limitations: (i) As mentioned, the demonstration data in MASs is usually distributed while these works assume that there is centralized learner which can obtain all the demonstrations, (ii) There are usually many underlying constraints MASs, e.g., avoiding collision with each other and obstacles, and thus learning reward function combined with a set constraints is better than learning a single reward function in terms of explaining the experts' behaviors [18 19]. Therefore, distributed inverse constrained reinforcement learning (D-ICRL) ()] is proposed where group of learners cooperatively learn the behaviors in an MAS by estimating the experts' reward functions and constraints and each learner can only access a local demonstration set.
In IRL TO 12 13 14.
demonstrations by first learning a reward function. Multi-agent IRL [15] 16 17
While D-ICRL performs over pre-collected distributed data, recent applications 20 21 of IRL motivate the need for algorithms that can learn from sequentially revealed demonstrations and continuously improve the learned models. For example, inferring a person's 's intent by observing her
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

ongoing daily routine (0 and updating evasion strategies by continuously observing the patrollers' behaviors [2T]. However, D-ICRL not efficient to deal with streaming data because has a double-loop learning structure where the outer loop is to update the constraints and the inner loop needs to find corresponding reward estimate. While the computation overhead of this double-loop structure is reluctantly acceptable in offline settings, it is too time-consuming for streaming data since the computation may not be finished before the next data arrives. As D-ICRL is the most important baseline of our work, we include a section in Appendix to summarize our improvements from it.
Related works and our improvements. Current theoretical works on online IRL 20 21 only consider linear reward functions and thus cast the problem as online convex optimization. While these approaches achieve sub-linear regret, their analysis does not hold for non-linear reward functions (e.g., neural networks) as the corresponding objective functions can be non-conver To quantify the algorithmic performance on online non-convex optimization, "local regret" [2 23 is proposed which,
at each online iteration, quantifies the gradient norms of the average sum of some ulready-revealle loss functions. Current state-of-the-are
methods to minimize the local regret. While their methods can achieve the tight regret bound, the follow-the the--hhadeerbbaed methods require multiple gradient descent steps until reaching a near-stationary point at each online iteration. However, if the data arrival rate is fast, the computation may not be done before the next data arrives. To alleviate the computation burden at each online iteration, we use an online gradient descent (OGD) method which only updates the decision variable by one gradient descent step at each online iteration. To the best of our knowledge, no works can quantify the local regret of OGD.
[2 23
use fewlowtth--eeder-bee
Inspired by 9 24 we formulate distributed online bi-level optimization problem where the learners cooperatively learn the reward functions in the outer-level problem and the constraints and corresponding policies in the inner-level problem. Papers (9, 24 25 use double-loop methods 26 27 28 to solve their bi-level optimization problems where they first find a (sub)optimal solution of the inner-level problem in faster loop and then solve the outer-level problem in slower loop. However, when it comes to streaming data, the double-loop method needs multiple steps for the inner-level problem before updating the decision variable of the outer-level problem, which can be too slow to finish the update of the outer decision variable when the data is revealed in a fast speed. Therefore, we use single-lopp method which updates both the outer and inner decision variable only once at each iteration. Notice that the state-of-the-ane on single-loop bi-level optimization [29 30 cannot be directly applied to our problem because they centralized and require the inner objective function to be strongly convex while our problem does not have these properties.
Contribution statement. Our contributions are threefold. First, we consider the problem where group of learners cooperatively recover the policies by estimating the reward functions and constraints from distributed streaming demonstrations of cooperative experts. We formulate this "multi-agent behavior inference from distributed and streaming demonstrations" (MA-BIRDS) problem as dis- tributed online bi-level optimization problem. Second, we propose novel distributed online gradient descent algorithm for the learners to learn the reward functions, constraints, and the corresponding policies in a single loop where the decision variables of both the outer-level and inner-level problems are updated only once at each online iteration. Third, we prove that the distributed learners achieve consensus in reward functions, constraints, and policies, respectively, at the rate of O(1/N" + 2 O(1N + 2 and ((1/Nm + 1/N + 2 where ? E (0. 1) and 1h. 122 E (1/2, 1). The local regret averaged over N iterations decreases at the rate of 0(1/N1 + 1/N1- + 1/N) and the cumulative constraint violation grows sub-linearly at the rate of O(N + 1). Moreover, if the reward functions are linear, we prove that the average cumulative reward difference between the experts and learners diminishes at the rate of O(1/11m + 1/N).
2 Model
This section presents the models of the experts and learners.
Experts. There are NE experts whose decision making is modeled as a constrained Markov game (CMG) [3I] A CMG A,,A, 7, T Po, T, P.rg, Cg, 6) consists of state set S - II S(i), an action set A A Ng A discount factor 7, a time horizon T. and an initial state distribution Po. The state transition function is P and P(s'|s, a) represents the probability of transitioning to state s' from (5)
by taking action e (a ... (N Expert i's reward function is rg S x A - R and the
2

---

experts are cooperative, i.e., rg No (6) The cost function of expert i is (1) Li=i"E "E"
c ) 2f0)
where (() SS x A + 00, d11" is an dimeennnii cost feature vector, d1 is a bounded constant, and wg (R) R is the weight. The cost function of all the experts is cg Em (1) Expert i's policy "g (a!*)s) represents the probability of expert taking action (++) at state and the joint policy of all the experts (T(a))) - II, (66) (a(0))) ss. We define J (=) _ F3,, o (rrr(rr, At) as the expected cumulative reward under policy where the initial state is drawn from Po and Jeg (T) - B 7 (S, As)] as the expected cumulative cost. The experts' policy TE wants to maximize Jrg (T) subject to Jee (T) z b where b is the budget. Following 9
19 we study
hard constraints (i.e., b = 0). These experts use TE to demonstrate Nr trajectories (clol at each online iteration n where each trajectory (m) - =) (m). ab (m).
(rl (m), ax (n) is state-action sequence of all the experts. This distributed online data style can also be found in [2]
Learners. There Nr. learners where each learner v knows (7, T, (6)(1) ) // (1)) and (1) is a demonstration observed by learner v at online iteration n. Each learner wants to use communications to learn the cost functions by estimating WE - )T ..... (w TTT and reward functions using parameterized models [rate)
N, fi=1 where B(6) E RRd is dimeenisi... Here we relax the linear reward assumption [9] but keep its linear cost assumption because non-linear cost functions
can make the problem ill-defined (explained in Appendix).
Assumption 1. The reward function rg satisfies the following: Iro(s, a)l S C, l[Voro a))l S O, and Fo a)ll S for any (s, a) E S x A and any 0 where C, C, and C are positive constants.
Notice that Assumption D standard in RL
33 34
35
The communication network is modeled as time-varying directed graph G(n) & (V, where V (1.... ,N) .N²) nication links) at time n. The edge (u, o') E {()) means that learner e receives information from learner vf at time and (v, u) E E(n) for all 2 0. The adjacency matrix of the graph at time is ((n) A [w<le'I (n))u, RN, where Wllv'((n) of neighbors of learner at time n (To((n) - {v/ VI(v, v') E E()).
is the node (learner) set and E(n) S V V is the set of directed edges (commu-
if and only if (v, e') $ 8()). The set
There exists an integer B such that the graph (V, E()) U U.. + 1)) is strongly connected for all n 2 O.
Assumption 2.
The adjacency matrix (n)) has the following properties: (i) W(() = I and W(n)1 where is the column vector whose entries are all ones. (üi There is an (0, 1) such that W [1m] (n) 2 for all and Wplon) (n)on'(()) 2 e if (v, v') E E(n).
Assumption 3.
Notice that these two assumptions are standard in distributed learning 3 9
36
Figure [stows that the learners stand outside the MAS observing the se- quential data revealed by the ex- perts and collaboratively learn the re- ward functions and constraints, Each learner aims to learn the reward func- tions and constraints of all the ex- perts where (ivl and wlll are the re- ward and cost function parameter es- timates of all the experts learned by learner v.
MAS (rp-ce)
MA-BIRDS online terations)
Expert 1
Learner
Espeet
plici
dr
Experi
Learner
Figure I: Relation between experts and learners
Notions and Notations. Define 0 A [(0())).... (((NE)) and ra & ΣNN gon. We use ((r) to represent learner u's learned 6. Therefore, the dimension of each Ølvl is ENS d(i) Given a trajectory Ç 8o, ao.... ,s,,ar, the empirical cumulative reward under ro is (C) a Σi 7' at), the empirical cumulative cost feature is defined as ji({) A Et 7 ( a+) where &- 2 [((()) ..... (o(Ne))T]T. The expectation of cumulative cost feature under given policy is ((TT) A E3 IT (S,( ((S,),,)) A.)] and the expectation of cumulative reward r'g under
3

---

given policy क is (r. (T) _ E EE (St, The set of all stochastic policies is II where every E II satisfies T[als) 2 0 for any (s, E A and Sae (aass)da 1 for any S.
3 Problem Formulation
In MA-BIRDS, the learners collaboratively learn the experts' policy aE by estimating the reward function rg and cost function Cg, and each learner does not share its private data such local trajectory ((v) and local estimates Jr, (ç(vl) and (((lol). While it seems that learning a well-structured reward function is enough to prevent "bad" movements by assigning negative reward, we include a section (in Appendix) further discuss the benefits of learning both reward and cost functions.
Many IRL works [9 [1 24 37 have a bi-level learning structure where the outer level is to learn reward function and the inner level is to learn corresponding policy by solving an RL problem under the current learned reward function. Inspired by their bi-level structure, we formulate a bi-level optimization problem where the outer level is to learn reward function ro and the inner level is to find the cost function and policy corresponding to rg. In what follows, we first define the inner-level optimization problem and then introduce the bi-level optimization problem.
The inner-level optimization. Given learned reward function rø, the corresponding policy Tre is the optimal solution of the following constrained RL problem where the reward function is ro:
No
(((T)++ + Jro (T), s.t. ((T) = A(clo)
Tra
arg max FEII
where H(m) & ET Es,Al- In (Ag[S:) causal entropy [38] The constraint problem
cost feature expectation matching similar to the spirit of "feature expectation matching" in [[] 38)
However, the policy The is hard to get because problem ① is non-convex. A standard way to tackle this difficulty is dual methods (39), therefore, we introduce the dual function of problem ([]
No. ((c(o(())) where the dual variable G(w;; n) & max (TT) + Jro (T) + w T (u(TT) N. Σ is used to estimate wg- Notice that the dual function G(w; m. is convex in w (3
Lemma 1. The optimal solution of problem ① is the constrained soft Bellman policy Tw- (B and its parameter w² (0, n.) is the optimal solution of the dual problem min,, G(w; (w:;O,n)
The expression of constrained soft Bellman policy is in Appendix. Lemma 1 shows that Tw (0 Tre and w"(A n) arg min,, G(w;; 0, n). Therefore, we can solve problem by solving its dual problem. We use the dual problem be the inner-level problem where w" w'6,, n) is the learned cost function and (0,)))) is the learned policy corresponding to the current learned reward function rg-
The bi-level optimization. Given a reward function re, the inner-level problem arg min,, G(w;; 0 n) can find the corresponding cost function and policy. The outer level aims to learn via minimizing the following loss function over
L(0, wn (00,,"((,,,, (0, n), s.t. w² (0, = arg (0) where L(0, w (0,00000 (). n) & -Ni ET 7 In Th (o. (n)) (n)) (m)) is the negative log like- lihood of the trajectories (cll received time n under the policy nw" (8.n): 40 and to learn
arg min G(w; m))
(())(()) {(s (m), (m),a"") dd) (n)) (osss-- The likelihood function widely used in IRL
the reward function.
Notice that 2 requires all the demonstrations {c(=) (nt) Ne time However, each learner can only observe glol and formulate its local negative log likelihood function Li (0, wn (0, n), & ETT T² In T ( (e. (a.") (n)]s(" (n)) and local dual function (iv)(ws 0, n) - max H(T)
Σ N Glol. Jro (TT) + WT (p(TT) p(clol (n))). Notice that L NNz [!") and G Nr
As the demonstrations are streaming, we have a sequence of loss functions {L(-, w w. (,,),, n) m>) We use this sequence of loss functions to formulate an online learning problem and common problem for online learning is to minimize the regret: ΣN" L(0(n), (0(n), - L(O", ,w' (0" (0",n)) n),

---

which quantifies the difference of the accumulative losses between the learned parameter 0 and the best parameter #* in hindsight. However, it too challenging to minimize the regret in our case because is non-convex [22]. Therefore, we use local regret [22 23 which is widely used in online non-convex optimization. quantifies the general stationarity of a sequence of loss functions. In specific, given a sequence of loss functions (f(;))))))) m)),21, the local regret [22 23
at online iteration n. is defined
as } E Vf(((nn), n - =)ll² which quantifies the gradient norms of the average of previously received loss functions under the current learned parameter sr(n). The total local regret is defined as
the sum of the local regret at every online iteration n, i.e., >n || V
(rr((n), n i)I In
our case, we replace f with our loss function (2) and thereby formulate the local regret (1(4) which has distributed bi-level formulation. We want to minimize the local regret (3)
N ΣE
V (l ~ ((())) (0(n), i)11?
(3)
Nz
s.t. w (0(n), n) = arg min
c ((n).
(4)
The time window length is 1 < N and (0, w. i) i < 0 22 The outer-level problem
(3) is to learn the reward parameter 9 and the inner-level problem 4 is to learn the cost parameter w
given A. The learned policy is the constrained soft Bellman policy Tw; with parameters (f), w).
4 Algorithm and Performance Guarantee
This section consists of two subsections where the first one introduces an approximation method to solve the bi-level optimization problem (3-4) in a single loop and the second one introduces consensus-based method for the multiple learners to solve the problem a distributed way.
4.1 Approximation-barel single-loop method
In this part, we develop an approximation- gradient of the outer-level problem (3) but an approximation the gradient: (ii) solves the outer-level and inner-level problems in single loop. In the following analysis, for simple notations, we omit the time index n and imply that the analysis holds for all n.
single-loop method which (i) does not use the exact
Lemma 2. The problem min,, G(w; 8) has unique optimal solution w² (0) for any 0.
Since the inner-level problem (4) is unconstrained and w" (0) is its optimal solution, then we have VwG(ww" (0); 8) = 0. Taking derivative with respect to @ on both sides renders:
V G( (0):0) + Glw (0): (0)
Vw
M(0 ((),"(()))
where M(,ww) & VL(O.w (0)) = VoL -0 (0)) (0 wn
Then, using the chain rule, we have:
(0)).
(5)
At online iteration n. an intuitive way to solve the bi-level optimization problem 33-44) is to solve in
a double-loop way 99 26 28). In specific, the double-loop method first solves the inner-level problem (4) to find a close approximation of wt (0) and then uses the obtained result to get the gradient (5). thus solving the outer-level problem
However, it requires multiple gradient descent for the inner-level problem (4) to get get (0) before updating the decision variable the outer-level problem where each gradient descent of the inner-level problem needs to solve a constrained RL problem in our case. Therefore, the double-loop method is not suitable to be an online algorithm when the data is revealed in a fast speed. To design algorithm suitable for the online fashion, we adopt the spirit of [2 30 and solve the lever- and inner-level problems in a single loop. However, our method is not simple extension of [29]] 30 to online settings because they are centralized and require the inner objective function to be strongly convex but our problem does not have these properties.
In specific, at each online iteration, the decision variables of both the luter-level and inner-level problems update only once where the gradient of the inner objective function given in Lemma 3 For the outer-level problem, as w w"(0) is inaccessible, cannot get the exact gradient defined in
5

---

(5). Therefore, we propose the following gradient approximation whose derivation can be found in
Appendix: VL(0,w) w) = Nr Ei S.A (=t=o '' (ar A.)] - E Vo (c1ol), where Tw: is the
constrained soft Bellman policy with parameters (w, 0). Compared (5). this gradient approximation does not include the second-order term M00,w) w) and thus is much more computationally efficient. It is shown in Appendix that the approximation error VVL,0, (0)) VI will S Co Collw=(0) will where Cg is positive constant whose expression is in Appendix. Intuitively, as the inner decision variable w approaches w (0) in the learning process, this gradient approximation error can be sufficiently small.
Lemma 3. The gradient of Glvl (w:; () is p( fu((ll)) where Tw:0 is the constrained soft Bellman policy with parameters (0, w).
Lemma 4. The global likelihood function L(0, w) is CL-lipschitz continuous and CL- -mmomhoth in (0, w). where Ct and CL are positive constants.
4.2 Consensus-based distributed learning
In our distributed learning setting, each learner only knows its local information (e.g., L and Gl so that it cannot directly solve the problem (3-(44) Therefore, each learner up- dates the decision variables using the gradients of its local outer-level and inner-level objec-
tive functions and uses communications to collahoratively solve the problem 3 3 Similar to the global gradient approximation VI, w) learner v has its local gradient approximation: ()l)(( E 15 Voro (S,, As)] - Vorrg (clo)). Learner e uses samples to estimate ml V VoJr,(5)
(0,,w via (L,1 w) A Ej=1
PoJJo(((v)) where Ç² is generated by rolling out Tw; and ml( is the number of the samples. Moreover, learner v also uses the same Imle) samples to estimate (Giv 0) in Lemma via (cll m. 1f=1 A((²) - A(ç)t)).
Algorithm 1 Multi-agent behavior inference from distributed and streaming demonstrations
Input: (olo (1)) W (1) (n))
Output:
(NMM(N))))))))) Vo E V
1: for 1,....,, ,N do
2: for v E V do
3: Finds policy T (l) using soft Q-learning 41 or soft actor-critic
42
4: Simulates samples (0 using (w)v)( (n).
5: Receives (n), wnl (n) from the neighbors v' E N (f)) and observes (l))
6: will(n + +1) EN=, Wlov'l (n)alle a(n) (w (w))) (l))),))
7: glvl(n (n + 1) = EV= wlon (n)ol'1) 8(m) i= 1 (Bl (n), (m),
8: end for
9:
end for
In Algorithm 1, at online iteration n. each learner u sequentially executes the following two steps: (i) uses current reward and cost function parameters to get the corresponding policy and generate samples (Lines 3-4); (ii) communicates with neighbors and updates its parameters for both outer-level and inner-level problems
single loop using the samples generated in last step (Lines 5-7). In the update process (Lines 6-7), the first term (convex combination) encourages consensus among different learners and the second term (gradient) drives to the set of stationary points. Notice that even though soft Q-learning and soft actor-critic are designed for unconstrained RL, as shown in Appendix, we can revise them to approximate the constrained soft Bellman policy.
Theorem 1. Suppose Assumptions
2 hold. Let the step sizes a(n) n. and 3(n) 3 where n, 72 E (g) 1) and ā, B E (0, Nz (2C2 then for any u, o' V in Algorithm 1:
n
(consensus): [[0())(N) (N) < 0 Noा + eN), [[al)(() wlo" (N)]l S 0 Nuz + E (als) (M) (als)] (alss) < 0 Nमा + Nw +E where
and sup ( sup().))SxxA outputs the supremum value over S x A and the expression of E (0, 1) can be

---

found in Appendix. (decreasing average local regret): O N No + ) 2(
Σ E ET (L(Olo((n) (n),wlu((m), e)[l9] s
(sub-linear cumulative constraint violation): En= [ ce (To (lo)))))))) S O(NN + 1), where the expectation is taken over randomly demonstrated trajectories at each online iteration.
Theorem I shows that the learners will achieve consensus the reward and cost function parameters, and policy. The average local regret decreases to an upper bound ((Cr) /T. Notice that this upper bound has similar property with that in (2 23 (i) they both less that the uniform upper bound Of of the global loss function L when > 2: (ii) they are both diminishing if is dependent on n and ((n) = (1) [23]. The number of total outer gradient steps taken by each learner Algorithm is O(N) which is smaller than ( + (2) in 12 and ((N(²) in [23]. The reason of fewer gradient steps Algorithm is that is an online gradient descent algorithm, which does not require multiple gradient calls at each online iteration as sellow-the-leader based methods [22 23 do.
Moreover, if the reward functions linear in 20 21 have the following stronger result: Corollary If the reward functions are linear, the average difference of cumulative reward between the learned policy and expert policy diminishes: N E F[(Jrg
[[[Jr((Tto))))dd)) (Tw(e)()))))1))))) Jrg (TE)) s
O N
vt) for any V.
5 Simulations
This section shows that Algorithm I effective to both discrete and continuous environments. We use four centralized baselines for comparisons: (i) Behavior inference from centralized and streaming demonstrations (BICS): This is the centralized counterpart of MA-BIRDS where central learner obtains all the demonstrations at each online iteration. (ii) Follow the leader (FTL): This method method to solve online non-convex optimization problems where (near)-stationary solution of the sum of all the previous loss functions is found at each online iteration. As this method only solves single-level optimization problems, we revise it to a single-loop method to solve bi-level optimization problems. (iii) Double-loop method (DLM): This method extends D-ICRL [ to online centralized settings where the inner-level problem is first solved and then the result is used solve the outer-level problem. At each online iteration, DLM only updates the decision variable of the outer-level problem once. (iv) ME-greedy: This method is an online extension of [18] which assumes the access the ground truth reward and uses greedy method to estimate the constraints based on maximum entropy (ME) IRL [1I.
[2 uses gellowthhe-leadr-bee
5.1 Evasion from patrolled area
We consider the evader-patrolee setting (Fig- ure 2ap introduced in (21). The experts (El and E2) are the patrollers patrolling around the area and they aim to switch their posi- tions. They have four actions (i.e., moving up, down, left, and right) and need to avoid colli- sions with each other and the obstacles (i.e., constraints). The experts are programmed to follow the optimal policy. The learners (L.1 and L2) are the evaders who want to Iearn the behavior model of the experts in order to reach the goal without being caught. The red crosses in Figure straints and each state is colored according to the scaled visitation frequency.
1.0
A
Viltution Pergenn
66
X X X X X
X X
X
X
X
0.4
X X
X
X XXXXX X X
X X
X
X X
X XXXXXXX
X X X X X
X
X
0.2
X
X
X
X
X
(a) Ground truth environment
(b) Learned environment
2 represent the con-
Figure 2: Evader-patroller environment.
Figure 2b shows the results learned by Algorithm (each learner recovers same constraints). Two constraints are not recovered as the experts' policy will not change even these constraints are absent. Three constraints are falsely learned because the experts (optimal policy) do not visit those states but the learned policy (constraint soft Bellman policy) have high chance of visiting the states if the
7

---

states are not prohibited as the constrained soft Bellman policy has non-zero probability of choosing any action and this probability can be large if the corresponding action is not heavily penalized.
To reason about the performance of our algorithm, we use four metrics: false positíve rate (FPR), false negative rate (FNR), constraint violation rate (CVR), and success rate (SR). The FPR 18 is the proportion of learned constraints that are not the ground truth constraints, FNR is the proportion of the ground truth constraints that are not learned, CVR introduced in [19] the percentage of the learned policy violating any constraint, and SR is the percentage of the learned policy reaching the destinations and avoiding collisions.
2:4
633
06
1.9
0.4
32
642
(a) FPR (lower is better)
(b) FNR (lower is better)
(c) CVR (lower is better)
(d) SR (higher is better)
L1
L2
BICS
.... FTL
DLM
ME-greedy
Figure 3: Algorithm performance. The LI and L2 are the distributed learners in MA-BIRDS.
Figure 3 shows that Algorithm is on par with and even outperforms the baselines even it is distributed and does not have the access to the ground truth reward. For the baselines, the centralized learners receive two demonstrations at each online iteration. We can see that the mrddient-based methods (i.e., MA-BIRDS, BICS, FTL,, and DLM) have much better performance than the greedy- based method (i.e., ME-greedy). The reason is that the greedy-based method can only learn one constraint at each online iteration while the gradient- based methods can learn multiple constraints at each online iteration because the gradient-based methods update w which works on all the possible constraints indicated by the cost feature vector Φb
Table I: Performance comparisons. Here, D means distributed and NATR means access to the (ground truth) rewards.
NATR
FPR
FNR
CVR
SR
MA- BIRDS
0.053 0.008
0.013 0.013
0.040 + 0.010
0.960 + 0.010
L2
4
0.053 = 0.008
0.013
0.045 0.015
0.955
0.015
BICS
0.038 0.019
4003+000013
0.010 + 0.005
0.960 + 0.005
FTL
0.047
0.009
0.032
0.032
0.030 + 0.010
0.970 = 0.010
DLM
X
0.050
+ 0.009
0.022 + 0.022
0.015 + 0.005
0.985
+ 0.005
MB-greedy
0.019 0.000
0.753 = 0.000
1.000 = 0.000
0.000 = 0.000
Table shows the final results after the 40 demonstrations are revealed. Notice that even if the gradient-basee based methods have different results in FPR and FNR, they achieve similar performance in CVR and SR. The reason is that the different constraints they learn will not affect the learned policy as those constraints are either blocked by other constraints or occupy the states that the experts will barely visit (as shown Figure 2b).
Moreover, to show that MA-BIRDS is suitable for online learning when the streaming data ar- rives at fast speed, we propose the following three metries: scaled time per online iteration (STPOI), 50% SR scaled time (50% ST), and 90% SR scaled time (90% ST). The STPOI is the scaled time that an algorithm needs to fin- ish the computation of an online iteration, 50% ST is the scaled time that an algorithm needs to reach 50% SR, and 90% ST the scaled time to
Table 2: Computation time comparisons.
STPOI
50% ST
90% ST
L1
1.000
1.000
1.000
L22
1.000
1.000
1.000
BICS
1.157
1.155
1.158
FTL.
7.500
3.753
3.769
DLM
7.482
3.740
7.481
ME-greedy
63.615
> 318.075
97.869
reach 90% SR. We use scaled time instead of actual time because actual time varies a lot on different
8

---

hardwares and different problems. The time is scaled in the way that the fastest algorithm has scaled time 1.000.
Table 2 shows that MA-BIRDS and BICS are much faster than the baselines in each online iteration, and thus faster than BICS in each online iteration because the centralized learner needs to process two new demonstrations each online iteration while each distributed learner only needs process one. Moreover, we can see that MA-BIRDS achieves 50% and 90% SR with the shortest time.
suitable for the online setting with fast streaming data. The MA-BIRDS is slightly
5.2 Drone motion planning with obstacles
In this example, we analyze MA-BIRDS real- world problem with continuous state and action spaces introduced in 19]. We build simulator in Gazebo (Figure (4)) where we (humans) control the drones their diagonal doors while avoid- ing collisions. We reveal each of the four learners demonstration each online iteration. In this experiment, the learners are the computers record- ing the demonstrations of the experts (humans) controlling the drones. As the state and action spaces are continuous, the potential constraints can also be continuous. Therefore, we cannot use the metrics FPR and FNR, and we cannot use the baseline ME-greedy. As ME-greedy is designed for discrete state-action space, we replace with ME-gradient [19] which extends ME-greedy continuous settings where a cost function learned using a gradient-based method. Similar to ME-greedy, ME-gradient is centralized and assumes access to the ground truth reward. Figure 4b shows the learned constraints on which the learners reach consensus and the trajectories the learned policy. Each of the four trajectories is generated by one of the four learners L1-L4. Each trajectory consists of the paths of the two drones (i.e., a red path and a blue path).
XX X
(a) Gazebo simulator
(b) Learned environment
Figure 4: Drone motion planning with obstacles.
Table 3: Performance and computation time comparisons (drone motion planning).
NATR
CVR
SR
STPOI
50% ST
90% ST
L1
0.025 0.025
0.974 + 0.025
1.000
1.000
1.000
L2
0.030 0.010
0.970 0.010
1.000
1.000
1.000
133
0.025 0.025
0.973 + 0.025
1.000
1.000
1.000
L4
/
0.025 = 0.025
0.972 1 0.015
1.000
1.000
1.000
BICS
0.015 0.015
0.979
0.020
1.029
1.025
1.027
FTI.
0.015 + 0.010
0.981
+ 0.018
10.481
7.860
5.240
DLM
0.020 0.015
0.975
0.015
9.658
6.767
6.837
ME-ggadient
0.013 - 0.013
0.980 0.018
1.013
1.010
1.012
Table together with Table shows that MA-BIRDS and BICS can reach the same good performance with the baselines and much shorter time or have fewer requirements. In specific, compared to
FTL (22), MA-BIRDS only requires about 20% the time to reach the same performance and is more than six times faster each iteration. Compared to DLM ( MA-BIRDS only requires about 15% of the time to reach the same performance and is also more than six times faster in each iteration. Compared to ME-gradient, MA-BIRDS reach the same performance within the same amount of time even if it is distributed and has no access to the ground truth reward.
Discussion and future work
We propose MA-BIRDS, the first IRL framework that is effective learning multi-agent behaviors from distributed and streaming demonstrations under continuous and discrete environments. We formulate a distributed online bi-level optimization problem and propose a fast distributed online gradient descent single-loop algorithm with theoretical guarantees that is suitable to online settings.

---

Experimental results show that MA-BIRDS is effective in both continuous and discrete environments. Despite its benefits, one limitation is the assumption of linear cost functions. We will explore approaches to relax this assumption in the future.
Potential negative social impact. Since MA-BIRDS infer the experts' behaviors, potential negative social impact may occur if the learners are malicious. Take the evader-patroller setting as an example; the patrollers could be safeguards or park rangers, and the evaders could be poachers. The malicious poachers may use MA-BIRDS to escape. To avoid this situation, the experts should take additional strategies such as regularly demonstrating misleading behaviors so that MA-BIRDS will leam wrong behavior model of the experts.
7
Acknowledgements
This work is partially supported by the National Science Foundation through grants ECCS 1846706 and CNS 1830390. We would like to thank the reviewers for their insightful and constructive suggestions.
10

---

References
[1] Stone and M. Veloso, "Multiagent systems: A survey from a machine learning perspective." Autonomous Robots, vol. 8, no. pp. 345-383, 2000.
[2] J. Verbraeken, M. Wolting, J. Katzy, J. Kloppenburg, T. Verbelen, and J. S. Rellermeyer, "A survey on distributed machine learning," ACM Computing Surveys, vol. 53, no. 2, pp. 1-33, 2020.
[3] Luo, H. Xiong, K. Lü, and Shi, "Distributed classification in peer-to- teeetrr-eerreeeee networks," in ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 968- 976, 2007.
[4] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. Arcas, "Communication learning of deep networks from decentralized data," in Artificial Intelligence and Statistics, pp. 1273-1282, 2017.
[5] M. Bendechache and M.-T. Kechadi, "Distributed clustering algorithm for spatial data mining," in IEEE International Conference on Spatial Data Mining and Geographical Knowledge Services, pp. 60-65, 2015.
[6] A. Bhaskara and M. Wijewardena, "Distributed clustering via Ish based data partitioning," in International Conference on Machine Learning, pp. 570-579, 2018.
[7] L. Espeholt, H. Soyer, R. Munos, K. Simonyan, V. Mnih, T. Ward, Y. Doron, V. Firoiu, T. Harley, I. Dunning, et al., "Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures," " in International Conference on Machine Learning, pp. 1407-1416, 2018.
[8] Y. Wang, M. Damani, P. Wang, Y. Cao, and G. Sartoretti, "Distributed reinforcement learning for robot teams: A review." Current Robotics Reports, vol. 3, no. 4, pp. 239-257, 2022.
[9] S. Liu and M. Zhu, "Distributed inverse constrained reinforcement learning for multi-agent systems," in Advances in Neural Information Processing Systems, vol. 35, pp. 33444-33456. 2022.
[10] P. Abbeel and A. Y. Ng, "Apprenticeship learning via inverse reinforcement learning," in International Conference Machine Learning, pp. 1-8, 2004.
[11] B. D. Ziebart, L. Maas, J. A. Bagnell, and A. K. Dey, "Maximum entropy inverse rein- forcement learning," in National Conference on Artificial intelligence, vol. 8, pp. 2008.
[12] Zeng, Li, A. Garcia, and M. Hong. Bexximum--ikelihoodd inverse reinforcement learning with finite-tima timee-timeeee guarantees," Advances in Neural Information Processing Systems, vol. 35, pp. 20122-10135,200 2022.
[13] S. Zeng, M. Hong, and A. Garcia, "Structural estimation of markov decision processes in high-dimensional state space with finite-time guarantees," arXiv preprint arXiv:2210.01282. 2022.
[14] S. Zeng, Li, A. Garcia, and M. Hong. "Understanding expertise through demonstrations: maximum likelihood framework for offline inverse reinforcement learning." arXiv preprint 2xXi:23322.0755: 2023.
[15] T. S. Reddy, V. Gopikrishna, G. Zaruba, and M. Huber, "Inverse reinforcement learning for decentralized non-cooperative multiagent systems," in IEEE International Conference on Systems, Man, and Cybernetics, pp. 1930-1935, 2012.
[16] S. Natarajan, G. Kunapuli, K. Judah, P. Tadepalli, Kersting, and Shavlik, "Multi-agen inverse reinforcement learning," in International Conference on Machine Learning and Applica- tions, pp. 395-400, 2010.
[17] I.. Yu, Song, and Ermon, "Multi-agent adversarial inverse reinforcement learning," in International Conference Machine Learning, pp. 7194-7201, 2019.

---

[18] D. R. Scobee and S. S. Sastry. "Maximum likelihood constraint inference for inverse reinforce- ment learning," in International Conference on Learning Representations, 2019.
[19] S. Malik, U. Anwar, A. Aghasi, and A. Ahmed, "Inverse constrained reinforcement learning." " in International Conference on Machine Learning, pp. 1390-7339, 2021.
[20] N. Rhinehart and K. M. Kitani, "First-person activity forecasting with online inverse rein- foreement learning," in IEEE International Conference on Computer Vision, pp. 3696-3705, 2017.
[21] S. Arora, P. Doshi, and B. Banerjee, "Online inverse reinforcement learning under occlusion," " in International Conference on Autonomous Agents and Multiagent Systems, pp. 1170-1177 1178, 2019.
[22] E. Hazan, K. Singh, and C. Zhang, "Efficient regret minimization in non-convex games," in International Conference on Machine Learning, pp. 1433-1441, 2017.
[23] N. Hallak, P. Mertikopoulos, and V. Cevher, "Regret minimization in stochastic non-convex learning via a moximall-gadiees approach,"" in International Conference on Machine Learning. pp. 4008-4017, 2021.
[24] N. Das, S. Bechtle, T. Davchev, D. Jayaraman, A. Rai, and F. Meier, "Model-based inverse reinforcement learning from visual demonstrations," in Conference on Robot Learning, pp. 1930- 1942, 2021.
[25] S. Xu and M. Zhu, "Efficient gradient approximation method for constrained bilevel opti- mization," Proceedings of the AAAI Conference on Artificial Intelligence, vol. 37, no. 10, pp. 12509-12517, 2023.
[26] Ghadimi and M. Wang. "Approximation methods for bilevel programming." arXiv preprint arXiv: arXiv:1802.00 1802.02246, 2018.
[27] N. Couellan and W. Wang, "On the convergence of stochastic bi-level gradient methods," Optimization, 2016
[28] K. Ji, J. Yang, and Liang, "Bilevel optimization: Convergence analysis and enhanced design," in International Conference on Machine Learning, pp. 4882-4892, 2021.
[29] M. Hong, H.-T. Wai, Z. Wang, and Z. Yang, "A two-timescale framework for bilevel optimiza- tion: Complexity analysis and application to actor-critie," arXiv preprint arXiv:2007.05) 20020007755700 2020.
[30] T. Chen, Y. Sun, Q. Xiao, and W. Yin, "A single-timescale method for stochastic bilevel optimization," in International Conference on Artificial Intelligence and Statisties, pp. 2466- 2488, 2022.
[31] E. Altman and A. Shwartz, "Constrained markov games: Nash equilibria," in Advances in Dynamic Games and Applications, pp. 213-221, 2000.
[32] D. Yuan, A. Proutiere, and G. Shi, "Distributed online optimization with long-term constraints," IEEE Transactions on Automatic Control, vol. 67, no. 3. pp. 1089-1104, 2021.
[33] L. Wang, Q Cai, Z. Yang, and Z. Wang, "Neural policy gradient methods: Global optimality and rates of convergence," " International Conference on Learning Representations, 2019.
[34] H. Kumar, Koppel, and A. Ribeiro, "On the sample complexity of actor-critic method for reinforcement learning with function approximation," arXiv preprint arXiv: 191.02991. 2019.
[35] K. Zhang, A. Koppel, H. Zhu, and T. Basar, "Global convergence of policy gradient methods to (almost) locally optimal policies," SIAM Journal on Control and Optimization, vol. 58, no. pp. 3586-3612, 2020.
[36] K. Zhang, Z. Yang, H. Liu, T. Zhang, and T. Basar, "Fully decentralized multi-agent rein- forcement learning with networked agents," in International Conference on Machine Learning, pp. 5872-5881, 2018.
12

---

[37] S. Arora and P. Doshi, "A survey of inverse reinforcement learning: Challenges, methods and progress," Artificial Intelligence, vol. 297, p. 103500, 2021.
[38] B. D. Ziebart, A. Bagnell, and A. K. Dey, "Modeling interaction via the principle maximum causal entropy," in International Conference on Machine Leurning, pp. 1255-1262 2010.
[39] S. P. Boyd and L. Vandenberghe, Convex Optimization. Cambridge university press, 2004.
[40] B. D. Ziebart, Modeling Purposeful Adaptive Behavior with the Principle of Maximum Causal Entropy. PhD thesis, Carnegie Mellon University, 2010.
[41] T. Haarnoja, H. Tang, P. Abbeel, and S. Levine, "Reinforcement learning with deep energy-based policies." in International Conference on Machine Learning, pp. 1352-1361, 2017.
[42] Haarnoja, A. Zhou, P. Abbeel, and S. Levine, "Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor," in International Conference on Machine Learning, pp. 1861-1870, 2018.
13


Reviews:
[{"review_id": "a0B7s2MItH", "reviewer": "Reviewer_UrMu", "summary": "\nThe paper tries to infer the behaviors of multiple interacting experts by estimating their reward functions and constraints. In their approach, the distributed demonstrated trajectories are sequentially revealed to a group of learners. The problem is set up as a distributed online optimization problem with 2 levels - the outer-level estimates the reward functions  - the inner-level problem learns the constraints and corresponding policies. The solution is called MA-BIRDS - multi-agent behavior inference from distributed and streaming demonstrations algorithm. The results guarantee that 1) the distributed learners achieve consensus on reward functions, constraints, and policies; 2) the average local regret (over N online iterations) decreases, and the cumulative constraint violation increases sub-linearly. A couple of examples illustrate that the approach appears to work well.", "questions": "Are the experts of similar capability? The more interesting case seems to be when they have varied capability and deciding amongst which to use of them?\n\nCan the authors comments on the tightness of the bounds in the contribution statement - especially in the numerical results section?", "limitations": "some discussion", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The problem is very interesting - the approach seems sound, and the results (e.g. the 1) are solid with extensions of the SOA (e.g. [20-21]).\n\nThe simulation results compare to a good set of baselines", "weaknesses": "The learned results (constraints) in Figure 2 seems similar, but the visitation frequencies (colors) seems quite different - pls explain. Is the goal being learned as a constraint in fig 2(b) correct?\n\nThe results (fig 3) showed the perf compared to several centralized algorithms, but it would be good to provide evidence that the distributed learning problem is actually hard - ie that a naive distributed learner would fail in this case - would lead to strong results.\n\nFor the drone example, with only 2 goals and a demonstration presumably showing the path to the appropriate goal, it is difficult to see why this problem is hard? Pls provide more evidence that this is a difficult problem that you are succeeding on.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive review. We appreciate that you find this work interesting and sound, and we believe that this discussion will contribute to a better paper. We address your comments below:\n\n**Weakness 1: The learned results (constraints) in Figure 2 seems similar, but the visitation frequencies (colors) seems quite different - pls explain. Is the goal being learned as a constraint in fig 2(b) correct?**\n\n**Answer**: The major reason of these different visitation frequencies is that the experts and learners follow different kinds of policies. The experts are programmed to follow the optimal policy (mentioned in line 290) while the learners use constrained soft Bellman policy (mentioned in Lemma 1). The expression of the constrained soft Bellman policy is included in Appendix (Subsection 8.1). From the expression, we can see that the constrained soft Bellman policy is more stochastic, e.g., it has non-zero probability of choosing any action and the probability of choosing two actions which have similar $Q$ values is similar. However, the optimal policy will only choose actions that have the highest $Q$ value. Therefore, it is expected that the constrained soft Bellman policy will lead to a more uniformly distributed visitation frequency. This aligns with the results in Figure 2. In Figure 2, the yellow states are must-visit states because they occupy the only exit of each corner. For those states that are not must-visit states, we can see that they are all green in Figure 2(b), i.e., the visitation frequency is more uniformly distributed, because the learners use the constrained soft Bellman policy. In practice, we use $\\epsilon$-greedy policy for the experts and that's why some states that are not likely visited also have non-zero visitation frequency in Figure 2(a).  \nThe goal is to learn both the reward function and constraints so that the learners can behave like the experts. We use the visitation frequency to show that the learners can reach the destinations and avoid the obstacles just like the experts.\n\n**Weakness 2: The results (fig 3) showed the perf compared to several centralized algorithms, but it would be good to provide evidence that the distributed learning problem is actually hard - ie that a naive distributed learner would fail in this case - would lead to strong results.**\n\n**Answer**: Thank you for pointing this out. We include the comparison result between MA-BIRDS learners and naive distributed learners of the evader-patroller experiment in the newly uploaded PDF file (Figure 1). The naive learners only know local data and do not cooperate with each other. From the figure, we can see that the learners of MA-BIRDS perform much better than the naive distributed learners. The reason is that the naive distributed learners do not leverage communications to obtain information in the data received by the other learner while the distributed learners of MA-BIRDS can utilize communications to gain the information of the global data.\n\n**Weakness 3: For the drone example, with only 2 goals and a demonstration presumably showing the path to the appropriate goal, it is difficult to see why this problem is hard? Pls provide more evidence that this is a difficult problem that you are succeeding on.**\n\n**Answer**: We agree that given a demonstrated trajectory that shows the path to the goal, it is easy for humans to know the goal position. However, the learners aim to learn the reward function which includes information more than the goal position. For example, the reward function can capture the quantitative preference of the experts such as minimum time to reach the goal. This leads to the learned reward function giving significant large reward at the goal because the sooner the learners reach the goal, the longer they can stay at the goal and thus the larger reward they get (given that the time horizon $T$ is fixed). The learned reward function also captures qualitative preference such as do not stay too close to the obstacles and do not incline to go through the area between the obstacles. These result in the learned reward function giving lower reward in the area between the obstacles and the area around the obstacles. We can see that the learned trajectories in Figure 4(b) use short paths to the goal, stay a certain distance from the obstacles, and do not go through the area between the obstacles.\n\n**Q1: Are the experts of similar capability? The more interesting case seems to be when they have varied capability and deciding amongst which to use of them?**\n\n**Answer**: Yes, you are correct. The experts have similar capability. The situation you mention is interesting and we will investigate on this in future works.\n\n**Q2: Can the authors comments on the tightness of the bounds in the contribution statement - especially in the numerical results section?**\n\n**Answer**: Mentioned in lines 260-267, the bound has similar properties with the tight local regret bound proved in the literature [A1,A2]. We will add this discussion in the contribution statement. For the numerical section, instead of choosing a fixed time window length, the time window length $l$ increases with the number of online iterations (i.e., $l(n)=n$) (line 278). Therefore, the bound of the local regret diminishes to zero (mentioned in lines 263-264). Then the algorithm becomes a no-regret algorithm and the numerical results show that the learners can achieve similar performance to the experts when the number of online iterations increases.\n\n[A1] E. Hazan, K. Singh, and C. Zhang, \"Efficient regret minimization in non-convex games,” International Conference on Machine Learning, pp. 1433–1441, 2017.\n\n[A2] N. Hallak, P. Mertikopoulos, and V. Cevher, “Regret minimization in stochastic non-convex learning via a proximal-gradient approach,” International Conference on Machine Learning, pp. 4008–4017, 2021."}, {"review_id": "EeEwStsM42", "reviewer": "Reviewer_grYB", "summary": "The paper introduces MA-BIRDS, an Inverse Reinforcement Learning (IRL) framework designed to effectively learn multi-agent behaviors from distributed and streaming demonstrations in continuous and discrete environments. The authors initially frame the problem as a distributed online bi-level optimization problem. They subsequently present a fast distributed online gradient descent single-loop algorithm, accompanied by theoretical guarantees. To showcase the efficacy of MA-BIRDS, the paper includes a set of experiments conducted in both continuous and discrete environments.", "questions": "1. In reference to line # 43-44: Is it true that there is no existing work on online IRL with non-linear rewards? On a quick search here [1] is a work that works with quadratic rewards in online IRL. \n\n2.  For better readability, I would suggest replacing 'state-of-the-arts' with 'state-of-the-art works' throughout the paper. \n\n3. In reference to line # 66-67: What are the exact challenges in extending single-loop bi-level centralized optimization to de-centralized case? \n\n4. What is `N' in line #76?\n\n5. Is the paper the first one to propose a  'distributed online bi-level optimization problem'?\n\n6. What are downstream applications to the problem setup discussed in para 3 of Introduction? Is the main challenge in ICRL estimating local rewards with streaming data. What are the exact challenges in this? \n\n7. In general in dual optimization implementations, inner or outer optimization problems are not solved fully, how important is it to MA-BIRDS to solve any or all of the optimization problems fully? \n\n[1] Self, R., Abudia, M., & Kamalapurkar, R. (2020, July). Online inverse reinforcement learning for systems with disturbances. In 2020 American control conference (ACC) (pp. 1118-1123). IEEE.", "limitations": "The authors include just one limitation about cost functions being linear. It would be nice to add a more comprehensive literature review. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper demonstrates a commendable effort in addressing the problem at hand and provides a satisfactory solution.", "weaknesses": "- The problem being tackled seems incremental over the existing literature on distributed inverse constrained reinforcement learning. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback. We believe that this discussion will help improve our paper. We address your comments below:\n\n**Weakness: The problem being tackled seems incremental over the existing literature on distributed inverse constrained reinforcement learning (D-ICRL).**\n\n**Answer**: As discussed in the introduction, this paper extends D-ICRL to online learning, so the problem is incremental. However, the algorithm and analysis are substantially different from D-ICRL. Mentioned in lines 41-42, we include a section in Appendix to discuss our improvements from D-ICRL. In Appendix (section 7), we point out that our algorithm improves D-ICRL in almost every aspect, including weaker assumption, simpler and more efficient algorithm, much stronger theoretical and empirical results. Due to space limit, we cannot elaborate it here and please refer to Appendix (section 7) for details.\n\n**Q1: In reference to line 43-44: Is it true that there is no existing work on online IRL with non-linear rewards? On a quick search there is a work that works with quadratic rewards in online IRL.**\n\n**Answer**: We appreciate that you provide this reference and we will revise the statement in lines 43-44. We would like to add this reference and include a more comprehensive literature review.\n\n**Q2: For better readability, I would suggest replacing 'state-of-the-arts' with 'state-of-the-art works' throughout the paper.**\n\n**Answer**: Thanks for your advice, we will use \"state-of-the-art works\" instead.\n\n**Q3: In reference to line 66-67: What are the exact challenges in extending single-loop bi-level centralized optimization to de-centralized case?**\n\n**Answer**: It is very insightful that you point this out. The challenge mainly comes from the fact that the distributed learners do not know the global demonstration set but need to solve a global problem (3)-(4). For example, a key step of solving bi-level optimization problems is to compute the hyper-gradient (5). The hyper-gradient (5) contains an inverse-of-Hessian term $[\\nabla_{\\omega\\omega}^2G]^{-1}$ (see the expression of $M(\\theta,\\omega)$ in line 205) that requires global demonstrations to compute because the function $G$ is global. A centralized learner can directly compute $[\\nabla_{\\omega\\omega}^2G]^{-1}$ since it knows the global data. However, it is difficult for distributed learners to compute this term since $[\\nabla_{\\omega\\omega}^2G]^{-1}$ is extremely hard to decompose.\n\n**Q4: What is `N' in line 76?**\n\n**Answer**: $N$ is the number of online iterations. We use $n$ to represent the general online iteration index and $N$ to represent a specific number of total online iterations.\n\n**Q5: Is the paper the first one to propose a 'distributed online bi-level optimization problem'?**\n\n**Answer**: To the best of our knowledge, there is no previous work on distributed online bi-level optimization.\n\n**Q6: What are downstream applications to the problem setup discussed in para 3 of Introduction? Is the main challenge in ICRL estimating local rewards with streaming data. What are the exact challenges in this?**\n\n**Answer**: Our problem setup is to learn reward functions and constraints from distributed and streaming demonstrations. There are plenty of downstream applications including inferring pedestrians' behaviors from their ongoing daily routines. The pedestrians have their destinations (i.e., reward functions) and some implicit constraints such as avoiding collision with obstacles. The demonstration data could be distributed since there could be multiple cameras recording the pedestrians' behaviors and the demonstrations are streaming given that the behaviors are recorded every day. Other applications include autonomous vehicles learning driving styles of humans from everyday observations and defenders learning the attacker's model from regular attacks in security, etc. The main challenge of our problem is to design fast and efficient algorithms that can learn reward functions and constraints from streaming data. Otherwise, the computation may not be finished before the next data arrives. Current works, e.g., double-loop methods or follow-the-leader methods, fail to update quickly at each online iteration. Therefore, we propose an online gradient descent single-loop algorithm (lines 53-55 and 64-65) that is much faster than baselines (see Tables 2-3).\n\n**Q7: In general in dual optimization implementations, inner or outer optimization problems are not solved fully, how important is it to MA-BIRDS to solve any or all of the optimization problems fully?**\n\n**Answer**: MA-BIRDS does not need to fully solve the outer or inner problem at any online iteration. In fact, this is the major contribution of MA-BIRDS. Fully solving the inner or outer problem will lead to more computation time, which is not suitable to be an online learning algorithm if the data arrives in a fast speed. MA-BIRDS only partially solves the inner and outer problems at each online iteration but we can still reach theoretical guarantees. More importantly, in the experiment, the baseline FTL fully solves the outer problem and the baseline DLM fully solves the inner problem. The empirical results show that MA-BIRDS is much faster than these two baselines in each online iteration and reaches the same good performance in a much shorter time (Tables 2-3).\n\n**Limitation: The authors include just one limitation about cost functions being linear. It would be nice to add a more comprehensive literature review.**\n\n**Answer**: We appreciate that you suggest a more comprehensive literature review. We will add more discussions on the related works, including online IRL, online non-convex optimization, and bi-level optimization. In specific, we will add the non-linear online IRL works and discuss our distinctions from them. For non-convex optimization and bi-level optimization, we will clearly mention that our work is the first one to study distributed online bi-level optimization."}, {"review_id": "UvvDb5SjO7", "reviewer": "Reviewer_QLML", "summary": "A new type of the MA-IRL problem is proposed and analysed in this paper, which features online learning, distributed demonstrations and constraints independent of rewards. To tackle challenges resulting from these features, the authors design a novel algorithm called MA-BIRDS that utilises a single-loop mechanism to learn the underlying reward functions, constraints and policies. Due to the decentralised nature, the local regret is used to approximate the actual gradient. Authors upper bound the local regret at an ideal case and provide a theoretical guarantee on the achievement of a consensus over the learned rewards, policy and costs among all agents. Fruitful experiments are executed that validate the effectiveness of the proposed algorithm.", "questions": "N/A", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper contributes a novel IRL algorithm that is adapted to streaming data and distributed multi-agent systems. The single-loop update of rewards and policies sets this work apart from the others in the literature in the sense that it can considerably alleviate the time pressure and is hence suitable for online scenarios. Theoretical results on convergence and consistency pin the proposed algorithm deeply down to reliability.", "weaknesses": "Although I agree that the single-loop update of rewards and policies is a significant contribution to the literature of IRL, I still doubt the online efficiency of the proposed algorithm because the soft-Q learning/soft actor-critic is involved in each round of updates. As far as I know, soft-Q learning or soft actor-critic is not a kind of fast-converging RL algorithm, or at least they cannot always guarantee fast convergence. This would potentially bring some negative effects on online efficiency when the problem scale is large or the online data comes with a complex structure. I would like to increase the score if the authors can make a discussion on this and/or provide some empirical evidence to clarify this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive and insightful review. Discussing this point will help us improve and clarify our work. We address the comment below.\n\n**Weakness: Although I agree that the single-loop update of rewards and policies is a significant contribution to the literature of IRL, I still doubt the online efficiency of the proposed algorithm because the soft-Q learning/soft actor-critic is involved in each round of updates. As far as I know, soft-Q learning or soft actor-critic is not a kind of fast-converging RL algorithm, or at least they cannot always guarantee fast convergence. This would potentially bring some negative effects on online efficiency when the problem scale is large or the online data comes with a complex structure. I would like to increase the score if the authors can make a discussion on this and/or provide some empirical evidence to clarify this.**\n\n**Answer**: It is very insightful of you to point out that the reinforcement learning step (e.g., soft Q learning or soft actor-critic) can be slow, thus resulting in a slow reward and cost update at each online iteration. This is indeed a problem for many IRL [C1,C2,C3] and online IRL [C4,C5] works since it is typical to require to solve an RL problem at each iteration for reward update. However, this problem can be alleviated by two ways.\n\nThe first one is warm start. In specific, at each online iteration, we need to compute the policy corresponding to the new reward and cost functions. Instead of computing the policy from random initialization, we use the results of the last online iteration as the initialization of this online iteration. Take soft actor-critic as an example, we can use the learned parameters of the policy net and value net at last online iteration as the initialization of the policy net and value net at current online iteration. Intuitively, if the reward and cost functions between two consecutive online iterations are close, it is expected that the corresponding policy and value nets should have similar parameter values. Therefore, the warm start can speed up the convergence of RL since it provides a good initialization. Moreover, The distance of reward parameters and the distance of cost parameters between two consecutive online iterations are indeed close in our situation. Since the step sizes $\\alpha(n)$ and $\\beta(n)$ are diminishing and the gradient of $L$ and $G$ are bounded (proved in Lemma 8 and lines 148-149 in Appendix), the distance of reward parameters and the distance of cost parameters between any consecutive online iterations will diminish. Therefore, the RL step will become faster and faster when the online iteration index $n$ increases. We include a figure (Figure 2) in the newly uploaded PDF file to show the scaled computation time of each online iteration for the evader-patroller experiment. From the figure, we can see that the warm start can significantly accelerate the RL process.\n\nThe second one is to use only one-step policy update at each online iteration. This idea has been proved to be effective in the offline setting [C6]. In specific, given the new reward and cost function at each online iteration, we only perform one-step policy update from the policy in the last online iteration instead of computing the corresponding constrained soft Bellman policy. The one-step policy update could be the policy update in soft Q learning or actor update in soft actor-critic. Since we only update the policy by one step instead of fully solving an RL problem, it will be much faster. Theoretically, this idea can work because of two-timescale stochastic approximation where the policy updates in a faster timescale and the reward and cost update in a slower timescale. The policy update is faster because it converges linearly under fixed reward and cost functions [C7] while the reward and cost updates are slower given that $\\alpha(n)\\propto n^{-\\eta_1}$ and $\\beta(n)\\propto n^{-\\eta_2}$ where $\\eta_1,\\eta_2\\in(\\frac{1}{2},1)$. Intuitively, since the policy update is faster than the reward and cost updates, the reward and cost parameters are \"relatively fixed\" compared to the policy. It is expected that the policy shall stay close to the corresponding constrained soft Bellman policy and at last converges to the corresponding constrained soft Bellman policy when $n$ increases.\n\n[C1] P. Abbeel and A. Y. Ng, “Apprenticeship learning via inverse reinforcement learning,” International Conference on Machine Learning, pp. 1–8, 2004.\n\n[C2] B. D. Ziebart, A. L. Maas, J. A. Bagnell, and A. K. Dey, \"Maximum entropy inverse reinforcement learning,” National Conference on Artificial Intelligence, pp. 1433–1438, 2008.\n\n[C3] S. Arora and P. Doshi, “A survey of inverse reinforcement learning: Challenges, methods and progress,” Artificial Intelligence, vol. 297, p. 103500, 2021.\n\n[C4] N. Rhinehart and K. M. Kitani, “First-person activity forecasting with online inverse reinforcement learning,” IEEE International Conference on Computer Vision, pp. 3696–3705, 2017.\n\n[C5] S. Arora, P. Doshi, and B. Banerjee, “Online inverse reinforcement learning under occlusion,”\nInternational Conference on Autonomous Agents and Multiagent Systems, pp. 1170–1178, 2019.\n\n[C6] S. Zeng, C. Li, A. Garcia, and M. Hong, “Maximum-likelihood inverse reinforcement learning with finite-time guarantees,” Advances in Neural Information Processing Systems, pp. 10122-10135, 2022.\n\n[C7] S. Cen, C. Cheng, Y. Chen, Y. Wei, and Y. Chi, \"Fast global convergence of natural policy gradient methods with entropy regularization,\" Operations Research, vol. 70, no. 4, pp. 2563–2578, 2022"}, {"review_id": "nkx4Z87Wof", "reviewer": "Reviewer_9ZLE", "summary": "The authors study the problem of uncovering the incentives and behaviors of a cooperative multiagent system (MAS) that is optimizing for an objective subject to constraints. The authors consider solving this as a distributed optimization problem where several learners observe separate trajectories of the MAS in parallel and infer the parameters of the MASs reward functions and policies. The learners periodically pool this information to arrive at a consensus. This problem is posed as a bi-level optimization problem where the inner problem of recovering a joint policy given a reward function is solved in the dual, and the outer problem is to learn the reward function via maximum likelihood estimation. The authors prove a consensus will be reached and give a convergence rate. They also prove the agreed upon policy enjoys sublinear regret as measured by constraint violation. The authors demonstrate their approach on two domains, a discrete evader-patroller domain and a continuous drone domain. MA-BIRDS is on par with prior centralized approaches (e.g, BICS) in terms of uncovering correct constraints and high performing policies but with slightly shorter runtimes.", "questions": "- Can you give intuition for why your theoretical convergence rates are independent of $N_L$?\n- One of the benefits of distributed learning is the ability to increase parallel computation to achieve faster learning. Did you vary $N_L$ at all for either experiment and can you include those results if you have them?", "limitations": "The evader-patroller setting suggests the proposed method could be used in a way that has negative societal impact. Typically, we want the patrollers (e.g., park rangers) to capture the evaders (e.g., poachers). Can you discuss this briefly?", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Given the complexity of the setting, I thought the authors did an excellent job explaining their setup and solution clearly. They clearly acknowledge prior work and explain their contribution to inferring the behaviors of an MAS with a *distributed*, *online* approach. They support their algorithmic development with theoretical analysis and run experiments comparing against several strong baselines.", "weaknesses": "I feel the paper could better motivate the *distributed* problem. The experiments show centralized approaches are nearly as fast and with similar, if not better performance. Distributed approaches can often take advantage of parallelism to achieve faster convergence at scale, but I did not see that reflected in the theoretical rates, nor did I see experiments testing this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive reviews. We believe that this discussion will help improve the paper. We address your comments below:\n\n**Weakness: I feel the paper could better motivate the distributed problem. The experiments show centralized approaches are nearly as fast and with similar, if not better performance. Distributed approaches can often take advantage of parallelism to achieve faster convergence at scale, but I did not see that reflected in the theoretical rates, nor did I see experiments testing this.**\n\n**Answer**: Thanks for mentioning the parallelism. The parallelism in our case may not significantly accelerate the learning. The reason is that the distributed learners only share the burden of data processing, which only consumes a small portion of the total computation time. Note that solving the RL problem (line 3 in Algorithm 1) consumes most of the computation time. Hence, distributed learning in our paper is not significantly faster than centralized learning because both learning methods need to solve an RL problem at each online iteration. This is consistent with the empirical results where the distributed learners are only slightly faster than the centralized learner at each online iteration.\n\nWe agree that parallelism can accelerate learning in some cases. For example, deep learning over a very large set of images [D1] where the global dataset is distributed to many local datasets and each learner only processes local data, computes the gradient using local data, and updates parameters via gradient descent in parallel. This kind of parallelism can significantly accelerate the learning because the major burden, i.e., processing the data and computing gradients using the data, is shared by the distributed learners. However, in our case, the major burden is to solve the RL problem and both distributed learning and centralized learning suffer the issue. Therefore, the parallelism cannot significantly accelerate the learning in our case. \n\nMentioned in lines 15-21, the data of multi-agent systems is usually distributed and thus centralized learning is infeasible. Therefore, the distributed learning in our case is not to accelerate the learning process but as a good substitute for the centralized learning since the distributed learning enables multiple learners to collaboratively solve the global learning problem over ad hoc networks without a centralized authority while each learner only knows a portion of training data.\n\n**Q1:  Can you give intuition for why your theoretical convergence rates are independent of $N_L$?**\n\n**Answer**: Thank you for pointing this out. Our convergence actually depends on $N_L$. We omit the dependence of $N_L$ in the theorem statement because we treat it as a constant with respect to the iteration number $N$. We will add this dependency for better understanding. The conclusion is that the convergence will be slower if $N_L$ becomes larger. The intuition behind this is that a larger number of learners will make it harder to achieve consensus, thus resulting in a slower convergence. Note that the distributed learning can be slightly faster at each online iteration, however, the convergence rate is to quantify the iteration complexity and a larger $N_L$ may result in more iterations to converge. The theoretical reason of slower convergence is in Appendix. In specific, from line 210 in Appendix, the convergence depends on the constants $C_1,C_2,C_3$ and the convergence will become slower for larger $C_1,C_2,C_3$. From lines 207-209 in Appendix, we see that $C_1,C_2,C_3$ will become larger if the constants $C\\_{max},\\tilde{C}\\_{max}$ become larger. From Lemma 10 and line 179 in Appendix, we can see that $C\\_{max}$ becomes larger if $B_0$ becomes larger. From lines 199-205, we can see that $\\tilde{C}\\_{max}$ becomes larger if $B_0$ becomes larger. From line 155 in Appendix, we know that $B_0=(N_L-1)B$ where $B$ is a positive constant defined in Assumption 2. Therefore, a larger $N_L$ will eventually lead to larger $C_1,C_2,C_3$, and thus slower convergence.\n\n**Q2: One of the benefits of distributed learning is the ability to increase parallel computation to achieve faster learning. Did you vary $N_L$ at all for either experiment and can you include those results if you have them?**\n\n**Answer**: The parallel computation among the distributed learners will not significantly accelerate the learning in our case. Please refer to the answer to the weakness for the reasons. We include a table (i.e., Table 1) in the newly uploaded PDF file to compare the scaled computation time for different numbers of learners. From the table, we can see that the computation time at each online iteration remains almost unchanged for different numbers of learners. However, the time for convergence, e.g., reaching certain performance, becomes longer when the number of learners increases. The reason is that it takes more iterations to reach consensus for a larger number of learners.\n\n**Limitation: The evader-patroller setting suggests the proposed method could be used in a way that has negative societal impact. Typically, we want the patrollers (e.g., park rangers) to capture the evaders (e.g., poachers). Can you discuss this briefly?**\n\n**Answer**: We appreciate that you mention the potential negative social impact. We would like to add the following discussion:\n\nSince MA-BIRDS can infer the experts' behaviors, potential negative social impact may occur if the learners are malicious. Take the evader-patroller setting as an example, the patrollers could be safeguards or park rangers and the evaders could be poachers. The malicious poachers may use MA-BIRDS to escape. To avoid this situation, the experts should take additional strategies such as regularly demonstrate misleading behaviors so that MA-BIRDS will learn a wrong behavior model of the experts.\n\n[D1] V. Hegde and S. Usmani, \"Parallel and distributed deep learning,\" Stanford University, 2016."}]

Author rebuttal:
Dear Reviewers,

Thanks for your detailed and constructive reviews. We believe that these discussions will lead to a stronger paper in general. We address all the comments of each reviewer under each review. We also include a PDF file in the global rebuttal that contains additional experiment results.

Best regards,  
Authors.

Meta-review: The paper studies the problem of inferring the behaviors of multiple interacting experts when demonstrations are streamed online. After rebuttal, there is general consensus among the reviewers about the interest of the setting and that the proposed approach is technical sound and it achieves satisfactory empirical performance. For all these reasons, I propose acceptance for the paper.

I would still like to encourage the authors to properly integrate their rebuttal in the final version of the paper. The motivation and the technical difficulties compared to previous work in a similar setting were much better clarified in the rebuttal than in the original submission. Similarly, it is important the authors include more intuition about the theoretical results and how to make the algorithm efficient.
Decision: Accept (poster)