# Decoupled Monte Carlo Tree Search for Cooperative Multi-Agent Planning
## 5 Method
### Combined Decoupled Monte Carlo Tree Search  
In decoupled-MCTS, we have a coordination problem where agents take actions without knowing which actions were taken by their teammates. Although we have this information, we do not keep or use it in the planning stage because we want to reduce the complexity of the planning. To solve this problem, we propose an improvement over the decoupled-MCTS method. We used decoupled planning to reduce the number of actions available at each node. Once, we completed the decoupled planning, we had good estimations of individual actions of agents. We used this information to construct a search tree over joint actions, but we did not construct all joint actions that would be intractable. We chose joint actions based on the value calculated in decoupled-MCTS planning. Then, we ran another planning stage on this combined search tree using UCT, but we did not add any new nodes to the tree. We were walking on the tree and updating the values of the nodes using rewards collected from new simulation runs. In this way, we improved the performance of overall planning by fine-tuning the joint action evaluations which we might have missed during decoupled planning. In Figure 5, we show how the decoupled-MCTS search tree was used to construct one new search tree having joint actions. In this simple example, we assumed that nodes were created by running five simulations (_sum_ shows the sum of the collected reward and  
Figure 4: Game matrices with different coordination problems: Attainable, penalty, and climbing as presented by [PERSON] et al. [1]. shows the number of visits). There were two agents with actions: \(A_{0}\), \(A_{1}\), and \(B_{0}\), \(B_{1}\). If we chose actions based on the current decoupled evaluations, agent 1 would choose \(A_{1}\) and agent 2 would choose \(B_{0}\). The method uses the statistics from decoupled-MCTS to decide how actions are going to be selected for combining. We sorted individual actions by their selected statistics and chose them to be part of a joint action one by one randomly. This reduced the complexity such that we did not need to construct all possible joint actions. If we used the average cumulative reward as a statistic, in Figure 5, we chose \(A_{1}\) and \(B_{0}\) as the first candidate. Then, to generate the next joint action, we replaced \(B_{0}\) with \(B_{1}\) and kept the \(A_{1}\) as it is. For that example, we randomly chose Agent 2 to update. After the joint actions were selected we calculated their statistics by summing the cumulative rewards of individual actions and dividing that by the total visits to individual actions. The joint action \(A_{1}\), \(B_{0}\) has 4.83 and \(A_{1}\), \(B_{1}\) had 4.8 as the cumulative reward. This ensured that the evaluations of individual actions were used to estimate the cumulative reward of the joint action. We set the visit count to 1. In this way, we could incorporate the statistics of individual actions to preset the initial action selection. However, because we set the visit count to 1, we gave very small weight to our initial evaluation. We limited the number of selected joint actions by the sum of the agents' actions to keep the total number the same as the decoupled one. For example, if one agent had 4 different actions and another agent had 3 different actions, we chose 7 different joint actions from 12 available joint actions. For the example in Figure 5, we chose two joint actions instead of four for illustrative purposes. When we collected statistics for individual actions, we used this data to select joint actions. The statistics of the actions could be used in many ways. We proposed two strategies for the combination of joint actions: (1) using the reward, and (2) using the variance of reward. The strategy of using actions with high expected rewards aimed to reevaluate the best actions to reduce the effect of miscalculation. This would reduce the uncertainty introduced due to miscoordination. However, it would not fix the problem of actions severely penalized due to miscoordination.