# United We Stand: Decentralized Multi-Agent
Planning With Attrition

Nhat Nguyen Corresponding Author. Email<EMAIL_ADDRESS>Duong Nguyen  Gianluca Rizzo  Hung Nguyen  The University of Adelaide,
Australia  HES SO Valais, Switzerland, and the University of Foggia, Italy.

###### Abstract

Decentralized planning is a key element of cooperative multi-agent systems for
information gathering tasks. However, despite the high frequency of agent
failures in realistic large deployment scenarios, current approaches perform
poorly in the presence of failures, by not converging at all, and/or by making
very inefficient use of resources (e.g. energy). In this work, we propose
Attritable MCTS (A-MCTS), a decentralized MCTS algorithm capable of timely and
efficient adaptation to changes in the set of active agents. It is based on
the use of a global reward function for the estimation of each agent’s local
contribution, and regret matching for coordination. We evaluate its
effectiveness in realistic data-harvesting problems under different scenarios.
We show both theoretically and experimentally that A-MCTS enables efficient
adaptation even under high failure rates. Results suggest that, in the
presence of frequent failures, our solution improves substantially over the
best existing approaches in terms of global utility and scalability.

1338

##  1 Introduction

Cooperative multi-agent systems (MAS) are systems where multiple agents (such
as autonomous vehicles/drones) work together to achieve a common goal such as
maximizing a shared utility [17]. These agents can communicate and coordinate
with each other, either directly or indirectly, to solve complex tasks that
are beyond a single agent’s capabilities. Examples are drone swarms for
autonomous aerial surveillance or disaster relief operations, or teams of
robots that collaborate to explore unknown environments, harvest data from
sensors, or manipulate objects, among others [47].

Centralized approaches for addressing the MAS planning problem do not scale
with the number of agents, as the amount of computational resources required
to solve it quickly becomes prohibitive. In addition, the amount of
information exchange required for a centralized planner to manage all agents
can be unfeasibly high in large-scale settings, particularly in remote areas
and disaster scenarios [44]. Thus, recent research has focused on
decentralized approaches for online MAS planning [49]. Indeed, they offer
enhanced robustness, reduced computational burden, and lower communication
load, particularly on infrastructure-based communications such as cellular
radio access networks [11].

The main challenge in decentralized approaches for cooperative MAS is
optimizing agents’ actions in a distributed manner to maximize a global reward
function. This problem can typically be modeled as a Decentralized Partially
Observable Markov Decision Process (Dec-POMDP) [34]. However, the
computational complexity of Dec-POMDPs presents a significant hurdle, making
direct optimal solution search infeasible in polynomial-time [5]. Several
sampling-based planning algorithms have also been proposed to improve
computational efficiency, particularly for special classes of Dec-POMDPs, such
as multi-robot active perception [49]. A first family of approaches to address
this is given by point-based methods, which scale well, but they may not cover
the entire belief space well [35, 42]. Another set of algorithms is based on
policy search [40, 1] based on a parameterized policy representation. They can
handle problems with large action spaces, but they may get stuck in local
optima or require many samples [1]. Thus, attention has turned towards
algorithms based on Monte Carlo tree search (MCTS), due to their ability to
effectively explore long planning horizons, their anytime nature [25], and
their excellent performance in decentralized settings [11, 7, 15], effectively
overcoming the limitations of other approaches.

In many present-day MAS application scenarios, the departure of agents from
the system (henceforth denoted as attrition, and due to e.g. failures or
energy depletion) is a very common feature. However, all of the main
approaches to decentralized MAS planning assume agents are always available
and actively contributing to the joint planning process. When applied to
scenarios with attrition, they perform in a heavily suboptimal manner and they
often do not converge at all [14, 33]. In swarm robotics, for instance, agent
attrition due to robot failures, damage, or energy depletion affects the
overall swarm behavior and task completion. Designing robust algorithms for
decentralized MAS planning capable of effectively handling agent loss is
critical for their successful deployment many in practical scenarios.

The common approaches for scenarios with attrition are based on periodically
resetting agents’ learned behavior, and restarting the learning process [2,
38, 21]. In volatile settings with frequent failures, such a feature may
significantly hamper the overall performance of the active perception task, by
slowing down the convergence rate and by keeping the system far from adapting
and thus from achieving optimal operating conditions. Therefore, how to
efficiently and effectively perform online MAS planning in the presence of
attrition, while achieving fast convergence, is a key open issue.

In this paper, we develop a novel decentralized planning algorithm that
achieves both of these objectives. Our approach is based on MCTS and the use
of the global reward instead of the local one in the estimation of each
agent’s local contribution. Moreover, it exploits regret matching (RM) [22] to
coordinate the actions between agents. We prove that our approach guarantees
that the average joint action of all agents converges to a Nash equilibrium
(NE) if every agent applies the same RM procedure in any cooperative game with
a submodular utility function. Arriving at an NE guarantees no diverging
interest between the agents, and therefore it ensures that all participants
come into a self-enforcing agreement to effectively coordinate their action
decisions in a decentralized manner. The main contributions of our work are:

  * •

We develop Attritable MCTS (A-MCTS), a new online decentralized planning
algorithm, based on MCTS and Regret Matching, that can quickly and efficiently
adapt the plan to settings where agents fail, even at high rates.

  * •

We show that, by modulating the utility function for each agent, under the
assumption of submodularity, successive iterations are guaranteed to improve
joint policies, and eventually lead to convergence of our algorithm. We prove
a strong convergence result for approximating a pure-strategy Nash equilibrium
in a fully distributed fashion.

  * •

We evaluate our proposed approach in several information-gathering scenarios
with attrition. Results suggest that, in the presence of frequent failures,
our solution improves substantially over the best existing approaches in terms
of global utility and scalability.

##  2 Related Work

Information-gathering problems are often modeled as sequential decision-making
problems [48]. When there are multiple agents, decentralized information
gathering can be viewed as a decentralized POMDP [5]. The dominant approach to
Dec-POMDP is to first solve the centralized, offline planning over the joint
multi-agent policy space, and then push these policies to agents to execute
them in a decentralized fashion [34]. When the state of the environment or
agents is not known ahead of time, these approaches become infeasible. Fully
decentralized Dec-POMDP solvers exist [43]. However, they require significant
memory and incur high computational complexity due to the requirements to
compute and store all the reachable joint state estimations [26].

Recently, simultaneous distributed approaches based on MCTS have gained
significant interest due to their flexibility in trading off computation time
for accuracy. The key idea is to use the upper confidence bound (UCB) [25] for
planning the best course of action. To implement cooperation between agents,
these methods usually keep a predefined model of the teammates, which can be
heuristic or machine learning trained [11, 15, 10]. However, as they are based
on trained knowledge, they are unsuitable for online planning in settings that
change unpredictably, such as in disastrous environments.

To address this, new approaches based not on apriori knowledge about agents’
behavior, but on information sharing among them, have been proposed (Dec-MCTS
[7]). A key aspect of Dec-MCTS and all its subsequent variations [27, 28, 33]
is that each agent is assigned a local utility function, which does not
measure the total team reward but the contribution of that agent only. To deal
with any uncertainty that arises during the mission, Dec-MCTS algorithms allow
for online replanning during execution, by having agents update their beliefs
about the system.

Under high uncertainty scenarios, a growing body of literature review in the
area of multi-drone systems [45, 29, 16, 20] explores the significant
challenges posed by agent attrition – the loss or removal of individual drones
(due to mechanical failures, environmental factors, and human errors), and
highlights the need to address attrition for robust system performance. In
systems with attrition in which agents may fail abruptly, all of the above-
mentioned approaches do not apply, as they do not allow adjusting to attrition
in agents’ populations. In the present work, we show that the suboptimality of
current Dec-MCTS algorithms is due to the usage of the marginal contribution
combined with the submodular properties of the global utility functions.

Another body of literature on related works concerns Open Agent Systems
(OASYS), in which agents can enter and leave over time. Most solutions to
OASYS are either fully or partially offline, i.e., offline planning with
online execution [12, 9] or online planning with precomputed offline policies
[18]. This is not feasible in applications with significant sources of
uncertainty, particularly when the environment’s state or mental models of the
agents are unknown in advance, and when the agents’ failures occur abruptly
during execution. A recent work [23] proposed a fully online approach that
leverages communication between agents related to their presence to predict
the actions of others. This approach assumes that agents can communicate their
existence implicitly. In scenarios where the communication is intermittent or
agents vanish without warning, the unforeseeable failure can significantly
impact coordination and planning, jeopardizing the overall performance. In
addition, the computational complexity of modeling each other’s presence and
predicting their actions can make the system computationally intractable on a
large scale. Thus, it isn’t directly equipped to handle sudden agent failures
and may require further refinement to be viable in large-scale or highly
dynamic environments.

Our paper focuses on problems where agents experience hard failures in an
abrupt and unforeseeable fashion. This unpredictable nature makes the existing
techniques not directly applicable. Therefore, more research is needed to
enhance the robustness and resilience of multi-agent systems in such uncertain
attrition scenarios. Our work explicitly tackles this challenge by providing a
new approach for online decentralized planning for multi-agents that does not
require precomputed offline policies and mental models. Instead, agents reason
about the actions and existence of others using directly communicated
information. We employ a computational-effective game-based technique to
coordinate agents, enabling adaptive decision-making in the presence of peer
failures while ensuring fast convergence in polynomial time relative to system
size.

##  3 Problem Formulation

In this paper, we consider a set $\mathcal{N}$ of $N$ autonomous agents moving
within a given area of space. We consider a set of $R$ regions of interest in
a given area, where $R_{k}$ is the $k$-th element of the set. We assume each
region is a sphere with an equal radius, however, the formulation could extend
to more complex models. Without loss of generality, we assume agents move
along an undirected graph $G=(V,E)$ that is placed in the same space as the
regions of interest. Each vertex $v_{i}\in V$ represents a location, and each
edge $e_{ij}$ represents a feasible route from vertex $v_{i}$ to $v_{j}$. A
key property of this graph is that it traverses at least once every region of
interest. This graph typically models constraints to agent trajectories due to
the morphology of the monitored environment, presence of obstacles, regions of
interest distribution, and characteristics of agent movements, among others.
The specific way in which the graph is derived is thus application and
context-dependent [33]. The graph is defined at the beginning of the mission,
it does not change over time and it is known by all agents.

The _path_ of agent $n$, denoted as $p^{n}$, is an ordered list of edges
$p^{n}=(e^{n}_{1},e^{n}_{2},...)$, such that two adjacent edges in the path
are connected by a vertex of the graph. With $p=(p^{1},...,p^{n},...,p^{N})$
we denote the joint paths of every agent. Let $B$ denote the maximum path
length of each agent, which equals the number of edges an agent can traverse.
Such a maximum value is derived from the agent’s speed, but it may also
capture various constraints, e.g. due to finite storage capacity, among
others. To any path $p^{n}$ we associate a cost $b(p^{n})$, equal to the
number of traversed edges. A region $R_{k}$ is observed if it is traversed by
a path of an agent. Every region $R_{k}$ is associated with a utility
$U(R_{k})$, which models the value of the information that agents may collect
from it. For ease of analytical treatment, we assume that it takes one unit of
time to traverse any edge and that any exchange of information among agents is
instantaneous. Note however that our approach can be easily extended to
account for nonzero exchange duration, as well as for edge traversal times
that differ among edges and agents.

Finally, we assume each agent can exchange information at any point in time
with any other agent. This models scenarios in which agents have a wireless
interface to a cellular access network. We assume the information exchange to
be instantaneous, independent from the amount of information shared, and
reliable, with no loss. In the experimental section, we relax this assumption
and investigate the impact of nonidealities in information sharing on the
effectiveness of our approach.

###  3.1 Multi-agent planning with attrition

We denote the information-gathering task as a mission, for which each agent
performs independent actions to achieve a collective goal - maximizing the
global utility for the whole team. Each agent $n$ plans its path $p^{n}$ and
coordinates with others in a decentralized manner while satisfying the given
budget constraint $B$ on path length. This formulation of the information
gathering problem generalizes many multi-agent path planning problems, such as
team orienteering problem [6]. We consider a scenario, in which mission
planning is performed in a decentralized manner for scalability and
computational feasibility, as mentioned in Section 1. Thus, each agent plans
its path while considering the potential actions of other agents and the
team’s total utility. We consider scenarios where a subset $\mathcal{F}$ of
the N agents fail during the mission. We focus on hard failures, where agents
interrupt reward collection and information exchange. We assume the set of
agents that fail $\mathcal{F}$ is unknown in advance and the time at which
they fail to be determined by any arbitrary criteria or distribution.
Therefore, our solution does not rely on knowing its size and probability
distribution. In the occurrence of a failure, all the utility collected by the
failed agent is lost, i.e. it is not considered anymore in the computation of
the global utility of the mission. This models a typical setup in information
gathering, in which data collected by agents is relayed to data sinks only at
the end of the mission.

Our goal is to provide an efficient planning and coordination mechanism that
can quickly adapt to agent failures and maximize the global utility of the
mission within the agent’s budget constraint. Let
$\mathcal{P}=(P^{1},...,P^{n},...,P^{N})$, with $P^{n}$ denote the set of all
possible paths of length $B$ which starts at agent $n$ starting position. We
define the following problem:

######  Problem 1.

(Multi-agent planning in attrition settings)

$\underset{p\in\mathcal{P}}{\text{maximize}}\ U_{g}(p)$ (1) Subject to:
$\displaystyle\quad b(p^{n})\leq B,\quad\forall n\in\mathcal{N}$ (2)
$\displaystyle\quad 0\leq|\mathcal{F}|\leq N$ (3)

Constraint (2) derives from imposing that the total path length for the agent
$n$ to be less than the travel budget $B$ available to each agent.
Intuitively, our goal is to find a path for each agent such that the global
utility associated with all regions observed by all agents during the mission
is maximized, while a subset $\mathcal{F}$ of agents fail. Such an
optimization problem cannot be solved efficiently. Indeed it is easy to see
that Problem 1 is a variant of the well-known NP-hard traveling salesman
problem.

##  4 Attritable MCTS with Regret Minimization

In this section, we first give a brief introduction to Monte Carlo Tree Search
and its most popular decentralized version. We then show the root cause of the
inefficiency of existing decentralized MCTS approaches with attrition.

MCTS is an excellent approach for online planning problems [25]. The tree
$\mathcal{T}_{n}$ for agent $n$ is defined such that each node $s$ of the tree
represents a state and each edge $a$ starting from that node represents an
available action. A branch from the root node to another node represents a
valid action sequence. The tree is incrementally grown via a four-step
process: _selection_ , _expansion_ , _rollout_ , and _backpropagation_.
Decentralized Monte Carlo Tree Search (Dec-MCTS) [7] extends the power of MCTS
to MAS using intention sharing. Specifically, agent $n$ maintains a
probability mass function $q_{n}(x_{n})$ over the set of all possible action
sequences $\mathcal{X}_{n}$, where $x_{n}\in\mathcal{X}_{n}$ is a primitive
action sequence. The intentions of other agents except agent $n$ are denoted
by $q_{-n}$ and $\mathcal{X}_{-n}$. By taking a probabilistic sampling from
the communicated intention, each agent can reconstruct the global utility. To
create better coordination, rather than optimizing directly for the global
utility $U_{g}$ of the entire team, each agent $n$ instead optimizes for a
local _marginal contribution_ utility function $U_{n}$. That is, agent $n$
estimates the rollout score for executing $x_{n}$ as:

$F_{n}(x_{n})=U_{n}(x_{n},x_{-n})=U_{g}(x_{n},x_{-n})-U_{g}(x_{-n})\ ,$ (4)

where $U_{g}(x_{-n})$ is the global utility without the contribution of agent
$n$.

We now analyze Dec-MCTS asymptotic behavior when agents fail. We are
particularly interested in submodular reward functions, frequently arising in
data collection problems [13, 39]. Submodular set function, which is defined
in Definition 1, satisfies the diminishing returns property. Regarding the
information-gathering problem discussed in this paper (see Section 3), the
marginal gain of adding a new location to the set of visited locations
decreases as the number of locations visited increases.

######  Definition 1 (Submodular set function).

Let $g:2^{\Omega}\rightarrow\mathbb{R}$ be a set function where $2^{\Omega}$
is the power set of $\Omega$. Then _g_ is a submodular function if for every
$X,Y\subseteq\Omega$ with $X\subseteq Y$ and every $x\in\Omega\setminus Y$ the
following inequality holds

$g(X\cup x)-g(X)\geq g(Y\cup x)-g(Y)\ .$

In particular, at iteration $t$, let $x_{n}$ denote the chosen action sequence
of agent $n$ and $x_{-n}$ denote the combined sampled action sequences of
other agents. Assume that at the next iteration $t+1$, a subset of agents
fails. Let $x^{\prime}_{-n}$ be the combined sampled action sequences of all
agents except agent $n$ and the lost agents (i.e., that is
$x^{\prime}_{-n}\subseteq x_{-n}$).

######  Proposition 1.

If the global objective function $U_{g}$ is submodular, then
$F_{n}^{(t+1)}(x^{*}_{n})\geq F_{n}^{(t)}(x^{*}_{n})$ by the diminishing
return property due to submodularity, where $F_{n}(x_{n})$ is defined in (4).

Figure 1: Overview of the A-MCTS algorithm. Agents incrementally grow the
search using the best response policy $x^{BR}$ and communicate their best
actions $\hat{\mathcal{X}}$. Regret Matching is then used to compute
distributively a joint policy for the cooperative game. These solutions are
synchronized and the most payoff-dominant is chosen as the best response
policy $x^{BR}$.

Proposition 1 states that if some agents fail during the mission, the
remaining agents would mistakenly perceive that the contribution of their
previous actions increases. Hence, they would not be aware of the actual
reduction of the global utility and update their plans111For analysis of Dec-
MCTS behavior when agent failures occur after the algorithm has converged,
please see Appendix A in the Supplementary Material. Fixing this issue
requires both a new, context-aware way to compute the reward and a new way to
coordinate the actions with other agents on this new reward function. In the
next section, we present our proposed algorithm for the multi-agent planning
in attrition settings problem 1.

###  4.1 Overview of the A-MCTS algorithm

We develop Attritable MCTS (A-MCTS), an online decentralized MCTS algorithm
that quickly adapts to agents’ attrition and efficiently coordinates action
between the remaining agents. Its performance mainly relies on two key
factors, including the joint-utility-guided decentralized tree search, and the
best response policy given the shared intentions of others. Each agent runs
A-MCTS distributedly to plan for itself a path that is expected to maximize
the total utility of the whole mission. Agents then execute the first planned
action and observe any changes. After that, they perform replanning from their
new state and update the planned paths based on newly available information.
The search tree may be pruned by removing all children of the root except the
selected branch. This cycle of planning and execution continues until the
travel budget expires. The pseudo-code of A-MCTS for agent $n$ is shown in
Algorithm 1.

The tree $\mathcal{T}_{n}$ of agent $n$ is incrementally built over its action
sequences space $\mathcal{X}_{n}$ while considering the possible behaviors of
others $\mathcal{X}_{-n}$ (Line 6-9). In the _selection phase_ , the
discounted upper confidence bound on Tree (D-UCT) [7] is applied to handle the
abrupt changes in reward values caused by the actions of other agents.

Algorithm 1 A-MCTS algorithm for agent $n$

0: Global objective function $U_{g}$, actions budget $B$

0: best action sequence $x^{\ast}_{n}$ for agent $n$

1: $\mathcal{T}_{n}\ {\leftarrow}\textit{Initilize MCTS Tree}$

2: while computation budget not met do

3: $\hat{\mathcal{X}_{n}}\ {\leftarrow}\textit{Select Subset
From}(\mathcal{T}_{n})$

4: $(\hat{\mathcal{X}},\hat{\mathcal{X}}_{-n})\
{\leftarrow}\textit{Communicate and Update}(\hat{\mathcal{X}_{n}})$

5: $x^{BR}\ {\leftarrow}\textit{Regret Matching
Coordination}(\hat{\mathcal{X}})$

6: for fixed number of iterations do

7: $x_{n}\ {\leftarrow}\textit{D-UCT Select, Expand \&
Rollout}(\mathcal{T}_{n},B)$

8: $F_{n}\ {\leftarrow}U_{g}(x_{n},x^{BR}_{-n})$

9: $\mathcal{T}_{n}\ {\leftarrow}Backpropagation(\mathcal{T}_{n},F_{n})$

10: $x^{\ast}_{n}\ {\leftarrow}\textit{Best Next Action}(\mathcal{T}_{n})$

11: return $x^{\ast}_{n}$

The key idea of our proposed algorithm is to have the search trees of every
agent be guided by the same utility of the joint action sequences. This is
achieved by letting all agents optimize their local actions using the global
utility $U_{g}$ directly (Line 8). Each agent can then decide its path $x_{n}$
independently to maximize $U_{g}$ and be aware of the change in the global
rewards immediately if there are failures in the system. However, the
uncertainty in other agents’ plans has also been shown to degrade the overall
performance when using the global objective function to optimize local actions
[46]. To overcome this issue, we propose to let each agent improve its policy
iteratively while assuming others keep their policies fixed.

More precisely, given a set of all possible action sequences of all agents
$\mathcal{X}=(\mathcal{X}_{n},\mathcal{X}_{-n})$, A-MCTS will periodically
compute a “best response" set of joint action sequences that maximize the
joint utility for all participants $x^{BR}:=\\{x^{BR}_{n},x^{BR}_{-n}\\}$
(Line 5). Each agent will then assume other agents coordinately determine
their policies following such “best response" $x^{BR}_{-n}$ and uses such
information to compute the utility for its action sequence selection while
growing the MCTS tree (Line 8). In general, the cardinality of
$\mathcal{X}_{n}$ can be very large and it grows exponentially. To reduce the
computation and communication requirements, we consider only those dynamically
updated subsets $\mathcal{\hat{X}}_{n}\subseteq\mathcal{X}_{n}$ of the most
promising action sequences. The set $\mathcal{\hat{X}}_{n}$ is chosen as the
best rollouts of $M$ fixed nodes in the search tree $\mathcal{T}_{n}$ with the
highest discounted empirical average (Line 3). We then define the following
problem:

######  Problem 2.

(Best joint policy for multi-agent planning)

$\underset{(x_{1},x_{2},\dots,x_{N})}{\text{maximize}}\
U_{g}(x_{1},x_{2},...,x_{N})\ $ (5) Subject to: $\displaystyle
x_{n}\in\hat{\mathcal{X}}_{n},\quad\forall n\in\mathcal{N}$ (6)

The objective is to find an action profile $(x_{1},x_{2},\dots,x_{N})$ that
maximizes the global utility $U_{g}(\cdot)$. Such an optimization problem
cannot be solved efficiently. Indeed it is NP-hard to maximize a submodular
function [37]. Seeking a Nash equilibrium (NE) (where each agent policy is the
best response to the others) that achieves a good efficiency compared to the
optimal solution is more accessible [36]. A greedy algorithm is usually
employed to find an approximation solution [31]. However, we will show later
with simulations that greedy solutions can be substantially suboptimal even in
scenarios with few agents. In the following section, we provide a distributed
regret-based solution to Problem 2 that quickly and efficiently computes an NE
joint policy for multi-agent systems, regardless of their complexity.

###  4.2 Regret Matching For Cooperative Coordination

In this paper, we consider the distributed solution of the optimization
problem 2 where each agent decides its path based on local information and
limited communication from its peers. We aim to design a decision-making
method that is capable of operating and adapting with occasional communication
or less, where every agent acts solely based on its local observation and does
not need to constantly communicate every decision with the others. This is to
guarantee that the algorithm can effectively handle the agent attrition
situation described in Section 3.1. The main difficulty here is how to ensure
the independent decisions of the agents lead to jointly optimal decisions for
the group. To address this challenge, we formulate the problem of finding for
each agent an action sequence that collectively maximizes the joint utility as
a multi-agent cooperative game. We then propose a distributed mechanism, where
every agent independently simulates a multi-player cooperative game based on
the local information available to itself and solves the game by self-play.
For this purpose, a game theory learning algorithm based on the Regret
Matching technique [22] is employed to approximate the Nash equilibrium of the
game.

Let $\hat{\mathcal{X}}=(\hat{\mathcal{X}_{n}},\hat{\mathcal{X}}_{-n})$ denote
the joint set of action sequences that are shared between all agents, and
$x_{nm}$ denote the action sequence $m$ of agent $n$. In our approach,
periodically, every agent independently constructs a matrix game in which the
set of players contains all the active agents and the set of actions is
$\hat{\mathcal{X}}$. At this stage, each agent applies the Regret Matching
(RM) procedure as proposed in [22] to its estimated matrix game to compute a
best response joint decision. The pseudo-code of our RM game is shown in
Algorithm 2.

To further improve the performance of RM in cooperative settings, we let the
agents use the global utility to calculate the regrets instead of the local
utility. At each iteration $t$, an action $x_{nm}\in\mathcal{X}$ is sampled
for each agent based on a probability distribution. Let $p$ denote this
probability distribution where $p(x_{nm})$ is the probability for $x_{nm}$ and
$\sum_{j=1}^{M}p(x_{nj})=1,\forall n\in\mathcal{N}$. With
$x^{(t)}:=\\{x^{(t)}_{n},x^{(t)}_{-n}\\}$, we denote the sampled set at
iteration $t$, where $x^{(t)}_{n}$ is the sample action for agent $n$ and
$x^{(t)}_{-n}$ is the sampled actions for all agents except agent $n$. We then
define the regret of agent $n$ for not taking action $m$ at iteration $t$ as
$R^{(t)}_{nm}=U_{g}(x_{nm},x^{(t)}_{-n})-U_{g}(x^{(t)}).$ Denote $\mathcal{R}$
as the cumulative regret matrix where an element $\mathcal{R}_{nm}$ is the
regret for $x_{nm}$ and $\mathcal{R}^{+}_{nm}=\max\\{\mathcal{R}_{nm},0\\}$.
Then, the probability distribution $p$ used at the next iteration will be
updated as

$p(x_{nm})=\begin{cases}\frac{\mathcal{R}^{+}_{nm}}{\sum_{m=1}^{M}\mathcal{R}^{+}_{nm}}&\text{if
$\sum_{m=1}^{M}\mathcal{R}^{+}_{nm}>0$,}\\\
\frac{1}{M}&\text{otherwise.}\end{cases}$ (7)

Algorithm 2 Regret Matching Coordination algorithm

0: Global objective function $U_{g}$, joint compressed action sequences set
$\hat{\mathcal{X}}$

0: Best response joint action sequences $x^{BR}$

1: Every agent $n\in\mathcal{N}$ performs the following steps $2-9$

2: Initialize $\mathcal{R}$ to zeroes and $p$ to uniformly random

3: for $t=1,2,\dots$ do

4: $x^{(t)}{\leftarrow}\textit{Sample}(\hat{\mathcal{X}},p)$

5: for each $x_{nm}\in\hat{\mathcal{X}}$ do

6: $\mathcal{R}_{nm}\
{\leftarrow}\mathcal{R}_{nm}+U_{g}(x_{nm},x^{(t)}_{-n})-U_{g}(x^{(t)})$

7: Update $p(x_{nm})$ using Eq. (7)

8:
$x^{RM}_{n}{\leftarrow}\operatorname*{arg\,max}_{x_{im}\in\hat{\mathcal{X}_{i}}}[p(x_{im})],\forall
i\in\mathcal{N}$

9: $x^{RM}_{-n}\ {\leftarrow}\textit{Communicate and Update}(x^{RM}_{n})$

10: return $x^{BR}{\leftarrow}\operatorname*{arg\,max}_{(x^{RM}_{n},\
x^{RM}_{-n})}[U_{g}(x^{RM}_{n},\ x^{RM}_{-n})]$

Denote the joint decision computed using RM by agent $n$, which is the set of
action sequences, one per agent, that has the highest probability $p(x_{nm})$,
as $x^{RM}_{n}$. Similarly, let $x^{RM}_{-n}$ be the computed set for all
agents except agent $n$. Finally, these sets are exchanged between every
agent, and the most payoff-dominant solution is chosen as the best response
joint decision $x^{BR}=(x^{BR}_{n},x^{BR}_{-n})$.

###  4.3 Analysis and Discussion

It has been shown in [4] that there exists no polynomial time algorithm to
compute a pure NE in multiplayer nonzero-sum stochastic games. Hence, we
employ an approximate method of finding the NE by proposing a decentralized
Nash selection method based on Regret Matching for making choices in a
multiplayer matrix game formulated at each decision-making state. Regret
Matching is a regret-based algorithm for learning strategies in games, and is
often used to compute correlated equilibria in multi-player repeated games
with imperfect information. Although the regret matching technique has been
widely used for non-cooperative games, its application in cooperative games,
such as the problem studied in our paper with a submodular utility function,
has only been recently explored [32]. In this work, by leveraging the
submodularity property of the joint objective function, we employ Regret
Matching as a self-play technique to independently learn a Nash-based strategy
for each player. We theoretically prove a stronger result of convergence using
Regret Matching to an approximate pure-strategy Nash solution (see Definition
2), rather than the commonly-used correlated equilibrium, in games where
players’ utility functions are submodular.

######  Definition 2 (Pure-Strategy Nash Equilibrium).

A pure-strategy Nash equilibrium (PSNE) is a joint action profile
$x^{*}=(x^{*}_{n},x^{*}_{-n})\in\hat{\mathcal{X}}$ if for all
$n\in\mathcal{N}$ and all $x_{n}\in\hat{\mathcal{X}}_{n}$ such that:
$U_{n}(x^{*}_{n},x^{*}_{-n})\geq U_{n}(x_{n},x^{*}_{-n})\ .$

######  Theorem 2.

The best response joint decision $x^{BR}$ computed using RM, under the
assumption of submodular utility functions, is a PSNE solution of the matrix-
game representation generated by the set of best feasible paths
$\hat{\mathcal{X}_{n}}\subseteq\mathcal{X}_{n}$ chosen by every agent at each
decision point222For proof and analysis, please see Appendix B and C in the
Supplementary Material .

##  5 Experimental Evaluation

Figure 2: Impact of different parameters on the algorithms’ performance at the
mission end. Failures intensity (the fraction of agents that fail) (a);
Planning time (b); Number of exchanged components (c); Actions budget (d),
Number of agents (e); Number of rewards (f), and Communication failure
probability (g). Results are with $95\%$ confidence interval.

To assess our A-MCTS algorithm, we consider the task of data collection from
underwater wireless sensor networks (UWSN). Such tasks usually call for a
collaboration of multiple autonomous underwater vehicles (AUVs) to traverse
the environment and gather data from sensors. The scenario consists of $200$
randomly distributed sensors in a $4000$ m $\times$ $4000$ m plane, with a
transmission radius of $50$ m (typical for UWSN, e.g. [8]). The graph $G$ of
feasible paths is constructed using a probabilistic roadmap with a Dubins path
model [24]. This model employs curves to refine the straight-line segments
connecting waypoints and is extensively utilized for representing motion
constraints pertinent to vehicle-like nonholonomic robots such as AUVs [3].
The graph $G$ consists of $400$ vertices and an average of $19000$ edges.

We benchmark A-MCTS against the following baselines:

  * •

_Centralized MCTS (Central-MCTS)_ : A single search tree is built for all of
the $M$ harvesting agents with the actions of agent $m$ are at tree depth
$(m,m+M,m+2M,...)$.

  * •

_Dec-MCTS_ [7]: It is the state-of-the-art decentralized multi-agent planning.
In it, agents build their search tree with a marginal contribution utility
function and adapt the same tree after churns occur.

  * •

_Dec-MCTS with reset (Dec-MCTS-Reset)_ : Like Dec-MCTS, each agent builds its
search tree with a marginal contribution utility function. Whenever churns
occur, the tree of each agent is reset. This variant is considered to show
that resetting the trees frequently could hamper the overall performance of
the algorithm.

  * •

_Dec-MCTS with global utility (Dec-MCTS-Global_ : Agents build their search
tree with a global utility function and adapt the same tree after churns
occur. This variant is considered to show that altering the utility function
alone would not enhance performances against churns.

  * •

_A-MCTS with greedy optimization (Greedy-MCTS)_ : In this scheme, we replace
the RM Coordination (Algorithm 2) in our A-MCTS with a greedy algorithm, in
which every agent sequentially picks the actions that deliver the highest
immediate rewards for collaboration. This variant is considered to show that
greedy solutions can be substantially suboptimal in MAS coordination.

For all algorithms, each planning phase consists of $500$ iterations, the
discounting factor is set to $0.9$, and the exploration parameter is set to
$0.4$ (i.e., within the ranges recommended in [7] to ensure the balance
between exploration and exploitation). Unless otherwise stated, each agent
compresses its tree into a set of $10$ possible paths and exchanges it with
its teammates every $50$ planning iterations. Unless otherwise stated, we
assume $20$ agents move in the graph, with a budget $B$ of $9$ actions. These
values are chosen as they have proven to enable a high total utility score in
the vast majority of scenarios considered in our experiments.

To model attrition in the population of agents, we assume that every agent has
the same probability of failing during the mission and that the time at which
each failure takes place is distributed uniformly at random throughout the
mission duration. The key metric we use to evaluate the performance of the
considered algorithms is the _Instantaneous reward coverage (IRC)_ , i.e. the
fraction of available rewards covered (i.e. collected) at a given time.

###  5.1 Performance Benchmarking

In the first evaluation of our algorithm’s adaptability to failures, we
examine the impact of the failure intensity (i.e. fractions of agents that
fail during the mission) on the IRC at the mission end, illustrated in Figure
2a. As expected, all algorithms experience performance declines with
increasing intensity, reflecting reduced reward coverage due to fewer
remaining agents in the system. Notably, with over $50\%$ of agents failing,
Dec-MCTS-Reset surpasses the non-reset version due to the smaller system size
which requires fewer iterations for exploration. Conversely, larger systems
necessitate more time for agents to learn about the environment, hence
frequent resets hamper the algorithm’s performance.

To further elaborate on this matter, we assessed the impact of planning time
on the IRC at the mission end. As Figure 2b shows, other baseline algorithms
improved as planning time increased, with Dec-MCTS-Reset starting to
outperform the non-reset with planning time larger than 750 iterations.
A-MCTS, on the other hand, requires significantly less computational time yet
still achieves the highest rewards regardless of the failure intensity and
rates, thus proving itself as a good solution for online replanning.

The number of paths exchanged between agents significantly influences system
complexity. Increased information exchange potentially leads to better
algorithm performance, albeit at the expense of greater computational
resources and time. To examine this trade-off, in Fig. 2c we evaluated the
impact of different numbers of exchanged components on the IRC at the mission
end. As expected, our proposed algorithm’s performance improved with more
exchanged components, while discounted algorithms showed no benefit. Indeed,
with more exchanged components the utility of the joint policy found by regret
matching improves too. However, given the finite number of optimal policies in
a multi-agent game, escalating the number of components eventually yields
diminishing returns.

As the above results show, resetting the tree would not consistently lead to
improvement because the planning process involves initial exploration in which
agents take random actions to learn reward distribution. Resetting without
sufficient planning time results in suboptimal joint policies. Additionally,
the use of the _marginal contribution_ utility combined with a _submodular_
reward function hampers agents’ ability to recognize global reward reduction
and hence adapt to failures efficiently. Moreover, sampling other agents’
action sequences increases variance in global utility estimation and degrades
the coordination quality. By assuming that the policies of other agents are
fixed, A-MCTS can overcome this instability issue and adapt to agent failures
better. Indeed, with regret matching aids in discovering better joint policies
and thus provides better guidance for the exploration-exploitation of the
search tree, our method exhibits superior performances in all cases.

In another set of experiments, we evaluated the impact of action budget $B$,
the number of agents $N$, the number of rewards, and the communication failure
probability, for a default failure intensity of $50\%$. As Fig. 2d shows,
A-MCTS managed to outperform Dec-MCTS substantially despite the difficulty of
decentralized planning with a growing actions budget. Furthermore, as we
doubled the budget of the action, the superiority of A-MCTS over the other
techniques tripled. A similar behavior is exhibited by the system when we vary
the number of agents. As shown in Fig. 2e, with a small number of agents, the
differences between our algorithm and the discounted methods grow to $20\%$
with an increasing number of agents. In the considered settings, we also
assess the impact of the density of sensors on the algorithms’ performance by
varying the number of sensors within the same area. As shown in Fig. 2f, the
IRC declines as more sensors are introduced in the system. Naturally, with an
increasing number of sensors the area that must be covered by agents expands
as well. Nevertheless, A-MCTS shows better scalability as it consistently
outperforms other methods.

The effectiveness of cooperative MAS is notably influenced by the quality of
inter-agent communication. To understand better the impact of such
limitations, we evaluated the algorithms’ performances under different
communication failure probabilities between each agent pair during a mission.
As shown in Fig. 2g, there is no notable decline in A-MCTS performance even
when half of the communication is disrupted, and it continues to outperform
baseline methods with severely unstable communication. This highlights
A-MCTS’s ability to enable efficient cooperation among agents in hostile
environments with restricted communication.

###  5.2 Trade Off Between Communication Loss and Attrition for A-MCTS
Analysis

Figure 3: Impact of allowed inter-agent communication loss on the performance
of A-MCTS at the end of the mission.

In our approach, repeated communication loss is used as an indication of
attrition. However, in practical settings, inter-agent communication can be
unreliable and intermittent. If the algorithm is more sensitive to
communication loss, it can mistakenly treat delayed messages as agent
failures.

To better understand such impact, in this section, we study how tolerance to
communication loss affects the performance of A-MCTS. Specifically, we
parameterize this tolerance level by the number of times an agent must
experience communication loss with another agent before treating it as
attrition. Fig. 3 shows the IRC at the end of the mission against different
numbers of allowed inter-agent communication loss. With up to 5 allowed
messages loss, A-MCTS still shows no noticeable degradation. However, as the
algorithm is more communication loss tolerant, the performance declines. This
is expected because the remaining agents can not recognize churns fast enough
and adapt efficiently.

##  6 Conclusions

Achieving efficient coordination in multi-agent planning for information
gathering is a critical challenge in practical settings with high attrition
rates. In this work, we proposed a new approach to tackle this issue. Our
proposed algorithm, Attritable MCTS (A-MCTS), effectively coordinates actions
among agents while adapting to agent failures by allowing all agents to
jointly optimize the global utility directly with a new coordination technique
based on regret matching. Our empirical evaluation demonstrates that A-MCTS
improves substantially over the best existing approaches in terms of global
utility and scalability in scenarios with frequent agent failures. As a
follow-up, we intend to extend A-MCTS to more dynamic systems where new agents
can join and the communication is probabilistic. Another line of inquiry is to
study the performance of our algorithm in problems with inter-agent
dependency, where the actions of an agent can only be enabled by the actions
of another.

## References

  * Amato et al. [2010] C. Amato, D. S. Bernstein, and S. Zilberstein.  Optimizing fixed-size stochastic controllers for pomdps and decentralized pomdps.  In _International Conference on Autonomous Agents and Multiagent Systems_ , page 459–466. International Foundation for Autonomous Agents and Multiagent Systems, 2010.
  * Avner and Mannor [2014] O. Avner and S. Mannor.  Concurrent bandits and cognitive radio networks.  In _ECML PKDD_ , pages 66–81. Springer, 2014.
  * Barsky and DeRose [1989] B. Barsky and T. DeRose.  Geometric continuity of parametric curves: three equivalent characterizations.  _IEEE Comput. Graph. Appl._ , 9(6):60–69, 1989.  10.1109/38.41470.
  * Berg and Sandholm [2017] K. Berg and T. Sandholm.  Exclusion method for finding nash equilibrium in multiplayer games.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 31, 2017.
  * Bernstein et al. [2002] D. S. Bernstein, R. Givan, N. Immerman, and S. Zilberstein.  The complexity of decentralized control of markov decision processes.  _Math. Oper. Res._ , 27(4):819–840, 2002.
  * Best et al. [2018] G. Best, J. Faigl, and R. Fitch.  Online planning for multi-robot active perception with self-organising maps.  _Autonomous Robots_ , 42(4):715–738, 2018.
  * Best et al. [2019] G. Best, O. M. Cliff, T. Patten, R. R. Mettu, and R. Fitch.  Dec-mcts: Decentralized planning for multi-robot active perception.  _Int. J. Robot. Res._ , 38(2-3):316–337, 2019.
  * Cai et al. [2019] S. Cai, Y. Zhu, T. Wang, G. Xu, A. Liu, and X. Liu.  Data collection in underwater sensor networks based on mobile edge computing.  _IEEE Access_ , 7:65357–65367, 2019.
  * Chandrasekaran et al. [2016] M. Chandrasekaran, A. Eck, P. Doshi, and L. Soh.  Individual planning in open and typed agent systems.  In _Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence_ , pages 82–91, 2016.
  * Choudhury et al. [2021] S. Choudhury, J. K. Gupta, P. Morales, and M. J. Kochenderfer.  Scalable anytime planning for multi-agent mdps.  In _AAMAS_ , pages 341–349, 2021.
  * Claes et al. [2017] D. Claes, F. Oliehoek, H. Baier, K. Tuyls, et al.  Decentralised online planning for multi-robot warehouse commissioning.  In _AAMAS_ , pages 492–500, 2017.
  * Cohen et al. [2017] J. Cohen, J.-S. Dibangoye, and A.-I. Mouaddib.  Open decentralized pomdps.  In _2017 IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI)_ , pages 977–984. IEEE, 2017.
  * Corah and Michael [2017] M. Corah and N. Michael.  Efficient online multi-robot exploration via distributed sequential greedy assignment.  In _Robotics: Science and Systems_ , volume 13, 2017.
  * Cybenko and Hallman [2021] G. Cybenko and R. A. Hallman.  Attritable multi-agent learning.  In _Disrupt. Sci. Technol. V_ , volume 11751, page 117510L. International Society for Optics and Photonics, 2021.
  * Czechowski and Oliehoek [2020] A. Czechowski and F. A. Oliehoek.  Decentralized mcts via learned teammate models.  In _IJCAI_ , pages 450–456, 2020.
  * Dinelli et al. [2023] C. Dinelli, J. Racette, M. Escarcega, S. Lotero, J. Gordon, J. Montoya, C. Dunaway, V. Androulakis, H. Khaniani, S. Shao, et al.  Configurations and applications of multi-agent hybrid drone/unmanned ground vehicle for underground environments: A review.  _Drones_ , 7(2):136, 2023.
  * Dorri et al. [2018] A. Dorri, S. S. Kanhere, and R. Jurdak.  Multi-agent systems: A survey.  _Ieee Access_ , 6:28573–28593, 2018.
  * Eck et al. [2020] A. Eck, M. Shah, P. Doshi, and L.-K. Soh.  Scalable decision-theoretic planning in open and typed multiagent systems.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 7127–7134, 2020.
  * Garivier and Moulines [2011] A. Garivier and E. Moulines.  On upper-confidence bound policies for switching bandit problems.  In _Algorithmic Learning Theory_ , pages 174–188. Springer, 2011.
  * Goeckner et al. [2023] A. Goeckner, X. Li, E. Wei, and Q. Zhu.  Attrition-aware adaptation for multi-agent patrolling.  _arXiv preprint arXiv:2304.01386_ , 2023.
  * Hanawal and Darak [2021] M. K. Hanawal and S. J. Darak.  Multiplayer bandits: A trekking approach.  _IEEE Transactions on Automatic Control_ , 67(5):2237–2252, 2021.
  * Hart and Mas-Colell [2000] S. Hart and A. Mas-Colell.  A simple adaptive procedure leading to correlated equilibrium.  _Econometrica_ , 68(5):1127–1150, 2000.
  * Kakarlapudi et al. [2022] A. Kakarlapudi, G. Anil, A. Eck, P. Doshi, and L.-K. Soh.  Decision-theoretic planning with communication in open multiagent systems.  In _Uncertainty in Artificial Intelligence_ , pages 938–948. PMLR, 2022.
  * Kavraki et al. [1996] L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars.  Probabilistic roadmaps for path planning in high-dimensional configuration spaces.  _IEEE Trans. Robot. Automat._ , 12(4):566–580, 1996.
  * Kocsis et al. [2006] L. Kocsis, C. Szepesvári, and J. Willemson.  Improved monte-carlo search.  _Univ. Tartu, Estonia, Tech. Rep_ , 1, 2006.
  * Lauri and Oliehoek [2020] M. Lauri and F. Oliehoek.  Multi-agent active perception with prediction rewards.  _NeurIPS_ , 33, 2020.
  * Li et al. [2019] M. Li, W. Yang, Z. Cai, S. Yang, and J. Wang.  Integrating decision sharing with prediction in decentralized planning for multi-agent coordination under uncertainty.  In _IJCAI_ , pages 450–456, 2019.
  * Li et al. [2021] M. Li, Z. Cai, W. Yang, L. Wu, Y. Xu, and J. Wang.  Dec-sgts: Decentralized sub-goal tree search for multi-agent coordination.  In _AAAI_ , volume 35, pages 11282–11289, 2021.
  * Lizzio et al. [2022] F. F. Lizzio, E. Capello, and G. Guglieri.  A review of consensus-based multi-agent uav implementations.  _Journal of Intelligent & Robotic Systems_, 106(2):43, 2022.
  * Marden et al. [2009] J. R. Marden, G. Arslan, and J. S. Shamma.  Cooperative control and potential games.  _IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)_ , 39(6):1393–1407, 2009.
  * Nemhauser et al. [1978] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher.  An analysis of approximations for maximizing submodular set functions—i.  _Mathematical programming_ , 14(1):265–294, 1978.
  * Nguyen et al. [2023] D. Nguyen, L. White, and H. Nguyen.  Social optimum equilibrium selection for distributed multi-agent optimization.  _arXiv preprint arXiv:2307.13242_ , 2023.
  * Nguyen et al. [2022] N. Nguyen, D. Nguyen, J. Kim, G. Rizzo, and H. Nguyen.  Multi-agent data collection in non-stationary environments.  In _IEEE 23rd WoWMoM_ , pages 120–129. IEEE, 2022.
  * Oliehoek and Amato [2016] F. A. Oliehoek and C. Amato.  _A concise introduction to decentralized POMDPs_.  Springer, 2016.
  * Pineau et al. [2003] J. Pineau, G. Gordon, and S. Thrun.  Point-based value iteration: An anytime algorithm for pomdps.  _IJCAI_ , 3:1025–1032, 2003.
  * Qu et al. [2019] G. Qu, D. Brown, and N. Li.  Distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions.  _Automatica_ , 105:206–215, 2019.
  * Rezazadeh and Kia [2023] N. Rezazadeh and S. S. Kia.  Distributed strategy selection: A submodular set function maximization approach.  _Automatica_ , 153:111000, 2023.
  * Rosenski et al. [2016] J. Rosenski, O. Shamir, and L. Szlak.  Multi-player bandits–a musical chairs approach.  In _International Conference on Machine Learning_ , pages 155–163. PMLR, 2016.
  * Satsangi et al. [2018] Y. Satsangi, S. Whiteson, F. A. Oliehoek, and M. T. Spaan.  Exploiting submodular value functions for scaling up active perception.  _Autonomous Robots_ , 42(2):209–233, 2018.
  * Seuken and Zilberstein [2011] S. Seuken and S. Zilberstein.  Memory-bounded dynamic programming for dec-pomdps.  In _IJCAI Proceedings-International Joint Conference on Artificial Intelligence_ , volume 22, page 2009–2015, 2011.
  * Sewak [2019] M. Sewak.  _Deep reinforcement learning_.  Springer, 2019.
  * Shani et al. [2013] G. Shani, J. Pineau, and R. Kaplow.  A survey of point-based pomdp solvers.  In _Autonomous Agents and Multi-Agent Systems_ , page 353–386. Springer, 2013.
  * Spaan et al. [2006] M. T. Spaan, G. J. Gordon, and N. Vlassis.  Decentralized planning under uncertainty for teams of communicating agents.  In _AAMAS_ , pages 249–256, 2006.
  * Trodden [2009] P. A. Trodden.  _Robust distributed control of constrained linear systems_.  PhD thesis, University of Bristol, 2009.
  * Williams et al. [2014] R. Williams, B. Konev, and F. Coenen.  Multi-agent environment exploration with ar. drones.  In _Advances in Autonomous Robotics Systems: 15th Annual Conference, TAROS 2014, Birmingham, UK, September 1-3, 2014. Proceedings 15_ , pages 60–71. Springer, 2014.
  * Wolpert et al. [2013] D. H. Wolpert, S. R. Bieniawski, and D. G. Rajnarayan.  Probability collectives in optimization.  _Handbook of Statistics_ , 31:61–99, 2013.
  * Xie and Liu [2017] J. Xie and C.-C. Liu.  Multi-agent systems and their applications.  _Journal of International Council on Electrical Engineering_ , 7(1):188–197, 2017.
  * Yao et al. [2020] X. Yao, X. Wang, F. Wang, and L. Zhang.  Path following based on waypoints and real-time obstacle avoidance control of an autonomous underwater vehicle.  _Sensors_ , 20(3):795, 2020.
  * Zhang et al. [2021] K. Zhang, Z. Yang, and T. Başar.  Multi-agent reinforcement learning: A selective overview of theories and algorithms.  _Handbook of Reinforcement Learning and Control_ , pages 321–384, 2021.

##  Appendix A Technical Results

###  A.1 Details of Discounted Upper Confidence Bound on Tree (D-UCT)

Consider an arbitrary node $s$ with a set of child nodes $\mathcal{A}_{n}(s)$.
Whenever $s$ is visited, the child node $s^{\prime}\in\mathcal{A}_{n}(s)$ with
the largest D-UCB is chosen as

$a_{n}^{(t)}(s)=\operatorname*{arg\,max}_{s^{\prime}\in\mathcal{A}_{n}(s)}X_{n}^{(t)}(s^{\prime})\
,$ (8)

where $X_{n}^{(t)}(s^{\prime})$ is the D-UCB score for node $s^{\prime}$ at
iteration $t$. $X_{n}^{(t)}(s^{\prime})$ is updated using the D-UCB algorithm
[19] as follows.

First, let $\gamma\in(1/2,1)$ be a discounting factor and $C_{p}>1\sqrt{8}$ an
exploration constant, the upper bound confidence for child node $s^{\prime}$
is calculated as

$X_{n}^{(t)}(s^{\prime},\gamma)\coloneqq\bar{F}_{n}^{(t)}(s^{\prime},\gamma)+c_{n}^{(t)}(s^{\prime},\gamma)\
,$ (9)

where $\bar{F}_{n}^{(t)}(s^{\prime},\gamma)$ is the average empirical reward
for choosing $s^{\prime}$, and $c_{n}^{(t)}(s^{\prime},\gamma)$ is the
exploration bonus.

Denote the discounted number of times the child node $s^{\prime}$ of the
parent node $s$ has been visited as

$N_{n}^{(t)}(s^{\prime},\gamma)\coloneqq\sum\nolimits_{\tau=1}^{t}\gamma^{t-\tau}\textbf{1}_{\left\\{a_{n}^{(\tau)}(s)=s^{\prime}\right\\}}\
,$ (10)

where $\textbf{1}_{\left\\{a_{n}^{(\tau)}(s)=s^{\prime}\right\\}}$ is the
indicator function that returns $1$ if node $s^{\prime}$ was selected at round
$\tau$ and $0$ otherwise.

Let $F_{n}^{(\tau)}$ be the rollout score at iteration $\tau\leq t$ and
$N_{n}^{(t)}(s,\gamma)$ be the discounted number of times the parent node $s$
has been visited. Then at time $t$, the average reward for node $s^{\prime}$
is computed as

$\bar{F}_{n}^{(t)}(s^{\prime},\gamma)=\frac{1}{N_{n}^{(t)}(s^{\prime},\gamma)}\sum\nolimits_{\tau=1}^{t}\gamma^{t-\tau}F_{n}^{(\tau)}\
\textbf{1}_{\left\\{a_{n}^{(\tau)}(s)=s^{\prime}\right\\}},$ (11)

and exploration bonus as

$c_{n}^{(t)}(s^{\prime},\gamma)=2C_{p}\sqrt{\frac{\log
N_{n}^{(t)}(s,\gamma)}{N_{n}^{(t)}(s^{\prime},\gamma)}}.$ (12)

###  A.2 Analysis of Dec-MCTS Performance in Attrition Settings

As shown in [7], Dec-MCTS has vanishing regret and converges as
$t\rightarrow\infty$. We prove here the behavior of Dec-MCTS after
convergence. Recall that by convergence we mean each agent stays with the same
action sequence (i.e., the UCB score for each action in such sequence is the
highest at that corresponding decision node).

Assume that Dec-MCTS converges at iteration $\tau_{0}$ (finite) for all
agents. At iteration $t>\tau_{0}$, let $x^{*}_{n}$ denote the converged action
sequence of agent $n$, and $x^{*}_{-n}$ denotes the converged action sequences
of every other agent except agent $n$. The rollout score received by agent $n$
for executing the action sequence $x^{*}_{n}$ given by the _marginal utility_
will then be a constant $L$:

$F_{n}^{(t)}(x^{*}_{n})=U_{n}(x^{*}_{n},x^{*}_{-n})=U_{g}(x^{*}_{n},x^{*}_{-n})-U_{g}(x^{*}_{-n})=L\
.$ (13)

Assume that at the next iteration $t+1$, a subset of agents becomes
unavailable due to failures. Let $x^{\prime}_{-n}$ be the combined sequences
of actions taken by all agents except agent $i$ and the lost agents. That is

$x^{\prime}_{-n}\subseteq x^{*}_{-n}.$

and the rollout score agent $i$ receives for the same action sequence now is

$F_{n}^{(t+1)}(x^{*}_{n})=U_{n}(x^{*}_{n},x^{\prime}_{-n})=U_{g}(x^{*}_{n},x^{\prime}_{-n})-U_{g}(x^{\prime}_{-n})\
.$ (14)

######  Lemma 3.

Assume that the Dec-MCTS algorithm has converged on all the agents at time
step $\tau_{0}$ and that the global objective function $U_{g}$ is submodular.
Then

$X_{n}^{(t+1)}(x^{*}_{n},\gamma)\geq X_{n}^{(t)}(x^{*}_{n},\gamma),\ \forall
t\geq\tau_{0}.$

Lemma 3 essentially states that once Dec-MCTS converges, the D-UCB score
calculated by agent $n$ for its converged action sequence $x_{n}$ is non-
decreasing even if it detects that some of the other agents have failed.
Hence, it always picks and updates the same action sequence (i.e., the series
of actions that has the highest D-UCB scores at each corresponding decision
node).

Let $c,p\in x^{*}_{n}$ be two nodes in the converged action sequence of agent
$i$, with $c$ being the child node of $p$. After the algorithm converges at
iteration $\tau_{0}$, by definition, the nodes $c$ and $p$ are going to be
selected repeatedly. Thus, at iteration $t$, the discounted number of times
$c$ is visited can be written as

$\displaystyle\begin{aligned} N^{(t)}_{n}(c,\gamma)&=\gamma^{t-\tau_{0}}\
N^{(\tau_{0})}_{c}+\sum_{\tau=0}^{t-\tau_{0}}\gamma^{\tau}\\\
&=\gamma^{t-\tau_{0}}\
N^{(\tau_{0})}_{c}+\frac{1-\gamma^{t-\tau_{0}+1}}{1-\gamma},\end{aligned}$
(15)

with the constant $N^{(\tau_{0})}_{c}$ is the discounted number of times node
$c$ is chosen at $\tau_{0}$. In addition, the discounted number of times $p$
is visited at iteration $t$ is

$\displaystyle\begin{aligned} N^{(t)}_{n}(p,\gamma)&=\gamma^{t-\tau_{0}}\
N^{(\tau_{0})}_{p}+\sum_{\tau=0}^{t-\tau_{0}}\gamma^{\tau}\\\
&=\gamma^{t-\tau_{0}}\
N^{(\tau_{0})}_{p}+\frac{1-\gamma^{t-\tau_{0}+1}}{1-\gamma},\end{aligned}$
(16)

with the constant $N^{(\tau_{0})}_{p}$ is the discounted number of times node
$p$ is chosen at $\tau_{0}$. Finally, the accumulated rollout score for $c$ at
iteration $t$ is

$\displaystyle\begin{aligned}
\sum_{\tau=1}^{t}\gamma^{t-\tau}F^{(\tau)}_{n}\textbf{1}_{\left\\{a_{n}^{(\tau)}(p)=c\right\\}}&=\gamma^{t-\tau_{0}}F^{(\tau_{0})}+L\
\sum_{\tau=0}^{t-\tau_{0}}\gamma^{\tau}\\\
&=\gamma^{t-\tau_{0}}F^{(\tau_{0})}+L\
\frac{1-\gamma^{t-\tau_{0}+1}}{1-\gamma}\ ,\end{aligned}$ (17)

with the constant $F^{(\tau_{0})}$ is the accumulated rollout score for $c$ at
$\tau_{0}$, and $L$ is the rollout score for $c$ at every iterations up to
$\tau_{0}$ as given in (13). For brevity of notations, we denote the following
values

$\displaystyle\begin{aligned} &N_{c}=\gamma^{t-\tau_{0}}\
N^{(\tau_{0})}_{c}+\frac{1-\gamma^{t-\tau_{0}+1}}{1-\gamma},\\\
&N_{p}=\gamma^{t-\tau_{0}}\
N^{(\tau_{0})}_{p}+\frac{1-\gamma^{t-\tau_{0}+1}}{1-\gamma},\\\
&F_{c}=\gamma^{t-\tau_{0}}\ F^{(\tau_{0})}+L\
\frac{1-\gamma^{t-\tau_{0}+1}}{1-\gamma},\\\
&A=F_{n}^{(t+1)}(x^{*}_{n}).\end{aligned}$ (18)

At iteration $t+1$ when failures occur, the values for the discounted numbers
of times node $c$ and $p$ are chosen, and the accumulated rollout score for
$c$ can be updated as

$\displaystyle\begin{aligned} &N^{(t+1)}_{n}(c,\gamma)=N_{c}+\gamma^{t},\\\
&N^{(t+1)}_{n}(p,\gamma)=N_{p}+\gamma^{t},\\\
&\sum_{\tau=1}^{t+1}\gamma^{t+1-\tau}F^{(\tau)}_{n}\textbf{1}_{\left\\{a_{n}^{(\tau)}(p)=c\right\\}}=F_{c}\
\gamma+A\ ,\end{aligned}$ (19)

with $A$ is the rollout score for $c$ at iteration $t+1$ as given above. The
inequality of Lemma 3 now can be written as

$\displaystyle\begin{aligned}
&\frac{F_{c}\gamma+A}{N_{c}+\gamma^{t}}+c_{p}\sqrt{\frac{2\log(N_{p}+\gamma^{t})}{N_{c}+\gamma^{t}}}\geq\frac{F_{c}}{N_{c}}+c_{p}\sqrt{\frac{2\log(N_{p})}{N_{c}}}\\\
\Leftrightarrow&\frac{F_{c}\gamma+A}{N_{c}+\gamma^{t}}-\frac{F_{c}}{N_{c}}&\\\
&+c_{p}\left(\sqrt{\frac{2\log(N_{p}+\gamma^{t})}{N_{c}+\gamma^{t}}}-\sqrt{\frac{2\log(N_{p})}{N_{c}}}\right)\geq
0.\end{aligned}$ (20)

Let

$f(t)=\frac{F_{c}\gamma+A}{N_{c}+\gamma^{t}}-\frac{F_{c}}{N_{c}}+c_{p}\left(\sqrt{\frac{2\log(N_{p}+\gamma^{t})}{N_{c}+\gamma^{t}}}-\sqrt{\frac{2\log(N_{p})}{N_{c}}}\right)$
(21)

be a funtion of time $t$ over the set of fixed paramters
$\\{\gamma,c_{p},F_{c},N_{c},N_{p}\\}$.

It can be verified that $f(t)$ is an increasing function as the derivative of
$f(t)$ is positive for $t\gg\tau_{0}$. In addition, as $t\gg\tau_{0}$, the
inequality of (20) becomes:

$\displaystyle\begin{aligned}
\frac{F_{c}\gamma+A}{N_{c}}&\geq\frac{F_{c}}{N_{c}}\\\
\Leftrightarrow\quad\quad\quad A&\geq
F_{c}(1-\gamma)=\left(\gamma^{t-\tau_{0}}F^{(\tau_{0})}+L\frac{1-\gamma^{t-\tau_{0}+1}}{1-\gamma}\right)(1-\gamma)\\\
\Leftrightarrow\quad\quad\quad A&\geq L.\end{aligned}$

The last inequality follows from the assumption that the global utility
function $U_{g}$ is submodular. That is, having failures as time $t+1$ implies
there are fewer agents collecting rewards, hence the local utility for agent
$i$ increases (or remains the same). Thus $A\geq L$.

Since Proposition 1 gives that $F_{n}^{\tau+1}(x^{*}_{n})\geq
F_{n}^{\tau}(x^{*}_{n})$, there exists a $\tau_{0}$ for which $f(t)$ is non-
negative for some $t\gg\tau_{0}$. This implies the UCB scores for each node in
the actions sequence $x^{*}_{n}$ will remain the highest. Thus, agent $i$ will
continue to select $x^{*}_{n}$ after failures. This concludes the proof.

Figure 4: Diamonds collection game (a), number of diamonds collected (b), and
D-UCB score for each action of Agent 1 (c).

Let’s illustrate the significant implication of the lemma through an example.
Consider a grid-world diamonds collection game [41], where two agents play in
a team using Dec-MCTS. An exploration factor $C_{p}$ and a discounting factor
$\gamma$ for Dec-MCTS are chosen as $0.5$ and $0.75$ respectively. As shown in
Figure 4, when simulating the game we see that the D-UCB scores for Agent 1
fluctuate until it converges to $\\{0.4607,0.5072\\}$ (after $135$ iterations
in our example). The empirical average reward of _Go Right_ is estimated by
Agent 1 by dividing its contribution (one diamond) to the global utility ($11$
diamonds), while the discounted number of visits is approximately $4$,
yielding the asymptotic score of $0.5072$. The D-UCB score for _Go Down_ (the
sub-optimal action) is non-deterministic depending on the random choices made
by the two agents during the initial transient. This value is not updated in
convergence as that branch of the search tree is not sampled, due to the MCTS
selection policy.

Using the marginal contribution as the utility improves stability and
convergence speed, but it causes issues when agents fail, as shown. At
iteration $150$, Agent 2 fails (or leaves the game). In this case, even if the
optimal choice for Agent 1 would be _Go Down_ (due to the higher amount of
diamonds), it sticks with _Go Right_. This happens because both the
exploration bonus and the local contribution to the overall _hypothetical
global reward_ remain the same, despite the real global reward has been
reduced.

##  Appendix B Proof of Theorem 1

Before going through the proof of Theorem 1, we first prove the existence of
at least one PSNE in the formulated game.

######  Lemma 4.

A finite coordination game will always have at least one PSNE, if maximizing
players’ local utilities corresponds to maximizing the global objective, i.e.,
the players’ local utility functions satisfy, $\forall
x_{n},x^{\prime}_{n}\in\hat{\mathcal{X}}_{n},\ \forall
x_{-n}\in\hat{\mathcal{X}}_{-n},\ \forall n\in\mathcal{N}\ ,$

$U_{n}(x_{n},x_{-n})-U_{n}(x^{\prime}_{n},x_{-n})>0\ \Rightarrow\
\Phi(x_{n},x_{-n})-\Phi(x^{\prime}_{n},x_{-n})>0\ ,$ (22)

where $\Phi(\cdot)$ is a function that represents the global objective.

###### Proof.

Every finite coordination game in which the global objective function is
aligned with the local utility functions of the players, that is, satisfies
the property as in (22), is a generalized ordinal potential game [30]. Let
$\phi$ be a potential function of a coordination game $\mathcal{G}$. Then the
equilibrium set of $\mathcal{G}$ corresponds to the set of local maxima of
$\phi$. That is, an action profile $x=(x_{n},x_{-n})$ is a NE point for
$\mathcal{G}$ if an only if for every $n\in\mathcal{N}$,

$\phi(x)\geq\phi(x^{\prime}_{n},x_{-n}),\ \forall
x^{\prime}_{n}\in\hat{\mathcal{X}}_{n}\ .$

Consider $x^{*}=(x_{n}^{*},x_{-n}^{*})\in\hat{\mathcal{X}}$ for which
$\phi(x^{*})$ is maximal (which is true by definition for a finite set
$\hat{\mathcal{X}}$), then for any $x^{\prime}=(x_{n}^{\prime},x_{-n})$:

$\phi(x_{n}^{*},x_{-n}^{*})>\phi(x^{\prime}_{n},x_{-n})\Leftrightarrow
U_{n}(x_{n}^{*},x_{-n}^{*})>U(x^{\prime}_{n},x_{-n})\ .$

Hence, the game possesses a pure strategy NE. ∎

We now proceed with the main proof. It is well known that, for any finite
matrix game, if all players apply the same Regret Matching policy the
empirical distribution of all players’ joint action converges to the set of
Coarse Correlated Equilibria (CCE) [22]. We prove a stronger result of
convergence to a PSNE under the assumption of submodular utility functions.

As we formulate the problem of multi-agent information gathering as
maximization of a submodular function, the considered matrix game generated by
the active agents and their corresponding sets of best feasible paths at each
decision point satisfies the following two properties:

  * •

_Property 1_ : $\displaystyle\sum_{n\in\mathcal{N}}\lambda_{n}\ U_{n}(x)$ is
concave in $x$,

  * •

_Property 2_ : $U_{n}(x_{n},x_{-n})$ is convex in $x_{-n}$,

where $x:=(x_{n},x_{-n})$ denotes a pure joint action in which agent $n$
chooses path $x_{n}$ and the other agents select $x_{-n}$. The combination of
the two properties implies that player $n$’s local utility function
$U_{n}(\cdot)$ is concave in $x_{n}$ given $x_{-n}$ is fixed.

Let $x$ be a CCE of the considered game, and let
$\bar{x}=\mathbf{E}_{\pi}\left[x\right]$, we then prove that $\bar{x}$ is a
pure strategy NE of the game. Without loss of generality, assume that
$\lambda_{n}=1,\ \forall n\in N$. As $x$ is a CCE point, it satisfies

$\mathbf{E}\left[U_{n}(x)\right]\geq\mathbf{E}\left[U_{n}(x_{n}^{\prime},x_{-n})\right]\
,$ (23)

for every $n\in N$ and every action $x_{n}^{\prime}\in\hat{\mathcal{X}}_{n}$.
Also, since $\bar{x}\in\hat{\mathcal{X}}$, using Property 2 we have

$\mathbf{E}\left[U_{n}(x_{n}^{\prime},x_{-n}\right]\geq
U_{n}\big{(}x_{n}^{\prime},\mathbf{E}\left[x_{-n}\right]\big{)}=U_{n}(x_{n}^{\prime},\bar{x}_{-n})\
.$ (24)

Combining (23) and (24) yields

$\mathbf{E}\left[U_{n}(x)\right]\geq U_{n}(x_{n}^{\prime},\bar{x}_{-n})\ .$
(25)

Replacing $x_{n}^{\prime}=\bar{x}_{n}$ and then summing over all $n\in N$

$\sum_{n\in N}\mathbf{E}\left[U_{n}(x)\right]\geq\sum_{n\in
N}U_{n}(\bar{x}_{n},\bar{x}_{-n})=\sum_{n\in N}U_{n}(\bar{x}).$

Using Property 1 implies

$\sum_{n\in N}\mathbf{E}\Big{[}U_{n}(x)\Big{]}=\mathbf{E}\left[\sum_{n\in
N}U_{n}(x)\right]\leq\sum_{n\in N}U_{n}\Big{(}\mathbf{E}\left[x\right]\Big{)}\
.$

Therefore

$\sum_{n\in N}\mathbf{E}\Big{[}U_{n}(x)\Big{]}=\sum_{n\in N}U_{n}(\bar{x})\ .$

Thus, $U_{n}(\bar{x})=\mathbf{E}\left[U_{n}(x)\right]$ for every $n$, and (25)
becomes

$U_{n}(\bar{x})\geq U_{n}(x_{n}^{\prime},\bar{x}_{-n})\ .$

for every $x^{\prime}_{n}\in\hat{\mathcal{X}}_{n}$. Therefore, $\bar{x}$ is a
pure Nash equilibrium. This implies that the time average of the joint action
of all players converges to a PSNE solution.

##  Appendix C Further Analysis of Regret Matching Coordination Algorithm

###  C.1 Rationale behind Nash equilibrium solution

Nash equilibrium is particularly useful in situations where agents have
incomplete information about the strategies of other agents, i.e.,
coordination when agents can not maintain perfect communication. In such
cooperative situations with limited communication, NE provides an effective
way to find a set of strategies for each agent that is robust to uncertainty
and incomplete information. In a Nash solution, no agent can improve its
outcome by unilaterally deviating from the NE strategy. Thus, NE is a stable
outcome for the agents involved in the planning process where all the agents
share the same common objective. Yet, a remaining challenge is that there
often exists multiple Nash equilibria and thus how to make sure the
combination of these individual Nash-based strategies, which each agent
independently computes, defines an optimal equilibrium. The selection of a
good Nash equilibrium among the many options, known as an equilibrium
selection problem, remains an open question for further investigation. Within
the scope of this work, to address this dilemma, we propose that the agents
synchronize their reached Nash points to identify the most payoff-dominant
Nash solution. The agents then simply follow the best computed Nash
equilibrium to select their decisions. In Appendix D, we demonstrate via
extensive simulation results that our approximate Nash-based approach achieves
an overall good efficiency compared to the optimal solution and substantially
improves over the main competing approaches, both in terms of convergence
speed and global utility achieved.

Figure 5: Evolution over the mission of the Instantaneous Reward Coverage (IRC) in the _Forced Failure_ setting for different times of attrition: no attrition (a), attrition after 2 actions (b), attrition after 4 actions (c), and attrition after 6 actions (d). Results are with $95\%$ confidence. Table 1: Optimality analysis of regret matching. | Number of Agents | Number of Components | Actions per Component
---|---|---|---
| 2 | 3 | 4 | 5 | 6 | 10 | 11 | 12 | 13 | 14 | 7 | 9 | 11 | 13 | 15
PFO (%) | 90 | 85 | 65 | 45 | 40 | 45 | 40 | 45 | 45 | 40 | 65 | 40 | 40 | 30 | 50
RNO | 0.97 | 0.96 | 0.97 | 0.97 | 0.97 | 0.97 | 0.97 | 0.98 | 0.98 | 0.97 | 0.98 | 0.97 | 0.98 | 0.98 | 0.98

###  C.2 The distributed and parallel execution of Regret Matching

In multi-agent systems where agent loss and unreliable communication are
expected to occur, a single point of failure is often unacceptable. Moreover,
a centralized approach that requires a global view of the game is often
intractable due to the exponential growth of the game’s size and complexity.
Therefore, we devise a distributed approach for executing the coordination
algorithm. In our approach, when an agent experiences a loss of communication
with other teammates, the agent can predict the other agent’s behaviors by
simulating their decision choices according to the information received
previously. However, when communication loss occurs repeatedly over a certain
number of times, it is treated as an agent attrition situation and the
remaining agents simply form a new game in which the set of players only
contains the active agents. On the one hand, the distributed execution of RM
allows the players to independently learn and adapt their strategies based on
local information, without the need for a central authority or synchronous
communication. On the other hand, the parallel execution of RM (the agents
execute the same algorithms in parallel) helps by exploring different NE
possibilities to avoid local optima and identify the most payoff-dominant one.

###  C.3 Computational complexity of Algorithm 2

Regret Matching was proven to guarantee a convergence rate of
$\mathcal{O}(1/\sqrt{(}T)$ after $T$ iterations [22]. We discuss here how
Algorithm 2 scales concerning the size of the problem and the number of
available actions for each agent to choose from. For matrix games, where each
player has a finite set of actions and the payoffs are given by a matrix, the
RM algorithm can be implemented in polynomial time. Specifically, a matrix
game with $N$ players and at most $M$ actions per player has $M^{N}$ action
combination in total. Each player has one local utility (or payoff) for each
action combination and thus it requires $N\times M^{N}$ integer numbers to
represent all possible players’ utilities. Therefore, as the number of players
and the number of actions per player increase, the size of the game tree grows
exponentially, making it intractable to compute the entire tree in memory or
time using a centralized approach.

In contrast, using our proposed distributed approach as presented in Algorithm
2, the computational complexity required for the computation of an NE solution
is reduced significantly. In particular, at each learning time step, each RM
player learns only its utility vector (of size at most equal to $M$) for
updating its action decision policy in the next time step. As a result, the
total amount of queries overtime required by each player to run the algorithm
will scale according to $\mathcal{O}(M\times T)$, where $T$ is the number of
iterations until convergence. Note that in the implementation of our proposed
approach, each agent has to do the same calculations for other simulated
players. Thus, the total computational complexity of our solution would scale
as $\sim\mathcal{O}(N\times M\times T)$, which is linearly proportional to the
number of agents, the number of agent’s actions, and the number of iterations
until convergence. Consequently, our proposed approach can converge to a NE
solution in a distributed and scalable way, making it more suitable,
effective, and practical in real-world scenarios, where the players may have
access to different and asynchronous information.

##  Appendix D Additional Experimental Resuls

###  D.1 Time of Attrition Analysis

To perform a baseline evaluation of our algorithm, we consider a setting with
no attrition and measure the task performance in terms of instantaneous reward
coverage throughout the mission. As shown in Fig. 5a, under this static
environment, although the IRC of A-MCTS appeared to be less than Dec-MCTS
initially, it ended up comparable and even slightly outperformed the state-of-
the-art at the end of the mission. This shows that our proposed algorithm can
discover paths that guarantee more long-term rewards and thus is also a good
fit for multi-agent coordinated information gathering in general settings.

To evaluate our algorithm’s adaptability to failures, we considered the
_Forced Failure_ setting, in which after a specific number of actions have
been taken, half of the agents (chosen at random) become unavailable.
Specifically, Fig. 5b, c, and d shows the instantaneous reward coverage with
attrition at the early stage (e.g., after 2 actions), middle stage (e.g.,
after 4 actions), and later stage (e.g., after 6 actions) of the mission
respectively. As these figures show, resetting the tree for replanning
produced no significant benefits compared to those that adopted the same tree.
This is because every MCTS process starts with the exploration phase where
agents intentionally take random actions to learn the reward distribution. As
such, resetting the tree without sufficient planning would cause the produced
joint policy from this period to be sub-optimal. In addition, as Dec-MCTS uses
the _marginal contribution_ as the utility function, it is unable to recognize
the reduction of the global reward and hence is unable to adapt to failures
efficiently. Indeed, the gap between it and Dec-MCTS-Global is halved compared
to the case with no failure. However, using the global utility function alone
is not enough, as sampling other agents’ action sequences introduces a lot of
variance in the estimation of the global utility. By assuming that the
policies of other agents are fixed, both A-MCTS and Greedy-MCTS can overcome
this instability issue and adapt to agent failures better, with A-MCTS
performing the best in all cases as the regret matching method allowing the
agents to discover better joint policies and thus provides better guidance for
the exploration-exploitation of the search tree. It is also interesting to
note that the superiority of A-MCTS compared to Dec-MCTS is slightly reduced
(from $15\%$ to $10\%$) as attrition occurs later. This is expected as when
some agents failed in the final stage of the mission, the remaining agents
would not have enough action budget left to recover the lost rewards.

###  D.2 A Closer Look At Regret Matching Behavior

In this section, we study the optimality of the Nash equilibrium point
computed by the regret matching algorithm in A-MCTS in the context of the
multi-agent underwater data collection problem (Problem 2). We use the
following two metrics to evaluate the performance of our algorithm:

  * •

_Probability of Finding Optimal policy (PFO)_ : Probability that the Nash
policy of our regret matching is optimal in a given setting.

$PFO=\frac{1}{T}\sum_{t=1}^{T}\textbf{1}_{\\{p(t)=p^{*}(t)\\}}$

  * •

_Ratio between Nash policy and Optimal policy (RNO)_ : Ratio between the
utility of the Nash policy of our regret matching and the optimal in a given
setting.

$RNO=\frac{U_{g}(p(t))}{U_{g}(p^{*}(t))}$

The optimal strategy is computed using an exhaustive search algorithm. Table 1
shows the results of this study with a default number of agents of $6$, number
of components per agent of $10$, and number of actions per component of $9$.
As expected, the probability of finding the optimal strategy decreases
significantly when we increase the number of agents. Indeed, with every added
agent, the size of the game increases exponentially, thus potentially causing
regret matching to get stuck at local-optimal points. The same behavior was
not observed when we increased the number of components per agent or the
number of actions per component. Regardless of this, in cases where A-MCTS did
not find the optimal strategy, it still sustainably achieved a ratio of $98\%$
compared to the optimal.