# Decoupled Monte Carlo Tree Search for Cooperative Multi-Agent Planning
## 5 Method
### Decoupled-MCTS  
In multi-agent planning, the complexity of the problem increases exponentially in terms of the number of agents. Decoupled-MCTS tackles this problem by planning for each  
Figure 2: On the left, the search tree of UCT with the joint actions. On the right, the search tree of decoupled-MCTS with nodes having different set of actions for each agent separately. agent separately. In the planning phase, each agent becomes the part of the environment from the perspective of the planner agent. All agents are both planner and also part of the environment. They collectively plan using the same simulation runs. In the beginning, each agent would be a noise to other agents, but as the agent converges to a behavior, each agent has a chance to adapt to other agents. Each agent runs a single agent MCTS planning. In the general game-playing domain, this approach works well when the deterministic action selection algorithm is used [2]. All agents get different rewards given the state for these problems. One common example would be zero-sum games, where at each state the sum of the agents' rewards is 0. Although decoupled-MCTS is not the only method, it works well as it reduces the exponential complexity. Cooperative multi-agent problem is a subset of the general game-playing problem. The main difference is that all agents share the same reward and aim to optimize the same performance. This difference has a big effect on the performance of decoupled-MCTS when deterministic action selection policy is used. Due to this limitation, we used stochastic action selection policies, which solve the action synchronization problem where statistics of first combinations of actions are fixed at the beginning (see Section 5.2.1). There are two possible representations for decoupled-MCTS: (1) single search tree and (2) separate search tree. Single search tree differs from single agent MCTS with the representation of actions. At each state node, we have the list of actions available to each agent with their respective statistics and next nodes, as seen in Figure 2. At each action selection, the method selects an action for each agent separately using the statistics, but it expands and moves on the same tree as if it was a single agent MCTS. Separate search tree differs from single search tree by maintaining different search trees for each agent. We have a single agent MCTS search tree for each agent, but action selection and back-propagation is driven by the simulation shared by all agents, as seen in Figure 3. The main advantage of separate search tree is distributed planning where each search tree can be distributed to different computation resource and exchange simulation data as required. Separate search trees also maintain different agent states relevant for Dec-MDP problems that is not in the scope of this paper. However, in this paper, we used the single search tree because we were able to fit search trees in memory and gain efficiency when we combined it to create a search tree over joint action space (see Section 5). At each planning step, decoupled-MCTS obtains the initial state and constructs a search tree starting from that state. The search tree construction is driven by the simulations and each simulation adds a new node. Nodes contain states, lists of actions and next nodes reachable from each action. Nodes also contain different statistics of the actions to use in an action selection algorithm. The main difference between MCTS and decoupled-MCTS is the representation of actions in search nodes. A decoupled-MCTS node has a list of actions for each agent with the relevant statistics. As a result of this change, decoupled-MCTS runs its selection and back-propagation steps for each agent on their action lists. Decoupled-MCTS modifies the action selection and back-propagation steps of the MCTS algorithm. The Algorithm 1 presents the main planner that returns the selected set  
Figure 3: On the left, Decoupled-MCTS with separate search trees for Agent 1 and Agent 2.