\chapter{Experimental Results}
\label{chap:exp}

In this chapter, we first consider two preliminary SPGs with a single state and analyze the behavior of the learning dynamics and the limiting ODE \eqref{eq:odei}. After that, we provide the experimental results obtained on the two SPG benchmarks, network routing games, and distancing games. All codes related to experiments in this chapter are publicly available online\footnote{\url{https://github.com/hafezgh/PoliTo-MSc-Thesis}}.

\section[ODE Simulation]{ODE Simulation}

In order to intuitively grasp the evolution of the dynamics, we simulate the limiting ODE \eqref{eq:odei} in two single-state potential games. Consider the two-player normal-form game in Table~\ref{tab:pot2p}. Considering, we simulated the ODE \eqref{eq:odei} using $dt=10^{-6}$, $\tau=0.01$, and $\gamma=0.5$. As the state value functions are constant in \eqref{eq:odeval}, they are set to zero, so that the $Q$ function would be equal to the reward function. evolution of the local $Q$-functions for both players with two different initial conditions are plotted in Figure~\ref{fig:ode2p}.

\begin{table}[htbp]
\begin{center}
\centering
\caption{A single-state potential game with two players and two actions alongside the potential function}
\begin{tabular}{c|c|c|}
\cline{2-3}
\begin{tabular}[c]{@{}c@{}}P2\\ P1\end{tabular} & a1                                       & a2                                       \\ \hline
\multicolumn{1}{|c|}{a1}                        & 0.2, -0.3                                & {\color[HTML]{FE0000} \textbf{0.4, 0.1}} \\ \hline
\multicolumn{1}{|c|}{a2}                        & {\color[HTML]{FE0000} \textbf{0.5, 0.2}} & 0.2, 0.1                                 \\ \hline
\end{tabular}
\quad
\begin{tabular}{lcc}
\multicolumn{1}{c}{$\Phi$} & \multicolumn{1}{l}{}                                     & \multicolumn{1}{l}{}                                     \\ \cline{2-3} 
\multicolumn{1}{l|}{}      & \multicolumn{1}{c|}{0.1}                                 & \multicolumn{1}{c|}{{\color[HTML]{FE0000} \textbf{0.5}}} \\ \cline{2-3} 
\multicolumn{1}{l|}{}      & \multicolumn{1}{c|}{{\color[HTML]{FE0000} \textbf{0.4}}} & \multicolumn{1}{c|}{0.3}                                 \\ \cline{2-3} 
\end{tabular}
\label{tab:pot2p}
\end{center}
\end{table}

\begin{figure}[h]
    \centering
  \begin{subfigure}[b]{0.48\textwidth}
  \centering
  \includegraphics[scale=0.17]{content/images/ode_a2_v1.png}
  \end{subfigure}
    \hfill
 \begin{subfigure}[b]{0.48\textwidth}
  \centering
  \includegraphics[scale=0.17]{content/images/ode_a2_v2.png}
  \end{subfigure}
  \caption{The ODE simulation for the two-player normal-form potential game in Table~\ref{tab:pot2p} with two different random initializations.}
  \label{fig:ode2p}
\end{figure}

It can be seen that the local $Q$-functions converge to the global $Q$-values corresponding to a Nash equilibrium. As supported by theory, this equilibrium could be any of the possible Nash equilibria of the game, and not necessarily the one corresponding to a strict Nash equilibrium or the maximum of the potential function.

Figure~\ref{fig:ode4p} presents similar simulation results for the game in Table~\ref{tab:pot4p}.

\begin{table}[h]
\begin{center}
\centering
\caption{A single-state potential game with two players and four actions alongside the potential function}
\begin{tabular}{c|c|c|c|c|}
\cline{2-5}
\begin{tabular}[c]{@{}c@{}}P2\\ P1\end{tabular} & a1                                       & a2                                       & a3                                      & a4                                      \\ \hline
\multicolumn{1}{|c|}{a1}                        & 0.1,-0.4                                 & {\color[HTML]{000000} 0.3,-0.2}          & {\color[HTML]{FE0000} \textbf{0.4,0.3}} & -0.1,-0.5                               \\ \hline
\multicolumn{1}{|c|}{a2}                        & {\color[HTML]{000000} 0.5,0.2}           & {\color[HTML]{FE0000} \textbf{0.7, 0.4}} & 0.2,0.3                                 & 0.1,-0.1                                \\ \hline
\multicolumn{1}{|c|}{a3}                        & 0.2,-0.2                                 & 0.3,-0.1                                 & {\color[HTML]{000000} 0.0,0.0}          & {\color[HTML]{FE0000} \textbf{0.4,0.1}} \\ \hline
\multicolumn{1}{|c|}{a4}                        & {\color[HTML]{FE0000} \textbf{0.6, 0.9}} & 0.4,0.7                                  & 0.1,0.8                                 & 0.0, 0.4                                \\ \hline
\end{tabular}
\quad
\begin{tabular}{ccccc}
$\Phi$                &                                                          &                                                          &                                                          &                                                          \\ \cline{2-5} 
\multicolumn{1}{c|}{} & \multicolumn{1}{c|}{0.2}                                 & \multicolumn{1}{c|}{{\color[HTML]{000000} 0.4}}          & \multicolumn{1}{c|}{{\color[HTML]{FE0000} \textbf{0.9}}} & \multicolumn{1}{c|}{0.1}                                 \\ \cline{2-5} 
\multicolumn{1}{c|}{} & \multicolumn{1}{c|}{{\color[HTML]{000000} 0.6}}          & \multicolumn{1}{c|}{{\color[HTML]{FE0000} \textbf{0.8}}} & \multicolumn{1}{c|}{0.7}                                 & \multicolumn{1}{c|}{0.3}                                 \\ \cline{2-5} 
\multicolumn{1}{c|}{} & \multicolumn{1}{c|}{0.3}                                 & \multicolumn{1}{c|}{0.4}                                 & \multicolumn{1}{c|}{{\color[HTML]{000000} 0.5}}          & \multicolumn{1}{c|}{{\color[HTML]{FE0000} \textbf{0.6}}} \\ \cline{2-5} 
\multicolumn{1}{c|}{} & \multicolumn{1}{c|}{{\color[HTML]{FE0000} \textbf{0.7}}} & \multicolumn{1}{c|}{0.5}                                 & \multicolumn{1}{c|}{0.6}                                 & \multicolumn{1}{c|}{0.2}                                 \\ \cline{2-5} 
\end{tabular}
\label{tab:pot4p}
\end{center}
\end{table}

\begin{figure}[h]
    \centering
  \begin{subfigure}[b]{0.48\textwidth}
  \centering
  \includegraphics[scale=0.17]{content/images/ode_a4_v1.png}
  \end{subfigure}
    \hfill
 \begin{subfigure}[b]{0.48\textwidth}
  \centering
  \includegraphics[scale=0.17]{content/images/ode_a4_v2.png}
  \end{subfigure}
  \caption{The ODE simulation for the four-player normal-form potential game in Table~\ref{tab:pot4p} with two different random initializations.}
  \label{fig:ode4p}
\end{figure}

Again, the local $Q$-functions converge to the global $Q$-values corresponding to a Nash equilibrium on the game depending on the initialization.

\section[Single-state Potential Games]{Single-state Potential Games}
In this section, we run the dynamics for the two games in Table~\ref{tab:pot2p} and Table~\ref{tab:pot4p}. For this experiment and all the folloeing experiments, we use step sizes $\alpha_t$ and $\beta_t$, and the temperature parameter $\tau_t$ with the following expressions and conditions that have been shown to satisfy Assumptions~\ref{as:step1}, \ref{as:step2}, and \ref{as:temp2} \cite{sayin2021decentralized}:

\begin{subequations}
\begin{equation}
    \alpha_t = t^{-\rho_{\alpha}},
\end{equation}
\begin{equation}
    \beta_t = t^{-\rho_{\beta}},
\end{equation}
\begin{equation}
    \tau'_t = \Bar{\tau}\big(1+\Bar{\tau}\frac{\rho_{\alpha}\rho}{4D}\log(c)\big)^{-1},
\end{equation}
\end{subequations}

where $0.5<\rho_{\alpha}<\rho_{\beta}\leq 1$, $\rho \in (0,2-1/\rho_{\alpha})$, and $\Bar{\tau}>0$.

Figures~\ref{fig:ode2p} and \ref{fig:ode2p} show the results of two runs corresponding to the games in Table~\ref{tab:pot2p} and Table~\ref{tab:pot4p}, respectively. The actions corresponding to the maximum of local $Q$-values in both cases correspond to a Nash equilibrium of the game ($(a1,a2)$, and $(a3,a4)$ respectively).

\begin{figure}[h]
\centering
\includegraphics[scale=0.5]{content/images/pot2p2a.pdf}
\caption{An individual run of the decentralized $Q$-learning dynamics for the potential game in Table~\ref{tab:pot2p}}
\end{figure}

\begin{figure}[h]
\centering
\includegraphics[scale=0.5]{content/images/pot2p4a.pdf}
\caption{An individual run of the decentralized $Q$-learning dynamics for the potential game in Table~\ref{tab:pot4p}}
\end{figure}

\section[Distancing Games]{Distancing Games}
In this section, we report our results on an example of the distancing game benchmark introduced in Section~\ref{sec:dist}. The game is played with $n=8$ players, and $m=4$ facilities in each state. Therefore, if more than 4 players choose the same facility in the safe state, the agents transit to the spread state. In order to go back to the safe state, exactly 2 agents should choose each facility in the spread state. The optimum strategies in these two states are visualized in Figure~\ref{fig:dist_opt}.

\begin{figure}[h]
    \centering
  \begin{subfigure}[b]{0.48\textwidth}
  \centering
  \includegraphics[scale=0.17]{content/images/dist_opt_safe.pdf}
  \caption{The optimum strategy in the safe state}
  \end{subfigure}
    \hfill
 \begin{subfigure}[b]{0.48\textwidth}
  \centering
  \includegraphics[scale=0.17]{content/images/dist_opt_spread.pdf}
  \caption{The optimum strategy in the spread state}
  \end{subfigure}
  \caption{Optimum strategies in a distancing game}
  \label{fig:dist_opt}
\end{figure}

In order to run the decentralized $Q$-learning dynamics on the distancing game, we consider as the convergence criterion the L1 accuracy metric, which is the average distance between the current policy and final perturbed $BR$ policy of the agents:

\begin{equation}\small
    L1-accuracy = \frac{1}{N}\sum_{i\in N}|BR^i-BR^i_{final}|=\frac{1}{N}\sum_{i\in N}\sum_{s\in \mathcal{S}}\sum_{a^i_j\in \mathcal{A}_i}|BR^i(s,a^i_j)-BR^i_{final}(s,a^i_j)|.
\end{equation}

We stop the iterations when the L1-accuracy goes below a small threshold $\epsilon$. Note that the convergence of $L1$ to zero indicates that the temperature parameter in $BR$ have become small enough and the the perturbed $BR$ has converged to a deterministic $BR$ that chooses the optimum action corresponding to a Nash equilibrium in each state.

Figure~\ref{fig:dist_res1} plots the L1-accuracy of 8 independent runs of decentralized $Q$-learning on the distancing game with $\gamma=0.5$, and Figure~\ref{fig:dist_res2} plots the corresponding means and shaded standard deviation of these runs. All independent runs converged to the optimal strategies in \ref{fig:dist_opt}. The configuration of specific agents in facilities in each state may differ in different runs depending on the random seed.

\begin{figure}[h]
  \centering
  \includegraphics[scale=0.5]{content/images/res_dist2.pdf}
  \caption{L1-accuracy trajectories for 8 independent runs of decentralized $Q$-learning dynamics on the distancing game benchmark}
   \label{fig:dist_res1}
\end{figure}

\begin{figure}[h]
  \centering
  \includegraphics[scale=0.5]{content/images/res_dist1.pdf}
  \caption{The mean and standard deviation of L1-accuracy trajectories for 8 independent runs of decentralized $Q$-learning dynamics on the distancing game benchmark}
   \label{fig:dist_res2}
\end{figure}

\section[Congestion Games]{Congestion Games}
As the second benchmark, we report our results on an example of atomic network routing game introduced in Section~\ref{sec:networkrouting}. We consider the game in Figure~\ref{fig:cong_opt} where agents all start in the source node, and have to take the left or right action in each intermediate stage until they reach the destination node. To make the SG infinite-horizon, we move the agents back to the source node after they reach the destination node. Based on this condition, the number of states in the game will be $(l-1)\times 2^{|N|}+1$, where $l$ is the number of internal layers, and $N$ is the number of agents. Therefore, the optimal policy in each state is for the agents to spread throughout the possible routes in each state and minimize congestion in the network. For example, the optimal number of agents in each route when they are all going from source to destination is written on arrows in Figure~\ref{fig:cong_opt}. We run the decentralized $Q$-learning dynamics in Figure~\ref{fig:cong_opt} for $N=4$ and $N=4$ agents corresponding to $|S|=17$ and $|S|=17$ states with a constant cost for each route and $\gamma=0.5$.


\begin{figure}[h]
\centering
\includegraphics[scale=0.4]{content/images/cong_opt.pdf}
\caption{The atomic network routing game and its optimal strategy for reaching the destination node}
\label{fig:cong_opt}
\end{figure}

Figures~\ref{fig:cong1_res_p4} and \ref{fig:cong1_res_p8} plot the L1-accuracy of 8 independent runs for $N=4$ and $N=8$ players, respectively, playing the game in Figure~\ref{fig:cong_opt}. Figures~\ref{fig:cong2_res_p4} and \ref{fig:cong2_res_p8} plot the corresponding means and shaded standard deviation of these runs for $N=4$ and $N=8$ players, respectively. All independent runs converged to the optimal strategies for all states, i.e., minimum congestion at each route was achieved by agents splitting throughout the routes in each state. Again, the configuration of specific agents in the network, i.e., their choice of routes in each state differs in different runs depending on the random seed.

\begin{figure}[h]
\centering
\includegraphics[scale=0.5]{content/images/res_cong2_p4.pdf}
\caption{L1-accuracy trajectories for 8 independent runs of decentralized $Q$-learning dynamics on the network routing game benchmark for $N=4$ agents}
 \label{fig:cong1_res_p4}
\end{figure}

\begin{figure}[h]
\centering
\includegraphics[scale=0.5]{content/images/res_cong1_p4.pdf}
\caption{The mean and standard deviation of L1-accuracy trajectories for 8 independent runs of decentralized $Q$-learning dynamics on the network routing game benchmark for $N=4$ agents}
 \label{fig:cong2_res_p4}
\end{figure}

\begin{figure}[h] 
\centering
\includegraphics[scale=0.5]{content/images/res_cong2_p8.pdf}
\caption{L1-accuracy trajectories for 8 independent runs of decentralized $Q$-learning dynamics on the network routing game benchmark for $N=8$ agents}
\label{fig:cong1_res_p8}
\end{figure}

\begin{figure}[h] 
\centering
\includegraphics[scale=0.5]{content/images/res_cong1_p8.pdf}
\caption{The mean and standard deviation of L1-accuracy trajectories for 8 independent runs of decentralized $Q$-learning dynamics on the network routing game benchmark for $N=8$ agents}
\label{fig:cong2_res_p8}
\end{figure}



