\chapter{Background and Preliminaries}
\label{chap:back}
In this chapter, we provide the introductory notions in reinforcement learning, game theory, and multi-agent reinforcement learning, and discuss the non-stationarity issue in decentralized MARL.

\section[Single-Agent RL]{Single-Agent RL}
Broadly speaking, reinforcement learning is a sub-field of machine learning (ML), and can be considered one of the three basic ML paradigms alongside supervised learning and unsupervised learning. In RL, the learner (agent) is not explicitly told what to do, but instead is left out in the wild to discover its environment and maps its states to actions that yield her the maximum cumulative reward overtime. She is highly dependent on trial and error during this process, and also may need to handle an important challenge named distant (delayed) reward, as the agent's actions may not only affect the immediate reward but also the reward values in the future \cite{sutton2018reinforcement}. 

RL lies between supervised and unsupervised learning. It is different from unsupervised learning which is mostly involved in finding patterns and structures in uncategorized data \cite{dayan1999unsupervised,hastie2009unsupervised}. It is also different from supervised learning where the model takes labelled data as its input and tries to generalize to recognize and label unlabelled samples \cite{hastie2009overview}. In a complex and interactive environment, it is usually impractical to obtain and label sample actions that are representative enough for different situations that the agent may find herself in. Therefore, in RL, the agent uses the reward signal as its compass, and builds a model to maximize its long-term return, all through policy improvement by trial and error and without access to any labelled data \cite{yang2020overview}. Another distinct difference between RL and both supervised and unsupervised learning is the trade-off between exploration and exploitation that is only present in RL. An agent should \emph{exploit} the actions that she knows would yield the maximum cumulative reward with a high certainty, however, in order to find such actions in different situations, she has to \emph{explore} untried actions in order to find them. How to balance exploration and exploitation is a dilemma that has been focused on by mathematicians and computer scientists through years \cite{sutton2018reinforcement}. The importance of RL in machine learning, and in general artificial intelligence (AI), is obvious when many renowned researchers believe that "Reward is Enough" to exhibit almost any ability related to natural and artificial intelligence \cite{silver2021reward}.

After this general introduction, we now mathematically formulate a single-agent RL problem. A Markovian discrete environment, with which an agent interacts, can be modelled through a Markov decision process (MDP) defined below.

\begin{definition}[Markov decision process] \label{def:mdp}
A Markov decision process\footnote{There are some generalizations to MDP to model partially observable environments. For example, in a partially observable Markov decision process (POMDP), the environment dynamics are determined by an MDP, however, the agent can only observe the environment through a set of sensors and maintain a probability distribution of different observations given the current state.} may be described using a tuple of four key elements $(\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R})$, where,
\begin{itemize}
    \item $\mathcal{S}$ is a set representing the different states in the environment.
    \item $\mathcal{A}$ is a set representing the possible actions an agent can take.
    \item $\mathcal{P}:\mathcal{S}\times\mathcal{A}\rightarrow \Delta(\mathcal{S})$ is a probability mapping\footnote{$\Delta(\mathcal{S})$ denotes a probability simplex over the set $\mathcal{S}$.} that at time step $t \in \mathbb{N}$ gives the transition probabilities that the agent taking action $a \in \mathcal{A}$ in state $s \in \mathcal{S}$ would go to the next state $s' \in \mathcal{S}$ at time step $t+1$.
    \item $\mathcal{R}: \mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow \mathbb{R}$ is the reward function that returns a bounded scalar in the range $[-R_{max},R_{max}]$ to the agent as a result of its action $a$ in state $s$ and the transition to $s'$.
\end{itemize}
\end{definition}

Given an MDP, the goal of the agent interacting with it and following a policy $\pi$, is to maximize her expectation of discounted sum of rewards over time,

\begin{equation} \label{eq:cumrew}
    \mathbb{E}_{a_t\sim \pi}\bigg\{\sum_{t=0}^{T}\gamma^t R_{a_t}(s_t,s_{t+1})\bigg\},
\end{equation}

where $T$ is the terminating time step and is finite in episodic tasks, or is equal to $\infty$ in continuing infinite-horizon tasks. $\gamma \in [0,1]$ is a discount factor determining the farsightedness of the agent (a lower value of gamma denotes a more myopic and greedy agent). In continuing tasks, $\gamma$ should be strictly less than one to ensure a finite value for the discounted reward. The policy $\pi: \mathcal{S}\rightarrow \Delta(A)$ denotes a probability mapping from each state to the set of possible actions. A policy is deterministic at a given state $s$, if a single action, $a$ has a probability equal to one, and the other actions have zero probability of being selected. The ultimate goal of the agent is finding an optimal policy that maximizes the cumulative reward in \eqref{eq:cumrew}.

In order to formulate a formal learning scenario, we can define some variables to denote the quality of different states and different actions in those states. Therefore, the state value function of state $s$ under a policy $\pi$ is defined as

\begin{equation} \label{eq:valfunsing}
    V^{\pi}(s) := \mathbb{E}_{a_t \sim \pi}\bigg\{\sum_{t=0}^{T}\gamma^t R_{a_t}(s_t,s_{t+1})|s_0 = s\bigg\}.
\end{equation}

We may also define the state-action value function, or $Q$-function under policy $\pi$ as

\begin{equation} \label{eq:qfunsing}
    Q^{\pi}(s, a) := \mathbb{E}_{a_t\sim\pi}\bigg\{\sum_{t=0}^{T}\gamma^t R_{a_t}(s_t,s_{t+1})|s_0 = s, a_0=a\bigg\}.
\end{equation}

The $Q$-function, where $Q$ stands for quality, shows the value of taking a specific action in state $s$ and following policy $\pi$ afterwards. If we choose action $a_0$ also according to $\pi$, $V^{\pi}=\mathbb{E}^{\pi}\{Q^{\pi}(s,a)\}$. We may write value functions for every state in recursive form that are known as Bellman equations \cite{bellman1966dynamic}

\begin{equation} \label{eq:bellmaneqs}
V^{\pi}(s) = \mathbb{E}_{a\sim\pi}\bigg\{R_a(s,s')+\gamma \sum_{s'\in \mathcal{S}}V^{\pi}(s')\mathcal{P}(s'|s,a) \bigg\},\quad \forall s \in \mathcal{S}.
\end{equation}

The optimal values of these equations are represented using the Bellman optimality equations for $V^*$ \cite{bellman1966dynamic},

\begin{equation} \label{eq:valbellman}
V^{*}(s) = \max_{a \in \mathcal{A}}(R_a(s,s')+\gamma \sum_{s'\in \mathcal{S}}V^{*}(s')\mathcal{P}(s'|s,a)), \quad \forall s \in \mathcal{S}.
\end{equation}

We may also write the optimal values of $Q^*$ for all state-action pairs using $V*$ as

\begin{equation} 
Q^{*}(s, a) = R_a(s,s')+\gamma \sum_{s'\in \mathcal{S}}V^{*}(s')\mathcal{P}(s'|s,a), \quad \forall (s,a) \in \mathcal{S}\times \mathcal{A}.
\end{equation}

The equations in \eqref{eq:valbellman} constitute a non-linear system whose solution is guaranteed to exist for all finite MDPs \cite{szepesvari2010algorithms}. After solving this system of equations and finding $V*$, one may find the actions for which \eqref{eq:valbellman} yields its maximum. To calculate the optimal policy at each state, we may assign a non-zero probability to these actions, and a zero probability to others. Since there is no difference in value for the optimal actions if they are more than one, the optimal policy can also be a purely deterministic policy favoring any of the optimal actions. Therefore, it can be said that any finite MDP has a deterministic optimal policy $\pi^*$.

As a side note, it should be mentioned that the MDP framework as a model of an RL environment is only valid if the environment possesses the Markov property

\begin{equation}\small
    \mathcal{P}(s_{t+1}=s', r_{t+1}=r|s_t,a_t)=\mathcal{P}(s_{t+1}=s', r_{t+1}=r|s_t,a_t,r_t,...,s_{1},a_{1},r_{1}s_0,a_0).
\end{equation}

Evidently, this assumption does not hold if one considers an arbitrary observation as the state in a complex environment. However, performing encoding tricks, such as augmenting several observations from consecutive time steps into a single state, may create state representations that include approximately all information needed for decision making. Furthermore, to theoretically prove convergence of many RL algorithms, the Markov assumption is necessary. Assuming that the Markov property holds and we perfectly know the dynamics of the environment, which is not always the case, solving the system of Bellman optimality equations \eqref{eq:valbellman} analytically for a complex environement with a large number of states is intractable. It requires an exhaustive search and looking ahead every possible trajectory in the MDP to find the optimal action in each state. A faster solution to find the optimal policy in MDPs is dynamic programming (DP) \cite{bellman1966dynamic}. DP methods solve a complicated problem by breaking it down to smaller sub-problems recursively. The two DP algorithms in RL are policy iteration and value iteration. Although these algorithms find the optimal policy in polynomial time of the number of states and actions in the worst case, they are rarely used in practice because they require a complete model of the environment. 

The DP approach is the most basic algorithm in the realm of \emph{model-based RL}. Any RL algorithm that uses a model, whether known (such as Monte Carlo tree search (MCTS)) or learned (such as World Models \cite{ha2018world}), to solve the MDP and calculate an optimal value function or policy can be considered model-based \cite{moerland2020model}. On the other hand, \emph{model-free RL} uses only experience in the environment without explicitly building a model of the MDP to adjust its policy and achieve maximum return. These model-free algorithms are either offline and wait until the end of the episode before updating their estimates (Monte Carlo (MC) methods), or they bootstrap in an online fashion, take advantage of the learned estimates up to now, and form the reward prediction error (RPE) to update the value or action-value estimates without the need to wait for the episode to terminate. This mode of learning, known as temporal difference (TD) learning is useful for tasks with long episodes and continuing tasks. It is worth mentioning that an algorithm may involve both model-free and model-based learning elements. An example of such agents is the renowned AlphaGo \cite{silver2017mastering} that defeated the human world champion of the ancient board game, Go, in 2016\footnote{\url{https://www.alphagomovie.com/}}.

Model-free RL is usually divided into two main categories; \emph{value-based} methods and \emph{policy-based} methods.

In value-based RL, the agent optimizes its estimation of the action-value ($Q$) function to obtain the optimal action choice in each state. If the policy being optimized is the same as the one the agent is following, the method is called \emph{on-policy}. State–action–reward–state–action (SARSA) is an example of on-policy value-based algorithms \cite{rummery1994line,sutton1995generalization}. On the other hand, if the followed policy differs from the policy being optimized, the algorithm is said to be \emph{off-policy}. Tabular $Q$-learning \cite{watkins1992q} and deep $Q$-learning \cite{mnih2013playing} that uses a deep neural network, known as deep $Q$-network (DQN) instead of a table as the action-value function approximator, are examples of off-policy value-based methods. 

In policy-based RL, the objective is to directly optimize the policy (and not the action-value function) using sampled reward values from the environment. For instance, policy gradient (PG) methods optimize a parameterized policy with respect to the expected return by gradient descent \cite{Peters:2010}. There are also policy-based RL algorithms that do not rely on calculation of gradients, such as the ones using evolutionary strategies or cross-entropy method \cite{kalashnikov2018scalable,lu2022aw}.

It should be noted that many modern model-free RL algorithms do not fit exclusively under one of value-based or policy-based categories. Combining off-policy value-based techniques with policy-based gradient-based strategies, has given rise to a powerful family of model-free RL algorithms known as actor-critic (AC) methods. In AC, optimization of the action-value function guides the agent in improving her policy. After the success of DQN in solving RL tasks with continous state and discrete action spaces, AC methods inspired applying deep learning in tasks with continous action spaces, and in 2015, deep deterministic policy gradient (DDPG) \cite{lillicrap2015continuous} was proposed. Figure~\ref{fig:rl_tax} shows a compact taxonomy of RL algorithms discussed up to now.

\begin{figure}[h] 
\centering
\includegraphics[width=.99\linewidth]{content/images/rl_tax.pdf}
\caption{Categorization of RL algorithms; reproduced with slight modifications from \cite{dong2020deep}.}
\label{fig:rl_tax}
\end{figure}

Since the decentralized MARL algorithm that we will be considering later on is built upon single-agent $Q$-learning, at the end of this section, we provide this algorithm and the conditions required for its convergence. Algorithm~\ref{alg:qlearn-alg} represents the tabular $Q$-learning algorithm for discrete state-action spaces. 

\begin{algorithm}[h]
\caption{Tabular $Q$-learning for Single-Agent RL}
\label{alg:qlearn-alg}
\begin{algorithmic}[1]
\Statex\textbf{Parameters:} set of states $\mathcal{S}$, set of actions $\mathcal{A}$, step size sequence $\{\alpha_t \in (0,1]\}$, an exploration probability $\epsilon \in [0,1)$.
\Statex Initialize $Q(s,a)$ for all $s \in \mathcal{S}$,$a \in \mathcal{A}$ arbitrarily except that $Q(s_{terminal},.)=0$.
\Procedure{Loop for each episode $k$:}{}
\State Randomly select an initial state $s$.
\State \textbf{Repeat} for each state of the episode:
\State \hspace{\algorithmicindent} Choose action $a$ using a GLIE policy derived from $Q$, e.g., $\epsilon$-greedy:
\State \hspace{\algorithmicindent} With probability $\epsilon$ choose a random action $a$.
\State \hspace{\algorithmicindent} Otherwise, $a=\argmax\limits_{a \in \mathcal{A}}Q(s,a)$.
\State \hspace{\algorithmicindent} Take action $a$, obtain reward $a$, and observe the next sate $s'$.
\begin{equation} \label{eq:qlearningupdate}
    Q(s,a) \leftarrow Q(s,a) + \alpha_{t,(s,a)}[r+\gamma\max\limits_{a' \in \mathcal{A}}Q(s',a')-Q(s,a)].
\end{equation} 
\State \hspace{\algorithmicindent} $s \leftarrow s'$.
\State Until $s$ is a terminal state.
\EndProcedure
\end{algorithmic}
\end{algorithm}

To state the convergence criteria for $Q$-learning in finite MDPs, we first introduce an important class of policies:

\begin{definition}[GLIE Policy]
    A learning policy is greedy in the limit with infinite exploration (GLIE) if it satisfies the following properties:
    \begin{enumerate}
        \item $\lim_{t\rightarrow \infty}N_t(s,a)=\infty$ if $\lim_{t\rightarrow \infty}N_t(s)=\infty$; all possible actions in a given state are selected infinitely often if the state is visited infinitely often.
        \item As the number of iterations goes to infinity, the policy converges to a greedy policy with respect to the action-vale ($Q$) function; $\lim_{t\rightarrow \infty}\pi_t=\delta_{\underset{a \in A}{\argmax}(Q_t(s,.))}$, where $\delta_j$ is a vector with all components equal to zero except the index corresponding to $j$ which is equal to one.
    \end{enumerate}
\end{definition}

Following a GLIE policy is an essential condition in the proof of convergence for RL algorithms with bounded estimates. An important policy that could easily satisfy GLIE conditions is the $\epsilon$-greedy policy. In $\epsilon$-greedy, the agent follows a greedy policy with respect to the $Q$-function with probability $1-\epsilon$, and selects a random action with probability $\epsilon$.

\begin{lemma}
    The $\epsilon$-greedy policy satisfies the GLIE conditions if at iteration $t$, $\epsilon_t=\frac{1}{t}$.
\end{lemma}

Now, we can state the convergence criteria for single-agent $Q$-learning \cite{szepesvari1997asymptotic,watkins1992q}:

\begin{theorem} \label{theo:qlearn}
    Given an MDP with finite state-action space, and a single agent following tabular $Q$-learning in Algorithm~\ref{alg:qlearn-alg}, as $t\rightarrow \infty$, $Q_t$ converges to $Q^*$, and $\pi_t$ converges to $\pi^*$ given the following conditions,
    \begin{enumerate}
        \item The agent follows a GLIE policy.
        \item The reward values are bounded; $R_{a_t}(s_t,s_{t+1})\leq D$.
        \item The learning rate satisfies the following properties as the number of episodes goes to infinity: $\sum_{t=1}^{\infty}\alpha_{t,(s,a)}=\infty$, $\sum_{t=1}^{\infty}\alpha_{t,(s,a)}^2<\infty$,\quad$\forall s,a$.
    \end{enumerate}
\end{theorem}


\section[Game Theory]{Game Theory} \label{sec:gt}
Before discussing the concept of multi-agent RL, as it is interrelated with game theory and repeated games, we first give an introductory overview of the main notions in game theory.

Game theory is a branch of mathematics that studies the interaction of multiple decision makers (players) with individual payoff functions whose decisions affect the payoff of other players. In a game, the players try to optimize their respective objective functions, i.e., they are rational, while taking into account the knowledge they have acquired and the expectation they have of the other players' behavior, i.e., they reason and act strategically \cite{osborne1994course}. Although a relatively new field, GT has been found applications in multiple fields, such as economic, military, and political strategic analysis, social sciences and social networks, robotics and multi-agent systems, and optimization of electrical grids and communication networks \cite{bauso2016game}.

The most basic form of a game is an strategic game in which players choose their actions simultaneously once and for all after analyzing the reward function of other players and forming an expectation of their behavior. We may define this type of game as below\footnote{All of the definitions from now on are given for games with discrete action space. Similar definitions can be provided for continous action spaces.}:

\begin{definition}[Strategic Game]
    A strategic game $\mathcal{G}$ can be defined by a tuple of three sets $(\mathcal{N},
\mathcal{A}=\{\mathcal{A}_i|i\in N\},U=\{u_i|i \in N\})$, where
\begin{itemize}
    \item $\mathcal{N}=\{1,2,3,...,n\}$ is a set of $n$ players with their own payoff function to maximize\footnote{Alternatively, we may also assume that players minimize their individual cost functions.}.
    \item $\mathcal{A}_i$ is a set of $m_i$ possible actions that player $i$ could play.
    \item $u_i: \mathcal{A}\rightarrow \mathcal{R}$ is the utility (payoff) function of player $i$ and is dependent on the actions of all players. For the sake of simplicity, we may write $u_i(a_1,a_2,...,a_n)$ as $u_i(a_i,a_{-i})$, \small where $a_{-i}=(a_j)_{j\in \mathcal{N},j\neq i}=(a_1,...,a_{i-1},a_{i+1},...,a_n)$ is the action profile of all players except player $i$.
\end{itemize}
\end{definition}

A common way to solve a strategic game when no communication or cooperation among agents is allowed, is to assume that all players are \emph{rational} and try to maximize their payoff function. By acting rationally, the agents may reach an equilibrium point known as a Nash equilibrium (NE) of the game \cite{nash1951non},


\begin{definition}[Deterministic Nash equilibrium in strategic games]
    An action profile $(a^*_1,a^*_2,...,a^*_n)$ is a deterministic Nash equilibrium of the game if no player can increase her payoff by individually deviating from the profile, i.e.,
    \begin{equation}
        u_i(a^*_i,a^*_{-i})\geq u_i(a_i,a^*_{-i}) \quad \forall a_i \in A_i, i \in N.
    \end{equation}
\end{definition}

We may also define Nash equilibrium using the \emph{best-response (BR)} set,

\begin{definition}[Best-Response Set]
    The best-response set for player $i$ is the action set resulting from the maximization of $u_i$ with respect to other players' strategies,
    \begin{equation}
        BR_i(a_{-i}):= \argmax_{a_i \in A_i}u_i(a_i,a_{-i})
    \end{equation}
\end{definition}

A Nash equilibrium in a strategic game happens when the action selected by all players falls into their respective best-response set,

\begin{equation}
        (a^*_1,a^*_2,...,a^*_n) \in NE(\mathcal{G}) \iff a^*_i \in BR_i(a_{-i}^*), \quad \forall i \in N
\end{equation}
where $NE(\mathcal{G})$ is the set of deterministic Nash equilibria of the strategic game. 
 
The best-response set provides us with a method to calculate deterministic Nash equilibria of a game. We may calculate $BR$ for all players and then find the profiles where $a^*_i \in BR_i(a_{-i}^*)$ for all $i \in N$. This also implies that a game may not possess a \emph{deterministic} Nash equilibrium because such action profile may not exist.

Although a game may not possess a deterministic Nash equilibrium, we may turn to another type of policies known as mixed strategies to extend the notion of Nash equilibrium. For player $i$, we define a mixed strategy over her possible actions as $\pi_i \in \Delta(A_i)$. In other words, $\pi_i$ is a probability distribution over the possible actions of player $i$, and $\pi_i[a^j]$ is the probability of choosing action $a^j$ in the game. Consequently, we may define the expected utility tensor of player $i$ following a mixed strategy as,

\begin{equation} \label{eq:mixedut}
    U_i(\pi^i, \pi^{-i}) = (\pi^i)^T u^i\prod_{j \in N, j\neq i}\pi^{j}
\end{equation}

where $u^i$ is the tensor of the utilities corresponding to deterministic action profiles. Jon Nash proved the following theorem for \emph{finite games} \cite{nash1950equilibrium},

\begin{theorem}[Existence of mixed NE in finite games]
    Every game with a finite set of players and finite strategy sets, admits at least one mixed Nash equilibrium profile $(\pi^i_*, \pi^{-i}_*)$ where,
    \begin{equation}
        U_i(\pi^i_*, \pi^{-i}_*) > U_i(\pi^i, \pi^{-i}_*), \quad \forall i, \pi^i
    \end{equation}
\end{theorem}

\noindent\textbf{Comment.} In this thesis, the terms player, utility/payoff, strategy, and learning dynamics are respectively equivalent to the terms agent, reward, policy, and learning algorithm, and are used interchangably. The first set of terms are more common in the game theory and learning in games literature, while the second set is usually used in ML/RL literature.

It should be noted that the concept of Nash equilibrium is defined in the context of non-cooperative games where agents do not cooperate with each other and are completely selfish. In such a setting, there may exist other action profiles where both agents can gain more than the Nash equilibrium of the game, yet they cannot reach that profile without cooperation. A famous example of such a game is the two-player prisoner's dilemma (Table~\ref{tab:prison}) where the green payoff cell is not achievable when following the rationality principle because each agent has an individual motivation to change her strategy and gain the payoff equal to $4$, and the only Nash equilibrium in this setting is the red cell.


\begin{table}[h]
\begin{center}
\centering
\caption{Two-player prisoner's dilemma}
\begin{tabular}{c|c|c|}
\cline{2-3}
\begin{tabular}[c]{@{}c@{}}P2\\ P1\end{tabular} & Confess                                       & Don't confess                                       \\ \hline
\multicolumn{1}{|c|}{Confess}                        & {\color[HTML]{32CB00} \textbf{3, 3}}                                & 0, 4 \\ \hline
\multicolumn{1}{|c|}{Don't confess}                        & 4, 0 & {\color[HTML]{FE0000} \textbf{1, 1}}                                 \\ \hline
\end{tabular}
\label{tab:prison}
\end{center}
\end{table}

We now introduce two important classes of games that have also been studied in the context of repeated games and multi-agent RL; zero-sum games, and potential games \cite{monderer1996potential}.

\begin{definition}[\small Two-player zero-sum game]A two-player game is zero-sum if the sum of two players' payoffs for each possible action profile is equal to zero\footnote{This class of games can be considered the purest form of non-cooperative games as there is absolutely no incentive for the players to cooperate with each other \cite{bauso2016game}.},
    \begin{equation}
        u_1(a_1, a_2) + u_2(a_1, a_2) = 0, \quad \forall (a_1, a_2) \in A_1\times A_2
    \end{equation}
\end{definition}

\begin{definition}[Potential game]
    A game $(N, A=\{\mathcal{A}_i\},U=\{u_i\})$ is (exact) potential, if there exists a potential function, $\Phi:\mathcal{A}\rightarrow \mathbb{R}$, s.t.,
    \begin{equation}
        u_i(a_i, a_{-i}) - u_i(a_i', a_{-i}) = \Phi(a_i, a_{-i})-\Phi(a_i', a_{-i}), \quad \forall i \in N
    \end{equation}
\end{definition} 

In a potential game, the change in the utility of player $i$, when changing her action unilaterally is proportional to the variation in the potential function. As discussed in \autoref{chap:intro}, potential games are capable of modeling several practical and real-world scenarios. Because the incentive of all players are mapped into a single function, the pure Nash equilibria of the game correspond to the local minima of the potential function. This is an important property that is used in studying convergence of learning dynamics to Nash equilibria in repeated games. Indeed, in the real world, games are not normally played once, and players have to play a game with \emph{partial observability} repeatedly and learn an optimal strategy. Partial observability implies a player may not be fully-rational, she may not be aware of her reward function and even may not be able to observe other players' actions and rewards during the game. To analyze the game dynamics and the equilibria that the game may converge to in the long run in such settings, we can turn to algorithms designed for learning strategies in repeated games \cite{fudenberg1998theory}. When players adopt a learning strategy, they may not necessarily converge to a Nash equilibrium, or they may converge to an approximate Nash equilibrium when the number of iterations of the game is limited. Therefore, we may define an $\epsilon-$Nash equilibrium as

\begin{theorem}[$\epsilon-$Nash equilibrium]
    A mixed strategy profile $(\pi^i_*, \pi^{-i}_*)$ is an $\epsilon$-Nash equilibrium if
    \begin{equation}
        U_i(\pi^i_*, \pi^{-i}_*) \geq U_i(\pi^i, \pi^{-i}_*)-\epsilon, \quad \forall i, \pi^i,
    \end{equation}
\end{theorem}

and a Nash equilibrium happens when $\epsilon$ is zero.

An important algorithm for learning in repeated games is fictitious play \cite{brown1951iterative}. In fictitious play, each player has full observability over her own reward function. However, she can only observe the actions of other players at each iteration, and not the reward they get. Each player assumes that other players follow a stationary mixed strategy, and at each round, she plays her best response to the empirical frequency of the previous actions played by her opponents. In other words, at each iteration, she gives a weight equal to the frequency of actions played by other players. Therefore, the the probability player $i$ assigns to player $-i$ for playing $a^{-i}_j$ will be,

\begin{equation}
    \gamma^i_t(a^{-i}_j) = \frac{\eta_t^i(a^{-i}_j)}{\sum_{a^{-i}_k \in A^{-i}}\eta_t^i(a^{-i}_k)}
\end{equation}

where $\eta_t^i(a^{-i}_k)$ is the number of times that player $-i$ has played $a^{-i}$ up to iteration $t$. $\eta^i$ can be considered a mixed strategy profile for player $-i$. At each round, player $i$ plays her best response with respect to the mixed utility calculated over $\eta^i$,

\begin{equation}
        BR_i(\eta^i):= \argmax_{a_j \in A_i}U_i(\delta_j,\eta^i)
\end{equation}

where $\delta_j$ is a vector with all components equal to zero except the index corresponding to $j$ which is equal to one.

Fictitious play has been proven to converge to a pure Nash equilibrium in many classes of games, including any two-player game with a generic payoff matrix \cite{berger2005fictitious} and potential games with arbitrary number of actions and players \cite{monderer1996potential}.

Since deterministic best response in fictitious play may change abruptly (discretely), in case of a mixed Nash equilibrium, the actual behavior overtime may not converge to the equilibrium, even though the beliefs converge to one \cite{hofbauer2002global}. To avoid such a problem, stochastic fictitious play was introduced by Fudenberg and Kreps \cite{fudenberg1993learning}, in which the deterministic BR is substituted by perturbed BR dynamics. In perturbed BR, the player payoffs are perturbed with a random noise at each iteration. Perturbed BR is proven to converge to a pure Nash equilibrium in zero-sum, potential, and supermodular games as the noise vector corresponding to each player's payoff becomes sufficiently small \cite{hofbauer2002global}.

\section[Multi-agent RL]{Multi-agent RL}
Unlike single-agent RL where the dynamics of the environement was only determined by the actions of a single player, in MARL, the evolution of the environment and the reward that each agent receives is dependent not only on her action, but on the actions of all players. Apart from this difference, each agent is again assumed to solve a decision-making problem sequentially, and through trial and error. Due to the involvement of multiple decision makers, it is reasonable to model a MARL problem using a game-theoretic framework, known as a stochastic (Markov) game \cite{shapley1953stochastic,littman1994markov}:

\begin{definition}[Stochastic (Markov) game] \label{def:pg}
    A stochastic (Markov) game\footnote{It is important to distinguish between stochastic games where agents make their decisions simultaneously, and extensive-form or tree games where agents take their actions sequentially after observing the actions of previous players.} is defined by extending the definition of MDP to a multi-player setting, and therfore can be described using a tuple of five key elements $(N, \mathcal{S},\mathcal{A}=\{\mathcal{A}_i|i\in N\},\mathcal{P},R=\{R_i|i \in \mathcal{N}\})$, where,
\begin{itemize}
    \item $\mathcal{N}=\{1,2,3,...,n\}$ is a set of $n$ players.
    \item $\mathcal{S}$ is a set representing the different states of the game, and is shared by all players.
    \item $\mathcal{A}_i$ is a set of $m_i$ possible actions that player $i$ could play at each state.
    \item $\mathcal{P}:\mathcal{S}\times \mathcal{A}\rightarrow \Delta(\mathcal{S})$ is a probability mapping that at time step $t \in \mathbb{N}$ gives the transition probabilities of the agents going from state $s \in \mathcal{S}$ to the next state $s' \in \mathcal{S}$ at time step $t+1$ given the action profile $(a_1,...,a_n) \in \mathcal{A}$.
    \item $\mathcal{R}: \mathcal{S}\times \mathcal{A}\times\mathcal{S}\rightarrow R$ is the reward function that returns a bounded scalar in the range $[-R_{max},R_{max}]$ to each agent as a result of the action profile $(a_1,...,a_n)$ taken in state $s$ and the transition to $s'$.
\end{itemize}
\end{definition}

Based on this definition, every state of a stochastic game (SG) can be viewed as a normal-form game with the important caveat that after taking actions, the agents may transit to a different state based on the transition probability matrix.


There are generally two different paradigms when approaching an MARL problem. The first one is coordinated (centralized) MARL in which a central coordinator has full observability over the joint actions, rewards, and observations of all agents, and it coordinates their behavior in order to optimize their individual policy and achieve an equilibrium profile. This setting requires either a simulation of the game or an express two-way connection between the agents and the controller, and considering the task of the controller, it usually needs to have a high computational capacity that grows with the number of agents. Up to now, the centralized paradigm has been the focus of many seminal works in MARL \cite{vinyals2019grandmaster,silver2017mastering,hessel2018rainbow,lowe2017multi}.

Centralized MARL deprives agents of their autonomy and competitive drive that are important factors in non-cooperative games. Indeed, in many practical multi-agent scenarios, such as decision making in economics \cite{friedman1998economic}, the nature of the game and the competition present, dictates that the agents take their actions independently and without coordination. Furthermore, the scale and complexity of a game that increases with the number of players, e.g., in large-scale robot systems \cite{robinson1951iterative}, motivates the use of distributed algorithms. The second paradigm in MARL is decentralized and based on independent decision making of individual agents. The main benefits of this paradigm are better scalability of the algorithm, and a reduction in computational cost, both of which are the results of eliminating the central controller. Furthermore, users may not be inclined to share their personal data with a coordinator server, and therefore, decentralized techniques may also be beneficial in terms of privacy. Before discussing the existing algorithms and methods in decentralized MARL, we discuss an important challenge that any MARL algorithm needs to address.

Unlike single-agent RL where the evolution of the environment is only a function of the single agent's behavior, in MARL, the joint policy of all participating agents shape the environment dynamics. Coupling this joint dependence with the fact that agents do not have access to other agents' policies gives rise to the \emph{non-stationarity} challenge in MARL. From a single agent's prespective, the environment dynamics is dependent on hidden and observable variables which makes independent policy optimization and decision making difficult. Adopting the centralized paradigm is an evident way to deal with non-stationarity \cite{papoudakis2019dealing,iqbal2019coordinated,lowe2017multi}. Therefore, in the next section, we examine the methods that deal with this challenge in the decentralized paradigm.

\section[Dealing with Non-stationarity in Decentralized MARL]{Dealing with Non-stationarity in Decentralized MARL}

Hernandez-Leal et al. \cite{hernandez2017survey} provides an interesting categorization for the techniques that decentralized MARL algorithms use to deal with non-stationarity. The first technique is ignoring the non-stationarity of the environment, and acting as if the opponents are playing a stationary strategy. This approach may easily fail to capture an optimal strategy if the opponents alter their policies. In the second category, called \emph{forget}, the agents continuously update their value estimates or policies based on recent observations, and therefore, forget about the information in the past. The third and fourth categories rely on communication channels between agents, or a higher degree of observability, to respond to the respond to target opponents  \cite{greenwald2003correlated,hernandez2017learning}, or learn models of the opponents \cite{foerster2016learning,losey2020learning}. The last category is based on theory of mind and recursive reasoning where the agent assumes that the opponent is strategically modeling her and creates her best response set based on recursive reasoning \cite{gmytrasiewicz2005framework,wunder2012framework}. 

Our area of interest in this thesis is the second category, \emph{forget}. These algorithms are mostly model-free as they are usually based on iterative updates of value and $Q$ functions, and policies. One approach that these algorithms use to deal with non-stationarity is asymmetric and variable step sizes for different agents to continuously adjust to opponents' behavior \cite{bowling2002multiagent,guo2021decentralized,zhao2021provably}. Another approach is two-timescale learning \cite{leslie2003convergent,sayin2021decentralized} to create periodic local stationary environments for agents. We particularly focus on this approach and the one proposed by Sayin et al. \cite{sayin2021decentralized} in decentralized $Q$-learning dynamics. In this dynamics, in the faster timescale, the environement can be assumed to be \emph{locally} stationary from an agent's prespective, while it changes in the background with the slow timescale updates.