Decentralized Q-learning in Zero-sum Markov Games
Authors: Muhammed O. Sayin
Kaiqing Zhang
David S. Leslie
Tamer Basar
Asuman E. Ozdaglar
Venue: NeurIPS 2021 Poster (2021)
Keywords: multi-agent reinforcement learning
decentralized learning
Markov games
two-timescale stochastic approximation

Abstract: We study multi-agent  reinforcement learning (MARL) in infinite-horizon discounted zero-sum Markov games. We focus on the practical but  challenging setting of decentralized MARL, where agents make decisions without coordination by a centralized controller, but only based on their own payoffs and local actions executed. The agents need not observe the opponent's actions or payoffs, possibly being even  oblivious to the presence of the opponent, nor be aware of the zero-sum structure of the underlying game, a setting also referred to as radically uncoupled in the literature of learning in games. In this paper, we develop a radically uncoupled Q-learning dynamics that is both rational and convergent: the learning dynamics converges to the best response to the opponent's strategy when the opponent follows an asymptotically stationary strategy;  when both agents adopt the learning dynamics, they converge to the Nash equilibrium of the game. The key challenge in this decentralized setting is the non-stationarity of the environment from an agent's perspective, since both her own payoffs and the system evolution depend on the actions of other agents, and each agent adapts her policies simultaneously and independently. To address this issue, we develop a two-timescale learning dynamics where each agent updates her local Q-function and value function estimates concurrently, with the latter happening at a slower timescale.

Decentralized Q-Learning in Zero-sum Markov Games
Muhammed O. Sayin' Bilkent University sayinβee. bilkent. edu. tr
Kaiqing Zhang MIT
kaiqing@mit. edu
David S. Leslie
Tamer Başar UIUC
Asuman Ozdaglar MIT asuman@mit edu
Lancaster University
d. www.eeee@lancaster.com ac.uk
Dasar10illimois.ed
Abstract
We study multi-agent reinforcement learning (MARL) in infinite-horizon dis- counted zero-sum Markov games. We focus the practical but challenging setting decentralized MARL, where agents make decisions without coordination by centralized controller, but only based on their executed. The agents need not observe the opponent's actions or payoffs,, possibly of the zero-sum
payoffs and local actions
being even oblivious to the presence of the opponent, nor be structure of the underlying game, a setting also referred to as radically uncoupled the literature of learning in games. In this paper, develop radically uncoupled Q-learning dynamics that is both rational and convergent: the learning dynamics converges to the best response the opponent's 's strategy when the opponent fol- lows an asymptotically stationary strategy; when both agents adopt the learning dynamics, they converge to the Nash equilibrium of the game. The key challenge in this decentralized setting is the non-stati statiitiion of the environment from an agent's perspective, since both her own payoffs and the system evolution depend the actions of other agents, and each agent adapts her policies simultaneously and independently. To address this issue, we develop two-timescale learning dy- namics where each agent updates her local QQ-function and value function estimates concurrently, with the latter happening at slower timescale.
Introduction
Reinforcement learning (RL) has achieved tremendous successes recently in wide range of applica- tions, including playing the game of Go [Silver et al. 2017]. playing video games (e.g., Atari [Mnih]
2015 Kober al. 2013]. and autonomous driving (Shalev-Shwartz et al. 2016 Sallab el al. 2017]. Most of these applications
al. 2015) and Starcraft [Vinyals et al. 2019 ) robotics Lillicrap
involve multiple decision-makers, where the agents rewards and the evolution of the system are affected by the joint behaviors of all agents. This setting naturally leads to the problem of multi-agent RL (MARL). In fact, MARL arguably one key ingredient of large-scale and reliable autonomy, and is significantly more challenging to analyze than single-agent RI. There has been a surging interest. recently in both a deeper theoretical and empirical understanding of MARL; see comprehensive overviews on this topic in Busoniu et al. (2008. Zhang et al. [202]] |ermandez--Leal et al. [2019].
The pioneering work that initiated the sub-area of MARL, where the model of Markov/stochastic games SShaple 1953 has been considered as framework, is Littman [994]. Since then, there
Equal contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

has been a plethora of works on MARL in Markov games; see detailed literature review in the supplementary material. These algorithms can be broadly categorized into two types: central- izeal/coordinated and decentrulizzd/inllpenie exists a central controller for the agents, who can access the agents joint actions and local observations. With full awareness of the game setup, the central controller coordinates the agents to optimize their own policies, and aims to compute an equilibrium. This centralized paradigm is typically suitable for the scenarios when a simulator of the game is accessible [Silver et al. 2017 Vinyals al. 2017].
ones. For the former type, it is assumed that there
Most existing MARL algorithms in Markov games have focused on this paradıgm.
Nevertheless, in many practical multi- learning scenarios, e.g., multi-robot control Wang and de Silva 2008 urban traffic control (Kuyer et al. [2008]. as well as economics with rational decision- makers Fudenberg and Levine, 1998,, J, agents make decentralized decisions without a coordinator. Specifically, agents make updates independently with only local observations of their own payoff' and action histories, usually in myopic fashion. Besides its ubiquity in practice, this decentralized paradigm also has the advantage of being scalable, as each agent only cares about her own policy and/or value functions, and the algorithms complexity do not suffer from the exponential dependence on the number of agents.
Unfortunately, establishing provably convergent decentralized MARL algorithms is well-known to be challenging; see the non-convergent cases (even in the fully cooperative setting) in Tan [1993).
Boutilier [996). Claus and Boutilier [1998]. and see Matignon et al.] [2012] for more empirical evidences. The key challenge is the nontstaaion of the environment from each agent's perspective since all agents are adapting their policies simultaneously and independently. In other words, the opponent is not playing according to a stationary strategy. This non-stationarity issue is in fact one of the core issues in (decentralized) MARL [Busoniu et al. 2008 Hernandez-LLea et al. (017].
Studying when self-interested players can converge to an equilibrium through non-equilibrium adaptation is core question in the related literature of learning in games [Fudenberg and Levine| 1998 2009]. For example, simple and stylized learning dynamics, such as fictitious play, are shown to converge to an equilibrium in certain but important classes of games, e.g., zero-sum [Robinson] [951 Harris 1998) and common- -interettt [Monderer and Shapley, [996], in repeated play of the same game. However, we cannot generalize these results to decentralized MARL in Markov games (also known as stochastic games, introduced by [Shapley] [953). ), because agents strategies affect not only the immediate reward, as in the repeated play of the same strategic-form game, but also the rewards that will be received in the future. Therefore, the configuration of the induced stage games are not necessarily stationary in Markov games.
Contributions. In this paper, we present a provably convergent decentralized MARL learning dynamic for zero-sum discounted Markov games over an infinite horizon with minimal information available agents. Particularly, each agent only has access to her immediate reward and the current state with perfect recall. They do not have access to the immediate reward the opponent receives. They do not know model of their reward functions and the underlying state transitions probabilities. They are oblivious to the zero-sum structure of the underlying game. They also do not observe the opponent's actions. Indeed, they may even be oblivious to the presence of other agents. Learning dynamics with such minimal information is also referred to as being radically uncoupled or value-based in the literature of learning games [Foster and Young 2006 Lestie and Collins 2005).
To address the non-stationarity issue, we advocate a two-timescale adaptation of the individual Q-learning, introduced by Leslie and Collins [2055] and originating in Fuudebbrrg and Levine [1998]. Particularly, each agent infers the opponent's 's strategy indirectly through an estimate of the local Q-function (a function of the opponent's 's strategy) and simultaneously forms an estimate of the value function to infer the continuation payoff. The slow update of the value function estimate is natural since agents tend to change their strategies faster than their estimates (as observed in the evolutionary game theory literature, e.g., Ely and Yilankaya (2001), Sandholm (200T), but this also helps weakening the dependence between the configuration of the stage games (specifically the global Q- ffunnctinss) and the strategies. We show the almost sure convergence of the learning dynamics to the Nash equilibrium using the stochastic approximation theory, by developing a novel Lyapunov function and identifying the sufficient conditions precisely later in $ Our techniques
"To emphasize the difference from many existing MARL algorithms that focus on the computation of Nash equilibrium, we refer to our update rule as learning dynamics, following the literature of learning in games.
2

---

toward addressing these challenges might be of independent interest. We also verify the convergence of the learning dynamics via numerical examples.
To the best of our knowledge, our learning dynamics appears to be one of the first provably convergent decentralized MARL learning dynamics for Markov games that enjoy all the appealing properties below addressing an important open question in the literature [Pérolat et al. 2018 Daskalakis et al. 2020 In particular, our learning dynamics-
requires only minimal information available to the agents, i.e., a radically uncoupled
learning dynamic, unlike many other MARL algorithm, e.g.. Pérolat et al. [2013]. (idford et al.
[2019), Leslie et al. 22000], Sayin et al.
2020]. Bai and Jin [2020], Xie et al. 2020). Zhang
et al. 20220. Liu et al. [2020]. Shah et al. [2200]
requires no coordination or communication between agents during learning. For example,
agents always play the (smoothed) best response consistent with their self-interested decision- making, contrary to being coordinated to keep playing the same strategy within certain time
intervals in Arslan and Yuksel (2017) and Wei al. [202]]:
requires no asymmetric update rules and/or stepsizes for the agents unlike existing literature
Vrieze and Tijs 1982 (Bowling and Veloso 2002
[Leslie and Collins 20033, (Daskalakis
et al. 2020]. Zhao et al. 202 Guo et al. 2021]. Such an asymmetry implies implicit
coordmation between agents decide who follows which update rule or who chooses which
stepsize (and correspondingly who reacts fast or slow). Daskalakis et al. (2020) refers to each agent playing symmetric role in learning as strongly independent learning. is both rational and convergent, a desired property for MARL (independent of whether it is centralized or decentralized), e.g., see see Boowling and Veloso (200T), [Busoniu al. (2008). A MARL algorithm is rational if each agent can converge to best-response, when the opponent plays an (asypptotically) stationary strategy; and it can converge only to an equilibrium when all agents adopt it.
detailed literature review is deferred to the supplementary material due space limitations. Of particular relevance are two recent works Tian et (2020) and Wei et al. [2021] studied decentralized setting similar ours. Tian al. (2020) focused on the exploration aspect for fiite-horizon settings, and focused on minimizing a weak notion of regret without providing convergence guarantees under self-play Wei et al. 2021 presented an optimistic variant of the gradient descent-ascent method that shares similar desired properties with our learning dynamics, with strong guarantee of last-iterate convergence rates. However, the algorithm is delicately designed and different from the common value/policy- RL update rules, e.g., Q-learning, as in our work. Moreover, to characterize finite-time convergence, the model-free setting, the agents need to coordinate to interact multiple steps at each iteration of the algorithm, while our learning dynamics is coordination-fres with natural update rules. These two works can thus be viewed as orthogonal to ours. After submitting our paper, became aware of concurrent and independent work Guo et al. [2021), which also developed decentralized algorithm for zero-sum Markov games with function approximation and finite- ssmmle guarantees. In contrast to our learning dynamics, the algorithm requires double-loop update rule, and thus is asymmetric and requires coordination between agents. The assumptions and technical novelties in both works are also fundamentally different. See $A.2 for a detailed comparison.
Organization. The rest of the paper is organized as follows. We describe Markov games and our decentralized Q-learning dynamics in $2 In $ we present the assumptions and the convergence results. In $ we provide numerical examples. We conclude the paper with some remarks $5) The supplementary material includes a detailed literature review and the proofs of technical results.
Notations. Superscript denotes player identity. We represent the entries of vectors q (or matrices Q) via qiं (or jl). For two vectors x and the inner product is denoted by æ y = x" y. For finite set A, we denote the probability simplex over A by ((A).
'Note that the same update rule with different stepsize and bonus choices and a certified policy technique. however, can return non- Markovian approximate Nash equilibrium policy pair in the self- play setting: see Bai al. 2020 for more details.
3

---

2 Decentralized Q-learning in Zero-sum Markov Games
This section presents a decentralized Q-learning dynamics that does not need access to the opponent's actions and does not need to know the zero-sum structure of the underlying Markov game. To this end, we first start by providing formal description of Markov games.
Consider two players interacting with each other in a common dynamic environment, with totally conflicting objectíves. The setting can be described by two-player zero-sum Markov game, charac- (1.2) S 7), where S denotes the set of states, A;, denotes the action set of player i at state E S, and y E [0. 1) denotes the discount factor. At each interaction round, player i receives a reward according to the function ri A! x A? - RR. Since is a zero-sum game, we have r. (a', a²) + rr2 a²) 0 for each joint action pair (a .a²) E A,, 4 x A3. We denote the transition probability from state s to state given a joint action profile (a), (2) by p(s'ls ()s ag. a²). Let us denote the stationary (Markov) strategy of player i by x² == { E A(A)) SES. We define the expected utility player under the strategy profile (iT) m²) as the expected discounted
terized by a tuple (S, {A²) ( (1.)) {r::
sum of the reward he collects over an infinite horizon
D Σ T at)
U' x²) (ag be
where {50 ~ Po, 8 ~ p(-|sp at. ag),k 2 0} is a stochastic process describing the evolution of the state over time and Po E (SS) is the initial state distribution. The expectation is taken with respect to the initial state, randomness induced by state transitions and mixed strategies.
A strategy profile (m.) m²) is e-Nash equilibrium of the Markov game with 2 0 provided that
20 + - E, Vi U (T?,, U2 ( m²) - E, Va²
(2a)
(2b)
A Nash equilibrium is e-Nash equilibrium with & 0. It is known that such Nash equilibrium exists for discounted Markov games Fiin 1964 Filar and Vrieze 2012).
Given strategy profile = (a 2), we define the value function of player i by
rr(aat rri(at a²) (2) + Σ o E=(())p661ssdddd)) S'ES
(s) E
(at mat bear2
Vs.
Note that (²( = E of (5o) s8 po}. We also define the Q-function that represents the value obtained for given state and joint action pair as
Qi ,a²) = ra(a'a (alaaaaa? a²) + r Σ (()0(11))))))) V(s,a',a²),
(4)
e'ES
as well as the local Q-funciion for player i d (8, a') == E, i (s,,t, V(s,a'),
(5)
where i denotes the opponent of player
By the one-stage deviation principle, we can interpret the interaction between the players at each stage as they are playing an auxiliary stage game, in which the payoff functions are equal to the Q-functions, e.g., see Shapley [953]. However, the Q-functions, and correspondingly the payoff functions in these auxiliary stage games, change with evolving strategies of the players. Therefore, the plethora of existing results for repeated play of the same strategic-form game (e.g., see the review Fudenberg and Levine (2009) do not generalize here. To address this challenge, we next introduce our decentralized Q-learning dynamics.
2.1 Decentralized Q-learning Dynamies
In our decentralized Q-learning dynamics, minimal information is available to players. In other words, they only have access the immediate reward received and current state visited with perfect recall. They do not observe the actions taken by the opponent. Correspondingly, they cannot form

---

Opponent's mixed strategy
Local Q-function
Global Q-function
Opponent's local action
Local action
X
]x
Player's mixed strategy
Local
Q-function
Immeddate
Discount factor
State
Value
reward
transition
function
probabilities
Figure 1: figurative illustration of the dependence between local Q-function, global Q-function opponent's s mixed strategy and the value function. From an agents' perspective, the local Q-function gives the expected values associated with local actions. Here, agents will infer the opponent's 's strategy over the local Q- 2-fuuction and estimate the value function slower timescale to ensure that the implicit global Q- Q-function is relatively stationary compared to the opponent's 's strategy.
belief about the opponent's strategy based the empirical play in fictitious play (Fudenberg and Levine 1998) or its variant for stochastic games [Sayin et al. 2020). Instead, the players can look for inferring the opponent's 's strategy, e.g., by estimating the local Q Q-function since the local Q-function contains information about the opponent's strategy, as illustrated in Figure [ As seen in Figure D however, the local Q-function also depends the global Q-function while the global Q-function is not necessarily stationary since it depends on the value function, and therefore, depends on the players' evolving strategies. An estimate of the global Q function which is slowly evolving would make it relatively stationary compared to the strategies. However, the players cannot estimate the global Q-function directly since they do not have access the opponent's actions. Instead, they estimate the value function while updating it at slower timescale. The slow update of the value function estimate makes the implicit global Q-function relatively stationary compared to the strategies. Therefore, the players can use the local Q funcction estimate to infer the opponent's 's strategy.
Note that the local Q-function estimate for different actions would get updated asynchronously via the classical Q-learning algorithm since they would be updated only when the associated action is taken, however, the actions likely to be taken at different frequencies. Instead, here the players update the local Q-function estimate via a learning dynamics inspired from the individual Q-lcarning. The individual Q-lcarning, presented by Leslie and Collins [2005] and originating in Fudenberg and Levine [1988] is based on the Q-learning with soft-max exploration while the step sizes are normalized with the probability of the actions taken. This normalization ensures that the estimates for every action get updated at the same learning rate in the expectation. We elaborate further on this after we introduce the precise update of the local Q-function estimate later in this section.
Each player i keeps track of {Ā J and ( estimating, respectively, the local Q-function and the value function. Player i updates { at faster timescale than { Jees. Players also count the number of times each state is visited (until the current stage), denoted by #s.
We assume players know that the reward function takes values in [R, R] for some R E (0, oo), i.., Ir aa²) < R for all (1,8,a) a², a,)).. Therefore, player è knows that his local Q-function llg,, (s.-s)))l S R/(1 7) =: D and the value function [u], (s)] S D for any strategy profile æ and s E S. Correspondingly, the players initiate these estimates arbitrarily such that |lo,,ollo S and
log < D, for all
Let 3ę denote the current state at stage k. Player takes his action of E A drawn from the
smoothed best response Br (4 k: T E A(A)), which depends a temperature parameter
T# 0 associated with #s. We define
Br( argmax {u:g+Tu MEA(AS)
(6)
5

---

Table 1: Decentralized Q-learning dynamics in Markov games
Require:
Keep track of (L 6 #sss
1: Observe the current state 8k-
2: Update the entry of the local Q-function estimate for the previous state Sk-1 and local action
d according to
& 9on-1,k-1laf 110 ai-1 (rk-1 + y0 - (
where - min {1,
awaa- and 1a 1 for all (8, o (8k-1; a/-1)
#5 10
3: Increment the counter only for the current state by one.
4: Take action of
T.. where
{u.Gr. {n. Lou Tao (w)
T argmax (EA()).)
5: Collect the local reward rf and update the value function estimate for the current state according to
Gf ss. G 8440 [ Loc.k
0 k.
On the other hand, 6 s = 0% for all + 8k.
where vi is a smooth and strictly concave function whose gradient is unbounded at the boundary of the simplex ((A)) (Fudenberg and Levine 1998). The temperature parameter >> 0 controls the amount of perturbation on the smoothed best response. The smooth perturbation ensures that there
exists unique maximizer कं. = Br (Gan TMse). Choosing (1( == Entesy p|a²] log pla"]
results in the explicit characterization:
exp (at
[a
> O.
Ea exp (at)) /T
We let player update his local Q-function estimate's 's entry associated with the current state and local action pair (sk, af)) towards the reward received plus the discounted continuation payoff estimate. To this end, we include 1 an unbiased estimate of the continuation payoff obtained by looking one stage ahead, as in the classical Q-learning introduced by Watkins and Dayan [1992). Due the
one-stage look ahead, the update for the current state and local action can take place just after the game visits the next state. The update of 4 given by
Ly ++1 [ak] = Ler. [ak] + at (ré + Yot 1 Haaulas))
(8)
where aj E (0, 1] is defined by of = min { 1, amoz }. with facleso a step size sequence, and m[[ail
ri E I- R, R] denotes the immediate reward of player at stage k. There is no update on others, ie.. a² 1= = [a") for all (s, a²) * (sk, a.). Inspired by the approach in Leslie and Collins (005), the normalization addresses the asynchronous update of the entries of the local Q-function estimate and ensures that every entry of the local Q--unction estimate is updated at the same rate in expectation. We will show this explicitly in the proof of main theorem the supplementary material.
Simultancous to updating the local Q-function estimate, player i updates his value function estimate 62, towards गे. Lay corresponding the expected value of the current state. However, the player uses different step size {Be]e>0 and updates 0i according to
k+ G.
Byter [T]]
For other states + 8k, there is update the value function estimate, i.e., 02 02 C% To sum up. player i follows the learning dynamics in Table We emphasize that this dynamic is radically uncoupled since each player's update rule does not depend on the opponent's payoffs or actions. In the next section, we study its convergence properties.

---

3 Convergence Results
We study whether the value function estimates in the learning dynamics, described in Table [ converge to an equilibrium value of the zero-sum Markov game. The answer is affirmative under certain conditions provided below precisely. The first assumption (with two parts) is related to the step sizes and the temperature parameter, and not to the properties of the Markov game model.
Assumption 1-i. The sequences {ar E (0, 1)) and {3,- E (0, 1)3ss are non-increasing and satisfy 00 O2. co, Le=1 Be 00, and lime- Oc. = -om Be =0
Assumption 1-ii. Given any M (0, 1), there exists non-decreasing polynomial function C(-)
a. (which may depend on M) such that for any A E (0.1) if { {E 2+ 1 cand de > x} # 8, then
{ ( 12 and
Be > > S Mc, Mc, Vc 0C
max
(10)
Assumption T-1 is a common assumption used in stochastic approximation theory, e.g., see [Benaim [1999], (orkar 2008]. On the other hand, Assumption I-ii imposes further condition the step sizes than the usual two-timescale learning assumption, e.g., lime-+00 as update of the iterates. Particularly, the iterates evolving at fast timescale can lag behind even the iterates evolving at slow timescale due to their asynchronous update. Assumption 1-ii ensures that this can be tolerated when states are visited at comparable frequencies.
& 0, to address the asynchronous
For example, ae c Par and B. P9, where 0.5 < Pa < pp S 1, satisfy Assumption I since it can be shown that there exists a non-decreasing polynomial, e.g., C(x) Mo for all x 2 1, where M, == M - > 0 and m E {m' E Z+ m' 2 1/(ps - pa)]. We provide the relevant technical details in the supplementary material.
Such learning dynamics is not guaranteed to converge to an equilibrium in every class of zero-sum Markov games. For example, the underlying Markov chain may have an absorbing state such that once the game reaches that state, it stays there forever. Then, the players will not have a chance to improve their estimates for other states. Therefore, in the following, we identify two sets of assumptions (in addition to Assumption I imposing increasingly stronger conditions on the underlying game while resulting in different convergence guarantees.
Assumption 2-i. Given any pair of states (s, s'), there exists at least one sequence of actions such that s' is reachable from with some positive probability within a finite number, n, of stages.
Assumption 2-il. The sequence {Ta)eso is non-increasing and satisfies lilll-aeo (To-1 - TT) = and li To for some >> O. The step size {uefeso satisfies >e a < 00.
In Assumption we do not let the temperature parameter go zero. Next we let lime-+o Tc = 0 but make the following assumption, imposing further condition on the underlying game and Jeso compared to Assumption 2 ensure that each state gets visited infinitely often at comparable frequencies and the normalization in the update of the local Q-function estimate does not cause an issue since it can be arbitrarily small when Te -> O.
Assumption 2' Given any pair of states (s, s') and any infinite sequence of actions, s' is reachable from s with some positive probability within a finite number, n, of stages.
Assumption ii. The sequence Jezo is non-increasing and satisfies lim - (TTe1 = O 56 and tim To 0. The step size (Dra)e50 satisfies Eez1 2 < for some p E (0, 1). There
exists C, C' E (0, 20) such that af exp (DD/Te) S C' for all c 222. C.
While being stronger than Assumption 2-i Assumption 2'-iiionn''iii still weaker than those used in Leslic al. [2020]. In Leslie et al. [2020).
assumed that there is a positive probability of reaching from any state to any other state in one stage for any joint action taken by the players. On the other hand, we say that a Markov game irreducible if given any pure stationary strategy profile, the states visited form an irreducible Markov chain [Hoffman and Karp 1966 Brafman and Tennenholiz] 2002]. Assumption 2 is akin to the irreducibility assumption for Markov games because the irreducibility assumption implies that there is a positive probability that any state is visited from any state within [S] stages. Furthermore, it reduces to the ergodicity property of Markov decision problems, e.g., see Kearns and Singh 22022. if one of the players has only one action at every state.
7

---

As an example, ae ca and P. = c where 0.5 < Pa < Ps S satisfies Assumptions 2-ii
and 2 -i There exists p E (0, 2 1/p,) ) for the latter since Pa (0.5, 1). To satisfy Assumption
2-ii the players can choose the temperature parameter (Te)eso
- + (1 (1- <>>
(11)
with some 0. On the other hand, to satisty Assumption 2 they can choose the temperature parameter {Tchsso as
T( - (1+ Pall Pau log(c) 4D
Vc 0.
(12)
Alternative
To max (c, T-] also satisfies Assumption 2-ii while having similar nature with We provide the relevant technical details in the supplementary material.
11
(12).
We have the following key properties for the estimate sequence generated by learning dynamics.
Proposition Since at E (0, 1] for all k 2 0, Se E (0, (0,1) for all e > 0, | S D and l - D for all (i, 8), the iterates are bounded, i.e., 11 I D and 10 S for all (i, 8) and h 0.
Proposition 2. Suppose that Assumption 1-i alnnd either Assumption 2- ii
or 2 -ii
hold. Then, there
exists C. E 2, for each & S such that ore exp (2D/Te) &min;=1. Correspondingly, the update of the local Q-fanction estimate ( reduces to
( }. for all e 2 Cs.
laia I2 [lak] +
OHa [h[ai]
(r), + yo s4
L (af((at))))
(13)
for all #sa 2 Cea since a [ S A la#s2 exp (2D/ (2D/T S 1 by 7
Proposition Suppose that either Assumption 2 or Assumption 2 holds. Then, at any stage k, there is a fixed positive probability, e.g., p >> O, that the game visits any state s at least once within n-stages independent of how players play. Therefore, #s + oo k - oo with probability 1.
Proposition
says that defining a² min (1i / aal] ensures that the iterates remain bounded.
On the other hand, Propositions 2 and 3 say that the update of the local Q-function estimates reduces to (13) where at. = s, / & [i after a finite number of stages, almost surely. The following
theorem characterizes the convergence properties of the Q-learning dynamics presented.
Theorem 1. Suppose that both players follow the learning dynamics described in Table and Assumption holds. Let v²_ and Q²., described resp. in 2 and (4). be the unique values associated with some equilibrium profile æ. (m), x2) of the underlying zero-sum Markov game. Then, the asymptotic behavior of the value function estimates {6) 1220 is given by
lim sup 6 v'a, (s)] <Eg(T), under Assumption 2
(14a)
k++00
lim 16 " (6)
under Assumption
(14b)
k-000
for all (i, E [1,2} x S, with probability (w.p.) 1, where & : max.es {log(14)/1421)) and 2+A-A7 with some X E (1,1/7).
9(7) (1->a)(117)
Furthermore, let Hi be the weighted time-average of the smoothed best response updated as
#2,4+1 #h. [smas) a# (T). #5,a)
Then, the asymptotic behavior of these weighted averages { is given by
lim 1-+00
max v² nr " (
vi # (s) S <et(()), under Assumption
(15a)
x²
lim k-000
max of
(s) O,
under Assumption
(15b)
#
for all 8) (1,2) x S, w.p. 1, where h(()) [A7 41/111 i.e., these weighted-average strategies converge to near or exact equilibrium depending on whether Assumption 2l 2 hold.

---

A brief sketch of the proof is as follows: We decouple the dynamics specific to a single state from others by addressing the asynchronous update of the local Q-function estimate and the diminishing temperature parameter. We then approximate the dynamies specific to single state via its limiting ordinary differential equation (o.d.e.) as if the iterates evolving at the slow timescale are time- invariant. We present novel Lyapunov function for the limiting o.d.e. to characterize the limit set of the discrete-time update. This Lyapunov function shows that the game perceived by the agents become zero-sum asymptotically and the local Q-function estimates are asymptotically belief-based Finally, we use this limit set characterization to show the convergence of the dynamics across every state by using asynchronous stochastic approximation methods, e.g., see Tiitsiklis [994]].
The following corollary to Theorem Thighlights the rationality property of our learning dynamics.
Corollary 1. Suppose that player -i follows an (asymptotically) stationary strategy { E int (A:)))))sss ses while player i adopts the learning dynamics described in Table | and Assumption / holds. Then, the asymptotic behavior of the value function estimate (62, 18 given by
lim sup
of 8a
S <eL'9(7), max (0))
under Assumption 2
(16a)
k-+00
m
lim
Va
max oft, (s) = 0,
under Assumption 2'
(16b)
1-000
for all 8 E S, w.p. 1, where 5¹ :- max (log(IA)/1)) and g(-) is as described in Theorem
1
Furthermore, the asymptotic behavior of the weighted averages (+1 k22, described in Theorem 7 is given by
lim sup +0000 x²
max (0)) - U -U/g -2)) S he under Assumption
(17a)
lim
(s) max D
- [/2. (0) =
under Assumption
(17b)
k-000
T²
for all s S, w.p. 1, where h(7) is as described in Theorem |
ie.. these weighted-average strategies
converge to near or exact best-response strategy, depending on whether Assumption or hold.
4 Simulation Results
All the simulations are executed on a desktop computer equipped with a 3.7 GHz Hexa-Core Intel Core 17-8700K processor with Matlab R2019b. The device also has two 8GB 3000MHz DDR4 memories and a NVIDIA GeForce GTX 1080 8GB GDDR5X graphic card. For illustration, we consider zero-sum Markov game with states and actions at each state, i.e., S = 21, ,5] and A [1. 3). The discount factor 7 = 0.6. The reward functions are chosen randomly in a way that (a a²) x ff,e" fe.a",e² _2² exp (s2) for 8 E S, where F. aaa is uniformly drawn from [-1, 1]. (a), aa)
then normalized by max,,a ,a² (r (a ,a²) so that Ir' aa²] < R for all (i, s, a a²). For the state transition dynamics p. we construct two cases, Case 1 and Case 2 by randomly generating transition probabilities, so that they satisfy Assumptions 2-1 and 2' respectively. For both cases, we choose ae = 1/c".9 and Be = 1/c with Pa 0.9, Ps = I, and
0.7, and set in accordance with (TT) and (12). respectively. For Case 1, we choose e 2 x 10 and F 4.5 x 104; for Case 2, 0.07. Note that the different choices of are due the different decreasing rates of To in (TT) and (2). and are chosen to generate aesthetic plots. The simulation results are illustrated Figure which are generated after 20 runs of our learning dynamics.
choose
As shown in Figure (a), for Case 1, the value function estimates successfully converge to the neighborhood of the Nash equilibrium values, where the size of the neighborhood is indeed controlled by (I4a). For Case 2, it is shown in (b) that the value function estimates converge to the Nash equilibrim, as 7 0. These observations have corroborated our theory established in $3 Moreover, is observed that the variance of the iterates decreases as they converge to the (neighborhood of) Nash equilibrium, implying the almost-sure convergence guarantees we have established.
Besides the illustrative example, we have also tested our learning dynamies on larger scale games, and validated our theory for this case (see Figure 3 See for for more details of the example.

---

0.6
0.4
Functions
Value Functions
0.2
0.2
-0.
-0.4
-0.4
0.5
10
500
20000
1o
Sev0
2000
20000
Be+07
Iterationn
Iteratione
Convergence under Assumption
(b) Convergence under Assumption
2
Figure 2: Convergence of the value function estimates after 20 runs the decentralized Qllearnin dynamics. The red and blue curves represent the quantities for players 1 and 2, respectively. The solid red/blue lines and the bar-areas around them denote the average value function estimates and the standard deviations, after the 20 runs, respectively. The solid
{ir (02,))22 all states black lines denote the summation of the estimates {ú0, + + x:20 at each s (which should converge (almost) zero asymptotically). The dotted lines ...../...... denote the actual Nash equilibrium values; the dashed-dotted lines -..._/-.-.- denote the boundaries of the neighborhoods around the Nash equilibrium given Theorem (a) Convergence to the neighborhood the Nash equilibrium
value, under Assumption 2 (b) Convergence to the Nash equilibrium value, under Assumption 2
0.8
0.5
0.4
Value Fundions
0.3
Value
0.1
02
0.3
104
10
10
10a
10
10
Iterations
(a) Convergence under Assumption
(b) Convergence under Assumption
Figure 3: Convergence of the value function estimates of the decentralized Q-learning dynamics. The blue curves represents the quantities for player 2. The solid blue lines denote the value function estimates (62,
J220 at all states s E S. The solid black lines denote the summation of the estimates {0), + J22o at each 8 (which should converge to (almost) zero asymptotically). The dotted lines ..... denote the actual Nash equilibrium values. (a) Convergence to the neighborhood of the Nash equilibrium value, under Assumption 2 (b) Convergence to the Nash equilibrium value, under Assumption 2
5 Concluding Remarks
This paper has studied decentralized multi-agent reinforcement learning in zero-sum Markov games. We have developed a decentralized Q-learning dynamics with provable convergence guarantees to the (neighborhoods the) Nash equilibrium value of the game. Unlike many existing MARL algorithms, our learning dynamics is both rational and convergent, and only based on the payoffs received and the local actions executed by each agent. It also requires neither asymmetric stepsizes/update rules or any coordination for the agents, nor even being aware of the existence of the opponent.
10

---

Acknowledgments and Disclosure of Funding
M. O. Sayin was with the Laboratory for Information and Decision Systems at MIT when this paper was submitted. K. Zhang and A. Ozdaglar were supported by DSTA grant 031017-00016. T. Başar was supported in part by ONR MURI Grant N00014-16-1-2711 and in part by AFOSR Grant FA9550-19-1-0353,
References
G. Arslan and S. Yuksel. Decentralized Q-learning for stochastic teams and games. IEEE Transactions on Automatic Control, 1545-158555558, 2017.
Y. Bai and C. Jin. Provable self-play algorithms for competitive reinforcement learning. In Proceed- ings of the 37th International Conference on Machine Learning (ICML), 2020.
Y. Bai, C. Jin, and Yu. Near-optimal reinforcement learning with self- eelf-play. In Advances Neural Information Processing Systems, volume 33, 2020.
M. Benaim. Dynamics of stochastic approximation algorithms. In Le Seminaire de Probabilities, Lecture Notes Math. 1709, pages 1-68, Berlin, 1999. Springer-Verte
V. Borkar. Reinforcement learning in Markovian evolutionary games. Advances in Complex Systems, 5(1):55-72, 2002.
V. S. Borkar. Stochastic Approximation: A Dynamical Systems Viewpoint. Hindustan Book Agency, 2008.
C. Boutilier. Planning, learning and coordination in multi-agent decision processes. In Conference on Theoretical Aspects of Rationality and Knowledge, pages 195-210, 1996.
M. Bowling and M. Veloso. Rational and convergent learning in stochastic games. In International Joint Conference on Artificial Intelligence, volume 17, pages 1021-1026, 2001.
M. Bowling and M. Veloso. Multiagent learning using variable learning rate. Artificial Intelligence, 136:215-2501 2002.
R. I. Brafman and M. Tennenholtz. R-MAX A general polynomial time algorithm for near-optimal reinforcement learning. Journal of Machine Learning Research, 3:213-231, 2002.
L. Busoniu, R. Babuska, and B. De Schutter. A comprehensive survey of multi-agent reinforcement learning. IEEE Transactions on Systems, Man, And Cybernetics-Purl C: Applications and Reviews, 38(2):156-17,, 2008.
N. 2006.
and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press,
C. Claus and C. Boutilier. The dynamics of reinforcement learning cooperative multiagent systems. In Proceedings of the 15th Conference on Artificial Intelligence (AAAI), pages 746 146-752, 1998.
C. Daskalakis, J. Foster, and N. Golowich. Independent policy gradient methods for competitive reinforcement learning. In Advances in Neural Information Processing Systems, 2020.
J. C. Ely and O. Yilankaya. Nash equilibrium and the evolution of preferences. Journal of Economic Theory, 97(2)2255-722, 2001.
J. Filar and K. Vrieze. Competitive Markov Decision Processes. Springer Science & Business Media, 2012.
A. M. Fink. Equilibrium in stochastic n-person game. Journal of Science Hiroshima University Series A-I, 28:89-93, 93, 1964.
J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, 2006.
D. Foster and H. Young. Regret testing: learning to play Nash equilibrium without knowing you have opponent. Theoretical Economics, 1:341-367, 2006.

---

Y. Freund and R. E. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):79-133, 1999.
D. Fudenberg and D. K. Levine. The Theory of Learning in Games, volume 2. MIT press, 1998.
D. Fudenberg and D. K. Levine. Learning and equilibrium. The Annual Review of Economics, 1: 385 419, 2009.
A. Greenwald, K. Hall, and R. Serrano. Correlated Q-learning. In International Conference on Machine Learning, pages 242-249 2003.
H. Guo, Z. Fu, Z. Yang, and Wang. Decentralized single-timescale actor-critic on zero-sum two-player stochastic games. In International Conference on Machine Learning, pages 3899-3909. PMLR, 2021.
C. Harris, On the rate of convergence of continuous- fictitious play. Games and Economic Behavior, 22:238-255 1998.
Hart and A. Mas-Colell, Uncoupled dynamics do not lead Nash equilibrium. American Economic Review, (3(5))1830-1)0) 1031-183000.----1111 2003.
Hemandezz M. Kaisers, T. Baarslag, and E. M. de Cote. A survey of learning in multiagent environments: Dealing with non non-stationarity. arXiv preprint arXiv:/707.09/88 2017.
P. Hemaadezz-Lal, B. Kartal, and M. E. Taylor. A survey and critique of multiagent deep reinforce- ment learning. Autonomous Agents and Multi-Agent Systems, 33(6):750-797, 2019.
J. Hofbauer and E. Hopkins. Learning in perturbed asymmetric games. Games and Economic Behavior, 52:133-152, 2005.
A. J. Hoffman and R. M. Karp. On nonterminating stochastic games. Management Science, 12(5): 359-370, 1966.
Hu and Wellman. Nash Q-learning for general-sum stochastic games. Journal of Machine Learning Research, 4(Nov):1039-1069 2003.
M. Kearns and S. Singh. Near-optimal reinforcement learning in polynomial time. Machine Learning, 49:209-232. 2002.
J. Kober, J. A. Bagnell, and J. Peters. Reinforcement learning in robotics: A survey, International Journal of Robotics Research, 32(11)):238-1274 2013.
L. Kuyer, S. Whiteson, B. Bakker, and N. Vlassis. Multiagent reinforcement learning for urban traffic control using coordination graphs. In Join! European Conference on Machine Learning and Knowledge Discovery in Databases, pages 156-671. Springer, 2008.
D. S. Leslie and E. J. Collins. Convergent multi-timescales reinforcement learning algorithms in normal form games. The Annals of Applied Probability, (234):1231-122 2003.
D. S. Leslie and E. J. Collins. Individual Q-learning in normal form games. SIAM J. Control Optim., 44(2):495-51) 514, 2005.
D. S. Leslie, S. Perkins, and Z. Xu. Best-response dynamics in zero-sum stochastic games. Journal of Economic Theory, 189, 2020.
P. Lillicrap, Hunt, Pritzel, al. Continuous control with deep reinforcement learning. arXiv preprint arXiv: 509.02971, 2015.
M. L. Littman. Markov games framework for multi-agent reinforcement learning. In Proceedings of the 1ith International Conference on Machine Learning (ICML), 1994.
M. L. Littman. Friend-or-foe Q-learning in general-sum games. In Proceedings of the Eighteenth International Conference on Machine Learning, pages 322-328. Morgan Kaufmann Publishers Inc., 2001.
12

---

Q. Liu, T. Yu, Y. Bai, and C. Jin. A sharp analysis of model-bases reinforcement learning with self-play, arXiv preprint arXiv:2010.01044, 2020.
L. Matignon, J. Laurent, and Le Fort-Piat. Independent reinforcement learners in cooperative Markov games: A survey regarding coordination problems. The Knowledge Engineering Review, 27(1): 31,, 2012.
Mertikopoulos and Z. Zhou. Learning in games with continuous action sets and unknown payoff functions. Mathematical Programming. 173(1):465-55) -677 2019.
V. Mnih, K. Kavukcuoglu, D. Silver, et al. Human-level control through deep reinforcement learning. Nature, 518(7549):529-533 2015.
D. Monderer and L. Shapley. Fictitious play property for games with identical interests. Journal of Economic Theory, 68:258 265, 1996.
J. Pérolat, B. Scherrer, B. Piot, and O. Pietquin. Approximate dynamic programming for two-player zero-sum Markov games. In International Conference on Machine Learning, pages 1321-1329, 2015.
J. Pérolat, B. Piot, and O. Pietquin. Actor-critic fictitious play in simultaneous move multistage games. In International Conference on Artificial Intelligence and Statistics, pages 919-928, 2018.
J. Robinson. An iterative method of solving game. Annals of Mathematics, 24:296-301, 1951.
A. E. Sallab, M. Abdou, E. Perot, and S. Yogamani. Deep reinforcement learning framework for autonomous driving. Electronic Imaging, 2017(19):00-76, 2017.
W. H. Sandholm. Preference evolution, two-speed dynamics, and rapid social change. Review of Economic Dynamics, 4(3):637-679, 2001.
M. O. Sayin, F. Parise, and A. Ozdaglar. Fictitious play in zero-sum stochastic games. arXiv:2010.04223,, 2020.
D. Shah, V. Somani, Q. Xie, and Z. Xu. On reinforcement learning for turn-based zero-sum Markov games. arXiv preprint 2xXi:2002./00600 2020.
S. Shalev-Shwartz, S. Shammah, and A. Shashua. Safe, multi-agent, reinforcement learning for 2016.
autonomous driving. arXiv preprint
L. S. Shapley. Stochastic games. Proceedings of National Academy of Science USA, 1095) 1100, 1953.
A. Sidford, M. Wang, L. F. Yang, and Y. Ye. Solving discounted stochastic two-player games with near-optimal time and sample complexity. arXiv preprint arXiv: /908. 1071, 2019.
D. Silver, Т. Hubert, J. Schrittwieser, et al. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv preprint arXh::1712.01813 2017.
C. Szepesvári and M. L. Littman. A unified analysis of value celleeffnnttio--eee based reinforeement-leaming algorithms. Neural Computation, 118)):01772060, 1999.
M. Tan. Multi-agent reinforcement learning: Independent vs. cooperative agents. In International Conference Machine Learning, pages 330-337, 1993.
Y. Tian, Y. Wang, T. Yu, and S. Sra. Provably efficient online agnostic learning in Markov games. arXiv preprint arXiv:2010. 15020, 2020.
N. Tsitsiklis. Asynchronous stochastic approximation and Q-learning. Machine Learning, 16: 185-202 1994.
O. Vinyals, T. Ewalds, S. Bartunov, et al. Starcraft II: A new challenge for reinforcement learning. arXiv preprint 11xxv:1708. 170800472, 2017.
O. Vinyals, I. Babuschkin, W. M. Czarnecki, Grandmaster level in StarCraft using multi-agent reinforcement learning. Nature, 575(7782):350-35, 2019.
13

---

O. J. Vrieze and S. H. Tijs. Fictitious play applied to sequences of games and discounted stochastic games. International Journal of Game Theory, 11(2):11-85, 1982.
Y. Wang and C. W. de Silva, A machine-learning approach to multi-robot coordination. Engineering Applications of Artificial Intelligence, 21(3):470-484, 2008.
C.J.C. C. H. Watkins and P. Dayan. Q-learning. Machine Learning, 8(3):279-292, 1992.
C.-Y. Wei, Y.-T. Hong, and C.-J. Lu. Online reinforcement learning in stochastic games. In Advances in Neural Information Processing Systems, pages 4987-4997, 2017.
C.-Y. Wei, C.-W. Lee, M. Zhang, and H. Luo. Last-iterate convergence of decentralized opti- mistic gradient descent/ascent in infinite-horizon competitive Markov games. arXiv preprini arXiv:2102.04540, 2021.
Q. Xie, Y. Chen, Z. Wang, and Z. Yang. Learning zero-sum sum simultaneous-move Markov games using function approximation and correlated equilibrium. In Conference on Learning Theory, pages 3674 3682. PMLR, 2020.
K. Zhang, Z. Yang, and T. Başar. Policy optimization provably converges to Nash equilibria in zero-sum linear quadratic games. In Advances in Neural Information Processing Systems, pages 11602-11614, 2019.
K. Zhang. S. Kakade, T. Başar, and L. Yang. Model-based multi-agent rl in zero-sum markov games with near-optimal sample complexity. In Advances Neural Information Processing Systems, 2020.
K. Zhang, 7. Yang, and T. Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Studies in Systems, Decision and Control, Handbook on RI. and Control, pages 321-384, 2021.
Y. Zhao, Tian, J. Lee, and S. Du. Provably efficient policy gradient methods for two-player zero-sum Markov games. arXiv preprint arXiv:2102.089000 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] See Section 3
(b) Did you deseribe the limitations of your work? [Yes] See Section 5
(c) Did you discuss any potential negative societal impacts of your work? [Yes] To the best of our knowledge, our work appears to be the first provably convergent decentralized Q- learning algorithm for Markov games that enjoys all the desired properties above. Some limitations that are worth further investigation include, establishing non-asymptotic convergence guarantees; generalizing to other types of Markov games other than the zero-sum setting; generalizing to the setting with large state-action spaces and function approximation. Still, we believe our work has addressed an important open question in multi-agent RL, which would have broader impact learning in Markov/dynamic games in general. We also believe that our work will not cause any potential negative societal impacts. In fact, allowing symmetric update rules benefit the faimess and equality of multi-agent RL algorithms when applied to societal applications.
advocated might
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] our paper conforms to the ethics review guidelines.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 3
(b) Did you include complete proofs of all theoretical results? [Yes] See the supplementary material. We also included sketch of the proof in Section]
3. If you experiments..
14

---

(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or as a URL)? [Yes] See the supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A] There is no training for the algorithm.
(c) Did you report error bars (c.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] See Section 4
(d) Did you include the total amount compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See the supplementary material.
4. If you are using existing assets (e.g., code, data, models) or curating/releasnng new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "cuFAZuKeV-Z", "reviewer": "Reviewer_nE2G", "summary": "The paper studies the convergence of decentralized q-learning in two-player zero-sum games. The theoretical conclusion of the paper is sound. My main concern is regarding the originality and significance of this paper in comparison to a recent ICML 2021 paper.", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "* The paper studies the convergence of decentralized q-learning in two-player zero-sum games. There seems a recent ICML 2021 paper studies the same learning in games setting and reaches almost the same result: http://proceedings.mlr.press/v139/guo21a/guo21a.pdf. So one concern is about the originality and significance of this paper. \n\n* In addition, one of the key assumptions in deriving the convergence results is that every state is visited infinitely many times --> so that the global value function estimation \\hat{v} can be an unbiased estimator. But the appearance of the state seen by agent 1 is affected by the action/stratedgies of agent 2. What if agent 2 is a dummy player that takes the same action or an adversarial player? Actually, the state is not visited infinitely many times (and many states may not be visited) is a key challenge in actually training MARL. The other paper ICML 2021 didn't make this assumption - and this may be one of the reasons that they only have a stochastic convergence guarantee instead of the prob 1 results achieved in this paper.\n\n* The author may want to explain the experiment setup in further details. In Figure 2(a, b) There are 5 lines for each agent in each sub-plot, are they corresponding to 5 different zero-sum games? what are the game setup and parameters?\n\n* Figure 1 is confusing - it might be helpful to add more explanations or adjust the presentation to be more clear, and link the definition of global and local Q-functions to the corresponding equations.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not apply", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "bZ4DunYHOqj", "reviewer": "Reviewer_p9zY", "summary": "This paper presents a fully decentralized Q-learning algorithm for Markov games.  The individual (\"local\") Q-function is tracked separately from a state-value function, with updates to the Q-function taken according to a TD-error computed using the state-value function (of the next state).  Crucially, these two function are learned at differing timescales, making the action-reward value for each state \"appear\" stationary.  The algorithm is demonstrated to converge to Nash equilibrium (or the neighborhood of a Nash equilibrium, depending on the strength of assumptions made) in zero-sum Markov games when both players use it, both theoretically and numerically.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper gives a very elegant solution to a persistently vexing problem in MARL.  The solution has the potential to extend beyond the simple setting initially studied by the paper, and could have a substantial impact.  The paper is very well structured, and gives a clear motivation and intuition for each aspect of its results.\n\n#### Additional comments ####\n\n* It seems like Theorem 1 is a consequence of Corollary 1 more than the reverse.  In particular, Corollary 1's statement does not appear to depend upon the zero-sum property of the game at all, whereas Theorem 1 is a straightforward consequence of Corollary 1 given that the game has the zero-sum property.  This could point toward extensions beyond the zero-sum case.  E.g., stochastic games in which each stage game is a potential game seems like a natural next step, since better-response dynamics are guaranteed to converge to an equilibrium, and corollary 1 seems to point to a strong connection with better-response dynamics.\n\n* All of the statements of Theorem 1 and related results refer to global learning rates $\\{\\alpha_c\\}$ and $\\{\\beta_c\\}$ rather than agent-specific sequences.  Is this without loss of generality, or does the result of Theorem 1 rely upon both agents using common learning rates?  If yes, then this is still more uncoupled than a case where agents must agree on who is the \"fast\" learner and who is the \"slow\" one, but it still requires some coordination to agree on the learning schedule.\n\n* On a related note, is this algorithm more vulnerable than standard independent Q-learning approaches to exploitation by a sophisticated opponent who knows the learning algorithm being used?  I.e., if I know the opponent is using a particular learning schedule, can I exploit their value-estimates' being out of date by a particular non-stationary strategy?\n\n* I found the convergence described in Figure 2 to be somewhat surprising; it appears that one or the other agent always converges to a stage-game-suboptimal strategy in each stage game, rather than a \"natural\" equilibrium in which each player plays some equilibrium of the stage game at each stage.  (This latter equilibrium is guaranteed to exist, even when the players have different discount factors; it would give every state a discounted value of 0).  Is this a consequence of the requirement to play each action with a softmax probability (i.e., when there is a tie in expected continuation value between two actions, they must be played with equal probability if they also have the same expected reward)?  Or is there something deeper going on here?  Or is this just happenstance of which equilibrium was selected?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are directly and adequately addressed, including societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "TcH8TR1OsT", "reviewer": "Reviewer_KoGL", "summary": "The authors propose an independent Q-learning algorithm for two-player zero-sum Markov games. Asymptotic convergence results are obtained for the cases where both (or only one) players both follow the proposed algorithm.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Writing quality and clarity are okay. It's nice to have figures to illustrate the Q-functions. I do have some questions and concerns regarding the theoretical results.\n\n1. Asymptotic convergence: Having asymptotic convergence is not a strong enough result. Given the works [1, 2], can the authors get a rate of convergence? If not, what are the algorithmic/technical barriers that make getting convergence rates fundamentally harder?\n\n2. Rationality property: I think the authors are trying to argue  in ​\"rationality property\" (Corollary 1) that a player would learn good response even if the opponent does not follow the proposed algorithm. But my concern here is that, \n\n(1) When considering asymptotic convergence, letting the opponent using a stationary strategy almost surely actually means you are fixing the opponent's strategy throughout the learning process. How does this differ from learning optimal policy in the single-agent setting\n\n(2) Do we not allow the opponent to choose whatever strategy he wants in each iteration? If that's the case, aren't we still asking the two players to collaborate in a sense that the opponent should either follow the algorithm or keep using the same strategy \"almost surely\"?\n\n(3) Is best-in-hindsight response to arbitrary strategy sequence possible?\n\nIn my opinion, the above concerns make the convergence results in this paper less appealing that the typical convergence results with rates, and weaken the claim that the algorithm is fully \"decentralized\".\n\n[1] https://arxiv.org/pdf/2011.01868.pdf\n\n[2] https://arxiv.org/pdf/2010.15020.pdf", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "HQutU1_1y1u", "reviewer": "Reviewer_j6QZ", "summary": "This paper introduces a two-timescale variant of decentralised Q-learning for two-player zero-sum Markov games (without terminal states). Convergence of the algorithm is shown under several assumptions, and example experiments are provided to illustrate this convergence in practice.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I thank the authors for their detailed response to my queries, and maintain my rating. I'm glad the authors will add more detail around the experiment to the main paper. Interesting points were raised in other reviews regarding e.g. degree of decentralisation that algorithm achieves given the need for similar time-scale updates between the players - further discussion of these points in a later version of  the paper would be useful.\n\n---\n\nThis is a strong paper with an important central contribution. The paper is also generally very clearly written, and in my opinion the authors have achieved an excellent balance in the main paper between describing the algorithm, required assumptions, proof sketch, and illustrative experimental results. In addition, the work is well contrasted against a variety of different approaches to MARL in zero-sum Markov games.\n\nI have not had time to check all proofs in the appendix line-by-line, but have checked Propositions 1-3 and found these to be correct.\n\nSome minor comments are given below:\n\nStatement of Proposition 3: I don't think \"Assumption 2\" or \"Assumption 2'\" are defined as terms in the paper - does Assumption 2 mean 2-i and 2-ii together?\n\nSection 4: I appreciated the inclusion of a proof-of-concept implementation and experiment here. However, at present there is not really enough detail provided in the main paper to take much from the diagrams, and the reader is essentially required to consult the appendix to understand the significance of what is illustrated. If space allows, I think this section could be improved by including sketch details of the environment (and algorithm settings), perhaps at the cost of not illustrating convergence for both assumption sets in the main paper. As a very minor point, the last x-axis tick label in Fig 2a seems to have been cut off.\n\nQuestions for the authors:\n * Regarding the clipped learning in Line 2 of the Table 1, presumably any choice of upper-bound (in the range (0,1]) to clip at would yield a convergent algorithm (i.e. with Prop. 2 still holding for this modified algorithm, and the remainder of the argument then going through). Is there any particular reason to select 1 as the upper-bound here, other than the largest value that still guarantees boundedness of the iterates?\n * Do the authors have a sense of how important is the choice of entropy regulariser in Table 1? I.e. could a convergence proof hold for other classes of regulariser with the properties of strong concavity, unbounded gradients at simplex boundary etc.\n\nMinor notational comments:\nThere are a few minor notational issues in the main paper:\n * I found #s quite odd notation, in contrast to something like N(s). Potentially the notation used should also be something like N_k(s_k) rather than N(s_k) (or #_k s_k rather than # s_k in current notation), to make clear the dependence on k of the visit count. Without this, statements such as Proposition 3 look odd, since in \"# s -> infty as k -> infty\", the dependence of # s on k is not clear. This notation is used to some extent (e.g. proof of Prop 3), but would be clearer if used throughout.\n * The notation is a little imprecise in places: Eqn (1): expectation written over actions, but not states?\n * There are also some typos to be corrected in the main paper and appendix e.g. \"ith\" -> \"with\" Line 607.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "These aspects are addressed in Section 5.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "756WoikJffS", "reviewer": "Reviewer_1VzG", "summary": "The paper studies the Q-learning algorithm in the multi-agent setting, under the assumption that each agent observes its action and reward only while being completely unaware of the other agent's actions and rewards (decentralized setting). The asymptotic convergence of the proposed algorithm is proved under two different sets of assumptions regarding the algorithm hyperparameters. An illustrative experiment is presented.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "***Major***\n- My main concern is about the novelty of the work compared with the recent work [1]. Both the present paper and [1] consider the Q-learning algorithm in the multi-agent decentralized setting, with no communication between the agents. Besides the fact that [1] considers a single-timescale rule and the present paper a two-timescale rule, it seems to me that the results of [1] are more general/stronger. In particular:\n1) The present paper limits to the finite state case, whereas [1] uses function approximation and, therefore, can be applied to continuous state spaces (although the theoretical results are provided under the assumption that the function approximator allows representing the Q-function)\n2) The present paper provides an asymptotic convergence guarantee, while [1] manages to derive a finite-sample guarantee.\n\nCompared to [1], the present paper proves that the proposed algorithm is \"rational\", which seems a not too demanding requirement. Indeed, if the opponent is playing a stationary strategy, the problem reduces to single-agent RL.\n\n- Assumption 2-ii. The value of the temperature converges to \\epsilon in this assumption. This means that the agent will never play a deterministic policy. Instead, a small exploration will always be preserved. Does this imply that the algorithm will converge to an \\epsilon-Nash equilibrium rather than a Nash equilibrium?\n\n- Experiment. The experiment seems a little sacrificed there. The explanation is very synthetic, and nothing about the employed environment is reported in the main paper. I suggest considering moving the experiment to the supplementary material.\n\n\n***Minor***\n- Line 185: the subscript k is introduced here, but its meaning is explained only later\n- Table 1: shouldn't this be considered an \"Algorithm\" rather than a \"Table\"? Missing full stop at the end of the caption.\n- Is there any relation between the requirements of Assumption 1 and the classical Robbins-Monro conditions?\n\n***Overall***\nThe paper is written in good English, and the presentation is overall clear. My main concern, as reported above, is about the novelty of the work compared with [1]. I would greatly appreciate it if the authors could elaborate on the substantial differences between their work and [1]. For this reason, at present, I opt for a borderline score.\n\n[1] Guo, Hongyi, Zuyue Fu, Zhuoran Yang, and Zhaoran Wang. \"Decentralized Single-Timescale Actor-Critic on Zero-Sum Two-Player Stochastic Games.\" In International Conference on Machine Learning, pp. 3899-3909. PMLR, 2021.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a mainly theoretical paper. I do not foresee any societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Almost all the Reviewers agree that this paper is worth being published. The potential overlap with the ICML 21 paper raised initially serious concerns by the Reviewers. However, all the Reviewers agree that this paper and the ICML 21 paper are concurrent. I also believe that these two papers present several differences and the authors clearly discuss these differences in the rebuttals. I invite the authors to add a section in their paper in which the differences with ICML 21 are discussed. I also invite the authors to take into seriously consideration the following concerns raised by Reviewer KoGL and to clarify these issues in the paper:

*The "fully" decentralized claim is still questionable to me after reading the response. To some extent, it does make sense for agents to follow "myopic" best-response dynamics. But still, assuming every one of them being at the same level of "myopia" is sort of collaborating. And the Corollary 1 does not really tell any meaningful thing in terms of the algorithm's ability to exploit opponents that do not follows such dynamics.*

Frankly, I don't think that *assuming every one of them being at the same level of "myopia" is sort of collaborating*, but it could be useful that the authors clarify better this point in their paper.

Decision: Accept (Poster)