Best Possible Q-Learning

## Abstract

Abstract Fully decentralized learning, where the global information, i.e. , the actions of other agents, is inaccessible, is a fundamental challenge in cooperative 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 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.

## 1 Introduction

Cooperative multi-agent reinforcement learning (MARL) trains a group of agents to maximize the cumulative shared reward, which has great significance for real-world applications, including logistics (Li et al., ), traffic signal control (Xu et al., ), power dispatch (Wang et al., ), and games (Vinyals et al., ). Although most existing 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 (Jiang & Lu, ).

However, in fully decentralized learning, as other agents are treated as a 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, ), is not theoretically guaranteed. Multi-agent alternate Q-learning (MA2QL) (Su et al., ) 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., ). Distributed IQL (Lauer & Riedmiller, ) and I2Q (Jiang & Lu, ) can learn the optimal joint policy, yet are limited to deterministic environments.
How to 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 possible 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 computes 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 the Q-table instantiation, non-stationarity is instinctively avoided, and in the neural network instantiation, non-stationarity in the replay buffer is no longer a drawback, but a necessary condition for convergence.

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., ), Multi-Agent MuJoCo (de Witt et al., ), SMAC (Samvelyan et al., ), and GRF (Kurach et al., ), covering fully and partially observable, deterministic 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. More simplifications and instantiations of best possible operator can be further explored. We believe BQL can be a new paradigm for fully decentralized learning.

## 2 Method

### 2.1 Preliminaries

Consider $N$-agent MDP $M_{\mathrm{env}}=<\mathcal{S},\mathcal{O},\mathcal{A},R,P_{\mathrm{env}},\gamma>$ with the state space $\mathcal{S}$ and the joint action space $\mathcal{A}$. Each agent $i$ chooses an individual action $a_{i}$, and the environment transitions to the next state $s^{\prime}$ by taking the joint action $\boldsymbol{a}$ with the transition probabilities $P_{\mathrm{env}}\left(s^{\prime}|s,\boldsymbol{a}\right)$. For simplicity of theoretical analysis, we assume all agents obtain the state $s$, though in practice each agent $i$ can make decisions using local observation $o_{i}\in\mathcal{O}$ or trajectory. All agents obtain a shared reward $r=R\left(s,s^{\prime}\right)\in[r_{\min},r_{\max}]$ and learn to maximize the expected discounted return $\mathbb{E}\sum_{t=0}^{\infty}\gamma^{t}r_{t}$. In fully decentralized setting, $M_{\mathrm{env}}$ is partially observable, since each agent $i$ only observes its own action $a_{i}$ instead of the joint action $\boldsymbol{a}$. From the perspective of each agent $i$, there is an MDP $M_{i}=<\mathcal{S},\mathcal{A}_{i},R,P_{i},\gamma>$ with the individual action space $\mathcal{A}_{i}$ and the transition probabilities

$$ $P_{i}\left(s^{\prime}|s,a_{i}\right)={\sum}_{\boldsymbol{a}_{-i}}P_{\mathrm{env}}\left(s^{\prime}|s,a_{i},\boldsymbol{a}_{-i}\right)\boldsymbol{\pi}_{-i}(\boldsymbol{a}_{-i}|s)$ (1) $$

where $\boldsymbol{\pi}_{-i}$ denotes the joint policy of all agents except agent $i$, similarly for $\boldsymbol{a}_{-i}$.
According to ([1](#S2.E1)), the transition probabilities $P_{i}$ depend on the policies of other agents $\boldsymbol{\pi}_{-i}$. As other agents are updating their policies continuously, $P_{i}$ becomes non-stationary. On the non-stationary transition probabilities, the convergence of independent Q-learning(^1^11For simplicity, we refer to the optimal value $Q^{*}$ as $Q$ in this paper, unless stated otherwise.)

$$ $Q_{i}(s,a_{i})=\mathbb{E}_{P_{i}(s^{\prime}|s,a_{i})}\left[r+\gamma\underset{a^{\prime}_{i}}{\max}Q_{i}(s^{\prime},a^{\prime}_{i})\right]$ (2) $$

is not guaranteed, and how to learn the optimal joint policy in fully decentralized settings is quite a challenge. In the next section, we propose best possible operator, a 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(s,\bm{a})=\mathbb{E}_{P_{\mathrm{env}}(s^{\prime}|s,\bm{a})}\left[r+\gamma\underset{\bm{a}^{\prime}}{\max}Q(s^{\prime},\bm{a}^{\prime})\right],$ (3) $$

which is the expected return of the optimal joint policy $\boldsymbol{\pi}^{*}(s)=\arg\max_{\boldsymbol{a}}Q(s,\boldsymbol{a})$. Based on the optimal joint Q-value, for each agent $i$, we define $\max_{\boldsymbol{a}_{-i}}Q(s,a_{i},\boldsymbol{a}_{-i})$, which follows the fixed point equation:

$$ $\displaystyle\underset{\boldsymbol{a}_{-i}}{\max}Q(s,a_{i},\boldsymbol{a}_{-i})$ $\displaystyle=$ $\displaystyle\underset{\boldsymbol{a}_{-i}}{\max}\ \mathbb{E}_{P_{\mathrm{env}}\left(s^{\prime}|s,\boldsymbol{a}\right)}\left[r+\gamma\underset{{a}^{\prime}_{i}}{\max}\ \underset{\boldsymbol{a}^{\prime}_{-i}}{\max}Q(s,{a}^{\prime}_{i},\boldsymbol{a}^{\prime}_{-i})\right]$ (4) $\displaystyle=$ $\displaystyle\mathbb{E}_{P_{\mathrm{env}}\left(s^{\prime}|s,a_{i},\boldsymbol{\pi}^{*}_{-i}(s,a_{i})\right)}\left[r+\gamma\underset{{a}^{\prime}_{i}}{\max}\ \underset{\boldsymbol{a}^{\prime}_{-i}}{\max}Q(s,{a}^{\prime}_{i},\boldsymbol{a}^{\prime}_{-i})\right]$ (5) $$

where $\boldsymbol{\pi}_{-i}^{*}(s,a_{i})={\arg\max}_{\boldsymbol{a}_{-i}}Q(s,a_{i},\boldsymbol{a}_{-i})$ is the optimal conditional joint policy of other agents given $a_{i}$. ([4](#S2.E4)) is from taking $\max_{\bm{a}_{-i}}$ on both sides of ([3](#S2.E3)), and ([5](#S2.E5)) is by folding $\boldsymbol{\pi}_{-i}^{*}(s,a_{i})$ into $P_{\mathrm{env}}$. Then we have the following lemma.

###### Lemma 2.1 .

If each agent $i$ learns the independent value function $Q_{i}(s,a_{i})=\max_{\boldsymbol{a}_{-i}}Q(s,a_{i},\boldsymbol{a}_{-i})$, and takes actions as $\arg\max_{a_{i}}Q_{i}(s,a_{i})$, the agents will obtain the optimal joint policy when there is only one optimal joint policy(^2^22We can use the simple solution proposed in I2Q to deal with multiple optimal joint policies, which is included in Appendix [D](#A4).).

###### Proof.

As $\max_{{a}_{i}}\max_{\boldsymbol{a}_{-i}}Q(s,{a}_{i},\boldsymbol{a}_{-i})=\max_{\bm{a}}Q(s,\bm{a})$ and there is only one optimal joint policy, $\arg\max_{a_{i}}Q_{i}(s,a_{i})$ is the action of agent $i$ in the optimal joint action $\bm{a}$.
∎

According to Lemma [2.1](#S2.Thmtheorem1), to obtain the optimal joint policy is to let each agent $i$ learn the value function $Q_{i}(s,a_{i})=\max_{\boldsymbol{a}_{-i}}Q(s,a_{i},\boldsymbol{a}_{-i})$. To this end, we propose a new operator to update $Q_{i}$ in a fully decentralized way:

$$ $Q_{i}(s,a_{i})=\underset{P_{i}(\cdot|s,a_{i})}{\max}\mathbb{E}_{P_{i}(s^{\prime}|s,a_{i})}\left[r+\gamma\underset{a^{\prime}_{i}}{\max}Q_{i}(s^{\prime},a^{\prime}_{i})\right].$ (6) $$

Given $s$ and $a_{i}$, there will be numerous $P_{i}(s^{\prime}|s,a_{i})$ due to different other agents’ policies $\boldsymbol{\pi}_{-i}$. To reduce the complexity, we only consider the deterministic policies, because when there is only one optimal joint policy, the optimal joint policy must be deterministic (Puterman, ). So the operator ([6](#S2.E6)) takes the maximum only over the transition probabilities $P_{i}(s^{\prime}|s,a_{i})$ under deterministic $\boldsymbol{\pi}_{-i}$.
Intuitively, the operator continuously pursues the ‘best possible expected return’, until $Q_{i}$ reaches the optimal expected return $\max_{\boldsymbol{a}_{-i}}Q(s,a_{i},\boldsymbol{a}_{-i})$, so we name the operator ([6](#S2.E6)) best possible operator. In the following, we theoretically prove that $Q_{i}(s,a_{i})$ converges to $\max_{\boldsymbol{a}_{-i}}Q(s,a_{i},\boldsymbol{a}_{-i})$ under best possible operator, thus the agents learn the optimal joint policy. Let $Q_{i}^{k}(s,a_{i})$ denote the value function in the update $k$ and $Q_{i}(s,a_{i}):=Q_{i}^{\infty}(s,a_{i})$. Then, we have the following lemma.

###### Lemma 2.2 .

If $Q_{i}^{0}$ is initialized to be the minimal return $\frac{r_{\min}}{1-\gamma}$, $\max_{\boldsymbol{a}_{-i}}Q(s,a_{i},\boldsymbol{a}_{-i})\geq Q^{k}_{i}(s,a_{i}),\forall s,a_{i},\forall k,$ under best possible operator.

###### Proof.

We prove the lemma by induction. First, as $Q_{i}^{0}$ is initialized to be the minimal return, $\max_{\boldsymbol{a}_{-i}}Q(s,a_{i},\boldsymbol{a}_{-i})\geq Q^{0}_{i}(s,a_{i})$. Then, suppose $\max_{\boldsymbol{a}_{-i}}Q(s,a_{i},\boldsymbol{a}_{-i})\geq Q^{k-1}_{i}(s,a_{i}),\,\forall s,a_{i}$. By denoting $\arg\max_{P_{i}(s^{\prime}|s,a_{i})}\mathbb{E}_{P_{i}(s^{\prime}|s,a_{i})}\left[r+\gamma\max_{a^{\prime}_{i}}Q^{k-1}_{i}(s^{\prime},a^{\prime}_{i})\right]$ as $P^{*}_{i}(s^{\prime}|s,a_{i})$, we have

$$ $\displaystyle\underset{\boldsymbol{a}_{-i}}{\max}Q(s,a_{i},\boldsymbol{a}_{-i})-Q^{k}_{i}(s,a_{i})$ $\displaystyle=$ $\displaystyle\underset{\boldsymbol{a}_{-i}}{\max}\sum_{s^{\prime}}P_{\mathrm{env}}\left(s^{\prime}|s,a_{i},\boldsymbol{a}_{-i}\right)\left[r+\gamma\max_{{a}^{\prime}_{i}}\underset{\boldsymbol{a}^{\prime}_{-i}}{\max}Q(s^{\prime},{a}^{\prime}_{i},\boldsymbol{a}^{\prime}_{-i})\right]$ $\displaystyle\qquad\qquad-\sum_{s^{\prime}}P^{*}_{i}(s^{\prime}|s,a_{i})\left[r+\gamma\underset{a^{\prime}_{i}}{\max}Q^{k-1}_{i}(s^{\prime},a^{\prime}_{i})\right]$ $\displaystyle\geq$ $\displaystyle\sum_{s^{\prime}}P^{*}_{i}(s^{\prime}|s,a_{i})\left[r+\gamma\max_{{a}^{\prime}_{i}}\underset{\boldsymbol{a}^{\prime}_{-i}}{\max}Q(s^{\prime},{a}^{\prime}_{i},\boldsymbol{a}^{\prime}_{-i})\right]$ $\displaystyle\qquad\qquad-\sum_{s^{\prime}}P^{*}_{i}(s^{\prime}|s,a_{i})\left[r+\gamma\underset{a^{\prime}_{i}}{\max}Q^{k-1}_{i}(s^{\prime},a^{\prime}_{i})\right]$ $\displaystyle=$ $\displaystyle\gamma\sum_{s^{\prime}}P^{*}_{i}(s^{\prime}|s,a_{i})\max_{{a}^{\prime}_{i}}\left(\underset{\boldsymbol{a}^{\prime}_{-i}}{\max}Q(s^{\prime},{a}^{\prime}_{i},\boldsymbol{a}^{\prime}_{-i})-Q^{k-1}_{i}(s^{\prime},a^{\prime}_{i})\right)$ $\displaystyle\geq$ $\displaystyle\gamma\sum_{s^{\prime}}P^{*}_{i}(s^{\prime}|s,a_{i})\left(\underset{\boldsymbol{a}^{\prime}_{-i}}{\max}Q(s^{\prime},{a}^{\prime*}_{i},\boldsymbol{a}^{\prime}_{-i})-Q^{k-1}_{i}(s^{\prime},{a}^{\prime*}_{i})\right)$ $\displaystyle\geq$ $\displaystyle 0,$ $$

where ${a}^{\prime*}_{i}=\arg\max_{a^{\prime}_{i}}Q^{k-1}_{i}(s^{\prime},{a}^{\prime}_{i})$. Thus, it holds in the update $k$. By the principle of induction, the lemma holds for all updates.
∎

Intuitively, $\max_{\boldsymbol{a}_{-i}}Q(s,a_{i},\boldsymbol{a}_{-i})$ is the optimal expected return after taking action $a_{i}$, so it is the upper bound of $Q_{i}(s,a_{i})$. Further, based on Lemma [2.2](#S2.Thmtheorem2), we have the following lemma.

###### Lemma 2.3 .

$Q_{i}(s,a_{i})$ converges to $\max_{\boldsymbol{a}_{-i}}Q(s,a_{i},\boldsymbol{a}_{-i})$ under best possible operator.

###### Proof.

For clear presentation, we use $P_{\mathrm{env}}\left(s^{\prime}|s,a_{i},\boldsymbol{\pi}^{*}_{-i}\right)$ to denote $P_{\mathrm{env}}\left(s^{\prime}|s,a_{i},\boldsymbol{\pi}^{*}_{-i}(s,a_{i})\right)$. From ([5](#S2.E5)) and ([6](#S2.E6)), we have

$$ $\displaystyle\Big{\|}\underset{\boldsymbol{a}_{-i}}{\max}Q(s,a_{i},\boldsymbol{a}_{-i})-Q^{k}_{i}(s,a_{i})\Big{\|}_{\infty}$ $\displaystyle=$ $\displaystyle\underset{s,a_{i}}{\max}\left(\sum_{s^{\prime}}P_{\mathrm{env}}\left(s^{\prime}|s,a_{i},\boldsymbol{\pi}^{*}_{-i}\right)\left[r+\gamma\max_{{a}^{\prime}_{i}}\underset{\boldsymbol{a}^{\prime}_{-i}}{\max}Q(s^{\prime},{a}^{\prime}_{i},\boldsymbol{a}^{\prime}_{-i})\right]\right.$ $\displaystyle\left.-\sum_{s^{\prime}}P^{*}_{i}(s^{\prime}|s,a_{i})\left[r+\gamma\underset{a^{\prime}_{i}}{\max}Q^{k-1}_{i}(s^{\prime},a^{\prime}_{i})\right]\right)\leftarrow(\text{Lemma \ref{lemma:2}})$ $\displaystyle\leq$ $\displaystyle\underset{s,a_{i}}{\max}\left(\sum_{s^{\prime}}P_{\mathrm{env}}\left(s^{\prime}|s,a_{i},\boldsymbol{\pi}^{*}_{-i}\right)\left[r+\gamma\max_{{a}^{\prime}_{i}}\underset{\boldsymbol{a}^{\prime}_{-i}}{\max}Q(s^{\prime},{a}^{\prime}_{i},\boldsymbol{a}^{\prime}_{-i})\right]\right.$ $\displaystyle\quad\left.-\sum_{s^{\prime}}P_{\mathrm{env}}\left(s^{\prime}|s,a_{i},\boldsymbol{\pi}^{*}_{-i}\right)\left[r+\gamma\underset{a^{\prime}_{i}}{\max}Q^{k-1}_{i}(s^{\prime},a^{\prime}_{i})\right]\right)$ $\displaystyle\leq$ $\displaystyle\gamma\underset{s^{\prime},a^{\prime}_{i}}{\max}\left(\underset{\boldsymbol{a^{\prime}}_{-i}}{\max}Q(s^{\prime},a^{\prime}_{i},\boldsymbol{a^{\prime}}_{-i})-Q^{k-1}_{i}(s^{\prime},a^{\prime}_{i})\right)$ $\displaystyle=$ $\displaystyle\gamma\Big{\|}\underset{\boldsymbol{a}_{-i}}{\max}Q(s,a_{i},\boldsymbol{a}_{-i})-Q^{k-1}_{i}(s,a_{i})\Big{\|}_{\infty}.$ $$

We have $\left\|\max_{\boldsymbol{a}_{-i}}Q(s,a_{i},\boldsymbol{a}_{-i})-Q^{k}_{i}(s,a_{i})\right\|_{\infty}\leq\gamma^{k}\left\|\max_{\boldsymbol{a}_{-i}}Q(s,a_{i},\boldsymbol{a}_{-i})-Q^{0}_{i}(s,a_{i})\right\|_{\infty}$. Let $k\rightarrow\infty$, then $Q_{i}(s,a_{i})\rightarrow\max_{\boldsymbol{a}_{-i}}Q(s,a_{i},\boldsymbol{a}_{-i})$, thus the lemma holds.
∎

According to Lemma [2.1](#S2.Thmtheorem1) and [2.3](#S2.Thmtheorem3), we immediately have:

###### Theorem 2.4 .

The agents learn the optimal joint policy under best possible operator.

###### Lemma 2.1 .

###### Proof.

###### Lemma 2.2 .

###### Proof.

###### Lemma 2.3 .

###### Proof.

###### Theorem 2.4 .

### 2.3 Simplified Best Possible Operator

Best possible operator guarantees the convergence to the optimal joint policy. However, to perform ([6](#S2.E6)), every update, each agent $i$ has to compute the expected values of all possible transition probabilities and update $Q_{i}$ to be the maximal expected value, which is too costly. Therefore, we introduce an auxiliary value function $Q^{\mathrm{e}}_{i}(s,a_{i})$, and simplify ([6](#S2.E6)) into two operators. First, at each update, we randomly select one of possible transition probabilities $\tilde{P}_{i}$ for each $(s,a_{i})$ and update $Q^{\mathrm{e}}_{i}(s,a_{i})$ by

$$ $Q^{\mathrm{e}}_{i}(s,a_{i})=\mathbb{E}_{\tilde{P}_{i}(s^{\prime}|s,a_{i})}\left[r+\gamma\underset{a^{\prime}_{i}}{\max}Q_{i}(s^{\prime},a^{\prime}_{i})\right].$ (7) $$

$Q^{\mathrm{e}}_{i}(s,a_{i})$ represents the expected value of the selected transition probabilities. Then we monotonically update $Q_{i}(s,a_{i})$ by

$$ $Q_{i}(s,a_{i})=\max\left(Q_{i}(s,a_{i}),Q^{\mathrm{e}}_{i}(s,a_{i})\right).$ (8) $$

We define ([7](#S2.E7)) and ([8](#S2.E8)) together as simplified best possible operator. By performing simplified best possible operator, $Q_{i}(s,a_{i})$ is efficiently updated towards the maximal expected value. And we have the following lemma.

###### Lemma 2.5 .

$Q_{i}(s,a_{i})$ converges to $\max_{\boldsymbol{a}_{-i}}Q(s,a_{i},\boldsymbol{a}_{-i})$ under simplified best possible operator.

###### Proof.

According to ([8](#S2.E8)), as $Q_{i}(s,a_{i})$ is monotonically increased, $Q^{k}_{i}(s,a_{i})\geq Q^{k-1}_{i}(s,a_{i})$ in the update $k$. Similar to the proof of Lemma [2.2](#S2.Thmtheorem2), we can easily prove $\max_{\boldsymbol{a}_{-i}}Q(s,a_{i},\boldsymbol{a}_{-i})\geq Q^{k}_{i}(s,a_{i})$ under ([7](#S2.E7)) and ([8](#S2.E8)). Thus, $\{Q^{k}_{i}(s,a_{i})\}$ is an increasing sequence and bounded above. According to the monotone convergence theorem, $\{Q^{k}_{i}(s,a_{i})\}$ converges when $k\rightarrow\infty$, and let $Q_{i}(s,a_{i}):=Q^{\infty}_{i}(s,a_{i})$.

Then we prove that the converged value $Q_{i}(s,a_{i})$ is equal to $\max_{\boldsymbol{a}_{-i}}Q(s,a_{i},\boldsymbol{a}_{-i})$. Due to monotonicity and convergence, $\forall\epsilon,s,a_{i},\exists K,\text{when }k>K,\,Q^{k}_{i}(s,a_{i})-Q^{k-1}_{i}(s,a_{i})\leq\epsilon$, no matter which $\tilde{P}_{i}$ is selected in the update $k$. Since each $\tilde{P}_{i}$ is possible to be selected, when selecting $\tilde{P}_{i}(s^{\prime}|s,a_{i})=\arg\max_{P_{i}(s^{\prime}|s,a_{i})}\mathbb{E}_{P_{i}(s^{\prime}|s,a_{i})}\left[r+\gamma\max_{a^{\prime}_{i}}Q^{k-1}_{i}(s^{\prime},a^{\prime}_{i})\right]=P^{*}_{i}(s^{\prime}|s,a_{i}),$
by performing ([7](#S2.E7)) and ([8](#S2.E8)), we have

$$ $\displaystyle Q^{k-1}_{i}(s,a_{i})+\epsilon\geq Q^{k}_{i}(s,a_{i})\geq Q^{\mathrm{e}}_{i}(s,a_{i})$ $\displaystyle=\sum_{s^{\prime}}P^{*}_{i}(s^{\prime}|s,a_{i})\left[r(s,s^{\prime})+\gamma\underset{a^{\prime}_{i}}{\max}Q^{k-1}_{i}(s^{\prime},a^{\prime}_{i})\right].$ $$

According to the proof of Lemma [2.3](#S2.Thmtheorem3), we have

$$ $\displaystyle\underset{s,a_{i}}{\max}\left(\underset{\boldsymbol{a}_{-i}}{\max}Q(s,a_{i},\boldsymbol{a}_{-i})-Q^{\mathrm{e}}_{i}(s,a_{i})\right)$ $\displaystyle\leq\gamma\underset{s,a_{i}}{\max}\left(\underset{\boldsymbol{a}_{-i}}{\max}Q(s,a_{i},\boldsymbol{a}_{-i})-Q^{k-1}_{i}(s,a_{i})\right).$ $$

Use $s^{*},a^{*}_{i}$ to denote

$$ $\arg\max_{s,a_{i}}\left(\max_{\boldsymbol{a}_{-i}}Q(s,a_{i},\boldsymbol{a}_{-i})-Q^{k-1}_{i}(s,a_{i})\right).$ $$

Since $Q^{k-1}_{i}(s,a_{i})+\epsilon\geq Q^{\mathrm{e}}_{i}(s,a_{i}),$

$$ $\displaystyle\underset{\boldsymbol{a}_{-i}}{\max}Q(s^{*},a^{*}_{i},\boldsymbol{a}_{-i})-Q^{k-1}_{i}(s^{*},a^{*}_{i})-\epsilon$ $\displaystyle\leq\gamma\underset{\boldsymbol{a}_{-i}}{\max}Q(s^{*},a^{*}_{i},\boldsymbol{a}_{-i})-\gamma Q^{k-1}_{i}(s^{*},a^{*}_{i}).$ $$

Then, we have

$$ $\Big{\|}\max_{\boldsymbol{a}_{-i}}Q(s,a_{i},\boldsymbol{a}_{-i})-Q^{k-1}_{i}(s,a_{i})\Big{\|}_{\infty}\leq\frac{\epsilon}{1-\gamma}.$ $$

Thus, $Q_{i}(s,a_{i})$ converges to $\max_{\boldsymbol{a}_{-i}}Q(s,a_{i},\boldsymbol{a}_{-i})$.
∎

According to Lemma [2.1](#S2.Thmtheorem1) and [2.5](#S2.Thmtheorem5), we also have:

###### Theorem 2.6 .

The agents learn the optimal joint policy under simplified best possible operator.

###### Lemma 2.5 .

###### Proof.

###### Theorem 2.6 .

### 2.4 Best Possible Q-Learning

Best possible Q-learning (BQL) is instantiated on simplified best possible operator. We first consider learning Q-table for tabular cases. The key challenge is how to obtain all possible transition probabilities under deterministic $\boldsymbol{\pi}_{-i}$ during learning. To solve this issue, the whole training process is divided into $M$ epochs. At the epoch $m$, each agent $i$ randomly and independently initializes a deterministic policy $\hat{\pi}_{i}^{m}$ and selects a subset of states $S_{i}^{m}$. Then each agent $i$ interacts with the environment using the deterministic policy

$$ $\left\{\begin{matrix}\arg\max_{a_{i}}Q_{i}(s,a_{i})&\text{if }s\notin S_{i}^{m},\\ \hat{\pi}_{i}^{m}(s)&\text{else}.\end{matrix}\right.$ $$

Each agent $i$ stores independent experiences $(s,a_{i},s^{\prime},r)$ in the replay buffer $\mathcal{D}_{i}^{m}$. As $P_{i}$ depends on $\boldsymbol{\pi}_{-i}$ and agents act deterministic policies, $\mathcal{D}_{i}^{m}$ contains one $P_{i}$ under a deterministic $\boldsymbol{\pi}_{-i}$. Since $P_{i}$ will change if other agents modify their policies $\boldsymbol{\pi}_{-i}$, acting the randomly initialized policy $\hat{\pi}_{i}^{m}$ on $S_{i}^{m}$ in the epoch $m$ not only helps each agent $i$ to explore state-action pairs, but also helps other agents to explore possible transition probabilities. When $M$ is sufficiently large, given any $(s,a_{i})$ pair, any $P_{i}(s,a_{i})$ can be found in a replay buffer.

After interaction of the epoch $m$, each agent $i$ has a buffer series $\{\mathcal{D}_{i}^{1},\cdots,\mathcal{D}_{i}^{m}\}$, each of which has different transition probabilities. At training period of the epoch $m$, each agent $i$ randomly selects one replay buffer $\mathcal{D}_{i}^{j}$ from $\{\mathcal{D}_{i}^{1},\cdots,\mathcal{D}_{i}^{m}\}$ and samples mini-batches $\{s,a_{i},s^{\prime},r\}$ from $\mathcal{D}_{i}^{j}$ to update Q-table $Q^{\mathrm{e}}_{i}(s,a_{i})$ by ([7](#S2.E7)), and then samples mini-batches from $\mathcal{D}_{i}^{j}$ to update $Q_{i}(s,a_{i})$ by ([8](#S2.E8)). The Q-table implementation is summarized in Algorithm [1](#alg1).

Figure: Algorithm 1 BQL with Q-table for each agent $i$

Figure: Algorithm 2 BQL with neural network for each agent $i$

Then we analyze the sample efficiency of collecting the buffer series. Simplified best possible operator requires that any possible $P_{i}(s,a_{i})$ of $(s,a_{i})$ 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 $|\mathcal{A}_{i}|\times|\mathcal{A}_{-i}|=|\mathcal{A}|$ small buffers to cover all possible $P_{i}$ for any $(s,a_{i})$ pair, which is very efficient for experience collection. We give an intuitive illustration for this and analyze that BQL has similar sample complexity to the joint Q-learning ([3](#S2.E3)) in Appendix [B](#A2).

In complex environments with large or 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 to accurately estimate the expectation ([7](#S2.E7)). Thus, in complex environments, same as IQL, each agent $i$ only maintains one replay buffer $\mathcal{D}_{i}$, which contains all historical experiences, and uses the same $\epsilon$-greedy policy as IQL (without the randomly initialized deterministic policy $\hat{\pi}_{i}$). Then we instantiate simplified best possible operator with neural networks $Q_{i}$ and $Q^{\mathrm{e}}_{i}$. $Q^{\mathrm{e}}_{i}$ is updated by minimizing:

$$ $\displaystyle\mathbb{E}_{s,a_{i},s^{\prime},r\sim\mathcal{D}_{i}}\left[\left(Q^{\mathrm{e}}_{i}\left(s,a_{i}\right)-r-\gamma Q_{i}(s^{\prime},a_{i}^{\prime*})\right)^{2}\right],$ (9) $\displaystyle a_{i}^{\prime*}=\arg\max_{{a}^{\prime}_{i}}{Q}_{i}(s^{\prime},{a}^{\prime}_{i}).$ $$

And $Q_{i}$ is updated by minimizing:

$$ $\displaystyle\mathbb{E}_{s,a_{i}\sim\mathcal{D}_{i}}\left[w(s,a_{i})\left(Q_{i}\left(s,a_{i}\right)-\bar{Q}^{\mathrm{e}}_{i}(s,a_{i})\right)^{2}\right],$ (10) $\displaystyle w(s,a_{i})=\left\{\begin{matrix}1&\text{if }\bar{Q}^{\mathrm{e}}_{i}(s,a_{i})>Q_{i}\left(s,a_{i}\right)\\ \lambda&\text{else}.\end{matrix}\right.$ $$

$\bar{Q}^{\mathrm{e}}_{i}$ is the softly updated target network of $Q^{\mathrm{e}}_{i}$. When $\lambda=0$, ([10](#S2.E10)) is equivalent to ([8](#S2.E8)). However, when $\lambda=0$, the positive random noise of $Q_{i}$ in the update can be continuously accumulated, which may cause value overestimation. So we adopt the weighted max in ([10](#S2.E10)) by setting $0<\lambda<1$ to offset the positive random noise. In continuous action space, following DDPG (Lillicrap et al., ), we train a policy network $\pi_{i}(s)$ by maximizing $Q_{i}(s,\pi_{i}(s))$ as a substitute of $\arg\max_{a_{i}}{Q}_{i}(s,a_{i})$. The neural network implementation is summarized in Algorithm [2](#alg2).

Simplified best possible operator is meaningful for neural network implementation. As there is only one buffer $\mathcal{D}_{i}$, we cannot perform ([6](#S2.E6)) but can still perform ([7](#S2.E7)) and ([8](#S2.E8)) on $\mathcal{D}_{i}$. As other agents are updating their policies, the transition probabilities in $\mathcal{D}_{i}$ will continuously change. If $\mathcal{D}_{i}$ sufficiently goes through all possible transition probabilities, $Q_{i}(s,a_{i})$ converges to $\max_{\boldsymbol{a}_{-i}}Q(s,a_{i},\boldsymbol{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.

## 3 Related Work

Most existing MARL methods (Lowe et al., ; Iqbal & Sha, ; Wang et al., ; Zhang et al., ; Su & Lu, ; Peng et al., ; Li et al., ; Sunehag et al., ; Rashid et al., ; Son et al., ; Wang et al., ; Rashid et al., ) follow the paradigm of centralized training and decentralized execution (CTDE), where the information of all agents can be accessed in a centralized 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., independent Q-learning (Tan, ) and independent PPO (IPPO) (de Witt et al., ), cannot guarantee the convergence of the learned policy, because the transition probabilities are non-stationary from the perspective of each agent as all agents are learning policies simultaneously. Multi-agent alternate Q-learning (MA2QL) (Su et al., ) guarantees the convergence to a Nash equilibrium, but the converged equilibrium may not be the optimal one when there are multiple Nash equilibria. Moreover, to obtain the theoretical guarantee, it has to be trained in an on-policy manner and cannot use replay buffers, which leads to poor sample efficiency. Following the principle of optimistic estimation, Hysteretic IQL (Matignon et al., ) sets a slow learning rate to the value punishment. Distributed IQL (Lauer & Riedmiller, ), a special case of Hysteretic IQL with the slow learning rate being zero, guarantees the convergence to the optimum but only in deterministic environments.
I2Q (Jiang & Lu, ) lets each agent perform independent Q-learning on ideal transition probabilities and could learn the optimal policy 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.
Decentralized methods with communication (Zhang et al., ; Konan et al., ; Li & He, ) allow information sharing with neighboring agents according to a time-varying communication channel. However, they do not follow the fully decentralized setting and thus are beyond the scope of this paper.

## 4 Experiments

Figure: (a) Stochastic games
Refer to caption: /html/2302.01188/assets/x1.png

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 differential games (Jiang & Lu, ), Multi-Agent MuJoCo (Peng et al., ), SMAC (Samvelyan et al., ), and GRF (Kurach et al., ). 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. The experiments are carried out on Intel i7-8700 CPU and NVIDIA GTX 1080Ti GPU. The training of each MPE, MuJoCo, and GRF task could be finished in 5 hours, and the training of each SMAC task could be finished in 20 hours. More details about hyperparameters are available in Appendix [E](#A5).

### 4.1 Stochastic Games

To support the theoretical analysis of BQL, we test the Q-table instantiation on stochastic games with $4$ agents, $30$ states, and infinite horizon. The action space of each agent is $4$, so the joint action space $|\mathcal{A}|=256$. The distribution of initial states is uniform. Each state will transition to any state given a 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 are shown in Figure [1(a)](#S4.F1.sf1). IQL cannot learn the optimal policies due to non-stationarity. Although using the optimistic update to remedy the non-stationarity, Hysteretic IQL (H-IQL) still cannot solve this problem in stochastic environments and shows similar performance to IQL. In Appendix [A](#A1), we thoroughly analyze the difference between H-IQL and BQL, and show H-IQL is a special case of BQL in deterministic environments. I2Q performs Q-learning on the ideal transition function where the next state is deterministically the one with the highest value, which however is impossible in stochastic tasks. So I2Q cannot guarantee the optimal joint policy in stochastic 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 to the optimum, and the tiny gap is caused by the fitting error of the Q-table update. This verifies our theoretical analysis. Note that, in Q-table instantiations, MA2QL and BQL use different experience collection from IQL, i.e., exploration strategy and replay buffer. MA2QL only uses 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 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](#S2.SS4), if 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.

Figure [1(b)](#S4.F1.sf2) shows the effect of the size of buffer $\mathcal{D}_{i}^{m}$ at the epoch $m$. If $|\mathcal{D}_{i}^{m}|$ is too small, i.e., $200$, the experiences in $|\mathcal{D}_{i}^{m}|$ are insufficient to accurately estimate the expected value ([7](#S2.E7)). If $|\mathcal{D}_{i}^{m}|$ is too large, i.e., $10000$, the experiences in $|\mathcal{D}_{i}^{m}|$ are redundant, and the buffer series is difficult to cover all possible transition probabilities given fixed total training timesteps. Figure [1(c)](#S4.F1.sf3) shows the effect of the number of states on which the agents perform the randomly initialized deterministic policy $\hat{\pi}_{i}^{m}$ for exploration. The larger $|S_{i}^{m}|$ means a stronger exploration for both state-action pairs and possible transition probabilities, which leads to better performance.

We then consider a one-stage game that is wildly adopted in MARL (Son et al., ). There are $2$ agents, and the action space of each agent is $3$. The reward matrix is

$$ $\footnotesize\begin{vmatrix}a_{1}/a_{2}&\mathcal{A}^{(1)}&\mathcal{A}^{(2)}&\mathcal{A}^{(3)}\\ \mathcal{A}^{(1)}&\mathbf{8}&-12&-12\\ \mathcal{A}^{(2)}&-12&0&0\\ \mathcal{A}^{(3)}&-12&0&0\end{vmatrix}$ $$

where the reward $8$ is the global optimum and the reward 0 0 is the sub-optimal Nash equilibrium. As shown in Figure [1(d)](#S4.F1.sf4), MA2QL converges to the sub-optimal Nash equilibrium when the initial policy of the second agent selects $\mathcal{A}^{(2)}$ or $\mathcal{A}^{(3)}$. But BQL converges to the global optimum easily.

### 4.2 MPE

Figure: (a) $\beta=0.2$
Refer to caption: /html/2302.01188/assets/x5.png

To evaluate the effectiveness of BQL with neural network implementation, we adopt the $3$-agent MPE-based differential game used in I2Q (Jiang & Lu, ), where $3$ agents can move in the range $[-1,1]$. Different from the original deterministic version, we add stochasticity to it. In each timestep, agent $i$ acts the action $a_{i}\in[-1,1]$, and the position of agent $i$ will be updated as $x_{i}=\text{clip}(x_{i}+0.1\times a_{i},-1,1)$ (i.e., the updated position is clipped to $[-1,1]$) with the probability $1-\beta$, or will be updated as $-x_{i}$ with the probability $\beta$. $\beta$ controls the stochasticity. The state is the vector of positions $\{x_{1},x_{2},x_{3}\}$. The reward function of each timestep is

$$ $\displaystyle\small r=\begin{cases}0.5\cos(4l\pi)+0.5&\text{ if }l\leq 0.25\\ 0&\text{ if }0.25<l\leq 0.6\\ 0.15\cos(5\pi(l-0.8))+0.15&\text{ if }0.6<l\leq 1.0\\ 0&\text{ if }l>1.0\end{cases}$ $$

where $l=\sqrt{\frac{2}{3}(x_{1}^{2}+x_{2}^{2}+x_{3}^{2})}$. We visualize the relation between $r$ and $l$ in Figure [12](#A5.F12) in Appendix. There is only one global optimum ($l=0$ and $r=1$) but infinite sub-optima ($l=0.8$ and $r=0.3$), and the narrow region with $r>0.3$ is surrounded by the region with $r=0$. So it is quite a challenge to learn the optimal policies in a fully decentralized way. Each episode contains $100$ timesteps, and the initial positions follow the uniform distribution. We perform experiments with different stochasticities $\beta$, and train the agents for eight seeds with each $\beta$. In continuous environments, BQL and baselines are built on DDPG.

As shown in Figure [2](#S4.F2), IQL always falls into the local optimum (total reward $\approx 30$) because of the non-stationary transition probabilities. H-IQL only escapes the local optimum in one seed in the setting with $\beta=0.3$. According to the theoretical analysis in I2Q paper, the value estimation error of I2Q will become larger when stochasticity grows, which is the reason why I2Q shows poor performance with $\beta=0.4$ and $0.5$. In neural network implementations, MA2QL and BQL use the same experience 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 off-policy data. BQL ($\lambda=0.01$) can escape from local optimum in more than $4$ seeds in all settings, which demonstrates the effectiveness of our optimization objectives ([9](#S2.E9)) and ([10](#S2.E10)). The difference between global optimum (total reward $\approx 100$) and local optimum is large, which results in the large variance of BQL. In the objective ([10](#S2.E10)), $\lambda$ controls the balance between performing best possible operator and offsetting the overestimation caused by the operator. As shown in Figure [2](#S4.F2), the large $\lambda$, i.e., $0.1$, will weaken the strength of BQL, while too small $\lambda$, i.e., 0 0, will cause severe overestimation and destroy the performance.

### 4.3 Multi-Agent MuJoCo

Figure: (a) $2\times 3$ Swimmer
Refer to caption: /html/2302.01188/assets/x9.png

To evaluate BQL in partially observable environments, we adopt Multi-Agent MuJoCo (Peng et al., ), where each agent independently controls one or some joints of the robot. In each task, we test four random seeds and plot the learning curves in Figure [3](#S4.F3). Here, we set $\lambda=0.5$. In the first three tasks, each agent can only observe the state of its own joints and bodies (with the parameter agent_obsk = 0). BQL achieves higher reward or learns faster than the baselines, which verifies that BQL could be applied to partially observable environments. In partially observable environments, BQL is performed on transition probabilities of observation $P_{i}(o_{i}^{\prime}|o_{i},a_{i})$, which also depends on $\boldsymbol{\pi}_{-i}$. The convergence and optimality of BQL can only be guaranteed when one observation $o_{i}$ uniquely corresponds to one state $s$. It has been proven that the optimality is undecidable in partially observable Markov decision processes (POMDPs) (Madani et al., ), so it is not the limitation of BQL.

In the first three tasks, we only consider two-agent cases in the partially observable setting, because the too limited observation range cannot support strong policies when there are more agents. We also test BQL on $17$-agent Humanoid with full observation in Figure [3(d)](#S4.F3.sf4). BQL obtains significant performance gain in this many-agent task, which can be evidence of the good scalability of BQL.

### 4.4 SMAC

Figure: (a) 2c_vs_64zg
Refer to caption: /html/2302.01188/assets/x13.png

Figure: (a) 3_vs_1 with keeper
Refer to caption: /html/2302.01188/assets/x17.png

We also perform experiments on partially observable and stochastic SMAC tasks (Samvelyan et al., ) with the version SC2.4.10, including both easy and hard maps (Yu et al., ). Agent numbers vary between $2$ and $9$. We build BQL on the implementation of PyMARL (Samvelyan et al., ) and train the agents for four random seeds. The learning curves are shown in Figure [4](#S4.F4). In general, BQL outperforms the baselines, which verifies that BQL can also obtain performance gain in high-dimensional complex tasks. In 2c_vs_64zg, by considering the non-stationary transition probabilities, BQL and I2Q achieve significant improvement over other methods. We conjecture that the interplay between agents is strong in this task.

### 4.5 Google Research Football

Google Research Football (GRF) (Kurach et al., ) is a physics-based 3D simulator where agents aim to master playing football. We select two academy tasks with sparse rewards: 3_vs_1 with keeper (3 agents) and counterattack easy (4 agents). We build BQL on the implementation of PyMARL2 (Hu et al., ) and train the agents for four random seeds. Although I2Q shows similar results with BQL in some SMAC tasks, BQL can outperform I2Q in GRF as shown in Figure [5(a)](#S4.F5.sf1) and [5(b)](#S4.F5.sf2), because GRF is more stochastic than SMAC and the value gap of I2Q will enlarge along with the increase of stochasticity.

### 4.6 Hyperparameter λ 𝜆 \lambda

We further investigate the effectiveness of $\lambda$ in Multi-Agent MuJoCo and SMAC. In the objective ([10](#S2.E10)), $\lambda$ controls the balance between performing best possible operator and offsetting the overestimation caused by the operator. As shown in Figure [5(c)](#S4.F5.sf3) and [5(d)](#S4.F5.sf4), too large $\lambda$ will weaken the strength of BQL. When $\lambda=1.0$, BQL degenerates into IQL. Too small $\lambda$, i.e., 0 0, will cause overestimation. If the environment is more complex, e.g., SMAC, overestimation is more likely to occur, so we should set a large $\lambda$. In $2\times 3$ Swimmer, when $\lambda$ falls within the interval $[0.2,0.8]$, BQL can obtain performance gain, showing the robustness to $\lambda$.

## 5 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 to the global optimum in stochastic environments. Empirically, BQL outperforms baselines in a variety of multi-agent tasks. We believe BQL can be a new paradigm for fully decentralized learning.

## Appendix A Comparison with Hysteretic IQL

Hysteretic IQL is a special case of BQL when the environment is deterministic. To thoroughly illustrate that, we rewrite the loss function of BQL

$$ $\displaystyle w(s,a_{i})\left(Q_{i}\left(s,a_{i}\right)-\mathbb{E}_{\tilde{P}_{i}(s^{\prime}|s,a_{i})}\left[r+\gamma\underset{a^{\prime}_{i}}{\max}Q_{i}(s^{\prime},a^{\prime}_{i})\right]\right)^{2},$ $\displaystyle w(s,a_{i})=\left\{\begin{matrix}1&\text{if }\mathbb{E}_{\tilde{P}_{i}(s^{\prime}|s,a_{i})}\left[r+\gamma\underset{a^{\prime}_{i}}{\max}Q_{i}(s^{\prime},a^{\prime}_{i})\right]>Q_{i}\left(s,a_{i}\right)\\ \lambda&\text{else}.\end{matrix}\right.$ $$

If $\lambda=0$, the update of BQL is

$$ $Q_{i}(s,a_{i})=\max\left(Q_{i}(s,a_{i}),\mathbb{E}_{\tilde{P}_{i}(s^{\prime}|s,a_{i})}\left[r+\gamma\underset{a^{\prime}_{i}}{\max}Q_{i}(s^{\prime},a^{\prime}_{i})\right]\right).$ $$

Hysteretic IQL follows the loss function

$$ $\displaystyle w(s,a_{i})\left(Q_{i}\left(s,a_{i}\right)-r-\gamma\underset{a^{\prime}_{i}}{\max}Q_{i}(s^{\prime},a^{\prime}_{i})\right)^{2},$ $\displaystyle w(s,a_{i})=\left\{\begin{matrix}1&\text{if }r+\gamma\underset{a^{\prime}_{i}}{\max}Q_{i}(s^{\prime},a^{\prime}_{i})>Q_{i}\left(s,a_{i}\right)\\ \lambda&\text{else}.\end{matrix}\right.$ $$

If $\lambda=0$, Hysteretic IQL degenerates into Distributed IQL (Lauer & Riedmiller, )

$$ $Q_{i}(s,a_{i})=\max\left(Q_{i}(s,a_{i}),r+\gamma\underset{a^{\prime}_{i}}{\max}Q_{i}(s^{\prime},a^{\prime}_{i})\right).$ $$

BQL takes the max of the expected target on transition probability $\tilde{P}_{i}(s^{\prime}|s,a_{i})$, while Hysteretic IQL takes the max of the target on the next state $s^{\prime}$. When the environment is deterministic, they are 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^{\prime}$. BQL can guarantee the global optimum in both deterministic and stochastic environments.

## Appendix B Efficiency of BQL

Figure: Figure 6: Space of other agents’ policies $\boldsymbol{\pi}_{-i}$ given an $(s,a_{i})$.
Refer to caption: /html/2302.01188/assets/x21.png

Figure: Figure 7: Toy case for illustrating the ideal buffer number. $|\mathcal{S}|=3$, $|\mathcal{A}_{i}|=2$, and $|\mathcal{A}_{-i}|=2$ corresponding to $P_{i}^{1}$ and $P_{i}^{2}$. We can see that any $P_{i}(s,a_{i})$ can be found in the 4 buffers.
Refer to caption: /html/2302.01188/assets/x22.png

We will discuss the efficiency of collecting the replay buffer for BQL. The space of other agents’ policies $\boldsymbol{\pi}_{-i}$ given $(s,a_{i})$ pair is a convex polytope. For clarity, Figure [6](#A2.F6) shows a triangle space. Each $\boldsymbol{\pi}_{-i}$ corresponds to a $P_{i}(s^{\prime}|s,a_{i})$. Deterministic policies $\boldsymbol{\pi}_{-i}$ locate at the vertexes, while the edges and the inside of the polytope are stochastic $\boldsymbol{\pi}_{-i}$, 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 in the collection of each buffer $\mathcal{D}_{i}^{m}$, which is efficient. BQL needs only $|\mathcal{A}_{i}|\times|\mathcal{A}_{-i}|=|\mathcal{A}|$ small buffers, which is irrelevant to state space $|\mathcal{S}|$, to meet the requirement of simplified best possible operator that any one of possible $P_{i}(s^{\prime}|s,a_{i})$ can be found in one (ideally only one) buffer given $(s,a_{i})$ pair. More specifically, $|\mathcal{A}_{i}|$ buffers are needed to cover action space, and $|\mathcal{A}_{-i}|$ buffers are needed to cover transition space for each action. We intuitively illustrate this in Figure [7](#A2.F7). Each state in $\mathcal{D}_{i}^{m}$ requires $\#$ samples to estimate the expectation in ([7](#S2.E7)), so the sample complexity is $O(|\mathcal{A}||S|\#)$. For the joint Q-learning ([3](#S2.E3)), the most efficient known method to guarantee the convergence and optimality in stochastic environments, each state-joint action pair $(s,\boldsymbol{a})$ requires $\#$ samples to estimate the expectation, so the sample complexity is also $O(|\mathcal{A}||S|\#)$. Thus, BQL is close to the joint Q-learning in terms of sample complexity, which is empirically verified in Figure [8](#A2.F8).

Figure: Figure 8: Learning curves of BQL and joint Q-learning (JQL). BQL shows similar sample efficiency to JQL.
Refer to caption: /html/2302.01188/assets/x23.png

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 one of possible transition probability functions of the whole state-action space could be found in one buffer, which needs $|\mathcal{A}_{-i}|^{|\mathcal{S}|}$ buffers. And training IQL $|\mathcal{A}_{-i}|^{|\mathcal{S}|}$ 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 $\mathcal{D}_{i}$ containing all historical experiences, which is the same as IQL. $P_{i}$ in $\mathcal{D}_{i}$ corresponds to the average of other agents’ historical policies, which is stochastic. Therefore, to guarantee the optimality, in theory, BQL with one buffer has to go through almost the whole $\boldsymbol{\pi}_{-i}$ space, which is costly. As shown in Figure [1(d)](#S4.F1.sf4), 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 [9](#A2.F9). Due to sample efficiency, the buffer series cannot achieve strong performance, and maintaining one buffer like IQL is a better choice in complex environments.

Figure: (a) MPE, $\beta=0.4$
Refer to caption: /html/2302.01188/assets/x24.png

## Appendix C Other Base Algorithms

Besides DDPG, BQL could also be built on other variants of Q-learning, e.g., SAC. Figure [10](#A3.F10) shows that BQL could also obtain performance gain on independent SAC. Independent PPO (IPPO) (de Witt et al., ) is an on-policy decentralized MARL baseline. IPPO is not a Q-learning method so it cannot be the base algorithm of BQL. On-policy algorithms do not use old experiences, which makes them weak on sample efficiency (Achiam, ) especially in fully decentralized settings as shown in Figure [10](#A3.F10). Thus, it is unfair to compare off-policy algorithms with on-policy algorithms.

Figure: (a) MPE, $\beta=0.4$
Refer to caption: /html/2302.01188/assets/x26.png

## Appendix D Multiple Optimal Joint Policies

Figure: (a) matrix game
Refer to caption: /html/2302.01188/assets/x28.png

We assume that there is only one optimal joint policy. With multiple optimal actions (with the max $Q_{i}(s,a_{i})$), if each agent arbitrarily selects one of the optimal independent actions, the joint action might not be optimal. To address this, we use the simple technique proposed in I2Q (Jiang & Lu, ). Concretely, we set a performance tolerance $\varepsilon$ and introduce a fixed randomly initialized reward function $\hat{r}(s,s^{\prime})\in(0,(1-\gamma)\varepsilon]$. Then all agents perform BQL to learn $\hat{Q}_{i}(s,a_{i})$ of the shaped reward $r+\hat{r}$. Since $\hat{r}>0$, $\hat{Q}_{i}(s,a_{i})>Q_{i}(s,a_{i})$. In $\hat{Q}_{i}(s,a_{i})$, the maximal contribution from $\hat{r}$ is $(1-\gamma)\varepsilon/(1-\gamma)=\varepsilon$, so the minimal contribution from $r$ is $\hat{Q}_{i}(s,a_{i})-\varepsilon>Q_{i}(s,a_{i})-\varepsilon$, which means that the maximal performance drop is $\varepsilon$ when selecting actions according to $\hat{Q}_{i}$. It is a small probability event to find multiple optimal joint policies on the reward function $r+\hat{r}$, because $\hat{r}(s,s^{\prime})$ is randomly initialized. Thus, if $\varepsilon$ is set to be small enough, BQL can solve the task with multiple optimal joint policies. However, this technique is introduced to only remedy the assumption for 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, so the comparison is fair.

We test the randomly initialized reward function on a one-stage matrix game with two optimal joint policies $(1,2)$ and $(2,1)$, as shown in Figure [11](#A4.F11). If the agents independently select actions, they might choose the miscoordinated joint policies $(1,1)$ and $(2,2)$. IQL cannot converge, but BQL 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.

## Appendix E Hyperparameters

Figure: Figure 12: Curves of reward and density of $l=\sqrt{\frac{2}{3}\sum_{i=0}^{3}x_{i}^{2}}$ in MPE. We plot the density of uniform state distribution. There is only one global optimum, but the density of local optimum is high. So decentralized agents will easily learn the local optimal policies.
Refer to caption: /html/2302.01188/assets/x30.png

In MPE-based differential games, the relationship between $r$ and $l$ is visualized in Figure [12](#A5.F12).

In $2\times 3$ Swimmer, there are two 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 SpinningUp (Achiam, ) implementation, the SOTA implementation of DDPG, and follow all hyperparameters in SpinningUp. The discount factor $\gamma=0.99$, the learning rate is $0.001$ with Adam optimizer, the batch size is $100$, the replay buffer contains $5\times 10^{5}$ transitions, the hidden units are $256$.

In SMAC, we adopt PyMARL (Samvelyan et al., ) implementation and follow all hyperparameters in PyMARL. The discount factor $\gamma=0.99$, the learning rate is $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 GRF, we adopt PyMARL2 (Hu et al., ) implementation and follow all hyperparameters in PyMARL2. The discount factor $\gamma=0.999$, the learning rate is $0.0005$ with Adam optimizer, the batch size is $128$ episodes, the replay buffer contains $2000$ episodes, the hidden units are $256$. We use simple115 feature (a 115-dimensional vector summarizing many aspects of the game) as observation instead of RGB image.

In MPE-based differential games, we set $\lambda=0.01$. In Multi-Agent MuJoCo, we set $\lambda=0.5$, and in SMAC, we set $\lambda=0.85$ for 2c_vs_64zg and $\lambda=0.8$ for other tasks. In GRF, we set $\lambda=0.1$ for 3_vs_1 with keeper and $\lambda=0.4$ for counterattack easy.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: See above.
soundness: 3
strengths: 1. The paper is quite novel and original since it proposed a novel operator to enable convergence despite the nonstationary environment caused by other players in a decentralized multi-agent and stochastic setting. 
2. The paper is very well written. The algorithm is explained clearly and the simulation results are easy to follow.
3. The results are significant since it addressed a long lasting open question on MARL.
summary: This paper considers decentralized training decentralized play for multi-agent reinforcement learning. A fully decentralized learning is proposed based on a best possible operator proposed in this paper. Though this operator is computationally expensive, it leads to convergence despite the nonstationarity caused by other players. A simplified operator is also proposed and the convergence and optimality based on this simplified operator is also provided. Simulation results demonstrate the performance of the proposed algorithm.
weaknesses: 1. It can be restrictive to assume there is only a unique optimal policy. How does the proposed algorithm perform when there are multiple optimal policies?

2. Can the authors provide explicit theorems and proofs for the convergence and optimality of BQL  for both the tabular case and the neural network case?

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. In Lemma 1, why do we need the condition of existence of only one optimal policy?

2. There is typo in the caption of Figure 3 : "Mojoco"->"Mujoco".

3.  In Section 2.4, $S^m_i$ has not been explained previously.
soundness: 3
strengths: 1. The authors proposed a new decentralized algorithm that could give new insights into the community. Even though the proposed algorithm has limitations, finding a global joint optimal policy in a decentralized manner seems to be a contribution.

2. The overall experimental result seems positive. It shows better or comparable results to existing ones including MA2QL, I2Q, H-IQL, IQL.
summary: This paper studies decentralized multi-agent Q-learning where every agents share the same state and observes only local action. Resolving non-stationary due to the joint-policy, it is difficult to establish convergence of to a joint optimal policy is an important problem in MARL. The authors propose a best-possible operator, which basically solves the joint opitmal Bellman equation for $i$-th agent:
$$   Q^i(s,a_i)=\max_{a_{-i}}\mathbb{E}_{s^{\prime}\sim P(\cdot\mid s,a_i,a_{-i} )}[r+\gamma Q^i(s,a_i)].$$
The authors solve the above equation in decentralized manner, and its extension to practical algorithm is studied.
weaknesses: 1. The memory space to store $P(\cdot\mid s,a_i,a_{-i})$ requires at least $O(|\mathcal{A}_{-i}|)$ space, which scales exponentially at the order of each action space. This makes the algorithm difficult to scale as number of agents increase. If we use function approximation, or somewhat similar methods to reduce this problem, will the arguments of this paper be still valid?

2. The search over all possible $\pi_{-i}(a_{-i},s)$ for evert state $s$ and $i$ seems to be quite a burden. It at least requires $N \prod_i |\mathcal{A}_i|$, which scale exponentially due to the joint action space. Even though the authors proposed a version in (7) to reduce the search time, I do not think this gives a meaningful cut in the search time in theoretical sense. Can the authors provide theoretical advantage in terms of search time for the proposed method?

3. A closely related work [1] deals with theoretical convergence of independent Q-learning. Please provide comparison with the work in sense that how the setting is different, and pros and cons.


4. The algorithm does not seem to be scalable.

---

confidence: 4
contribution: 2
initial_rating: 1
presentation: 2
questions: * Surely the claim of global optimality in line 62 is restricted to tabular cases, right? Such broad claims should be avoided (unless somehow they are true) in order to ensure the work is not misunderstood by a casual reader. Please clarify the setting in which this claim is valid.
* Why can’t we treat all agents as one “super agent” whose action space is the product space of the individual agents, and conclude that because (tabular) Q learning would converge for the “super agent,” it will also for the individual Q learners? If we did value iteration instead of Q learning would it work? An explanation here would probably not depend upon (non)stationarity arguments, I think. At the very least, the authors should provide a reference for the statement of non-convergence on line 87.
* I do not follow the step from line 142 to line 144. Is it generally true that max_x f(x) - max_x g(x) \ge f(x’) - g(x’) for a generic x’ (here, x’ is analogous to a_i^{‘*})? I can certainly find counterexamples in general, so what is special about this case which admits this inequality? Please explain what is going on here more carefully.
* I am not clear on why we need to “explore” all state/action pairs with a deterministic policy (looking at line 236). Can’t we just enumerate them in a tabular problem? Please explain why the exploration is needed and enumeration does not suffice.
    * This relates to the italicized sentence at the end of section 2.
soundness: 1
strengths: * The main idea of having each agent “imagine” a best-case scenario of what the other agents do is a very clean way to synchronize the independent Q-learning approach which could otherwise fail to converge. 
* For the most part, the proofs are logical and easy to follow. (See question below.)
summary: This paper presents a new take on decentralized Q-learning, in which each agent (independently) updates its value function by pretending that the other agents act optimally with respect to its current estimate of the value function. A simplification of this procedure is proposed which the authors show also leads to desirable convergence properties. Experiments contrast the proposed method with relevant baselines.
weaknesses: * Some syntax errors on line 70: no whitespace after “MDP” and also the <> symbols should probably be () for a tuple as is standard in the MDP literature.
* Many instances of grammatical issues, e.g. missing “the” in a sentence.
* The simplified operator seems like it will be egregiously inefficient, particularly in larger state/action spaces. Isn’t it effectively just random search?
* The sentence “but the converged equilibrium may not be the optimal one when there are multiple Nash equilibria” on line 322 only makes sense in (a) games where agents share a common objective — otherwise what is the measure of optimal — and (b) is not really a critique for non-convex games where methods would only at best be able to find local equilibria and there is no good way to find the “best” such equilibrium. Similar comment for the statement about Hysteretic IQL on line 325. 
* “slow learning rate to the value punishment” on line 324 must be a typo of some kind
* “using mean and standard” on line 345 is a typo
* “action space of each agent is 4” -> another typo on line 351
* More details should be provided about the distribution from which transition kernels and reward functions are sampled (cf line 354). Depending on the variance of these distributions, using only 20 samples could easily give a very poor statistical estimate of performance. Since the standard deviations look fairly small (at least in Figure 1), I am guessing that these distributions are fairly well structured. It would be useful to understand that structure so as to better appreciate the testing scenario and results.
* “std” on line 356 should be spelled out
* I do not follow all the issues that are being discussed in the paragraph ending on line 374. This discussion should be substantially rewritten for clarity.
* “wildly adopted” -> typo on line 301. I presume it should be “widely” but if that is the case, why is there only one reference here?
* “MPE” is not defined anywhere as far as I can remember. Cf. line 341 and section 4.2. From the description in section 4.2, this is not actually a differential game since time is not a continuous variable. Cf. the standard texts by Rufus Isaacs and Tamer Basar & Geert Olsder. The proper term would be “dynamic game,” which includes discrete-time problems.
* “In continuous environments, BQL and baselines are built on DDPG.” (Line 428) -> this should be explained far more carefully so that readers can appreciate how this choice influences the results
* In Figure 2, the results are not easily interpretable due to the color choices being so similar for the confidence intervals, and the intervals themselves being so wide for some methods. 
* All of the subfigure captions in Figures 3-5 are confusing. Without clear explanations of every single experiment, results are impossible to interpret and certainly cannot be trusted by a serious reader. 
    * Some of the descriptions of these subfigures in section 4.4 even make it sound like these are tasks where different agents have different objectives; clearly that does not conform to the present paper setting, so something is additionally confusing here.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: 1. How is eq (4) obtained? Eq(3) holds when $a=(a_1^*,a_2^*,...,a^*_n)=\pi^*(s)$. Now if taking the maximum of other actions, will it require to fix $a_i=a^*_i$?
2. In the case of there exists onle one optimal policy, why is it deterministic? The Puterman's book is too large and more specific reference should be provided. It also seems to me that the Puterman's book is for single agent case mostly. 
3. In the proof of Lemma 4, the convergence is based on the fact that the optimal kernel is chosen during updating. What if the kernel is never choosen? 
4. When only deterministic policies are considered, the set of all possible kernels is finite, making Q3 a bit reasonable. But what if random policies are also considered?
soundness: 2
strengths: 1. The problem of MARL is definitely important. This work provide a theoretical study on it with convergence guarantees.
2. I do appreciate the experiment part.
summary: This paper studies multi agent RL. A best possible operator is proposed to learn the optimal joint Q function. To address the computational cost, a simplied randomized operator is proposed. Algorithm based on it is further designed and extensive experiments are developed.
weaknesses: 1. The observation of the global state can be a strong assumption.
2. The uniqueness of the joint optimal policy can also be strong. 
3. Since I am not familar with MARL, some statements/claims will benifit from more explanations. 
4. Some proofs are not convinced.

Meta-review: This paper studies decentralized reinforcement learning over networked agents, based on a best-possible operator. The studied problem is important and the algorithm design contains new ideas. In particular, the use of the best-possible operator in this decentralized multi-agent RL setting is interesting, the paper is overall easy to follow, and the experiments are compelling in general. However, there were some concerns regarding the rigor and clarity of the technical contributions, as well as the presentation/writing of the paper. Theoretical contributions have taken up quite some space in the paper, but seem to be not significant and strong enough to clear the bar for acceptance, especially given some strong assumptions required in the theorems, which were also stated relatively loosely/informally. In fact, for the core algorithm BQL, there were no theoretical guarantees (as per Sec. 2.4). I suggest the authors incorporate the feedback in preparing the next version of the paper.

Decision: Reject