# Decoupled Monte Carlo Tree Search for Cooperative Multi-Agent Planning
## 5 Method
### Decoupled-MCTS
#### 5.2.1 Action Synchronization Problem  
In decoupled-MCTS, if the action selection policy is deterministic, the initial selection of actions generates a limited number of possible combinations to be evaluated by the simulations. As the number of agents and the number of actions increase, the difference becomes larger. This is a huge limitation that hinders the performance of deterministic policies. We showed that the stochastic action selection policies outperformed the deterministic ones due to this problem.  
We used a matrix game, the climbing reward structure of which is shown in Figure 4 for illustrative purposes. There are two agents and each agent has three actions. In decoupled-MCTS, each agent has a table to keep the statistics of each action. Since the matrix game is a single-step planning problem, a table is used instead of a search tree. Note that the action selection is random until all actions are selected at least once. Let us assume that agent 1 chooses \(B_{1}\), \(B_{2}\), and \(B_{3}\) actions and agent 2 chooses \(A_{2}\), \(A_{3}\), and \(A_{1}\) for the first three simulations, respectively. In other words, \(\langle B_{1},A_{2}\rangle\), \(\langle B_{2},A_{3}\rangle\), and \(\langle B_{3},A_{1}\rangle\) action combinations are selected in the first three simulations. According to these selections, the action values are updated as follows: \(B_{1}=-30\), \(A_{2}=-30\), \(B_{2}=6\), \(A_{3}=6\), \(B_{3}=0\), and \(A_{1}=0\). Since each action has some statistics, the next actions are selected based on them. However, a problem arises due to the shared reward. The first selected combinations are synchronized such that their statistics are updated together. For example, when we use UCB1 deterministic action selection policy, agent 1 selects \(A_{3}\) and agent 2 selects \(B_{2}\) since they have the highest UCB1 values. After these actions are selected for some time, the UCB1 explores other actions; agent 1 chooses \(A_{1}\) and agent 2 chooses \(B_{3}\) since they have the second highest values. Finally, agent 1 explores \(A_{2}\) and agent 2 explores \(B_{1}\). As is seen from the action selection pattern, the action combinations that are considered by decoupled-MCTS only consist of the first combinations that are created randomly. Therefore, for that problem, the algorithm only considers three joint action combinations (\(\langle B_{1},A_{2}\rangle\), \(\langle B_{2},A_{3}\rangle\), and \(\langle B_{3},A_{1}\rangle\)) out of nine possible combinations.  
The action synchronization can affect performance in a limited way, depending on the reward structure of the problem. If some combinations of actions result in the same reward, the UCB1 (or any deterministic action selection policy) can randomize the action selection for actions having the same statistics. It can arise directly from the regularities in the reward structure (similar to the attainable matrix game in Figure 4) or from a specific exploration term that equalizes the UCB1 values of the actions at some stage. In the experiments section, we show that the effect of regularities and exploration term on the performance was limited, and deterministic action selection policies performed worse, compared to stochastic action selection policies.  
We evaluated two well-known stochastic selection policies: \(\epsilon\)-greedy and EXP3 in the experiments. Although \(\epsilon\)-greedy is simple and lacks good analytical regret boundaries, it performed better than EXP3 in most of the experiments. We observed that the weight iteration step of EXP3 grew boundlessly and equalized all weights at a very high value in our experiments. We normalized and set a maximum weight value to address this issue,but EXP3 was still behind of \(e\)-greedy. We also found it harder to optimize the exploration parameter of EXP3 compared to \(e\)-greedy.