## 5 Multi Agent Planning Using QMC
### Policy Pruning Strategy  
Pruning is split into hard pruning, which removes branches of the tree permanently, and soft pruning, which temporarily removes branches, but then adds them back into the search at some later point [33]. In this paper, we use hard pruning as our pruning strategy.  
The ICE algorithm maintains a policy pool. A node in the pool is denoted as a tuple \(<\varphi,\hat{v},h>\), where \(\varphi\) is a partial policy, \(\hat{v}\) is its value, and \(h\) is its depth. We know the value of a node is an actual value plus an estimated value: \(\varphi=V^{0..t-1}(\varphi^{t})+\hat{V}(\beta^{t})\). The estimated value \(\hat{V}(\beta^{t})\) is an overestimation of the actual value from this node to a terminal. Actually, the value of a node \(\varphi\) is the value of a path or a policy across this node. Therefore, with the search descending deep down to the terminal or the finite horizon, the value of a node is also descending (note that the actual value becomes larger and larger, and the estimated value becomes close to the actual value). When the search reaches the terminal, the value of the terminal node can be seen as the best lower bound ever found. If the value of a node in the policy pool is smaller than the best lower bound, it would never be the optimal. Therefore, it uses the best lower bound \(\underline{v}\) to prune the policy pool. However, for some problems in the literature, the policy pool shrinks slowly, which wastes a lot of time in computing useless nodes.  
We use an example to illustrate it. Consider, for example, Figure 2 is a search tree. The policy pool is a priority list, which has several nodes, such as \(\{\langle\varphi^{2},10.125,2\rangle,\langle\varphi^{1^{\prime}},10.125,1 \rangle,\langle\varphi^{2^{\prime}},9.721,2\rangle,\langle\varphi^{2^{\prime \prime}},6.182,2\rangle,\dots\ \}\). The superscript of \(\varphi\) is its time step or its depth. At each loop the ICE algorithm chooses the first node in the pool and expands it. If the algorithm reaches the last step, it returns the fully expanded node (\(\langle\varphi^{3},5.363,3\rangle\)) as the best lower bound to prune the policy pool. However, node \(\langle\varphi^{2^{\prime\prime}},6.182,2\rangle>\text{node }\langle\varphi^{3},5.363,3\rangle\) according to the node priority, and it will not be pruned. Assuming that the child of the node \(\varphi^{2^{\prime\prime}}\) is \(\langle\varphi^{3^{\prime}},4.182,3\rangle\), this fully expanded policy is obviously not the optimal one and should have been pruned in advance, but node \(\langle\varphi^{2^{\prime\prime}},6.182,2\rangle\) will be still expanded in these iterations. Not pruning in advance makes the search algorithm go the wrong direction and this is to be solved in our policy pruning strategy.  
Thus, these useless nodes like \(\langle\varphi^{2^{\prime\prime}},6.182,2\rangle\) should be removed as early as possible. We improve the pruning function using the max Q-value function at time step \(t\)\(\text{Q}_{\text{MC}}^{t,*}\), combined with the best lower bound \(\underline{v}\), that is:\[\left\{\begin{array}{ll}\{q\in L|\vartheta>v^{*}\}&,&\text{if }t<h-1\\ \{q\in L|\vartheta>\underline{v}\}&,&\text{if }t=h-1\end{array}\right. \tag{14}\]  
where \(t\) is the deepest level in the policy pool, \(v^{*}\) is computed through \(\text{Q}_{\text{MC}}^{t,*}\):  
\[v^{*}=V^{0..t-1}(\vartheta^{t})+\max_{a}\text{Q}_{\text{MC}}(\overset{\to}{ \theta}^{t},a) \tag{15}\]  
The Equation (14) illustrates that if \(t<h-1\), all nodes with values less than \(v^{*}\) can be pruned and if CEMC reaches the last step, any node with values less than \(\underline{v}\) can be pruned. Note that pruning using \(v^{*}\) is done during the planning, it does not have to wait for full expansion. This technique can reduce the number of nodes in the policy pool and make the algorithm converge quickly, which is tested experimentally in Section 5.