MA2QL: A Minimalist Approach to Fully Decentralized Multi-Agent Reinforcement Learning

Dec-POMDP. Decentralized partially observable Markov decision process (Dec-POMDP) is a general model for cooperative MARL. A Dec-POMDP is a tuple $M=\left\{S,A,P,Y,O,I,n,r,\gamma\right\}$. $S$ is the state space, $n$ is the number of agents, $\gamma\in[0,1)$ is the discount factor, and $I=\{1,2\cdots n\}$ is the set of all agents. $A=A_{1}\times A_{2}\times\cdots\times A_{n}$ represents the joint action space where $A_{i}$ is the individual action space for agent $i$. $P(s^{\prime}|s,\bm{a}):S\times A\times S\to[0,1]$ is the transition function, and $r(s,\bm{a}):S\times A\to\mathbb{R}$ is the reward function of state $s$ and joint action $\bm{a}$. $Y$ is the observation space, and $O(s,i):S\times I\to Y$ is a mapping from state to observation for each agent. The objective of Dec-POMDP is to maximize $J({\bm{\pi}})=\mathbb{E}_{\bm{\pi}}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},\bm{a}_{t})\right],$ and thus we need to find the optimal joint policy ${\bm{\pi}}^{*}=\arg\max_{{\bm{\pi}}}J({\bm{\pi}})$. To settle the partial observable problem, history $\tau_{i}\in\mathcal{T}_{i}:(Y\times A_{i})^{*}$ is often used to replace observation $o_{i}\in Y$. Each agent $i$ has an individual policy $\pi_{i}(a_{i}|\tau_{i})$ and the joint policy $\bm{\pi}$ is the product of each $\pi_{i}$. Though the individual policy is learned as $\pi_{i}(a_{i}|\tau_{i})$ in practice, as Dec-POMDP is undecidable (Madani et al., 1999) and the analysis in partially observable environments is much harder, we will use $\pi_{i}(a_{i}|s)$ in analysis and proofs for simplicity.

Dec-MARL. Although decentralized cooperative multi-agent reinforcement learning (Dec-MARL) has been previously investigated (Zhang et al., 2018; de Witt et al., 2020), the setting varies across these studies. In this paper, we consider Dec-MARL as a fully decentralized solution to Dec-POMDP, where each agent learns its policy/Q-function from its own action individually without communication or parameter-sharing. Therefore, in Dec-MARL, each agent $i$ actually learns in the environment with transition function $P_{i}(s^{\prime}|s,a_{i})=\mathbb{E}_{a_{-i}\sim\pi_{-i}}[P(s^{\prime}|s,a_{i},a_{-i})]$ and reward function $r_{i}(s,a_{i})=\mathbb{E}_{a_{-i}\sim\pi_{-i}}[r(s,a_{i},a_{-i})]$, where $\pi_{-i}$ and $a_{-i}$ respectively denote the joint policy and joint action of all agents expect $i$. As other agents are also learning (i.e., $\pi_{-i}$ is changing), from the perspective of each individual agent, the environment is non-stationary. This is the non-stationarity problem, the main challenge in Dec-MARL.

IQL. Independent Q-learning (IQL) is a straightforward method for Dec-MARL, where each agent $i$ learns a Q-function $Q(s,a_{i})$ by Q-learning. However, as all agents learn simultaneously, there is no theoretical guarantee on convergence due to non-stationarity, to the best of our knowledge. In practice, IQL is often taken as a simple baseline in favor of more elaborate MARL approaches, such as value-based CTDE methods (Rashid et al., 2018; Son et al., 2019). However, much less attention has been paid to IQL itself for Dec-MARL.

To address the non-stationarity problem in Dec-MARL, a fundamental way is simply to make the environment stationary during the learning of each agent. Following this principle, we let agents learn by turns; in each turn, one agent performs policy iteration while fixing the policies of other agents. This procedure is referred to as multi-agent alternate policy iteration. As illustrated in Figure 1, multi-agent alternate policy iteration differs from policy iteration in single-agent RL. In single-agent RL, policy iteration is performed on the same MDP. However, here, for each agent, policy iteration at a different round is performed on a different MDP. As $\pi_{-i}$ is fixed at each turn, $P_{i}(s^{\prime}|s,a_{i})$ and $r_{i}(s,a_{i})$ are stationary and we can easily have the following lemma.

Lemma 1 is simple but useful, which is also reached independently and implicitly by existing studies in different contexts (Fang et al., 2019; Bertsekas, 2020). Moreover, Lemma 1 immediately indicates an approach with the convergence guarantee for Dec-MARL and also tells us that if we find the optimal policy for agent $i$ in each round $k$ given the other agents’ policies $\pi_{-i}^{k}$, then the joint policy will obtain the largest improvement. This result can be formulated as follows,

We could obtain this $\pi^{*,k}_{i}$ by policy iteration with many on-policy iterations. However, such a method will face the issue of sample inefficiency which may be amplified in MARL settings. We will use Q-iteration to settle this problem as in Fang et al. (2019); Bertsekas (2020). However, unlike these studies, we propose to truncate Q-iteration for fast learning but with the same theoretical guarantee.

Instead of policy iteration, we let agents perform Q-iteration by turns as depicted in Figure 1. Let $\mathcal{M}^{k}_{i}=\{P_{i}^{k},r^{k}_{i}\}$ denote the MDP of agent $i$ in round $k$, where we have $\mathcal{M}^{k}_{i}\neq\mathcal{M}^{k-1}_{i}$ unless $\pi_{-i}$ has converged, and $Q^{t,k}_{i}(s,a_{i})$ denote the Q-function of agent $i$ with $t$ updates in the round $k$. We define the Q-iteration as follows,

Then, the sequence $\{Q^{t,k}_{i}\}$ converges to $Q^{*,k}_{i}$ with respect to the MDP $\mathcal{M}_{i}^{k}=\{P_{i}^{k},r_{i}^{k}\}$, and we have the following lemma and corollary.

With Lemma 1, Lemma 2, and Corollary 1, we have the following theorem.

All the proofs are included in Appendix A.

Theorem 1 assumes that for each agent, $Q_{i}^{*}$ has the unique maximum over actions for all states. Although this may not hold in general, in practice we can easily settle this by introducing a positive random noise to the reward function. Suppose the random noise is bounded by $\delta$, then we can easily derive that the performance drop of optimizing environmental reward plus noise is bounded by $\delta/(1-\gamma)$. As we can make $\delta$ arbitrarily small, the bound is tight. Moreover, as there might be many Nash equilibria, Theorem 1 does not guarantee the converged joint policy is optimal.

From Theorem 1, we know that if each agent $i$ guarantees $\varepsilon$-convergence to $Q_{i}^{*,k}$ in each round $k$, multi-agent alternate Q-iteration also guarantees a Nash equilibrium of the joint policy. This immediately suggests a simple, practical fully decentralized learning method, namely multi-agent alternate Q-learning (MA2QL).

For learning Q-table or Q-network, MA2QL makes minimal changes to IQL.

• •

  For learning Q-tables, all agents in turn update their Q-tables. At a round $k$ of an agent $i$, all agents interact in the environment, and the agent $i$ updates its Q-table a few times using the collected transitions $\left<s,a_{i},r,s^{\prime}\right>$.

• •

  For learning Q-networks, all agents in turn update their Q-networks. At a round of an agent $i$, all agents interact in the environment, and each agent $j$ stores the collected transitions $\left<s,a_{j},r,s^{\prime}\right>$ into its replay buffer, and the agent $i$ updates its Q-network using sampled mini-batches from its replay buffer.

There is a slight difference between learning Q-table and Q-network. Strictly following multi-agent alternate Q-iteration, Q-table is updated by transitions sampled from the current MDP. On the other hand, Q-network is updated by mini-batches sampled from the replay buffer. If the replay buffer only contains the experiences sampled from the current MDP, learning Q-network also strictly follows multi-agent alternate Q-iteration. However, in practice, we slightly deviate from that and allow the replay buffer to contain transitions of past MDPs, following IQL (Sunehag et al., 2018; Rashid et al., 2018; Papoudakis et al., 2021) for sample efficiency, the convergence may not be theoretically guaranteed though.

MA2QL and IQL can be simply summarized and highlighted as MA2QL agents take turns to update Q-functions by Q-learning, whereas IQL agents simultaneously update Q-functions by Q-learning.

The didactic game is a cooperative stochastic game, which is randomly generated for the reward function and transition probabilities with 30 states, 3 agents, and 5 actions for each agent. Each episode in the game contains 30 timesteps. For comparison, we use dynamic programming to find the global optimal solution, denoted as OPTIMAL. For MA2QL and IQL, each agent independently learns a $30\times 5$ Q-table.

First, we investigate how the number of Q-iterations empirically affects the convergence of multi-agent alternate Q-iteration, where Q-iteration is performed by dynamic programming (full sweep over the state set) and denoted as MA2QL-DP. As shown in Figure 2(a), we can see that different numbers of Q-iterations (i.e., $t=1,5,10,50$) that each agent takes at each turn do not affect the convergence in the didactic game, even when $t=1$. This indicates $\varepsilon$-convergence of Q-iteration can be easily satisfied with as few as one iteration. Next, we compare the performance of MA2QL and IQL. As illustrated in Figure 2(b), IQL converges slowly (about 2000 steps), while MA2QL converges much faster (less than 100 steps) to a better return and also approximates OPTIMAL. Once again, MA2QL and IQL use the same number of samples and Q-table updates for each agent. One may notice that the performance of MA2QL is better than MA2QL-DP. This may be attributed to sampling and exploration of MA2QL, which induces a better Nash equilibrium. Then, we investigate MA2QL in terms of the number of Q-table updates at each turn, which resembles the number of Q-iterations by learning on samples. Specifically, denoting $K$ as the number of Q-table updates, to update an agent, we repeat $K$ times of the process of sampling experiences and updating Q-table. This means with a larger $K$, agents take turns less frequently. As shown in Figure 2(c), with larger $K$, the learning curve is more stair-like, which means in this game a small number $K$ is enough for convergence at each turn. Thus, with larger $K$, the learning curve converges more slowly. Last, we investigate how the number of collected transitions at each turn impacts the performance of MA2QL. As depicted in Figure 2(d), the performance of MA2QL is better with more samples. This is because the update of Q-learning using more samples is more like to induce a full iteration of Q-table.

Stochasticity. We investigate MA2QL under different stochasticity levels of the environment. We control the stochasticity level by introducing p_trans. For any transition, a state has the probability of p_trans to transition to next state uniformly at random, otherwise follows the original transition probability. Thus, larger p_trans means higher level of stochasticity. As illustrated in Figure 3, MA2QL outperforms IQL in all stochasticity levels.

Exploration. We further investigate the performance of MA2QL under different exploration schemes, including different decaying rates and constant $\epsilon$. As illustrated in Figure 4, MA2QL again outperforms IQL in all these exploration schemes. Note that decay_1M means $\epsilon$ decays from 1 to 0.02 over $10^{6}$ environment steps, similarly for others. These results show the robustness of MA2QL under various exploration schemes, even when $\epsilon=1$.

Update Order. Our theoretical result holds on any update order of agents, which means the order does not affect the convergence theoretically. Here we investigate the empirical performance of MA2QL under different pre-defined orders and the random order at each round. As there are three agents in this environment, there are essentially two different pre-defined orders. Suppose that three agents are indexed from 0 to 2. The alternating update orders [0, 1, 2], [1, 2, 0], and [2, 0, 1] are the same, while [0, 2, 1], [1, 0, 2], and [2, 1, 0] are the same. As illustrated in Figure 5, the performance of MA2QL is almost the same under the two orders (MA2QL is the order of [0, 1, 2]), which shows the robustness of MA2QL under different pre-defined orders. As for the random order at each round, the performance drops but is still better than IQL. One possible reason is that agents are not evenly updated due to the random order at each round, which may consequently induce a worse Nash equilibrium.

In the didactic game, we show that MA2QL consistently outperforms IQL under various settings. In the following experiments, for a fair comparison, the hyperparameters of IQL are well-tuned and we directly build MA2QL on top of IQL. As for the update order of MA2QL agents, we use a randomly determined order throughout a training process.

MPE is a popular environment in cooperative MARL. We consider three partially observable tasks: 5-agent simple spread, 5-agent line control, and 7-agent circle control (Agarwal et al., 2020), where the action space is set to discrete. Moreover, we use the sparse reward setting for these tasks, thus they are more difficult than the original ones. More details are available in Appendix B. For both IQL and MA2QL, Q-network is learned by DQN (Mnih et al., 2013).

Figure 6 shows the learning curve of MA2QL compared with IQL in these three MPE tasks. In simple spread and circle control, at the early training stage, IQL learns faster and better than MA2QL, but eventually MA2QL converges to a better joint policy than IQL. The converged performance of IQL is always worse than MA2QL, similar to that in the didactic game. Moreover, unlike the didactic game, simultaneous learning of IQL may also make the learning unstable even at the late training stage as in line control and circle control, where the episode rewards may decrease. On the other hand, learning by turns gradually improves the performance and converges to a better joint policy than IQL.

As MA2QL and IQL both use replay buffer that contains old experiences, why does MA2QL outperform IQL? The reason is that their experiences are generated in different manners. In the Q-learning procedure for each agent $i$ , the ideal target is $y_{i}=r^{\bm{\pi}}_{i}(s,a_{i})+\lambda\mathbb{E}_{s^{\prime}\sim P^{\bm{\pi}}_{i}(\cdot|s,a_{i})}[\max_{a^{\prime}_{i}}Q_{i}(s^{\prime},a^{\prime}_{i})]$ and the practical target is $\tilde{y}_{i}=r^{\bm{\pi}_{\operatorname{D}}}_{i}(s,a_{i})+\lambda\mathbb{E}_{s^{\prime}\sim P^{\bm{\pi}_{\operatorname{D}}}_{i}(\cdot|s,a_{i})}[\max_{a^{\prime}_{i}}Q_{i}(s^{\prime},a^{\prime}_{i})]$, where $\bm{\pi}_{\operatorname{D}}$ is the average joint policy for the experiences in the replay buffer. We then can easily obtain a bound for the target that $\left|y_{i}-\tilde{y}_{i}\right|\leq\frac{2-\gamma}{1-\gamma}r_{\max}D_{\operatorname{TV}}\left(\pi^{-i}(\cdot|s)\|\pi_{\operatorname{D}}^{-i}(\cdot|s)\right)$ where $r_{\max}=\max_{s,\bm{a}}r(s,\bm{a})$. We can then give an explanation from the aspect of the divergence between $\bm{\pi}$ and $\bm{\pi}_{\operatorname{D}}$. MA2QL obtains experiences with only one agent learning, so the variation for the joint policy is smaller than that of IQL. Thus, in general, the divergence between $\bm{\pi}$ and $\bm{\pi}_{\operatorname{D}}$ is smaller for MA2QL, which is beneficial to the learning.

Multi-agent MuJoCo has become a popular environment in cooperative MARL for continuous action space. We choose three robotic control tasks: $2\times 3$ HalfCheetah, $3\times 1$ Hopper, and $3\times 2$ Walker2d. To investigate continuous action space in both partially and fully observable environments, we configure $2\times 3$ HalfCheetah and $3\times 1$ Hopper as fully observable, and $3\times 2$ Walker2d as partially observable. More details and results on multi-agent MuJoCo are available in Appendix B and D respectively. For both IQL and MA2QL, we use DDPG (Lillicrap et al., 2016) as the alternative to DQN to learn a Q-network and a deterministic policy for each agent to handle continuous action space. Here we abuse the notation a little and still denote them as IQL and MA2QL respectively.

In comparison to discrete action space, training multiple cooperative agents in continuous action space still remains challenging due to the difficulty of exploration and coordination in continuous action space. Thus, the evaluation on these multi-agent MuJoCo tasks can better demonstrate the effectiveness of decentralized cooperative MARL methods. As illustrated in Figure 7, in all the tasks, we find that MA2QL consistently and significantly outperforms IQL while IQL struggles. We believe the reason is that the robotic control tasks are much more dynamic than MPE and the non-stationarity induced by simultaneous learning of IQL may be amplified, which makes it hard for agents to learn effective and cooperative policies. On the other hand, alternate learning of MA2QL can deal with the non-stationarity and sufficiently stabilize the environment during the learning process, especially in HalfCheetah and Hopper, where MA2QL stably converges to much better performance than IQL. According to these experiments, we can verify the superiority of MA2QL over IQL in the continuous action space.

SMAC is a popular partially observable environment for benchmarking cooperative MARL algorithms. SMAC has a much larger exploration space, where agents are much easy to get stuck in sub-optimal policies especially in the decentralized setting. We test our method on three representative maps for three difficulties: $\mathtt{3s\_vs\_4z}$ (easy), $\mathtt{5m\_vs\_6m}$ (hard), and $\mathtt{corridor}$ (super hard), where harder map has more agents. It is worth noting that we do not use any global state in the decentralized training and each agent learns on its own trajectory.

The results are shown in Figure 8. On the map $\mathtt{3s\_vs\_4z}$, IQL and MA2QL both converge to the winning rate of 100%. However, on the hard and super hard map $\mathtt{5m\_vs\_6m}$ and $\mathtt{corridor}$, MA2QL achieves stronger than IQL. It is worth noting that the recent study (Papoudakis et al., 2021) shows that IQL performs well in SMAC, even close to CTDE methods like QMIX (Rashid et al., 2018). Here, we show that MA2QL can still outperform IQL in three maps with various difficulties, which indicates that MA2QL can also tackle the non-stationarity problem and bring performance gain in more complex tasks.

We further investigate the influence of the hyperparameters on MA2QL and the scalability of MA2QL. First, we study the effect of $K$ (the number of Q-network updates at each turn) in the robotic control task: 3-agent Hopper. We consider $K=[4000,8000,40000]$. As shown in Figure 9(a), when $K$ is small, it outperforms IQL but still gets stuck in sub-optimal policies. On the contrary, if $K$ is large, different $K$ affects the efficiency of the learning, but not the final performance.

As discussed before, the hyperparameters are the same for IQL and MA2QL, which are well-tuned for IQL. To further study their effect on MA2QL, we conduct additional experiments in simple spread with different learning rates and in HalfCheetah with different batch sizes. As shown in Figure 9(b) and Figure 9(c), under these different hyperparameters, the performance of IQL and MA2QL varies, but MA2QL consistently outperforms IQL, which can be evidence of the gain of MA2QL over IQL is robust to the hyperparameters of IQL. The default learning rate in MPE is 0.0005 and the default batch size in multi-agent MuJoCo is 100.

As for scalability, we additionally evaluate MA2QL in 15-agent simple spread in MPE and $17\times 1$ Humanoid in multi-agent MuJoCo. As illustrated in Figure 10, MA2QL brings large performance gains over IQL in both tasks. More agents mean the environments become more complex and unstable for decentralized learning. IQL is easy to get stuck by the non-stationarity problem while MA2QL can handle it well. The results show again that alternate learning of MA2QL can sufficiently stabilize the environment during the learning process. It also indicates the good scalability of MA2QL.