\chapter{Learning Dynamics and Convergence Analysis}
\label{chap:alg}

In this chapter, we outline the preliminary definitions and notations, and afterwards, present the decentralized $Q$-learning two-timestep algorithm for $n$-player stochastic games. Decentralized $Q$-learning was first introduced for two-player zero-sum stochastic games by Sayin et al. \cite{leslie2020best,sayin2020fictitious}. Afterwards, we analyze the asymptotic convergence of this algorithm in stochastic potential games.

\section[Definitions and Notations]{Definitions and Notations}
In a given SG (Definition~\ref{def:pg}), where player $i$ follows a stochastic policy $\pi^i \in \Delta(A^i)$, we denote the joint policy profile as $\pi = (\pi^1,\pi^2,...,\pi^n) \in \Delta(A)$ and define the expected utility of player $i$ when playing the SG over an infinite horizon as

\begin{equation} \label{eq:exputil}
    U^i(\pi^i, \pi^{-i}) = \mathbb{E}_{(a^i_t,a^{-i}_t)\sim\pi}\bigg\{\sum_{t=0}^{\infty}\gamma^t r^i_{s_t}(a^i,a^{-i})\bigg\}.
\end{equation}

where $s_0$ is drawn from a probability distribution $p_{s_0} \in \Delta(s)$, and the consecutive states are determined by the transition mapping $\mathcal{P}:\mathcal{S}\times \mathcal{A}\rightarrow \Delta(\mathcal{S})$. An $\epsilon$-Nash equilibrium can be defined for an SG similar to a normal-form game as a strategy profile $\pi_*=(\pi^1_*,\pi^2_*,...,\pi^n_*)$ if the following holds,

\begin{equation}
    U_i(\pi^i_*, \pi^{-i}_*) \geq U_i(\pi^i, \pi^{-i}_*)-\epsilon, \quad \forall i, \pi^i \in \Delta(A^i),
\end{equation}

where $\epsilon=0$ results in a Nash equilibrium. It is proven that every finite SG possesses at least one Nash equilibrium \cite{fink1964equilibrium}. To attribute a value to a given state from each agent's prespective, we define the value function of player $i$ in state $s$ as

\begin{equation} \label{eq:valfun}
    v^i_{\pi}(s) = \mathbb{E}_{(a^i,a^{-i})\sim \pi}\bigg\{r^i_s(a^i,a^{-i})+\gamma\sum_{s'\in S}v^i_{\pi}(s')p(s'|s,a^i,a^{-i})\bigg\}.
\end{equation}

It follows that $U_i(\pi^i, \pi^{-i})=\mathbb{E}_{s_0\sim p_{s_0}}\{v(s_0)\}$. Furthermore, the $Q$-function for state $s$ and a given action profile $(a^i, a^{-i})$ is defined as

\begin{equation} 
    Q^i_{\pi}(s,a^i,a^{-i}) = r^i_s(a^i,a^{-i})+\gamma\sum_{s'\in S}v^i_{\pi}(s')p(s'|s,a^i,a^{-i}).
\end{equation}

This function can be called the \emph{global} $Q$-function because it is a function of all players' actions and can be obtained only by full-observability over the game. The global $Q$-function at state $s$ can be interpreted as the utility function of player $i$ corresponding to that state over the iterations of the stochastic game. However, there are two obstacles in the way of using algorithms designed for repeated games, such as fictitious play, over this global $Q$-function; first, the $Q$-function is not constant and evolves alongside the value function and the policy of other players, and second, even if we could consider $Q$ constant, in decentralized learning, the agents would not have access to the actions of other players, and therefore, cannot calculate the $Q$-function. Both of these challenges can be addressed by employing the two-timestep decentralized $Q$-learning algorithm. In this algorithm, the agents employ their state value estimations, that have become \emph{locally stationary} in a slow timescale, to approximate the expected quality of a given action with respect to the other players' strategy. This is done by introducing the \emph{local} $Q$-function for player $i$ as

\begin{equation}
    q^i_{\pi}(s,a^i) = \mathbb{E}_{a^{-i}\sim \pi^{-i}}\big\{Q^i_{\pi}(s,a^i,a^{-i})\big\}
\end{equation}

\section[Decentralized Q-Learning]{Decentralized Q-Learning}
The decentralized $Q$-learning is based on a two-timescale update rule. In the faster timescale, agents assume that the environement is stationary, which is equivalent to assuming that the value function is constant and as if they are playing a single-state normal-form game. Consequently, they update their estimates of the local $Q$-function accordingly (\textbf{$Q$-update}). In the slower timescale, the agents apply the knowledge that they have gained from their observations since the previous slow timescale update and update their estimates of the value function to make the stage ready for another sequence of fast timescale updates with assumed stationarity. The algorithm has been designed in a way that each agent may be oblivious to the nature of the game or even the presence of other players.

Before presenting the algorithm, we define the type of policy that the agents follow in the algorithm. Perturbed best-response (also known as smoothed or noisy best-response), that was mentioned in Section~\ref{sec:gt}, can be defined for player $i$ in general terms as follows

\begin{equation} \label{eq:brgen}
    Br(q^i) = \argmax_{\mu \in \Delta(A)}\bigg\{\mu q^i-\nu(\mu)\bigg\}
\end{equation}

where $\mu$ is a probability distribution (stochastic policy) over $A$, and $\nu$ is a perturbation (noise) function, and $\mu\cdot q^i$ denotes the inner product of vectors $\mu$ and $q^i$. If the perturbation function $\nu$ is smooth, strictly concave, and with an unbounded gradient at the boundary of $\Delta(A)$, \eqref{eq:brgen} is shown to have a unique maximizer. Choosing $\nu$ as the negative entropy function with a noise level (temperature) $\tau$.

\begin{equation} \label{eq:nulogit}
    \nu(\mu,\tau)=\tau\sum_{a_j \in A}\mu_j \log(\mu_j)
\end{equation}

will result in a logit choice (softmax) BR function,

\begin{equation} \label{eq:logitdef}
Br(q^i,\tau) = \frac{\exp(q^i/\tau)}{\sum_{a_j \in A}\exp(q^i_j/\tau)}
\end{equation}

Algorithm~\ref{alg:decq-alg} presents the two-timescale decentralized $Q$-learning dynamics for a SG with $n$ players who follow a noisy $Br$ policy. As can be seen in the algorithm, the step sizes are normalized at every time step \cite{sayin2021decentralized,leslie2005individual,fudenberg1998theory}. As will be seen in the convergence proof, the normalization addresses the asynchronous updates of the local $Q$-function entries. With this procedure, although different actions in a given state may not be chosen with the same frequency, they are updates at the same rate in the expectation.

\begin{algorithm} 
\small
\caption{Decentralized Q-learning Dynamics}
\label{alg:decq-alg}
\begin{algorithmic}[1]
\Statex\textbf{Preliminary comments:}
\Statex$q^i_{s,t}$ denotes the local $Q$-values of player $i$ in state $s$ and time step $t$, and is a vector with $|A_i|$ elements. $q^i_{s,t}[j]$ denotes the $j^{th}$ entry this vector.
\Statex$v^i_{s,t}$ is a scalar denoting the value of state $s$ from the prespective of player $i$ at time step $t$.
\Statex$\#s$ is the number of visits to state $s$ up to now. This value is used to update the step sizes and temperature parameter overtime.
\Statex$\alpha_{\#s}$ is the smaller step size (corresponding to the faster timescale) for updating local $Q$-functions.
\Statex$\beta_{\#s}$  is the larger step size (corresponding to the slower timescale) for updating state value functions.
\Statex$\tau_{\#s}$ is the temperature parameter of the noisy best response policy.
\Statex$\alpha$, $\beta$ and $\tau$ are calculated at every visit to a state and all of them are inversely proportional to the number of visits to that state ($\#s$), and therefore decay overtime.
\Statex
\Statex\textbf{Require:} Keep track of \{$q^i_{s,t}$, $v^i_{s,t}$,$\#s$\}.
\Procedure{Separately for each player $i$, run the following dynamics for a pre-determined number of iterations or until a convergence criterion is met.}{}
\State Observe the current state $s_t$ and receive the reward $r^i_{t-1}$ for the previous action $a^i_{t-1}$ performed at state $s_{t-1}$.
\State Calculate the step sizes $\alpha_{\#s}$, $\beta_{\#s}$ and the temperature parameter $\tau_{\#s}$ based on the number of visits to $s_t$ up to now.
\State Normalize the step sizes $\Bar{\alpha}^i_{t-1}=\min(1,\alpha_{\#s})$, $\Bar{\beta}^i_{t-1}=\min(1,\beta_{\#s})$ to have expected synchronous updates of the $Q$-function entries.
\State Update the entry of the local $Q$-function corresponding to the chosen action $a^i_{t-1}$ (other entries and other states' estimates will not change):

\begin{equation} \label{eq:qupdate}
    q^i_{s_{t-1},t}[a^i_{t-1}] = q^i_{s_{t-1},t}[a^i_{t-1}] + \alpha_{\#s_{t-1}}(r^i_{t-1}+\gamma(v^i_{s_{t-1},t-1})-q^i_{s_{t-1},t}[a^i_{t-1}])
\end{equation} 

\State Construct the noisy best response policy:

\begin{equation} \label{eq:brupdate}
\pi^i_t = Br(q^i_{s_t},\tau_{\#s_t}) 
\end{equation}

\State Update the value function estimate of state $s$ (the value of other states will not change):

\begin{equation} \label{eq:vupdate}
v^i_{s_t,t+1} = v^i_{s_t,t} + \beta_{\#s_t}(\pi^i_t\cdot q^i_{s_t,t}-v^i_{s_t,t})
\end{equation}
\EndProcedure
\end{algorithmic}
\end{algorithm}

The following assumptions on step sizes and the temperature parameter are needed for the dynamics to converge.

\begin{assumption} \label{as:step1}
    The step size sequences $\{\alpha_t \in (0,1)|t\in \Z\}$ and $\{\beta_t \in (0,1)|t\in \Z\}$ are non-increasing and satisfy
    \begin{equation}
        \sum_{t=1}^{\infty}\alpha_t=\infty, \quad \sum_{t=1}^{\infty}\beta_t=\infty, \quad \lim_{t\rightarrow \infty}\alpha_t = \lim_{t\rightarrow \infty}\beta_t = 0
    \end{equation}
\end{assumption}

This assumption, similar to the one used in tabular $Q$-learning (Theorem~\ref{theo:qlearn}) is common in proving convergence of iterative algorithms using stochastic approximation theory \cite{borkar2009stochastic,benaim1999dynamics}.

\begin{assumption} \label{as:step2}
Given $J \in (0,1)$, a polynomial function $P(.)$, that may depend on $J$, exists such that for any factor $\lambda \in (0,1)$, if the set $\{k\in \Z_+|k\leq c, \frac{\beta_k}{\alpha_c}> \lambda\}$ is not empty, we will have
\begin{equation}
        \max\big\{l \in \Z_+|l\leq c,\quad and \quad \frac{\beta_l}{\alpha_c}> \lambda\big\}\leq Jc,\quad \forall c\geq P(\lambda^{-1})
    \end{equation}
\end{assumption}

The above assumption ensures two-timescale learning but it is stronger than $\lim_{t\rightarrow \infty}\frac{\beta_t}{\alpha_t}$ to ensure that when states are not visited with the same rate, the fast timescale updates of states with less frequent visits do not lag behind and interfere with two-timescale learning.

\begin{assumption} \label{as:temp1}
For any infinite sequence of actions, the environement dynamics are such that we may reach from any state $s$ to any other state $s'$ with a positive probability and within a finite number of iterations $n$.
\end{assumption}

\begin{assumption} \label{as:temp2}
The temperature sequence ${\tau}_{t> 0}$ is non-increasing and satisfies
    \begin{equation}
        \lim_{t\rightarrow \infty}\frac{(\tau_{t+1}-\tau_t)}{\alpha_t}=0, \quad and \quad \lim_{t\rightarrow \infty}\tau_t=0
    \end{equation}
    
Furthermore, the step size sequence $\{\alpha_t\}_{t>0}$ satisfies $\sum_{t=1}^{\infty}\alpha_t^{2-\rho}<\infty$, for some $\rho \in (0,1)$, and there exists $T,T'\in (0,\infty)$ such that $\alpha^{\rho}_t \exp(4D/\tau_t)\leq T'$ for all $t\geq T$.
\end{assumption}

These two assumptions ensure that states are visited infinitely often, so that the random noise in the perturbed $BR$ vanishes and the policy becomes deterministic as the number of iterations approach infinity.

Now, we state the main theorem for convergence of decentralized $Q$-learning in SPGs.

\begin{conjecture} \label{theo:main}
Given a SPG with $n$ players, if all agents follow the dynamics in Algorithm~\ref{alg:decq-alg}, and Assumptions~\ref{as:step1} to \ref{as:temp2} hold, the agents asymptotically converge to a pure Nash equilibrium policy of the SPG.
\end{conjecture}

An idea for the potential proof of this conjecture is given in Appendix~\ref{chap:append}. The first part of the given analysis is similar to Sayin et al. \cite{sayin2021decentralized} as the dynamics of a single state are decoupled from other states, yet it is reformulated for a game with $n$ players instead of two. The following limiting ODE is extracted for the decoupled dynamics

\begin{subequations} \label{eq:ode}
\begin{equation} \label{eq:odei}
\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:odeval}
\frac{dv^i_s(t)}{dt} = 0, \quad \forall (i,s) \in N\times\mathcal{S},
\end{equation}
\begin{equation} \label{eq:odetau}
\frac{d\tau(t)}{dt} = 0, \quad \forall s \in \mathcal{S},
\end{equation}
\end{subequations}

with the following simplification of notation 
\begin{multline}
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}

Afterwards, we associate this ODE to the stochastic fictitious play dynamics \cite{hofbauer2002global} by quantifying the difference error between them in order establish that the learning dynamics converges to the same point as the fictitious play dynamics, which is a Nash equilibrium, as this error and the temperature sequence converges to zero. At the end of Appendix~\ref{chap:append}, we also prove the convergence to a Nash equilibrium under an extra assumption.
