Revisiting Higher-Order Gradient Methods for Multi-Agent Reinforcement Learning
Authors: Ariyan Bighashdel
Daan De Geus
Pavol Jancura
Gijs Dubbelman
Venue: Submitted to ICLR 2023 (2023)
Keywords: Multi-agent reinforcement learning
Higher-order gradient-based optimization

Abstract: This paper revisits Higher-Order Gradient (HOG) methods for Multi-Agent Reinforcement Learning (MARL). HOG methods are algorithms in which agents use higher-order gradient information to account for other agents' anticipated learning, and are shown to improve coordination in games with self-interested agents. So far, however, HOG methods are only applied to games with low-dimensional state spaces due to inefficient computation and preservation of higher-order gradient information. In this work, we solve these limitations and propose a HOG framework that can be applied to games with higher-dimensional state spaces. Moreover, we show that current HOG methods, when applied to games with common-interested agents, i.e., team games, can lead to miscoordination between the agents. To solve this, we propose Hierarchical Reasoning (HR) to improve coordination in team games, and we experimentally show that our proposed HR significantly outperforms state-of-the-art methods in standard multi-agent games. With our contributions, we greatly improve the applicability of HOG methods for MARL. For reproducibility, the code used for our work will be shared after the reviewing process.

Under review as a conference paper at ICLR 2023
REVISITING HIGHER-ORDER GRADIENT METHODS FOR MULTI-AGENT REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
This paper revisits Higher-Order Gradient (HOG) methods for Multi-Agent Rein- forcement Learning (MARL). HOG methods are algorithms in which agents use higher-order gradient information to account for other agents' anticipated learn- ing, and are shown to improve coordination in games with self-interested agents. So far, however, HOG methods are only applied to games with low-dimensional state spaces due to inefficient computation and preservation of higher-order gra- dient information. In this work, we solve these limitations and propose a HOG framework that can be applied to games with higher-dimension Moreover, we show that current HOG methods, when applied to games with common-interested agents, i.e., team games, can lead to miscoordination among the agents. To solve this, we propose Hierarchical Reasoning (HR) to improve coordination in team games, and we experimentally show that our proposed HR significantly outperforms state-of-the-an methods in standard multi-agent games. With our contributions, we greatly improve the applicability HOG methods for MARL. For reproducibility, the code used for our work will be shared after the reviewing process.
state spaces.
INTRODUCTION
In multi-agent systems, the paradigm of agents' reasoning about other agents has been explored and researched extensively (Goodie et al. 2012 Liu & Lakemeyer) (02T). Recently, this paradigm being studied in the subfield of Multi-Agent Reinforcement Learning (MARL) (Wen al. 2019 22200 Konan et al., (2022). Generally speaking, MARL deals with several agents simultancously learning and interacting an environment. In the context of MARL, reasoning can be interpreted as accounting for the anticipated learning of other agents (Zhang & Lesser 2010). As MARL uses gradient- based optimization, learning anticipation naturally leads the usage of higher-order gradient information (Letcher et al.) 2019). The so-called Higher-Order Gradient (HOG) methods use this extra gradient information to predict and, some cases, shape the learning of other agents [Letcher et al. 2019). The importance of prediction and shaping has been frequently shown for various games, such as the Iterated Prisoner's Dilemma (IPD), where shaping ensures cooperation among the agents (Foerster et al.] 2018a). However, current HOG methods have clear limitations, as they can only work for specific types of games, and become inefficient when the dimensionality of the game increases. In this paper, we explore these limitations and propose a framework that can extend the application scope of HOG methods to a broader range of problem settings in MARL.
The vast majority of existing HOG methods focus only games with low-dimensional state spaces, e.g., matrix games (Foerster et al. 201 by Willi et al. 2022). There are two challenges that limit HOG methods from being applied games with high-dimensional state spaces: inefficient compu- tation and preservation of higher-orde gradient information. Specifically, current implementations of HOG methods require multiple data sampling stages to compute higher-order gradient informa- tion (Foerster et al.] 2018b). Moreover, the higher-order gradient information is applied and, more importantly, preserved in the policy network's parameter space. As a result, existing HOG meth- ods become very inefficient when applied to games that have high-dimensional state spaces, and therefore require high-dimensional parameter spaces. In this paper, to solve this, we propose an HOG framework where the higher-order gradient information efficiently. By comparing our proposed framework to existing HOG methods in well-controlled studies, demonstrate that the overall performance and efficiency of our proposed framework stay
computed and preserved more

---

Under review as a conference paper at ICLR 2023
consistent with increased dimensionality, unlike for existing HOG methods, where they get drasti- cally worse.
In addition to dimensionality limitations, the generalizability of HOG methods to various types of games is questionable. Originally, HOG methods are proposed to improve cooperation in games with self-interested agents (Zhang & Lesser 2010, Foerster al. 2018ap. So far, however, it is unclear how HOG methods perform when agents are fully cooperative, i.e., for common-interested agents in team games. We demonstrate that existing HOG methods have the tendency to lead to miscoordination among common-interested agents, causing a sub-optimal overall reward. To solve this, and improve the applicability of HOG methods team games, we propose Hierarchical Rea- soning (HR), a new HOG methodology explicitly developed for improving coordination in games with common-interested agents. Below, we summarize our contributions.
We propose HOG-MADDPG, framework to make existing HOG methodologies, e-g.- LA and LOLA, applicable to games with higher-dimensional state spaces by solving the limitations in computation and preservation of higher-order gradient information. With our framework, we develop two novel HOG methods, LA-MADDPG and LOLA-MADDPG, which apply the principles of LA and LOLA, respectively.
We demonstrate theoretically, in two-agent two-action coordination game, and empiri- cally, in two-agent three- aaceencttinn coordination game, that the existing HOG methodolo- gies can suffer from miscoordination among common-interested agents. To solve this, we propose the HR methodology and show, theoretically and empirically, that it overcomes miscoordination in the coordination games.
We apply the HR principle to our HOG-MADDPG framework and develop HR-MADDPG, a HOG method for common interested agents. We show that HR-MADDPE outperforms the existing state- of-tthe-rt methods on standard multi-agent games.
2 RELATED WORKS
When direct communication among agents is not possible, the standard tool for MARL agents to apply reasoning is Agents Modeling Agents (AMA) (Albrecht & Stone 2018). Although agents traditionally use AMA only predict the behavior of others (He et al.) 2016; Hong et al.) 2018), recent studies have extended AMA to further consider multiple levels of reasoning over the predicted behaviors (Wen et al. 2019 2020). However, these approaches do not explicitly account for the other agents' anticipated learning, which has shown to be beneficial in games where interaction among self-interested agents naturally leads worst-case outcomes (Foerster et al. 2018a).
HOG methods, on the other hand, are a range of methods that use higher-order gradient informa- tion to predict and, in some cases, shape the anticipated learning of other agents directly. This includes Learning with Opponent-Learninn better coordination Iterated Prisoner's Dilemma (IPD) by Foerster et al. (2018a), Look-Ahead (LA),, proposed to guarantee convergence in cyelic games by ZZhan & Lesser (2010), Stable Op- ponent Shaping (SOS), developed by Letcher et al. (2019) as an interpolation between LOLA and LA to inherit the benefits of both, and other methods such Consensus Optimization (CO) and Symplectic Gradient Adjustment (SGA), that are proposed to improve cooperation by Bertsekas (2014) Balduzzi et al.) (2018), respectively. However, as we explain in Section 4 these methods have only been applied to simple games due to the challenges in computation and preservation of higher-order gradient information. Furthermore, the impact of current HOG methods coordina- tion among common-interesee are limited to convergence and non-convergence to stable and unstable fixed points in differential games, respectively (Letcher et al. 2019). However, we demonstrate in Section [.] that in the case of a two-agent, two-action coordination game with unstable fixed points, HOG methods can con- verge to miscoordination points. The focus of this work is to extend current HOG methodology so that it can be used for games with nigher-dimension state spaces and common-inter interesstet agents.
Awareness (LOLA), proposed to shape opponents for
agents has not yet been fully investigated. Current investigations
3 BACKGROUND
We formulate the MARL setup as a Markov Game (MG) Littmann 1994.. An MG is a tuple
(W,S, (Ailien, (Ri)ieN; T,, P, 7), where A is the set of agents ([W n), S is the set of states,
2

---

Under review as a conference paper at ICLR 2023
and A, is the set of possible actions for agent E N. Agent i chooses its action a, A, through the policy network ne, : S x A, + [0,1] parameterized by 8 conditioning on the given state S. Given the actions of all agents, each agent i obtains reward r; according to its reward function R₃ : S x Ai x... x An + R. Given an initial state, the next state is produced according to the state transition function T
S. We denote an episode of horizon A1 ... An
I' as r = ((s", ai.... ..., on T aa:.... ...9 {s ai y 2f T y...
( (T)) and the discounted return for each agent i at time step < T is defined by (T) EE 2 "T; where r is predefined dis- count factor. The expected return given the agents' policy parameters approximates the state value s)]. Each agent aims to maximize the expected return given the distribution of the initial state p(s), denoted by the performance objec- tive Jj p(s) (s, 01,..., 0n) ) A naive agent updates its policy parameters in the direction of the objective's gradient: J. Ep(s) V.. 0,).
function for each agent Vi(s, . 0n) (T
Learning With Opponent-Leane Learning Awareness (LOLA). Unlike naive agents, LOLA agents modify their learning objectives by differentiating through the anticipated learning steps of the op- ponents (Foerster et al.) 8a). Given n = 2 for simplicity, a first-order LOLA agent assumes a naïve opponent and optimizes VIOOA f1, 82 A02) where A02 V, (s, 0,, 02) and 1) is the prediction length. Using first-order Taylor expansion, and by differentiating with respect to 0,, the gradient adjustment for the first LOLA agent (Foerster al. 2018a) is given by
V 11 LOLA (s, 0,.01,02 02 + A02) R Vo, V1 + (Vozo, A1) + (Vo, A02) VI,
shaping
where V1 (s, 01000.00.. 02). The rightmost term in the LOLA update allows for active shaping of the opponent's ' learning. This term has been proven effective in enforcing cooperation in various games, including IPD (Foerster et al. 2018a b). The LOLA update be further extended to non-naïve opponents, resulting in higher-order LOLA agents (Foerster et al. 2018a Willi et al.) (022).
Look Ahead (LA). LA agents assume that the opponents' learning steps cannot be influenced, i.e., cannot be shaped (Zhang & Lesser 2010: Letcher et al.) 2019). In other words, agent assumes that the prediction step, At2, is independent of the current optimization, i.e., Vo, A02 0. Therefore, the shaping term disappears and the gradient adjustment for the first LA agent will be
Vo, V1 (s, + A02) x Vo, Vi + (Vago, A12
A HOG FRAMEWORK FOR HIGH-DIMENSIONAL STATE SPACES
Existing HOG methods like LOLA and LA are only applied to games with low-dimensional state spaces, e.g., matrix games (Zhang & Lesser 2010: Foerster et al., 2018b a Letcher et al. 2019 Willi et al., 2022). When applied to games with higher-dimensional state spaces, they become very inefficient, due to the way the higher-order gradient information is computed and preserved. In this section, we analyze these problems, and we propose a framework that makes HOG practical for application to games with high-dimensional state spaces.
4.1 LIMITATIONS OF EXISTING HOG APPROACHESS
Computation of higher-order gradient. Existing HOG methods are implemented in the stochastic policy gradient framework, and optimize non non-differentiable objectives. Furthermore, the learning step for one agent in the standard stochastic policy gradient theorem is independent of other agents' parameters. Therefore, higher-order mixed partial derivatives (among multiple agents) cannot be easily computed. Foorster al. (2018b) proposed an infinitely differentiable Monte Carlo estimator, referred to as DiCE, to correctly optimize the stochastic objectives with any order of gradients. Similarly to meta-learning frameworks, the agents reason about and predict the learning process of the opponents using inner learning loops and update their parameters in outer learning loops. However, each learning loop for each agent requires a sampling stage which is very inefficient for high-order reasoning and games with nigher-dimension state spaces, i.e., beyond matrix games.
Preservation of higher-order gradient information. HOG methods should constantly compute and update the higher-order gradient values and computation graphs that keep track of how the
3

---

Under review as a conference paper at ICLR 2023
gradients should flow. In the implementation of existing HOG methods, the higher-order gradi- ent information is computed and preserved in the parameter spaces of the agents' policy networks (Foerster et al. 2018alb). As result, the agents should either have access to other agents' exact parameters or infer other agents' parameters from state-action trajectories (Foerster et al. 201 20) In many game settings, these parameters are obscured. Moreover, when the dimensionality of state spaces increases, c.g., when having images as input, the dimensionality of the parameter spaces in- creases as well, making the parameter inference problem computationally expensive. Furthermore, computing and storing the higher-order gradient information in high-dimension parameter spaces inefficient, whether the parameters are inferred or exact.
4.2 HOG-MADDPG
To efficiently compute any-order mixed partial derivatives, we need to optimize differentiable objec- tives, which are directly dependent on all agents' parameters and can be efficiently estimated. The only platform that meets the above requirements and can deal with both discrete and continuous ac- tion spaces is Multi-Agent Deep Deterministic Policy Gradient (MADDPG) (Lowe al.) (017)). In this platform, decentralized policies are trained to optimize centralized, differentiable objectives, i.e.. state-action value functions, that estimated efficiently from trajectories sampled from distinct behavior policy, i.e., the off-policy approach. Therefore, we propose to build our HOG framework on top of the MADDPG platform. Similarly to MADDPG, we follow the Centralized Training and Decentralized Execution (CTDE) setting in our work. However, differently from MADDPG, we better exploit the available information CTDE by accounting for the agents' anticipated learning-
The only unsolved problem is the preservation of higher-order gradient information, as the central- ized learning of MADDPG does not grant access to agents' parameters. To solve this, we propose to project the anticipated gradient information from the policies' parameter spaces to the action spaces. This way, 1) we avoid additional constraints above the centralized state-action value functions where the agents have access to all actions, and 2) we improve efficiency the action spaces have signif- icantly lower dimensionality than the policies' parameter spaces. In Appendix we thcoretically analyze the influence of the proposed projection concept the overall performance (Appendix BB.I). and the time complexity of gradient anticipation (Appendix [B.2). In the following sections, we ap- ply our proposed framework to two HOG methods and explain the details of their update rules for policy parameters. For all proposed methods in the HOG-MADDPG frameworks, the centralized state-action value functions are updated in way identical to MADDPG (Lowe et al. 2017).
4.2.1 LA-MADDPG
In the MADDPG platform, a deterministic policy Me for agent i is defined as μle S - A₁, parame- terized by 0,. By denoting centralized state-action function for each agent i as (, 01, ..., an) (rlst s, aj = a.Vi E A/),, the gradient of the MADDPG performance objective Jj with respect 0g can be approximated as:
V RJ (s,))) Vo, Qi(s, (i,, .... Ci ..., an)la.=po,
where (s, a) is the state-action distribution of the behavior policy and = (á.Vi E A are the actions sampled from the behavior policy during the exploration stage. Given 2 and naive opponent for simplicity, the gradient adjustment for parameters of the LA-MADDPG agent (01) is computed by accounting for the anticipated policy parameters of the opponent, i.e., 6₂ + Ad2(s):
V J. Rs Epe(s) Vo, Qi(s, 01, la
=uo, (s). (8)
(4)
where A02 = V/ & Q2 âi, (2) م2)1ā (6) (e) and 0, and 02 are the behavior policy param- eters. As the agents cannot have access these parameters, we propose to project the anticipated gradients to the action space (see Appendix A.D
Vg, JLL ~ E (s.aa VA, Ha, (s) V. (i a, à2 + ddz) my mpo (s).
(5)
where Ad2 viV WVaaQ(s, 01, 22) and is the projected prediction length (see Alg. 1
4

---

Under review as a conference paper at ICLR 2023
MADOPG
CFG MADOPG
MADORG
LOLA MAPOPG (ours)
LA loun!
Method
IRG (DIE. L)
LA-DiCE
0.09:10.07
LA-MADDPG (ours)
0.03:10.02
Method
IPD (AER f)
LOLA-DiCE
-2.16:10.12
LOLA-MADDPG (ours)
-2.08:10.02
044
106
303
300
500
100 15
23
Table 1:
Comparisons of the LA and LOLA methods in the frame- works of DiCE and our proposed ROG-MADDPG
Figure 1: Learning curves in two matrix games. Left: Iterated
Rotational Game in terms of the distance the equilibrium point (4). Right: Iterated Prisoner's Dilemma in terms of the normal- ized averages return (t).
4.2.2 LOLA-MADDPG
In the standard MADDPG, is assumed that the opponents' actions are fixed during the optimization steps for the agents. This assumption is problematic for LOLA agents that require shaping on the opponents" learning steps. To make these dependencies possible, we employ the Centralized Policy Gradient (CPG) (Peng et al. (021) to derive the learning step of the LOLA agents. In CPG-
MADDPG, the gradient update in Eq. (3) is modified to:
Vo ~ E pP(e) V Qi(s, ai,.... "1,,..,G))l,; po, WEE.
Again, we propose to project the anticipated gradient information to the action space. Given = 2, the first-order LOLA-MADDPG agent updates the policy parameters through (see Appendix [A.2]:
Ve, J E, (s) V Me; Vs) Qi a1, a2 Aaz)ler=upp (1),11= (s))
where Aes V 02
a1, a1, which, unlike for LA-MADDPG, is function of a (see Alg. 2
4.3 EXPERIMENTS
In this section, we first verify our proposed HOG-MADDPG methods on simple matrix games, to show how they work in the same situations the original HOG methods. Second, we apply our proposed methods to games with high-dimension state spaces, which is the envisioned use case for methods, and evaluate the performance and efficiency. As the primary baselines, apply HOG methods on the DiCE framework (Foerster et al., 2018b), i.e., LA-DiCE and LOLA-DICE. We further compare our proposed methods with the standard MADDPG configured with three state- of-the-art update rules: 1) standard update rule (Lowe et al. 2017). referred to as MADDPG, 2) CPG update rule (Peng al. 202T), referred to as CPG-MADDPG, and 3) Probabilistic Recursive Reasoning (PR2) update rule (Wen et al.) 2019). referred to as PR2-MADDPG, For fair compar- ison, we have employed identical architectures with the same number of policy and value function parameters for all the baseline (see Appendix D).
4.3.1 MATRIX GAMES
We evaluate the methods on the following commonly-used, two-agent matrix games: 1) Iterated Rotational Game (IRG) (Zhang & Lesser 2010), one-state game with 1-Dimensional (1-D) continuous action space between 0 and representing the probability of taking two discrete actions, and 2) Iterated Prisoner's Dilemma (IPD) (Foerster al. 2018a). a five-state game with two discrete actions and T = 150. The games are developed to highlight the strengths of specific HOG methods (IRG for LA-based methods and IPD for LOLA). Further details about these games are provided in Appendix D.I We evaluate the performances of methods based on the Distance to Equilibrium (DtE) in IRG (the equilibrium point in IRG reached when 01 = a2 0.5) and the Averaged Episode Reward (AER) in IPD. In Figure we depict the learning curves for our methods and other, state-of-the-art MADDPG-based algorithms. From this figure, we find that our HOG methods are the only MADDPG-based networks that can effectively solve these games, with LA-MADDPG for IRG and information. To further show its effectiveness, (Foerster et al. 2018b) which are designed for these matrix games, in Table | and we find that we even achieve slightly better results.
for IPD. This highlights the importance of using higher-order gradient
compare with current DiCE-based HOG methods
5

---

Under review as a conference paper at ICLR 2023
MADDPG
MADORG
MADOPG
LOGA MADOPG
LA MADOPI
Co
1pieda
130
1081
230 3091
Syonnd
2997
1360
2000 "piods
2A0 3048 2003 100
(a) level one.
(b) Exit-Room level two.
(c)
level three.
Figure 2:
Learning curves in different complexity levels of the exit-room game in terms of the normalized average return. Higher values better.
1NAER Exil-Room game
LNTT in Exil-Room game
Methods
1=2 2
==3
Naive
Ist-order
2nd-order
Ard-order
4th-order
ROLA-DDCE
0.91=0.04
0.68=0006
0.56=#.11
2.39
3.74
5.12
6.41
LOLA M.A.DM (ours)
1.00 0.00
0.99+0001
0.93
1.03
1.05
1.08
1.12
Comparisons of DiCE with our proposed HOG-MADDPG in the Exit-Room game, in terms of performance (normalized average return in different game levels) and efficiency (training time per iteration in different reasoning levels).
Table 2:
4.3.2 MULTI-LEVEL EXIT-ROOM GAME
Inspired by Vinitsky et al. 2019), we propose an Exit-Room game with three levels of complexity (see Figure 3) The Exit- Room game is grid-world variant of the IPD, with two agents (blue and red), and is specifically developed to highlight the strength of LOLA. The agents should cooperate and move towards the exit doors the right. However, they tempted exit the left doors, and in some cases, not exiting at all. In level 1, the agents have three possible actions (move-left, move-right, or do nothing), and in levels 2 and they have additional move-up and move-down actions. Additionally, in level 3, the door positions are randomly located, resulting in more complex interactions among the agents. For more details about the game, see Appendix [)2
Figure 2 compares the learning curves of LOLA- MADDPG with the state-of-the-art, MADDPG-based methods in terms of Normalized Average Episode Re- ward (NAER) which the AER value that normal- ized between the highest and lowest episode rewards in each game level. Figure ? we can clearly see that our LOLA-MADDPG significantly outperforms the other methods, similarly as for the matrix games. To highlight the benefits of proposed method with respect ex- isting HOG methods, we compare our LOLA-MADDPG
Figure 3: State observation in the Exit- Room game, level one (left), level two (middle), and level three (right).
with LOLA-DiCE in terms of performance (by comparing NAER) and training efficiency, in Table For training efficiency, we use the average Training Time per Iteration (TTI) for various opponents reasoning levels. For fair comparison, we report Normalized TTI (NTTI) for both methods, which are the normalized TTI values with respect to naïve (zero-order) version of each method. Observ- ing Table 2 is apparent that LOLA-DiCE fails to acquire the highest rewards, particularly for the second and third levels of the game. where complexity is increased. Moreover, our proposed LOLA- MADDPG performs better all levels of the game terms of NAER, and scaling from naïve to higher-order opponents is significantly more efficient for LOLA-MADDPG than LOLA-DiCE. This emphasizes that we have overcome the limitations of HOG methods described in Section 4.1
A HOG METHODOLOGY FOR COMMON-INTERESTER AGENTS
Current HOG methods are proposed to enforce coordination in games with self-interested agents. In many applications, however, agents should cooperate to increase a common reward function, i.e., as team game. As multiple agents should interact and cooperate, anticipating the learning of other agents, which is the core idea of HOG methods, has the potential to work well in these types of games too. In this section, games, because they suffer from miscoordination. Subsequently, we propose a method to overcome this limitation, and evaluate it for several different games.
first show that standard HOG methods do not work well for team

---

Under review as a conference paper at ICLR 2023
5.1 MISCOORDINATION ANALYSIS IN COOPERATIVE SCENARIOS
To investigate the effectiveness of HOG methods on the coordination among common-interrsted agents, consider two-agent, two-action coordination game (Claus & Boutilier 1998) with an added miscoordination penalty. The game is defined by a common reward matrix I = [ where a 0 coordination reward and I 0 is the miscoordination penalty. We further define k > 0 as the miscoordination regret. The agents are parameterized by 01 E [0, 1] and 0g E [0, 1]. denoting the probability of choosing the first action by agent one and two, respectively. Similarly to (Singh et al. ) Zhang & Lesser (2010), we analyze the dynamics of 0₁ and 0g for LOLA, LA, and naive agents to investigate the coordination behaviors.
Theorem If. in the previously defined two-person, two-action coordination game with miscoor- dination regret g. the agents are updated following the LA method and a fixed prediction length n, then they are subject to miscoordination for g > 1/27. If the agents are updated following the LOLA method and a fixed prediction length then they are subject to miscoordination for >> 1/4n. If the agents follow the naive updates, then they are never subject to miscoordination, for any value of g. Proof - See Appendix C.I
A closer inspection of the HOG methods reveals two important aspects about their fundamental ideas. First, anticipating other agents' learning is only effective when it is close to their true future learning. Existing HOG methods assume reasoning level for other agents. If this assumption is wrong, it can negatively affect the coordination among the cooperative agents. Second, the idea of shaping other agents' learning can be misleading if the other agents do not follow, making agents more likely to suffer from miscoordination. We hypothesize that by addressing these two aspects of current HOG methods, miscoordination among agents can be avoided.
5.2 HIERARCHICAL REASONING
Based on our hypothesis, we propose Hierarchical Reasoning (HR), an HOG methodology espe- cially designed for cooperative agents. In contrast to standard HOG methods, HR determines a hierarchy among the agents in each training iteration, which determines the reasoning orders of the agents. Concretely, in = 2. and we assume that the first agent is the leader and the second agent is the follower, the gradient adjustment for the leader is similar to first-order LOLA agents, and is:
(8) where V= Vss, 02) is the common value function, and A02 vV V. However, unlike LOLA agents, the leader knows the reasoning level of the follower, which is a naïve agent. The plan for the leader is to change its parameters 01 01 + Ve, Vleaterss 01 82 + At2) in such a way that an optimal increase in the common value achieved, after its new parameters are taken into account by the follower. Therefore, the follower must follow the plan and adjust its parameters through
Vo, V Leader (s, 02 + A02) R Ve, V + (Voze, V)T + (Ve, V
Vo, Followerr (s, 02) = Vo, + (Vo,0, Vo, Leader (s, 01, 0g + A62),
Theorem If. in the previously defined two-person, two-action coordination game with miscoor- dination regret g, the agents are updated following the HR methodology, then they are not subject to miscoordiiattion for any value of g.
Proof - See Appendix C.2
With this. we have shown that HR naturally avoids miscoordination and therefore, our hypothesis is cor- rect. However, the main goal is to demonstrate that HR improves coordination among common- interested agents with respect to naive learning, which does not take into account higher-order gra- dients at all. If HR does not improve the coordina- tion, there is no clear benefit over the naïve learners, as they also avoid miscoordination. To show the benefits of HR, we employ a standard two-agent, three-action coordination game (Claus & Boutilier 1998). The game has common reward matrix
Rewand
Naivo
LOLA
HiM lours)
-20
50
100
150
200
2:00
300
Bagiee
Figure 4: Converged results for various val- ues of miscoordination regret.
10 0 &
R
0 2 6 and we define g = 10 l as the miscoordination regret. Each agent is parame-
k o 10
terized with three parameters: 01, 02 and @3 (0' 0 Vi (1,2,3) and Σ gi 1), representing

---

Under review as a conference paper at ICLR 2023
Action Updating
+ Any
Parameter Updating
Per B, (=)āa; del Vayy 06 mo
ii Sag
Vor - Eyr PoyMo, (s)dit
Reasoning
Vaay (60,2122))
A0; Oien, A2
ForJ"h Eptto Fo, (s)dn; da, Whe 0g.
du, = (oaaataa
Dil (2
Updaic Singe for agent
Updatte Siage for ugent
Update Stuge for agent
Figure 5: An example of the parameter update stages in HR-MADDPG, for a game with three common-interested agents = 3, assigned to three hierarchy levels.
the probability of taking the actions a², a², and a², respectively. The game has two global equi- librium points (if 01 or 6 = for all agents), and one local equilibrium point (if 0² for all agents). In Figure we depict the converged results for this game for naïve, LA. LOLA, and HR agents, for various values of miscoordination regret g. The experiments are run 500 times until convergence, with random initializations. From 4 we find that both LA and LOLA agents are sub- ject to miscoordination for high values of g. which is consistent with our findings for the two-action coordination game. However, the most interesting aspect of this experiment is that by increasing the value of g. the coordination among the naive agents reduces, leading them to the local equilib- rium point, whereas our HR agents consistently achieve the highest reward, independently of the miscoordination regret. This shows the benefit of HR agents over naïve agents.
5.2.1 HR-MADDPG
In this section, we propose HR-MADDPG, an extension of HOG-MADDPG for games with common-intereste agents and high-dimensional state spaces. We first define M C W, a set of common-interested agents such that R; = R Vi,j E M. Without the loss of generality, we consider M = N, i.e., team games with common state-action value function Q(s, o1...., am))
Hierarchy level assignment. In the policy update step of HR-MADDPG, each agent is first assigned to one of m |M levels of hierarchy based on the amount of influence that it has other agents, i.e. its shaping capacity, in each training iteration. The shaping capacity of the zth agent, fi, is the sum of 22-norms of the shaping term in Eq.
1 with respect to all other agents j:
fr Σ
(a, Va, Q(a1,...,
(10)
jti SALMES EM
where Aa;- = Vay Qua1,..., ..., a.). In each hierarchy level, the assigned agent is a leader of the lower hierarchy levels and a follower of the higher ones, with two reasoning rules: 1) a leader knows the reasoning levels of the followers and is one level higher, and 2) follower cannot reason about the leaders and only follows their shaping plans. As HR-MADDPG benefits from centralized learning, the only constraint for these reasoning rules remains the centralized state-action value function.
Parameter update. After the hierarchy level assignment, the agents update their policy parameters in update stages, i.e., one for each agent, and in top-down fashion: the agent in the highest hierarchy level updates its policy parameters first. In each update stage, the corresponding agent 1) reasons about the followers (if any) in bottom-up fashion, i.e., it reasons about the agent in the lowest hierarchy level first, 2) updates its policy parameters, and 3) updates its action for the next update stage (if any). Figure 5 demonstrates an example with the update stages for three common- interested agents 1, 2 and 3, that are assigned to hierarchy levels ht", hi,, 10", where agent 3, assigned to 3 is the leader, etc. For the case of m agents, see the MRDDDG update rules in Alg.
5.3 EXPERIMENTS
In this section, we aim to demonstrate the advantages of our proposed HR- MRDDDDDPG for games with common-interested agents, compared to 1) LA-MADDPG and LOLA-MADDPG and 2) state-of- the-art methods: MADDPG (Lowe et al. 2017). CPG-MADDPG (Peng et al.) 2021). and PR2- MADDPG (Wen et al. 2019). For this purpose, we first develop the Particle Coordination game to assess the coordination capability of the methods carefully. Then, compare the general perfor- mance of all the methods in standard multi-agent games (Lowe et al. 2017 Peng et al. 202I). See Appendix D.3 and D.4 for details on the experiments.
8

---

Under review as a conference paper at ICLR 2023
NNARR in Particle Environment
1NAER in Mujoco Environment
Methods
Cooperative Navigation
Physical Deception
Predator-Prey
Half-Cheetah
Walker
Reacher
DDPG
0.00
0.00
0.00
0.00
0.00
0.00
C-MADDPG (UB)
1.00
1.00
1.00
1,00
1.00
1.00
MADDPG
0.77
0.21
0.86
0.02
CPG-MADDPG
0.78
0.67
0.18
0.88
0.46
0.05
PR2-MADDPG
0.78
0,54
0,08
0.85
0.45
0.01
LA-MADDPG (ours)
0.78
0.85
0.43
0,04
LOLA-MADDPG (ours)
0.77
0.56
0.13
0.83
0.42
0.01
HR UR-MADDPG (ours)
0.88
0.83
0.44
0.94
0.67
0.42
Table 3:
Comparisons of methods in terms of the Normalized Average Episode Reward (NAER)
for common- inttrne-tterestee agents. LB: Lower Bound. UB: Upper Bound.
5.3.1 PARTICLE COORDINATION GAME
Our proposed game is variant of the Cooperative Navi- gation game (Lowe et al., 2017) with two agents and three landmarks. The agents should select and approach one of the landmarks, and the landmark closest to an agent is
PR MASTINN
LA SARREP
Aorego Epreod Bonod
considered be the selected landmark. If the agents se- lect and approach the same landmark, they receive global or local optimal rewards based the selected landmark. They will receive an assigned miscoordination penalty if they select and approach different landmarks. In Fig-
ure [ we depict the learning curves for our method and other MADDPG-hased algorithms. From this figure, it is clear that our HR-MADDPG is the only method that con- sistently converges to the global optimum of the game, which is consistent with our previous results coordination games. Further experiments regarding the sensitivity of HOG-MADDPG methods to the prediction length provided in Appendix D.3
Estacdke
Figure Learning curves in the Particle Coordination game. Higher values are better.
5.3.2 STANDARD MULTI-AGENT GAMES
We evaluate the methods in three Particle environment games (Lowe et al., 2017): 1) Coopera- tive Navigation with three common-interested agents, 2) Physical Deception with common- interested and one self-interested agent, and 3) Predator-Pres with two common-interester (predator) and one self-interested (prey) agents. Furthermore, we compare the methods in three games within the multi-agent Mujoco environment (Peng et al. 2021): 1) two-agent Half-Cheetah, 2) two-agent Walker, and 3) two-agent Reacher. In the mixed environments (Physical Deception and Predator- Prey), we have employed the MADDPG method for the self-interested agents. We report the Nor- malized Average Episode Reward for the common-inted interested agents in Table 3 where the normal- ization is done between the single-agent variant of MADDPG (DDPG (Lillicrap et al. (016)) and a fully centralized (in learning and execution) variant of MADDPG, referred to as C-MADDPG. In Table 3 observe that our proposed HOG-MADDPG consistently and significantly outperforms all the state-of-the-art MADDPG-based methods. Again, these results confirm that our proposed HR-MADDPG improves coordination among common-interested agents, leading to better results.
DISCUSSION
In this paper, we proposed the HOG-MADDPG framework to make HOG methods applicable to games with high-dimensional state spaces. As result, the benefits of HOG can now be used in many more MARL problems. As first case study, we investigated the applicability current HOG methodologies to team games, and found that they suffer from miscoordination, which we then solved with our proposed HR methodology. Like this solution, there are numerous other possibilities for extending HOG-MADDPG, e.g., factorizing the centralized value functions, which is essential for many- agent games. With our work, we aim to spark such new ideas for HOG methods in MARL, and we provide the framework to realize them.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Stefano V Albrecht and Peter Stone. Autonomous agents modelling other agents: A comprehensive survey and open problems. Artificial Intelligence, 258:66-999 2018.
David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Grae- pel. The mechanics of n-player differentiable games. In International Conference on Machine Learning, pp. 354 363. PMLR, 2018.
Dimitri Bertsekas. Constrained optimization and Lagrange multiplier methods. Academic press, 2014.
Caroline Claus and Craig Boutilier. The dynamics of reinforcement learning in cooperative multia- gent systems, AAAI/AАI,, 1998(746-752):2 1998.
Thomas Degris, Martha White, and Richard Sutton. Off-Policy Actor-Critic In International Con- ference on Machine Leurning, 2012.
Stefan Elfwing, Eiji Uchibe, and Kenji Doya. Siggoid-weighted linear units for neural network function approximation in reinforcement learning. Neural Networks, 107:3-11,201
Jakob Foerster, Richard Y Chen, Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbeel, and Igor Mordatch. Learning with Opponent-Learning Awareness. In Proceedings of the 17th Interna- fional Conference on Autonomous Agenty and MultiAgent Systems, pp. 122-130, 2018a.
Jakob Foerster, Gregory Farquhar, Maruan Al-Shedivat, Tim Rocktäschel, Eric Xing, and Shimon Whiteson. Dice: The infinitely differentiable monte carlo estimator. In International Conference on Machine Learning, pp. 1529-1538. PMLR, 201 8b.
Adam S Goodie, Prashant Doshi, and Diana Young. Levels theory-of-mind reasoning com- petitive games. Journal of Behavioral Decision Making, 25(1):95-108 2012.
He Hc. Jordan Boyd-Graber Kevin Kwok, and Hal Daumé III. Opponent modeling in deep rein- forcement learning. In International conference machine learning, pp. 1804-1813. PMLR, 2016.
Zhang-Wa Wei Hong, Shih-Yang Su, Yun Shann, Yi-Hsiang Chang, and Chun-Y Yi Lee. A Deep Policy Inference Q-Network for Multi-Agent Systems. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pp. 1388-1396, 2018
Eric Jang, Shixiang Gu, and Ben Poole. Categorical Reparametrization with Gumble-Softmax. In International Conference on Learning Representations (ICLR 2017). OpenReview. net, 2017.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
Sachin Konan, Esmaeil Seraj, and Matthew Gombolay. Iterated Reasoning with Mutual Information in Cooperative and Byzantine Decentralized Teaming. arXiv preprint arXiv:2201 008484 2022.
Alistair Letcher, Jakob Foerster, David Balduzzi, Tim Rocktäschel, and Shimon Whiteson. Stable Opponent Shaping in Differentiable Games. In International Conference on Learning Represen- tations, 2019.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In ICLR (Poster), 2016.
Raymond Lister and James V Stone. An empirical study of the time complexity of various error functions with conjugate gradient backpropagation. In Proceedings of ICNN'95-Intermationnll Conference Neural Networks, volume 1,, pp. 237-241. IEEE, 1995.
Michael L Littman. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pp. 157-163. Elsevier, 1994.
10

---

Under review as a conference paper at ICLR 2023
Daxin Liu and Gerhard Lakemeyer. Reasoning about Beliefs and Beta-Belliefs by Regression in an Expressive Probabilistic Action Logic. In international joint conference on artificial intelligence. IJCAI, 2021.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed cooperative-compeittvee environments. In NIPS, 2017.
Bei Peng, Tabish Rashid, Christian Schroeder de Witt, Pierre-Alcxandre Kamienny, Philip Torr, Wendelin Boehmer, and Shimon Whiteson. FACMAC: Factored Multi-Agent Centralised Policy Gradients. NeurlPS, 2021.
Satinder P Singh, Michael J Kearns, and Yishay Mansour. Nash Convergence of Gradient Dynamics in General-Sum Games. In UAI, pp. 541-548, 2000.
Eugene Vinitsky, Natasha Jaques, Joel Leibo, Antonio Castenada, and Edward Hughes. An open source implementation of sequential social dilemma games. /tttps://github com/ leugenevin n t tsky seepey/segunttttt ial_socia a _di remaacaamss/sssues/555 GitHub repository.
2019.
Ying Wen, Yaodong Yang, Rui Luo, Jun Wang, and Wei Pan. Probabilistic recursive reasoning for multi-agent reinforcement learning. In 7th International Conference on Learning Representa- tions, ICLR 2019, 2019.
Ying Wen, Yaodong Yang, and Jun Wang. Modelling Bounded Rationality in Multi-Agent Interac- tions by Generalized Recursive Reasoning. IJCAI, 2020.
Timon Willi, Alistair Hp Letcher, Johannes Treutlein, and Jakob Foerster. COLA: consistent learn- ing with opponent-learning awareness. In International Conference on Machine Learning, pp- 23804-23831. PMLR, 2022.
Chongjie Zhang and Victor Lesser. Multi-agent learning with policy prediction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 24, 2010.
APPENDIX
A MORE DETAILS ON THE HOG-MADDPG METHODS
A.I LA-MADDPG
In the standard MADDPG, the performance objective is defined as:
J; (s.a) Qi(s, ..,, Ui, ..., anz 01, ...; 0n) (e)le.=po,())
(11)
where (²{s,á) à) is the action distribution of the behavior policy with à (a,Vi E N/. The gradient of J; with respect to 0 can be approximated as:
Jo Rs (s,a) Vo, Qi(s, âi, ...; U1 ân) la.=po
(12)
where the direct dependencies state-action value function to policy parameters can be dropped and naïve opponent for simplicity, the gradient adjustment for parameters of the LA-MADDPG agent (0,) is computed by accounting for the anticipated policy parameters of the opponent, i.c., 02 + Ad2(s):
based the proofs presented in Degris al. (2012). Given
Ve, JLL 2 E Ve, Q2 01, 22) (aj=,,, (s). "8, 2bg (+)+
(13)
where ^02 = 1/ V. (2 àn â2)1a, (z), and 0, and 02 are the behavior policy param- eters. As the agents cannot have access to these parameters, we propose to project the anticipated gradient information to the action space using first-order Taylor expansion:
02 = 1 10, (s)
(14)
2 Mág (s) (AOz) TV V (,,
11

---

Under review as a conference paper at ICLR 2023
Algorithm 1: LA-MADDMO for set of n self-interested agents (N).
Initialize pe,, Q+ p4, and Q Vi .
for episode
max-mum-episodes do
Receive initial state 8
for f = 1 to max-episode-length do
Select action a; from μe, (s) and the exploration strategy Vi E W
Execute actions a {aiEvies and observe rewards {ra wie and new state s
Store the tuple as, s') in replay buffer D
Set s s'
Sample random K tuples {(s* at rh, , )EE(L.....)) from for agent = 1 to do Set y = r + (Qi(" (iy..,,((()a,, mag (o for {I.... K}
Update state-action value function Q: by minimizing:
L 1 K
[(Qi(s af,...,.a d - - kE(l...,K)
E
end for for agent 1 to do
for agent = to do
Project the anticipated gradients if j = then continue
Set Aat dat
a (s at...., a for k E {i,...,K
end for Update policy parameters Og via: AA. s
Σ
Vo.11
Qi(s af + af,... an + Aa (0t)
K
dak
kE(
end for Update Q and 14 V end for end for
Given that:
A0₂ -/ Q2(s, 22)
(15)
= 1/ bo - M/ (s)
(Vis (Va 12.22(s..0 0201=1--))))
we have:
ā2 M4, (5) 17 (s) (Va, A2(s,
(s)
14, (8) - 22, 0z)
VV Ma (8)
(s)
(16)
-Ma, (s) VarQ2 a, 02 1
-Ma (s) Q2,, az)
where ||-|| is the 2-normm and we have defined the projected prediction length fj 7 V (b2(5)
2 is positive number and independent of 01. Therefore:
since V 70,10
ā2 M4, (s) + a (z,
(17)
ب + Ad2.
12

---

Under review as a conference paper at ICLR 2023
Algorithm LOLA-MADDIP for set of n self-interested agents (N).
Initialize pe,, Q1 p4, and Q Vi N
for episode to max--um-eppisoes do
Receive initial state 8
for f = 1 to max-episode-length do
Select action a; from μe, (s) and the exploration strategy Vi E W
Execute actions a viEN and observe rewards {ra Wie and new state s
Store the tuple as, s') in replay buffer D
Set s s'
Sample random K tuples {(s* at rh, 8 ) from for agent = 1 to do Set y = o + (Qi(" "á,...,,/,)ls mag (o for {I,.... K}
Update state-action value function Q: by minimizing:
L
1 K
[[Qi(* af,...,,a a - -v;) kE(l...)))
E
end for
Set at 140 (s* for (1,-.., K} and N
for agent = 1 to do do Project the anticipated gradients
for agent
j = then continue
Set Ao 77 Ø aay (s at...., a for k E fi,..., K}
end for Update policy parameters 8, via: Vo
Σ
(s. Ri(s at + Dat, af. ..,,., A
K
dak
kE(L.....K)
end for Update Q and 1 ViE end for end for
Replacing Eq. in Eq. 13 yields Eq.
L E (a Vo, Mo, (8) Va, Q1(s, Aáz)la.=pe (+)-
(18)
In the case of n agents, the agent e N first anticipates the gradient information of all agents the action space as:
Ad V Q2 ai, an)
(19)
Then, agent i updates parameters 0, by the following gradient adjustment:
Vo, (p.( He, (s) (s + Adj .... 0i ...; ån Adn)la.=po, (a)
(20)
Please refer Alg. 1 for more details the LA-MADDPG optimization framework.
A.2 LOLA-MADDPG
In CPG-MADDPG, the gradient update is:
Vo, J. (p) (i, 01, an) an)lo,= WeN-
(21)
Given n = and a naive opponent for simplicity, the gradient adjustment for parameters of the LOLA-MADDPG agent (0) computed by accounting for the anticipated policy parameters of the
13

---

Under review as a conference paper at ICLR 2023
Algorithm 3: HR-MADDPG for set of m common-interested agents (M).
Initialize pe,, Qs p4, and Q Vi M
for episode
to nax-mum-episodes do
Receive initial state 8
for f = 1 to max-episode-length do
Select action a; from μe, (s) and the exploration strategy Vi E M
Execute actions a {ai (ii.v and observe common reward and new state s
Store the tuple (s, r, s in replay buffer D
Set s s'
)E((L......)) from Sample random K tuples {(s*, at )
Set y rd + ?s' d,,,.., am)laa =ui (ort), for & E {1...., K} Update state-action value function Q by minimizing:
L
1 K
Σ
I(Q(s
a )²
Assign the agents into hierarchy levels using Eq. 10 Set a. = (s"), for E (1,..., and i E M for agent
to 1 do
for agent j 1 to do
Project the anticipated gradients Compute Aaj, for & E {1..... K}:
if j 1 & m then d 2a
a (s off at at in agp)
elif j * 1 & m then A 1 an
(sst at +Aat..., a + Dat 14 a
elif 1 & = m then dat auf
á
Q(sh a at.....,at. at)
else Aat " Qs*h at + Aat .... a + Dat. A ag 0511
end for Update policy parameters 8 via:
Vo J! ~ K
Σ
Vo,110 (s*)
ke
kE,,,..,KK
Set at = detach(a + ) for k E {I,..., K} end for
Update Q and p² Vi M end for end for
opponent, i.e., 02 A02(s);
V JLOLA to (p) Ve, Qi(s, (2)) (5), moy (*))
(22)
where A02 V (2(s, 01, a2) las =ne a2) (a)) and unlike for LA-MADDPG, is a function of 0j. Again, we propose to project the anticipated gradient information to the action space. Given that:
A02 (e (s) (Var Q2(s, a1, 02)las may, (s). (o)
(23)
we have:
āg = Uæ u
~ (s) + Te,
(24)
= =s) + V Q2 a1 | VosPos
(s) + V 02 Q2 al, 22)
14

---

Under review as a conference paper at ICLR 2023
where ||-|| is the (²-norm and we have defined the projected prediction length / V2222 is positive number and independent of 81. Therefore:
since V (2))
|
(22 02 Aa2.
(25)
Replacing Eq. 25 in Eq. 22 yields Eq. 7
Vo, OOLA
E (s) Vo, (+) Q1(8, an, + A02)le ( (+),a:=uo(())
(26)
In the case of n agents, the agent E N first anticipates the gradient information of all agents in the action space as:
N
Aaj = viV Q2(,, (1,,, an)
(27)
Then, agent i updates its parameters 0; by the following gradient adjustment:
Vo, E (s.a) Ve,No, V., (i(s, + A01, ... ais .... On Aa,) (8)
(28)
Please refer Alg. 2 for more details on the LOLA-MADDPG optimization framework.
A.3 HR-MADDPG
For the general cases of m agents, we provide the HR-MADDPG algorithm in Alg.
B THEORETICAL ANALYSES ON THE PROJECTION ESTIMATION
B. INFLUENCE OF THE PROJECTION ESTIMATION
As discussed in Appendices A. and A.2 we project the anticipated gradient information to the action space using first-order Taylor expansion. This section studies the influence of this projec- tion estimation on the performance of the HOG methods. Without the loss of generality, we con- with two agents (naïve opponents). Using first-order Taylor expansion, we showed in Appendix A.2 that the anticipated gradient of the second agent on the parameter space is projected the action space as:
sider
Me.+a0, (s) R (s)(s) Va, a1,
(29)
where Ad, V2, a1, 02), R+ is the prediction length, and we denote îist E R+ as the projected prediction length via first-order Taylor expansion, which obtained (see Appendix A.2
Ms = Ve2Hoz(0))
(30)
Theorem If the anticipated gradients projected using first-order Taylor expansion, for suffi- ciently small îus there exists T/ E Rt such that
102+ (8) = (5) + Nn V Q2(8,22(,0)) a1, (1))
(31)
where
A0 1/ V Q2(5,
7 V (, 17 R
(32)
In order to prove Theorem 3 we first need to show that:
Lemma If the anticipated gradients are projected using full-order Taylor expansion, there exists Mall E R such that
|60 102+40,28 (s) 140z (3) Rolll Vag Q2(s,a1,
(33)
where
Ad2 = V, Q2
(34)
E R+
15

---

Under review as a conference paper at ICLR 2023
Proof The full-order Taylor expansion of the anticipated gradient yields:
1 (s) (s) (A02) Ve, (s) + (A02) (s) - -0(l=20))))))))
(35)
where Huog (8) denotes the Hessian of μ4g, at Given that:
A02 = 17 v, Q2,,
01, = 1) VyVa,He (8) oos (2())
(36)
we have
M02+20, (s) =/o (106(11)) (s) V
Q2002222200 a2, 02)n Ve,
1
+ Vag
a Q2(,, u2)1 (VnzHo, Hnng (8) (z) (Vog 02(),
2
+
(37)
By defining
C1(s) = Vo (0)00)
1
(38)
C2(s) 2 (V0 (s)) Hueg (s)
we have:
P 202 (6) 11, (8) + (
(39)
Given the definition of (s(s) and the dimension constraint implied by Vaz Q2, 02), it can be concluded that (s) E R and C2(s) E R. Therefore:
40,+20, (s) =140 (s) + Mul e 02), where Muall r)((ss) C2(ss 0 R. Consequently, we have proved Lemma
(40)
If we now project the anticipated gradients, with a prediction length v/ E RT, to the action space using full-order Taylor expansion, we have:
M62+ (s) + 7 tuu Vag Q2(5, al, a1,
(41)
where 7 full (s) + 7/2 C2()) + (r) In order to prove Theorem 3 we need to find the values of أر that yields:
Ma = r''
(42)
= r +
and at the same time r/ E RR By neglecting (rr(*) and given that Mh Rt, there are two cases to be considered:
if C2(s) non-negative, then for any value of Mmr Rt there exists 1 R+
C.(s)² * if C2(8) is negative, then for Ma < "[C268]] there exists 1/ E R-
Ci(s)² there always exists R and conse- 4[Ca(s]]
Therefore, for sufficiently small Mas i.e., Ma quently, the Theorem is proved.
Based on Theorem 3, the projection estimation via first-order Taylor expansion and sufficiently small fis only scales the prediction length as both 7 and 7f' are non-negative numbers. The amount of this scaling depends on both values of C₁ (s) and C2(s).
The general theoretical analyses on single-sate games reveal that scaling the prediction length di- rectly influences the HOG methods' convergence speed (Letcher et al. Zhang & Lesser 2010). However, by directly changing the projected prediction length, i.e., Miss we can tune the resulting prediction length in the state space, i.e., r/', and consequently improve the convergence behavior. To empirically show this, we conducted an experimental study to analyze the influence ftsst on the convergence behavior of are repeated four times, and the mean results are reported in the form of normalized average episode reward in Figure 7 It is clear from Figure 7 that increasing îh improves the convergence behavior of COLA-MADDPG However, high values of the projected prediction length (f) = 1.3 in Figure can lead instability of the algorithm which can be attributed to findings in Theorem 3.
in the Exit-room game (See Figure 7). The experiments
16

---

Under review as a conference paper at ICLR 2023
fix = 0.1
fu 0.5
hua = 0.9
Mat = 1.3
Normalaized Average Episode Reward
1.0
Mis
ALs 0.7
fua 1.1
0.8
0.6
0.4
0.2
1000
2000
3000
4000
5000
Episode
Figure 7: The influence of th on the convergence behavior of LOLA-MADDPG in the Exit-room game.
B.2 TIME COMPLEXITY OF THE PROJECTION ESTIMATION
In this section, we first study the time complexity of gradient anticipation in the parameter space. Then, discuss the time complexity reduction gain by projecting the anticipated gradients to the action space.
As both policy and state-action value functions approximated via neural networks, the time complexity of the gradient anticipation follows the time complexity of backpropagation in neural networks. Without the loss of the generality, we assume (as done in our experiments) that policy and state-action value networks have the same number of hidden layers, H, and neurons in each hidden layer, N. Therefore, the backpropagation time complexity of the networks for an input state of size N, and action of size Na is (Lister & Stone 1995):
Backpropagation time complexity in the policy network: O(N,N + -H- + NNo) Backpropagation time complexity in the state-action value network: O( Na) +
(11 - 1) NN)
Given that N > N - N., the time complexity of both networks can upper bounded by O(L
where we defined L = H + 1. As discussed in Appendix A.2) the anticipated gradient in the state space for the case the two-agent LOLA-MADDPG is:
A0₂ Ve,uo, (s) (Vaz Q2(s, a1, 02)1as -ee, (0).2--ra (s) )³
(43)
Therefore, the time complexity of gradient anticipation in the state space O O(L or in other words, O This is while the projected anticipated gradient in the action space is:
Aag = VjV Q2(8, (2),
(44)
which has the complexity of O(LN2). Consequently, by projecting the anticipated gradient to the action space, the time complexity reduced by (LL22).
C MORE DETAILS ON THE MISCOORDDINTIION ANALYSES
The two-agent, two-action coordination game (Claus & Boutilier 1998 defined by common reward matrix Rt = [ $ where a > is coordination reward and k < 0 is the miscoordination penalty. We further define g = a > as the miscoordination regret. Let 6, [0, 1] and 0g [0, denote the probability of choosing the first action by first and second agents, respectively.
17

---

Under review as a conference paper at ICLR 2023
Food
Equibtctmm point
Micoordisation
82
82
02
8,
Figure 8: Phase planes of the LA and LOLA dynamics. Left: unstable fixed point. Right: unstable saddle fixed point.
The common value function ((0,, 02) 02) g(0 + +02) + a the expected reward, given
0, and 02. The game has two equivalent Nash equilibria: 0₁ 02 0 and 0, = 02 1. We further define two miscoordination points: (01 = 1, 02 = 0) and
C.1 PROOF OF THEOREM 1
Given Eq. the unconstrained dynamics of LA agents can be defined by the following differential equations:
[ngg
2g 4ng2
0.
2ng² + +
(45)
a02/ax
2g
02
2ng 9
This system of equations has unique fixed point (zero gradients) at 6, = 02 = 0.5 (see Figure 8 The eigenvalue analysis of the coefficient matrix yields two real eigenvalues, A2 4vgg 2y, and two respective diagonal and off-diagonal eigenvectors. While À is always positive, the sign of A2 depends on the values both rj and g. For a fixed prediction length, non- positive values of A2 are reached by g L. In this case, the fixed point is an unstable saddle point (or unstable line in case of X2 0), and the agents, with any initial values of 0, and 0g (except the fixed point itself), converge to the equilibrium points (see Figure Left). However, when the miscoordination regret increases, g 27²" the fixed point becomes an unstable (source) point (see Figure Right). Therefore, some initial values 0, and 0₂ naturally lead the miscoordination points [01 0, 02 1).
= 4ngg² 2g and
In the case LoLA agents, the unconstrained dynamics can be defined as:
T00 fax [8ng
2g Sng"
[0
4ng² 4ng² +
(46)
802/ox
2g
02
This system of equations has a unique fixed point, again at 02 = 02 = 0.5 (see Figure 8). The eigenvalue analysis of the coefficient matrix yields two real eigenvalues, A1 8ng2 + 2g and Ag 8ng² 2g. and two respective diagonal and off-diagonal cigenvectors. Similar to the case of LA agents, A is always positive and the sign of X2 depends the values of both 1) and g. For a fixed prediction length, non-positive values A2 are reached by g S Ary In this case, the fixed point is an unstable saddle point (or unstable line in case of X 0), and the agents, with any initial values of 0₂ and 82 (except on the fixed point itself), converge to the equilibrium points. However, when the miscoordination regret increases, > 1. point. Therefore, some initial values of 0, and 02 naturally lead to the miscoordination points.
4nj the fixed point becomes unstable (source)
In the case naive agents, we have:
T801/an /0t 002/00
0
2g
0
g g
(47)
2g
02
Similar to the case of LOLA and LA, this system of equations has a unique fixed point (zero gradi- ents) 02 0₂ 0.5. The eigenvalue analysis of the coefficient matrix yields two real eigenvalues, X = 2g and 222 = -2g. and two respective diagonal and off- off-diagonal eigenvectors. This time, however, the eigenvalues of opposite signs for any values of and the fixed point is always
18

---

Under review as a conference paper at ICLR 2023
unstable saddle point. Therefore, any initial values of 01 and 0g (except on the fixed point itself) naturally lead to the equilibrium points.
Based on these results, hypothesize that 1) wrong reasoning level assumptions and 2) shaping plans that are not followed can lead to miscoordination points. Both LOLA and LA agents as- sume that other agents are naïve learners, which is obviously wrong assumption since all agents conduct first-order reasoning. For self-interested agents, is natural for the agents to don't un- veil their reasoning order each other. as they have different goals. However, common-interested agents can benefit more from this reasoning information to achieve their common goal. Further- more, LOLA agents constantly underestimate other LOLA agents and try shape them. This is while other LOLA agents do not follow the plan, and each tries to show that it is smarter than the others. [etcher al. (2019) shows that these arrogant behaviors lead to outcomes that are strictly worse for everyone. It is also clear from Theorem that the range of that leads to miscoordination in LOLA (g >
Try larger than the range of g in LA (g 2ny
In the above coordination game, one general solution to reduce the possibility of miscoordination decreasing the prediction length's values. However, in non-tabular settings, with large state spaces, it is infeasible to estimate the miscoordination regret and adjust the prediction length accordingly. Furthermore, the prediction length directly affects the usage of higher-order gradient information, and further reducing the prediction length (77 - 0) leads to the naïve learners.
C.2 PROOF OF THEOREM 2
Given Eqs. and the unconstrained dynamics of the HR agents be defined by the following differential equations:
800 for
8ng2
2g 4ng²
81
4ng² + g 81j2g²
(48)
80t
2g + 16
02
+ 4ng +
resulting in a unique fixed point at 01 02
0.5 and two real eigenvalues, À = 6ng² +
pov/eetaggz II. Unlike the case of LOLA and LA, the eigenvalues are now of opposite signs for any values of g. and the fixed point is always an unstable saddle point. Therefore, any initial values of 02 and 0g (except the fixed point itself) naturally lead the equilibrium points.
D MORE DETAILS ON THE EXPERIMENTS AND THE IMPLEMENTATIONS
In this section, we describe all the experiments and the implementations in detail. To ease the reproducibility of our work, the code of our methods and experiments are shared with the commu- nity at [to comply with the double-blind policy, the link will be inserted in the final version].
A note partial observability. So far, have formulated the MARL setup as an MG, where assumed that the agents have access to the state space. However, many games, the agents only receive private state observation of the current state. In this case, the MARL setup can be formulated as Partially Observable Markov Game (PO-MG) (Littman 1994). A PO-MG is tuple (W,S, (A, Hie,, (O.)ee,, (R, heN, T, (94)ie P. 7), where O2 is the set of sate observations for agent i E N. Each agent i chooses its action a; E A, through the policy To, : O; x A; [0, parameterized by 0, conditioning on the given state observation o, E O,, After transition to a new state, each agent i receives a private state observation through its observation function Q + O, In this case, the centralized state-action value function for each agent is defindd as Qi(01, ..... On- C1..... an) (Ti'" = o, = (2(s) & af = a.Vi E AN). Therefore, the proposed HOG-MADDPG framework can be modified accordingly.
D.1 MATRIX GAMES
Iterated Rotational Game (RR))Zhang & Lesser 2010) is one-state, two-agent, one-action matrix game with the reward matrices depicted in Table (for two discrete actions). Each agent must choose 1 1-D continuous action (0; for agent of taking two discrete actions. The game has a unique equilibrium point at a 02 = 0.5. which is also the fixed point of the game. IRG is originally proposed to demonstrate the circular behavior that
and ag for agent two) representing the probability
19

---

Under review as a conference paper at ICLR 2023
discrete action 1 discrete action 2
Cooperate
Defect
discrete action 1
(0,3)
(3,2)
Cooperate
(-1,-1)
(-3,0)
discrete action 2
(1,0)
(2, 1)
Defect
(0, (3)
(-3, -3)
Table 4: Reward matrix in IRG.
Table 5: Reward matrix in IPD.
can emerge the agents follow the naive gradient updates. LA agents, on the other hand, can quickly converge to the equilibrium point by considering their opponent's parameter adjustment. As LOLA agents cannot preserve the fixed point of the game (Letcher et al. 2019), they converge to non- equilibrium points. We evaluate the performances of methods based on the Distance to Equilibrium (DtE).
Iterated Prisoner's Dilemma (IPD) (Foerster al. 2018a) is a five-state, two-agent, two-action game with the reward matrices depicted in Table Each agent must choose between two discrete actions (cooperate defect). The game is played for 150 time steps (T 150). In the one-shot version of the game, there is only one Nash equilibrium for the agents (Defect, Defect). In the iterated games, (Defect, Defect) is also Nash equilibrium. However, better equilibrium is Tit-For-Tat (TFT), where the players start by cooperating and then repeat the previous action of the opponents. The LOLA agents can shape the opponent's learning to encourage cooperation and, therefore, con- verge to TFT (Letcher et al. 2019). We evaluate the methods' performances based on the Averaged Episode Reward (AER).
Implementation details. We used policies and state-action value functions with the same neural network architecture all methods. We employed Multi-Layer Perceptron (MIP) networks with two hidden layers of dimension 64 for policies and state-action value functions. In order to make the value functions any-order differentiable, we used SiL.U nonlinear function (Elfwing et al. 2018) in between the hidden layers. For IRG, we used the Sigmoid function in the policies to output I- continues action, and for IPD, we used the Gumble-softmax function (Jang et al. 2017) in the policies to output two discrete actions. The algorithms IPD) episodes by rumning Adam optimizer (Kingma & Ba 2013) with fixed learning rate of 0.01. The prediction length, 1), for LOLA and LA agents in both HOG-MADDPG and DiCE frameworks are fixed to in all experiments. We reported the best methods' performances in Table [ All experiments are repeated five times, and the results are reported in terms of mean and standard deviation in Figure I and Table [
trained for 900 (in IRG) and 50 (in
D.2 EXIT-ROOM GAME
The Exit-Room game is a grid-world variant of the IPD, with two agents (blue and red) and 152t states where/ {1, 2, 3) is the complexity level of the game. The agents should cooperate and move towards the exit doors on the right. However, they are tempted to exit the left doors and, in some cases, not exiting at all. In level 1, the agents have three possible actions (move-left. move-right, or do nothing), and the reward is computed as Vinitsky et al. 2019)
rewardo = A (cooperation s + cooperation opponennt
reward = Ap - cooperation
(49)
reward reward + reward
where λc and Ap are some constants, and cooperation and cooperation.oppnnee are the normal- ized distances of the agent and its opponent the right door, respectively. In levels 2 and 3, the agents have additional move-up and move-down actions. In level 3, the door positions are randomly located, resulting in more complex interactions among the agents. In addition to the reward in Eq. 449), the agents receive additional reward for approaching the doors in levels 2 and 3. Each agent receives four 90 x 90 RGB images representing the state observations of the last four time steps.
Implementation details. As before, used policies and state-action value functions with the same neural network architecture in all methods. Both policy and value networks consist of two parts: encoder and decoder. The encoders
CNN networks with three convolutional layers (12 x 90 x 90 + 32 x 21 x 21 + 64 x 9 9 - 64 x 7 7) and two fully connected layers (3136 + 512 - 128 with SiLU nonlinear functions (Elfwing al. 2018) in between. The decoders MI.P
20

---

Under review as a conference paper at ICLR 2023
LA-ADDPG
642
1008
236
68c
1006
Tamedd
(a)
0.1
(c) 1j
0.01
Figure 9: Learning curves in the particle coordination game with different values of the prediction
length, 7, for HOG-MADDPG methods.
networks with two hidden layers of dimension 64 for policies and state-action value functions. We used the Gumble-softmax function in the policies (Jang et al. 2017) to output the discrete actions. The algorithms are trained for 450 (in level one) and 4500 (in levels two and three) episodes by running Adam optimizer (Kingma Ba 2015) with a fixed learning rate of 0.01. The prediction length, for LOLA and LA agents in both HOG-MADDPG and DíCE frameworks are fixed to in all experiments. All experiments are repeated five times, and the results are reported in terms of mean and standard deviation in Figure 2 and Table The methods evaluated in terms of the Normalized Average Episode Reward (NAER), where the normalization is done between the highest and lowest episode rewards in each game level. We reported the best methods' performances in Table
D.3 PARTICLE COORDINATION GAME
Our proposed game is a variant of the Cooperative Nav- igation game in the Particle environment (Lowe et al. 2017]. As shown Figure each one of the two agents (purple circles) should select and approach one of the three landmarks (one gray and two green circles). Land- marks are selected based on the closest distance between the agent and the landmarks. Suppose the agents select and approach the same landmark. In that case, they re- ceive global (by selecting the green landmarks) or local (by selecting the gray landmark) optimal rewards. They will receive an assigned miscoordination penalty if they select and approach different landmarks. Each agents re- ceive a 14-D state observation vector and select 5-D, one-hot vector, representing one of the five discrete ac- tions: move-right, move-left, move-up, move-down, and stay. The horizon is set to 25, T = 22. The
Agent
Agent 2
Particle coordination game with two agents and three landmarks.
Figure 10:
agents receive a Landmark Selection (LS) reward indicated by the matrix: RLs = -[ 0,1 ].
-20
20
where the rows and columns indicate the selected landmarks by the first and second agents, respec- tively. Furthermore, the agents receive an additional reward for approaching the landmarks.
Implementation details. We used policies and state-action value functions with the same neural network architecture in all methods. We employed MLP networks with two hidden layers of dimen- sion 64 for policies and state-action value functions with SiLU nonlinear functions (Elfwing al., 2018) in between. We used the Gumble-softnax function (Jang et al. 2017) in the policies to out- put the discrete actions. The algorithms are trained for 100k episodes by running Adam optimizer (Kingma & Bal 2015) with fixed learning rate of 0.01. We set the prediction length, 7,, to 0.1 for HR agents and 0.01 for LOLA and LA agents. All experiments are repeated five times, and the results reported in terms of mean and standard deviation in Figure
Effect of the prediction length. Additionally, we illustrate the effect of various prediction lengths on the performance of HR, LOLA. and LA agents in Figure 9 As shown, the HR-MADDPG method and
consistently converges to the global optimum the game. This is while both LA-MADDPG demonstrate weak performances, especially by increasing the prediction length.
21

---

Under review as a conference paper at ICLR 2023
Particle Environment
Mujoco Environment
Cooperative Navigation
Physical Deception
Predator Prey
Half-Cheetaal
Walker
Reacher
Observation
18-D
10-D(8-D)
I4-D (12-D)
11-D
11-D
8-D
Observation type
continuous infinite
continuous infinite
continuous
continueus
continuous
continuous infinite
Discrete ubservations
infinite
infinite
infinite
Action
5-D (5-D)
5-D (5-D)
3-D
3-D
1-D
Action lype
discrete
discrete
discrete
continuous 70K D
continuous 70K D
continuous 70K D
Policy parameter
11K-D
11K (8-D) 25
10K D (12-D) 25
Horizon (step)
100
300
50
Table 6: Specifications in the standard multi-agent games. In the mixed environments, the dimen- sions are reported as "d1 (d2)" where d1 is the dimension for common inttenn-tterested agents and dg is the dimension for self-interested ones.
D.4 STANDARD MULTI-AGENT GAMES
We evaluate the methods in three Particle environment games (Lowe et al. 2017): 1) Coopera- tive Navigation with three common-interested" agents, 2) Physical Deception with two common- interested and one self-interested agent, and 3) Fredator-Prey with two common-interested (predator) and one self-interested (prey) agents. Furthermore, we compare the methods in three games within the multi-agent Mujoco environment (Peng et al., 2021]: 1) two-agent Caef-,h 2) two-agent Walker, and 3) two-agent Reacher. In the mixed environments (Physical Deception and Predator- Prey), we have employed the MADDPG method for the self- interested agents. Games' specifications reported in T We created separate validation and test sets for each game that included 100 and 300 randomly generated scenarios, respectively. In each game, we save the models that have the best performance on the validation set and test them on the test set to report the results. All experiments are repeated five times, and the mean results are reported in Table 3 in terms of the Normalized Average Episode Reward (NAER). The normalization done between the single-agent variant of MADDPG (DDPG (Lillicrap et al. (0166) and a fully centralized (in learning and ex- ecution) variant of MADDPG, referred to as C-MADDPG. The non-normalized data are reported in Table { in terms of the Collective Average Episode Reward (CAER) for the common-interested agents.
Implementation details. As before, we used policies and state-action value functions with the same neural network architecture in all methods. We employed MLP networks with two hidden layers (of dimension 64 for the Particle environment and 256 for the Mujoco environment) for policies and state-action value functions with SiLU nonlinear functions (Elfwing et al.) 2018). In the Particle environment, We used the Gumble-softmax function (Jang et al.) (017) in the policies output the discrete actions and trained the algorithms for 100k episodes by running Adam optimizer (Kingma & Bal 2015) with a fixed learning rate of 0.01. In the Mujoco environment,
used the Tanh function in the policies to output the continuous actions and train the algorithms for 10k episodes by running Adam optimizer (Kingma & Ba 2015) with a fixed learning rate of 0.001. The prediction lengths, in HR-MADDPG, LA-MADDPG, and LOLA-MADDPS are optimized between 0.001 - 0.1 in all games. We avoid considering any smaller value than 0.001 for the prediction length as makes the algorithms similar to the naïve learners. The optimized prediction lengths are reported in Table
Ablation study. We have additionally conducted an ablation study on the hierarchy level assign- ments in the -RR-MDDPPG. Rather than iteratively sorting the agents based on their shaping capaci- ties through Eq. (10). randomly assigned the agents hierarchy levels in the beginning and fixed the hierarchy levels throughout the optimization. This variant of the HR-MADDPG, referred to as HR-MADDPG (F), is evaluated and compared in Table 9 As can be seen, using the proposed sort- ing strategy based on the shaping capacities of the agents, as done in our HR-MADDPG, constantly improves performance.
22

---

Under review as a conference paper at ICLR 2023
Particle Environment
Mujoco Environment
Cooperative Navigation Physical Deception
Prodator-Prey
Half-Chectah
Walker
Reacher
LA-MADDPG DPP--MADPPG
0.002
0.003
0.01
0.001
0.002
0.003
0.001
0.003
0.008
0.001
0.001
0.002
HR- HR-MADDPG
0.003
0.01
0.04
0.004
0.004
0.007
Table 7: The optimized prediction lengths for HOG-MADDPG methods.
CCAER in Partiele Environment
1CAER in Mujaco Environment
Methods
Cooperative Navigation
Physical Deception
Predator-Prey
Half-Chectah
Walker
Reacher
DDPG (LB)
-189.18
13.04
10.20
611.74
2925.17
-16.19
C-MADDPG (UB)
-130.91
20.82
20.87
1564.60
6362.36
-8.89
MADDPG
.144.02
17. 82
12.46
1435.93
4482.31
-16.02
CPG-MADDPG
-143.96
18.29
12.08
1454.62
4511.08
-15,84
PR2-MADDPG
-143.67
17.26
11.08
1418.69
4473.14
-16.09
LA-MADDPG
-143.72
17.92
11.58
1424.39
4408.56
-15,89
LOLA-MADDPG
-144.21
17.43
11.54
1406.61
4369.13
-16.13
HR-MADDPG
-137.63
19.48
14.85
1503.07
5226.26
-13.16
Table 8: Comparisons of methods in terms of the Collective Average Episode Reward (CAER) for common- -nnton-interested agents, corresponding the normalized data in Table
NNAER Particle Environment
NNAER Mujoco Environment
Methods
Cooperative Navigation
Physical Deception
Predator-Prey
Half Cheetah
Walker
Reacher
HR-M MADDPG
0.85
0.80
0.38
0.92
0.63
0.38
HR-MADDPG
0.88
0.83
0.44
0.94
0.67
0.42
Table 9: Ablation study on the hierarchy level assignments in our HR-MADDPE method.
23


Reviews:
[{"review_id": "a6jwO_QmngV", "reviewer": "Reviewer_VXeR", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "This paper studies the use of higher order gradient methods for multi-agent RL with high dimensional state space. It shows that existing methods can lead to miscoordination among agents. A hierarchical reasoning algorithm is proposed. Experimental results are presented to show the applicability of the method. \n\n", "summary_of_the_review": "Overall, the paper considers an interesting problem and the experimental results show that the algorithms perform well. However, the presentation of the paper could be improved, also, the contributions need to be better explained. ", "strength_and_weaknesses": "Strength\n- The problem in consideration is interesting. \n- The proposed algorithm performs well in the experiments. \n\nWeakness\n- The paper could make it clear what the exact setting is. This will help clarify some potential confusion. For example, the issue raised in the intro does not seem to exist in the CTDE framework (not a game setting). \n- What are the forms of (1) and (2) when there are multiple agents? So are (3)-(7). Right now everything is done with n=2. \n- Following the above comment, it appears that most of the derivation and most experiments are done for a 2-user case (or two coordinating agents with others). While the reviewer understands the tractability of this case, it seems a bit limited that even in the experiments only two agents are considered. \n- Where is the projection step in the algorithms? Also, what is the complexity for doing so? \n- The presentation is a bit confusing. In Fig. 2,  LA-MADDPG and LOLA-MADDPG are both marked as “ours”. But in Table 3, only HR-MADDPG has this label. From the text, it seems that the paper applies the ideas to LA-MADDPG and LOLA-MADDPG. Please clarify. \n- It would be useful to highlight the key difference between the proposed algorithms and MADDPG. Right now the novelty of the algorithm is not clear. \n- Minor: “between the agents” should be “among the agents”", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "EQqRPa9tpa", "reviewer": "Reviewer_ynkz", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "The Higher-Order Gradient approach is of great value to the field of MAS, as it can be used in many important areas such as the theory of mind. The authors review the existing work and further propose Hierarchical Reasoning to facilitate the collaboration of team agents, noting that their approach is highly extensible and will help the community to explore the problem in the future.", "summary_of_the_review": "Looks like a good paper, very interesting, I will adjust my score further after considering the author's rebuttal with other reviewers' comments.", "strength_and_weaknesses": "Strength.\n* The authors have studied a very important direction\n* The paper is clearly written and well understood\n* A comprehensive review of existing papers so that the value of the methods can be pinpointed\n* The experimental part looks adequate\n\nWeaknesses.\n* The authors claim that the existing methods are only applicable to low-dimensional settings, while their proposed methods can be applied to high-dimensional settings. But what puzzles me is that the experimental environment looks simple, while the number of real states in the environment is not very large, please note that I mean how many discrete states are in the environment.\n* Although the experiments show the effectiveness of the authors' method, it looks like the variance is large and there is a relatively large overlap between the algorithms, does this mean that more iterations of the experiments are needed or think about other evaluation methods?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5PZsDnVW3H", "reviewer": "Reviewer_eo4T", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "\nThis paper revisits high order gradient methods for multi-agent reinforcement learning and points out that it usually does not apply to games with high-dimensional state spaces due to inefficient computation and preservation of high-order gradient information. The authors develop a scheme to address the problem and enable order gradient methods to work for high dimensional problem. Furthermore, hierarchical reasoning is proposed to improve the coordination in team games.\n", "summary_of_the_review": "1.\tThe review does not think that resorting to MADDPG can totally mitigate the computation difficulty of high-dimensional gradient. Even though  the high order gradient can be calculated, it takes long time when the gradient is of really high-dimensional.\n2.\tAbout projecting the gradient information from state space to action space, there is no theoretical analysis on how the projection influence the results. Does it degrade the performance or not? If not, what conditions are supposed to be satisfied.\n3.\tFor the hierarchical reasoning, is it guaranteed to converge to the equilibria for any level of hierarchy. \n", "strength_and_weaknesses": "\nStrength:\n1.\tMulti-Agent Deep Deterministic Policy Gradient (MADDPG)  and projecting gradient from state space to action space are adopted to addressed the issue of computation and preservation of high-order gradient information, respectively.\n2.\tHierarchical reasoning is proposed tackle the miscoordination of between common-interested agents. \nWeaknesses:\nLack of theoretical analysis on the proposed methods.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3RmMPgBpZB", "reviewer": "Reviewer_TWCf", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "The paper revisits the idea of using higher-order gradient in multi-agent RL with two improvements: (1) using LOLA and LA for preserving higher-order gradients and (2) use a hierarchical reasoning approach to coordinate agents in team (cooperation) scenario.", "summary_of_the_review": "The paper revisits the idea of using higher-order gradient in multi-agent RL with two improvements: (1) using LOLA and LA for preserving higher-order gradients and (2) use a hierarchical reasoning approach to coordinate agents in team (cooperation) scenarios. So far I am not fully convinced of the novelty of the paper.", "strength_and_weaknesses": "Pros:\n- The LOLA and LA approximations makes preserving high-order gradient more efficient and the improvement is shown via experiment results\n- The hierarchical reasoning approach further improves the performance in fully-cooperative case.\n\nCons:\n- The two approximation scheme, LA and LOLA, are existing approaches well known in the community. So how do you place your novelty using these methods for approximation purposes?\n- The term high-oerder gradient is actually very confusing. At the very beginning I was thinking this is use higher-order derivatives to do policy optimization. It would be super helpful if the author make a comment on this early in the intro part.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject