\chapter{Analysis of Conjecture~\ref{theo:main}}
\label{chap:append}

The following theorem that is needed for decoupling the dynamics of each state, is based on Proposition 4.1 and Corollary 6.6 of Benaim \cite{benaim1999dynamics} is given as Theorem 2 in Sayin et al. \cite{sayin2021decentralized}:

\begin{theorem} \label{theo:stoch}
Consider the following discrete-time update rule,
\begin{equation} \label{eq:updatelimode}
    x_{t+1} = x_t + \lambda_t (F(x_t)+\epsilon_t+\omega_t),
\end{equation}
and its limiting ordinary differential equation (ODE),
\begin{equation} \label{eq:limode}
    \frac{dx(t)}{dt}=F(x_t).
\end{equation}
Assuming that the following are true,
\begin{enumerate}
    \item There exists a Lyapunov function $V: \mathbb{R}^m \rightarrow [0, \infty)$ for the ODE in \eqref{eq:limode}.
    \item The sequence of learning rates are bounded, their sum is divergent, and they are square-summable,
    \begin{equation}
        \lambda_t \in [0,1] \quad \forall t, \quad \sum_{t=0}^{\infty}\lambda_t = \infty, \quad \sum_{t=0}^{\infty}\lambda_t^2 < \infty
    \end{equation}
    \item All iterates $x_t \in \mathbb{R}^m$ are bounded, $\sup_{t} ||x_t||_{\infty}<\infty$.
    \item The vector field $F:\mathbb{R}^m\rightarrow \mathbb{R}^m$ is globally Lipschitz continuous.
    \item The stochastic approximation term $\omega_t \in \mathbb{R}^m$ satisfies the following condition for all $T>0$,
    \begin{equation}
        \lim_{t\rightarrow \infty}\sup_{n>t:\sum_{l=t}^{n-1}\lambda_l\leq T}\bigg\{\bigg|\bigg|\sum_{l=t}^{n-1} \lambda_l \omega_l\bigg|\bigg|\bigg\}=0.
    \end{equation}
    \item The error term $\epsilon_t \in \mathbb{R}^m$ is asymptotically negligible, i.e., $\lim_{t\rightarrow \infty}||\epsilon_t||=0$ with probability 1.
\end{enumerate}

the limit set of \eqref{eq:updatelimode} will be contained in the following set with probability 1,
\begin{equation}
    \{x \in \mathbb{R}^m: V(x)=0\}.
\end{equation}
\end{theorem}

We now show that the normalization of the learning rates at each timestep, would make the evolution of every entry of the local $Q$- function, synchronous in the expectation. For player $i$, the stochastic approximation term in \ref{theo:stoch} for all $a^i \in A^i_s$ and iteration $t$ is

\begin{multline} \label{eq:omega}
    \omega^i_{s_t,t}[a^i_t] := \textbf{1}_{a^i_t=a^i}\frac{r^i_s(a^i,a^{-i}_t)+\gamma v^i_{s_{t+1},t}-q^i_{s_t,t}[a^i]}{\overline{\pi}^i_t [a^i]}\\
    -\mathbb{E}\bigg\{\textbf{1}_{a^i_t=a^i}\frac{r^i_s(a^i,a^{-i}_t)+\gamma v^i_{s_{t+1},t}-q^i_{s_t,t}[a^i]}{\overline{\pi}^i_t [a^i]} \big| h_t \bigg\},
\end{multline}

where $h_t=\{q^j_{s,t},v^j_{s,t}|(j,s) \in \{1,...,n\}\times \mathcal{S}\}$ is the set of all current value and local $Q$-function estimates of players. To simplify the notation, we denote $\overline{\pi}^1_t[\Tilde{a}^{1}]... \overline{\pi}^{i-1}_t[\Tilde{a}^{i-1}]\overline{\pi}^{i+1}_t[\Tilde{a}^{i+1}]...\overline{\pi}^n_t[\Tilde{a}^{n}]$ as $\overline{\pi}^{-i}_t[\Tilde{a}^{-i}]$, and $\sum_{\Tilde{a}^1}...\sum_{\Tilde{a}^{i-1}}\sum_{\Tilde{a}^{i+1}}...\sum_{\Tilde{a}^{n}}$ as $\sum_{\Tilde{a}^{-i}}$. Now, we can expand the expectation above,

\begin{multline}
    \mathbb{E}\bigg\{\textbf{1}_{a^i_t=a^i}\frac{r^i_s(a^i,a^{-i}_t)+\gamma v^i_{s_{t+1},t}-q^i_{s_t,t}[a^i]}{\overline{\pi}^i_t [a^i]} \big| h_t \bigg\}\\
    =\bar{\pi}^i_t[a^i]\sum_{\Tilde{a}^{-i}}\overline{\pi}^{-i}_t[\Tilde{a}^{-i}]\frac{Q^i_{s_t,t}[a^i,\Tilde{a}^{-i}]-q^i_{s_t,t}[a^i]}{\overline{\pi}^i_t[a^i]}
\end{multline}

Therefore, after eliminating $\overline{\pi}^i_t[a^i]$, \eqref{eq:omega} can be written as,

\begin{multline} 
    \omega^i_{s_t,t}[a^i_t] := \textbf{1}_{a^i_t=a^i}\frac{r^i_s(a^i,a^{-i}_t)+\gamma v^i_{s_{t+1},t}-q^i_{s_t,t}[a^i]}{\overline{\pi}^i_t [a^i]}\\
    -\bigg(\sum_{\Tilde{a}^{-i}}Q^i_{s_t,t}(a^i, \Tilde{a}^{-i})\overline{\pi}^{-i}_t[\Tilde{a}^{-i}]-q^i_{s_t,t}[a^i]\bigg), 
\end{multline}

Denoting the multi-dimensional tensor multiplication $Q^i_{s^t,t}\overline{\pi}^1_t... \overline{\pi}^{i-1}_t\overline{\pi}^{i+1}_t...\overline{\pi}^n_t$ as $Q^i_{s_t,t}\overline{\pi}^{-i}_t$, based on Proposition 2 in Sayin et al. \cite{sayin2021decentralized}, we can write the update rule in~\eqref{eq:qupdate} as

\begin{equation} \label{eq:newupdateform}
    q^i_{s_t,t+1}=q^i_{s_t,t}+\alpha_{\#s_t}\big(Q^i_{s_t,t}\overline{\pi}_t^{-i}-q^i_{s_t,t}+\omega^i_{s^t,t}\big)
\end{equation}

We now consider the learning dynamics focused on a single state between two consecutive visits of that state. We may write the system of equation between these two visits of state $s$, as

\begin{subequations} \label{eq:visits}
\begin{equation} \label{eq:qvisits}
q^i_{s,t'} = q^i_{s,t}+\alpha_{\#s}\big(Q^i_{s,t}Br^{-i}(q^{-i}_{s,t},\tau_{\#s})-q^i_{s,t} + \mathbf{0} + \omega^i_{s,t}\big) \quad \forall i \in N,
\end{equation}
\begin{equation} \label{eq:vvisits}
v^i_{\Hat{s},t'} = v^i_{\Hat{s},t}+\alpha_{\#s}(0+\epsilon^i_{\Hat{s},t'}+0), \quad \forall (i,\Hat{s}) \in N\times\mathcal{S},
\end{equation}
\begin{equation} \label{eq:tauvisits}
\tau_{\#s+1} = \tau_{\#s}+\alpha_{\#s}(0+\frac{\tau_{\#s+1}-\tau_{\#s}}{\alpha_{\#s}}+0).
\end{equation}
\end{subequations}

where

\begin{equation} \label{eq:errv}
    \epsilon^i_{\Hat{s},t'} := \frac{v^i_{\Hat{s},t'}-v^i_{\Hat{s},t}}{\alpha_{\#s}}, \quad \forall (i,\Hat{s}) \in N\times\mathcal{S}.
\end{equation}

In \eqref{eq:visits}, the first term inside the parentheses correspond to $F(x_t)$, the second term corresponds to $\epsilon_t$, and the last term corresponds to $\omega_t$ in \eqref{eq:updatelimode}. 

Based on Lemma 2 in Sayin et al. \cite{sayin2021decentralized}, the error terms in \eqref{eq:errv} are asymptotically zero. Now, based on Proposition 3 in Saying et al. \cite{sayin2021decentralized} that ensures that $#s\rightarrow \infty$ as $t\rightarrow \infty$ for every $s$, following Theorem~\ref{theo:stoch}, we can write the limiting ODE of \eqref{eq:visits} as


\begin{subequations} \label{eq:odeapp}
\begin{equation} \label{eq:odeiapp}
\frac{dq^i_s(t)}{dt} = Q^i_s Br^{-i}(q^{-i}_s(t),\tau(t))-q^i(t) \quad \forall (i,s) \in N\times\mathcal{S},
\end{equation}
\begin{equation} \label{eq:odevalapp}
\frac{dv^i_s(t)}{dt} = 0, \quad \forall (i,s) \in N\times\mathcal{S},
\end{equation}
\begin{equation} \label{eq:odetauapp}
\frac{d\tau(t)}{dt} = 0, \quad \forall s \in \mathcal{s}.
\end{equation}
\end{subequations}

With the following notation
\begin{multline} \label{eq:notation}
Q^i_s Br^{-i}(q^{-i}_s(t),\tau(t)) \\
:= Q^i_s\overline{Br}^{1}(q^1_s(t),\tau(t))...\overline{Br}^{i-1}(q^{i-1}_s(t),\tau(t))\overline{Br}^{i+1}(q^{i+1}_s(t),\tau(t))...\overline{Br}^{n}(q^n_s(t),\tau(t))
\end{multline}


Before approaching to the next step of the proof, we state the following lemma about SPGs:

\begin{lemma} \label{lemma:qpot}
Assuming that the agents are playing an SPG (\ref{def:spg}) with state transitivity (\ref{def:stran}), based on Proposition 4 in Mguni et al. \cite{mguni2021learning}, the global $Q$-function of the game admits a potential function G:
\begin{equation} \label{eq:pot}
    Q^i(s,(a^i)',a^{-i}) - Q^i(s,a^i,a^{-i}) = G(s,(a^i)',a^{-i}) - G(s,a^i,a^{-i}), \quad \forall (i,s) \in N\times\mathcal{S}.
\end{equation}
\end{lemma}

We may add $n$ auxiliary ODEs for $\pi^i$ that trivially hold when we follow a noisy BR policy to the system of ODEs as

\begin{equation} \label{eq:odeadd}
\frac{d\pi^i_s(t)}{dt} = Br^i(q^i_s(t),\tau(t))-\pi^i_s(t), \quad \forall (i,s) \in N\times\mathcal{S}
\end{equation}

Merging \eqref{eq:odeapp} and \eqref{eq:odeadd} and removing the state subscript, we will have the following system of ODEs for all $i$:

\begin{subequations}
\begin{equation}  \label{eq:odenew}
\frac{dq^i(t)}{dt} = Q^i Br^{-i}(q^{-i}(t),\tau)-q^i(t),
\end{equation}
\begin{equation}
\frac{d\pi^i(t)}{dt} = Br^{i}(q^{i}(t),\tau)-\pi^i(t),
\end{equation}
\end{subequations}

Our ultimate goal is to prove that the policies $\pi^i$ will converge to a Nash equilubrium profile as $t \rightarrow \infty$.

To move towards this goal, we need to define a suitable Lyapunov function on the system of ODE at hand. We first define the following property for $q^i$, 

\begin{definition}[Belief-based $Q$-function] \label{def:belief}
    We call the local $Q$-function, $q^i$ for player $i$, \emph{belief-based}, if there exists a strategy $\pi^{-i} \in \Delta(A)$ (following the same notation as \eqref{eq:notation}), where we could establish the following equality:
    \begin{equation}
        q^i(t) = Q^{i}\pi^{-i}(t)
    \end{equation}
\end{definition}

If we could establish that $q^i$ are belief-based for every time step, then, the ODEs in \eqref{def:belief} would follow the same trajectory as the stochastic fictitious play \cite{hofbauer2002global} with the following system of ODE:

\begin{equation} \label{eq:odebr}
\frac{d\pi^i(t)}{dt} = Br^{i}(Q^{i}\pi^{-i}(t),\tau)-\pi^i(t),
\end{equation}

In Proposition 4.1, \cite{hofbauer2002global} proposes the following strict Lyapunov function for stochastic fictitious play in potential games,

\begin{equation} \label{eq:lpnoisybr}
    L(\pi^i,\pi^{-i})= (\pi^i)^T Q^i\pi^{-i} - \sum_{i \in N}\nu(\pi^i)
\end{equation}

where $\nu$ is the perturbation function in \eqref{eq:brgen} that can be chosen as \eqref{eq:nulogit}. 

Proposition 4.2 of Hofbauer \cite{hofbauer2002global} proves that the function in \eqref{eq:lpnoisybr} is strictly increasing and converge to rest points as long as the perturbation function $\nu$ is sufficiently smooth, and in Proposition 3.1, it states that as the perturbations become small enough, these rest points approximate a Nash equilibrium of the underlying game.

The aforementioned proof is only valid if the belief-based property in Definition \ref{def:belief} holds for every time step. If that is true, based on Lemma \ref{lemma:qpot}, the trajectories of \ref{eq:odebr} and \ref{eq:odenew} would follow the same path towards a Nash equilibrium. However, the belief-based property does not necessary hold for the whole trajectory. It is possible to prove that $q^i$ becomes belief-based in the limit using the following Lyapunov function,

\begin{equation} \label{lp:belief}
    H(t) = \sum_{i \in N}||q^i-Q^i\pi^{-i}||^2
\end{equation}

By definition, \eqref{lp:belief} is always greater or equal to zero. Using \eqref{eq:ode} and \eqref{eq:odeadd}, we can take the derivative of $H$

\begin{equation}
\frac{dH(t)}{dt} = -nH(t)
\end{equation}

Therefore, $H(t)$ is a Lyapunov function for the flow, and,

\begin{equation} \label{eq:belief-lim}
    \lim_{t\rightarrow \infty}||q^i_t-Q^i\pi^{-i}_t||^2=0
\end{equation}

Which proves that $q^i$ is belief-based asymptotically for every $i$.

We can form the belief-based error along the trajectory of \ref{eq:belief-lim} as

\begin{equation}
    \varepsilon(t) := q^i(t)-Q^i\pi^{-i}(t).
\end{equation}

A possible direction to complete the proof would be quantifying this error term and establishing its rate of convergence towards zero.

\noindent\textbf{Convergence Proof with an Extra Assumption:} If we are able to establish the belief-based property (\ref{def:belief}) at the beginning of the trajectory with a communication-based initialization among the agents, then based on Corollary 8.17 in Kelly and Peterson \cite{kelley2010theory}, the system of linear ODEs formed by merging \eqref{eq:odebr} and \eqref{eq:odenew} become coupled together and the system will have a unique solution that based on Hofbauer \cite{hofbauer2002global} is a Nash equilibrium.