$\displaystyle||\mathcal{I}^{n}(f)-\mathcal{I}^{m}(f)||_{Z_{\mathfrak{a}}}$
$\displaystyle\leq\sum_{k=n}^{m-1}||\mathcal{I}^{k}(f)-\mathcal{I}^{k+1}(f)||_{Z_{\gamma}},$
(7.79)
$\displaystyle\leq\sum_{k=n}^{m-1}\frac{L^{k}T^{k}}{(\mathfrak{a}-\gamma)^{qk}}\frac{n^{qk}}{k!}\
||f-\mathcal{I}(f)||_{Z_{\gamma}},$ (7.80)
$\displaystyle\leq\sum_{k=n}^{\infty}\frac{L^{k}T^{k}}{(\mathfrak{a}-\gamma)^{qk}}\frac{n^{qk}}{k!}\
||f-\mathcal{I}(f)||_{Z_{\gamma}}.$ (7.81)

According to Theorem 7.1 the right hadn side of inequality (7.81) above is a
remainder of a convergent series. Therefore we conclude that sequence
$\\{\mathcal{I}^{n}(f)\\}n\in\mathbb{N}$ is Cauchy in $Z_{\mathfrak{a}}$.
Since $\mathfrak{a}$ is arbitrary, let us now consider
$\alpha<\beta\in(\underline{\mathfrak{a}},\overline{\mathfrak{a}})$ and

$\displaystyle\overbrace{\ \lim_{n\to\infty}\mathcal{I}^{n}(f)\ }^{\text{in}\
Z_{\alpha}}=\phi_{\alpha}.$ (7.82) $\displaystyle\overbrace{\
\lim_{n\to\infty}\mathcal{I}^{n}(f)\ }^{\text{in}\ Z_{\beta}}=\phi_{\beta}.$
(7.83)

Because $Z_{\alpha}\prec Z_{\beta}$ we see that

$\displaystyle\|\phi_{\beta}-\phi_{\alpha}\|_{Z_{\beta}}$
$\displaystyle\leq\|\phi_{\beta}-\mathcal{I}^{n}(f)\|_{Z_{\beta}}+\|\mathcal{I}^{n}(f)-\phi_{\alpha}\|_{Z_{\beta}},$
(7.84)
$\displaystyle\leq\|\phi_{\beta}-\mathcal{I}^{n}(f)\|_{Z_{\beta}}+\|\mathcal{I}^{n}(f)-\phi_{\alpha}\|_{Z_{\alpha}},$
(7.85)

which shows that $\phi_{\beta}=\phi_{\alpha}$. Therefore defining

$\displaystyle\phi_{\alpha}\eqqcolon\phi\coloneqq\phi_{\beta},$ (7.86)

we see that $\phi\in\underline{Z}$ and

$\displaystyle\overbrace{\ \lim_{n\to\infty}\mathcal{I}^{n}(f)\ }^{\text{in}\
Z_{\mathfrak{a}}}=\phi.$ (7.87)

Now, from Theorem 7.23 it follows that $\mathcal{I}$ is a continuous map from
$Z_{\mathfrak{a}}$ to $Z_{\overline{\mathfrak{a}}}$. Hence we see that

$\displaystyle\mathcal{I}^{n+1}(f)$ $\displaystyle\to\phi\ \text{as}\
n\to\infty,$ (7.88)
$\displaystyle\mathcal{I}^{n+1}(f)=\mathcal{I}(\mathcal{I}^{n}(f))$
$\displaystyle\to\mathcal{I}(\phi)\ \text{as}\ n\to\infty,$ (7.89)

which shows that $\mathcal{I}(\phi)=\phi$. Finally suppose that there exists
$\psi\in\underline{Z}$ such that $\psi\not=\phi$ and $\mathcal{I}(\psi)=\psi$.
In this case it is clear that

$\displaystyle||\mathcal{I}^{n}(\phi)-\mathcal{I}^{n+1}(\psi)||_{Z_{\mathfrak{a}}}=||\phi-\psi||_{Z_{\mathfrak{a}}}.$
(7.90)

However from Theorem 7.25 we can infer that

$\displaystyle||\mathcal{I}^{n}(\phi)-\mathcal{I}^{n+1}(\psi)||_{Z_{\mathfrak{a}}}$
$\displaystyle\leq\frac{L^{n}T^{n}}{(\beta-\alpha)^{qn}}\frac{n^{qn}}{n!}||\phi-\mathcal{I}(\psi)||_{Z_{\alpha}},$
(7.91)
$\displaystyle=\frac{L^{n}T^{n}}{(\beta-\alpha)^{qn}}\frac{n^{qn}}{n!}||\phi-\psi||_{Z_{\alpha}}.$
(7.92)

Since, by Theorem 7.1, the right hand side of inequality (7.92) tends to zero
we conclude that $||\phi-\psi||_{Z_{\mathfrak{a}}}=0$. Therefore $\phi$ is
unique and the proof is complete. ∎

We now formulate and prove the main result of this appendix.

######  Theorem 7.27.

Suppose $x_{\underline{\mathfrak{a}}}\in X_{\underline{\mathfrak{a}}}$, $q<1$
and $F\in\mathcal{O}(\mathbf{X},L,q)$ are fixed. Then there exist a unique map
$f:[0,T]\to\underline{X}$ such that if
$\mathfrak{a}\in(\underline{\mathfrak{a}},\overline{\mathfrak{a}})$ then
$f:[0,T]\to X_{\mathfrak{a}}$ is continuous and

$f(t)=x_{\underline{\mathfrak{a}}}+\int_{0}^{t}F(f(s))ds,\ t\in[0,T].$

###### Proof.

This result folows directly from Theorem 7.26 above by letting
$f\coloneqq\phi$. ∎

######  Remark.

For $q=1$ current method can be used to prove Theorem 7.27 by introducing a
suitable upper bound on $T$.

The final result of this appendix is a usefull norm estimate. To prove this
final result we now make two preliminary observations.

First, suppose that $\alpha<\beta\in\mathcal{A}$ and $x\in X_{\alpha}$. Then
we can see that

$\displaystyle\|F(x)\|_{X_{\beta}}$
$\displaystyle=\|F(x)+F(0)-F(0)\|_{X_{\beta}},$ (7.93)
$\displaystyle\leq\|F(x)-F(0)\|_{X_{\beta}}+\|F(0)\|_{X_{\beta}},$ (7.94)
$\displaystyle\leq\frac{L}{(\beta-\alpha)^{q}}\|x\|_{X_{\alpha}}+\|F(0)\|_{X_{\beta}},$
(7.95)
$\displaystyle\leq\frac{L}{(\beta-\alpha)^{q}}\bigg{(}P+\|x\|_{X_{\alpha}}\bigg{)},$
(7.96)

where

$\displaystyle P\coloneqq\frac{\|F(0)\|_{X_{\beta}}(\beta-\alpha)^{q}}{L}.$
(7.97)

Second, suppose
$\mathfrak{a}\in(\underline{\mathfrak{a}},\overline{\mathfrak{a}})$ and
$x_{\underline{\mathfrak{a}}}\in X_{\underline{\mathfrak{a}}}$. Moreover
consider a partition $\\{\psi_{i}\\}_{i=0}^{n+1}$ of
$[\underline{\mathfrak{a}},\alpha]$ into $n+1$ intervals of equal length. That
is $\psi_{0}=\underline{\mathfrak{a}}$, $\psi_{n+1}=\alpha$ and
$\psi_{i+1}-\psi_{i}=\frac{\alpha-\underline{\mathfrak{a}}}{n-1}$ for all
$0\leq i\leq n$. Now, from Theorem 7.25 we see that for all
$n\in\mathbb{N}^{0}$ we have

$\displaystyle||\mathcal{I}^{n}(x_{\underline{\mathfrak{a}}})(t)-\mathcal{I}^{n+1}(x_{\underline{\mathfrak{a}}})(t)||_{X_{\mathfrak{a}}}$
$\displaystyle\leq\frac{L^{n}}{(\mathfrak{a}-\psi_{1})^{qn}}n^{qn}\mathcal{H}^{n}(t,||x_{\underline{\mathfrak{a}}}-\mathcal{I}(x_{\underline{\mathfrak{a}}})||_{X_{\psi_{1}}}),$
$\displaystyle\leq\frac{L^{n}}{(\mathfrak{a}-\psi_{1})^{qn}}n^{qn}\mathcal{H}^{n+1}(t,\|F(x_{\underline{\mathfrak{a}}})\|_{X_{\psi_{1}}}),$
$\displaystyle\leq\frac{L^{n}}{(\mathfrak{a}-\psi_{1})^{qn}}\frac{L}{(\psi_{1}-\underline{\mathfrak{a}})}n^{qn}\mathcal{H}^{n+1}(t,P+\|x_{\underline{\mathfrak{a}}}\|_{X_{\underline{\mathfrak{a}}}}),$
$\displaystyle\leq\frac{L^{n}T^{n+1}}{(\mathfrak{a}-\psi_{1})^{qn}}\frac{L}{(\psi_{1}-\underline{\mathfrak{a}})}\frac{n^{qn}}{(n+1)!}\bigg{(}P+\|x_{\underline{\mathfrak{a}}}\|_{X_{\underline{\mathfrak{a}}}}\bigg{)},$
$\displaystyle\leq\frac{L^{n+1}T^{n+1}}{(\mathfrak{a}-\underline{\mathfrak{a}})^{q(n+1)}}\frac{(n+1)^{q(n+1)}}{(n+1)!}\bigg{(}P+\|x_{\underline{\mathfrak{a}}}\|_{X_{\underline{\mathfrak{a}}}}\bigg{)}.$

We now obtain the norm estimate.

######  Theorem 7.28.

Let $f$ be defined by Theorem 7.27 and suppose that
$\mathfrak{a}\in(\underline{\mathfrak{a}},\overline{\mathfrak{a}})$. Then for
all $t\in[0,T]$

$\displaystyle||f(t)||_{X_{\mathfrak{a}}}\leq\sum_{n=0}^{\infty}\frac{L^{n}T^{n}}{(\mathfrak{a}-\underline{\mathfrak{a}})^{qn}}\frac{n^{qn}}{n!}\bigg{(}P+\|x_{\underline{\mathfrak{a}}}\|_{X_{\underline{\mathfrak{a}}}}\bigg{)}.$
(7.98)

###### Proof.

From Theorem 7.26 it is clear by continuity of $f$ that for all $t\in[0,T]$ we
have

$\displaystyle\overbrace{\
\lim_{n\to\infty}\|\mathcal{I}^{n}(x_{\underline{\mathfrak{a}}})(t)\|_{X_{\mathfrak{a}}}\
}^{\text{in}\ X_{\mathfrak{a}}}=\|f(t)\|_{X_{\mathfrak{a}}}.$ (7.99)

Hence we now use estimate (7.3) to see that for all $n\in\mathbb{N}$ and all
$t\in[0,T]$ we have

$\displaystyle\|\mathcal{I}^{n}(x_{\underline{\mathfrak{a}}})(t)\|_{X_{\mathfrak{a}}}-\|\mathcal{I}^{0}(x_{\underline{\mathfrak{a}}})(t)\|_{X_{\mathfrak{a}}}$
$\displaystyle=\sum_{k=1}^{n}\|\mathcal{I}^{k}(x_{\underline{\mathfrak{a}}})(t)\|_{X_{\mathfrak{a}}}-\|\mathcal{I}^{k-1}(x_{\underline{\mathfrak{a}}})(t)\|_{X_{\mathfrak{a}}},$
$\displaystyle\leq\sum_{k=1}^{n}\|\mathcal{I}^{k-1}(x_{\underline{\mathfrak{a}}})(t)-\mathcal{I}^{k}(x_{\underline{\mathfrak{a}}})(t)\|_{X_{\mathfrak{a}}},$
$\displaystyle\leq\sum_{k=1}^{n}\frac{L^{k}T^{k}}{(\mathfrak{a}-\underline{\mathfrak{a}})^{qn}}\frac{k^{qk}}{k!}\bigg{(}P+\|x_{\underline{\mathfrak{a}}}\|_{X_{\underline{\mathfrak{a}}}}\bigg{)}.$
(7.100)

Therefore for all $n\in\mathbb{N}$ and all $t\in[0,T]$ we have

$\displaystyle\|\mathcal{I}^{n}(x_{\underline{\mathfrak{a}}})(t)\|_{X_{\mathfrak{a}}}$
$\displaystyle\leq\|\mathcal{I}^{0}(x_{\underline{\mathfrak{a}}})(t)\|_{X_{\mathfrak{a}}}+\sum_{k=1}^{n}\frac{L^{k}T^{k}}{(\mathfrak{a}-\underline{\mathfrak{a}})^{qn}}\frac{k^{qk}}{k!}\bigg{(}P+\|x_{\underline{\mathfrak{a}}}\|_{X_{\underline{\mathfrak{a}}}}\bigg{)},$
$\displaystyle\leq
P+\|x_{\underline{\mathfrak{a}}}\|_{X_{\underline{\mathfrak{a}}}}+\sum_{k=1}^{n}\frac{L^{k}T^{k}}{(\mathfrak{a}-\underline{\mathfrak{a}})^{qn}}\frac{k^{qk}}{k!}\bigg{(}P+\|x_{\underline{\mathfrak{a}}}\|_{X_{\underline{\mathfrak{a}}}}\bigg{)},$
$\displaystyle\leq\bigg{(}1+\sum_{k=1}^{n}\frac{L^{k}T^{k}}{(\mathfrak{a}-\underline{\mathfrak{a}})^{qn}}\frac{k^{qk}}{k!}\bigg{)}\bigg{(}P+\|x_{\underline{\mathfrak{a}}}\|_{X_{\underline{\mathfrak{a}}}}\bigg{)},$
$\displaystyle\leq\sum_{k=0}^{n}\frac{L^{k}T^{k}}{(\mathfrak{a}-\underline{\mathfrak{a}})^{qn}}\frac{k^{qk}}{k!}\bigg{(}P+\|x_{\underline{\mathfrak{a}}}\|_{X_{\underline{\mathfrak{a}}}}\bigg{)}.$

Finally taking the limit on both sides of inequality (7.3) we see that for all
$t\in[0,T]$ we have

$\displaystyle||f(t)||_{X_{\mathfrak{a}}}\leq\sum_{n=0}^{\infty}\frac{L^{n}T^{n}}{(\mathfrak{a}-\underline{\mathfrak{a}})^{qn}}\frac{n^{qn}}{n!}\bigg{(}P+\|x_{\underline{\mathfrak{a}}}\|_{X_{\underline{\mathfrak{a}}}}\bigg{)},$

hence the proof is complete. ∎

######  Remark.

It is clear from the definition (7.97) that if $F$ is a linear map then
$P\equiv 0$ hence in this case from Theorem 7.28 we see that for all
$\mathfrak{a}\in(\underline{\mathfrak{a}},\overline{\mathfrak{a}})$.
$\displaystyle||f(t)||_{X_{\mathfrak{a}}}\leq\sum_{n=0}^{\infty}\frac{L^{n}T^{n}}{(\mathfrak{a}-\underline{\mathfrak{a}})^{qn}}\frac{n^{qn}}{n!}\|x_{\underline{\mathfrak{a}}}\|_{X_{\underline{\mathfrak{a}}}}.$
(7.101)

######  Remark.

It is aso clear from Theorem 7.28 that
$\displaystyle||f||_{Z_{\mathfrak{a}}}\leq\sum_{n=0}^{\infty}\frac{L^{n}T^{n}}{(\mathfrak{a}-\underline{\mathfrak{a}})^{qn}}\frac{n^{qn}}{n!}\bigg{(}P+\|x_{\underline{\mathfrak{a}}}\|_{X_{\underline{\mathfrak{a}}}}\bigg{)}.$
(7.102)

## References

  * [1] A. Daletskii, Stochastic differential equations in a scale of Hilbert spaces, Electronic Journal of Probability, (2018).
  * [2] A. Daletskii, D. Finkelshtein, Row-finite systems of ordinary differential equations in a scale of Banach spaces, Journal of Statistical Physics, (2018).
  * [3] C. Prevot and M. Rockner, Concise Course on Stochastic Partial Differential Equations, Springer, (2007).
  * [4] G. Da Prato and J. Zabczyk, Stochastic Equations in Infinite Dimensions, Cambridge University Press, (2014).
  * [5] L. V. Ovsjannikov, A nonlinear Cauchy problem in a scale of Banach spaces, Dokl. Acad. Nauk SSSR, 200 (1971); Soviet Math. Dokl. 12 (1971) p1497-1502.
  * [6] L . V . Ovsjannikov, Singular operators in Banach scales, Dokl. Akad. Nauk. SSSR 163 (1965) 819-822; Soviet Math. Dokl. 6 (1965) p1025-1028.
  * [7] M. Reed and B. Simon, Functional Analysis, Academic Press, (1980).
  * [8] S. K. Berberian, Measure and Integration, The Macmillan Company, (1965).
  * [9] T. Nishida, A note on a theorem of Nirenberg, Journal of Differential Geometry, (1977).
  * [10] D. Revuz and M. Yor, Continuous Martingales and Brownian Motion, Springer, (2005).
  * [11] R. L. Schilling, Measures Integrals and Martingales, Cambridge University Press, (2005).
  * [12] Hui-Hsiung Kuo, Introduction to Stochastic Integration, Springer, (2006).
  * [13] Y. L. Dalecky and S. V. Fomin, Measures and Differential Equations in Infinite-Dimensional Space, Springer, (1991).
  * [14] S. Albeverio, Z. Brzezniak, J. L. Wu, Existence of global solutions and invariant measures for stochastic differential equations driven by Poisson type noise with non-Lipschitz coefficients, J. Math. Anal. Appl., (2010).
  * [15] C. Marinelli and M. Röckner, On the maximal inequalities of Burkholder, Davis and Gundy, J. Expo. Math., (2016).
  * [16] S.Albeverio, YU. G. Kondratiev, T. V. Tsikalenko, Stochastic dynamics for quantum lattice systems and stochastic quantization I: Ergodicity, J. Random Oper, and Stoch Eqn., (1994).
  * [17] S.Albeverio, YU. G. Kondratiev, T. V. Tsikalenko, M. Röckner Glauber Dynamics For Quantum Lattice Systems, Reviews in Mathematical Physics, (2001).
  * [18] M. H. Protter and C. B. Morrey, A First Course in Real Analysis, , Springer, (1991).
  * [19] P. J. Nahin, Inside Interesting Integrals, Springer, (2015).
  * [20] S. Lang, Real and Functional Analysis, Springer, (1993).
  * [21] G. Parisi and Y. Wu, Perturbation theory without gauge fixing, Scientia Sin. 24, (1981).
  * [22] G. J. Lasinio and P. K. Mitter, On the stochastic quantization of field theory, Comm. Math. Physics, (1985).
  * [23] S. Albeverio and M. Röckner, Stochastic differential equations in infinite dimensions: solution via Dirichlet forms, Prob. Th. Rel. Fields, (1991).
  * [24] G. Royer, Processus de diffusion associe à certains modèles d‘Ising a spin continus, Z. Wahrsch. Verw. Gebiete, (1979)
  * [25] R. L. Dobrushin, Markov processes with a large number of locally interacted components — existence of the limiting process and its ergodicity, Problems of Information Transmission, (1971)
  * [26] G. Da Prato, J. Zabczyk, Ergodicity for Infinite Dimensional Systems, _London Mathematical Society Lecture Note Series_ 229, University Press, Cambridge, (1996).
  * [27] J. Inglis, M. Neklyudov, B. Zegarliński, Ergodicity for infinite particle systems with locally conserved quantities, _Infin. Dimens. Anal. Quantum Probab. Relat. Top_. 15 (2012), No. 1, 1250005.
  * [28] O. Lanford, J. Lebowitz, E. Lieb, Time Evolution of Infinite Anharmonic Systems, J. Stat. Phys. 16 (1977), No. 6, 453–461.
  * [29] G. Chargaziya and A. Daletskii, Stochastic differential equations in a scale of Hilbert spaces 2. Global solutions, In preparation.


ifaamas [AAMAS ’23]Proc. of the 22nd International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2023)May 29 – June 2, 2023 London, United
KingdomA. Ricci, W. Yeoh, N. Agmon, B. An (eds.) 2023 2023 442 1 Tsinghua
University, 2 4Paradigm Inc., 3 Fudan University, 4 Shanghai Artificial
Intelligence Laboratory† Corresponding Author

# Learning Graph-Enhanced Commander-Executor
for Multi-Agent Navigation

Xinyi Yang1, Shiyu Huang2, Yiwen Sun3, Yuxiang Yang1, Chao Yu1,4, Wei-Wei Tu2,
Huazhong Yang1†, Yu Wang1†
<EMAIL_ADDRESS>
###### Abstract.

This paper investigates the multi-agent navigation problem, which requires
multiple agents to reach the target goals in a limited time. Multi-agent
reinforcement learning (MARL) has shown promising results for solving this
issue. However, it is inefficient for MARL to directly explore the (nearly)
optimal policy in the large search space, which is exacerbated as the agent
number increases (e.g., 10+ agents) or the environment is more complex (e.g.,
3$D$ simulator). Goal-conditioned hierarchical reinforcement learning (HRL)
provides a promising direction to tackle this challenge by introducing a
hierarchical structure to decompose the search space, where the low-level
policy predicts primitive actions in the guidance of the goals derived from
the high-level policy. In this paper, we propose _M ulti-Agent Graph-Enhanced
Commander-EXecutor_ (MAGE-X), a graph-based goal-conditioned hierarchical
method for multi-agent navigation tasks. MAGE-X comprises a high-level _Goal
Commander_ and a low-level _Action Executor_. The _Goal Commander_ predicts
the probability distribution of the goals and leverages them to assign the
most appropriate final target to each agent. The _Action Executor_ utilizes
graph neural networks (GNN) to construct a subgraph for each agent that only
contains its crucial partners to improve cooperation. Additionally, the Goal
Encoder in the _Action Executor_ captures the relationship between the agent
and the designated goal to encourage the agent to reach the final target. The
results show that MAGE-X outperforms the state-of-the-art MARL baselines with
a 100% success rate with only 3 million training steps in multi-agent particle
environments (MPE) with 50 agents, and at least a 12% higher success rate and
2$\times$ higher data efficiency in a more complicated quadrotor 3$D$
navigation task.

###### Key words and phrases:

Multi-agent Reinforcement Learning, Goal-conditioned Reinforcement Learning,
Multi-agent Navigation, Graph Neural Network

##  1\. Introduction

Navigation is a typical task in the intelligent agent system, applied in a
wide range of applications, such as autonomous driving Bresson et al. (2017);
Grigorescu et al. (2020), logistics and transportation Liu and Hu (2009); Gao
et al. (2018), and search and rescue for disasters Kleiner et al. (2006);
Calisi et al. (2005). In this paper, we consider a multi-agent navigation task
where multiple agents simultaneously move to the target goals in a cooperative
fashion. Multi-agent reinforcement learning (MARL) has attracted significant
attention due to its powerful expressiveness in multi-agent navigation tasks
Yu et al. (2022); Jin et al. (2019); Marchesini and Farinelli (2022); Xia et
al. (2021).

The common approach to searching for the near-optimal solution in MARL Yu et
al. (2021); Wen et al. (2022) is to directly train a policy that produces
environmental actions for agents. However, learning the strategy directly from
large search space results in low data efficiency, which is more severe as the
number of agents or the complexity of the environment increases. Therefore,
the existing methods in navigation tasks target simple scenarios with few
agents. Goal-conditioned HRL Dayan and Hinton (1992); Kulkarni et al. (2016);
Nachum et al. (2018); Levy et al. (2017); Hoang et al. (2021); Kim et al.
(2021); Zhang et al. (2020) has been recognized as an effective paradigm to
address this problem, comprising a high-level policy that breaks the original
task into a series of subgoals and a low-level policy that aims at the arrival
of these subgoals. Recent works Jeon et al. (2022); Chen et al. (2021) in
goal-conditioned HRL mainly focus on developing high-level policies for
providing agents with appropriate subgoals. However, designating the subgoals
may confuse agents on which target goals they should reach.

Graph neural networks (GNN) have been widely applied in multi-agent
cooperative tasks due to their effective learning of agents’ graph
representations. The literature on GNN Niu et al. (2021); Li et al. (2020);
Jiang et al. (2018) in MARL constructs a graph whose nodes represent agents’
information to model the interaction among them and encourage agents to
cooperate. To enhance the cooperation among agents, we can leverage GNN in the
low-level policy in HRL to capture the relationship of agents and express
preferences for different teammates.

To improve data efficiency and cooperation, we propose _M ulti-Agent Graph-
Enhanced Commander-EXecutor_ (MAGE-X), a graph-based goal-conditioned
hierarchical framework in multi-agent navigation tasks. MAGE-X consists of two
components, the high-level Goal Commander and the low-level Action Executor.
For the target-goal assignment, the Goal Commander infers the probability
distribution of target goals to assign the most appropriate target goal for
each agent instead of the subgoal. As a result, the multi-agent navigation is
converted to multiple single-agent navigation tasks in the multi-agent
environment, in which each agent is required to reach the designated goal
while avoiding collisions. In the Action Executor, we take advantage of GNN to
perceive the relationship among agents and produce a subgraph for each agent
to decide to whom they should pay attention. After that, the State Extractor
receives the correlation between the agent and its target goal from the Goal
Encoder and the agent’s embedded feature in the subgraph to empower the team
representation with strong goal guidance, promoting agents to reach target
goals. The suggested scheme is challenged against MARL baselines in multi-
agent particle environments (MPE) Lowe et al. (2017a) with a massive number of
agents and a more complicated quadrotor navigation task Panerati et al.
(2021). The experimental results demonstrate that MAGE-X outperforms the MARL
baselines, achieving a 100% success rate with only 3 million training steps in
MPE with 50 agents. Furthermore, MAGE-X attains at least a 12% higher success
rate and 2$\times$ higher data efficiency in the quadrotor navigation task.

Our contributions can be summarized as follows:

  * •

We introduce a graph-based goal-conditioned framework in multi-agent
navigation tasks, _Multi-Agent Graph-enhanced Commander-Executor_ (MAGE-X), to
solve the problem of data efficiency and cooperation in large search space.

  * •

We develop a high-level Goal Commander, which utilizes the probability
distribution of goals to allocate each agent to the most appropriate target
goal.

  * •

We propose the low-level Action Executor, which adopts GNN to improve the
coordination, and the Goal Encoder and the State Extractor to encourage agents
to complete the task.

  * •

MAGE-X converges much faster and substantially outperforms MARL algorithms in
multi-agent particle environments (MPE) Lowe et al. (2017a) with a massive
number of agents and a quadrotor navigation task Panerati et al. (2021).

##  2\. Related Work

###  2.1. Navigation

Navigation has been widely investigated in recent years, where RL has shown
its ability to solve various applications Zhu et al. (2017); Marchesini and
Farinelli (2020); Koh et al. (2020); Yang et al. (2022). For example, Rao Rao
et al. (2021) presents a model-embedded actor-critic architecture for the
multi-goal visual navigation task. This embedded model consists of two
auxiliary task modules, a path closed-loop detection module to understand
whether the state is experienced and a state-target matching module to
distinguish the difference between states and goals. Furthermore, Zhu Zhu et
al. (2017) introduces a target-driven actor-critic model to achieve greater
adaptability and flexibility for the target-driven visual navigation task.

As for multi-agent navigation tasks in MARL Jin et al. (2019); Marchesini and
Farinelli (2022); Xia et al. (2021); Yu et al. (2022), the difficulties lie in
data efficiency and cooperation in large space spaces, which is exacerbated as
agent number increases and the environment becomes more complicated. EPS
Marchesini and Farinelli (2022) is introduced to enhance exploration
efficiency and improve sample efficiency in multi-robot mapless navigation,
which uses the evolutionary population periodically generated from robots’
policies to search for different and novel states. Furthermore, Xia Xia et al.
(2021) proposes an inference-based hierarchical reinforcement learning
framework (IHRL) to address the multi-agent cooperative navigation problem via
the interplay of high-level inference and low-level actions. The proposed
MAGE-X specializes in navigation tasks and outperforms the MARL baselines with
high sample efficiency.

###  2.2. Goal-conditioned HRL

Goal-conditioned hierarchical reinforcement Learning (HRL) has shown its
capability in a wide range of tasks Chane-Sane et al. (2021); Nair and Finn
(2019); Pertsch et al. (2020) with a hierarchy consisting of high-level and
low-level policies. The high-level policy generates intermediate subgoals
every global timestep, which is regarded as a goal guidance of the low-level
policy.

Kreidieh Kreidieh et al. (2019) addresses the challenges of the interactions
between high-level and low-level agents by introducing inter-level
cooperation. This inter-level cooperation is given by modifying the high-level
policy’s objective function and subsequent gradients. Another representative
is LGA Chen et al. (2021), where the subgoal assignment is parameterized as
latent variables to be trained. LGA directly provides primitive actions for
agents depending on latent variables to accomplish multi-agent tasks. MASER
Jeon et al. (2022) automatically produces subgoals for agents from the
experience replay buffer relying on both individual and total Q-values.
Besides, it adopts the individual intrinsic reward for each agent to reach the
assigned subgoals and maximize the joint action value. However, the generation
of subgoals may be inefficient since the correspondence between subgoals and
the final goals is implicit. In this paper, MAGE-X utilizes the goal-
conditioned hierarchical framework in multi-agent navigation tasks to improve
the sample efficiency, where the high-level policy deals with target-goal
assignment and the low-level policy deals with the action execution for each
agent.

###  2.3. Graph Neural Networks

Graph neural networks (GNN) Scarselli et al. (2008) are broadly used due to
their effective learning of graph representations and the ability to capture
the relationships of different graphs. Recently, several works have applied
GNN in multi-agent systems to model agents’ interactions. HAMA Ryu et al.
(2020) proposes a hierarchical graph attention network that captures the
underlying relationships at the agent-level and the group-level, enhancing
generalization and scalability. MAGIC Niu et al. (2021) is a novel graph
communication protocol that implies the topology of agents’ interactions,
helping agents decide when to communicate and with whom to communicate. DICG
Li et al. (2020) leverages dynamic coordination graphs to infer joint actions
and values implicitly. GCS Ruan et al. (2022) learns coordinated behaviors by
factorizing the joint team policy into a graph generator and a graph-based
coordinated policy. The generator captures the underlying dynamic correlation
of agents, which is then exploited by the graph-based coordinated policy. The
Action Executor of MAGE-X benefits from GNN to capture the team representation
and introduces a Goal Encoder and a State Extractor to strengthen the
expression of target goals.

##  3\. Preliminary

Figure 1. Overview of _Multi-Agent Graph-enhanced Commander-Executor_
(MAGE-X).

###  3.1. Dec-MDPs

In this paper, we consider a variant of MDP to solve the decentralized control
problem in stochastic environments called Decentralized Markov Decision
Processes (Dec-MDPs).

Here, the multi-agent Dec-MDPs problem is formulated as:

$<\mathcal{N},\mathcal{S},\mathcal{A},\mathcal{T},R,G,\mathcal{O},\gamma>,$
(1)

where $\mathcal{N}\equiv\\{1,...,n\\}$ is a set of $N=|\mathcal{N}|$ agents.
Note that $\mathcal{S}$ is a set of global states in the assumption that
$\mathcal{S}$ is jointly observable. $\mathcal{A}$ is the action space of each
agent, and $\mathbf{A}\equiv\mathcal{A}^{N}$ is the joint action space.
$\mathcal{O}$ is the observation space. $R$ represents the reward function,
and $R(s,\mathbf{a},s^{\prime})$ is the reward obtained from the transition of
joint actions $\mathbf{a}\in\mathbf{A}$ from the state $s\in\mathcal{S}$ to
the state $s^{\prime}\in\mathcal{S}$. $\gamma\in[0,1)$ is the discount factor.
$\mathcal{T}(s,\mathbf{a},s^{\prime}):\mathcal{S}\times\mathbf{A}\times\mathcal{S}\mapsto[0,1]$
is the dynamics function denoting the transition probability. $G$ is the
observation function, and $G(s,\mathbf{a},s^{\prime},o_{i})$ is the
probability of agents $i\in\mathcal{N}$ seeing observation
$o_{i}\in\mathcal{O}$. Each agent has a policy
$\pi^{i}(a^{i}_{t}|o^{i}_{1:t})$ to produce action $a^{i}_{t}$ from
observations $o^{i}_{t}$ at step $t$. And agents need to maximize the expected
discounted return $\mathbb{E}\sum^{\inf}_{l=0}\gamma^{l}r_{t+l}$, where
$r_{t}=R(s_{t},\mathbf{a}_{t},s_{t+1})$ is the joint reward at step $t$.

###  3.2. Graph Neural Networks

Graph neural networks (GNN) are a special type of neural network capable of
dealing with data in the graph structure. The critical ingredient of GNN is
pairwise message passing, i.e., graph nodes iteratively update their
representations by exchanging information with their neighbors. The general
formula is given as below:

$h_{i}^{(l)}=\sigma(\sum_{j\in
N_{i}}\frac{1}{\sqrt{d_{i}d_{j}}}(h_{j}^{l-1}W^{(l)})),$ (2)

where $h_{i}$ is the feature vector of node $i$. $N_{i}$ represents a set of
neighbouring nodes of $i$ and $W^{(l)}$ is the learnable weights in the layer
$l$. $\sigma$ is the activation function. $d_{i}$ is the dimension of feature
stored in node $i$. Equation 2 shows that the feature of node $i$ will be
influenced by its neighbors. In this paper, we use graph convolutional
networks (GCN) Kipf and Welling (2016) to model the interaction of agents. GCN
is a variant of convolution neural networks (CNN) to be applied in the data
with graph structure.

##  4\. Methodology

Figure 2. Workflow of Action Executor, including a Subgraph Extractor, a Goal
Encoder, a State Extractor for representation learning and an Action
Generator.

In this section, we introduce the proposed framework, MAGE-X, to improve
sample efficiency and the cooperation in multi-agent navigation tasks. The
overview of our framework is demonstrated in Fig. 1. MAGE-X comprises two
components, the Goal Commander and the Action Executor. The high-level Goal
Commander follows the principles of centralized-training-centralized-execution
(CTCE). In contrast, the low-level Action Executor is in a decentralized
setting with partial observation of $N$ agents, where agent $k$ receives local
observation, $o_{t}^{k}$, at step $t$. Agent $k$ learns the policy, $\pi_{k}$,
to produce a distribution over actions at each time step $t$,
$a_{t}^{k}\sim\pi_{k}(a_{t}^{k}|o_{t}^{k})$. The process of a navigation task
begins with the Goal Scheduler in the Goal Commander receiving the spawn
locations of all the agents and the target goals. The probability distribution
of the target goals is predicted by the scheduler, and each agent is assigned
the most appropriate target goal rather than the subgoal. Therefore, the
multi-agent navigation is converted to multiple single-agent navigation tasks
in the multi-agent environment, where each agent is required to reach the
given goal as quickly as possible while avoiding collisions. Take agent $k$ as
an example. The Subgraph Extractor takes in the observation of agent $k$ and
other agents and produces the subgraph of agent $k$ only including its crucial
neighbors to improve cooperation. The relationship of agent $k$ and its target
goal is extracted from the Goal Encoder, which is then sent to the State
Extractor combined with the feature of agent $k$ in the subgraph to endow the
team representation with strong goal guidance. Finally, agent $k$ takes the
preliminary action from the Action Generator to complete the navigation task.

###  4.1. Goal Commander

Goal assignment is a long-studied maximal matching problem, especially in
scenarios with large-scale agents. The Goal Commander builds upon a Goal
Scheduler module for target-goal assignment, which produces the probability
distribution of target goals. The designed reward is related to the distance
cost of the Hungarian algorithm Jonker and Volgenant (1986), a state-of-the-
art classical method to tackle the combinatorial optimization algorithm in
graph theory.

Goal Scheduler: This module is made up by a Multi-Layer Perception (MLP)
layer, $f_{sche}$, that takes the positions of all agents, $P_{a}$, and the
positions of target goals, $P_{g}$, as input. We obtain the probability of the
target goals, $P_{goal}$, by computing the softmax operator over the output of
$f_{sche}$:

$P_{goal}=Softmax(f_{sche}(P_{a},P_{g})).$ (3)

Thereafter, $P_{goal}$ is ranked in decreasing order and the reordered goals
$1...N$ are sequentially assigned to agent $1...N$. The reward of the Goal
Scheduler, $R_{c}$, represents the distance cost of our assignment strategy,
$C_{c}$, against the distance cost of the Hungarian algorithm, $C_{h}$:

$R_{c}=1-\frac{C_{c}}{C_{h}}.$ (4)

###  4.2. Action Executor

The Action Executor is designed for high cooperation where agents speedily
reach the designated goal with little collision in the multi-agent
environment. The workflow of the Action Executor is illustrated in Fig. 2. It
consists of the Subgraph Extractor, the Goal Encoder, the State Extractor, and
the Action Generator. The Subgraph Extractor encodes the observations of all
agents and yields a subgraph for agent $k$ only containing the crucial
teammates. The Goal Encoder extracts the correlation of agent $k$ and its
assigned goal, which is then fed into the State Extractor with the feature of
agent $k$ in the subgraph to endow the team representation with target goal
guidance. Finally, the Action Generator produces the action for the agent $k$.

The environmental reward for each agent, $R_{e}$, is the linear combination of
the complete bonus, $R_{b}$, the distance penalty, $R_{d}$, and the collision
penalty, $R_{c}$:

$R_{e}=\alpha{R_{b}}+\beta{R_{d}}+\gamma{R_{c}},$ (5)

where $\alpha$, $\beta$ and $\gamma$ are the coefficient of $R_{b}$, $R_{d}$
and $R_{c}$, respectively.

Subgraph Extractor: The Subgraph Extractor is comprised of the Observation
Encoder and the Graph Encoder. In the Observation Encoder, we apply an MLP
layer $f_{o}$ to encode the observations of all agents and GCN to produce a
fully connected graph of agents, $G_{a}$. This can be formulated as:

$G_{a}=GCN\left(\left(f_{o}(o^{1}),f_{o}(o^{2}),..f_{o}(o^{N})\right),A_{f}\right),$
(6)

where $A_{f}$ is denoted as an adjacent matrix of a fully connected graph. In
the Graph Encoder, we compute the gumbel softmax Jang et al. (2016) over the
feature of $G_{a}$ updated by an MLP layer, $f_{g}$. Thus, we can obtain an
adjacent matrix of $A_{s}^{k}$ through it:

$A_{s}=Gumbel\\_Softmax(f_{g}(G_{a})).$ (7)

Afterwards, we use GCN to generate $G_{s}^{k}$:

$G_{s}^{k}=GCN(G_{a},A_{s}^{k}).$ (8)

The feature of the agent $k$ in $G_{s}^{k}$ is then sent to the State
Extractor. Note that there are $l_{g}$ blocks in the Graph Encoder.

Goal Encoder and State Extractor: To capture the correlation between the agent
$k$ and its assigned goal, the Goal Encoder comprises an MLP layer $f_{goal}$,
and takes in the target goal’s position $P_{g}^{k}$, and the agent’s
observation $o^{k}$. This can be formulated as:

$E_{goal}^{k}=f_{goal}(P_{g}^{k},o^{k}).$ (9)

Receiving the relationship between the agent and its target goal and the
embedded feature of agent $k$ in $G_{s}$, $E_{a}^{k}$, we leverage the State
Extractor to enhance the team representation with target goal guidance and
output $E_{all}^{k}$. The State Extractor consists of an MLP layer
$f_{state}$, and recurrent neural networks (RNN) in consideration of the high
correlation between current and historical states:

$E_{all}^{k}=RNN\left(f_{state}\left(concat\left(E_{goal}^{k},E_{a}^{k}\right)\right)\right).$
(10)

###  4.3. Multi-agent Commander-Executor Training

Algorithm 1 Training Procedure of _MAGE-X_

0: The positions $P_{a}$ of all agents, the joint observation $\mathbf{o}$ of
all agents , and the positions $P_{g}$ of target goals.

0: Final policy $\pi_{\theta}$ for the Goal Commander and
$\pi_{\theta^{\prime}}$ for the Action Executor.

1: Initialize: agents number $N$, maximal steps in an episode $T_{e}$, params
in the Goal Commander $\theta$, $\phi$, params in the Action Executor
$\theta^{\prime}$, $\phi^{\prime}$, the Goal Commander buffer $D$, the Action
Executor buffer $D^{\prime}$.

2: while $\theta$ and $\theta^{\prime}$ not converges do

3: Reset environment and get $P_{a}$, $P_{g}$.

4: Initialize: the step-count $t\leftarrow 1$ in $D$, the step-count
$t^{\prime}\leftarrow 1$ in $D^{\prime}$.

5: $P_{goal}\leftarrow$ Goal_Commander$(P_{a}$, $P_{g})$.

6: Calculate $\pi_{\theta}(a_{t}|\mathbf{o}_{t})$ and
$V_{\phi}(\mathbf{o}_{t})$.

7: Perform $a_{t}\sim\pi_{\theta}(a_{t}|\mathbf{o}_{t})$.

8: while $t^{\prime}<T_{e}$ and not terminal do

9: $E_{all}^{k}\leftarrow$ Action Executor ($\mathbf{o}$, $P_{g}^{k}$)  for
each agent $k$

10: Calculate $\pi_{\theta^{\prime}}({a^{\prime k}_{t^{\prime}}}|{o^{\prime
k}_{t^{\prime}}})$ and $V_{\phi^{\prime}}({o^{\prime k}_{t^{\prime}}})$ for
each agent $k$.

11: Perform $a^{\prime k}_{t^{\prime}}\sim\pi_{\theta^{\prime}}(a^{\prime
k}_{t^{\prime}}|{o^{\prime k}_{t^{\prime}}})$ for each agent $k$.

12: Receive $r^{\prime}_{t^{\prime}}$ and ${o^{\prime k}_{t^{\prime}+1}}$ for
each agent $k$.

13: Store $({o^{\prime k}_{t^{\prime}}},{a^{\prime
k}_{t^{\prime}}},\pi_{\theta^{\prime}},({a^{\prime
k}_{t^{\prime}}}|o^{\prime}_{t^{\prime}}),V_{\phi^{\prime}}({o^{\prime
k}_{t^{\prime}}}),r^{\prime}_{t^{\prime}},{o^{\prime}}^{k}_{t^{\prime}+1})$ in
$D^{\prime}$.

14: $t^{\prime}\leftarrow t^{\prime}+1$

15: end while

16: Receive $r_{t}$ and $o_{t+1}$.

17: $t\leftarrow t+1$

18: Store
$(o_{t},a_{t},\pi_{\theta},(\mathbf{a}_{t}|\mathbf{o}_{t}),V_{\phi}(o_{t}),r_{t},o_{t+1})$
in D.

19: Perform update of $\theta$, $\phi$, $\theta^{\prime}$ and $\phi^{\prime}$.

20: end while

MAGE-X, following the goal-conditioned MARL framework, trains two policy
networks for the Goal Commander and the Action Executor separately, which are
optimized by maximizing the accumulated reward in the entire episode via
reinforcement learning. We use Multi-agent Proximal Policy Optimization
(MAPPO) Yu et al. (2021), a multi-agent variant of Proximal Policy
Optimization (PPO) Schulman et al. (2017), as the policy optimizer.

As shown in Algorithm 1, MAGE-X takes in the positions of agents, the
observations of agents, and the positions of landmarks. Then, it produces the
final policy $\pi_{\theta}$ for the Goal Commander and $\pi_{\theta^{\prime}}$
for the Action Executor. First, we initialize the number of agents along with
several training parameters, including maximal steps, parameters in the Goal
Commander, parameters in the Action Executor, the Goal Commander reply buffer,
$D$, and the Action Executor reply buffer, $D^{\prime}$ (Line 1). The Goal
Commander only performs one action every episode to assign the goals to agents
in the beginning (Line $5\sim 7$) and receives the reward $r_{t}$ and the
subsequent observation $o_{(t+1)}$ at the end of each episode, where $t$
represents the step-count in $D$ (Line 15 and 16). Thereafter, we update
$\theta$ for the policy network $\pi_{\theta}$, and $\phi$ for the value
network $V_{\phi}$, in the Goal Commander. Regarding the Action Executor, it
outputs the action ${a^{\prime}}^{k}_{t^{\prime}}$ for each agent $k$, and
stores a group of data in $D^{{}^{\prime}}$ at each timestep $t^{\prime}$
(Line $9\sim 13$). Similarly, we update $\theta^{\prime}$ for the policy
network $\pi_{\theta^{\prime}}$, and $\phi^{\prime}$ for the value network
$V_{\phi^{\prime}}$, in the Action Executor.

##  5\. Experiments

###  5.1. Task Setup

To evaluate the effectiveness of our algorithm in large search space, we
consider MPE Lowe et al. (2017a) with a massive number of agents and pybullet-
gym-drones Panerati et al. (2021) in 3$D$ space as the experimental
environments, as shown in Fig. 3 and Fig. 4. We select three typical tasks
from these two environments: Simple Spread, Push Ball, and Drones. Then, we
conduct experiments with $N\in\\{5,20,50\\}$ agents in Simple Spread and
$N\in\\{5,20\\}$ agents in Push Ball in MPE. Drone is a more complicated
quadrotor navigation task in gym-pybullet-drones, which adopts aerodynamic
models of quadrotors to narrow the gap between the simulation and the real
world. Therefore, quadrotors in Drone require stronger cooperation to avoid
the crash. We conduct experiments with 2 and 4 quadrotors in this 3$D$
simulator.

####  5.1.1. Simple Spread

We utilize Simple Spread environment in MPE Lowe et al. (2017a), a classical
2D navigation task. The episode starts with the initialization of $N$ agents
and $N$ landmarks. When all the agents reach the landmarks, this task is 100%
successful. The consequence of the collision between agents is that they will
bounce off each other, which is detrimental to navigation efficiency. The
available discrete actions of agents include _Up_ , _Down_ , _Left_ , and
_Right_. The task’s difficulty increases with a larger agent number and map
space. The experiment is conducted on 5, 20, and 50 agents. In the 5-agent
setting, the spawn locations of agents and landmarks are random on the map
with a size of 4. In the setting of $N\in\\{20,50\\}$, the spawn locations of
agents and landmarks are randomly initialized in four challenging maps with
the size of 36 and 100, respectively, as shown in Fig 3(b). The horizons of
steps in $N=5$, $20$, $50$ are 60, 100, and 120, respectively.

(a) Simple Spread

(b) Simple Spread with 20, 50 agents

(c) Push Ball

(d) Push Ball with 20 agents

Figure 3. Experimental environments of Simple Spread and Push Ball in MPE. We
remark that (b) represents simplified demonstration of 4 challenging task
modes in Simple Spread, where the spawn locations of agents and landmarks are
randomly distributed in the orange lines and the blue lines, respectively. (d)
expresses simplified demonstration of 4 typical task modes in Push Ball, where
the spawn locations of agents and landmarks are randomly distributed in the
orange lines, and the spawn locations of balls are randomly distributed in the
pink lines. Figure 4. Experiment environments of Drone.

####  5.1.2. Push Ball

Push Ball is a more complicated two-stage navigation task in MPE Lowe et al.
(2017a), requiring each agent to find the ball first, then push it into the
landmark. At the beginning of each episode, $N$ agents, $N$ balls, and $N$
landmarks are initialized in the environment. The success rate of the task is
the number of agents reaching the landmarks with the balls to the total number
of all agents. The available discrete actions of agents include _Up_ , _Down_
, _Left_ , and _Right_. We conduct the experiments in the setting of 5 and 20
agents. In the scenarios of $N=5$, the spawn locations of agents, balls, and
landmarks are randomly distributed on the map of size 16. For $N=20$, their
initialization follows four challenging space arrangements on the map with a
size of 144, as displayed in Fig 3(d). The horizons of the steps in $N=5$ and
$20$ are 100 and 200, respectively.

####  5.1.3. Drone

We further adopt Drone in pybullet-gym-drones Panerati et al. (2021), a 3D
simulator for flying quadrotors based on pybullet. Drone models the dynamics
of quadrotors and controls them by adjusting the torque. Unlike MPE, the
collision between quadrotors will lead to a crash and the failure of the task.
In our navigation task, the spawn locations of $N$ quadrotors and $N$ landmark
are random in the coordinates $x$ and $y$, but fixed in the coordinate $z$,
with $x\in(-1.5,1.5),y\in(-1.5,1.5)$ and $z=1.5$. The task’s objective is that
quadrotors are required to reach all the landmarks on a limited time budget.
The action space of each quadrotor is the direction of the acceleration in
$x$, $y$, $z$ coordinate, containing _Forward_ , _Backward_ , and _Stop_ in
each coordinate. We consider the experiments with $2$ and $4$ quadrotors. In
our setting, the frequency at which the physics engine steps is 120 $HZ$; the
max speed is 2 $m/s$, and the acceleration is 5 $m/{s}^{2}$. In every low-
level step, we utilize the predicted acceleration direction to calculate each
quadrotor’s target velocity, and then the quadrotor executes the action every
four physics engine steps. The horizon of the steps in $N=2$ and $4$ is 120.

###  5.2. Implementation Details

Each RL training is performed over 3 random seeds for a fair comparison. Each
evaluation score is expressed in the format of ”mean (standard deviation)”,
which is averaged over a total of 300 testing episodes, i.e., 100 episodes per
random seed. In addition, we use the success rate, the number of landmarks
reached by the agents to the total number of landmarks, to express the
performance of each algorithm. In the Drone, we additionally consider the
collision rate, the number of crashed quadrotors to the total number of
quadrotors, to express the capability of cooperation. Our experimental
platform involves a 128-core CPU, 256GB RAM, and an NVIDIA GeForce RTX 3090Ti
with 24GB VRAM.

Figure 5. Comparison between MAGE-X and other baselines in Simple Spread with
$N=5$, $20$, $50$. Figure 6. Comparison between MAGE-X and other baselines in
Push Ball with $N=5$, $20$. Figure 7. Evaluation performance of the success
rate and the collision rate between MAGE-X and baselines in Drone. The node in
the upper left corner of the figure represents higher performance. Figure 8.
Comparison between MAGE-X and other baselines in Drone.

###  5.3. Baselines

To demonstrate the effectiveness of our methods, we challenge it against four
MARL baseline approaches.

  * •

MAPPO Yu et al. (2021): This is the first and the most direct approach for
applying PPO in MARL. It equips all agents with one shared set of parameters
and updates the shared policy through agents’ aggregated trajectories.

  * •

Multi-Agent-Transformer (MAT) Wen et al. (2022): This is an encoder-decoder
architecture that leverages the multi-agent advantage decomposition theorem to
transform the joint policy search problem into a sequential decision-making
process.

  * •

DICG Li et al. (2020): This graph-based method comprises a module that infers
the dynamic coordination graph structure and a GNN module that implicitly
reasons about the joint actions or value based on the former module’s output.

  * •

Maser Jeon et al. (2022): This is a goal-conditioned MARL method that
automatically generates subgoals for multiple agents from the experience
replay buffer by considering both the individual Q-value and the total
Q-value.

###  5.4. Main Results

We present and analyze the experiment results of MAGE-X and MARL baselines in
three competitive environments.

####  5.4.1. Simple Spread

We demonstrate the training curves in Fig. 5 and the evaluation performance in
Table 1. The results suggest that MAGE-X performs the best, especially in
scenarios with 50 agents, where it converges to the near-optimal solution
quickly with a success rate of 100%, attaining training efficiency more than
$10\times$ higher than other competitors. The results show that our algorithm
performs the best, especially in the scenario with 50 agents. This graph-
enhanced hierarchical framework helps agents quickly handle the problem of
reaching targets with high cooperation. MAT excels in other MARL baselines and
can achieve a success rate of 100% in the 5-agent setting, indicating that MAT
agents profit from the action information of their teammates. However, as the
number of agents increases, the performance of MAT degrades significantly.
DiCG is on-par with MAPPO, which indicates that directly utilizing the graph-
based method can’t contribute to better cooperation and efficiency. Although
MASER is also a goal-conditioned HRL method, it is the worst among all the
competitors. It implies that the value-based method, MASER, fails to discover
effective cooperation strategies within limited training steps since it infers
subgoals from the experience replay buffer and lacks a strong connection
between agents and target goals.

| MAPPO | MAT | DICG | MASER | MAGE-X
---|---|---|---|---|---
5 agents | 0.82(0.03) | 1.00(0.01) | 0.71(0.05) | 0.06(0.12) |  1.00(0.01)
20 agents | 0.50(0.31) | 0.56(0.26) | 0.41(0.04) | 0.02(0.23) |  1.00(0.01)
50 agents | 0.13(0.02) | 0.11(0.01) | 0.12(0.02) | 0.01(0.05) |  1.00(0.01)
Table 1.  Evaluation performance of the success rate between MAGE-X and baselines in Simple Spread. | MAPPO | MAT | DICG | MASER | MAGE-X
---|---|---|---|---|---
5 agents | 0.20(0.01) | 0.32(0.04) | 0.20(0.01) | 0.01(0.01) |  1.00(0.01)
20 agents | 0.26(0.01) | 0.25(0.02) | 0.36(0.01) | 0.01(0.01) |  1.00(0.01)
Table 2.  Evaluation performance of the success rate between MAGE-X and baselines in Push Ball. | 2 agents | 4 agents
---|---|---
| Suc. Rate | Colli. Rate | Suc. Rate | Colli. Rate
MAPPO | 0.83(0.03) | 0.10(0.01) | 0.64 (0.01) | 0.18 (0.02)
MAT | 0.61(0.01) | 0.09 (0.01) | 0.34(0.04) |  0.06(0.01)
DICG | 0.45(0.02) | 0.03(0.02) | 0.12(0.01) | 0.07(0.01)
MAGE-X |  0.95(0.03) |  0.02(0.01 ) |  0.79(0.07) | 0.12 (0.01)
Table 3.  Evaluation performance of the success rate and the collision rate
between MAGE-X and baselines in Drones.

####  5.4.2. Push Ball

As shown in Fig. 6 and Table 2, we conduct the experiments with
$N\in\\{20,50\\}$ agents in Push Ball. The difficulty of Push Ball lies in
that it requires a two-stage goal assignment, i.e., the agents first get the
designated ball and then reach the target landmark with the ball.
Nevertheless, MAGE-X still achieves a 100% success rate with few training
timsteps. In contrast, except for MAT, whose success rate slightly increases,
other baselines obtain suboptimal policies with a success rate of 20% in the
5-agent setting. In the scenario with 20 agents, all baselines fail to reach
the goals. The results express that the high-level Goal Commander in MAGE-X
has the potential to simultaneously tackle multiple goal assignment problems,
for it breaks this $M$stage goal assignment into $M$ independent tasks, only
requiring the information of assigned targets.

####  5.4.3. Drones

We report the training performance in Fig. 8 and the evaluation results in
Fig. 7 and Table 3. The experiment shows that MAGE-X is superior to other
competitors with a success rate of 95% in $N=2$ and 79% in $N=4$ in the
physically realistic 3D environment, Drone. Unlike MPE, the best competitor in
Drone among baselines is MAPPO rather than MAT, indicating that MAPPO has
better competence in complex tasks with few agents. Specifically, MAGE-X
outperforms MAPPO, with 12% higher and 15% higher success rates in $N=2$ and
$4$, respectively. Furthermore, MAGE-X manifests high coordination with a low
collision rate of 0.02% in $N=2$ and 0.12% in $N=4$, demonstrating that MAGE-X
succeeds in assigning target goals to agents to coordinate and capture the
interaction among agents. Although MAPPO performs best among baselines, its
collision rate is remarkably high. We speculate that MAPPO agent pursues high
individual capability instead of cooperation. Furthermore, the sample
efficiency of MAGE-X is $2\times$ higher than that of MAPPO in the 4-agent
setting.

###  5.5. Ablation Study

To illustrate the effectiveness of each component of MAGE-X, we consider 3
variants of our method in Simple Spread with 50 agents:

  * •

MAGE-X w. RG: We substitute the Goal Scheduler in the Goal Commander with
random sampling without replacement to assign each agent a random target goal.

  * •

MAGE-X-Atten: We remove GCN in the Obs. Encoder and replace the Graph Encoder
in the Action Executor with the attention module Vaswani et al. (2017) to
extract the relationship of agents. The concatenation of
$(f_{o}(o_{1}),f_{o}(o_{2}),..f_{o}(o_{N}))$ is fed into the attention module.

  * •

MAGE-X-MLP: We consider the MLP layer as the alternative to the Action
Executor to capture the correlation between agents and goals. The MLP layer
takes the concatenation of $(f_{o}(o_{1}),f_{o}(o_{2}),..f_{o}(o_{N}),P_{g})$
as input.

Figure 9. Ablation study on MAGE-X in Simple Spread with $50$ agents.

Fig. 9 and Table 4 summarize the performance of MAGE-X and its variants on
training and evaluation, respectively. MAGE-X excels in data efficiency and
final performance with a 100% success rate. _MAGE-X-MLP_ degrades most,
implying that the MLP layer is incapable of distinguishing the correlation of
agents and target goals from the given information. _MAGE-X w. RG_ lacks an
appropriate Goal scheduler in the high-level Goal Commander, which may lead to
agents being assigned distant goals. Therefore, MAGE-X w. RG reveals a worse
performance with an 83% success rate. _MAGE-X-Atten_ is slightly inferior to
MAGE-X with a 7% lower success rate. We hypothesize that _MAGE-X-Atten_
provides each agent with the attention weights of all the neighbors, where
needless teammates may influence agents. On the contrary, MAGE-X agent only
concentrates on crucial neighbors in the subgraph with useful information.

| MAGE-X w. RG | MAGE-X-Atten | MAGE-X-MLP | MAGE-X
---|---|---|---|---
Suc. Rate | 0.83(0.01) | 0.93(0.01) | 0.50(0.08) |  1.00(0.01)
Table 4.  Evaluation performance of Success Rate between MAGE-X and its
variants in Simple Spread.

##  6\. Conclusion and Future Work

In this paper, we propose a goal-conditioned MARL framework, _Multi-Agent
Commander-Executor_ (MAGE-X), to improve data efficiency and cooperation in
multi-agent navigation tasks, especially in scenarios with large space spaces
(e.g., a massive number of agents or complex 3$D$ simulator). MAGE-X consists
of a high-level Goal Commander and a low-level Action Executor, where the
Commander allocates target goals to agents via the probability distribution of
goals and the Executor leverages GNN and a Goal Encoder to capture team
representation with strong goal guidance. Thorough experiments demonstrate
that MAGE-X achieves higher sample efficiency and better performances than all
the state-of-the-art MARL baselines in multi-agent particle environments (MPE)
with large-scale agents and a more complicated quadrotor navigation task.
Currently, MAGE-X mainly focuses on multi-agent navigation tasks, and we will
try to apply MAGE-X to other multi-agent tasks beyond navigation in the
future.

## ACKNOWLEDGMENT

This research was supported by National Natural Science Foundation of China
(No.62203257, U19B2019, M-0248), Tsinghua University Initiative Scientific
Research Program, Tsinghua-Meituan Joint Institute for Digital Life, Beijing
National Research Center for Information Science, Technology (BNRist) and
Beijing Innovation Center for Future Chips.

We would suggest to visit https://sites.google.com/view/mage-x23 for more
information.

##  A. MAGE-X Details

###  A.1. Hungarian algorithm

The Hungarian algorithm Jonker and Volgenant (1986) is a combinatorial
optimization algorithm which solves the assignment problem. To be specific,
the assignment problem can be formulated with a bipartite graph. Assume that
we have a complete bipartite graph $G=(S,T;E)$ with $n$ worker vertices $S$
and $n$ job vertices $T$, and each edge has a non-negative cost $c(i,j)$. We
want to find a perfect matching with a minimum total cost. And the graph and
cost can also be translated as a matrix, where the element in the $i_{th}$ row
and $j_{th}$ column represents the cost of assigning the $j_{th}$ job to the
$i_{th}$ worker. However, the Hungarian algorithm is not the exact optimal
solution and yields an approximately optimal solution with unaffordable time
complexity $O(n^{3})$. Therefore, we propose a learning-based module, the Goal
Commander, to figure out a (nearly)-optimal solution with less inference
computation. And we implement the Hungarian algorithm as an expert to judge
the performance of the Goal Commander by calculating the reward formulated as:

$R_{c}=1-\frac{C_{c}}{C_{h}}.$

$R_{c}$ represents the distance cost of our assignment strategy, $C_{c}$,
against the distance cost of the Hungarian algorithm, $C_{h}$.

###  A.2. Observation Space and Action Space

For the Goal Commander, the observation space is the positions of all agents,
$(x,y)\in\mathbb{R}^{2},x,y\in[0,mapsize]$, and the positions of target goals,
$(g_{x},g_{y})\in\mathbb{R}^{2},x,y\in[0,mapsize]$. The action space of the
Goal Commander is the index of assigned goals for agents, $A_{com}=\\{i,i\in
N\\}$, where $i$ is the index of assigned goals, and $N$ represents the number
of goals. For each Action Executor $i$, the observation space contains agent
$i$’s position $(x_{i},y_{i})\in\mathbb{R}^{2},x_{i},y_{i}\in[0,mapsize]$, and
its target goal was given by the commander
$(g_{i}^{x},g_{i}^{y})\in\mathbb{R}^{2},g_{i}^{x},g_{i}^{y}\in[0,mapsize]$,
other agents’ positions
$(x_{-i},y_{-i})\in\mathbb{R}^{2},x_{-i},y_{-i}\in[0,mapsize]$, and one hot
label $L_{i}$ to represent whether it has reached the goal. The action space
of each Action Executor is the primitive action for each agent,
$A_{exe}^{i}=\\{a^{i}|a^{i}\in action\\}$. We denote that $action$ is the
available primitive action, which is a discrete variable sampled from the
categorical distribution.

###  A.3. Action Generator

The Action Generator takes in the team features with strong goal guidance from
the State Extractor then infers a primitive action for each agent to complete
the navigation tasks.

common hyperparameters | value
---|---
gradient clip norm | 10.0
GAE lambda | 0.95
gamma | 0.99
value loss | huber loss
huber delta | 10.0
mini batch size | batch size / mini-batch
optimizer | Adam
optimizer epsilon | 1e-5
weight decay | 0
network initialization | Orthogonal
use reward normalization | True
use feature normalization | True
learning rate | 2.5e-5
parallel environment threads | 10
number of local steps | 15
Table 1. MAPPO Hyperparameters architecture hyperparameters | value
---|---
$f_{sche}$ | $[4\times N,1\times N,1]$
$f_{o}$ | $[2\times N,32,1]$
$f_{g}$ | $[32\times N,32\times N,1]$
$f_{goal}$ | $[2\times(N+1),32,1]$
$f_{state}$ | $[32\times 2,32,1]$
feature size | 32
$l_{g}$ | 2
Table 2. Architecture Hyperparameters

##  B. Experiments

###  B.1. Training Details

We train our policy with MAPPO Yu et al. (2021), which is a multi-agent
extension of PPO Schulman et al. (2017). The training hyperparameters can be
found in Table 1 and the detailed architecture of MAGE-X is shown in Table 2.

In MAGE-X, we implement feature normalization and reward normalization to
achieve more robustness. We use Adam optimizer with optimizer epsilon as
$1e^{-5}$, and the learning rate is $2.5e^{-5}$. Value loss is Huber loss with
Huber delta $10.0$. The gradient clip norm we choose is $10.0$ and GAE lambda
is $0.95$. Discounted factor $gamma$ of the expected reward is $0.99$, and no
weight decay has been used. Parallel threads of the environment are $10$ and
the number of local steps is $15$. For neural network architecture, it is
orthogonal initialized with feature size $32$.

###  B.2. Baseline

In MAGE-X, we compare against one planning-based competitor, Multi-Agent $A*$,
and four MARL baseline algorithms, MAPPO, MAT, DICG, and Maser.

####  B.2.1. Multi-Agent A* (MA A*) Faridi et al. (2018)

MA A* is the Multi-Agent version of $A*$ algorithm. It first transforms the
continuous space into grid space and calculates the cost of each grid. The
cost is the distance between the grid and the agent, and the distance between
the grid and the goal. Besides, it also considers the collision among agents.
The target is to find a path from the agent to the target goal with the
minimal total cost.

####  B.2.2. MAPPO Yu et al. (2021)

MAPPO, the Multi-Agent version of PPO, achieves surprisingly strong
performance in StarCraftII, Google Research Football, MPE, and Hanabi. Compare
with common value-based Multi-Agent algorithm Rashid et al. (2018); Son et al.
(2019); Lowe et al. (2017b), Mappo is the first and the most direct, approach
for applying PPO in MARL. It equips all agents with one shared set of
parameters and updates the shared policy through agents’ aggregated
trajectories, and achieves competitive or superior results in final rewards
without losing sample efficiency.

####  B.2.3. MAT Wen et al. (2022)

MAT is an encoder-decoder architecture which leverages the multi-agent
advantage decomposition theorem to transform the joint policy search problem
into a sequential decision-making process. Unlike prior arts such as Decision
Transformer fit only pre-collected offline data, MAT is trained by online
trials and errors from the environment in an on-policy fashion.

####  B.2.4. DICG Li et al. (2020)

DICG is a graph-based method consisting of a module that infers the dynamic
coordination graph structure, and a GNN module that implicitly reasons about
the joint actions or value based on the former module’s output. It allows the
agent to learn the trade oﬀ between full centralization and decentralization
via standard actor-critic methods to significantly improve coordination for
domains with large numbers of agents.

####  B.2.5. Maser Jeon et al. (2022)

Maser is a goal-conditioned MARL method that automatically generates subgoals
for multiple agents from the experience replay buffer by considering both the
individual Q-value and the total Q-value. It adopts the individual intrinsic
reward for each agent to reach the assigned subgoals and maximize the joint
action value.

###  B.3. Additional Results

####  B.3.1. Compared with MA A*

Table 1 shows the performance of MAGE-X and the planning-based baseline, MA
A*, in Simple Spread. It expresses that MA A* has a comparable performance
with MAGE-X in $N=$ 5, 20 agents, but shows a worse result in $N=$ 50\. It
implies that MA A* has the potential to handle the multi-agent multi-target
problem, but it may be difficult to find optimal paths when the number of
agents increases.

Agents | 5 | 20 | 50
---|---|---|---
MA A* |  1.00(0.01) | 0.93(0.03) | 0.77(0.03)
MAGE-X |  1.00(0.01) |  1.00(0.01) |  1.00(0.01)
Table 3.  Evaluation performance of the success rate between MAGE-X and MA A∗
in Simple Spread.

## References

  * (1)
  * Bresson et al. (2017) Guillaume Bresson, Zayed Alsayed, Li Yu, and Sébastien Glaser. 2017.  Simultaneous localization and mapping: A survey of current trends in autonomous driving.  _IEEE Transactions on Intelligent Vehicles_ 2, 3 (2017), 194–220.
  * Calisi et al. (2005) Daniele Calisi, Alessandro Farinelli, Luca Iocchi, and Daniele Nardi. 2005.  Autonomous navigation and exploration in a rescue environment. In _IEEE International Safety, Security and Rescue Rototics, Workshop, 2005._ IEEE, 54–59.
  * Chane-Sane et al. (2021) Elliot Chane-Sane, Cordelia Schmid, and Ivan Laptev. 2021\.  Goal-conditioned reinforcement learning with imagined subgoals. In _International Conference on Machine Learning_. PMLR, 1430–1440.
  * Chen et al. (2021) Rui Chen, Peide Huang, and Laixi Shi. 2021.  Latent Goal Allocation for Multi-Agent Goal-Conditioned Self-Supervised Imitation Learning. In _Advances in Neural Information Processing Systems_.
  * Dayan and Hinton (1992) Peter Dayan and Geoffrey E Hinton. 1992.  Feudal reinforcement learning.  _Advances in neural information processing systems_ 5 (1992).
  * Faridi et al. (2018) Abdul Qadir Faridi, Sanjeev Sharma, Anupam Shukla, Ritu Tiwari, and Joydip Dhar. 2018\.  Multi-robot multi-target dynamic path planning using artificial bee colony and evolutionary programming in unknown environment.  _Intelligent Service Robotics_ 11 (2018), 171–186.
  * Gao et al. (2018) Kaivuan Gao, Jing Xin, Han Cheng, Ding Liu, and Jiang Li. 2018.  Multi-mobile robot autonomous navigation system for intelligent logistics. In _2018 Chinese Automation Congress (CAC)_. IEEE, 2603–2609.
  * Grigorescu et al. (2020) Sorin Grigorescu, Bogdan Trasnea, Tiberiu Cocias, and Gigel Macesanu. 2020.  A survey of deep learning techniques for autonomous driving.  _Journal of Field Robotics_ 37, 3 (2020), 362–386.
  * Hoang et al. (2021) Christopher Hoang, Sungryull Sohn, Jongwook Choi, Wilka Carvalho, and Honglak Lee. 2021\.  Successor Feature Landmarks for Long-Horizon Goal-Conditioned Reinforcement Learning.  _Advances in Neural Information Processing Systems_ 34 (2021), 26963–26975.
  * Jang et al. (2016) Eric Jang, Shixiang Gu, and Ben Poole. 2016.  Categorical reparameterization with gumbel-softmax.  _arXiv preprint arXiv:1611.01144_ (2016).
  * Jeon et al. (2022) Jeewon Jeon, Woojun Kim, Whiyoung Jung, and Youngchul Sung. 2022\.  MASER: Multi-Agent Reinforcement Learning with Subgoals Generated from Experience Replay Buffer. In _International Conference on Machine Learning_. PMLR, 10041–10052.
  * Jiang et al. (2018) Jiechuan Jiang, Chen Dun, Tiejun Huang, and Zongqing Lu. 2018\.  Graph convolutional reinforcement learning.  _arXiv preprint arXiv:1810.09202_ (2018).
  * Jin et al. (2019) Yue Jin, Yaodong Zhang, Jian Yuan, and Xudong Zhang. 2019\.  Efficient multi-agent cooperative navigation in unknown environments with interlaced deep reinforcement learning. In _ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2897–2901.
  * Jonker and Volgenant (1986) Roy Jonker and Ton Volgenant. 1986.  Improving the Hungarian assignment algorithm.  _Operations Research Letters_ 5, 4 (1986), 171–175.
  * Kim et al. (2021) Junsu Kim, Younggyo Seo, and Jinwoo Shin. 2021.  Landmark-guided subgoal generation in hierarchical reinforcement learning.  _Advances in Neural Information Processing Systems_ 34 (2021), 28336–28349.
  * Kipf and Welling (2016) Thomas N Kipf and Max Welling. 2016.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ (2016).
  * Kleiner et al. (2006) Alexander Kleiner, Johann Prediger, and Bernhard Nebel. 2006\.  RFID technology-based exploration and SLAM for search and rescue. In _2006 IEEE/RSJ International Conference on Intelligent Robots and Systems_. IEEE, 4054–4059.
  * Koh et al. (2020) Songsang Koh, Bo Zhou, Hui Fang, Po Yang, Zaili Yang, Qiang Yang, Lin Guan, and Zhigang Ji. 2020.  Real-time deep reinforcement learning based vehicle navigation.  _Applied Soft Computing_ 96 (2020), 106694.
  * Kreidieh et al. (2019) Abdul Rahman Kreidieh, Glen Berseth, Brandon Trabucco, Samyak Parajuli, Sergey Levine, and Alexandre M Bayen. 2019.  Inter-level cooperation in hierarchical reinforcement learning.  _arXiv preprint arXiv:1912.02368_ (2019).
  * Kulkarni et al. (2016) Tejas D Kulkarni, Karthik Narasimhan, Ardavan Saeedi, and Josh Tenenbaum. 2016.  Hierarchical deep reinforcement learning: Integrating temporal abstraction and intrinsic motivation.  _Advances in neural information processing systems_ 29 (2016).
  * Levy et al. (2017) Andrew Levy, George Konidaris, Robert Platt, and Kate Saenko. 2017.  Learning multi-level hierarchies with hindsight.  _arXiv preprint arXiv:1712.00948_ (2017).
  * Li et al. (2020) Sheng Li, Jayesh K Gupta, Peter Morales, Ross Allen, and Mykel J Kochenderfer. 2020.  Deep implicit coordination graphs for multi-agent reinforcement learning.  _arXiv preprint arXiv:2006.11438_ (2020).
  * Liu and Hu (2009) Shaotang Liu and Lixin Hu. 2009.  Application of beidou navigation satellite system in logistics and transportation.  In _Logistics: The Emerging Frontiers of Transportation and Development in China_. 1789–1794.
  * Lowe et al. (2017a) Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAI Pieter Abbeel, and Igor Mordatch. 2017a.  Multi-agent actor-critic for mixed cooperative-competitive environments.  _Advances in neural information processing systems_ 30 (2017).
  * Lowe et al. (2017b) Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAI Pieter Abbeel, and Igor Mordatch. 2017b.  Multi-agent actor-critic for mixed cooperative-competitive environments.  _Advances in neural information processing systems_ 30 (2017).
  * Marchesini and Farinelli (2020) Enrico Marchesini and Alessandro Farinelli. 2020.  Discrete deep reinforcement learning for mapless navigation. In _2020 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 10688–10694.
  * Marchesini and Farinelli (2022) Enrico Marchesini and Alessandro Farinelli. 2022.  Enhancing deep reinforcement learning approaches for multi-robot navigation via single-robot evolutionary policy search. In _2022 International Conference on Robotics and Automation (ICRA)_. IEEE, 5525–5531.
  * Nachum et al. (2018) Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. 2018.  Data-efficient hierarchical reinforcement learning.  _Advances in neural information processing systems_ 31 (2018).
  * Nair and Finn (2019) Suraj Nair and Chelsea Finn. 2019.  Hierarchical foresight: Self-supervised learning of long-horizon tasks via visual subgoal generation.  _arXiv preprint arXiv:1909.05829_ (2019).
  * Niu et al. (2021) Yaru Niu, Rohan R Paleja, and Matthew C Gombolay. 2021.  Multi-Agent Graph-Attention Communication and Teaming.. In _AAMAS_. 964–973.
  * Panerati et al. (2021) Jacopo Panerati, Hehui Zheng, SiQi Zhou, James Xu, Amanda Prorok, and Angela P Schoellig. 2021\.  Learning to fly—a gym environment with pybullet physics for reinforcement learning of multi-agent quadcopter control. In _2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 7512–7519.
  * Pertsch et al. (2020) Karl Pertsch, Oleh Rybkin, Frederik Ebert, Shenghao Zhou, Dinesh Jayaraman, Chelsea Finn, and Sergey Levine. 2020.  Long-horizon visual planning with goal-conditioned hierarchical predictors.  _Advances in Neural Information Processing Systems_ 33 (2020), 17321–17333.
  * Rao et al. (2021) Zhenhuan Rao, Yuechen Wu, Zifei Yang, Wei Zhang, Shijian Lu, Weizhi Lu, and ZhengJun Zha. 2021.  Visual navigation with multiple goals based on deep reinforcement learning.  _IEEE Transactions on Neural Networks and Learning Systems_ 32, 12 (2021), 5445–5455.
  * Rashid et al. (2018) Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. 2018.  Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In _International conference on machine learning_. PMLR, 4295–4304.
  * Ruan et al. (2022) Jingqing Ruan, Yali Du, Xuantang Xiong, Dengpeng Xing, Xiyun Li, Linghui Meng, Haifeng Zhang, Jun Wang, and Bo Xu. 2022.  GCS: Graph-Based Coordination Strategy for Multi-Agent Reinforcement Learning.  _arXiv preprint arXiv:2201.06257_ (2022).
  * Ryu et al. (2020) Heechang Ryu, Hayong Shin, and Jinkyoo Park. 2020\.  Multi-agent actor-critic with hierarchical graph attention network. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 34. 7236–7243.
  * Scarselli et al. (2008) Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. 2008\.  The graph neural network model.  _IEEE transactions on neural networks_ 20, 1 (2008), 61–80.
  * Schulman et al. (2017) John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. 2017.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_ (2017).
  * Son et al. (2019) Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. 2019.  Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In _International conference on machine learning_. PMLR, 5887–5896.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _Advances in neural information processing systems_ 30 (2017).
  * Wen et al. (2022) Muning Wen, Jakub Grudzien Kuba, Runji Lin, Weinan Zhang, Ying Wen, Jun Wang, and Yaodong Yang. 2022.  Multi-Agent Reinforcement Learning is a Sequence Modeling Problem.  _arXiv preprint arXiv:2205.14953_ (2022).
  * Xia et al. (2021) Lijun Xia, Chao Yu, and Zifan Wu. 2021.  Inference-based Hierarchical Reinforcement Learning for Cooperative Multi-agent Navigation. In _2021 IEEE 33rd International Conference on Tools with Artificial Intelligence (ICTAI)_. IEEE, 57–64.
  * Yang et al. (2022) Xinyi Yang, Chao Yu, Jiaxuan Gao, Yu Wang, and Huazhong Yang. 2022.  SAVE: Spatial-Attention Visual Exploration. In _2022 IEEE International Conference on Image Processing (ICIP)_. IEEE, 1356–1360.
  * Yu et al. (2021) Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. 2021\.  The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games.  _arXiv preprint arXiv:2103.01955_ (2021).
  * Yu et al. (2022) Chao Yu, Xinyi Yang, Jiaxuan Gao, Huazhong Yang, Yu Wang, and Yi Wu. 2022\.  Learning efficient multi-agent cooperative visual exploration. In _European Conference on Computer Vision_. Springer, 497–515.
  * Zhang et al. (2020) Tianren Zhang, Shangqi Guo, Tian Tan, Xiaolin Hu, and Feng Chen. 2020.  Generating adjacency-constrained subgoals in hierarchical reinforcement learning.  _Advances in Neural Information Processing Systems_ 33 (2020), 21579–21590.
  * Zhu et al. (2017) Yuke Zhu, Roozbeh Mottaghi, Eric Kolve, Joseph J Lim, Abhinav Gupta, Li Fei-Fei, and Ali Farhadi. 2017.  Target-driven visual navigation in indoor scenes using deep reinforcement learning. In _2017 IEEE international conference on robotics and automation (ICRA)_. IEEE, 3357–3364.


1. 1.

Consider continuity of the objective first.

Assumption 3 (iv) implies $h(y,x,b)$ is continuous in $b$, and assumption 1
(iv) includes that $f^{*}(\cdot)$ is essentially smooth. It follows that

$\hat{M}_{n}(b,\lambda)=\frac{1}{n}\sum_{i=1}^{n}\frac{\lambda^{\intercal}J(D_{i})h(D_{i}Y_{i},X_{i},b)}{1-\hat{p}_{D,n}}-\frac{D_{i}}{\hat{p}_{D,n}}f^{*}(\lambda^{\intercal}h(D_{i}Y_{i},X_{i},b))$

is continuous at $(b,\lambda)$ if and only if
$\lambda^{\intercal}h(D_{i}Y_{i},X_{i},b)\in(\ell^{*},u^{*})$ for every $i$,
which holds if and only if $\hat{M}_{n}(b,\lambda)<\infty$. Notice that
$\text{Gr}(\lambda)^{\eta/2}\equiv\left\\{(b,\lambda)\;;\;\inf_{(b^{\prime},\lambda^{\prime})\in\text{Gr}(\lambda)}\lVert(b,\lambda)-(b^{\prime},\lambda^{\prime})\rVert\leq\eta/2\right\\}$
contains $\text{Gr}(\Lambda)$ because
$(b^{\prime},\lambda^{\prime})=(b,\lambda(b))$ is an element of
$\text{Gr}(\lambda)=\left\\{(b,\lambda(b))\;;\;b\in B\right\\}$. Assumption 3
(v) implies $\sup_{(b,\lambda)\in\text{Gr}(\lambda)^{\eta/2}}\lvert
M(b,\lambda)\rvert$ is finite, and lemma D.8 shows that $\hat{M}_{n}$ is
uniformly consistent for $M$ on $\text{Gr}(\lambda)^{\eta/2}$, thus the
continuous mapping theorem implies
$\sup_{(b,\lambda)\in\text{Gr}(\lambda)^{\eta/2}}\lvert\hat{M}_{n}(b,\lambda)\rvert\overset{p}{\rightarrow}\sup_{(b,\lambda)\in\text{Gr}(\lambda)^{\eta/2}}\lvert
M(b,\lambda)\rvert$ and therefore
$\sup_{(b,\lambda)\in\text{Gr}(\lambda)^{\eta/2}}\lvert\hat{M}_{n}(b,\lambda)\rvert$
is finite with probability approaching one. When it is,

$\sup_{(b,\lambda)\in\text{Gr}(\Lambda)}\hat{M}_{n}(b,\lambda)\leq\sup_{(b,\lambda)\in\text{Gr}(\lambda)^{\eta/2}}\lvert\hat{M}_{n}(b,\lambda)\rvert<\infty.$

and $\hat{M}_{n}$ is continuous on $\text{Gr}(\Lambda)$.

  2. 2.

Now consider continuity of $\Lambda:B\rightrightarrows\lambda(B)^{\eta/2}$.

Upper hemicontinuity will follow by application of the Closed Graph Theorem,
Aliprantis & Border (2006) theorem 17.11. $B$ is compact by assumption 2 and
D.7 shows that $\lambda(\cdot)$ is continuous, therefore
$\lambda(B)=\\{\lambda(b)\;;\;b\in B\\}$ is compact, and hence
$\lambda(B)^{\eta/2}$ is compact. Suppose
$\\{(b_{n},\lambda_{n})\\}_{n=1}^{\infty}\subseteq\text{Gr}(\Lambda)$
converges to $(b,\lambda)$. Then $b\in B$ because $B$ is closed. Since
$\lambda(\cdot)$ is continuous,
$\lVert\lambda(b_{n})-\lambda(b)\rVert\rightarrow 0$, and therefore

$\lVert\lambda-\lambda(b)\rVert\leq\underbrace{\lVert\lambda-\lambda_{n}\rVert}_{\rightarrow
0}+\underbrace{\lVert\lambda_{n}-\lambda(b_{n})\rVert}_{\leq\eta/2}+\underbrace{\lVert\lambda(b_{n})-\lambda(b)\rVert}_{\rightarrow
0}$

shows that $\lVert\lambda-\lambda(b)\rVert\leq\eta/2$, i.e.
$\lambda\in\Lambda(b)$. Thus $(b,\lambda)\in\text{Gr}(\Lambda)$, so
$\text{Gr}(\Lambda)$ is closed. Aliprantis & Border (2006) theorem 17.11 then
implies $\Lambda:B\rightrightarrows\lambda(B)^{\eta/2}$ is upper
hemicontinuous.

Regarding lower semicontinuity, note that $B\subseteq\mathbb{R}^{d_{b}}$ and
$\lambda(B)^{\eta/2}\subseteq\mathbb{R}^{d_{g}+K}$ are both metric spaces and
hence first countable. Thus Aliprantis & Border (2006) theorem 17.21 implies
$\Lambda$ is lower hemicontinuous at $b\in B$ if and only if for any sequence
$\\{b_{n}\\}\subseteq B$ with $b_{n}\rightarrow b$ and any
$\lambda\in\Lambda(b)$, there exists a subsequence
$\\{b_{n_{k}}\\}_{k=1}^{\infty}$ and elements
$\lambda_{k}\in\Lambda(b_{n_{k}})$ for each $k$ such that
$\lambda_{k}\rightarrow\lambda$. For the subsequence we can take the sequence
itself. Notice that $\lambda_{n}\equiv\lambda(b_{n})+\lambda-\lambda(b)$
satisfies

$\lVert\lambda_{n}-\lambda(b_{n})\rVert=\lVert\lambda(b_{n})+\lambda-\lambda(b)-\lambda(b_{n})\rVert=\lVert\lambda-\lambda(b)\rVert\leq\eta/2$

and therefore $\lambda_{n}\in\lambda(b_{n})$. Continuity of $\lambda(\cdot)$
and $b_{n}\rightarrow b$ implies $\lambda_{n}\rightarrow\lambda$, and thus
$\Lambda$ is lower semicontinuous.

To summarize,

$\displaystyle\sup_{b\in
B}\left\lVert\hat{\lambda}_{n}(b)-\lambda(b)\right\rVert<\eta/2$ and
$\displaystyle\sup_{(b,\lambda)\in\text{Gr}(\Lambda)}\hat{M}_{n}(b,\lambda)<\infty$

hold with probability approaching one. When both hold,
$\hat{\nu}_{n}(b)=\max_{\lambda\in\Lambda(b)}\hat{M}_{n}(b,\lambda)$ is
continuous by the berge Maximum theorem, implying
$\sqrt{n}(\hat{\nu}_{n}-\nu)\in\mathcal{C}(B)$. Thus

$P(\sqrt{n}(\hat{\nu}_{n}-\nu)\in\mathcal{C}(B))\geq P\left(\sup_{b\in
B}\left\lVert\hat{\lambda}_{n}(b)-\lambda(b)\right\rVert<\eta/2\text{ and
}\sup_{(b,\lambda)\in\text{Gr}(\Lambda)}\hat{M}_{n}(b,\lambda)<\infty\right)\rightarrow
1.$

As argued above, the Portmanteau theorem implies
$P(\mathbb{G}_{\nu}\in\mathcal{C}(B))=1$. ∎

######  Lemma D.15 ($\sqrt{n}$-consistency and convergence in distribution).

Suppose assumptions 1 and 2 hold, and 3 (i), (iii), (iv), (v) hold, but do not
assume $\textbf{m}(\nu)=\operatorname*{arg\,min}_{b\in
B\cap\textbf{B}_{0}}\nu(b)$ is unique. Then

$\displaystyle\sqrt{n}(\hat{\delta}_{n}^{BP}-\delta^{BP})\overset{d}{\rightarrow}\inf_{b\in\textbf{m}(\nu)}\mathbb{G}_{\nu}(b)$

where $\mathbb{G}_{\nu}$ is the weak limit of $\sqrt{n}(\hat{\nu}_{n}-\nu)$ in
$\ell^{\infty}(B)$.

###### Proof.

Let $\iota:\ell^{\infty}(B)\rightarrow\mathbb{R}$ be given by
$\iota(f)=\inf_{b\in B\cap\textbf{B}_{0}}f(b)$. Then

$\sqrt{n}(\hat{\delta}_{n}^{BP}-\delta^{BP})=\sqrt{n}(\iota(\hat{\nu}_{n})-\iota(\nu))$

suggests applying the Delta method, found in Fang & Santos (2019) as theorem
2.1. There are two assumptions to verify:

  1. 1.

On the map $\iota$:

    1. (i)

$\iota$ maps $(\ell^{\infty}(B),\lVert\cdot\rVert_{B})$ to
$(\mathbb{R},\lvert\cdot\rvert)$, which are both Banach spaces.

    2. (ii)

Lemma D.3 implies that $\iota$ is Hadamard directionally differentiable at any
$f\in\mathcal{C}(B)$ tangentially to $\mathcal{C}(B)$, and lemma D.7 shows
that $\nu\in\mathcal{C}(B)$.

  2. 2.

On the estimator $\hat{\nu}_{n}$:

    1. (i)

As noted in lemma D.14,
$\sqrt{n}(\hat{\nu}_{n}-\nu)\overset{L}{\rightarrow}\mathbb{G}_{\nu}$ in
$\ell^{\infty}(B)$.

    2. (ii)

$\mathbb{G}_{\nu}$ is tight. Lemma D.14 shows that
$P(\mathbb{G}_{\nu}\in\mathcal{C}(B))=1$, i.e. the support of
$\mathbb{G}_{\nu}$ is included in $\mathcal{C}(B)$.

Fang & Santos (2019) theorem 2.1 then implies

$\displaystyle\sqrt{n}(\iota(\hat{\nu}_{n})-\iota(\nu))=\iota_{\nu}^{\prime}(\sqrt{n}(\hat{\nu}_{n}-\nu))+o_{p}(1)$

Lemma D.3 shows the directional derivative of $\iota$ at $\nu$ is given by

$\displaystyle\iota_{\nu}^{\prime}:\mathcal{C}(B)\rightarrow\mathbb{R},$
$\displaystyle\iota_{\nu}^{\prime}(h)=\inf_{b\in\textbf{m}(\nu)}h(b)$

and therefore

$\displaystyle\sqrt{n}(\hat{\delta}_{n}^{BP}-\delta^{BP})=\sqrt{n}(\iota(\hat{\nu}_{n})-\iota(\nu))=\inf_{b\in\textbf{m}(\nu)}\left\\{\sqrt{n}(\hat{\nu}_{n}(b)-\nu(b))\right\\}+o_{p}(1)\overset{L}{\rightarrow}\inf_{b\in\textbf{m}(\nu)}\mathbb{G}_{\nu}(b).$

∎

See 4.2

###### Proof.

Since $\textbf{m}(\nu)$ is a singleton, say $\textbf{m}(\nu)=\\{b_{\nu}\\}$,
lemmas D.13 and D.15 imply
$\sqrt{n}(\hat{\delta}_{n}^{BP}-\delta^{BP})\overset{d}{\rightarrow}N(0,\sigma^{2})$
where

$\displaystyle\sigma^{2}$
$\displaystyle=E\left[\left((\Phi(b_{\nu})^{-1})^{(1)}\phi(D,DY,X,b_{\nu},\theta_{0}(b_{\nu}))\right)^{2}\right]$
$\displaystyle=e_{1}^{\intercal}\Phi(b_{\nu})^{-1}E\left[\phi(D,DY,X,b_{\nu},\theta_{0}(b_{0}))\phi(D,DY,X,b_{\nu},\theta_{0}(b_{0}))^{\intercal}\right](\Phi(b_{\nu})^{-1})^{\intercal}e_{1}$

and $e_{1}=(1,0,\ldots,0)\in\mathbb{R}^{d_{g}+K+2}$. Now notice that
$\hat{\sigma}_{n}^{2}$ is the sample analogue:

$\displaystyle\hat{\sigma}_{n}^{2}$
$\displaystyle\equiv\frac{1}{n}\sum_{i=1}^{n}\left((\hat{\Phi}_{n}(\hat{b}_{n})^{-1})^{(1)}\phi(D,DY,X,\hat{b}_{n},\hat{\theta}_{n}(\hat{b}_{n}))\right)^{2}$
$\displaystyle=e_{1}^{\intercal}\hat{\Phi}_{n}(\hat{b}_{n})^{-1}\left[\frac{1}{n}\sum_{i=1}^{n}\phi(D_{i},D_{i}Y_{i},X_{i},\hat{b}_{n},\hat{\theta}_{n}(\hat{b}_{n}))\phi(D_{i},D_{i}Y_{i},X_{i},\hat{b}_{n},\hat{\theta}_{n}(\hat{b}_{n}))^{\intercal}\right](\hat{\Phi}_{n}(\hat{b}_{n})^{-1})^{\intercal}e_{1}$

It suffices to show
$\hat{\Phi}_{n}(\hat{b}_{n})\overset{p}{\rightarrow}\Phi(b_{\nu})$ and

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\phi(D_{i},D_{i}Y_{i},X_{i},\hat{b}_{n},\hat{\theta}_{n}(\hat{b}_{n}))\phi(D_{i},D_{i}Y_{i},X_{i},\hat{b}_{n},\hat{\theta}_{n}(\hat{b}_{n}))^{\intercal}$
$\displaystyle\hskip
85.35826pt\overset{p}{\rightarrow}E\left[\phi(D,DY,X,b_{\nu},\theta_{0}(b_{0}))\phi(D,DY,X,b_{\nu},\theta_{0}(b_{0}))^{\intercal}\right].$
(37)

With these, the continuous mapping theorem will imply
$\hat{\sigma}_{n}\overset{p}{\rightarrow}\sigma$, hence
$(\sqrt{n}(\hat{\delta}_{n}^{BP}-\delta^{BP}),\hat{\sigma})\overset{d}{\rightarrow}(N(0,\sigma^{2}),\sigma)$,
and another application of the continuous mapping theorem gives the conclusion
$\frac{\sqrt{n}(\hat{\delta}_{n}^{BP}-\delta^{BP})}{\hat{\sigma}_{n}}\overset{d}{\rightarrow}N(0,1)$.

To show $\hat{\Phi}_{n}(\hat{b}_{n})\overset{p}{\rightarrow}\Phi(b_{\nu})$ and
(37), first notice that

$\displaystyle\left\\{\phi(D,DY,X,b,\theta)\phi(D,DY,X,b,\theta)^{\intercal}\;;\;(b,\theta)\in\text{Gr}(\theta_{0})^{\eta}\right\\}$
$\displaystyle\left\\{\nabla_{\theta}\phi(D,DY,X,b,\theta)\;;\;(b,\theta)\in\text{Gr}(\theta_{0})^{\eta}\right\\}$

are special cases of van der Vaart (2007) example 19.8 and hence Glivenko-
Cantelli. Specifically, $\text{Gr}(\theta_{0})^{\eta}$ is closed and bounded
and hence compact.
$(b,\theta)\mapsto\phi(D,DY,X,b,\theta)\phi(D,DY,X,b,\theta)^{\intercal}$ and
$(b,\theta)\mapsto\nabla_{\theta}\phi(D,DY,X,b,\theta)$ are continuous by
inspection of (19), (21), and (22). Finally,
$E\left[\sup_{(b,\theta)\in\text{Gr}(\theta_{0})^{\eta}}\rVert\nabla_{\theta}\phi(D,DY,X,b,\theta)\rVert\right]<\infty$
and

$E\left[\sup_{(b,\theta)\in\text{Gr}(\theta_{0})^{\eta}}\rVert\phi(D,DY,X,b,\theta)\phi(D,DY,X,b,\theta)^{\intercal}\rVert_{o}\right]=E\left[\sup_{(b,\theta)\in\text{Gr}(\theta_{0})^{\eta}}\rVert\phi(D,DY,X,b,\theta)\rVert^{2}\right]<\infty$

are implied by assumption 3 (v).

Next, observe that
$(\hat{b}_{n},\hat{\theta}_{n}(\hat{b}_{n}))\overset{p}{\rightarrow}(b_{\nu},\theta_{0}(b_{\nu}))$.
First, $\hat{b}_{n}\overset{p}{\rightarrow}b_{\nu}$ follows from a standard
extremum estimator argument. The function $\nu:B\rightarrow\mathbb{R}$ is
continuous, uniquely minimized over the compact $B\cap\textbf{B}_{0}$ at
$b_{\nu}$, and $\sup_{b\in
B}\lvert\hat{\nu}_{n}(b)-\nu(b)\rvert\overset{p}{\rightarrow}0$ by lemma D.9.
Thus Newey & McFadden (1994) theorem 2.1 implies
$\hat{b}_{n}=\operatorname*{arg\,min}_{b\in
B\cap\textbf{B}_{0}}\hat{\nu}_{n}(b)$ are consistent for $b_{\nu}$. Use the
triangle inequality, $\hat{b}_{n}\overset{p}{\rightarrow}b_{\nu}$, continuity
of $\theta_{0}(b)=(\nu(b),\lambda(b),p_{D})$ (lemma D.7), and $\sup_{b\in
B}\lVert\hat{\theta}_{n}(b)-\theta_{0}(b)\rVert=o_{p}(1)$ (lemma D.9) to see
that

$\displaystyle\lVert\hat{\theta}_{n}(\hat{b}_{n})-\theta_{0}(b_{\nu})\rVert$
$\displaystyle\leq\underbrace{\sup_{b\in
B}\lVert\hat{\theta}_{n}(b)-\theta_{0}(b)\rVert}_{=o_{p}(1)}+\underbrace{\lVert\theta_{0}(\hat{b}_{n})-\theta_{0}(b_{\nu})\rVert}_{=o_{p}(1)\text{
by CMT}}=o_{p}(1)$

Note that $(b,\theta)\mapsto E[\nabla_{\theta}\phi(D,DY,X,b,\theta)]$ is
continuous on $\text{Gr}(\theta_{0})^{\eta}$ by the dominated convergence
theorem and continuity of
$(b,\theta)\mapsto\nabla_{\theta}\phi(D,DY,X,b,\theta)$ visible in equations
(21) and (22).
$(\hat{b}_{n},\hat{\theta}_{n}(\hat{b}_{n}))\overset{p}{\rightarrow}(b_{\nu},\theta_{0}(b_{\nu}))$,
so
$(\hat{b}_{n},\hat{\theta}_{n}(\hat{b}_{n}))\in\text{Gr}(\theta_{0})^{\eta}$
holds with probability approaching one and when it does,

$\displaystyle\lVert\hat{\Phi}_{n}(\hat{b}_{n})-\Phi(b_{\nu})\rVert$
$\displaystyle=\left\lVert\frac{1}{n}\sum_{i=1}^{n}\nabla_{\theta}\phi(D_{i},D_{i}Y_{i},X_{i},\hat{b}_{n},\hat{\theta}_{n}(\hat{b}_{n}))-E\left[\nabla_{\theta}\phi(D,DY,X,b_{\nu},\theta_{0}(b_{\nu}))\right]\right\rVert$
$\displaystyle\leq\left\lVert\frac{1}{n}\sum_{i=1}^{n}\nabla_{\theta}\phi(D_{i},D_{i}Y_{i},X_{i},\hat{b}_{n},\hat{\theta}_{n}(\hat{b}_{n}))-E\left[\nabla_{\theta}\phi(D,DY,X,\hat{b}_{n},\hat{\theta}_{n}(\hat{b}))\right]\right\rVert$
$\displaystyle\hskip 28.45274pt+\left\lVert
E\left[\nabla_{\theta}\phi(D,DY,X,\hat{b}_{n},\hat{\theta}_{n}(\hat{b}))\right]-E\left[\nabla_{\theta}\phi(D,DY,X,b_{\nu},\theta_{0}(b_{\nu}))\right]\right\rVert$
$\displaystyle\leq\underbrace{\sup_{(b,\theta)\in\text{Gr}(\theta_{0})^{\eta}}\left\lVert\frac{1}{n}\sum_{i=1}^{n}\nabla_{\theta}\phi(D_{i},D_{i}Y_{i},X_{i},b,\theta)-E\left[\nabla_{\theta}\phi(D,DY,X,b,\theta)\right]\right\rVert}_{=o_{p}(1)\text{
by Glivenko-Cantelli}}$ $\displaystyle\hskip
28.45274pt+\underbrace{\left\lVert
E\left[\nabla_{\theta}\phi(D,DY,X,\hat{b}_{n},\hat{\theta}_{n}(\hat{b}))\right]-E\left[\nabla_{\theta}\phi(D,DY,X,b_{\nu},\theta_{0}(b_{\nu}))\right]\right\rVert}_{=o_{p}(1)\text{
by CMT}}$ $\displaystyle=o_{p}(1).$

Essentially the same argument implies (37) holds, which completes the proof. ∎

##  Appendix E Appendix: examples

###  E.1 Expectation

This simple example is useful primarily to illustrate the ideas in a concrete
setting.

Suppose the parameter of interest is $\beta=E[Y]\in\mathbb{R}$, and the sample
is $\\{D_{i},D_{i}Y_{i}\\}_{i=1}^{n}$. The conclusion to be supported is that
$\beta>\bar{b}$, motivating the null and alternative hypotheses

$\displaystyle H_{0}\;:\;\beta\leq\bar{b},$ $\displaystyle
H_{1}\;:\;\beta>\bar{b}$

The model is characterized by $g(y,b)=y-b$. For the dual problem, set
$h(y,b)=\begin{pmatrix}y-b&1\end{pmatrix}^{\intercal}$. The dual problem is

$\sup_{\lambda\in\mathbb{R}^{2}}\lambda^{\intercal}c(b)-E_{P_{1}}[f^{*}(\lambda^{\intercal}h(Y,b))]$
(38)

where
$c(b)=\begin{pmatrix}\frac{-p_{D}}{1-p_{D}}(E_{P_{1}}[Y]-b)&1\end{pmatrix}^{\intercal}$.

####  E.1.1 Dual solution when $d_{f}$ is Kullback-Leibler and $P_{1}$ is
$\mathcal{U}[0,1]$

Suppose that $P_{1}$, the distribution of $Y\mid D=1$, is $\mathcal{U}[0,1]$.
Let $\mu_{1}=E[Y\mid D=1]=1/2$. Note that, since the support of $P_{0}$ is
contained within $[0,1]$ as well, we have
$\beta=E[Y]\in\left[p_{D}\mu_{1},p_{D}\mu_{1}+(1-p_{D})\right]$. The endpoints
are only attained if $P_{0}$ concentrates degenerately at $0$ or $1$
respectively, distributions which violate $P_{0}\ll P_{1}$.

For tractability, let the measure of selection be Kullback-Leibler. For this
divergence we let $f(t)=t\log(t)-t+1$, which has convex conjugate
$f^{*}(r)=\exp(r)-1$. The dual problem has first order condition

$\displaystyle 0$
$\displaystyle=c(b)-E_{P_{1}}\left[(f^{*})^{\prime}(\lambda^{\intercal}h(Y,b))h(Y,b)\right]$
$\displaystyle=\begin{pmatrix}\frac{-p_{D}}{1-p_{D}}\left(\frac{1}{2}-b\right)\\\
1\end{pmatrix}-E\left[\exp\left(\lambda_{1}(Y-b)+\lambda_{2}\right)\begin{pmatrix}(Y-b)\\\
1\end{pmatrix}\right]$

From the second equation we have

$\lambda_{2}=-\log\left(E[\exp(\lambda_{1}(Y-b))]\right)$ (39)

Suppose $b=\frac{1}{2}$. Then the first equation requires

$0=E\left[\exp(\lambda_{1}(Y-b)+\lambda_{2})\left(Y-\frac{1}{2}\right)\right]$
(40)

Notice that if $\lambda_{1}=0$, then (39) implies $\lambda_{2}=0$, and (40)
holds.

Now suppose $b\neq 1/2$. Consider the dual objective, and notice that

$E_{P_{1}}[f^{*}(\lambda^{\intercal}h(Y,b))]=\int_{0}^{1}\exp(\lambda^{\intercal}h(y,b))-1dy$

Since $b\neq 1/2$, it follows that $\frac{-p_{D}}{1-p_{D}}(1/2-b)\neq 0$ and
so $\lambda_{1}\neq 0$. Thus the integral above can be solved with
$u$-substition, setting $u=\lambda_{1}(y-b)+\lambda_{2}$:

$\displaystyle E_{P_{1}}[f^{*}(\lambda^{\intercal}h(Y,b))]$
$\displaystyle=\int_{0}^{1}\exp(\lambda^{\intercal}h(y,b))-1dy=\frac{1}{\lambda_{1}}\int_{\lambda_{1}(-b)+\lambda_{2}}^{\lambda_{1}(1-b)+\lambda_{2}}\exp(u)du-1$
$\displaystyle=\frac{\exp(\lambda^{\intercal}\textbf{b}_{1})-\exp(\lambda^{\intercal}\textbf{b}_{0})}{\lambda^{\intercal}e_{1}}-1$

where $\textbf{b}_{1}=\begin{pmatrix}1-b&1\end{pmatrix}^{\intercal}$,
$\textbf{b}_{0}=\begin{pmatrix}-b&1\end{pmatrix}^{\intercal}$, and
$e_{1}=\begin{pmatrix}1&0\end{pmatrix}^{\intercal}$. Thus (38) becomes

$\displaystyle\sup_{\lambda\in\mathbb{R}^{2}}\lambda^{\intercal}\begin{pmatrix}\frac{-p_{D}}{1-p_{D}}(1/2-b)\\\
1\end{pmatrix}-\frac{\exp(\lambda^{\intercal}\textbf{b}_{1})-\exp(\lambda^{\intercal}\textbf{b}_{0})}{\lambda^{\intercal}e_{1}}+1$

from which we can compute the first order conditions

$\displaystyle 0=\begin{pmatrix}\frac{-p_{D}}{1-p_{D}}(1/2-b)\\\
1\end{pmatrix}-\frac{\exp(\lambda^{\intercal}\textbf{b}_{1})\textbf{b}_{1}-\exp(\lambda^{\intercal}\textbf{b}_{0})\textbf{b}_{0}}{\lambda^{\intercal}e_{1}}+\frac{\exp(\lambda^{\intercal}\textbf{b}_{1})-\exp(\lambda^{\intercal}\textbf{b}_{0})}{(\lambda^{\intercal}e_{1})^{2}}e_{1}$

Once again, the second equation can be solved for $\lambda_{2}$. The following
form will be more useful:

$\displaystyle 0$
$\displaystyle=1-\frac{\exp(\lambda_{1}(1-b)+\lambda_{2})-\exp(\lambda_{1}(-b)+\lambda_{2})}{\lambda_{1}}$
$\displaystyle\implies\frac{\lambda_{1}}{\exp(\lambda_{2})}$
$\displaystyle=\exp(\lambda_{1}(1-b))-\exp(\lambda_{1}(-b))$ (41)

The first equation is

$\displaystyle\frac{-p_{D}}{1-p_{D}}\left(\frac{1}{2}-b\right)$
$\displaystyle=\frac{\exp(\lambda_{1}(1-b)+\lambda_{2})(1-b)-\exp(\lambda_{1}(-b)+\lambda_{2})(-b)}{\lambda_{1}}$
$\displaystyle\hskip
113.81102pt-\frac{\exp(\lambda_{1}(1-b)+\lambda_{2})-\exp(\lambda_{1}(-b)+\lambda_{2})}{\lambda_{1}^{2}}$
$\displaystyle=\frac{\exp(\lambda_{2})}{\lambda_{1}}\Bigg{[}\exp(\lambda_{1}(1-b))-b[\exp(\lambda_{1}(1-b))-\exp(\lambda_{1}(-b))]$
$\displaystyle\hskip
113.81102pt-\frac{\exp(\lambda_{1}(1-b))-\exp(\lambda_{1}(-b))}{\lambda_{1}}\Bigg{]}$
$\displaystyle=\frac{\exp(\lambda_{1}(1-b))}{\exp(\lambda_{1}(1-b))-\exp(\lambda_{1}(-b))}-b-\frac{1}{\lambda_{1}}=\frac{\exp(\lambda_{1})}{\exp(\lambda_{1})-1}-b-\frac{1}{\lambda_{1}}$

where the second to last equality uses (41) above. Rearranging gives

$\displaystyle\frac{\exp(\lambda_{1})}{\exp(\lambda_{1})-1}-\frac{1}{\lambda_{1}}$
$\displaystyle=\frac{-p_{D}(1/2-b)+(1-p_{D})b}{1-p_{D}}=\frac{2b-p_{D}}{2(1-p_{D})}$

Now notice that
$\frac{\exp(\lambda_{1})}{\exp(\lambda_{1})-1}-\frac{1}{\lambda_{1}}$ is well
defined and continuous whenever $\lambda_{1}\neq 0$, takes values between $0$
and $1$, with limits

$\displaystyle\lim_{\lambda_{1}\rightarrow\infty}\frac{\exp(\lambda_{1})}{\exp(\lambda_{1})-1}-\frac{1}{\lambda_{1}}=1,$
$\displaystyle\lim_{\lambda_{1}\rightarrow-\infty}\frac{\exp(\lambda_{1})}{\exp(\lambda_{1})-1}-\frac{1}{\lambda_{1}}=0$

Repeated applications of l’Hôpital’s rule shows that

$\displaystyle\lim_{\lambda_{1}\rightarrow
0}\frac{\exp(\lambda_{1})}{\exp(\lambda_{1})-1}-\frac{1}{\lambda_{1}}$
$\displaystyle=\lim_{\lambda_{1}\rightarrow
0}\frac{\lambda_{1}\exp(\lambda_{1})-\exp(\lambda_{1})+1}{\lambda_{1}(\exp(\lambda_{1})-1)}=\frac{1}{2}$

Therefore there exists a solution whenever
$\frac{2b-p_{D}}{2(1-p_{D})}\in\left(0,\frac{1}{2}\right)\cup\left(\frac{1}{2},1\right)$.
Given this solution, (41) can be rearranged to obtain

$\lambda_{2}=\log\left(\frac{\lambda_{1}}{\exp(\lambda_{1}(1-b))-\exp(\lambda_{1}(-b))}\right)$

Now notice that

$\displaystyle\frac{2b-p_{D}}{2(1-p_{D})}>0$ $\displaystyle\implies
b>\frac{p_{D}}{2},$ $\displaystyle\frac{2b-p_{D}}{2(1-p_{D})}<1$
$\displaystyle\implies b<1-\frac{p_{D}}{2}$

and recall that $b=1/2$ implies $\lambda_{1}=\lambda_{2}=0$ solves the dual
problem. Therefore the dual problem has a solution whenever
$b\in\left(\frac{p_{D}}{2},1-\frac{p_{D}}{2}\right)$.

$P_{1}$ has compact support, and
$f^{*}(\lambda_{1}(y-b)+\lambda_{2})=\exp(\lambda_{1}(y-b)+\lambda_{2})-1$ is
continuous in $y$ for any $(\lambda_{1},\lambda_{2})$. Thus the extreme value
theorem implies the solution is in the interior of
$\left\\{\lambda\in\mathbb{R}^{2}\;;\;E[\lvert
f^{*}(\lambda^{\intercal}h(Y,b))\rvert]<\infty\right\\}=\left\\{\lambda\in\mathbb{R}^{2}\;;\;\int\lvert\exp(\lambda_{1}(y-b)+\lambda_{2})-1\rvert
dy<\infty\right\\}$. The implied solution to the primal,
$q^{b}(y)=(f^{*})^{\prime}(\lambda^{\intercal}h(y,b))=\exp(\lambda_{1}(y-b)+\lambda_{2})$
satisfies $0<q^{b}(y)<\infty$ on the support of $P_{1}$ and solves the moment
conditions. Thus assumption 2 is satisfied for any convex, compact
$B\subset\left(\frac{p_{D}}{2},1-\frac{p_{D}}{2}\right)$.

###  E.2 Linear models

See 4.1

###### Proof.

Let $b^{0},b^{1}\in B$, be distinct, $\alpha\in(0,1)$, and $b^{\alpha}=\alpha
b^{1}+(1-\alpha)b^{0}$. The proof of theorem (3.1) shows that the primal
problem at $b^{0}$ and $b^{1}$ is attained by $Q^{0}$ and $Q^{1}$ with
densities $q^{0}$, $q^{1}$. The moment conditions are
$0=E\left[X_{2}(Y-X_{1}^{\intercal}\beta)\right]=E\left[X_{2}Y\right]-E\left[X_{2}X_{1}^{\intercal}\right]\beta$,
so $Q^{0}\in\textbf{P}^{b^{0}}$ and $Q^{\in}\textbf{P}^{b^{1}}$ implies

$\displaystyle
E_{Q^{1}}\left[X_{2}Y\right]-E_{P_{0X}}\left[X_{2}X_{1}^{\intercal}\right]b^{1}$
$\displaystyle=\frac{-p_{D}}{1-p_{D}}\left(E_{P_{1}}\left[X_{2}Y\right]-E_{P_{1}}\left[X_{2}X_{1}^{\intercal}\right]b^{1}\right),$
(42) $\displaystyle
E_{Q^{0}}\left[X_{2}Y\right]-E_{P_{0X}}\left[X_{2}X_{1}^{\intercal}\right]b^{0}$
$\displaystyle=\frac{-p_{D}}{1-p_{D}}\left(E_{P_{1}}\left[X_{2}Y\right]-E_{P_{1}}\left[X_{2}X_{1}^{\intercal}\right]b^{0}\right)$
(43)

implying that

$E_{\alpha
Q^{1}+(1-\alpha)Q^{0}}\left[X_{2}Y\right]-E_{P_{0X}}\left[X_{2}X_{1}^{\intercal}\right]b^{\alpha}=\frac{-p_{D}}{1-p_{D}}\left(E_{P_{1}}\left[X_{2}Y\right]-E_{P_{1}}\left[X_{2}X_{1}^{\intercal}\right]b^{\alpha}\right)$

Similarly,
$E_{Q^{0}}[\mathbbm{1}\\{X=x_{k}\\}]=E_{Q^{1}}[\mathbbm{1}\\{X=x_{k}\\}]=E_{P_{0X}}[\mathbbm{1}\\{X=x_{k}\\}]$
for all $k=1,\ldots,K$. It follows that $Q^{\alpha}\equiv\alpha
Q^{1}+(1-\alpha)Q^{0}$ is feasible for $b^{\alpha}=\alpha
b^{1}+(1-\alpha)b^{0}$. This implies

$d_{f}(Q^{\alpha}\|P_{1})\geq\inf_{Q\in\textbf{P}^{b^{\alpha}}}d_{f}(Q\|P_{1})=\nu(b^{\alpha})$

$Q^{\alpha}$ has $P_{1}$-density $q^{\alpha}=\alpha q^{1}+(1-\alpha)q^{0}$.
Convexity of $f$ implies that for any $(y,x)$,

$\alpha f(q^{1}(y,x))+(1-\alpha)f(q^{0}(y,x))\geq f(\alpha
q^{1}(y,x)+(1-\alpha)q^{0}(y,x))=f(q^{\alpha}(y,x))$

integrating with respect to $P_{1}$ shows that

$\alpha d_{f}(Q^{1}\|P_{1})+(1-\alpha)d_{f}(Q^{0}\|P_{1})\geq
d_{f}(Q^{\alpha}\|P_{1})\geq\nu(b^{\alpha})$

Since the left hand side equals $\alpha\nu(b^{1})+(1-\alpha)\nu(b^{0})$, this
shows $\nu$ is convex. Notice that no properties of $P_{1}$, $P_{0X}$ were
specified in the argument above, so the same argument works to show
$\hat{\nu}_{n}(b)$ is convex in $b$ by replacing $P_{1}$, $P_{0X}$ with their
empirical counterparts.

Finally, to see that $\nu$ is strictly convex when $E[X_{2}X_{1}^{\intercal}]$
has full column rank, use equations (42) and (43) to see that

$\displaystyle(1-p_{D})\left[E_{Q^{1,n}}\left[X_{2}Y\right]-E_{Q^{0,n}}\left[X_{2}Y\right]\right]$
$\displaystyle=\underbrace{\left[p_{D}E_{P_{1}}[X_{2}X_{1}^{\intercal}]+(1-p_{D})E_{P_{0}}[X_{2}X_{1}^{\intercal}]\right]}_{=E[X_{2}X_{1}^{\intercal}]}(b^{1}-b_{0})$

Since $E[X_{2}X_{1}^{\intercal}]$ has full column rank and $b^{1}-b^{0}\neq
0$,

$\displaystyle(1-p_{D})\left[E_{Q^{1}}\left[X_{2}Y\right]-E_{Q^{0}}\left[X_{2}Y\right]\right]\neq
0$

and thus $Q^{1}$ differs from $Q^{0}$, implying $q^{1}$ differs from $q^{0}$
on a set of positive $P_{1}$ measure. For $(y,x)$ in that set, strict
convexity of $f$ assumed in (1) (iv) implies

$\alpha f(q^{1}(y,x))+(1-\alpha)f(q^{0}(y,x))>f(\alpha
q^{1}(y,x)+(1-\alpha)q^{0}(y,x))=f(q^{\alpha}(y,x))$

integrating with respect to $P_{1}$ implies $\alpha
d_{f}(Q^{1}\|P_{1})+(1-\alpha)d_{f}(Q^{0}\|P_{1})>d_{f}(Q^{\alpha}\|P_{1})$,
and thus
$\alpha\nu(b^{1})+(1-\alpha)\nu(b^{0})>d_{f}(Q^{\alpha}\|P_{1})\geq\nu(b^{\alpha})$.
∎

Simulations suggest that OLS more generally produces convex $\nu(b)$. Consider
the data generating process described in section 5.2. Here the data is of the
form $\\{D_{i},D_{i}Y_{i1},D_{i}Y_{i2},X_{i1},X_{i2}\\}_{i=1}^{n}$, and the
model is given by

$\displaystyle
Y_{i1}=\beta_{0}+\beta_{1}X_{1}+\beta_{2}Y_{2}+\beta_{3}X_{2}+\varepsilon,$
$\displaystyle E\left[\begin{pmatrix}1\\\ X_{1}\\\ Y_{2}\\\
X_{2}\end{pmatrix}\varepsilon\right]=0$

The following figure investigates convexity of the $\nu(b)$ (where
$d_{f}(Q\|P)=H^{2}(Q,P)$) numerically, by looking for convexity along random
line segments. Specifically, let $b_{1}$ and $b_{0}$ be points in the sample
space and compute $\hat{\nu}_{n}(\lambda b_{1}+(1-\lambda)b_{0})$ for many
values of $\lambda$ between $0$ and $1$. The following figure shows the
results of this exercise for 10 randomly selected $(b_{0},b_{1})$ pairs, and
shows that no deviation from convexity was detected.

###  E.3 Binary choice models

Let $V\in\\{0,1\\}$, $W\in\mathbb{R}^{d}$, and suppose interest is in
$P(V=1\mid W=w)$. A common choice of model assumes

$P(V=1\mid W=w)=F(w^{\intercal}\beta)$

for a known CDF $F(\cdot)$. This model can be derived from a latent variable
model of the form $V=\mathbbm{1}\\{W^{\prime}\beta\geq\xi\\}$, where
conditional on $W$, the unobserved “latent variable” $\xi$ has distribution
$F(x)$.

$P(V=1\mid W=w)=P(\xi\leq W^{\intercal}\beta\mid W=w)=F(w^{\intercal}\beta)$

For example, the logistic regression uses
$F(x)=\Lambda(x)=\frac{\exp(x)}{1+\exp(x)}$, while the probit model uses
$F(x)=\Phi(x)=\int_{\infty}^{x}\frac{1}{\sqrt{2\pi}}\exp(-t^{2}/2)dt$.

Given i.i.d. data of the form $\\{V_{i},W_{i}\\}_{i=1}^{n}$, the model can be
estimated through maximum likelihood. The likelihood of an observation $(V,W)$
is $F(W^{\intercal}b)^{V}(1-F(W^{\intercal}b)^{1-V}$, implying a population
log-likelihood of

$\displaystyle\ell(b)\equiv
E\left[V\ln(F(W^{\intercal}b))+(1-V)\ln(1-F(W^{\intercal}b))\right]$

Assuming $F(x)$ is differentiable with density $f(x)$ and that differentiation
and expectation can be interchanged, the score is given by

$\displaystyle
s(b)\equiv\nabla_{b}\ell(b)=E\left[\frac{f(W^{\intercal}b)}{F(W^{\intercal}b)\left(1-F(W^{\intercal}b)\right)}\left(V-F(W^{\intercal}b)\right)W\right]$

and supposing $f(x)$ is differentiable with derivative $f^{\prime}(x)$, the
Hessian can be calculated and shown negative definite when $E[WW^{\intercal}]$
is full rank. This implies the log-likelihood is strictly concave, and hence
the first order condition suffices for maximization. Therefore the model could
also be viewed as a GMM model solving

$\displaystyle
0=E\left[\frac{f(W^{\intercal}\beta)}{F(W^{\intercal}\beta)\left(1-F(W^{\intercal}\beta)\right)}\left(V-F(W^{\intercal}\beta)\right)W\right]$

####  E.3.1 Logistic model

For the logistic model, $F(x)=\Lambda(x)=\frac{\exp(x)}{1+\exp(x)}$, we can
compute that

$f(x)=\frac{\exp(x)}{(1+\exp(x))^{2}}=F(x)(1-F(x))$

and thus the score simplifies to

$s(b)=E\left[\left(V-\Lambda(W^{\intercal}b)\right)W\right]$

This makes it straightforward to compute the Hessian of the log-likelihood as

$\nabla_{b}^{2}\ell(b)=E\left[-\Lambda(W^{\intercal}b)(1-\Lambda(W^{\intercal}b))WW^{\intercal}\right]$

Let $U\equiv\sqrt{\Lambda(W^{\intercal}b)(1-\Lambda(W^{\intercal}b))}W$ and
observe that $\nabla_{b}^{2}\ell(b)=-E[UU^{\intercal}]$ is negative definite
if $E[WW^{\intercal}]$ is full rank. Thus, the logistic model can be viewed as
a GMM model, where $\beta$ solves

$0=E\left[\left(V-\Lambda(W^{\intercal}\beta)\right)W\right]$

This model can be put into the form used in assumption 1 with
$Z=(Z_{(1)},Z_{-1})=(V,W)$,
$g(z,b)=(z_{1}-\Lambda(z_{-1}^{\intercal}b))z_{-1}$, and
$\nabla_{b}g(z,b)=-\Lambda(z_{-1}^{\intercal}b)(1-\Lambda(z_{-1}^{\intercal}b))z_{-1}z_{-1}^{\intercal}$.

Simulations suggest that the logistic model may also produce a convex
$\nu(b)$. Consider the data generating process described in section 5.3. The
logistic model can also be investigated for convexity. The same numerical
exercise described above results in a figure that again shows no deviation
from convexity.