# Asynchronous Decentralized Q-Learning: Two Timescale Analysis By
Persistence††thanks: An earlier version of this work containing preliminary
results has been accepted for presentation at the 2023 IEEE Conference on
Decision and Control.

Bora Yongacoglu Department of Mathematics and Statistics, Queen’s University
Gürdal Arslan Department of Electrical Engineering, University of Hawaii at
Manoa Serdar Yüksel22footnotemark: 2

###### Abstract

Non-stationarity is a fundamental challenge in multi-agent reinforcement
learning (MARL), where agents update their behaviour as they learn. Many
theoretical advances in MARL avoid the challenge of non-stationarity by
coordinating the policy updates of agents in various ways, including
synchronizing times at which agents are allowed to revise their policies.
Synchronization enables analysis of many MARL algorithms via multi-timescale
methods, but such synchrony is infeasible in many decentralized applications.
In this paper, we study an asynchronous variant of the decentralized
Q-learning algorithm, a recent MARL algorithm for stochastic games. We provide
sufficient conditions under which the asynchronous algorithm drives play to
equilibrium with high probability. Our solution utilizes constant learning
rates in the Q-factor update, which we show to be critical for relaxing the
synchrony assumptions of earlier work. Our analysis also applies to
asynchronous generalizations of a number of other algorithms from the regret
testing tradition, whose performance is analyzed by multi-timescale methods
that study Markov chains obtained via policy update dynamics. This work
extends the applicability of the decentralized Q-learning algorithm and its
relatives to settings in which parameters are selected in an independent
manner, and tames non-stationarity without imposing the coordination
assumptions of prior work.

###### keywords:

Multi-agent reinforcement learning, independent learners, learning in games,
stochastic games, decentralized systems

91A15, 91A26, 60J20, 93A14

Bora Yongacoglu Department of Mathematics and Statistics, Queen’s University
Gürdal Arslan Department of Electrical Engineering, University of Hawaii at
Manoa Serdar Yüksel11footnotemark: 1

##  1 Introduction

Multi-agent systems are characterized by the coexistence of several autonomous
agents acting in a shared environment. In multi-agent reinforcement learning
(MARL), agents in the system change their behaviour in response to feedback
information received in previous interactions, and the system is non-
stationary from any one agent’s perspective. In this non-stationary
environment, agents attempt to optimize their performance against a moving
target [12]. This non-stationarity has been identified as one of the
fundamental technical challenges in MARL [11]. In contrast to the rich
literature on single-agent learning theory, the theory of MARL is relatively
underdeveloped, due in large part to the inherent challenges of non-
stationarity and decentralized information.

This paper considers learning algorithms for stochastic games, a common
framework for studying MARL in which the cost-relevant history of the system
is summarized by a state variable. We focus on stochastic games in which each
agent fully observes the system’s state variable but does not observe the
actions of other agents, exacerbating the challenge of non-stationarity.

Early theoretical work on MARL in stochastic games avoided the problem of non-
stationarity by studying applications in which joint actions were observed by
all agents [22, 21, 13]. There has also been interest in the _local action
learner_ setting, where actions are not shared between agents. Several
rigorous contributions have recently been made in this setting, including the
works of [1, 6, 31, 36, 37], to be discussed shortly.

Of the recent advances in MARL for the local action learner setting, many of
the algorithms with strong guarantees have circumvented the challenge of non-
stationarity by relying, implicitly or explicitly, on coordination between
agents. In particular, several works in the _regret testing_ tradition rely on
some form of synchrony, whereby agents agree on the times at which they may
revise their behaviour and are constrained to fix their policies during the
intervening periods. This synchronized approach allows for the use of two
timescale analyses common to many single- and multi-agent reinforcement
learning paradigms, in which the behaviour of value function estimates and the
behaviour of the joint policy process can be effectively uncoupled and
analyzed separately [18, 3, 15].

A variety of regret testing algorithms have been proposed for different
classes of games, including [9, 10, 1] and [37]. These algorithms differ in
their policy update rules, which are typically chosen to exploit some
underlying structure of particular classes of games, from better/best-response
dynamics in [1] to arbitrary $\epsilon$-satisficing policy update rules in
[37]. Despite such differences, previous regret testing algorithms are united
in their reliance on synchrony to facilitate the analysis of learning iterates
and to guarantee accuracy of value function estimates. While this is
justifiable in some settings, it can be restrictive in others, including
applications where parameters are selected independently. As such, it would be
desirable to provide MARL algorithms that do not require synchrony but still
come with rigorous performance guarantees in the local action learner setting.

This paper studies weakly acyclic stochastic games, where the definition of
weak acyclicity is in terms of single-agent best-responding. In this context,
our aim is to give guarantees of convergence stationary deterministic
equilibrium policies. We find that, with slight modification, the
decentralized Q-learning algorithm of [1] can be made to tolerate asynchrony
in the policy updates of players, and that strong coordination assumptions
about parameter choice and timing are not necessary. This constitutes a direct
generalization of the algorithm and results in [1]. The key modification
involves utilizing constant learning rates in the Q-function updates,
replacing the decreasing learning rates used in [1] and in all previous regret
testing algorithms. Unlike decreasing learning rates, which place relatively
large weight on data encountered in the distant past, constant learning rates
allow agents to rapidly correct their Q-factor estimates by discarding
outdated information. Additionally, we retain the use of random inertia in the
policy update, which we show acts as a decentralized stabilizing mechanism.
These two algorithmic components combine to enable analysis that is
essentially two timescale in nature.

Although the technical exposition here focuses on weakly acyclic games, the
analytic insights in this paper are not limited to this setting. In fact, the
results of this paper can be generalized in various directions by studying
different classes of games, different policy revision mechanisms, or by
selecting different sets of policies as the target for convergence. We now
list several other regret testing results that can be generalized to
accommodate for asynchronous agents by employing constant learning rates and
inertia in the policy update.

Teams and Optimality. Stochastic teams and their generalizations of common
interest games constitute an important special case of weakly acyclic games,
with applications to distributed control [36]. In common interest games, one
typically seeks _team optimal policies_ , a subset of equilibrium policies
that simultaneously achieves minimum cost for each player and may not exist in
more general classes of games. A modification of the decentralized Q-learning
algorithm was proposed in [36], which incorporated memory to account for past
performance as well as random search of players’ policy spaces to search for
team optimal policies. This algorithm, however, was developed in the
synchronized setting, where the analysis of learning iterates was decoupled
from policy dynamics. This algorithm can be further adapted to accommodate
asynchrony by utilizing constant learning rates.

General games and $\epsilon$-equilibrium. Rather than restricting players to
revise policies via inertial best-responding, one may be interested in more
general revision mechanisms, to model settings where players are more
exploratory in nature. If one imposes a stopping condition, such as refraining
from updating when one is already $\epsilon$-best-responding, then the policy
dynamics can be studied using the theory of _$\epsilon$ -satisficing paths_
presented by [37]. In [37], it was shown that a synchronized variant of
decentralized Q-learning, which used random search of the policy space when
not $\epsilon$-best-responding, drove policies to $\epsilon$-equilibrium in
symmetric stochastic games. With appropriate modifications, a similar result
can be obtained without assuming synchrony.

General games and cumber sets. In general stochastic games, the set of
stationary deterministic equilibrium policies can be empty. Even if this set
is not empty, in general, it is not guaranteed that inertial best-response
dynamics drives play to equilibrium. The notions of _cusber_ sets (introduced
in [14]) and _cumber_ sets ([36]) are useful for studying the dynamics of
inertial best-responding in general games. Cusber sets are subsets of policies
that are closed under single-agent best-responses, while cumber sets are
defined as being closed under multi-agent best-responses. It was previously
shown in [36] that variants of decentralized Q-learning drive play to minimal
cumber sets even in general games, though play may cycle between several
policies within this minimal set. The results of the present paper can be
combined with the analysis of [36] to guarantee convergence of asynchronous
decentralized Q-learning to cumber sets in general games.

Contributions: In this paper, we offer persistent learning via non-decreasing
learning rates as a solution for synchrony assumptions commonly made in the
regret testing paradigm of MARL. We provide mathematical details for a
particular set-up involving the asynchronous variant of the decentralized
Q-learning algorithm of [1], a recent MARL algorithm designed for weakly
acyclic stochastic games, a class of games that admits teams and potential
games as important special cases. We do not impose synchronization of policy
revision times, which is a common and restrictive assumption in prior work. We
show that persistent learning provides a mechanism for taming non-stationarity
_without_ coordinating agents’ parameter choices ahead of play. In particular,
we show that this algorithm drives policies to equilibrium with arbitrarily
high probability, under appropriate parameter selection. As we discuss below
in Section 3, this appears to be the first formal analysis of an asynchronous
algorithm in the _regret testing_ tradition. We also note that the same
analysis can be adapted and applied to a variety of related learning
algorithms, which all impose the synchrony condition and are analyzed via
multi-timescale methods. Thus, the results of this paper establish that
persistent learning can address asynchrony in a variety of multi-agent
learning environments above and beyond weakly acyclic games.

Notation: For a standard Borel space $A$, we let $\mathcal{P}(A)$ denote the
set of probability measures on $A$ with its Borel $\sigma$-algebra. For
standard Borel spaces $A$ and $B$, we let $\mathcal{P}(A|B)$ denote the set of
transition kernels on $A$ given $B$. For a finite set $A$, we let
$\mathbb{R}^{A}$ denote the set of functions from $A$ to $\mathbb{R}$, and we
let $\text{Unif}(A)$ denote the uniform probability distribution on $A$. We
let $\mathbb{Z}_{\geq 0}$ denote the set of non-negative integers. To denote
that a random variable $X$ has distribution $\mu$, we write $X\sim\mu$.

Terminology: We use the terms _player_ and _agent_ interchangeably. When
considering a particular player and referring to other players in the same
game, these other players may be variously called _counterparts_ or
_counterplayers_.

###  1.1 Organization

The remainder of the paper is organized as follows. In Section 2, we present
the model of stochastic games. Related work is surveyed in Section 3. In
Section 4, we present the asynchronous decentralized Q-learning algorithm and
we state our main result, Theorem 4.1, on high probability guarantees for
equilibrium in weakly acyclic stochastic games. The proof of Theorem 4.1 is
presented in Section 5. The results of a simulation study are presented in
Section 6, and the final section concludes.

##  2 Model

A stochastic game $\mathcal{G}$ is described by a list:

(1)
$\mathcal{G}=\left(\mathcal{N},\mathbb{X},\\{\mathbb{U}^{i},c^{i},\beta^{i}:i\in\mathcal{N}\\},P,\nu_{0}\right).$

The components of $\mathcal{G}$ are as follows:
$\mathcal{N}=\\{1,2,\dots,N\\}$ is a finite set of $N$ agents. The set
$\mathbb{X}$ is a finite set of system states. For each player
$i\in\mathcal{N}$, $\mathbb{U}^{i}$ is $i$’s finite set of actions. We write
$\textnormal{{U}}=\times_{i\in\mathcal{N}}\mathbb{U}^{i}$, and refer to
elements of U as _joint actions_. For each player $i$, a function
$c^{i}:\mathbb{X}\times\textnormal{{U}}\to\mathbb{R}$ determines player $i$’s
stage costs, which are aggregated using a discount factor $\beta^{i}\in[0,1)$.
The initial system state has distribution $\nu_{0}\in\mathcal{P}(\mathbb{X})$,
and state transitions are governed by a transition kernel
$P\in\mathcal{P}(\mathbb{X}|\mathbb{X}\times\textnormal{{U}})$.

At time $t\in\mathbb{Z}_{\geq 0}$, the state variable is denoted by $x_{t}$,
and each player $i$ selects an action $u^{i}_{t}\in\mathbb{U}^{i}$ according
to its policy, to be described shortly. The joint action at time $t$ is
denoted $\textnormal{{u}}_{t}$. Each player $i$ then incurs a cost
$c^{i}_{t}:=c^{i}(x_{t},\textnormal{{u}}_{t})$, and state variable evolves
according to $x_{t+1}\sim P(\cdot|x_{t},\textnormal{{u}}_{t})$. This process
is then repeated at time $t+1$, and so on.

A policy for player $i$ is an action selection rule that, at each time $t\geq
0$, selects player $i$’s action $u^{i}_{t}$ in some (possibly random) manner
that depends only on information locally available to player $i$ at time $t$.
Using $h^{i}_{t}$ to denote the information that is locally available to
player $i$ at time $t$, the following standing assumption specifies the
decentralized information structure considered in this paper.

######  Assumption 1 (Local action learners).

For each $i\in\mathcal{N}$, player $i$’s information variables
$\\{h^{i}_{t}\\}_{t\geq 0}$ are given by $h^{i}_{0}=x_{0}$ and

$h^{i}_{t+1}=\left(h^{i}_{t},u^{i}_{t},c^{i}(x_{t},\textnormal{{u}}_{t}),x_{t+1}\right),\text{
for }t\geq 0.$

Under this information structure, each player $i$ observes the complete system
state without noise, and additionally observes its own actions and its own
cost _realizations,_ but does not observe the actions of other players
directly. This _local action learner_ (LAL) information structure is common in
the literature in MARL, with examples such as [1, 5, 6, 25, 31, 36, 37], and
is sometimes called the independent learning paradigm.111This terminology is,
however, not uniform, as independent learning has also recently been used to
refer to learners that update their policies in a (perhaps myopic) self-
interested manner [30]. In response to the changing conventions, we recommend
that learners who condition only on their local action history should be
called local action learners, in analogy to joint action learners. The LAL
paradigm is one of the principal alternatives to the joint action learner
(JAL) paradigm, studied previously in [20] and [21] among others. The key
difference is that the JAL paradigm assumes that each agent $i$ gets to
observe the complete joint action profile $\textnormal{{u}}_{t}$ after it is
played; i.e.
$h^{i}_{t+1}=(h^{i}_{t},\textnormal{{u}}_{t},c^{i}(x_{t},\textnormal{{u}}_{t}),x_{t+1})$.

######  Definition 2.1.

For $i\in\mathcal{N}$ and $t\geq 0$, let
$H^{i}_{t}:=\mathbb{X}\times\left(\mathbb{U}^{i}\times\mathbb{R}\times\mathbb{X}\right)^{t}$.
A sequence $\pi^{i}=(\pi^{i}_{t})_{t\geq 0}$ is called a _policy_ for player
$i$ if $\pi^{i}_{t}\in\mathcal{P}(\mathbb{U}^{i}|H^{i}_{t})$ for each $t\geq
0$.

We let $\Gamma^{i}$ denote player $i$’s set of policies. When following a
policy $\pi^{i}=(\pi^{i}_{t})_{t\geq 0}$, player $i$ selects actions according
to $u^{i}_{t}\sim\pi^{i}_{t}(\cdot|h^{i}_{t})$.

In general, action selection can incorporate randomness, and players may use
arbitrarily complicated, history-dependent policies. However, our analysis
will focus on stationary (Markov) policies, a subset of policies that randomly
select actions in a time invariant manner that conditions only on the
currently observed state variable. Such a restriction entails no loss in
optimality for a particular player, provided the remaining players also use
stationary policies. Focusing on stationary policies is quite natural: we
refer the reader to [19] for an excellent elaboration.

######  Definition 2.2.

For $i\in\mathcal{N}$, a policy $\pi^{i}\in\Gamma^{i}$ is called _stationary_
, if the following holds for any $t,k\geq 0$ and any $\hat{h}^{i}_{t}\in
H^{i}_{t},\bar{h}^{i}_{k}\in H^{i}_{k}$:

$\hat{x}_{t}=\bar{x}_{k}\Rightarrow\pi^{i}_{t}(\cdot|\hat{h}^{i}_{t})=\pi^{i}_{t}(\cdot|\bar{h}^{i}_{k}),$

where $\hat{x}_{t}$ and $\bar{x}_{k}$ denote the final components of
$\hat{h}^{i}_{t}$ and $\bar{h}^{i}_{k}$, respectively.

The set of stationary policies for player $i\in\mathcal{N}$ is denoted
$\Gamma^{i}_{S}$ and we identify $\Gamma^{i}_{S}$ with
$\mathcal{P}(\mathbb{U}^{i}|\mathbb{X})$, the set of transition kernels on
$\mathbb{U}^{i}$ given $\mathbb{X}$. Henceforth, unqualified reference to a
policy shall be understood to mean a stationary policy, while non-stationary
policies will be explicitly identified as such.

######  Definition 2.3.

For $i\in\mathcal{N}$, $\xi>0$, a policy $\pi^{i}\in\Gamma^{i}_{S}$ is called
_$\xi$ -soft_ if $\pi^{i}(a^{i}|x)\geq\xi$ for all
$(x,a^{i})\in\mathbb{X}\times\mathbb{U}^{i}$. A policy
$\pi^{i}\in\Gamma^{i}_{S}$ is called _soft_ if it is $\xi$-soft for some
$\xi>0$.

######  Definition 2.4.

A policy $\pi^{i}\in\Gamma^{i}_{S}$ is called _deterministic_ if for each
$x\in\mathbb{X}$, there exists $a^{i}\in\mathbb{U}^{i}$ such that
$\pi^{i}(a^{i}|x)=1$.

The set of deterministic stationary policies for player $i$ is denoted by
$\Gamma^{i}_{SD}$ and is identified with the set of functions from
$\mathbb{X}$ to $\mathbb{U}^{i}$.

Notation: We let $\bm{\Gamma}_{S}:=\times_{i\in\mathcal{N}}\Gamma^{i}_{S}$
denote the set of joint policies. To isolate player $i$’s component in a
particular joint policy $\bm{\pi}\in\bm{\Gamma}_{S}$, we write
$\bm{\pi}=(\pi^{i},\bm{\pi}^{-i})$, where $-i$ is used in the agent index to
represent all agents other than $i$. Similarly, we write the joint policy set
as $\bm{\Gamma}_{S}=\Gamma_{S}^{i}\times\bm{\Gamma}_{S}^{-i}$, and so on.

For any joint policy $\bm{\pi}$ and initial distribution
$\nu\in\mathcal{P}(\mathbb{X})$, there is a unique probability measure on the
set of state-action trajectories
$(\mathbb{X}\times\textnormal{{U}})^{\infty}$. We denote this measure by ${\rm
Pr}^{\bm{\pi}}_{\nu}$, and let $E^{\bm{\pi}}_{\nu}$ denote its expectation. We
use this to define player $i$’s value function:

$J^{i}(\bm{\pi},\nu):=E^{\bm{\pi}}_{\nu}\left[\sum_{t=0}^{\infty}\beta^{t}c^{i}_{t}\right]=E^{\bm{\pi}}_{\nu}\left[\sum_{t=0}^{\infty}\beta^{t}c^{i}(x_{t},\textnormal{{u}}_{t})\right].$

When $\nu=\delta_{s}$ is the Dirac measure of some state $s\in\mathbb{X}$, we
write $J^{i}(\bm{\pi},s)$ instead of $J^{i}(\bm{\pi},\delta_{s})$. For
$\bm{\pi}=(\pi^{i},\bm{\pi}^{-i})$, we will also write
$J^{i}(\pi^{i},\bm{\pi}^{-i},\nu)$ to isolate the role of $\pi^{i}$.

######  Definition 2.5.

Let $\epsilon\geq 0$, $i\in\mathcal{N}$. A policy $\pi^{*i}\in\Gamma^{i}_{S}$
is called an $\epsilon$-_best-response to
$\bm{\pi}^{-i}\in\bm{\Gamma}^{-i}_{S}$_ if, for every $s\in\mathbb{X}$,

$J^{i}(\pi^{*i},\bm{\pi}^{-i},s)\leq\inf_{\tilde{\pi}^{i}\in\Gamma^{i}}J^{i}(\tilde{\pi}^{i},\bm{\pi}^{-i},s)+\epsilon.$

The set of $\epsilon$-best-responses to $\bm{\pi}^{-i}$ is denoted ${\rm
BR}^{i}_{\epsilon}(\bm{\pi}^{-i})\subseteq\Gamma^{i}_{S}$. It is well-known
that for any $\bm{\pi}^{-i}\in\bm{\Gamma}^{-i}_{S}$, player $i$’s set of
0-best-responses ${\rm BR}^{i}_{0}(\bm{\pi}^{-i})$ is non-empty, and the
infimum above is in fact attained by some policy in $\Gamma^{i}_{S}$.
Furthermore, for any $\bm{\pi}^{-i}\in\bm{\Gamma}^{-i}_{S}$, we have that the
set of deterministic 0-best-responses is also non-empty:
$\Gamma^{i}_{SD}\cap{\rm BR}^{i}_{0}(\bm{\pi}^{-i})\not=\varnothing$.

######  Definition 2.6.

Let $\epsilon\geq 0$. A joint policy $\bm{\pi}^{*}\in\bm{\Gamma}_{S}$ is
called an _$\epsilon$ -equilibrium_ if $\pi^{*i}\in{\rm
BR}^{i}_{\epsilon}(\bm{\pi}^{*-i})$ for all $i\in\mathcal{N}$.

For $\epsilon\geq 0$, we let
$\bm{\Gamma}^{\epsilon{\rm\text{-}eq}}_{S}\subseteq\bm{\Gamma}_{S}$ denote the
set of $\epsilon$-equilibrium policies. It is known that the set
$\bm{\Gamma}^{0{\rm\text{-}eq}}_{S}$ is non-empty [7]. We also let
$\bm{\Gamma}^{\epsilon{\rm\text{-}eq}}_{SD}\subseteq\bm{\Gamma}_{SD}$ denote
the subset of stationary deterministic $\epsilon$-equilibrium policies, which
may be empty in general.

###  2.1 Weakly Acyclic Stochastic Games

We now introduce weakly acyclic games, an important subclass of games that
will be the main focus of this paper.

######  Definition 2.7.

A sequence $\\{\bm{\pi}_{k}\\}_{k\geq 0}$ in $\bm{\Gamma}_{SD}$ is called a
_strict best-response path_ if for any $k\geq 0$ there is a unique player
$i\in\mathcal{N}$ such that $\pi^{i}_{k+1}\not=\pi^{i}_{k}$ and
$\pi^{i}_{k+1}\in{\rm BR}^{i}_{0}(\bm{\pi}^{-i}_{k})$.

######  Definition 2.8.

The stochastic game $\mathcal{G}$ is weakly acyclic if (i)
$\bm{\Gamma}^{0{\rm\text{-}eq}}_{SD}\not=\varnothing$, and (ii) for any
$\bm{\pi}_{0}\in\bm{\Gamma}_{SD}$, there is a strict best-response path from
$\bm{\pi}_{0}$ to some $\bm{\pi}^{*}\in\bm{\Gamma}^{0{\rm\text{-}eq}}_{SD}$.

The multi-state formulation above was stated in [1], though weakly acyclic
games had previously been studied in stateless games [38]. An important
special case is that of stochastic teams, where $c^{i}=c^{j}$ and
$\beta^{i}=\beta^{j}$ for any players $i,j\in\mathcal{N}$, and the interests
of all agents are perfectly aligned. Markov potential games with finitely many
states constitute another special case of weakly acyclic games [28, 16, 39].

###  2.2 Q-Functions in Stochastic Games

In the stochastic game $\mathcal{G}$, when the other players use a stationary
policy $\bm{\pi}^{-i}\in\bm{\Gamma}^{-i}_{S}$, player $i$ faces an environment
that is equivalent to a single-agent MDP. The MDP in question depends on the
policy $\bm{\pi}^{-i}$ as well as the game $\mathcal{G}$, and (stationary
Markov) optimal policies for this MDP are equivalent to 0-best-responses to
$\bm{\pi}^{-i}$ in the game $\mathcal{G}$.

Player $i$’s best-responses to a policy $\bm{\pi}^{-i}\in\bm{\Gamma}^{-i}_{S}$
can be characterized using an appropriately defined _Q-function_ ,
$Q^{*i}_{\bm{\pi}^{-i}}:\mathbb{X}\times\mathbb{U}^{i}\to\mathbb{R}$.222We use
the terms Q-function and (state-) action-value function interchangeably. The
function $Q^{*i}_{\bm{\pi}^{-i}}$ can be defined by a fixed point equation of
a Bellman operator, but here we give an equivalent definition in terms of the
optimal policy of the corresponding MDP:

$Q^{*i}_{\bm{\pi}^{-i}}(x,a^{i}):=E^{\bm{\pi}^{*}}_{\nu}\left[\sum_{t=0}^{\infty}(\beta^{i})^{t}c^{i}(x_{t},\textnormal{{u}}_{t})\middle|x_{0}=x,u^{i}_{0}=a^{i}\right],$

for all $(x,a^{i})\in\mathbb{X}\times\mathbb{U}^{i},$ where
$\bm{\pi}^{*}=(\pi^{*i},\bm{\pi}^{-i})$ and $\pi^{*i}\in{\rm
BR}^{i}_{0}(\bm{\pi}^{-i})\cap\Gamma^{i}_{SD}.$

######  Definition 2.9.

For $Q^{i}:\mathbb{X}\times\mathbb{U}^{i}\to\mathbb{R}$ and $\epsilon\geq 0$,
we define

$\widehat{{\rm
BR}}^{i}_{\epsilon}(Q^{i}):=\left\\{\pi^{*i}\in\Gamma^{i}_{SD}:Q^{i}(x,\pi^{*i}(x))\leq\min_{a^{i}\in\mathbb{U}^{i}}Q^{i}(x,a^{i})+\epsilon,\>\forall
x\in\mathbb{X}\right\\}.$

The set $\widehat{{\rm BR}}^{i}_{\epsilon}(Q^{i})$ is the set of stationary
deterministic policies that are $\epsilon$-greedy with respect to $Q^{i}$. The
function $Q^{i}$ plays the role of an action-value function, and for
$Q^{i}=Q^{*i}_{\bm{\pi}^{-i}}$, we have $\widehat{{\rm
BR}}^{i}_{0}(Q^{*i}_{\bm{\pi}^{-i}})={\rm
BR}^{i}_{0}(\bm{\pi}^{-i})\cap\Gamma^{i}_{SD}$.

When the remaining players follow a stationary policy, player $i$ can use
Q-learning to estimate its action-values, which can then be used to estimate a
0-best-response policy. In the next section, we observe that the situation is
more complicated when the remaining players employ learning algorithms that
adapt to feedback and revise their action selection probabilities over time.

##  3 Related Work

In this paper, we are interested in MARL for stochastic games in the local
action learner setting of 1. In this framework, players do not have knowledge
of their cost functions, the transition kernel $P$, and perhaps even the
existence or nature of other players in the system. We focus on the online
setting, where players do not have access to a generative model for sampling
state transitions or costs, and instead must rely on sequential interactions
with the multi-agent system in order to gather data.

At a high level, our objective is to study and design learning algorithms that
drive play of the game to stable and individually rational joint policies. Our
objectives are closely aligned with the desiderata of MARL algorithms outlined
in [4], namely _convergence_ and _rationality_. In particular, we wish to
establish that joint policies converge to some stationary ($\epsilon$-)
equilibrium policy.

A number of MARL algorithms have been proposed with the same high level
objectives as ours. The wide ranging field of algorithms differ from one
another in terms of how and when incoming feedback data is processed and how
and when the agent’s policy is accordingly modified. In this section, we
survey some related work that is especially relevant to our chosen setting of
MARL in stochastic games with local action learners.

###  3.1 Q-Learning and its Challenges

In decentralized MARL settings, where agents have minimal information about
strategic interactions with other players, one natural and commonly studied
approach to algorithm design is to treat each agent’s game environment as a
separate single-agent RL environment. Indeed, when the remaining players use a
stationary policy $\bm{\pi}^{-i}\in\bm{\Gamma}^{-i}_{S}$, then player $i$
truly does face a strategic environment equivalent to an MDP, and can approach
its learning task with single-agent Q-learning.

Picking some
$\widehat{Q}^{i}_{0}\in\mathbb{R}^{\mathbb{X}\times\mathbb{U}^{i}}$ to serve
as an initial estimate of its optimal Q-function, player $i$ would iteratively
apply the following update rule:

(2)
$\widehat{Q}^{i}_{t+1}(x_{t},u^{i}_{t})=(1-\alpha_{t})\widehat{Q}^{i}_{t}(x_{t},u^{i}_{t})+\alpha_{t}\left[c^{i}(x_{t},\textnormal{{u}}_{t})+\beta^{i}\min_{a^{i}}\widehat{Q}^{i}_{t}(x_{t+1},a^{i})\right],$

where $\alpha_{t}=\alpha_{t}(x_{t},u^{i}_{t})$ is a random learning rate that
depends on the state-action pair $(x_{t},u^{i}_{t})$ and
$\widehat{Q}^{i}_{t+1}(x,a)=\widehat{Q}^{i}_{t}(x,a)$ for all
$(x,a)\not=(x_{t},u^{i}_{t})$.

If the learning rate $\alpha_{t}(x_{t},u^{i}_{t})$ is decreased at an
appropriate rate in the number of visits to the state-action pair
$(x_{t},u^{i}_{t})$, and if every state-action pair is visited infinitely
often, then one has $\widehat{Q}^{i}_{t}\to Q^{*i}_{\bm{\pi}^{-i}}$ almost
surely [35]. We recall that $Q^{*i}_{\bm{\pi}^{-i}}$ was defined in Section 2
as the optimal Q-function for player $i$ when playing against the stationary
policy $\bm{\pi}^{-i}$.

In order to asymptotically respond (nearly) optimally to the policy of its
counterparts, player $i$ must exploit the information carried by its learning
iterates. Since one must balance this exploitation with persistent
exploration, a standard approach in algorithm design is to periodically revise
an agent’s policy—either after every system interaction or less frequently—in
a manner that places higher probability on actions with better action values.
A widely used device for balancing exploration and exploitation is Boltzmann
action selection, wherein

${\rm
Pr}\left(u^{i}_{t}=a^{i}\middle|h^{i}_{t}\right)=\frac{\exp\left(-\widehat{Q}^{i}_{t}(x_{t},{a}^{i})/\tau_{t}\right)}{\sum_{\bar{a}^{i}\in\mathbb{U}^{i}}\exp\left(-\widehat{Q}^{i}_{t}(x_{t},\bar{a}^{i})/\tau_{t}\right)},\text{
for }t\geq 0,$

where $\tau_{t}>0$ is a temperature parameter that is typically taken to
decrease to 0 as $t\to\infty$, and player $i$’s Q-factor estimates
$\widehat{Q}^{i}_{t}$ are constructed from the local history $h^{i}_{t}$
observed by player $i$.

Boltzmann action selection is not the only feasible alternative for balancing
the trade-off between exploration and exploitation in this context; several
other greedy in the limit with infinite exploration (GLIE) mechanisms may also
be used to the same effect [33].

In the preceding equations, one observes that ${\rm
Pr}(u^{i}_{t}=\cdot\,|h^{i}_{t})$ is simply an alternative representation of
the policy actually followed by player $i$. Since player $i$’s Q-factor
estimates and other relevant parameters (e.g. the temperature sequence) change
with time, any adaptive learning algorithm that exploits learned iterates will
be _non-stationary_. If other players use analogous learning algorithms and
exploit their own learned information, then other players will also follow
non-stationary policies. In symbols, this is to say that
$\bm{\pi}^{-i}\notin\bm{\Gamma}^{-i}_{S}$. In this case, the strategic
environment defined by the non-stationary policy $\bm{\pi}^{-i}$ is _not_
generally equivalent to an MDP, and there is no guarantee that the Q-factor
estimates given by (2) will converge to some meaningful quantity, if they are
to converge at all.

Provable non-convergence of Q-iterates obtained by single-agent Q-learning in
small, stateless games has been established [17]. Similar non-convergence had
been previously been observed empirically in stochastic games [4, 34]. Thus,
some modification is needed in order to employ algorithms based on Q-learning
in multi-agent settings. Modifications may involve changes to how and when
Q-factor updates are performed or may involve changes to how and when action
selection probabilities are updated.

###  3.2 Algorithms for Local Action Learners

As described in the previous section, myopic algorithms that repeatedly change
an agent’s policy during the course of interaction can be effective in single-
agent settings, when an agent faces a stationary environment. By contrast,
when all agents employ such algorithms in a multi-agent system, each agent
faces a non-stationary environment and the same convergence guarantees need
not apply. In addition to the previously described non-convergence of
Q-factors, provable non-convergence of policies under particular learning
algorithms has also been observed in various settings, [8, 26, 27].

With the understanding that some modification of single-agent RL algorithms is
needed to address the challenge of non-stationarity in MARL, several multi-
agent algorithms have been proposed that use multiple timescales. The key
feature of the multi-timescale approach is that certain iterates—whether
policy parameters, Q-factor estimates, or otherwise—are updated slowly
relative to other iterates. In effect, this allows one to analyze the rapidly
changing iterates as though the slowly changing iterates were held fixed,
artificially mimicking stationarity.

Some works have studied MARL algorithms in which some agents update their
policies slowly while others update quickly. A two-timescale policy gradient
algorithm was studied for two-player, zero-sum games in [6], where a
performance guarantee was proven for the minimizing player. Other works,
including [29], have empirically studied MARL algorithms in which the agents
alternate between updating their policies slowly and quickly according to some
commonly accepted schedule.

A second type of multi-timescale algorithm updates various policy-relevant
parameters quickly relative to value function estimates, which are updated
relatively slowly. This approach can be found in [30, 31] and [32]. This can
be contrasted with a third type of multi-timescale algorithm, in which
policies are updated relatively slowly while value functions are updated
relatively quickly. For a recent example of this, see [23].

###  3.3 Regret Testers

In the MARL algorithms surveyed above, the agents update all relevant
parameters after each system interaction, and the multi-timescale analysis is
implemented by controlling the magnitude of these every-step updates via step-
size constraints. An alternative approach is to update certain iterates after
each system interaction while updating other iterates infrequently, with many
system interactions between updates. Such is the approach taken by works in
the tradition of _regret testing_ , pioneered by Foster and Young in [9],
which presented an algorithm for stateless games. This approach was later
studied by [10] and [24] among others in the context of stateless repeated
games, where impressive convergence guarantees were proven. The strong results
of [10] and [24] in stateless games were enabled to a significant extent by
the absence of state dynamics, which would otherwise complicate value
estimation and policy evaluation in multi-state games.

In [1], the regret testing paradigm of Foster and Young was modified for
multi-state stochastic games, where one must account for both the immediate
cost of an action and also the cost-to-go, which depends on the evolution of
the state variable. The decentralized Q-learning algorithm of [1] instructs
agents to agree on an increasing sequence of policy update times,
$(t_{k})_{k\geq 0}$, and to fix one’s policy within the intervals
$[t_{k},t_{k+1})$, called the $k^{th}$ _exploration phase_.333Although the
terminology of exploration phases first appeared in [1], the exploration phase
approach was pioneered by [9]. In so doing, the joint policy process is fixed
over each exploration phase, and within each exploration phase, each agent
faces a Markov decision problem (MDP). Each agent then runs a standard
Q-learning algorithm within its $k^{th}$ exploration phase, and updates its
policy in light of its Q-factors at the end of the $k^{th}$ exploration phase.
Since each agent faces an MDP, one can analyze the learning iterates using
single-agent learning theory. Provided the exploration phase lengths
$T_{k}:=t_{k+1}-t_{k}$ are sufficiently long, the probability of correctly
recovering one’s Q-function (defined with respect to the policies of the other
agents and elaborated in the coming sections) can be made arbitrarily close to
1.

In many of the papers on regret testers, the proofs of convergence to
equilibrium share the same core elements, which can be summarized as follows.
First, one defines an equilibrium event. (In the fully synchronous regime
described above, this equilibrium event is usually the event that the joint
policy of the $k^{th}$ exploration phase is an equilibrium.) Second, one
uniformly lower bounds the probability of transiting from non-equilibrium to
equilibrium in a fixed number of steps. Third, one shows that the probability
of remaining at equilibrium once at equilibrium can be made arbitrarily large
relative to the aforementioned lower bound. Fourth and finally, one obtains a
high probability guarantee of equilibrium by analyzing the ratio of entry and
exit probabilities to equilibrium policies (see, for instance, [9, Lemma 2]).

In effect, the exploration phase technique decouples learning from adaptation,
and allows for separate analysis of learning iterates and policy dynamics.
This allows for approximation arguments to be used, in which the dynamics of
the policy process resemble those of an idealized process where players obtain
noise-free learning iterates for use in their policy updates. This has lead to
a series of theoretical contributions in MARL that make use of the exploration
phase technique, including [36] and [37].

One natural criticism of the exploration phase technique described above is
its reliance on synchronization of policy updating. In the description above,
agents agree on the policy update times $\\{t_{k}\\}_{k\geq 0}$ exactly, and
no agent ever updates its policy in the interval $(t_{k},t_{k+1}-1]$. This can
be justified in some settings, but is demanding in decentralized settings
where parameters are selected independently across players. Indeed, the
mathematically convenient assumption of synchrony is made in various works in
the regret testing tradition, including [9, 10] and [24].

To relax the synchrony assumption of regret testers, one allows each player
$i$ to select its own exploration phase times $(t^{i}_{k})_{k\geq 0}$. Player
$i$ then has the opportunity to revise its policies at each time in
$(t^{i}_{k})_{k\geq 0}$. We observe that an update time for player $i$ may
fall within an exploration phase for some other player $j$. That is,
$t^{j}_{m}<t^{i}_{k}<t^{j}_{m+1}$ for two players $i,j$ and exploration phase
indices $k$ and $m$. In this case, the environment faced by player $j$ during
its $m^{th}$ exploration phase is non-stationary, having been disrupted (at
least) by player $i$’s changing policies.

Intuitively, asynchrony may be problematic for regret testers because the
action-value estimates of a given player depend on historical data from that
player’s most recent exploration phase, which in turn depends on the (time-
varying) joint policies used during this period. As such, if other players
change their policies during an individual’s exploration phase, the individual
receives feedback from different sources, and its learning iterates may not
approximate any quantity relevant to the prevailing environment at the time of
the individual’s policy update. These changes of policy during an exploration
phase constitute potential disruptions of a player’s learning, and analysis of
the overall joint policy process is difficult when players do not reliably
learn accurate action-values.

In this asynchronous regime, learning and adaptation are not decoupled, as
agents do not face stationary MDPs during each of their exploration phases. In
particular, it is not guaranteed that a given player’s Q-factors will
converge. Consequently, it is not clear that the second and especially the
third steps of the standard line of proof described above can be reproduced in
the asynchronous setting.

In [24], a heuristic argument suggested that the use of inertia in policy
updating may allow one to relax the assumption of perfect synchrony in regret
testing algorithms for stateless repeated games. This argument offers a
promising starting point, but also has two potential gaps. The first
unresolved aspect pertains to the ratio of entry and exit probabilities. The
heuristic argument correctly states that one can use inertia to both (i) lower
bound the probability of transiting to equilibrium from out of equilibrium,
and (ii) make the probability of remaining at equilibrium arbitrarily close to
1. However, the analysis of the overall joint policy process depends on the
ratio of these entry and exit probabilities, which depends on the choice of
inertia parameter and may be somewhat challenging to analyze.

A second unresolved aspect has to do with the learning routine and how quickly
errors are corrected. Here, the specific learning rate used in each agent’s
Q-learning algorithm plays an important role. Existing regret testing
algorithms employ a decreasing learning rate, so as to ensure the convergence
of learning iterates within a synchronized exploration phase. In the
asynchronous regime, however, agents learn against time-varying environments.
If an agent uses a decreasing learning rate, it gives relatively high weight
to outdated data that are no longer representative of its current environment.
As such, it may take a long, uninterrupted stretch of learning against the
prevailing environment to correct the outdated learning. The time required
will depend on how much the learning rate parameters have been reduced, and
these considerations must be quantified explicitly in the analysis. This point
is somewhat subtle, and may pose a challenge if one attempts to use decreasing
learning rates in the asynchronous regime.

In this paper, we formalize the heuristic argument of [24] and show that it is
effectively correct, with minor caveats. To rectify the unaddressed aspects
mentioned above, we modify the Q-learning protocol to use a constant learning
rate and conduct a somewhat involved analysis of the resulting behaviour. We
focus on weakly acyclic games and best-response-based policy updating
routines, but the analysis from this setting can be used to study other policy
update routines and classes of games, including $\epsilon$-satisficing policy
update dynamics such as those described in [37].

##  4 Asynchronous Decentralized Q-Learning

In this section, we present Algorithm 1, an asynchronous variant of the
decentralized Q-learning of [1]. Unlike in the original decentralized
Q-learning algorithm, Algorithm 1 allows for the sequence of exploration phase
lengths $\\{T^{i}_{k}\\}_{k\geq 0}$ vary by agent.

1

2

3

4Set Parameters

5 $\\{T^{i}_{k}\\}_{k\geq 0}$: a sequence in $\mathbb{N}$ of learning phase
lengths

6 Put $t^{i}_{0}=0$ and $t^{i}_{k+1}=t^{i}_{k}+T^{i}_{k}$ for all $k\geq 0$.

7 $\rho^{i}\in(0,1)$: experimentation probability

8 $\lambda^{i}\in(0,1)$: inertia during policy update

9 $\delta^{i}\in(0,\infty)$: tolerance level for sub-optimality

10 $\alpha^{i}\in(0,1)$: step-size parameter

11

12Initialize $\pi_{0}^{i}\in\Gamma^{i}_{SD}$,
$\widehat{Q}_{0}^{i}\in\mathbb{R}^{\mathbb{X}\times\mathbb{U}^{i}}$
(arbitrary)

13

14for $k\geq 0$ ($k^{th}$ exploration phase for agent $i$ )

15 for $t=t_{k}^{i},t_{k}^{i}+1,\dots,t^{i}_{k+1}-1$

16 Observe $x_{t}$

17 Select $u^{i}_{t}=\begin{cases}\pi^{i}_{k}(x_{t}),&\text{w.p.
}1-\rho^{i}\\\ u^{i}\sim\text{Unif}(\mathbb{U}^{i}),&\text{w.p.
}\rho^{i}\end{cases}$

18

19 Observe cost $c^{i}_{t}:=c(x_{t},\textnormal{{u}}_{t})$, state $x_{t+1}$

20

21 Put
$\Delta^{i}_{t}=c^{i}_{t}+\beta^{i}\min_{a^{i}}\widehat{Q}^{i}_{t}(x_{t+1},a^{i})$

22

23
$\widehat{Q}^{i}_{t+1}(x_{t},u_{t}^{i})=(1-\alpha^{i})\widehat{Q}_{t}^{i}(x_{t},u_{t}^{i})+\alpha^{i}\Delta^{i}_{t}$

24

25 $\widehat{Q}_{t+1}^{i}(x,u^{i})=\widehat{Q}^{i}_{t}(x,u^{i})$, for all
$(x,u^{i})\not=(x_{t},u_{t}^{i})$

26

27

28 if  _ $\pi^{i}_{k}\in\widehat{{\rm
BR}}^{i}_{\delta^{i}}(\widehat{Q}^{i}_{t^{i}_{k+1}})$,_ then

29 $\pi^{i}_{k+1}\leftarrow\pi^{i}_{k}$

30 else

31 $\pi^{i}_{k+1}\leftarrow\begin{cases}\pi^{i}_{k},&\text{w.p.
}\lambda^{i}\\\ \pi^{i}\in\widehat{{\rm
BR}}^{i}_{\delta^{i}}(\widehat{Q}^{i}_{t^{i}_{k+1}}),&\text{w.p.
}1-\lambda^{i}\end{cases}$

Algorithm 1 Asynchronous Decentralized Q-Learning

###  4.1 Primitive Random Variables

We now introduce several collections of _primitive_ random variables that will
be used in describing the assumptions and implementation of Algorithm 1. For
any player $i\in\mathcal{N}$ and $t\geq 0$, we define the following random
variables:

  * •

$\\{W_{t}\\}_{t\geq 0}$ is an identically distributed, $[0,1]$-valued
stochastic process. For some
$f:\mathbb{X}\times\textnormal{{U}}\times[0,1]\to\mathbb{X}$, state
transitions are driven by $\\{W_{t}\\}_{t\geq 0}$ via $f$:

$\displaystyle{\rm
Pr}(x_{t+1}=s^{\prime}|x_{t}=s,\textnormal{{u}}_{t}=\textnormal{{a}})={\rm
Pr}\left(W_{t}\in\\{w:f(s,\textnormal{{a}},w)=s^{\prime}\\}\right),$

for any
$(s,\textnormal{{a}},s^{\prime})\in\mathbb{X}\times\textnormal{{U}}\times\mathbb{X}$
and $t\geq 0$;

  * •

$\tilde{u}^{i}_{t}\sim\text{Unif}(\mathbb{U}^{i})$;

  * •

$\tilde{\rho}^{i}_{t}\sim\text{Unif}([0,1])$;

  * •

$\tilde{\lambda}^{i}_{t}\sim\text{Unif}([0,1])$;

  * •

For non-empty $B^{i}\subseteq\Gamma^{i}_{SD}$,
$\tilde{\pi}^{i}_{t}(B^{i})\sim\text{Unif}(B^{i})$;

  * •

$T^{i}_{t}$ is an $\mathbb{N}$-valued random variable, elaborated below.

######  Assumption 2.

The collection of primitive random variables
$\mathcal{V}_{1}\cup\mathcal{V}_{2}$ is mutually independent, where

$\displaystyle\mathcal{V}_{1}$ $\displaystyle:=\bigcup_{i\in\mathcal{N},t\geq
0}\left\\{W_{t},\tilde{\rho}^{i}_{t},\tilde{u}^{i}_{t},\tilde{\lambda}^{i}_{t},T^{i}_{t}\right\\},$
$\displaystyle\mathcal{V}_{2}$ $\displaystyle:=\bigcup_{i\in\mathcal{N},t\geq
0}\left\\{\tilde{\pi}^{i}_{t}(B^{i}):B^{i}\subseteq\Gamma^{i}_{SD},B^{i}\not=\varnothing\right\\}.$

Remark: The random variables in $\mathcal{V}_{1}\cup\mathcal{V}_{2}$ are
primitive random variables that, with the exception of exploration phase
lengths $\\{T^{i}_{k}\\}_{i\in\mathcal{N},k\geq 0}$, do not depend on any
player’s choice of hyperparameters. The exploration phase lengths are
hyperparameters that we allow to be randomly selected at the outset of play.
We also note that the primitive random variables
$\\{\tilde{u}^{i}_{t}:i\in\mathcal{N},t\geq 0\\}$ should not be conflated with
the action process $\\{u^{i}_{t}:i\in\mathcal{N},t\geq 0\\}$, which depends on
the sample path and is not a collection of primitive random variables.

###  4.2 Assumptions

In order to state our main result, Theorem 4.1, we now impose some assumptions
on the underlying game $\mathcal{G}$ and on the hyperparameters chosen by each
player.

######  Assumption 3.

For any pair $(s,s^{\prime})\in\mathbb{X}\times\mathbb{X}$, there exists
$H=H(s,s^{\prime})\in\mathbb{N}$ and a sequence of joint actions
_$\textnormal{{a}}_{0},\dots,\textnormal{{a}}_{H}\in\textnormal{{U}}$_ such
that

${\rm
Pr}(x_{H+1}=s^{\prime}|x_{0}=s,\text{\emph{$\textnormal{{u}}_{0}=\textnormal{{a}}_{0},\dots,\textnormal{{u}}_{H}=\textnormal{{a}}_{H}$}})>0.$

3 requires that the state process can be driven from any initial state to any
other state in finitely many steps, provided a suitable selection of joint
actions is made. This is a rather weak assumption on the underlying transition
kernel $P$, and is quite standard in the theory of MARL (c.f. [30, Assumption
4.1, Case iv]).

Our next assumption restricts the hyperparameter selections in Algorithm 1.
Let $\bar{\delta}:=\min\left(\mathfrak{A}\setminus\\{0\\}\right)$, where

$\displaystyle\mathfrak{A}:={\big{\\{}}$
$\displaystyle{\big{|}}Q^{*i}_{\bm{\pi}^{-i}}(s,a^{i}_{1})-Q^{*i}_{\bm{\pi}^{-i}}(s,a^{i}_{2}){\big{|}}:i\in\mathcal{N},\bm{\pi}^{-i}\in\bm{\Gamma}^{-i}_{SD},s\in\mathbb{X},a^{i}_{1},a^{i}_{2}\in\mathbb{U}^{i}{\big{\\}}}.$

The quantity $\bar{\delta}$, defined originally by [1] and recalled above, is
the minimum non-zero separation between two optimal Q-factors with matching
states, minimized over all agents $i\in\mathcal{N}$ and over all policies
$\bm{\pi}^{-i}\in\bm{\Gamma}^{-i}_{SD}$.

For any baseline policy $\bm{\pi}\in\bm{\Gamma}_{SD}$ and fixed exploration
parameters $\\{\rho^{i}\\}_{i\in\mathcal{N}}$, we use the notation
$\hat{\bm{\pi}}\in\bm{\Gamma}_{S}$ to denote a corresponding behaviour policy,
which is stationary but not deterministic. When using $\hat{\pi}^{i}$, agent
$i\in\mathcal{N}$ follows $\pi^{i}$ with probability $1-\rho^{i}$ and mixes
uniformly over $\mathbb{U}^{i}$ with probability $\rho^{i}$. It was previously
shown in [1, Lemma B3] that the optimal Q-factors for these two environments
will be close provided $\rho^{i}$ is sufficiently small for all
$i\in\mathcal{N}$. In particular, there exists $\bar{\rho}>0$ such that if
$\rho^{i}\in(0,\bar{\rho})$ $\forall i\in\mathcal{N}$, then

$\|Q^{*j}_{\bm{\pi}^{-j}}-Q^{*j}_{\hat{\bm{\pi}}^{-j}}\|_{\infty}<\frac{\min_{i\in\mathcal{N}}\min\\{\delta^{i},\bar{\delta}-\delta^{i}\\}}{4},\>\forall
j\in\mathcal{N},\bm{\pi}^{-j}\in\bm{\Gamma}^{-j}_{SD}.$

######  Assumption 4.

For all $i\in\mathcal{N}$, $\delta^{i}\in(0,\bar{\delta})$ and
$\rho^{i}\in(0,\bar{\rho})$.

We require that $\delta^{i}$, player $i$’s tolerance for sub-optimality in its
Q-factor, is positive to account for noise in its learning iterates, as exact
convergence is unreasonably demanding during a truncated learning phase. On
the other hand, the tolerance parameter $\delta^{i}$ is upper bounded so as to
exclude truly suboptimal policies from consideration in an estimated best-
response set.

The second part of 4 concerns the experimentation parameter $\rho^{i}$. We
assume that $\rho^{i}>0$ so that player $i$ can explore all of its actions and
accurately learn its Q-factors in the limit. This experimentation parameter
$\rho^{i}$ must be kept small, however, so player $i$’s behaviour policy
closely approximates its baseline policy.

4 appears as Assumption 2 in [1].

######  Assumption 5.

There exists integers $R,T\in\mathbb{N}$ such that

${\rm Pr}\left(\cap_{i\in\mathcal{N},k\geq
0}\left\\{T^{i}_{k}\in[T,RT]\right\\}\right)=1.$

5 requires that each agent spends a long time learning during any given
exploration phase ($T^{i}_{k}\geq T$ almost surely for any player $i$ during
any exploration phase $k$). The second part of 5, that $T^{i}_{k}\leq RT$
almost surely for all $i,k$, is assumed in order to control the relative
frequency at which different agents update their policies.This is done to
avoid the potentially problematic regime in which some agents update their
policies an enormous number of times and repeatedly disrupt the learning of
another agent who uses long exploration phase lengths.

When all players use Algorithm 1, we view the resulting sequence of policies
$\\{\pi^{i}_{k}\\}_{k\geq 0}$ as player $i$’s _baseline_ policy process, where
$\pi^{i}_{k}$ is player $i$’s baseline policy during
$[t^{i}_{k},t^{i}_{k+1})$, player $i$’s $k^{th}$ exploration phase. This
policy process $\\{\pi^{i}_{k}\\}_{k\geq 0}$ is indexed on the coarser
timescale of exploration phases. For ease of reference, we also introduce a
sequence of baseline policies indexed by the finer timescale of stage games.
For $t\geq 0$ with $t\in[t^{i}_{k},t^{i}_{k+1})$, we let
$\phi^{i}_{t}:=\pi^{i}_{k}$ denote player $i$’s baseline policy during the
stage game at time $t$. The baseline joint policy at stage game $t$ is then
denoted $\bm{\phi}_{t}=(\phi^{i}_{t})_{i\in\mathcal{N}}$. Furthermore, we
refer to the collection of Q-factor step-size parameters
$\\{\alpha^{i}\\}_{i\in\mathcal{N}}$ as $\bm{\alpha}\in(0,1)^{N}$.

######  Theorem 4.1.

Let $\mathcal{G}$ be a weakly acyclic game and suppose each player
$i\in\mathcal{N}$ uses Algorithm 1 to play $\mathcal{G}$. Suppose Assumptions
2–5 hold, and let $\epsilon>0$. There exists $\bar{\alpha}_{\epsilon}>0$ and a
function $\bar{T}_{\epsilon}:(0,1)^{N}\times\mathbb{N}\to\mathbb{N}$ such that
if

$\max_{i\in\mathcal{N}}\alpha^{i}<\bar{\alpha}_{\epsilon},\text{ and
}T\geq\bar{T}_{\epsilon}(\bm{\alpha},R),$

then ${\rm Pr}(\bm{\phi}_{t}\in\bm{\Gamma}^{0{\rm\text{-}eq}}_{SD})\geq
1-\epsilon,$ for all sufficiently large $t\in\mathbb{N}$.

In words, Theorem 4.1 says the following: if the relative frequency of policy
update times of different players is controlled by some ratio $R$, if players
use sufficiently small learning rates $\bm{\alpha}$, and if the lower bound
$T$ on each player’s exploration phase length is sufficiently long relative to
both the learning rates $\bm{\alpha}$ as well as the ratio parameter $R$, then
play will be driven to equilibrium with high probability.

As we will see, the interdependence of the various parameters—$R,\bm{\alpha},$
and $T$—is significant in the analysis to follow.

##  5 Proof of Theorem 4.1

In the analysis to follow, we study the performance of Algorithm 1 under a
fixed realization of the primitive exploration phase random variables
$\mathcal{T}=\\{T^{i}_{k}:i\in\mathcal{N},k\geq 0\\}$. We now introduce
several objects to facilitate the analysis, and we suppress any dependence on
the realization of $\mathcal{T}$.

###  5.1 Various Notations and Constructions for the Proof

For each $i\in\mathcal{N}$, we arbitrarily order non-empty subsets of
$\Gamma^{i}_{SD}$ as $B^{i,1},\dots,B^{i,m_{i}}$, where
$m_{i}=|2^{\Gamma^{i}_{SD}}\setminus\varnothing|$. We introduce the following
new quantities for each $t\geq 0$:

  * •

$\omega^{i}_{t}:=(\tilde{\rho}^{i}_{t},\tilde{u}^{i}_{t},\tilde{\lambda}^{i}_{t},\tilde{\pi}^{i}_{t}(B^{i,1}),\dots,\tilde{\pi}^{i}_{t}(B^{i,m_{i}})),$
for all $i\in\mathcal{N}$. We define $\mathfrak{S}^{i}$ to be the set in which
the random quantity $\omega^{i}_{t}$ takes its values. That is,

$\mathfrak{S}^{i}:=[0,1]\times\mathbb{U}^{i}\times[0,1]\times
B^{i,1}\times\cdots\times B^{i,m_{i}},\quad\forall i\in\mathcal{N}.$

  * •

$\bm{\omega}_{t}:=(W_{t},\omega^{1}_{t},\dots,\omega^{N}_{t})$, where
$\\{W_{t}\\}_{t\geq 0}$ is the $[0,1]$-valued independent and identically
distributed (i.i.d.) noise process driving state transitions that was
introduced in §4.1;

  * •

$\bm{\varpi}_{t}:=(\bm{\omega}_{t},\bm{\omega}_{t+1},\dots)$;

  * •

$\widehat{\textbf{Q}}_{t}:=(\widehat{Q}^{1}_{t},\dots,\widehat{Q}^{N}_{t})$;

  * •

$h_{t}$
$:=(x_{0},\bm{\phi}_{0},\widehat{\textbf{Q}}_{0},\dots,x_{t},\bm{\phi}_{t},\widehat{\textbf{Q}}_{t})$;

  * •

$H_{t}$
$:=\left(\mathbb{X}\times\bm{\Gamma}_{SD}\times\mathbb{R}^{\mathbb{X}\times\mathbb{U}^{1}}\times\dots\times\mathbb{R}^{\mathbb{X}\times\mathbb{U}^{N}}\right)^{t+1}$;

  * •

$H_{t,\rm eq}$ $:=\\{h_{t}\in
H_{t}:\bm{\phi}_{t}\in\bm{\Gamma}^{0{\rm\text{-}eq}}_{SD}\\}$.

We note that $\omega^{i}_{t}$ is a random quantity taking values in
$\mathfrak{S}^{i}$, while $\bm{\omega}_{t}$ is a random quantity taking values
in $[0,1]\times\mathfrak{S}^{1}\times\cdots\times\mathfrak{S}^{N}$. For each
$t\geq 0$, a realization of the random quantity $\bm{\varpi}_{t}$ is a
sequence with entries in
$[0,1]\times\mathfrak{S}^{1}\times\cdots\times\mathfrak{S}^{N}$.

When every player uses Algorithm 1 to play the game and each player’s
randomization mechanism is governed by the primitive random variables of §4.1,
we have that the sample path of play—including realizations of the state
process $\\{x_{t}\\}_{t\geq 0}$, the action processes $\\{u^{i}_{t}\\}_{t\geq
0}$ for each agent $i\in\mathcal{N}$, the baseline joint policy process
$\\{\bm{\phi}_{t}\\}_{t\geq 0}$, and the Q-factor estimates
$\\{\widehat{Q}^{i}_{t}\\}_{t\geq 0}$—are deterministic functions of any given
prefix history $h_{s}\in H_{s}$ and its corresponding continuation,
$\bm{\varpi}_{s}\in\left([0,1]\times\mathfrak{S}^{1}\times\cdots\times\mathfrak{S}^{N}\right)^{\infty}$,
where $s\in\mathbb{Z}_{\geq 0}$. With this in mind, for $i\in\mathcal{N}$ and
$t\geq 0$, let the functions $\mathcal{Q}^{i}_{t}$ and $\Phi_{t}$ be
constructed such that
$\widehat{Q}^{i}_{t}=\mathcal{Q}^{i}_{t}(h_{s},\bm{\varpi}_{s}),$ and
$\bm{\phi}_{t}=\Phi_{t}(h_{s},\bm{\varpi}_{s}),$ for all $0\leq s\leq t$.

Next, for any $s,t\geq 0$ and any $i\in\mathcal{N}$, we introduce a function
$\bar{Q}^{i}_{t+s}(h_{t},\bm{\varpi}_{t})$ that reports the _hypothetical
Q-factors_ player $i$ _would have_ obtained if the baseline policies had been
frozen at time $t$. That is, the history up to time $t$ is given by $h_{t}$,
the primitive random variables from $t$ onward are given by $\bm{\varpi}_{t}$,
and we obtain the hypothetical ($\bm{\varpi}_{t}$-measurable) continuation
trajectory
$(\bar{x}_{t},\bar{\textnormal{{u}}}_{t},\dots,\bar{x}_{t+s},\bar{\textnormal{{u}}}_{t+s})$,
as $\bar{x}_{t}:=x_{t}$,

$\bar{x}_{t+m+1}=f(\bar{x}_{t+m},\bar{\textnormal{{u}}}_{t+m},W_{t+m}),\quad\forall\,0\leq
m\leq s,$

where for each player $j$ and time $t+m\geq t$,

$\bar{u}^{j}_{t+m}:=\begin{cases}\phi^{j}_{t}(\bar{x}_{t+m}),&\text{if
}\tilde{\rho}^{j}_{t+m}>\rho^{j}\\\
\tilde{u}^{j}_{t+m}&\text{otherwise.}\end{cases}$

Note that the index of $\phi^{i}_{t}$ is not $t+m$, which reflects that, in
this hypothetical continuation, the baseline policies were frozen at time $t$.
Each hypothetical Q-factor estimate $\bar{Q}^{i}_{t+s}(s,a^{i})$ is then
(analytically) built out of this hypothetical trajectory using the regular
Q-learning update with the initial condition prescribed by
$\widehat{\textbf{Q}}_{t}$.

Hypothetical Q-factors feature prominently in the analysis of the coming
sections, and are a somewhat subtle construction, so we explain their
utilization here. To analyze the likelihood of driving play to equilibrium or
the likelihood of remaining at equilibrium, we ultimately wish to make
probabilistic statements about the realized Q-learning iterates,
$\\{\widehat{\textbf{Q}}_{t}\\}_{t\geq 0}$, conditional on various events,
such as the event that players did not switch their baseline policies
recently. However, conditioning on such events can be problematic in the
analysis, since the conditioning event clearly carries information about the
state-action trajectory that may be consequential for the evolution of the
Q-factor estimates. Due to this confounding effect, we will avoid making
statements about conditional probabilities directly, and we will instead study
trajectories of the hypothetical Q-factors. In so doing, we can describe
likelihoods of relevant events in terms of the primitive random variables,
thereby avoiding the confounding effects of conditioning.

###  5.2 Supporting Results on Q-Learning Iterates

######  Lemma 5.1.

For some $M<\infty$, the following holds almost surely:

$\max_{i\in\mathcal{N}}\sup_{t\geq
0}\left\|\widehat{Q}^{i}_{t}\right\|_{\infty}\leq M.$

######  Proof 5.2.

For all $i\in\mathcal{N}$, we have

$\displaystyle\|\widehat{Q}_{t+1}^{i}\|_{\infty}$
$\displaystyle\leq\max\bigg{\\{}(1-\alpha^{i})\|\widehat{Q}_{t}^{i}\|_{\infty}+\alpha^{i}\big{(}\|c^{i}\|_{\infty}+\beta^{i}\|\widehat{Q}_{t}^{i}\|_{\infty}\big{)},\|\widehat{Q}_{t}^{i}\|_{\infty}\bigg{\\}}.$

Defining
$M:=\max_{i\in\mathcal{N}}\left\\{\left\|\widehat{Q}^{i}_{0}\right\|_{\infty},\frac{\|c^{i}\|_{\infty}}{1-\beta^{i}}\right\\}$,
we have that if $\left\|\widehat{Q}^{i}_{t}\right\|_{\infty}\leq M$, then

$\displaystyle\|\widehat{Q}_{t+1}^{i}\|_{\infty}$
$\displaystyle\leq\max\bigg{\\{}(1-\alpha^{i})M+\alpha^{i}\big{(}\|c^{i}\|_{\infty}+\beta
M\big{)},M\bigg{\\}}$
$\displaystyle=\max\bigg{\\{}M+\alpha^{i}\big{(}\underbrace{\|c^{i}\|_{\infty}-(1-\beta^{i})M}_{\leq
0}\big{)},M\bigg{\\}}=M.$

This proves the lemma, as $\|\widehat{Q}_{0}^{i}\|_{\infty}\leq M<\infty$ for
each $i\in\mathcal{N}$.

The following lemma says that players can learn their optimal Q-factors
accurately when they use sufficiently small step sizes and when their learning
is not disrupted by policy updates for a sufficiently long number of steps. It
is worded in terms of primitive random variables and hypothetical continuation
Q-factors for reasons described above.

######  Lemma 5.3.

For any $\xi>0$, there exists $\hat{\alpha}_{\xi}>0$ and function
$\hat{T}_{\xi}:(0,1)^{N}\to\mathbb{N}$ such that if (1)
$\alpha^{i}\in(0,\hat{\alpha}_{\xi})$ for all $i\in\mathcal{N}$, and (2)
$\tilde{T}\geq\hat{T}_{\xi}(\bm{\alpha})$, then

${\rm Pr}(\Omega_{t:t+\tilde{T}})\geq 1-\xi,\quad\forall\,t\geq 0,h_{t}\in
H_{t},$

where
$\Omega_{t:t+\tilde{T}}=\big{\\{}\bm{\varpi}_{t}:\max_{i\in\mathcal{N}}\|\bar{Q}_{t+\tilde{T}}^{i}(h_{t},\bm{\varpi}_{t})-\widehat{Q}_{\bm{\phi}_{t}^{-i}}^{*i}\|_{\infty}<\xi\big{\\}}.$

######  Proof 5.4.

Since each player $i$’s policy is $\rho^{i}$-soft, our 3 implies the
persistent excitation assumption of [2, Assumption 1]. The result then follows
from Lemma 5.1 and [2, Theorem 3.4], using Markov’s inequality.

In the asynchronous regime, where each agent faces a non-stationary, time-
varying environment and uses Q-learning, Lemma 5.3 is an extremely useful
result that allows one to quantify the amount of time needed to correct
outdated information contained in the learning iterates. The choice to employ
constant learning rates was made in large part due to this consideration.

In the sequel, we fix $\hat{\alpha}_{\xi}$ and $\hat{T}_{\xi}(\cdot)$ with the
properties outlined in Lemma 5.3.

###  5.3 A Supporting Result Controlling Update Frequencies

A core challenge of analyzing non-synchronized multi-agent learning is that
policy updates for one player constitute potential destabilizations of
learning for others. We now introduce a sequence of time intervals
$\\{[\tau^{\min}_{k},\tau^{\max}_{k}]\\}_{k\geq 0}$ that will be useful in
quantifying and analyzing the effects of such disruptions. In particular, we
wish to upper bound the number of potential disruptions to a given player’s
learning, which can be upper bounded by the number of times other players
finish an exploration phase during the given individual’s current exploration
phase. Producing an upper bound of this sort will be important for quantifying
the importance of inertia for stabilizing the environment in the heuristic
argument of [24].

######  Definition 5.5.

Let $\tau^{\min}_{0}=\tau^{\max}_{0}:=0$. For $k\geq 0$, define

$\displaystyle\tau^{\min}_{k+1}$
$\displaystyle:=\inf\\{t^{i}_{n}:t^{i}_{n}>\tau^{\max}_{k},i\in\mathcal{N},n\geq
0\\}$ $\displaystyle\tau^{\max}_{k+1}$
$\displaystyle:=\inf{\big{\\{}}t\geq\tau^{\min}_{k+1}:\forall\,i\in\mathcal{N},\exists\,n\in\mathbb{N}\text{
s.t. }t^{i}_{n}\in[\tau^{\min}_{k+1},t],$
$\displaystyle\qquad\quad\qquad\quad\qquad\text{ and
}\inf\\{t^{i}_{\bar{n}}>t:i\in\mathcal{N},\bar{n}\in\mathbb{N}\\}\geq
t+T/N{\big{\\}}},$

where $T$ is the constant appearing in 5.

The intervals $[\tau^{\min}_{k},\tau^{\max}_{k}]$ represent active phases,
during which players may change their policies. The $(k+1)^{th}$ active phase
starts at $\tau^{\min}_{k+1}$, which is defined as the first time after
$\tau^{\max}_{k}$ at which some agent has an opportunity to revise its policy.
As a consequence of these definitions, no policy updates occur in
$(\tau^{\max}_{k},\tau^{\min}_{k+1})$.

The definition of $\tau^{\max}_{k+1}$ is slightly more involved:
$\tau^{\max}_{k+1}$ is the minimal stage game time at which (a) each agent has
an opportunity to switch policies in $[\tau^{\min}_{k+1},\tau^{\max}_{k+1}]$
and (b) that no agent finishes its current exploration phase in the next $T/N$
stage games. The latter point is critical, as it guarantees that each player’s
learning is allowed to proceed uninterrupted for at least $T/N$ stages after
the final (potential) disruption.

These active phases are characterized by the end times of each player’s
exploration phases, $\\{t^{i}_{n}:i\in\mathcal{N},n\geq 1\\}$, and therefore
depend on the exploration phase length parameters
$\mathcal{T}=\\{T^{i}_{n}:i\in\mathcal{N},n\geq 0\\}$. We recall that the
collection $\mathcal{T}$ is generated at the outset of play, independently of
the other primitive random variables. In the analysis to follow, we fix a
particular realization of $\mathcal{T}$ satisfying 5 and our notation
suppresses the dependence of $\\{\tau^{\min}_{k},\tau^{\max}_{k}\\}_{k\geq 0}$
on this realization. All of the statements below are understood to hold almost
surely.

######  Lemma 5.6.

The sequences $\\{\tau^{\min}_{k}\\}_{k\geq 0}$ and
$\\{\tau^{\max}_{k}\\}_{k\geq 0}$ are well-defined (i.e. the infimum defining
each term is achieved by a finite integer), and the following holds for any
$k\geq 0$:

  * (a)

$\tau^{\min}_{k+1}\geq\tau^{\max}_{k}+T/N$.

  * (b)

For each $i\in\mathcal{N}$, we have _$\sum_{n\geq
0}\textbf{1}\\{t^{i}_{n}\in[\tau^{\min}_{k},\tau^{\max}_{k}]\\}\leq R+1.$_

In words, part (a) of Lemma 5.6 guarantees that any successive active phases
are separated by at least $T/N$ stage games, while part (b) guarantees that
any individual player has at most $R+1$ opportunities to revise its policy
during the $k^{th}$ active phase.

######  Proof 5.7.

For some $k\geq 0$, suppose that (a) and (b) hold for all $l\leq k$. That is,

  * (a)

$\tau^{\min}_{l+1}\geq\tau^{\max}_{l}+T/N$, for all $0\leq l\leq k$, and

  * (b)

for each $i\in\mathcal{N},l\leq k$, we have $\sum_{n\geq
0}\textbf{1}\\{t^{i}_{n}\in[\tau^{\min}_{l},\tau^{\max}_{l}]\\}\leq R+1.$

Note that this holds for $k=0$. We will show the following: (1)
$\tau^{\max}_{k+1}<\infty$; (2)
$\tau^{\min}_{k+2}~{}\geq~{}\tau^{\max}_{k+1}~{}+~{}T/N$; (3) For all
$i\in\mathcal{N}$, we have $\sum_{n\geq
0}\textbf{1}\\{t^{i}_{n}\in[\tau^{\min}_{k+1},\tau^{\max}_{k+1}]\\}\leq R+1.$

For each $i\in\mathcal{N}$, let $n_{i}\in\mathbb{Z}_{\geq 0}$ denote the index
such that

$t^{i}_{n_{i}-1}<\tau^{\min}_{k+1}\leq t^{i}_{n_{i}}.$

By minimality of $\tau^{\min}_{k+1}$, we have that
$t^{i}_{n_{i}-1}\leq\tau^{\max}_{k}$. By 5, we have $T^{i}_{n_{i}-1}\leq RT$
and thus

$t^{i}_{n_{i}}=t^{i}_{n_{i}-1}+T^{i}_{n_{i}-1}\leq\tau^{\max}_{k}+RT.$

This implies $t^{i}_{n_{i}}-\tau^{\min}_{k+1}\leq RT-T/N$, since
$\tau^{\min}_{k+1}\geq\tau^{\max}_{k}+T/N$ by hypothesis.

We put $\hat{t}_{0}:=\max_{i}t^{i}_{n_{i}}$, and let $j(0)\in\mathcal{N}$
denote an agent with $t^{j(0)}_{n_{j(0)}}=\hat{t}_{0}$.

For each $l\in\\{0,1,\dots,N-1\\}$, we define $\hat{t}_{l+1}$ as

$\hat{t}_{l+1}=\min\left\\{t^{j}_{\bar{k}}>\hat{t}_{l}:j\in\mathcal{N},\bar{k}\geq
0\right\\}.$

Observe that $\hat{t}_{0}\leq\tau^{\max}_{k+1}$. Moreover, if there exists
some $l\leq N-1$ such that $\hat{t}_{l+1}\geq\hat{t}_{l}+T/N$, then
$\tau^{\max}_{k+1}\leq\hat{t}_{l}$, and thus $\tau^{\max}_{k+1}<\infty$. We
now argue that such $l$ exists.

Suppose that no such $l$ exists:

(3)
$\displaystyle\max\\{\hat{t}_{1}-\hat{t}_{0},\cdots,\hat{t}_{N}-\hat{t}_{N-1}\\}<T/N$
$\displaystyle\Rightarrow$
$\displaystyle\hat{t}_{N}-\hat{t}_{0}=\sum_{l=0}^{N-1}\left(\hat{t}_{l+1}-\hat{t}_{l}\right)<N\cdot\frac{T}{N}=T\leq\min_{i,n}T^{i}_{n}.$

One concludes that the minima defining each $\\{\hat{t}_{l}:1\leq l\leq N\\}$
are attained by $N$ distinct minimizing agents, one of whom is $j(0)$. But
then, for some $l$, we have

$\hat{t}_{0}=t^{j(0)}_{n_{j(0)}},\text{ and
}\>t^{j(0)}_{n_{j(0)}}+T^{j(0)}_{n_{j(0)}}=\hat{t}_{l}\leq\hat{t}_{N},$

which implies $T^{j(0)}_{n_{j(0)}}<T$, contradicting 5.

We have thus shown that the set $\mathfrak{T}\not=\varnothing$, where
$\mathfrak{T}$ is given by

$\mathfrak{T}:=\\{l\in\\{0,1,\dots,N-1\\}:\hat{t}_{l+1}\geq\hat{t}_{l}+T/N\\}.$

Let $l^{*}=\min\mathfrak{T}$, and note that, if $l^{*}\not=0$, then
$\hat{t}_{k+1}<\hat{t}_{k}+T/N$ for all $k<l^{*}$. It follows that (1)
$\tau^{\max}_{k+1}=\hat{t}_{l^{*}}<\infty$ and (2)
$\tau^{\min}_{k+2}=\hat{t}_{l^{*}+1}\geq\tau^{\max}_{k+1}+T/N$.

We conclude by showing that (3) holds. That is,

$\sum_{n\geq
0}\textbf{1}\\{t^{i}_{n}\in[\tau^{\min}_{k+1},\tau^{\max}_{k+1}]\\}\leq
R+1,\quad\forall i\in\mathcal{N}.$

By 5, it suffices to show that $\tau^{\max}_{k+1}-\tau^{\min}_{k+1}<(R+1)T.$

We have already shown $\hat{t}_{0}-\tau^{\min}_{k+1}\leq RT-T/N$, which
handles the case where $l^{*}=0$, and we focus on $l^{*}>0$. Since
$\hat{t}_{k+1}<\hat{t}_{k}+T/N$ for all $k<l^{*}$ and $l^{*}\leq N-1$, we have
$\tau^{\max}_{k+1}-\tau^{\min}_{k+1}=\hat{t}_{l^{*}}-\tau^{\min}_{k+1}$ and

$\displaystyle\hat{t}_{l^{*}}-\tau^{\min}_{k+1}=\left(\sum_{l=0}^{l^{*}-1}\left[\hat{t}_{l+1}-\hat{t}_{l}\right]\right)+\hat{t}_{0}-\tau^{\min}_{k+1}\leq
l^{*}(T/N)+(RT-T/N)<(R+1)T,$

which concludes the proof.

Note that the proof above also shows that for any active phase
$[\tau^{\min}_{k},\tau^{\max}_{k}]$, there exists some agent that has exactly
one opportunity to update its policy in $[\tau^{\min}_{k},\tau^{\max}_{k}]$.

For $k\geq 0$, we define $B_{k}$ to be the event that the baseline policy is a
fixed equilibrium policy throughout the $k^{th}$ active phase,
$[\tau^{\min}_{k},\tau^{\max}_{k}]$. That is,

$B_{k}:=\left\\{\bm{\phi}_{\tau^{\min}_{k}}=\cdots=\bm{\phi}_{\tau^{\max}_{k}}\in\bm{\Gamma}^{0{\rm\text{-}eq}}_{SD}\right\\}.$

We define $L:=\ell^{*}+1$, where
$\ell^{*}=\max\\{\ell(\bm{\pi}):\bm{\pi}\in\bm{\Gamma}_{SD}\\}$ and
$\ell(\bm{\pi})$ denotes the length of a shortest strict best-response path
from $\bm{\pi}\in\bm{\Gamma}_{SD}$ to an equilibrium policy in
$\bm{\Gamma}^{0{\rm\text{-}eq}}_{SD}$.

######  Lemma 5.8.

Let $\theta>0$, and define

$\xi:=\frac{1}{(R+1)NL}\min\left\\{\theta,\frac{1}{2}\min_{i\in\mathcal{N}}\\{\delta^{i},\bar{\delta}-\delta^{i}\\}\right\\}.$

Suppose $\max_{i\in\mathcal{N}}\alpha^{i}<\hat{\alpha}_{\xi}$ and $T\geq
N\hat{T}_{\xi}(\bm{\alpha})$, where $\hat{\alpha}_{\xi}$ and
$\hat{T}_{\xi}(\cdot)$ are the objects specified in Lemma 5.3. For any $k\geq
0$ and history $h_{\tau^{\max}_{k}}\in H_{\tau^{\max}_{k},\rm eq}$, we have

${\rm Pr}\left(B_{k+1}|h_{\tau^{\max}_{k}}\right)\geq 1-\theta/L.$

Remark: Since we are studying a particular realization of the exploration
phase lengths $\mathcal{T}$, we have that $\tau^{\max}_{k}\in\mathbb{Z}_{\geq
0}$ is some constant, and $h_{\tau^{\max}_{k}}$ is a
$\tau^{\max}_{k}$-history,

$h_{\tau^{\max}_{k}}=(x_{0},\bm{\phi}_{0},\widehat{\textbf{Q}}_{0},\dots,x_{\tau^{\max}_{k}},\bm{\phi}_{\tau^{\max}_{k}},\widehat{\textbf{Q}}_{\tau^{\max}_{k}}),$

with
$\bm{\phi}_{\tau^{\max}_{k}}\in\bm{\Gamma}_{SD}\cap\bm{\Gamma}^{0{\rm\text{-}eq}}$.

######  Proof 5.9.

We put $\tilde{t}_{0}:=\tau^{\min}_{k+1}$ and recursively define

$\tilde{t}_{l+1}:=\min\\{t^{i}_{n}>\tilde{t}_{l}:i\in\mathcal{N},n\geq
0\\},\quad\forall l\geq 0.$

We define $m\in\mathbb{Z}_{\geq 0}$ to be the index achieving
$\tilde{t}_{m}=\tau^{\max}_{k+1}$, and note that $m=0$ is possible when
$\tau^{\max}_{k+1}=\tau^{\min}_{k+1}$.

Note that $m$ counts the number of stage games after $\tau^{\min}_{k+1}$ and
on/before $\tau^{\max}_{k+1}$ at which _any_ player ends an exploration phase.
From the proof of Lemma 5.6 we have that

$m\leq\sum_{i\in\mathcal{N}}\sum_{n\geq
0}\textbf{1}\\{t^{i}_{n}\in[\tau^{\min}_{k+1},\tau^{\max}_{k+1}]\\}<(R+1)N.$

where the strict inequality obtains since at least one player (player $j(0)$
in the proof of Lemma 5.6) has exactly one exploration phase ending in
$[\tau^{\min}_{k+1},\tau^{\max}_{k+1}]$, while the remaining $N-1$ players
have at most $R+1$.

For each $l\in\\{0,\cdots,m\\}$, let $A_{l}$ denote the set of players who
have an opportunity to switch policies at time $\tilde{t}_{l}$. That is,

$A_{l}:=\\{i\in\mathcal{N}:\exists\;n(l)\in\mathbb{N}\text{ s.t.
}t^{i}_{n(l)}=\tilde{t}_{l}\\}.$

From our choices of $\xi,\bm{\alpha}$, and $T\geq N\hat{T}_{\xi}(\bm{\alpha})$
and the fact that $\tilde{t}_{l}\geq\tau^{\min}_{k+1}\geq\tau^{\max}_{k}+T/N$
for all $l\in\\{0,1,\dots,m\\}$, we have, by Lemma 5.3, that

${\rm Pr}\left(\Omega_{\tau^{\max}_{k}:\tilde{t}_{l}}\right)\geq
1-\xi,\quad\forall l\in\\{0,1,\dots,m\\},$

where, for any $s,t\geq 0$, we recall that $\Omega_{t:t+s}$ is given by

$\Omega_{t:t+s}=\left\\{\bm{\varpi}_{t}:\max_{i\in\mathcal{N}}\left\|\bar{Q}^{i}_{t+s}(h_{t},\bm{\varpi}_{t})-Q^{*i}_{\bm{\phi}^{-i}_{t}}\right\|_{\infty}<\xi\right\\}.$

Note that $\tilde{t}_{0}=\tau^{\min}_{k+1}$, and the minimality defining
$\tau^{\min}_{k+1}$ implies that no player updates its policy during the
interval $(\tau^{\max}_{k},\tau^{\min}_{k+1})$. It follows that the
hypothetical continuation trajectory defining each player $i$’s hypothetical
Q-factors
$\bar{Q}^{i}_{\tilde{t}_{0}}(h_{\tau^{\max}_{k}},\bm{\varpi}_{\tau^{\max}_{k}})$
coincides with the sample trajectory defining
$\widehat{\textbf{Q}}_{\tilde{t}_{0}}$, since action selections and state
transitions are decided by $\bm{\phi}_{\tau^{\max}_{k}}$ and
$\bm{\varpi}_{\tau^{\max}_{k}}$. Thus, by our choice of
$\tilde{t}_{0}=\tau^{\min}_{k+1}$,

$\bar{Q}^{i}_{\tilde{t}_{0}}(h_{\tau^{\max}_{k}},\bm{\varpi}_{\tau^{\max}_{k}})=\widehat{Q}^{i}_{\tilde{t}_{0}},\quad\forall
i\in\mathcal{N}.$

For $\bm{\varpi}_{\tau^{\max}_{k}}\in\Omega_{\tau^{\max}_{k}:\tilde{t}_{0}}$,
each player $i\in A_{0}$ recovers its estimated Q-factors
$\widehat{Q}^{i}_{\tilde{t}_{0}}$ within $\xi$ of
$Q^{*i}_{\bm{\phi}^{-i}_{\tau^{\max}_{k}}}$, since

$\widehat{Q}^{i}_{\tilde{t}_{0}}=\mathcal{Q}^{i}_{\tilde{t}_{0}}(h_{\tau^{\max}_{k}},\bm{\varpi}_{\tau^{\max}_{k}}).$

Since we have hypothesized that
$\bm{\phi}_{\tau^{\max}_{k}}\in\bm{\Gamma}^{0{\rm\text{-}eq}}_{SD}$ and chosen
$\xi<\frac{1}{2}\min\\{\delta^{i},\bar{\delta}-\delta^{i}\\}$, it follows that
agent $i$ does not change its policy at time $\tilde{t}_{0}=\tau^{\min}_{k+1}$
when given the opportunity to revise its policy. In words, the agent appraises
its policy as being sufficiently close to optimal with respect to its learned
Q-factors, and does not switch its policy. In symbols, that is to say

$\displaystyle\bm{\varpi}_{\tau^{\max}_{k}}\in\Omega_{\tau^{\max}_{k}:\tilde{t}_{0}}\Rightarrow\max_{i\in\mathcal{N}}\left\|\mathcal{Q}^{i}_{\tilde{t}_{0}}(h_{\tau^{\max}_{k}},\bm{\varpi}_{\tau^{\max}_{k}})-Q^{*i}_{\bm{\phi}^{-i}_{\tau^{\max}_{k}}}\right\|_{\infty}<\xi,$

which in turn implies that
$\bm{\phi}_{\tilde{t}_{0}}=\Phi_{\tilde{t}_{0}}(h_{\tau^{\max}_{k}},\bm{\varpi}_{\tau^{\max}_{k}})=\bm{\phi}_{\tau^{\max}_{k}}.$

Repeating this logic, one has that if

$\bm{\varpi}_{\tau^{\max}_{k}}\in\bigcap_{0\leq l\leq
m}\Omega_{\tau^{\max}_{k}:\tilde{t}_{l}}$

then
$\bm{\phi}_{\tilde{t}_{l}}=\Phi(h_{\tau^{\max}_{k}},\bm{\varpi}_{\tau^{\max}_{k}})=\bm{\phi}_{\tau^{\max}_{k}}$
for each $l\leq m$. The probability of this intersection is lower bounded
using the union bound and Lemma 5.3:

${\rm Pr}\left(\bigcap_{0\leq l\leq
m}\Omega_{\tau^{\max}_{k}:\tilde{t}_{l}}\right)\geq 1-(m+1)\xi\geq
1-\theta/L,$

as desired.

######  Lemma 5.10.

Let $\theta>0$, and define

$\xi:=\frac{1}{(R+1)NL}\min\left\\{\theta,\frac{1}{2}\min_{i\in\mathcal{N}}\\{\delta^{i},\bar{\delta}-\delta^{i}\\}\right\\}.$

Suppose $\max_{i\in\mathcal{N}}\alpha^{i}<\hat{\alpha}_{\xi}$ and $T\geq
N\hat{T}_{\xi}(\bm{\alpha})$, where $\hat{\alpha}_{\xi}$ and
$\hat{T}_{\xi}(\cdot)$ are the objects specified in Lemma 5.3. For any $k\geq
0$ and history $h_{\tau^{\max}_{k}}\in H_{\tau^{\max}_{k}}\setminus
H_{\tau^{\max}_{k},\rm eq}$, we have

${\rm Pr}\left(B_{k+L}|h_{\tau^{\max}_{k}}\right)\geq p_{\min}(1-\theta),$

where
$p_{\min}:=\prod_{j\in\mathcal{N}}\min\left\\{\frac{1-\lambda^{j}}{|\Gamma^{j}_{SD}|},\lambda^{j}\right\\}^{(R+1)L}>0$
and $L$ was defined above Lemma 5.8.

######  Proof 5.11.

Let $\bm{\pi}_{0},\dots,\bm{\pi}_{\ell}$ be a (shortest) strict best-response
path from $\bm{\pi}_{0}:=\bm{\phi}_{\tau_{k}^{\max}}$ to
$\bm{\pi}_{\ell}\in\bm{\Gamma}^{0{\rm\text{-}eq}}_{SD}$, and
$\ell\in\\{1,\dots,\ell^{*}\\}$, where $\ell^{*}$ was defined along with $L$
immediately before Lemma 5.8. For each pair of neighbouring joint policies
$\bm{\pi}_{l}$ and $\bm{\pi}_{l+1}$, there exists exactly one player $i(l)$
who switches its policy. That is, $\pi^{j}_{l+1}=\pi^{j}_{l}$ for all
$j\not=i(l)$.

Consider the event that no agent updates its policy during
$[\tau_{k}^{\max},\tau_{k+1}^{\max}]$ due to inertia except player $i(0)$, who
updates its policy exactly once to $\pi^{i(0)}_{1}$ and remains inert at all
other update opportunities in $[\tau_{k}^{\max},\tau_{k+1}^{\max}]$.

By Lemma 5.3 and Lemma 5.6, the conditional probability of this event given
$h_{\tau_{k}^{\max}}$ is lower bounded by

$(1-\theta/L)\prod_{j\in\mathcal{N}}\min\left\\{\frac{1-\lambda^{j}}{|\Gamma_{SD}^{j}|},\lambda^{j}\right\\}^{R+1}.$

The same lower bound similarly applies to each transition along
$\bm{\pi}_{0},\dots,\bm{\pi}_{\ell}$, which leads to

$\displaystyle{\rm
Pr}\left(\bm{\phi}_{\tau^{\max}_{k+\ell}}=\bm{\pi}_{\ell}\middle|h_{\tau_{k}^{\max}}\right)\geq(1-\theta/L)^{\ell}\prod_{j\in\mathcal{N}}\min\left\\{\frac{1-\lambda^{j}}{|\Gamma_{SD}^{j}|},\lambda^{j}\right\\}^{(R+1)\ell}.$

Next, consider the event that no agent updates its policy during
$[\tau^{\max}_{k+\ell},\tau^{\max}_{k+L}]$ due to inertia. The conditional
probability of this event given $h_{\tau^{\max}_{k+\ell}}$ is lower bounded by

$\prod_{j\in\mathcal{N}}(\lambda^{j})^{(R+1)(L-\ell)}.$

This results in ${\rm
Pr}(B_{k+L}|h_{\tau_{k}^{\max}})\geq(1-\theta/L)^{L}p_{\min},$ which proves
the lemma since $(1-\theta/L)^{L}\geq 1-\theta$.

###  5.4 Proof of Theorem 4.1

Given $\epsilon>0$, let $\theta>0$ be the unique solution to

$\frac{(1-\theta)p_{\min}}{\theta+(1-\theta)p_{\min}}-\theta=1-\epsilon$

and

$\xi=\frac{1}{(R+1)NL}\min\left\\{\theta,\frac{1}{2}\min_{i\in\mathcal{N}}\\{\delta^{i},\bar{\delta}-\delta^{i}\\}\right\\}.$

Suppose that

$\max_{i\in\mathcal{N}}\alpha^{i}\leq\bar{\alpha}_{\epsilon}:=\hat{\alpha}_{\xi}\>\,\textrm{and}\quad
T\geq\bar{T}_{\epsilon}(\bm{\alpha},R):=N\hat{T}_{\xi}(\bm{\alpha}).$

By Lemmas 5.8 and 5.10, for all $k\geq 0$,

(4) $\displaystyle{\rm Pr}(B_{k+L}|B_{k})$ $\displaystyle\geq 1-\theta,$ (5)
$\displaystyle{\rm Pr}(B_{k+L}|B_{k}^{c})$
$\displaystyle\geq(1-\theta)p_{\min}.$

Let $p_{k}:={\rm Pr}(B_{k})$ for all $k\geq 0$. The subsequent details lower
bounding $p_{k+mL}$ for large $m$ and every $k<L$ are omitted, as they
resemble the proofs of [1] or [37].

##  6 Simulations

In this section, we present empirical findings of a simulation study where
Algorithm 1 was applied to the stochastic game whose stage game costs and
transition probabilities are presented below.

We have chosen to simulate play of a game with two players,
$\mathcal{N}=\\{1,2\\}$, state space $\mathbb{X}=\\{s_{0},s_{1}\\}$, and two
actions per player, with action sets labelled
$\mathbb{U}^{1}=\mathbb{U}^{2}=\\{a_{0},a_{1}\\}$. Each player’s discount
factor is set to 0.8, and the transition kernel is described as follows:

$\displaystyle{\rm
Pr}\left(x_{t+1}=s_{0}|x_{t}=s_{0},u^{1}_{t},u^{2}_{t}\right)$
$\displaystyle\equiv 0.5,$ $\displaystyle{\rm
Pr}\left(x_{t+1}=s_{0}|x_{t}=s_{1},u^{1}_{t}=u^{2}_{t}\right)$
$\displaystyle=0.25$ $\displaystyle{\rm
Pr}\left(x_{t+1}=s_{0}|x_{t}=s_{1},u^{1}_{t}\not=u^{2}_{t}\right)$
$\displaystyle=0.9$

In words, the state dynamics out of state $s_{0}$ do not depend on the choice
of joint action, while the dynamics out of state $s_{1}$ do. In state $s_{1}$,
if players select matching actions, then the state transitions to $s_{0}$ with
(low) probability 0.25. Otherwise, if players select distinct actions in state
$s_{1}$, play transitions to state $s_{0}$ with (high) probability 0.9.

The stage game’s symmetric cost structure is summarized by the tables below.

22[] &$a_{0}$ $a_{1}$
$a_{0}$ 0, 0 2, 2
$a_{1}$ 2, 2 0, 0

(a) State $s_{0}$: low cost state

22[] &$a_{0}$ $a_{1}$
$a_{0}$ 10, 10 11, 11
$a_{1}$ 11, 11 10, 10

(b) State $s_{1}$: high cost state

Figure 1: Stage costs: Player 1 (respectively, 2) picks a row (column), and
its stage cost is the 1st (2nd) entry of the chosen cell.

In either state, the stage cost to a given player is minimized by selecting
one’s action to match the action choice of the opponent. We note that the
stage costs in state $s_{0}$ are considerably lower than those of state
$s_{1}$. Despite the apparent coordination flavour of the stage game payoffs,
the transition probabilities dictate that an optimizing agent should _not_
match its counterpart’s action in state $s_{1}$, and should instead attempt to
drive play to the low cost state $s_{0}$.

The challenge of non-stationarity to multi-agent learning in this game is
such: if players use a joint policy under which they mismatch actions in state
$s_{0}$ or match actions in state $s_{1}$, then either player has an incentive
to switch its policy in the relevant state. If both players switch policies in
an attempt to respond to the other, then cyclic behaviour ensues, where the
individual responds to an outdated policy, as the other player will have
switched its behaviour by the time the individual is ready to update its own
policy.

With the cost structure, transition probabilities, and discount factors
described above, we have the joint policies in which players’ actions match in
state $s_{0}$ and players’ actions do not match in state $s_{1}$ constitute
0-equilibrium policies.

### Parameter Choices

We conducted 500 independent trials of Algorithm 1. Each trial consisted of
$10^{6}$ stage games. Each player’s exploration phase lengths, $T^{i}_{k}$,
were selected uniformly at random from the interval $[T,R\cdot T]$, with $T$
set to $5000$ and the ratio parameter $R$ set to $R=3$.

For our gameplay parameters, we set the stage game action experimentation
parameters to be $\rho^{1}=\rho^{2}=0.05$. The parameter controlling inertia
in the policy update was chosen as $\lambda^{1}=\lambda^{2}=0.2$. The
parameter controlling tolerance for sub-optimality in Q-factor assessment was
chosen as $\delta^{1}=\delta^{2}=0.5$. The learning rate parameters were
selected to be $\alpha^{1}=\alpha^{2}=0.08$.

### Results

The results of our simulations are summarized below in Figure 2 and Table 1.
With randomly selected initial policies, we observed that Algorithm 1 rapidly
drove play to equilibrium, with the relative frequency of equilibrium
stabilizing at over 98% of trials after approximately 40,000 stage games.

Figure 2: Frequency of $\bm{\phi}_{t}\in\bm{\Gamma}^{0{\rm\text{-}eq}}_{SD}$, averaged over 500 trials. Stage game index $t=$ | 0 | 10,000 | 20,000 | 30,000 | 40,000
---|---|---|---|---|---
$\frac{1}{500}\sum_{k=1}^{500}\textbf{1}\\{\bm{\phi}_{t}\in\bm{\Gamma}^{0{\rm\text{-}eq}}_{SD}\\}$ | 0.264 | 0.620 | 0.728 | 0.974 | 0.984
Table 1: Frequency of equilibrium at select stage game indices

##  7 Conclusions

In this paper, we considered an asynchronous variant of the decentralized
Q-learning algorithm of [1]. We formalized an argument presented in [24],
which contended that inertia alone would stabilize the learning process and
tame non-stationarity. In the process of formalizing the argument of [24],
some modifications were needed to handle technical nuances relating to the
dynamics of the policy process and the convergence of learning iterates. To
accommodate asynchronous policy updating and non-stationarity in each agent’s
learning environment, we have introduced a constant learning rate that can
rapidly overcome errors in learning estimates that are artifacts of outdated
information. In so doing, we have shown that decentralized Q-learning can
still drive policies to equilibrium in weakly acyclic stochastic games without
making strong coordination assumptions such as synchronizing the schedules on
which players update their policies.

## References

  * [1] Gürdal Arslan and Serdar Yüksel.  Decentralized Q-learning for stochastic teams and games.  IEEE Transactions on Automatic Control, 62(4):1545–1558, 2017.
  * [2] Carolyn L Beck and Rayadurgam Srikant.  Error bounds for constant step-size Q-learning.  Systems & Control Letters, 61(12):1203–1208, 2012.
  * [3] Vivek S Borkar.  Reinforcement learning in markovian evolutionary games.  Advances in Complex Systems, 5(01):55–72, 2002.
  * [4] Michael Bowling and Manuela Veloso.  Multiagent learning using a variable learning rate.  Artificial Intelligence, 136(2):215–250, 2002.
  * [5] Caroline Claus and Craig Boutilier.  The dynamics of reinforcement learning in cooperative multiagent systems.  In Proceedings of the Tenth Innovative Applications of Artificial Intelligence Conference, Madison, Wisconsin, pages 746–752, 1998\.
  * [6] Constantinos Daskalakis, Dylan J Foster, and Noah Golowich.  Independent policy gradient methods for competitive reinforcement learning.  Advances in Neural Information Processing Systems, 33:5527–5540, 2020.
  * [7] Arlington M. Fink.  Equilibrium in a stochastic $n$-person game.  Journal of Science of the Hiroshima University, Series AI (Mathematics), 28(1):89–93, 1964.
  * [8] D. P. Foster and H. P. Young.  On the nonconvergence of fictitious play in coordination games.  Games Econ. Behav., 25:79–96, 1998.
  * [9] Dean Foster and H. Peyton Young.  Regret testing: Learning to play Nash equilibrium without knowing you have an opponent.  Theoretical Economics, 1:341–367, 2006.
  * [10] Fabrizio Germano and Gabor Lugosi.  Global Nash convergence of Foster and Young’s regret testing.  Games and Economic Behavior, 60(1):135–154, 2007.
  * [11] Pablo Hernandez-Leal, Michael Kaisers, Tim Baarslag, and Enrique Munoz de Cote.  A survey of learning in multiagent environments: Dealing with non-stationarity.  arXiv preprint arXiv:1707.09183, 2017.
  * [12] Pablo Hernandez-Leal, Bilal Kartal, and Matthew E Taylor.  A survey and critique of multiagent deep reinforcement learning.  Autonomous Agents and Multi-Agent Systems, 33(6):750–797, 2019\.
  * [13] Junling Hu and Michael P. Wellman.  Nash Q-learning for general-sum stochastic games.  Journal of Machine Learning Research, 4(Nov):1039–1069, 2003.
  * [14] Jens Josephson and Alexander Matros.  Stochastic imitation in finite games.  Games and Economic Behavior, 49(2):244–259, 2004.
  * [15] Vijaymohan R Konda and Vivek S Borkar.  Actor-critic–type learning algorithms for markov decision processes.  SIAM Journal on control and Optimization, 38(1):94–123, 1999.
  * [16] Stefanos Leonardos, Will Overman, Ioannis Panageas, and Georgios Piliouras.  Global convergence of multi-agent policy gradient in Markov potential games.  arXiv preprint arXiv:2106.01969, 2021.
  * [17] D. Leslie and E. Collins.  Individual Q-learning in normal form games.  SIAM Journal on Control and Optimization, 44:495–514, 2005.
  * [18] David S Leslie and Edmund J Collins.  Convergent multiple-timescales reinforcement learning algorithms in normal form games.  The Annals of Applied Probability, 13(4):1231–1251, 2003.
  * [19] Yehuda Levy.  Discounted stochastic games with no stationary nash equilibrium: two examples.  Econometrica, 81(5):1973–2007, 2013.
  * [20] Michael L. Littman.  Markov games as a framework for multi-agent reinforcement learning.  In Machine Learning Proceedings 1994, pages 157–163. Elsevier, 1994\.
  * [21] Michael L. Littman.  Friend-or-foe Q-learning in general-sum games.  In ICML, volume 1, pages 322–328, 2001.
  * [22] Michael L. Littman and Csaba Szepesvári.  A generalized reinforcement-learning model: Convergence and applications.  In ICML, volume 96, pages 310–318. Citeseer, 1996.
  * [23] Chinmay Maheshwari, Manxi Wu, Druv Pai, and Shankar Sastry.  Independent and decentralized learning in markov potential games.  arXiv preprint arXiv:2205.14590, 2022.
  * [24] Jason R. Marden, H. Peyton Young, Gürdal Arslan, and Jeff S. Shamma.  Payoff-based dynamics for multiplayer weakly acyclic games.  SIAM Journal on Control and Optimization, 48(1):373–396, 2009.
  * [25] Laetitia Matignon, Guillaume J. Laurent, and Nadine Le Fort-Piat.  Independent reinforcement learners in cooperative markov games: a survey regarding coordination problems.  Knowledge Engineering Review, 27(1):1–31, 2012.
  * [26] Eric Mazumdar, Lillian J Ratliff, Michael I Jordan, and S Shankar Sastry.  Policy-gradient algorithms have no guarantees of convergence in linear quadratic games.  arXiv preprint arXiv:1907.03712, 2019.
  * [27] Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras.  Cycles in adversarial regularized learning.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2703–2717. SIAM, 2018.
  * [28] David H Mguni, Yutong Wu, Yali Du, Yaodong Yang, Ziyi Wang, Minne Li, Ying Wen, Joel Jennings, and Jun Wang.  Learning in nonzero-sum stochastic games with potentials.  In International Conference on Machine Learning, pages 7688–7699. PMLR, 2021.
  * [29] Hadi Nekoei, Akilesh Badrinaaraayanan, Amit Sinha, Mohammad Amini, Janarthanan Rajendran, Aditya Mahajan, and Sarath Chandar.  Dealing with non-stationarity in decentralized cooperative multi-agent deep reinforcement learning via multi-timescale learning.  arXiv preprint arXiv:2302.02792, 2023.
  * [30] Asuman Ozdaglar, Muhammed O Sayin, and Kaiqing Zhang.  Independent learning in stochastic games.  arXiv preprint arXiv:2111.11743, 2021.
  * [31] Muhammed Sayin, Kaiqing Zhang, David Leslie, Tamer Başar, and Asuman Ozdaglar.  Decentralized Q-learning in zero-sum Markov games.  Advances in Neural Information Processing Systems, 34:18320–18334, 2021.
  * [32] Muhammed O Sayin and Onur Unlu.  Logit-q learning in markov games.  arXiv preprint arXiv:2205.13266, 2022.
  * [33] Satinder Singh, Tommi Jaakkola, Michael L Littman, and Csaba Szepesvári.  Convergence results for single-step on-policy reinforcement-learning algorithms.  Machine learning, 38(3):287–308, 2000.
  * [34] Ming Tan.  Multi-agent reinforcement learning: Independent vs. cooperative agents.  In Proceedings of the Tenth International Conference on Machine Learning, pages 330–337, 1993.
  * [35] J. N. Tsitsiklis.  Asynchronous stochastic approximation and Q-learning.  Machine Learning, 16(3):185–202, 1994.
  * [36] Bora Yongacoglu, Gürdal Arslan, and Serdar Yüksel.  Decentralized learning for optimality in stochastic dynamic teams and games with local control and global state information.  IEEE Transactions on Automatic Control, 67(10):5230–5245, 2022\.
  * [37] Bora Yongacoglu, Gürdal Arslan, and Serdar Yüksel.  Satisficing paths and independent multi-agent reinforcement learning in stochastic games.  SIAM Journal on Mathematics of Data Science, to appear.
  * [38] H. Peyton Young.  Strategic Learning and its Limits.  Oxford University Press., 2004.
  * [39] Runyu Zhang, Zhaolin Ren, and Na Li.  Gradient play in multi-agent Markov stochastic games: Stationary points and convergence.  arXiv preprint arXiv:2106.00198, 2021.