\chapter{Introduction}
\label{chap:intro}
\section[Motivations]{Motivations}
\label{sec:mot}
\subsection[MARL and Stochastic Potential Games]{MARL and Stochastic Potential Games}
Multi-agent reinforcement learning (MARL) is a branch of reinforcement learning (RL) where multiple decision makers (agents or players) interact with a shared environment. As there are multiple players involved in MARL, it is closely related to game theory (GT), and especially repeated games. In a classical MARL setting, each agent tries to maximize its own notion of cumulative reward over repeated trials (games). The nature of the environment and the reward function of the agents can fit into one of three categories. In a purely cooperative setting, the agents share the same reward function (they have identical interests), and are incentivized to collaborate and maximize the shared reward. The second scenario is the fully competitive zero-sum environment with conflicting interests among agents. The pure competitive and collaborative settings have few practical and real-world use cases, and therefore, we may consider a third and middle-ground scenario, i.e., a non-zero sum mixed-motive environment where agents should balance collaboration and competition to achieve a stable equilibrium. An important class of mixed-motive environments is potential games that can be used to model a large number of real-world scenarios, in areas such as routing in computer and transportation networks that can be formulated as congestion games \cite{rosenthal1973class}, resource allocation in settings like public good games \cite{heikkinen2006potential}, relaxation-labeling in image classification and segmentation \cite{yu1995game,berthod1996bayesian}, and many more practical use cases \cite{babichenko2016graphical}. Therefore, in this work, we focus on a newly emerged setup for MARL, known as stochastic potential game (SPG), also known as Markov potential game (MPG) \cite{mguni2020stochastic,mguni2021learning,leonardos2021global,zhang2021gradient}.

\subsection[Decentralized Learning]{Decentralized Learning}
MARL methods can be either centralized (coordinated), or decentralized (independent). The latter methods take advantage of a central coordinator who is in contact with all agents and can coordinate them to reach an equilibrium. On the other hand, in decentralized methods, the agents should make their decisions independently and only using local information. A degree of communication between neighboring agents may also be allowed in this setting.

In centralized MARL, the coordinator is fully aware of the game setup and can access the actions of all agents, and therefore, this setup is only feasible when we can simulate the game in a controlled environment \cite{silver2017mastering,vinyals2019grandmaster}. Furthermore, central algorithms may harm the privacy of agents and they may not scale as the number of agents grows. In decentralized MARL, many problems related to privacy and scalibility go away, as each agent only uses local information to make her decision. However, a great challenge that emerges in this setting is the non-stationarity of the environment \cite{hernandez2017survey,busoniu2008comprehensive}. The changes in a MARL environment are a function of all agents' actions, however, each agent is not aware of the actions of other agents and has to act only based on her local observations and rewards. Therefore, since the opponents modify their strategies over time, the environment dynamics is non-stationary from the agent's prespective. Although information exchange between neighboring agents may be possible in some cases and may sometimes alleviate part of the non-stationarity problem, there are many cases where privacy, cost, or scale of the problem make the local communication between agents harmful, expensive, or futile. Therefore, a fully decentralized learning scheme that addresses the non-stationarity challenge and in which agents act with complete independence, could be beneficial in terms of privacy, cost, and scalibility in multi-agent reinforcement learning.

\section[Contribution]{Contribution}
Motivated by the previous section, in this work, we consider a two-timescale decentralized Q-learning algorithm that has been proposed for two-player zero-sum Markov games \cite{sayin2021decentralized}. We extend this dynamics to multi-player settings and apply it to stochastic potential games. We observe that the learning dynamics asymptotically converge to a Nash equilibrium of the SPG. To our knowledge, this is the first value-based MARL work on SPGs. We run experiments on two SPG benchmarks, distancing games \cite{leonardos2021global} and network routing games \cite{roughgarden2007routing}, to evaluate the empirical performance of the algorithm.

\section[Outline]{Outline}
This thesis is organized in the following order. Chapter~\ref{chap:back} provides the necessary background and preliminaries in reinforcement learning, game theory, and multi-agent reinforcement learning. Chapter~\ref{chap:spg} introduces the concept of stochastic potential game and its benchmarks, and discusses previous works on SPGs. Chapter~\ref{chap:alg} is dedicated to the learning dynamics and its convergence analysis. In Chapter~\ref{chap:exp}, we present our experimental results. Finally, Chapter~\ref{chap:conc} concludes the thesis with a discussion on game-agnostic learning and possible directions for future works.


