Learning Expensive Coordination: An Event-Based Deep RL Approach
Authors: Zhenyu Shi*
Runsheng Yu*
Xinrun Wang*
Rundong Wang
Youzhi Zhang
Hanjiang Lai
Bo An
Venue:  (2020)
Keywords: Multi-Agent Deep Reinforcement Learning
Deep Reinforcement Learning
Leader–Follower Markov Game
Expensive Coordination

Abstract: Existing works in deep Multi-Agent Reinforcement Learning (MARL) mainly focus on coordinating cooperative agents to complete certain tasks jointly. However, in many cases of the real world, agents are self-interested such as employees in a company and clubs in a league. Therefore, the leader, i.e., the manager of the company or the league, needs to provide bonuses to followers for efficient coordination, which we call expensive coordination. The main difficulties of expensive coordination are that i) the leader has to consider the long-term effect and predict the followers' behaviors when assigning bonuses and ii) the complex interactions between followers make the training process hard to converge, especially when the leader's policy changes with time. In this work, we address this problem through an event-based deep RL approach. Our main contributions are threefold. (1) We model the leader's decision-making process as a semi-Markov Decision Process and propose a novel multi-agent event-based policy gradient to learn the leader's long-term policy. (2) We exploit the leader-follower consistency scheme to design a follower-aware module and a follower-specific attention module to predict the followers' behaviors and make accurate response to their behaviors. (3) We propose an action abstraction-based policy gradient algorithm to reduce the followers' decision space and thus accelerate the training process of followers. Experiments in resource collections, navigation, and the predator-prey game reveal that our approach outperforms the state-of-the-art methods dramatically.

Published as a conference paper at ICLR 2020
LEARNING EXPENSIVE COORDINATION: AN OVENT-BASED DEEP RL APPROACH
Runsheng Yu, Xinrun Wang, Rundong Wang, Youzhi Zhang, & Bo An School Computer Science and Engineering, Nanyang Technological University, Singapore
runshengyu@gmail. com,
(xwang033, rundong001, y edu. boan@ntu. edu.sg
Zhen Yu & Hanjiang Lait
School of Data and Computer Science, Sun Yat-sen University
Guangzhou, China
shi shizhy6@maill sysu. w.w..sysuuuuuu.. edu. en, 1athanj3email..oeo sys.maii..sss..e..mmm.. www.su.edu.c.
ABSTRACT
Existing works in deep Multi-Agent Reinforcement Learning (MARL) mainly fo- cus coordinating cooperative agents complete certain tasks jointly. However, in many cases of the real world, agents are self-interested such as employees in company and clubs in a league. Therefore, the leader, i.e., the manager of the company or the league, needs to provide bonuses to followers for efficient coordi- nation, which we call expensive coordination. The main difficulties of expensive coordination are that i) the leader has to consider the long-term effect and predict the followers' behaviors when assigning bonuses, and ii) the complex interactions between followers make the training process hard to converge, especially when the leader's policy changes with time. In this work, we address this problem through event-based deep RL approach. Our main contributions process as a semi-Markov Decision Process and propose novel multi-agent event-based policy gradient learn the leader's long-term policy. (2) We exploit the leader-follower consistency scheme design a follower-aware module and a follower-specift attention module predict the followers' behaviors and make accurate response to their behaviors. (3) We propose an action abstraction- the followers' decision space and thus accelerate the training process of follow- ers. Experiments in resource collections, navigation, and the predator-pres -eryyyyr-pyyy game reveal that our approach outperforms the ofte-offthheart methods dramatically.
threefold.
(1) We model the leader's decision-
policy gradient algorithm to reduce
INTRODUCTION
Deep Multi-Agent Reinforcement Learning (MARL) has been widely used in coordinating cooper- ative agents to jointly complete certain tasks where the agent is assumed to be selfless (fully coop- erative), i.e., the agent is willing to sacrifice itself to maximize the team reward. However, in many cases of the real world, the agents are self-interested, such taxi drivers in taxi company (fleets) and clubs a league. For instance, in the example of taxi fleets (Miao et al. 2016), drivers may pre- fer to stay in the area with high customer demand gain more reward. It is unfair and not efficient to compel the taxi driver to selflessly contribute to the company, c.g., to stay in the low customer demand area. Foreing the drivers selflessly contribute may increase the income for the company in short-term but it will finally causes the low efficient and unsustainable of that company in the
Indicates equal contribution. Co-correepponing authors.

---

Published as a conference paper at ICLR 2020
long rum because the unsatisfied drivers may be demotivated and even leave the company. Another important example is that the govermment wants some companies to invest on the poverty area to achieve the fairness of the society, which may inevitably reduce the profits of companies. Similar to previous example, the companies may leave when the government forces them to invest. A better way to achieve coordination among followers and achieve the leader's goals is that the manager of the company or the government needs to provide bonuses to followers, like the taxi company pays extra bonuses for serving the customers in rural areas and the government provides subsidies for investing in the poverty areas, which we term as expensive coordination. In this paper, we solve the large-scale sequential expensive coordination problem with a novel RL training scheme.
There are several lines of works related to the expensive coordination problem, including mecha- nism design (Nisan & Ronen, 200T) and the principal-agent model (Laffont & Martimort 2009). However, these works focus more on static decisions (each agent only makes single decision). To consider sequential decisions, the leader-follower MDP game (Sabbadin & Viet 2013 2016) and the RL-based mechanism design Tang
[Shen et al. 2017) are introduced but most of their works only focus on matrix games or small-scai Markov games, which cannot be applied to the case with the large-scale action or state space. The most related work is RL (Shu & Tian 2019) where the leader assigns goals and bonuses by using a simple attention mechanism (summing/averaging the features together) and mind (behaviors) tracking to predict the followers' behaviors and makes response to the followers' behaviors. But they only consider the rule-based followers, i.e., followers with fixed preference, and ignore the followers' behaviors responding to the leader's policy, which significantly simplifies the problem and leads the unrcasonability of the model.
In the expensive coordination problem, there are two critical issues which should be considered: 1) the leader's long-term decision process where the leader has to consider both the long-term effect of itself and long-tenn behaviors of the followers when determining his action to incentivise the coordination among followers, which is not considered in (Sabbadin & Viet 2013) Mguni et al., p and 2) the complex interactions between the leader and followers where the followers will adapt their policies to maximize their own utility given the leader's 's policy, which makes the training process unstable and hard, if not unable, to converge in large-scale environment, especially when the leader changes his actions frequently, which is ignored by (Tharakunnel & Bhattacharyya 20077: Shu & Tian 2019). In this work, we address these two issues in the expensive coordination problem through an abstraction-basee deep RL approach.
Our main contributions are threefold. (1) We model the leader's decision -akinn process as a semi- Markov Decision Process (semi-MDP) and propose a novel event-based policy gradient learn the leader's policy considering the long-term effect (leader takes actions at important points rather than at each step avoid myopic decisions.) (Section 4.1). (2) A well-performing leader's policy is also highly dependent on how well the leader knows the followers. To predict the followers' behaviors precisely, we show the leader-follower consistency scheme. Based on the scheme, the follower-aware module, the follower-specific attention module, and the sequential decision module are proposed capture these followers' behaviors and make accurate response to their behaviors (Section 4.2) p. (3) To accelerate the training process, we propose an action abstraction-based policy gradient algorithm for the followers. This approach is able to reduce followers' decision space and thus simplifies the interaction between the leader and followers as well as accelerates the training process of followers (Section 4.3). Experiments in resource collections, navigation and predator- prey show that our method outperforms the state-of-the-art methods dramatically.
2 RELATED WORKS
Our works are closely related to leader-follower RL., temporal abstraction RI, and event-based RL.
Leader-follower RI. The leader-follower RL targets at addressing the issue of expensive coordina- tion where the leader wants to maximize the social benefit (or the leader's self-benefit) by coor- dinating non-cooperative followers through providing them bonuses. Previous works have investi- gated different approaches to solve the expensive coordination, including the vanilla leader-follower MARL (Sabbadin & Viet 2013) Laumónier & thaib-draa 2005). leader semi-MDP (Tharakunnel)
& Bhattacharyya 2007), multiple followers and sub-followers MARL (Cheng et al. 2017), follow-
ers abstraction (Sabbadin & Viet 2016). and Bayesian optimization (Mguni et al. 2019). But most
of them focus on simple tabular games scall-scale Markov games. The most related work (Shu
2

---

Published as a conference paper at ICLR 2020
Leader Module
Hittery Enceder
Temisation Functiion
Aftcation Model
Ai
A(A, Ri. AD)
Policy
Fallneer Aware
Follower Medule
Hlgh- kivll atetractonn
L371
R2, of)
Encsler
:
CommiterrNa eos
Spcta
Barras Pullcy
Overview of our framework. The details of the leader's module and the follower's 's module can be found in Section 4.2 and Section 4.3 respectively. The implement details of each module can be found in Appendix D.2.1
Figure/ I:
& Tian 2019) leverages the deep RL approach to compute the leader's policy of assigning goals and bonuses to rule-based followers. But their method performs poorly when the followers are RL- based. In this work, we aim to compute the leader's policy against the RL-based followers in the complex and sequential scenarios.
Temporal abstraction RL. Our methods are also related to temporal abstraction method (Sutton al., 1998 Daniel et al.] 2016 Bacon et al. 2017 Smith et al.] 2018 /Zhang & Whiteson 2019 Vezhn- evets et al. 2016). The basic idea temporal abstraction is to divide the original one-level decision process into two-level decision process where the high-level part is decide the meta goal while the low-level policy is to select the primitive actions. Our leader's decision process different from those methods mentioned above because the leader's policy naturally form (temporal abstraction) decision process (semi-MDP) (Tharakunnel & Bhattacharyya (007) and is unnecessary design the two-level decision process for the leader (since the low-level decision process is the follower). Based on the nature of the leader, a novel training method is introduced.
intermittent
Event-based RL & Planning. Previous studies also foeus using events capture important elements (e.g., whether agent reaches a goal) during the whole episode. [Upadhyay et al. (2018) regard the leader's action and the environment feedback as events the continuous time environ- ment. [Becker et al. (2004); Gupta et al.] (2018) leverage events to capture the fact that an agent has accomplished some goals. We adopt this idea by depicting the event as the actions taken by the leader at some time steps and design novel event-based policy gradient to learn the long-tern leader's policy.
3 STACKELBERG MARKOV GAMES
Our research focuses on single-leader multi-follower Stackelberg Markov Games (SMG) (Mguni ctt al. 2019; Sabbadin & Viet 2013), which can be formulated as a tuple G = (N, S,, A, Ω, P, R, 7)- N the set of N followers, 1.e., [ N. S is the set of states. su E Sg C S is an initial state and So is the set of initial states. A = x A is the set of joint actions for followers where k E A is an action for the k-tth follower. w E s2 = x is an action for the leader and w {g 80 E
Ω* is goal and a bonus that the leader assigns to the k-th follower. ::S. S
A - (S) is the
transition functior and R * rd is the reward function set where n. S x A Ω R is the reward function for the k-th follower and r' S x A x Ω + R is the reward function for the leader, 7 is the discount factor and a is a joint action followers.
The leader's policy is defined as μ1 (eT)) where μ²* Ω x S + A(2*) is the leader's action to the lo-th follower given the leader's 's action in the previous timestep Wi-1 and the current state st. A(-) is a probability distribution. The followers' joint policy is defined
(n²) where n 22 x S - ((AA)) is the k-th follower policy given the leader's action with and the current state 8t. Given the policy profile of the leader and followers (n,, TT,, the follower's utility is defined as
(H, = ET= (st, w.)) and the leader's utility is [1, T) = E Er= 7'vi (st, a,, ao.)
We assume that the leader and followers aim to maximize their own utilities. We define the trajectory
T as a sequence state, leader's 's action, and followers' actions (w-1. (8), a,, w where w is the first step leader's 's action and is set zero.
Notice that the transition function does depend the leader's action.
3

---

Published as a conference paper at ICLR 2020
@
Commit new action
Maintain previous action
Time step
For Follower
For Follower II
(a) A simple example for the illustration of Arr. Sup- pose that the whole step 4, the Ar {el (0, wb),, el = (1,wf), e (.
(b) The probabilistic graphical model of the pro- posed framework. Dotted line means that & affects the final result of w indirectly. w-1 is set to be zero.
Figure 2: An example and probabilistic graphical model to illustrate our method.
4 METHODOLOGY
In this section, we propose a novel training scheme to train a well-performing leader policy against both rule-based and RL-based followers in the expensive coordination problem. We address the two issues, the leader's long-term decision process and the complex interactions between the leader and followers, with three key steps: (a) model the leader's decision-making process semi- Markov Decision Process (semi-MDP) and propose a novel event-based policy gradient to take actions only at important time steps avoid myopic policy; (b) accurately predict followers' be- haviors, we construct a follower-aware module based on the leader-follower consistency, including a novel follower-spese
attention mechanism, and a sequential decision module predict followers' behaviors precisely and make accurate response to these behaviors; and (c) an action abstraction- based policy gradient method for followers proposed to simplify the decision process for the followers and thus simplify the interaction between leader and followers, and accelerate the conver- gence of the training process.
4.1 EVENT-BASED TRAJECTORY OPTIMIZATION FOR LEADER
We first describe the event-based trajectory optimization for the leader. As we mentioned above, the leader's decision process can be naturally formulated as a semi-MDP (Tharakun- nel & Bhattacharyyal (2077). Therefore, we firstly describe the basic ideas of semi- MDP using the modified option structure. We define the modified option as tuple: (1,, (5*)) )REN) where lr is the leader's policy as we defined above and (8t,,, w(-1)
+ [0, is the termination function for the k-th follower, to indicate the probabil- ity whether the leader's action the k-th follower changes (wt=1 A wf)). Based on these definitions, we formulate the one-step option-state transition function with decay as: yP (st+1/se, a.) π (a, s,,w)) II {1 I (st, w(1)) Lup + where 1 is the indicator function and (a, w,)
P.y (st+1. a: (0][8;
3 (st,Wi-1) (wf(s,, IREN x² (af w)) is the joint policy for followers. Notice that this is an extension of the aug- mented process mentioned in (Bacon et al., 2017). Differently, we do not have the low-level policy here (the low-level policy is the follower) and since we only focus on the finite time horizon, y is set to be 1. Our modified option is used to depict the long-term decision process for the leader as shown in Fig. 2
Now we start to discuss our leader's policy gradient. In fact, it is not easy to directly optimize the leader's utility based on this multi-agent option-state transition function since this form in- cludes leader's different action stages different followers. Notice that for a sampled trajec- tory, the occurrence of the leader actions is deterministic. Therefore, we can regard the time step and the action the leader takes at that step as an event and define the (universal) event set Ur = (11,,,
T,k E NJ. We the notation et = (4,, to represent the leader's action to the k-th follower at step t; is the index of the event. Since we focus on the change of the actions from the leader, we further define a set that represents a collection of new actions (wi * w(_)) taken by the leader within that trajectory: Ar = kwt + w < T,K E NN C Ur, where 4, the previous time step. AT represents when and how the leader commits to new action (an example can be found in Fig. 2ah. For brevity, et & Arr means ej E UAA. The probability of
4

---

Published as a conference paper at ICLR 2020
Ar can be represented as:
P(Ar)= = IILE Iere 3
(wt, (ulllss
II Hogear (1- we,-1)).
where i - 1 is the previous time step for ty. This equation illustrates that the probability of the occurrence of a certain leader's event set within a trajectory. Concretely, the leader changes action to the k-th follower at 4 E ex while maintaining the same action within the interval from 6; - - e to 4 (s.t,, 4 E et. Similarly, we can further define the probability of the whole trajectory r as:
P(r) = P(so) ITEE { [[etes (o ( (wi, (s.,) xM (ai, lot wi:) x
Il M HAAT (1- 10 (8t,) n" (at (t,)
| P(ss+1|ss,a.) a.).
Comparing with P(AT), P(r) includes the probability of the followers as well as the state transition. Do note that our goal to maximize maXA, Px)) [RT (T)], indicating that the leader is required to select an action that can maximize the accumulated reward, where R (T) = Ei= r'r is the accumulated reward and r is to stress that its accumulated reward from the trajectory т. Following the REINFORCE trick (Sutton & Barto 1998), the policy gradient for the termination function and the leader's policy function can be formulated under the following proposition:
The policy gradients for the termination function 3h ($1,; wi.) and leader's 's policy function μ (wtt 18,2 w1, can be written as:
Proposition
{ErE ((S)
(loce)) R (T)): VoJ(O) vo EraDr() [EnE Ei r'ce)) (T))
VoJ(O) & ETSDL()
where O and 0 are the parameters for the termination function By and leader's policy 1bg I()) and T'()) are the piece-wise functions:
Vo3" (01,00))))
EATT of E AUT
I(c?)
(es, Vogt pagt (ee, (e, 8y (Ne, (1)-1)
r'(ct) { Vo log log (wf w1- ej E Ar, cj & hr.
=
oi Ar.
0
All the proof' can be found in Appendix AA] Proposition Iinioonnmmmiiii Timplies that under the weent-bssed method, whether the leader's commitment to a new action will induce different policy gradients for both termination function and the policy function.
However, from the empirical results, we find that the leader's policy function updates rarely during the whole episode because the policy only updates when the leader commits to new action, which causes the sample inefficiency. Notice that in fact the leader commits to the same action when et & Arr. Therefore, the policy indication function I'(.) can be formulated in an alternative way: (e(e)) v log y² (wi) st.,
(t., -) ef E Ar; V (wf, = - wi)-1) eet Ar- This form considers both committing
new action and maintaining the same actions (Details can be found in Remark 2 which we call the Event- -ased Policy Gradient (EBPG) and the previous one as the sparse EBPG respectively.
Intuitively, the dense EBPG is better than the sparse EBPG because it updates the leader's policy function more frequently than the sparse one. For example, in time step supposing that the leader chooses wrong action for follower & and receives a negative reward. Then, the leader should learn to diminish the action chosen that state by EBPG. The sparse EBPG only do one PG during before terminating the action (at the committing action step) while the dense one does PG in each step before terminating the action. The latter can provide more signal to correct the wrong action. Experiments also reveal that the dense one is better (Sec. D.3.3).
4.2 NEURAL NETWORK BASED LEADER
The EBPG approach is able to improve leader's performance. However, it is still very hard for the leader to choose actions considering long-term effect only based on the current state informa- tion. This is because the followers change their behaviors over time according the leader's policy.
5

---

Published as a conference paper at ICLR 2020
Therefore, we introduce new modules and training schemes to capture the change of the fol- lowers' behaviors as well as the global state. To abstract the complicated state information, we neural networks to learn the state representation. To capture the followers' behaviors and make accurate response to their behaviors, we design three modules: (1) we exploit the leader-follower consistency under game regularization and policy bound conditions, (2) based the consistency, follower-aware module is introduced and (3) based on the follower-aware module, a novel attention mechanism, and sequential decision making module designed to make accurate response to these followers' behaviors as shown in Fig.
Consistency. In previous works, surge of researches focus on predicting other agents' behaviors through historical information, where the other agents are assumed to be oppo- nents of that agent, which is only suitable for zero-sum games (Zheng et al.] 2018 Foerster al. 2018 He et al. 2016). However, these methods cannot be directly applied to our case because SMG is not zero-sum. We note that [Shu Tian (2019) attempt to directly use the followers' behavior prediction module (use the history of the followers to predict their future actions) but do not analyze when and how it works. To ensure that the leader can predict the followers' behaviors, we introduce the following assumptions.
Leader-Follower
Assumption 1. (Game regularization) The leader-follower state-action space (A x Ω x S) is com- pact and b a continuous fanction w.r.t. μe bounded by Rmaxx
This assumption is inspired by (Antos et al. 2008). We only extend into the multi-agent forms. This assumption indicates that the action and states space should be limited and the reward function for the leader action should be smooth.
Assumption 2. (Policy Bound) For any agent k, reward functionn p* and policy is consistency, i.e.,
j ([**, , " 1o) - ['((T= ; *=] ,²'l 2 C2 T
Where C2 is constant that satisfies C > 0. T is the followerss new policy, μl is the leader's new policy.
This assumption inspired by (Mguni al. 2019). indicates the joint policy without the k-th agent's. This assumption indicates that the change of the leader causes only slightly changes on each followers policy.
Based on these two assumptions, we propose a proposition here:
Proposition 2. Seeader-Follower Consistency.) If both the assumptions of game regularization and policy bound are satisfied, for 'Ve >> 0, N, there exists > O, such that |1 ju--a μ S e implies Ar Th I 6, where μl and 1hth are the new policies for the leader and the k-th follower respectively.
This proposition reveals that the change of the leader causes only slightly changes on each follower's policy under the game regularization assumption and the policy bound assumption, which is fun- damental to follower-aware learning. Roughly speaking. the game regularization requires that the states, actions, and rewards are bounded while the policy bound states that a little change of a fol- lower's policy does not change its utility so much. The former is from the game itself and we only focus on the latter. To satisfy the latter, one possible method is make the μ and μı' close because the followers always find the best response to the leader's ' policy and if the leader changes a little, the followers do not change too much since the new best response to 2ı' is not far away from best response to One direct method is to slow down the learning rate of the leader to make fı' and μ close. Moreover, for the leader part, taking the right actions also an important way to guarantee the second assumption because the taken action will more precisely decrease the probability of huge change of the whole process and stabilize the training process. There an interesting phenomenon that hand, knowing more about the followers can diminish the wrong decision and thus aids the establishment of the consistency. On the other hand, the consistency will further guarantee the accuracy of the follower-aware module. Therefore, they form a positive feedback.
Follower-Aware Module. Based on the leader-follower consistency, we can safely implement the follower-aware module to network. Before we discuss this module in details, first define the history for both the leader and followers. For the k-th follower. its history at time step t is a sequence of states, its actions, and the leader's actions it, i.e., h ((se, ab wtt Jegd) E H

---

Published as a conference paper at ICLR 2020
while the leader's history is the stack of all followers histories h, (KT)KEN E Hi. Then, we define the distory-based leader's policy as: 1hi (5t) = Z 'p( st, ai. he)p(ārlss he) oc p(wfiss st, az. h2) I pd (a st. nr),, where Z is the normalization term, p² is the predicted action probability of the k-th follower and à defines the predicted action (predicted by the leader). p is to stress the output is a probability. Since we cannot directly obtain an accurate estimation of a², we adopt an alternative way to leverage history information and imitation learning to make pre- diction of other agents' action probability function p (a.) st, h (Implementation details can be found in Appendix B and p(w+ st: ā₂, hes) is designed using the attention mechanism well as the sequential decision module presented below.
Follower-Specifeed Attention Mechanism. Inspired by (Chen al. 2018), we introduce follower-specific attention mechanism to identify the important followers where the important fol- lowers are followers who has just finished task and the leader has commit new actions to these followers. The attention mechanism is as follows:
cxp (A (c,, af. k))))
w/
C₁ = =IENN u (st. at, ht) : : = A
(3,, af. k.
EKEN exp (A
[A( (st, at 1))
Where w is the weight of the k-th follower, A(.) IR dexd, xddt - Re is a function to blend various information of an agent together (d, means the dimension of the output of the A(.)). f(): map the blending information to real number, and ot is the k-th
Rd + R! is function agent attention value (the compression of history, states and actions for follower k as well as other followers). at is the output of pa (āt ss, ht))), the predicted the k-th follower's action. This attention mechanism is better because it quantifies the importance of each follower in each state through learning while the original methods only adds/averages all the features (s,, a.. ht) together (Shu & Tian 2019). Another advantage is that its weights can be visualized to see which follower is important to the leader at current step. (Details can be found in Appendices D.2.1 & D.3.4). of then is used by 3 and μ.².
Sequentially Determining Goals and Bonuses, Also notice that the goal and the bonus are sequen- tially correlated. Therefore, it is better for the leader to choose the bonus and the goal sequentially rather than select them independently. Therefore, to consider the goal and bonus jointly when mak- ing decision, we build probabilistic graph-based model as: pl p( [& âz; he) x plaf; (f(ct) x p(b/lg cf) x p(g |ct). the first approximate equation is established because of is the compression of (st, âe, fe)). p(b 1 cf)) and p(g ct) means the policy for bonuses and goals (Implementation
details can be found in Appendix 1.2.1)
4.3 FOLLOWER ACTION ABSTRACTION POLICY GRADIENT
These methods mentioned above are fully implemented can enhance the performance dramatically. But when facing the RL--based followers, the SMG is still hard to converge. This is because in SMG, the policies of the leader and followers are always changing depending on other agents' performance. To guarantee convergence, the leader can only update its policy when the followers reach (or are near to) the best response policy (Fiez et al. 2019). However, when the followers are RL-based agents, there is no way to ensure the followers' policies are (near) the best response policies in large-scale SMG and the commonly-sedn idea is to provide enough training time but is unbearable in practice due to the limitation of computing power (Mguni et al. 2019).
To accelerate the training process, inspired by the action abstraction approach which commonly- seen in Poker (Brown & Sandholm [201:: Tuyls et al.) 2018) and action abstraction RI. (Chandak cet al. 2019), we collect the followers' primitive actions sharing the same properties together as a meta policy. Then, the followers only need to select the meta action to make decision. Therefore, the original game is converted into a meta game, which is easy to solve.
Specifically, we define the policy for the k-th follower as: T/ E, T (z (als, 2). where å = (s, is the augmented state for the follower (the combination of current state and the leader's action). = (2(5) is the meta policy for the k-th follower and is the high-level (meta) action. We hypothesize that the lower-level policy (the policy to choose the primitive actions) is already known (rule-based) and deterministic, i..., Th Fonwer (a*13, z)= 1. For instance, given the example of the navigation task, the Th Theta can be the selection to which landmark to explore while nht noowrr is a specific route planning algorithm (such
7

---

Published as a conference paper at ICLR 2020
nown
Oalt Mariien
Out
Gat Al Alteee
0,3
(a) Resource Collections.
(b) Multi-Bonus Resource
(c) Navigation.
(d) Predator- Prey.
Collections.
Figure 3: Leader's reward curves for different tasks (rule-based followers).
as Dijkstra Algorithm). Based on this assumption, we can design novel policy gradient to train the meta policy: Vx k oc EE Xxx log ni Tineta (2|)) where X is the parameter for meta-policyy meta (Details can be found in Lemma
T
4.4 Loss FUNCTIONS
In this section, we discuss how design the leader's and followers' loss functions.
Loss Functions for the Leaders. The basic structure for the leader is the actor-critic structure (Sut-) & Barto 1998). We find that adding regularizers can enhance the leader's performance and we implement the maximum entropy for the leader's s policy function as well as the 1.2 regularization for the termination function, i.e., Lemp
Σx Ene 1a (w*|s, h) log μ. (w*1s. (s. ft) and Trey = 88. We also use imitation learning to learn the predicted action function zh Following the same logic of (Shu & Tian 2019), two baseline functions 69 (cx) and (cx) are also introduced to further reduce the variance. Details can found Appendix B
Loss Functions for the RL-Based Followers. The basic structure for each follower is also based on the actor-critic structure. We leverage the action abstraction policy gradient as we mentioned above. The learning rate between the leader and follower should satisfy the two time-scale principle (Roughly speaking, the leader learns slower than the follower(s)), similar to (Borkar 1997). Details can be found in Appendix and the pseudo-code can be found in Appendix
5 EXPERIMENTAL RESULTS
5.1 SETUP
Tasks. We evaluate the follow- ing tasks to testify the performance of our proposed method. All of these tasks are based on SMG men- tioned above. (1) resource collec- tions: each follower collects three types of resources including its pre- ferred one and the leader can choose two bonuses levels (Shu Tian 2019) (2) multi- bonus resources col- lections: based on (1), the leader can choose four bonuses levels; (3) modified navigation: followers are required to navigate some landmarks and after one of the landmarks is reached, the reached land- mark disappears and new landmark will appear randomly. (4) modified predator-prey: followers are required to capture some randomly moving preys, prizes will be given after touching them. Both (3) and (4) are based on (Lowe et al. 2017) and we modify them into our SMG setting. Moreover, to increase the difficulty, each episode, the combinations of the followers will change, i.e., in each task, there are 40 different followers and at each episode, we randomly choose some followers to play the game. More details be found in Appendix
Dura Tre acstraction)
(PAAl Ovi aberrattion
Ressucee Colleticn Muribocess Rescerce Cellction
Predetie
Figure 4:
The final reward for RL-based followers. No ab- straction means vanilla RL-based followers.
Baselines Ablations. To evaluate our method, we compare a recently proposed method as our baseline: M (Shu & Tian 2019). We do not include other baselines because other methods
8

---

Published as a conference paper at ICLR 2020
cannot be used in our problems, justified in (Shu & Tian 2019). For the ablations of the leader part, we choose: (1) ours: the full implementation of our method. (2) ours w/o EBPG: removing the event-based policy gradient part: (3) ours w/o Attention: replacing follower-specified attention model by the original attention model mentioned in (Shu & Tian, 2019). For the follower part, choose (a) with rule-based follower (b) with vanilla RL-baaed follower, and (c) with action abstraction RL-based follower to testify the ability of our methods when facing different followers.
Syype--Parameteee Our code is implemented in Pytorch (Paszke et al. 2017). If special men- tion, the batch size is 1 (online learning). Similar to (Shu & Tian 2019). we set the learning rate as 0.001 for the leader's critic and followers while 0.0003 for the leader's s policy, The optimization al- gorithm is Adam (Kingma& & Ba, 2014). Our method takes less than two days to train on NVIDIA Geforce GTX 1080Ti GPU each experiment.
For the loss function, we set the \ 0.01 and X2 0.001. The total training episode is 250, 000 for all the tasks (including both the based followers and the RL-based followers). To encourage exploration, we use the (-greedy] For the leader, the exploration rate is set to 0.1 and slightly decreases to zero (5000 episode). For the followers, the exploration rate for each agent is always 0.3 (except for the noise experiments).
5.2 LEARNING EFFICIENCY
Table I: Robustness results in multi-bount resource collections. 8% is the probability that followers randomly choose actions.
The quantitative results with dif- ferent tasks are shown in Figs. 3 & 4 For the rule-based fol- lowers, from Fig. that our method outperforms the state-of-the-arr method in all the tasks, showing that our method sample efficient and fast to coverage. There is an interesting phenomenon that in the task of multi-bonus resource collections and navigation, only our method obtains a positive reward, indi- cating that our method can work well in complicated environments. For ablations, we can see that ours w/o attention and ours w/o EBPG are worse than ours, representing these components do en- hance the performance. For the RL-based followers, from Fig. 4 we observe that when facing the RL-based method with action abstraction, our approach outperforms the baseline method in all the tasks (in predator-prey game, the reward for ours is twice as that of the state-of-the-art), We also find that without action abstraction, the reward is less than zero, revealing that the abstraction does play a crucial role in stabilizing training.
Methods
0% Noise
30% Noise
50% Noise
Ours total incentive
18.32
17.63
17.28
find
RLRL total incentive
4.06
3.85
4.02
Ours total reward
10.06
5.36
5.30
RL total reward
-1.58
-3.23
-8.96
5.3 ROBUSTNESS
This experiment is to evaluate whether our method is robust to the noise, i.c., the follower randomly takes actions. We make this experiment by introducing noise into the follower decision. From Table [ we find that our method reaches higher total reward (more than 5) among all the environment with noise than the state-of-the-art, indicating that our method is robust to the noise. We also observe that the total reward for the baseline method becomes lower with the increase of the noise while our method is more robust to the change. Moreover, for the incentive (the total gain), we find that our method gains much more incentive than the state-of-th the method, showing that our method coordinates have a better coordination the followers than the state-of- oate--of-the-ar method.
5.4 MORE EXPERIMENTS
We also do substantial number of experiments. However, due the space limitation, we can only provide some results here: (1) The total incentives: incentive can reveal the performance of successful rate interacting with the followers. Our method outperforms the sfate-of-the-ar method, indicating that our method has better ability to interact with the followers. (2) Sparse EBPG: we compare the performance gap between sparse EBPG and (dense) EBPG. This results show that the sparse one is worse than the dense one, supporting the assumption that the dense signal can improve
Normally it is called the decayed e-greody. We use instead of avoid notation abuse.

---

Published as a conference paper at ICLR 2020
the sample efficiency. (3) Visualizing attention: We visualize the attention module to find what it ac- tually learns and the result indicates that our attention mechanism does capture the followers whom the leader needs to assign bonuses to. (4) Two time-scale training: We testify whether our two time- scale training scheme works and the ablation shows that this scheme does play an important role in improving the performance of both the leader and the followers. (5) The committing interval: We observe that the dynamic committing interval (our method) performs better than the one with fixed committing intervals. (6) Reward for RL-based followers: we show the reward for the followers, which can provide the situation of the followers. The result represents that our method aids the followers to gain more than the state-of-the-ar method. (7) Number of RL-based followers: finally, we testify our method in cases with different number of RL-based followers. The result shows that our method always performs well. The full results can found Appendix D
CONCLUSION REMARKS
This paper proposes a novel RL training scheme for Stackelberg Markov Games with single leader and multiple self-interested followers, which considers the leader's long-term decision process and complicated interaction between followers with three contributions. 1) To consider the long-term effect of the leader's 's behavior, we develop event- policy gradient for the leader's policy. 2) To predict the followers' behaviors and make accurate response to their behaviors, we exploit the meder--flllowe consistency to design novel follower-aware module and follower-specific attention mechanism. 3) We propose an action inttraction-based policy gradient algorithm to accelerate the training process of followers. Experiments in resource collections, navigation, and predator-prey game reveal that our method outperforms the state-of-the-ar methods dramatically.
We are willing to highlight that SMGs contribute to the RL (especially MARL) community with three key aspects: 1). As we mentioned in the Introduction, most of the existing MARL methods assume that all the agents are willing to sacrifice themselves to maximize the total rewards, which is not true in many real-world non-cooperative scenarios. On the contrary, our proposed method realistically assumes that agents are self-interested. Thus, SMGs provide new scheme focusing more on the self-interested agents. We think this aspect is the most significant contribution to the RI. community. 2). The SMGs can be regarded as the multi-agent system with different roles (the leader and the followers) (Wilson et al., 2008) and our method provides a solution to that problem. 3). Our methods also contribute to the hicrarchical RL, i.c., it provides a non-cooperative training scheme between the high-level policy (the leaders) and the low-level policy (the followers). which plays an important role when the followers are self-interested. Moreover, our EBPG also propose an novel policy gradient method for the temporal abstraction structure.
There are several directions we would like to investigate to further extend our SMG model: i) we will consider multiple cooperative/competiiv leaders and multiple self-interested followers, which is the case in the labor market, ii) we will consider multi-level leaders, which is the case in the hierarchical organizations and companies and iii) we will consider the adversarial attacks our SMG model, which may induce extra cost to the leader for efficient coordination. We believe that our work is a preliminary step towards a deeper understanding of the leader-follower scheme in both research and the application to society.
ACKNOW
This research is supported by NRF
NSOE-TSS2019-01, MOE and NTU.
Also, this work is supported by the National Natural Science Foundation of China under Grants (U1611266 1264, ported by the Pearl River Nova Program of Guangzhou (01906010080).
61772567, U1811262 and U1711262). This work is also sup-
We would like to thank Tianming Shu, Darren Chua, Suming Yu, Enrique Munoz de Cote, and Xu He for their kind suggestions and helps. We also appreciate the anonymous reviewers for their useful suggestions.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
András Antos, Csaba Szepesvári, and Rémi Munos. Fitted Q-iteration in continuous action-space mdps. In NeurlPS, pp. 9-16, 2008.
Pierre-Luc Bacon, Jean Harb, and Doina Precup. The option-critic architecture. In AAAI, 1726- 1734, 2017.
Raphen Becker, Shlomo Zilberstein, Victor Lesser, and Claudia V Goldman. Solving transition independent decentralized Markov decision processes. Journal of Artificial Intelligence Research, 12:423-455 2004.
Vivek S Borkar. Stochastic approximation with two time scales. Systems & Control Letters, 29(5): 291-294, 1997.
Noam Brown and Tuomas Sandholm. Superhuman AI for multiplayer poker. Science, 365(6456): 885-890, 2019.
Yash Chandak, Georgios Theocharous, James Kostas, Scott Jordan, and Philip S Thomas. Learning action representations for reinforcement learning. arXiv preprint arXiv: 2019.
Changan Chen, Yuejiang Liu, Sven Kreiss, and Alexandre Alahi. Crowd-robot interaction: Crowd-aware robot navigation with attention-base deep reinforcement learning. arXiv preprint /800008800 2018.
Chi Cheng, Zhangqing Zhu, Bo Xin, and Chunlin Chen. A multi-agent reinforcement learning algorithm based on Stackelberg game. In DDCLS, pp. 727-732, 2017.
Christian Daniel, Herke Van Hoof, Jan Peters, and Gerhard Neumann. Probabilistic inference for determining options reinforcement learning. Machine Learning, 104(2-3)3337-357, 2016.
Tanner Fiez, Benjamin Chasnov, and Lillian J Ratliff. Convergence of learning dynamics in Stack- elberg games. arXiv preprint arXiv: /tt////060021,,. 2019.
Jakob Foerster, Richard Y Chen, Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbeel, and Igor Mordatch. Learning with opponent-learning awareness. In AAMAS, pp. 122-130, 2018.
FA Gers, J Schmidhuber, and F Cummins. Learning to forget: Continual prediction with LSTM. Neural Computation, 12(10):2451, 2000.
Tarun Gupta, Akshat Kumar, and Praveen Paruchuri. Planning and learning for decentralized MDPs with event driven rewards. In AAAI, pp. 6186-6194, 2018.
He He, Jordan Boyd-Graber, Kevin Kwok, and Hal Daumé III. Opponent modeling in deep rein- forcement learning. In ICML, pp. 1804-1813, 2016.
Shariq Iqbal and Fei Sha. Actor-attentionncritiec for multi-agent reinforcement learning. ICMI., pp. 2961-2970, 2019.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In ICML, pp. 267-274, 2002.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1rXiv:1412.6988) 2014.
Jean-Jacques Laffont and David Martimort. The Theory of Incentives: The Principal-Agent Model. Princeton University Press, 2009.
Julien Laumônier and Brahim Chaib-draa. Multiagent q-learning: Preliminary study on dominance between the nash and stackelberg equilibriums. In aAAi workshop. 2005.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-compettiiee environments. In NeurIPS, pp. 6379-6390, 2017.

---

Published as a conference paper at ICLR 2020
David Mguni, Joel Jennings, Emilio Sison, Sergio Valcareel Macua, Sofia Ceppi, and Enrique Munoz de Cote. Coordinating the crowd: Inducing desirable equilibria in non-cooperative sys- tems. In AAMAS, pp. 386-394, 2019.
Fei Miao, Shuo Han, Shan Lin, John A Stankovic, Desheng Zhang, Sirajum Munir, Hua Huang, Tian He, and George J Pappas. Taxi dispatch with real-time sensing data in metropolitan areas: A receding horizon control approach. IEEE Transactions on Automation Science and Engineering, 13(2):663-478 2016.
Noam Nisan and Amir Ronen, Algorithmic mechanism design. Games and Economic Behavior, 35 (1-2):166-19)) 196, 2001.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch. In Autodiff Workshop NeurlPS, 2017.
Neil Rabinowitz, Frank Perbet, Francis Song, Chiyuan Zhang, SM Ali Eslami, and Matthew Botvinick. Machine theory of mind. In International Conference on Machine Learning, pp- 4215-4224, 2018.
Régis Sabbadin and Anne-France Viet. A tractable leader-follower MDP model for animal disease management. AAAI, pp. 1320-1326, 2013.
Régis Sabbadin and Anne-France Viet. Leader-follower MDP models with factored state space and many hallowers-folloeerr abstraction, structured dynamics and state aggregation. In ECAI, pp. 116-124, 2016.
Weiran Shen, Binghui Peng, Hanpeng Liu, Michael Zhang, Ruohan Qian, Yan Hong, Zhi Guo, Zongyao Ding, Pengjun Lu, and Pingzhong Tang. Reinforcement mechanism design. with ap- plications dynamic pricing in sponsored search auctions. arXiv preprint 17Xiv:1711.10279. 2017.
Tianmin Shu and Yuandong Tian. RL Mind-aware multi-agent management reinforcement learning. ICLR, 2019.
Matthew
Smith, Herke Hoof, and Joelle Pineau. An inference-based policy gradient method for learning options. In ICML, pp. 4710-4719, 2018.
Richard S Sutton and Andrew G Barto. Introduction to Reinforcement Learning, MIT Press Cam- bridge, 1998.
Richard S Sutton, Doina Precup, and Satinder Singh. Intra-option learning about temporally abstract actions. In ICML, pp. 556-564, 1998.
Pingzhong Tang. Reinforcement mechanism design. ISCAI, pp. 26-30, 2017.
Kurian Tharakunnel and Siddhartha Bhattacharyya. Leader-follower semi-Markov decision prob- lems: Theoretical framework and approximate solution. In 2007 IEEE International Symposium
on Approximate Dynamic Programming and Reinforcement Learning, 111-118, 2007.
Karl Tuyls, Julien Perolat, Mare Lanctot, Joel Z Leibo, and Thore Graepel. A generalised method for empirical game thcoretic analysis. In AAMAS, pp. 77-85, 2018.
Utkarsh Upadhyay, Abir De, and Manuel Gomez Rodriguez. Deep reinforcement learning of marked temporal point processes. In NeurlPS, pp. 3168-3178, 2018.
Alexander Vezhnevets, Volodymyr Mnih, Simon Osindero, Alex Graves, Oriol Vinyals, John Aga- piou, al. Strategic attentive writer for learning macro-actions. In NeurIPS, pp. 3486-3494, 2016.
Aaron Wilson, Alan Fern, Soumya Ray, and Prasad Tadepalli. Learning and transferring roles in multi-agent reinforcement. Proc. AAAI-08 Workshop on Transfer Learning for Complex Tasks, 2008.
12

---

Published as a conference paper at ICLR 2020
Shangtong Zhang and Shimon Whiteson. DAC: The double actor-critic architecture for learning options. arXiv preprint 1rXv: 2019.
Yan Zheng, Zhaopeng Meng, Jianye Hao, Zongzhang Zhang, Tianpei Yang, and Changjie Fan. A deep Bayesian policy reuse approach against non-stationary agents. In NeurIPS, pp. 954-964, 2018.
13

---

Published as a conference paper at ICLR 2020
A PROOFS
Proposition 1. The policy gradients for termination function 3h (8t,, wi.) and leader's 's policy func- tion/ μ (1) can be written as:
{ Σ LEEN
T
VoJ(O) ~ Exppi() |
{
T M(t))
mim]s
VaJ(0) vo Brope()
ΣΣNe
T( 1=
KEE T=U
where O and i are the parameters for the termination function 3 and the leader's policy nd I(.) and (-) are the piece-wise functions:
(EL
ot E AT
I(e?)
1-88 (ee)
('(e)) {0
Vo log log (wtt I9t, w1:
of E Ar
Vost (de, (w
ct & Ar
ot & Ar..
18 (e 1)
Proof. First recall the utility for the leader:
(0) Er(T) (T))
ΣΣ P( P(ATT P()))s)) ILLE { [ILeen (s,,, (w Ist,, w1 a (att |st. a
Hyyer (1 (1- 3h (st, )) * (ot,lss,)uuf) wi:)
}II P(s4t1ls, R
Where m the number of the times taking new action, m S. T. If m T, implying that the leader has taken new action at each time. P([AT] m) means the probability of times taking new action within an episode.
Take derivatives on both LHS and RHS, we get:
VoJ(0) ΣΣ VoP(IAT) = ( II
II CEEAT
(5 We, (t, -)p (wt, 18t, we:-1) a (a (se, (et
KEN
} ToP((Arl=m)[La m) IhEN HoteR (Se,, We, Noteer (8t,: wr,-1)
T
II (1 - 3 ($t, Wi, (1) / (at, (ellls,,.u
II P(sc41|82, at) (T)
t=
VoP([AT] =
P(ATT] = m) IREN Ietear B (8t,,, Wt, Hoyear
yer (1 - ($1e, Wky w -1)
x P([ATI = P(so)
II
w (st,, Wr, w (w ( tt (a (s,, wnti) x
REN
EEAT
T
II (1 - (8t,s Wig 1)) x (a (at)) Loggtor
}
II P( Re) (T)
For brevity, we use P(T) to represent P(so) llEN
[LayEay (K (1st,,Wr,11) 1) (wfflse,, Wi; wi, at (at, 18,, (tt
[eyerr (1 - 3 (st, Wr, 1)) t (at (st,1se,, ]
I P(set1l3 ac). the trajectory probabil-
ity. And we use E et and j E et to represent E ot E Arr to et Arr with slight abuse of
14

---

Published as a conference paper at ICLR 2020
notation.
Thus the equation mentioned above can be further simplified as:
ΣΣ P(|TT|=
V
Σ KEW iEet
log(1 13t (8t, ((;-1)
Σ
Σ
log 36 (1)): P(T)
kEN jEEj
2 (x
Vo
Σ KEN VEct
Σ
log(1 - Bt (8t., (1,
Σ log 1r (st,s Wiy W
R((T)
REN jEEj
V Volt (Sty: W1,-1) R² (T) }
ΣΣ
- Vogk (st, W1,-1)
=E
3h (St,,
3h (st, Wey
KEN FEE KENiEET
REN JEEJ
The equation above is exactly the REINFORCE trick (Sutton & Barto 1998) and the rule of deriva- tions. The approximation indicates that one trajectory only has one AT of et and ey,, the equation can be rewritten in a more compact form:
Also based on the definition
Voig (st. W Bh (st, w1
Vogh (st,, (t.:) Bh (st,, 11
(0) = ETepr())
Σ KEN jEet
Ha (T)
AEN iEef
Σ ΣΣΣnN KEN
I(et) R(T])
ET
Where I(.) is the piece-wise function:
Vast (sa, (1r ef E AT
3y (oe,
I(e
Vont (ss, oi $ Ar-
B (51,
This is the first part of the proof (the policy gradient for the termination function). Here, we start proving the second part (the policy gradient for the leader's 's action).
The proof of the second part is similar to the first part.
voJ(0) Σ Σ P([ATI = P(50)
II
{
II LeEER
3 (Sr,, Wi w (wi, 1sc, w(--1) ahe (at, loc, wtt x
REN
T
II gAT
(1 - 8h (st, 1))
P(s 11 R))
2=
ΣΣ voP(IAT] m)) ILEN Hoye uh (wi, 18,
(e wi:-1)
P(ATT =m) IIEE Ileea wh (W (.,
x P( m)) P(so) II II ( wi- dut (w Ioi w) x (att, 182, wt.))
kENiect x
II
8t (s1ys Why -hy 11))
(at wtt R (T)
ΣΣ
V log nd (w (ut (o)-)) (T))
T m
KEN et
Vo log n² (wt (1, ao....)) | Σ RENSEC
=
Er
We find that Upadhyay al. 2018 also implement this approximation but different explanations.
15

---

Published as a conference paper at ICLR 2020
We rewrite it to more compact form:
T
VoJ(0) Brapr()
Σ Σ LEEN i=1
((tt)
(T())
[((e)) Vo VVologu nr (uf; (80, We,
eg E AT eg & Arr
Remark 1. Some researches also focus event-based RL but either single-agent continuous time (Upadhyay et al.) (0118) or reward representation (Gupta et al.) 2018). We are the first to develop and implement the event-based policy gradient into the mulli-agent system.
Remark 2. In fact, the policy gradient for the leader actions might be somewhat sparse, i.e., only update the policy when the leader changes ils actions. Notice that the leader commits to the same action when ex & hor. Therefore, the probability of leader's 's action P P(AT) can also represented as:
P(A-) = II
II
(st,, Wi: 111 (wi, 18,,, wi,
kEN of EAT
x II
(1 3h (st,, (itt-111))) 10th (ut, - wt,-
EAT
Then the policy gradient for leader's policy Exspr() { [EKEN Et l'(et)] R (T)).. where
V (o) can thus be VoJ(O) 2
r(eet) = (Vo Pologgt (w lo,,,,,,- w1-1) ouu (wh, = wt - 18c, w1,-1)
e E Av e & AuT
Lemma 1. (Reward Bound) For any agent k the corresponding reward function 1hth wan w is C- Lipschitz continuous.
lr af, az 11) - re (se, al ai u0) I Clu 4'), Se, a. [a ar k
Where C constant that satisfies C Ju' is leader's new policy. a is the joint action without agent k's s's.
Proof. Based Assumption 1
build compact metric space (A x Ω 8, R*). From the Canne- theorem we know that the compact metric space induce uniformly continuous.
That is, for every e > 0, there exists 8 > 0, such that 114 - |²| S c implies |r (st, at a, 14) r (St, of ot" -
u²) ))] 5. There exists at least one positive Constance C' such that 8 < C/e. Then
Int (st, at, a, 11) - r (se, at, on u²) s 5 c Clu n').
This Lemma is similar to the assumption in MMguni et al. 2019). We prove it rather than make it an assumption.
Lemma 2. If Asssupptinn iss satisfied, the inequality is established:
I ([TTTT "] 11) Jd ['(["" x
p²)l "1, Clu μrl
Proof. Expand the utility function by the bellman equation:
"The follower's 's reward is originally defined based the r. (s:, at o, * 14). Here to emphasize the relationship between leader's policy and reward, with little abuse of the notation, we use r (st, at o, *,1) represent the reward function..
16

---

Published as a conference paper at ICLR 2020
1 ([xx [ [x] 14) ([T -,x :1))1
=mmax R mell
k 00. , ?
E
P (sils00 a0) "1 pr, 81)
max mell
k (50. H²) + + Σ
P (si and VT x H (1)
(2)
#1E8
max well
(r
(50: at. 00th 1i) - rk (su, a a0 u1)
+
Σ
P(slss,
((T)))))) (1) - V क s1)|11
(3)
Σ
* pm (8t+1
max well
E [r (se, at ar (2) - pk (*t, a aj |4)]]
(4)
#ES t=
The first relaxation is due the property of max: max (A(x) B(x) 2 max A(x) max (z)),, where A(x) and B(x) are both the real functions. The Eq. (4 is the result of recursive iteration.
5(1 (1-7)) max Er [r (st, at a, (4) x af a, n²) Clps 1²'
(5)
Where C (1
-- - last equation drawn form the Assumption and the inequality of >- < (1 <1-7)-1 Some parts follow the same logic of (Bacon et al.
geometric series:
[
2017 Mguni et al. 2019 Kakade & Langford 2002).
Proposition 2. (Leader-Follower Consistency.) both Assumptions and 2 are satisfied, for every > 0 E N, there exists 8 > O, such that - - S implies are the new policies for the leader and and follower respectively.
n S 8, where μí' and x²
Proof. By combining Lemma and Assumption
we can draw that:
T - π S (1 - 7)00 μ'l
If there exist |W w/1 and we have:
n² (1- w'l
(1-
D)C
And set c(1 ()- the consistency is established.
Lemma 3. (Action Abstraction Policy Gradient.) Under the assumption that the low-level follower
policy & Flower (as st, 21) is fixed and deterministic, the policy gradient for action iittraction--asee follower can be formulated as:
J x
Vxa log dh meeta (2|$) R*)
Where R² the accumulated reward for the k-th follower.
Proof. Recall the utility for the k-th follower:
T 1kt (1,, m) = E En= r / (8t, a2 wi) lar ~ ai (-18)) 8t41 ~ P (.1se, at) , = 8, s, ~ pa(-1se; wI-1)
For brevity, we rewrite the object j E Ets ''r (st, ac we))
with slight abuse of
notation. The standard policy gradient can be:
J+ = E/V A+ log o. R+
17

---

Published as a conference paper at ICLR 2020
When Toower (als, 2) is fixed and deterministic, the equation can be:
Aa D2,, T Tmeta (2e(5))) (os)))ooonee (as 18,, z1)]
V
E
Vx logl
Σ menra (2e (e))) (eelse, 23 1R
=
Ex, T (2e (8) lower (at 18t; 24)
RL
V Ex, Tieta (2e(se) (ar 10c ze)1
Σ be VAN VAn (20(8t) Tower (as $e, ze)l R
E
R
E
Σn, = mera (1/811))111111 (e(8t))fower (at 18t; 2t)
Ex, 2, merr (2g 8e Towee (ee| 2x)
Es VAntmeta (Zrl (e tower (as [8, zr)] 12
E
Z
x E
XA log[=mera (2) R84]
Where Eg k mata (2 8t) fower (at 18,, 22) is the partition function. For brevity, with slight abuse of notation, we omit the superscript for variables a and 2 which represents the index of an agent.
B LOSS FUNCTIONS
B. LEADER LOss FUNCTIONS
We add baseline function reduce the variance of the event-based policy gradient for the leader. We adopt the idea of successor representation (Rabinowitz et al. 2018 Shu & Tian 2019) as two expected baseline functions: (c,) and (c.). For the gain bascline function:
ΣΣ MEG KEN
(g g. (st = 8g) Ug.
For the bonus-based baseline function:
Σ
TI (g s( Dr.
9EG KEN
Two baseline neural network functions with parameters by and O, are trained through minimizing the mean square error:
Lbaseline = (c;; Φ3)2 (o'(cr; 0by2.
Where a is the attention- based latent variable.
To this end, the gradient for the leader can be formulated as:
VoL (0) + V (rr V PoLplicy -VoJ(())
+ (o (D(22een)).
Where
VoJ ~ Exrp:()
Σ ΣΣΣ 1(67)
(IT (c; (((())) + o (cin
LIEN
VoJ RJ B
ΣΣ r(t))
(RE ( 0,) + (ccrslo))
LIEN
are the baseline policy gradients.
We also leverage the imitation learning to learn the action probability function p (at h2, 01) similar (Shu Tian 2019), where 0, is the parameters for follower-aware module:
log pz (a-lst, hr: (1:
LI
N
REN
The history encoder, the state encoder and the attention module are updated with the leader's 's policy gradient end-to-end.
18

---

Published as a conference paper at ICLR 2020
B.2 FOLLOWER Loss FUNCTIONS
The follower policy gradient from Lemma and we find that adding the history h can improve the performance:
V A
E Vx,
A log π meta )
and the learning rate of the follower and the leader 3 satisfy
Σ ar Σ B. DO,
Σ of 3 oc,
lim Be/or O. 10000
Which indicates the follower's learning rate is much higher than the leader. is the learning rate for the leader's critic function, which the same as a. Followers do have critic function.
C ALGORITHM
Algorithm 1: EBPG
Input: The initialized leader's parameters and followers' parameters X; Output: Well-trained leader and followers;
while not converge do if Rollout Stage then for t < ' do
3
leader commits to the goals g and bonuses according Algorithm send the goals and bonuses to each agent separately;
for &
The k-th follower receives its bonus by and goal g
each agent make decision at क (a (5);; end
St+1, rh, (r+ JuEN step(se, ar):
transition function.
end
store (st, ae, We, S141, rh, frt JNEN) in episode buffer; else if Training Stage then
14
for k E N do x
15
x - J
// the follower's s parameters
end
17
0, - 0g 3V Loasetine Or + 0, 3V, Laaseline
// the critic's s
parameters
o -- 0, -T Va, Tmn:
1/ the follower-aware module's s parameters
0 0 Ao I.patio
// the termination function's parameters
20
- 2 vV 2 policy.
// the parameters of leader's s policy:
21
end
Algorithm 2: Action Choices for Leader
Input: Leader's policy μ4
Output: goals g and bonuses b;
for k E N do
sample the termination function 3h: if 188 terminates previous leader's action w then choose new action wf:
5
else
w w
// maintain previous action.
19

---

Published as a conference paper at ICLR 2020
spont
obstado
prodator
resnurce
landmark
pray
(a) Resource Collections
(b) Navigation.
(c) Predator-Prey
Multi-bonus Resource Collec- tions. This figure is inspired by
Shu & Tian 2019).
Figure 5: Illustration of different tasks.
D EXPERIMENT DETAILS
D.I TASKS DETAILS
The illustration of experimental scenarios be found in Figure Here we give some details about these environments:
Resource Collections. This task is similar to (Shu & Tian 2019). which is based on the scene that the leader and the followers collect some resources. Each follower has its own preference which might be the same (or against) the leader's preference. In order to make the followers obey the leader's instruction, the leader should pay the followers bonuses. There are total 4 types of resources and for different resources each agent has different preferences. The leader owns type of bonus (1 or 2) and types of goals (each resource a goal). The number of leader is 1 while the number of followers is 4.
Multi-Bonus Resource Collections. This task is similar to Resource Collections. Except that the leader can take level bonuses bonus from to 4) while each agent owns one skill. The number of leader is 1 while the number of followers is 4.
Modified Navigation. This task is original from (Lowe al. 2017). We make some modifications here to make it suitable our SMG: the leader and the followers are going to navigate some land- marks. Each follower has own preference which might be the same (or against) to the leader's preference. When a landmark has been navigated, it disappears immediately and new landmark will appear. There are total 6 types of landmarks and for different landmarks, each agent has differ- ent preferences. The leader owns two type of bonuses and types of goals (each landmark is goal). The number of leader is while the number of followers is 8 and the number of the landmarks is 6.
Modified Predator- Prey. This task is also original from (Lowe al. 2017). We make some modifi- cation here to make it suitable our SMG: the leader and the followers are going to catch some preys. Each follower has its preference which might be the same (or against) to the leader's preference. In each step, whether a prey has been caught, it randomly chooses a direction to go. Catching a prey will not make it disappear, which means that the preys can exist until the game ends. There total 8 types of preys and for different preys, each agent has different preferences. The leader owns two type of bonuses and 8 types of goals (each prey is a goal). The followers are faster than the preys. The number of leader is while the number of followers is 10 and the number of the landmarks is 8.
Reward Design. The rewards mentioned in Section 3 are the general forms. Here, we define two specified forms of the leader and followers reward function in our experiments:
Leader Reward. We define vy the prize (utility) for finishing task g. We the reward function for the leader at step as: rf Eges Etex (g - gft) (I (s sg) Vy bt). formulated by the total gain EgeG ExEN I (g g: (s - = sn) vg (the total prizes got by the leader at time f) minus the total payment Eges EkeN (g ..:) by (the total bonuses paid the followers). We should
20

---

Published as a conference paper at ICLR 2020
emphasize that our leader reward is total different from the (Shu & Tian 2019): in their approaches, the leader changes its mind after signing a contract will not be punished. To make suitable to the real world, we modify the reward as the leader should pay the followers bonuses immediately after signing the contract and cannot get back if it gives up the contract.
Follower Reward. For the followers,
set the reward for the k-th follower as: r. - -g
(ux.g II (sf= sg) + (o) = gf) x b)), where uk.g reveals the payoff of the k-th follower when finishing task g (the preference). Specifically, rf indicates that the follower can either follow the leader's instruction or just do what prefers to. The followers will receive reward immediately after signing the contract (the leader and the followers achieve an agreement). T (s sy) means that the follower finishes the task ! at step A penalty is added to the followers if the followers betray the leader (the followers and the leader sign the contract but the followers do not agree to work).
D.2 TRAINING DETAILS
D.2.1 NETWORK DESIGN
Our network is based on (Shu & Tian 2019). Some do not suit our method. We do some modification here: (1) We change the vanilla attention mechanism (sum/average all the history and action of each follower together) to a follower selloeer-ppeified one: each follower has a weight which indicates how important the follower is at the current step. (2) The output for 9 and b are changed into the sequential form, i.e., we first calculate p(ght (c)) to get gf then based on of we choose p(b gg. ct). (3) The history information hy is compressed by the LSTM (Gers et al., 2000).
Leader's Network. For the history information, we are willing to stress that the history consists of two parts, one is the statistical information similar to (Shu & Tian 2019) and the other is the past information given by the neural networks. We leverage the LSTM with 128 hidden units and two fully-connected layers to compress the past information and the statistical information and obtain hR. Each layer contains 128 neurons.
For the state information, we encode it into 128ddimension hidden state by a state encoder. For resource collections task, the state encoder consist of a convolutional layer with 64 channels and kernels of 1 xx1 and two fully connected layers with 128 neurons. For navigation and predator-prey task, we encode the state using two fully connected layers with 128 neurons.
For the follower-specte attention module, we firstly predict the a from the follower-aware mod- ule which contains an LSTM with 128 hidden units and two fully-connected layers with 128 neu- rons. Secondly, we transform at. h and the output of the state encoder into A(st, at ht) using a fully connected layer with 128 neurons. The hidden vector is generated by concatenating all the A(s,, at, htt) Then the attention weight max activation. The c is calculated as weighted summation of w and A(-). Finally, we obtain the k-tth attention value of by concatenating e, and A(st, at. hT)).
calculated using two fully connected layers with soft-
For sequential graph-based model, we firstly calculate p(g" (ct) using two fully connected layers. Each layer consists of 128 neuron units. The input of layers is of and the output is of Then we obtain By by two fully connected layers. The input of layers is the concatenation of oe and gf"
Follower's Network. We construct the RL-based followers by state encoder and two fully con- nected layers. Each fully connected layer contains 1 128 neurons. For resource collections task, the state encoder consists of a convolutional layer with 64 channels and kernels of 1x 1, two fully con- nected layers with 128 neurons and an LSTM with 128 hidden units. For navigation and predator- prey task, we encode the state using two fully connected layers with 128 neurons and an LSTM with 128 hidden units. Notice that the network structure of abbttrnnasttttiinnnnn Ra-based follower and non-action-ale abstraction RL-based follower is similar. The only difference is that the output of the former is high-level action z and the output of the latter is low-level action of.
21

---

Published as a conference paper at ICLR 2020
120
17.5
Ours
Ours w/o EBPG
Ours w/o Attention
M'RE"
12.5
Incentive
Incentive
50
7.5
Ours
Ours w/o EBPG
Ours Attention
2.5
M RL
50000
100020
150000
200303
250000
200000
250000
Episodes
Episodes
(a) Total incentive for the predator-pre prey task (rule- based agent).
(b) Total incentive for the colti-bonus task (rulc- based agent).
Figure Total incentives for predator-prn prey task and multi-bonun resource collections task.
70
17.
Ours
Incentive
Ours
25.0
40
12.5
Attention
Attention
M RL
MRRL
20
5.0
50000
100000
150000
200003
250000
50000
100000
150000
200000
Episodes
Episodes
(a) Total incentive for the resource collections task (rule-based agent).
(b) Total incentives for the navigation task (rulc- based agent).
Figure Total incentives for resource collections task and navigation task.
D.3
MORE EXPERIMENTAL RESULTS
D.3.1 TOTAL INCENTIVE FUNCTION
Total incentive (income) functions R = E Σ. by can reveal how well the leader interacts with the followers; the higher the Rin is, the more successful the coordination between the leader and the followers.
From Figure 6 and comparing with the state-of-the th--r-r method, we can see that our method far outperforms the state-of-the-art method, which reveals that our method does have a better ability to coordinate with the followers. In all of the scenarios, without the EBPG, the performance of our method is worse than ours with EBPG. Specifically, collections, navigation), without the EBPG, the performance of our method is (or nearly) similar to the performance of RL showing the effectiveness of our novel policy gradient. Moreover, we can notice that in navigation environment, without follower-specifie attention, the performance of our method diminishes rapidly, which implies that in some scenarios, attention does play an important role.
some scenarios (e.g., multi-bonus resource
22

---

Published as a conference paper at ICLR 2020
Reward
Incentive
12.5
10.0
-40
7.5
Ours
Ours Sparse EBPG
Sparse EBPG
Sparse EBPG Attention
Sparse EBPG w/o Attention
100020
150000
250000
150000
200000
250000
Episodes
Episodes
(a) The reward curves for multi-bonus resource collections.
(b) The total incentive curves for multi-boma re- source collections.
Figure 8: The ablation study sparse EBPG in the multi-bonus resource collections task.
-30
Reward
Incentive
80
-100
-150
Ours
Ours
-200
Sparse EBPG
20
Sparse EBPG
Sparse EBPG w/o Attention
Sparse EBPG w/o Attention
50000
100020
150000
Episodes
Episodes
(a) The reward curves for predator-prey.
(b) total incentive curves predator-prey.
Figure 9: The ablation study of sparse EBPG in the predator-prey, task.
D.3.2 ROBUST OUR METHOD
In this section, our method is robust to the noise. We make this experiment by introducing noise into the follower decision. For example, if set the noise function as 30%, indicating that there is 30% probability that the followers will choose action randomly.
going testify the robust of method. Specifically, evaluate whether
D.3.3 SPARSE EVENT-BASHD POLICY GRADIENT
This experiment testifies whether the dense event-based policy gradient increases the leader's per- formance comparing with the sparse event- event-based policy gradient. We make ablations here: (1) Ours: the full structure of our method; (2) Sparse Event-Based Policy Gradient (sparse EBPG): the fully structure of ours except that the EBPG is replaced by sparse event-based policy gradient; (3) sparse EBPG w/o attention: replacing the follower-specified attention mechanism by averaging the input features.
From Figure 8 and 9 we can find that if the policy gradient is sparse, its performance is worse than the dense one, implying that the dense method does improve the leader's performance. There is also an interesting phenomenon that sparse EBPG with follower-specified attention mechanism performs better than that without, revealing that the attention can stabilize training when the training signal is sparse.
23

---

Published as a conference paper at ICLR 2020
6.3
Feleers Feltwerd
Blower
Rlover
Blowerd
Moowr
AMarson We
Commito Toloner3
Folowrr2
Gennel 3alkeer
(a)
(d)
Figure 10: Visualization of the attention. The x-axis indicates the commit time for different agents and the y-axis indicates corresponding weights w when the leader commits to that agent.
10
7.
5.0
Reward
Reward
-25
Ours (different tearning-rate)
Ours [different learning -rate)
Ours (same learning-rate)
-10
Ours (same learning-rate)
M RR (different learning-rate)
M (different leamiin--rate)
-15
M (same learning-rate)
M (same learning-rate)
-100
50000
100000
150000
250000
-20
100000
150000
200000
250009
Episodes
Episodes
(a) The ablation study of reward for time-scale update method (one RL--hased fol- lower).
The ablation study of reward for
time-scale update method (two Rl--based follow- ers).
Figure 11: The ablation study of reward curves for two time-scale update method in resource col- lections task.
D.3.4 VISUALIZING ATTENTION
Following the logic of (gaall & Sha 2019), visualize the weight of the attention when the leader takes actions. From Figure 10 we find that the attention mechanism does learn to strongly attend the followers that the leader needs take actions. The followers with leader's commitment obtain much higher attention weight than others, showing that the attention module actually learn to identify the important followers while leader committing new action. Thus, the attention mechanism does play an important role in improving the performance.
D.3.5 TWO TIME-SCALE UPDATING
In order evaluate the performance our two time-scale update scheme (TTSU), we do an ablation study as shown in Fig 11 We can find that the performance where the followers' learning rate (1 10-3) much larger than the leader's 3 x 10- better than the performance where the leader's learning rate is similar the followers (1 10-3). Morcover, without TTSU, the reward curves of training methods become unstable, revealing that TTSU can stabilize the training process. In fact, TTSU improves the rate of convergence and play important role in improving performance.
D.3.6 COMMITTING INTERVAL
We evaluate the leader's performance between static committing interval and dynamic commit- ting interval. As shown in Figure [2, we observe that all the different fixed committing intervals only change the rate of convergence and do not enhance the leader's performance. All the fixed
24

---

Published as a conference paper at ICLR 2020
-20
-50
Dynamic committing interval (ours)
Reward
-40
Reward
-75
step committing interval (M*RL)
committing interval RM)
-100
Dynamic interval commit (ours)
6 step committing interval (M*RU
-129
step interval commit (M (M)
-80
step interval (M RRL)
step interval commit (ML)
50000
100020
150000
200303
250000
150000
200000
250000
Episodes
Episodes
(a) The ablation study of reward curves for differ- ent committing interval in resource collections.
(b) The ablation study of reward curves for fixed committing interval method in navigation.
0
-20
Dynamic committtnng interval (ours)
Reward
-40
Reward
-100
step committing Interval (MFRL)
-10
-150
step committing interval (M*RL)
Dynamic interval commit (ours)
6 step committing interval (M*LL)
-30
step Interval commit (M PRL)
step interval commit (M (RL)
-250
step interval commit (M RRL)
-300
50000
100020
150000
200000
250000
23000 50000
75000 100000125:00110000000 175000 200000 Episodes
Episodes
(c) The ablation study of reward curves for fixed committing interval method in multi-bonus re- collections.
(d) The ablation study of reward curves for fixed committing interval method in predator-prey.
Figure 12: The ablation study of reward curves for fixed commitment time in resource collections task.
committing intervals are much worse than our dynamic committing approach, revealing the fact that our dynamic committing approach aids a lot in improving the leader's performance.
Table 2: Ablation results of RL-based followers for resource collections. means the module is used.
Modules
EBPG
Leader-follower consistency
Action abstraction policy gradient
/
/
Final reward
8.12
6.26
4.18
3.48
-0.02*
-0.03*
-0.05*
-0.05*
* The last four terms are so close to zero and we use the rewards from last episode as the final results.
D.3.7 REWARD FOR RL-BASED FOLLOWERS
We are interesting in the reward for the RL-based follower(s). Intuitively, a well- well-performing leader make the follower gain more. As shown in Figure [3] the reward for RL follower is higher than RL follower in all the tasks. This represents the leader can coordinate the followers better and make them gain more reward than other methods, which forms win-win strategy.
25

---

Published as a conference paper at ICLR 2020
PPLL
Rowerd
(a) Resource Collections. (b) Multi-Bonus Resource
(c) Navigation.
(d) Predator-Pres Prey.
Collections.
Figure 13: Reward curves for RL-based followers in different tasks.
Ou
Towere
Toware
Oura Dan disttiiee)
speradic
00.00005
(a) Resource Collections,
(b) Manti-Bonus Resource Collections.
(c) Navigation.
(d) Predator-Prey.
Figure 14: Leader's reward curves for different tasks (RL-based followers).
D.3.8 NUMBER THE FOLLOWER AGENTS
Finally, we evaluate the leader's performance with different number RI--based followers. shown in Figure 15 we find that method outperforms the state-of-the-art method when facing different number of RL-based workers.
D.3.9 DIFFERENT COMBINATIONS STUDY
To further illustrate the performance of different combinations of our methods, we make an extra ablation here. We choose the resource collections as the environments. Our analysis is as follows:
For the RL based followers scenario, shown in Table 2 we find that the action abstraction policy gradient is very important to converge. Additionally, adding different modules can improve the performance and the method with all the modules reach the highest reward than other combinations. The contribution ranking for each module is: Action abstraction policy gradient > EBPG Leader- follower consistency.
4. Reve
Tunur
(a) Resource Collections,
(b) Multi-Bonus Bonus Resource Collections.
Navigation.
(d) Predator Precy.
Figure 15: The final reward of different number of follower agents in different tasks.
26


Reviews:
[{"review_id": "Skx4ZTo2YH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper aims to improve the performance of leader agents in leader-follower Stackelberg Markov games (SMG) by introducing architectural components. an event-aware policy gradient for the temporally abstracted level of the leader, and a follower abstraction technique that mitigates the impact of follower distributional shift. The authors show significant improvements over the state of the art on several problems, and also evaluate the importance of the different components of their approach with thorough ablations.\n\nI am not particularly familiar with the literature on SMGs, but I recommend this paper for acceptance. The architectural components (follower-wise attention), dense policy gradient, and follower-level abstractions are well-motivated, and the evaluations are extremely thorough. The supplementary material is longer than the main paper, and almost half of it is additional results.\n\nThe paper could be improved with more discussion of the applications of SMGs, although this could be due to my relative unfamiliarity with the area. For example, this seems immediately relevant to hierarchical RL problems that involve learning to coordinate multiple skills where the optimal subpolicies are incompatible, e.g. multi-robot coordination (or multi-limbed single robot coordination) with collisions. More discussion of the concrete applications would be informative.\n\nAlthough I am not intimately familiar with the research area of SMGs, I expect this work will have significant impact in the area on the basis of the thoroughness of the results alone.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "S1ljILl2FH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper proposes an interesting event-based policy gradient algorithm for single-leader multi-follower Stackelberg Markov Games (SMG). The authors claimed 3 contributions on their work: model the leader's decision-making process as a semi-MDP and proposed an event-based policy gradient algorithm for the leader to consider long-term effect; exploit a leader-follower consistency scheme with a follower-aware module and a follower-specific attention module to better predict the follower's behaviors; and propose an action-abstraction policy gradient algorithm in order to make SMG easier to converge.\n\nThe proposed model is interesting and the authors have done sufficient empirical studies to show the success of their method, as well as some necessary theoretical derivations. My major concern about this work is whether the task that this paper follows is widely studied in the reinforcement learning community, as the authors mentioned that only [1] can be used as baseline methods since the other methods can not be applied in their problem. But in general I think this is an interesting paper. Some detailed comments and suggestions:\n\n1. This paper proposed 3 major contributions: event-based policy gradient, leader-follower consistency scheme and action abstraction policy gradient. The authors show the empirical performance comparison for the case with and without each of these techniques in the experiments. It can be seen that all of the 3 techniques help the proposed method perform better. In addition, the proposed method performs better compared to the state-of-the-art method (in [1]). Hence the authors have shown the success of their algorithm empirically. One thing that can be done to improve this paper is to show a joint comparison for the 2 ^ 3 = 8 cases of with / without any of the 3 techniques so that we can gain a better understanding about the effect of these 3 techniques.\n\n2. The authors provide some necessary theoretical derivations to compute the policy gradients. But there are some typos in the equations. For example, the numerator of the equation of the case e_i^k\\not\\in A_T in I(e_i^k) at the bottom of page 4 is incorrect. In addition, the equation on the second last line of page 3 should be P_\\gamma(s_{t+1}, \\omega_t, a_t | s_t, \\omega_{t-1}), not P_\\gamma(s_{t+1}, \\omega_t | s_t, \\omega_{t-1}, a_t).  Please check the details and solve these typos.\n\n3. It will be better if the authors can provide more theoretical analysis or quantitative explanation about the proposed method. For example, why a dense EBPG better than a sparse one? Why the equations in the attention mechanism appear in their form, not some similar forms (e.g. scale the values from the function A before putting them into the softmax function)? Intuitively the proposed techniques make sense, but it will be great if more insights are provided.\n\n4. As I mentioned, I am concerned if the proposed problem is widely studied in the reinforcement learning community. Also, since the authors mentioned in the appendix that two of the tasks are original from [2], but we can not apply the method in [2] as a baseline method. It is possible to modify the method in [2] to fit with the setting and compare with them?\n\n5. It will be better if the authors can rearrange the paper for a little bit, since there are too many important details (e.g. experiment settings, assumptions in the theorems) are in appendix.\n\nQuestions:\n\n1. Can the authors try to modify the method in [2] and compare with it (details in my comment 4)?\n\nReference:\n\n[1] Tianmin Shu and Yuandong Tian. M3RL: Mind-aware multi-agent management reinforcement learning. In ICLR, 2019.\n\n[2] Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAI Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-competitive environments. In NeurIPS, pp. 6379–6390, 2017.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "BylAQBSCFS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "1. Summary\n\nThe authors apply MARL to principal-agent / mechanism design problems where selfish agents need to be incentivized to coordinate towards a leader's (collective) goal.\n\nThe leader is modeled as a semi-MDP with event-based policy gradients and modules to model/predict followers' actions. The leader sends messages to followers, an \"event\" is a pair (timestep, message of leader to a follower).\nA `termination' menas that an agent should stop executing the previous selected action; the leader signals as such to the agent.\nWith this modeling step, the authors formulate an event-based policy gradient, which considers models for which goal to send to followers and when.\n\nThe authors compare this approach on 4 environments with M3RL, which also solves (extensions of) principal-agent problems.\n\n2. Decision (accept or reject) with one or two key reasons for this choice.\n\nWeak accept.\n\n3. Supporting arguments\n\nThe approach seems sound and conceptually related to a multi-agent generalization of STRAW https://arxiv.org/pdf/1606.04695.pdf, where a planner predicts / commits to an action-plan for a single agent.\n\n4. Additional feedback with the aim to improve the paper. Make it clear that these points are here to help, and not necessarily part of your decision assessment.\n\n5. Questions", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper tackles the challenge of incentivising selfish agents towards a collaborative goal. In doing so, the authors propose several new modules. 

The reviewers commented on experiments being extremely thorough. One reviewer commented on a lack of ablation study of the 3 contributions, which was promptly provided by the authors. The proposed method is also supported by theoretical derivations. The contributions appear to be quite novel, significantly improving performance of the studied SMGs.

One reviewer mentioned the clarity being compromised by too much material being in the appendix, which has been addressed by the authors moving some main pieces of content to the main text. 

Two reviewer commented on the relevance being lower because of the problem not being widely studied in RL. I would disagree with the reviewers on this aspect, it is great to have new problem brought to light and have fresh and novel results, rather than having yet another paper work on Atari. I also think that the authors in their rebuttal made the practical relevance of their problem setting sufficiently clear with several practical examples. 
Decision: Accept (Poster)