# Decoupled Monte Carlo Tree Search for Cooperative Multi-Agent Planning
## 6 Results
### Experimental Setup  
We used the _penalty_ and _climbing_ matrix games, as seen in Figure 4. We replaced \(k\) in _penalty_ problem with different values to study the effect of the penalty amount on the performance. Each repeated matrix game was tested with an episode length of 10. For each decision-making step, we ran 500 simulations. The results were provided over 100 runs. In addition to the matrix games from the literature, we constructed two more matrix games to better illustrate the effect of action synchronization and action combination problems in Figure 6. The _random_ game matrix had randomly unique reward values. The values were less than one for all action combinations, except the reward at \(A6\times B6\). We set the reward of one of the action combinations to 10 to set an optimal action with a clear high reward value. The _negative penalty_ game matrix is an extended version of _penalty_ matrix (see Figure 4). We further added penalties and set them to a unique random value less than \(-100\). We compared \(UCB1\), \(EXP3\), and \(\epsilon-greedy\) action selection policies in decoupled-MCTS. The exploration constant of \(UCB1\) was set to the difference between maximum and minimum reward, as suggested in [33]. The \(\gamma\) and \(\epsilon\) parameter of \(EXP3\) and \(\epsilon-greedy\) selection algorithms were selected by running experiments between 0 and 1. The parameters were searched with a 0.01 increment. We also did not use raw reward for the \(EXP3\) action selection policy. The rewards were used as exponential terms in the probability calculation and that resulted in an intractable calculation when rewards were large. To solve that problem, we scaled the reward to a value between 0 and 1. We used \(UCB1\) to provide a baseline for deterministic action selection policies. Results  
We present the average cumulative reward for each policy in Table 1. The results are provided with standard error. The optimal value of the _climbing_ game matrix was 110, _penalty_ was 100, _random_ was 100, and _negative penalties_ was 100. We observed that the baseline action selection policy (\(UCB1\)) outperformed \(EXP3\) for some of the _penalty_ game  
Figure 6: Random (**left**): A game matrix having an optimal action combination with value 10. Negative penalties (**right**): A game matrix having high penalties for all action combinations in addition to the original penalty game matrix. matrices and the _climbing_ one. Contrary to our expectations, it did not suffer from action synchronization or coordination problems at the level we expected. When we investigated these problems, we saw that some action combinations resulted in the same reward. Some actions had a reward of 0 and some had symmetric values. When these conditions were met, the action selection was randomized for the actions. That randomization helped to loosen the action synchronization problem. We investigated the performances for extended matrix games (see Figure 6) for _random_ and _negative penalties_. As expected, \(UCB1\) suffered from action synchronization problems in both game matrices. The reward structures in these game matrices did not help the deterministic action selection policies to randomize its selection. The \(EXP3\) and \(\epsilon-greedy\) methods were not affected severely. Although there was a small performance loss, this could be attributed to the increase in the complexity of the problem, due to the increase in the number of actions. We saw that \(\epsilon-greedy\) outperformed \(EXP3\) in all problems. The performance difference became bigger as the complexity of the problem increased. In Figure 7, we present the average cumulative reward over the parameters of the action selection policies for penalty k = \(-100\) game matrix. As the parameter value became closer to 1, \(\epsilon-greedy\) and \(EXP3\) made more uniformly random action selections. In other words, they were exploring more. As the exploration increased, the action selection policies converged to the 20 sub-optimal Nash equilibrium.