# Decoupled Monte Carlo Tree Search for Cooperative Multi-Agent Planning
## 6 Results
### Experimental Setup
#### 6.1.2 MMDP Problems
The exploration constant of the _UCT_ was set as the difference between the maximum and minimum cumulative rewards. Results  
We present the average performance of \(\epsilon-greedy\) and \(EXP3\) action selection policies against _UCT_ for _meeting in grid_ problem in Figure 10. We report the average performance difference as a percentage. We showed that decoupled-MCTS outperformed the standard centralized planning algorithm (UCT) in different grid sizes. We also showed that the performance difference became bigger as the size of the grid and the horizon of the problem increased. As the grid size became bigger the goal state was positioned deeper. It would take more steps for agents to meet, which resulted in performance degradation for the UCT algorithm. As the number of simulations was the same for each grid size, the search tree created would be shallow for _UCT_ compared to decoupled-MCTS, due to the high branching factor of joint actions. When we tested the results for statistical significance using _Mann-Whitney_ with \(p\ \leq\ 0.05\), we saw that \(EXP3\) outperformed _UCT_ method for grid sizes of 3, 5, and 7, and the \(\epsilon-greedy\) outperformed for grid sizes of 6, 8, 9. However, when we compared \(EXP3\) with \(\epsilon-greedy\), the performance difference was not significant, except for the problem with the grid size 7. Based on these results, we could conclude that the decoupled-MCTS method outperformed the central planning as well and we did not have a winner action selection policy for decoupled-MCTS for _meeting in grid_ problem. We present the average performance of \(\epsilon-greedy\) and \(EXP3\) action selection policies against _UCT_ for _fire fighting_ problem in Figure 11. We report the average performance  
Figure 10: The average cumulative reward difference in % over different grid size of _meeting in grid_ problem. 0.0 line represents the performance of _UCT_. The whiskers show the standard error. Figure 9: The average cumulative reward over the action selection policy parameters: \(\epsilon\) and \(\gamma\) in MMDP Problems. (**left**) The fire fighting problem. (**right**) The meeting in grid problem. The whiskers show the standard error. difference as a percentage. In comparison to the _meeting in grid_ problem, _UCT_ outperformed decoupled-MCTS with \(EXP3\) action selection. As we previously observed with problems having a negative reward, \(EXP3\) action selection was severely affected, although we were normalizing the reward to the 0 and 1 range. _UCT_ also had solid performance against decoupled-MCTS with \(\epsilon-greedy\) action selection when there were few houses and the problem horizon was small. However, as the number of houses increased that also increased the horizon, and the performance of the _UCT_ degraded. Similar to _meeting in grid_ problem, as the problem became complex centralized planning suffered from a shallow search tree. In the case of _fire fighting_ problem, there was no goal state, but the number of houses determined the available actions to the agents. When the number of houses increased, the number of actions of decoupled-MCTS search increased linearly, but for UCT it increased exponentially. We tested the results for statistical significance using _Mann-Whitney_ with \(p\ \leq\ 0.05\). We saw that _UCT_ outperformed \(EXP3\) for all problems. This was an unexpected result, since we expected a decrease in the performance of _UCT_ as the problem complexity increased, but we saw that \(EXP3\) was affected by negative rewards. The \(\epsilon-greedy\) outperformed _UCT_ for problems with houses from 10 to 14. Similarly, \(\epsilon-greedy\) had a higher reward than \(EXP3\) for all problems. Based on the results, we could conclude that decoupled-MCTS with \(\epsilon-greedy\) action selection outperformed centralized planning when the complexity of the problem increased. Finally, we stated that \(\epsilon-greedy\) was better than \(EXP3\) action selection policy for decoupled-MCTS.