# Decoupled Monte Carlo Tree Search for Cooperative Multi-Agent Planning
## 2 Related Work  
There are two main issues in multi-agent planning; coordination and the _curse of dimensionality_. The coordination problem arises when agents execute actions without the knowledge of other agents. In literature, there are three main approaches to handle the coordination problem; coordination-free, coordination-based, and explicit coordination [9]. Coordination-free methods just ignore the problem and assume that the optimal joint action is unique. Coordination-based approaches use the coordination graph to decompose the value function over agents. The value function calculates an expected cumulative reward of the joint state. Explicit coordination mechanisms generally use a social convention or communication to determine a global ordering of agents and their actions [10]. Our method used a coordination-free approach, where we assumed that the optimal joint action was unique. The curse of dimensionality problem results from the Cartesian product of the action sets and state sets of agents. [PERSON] and [PERSON] categorized the cooperative decentralized planning problems in terms of model specializations, and communications [11]. They showed that Decentralized Partially Observable Markov Decision Processes (Dec-POMDP) with independent observation and transition functions have NP-complete complexity and are a lot simpler than the original Dec-POMDP model (NExp-Complete [12]). Even further specializations, such as having a single goal state and uniform cost, reduce the complexity to P-complete [13]. They also showed that having direct communication between agents did not change the complexity class of decision processes. The decision-theoretic model of the problem targeted in this work was the Multi-agent Markov Decision Process (MMDP). The complexity of the MMDP is the same as MDP, except for the exponential increase in the action and state space. MMDP problems have the _curse of dimensionality_ due to the number of agents. Therefore, we attacked the _curse of dimensionality_ problem by representing every agent as an independent planner. However, representing every agent as an independent planner required a special mechanism to solve the coordination problem [1,14]. [PERSON] and [PERSON] presented a decentralized reinforcement learning algorithm for deterministic multi-agent domains [15] where the coordination problem was solved using a special mechanism. The algorithm made use of the deterministic nature of the problem, such that agents could infer other agents' actions using the next state and reward that was observable. However, every agent iteratively improved its policy and achieved coordination via updating its policy only in the case of improvement. That eliminated the accumulation of two or more actions having the same expected sum of rewards, and, therefore, policies chose one of the equilibrium points and solved the coordination problem. [PERSON] et al. proposed another method for a decentralized policy search algorithm for cooperative multi-agent problems [16]. They assumed that agents had local policies that mapped the local states of the agents to the actions. They showed that a decentralized policy search could learn local optimal policies using the gradient descent algorithm. [PERSON] et al. presented the challenges of multi-agent problems in the deep reinforcement learning domain [17]. They listed non-stationarity and coordination under the distributed training of cooperative problems. However, these challenges are also valid for online planning methods, because they use the same mathematical formalism [18]. The value-based reinforcement learning methods address these challenges by summarizing the effect of other agents [19,20]. Another line of research uses a coordination graph [21]to decouple the agents and build a new formalism to describe the _influence_ of agents to each other [22].