ifaamas [AAMAS ’23]Proc. of the 22nd International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2023)May 29 – June 2, 2023 London, United
KingdomA. Ricci, W. Yeoh, N. Agmon, B. An (eds.) 2023 2023 none
printacmref=false printfolios=true Univ. Grenoble Alpes, Inria, CNRS, Grenoble
INP, LIG 38000 Grenoble France Univ. Grenoble Alpes, Inria, CNRS, Grenoble
INP, LIG 38000 Grenoble France Univ. Grenoble Alpes, Inria, CNRS, Grenoble
INP, LIG 38000 Grenoble France

# Decentralized model-free reinforcement learning in stochastic games with
average-reward objective

Romain Cravic<EMAIL_ADDRESS>,  Nicolas Gast<EMAIL_ADDRESS>and  Bruno Gaujal<EMAIL_ADDRESS>
(Date: October 2022)

###### Abstract.

We propose the first model-free algorithm that achieves low regret performance
for decentralized learning in two-player zero-sum tabular stochastic games
with infinite-horizon average-reward objective. In decentralized learning, the
learning agent controls only one player and tries to achieve low regret
performances against an arbitrary opponent. This contrasts with centralized
learning where the agent tries to approximate the Nash equilibrium by
controlling both players. In our infinite-horizon undiscounted setting,
additional structure assumptions is needed to provide good behaviors of
learning processes : here we assume for every strategy of the opponent, the
agent has a way to go from any state to any other. This assumption is the
analogous to the ”communicating” assumption in the MDP setting. We show that
our Decentralized Optimistic Nash Q-Learning (DONQ-learning) algorithm
achieves both sublinear high probability regret of order $T^{3/4}$ and
sublinear expected regret of order $T^{2/3}$. Moreover, our algorithm enjoys a
low computational complexity and low memory space requirement compared to the
previous works of Wei et al. (2017) and Jafarnia-Jahromi et al. (2021) in the
same setting.

##  1\. Introduction

Recently, reinforcement learning, combined with technologicalprogress, has
achieved superhuman performances in computing optimal behaviors in various
decision processes. Particularly, there is a development of self-play
algorithms to design strong artificial intelligence in games such as Go or
Chess Silver et al. (2017, 2018). These methods have the practical interest
that they do not require supervision neither with huge data set nor with
expert feedback to train efficiently. We focus here on Competitive Multi-Agent
Reinforcement Learning (MARL) where several agents interact with an
environment that may involve randomness, in order to maximize their own
profit. One of the mostly used model to deal with MARL is stochastic game
(a.k.a. Markov game in the literature) that was introduced in the 50s by
Shapley Shapley (1953). Stochastic games (SGs) are more pertinent to handle
MARL compared to Markov decision processes (MDPs) that are widely used for
single-agent reinforcement learning.

Here we consider learning in infinite-horizon two-player zero-sum game with
the average-reward criterion: There are two players that play indefinitely,
and each player wins exactly what their opponent loses. At each time, the game
has a current state and players choose and play an action simultaneously :
they receive rewards and then the state of the environment changes (possibly
randomly), this depending on the current state and the joint choice of
actions. At the early stage of the game, the reward function and transition
probabilities are unknown by the learning agent.

An important concept in stochastic games is the Nash equilibrium. In two-
player zero-sum stochastic games, all Nash equilibria have the same value
which represents a bound of the minimum expected average-reward that each
player can obtain if they play optimally, regardless of the strategy of the
opponent. When both agents play according to the Nash equilibrium, each of
them can not hope a greater payoff by changing unilaterally his own strategy.
Therefore, Nash equilibrium is often a benchmark for learning performances and
a large set of works focus on this notion.

Two settings can be considered for learning in stochastic games: centralized
and decentralized. In the first setting, a central learner tries to find the
Nash equilibrium as quick as possible by controlling both players, _e.g._
Littman (1994); Sidford et al. (2020); Bai and Jin (2020); Bai et al. (2020);
Xie et al. (2020). In the second setting, the learner controls only one player
and tries to be as efficient as possible against an arbitrary opponent, see
Brafman and Tennenholtz (2002); Wei et al. (2017); Tian et al. (2021);
Jafarnia-Jahromi et al. (2021); Xie et al. (2020); Sayin et al. (2021); Liu et
al. (2022); Mao and Başar (2022); Sayin et al. (2022); Wei et al. (2021) for
different settings and objectives. This setting is quite natural but more
challenging than the first one because the learner has no control on the
opponent strategy that may change over time. In this paper, we consider the
decentralized learning problem. Several definitions for the regret are
possible in this case, that we will discuss in more detail in Section 2.3.

Learning algorithms are often split into two families called respectively
model-based algorithms and model-free algorithms. In a model-based algorithm,
the learner gathers observations of the game in order to estimate the
parameters of the model (reward functions and transition probabilities), and
then uses this estimation to compute a policy that is used for playing and
gathering more information. In a model-free algorithm, the learner directly
tries to estimate the values of the true model and plays optimally according
to these value estimations. The two papers that are closest to ours are the
algorithms UCSG in Wei et al. (2017) and PSRL-ZSG in Jafarnia-Jahromi et al.
(2021). They both present a decentralized learning algorithm in average-reward
SG and are both model-based. To the best of our knowledge, we propose in this
paper the first model-free algorithm for the stochastic games with infinite-
horizon average-reward objective. Model-free algorithms have the advantage
that they often need considerably less memory space to work, and additionally
they often enjoy much better time complexity, which motivates our work. They
can also be generalized to other settings, such as linear SGs. The drawbacks
of model-free is that, in the literature, model-based algorithms often achieve
better performances than model-free.

###  1.1. Our contribution

We propose an algorithm, that we call decentralized optimisticNash Q-learning
(DONQ-learning). This algorithm is designed for infinite-horizon stochastic
games with average-reward objective. Our paper uses Q-learning optimism
techniques similar to the one introduced by Jin _et al._ in their seminal
paper Jin et al. (2018) for finite-horizon MDPs. This optimistic Q-learning
has then been extended in two directions: (1) to infinite-horizon average-
reward MDPs in Wei and Jafarnia-Jahromi (2020) by using an artificial
discounted setting, and (2) to finite horizon stochastic games in Bai et al.
(2020); Tian et al. (2021). In this paper we combine these two lines of work
to obtain an efficient learning algorithm with sublinear regret in infinite-
horizon average-reward SGs. We show that the expected regret of DONQ-learning
is sublinear in time and is bounded by
$O(D(SAB\log(2T^{2}))^{\frac{1}{3}}T^{\frac{2}{3}})$, where $T$ is the time
horizon, $S$ is the number of states, $A$ and $B$ are the size of learner’s
and of the opponent’s actions sets, and $D$ a known upper bound of the span of
the game. This result is similar to the bound obtained in Wei and Jafarnia-
Jahromi (2020) for the regret in infinite-horizon MDP. In addition, our
algorithm enjoys a low computational complexity and low memory space
requirement compared to the previous works of Wei et al. (2017) and Jafarnia-
Jahromi et al. (2021) in the same setting. We also provide a high-probability
bound for the regret of our algorithm. Surprisingly, our analysis also shows a
high probability upper bound for the regret of order
$O(\sqrt{D\log(2/\delta)}T^{\frac{3}{4}})$, which has a dependency in $T$ that
is significantly higher than for the expected regret. This higher dependency
in $T$ is due to an additional term that appears because of our decentralized
setting where the learner may play against a weak opponent. This additional
term appears as a martingale difference sequence which disappears when the
expected regret is considered.

##### Outline

The rest of the paper is organized as follows. We first introduce the model,
the regret definition and some background on optimistic Q-learning in Section
2. We present our DONQ-learning algorithm in Section 3. In Section 4, we give
the regret upper bounds (expected regret and regret with high probability),
along with their proofs. We provide a proof of the most important technical
lemmas in Section 5, and the proofs of some other lemmas are delegated to the
Appendix. Finally, we conclude in Section 6.

###  1.2. Related work

Q-learning in MDP : Q-learning algorithms appeared in 1989 in the seminal
paper of Watkins Watkins (1989). The first provably-efficient Q-learning
appears in Jin et al. (2018), where the authors add an optimism term to
Q-learning and prove that the algorithm achieves low regret performances in
finite-horizon MDPs. The authors use a smart choice of learning rates that we
also use in this paper. The same techniques are then adapted in Dong et al.
(2019) for the discounted setting to derive an algorithm with sample-
complexity guaranties. The above two works are used in Wei and Jafarnia-
Jahromi (2020) to derive an optimistic Q-learning for average-reward MDPs that
has a regret bound of order $T^{\frac{2}{3}}$. This algorithm only assumes
that the MDP is weakly-communicating. Our work is inspired from Wei and
Jafarnia-Jahromi (2020) and extend their algorithm for the decentralized
multi-agent setting.

Q-learning in SG : For stochastic games, a Q-learning with optimism principle
first appears in Bai et al. (2020) for finite-horizon problems. An adaptation
to decentralized learning (still in finite-horizon SG) is given in Tian et al.
(2021). For the infinite-horizon setting, the authors of Sayin et al. (2021)
use Q-learning in discounted SG for decentralized learning but without
optimism so they only establish convergence results. Our work differs from the
above because we consider the infinite-horizon average-reward setting.

Other model-free approaches : Some papers propose other model-free algorithms,
different from Q-learning, that also use optimism techniques. This includes
the following:
V-learning : An unavoidable assumption to use Q-learning like algorithms is
that the learner must observe the opponent’s action at each time. The
V-learning algorithm is proposed in Bai et al. (2020) for centralized learning
in finite-horizon SG, and then is adapted in Tian et al. (2021) to design an
efficient algorithm for decentralized learning when the agents do not observe
the action of their opponent.
OOMD : For infinite-horizon average-reward MDP, the authors of Wei and
Jafarnia-Jahromi (2020) propose the OOMD algorithm that achieves a regret
bound of order $\sqrt{T}$ when they assume the ergodicity assumption. They
construct an adversarial multi-armed bandit instance for each state to design
efficient policies.
Gradient descent : Gradient descent is another approach for decentralized
learning in SG when the agent does not observe the action of its opponent.
Some papers propose procedures based on the optimistic gradient descent to
achieve Nash equilibrium identification guaranties after a finite time, for
the finite-horizon setting in Daskalakis et al. (2020), and for the discounted
setting in Wei et al. (2021).

Model-based algorithms : To the best of our knowledge, all the algorithms that
deal with learning in infinite-horizon average reward stochastic games are
model-based. UCRL2 is introduced in Auer et al. (2008) and uses optimism to
achieve sublinear regret bounds in infinite-horizon average-reward MDP with
finite diameter. In Wei et al. (2017), UCRL2 is adapted into UCSG for SG
setting, and two possible definitions for the diameter are proposed. These
definitions extend the notions of ”communicating” MDP and ”ergodic” MDP for
SG. Under the weakest assumption, UCSG enjoys a regret bound of order
$T^{\frac{2}{3}}$. In this paper we assume the same diameter assumption. In a
recent work, inspired from PSRL algorithm for MDP, PSRL-ZSG algorithm is
proposed in Jafarnia-Jahromi et al. (2021) and achieves a Bayesian regret of
order $\sqrt{T}$ under the same structure assumption. Our work does not
improve the above regret bounds but the model-free property of our algorithm
induces a lower computational complexity and memory space requirement than the
previous model-based algorithms. Plus, we do not study Bayesian regret but
worst-case expected regret or worst-case high probability regret.

##  2\. Preliminaries

###  2.1. Stochastic game model and notations

We consider two-player zero-sum simultaneous stochastic games (also known as
Markov games in the literature), which generalize the standard Markov decision
processes (MDPs) into the two-player setting where both players try to
maximize their own payoff. Zero-sum means that in this game, what a player
wins corresponds exactly to what the other loses. We write the payoff for the
point of the first player, that we call the max-player. This player tries to
maximize the payoff whereas the second player, that we call the min-player,
tries to minimize it. In this paper, the learner is the max-player and the
opponent is the min-player. The term simultaneous means that the two players
choose simultaneously how to interact with the environment at each time. Here
we consider the infinite-horizon setting where players play indefinitely. At
each time step, the game is in a current state known by the players and they
play simultaneously an action. The players obtain a reward and the state of
the game changes, both depending on the current state and the choices of
actions.

Formally, an instance of an infinite-horizon stochastic game is a tuple
$(\mathcal{S},\mathcal{A},\mathcal{B},r,P)$, where $\mathcal{S}$ is a set of
states, $\mathcal{A}$ is the action set of the max-player, and $\mathcal{B}$
it the action set of the min-player. We assume that all the states and actions
spaces are finite and of sizes $S$, $A$ and $B$. For every
$s,a,b\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}$, $r(s,a,b)\in[0,1]$ is
the reward that the max-player wins (and that the min-player loses) when the
pair of actions $(a,b)$ is played in state $s$. Then the next state of the
game is randomly drawn with the probability distribution $P(.|s,a,b)$. At each
time step $t$ the players observe the states of the game $s_{t}$, they both
choose simultaneously an action $a_{t}$ and $b_{t}$ that they play. They then
observe the action of their opponent, receive the reward
$r(s_{t},a_{t},b_{t})$. The next state $s_{t+1}$ is then drawn according to
$P(.|s_{h},a_{h},b_{h})$.

Markovian policies : A max-player Markovian policy
$\mu:\mathcal{S}\rightarrow\Delta_{\mathcal{A}}$ is a function that maps every
state $s$ with a probability distribution $\mu(.|s)$ on max-player’s actions.
Similarly, a min-player Markovian policy
$\nu:\mathcal{S}\rightarrow\Delta_{\mathcal{B}}$ maps every state $s$ with a
probability distribution $\nu(.|s)$ on min-player’s actions. The pair of
policies $(\mu,\nu)$ determines the rewards and the dynamics of the game.

Notations : For a function $f:\mathcal{S}\rightarrow\mathbb{R}$, we write
$Pf(s,a,b)$ for $\sum_{s^{\prime}}P(s^{\prime}|s,a,b)f(s^{\prime})$. We also
write $sp(f)$ for $\max_{s}f(s)-\min_{s}f(s)$.
For a function
$g:\mathcal{S}\times\mathcal{A}\times\mathcal{B}\rightarrow\mathbb{R}$ and a
pair of Markovian policies $(\mu,\nu)$, we write
$\mathbb{D}_{(\mu,\nu)}[g](s)=\mathbb{E}_{a\sim\mu(.|s),b\sim\nu(.|s)}[g(s,a,b)]$.
To lighten notation, we sometimes write $g^{(\mu,\nu)}(s)$ for this quantity.
In particular, for the reward and transition probability, we have:

$\displaystyle r^{(\mu,\nu)}(s)$
$\displaystyle=\mathbb{E}_{a\sim\mu(.|s),b\sim\nu(.|s)}[r(s,a,b)]$
$\displaystyle P^{(\mu,\nu)}(s^{\prime}|s)$
$\displaystyle=\mathbb{E}_{a\sim\mu(.|s),b\sim\nu(.|s)}[P(s^{\prime}|s,a,b)].$

###  2.2. Average-reward and game structure

In this paper we establish low regret bounds for the undiscounted setting
where players play indefinitely and try to maximize their average-reward over
time. The average-reward of a pair of policies $(\mu,\nu)$ is defined for
every state $s$, whenever the limit exists, by

$J^{(\mu,\nu)}(s)=\lim_{T\rightarrow+\infty}\frac{1}{T}\mathbb{E}_{(\mu,\nu)}\left[\sum_{t=1}^{T}r^{(\mu,\nu)}(s_{t})\mid
s_{1}=s\right],$

where $\mathbb{E}_{(\mu,\nu)}$ hides that the $(s_{t})_{t}$ is a Markov chain
whose transition kernel is $P^{(\mu,\nu)}$. This represents the expected
average-reward for the max-player starting from state $s$ if both players play
policies $\mu$ and $\nu$ respectively.

Given a min-player policy $\nu$, a best response against $\nu$ for the
undiscounted setting is a max-player policy $\mu^{*}$ such that for all state
$s$, $J^{(\mu^{*},\nu)}(s)=\max_{\mu}J^{(\mu,\nu)}(s)$. Similarly, given a
max-player policy $\mu$, a best response against $\mu$ is a min-player policy
$\nu^{*}$ such that for all state $s$,
$J^{(\mu,\nu^{*})}(s)=\min_{\nu}J^{(\mu,\nu)}(s)$.

To deal with the undiscounted setting, we assume the following structure
property, which is known in the particular case of MDP, to be a minimal
relevant framework for learning Bartlett and Tewari (2012) :

######  Asumption 1.

For every pair $(s,s^{\prime})$ of states, and any min-player policy $\nu$,
there exists a max-player policy $\mu$ such that $s^{\prime}$ is accessible
from $s$ with positive probability under policies $(\mu,\nu)$.

This assumption is intuitively necessary to get low regret because if this
assumption does not hold, it means that the opponent may have a way to lock
the learning agent in ”bad stage” while at the early stage of the learning
process, the agent could not have enough information to avoid this. Note that
for the MDP setting, the analog of this assumption would be to assume that the
MDP is ”communicating”: here the SG is communicating for the max-player’s
point of view, _i.e._ , from the learner’s point of view. In fact we may
additionally assume the existence of a set of states that are transient under
all Markovian policies, which would be the analogous property of ”weakly
communicating” for the MDP setting. This would not change our result but would
complexify notations and proofs.

As a consequence of Assumption 1, if $T^{(\mu,\nu)}_{s\rightarrow s^{\prime}}$
is the expected time to go from $s$ to $s^{\prime}$ under policies
$(\mu,\nu)$, there exists a real number $D$ such that

$\max_{s,s^{\prime}}\max_{\nu}\min_{\mu}T^{(\mu,\nu)}_{s\rightarrow
s^{\prime}}\leq D$

The minimal $D$ is the diameter of the game Wei et al. (2017). In this paper,
we denote by $D$ an upper bound of the diameter and we suppose that this $D$
is known by the learning agent, so $D$ can be used to set some values of
parameters.

We summarize important results that hold under Assumption 1 in the Theorem 1
below. This theorem justifies the relevance of the learning objective in this
framework. For a proof of these results, we refer to Theorem E.1 of Wei et al.
(2017).

######  Theorem 1 (Theorem E.1 of Wei et al. (2017)).

Under assumption 1, there exist a unique real number $J^{*}$, a function
$h^{*}:\mathcal{S}\longrightarrow\mathbb{R}$, and a pair of Markovian policies
$(\mu^{*},\nu^{*})$ such that

  1. (1)

$J^{*}=\max_{\mu}\min_{\nu}J^{(\mu,\nu)}(s)=\min_{\nu}\max_{\mu}J^{(\mu,\nu)}(s)$
for every $s$ : the game value exists and does not depend on $s$.

  2. (2)

$(\mu^{*},\nu^{*})$ is a pair of Markovian policies such that
$J^{(\mu^{*},\nu^{*})}(s)=J^{*}$ for all $s$ : $\mu^{*}$ is a best response
against $\nu^{*}$ and vice-versa (Nash equilibrium).

  3. (3)

$sp(h^{*})\leq D$ and satisfies the following Bellman’s optimality equations :

$\displaystyle J^{*}+h^{*}(s)$ $\displaystyle=$
$\displaystyle\max_{\mu}\left(r^{(\mu,\nu^{*})}(s)+P^{(\mu,\nu^{*})}h^{*}(s)\right),$
$\displaystyle J^{*}+h^{*}(s)$ $\displaystyle=$
$\displaystyle\min_{\nu}\left(r^{(\mu^{*},\nu)}(s)+P^{(\mu^{*},\nu)}h^{*}(s)\right).$

###  2.3. Learning objective

In this paper, we consider a decentralized learning algorithm that has a low
regret in a two-player zero-sum stochastic game. Nash equilibria in this
setting provide to players an optimal way to play whatever their opponent
does: If the max-player plays their Nash policy, it guarantees them an
average-reward of at least $J^{*}$ against any opponent and we want to measure
the online performance of the learning agent compared to this Nash policy.
Thus our regret is given by

$\text{Reg}(T)=\sum_{t=1}^{T}\left(J^{*}-r(s_{t},a_{t},b_{t})\right)$ (1)

This definition is classical for the regret in decentralized learning Wei et
al. (2017); Tian et al. (2021); Jafarnia-Jahromi et al. (2021), and
generalizes the definition for the MDP setting Auer et al. (2008); Wei and
Jafarnia-Jahromi (2020). Note that in contrast with MDPs, the regret is not
necessarily non-negative: If the opponent is weak, then the learning agent can
achieve an average-reward greater than $J^{*}$. The definition in Equation (1)
ensures that, whatever the opponent’s strategy, the learner should learn a
defensive strategy that works against it - but does not need to exploit the
opponent’s weakness - to achieve sublinear performances.

A stronger regret definition would be to consider that the learner competes
with the best response against the opponent (potentially assuming this one
uses only Markovian policies). This would lead to the following regret
definition:

$\sum_{t=1}^{T}\left(\max_{\mu}J^{(\mu,\nu_{t})}-r(s_{t},a_{t},b_{t})\right),$

or a weaker version where the learner competes with the best fixed (over time)
max-player policy, that is

$\max_{\mu}\sum_{t=1}^{T}\left(J^{(\mu,\nu_{t})}-r(s_{t},a_{t},b_{t})\right).$

Unfortunately, it is shown in Liu et al. (2022) that for the finite-horizon
setting, it is not possible to design an algorithm that has a sublinear regret
with the two above learning objectives. Hence, and because the infinite-
horizon setting is more general than the finite-horizon one, in this paper we
focus on the regret definition given by (1).

###  2.4. Background on discounted SG

As we will see later, our DONQ-learning algorithm, uses an artificial
discounted setting to run. Hence, we recall here some facts and notations
about the discounted setting.

In the discounted setting, what players get at time $t$ is amortized by a
factor $\gamma^{t-1}$ where $\gamma<1$ is called the discount factor. Given a
discount factor $\gamma$ and a pair of policies $(\mu,\nu)$, the value
function for the discounted setting is defined for every state $s$ as

$V_{\gamma}^{(\mu,\nu)}(s)=\mathbb{E}_{(\mu,\nu)}\left[\sum_{t=1}^{+\infty}\gamma^{t-1}r^{(\mu,\nu)}(s_{t})\mid
s_{1}=s\right],$

where $\mathbb{E}_{(\mu,\nu)}$ hides that the $(s_{t})_{t}$ is a Markov chain
whose transition kernel is $P^{(\mu,\nu)}$. This represents the expected
discounted cumulative reward for the max-player starting from state $s$ if
both players play policies $\mu$ and $\nu$ respectively. Then, for every pair
of actions $(a,b)$, the Q-value function in $(s,a,b)$ is defined as

$Q_{\gamma}^{(\mu,\nu)}(s,a,b)=r(s,a,b)+\gamma
PV_{\gamma}^{(\mu,\nu)}(s,a,b).$

This represents the expected discounted cumulative reward for the max-player
starting from state $s$ where players first play $a$ and $b$ respectively, and
then follow policies $\mu$ and $\nu$ respectively. Therefore, for every state
$s$ we have the relation

$V_{\gamma}^{(\mu,\nu)}(s)=\mathbb{D}_{(\mu,\nu)}[Q_{\gamma}^{(\mu,\nu)}](s).$

Given a min-player policy $\nu$, a best response against $\nu$ for the
$\gamma$-discounted setting is a max-player policy $\mu^{*}$ such that for all
state $s$,
$V_{\gamma}^{(\mu^{*},\nu)}(s)=\max_{\mu}V_{\gamma}^{(\mu,\nu)}(s)$.
Similarly, given a max-player policy $\mu$, a best response against $\mu$ is a
min-player policy $\nu^{*}$ such that for all state $s$,
$V_{\gamma}^{(\mu,\nu^{*})}(s)=\min_{\nu}V_{\gamma}^{(\mu,\nu)}(s)$.

It is known that there always exists a pair of policies
$(\mu^{\gamma},\nu^{\gamma})$ such that $\mu^{\gamma}$ is a best response
against $\nu^{\gamma}$ and vice-verse for the $\gamma$-discounted setting.
$(\mu^{\gamma},\nu^{\gamma})$ is called a Nash equilibrium of the game. All
Nash equilibria have the same value function, denoted by $V_{\gamma}^{*}$,
which satisfies for every state $s$

$V_{\gamma}^{*}(s)=\max_{\mu}\min_{\nu}V_{\gamma}^{(\mu,\nu)}(s)=\min_{\nu}\max_{\mu}V_{\gamma}^{(\mu,\nu)}(s).$

We also denote by $Q_{\gamma}^{*}$ the unique Q-value function of the Nash
equilibria. $V_{\gamma}^{*}$ and $Q_{\gamma}^{*}$ satisfy the following
Bellman’s optimality equations for all $(s,a,b)$ :

$\displaystyle Q_{\gamma}^{*}(s,a,b)$ $\displaystyle=r(s,a,b)+\gamma
PV_{\gamma}^{*}(s,a,b),$ $\displaystyle V_{\gamma}^{*}(s)$
$\displaystyle=\max_{\mu}\min_{\nu}\mathbb{D}_{(\mu,\nu)}[Q_{\gamma}^{*}](s).$

We recall (see e.g. Wei et al. (2017) Lemma E.2) that under Assumption 1, if
$D$ is a bound on the diameter of the game as defined above, then for any
$\gamma<1$ we have

$sp(V_{\gamma}^{*})\leq D.$ (2)

###  2.5. Learning rate notations and properties

In our DONQ-learning algorithm, we use optimistic Q-learning updates to
maintain estimators. At a given time $t$, such an algorithm observes the
current state-action triplet $(s,a,b)$ and updates the $Q$-value of this
triplet as:

$Q_{t+1}(s,a,b)\leftarrow(1-\alpha_{\tau})Q_{t}(s,a,b)+\alpha_{\tau}(\text{[new
sample]}+\text{[bonus]}),$

where $\tau$ is the number of visits of the triplet $(s,a,b)$ up to time $t$.

The quantity $\alpha_{\tau}$ is called the learning rate and has to be well-
chosen to ensure good learning performances. In the optimistic Q-learning
algorithm for $H$-finite-horizon MDPs, the authors of Jin et al. (2018)
propose the learning rate $\alpha_{\tau}=\frac{H+1}{H+\tau}$ and they show
that such a learning rate has good properties summarized in Lemma 2 below. For
every $0\leq\tau\leq T$, they define
$\alpha_{\tau}^{0}=\prod_{j=1}^{\tau}(1-\alpha_{j})$ and for all $1\leq
i\leq\tau$, $\alpha_{\tau}^{i}=\alpha_{i}\prod_{j=i+1}^{\tau}(1-\alpha_{j})$.
Note that if $\tau\geq 1$, $\alpha_{\tau}^{0}=0$ and that
$\sum_{i==0}^{\tau}\alpha_{\tau}^{i}=1$. The sequence $\alpha_{\tau}^{i}$ has
the following properties.

######  Lemma 0 (Lemma 4.1 of Jin et al. (2018)).

The sequence $\alpha_{\tau}^{i}$ satisfy :

  1. (1)

$\frac{1}{\sqrt{\tau}}\leq\sum_{i=1}^{\tau}\frac{\alpha_{\tau}^{i}}{\sqrt{i}}\leq\frac{2}{\sqrt{\tau}}$
for every $\tau\geq 1$.

  2. (2)

$\sum_{t=1}^{\tau}(\alpha_{\tau}^{i})^{2}\leq\frac{2H}{\tau}$ for every
$\tau\geq 1$.

  3. (3)

$\sum_{\tau=i}^{\infty}\alpha_{\tau}^{i}\leq 1+\frac{1}{H}$ for every $i\geq
1$

In this paper we use the same choice of learning rate for some carefully
chosen parameter $H$.

##  3\. The DONQ-learning Algorithm

The main idea of our decentralized optimistic Nash Q-learning (that we present
in Algorithm 1) is to learn the game in a well-chosen discounted setting using
optimistic Q-Learning techniques first introduced in Jin et al. (2018). The
convenience of the $\gamma$-discounted setting is that the Q-values are well-
defined and bounded by $1/(1-\gamma)$ which enables to build and maintain
optimistic estimators $\overline{Q}_{t}$ for the Nash Q-value
$Q_{\gamma}^{*}$.

Algorithm 1 DONQ-learning Algorithm

1:Parameters : $H>1$, $\delta\in(0,1)$

2:Initialization : $\forall s,a,b$

3:$\overline{Q}_{1}(s,a,b)=\overline{Q}^{\downarrow}_{1}(s,a,b)=\overline{V}^{\downarrow}_{1}(s)=H$

4:$N_{1}(s,a,b)=0$ ; $\mu_{1}(a|s)=1/A$ ; $\gamma=1-1/H$

5:$\forall\tau\geq
1,\quad\alpha_{\tau}=\frac{H+1}{H+\tau}\quad\beta_{\tau}=2D\sqrt{\frac{H\log(2T/\delta)}{\tau}}$

6:Begin :

7:Observe $s_{1}$.

8:for $t=1,2,\ldots,T$ do

9: Draw and play $a_{t}\sim\mu_{t}(.|s_{t})$.

10: Observe $b_{t}$ (drawn from the unknown opponent’s policy).

11: Observe $r(s_{t},a_{t},b_{t})$ and $s_{t+1}$.

12: Increment $N_{t+1}(s_{t},a_{t},b_{t})\leftarrow
N_{t}(s_{t},a_{t},b_{t})+1$

13: Set $\tau:=N_{t+1}(s_{t},a_{t},b_{t})$ and update $Q$-estimators as:
$\displaystyle\overline{Q}_{t+1}(s_{t},a_{t},b_{t})$
$\displaystyle\leftarrow(1-\alpha_{\tau})\overline{Q}_{t}(s_{t},a_{t},b_{t})+{}$
$\displaystyle\phantom{{}\leftarrow{}}\alpha_{\tau}\left[r(s_{t},a_{t},b_{t})+\gamma\overline{V}^{\downarrow}_{t}(s_{t+1})+\beta_{\tau}\right]$
$\displaystyle\overline{Q}^{\downarrow}_{t+1}(s_{t},a_{t},b_{t})$
$\displaystyle\leftarrow\min{\left(\overline{Q}^{\downarrow}_{t}(s_{t},a_{t},b_{t}),\overline{Q}_{t+1}(s_{t},a_{t},b_{t})\right)}$

14: Update the policy
$(\mu_{t+1}(.|s_{t}),\tilde{\nu}_{t+1}(.|s_{t}))\leftarrow\text{GetNashPolicies}\left(\overline{Q}^{\downarrow}_{t+1}(s_{t},.,.)\right)$

15: Update $V$-estimator
$\overline{V}_{t+1}^{\downarrow}(s_{t})\leftarrow\mathbb{D}_{(\mu_{t+1},\tilde{\nu}_{t+1})}[\overline{Q}_{t+1}^{\downarrow}](s_{t})$

16: $N_{t+1}$, $\overline{Q}_{t+1}$, $\overline{Q}_{t+1}^{\downarrow}$,
$\overline{V}_{t+1}^{\downarrow}$, $\mu_{t+1}$ are kept equal to their values
at the previous time step, $N_{t}$, $\overline{Q}_{t}$,
$\overline{Q}_{t}^{\downarrow}$, $\overline{V}_{t}^{\downarrow}$, $\mu_{t}$,
for all other $s,a,b$.

17:end for

The DONQ-learning algorithm takes as input a parameter $H$ and defines a
discount factor $\gamma=1-\frac{1}{H}$. The agent then operates as if it was
in a discounted objective. The algorithm also takes as parameter a confidence
level $\delta\in(0,1)$ which is set either to obtain a high probability regret
bound, or to obtain a sublinear expected regret.

All optimistic estimators are initialized with $H$. At each time $t$, the
learner plays an action $a_{t}$ drawn from the current policy $\mu_{t}$ and
observes the opponent action $b_{t}$, the reward $r(s_{t},a_{t},b_{t})$ and
the next state $s_{t+1}$. Then the optimistic estimator $\overline{Q}_{t+1}$
is updated for the current state-actions tuple $(s_{t},a_{t},b_{t})$, by using
an optimistic Q-learning like operation with a learning rate
$\alpha_{\tau}=\frac{H+1}{H+\tau}$, the current optimistic estimator of the
next state value $\overline{V}_{t}^{\downarrow}(s_{t+1})$ and a bonus term
$\beta_{\tau}$ that scales in $D\sqrt{\frac{H}{\tau}}$, where $\tau$ is the
number of visits of state-actions tuple $(s_{t},a_{t},b_{t})$. For technical
reasons, the algorithm maintains a non-increasing version of
$\overline{Q}_{t}$, denoted by $\overline{Q}_{t}^{\downarrow}$, which is the
one used to update the learner’s policy and to compute the optimistic value
estimators $\overline{V}_{t}^{\downarrow}$.

The learner’s policy is updated for the current state $s_{t}$ :
$\mu_{t+1}(.|s_{t})$ is chosen to be the max-player Nash policy of the matrix
game $\overline{Q}_{t+1}^{\downarrow}(s_{t},.,.)$. Note that if $\mu^{*}$ is
an optimal Markovian Nash policy of the max-player, then for all $s$,
$\mu^{*}(.|s)$ is a max-player Nash policy of the matrix game $Q^{*}(s,.,.)$.
Then the algorithm also computes the min-player Nash policy
$\tilde{\nu}_{t+1}(.|s_{t})$ of the matrix game
$\overline{Q}_{t+1}^{\downarrow}(s_{t},.,.)$ in order to update
$\overline{V}_{t+1}^{\downarrow}(s_{t})$ as the expected value of
$\overline{Q}_{t+1}^{\downarrow}(s_{t},.,.)$ under policies $\mu_{t+1}$ and
$\tilde{\nu}_{t+1}$. We emphasize that $\tilde{\nu}_{t+1}$ is not the policy
used by the opponent at time $t+1$ (the opponent’s policy is unknown to us and
can be arbitrary).

##  4\. Theoretical guarantees

###  4.1. Main results: Regret Guarantees

The key challenge is to correctly set the parameter $H$ to obtain sublinear
regret guarantees. On the one hand, a large value for $H$ implies that the
undiscounted objective is well approximated by the discounted case, but at the
same time, the regret coming from the discounted analysis will be large. On
the other hand, a small value of $H$ means that the undiscounted objective is
not well approximated by the discounted case, which may have bad consequences
the regret.

We give here two regret bounds, with high probability and in expectation, both
with a sublinear dependency in $T$ obtained with a smart choice of the
parameter $H$. First, Theorem 3 provides the high probability regret bound,
depending on the parameter $H$.

######  Theorem 3.

For any $\delta\in(0,1)$, there exists an absolute111By absolute, we mean a
constant that does not depend on any of the models parameters. constant $C$
such that with probability at least $1-3\delta$, the regret is bounded by

$\displaystyle\text{Reg}(T)\leq$ $\displaystyle
D\frac{T}{H}+2H\sqrt{2T\log(2/\delta)}$
$\displaystyle+12D\sqrt{SABHT\log(2T/\delta)}$
$\displaystyle+C\left(SABH+D\sqrt{T\log(4/\delta)}\right).$

If the parameter $H$ scales in $T^{\frac{1}{4}}$, this theorem shows a high
probability regret bound of order $T^{\frac{3}{4}}$. Indeed, such a value of
$H$ balances the terms $\frac{T}{H}$ and $H\sqrt{T}$ that appear in our
analysis.

######  Corollary 1.

For any $\delta\in(0,1)$, we have that with probability at least $1-3\delta$,
by setting the parameter
$H=\sqrt{\frac{D}{\log(2/\delta)^{\frac{1}{2}}}}T^{\frac{1}{4}}$, for $T$
sufficiently large the regret is upper bounded by

$\text{Reg}(T)\leq\sqrt{D\log(2/\delta)^{\frac{1}{2}}}T^{\frac{3}{4}}+o\left(T^{\frac{3}{4}}\right).$

The second term of the regret bound of Theorem 3 has a $H\sqrt{T}$ factor.
This term does not appear in the analysis of Wei and Jafarnia-Jahromi (2020)
for the MDP case. It is due to the fact that we were not able to bound
$(\overline{Q}_{t}^{\downarrow}-Q_{\gamma}^{*})(s_{t},a_{t},b_{t})$ with a
better bound than $H$ (see Equation ${\bf(s4)}$ in the regret decomposition
below). This difficulty appears because the learner plays against an opponent
that may be possibly weak. More explanations are given in Appendix A.7. This
term appears because we simply use Azuma-Hoeffding’s inequality for our high
probability regret bound. However, since this term appears as terms of a
martingale difference sequence, their sum can be bounded more efficiently when
we consider the expected regret, as we see below.

Theorem 4 provides upper bounds for the expected regret, also depending on the
parameter $H$. This bound is similar to the regret bound of Theorem 3 with
$\delta=1/T$ but is significantly smaller because the second term of the
regret bound of Theorem 3 disappears.

######  Theorem 4.

There exists an absolute constant $C$ such that

$\displaystyle\mathbb{E}[\text{Reg}(T)]\leq$ $\displaystyle
D\frac{T}{H}+12D\sqrt{SABHT\log(2T^{2})}$
$\displaystyle+C\left(SABH+D\sqrt{T\log(4T)}\right).$

By setting a parameter $H$ that scales in $T^{\frac{1}{3}}$, we can balance
the terms $\frac{T}{H}$ and $\sqrt{HT}$ (due to regret bound for discounted
setting) and obtain a regret bound in expectation of order $T^{\frac{2}{3}}$.
The bound that we obtain for the expected regret is then significantly smaller
than the high probability bound of Corollary 1 because Theorem 4 does not has
the term in $H\sqrt{T}$ as Theorem 3.

######  Corollary 2.

For $T$ sufficiently large, by setting the parameter
$H=\left(\frac{T}{SAB\log(2T^{2})}\right)^{1/3}$, the expectation of the
regret is bounded by

$\mathbb{E}[\text{Reg}(T)]\leq
D(SAB\log(2T^{2}))^{\frac{1}{3}}T^{\frac{2}{3}}+o\left(T^{\frac{2}{3}}\right).$

We highlight the fact that in the algorithm and our analysis, we only use that
the diameter $D$ is an upper bound of $sp(h^{*})$ (Theorem 1) and $sp(V^{*})$
: any other known quantity that satisfies these two properties can replace $D$
in the parameter setting and the theoretical guarantees.

###  4.2. Computational complexity

An interesting property of Q-learning like algorithms is that only the values
of the current state and state-action tuple are updated at each step. This
contrasts with model-based approaches Wei et al. (2017); Jafarnia-Jahromi et
al. (2021) where some policies have to be entirely computed in the inner loop
of the algorithm, or with value-iteration like algorithms Bai and Jin (2020);
Xie et al. (2020) where a sweep of the state space is needed at each step. The
only non-constant time operation in DONQ-learning is the call to
GetNashPolicies procedure, but it is known that we can compute the value and
the Nash policy of a zero-sum matrix game of size $A\times B$ in a polynomial
time via linear programming Khachiyan (1979); Gay et al. (1986), and this does
depend on the size of the state space.

###  4.3. Proofs of Theorems 3 and 4

To show Theorem 3 and 4, we decompose the regret as follows:

$\displaystyle\text{Reg}(T)=$
$\displaystyle\sum_{t=1}^{T}(J^{*}-r(s_{t},a_{t},b_{t}))$ $\displaystyle=$
$\displaystyle\sum_{t=1}^{T}(J^{*}-(1-\gamma)V^{*}_{\gamma}(s_{t}))$
$\displaystyle\bf{(s1)}$
$\displaystyle+\sum_{t=1}^{T}(V^{*}_{\gamma}(s_{t})-\mathbb{D}_{(\mu_{t},\nu_{t})}[Q^{*}_{\gamma}](s_{t})-\zeta_{t})$
$\displaystyle\bf{(s2)}$
$\displaystyle+\sum_{t=1}^{T}(\mathbb{D}_{(\mu_{t},\nu_{t})}[Q^{*}_{\gamma}](s_{t})-r(s_{t},a_{t},b_{t})-\gamma
V^{*}_{\gamma}(s_{t}))$ $\displaystyle\bf{(s3)}$
$\displaystyle+\sum_{t=1}^{T}\zeta_{t}$ $\displaystyle{\bf(s4)}$

where
$\zeta_{t}=\mathbb{D}_{(\mu_{t},\nu_{t})}[\overline{Q}_{t}^{\downarrow}-Q^{*}_{\gamma}](s_{t})-(\overline{Q}_{t}^{\downarrow}-Q^{*}_{\gamma})(s_{t},a_{t},b_{t})$.
Note that $\\{\zeta_{t}\\}_{t}$ is a martingale difference sequence, bounded
by $2H$ in absolute value, with respect to the $\sigma$-algebra generated by
all random variables up to $s_{t}$ since $a_{t}$ and $b_{t}$ are drawn with
policies $\mu_{t}(.|s_{t})$ and $\nu_{t}(.|s_{t})$ respectively. We bound
(s1), (s2) and (s3) separately, sometimes under high probability events, and
we finally deal with (s4) specifically for both types of regret bounds.

####  4.3.1. Analysis of the term (s1)

The term ${\bf(s1)}$ represents the gap we pay because we learn in an
artificial discounted setting. Each term of ${\bf(s1)}$ tends to 0 when
$\gamma$ is close to 1, that is when $H$ is big. Concretely we show the
following Lemma 5 :

######  Lemma 0.

For every $s\in\mathcal{S}$,

$\left|J^{*}-(1-\gamma)V^{*}_{\gamma}(s)\right|\leq(1-\gamma)D=\frac{D}{H}.$

When summing over $t$ in (s1), a factor $T$ appears but the factor $1/H$
enables to get a sublinear dependency in $T$ in the regret with a well-chosen
parameter $H$.

####  4.3.2. Analysis of the term (s2)

Then, we first bound (s2) under an event $\mathcal{E}_{\delta}$ defined below
for any $\delta\in(0,1)$ and that ensures in particular that
$\overline{Q}_{t}^{\downarrow}$ and $\overline{V}_{t}^{\downarrow}$ are really
upper bounds of $Q_{\gamma}^{*}$ and $V_{\gamma}^{*}$ respectively.

$\mathcal{E}_{\delta}$ := For all $(s,a,b)$ and time $t$, the following
inequalities hold $(\overline{Q}_{t}^{\downarrow}-Q_{\gamma}^{*})(s,a,b)\geq
0,\quad\quad(\overline{V}_{t}^{\downarrow}-V_{\gamma}^{*})(s)\geq 0,$ (3)
$\displaystyle(\overline{Q}_{t+1}^{\downarrow}-Q_{\gamma}^{*})(s,a,b)\leq$
$\displaystyle\alpha_{\tau}^{0}H+6D\sqrt{\frac{H}{\tau}\log(2T/\delta)}$
$\displaystyle\phantom{\alpha_{\tau}^{0}H}+\sum_{i=1}^{\tau}\gamma\alpha_{\tau}^{i}\left[(\overline{V}_{t_{i}}^{\downarrow}-V_{\gamma}^{*})(s_{t_{i}+1})\right]$
(4) where $\tau=N_{t+1}(s,a,b)$ and $t_{1},t_{2},\ldots,t_{\tau}$ the times
where $(s,a,b)$ was visited.

######  Lemma 0.

For any $\delta\in(0,1)$, $\mathcal{E}_{\delta}$ is true with probability at
least $1-\delta$.

A proof of Lemma 6 is given in Appendix A.1. $\mathcal{E}_{\delta}$ holds with
probability at least $1-\delta$ and under $\mathcal{E}_{\delta}$, Lemma 7
gives an upper bound for ${\bf(s2)}$ that scales in $\sqrt{HT}$. This is the
main contribution of the regret due to performances of optimistic Q-learning
in the discounted setting.

######  Lemma 0.

For any $\delta\in(0,1)$, under $\mathcal{E}_{\delta}$, there exists an
absolute constant $c$ such that

$\displaystyle\sum_{t=1}^{T}(V_{\gamma}^{*}(s_{t})-\mathbb{D}_{(\mu_{t},\nu_{t})}[Q_{\gamma}^{*}](s_{t})-\zeta_{t})$
$\displaystyle\leq 12D\sqrt{SABHT\log(2T/\delta)}$
$\displaystyle\qquad+cSABH.$

####  4.3.3. Analysis of the term (s3)

To bound ${\bf(s3)}$ we define an other event $\mathcal{E}_{\delta}^{\prime}$
for any $\delta\in(0,1)$ that ensures that Azuma-Hoeffding’s inequalities used
on functions $V_{\gamma}^{*}$ and $Q_{\gamma}^{*}$ hold.

$\mathcal{E}_{\delta}^{\prime}$ : The two following inequalities hold
$\left|\sum_{t=1}^{T}(\mathbb{D}_{(\mu_{t},\nu_{t})}[Q_{\gamma}^{*}](s_{t})-Q_{\gamma}^{*}(s_{t},a_{t},b_{t}))\right|\leq(1+\gamma
D)\sqrt{2T\log(4/\delta)}$ (5)
$\left|\sum_{t=1}^{T}(PV_{\gamma}^{*}(s_{t},a_{t},b_{t})-V_{\gamma}^{*}(s_{t+1}))\right|\leq
D\sqrt{2T\log(4/\delta)}$ (6)

######  Lemma 0.

$\mathcal{E}_{\delta}^{\prime}$ holds with probability at least $1-\delta$

A proof of Lemma 8 is given in Appendix A.2. In fact, the terms in ${\bf(s3)}$
are almost terms of Bellman’s equations so, since
$\mathcal{E}_{\delta}^{\prime}$ holds with probability at least $1-\delta$, we
bound ${\bf(s3)}$ with high probability as shown in Lemma 9 that is proved in
Appendix A.3.

######  Lemma 0.

For any $\delta\in(0,1)$, under $\mathcal{E}_{\delta}^{\prime}$, there exists
an absolute constant $c^{\prime}$ such that

$\sum_{t=1}^{T}(\mathbb{D}_{(\mu_{t},\nu_{t})}[Q_{\gamma}^{*}](s_{t})-r(s_{t},a_{t},b_{t})-\gamma
V_{\gamma}^{*}(s_{t}))\leq c^{\prime}D\sqrt{T\log(4/\delta)}.$

####  4.3.4. Analysis of the term (s4) and conclusion

We prove the high probability regret bound by compiling the previous high
probability bounds on (s1), (s2), and (s3) (Lemmas 5, 7 and 9). Additionally
we use Azuma-Hoeffding to bound $\sum_{t=1}^{T}\zeta_{t}$ with high
probability. This makes appear a term that scales in $H\sqrt{T}$. We balance
this term and the term $\frac{T}{H}$ of (s1) with a well-chosen parameter $H$
of order $T^{\frac{1}{4}}$ to obtain an upper bound of order $T^{\frac{3}{4}}$
for the regret. More details are given in Appendix A.5.

We also establish the regret bound in expectation using the results of
previous sections (Lemmas 5, 7 and 9). To deal with the remaining
$\sum_{t=1}^{T}\zeta_{t}$, we use the fact that $\\{\zeta_{t}\\}$ is a
martingale difference sequence (bounded sequence with a conditional
expectation of 0 according to its filtration) to show that its weight is
negligible especially in the case where the previous high probability events
hold. We then set $H$ smartly to balance the dominant term $\frac{T}{H}$ and
$\sqrt{HT}$ with respect to $T$, and obtain the desired regret bound in
expectation of order $T^{\frac{2}{3}}$. More details are given in the Appendix
A.6.

##  5\. Proofs of main Lemmas

Here we give the proofs of Lemma 5 and 7. All the other omited proofs are
given in Appendix. Lemma 5 (resp. Lemma 7) induces the term that scales in
$\frac{T}{H}$ (resp. $\sqrt{HT}$) in the statements of Theorems 3 and 4.

###  5.1. Proof of Lemma 5

We denote by $(\mu^{*},\nu^{*})$ and $h^{*}$ the Nash equilibrium for the
undiscounted setting and the bounded function, both given by Theorem 1. We
also denote by $(\mu^{\gamma},\nu^{\gamma})$ a Nash equilibrium for the
discounted setting with discount $\gamma$.

By sub-optimality of $\mu^{*}$ against $\nu^{\gamma}$ for the discounted
setting (first inequality), and the sub-optimality of $\nu^{\gamma}$ against
$\mu^{*}$ for the undiscounted setting (second inequality), we get

$\displaystyle V^{*}_{\gamma}(s)$ $\displaystyle\geq
V^{(\mu^{*},\nu^{\gamma})}_{\gamma}(s)$
$\displaystyle=\mathbb{E}_{\mu^{*},\nu^{\gamma}}\left[\sum_{t=1}^{+\infty}\gamma^{t-1}r^{(\mu^{*},\nu^{\gamma})}(\mathscr{s}_{t})\quad|\mathscr{s}_{1}=s\right]$
$\displaystyle\geq\mathbb{E}_{\mu^{*},\nu^{\gamma}}\left[\sum_{t=1}^{+\infty}\gamma^{t-1}\left(J^{*}+h^{*}(\mathscr{s}_{t})-P^{(\mu^{*},\nu^{\gamma})}h^{*}(\mathscr{s}_{t})\right)\quad|\mathscr{s}_{1}=s\right].$

Since $\mathscr{s}_{t+1}$ is generated with transition probability
$P^{(\mu^{*},\nu^{\gamma})}(.|\mathscr{s}_{t})$ in the stochastic process
under $\mathbb{E}_{\mu^{*},\nu^{\gamma}}$, the last term in the expectation
can be seen as $h^{*}(\mathscr{s}_{t+1})$. Therefore we get

$\displaystyle V^{*}_{\gamma}(s)$
$\displaystyle\geq\frac{J^{*}}{1-\gamma}+\mathbb{E}_{\mu^{*},\nu^{\gamma}}\left[\sum_{t=1}^{+\infty}\gamma^{t-1}(h^{*}(\mathscr{s}_{t})-h^{*}(\mathscr{s}_{t+1}))\quad|\mathscr{s}_{1}=s\right]$
$\displaystyle=\frac{J^{*}}{1-\gamma}+h^{*}(\mathscr{s}_{1})-\mathbb{E}_{\mu^{*},\nu^{\gamma}}\left[\sum_{t=2}^{+\infty}(\gamma^{t-2}-\gamma^{t-1})h^{*}(\mathscr{s}_{t})\quad|\mathscr{s}_{1}=s\right]$
$\displaystyle\geq\frac{J^{*}}{1-\gamma}+\min_{s}h^{*}(s)-\max_{s}h^{*}(s)\sum_{t=2}^{+\infty}(\gamma^{t-2}-\gamma^{t-1})$
$\displaystyle\geq\frac{J^{*}}{1-\gamma}-sp(h^{*})$
$\displaystyle\geq\frac{J^{*}}{1-\gamma}-D.$

By the sub-optimality of $\nu^{*}$ against $\mu^{\gamma}$ in the discounted
setting (first inequality), and the sub-optimality of $\mu^{\gamma}$ against
$\nu^{*}$ in the undiscounted setting (second inequality), we have

$\displaystyle V^{*}_{\gamma}(s)$ $\displaystyle\leq
V^{(\mu^{\gamma},\nu^{*})}_{\gamma}(s)$
$\displaystyle=\mathbb{E}_{(\mu^{\gamma},\nu^{*})}\left[\sum_{t=1}^{+\infty}\gamma^{t-1}r^{(\mu^{\gamma},\nu^{*})}(\mathscr{s}^{\prime}_{t})\quad|\mathscr{s}^{\prime}_{1}=s\right]$
$\displaystyle\leq\mathbb{E}_{(\mu^{\gamma},\nu^{*})}\left[\sum_{t=1}^{+\infty}\gamma^{t-1}(J^{*}+h^{*}(\mathscr{s}^{\prime}_{t})-P^{(\mu^{\gamma},\nu^{*})}h^{*}(\mathscr{s}^{\prime}_{t}))\quad|\mathscr{s}^{\prime}_{1}=s\right].$

Here, $\mathscr{s}^{\prime}_{t+1}$ is generated with transition probability
$P^{(\mu^{\gamma},\nu^{*})}(.|\mathscr{s}^{\prime}_{t})$ in the stochastic
process under $\mathbb{E}_{(\mu^{\gamma},\nu^{*})}$, the last term in the
expectation can be seen as $h^{*}(\mathscr{s}^{\prime}_{t+1})$. Therefore we
get

$\displaystyle V^{*}_{\gamma}(s)$
$\displaystyle\leq\frac{J^{*}}{1-\gamma}+\mathbb{E}_{\mu^{\gamma},\nu^{*}}\left[\sum_{t=1}^{+\infty}\gamma^{t-1}(h^{*}(\mathscr{s}^{\prime}_{t})-h^{*}(\mathscr{s}^{\prime}_{t+1}))\quad|\mathscr{s}^{\prime}_{1}=s\right]$
$\displaystyle=\frac{J^{*}}{1-\gamma}+h^{*}(\mathscr{s}^{\prime}_{1})-\mathbb{E}_{\mu^{\gamma},\nu^{*}}\left[\sum_{t=2}^{+\infty}(\gamma^{t-2}-\gamma^{t-1})h^{*}(\mathscr{s}^{\prime}_{t})\quad|\mathscr{s}^{\prime}_{1}=s\right]$
$\displaystyle\leq\frac{J^{*}}{1-\gamma}+\max_{s}h^{*}(s)-\min_{s}h^{*}(s)\sum_{t=2}^{+\infty}(\gamma^{t-2}-\gamma^{t-1})$
$\displaystyle\leq\frac{J^{*}}{1-\gamma}+sp(h^{*})$
$\displaystyle\leq\frac{J^{*}}{1-\gamma}+D.$

Putting both parts together and multiplying by $(1-\gamma)$ we obtain the
desired statement.

###  5.2. Proof of Lemma 7

We simply write $V^{*}$ and $Q^{*}$ for $V^{*}_{\gamma}$ and $Q^{*}_{\gamma}$
respectively to lighten notations.

For every time $t$ we have

$V^{*}(s_{t})-\mathbb{D}_{(\mu_{t},\nu_{t})}[Q^{*}](s_{t})=(V^{*}-\overline{V}_{t}^{\downarrow})(s_{t})+(\overline{V}_{t}^{\downarrow}-\mathbb{D}_{(\mu_{t},\nu_{t})}[Q^{*}])(s_{t}).$

The second difference is upper bounded by

$\displaystyle\overline{V}_{t}^{\downarrow}(s_{t})-\mathbb{D}_{(\mu_{t},\nu_{t})}[Q^{*}](s_{t})$
$\displaystyle=\mathbb{D}_{\mu_{t},\tilde{\nu}_{t}}[\overline{Q}_{t}^{\downarrow}](s_{t})-\mathbb{D}_{(\mu_{t},\nu_{t})}[Q^{*}](s_{t})$
$\displaystyle\leq\mathbb{D}_{(\mu_{t},\nu_{t})}[\overline{Q}_{t}^{\downarrow}-Q^{*}](s_{t})$
$\displaystyle=(\overline{Q}_{t}^{\downarrow}-Q^{*})(s_{t},a_{t},b_{t})+\zeta_{t}$
$\displaystyle=(\overline{Q}_{t+1}^{\downarrow}-Q^{*})(s_{t},a_{t},b_{t})$
$\displaystyle\phantom{=}\hskip
2.84544pt+(\overline{Q}_{t}^{\downarrow}-\overline{Q}_{t+1}^{\downarrow})(s_{t},a_{t},b_{t})+\zeta_{t}.$

The inequality holds by definition of $\tilde{\nu}_{t}$ as a best-response
against $\mu_{t}$ for the matrix game
$\overline{Q}_{t}^{\downarrow}(s_{t},.,.)$. Under $\mathcal{E}_{\delta}$,
inequality (4.3.2) bounds the term
$(\overline{Q}_{t+1}^{\downarrow}-Q^{*})(s_{t},a_{t},b_{t})$, and therefore,

$\displaystyle V^{*}(s_{t})-\mathbb{D}_{(\mu_{t},\nu_{t})}$
$\displaystyle[Q^{*}](s_{t})-\zeta_{t}\leq(V^{*}-\overline{V}_{t}^{\downarrow})(s_{t})$
$\displaystyle+(\overline{Q}_{t}^{\downarrow}-\overline{Q}_{t+1}^{\downarrow})(s_{t},a_{t},b_{t})$
$\displaystyle+6D\sqrt{\frac{H}{n_{t}}\log(2T/\delta)}$
$\displaystyle+\sum_{i=1}^{n_{t}}\gamma\alpha_{n_{t}}^{i}\left[(\overline{V}_{t_{i}(s_{t},a_{t},b_{t})}^{\downarrow}-V^{*})(s_{t_{i}(s_{t},a_{t},b_{t})+1})\right],$

where $n_{t}=N_{t+1}(s_{t},a_{t},b_{t})$ and $t_{i}(s_{t},a_{t},b_{t})$ is the
$i$-th time when $(s_{t},a_{t},b_{t})$ has been visited. Note that
$\alpha_{n_{t}}^{0}H=0$ since
$n_{t}=N_{t+1}(s_{t},a_{t},b_{t})>0$ by definition.

Now we sum over $t$ to get (s2). We need this technical Lemma :

######  Lemma 0.

Under $\mathcal{E}_{\delta}$, we have

$\gamma\sum_{t=1}^{T}\sum_{i=1}^{n_{t}}\alpha_{n_{t}}^{i}(\overline{V}_{t_{i}(s_{t},a_{t},b_{t})}^{\downarrow}-V^{*})(s_{t_{i}(s_{t},a_{t},b_{t})+1})\leq
SH+\sum_{t=2}^{T+1}(\overline{V}_{t}^{\downarrow}-V^{*})(s_{t})$

where $n_{t}=N_{t+1}(s_{t},a_{t},b_{t})$ and $t_{i}(s_{t},a_{t},b_{t})$ is the
$i$-th time when $(s_{t},a_{t},b_{t})$ has been visited.

A proof of Lemma 10 is given in Appendix A.4.

  * •

By Lem.10,
$\sum_{t=1}^{T}\sum_{i=1}^{n_{t}}\gamma\alpha_{n_{t}}^{i}(\overline{V}_{t_{i}(s_{t},a_{t},b_{t})}^{\downarrow}-V^{*})(s_{t_{i}(s_{t},a_{t},b_{t})+1})\leq
SH+\sum_{t=2}^{T+1}(\overline{V}_{t}^{\downarrow}-V^{*})(s_{t})$. This gives a
telescoping sum with
$\sum_{t=1}^{T}(V^{*}-\overline{V}_{t}^{\downarrow})(s_{t})$ and only
$(\overline{V}_{T+1}^{\downarrow}-V^{*})(s_{T+1})-(\overline{V}_{1}^{\downarrow}-V^{*})(s_{1})\leq
2H$ remains.

  * •

Since $\overline{Q}_{t}^{\downarrow}$ decreases of at most $H$ per tuple
$(s,a,b)$, we have
$\sum_{t=1}^{T}(\overline{Q}_{t}^{\downarrow}-\overline{Q}_{t+1}^{\downarrow})(s_{t},a_{t},b_{t})\leq
SABH.$

  * •

Since $\sum_{s,a,b}N_{T+1}(s,a,b)=T$, we have

$\displaystyle\sum_{t=1}^{T}\frac{1}{\sqrt{n_{t}}}=\sum_{t=1}^{T}\sum_{s,a,b}\frac{{\bf
1}(s_{t}=s,a_{t}=a,b_{t}=b)}{\sqrt{N_{t+1}(s,a,b)}}=\sum_{s,a,b}\sum_{j=1}^{N_{T+1}(s,a,b)}\frac{1}{\sqrt{j}}$
$\displaystyle\leq\sum_{s,a,b}2\sqrt{N_{T+1}(s,a,b)}\leq
2\sqrt{SAB\sum_{s,a,b}N_{T+1}(s,a,b)}\leq 2\sqrt{SABT}.$

Putting every thing together, we get the desired inequality for a certain
absolute constant $c$.

##  6\. Conclusion

In this work we propose the DONQ-learning algorithm that is the first model-
free algorithm that deals with decentralized learning in infinite-horizon
average-reward stochastic games. It uses an artificial discounted setting in
order to use optimism techniques developed in previous works. This algorithm
achieves sublinear regret performances both with high probability and in
expectation. Surprisingly, our analysis gives a high probability upper bound
of order $T^{\frac{3}{4}}$ whereas we show an upper bound of order
$T^{\frac{2}{3}}$ for the expected regret. We are not sure if this difference
is a proof artifact or an actual difference between the expected and high-
probability regret. The high probability regret bound is obtained by choosing
a parameter $H=T^{1/4}$ while the bound for the expected regret is obtained by
choosing $H=T^{1/3}$. An open question is whether choosing $H=T^{1/3}$ leads
to a high probability bound in $T^{2/3}$ or in $T^{5/6}$ which is the high
probability bound given by our analysis. Another open question is to know if
there exists a model-free algorithm that achieves the information-theoretical
lower bound of order $T^{\frac{1}{2}}$ under our Assumption 1. For future
work, the same setting (decentralized learning in infinite-horizon average-
reward SG) where we additionally assume that the opponent’s actions are
unobservable may be studied. This has already been studied for the finite-
horizon setting with for instance the V-learning algorithm. It would be
interesting to see if such model-free algorithms can be adapted to the
infinite-horizon setting.

## References

  * (1)
  * Auer et al. (2008) Peter Auer, Thomas Jaksch, and Ronald Ortner. 2008\.  Near-optimal regret bounds for reinforcement learning.  _Advances in neural information processing systems_ 21 (2008).
  * Bai and Jin (2020) Yu Bai and Chi Jin. 2020\.  Provable self-play algorithms for competitive reinforcement learning. In _International conference on machine learning_. PMLR, 551–560.
  * Bai et al. (2020) Yu Bai, Chi Jin, and Tiancheng Yu. 2020.  Near-optimal reinforcement learning with self-play.  _Advances in neural information processing systems_ 33 (2020), 2159–2170.
  * Bartlett and Tewari (2012) Peter L Bartlett and Ambuj Tewari. 2012.  REGAL: A regularization based algorithm for reinforcement learning in weakly communicating MDPs.  _arXiv preprint arXiv:1205.2661_ (2012).
  * Brafman and Tennenholtz (2002) Ronen I Brafman and Moshe Tennenholtz. 2002.  R-max-a general polynomial time algorithm for near-optimal reinforcement learning.  _Journal of Machine Learning Research_ 3, Oct (2002), 213–231.
  * Daskalakis et al. (2020) Constantinos Daskalakis, Dylan J Foster, and Noah Golowich. 2020\.  Independent policy gradient methods for competitive reinforcement learning.  _Advances in neural information processing systems_ 33 (2020), 5527–5540.
  * Dong et al. (2019) Kefan Dong, Yuanhao Wang, Xiaoyu Chen, and Liwei Wang. 2019\.  Q-learning with ucb exploration is sample efficient for infinite-horizon mdp.  _arXiv preprint arXiv:1901.09311_ (2019).
  * Gay et al. (1986) DM Gay, NK Karmarkar, and KG Ramakrishnan. 1986.  The Karmarkar Algorithm-Adding Wings to Linear Programming.  _Record - AT &T Bell Laboratories_ 64, 2 (1986), 4–10.
  * Jafarnia-Jahromi et al. (2021) Mehdi Jafarnia-Jahromi, Rahul Jain, and Ashutosh Nayyar. 2021\.  Learning zero-sum stochastic games with posterior sampling.  _arXiv preprint arXiv:2109.03396_ (2021).
  * Jin et al. (2018) Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. 2018.  Is Q-learning provably efficient?  _Advances in neural information processing systems_ 31 (2018).
  * Khachiyan (1979) Leonid G Khachiyan. 1979\.  A polynomial algorithm in linear programming (english translation). In _Soviet Mathematics Doklady_ , Vol. 20. 191–194.
  * Littman (1994) Michael L Littman. 1994\.  Markov games as a framework for multi-agent reinforcement learning.  In _Machine learning proceedings 1994_. Elsevier, 157–163.
  * Liu et al. (2022) Qinghua Liu, Yuanhao Wang, and Chi Jin. 2022.  Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limits.  _arXiv preprint arXiv:2203.06803_ (2022).
  * Mao and Başar (2022) Weichao Mao and Tamer Başar. 2022.  Provably efficient reinforcement learning in decentralized general-sum markov games.  _Dynamic Games and Applications_ (2022), 1–22.
  * Sayin et al. (2021) Muhammed Sayin, Kaiqing Zhang, David Leslie, Tamer Basar, and Asuman Ozdaglar. 2021.  Decentralized Q-learning in zero-sum Markov games.  _Advances in Neural Information Processing Systems_ 34 (2021), 18320–18334.
  * Sayin et al. (2022) Muhammed O Sayin, Francesca Parise, and Asuman Ozdaglar. 2022\.  Fictitious play in zero-sum stochastic games.  _SIAM Journal on Control and Optimization_ 60, 4 (2022), 2095–2114.
  * Shapley (1953) Lloyd S Shapley. 1953\.  Stochastic games.  _Proceedings of the national academy of sciences_ 39, 10 (1953), 1095–1100.
  * Sidford et al. (2020) Aaron Sidford, Mengdi Wang, Lin Yang, and Yinyu Ye. 2020\.  Solving discounted stochastic two-player games with near-optimal time and sample complexity. In _International Conference on Artificial Intelligence and Statistics_. PMLR, 2992–3002.
  * Silver et al. (2018) David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. 2018\.  A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play.  _Science_ 362, 6419 (2018), 1140–1144.
  * Silver et al. (2017) David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. 2017\.  Mastering the game of go without human knowledge.  _nature_ 550, 7676 (2017), 354–359.
  * Tian et al. (2021) Yi Tian, Yuanhao Wang, Tiancheng Yu, and Suvrit Sra. 2021\.  Online learning in unknown markov games. In _International conference on machine learning_. PMLR, 10279–10288.
  * Watkins (1989) Christopher John Cornish Hellaby Watkins. 1989\.  Learning from delayed rewards.  (1989).
  * Wei et al. (2017) Chen-Yu Wei, Yi-Te Hong, and Chi-Jen Lu. 2017.  Online reinforcement learning in stochastic games.  _Advances in Neural Information Processing Systems_ 30 (2017).
  * Wei and Jafarnia-Jahromi (2020) Chen-Yu Wei and Mehdi Jafarnia-Jahromi. 2020.  Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes”, ICML (Int’l Conf. on Machine Learning) 2020.  _Proceedings of Machine Learning Research_ 119 (2020).
  * Wei et al. (2021) Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, and Haipeng Luo. 2021\.  Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive markov games. In _Conference on learning theory_. PMLR, 4259–4299.
  * Xie et al. (2020) Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. 2020\.  Learning zero-sum simultaneous-move markov games using function approximation and correlated equilibrium. In _Conference on learning theory_. PMLR, 3674–3682.

##  Appendix A Appendix

Recall the regret definition and our decomposition of it :

$\displaystyle\text{Reg}(T)$
$\displaystyle=\sum_{t=1}^{T}(J^{*}-r(s_{t},a_{t},b_{t}))$
$\displaystyle=\sum_{t=1}^{T}(J^{*}-(1-\gamma)V^{*}_{\gamma}(s_{t}))$
$\displaystyle\bf{(s1)}$
$\displaystyle+\sum_{t=1}^{T}(V^{*}_{\gamma}(s_{t})-\mathbb{D}_{(\mu_{t},\nu_{t})}[Q^{*}_{\gamma}](s_{t})-\zeta_{t})$
$\displaystyle\bf{(s2)}$
$\displaystyle+\sum_{t=1}^{T}(\mathbb{D}_{(\mu_{t},\nu_{t})}[Q^{*}_{\gamma}](s_{t})-r(s_{t},a_{t},b_{t})-\gamma
V^{*}_{\gamma}(s_{t}))$ $\displaystyle\bf{(s3)}$
$\displaystyle+\sum_{t=1}^{T}\zeta_{t}$ $\displaystyle{\bf(s4)}$

where
$\zeta_{t}=\mathbb{D}_{(\mu_{t},\nu_{t})}[\overline{Q}_{t}^{\downarrow}-Q^{*}_{\gamma}](s_{t})-(\overline{Q}_{t}^{\downarrow}-Q^{*}_{\gamma})(s_{t},a_{t},b_{t})$.

In what follows, we simply write $V^{*}$ and $Q^{*}$ for $V^{*}_{\gamma}$ and
$Q^{*}_{\gamma}$ respectively to lighten notations.

###  A.1. Proof of Lemma 6

This proof is adapted from the proof of Lemma 12 of Wei and Jafarnia-Jahromi
(2020): the proof is done for MDPs in Wei and Jafarnia-Jahromi (2020) and we
adapt it to stochastic games.

We have the following expression for $\overline{Q}_{t+1}(s,a,b)$ :

$\overline{Q}_{t+1}(s,a,b)=\alpha_{\tau}^{0}H+\sum_{i=1}^{\tau}\alpha_{\tau}^{i}\left[r(s,a,b)+\gamma\overline{V}_{t_{i}}^{\downarrow}(s_{t_{i}+1})+\beta_{i}\right].$

By the Bellman equation on $Q^{*}$ and since
$\sum_{i=0}^{\tau}\alpha_{\tau}^{i}=1$, this gives

$\displaystyle(\overline{Q}_{t+1}-Q^{*})(s,a,b)$
$\displaystyle=\alpha_{\tau}^{0}(H-Q^{*}(s,a,b))+\sum_{i=1}^{\tau}\alpha_{\tau}^{i}\left[\gamma\overline{V}_{t_{i}}^{\downarrow}(s_{t_{i}+1})-\gamma
PV^{*}(s,a,b)+\beta_{i}\right].$

By doing $\pm\gamma V^{*}(s_{t_{i}+1})$ in the sum, and with
$\tilde{\beta}_{\tau}=\sum_{i=1}^{\tau}\alpha_{\tau}^{i}\beta_{i}$, we split
the last into

$\displaystyle(\overline{Q}_{t+1}-Q^{*})(s,a,b)$
$\displaystyle=\alpha_{\tau}^{0}(H-Q^{*}(s,a,b))$
$\displaystyle\quad+\sum_{i=1}^{\tau}\gamma\alpha_{\tau}^{i}\left[(\overline{V}_{t_{i}}^{\downarrow}-V^{*})(s_{t_{i}+1})\right]$
$\displaystyle\quad+\sum_{i=1}^{\tau}\gamma\alpha_{\tau}^{i}\left[V^{*}(s_{t_{i}+1})-PV^{*}(s,a,b)\right]$
$\displaystyle\quad+\tilde{\beta}_{\tau}.$ (7)

The first term is bounded between 0 and $\alpha_{\tau}^{0}H$ because
$Q^{*}(s,a,b)$ is bounded between 0 and $1/(1-\gamma)=H$. The third term is a
martingale difference sequence with each term bounded in
$[-\gamma\alpha_{\tau}^{i}sp(V^{*}),\gamma\alpha_{\tau}^{i}sp(V^{*})]$, so by
Azuma-Hoeffding’s inequality, Lemma 2 and inequality (2), with probability at
least $1-\delta/T$, the third term is bounded in absolute value by $\gamma
sp(V^{*})\sqrt{2\sum_{i=1}^{\tau}(\alpha_{\tau}^{i})^{2}\log(2T/\delta)})\leq
2\gamma D\sqrt{\frac{H}{\tau}\log(2T/\delta)}$. Note that when $s,a,b,t$ vary,
$\tau$ only takes its value in $1,2,\ldots,T$ so with a union bound, the
previous bound holds for all $(s,a,b,t)$ with probability $1-\delta$. The
forth term is bounded between $2\gamma D\sqrt{\frac{H}{\tau}\log(2T/\delta)}$
and $4\gamma D\sqrt{\frac{H}{\tau}\log(2T/\delta)}$ by Lemma 2.

By combining all aforementioned upper bounds (sometimes omitting $\gamma<1$),
and since $\overline{Q}_{t+1}^{\downarrow}\leq\overline{Q}_{t+1}$, we have
inequality (4.3.2).

We prove inequalities (3) by induction on $t$. Suppose that for a fixed time
$t$, inequalities (3) hold for all $(s,a,b)$. By equation (A.1), the induction
hypothesis applied on the
$(\overline{V}_{t_{i}}^{\downarrow}-V^{*})(s_{t_{i}+1})$, and aforementioned
lower bounds, for all $(s,a,b)$ we have $(\overline{Q}_{t+1}-Q^{*})(s,a,b)\geq
0$, so $(\overline{Q}_{t+1}^{\downarrow}-Q^{*})(s,a,b)\geq 0$ by induction
since
$\overline{Q}_{t+1}^{\downarrow}(s,a,b)=\min(\overline{Q}_{t}^{\downarrow}(s,a,b),\overline{Q}_{t+1}(s,a,b))$.
Then,

$\displaystyle(\overline{V}_{t+1}^{\downarrow}-V^{*})(s)$
$\displaystyle=\mathbb{D}_{\mu_{t+1},\tilde{\nu}_{t+1}}[\overline{Q}_{t+1}^{\downarrow}](s)-\mathbb{D}_{\mu^{\gamma},\nu^{\gamma}}[Q^{*}](s)$
$\displaystyle\geq\mathbb{D}_{\mu^{\gamma},\tilde{\nu}_{t+1}}[\overline{Q}_{t+1}^{\downarrow}](s)-\mathbb{D}_{\mu^{\gamma},\tilde{\nu}_{t+1}}[Q^{*}](s)$
$\displaystyle\geq 0,$

where $(\mu^{\gamma},\nu^{\gamma})$ is the Nash equilibrium of $Q^{*}(s,.,.)$.
The first inequality is by definition of $(\mu_{t+1},\tilde{\nu}_{t+1})$ as a
Nash equilibrium of $\overline{Q}_{t+1}^{\downarrow}(s,.,.)$.

###  A.2. Proof of Lemma 8

The event $\mathcal{E}_{\delta}^{\prime}$ is the conjunction of two events
that we can analyze separately:

  * •

The sequence
$\mathbb{D}_{(\mu_{t},\nu_{t})}[Q^{*}](s_{t})-Q^{*}(s_{t},a_{t},b_{t})$ is a
martingale difference sequence since $a_{t}$ and $b_{t}$ are drawn from the
policies $\mu_{t}$ and $\nu_{t}$. By assumption of the span, each term is in
an interval of length $1+\gamma sp(V^{*})\leq 1+\gamma D$. Therefore, by
Azuma-Hoeffding, with probability at least $1-\frac{\delta}{2}$, Equation (5)
holds.

  * •

The sequence $PV^{*}(s_{t},a_{t},b_{t})-V^{*}(s_{t+1})$ is a martingale
difference sequence since $s_{t+1}$ is drawn according to
$P(.|s_{t},a_{t},b_{t})$. By assumption on the span, each term is in an
interval of length $sp(V^{*})\leq D$. Therefore by Azuma-Hoeffding, equation
(6) holds with probability at least $1-\frac{\delta}{2}$.

By the union bound, this shows that $\mathcal{E}_{\delta}^{\prime}$ holds with
probability at least $1-\delta$.

###  A.3. Proof of Lemma 9

We split each term of the left-hand side of the main equation of Lemma 9 as
follows:

$\displaystyle\mathbb{D}_{(\mu_{t},\nu_{t})}[Q^{*}](s_{t})-r(s_{t},a_{t},b_{t})-\gamma
V^{*}(s_{t})$
$\displaystyle=(\mathbb{D}_{(\mu_{t},\nu_{t})}[Q^{*}](s_{t})-Q^{*}(s_{t},a_{t},b_{t}))$
$\displaystyle\quad+(Q^{*}(s_{t},a_{t},b_{t})-r(s_{t},a_{t},b_{t})-\gamma
PV^{*}(s_{t},a_{t},b_{t}))$
$\displaystyle\quad+\gamma(PV^{*}(s_{t},a_{t},b_{t})-V^{*}(s_{t+1}))$
$\displaystyle\quad+\gamma(V^{*}(s_{t+1})-V^{*}(s_{t})).$

Now we sum each term :

  * •

Under $\mathcal{E}_{\delta}^{\prime}$,
$\sum_{t=1}^{T}(\mathbb{D}_{(\mu_{t},\nu_{t})}[Q^{*}](s_{t})-Q^{*}(s_{t},a_{t},b_{t}))\leq(1+\gamma
D)\sqrt{2T\log(4/\delta)}$.

  * •

The second term is 0 by Bellman’s optimality equation for the discounted
setting.

  * •

Under $\mathcal{E}_{\delta}^{\prime}$,
$\gamma\sum_{t=1}^{T}(PV^{*}(s_{t},a_{t},b_{t})-V^{*}(s_{t+1}))\leq
D\sqrt{2T\log(4/\delta)}$.

  * •

The last term gives a telescopic sum where
$\gamma(V^{*}(s_{T+1})-V^{*}(s_{1}))\leq D$ remains by inequality (2).

Putting everything together finishes the proof.

###  A.4. Proof of Lemma 10

We simply adapt the proof of Wei and Jafarnia-Jahromi (2020) for the
stochastic game setting. We split the sum of the left-hand side as follows to
change the order of summation.

$\displaystyle\gamma\sum_{t=1}^{T}\sum_{i=1}^{n_{t}}\alpha_{n_{t}}^{i}[(\overline{V}_{t_{i}(s_{t},a_{t},b_{t})}^{\downarrow}-V^{*})(s_{t_{i}(s_{t},a_{t},b_{t})+1})]$
$\displaystyle=\gamma\sum_{t=1}^{T}\sum_{s,a,b}{\bf
1}(s_{t}=s,a_{t}=a,b_{t}=b)\sum_{i=1}^{N_{t+1}(s,a,b)}\alpha_{N_{t+1}(s,a,b)}^{i}[(\overline{V}_{t_{i}(s,a,b)}^{\downarrow}-V^{*})(s_{t_{i}(s,a,b)+1})]$
$\displaystyle=\gamma\sum_{s,a,b}\sum_{j=1}^{N_{T+1}(s,a,b)}\sum_{i=1}^{j}\alpha_{j}^{i}[(\overline{V}_{t_{i}(s,a,b)}^{\downarrow}-V^{*})(s_{t_{i}(s,a,b)+1})]$
$\displaystyle=\gamma\sum_{s,a,b}\sum_{i=1}^{N_{T+1}(s,a,b)}\sum_{j=i}^{N_{T+1}(s,a,b)}\alpha_{j}^{i}[(\overline{V}_{t_{i}(s,a,b)}^{\downarrow}-V^{*})(s_{t_{i}(s,a,b)+1})]$
$\displaystyle=\gamma\sum_{s,a,b}\sum_{i=1}^{N_{T+1}(s,a,b)}[(\overline{V}_{t_{i}(s,a,b)}^{\downarrow}-V^{*})(s_{t_{i}(s,a,b)+1})]\left(\sum_{j=i}^{N_{T+1}(s,a,b)}\alpha_{j}^{i}\right)$
$\displaystyle\leq\gamma\sum_{s,a,b}\sum_{i=1}^{N_{T+1}(s,a,b)}[(\overline{V}_{t_{i}(s,a,b)}^{\downarrow}-V^{*})(s_{t_{i}(s,a,b)+1})]\left(1+\frac{1}{H}\right),$

where the last inequality is because by Lemma 2 and the fact that
$[(\overline{V}_{t_{i}(s,a,b)}]^{\downarrow}-V^{*})(s_{t_{i}(s,a,b)+1})]\geq
0$ under $\mathcal{E}_{\delta}$ (equation (3)).

As $\gamma\left(1+\frac{1}{H}\right)\leq 1$, this is smaller than:

$\displaystyle\leq\sum_{t=1}^{T}[(\overline{V}_{t}^{\downarrow}-V^{*})(s_{t+1})]$
$\displaystyle=\sum_{t=2}^{T+1}[(\overline{V}_{t}^{\downarrow}-V^{*})(s_{t})]+\sum_{t=1}^{T}[(\overline{V}_{t}^{\downarrow}-\overline{V}_{t+1}^{\downarrow}](s_{t+1})$
$\displaystyle\leq\sum_{t=2}^{T+1}[(\overline{V}_{t}^{\downarrow}-V^{*})(s_{t})]+SH,$

where the last inequality is because $\overline{V}_{t}^{\downarrow}$ decreases
of at most $H$ per state $s$.

###  A.5. Details for the proof of Theorem 3

$\zeta_{t}$ is a martingale difference sequence which is bounded in
$[-2H,2H]$, so by Azuma-Hoeffding,

$\left|\sum_{t=1}^{T}\zeta_{t}\right|\leq 2H\sqrt{2T\log(2/\delta)}$

with probability at least $1-\delta$. By Lemma 6 and Lemma 8,
$\mathcal{E}_{\delta}$, $\mathcal{E}_{\delta}^{\prime}$ and this last
inequality hold together with probability at least $1-3\delta$. Therefore, by
Lemmas 5, 7 and 9, with probability at least $1-3\delta$ the regret is upper
bounded by

$\displaystyle\text{Reg}(T)$ $\displaystyle\leq D\frac{T}{H}$
$\displaystyle+2H\sqrt{2T\log(2/\delta)}$
$\displaystyle+12D\sqrt{SABHT\log(2T/\delta)}$
$\displaystyle+C\left(SABH+D\sqrt{T\log(4/\delta)}\right),$

with $C=\max(c,c^{\prime})$.

###  A.6. Details for the proof of Theorem 4

For any $\delta\in(0,1)$, let
$\mathcal{E}_{\delta}^{\prime\prime}=\mathcal{E}_{\delta}\cap\mathcal{E}_{\delta}^{\prime}$.
By Lemma 6 and Lemma 8, $\mathcal{E}_{\delta}^{\prime\prime}$ holds with
probability at least $1-2\delta$.

The following inequality holds :

$\mathbb{E}\left[{\bf
1}(\mathcal{E}_{\delta}^{\prime\prime})\sum_{t=1}^{T}\zeta_{t}\right]\leq
4HT\delta.$ (8)

Indeed, we write

$\zeta_{t}={\bf 1}(\mathcal{E}_{\delta}^{\prime\prime})\zeta_{t}+{\bf
1}(\neg\mathcal{E}_{\delta}^{\prime\prime})\zeta_{t},$

where $\neg\mathcal{E}_{\delta}^{\prime\prime}$ is the complementary event of
$\mathcal{E}_{\delta}^{\prime\prime}$. For any $t$, $\zeta_{t}$ is bounded by
$2H$ in absolute value, therefore

$-\mathbb{E}\left[{\bf
1}(\neg\mathcal{E}_{\delta}^{\prime\prime})\sum_{t=1}^{T}\zeta_{t}\right]\leq
2HT\mathbb{E}\left[{\bf 1}(\neg\mathcal{E}_{\delta}^{\prime\prime})\right]\leq
4HT\delta.$

Moreover, if $\mathcal{F}_{t}$ is the $\sigma$-algebra generated by all random
variables up to $s_{t}$, since $\zeta_{t}$ is a martingale difference sequence
for the filtration $\\{\mathcal{F}_{t}\\}_{t}$, we have

$\mathbb{E}\left[\sum_{t=1}^{T}\zeta_{t}\right]=\mathbb{E}\left[\sum_{t=1}^{T}\mathbb{E}[\zeta_{t}|\mathcal{F}_{t}]\right]=0$

which proves inequality (8).

Finally the expectation of the regret is written as follows for some
$\delta\in(0,1)$ that we smartly choose later :

$\mathbb{E}[\text{Reg}(T)]=\mathbb{E}[{\bf
1}(\mathcal{E}_{\delta}^{\prime\prime})\text{Reg}(T)]+\mathbb{E}[{\bf
1}(\neg\mathcal{E}_{\delta}^{\prime\prime})\text{Reg}(T)].$ (9)

By Lemma 5, Lemma 7, Lemma 9, and equation (8), the first term is upper
bounded by

$\displaystyle\mathbb{E}\left[{\bf
1}(\mathcal{E}_{\delta}^{\prime\prime})\text{Reg}(T)\right]$
$\displaystyle\leq D\frac{T}{H}+12D\sqrt{SABHT\log(2T/\delta)}$
$\displaystyle+\underbrace{\mathbb{E}\left[{\bf
1}(\mathcal{E}_{\delta}^{\prime\prime})\sum_{t=1}^{T}\zeta_{t}\right]}_{\leq
4HT\delta}+C\left(SABH+D\sqrt{T\log(4/\delta)}\right),$

where $C=\max(c,c^{\prime})$.

Since the regret is clearly upper bounded by $T$, the second term of (9) is
upper bounded in expectation by

$\mathbb{E}\left[{\bf
1}(\neg\mathcal{E}_{\delta}^{\prime\prime})\text{Reg}(T)\right]\leq 2T\delta.$

By setting $\delta=\frac{1}{T}$, this gives the desired regret bound.

###  A.7. Discussion for bounding $\zeta_{t}$

The factor $H\sqrt{T}$ that appears in Theorem 3 comes from the fact that we
were not able to bound the terms in ${\bf(s4)}$ with a better bound than $H$.
Indeed, consider a repeated version of Rock-Paper-Scissors ($S=1$) and suppose
the opponent always plays Rock. The optimistic estimations
$\overline{Q}_{t}^{\downarrow}$ corresponding to the not-played opponent
actions are never updated and remain equal to $H$, which leads to keep the
estimator $\overline{V}_{t}^{\downarrow}$ equals to $H$. Therefore
$\overline{Q}_{t}^{\downarrow}$ remains of order $H$ for all state-actions
tuple whereas it is not the case for $Q^{*}$. Therefore it is not clear that
the term
$\zeta_{t}=(\overline{Q}_{t}^{\downarrow}-Q^{*})(s_{t},a_{t},b_{t})-\mathbb{D}_{(\mu_{t},\nu_{t})}[(\overline{Q}_{t}^{\downarrow}-Q^{*})](s_{t})$
can be efficiently bounded in order to use Azuma-Hoeffding’s inequality on
$\sum_{t=1}^{T}\zeta_{t}$.


Wikipedia has high-quality articles on a variety of topics and has been used in diverse research areas.
In this study, a method is presented for using Wikipedia's editor information to build recommender systems in various domains that outperform content-based systems.

Keywords: recommendation, collaborative filtering, Wikipedia, editor information, user preference

§ INTRODUCTION

Wikipedia is an online encyclopedia that can be edited by anyone, and due to the ease of editing and the large number of editors, there are high-quality articles on a variety of topics (hereafter “entities”). Information obtained from Wikipedia has thus been used in various research fields. Among them, entity similarity estimation is a hot research topic that has many applications such as recommendation systems [Musto et al., 2016] and search engines [Gabrilovich and Markovitch, 2007]. To estimate similarities between entities, it is necessary to extract entity features. A commonly used source for feature extraction is Wikipedia's content information such as text abstracts and hyperlinks (see Figure <ref>).

Given that Wikipedia is an encyclopedia, one of its basic policies is that content must be written from a “neutral point of view”, which means that articles are edited by carefully analyzing reliable information sources and eliminating as much editorial bias as possible[<https://en.wikipedia.org/wiki/Wikipedia:Neutral_point_of_view>]. Unlike critiques and reviews, Wikipedia's content is free of personal opinions and impressions. In other words, Wikipedia's content information is limited to superficial attribute information about entities, and is unlikely to reflect the editor's personal opinions and preferences. Therefore, a drawback of conventional content-based methods is that it is difficult to capture complex similarities between entities inherent in human preferences.

An alternative to content-based methods is collaborative filtering, which is based on user preference information and enables the capture of the complex similarities inherent among entities.
It has been developed mainly in the field of recommendation research.
Since building a recommender system on the basis of collaborative filtering requires user profile information such as purchase history, the domains in which it can be applied are limited.

In this paper, We have developed a new collaborative filtering method for estimating similarities between entities in Wikipedia. As shown in Figure <ref>, Wikipedia keeps a history record of who edited each article, and the proposed method utilizes that information on the editors of articles. Since editors generally edit articles on topics in which they are interested in, we can assume from the viewpoint of collaborative filtering that entities corresponding to articles edited by the same editor are similar to each other. The proposed method is thus be able to estimate complex similarities between entities that are difficult to capture with content-based methods.

We experimentally investigated the effectiveness of the proposed method on three recommendation datasets for movies, music artists, and books. The results show that the proposed method has higher recommendation accuracy than content-based methods using text abstracts, hyperlinks, or categories[This paper is an English version of the Japan domestic conference paper [Takeuchi and Hayashi, 2022].].

§ SIMILARITY ESTIMATION

Given $N$ Wikipedia articles $(D_1,D_2,\cdots,D_N)$, $D_i$ can be represented as a feature vector $[f_{i1},f_{i2},\cdots,f_{iM}]\transpose$ in which $f_{ij}=1$ if a feature $w_j$ appears in a Wikipedia article $D_i$ and $f_{ij}=0$ if not[For $f_{ij}$, we can also consider the number of times the feature $w_j$ appears in the Wikipedia article $D_i$.].
We define a Wikipedia article matrix:

\[
\mat{F}=\left( \begin{array}{cccc}
f_{11} & f_{12} & \cdots & f_{1M}\\
f_{21} & f_{22} & \cdots & f_{2M} \\
\vdots & \vdots & \ddots & \vdots \\
f_{N1} & f_{N2} & \cdots & f_{NM}
\end{array} \right) \in \{0,1\}^{N\times M}.
\]

We can use word $n$-grams, hyperlinks, or editors as features.
To estimate a similarity matrix $\mat{B}\in\Rset^{N\times N}$ with EASE, we formulate the estimation problem as a linear regression formula:

\begin{eqnarray}
\label{eq:ae}
&&\widehat{\mat{B}}=\argmin_{\mat{B}}\Bigl\{||\mat{F}-\mat{F}\mat{B}||_{F}^{2}+\lambda||\mat{B}||_{F}^{2}\Bigr\} \\\nonumber
&&\text{s.t.}\ \ \ \diag{(\mat{B})}=\mat{0}.\nonumber
\end{eqnarray}

The objective is to obtain a weight (similarity) matrix $\mat{B}$ that reconstructs the Wikipedia article matrix $\mat{F}$ from $\mat{F}\mat{B}$ by minimizing the squared loss with L2 regularization.
However, when $\mat{B}=\mat{I}$, the minimization of Eq.(<ref>) can be achieved in an obvious way, and so $\diag{(\mat{B})}=\mat{0}$ is imposed as a constraint condition.
This constraint means that all diagonal components of $\mat{B}$ must be zero.

The equation (<ref>) is attributed to the problem of minimizing

\[
\]

by Lagrange's undetermined multiplier method.
Where $\boldsymbol{\alpha}$ denotes the vector of Lagrange multipliers.
The solution has the following closed form,

\begin{equation}
\label{eq:closed}
\widehat{\mat{B}}=\mat{I}-\mat{P}\mtrx{(\mat{1}\oslash\diag{(\mat{P})})}
\end{equation}

$\mat{P}=(\mat{F}\transpose\mat{F}+\lambda\mat{I})^{-1}$,and each element can be estimated as

\begin{equation}
\label{eq:solution}
\widehat{\mat{B}}_{jk}=
\left\{
\begin{array}{ll}
0 & (j=k)\\
-\frac{\mat{P}_{jk}}{\mat{P}_{kk}} & (j\neq k)
\end{array}
\right.
\end{equation}

The $\widehat{\mat{B}}$ can be used as a similarity matrix between Wikipedia articles.
We use the EASE [Steck, 2019] model for estimating similarity between entities (i.e. Wikipedia articles).
Given $N$ Wikipedia articles $(D_1,D_2,\cdots,D_N)$, $D_i$ can be represented as a feature vector $[f_{i1},f_{i2},\cdots,f_{iM}]\transpose$ in which $f_{ij}=1$ if a feature $w_j$ appears in a Wikipedia article $D_i$ and $f_{ij}=0$ if not[For $f_{ij}$, we can also consider the number of times the feature $w_j$ appears in the Wikipedia article $D_i$.].
We define a Wikipedia article matrix:

\[
\mat{F}=\left( \begin{array}{cccc}
f_{11} & f_{12} & \cdots & f_{1M}\\
f_{21} & f_{22} & \cdots & f_{2M} \\
\vdots & \vdots & \ddots & \vdots \\
f_{N1} & f_{N2} & \cdots & f_{NM}
\end{array} \right) \in \{0,1\}^{N\times M}.
\]

We can use word $n$-grams, hyperlinks, or editors as features.
To estimate a similarity matrix $\mat{B}\in\Rset^{N\times N}$ with EASE, we formulate the estimation problem as a inear regression formula:

\begin{eqnarray}
\label{eq:ae}
&&\widehat{\mat{B}}=\argmin_{\mat{B}}\Bigl\{||\mat{F}-\mat{F}\mat{B}||_{F}^{2}+\lambda||\mat{B}||_{F}^{2}\Bigr\} \\\nonumber
&&\text{s.t.}\ \ \ \diag{(\mat{B})}=\mat{0}.\nonumber
\end{eqnarray}

The objective is to obtain a weight (similarity) matrix $\mat{B}$ that reconstructs the Wikipedia article matrix $\mat{F}$ from $\mat{F}\mat{B}$ by minimizing the squared loss with L2 regularization.
However, when $\mat{B}=\mat{I}$, the minimization of Eq.(<ref>) can be achieved in an obvious way, and so $\diag{(\mat{B})}=\mat{0}$ is imposed as a constraint condition.
This constraint means that all diagonal components of $\mat{B}$ must be zero.

§ EXPERIMENTS

§.§ Recommendation Datasets

We used three recommendation datasets for evaluation: (1) MovieLens-20M (ML-20M)[<https://grouplens.org/datasets/movielens/20m/>], (2) Last.fm hetrec-2011 (Last.fm) [Cantador et al., 2011]
and (3) LibraryThing (LT)[<https://github.com/sisinflab/LinkedDatasets>].

* MovieLens-20M (ML-20M)[<https://grouplens.org/datasets/movielens/20m/>]

* Last.fm hetrec-2011 (Last.fm) [Cantador et al., 2011]

* LibraryThing (LT)[<https://github.com/sisinflab/LinkedDatasets>].

In our experiments, we considered an implicit feedback setting, so users
did not need to express
their tastes explicitly.
In this setting, the user's preference scores were treated as binary values.
From the Wikipedia articles that correspond to three types of entities (movies, music artists and books) of the three datasets, we extracted information about the editors of the aritcles in English Wikipedia, the editors of the aricles in multilingual Wikipedia, the English text abstracts, the hyperlinks and the categories. Table <ref> summarizes the dataset statistics.

§.§ Recommendation Evaluation

We evaluated our proposed method on the recommendation task. In the following, we describe the procedure of the recommendation task.

*Evaluation Procedure
To evaluate the recommender systems, we split each recommendation dataset into history and answer data.
The history data was “past preference” profile information of users.
The answer data is “expected preference” profile information for the same users as the history data, but the entities preferred by a user in the answer data were completely different from those in the history data.
For each recommendation dataset, the users were randomly divided into five groups, and for each group of users, the preference profiles were roughly divided into 80% (history data) and 20% (answer data).
The answer data were used for evaluating recommendations predicted by a recommender system.

We evaluated recommendation performance using two metrics, Recall@$R$ and nDCG@$R$, where $R$ is the number of recommended entities.
Figure <ref> shows the results.
We reported the mean and standard deviation of each metric for the five split data.
Compared with using content-based information, using editor information resulted in better performance for all the datasets.

§ CONTRIBUTIONS AND FINDINGS

We summarize our contributions as follows:

* We presented a new method for using Wikipedia editor information to estimate entity (i.e. article) similarity.

* Our method
largely outperforms conventional content-based ones on several recommendation datasets.

[Cantador et al., 2011]
Iván Cantador, Peter Brusilovsky, and Tsvi Kuflik.
Second workshop on information heterogeneity and fusion in
recommender systems (hetrec2011).
In Proc. of RecSys Conference, pages 387–388, 2011.

[Gabrilovich and Markovitch, 2007]
Evgeniy Gabrilovich and Shaul Markovitch.
Computing semantic relatedness using wikipedia-based explicit
semantic analysis.
In Proc. of IJCAI, pages 1606–1611, 2007.

[Musto et al., 2016]
Cataldo Musto, Giovanni Semeraro, Marco de Gemmis, and Pasquale Lops.
Learning word embeddings from wikipedia for content-based recommender
In Proc. of ECIR, pages 729–734. Springer, 2016.

[Steck, 2019]
Harald Steck.
Embarrassingly shallow autoencoders for sparse data.
In Proc. of WWW Conference, pages 3251–3257, 2019.

[Takeuchi and Hayashi, 2022]
Koki Takeuchi and Katsuhiko Hayashi.
Entity similarity estimation by collaborative filtering with
wikipedia editor information.
Proceedings of Web Intelligence and Interaction, 18:0
43–50, 2022.