## Appendix A  
**Lemma 1. Proofs**  
We use a Dec-POMDP with \(k\) steps delayed communication model to prove Lemma 1. This model can be denoted as an augmented MDP, which is a reformulation of the prior work [35; 36] and extended to the Dec-POMDP setting [4]. The augmented MDP is defined as \(\hat{M}=<\hat{S},\hat{A},\hat{T},\hat{R}>\), where an augmented state \(\hat{s}\in\hat{S}\) is composed of a joint action-observation history \(\overset{\rightarrow}{\theta}^{t}\) and a joint policy tree \(q^{t}\):  
\[\hat{s}=\left\{ \begin{array}{ll}\overset{\rightarrow}{\langle\theta\,,\,q^ {t}\rangle}&,&0\leq t\leq h-k-1\\ \overset{\rightarrow}{\langle\theta\,,\,q^{\tau=h-t}\rangle}&,&h-k\leq t\leq h -1\end{array} \right. \tag{1}\]  
The contained \(q^{t}\) is a joint depth-\(k\) policy tree \(q^{t}=\langle q^{t}_{1},\ldots,q^{t}_{n}\rangle\) starting from stage \(t\) and \(q^{\tau=h-t}\) is a \(\tau\)-steps-to-go sub-tree policy. For example, if \(k=2\), \(q^{t}\) represents a joint depth-2 policy tree for \(0\leq t\leq h-3\). For \(h-2\leq t\leq h-1\), state \(\hat{s}\) contains \(q^{\tau=2}\) and \(q^{\tau=1}\). An augmented action \(\hat{a}\in\hat{A}\) is a joint policy \(\hat{a}=<\delta^{t+k}_{1},\ldots,\delta^{t+k}_{n}>\) mapping length-\(k\) observation histories to joint actions at stage \(t+k\). The transition model \(\hat{T}\) is a probability \(P(\overset{\rightarrow}{\theta}^{t+1}|\overset{\rightarrow}{\theta}^{t})=P (\overset{\rightarrow}{(\overset{\rightarrow}{\theta}^{t+1}},q^{t+1})| \overset{\rightarrow}{(\overset{\rightarrow}{\theta}^{t}},q^{t}),\delta^{t+k })=P(\overset{\rightarrow}{\theta}^{t+1}|\overset{\rightarrow}{\theta}^{t},q ^{t}(\overset{\rightarrow}{\theta}_{\varnothing}))\) with an empty observation \(\overset{\rightarrow}{\theta}_{\varnothing}\) at stage t, where \(\overset{\rightarrow}{\theta}^{t+1}=\overset{\rightarrow}{(\overset{ \rightarrow}{\theta}^{t},a^{t},o^{t+1})}\), \(q^{t}(\overset{\rightarrow}{\theta}_{\varnothing})\) is an initial joint action at stage \(t\) and \(q^{t+1}=\langle q^{t}\circ\delta^{t+k}\rangle\) meaning appending a policy \(\delta^{t+k}\) to \(q^{t}\). The reward model \(\hat{R}\) is defined as \(\hat{R}(\hat{s})=\hat{R}(\overset{\rightarrow}{(\overset{\rightarrow}{ \theta}^{t}\,,q^{t})})=R(\overset{\rightarrow}{(\overset{\rightarrow}{ \theta}^{t}\,,q^{t}(\overset{\rightarrow}{\theta}_{\varnothing}))})\). Therefore, the optimal Q-value function \(Q_{k}\) for a \(k\)-steps delayed communication model for \(0\leq t\leq h-k-1\) is as follows. \[Q_{k}(\hat{s},\delta^{t+k})=R(\overset{\rightarrow}{\theta}^{t},q^{t}( \overset{\rightarrow}{\theta}_{\varnothing}))+\sum_{o^{t+1}\in O}P(o^{t+1}| \overset{\rightarrow}{\theta}^{t},q^{t}(\overset{\rightarrow}{\theta}_{ \varnothing}))\max_{\delta^{t+k}}Q_{k}(\hat{s}^{t+1},\delta^{t+k}) \tag{2}\]  
For \(h-k\leq t\leq h-1\), there are \(\tau=h-t\) stages to go and the Q-value function is the same as the original one. If \(k=0\), \(q^{t}\) is a depth-0 policy and \(\hat{s}\) reduces to \(\overset{\rightarrow}{(\overset{\rightarrow}{\theta}^{t}\,,\varnothing)}\) or \(\overset{\rightarrow}{\theta}^{t}\), \(\delta^{t+k}\) reduces to \(a^{t}\). Equation (18) reduces to \(Q_{0}(\overset{\rightarrow}{\theta}^{t},a^{t})=R(\overset{\rightarrow}{ \theta}^{t},a^{t})+\sum\limits_{o^{t+1}\in O}P(o^{t+1}|\overset{\rightarrow}{ \theta}^{t},a^{t})\max_{a^{t+1}}Q_{0}(\overset{\rightarrow}{\theta}^{t+1}, a^{t+1})\). Contrasting with Equation (7), we can get that QMC corresponds to the Q-value function \(Q_{0}\) of a 0-delayed communication system. According to the theory of [4], a Dec-POMDP is identical to an \(h\)-steps delayed communication system. The optimal Q-value function \(Q_{k}\) of a Dec-POMDP with \(k\)-steps delayed communication is an upper bound to \(Q_{k+1}\), that of a \(k+1\)-steps delayed communication system.