## 5 Multi Agent Planning Using QMC
### Offline Planning Algorithm--CEMC  
Offline algorithms generate a complete policy before execution begins. The policy specifies what actions to take in any possible runtime situation. Before presenting CEMC, we first introduce two successful techniques used in ICE, which is also adopted by CEMC. The first one is lossless clustering. Two individual action-observation histories \(\theta_{i,a}\), \(\theta_{i,b}\) for agent \(i\) can be losslessly clustered when they satisfy probabilistic equivalence criterion:  
\[\forall\overset{\rightarrow}{\theta}_{\
eq i},\forall s\enspace,\enspace P(s, \overset{\rightarrow}{\theta}_{\
eq i}|\theta_{i,a})\enspace=P(s,\overset{ \rightarrow}{\theta}_{\
eq i}|\theta_{i,b}) \tag{10}\]  
where \(\overset{\rightarrow}{\theta}_{\
eq i}\) is the joint action-observation histories of all agents except agent \(i\). This means that the probability distribution over the other agent's joint action-observation histories are identical for both \(\theta_{i,a}\), \(\theta_{i,b}\). The second one is incremental expansion which defines a method of incrementally constructing a search tree by expanding the most promising child \(\varphi^{t+1}=(\varphi^{t},\beta^{*})\) where \(\beta^{*}\) is the optimal solution of CBGs. A child is selected by node priority. Node \(q\) in the search tree is a 3-tuple \(<\varphi^{t},\vartheta,h>\). Node priority \(q<q^{\prime}\) if:  
\[\left\{ \begin{array}{lcl}\vartheta<\vartheta^{\prime}&,&\text{if }\vartheta \
eq\vartheta^{\prime}\\ h<h^{\prime}&,&\text{otherwise if }h\
eq h^{\prime}\end{array} \right.\enspace. \tag{11}\]  
That is, if the heuristic values are equal, the greater depth will be chosen first. This helps find the tight lower bound early by first expanding deeper nodes and converge quickly. The CEMC algorithm (Algorithm 4) starts planning with an unspecified partial joint policy \(\varphi^{0}\) in an initialized policy pool. It greedily selects the best partial joint policy in the pool according to the node priority(Select(L)). Then, it proceeds by constructing a CBG using lossless clustering (ClusterBG(0)). After that, the CBG is solved, which returns a 2-tupe \(\langle\beta^{t},\hat{V}(\beta^{t})\rangle\) where \(\beta^{t}\) is a Bayesian game policy, and \(\hat{V}(\beta^{t})\) is given by the function Solver():  
\[\hat{V}(\beta^{t})=\sum_{\overset{\rightarrow}{\theta}}P(\overset{ \rightarrow}{\theta}^{t}|b^{0},\varphi^{t})\text{Q}_{\text{MC}}(\overset{ \rightarrow}{\theta}^{t},\beta(\overset{\rightarrow}{\theta}^{t})) \tag{12}\]  
where \(P(\overset{\rightarrow}{\theta}^{t}|b^{0},\varphi^{t})\) is the probability distribution over joint histories and \(\text{Q}_{\text{MC}}(\overset{\rightarrow}{\theta}^{t},\beta(\overset{ \rightarrow}{\theta}^{t}))\) is the Q-value function computed by Algorithm 1. ```
Input: a Dec-POMDP, an empty policy pool \(L\) Output: an optimal joint policy \(\pi^{*}\)
1: Initialize()
2:while\(\
eg\)empty(\(L\))do
3:\(q\leftarrow\) Select(\(L\))
4:\(B(\varphi^{t})\leftarrow\) ClusterBG() //clustering
5:\(\langle\beta^{t},\hat{V}(\beta^{t})\rangle\gets B(\varphi^{t}).\)Solver() //computing \(\text{Q}_{\text{MC}}\) as required
6:\(\text{N}_{\text{IC}}\leftarrow\) IncExp() //incrementally expand nodes
7:\(v^{*}\) = BestValue(\(\text{Q}_{\text{MC}}\)) //return the best \(\text{Q}_{\text{MC}}\) at step \(t\)
8:if depth(\(q\)) = \(h-1\)then
9:\(\langle\pi,v\rangle\leftarrow\) ComputePolicyAndValue(\(N_{\text{IE}}\))
10:if\(v>\underline{v}\)then
11:\(\pi^{*}\leftarrow\pi,\underline{v}\gets v\)
12:\(L.\text{Prune}(\underline{v})\) //pruning the policy pool
13:else
14:\(L.\text{Insert}(N_{\text{IE}})\)
15:\(L.\text{Prune}(v^{*})\) //pruning the policy pool
16: return \(\pi^{*}\)
```  
**Algorithm 4** CEMC  
The set of child nodes \(N_{\text{IE}}\) is expanded using the incremental expansion technique and only the promising child node \(\beta^{t,*}\) will be put into \(N_{\text{IE}}(\text{IncExp}(0))\).