# Optimal Model-Free Mean-Square Consensus for Multi-Agents with Markov Switching Topology
## 3 Main Results
### Convergence of the PI Algorithm  
**Lemma 2**. : [34] _Considering that (27) and (28), update \(u_{i}^{s}(k)\) and \(V_{i}^{s}(e_{i}(k))\), respectively. For \(\forall i\), if initial policies \(u_{i}^{0}(k)\) are admissible, then, for every iteration step \(s=0,1,2,\ldots\), the policies \(u_{i}^{s}(k)\) retain their permissibility. This implies that they can stabilize the dynamics (8) and ensure the boundedness of the performance functions (16)._  
**Lemma 3**. : _For \(\forall i\) and \(\forall s\), let initial policies be admissible and \(V_{i}^{s}(e_{i}(k))\) and \(u_{i}^{s}(k)\) are iteratively updated via Equations (27) and (28), respectively. Then, \(V_{i}^{s}(e_{i}(k))\) may be found to be monotonically nonincreasing, i.e., \(V_{i}^{s+1}(e_{i}(k))\leq V_{i}^{s}(e_{i}(k))\)._Proof. : Because of \(V_{i}^{s}(e_{i}(k))=\sum_{\tau\in\mathcal{F}}V_{i}^{s}(e_{i}(k),\tau)\cdot Pr\{ \sigma(k)=\tau\}\), we only need to prove that \(V_{i}^{s+1}(e_{i}(k),\tau)\leqslant V_{i}^{s}(e_{i}(k),\tau)\). For \(\forall i\) and \(\forall s\), we build a new performance function \(\Phi_{i}^{s+1}(e_{i}(k)\)\(,\tau)\) as follows:  
\[\Phi_{i}^{s+1}(e_{i}(k),\tau) =r_{E}^{s+1}(e_{i}(k),\tau)+\gamma\sum_{\tau^{\prime}}V_{i}^{s}(e _{i}(k+1),\tau^{\prime})\cdot p_{\tau\tau^{\prime}} \tag{30}\] \[=\min_{u_{i}(k)}\{r_{E}(e_{i}(k),\tau)+\gamma\sum_{\tau^{\prime}} V_{i}^{s}(e_{i}(k+1),\tau^{\prime})\cdot p_{\tau\tau^{\prime}}\}\]  
Based on (28), (29), and (30), we have  
\[\Phi_{i}^{s+1}(e_{i}(k),\tau)\leqslant V_{i}^{s}(e_{i}(k),\tau). \tag{31}\]  
Definition 2 indicates that we have \(e_{i}(k)\to 0\) for any admissible control policies \(u_{i}^{s}(k)\) for \(\forall i\). When the tracking error disappears, the control policies of (1) are also zero; that is, \(u_{i}^{s}(k)\to 0\) as \(k\to\infty\). We know that \(u_{i}^{s+1}(k)\) are also admissible control policies based on Lemma 2. Thus, \(u_{i}^{s+1}(k)\to 0\) as \(k\to\infty\). Let \(k\ =\ q\), where \(q\to\infty\); then, we manage to procure  
\[V_{i}^{s+1}(e_{i}(q),\tau)\ =\ \Phi_{i}^{s+1}(e_{i}(q),\tau)\ =\ V_{i}^{s}(e_{i}(q), \tau),\ \ \forall\tau\in\mathcal{F}. \tag{32}\]  
Let \(k=q-1\). It follows from (28)-(30) that  
\[V_{i}^{s+1}(e_{i}(q-1),\tau) =r_{E}^{s+1}(e_{i}(q-1),\tau)+\gamma\sum_{\tau^{\prime}}V_{i}^{s+ 1}(e_{i}(q),\tau^{\prime})\cdot p_{\tau\tau^{\prime}} \tag{33}\] \[=r_{E}^{s+1}(e_{i}(q-1),\tau)+\gamma\sum_{\tau^{\prime}}V_{i}^{s} (e_{i}(q),\tau^{\prime})\cdot p_{\tau\tau^{\prime}}\] \[=\min_{u_{i}(q-1)}\{r_{E}(e_{i}(q-1),\tau)+\gamma\sum_{\tau^{ \prime}}V_{i}^{s}(e_{i}(q),\tau^{\prime})\cdot p_{\tau\tau^{\prime}}\}\] \[\leqslant r_{E}^{s}(e_{i}(q-1),\tau)+\gamma\sum_{\tau^{\prime}}V_ {i}^{s}(e_{i}(q),\tau^{\prime})\cdot p_{\tau\tau^{\prime}}\] \[=V_{i}^{s}(e_{i}(q-1),\tau).\]  
From (33), \(V_{i}^{s+1}(e_{i}(k),\tau)\leqslant V_{i}^{s}(e_{i}(k),\tau)\) holds for \(k=q-1\). Next, for \(k=M+1\), assume that \(V_{i}^{s+1}(e_{i}(M+1),\tau)\leqslant V_{i}^{s}(e_{i}(M+1),\tau)\) is true, where \(\forall M=0,1,2,\dots\). Let \(k=M\); we can obtain that  
\[V_{i}^{s+1}(e_{i}(M),\tau) =r_{E}^{s+1}(e_{i}(M),\tau)+\gamma\sum_{\tau^{\prime}}V_{i}^{s+1} (e_{i}(M+1),\tau^{\prime})\cdot p_{\tau\tau^{\prime}} \tag{34}\] \[=\min_{u_{i}(k)}\{r_{E}(e_{i}(k),\tau)+\gamma\sum_{\tau^{\prime}} V_{i}^{s}(e_{i}(k+1),\tau^{\prime})\cdot p_{\tau\tau^{\prime}}\}\]0 \[=\min_{u_{i}(k)}\{r_{E}(e_{i}(k),\tau)+\gamma\sum_{\tau^{\prime}} V_{i}^{s}(e_{i}(k+1),\tau^{\prime})\cdot p_{\tau\tau^{\prime}}\}\]1  
From (34), we can show that the inequality \(V_{i}^{s+1}(e_{i}(k),\tau)\leq V_{i}^{s}(e_{i}(k),\tau)\) holds for all \(k\). By using mathematical induction, the proof has been finished. For \(\forall i,\forall s\), let initial policies be admissible, and \(V_{i}^{s}(e_{i}(k))\) and \(u_{i}^{s}(k)\) are iteratively updated via Equations (27) and (28), respectively. After that, when \(k\to\infty\), it follows that \(V_{i}^{s}(e_{i}(k))\to V_{i}^{s}(e_{i}(k))\) and \(u_{i}^{s}(k)\to u_{i}^{s}(k)\). Proof.