$\displaystyle\left(\gamma+\frac{4\sqrt{|\mathcal{S}|A_{\max}}c^{1/2}_{\alpha,\beta}}{c_{\tau}^{1/2}\tau^{1/2}}\right)\mathbb{E}[\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}]$
$\displaystyle+\frac{4\sqrt{|\mathcal{S}|A_{\max}}(K-z_{\beta})^{1/2}}{(1-\gamma)}\left(1-\frac{c_{\alpha,\beta}\alpha}{2}\right)^{\frac{K-z_{\beta}-1}{2}}$
$\displaystyle+\frac{20|\mathcal{S}|^{3/4}A_{\max}^{3/4}\hat{L}_{\tau}^{1/2}}{c_{\tau}^{1/2}(1-\gamma)}z_{\beta}\alpha^{1/2}$
$\displaystyle\leq\;$
$\displaystyle\left(\frac{1+\gamma}{2}\right)\mathbb{E}[\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}]$
$\displaystyle+\frac{4\sqrt{|\mathcal{S}|A_{\max}}(K-z_{\beta})^{1/2}}{(1-\gamma)}\left(1-\frac{c_{\alpha,\beta}\alpha}{2}\right)^{\frac{K-z_{\beta}-1}{2}}$
$\displaystyle+\frac{20|\mathcal{S}|^{3/4}A_{\max}^{3/4}\hat{L}_{\tau}^{1/2}}{c_{\tau}^{1/2}(1-\gamma)}z_{\beta}\alpha^{1/2},$

where the last line follows from Condition A.1. Since
$\|v_{0}^{i}+v_{0}^{-i}\|_{\infty}\leq\frac{2}{1-\gamma}$, repeatedly using
the previous inequality starting from $0$ and we have for all $t\geq 0$ that

$\displaystyle\mathbb{E}[\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}]\leq\;$
$\displaystyle\frac{2}{1-\gamma}\left(\frac{1+\gamma}{2}\right)^{t}+\frac{8\sqrt{|\mathcal{S}|A_{\max}}(K-z_{\beta})^{1/2}}{(1-\gamma)^{2}}\left(1-\frac{c_{\alpha,\beta}\alpha}{2}\right)^{\frac{K-z_{\beta}-1}{2}}$
$\displaystyle+\frac{40|\mathcal{S}|^{3/4}A_{\max}^{3/4}\hat{L}_{\tau}^{1/2}}{c_{\tau}^{1/2}(1-\gamma)^{2}}z_{\beta}\alpha^{1/2}.$
(41)

Now we have obtained finite-sample bounds for $\mathcal{L}_{q}(t,k)$,
$\mathcal{L}_{\pi}(t,k)$, and $\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}$. The next
step is to use them in Eq. (• ‣ A.6) to obtain finite-sample bounds for
$\|v_{t}^{i}-v_{*}^{i}\|_{\infty}$. Specifically, we have by Eq. (• ‣ A.6),
Eq. (A.6.1), and Eq. (A.6.1) that

$\displaystyle\mathbb{E}[\|v_{t+1}^{i}-v_{*}^{i}\|_{\infty}]\leq\;$
$\displaystyle\gamma\mathbb{E}[\|v_{t}^{i}-v_{*}^{i}\|_{\infty}]+2\mathbb{E}[\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}]+4\tau\log(A_{\max})$
$\displaystyle+2\mathbb{E}[\mathcal{L}_{\pi}(t,K)]+\sum_{i=1,2}\mathbb{E}\|q_{t,K}^{i}-\bar{q}_{t,K}^{i}\|_{2}]$
$\displaystyle\leq\;$
$\displaystyle\gamma\mathbb{E}[\|v_{t}^{i}-v_{*}^{i}\|_{\infty}]+2\mathbb{E}[\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}]+4\tau\log(A_{\max})$
$\displaystyle+2\mathbb{E}[\mathcal{L}_{\pi}(t,K)]+2\mathbb{E}_{t}[\mathcal{L}_{q}(t,K)]^{1/2}$
$\displaystyle\leq\;$
$\displaystyle\gamma\mathbb{E}[\|v_{t}^{i}-v_{*}^{i}\|_{\infty}]+2\mathbb{E}[\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}]+4\tau\log(A_{\max})$
$\displaystyle+\frac{8|\mathcal{S}|A_{\max}}{(1-\gamma)^{2}}\left(1-\frac{c_{\alpha,\beta}\alpha}{2}\right)^{K-z_{\beta}}+\frac{64|\mathcal{S}|A_{\max}}{\tau}\mathbb{E}[\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}^{2}]$
$\displaystyle+\frac{1424|\mathcal{S}|^{3/2}A_{\max}^{3/2}\hat{L}_{\tau}}{(1-\gamma)^{2}c_{\alpha,\beta}}z_{\beta}^{2}\alpha+\frac{3\sqrt{|\mathcal{S}|A_{\max}}}{(1-\gamma)}\left(1-\frac{c_{\tau}\alpha}{2}\right)^{\frac{K-z_{\beta}}{2}}$
$\displaystyle+\frac{\sqrt{|\mathcal{S}|A_{\max}}c^{1/2}_{\alpha,\beta}\alpha^{1/2}(K-z_{\beta})^{1/2}}{(1-\gamma)}\left(1-\frac{c_{\alpha,\beta}\alpha}{2}\right)^{\frac{K-z_{\beta}-1}{2}}$
$\displaystyle+\frac{4\sqrt{|\mathcal{S}|A_{\max}}c^{1/2}_{\alpha,\beta}}{c_{\tau}^{1/2}\tau^{1/2}}\mathbb{E}[\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}]+\frac{20|\mathcal{S}|^{3/4}A_{\max}^{3/4}\hat{L}_{\tau}^{1/2}}{c_{\tau}^{1/2}(1-\gamma)}z_{\beta}\alpha^{1/2}$
$\displaystyle\leq\;$
$\displaystyle\gamma\mathbb{E}[\|v_{t}^{i}-v_{*}^{i}\|_{\infty}]+\frac{134|\mathcal{S}|A_{\max}}{\tau(1-\gamma)}\mathbb{E}[\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}]+4\tau\log(A_{\max})$
$\displaystyle+\frac{12|\mathcal{S}|A_{\max}(K-z_{\beta})^{1/2}}{(1-\gamma)^{2}}\left(1-\frac{c_{\alpha,\beta}\alpha}{2}\right)^{\frac{K-z_{\beta}-1}{2}}$
$\displaystyle+\frac{1444|\mathcal{S}|^{3/2}A_{\max}^{3/2}\hat{L}_{\tau}}{(1-\gamma)^{2}c_{\alpha,\beta}}z_{\beta}^{2}\alpha^{1/2}$
$\displaystyle\leq\;$
$\displaystyle\gamma\mathbb{E}[\|v_{t}^{i}-v_{*}^{i}\|_{\infty}]+4\tau\log(A_{\max})+\frac{1444|\mathcal{S}|^{3/2}A_{\max}^{3/2}\hat{L}_{\tau}}{(1-\gamma)^{2}c_{\alpha,\beta}}z_{\beta}^{2}\alpha^{1/2}$
$\displaystyle+\frac{12|\mathcal{S}|A_{\max}(K-z_{\beta})^{1/2}}{(1-\gamma)^{2}}\left(1-\frac{c_{\alpha,\beta}\alpha}{2}\right)^{\frac{K-z_{\beta}-1}{2}}$
$\displaystyle+\frac{134|\mathcal{S}|A_{\max}}{\tau(1-\gamma)}\left(\frac{2}{1-\gamma}\left(\frac{1+\gamma}{2}\right)^{t}+\frac{40|\mathcal{S}|^{3/4}A_{\max}^{3/4}\hat{L}_{\tau}^{1/2}}{c_{\tau}^{1/2}(1-\gamma)^{2}}z_{\beta}\alpha^{1/2}\right.$
$\displaystyle\left.+\frac{8\sqrt{|\mathcal{S}|A_{\max}}(K-z_{\beta})^{1/2}}{(1-\gamma)^{2}}\left(1-\frac{c_{\alpha,\beta}\alpha}{2}\right)^{\frac{K-z_{\beta}-1}{2}}\right)$
$\displaystyle\leq\;$
$\displaystyle\gamma\mathbb{E}[\|v_{t}^{i}-v_{*}^{i}\|_{\infty}]+4\tau\log(A_{\max})+\frac{268|\mathcal{S}|A_{\max}}{\tau(1-\gamma)^{2}}\left(\frac{1+\gamma}{2}\right)^{t}$
$\displaystyle+\frac{1084|\mathcal{S}|^{3/2}A_{\max}^{3/2}(K-z_{\beta})^{1/2}}{\tau(1-\gamma)^{3}}\left(1-\frac{c_{\alpha,\beta}\alpha}{2}\right)^{\frac{K-z_{\beta}-1}{2}}$
$\displaystyle+\frac{6804|\mathcal{S}|^{2}A_{\max}^{2}\hat{L}_{\tau}}{c_{\alpha,\beta}(1-\gamma)^{3}}z_{\beta}^{2}\alpha^{1/2}.$

Repeatedly using the previous inequality from $0$ to $T-1$ and we have

$\displaystyle\mathbb{E}[\|v_{T}^{i}-v_{*}^{i}\|_{\infty}]\leq\;$
$\displaystyle\frac{4\tau\log(A_{\max})}{1-\gamma}+\frac{270|\mathcal{S}|A_{\max}T}{\tau(1-\gamma)^{2}}\left(\frac{1+\gamma}{2}\right)^{T-1}$
$\displaystyle+\frac{1084|\mathcal{S}|^{3/2}A_{\max}^{3/2}(K-z_{\beta})^{1/2}}{\tau(1-\gamma)^{4}}\left(1-\frac{c_{\alpha,\beta}\alpha}{2}\right)^{\frac{K-z_{\beta}-1}{2}}$
$\displaystyle+\frac{6804|\mathcal{S}|^{2}A_{\max}^{2}\hat{L}_{\tau}}{c_{\alpha,\beta}(1-\gamma)^{4}}z_{\beta}^{2}\alpha^{1/2},$

where we used $\|v_{0}^{i}-v_{*}^{i}\|_{\infty}\leq 2/(1-\gamma)$.

Our next step is to use the bounds we obtained for $\mathcal{L}_{q}(t,k)$,
$\mathcal{L}_{\pi}(t,k)$, $\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}$, and
$\|v_{t}^{i}-v_{*}^{i}\|_{\infty}$ in Lemma A.4. For simplicity, we use
$a\lesssim b$ to mean that there exists a numerical constant $c$ such that
$a\leq cb$. Now, we have by the previous inequality, Eq. (A.6.1), and Eq.
(A.6.1) that

$\displaystyle\mathbb{E}\left[\left\|v^{i}_{*,\pi_{T,K}^{-i}}-v^{i}_{\pi_{T,K}^{i},\pi_{T,K}^{-i}}\right\|_{\infty}\right]$
$\displaystyle\leq\;$
$\displaystyle\frac{2}{1-\gamma}\left(2\mathbb{E}[\|v_{T}^{i}+v_{T}^{-i}\|_{\infty}]+2\mathbb{E}[\|v^{i}_{T}-v^{i}_{*}\|_{\infty}]+\mathcal{L}_{\pi}(T,K)+2\tau\log(A_{\max})\right)$
$\displaystyle\lesssim\;$
$\displaystyle\frac{\tau\log(A_{\max})}{(1-\gamma)^{2}}+\frac{|\mathcal{S}|A_{\max}T}{\tau(1-\gamma)^{3}}\left(\frac{1+\gamma}{2}\right)^{T-1}$
$\displaystyle+\frac{|\mathcal{S}|^{3/2}A_{\max}^{3/2}(K-z_{\beta})^{1/2}}{\tau(1-\gamma)^{5}}\left(1-\frac{c_{\alpha,\beta}\alpha}{2}\right)^{\frac{K-z_{\beta}-1}{2}}+\frac{|\mathcal{S}|^{2}A_{\max}^{2}\hat{L}_{\tau}}{c_{\alpha,\beta}(1-\gamma)^{5}}z_{\beta}^{2}\alpha^{1/2},$

Finally, using the previous inequality in Lemma A.3 and we have

$\displaystyle\mathbb{E}[\textit{NG}(\pi_{T,K}^{i},\pi_{T,K}^{-i})]\lesssim\;$
$\displaystyle\frac{\tau\log(A_{\max})}{(1-\gamma)^{2}}+\frac{|\mathcal{S}|A_{\max}T}{\tau(1-\gamma)^{3}}\left(\frac{1+\gamma}{2}\right)^{T-1}$
$\displaystyle+\frac{|\mathcal{S}|^{3/2}A_{\max}^{3/2}(K-z_{\beta})^{1/2}}{\tau(1-\gamma)^{5}}\left(1-\frac{c_{\alpha,\beta}\alpha}{2}\right)^{\frac{K-z_{\beta}-1}{2}}$
$\displaystyle+\frac{|\mathcal{S}|^{2}A_{\max}^{2}\hat{L}_{\tau}}{c_{\alpha,\beta}(1-\gamma)^{5}}z_{\beta}^{2}\alpha^{1/2}.$

The proof of Theorem 3.1 is complete.

####  A.6.2 Diminishing Stepsizes

Consider using linearly diminishing stepsizes, i.e.,
$\alpha_{k}=\frac{\alpha}{k+h}$, $\beta_{k}=\frac{\beta}{k+h}$, and
$\beta=c_{\alpha,\beta}\alpha$. Repeatedly using Eq. (A.6) and we have for all
$k\geq k_{0}$ that

$\displaystyle\mathbb{E}_{t}[\mathcal{L}_{\pi}(t,k)+\mathcal{L}_{q}(t,k)]\lesssim\;$
$\displaystyle\frac{4|\mathcal{S}|A_{\max}}{(1-\gamma)^{2}}\underbrace{\prod_{m=k_{0}}^{k-1}\left(1-\frac{c_{\alpha,\beta}\alpha_{m}}{2}\right)}_{\hat{\mathcal{E}}_{1}}$
$\displaystyle+\frac{|\mathcal{S}|^{3/2}A_{\max}^{2}\hat{L}_{\tau}}{(1-\gamma)^{2}}\underbrace{\sum_{n=k_{0}}^{k-1}z_{n}^{2}\alpha_{n}^{2}\prod_{m=n+1}^{k-1}\left(1-\frac{c_{\alpha,\beta}\alpha_{m}}{2}\right)}_{\hat{\mathcal{E}}_{2}}$
$\displaystyle+\frac{|\mathcal{S}|A_{\max}c_{\alpha,\beta}}{\tau}\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}^{2}\underbrace{\sum_{n=k_{0}}^{k-1}\alpha_{n}\prod_{m=n+1}^{k-1}\left(1-\frac{c_{\alpha,\beta}\alpha_{m}}{2}\right)}_{\hat{\mathcal{E}}_{3}}.$

We next provide estimates for the terms $\\{\hat{\mathcal{E}}_{j}\\}_{1\leq
j\leq 3}$. Bounds of terms like $\\{\hat{\mathcal{E}}_{j}\\}_{1\leq j\leq 3}$
are well-established in existing work studying the convergence rate of
iterative algorithms (Srikant and Ying, , 2019; Lan, , 2020; Chen et al.,
2021b, ). Specifically, we have from (Chen et al., 2021b, , Appendix A.2.)
that

$\displaystyle\hat{\mathcal{E}}_{1}\leq\left(\frac{k_{0}+h}{k+h}\right)^{c_{\alpha,\beta}\alpha/2},\quad\hat{\mathcal{E}}_{2}\leq\frac{4ez_{k}^{2}\alpha^{2}}{c_{\alpha,\beta}\alpha/2-1}\frac{1}{k+h},\;\text{
and }\;\hat{\mathcal{E}}_{3}\leq\frac{2}{c_{\alpha,\beta}}.$

It follows that

$\displaystyle\mathbb{E}_{t}[\mathcal{L}_{\pi}(t,k)+\mathcal{L}_{q}(t,k)]$
$\displaystyle\lesssim\;$
$\displaystyle\frac{|\mathcal{S}|A_{\max}}{(1-\gamma)^{2}}\left(\frac{k_{0}+h}{k+h}\right)^{c_{\alpha,\beta}\alpha/2}+\frac{|\mathcal{S}|^{3/2}A_{\max}^{2}\hat{L}_{\tau}}{(1-\gamma)^{2}}\frac{z_{k}^{2}\alpha^{2}}{c_{\alpha,\beta}\alpha/2-1}\frac{1}{k+h}$
$\displaystyle+\frac{|\mathcal{S}|A_{\max}}{\tau}\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}^{2}$
$\displaystyle\lesssim\;$
$\displaystyle\frac{|\mathcal{S}|A_{\max}}{(1-\gamma)^{2}}\left(\frac{\alpha_{k}}{\alpha_{k_{0}}}\right)^{c_{\alpha,\beta}\alpha/2}+\frac{|\mathcal{S}|^{3/2}A_{\max}^{2}\hat{L}_{\tau}}{(1-\gamma)^{2}}\frac{z_{k}^{2}\alpha^{2}}{c_{\alpha,\beta}\alpha/2-1}\frac{1}{k+h}$
$\displaystyle+\frac{|\mathcal{S}|A_{\max}}{\tau}\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}^{2},$
(42)

which implies

$\displaystyle\mathbb{E}_{t}[\mathcal{L}_{\pi}(t,k)]\lesssim\;$
$\displaystyle\frac{|\mathcal{S}|A_{\max}}{(1-\gamma)^{2}}\left(\frac{\alpha_{k}}{\alpha_{k_{0}}}\right)^{c_{\alpha,\beta}\alpha/2}+\frac{|\mathcal{S}|^{3/2}A_{\max}^{2}\hat{L}_{\tau}}{(1-\gamma)^{2}}\frac{z_{k}^{2}\alpha^{2}}{c_{\alpha,\beta}\alpha/2-1}\frac{1}{k+h}$
$\displaystyle+\frac{|\mathcal{S}|A_{\max}}{\tau}\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}^{2}.$

Using the previous bound on $\mathbb{E}_{t}[\mathcal{L}_{\pi}(t,k)]$ in Eq. (•
‣ A.6) and we have

$\displaystyle\mathbb{E}_{t}[\mathcal{L}_{q}(t,k+1)]\leq\;$
$\displaystyle\left(1-c_{\tau}\alpha_{k}+\frac{17A_{\max}^{2}\beta_{k}}{\tau(1-\gamma)^{2}}\right)\mathbb{E}_{t}[\mathcal{L}_{q}(t,k)]$
$\displaystyle+\frac{\beta_{k}}{16}\mathbb{E}_{t}[\mathcal{L}_{\pi}(t,k)]+\frac{352|\mathcal{S}|^{3/2}A_{\max}^{3/2}\hat{L}_{\tau}}{(1-\gamma)^{2}}z_{k}\alpha_{k}\alpha_{k-z_{k},k-1}$
$\displaystyle\lesssim\;$
$\displaystyle\left(1-\frac{c_{\tau}\alpha_{k}}{2}\right)\mathbb{E}_{t}[\mathcal{L}_{q}(t,k)]+\frac{|\mathcal{S}|^{3/2}A_{\max}^{2}}{\alpha_{k_{0}}(1-\gamma)^{2}}z_{k}^{2}\alpha_{k}^{2}$
$\displaystyle+\frac{|\mathcal{S}|A_{\max}c_{\alpha,\beta}\alpha_{k}}{\tau}\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}^{2}.$

Repeatedly using the previous inequality starting from $k_{0}$ and we have

$\displaystyle\mathbb{E}_{t}[\mathcal{L}_{q}(t,k)]\lesssim\;$
$\displaystyle\frac{|\mathcal{S}|A_{\max}}{(1-\gamma)^{2}}\left(\frac{\alpha_{k}}{\alpha_{k_{0}}}\right)^{c_{\tau}\alpha/2}+\frac{|\mathcal{S}|^{3/2}A_{\max}^{2}}{\alpha_{k_{0}}(1-\gamma)^{2}}z_{k}^{2}\alpha_{k}$
$\displaystyle+\frac{|\mathcal{S}|A_{\max}c_{\alpha,\beta}}{c_{\tau}\tau}\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}^{2}$
$\displaystyle\lesssim\;$
$\displaystyle\frac{|\mathcal{S}|^{3/2}A_{\max}^{2}}{\alpha_{k_{0}}(1-\gamma)^{2}}z_{k}^{2}\alpha_{k}+\frac{|\mathcal{S}|A_{\max}c_{\alpha,\beta}}{c_{\tau}\tau}\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}^{2}$

Since
$\sum_{i=1,2}\mathbb{E}_{t}\left[\|q_{t,K}^{i}-\bar{q}_{t,K}^{i}\|_{2}\right]\lesssim\mathbb{E}_{t}[\mathcal{L}_{q}(t,K)]^{1/2}$,
we have

$\displaystyle\sum_{i=1,2}\mathbb{E}_{t}\left[\|q_{t,K}^{i}-\bar{q}_{t,K}^{i}\|_{2}\right]\leq\;$
$\displaystyle\frac{c_{1}^{\prime}|\mathcal{S}|^{3/4}A_{\max}}{\alpha^{1/2}_{k_{0}}(1-\gamma)}z_{k}\alpha_{k}^{1/2}+\frac{c_{2}^{\prime}\sqrt{|\mathcal{S}|A_{\max}}c^{1/2}_{\alpha,\beta}}{c_{\tau}^{1/2}\tau^{1/2}}\|v_{t}^{i}+v_{t}^{-i}\|_{\infty},$
(43)

where $c_{1}^{\prime}$ and $c_{2}^{\prime}$ are numerical constants. Taking
total expectation on boths sides of the previous inequality and then using the
result in Eq. (34), and we have

$\displaystyle\mathbb{E}[\|v_{t+1}^{i}+v_{t+1}^{-i}\|_{\infty}]$
$\displaystyle\leq\;$
$\displaystyle\left(\gamma+\frac{c_{2}^{\prime}\sqrt{|\mathcal{S}|A_{\max}}c^{1/2}_{\alpha,\beta}}{c_{\tau}^{1/2}\tau^{1/2}}\right)\mathbb{E}[\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}]+\frac{c_{1}^{\prime}|\mathcal{S}|^{3/4}A_{\max}}{\alpha^{1/2}_{k_{0}}(1-\gamma)}z_{k}\alpha_{k}^{1/2}$
$\displaystyle\leq\;$
$\displaystyle\left(\frac{\gamma+1}{2}\right)\mathbb{E}[\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}]+\frac{c_{1}^{\prime}|\mathcal{S}|^{3/4}A_{\max}}{\alpha^{1/2}_{k_{0}}(1-\gamma)}z_{k}\alpha_{k}^{1/2},$

where the last line follows from Condition A.1. Repeatedly using the previous
inequality starting from $0$ and we have

$\displaystyle\mathbb{E}[\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}]\lesssim\frac{2}{1-\gamma}\left(\frac{\gamma+1}{2}\right)^{t}+\frac{|\mathcal{S}|^{3/4}A_{\max}}{\alpha^{1/2}_{k_{0}}(1-\gamma)^{2}}z_{k}\alpha_{k}^{1/2}.$
(44)

The next step is to bound $\|v_{t}^{i}-v_{*}^{i}\|_{\infty}$. Recall from Eq.
(• ‣ A.6) that

$\displaystyle\mathbb{E}[\|v_{t+1}^{i}-v_{*}^{i}\|_{\infty}]\leq\;$
$\displaystyle\gamma\mathbb{E}[\|v_{t}^{i}-v_{*}^{i}\|_{\infty}]+2\mathbb{E}[\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}]+4\tau\log(A_{\max})$
$\displaystyle+2\mathbb{E}[\mathcal{L}_{\pi}(t,K)]+2\mathbb{E}[\mathcal{L}_{q}(t,K)]^{1/2}.$

Since Eq. (A.6.2) and Eq. (43) imply that

$\displaystyle\mathbb{E}[\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}]+\tau\log(A_{\max})+\mathbb{E}[\mathcal{L}_{\pi}(t,K)]+\mathbb{E}[\mathcal{L}_{q}(t,K)]^{1/2}$
$\displaystyle\lesssim\;$
$\displaystyle\frac{|\mathcal{S}|A_{\max}}{\tau(1-\gamma)^{2}}\left(\frac{\gamma+1}{2}\right)^{t}+\tau\log(A_{\max})+\frac{|\mathcal{S}|^{2}A_{\max}^{2}\hat{L}_{\tau}}{\alpha_{k_{0}}c_{\alpha,\beta}(1-\gamma)^{3}}z_{K}^{2}\alpha_{K}^{1/2},$

we have

$\displaystyle\mathbb{E}[\|v_{t+1}^{i}-v_{*}^{i}\|_{\infty}]\leq\;$
$\displaystyle\gamma\mathbb{E}[\|v_{t}^{i}-v_{*}^{i}\|_{\infty}]$
$\displaystyle+c^{\prime\prime}\left[\frac{|\mathcal{S}|A_{\max}}{\tau(1-\gamma)^{2}}\left(\frac{\gamma+1}{2}\right)^{t}+\tau\log(A_{\max})+\frac{|\mathcal{S}|^{2}A_{\max}^{2}\hat{L}_{\tau}}{\alpha_{k_{0}}c_{\alpha,\beta}(1-\gamma)^{3}}z_{K}^{2}\alpha_{K}^{1/2}\right]$

for some numerical constant $c^{\prime\prime}$. Repeatedly using the previous
inequality starting from $0$ to $T-1$ and we have

$\displaystyle\mathbb{E}[\|v_{T}^{i}-v_{*}^{i}\|_{\infty}]\lesssim\frac{|\mathcal{S}|A_{\max}T}{\tau(1-\gamma)^{2}}\left(\frac{\gamma+1}{2}\right)^{T-1}+\frac{\tau\log(A_{\max})}{(1-\gamma)}+\frac{|\mathcal{S}|^{2}A_{\max}^{2}\hat{L}_{\tau}}{\alpha_{k_{0}}c_{\alpha,\beta}(1-\gamma)^{4}}z_{K}^{2}\alpha_{K}^{1/2}$

Using the previous inequality, Eq. (A.6.2), and Eq. (44) in Lemma A.4, and we
obtain

$\displaystyle\mathbb{E}[\|v^{i}_{*,\pi_{T,K}^{-i}}-v^{i}_{\pi_{T,K}^{i},\pi_{T,K}^{-i}}\|_{\infty}]\lesssim\;$
$\displaystyle\frac{|\mathcal{S}|A_{\max}T}{\tau(1-\gamma)^{3}}\left(\frac{\gamma+1}{2}\right)^{T-1}+\frac{\tau\log(A_{\max})}{(1-\gamma)^{2}}$
$\displaystyle+\frac{|\mathcal{S}|^{2}A_{\max}^{2}\hat{L}_{\tau}}{\alpha_{k_{0}}c_{\alpha,\beta}(1-\gamma)^{5}}z_{K}^{2}\alpha_{K}^{1/2}$

Finally, we have by the previous inequality and Lemma A.3 that

$\displaystyle\mathbb{E}[\textit{NG}(\pi_{T,K}^{i},\pi_{T,K}^{-i})]\lesssim\;$
$\displaystyle\frac{|\mathcal{S}|A_{\max}T}{\tau(1-\gamma)^{3}}\left(\frac{\gamma+1}{2}\right)^{T-1}+\frac{\tau\log(A_{\max})}{(1-\gamma)^{2}}$
$\displaystyle+\frac{|\mathcal{S}|^{2}A_{\max}^{2}\hat{L}_{\tau}}{\alpha_{k_{0}}c_{\alpha,\beta}(1-\gamma)^{5}}z_{K}^{2}\alpha_{K}^{1/2}.$

The proof of Theorem 3.2 is complete.

### A.7 Proof of All Supporting Lemmas

####  A.7.1 Proof of Lemma A.1

We first show by induction that whenever
$\|v_{t}^{i}\|_{\infty}\leq\frac{1}{1-\gamma}$, we have
$\|q_{t,k}^{i}\|_{\infty}\leq\frac{1}{1-\gamma}$ for all $k\geq 0$. Note that
$\|q_{t,0}^{i}\|_{\infty}\leq\frac{1}{1-\gamma}$ holds by our initialization.
Suppose that $\|q_{t,k}^{i}\|_{\infty}\leq\frac{1}{1-\gamma}$ for some $k\geq
0$. Then we have for all $(s,a^{i})$ that

$\displaystyle|q_{t,k+1}^{i}(s,a^{i})|$ $\displaystyle=\;$
$\displaystyle|q_{t,k}^{i}(s,a^{i})+\alpha_{k}\mathds{1}_{\\{(s,a^{i})=(S_{k},A_{k}^{i})\\}}(\mathcal{R}^{i}(S_{k},A_{k}^{i},A_{k}^{-i})+\gamma
v_{t}^{i}(S_{k+1})-q_{t,k}^{i}(S_{k},A_{k}^{i}))|$ $\displaystyle\leq\;$
$\displaystyle(1-\alpha_{k}\mathds{1}_{\\{(s,a^{i})=(S_{k},A_{k}^{i})\\}})|q_{t,k}^{i}(s,a^{i})|$
$\displaystyle+\alpha_{k}\mathds{1}_{\\{(s,a^{i})=(S_{k},A_{k}^{i})\\}}|\mathcal{R}^{i}(S_{k},A_{k}^{i},A_{k}^{-i})+\gamma
v_{t}^{i}(S_{k+1})|$ $\displaystyle\leq\;$
$\displaystyle(1-\alpha_{k}\mathds{1}_{\\{(s,a^{i})=(S_{k},A_{k}^{i})\\}})\frac{1}{1-\gamma}+\alpha_{k}\mathds{1}_{\\{(s,a^{i})=(S_{k},A_{k}^{i})\\}}\left(1+\frac{\gamma}{1-\gamma}\right)$
(45) $\displaystyle=\;$ $\displaystyle\frac{1}{1-\gamma},$

where Eq. (45) follows from the induction hypothesis
$\|q_{t,0}^{i}\|_{\infty}\leq\frac{1}{1-\gamma}$,
$\|v_{t}^{i}\|_{\infty}\leq\frac{1}{1-\gamma}$, and
$\max_{s,a^{i},a^{-i}}|\mathcal{R}^{i}(s,a^{i},a^{-i})|\leq 1$. The induction
is now complete and we have $\|q_{t,k}^{i}\|_{\infty}\leq\frac{1}{1-\gamma}$
for all $k\geq 0$ whenever $\|v_{t}^{i}\|_{\infty}\leq\frac{1}{1-\gamma}$.

We next again use induction to show that
$\|v_{t}^{i}\|_{\infty}\leq\frac{1}{1-\gamma}$ for all $t\geq 0$. Our
initialization ensures that $\|v_{0}^{i}\|_{\infty}\leq\frac{1}{1-\gamma}$.
Suppose that $\|v_{t}^{i}\|_{\infty}\leq\frac{1}{1-\gamma}$ for some $t\geq
0$. Using the update equation for $v_{t+1}^{i}$ (i.e., Algorithm 2 Line $8$)
and the fact that $\|q_{t,k}^{i}\|_{\infty}\leq\frac{1}{1-\gamma}$ for all
$k\geq 0$, we have for all $s\in\mathcal{S}$ that

$\displaystyle|v_{t+1}^{i}(s)|=\left|\sum_{a^{i}\in\mathcal{A}^{i}}\pi^{i}_{t,K}(a^{i}|s)q_{t,K}^{i}(s,a^{i})\right|\leq\sum_{a^{i}\in\mathcal{A}^{i}}\pi^{i}_{t,K}(a^{i}|s)\|q_{t,K}^{i}\|_{\infty}\leq\frac{1}{1-\gamma}.$

The induction for $\\{v_{t}^{i}\\}$ is now complete and we have
$\|v_{t}^{i}\|_{\infty}\leq\frac{1}{1-\gamma}$ for all $t\geq 0$.

####  A.7.2 Proof of Lemma A.2

Observe that for any $x\in\mathbb{R}^{d}$ and $j\in\\{1,2,\cdots,d\\}$, we
have

$\displaystyle\frac{\exp(x_{j})}{\sum_{\ell=1}^{d}\exp(x_{\ell})}=\;$
$\displaystyle\frac{\exp(x_{j})}{\exp(x_{j})+\sum_{\ell\neq j}\exp(x_{\ell})}$
$\displaystyle=\;$ $\displaystyle\frac{1}{1+\sum_{\ell\neq
j}\exp(x_{\ell}-x_{j})}$ $\displaystyle\geq\;$
$\displaystyle\frac{1}{1+(d-1)\exp(2\|x\|_{\infty})}.$

Therefore, since $\|q^{i}_{t,k}\|_{\infty}\leq 1/(1-\gamma)$ for all $t,k\geq
0$ (cf. Lemma A.1), we have for all $t,k\geq 0$ and $(s,a^{i})$ that

$\displaystyle\sigma_{\tau}(q_{t,k}^{i}(s))(a^{i})\geq\;$
$\displaystyle\frac{1}{1+(A_{\max}-1)\exp(2/[(1-\gamma)\tau])}=\ell_{\tau}.$
(46)

We next use induction to show that $\pi_{t,k}^{i}(a^{i}|s)\geq\ell_{\tau}$ for
all $t,k\geq 0$. Given any $t\geq 0$, our uniform initialization of
$\pi_{t,0}^{i}$ ensures that $\pi_{t,0}^{i}(a^{i}|s)\geq\ell_{\tau}$ for all
$(s,a^{i})$. Now suppose that $\pi_{t,k}^{i}(a^{i}|s)\geq\ell_{\tau}$ for all
$(s,a^{i})$ for some $k\geq 0$. Then we have from Algorithm 2 Line $4$ that

$\displaystyle\pi_{t,k+1}^{i}(a^{i}|s)=\;$
$\displaystyle(1-\beta_{k})\pi_{t,k}^{i}(a^{i}|s)+\beta_{k}\sigma_{\tau}(q_{t,k}^{i}(s))(a^{i})$
$\displaystyle\geq\;$
$\displaystyle(1-\beta_{k})\ell_{\tau}+\beta_{k}\ell_{\tau}$
$\displaystyle=\;$ $\displaystyle\ell_{\tau},$

where the inequality follows from Eq. (46) and the induction hypothesis. The
induction is now complete and we have $\pi_{t,k}^{i}(a^{i}|s)\geq\ell_{\tau}$
for all $t,k\geq 0$ and $(s,a^{i})$. Similarly, we also have
$\pi_{t,k}^{-i}(a^{-i}|s)\geq\ell_{\tau}$ for all $t,k\geq 0$ and
$(s,a^{-i})$.

####  A.7.3 Proof of Lemma 4.1

Lemma 4.1 (1), (3), and (4) are identical to (Zhang et al., 2022c, ,
Proposition 3). We here only prove Lemma 4.1 (2).

Consider the Markov chain $\\{S_{k}\\}$ induced by $\pi_{b}$. Since
$\\{S_{k}\\}$ is irreducible and aperiodic, there exists a positive integer
$r_{b}$ such that $P_{\pi_{b}}^{r_{b}}$ has strictly positive entries (Levin
and Peres, , 2017, Proposition 1.7). Therefore, there exists
$\delta_{b}\in(0,1)$ such that

$\displaystyle
P_{\pi_{b}}^{r_{b}}(s,s^{\prime})\geq\delta_{b}\mu_{b}(s^{\prime})$

for all $(s,s^{\prime})$. In addition, the constant $\rho_{b}$ introduced
after Assumption 3.1 is explicitly given as
$\rho_{b}=\exp(-\delta_{b}/r_{b})$. The previous two equations are from the
proof of the Markov chain convergence theorem presented in (Levin and Peres, ,
2017, Section 4.3).

Next we consider the Markov chain $\\{S_{k}\\}$ induced by an arbitrary
$\pi\in\Pi_{\delta}$. Since

$\displaystyle\frac{\pi_{b}(a|s)}{\pi(a|s)}=\frac{\pi_{b}^{i}(a^{i}|s)\pi_{b}^{-i}(a^{i}|s)}{\pi^{i}(a^{i}|s)\pi^{-i}(a^{i}|s)}\leq\frac{1}{\delta_{i}\delta_{-i}},\quad\forall\;a=(a^{i},a^{-i})\text{
and }s,$

we have for any $s,s^{\prime}\in\mathcal{S}$ and $k\geq 1$ that

$\displaystyle P_{\pi_{b}}^{k}(s,s^{\prime})=\;$
$\displaystyle\sum_{s_{0}}P^{k-1}_{\pi_{b}}(s,s_{0})P_{\pi_{b}}(s_{0},s^{\prime})$
$\displaystyle=\;$
$\displaystyle\sum_{s_{0}}P^{k-1}_{\pi_{b}}(s,s_{0})\sum_{a\in\mathcal{A}}\pi_{b}(a|s_{0})P_{a}(s_{0},s^{\prime})$
$\displaystyle=\;$
$\displaystyle\sum_{s_{0}}P^{k-1}_{\pi_{b}}(s,s_{0})\sum_{a\in\mathcal{A}}\frac{\pi_{b}(a|s_{0})}{\pi(a|s_{0})}\pi(a|s_{0})P_{a}(s_{0},s^{\prime})$
$\displaystyle\leq\;$
$\displaystyle\frac{1}{\delta_{i}\delta_{-i}}\sum_{s_{0}}P^{k-1}_{\pi_{b}}(s,s_{0})\sum_{a\in\mathcal{A}}\pi(a|s_{0})P_{a}(s_{0},s^{\prime})$
$\displaystyle\leq\;$
$\displaystyle\frac{1}{\delta_{i}\delta_{-i}}\sum_{s_{0}}P^{k-1}_{\pi_{b}}(s,s_{0})P_{\pi}(s_{0},s^{\prime})$
$\displaystyle=\;$
$\displaystyle\frac{1}{\delta_{i}\delta_{-i}}[P^{k-1}_{\pi_{b}}P_{\pi}](s,s^{\prime}).$

Since the previous inequality holds for all $s$ and $s^{\prime}$, we in fact
have $\delta_{i}\delta_{-i}P_{\pi_{b}}^{k}\leq P^{k-1}_{\pi_{b}}P_{\pi}$
(which is an entry-wise inequality). Repeatedly using the previous inequality
and we obtain

$\displaystyle(\delta_{i}\delta_{-i})^{k}P_{\pi_{b}}^{k}\leq P_{\pi}^{k},$

which implies

$\displaystyle P_{\pi}^{r_{b}}(s,s^{\prime})\geq\;$
$\displaystyle(\delta_{i}\delta_{-i})^{r_{b}}P_{\pi_{b}}^{r_{b}}(s,s^{\prime})$
$\displaystyle\geq\;$
$\displaystyle\delta_{b}(\delta_{i}\delta_{-i})^{r_{b}}\mu_{b}(s^{\prime})$
$\displaystyle\geq\;$
$\displaystyle\delta_{b}(\delta_{i}\delta_{-i})^{r_{b}}\frac{\mu_{b}(s^{\prime})}{\mu_{\pi}(s^{\prime})}\mu_{\pi}(s^{\prime})$
$\displaystyle\geq\;$
$\displaystyle\delta_{b}(\delta_{i}\delta_{-i})^{r_{b}}\mu_{b,\min}\mu_{\pi}(s^{\prime}).$

Following the proof of the Markov chain convergence theorem in (Levin and
Peres, , 2017, Section 4.3) and we have

$\displaystyle\|P_{\pi}^{k}(s,\cdot)-\mu_{\pi}(\cdot)\|_{\text{TV}}\leq\;$
$\displaystyle(1-\delta_{b}(\delta_{i}\delta_{-i})^{r_{b}}\mu_{b,\min})^{k/r_{b}-1},\quad\forall\;s\in\mathcal{S},\;\pi\in\Pi_{\delta}.$
(47)

Since $A_{\max}\geq 2$ (otherwise there is no decision to make in this Markov
game), we have $\delta_{i}\delta_{-i}\leq\frac{1}{2}$. It follows that
$1-\delta_{b}(\delta_{i}\delta_{-i})^{r_{b}}\mu_{b,\min}>1/2$. Using the
previous inequality in Eq. (47) and we have

$\displaystyle\sup_{\pi\in\Pi_{\delta}}\max_{s\in\mathcal{S}}\|P_{\pi}^{k}(s,\cdot)-\mu_{\pi}(\cdot)\|_{\text{TV}}\leq\;$
$\displaystyle
2(1-\delta_{b}(\delta_{i}\delta_{-i})^{r_{b}}\mu_{b,\min})^{k/r_{b}}$
$\displaystyle\leq\;$ $\displaystyle
2\exp\left(-\delta_{b}(\delta_{i}\delta_{-i})^{r_{b}}\mu_{b,\min}k/r_{b}\right)$
$\displaystyle=\;$ $\displaystyle
2\rho_{b}^{(\delta_{i}\delta_{-i})^{r_{b}}\mu_{b,\min}k}$ (Recall that
$\rho_{b}=\exp(-\delta_{b}/r_{b})$) $\displaystyle=\;$ $\displaystyle
2\rho_{\delta}^{k}.$

We next compute the mixing time. Using the previous inequality and the
definition of the total variation distance, we have

$\displaystyle\sup_{\pi\in\Pi_{\delta}}\max_{s\in\mathcal{S}}\|P_{\pi}^{k}(s,\cdot)-\mu_{\pi}(\cdot)\|_{\text{TV}}\leq\eta$

as long as

$\displaystyle
k\geq\frac{\log(2/\eta)}{\log(1/\rho_{\delta})}=\frac{1}{(\delta_{i}\delta_{-i})^{r_{b}}\mu_{b,\min}}\frac{\log(2/\eta)}{\log(1/\rho_{b})}\geq\frac{t_{\pi_{b},\eta}}{(\delta_{i}\delta_{-i})^{r_{b}}\mu_{b,\min}}.$

####  A.7.4 Proof of Lemma A.3

Using the definition of utility functions and we have

$\displaystyle\sum_{i=1,2}\left(\max_{\pi^{i}}U^{i}(\pi^{i},\pi_{T,K}^{-i})-U^{i}(\pi_{T,K}^{i},\pi_{T,K}^{-i})\right)$
$\displaystyle=\;$
$\displaystyle\sum_{i=1,2}\left(\max_{\pi^{i}}\mathbb{E}_{S\sim
p_{o}}\left[v^{i}_{\pi^{i},\pi_{T,K}^{-i}}(S)-v^{i}_{\pi_{T,K}^{i},\pi_{T,K}^{-i}}(S)\right]\right)$
$\displaystyle\leq\;$ $\displaystyle\sum_{i=1,2}\left(\mathbb{E}_{S\sim
p_{o}}\left[\max_{\pi^{i}}v^{i}_{\pi^{i},\pi_{T,K}^{-i}}(S)-v^{i}_{\pi_{T,K}^{i},\pi_{T,K}^{-i}}(S)\right]\right)$
(Jensen’s inequality) $\displaystyle=\;$
$\displaystyle\sum_{i=1,2}\left(\mathbb{E}_{S\sim
p_{o}}\left[v^{i}_{*,\pi_{T,K}^{-i}}(S)-v^{i}_{\pi_{T,K}^{i},\pi_{T,K}^{-i}}(S)\right]\right)$
$\displaystyle\leq\;$
$\displaystyle\sum_{i=1,2}\left\|v^{i}_{*,\pi_{T,K}^{-i}}-v^{i}_{\pi_{T,K}^{i},\pi_{T,K}^{-i}}\right\|_{\infty}.$

####  A.7.5 Proof of Lemma A.4

For any $t\geq 0$, $s\in\mathcal{S}$, and $i\in\\{1,2\\}$, we have

$\displaystyle 0\leq\;$
$\displaystyle\left|v^{i}_{*,\pi_{t,K}^{-i}}(s)-v^{i}_{\pi_{t,K}^{i},\pi_{t,K}^{-i}}(s)\right|$
$\displaystyle=\;$ $\displaystyle
v^{i}_{*,\pi_{t,K}^{-i}}(s)-v^{i}_{\pi_{t,K}^{i},\pi_{t,K}^{-i}}(s)$
$\displaystyle\leq\;$ $\displaystyle
v^{i}_{*,\pi_{t,K}^{-i}}(s)-v^{i}_{\pi_{t,K}^{i},*}(s)$ $\displaystyle=\;$
$\displaystyle-v^{-i}_{\pi_{t,K}^{-i},*}(s)-v^{i}_{\pi_{t,K}^{i},*}(s)$
$\displaystyle=\;$ $\displaystyle
v^{i}_{*}(s)-v^{-i}_{\pi_{t,K}^{-i},*}(s)+v^{-i}_{*}(s)-v^{i}_{\pi_{t,K}^{i},*}(s)$
$\displaystyle\leq\;$
$\displaystyle\|v^{-i}_{*}-v^{-i}_{\pi_{t,K}^{-i},*}\|_{\infty}+\|v^{i}_{*}-v^{i}_{\pi_{t,K}^{i},*}\|_{\infty}.$
(48)

It remains to bound the two terms on the RHS of the previous inequality. For
the first term, note that for any $s\in\mathcal{S}$ and $t\geq 0$, we have

$\displaystyle 0\leq\;$ $\displaystyle
v^{-i}_{*}(s)-v^{-i}_{\pi_{t,K}^{-i},*}(s)$ $\displaystyle=\;$ $\displaystyle
v^{i}_{*,\pi_{t,K}^{-i}}(s)-v^{i}_{*}(s)$ $\displaystyle=\;$
$\displaystyle\max_{\mu^{i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v^{i}_{*,\pi_{t,K}^{-i}})(s)\pi_{t,K}^{-i}(s)-\max_{\mu^{i}}\min_{\mu^{-i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v_{*}^{i})(s)\mu^{-i}$
$\displaystyle=\;$
$\displaystyle|\max_{\mu^{i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v^{i}_{*,\pi_{t,K}^{-i}})(s)\pi_{t,K}^{-i}(s)-\max_{\mu^{i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v^{i}_{*})(s)\pi_{t,K}^{-i}(s)|$
$\displaystyle+|\max_{\mu^{i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v^{i}_{*})(s)\pi_{t,K}^{-i}(s)-\max_{\mu^{i}}\min_{\mu^{-i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v_{*}^{i})(s)\mu^{-i}|$
$\displaystyle\leq\;$
$\displaystyle\max_{\mu^{i}}|(\mu^{i})^{\top}(\mathcal{T}^{i}(v^{i}_{*,\pi_{t,K}^{-i}})(s)-\mathcal{T}^{i}(v^{i}_{*})(s))\pi_{t,K}^{-i}(s)|$
$\displaystyle+|\max_{\mu^{i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v^{i}_{*})(s)\pi_{t,K}^{-i}(s)-\max_{\mu^{i}}\min_{\mu^{-i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v^{i}_{t})(s)\mu^{-i}|$
$\displaystyle+|\max_{\mu^{i}}\min_{\mu^{-i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v^{i}_{t})(s)\mu^{-i}-\max_{\mu^{i}}\min_{\mu^{-i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v_{*}^{i})(s)\mu^{-i}|$
$\displaystyle\leq\;$
$\displaystyle\underbrace{\max_{\mu^{i}}|(\mu^{i})^{\top}(\mathcal{T}^{i}(v^{i}_{*,\pi_{t,K}^{-i}})(s)-\mathcal{T}^{i}(v^{i}_{*})(s))\pi_{t,K}^{-i}(s)|}_{\hat{E}_{1}}$
$\displaystyle+\underbrace{|\max_{\mu^{i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v^{i}_{*})(s)\pi_{t,K}^{-i}(s)-\max_{\mu^{i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)|}_{\hat{E}_{2}}$
$\displaystyle+\underbrace{\max_{\mu^{i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)-\max_{\mu^{i}}\min_{\mu^{-i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v^{i}_{t})(s)\mu^{-i}}_{\hat{E}_{3}}$
$\displaystyle+\underbrace{|\max_{\mu^{i}}\min_{\mu^{-i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v^{i}_{t})(s)\mu^{-i}-\max_{\mu^{i}}\min_{\mu^{-i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v_{*}^{i})(s)\mu^{-i}|}_{\hat{E}_{4}}.$
(49)

We next bound the terms $\\{\hat{E}_{j}\\}_{1\leq j\leq 4}$. For any
$v_{1}^{i},v_{2}^{i}\in\mathbb{R}^{|\mathcal{S}|}$, we have for any
$(s,a^{i},a^{-i})$ that

$\displaystyle|\mathcal{T}^{i}(v_{1}^{i})(s,a^{i},a^{-i})-\mathcal{T}^{i}(v_{2}^{i})(s,a^{i},a^{-i})|$
$\displaystyle=\;$
$\displaystyle\gamma|\mathbb{E}[v_{1}^{i}(S_{1})-v_{2}^{i}(S_{1})\mid
S_{0}=s,A_{0}^{i}=a^{i},A_{0}^{-i}=a^{-i}]|$ $\displaystyle\leq\;$
$\displaystyle\gamma\|v_{1}^{i}-v_{2}^{i}\|_{\infty},$

which implies
$\|\mathcal{T}^{i}(v_{1}^{i})-\mathcal{T}^{i}(v_{2}^{i})\|_{\infty}\leq\gamma\|v_{1}^{i}-v_{2}^{i}\|_{\infty}$.
As a result, we have

$\displaystyle\hat{E}_{1}\leq\;$
$\displaystyle\|\mathcal{T}^{i}(v^{i}_{*,\pi_{t,K}^{-i}})-\mathcal{T}^{i}(v^{i}_{*})\|_{\infty}\leq\gamma\|v^{i}_{*,\pi_{t,K}^{-i}}-v^{i}_{*}\|_{\infty},$
$\displaystyle\hat{E}_{2}\leq\;$
$\displaystyle\|\mathcal{T}^{i}(v_{t}^{i})-\mathcal{T}^{i}(v^{i}_{*})\|_{\infty}\leq\gamma\|v^{i}_{t}-v^{i}_{*}\|_{\infty},$
$\displaystyle\hat{E}_{4}\leq\;$
$\displaystyle\|\mathcal{T}^{i}(v_{t}^{i})-\mathcal{T}^{i}(v^{i}_{*})\|_{\infty}\leq\gamma\|v^{i}_{t}-v^{i}_{*}\|_{\infty}.$

Bounding the term $\hat{E}_{3}$ requires more effort. First observe that

$\displaystyle\hat{E}_{3}\leq\;$
$\displaystyle\left|\max_{\mu^{i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v_{t}^{i})(s)\pi_{t,K}^{-i}(s)-\min_{\mu^{-i}}\pi_{t,K}^{i}(s)\mathcal{T}^{i}(v_{t}^{i})(s)\mu^{-i}\right|$
$\displaystyle\leq\;$
$\displaystyle\left|\max_{\mu^{-i}}(\mu^{-i})^{\top}\mathcal{T}^{-i}(v_{t}^{-i})(s)\pi_{t,K}^{i}(s)+\min_{\mu^{-i}}(\mu^{-i})^{\top}\mathcal{T}^{i}(v_{t}^{i})(s)^{\top}\pi_{t,K}^{i}(s)\right|$
$\displaystyle+\left|\sum_{i=1,2}\max_{\mu^{i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v_{t}^{i})(s)\pi_{t,K}^{-i}(s)\right|$
$\displaystyle\leq\;$
$\displaystyle\left|\max_{\mu^{-i}}(\mu^{-i})^{\top}\mathcal{T}^{-i}(v_{t}^{-i})(s)\pi_{t,K}^{i}(s)-\max_{\mu^{-i}}(\mu^{-i})^{\top}[-\mathcal{T}^{i}(v_{t}^{i})(s)]^{\top}\pi_{t,K}^{i}(s)\right|$
$\displaystyle+\left|\sum_{i=1,2}\max_{\mu^{i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v_{t}^{i})(s)\pi_{t,K}^{-i}(s)\right|$
$\displaystyle\leq\;$
$\displaystyle\max_{\mu^{-i}}\left|(\mu^{-i})^{\top}(\mathcal{T}^{-i}(v_{t}^{-i})(s)+[\mathcal{T}^{i}(v_{t}^{i})(s)]^{\top})\pi_{t,K}^{i}(s)\right|$
$\displaystyle+\left|\sum_{i=1,2}\max_{\mu^{i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v_{t}^{i})(s)\pi_{t,K}^{-i}(s)\right|$
$\displaystyle\leq\;$
$\displaystyle\max_{a^{i},a^{-i}}\left|\mathcal{T}^{i}(v_{t}^{i})(s,a^{i},a^{-i})+\mathcal{T}^{-i}(v_{t}^{-i})(s,a^{i},a^{-i})\right|$
$\displaystyle+\left|\sum_{i=1,2}\max_{\mu^{i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v_{t}^{i})(s)\pi_{t,K}^{-i}(s)\right|$
$\displaystyle\leq\;$
$\displaystyle\gamma\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}+\left|\sum_{i=1,2}\max_{\mu^{i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v_{t}^{i})(s)\pi_{t,K}^{-i}(s)\right|,$

where the last line follows from

$\displaystyle|\mathcal{T}^{i}(v_{t}^{i})(s,a^{i},a^{-i})+\mathcal{T}^{-i}(v_{t}^{-i})(s,a^{i},a^{-i})|$
$\displaystyle=\;$
$\displaystyle\gamma|\mathbb{E}[v_{t}^{i}(S_{1})+v_{t}^{i}(S_{1})\mid
S_{0}=s,A_{0}^{i}=a^{i},A_{0}^{-i}=a^{-i}]|$ $\displaystyle\leq\;$
$\displaystyle\gamma\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}.$

In addition, we have

$\displaystyle\left|\sum_{i=1,2}\max_{\mu^{i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v_{t}^{i})(s)\pi_{t,K}^{-i}(s)\right|$
$\displaystyle=\;$
$\displaystyle\left|\sum_{i=1,2}\left\\{\max_{\mu^{i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)-(\pi_{t,K}^{i}(s))^{\top}\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)\right\\}\right|$
$\displaystyle+\left|\sum_{i=1,2}(\pi_{t,K}^{i}(s))^{\top}\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)\right|$
$\displaystyle=\;$
$\displaystyle\sum_{i=1,2}\left\\{\max_{\mu^{i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)-(\pi_{t,K}^{i}(s))^{\top}\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)\right\\}$
$\displaystyle+\left|\sum_{i=1,2}(\pi_{t,K}^{i}(s))^{\top}\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)\right|$
$\displaystyle\leq\;$
$\displaystyle\sum_{i=1,2}\max_{\mu^{i}}\left\\{(\mu^{i}-\pi_{t,K}^{i}(s))^{\top}\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)+\tau\nu(\mu^{i})-\tau\nu(\pi_{t,K}^{i}(s))\right\\}+2\tau\log(A_{\max})$
$\displaystyle+\left|\sum_{i=1,2}(\pi_{t,K}^{i}(s))^{\top}\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)\right|$
$\displaystyle=\;$ $\displaystyle
V_{v_{t},s}(\pi_{t,K}^{i}(s),\pi_{t,K}^{-i}(s))+2\tau\log(A_{\max})+\left|\sum_{i=1,2}(\pi_{t,K}^{i}(s))^{\top}\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)\right|$
$\displaystyle\leq\;$ $\displaystyle
V_{v_{t},s}(\pi_{t,K}^{i}(s),\pi_{t,K}^{-i}(s))+2\tau\log(A_{\max})$
$\displaystyle+\max_{a^{i},a^{-i}}\left|\mathcal{T}^{i}(v_{t}^{i})(s,a^{i},a^{-i})+\mathcal{T}^{-i}(v_{t}^{-i})(s,a^{i},a^{-i})\right|$
$\displaystyle\leq\;$ $\displaystyle
V_{v_{t},s}(\pi_{t,K}^{i}(s),\pi_{t,K}^{-i}(s))+2\tau\log(A_{\max})+\gamma\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}.$

It follows that

$\displaystyle\hat{E}_{3}\leq
2\gamma\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}+\max_{s}V_{v_{t},s}(\pi_{t,K}^{i}(s),\pi_{t,K}^{-i}(s))+2\tau\log(A_{\max}).$
(50)

Substituting the upper bounds we obtained for the terms $\\{E_{j}\\}_{1\leq
j\leq 4}$ into Eq. (49) and we have

$\displaystyle\|v^{-i}_{*}-v^{-i}_{\pi_{t,K}^{-i},*}\|_{\infty}\leq\;$
$\displaystyle\gamma\|v^{i}_{*,\pi_{t,K}^{-i}}-v^{i}_{*}\|_{\infty}+2\gamma\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}+2\gamma\|v^{i}_{t}-v^{i}_{*}\|_{\infty}$
$\displaystyle+\max_{s}V_{v_{t},s}(\pi_{t,K}^{i}(s),\pi_{t,K}^{-i}(s))+2\tau\log(A_{\max})$
$\displaystyle=\;$
$\displaystyle\gamma\|v^{-i}_{*}-v^{-i}_{\pi_{t,K}^{-i},*}\|_{\infty}+2\gamma\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}+2\gamma\|v^{i}_{t}-v^{i}_{*}\|_{\infty}$
$\displaystyle+\max_{s}V_{v_{t},s}(\pi_{t,K}^{i}(s),\pi_{t,K}^{-i}(s))+2\tau\log(A_{\max}),$

which after rearranging terms implies

$\displaystyle\|v^{-i}_{*}-v^{-i}_{\pi_{t,K}^{-i},*}\|_{\infty}\leq\;$
$\displaystyle\frac{1}{1-\gamma}\bigg{(}2\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}+2\|v^{i}_{t}-v^{i}_{*}\|_{\infty}$
$\displaystyle+\max_{s}V_{v_{t},s}(\pi_{t,K}^{i}(s),\pi_{t,K}^{-i}(s))+2\tau\log(A_{\max})\bigg{)}.$

Similarly, we also have

$\displaystyle\|v^{i}_{*}-v^{i}_{\pi_{t,K}^{i},*}\|_{\infty}\leq\;$
$\displaystyle\frac{1}{1-\gamma}\bigg{(}2\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}+2\|v^{i}_{t}-v^{i}_{*}\|_{\infty}$
$\displaystyle+\max_{s}V_{v_{t},s}(\pi_{t,K}^{i}(s),\pi_{t,K}^{-i}(s))+2\tau\log(A_{\max})\bigg{)}.$

Substituting the previous two inequalities into Eq. (48) and we finally obtain

$\displaystyle\|v^{i}_{*,\pi_{t,K}^{-i}}-v^{i}_{\pi_{t,K}^{i},\pi_{t,K}^{-i}}\|_{\infty}\leq\;$
$\displaystyle\frac{2}{1-\gamma}\bigg{(}2\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}+2\|v^{i}_{t}-v^{i}_{*}\|_{\infty}$
$\displaystyle+\max_{s}V_{v_{t},s}(\pi_{t,K}^{i}(s),\pi_{t,K}^{-i}(s))+2\tau\log(A_{\max})\bigg{)}.$

####  A.7.6 Proof of Lemma A.5

For any $i\in\\{1,2\\}$, we have by the outer-loop update equation (cf. Line
$8$) of Algorithm 2 that

$\displaystyle v_{t+1}^{i}(s)=\;$
$\displaystyle\pi_{t,K}^{i}(s)^{\top}q_{t,K}^{i}(s)$ $\displaystyle=\;$
$\displaystyle\textit{val}^{i}(\mathcal{T}^{i}(v^{i}_{t})(s))+\pi_{t,K}^{i}(s)^{\top}q_{t,K}^{i}(s)-\textit{val}^{i}(\mathcal{T}^{i}(v^{i}_{t})(s))$

Since
$\textit{val}^{i}(\mathcal{T}^{i}(v_{*}^{i})(s))=\mathcal{B}^{i}(v_{*}^{i})(s)=v_{*}^{i}(s)$,
we have

$\displaystyle|v_{t+1}^{i}(s)-v_{*}^{i}(s)|=\;$
$\displaystyle|\textit{val}^{i}(\mathcal{T}^{i}(v^{i}_{t})(s))-\textit{val}^{i}(\mathcal{T}^{i}(v_{*}^{i})(s))|$
$\displaystyle+|\pi_{t,K}^{i}(s)^{\top}q_{t,K}^{i}(s)-\textit{val}^{i}(\mathcal{T}^{i}(v^{i}_{t})(s))|.$
(51)

For the first term on the RHS of Eq. (51), we have by the contraction property
of the minimax Bellman operator that

$\displaystyle\left|\textit{val}^{i}(\mathcal{T}^{i}(v^{i}_{t})(s))-\textit{val}^{i}(\mathcal{T}^{i}(v_{*}^{i})(s))\right|=\;$
$\displaystyle\left|\mathcal{B}^{i}(v_{t}^{i})(s)-\mathcal{B}^{i}(v_{*}^{i})(s)\right|$
$\displaystyle\leq\;$ $\displaystyle\gamma\|v^{i}_{t}-v_{*}^{i}\|_{\infty}.$

For the second term on the RHS of Eq. (51), we have

$\displaystyle\left|\pi_{t,K}^{i}(s)^{\top}q_{t,K}^{i}(s)-\textit{val}^{i}(\mathcal{T}^{i}(v^{i}_{t})(s))\right|\leq\;$
$\displaystyle\underbrace{\left|\max_{\mu^{i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)-\pi_{t,K}^{i}(s)^{\top}q_{t,K}^{i}(s)\right|}_{T_{1}}$
$\displaystyle+\underbrace{\left|\max_{\mu^{i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)-\textit{val}^{i}(\mathcal{T}^{i}(v^{i}_{t})(s))\right|}_{T_{2}}$

For the term $T_{1}$, we have

$\displaystyle T_{1}\leq\;$
$\displaystyle\left|\max_{\mu^{i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)-(\pi_{t,K}^{i}(s))^{\top}\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)\right|$
$\displaystyle+\left|(\pi_{t,K}^{i}(s))^{\top}\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)-\pi_{t,K}^{i}(s)^{\top}q_{t,K}^{i}(s)\right|$
$\displaystyle\leq\;$
$\displaystyle\max_{\mu^{i}}(\mu^{i})^{\top}\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)-(\pi_{t,K}^{i}(s))^{\top}\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)$
$\displaystyle+\|\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)-q_{t,K}^{i}(s)\|_{\infty}$
$\displaystyle\leq\;$
$\displaystyle\sum_{i=1,2}\left\\{\max_{\mu^{i}}(\mu^{i}-\pi_{t,K}^{i}(s))^{\top}\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)\right\\}$
$\displaystyle+\|\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)-q_{t,K}^{i}(s)\|_{\infty}$
$\displaystyle\leq\;$
$\displaystyle\sum_{i=1,2}\left\\{\max_{\mu^{i}}(\mu^{i}-\pi_{t,K}^{i}(s))^{\top}\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)+\tau\nu(\mu^{i})-\tau\nu(\pi_{t,K}^{i}(s))\right\\}$
$\displaystyle+2\tau\log(A_{\max})+\|\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)-q_{t,K}^{i}(s)\|_{\infty}$
$\displaystyle\leq\;$ $\displaystyle
V_{v_{t},s}(\pi_{t,K}^{i}(s),\pi_{t,K}^{-i}(s))+2\tau\log(A_{\max})+\|\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)-q_{t,K}^{i}(s)\|_{\infty}.$

Note that $T_{2}$ is exactly the term $\hat{E}_{3}$ we analyzed in proving
Lemma A.4. Therefore, we have from Eq. (50) that

$\displaystyle T_{2}\leq
2\gamma\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}+\max_{s}V_{v_{t},s}(\pi_{t,K}^{i}(s),\pi_{t,K}^{-i}(s))+2\tau\log(A_{\max}).$

It follows that

$\displaystyle\left|\pi_{t,K}^{i}(s)^{\top}q_{t,K}^{i}(s)-\textit{val}^{i}(\mathcal{T}^{i}(v^{i}_{t})(s))\right|$
$\displaystyle\leq\;$ $\displaystyle T_{1}+T_{2}$ $\displaystyle\leq\;$
$\displaystyle
2\max_{s}V(\pi_{t,K}^{i}(s),\pi_{t,K}^{-i}(s))+\max_{s}\|\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)-q_{t,K}^{i}(s)\|_{\infty}$
$\displaystyle+2\gamma\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}+4\tau\log(A_{\max}).$

Using the upper bounds we obtained for the two terms on the RHS of Eq. (51)
and we have

$\displaystyle|v_{t+1}^{i}(s)-v_{*}^{i}(s)|\leq\;$
$\displaystyle\gamma\|v_{t}^{i}-v_{*}^{i}\|_{\infty}+2\max_{s\in\mathcal{S}}V(\pi_{t,K}^{i}(s),\pi_{t,K}^{-i}(s))+4\tau\log(A_{\max})$
$\displaystyle+\max_{s\in\mathcal{S}}\|\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)-q_{t,K}^{i}(s)\|_{\infty}+2\gamma\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}.$

Since the RHS of the previous inequality does not depend on $s$, we have for
any $i\in\\{1,2\\}$ that

$\displaystyle\|v_{t+1}^{i}-v_{*}^{i}\|_{\infty}\leq\;$
$\displaystyle\gamma\|v_{t}^{i}-v_{*}^{i}\|_{\infty}+2\max_{s\in\mathcal{S}}V(\pi_{t,K}^{i}(s),\pi_{t,K}^{-i}(s))+4\tau\log(A_{\max})$
$\displaystyle+\max_{s\in\mathcal{S}}\|\mathcal{T}^{i}(v^{i}_{t})(s)\pi_{t,K}^{-i}(s)-q_{t,K}^{i}(s)\|_{\infty}+2\gamma\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}.$

####  A.7.7 Proof of Lemma A.6

Using the outer-loop update equation (cf. Algorithm 2 Line $8$) and we have

$\displaystyle\left|\sum_{i=1,2}v_{t+1}^{i}(s)\right|=\;$
$\displaystyle\sum_{i=1,2}\pi_{t,K}^{i}(s)^{\top}q_{t,K}^{i}(s)$
$\displaystyle=\;$
$\displaystyle\left|\sum_{i=1,2}\pi_{t,K}^{i}(s)^{\top}(q_{t,K}^{i}(s)-\mathcal{T}^{i}(v_{t}^{i})(s)\pi_{t,K}^{-i}(s))\right|$
$\displaystyle+\left|\sum_{i=1,2}\pi_{t,K}^{i}(s)\mathcal{T}^{i}(v_{t}^{i})(s)\pi_{t,K}^{-i}(s)\right|$
$\displaystyle\leq\;$
$\displaystyle\sum_{i=1,2}\max_{s\in\mathcal{S}}\|q_{t,K}^{i}(s)-\mathcal{T}^{i}(v_{t}^{i})(s)\pi_{t,K}^{-i}(s)\|_{\infty}$
$\displaystyle+\max_{(s,a^{i},a^{-i})}\left|\mathcal{T}^{i}(v_{t}^{i})(s,a^{i},a^{-i})+\mathcal{T}^{-i}(v_{t}^{-i})(s,a^{i},a^{-i})\right|$
$\displaystyle\leq\;$
$\displaystyle\sum_{i=1,2}\max_{s\in\mathcal{S}}\|q_{t,K}^{i}(s)-\mathcal{T}^{i}(v_{t}^{i})(s)\pi_{t,K}^{-i}(s)\|_{\infty}+\gamma\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}.$

Since the RHS of the previous inequality does not depend on $s$, we in fact
have

$\displaystyle\|v_{t+1}^{i}+v_{t+1}^{-i}\|_{\infty}\leq\gamma\|v_{t}^{i}+v_{t}^{-i}\|_{\infty}+\sum_{i=1,2}\max_{s\in\mathcal{S}}\|q_{t,K}^{i}(s)-\mathcal{T}^{i}(v_{t}^{i})(s)\pi_{t,K}^{-i}(s)\|_{\infty}.$

####  A.7.8 Proof of Lemma A.7

To begin with, observe that

$\displaystyle{\arg\max}_{\hat{\mu}^{i}\in\Delta^{|\mathcal{A}^{i}|}}\left\\{(\hat{\mu}^{i})^{\top}X_{i}\mu^{-i}+\tau\nu(\hat{\mu}^{i})\right\\}=\sigma_{\tau}(X_{i}\mu^{-i}).$

Therefore, the function $V_{X}(\cdot,\cdot)$ can be equivalently written as

$\displaystyle
V_{X}(\mu^{i},\mu^{-i})=\sum_{i=1,2}\left[(\sigma_{\tau}(X_{i}\mu^{-i}))^{\top}X_{i}\mu^{-i}+\tau\nu(\sigma_{\tau}(X_{i}\mu^{-i}))-(\mu^{i})^{\top}X_{i}\mu^{-i}-\tau\nu(\mu^{i})\right],$

which will frequently used in our analysis.

  1. (1)

It is clear that the function $V_{X}(\cdot,\cdot)$ is by definition non-
negative. The strong convexity follows from the following two observations.

    1. (i)

The negative entropy $-\nu(\cdot)$ is $1$ – strongly convex with respect to
$\|\cdot\|_{2}$ (Beck, , 2017, Example 5.27).

    2. (ii)

The following function of $\mu^{i}$

$\displaystyle(\sigma_{\tau}(X_{-i}\mu^{i}))^{\top}X_{-i}\mu^{i}+\tau\nu(\sigma_{\tau}(X_{-i}\mu^{i}))=\max_{\hat{\mu}^{-i}\in\Delta^{|\mathcal{A}^{-i}|}}\left\\{(\hat{\mu}^{-i})^{\top}X_{-i}\mu^{i}+\tau\nu(\hat{\mu}^{-i})\right\\}$

is the maximum of linear functions in $\mu^{i}$, and hence is convex.

Therefore, the function $V_{X}(\mu^{i},\mu^{-i})$ is $\tau$ – strongly convex
in $\mu^{i}$ with respect to $\|\cdot\|_{2}$ uniformly for all $\mu^{-i}$.

  2. (2)

The smoothness follows from the following two results.

    1. (i)

Since the Hessian matrix of the negative entropy function $-\nu(\mu^{i})$
satisfies

$\displaystyle
H_{-\nu}(\mu^{i})=\text{diag}\left(\frac{1}{\mu^{i}(a_{1}^{i})},\cdots,\frac{1}{\mu^{i}(a_{n}^{i})}\right)\leq\frac{I_{|\mathcal{A}^{i}|}}{\delta_{i}}$

for all $\mu^{i}\in\Delta^{|\mathcal{A}^{i}|}$ satisfying
$\min_{a^{i}\in\mathcal{A}^{i}}\mu^{i}(a^{i})\geq\delta_{i}$, we have from the
second order characterization of smoothness that $-\nu(\mu^{i})$ is a
$\frac{1}{\delta_{i}}$ – smooth function on
$\\{\mu^{i}\in\Delta^{|\mathcal{A}^{i}|}\mid\mu^{i}(a^{i})\geq\delta_{i},\forall\;a^{i}\in\mathcal{A}^{i}\\}$
with respect to $\|\cdot\|_{2}$ .

    2. (ii)

Using the optimality condition and we have

$\displaystyle\nabla_{\mu^{i}}(\sigma_{\tau}(X_{-i}\mu^{i}))^{\top}X_{-i}\mu^{i}+\tau\nu(\sigma_{\tau}(X_{-i}\mu^{i}))$
$\displaystyle=\;$
$\displaystyle\nabla_{\mu^{i}}\max_{\hat{\mu}^{-i}\in\Delta^{|\mathcal{A}^{-i}|}}\left\\{(\hat{\mu}^{-i})^{\top}X_{-i}\mu^{i}+\tau\nu(\hat{\mu}^{-i})\right\\}$
$\displaystyle=\;$ $\displaystyle X_{-i}^{\top}\sigma_{\tau}(X_{-i}\mu^{i}).$

Therefore, using the formula for the gradient of the softmax function (Gao and
Pavel, , 2017), the Hessian $H(\mu^{i})$ of the function
$(\sigma_{\tau}(X_{-i}\mu^{i}))^{\top}X_{-i}\mu^{i}+\tau\nu(\sigma_{\tau}(X_{-i}\mu^{i}))$
satisfies

$\displaystyle H(\mu^{i})=\;$
$\displaystyle\frac{1}{\tau}X_{-i}^{\top}(\text{diag}(\sigma_{\tau}(X_{-i}\mu^{i}))-\sigma_{\tau}(X_{-i}\mu^{i})\sigma_{\tau}(X_{-i}\mu^{i})^{\top})X_{-i}$
$\displaystyle\leq\;$
$\displaystyle\frac{1}{\tau}X_{-i}^{\top}\text{diag}(\sigma_{\tau}(X_{-i}\mu^{i}))X_{-i}$
$\displaystyle\leq\;$ $\displaystyle\frac{1}{\tau}X_{-i}^{\top}X_{-i}$
$\displaystyle\leq\;$
$\displaystyle\frac{\sigma^{2}_{\max}(X_{-i})}{\tau}I_{|\mathcal{A}^{i}|}$

Using the second order characterization of smoothness and we conclude that the
function
$(\sigma_{\tau}(X_{-i}\mu^{i}))^{\top}X_{-i}\mu^{i}+\tau\nu(\sigma_{\tau}(X_{-i}\mu^{i}))$
is $\frac{\sigma^{2}_{\max}(X_{-i})}{\tau}$ – smooth with respect to
$\|\cdot\|_{2}$.

Combining (i) and (ii) and we conclude that the function
$V_{X}(\mu^{i},\mu^{-i})$ is a
$(\frac{\sigma_{\max}^{2}(X_{-i})}{\tau}+\frac{\tau}{\delta_{i}})$ – smooth
function on
$\\{\mu^{i}\in\Delta^{|\mathcal{A}^{i}|}\mid\mu^{i}(a^{i})\geq\delta_{i},\forall\;a^{i}\in\mathcal{A}^{i}\\}$
with respect to $\|\cdot\|_{2}$ uniformly for all $\mu^{-i}$.

  3. (3)

We first compute the gradient $\nabla_{1}V_{X}(\mu^{i},\mu^{-i})$ using
Danskin’s theorem:

$\displaystyle\nabla_{1}V_{X}(\mu^{i},\mu^{-i})=-(X_{i}+X_{-i}^{\top})\mu^{-i}-\tau\nabla\nu(\mu^{i})+X_{-i}^{\top}\sigma_{\tau}(X_{-i}\mu^{i}).$
(52)

It follows that

$\displaystyle\langle\nabla_{1}V_{X}(\mu^{i},\mu^{-i}),\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i}\rangle$
$\displaystyle=\;$
$\displaystyle\langle-(X_{i}+X_{-i}^{\top})\mu^{-i}-\tau\nabla\nu(\mu^{i})+X_{-i}^{\top}\sigma_{\tau}(X_{-i}\mu^{i}),\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i}\rangle$
$\displaystyle=\;$
$\displaystyle\langle-(X_{i}+X_{-i}^{\top})\mu^{-i}-\tau\nabla\nu(\mu^{i})+X_{-i}^{\top}\sigma_{\tau}(X_{-i}\mu^{i}),\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i}\rangle$
$\displaystyle+\langle
X_{i}\mu^{-i}+\tau\nabla\nu(\sigma_{\tau}(X_{i}\mu^{-i})),\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i}\rangle$
(53) $\displaystyle=\;$
$\displaystyle\tau\langle\nabla\nu(\sigma_{\tau}(X_{i}\mu^{-i}))-\nabla\nu(\mu^{i}),\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i}\rangle$
$\displaystyle+(\sigma_{\tau}(X_{-i}\mu^{i})-\mu^{-i})^{\top}X_{-i}(\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i}).$

where Eq. (53) is due to the optimality condition
$X_{i}\mu^{-i}+\tau\nabla\nu(\sigma_{\tau}(X_{i}\mu^{-i}))=0$. To proceed,
observe that the concavity of $\nu(\cdot)$ and the optimality condition
$X_{i}\mu^{-i}+\tau\nabla\nu(\sigma_{\tau}(X_{i}\mu^{-i}))=0$ together imply
that

$\displaystyle\langle\nabla\nu(\sigma_{\tau}(X_{i}\mu^{-i}))-\nabla\nu(\mu^{i}),\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i}\rangle$
$\displaystyle=\;$
$\displaystyle\langle\nabla\nu(\mu^{i})-\nabla\nu(\sigma_{\tau}(X_{i}\mu^{-i})),\mu^{i}-\sigma_{\tau}(X_{i}\mu^{-i})\rangle$
$\displaystyle=\;$
$\displaystyle\langle\nabla\nu(\mu^{i}),\mu^{i}-\sigma_{\tau}(X_{i}\mu^{-i})\rangle-\langle\nabla\nu(\sigma_{\tau}(X_{i}\mu^{-i})),\mu^{i}-\sigma_{\tau}(X_{i}\mu^{-i})\rangle$
$\displaystyle\leq\;$
$\displaystyle\nu(\mu^{i})-\nu(\sigma_{\tau}(X_{i}\mu^{-i}))-\langle\nabla\nu(\sigma_{\tau}(X_{i}\mu^{-i})),\mu^{i}-\sigma_{\tau}(X_{i}\mu^{-i})\rangle$
$\displaystyle=\;$
$\displaystyle\nu(\mu^{i})-\nu(\sigma_{\tau}(X_{i}\mu^{-i}))+\frac{1}{\tau}\langle
X_{i}\mu^{-i},\mu^{i}-\sigma_{\tau}(X_{i}\mu^{-i})\rangle$ $\displaystyle=\;$
$\displaystyle\frac{1}{\tau}\left[(\mu^{i})^{\top}X_{i}\mu^{-i}+\tau\nu(\mu^{i})-\max_{\hat{\mu}^{i}\in\Delta^{|\mathcal{A}^{i}|}}\left\\{(\hat{\mu}^{i})^{\top}X_{i}\mu^{-i}+\tau\nu(\hat{\mu}^{i})\right\\}\right].$

Therefore, we have

$\displaystyle\langle\nabla_{1}V_{X}(\mu^{i},\mu^{-i}),\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i}\rangle$
$\displaystyle\leq\;$
$\displaystyle\left[(\mu^{i})^{\top}X_{i}\mu^{-i}+\tau\nu(\mu^{i})-\max_{\hat{\mu}^{i}\in\Delta^{|\mathcal{A}^{i}|}}\left\\{(\hat{\mu}^{i})^{\top}X_{i}\mu^{-i}+\tau\nu(\hat{\mu}^{i})\right\\}\right]$
$\displaystyle+(\sigma_{\tau}(X_{-i}\mu^{i})-\mu^{-i})^{\top}X_{-i}(\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i})$

Similarly, we also have

$\displaystyle\langle\nabla_{2}V_{X}(\mu^{i},\mu^{-i}),\sigma_{\tau}(X_{-i}\mu^{i})-\mu^{-i}\rangle$
$\displaystyle\leq\;$
$\displaystyle\left[(\mu^{-i})^{\top}X_{-i}\mu^{i}+\tau\nu(\mu^{-i})-\max_{\hat{\mu}^{-i}\in\Delta^{|\mathcal{A}^{-i}|}}\left\\{(\hat{\mu}^{-i})^{\top}X_{-i}\mu^{i}+\tau\nu(\hat{\mu}^{-i})\right\\}\right]$
$\displaystyle+(\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i})^{\top}X_{i}(\sigma_{\tau}(X_{-i}\mu^{i})-\mu^{-i})$

Adding up the previous two inequalities and we obtain

$\displaystyle\langle\nabla_{1}V_{X}(\mu^{i},\mu^{-i}),\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i}\rangle+\langle\nabla_{2}V_{X}(\mu^{i},\mu^{-i}),\sigma_{\tau}(X_{-i}\mu^{i})-\mu^{-i}\rangle$
$\displaystyle\leq\;$ $\displaystyle-
V_{X}(\mu^{i},\mu^{-i})+(\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i})^{\top}(X_{i}+X_{-i}^{\top})(\sigma_{\tau}(X_{-i}\mu^{i})-\mu^{-i}).$
(54)

To control the second term on the RHS of Eq. (54), observe that

$\displaystyle(\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i})^{\top}(X_{i}+X_{-i}^{\top})(\sigma_{\tau}(X_{-i}\mu^{i})-\mu^{-i})$
$\displaystyle\leq\;$
$\displaystyle\|\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i}\|_{2}\|X_{i}+X_{-i}^{\top}\|_{2}\|\sigma_{\tau}(X_{-i}\mu^{i})-\mu^{-i}\|_{2}$
$\displaystyle\leq\;$
$\displaystyle(\|\sigma_{\tau}(X_{i}\mu^{-i})\|_{2}+\|\mu^{i}\|_{2})\|X_{i}+X_{-i}^{\top}\|_{2}\|\sigma_{\tau}(X_{-i}\mu^{i})-\mu^{-i}\|_{2}$
$\displaystyle\leq\;$ $\displaystyle
2\|X_{i}+X_{-i}^{\top}\|_{2}\|\sigma_{\tau}(X_{-i}\mu^{i})-\mu^{-i}\|_{2}$
$\displaystyle\leq\;$ $\displaystyle
c_{1}\|X_{i}+X_{-i}^{\top}\|_{2}^{2}+\frac{1}{c_{1}}\|\sigma_{\tau}(X_{-i}\mu^{i})-\mu^{-i}\|_{2}^{2}$
$\displaystyle\leq\;$ $\displaystyle
c_{1}\|X_{i}+X_{-i}^{\top}\|_{2}^{2}+\frac{1}{c_{1}}(\|\sigma_{\tau}(X_{-i}\mu^{i})-\mu^{-i}\|_{2}^{2}+\|\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i}\|_{2}^{2}).$
(55)

To proceed, note that the function

$\displaystyle
F_{X_{i}}(\mu^{i},\mu^{-i}):=\max_{\hat{\mu}^{i}}\left\\{(\hat{\mu}^{i}-\mu^{i})^{\top}X_{i}\mu^{-i}+\tau\nu(\hat{\mu}^{i})-\tau\nu(\mu^{i})\right\\}$

is a $\tau$-strongly convex function of $\mu^{i}$ uniformly for all
$\mu^{-i}$. Therefore, we have

$\displaystyle F_{X_{i}}(\mu^{i},\mu^{-i})=\;$ $\displaystyle
F_{X_{i}}(\mu^{i},\mu^{-i})-F_{X_{i}}(\sigma_{\tau}(X_{i}\mu^{-i}),\mu^{-i})$
$\displaystyle=\;$ $\displaystyle
F_{X_{i}}(\mu^{i},\mu^{-i})-\min_{\mu^{i}}F_{X_{i}}(\mu^{i},\mu^{-i})$
$\displaystyle\geq\;$
$\displaystyle\frac{\tau}{2}\|\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i}\|_{2}^{2},$

which is called the quadratic growth property in optimization literature. It
follows that

$\displaystyle\|\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i}\|_{2}^{2}\leq\frac{2}{\tau}\max_{\hat{\mu}^{i}}\left\\{(\hat{\mu}^{i}-\mu^{i})^{\top}X_{i}\mu^{-i}+\tau\nu(\hat{\mu}^{i})-\tau\nu(\mu^{i})\right\\}.$

Similarly, we also have

$\displaystyle\|\sigma_{\tau}(X_{-i}\mu^{i})-\mu^{-i}\|_{2}^{2}\leq\frac{2}{\tau}\max_{\hat{\mu}^{-i}}\left\\{(\hat{\mu}^{-i}-\mu^{-i})^{\top}X_{-i}\mu^{i}+\tau\nu(\hat{\mu}^{-i})-\tau\nu(\mu^{-i})\right\\}.$

Adding up the previous two inequalities and we have

$\displaystyle\|\sigma_{\tau}(X_{-i}\mu^{i})-\mu^{-i}\|_{2}^{2}+\|\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i}\|_{2}^{2}\leq\frac{2}{\tau}V_{X}(\mu^{i},\mu^{-i}).$

Using the previous inequality in Eq. (55) and we have

$\displaystyle(\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i})^{\top}(X_{i}+X_{-i}^{\top})(\sigma_{\tau}(X_{-i}\mu^{i})-\mu^{-i})$
$\displaystyle\leq\;$ $\displaystyle
c_{1}\|X_{i}+X_{-i}^{\top}\|_{2}^{2}+\frac{1}{c_{1}}(\|\sigma_{\tau}(X_{-i}\mu^{i})-\mu^{-i}\|_{2}^{2}+\|\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i}\|_{2}^{2})$
$\displaystyle\leq\;$ $\displaystyle
c_{1}\|X_{i}+X_{-i}^{\top}\|_{2}^{2}+\frac{2}{c_{1}\tau}V_{X}(\mu^{i},\mu^{-i})$
$\displaystyle=\;$
$\displaystyle\frac{16}{\tau}\|X_{i}+X_{-i}^{\top}\|_{2}^{2}+\frac{1}{8}V_{X}(\mu^{i},\mu^{-i}),$

where the last line follows from choosing $c_{1}=16/\tau$. Using the previous
inequality in Eq. (54) and we obtain

$\displaystyle\langle\nabla_{1}V_{X}(\mu^{i},\mu^{-i}),\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i}\rangle+\langle\nabla_{2}V_{X}(\mu^{i},\mu^{-i}),\sigma_{\tau}(X_{-i}\mu^{i})-\mu^{-i}\rangle$
$\displaystyle\leq\;$
$\displaystyle-\frac{7}{8}V_{X}(\mu^{i},\mu^{-i})+\frac{16}{\tau}\|X_{i}+X_{-i}^{\top}\|_{2}^{2}.$

  4. (4)

For any $u^{i}\in\mathbb{R}^{|\mathcal{A}^{i}|}$, using the explicit
expression of the gradient of $V_{X}(\cdot,\cdot)$ from Eq. (52) and we have

$\displaystyle\langle\nabla_{1}V_{X}(\mu^{i},\mu^{-i}),\sigma_{\tau}(u^{i})-\sigma_{\tau}(X_{i}\mu^{-i})\rangle$
$\displaystyle=\;$
$\displaystyle\langle-(X_{i}+X_{-i}^{\top})\mu^{-i}-\tau\nabla\nu(\mu^{i})+X_{-i}^{\top}\sigma_{\tau}(X_{-i}\mu^{i}),\sigma_{\tau}(u^{i})-\sigma_{\tau}(X_{i}\mu^{-i})\rangle$
$\displaystyle=\;$
$\displaystyle\langle-(X_{i}+X_{-i}^{\top})\mu^{-i}-\tau\nabla\nu(\mu^{i})+X_{-i}^{\top}\sigma_{\tau}(X_{-i}\mu^{i}),\sigma_{\tau}(u^{i})-\sigma_{\tau}(X_{i}\mu^{-i})\rangle$
$\displaystyle+\langle
X_{i}\mu^{-i}+\tau\nabla\nu(\sigma_{\tau}(X_{i}\mu^{-i})),\sigma_{\tau}(u^{i})-\sigma_{\tau}(X_{i}\mu^{-i})\rangle$
$\displaystyle=\;$
$\displaystyle\tau\langle\nabla\nu(\sigma_{\tau}(X_{i}\mu^{-i}))-\nabla\nu(\mu^{i}),\sigma_{\tau}(u^{i})-\sigma_{\tau}(X_{i}\mu^{-i})\rangle$
$\displaystyle+(\sigma_{\tau}(X_{-i}\mu^{i})-\mu^{-i})^{\top}X_{-i}(\sigma_{\tau}(u^{i})-\sigma_{\tau}(X_{i}\mu^{-i}))$
$\displaystyle\leq\;$
$\displaystyle\tau\|\nabla\nu(\sigma_{\tau}(X_{i}\mu^{-i}))-\nabla\nu(\mu^{i})\|_{2}\|\sigma_{\tau}(u^{i})-\sigma_{\tau}(X_{i}\mu^{-i})\|_{2}$
$\displaystyle+\|\sigma_{\tau}(X_{-i}\mu^{i})-\mu^{-i}\|_{2}\|X_{-i}\|_{2}\|\sigma_{\tau}(u^{i})-\sigma_{\tau}(X_{i}\mu^{-i})\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\frac{\tau}{\delta_{i}}\|\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i}\|_{2}\|\sigma_{\tau}(u^{i})-\sigma_{\tau}(X_{i}\mu^{-i})\|_{2}$
$\displaystyle+\|X_{-i}\|_{2}\|\sigma_{\tau}(X_{-i}\mu^{i})-\mu^{-i}\|_{2}\|\sigma_{\tau}(u^{i})-\sigma_{\tau}(X_{i}\mu^{-i})\|_{2},$

where the last inequality follows from the smoothness of $\nu(\cdot)$ in Lemma
A.7 (2). Similarly, we also have for any
$u^{-i}\in\mathbb{R}^{|\mathcal{A}^{-i}|}$ that

$\displaystyle\langle\nabla_{2}V_{X}(\mu^{i},\mu^{-i}),\sigma_{\tau}(u^{-i})-\sigma_{\tau}(X_{-i}\mu^{i})\rangle$
$\displaystyle\leq\;$
$\displaystyle\frac{\tau}{\delta_{-i}}\|\sigma_{\tau}(X_{-i}\mu^{i})-\mu^{-i}\|_{2}\|\sigma_{\tau}(u^{-i})-\sigma_{\tau}(X_{-i}\mu^{i})\|_{2}$
$\displaystyle+\|X_{i}\|_{2}\|\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i}\|_{2}\|\sigma_{\tau}(u^{-i})-\sigma_{\tau}(X_{i}\mu^{i})\|_{2}.$

Adding up the previous two inequalities and we have

$\displaystyle\langle\nabla_{1}V_{X}(\mu^{i},\mu^{-i}),\sigma_{\tau}(u^{i})-\sigma_{\tau}(X_{i}\mu^{-i})\rangle+\langle\nabla_{2}V_{X}(\mu^{i},\mu^{-i}),\sigma_{\tau}(u^{-i})-\sigma_{\tau}(X_{-i}\mu^{i})\rangle$
$\displaystyle\leq\;$
$\displaystyle\left(\frac{\tau}{\delta_{i}}+\frac{\tau}{\delta_{-i}}+\|X_{i}\|_{2}+\|X_{-i}\|_{2}\right)\left(\|\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i}\|_{2}+\|\sigma_{\tau}(X_{-i}\mu^{i})-\mu^{-i}\|_{2}\right)$
$\displaystyle\times\left(\|\sigma_{\tau}(u^{i})-\sigma_{\tau}(X_{i}\mu^{-i})\|_{2}+\|\sigma_{\tau}(u^{-i})-\sigma_{\tau}(X_{i}\mu^{i})\|_{2}\right)$
$\displaystyle\leq\;$
$\displaystyle\frac{1}{2}\left(\frac{\tau}{\delta_{i}}+\frac{\tau}{\delta_{-i}}+\|X_{i}\|_{2}+\|X_{-i}\|_{2}\right)\bigg{[}\bar{c}\left(\|\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i}\|_{2}+\|\sigma_{\tau}(X_{-i}\mu^{i})-\mu^{-i}\|_{2}\right)^{2}$
$\displaystyle+\frac{1}{\bar{c}}\left(\|\sigma_{\tau}(u^{i})-\sigma_{\tau}(X_{i}\mu^{-i})\|_{2}+\|\sigma_{\tau}(u^{-i})-\sigma_{\tau}(X_{i}\mu^{i})\|_{2}\right)^{2}\bigg{]}$
(This is true for all $\bar{c}>0$) $\displaystyle\leq\;$
$\displaystyle\left(\frac{\tau}{\delta_{i}}+\frac{\tau}{\delta_{-i}}+\|X_{i}\|_{2}+\|X_{-i}\|_{2}\right)\bigg{[}\bar{c}\|\sigma_{\tau}(X_{i}\mu^{-i})-\mu^{i}\|_{2}^{2}+\bar{c}\|\sigma_{\tau}(X_{-i}\mu^{i})-\mu^{-i}\|_{2}^{2}$
$\displaystyle+\frac{1}{\bar{c}}\|\sigma_{\tau}(u^{i})-\sigma_{\tau}(X_{i}\mu^{-i})\|_{2}^{2}+\frac{1}{\bar{c}}\|\sigma_{\tau}(u^{-i})-\sigma_{\tau}(X_{i}\mu^{i})\|_{2}^{2}\bigg{]}$
(This is true because $(a+b)^{2}\leq 2(a^{2}+b^{2})$ for all
$a,b\in\mathbb{R}$) $\displaystyle\leq\;$
$\displaystyle\left(\frac{\tau}{\delta_{i}}+\frac{\tau}{\delta_{-i}}+\|X_{i}\|_{2}+\|X_{-i}\|_{2}\right)\bigg{[}\frac{2\bar{c}}{\tau}V_{X}(\mu^{i},\mu^{-i})+\frac{1}{\bar{c}\tau^{2}}\|u^{i}-X_{i}\mu^{-i}\|_{2}^{2}$
$\displaystyle+\frac{1}{\bar{c}\tau^{2}}\|u^{-i}-X_{i}\mu^{i}\|_{2}^{2}\bigg{]},$

where the last line follows from the quadratic growth property of strongly
convex functions and the Lipschitz continuity of the softmax function (Gao and
Pavel, , 2017).

####  A.7.9 Proof of Lemma A.8

Since $\min_{i=1,2}\min_{s,a^{i}}\pi_{k}^{i}(a^{i}|s)\geq\ell_{\tau}$ (cf.
Lemma A.2), Lemma A.7 (2) implies that the function
$V_{v,s}(\mu^{i},\mu^{-i})$ as a function of $\mu^{i}$ is $L_{\tau,i}$ –
smooth on
$\\{\mu^{i}\in\Delta^{|\mathcal{A}^{i}|}\mid\min_{a^{i}}\mu^{i}(a^{i})\geq\ell_{\tau}\\}$
uniformly for all $\mu^{-i}$, where

$\displaystyle L_{\tau,i}:=\;$
$\displaystyle\frac{\sigma_{\max}^{2}(\mathcal{T}^{-i}(v^{-i})(s))}{\tau}+\frac{\tau}{\ell_{\tau}}.$

We next bound $L_{\tau,i}$ from above. Since $\|v^{i}\|_{\infty}\leq
1/(1-\gamma)$ and $\|v^{-i}\|_{\infty}\leq 1/(1-\gamma)$, we have for any
$(s,a^{i},a^{-i})$ that

$\displaystyle|\mathcal{T}^{-i}(v^{-i})(s,a^{-i},a^{i})|\leq\;$
$\displaystyle|\mathcal{R}^{-i}(s,a^{-i},a^{i})|+\gamma\mathbb{E}[|v^{-i}(S_{1})|\mid
S_{0}=s,A_{0}^{i}=a^{i},A_{0}^{-i}=a^{-i}]$ $\displaystyle\leq\;$
$\displaystyle 1+\frac{\gamma}{1-\gamma}$ $\displaystyle=\;$
$\displaystyle\frac{1}{1-\gamma},$

which implies

$\displaystyle\sigma_{\max}(\mathcal{T}^{-i}(v^{-i})(s))=\;$
$\displaystyle\|\mathcal{T}^{-i}(v^{-i})(s))\|_{2}\leq\frac{\sqrt{|\mathcal{A}^{i}||\mathcal{A}^{-i}|}}{1-\gamma}\leq\frac{A_{\max}}{1-\gamma}.$
(56)

As a result, we have by $\tau\leq 1$ and $\ell_{\tau}\leq 1$ that

$\displaystyle
L_{\tau,i}=\frac{\sigma_{\max}^{2}(\mathcal{T}^{-i}(v^{-i})(s))}{\tau}+\frac{\tau}{\ell_{\tau}}\leq\frac{A_{\max}^{2}}{\tau(1-\gamma)^{2}}+\frac{\tau}{\ell_{\tau}}\leq\frac{2A_{\max}^{2}}{\ell_{\tau}(1-\gamma)^{2}}:=L_{\tau}.$

Similarly, $V_{v,s}(\mu^{i},\mu^{-i})$ as a function of $\mu^{-i}$ is also
$L_{\tau}$ – smooth on the set
$\\{\mu^{-i}\in\Delta^{|\mathcal{A}^{-i}|}\mid\min_{a^{-i}}\mu^{i}(a^{-i})\geq\ell_{\tau}\\}$
uniformly for all $\mu^{i}$.

Using the smoothness of $V_{v,s}(\cdot,\cdot)$ established above, for any
$s\in\mathcal{S}$, we have by the policy update equation (cf. Algorithm 3 Line
$3$) that

$\displaystyle V_{v,s}(\pi_{k+1}^{i}(s),\pi_{k+1}^{-i}(s))$
$\displaystyle\leq\;$ $\displaystyle
V_{v,s}(\pi_{k}^{i}(s),\pi_{k}^{-i}(s))+\beta_{k}\langle\nabla_{2}V_{v,s}(\pi_{k}^{i}(s),\pi_{k}^{-i}(s)),\sigma_{\tau}(q_{k}^{-i}(s))-\pi_{k}^{-i}(s)\rangle$
$\displaystyle+\beta_{k}\langle\nabla_{1}V_{v,s}(\pi_{k}^{i}(s),\pi_{k+1}^{-i}(s)),\sigma_{\tau}(q_{k}^{i}(s))-\pi_{k}^{i}(s)\rangle$
$\displaystyle+\frac{L_{\tau}\beta_{k}^{2}}{2}\|\sigma_{\tau}(q_{k}^{i}(s))-\pi_{k}^{i}(s)\|_{2}^{2}+\frac{L_{\tau}\beta_{k}^{2}}{2}\|\sigma_{\tau}(q_{k}^{-i}(s))-\pi_{k}^{-i}(s)\|_{2}^{2}$
$\displaystyle\leq\;$ $\displaystyle
V_{v,s}(\pi_{k}^{i}(s),\pi_{k}^{-i}(s))+\underbrace{\beta_{k}\langle\nabla_{2}V_{v,s}(\pi_{k}^{i}(s),\pi_{k}^{-i}(s)),\sigma_{\tau}(\mathcal{T}^{-i}(v^{-i})(s)\pi_{k}^{i}(s))-\pi_{k}^{-i}(s)\rangle}_{\hat{N}_{1}}$
$\displaystyle+\underbrace{\beta_{k}\langle\nabla_{1}V_{v,s}(\pi_{k}^{i}(s),\pi_{k+1}^{-i}(s)),\sigma_{\tau}(\mathcal{T}^{i}(v^{i})(s)\pi_{k}^{-i}(s))-\pi_{k}^{i}(s)\rangle}_{\hat{N}_{2}}$
$\displaystyle+\underbrace{\beta_{k}\langle\nabla_{2}V_{v,s}(\pi_{k}^{i}(s),\pi_{k}^{-i}(s)),\sigma_{\tau}(q_{k}^{-i}(s))-\sigma_{\tau}(\mathcal{T}^{-i}(v^{-i})(s)\pi_{k}^{i}(s))\rangle}_{\hat{N}_{3}}$
$\displaystyle+\underbrace{\beta_{k}\langle\nabla_{1}V_{v,s}(\pi_{k}^{i}(s),\pi_{k+1}^{-i}(s)),\sigma_{\tau}(q_{k}^{i}(s))-\sigma_{\tau}(\mathcal{T}^{i}(v^{i})(s)\pi_{k}^{-i}(s))\rangle}_{\hat{N}_{4}}$
$\displaystyle+2L_{\tau}\beta_{k}^{2}.$ (57)

We next bound the terms $\\{\hat{N}_{j}\\}_{1\leq j\leq 4}$ on the RHS of Eq.
(57) using Lemma A.7 (3) and (4).

First consider $\hat{N}_{1}+\hat{N}_{2}$. We have by Lemma A.7 (3) that

$\displaystyle\hat{N}_{1}+\hat{N}_{2}\leq\;$
$\displaystyle-\frac{7\beta_{k}}{8}V_{v,s}(\pi_{k}^{i}(s),\pi_{k}^{-i}(s))+\frac{16\beta_{k}}{\tau}\|\mathcal{T}^{i}(v^{i})(s)+\mathcal{T}^{-i}(v^{-i}(s)^{\top}\|_{2}^{2}.$

To proceed, note that for any $\mu^{-i}\in\mathbb{R}^{|\mathcal{A}^{-i}|}$
satisfying $\|\mu^{-i}\|_{2}=1$, we have

$\displaystyle\|(\mathcal{T}^{i}(v^{i})(s)+\mathcal{T}^{-i}(v^{-i}(s)^{\top})\mu^{i}\|_{2}^{2}$
$\displaystyle=\;$
$\displaystyle\gamma^{2}\sum_{a^{i}}\left[\sum_{a^{-i}}\mathbb{E}[v^{i}(S_{1})+v^{-i}(S_{1})\mid
S_{0}=s,A_{0}^{i}=a^{i},A_{0}^{-i}=a^{-i}]\mu^{-i}(a^{-i})\right]^{2}$
$\displaystyle\leq\;$
$\displaystyle\gamma^{2}\|v^{i}+v^{-i}\|_{\infty}^{2}\sum_{a^{i}}\left[\sum_{a^{-i}}\mu^{-i}(a^{-i})\right]^{2}$
$\displaystyle\leq\;$
$\displaystyle\gamma^{2}A_{\max}\|v^{i}+v^{-i}\|_{\infty}^{2},$

which implies

$\displaystyle\|\mathcal{T}^{i}(v^{i})(s)+\mathcal{T}^{-i}(v^{-i}(s)^{\top}\|_{2}^{2}\leq\gamma^{2}A_{\max}\|v^{i}+v^{-i}\|_{\infty}^{2}.$

It follows that

$\displaystyle\hat{N}_{1}+\hat{N}_{2}\leq\;$
$\displaystyle-\frac{7\beta_{k}}{8}V_{v,s}(\pi_{k}^{i}(s),\pi_{k}^{-i}(s))+\frac{16A_{\max}\beta_{k}}{\tau}\|v^{i}+v^{-i}\|_{\infty}^{2}.$

We next consider $\hat{N}_{3}+\hat{N}_{4}$. Since

$\displaystyle\max(\|\mathcal{T}^{i}(v^{i})(s)\|_{2},\|\mathcal{T}^{-i}(v^{-i})(s)\|_{2})\leq\frac{A_{\max}}{1-\gamma},$
(See Eq. (56))

we have by Lemma A.7 (4) that

$\displaystyle\hat{N}_{3}+\hat{N}_{4}$ $\displaystyle\leq\;$ $\displaystyle
2\beta_{k}\left(\frac{\tau}{\ell_{\tau}}+\frac{A_{\max}}{1-\gamma}\right)\bigg{[}\frac{2\bar{c}}{\tau}V_{v,s}(\pi_{k}^{i}(s),\pi_{k}^{-i}(s))$
$\displaystyle+\frac{1}{\bar{c}\tau^{2}}\|q_{k}^{i}(s)-\mathcal{T}^{i}(v^{i})(s)\pi_{k}^{-i}(s)\|_{2}^{2}+\frac{1}{\bar{c}\tau^{2}}\|q_{k}^{-i}(s)-\mathcal{T}^{-i}(v^{-i})(s)\pi_{k}^{i}(s)\|_{2}^{2}\bigg{]}$

for any $\bar{c}>0$. By choosing
$\bar{c}=\frac{\tau}{32}(\frac{\tau}{\ell_{\tau}}+\frac{A_{\max}}{1-\gamma})^{-1}$,
we have from the previous inequality that

$\displaystyle\hat{N}_{3}+\hat{N}_{4}\leq\;$
$\displaystyle\frac{\beta_{k}}{8}V_{v,s}(\pi_{k}^{i}(s),\pi_{k}^{-i}(s))+\frac{64\beta_{k}\left(\frac{\tau}{\ell_{\tau}}+\frac{A_{\max}}{1-\gamma}\right)^{2}}{\tau^{3}}\|q_{k}^{i}(s)-\mathcal{T}^{i}(v^{i})(s)\pi_{k}^{-i}(s)\|_{2}^{2}$
$\displaystyle+\frac{64\beta_{k}\left(\frac{\tau}{\ell_{\tau}}+\frac{A_{\max}}{1-\gamma}\right)^{2}}{\tau^{3}}\|q_{k}^{-i}(s)-\mathcal{T}^{-i}(v^{-i})(s)\pi_{k}^{i}(s)\|_{2}^{2}$
$\displaystyle\leq\;$
$\displaystyle\frac{\beta_{k}}{8}V_{v,s}(\pi_{k}^{i}(s),\pi_{k}^{-i}(s))+\frac{256A_{\max}^{2}\beta_{k}}{\ell_{\tau}^{2}\tau^{3}(1-\gamma)^{2}}\|q_{k}^{i}(s)-\mathcal{T}^{i}(v^{i})(s)\pi_{k}^{-i}(s)\|_{2}^{2}$
$\displaystyle+\frac{256A_{\max}^{2}\beta_{k}}{\ell_{\tau}^{2}\tau^{3}(1-\gamma)^{2}}\|q_{k}^{-i}(s)-\mathcal{T}^{-i}(v^{-i})(s)\pi_{k}^{i}(s)\|_{2}^{2}.$

Finally, using the upper bounds we obtained for the terms
$\hat{N}_{1}+\hat{N}_{2}$ and $\hat{N}_{3}+\hat{N}_{4}$ in Eq. (57) and we
have

$\displaystyle V_{v,s}(\pi_{k+1}^{i}(s),\pi_{k+1}^{-i}(s))$
$\displaystyle\leq\;$
$\displaystyle\left(1-\frac{3\beta_{k}}{4}\right)V_{v,s}(\pi_{k}^{i}(s),\pi_{k}^{-i}(s))+\frac{16A_{\max}\beta_{k}}{\tau}\|v^{i}+v^{-i}\|_{\infty}^{2}.$
$\displaystyle+\frac{256A_{\max}^{2}\beta_{k}}{\ell_{\tau}^{2}\tau^{3}(1-\gamma)^{2}}\|q_{k}^{i}(s)-\mathcal{T}^{i}(v^{i})(s)\pi_{k}^{-i}(s)\|_{2}^{2}$
$\displaystyle+\frac{256A_{\max}^{2}\beta_{k}}{\ell_{\tau}^{2}\tau^{3}(1-\gamma)^{2}}\|q_{k}^{-i}(s)-\mathcal{T}^{-i}(v^{-i})(s)\pi_{k}^{i}(s)\|_{2}^{2}$
$\displaystyle+\frac{4A_{\max}^{2}}{\ell_{\tau}(1-\gamma)^{2}}\beta_{k}^{2}.$

Summing up both sides of the previous inequality for all $s$ and then taking
expectation, and we have the desired result.

####  A.7.10 Proof of Lemma A.9

  1. (1)

For any $(q_{1}^{i},q_{2}^{i})$ and $(s_{0},a_{0}^{i},a_{0}^{-i},s_{1})$, we
have

$\displaystyle\|F^{i}(q_{1}^{i},s_{0},a_{0}^{i},a_{0}^{-i},s_{1})-F^{i}(q_{2}^{i},s_{0},a_{0}^{i},a_{0}^{-i},s_{1})\|_{2}^{2}$
$\displaystyle=\;$
$\displaystyle\sum_{(s,a^{i})}([F^{i}(q_{1}^{i},s_{0},a_{0}^{i},a_{0}^{-i},s_{1})](s,a^{i})-[F^{i}(q_{2}^{i},s_{0},a_{0}^{i},a_{0}^{-i},s_{1})](s,a^{i}))^{2}$
$\displaystyle=\;$
$\displaystyle\sum_{(s,a^{i})}\mathds{1}_{\\{(s,a^{i})=(s_{0},a_{0}^{i})\\}}\left(q_{1}^{i}(s_{0},a_{0}^{i})-q_{2}^{i}(s_{0},a_{0}^{i})\right)^{2}$
$\displaystyle\leq\;$ $\displaystyle\|q_{1}^{i}-q_{2}^{i}\|_{2}^{2}.$

  2. (2)

For any $(s_{0},a_{0}^{i},a_{0}^{-i},s_{1})$, we have

$\displaystyle\|F^{i}(\bm{0},s_{0},a_{0}^{i},a_{0}^{-i},s_{1})\|_{2}^{2}=\;$
$\displaystyle\sum_{(s,a^{i})}([F^{i}(\bm{0},s_{0},a_{0}^{i},a_{0}^{-i},s_{1})](s,a^{i}))^{2}$
$\displaystyle=\;$
$\displaystyle\sum_{(s,a^{i})}\mathds{1}_{\\{(s,a^{i})=(s_{0},a_{0}^{i})\\}}\left(\mathcal{R}^{i}(s_{0},a_{0}^{i},a_{0}^{-i})+\gamma
v^{i}(s_{1})\right)^{2}$ $\displaystyle\leq\;$
$\displaystyle\frac{1}{(1-\gamma)^{2}},$

where the last line follows from $\|v^{i}\|_{\infty}\leq 1/(1-\gamma)$ and
$|\mathcal{R}^{i}(s_{0},a_{0}^{i},a_{0}^{-i})|\leq 1$.

  3. (3)

We first write down the explicit expression of $\bar{F}_{k}^{i}(\cdot)$. Using
the definition of $\mathcal{T}^{i}(\cdot)$ and we have

$\displaystyle\bar{F}_{k}^{i}(q^{i})(s)=\mu_{k}(s)\Pi_{k}^{i}(s)\left(\mathcal{T}^{i}(v^{i})(s)\pi_{k}^{-i}(s)-q^{i}(s)\right),\;\forall\;s\in\mathcal{S},$

where $\Pi_{k}^{i}(s):=\text{diag}(\pi_{k}^{i}(s))$. Since $\min_{0\leq k\leq
K-1}\min_{s\in\mathcal{S}}\mu_{k}(s)>0$ (cf. Lemma A.2 and Lemma 4.1 (4)) and
$\Pi_{k}^{i}(s)$ has strictly positive diagonal entries for all $s$ and $k$
(cf. Lemma A.2), the equation $\bar{F}_{k}^{i}(q^{i})=0$ has a unique solution
$\bar{q}_{k}^{i}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}^{i}|}$, which is
explicitly given by

$\displaystyle\bar{q}_{k}^{i}(s)=\mathcal{T}^{i}(v^{i})(s)\pi_{k}^{-i}(s),\;\forall\;s\in\mathcal{S}.$

  4. (4)

Using the explicit expression of $\bar{F}_{k}^{i}(\cdot)$ and we have for any
$q_{1}^{i}$ and $q_{2}^{i}$ that

$\displaystyle\langle\bar{F}_{k}^{i}(q_{1}^{i})-\bar{F}_{k}^{i}(q_{2}^{i}),q_{1}^{i}-q_{2}^{i}\rangle=\;$
$\displaystyle-\sum_{s,a^{i}}\mu_{k}(s)\pi_{k}^{i}(a^{i}|s)(q_{1}^{i}(s,a^{i})-q_{2}^{i}(s,a^{i}))^{2}$
$\displaystyle\leq\;$
$\displaystyle-\min_{s,a^{i}}\mu_{k}(s)\pi_{k}^{i}(a^{i}|s)\|q_{1}^{i}-q_{2}^{i}\|_{2}^{2}$
$\displaystyle\leq\;$
$\displaystyle-\mu_{\tau}\ell_{\tau}\|q_{1}^{i}-q_{2}^{i}\|_{2}^{2}$ (Lemma
4.1 (4) and Lemma A.2) $\displaystyle=\;$ $\displaystyle-
c_{\tau}\|q_{1}^{i}-q_{2}^{i}\|_{2}^{2},$

where we recall that $c_{\tau}=\mu_{\tau}\ell_{\tau}$.

####  A.7.11 Proof of Lemma A.10

For any $k\geq 0$, we have

$\displaystyle N_{2}=\;$ $\displaystyle\mathbb{E}[\langle
F^{i}(q_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-\bar{F}_{k}^{i}(q_{k}^{i}),q_{k}^{i}-\bar{q}_{k}^{i}\rangle]$
$\displaystyle=\;$ $\displaystyle\underbrace{\mathbb{E}[\langle
F^{i}(q_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-\bar{F}_{k-z_{k}}^{i}(q_{k-z_{k}}^{i}),q_{k-z_{k}}^{i}-\bar{q}_{k-z_{k}}^{i}\rangle]}_{N_{2,1}}$
$\displaystyle+\underbrace{\mathbb{E}[\langle
F^{i}(q_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-\bar{F}_{k-z_{k}}^{i}(q_{k-z_{k}}^{i}),q_{k}^{i}-q_{k-z_{k}}^{i}\rangle]}_{N_{2,2}}$
$\displaystyle+\underbrace{\mathbb{E}[\langle
F^{i}(q_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-\bar{F}_{k-z_{k}}^{i}(q_{k-z_{k}}^{i}),\bar{q}_{k-z_{k}}^{i}-\bar{q}_{k}^{i}\rangle]}_{N_{2,3}}$
$\displaystyle+\underbrace{\mathbb{E}[\langle
F^{i}(q_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-F^{i}(q_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1}),q_{k}^{i}-\bar{q}_{k}^{i}\rangle]}_{N_{2,4}}$
$\displaystyle+\underbrace{\mathbb{E}[\langle\bar{F}_{k-z_{k}}^{i}(q_{k-z_{k}}^{i})-\bar{F}_{k}^{i}(q_{k}^{i}),q_{k}^{i}-\bar{q}_{k}^{i}\rangle]}_{N_{2,5}}$

We next control the terms $\\{N_{2,j}\\}_{1\leq j\leq 5}$ on the RHS of the
previous inequality. Before that, the following two lemmas are needed. The
proof of Lemma A.13 follows from that of (Srikant and Ying, , 2019, Lemma 3)
and (Chen et al., 2021b, , Lemma A.3). Lemma A.14 is the policy-counterpart of
Lemma A.13.

######  Lemma A.13 (Proof in Appendix A.7.14).

Given positive integers $k_{1}\leq k_{2}$ satisfying
$\alpha_{k_{1},k_{2}-1}\leq 1/4$, we have for any
$k\in\\{k_{1},k_{1}+1,\cdots,k_{2}\\}$ that

$\displaystyle\|q_{k}^{i}-q_{k_{1}}^{i}\|_{2}\leq\;$
$\displaystyle\min(2\alpha_{k_{1},k_{2}-1},1/2)\left(\|q_{k_{1}}^{i}\|_{2}+\frac{1}{1-\gamma}\right),$
$\displaystyle\|q_{k}^{i}-q_{k_{1}}^{i}\|_{2}\leq\;$
$\displaystyle\min(4\alpha_{k_{1},k_{2}-1},1)\left(\|q_{k_{2}}^{i}\|_{2}+\frac{1}{1-\gamma}\right).$

######  Lemma A.14 (Proof in Appendix A.7.15).

Given positive integers $k_{1}\leq k_{2}$ satisfying
$\beta_{k_{1},k_{2}-1}\leq 1/4$, we have for any $s\in\mathcal{S}$ and
$k\in\\{k_{1},k_{1}+1,\cdots,k_{2}\\}$ that

$\displaystyle\|\pi_{k}^{i}(s)-\pi_{k_{1}}^{i}(s)\|_{2}\leq\;$
$\displaystyle\min(2\beta_{k_{1},k_{2}-1},1/2)\left(\|\pi_{k_{1}}^{i}(s)\|_{2}+1\right),$
$\displaystyle\|\pi_{k}^{i}(s)-\pi_{k_{1}}^{i}(s)\|_{2}\leq\;$
$\displaystyle\min(4\beta_{k_{1},k_{2}-1},1)\left(\|\pi_{k_{2}}^{i}(s)\|_{2}+1\right).$

We next bound the terms $\\{N_{2,j}\\}_{1\leq j\leq 5}$. Let $\mathcal{F}_{k}$
be the $\sigma$-algebra generated the sequence of random variables
$\\{S_{0},A_{0}^{i},A_{0}^{-i},\cdots,S_{k-1},A_{k-1}^{i},A_{k-1}^{-i},S_{k}\\}$.

##### The Term $N_{2,1}$.

Using the tower property of conditional expectations and we have

$\displaystyle N_{2,1}$ $\displaystyle=\;$ $\displaystyle\mathbb{E}[\langle
F^{i}(q_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-\bar{F}_{k-z_{k}}^{i}(q_{k-z_{k}}^{i}),q_{k-z_{k}}^{i}-\bar{q}_{k-z_{k}}^{i}\rangle]$
$\displaystyle=\;$
$\displaystyle\mathbb{E}[\langle\mathbb{E}[F^{i}(q_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\mid\mathcal{F}_{k-z_{k}}]-\bar{F}_{k-z_{k}}^{i}(q_{k-z_{k}}^{i}),q_{k-z_{k}}^{i}-\bar{q}_{k-z_{k}}^{i}\rangle]$
$\displaystyle\leq\;$
$\displaystyle\mathbb{E}[\|\mathbb{E}[F^{i}(q_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\mid\mathcal{F}_{k-z_{k}}]-\bar{F}_{k-z_{k}}^{i}(q_{k-z_{k}}^{i})\|_{2}\|q_{k-z_{k}}^{i}-\bar{q}_{k-z_{k}}^{i}\|_{2}]$
$\displaystyle\leq\;$
$\displaystyle\frac{2\sqrt{|\mathcal{S}|A_{\max}}}{1-\gamma}\mathbb{E}[\underbrace{\|F^{i}(q_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\mid\mathcal{F}_{k-z_{k}}]-\bar{F}_{k-z_{k}}^{i}(q_{k-z_{k}}^{i})\|_{2}}_{N_{2,1,1}}],$

where the last line follows from
$\|q_{k-z_{k}}^{i}\|_{2}\leq\sqrt{|\mathcal{S}|A_{\max}}\|q_{k-z_{k}}^{i}\|_{\infty}\leq\sqrt{|\mathcal{S}|A_{\max}}/(1-\gamma)$
and similarly
$\|\bar{q}_{k-z_{k}}^{i}\|_{2}\leq\sqrt{|\mathcal{S}|A_{\max}}/(1-\gamma)$.
For the term $N_{2,1,1}$, using triangle inequality and we have

$\displaystyle\|F^{i}(q_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\mid\mathcal{F}_{k-z_{k}}]-\bar{F}_{k-z_{k}}^{i}(q_{k-z_{k}}^{i})\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\|\bar{F}_{k}^{i}(q_{k-z_{k}}^{i})\\!-\\!\bar{F}_{k-z_{k}}^{i}(q_{k-z_{k}}^{i})\|_{2}$
$\displaystyle+\|F^{i}(q_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\mid\mathcal{F}_{k-z_{k}}]\\!-\\!\bar{F}_{k}^{i}(q_{k-z_{k}}^{i})\|_{2}.$
(58)

To control the first term on the RHS of Eq. (58), recall that

$\displaystyle\bar{F}_{k}^{i}(q^{i})(s)=\mu_{k}(s)\Pi_{k}^{i}(s)\left(\mathcal{T}^{i}(v^{i})(s)\pi_{k}^{-i}(s)-q^{i}(s)\right),\;\forall\;s\in\mathcal{S},\;q^{i}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}^{i}|},$

where $\Pi_{k}^{i}(s)=\text{diag}(\pi_{k}^{i}(s))$. Therefore, we have for any
$s\in\mathcal{S}$ and $q^{i}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}^{i}|}$
that

$\displaystyle\|\bar{F}_{k}^{i}(q^{i})(s)-\bar{F}_{k-z_{k}}^{i}(q^{i})(s)\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\|\mu_{k}(s)\Pi_{k}^{i}(s)\mathcal{T}^{i}(v^{i})(s)\pi_{k}^{-i}(s)-\mu_{k-z_{k}}(s)\Pi_{k-z_{k}}^{i}(s)\mathcal{T}^{i}(v^{i})(s)\pi_{k-z_{k}}^{-i}(s)\|_{2}$
$\displaystyle+\|(\mu_{k}(s)\Pi_{k}^{i}(s)-\mu_{k-z_{k}}(s)\Pi_{k-z_{k}}^{i}(s))q^{i}(s)\|_{2}.$
(59)

We next bound the two terms on the RHS of Eq. (59). For the first term, we
have

$\displaystyle\|(\mu_{k}(s)\Pi_{k}^{i}(s)-\mu_{k-z_{k}}(s)\Pi_{k-z_{k}}^{i}(s))q^{i}(s)\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\frac{A_{\max}^{1/2}}{1-\gamma}\|\mu_{k}(s)\Pi_{k}^{i}(s)-\mu_{k-z_{k}}(s)\Pi_{k-z_{k}}^{i}(s)\|_{2}$
($\|q^{i}(s)\|_{2}\leq\frac{A_{\max}^{1/2}}{1-\gamma}$) $\displaystyle=\;$
$\displaystyle\frac{A_{\max}^{1/2}}{1-\gamma}\left(\|\mu_{k}(s)(\Pi_{k}^{i}(s)-\Pi_{k-z_{k}}^{i}(s))\|_{2}+\|(\mu_{k}(s)-\mu_{k-z_{k}}(s))\Pi_{k-z_{k}}^{i}(s)\|_{2}\right)$
$\displaystyle\leq\;$
$\displaystyle\frac{A_{\max}^{1/2}}{1-\gamma}\left(\mu_{k}(s)\|\Pi_{k}^{i}(s)-\Pi_{k-z_{k}}^{i}(s)\|_{2}+|\mu_{k}(s)-\mu_{k-z_{k}}(s)|\right)$
($\|\Pi_{k-z_{k}}^{i}(s)\|_{2}\leq 1$) $\displaystyle=\;$
$\displaystyle\frac{A_{\max}^{1/2}}{1-\gamma}\left(\mu_{k}(s)\|\pi_{k}^{i}(s)-\pi_{k-z_{k}}^{i}(s)\|_{\infty}+|\mu_{k}(s)-\mu_{k-z_{k}}(s)|\right).$

For the second term on the RHS of Eq. (59), we have

$\displaystyle\|\mu_{k}(s)\Pi_{k}^{i}(s)\mathcal{T}^{i}(v^{i})(s)\pi_{k}^{-i}(s)-\mu_{k-z_{k}}(s)\Pi_{k-z_{k}}^{i}(s)\mathcal{T}^{i}(v^{i})(s)\pi_{k-z_{k}}^{-i}(s)\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\|(\mu_{k}(s)\Pi_{k}^{i}(s)-\mu_{k-z_{k}}(s)\Pi_{k-z_{k}}^{i}(s))\mathcal{T}^{i}(v^{i})(s)\pi_{k}^{-i}(s)\|_{2}$
$\displaystyle+\|\mu_{k-z_{k}}(s)\Pi_{k-z_{k}}^{i}(s)\mathcal{T}^{i}(v^{i})(s)(\pi_{k}^{-i}(s)-\pi_{k-z_{k}}^{-i}(s))\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\frac{A_{\max}^{1/2}}{1-\gamma}\|\mu_{k}(s)\Pi_{k}^{i}(s)-\mu_{k-z_{k}}(s)\Pi_{k-z_{k}}^{i}(s)\|_{2}+\frac{1}{1-\gamma}\mu_{k-z_{k}}(s)\|\pi_{k}^{-i}(s)-\pi_{k-z_{k}}^{-i}(s)\|_{\infty}$
$\displaystyle\leq\;$
$\displaystyle\frac{A_{\max}^{1/2}}{1-\gamma}\left(\mu_{k}(s)\|\Pi_{k}^{i}(s)-\Pi_{k-z_{k}}^{i}(s)\|_{2}+|\mu_{k}(s)-\mu_{k-z_{k}}(s)|\right)$
$\displaystyle+\frac{\mu_{k-z_{k}}(s)}{1-\gamma}\|\pi_{k}^{-i}(s)-\pi_{k-z_{k}}^{-i}(s)\|_{\infty}$
$\displaystyle\leq\;$
$\displaystyle\frac{A_{\max}^{1/2}}{1-\gamma}\left(|\mu_{k}(s)-\mu_{k-z_{k}}(s)|+(\mu_{k}(s)+\mu_{k-z_{k}}(s))\|\pi_{k}^{-i}(s)-\pi_{k-z_{k}}^{-i}(s)\|_{\infty}\right).$

Using the previous two inequalities in Eq. (59) and we have

$\displaystyle\|\bar{F}_{k}^{i}(q^{i})(s)-\bar{F}_{k-z_{k}}^{i}(q^{i})(s)\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\frac{A_{\max}^{1/2}}{1-\gamma}\left(2|\mu_{k}(s)-\mu_{k-z_{k}}(s)|+(\mu_{k}(s)+\mu_{k-z_{k}}(s))\|\pi_{k}^{-i}(s)-\pi_{k-z_{k}}^{-i}(s)\|_{\infty}\right)$
$\displaystyle+\frac{A_{\max}^{1/2}}{1-\gamma}\mu_{k}(s)\|\pi_{k}^{i}(s)-\pi_{k-z_{k}}^{i}(s)\|_{\infty},$

which implies

$\displaystyle\|\bar{F}_{k}^{i}(q^{i})(s)-\bar{F}_{k-z_{k}}^{i}(q^{i})(s)\|_{2}^{2}$
$\displaystyle\leq\;$
$\displaystyle\frac{3A_{\max}}{(1-\gamma)^{2}}\left(4|\mu_{k}(s)-\mu_{k-z_{k}}(s)|^{2}+2(\mu_{k}(s)^{2}+\mu_{k-z_{k}}(s)^{2})\|\pi_{k}^{-i}(s)-\pi_{k-z_{k}}^{-i}(s)\|_{\infty}^{2}\right)$
$\displaystyle+\frac{3A_{\max}}{(1-\gamma)^{2}}\mu_{k}(s)^{2}\|\pi_{k}^{i}(s)-\pi_{k-z_{k}}^{i}(s)\|_{\infty}^{2}.$

It follows that

$\displaystyle\|\bar{F}_{k}^{i}(q^{i})-\bar{F}_{k-z_{k}}^{i}(q^{i})\|_{2}^{2}=\;$
$\displaystyle\sum_{s}\|\bar{F}_{k}^{i}(q^{i})(s)-\bar{F}_{k-z_{k}}^{i}(q^{i})(s)\|_{2}^{2}$
$\displaystyle\leq\;$
$\displaystyle\frac{3A_{\max}}{(1-\gamma)^{2}}\left(4\|\mu_{k}-\mu_{k-z_{k}}\|_{2}^{2}+4\max_{s}\|\pi_{k}^{-i}(s)-\pi_{k-z_{k}}^{-i}(s)\|_{\infty}^{2}\right)$
$\displaystyle+\frac{3A_{\max}}{(1-\gamma)^{2}}\max_{s}\|\pi_{k}^{i}(s)-\pi_{k-z_{k}}^{i}(s)\|_{\infty}^{2}.$

Since

$\displaystyle\|\mu_{k}-\mu_{k-z_{k}}\|_{2}^{2}\leq\;$
$\displaystyle|\mathcal{S}|\|\mu_{k}-\mu_{k-z_{k}}\|_{\infty}^{2}$
$\displaystyle\leq\;$
$\displaystyle|\mathcal{S}|\hat{L}_{\tau}^{2}\|\pi_{k}^{i}-\pi_{k-z_{k}}^{i}\|_{\infty}^{2}$
(Lemma 4.1 (3)) $\displaystyle=\;$
$\displaystyle|\mathcal{S}|\hat{L}_{\tau}^{2}\max_{s\in\mathcal{S}}\|\pi_{k}^{i}(s)-\pi_{k-z_{k}}^{i}(s)\|_{1}^{2}$
$\displaystyle\leq\;$
$\displaystyle|\mathcal{S}|^{2}\hat{L}_{\tau}^{2}\max_{s\in\mathcal{S}}\|\pi_{k}^{i}(s)-\pi_{k-z_{k}}^{i}(s)\|_{2}^{2}$
$\displaystyle\leq\;$ $\displaystyle
16|\mathcal{S}|^{2}\hat{L}_{\tau}^{2}\beta_{k-z_{k},k-1}^{2}\max_{s\in\mathcal{S}}(\|\pi_{k}^{i}(s)\|_{2}+1)^{2}$
(Lemma A.14) $\displaystyle\leq\;$ $\displaystyle
64|\mathcal{S}|^{2}\hat{L}_{\tau}^{2}\beta_{k-z_{k},k-1}^{2}$

and

$\displaystyle\max_{s}\|\pi_{k}^{i}(s)-\pi_{k-z_{k}}^{i}(s)\|_{\infty}^{2}\leq\;$
$\displaystyle\max_{s}\|\pi_{k}^{i}(s)-\pi_{k-z_{k}}^{i}(s)\|_{2}^{2}$
$\displaystyle\leq\;$ $\displaystyle
16\beta_{k-z_{k},k-1}^{2}\max_{s}(\|\pi_{k}^{i}(s)\|_{2}+1)^{2}$ (Lemma A.14)
$\displaystyle\leq\;$ $\displaystyle 64\beta_{k-z_{k},k-1}^{2},\quad
i\in\\{1,2\\},$

we have

$\displaystyle\|\bar{F}_{k}^{i}(q^{i})-\bar{F}_{k-z_{k}}^{i}(q^{i})\|_{2}^{2}\leq\;$
$\displaystyle\frac{3A_{\max}}{(1-\gamma)^{2}}\left(256|\mathcal{S}|^{2}\hat{L}_{\tau}^{2}\beta_{k-z_{k},k-1}^{2}+320\beta_{k-z_{k},k-1}^{2}\right)$
$\displaystyle\leq\;$
$\displaystyle\frac{1728A_{\max}|\mathcal{S}|^{2}\hat{L}_{\tau}^{2}\beta_{k-z_{k},k-1}^{2}}{(1-\gamma)^{2}},$

which implies

$\displaystyle\|\bar{F}_{k}^{i}(q^{i})-\bar{F}_{k-z_{k}}^{i}(q^{i})\|_{2}\leq\frac{42|\mathcal{S}|A_{\max}^{1/2}\hat{L}_{\tau}\beta_{k-z_{k},k-1}}{1-\gamma}$
(60)

for all $q^{i}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}^{i}|}$.

We next move on to bound the second term on the RHS of Eq. (58). Recall that
we denote $P_{\pi}\in\mathbb{R}^{|\mathcal{S}|\times|\mathcal{S}|}$ as the
transition probability matrix of the Markov chain $\\{S_{k}\\}$ induced by the
joint policy $\pi$. Using the definition of conditional expectation and we
have

$\displaystyle\|\mathbb{E}[F^{i}(q_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\mid\mathcal{F}_{k-z_{k}}]-\bar{F}_{k}^{i}(q_{k-z_{k}}^{i})\|_{2}$
$\displaystyle=\;$
$\displaystyle\bigg{\|}\sum_{s}\left[\left(\prod_{j=k+1}^{k+z_{k}}P_{\pi_{j-z_{k}}}\right)(S_{k-z_{k}},s)-\mu_{k}(s)\right]\sum_{a^{i}}\pi_{k}^{i}(a^{i}|s)\sum_{a^{-i}}\pi_{k}^{-i}(a^{-i}|s)$
$\displaystyle\times\sum_{s^{\prime}}p(s^{\prime}|s,a^{i},a^{-i})F^{i}(q_{k-z_{k}}^{i},s,a^{i},a^{-i},s^{\prime})\bigg{\|}_{2}$
$\displaystyle\leq\;$
$\displaystyle\left|\sum_{s}\left[\left(\prod_{j=k+1}^{k+z_{k}}P_{\pi_{j-z_{k}}}\right)(S_{k-z_{k}},s)-\mu_{k}(s)\right]\right|\left(\|q_{k-z_{k}}^{i}\|_{2}+\frac{1}{1-\gamma}\right)$
$\displaystyle\leq\;$
$\displaystyle\sum_{s}\left|\left(\prod_{j=k+1}^{k+z_{k}}P_{\pi_{j-z_{k}}}\right)(S_{k-z_{k}},s)-\mu_{k}(s)\right|\left(\|q_{k-z_{k}}^{i}\|_{2}+\frac{1}{1-\gamma}\right)$
$\displaystyle\leq\;$
$\displaystyle\left\\{\sum_{s}\left|\left(\prod_{j=k+1}^{k+z_{k}}P_{\pi_{j-z_{k}}}\right)(S_{k-z_{k}},s)-P_{\pi_{k}}^{z_{k}}(S_{k-z_{k}},s)\right|+\sum_{s}\left|P_{\pi_{k}}^{z_{k}}(S_{k-z_{k}},s)-\mu_{k}(s)\right|\right\\}$
$\displaystyle\times\left(\|q_{k-z_{k}}^{i}\|_{2}+\frac{1}{1-\gamma}\right)$
$\displaystyle\leq\;$
$\displaystyle\left\\{\left\|\prod_{j=k+1}^{k+z_{k}}P_{\pi_{j-z_{k}}}-P_{\pi_{k}}^{z_{k}}\right\|_{\infty}+2\rho_{\tau}^{z_{k}}\right\\}\left(\|q_{k-z_{k}}^{i}\|_{2}+\frac{1}{1-\gamma}\right),$
(61)

where the last line follows from Lemma 4.1 (2) and Lemma A.2. Observe that

$\displaystyle\left\|\prod_{j=k+1}^{k+z_{k}}P_{\pi_{j-z_{k}}}-P_{\pi_{k}}^{z_{k}}\right\|_{\infty}=\;$
$\displaystyle\left\|\sum_{\ell=1}^{z_{k}}\left(\prod_{j=k+1}^{k-\ell+1+z_{k}}P_{\pi_{j-z_{k}}}P_{\pi_{k}}^{\ell-1}-\prod_{j=k+1}^{k-\ell+z_{k}}P_{\pi_{j-z_{k}}}P_{\pi_{k}}^{\ell}\right)\right\|_{\infty}$
$\displaystyle=\;$
$\displaystyle\left\|\sum_{\ell=1}^{z_{k}}\left(\prod_{j=k+1}^{k-\ell+z_{k}}P_{\pi_{j-z_{k}}}(P_{\pi_{k-\ell+1}}-P_{\pi_{k}})P_{\pi_{k}}^{\ell-1}\right)\right\|_{\infty}$
$\displaystyle\leq\;$
$\displaystyle\sum_{\ell=1}^{z_{k}}\left\|\prod_{j=k+1}^{k-\ell+z_{k}}P_{\pi_{j-z_{k}}}\right\|_{\infty}\|P_{\pi_{k-\ell+1}}-P_{\pi_{k}}\|_{\infty}\|P_{\pi_{k}}^{\ell-1}\|_{\infty}.$

Since the induced $\ell_{\infty}$-norm for any stochastic matrix is $1$ and
$P_{\pi}$ as a function of $\pi$ is $1$-Lipschitz continuous with respect to
the $\ell_{\infty}$-norm, we have

$\displaystyle\left\|\prod_{j=k+1}^{k+z_{k}}P_{\pi_{j-z_{k}}}-P_{\pi_{k}}^{z_{k}}\right\|_{\infty}$
$\displaystyle\leq\;$
$\displaystyle\sum_{\ell=1}^{z_{k}}\|\pi_{k-\ell+1}-\pi_{k}\|_{\infty}$
$\displaystyle=\;$
$\displaystyle\sum_{\ell=1}^{z_{k}}\max_{s\in\mathcal{S}}\sum_{a^{i},a^{-i}}|\pi_{k-\ell+1}^{i}(a^{i}|s)\pi_{k-\ell+1}^{-i}(a^{-i}|s)-\pi_{k}^{i}(a^{i}|s)\pi_{k}^{-i}(a^{-i}|s)|$
$\displaystyle\leq\;$
$\displaystyle\sum_{\ell=1}^{z_{k}}\max_{s\in\mathcal{S}}\sum_{a^{i},a^{-i}}\pi_{k-\ell+1}^{i}(a^{i}|s)|\pi_{k-\ell+1}^{-i}(a^{-i}|s)-\pi_{k}^{-i}(a^{-i}|s)|$
$\displaystyle+\sum_{\ell=1}^{z_{k}}\max_{s\in\mathcal{S}}\sum_{a^{i},a^{-i}}|\pi_{k-\ell+1}^{i}(a^{i}|s)-\pi_{k}^{i}(a^{i}|s)|\pi_{k}^{-i}(a^{-i}|s)$
$\displaystyle=\;$
$\displaystyle\sum_{\ell=1}^{z_{k}}\max_{s\in\mathcal{S}}\left(\sum_{a^{-i}}|\pi_{k-\ell+1}^{-i}(a^{-i}|s)-\pi_{k}^{-i}(a^{-i}|s)|+\sum_{a^{i}}|\pi_{k-\ell+1}^{i}(a^{i}|s)-\pi_{k}^{i}(a^{i}|s)|\right)$
$\displaystyle=\;$
$\displaystyle\sum_{\ell=1}^{z_{k}}\max_{s\in\mathcal{S}}\left(\|\pi_{k-\ell+1}^{-i}(s)-\pi_{k}^{-i}(s)\|_{1}+\|\pi_{k-\ell+1}^{i}(s)-\pi_{k}^{i}(s)\|_{1}\right)$
$\displaystyle\leq\;$ $\displaystyle
A_{\max}^{1/2}\sum_{\ell=1}^{z_{k}}\max_{s\in\mathcal{S}}\left(\|\pi_{k-\ell+1}^{-i}(s)-\pi_{k}^{-i}(s)\|_{2}+\|\pi_{k-\ell+1}^{i}(s)-\pi_{k}^{i}(s)\|_{2}\right)$
$\displaystyle\leq\;$ $\displaystyle
4z_{k}\beta_{k-z_{k},k-1}A_{\max}^{1/2}\max_{s\in\mathcal{S}}\left(\|\pi_{k}^{-i}(s)\|_{2}+\|\pi_{k}^{i}(s)\|_{2}+2\right)$
(Lemma A.14) $\displaystyle\leq\;$ $\displaystyle
16z_{k}\beta_{k-z_{k},k-1}A_{\max}^{1/2}$ $\displaystyle\leq\;$ $\displaystyle
16z_{k}\beta_{k-z_{k},k-1}A_{\max}^{1/2}.$

It then follows from the previous inequality that

$\displaystyle\|\mathbb{E}[F^{i}(q_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\mid\mathcal{F}_{k-z_{k}}]-\bar{F}_{k}^{i}(q_{k-z_{k}}^{i})\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\left\\{\left\|\prod_{j=k+1}^{k+z_{k}}P_{\pi_{j-z_{k}}}-P_{\pi_{k}}^{z_{k}}\right\|_{\infty}+2\rho_{\tau}^{z_{k}}\right\\}\left(\|q_{k-z_{k}}^{i}\|_{2}+\frac{1}{1-\gamma}\right)$
$\displaystyle\leq\;$
$\displaystyle\left(16A_{\max}^{1/2}z_{k}\beta_{k-z_{k},k-1}+2\rho_{\tau}^{z_{k}}\right)\left(\|q_{k-z_{k}}^{i}\|_{2}+\frac{1}{1-\gamma}\right)$
$\displaystyle\leq\;$
$\displaystyle\frac{2\sqrt{|\mathcal{S}|A_{\max}}}{1-\gamma}\left(16A_{\max}^{1/2}z_{k}\beta_{k-z_{k},k-1}+2\rho_{\tau}^{z_{k}}\right)$
$\displaystyle\leq\;$
$\displaystyle\frac{2\sqrt{|\mathcal{S}|A_{\max}}}{1-\gamma}\left(16A_{\max}^{1/2}z_{k}\beta_{k-z_{k},k-1}+2\beta_{k}\right)$
(Definition of $z_{k}$) $\displaystyle\leq\;$
$\displaystyle\frac{36\sqrt{|\mathcal{S}|}A_{\max}z_{k}\beta_{k-z_{k},k-1}}{1-\gamma}$

Substituting the previous inequality and the bound in Eq. (60) into Eq. (58)
and we have

$\displaystyle N_{2,1,1}\leq\;$
$\displaystyle\frac{42|\mathcal{S}|A_{\max}^{1/2}\hat{L}_{\tau}\beta_{k-z_{k},k-1}}{1-\gamma}+\frac{36\sqrt{|\mathcal{S}|}A_{\max}z_{k}\beta_{k-z_{k},k-1}}{1-\gamma}$
$\displaystyle\leq\;$
$\displaystyle\frac{80|\mathcal{S}|A_{\max}\hat{L}_{\tau}z_{k}\beta_{k-z_{k},k-1}}{1-\gamma}.$

It follows that

$\displaystyle
N_{2,1}\leq\frac{2\sqrt{|\mathcal{S}|A_{\max}}}{1-\gamma}\mathbb{E}[N_{2,1,1}]\leq\frac{160|\mathcal{S}|^{3/2}A_{\max}^{3/2}\hat{L}_{\tau}}{(1-\gamma)^{2}}z_{k}\beta_{k-z_{k},k-1}.$

##### The Term $N_{2,2}$.

For any $k\geq z_{k}$, we have

$\displaystyle N_{2,2}=\;$ $\displaystyle\mathbb{E}[\langle
F^{i}(q_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-\bar{F}_{k-z_{k}}^{i}(q_{k-z_{k}}^{i}),q_{k}^{i}-q_{k-z_{k}}^{i}\rangle]$
$\displaystyle\leq\;$
$\displaystyle\mathbb{E}[\underbrace{\|F^{i}(q_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-\bar{F}_{k-z_{k}}^{i}(q_{k-z_{k}}^{i})\|_{2}}_{N_{2,2,1}}\underbrace{\|q_{k}^{i}-q_{k-z_{k}}^{i}\|_{2}}_{N_{2,2,2}}]$

Using Lemma A.9 and we have

$\displaystyle N_{2,2,1}$ $\displaystyle=\;$
$\displaystyle\|F^{i}(q_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-\bar{F}_{k-z_{k}}^{i}(q_{k-z_{k}}^{i})\|_{2}$
$\displaystyle=\;$
$\displaystyle\|F^{i}(q_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\\!-\\!F^{i}(\bm{0},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\\!+\\!F^{i}(\bm{0},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\|_{2}$
$\displaystyle+\|\bar{F}_{k-z_{k}}^{i}(q_{k-z_{k}}^{i})-\bar{F}_{k-z_{k}}^{i}(\bm{0})+\bar{F}_{k-z_{k}}^{i}(\bm{0})\|_{2}$
$\displaystyle\leq\;$ $\displaystyle
2\|q_{k-z_{k}}^{i}\|_{2}+\frac{2}{1-\gamma}$ (Lemma A.1 and Jensen’s
inequality) $\displaystyle\leq\;$
$\displaystyle\frac{2|\mathcal{S}|^{1/2}A_{\max}^{1/2}}{1-\gamma}+\frac{2}{1-\gamma}$
(Lemma A.1) $\displaystyle\leq\;$
$\displaystyle\frac{4|\mathcal{S}|^{1/2}A_{\max}^{1/2}}{1-\gamma}.$

Moreover, we have by Lemma A.13 and Lemma A.1 that

$\displaystyle N_{2,2,2}\leq
4\alpha_{k-z_{k},k-1}\left(\|q_{k}^{i}\|_{2}+\frac{1}{1-\gamma}\right)\leq\frac{8|\mathcal{S}|^{1/2}A_{\max}^{1/2}\alpha_{k-z_{k},k-1}}{1-\gamma}.$

Therefore, we have

$\displaystyle N_{2,2}\leq\mathbb{E}[N_{2,2,1}\times
N_{2,2,2}]\leq\frac{32|\mathcal{S}|A_{\max}}{(1-\gamma)^{2}}\alpha_{k-z_{k},k-1}.$

##### The Term $N_{2,3}$.

For any $k\geq z_{k}$, we have

$\displaystyle N_{2,3}=\;$ $\displaystyle\mathbb{E}[\langle
F^{i}(q_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-\bar{F}_{k-z_{k}}^{i}(q_{k-z_{k}}^{i}),\bar{q}_{k-z_{k}}^{i}-\bar{q}_{k}^{i}\rangle]$
$\displaystyle\leq\;$
$\displaystyle\frac{c^{\prime}}{2}\mathbb{E}[\underbrace{\|F^{i}(q_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-\bar{F}_{k-z_{k}}^{i}(q_{k-z_{k}}^{i})\|_{2}^{2}}_{N_{2,3,1}}]+\frac{1}{2c^{\prime}}\mathbb{E}[\underbrace{\|\bar{q}_{k-z_{k}}^{i}-\bar{q}_{k}^{i}\|_{2}^{2}}_{N_{2,3,2}}],$

where $c^{\prime}>0$ is any positive real number. Since
$N_{2,3,1}=N_{2,2,1}^{2}$, we have

$\displaystyle N_{2,3,1}\leq\frac{16|\mathcal{S}|A_{\max}}{(1-\gamma)^{2}}.$

To control the term $N_{2,3,2}$, using the explicit expression of
$\bar{q}_{k}^{i}$ provided in Lemma A.9 (3) and we have

$\displaystyle\|\bar{q}_{k-z_{k}}^{i}-\bar{q}_{k}^{i}\|_{2}^{2}=\;$
$\displaystyle\sum_{s}\|\mathcal{T}^{i}(v^{i})(s)(\pi_{k-z_{k}}^{-i}(s)-\pi_{k}^{-i}(s))\|_{2}^{2}.$

Since

$\displaystyle\|\mathcal{T}^{i}(v^{i})(s)(\pi_{k}^{-i}(s)-\pi_{k-z_{k}}^{-i}(s))\|_{2}\leq\;$
$\displaystyle\frac{A_{\max}}{1-\gamma}\|\pi_{k}^{-i}(s)-\pi_{k-z_{k}}^{-i}(s)\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\frac{4A_{\max}\beta_{k-z_{k},k-1}}{1-\gamma}(\|\pi_{k}^{-i}(s)\|_{2}+1)$
(Lemma A.14) $\displaystyle\leq\;$
$\displaystyle\frac{8A_{\max}\beta_{k-z_{k},k-1}}{1-\gamma},$

we have

$\displaystyle
N_{2,3,2}\leq\frac{64|\mathcal{S}|A_{\max}^{2}\beta_{k-z_{k},k-1}^{2}}{(1-\gamma)^{2}}$

It follows that

$\displaystyle N_{2,3}=\;$
$\displaystyle\frac{c^{\prime}}{2}\mathbb{E}[N_{2,3,1}]+\frac{1}{2c^{\prime}}\mathbb{E}[N_{2,3,2}]$
$\displaystyle\leq\;$
$\displaystyle\frac{8c^{\prime}|\mathcal{S}|A_{\max}}{(1-\gamma)^{2}}+\frac{32|\mathcal{S}|A_{\max}^{2}\beta_{k-z_{k},k-1}^{2}}{c^{\prime}(1-\gamma)^{2}}$
$\displaystyle\leq\;$
$\displaystyle\frac{8|\mathcal{S}|A_{\max}}{(1-\gamma)^{2}}\left(c^{\prime}+\frac{4A_{\max}\beta_{k-z_{k},k-1}^{2}}{c^{\prime}}\right)$
$\displaystyle=\;$
$\displaystyle\frac{32|\mathcal{S}|A_{\max}^{3/2}\beta_{k-z_{k},k-1}}{(1-\gamma)^{2}},$

where the last line follows by choosing
$c^{\prime}=2A_{\max}^{1/2}\beta_{k-z_{k},k-1}$.

##### The Term $N_{2,4}$.

For any $k\geq 0$, we have

$\displaystyle N_{2,4}=\;$ $\displaystyle\mathbb{E}[\langle
F^{i}(q_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-F^{i}(q_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1}),q_{k}^{i}-\bar{q}_{k}^{i}\rangle]$
$\displaystyle\leq\;$
$\displaystyle\mathbb{E}[\|F^{i}(q_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-F^{i}(q_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\|_{2}\|q_{k}^{i}-\bar{q}_{k}^{i}\|_{2}]$
$\displaystyle\leq\;$
$\displaystyle\mathbb{E}[\|q_{k}^{i}-q_{k-z_{k}}^{i}\|_{2}\|q_{k}^{i}-\bar{q}_{k}^{i}\|_{2}]$
(Lemma A.9) $\displaystyle\leq\;$ $\displaystyle
4\alpha_{k-z_{k},k-1}\mathbb{E}\left[\left(\|q_{k}^{i}\|_{2}+\frac{1}{1-\gamma}\right)\|q_{k}^{i}-\bar{q}_{k}^{i}\|_{2}\right]$
(Lemma A.13) $\displaystyle\leq\;$
$\displaystyle\frac{16|\mathcal{S}|A_{\max}\alpha_{k-z_{k},k-1}}{(1-\gamma)^{2}},$

where the last line follows from
$\|q_{k}^{i}\|_{\infty}\leq\frac{1}{1-\gamma}$ and
$\|\bar{q}_{k}^{i}\|_{\infty}\leq\frac{1}{1-\gamma}$.

##### The Term $N_{2,5}$.

For any $k\geq 0$, we have

$\displaystyle N_{2,5}=\;$
$\displaystyle\mathbb{E}[\langle\bar{F}_{k}^{i}(q_{k}^{i})-\bar{F}_{k-z_{k}}^{i}(q_{k-z_{k}}^{i}),q_{k}^{i}-\bar{q}_{k}^{i}\rangle]$
$\displaystyle\leq\;$
$\displaystyle\mathbb{E}[\|\bar{F}_{k}^{i}(q_{k}^{i})-\bar{F}_{k-z_{k}}^{i}(q_{k-z_{k}}^{i})\|_{2}\|q_{k}^{i}-\bar{q}_{k}^{i}\|_{2}]$
$\displaystyle\leq\;$
$\displaystyle\mathbb{E}[(\|\bar{F}_{k}^{i}(q_{k}^{i})-\bar{F}_{k-z_{k}}^{i}(q_{k}^{i})\|_{2}+\|\bar{F}_{k-z_{k}}^{i}(q_{k}^{i})-\bar{F}_{k-z_{k}}^{i}(q_{k-z_{k}}^{i})\|_{2})\|q_{k}^{i}-\bar{q}_{k}^{i}\|_{2}]$
$\displaystyle\leq\;$
$\displaystyle\mathbb{E}[\|q_{k}^{i}-q_{k-z_{k}}^{i}\|_{2}\|q_{k}^{i}-\bar{q}_{k}^{i}\|_{2}]+\frac{42|\mathcal{S}|A_{\max}^{1/2}\hat{L}_{\tau}\beta_{k-z_{k},k-1}}{1-\gamma}\mathbb{E}[\|q_{k}^{i}-\bar{q}_{k}^{i}\|_{2}]$
(Lemma A.9 and Eq. (60)) $\displaystyle\leq\;$ $\displaystyle
4\alpha_{k-z_{k},k-1}\mathbb{E}\left[\left(\|q_{k}^{i}\|_{2}+\frac{1}{1-\gamma}\right)\|q_{k}^{i}-\bar{q}_{k}^{i}\|_{2}\right]$
(Lemma A.13)
$\displaystyle+\frac{42|\mathcal{S}|A_{\max}^{1/2}\hat{L}_{\tau}\beta_{k-z_{k},k-1}}{1-\gamma}\mathbb{E}[\|q_{k}^{i}-\bar{q}_{k}^{i}\|_{2}]$
$\displaystyle\leq\;$
$\displaystyle\frac{16|\mathcal{S}|A_{\max}\alpha_{k-z_{k},k-1}}{(1-\gamma)^{2}}+\frac{84|\mathcal{S}|^{3/2}A_{\max}\hat{L}_{\tau}\beta_{k-z_{k},k-1}}{(1-\gamma)^{2}}$
$\displaystyle\leq\;$
$\displaystyle\frac{100|\mathcal{S}|^{3/2}A_{\max}\hat{L}_{\tau}\alpha_{k-z_{k},k-1}}{(1-\gamma)^{2}}.$

Finally, combining the upper bounds we derived for the terms
$\\{N_{2,j}\\}_{1\leq j\leq 5}$ and we have

$\displaystyle N_{2}\leq\;$ $\displaystyle\sum_{j=1}^{5}N_{2,j}$
$\displaystyle\leq\;$
$\displaystyle\frac{160|\mathcal{S}|^{3/2}A_{\max}^{3/2}\hat{L}_{\tau}}{(1-\gamma)^{2}}z_{k}\beta_{k-z_{k},k-1}+\frac{32|\mathcal{S}|A_{\max}}{(1-\gamma)^{2}}\alpha_{k-z_{k},k-1}$
$\displaystyle+\frac{32|\mathcal{S}|A_{\max}^{3/2}\beta_{k-z_{k},k-1}}{(1-\gamma)^{2}}+\frac{16|\mathcal{S}|A_{\max}\alpha_{k-z_{k},k-1}}{(1-\gamma)^{2}}$
$\displaystyle+\frac{100|\mathcal{S}|^{3/2}A_{\max}\hat{L}_{\tau}\alpha_{k-z_{k},k-1}}{(1-\gamma)^{2}}$
$\displaystyle\leq\;$
$\displaystyle\frac{340|\mathcal{S}|^{3/2}A_{\max}^{3/2}\hat{L}_{\tau}}{(1-\gamma)^{2}}z_{k}\alpha_{k-z_{k},k-1}.$

####  A.7.12 Proof of Lemma A.11

  1. (1)

For any $k\geq 0$, using Lemma A.9 and we have

$\displaystyle\|q_{k+1}^{i}-q_{k}^{i}\|_{2}^{2}=\;$
$\displaystyle\alpha_{k}^{2}\|F^{i}(q_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\|_{2}^{2}$
$\displaystyle=\;$
$\displaystyle\alpha_{k}^{2}\|F^{i}(q_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-F^{i}(\bm{0},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})$
$\displaystyle+F^{i}(\bm{0},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\|_{2}^{2}$
$\displaystyle\leq\;$
$\displaystyle\alpha_{k}^{2}\left(\|q_{k}^{i}\|_{2}+\frac{1}{1-\gamma}\right)^{2}$
$\displaystyle\leq\;$
$\displaystyle\alpha_{k}^{2}\left(\frac{\sqrt{|\mathcal{S}|A_{\max}}}{1-\gamma}+\frac{1}{1-\gamma}\right)^{2}$
($\|q_{k}^{i}\|_{\infty}\leq\frac{1}{1-\gamma}$) $\displaystyle\leq\;$
$\displaystyle\frac{4|\mathcal{S}|A_{\max}\alpha_{k}^{2}}{(1-\gamma)^{2}}.$

The result follows by taking expectation on both sides of the previous
inequality.

  2. (2)

For any $k\geq 0$, we have by Lemma A.9 that

$\displaystyle\|\bar{q}_{k}^{i}-\bar{q}_{k+1}^{i}\|_{2}^{2}=\;$
$\displaystyle\sum_{s}\|\mathcal{T}^{i}(v^{i})(s)(\pi_{k+1}^{-i}(s)-\pi_{k}^{-i}(s))\|_{2}^{2}$
$\displaystyle=\;$
$\displaystyle\beta_{k}^{2}\sum_{s}\|\mathcal{T}^{i}(v^{i})(s)(\sigma_{\tau}(q_{k}^{-i}(s))-\pi_{k}^{-i}(s))\|_{2}^{2}$
$\displaystyle\leq\;$
$\displaystyle\beta_{k}^{2}\sum_{s}(\|\mathcal{T}^{i}(v^{i})(s)\sigma_{\tau}(q_{k}^{-i}(s))\|_{2}+\|\mathcal{T}^{i}(v^{i})(s)\pi_{k}^{-i}(s)\|_{2})^{2}$
$\displaystyle\leq\;$
$\displaystyle\frac{4|\mathcal{S}|A_{\max}\beta_{k}^{2}}{(1-\gamma)^{2}}.$

The result follows by taking expectation on both sides of the previous
inequality.

  3. (3)

For any $k\geq 0$, we have

$\displaystyle\langle
q_{k+1}^{i}-q_{k}^{i},\bar{q}_{k}^{i}-\bar{q}_{k+1}^{i}\rangle\leq\|q_{k+1}^{i}-q_{k}^{i}\|_{2}\|\bar{q}_{k}^{i}-\bar{q}_{k+1}^{i}\|_{2}\leq\frac{4|\mathcal{S}|A_{\max}\alpha_{k}\beta_{k}}{(1-\gamma)^{2}},$

where the last inequality follows from Part (1) and Part (2) of this lemma.
The result follows by taking expectation on both sides of the previous
inequality.

  4. (4)

For any $k\geq 0$, we have

$\displaystyle\langle
q_{k}^{i}-\bar{q}_{k}^{i},\bar{q}_{k}^{i}-\bar{q}_{k+1}^{i}\rangle$
$\displaystyle=\;$ $\displaystyle\beta_{k}\sum_{s}\langle
q_{k}^{i}(s)-\bar{q}_{k}^{i}(s),\mathcal{T}^{i}(v^{i})(s)(\sigma_{\tau}(q_{k}^{-i}(s))-\pi_{k}^{-i}(s))\rangle$
$\displaystyle\leq\;$
$\displaystyle\beta_{k}\left(\frac{\hat{c}\|q_{k}^{i}-\bar{q}_{k}^{i}\|_{2}^{2}}{2}+\frac{\sum_{s}\|\mathcal{T}^{i}(v^{i})(s)(\sigma_{\tau}(q_{k}^{-i}(s))-\pi_{k}^{-i}(s))\|_{2}^{2}}{2\hat{c}}\right),$
(62)

where $\hat{c}$ is an arbitrary positive real number. We next analyze the
second term on the RHS of the previous inequality. For any $s\in\mathcal{S}$,
we have

$\displaystyle\|\mathcal{T}^{i}(v^{i})(s)(\sigma_{\tau}(q_{k}^{-i}(s))-\pi_{k}^{-i}(s))\|_{2}$
$\displaystyle=\;$
$\displaystyle\|\mathcal{T}^{i}(v^{i})(s)(\sigma_{\tau}(q_{k}^{-i}(s))-\sigma_{\tau}(\bar{q}_{k}^{-i}(s))+\sigma_{\tau}(\mathcal{T}^{-i}(v^{-i})(s)\pi_{k}^{i}(s))-\pi_{k}^{-i}(s))\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\underbrace{\|\mathcal{T}^{i}(v^{i})(s)(\sigma_{\tau}(q_{k}^{-i}(s))-\sigma_{\tau}(\bar{q}_{k}^{-i}(s)))\|_{2}}_{B_{1}}$
$\displaystyle+\underbrace{\|\mathcal{T}^{i}(v^{i})(s)(\sigma_{\tau}(\mathcal{T}^{-i}(v^{-i})(s)\pi_{k}^{i}(s))-\pi_{k}^{-i}(s))\|_{2}}_{B_{2}}.$

Since the softmax operator $\sigma_{\tau}(\cdot)$ is $\frac{1}{\tau}$ –
Lipschitz continuous with respect to $\|\cdot\|_{2}$ (Gao and Pavel, , 2017,
Proposition 4), we have

$\displaystyle B_{1}\leq\;$
$\displaystyle\|\mathcal{T}^{i}(v^{i})(s)\|_{2}\|\sigma_{\tau}(q_{k}^{-i}(s))-\sigma_{\tau}(\bar{q}_{k}^{-i}(s))\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\frac{A_{\max}}{\tau(1-\gamma)}\|q_{k}^{-i}(s)-\bar{q}_{k}^{-i}(s)\|_{2}.$

We next analyze the term $B_{2}$. Using the quadratic growth property of
strongly convex functions and we have

$\displaystyle B_{2}=\;$
$\displaystyle\|\mathcal{T}^{i}(v^{i})(s)(\sigma_{\tau}(\mathcal{T}^{-i}(v^{-i})(s)\pi_{k}^{i}(s))-\pi_{k}^{-i}(s))\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\|\mathcal{T}^{i}(v^{i})(s)\|_{2}\|\sigma_{\tau}(\mathcal{T}^{-i}(v^{-i})(s)\pi_{k}^{i}(s))-\pi_{k}^{-i}(s)\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\frac{\sqrt{2}A_{\max}}{\sqrt{\tau}(1-\gamma)}V_{v,s}^{1/2}(\pi_{k}^{i}(s),\pi_{k}^{-i}(s)).$

Combine the upper bounds we obtained for the terms $B_{1}$ and $B_{2}$ and we
obtain

$\displaystyle\sum_{s}\|\mathcal{T}^{i}(v^{i})(s)(\sigma_{\tau}(q_{k}^{-i}(s))-\pi_{k}^{-i}(s))\|_{2}^{2}$
$\displaystyle\leq\;$ $\displaystyle\sum_{s}(B_{1}+B_{2})^{2}$
$\displaystyle\leq\;$ $\displaystyle 2\sum_{s}(B_{1}^{2}+B_{2}^{2})$
$\displaystyle\leq\;$ $\displaystyle
2\sum_{s}\left(\frac{A_{\max}^{2}}{\tau^{2}(1-\gamma)^{2}}\|q_{k}^{-i}(s))-\bar{q}_{k}^{-i}(s)\|_{2}^{2}+\frac{2A_{\max}^{2}}{\tau(1-\gamma)^{2}}V_{v,s}(\pi_{k}^{i}(s),\pi_{k}^{-i}(s))\right)$
$\displaystyle=\;$
$\displaystyle\frac{2A_{\max}^{2}}{\tau^{2}(1-\gamma)^{2}}\|q_{k}^{-i}-\bar{q}_{k}^{-i}\|_{2}^{2}+\frac{4A_{\max}^{2}}{\tau(1-\gamma)^{2}}\sum_{s}V_{v,s}(\pi_{k}^{i}(s),\pi_{k}^{-i}(s)).$

Coming back to Eq. (62), using the previous inequality and we have

$\displaystyle\langle
q_{k}^{i}-\bar{q}_{k}^{i},\bar{q}_{k}^{i}-\bar{q}_{k+1}^{i}\rangle$
$\displaystyle\leq\;$
$\displaystyle\beta_{k}\left(\frac{\hat{c}\|q_{k}^{i}-\bar{q}_{k}^{i}\|_{2}^{2}}{2}+\frac{\sum_{s}\|\mathcal{T}^{i}(v^{i})(s)(\sigma_{\tau}(q_{k}^{-i}(s))-\pi_{k}^{-i}(s))\|_{2}^{2}}{2\hat{c}}\right)$
$\displaystyle\leq\;$
$\displaystyle\beta_{k}\left(\frac{\hat{c}\|q_{k}^{i}-\bar{q}_{k}^{i}\|_{2}^{2}}{2}+\frac{A_{\max}^{2}}{\hat{c}\tau^{2}(1-\gamma)^{2}}\|q_{k}^{-i}-\bar{q}_{k}^{-i}\|_{2}^{2}\right.$
$\displaystyle\left.+\frac{2A_{\max}^{2}}{\hat{c}\tau(1-\gamma)^{2}}\sum_{s}V_{v,s}(\pi_{k}^{i}(s),\pi_{k}^{-i}(s))\right).$

Choosing $\hat{c}=\frac{32A_{\max}^{2}}{\tau(1-\gamma)^{2}}$ in the previous
inequality and then taking total expectation, and we obtain

$\displaystyle\mathbb{E}[\langle
q_{k}^{i}-\bar{q}_{k}^{i},\bar{q}_{k}^{i}-\bar{q}_{k+1}^{i}\rangle]\leq\frac{17A_{\max}^{2}\beta_{k}}{\tau(1-\gamma)^{2}}\mathbb{E}[\|q_{k}^{i}-\bar{q}_{k}^{i}\|_{2}^{2}]+\frac{\beta_{k}}{16}\sum_{s}\mathbb{E}[V_{v,s}(\pi_{k}^{i}(s),\pi_{k}^{-i}(s))].$

####  A.7.13 Proof of Lemma A.12

For $i\in\\{1,2\\}$, we have from Eq. (31), Eq. (32), Lemma A.10, and Lemma
A.11 that

$\displaystyle\mathbb{E}[\|q_{k+1}^{i}-\bar{q}_{k+1}^{i}\|_{2}^{2}]$
$\displaystyle\leq\;$
$\displaystyle\mathbb{E}[\|q_{k}^{i}-\bar{q}_{k}^{i}\|_{2}^{2}]-\alpha_{k}c_{\tau}\mathbb{E}[\|q_{k}^{i}-\bar{q}_{k}^{i}\|_{2}^{2}]$
$\displaystyle+\frac{4|\mathcal{S}|A_{\max}}{(1-\gamma)^{2}}(\alpha_{k}^{2}+\alpha_{k}\beta_{k}+\beta_{k}^{2})$
$\displaystyle+\frac{340|\mathcal{S}|^{3/2}A_{\max}^{3/2}\hat{L}_{\tau}}{(1-\gamma)^{2}}z_{k}\alpha_{k}\alpha_{k-z_{k},k-1}$
$\displaystyle+\frac{17A_{\max}^{2}\beta_{k}}{\tau(1-\gamma)^{2}}\mathbb{E}[\|q_{k}^{i}-\bar{q}_{k}^{i}\|_{2}^{2}]+\frac{\beta_{k}}{16}\sum_{s}\mathbb{E}[V_{v,s}(\pi_{k}^{i}(s),\pi_{k}^{-i}(s))]$
$\displaystyle\leq\;$
$\displaystyle\left(1-\alpha_{k}c_{\tau}+\frac{17A_{\max}^{2}\beta_{k}}{\tau(1-\gamma)^{2}}\right)\mathbb{E}[\|q_{k}^{i}-\bar{q}_{k}^{i}\|_{2}^{2}]$
$\displaystyle+\frac{12|\mathcal{S}|A_{\max}}{(1-\gamma)^{2}}\alpha_{k}^{2}+\frac{340|\mathcal{S}|^{3/2}A_{\max}^{3/2}\hat{L}_{\tau}}{(1-\gamma)^{2}}z_{k}\alpha_{k}\alpha_{k-z_{k},k-1}$
$\displaystyle+\frac{\beta_{k}}{16}\sum_{s}\mathbb{E}[V_{v,s}(\pi_{k}^{i}(s),\pi_{k}^{-i}(s))]$
$\displaystyle\leq\;$
$\displaystyle\left(1-\alpha_{k}c_{\tau}+\frac{17A_{\max}^{2}\beta_{k}}{\tau(1-\gamma)^{2}}\right)\mathbb{E}[\|q_{k}^{i}-\bar{q}_{k}^{i}\|_{2}^{2}]$
$\displaystyle+\frac{352|\mathcal{S}|^{3/2}A_{\max}^{3/2}\hat{L}_{\tau}}{(1-\gamma)^{2}}z_{k}\alpha_{k}\alpha_{k-z_{k},k-1}+\frac{\beta_{k}}{16}\sum_{s}\mathbb{E}[V_{v,s}(\pi_{k}^{i}(s),\pi_{k}^{-i}(s))],$

where the second inequality follows from
$\beta_{k}=c_{\alpha,\beta}\alpha_{k}$ with $c_{\alpha,\beta}\leq 1$.

####  A.7.14 Proof of Lemma A.13

For any $k\in[k_{1},k_{2}-1]$, we have

$\displaystyle\|q_{k+1}^{i}\|_{2}-\|q_{k}^{i}\|_{2}\leq\;$
$\displaystyle\|q_{k+1}^{i}-q_{k}^{i}\|_{2}$ (triangle inequality)
$\displaystyle=\;$
$\displaystyle\alpha_{k}\|F^{i}(q_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\alpha_{k}\|F^{i}(q_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-F^{i}(\bm{0},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\|_{2}$
$\displaystyle+\alpha_{k}\|F^{i}(\bm{0},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\alpha_{k}\left(\|q_{k}^{i}\|_{2}+\frac{1}{1-\gamma}\right),$
(63)

where the last inequality follows from Lemma A.9. Adding $1/(1-\gamma)$ to
both sides of the previous inequality and we have

$\displaystyle\|q_{k+1}^{i}\|_{2}+\frac{1}{1-\gamma}\leq(1+\alpha_{k})\left(\|q_{k}^{i}\|_{2}+\frac{1}{1-\gamma}\right).$

Repeatedly using the previous inequality and we have for all
$k\in[k_{1},k_{2}]$:

$\displaystyle\|q_{k}^{i}\|_{2}\leq\prod_{j=k_{1}}^{k-1}(1+\alpha_{j})\left(\|q_{k_{1}}^{i}\|_{2}+\frac{1}{1-\gamma}\right)-\frac{1}{1-\gamma}.$

Since $1+x\leq e^{x}\leq 1+2x$ for all $x\in[0,1/2]$ and
$\alpha_{k_{1},k_{2}-1}\leq 1/4$, we have

$\displaystyle\prod_{j=k_{1}}^{k-1}(1+\alpha_{j})\leq\exp\left(\alpha_{k_{1},k-1}\right)\leq
1+2\alpha_{k_{1},k-1}.$

As a result, we have for all $k\in[k_{1},k_{2}]$ that

$\displaystyle\|q_{k}^{i}\|_{2}\leq(1+2\alpha_{k_{1},k-1})\|q_{k_{1}}^{i}\|_{2}+\frac{2\alpha_{k_{1},k-1}}{1-\gamma}.$

Using the previous inequality in Eq. (63) and we have for any
$k\in[k_{1},k_{2}-1]$:

$\displaystyle\|q_{k+1}^{i}-q_{k}^{i}\|_{2}$
$\displaystyle\leq\alpha_{k}\left(\|q_{k}^{i}\|_{2}+\frac{1}{1-\gamma}\right)$
$\displaystyle\leq\alpha_{k}(1+2\alpha_{k_{1},k-1})\|q_{k_{1}}^{i}\|_{2}+\frac{2\alpha_{k}\alpha_{k_{1},k-1}}{1-\gamma}$
$\displaystyle\leq
2\alpha_{k}\left(\|q_{k_{1}}^{i}\|_{2}+\frac{1}{1-\gamma}\right),$

where the last line follows from $\alpha_{k_{1},k-1}\leq 1/4$. Therefore, we
have for any $k\in[k_{1},k_{2}]$:

$\displaystyle\|q_{k}^{i}-q_{k_{1}}^{i}\|_{2}\leq\;$
$\displaystyle\sum_{j=k_{1}}^{k-1}\|q_{j+1}^{i}-q_{j}^{i}\|_{2}$
$\displaystyle\leq\;$ $\displaystyle
2\sum_{j=k_{1}}^{k-1}\alpha_{j}\left(\|q_{k_{1}}^{i}\|_{2}+\frac{1}{1-\gamma}\right)$
$\displaystyle=\;$ $\displaystyle
2\alpha_{k_{1},k-1}\left(\|q_{k_{1}}^{i}\|_{2}+\frac{1}{1-\gamma}\right)$
$\displaystyle\leq\;$ $\displaystyle
2\alpha_{k_{1},k_{2}-1}\left(\|q_{k_{1}}^{i}\|_{2}+\frac{1}{1-\gamma}\right),$

where the last line follows from
$\alpha_{k_{1},k-1}\leq\alpha_{k_{1},k_{2}-1}$. This proves the first claimed
inequality.

To prove the second claimed inequality, note that

$\displaystyle\|q_{k_{2}}^{i}-q_{k_{1}}^{i}\|_{2}$ $\displaystyle\leq
2\alpha_{k_{1},k_{2}-1}\left(\|q_{k_{1}}^{i}\|_{2}+\frac{1}{1-\gamma}\right)$
$\displaystyle\leq
2\alpha_{k_{1},k_{2}-1}\left(\|q_{k_{1}}^{i}-q_{k_{2}}^{i}\|_{2}+\|q_{k_{2}}^{i}\|_{2}+\frac{1}{1-\gamma}\right)$
$\displaystyle\leq\frac{1}{2}\|q_{k_{2}}^{i}-q_{k_{1}}^{i}\|_{2}+2\alpha_{k_{1},k_{2}-1}\left(\|q_{k_{2}}^{i}\|_{2}+\frac{1}{1-\gamma}\right),$

we have $\|q_{k_{2}}^{i}-q_{k_{1}}^{i}\|_{2}\leq
4\alpha_{k_{1},k_{2}-1}(\|q_{k_{2}}^{i}\|_{2}+1/(1-\gamma))$. Therefore, we
have for any $k\in[k_{1},k_{2}]$:

$\displaystyle\|q_{k}^{i}-q_{k_{1}}^{i}\|_{2}$ $\displaystyle\leq
2\alpha_{k_{1},k_{2}-1}\left(\|q_{k_{1}}^{i}\|_{2}+\frac{1}{1-\gamma}\right)$
$\displaystyle\leq
2\alpha_{k_{1},k_{2}-1}\left(\|q_{k_{1}}^{i}-q_{k_{2}}^{i}\|_{2}+\|q_{k_{2}}^{i}\|_{2}+\frac{1}{1-\gamma}\right)$
$\displaystyle\leq
2\alpha_{k_{1},k_{2}-1}\left(4\alpha_{k_{1},k_{2}-1}\left(\|q_{k_{2}}^{i}\|_{2}+\frac{1}{1-\gamma}\right)+\|q_{k_{2}}^{i}\|_{2}+\frac{1}{1-\gamma}\right)$
$\displaystyle\leq
4\alpha_{k_{1},k_{2}-1}\left(\|q_{k_{2}}^{i}\|_{2}+\frac{1}{1-\gamma}\right),$

where the last inequality follows from $\alpha_{k_{1},k_{2}-1}\leq 1/4$. The
proof is now complete.

####  A.7.15 Proof of Lemma A.14

For any $k\geq 0$ and $s\in\mathcal{S}$, we have

$\displaystyle\|\pi_{k+1}^{i}(s)\|_{2}-\|\pi_{k}^{i}(s)\|_{2}\leq\;$
$\displaystyle\|\pi_{k+1}^{i}(s)-\pi_{k}^{i}(s)\|_{2}$ $\displaystyle=\;$
$\displaystyle\beta_{k}\|\sigma_{\tau}(q_{k}^{i}(s))-\pi_{k}^{i}(s)\|_{2}$
$\displaystyle\leq\;$ $\displaystyle\beta_{k}(\|\pi_{k}^{i}(s)\|_{2}+1).$

The rest of the proof is identical to that of Lemma A.13 (after Eq. (63)).

##  Appendix B Proof of Theorem 2.1

Note that Algorithm 1 is a special case of Algorithm 3 when the Markov game
has only one state, and the inputs $v^{i}$ and $v^{-i}$ satisfy
$v^{i}=v^{-i}=\bm{0}$. Therefore, Lemma A.8 and Lemma A.12 are both
applicable, and are restated in the following.

######  Lemma B.1.

The following inequality holds for all $k\geq 0$.

$\displaystyle\mathbb{E}[V_{\mathcal{R}}(\pi_{k+1}^{i},\pi_{k+1}^{-i})]\leq$
$\displaystyle\left(1-\frac{3\beta_{k}}{4}\right)\mathbb{E}[V_{\mathcal{R}}(\pi_{k}^{i},\pi_{k}^{-i})]+\frac{4A_{\max}^{2}\beta_{k}^{2}}{\ell_{\tau}}$
$\displaystyle+\frac{256A_{\max}^{2}\beta_{k}}{\ell_{\tau}^{2}\tau^{3}}\sum_{i=1,2}\mathbb{E}[\|q_{k}^{i}-\mathcal{R}^{i}\pi_{k}^{-i}\|_{2}^{2}].$
(64)

######  Lemma B.2.

The following inequality holds for all $k\geq 0$:

$\displaystyle\sum_{i=1,2}\mathbb{E}[\|q_{k+1}^{i}-\mathcal{R}^{i}\pi_{k+1}^{-i}\|_{2}^{2}]\leq\;$
$\displaystyle\left(1-\ell_{\tau}\alpha_{k}+\frac{17A_{\max}^{2}\beta_{k}}{\tau}\right)\sum_{i=1,2}\mathbb{E}[\|q_{k}^{i}-\mathcal{R}^{i}\pi_{k}^{-i}\|_{2}^{2}]$
$\displaystyle+352A_{\max}^{3/2}\alpha_{k}^{2}+\frac{\beta_{k}}{8}\mathbb{E}[V_{\mathcal{R}}(\pi_{k}^{i},\pi_{k}^{-i})].$
(65)

Adding up Eqs. (B.2) and (B.1) and we have for any $k\geq 0$ that

$\displaystyle\sum_{i=1,2}\mathbb{E}[\|q_{k+1}^{i}-\mathcal{R}^{i}\pi_{k+1}^{-i}\|_{2}^{2}]+\mathbb{E}[V_{\mathcal{R}}(\pi_{k+1}^{i},\pi_{k+1}^{-i})]$
$\displaystyle\leq\;$
$\displaystyle\left(1-\ell_{\tau}\alpha_{k}+\frac{280A_{\max}^{2}\beta_{k}}{\ell_{\tau}^{2}\tau^{3}}\right)\sum_{i=1,2}\mathbb{E}[\|q_{k}^{i}-\mathcal{R}^{i}\pi_{k}^{-i}\|_{2}^{2}]$
$\displaystyle+\left(1-\frac{\beta_{k}}{2}\right)\mathbb{E}[V_{\mathcal{R}}(\pi_{k}^{i},\pi_{k}^{-i})]+\frac{4A_{\max}^{2}\beta_{k}^{2}}{\ell_{\tau}}+352A_{\max}^{3/2}\alpha_{k}^{2}$
$\displaystyle\leq$
$\displaystyle\left(1-\frac{c_{\alpha,\beta}\alpha_{k}}{2}\right)(\mathbb{E}[\|q_{k}^{i}-\mathcal{R}^{i}\pi_{k}^{-i}\|_{2}^{2}]+\mathbb{E}[V_{\mathcal{R}}(\pi_{k}^{i},\pi_{k}^{-i})])$
$\displaystyle+\frac{4A_{\max}^{2}c_{\alpha,\beta}^{2}\alpha_{k}^{2}}{\ell_{\tau}}+356A_{\max}^{3/2}\alpha_{k}^{2},$

where the last line follows from Condition A.1. Denote
$M_{k}=\mathbb{E}[V_{\mathcal{R}}(\pi_{k}^{i},\pi_{k}^{-i})]+\sum_{i=1,2}\mathbb{E}[\|q_{k}^{i}-\mathcal{R}^{i}\pi_{k}^{-i}\|_{2}^{2}]$.
The previous inequality reads

$\displaystyle
M_{k+1}\leq\left(1-\frac{c_{\alpha,\beta}\alpha_{k}}{2}\right)M_{k}+356A_{\max}^{3/2}\alpha_{k}^{2}.$

Repeatedly using the previous inequality and we have for all $k\geq 0$ that

$\displaystyle
M_{k}\leq\prod_{m=0}^{k-1}\left(1-\frac{c_{\alpha,\beta}\alpha_{m}}{2}\right)M_{0}+356A_{\max}^{3/2}\sum_{n=0}^{k-1}\alpha_{n}^{2}\prod_{m=n+1}^{k-1}\left(1-\frac{c_{\alpha,\beta}\alpha_{m}}{2}\right).$
(66)

Due to our initialization, we have

$\displaystyle
M_{0}=V_{\mathcal{R}}(\pi_{0}^{i},\pi_{0}^{-i})+\sum_{i=1,2}\|q_{0}^{i}-\mathcal{R}^{i}\pi_{0}^{-i}\|_{2}^{2}\leq
3.$

It remains to bound
$\prod_{m=0}^{k-1}\left(1-\frac{c_{\alpha,\beta}\alpha_{m}}{2}\right)$ and
$\sum_{n=0}^{k-1}\alpha_{n}^{2}\prod_{m=n+1}^{k-1}\left(1-\frac{c_{\alpha,\beta}\alpha_{m}}{2}\right)$
when $\alpha_{k}$ is explicitly chosen. Using results in (Chen et al., 2021b,
, Appendix A.2) and we have the following inequalities:

  1. (1)

When using constant stepsize, i.e., $\alpha_{k}\equiv\alpha$, we have for all
$k\geq 0$ that

$\displaystyle M_{k}\leq
3\left(1-\frac{c_{\alpha,\beta}\alpha}{2}\right)^{k}+\frac{712A_{\max}^{3/2}\alpha}{c_{\alpha,\beta}}.$

  2. (2)

When $\alpha_{k}=\frac{\alpha}{k+h}$ with $\alpha c_{\alpha,\beta}=4$ and $h$
chosen such that $\alpha/h<1$, we have for all $k\geq 0$ that

$\displaystyle M_{k}\leq
3\left(\frac{h}{k+h}\right)^{2}+356A_{\max}^{3/2}\frac{16e}{c_{\alpha,\beta}}\frac{\alpha}{k+h}.$

  3. (3)

When $\alpha_{k}=\frac{\alpha}{(k+h)^{z}}$, where $\alpha>0$, $z\in(0,1)$, and
$h\geq[4z/(c_{\alpha,\beta}\alpha)]^{1/(1-z)}$, we have for all $k\geq 0$ that

$\displaystyle M_{k}\leq
3\exp\left(-\frac{\alpha}{2c_{\alpha,\beta}(1-z)}((k+h)^{1-z}-h^{1-z})\right)+356A_{\max}^{3/2}\frac{4}{c_{\alpha,\beta}}\frac{\alpha}{(k+h)^{z}}.$

The result follows by observing that

$\displaystyle\mathbb{E}[\text{NG}(\pi_{K}^{i},\pi_{K}^{-i})]$
$\displaystyle=\;$
$\displaystyle\mathbb{E}\left[\sum_{i=1,2}\left(\max_{\hat{\pi}^{i}}(\hat{\pi}^{i})^{\top}\mathcal{R}^{i}\pi_{K}^{-i}-(\pi_{K}^{i})^{\top}\mathcal{R}^{i}\pi_{K}^{-i}\right)\right]$
$\displaystyle\leq\;$
$\displaystyle\mathbb{E}\left[\sum_{i=1,2}\left(\max_{\hat{\pi}^{i}}\left\\{(\hat{\pi}^{i})^{\top}\mathcal{R}^{i}\pi_{K}^{-i}+\tau\nu(\hat{\pi}^{i})\right\\}-(\pi_{K}^{i})^{\top}\mathcal{R}^{i}\pi_{K}^{-i}\right)\right]$
$\displaystyle\leq\;$
$\displaystyle\mathbb{E}\left[\sum_{i=1,2}\left(\max_{\hat{\pi}^{i}}\left\\{(\hat{\pi}^{i})^{\top}\mathcal{R}^{i}\pi_{K}^{-i}+\tau\nu(\hat{\pi}^{i})\right\\}-(\pi_{K}^{i})^{\top}\mathcal{R}^{i}\pi_{K}^{-i}-\tau\nu(\pi_{K}^{i})\right)\right]+\tau\log(A_{\max}^{2})$
$\displaystyle=\;$
$\displaystyle\mathbb{E}[V_{\mathcal{R}}(\pi_{K}^{i},\pi_{K}^{-i})]+\tau\log(A_{\max}^{2})$
$\displaystyle\leq\;$ $\displaystyle M_{k}+2\tau\log(A_{\max}).$

##  Appendix C Proof of Corollary 2.1.2 and Corollary 3.2.2

We first consider Corollary 2.1.2. The following proof idea was previous used
in Sayin et al.,  (2021) to show the rationality of their decentralized
$Q$-learning algorithm.

Observe that Theorem 2.1 can be easily generalized to the case where the
reward is corrupted by noise. Specifically, suppose that player $i$ takes
action $a^{i}$ and player $-i$ takes action $a^{-i}$. Instead of assuming
player $i$ receives a deterministic reward $\mathcal{R}^{i}(a^{i},a^{-i})$, we
assume that player $i$ receives a random reward $r^{i}(a^{i},a^{-i},\xi)$,
where $\xi\in\Xi$ (where $\Xi$ is a finite set) is a random variable with
distribution $\mu_{\xi}$, and is independent of everything else. The proof is
identical as long as $r^{i}+r^{-i}=0$, and the reward is uniformly bounded,
i.e., $\max_{a^{i},a^{-i},\xi}|r^{i}(a^{i},a^{-i},\xi)|<\infty$.

Now consider the case where player $i$’s opponent follows a stationary policy
$\pi^{-i}$. We incorporate the randomness of player $-i$’s action into the
model and introduce a fictitious opponent with only one action $a^{*}$. In
particular, let
$\hat{r}^{i}(a^{i},a^{*},a^{-i})=\mathcal{R}^{i}(a^{i},a^{-i})$ for all
$a^{i}$ and $a^{-i}$, and let $\hat{p}(s^{\prime}\mid
s,a^{i},a^{*})=\sum_{\pi^{-i}(a^{-i}|s)}p(s^{\prime}\mid a^{i},a^{-i},s)$. Now
the problem can be reformulated as player $i$ playing against the fictitious
player with a single action $a^{*}$, with reward function $\hat{r}^{i}$
($i\in\\{1,2\\}$) and transition probabilities $\hat{p}$. Applying Theorem 2.1
and we have the $\mathcal{O}(1/\epsilon)$ sample complexity for player $i$ to
find its best response against $\pi^{-i}$, up to a smoothing bias.

The proof of Corollary 3.2.2 is identical to that of Corollary 2.1.2.

##  Appendix D On the Mixing Time of MDPs with Almost Deterministic Policies

Consider an MDP with two states $s_{1},s_{2}$ and two actions $a_{1},a_{2}$.
The transition probability matrix $P_{1}$ of taking action $a_{1}$ is the
identity matrix $I_{2}$, and the transition probability matrix $P_{2}$ of
taking action $a_{2}$ is $P_{2}=[0,1;1,0]$. Given $\alpha\in(1/2,1)$, let
$\pi_{\alpha}$ be a policy such that $\pi(a_{1}|s)=\alpha$ and
$\pi(a_{2}|s)=1-\alpha$ for any $s\in\\{s_{1},s_{2}\\}$. Denote $P_{\alpha}$
as the transition probability matrix under $\pi_{\alpha}$. It is easy to see
that

$\displaystyle P_{\alpha}=\begin{bmatrix}\alpha&1-\alpha\\\
1-\alpha&\alpha\end{bmatrix}.$

Since $P_{\alpha}$ is a doubly stochastic matrix, and has strictly positive
entries, it has a unique stationary distribution $\mu=\bm{1}^{\top}/2$.

We next compute a lower bound of the mixing time of the $\pi_{\alpha}$-induced
Markov chain. Let $e_{1}=[1,0]^{\top}$ be the initial distribution of the
states, and denote $[x_{k},1-x_{k}]^{\top}$ as the distribution of the states
at time step $k$. Then we have

$\displaystyle x_{k+1}=\;$ $\displaystyle x_{k}\alpha+(1-x_{k})(1-\alpha)$
$\displaystyle=\;$ $\displaystyle(2\alpha-1)x_{k}+1-\alpha$ $\displaystyle=\;$
$\displaystyle(2\alpha-1)^{k+1}x_{0}+\sum_{i=0}^{k}(1-\alpha)(2\alpha-1)^{k-i}$
$\displaystyle=\;$ $\displaystyle\frac{1}{2}+\frac{(2\alpha-1)^{k+1}}{2}.$

It follows that

$\displaystyle t_{\pi_{\alpha},\eta}=\;$ $\displaystyle\min_{k\geq
0}\left\\{\max_{\mu_{0}\in\Delta^{2}}\left\|\mu_{0}^{\top}P_{\alpha}^{k}-\bm{1}^{\top}/2\right\|_{\text{TV}}\leq\eta\right\\}$
$\displaystyle\geq\;$ $\displaystyle\min_{k\geq
0}\left\\{\left\|e_{1}^{\top}P_{\alpha}^{k}-\bm{1}^{\top}/2\right\|_{\text{TV}}\leq\eta\right\\}$
$\displaystyle=\;$ $\displaystyle\min_{k\geq 0}\left\\{(2\alpha-1)^{k}\leq
2\eta\right\\}$ $\displaystyle\geq\;$
$\displaystyle\frac{\log(1/2\eta)}{\log(1/(2\alpha-1))}-1,$

which implies $\lim_{\alpha\rightarrow 1}t_{\alpha,\eta}=\infty$. Therefore,
as the policies become deterministic, the mixing time of the associated Markov
chain can approach infinity.