Decentralized Cooperative Multi-Agent Reinforcement Learning with Exploration
Authors: Weichao Mao
Tamer Basar
Lin Yang
Kaiqing Zhang
Venue: ICLR 2022 Submitted (2022)
Keywords: decentralized control
decentralized learning
game theory
reinforcement learning
reinforcement learning theory

Abstract: Many real-world applications of multi-agent reinforcement learning (RL), such as multi-robot navigation and decentralized control of cyber-physical systems, involve the cooperation of agents as a team with aligned objectives. We study multi-agent RL in the most basic cooperative setting --- Markov teams --- a class of Markov games where the cooperating agents share a common reward. We propose an algorithm in which each agent independently runs stage-based V-learning (a Q-learning style algorithm) to efficiently explore the unknown environment, while using a stochastic gradient descent (SGD) subroutine for policy updates. We show that the agents can learn an $\epsilon$-approximate Nash equilibrium policy in at most $\propto\widetilde{O}(1/\epsilon^4)$ episodes. Our results advocate the use of a novel \emph{stage-based} V-learning approach to create a stage-wise stationary environment. We also show that under certain smoothness assumptions of the team, our algorithm can achieve a nearly \emph{team-optimal} Nash equilibrium. Simulation results corroborate our theoretical findings. One key feature of our algorithm is being \emph{decentralized}, in the sense that each agent has access to only the state and its local actions, and is even \emph{oblivious} to the presence of the other agents. Neither communication among teammates nor coordination by a central controller is required during learning. Hence, our algorithm can readily generalize to an arbitrary number of agents, without suffering from the exponential dependence on the number of agents. 

Under review as a conference paper at ICLR 2022
DECENTRALIZED COOPERATIVE MULTI-AGENT REIN- FORCEMENT LEARNING WITH EXPLORATION
Anonymous authors Paper under double-blind review
ABSTRACT
Many real-world applications of multi- agent reinforcement learning (RL), such as multi-robot navigation and decentralized control of cyber-physical systems, involve the cooperation of agents a team with aligned objectives. We study multi-agent RI. in the most basic cooperative setting - Markov teams - a class Markov games where the cooperating agents share a common reward. We propose an algorithm in which each agent independently runs stage-based based V-learning (a Q-learning style algorithm) to efficiently explore the unknown environment, while using stochastic gradient descent (SGD) subroutine for policy updates. We show that the agents can learn an e-approximate Nash equilibrium policy in at most xx Ö(L/s*) episodes. Our results advocate the use of a novel stage-based V-learning approach to create stage-wise stationary environment. We also show that under certain smoothness assumptions of the team, our algorithm can achieve a nearly leam-optinal Nash equilibrium. Simulation results corroborate our theoretical findings. One key feature of our algorithm is being decentralized, in the sense that each agent has access to only the state and its local actions, and is even oblivious to the presence of the other agents. Neither communication among teammates nor coordination by a central controller is required during learning. Hence, our algorithm can readily generalize to an arbitrary number of agents, without suffering from the exponential dependence on the number of agents.
INTRODUCTION
variety of real-world sequential decision-making problems have been successfully addressed with reinforcement learning (RL), such as playing the game of Go (Silver et al. (016). Poker (Brown) Sandholm, 2018), real-time strategy games (Vinyals al.] 2019), autonomous driving (Shalev Shwartz et al. 2016), and robotics (Kober et al.] (013). Many of these applications can be cast as a multi-agent reinforcement learning (MARL) problem, where multiple agents are involved in interactive environment. These successful applications have inspired surging interest in understanding the theoretical aspects of MARL, which, however, is mostly devoted to the competitive setting, e.g., two-player zero-sum Markov games. This has left many problems in other important MARL settings, especially cooperative MARI, relatively open.
common task. We roughly categorize cooperative MARL settings into three classes based on the information available to the agents. The first class is (1) centralized/joint learning (Boutilier) 1996 Claus & Boutilier] 1998). which assumes that there exists single coordinator who can access the local information of all the agents, and makes decisions/learss policies jointly for all of them. This centralized training (though possibly decentralized execution) approach has become common practice in empirical MARL OOlihhoek et al. 2008 Foerster al. 2016 Lowe al., 2017 Rashid et al. 2018 Son et al.) 2019). Centralized learning essentially reduces the multi-agent problem to single-agent one, but such method does not scale well with the number of agents. fact, one can show that the computation & sample complexity grows exponentially with the number of agents in the worst case. The second class is (2) learning with communications (Kar et al. 2013 Zhang et al. 20188) Dubey & Pentland 2021), which typically assumes that the agents can communicate by sharing some local information with other agents (sometimes through a central agent). This approach gets around the centralized computation bottleneck, but instead suffers from additional communication overhead. It can also be
Cooperative MARL generally involves team of agents collaborating

---

Under review as a conference paper at ICLR 2022
unrealistic in some real-world scenarios where communication may be expensive and/or unreliable, such as in unmanned aerial vehicle (UAV) field coverage (Pham et al. 2018).
Given the aforementioned limitations, we are more interested, in this paper, in more practical setting: (3) decentralized learning") | to its own local information (e.g., local actions and rewards), and can neither communicate with its teammates nor be coordinated by any central controller during learning. In fact, we require that each agent is completely unaware of the underlying structure of the game (whether it is cooperative or not), or even the presence of other agents. Among the three classes mentioned above, decentralized learning requires the weakest assumption on information availability, which makes it suitable for many practical multi-agent learning scenarios (Fudenberg et al., 1998; Waag & de Silva, (208] Kuyer et al. 2008). In addition, decentralized learning is generally more scalable, and does not suffer from the exponential sample & computation complexity in the number of agents. Seemingly tempting, one might wonder how strong, if any, theoretical results can be established in this challenging decentralized setting. In the paper, we investigate the theoretical aspects of decentralized cooperative multi-agent RL in the non-asymptotic regime. A natural and fundamental theoretical question is:
We enforce a seemingly daunting restriction: Each agent only has access
Does any independent Q-learning style algorithm lead Nash equilibria in cooperative MARL?
The answer to this question has remained elusive ever since it raised in Lauer & Riedmiller (2000). To answer this question, we focus on arguably the most basic and fundamental cooperative MARL setting- Markov teams (Lauer& & Riedmiller 2000 Boutilier 1996; Wang & Sandholm 2002) where the cooperating agents share a common team-reward function, and the state transition the environment is affected by the joint actions of all agents. In fact, even in the basic Markov team setting, decentralized learning can be highly challenging. First, since both rewards and transitions are affected by the other agents, the environment becomes non-stationary from each agent's own perspective when the other agents also update their policies. Hence, an agent needs to explore the unknown environment efficiently while keeping in mind that the information it gathers now will soon become outdated. This rules out many successful single-agent RL solutions, which critically rely on the assumption that the agent is learning in a stationary environment. Second, compared with RL in two-player zero-sum games, an additional challenge in teams is the existence of possibly multiple Nash equilibria (NE) with different values. The agents in teams hence have to additionally coordinate on which NE to converge to. Our contributions in the paper are summarized as follows.
Contributions. 1) As a warm-up, we start with decentralized matrix teams (Section 3 which constitute special class of Markov teams with state transitions. We show that a simple stochastic gradient descent (SGD) algorithm can provably find an E-approximate NE policy using x O(1/E") samples, which can be improved to O(1/e") by using variance reduction techniques. 2) For the general problem of decentralized Markov teams (Section 4 we propose an algorithm named Stage- Based V-learning with Stochastic Gradient Descent (V- 1e-learnning SGD), where V-learning (a name first coined in Bai et al. (2020) is a simple variant of Q-learning. Our algorithm can be executed in decentralized way as we defined above. 3) We show in Section5]thhr that if all agents in the team V-lea rnternniin ng SGD, they can find e-approximate NE in most 0(1/e") poly(S, H, Amax) episodes, where S is the number of states, Amax is the size of the largest action space, and И is the length of an episode. Our results rely on a novel investigation of stage-based V-learning to create a stage-wiss stationary environment for the agents. 4) We further show that our algorithm can approach the best equilibrium, i.e., the tpti-optimallty, in a specific class of problems named "smooth teams". 5) In Se we provide numerical results that corroborate our theoretical findings. To the best of our knowledge, our work appears to be the first to provide non-asymptotic guarantees for cooperative MARL with exploration, while having the additional advantage of being decentralized.
Related Work. common mathematical framework of multi-agent RL is stochastic games (Shapley) 1953), which is also referred to as Markov games. Early attempts to learn NE in Markov games include Littman 1994 200T): ); Hu & Wellman (2003); Hansen et al. (2013), but they either assume the transition kernel and rewards are known, or only yield asymptotic guarantees. Recently, various sample efficient methods have been proposed (Wei et al. 2017 Bai & Jin 2020 (Sidford et al. 2020
'This setting has been studied under various names in the literature, including individual learning (Leslie
Collins (005) decentralized learning (Arslan & Yükksll 2016). agnostic learning (Tian et al. [202]] Wei et al.
2021). and independent learning (Claus & Boutilier | Daskalakis et al. 2020). It also belongs a more
general category of teams/games with decentralized information structure (Ho 1980 Nayyar et al. 2013a
2

---

Under review as a conference paper at ICLR 2022
Xie et al. 2020 Bai et al. 2020 Liu et al. 2021 Zhao et al., 2021: Guo al. 2021 mostly for
learning in two wlo-player zero-sum Markov games. Several works have investigated zero-sun sum games in decentralized setting as we consider here (Daskalakis et al., 2020 Tian et al.. [021 Wei et al. [202]] Sayin et al. 2021). but these results do not carry over in any way to the decentralized cooperative/team setting. We refer the reader Appendix [ for more detailed discussion on these related works.
Another line of research has considered RL in teams. Without enforcing a decentralized environment, Boutilier 1996) has proposed coordinate the agents by letting them take actions in a lexicographic order. Wang & Sandholm (2022) have studied optimal adaptive learning that converges to the optimal NE in Markov teams. These two methods critically rely on communications among the agents (beforehand) and/or observing the teammates' actions. In contrast, the distributed Q-learning algorithm in Lauer & Riedmiller (2000) is decentralized and coordination-free. which, however, only works for deterministic tasks, and has no non-asymptotic convergence guarantees. In fact, developing provable decentralized RI. for cooperation in general stochastic environments is considered an important open problem in Lauer & Riedmiller 22000) which we address in this paper.
Arslan & Yüksel (2016) and Yongacoglu et al. 2019) have shown that decentralized Q-learning style algorithms can converge to NE in weakly acyclic games, which cover Markov teams as an important special case. Their decentralized settings are most similar to ours in that each agent is oblivious to the presence of the others. However, both of them require coordinated exploration phase, and only yield asymptotic guarantees. In fact, it is not clear if their methods will converge in polynomial time. We significantly improve their results in this respect, by explicitly showing polynomial sample complexity upper bound. Two contemporancous works (Zhang et al. 2021b) Leonardos al. 2021 have studied gradient play in Markov potential games [ but they do not consider the aspect of exploring the unknown environment, one of the key issues in RL, and/or have to assume perfect knowledge of the environment. A concurrent work (Chang al., [22T] has studied cooperative multi- player multi-armed bandits with information asymmetry, which parallels our matrix team setting. Nevertheless, (Chang et al., 202T) requires stronger conditions than our decentralized setting as their algorithm relies on playing predetermined sequence of actions.
2 PRELIMINARIES
An N N-player episodic Markov team is defined by tuple (N, S. [A
Ii=1, P). where (1) =
{1, J,......, N} is the set of agents; (2) H E N_ the number of time steps in each episode; (3) is the finite state space; (4) AA' is the finite action space for agent E N: (5) [H] x S x A - [0. 1] the team reward function for all agents, where A = x A' A is the joint action (or action profile)
space; and (6) P: [M] x S x A A(S) is the transition kernel. We remark that both the reward function and the state transition function depend on the joint actions of all the agents.
The agents interact in unknown environment for K episodes. At each time step h E [M]. the agents observe the state 8/ E S, and take actions aj, E AA', E N simultaneously. All agents receive the same reward Th (sh, a,). where a₁ = (a)..... a ), and the environment transitions to the next state S/+11 ~ Pr. (-|sn, ).). We assume for simplicity that the initial state $1 of each episode is fixed. Note that the state transition here is general and not restricted to be deterministic, in contrast to Lauer & Riedmiller (000). This makes decentralized learning considerably more challenging, the agents cannot implicitly coordinate by snumerating/rehearsinn all possible states. We focus on the decentralized setting, where each agent only observes the states, rewards, and its own actions, but not the actions of the other agents. We require that each agent is completely oblivious of the existence of the others, and is also not allowed communicate. This decentralized information structure requires each agent to learn to make decisions based on only its local information.
For each agent i, a (Markov) policy T' [M] S + A(A') is mapping from the time index and state space to distribution over its own action space. Each agent seeks to find a policy that maximizes own reward. A joint policy (or policy profile) æ (T ........'' .. NN) induces a probability measure over the sequence of states and joint actions. For convenience, we use the superscript -i denote the set of agents excluding agent i, i.e., (i). For example, we can rewrite म = ( ; -)
2 All our results in this paper immediately generalize to Markov potential games, which include Markov teams as special case. For simplicity of notations, we illustrate our algorithm and results only in the Markov team setting. A short discussion Markov potential games is included in Appendix B
3

---

Under review as a conference paper at ICLR 2022
using this convention. For policy profile 9, and for any h [H] E S, and a E A, we define the value function and the state-action value function (or Q-function) as follows:
H The an)) 88 s) O. (7, h==h
H
E
The The (Bw, aw)) 88 8, ap = (1)
N/=h
For agent i, a policy x²x is a best response to π if V
(s) = sup,r V/ Vi (s), for any step
E [H] and state s E S. A policy profile π = (I' "T is a Nash equilibrium if is a best response x' for all E .V. One can show that NE always exists in finite Markov teams (Boutilier 1996). There can be multiple NE in a Markov team with possibly different values. One desirable cquilibrium is the team-optimal one that achieves the highest value. Specifically, a policy profile ' is
tean-optimal if V (s) =up= V (s), for any step h E [H] and state E S. It follows immediately that a team-optimal policy profile is always a NE, but the converse is not true in general.
For general (non-Markov) policies, we can still define their values step h in sense similar to Equation I A best response T with respect to general policies x maximizes player i's value at step I, i... Vi=". ; (s1) sup,. ViT", (s1). The best response to the general policies of the opponents is not necessarily Markov. We also have an approximate notion of Nash equilibrium:
Definition 1. (e-approximate Nash equilibrium). F > a general policy profile π (I², x= is
an e-approximate Nash equilibrium if V (s1) 2 sup," gt
V x (ss) for all i E N, where the supremam is taken over all general policies that are not necessarily Markov.
For notational convenience, in most parts of the paper we illustrate our algorithms and results for two-player teams, i.c., N = 2. It is straightforward to extend our results the general N -player team as we defined above. With two players, we use A and B to denote the action spaces of players 1 and 2, respectively. Let S [8], A |A B [ Denote by Amax max B), which is known to both players. We also rewrite the policies (xt T²2 as (H, ) for notational convenience.
3 WARM-UP: THE MATRIX TEAM
As a warm-up, we start with a simple matrix team problem, where two agents repeatedly interact in a single-stage team (Claus & Boutilier 1998) with stochastic rewards. This is essentially Markov team with single state and H 1. The intuitions and results in this section will become useful later in our analysis of the general Markov team problem.
two-player finite matrix team can be described by a tuple (A, B. p). where A and B are the finite action spaces for agent 1 and agent 2, respectively, and the stochastic reward function p p= (Pa. a E A, b E B) is a collection of reward distributions with support [0, 1]. The agents interact for T rounds. At each round & E [T]. agent 1 (resp. agent 2) chooses an action a, A (resp. b, B). Both agents receive the same reward RG drawn i..dd. from the reward distribution Pache. We let r: A B + 10 be the expected value of the reward function, i.e., r(a, b) fo ad (x)),,(x)) We use μ (AA and ABB) to denote the mixed strategies (or simply strategies) for agent 1 and agent 2, respectively. Slightly abusing notations, the value function for a strategy pair = (1,, v) is denoted by ((x) = (p, v) def [Exxo[r(a, b)], where a ~ - and b V.
In an unknown environment, a natural tactic for a self-interested agent is to adopt a no-regret learning algorithm to guide its action selection (Cesa-Bianchi & Lugosi 2006). In our problem, we propose to let each agent run a simple no-regret learning algorithm, namely (projected) stochastic gradient descent (SGD). Our Stochastic Gradient Descent with Implicit Exploration BSGD-IX) algorithm for agent 1 is presented in Algorithm[[ The algorithm run by agent 2 is symmetric and hence not included. Our use of SGD is motivated by the simple observation that every first-order stationary point of the value function is also NE for the matrix team (Lemma 4), and that SGD does lead to stationary points in non-convex optimization (Ghadimi & Lan 2013). Our solution also relies on the fact that centralized SGD can be decoupled into a decentralized one (Lemma 5). the joint strategy is a Cartesian product of individual strategies. For generality, we write our gradient descent step in Algorithm|] aas online mirror descent (OMD) update. For more detailed descriptions and we refer the reader to Appendix D The following result shows that the
intuitions of Algorithm [ output strategy pair of Algorithm]] 1 is close to NE in expectation.
4

---

Under review as a conference paper at ICLR 2022
Algorithm I: SGD-IX: Stochastic Gradient Descent with Implicit Exploration (for player 1)
Initialize: Mi,a < 1/A, Va A, a4 + T Vt [T], and x- T-144
2 for t 4- to T' do
Draw action de ~ 14 (14.1...... pe,A):
4 Take action ag, and observe the team reward R;;
1-fe Ifat a), Va E A, and V Vula t- (V Vi,it...... Vy, L..: Me+1 + AE { ( (V 1)) + J. DW (1, mi) where w(x) ||m112 and Du (²) ) = w(p) (p') (Vw (p'), H¹);
Vaaat #1.tt
Output 14, where + is uniformly sampled from (1....,7}:
Theorem 1. Suppose that both agents run Algorithm for I rounds. Let the two agents uniformly draw time index T from [I....,T} and denote by Iy = (Ur, the output of the algorithm. For any E > 0, i (2(1/=)) )polyAAmax), (Amax), then (Hr, 1/)) is an e-approximate Nash equilibrium in expectation, where poly(Auax) denotes a polynomial of Amax.
Note that to extract an approximate NE strategy, the agents need to sample the same time index 7. This requires some common source of randomness like shared random seed. Such common randomness is also termed a correlation device, and is standard in decentralized learning (Bernstein) al. 2009] Arabneydi & Mahajan 2015 Zhang et al.) 2019), Note that the correlation device is never used during the learning process to coordinate the exploration, but is simply used to synchronize the selection of the strategies after they have already been generated by the learning algorithm. common mild assumption and does not break the decentralized paradigm. In addition, we would like to remark that Theorem Dis not an immediate consequence of, and, in fact, is fundamentally different from, the folklore result that the empirical frequency of plays of independent no-regret learning converges to the set of coarse correlated equilibria (CCE) in general-sum normal-form games (Hart & Maa-Colell 2000). In teams, the of NE can be strict subset of CCE in general. Theorem also crucially takes advantage of the first-order stationarity of NE in teams, property that clearly absent in the folklore result of general-sum games.
random seed is generally considered
In the following theorem, we further show that the sample complexity of learning in matrix teams can be improved to ((1/e*) by utilizing variance reduction technique. The corresponding algorithm and its analysis are deferred to the appendices due to space limitations.
Theorem 2. Let the agents run variance-reduced SGD (Algorithm in Appendix E) for T rounds. For any 0, T (2(1 (((1/=4) poly( Amax), ), then (Mr; 1y) is an S-approximate NE in expectation.
4 A DECENTRALIZED COOPERATIVE MARL ALGORITHM
In this section, we introduce our algorithm Stage-Based V-learning with Stochastic Gradient Descent (V-learning SGD) for decentralized multi-agent RL in Markov teams. A well-known key chal- lenge in MARL is that the environment becomes ntn-stationary from each agent's 's own perspective when the other agents also update their policies (Busoniu et al. 2008 Zhang et al. 2021a). To address such challenge, we propose to stage-based Q-learning style algorithm to create stationary environment for the agents, while invoking the SCD-IX subroutine (Algorithm such stationary stage for policy updates. As interesting side remark, stage-based Q-learning has also achieved near-optimal regret bounds in single-agent RL (Zhang et al. 2020b).
tisee [ in each
The algorithm run by agent is presented in Algorithm 2 The algorithm for agent is symmetric, by simply replacing the action space A with B. Each agent runs a stage-based V-lcarning algorithm independently, and maintains upper confidence bounds on the value functions to actively explore the unknown environment. For each step-state pair (h, s), we divide the visitations to this pair into multiple stages, where the lengths of the stages increase exponentially at a rate of (1 + 1/H) (Zhang H, and ci+1 [[1 + 1/ Hea 2 denote the lengths of the stages, and let the partial sums L def (Ei- e; j = 1,2,3..... denote the set of ending times of the stages. For each (h, s) pair, we update our optimistic estimates V (sx) of the value function at the end of each stage (that is, when the total number of visitations (s, h)) lies in the set
et al. 2020b). Specifically, we let
5

---

Under review as a conference paper at ICLR 2022
Algorithm 2: V-VVeaaainng SGD: Stage-Based V-learning with Stochastic Gradient Descent
Initialize: (s(s) H h + (s) 0, (s) t 0, 0% + (,) H.
and u (a 8) < 1/A, vh E [H] S.
for episode k < to K do
Receive $1;
for step h t 1 to H do
(s, (sh) + 1, _ Ns.ss)) (sh) + 1;
Take action ap p. sn), and observe reward Tu and next state $/+1i
(sh))) + (sh) + The Un (sh) + (sh) + (5t4()))1:
if (sh)))) ) E C then
//Entering a new stage
(n(sh) & (1(9h) + (n(sn) + ba, where ba t 25H V A Amaxx/ ////4, (sh) (5.) + (s)) + O, (,hh(sh)= [11 [shh(s))];
11
1/(a sh)= t 11/A, Va AA;
12
On + (3n)) -3/4 .7 + (fn()n)) -1/1
13
V vnaLn t 8-h+1- + (etzi I(an = a}, Va E A:
14
JuLn t- (VH,ILa..... MALL));
p (. (n) <- argmin (EA(A) (. (Vplin 11)
11) (aa)) where w(p) |114122 and D. (1, = ((x) - w (1') - (Vu (V ,1 - -d));
Da (1.
16
on
L). using samples only from this single stage. This way, our stage-based V-learning ensures that only the most recent Ol1HH) fraction of the collected samples are used to calculate V a (sx), while the first 1 1 H) fraction is forgotten. Such a stage-based update framework some sense mimics the celebrated optimistic Q-learning algorithm with learning rate of a, = π++
H+1 (Jin et al. 2018), which also roughly uses the last O(1 H) fraction of samples for value updates. However, we would like specifically emphasize that the V-learning variant Jin al. (2018) does not directly apply to our problem due to some technical challenges that will be covered in Section Unlike Jiin et al. (2018). our stage-based V-learning ensures that the value function estimates are updated a low frequency, property also termed low-switching cost in single-agent RL (Bai et al. 2019), which is crucial address the non -tationntna issue in our MARL problem.
Another key component of Algorithm is is the SGD subroutine. For each step h E [H] and each state 8, S. we treat the agents' interactions s; as a separate matrix team problem, similar to what we have defined in Section 3 The reward function for such matrix team is the Q Q-function at the corresponding state, which is directly related the optimistic value function estimates V (8h) that we have constructed in the V-learning part. Since our stage-based V-learning only updates V, (s,) at the end of a stage, it creates stage-wise stationary environment in the sense that the value of (*)) ) is fixed within each stage, which can be captured by our stationary problem formulation in Section We can hence directly invoke Algorithm and its analyses for the matrix team problem at each step-state pair (h, sn). Finally, we remark that both the V-learning and the SGD components of algorithm are decentralized, which can be implemented using only the states observed and the local actions executed, without any communication or central coordination among the agents.
5 THEORETICAL ANALYSES
In this section, present main results on the sample complexity of V- V-learning SGD. We
first introduce a few notations to facilitate the analysis. For a step E [H] of an episode k E [K], denote by si the state that the agents observe this time step. For any state
S, we let
u s) (AA) and v. (-1 | s) E A(B) be the strategies prescribed by Algorithm 2 to agents 1 and 2, respectively, at this step. Notice that such notations are well-defined for every s E S even
if might not be the state S that is actually visited. We further let μ {nf(- |s) s E S) and
ot =v s) S). Let of E A and by B be the actual actions taken by the agents.

---

Under review as a conference paper at ICLR 2022
Algorithm 3: Construction of the Output Policy Fi
Input:
The strategy trajectory (u (MJ specified by Algorithm
H.K
Initialize: k' <- k. for step ht 4 h to H do Receive 8p6;
5. Take action ON- ~ (. sw);;
Uniformly sample from {1, .1........ NW (sw));;
7 Set + , where recall that iy is the index of the episode such that state sn was visited
the i-th time (among the total N (sw) times) in the last stage;
For any s E S, let (s), (s), and (s) denote, respectively, the values of (s), and (s) at the beginning of the k-th episode. Note that it proper to use the same notation to denote these values from the two agents' perspectives, because both agents maintain the same estimates of these three terms as they can be calculated from the common observations (of the state- visitaiista::on)
Further, for a state st, let ni denote the number of times that state a has been visited (at the h-th step) in the stage right before the current stage, and let ih,, denote the index of the episode that this state was visited the i-th time among the nil, times. For notational convenience, we use to denote nh. and 4, to denote i/. whenever h and are clear from the context. With the new notations, the update rule in Line 10 of Algorithm 2 can be equivalently expressed as
Σ i=1
(ra(s,,af .l.b///))))) V (iin(())t))) + ba-
Similar to the situation of learning in zero-sum Markov games (Bai et al. 2020), the strategy trajectories {p k) H.K
) Jhm1,km themselves are not guaranteed to converge to an approximate NE. H.K
Instead, based on (Guk, 1h) we extract an auxiliary set of policies ((ak, { that leads to an approximate NE, Our construction of the auxiliary policies, largely inspired by the "certified policies" (Bai et al. 2020 for learning in two-player zero-sum games, is formally presented in Algorithm 3 At the step and state Sh, f first executes the strategy (1 s).). It then uniformly samples an episode index k'' from the total N1 (8%. episodes that the state 84, was visited during the last stage. Finally, 2 repeats a similar process at step h + and episode K' and so on. We define & analogously. Compared with the certified policies in zero-sum games, our team problem has the additional challenge that the NE value is not necessarily unique, and need first specify which NE to compare with before we are able to define the notion of regret. Therefore, the analytical method of bounding the duality gap in zero-sum games (Bai et al., (2200) does not apply our problem. We also remark that our construction of the auxiliary policies slightly simplifies the "certified policies" in the sense that we only need uniformly sample an episode index at each step, while the certified policies rely on a rather complicated weighted sampling. Such simplification is a natural benefit of our stage-based V-learning that assigns uniform weights to all time steps of the same stage in history.
Clearly, the policies (n 2/) are Mon-Markov, and many notations defined for Markov policies in Section 2 no longer hold. Nonetheless, we can still define the value function and the Q-function starting from a step h E [H] for a pair of non-Markov policies (7 D in similar way as in (I). because (f 27)) does not depend on the history before the h-th step. For notational convenience, we introduce the operators Pr, Vs, a, b) = E.g (-) (s") for any value function V, and Q(x) = ((a,)))((.)) Q(s, a, b). With these notations. the Bellman equations can be rewritten more succinctly as Qh (s, a, (rx + PA WIHH) (s, a, b), and (s = (Dinxu 2h (s) for
any (8, b, E S B H). For each la E [H], E S, define V (19911(() (s) and
def max D
PA h+1
(6),
(3)
where the stages are partitioned in the same way as the execution of Algorithm 2 particular, if the visitation to certain state is in its first stage, we let Vi (s) H hh+ 1 instead. We emphasize
7

---

Under review as a conference paper at ICLR 2022
that the maximum in ( is taken with respect to each individual episode i, and hence V/ (s) can be considered as the value of the "dynamic best response" with respect to the non-Markov policy p Such definition is stronger than the usual concept of "best fixed response in hindsight", and is crucial to ensure that we obtain a NE in the end, instead of only coarse correlated equilibrium (see
also Remark for detailed discussions). Define V7th.** (s) analogously.
In the following, we start with an intermediate result, which states that the optimistic value function 1% V (s) an upper bound of both VA (s) and Vi (s) in expectation.
Lemma 1. (s) 2 EIV, Si (s)] and B[V" 2 E[V," (s)], v(s,h,k) E S [M] x [K].
The proof of Lemma rrelies on our results from Section 3 Specifically, we can show that within each (stationary) stage, the agents face matrix team problem that lasts for n rounds, whose reward function
is associated with the optimistic value function (s) at the given state s. Since in Algorithm 2
both agents essentially reduces to the investigation of A Algorithm|i ii Section 3 We also remark that optimistic Q-learning with the celebrated learning rate of a₁ H-r (Jin et al. 2018) could fail this step, because induces matrix team problem with weighted rewards where the weights vary over time and cannot be pre-computed. Such time- vvre-ia rewards are not compatible with our SGD framework, and as far as we know it is challenging problem in stochastic non-convex optimization on its own. Interested readers are referred to Remarks ( 3 ii Appendix for detailed discussions of this technical challenge. We bypassed such a challenge by utilizing stage-based V-learning instead, which in essence assigns invariant and pre-computable weights to each time step in history. Our results hence advocate the use of stage-based V-learning in MARL, over the seminal work Jin al. (2018). because the former creates a stage-wist wise stationary environment, and by nature provides solution to the core issue of non-stationaritt (Busoniu et al., 2008: Zhang et al., (021a) in MARL.
an individual copy of Algorithm [ for each state, our analysis exactly
H+1
Suppose that for every (h,, A)) E [H] x [K], 7 and oy use a common random seed to sample the episode index from (I...., No. (s)). The value function for (ih, p/) can be written recursively as
pt oh (s)
ñ M
Xouff (Te + Pn V.P. Fhin PR
(s),
and y V reward sequence and the agents' selected actions), the agents have no incentive to deviate from the policy pairs {ūi k up to error term of the order O(K-3)
f (s) = O. The following result shows that, in expectation (over the randomness of the
Theorem 3. The auxiliary policies {Pp) )
) 1,k=1 satisfy that
H.K
E Vi (s1) - -on)-viin ut (51) s O(H s A kx)) A and
K
E pypt (s1) - vatt.et s SHH 2f
s 2 K*).
An immediate corollary is that, if we let the agents uniformly sample an episode index k from {I...., K). the policy pair (p" D we constructed an approximate NE.
Theorem 4. Suppose that the two agents run Algorithum for K episodes with K = 22(1==)) poly( H, S, Amax). and uniformly sample an episode index k from {1....,K) K). Then, with probability at least 3. the policy pair , is an 6-approximate Nash equilibrium in expectation. A standard boosting technique (Mirzenmacher & Upfal 2017) can increase the success probability to an arbitrary value 1 for p (0, by repeating the process for Olog 1) times.
Remark 1. Theorem f states that we obtain an approximate NE with high probability for any realization of K, rather than only in expectation over the randomness of K. The former condition guarantees that each outcome (pf. ["r of the sampling process is a Nash equilibrium with high probability; with the latter condition, we only conclude that the uniform distribution over {(ph, 2/4 ) is a coarse correlated equilibrium, a weaker solution concept, where the common random seed plays the role of the "trusted coordinator" in the language of correlated equilibria.
8

---

Under review as a conference paper at ICLR 2022
Our sample complexity bound depends max(A, B} instead of A x B. This is the benefit from decentralized learning, and would not have been achieved by centralized approaches. Such an improvement would become more significant the number of agents N increases. Our decentralized approach only depends on the largest single action space max [A'), while the centralized methods would have exponential dependence TT A Also note that our sample complexity bound in Theorem 4 holds in expectation. To obtain standard high-probability result that holds with probability 1 p, one could either immediately apply Markov's inequality and tolerate an additional O(1/p) factor of computation, or replace our SGD subroutine with one that has high-pun tigh-probbbilityy guarantees instead (Li & Orabonal 2020). We leave such improvements to our future work as they diverge from the main focus of this paper. Similar to Section 3
the sample complexity in Theorem 4 can be further improved to Ö(L/E*) by incorporating variance reduction, which is sketched in Theorem 7 of Appendix G We remark that we have not attempted to optimize the dependence on the other parameters S and Amax- There are many straightforward ways to obtain tighter (t and y dependent on Amax-
bounds in these parameters, such as making the hyper-parametee For completeness, sample complexity lower bound in the order of (2(1=²)) poly(H, S, Amax) is presented in Appendix G which is achieved by a reduction to a single-agent RL problem. We leave the tightening of both the upper and lower bounds to our future work.
Finally, we show that our algorithm can nearly find the team- NE in an important subclass of Markov teams named smooth teams. Our definition of (A. p)ssooth team, adapted from the definition of smooth games (Roughgarden) 2009 Radanovic et al. 2019), is formally introduced in Definition 5 of Appendix G Define V to be the team-optimal value function, i.e, Vi,
max, V (8) for any h E [H] E S. The following theorem states that the output policies of Algorithm converge to A/(1 + factor of team-optimality at rate of O(K-)/))
Theorem 5. Let K (1(/=()))))))))))))))(())))))( )pol((H, S, Amax). In a (d, p) smooth team, the value of the auxiliary
H.K policies (phk 1=1 1 satisfies
vat (oi) 2 I+p
A (i (v)(
B) 1
1
6 SIMULATIONS
We empirically evaluate SGD-IX on a classic matrix team task, and V-learning SGD on a Markov team. Figure I Iillutraates the performances of the algorithms in terms of both the rewards and the L equilibrium gaps (which measure the L distance to NE, formally defined in (39) of Appendix Hj. Our simulation results turn out to be more encouraging that what our theory suggests: Both the actual policy trajectories ("Current") and the auxiliary policies ("Average") converge to NE in the tasks tested. Further, the rewards obtained approach those of team-optimal oracle ("Centralized"), which suggests that our algorithm achieves the team-optimal NE very frequently in our simulations, even though our theory does not guarantee so in general. Detailed descriptions of the simulations are deferred to Appendix due to space limitations.
Caree
Avetage Indeperttee
Aucrage
255
(a) Equilibrium gap (matrix) (b) Reward (matrix) (c) Equilibrium gap (Markov) (d) Reward (Markov)
Figure 1: (a) L equilibrium gaps and (b) rewards of Algorithm on the matrix team task, and (c) L equilibrium gaps and (d) rewards of Algorithm 2 on the Markov team task. "Current" denotes the actual policy trajectory H.KK
{(14, ) -= while "Average" represents the auxiliary policies ( (/) b In "Indopendent", each agent runs naive single-agent Q-lcarning algorithm independently, by taking greedy actions w.r.t its local Q-function estimates. Shaded areas denote the standard deviations of the equilibrium gap or reward.

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
As a theory-orienter work, we do not believe that our research will cause any ethical issue, or put anyone any disadvantage. In particular, do not believe that work will cause any discrimination / bias/ / fairness concerns, privacy and security issues, or legal compliance, and so on.
REPRODUCIBILITY STATEMENT
For every theoretical claim in the paper, we included clear statement and explanation all necessary assumptions right before after the theoretical claim. The complete proofs of all theoretical results in the paper can be found in Appendices E, F, and G. The source code used in the simulations are uploaded supplementary materials along with the submission of the paper.
REFERENCES
Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with a generative model is minimax optimal. In Conference on Learning Theory, pp. 67-83, 2020.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-76, 2021.
Zeyuan Allen-Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. In International Conference Machine Learning, pp. 699-707. PMLR, 2016.
Jalal Arabneydi and Aditya Mahajan. Reinforcement learning in decentralized stochastic control systems with partial history sharing. In American Control Conference, pp. 5449-5456. IEEE, 2015.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprint 1rXiv:1912.000 2019.
Gürdal Arslan and Serdar Yüksel. Decentralized Q-learning for stochastic teams and games. IEEE Transactions Aulomatic Control, 6254):1555-1558 2016.
Orly Avner and Shie Mannor. Concurrent bandits and cognitive radio networks. Joint European Conference Machine Learning and Knowledge Discovery in Databases, pp. 66 66-81, 2014.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce-
ment learning. In International Conference on Machine Learning, pp. 203-262222 2017.
Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning. In International Conference on Machine Learning, pp. 551-560, 2020.
Yu Bai, Tengyang Xie, Nan Jiang, and Yu-Xiang Wang. Provably efficient Q-learning with low switching cost. International Conference on Neural Information Processing Systems, pp. 8004-8013, 2019.
Yu Bai, Chi Jin, and Tiancheng Yu. Near-optimal reinforcement learning with self-play. Advances in Neural Information Processing Systems, 33, 2020.
Amir Beck. First-order Methods in Optimization. SIAM, 2017.
Daniel Bernstein, Christopher Amato, Eric Hansen, and Shlomo Zilberstein. Policy iteration for decentralized control of Markov decision processes. Journal of Artificial Intelligence Research, 34: 89-132, 2009.
Craig Boutilier. Planning, learning and coordination in multiagent decision processes. In Conference on Theoretical Aspects of Rationality and Knowledge, pp. 195-210. 1996.
Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near- optimal reinforcement learning. Journal of Machine Learning Research, 3(Oct):213-231, 2002.
10

---

Under review as a conference paper at ICLR 2022
Noam Brown and Tuomas Sandholm. Superhuman AI for heads-up no-limit poker: top professionals. Science, 359(6374):418 424, 2018.
Libratus beats
Sébastien Bubeck and Thomas Budzinski. Coordination without communication: Optimal regret in two players multi-armed bandits. Conference on Leurning Theory, pp. 916-939, 2020.
Lucian Busoniu, Robert Babuska, and Bart De Schutter. A comprehensive survey of multiagent reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), (8(2):156-172 2008.
Nicolo Cesa-Bianche Bianchi and Gábor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
William Chang, Mehdi lafarnia-Jahromi. and Rahul Jain. Online learning for cooperative multi-player multi-armed bandits. arXiv preprint arXiv:2109.038/5 2021.
Caroline Claus and Craig Boutilier. The dynamics of reinforcement learning in cooperative multiagent systems, AAAI Conference on Artificial Intelligence, 1998(746-752):2. 1998.
Johanne Cohen, Amélie Héliou, and Panayotis Mertikopoulos, Learning with bandit feedback in potential games. In Proceedings of the I International Conference Neural Information Processing Systems, pp. 6372-6381, 2017.
Ashok Cutkosky and Francesco Orabona. Momentum- based variance reduction in non-convex SGD. Advances in Neural Information Processing Systems, 32:15236-15245, 2019.
Constantinos Daskalakis, Dylan Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. Advances in Neural Information Processing Systems, 33, 2020.
Damek Davis and Dmitriy Drusvyatskiy. Stochastic subgradient method converges at the rate O(k-l/4) weakly convex functions. arXiv preprint arXiv:/802.02998. 2018.
Dmitriy Drusvyatskiy and Courtney Paquette. Efficiency of minimizing compositions of convex functions and smooth maps. Mathematical Programming. 178(1):503-558, 2019.
Abhimanyu Dubey and Alex Pentland. Provably efficient cooperative multi-agent reinforcement learning with function approximation. arXiv preprint arXiv:2103.04977 2021.
Jakob N Foerster, Yannis M Assael, Nando de Freitas, and Shimon Whiteson. Learning to com- municate with deep multi-agent reinforcement learning. In International Conference on Neural Information Processing Systems, pp. 2145-2153, 2016.
Dylan J Foster, Zhiyuan Li, Thodoris Lykouris, Karthik Sridharan, and Éva Tardos. Learning in games: Robustness of fast convergence. In International Conference on Neural Information Processing Systems, pp. 4734 4742, 2016.
Yoav Freund and Robert E Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1 1999.
Drew Fudenberg, Fudenberg Drew, David K Levine, and David K Levine. The Theory of Learning in Games, volume 2. MIT press, 1998.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-ordes methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341 1-3688, 2013.
Hongyi Guo, Zuyue Fu, Zhuoran Yang, and Zhaoran Wang. Decentralized single-timescale actor- critic zero-sum two-player stochastic games. In International Conference Machine Learning, pp. 3899-3909, PMLR, 2021.
Thomas Dueholm Hansen, Peter Bro Miltersen, and Uri Zwick. Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor. Journal of the ACM, 6011):1-16. 2013.
11

---

Under review as a conference paper at ICLR 2022
Sergiu Hart and Andreu Mas-Colell A simple adaptive procedure leading correlated equilibrium. Econometrica, (8(5):1 2000.
Sergiu Hart and Andreu -olell. Uncoupled dynamics do not lead to nash equilibrium. American Economic Review, 93(5):1830-1535 2003.
Yu-Chi Ho. Team decision theory and information structures. Proceedings of the IEEE, 68(6): 644-654, 1980.
Junling Hu and Michael P Wellman. Nash Q-learning for general-sum stochastic games. Journal of Machine Learning Research, 4(Nov):103--1069, 2003.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(4), 2010.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is Q-learning provably efficient? In International Conference on Neural Information Processing Systems, pp. 1866-4874 2018.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in Neural Information Processing Systems, 26:315-324 323, 2013.
Dileep Kalathil, Naumaan Nayyar, and Rahul Jain. Decentralized learning for multiplayer multiarmed bandits. IEEE Transactions on Information Theory, 60(4):2331-2344 2014.
Soummya Kar, José M. F. Moura, and H. Vincent Poor. QD-learning: A collaborative distributed strat- egy for multi-agent reinforcement learning through consensus innovations. IEEE Transactions on Signal Processing, (7): 10):11144 148-1862, 2013.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1412.6912 2014.
Robert Kleinberg, Georgios Piliouras, and Éva Tardos. Multiplicative updates outperform generic no-regret learning in congestion games. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, pp. 533-542, 2009.
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. International Journal of Robotics Research, 32(11))1288-1274, 2013.
Lior Kuyer, Shimon Whiteson, Bram Bakker, and Nikos Vlassis. Multiagent reinforcement learning for urban traffic control using coordination graphs. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp- 656-671. Springer, 2008
Lifeng Lai, Hai Jiang, and H Vincent Poor. Medium access in cognitive radio networks: A competitive multi-armed bandit framework. In Asilomar Conference on Signals, Systems and Computers, pp. 98-102. IEEE, 2008
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Martin Lauer and Martin Riedmiller. An algorithm for distributed reinforcement learning in coopera- tive multi-agent systems. In International Conference Machine Learning, 2000.
Stefanos Leonardos, Will Overman, Joannis Panageas, and Georgios Piliouras. Global convergence of multi-agent policy gradient in markov potential games. arXiv preprint arXiv:2106.0/996 2021.
David S Leslie and Edmund J Collins. Individual Q-learning in normal form games. SIAM Journal on Control and Optimization, 44(2):495-o 514, 2005.
Xiaoyu Li and Francesco Orabona. high probability analysis of adaptive SGD with momentum. arXiv preprint arXiv:2007.14294 2020.
Michael L Littman. Markov games framework for multi-agent reinforcement learning. In Machine Learning, pp. 157-163. 1994.
Michael Littman. Friend-or-Foe Q-learning in general-sum games. In International Conference on Machine Learning, pp. 322-328, 2001.
12

---

Under review as a conference paper at ICLR 2022
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. A sharp analysis of modell-based reinforcement learning with self-play. In International Conference on Machine Learning. 2021.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed cooperative environments. Advances Neural Information Processing Systems, 30:6379-6390, 2017.
Haihao Lu. "Relative continuity" for non- -on-Lipschitz nonsmooth convex optimization using stochastic (or deterministic) mirror descent. INFORMS Journal on Optimization, 1(4):288-303, 2019.
Weichao Mao, Kaiqing Zhang, Ruihao Zhu, David Simchi-Levi, and Tamer Başar. Near-optimal regret bounds for model-free RL in non-stationary episodic MDPs. In International Conference on Machine Learning, 2020.
Jason R Marden, Gürdal Arslan, and Jeff S Shamma. Cooperative control and potential games. IEEE Transactions Systems, Man, and Cybernetics, Part B (Cybernetics), 39(6): (116)))393-1407 2009a.
Jason R Marden, Peyton Young, Gürdal Arslan, and Jeff's Shamma. Payoff-based dynamics for multiplayer weakly acyclic games. SIAM Journal on Control and Optinization, 48(1):373-396 2009b.
Pierre Menard, Omar Darwiche Domingues, Xuedong Shang, and Michal Valko. UCB momentum Q-learning: Correcting the bias without forgetting. arXiv preprint arXiv:2103.0133 2021.
Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press, 2017.
Dov Monderer and Lloyd S Shapley. Potential games. Games and Economic Behavior, 14(1): 124-143, 1996.
Jean-Jacques Moreau, Proximité et dualité dans un espace hilbertien. Bulletin de Société mathéma- fique de France, 93:273-299, 1965.
Ashutosh Nayyar, Abhishek Gupta, Cedric Langbort, and Tamer Başar. Common information based Markov perfect equilibria for stochastic games with asymmetric information: Finite games. IEEE Transactions on Automatic Control, 59(3):555-570, 2013a.
Ashutosh Nayyar, Aditya Mahajan, and Demosthenis Teneketzis. Decentralized stochastic control with partial history sharing: common information approach. IEEE Transactions on Automatic Control, 58(7): 1644-168888 2013b.
Gergely Neu. Explore no more: Improved high-probability regret bounds for non-stochastic bandits. Advances in Neural Information Processing Systems, 28:3168-3176, 2015.
Frans A Oliehoek, Matthijs TJ Spaan, and Nikos Vlassis. Optimal and approximate Q-value functions for decentralized POMDPs. Journal of Artificial Intelligence Research, 32:289-355. -333, 2008
Huy Xuan Pham, Hung Manh La. David Feil-Seifee and Aria Nefian. Cooperative and distributed reinforcement learning of drones for field coverage. arXiv preprint arXiv:1803.07250, 2018.
Goran Radanovic, Rati Devidze, David Parkes, and Adish Singla. Learning to collaborate in Markov decision processes. In International Conference on Machine Learning, pp. 5261-551129 5261-5 2019.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shi- mon Whiteson. QMIX: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference Machine Learning, pp. 4295-4925 4304. PMLR, 2018.
Sashank Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In International Conference on Machine Learning, pp. 314-323. PMLR, 2016.
Tim Roughgarden. Intrinsic robustness of the price of anarchy. In ACM Symposium on Theory of Computing, pp. 513-522, 2009.
13

---

Under review as a conference paper at ICLR 2022
Muhammed O Sayin, Kaiqing Zhang, David S Leslie, Tamer Başar, and Asuman Ozdaglar. Decen- tralized Q-learning in zero-sum Markov games. arXiv preprint arXiv:2106.02748, 2021.
Shai Shalev-Shwarzz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv: 2016.
Lloyd S Shapley. Stochastic games. Proceedings of the National Academy of Sciences, 39(10): 1095-1100, 1953.
Aaron Sidford, Mengdi Wang, Lin Yang, and Yinyu Ye. Solving discounted stochastic two-player games with near-optimal time and sample complexity. In International Conference Artificial Intelligence and Statistics, pp. 2992-3002. PMLR, 2020.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game Go with deep neural networks and tree search. Nature, 529(7587):484 489, 2016.
Kyunghwan Son, Daewoo Kim, Wan Kang, David Earl Hostallero, and Yung Yi. Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In International Conference on Machine Learming, pp. 5887-5896. PMLR, 2019.
Vasilis Syrgkanis and Eva Tardos. Composable and efficient mechanisms. In ACM Symposium on Theeory of Computing, pp. 211 211-220, 2013.
Vasilis Syrgkamis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regularized learning in games. In International Conference on Neural Information Processing Systems, pp. 2989-2997, 2015.
Yi Tian, Yuanhao Wang, Tiancheng Yu, and Suvrit Sra. Online learning in unknown Markov games. International Conference on Machine Learning, 2021.
Katja Verbeeck, Ann Nowé, Tom Lenaerts, and Johan Parent. Learning to reach the Pareto optimal Nash equilibrium team. In Australian Joint Conference Artificial Intelligence, pp. 407-418. Springer, 2002.
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, al. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature, 575(7782):350-354 2019.
Yannick Viossat and Andriy Zapechelnyuk. No-regret dynamics and fictitious play. Journal of
Economic Theory, 148(2):825-84)) 2013.
Xiaofeng Wang and Tuomas Sandholm. Reinforcement learning to play optimal Nash equilibrium in team Markov games. Advances Neural Information Processing Systems, 15:1603-1610, 2002.
Ying Wang and Clarence W de Silva. A machine-learning approach to multi-robot coordination. Engineering Applications of Artificial Intelligence, 21(3):70-444, 2008
Chen-Yo Yu Wei, Yi-Te Hong, and Chi-Jen Lu. Online reinforcement learning in stochastic games. In International Conference on Neural Information Processing Systems. pp. 1994-5004, 2017.
Chen-Yo Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horize competitive Markov games. Annual Conference on Learning Theory, 2021.
Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum simultancous- move Markov games using function approximation and correlated equilibrium. In Conference Learning Theory, pp. 3674-3682, 2020.
Bora Yongacoglu, Gürdal Arslan, and Serdar Yüksel. Learning ccam-optimallity for decentralized stochastic control and dynamic games. arXiv preprint arXiv: /903: 058122 2019.
Kaiqing Zhang, Zhuoran Yang. Han Liu, Tong Zhang, and Tamer Başar. Fully decentralized multi- agent reinforcement learning with networked agents. In International Conference on Machine Learning, pp. 5872-5881, 2018
14

---

Under review as a conference paper at ICLR 2022
Kaiqing Zhang, Erik Miehling, and Tamer Başar. Online planning for decentralized stochastic control with partial history sharing. American Control Conference, pp. 3544-3550. IEEE, 2019.
Kaiqing Zhang, Sham Kakade, Tamer Başar, and Lin Yang. Model-based multi-agent RL in zero-sum Markov games with near-optimal sample complexity. Advances in Neural Information Processing Systems, 33, 2020a.
Kaiqing Zhang, Zhuoran Yang. and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pp- 321-384, 2021a.
Runyu Zhang, Zhaolin Ren, and Na Li. Gradient play in multi-agent markov stochastic games: Stationary points and convergence. arXiv preprint arXiv:2106.00/ 18, 2021b.
Siqi Zhang and Niao He. On the convergence rate of stochastic mirror descent for nonsmooth nonconvex optimization. arXiv preprint arXiv:1806. 04781, 2018.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference-advantage decomposition. Advances in Neural Information Processing Systems, 33, 2020b.
Yulai Zhao, Yuandong Tian, Jason D Lee, and Simon S Du. Provably efficient policy gradient methods for two-player zero-sum Markov games. arXiv preprint a:Xiv:2102.08803, 2021.
15

---

Under review as a conference paper at ICLR 2022
Supplementary Materials for "Decentralized Cooperative Multi-Agent Reinforcement Learning with Exploration"
A DETAILED DISCUSSIONS ON RELATED WORK
A common mathematical framework of multi-agent RL is stochastic games (Shapley 1953), which is also referred to as Markov games. Early attempts to learn Nash equilibria in Markov games include Littman 1994] 200T); Hu & Wellman (2003);|Hansen Hansen et al. (0133) but they either assume the transition kernel and rewards are known, or only yield asymptotic guarantees. More recently, various sample efficient methods have been proposed (Wei et al. 2017 Bai & Jin 2020 Sidford
ct al., 2020 Xie et al. 2020 Bai et al. 2020 Liu et al. 2021 Zhao et al. 2021), mostly for learning in two-player zero-sum Markov games. Most notably, several works have investigated two-player zero-sum games in a decentralized environment: Daskalakis et al. (2020) have shown non-asymptoti convergence guarantees for independent policy gradient methods when the learning rates of the two agents follow a two-timescale rule. TTan et al. (202T) have studied online learning when the actions of the opponents are not observable, and have achieved the first sub-linear regret Ö(K å in the decentralized setting for K episodes. More recently, Wei et al. (202T) have proposed an Optimistic critic, and have shown a strong finite-time
Gradient Descent Ascent algorithm with a last-iterate convergence result in the decentralizeel/agnostic environment. Overall, these works have mainly focused on two-player zero-sum games. These results do not carry over in any way to the decentralized cooperative/team setting that we consider in this paper.
Another line of research has considered RL in teams cooperative games. Without enforcing a decentralized environment, [Bottilier 1996) has proposed to coordinate the agents by letting them take actions in a lexicographic order. In similar setting, Wang & Sandholm (0002 have studied optimal adaptive learning that converges to the optimal NE in Markov teams. Verbeeck et al. (2002) have presented independent learning algorithm that achieves Pareto optimal Nash equilibrium in common interest games with limited communication. These methods critically relied on communications among the agents (beforehand) or observing the teammates' actions. In contrast, the distributed Q-learning algorithm in Lauer& & Riedmiller (2000) is decentralized and coordination- free, which, however, only works for deterministic tasks, and has no con-asymptotic guarantees. In fact, developing provable decentralized RI. in teams with stochastic environment is considered as an open problem in Lauer& & Riedmiller (2000), which we address in this paper.
Another relevant work (Arslan& & Y Yüksel 2016) has shown that decentralized Q-learning can converge to Nash equilíbria in weakly acyclic games (WAGs), which cover Markov teams as an important special case. Their decentralized setting is most similar to ours in that each agent is completely oblivious to the presence the others. Later, such a method has been improved in Yongacoglu et al.) (2019) to achieve team-optimality. However, both of them require coordinated exploration phase, and only yield asymptotic guarantees. In fact, to the best of our knowledge, it is not clear if their methods will converge in polynomial time. We significantly improve their results in this respect, by explicitly showing a polynomial sample complexity upper bound. Similarly, decentralized learning has also been studied in single-stage weakly acyclic games (Marden al., 2009b) or potential games (a subclass of WAGs) (Marden et al. 2009a] Cohen et al. (017). Two contemporaneous works (Zhang al. 20216 Leonardos et al. 2021) have studied gradient play in Markov potential games, which also cover Markov teams. Nonetheless, they do not consider the aspect of exploring the unknown environment, one of the key issues in RL, and/or have to assume perfect knowledge of the environment.
In general-sum normal-form games, a folklore result is that when the agents independently run no- regret learning algorithms, their empirical frequency of plays converges to the set of coarse correlated cquilibria (CCE) of the game (Hart & Mas-Colell 2000). However, a CCE may suggest that the agents play obviously non-rational strategies. For example. Viossat & Zapechelnyuk (2013) have constructed an example where a CCE assigns positive probabilities only to strictly dominated strategies. On the other hand, given the PPAD completeness of finding Nash equilibrium, convergence to NE seems hopeless in general. An impossibility result (Hart & Mas-Colell 2003) has shown that uncoupled no- regret learning does not converge to Nash equilibrium in general, due to the informational constraint
16

---

Under review as a conference paper at ICLR 2022
that the adjustment in an agent's strategy does not depend the reward functions of the others. Hence, convergence to Nash equilibria is guaranteed mostly in games with special reward structures, such two-player zero-sum games (Freund & Schapire 1999) and potential games (Kleinberg et al. 2009
Cohen et al., 2017).
Efficient exploration has also been widely studied in the literature of single-agent RL, see, e.g..
Brafman & Tennenholtz (2002); Jaksch et al. (2010): Azar et [ (2017); Jin et al. (2018); A garwal
al. (2020). For the tabular episodic setting, various methods (Azar et al. 2017] Zhang et al. 2020b
Menard et al. 2021) have achieved the sample complexity of O S AA/4 A/s"), which matches the
information theoretical lower bound. When reduced to the bandit case, our problem is also related to the cooperative multi-armed bandit (MAB) problem (Lai et al.) 2008 Avner & Mannor [2014] Kalathil et al. 2014 Bubeekk & Budzinski, 2020), originated from the literature of cognitive radio networks, The difference is that, in cooperative MAB, each agent is essentially interacting with an individual copy of the bandit, with an extra caution of action collisions; in formulation, the reward function is defined on the Cartesian product of the action spaces, which allows the agents to be coupled in more general forms. A concurrent work (Chang et al. (021) has studied cooperative multi-player multi-armed bandits with information asymmetry, which parallels our matrix team setting. Nevertheless, (Chang et al., 202I) requires stronger conditions than our decentralized setting as their algorithm relies on playing a predetermined sequence of actions.
B DISCUSSIONS ON MARKOV POTENTIAL GAMES
An N-player episodic Markov potential game can be described by a tuple G (N, H. (A') 1:=1: [r P. P). where (1) N = (1.2...., N is the set of agents; (2) H E N. is the number of time steps in each episode; (3) S is the finite state space; (4) A' is the finite action
space for agent E N; (5) r' [H] x S x A + [0.1] is the reward function for agent i, where A X N A is the joint action space; and (6) P : [H] S x A - A(8) is the transition kernel. We remark that the agents could have different reward functions, but the reward that an agent receives also depends on the joint actions of all the agents.
We define the space of policies for agent by IT' = {x² [M] x S + A(A)). The joint policy space II' II', For a joint policy π II, and for any h E [H]. e S, and A. we
denoted by II x
define the value function for agent i as:
v ( def E P (l
Σ rir
s/
(4)
We call G a Markov potential game if for every h E [H] and E S, there exists function db II + R. such that
( 11 - (1("" .- = ( (((ta=)))))) r/ in (i)))))))))))))))))))
for all i E N. n² II and - - E II- Such a definition extends the normal-form potential games (Monderer & Shapley 1996) to state-dependent games. In words, D can be considered as potential function such that any unilateral change in an agent's policy causes equal amount of change to the potential function and its own value function. It is known that every Markov potential game possesses at least one deterministic Nash equilibrium.
We can easily see that Markov teams are special case of Markov potential games, where the potential function is simply the team value function. Since all the agents are correlated by a single potential function in Markov potential games, the process of learning Nash equilibria reduces to searching for the local optima of the potential function, which is exactly the core idea behind our design of Algorithm| for Markov teams. One potential games, and hence the same sample complexity bounds from Theorems [ and 4 also hold in such broader class of games.
that Lemmas 4 and [5 immediately generalize to Markov
17

---

Under review as a conference paper at ICLR 2022
C AUXILIARY LEMMAS
C.I PROPERTIES OF THE BREGMAN DIVERGENCE
Let w X' - I be continuously differentiable mirror map that is 1-strongly convex on X. where is non-empty closed convex set. In this paper, we specifically take w as the L'-induced regularizer, i.e., w(x) 2 || although the following result holds more generally. Let (w. y)
w(x) wly) (zz y, (yy))) be the w-induced Bregman divergence.
Lemma 2. (Beck 2017 Section 9.2.1). The Bregman divergence satisfies the following properties:
(a) Three-point identity:
(=(x,y) + (y, Dw = (Vw(2) Vw(y), y), H, X.
(b) Suppose xxx) is convex and x argmin {f((x) + Du (z, 2)} for some > O, we have
xEN
((x) + Dw,, 2 (2t) - Du (zt,2) + - Dw (I, v/ E X.
a
a
C.2 PROPERTIES OF THE GRADIENT MAPPING
Lemma 3. (Agarwal et al. the gradient mapping as
2021 Proposition B.I). Let : X + IR be a 8-smooth function. Define
(x)
xTxx (x + V)(x)) x))
The update rule for projected gradient ascent is x+ = + (z)) If (=)) S E, then (TVL(x*) S +1)
max -+1EX,ME
D AN EXTENDED DISCUSSION OF SECTION 3
We first introduce few more notations for ease of presentation. Recall that AA B + |0, 1] the
expected value of the reward function, i.e., r(a, b) = fo' ax))).( We further let Q E R x R be the matrix of expected rewards. That is, given a mixed strategy pair æ (H, the corresponding expected reward for the players can be denoted by V(T)) = V(n, v) [rxa[r(a, b)] μ Qv, where a ~ μ and b v. The function V is also called the value function.
In certain circumstances, it is more convenient to work with costs instead of rewards. We let 1: A x B >> J0, 1] be the expected cost function such that I(a, b) Let M = AAxB Q be the matrix of expected costs, where 1 LAx B is an all-one matrix of the size A x B. Similar to the value function V, we define L(T)- = Luu, v) del [[a, b)] = 4 M as the corresponding loss function.
r(a, b), V(a, b) E x B.
Our definition an approximate Nash equilibrium (Definition T can be easily reduced to the matrix team setting as follows.
Definition 2. (E-approximate NE for matrix teams). For e O, strategy pair (n² v²)) is E-approximate Nash equilibrium for a matrix team if (p" v²) 2 V(p,v") -, vu E A(A), and V(u", v²) Z V(u", (v)" e, Vv E A(B).
In the following, introduce the definition of an approximate stationary point.
Definition& 3. (s-approximate stationary point). A strategy pair π (H,P) A(A) A(B) is a (first-rder)) 8-approximate stationary point for the function V A(AA) x ABB) - R if ffr any
81 E ARA, &2 E RB such that 1|0:1/2 + || 2/222222 < 1, + & E ((A), and + &g E AB)), it holds that
VV + + VV Se.
18

---

Under review as a conference paper at ICLR 2022
Intuitively, is stationary point if the value function V cannot increase by more than along any direction that lies in the intersection of the strategy simplex and the neighborhood of л. Comparing the definitions of an approximate stationary point with an approximate NE easily leads to the following observation.
Lemma 4. Let Leta*= = (H,," ,v*) be an E-approximate stationary point of the value function V for some & E>0, O. Then, the strategy pair vV)) is a <2e-approximaae Nash equilibrium of the corresponding matrix team.
All missing proofs of this section are deferred to Appendix E for clarity. With Lemma learning a NE of the team reduces finding a stationary point of the corresponding value function, equivalently, the loss function. In what follows, we focus on the loss function L for reasons that will be clear soon. Numerous SGD methods have been proposed to find stationary point in stochastic non-convex optimization (Ghadimi & Lan 2013). For generality, we write our gradient step as an Online Mirror Descent (OMD) update with L regularization to search for the stationary point. The standard OMD algorithm performs the following update rule at each iteration:
(VL())), + (a, (
Ft41 f- argmin ZEX
(5)
04.
where X' A(A) ((B) is the feasible region, (Ix,) is an estimator of the subgradient of L at at, or >> 0 is the stepsize, w : X + R is a 1-strongly convex and continuously differentiable regularizer, and Dw (x) w(xr (1r) (Vu (Ix) x 2z) is the Bregman divergence induced by the regularizer w.
The following nuance in the general OMD update requires some attention before we directly apply existing results. Since the optimization objective L is a function of π E (AA) x A ABB), existing methods typically proceed in a centralized way and manipulate π as a whole. In contrast, in our decentralized setting, the strategies μ and v need to be updated separately and independently. However, such a nuance does not exist with SGD. Specifically, if we instantiate w as an i.d-induced
regularizer, i.c. w(x) = 1/ || [|: then our OMD procedure is equivalent to projected SGD (Lattimore
2
& Szepesvári 2020 Example 28.2). In this case, the Bregman divergence simplifies to (I,
Fe 2
The update rule in (5) can hence be simplified
T44 + 1xx (I-a
where (x) denotes the Euclidean projection of onto X. We then point out the following simple fact, which states that conducting projected SGD on the optimization variable и = (H4, v) as a whole equivalent to running the same algorithm on each component of independently.
Lemma 5. Let ग = (n, v) be a strategy pair, and let L = (V,L(=), (T)( be an arbitrary (not necessarily unbiased) gradient estimator of L at ग. Let - = (TTA)xx00(F=-V__.. result of a centralized gradient update step with stepsize a > O, and let μ² = [ل - a ((T)) and + [I (v a a (TT)) be the results of applying the gradient update each agent's 's strategy independently. Then, - (1tt, v+)
be the
Therefore, it suffices to only analyze the centralized OMD algorithm with L regularization, as it equivalent to decentralized SGD. Since our algorithm is essentially performing gradient descent instead of ascent, we choose the loss function L as our optimization objective.
We now turn to the gradient estimator A (z). Existing stochastic non-convex optimization meth- ods (Ghadimi & Lan 2013) typically assume the existence a stochastic oracle: Given any input I E X. the oracle outputs a random vector L 5 that is an unbiased estimator of the gradient and has bounded variance. More specifically, it is assumed that for any x E X, Eg L E)] E aL(x), where (L(z) (z) is the subdifferential set of L at æ. and E3 L(, E)IB < o² for some constant p > 0. The latter condition is also called the p-stochastic continuity of L (Lu 2019). Such an oracle does not come for free in our problem, as the agents are faced with bandit feedback and can only observe
' is a random variable that is used to explicitly show the randomness of the estimator. When there no possibility of ambiguity, we suppress the & term and simply write the estimator as V (z))..
19

---

Under review as a conference paper at ICLR 2022
the reward associated with the selected action pair. To deal with this challenge, at the t-th round of the problem, let agent construct biased gradient estimator V, Tu in the form of
1 - Re Ifa ii.Vie A, He,i +
V pa
where Pr.i is the probability that agent takes action E AA in round t, and y > O is a constant specified in Algorithm The biased gradient estimator Le for agent 2 is constructed similarly. We can see that the estimator we use tends to underestimate the actual cost. Such technique is called Implicit e eXploration (Neu 2015) in the literature, and is widely used to prove high-probability regret bounds in multi-armed bandits, an objective that we do not pursue in this paper.
Our analysis of Algorithm 1 relies on showing that the biased estimator L we constructed has bounded variance, and is upper bounded by the actual gradient in expectation, which satisfies the oracle requirements in a weaker sense. We can then analyze the non-asymptotic convergence behavior stationary point. For generality, the proof we present in this paper follows
of our SGD algorithm the analysis of general proximal point method (Davis & Drusvyatskiy 2018 Zhhan & He 2018). by showing that the gradient of the Moreau envelope converges although simpler proofs for the convergence of SGD in non-convex optimization exist. Finally, we invoke Lemma 4o conclude that the stationary point we find close to a NE,
E
MISSING RESULTS IN SECTION 3 AND APPENDIX D
E.1 PROOF LEMMA
Proof. Let '- = (H", ,1*) be an e-approximate stationary point of the value function V. For any strategy μ A(A).
v(u,v") V(*", (p-p")) (n- = V2. 1 -/ VT) ( 22,
1 (m - n11 112 S.
where the last step follows from the e-approximate stationarity of x* and similar argument can show that V(n*, v) - V(*",v") v2s, Vu E A(B). Therefore, (M*, is a2saapproxi NE of the matrix team.
E.2 PROOF OF LEMMA 5
Proof. Let ग = (H, v). First, notice that ग - aV = (u - aVL,(T), - -(v)))))) Then, by the definition of the Euclidean projection,
π a.))(())
=I(A(A))A(B))
2
argmin ((A(()))(B)
T -T- -=1
(Iu-aPnl(*t) p
+ au-avaL(m - =22 122
argmin =(EA(A)
argmin m1EA(A) jn-ov x1 argmin m2EA(88)
1 a v I.TTT 122
=ITA(A) (M (p-avp((m) + +IA (u (v-aV.L(m)
=1- + +.
This completes the proof of the lemma.
E.3 PROOF OF LEMMA 7
Proof. Our proof relies on the smoothness of the function L and a gradient mapping property (Proposition B.1 in Agarwal et al. (202T), also reproduced Lemma in our Appendix C for
20

---

Under review as a conference paper at ICLR 2022
completeness). First, recall the definition that 2 argmin,gx** [L(=) + XD 2)), and notice that the function [(2 + (2, (A -sstrongyyy convex in for any fixed x E X. We know from Lemmaßitha that
I(x) - [T(.) + ADw (+) (A (x,,
Therefore, we can derive that
L(x) - L(Ø) (((((())=[(() - ( + + (A ())
+ 2(1 - (D (G,
=(^ - 1) x =11
is easy to verify that [xx) is an (A+ B) -smooth function, in the sense that VL(x)) VL(y)ll2 v
(A + B) || yl12. We can hence invoke Lemma
3 and conclude that æ an approximate stationary
point, such that
(VL((x) < 2(2Amax + AIVE
max =+
V1 V
E.4 PROOF THEOREM
Proof. From Lemma we know that it suffices to analyze Aggrrthhm[[rrmm a centralized perspective, because running projected gradient descent on the joint strategy x (H, v) as a whole is equivalent to updating each agent's 's strategy and individually. To show that x, (H+, is approximate Nash equilibrium, we also know from Lemma that the problem reduces to showing its approximate stationarity with respect the loss function L.
For generality, the proof we present in this paper follows the analysis of a general proximal point method (Davis & Drusvyatskiy 2018 Zhang & He 2018), although many simpler proofs given
in the literature to show the convergence of SGD in non-convex optimization. To facilitate the analysis, we first introduce the following definition of the Bregman-Moreau envelope (Moreau 1965
Drusvyatskiy & Paquette 2019 Davis & Drusvyatskiy 2018 Zhang & He 2018).
Definition 4. (Bregman-Morecd envelope). For À > O, given a function L X + RR and a vector E X, the Bregman-Moreau envelope is defined as
der min [(x)+ 1 1
Lx(2)
#EX
The corresponding Bregman proximal operator is
L(x) + -
prox (2) det
argmin TEX
We start with the observation that a 1-weakly convex function, in the sense that L(x) + ((r) convex for w(x) = || It then follows that for any 0 < < 1, the proximal operator is well-defined and unique.
Lemma 6. (Zhang & He 2018 Lemma 2.2). Suppose L is 1-weakly convex X, and let < X 1.
Then, for any vector z E X, the function T(x) + x (w, 2) is (X-1 - (iet-11)-aa 1)-strongly convex in v. and the Bregman proximal operator proxx,1 is uniquely defined.
For simplicity of notations, in the following, we use F; = (Me, v.) E X' denote the strategy pair used by the two agents at round e [T]. For any À and X, we let
and we know from Lemma that à is uniquely defind. By the definition of the Bregman envelope, L L1/((1+41) = [( + AD (f+11, The optimality of f+41 implies that
[4)((141)) S T(O.) + XDa (D (6r, x++1)-
(6)
21

---

Under review as a conference paper at ICLR 2022
Let = (V,L. V,L)) E R4+B be the biased gradient estimator constructed by concate- nating the two players' individual estimates in Line of Algorithm | Further, let L(zz)) = (V,L(æ)), vxL(zz)) (Mr, MTT) be the actual gradient of L at It, value that do not have access to and is only used for analytical purposes. Our proof relies on a few properties of the Bregman divergence, which standard results from the literature and are reproduced in Appendix C for completeness. Setting
21, 2441.2 I
fr. a aiz, and p(x)) (VL,, x) in Lemma b)
(Appendix C
leads to
04 (VIn, Re - x141) 2 Dw (fe, F141) + Dw (1141, - Dw (ft,
Rearranging and combining 66) and 7
(1/4(1441) S ((fe) (
<L(G.) + +x(0r (VL,, 8t - xz+1) ) Du (1e41, 21) + Du (iz, x1))
=L1/a(z))+ + X (ar (ĀLe, -00:))--14))) - Dw
-D (1)+1:
=11/ + da (L fr - 21 + (at: (bLL, 2141) Du (1)41.
(8)
where the first equality is by the definition of the Bregman-Moreau envelope. The second term in can be further decomposed into
LL zz) = (VL(x)) 21)
(L - VL(x)). (. - VL(m), xi)
(9)
In the following, we bound (the expected value of) each term in separately. First, since L is 1- 1-weakly convex on X', the first term in (9) is bounded by
(VI()),, 2. x²)= S [(a)) [xx)) + 2 1 xel12 I(xe) Mxx)) + Du (10)
Second, by our construction of the biased estimator, for any E A.
Rd Ifat =a===) =1]
V M.i [t] = E
Me, +
<E
- Rg
Mat =1]
Σ Plb j) .E
1 R Mar Hor = =1]
M4g
14,
jEB
Σ Pbb = f)-
V Vu,L((a))
JEB
where here E..] denotes the conditional expectation given the history of both agents up to the current
round, and V [(xt) denotes the i-th entry of the actual gradient V (xx.). A similar result holds
for agent 2, that is, E[ < (eyL((z) Vj e B. Hence, we know that E E L, [L(x,)] = O, where = denotes element- dlement-wise comparison. Since &, lies in the the domain X' = A x ABB), it is a non-negative vector, i.e., &, 2 O. We can therefore upper bound the expected value the second term in 99 by
E O E (VL, (Z,)),, 2,)1 S
(11)
Finally, recalling that D, (Me, 1t), we decompose the third term in 9 into two parts,
3 = - LV VI(())) m²) (vx) V pt) + (v.L(z.)- V. vt).
In the following, we show an upper bound of the first part, and the proof for the second part follows similarly. Using the definition of the inner product,
(())
V TpTa,pu (b)
Σ (V - -uust) pe,i
(12)
tEA
where He, is the i-th component in the vector Nr. Again, by taking the expectation of the biased gradient estimator,
1 Rr
1 Re T(a = i} P4,i
E E
E
T(as 13
Σ
P(b. =j) . E
Mess +
JEB
((i.j)Me.
Σ Vi.j
Me, +
JEB
22

---

Under review as a conference paper at ICLR 2022
Plugging it back to (12), and recalling the definitions that vxL(x,) Mv and Va,a((zi) EjeB (2. j)r.. we have that
1(i,5)mt.
E (V (v)(( Vil
= =E
Σ
(ii.))es
Evea
Ve.à
Ma,
Me, +
iEA
JEB
jEB
ΣΣ
((,, (1 (1-
He,
He,, + +
iEAEEB
ΣΣ ((i,j)vt.
7
7/M4.
iEAJEB
ΣΣ 1(1,))e257
iEAjEB
<Ay,
where the first incquality is due to 1+7//e, 1, and the second incquality uses the facts that ((i,j)
1, Vi E A, E B and EJEB Mt,j 1. A similar argument shows that E (v.L Vetn, uz)
By. Combining the two parts, we conclude that the third term in 9 can be bounded by
-3 E(L VL(x,), ax)] S (A + B)y S 2Amax7.
(13)
From (9) we know that inequalities TTp. T. and (13) together can upper bound the expected value of the second term in (8) Finally, to bound the third term in (8). we apply Young's 's inequality and obtain almost surely that
v Le, vt. - x0411 > Du (11+1, are (V x1+1)
1
||
1
2
1
(1 R1) II =
(1 RI = =s}
a
2
11
2 ai
Σ IEA
2
(Me,r + 7)2
(vr.s + 77²²
JEB
A am
(14)
72
where the last step holds because (Mr. + 7)² > 72, and (1 R.) = i} < 1 almost surely.
Substituting (IO). (3). and 14) back to (8) we finally conclude that
[[ S ([L1/x(a1) + Aa, (I(+)) L(x,) + ( xx) + 2A maxx))) 7)] + Amax
722
Rearranging, taking the sum from L= = to T, and telescoping leads to
Σ [(a)(((z)) L(e.) (u
Amax
E ((Li)A(Z1) 41/x -11x(((71)11))) 2A
Σ
Σ
2 ai
a2
72
1=1
t=1
T
T
1 x + 2A
Amax
a3
+
Σ
a
(15)
722
1=1
t=1
where in the last step we used the fact that 0 S [1/x(x) 11, Vo E E. In the following lemma, we show that bounding the LHS of (15) is sufficient to obtain an approximate stationary point.
Lemma 7. Let prox1/X.1. (x) with X 1. For any E 0, if [(x) L(a) Da ( S e, then
x is a 2(2A +NVE
approximate stationary point of the value function V.
VX
Dividing both sides of the inequality by Σ at, we obtain that
Ei Bla(((a) L(te) - D (2t,
Auge
7 E1= of
<
+ 2Amax7
(16)
Σl
A ET 11=1 at
23

---

Under review as a conference paper at ICLR 2022
Recall that in Line 7 of Algorithm 1 the two agents uniformly sample time index from {1...., ... T using a common random seed. Let z; = (1z, 1/) be the output of the algorithm. Then, we can that the LHS of (T)) is equivalent to [[ L(Ø,) ( 27)], because we assign equal values to the step sizes 0t-- Plugging back the parameter values at -T43/4 and y 1/4, and letting = yields,
E (
(u x,)] S 4. 1/4
Together with Lemma we can see that x; is a 1 / appoo-ipoo stationary point of V in expectation. Finally, invoking Lemma we can conclude that 2 is an 16 / approximate Nash equilibrium in expectation. In other words, to obtain an e-approximate NE, suffices to use (AA samples.
E.5 PROOF OF THEOREM 2
We first describe more explicitly the new variance-reduced algorithm that the agents are using, which has been skipped in the main text due to space limitations. Again, we only illustrate the algorithm for agent 1, as its counterpart for agent is symmetric.
Similar to vanilla SGD (with no variance reduction) in Algorithm 1 agent maintains a probability distribution 14 over its action space for each time step E [T) Such a distribution is uniformly initialized, i.e., M1.: 1/A, Vi E A. At each time step E [T). the agent first draws action as according to a perturbation of the distribution μr = 1, () to be specified later. It then executes the selected action de and observes the team reward R. Subsequently, the agent updates its probability distribution by following a variance-reduced gradient descent step.
The gradient update rule that Appendix F as it can be considered as solution to a standard constrained optimization problem on its own. Specifically, in Appendix | we present (projected) stochastic gradient descent algorithm that finds stationary point in constrained smooth non-convex optimization at rate of O(1 O(1/T)/3), Our method is straightforward extension of the STOchastic Recursive Momentum (STORM) algorithm proposed in Cutkosky & Orabona (2019), which uses momentum-based approach reduce the variances in SGD.
and its convergence analysis are presented independently in
is important note that we rely on a non-adaptive variant of the STORM algorithm. In the original STORM (Algorithm 1 Cutkkkkk & Orabona (2019)), the adaptive step size T) is calculated in a data-dependent manner (using knowledge of f= ll) []). This ordinarily a desired property, as it alleviates the need of manual parameter tuning, and also finds wide applications in heuristic methods like Adam (Kingma & Ba 2014). However, such adaptivity breaks our decentralized paradigm, because the agents update the step sizes using the local samples, and hence can end up with different step size values. This breaks the equivalence (between centralized and decentralized SGD) that we established in Lemma 5] which critically relies equal step size values among all agents. Consequently, we need to refer to a non-adaptive variant of STORM (Cutkosky & Orabonal 2019 that replaces the data-dependent values with universal upper bound
Finally, to prove Theorem 2 we only need to instantiate the various notations (Fi, Vf. and { of Appendix F in the context of the matrix team problem, and verify that all the assumptions in Appendix F are indeed satisfied. Then, we can complete the proof by invoking the convergence guarantee of Theorem 6 from Appendix [F] It is easy to see that F; represents the loss function T. in Section 3, and the random variable & is associated with the action drawn at time step t. The notation f deserves more commentary. To ensure that the bounded variance assumption from Appendix F is satisfied, we cannot let the agent draw an action according to the distribution μ4, but instead according o g-greedy parameterization of bu for some > Specifically, for probability distribution μ4 at time t, the agent samples an action a, according to i. = -.. A,, where:
jo. = (1 0) + 0/A,Vi
To put it in a different way, with probability 1 - 0, the agent randomly selects an action ac- cording to the distribution 14; with probability 0, the agent uniformly samples a, from A. The gradient estimator is instantiated with respect to the 0-greedy paramcterization as Vf(,,, = (V (c). Vff &,),, where
1- Rr Re
Pr.
24

---

Under review as a conference paper at ICLR 2022
Algorithm 4: STORM (Cutkosky & Orabona 2019) with Projections
d1 < (
for i +- 1 to do
k
?]e (w+t22)1/35
T++1 t lx( mede);
G.4- - -ch:
de1 t (f(re- Ee+1) + (1 (d (i(t,,, (t+1));
Output where T is uniformly sampled from (1....,y) T]:
We can see that ff(44, Ex) is an unbiased gradient estimator. Further, since jú. 2 0/A, E A, we also verify that V [i(e,, {x) has bounded variance. Simple calculations show that Assumption ] in Appendix F holds under the following instantiation of parameters:
2Amax and
4.22
a²
max
0
0
We can then invoke Theorem to conclude that
1
(x++) - x+)) M/3
Mo2/3 +
Chn T
Amax
11/3
E
S
77
Tk
T2/3k
T2/3
0
where 2, (J4,, 1/7 and C is some absolute constant. To ensure E
(x,+1
S it
1
suffices that T 52 ( + If we further set g2/11, then we only need = 12 112
From the gradient mapping property (Lemma 3 we know that
1 ( - x,7) S implies a e n.
approximate stationary point, where we used the condition that 7, S T in Appendix Finally, we invoke Lemma to conclude with an s-approximate Nash equilibrium after T (2(1/ poly(Amax) rounds. This completes the proof of Theorem
F SGD WITH VARIANCE REDUCTION
In this section, we present a (projected) stochastic gradient descent method with variance reduc- tion (Johnson & Zhang 2013 Allen-Zhu & Hazan 2016 Reddi al. 2016). This method proceeds by adding simple projection step to non-adaptive variant of the STOchastic Recursive Momentum (STORM) algorithm proposed in Cutkossy & Orabona (2019).
We consider generic stochastic non-convex optimization problem as follows: We are given an objective function F A - RR, and our goal to 0, where X' is the feasible region. We do not have accurate information about the function F, and can only access through a stochastic sampling oracle f(: where the random variable ç represents the "randomness" of the oracle. Throughout this section, make the following assumptions that are standard in the literature (Arjevani et al. 2019). All norms ||-|| in this section are L norms unless otherwise specified.
find point x E X C R such that V F(x) is close
Assumption 1. 1. We have access to stream of random variables Ei,..., ST, such that the gra- dient estimators are unbiased and have bounded variances: VE,,1/(a,6 = VF(x), and - VF(x)11]
- S o² for some a > for all t [n] I E X.
2. The objective F has bounded initial sub- sub-optimality and is L-smooth: F(xg) - -infinffxx F(x) < co. and F[VF(x) F())ll < || vll Vx,y E RA for some > O. The stochas- tic oracle also satisfies a mean-squared smoothness property for the same constant Lx ((,,) v fvr 12 || yl Vz,y E A with probability 1.
Our method STORM with projections is formally presented in Algorithm STORM uses a variant of momentum to reduce the variance of the gradients in SGD. It achieves an optimal convergence rate of O(1/T1/ which improves over the standard convergence rate 0(1 (11/T1/4) of SGD with no
25

---

Under review as a conference paper at ICLR 2022
variance reduction. Before present the convergence guarantee of Algorithm we first introduce few notations for ease of presentations.
For any t [T], we break the update rule into two steps:
del Dt nide, and T++1 = Ix (x((1)1)
In addition, for each & [T], define 2,μ 1xx VF(xz)) to be the next iterate updated using the full gradient V (x+), value we do not have access to. Define def de V (xx)) to the error in dz. The high-level procedure of our proof is to seek to upper bound the value
Mi (+t+--x)) x2) m and then invoke the gradient mapping property in Lemma 3 to
conclude with a stationary point. This is in contrast with the unconstrained case, where Cutkosky & Orabona (2019) directly derive an upper bound of E Σ [VF(())) the following, we start with few technical lemmas.
Lemma 8. Suppose т S +e for all E [T]. Then,
B[F(#4+1) F(x:)) <
3
|
11
7me
|| 11
167)
Proof. From the first-order optimality condition, we know that
(x- 1,+1,Te+11 (x+ m)dde) 2 0,
for any E X. Taking xy leads to
( - 2441, I++1 - 2z) + (xe - rt+1, Md)) 2 20,
which in turn implies that
1 _ || - 11+1
(Io+1 Iz, di)
(17)
1/1
follows that
(VF(2)), - 22) (de St; Fz41 vta)
|2, I1+11l 11
-(E1, 2141 - Iz)
1)1
|xt xz41 ||
1/t ||+,11 2
1
|| - 2ell
1)t
21
1
|| - x141
?t +
||
2n
2
where the first inequality uses (17). and the second inequality is due to Hölder's inequality and Young's inequality. From the smoothness of
L
B[F(x++1) SE
F(x.) + (VF(s))) #111 -x,) +
||
- xell?
2
<<
F(z:)
1
|| xe+1112
7h
||se||
L
|| - arell?
21p.
2
2
<
F(x:)
3
||
Jet1
11
77
||e.|1
(18)
Smp
2
where the last step uses 17t <
From the fact that
|| +
y/1
< 2 ||=
+ 2 1lell we know
AL
| =. ==11²= = | F++1 + Fe+1
22
<
set1ll 110111 srell
26

---

Under review as a conference paper at ICLR 2022
Rearranging the terms leads
- I Fe+1 112 $ | x2+1 1
1
| -
[xx - 1/ (zF() 11x mnde)l || - xel1?
1 ||
< (1e T (v)))) (xt (md)l
soll
2
- ||e.|l
1
||=|1 xz 11
(19)
The second inequality uses the definition of x The third step holds because the projection operator non-expansive, i.e. [x) [x)
<
20
yll. Substituting (19) back to (18) leads to
3
24 11 + 7 l 11
1 [[F(( S F(xx)
|
167
Rearranging the terms completes the proof.
Lemma 9. (Lemma 3 in
Cutkosky & Orabona 2019)). For any t [T), it holds that
[1 a,)²
E
(VI(s),))) VF(x+)) 62-1
=0;
1/-
a+)2 (VI(Ie:))) - vi((E-1, VF(()) + VF((+-1)) St-1 =0.
Th-1
Lemma 10.
(Adapted from Lemma in Cutkosky & Orabona (2019)).
With the notations in
Algorithm
4
we have
|
2
(4L2 1)(1-a0)) -61--))) oz)²
4(1 az) I22
E
2c
2 nh
0²
1x- x 11
M--1
1--1
97-1
Proof. First, observe that
E
V f {t) VI( (V(
<E
[x - &0) - VF
21
((V f(x,, 4.) ()( vF(zx) - VF(x,,1))
<E
51) - V())))-((() VF((z) -F
2E
[E
((V 32 41) ( VF( VF( E-ill
EE
|| [ (t)
VV - (F
<E
|| fx - V f(x1-1,))
(20)
By the definition of Ec. have E, de - VF(x.) -faua))4---///aaa--//aaa F((x). Therefore,
||
E
E
[V + - -
77
E
(V.(VV 4 - VF(x))) + -1
1/:-1
+ (1 - a.) 3r) Vf(x,11 VF(x;) + VF(C,,)))1
1 (1 - ox)² || ||
<
26 1- | (zt.
(x))))
2
(1 2
V
(xe,
&
VS - (F + VF (1=11)1
1/-
27

---

Under review as a conference paper at ICLR 2022
where in the last step used Lemma 9 and the simple fact that || + yyl S 2| +2 llvll applying (20) and the assumption that E
Further
f Et) - (F(aa))
I 0² leads to
(1-0))
- 21 2 ||0--112
ax)²
2c. 1h
100 +
V (i(,,
&0)
1/1
9)-11
71-1
- 0z)
2 2 a=)² I
20 nh 10
||E--1|
||
x1-1
77--1
17:-1
SE
20 nh 1-
(1-02)
||E--111
4 4 a1)² L
L
(112) xi 11 + || xz-1 11²)
7/-1
1/-1
(4I22
1)(1 )2)
|| + 4(1 ax)²
L2
SI
26 11- 11
|| || - It 11?
7--1
T]
The first inequality is due to the L-smoothness of the function f. The second inequality again uses the fact that || + =ll < 2 2|x== + 2 |lvll The last step holds because of the eenexxpansivensss of the projection operator, that is,
| xF || [x id-1)) xx 7/-
1h-1 ||
This completes the proof of the lemma.
Now, we are ready to present the convergence guarantee of Algorithm 4
Theorem 6. (Adapted from Theorem 2 in Curkosky & Orabona tions in Assumption
(2019)) Suppose the condi- bo
! are satisfied. For any b > 0, let h.
321? + 0² (7LA3) o² max (2 (326 - /64)
L ,
L3 (32 + 1/ (76*))
max (4LA)), 20 (oL) 1²
ck "))
and M = 16)F(x1) holds for Algorithm
F*) + 21 +
w²130²
In + 2). Then, the following convergence guarantee L
1
2/3 Mo2/3 Tk
E
= (xt
T
T2/3k
Proof. The proof is similar to that of Theorem 2 in Cutkosky & Orabona (2019). and we reproduce here for convenience of the reader. First, define the Lyapunov function 4; F((x)) + 321 ||eel| From Lemma I0,
we can derive that
|E++1l
|
E
1/1
(f + 1)(1 - a²+1)²
4(1 - a(+1)² L
||&
SE
2c 10 0 +
||e.|12
|| - xell
7)t
1/
<E
20 3 0 +
(4L2m)
1)(1
a2+1)
||
+
4(1
a(41)² I
| - 26/ 11?
1/-1
A
B.
C²
The first two terms A, and B, are exactly the same as the proof of Theorem 2 in Cutkosky & Orabona (2019), and we refer to their results as follows:
T
T Σ
Σ A 2k In(T + 2), and Σ t=
B. < -28
mh 1|
t=1
t=1
28

---

Under review as a conference paper at ICLR 2022
From 2 (4Lk)², we know that 7/ I
1
Further, since ac+1
onj. we have that ac+1 S
41.
dk 4
I 1 for all t, and hence C, - 4L²
| 2x 2=
Putting it all together, we obtain
I
||
c2c²
T
7 | - xel2²
In(T +
2)
+
||
32L
16L2
8mp
8
(21)
From Lemma
we know that
E [
< EE
3
||=
111
+
7 8
||
|ee+1ll2
||
16m
32T.2m
321.2m
Summing over t from 1 to T and then applying
we obtain
3
7
[
Φ1]
E
|
Fe
||
2
|1++1||
|e
167Jt
8
321.2
321,2
t=
<
c²2²
In(T
+
T
1
a++1 - It ||?
1612
167
Rearranging the terms leads
T
132²
<E 16( - 11+11 + Fe+1 - 2el1
In(T + +2)
1/:
T22
1
k36²
<16(F(x1) F*)
||||a|1]+
In(T + 2)
2T.2
T
w
w//3g²²
1.
<16(F(x1) FF)
+
In(T + 2),
2L2k
L
where the last step holds due the definition that iju wi/s Since ny is decreasing t,
T
T
T
1
- x7.
=
( - mit
2 ETr
(at+1 - xx.)
176
Dividing both sides by Tipr and recalling the definition M = 16(F(<x)) 2), we obtain
F
1/3
+ 2L
13
D
In(T
1
T
M
M(w + 02T)3
1/3
M/2/3
E
(2t
T
71
Tnr
Tk
Tk
T2133/²
1=1
where in the last step we used the fact that (a + 6/2133 < 4//3 + b2/3.
G MISSING RESULTS IN SECTION 5
G.1 PROOF OF LEMMA
In the following, we give proof for the first inequality. The second inequality can be proved via a similar argument. The desired result clearly holds for any state that is in its first stage, due to our definition of Vi .h (s) for this special case. In the following, we only need to focus on the case where Vs(s) has been updated at least once at the given state before the k-th episode.
Our proof relies on induction on & E [K]. First, the claim holds for
due to the aforementioned logic. For each step h [H] and E S, we consider the following two cases.
Case 1: (s(s) has just been updated in (the end of) episode & 1. In this case,
1 (+())) = ñ Σ
"
rn,(s, di b1:) + Then (o + bj-
(22)
29

---

Under review as a conference paper at ICLR 2022
By the definition of Vi (s) and the induction hypothesis,
R
max ID
rh + Ps A+41
P/
1++ (s)
uxth
rn (r++Pp In+PPViit? (5),
max ID 1
(23)
pxyn
Further, we define the regret
Ra (8) = Σ max pxai
Pr rh + IP h+1
(8) á
Pi x rh + Ph Ph (its)) (
(0). (24)
Since we only update the optimistic value function Vn at the end of stage, its value remain unchanged within each stage. Observe that in (24), the iterator ( takes values of episode indices that belong to the same stage. Therefore, we know that Vi+ is constant value for all i E {1....,h} n).
We can hence drop the index and simply rewrite as V h+1 when there is no ambiguity. With such formulation, one may quickly realize that bounding the regret Rt (s) reduces to analyzing matrix team problem at each state 8, as we have defined in Section B Specifically, the matrix team lasts for à rounds. For strategy pair (J,, 2) of the players, the expected reward function for this matrix team
Duxe (rh + PA V h+))(s).
Remark 2. It is worth mentioning that an additional step is required if one uses V-learning with the celebrated learning rate 0g
(Jin et al. 2018) instead to update Vn, which induces an update H+t
H+1
rule as follows:
V (5h) (1- V (sn) - ar (rn (sh, ash,an, bn) + V h41 (sh-1) + Bi),
(25)
where t is the number of times that sp. has been visited, and Br is some bonus term. In this way, V h is updated every time the state 85 is visited, and hence its value varies at each step. Drawing connections back to our approach, this will lead to a matrix team problem where the expected reward function is non- non-stationary over time. Our algorithu and analyses in Section do not directly apply to such non-stationary problem. However, in our experience, we were able to show that it is possible to carefully tune the order of the learning rate a in way such that the level of non-stationarin in non ota-stationary H+1 requires more delicate variant of Algorithm 1 Therefore, in this step, the learning rate az - treatments but does not completely fail.
Vn h can be "endured" (guarantees sublinear regret in (2 by a specifically-desiine
Since in Algorithm 2 both players essentially run an individual copy of Algorithm [ for each state, our analysis exactly reduces to the investigation of Algorithm in the matrix team problem. One may also realize that taking the average over (24) is equivalent to uniformly sample time index from (1.....f) Ai} and then take the expectation over the randomness of such a sampling process. This is exactly how we constructed the approximate Nash equilibrium in Theorem [ By applying the /haa//////// fn1/4-approximat NE in expectation after running Algorithm [ for rounds. The extra H factor comes from the additional nuance that in the problem formulation of Theorem [ the reward is assumed to be bounded in Jo, 1], while in the current matrix team problem, the rewards lie in [o, Hf.. The result above implies that for any nf A(A) that is best response of v/2- it holds that
results (and proofs) of Theorem 1 we deduce that (14) v/= is an 16H /243 max/
E T xel- (rn PA P (s) -Daf x (rn P. P (+))
16H / 243 aax /
where the expectation is taken over the randomness of t, the rewards, and the algorithm itself. The above inequality equivalent to
E R < 16H / 2A maax //4
(26)
where the expectation is only with respect the randomness of the rewards and the algorithm.
30

---

Under review as a conference paper at ICLR 2022
Remark 3. Again, would like to discuss the alternative of using V-learning with the popular learning rate a H+1 be equivalently expressed
(Jin et al. 2018). With such a learning rate, the update rule (25) of V V can
H+1
(*()) - o.H.
H
Σ 1=1
og Th 8, a b%) + Vhii (sh ($h+1) + BB
where is the number of times that 8h has been visited, k is the index of the episode such that 8n. is visited the i-th time, and Bg is some bonus term. The weights of are given by
II (1-a)), and af a, II (1-0)) (1-a)), j=++1
we redefine vilh (s) and Vx rewritten as
vii (s) comply with this update rule, the regret in 24 would be
R((s) Σ
uxxu (rh ( Pr Vh-1 (8)
Σ
(ra + h+1 (8).
at max a
xuti
For now, let us forget about the non-stationarity of V h+1 and pretend that can be considered constant term throughout the entire horizon by applying the method sketched in Remark Even in this simplified scenario, for each fixed I, we still need to address a weighted matrix team problem where the reward at time i is assigned the weight oi. Further, as I varies, the weight oi assigned to the same step also changes over time. Unfortunately. such dynamically weighted rewards cannot be easily handled by Algorithm [ as well as other stochastic non-convex optimization algorithms that we are aware of. During the execution of Algorithm 7 we are not able to modify the learning step size of previous step online cope with the changing weights. These weights also cannot be pre-computed, because it relies on knowing the total number of times that a certain state 8,. is visited during the entire horizon, which is impossible before seeing the output of the algorithm. Therefore, such an SGD framework is incompatible with the dynamic weights o that change over t, and this technical difficulty prevents us from directly applying the popular learning rale we proposed to utilize stage-based V-learning, because it essentially assigns uniform weights to each time step in history. These weights only depend the number of visitations the state Sh. in certain stage, which can be pre-computed from the recursive formula Ci+1 = = (1+ H )e.
Instead, H++
#++
Further, let F; be the o-algebra generated by all the random variables before episode 4,. Then, we 4
can see that (rx (8, 0g oif) + Viin f)) is martingale with respect to (F:) For any probability E (0, 1], let = log(2SK H/p) From the Azuma-Hoeffäie inequality, it holds with probability least 1 (2S2HHK) that
Mg xo
Th PA h+1
(8)
Σ 1=1
4. rh(s, bk) virnlshnn) s 2H 2H Vi/n, (27)
where suppresses logarithmic terms. In fact, since we only need Lemma 1 to hold in expectation instead of with high probability, suffices to replace (2) with an even simpler statement:
E
D Ps
+ -.P (8)
Σ
a
ra(s, oi (4.b))) v ( (hh.)) =0; (28)
ñ
x
31

---

Under review as a conference paper at ICLR 2022
which holds simply due to the martingale property. Finally, combining the results in 23 we obtain that
28
E
Pk
SE
max D
uxc
rh + Ph (ir (s)
71
1
(rn + ( V ( (0)
SE
pe xui
+ +16H v 2A /
71
(n( o/2 (/,))))) (/)) + V (ol))))))))
+ 16H /242 / //4/4
-E
rn(s,, of. 0/:) + v Virzlohen)
SE
+ ba
= [s]V,
where the second last step by the definition of 6n 25/1 V A /Aamx////// ///4, In the last step we used the formulation of V (s) in (2
Case 2: Vn (s) was not updated in (the end of) episode A 1. Since we have excluded the case that Vn has never been updated, we are guaranteed that there exists an episode j such that (s))) has been updated in the end of episode j - most recently. In this case, ( IV A (+) =
(VV(())) 2 EVVV (s)], where the last step is by the induction hypothesis. Finally, observe that by definition, the value of 1/ (s) is constant for all episode indices that belong to the same stage. Since we know that episode j and episode & lie in the same stage, we can conclude that E[V, (s)] = VVV % (s) < (s)).
Combining the two cases completes our proof.
G.2 PROOF OF THEOREM 3
In the following, we present the proof for the first inequality. The second bound can be proved via a similar argument.
Before proceeding further, we first recall the definitions of several notations from Section 5 and define a few new ones. For a state s let n be the total number of episodes that this state has been visited (at the h-thh step) prior the current stage, and let lf., denote the index of the episode that this state was visited the i-th time among the total nf, times. Similarly, recall that n denotes the number of visits to the state sy in the stage right before the current stage, and ih, denotes the i-th episode among the nf episodes. For simplicity, we use 4 and L, to denote 1h and i and to denote n whenever and are clear from the context.
From Lemmal) I we first obtain that
K
K
Σ
(81) - (ppt:(((s))
Σ E [+
(pii((()))
k=1
We hence only need upper bound the RHS. For ease of exposition, we define the following notation:
dut (()t)
Vp (
The main idea of the proof is to upper bound Σk a recursive formula. From the update rule of V x (s in (). we know that
K k= 8h by the next step Σk o/ and then obtain
n
Vh Iin = 0}H +
[n o (1.))) + Than (st(()))))) + ba,
ñ
1=1
32

---

Under review as a conference paper at ICLR 2022
where the [[n 0] term counts for the event that the optimistic value function has never been updated for the given state.
Let Fj be the o-algebra generated by all the random variables before the 1,-th episode. It can be seen that (ra(s, oi b/)) + 1+1
u " (s) 1+1=))== is martingale with respect to the filtration (Fi)
For any probability p E (0, 11. let (og(2SHH/p)) From the Ezuma-Hoeffdiin inequality, holds with probability at least - p/ that
(5)
ni
D
x
(Th + Pr
P.V ( (s)
V V
h+1
ra(ss aj; b))) +
v h+1
hit (d/tte) HV//i
(29)
where suppresses logarithmic terms. Substituting the two inequalities above into the definition of 8% we have
rn(s, o/ 6/2) + Vhi Vitz(shtzt) + bn
II = O|H +
1 7 ==1
Th + Pr w piits pir1)) (s)
D
MB Xux
<Tnm H
V V ( (thni) ba + 2/ H2//
22/HH2//
à
-Inm H| +
h+1 + by +2 H21/h.
(30)
where in the last step we used the definition of 8/ -- In fact, since we only need the results in Theorem to hold in expectation rather than with high probability, we can simply replace (29) with
phi th a+1 (5/ (5/++1)
rn (n b/2)
h+1l
by invoking the martingale property. Consequently, we can also derive expectation form of (30 as follows:
[ < Tin = 0) +
+ ba
(31)
To find an upper bound of Σk= tt we proceed to upper bound each term in the RHS of (31
separately. First, notice that Σ I [nt o] < SH, because each fixed state-step pair hs
contributes at most to ΣK [ 0]. Next, we turn to analyze the second term the RHS of
31.. Observe that
K
K
K
1
[i
=
h++1
1+1
km
k=
1=1
1
i=1
77 =
(32)
For fixed episode j. notice that Σ 117% = -] < 1, and that D 1 = = happens if and only if sft = si, and (j. h) lies in the previous stage of (k: h) with respect to the state-step pair (sf h). Define KG {k= E [K] E 117, = jl 1}. We then know that all episode indices le E K, belong the stage, and hence these episodes have the same value of n.. That is, there
33

---

Under review as a conference paper at ICLR 2022
exists integer N, O, such that n N, Vk Kj. Further, since the stages are partitioned in way such that each stage is at most (1 H/ times longer than the previous stage, we know that |Kyl - (1 + H )Ny. Therefore, for every j. it holds that
k
4 +1+ H
Σ
(33)
k=
Combining (32 and 333 leads to the following upper bound of the second term in 31
K
K
S
(1+
(34)
h++
H
h+1
k=1
So far, we have obtained the following upper bound:
k
K
K
< SH + (1+
EE
5k
bag
H
k++
1==1
Iterating the above inequality over h = H, H 1..... leads to
K
H
K h
8
<0
SH +
>>
bag
(35)
H
h=1k=1
where used the fact that (1 + }) " In the following, we analyze the bonus term b
more carefully. Recall our definitions that e1 = H, e++l = (1 + ]ee i 2 1, and ba
25H / V //auxx/ ////4, For any h E [A].
1 h- g
1 1 25H
A3
E 1=1
b
H
H
(st) 1/4
k=
K
255H /
A3
H
1-
s =c]
max
#ES f21
k=1
-25H V //3
max ΣΣ
(1+
-h w)s,
h-
H
121
where we define wxss def
Σ [ = 8, No (xt) eg] for any 8 S. we further let w(s) def Σjz1 (s, we can see that E.es w(s) = K. For each fixed state s, we now seek an upper bound of its corresponding value, denoted as J in what follows. Since each stage is (1 + H/ than its previous stage, we know that w(s.j)
1 times longer
I s, (s) e,] = [(1 + H
1 )e,] for
any 1 S j J. Since Σ/= w(s, = w(s), obtain that eJ S (1 /) /-1 < 1+
10 w(e) by
taking the sum of geometric sequence. Therefore, by plugging in w(s,j) [(1 + }
Ea+ म w(s.)) 3 5o J21
Σ
so (w())+HH)))
where in the second step we again used the formula of the sum of a geometric sequence. Finally, using the fact that Exes w(s) K and applying the Cauchy-Schwartz inequality, we have
ΣΣ
K (1
1 } H
-a -0
1 H22 VA2 max ΣΣ म
(1
y w ((s.))ee
km
J21
0
(K
$ A
(36)
34

---

Under review as a conference paper at ICLR 2022
Summarizing the results above leads
E
Σ ot
SH
K H 10 S A
When K' is large enough such that K 2 SH3/T the second term becomes dominant, and we obtain the desired result:
Σ R. ( -Vp Vi
- Σ Bioh] s so OKkH'' (KKH''' (k A
This completes the proof of the theorem.
G.3 PROOF OF THEOREM 4
The result essentially follows from the "regret to PAC guarantee" conversion given in Jin et al. (2018). Specifically, we know from Theorem that
K
Σ E v (81) ( (o)--V(e - (8)) sC
(37)
for some C₁ that is independent of K, is important to notice that
vi V (s1) val.et ($1) 20,
(38)
for each individual & [K]. because Vi (s1) defined the dynamic best response instead of the best fixed response in hindsight. Since the two agents uniformly draw the index x from {1, (1, K}, conclude from 37 and (38) that for any realization of K;
Vi Pi (s1)
v oT (51) S 50,H S A K
E
with probability at least 5.J To ensure 5C S / S E, it suffices to require that K > SA12 SA Similarly, if K 5 SA for some constant C2, then H
E V
(a1) (in--viioe 1i (01) s 502H' S A / K3.
Therefore, the agents run Algorithm for at least K 0(1 /* episodes, the randomly drawn policy pair (MT: o7) will be an E-approximate NE in expectation with probability at least by taking union bound. To improve the success probability to an arbitrary value 1-p for p (0, 3), one can adopt the standard "boosting" technique in the literature randomized algorithms (Mitzenmacher & Upfal 2017). by repeating the process for Olog 4) iterations, and then choosing the iteration with the smallest resulting regret. Finally, remark that have made no effort to optimize the sample complexity dependence on H, S, and Amax, which can certainly be improved.
G.4 V-LEARNING SGD WITH VARIANCE REDUCTION
Theorem 7. (Informal). For any > replace the SGD- IX subroutine in Algorithm 2 with variance-reduced SGD method (Algorithm 4 and the bonus term be by CHA (In aay for some absolute constant C' instead. Suppose that the two agents run such an algorithm for K episodes with K = (11/EA)) poly( H, S, A Amax), ) and uniformly sample an episode index i from the set (1....,K) K).
4175ga75
Then, with probability at least 5, the policy pair (jT DT) ) is an E-approximate Nash equilibrium in expectation.
Proof sketch. The proof follows a similar procedure as in the proofs of Lemma and Theorems and Due their similarities, in the following, we only sketch some of the differences in the proofs.
By setting the new bonus term to be by CH A5/11 11/
verify that the proof of Lemma
175
35

---

Under review as a conference paper at ICLR 2022
still holds. That is, the optimistic value function V (s) (with a modified bonus term) is still valid upper bound of both Ve (5) and v (s) expectation. Everything up to (35) the proof of Theorem also holds. Starting from 35 we further deduce that
ΣΣ
0gg s o (k3//tt) poly(H,
Smaxx) Amax),
by following similar argument when we derived (3)). Plugging the above inequality back the proof of Theorem
3
we obtain that
E
Vi
pi (81)
Vuti -((K))--)) - Amaxx, and
K
K
Σ
E
(s))
(81) (0))-Viit -VBti (8)) S SŌ(K-t poly(H, Amax).
K
k=1
Finally, repeating the proof idea of Theorem leads to the desired result.
G.5 A SAMPLE COMPLEXITY LOWER BOUND
To obtain a sample complexity lower bound of the problem, we consider a simple instance where either A or B is singleton, i.c., A = 1 or B 1. Learning approximate NE in such Markov team reduces to finding a near-optimal policy in a single-agent RL problem. Applying the regret lower bound of single-agent RI yields the following result for RL. in Markov teams.
Corollary 1. (Corollary of Jaksch et al. (2010).. For any algorithm, there exists two-player Markov team problem that takes the algorithm at least 9t HH SAmaz/e episodes to learn an E-approximate Nash equilibrium.
We remark that such lower bound might be very loose. Reducing to single-agent RL problem evades the strategic learning behavior of the agents and the non-stationarity that such behavior causes to the environment, which in our opinion are the central difficulties of learning in Markov teams. To derive a tighter lower bound in our decentralized setting, one should also utilize the additional constraint that each agent only has access to its local information, factor that Corollary apparently does not take into account. It is hence unsurprising that when comparing Theorem with Corollary we can see obvious gap the parameter dependence.
C
G.6 DECENTRALIZED MARL IN SMOOTH TEAMS
In the following, we address important subclass of Markov teams, named smooth teams, using the V-learning SGD algorithm. More importantly, we show that our algorithm can achieve near team-optimality, i.c., find the best Nash equilibrium, in such problems.
Smooth games were first introduced in Roughgarden (2009) to study the Price of Anarchy (POA) in normal-form games. large class of games are covered as examples of smooth games, including
congestion games and many forms of auctions (Roughgarden 2009 Syrgkanis & Tardos (013). The
notion of smoothness was later extended to learning in normal-fore games (Syrgkamis al. 2015)
Foster et al., 2016) and cooperative Markov games (Radanovic et al. 2019 Mao et al. 222)) This concept essentially ensures that the game has bounded POA, and hence decentralized no-regret learning dynamics can possibly converge to near-optimality.
Define V* to be the team-optimal value function, i.e., (s) = max Vž (s) for any h E [H] E
S, where II is the set of joint policies of the agents. We consider the following definition of smooth Markov team:
Definition 5. (Adapted from Radanovic et al. (2019)) For X 2 and 0 < p < 1, an N-player Murkov leam is (X, p)-smooth if there exists policy profile n² such that for any policy profile
π (T)) 1)):
(8) 222AV - V.
h
36

---

Under review as a conference paper at ICLR 2022
The (A, -msotthhesssss ensures that agent continues doing well by playing its optimal policy when the other agents are using slightly sub-optimal policies. It immediately follows that the resultant policies of Algorithm converge to 2/(1 + p) factor of the team-optimal NE at a rate of O ((-)/
Theorem Let K =2(1/=*) poly A, Amax). In (A, p)-soothh team, the value of running the auxiliary policies [ } ) h=1,k== satisfies
E
(51)
A
1+ - $). (11(s))
1 O(K-
K
1+p
Proof. From Theorem
it holds that
K
E
V
(81)
1
E
V v1 - O(K-
K
k=1
a Vi - v (s1)) O(K
K
where the second step simply by the definition of smoothness. Rearranging the terms leads the desired result.
Equivalently, such a result also holds when the agents uniformly sample an episode index k from {1...., K} and then run (p% .. In Theorem 5 illustrated our results in the of two agents, although one can easily verify that a similar result holds more generally for N N-player smooth teams. Our approach significantly generalizes Radanovic et al. (2019) and Mao et al. (2020) in that we design natural update rules for both agents, who play symmetric roles in the self-play setting; the other works only assign the algorithm to agent, and have assume that the policy of the other agent changes slowly.
H SIMULATIONS
In this section, we demonstrate the empirical performances of our algorithms. We start by evaluating SCD-IX (Algorithm I on classic matrix team problem. Then, we evaluate V-learn SGD (Algorithm 2 on a Markov team problem, and compare its performances with various benchmarks.
H.1 MATRIX TEAMS
First, to evaluate Algorithm 1 we use classic matrix team example from the literature (Claus & Boutilier 1998 Lauer & Riedmiller 2000). Its reward table is reproduced Table [ where agent the row player, and agent 2 is the column player, both being maximizers. The action spaces of the agents are A = {ag. 01, } and = (bo, b1, b2). There are three deterministic Nash equilibria in this team, among which two of them, (an, bn) and (ag, b2), are team-optimal. It would be preferred that the agents not only learn a NE, but also settle on the same NE out of the two team-optimal ones.
b0
61
b2
10
0
-10
80
bo
b
81
bo
b
41
0
0
0g
-2
0p
-10
0
10
2 -2
0
Table 1: Reward table for the matrix team.
Table 2: Reward tables for the Markov team.
We run our SGD-I IX algorithm on this task for T 5000 rounds, and we set the step size or = 0.002 and the implicit exploration parameter 0.001. We evaluate our algorithm in terms of both the rewards it obtained and its L equilibrium gap. Specifically, we define the L2 equilibrium gap as the L distance to equilibrium point. For pair of strategies (H, A(A) x A (BB) its L equilibrium gap is defined as:
Gap(u, def (i=n((()) -
(39)
37

---

Under review as a conference paper at ICLR 2022
where (1) (resp. μ² (v)) is the best response with respect (resp. 2), and 11-1|2 is the L norm. The simulation results are presented in Figure All results are averaged over 20 runs. Notice that we evaluate two sets of strategy trajectories: The "Current" strategy (14, 1/) is the strategy pair used by Algorithm at round I, while the "Average" strategy (fzz, D/)) is the uniformly sampled strategy pair obtain after running Algorithm[]]oo rounds. Drawing analogy to the Markov team setting, H.K
"Current" denotes the actual policies {(H, 1/= used at the step (k, h) of Algorithm 2 while
"Average" represents the auxiliary policies {00) ) teams, the auxiliary policy at round simply reduces uniformly drawing random time index from tt and running the strategy pair (n7, U4).
11=1k==1 that have constructed. In matrix
1.75
Average
L92
Equilbrium Cap
1.25
Rewwnrd
0.75
4.29
Durrent Average
12:00
2000
5000
1200
2000
AAG
s6c2
Iterations
Iterations
(a) Equilibrium gap
(b) Reward
Figure 2: (a) 2 equilibrium gaps and (b) rewards of Algorithm I on the matrix team task given in Table "Current" denotes the actual strategy trajectory, while "Average" represents the uniformly sampled strategy pair. Shaded areas denote the standard deviations of the equilibrium gap reward.
Note that in Theorems I and 4 we only have theoretical guarantees for the auxiliary policies ("Aver- age") but not the actual policy trajectories ("Current"). Encouragingly, our simulation results show that the actual policy trajectories also enjoy convergence behavior to NE empirically, and in most cases the "Current" policies converge even faster. Specifically, from Figure [(a)] we can see that the equilibrium gap of both "Current" and "Average" converge zero, indicating that they indeed find an equilibrium as the number of iterations increase. The convergence of "Average" slightly lags behind "Current" because in Algorithm [ "Average" simply takes the mean value the actual trajectories, which requires some time to reflect the convergence behavior. A more promising result is that from Figure 2(b). we can see that the rewards collected by "Current" and "Average" converge to values close to 9. This suggests that Algorithm [ not only finds a NE in this task, but actually converges to tetm-optimal equilibrium most of the time. It does not exactly reach the team-optimal value of 10 because it still converges to non-team-optingg NE at rather low frequency.
H.2 MARKOV TEAMS
We further evaluate Algorithm 2 on a Markov team task. Inspired by Yongacoglu et al. (2019), we construct a Markov team problem with two states S = (so, $1), where so is the "good state" and s is the "bad state". Each agent has two candidate actions AA = {ag, aj } or B = {bo, 6 J. The reward function each state presented in Table Specifically, at state $1, both agents get a reward of 0 no matter what actions they select, while at state so, they will obtain a strictly positive reward if they either take the joint action (ao, b1) or the one (a1,b)) The state transition function is defined as follows:
(s so or 81, a,, b1) = 1 - Ph(S1 80 or 81, not (ag, b.)) = - e, vh E [H],
and all the other transitions happen with probability Intuitively, no matter which state the agents are in, they will transition to the good state su with a high probability - E at the next step as long as they select the action pair (ou, b1). All the other joint actions will lead to the bad state $1 with high probability - E. The task hence rewards the agents who learn to consistently play the action pair (ag, b)).
38

---

Under review as a conference paper at ICLR 2022
We run our V-learning SGD algorithm on this example for K 5000 episodes, each episode containing H = 10 steps. We set the transition probability E = 0.1, the step size a 0.0004, and the implicit exploration parameter 7 0.002. We again evaluate our algorithm in terms of the reward and the equilibrium gap. The simulation results are presented in Figure where all results are averaged over 20 runs. We would like to remind the reader that "Current" denotes the performances of the actual policy trajectory {Ph 2/)) H h=1,k=1 while "Average" represents the auxiliary policies (Fh 1
H.K
30-
Average
Equilbrium Copp
Current
Average
Centralized
Independent
1000
2000
3000
5003
1200
2000
2000
4000
5662
Ieeraioos
Iteracions
(a) Equilibrium gap
(b) Reward
Figure 3: (a) L equilibrium gaps and (b) rewards of Algorithm on the Markov team task given in Table 2 "Current" denotes the actual policy trajectory +)) H.K
while "Average" represents the auxiliary policies { 1 Shaded areas denote the standard deviations of the equilibrium gap or reward.
We compare our algorithm with two meaningful benchmarks. The first benchmark is a "Centralized" oracle. This oracle acts centralized coordinator that control the actions of both agents. Such an oracle essentially converts the Markov team task into a single-agent RL problem. The (randomized) action space of the centralized agent is A(A B), which is larger than the ((A) A(B) space that we allow in our decentralized approach. Therefore, "Centralized" clearly upper bounds the performance that any decentralized learning algorithm can possibly achieve in this task. In our simulations, we implement "Centralized" by using Hoeffding- based variant of a state-of-the- single-agent RI. algorithm ACB-ADVANTAGE (Zhang al. 2020a). This algorithm has achieved the tightest sample complexity bound for single-agent RL in theory, and has also demonstrated remarkable empirical performances in practice (Mao et al., 2020). Such an algorithm could provide strong performance upper bound in our task. The second benchmark we consider is the naïve "Independent" Q-learning. Specifically, we let each agent run a single-agent Q-learning algorithm independently, without being aware of the existence of the other agent the structure of the Markov team. Each agent maintains an local optimistic Q-function, and takes greedy actions with respect to such optimistic estimates, without taking into account the other agents' actions. Since the agents update their policies simultaneously. the stationarity assumption of the environment single-agent RL quickly collapses, and the theoretical guarantees for single-agent Q-learning no longer hold. This is also reminiscent of the "independent learner" approach proposed in an early work (Claus) Boutilier 1998) for learning in Markov teams. We believe such benchmark could provide meaningful intuitions about the consequences of not taking care of the team structure in decentralized methods. In our simulations, we implement such benchmark by letting each agent running variant of the single-agent UCB-ADVANTAGE (Zhang et al. 2020a) algorithm independently. where the (randomized) action spaces of the agents are (AA) and A(B).
We can observe from Figure 3(a) that the I equilibrium gaps of both "Current" and "Average" converge to zero, indicating that both them find a Nash equilibrium. This encouraging because our theoretical results in Theorem only guarantee the performance of the auxiliary policies, while our simulation results suggest that the actual policy trajectories also converge to a NE. The actual policy sequence also converges faster than the auxiliary policies, for reasons similar to the matrix team simulations. From Figure ((b) we can again see that our algorithm even finds to the team- team-optimal NE most of the time, as the rewards it obtained nearly match the "Centralized" oracle. On the other hand,
39

---

Under review as a conference paper at ICLR 2022
the "Independent" benchmark converges, albeit faster, to clearly suboptimal value. This reiterates that the naive idea of independent learning does not work well for multi-agent RL in general, and careful treatment of the game/team structure (like our SGD subroutine) is necessary. Finally, the implemented V-1 ea rn pariing ng SGD algorithm takes much fewer samples to find an approximate NE than theoretical results suggested. This indicates that the theoretical bounds might be overly conservative, and our algorithm could converge much faster in practice.
40


Reviews:
[{"review_id": "x6ZYReoPYlV", "reviewer": "Reviewer_hhmV", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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 is an interesting subclass of problem, I found the paper was well written and explained the approach clearly. The authors correctly point out the considerable scaling issues with communication in agent based cooperative tasks that attempt to exchange information between the agents, and since it is easy for those to be intractable, it is very useful to identify alternatives. \n\nI take mild issue with the claim that there is \"no communication\" between agents in this kind of approach though - there is, it is the information distributed to all the agents at the beginning of the algorithm in the form of the reward function. The agents then don't rely on any further exchanges of information to achieve a local optimum that achieves a global approximate Nash equilibrium policy. This in no way discredits the approach, and there is an interesting sub-class of problems that can be solved this way (for example American Football´s play books somewhat fit this model), but I would like to see this pointed out in the discussion. There is a danger, especially in simulating this problem, that the reward function contains enough information to in some sense encode the solution, and It would improve the paper significantly if there was a discussion of the size of the information communicated by the reward function, versus the settling time of the algorithm. It would also be nice to see concrete real world examples where this approach is useful, although I appreciate that this is a theoretical paper, making that in some sense somebody else's job.", "summary_of_the_paper": "This paper examines the problem of completely decentralised agent cooperation in a Markov game environment, where there is no communication between agents. They propose a stage based learning algorithm to explore an unknown environment using this approach.", "summary_of_the_review": "I think this paper is a useful contribution, and although I don't think the issues I raise are completely minor, they shouldn't be too hard to address by the authors.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "sAv-vVVA2w", "reviewer": "Reviewer_t9pe", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 is extraordinarily well written; I did not find any issues with spelling, grammar nor presentation.\nThe authors provide a variety of interesting theoretical results. \n\nThe O(1/epsilon^4) result from Theorem 2 is particularly exciting. An extension to continuous action spaces (with some reasonable structural assumptions) would be interesting.\n\nThe use of a stage-based approach to tackle multi-agent learning non-stationarity is by itself refreshing (even without the perks of establishing unique non-asymptotic convergence bounds), and I expect it will resonate within the deep MARL community.\n\nIn section 4, I would suggest using a letter other than \\mathcal{L} for denoting the partial sums over stage lengths, as \\mathcal{L} is frequently used to denote loss objectives in MARL literature.\n\nTo further improve the paper, I believe the authors should compare their empirical results against other methods that aim to tackle nonstationarity in multi-agent learning. These include CTDE algorithms, such as tabular variants of QMIX [Rashid et al] or VDN [Sunehag et al]. This also includes tabular variants of policy-gradient algorithms, such as IPPO [Schroeder de Witt et al]. \n\nI see two major opportunities for future work:\n1. Extend V-learning SGD to Q-learning with function approximation, ideally with theoretical guarantees, but an empirical demonstration would also be extremely interesting\n2. Can V-learning SGD additionally benefit from CTDE settings, i.e. can the availability of extra state information during training be exploited? What about parameter-sharing in function approximation settings?", "summary_of_the_paper": "The authors establish a variety of novel theoretical results for Markov team problems. First of all, they present a novel non-asymptotic convergence bound for single-step Markov teams, using a no-regret independent learning variant of stochastic gradient descent (SGD-IX). Secondly, they extend SGD-IX with a stage-based design to arrive at a novel, decentralized MARL algorithm (Stage-based V-learning). For Stage-based V-learning, the authors additionally proceed to establish a novel non-asymptotic convergence bounds that do not depend on the size of the centralised joint policy, but instead just the largest individual action space. The authors also show how their algorithm sidesteps technical difficulties inherent to establishing convergence bounds for Optimistic Q-learning [Jin et al, 2018]. Using a simple matrix team task, as well as a Markov team task as an example, the authors demonstrate empirically that their algorithms can end up selecting favourable Nash equilibria.", "summary_of_the_review": "I recommend the paper be accepted as is. The paper's writing and presentation are very clear and polished, and the results are both sound and significant. I expect this paper to stimulate the cooperative MARL community.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "EBGbzYFEgBq", "reviewer": "Reviewer_iszg", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Pros\n+ The paper is theoretically strong. Theorem 4, shows a 60% convergence probability of their algorithm on expectation, yet with two more iterations (if I did the math right) it bumps it to 99%.\n+ The sample complexity reduction compared to the previous work is impressive.\n\nRoom for Improvement\n- The paper is difficult to follow. I recommend pushing more sections into the Appendix so you can explain the existing content well in the main body. For example, Algorithm 2 was mentioned without enough discussion. How certain constants where picked, etc.\n- Given the strong promise of the paper, I was underwhelmed with the simulation results. Why did you pick a simple 2 player game? Why not going for something much larger? After all that is the main catch of your bound. \n- For the simulation result, I think you could also calculate he optimal policy for the centralized case using backward dynamic programming in time since your H is fixed. How come you did not include that?\n\nDetails\n- \"Oblivious to the presence of agents\" => Does this limit the applicability of the method? For example if multiple agents are trying to do something together, often their location would heavily impact each other.\n- O(1/e^4) samples (paper) or episodes (abstract)? While given the fixed H and Poly part of the theorem it does not matter, it would be great to make ti consistent.\n- Any thoughts of expanding this to infinite horizon problem?\n- recommend using t instead of h for tilmestep.", "summary_of_the_paper": "Authors tackles the cooperative multi-agent reinforcement learning problem with stochastic dynamics. They introduced V-learning Stochastic Gradient Descent (SGD) with theoretical proofs of convergence to the optimal policy with desired e probability. The resulting sample complexity is O(1/e^4) * Poly (A,S,H), where H is the episode horizon. Authors also empirically tested the algorithm in a toy 2 agent matrix game showing convergence to the optimal policy.", "summary_of_the_review": "I think the theoretical contributions of the paper are great and would benefit the community. I was hoping to see much bigger domain in the simulation part. The writing is currently very dense.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0UZp-zXP6Y", "reviewer": "Reviewer_8WCV", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "There are the following problems of this paper. \n- Typically, a Nash equilibrium is required to be a product policy (the players cannot have shared randomness). The policy pairs $(\\mu_h^\\kappa, \\nu_h^\\kappa)$ generated by Algorithm 3 is not a product policy, so this is not a Nash-equilibrium. In line 6, the authors propose to use a shared random variable $i$ among all the players (this is essential for the value iteration equation above Theorem 3 to hold; if the value iteration equation does not hold, the whole proof is wrong), and such shared randomness makes the policy correlated. Such a correlated policy is a CCE, but not Nash-equilibrium. The authors can argue that, by Markov inequality, the first step randomness $\\kappa$ can be de-randomized, so theorem 1 and 2 may be valid (but these are just single step Markov games). But for Markov games, the later steps' randomness cannot be decoupled by the Markov inequality. \n\n- Even if the issue can be fixed, the authors just considered two players Markov cooperative games, instead of multi-players Markov cooperative games. It is not clear whether it can be generalized to multi-players games with similar bounds. \n\n\nMinor problems: \n1. In the abstract the author wrote that their sample complexity is O(1/eps^4) for Markov team. However, it is O(1/eps^4) for Matrix team and O(1/eps^8) for Markov team. \n2. The paper by Leonardos et.al. 2021 considered \"the aspect of exploring the unknown environment\" and had a sample complexity guarantee (in the related work section). \n\n\n", "summary_of_the_paper": "This paper studies sample complexity bound for finding approximate Nash equilibrium in two-player Markov cooperative games using decentralized algorithms. The authors designed a stage-based V-learning algorithm, which achieves eps approximate Nash equilibrium in $1/eps^8$ episodes. Under the smoothness conditions, such equilibrium is a team-optimal Nash. \n\n", "summary_of_the_review": "The main theorem is wrong. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a decentralized cooperative approach in multi-agents using Markov games theory. After reviewing the paper and reading the comments from the reviewers, here are my comments:
 
- The paper is well-written, quite difficult to follow, but very informative.
- The contribution is clearly stated and the results support it.
- Theoretical results are interesting for the RL community.
- The main concern is about learning the epsilon-approximate Nash equilibrium policy which is a fundamental part of the paper.
Decision: Reject