* Kempe et al. [2020] Kempe D, Yu S, Vorobeychik Y (2020) Inducing equilibria in networked public goods games through network structure modification. _arXiv preprint arXiv:2002.10627_ .
  * Lee and He [2019] Lee D, He N (2019) A unified switching system perspective and ode analysis of Q-learning algorithms. _arXiv preprint arXiv:1912.02270_ .
  * Lei and Shanbhag [2018] Lei J, Shanbhag UV (2018) Distributed variable sample-size gradient-response and best-response schemes for stochastic Nash equilibrium problems over graphs. _arXiv preprint arXiv:1811.11246_ .
  * Lei and Shanbhag [2020] Lei J, Shanbhag UV (2020) Asynchronous schemes for stochastic and misspecified potential games and nonconvex optimization. _Operations Research_ 68(6):1742–1766.
  * Lei et al. [2020] Lei J, Shanbhag UV, Pang JS, Sen S (2020) On synchronous, asynchronous, and randomized best-response schemes for stochastic Nash games. _Mathematics of Operations Research_ 45(1):157–190.
  * Leslie and Collins [2005] Leslie DS, Collins EJ (2005) Individual Q-learning in normal form games. _SIAM Journal on Control and Optimization_ 44(2):495–514.
  * Leslie et al. [2020] Leslie DS, Perkins S, Xu Z (2020) Best-response dynamics in zero-sum stochastic games. _Journal of Economic Theory_ 189:105095.
  * Li et al. [2020] Li G, Wei Y, Chi Y, Gu Y, Chen Y (2020) Sample complexity of asynchronous Q-learning: Sharper analysis and variance reduction. _Advances in Neural Information Processing Systems_ , volume 33, 7031–7043.
  * Lin et al. [2021] Lin Y, Qu G, Huang L, Wierman A (2021) Multi-agent reinforcement learning in stochastic networked systems. _Thirty-Fifth Conference on Neural Information Processing Systems_.
  * Littman [1994] Littman ML (1994) Markov games as a framework for multi-agent reinforcement learning. _Machine Learning Proceedings_ , 157–163 (Elsevier).
  * Littman [2001] Littman ML (2001) Friend-or-foe Q-learning in general-sum games. _Proceedings of the Eighteenth International Conference on Machine Learning_ , 322–328 (Morgan Kaufmann Publishers Inc.).
  * Liu et al. [2021] Liu Q, Yu T, Bai Y, Jin C (2021) A sharp analysis of model-based reinforcement learning with self-play. _International Conference on Machine Learning_ , 7001–7010 (PMLR).
  * Mao and Başar [2021] Mao W, Başar T (2021) Provably efficient reinforcement learning in decentralized general-sum Markov games. _arXiv preprint arXiv:2110.05682_ .
  * Maskin and Tirole [1988] Maskin E, Tirole J (1988) A theory of dynamic oligopoly, i: Overview and quantity competition with large fixed costs. _Econometrica: Journal of the Econometric Society_ 549–569.
  * Melo et al. [2008] Melo FS, Meyn SP, Ribeiro MI (2008) An analysis of reinforcement learning with function approximation. _Proceedings of the 25th International Conference on Machine Learning_ , 664–671.
  * Milchtaich [1996] Milchtaich I (1996) Congestion games with player-specific payoff functions. _Games and Economic Behavior_ 13(1):111–124.
  * Monderer and Shapley [1996] Monderer D, Shapley LS (1996) Potential games. _Games and Economic Behavior_ 14(1):124–143.
  * Nash et al. [1950] Nash JF, et al. (1950) Equilibrium points in $n$-person games. _Proceedings of the National Academy of Sciences_ 36(1):48–49.
  * Pang et al. [2017] Pang JS, Sen S, Shanbhag UV (2017) Two-stage non-cooperative games with risk-averse players. _Mathematical Programming_ 165(1):235–290.
  * Paulin et al. [2015] Paulin D, et al. (2015) Concentration inequalities for Markov chains by Marton couplings and spectral methods. _Electronic Journal of Probability_ 20\.
  * Qu and Wierman [2020] Qu G, Wierman A (2020) Finite-time analysis of asynchronous stochastic approximation and Q-learning. _Conference on Learning Theory_ , 3185–3205 (PMLR).
  * Qu et al. [2020] Qu G, Wierman A, Li N (2020) Scalable reinforcement learning of localized policies for multi-agent networked systems. _Learning for Dynamics and Control_ , 256–266 (PMLR).
  * Rosenthal [1973] Rosenthal RW (1973) A class of games possessing pure-strategy Nash equilibria. _International Journal of Game Theory_ 2(1):65–67.
  * Sayin et al. [2021] Sayin MO, Zhang K, Leslie DS, Başar T, Ozdaglar A (2021) Decentralized Q-learning in zero-sum Markov games. _arXiv preprint arXiv:2106.02748_ .
  * Sen et al. [1994] Sen S, Sekaran M, Hale J, et al. (1994) Learning to coordinate without sharing information. _AAAI_ , volume 94, 426–431.
  * Shapley [1953] Shapley LS (1953) Stochastic games. _Proceedings of the National Academy of Sciences_ 39(10):1095–1100.
  * Shoham et al. [2007] Shoham Y, Powers R, Grenager T (2007) If multi-agent learning is the answer, what is the question? _Artificial Intelligence_ 171(7):365–377.
  * Sidford et al. [2020] Sidford A, Wang M, Yang L, Ye Y (2020) Solving discounted stochastic two-player games with near-optimal time and sample complexity. _International Conference on Artificial Intelligence and Statistics_ , 2992–3002 (PMLR).
  * Song et al. [2021] Song Z, Mei S, Bai Y (2021) When can we learn general-sum Markov games with a large number of players sample-efficiently? _arXiv preprint arXiv:2110.04184_ .
  * Stern and Birge [2020] Stern M, Birge JR (2020) Dynamic learning in strategic pricing games. _Available at SSRN 3579123_ .
  * Stone and Veloso [2000] Stone P, Veloso M (2000) Multiagent systems: A survey from a machine learning perspective. _Autonomous Robots_ 8(3):345–383.
  * Sutton and Barto [2018] Sutton RS, Barto AG (2018) _Reinforcement Learning: An Introduction_ (MIT press).
  * Swenson et al. [2018] Swenson B, Murray R, Kar S (2018) On best-response dynamics in potential games. _SIAM Journal on Control and Optimization_ 56(4):2734–2767.
  * Syrgkanis [2010] Syrgkanis V (2010) The complexity of equilibria in cost sharing games. _International Workshop on Internet and Network Economics_ , 366–377 (Springer).
  * Tan [1993] Tan M (1993) Multi-agent reinforcement learning: Independent vs. cooperative agents. _International Conference on Machine Learning_ , 330–337.
  * Tian et al. [2020] Tian Y, Wang Y, Yu T, Sra S (2020) Provably efficient online agnostic learning in Markov games. _arXiv preprint arXiv:2010.15020_ .
  * Tsitsiklis [1994] Tsitsiklis JN (1994) Asynchronous stochastic approximation and Q-learning. _Machine Learning_ 16(3):185–202.
  * Wainwright [2019] Wainwright MJ (2019) Stochastic approximation with cone-contractive operators: Sharp $\ell_{\infty}$-bounds for Q-learning. _arXiv preprint arXiv:1905.06265_ .
  * Watkins and Dayan [1992] Watkins CJ, Dayan P (1992) Q-learning. _Machine Learning_ 8(3-4):279–292.
  * Wei et al. [2017] Wei CY, Hong YT, Lu CJ (2017) Online reinforcement learning in stochastic games. _Advances in Neural Information Processing Systems_ , 4987–4997.
  * Wei et al. [2020] Wei CY, Lee CW, Zhang M, Luo H (2020) Linear last-iterate convergence in constrained saddle-point optimization. _arXiv preprint arXiv:2006.09517_ .
  * Wei et al. [2021] Wei CY, Lee CW, Zhang M, Luo H (2021) Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive Markov games. _arXiv preprint arXiv:2102.04540_ .
  * Wu et al. [2021] Wu Y, Khodabakhsh A, Li B, Nikolova E, Pountourakis E (2021) Eliciting information with partial signals in repeated games. _arXiv preprint arXiv:2109.04343_ .
  * Xie et al. [2020] Xie Q, Chen Y, Wang Z, Yang Z (2020) Learning zero-sum simultaneous-move Markov games using function approximation and correlated equilibrium. _Conference on Learning Theory_ , 3674–3682 (PMLR).
  * Young [2004] Young HP (2004) _Strategic Learning and its Limits_ (OUP Oxford).
  * Yüksel and Başar [2013] Yüksel S, Başar T (2013) _Stochastic Networked Control Systems: Stabilization and Optimization Under Information Constraints_ (Springer Science & Business Media).
  * Zhang et al. [2020] Zhang K, Kakade SM, Başar T, Yang LF (2020) Model-based multi-agent RL in zero-sum Markov games with near-optimal sample complexity. _arXiv preprint arXiv:2007.07461_ .
  * Zhang et al. [2021] Zhang K, Yang Z, Başar T (2021) Multi-agent reinforcement learning: A selective overview of theories and algorithms. _Handbook of Reinforcement Learning and Control_ , 321–384 (Springer).

##  6 Proof of Theorem 2

We first introduce the following lemma, which is an application of the sample
complexity result on the convergence of $\theta$ for single agent Q-learning
(Chen et al. [13]).

###### Lemma 10

Fix any arbitrary $\pi_{k}\in\Pi$. For any $\epsilon\geq 0$ and
$0<\hat{\delta}<1$, we have that

$P\left[\big{|}\theta_{t_{k+1}}^{i}-\theta_{\bar{\pi}_{k}^{-i}}^{i}\big{|}_{\infty}\leq\epsilon,\
\forall i\in[N]\right]\geq 1-\hat{\delta},$

provided that the iteration number $T_{k}$ and the learning rates
$\eta_{t}^{i}$ obey

$\displaystyle\eta^{i}_{t}$
$\displaystyle=\eta^{i}\leq\frac{\epsilon^{2}\hat{\delta}\xi^{i}}{456N\left(1+\gamma^{i}+r_{\max}^{i}\right)^{2}(D^{i}+1)^{2}t_{{\rm
mix},k}^{i}(\eta^{i})},\quad\forall t=t_{k},\ldots,t_{k+1}-1,\forall i\in[N],$
(68a) $\displaystyle T_{k}$ $\displaystyle\geq t_{{\rm
mix},k}(\eta_{\min})+\frac{\log\frac{\epsilon^{2}\hat{\delta}}{2N(2D+1)^{2}}}{\log\left(1-\xi_{\min}\eta_{\min}/2\right)},$
(68b)

where $D=\max_{i}D^{i}$, $\eta_{\min}=\min_{i}\eta^{i}$, and
$\xi_{\min}=\min_{i}\xi^{i}$.

[Proof of Lemma 10] Note that in the $k$th exploration phase, agents adopt the
joint policy $\bar{\pi}_{k}$ as defined in (10). Under Assumptions 1, 2, 4,
and 5, Theorem 3.1 of Chen et al. [13] implies that for any agent $i$,

$\displaystyle\mathbb{E}\left[\left\|\theta_{t_{k+1}}^{i}-\theta_{\bar{\pi}_{k}^{-i}}^{i}\right\|^{2}_{2}\right]\leq\beta_{1}\left(1-\xi^{i}\eta_{t}^{i}/2\right)^{T_{k}-t_{{\rm
mix},k}^{i}(\eta_{t}^{i})}+2\beta_{2}\eta_{t}^{i}t_{{\rm
mix},k}^{i}(\eta_{t}^{i})/\xi^{i},$

where $\beta_{1}=(2D^{i}+1)^{2}$,
$\beta_{2}=114\left(1+\gamma^{i}+r_{\max}^{i}\right)^{2}(D^{i}+1)^{2}$, and
$\eta_{t}^{i}=\eta^{i}$ are such that
$\eta^{i}\leq\frac{\xi^{i}}{228\left(1+\gamma^{i}+r_{\max}^{i}\right)^{2}t_{{\rm
mix},k}^{i}(\eta^{i})}$.

For any given $\epsilon>0$ and $0<\delta_{0}<1$, let $\eta^{i}_{t}$ and
$T_{k}$ be such that

$\displaystyle\eta^{i}_{t}$
$\displaystyle=\eta^{i}\leq\frac{\epsilon^{2}\delta_{0}\xi^{i}}{456\left(1+\gamma^{i}+r_{\max}^{i}\right)^{2}(D^{i}+1)^{2}t_{{\rm
mix},k}^{i}(\eta^{i})},\quad\forall t=t_{k},\ldots,t_{k+1}-1$ (69a)
$\displaystyle T_{k}$ $\displaystyle\geq t_{{\rm
mix},k}^{i}(\eta^{i})+\frac{\log\frac{\epsilon^{2}\delta_{0}}{2(2D^{i}+1)^{2}}}{\log\left(1-\xi^{i}\eta^{i}/2\right)},\quad\forall
i\in[N].$ (69b)

Then, we have that

$\displaystyle\mathbb{E}\left[\left\|\theta_{t_{k+1}}^{i}-\theta_{\bar{\pi}_{k}^{-i}}^{i}\right\|^{2}_{2}\right]$
$\displaystyle\leq\beta_{1}\left(1-\xi^{i}\eta_{t}^{i}/2\right)^{T_{k}-t_{{\rm
mix},k}^{i}(\eta_{t}^{i})}+2\beta_{2}\eta_{t}^{i}t_{{\rm
mix},k}^{i}(\eta_{t}^{i})/\xi^{i}\leq\frac{\epsilon^{2}\delta_{0}}{2}+\frac{\epsilon^{2}\delta_{0}}{2}=\epsilon^{2}\delta_{0},\quad\forall
i\in[N].$

By Markov inequality, this further implies that

$\displaystyle
P\left[\left\|\theta_{t_{k+1}}^{i}-\theta_{\bar{\pi}_{k}^{-i}}^{i}\right\|_{2}^{2}\geq\epsilon^{2}\right]\leq\frac{\mathbb{E}\left[\left\|\theta_{t_{k+1}}^{i}-\theta_{\bar{\pi}_{k}^{-i}}^{i}\right\|^{2}_{2}\right]}{\epsilon^{2}}\leq{\delta_{0}},\quad\forall
i\in[N],$

which is equivalent to

$\displaystyle
P\left[\left\|\theta_{t_{k+1}}^{i}-\theta_{\bar{\pi}_{k}^{-i}}^{i}\right\|_{2}\geq\epsilon\right]\leq\frac{\mathbb{E}\left[\left\|\theta_{t_{k+1}}^{i}-\theta_{\bar{\pi}_{k}^{-i}}^{i}\right\|^{2}_{2}\right]}{\epsilon^{2}}\leq{\delta_{0}},\quad\forall
i\in[N].$

From the union bound,

$\displaystyle
P\left[\left\|\theta_{t_{k+1}}^{i}-\theta_{\bar{\pi}_{k}^{-i}}^{i}\right\|_{2}\geq\epsilon,\
\exists
i\in[N]\right]\leq\sum_{i\in[N]}P\left[\left\|\theta_{t_{k+1}}^{i}-\theta_{\bar{\pi}_{k}^{-i}}^{i}\right\|_{2}\geq\epsilon\right]\leq
N\delta_{0}.$

Therefore,

$\displaystyle
P\left[\left\|\theta_{t_{k+1}}^{i}-\theta_{\bar{\pi}_{k}^{-i}}^{i}\right\|_{2}\leq\epsilon,\
\forall i\in[N]\right]$ $\displaystyle\geq
1-P\left[\left\|\theta_{t_{k+1}}^{i}-\theta_{\bar{\pi}_{k}^{-i}}^{i}\right\|_{2}\geq\epsilon,\
\exists i\in[N]\right]\geq 1-N\delta_{0}.$

Furthermore, since
$\big{|}\theta_{t_{k+1}}^{i}-\theta_{\bar{\pi}_{k}^{-i}}^{i}\big{|}_{\infty}\leq\left\|\theta_{t_{k+1}}^{i}-\theta_{\bar{\pi}_{k}^{-i}}^{i}\right\|_{2}$,
we have that

$\displaystyle
P\left[\big{|}\theta_{t_{k+1}}^{i}-\theta_{\bar{\pi}_{k}^{-i}}^{i}\big{|}_{\infty}\leq\epsilon,\
\forall i\in[N]\right]\geq
P\left[\left\|\theta_{t_{k+1}}^{i}-\theta_{\bar{\pi}_{k}^{-i}}^{i}\right\|_{2}\leq\epsilon,\
\forall i\in[N]\right]\geq 1-N\delta_{0}.$

By taking $\hat{\delta}=N\delta_{0}$, $\eta^{i}_{t}$ as in (69a), and

$T_{k}\geq t_{{\rm
mix},k}(\eta_{\min})+\frac{\log\frac{\epsilon^{2}\hat{\delta}}{2N(2D+1)^{2}}}{\log\left(1-\xi_{\min}\eta_{\min}/2\right)}\geq
t_{{\rm
mix},k}^{i}(\eta^{i})+\frac{\log\frac{\epsilon^{2}\delta_{0}}{2(2D^{i}+1)^{2}}}{\log\left(1-\xi^{i}\eta^{i}/2\right)},\quad\forall
i\in[N],$

the proof is completed.

Lemma 10 bounds the approximation error of $\theta^{i}_{t_{k+1}}$ for each
agent. By noting that $|\phi^{i}|_{\infty}\leq\|\phi^{i}\|_{2}\leq 1$, Lemma
10 implies that for an arbitrary $\bar{\pi}_{k}$ as in (10) and for any
$\epsilon>0$ and $0<\hat{\delta}<1$,

$\displaystyle
P\left[\left|Q_{\theta_{t_{k+1}}^{i}}^{i}-Q^{i}_{\theta_{\bar{\pi}_{k}^{-i}}^{i}}\right|_{\infty}\leq\epsilon,\
\forall
i\in[N]\right]=P\left[\left|{\phi^{i}}^{\top}\theta_{t_{k+1}}^{i}-{\phi^{i}}^{\top}\theta_{\bar{\pi}_{k}^{-i}}^{i}\right|_{\infty}\leq\epsilon,\
\forall i\in[N]\right]\geq 1-\hat{\delta}$ (70)

when the same conditions (68) are satisfied.

Our next goal is to bound the approximation error of policy perturbation.
Recall the definition of the randomized policy in (10), and consider the joint
policies of all agents except $i$. With probability $\prod_{j\neq
i}(1-\rho^{j})$, all agents $j\neq i$ end up playing their baseline policies,
which results in
$\left|Q_{\theta_{\pi_{k}^{-i}}^{i}}^{i}-Q_{\theta_{\bar{\pi}_{k}^{-i}}^{i}}^{i}\right|_{\infty}=0$,
i.e. the approximation error of policy perturbation becomes zero in this case.
When not all agents play their baseline policies, let
$\varphi^{-i}\in\Delta^{-i}$ be some convex combination of the policies in
$\Delta^{-i}$ of the form where each agent $j\neq i$ either uses a baseline
policy $\pi^{j}\in\Pi^{j}$ or the uniform distribution. More precisely, let
$J$ denote the subset of agents choosing the baseline policies, and let

$\displaystyle\varphi^{-i}=\sum_{J\subset\\{1,\ldots,N\\}\setminus\\{i\\}}a_{J}\varphi_{J}^{-i},$
(71)

where $a_{J}:=\frac{\prod_{j\in J}(1-\rho^{j})\prod_{j\notin
J\cup\\{i\\}}\rho^{j}}{1-\prod_{j\neq i}(1-\rho^{j})}$ and
$\varphi_{J}\in\Delta^{-i}$ is such that $\varphi_{J}^{j}=\pi^{j}$ for $j\in
J$ and $\varphi_{J}^{j}=\nu^{j}$ for $j\notin J\cup\\{i\\}$. Denote by
$\bar{\Delta}^{-i}\subset\Delta^{-i}$ the set of all policies in the form of
(71). Note that $\bar{\Delta}^{-i}$ is a finite set. We then define

$\displaystyle\widetilde{\Gamma}:=\max_{\left(\pi^{-i},\varphi^{-i}\right)\in\Pi^{-i}\times\bar{\Delta}^{-i}}\left|\mathcal{T}_{\pi^{-i}}^{i}\Big{(}Q_{\theta_{\pi^{-i}}^{i}}^{i}\Big{)}-\mathcal{T}_{\varphi^{-i}}^{i}\Big{(}Q_{\theta_{\pi^{-i}}^{i}}^{i}\Big{)}\right|_{\infty}.$
(72)

We next have the following lemma on the approximation error due to policy
perturbation.

###### Lemma 11

Fix any arbitrary $\pi_{k}\in\Pi$. For any $\tilde{\epsilon}>0$, if $\rho^{i}$
satisfies

$\displaystyle\rho^{i}\leq
1-\left(1-\frac{\tilde{\epsilon}(1-\bar{\gamma})}{\widetilde{\Gamma}}\right)^{\frac{1}{N-1}},\quad\forall
i\in[N],$ (73)

then, we have that

$\left|Q_{\theta_{\pi_{k}^{-i}}^{i}}^{i}-Q_{\theta_{\bar{\pi}_{k}^{-i}}^{i}}^{i}\right|_{\infty}=\left|{\phi^{i}}^{\top}\theta^{i}_{\pi_{k}^{-i}}-{\phi^{i}}^{\top}\theta^{i}_{\bar{\pi}_{k}^{-i}}\right|_{\infty}\leq\tilde{\epsilon}+\frac{2b}{1-\bar{\gamma}},\quad\forall
i\in[N],k\in[K].$

[Proof of Lemma 11] First note that, for all $i\in[N]$ and $k\in[K]$,

$\displaystyle\left|Q_{\theta_{\pi_{k}^{-i}}^{i}}^{i}-Q_{\theta_{\bar{\pi}_{k}^{-i}}^{i}}^{i}\right|_{\infty}$
$\displaystyle=\left|Q_{\theta_{\pi_{k}^{-i}}^{i}}^{i}-\mathcal{T}_{\pi_{k}^{-i}}^{i}\Big{(}Q_{\theta_{\pi_{k}^{-i}}^{i}}^{i}\Big{)}+\mathcal{T}_{\pi_{k}^{-i}}^{i}\Big{(}Q_{\theta_{\pi_{k}^{-i}}^{i}}^{i}\Big{)}-\mathcal{T}_{\bar{\pi}_{k}^{-i}}^{i}\Big{(}Q_{\theta_{\bar{\pi}_{k}^{-i}}^{i}}^{i}\Big{)}+\mathcal{T}_{\bar{\pi}_{k}^{-i}}^{i}\Big{(}Q_{\theta_{\bar{\pi}_{k}^{-i}}^{i}}^{i}\Big{)}-Q_{\theta_{\bar{\pi}_{k}^{-i}}^{i}}^{i}\right|_{\infty}$
$\displaystyle=\left|Q_{\theta_{\pi_{k}^{-i}}^{i}}^{i}-\mathcal{T}_{\pi_{k}^{-i}}^{i}\Big{(}Q_{\theta_{\pi_{k}^{-i}}^{i}}^{i}\Big{)}\right|_{\infty}+\left|\mathcal{T}_{\pi_{k}^{-i}}^{i}\Big{(}Q_{\theta_{\pi_{k}^{-i}}^{i}}^{i}\Big{)}-\mathcal{T}_{\bar{\pi}_{k}^{-i}}^{i}\Big{(}Q_{\theta_{\bar{\pi}_{k}^{-i}}^{i}}^{i}\Big{)}\right|_{\infty}+\left|\mathcal{T}_{\bar{\pi}_{k}^{-i}}^{i}\Big{(}Q_{\theta_{\bar{\pi}_{k}^{-i}}^{i}}^{i}\Big{)}-Q_{\theta_{\bar{\pi}_{k}^{-i}}^{i}}^{i}\right|_{\infty}$
$\displaystyle\leq
b+\left|\mathcal{T}_{\pi_{k}^{-i}}^{i}\Big{(}Q_{\theta_{\pi_{k}^{-i}}^{i}}^{i}\Big{)}-\mathcal{T}_{\bar{\pi}_{k}^{-i}}^{i}\Big{(}Q_{\theta_{\bar{\pi}_{k}^{-i}}^{i}}^{i}\Big{)}\right|_{\infty}+b$
$\displaystyle\leq\left|\mathcal{T}_{\pi_{k}^{-i}}^{i}\Big{(}Q_{\theta_{\pi_{k}^{-i}}^{i}}^{i}\Big{)}-\mathcal{T}_{\bar{\pi}_{k}^{-i}}^{i}\Big{(}Q_{\theta_{{\pi}_{k}^{-i}}^{i}}^{i}\Big{)}\right|_{\infty}+\left|\mathcal{T}_{\bar{\pi}_{k}^{-i}}^{i}\Big{(}Q_{\theta_{\pi_{k}^{-i}}^{i}}^{i}\Big{)}-\mathcal{T}_{\bar{\pi}_{k}^{-i}}^{i}\Big{(}Q_{\theta_{\bar{\pi}_{k}^{-i}}^{i}}^{i}\Big{)}\right|_{\infty}+2b.$
(74)

By definition of $\bar{\pi}_{k}^{-i}$, we have that
$P\left[\bar{\pi}_{k}^{-i}=\pi_{k}^{-i}\right]=\prod_{j\neq i}(1-\rho^{j})$.
With probability $1-\prod_{j\neq i}(1-\rho^{j})$,
$\bar{\pi}_{k}^{-i}\neq\pi_{k}^{-i}$ and
$\bar{\pi}_{k}^{-i}\in\bar{\Delta}^{-i}$. Thus, the first term of (74) can be
bounded by

$\displaystyle\left|\mathcal{T}_{\pi_{k}^{-i}}^{i}\Big{(}Q_{\theta_{\pi_{k}^{-i}}^{i}}^{i}\Big{)}-\mathcal{T}_{\bar{\pi}_{k}^{-i}}^{i}\Big{(}Q_{\theta_{{\pi}_{k}^{-i}}^{i}}^{i}\Big{)}\right|_{\infty}\leq\left(1-\prod_{j\neq
i}(1-\rho^{j})\right)\times\left|\mathcal{T}_{\pi_{k}^{-i}}^{i}\Big{(}Q_{\theta_{\pi_{k}^{-i}}^{i}}^{i}\Big{)}-\mathcal{T}_{\varphi_{k}^{-i}}^{i}\Big{(}Q_{\theta_{\pi_{k}^{-i}}^{i}}^{i}\Big{)}\right|_{\infty},$
(75)

for some $\phi_{k}^{-i}\in\bar{\Delta}^{-i}$. On the other hand, by the
contraction mapping of the Bellman operator, we have that

$\displaystyle\left|\mathcal{T}_{\bar{\pi}_{k}^{-i}}^{i}\Big{(}Q_{\theta_{\pi_{k}^{-i}}^{i}}^{i}\Big{)}-\mathcal{T}_{\bar{\pi}_{k}^{-i}}^{i}\Big{(}Q_{\theta_{\bar{\pi}_{k}^{-i}}^{i}}^{i}\Big{)}\right|_{\infty}\leq\gamma^{i}\left|Q_{\theta_{\pi_{k}^{-i}}^{i}}^{i}-Q_{\theta_{\bar{\pi}_{k}^{-i}}^{i}}^{i}\right|_{\infty}.$
(76)

Substituting (75) and (76) back into (74), we have that

$\displaystyle\left|Q_{\theta^{i}_{\pi_{k}^{-i}}}^{i}-Q_{\theta^{i}_{\bar{\pi}_{k}^{-i}}}^{i}\right|_{\infty}$
$\displaystyle\leq\left(1-\prod_{j\neq
i}(1-\rho^{j})\right)\times\left|\mathcal{T}_{\pi_{k}^{-i}}^{i}\Big{(}Q_{\theta_{\pi_{k}^{-i}}^{i}}^{i}\Big{)}-\mathcal{T}_{\varphi_{k}^{-i}}^{i}\Big{(}Q_{\theta_{\pi_{k}^{-i}}^{i}}^{i}\Big{)}\right|_{\infty}+\gamma^{i}\left|Q_{\theta_{\pi_{k}^{-i}}^{i}}^{i}-Q_{\theta_{\bar{\pi}_{k}^{-i}}^{i}}^{i}\right|_{\infty}+2b$
$\displaystyle\leq\left(1-\prod_{j\neq
i}(1-\rho^{j})\right)\widetilde{\Gamma}+\gamma^{i}\left|Q_{\theta_{\pi_{k}^{-i}}^{i}}^{i}-Q_{\theta_{\bar{\pi}_{k}^{-i}}^{i}}^{i}\right|_{\infty}+2b,$

which implies that

$\displaystyle\left|Q_{\theta^{i}_{\pi_{k}^{-i}}}^{i}-Q_{\theta^{i}_{\bar{\pi}_{k}^{-i}}}^{i}\right|_{\infty}$
$\displaystyle\leq\frac{\left(1-\prod_{j\neq
i}(1-\rho^{j})\right)\widetilde{\Gamma}+2b}{1-\gamma^{i}}\leq\frac{\left(1-\prod_{j\neq
i}(1-\rho^{j})\right)\widetilde{\Gamma}+2b}{1-\bar{\gamma}}.$

If for all $i\in[N]$, $\rho^{i}\leq
1-\left(1-\frac{\tilde{\epsilon}(1-\bar{\gamma})}{\widetilde{\Gamma}}\right)^{\frac{1}{N-1}}$,
then, we have that
$1-\rho^{j}\geq\left(1-\frac{\tilde{\epsilon}(1-\bar{\gamma})}{\widetilde{\Gamma}}\right)^{\frac{1}{N-1}}$,
which implies that $\prod_{j\neq i}(1-\rho^{j})\geq
1-\frac{\tilde{\epsilon}(1-\bar{\gamma})}{\widetilde{\Gamma}}$, and thus

$\displaystyle\left|Q_{\theta^{i}_{\pi_{k}^{-i}}}^{i}-Q_{\theta^{i}_{\bar{\pi}_{k}^{-i}}}^{i}\right|_{\infty}\leq\frac{\left(1-\prod_{j\neq
i}(1-\rho^{j})\right)\widetilde{\Gamma}+2b}{1-\bar{\gamma}}\leq\tilde{\epsilon}+\frac{2b}{1-\bar{\gamma}}.$

The above holds for all $i\in[N]$ and $k\in[K]$, which completes the proof.

Recall from (64) that $\bar{\zeta}_{\theta}$ is the minimum separation of
agents’ optimal linear approximated Q-factors. By Assumption 6, we have that
$\bar{\zeta}_{\theta}>\frac{8b}{1-\bar{\gamma}}$. We consider
$\bar{\zeta}_{\theta}$ as an upper bound on $\zeta^{i}_{\theta}$ for all $i$.
We next define the following random event for any arbitrary $\pi_{k}\in\Pi$:

$\displaystyle\widetilde{E}_{k}:=\left\\{\omega\in\Omega:\left|Q_{\theta^{i}_{t_{k+1}}}^{i}-Q_{\theta^{i}_{\pi_{k}^{-i}}}^{i}\right|_{\infty}<\frac{1}{4}\min\\{\zeta^{i}_{\theta},\bar{\zeta}_{\theta}-\zeta^{i}_{\theta}\\},\forall
i\right\\}.$

With this definition of $\widetilde{E}_{k}$, we show that, if
$\widetilde{E}_{k}$ is not empty and $\pi_{k}\in\widetilde{\Pi}_{\rm eq}$,
then $\pi_{k+1}=\pi_{k}$ with probability $1$.

###### Lemma 12

Given any $\pi_{k}\in\Pi$ and the corresponding $\widetilde{E}_{k}$, for all
$k$, we have that

$P\left[\pi_{k+1}=\pi_{k}\mid\widetilde{E}_{k},\
\pi_{k}\in\widetilde{\Pi}_{\rm eq}\right]=1.$

[Proof of Lemma 12] Let
$\hat{a}^{i*}:=\argmax_{\hat{a}^{i}}Q^{i}_{t_{k+1}}\left(s,\hat{a}^{i}\right)$.
Then, conditioned on $E_{k}$ and $\pi_{k}\in\widetilde{\Pi}_{\rm eq}$, we have
that

$\displaystyle\qquad\max_{\hat{a}^{i}}Q^{i}_{\theta^{i}_{t_{k+1}}}\left(s,\hat{a}^{i}\right)-Q^{i}_{\theta^{i}_{t_{k+1}}}\left(s,\pi_{k}^{i}(s)\right)$
$\displaystyle=Q^{i}_{\theta^{i}_{t_{k+1}}}\left(s,\hat{a}^{i*}\right)-Q^{i}_{\theta^{i}_{t_{k+1}}}\left(s,\pi_{k}^{i}(s)\right)$
$\displaystyle=\left[Q^{i}_{\theta^{i}_{t_{k+1}}}\left(s,\hat{a}^{i*}\right)-Q^{i}_{\theta^{i}_{\pi_{k}^{-i}}}\left(s,\pi_{k}^{i}(s)\right)\right]+\left[Q^{i}_{\theta^{i}_{\pi_{k}^{-i}}}\left(s,\pi_{k}^{i}(s)\right)-Q^{i}_{\theta^{i}_{t_{k+1}}}\left(s,\pi_{k}^{i}(s)\right)\right]$
$\displaystyle<Q^{i}_{\theta^{i}_{t_{k+1}}}\left(s,\hat{a}^{i*}\right)-Q^{i}_{\theta^{i}_{\pi_{k}^{-i}}}\left(s,\pi_{k}^{i}(s)\right)+\frac{1}{4}\min\left\\{\zeta^{i}_{\theta},\bar{\zeta}_{\theta}-\zeta^{i}_{\theta}\right\\}$
$\displaystyle<\left[Q^{i}_{\theta^{i}_{t_{k+1}}}\left(s,\hat{a}^{i*}\right)-Q^{i}_{\theta^{i}_{\pi_{k}^{-i}}}\left(s,\hat{a}^{i*}\right)\right]+\left[Q^{i}_{\theta^{i}_{\pi_{k}^{-i}}}\left(s,\hat{a}^{i*}\right)-Q^{i}_{\theta^{i}_{\pi_{k}^{-i}}}\left(s,\pi_{k}^{i}(s)\right)\right]+\frac{1}{4}\min\left\\{\zeta^{i}_{\theta},\bar{\zeta}_{\theta}-\zeta^{i}_{\theta}\right\\}$
$\displaystyle<\frac{1}{4}\min\left\\{\zeta^{i}_{\theta},\bar{\zeta}_{\theta}-\zeta^{i}_{\theta}\right\\}+\frac{1}{4}\min\left\\{\zeta^{i}_{\theta},\bar{\zeta}_{\theta}-\zeta^{i}_{\theta}\right\\}$
$\displaystyle\leq\frac{1}{2}\min\left\\{\zeta^{i}_{\theta},\bar{\zeta}_{\theta}-\zeta^{i}_{\theta}\right\\},$

where the second-to-last inequality follows since
$Q^{i}_{\theta^{i}_{\pi_{k}^{-i}}}\left(s,\hat{a}^{i*}\right)-Q^{i}_{\theta^{i}_{\pi_{k}^{-i}}}\left(s,\pi_{k}^{i}(s)\right)<0$,
which follows from $\pi_{k}\in\widetilde{\Pi}_{\rm eq}$. It follows that
$Q^{i}_{\theta^{i}_{t_{k+1}}}\left(s,\pi_{k}^{i}(s)\right)\geq\max_{\hat{a}^{i}}Q^{i}_{\theta^{i}_{t_{k+1}}}\left(s,\hat{a}^{i}\right)-\frac{1}{2}\zeta^{i}_{\theta}$
for all $i$. Then, by Algorithm 2 (lines 10-12), we have that
$\pi_{k+1}=\pi_{k}$ with probability $1$. Recall that $\widetilde{L}$ is the
maximum length of the shortest strict best reply path from any policy to a
linear approximated equilibrium policy. Our next lemma lower bounds the
conditional probability of $\pi_{k+L}$ being a linear approximated equilibrium
policy, given that $\pi_{k}$ is not a linear approximated equilibrium policy
and given $\widetilde{E}_{k},\ldots,\widetilde{E}_{k+\widetilde{L}-1}$.

###### Lemma 13

Let

$\displaystyle\tilde{p}:=\left(\min_{j\in\\{1,\ldots,N\\}}\left\\{\frac{1-\lambda^{j}}{\left|\Pi^{j}\right|}\cdot\prod_{i\neq
j}\lambda^{i}\right\\}\right)^{\widetilde{L}}=\hat{p}^{\widetilde{L}/L}.$ (77)

We have that

$\displaystyle P\left[\pi_{k+\widetilde{L}}\in\widetilde{\Pi}_{\rm eq}\
\big{|}\
\widetilde{E}_{k},\dots,\widetilde{E}_{k+\widetilde{L}-1},\pi_{k}\not\in\widetilde{\Pi}_{\rm
eq}\right]\geq\tilde{p}.$ (78)

[Proof of Lemma 13] The proof is similar to that of Lemma 5. Consider some
$\pi_{k}\notin\widetilde{\Pi}_{\rm eq}$; there must exist at least one agent,
say $i$, whose policy $\pi^{i}_{k}$ is not the best reply to $\pi_{k}^{-i}$,
i.e., $\pi^{i}_{k}\notin\widetilde{\Pi}^{i}_{\pi_{k}^{-i}}$. In this case, we
claim that $\pi_{k}^{i}\notin\widetilde{\Pi}^{i}_{k+1}$, where
$\widetilde{\Pi}^{i}_{k+1}$ is as defined in Algorithm 2 (line 10). In other
words, the “else” statement in Algorithm 2 (line 14) will be executed. To see
this, it suffices to show that
$\phi_{t_{k+1}}^{i}(s,\pi_{k}^{i}(s))^{\top}\theta^{i}_{t_{k+1}}<\max_{a^{i}\in\mathcal{A}^{i}}\phi_{t_{k+1}}^{i}(s,a^{i})^{\top}\theta^{i}_{t_{k+1}}-\frac{1}{2}\zeta^{i}_{\theta}$,
for some $s\in\mathcal{S}$. Conditioned on $\widetilde{E}_{k}$, we have that

$Q^{i}_{\theta^{i}_{\pi_{k}^{-i}}}(s,a^{i})-\frac{1}{4}\min\\{\zeta^{i}_{\theta},\bar{\zeta}_{\theta}-\zeta^{i}_{\theta}\\}<Q^{i}_{\theta^{i}_{t_{k+1}}}(s,a^{i})<Q^{i}_{\theta^{i}_{\pi_{k}^{-i}}}(s,a^{i})+\frac{1}{4}\min\\{\zeta^{i}_{\theta},\bar{\zeta}_{\theta}-\zeta^{i}_{\theta}\\},$

i.e., $Q^{i}_{\theta^{i}_{t_{k+1}}}(s,a^{i})$ lies within a distance of
$\frac{1}{4}\min\\{\zeta^{i}_{\theta},\bar{\zeta}_{\theta}-\zeta^{i}_{\theta}\\}$
to $Q^{i}_{\theta^{i}_{\pi_{k}^{-i}}}(s,a^{i})$. Moreover, we note that
$\frac{1}{4}\min\\{\zeta^{i}_{\theta},\bar{\zeta}_{\theta}-\zeta^{i}_{\theta}\\}\leq\frac{1}{8}\bar{\zeta}_{\theta}$.
Recall that
$\\{Q^{i}_{\theta^{i}_{\pi_{k}^{-i}}}(s,a^{i}):a^{i}\in\mathcal{A}^{i}\\}$ are
dispersed with spacing being at least $\bar{\zeta}_{\theta}$, where
$\bar{\zeta}_{\theta}$ is as defined in (64) as the minimum separation between
the approximated $Q$-factors. Thus, it follows that the possible ranges of
$Q^{i}_{\theta^{i}_{t_{k+1}}}(s,a^{i})$ for all $a^{i}\in\mathcal{A}^{i}$ are
mutually exclusive, which implies that the $\tau$-th best action under
$Q^{i}_{\theta^{i}_{\pi_{k}^{-i}}}$ is identical to that under
$Q^{i}_{\theta^{i}_{t_{k+1}}}$, i.e.,

$\argmax_{a^{i}\in\mathcal{A}^{i}}\Big{(}Q^{i}_{\theta^{i}_{\pi_{k}^{-i}}}(s,a^{i})\Big{)}_{(\tau)}=\argmax_{a^{i}\in\mathcal{A}^{i}}\Big{(}Q^{i}_{\theta^{i}_{t_{k+1}}}(s,a^{i})\Big{)}_{(\tau)},$

where $(\cdot)_{(\tau)}$ represents the $\tau$-th largest value. For instance,
when $\tau=1$, we have that
$\argmax_{a^{i}\in\mathcal{A}^{i}}Q^{i}_{\theta^{i}_{\pi_{k}^{-i}}}(s,a^{i})=\argmax_{a^{i}\in\mathcal{A}^{i}}Q^{i}_{\theta^{i}_{t_{k+1}}}(s,a^{i})$,
which are denoted by $a^{i*}_{\theta^{i}_{\pi_{k}^{-i}}}(s)$ and
$a^{i*}_{\theta^{i}_{t_{k+1}}}(s)$, respectively.

Since $\pi^{i}_{k}\notin\widetilde{\Pi}^{i}_{\pi_{k}^{-i}}$, it follows that
$\pi^{i}_{k}(s)\neq\argmax_{a^{i}\in\mathcal{A}^{i}}Q^{i}_{\theta^{i}_{\pi_{k}^{-i}}}(s,a^{i})=:a^{i*}_{\theta^{i}_{\pi_{k}^{-1}}}(s)$
for some $s\in\mathcal{S}$. Then, we have that

$\displaystyle\max_{a^{i}\in\mathcal{A}^{i}}Q_{\theta^{i}_{t_{k+1}}}^{i}(s,a^{i})-Q_{\theta^{i}_{t_{k+1}}}^{i}(s,\pi^{i}_{k}(s))$
$\displaystyle>\left(\max_{a^{i}\in\mathcal{A}^{i}}Q_{\theta^{i}_{\pi_{k}^{-i}}}^{i}(s,a^{i})-\frac{1}{8}\bar{\zeta}_{\theta}\right)-\left(Q_{\theta^{i}_{\pi_{k}^{-i}}}^{i}(s,\pi^{i}_{k}(s))+\frac{1}{8}\bar{\zeta}_{\theta}\right)$
$\displaystyle=\left(Q_{\theta^{i}_{\pi_{k}^{-i}}}^{i}\Big{(}s,a^{i*}_{\theta^{i}_{\pi_{k}^{-i}}}(s)\Big{)}-Q_{\theta^{i}_{\pi_{k}^{-i}}}^{i}(s,\pi^{i}_{k}(s))\right)-\frac{1}{4}\bar{\zeta}_{\theta}$
$\displaystyle\geq\bar{\zeta}_{\theta}-\frac{1}{4}\bar{\zeta}_{\theta}=\frac{3}{4}\bar{\zeta}_{\theta}\geq\frac{3}{4}\zeta^{i}_{\theta}>\frac{1}{2}\zeta^{i}_{\theta}$

as desired. Now, we are ready to prove the statement.

Let $l$ be the length of the shortest strict best reply path from $\pi_{k}$ to
a linear approximated equilibrium policy. Then, $l\leq\widetilde{L}$. Let the
sequence of policies along the path be $\pi_{0},\pi_{1},\ldots,\pi_{l}$, with
$\pi_{0}=\pi_{k}\notin\widetilde{\Pi}_{\rm eq}$ and
$\pi_{l}\in\widetilde{\Pi}_{\rm eq}$. Further, let $i_{1},\ldots,i_{l}$ be the
agent that changes its policy at each update, i.e., $\pi_{n-1}$ and $\pi_{n}$
differ only at agent $i_{n}$, for all $n=1,\ldots,l$. Then, we use the two
probabilities in the policy update rule in Algorithm 2 (line 14) to yield

$\displaystyle\quad P\left[\pi_{k+\widetilde{L}}\in\widetilde{\Pi}{\rm eq}\
\big{|}\ E_{k},\dots,E_{k+\widetilde{L}-1},\pi_{k}\not\in\widetilde{\Pi}_{\rm
eq}\right]\geq P\left[\pi_{k+\widetilde{L}}=\pi_{l}\ \big{|}\
E_{k},\dots,E_{k+\widetilde{L}-1},\pi_{k}\not\in\widetilde{\Pi}_{\rm
eq}\right]$ $\displaystyle\geq
P\left[\pi_{k+1}=\pi_{1},\pi_{k+2}=\pi_{2},\ldots,\pi_{k+l}=\pi_{l},\pi_{k+l+1}=\cdots=\pi_{k+\widetilde{L}}=\pi_{l}\
\big{|}\ E_{k},\dots,E_{k+\widetilde{L}-1},\pi_{k}\not\in\widetilde{\Pi}_{\rm
eq}\right]$ $\displaystyle\geq P\left[\pi_{k+1}=\pi_{1}\ \big{|}\
E_{k},\dots,E_{k+\widetilde{L}-1},\pi_{k}=\pi_{0}\right]\cdot
P\left[\pi_{k+2}=\pi_{2}\ \big{|}\
E_{k},\dots,E_{k+\widetilde{L}-1},\pi_{k}=\pi_{0},\pi_{k+1}=\pi_{1}\right]$
$\displaystyle\quad\cdot P\left[\pi_{k+3}=\pi_{3}\ \big{|}\
E_{k},\dots,E_{k+\widetilde{L}-1},\pi_{k}=\pi_{0},\pi_{k+1}=\pi_{1},\pi_{k+2}=\pi_{2}\right]\cdot\cdots$
$\displaystyle\quad\cdot P\left[\pi_{k+l}=\pi_{l}\ \big{|}\
E_{k},\dots,E_{k+\widetilde{L}-1},\pi_{k}=\pi_{0},\pi_{k+1}=\pi_{1},\ldots,\pi_{k+l-1}=\pi_{l-1}\right]$
$\displaystyle\quad\cdot P\left[\pi_{k+l+1}=\pi_{l}\ \big{|}\
E_{k},\dots,E_{k+\widetilde{L}-1},\pi_{k}=\pi_{0},\pi_{k+1}=\pi_{1},\ldots,\pi_{k+l}=\pi_{l}\right]\cdot\cdots$
$\displaystyle\quad\cdot P\left[\pi_{k+\widetilde{L}}=\pi_{l}\ \big{|}\
E_{k},\dots,E_{k+\widetilde{L}-1},\pi_{k}=\pi_{0},\pi_{k+1}=\pi_{1},\ldots,\pi_{k+l}=\pi_{l},\ldots,\pi_{k+\widetilde{L}-1}=\pi_{l}\right]$
$\displaystyle\geq\prod_{j\in\\{i_{1},\ldots,i_{l}\\}}\left(\frac{1-\lambda^{j}}{\left|\Pi^{j}\right|}\cdot\prod_{i\neq
j}\lambda^{i}\right)\geq\left(\min_{j\in\\{1,\ldots,N\\}}\left\\{\frac{1-\lambda^{j}}{\left|\Pi^{j}\right|}\cdot\prod_{i\neq
j}\lambda^{i}\right\\}\right)^{l}\geq\left(\min_{j\in\\{1,\ldots,N\\}}\left\\{\frac{1-\lambda^{j}}{\left|\Pi^{j}\right|}\cdot\prod_{i\neq
j}\lambda^{i}\right\\}\right)^{\widetilde{L}},$

where we have used the fact from Lemma 12: given
$\pi_{l}\in\widetilde{\Pi}_{\rm eq}$ and the events
$E_{k},\ldots,E_{k+\widetilde{L}-1}$, the conditional probability that
$\pi_{s}\in\widetilde{\Pi}_{\rm eq}$ is $1$ for all $s\geq l$.

We will then bound
$P\left[\widetilde{E}_{k},\ldots,\widetilde{E}_{k+\widetilde{L}-1}\right]$.
Before doing that, we first look at $P[\widetilde{E}_{k}]$. We would like
$P[\widetilde{E}_{k}]$ to be as large as possible. Note that
$\frac{1}{4}\min\\{\zeta^{i}_{\theta},\bar{\zeta}_{\theta}-\zeta^{i}_{\theta}\\}\leq\frac{1}{8}\bar{\zeta}_{\theta}$,
with equality holding when
$\zeta^{i}_{\theta}=\frac{1}{2}\bar{\zeta}_{\theta}$. We next have the
following lemma.

###### Lemma 14

Let $\zeta^{i}_{\theta}=\frac{\bar{\zeta}_{\theta}}{2}$ for all $i\in[N]$. Fix
an arbitrary $\pi_{k}\in\Pi$. For any $0<\hat{\delta}<1$, we have that

$P\left[\widetilde{E}_{k}\right]\geq 1-\hat{\delta},$

provided that $\rho^{i}\leq
1-\left(1-\frac{\left(\bar{\zeta}_{\theta}/8-\epsilon\right)(1-\bar{\gamma})-2b}{\widetilde{\Gamma}}\right)^{\frac{1}{N-1}}$,
and $T_{k}$ and $\eta_{t}^{i}$ satisfy (68), where $\epsilon$ can take any
value in
$0<\epsilon<\min\left\\{\frac{\bar{\zeta}_{\theta}}{8}-\frac{2b}{1-\bar{\gamma}},\frac{1}{1-{\gamma}_{\min}}\right\\}$.

[Proof of Lemma 14] A direct implication of Lemma 10 with (70) and Lemma 11 is
that when $T_{k}$ and $\eta_{t}^{i}$ satisfy (68), and $\rho^{i}$ satisfies
(73), then, by triangle inequality, we have that

$\displaystyle
P\left[\left|Q^{i}_{\theta^{i}_{t_{k+1}}}-Q^{i}_{\theta^{i}_{\pi_{k}^{-i}}}\right|_{\infty}\leq\epsilon+\tilde{\epsilon}+\frac{2b}{1-\bar{\gamma}},\quad\forall
i\in[N]\right]\geq 1-\hat{\delta}.$ (79)

The lemma then follows by taking
$\tilde{\epsilon}=\frac{1}{8}\bar{\zeta}_{\theta}-\epsilon-\frac{2b}{1-\bar{\gamma}}$.
We then have the following lemma which bounds
$P\left[\widetilde{E}_{k},\ldots,\widetilde{E}_{k+\widetilde{L}-1}\right]$.

###### Lemma 15

For any arbitrary sequence of joint policies
$\pi_{k},\ldots,\pi_{k+\widetilde{L}-1}\in\Pi$, and for any
$0<\tilde{\delta}<1$, we have that

$\displaystyle
P\left[\widetilde{E}_{k},\ldots,\widetilde{E}_{k+\widetilde{L}-1}\right]\geq
1-\tilde{\delta},$

provided that for all $i\in[N]$ and for all
$\hat{k}\in\\{k,\ldots,k+\widetilde{L}-1\\}$,

$\displaystyle\eta^{i}_{t}$
$\displaystyle=\eta^{i}\leq\frac{\epsilon^{2}\tilde{\delta}\xi^{i}}{456N\widetilde{L}\left(1+\gamma^{i}+r_{\max}^{i}\right)^{2}(D^{i}+1)^{2}t_{{\rm
mix},k}^{i}(\eta^{i})},\quad\forall
t=t_{\hat{k}},\ldots,t_{\hat{k}+1}-1,\forall i\in[N],$ (80a) $\displaystyle
T_{\hat{k}}$ $\displaystyle\geq t_{{\rm
mix},k}(\eta_{\min})+\frac{\log\frac{\epsilon^{2}\tilde{\delta}}{2N\widetilde{L}(2D+1)^{2}}}{\log\left(1-\xi_{\min}\eta_{\min}/2\right)},$
(80b) $\displaystyle\rho^{i}$ $\displaystyle\leq
1-\left(1-\frac{\left(\bar{\zeta}_{\theta}/8-\epsilon\right)(1-\bar{\gamma})-2b}{\widetilde{\Gamma}}\right)^{\frac{1}{N-1}},$
(80c) $\displaystyle\zeta^{i}$ $\displaystyle=\frac{\bar{\zeta}}{2},$ (80d)

where $\epsilon$ can take any value in
$0<\epsilon<\min\left\\{\frac{\bar{\zeta}_{\theta}}{8}-\frac{2b}{1-\bar{\gamma}},\frac{1}{1-{\gamma}_{\min}}\right\\}$.

[Proof of Lemma 15] When the conditions of Lemma 14 are satisfied, we have
that $P\left[\widetilde{E}_{k}^{c}\right]<\hat{\delta}$, where
$\widetilde{E}_{k}^{c}$ is the complement of $\widetilde{E}_{k}$. Then,

$\displaystyle
P\left[\widetilde{E}_{k},\ldots,\widetilde{E}_{k+\widetilde{L}-1}\right]$
$\displaystyle=1-P\left[\left(\widetilde{E}_{k},\ldots,\widetilde{E}_{k+\widetilde{L}-1}\right)^{c}\right]=1-P\left[\widetilde{E}_{k}^{c}\cup\cdots\cup\widetilde{E}_{k+\widetilde{L}-1}^{c}\right]$
$\displaystyle\geq
1-\left(P\left[\widetilde{E}_{k}^{c}\right]+P\left[\widetilde{E}_{k+1}^{c}\right]+\cdots+P\left[\widetilde{E}_{k+\widetilde{L}-1}^{c}\right]\right)=1-\widetilde{L}\hat{\delta}.$

By taking $\tilde{\delta}=\widetilde{L}\hat{\delta}$, it follows that the
conditions (68) now become (80), and the lemma is proved.

For simplicity, we choose
$\epsilon=\frac{1}{2}\min\left\\{\frac{\bar{\zeta}_{\theta}}{8}-\frac{2b}{1-\bar{\gamma}},\frac{1}{1-{\gamma}_{\min}}\right\\}$
in Theorem 2. Note that the result of Lemma 15 holds for any realization of
$\pi_{k}\in\Pi$. Therefore, under the same conditions, we in fact have that

$\displaystyle
P\left[\widetilde{E}_{k},\ldots,\widetilde{E}_{k+\widetilde{L}-1}\ \big{|}\
\pi_{k}\in\widetilde{\Pi}_{\rm eq}\right]\geq 1-\tilde{\delta},$ (81a)
$\displaystyle
P\left[\widetilde{E}_{k},\ldots,\widetilde{E}_{k+\widetilde{L}-1}\ \big{|}\
\pi_{k}\notin\widetilde{\Pi}_{\rm eq}\right]\geq 1-\tilde{\delta}.$ (81b)

By Lemma 12 and (81a), under conditions (80), we have that for all $k$,

$\displaystyle P\left[\pi_{k}=\pi_{k+1}=\cdots=\pi_{k+\widetilde{L}}\ \big{|}\
\pi_{k}\in\widetilde{\Pi}_{\rm eq}\right]\geq 1-\tilde{\delta}.$ (82)

By Lemma 13 and (81b), under conditions (80), we have that for all $k$,

$\displaystyle P\left[\pi_{k+\widetilde{L}}\in\widetilde{\Pi}_{\rm eq}\
\big{|}\ \pi_{k}\notin\widetilde{\Pi}_{\rm
eq}\right]\geq\tilde{p}\left(1-\tilde{\delta}\right).$ (83)

As a notation, let ${p}_{k}:=P\left[\pi_{k}\in\widetilde{\Pi}_{\rm
eq}\right]$. Then, (82) and (83) together imply that

$\displaystyle p_{(n+1)L}\geq
p_{nL}\left(1-\tilde{\delta}\right)+(1-p_{nL})\tilde{p}\left(1-\tilde{\delta}\right).$
(84)

Rearranging the above, we obtain that

$\displaystyle p_{(n+1)L}-p_{nL}$
$\displaystyle\geq\left(1-\tilde{\delta}\right)\tilde{p}-\tilde{\delta}p_{nL}-\left(1-\tilde{\delta}\right)\tilde{p}p_{nL}=\left[\tilde{\delta}+\left(1-\tilde{\delta}\right)\tilde{p}\right]\left[\frac{\left(1-\tilde{\delta}\right)\tilde{p}}{\tilde{\delta}+\left(1-\tilde{\delta}\right)\tilde{p}}-p_{nL}\right]$
(85) $\displaystyle\geq-\tilde{\delta}$ (86)

Note that $p_{(n+1)L}-p_{nL}\geq 0$ as long as
$p_{nL}\leq\frac{\left(1-\tilde{\delta}\right)\tilde{p}}{\tilde{\delta}+\left(1-\tilde{\delta}\right)\tilde{p}}$.
Further, if
$p_{nL}\leq\frac{\left(1-\tilde{\delta}\right)\tilde{p}}{\tilde{\delta}+\left(1-\tilde{\delta}\right)\tilde{p}}-\tilde{\delta}$,
then from (85), we have that
$p_{(n+1)L}-p_{nL}\geq\left[\tilde{\delta}+\left(1-\tilde{\delta}\right)\tilde{p}\right]\tilde{\delta}$;
if
$p_{nL}>\frac{\left(1-\tilde{\delta}\right)\tilde{p}}{\tilde{\delta}+\left(1-\tilde{\delta}\right)\tilde{p}}$,
then $p_{(n+1)L}-p_{nL}\geq-\tilde{\delta}$ from (86). Therefore, we have that

$\displaystyle
p_{nL}\geq\frac{\left(1-\tilde{\delta}\right)\tilde{p}}{\tilde{\delta}+\left(1-\tilde{\delta}\right)\tilde{p}}-\tilde{\delta},\quad\forall
n\geq\tilde{n},$ (87)

where

$\displaystyle\tilde{n}:=\frac{\frac{\left(1-\tilde{\delta}\right)\tilde{p}}{\tilde{\delta}+\left(1-\tilde{\delta}\right)\tilde{p}}-\tilde{\delta}}{\left[\tilde{\delta}+\left(1-\tilde{\delta}\right)\tilde{p}\right]\tilde{\delta}}=\frac{\left(1-\tilde{\delta}\right)^{2}\tilde{p}-\tilde{\delta}^{2}}{\left[\tilde{\delta}+\left(1-\tilde{\delta}\right)\tilde{p}\right]^{2}\tilde{\delta}}.$
(88)

This, together with (82), implies that for all $n\geq\tilde{n}$,

$\displaystyle
P\left[\pi_{nL}=\pi_{nL+1}=\cdots=\pi_{nL+L}\in\widetilde{\Pi}_{\rm
eq}\right]\geq\left(\frac{\left(1-\tilde{\delta}\right)\tilde{p}}{\tilde{\delta}+\left(1-\tilde{\delta}\right)\tilde{p}}-\tilde{\delta}\right)\left(1-\tilde{\delta}\right):=f(\tilde{\delta}).$
(89)

Therefore, if the number of exploration phases $k\geq
K:=\tilde{n}\widetilde{L}$, then $P\left[\pi_{k}\in\widetilde{\Pi}_{\rm
eq}\right]\geq f(\tilde{\delta})$. Note that $f(\tilde{\delta})$ is
continuous, decreasing in $\tilde{\delta}$, and $f(0)=1$, $f(\delta)<1-\delta$
for any $0<\delta<1$. Thus, we can take $\tilde{\delta}\in(0,\delta)$ such
that

$\displaystyle\left(\frac{\left(1-\tilde{\delta}\right)\tilde{p}}{\tilde{\delta}+\left(1-\tilde{\delta}\right)\tilde{p}}-\tilde{\delta}\right)\left(1-\tilde{\delta}\right)=1-\delta,$
(90)

which leads to $P\left[\pi_{k}\in\widetilde{\Pi}_{\rm eq}\right]\geq 1-\delta$
for all $k\geq K$, and this completes the proof of Theorem 2.

##  7 Proof of Theorem 3

Following Lemma 10 and by noting that
$|\phi^{i}|_{\infty}\leq\|\phi^{i}\|_{2}\leq 1$, Lemma 10 implies that for an
arbitrary $\bar{\pi}_{k}$ as in (10) and for any $\epsilon>0$ and
$0<\hat{\delta}<1$,

$\displaystyle
P\left[\left|Q_{\theta_{t_{k+1}}^{i}}^{i}-Q^{i}_{\theta_{\bar{\pi}_{k}^{-i}}^{i}}\right|_{\infty}\leq\epsilon,\
\forall
i\in[N]\right]=P\left[\left|{\phi^{i}}^{\top}\theta_{t_{k+1}}^{i}-{\phi^{i}}^{\top}\theta_{\bar{\pi}_{k}^{-i}}^{i}\right|_{\infty}\leq\epsilon,\
\forall i\in[N]\right]\geq 1-\hat{\delta}$

when the conditions (68) are satisfied. Under Assumption 7, we have that
$Q^{i}_{\theta_{\bar{\pi}_{k}^{-i}}^{i}}=Q^{i}_{\bar{\pi}_{k}^{-i}}$, which
leads to

$\displaystyle
P\left[\left|Q_{\theta_{t_{k+1}}^{i}}^{i}-Q^{i}_{{\bar{\pi}_{k}^{-i}}}\right|_{\infty}\leq\epsilon,\
\forall i\in[N]\right]\geq 1-\hat{\delta}.$

The above is exactly the same as the result in Lemma 2, and the rest of the
proof follows the proof of Theorem 1.