# Optimal Model-Free Mean-Square Consensus for Multi-Agents with Markov Switching Topology
## 3 Main Results
### Convergence of the PI Algorithm
: According to Lemma 3, \(V_{i}^{s}(e_{i}(k))\) is monotonic and non-increasing with a lower bound, and therefore has a limit, denoted as \(V_{i}^{\infty}(e_{i}(k))=\lim_{k\to\infty}V_{i}^{s}(e_{i}(k))\). According to (30), it is simple to obtain  
\[=\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}}\}\]2 \[=\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}}\}\]3By selecting a sufficiently large \(s\), where \(s\to\infty\), we obtain  
\[=\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}}\}\]4  
Let \(\varepsilon_{i}>0\) be an arbitrary constant that is small enough. As \(V_{i}^{s}(e_{i}(k),\tau)\) is monotonically nonincreasing, an iteration index \(H\) can be found such that  
\[=\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}}\}\]5  
It follows from (37) that  
\[ \begin{split} V_{i}^{\infty}(e_{i}(k),\tau)& \geqslant V_{i}^{H}(e_{i}(k),\tau)-\varepsilon_{i}\\ &=r_{E}^{H}(e_{i}(k),\tau)+\gamma\sum_{\tau^{\prime}}V_{i}^{H}(e_ {i}(k+1),\tau^{\prime})\cdot p_{\tau\tau^{\prime}}-\varepsilon_{i}\\ &\geqslant r_{E}^{H}(e_{i}(k),\tau)+\gamma\sum_{\tau^{\prime}}V_{ i}^{\infty}(e_{i}(k+1),\tau^{\prime})\cdot p_{\tau\tau^{\prime}}-\varepsilon_{i}\\ &\geqslant\min_{u_{i}(k)}\{r_{E}(e_{i}(k),\tau)+\gamma\sum_{\tau ^{\prime}}V_{i}^{\infty}(e_{i}(k+1),\tau^{\prime})\cdot p_{\tau\tau^{\prime}} \}-\varepsilon_{i}.\end{split}  \tag{38}\]  
Since \(\varepsilon_{i}\) is any positive constant and it is small enough, it follows that  
\[V_{i}^{\infty}(\varepsilon_{i}(k),\tau)\geqslant\min_{u_{i}(k)}\{r_{E}(e_{i} (k),\tau)+\gamma\sum_{\tau^{\prime}}V_{i}^{\infty}(e_{i}(k+1),\tau^{\prime}) \cdot p_{\tau\tau^{\prime}}\}. \tag{39}\]  
Combining (36) and (39) yields  
\[V_{i}^{\infty}(e_{i}(k),\tau)=\min_{u_{i}(k)}\{r_{E}(e_{i}(k),\tau)+\gamma\sum _{\tau^{\prime}}V_{i}^{\infty}(e_{i}(k+1),\tau^{\prime})\cdot p_{\tau\tau^{ \prime}}\}. \tag{40}\]  
Introduce a novel performance index \(\Psi(e_{i}(k),\tau)\) defined by  
\[\Psi_{i}(e_{i}(k),\tau)=E[r(e_{i}(k),\mu_{i}(k),\mu_{-i}(k))|\sigma(k)=\tau]+ \gamma\sum_{\tau^{\prime}}\Psi_{i}(e_{i}(k+1),\tau^{\prime})\cdot p_{\tau\tau^ {\prime}}. \tag{41}\]  
where \(\mu_{i}(k)\) and \(\mu_{-i}(k)\) are the arbitrarily admissible control policies. Let \(k=p\), where \(p\to\infty\); then, it follows from Lemma 2 that \(e_{i}(p)\to 0\), which suggests that \(V_{i}^{\infty}(e_{i}(p),\tau)=\Psi_{i}(e_{i}(k),\tau)\). Then, let \(k=p-1\); it is possible to acquire  
\[ \begin{split}\Psi_{i}(e_{i}(k),\tau)&=E[r(e_{i}(p-1 ),\mu_{i}(p-1),\mu_{-i}(p-1))|\sigma(p-1)=\tau]+\gamma\sum_{\tau^{\prime}} \Psi_{i}(e_{i}(p),\tau^{\prime})\cdot p_{\tau\tau^{\prime}}\\ &\geqslant\min_{u_{i}(p-1)}\{E[r(e_{i}(p-1),u_{i}(p-1),u_{-i}(p-1 ))|\sigma(p-1)=\tau]+\gamma\sum_{\tau^{\prime}}\Psi_{i}(e_{i}(p),\tau^{\prime })\cdot p_{\tau\tau^{\prime}}\}\\ &=\min_{u_{i}(p-1)}\{E[r(e_{i}(p-1),u_{i}(p-1),u_{-i}(p-1))| \sigma(p-1)=\tau]+\gamma\sum_{\tau^{\prime}}V_{i}^{\infty}(e_{i}(p),\tau^{ \prime})\cdot p_{\tau\tau^{\prime}}\}\\ &=V_{i}^{\infty}(e_{i}(p-1)).\end{split}  \tag{42}\]  
For \(k=\varsigma+1\), assume that \(V_{i}^{\infty}(e_{i}(\varsigma+1),\tau)\leqslant\Psi_{i}(e_{i}(\varsigma+1),\tau)\) is true, where \(\forall\varsigma=0,1,2,\ldots\). Let \(k=\varsigma\); we can obtain that  
\[