y_{k}^{\top}(\sigma_{\tau}(y_{k})-p(\mu,x_{k},y_{k}))+\tau\langle\nabla\nu(p(\mu,x_{k},y_{k})),p(\mu,x_{k},y_{k})-\sigma_{\tau}(y_{k})\rangle$
$\displaystyle-\frac{1}{\mu}\|x_{k}-Bp(\mu,x_{k},y_{k})\|_{2}^{2}$
$\displaystyle\leq\;$ $\displaystyle-
y_{k}^{\top}(\sigma_{\tau}(y_{k})-p(\mu,x_{k},y_{k}))-\tau(\nu(\sigma_{\tau}(y_{k}))-\nu(p(\mu,x_{k},y_{k})))-\frac{1}{\mu}\|x_{k}-Bp(\mu,x_{k},y_{k})\|_{2}^{2}$
(The concavity of $\nu(\cdot)$) $\displaystyle=\;$
$\displaystyle-\left(y_{k}^{\top}\sigma_{\tau}(y_{k})+\tau\nu(\sigma_{\tau}(y_{k}))-y_{k}^{\top}p(\mu,x_{k},y_{k})-\tau\nu(p(\mu,x_{k},y_{k}))+\frac{1}{\mu}\|x_{k}-Bp(\mu,x_{k},y_{k})\|_{2}^{2}\right)$
$\displaystyle\leq\;$ $\displaystyle-V_{1}(x_{k},y_{k}),$

where the last line follows from the definition of $V_{1}(\cdot,\cdot)$. For
the term $E_{1,2}$ on the RHS of Eq. (35), we have

$\displaystyle E_{1,2}=\;$ $\displaystyle\frac{1}{\mu}\langle
x_{k}-Bp(\mu,x_{k},y_{k}),\mathcal{E}_{k,x}\rangle$ $\displaystyle\leq\;$
$\displaystyle\frac{1}{\mu}\|x_{k}-Bp(\mu,x_{k},y_{k})\|_{2}\|\mathcal{E}_{k,x}\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\frac{\sqrt{2}}{\sqrt{\mu}}V_{1}(x_{k},y_{k})^{1/2}\|\mathcal{E}_{k,x}\|_{2}$
(Lemma A.12) $\displaystyle\leq\;$
$\displaystyle\frac{V_{1}(x_{k},y_{k})}{16}+\frac{8}{\mu}\|\mathcal{E}_{k,x}\|_{2}^{2},$

where the last line follows from $a^{2}+b^{2}\geq 2ab$. For the term $E_{1,3}$
on the RHS of Eq. (35), we have

$\displaystyle E_{1,3}=\;$
$\displaystyle\langle\sigma_{\tau}(x_{k})-q(\mu,x_{k},y_{k}),B\sigma_{\tau}(y_{k})-Bp(\mu,x_{k},y_{k})+Bp(\mu,x_{k},y_{k})-x_{k}\rangle$
$\displaystyle=\;$
$\displaystyle\langle\sigma_{\tau}(x_{k})-q(\mu,x_{k},y_{k}),Bp(\mu,x_{k},y_{k})-x_{k}\rangle$
$\displaystyle+(\sigma_{\tau}(x_{k})-q(\mu,x_{k},y_{k}))^{\top}B(\sigma_{\tau}(y_{k})-p(\mu,x_{k},y_{k}))$
$\displaystyle\leq\;$
$\displaystyle\|\sigma_{\tau}(x_{k})-q(\mu,x_{k},y_{k})\|_{2}\|Bp(\mu,x_{k},y_{k})-x_{k}\|_{2}$
$\displaystyle+(\sigma_{\tau}(x_{k})-q(\mu,x_{k},y_{k}))^{\top}B(\sigma_{\tau}(y_{k})-p(\mu,x_{k},y_{k}))$
$\displaystyle\leq\;$
$\displaystyle\frac{2\sqrt{\mu}}{\sqrt{\tau}}V_{2}(x_{k},y_{k})^{1/2}V_{1}(x_{k},y_{k})^{1/2}+(\sigma_{\tau}(x_{k})-q(\mu,x_{k},y_{k}))^{\top}B(\sigma_{\tau}(y_{k})-p(\mu,x_{k},y_{k}))$
(Lemma A.12) $\displaystyle\leq\;$
$\displaystyle\frac{\sqrt{\mu}}{\sqrt{\tau}}V(x_{k},y_{k})+(\sigma_{\tau}(x_{k})-q(\mu,x_{k},y_{k}))^{\top}B(\sigma_{\tau}(y_{k})-p(\mu,x_{k},y_{k})).$

where the last line follows from $a+b\geq 2\sqrt{ab}$ for all $a,b\geq 0$. For
the term $E_{1,4}$ on the RHS of Eq. (35), we have

$\displaystyle E_{1,4}=\;$
$\displaystyle\langle\sigma_{\tau}(x_{k})-q(\mu,x_{k},y_{k}),\mathcal{E}_{k,x}\rangle$
$\displaystyle\leq\;$
$\displaystyle\|\sigma_{\tau}(x_{k})-q(\mu,x_{k},y_{k})\|_{2}\|\mathcal{E}_{k,x}\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\frac{\sqrt{2}}{\sqrt{\tau}}V_{2}(x_{k},y_{k})^{1/2}\|\mathcal{E}_{k,x}\|_{2}$
(Lemma A.12) $\displaystyle\leq\;$
$\displaystyle\frac{V_{2}(x_{k},y_{k})}{16}+\frac{8}{\tau}\|\mathcal{E}_{k,x}\|_{2}^{2},$

where the last line follows from $a+b\geq 2\sqrt{ab}$ for all $a,b\geq 0$.
Using the upper bounds we obtained for $\\{E_{1,i}\\}_{1\leq i\leq 4}$ all
together in Eq. (35), we have

$\displaystyle E_{1}=\;$
$\displaystyle\beta_{k}(E_{1,1}+E_{1,2}+E_{1,3}+E_{1,4})$
$\displaystyle\leq\;$
$\displaystyle-\beta_{k}V_{1}(x_{k},y_{k})+\frac{\beta_{k}}{16}V(x_{k},y_{k})+8\beta_{k}\left(\frac{1}{\mu}+\frac{1}{\tau}\right)\|\mathcal{E}_{k,x}\|_{2}^{2}+\frac{\sqrt{\mu}}{\sqrt{\tau}}\beta_{k}V(x_{k},y_{k})$
$\displaystyle+\beta_{k}(\sigma_{\tau}(x_{k})-q(\mu,x_{k},y_{k}))^{\top}B(\sigma_{\tau}(y_{k})-p(\mu,x_{k},y_{k})).$

Using an identical argument, we also have

$\displaystyle E_{3}\leq\;$
$\displaystyle-\beta_{k}V_{2}(x_{k},y_{k})+\frac{\beta_{k}}{16}V(x_{k},y_{k})+8\beta_{k}\left(\frac{1}{\mu}+\frac{1}{\tau}\right)\|\mathcal{E}_{k,y}\|_{2}^{2}+\frac{\sqrt{\mu}}{\sqrt{\tau}}\beta_{k}V(x_{k},y_{k})$
$\displaystyle+\beta_{k}(\sigma_{\tau}(y_{k})-p(\mu,x_{k},y_{k}))^{\top}A(\sigma_{\tau}(x_{k})-q(\mu,x_{k},y_{k}))$

Using the upper bounds we obtained for the terms $E_{1}$ to $E_{4}$ all
together in Eq. (34), we have

$\displaystyle V(x_{k+1},y_{k+1})\leq\;$
$\displaystyle\left(1-\frac{7}{8}\beta_{k}+\frac{2\sqrt{\mu}}{\sqrt{\tau}}\beta_{k}\right)V(x_{k},y_{k})+8\beta_{k}\left(\frac{1}{\mu}+\frac{1}{\tau}\right)(\|\mathcal{E}_{k,x}\|_{2}^{2}+\|\mathcal{E}_{k,y}\|_{2}^{2})$
$\displaystyle+\beta_{k}(\sigma_{\tau}(y_{k})-p(\mu,x_{k},y_{k}))^{\top}(A+B^{\top})(\sigma_{\tau}(x_{k})-q(\mu,x_{k},y_{k}))+L_{v}L_{b}\beta_{k}^{2}.$

Since $L_{V}=2/\mu+2/\tau+1/\sqrt{\mu\tau}$ and $\mu=\tau/64$, we have from
the previous inequality that

$\displaystyle V(x_{k+1},y_{k+1})\leq\;$
$\displaystyle\left(1-\frac{\beta_{k}}{2}\right)V(x_{k},y_{k})+\frac{520\beta_{k}}{\tau}(\|\mathcal{E}_{k,x}\|_{2}^{2}+\|\mathcal{E}_{k,y}\|_{2}^{2})$
$\displaystyle+\beta_{k}(\sigma_{\tau}(y_{k})-p(\mu,x_{k},y_{k}))^{\top}(A+B^{\top})(\sigma_{\tau}(x_{k})-q(\mu,x_{k},y_{k}))+\frac{138L_{b}\beta_{k}^{2}}{\tau}$
$\displaystyle\leq\;$
$\displaystyle\left(1-\frac{\beta_{k}}{2}\right)V(x_{k},y_{k})+\frac{520\beta_{k}}{\tau}(\|\mathcal{E}_{k,x}\|_{2}^{2}+\|\mathcal{E}_{k,y}\|_{2}^{2})$
$\displaystyle+4\beta_{k}\max_{i,j}|A(i,j)+B(j,i)|+\frac{138L_{b}\beta_{k}^{2}}{\tau}$

∎

We next apply Proposition A.1 to establish a negative drift inequality of the
slow-timescale iterate $\theta_{k}^{i}$.

######  Lemma A.6.

It holds for all $k\geq 0$ that

$\displaystyle\mathcal{L}_{\theta}(k+1)\leq\left(1-\frac{\beta_{k}}{2}\right)\mathcal{L}_{\theta}(k)+\frac{520A_{\max}\beta_{k}}{\tau}\mathcal{L}_{w}(k)+4\beta_{k}\|v^{1}+v^{2}\|_{\infty}+\frac{276A_{\max}^{1/2}\beta_{k}^{2}}{\tau\lambda^{1/2}(1-\gamma)}.$
(36)

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

To apply Proposition A.1 to the policy update equation in Algorithm 4 Line $3$
(or equivalently Eq. (31)), we first identify the constant $L_{b}$. Observe
that

$\displaystyle\|q_{k}^{i}(s)-\tilde{q}_{k}^{i}(s)\|_{2}=\;$
$\displaystyle\left[\sum_{a^{i}}(\phi^{i}(s,a^{i})^{\top}(w_{k}^{i}-\theta_{k}^{i}))^{2}\right]^{1/2}$
$\displaystyle\leq\;$
$\displaystyle\left[\sum_{a^{i}}\|\phi^{i}(s,a^{i}\|_{2}^{2}\|w_{k}^{i}-\theta_{k}^{i}\|_{2}^{2}\right]^{1/2}$
$\displaystyle\leq\;$
$\displaystyle\left[\sum_{a^{i}}(\|w_{k}^{i}\|_{2}+\|\theta_{k}^{i}\|_{2})^{2}\right]^{1/2}$
($\|\phi^{i}(s,a^{i})\|_{2}\leq 1$ for all $(s,a^{i})$) $\displaystyle\leq\;$
$\displaystyle 2A_{\max}^{1/2}M$ $\displaystyle=\;$
$\displaystyle\frac{2A_{\max}^{1/2}}{\lambda^{1/2}(1-\gamma)}.$

Therefore, we have for all $k\geq 0$ and $s\in\mathcal{S}$ that

$\displaystyle V_{v,s}(\tilde{q}_{k+1}^{1}(s),\tilde{q}_{k+1}^{2}(s))\leq\;$
$\displaystyle\left(1-\frac{\beta_{k}}{2}\right)V_{v,s}(\tilde{q}_{k}^{1}(s),\tilde{q}_{k}^{2}(s))+\frac{520\beta_{k}}{\tau}\sum_{i=1,2}\|q_{k}^{i}(s)-\mathcal{T}^{i}(v^{i})(s)\pi_{k}^{-i}(s)\|_{2}^{2}$
$\displaystyle+4\beta_{k}\max_{a^{1},a^{2}}\left|\mathcal{T}^{1}(v^{1})(s,a^{1},a^{2})+[\mathcal{T}^{2}(v^{2})(s,a^{2},a^{1})]^{\top}\right|+\frac{276A_{\max}^{1/2}\beta_{k}^{2}}{\tau\lambda^{1/2}(1-\gamma)}$
$\displaystyle\leq\;$
$\displaystyle\left(1-\frac{\beta_{k}}{2}\right)V_{v,s}(\tilde{q}_{k}^{1}(s),\tilde{q}_{k}^{2}(s))+\frac{520A_{\max}\beta_{k}}{\tau}\sum_{i=1,2}\|w_{k}^{i}-\bar{w}_{k}^{i}\|_{2}^{2}$
$\displaystyle+4\beta_{k}\|v^{1}+v^{2}\|_{\infty}+\frac{276A_{\max}^{1/2}\beta_{k}^{2}}{\tau\lambda^{1/2}(1-\gamma)},$

where the last line follows from

$\displaystyle\sum_{i=1,2}\|q_{k}^{i}(s)-\mathcal{T}^{i}(v^{i})(s)\pi_{k}^{-i}(s)\|_{2}^{2}=\;$
$\displaystyle\sum_{i=1,2}\|q_{k}^{i}(s)-\bar{q}_{k}^{i}(s)\|_{2}^{2}$
$\displaystyle=\;$
$\displaystyle\sum_{i=1,2}\sum_{a^{i}}(\phi^{i}(s,a^{i})^{\top}(w_{k}^{i}-\bar{w}_{k}^{i}))^{2}$
$\displaystyle\leq\;$
$\displaystyle\sum_{i=1,2}\sum_{a^{i}}\|\phi^{i}(s,a^{i})\|_{2}^{2}\|w_{k}^{i}-\bar{w}_{k}^{i}\|_{2}^{2}$
$\displaystyle\leq\;$ $\displaystyle
A_{\max}\sum_{i=1,2}\|w_{k}^{i}-\bar{w}_{k}^{i}\|_{2}^{2}.$
($\|\phi^{i}(s,a^{i})\|_{2}\leq 1$ for all $(s,a^{i})$)

As a result, we have

$\displaystyle\mathcal{L}_{\theta}(k+1)\leq\;$
$\displaystyle\left(1-\frac{\beta_{k}}{2}\right)\mathcal{L}_{\theta}(k)+\frac{520A_{\max}\beta_{k}}{\tau}\mathcal{L}_{w}(k)+4\beta_{k}\|v^{1}+v^{2}\|_{\infty}+\frac{276A_{\max}^{1/2}\beta_{k}^{2}}{\tau\lambda^{1/2}(1-\gamma)}.$

∎

#### A.4.2 Properties of the Lyapunov function $V(x,y)$

######  Lemma A.7.

For any $x\in\mathbb{R}^{n}$ and $y\in\mathbb{R}^{m}$, we have

$\displaystyle\nabla_{x}V_{1}(x,y)=\;$
$\displaystyle\frac{1}{\mu}(x-Bp(\mu,x,y)),$
$\displaystyle\quad\nabla_{y}V_{1}(x,y)=\;$
$\displaystyle\sigma_{\tau}(y)-p(\mu,x,y),$
$\displaystyle\nabla_{x}V_{2}(x,y)=\;$
$\displaystyle\sigma_{\tau}(x)-q(\mu,x,y),$
$\displaystyle\quad\nabla_{y}V_{2}(x,y)=\;$
$\displaystyle\frac{1}{\mu}(y-Aq(\mu,x,y)).$

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

We will only show the computation of $\nabla_{x}V_{1}(x,y)$. The computation
of all other gradients follows from an identical approach. We begin by writing
$V_{1}(\cdot,\cdot)$ in the following:

$\displaystyle
V_{1}(x,y)=\max_{u^{\prime}\in\Delta^{n}}\left\\{u^{\prime\top}y+\tau\nu(u^{\prime})\right\\}+\min_{u\in\Delta^{n}}\left\\{-u^{\top}y-\tau\nu(u)+\frac{1}{2\mu}\|x-Bu\|_{2}^{2}\right\\}.$
(37)

We next compute the gradient of each term on the RHS of the previous
inequality. The first term on the RHS of Eq. (37) is not a function of $x$.
For the second term, observe that

$\displaystyle\min_{u\in\Delta^{n}}\left\\{-u^{\top}y-\tau\nu(u)+\frac{1}{2\mu}\|x-Bu\|_{2}^{2}\right\\}=\;$
$\displaystyle-\max_{u\in\Delta^{n}}\left\\{u^{\top}y+\tau\nu(u)-\frac{1}{2\mu}\|x-Bu\|_{2}^{2}\right\\}$
$\displaystyle=\;$
$\displaystyle-\max_{u\in\Delta^{n}}\underbrace{\left\\{u^{\top}y+\tau\nu(u)-\frac{1}{2\mu}\|Bu\|_{2}^{2}+\frac{1}{\mu}x^{\top}Bu\right\\}}_{:=G(\mu,x,y,u)}$
$\displaystyle+\frac{1}{2\mu}\|x\|_{2}^{2}.$

Since $G(\mu,x,y,u)$ as a function of $x$ is linear, hence convex, we have by
Danskin’s theorem that

$\displaystyle\nabla_{x}\max_{u\in\Delta^{n}}G(\mu,x,y,u)=\frac{1}{\mu}Bp(\mu,x,y).$

where we recall that $p(\mu,x,y)={\arg\max}_{u\in\Delta^{n}}G(\mu,x,y,u)$. It
follows that

$\displaystyle\nabla_{x}V_{1}(x,y)=-\nabla_{x}\max_{u\in\Delta^{n}}G(\mu,x,y,u)+\frac{1}{\mu}x=\frac{1}{\mu}(x-Bp(\mu,x,y)).$

∎

######  Lemma A.8.

The Lyapunov function $V(x,y)$ is $L_{V}$ – smooth, where
$L_{V}=2/\mu+2/\tau+1/\sqrt{\mu\tau}$.

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

For any $x_{1},x_{2}\in\mathbb{R}^{n}$ and $y_{1},y_{2}\in\mathbb{R}^{m}$, we
have by Lemma A.7 that

$\displaystyle\nabla_{x}V(x_{1},y_{1})-\nabla_{x}V(x_{2},y_{2})=\;$
$\displaystyle\frac{1}{\mu}(x_{1}-Bp(\mu,x_{1},y_{1}))+\sigma_{\tau}(x_{1})-q(\mu,x_{1},y_{1})$
$\displaystyle-\frac{1}{\mu}(x_{2}-Bp(\mu,x_{2},y_{2}))-\sigma_{\tau}(x_{2})+q(\mu,x_{2},y_{2})$
$\displaystyle=\;$
$\displaystyle\frac{1}{\mu}(x_{1}-x_{2})+\frac{1}{\mu}B(p(\mu,x_{2},y_{2})-p(\mu,x_{1},y_{1}))$
$\displaystyle+\sigma_{\tau}(x_{1})-\sigma_{\tau}(x_{2})+q(\mu,x_{2},y_{2})-q(\mu,x_{1},y_{1})$
$\displaystyle=\;$
$\displaystyle\frac{1}{\mu}(x_{1}-x_{2})+\frac{1}{\mu}B(p(\mu,x_{2},y_{2})-p(\mu,x_{1},y_{2}))$
$\displaystyle+\frac{1}{\mu}B(p(\mu,x_{1},y_{2})-p(\mu,x_{1},y_{1}))$
$\displaystyle+\sigma_{\tau}(x_{1})-\sigma_{\tau}(x_{2})+q(\mu,x_{2},y_{2})-q(\mu,x_{1},y_{2})$
$\displaystyle+q(\mu,x_{1},y_{2})-q(\mu,x_{1},y_{1}).$

Taking $\|\cdot\|_{2}$ on both sides of the previous inequality and then using
triangle inequality, we have

$\displaystyle\|\nabla_{x}V(x_{1},y_{1})-\nabla_{x}V(x_{2},y_{2})\|_{2}\leq\;$
$\displaystyle\frac{1}{\mu}\|x_{1}-x_{2}\|_{2}+\frac{1}{\mu}\|B(p(\mu,x_{2},y_{2})-p(\mu,x_{1},y_{2}))\|_{2}$
$\displaystyle+\frac{1}{\mu}\|B(p(\mu,x_{1},y_{2})-p(\mu,x_{1},y_{1}))\|_{2}$
$\displaystyle+\|\sigma_{\tau}(x_{1})-\sigma_{\tau}(x_{2})\|_{2}+\|q(\mu,x_{2},y_{2})-q(\mu,x_{1},y_{2})\|_{2}$
$\displaystyle+\|q(\mu,x_{1},y_{2})-q(\mu,x_{1},y_{1})\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\frac{1}{\mu}\|x_{1}-x_{2}\|_{2}+\frac{1}{\mu}\|x_{1}-x_{2}\|_{2}+\frac{1}{2\sqrt{\mu\tau}}\|y_{1}-y_{2}\|_{2}$
$\displaystyle+\frac{1}{\tau}\|x_{1}-x_{2}\|_{2}+\frac{1}{\tau}\|x_{1}-x_{2}\|_{2}$
$\displaystyle+\frac{1}{2\sqrt{\mu\tau}}\|y_{1}-y_{2}\|_{2}$ (Lemmas A.10 and
A.11) $\displaystyle=\;$
$\displaystyle\left(\frac{2}{\mu}+\frac{2}{\tau}\right)\|x_{1}-x_{2}\|_{2}+\frac{1}{\sqrt{\tau\mu}}\|y_{1}-y_{2}\|_{2}.$

Similarly, we also have

$\displaystyle\|\nabla_{y}V(x_{1},y_{1})-\nabla_{y}V(x_{2},y_{2})\|_{2}\leq\;$
$\displaystyle\left(\frac{2}{\mu}+\frac{2}{\tau}\right)\|y_{1}-y_{2}\|_{2}+\frac{1}{\sqrt{\tau\mu}}\|x_{1}-x_{2}\|_{2}.$

It follows that

$\displaystyle\left\|\nabla V(x_{1},y_{1})-\nabla
V(x_{2},y_{2})\right\|_{2}^{2}$ $\displaystyle=\;$
$\displaystyle\|\nabla_{x}V(x_{1},y_{1})-\nabla_{x}V(x_{2},y_{2})\|_{2}^{2}+\|\nabla_{y}V(x_{1},y_{1})-\nabla_{y}V(x_{2},y_{2})\|_{2}^{2}$
$\displaystyle\leq\;$
$\displaystyle\left[\left(\frac{2}{\mu}+\frac{2}{\tau}\right)\|y_{1}-y_{2}\|_{2}+\frac{1}{\sqrt{\tau\mu}}\|x_{1}-x_{2}\|_{2}\right]^{2}+\left[\left(\frac{2}{\mu}+\frac{2}{\tau}\right)\|x_{1}-x_{2}\|_{2}+\frac{1}{\sqrt{\tau\mu}}\|y_{1}-y_{2}\|_{2}\right]^{2}$
$\displaystyle\leq\;$
$\displaystyle\left(\frac{2}{\mu}+\frac{2}{\tau}+\frac{1}{\sqrt{\tau\mu}}\right)^{2}(\|x_{1}-x_{2}\|_{2}^{2}+\|y_{1}-y_{2}\|_{2}^{2}).$

which implies

$\displaystyle\left\|\nabla V(x_{1},y_{1})-\nabla
V(x_{2},y_{2})\right\|_{2}\leq\left(\frac{2}{\mu}+\frac{2}{\tau}+\frac{1}{\sqrt{\tau\mu}}\right)(\|x_{1}-x_{2}\|_{2}^{2}+\|y_{1}-y_{2}\|_{2}^{2})^{1/2}.$

As a result, the Lyapunov function $V(\cdot,\cdot)$ is $L_{V}$ – smooth, where
$L_{V}=2/\mu+2/\tau+1/\sqrt{\mu\tau}$. ∎

######  Lemma A.9.

For any $x\in\mathbb{R}^{n}$ and $y\in\mathbb{R}^{m}$, we have

$\displaystyle y+\tau\nabla\nu(\sigma_{\tau}(y))=0,\quad\text{and}\quad
y+\tau\nabla\nu(p(\mu,x,y))=\frac{1}{\mu}B^{\top}(Bp(\mu,x,y)-x).$

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

Since
$\sigma_{\tau}(y)={\arg\max}_{u\in\Delta^{m}}\\{u^{\top}y+\tau\nu(u)\\}$, the
first claimed inequality follows from the first order optimality condition.
The second inequality follows from an identical approach. ∎

######  Lemma A.10.

The following two inequalities hold for all $x_{1},x_{2}\in\mathbb{R}^{n}$,
and $y\in\mathbb{R}^{m}$:

$\displaystyle\|B(p(\mu,x_{2},y)-p(\mu,x_{1},y))\|_{2}\leq\;$
$\displaystyle\|x_{2}-x_{1}\|_{2}$
$\displaystyle\|p(\mu,x_{2},y)-p(\mu,x_{1},y)\|_{2}\leq\;$
$\displaystyle\frac{1}{2\sqrt{\mu\tau}}\|x_{2}-x_{1}\|_{2}.$

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

For any $x_{1},x_{2}\in\mathbb{R}^{n}$, and $y\in\mathbb{R}^{m}$, we have by
Lemma A.9 that

$\displaystyle-y-\tau\nabla\nu(p(\mu,x_{1},y))+\frac{1}{\mu}B^{\top}(Bp(\mu,x_{1},y)-x_{1})=\;$
$\displaystyle 0,$
$\displaystyle-y-\tau\nabla\nu(p(\mu,x_{2},y))+\frac{1}{\mu}B^{\top}(Bp(\mu,x_{2},y)-x_{2})=\;$
$\displaystyle 0.$

It follows that

$\displaystyle
B^{\top}(x_{2}-x_{1})=B^{\top}B(p(\mu,x_{2},y)-p(\mu,x_{1},y))+\mu\tau(\nabla\nu(p(\mu,x_{1},y))-\nabla\nu(p(\mu,x_{2},y))),$

which implies

$\displaystyle\|B(p(\mu,x_{2},y)-p(\mu,x_{1},y))\|_{2}\|x_{2}-x_{1}\|_{2}$
$\displaystyle\geq\;$
$\displaystyle(p(\mu,x_{2},y)-p(\mu,x_{1},y))^{\top}B^{\top}(x_{2}-x_{1})$
(Cauchy–Schwarz inequality) $\displaystyle=\;$
$\displaystyle\|B(p(\mu,x_{2},y)-p(\mu,x_{1},y)\|_{2}^{2}+\mu\tau(p(\mu,x_{2},y)-p(\mu,x_{1},y))^{\top}(\nabla\nu(p(\mu,x_{1},y))-\nabla\nu(p(\mu,x_{2},y)))$
(The previous inequality) $\displaystyle\geq\;$
$\displaystyle\|B(p(\mu,x_{2},y)-p(\mu,x_{1},y))\|_{2}^{2}+\mu\tau\|p(\mu,x_{2},y)-p(\mu,x_{1},y)\|_{2}^{2},$

where the last line follows from $-\nu(\cdot)$ being a $1$ – strongly convex
function with respect to $\|\cdot\|_{2}$ [8, Example 5.27]. As a result, we
have from the previous inequality that

$\displaystyle\|B(p(\mu,x_{2},y)-p(\mu,x_{1},y))\|_{2}\leq\|x_{2}-x_{1}\|_{2}$

and

$\displaystyle\|p(\mu,x_{2},y)-p(\mu,x_{1},y)\|_{2}\leq\frac{1}{2\sqrt{\mu\tau}}\|x_{2}-x_{1}\|_{2}.$

∎

######  Lemma A.11.

The following two inequalities hold for all $x\in\mathbb{R}^{n}$ and
$y_{1},y_{2}\in\mathbb{R}^{m}$:

$\displaystyle\|p(\mu,x,y_{2})-p(\mu,x,y_{1})\|_{2}\leq\;$
$\displaystyle\frac{1}{\tau}\|y_{2}-y_{1}\|_{2},$
$\displaystyle\|B(p(\mu,x,y_{2})-p(\mu,x,y_{1}))\|_{2}\leq\;$
$\displaystyle\frac{\sqrt{\mu}}{2\sqrt{\tau}}\|y_{2}-y_{1}\|_{2}.$

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

For any $x\in\mathbb{R}^{n}$ and $y_{1},y_{2}\in\mathbb{R}^{m}$, we have by
Lemma A.9 that

$\displaystyle-
y_{1}-\tau\nabla\nu(p(\mu,x,y_{1}))+\frac{1}{\mu}B^{\top}(Bp(\mu,x,y_{1})-x)=\;$
$\displaystyle 0$ $\displaystyle-
y_{2}-\tau\nabla\nu(p(\mu,x,y_{2}))+\frac{1}{\mu}B^{\top}(Bp(\mu,x,y_{2})-x)=\;$
$\displaystyle 0.$

It follows that

$\displaystyle
y_{2}-y_{1}=\tau\nabla\nu(p(\mu,x,y_{1}))-\tau\nabla\nu(p(\mu,x,y_{2}))+\frac{1}{\mu}B^{\top}B(p(\mu,x,y_{2})-p(\mu,x,y_{1})),$

which implies

$\displaystyle\|p(\mu,x,y_{2})-p(\mu,x,y_{1})\|_{2}\|y_{2}-y_{1}\|_{2}$
$\displaystyle\geq\;$
$\displaystyle(p(\mu,x,y_{2})-p(\mu,x,y_{1}))^{\top}(y_{2}-y_{1})$
(Cauchy–Schwarz inequality) $\displaystyle=\;$
$\displaystyle\tau(p(\mu,x,y_{2})-p(\mu,x,y_{1}))^{\top}(\nabla\nu(p(\mu,x,y_{1}))-\nabla\nu(p(\mu,x,y_{2})))$
(The previous inequality)
$\displaystyle+\frac{1}{\mu}\|B(p(\mu,x,y_{2})-p(\mu,x,y_{1}))\|_{2}^{2}$
$\displaystyle\geq\;$
$\displaystyle\tau\|p(\mu,x,y_{2})-p(\mu,x,y_{1})\|_{2}^{2}+\frac{1}{\mu}\|B(p(\mu,x,y_{2})-p(\mu,x,y_{1}))\|_{2}^{2},$

where the last line follows from the $1$ – strong convexity of $-\nu(\cdot)$.
The previous inequality implies

$\displaystyle\|p(\mu,x,y_{2})-p(\mu,x,y_{1})\|_{2}\leq\frac{1}{\tau}\|y_{2}-y_{1}\|_{2},$

and

$\displaystyle\|B(p(\mu,x,y_{2})-p(\mu,x,y_{1}))\|_{2}\leq\frac{\sqrt{\mu}}{2\sqrt{\tau}}\|y_{2}-y_{1}\|_{2}.$

∎

######  Lemma A.12.

The following $2$ inequalities hold for any $x\in\mathbb{R}^{n}$ and
$y\in\mathbb{R}^{m}$:

$\displaystyle\|\sigma_{\tau}(y)-p(\mu,x,y)\|_{2}\leq\;$
$\displaystyle\frac{\sqrt{2}}{\sqrt{\tau}}V_{1}(x,y)^{1/2},$
$\displaystyle\|Bp(\mu,x,y)-x\|_{2}\leq\;$
$\displaystyle\sqrt{2\mu}V_{1}(x,y)^{1/2}.$

In addition, suppose that $\mu\leq\|B\|_{2}^{2}/\tau$. Then we have

$\displaystyle\|B\sigma_{\tau}(y)-x\|_{2}\leq\frac{2\sqrt{2}\|B\|_{2}}{\sqrt{\tau}}V_{1}(x,y)^{1/2}.$

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

For any $x\in\mathbb{R}^{n}$ and $y\in\mathbb{R}^{m}$, since
$-u^{\top}y-\tau\nu(u)$ as a function $u$ is $\tau$ – strongly convex with
respect to $\|\cdot\|_{2}$, we have by the quadratic growth property of
strongly convex functions that

$\displaystyle\|\sigma_{\tau}(y)-p(\mu,x,y)\|_{2}^{2}$ $\displaystyle\leq\;$
$\displaystyle\frac{2}{\tau}\left[\sigma_{\tau}(y)^{\top}y+\tau\nu(\sigma_{\tau}(y))-p(\mu,x,y)^{\top}y-\tau\nu(p(\mu,x,y))\right]$
$\displaystyle\leq\;$
$\displaystyle\frac{2}{\tau}\left[\sigma_{\tau}(y)^{\top}y+\tau\nu(\sigma_{\tau}(y))-p(\mu,x,y)^{\top}y-\tau\nu(p(\mu,x,y))+\frac{1}{2\mu}\|x-Bp(\mu,x,y)\|_{2}^{2}\right]$
$\displaystyle=\;$
$\displaystyle\frac{2}{\tau}\left[\max_{u^{\prime}\in\Delta^{m}}\left\\{u^{\prime\top}y+\tau\nu(u^{\prime})\right\\}+\min_{u\in\Delta^{m}}\left\\{-u^{\top}y-\tau\nu(u)+\frac{1}{2\mu}\|x-Bu\|_{2}^{2}\right\\}\right]$
$\displaystyle=\;$ $\displaystyle\frac{2}{\tau}V_{1}(x,y).$

Taking square root on both sides of the previous inequality, we obtain

$\displaystyle\|\sigma_{\tau}(y)-p(\mu,x,y)\|_{2}\leq\frac{\sqrt{2}}{\sqrt{\tau}}V_{1}(x,y)^{1/2}.$

Next, we prove the second claimed inequality. For any $x\in\mathbb{R}^{n}$ and
$y\in\mathbb{R}^{m}$, we have

$\displaystyle\|Bp(\mu,x,y)-x\|_{2}^{2}=2\mu\frac{1}{2\mu}\|Bp(\mu,x,y)-x\|_{2}^{2}\leq
2\mu V_{1}(x,y),$

which implies

$\displaystyle\|Bp(\mu,x,y)-x\|_{2}\leq\sqrt{2\mu}V_{1}(x,y)^{1/2}.$

Finally, we prove the last claimed inequality. For any $x\in\mathbb{R}^{n}$
and $y\in\mathbb{R}^{m}$, we have

$\displaystyle\|B\sigma_{\tau}(y)-x\|_{2}\leq\;$
$\displaystyle\|B\|_{2}\|\sigma_{\tau}(y)-p(\mu,x,y)\|_{2}+\|Bp(\mu,x,y)-x\|_{2}$
(Triangle inequality) $\displaystyle\leq\;$
$\displaystyle\frac{\sqrt{2}\|B\|_{2}}{\sqrt{\tau}}V_{1}(x,y)^{1/2}+\sqrt{2\mu}V_{1}(x,y)^{1/2}$
(The previous two inequalities in this lemma) $\displaystyle\leq\;$
$\displaystyle\frac{2\sqrt{2}\|B\|_{2}}{\sqrt{\tau}}V_{1}(x,y)^{1/2},$

where the last line follows from $\mu\leq\|B\|_{2}^{2}/\tau$. ∎

#### A.4.3 Analysis of the Fast-Timescale Iterates

Fixing $v^{i}\in\mathbb{R}^{|\mathcal{S}|}$, let
$F^{i}:\mathbb{R}^{d_{i}}\times\mathcal{S}\times\mathcal{A}^{i}\times\mathcal{A}^{-i}\times\mathcal{S}\mapsto\mathbb{R}^{d_{i}}$
be an operator defined as

$\displaystyle
F^{i}(w^{i},s,a^{i},a^{-i},s^{\prime})=\phi^{i}(s,a^{i})(R_{i}(s,a^{i},a^{-i})+\gamma
v^{i}(s^{\prime})-\phi^{i}(s,a^{i})^{\top}w^{i})$

for all $(s,a^{i},a^{-i},s^{\prime})$ and $w\in\mathbb{R}^{d_{i}}$. Then,
Algorithm 4 Line $5$ can be equivalently written as

$\displaystyle
w_{k+1}^{i}=\text{Proj}_{M}^{i}\left[w_{k}^{i}+\alpha_{k}F^{i}(w_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\right].$
(38)

For any $k\geq 0$, define
$\bar{F}_{k}^{i}:\mathbb{R}^{d_{i}}\mapsto\mathbb{R}^{d_{i}}$ as

$\displaystyle\bar{F}_{k}^{i}(w^{i})=\mathbb{E}_{S\sim\mu_{k}(\cdot),A^{i}\sim\pi_{k}^{i}(\cdot\mid
S),A^{-i}\sim\pi_{k}^{-i}(\cdot\mid S),S^{\prime}\sim p(\cdot\mid
S,A^{i},A^{-i})}[F^{i}(w^{i},S,A^{i},A^{-i},S^{\prime})]$

for all $w^{i}\in\mathbb{R}^{d_{i}}$, where $\mu_{k}\in\Delta(\mathcal{S})$ is
the stationary distribution of the Markov chain $\\{S_{k}\\}$ induced by the
joint policy $\pi_{k}=(\pi_{k}^{1},\pi_{k}^{2})$. Note that $\mu_{k}$ is
guaranteed to exist and is unique under Assumption 4.1. Eq. (38) can then be
viewed as a stochastic approximation algorithm for solving the time-varying
equation $\bar{F}_{k}^{i}(w^{i})=0$. The properties of the operators
$F^{i}(\cdot)$ and $\bar{F}_{k}^{i}(\cdot)$ are established in Lemma A.15.

Using the equivalent formulation of the update equation (38), we have for all
$k\geq 0$ that

$\displaystyle\mathbb{E}[\|w_{k+1}^{i}-\bar{w}_{k+1}^{i}\|_{2}^{2}]$
$\displaystyle=\;$
$\displaystyle\mathbb{E}[\|\text{Proj}_{M}^{i}[w_{k}^{i}+\alpha_{k}F^{i}(w_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})]-\text{Proj}_{M}^{i}(\bar{w}_{k+1}^{i})\|_{2}^{2}]$
$\displaystyle\leq\;$
$\displaystyle\mathbb{E}[\|w_{k}^{i}+\alpha_{k}F^{i}(w_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-\bar{w}_{k+1}^{i}\|_{2}^{2}]$
$\displaystyle=\;$
$\displaystyle\mathbb{E}[\|\alpha_{k}F^{i}(w_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})+w_{k}^{i}-\bar{w}_{k}^{i}+\bar{w}_{k}^{i}-\bar{w}_{k+1}^{i}\|_{2}^{2}]$
$\displaystyle=\;$
$\displaystyle\mathbb{E}[\|w_{k}^{i}-\bar{w}_{k}^{i}\|_{2}^{2}]+\alpha_{k}^{2}\mathbb{E}[\|F^{i}(w_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\|_{2}^{2}]+\mathbb{E}[\|\bar{w}_{k}^{i}-\bar{w}_{k+1}^{i}\|_{2}^{2}]$
$\displaystyle+2\alpha_{k}\mathbb{E}[(w_{k}^{i}-\bar{w}_{k}^{i})^{\top}(\bar{F}_{k}^{i}(w_{k}^{i}))]$
$\displaystyle+2\alpha_{k}\mathbb{E}[(w_{k}^{i}-\bar{w}_{k}^{i})^{\top}(F^{i}(w_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-\bar{F}_{k}^{i}(w_{k}^{i}))]$
$\displaystyle+2\alpha_{k}\mathbb{E}[(\bar{w}_{k}^{i}-\bar{w}_{k+1}^{i})^{\top}F^{i}(w_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})]$
$\displaystyle+2\mathbb{E}[(w_{k}^{i}-\bar{w}_{k}^{i})^{\top}(\bar{w}_{k}^{i}-\bar{w}_{k+1}^{i})]$
$\displaystyle\leq\;$
$\displaystyle(1-2\lambda\alpha_{k})\mathbb{E}[\|w_{k}^{i}-\bar{w}_{k}^{i}\|_{2}^{2}]+\alpha_{k}^{2}\mathbb{E}[\|F^{i}(w_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\|_{2}^{2}]+\mathbb{E}[\|\bar{w}_{k}^{i}-\bar{w}_{k+1}^{i}\|_{2}^{2}]$
$\displaystyle+2\alpha_{k}\mathbb{E}[(w_{k}^{i}-\bar{w}_{k}^{i})^{\top}(F^{i}(w_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-\bar{F}_{k}^{i}(w_{k}^{i}))]$
$\displaystyle+\mathbb{E}[\|\bar{w}_{k}^{i}-\bar{w}_{k+1}^{i}\|_{2}^{2}]+\alpha_{k}^{2}\mathbb{E}[\|F^{i}(w_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1}\|_{2}^{2}]$
$\displaystyle+\frac{\lambda\alpha_{k}}{2}\mathbb{E}[\|w_{k}^{i}-\bar{w}_{k}^{i}\|_{2}^{2}]+\frac{2}{\lambda\alpha_{k}}\mathbb{E}[\|\bar{w}_{k}^{i}-\bar{w}_{k+1}^{i}\|_{2}^{2}]$
$\displaystyle\leq\;$
$\displaystyle\left(1-\frac{3\lambda\alpha_{k}}{2}\right)\mathbb{E}[\|w_{k}^{i}-\bar{w}_{k}^{i}\|_{2}^{2}]+2\alpha_{k}^{2}\underbrace{\mathbb{E}[\|F^{i}(w_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\|_{2}^{2}]}_{E_{w,1}}+\frac{4}{\lambda\alpha_{k}}\underbrace{\mathbb{E}[\|\bar{w}_{k}^{i}-\bar{w}_{k+1}^{i}\|_{2}^{2}]}_{E_{w,2}}$
$\displaystyle+2\alpha_{k}\underbrace{\mathbb{E}[(w_{k}^{i}-\bar{w}_{k}^{i})^{\top}(F^{i}(w_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-\bar{F}_{k}^{i}(w_{k}^{i}))]}_{E_{w,3}},$
(39)

where the second last inequality follows from Lemma A.15 (2), Cauchy–Schwarz
inequality, and $a^{2}+b^{2}\geq 2\sqrt{ab}$, and the last inequality follows
from $\alpha_{0}\leq 1/\lambda$. Next, we bound the terms $E_{w,1}$ to
$E_{w,3}$ on the RHS of the previous inequality.

Consider the term $E_{w,1}$. Using Lemma A.15 (1) and (2), we have

$\displaystyle E_{w,1}=\;$
$\displaystyle\mathbb{E}[\|F^{i}(w_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\|_{2}^{2}]$
$\displaystyle=\;$
$\displaystyle\mathbb{E}[\|F^{i}(w_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-F^{i}(0,S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})+F^{i}(0,S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\|_{2}^{2}]$
$\displaystyle\leq\;$
$\displaystyle\mathbb{E}[(\|w_{k}^{i}\|_{2}+1/(1-\gamma))^{2}]$
$\displaystyle\leq\;$
$\displaystyle\left(\frac{1}{\lambda^{1/2}(1-\gamma)}+\frac{1}{1-\gamma}\right)^{2}$
($\|w_{k}^{i}\|_{2}\leq M=\frac{1}{\lambda^{1/2}(1-\gamma)}$)
$\displaystyle\leq\;$ $\displaystyle\frac{4}{\lambda(1-\gamma)^{2}},$

where the last line follows from

$\displaystyle\lambda^{2}\leq\;$
$\displaystyle\max_{i\in\\{1,2\\}}\max_{w^{i}\in\mathbb{R}^{d_{i}},\|w^{i}\|_{2}=1}\|\Phi^{i}w^{i}\|_{\infty}$
$\displaystyle=\;$
$\displaystyle\max_{i\in\\{1,2\\}}\max_{w^{i}\in\mathbb{R}^{d_{i}},\|w^{i}\|_{2}=1}\max_{s,a^{i}}|\phi^{i}(s,a^{i})^{\top}w^{i}|$
$\displaystyle\leq\;$
$\displaystyle\max_{i\in\\{1,2\\}}\max_{s,a^{i}}\|\phi^{i}(s,a^{i})\|_{2}$
$\displaystyle\leq\;$ $\displaystyle 1.$

Next, we consider the term $E_{w,2}$. Using Lemma A.15 (4), we have

$\displaystyle
E_{w,2}\leq\frac{4A_{\max}^{2}\beta_{k}^{2}}{\tau^{2}\lambda^{2}(1-\gamma)^{4}}.$

Finally, we bound the term $E_{w,3}$ in the following lemma.

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

Under Condition 4.1, we have for all $k\geq z_{k}$ that

$\displaystyle
E_{w,3}\leq\frac{17z_{k}\alpha_{k-z_{k},k-1}}{\tau\lambda^{3/2}(1-\gamma)^{3}}.$

Using the upper bounds we obtained for the terms $E_{w,1}$ to $E_{w,3}$ in Eq.
(39), we have for all $k\geq z_{k}$ that

$\displaystyle\mathbb{E}[\|w_{k+1}^{i}-\bar{w}_{k+1}^{i}\|_{2}^{2}]\leq\;$
$\displaystyle\left(1-\frac{3\lambda\alpha_{k}}{2}\right)\mathbb{E}[\|w_{k}^{i}-\bar{w}_{k}^{i}\|_{2}^{2}]+\frac{8\alpha_{k}^{2}}{\lambda(1-\gamma)^{2}}+\frac{16A_{\max}^{2}\beta_{k}^{2}}{\tau^{2}\lambda^{3}(1-\gamma)^{4}\alpha_{k}}$
$\displaystyle+\frac{34z_{k}\alpha_{k}\alpha_{k-z_{k},k-1}}{\tau\lambda^{3/2}(1-\gamma)^{3}}$
$\displaystyle\leq\;$
$\displaystyle\left(1-\frac{3\lambda\alpha_{k}}{2}\right)\mathbb{E}[\|w_{k}^{i}-\bar{w}_{k}^{i}\|_{2}^{2}]+\frac{42z_{k}\alpha_{k}\alpha_{k-z_{k},k-1}}{\tau\lambda^{3/2}(1-\gamma)^{3}}+\frac{16A_{\max}^{2}\beta_{k}^{2}}{\tau^{2}\lambda^{3}(1-\gamma)^{4}\alpha_{k}},$

where the last inequality follows from $\lambda\leq 1$ and $\tau\leq
1/(1-\gamma)$. Summing up the previous inequality for $i\in\\{1,2\\}$, we have
the following lemma.

######  Lemma A.14.

It holds for all $k\geq z_{k}$ that

$\displaystyle\mathbb{E}[\mathcal{L}_{w}(k+1)]\leq\;$
$\displaystyle\left(1-\frac{3\lambda\alpha_{k}}{2}\right)\mathbb{E}[\mathcal{L}_{w}(k)]+\frac{84z_{k}\alpha_{k}\alpha_{k-z_{k},k-1}}{\tau\lambda^{3/2}(1-\gamma)^{3}}+\frac{32A_{\max}^{2}\beta_{k}^{2}}{\tau^{2}\lambda^{3}(1-\gamma)^{4}\alpha_{k}}.$

#### A.4.4 Supporting Lemmas

######  Lemma A.15.

The operators $F^{i}(\cdot)$ and $\bar{F}_{k}^{i}(\cdot)$ have the following
properties.

  1. (1)

It holds for any $w_{1}^{i},w_{2}^{i}\in\mathbb{R}^{d_{i}}$ and
$(s,a^{i},a^{-i},s^{\prime})$ that

$\displaystyle\|F^{i}(w_{1}^{i},s,a^{i},a^{-i},s^{\prime})-F^{i}(w_{2}^{i},s,a^{i},a^{-i},s^{\prime})\|_{2}\leq\;$
$\displaystyle\|w_{1}^{i}-w_{2}^{i}\|_{2},$
$\displaystyle\|F^{i}(0,s,a^{i},a^{-i},s^{\prime})\|_{2}\leq\;$
$\displaystyle\frac{1}{1-\gamma}.$

  2. (2)

It holds for any $k\geq 0$ that
$\langle\bar{F}_{k}(w_{1}^{i})-\bar{F}_{k}(w_{2}^{i}),w_{1}^{i}-w_{2}^{i}\rangle\leq-\lambda\|w_{1}^{i}-w_{2}^{i}\|_{2}^{2}$.

  3. (3)

It holds for any $k\geq 0$ that
$\|\bar{w}_{k}^{i}\|_{2}\leq\lambda^{-1/2}(1-\gamma)^{-1}$.

  4. (4)

It holds for all $k\geq 0$ that
$\|\bar{w}_{k+1}^{i}-\bar{w}_{k}^{i}\|_{2}\leq\frac{2A_{\max}\beta_{k}}{\tau\lambda(1-\gamma)^{2}}$.

###### Proof of Lemma A.15.

  1. (1)

For any $w_{1}^{i},w_{2}^{i}\in\mathbb{R}^{d_{i}}$ and
$(s,a^{i},a^{-i},s^{\prime})$, by definition of $F^{i}(\cdot)$, we have

$\displaystyle\|F^{i}(w_{1}^{i},s,a^{i},a^{-i},s^{\prime})-F^{i}(w_{2}^{i},s,a^{i},a^{-i},s^{\prime})\|_{2}=\;$
$\displaystyle\|\phi^{i}(s,a^{i})\phi^{i}(s,a^{i})^{\top}(w_{1}^{i}-w_{2}^{i})\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\|\phi^{i}(s,a^{i})\|_{2}^{2}\|w_{1}^{i}-w_{2}^{i}\|_{2}$
$\displaystyle\leq\;$ $\displaystyle\|w_{1}^{i}-w_{2}^{i}\|_{2},$

where the last line follows from $\max_{s,a^{i}}\|\phi^{i}(s,a^{i})\|_{2}\leq
1$. Similarly, for any $(s,a^{i},a^{-i},s^{\prime})$, we have

$\displaystyle\|F^{i}(0,s,a^{i},a^{-i},s^{\prime})\|_{2}=\;$
$\displaystyle|R_{i}(s,a^{i},a^{-i})+\gamma
v^{i}(s^{\prime})|\|\phi^{i}(s,a^{i})\|_{2}$ $\displaystyle\leq\;$
$\displaystyle 1+\frac{\gamma}{1-\gamma}$ $\displaystyle\leq\;$
$\displaystyle\frac{1}{1-\gamma}.$

  2. (2)

For simplicity of notation, for $i\in\\{1,2\\}$, let
$\mathcal{H}^{i}:\mathbb{R}^{|\mathcal{S}|}\times\mathbb{R}^{|\mathcal{S}||\mathcal{A}^{-i}|}\mapsto\mathbb{R}^{|\mathcal{S}||\mathcal{A}^{i}|}$
be an operator defined as

$\displaystyle[\mathcal{H}^{i}(v,\pi^{-i})](s,a^{i})=\mathbb{E}\left[R_{i}(s,a^{i},A_{0}^{-i})+\gamma
v(S_{1})\;\middle|\;S_{0}=s,A_{0}^{i}=a^{i},A_{0}^{-i}\sim\pi^{-i}(\cdot\mid
S_{0})\right]$ (40)

for all $v$, $\pi^{-i}$, and $(s,a^{i})$. Observe that the operator
$\bar{F}_{k}(\cdot)$ is explicitly given as

$\displaystyle\bar{F}_{k}(w^{i})=(\Phi^{i})^{\top}D_{k}^{i}(\mathcal{H}^{i}(v^{i},\pi_{k}^{-i})-\Phi^{i}w^{i}),$

where
$D_{k}^{i}=\text{diag}(\\{\mu_{k}(s)\pi_{k}^{i}(a^{i}|s)\\}_{(s,a^{i})\in\mathcal{S}\times\mathcal{A}^{i}})$.
Therefore, the equation $\bar{F}_{k}(w^{i})=0$ has a unique solution

$\displaystyle\bar{w}_{k}^{i}=[(\Phi^{i})^{\top}D_{k}^{i}\Phi^{i}]^{-1}(\Phi^{i})^{\top}D_{k}^{i}\mathcal{H}^{i}(v^{i},\pi_{k}^{-i}).$

In addition, for any $w_{1}^{i},w_{2}^{i}\in\mathbb{R}^{d_{i}}$, we have

$\displaystyle\langle\bar{F}_{k}(w_{1}^{i})-\bar{F}_{k}(w_{2}^{i}),w_{1}^{i}-w_{2}^{i}\rangle=\;$
$\displaystyle-(w_{1}^{i}-w_{2}^{i})^{\top}((\Phi^{i})^{\top}D_{k}^{i}\Phi^{i})(w_{1}^{i}-w_{2}^{i})$
$\displaystyle\leq\;$ $\displaystyle-\lambda\|w_{1}^{i}-w_{2}^{i}\|_{2}^{2},$

where we recall from Assumption 4.1 that
$\lambda=\min_{i\in\\{1,2\\}}\inf_{\pi\in\Pi}\lambda_{\min}((\Phi^{i})^{\top}D_{\pi}^{i}\Phi^{i})>0$.

  3. (3)

Observe that

$\displaystyle\|\Phi^{i}\bar{w}_{k}^{i}\|_{D_{k}^{i}}=\left[(\bar{w}_{k}^{i})^{\top}(\Phi^{i})^{\top}D_{k}^{i}\Phi^{i}\bar{w}_{k}^{i}\right]^{1/2}\geq\lambda^{1/2}\|\bar{w}_{k}^{i}\|_{2}.$
(41)

Moreover, using the explicit expression of $\bar{w}_{k}^{i}$ from Part (2) of
this lemma, we have

$\displaystyle\|\Phi^{i}\bar{w}_{k}^{i}\|_{D_{k}^{i}}=\;$
$\displaystyle\|\Phi^{i}[(\Phi^{i})^{\top}D_{k}^{i}\Phi^{i}]^{-1}(\Phi^{i})^{\top}D_{k}^{i}\mathcal{H}^{i}(v^{i},\pi_{k}^{-i})\|_{D_{k}^{i}}$
$\displaystyle=\;$
$\displaystyle\|\text{Proj}_{k}^{i}\mathcal{H}^{i}(v^{i},\pi_{k}^{-i})\|_{D_{k}^{i}}$
$\displaystyle\leq\;$
$\displaystyle\|\mathcal{H}^{i}(v^{i},\pi_{k}^{-i})\|_{D_{k}^{i}}$
($\text{Proj}_{k}^{i}(\cdot)$ being non-expansive with respect to
$\|\cdot\|_{D_{k}^{i}}$) $\displaystyle\leq\;$
$\displaystyle\|\mathcal{H}^{i}(v^{i},\pi_{k}^{-i})\|_{\infty}$
$\displaystyle\leq\;$ $\displaystyle 1+\gamma\|v^{i}\|_{\infty}$
$\displaystyle\leq\;$ $\displaystyle\frac{1}{1-\gamma},$

where the second last line follows from the definition of
$\mathcal{H}^{i}(\cdot,\cdot)$ in Eq. (40). Combining the previous inequality
and Eq. (41), we have
$\|\bar{w}_{k}^{i}\|_{2}\leq\lambda^{-1/2}(1-\gamma)^{-1}$.

  4. (4)

For any $k\geq 0$, we have by Assumption 4.3 that

$\displaystyle\Phi^{i}\bar{w}_{k}^{i}=\Phi^{i}[(\Phi^{i})^{\top}D_{k}^{i}\Phi^{i}]^{-1}(\Phi^{i})^{\top}D_{k}^{i}\mathcal{H}^{i}(v^{i},\pi_{k}^{-i})=\text{Proj}_{k}^{i}\mathcal{H}^{i}(v^{i},\pi_{k}^{-i})=\mathcal{H}^{i}(v^{i},\pi_{k}^{-i}).$

Let
$D^{i}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}^{i}|\times|\mathcal{S}||\mathcal{A}^{i}|}$
be a diagonal matrix such that each of the diagonal components is
$1/(|\mathcal{S}||\mathcal{A}^{i}|)$. Then, on the one hand, we have

$\displaystyle\|\Phi^{i}\bar{w}_{k+1}^{i}-\Phi^{i}\bar{w}_{k}^{i}\|_{D}^{2}\geq\;$
$\displaystyle\lambda_{\min}((\Phi^{i})^{\top}D\Phi^{i})\|\bar{w}_{k+1}^{i}-\bar{w}_{k}^{i}\|_{2}^{2}\geq\lambda\|\bar{w}_{k+1}^{i}-\bar{w}_{k}^{i}\|_{2}^{2}.$
(Assumption 4.1)

On the other hand, we have

$\displaystyle\|\mathcal{H}^{i}(v^{i},\pi_{k+1}^{-i})-\mathcal{H}^{i}(v^{i},\pi_{k}^{-i})\|_{D}$
$\displaystyle\leq\;$
$\displaystyle\|\mathcal{H}^{i}(v^{i},\pi_{k+1}^{-i})-\mathcal{H}^{i}(v^{i},\pi_{k}^{-i})\|_{\infty}$
$\displaystyle=\;$
$\displaystyle\max_{s,a^{i}}\left|\sum_{a^{-i}}\mathcal{T}^{i}(v^{i})(s,a^{i},a^{-i})(\pi_{k}^{-i}(a^{-i}\mid
s)-\pi_{k+1}^{-i}(a^{-i}\mid s))\right|$ $\displaystyle\leq\;$
$\displaystyle\max_{s,a^{i}}\left\\{\max_{a^{-i}}|\mathcal{T}^{i}(v^{i})(s,a^{i},a^{-i})|\right\\}\sum_{a^{-i}}|\pi_{k}^{-i}(a^{-i}\mid
s)-\pi_{k+1}^{-i}(a^{-i}\mid s)|$ $\displaystyle\leq\;$
$\displaystyle\frac{1}{1-\gamma}\max_{s}\|\pi_{k+1}^{-i}(s)-\pi_{k}^{-i}(s)\|_{1}$
$\displaystyle\leq\;$
$\displaystyle\frac{2A_{\max}\beta_{k}}{\tau\lambda^{1/2}(1-\gamma)^{2}}.$
(Lemma A.17)

It follows from the previous $3$ inequalities that

$\displaystyle\|\bar{w}_{k+1}^{i}-\bar{w}_{k}^{i}\|_{2}\leq\frac{2A_{\max}\beta_{k}}{\tau\lambda(1-\gamma)^{2}}.$

∎

######  Lemma A.16.

Given non-negative integers $k_{1}\leq k_{2}$, we have for any
$k\in\\{k_{1},\cdots,k_{2}\\}$ that

$\displaystyle\|w_{k_{2}}^{i}-w_{k_{1}}^{i}\|_{2}\leq\frac{2\alpha_{k_{1},k_{2}-1}}{\lambda^{1/2}(1-\gamma)}.$

###### Proof of Lemma A.16.

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

$\displaystyle\|w_{k+1}^{i}-w_{k}^{i}\|_{2}\leq\;$
$\displaystyle\alpha_{k}\|F^{i}(w_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\alpha_{k}(\|F^{i}(w_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-F^{i}(0,S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\|_{2})$
$\displaystyle+\alpha_{k}\|F^{i}(0,S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\alpha_{k}\left(\|w_{k}^{i}\|_{2}+\frac{1}{1-\gamma}\right)$
(Lemma A.15 (1) and (2)) $\displaystyle\leq\;$
$\displaystyle\alpha_{k}\left(\frac{1}{\lambda^{1/2}(1-\gamma)}+\frac{1}{1-\gamma}\right)$
($\|w_{k}^{i}\|_{2}\leq M=\frac{1}{\lambda^{1/2}(1-\gamma)}$)
$\displaystyle\leq\;$
$\displaystyle\frac{2\alpha_{k}}{\lambda^{1/2}(1-\gamma)}.$ ($\lambda\leq 1$)

Therefore, we have by telescoping that

$\displaystyle\|w_{k_{2}}^{i}-w_{k_{1}}^{i}\|_{2}\leq\frac{2\alpha_{k_{1},k_{2}-1}}{\lambda^{1/2}(1-\gamma)}.$

∎

######  Lemma A.17.

Given non-negative integers $k_{1}\leq k_{2}$ and $i\in\\{1,2\\}$, we have

$\displaystyle\|\pi_{k_{2}}^{i}(s)-\pi_{k_{1}}^{i}(s)\|_{1}\leq\frac{2A_{\max}\beta_{k_{1},k_{2}-1}}{\tau\lambda^{1/2}(1-\gamma)}.$

###### Proof of Lemma A.18.

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

$\displaystyle\|\pi_{k+1}^{i}(s)-\pi_{k}^{i}(s)\|_{1}=\;$
$\displaystyle\|\sigma_{\tau}(\tilde{q}_{k+1}^{i}(s))-\sigma_{\tau}(\tilde{q}_{k}^{i}(s))\|_{1}$
$\displaystyle\leq\;$
$\displaystyle\frac{1}{\tau}\|\tilde{q}_{k+1}^{i}(s)-\tilde{q}_{k}^{i}(s)\|_{1}$
$\displaystyle\leq\;$
$\displaystyle\frac{\beta_{k}}{\tau}\|q_{k}^{i}(s)-\tilde{q}_{k}^{i}(s)\|_{1}$
$\displaystyle\leq\;$
$\displaystyle\frac{\beta_{k}}{\tau}\sum_{a^{i}}\left|\phi^{i}(s,a^{i})^{\top}(w_{k}^{i}-\theta_{k}^{i})\right|$
$\displaystyle\leq\;$
$\displaystyle\frac{\beta_{k}}{\tau}\sum_{a^{i}}\|\phi^{i}(s,a^{i})\|_{2}(\|w_{k}^{i}\|_{2}+\|\theta_{k}^{i}\|_{2})$
$\displaystyle\leq\;$
$\displaystyle\frac{2A_{\max}\beta_{k}}{\tau\lambda^{1/2}(1-\gamma)}.$

The result follows from the previous inequality and telescoping. ∎

######  Lemma A.18.

Under Assumption 4.1, there exists $L_{p}\geq 1$ such that

$\displaystyle\|\mu_{\pi_{1}}-\mu_{\pi_{2}}\|_{1}\leq
L_{p}\max_{s\in\mathcal{S}}\sum_{i=1,2}\|\pi_{1}^{i}(s)-\pi_{2}^{i}(s)\|_{1}.$

###### Proof of Lemma A.18.

For any joint policies $\pi,\bar{\pi}\in\Pi$, under Assumption 4.1, the Markov
chain induced by either $\pi$ or $\bar{\pi}$ is irreducible and aperiodic,
hence is uniformly ergodic. Therefore, for any $\pi,\bar{\pi}\in\Pi$, the
existing Markov chain sensitivity analysis [79, Corollary 3.1] implies that

$\displaystyle\|\mu_{\pi}-\mu_{\bar{\pi}}\|_{1}\leq\;$
$\displaystyle\left(\hat{n}+\frac{C\rho^{\hat{n}}}{1-\rho}\right)\|P_{\pi}-P_{\bar{\pi}}\|_{\infty}$
($\hat{n}=\min\\{k\in\mathbb{Z}_{+}\,:\,k\geq\log_{\rho}C^{-1}\\}$)
$\displaystyle\leq\;$
$\displaystyle\left(\hat{n}+\frac{C\rho^{\hat{n}}}{1-\rho}\right)\max_{s\in\mathcal{S}}\|\pi(a^{1},a^{2}\mid
s)-\bar{\pi}(a^{1},a^{2}\mid s)\|_{1}$ $\displaystyle\leq\;$
$\displaystyle\left(\hat{n}+\frac{C\rho^{\hat{n}}}{1-\rho}\right)\max_{s\in\mathcal{S}}\sum_{a^{1},a^{2}}|\pi^{1}(a^{1}\mid
s)\pi^{2}(a^{2}\mid s)-\bar{\pi}^{1}(a^{1}\mid s)\bar{\pi}^{2}(a^{2}\mid s)|$
$\displaystyle\leq\;$
$\displaystyle\left(\hat{n}+\frac{C\rho^{\hat{n}}}{1-\rho}\right)\max_{s\in\mathcal{S}}\left(\sum_{a^{2}}|\pi^{2}(a^{2}\mid
s)-\bar{\pi}^{2}(a^{2}\mid s)|+\sum_{a^{1}}|\pi^{1}(a^{1}\mid
s)-\bar{\pi}^{1}(a^{1}\mid s)|\right)$ $\displaystyle=\;$
$\displaystyle\left(\hat{n}+\frac{C\rho^{\hat{n}}}{1-\rho}\right)\max_{s\in\mathcal{S}}\sum_{i=1,2}\|\pi_{1}^{i}(s)-\pi_{2}^{i}(s)\|_{1}.$

Since

$\displaystyle\hat{n}+\frac{C\rho^{\hat{n}}}{1-\rho}\leq\frac{\log(\rho/C)}{\log(\rho)}+\frac{1}{1-\rho},$

The result follows by letting
$L_{p}=\frac{\log(\rho/C)}{\log(\rho)}+\frac{1}{1-\rho}$.

#### A.4.5 Proof of Lemma A.13

Inspired by [15, 101, 126, 32], we use a conditioning argument to control
$E_{w,3}$. For any $k\geq z_{k}$, we have

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

We next bound each term on the RHS of the previous inequality.

##### The Term $E_{w,3,1}$.

Using the tower property of conditional expectations, we have

$\displaystyle E_{w,3,1}=\;$ $\displaystyle\mathbb{E}[\langle
F^{i}(w_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-\bar{F}_{k-z_{k}}^{i}(w_{k-z_{k}}^{i}),w_{k-z_{k}}^{i}-\bar{w}_{k-z_{k}}^{i}\rangle]$
$\displaystyle=\;$
$\displaystyle\mathbb{E}[\langle\mathbb{E}[F^{i}(w_{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}(w_{k-z_{k}}^{i}),w_{k-z_{k}}^{i}-\bar{w}_{k-z_{k}}^{i}\rangle]$
$\displaystyle\leq\;$
$\displaystyle\mathbb{E}[\|\mathbb{E}[F^{i}(w_{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}(w_{k-z_{k}}^{i})\|_{2}\|w_{k-z_{k}}^{i}-\bar{w}_{k-z_{k}}^{i}\|_{2}]$
$\displaystyle\leq\;$
$\displaystyle\frac{2}{\lambda^{1/2}(1-\gamma)}\mathbb{E}[\|\mathbb{E}[F^{i}(w_{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}(w_{k-z_{k}}^{i})\|_{2}],$
(43)

where the last line follows from $\|w_{k}^{i}\|_{2}\leq
M=\lambda^{-1/2}(1-\gamma)^{-1}$ and Lemma A.15 (3). To proceed, observe that

$\displaystyle\|\mathbb{E}[F^{i}(w_{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}(w_{k-z_{k}}^{i})\|_{2}$
$\displaystyle=\;$
$\displaystyle\|\bar{F}_{k}^{i}(w_{k-z_{k}}^{i})-\bar{F}_{k-z_{k}}^{i}(w_{k-z_{k}}^{i})\|_{2}+\|\mathbb{E}[F^{i}(w_{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}(w_{k-z_{k}}^{i})\|_{2}.$
(44)

We next bound each term on the RHS of Eq. (44). For the term
$\|\bar{F}_{k}^{i}(w_{k-z_{k}}^{i})-\bar{F}_{k-z_{k}}^{i}(w_{k-z_{k}}^{i})\|_{2}$,
we have

$\displaystyle\|\bar{F}_{k}^{i}(w_{k-z_{k}}^{i})-\bar{F}_{k-z_{k}}^{i}(w_{k-z_{k}}^{i})\|_{2}$
$\displaystyle=\;$
$\displaystyle\|(\Phi^{i})^{\top}D_{k}^{i}(\mathcal{H}^{i}(v^{i},\pi_{k}^{-i})-\Phi^{i}w_{k-z_{k}}^{i})-(\Phi^{i})^{\top}D_{k-z_{k}}^{i}(\mathcal{H}^{i}(v^{i},\pi_{k-z_{k}}^{-i})-\Phi^{i}w_{k-z_{k}}^{i})\|_{2}$
(Lemma A.15 (2) ) $\displaystyle=\;$
$\displaystyle\|(\Phi^{i})^{\top}D_{k}^{i}\Phi^{i}(\bar{w}_{k}^{i}-w_{k-z_{k}}^{i})-(\Phi^{i})^{\top}D_{k-z_{k}}^{i}\Phi^{i}(\bar{w}_{k-z_{k}}^{i}-w_{k-z_{k}}^{i})\|_{2}$
(Lemma A.15 (2) ) $\displaystyle\leq\;$
$\displaystyle\|(\Phi^{i})^{\top}D_{k}^{i}\Phi^{i}(\bar{w}_{k}^{i}-\bar{w}_{k-z_{k}}^{i})\|_{2}+\|(\Phi^{i})^{\top}(D_{k-z_{k}}^{i}-D_{k}^{i})\Phi^{i}(w_{k-z_{k}}^{i}-\bar{w}_{k-z_{k}}^{i})\|_{2}$
(Triangle inequality) $\displaystyle\leq\;$
$\displaystyle\frac{2A_{\max}\beta_{k-z_{k},k-1}}{\tau\lambda(1-\gamma)^{2}}+\frac{16L_{p}A_{\max}\beta_{k-z_{k},k-1}}{\tau\lambda(1-\gamma)^{2}}$
$\displaystyle\leq\;$
$\displaystyle\frac{18L_{p}A_{\max}\beta_{k-z_{k},k-1}}{\tau\lambda(1-\gamma)^{2}},$
($L_{p}\geq 1$)

where the second last inequality follows from

$\displaystyle\|(\Phi^{i})^{\top}D_{k}^{i}\Phi^{i}(\bar{w}_{k}^{i}-\bar{w}_{k-z_{k}}^{i})\|_{2}\leq\;$
$\displaystyle\|(\Phi^{i})^{\top}D_{k}^{i}\Phi^{i}\|_{2}\|\bar{w}_{k}^{i}-\bar{w}_{k-z_{k}}^{i}\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\|\bar{w}_{k}^{i}-\bar{w}_{k-z_{k}}^{i}\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\frac{2A_{\max}\beta_{k-z_{k},k-1}}{\tau\lambda(1-\gamma)^{2}}$
(Lemma A.15 (4) and telescoping)

and

$\displaystyle\|(\Phi^{i})^{\top}(D_{k-z_{k}}^{i}-D_{k}^{i})\Phi^{i}(w_{k-z_{k}}^{i}-\bar{w}_{k-z_{k}}^{i})\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\|(\Phi^{i})^{\top}\|_{1,2}\|D_{k-z_{k}}^{i}-D_{k}^{i}\|_{\infty,1}\|\Phi^{i}\|_{2,\infty}\|w_{k-z_{k}}^{i}-\bar{w}_{k-z_{k}}^{i}\|_{2}$
$\displaystyle=\;$
$\displaystyle\left(\max_{s,a^{i}}\|\phi^{i}(s,a^{i})\|_{2}\right)^{2}\sum_{s,a^{i}}\left|\mu_{k-z_{k}}(s)\pi_{k-z_{k}}^{i}(a^{i}\mid
s)-\mu_{k}(s)\pi_{k}^{i}(a^{i}\mid
s)\right|\|w_{k-z_{k}}^{i}-\bar{w}_{k-z_{k}}^{i}\|_{2}$ $\displaystyle\leq\;$
$\displaystyle\sum_{s,a^{i}}\left|\mu_{k-z_{k}}(s)\pi_{k-z_{k}}^{i}(a^{i}\mid
s)-\mu_{k}(s)\pi_{k}^{i}(a^{i}\mid
s)\right|\|w_{k-z_{k}}^{i}-\bar{w}_{k-z_{k}}^{i}\|_{2}$ $\displaystyle\leq\;$
$\displaystyle(\|\mu_{k-z_{k}}-\mu_{k}\|_{1}+\max_{s\in\mathcal{S}}\|\pi_{k-z_{k}}^{i}(s)-\pi_{k}^{i}(s)\|_{1})\|w_{k-z_{k}}^{i}-\bar{w}_{k-z_{k}}^{i}\|_{2}$
$\displaystyle\leq\;$ $\displaystyle
2L_{p}\sum_{j=1,2}\max_{s\in\mathcal{S}}\|\pi_{k-z_{k}}^{j}(s)-\pi_{k}^{j}(s)\|_{1}\|w_{k-z_{k}}^{i}-\bar{w}_{k-z_{k}}^{i}\|_{2}$
(Lemma A.18 and $L_{p}\geq 1$) $\displaystyle\leq\;$
$\displaystyle\frac{16L_{p}A_{\max}\beta_{k-z_{k},k-1}}{\tau\lambda(1-\gamma)^{2}}.$
(Lemma A.17, Lemma A.15 (4), and $\|w_{k}^{i}\|_{2}\leq M$ for all $k$)

For the term
$\|\mathbb{E}[F^{i}(w_{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}(w_{k-z_{k}}^{i})\|_{2}$
on the RHS of Eq. (44), we have

$\displaystyle\|\mathbb{E}[F^{i}(w_{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}(w_{k-z_{k}}^{i})\|_{2}$
$\displaystyle=\;$
$\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]\sum_{a^{i}}\pi_{k}^{i}(a^{i}\mid
s)\sum_{a^{-i}}\pi_{k}^{-i}(a^{-i}\mid s)\right.$
$\displaystyle\left.\times\sum_{s^{\prime}}p(s^{\prime}\mid
s,a^{i},a^{-i})F^{i}(w_{k-z_{k}}^{i},s,a^{i},a^{-i},s^{\prime})\right\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\frac{2}{\lambda^{1/2}(1-\gamma)}\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|$
(Lemma A.15 (1)) $\displaystyle\leq\;$
$\displaystyle\frac{2}{\lambda^{1/2}(1-\gamma)}\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|$
$\displaystyle+\frac{2}{\lambda^{1/2}(1-\gamma)}\sum_{s}\left|P_{\pi_{k}}^{z_{k}}(S_{k-z_{k}},s)-\mu_{k}(s)\right|$
$\displaystyle\leq\;$
$\displaystyle\frac{2}{\lambda^{1/2}(1-\gamma)}\left\|\prod_{j=k+1}^{k+z_{k}}P_{\pi_{j-z_{k}}}-P_{\pi_{k}}^{z_{k}}\right\|_{\infty}+\frac{4C\rho^{z_{k}}}{\lambda^{1/2}(1-\gamma)}$
(Assumption 4.1) $\displaystyle\leq\;$
$\displaystyle\frac{2}{\lambda^{1/2}(1-\gamma)}\left\|\prod_{j=k+1}^{k+z_{k}}P_{\pi_{j-z_{k}}}-P_{\pi_{k}}^{z_{k}}\right\|_{\infty}+\frac{4\beta_{k}}{\lambda^{1/2}(1-\gamma)},$

where the last line follows from the definition of $z_{k}$. To proceed,
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}$
$\displaystyle\leq\;$
$\displaystyle\sum_{\ell=1}^{z_{k}}\|P_{\pi_{k-\ell+1}}-P_{\pi_{k}}\|_{\infty}.$

It remains to bound $\|P_{\pi_{k-\ell+1}}-P_{\pi_{k}}\|_{\infty}$. Using the
explicit expression of $P_{\pi_{k}}$, we have for any $\ell\in[1,z_{k}]$ that

$\displaystyle\|P_{\pi_{k-\ell+1}}-P_{\pi_{k}}\|_{\infty}$ $\displaystyle=\;$
$\displaystyle\max_{s}\sum_{s^{\prime}}\left|\sum_{a^{i},a^{-i}}(\pi_{k-\ell+1}^{i}(a^{i}\mid
s)\pi_{k-\ell+1}^{-i}(a^{-i}\mid s)-\pi_{k}^{i}(a^{i}\mid
s)\pi_{k}^{-i}(a^{-i}\mid s))p(s^{\prime}\mid s,a^{i},a^{-i})\right|$
$\displaystyle\leq\;$
$\displaystyle\max_{s}\sum_{a^{i},a^{-i}}\left|\pi_{k-\ell+1}^{i}(a^{i}\mid
s)\pi_{k-\ell+1}^{-i}(a^{-i}\mid s)-\pi_{k}^{i}(a^{i}\mid
s)\pi_{k}^{-i}(a^{-i}\mid s)\right|$ $\displaystyle\leq\;$
$\displaystyle\max_{s}\sum_{a^{-i}}\left|\pi_{k-\ell+1}^{-i}(a^{-i}\mid
s)-\pi_{k}^{-i}(a^{-i}\mid
s)\right|+\max_{s}\sum_{a^{i}}\left|\pi_{k-\ell+1}^{i}(a^{i}\mid
s)-\pi_{k}^{i}(a^{i}\mid s)\right|$ $\displaystyle=\;$
$\displaystyle\sum_{i=1,2}\max_{s}\|\pi_{k}^{i}(s)-\pi_{k-\ell+1}^{i}(s)\|_{1}$
$\displaystyle\leq\;$
$\displaystyle\frac{4A_{\max}\beta_{k-z_{k},k-1}}{\tau\lambda^{1/2}(1-\gamma)}$
(Lemma A.17)

It follows that

$\displaystyle\left\|\prod_{j=k+1}^{k+z_{k}}P_{\pi_{j-z_{k}}}-P_{\pi_{k}}^{z_{k}}\right\|_{\infty}\leq\frac{4A_{\max}z_{k}\beta_{k-z_{k},k-1}}{\tau\lambda^{1/2}(1-\gamma)}$

As a result, we have

$\displaystyle\|\mathbb{E}[F^{i}(w_{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}(w_{k-z_{k}}^{i})\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\frac{8A_{\max}z_{k}\beta_{k-z_{k},k-1}}{\tau\lambda(1-\gamma)^{2}}+\frac{4\beta_{k}}{\lambda^{1/2}(1-\gamma)}$
$\displaystyle\leq\;$
$\displaystyle\frac{10A_{\max}z_{k}\beta_{k-z_{k},k-1}}{\tau\lambda(1-\gamma)^{2}},$

where the last line follows from $\lambda\leq 1$, $A_{\max}\geq 2$, and
$\tau\leq 1/(1-\gamma)$. Using the upper bounds we established for both terms
on the RHS of Eq. (44), we have

$\displaystyle\|\mathbb{E}[F^{i}(w_{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}(w_{k-z_{k}}^{i})\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\frac{10A_{\max}z_{k}\beta_{k-z_{k},k-1}}{\tau\lambda(1-\gamma)^{2}}+\frac{18L_{p}A_{\max}\beta_{k-z_{k},k-1}}{\tau\lambda(1-\gamma)^{2}}$
$\displaystyle\leq\;$
$\displaystyle\frac{28L_{p}A_{\max}z_{k}\beta_{k-z_{k},k-1}}{\tau\lambda(1-\gamma)^{2}}$
($L_{p}\geq 1$)

Finally, using the previous inequality in Eq. (43), we have

$\displaystyle E_{w,3,1}\leq\;$
$\displaystyle\frac{2}{\lambda^{1/2}(1-\gamma)}\mathbb{E}[\|\mathbb{E}[F^{i}(w_{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}(w_{k-z_{k}}^{i})\|_{2}]$
$\displaystyle\leq\;$
$\displaystyle\frac{56L_{p}A_{\max}z_{k}\beta_{k-z_{k},k-1}}{\tau\lambda^{3/2}(1-\gamma)^{3}}.$

##### The Term $E_{w,3,2}$.

For the term $E_{w,3,2}$, we have

$\displaystyle E_{w,3,2}=\;$ $\displaystyle\mathbb{E}[\langle
F^{i}(w_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-\bar{F}_{k-z_{k}}^{i}(w_{k-z_{k}}^{i}),w_{k}^{i}-w_{k-z_{k}}^{i}\rangle]$
$\displaystyle\leq\;$
$\displaystyle\mathbb{E}[\|F^{i}(w_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-\bar{F}_{k-z_{k}}^{i}(w_{k-z_{k}}^{i})\|_{2}\|w_{k}^{i}-w_{k-z_{k}}^{i}\|_{2}].$
(45)

For the term
$\|F^{i}(w_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-\bar{F}_{k-z_{k}}^{i}(w_{k-z_{k}}^{i})\|_{2}$,
we have

$\displaystyle\|F^{i}(w_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-\bar{F}_{k-z_{k}}^{i}(w_{k-z_{k}}^{i})\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\|F^{i}(w_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-F^{i}(0,S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\|_{2}$
$\displaystyle+\|F^{i}(0,S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\|_{2}+\|\bar{F}_{k-z_{k}}^{i}(w_{k-z_{k}}^{i})-\bar{F}_{k-z_{k}}^{i}(0)\|_{2}+\|\bar{F}_{k-z_{k}}^{i}(0)\|_{2}$
$\displaystyle\leq\;$ $\displaystyle
2\|w_{k-z_{k}}^{i}\|_{2}+\frac{2}{1-\gamma}$ $\displaystyle\leq\;$
$\displaystyle\frac{4}{\lambda^{1/2}(1-\gamma)},$ (46)

where the last line follows from $\|w_{k}^{i}\|_{2}\leq
M=\lambda^{-1/2}(1-\gamma)^{-1}$ for all $k$. For the term
$\|w_{k}^{i}-w_{k-z_{k}}^{i}\|_{2}$ on the RHS of Eq. (45), we have by Lemma
A.16 that

$\displaystyle\|w_{k}^{i}-w_{k-z_{k}}^{i}\|_{2}\leq\frac{2\alpha_{k-z_{k},k-1}}{\lambda^{1/2}(1-\gamma)}.$

Using the previous two inequalities in Eq. (45), we have

$\displaystyle
E_{w,3,2}\leq\frac{8\alpha_{k-z_{k},k-1}}{\lambda(1-\gamma)^{2}}.$

##### The Term $E_{w,3,3}$.

For the term $E_{w,3,3}$, we have

$\displaystyle E_{w,3,3}=\;$ $\displaystyle\mathbb{E}[\langle
F^{i}(w_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-\bar{F}_{k-z_{k}}^{i}(w_{k-z_{k}}^{i}),\bar{w}_{k-z_{k}}^{i}-\bar{w}_{k}^{i}\rangle]$
$\displaystyle\leq\;$
$\displaystyle\mathbb{E}[\|F^{i}(w_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-\bar{F}_{k-z_{k}}^{i}(w_{k-z_{k}}^{i})\|_{2}\|\bar{w}_{k-z_{k}}^{i}-\bar{w}_{k}^{i}\|_{2}]$
$\displaystyle\leq\;$
$\displaystyle\frac{4}{\lambda^{1/2}(1-\gamma)}\frac{2A_{\max}\beta_{k-z_{k},k-1}}{\tau\lambda(1-\gamma)^{2}}$
$\displaystyle=\;$
$\displaystyle\frac{8A_{\max}\beta_{k-z_{k},k-1}}{\tau\lambda^{3/2}(1-\gamma)^{3}},$
(47)

where the last line follows from Eq. (46) and Lemma A.15 (4).

##### The Term $E_{w,3,4}$.

For the term $E_{w,3,4}$, we have

$\displaystyle E_{w,3,4}=\;$ $\displaystyle\mathbb{E}[\langle
F^{i}(w_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-F^{i}(w_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1}),w_{k}^{i}-\bar{w}_{k}^{i}\rangle]$
$\displaystyle=\;$
$\displaystyle\mathbb{E}[\|F^{i}(w_{k}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})-F^{i}(w_{k-z_{k}}^{i},S_{k},A_{k}^{i},A_{k}^{-i},S_{k+1})\|_{2}\|w_{k}^{i}-\bar{w}_{k}^{i}\|_{2}]$
$\displaystyle\leq\;$
$\displaystyle\mathbb{E}[\|w_{k}^{i}-w_{k-z_{k}}^{i}\|_{2}\|w_{k}^{i}-\bar{w}_{k}^{i}\|_{2}]$
(Lemma A.15 (1)) $\displaystyle\leq\;$
$\displaystyle\mathbb{E}[\|w_{k}^{i}-w_{k-z_{k}}^{i}\|_{2}(\|w_{k}^{i}\|_{2}+\|\bar{w}_{k}^{i}\|_{2})]$
$\displaystyle\leq\;$
$\displaystyle\frac{4\alpha_{k-z_{k},k-1}}{\lambda(1-\gamma)^{2}},$

where the last line follows from Lemma A.16, Lemma A.15 (3), and
$\|w_{k}^{i}\|_{2}\leq M=\lambda^{-1/2}(1-\gamma)^{-1}$.

##### The Term $E_{w,3,5}$.

For the term $E_{w,3,5}$, we have

$\displaystyle E_{w,3,4}=\;$
$\displaystyle\mathbb{E}[\langle\bar{F}_{k-z_{k}}^{i}(w_{k-z_{k}}^{i})-\bar{F}_{k}^{i}(w_{k}^{i}),w_{k}^{i}-\bar{w}_{k}^{i}\rangle]$
$\displaystyle\leq\;$
$\displaystyle\mathbb{E}[\|\bar{F}_{k-z_{k}}^{i}(w_{k-z_{k}}^{i})-\bar{F}_{k}^{i}(w_{k}^{i})\|_{2}\|w_{k}^{i}-\bar{w}_{k}^{i}\|_{2}]$
$\displaystyle\leq\;$
$\displaystyle\mathbb{E}[\|w_{k-z_{k}}^{i}-w_{k}^{i}\|_{2}\|w_{k}^{i}-\bar{w}_{k}^{i}\|_{2}]$
(Lemma A.15 (1) and Jensen’s inequality) $\displaystyle\leq\;$
$\displaystyle\frac{4\alpha_{k-z_{k},k-1}}{\lambda(1-\gamma)^{2}},$

where the last line follows from Lemma A.16, Lemma A.15 (3), and
$\|w_{k}^{i}\|_{2}\leq M=\lambda^{-1/2}(1-\gamma)^{-1}$.

Using the upper bounds we obtained for the terms $E_{w,3,1}$ to $E_{w,3,5}$ in
Eq. (42), we have

$\displaystyle E_{w,3}=\;$
$\displaystyle\frac{56L_{p}A_{\max}z_{k}\beta_{k-z_{k},k-1}}{\tau\lambda^{3/2}(1-\gamma)^{3}}+\frac{8A_{\max}\beta_{k-z_{k},k-1}}{\tau\lambda^{3/2}(1-\gamma)^{3}}+\frac{16\alpha_{k-z_{k},k-1}}{\lambda(1-\gamma)^{2}}$
$\displaystyle\leq\;$
$\displaystyle\frac{64L_{p}A_{\max}z_{k}\beta_{k-z_{k},k-1}}{\tau\lambda^{3/2}(1-\gamma)^{3}}+\frac{16\alpha_{k-z_{k},k-1}}{\lambda(1-\gamma)^{2}}$
($L_{p}\geq 1$) $\displaystyle\leq\;$
$\displaystyle\frac{17z_{k}\alpha_{k-z_{k},k-1}}{\tau\lambda^{3/2}(1-\gamma)^{3}},$

where the last line follows from
$\frac{\beta_{k}}{\alpha_{k}}=c_{\alpha,\beta}\leq\frac{1}{64L_{p}A_{\max}}$,
$\lambda\leq 1$, and $\tau\leq 1/(1-\gamma)$. ∎

### A.5 Solving the Recursion

We begin by restating the Lyapunov inequalities from the previous sections:

  * •

Lemma A.4:

$\displaystyle\mathcal{L}_{v}(t+1)\leq\gamma\mathcal{L}_{v}(t)+\frac{17A_{\max}^{2}}{\tau^{2}(1-\gamma)^{2}}\mathcal{L}_{\theta}(t,K)+2\mathcal{L}_{\text{sum}}(t)+2\mathcal{L}_{w}(t,K)^{1/2}+12\tau\log(A_{\max})+\mu.$
(48)

  * •

Lemma A.5:

$\displaystyle\mathcal{L}_{\text{sum}}(t+1)\leq\gamma\mathcal{L}_{\text{sum}}(t)+2\mathcal{L}_{w}(t,K)^{1/2}.$
(49)

  * •

Lemma A.6:

$\displaystyle\mathcal{L}_{\theta}(t,k+1)\leq\left(1-\frac{\beta_{k}}{2}\right)\mathcal{L}_{\theta}(t,k)+\frac{520A_{\max}\beta_{k}}{\tau}\mathcal{L}_{w}(t,k)+4\beta_{k}\mathcal{L}_{\text{sum}}(t)+\frac{276A_{\max}^{1/2}\beta_{k}^{2}}{\tau\lambda^{1/2}(1-\gamma)}.$
(50)

  * •

Lemma A.14:

$\displaystyle\mathbb{E}[\mathcal{L}_{w}(t,k+1)]\leq\;$
$\displaystyle\left(1-\frac{3\lambda\alpha_{k}}{2}\right)\mathbb{E}[\mathcal{L}_{w}(t,k)]+\frac{84z_{k}\alpha_{k}\alpha_{k-z_{k},k-1}}{\tau\lambda^{3/2}(1-\gamma)^{3}}+\frac{32A_{\max}^{2}\beta_{k}^{2}}{\tau^{2}\lambda^{3}(1-\gamma)^{4}\alpha_{k}}.$
(51)

The next step is to solve the coupled Lyapunov inequalities above to obtain
finite-sample bounds. Here, we consider using constant stepsizes:
$\alpha_{k}\equiv\alpha$ and $\beta_{k}\equiv\beta$. The finite-sample bounds
for using diminishing stepsizes are straightforward extensions as we derived
all the Lyapunov drift inequalities for general stepsizes.

Repeatedly using Eq. (51), we have for all $k\geq z_{\beta}$ that

$\displaystyle\mathbb{E}[\mathcal{L}_{w}(t,k)]\leq\;$
$\displaystyle\left(1-\lambda\alpha\right)^{k-z_{\beta}}\mathbb{E}[\mathcal{L}_{w}(t,z_{\beta})]+\frac{84z_{\beta}^{2}\alpha}{\tau\lambda^{5/2}(1-\gamma)^{3}}+\frac{32A_{\max}^{2}\beta^{2}}{\tau^{2}\lambda^{4}(1-\gamma)^{4}\alpha^{2}}$
$\displaystyle\leq\;$
$\displaystyle\frac{8\left(1-\lambda\alpha\right)^{k-z_{\beta}}}{\lambda(1-\gamma)^{2}}+\frac{84z_{\beta}^{2}\alpha}{\tau\lambda^{5/2}(1-\gamma)^{3}}+\frac{32A_{\max}^{2}\beta^{2}}{\tau^{2}\lambda^{4}(1-\gamma)^{4}\alpha^{2}},$
(52)

where the last line follows from

$\displaystyle\mathcal{L}_{w}(t,k)=\sum_{i=1,2}\mathbb{E}[\|w_{t,k}^{i}-\bar{w}_{t,k}^{i}\|_{2}^{2}]\leq\frac{8}{\lambda(1-\gamma)^{2}}.$

Using Eq. (52) in Eq. (50), we have

$\displaystyle\mathbb{E}[\mathcal{L}_{\theta}(t,k+1)]\leq\;$
$\displaystyle\left(1-\frac{\beta}{2}\right)\mathbb{E}[\mathcal{L}_{\theta}(t,k)]+4\beta\mathbb{E}[\mathcal{L}_{\text{sum}}(t)]+\frac{276A_{\max}^{1/2}\beta^{2}}{\tau\lambda^{1/2}(1-\gamma)}$
$\displaystyle+\frac{520A_{\max}\beta}{\tau}\left[\frac{8\left(1-\lambda\alpha\right)^{k-z_{\beta}}}{\lambda(1-\gamma)^{2}}+\frac{84z_{\beta}^{2}\alpha}{\tau\lambda^{5/2}(1-\gamma)^{3}}+\frac{32A_{\max}^{2}\beta^{2}}{\tau^{2}\lambda^{4}(1-\gamma)^{4}\alpha^{2}}\right]$
$\displaystyle\leq\;$
$\displaystyle\left(1-\frac{\beta}{2}\right)\mathbb{E}[\mathcal{L}_{\theta}(t,k)]+4\beta\mathbb{E}[\mathcal{L}_{\text{sum}}(t)]+\frac{276A_{\max}^{1/2}\beta^{2}}{\tau\lambda^{1/2}(1-\gamma)}$
$\displaystyle+\frac{520A_{\max}\beta}{\tau}\left[\frac{8\left(1-\beta\right)^{k-z_{\beta}}}{\lambda(1-\gamma)^{2}}+\frac{84z_{\beta}^{2}\alpha}{\tau\lambda^{5/2}(1-\gamma)^{3}}+\frac{32A_{\max}^{2}\beta^{2}}{\tau^{2}\lambda^{4}(1-\gamma)^{4}\alpha^{2}}\right],$

where the last line follows from $\beta\leq\lambda\alpha$. Repeatedly using
the previous inequality, we have for all $k\geq z_{\beta}$ that

$\displaystyle\mathbb{E}[\mathcal{L}_{\theta}(t,k)]\leq\;$
$\displaystyle\left(1-\frac{\beta}{2}\right)^{k-z_{\beta}}\mathcal{L}_{\theta}(t,z_{\beta})+8\mathbb{E}[\mathcal{L}_{\text{sum}}(t)]+\frac{552A_{\max}^{1/2}\beta}{\tau\lambda^{1/2}(1-\gamma)}$
$\displaystyle+\frac{520A_{\max}}{\tau}\left[\frac{8\beta(k-z_{\beta})\left(1-\beta/2\right)^{k-z_{\beta}-1}}{\lambda(1-\gamma)^{2}}+\frac{168z_{\beta}^{2}\alpha}{\tau\lambda^{5/2}(1-\gamma)^{3}}+\frac{64A_{\max}^{2}\beta^{2}}{\tau^{2}\lambda^{4}(1-\gamma)^{4}\alpha^{2}}\right]$
$\displaystyle\leq\;$
$\displaystyle\frac{256A_{\max}}{\tau\lambda(1-\gamma)^{2}}\left(1-\frac{\beta}{2}\right)^{k-z_{\beta}}+8\mathbb{E}[\mathcal{L}_{\text{sum}}(t)]+\frac{552A_{\max}^{1/2}\beta}{\tau\lambda^{1/2}(1-\gamma)}$
$\displaystyle+\frac{520A_{\max}}{\tau}\left[\frac{8\beta(k-z_{\beta})\left(1-\beta/2\right)^{k-z_{\beta}-1}}{\lambda(1-\gamma)^{2}}+\frac{168z_{\beta}^{2}\alpha}{\tau\lambda^{5/2}(1-\gamma)^{3}}+\frac{64A_{\max}^{2}\beta^{2}}{\tau^{2}\lambda^{4}(1-\gamma)^{4}\alpha^{2}}\right],$
(53)

where the last line follows from

$\displaystyle\mathcal{L}_{\theta}(t,k)=\;$
$\displaystyle\max_{s\in\mathcal{S}}\sum_{i=1,2}\max_{u^{i}\in\Delta(\mathcal{A}^{i})}\min_{\bar{u}^{i}\in\Delta(\mathcal{A}^{i})}\left\\{(u^{i}-\bar{u}^{i})^{\top}\tilde{q}_{t,k}^{i}(s)+\tau\nu(u^{i})-\tau\nu(\bar{u}^{i})\right.$
$\displaystyle\left.+\;\frac{1}{2\mu}\|\tilde{q}_{t,k}^{-i}(s)-\mathcal{T}^{-i}(v_{t}^{-i})(s)\bar{u}^{i}\|_{2}^{2}\right\\}$
$\displaystyle\leq\;$
$\displaystyle\max_{s\in\mathcal{S}}\sum_{i=1,2}\frac{1}{2\mu}\|\tilde{q}_{t,k}^{-i}(s)-\mathcal{T}^{-i}(v_{t}^{-i})(s)\sigma_{\tau}(\tilde{q}_{t,k}^{i}(s))\|_{2}^{2}$
$\displaystyle\leq\;$
$\displaystyle\max_{s\in\mathcal{S}}\sum_{i=1,2}\frac{1}{2\mu}(\|\tilde{q}_{t,k}^{-i}(s)\|_{2}+\|\mathcal{T}^{-i}(v_{t}^{-i})(s)\sigma_{\tau}(\tilde{q}_{t,k}^{i}(s))\|_{2})^{2}$
$\displaystyle\leq\;$
$\displaystyle\max_{s\in\mathcal{S}}\sum_{i=1,2}\frac{1}{\mu}(\|\tilde{q}_{t,k}^{-i}(s)\|_{2}^{2}+\|\mathcal{T}^{-i}(v_{t}^{-i})(s)\sigma_{\tau}(\tilde{q}_{t,k}^{i}(s))\|_{2}^{2})$
($(a+b)^{2}\leq 2a^{2}+2b^{2}$) $\displaystyle\leq\;$
$\displaystyle\max_{s\in\mathcal{S}}\sum_{i=1,2}\frac{1}{\mu}\left(\sum_{a^{i}}(\phi^{i}(s,a^{i})^{\top}\theta_{k}^{i})^{2}+\frac{A_{\max}}{(1-\gamma)^{2}}\right)$
$\displaystyle\leq\;$
$\displaystyle\sum_{i=1,2}\frac{1}{\mu}\left(A_{\max}\|\theta_{k}^{i}\|_{2}^{2}+\frac{A_{\max}}{(1-\gamma)^{2}}\right)$
(Cauchy–Schwarz inequality and $\|\phi^{i}(s,a^{i})\|_{2}\leq 1$)
$\displaystyle\leq\;$
$\displaystyle\sum_{i=1,2}\frac{1}{\mu}\left(\frac{A_{\max}}{\lambda(1-\gamma)^{2}}+\frac{A_{\max}}{(1-\gamma)^{2}}\right)$
$\displaystyle\leq\;$
$\displaystyle\frac{256A_{\max}}{\tau\lambda(1-\gamma)^{2}},\quad\forall\;t,k,$

where the second last inequality follows from $\|w_{t,k}^{i}\|_{2}\leq
M=\lambda^{-1/2}(1-\gamma)^{-1}$ and $\theta_{t,k}^{i}$ being a convex
combination of $\\{w_{t,\ell}^{i}\\}_{0\leq\ell\leq k-1}$, and the last
inequality follows from $\lambda\leq 1$ and $\mu=\tau/64$.

Similarly, using Eq. (52) in Eq. (49), we have

$\displaystyle\mathbb{E}[\mathcal{L}_{\text{sum}}(t+1)]\leq\gamma\mathbb{E}[\mathcal{L}_{\text{sum}}(t)]+\frac{6\left(1-\lambda\alpha\right)^{\frac{K-z_{\beta}}{2}}}{\lambda^{1/2}(1-\gamma)}+\frac{20z_{\beta}\alpha^{1/2}}{\tau^{1/2}\lambda^{5/4}(1-\gamma)^{3/2}}+\frac{12A_{\max}\beta}{\tau\lambda^{2}(1-\gamma)^{2}\alpha}.$

Repeatedly using the previous inequality, since
$\mathcal{L}_{\text{sum}}(t)\leq 2/(1-\gamma)$, we have

$\displaystyle\mathbb{E}[\mathcal{L}_{\text{sum}}(t)]\leq\frac{2\gamma^{t}}{1-\gamma}+\frac{6\left(1-\lambda\alpha\right)^{\frac{K-z_{\beta}}{2}}}{\lambda^{1/2}(1-\gamma)^{2}}+\frac{20z_{\beta}\alpha^{1/2}}{\tau^{1/2}\lambda^{5/4}(1-\gamma)^{5/2}}+\frac{12A_{\max}\beta}{\tau\lambda^{2}(1-\gamma)^{3}\alpha}$
(54)

Using Eqs. (52), (53), and (54) altogether in Eq. (48), we have

$\displaystyle\mathbb{E}[\mathcal{L}_{v}(t+1)]\leq\;$
$\displaystyle\gamma\mathbb{E}[\mathcal{L}_{v}(t)]+\frac{17A_{\max}^{2}}{\tau^{2}(1-\gamma)^{2}}\mathbb{E}[\mathcal{L}_{\theta}(t,K)]+2\mathbb{E}[\mathcal{L}_{\text{sum}}(t)]+2\mathbb{E}[\mathcal{L}_{w}(t,K)^{1/2}]$
$\displaystyle+12\tau\log(A_{\max})+\mu$ $\displaystyle\leq\;$
$\displaystyle\gamma\mathbb{E}[\mathcal{L}_{v}(t)]+\frac{276A_{\max}^{2}\gamma^{t}}{\tau^{2}(1-\gamma)^{3}}+\frac{828A_{\max}^{2}\left(1-\lambda\alpha\right)^{\frac{K-z_{\beta}}{2}}}{\tau^{2}\lambda^{1/2}(1-\gamma)^{4}}+\frac{2760A_{\max}^{2}z_{\beta}\alpha^{1/2}}{\tau^{5/2}\lambda^{5/4}(1-\gamma)^{9/2}}$
$\displaystyle+\frac{1656A_{\max}^{3}\beta}{\tau^{3}\lambda^{2}(1-\gamma)^{5}\alpha}+\frac{4352A_{\max}^{3}}{\tau^{3}\lambda(1-\gamma)^{4}}\left(1-\frac{\beta}{2}\right)^{K-z_{\beta}}+\frac{9384A_{\max}^{5/2}\beta}{\tau^{3}\lambda^{1/2}(1-\gamma)^{3}}$
$\displaystyle+\frac{70720A_{\max}^{3}(K-z_{\beta})\left(1-\beta/2\right)^{K-z_{\beta}-1}}{\tau^{3}\lambda(1-\gamma)^{4}}+\frac{1485120A_{\max}^{3}z_{\beta}^{2}\alpha}{\tau^{4}\lambda^{5/2}(1-\gamma)^{5}}+\frac{565760A_{\max}^{5}\beta^{2}}{\tau^{5}\lambda^{4}(1-\gamma)^{6}\alpha^{2}}$
$\displaystyle+\frac{6\left(1-\lambda\alpha\right)^{\frac{K-z_{\beta}}{2}}}{\lambda^{1/2}(1-\gamma)}+\frac{20z_{\beta}\alpha^{1/2}}{\tau^{1/2}\lambda^{5/4}(1-\gamma)^{3/2}}+\frac{12A_{\max}\beta}{\tau\lambda^{2}(1-\gamma)^{2}\alpha}$
$\displaystyle+12\tau\log(A_{\max})+\frac{\tau}{64}$ $\displaystyle\leq\;$
$\displaystyle\gamma\mathbb{E}[\mathcal{L}_{v}(t)]+\frac{75906A_{\max}^{3}K\left(1-\beta/2\right)^{\frac{K-z_{\beta}-1}{2}}}{\tau^{3}\lambda(1-\gamma)^{5}}+\frac{276A_{\max}^{2}\gamma^{t}}{\tau^{2}(1-\gamma)^{3}}+\frac{2780A_{\max}^{2}z_{\beta}\alpha^{1/2}}{\tau^{5/2}\lambda^{5/4}(1-\gamma)^{9/2}}$
$\displaystyle+\frac{1668A_{\max}^{3}\beta}{\tau^{3}\lambda^{2}(1-\gamma)^{5}\alpha}+\frac{1494504A_{\max}^{3}z_{\beta}^{2}\alpha}{\tau^{4}\lambda^{5/2}(1-\gamma)^{5}}+\frac{565760A_{\max}^{5}\beta^{2}}{\tau^{5}\lambda^{4}(1-\gamma)^{6}\alpha^{2}}+13\tau\log(A_{\max}).$

Repeatedly using the previous inequality, since
$\mathcal{L}_{v}(t)\leq\frac{4}{1-\gamma}$, we have

$\displaystyle\mathbb{E}[\mathcal{L}_{v}(T)]\lesssim\;$
$\displaystyle\frac{A_{\max}^{3}K\left(1-\beta/2\right)^{\frac{K-z_{\beta}-1}{2}}}{\tau^{3}\lambda(1-\gamma)^{6}}+\frac{A_{\max}^{2}T\gamma^{T-1}}{\tau^{2}(1-\gamma)^{3}}+\frac{A_{\max}^{2}z_{\beta}\alpha^{1/2}}{\tau^{5/2}\lambda^{5/4}(1-\gamma)^{11/2}}$
$\displaystyle+\frac{A_{\max}^{3}\beta}{\tau^{3}\lambda^{2}(1-\gamma)^{6}\alpha}+\frac{A_{\max}^{3}z_{\beta}^{2}\alpha}{\tau^{4}\lambda^{5/2}(1-\gamma)^{6}}+\frac{A_{\max}^{5}\beta^{2}}{\tau^{5}\lambda^{4}(1-\gamma)^{7}\alpha^{2}}+\frac{\tau\log(A_{\max})}{1-\gamma},$
(55)

where we recall that the notation $a\lesssim b$ means that there exists an
absolute constant $c>0$ such that $a\leq bc$.

Finally, using Eqs. (55), (52), (53), and (54) together in Lemma A.3, we have

$\displaystyle\mathbb{E}[\text{NG}(\pi_{T,K}^{1},\pi_{T,K}^{2})]\lesssim\;$
$\displaystyle\frac{A_{\max}^{3}K\left(1-\beta/2\right)^{\frac{K-z_{\beta}-1}{2}}}{\tau^{3}\lambda(1-\gamma)^{7}}+\frac{A_{\max}^{2}T\gamma^{T-1}}{\tau^{2}(1-\gamma)^{4}}+\frac{A_{\max}^{2}z_{\beta}\alpha^{1/2}}{\tau^{5/2}\lambda^{5/4}(1-\gamma)^{13/2}}$
$\displaystyle+\frac{A_{\max}^{3}\beta}{\tau^{3}\lambda^{2}(1-\gamma)^{7}\alpha}+\frac{A_{\max}^{3}z_{\beta}^{2}\alpha}{\tau^{4}\lambda^{5/2}(1-\gamma)^{7}}+\frac{A_{\max}^{5}\beta^{2}}{\tau^{5}\lambda^{4}(1-\gamma)^{8}\alpha^{2}}+\frac{\tau\log(A_{\max})}{(1-\gamma)^{2}}.$

As for the sample complexity, to achieve
$\mathbb{E}[\text{NG}(\pi_{T,K}^{1},\pi_{T,K}^{2})]\leq\epsilon$, in view of
the previous inequality, we have

$\displaystyle
T=\tilde{\mathcal{O}}(1),\;\tau=\mathcal{O}(\epsilon),\;\alpha=\tilde{\mathcal{O}}(\epsilon^{7}),\beta=\tilde{\mathcal{O}}(\epsilon^{11}),\;K=\tilde{\mathcal{O}}(\epsilon^{-11}).$

Therefore, the overall sample complexity (i.e., $KT$) is
$\tilde{\mathcal{O}}(\epsilon^{-11})$. It is easy to check that it is also
polynomial in $1/(1-\gamma)$ and $\lambda$.

### A.6 Supporting Lemmas

######  Lemma A.19.

The following results hold.

  1. (1)

For any $v_{1},v_{2}\in\mathbb{R}^{|\mathcal{S}|}$ and $i\in\\{1,2\\}$, we
have

$\displaystyle\|\mathcal{T}^{i}(v_{1})-\mathcal{T}^{i}(v_{2})\|_{\infty}\leq\gamma\|v_{1}-v_{2}\|_{\infty},\quad\text{and}\quad\|\mathcal{T}^{i}(v_{1})+\mathcal{T}^{-i}(v_{2})\|_{\infty}\leq\gamma\|v_{1}+v_{2}\|_{\infty}.$

  2. (2)

For any $v_{1},v_{2}\in\mathbb{R}^{|\mathcal{S}|}$, $s\in\mathcal{S}$, and
$i\in\\{1,2\\}$, we have

$\displaystyle\max_{\mu^{i}\in\Delta(\mathcal{\mathcal{A}}^{i})}\max_{\mu^{-i}\in\Delta(\mathcal{\mathcal{A}}^{-i})}\left|(\mu^{i})^{\top}(\mathcal{T}^{i}(v_{1})(s)-\mathcal{T}^{i}(v_{2})(s))\mu^{-i}\right|\leq\gamma\|v_{1}-v_{2}\|_{\infty}.$

  3. (3)

Given any $v^{1},v^{2}\in\mathbb{R}^{|\mathcal{S}|}$,
$\tilde{q}^{1}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}^{1}|}$ and
$\tilde{q}^{2}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}^{2}|}$, let
$\pi^{i}(s)=\sigma_{\tau}(\tilde{q}^{i}(s))$ for all $s\in\mathcal{S}$ and
$i\in\\{1,2\\}$. Then we have for all $s\in\mathcal{S}$ that

$\displaystyle\left|\sum_{i=1,2}\max_{\mu^{i}\in\Delta(\mathcal{A}^{i})}(\mu^{i})^{\top}\mathcal{T}^{i}(v^{i})(s)\pi^{-i}(s)\right|\leq\;$
$\displaystyle\frac{9A_{\max}^{2}}{\tau^{2}(1-\gamma)^{2}}V_{v,s}(\tilde{q}^{1}(s),\tilde{q}^{2}(s))+\gamma\|v^{1}+v^{2}\|_{\infty}$
$\displaystyle+6\tau\log(A_{\max})+\mu.$

###### Proof of Lemma A.19.

  1. (1)

For any $v_{1},v_{2}\in\mathbb{R}^{|\mathcal{S}|}$ and $i\in\\{1,2\\}$, we
have for any $(s,a^{i},a^{-i})$ that

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

It follows that
$\|\mathcal{T}^{i}(v_{1})-\mathcal{T}^{i}(v_{2})\|_{\infty}\leq\gamma\|v_{1}-v_{2}\|_{\infty}$.
Since $\mathcal{T}^{i}(-v)=-\mathcal{T}^{-i}(v)$ for any
$v\in\mathbb{R}^{|\mathcal{S}|}$, we also have

$\displaystyle\|\mathcal{T}^{i}(v_{1})+\mathcal{T}^{-i}(v_{2})\|_{\infty}=\|\mathcal{T}^{i}(v_{1})-\mathcal{T}^{i}(-v_{2})\|_{\infty}\leq\gamma\|v_{1}+v_{2}\|_{\infty}.$

  2. (2)

For any $v_{1},v_{2}\in\mathbb{R}^{|\mathcal{S}|}$, we have

$\displaystyle\max_{\mu^{i}\in\Delta(\mathcal{\mathcal{A}}^{i})}\max_{\mu^{-i}\in\Delta(\mathcal{\mathcal{A}}^{-i})}\left|(\mu^{i})^{\top}(\mathcal{T}^{i}(v_{1})(s)-\mathcal{T}^{i}(v_{2})(s))\mu^{-i}\right|\leq\;$
$\displaystyle\left\|\mathcal{T}^{i}(v_{1})-\mathcal{T}^{i}(v_{2})\right\|_{\infty}$
$\displaystyle\leq\;$ $\displaystyle\gamma\|v_{1}-v_{2}\|_{\infty},$

where the last inequality follows from Part (1) of this lemma.

  3. (3)

We start by decomposing the term we want to bound as

$\displaystyle\left|\sum_{i=1,2}\max_{\mu^{i}\in\Delta(\mathcal{A}^{i})}(\mu^{i})^{\top}\mathcal{T}^{i}(v^{i})(s)\pi^{-i}(s)\right|=\;$
$\displaystyle\left|\sum_{i=1,2}\max_{\mu^{i}\in\Delta(\mathcal{A}^{i})}(\mu^{i})^{\top}(\mathcal{T}^{i}(v^{i})(s)\pi^{-i}(s)-\tilde{q}^{i}(s))\right|$
$\displaystyle+\left|\sum_{i=1,2}\max_{\mu^{i}\in\Delta(\mathcal{A}^{i})}(\mu^{i})^{\top}\tilde{q}^{i}(s)\right|.$
(56)

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

$\displaystyle\left|\sum_{i=1,2}\max_{\mu^{i}\in\Delta(\mathcal{A}^{i})}(\mu^{i})^{\top}(\mathcal{T}^{i}(v^{i})(s)\pi^{-i}(s)-\tilde{q}^{i}(s))\right|\leq\;$
$\displaystyle\sum_{i=1,2}\|\tilde{q}^{i}(s)-\mathcal{T}^{i}(v^{i})(s)\pi^{-i}(s)\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\frac{2\sqrt{2}}{\sqrt{\tau}}V_{v,s}^{1/2}(\tilde{q}^{1}(s),\tilde{q}^{2}(s))\sum_{i=1,2}\|\mathcal{T}^{i}(v^{i})(s)\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\frac{4\sqrt{2}A_{\max}}{\sqrt{\tau}(1-\gamma)}V^{1/2}_{v,s}(\tilde{q}^{1}(s),\tilde{q}^{2}(s))$
$\displaystyle\leq\;$
$\displaystyle\tau+\frac{8A_{\max}^{2}}{\tau^{2}(1-\gamma)^{2}}V_{v,s}(\tilde{q}^{1}(s),\tilde{q}^{2}(s)),$
(57)

where the last line follows from $a^{2}+b^{2}\geq 2ab$. For the second term on
the RHS of Eq. (56), we have for any
$\hat{\mu}^{1}\in\Delta(\mathcal{A}^{1})$,
$\hat{\mu}^{2}\in\Delta(\mathcal{A}^{2})$, and $s\in\mathcal{S}$ that

$\displaystyle\left|\sum_{i=1,2}\max_{\mu^{i}\in\Delta(\mathcal{A}^{i})}(\mu^{i})^{\top}\tilde{q}^{i}(s)\right|\leq\;$
$\displaystyle\sum_{i=1,2}\max_{\mu^{i}\in\Delta(\mathcal{A}^{i})}(\mu^{i}-\hat{\mu}^{i})^{\top}\tilde{q}^{i}(s)+\left|\sum_{i=1,2}(\hat{\mu}^{i})^{\top}\tilde{q}^{i}(s)\right|$
$\displaystyle\leq\;$
$\displaystyle\sum_{i=1,2}\max_{\mu^{i}\in\Delta(\mathcal{A}^{i})}\left\\{(\mu^{i}-\hat{\mu}^{i})^{\top}\tilde{q}^{i}(s)+\tau\nu(\mu^{i})-\tau\nu(\hat{\mu}^{i})\right\\}+2\tau\log(A_{\max})$
$\displaystyle+\left|\sum_{i=1,2}(\hat{\mu}^{i})^{\top}\tilde{q}^{i}(s)\right|.$
(58)

We next consider the last term on the RHS of the previous inequality. Observe
that

$\displaystyle\left|\sum_{i=1,2}(\hat{\mu}^{i})^{\top}\tilde{q}^{i}(s)\right|=\;$
$\displaystyle\left|\sum_{i=1,2}(\hat{\mu}^{i})^{\top}\left(\tilde{q}^{i}(s)-\mathcal{T}^{i}(v^{i})(s)\hat{\mu}^{-i}\right)\right|+\left|\sum_{i=1,2}(\hat{\mu}^{i})^{\top}\mathcal{T}^{i}(v^{i})(s)\hat{\mu}^{-i}\right|$
$\displaystyle\leq\;$
$\displaystyle\sum_{i=1,2}\|\hat{\mu}^{i}\|_{2}\|\tilde{q}^{i}(s)-\mathcal{T}^{i}(v^{i})(s)\hat{\mu}^{-i}\|_{2}+\gamma\|v^{1}+v^{2}\|_{\infty}$
(Part (2) of this lemma) $\displaystyle\leq\;$
$\displaystyle\sum_{i=1,2}\left(\frac{\mu\|\hat{\mu}^{i}\|_{2}^{2}}{2}+\frac{\|\tilde{q}^{i}(s)-\mathcal{T}^{i}(v^{i})(s)\hat{\mu}^{-i}\|_{2}^{2}}{2\mu}\right)+\gamma\|v^{1}+v^{2}\|_{\infty}$
($a^{2}+b^{2}\geq 2ab$) $\displaystyle\leq\;$
$\displaystyle\mu+\sum_{i=1,2}\frac{1}{2\mu}\|\tilde{q}^{i}(s)-\mathcal{T}^{i}(v^{i})(s)\hat{\mu}^{-i}\|_{2}^{2}+\gamma\|v^{1}+v^{2}\|_{\infty}.$

Substituting the previous inequality into Eq. (58), we have

$\displaystyle\left|\sum_{i=1,2}\max_{\mu^{i}\in\Delta(\mathcal{A}^{i})}(\mu^{i})^{\top}\tilde{q}^{i}(s)\right|$
$\displaystyle\leq\;$
$\displaystyle\sum_{i=1,2}\max_{\mu^{i}\in\Delta(\mathcal{A}^{i})}\left\\{(\mu^{i}-\hat{\mu}^{i})^{\top}\tilde{q}^{i}(s)+\tau\nu(\mu^{i})-\tau\nu(\hat{\mu}^{i})+\frac{1}{2\mu}\|\tilde{q}^{i}(s)-\mathcal{T}^{i}(v^{i})(s)\hat{\mu}^{-i}\|_{2}^{2}\right\\}$
$\displaystyle+\gamma\|v^{1}+v^{2}\|_{\infty}+2\tau\log(A_{\max})+\mu.$

Since the previous inequality holds for all
$\hat{\mu}^{1}\in\Delta(\mathcal{A}^{1})$ and
$\hat{\mu}^{2}\in\Delta(\mathcal{A}^{2})$, we have

$\displaystyle\left|\sum_{i=1,2}\max_{\mu^{i}\in\Delta(\mathcal{A}^{i})}(\mu^{i})^{\top}\tilde{q}^{i}(s)\right|$
$\displaystyle\leq\;$
$\displaystyle\sum_{i=1,2}\max_{\mu^{i}\in\Delta(\mathcal{A}^{i})}\min_{\hat{\mu}^{i}\in\Delta(\mathcal{A}^{i})}\left\\{(\mu^{i}-\hat{\mu}^{i})^{\top}\tilde{q}^{i}(s)+\tau\nu(\mu^{i})-\tau\nu(\hat{\mu}^{i})+\frac{1}{2\mu}\|\tilde{q}^{i}(s)-\mathcal{T}^{i}(v^{i})(s)\hat{\mu}^{-i}\|_{2}^{2}\right\\}$
$\displaystyle+\gamma\|v^{1}+v^{2}\|_{\infty}+2\tau\log(A_{\max})+\mu$
$\displaystyle=\;$ $\displaystyle
V_{v,s}(\tilde{q}^{1}(s),\tilde{q}^{2}(s))+\gamma\|v^{1}+v^{2}\|_{\infty}+2\tau\log(A_{\max})+\mu.$

Using the previous inequality and Eq. (57) together in Eq. (56), since
$A_{\max}\geq 2$ and $\tau\leq 1/(1-\gamma)$, we have

$\displaystyle\left|\sum_{i=1,2}\max_{\mu^{i}\in\Delta(\mathcal{A}^{i})}(\mu^{i})^{\top}\mathcal{T}^{i}(v^{i})(s)\pi^{-i}(s)\right|\leq\;$
$\displaystyle\frac{9A_{\max}^{2}}{\tau^{2}(1-\gamma)^{2}}V_{v,s}(\tilde{q}^{1}(s),\tilde{q}^{2}(s))+\gamma\|v^{1}+v^{2}\|_{\infty}$
$\displaystyle+6\tau\log(A_{\max})+\mu.$

∎