## 4 Monte Carlo Q-Value Function
### QMC  
In reinforcement learning [30], the Q-value function \(Q(s,a)\) is defined as the expected return starting from state \(s\), taking action \(a\), and then following policy \(\pi\):  
\[ \begin{array}{ll}Q^{\pi}(s,a)&=\mathbb{E}_{\pi}[R_{t+1}+\gamma Q^{\pi}(S_{t +1},a^{\prime})|S_{t}=s,A_{t}=a]\\ &=\sum\limits_{s^{\prime}\
eq r}p(s^{\prime},r|s,a)[r+\gamma Q(s^{\prime},a^{ \prime})].\end{array}  \tag{6}\]  
Different from the former, the state in QMC is the joint history \(\overset{\rightarrow}{\theta}_{t}\) at time step \(t\). We define QMC as:  
\[ \begin{array}{ll}\text{Q}_{\text{MC}}(\overset{\rightarrow}{\theta}^{t}, \overset{\rightarrow}{a})=R(\overset{\rightarrow}{\theta}^{t},\overset{ \rightarrow}{a})+\sum\limits_{\overset{\rightarrow}{\theta}^{t+1}\in O}P( \overset{\rightarrow}{\theta}^{t+1}\big{|}\overset{\rightarrow}{\theta}^{t}, \overset{\rightarrow}{a})\max\limits_{\text{MC}(\overset{\rightarrow}{\theta} ^{t+1})}\text{Q}_{\text{MC}}(\overset{\rightarrow}{\theta}^{t+1},\text{MC}( \overset{\rightarrow}{\theta}^{t+1}))\end{array}  \tag{7}\]  
where \(MC\) is the Monte Carlo method, which returns the optimal action \(MC(\overset{\rightarrow}{\theta}^{t+1})\) when observing \(\overset{\rightarrow}{\theta}^{t+1}\). Because of the partially observability, the probability multiplied by QMC is a conditional probability of all observations at \(\overset{\rightarrow}{\theta}_{t}\) and \(\overset{\rightarrow}{a}\). The solution of QMC can be illustrated in Figure 1. The black filled nodes are joint histories, and the solid links and dotted links are respectively joint actions taken and joint observations received by agents. Each joint history node contains two statistical values--\(N(\overrightarrow{\theta})\), visiting count of node \(\overrightarrow{\theta}\) and \(N(\overrightarrow{\theta},\overrightarrow{a})\), number of taking \(\overrightarrow{a}\) at \(\overrightarrow{\theta}\). At the selection phase of QMC, UCB1 is used to choose the best action \(a^{*}\)  
\[a^{*}=\underset{\overrightarrow{a}\in A}{\operatorname{argmax}}\left\{R+ \hat{R}+c\sqrt{\frac{2\ln N(\overrightarrow{\theta})}{N(\overrightarrow{ \theta},\overrightarrow{a})}}\right\} \tag{8}\]  
where \(R\) and \(\hat{R}\) are respectively the immediate and future reward at.., and the term added to it is called a UCT bonus, which is used to balance exploitation and exploration. \(R+\hat{R}\) is the mean value of reward. The \(c\) parameter is a constant (\(c>0\)), which is used to tune how much influence the bonus has on the action selection. It is set bigger for problems with more branches and smaller for deeper ones. We did not consider adaptive setting of parameter \(c\) in this paper. At the expansion phase of QMC, it expands only one node. At the simulation phase, QMC replaces the default random policy with heavy playout--an enhancement of Monte Carlo, which is presented in Section 3.3. At the backpropagation phase, QMC updates the values or statistics of nodes that are visited in this iteration with the result of the finished play. **Lemma 1**. : QMC _is an upper bound of the optimal \(Q\)-value function Q*._  
Proof. : See appendix. \(\square\)  
From the representation of QMC we can see that it treats Dec-POMDPs as models in which a single agent takes joint actions and receives joint observations, but has the same state set \(S\), transition function \(T\), observation function \(O\) and reward function \(R\). The assumption makes more information available than the underlying Dec-POMDPs. QMC is an overestimation of the optimal Q-value function and makes A*-like search find the optimal policy. The pseudocode of computing QMC is shown in Algorithms 1 and 2. Figure 1: Tree of Monte Carlo Q-value function.