Best Possible Q-Learning
Authors: Jiechuan Jiang
Zongqing Lu
Venue: Submitted to ICLR 2023 (2023)
Keywords: multi-agent reinforcement learning

Abstract: Fully decentralized learning, where the global information, i.e., the actions of other agents, is inaccessible, is a fundamental challenge in multi-agent reinforcement learning. However, the convergence and optimality of most decentralized algorithms are not theoretically guaranteed, since the transition probabilities are non-stationary as all agents are updating policies simultaneously. To tackle this challenge, we propose \textit{best possible operator}, a novel decentralized operator, and prove that the policies of agents will converge to the optimal joint policy if each agent independently updates its individual state-action value by the operator. Further, to make the update more efficient and practical, we simplify the operator and prove that the convergence and optimality still hold with the simplified one. By instantiating the simplified operator, the derived fully decentralized algorithm, best possible Q-learning (BQL), does not suffer from non-stationarity. Empirically, we show that BQL achieves remarkable improvement over baselines in a variety of cooperative multi-agent tasks.

Under review as a conference paper at ICLR 2023
BEST POSSIBLE Q-LEARNING
Anonymous authors
Paper under double-blie blind review
ABSTRACT
Fully decentralized learning, where the global information, ie.. the actions of other agents, is inaccessible, is fundamental challenge cooperative multi-agent reinforcement learning. However, the convergence and optimality of most decen- tralized algorithms are not theoretically guaranteed, since the transition probabili- ties are non-stationary as all agents are updating policies simultaneously. To tackle this challenge, we propose best possible operator, a novel decentralized operator, and prove that the policies of agents will converge to the optimal joint policy if each agent independently updates its individual state-action value by the operator. Further, to make the update more efficient and practical, we simplify the operator and prove that the convergence and optimality still hold with the simplified one. By instantiating the simplified operator, the derived fully decentralized algorithm, best possible Q-learming (BQL., does not suffer from non-stationarity. Empiri- cally, we show that BQL achieves remarkable improvement over baselines in a variety of cooperative multi-agent tasks.
INTRODUCTION
Multi-agent reinforcement learning (MARL) trains group of agents cooperatively maximize the cumulative shared reward, which has great significance for real-world applications, including logistics (Li et al., 2019), traffic signal control (Xu al., 2021), power dispatch (Wang et al., 2021b), and games (Vinyals et al., 2019). Although most existing MARL methods follow the paradigm of centralized training and decentralized execution (CTDE), in many scenarios where the information of all agents is unavailable in the training period, each agent has to learn independently without centralized information. Thus, fully decentralized learning, where the agents can only use local experiences without the actions of other agents, is highly desirable.
However, in fully decentralized learning, as other agents are treated as part of the environment and are updating their policies simultaneously, the transition probabilities from the perspective of individual agents will be non-stationary. Thus, the convergence of most decentralized algorithms, e.g., independent Q-learning (IQL) (Tan, 1993). is not theoretically guaranteed. Multi-agent alter- nate Q-learning (MA2QL) (Su et al., 2022) guarantees the convergence to a Nash equilibrium, but the converged equilibrium may not be the optimal one when there are multiple equilibria (Zhang et al., 2021a). Distributed IQL. (Lauer & Riedmiller, 2000) can learn the optimal joint policy, yet is limited deterministic environments. How guarantee the convergence of the optimal joint policy in stochastic environments remains open.
To tackle this challenge, we propose best possible operator, a novel decentralized operator to update the individual state-action value of each agent, and prove that the policies of agents converge to the optimal joint policy under this operator. However, it is inefficient and thus impractical to perform best possible operator. because at each update it needs to compute the expected values of all possi- ble transition probabilities and update the state-action value to be the maximal one. Therefore, we further propose simplified best possible operator. At each update, the simplified operator only com- putes the expected value of one of the possible transition probabilities and monotonically updates the state-action value. We prove that the policies of agents also converge to the optimal joint policy under the simplified operator. We respectively instantiate the simplified operator with Q-table for tabular cases and with neural networks for complex environments. In Q-talle instantiation, non- stationarity is instinctively avoided, and in neural network instantiation, non-stationarity in replay buffer is longer drawback, but necessary condition for convergence.

---

Under review as a conference paper at ICLR 2023
The proposed algorithm, best possible Q-learning (BQL), is fully decentralized, without using the information of other agents. We evaluate BQL on a variety of multi-agent cooperative tasks, i.e., stochastic games, MPE-based differential games (Lowe et al., 2017), multi-agent MuJoCo (de Witt et al., 2020b), and SMAC (Samvelyan et al., 2019), covering fully and partially observable, de- terministic and stochastic, discrete and continuous environments. Empirically, BQL substantially outperforms baselines. To the best of our knowledge, BQL is the first decentralized algorithm that guarantees the convergence to the global optimum in stochastic environments, and more simplifica- tions and instantiations of best possible operator can be further explored. We believe BQL will be new paradigm for fully decentralized learning.
METHOD
2.1 PRELIMINARIES
We consider N N-agent MDP Menv =< S,, Ponv: > with the state space S and the joint action space A. At each timestep, each agent chooses individual action a, and the environ- ment transitions to the next state s by taking the joint action a with the transition probabilities Penv (s'|s, a). For simplicity of theoretical analysis, we assume all agents obtain the state s, though in practice each agent i can make decisions based on local observation oN E O or trajectory. All agents obtain a shared reward r = R (s, s') and learn to maximize the expected return TE oc 7're with the discount factor 7. In fully decentralized setting, Menv is partially observable to each agent, since each agent only observes its own action a, instead of the joint action a. From the perspective of each agent there is an MDP M, =< S, Ai, R. Ps, with the individual action space A, and the transition probabilities
Ps (s E Penv (s'ls, a, a-.) (a((a_)s)
(1)
where π- denotes the joint policy of all agents except agent i. similarly for a-s. According to (1), the transition probabilities P. depend on the policies of other agents n As other agents are updating their policies continuously, P: becomes non-stationary. On the non-stationary transition probabilities, the convergence of independent Q-learning'
(s a;) = Bp((ol)a.) r ymaxQu(s .a))
of
is not guaranteed, and how to learn the optimal joint policy in fully decentralized settings is quite challenge. In the next section, propose best possible operator, novel fully decentralized operator, which theoretically guarantees the convergence to the optimal joint policy in stochastic environments.
2.2
BEST POSSIBLE OPERATOR
First, let us consider the optimal joint Q-value
Q a) E (e'lea)))
ymaxQ(ss' a')s
(3)
which is the expected return the optimal joint policy π T8()) arg maxa ((s, a). Based on the optimal joint Q-value, for each agent i, we define maxa Q(, a, a.), which follows the fixed point equation:
maxQ(s, Gj, am;) = max E E (s')e.a) r ymax maxQ al. a'..) a
(4)
a
a'
+ ymax maxQ dis a'.
Pone ((l1,,,,,
(5)
((s, ai, a-;) given 0; (4) is from taking maxa.. on both sides of (3), and (5) is by folding ( 0:) into Peny-
where T a4) arg max a.,
)) is the optimal conditional joint policy of other agents
Then we have the following lemma.
For simplicity, we refer the optimal value Q" as Q in this paper, unless stated otherwise.
2

---

Under review as a conference paper at ICLR 2023
Lemmal 1. If each agent learns the independent value function Qs(s. 0.) = max, Q(s, ai a-i), and takes actions as arg maxa. Qi(s, 0z), the agents will obtain the optimal joint policy, when there is only one optimal joint policy'.
Proof. Since max., maxo-: (ss, 0t a-i) = maxa Q(ss, a), and there is only one optimal joint policy, arg maxo, (i,, a;) is the action of agent i in the optimal joint action
According Lemma 1, to obtain the optimal joint policy is to let each agent i learn the value function Q1 0:) = maxa-; Q(8, a, a-i). To this end, we propose a new operator to update Q: in fully decentralized way:
a.)) max Br((s()saa)) r 7max of) P.(.)a,a.)
(6)
of
Given 8 and ag, there will be numerous Ps(s"|s, Is, as) due to different other agents' policies π- To reduces the complexity, we can only consider the deterministic policies, because when there is only one optimal joint policy, the optimal joint policy must be deterministic (Puterman, 1994), so the operator (6) takes the maximum only over the transition probabilities P.(s'|s, a:) under de- terministic - Intuitively, the operator continuously pursues the 'best possible expected return', until Qi reaches the optimal expected return maxa_, Q(s, ds a-i), so we name the operator (6) as best possible operator. In the following, we theoretically prove that Qi(s, 0;) converges to maxa Q(8, a(s)) under best possible operator, thus the agents learn the optimal joint policy. Let (s,, ai) denote the value function in the update k. Q is initialized to be the minimal return, and Qi(s,a;) == Q2 (s, a.). Then, we have the following Lemma.
Lemma 2. max Q(s, a, a a).) 2 O² (s, a.). Vss ag, Vk, under best possible operator.
Proof. We prove the lemma by induction. First, as Q is initialized to be the minimal return, max._, Q(s, a,, a))) 2 (s, az). Then, suppose maxa-. Q(s, as. a_s) 2 Q az), Vs, a. By denoting arg max a.a.) Ep,(s' s.) (,))) [r + y max,; Q 1 [4]] as P. (s'1s, a.), we have
maxQ(s, (j; ((,
a_;
Σ
Penr aslss,;,aa) an ((8,8') + manammaaaaa maxQ(s', of d²=
max a-1
(s((sss, ((8,5)) mmax (88 af))
2 Σ (s) r(s,s')+ + max (s dis a'i)
of
Σ (o)l,,a))) (((5,5) + x (6'.a()
(5'1,,a)))
max max d/ a²_,) - .d)
of a_
maxQ(s' a',)) - -
where at" arg maxa; Qs- of). Thus, it holds in the update k. By the principle of induction, the lemma holds for all updates.
Intuitively, max. Q(8, ais a-;) is the optimal expected return after taking action ag so it is the upper bound of Qi(s, a.). Further, based on Lemma 2, we prove the following lemma.
We provide simple solution for situations with multiple optimal joint policies in Appendix D.
3

---

Under review as a conference paper at ICLR 2023
Lemma 3. Qi(s,aa) as) converges maNa Q(s, as a-1) under best possible operator.
Proof. From (5) and (6), we have
msx ai am:) - Of (3(,aai)
Σ Ponv ai, r(s,5') + max max a'i)) d'_
max 5,04
Σ (dd(s,))))) ((8,8)) + mmaxa ( (s1, - (Lemma 2)
Σ Pano a, T=, r(8,5') + max max di a'
< max
8,0,
of a'_
D Panv (i, ((8,8)) mmaxat (s (5' d6)) )
S maa o'
maxQ(s' (s)Q(s''',,'')) d', O,- (5'
a'
= max (s, as - -2 -
We have maaxa-, Q(s, az a-)) - (s, Sr |maxa_. Q(s a-.) Q Let k + xo, then Qi(8, a;) + maxa (s, ai ami,, thus the lemma holds.
According to Lemma and 3, we have: Theorem 1.
The agents learn the optimal joint policy under best possible operator.
2.3 SIMPLIFIED BEST POSSIBLE OPERATOR
Best possible operator guarantees the convergence to the optimal joint policy. However, to perform (6), every update, each agent has to compute the expected values of all possible transition probabil- ities and update Qi to be the maximal expected value, which is too costly. Therefore, we introduce an auxiliary value function Q (s, az), and simplify (6) into two operators. First, each update, we randomly select one of possible transition probabilities P. for each (s, a;) and update ( a:) by
( a.) E ((((oa))))))
[
ymax),(s'
Q7 aq) represents the expected value of the selected transition probabilities. Then we monotoni- cally update Qi a,) by
Qi(s, a.) max Q,),
(8)
We define (7) and (8) together simplified best possible operator. By performing simplified best possible operator, (s, 04) is efficiently updated towards the maximal expected value. And we have the following lemma.
Lemma 4. Qi(s,a;) a;) converges to max ((s, 0i, a-;) under simplisied best possible operator.
Proof. According to (8), as Qi(s, a;) is monotonically increased, Q! (s. (z) 2 - az) in the update k. Similar to the proof of Lemma 2, we can easily prove maxa-, Q( 0; a_ 2 Q (s, a;) under (7) and (8). Thus, {Qf } is an increasing sequence and bounded above. According to the monotone convergence theorem, {Q+ (s. a;)} converges when & - oo, and let Qi o.) = Q? (s, a;).
Then we prove that the converged value (i az) is equal to max Q(8, ai a.i). Due to mono- tonicity and convergence, Ve, a, 3K, when & > K, (+ a.) - O (s, S e, no matter which P. is selected in the update k. Since each P. is possible to be selected, when selecting
4

---

Under review as a conference paper at ICLR 2023
(,())(s,a,) arg p (s)(aa))) [r ymaxa, (5 (s by per- forming (7) and (8), we have
(s.a)) + Q,(ss (s)) = (s ((s,88 + xmaxaa (s',
According to the proof of Lemma 3, we have
maxQ(s, a,, a..) - Qi( a.)
maxQ(s, a. ts, ai).
max
ymax 8,a,
a-1
8" of arg m (maxo.. Q(s, ai a-i) - - and " + (i ai)
maxQ(s" a_,) ( (s", 1
S ymax( at a_.) -0 - (?))
Then, we have
max Q a, a-i - (s. $ I--' a_:
Thus, Qi(s, a;) converges to maxa Q(s, aj, a.:.
According to Lemma and 4, we have: Theorem 2.
The agents learn the optimal joint policy under simplified best possible operator.
2.4 BEST POSSIBLE Q-LEARNING
Best possible Q-learning (BQL) is instantiated on simplified hest possible operator. We first con- sider learning Q-table for tabular cases. The key challenge is how to obtain all possible transition probabilities under deterministic πh during learning. To solve this issue, the whole training pro- cess divided into M epochs. At the epoch m, each agent i randomly and independently initializes deterministic policy a: and selects subset of states S.n. Then each agent interacts with the environment using the deterministic policy
arg maxA, Qi(s, Am (s)
if $ S.m else.
Each agent stores independent experiences (s, (s, s', in the replay buffer D." As P: depends on --;;; and agents act deterministic policies, DI" contains one P, under a deterministic -T Since P. will change if other agents modify their policies π- acting the randomly initialized policy n. on ST in the epoch m not only helps each agent to explore state-action pairs, but also helps other agents to explore possible transition probabilities. When M is sufficiently large, given any (s, a.) pair, any (, a;) can be found in a replay buffer.
After interaction of the epoch m, each agent i has buffer series (D), D each of which has different transition probabilities. At training period of the epoch m, each agent randomly selects one replay buffer D. from {D!.... Drm }. and samples mini-batches {s, a; s', r3 from D to update Q-table Q (s, a.) by (7), and then samples mini-batches from D. to update Qi(s, a,) by
(8). The Q-table implementation summarized in Algorithm
Then we analyze sample efficiency of collecting the buffer series. Simplified best possible operator requires that any possible (s, a;) of (s. a,) pair can be found in one buffer, but does not care about the relationship between transition probabilities of different state-action pairs in the same buffer. So BQL. ideally needs only [A, x |A=i| |A] small buffers cover possible P. for any (8, a;) pair, which is very efficient for experience collection. We give intuitive illustration for this and analyze that BQL has similar sample complexity to the joint Q-learning (3) in Appendix B.
In complex environments with large continuous state-action space, it is inefficient and costly to follow the experience collection in tabular cases, where the agents cannot update their policies during the interaction of each epoch, and each epoch requires adequate samples accurately estimate the expectation (7). Thus, in complex environments, same as IQL, each agent only maintains one replay buffer D,, which contains all historical experiences, and uses the same e-greedy policy as
5

---

Under review as a conference paper at ICLR 2023
Algorithm 1. BQL with Q-table for each agent i
1: Initialize tables Qi and O.
2: for m = .....:....
3: Initialize the replay buffer D and the exploration policy a!".
4: All agents interact with the environment and store experiences (s, as, s', in D.".
5: for I,.... n_update do
6: Randomly select buffer DJ from D ..,...,. D.".
7: Update Oi according to (7) using samples from D
8: Update Qi according to (8) using samples from D
9: end for
10: end for
Algorithm 2. BQL with neural network for each agent
1: Initialize neural networks Q, and Q2, and the target network Q?.
2: Initialize the replay buffer D;
3: for = 1...., nlLiteration do
4: All agents interact with the environment and store experiences (s, a, s r',r) in D..
5: Sample a mini-batch from D..
6: Update Q by minimizing (9).
7: Update Q; by minimizing (10).
8: Update the target networks Qç
9: end for
IQL without the randomly initialized deterministic policy ü, Then we instantiate simplified best possible operator with neural networks Q; and Q Oi updated by minimizing:
Es Drw: [ (s, - 7Qi(s', d arg max Qi(s',a))
"
And Q; is updated by minimizing:
E Eg (u(s,a)) a.) (Qr (s, a.) - a.)) w0s a;) = {1 if ( a,) > Qi (s)
(10)
else.
Q is the softly updated target network of Q: When X 0. (10) is equivalent to (8). However, when == 0, the positive random noise of Q; in the update can be continuously accumulated, which may cause value overestimation. So we adopt the weighted max in (10) by setting 0 < < 1 to offset the positive random noise, In continuous action space, following DDPG (Lillicrap al., 2016), we train a policy network T; (s) by maximizing (s s, T. (s)) as substitute of arg max., Qi az). The neural network implementation summarized in Algorithm 2.
Simplified best possible operator is meaningful for neural network implementation. As there is only one buffer D., we cannot perform (6) but can still perform (7) and (8) on D;, As other agents are updating their policies, the transition probabilities in D, will continuously change. If D, sufficiently goes through all possible transition probabilities, Qi(s, as) converges to maxa Q88, az, a-i) and the agents learn the optimal joint policy. That is to say, non-stationarity in the replay buffer is no longer a drawback, but a necessary condition for BQL.
RELATED WORK
Most existing MARL methods (Lowe et al., 2017; Iqbal & Sha, 2019; Wang at. 2020; Zhang et al., 2021b: lb; Su & Lu, 2022; Peng et al., 2021; Li et al., 2022; Sunehag et al., 2018: Rashid et al., 2018; Son et al., 2019; Wang et al., 2021a: Rashid et al., 2020) follow the paradigm centralized training and decentralized execution (CTDE), where the information of all agents can be accessed in cen- tralized way during training. Unlike these methods, we focus on fully decentralized learning where global information is not available. The most straightforward decentralized methods, i.e., indepen- dent Q-learning (Tan, 1993) and independent PPO (IPPO) (de Witt et al., 2020a), cannot guarantee the convergence of the learned policy, because the transition probabilities non-stationary from

---

Under review as a conference paper at ICLR 2023
071 -2
145L
12k
Ohedap
Shedlp
(a) Stochastic games
(b)
[D,")
(c)
|S(
(d) One-stage game
Figure 1: Learning curves on cooperative stochastic games.
the perspective of each agent, as all agents are learning policies simultaneously. Multi-agent alter- nate Q-learning (MA2QL) (Su et al., 2022) guarantees the convergence to Nash equilibrium, but the converged equilibrium may not be the optimal one when there are multiple equilibria, and it has to be trained in an on- on-policy manner and cannot use replay buffers, which leads to poor sample effi- ciency. Following the principle of optimistic estimation, Hysteretic IQL (Matignon et al., 2007) sets a slow learning rate to the value punishment. Distributed IQL (Lauer & Riedmiller, 2000), a special case of Hysteretic IQL with the slow learning rate being zero, guarantees the convergence to the optimum but only in deterministic environments. Our BQL is the first fully decentralized algorithm that converges to the optimal joint policy in stochastic environments.
In the next section, we compare BQL against these Q-learning variants (Distributed IQL is included in Hysteretic IQL). Comparing with on-policy algorithms, e.g., IPPO, that are not sample-efficient especially in fully decentralized settings, is out of focus and thus deferred to Appendix. Decen- tralized methods with communication (Zhang et al., 2018; Konan et al., 2021) allow information sharing with neighboring agents according to time-varying communication channel, which do not follow the fully decentralized setting and thus are beyond the scope of this paper.
4 EXPERIMENTS
In experiments, we first test BQL with Q-table on randomly generated cooperative stochastic games to verify its convergence and optimality. Then, to illustrate its performance on complex tasks, we compare BQL with neural networks against Q-learning variants on MPE-version (Lowe et al., 2017) differential games, Multi-Agent MuJoCo (Peng et al., 2021), and SMAC (Samvelyan et al., 2019). The experiments cover both fully and partially observable, deterministic and stochastic, discrete and continuous environments. Since we consider the fully decentralized setting, BQL and the baselines do not use parameter sharing. The results are presented using mean and standard deviation with different random seeds. More details about hyperparameters are available in Appendix E.
4.1 STOCHASTIC GAMES
To support the theoretical analysis of BQL, we test Q-table instantiation stochastic games with 4 agents, 30 states, and infinite horizon. The action space of each agent is 4, so the joint action space [A| = 256. The distribution of initial states is uniform. Each state will transition to any state given joint action according to transition probabilities. The transition probabilities and reward function are randomly generated and fixed in each game. We randomly generate 20 games and train the agents for four different seeds in each game.
The mean normalized return (normalized by the optimal return) and std over the 20 games shown in Figure aa. IQL cannot learn the optimal policies due to non-stationarity. Although using the opti- mistic update remedy the non- con-stationarity. Hysteretic IQL (H-IQL) still cannot theoretically solve this problem in stochastic environments and shows similar performance to IQL. In Appendix A, we thoroughly analyze the difference between H-IQL and BQL,, and show H-IQL is special case of BQL in deterministic environments. MA2QL guarantees the convergence to a Nash equilibrium, but the converged one may not be the optimal one, thus there is a performance gap between MA2QL and optimal policies. BQL could converge the optimum, and the tiny gap is caused by the fitting error of the Q-table update, which verifies the theoretical analysis. Note that, in Q-table instantia- tions, MA2QL and BQL use different experience collection from IQL, i.e., exploration strategy and replay buffer. MA2QL only uses on on-policy experiences and BQL collects a series of small buffers. However, for sample efficiency, the two methods have to use the same experience collection as IQL.
7

---

Figure lb shows the effect of the size of buffer D.T at the epoch m. If (D is too small, ie.. 200, the experiences in [D,") are insufficient to accurately estimate the expected value (7). If [D,"] is too Under review as a conference paper at ICLR 2023
DOL
DCL
DGL
DOL
(a) / 0.2
(b) B 0.3
(c) 0.4
(d) 3 = 0.5
Figure 2: Learning curves on MPE-based differential games with different B.
in complex tasks with neural networks. MA2QL- and BQL- respectively denote the two methods with the same experience collection as IQL. Trained on off-policy experiences, MA2QL- suffers from non-stationarity and achieves similar performance to IQL. Even if using only one buffer, as we have analyzed in Section 2.4, the non-stationary buffer sufficiently goes through all possible transition probabilities, BQL agents can also converge to the optimum. Although going through all possible transition probabilities by one buffer is inefficient, BQL- significantly outperforms IQL, which implies the potential of BQL with one buffer in complex tasks.
large, i.e., 10000, the experiences in [D:"] are redundant, and the buffer series is difficult to cover all possible transition probabilities given total training timesteps. Figure I shows the effect of the number of states on which the agents perform the randomly initialized deterministic policy # for exploration. The larger |S means a stronger exploration for both state-action pairs and possible transition probabilities, which leads to better performance.
We then consider one-stage game that is wildly adopted in MARL (Son al., 2019). There are agents, and the action space of each agent is 3. The reward matrix is
a1 a1/02
AA
A
A
A
8
12
-12
A4
-12
0
0
(33
-22
where reward 8 is the global optimum and the reward 0 is the sub-optimal Nash equilibrium. As shown in Figure 1d, MA2QL converges the sub-optimal Nash equilibrium when the initial policy of the second agent selects A22) or A(3), But BQL converges to the global optimum easily.
4.2 MPE
To evaluate the effectiveness of BQL. with neural network implementation, we design an MPE-based differential game, where 3 agents can move in the range [-1, 1]. In each timestep, agent i acts the action a, E [-11, 1]. and the position of agentt will be updated as x; = clip(z,+ +0.1 a,, -1, 1) (i.e., the updated position is clipped to [-1, 1) with the probability 1 1 3, will be updated -r; with the probability 3. B controls the stochasticity. The state is the vector of positions {a1, 22 Ø3}- The
[o] + xz) is given in Appendix E. We visualize the relation between and / in Figure 15. There is only one global optimum (1 and 1) but infinite sub-optima (1 (t=00 0.8 and = 0.3). and the narrow region with r > 0.3 is surrounded by the region with r 0. So it is quite challenge learn the optimal policies in fully decentralized way. Each episode contains 100 timesteps, and the initial positions follow the uniform distribution. We perform experiments with different stochasticities 8, and train the agents for eight seeds with each B. In continuous environments, BQL and baselines are built on DDPG.
reward function of each timestep r(),
As shown in Figure 2, IQL always falls into the local optimum (total reward R 30) because of the non-stationary transition probabilities. H-IQL. only escapes the local optimum in one seed in the setting with 3 = 0.3. In neural network implementations, MA2QL and BQL use the same experi- ence collection as IQL, so there is no MA2QL- and BQL- MA2QL converges to the local optimum because it cannot guarantee that the converged equilibrium is the global optimum, especially trained using oof-po data. BQL (A 0.01) escape from local optimum in more than 4 seeds in all settings, which demonstrates the effectiveness of our optimization objectives (9) and (10). The difference between global optimum (total reward z 100) and local optimum is large, which results
8

---

Under review as a conference paper at ICLR 2023
HOSZL HHREL
1H-OL
V21
1SL
MTADCL
1C1
teeno
(a) 2 Swimmer
(b) 2 Swimmer
X 4d Ant
(d) 6|2 Ant
Figure Learning curves on Multi-Agent MoloCo.
MAPG
sanng) HHCL
BOL
(a) 2c_7g_647g
(b) 2s3z.
(c) 3s5%
(d) 1c3s5z
Figure 4: Learning curves on SMAC.
in the large variance of BQL.. In the objective (10), À controls the balance between performing best possible operator and offsetting the overestimation caused by the operator. As shown in Figure 2, the large A, i.e., 0.1, will weaken the strength of BQL, while small X, i.e. O, will cause severe overestimation and destroy the performance.
4.3 MULTI-AGENT MuJoCo
To evaluate BQL in partially observable environments, we adopt Multi-Agent MuJoCo (Peng al., 2021), where each agent independently controls one or some joints of the robot and can only observe the state of its own joints and bodies (with the parameter agent_obsk = 0). each task, we test four random seeds and plot the learning curves in Figure 3. BQL achieves higher reward or learns faster than the baselines, which verifies that BQL could applied partially observable environments. Here, we set À 0.5 and show that BQL is robust to À in Appendix C.I. In partially observable environments, BQL is performed on transition probabilities of observation Po a,), which also depends -. The convergence and optimality of BQL only be guaranteed when one obser- vation o; uniquely corresponds to one state s. has been proven that the optimality is undecidable in partially observable Markov decision processes (POMDPs) (Madani et al., 1999), it is not the limitation BQL. We only consider two-agent cases the partially observable setting, because the too limited observation range cannot support strong policies when there Appendix C.2, we test BQL. on 17-agent Humanoid with full observation to verify the scalability.
agents. In
4.4 SMAC
We also perform experiments partially observable and stochastic SMAC tasks (Samvelyan al., 2019) with the version SC2.4.10, including both easy and hard maps (Yu et al., 2021). Agent num- bers vary between 2 and 9. We build BQL the implementation of PyMARL (Samvelyan al., 2019) and train the agents for four random seeds. The learning curves are shown in Figure BQL also outperforms the baselines, which verifies that BQL can also obtain performance gain in high- dimensional complex tasks.
CONCLUSION
We propose best possible operator and theoretically prove that the policies of agents will converge to the optimal joint policy if each agent independently updates its individual state-action value by the operator. We then simplify the operator and derive BQL, the first decentralized MARL algorithm that guarantees the convergence the global optimum in stochastic environments. Empirically, BQL outperforms baselines in variety of multi-agent tasks. We believe BQL will be a new paradigm for fully decentralized learning.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Joshua Achiam. Spinning Up in Deep Reinforcement Learning. 2018.
Christian Schroeder de Witt, Tarun Gupta, Denys Makoviichuk, Viktor Makoviychuk, Philip HS Torr, Mingfei Sun, and Shimon Whiteson. Is Independent Learning All You Need in The StarCraft Multi-Agent Challenge? arXiv preprint arXiv:20/ 1.09533, 2020a.
Christian Schroeder de Witt, Bei Peng, Plerne-Alexandre Kamienny, Philip Torr, Wendelin Böhmer, and Shimon Whiteson. Deep Multi-Agent Reinforcement Learning for Decentralized Continuous Cooperative Control. arXiv preprini arXii::0033.06704 2020b.
Shariq Iqbal and Fei Sha. Actor Pioo-AAttentoo-Criiie for Multi-Agent Reinforcement Learning. In International Conference Machine Learning (ICML), 2019.
Sachin G Konan, Esmaeil Seraj, and Matthew Gombolay. Iterated reasoning with mutual informa- tion in cooperative and byzantine decentralized teaming, In International Conference on Learning Representations (ICLR), 2021.
Martin Lauer and Martin Riedmiller. An algorithm for distributed reinforcement learning in coop- erative multi-agent systems. In International Conference on Machine Learning (ICML), 2000.
Xihan Li, Jia Zhang, Jiang Bian, Yunhai Tong, and Tie- Yan Liu. A cooperative multi-agent rein- forcement learning framework for resource balancing in complex logistics network. Interna- tional Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2019.
Yucheng Li, Guangming Xie, and Zongqing Lu. Difference advantage estimation for multi-agent policy gradients. International Conference on Machine Learning (ICML), 2022.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning, In Inter- national Conference on Learning Representations (ICIR), 2016.
Ryan Lowe, Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-Agent Actor- Critic for Mixed Cooperative-Compeiiiie Environments. Neural Information Processing Systems (NeurIPS), 2017.
Omid Madani, Steve Hanks, and Anne Condon. On the undecidability of probabilistic planning and infinite-horizon partially observable markov decision problems. In AAAI/IAAI, 1999.
Laëtitia Matignon, Guillaume J Laurent, and Nadine Le Fort-Piat. Hysteretic q-learning: an algo- rithm for decentralized reinforcement learning in cooperative multi-agent teams. In JEEE/RSI International Conference Intelligent Robots and Systems (IROS), 2007.
Bei Peng, Tabish Rashid, Christian Schroeder de Witt, Pierre-Alexandre Kamienny, Philip Torr, Wendelin Böhmer, and Shimon Whiteson. Facmac: Factored multi-agent centralised policy gra- dients. Advances in Neural Information Processing Systems (NeurIPS), 2021.
Martin L Puterman. Markov decision processes: Discrete stochastic dynamic programming, 1994.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder De Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning. In International Conference Machine Learning (ICML), 2018.
Tabish Rashid, Gregory Farquhar, Bei Peng. and Shimon Whiteson. Weighted qmix: Expanding monotonic value function factorisation for deep multi-agent reinforcement learning. Advances in Neural Information Processing Systems (NeurIPS), 2020.
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt. Gregory Farquhar, Nantas Nardelli, Tim G. J. Rudner, Chia-Man Hung. Philiph H. Torr, Jakob Foerster, and Shimon Whiteson. The StarCraft Multi-Agent Challenge. arXiv preprint arXiv: 1902. 04043, 2019.
Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. QTRAN: Learn- ing To Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learning. In International Conference Machine Learning (ICML.), 2019.
10

---

Under review as a conference paper at ICLR 2023
Kefan Su and Zongqing Lu. Conference on Machine Learning (ICML), 2022.
Multi-Agent Actor-Critic. In International
Kefan Su, Siyuan Zhou, Chuang Gan, Xiangjun Wang, and Zongqing Lu. MA2QL: A min-
imalist approach fully decentralized multi-agent reinforcement learning. arXiv preprint arXiv:2209.08244 2022.
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, al. caloppeccomoosition Networks for Cooperative Multi-Agent Learning Based on Team Reward. In International Con- ference on Autonomous Agents and Multiagent Systems (AAMAS), 2018.
Ming Tan. Multi-agent reinforcement learning: Independent vs. cooperative agents. In International Conference Machine Learning (ICML), 1993.
Oriol Vinyals, Igor Babuschkin, Wojeiech Czameekk, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster Level in StarCraft II Using Multi-Agent Reinforcement Learning. Nature, 575(7782)33003354 2019.
Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. Qplex: Duplex Duel- ing Multi-Agent Q-Learnin. In International Conference on Learning Representations (ICLR), 2021a.
Jianhong Wang. Wangkun Xu, Yunjie Gu, Wenbin Song, and Tim C Green. Multi-agent reinforce- ment learning for active voltage control on power distribution networks. Advances in Neural Information Processing Systems (NeurIPS), 2021b.
Yihan Wang, Beining Han, Tonghan Wang. Heng Dong, and Chongjie Zhang. Dop: Off-policy multi-agent decomposed policy gradients. In International Conference on Learning Representa- tions (ICLR), 2020.
Bingyu Xu, Yaowei Wang, Zhaozhi Wang, Huizhu Jia, and Zongqing Lu. Hierarchically and co- operatively learning traffic signal control. In AAAI Conference Artificial Intelligence (AAAI), 2021.
Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness ppo in cooperative, multi-agent games. arXiv preprint arXiv:2103.01955. 2021.
Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. Fully decentralized multi- agent reinforcement learning with networked agents. In International Conference Machine Learning (ICML), 2018
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.
Tianhao Zhang, Yueheng Li, Chen Wang, Guangming Xie, and Zongqing Lu. FOP: Factorizing Op- timal Joint Policy of Aiximuum-Entrope Multi-Agent Reinforcement Learning. In International Conference on Machine Learning (ICML), 2021b.

---

Under review as a conference paper at ICLR 2023
A COMPARISON WITH HYSTERETIC IQL
Hysteretic IQL special case of BQL when the environment deterministic. To thoroughly illustrate that, we rewrite the loss function of BQL
w(s,aj a.) Q (s, -Ba(ollaaa) r (++ (1=xax(((((( (18 a4)
1 if (((olaa))
r (maxQ((s(, > Qi (s,a,)
of clse.
If X 0, the update of BQL is
Qi(s,a:) max (e),s,
x o ot) ( (
Hysteretic IQL. follows the loss function
w(s,a;) @1: (s) - - - .q,)
{1 if ymaxQ a4)) > Qi (s,ag)
((s, as)
else.
0, Hysteretic IQL degenerates into Distributed IQL (Lauer & Riedmiller, 2000)
Q,(s, max (Q((s,a))) + ms
BQL takes the max of the expected target on transition probability Ps(ls,,, a:), while Hysteretic IQL takes the max of the target on the next state s'. When the environment is deterministic, they equivalent. However, in stochastic environments, Hysteretic IQL cannot guarantee to converge to the global optimum since the environment will not always transition to the same s'. BQL can guarantee the global optimum in both deterministic and stochastic environments.
B EFFICIENCY OF BQL
P deterinistic π
stochastic a
p
x4
Figure 5: Space of other agents' policies æ given an (s.
We will discuss the efficiency of collecting the replay buffer for BQL. The space of other agents' policies и- given (s, a4) pair is a convex polytope. For clarity, Figure 5 shows triangle space. Each π-, corresponds to (s(' a.). Deterministic policies π locate at the vertexes, while the edges and the inside of the polytope are stochastic π- the mix of deterministic ones. Since BQL only considers deterministic policies, the buffer series only needs to cover all the vertexes by acting deterministic policies the collection of each buffer D. which efficient. BQL needs only [A.] x |A-iI IAl small buffers, which is irrelevant to state space |S], to meet the requirement of simplified best possible operator that any one of possible P,(s'|s, a.) can be found one (ideally only one) buffer given (s, a.) pair. More specifically, |A,] buffers are needed to cover action space, and [A_;]] buffers are needed to cover transition space for each action. We intuitively illustrate this in Figure 6. Each state in D.d requires # samples to estimate the expectation in (7), so the sample complexity is O[[A] S #). For the joint Q-learning (3), the most efficient known method guarantee the convergence and optimality in stochastic environments, each state-joint action pair
12

---

Under review as a conference paper at ICLR 2023
Ideally 4 buffers cover all possible P:(s, a:)
< <4h.PPo000)eccc44p000000001d1111
< oolod..Pe..d)).cccd.....
< P(t.a,.
<
Figure 6: Toy case for illustrating the ideal buffer number. |S| = 3, |A,1| = 2, and
|A_,| = corresponding to
P. and P. We can see that any (s(s, a.) can be found in the buffers.
XGL
Gendlop
Figure 7: Learning curves of BQL and joint Q-learning (JQL). BQL shows similar sample efficiency JQL.
(s, a) requires # samples to estimate the expectation, so the sample complexity is also O(IA Thus, BQL close to the joint Q-learning in terms of sample complexity, which empirically verified in Figure 7.
One may ask "since you obtain all possible transition probabilities, why not perform IQL on each transition probability and choose the highest value?" Actually, this naive algorithm can also learn the optimal policy, but the buffer collection of the naive algorithm is much more costly than that of BQL. The naive algorithm requires that any of possible transition probability functions of the whole stute-action spuce could be found in one buffer, which needs | buffers. And training IQL |A times is also formidable. BQL only requires that any one of possible transition probability of any state-action pair could be found in one buffer, which is much more efficient.
However, considering sample efficiency, BQL with neural networks only maintains one replay buffer D, containing all historical experiences, which is the same as IQL. P, in D, corresponds to the aver- age of other agents' historical policies, which is stochastic. Therefore, to guarantec the optimality, in theory, BQL with one buffer has to go through almost the whole π space, which is costly. As shown in Figure 1d, BQL- (with one buffer) outperforms IQL. but cannot achieve similar results as BQL. (with buffer series), showing that maintaining one buffer is costly but still effective. In neural network instantiation, we show the results of BQL with the buffer series in Figure Due sample efficiency, the buffer series cannot achieve strong performance, and maintaining one buffer like IQL a better choice in complex environments.
one buffer
hufive
resard
Emeettop
timatep
(a) MPE, 3
0.4
(b) 2 x Swimmer
Figure 8: BQL with one buffer and buffer series.
13

---

Under review as a conference paper at ICLR 2023
C ADDITIONAL RESULTS
C.I HYPERPARAMETER À
In the objective (10), controls the balance between performing best possible operator and offsetting the overestimation caused by the operator. We investigate the effectiveness of in Figure Too large À will weaken the strength of BQL.. When À 1.0, BQL degenerates into IQL. Too small X, i.e., 0, will cause severe overestimation and destroy the performance. When falls within the interval (0.2, 0.8), BQL could obtain performance gain, showing the robustness A.
A.00
0.00
IQU
0.
1217
(a) 2 x 3 Swimmer
(b) 2 4 Swimmer
(c) 2c_vs_647g
Figure 9: Learning curves with different X.
C.2 SCALABILITY
We test BQL on 17-agent Humanoid with full observation, the results are shown Figure 10. BQL obtains significant performance gain in this many-agent task, which can be evidence of the good scalability of BQI..
14/01
IQL
Uesutop
Figure 10: Learning curves on 17-agent Humanoid.
C.3 OTHER BASE ALGORITHMS
Besides DDPG, BQL could also be built on other variants of Q-learning, e.g., SAC. Figure 11 shows that BQL could also obtain performance gain on independent SAC. Independent PPO (IPPO) (de Witt et al., 2020a) is an on-policy decentralized MARL baseline. IPPO is not Q-learning method so cannot be the base algorithm of BQL. On-policy algorithms not use old experiences, which makes them weak sample efficiency (Achiam, 2018) especially in fully decentralized set- tings as shown in Figure/ 11.
BQL on SAC
SAC
10)
50
BQL SAC
DQQL.
IQ)
mimsttop
(a) MPE, 3 0.4
(b) 2 x 4d Ant
Figure 11: Learning curves of other base algorithms. BQL can also be naturally and theoretically applied on MA2QL. We test BQL+MA2QL three mujoco tasks used MA2QL. Figure 12 shows BQL could obtain performance gain on MA2QL, especially HalfCheetah.
14

---

Under review as a conference paper at ICLR 2023
BOL- MMADO
MAZOL
BQL-MADO.
-OLL-MAOL
MAD2
1920
trrettpp
(a) HalfCheetah, obsk (b) x
Hopper, obsk
(c) 2 Walker, obsk =
Figure 12: Learning curves of BQL+MAZQL.
We also compare BQL against MA2QL in more SMAC tasks. As shown in Figure 13, BQL and MA2QL achieve similar performance, and the converged results are very close to some CTDE meth- ods, indicating that non-stationarity is not severe problem in these two tasks.
BQL
tineeteg
nrwwep
(a) 5m VS 6m
(b) corridor
Figure 13: Learning curves in SMAC.
D MULTIPLE OPTIMAL JOINT POLICIES
We assume that there is only one optimal joint policy. With multiple optimal actions (with the max Qi a.)). if each agent arbitrarily selects one of the optimal independent actions, the joint action might not be optimal. To address this, we set a performance tolerance E and introduce fixed randomly initialized reward function f's, E (0, (1 >)e]. Then all agents perform BQL F. Since
to learn (s, a;) of the shaped reward the maximal contribution from is (1 - 7) - 7) = E, so the minimal contribution from r is (s (4) e Qi(s, - which means that the maximal performance drop is when selecting actions according to Q, is small probability event to find multiple optimal joint policies on the reward function r + F, because f(s, 8') randomly initialized. Therefore, if ε is set to be small enough, BQL could solve the task with multiple optimal joint policies. However, this technique introduced to only remedy the assumption for our theoretical results. Empirically, this is not required, because there is usually only one optimal joint policy in complex environments. In all experiments, we do not use the randomly initialized reward function for BQL and other baselines, thus the comparison is fair.
0. (s, > Qi(s, In (s a.),
We test the randomly initialized reward function on a one-stage matrix game with two optimal joint policies (1,2) and 12, shown in Figure 14. If the agents independently select actions, they might choose the miscoordinated joint policies (1, 1) and (2, IQL. cannot converge, but BQI. agents always select coordinated actions, though the value gap between the optimal policy and suboptimal policy is so small, which verifies the effectiveness of the randomly initialized reward.
A
.A(3)
9.99
0
(a) matrix game
(b) learning curves
Figure 14: Learning curves sta-stage matrix game with multiple optimal joint policies.
15

---

Under review as a conference paper at ICLR 2023
reaad of cerety
Figure 15: Curves of reward and density of V E. 22 in MPE. We plot the density of uniform state distribution. There is only one global optimum, but the donsity of local optimum high. So decentralized agents will easily learn the local optimal policies.
E HYPERPARAMETERS
In MPE-based differential games, the reward function defined as
0.5 cos( 0.5
if 0.25 0.25 < < 0.6
0
1=
2 3
Σ 2
0. 0.15 cos cos(co 0.8)) 0.15
0f < 1 1.0
i=0
0
i 1.0
And the relationship between r and is visualized in Figure 15.
In 2 x 3 Swimmer, there agents and each of them controls 3 joints of ManyAgent Swimmer. In 6/2 Ant, there are two agents. One of them controls 6 joints, and one of them controls 2 joints. And so on.
In MPE-based differential games and Multi-Agent MuJoCo, we adopt Spinning (Achiam, 2018) implementation, the SOTA implementation of DDPG, and follow all hyperparameters in Spin- ningUp. The discount factor = 0.99, the learning rate is 0.001 with Adam optimizer, the batch size is 100, the replay buffer contains 5 x 10 transitions, the hidden units are 256.
In SMAC, we adopt PyMARL (Samvelyan et al., 2019) implementation and follow all hyperpa- rameters in PyMARL. The discount factor y 0.99, the learning rate 0.0005 with RMSprop optimizer, the batch size is 32 episodes, the replay buffer contains 5000 episodes, the hidden units are 64. We adopt the version SC2.4. 10 of SMAC.
In MPE-based differential games, we set À 0.01. In Multi-Agent MuJoCo, we set À 0.5, and SMAC, we set 0.8.
The experiments are carried out on Intel i7-8700 CPU and NVIDIA GTX 1080Ti GPU. The training of each MPE and Multi-Agent MuJoCo task could be finished in hours, and the training of each SMAC task could be finished in 20 hours.
F
MORE SMAC RESULTS
We test BQL SMAC MMM2 task, the results shown in Figure 16.
IQL
Figure 16: Learning MMM2.
16


Reviews:
[{"review_id": "qoksq7veEq", "reviewer": "Reviewer_NZDY", "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": "", "summary_of_the_paper": "The paper proposes the best possible operator for decentralized learning in cooperative multi-agent games. Since the best possible operator is almost impossible to implement in practice, the authors also propose a simplified best possible operator. Experiments are conducted on simple stochastic game, stage game, MPE, MuJoCo and SMAC.\n", "summary_of_the_review": "The paper generally needs a major revision for improving its quality in terms of writing, technical contents, method description and result reports. More baseline methods should be compared. The theoretical justification needs to be provided with more details.", "strength_and_weaknesses": "Strength:\n\nThe experiments are evaluated on multiple types of tasks. The fully decentralized setting for cooperative MARL is appealing.\n\nWeaknesses:\n\nThe abstract is a bit misleading at the beginning. It does not clearly specify the scope of the research, only in the last sentence it tells that the experiments are conducted on cooperative multi-agent tasks.\n\nSec. 2.2,”To reduces the complexity, we can only consider the deterministic policies …” is not well justified.\n\nSec. 2.3 “Similar to the proof of Lemma 2, we can easily prove…” is less clear.\n\nFor the simplified best possible operator, it seems $\\tilde{P}_i$ is sampled from all possible transition probabilities, how could this effectively update $Q_i$? In practice it means to sample from all possible policies of the other agents. \n\nThe conditions and assumptions for all lemmas and theorems are not clearly specified. \n\nSeveral baseline methods are missed, like:\n\n1. Li, Hepeng, and Haibo He. \"Multi-agent trust region policy optimization.\" arXiv preprint arXiv:2010.07916 (2020).\n\n2. Kuba, Jakub Grudzien, et al. \"Trust region policy optimisation in multi-agent reinforcement learning.\" arXiv preprint arXiv:2109.11251 (2021).\n\nThe numerical results should also be provided in tables apart from just the learning curves.\n\nThere are lots of typos in the paper to be fixed.\n", "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": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "lNyJ17bIR2", "reviewer": "Reviewer_oR8C", "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": "", "summary_of_the_paper": "This paper designs a new decentralized learning algorithm in cooperative multi-agent reinforcement learning where no communication or parameter sharing among agents is allowed. From each agent’s point of view, the transition probability is non-stationary due to the other agents’ changing policies. The proposed best possible operator considers the maximum target over the available transition probabilities and is claimed to produce the optimal policy assuming the optimal joint policy is unique. Next, a simplified best-possible operator is suggested by randomly selecting one possible transition probability followed by a monotonic update and is claimed to produce the optimal joint policy under the same assumption. The authors practically applied the operator to action-value function learning with neural networks, and numerical results showed promising results in some cooperative multi-agent environments.", "summary_of_the_review": "The target of this paper is fully decentralized multi-agent reinforcement learning (MARL), an emerging area in the MARL community. However, the numerical study should be expanded and the proposed algorithm should be fairly compared with the baselines, guaranteeing reproducibility verification. In addition, the authors need to clarify unclear technical explanations to support the main claim. \n\n", "strength_and_weaknesses": "Strength: This paper is overall well-written and easy to read. The authors tried to show theoretical support for the proposed algorithm under a specific assumption.\n\nWeaknesses: The authors lack experiments for fair comparisons with the considered baselines. In addition, there is a gap between the proposed simplified operator and its implementation regarding sampling data. Reproducibility could not be well verified. Investigation into the multiple optimal policies was not considered. Please see the following comments and questions.\n\n\n<Comments>\n\nC1. Regarding a fair comparison with MA2QL\n\n- The MA2QL paper states that “for a fair comparison, the total number of Q-function updates for each agent in MA2QL is set to be the same with that in IQL.” Is this rule explicitly applied to the conducted experiments? Please clarify the (fine-tuned) training steps for updating an agent at each turn in every environment.\n- In Fig.4, there are three easy SMAC environments and one hard environment (2c_vs_64zg). In MA2QL paper, three other environments are considered(3s_vs_4z (easy), 5m_vs_6m (hard) and\ncorridor (super hard)). Among the three environments, MA2QL shows superiority over IQL in the latter two environments. For a fair comparison with MA2QL, SMAC experiments in those three environments should be performed.\n- In Multi-agent Mujoco, BQL only considered two-agent cases in the partially observable setting, which seems an empirical limitation of this paper. On the other hand, MA2QL conducted experiments on 2-agent HalfCheetah, 3-agent Hopper, and partially observable 3-agent Walker2d in multi-agent MuJoCo. For a fair comparison with MA2QL,  Multi-agent Mujoco experiments in those three environments are required.\n\nC2. Regarding a fair comparison with H-IQL\n\n- As far as I understand, the H-IQL method represents the equation in Appendix A. If yes, then the authors should report the (fine-tuned) value of $\\lambda (<1)$.\n\nC3. Regarding sampling from the replay buffer\n\n- In my opinion, the (hidden) key part of BQL is how to sample data as well as the formulation itself in Eqs. 9 and 10. There is a gap between Eq. 7 and Eq. 9 (with one replay buffer) regarding sampling data. The authors explicitly need any method to reduce the gap. For example, I think the minibatch should contain samples from “similar” transitions. Partitioning one buffer into several parts in chronological order, and choosing one part of them for sampling can apply to Eq. 7. (Note that this partitioning is different from using buffer series in Appendix B since the former uses one buffer, but just changes the sampling method inside the same buffer.)\n- Can we guarantee that $\\mathcal{D}_i$ sufficiently goes through all possible transition probabilities? (page 6)\n- On page 5 and Appendix B, the authors claim the sample efficiency of Eq. 7 over Eq. 6. While Eq. 7 is practical since we ideally require samples from every $\\pi_{-i}$ to compute Eq. 6. However, other than that, the explanation in the second paragraph on page 13 is not clearly understood, especially the complexity of Eq.6. In my opinion, this additional explanation requires clarification.\n\n\nC4. Regarding multiple optimal policies & scalability\n\n- We can extend the matrix game on page 8 to observe what happens to BQL when there are multiple optimal policies. We can also check whether the proposed approach in Appendix D is practically applicable in this case. \n- Another promising experiment can be a scalability test on the SMAC environment (e.g., 10m vs 11m, 27m vs 30m, bane_bane) since there may be a relatively higher possibility of multiple optimal policies when the number of (homogeneous) agents increases. This SMAC test can also strengthen the scalability of BQL. (I checked Appendix C.2.)\n\nC5. Regarding reproducibility \n\n- I could not check the reproducibility of the experiments as the authors did not provide their implementation codes.\n- Why are the performance of IQL in 2c_vs_64zg and 1c3s5z much higher than those in *Samvelyan et al. (2019)? In the paper, the win rates are 7% and 21%, respectively, while in this paper, about 50% and 70%, respectively. Did the authors tune the IQL code? * Samvelyan et al., The StarCraft Multi-Agent Challenge, 2019.\n- For clarity, do the BQL, H-IQL, and IQL use synchronized sampling (i.e., each agent samples the same episodes) or not? \n\n\n<Questions>\n\n1. On page 3, does “$Q_i^0$ is initialized to be the minimal return” mean  $Q_i^0=-r_{min}$? Does this initialization is applied in Algorithms 1 and 2? (I could not find any explicit mention regarding this.)\n2. Are the proofs of Lemma 2, 3, and 4 available for stochastic $\\pi_{-i}$? For example, the first inequality in Lemma 2 may be valid for $P_i^*$ under stochastic $\\pi_{-i}$. If yes, is that a reason for considering only deterministic policies? \n3. On page 5, can the authors clarify how to select “a subset of state $S_i^m$”?\n4. Instead of Eq.10, can we directly apply the max operation as seen in Eq. 8?\n5. Could you explain “the positive random noise of $Q_i$”? (page 6) The necessity of $\\lambda$ in Eq. 10 is empirically appealing, but less conceptually.\n6. Regarding independent SAC in Appendix C.3\n- How can BQL be applied to SAC as (i) SAC contains entropy term and (ii) the considered policy is stochastic, unlike deterministic in DDPG? This part should be clarified with the explicit formulation.\n- Does independent SAC use two Q functions for each agent? Two $\\bar{Q}_i^e$ functions for each agent? \n- What is the base code for implementing independent SAC?\n\n7. What is the target update period or coefficient in Line 8 of Algorithm 2?\n8. On page 8, it seems that “the narrow region $r>3$ is surrounded by the region with $r=0$” is written in reverse order. \n9. Is there any explanation regarding the fine-tuned value of $\\lambda$ increasing as the environment becomes more complicated?\n\nMinor: $max_{P_i(s'|s,a)} \\rightarrow max_{P_i(\\cdot|s,a)}$ in Eq.6.\n", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JFzNhUnfYx5", "reviewer": "Reviewer_hhze", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes what they call \"the best possible operator\" for decentralized Q-learning when there are multiple agents. The operator updates the policies of each agent individually at each step and can be shown to converge to the optimal joint policy. However, the operator is too complex and impractical. What the paper really proposes is the \"simplified best possible operator\" which computes only one of the possible transition probabilities but still can be proved to converge to the best optimal policy. The algorithm is then called \"best possible Q-learning (BQL).  The algorithm can be implemented with a Q-table for each agent por with a neural network for each agent. The paper evaluates BQL on a variety of tasks (stochastic games, etc) and compares the performance with the performance of different algorithms.", "summary_of_the_review": "A well-written paper that presents an algorithm, BQL, for multi-agent reinforcement learning that guarantees the learning process will converge to the optimal joint policy when the optimal policy is unique.  BQL is computationally more efficient than algorithms that explore all possible transition probabilities.", "strength_and_weaknesses": "Strengths: There is novelty in the algorithms proposed and the guarantee to converge to the joint optimal policy is important. The optimality of the joint policy found is proved formally. \nWeaknesses: Finding the optimal policy is guaranteed only when there is only one optimal policy.  This is reported in the Appendix, not in the paper. Many results are shown in the Appendix. There are many acronyms, but not all of them are defined.", "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": "8z4kcOTRiq", "reviewer": "Reviewer_o76z", "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": "", "summary_of_the_paper": "The paper proposes _best possible Q-learning_, a multiagent reinforcement learning approach that - being decentralized - ensures convergence to optimality. The paper assumes full state observability, i.e., all agents have access to the full state of the environment. To ensure convergence to the optimal joint policy, the paper introduces the _best possible operator_, which at its core is similar to a Bellman operator for each agent $n$ in a multiagent MDP that considers that the other agents follow a greedy policy, i.e., agent $n$'s $Q$-function, $Q_n$, is updated as\n\n$$Q_n(s,a_n)\\leftarrow\\max_{a_{-n}}\\mathbb{E}[r+\\gamma\\max_{a'}Q_n(s',a')\\mid s'\\sim P(\\cdot\\mid s,a_n,a_{-n})],$$\n\nwith $a'\\in A_n$. The paper actually uses a more evolved formulation for $\\mathcal{T}$ using transition probabilities, but unless if I missed something, it seems to me that it is equivalent to the one above. The paper then proposes a _simplified best possible operator_, where the maximization over $a_{-n}$ is replaced by a (fixed) arbitrary choice of $a_{-n}$, leading to the computation of an intermediate Q-value, dubbed $Q^e_n$, such that\n\n$$Q^e_n(s,a_n)=\\mathbb{E}[r+\\gamma\\max_{a'}Q_n(s',a')\\mid s'\\sim P(\\cdot\\mid s,a_n,a_{-n})],$$\n\nleading to the update\n\n$$Q_n(s,a_n)\\leftarrow\\max(Q_n(s,a_n),Q^e_n(s,a_n)).$$\n\nThe above operator is then turned into a Q-learning algorithm, by allowing the different agents to interact in episodes where their policy is essentially held fixed. The experiences collected during different episodes provide an estimate for $Q^e_n$ above, and $Q_n$ is then updated accordingly.", "summary_of_the_review": "The problem addressed in the paper is relevant (although in a somewhat constricted setting) and the contribution novel and interesting. There are some aspects of the contribution that could be discussed in greater detail. ", "strength_and_weaknesses": "**Strengths**\n\nThe paper addresses an interesting problem and provides an interesting approach, which is reminiscent of the distributed IQL of Lauer and Riedmiller mentioned in the paper. \n\n**Weaknesses**\n\nThe fact that the paper assumes full state observability is, in my view, an important setback, given current research in MARL mostly considers that agents have only access to local observations. Granted, the paper does evaluate its approach in a partially observable setting, but (i) the theoretical grounding of the algorithm does not hold for partially observable settings (at least not directly); (ii) from the portrayed experiments it is difficult (at least for me) to assess how robust the algorithm is to general partially observable settings. \n\nAnother important aspect that is not discussed significantly in the paper is related with _coordination_, since in scenarios where multiple policies exist it does not seem to me that the agents necessarily converge to a coordinated policy. The paper refers to Appendix D for a solution to the case where multiple optimal policies may exist (which I'm convinced is the most common scenario), but I believe that this is an important issue that should have its space in the main body of the paper. ", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject