Abstract
Cooperative multi-agent reinforcement learning often requires decentralisedpolicies, which severely limit the agents' ability to coordinate theirbehaviour. In this paper, we show that common knowledge between agents allowsfor complex decentralised coordination. Common knowledge arises naturally in alarge number of decentralised cooperative multi-agent tasks, for example, whenagents can reconstruct parts of each others' observations. Since agents anindependently agree on their common knowledge, they can execute complexcoordinated policies that condition on this knowledge in a fully decentralisedfashion. We propose multi-agent common knowledge reinforcement learning(MACKRL), a novel stochastic actor-critic algorithm that learns a hierarchicalpolicy tree. Higher levels in the hierarchy coordinate groups of agents byconditioning on their common knowledge, or delegate to lower levels withsmaller subgroups but potentially richer common knowledge. The entire policytree can be executed in a fully decentralised fashion. As the lowest policytree level consists of independent policies for each agent, MACKRL reduces toindependently learnt decentralised policies as a special case. We demonstratethat our method can exploit common knowledge for superior performance oncomplex decentralised coordination tasks, including a stochastic matrix gameand challenging problems in StarCraft II unit micromanagement.
Quick Read (beta)
Multi-Agent Common Knowledge
Reinforcement Learning
Abstract
Cooperative multi-agent reinforcement learning often requires decentralised policies, which severely limit the agents’ ability to coordinate their behaviour. In this paper, we show that common knowledge between agents allows for complex decentralised coordination. Common knowledge arises naturally in a large number of decentralised cooperative multi-agent tasks, for example, when agents can reconstruct parts of each others’ observations. Since agents can independently agree on their common knowledge, they can execute complex coordinated policies that condition on this knowledge in a fully decentralised fashion. We propose multi-agent common knowledge reinforcement learning (MACKRL), a novel stochastic actor-critic algorithm that learns a hierarchical policy tree. Higher levels in the hierarchy coordinate groups of agents by conditioning on their common knowledge, or delegate to lower levels with smaller subgroups but potentially richer common knowledge. The entire policy tree can be executed in a fully decentralised fashion. As the lowest policy tree level consists of independent policies for each agent, MACKRL reduces to independently learnt decentralised policies as a special case. We demonstrate that our method can exploit common knowledge for superior performance on complex decentralised coordination tasks, including a stochastic matrix game and challenging problems in StarCraft II unit micromanagement.
units \usetikzlibrarytrees
Multi-Agent Common Knowledge
Reinforcement Learning
Christian A. Schroeder de Witt^{†}^{†}thanks: Equal contribution. Correspondence to Christian Schroeder de Witt <[email protected]>^{†}^{†}thanks: University of Oxford, UK Jakob N. Foerster^{*}^{†} Gregory Farquhar^{†} Philip H. S. Torr^{†} Wendelin Böhmer^{†} Shimon Whiteson^{†}
noticebox[b]\[email protected]
1 Introduction
Cooperative multi-agent problems are ubiquitous, for example, in the coordination of autonomous cars (Cao et al., 2013). However, how to learn control policies for such systems remains a major open question. Joint action learning (JAL, Claus & Boutilier, 1998) learns centralised policies that select joint actions conditioned on the global state or joint observation. However, in order to execute such policies, the agents naturally must have access to either the global state or an instantaneous communication channel with sufficient bandwidth to enable them to aggregate their individual observations. These requirements often do not hold in practice, but even when they do, learning a centralised policy can be infeasible as the size of the joint action space grows exponentially in the number of agents. By contrast, Independent Learning (IL, Tan, 1993) learns fully decentralisable policies but introduces non-stationarity as each agent treats the other agents as part of its environment.
These difficulties motivate an alternative approach: centralised training of decentralised policies. During learning the agents can share observations, parameters, gradients, etc. without restriction but the result of learning is a set of decentralised policies such that each agent can select actions based only on its individual observations. While significant progress has been made in this direction (Rashid et al., 2018; Foerster et al., 2016, 2017, 2018; Kraemer & Banerjee, 2016; Jorge et al., 2016), the requirement that policies must be fully decentralised severely limits the agents’ ability to coordinate their behaviour. Often agents are forced to ignore information in their individual observations that would in principle be useful for maximising reward, because acting on it would make their behaviour less predictable to their teammates. This limitation is particularly salient in IL, which cannot solve many coordination tasks (Claus & Boutilier, 1998).
Common knowledge for a group of agents consists of facts that all agents know and “each individual knows that all other individuals know it, each individual knows that all other individuals know that all the individuals know it, and so on” (Osborne & Rubinstein, 1994). This may arise in a wide range of multi-agent problems, e.g., whenever a reliable communication channel is present. But common knowledge can also arise without communication, if agents can infer some part of each other’s observations. For example, if each agent can reliably observe objects within its field of view and the agents know each other’s fields of view, then they share common knowledge whenever they see each other. This setting is illustrated in Figure 1 and applies to a range of real-world scenarios, for example, to robo-soccer (Genter et al., 2017), fleets of self-driving cars and multi-agent StarCraft micromanagement (Synnaeve et al., 2016).
In the absence of common knowledge, complex decentralised coordination has to rely on implicit communication, i.e., observing each other’s actions or their effects (Heider & Simmel, 1944; Rasouli et al., 2017). However, implicit communication protocols for complex coordination problems are difficult to learn and, as they typically require multiple timesteps to execute, can limit the agility of control during execution (Tian et al., 2018). By contrast, coordination based on common knowledge is simultaneous, that is, does not require learning communication protocols (Halpern & Moses, 2000).
In this paper, we introduce multi-agent common knowledge reinforcement learning (MACKRL), a novel stochastic policy actor-critic algorithm that can learn complex coordination policies end-to-end by exploiting common knowledge between groups of agents at the appropriate level. MACKRL uses a hierarchical policy tree in order to dynamically select the right level of coordination. By conditioning joint policies on common knowledge of groups of agents, MACKRL uniquely occupies a middle ground between IL and JAL, while remaining fully decentralised.
Using a proof-of-concept matrix game, we show that MACKRL outperforms both IL and JAL. Furthermore, we use a noisy variant of the same matrix game to show that MACKRL can exploit a weaker form of group knowledge called probabilistic common knowledge (Krasucki et al., 1991), that is induced by agent beliefs over common knowledge, derived from from noisy observations. We show that MACKRL’s performance degrades gracefully with increasing noise levels.
We then apply MACKRL to challenging StarCraft II unit micromanagement tasks (Vinyals et al., 2017) from the StarCraft Multi-Agent Challenge (SMAC, Samvelyan et al., 2019). We show that simultaneous coordination based on pairwise common knowledge enables MACKRL to outperform the state-of-the-art algorithms COMA (Foerster et al., 2018) and QMIX (Rashid et al., 2018) and provide a variant of MACKRL that scales to tasks with many agents.
2 Problem Setting
Cooperative multi-agent tasks with $n$ agents $a\in \mathcal{A}$ can be modelled as decentralised partially observable Markov decision processes (Dec-POMDPs, Oliehoek et al., 2008). The state of the system is $s\in \mathcal{S}$. At each time-step, each agent $a$ receives an observation ${z}^{a}\in \mathcal{Z}$ and can select an action ${u}_{\text{env}}^{a}\in {\mathcal{U}}_{\text{env}}^{a}$. We use the env-subscript to denote actions executed by the agents in the environment, as opposed to latent ‘actions’ that may be taken by higher-level controllers of the hierarchical method introduced in Section 3. Given a joint action ${\mathbf{u}}_{\text{env}}:=({u}_{\text{env}}^{1},\mathrm{\dots},{u}_{\text{env}}^{n})\in {\mathcal{U}}_{\text{env}}$, the discrete-time system dynamics draw the successive state ${s}^{\prime}\in \mathcal{S}$ from the conditional distribution $P({s}^{\prime}|s,{\mathbf{u}}_{\text{env}})$ and yield a cooperative reward according to the function $r(s,{\mathbf{u}}_{\text{env}})$.
The agents aim to maximise the discounted return ${R}_{t}={\sum}_{l=0}^{H}{\gamma}^{l}r({s}_{t+l},{\mathbf{u}}_{t+l,\text{env}})$ from episodes of length $H$. The joint policy $\pi ({\mathbf{u}}_{\text{env}}|s)$ is restricted to a set of decentralised policies ${\pi}^{a}({u}_{\text{env}}^{a}|{\tau}_{t}^{a})$ that can be executed independently, i.e., each agent’s policy conditions only on its own action-observation history ${\tau}_{t}^{a}:=[{z}_{0}^{a},{u}_{0}^{a},{z}_{1}^{a},\mathrm{\dots},{z}_{t}^{a}]$. Following previous work (Rashid et al., 2018; Foerster et al., 2016, 2017, 2018; Kraemer & Banerjee, 2016; Jorge et al., 2016), we allow decentralised policies to be learnt in a centralised fashion.
Common knowledge of a group of agents $\mathcal{G}$ refers to facts that all members know, and that “each individual knows that all other individuals know it, each individual knows that all other individuals know that all the individuals know it, and so on” Osborne & Rubinstein (1994). Any data $\xi $ that are known to all agents before execution/training, like a shared random seed, are obviously common knowledge. Crucially, every agent $a\in \mathcal{G}$ can deduce the same history of common knowledge ${\tau}_{t}^{\mathcal{G}}$ from its own history ${\tau}_{t}^{a}$ and the commonly known data $\xi $, that is, ${\tau}_{t}^{\mathcal{G}}:={\mathcal{I}}^{\mathcal{G}}({\tau}_{t}^{a},\xi )={\mathcal{I}}^{\mathcal{G}}({\tau}_{t}^{\overline{a}},\xi ),\forall a,\overline{a}\in \mathcal{G}$. Furthermore, any actions taken by a policy ${\pi}^{\mathcal{G}}({u}_{\text{env}}^{\mathcal{G}}|{\tau}_{t}^{\mathcal{G}})$ over the group’s joint action space ${\mathcal{U}}_{\text{env}}^{\mathcal{G}}$ are themselves common knowledge, if the policy is deterministic or pseudo-random with a shared random seed and conditions only on the common history ${\tau}_{t}^{\mathcal{G}}$. Note that common knowledge of subgroups ${\mathcal{G}}^{\prime}\subset \mathcal{G}$ cannot decrease, that is, ${\mathcal{I}}^{{\mathcal{G}}^{\prime}}({\tau}_{t}^{a},\xi )\ge {\mathcal{I}}^{\mathcal{G}}({\tau}_{t}^{a},\xi )$.
Given a Dec-POMDP with noisy observations, agents might not be able to establish true common knowledge (Halpern & Moses, 2000). Instead, each agent $a$ can only deduce its own beliefs ${\stackrel{~}{\mathcal{I}}}_{a}^{\mathcal{G}}({\tau}_{t}^{a})$ over what is commonly known to a group $\mathcal{G}$ of agents. If sensor noise properties are commonly known among all agents, such agent beliefs give rise to a slightly weaker notion of group knowledge called probabilistic common knowledge (Krasucki et al., 1991).
Learning under common knowledge is a cooperative multi-agent reinforcement learning setting, where a Dec-POMDP is augmented by a common knowledge function ${\mathcal{I}}^{\mathcal{G}}$ (or probabilistic common knowledge ${\stackrel{~}{\mathcal{I}}}_{a}^{\mathcal{G}}$). Groups of agents $\mathcal{G}$ can coordinate by learning policies that condition on their common knowledge. In this paper ${\mathcal{I}}^{\mathcal{G}}$ is fixed apriori, but it could also be learnt during training. The setting accommodates a wide range of real-world and simulated multi-agent tasks. Whenever a task is cooperative and learning is centralised, then agents can naturally learn suitable ${\mathcal{I}}^{\mathcal{G}}$ or ${\stackrel{~}{\mathcal{I}}}_{a}^{\mathcal{G}}$. Policy parameters can be exchanged during training as well and become part of the commonly known data $\xi $. Joint policies where coordinated decisions of a group $\mathcal{G}$ only condition on the common knowledge of $\mathcal{G}$, can be executed in a fully decentralised fashion. In Section 3 we introduce MACKRL, which uses central training to learn fully decentralised policies under common knowledge.
Field-of-view common knowledge is a form of complete-history common knowledge (Halpern & Moses, 2000), that arises within a Dec-POMDP if agents can deduce parts of other agents’ observations from their own. In this case, an agent group’s common knowledge is the intersection of observations that all members can reconstruct from each other. In Appendix D we formalise this concept and show that, under some assumptions, common knowledge is the intersection of all agents’ sets of visible objects, if and only if all agents can see each other. Figure 1 shows an example for three agents with circular fields of view. If observations are noisy, each agent bases its belief on its own noisy observations thus inducing an equivalent form of probabilistic common knowledge ${\stackrel{~}{\mathcal{I}}}_{a}^{\mathcal{G}}$.
Field-of-view common knowledge naturally occurs in many interesting real-world tasks, such as autonomous driving (Cao et al., 2013) and robo-soccer (Genter et al., 2017), as well as in simulated benchmarks such as StarCraft II (Vinyals et al., 2017). A large number of cooperative multi-agent tasks can therefore benefit from common knowledge-based coordination introduced in this paper.
3 Multi-Agent Common Knowledge Reinforcement Learning
The key idea behind MACKRL is to learn decentralised policies that are nonetheless coordinated by common knowledge. As the common knowledge history ${\tau}_{t}^{\mathcal{G}}$ of a group of agents $\mathcal{G}$ can be deduced by every member, i.e., ${\tau}_{t}^{\mathcal{G}}={\mathcal{I}}^{\mathcal{G}}({\tau}_{t}^{a},\xi ),\forall a\in \mathcal{G}$, any deterministic function based only on ${\tau}_{t}^{\mathcal{G}}$ can thus be independently computed by every member as well. The same holds for pseudo-random functions like stochastic policies, if they condition on a commonly known random seed in $\xi $.
MACKRL uses a hierarchical policy $\pi ({\mathbf{u}}_{\text{env}}|{\{{\tau}_{t}^{a}\}}_{a\in \mathcal{A}},\xi )$ over the joint environmental action space of all agents ${\mathcal{U}}_{\text{env}}$. The hierarchy forms a tree of sub-policies ${\pi}^{\mathcal{G}}$ over groups $\mathcal{G}$, where the root ${\pi}^{\mathcal{A}}$ covers all agents. Each sub-policy ${\pi}^{\mathcal{G}}({u}^{\mathcal{G}}|{\mathcal{I}}^{\mathcal{G}}({\tau}_{t}^{a},\xi ))$ conditions on the common knowledge of $\mathcal{G}$, including a shared random seed in $\xi $, and can thus be executed by every member of $\mathcal{G}$ independently. The corresponding action space ${\mathcal{U}}^{\mathcal{G}}$ contains the environmental actions of the group ${\mathbf{u}}_{\text{env}}^{\mathcal{G}}\in {\mathcal{U}}_{\text{env}}^{\mathcal{G}}$ and/or a set of group partitions, that is, ${\mathbf{u}}^{\mathcal{G}}=\{{\mathcal{G}}_{1},\mathrm{\dots},{\mathcal{G}}_{k}\}$ with ${\mathcal{G}}_{i}\cap {\mathcal{G}}_{j}=\mathrm{\varnothing},\forall i\ne j$ and ${\cup}_{i=1}^{k}{\mathcal{G}}_{i}=\mathcal{G}$. Choosing a partition ${\mathbf{u}}^{\mathcal{G}}\ne {\mathcal{U}}_{\text{env}}^{\mathcal{G}}$ yields control to the sub-policies ${\pi}^{{\mathcal{G}}_{i}}$ of the partition’s subgroups ${\mathcal{G}}_{i}\in {\mathbf{u}}^{\mathcal{G}}$. This can be an advantage in states where the common history ${\tau}_{t}^{{\mathcal{G}}_{i}}$ of the subgroups is more informative than ${\tau}_{t}^{\mathcal{G}}$. All action spaces have to be specified in advance, which induces the hierarchical tree structure of the joint policy. Algorithm 2 shows the decentralised sampling of environmental actions from the hierarchical joint policy as seen by an individual agent $a\in \mathcal{A}$.
[b!] \[email protected]@algorithmic \Functionselect_action$a,{\tau}_{t}^{a},\xi $ \Commentrandom seed in $\xi $ is common knowledge \State$\mathcal{G}:=\mathcal{A}$ \Commentinitialise the group $\mathcal{G}$ of all agents \State${\mathbf{u}}_{t}^{\mathcal{G}}\sim {\pi}^{\mathcal{G}}(\cdot |{\mathcal{I}}^{\mathcal{G}}({\tau}_{t}^{a},\xi ))$ \Comment${\mathbf{u}}_{t}^{\mathcal{G}}$ is either a joint environmental action in ${\mathcal{U}}_{\text{env}}^{\mathcal{G}}$… \While${\mathbf{u}}_{t}^{\mathcal{G}}\notin {\mathcal{U}}_{\text{env}}^{\mathcal{G}}$ \Comment… or a set of disjoint subgroups $\{{\mathcal{G}}_{1},\mathrm{\dots},{\mathcal{G}}_{k}\}$ \State$\mathcal{G}:=\{{\mathcal{G}}^{\prime}|a\in {\mathcal{G}}^{\prime},{\mathcal{G}}^{\prime}\in {\mathbf{u}}_{t}^{\mathcal{G}}\}$ \Commentselect subgroup containing agent $a$ \State${\mathbf{u}}_{t}^{\mathcal{G}}\sim {\pi}^{\mathcal{G}}(\cdot |{\mathcal{I}}^{\mathcal{G}}({\tau}_{t}^{a},\xi ))$ \Commentdraw an action for that subgroup \EndWhile\Return${u}_{t}^{a}$ \Commentreturn environmental action ${u}_{t}^{a}\in {\mathcal{U}}_{\text{env}}^{\mathcal{G}}$ of agent $a$ \EndFunction
As the common knowledge of a group with only one agent $\mathcal{G}=\{a\}$ is ${\mathcal{I}}^{\{a\}}({\tau}^{a},\xi )={\tau}^{a}$, fully decentralised policies are a special case of MACKRL policies: in this case, the root policy ${\pi}^{\mathcal{A}}$ has only one action ${\mathcal{U}}^{\mathcal{A}}:=\{{\mathbf{u}}^{\mathcal{A}}\}$, ${\mathbf{u}}^{\mathcal{A}}:=\{\{1\},\mathrm{\dots},\{n\}\}$, and all leaf policies ${\pi}^{\{a\}}$ have only environmental actions ${\mathcal{U}}^{\{a\}}:={\mathcal{U}}_{\text{env}}^{a}$.
3.1 Pairwise MACKRL
To give an example of one possible MACKRL architecture, we define Pairwise MACKRL, illustrated in Figure 2. As joint action spaces grow exponentially in the number of agents, we restrict ourselves to pairwise joint policies and define a three-level hierarchy of controllers.
The root of this hierarchy is the pair selector ${\pi}_{\text{ps}}^{\mathcal{A}}$, with an action set ${\mathcal{U}}_{\text{ps}}^{\mathcal{A}}$ that contains all possible partitions of agents into pairs $\{\{{a}_{1},{\overline{a}}_{1}\},\mathrm{\dots},\{{a}_{n/2},{\overline{a}}_{n/2}\}\}=:{\mathbf{u}}^{\mathcal{A}}\in {\mathcal{U}}_{\text{ps}}^{\mathcal{A}}$, but no environmental actions. If there are an odd number of agents, then one agent is put in a singleton group. At the second level, each pair controller ${\pi}_{\text{pc}}^{a\overline{a}}$ of the pair $\mathcal{G}=\{a,\overline{a}\}$ can choose between joint actions ${\mathbf{u}}_{\text{env}}^{a\overline{a}}\in {\mathcal{U}}_{\text{env}}^{a}\times {\mathcal{U}}_{\text{env}}^{\overline{a}}$ and one delegation action ${u}_{d}^{a\overline{a}}:=\{\{a\},\{\overline{a}\}\}$, i.e. ${\mathcal{U}}_{\text{pc}}^{a\overline{a}}:={\mathcal{U}}_{\text{env}}^{a}\times {\mathcal{U}}_{\text{env}}^{\overline{a}}\cup \{{u}_{d}^{a\overline{a}}\}$. At the third level, individual controllers ${\pi}^{a}$ select an individual action ${u}_{\text{env}}^{a}\in {\mathcal{U}}_{\text{env}}^{a}$ for a single agent $a$. This architecture retains manageable joint action spaces, while considering all possible pairwise coordination configurations. Fully decentralised policies are the special case when all pair controllers always choose partition ${u}_{d}^{a\overline{a}}$ to delegate.
Unfortunately, the number of possible pairwise partitions is $O(n!)$, which limits the algorithm to medium sized sets of agents. For example, $n=11$ agents induce $|{\mathcal{U}}_{\text{ps}}^{\mathcal{A}}|=10395$ unique partitions. To scale our approach to tasks with many agents, we first of all share network parameters between all pair selectors with identical action spaces to greatly increase sample efficiency. We also investigate a variant in which the action space of the pair selector ${\pi}_{\text{ps}}^{\mathcal{A}}$ is only a fixed random subset of all possible pairwise partitions. This restricts agent coordination to a smaller set of predefined pairs, but does not necessarily affect MACKRL’s performance dramatically (see Section 4.2).
3.2 Training
{algorithm}[t!] \[email protected]@algorithmic \Functionjoint_policy${\mathbf{u}}_{\text{env}}^{\mathcal{G}}|\mathcal{G},{\{{\tau}_{t}^{a}\}}_{a\in \mathcal{G}},\xi $ \Commentrandom seed in $\xi $ is common knowledge \State${a}^{\prime}\sim \mathcal{G};{\mathbf{I}}^{\mathcal{G}}:={\mathcal{I}}^{\mathcal{G}}({\tau}_{t}^{{a}^{\prime}},\xi )$ \Commentcommon knowledge ${\mathbf{I}}^{\mathcal{G}}$ is identical for every agent ${a}^{\prime}\in \mathcal{G}$ \State${p}_{\text{env}}:=0$ \Commentinitialise probability for choosing environmental joint action ${\mathbf{u}}_{\text{env}}^{\mathcal{G}}$ \For${\mathbf{u}}^{\mathcal{G}}\in {\mathcal{U}}^{\mathcal{G}}$ \Commentadd probability to choose ${\mathbf{u}}_{\text{env}}^{\mathcal{G}}$ for all outcomes of ${\pi}^{\mathcal{G}}$ \If${\mathbf{u}}^{\mathcal{G}}={\mathbf{u}}_{\text{env}}^{\mathcal{G}}$ \Commentif ${\mathbf{u}}^{\mathcal{G}}$ is the environmental joint action in question \State${p}_{\text{env}}:={p}_{\text{env}}+{\pi}^{\mathcal{G}}\left({\mathbf{u}}_{\text{env}}^{\mathcal{G}}|{\mathbf{I}}^{\mathcal{G}}\right)$ \EndIf \If${\mathbf{u}}^{\mathcal{G}}\notin {\mathcal{U}}_{\text{env}}^{\mathcal{G}}$ \Commentif ${\mathbf{u}}^{\mathcal{G}}=\{{\mathcal{G}}^{1},\mathrm{\dots},{\mathcal{G}}^{k}\}$ is a set of disjoint subgroups \State${p}_{\text{env}}:={p}_{\text{env}}+{\pi}^{\mathcal{G}}\left({\mathbf{u}}^{\mathcal{G}}|{\mathbf{I}}^{\mathcal{G}}\right)\prod _{{\mathcal{G}}^{\prime}\in {\mathbf{u}}^{\mathcal{G}}}\mathrm{\text{joint\_policy}}\left({\mathbf{u}}_{\text{env}}^{{\mathcal{G}}^{\prime}}|{\mathcal{G}}^{\prime},{\{{\tau}_{t}^{a}\}}_{a\in {\mathcal{G}}^{\prime}},\xi \right)$ \EndIf\EndFor\Return${p}_{\text{env}}$ \Commentreturn probability that controller ${\pi}^{\mathcal{G}}$ would have chosen ${\mathbf{u}}_{\text{env}}^{\mathcal{G}}$ \EndFunction
We train policies belonging to the MACKRL family based on Central-V (Foerster et al., 2018), a stochastic policy gradient algorithm (Williams, 1992) with a centralised critic. Unlike the decentralised policy, we condition the centralised critic on the state ${s}_{t}\in \mathcal{S}$ and the last actions of all agents ${\mathbf{u}}_{\text{env},t-1}\in {\mathcal{U}}_{\text{env}}$. We do not use the multi-agent counterfactual baseline proposed by Foerster et al. (2018), because MACKRL effectively turns training into a single agent problem by inducing a correlated probability across the joint action space. Algorithm 3.2 shows how the probability of choosing a joint environmental action ${\mathbf{u}}_{\text{env}}^{\mathcal{G}}\in {\mathcal{U}}_{\text{env}}^{\mathcal{G}}$ of group $\mathcal{G}$ is computed: the probability of choosing the action in question is added to the recursive probabilities that each partition ${\mathbf{u}}^{\mathcal{G}}\notin {\mathcal{U}}_{\text{env}}^{\mathcal{G}}$ would have selected it. Note that Algorithm 2 only traverses one branch of the tree during execution.
At time $t$, the gradient with respect to the parameters $\theta $ of the joint policy $\pi ({\mathbf{u}}_{\text{env}}|{\{{\tau}_{t}^{a}\}}_{a\in \mathcal{A}},\xi )$ is:
$${\nabla}_{\theta}{J}_{t}=\left(\underset{\text{sample estimate of the advantage function}}{\underset{\u23df}{r({s}_{t},{\mathbf{u}}_{\text{env},t})+\gamma V({s}_{t+1},{\mathbf{u}}_{\text{env},t})-V({s}_{t},{\mathbf{u}}_{\text{env},t-1})}}\right){\nabla}_{\theta}\mathrm{log}\left(\underset{\mathrm{\text{joint\_policy}}({\mathbf{u}}_{\text{env},t}|\mathcal{A},{\{{\tau}_{t}^{a}\}}_{a\in \mathcal{A}},\xi )}{\underset{\u23df}{\pi ({\mathbf{u}}_{\text{env},t}|{\{{\tau}_{t}^{a}\}}_{a\in \mathcal{A}},\xi )}}\right),$$ | (1) |
The value function $V$ is learned by gradient descent on the TD($\lambda $) loss (Sutton & Barto, 1998).
4 Experiments and Results
We evaluate Pairwise MACKRL (henceforth referred to as MACKRL) on two environments: First, we use a matrix game with special coordination requirements to illustrate MACKRL’s ability to surpass both IL and JAL. Secondly, we employ MACKRL with deep recurrent neural network policies in order to outperform state-of-the-art baselines on a number of challenging StarCraft II unit micromanagement tasks. Finally, we analyse MACKRL’s robustness to sensor noise and its scalability to large numbers of agents to illustrate its applicability to real-world tasks.
4.1 Single-step matrix game
To demonstrate how MACKRL trades off between independent and joint action selection, we evaluate a two-agent matrix game with partial observability. In each round, a fair coin toss decides which of the two matrix games in Figure 3 [left] is played. Both agents can observe which game has been selected if the observable common knowledge bit is set. If the bit is not set, each agent observes the correct game only with probability 0.5, and is given no observation otherwise. Crucially, whether agents can observe the current game is in this case determined independently of each other. Even if both agents can observe which game is played, this observation is no longer common knowledge and cannot be used to infer the choices of the other agent.
Figure 3 [middle] shows MACKRL’s performance as a function of the probability of observing the common knowledge bit. We contrast this with JAL, which selects both agents’ actions together. With JAL, the agents learn the optimal decision for each matrix, but this decision yields no reward in the other matrix. As the probability for common knowledge increases, so does the probability of observing the current game. JAL’s expected reward closely follows the latter probability. This indicates that JAL learns each game perfectly, but does not find the optimal policy in the case of no observations. In contrast, the optimal no observation policy is found by independent actor-critic (IAC), which is a variant of IL where each agent uses an actor-critic approach. However, as IAC agents have no knowledge of each other’s actions, they find only a suboptimal solution when they can in fact observe which game is played. As expected, MACKRL smoothly interpolates between these extremes. For no common knowledge, MACKRL behaves like IAC, but the exploitation of available common knowledge allows each agent to anticipate the other’s actions. MACKRL therefore outperforms IAC and JAL in almost all cases. Inspecting the policy verifies that MACKRL learns the optimal policy, which is to delegate to the independent controllers whenever the common knowledge bit is absent and let the pair controllers execute a joint action otherwise.
To assess MACKRL’s performance in the case of probabilistic common knowledge (see Section 2), we also consider the case where the observed common knowledge bit of individual agents is randomly flipped with probability $p$. This noise means that agents can no longer guarantee that they consistently choose the same coordinated actions at all times. However, using correlated sampling, agents can ensure that such inconsistencies are minimised (see Bavarian et al. (2016) and Appendix D). Figure 3 [right] shows MACKRL’s performance decline remarkably graceful with increasing observation noise. This illustrates MACKRL’s applicability to real-world tasks with noisy observation sensors.
4.2 StarCraft II micromanagement
To demonstrate MACKRL’s ability to solve complex coordination tasks, we evaluate it on a challenging multi-agent version of StarCraft II (SCII) micromanagement. To this end, we report performance on three challenging coordination tasks from the established multi-agent benchmark SMAC (Samvelyan et al., 2019).
The first task, map 2s3z, contains mixed unit types, where both the MACKRL agent and the game engine each control two Stalkers and three Zealots. Stalkers are ranged-attack units that take heavy damage from melee-type Zealots. Consequently, a winning strategy needs to be able to dynamically coordinate between letting one’s own Zealots attack enemy Stalkers, and when to backtrack in order to defend one’s own Stalkers against enemy Zealots. The challenge of this coordination task results in a particularly poor performance of Independent Learning (Samvelyan et al., 2019).
The second task, map 3m, presents both sides with three Marines, which are medium-ranged infantry units. The coordination challenge on this map is to reduce enemy fire power as quickly as possible by focusing unit fire to defeat each enemy unit in turn. The third task, map 8m, scales this task up to eight Marines on both sides. The relatively large number of agents involved poses additional scalability challenges.
On all maps, the units are subject to partial observability constraints and have a circular field of view with fixed radius. Common knowledge ${\mathcal{I}}^{\mathcal{G}}$ between groups $\mathcal{G}$ of agents arises through entity-based field-of-view common knowledge (see Section 2 and Appendix D).
We compare MACKRL to Central-V (Foerster et al., 2018), as well as COMA (Foerster et al., 2018) and QMIX (Rashid et al., 2018), where the latter is an off-policy value-based algorithm that is the current state-of-the-art on all maps. We omit IL results since it is known to do comparatively poorly (Samvelyan et al., 2019).
All experiments use SMAC settings for comparability (Samvelyan et al., 2019) (see Appendix B for details). In addition, MACKRL and its within-class baseline Central-V share equal hyper-parameters as far as applicable.
MACKRL outperforms the Central-V baseline in terms of sample efficiency and limit performance on all maps (see Figure 4). All other parameters being equal, this suggests that MACKRL’s superiority over Central-V is due to its ability to exploit common knowledge. In Appendix C, we confirm this conclusion by showing that the policies learnt by the pair controllers are almost always preferred over individual controllers whenever agents have access to substantial amounts of common knowledge.
MACKRL also significantly outperforms COMA and QMIX on all maps in terms of sample efficiency, with a similar limit performance to QMIX (see Figure 4). These results are particularly noteworthy as MACKRL employs neither a sophisticated multi-agent baseline, like COMA, nor an off-policy replay buffer, like QMIX.
As mentioned in Section 3.1, the number of possible agent partitions available to the pair selector ${\pi}_{\text{ps}}^{\mathcal{A}}$ grows as $\mathcal{O}(n!)$. We evaluate a scalable variant of MACKRL that constrains the number of partitions to a fixed subset, which is drawn randomly before training. Figure 5 shows that sample efficiency declines gracefully with subsample size. MACKRL’s policies appear able to exploit any common knowledge configurations available, even if the set of allowed partitions is not exhaustive.
5 Related Work
Multi-agent reinforcement learning (MARL) has been studied extensively in small environments (Busoniu et al., 2008; Yang & Gu, 2004), but scaling it to large state spaces or many agents has proved problematic. Guestrin et al. (2002a) propose the use of coordination graphs, which exploit conditional independence properties between agents that are captured in an undirected graphical model, in order to efficiently select joint actions. Sparse cooperative $Q$-learning (Kok & Vlassis, 2004) also uses coordination graphs to efficiently maximise over joint actions in the $Q$-learning update rule. Whilst these approaches allow agents to coordinate optimally, they require the coordination graph to be known and for the agents to either observe the global state or to be able to freely communicate. Even then, this approach is still being intractable in the worst case.
There has been much work on scaling MARL to handle complex, high dimensional state and action spaces. In the setting of fully centralised training and execution, Usunier et al. (2016) frame the problem as a greedy MDP and train a centralised controller to select actions for each agent in a sequential fashion. Sukhbaatar et al. (2016) and Peng et al. (2017) train factorised but centralised controllers that use special network architectures to share information between agents. These approaches assume unlimited bandwidth for communication.
One way to decentralise the agents’ policies is to learn a separate $Q$-function for each agent as in Independent $Q$-Learning (Tan, 1993). Foerster et al. (2017) and Omidshafiei et al. (2017) examine the problem of instability that arises from the non-stationarity of the environment induced by both the agents’ exploration and their changing policies. Rashid et al. (2018) and Sunehag et al. (2017) propose learning a centralised value function that factors into per-agent components. Gupta et al. (2017) learn separate policies for each agent in an actor-critic framework, where the critic for each agent conditions only on per-agent information. Foerster et al. (2018) and Lowe et al. (2017) propose a single centralised critic with decentralised actors. None of these approaches explicitly learns a policy over joint actions and hence are limited in the coordination they can achieve.
Thomas et al. (2014) explore the psychology of common knowledge and coordination. Rubinstein (1989) shows that any finite number of reasoning steps, short of the infinite number required for common knowledge, can be insufficient for achieving coordination (cf. Appendix D). Korkmaz et al. (2014) examine common knowledge in scenarios where agents use Facebook-like communication.Brafman & Tennenholtz (2003) use a common knowledge protocol to improve coordination in common interest stochastic games but, in contrast to our approach, establish common knowledge about agents’ action sets and not about subsets of their observation spaces.
Aumann et al. (1974) introduce the concept of a correlated equilibrium, whereby a shared correlation device helps agents coordinate better. Cigler & Faltings (2013) examine how the agents can reach such an equilibrium when given access to a simple shared correlation vector and a communication channel. Boutilier (1999) augments the state space with a coordination mechanism, to ensure coordination between agents is possible in a fully observable multi-agent setting. This is in general not possible in the partially observable setting we consider.
Amato et al. (2014) propose MacDec-POMDPs, which use hierarchically optimal policies that allow agents to undertake temporally extended macro-actions. Liu et al. (2017) investigate how to learn such models in environments where the transition dynamics are not known. Makar et al. (2001) extend the MAXQ single-agent hierarchical framework (Dietterich, 2000) to the multi-agent domain. They allow certain policies in the hierarchy to be cooperative, which entails learning the joint action-value function and allows for faster coordination across agents. Kumar et al. (2017) use a hierarchical controller that produces subtasks for each agent and chooses which pairs of agents should communicate in order to select their actions. Oh & Smith (2008) employ a hierarchical learning algorithm for cooperative control tasks where the outer layer decides whether an agent should coordinate or act independently, and the inner layer then chooses the agent’s action accordingly. In contrast with our approach, these methods require communication during execution and some of them do not test on sequential tasks.
Nayyar et al. (2013) show that common knowledge can be used to reformulate decentralised planning problems as POMDPs to be solved by a central coordinator using dynamic programming. However, they do not propose a method for scaling this to high dimensions. By contrast, MACKRL is entirely model-free and learns trivially decentralisable control policies end-to-end.
Guestrin et al. (2002b) represent agents’ value functions as a sum of context-specific value rules that are part of the agents’ fixed a priori common knowledge. By contrast, MACKRL learns such value rules dynamically during training and does not require explicit communication during execution.
6 Conclusion and Future Work
We proposed that common knowledge can be used in order to improve the ability of decentralised policies to coordinate. To this end, we introduce MACKRL, an algorithm which allows a team of agents to learn a fully decentralised policy that nonetheless can select actions jointly by using the common knowledge available. MACKRL uses a hierarchy of controllers that can either select joint actions for a pair or delegate to independent controllers. In evaluation on a matrix game and a challenging multi-agent version of StarCraft II micromanagement, MACKRL outperforms strong baselines and even exceeds state-of-the-art by exploiting common knowledge. We present versions of MACKRL with approximations that allow scaling to larger numbers of agents and demonstrate robustness to observation noise. In future work, we would like to explore off-policy variants of MACKRL and investigate how limited-bandwidth communication can be exploited in the presence of common knowledge.
Acknowledgements
We would like to thank Chia-Man Hung, Tim Rudner and Tabish Rashid for valuable discussions.
This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement number 637713), the National Institutes of Health (grant agreement number R01GM114311), EPSRC/MURI grant EP/N019474/1 and the JP Morgan Chase Faculty Research Award. This work is linked to and partly funded by the project Free the Drones (FreeD) under the Innovation Fund Denmark and Microsoft. It was also supported by the Oxford-Google DeepMind Graduate Scholarship and a generous equipment grant from NVIDIA.
References
- Amato et al. (2014) Amato, C., Konidaris, G. D., and Kaelbling, L. P. Planning with macro-actions in decentralized POMDPs. In Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems, pp. 1273–1280. International Foundation for Autonomous Agents and Multiagent Systems, 2014.
- Aumann et al. (1974) Aumann, R. J. et al. Subjectivity and correlation in randomized strategies. Journal of mathematical Economics, 1(1):67–96, 1974.
- Bavarian et al. (2016) Bavarian, M., Ghazi, B., Haramaty, E., Kamath, P., Rivest, R. L., and Sudan, M. The optimality of correlated sampling. 2016. URL http://arxiv.org/abs/1612.01041.
- Boutilier (1999) Boutilier, C. Sequential optimality and coordination in multiagent systems. In IJCAI, volume 99, pp. 478–485, 1999.
- Brafman & Tennenholtz (2003) Brafman, R. I. and Tennenholtz, M. Learning to coordinate efficiently: a model-based approach. In Journal of Artificial Intelligence Research, volume 19, pp. 11–23, 2003.
- Busoniu et al. (2008) Busoniu, L., Babuska, R., and De Schutter, B. A comprehensive survey of multiagent reinforcement learning. IEEE Transactions on Systems Man and Cybernetics Part C Applications and Reviews, 38(2):156, 2008.
- Cao et al. (2013) Cao, Y., Yu, W., Ren, W., and Chen, G. An overview of recent progress in the study of distributed multi-agent coordination. IEEE Transactions on Industrial informatics, 9(1):427–438, 2013.
- Cigler & Faltings (2013) Cigler, L. and Faltings, B. Decentralized anti-coordination through multi-agent learning. Journal of Artificial Intelligence Research, 47:441–473, 2013.
- Claus & Boutilier (1998) Claus, C. and Boutilier, C. The dynamics of reinforcement learning cooperative multiagent systems. In Proceedings of the Fifteenth National Conference on Artificial Intelligence, pp. 746–752, June 1998.
- Dietterich (2000) Dietterich, T. G. Hierarchical reinforcement learning with the MAXQ value function decomposition. Journal Artificial Intelligence Research, 13(1):227–303, November 2000. ISSN 1076-9757.
- Foerster et al. (2016) Foerster, J., Assael, Y. M., de Freitas, N., and Whiteson, S. Learning to communicate with deep multi-agent reinforcement learning. In Advances in Neural Information Processing Systems, pp. 2137–2145, 2016.
- Foerster et al. (2017) Foerster, J., Nardelli, N., Farquhar, G., Torr, P., Kohli, P., Whiteson, S., et al. Stabilising experience replay for deep multi-agent reinforcement learning. In Proceedings of The 34th International Conference on Machine Learning, 2017.
- Foerster et al. (2018) Foerster, J., Farquhar, G., Afouras, T., Nardelli, N., and Whiteson, S. Counterfactual multi-agent policy gradients. In AAAI, 2018.
- Genter et al. (2017) Genter, K., Laue, T., and Stone, P. Three years of the robocup standard platform league drop-in player competition. Autonomous Agents and Multi-Agent Systems, 31(4):790–820, 2017.
- Guestrin et al. (2002a) Guestrin, C., Koller, D., and Parr, R. Multiagent planning with factored MDPs. In Advances in neural information processing systems, pp. 1523–1530, 2002a.
- Guestrin et al. (2002b) Guestrin, C., Venkataraman, S., and Koller, D. Context-specific multiagent coordination and planning with factored MDPs. In AAAI/IAAI, 2002b.
- Gupta et al. (2017) Gupta, J. K., Egorov, M., and Kochenderfer, M. Cooperative multi-agent control using deep reinforcement learning. 2017.
- Halpern & Moses (2000) Halpern, J. Y. and Moses, Y. Knowledge and common knowledge in a distributed environment. arXiv:cs/0006009, June 2000. URL http://arxiv.org/abs/cs/0006009. arXiv: cs/0006009.
- Heider & Simmel (1944) Heider, F. and Simmel, M. An experimental study of apparent behavior. The American Journal of Psychology, 57(2):243–259, 1944. ISSN 0002-9556. doi: 10.2307/1416950. URL https://www.jstor.org/stable/1416950.
- Holenstein (2007) Holenstein, T. Parallel repetition: simplifications and the no-signaling case. In Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing, STOC ’07, pp. 411–419. ACM, 2007. ISBN 978-1-59593-631-8. doi: 10.1145/1250790.1250852. URL http://doi.acm.org/10.1145/1250790.1250852.
- Jorge et al. (2016) Jorge, E., Kageback, M., and Gustavsson, E. Learning to play Guess Who? and inventing a grounded language as a consequence. arXiv preprint arXiv:1611.03218, 2016.
- Kok & Vlassis (2004) Kok, J. R. and Vlassis, N. Sparse cooperative Q-learning. In Proceedings of the twenty-first international conference on Machine learning, pp. 61. ACM, 2004.
- Konda & Tsitsiklis (1999) Konda, V. R. and Tsitsiklis, J. N. Actor-critic algorithms. In NIPS, volume 13, pp. 1008–1014, 1999.
- Korkmaz et al. (2014) Korkmaz, G., Kuhlman, C. J., Marathe, A., Marathe, M. V., and Vega-Redondo, F. Collective action through common knowledge using a Facebook model. In Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems, pp. 253–260. International Foundation for Autonomous Agents and Multiagent Systems, 2014.
- Kraemer & Banerjee (2016) Kraemer, L. and Banerjee, B. Multi-agent reinforcement learning as a rehearsal for decentralized planning. Neurocomputing, 190:82–94, 2016.
- Krasucki et al. (1991) Krasucki, P., Parikh, R., and Ndjatou, G. Probabilistic knowledge and probabilistic common knowledge. pp. 1–8, May 1991.
- Kumar et al. (2017) Kumar, S., Shah, P., Hakkani-Tur, D., and Heck, L. Federated control with hierarchical multi-agent deep reinforcement learning. arXiv preprint arXiv:1712.08266, 2017.
- Liu et al. (2017) Liu, M., Sivakumar, K., Omidshafiei, S., Amato, C., and How, J. P. Learning for multi-robot cooperation in partially observable stochastic environments with macro-actions. arXiv preprint arXiv:1707.07399, 2017.
- Lowe et al. (2017) Lowe, R., Wu, Y., Tamar, A., Harb, J., Abbeel, P., and Mordatch, I. Multi-agent actor-critic for mixed cooperative-competitive environments. arXiv preprint arXiv:1706.02275, 2017.
- Makar et al. (2001) Makar, R., Mahadevan, S., and Ghavamzadeh, M. Hierarchical multi-agent reinforcement learning. In Proceedings of the fifth international conference on Autonomous agents, pp. 246–253. ACM, 2001.
- Nayyar et al. (2013) Nayyar, A., Mahajan, A., and Teneketzis, D. Decentralized stochastic control with partial history sharing: a common information approach, 2013.
- Oh & Smith (2008) Oh, J. and Smith, S. F. A few good agents: multi-agent social learning. In AAMAS, 2008. doi: 10.1145/1402383.1402434.
- Oliehoek et al. (2008) Oliehoek, F. A., Spaan, M. T. J., and Vlassis, N. Optimal and approximate Q-value functions for decentralized POMDPs. 32:289–353, 2008.
- Omidshafiei et al. (2017) Omidshafiei, S., Pazis, J., Amato, C., How, J. P., and Vian, J. Deep decentralized multi-task multi-agent RL under partial observability. arXiv preprint arXiv:1703.06182, 2017.
- Osborne & Rubinstein (1994) Osborne, M. J. and Rubinstein, A. A course in game theory. MIT press, 1994.
- Peng et al. (2017) Peng, P., Yuan, Q., Wen, Y., Yang, Y., Tang, Z., Long, H., and Wang, J. Multiagent bidirectionally-coordinated nets for learning to play starcraft combat games. arXiv preprint arXiv:1703.10069, 2017.
- Rashid et al. (2018) Rashid, T., Samvelyan, M., de Witt, C. S., Farquhar, G., Foerster, J., and Whiteson, S. QMIX: monotonic value function factorisation for deep multi-agent reinforcement learning. In Proceedings of The 35th International Conference on Machine Learning, 2018.
- Rasouli et al. (2017) Rasouli, A., Kotseruba, I., and Tsotsos, J. K. Agreeing to cross: how drivers and pedestrians communicate. arXiv:1702.03555 [cs], February 2017. URL http://arxiv.org/abs/1702.03555. arXiv: 1702.03555.
- Rubinstein (1989) Rubinstein, A. The electronic mail game: strategic behavior under "almost common knowledge". The American Economic Review, pp. 385–391, 1989.
- Samvelyan et al. (2019) Samvelyan, M., Rashid, T., de Witt, C. S., Farquhar, G., Nardelli, N., Rudner, T. G. J., Hung, C.-M., Torr, P. H. S., Foerster, J., and Whiteson, S. The starcraft multi-agent challenge. CoRR, abs/1902.04043, 2019.
- Sukhbaatar et al. (2016) Sukhbaatar, S., Szlam, A., and Fergus, R. Learning multiagent communication with backpropagation. In Advances in Neural Information Processing Systems, pp. 2244–2252, 2016.
- Sunehag et al. (2017) Sunehag, P., Lever, G., Gruslys, A., Czarnecki, W. M., Zambaldi, V., Jaderberg, M., Lanctot, M., Sonnerat, N., Leibo, J. Z., Tuyls, K., et al. Value-decomposition networks for cooperative multi-agent learning. arXiv preprint arXiv:1706.05296, 2017.
- Sutton & Barto (1998) Sutton, R. S. and Barto, A. G. Reinforcement learning: an introduction, volume 1. MIT press Cambridge, 1998.
- Sutton et al. (1999) Sutton, R. S., McAllester, D. A., Singh, S. P., Mansour, Y., et al. Policy gradient methods for reinforcement learning with function approximation. In NIPS, volume 99, pp. 1057–1063, 1999.
- Synnaeve et al. (2016) Synnaeve, G., Nardelli, N., Auvolat, A., Chintala, S., Lacroix, T., Lin, Z., Richoux, F., and Usunier, N. Torchcraft: a library for machine learning research on real-time strategy games. arXiv preprint arXiv:1611.00625, 2016.
- Tan (1993) Tan, M. Multi-agent reinforcement learning: independent vs. cooperative agents. In Proceedings of the tenth international conference on machine learning, pp. 330–337, 1993.
- Thomas et al. (2014) Thomas, K. A., DeScioli, P., Haque, O. S., and Pinker, S. The psychology of coordination and common knowledge. Journal of personality and social psychology, 107(4):657, 2014.
- Tian et al. (2018) Tian, Z., Zou, S., Warr, T., Wu, L., and Wang, J. Learning to communicate implicitly by actions. arXiv:1810.04444 [cs], October 2018. URL http://arxiv.org/abs/1810.04444. arXiv: 1810.04444.
- Usunier et al. (2016) Usunier, N., Synnaeve, G., Lin, Z., and Chintala, S. Episodic exploration for deep deterministic policies: an application to starcraft micromanagement tasks. arXiv preprint arXiv:1609.02993, 2016.
- Vinyals et al. (2017) Vinyals, O., Ewalds, T., Bartunov, S., Georgiev, P., Vezhnevets, A. S., Yeo, M., Makhzani, A., Küttler, H., Agapiou, J., Schrittwieser, J., Quan, J., Gaffney, S., Petersen, S., Simonyan, K., Schaul, T., van Hasselt, H., Silver, D., Lillicrap, T. P., Calderone, K., Keet, P., Brunasso, A., Lawrence, D., Ekermo, A., Repp, J., and Tsing, R. Starcraft II: a new challenge for reinforcement learning. CoRR, abs/1708.04782, 2017.
- Williams (1992) Williams, R. J. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229–256, 1992.
- Yang & Gu (2004) Yang, E. and Gu, D. Multiagent reinforcement learning for multi-robot systems: a survey. Technical report, tech. rep, 2004.
Appendix
Appendix A Pairwise MACKRL
This section aims to give a better intuition about Pairwise MACKRL using the example of three agents $\mathcal{A}:=\{1,2,3\}$. The explicitly written-out joint policy of Pairwise MACKRL for these agents is:
${\bm{\pi}}_{\theta}({u}_{\text{env}}^{1},{u}_{\text{env}}^{2},{u}_{\text{env}}^{3})$ | $={\pi}_{\text{ps},\theta}^{\mathcal{A}}({u}_{\text{ps}}^{\mathcal{A}}=\{\{1\},\{2,3\}\}|{\mathcal{I}}_{s}^{1,2,3})\cdot {\pi}_{\theta}^{1}({u}_{\text{env}}^{1}|{\tau}^{1})$ | ||
$\mathrm{\hspace{1em}\hspace{1em}}\cdot \left({\pi}_{\text{pc},\theta}^{2,3}({u}_{\text{env}}^{2,3}|{\mathcal{I}}_{s}^{2,3})+{\pi}_{\text{pc},\theta}^{2,3}({u}_{d}^{2,3}|{\mathcal{I}}_{s}^{2,3})\cdot {\pi}_{\theta}^{2}({u}_{\text{env}}^{2}|{\tau}^{2})\cdot {\pi}_{\theta}^{3}({u}_{\text{env}}^{3}|{\tau}^{3})\right)$ | |||
$+{\pi}_{\text{ps},\theta}^{\mathcal{A}}({u}_{\text{ps}}^{\mathcal{A}}=\{\{2\},\{1,3\}\}|{\mathcal{I}}_{s}^{1,2,3})\cdot {\pi}_{\theta}^{2}({u}_{\text{env}}^{2}|{\tau}^{2})$ | |||
$\mathrm{\hspace{1em}\hspace{1em}}\cdot \left({\pi}_{\text{pc},\theta}^{1,3}({u}_{\text{env}}^{1,3}|{\mathcal{I}}_{s}^{1,3})+{\pi}_{\text{pc},\theta}^{1,3}({u}_{d}^{1,3}|{\mathcal{I}}_{s}^{1,3})\cdot {\pi}_{\theta}^{1}({u}_{\text{env}}^{1}|{\tau}^{1})\cdot {\pi}_{\theta}^{2}({u}_{\text{env}}^{3}|{\tau}^{3})\right)$ | |||
$+{\pi}_{\text{ps},\theta}^{\mathcal{A}}({u}_{\text{ps}}^{\mathcal{A}}=\{\{3\},\{1,2\}\}|{\mathcal{I}}_{s}^{1,2,3})\cdot {\pi}_{\theta}^{3}({u}_{\text{env}}^{3}|{\tau}^{3})$ | |||
$\mathrm{\hspace{1em}\hspace{1em}}\cdot \left({\pi}_{\text{pc},\theta}^{1,2}({u}_{\text{env}}^{1,2}|{\mathcal{I}}_{s}^{1,2})+{\pi}_{\text{pc},\theta}^{1,2}({u}_{d}^{1,2}|{\mathcal{I}}_{s}^{1,2})\cdot {\pi}_{\theta}^{1}({u}_{\text{env}}^{1}|{\tau}^{1})\cdot {\pi}_{\theta}^{2}({u}_{\text{env}}^{2}|{\tau}^{2})\right).$ |
Conditional variables beyond common knowledge ${\mathcal{I}}^{\mathcal{G}}$ and action-observation histories ${\tau}^{a}$ have been omitted for brevity. See Table 1 for a detailed depiction of Pairwise MACKRL’s hierarchical controllers.
Level | Policy / Controller | #$\pi $ |
---|---|---|
1 | ${\pi}_{\text{ps}}({u}^{\text{ps}}|{\mathcal{I}}_{{s}_{t}}^{\mathcal{A}},{u}_{t-1}^{\text{ps}},{h}_{t-1}^{\text{ps}})$ | 1 |
2 | ${\pi}_{\text{pc}}^{a{a}^{\prime}}({u}^{a{a}^{\prime}}|{\mathcal{I}}_{{s}_{t}}^{a{a}^{\prime}},{u}_{t-1}^{a{a}^{\prime}},{h}_{t-1}^{a{a}^{\prime}},a{a}^{\prime})$ | 3 |
3 | ${\pi}^{a}({u}^{a}|{z}_{t}^{a},{h}_{t-1}^{a},{u}_{t-1}^{a},a)$ | 3 |
However the sampling of each agent’s actions ${u}_{\text{env}}^{a}\in {\mathcal{U}}^{a}$ only needs to traverse one branch of the tree, as shown in Figure 6. At the top level, an agent id partition ${u}_{\text{ps}}$ is categorically sampled from the pair selector policy ${\pi}_{\text{ps},\theta}$. At the second level, the pair selector policy for the pair contained in the partition ${\pi}_{\text{pc}}^{a,b}$ is categorically sampled from in order to receive ${u}^{a,b}$ where $a,b\in {u}_{\text{ps}}$. If the delegation action $d$ is sampled, then both ${u}^{a}$ and ${u}^{b}$ are categorically resampled from their respective independent policies ${\pi}^{a}$ and ${\pi}^{b}$. Otherwise, ${u}^{a}$ and ${u}^{b}$ are determined by ${u}^{a,b}$. The leftover agent $c\notin {u}_{\text{ps}}$ samples its action from its corresponding independent policy ${\pi}^{c}$. Note that this sampling scheme naturally generalised for $n>3$.
level 1=[level distance=1cm, sibling distance=1cm] \tikzstylelevel 2=[level distance=1.5cm, sibling distance=1.5cm]
bag = [text width=4em, text centered] \tikzstyleend = [circle, minimum width=3pt,fill, inner sep=0pt]
level 1=[level distance=3.5cm, sibling distance=3.5cm] \tikzstylelevel 2=[level distance=3.5cm, sibling distance=2cm]
bag = [text width=4em, text centered] \tikzstyleend = [circle, minimum width=3pt,fill, inner sep=0pt]
[grow=right, sloped, scale=0.7] \node[bag] Game matrix $A,B$ child node[bag] CK available $\text{Yes},\text{No}$ child node[end, label=right: ${c}_{1},{c}_{2}$; σ_1, σ_2= { B, B with prob. p σ 2 B, ? with prob. ( 1-p σ ) p σ ?, B with prob. p σ ( 1-p σ ) ?,? with prob. ( 1-p σ ) 2 ] edge from parent node[above] No node[below] $1-{p}_{ck}$ child node[end, label=right: ${c}_{1},{c}_{2}=\mathcal{C}\mathcal{K};{\sigma}_{1},{\sigma}_{2}=B$] edge from parent node[above] Yes node[below] ${p}_{ck}$ edge from parent node[above] $B$ node[below] $\frac{1}{2}$ child node[bag] CK available $\text{Yes},\text{No}$ child node[end, label=right: ${c}_{1},{c}_{2}$; σ_1, σ_2= { A, A with prob. p σ 2 A, ? with prob. ( 1-p σ ) p σ ?, A with prob. p σ ( 1-p σ ) ?, ? with prob. ( 1-p σ ) 2 ] edge from parent node[above] No node[below] $1-{p}_{ck}$ child node[end, label=right: ${c}_{1},{c}_{2}=\mathcal{C}\mathcal{K};{\sigma}_{1},{\sigma}_{2}=A$] edge from parent node[above] Yes node[below] ${p}_{ck}$ edge from parent node[above] $A$ node[below] $\frac{1}{2}$ ;
Appendix B Experimental Setup - StarCraft II
All policies are implemented as two-layer recurrent neural networks (GRUs) with $64$ hidden units, while the critic is feed forward and uses full state information. Parameters are shared across controllers within each of the second and third levels of the hierarchy. We also feed into the policy the agent index or index pairs. For exploration, we use a bounded softmax distribution in which the agent samples from a softmax over the policy logits with probability $(1-\u03f5)$ and samples randomly with probability $\u03f5$. We anneal $\u03f5$ from $0.5$ to $0.01$ across the first $50$k environment steps.
Episodes are collected using eight parallel SCII environments. Optimisation is carried out on a single GPU with Adam and a learning rate of $0.0005$ for both the agents and the critic. The policies are fully unrolled and updated in a large mini-batch of $T\times B$ entries, where $T=60$ and $B=8$. By contrast, the critic is optimised in small mini-batches of size $8$, one for each time-step, looping backwards in time. We found that this stabilised and accelerated training compared to full batch updates for the critic. The target network for the critic is updated after every $200$ critic updates. We use $\lambda =0.8$ in TD($\lambda $) to accelerate reward propagation.
Appendix C Pair controller introspection
We now test the hypothesis that MACKRL’s superior performance is indeed due to its ability to learn how to use common knowledge for coordination. To demonstrate that the pair controller can indeed learn to delegate strategically, we plot in Figure 8 the percentage of delegation actions ${u}_{d}$ against the number of enemies in the common knowledge of the selected pair controller, in situations where there is at least some common knowledge.
Since we start with randomly initialised policies, at the beginning of training the pair controller delegates only rarely to the decentralised controllers. As training proceeds, it learns to delegate in most situations where the number of enemies in the common knowledge of the pair is small, the exception being no visible enemies, which happens too rarely ($5\%$ of cases). This shows that MACKRL can learn to delegate in order to take advantage of the private observations of the agents, but also learns to coordinate in the joint action space when there is substantial common knowledge.
Appendix D Common Knowledge with Entities
To exploit a particular form of field-of-view common knowledge with MACKRL, we formalise an instance of a Dec-POMDP, in which such common knowledge naturally arises. In this Dec-POMDP, the state $s$ is composed of a number of entities $e\in \mathcal{E}$, with state features ${s}^{e}$, i.e., $s=\{{s}^{e}|e\in \mathcal{E}\}$. Some entities are agents $a\in \mathcal{A}\subseteq \mathcal{E}$. Other entities could be enemies, obstacles, or goals.
The agents have a particular form of partial observability: the observation ${z}^{a}$ contains the subset of state features ${s}^{e}$ from all the entities $e$ that $a$ can see. Whether $a$ can observe $e$ is determined by the binary mask ${\mu}^{a}({s}^{a},{s}^{e})\in \{\top ,\perp \}$ over the agent’s and entity’s observable features. An agent can always observe itself, i.e., ${\mu}^{a}({s}^{a},{s}^{a})=\top ,\forall a\in \mathcal{A}$. The set of all entities the agent can see is therefore ${\mathcal{M}}^{a}:=\{e|{\mu}^{a}({s}^{a},{s}^{e})\}\subseteq \mathcal{E}$, and the agent’s observation is specified by the deterministic observation function $o(s,a)$ such that ${z}^{a}=o(s,a)=\{{s}^{e}|e\in {\mathcal{M}}^{a}\}\in \mathcal{Z}$. In the example of Figure 1, ${\mathcal{M}}^{A}={\mathcal{M}}^{B}=\{A,B\}$ and ${\mathcal{M}}^{C}=\{A,B,C\}$.
This special Dec-POMDP yields perceptual aliasing in which the state features of each entity are either accurately observed or completely occluded. The Dec-POMDP could be augmented with additional state features that do not correspond to entities, as well as additional possibly noisy observation features, without disrupting the common knowledge we establish about entities. For simplicity, we omit such additions.
A key property of the binary mask ${\mu}^{a}$ is that it depends only on the features ${s}^{a}$ and ${s}^{e}$ to determine whether agent $a$ can see entity $e$. If we assume that an agent $a$’s mask ${\mu}^{a}$ is common knowledge, then this means that another agent $b$, that can see $a$ and $e$, i.e., $a,e\in {\mathcal{M}}^{b}$, can deduce whether $a$ can also see $e$. This assumption can give rise to common knowledge about entities. Figure 1 demonstrates this for 3 agents with commonly known observation radii.
The mutual knowledge ${\mathcal{M}}^{\mathcal{G}}$ of a group of agents $\mathcal{G}\subseteq \mathcal{A}$ in state $s$ is the set of entities that all agents in the group can see in that state: ${\mathcal{M}}^{\mathcal{G}}:={\cap}_{a\in \mathcal{G}}{\mathcal{M}}^{a}$. However, mutual knowledge does not imply common knowledge. Instead, the common knowledge ${\mathcal{I}}^{\mathcal{G}}$ of group $\mathcal{G}$ in state $s\in \mathcal{S}$ is the set of entities such that all agents in $\mathcal{G}$ see ${\mathcal{I}}^{\mathcal{G}}$, know that all other agents in $\mathcal{G}$ see ${\mathcal{I}}^{\mathcal{G}}$, know that they know that all other agents see ${\mathcal{I}}^{\mathcal{G}}$, and so forth (Osborne & Rubinstein, 1994).
To know that another agent $b$ also sees $e\in \mathcal{E}$, agent $a$ must see $b$ and $b$ must see $e$, i.e., ${\mu}^{a}({s}^{a},{s}^{b})\wedge {\mu}^{b}({s}^{b},{s}^{e})$. Common knowledge ${\mathcal{I}}^{\mathcal{G}}$ can then be formalised recursively for every agent $a\in \mathcal{G}$ as:
$${\mathcal{I}}_{0}^{a}:={\mathcal{M}}^{a},{\mathcal{I}}_{m}^{a}:=\bigcap _{b\in \mathcal{G}}\left\{e\in {\mathcal{I}}_{m-1}^{b}|{\mu}^{a}({s}^{a},{s}^{b})\right\},{\mathcal{I}}^{\mathcal{G}}:=\underset{m\to \mathrm{\infty}}{lim}{\mathcal{I}}_{m}^{a}.$$ | (2) |
This definition formalises the above description that common knowledge is the set of entities that a group member sees ($m=0$), that it knows all other group members see as well ($m=1$), and so forth ad infinitum. In the example of Figure 1, ${\mathcal{I}}^{AB}=\{A,B\}$ and ${\mathcal{I}}^{AC}={\mathcal{I}}^{BC}={\mathcal{I}}^{ABC}=\mathrm{\varnothing}$.
The following lemma establishes that, in our setting, if a group of agents can all see each other, their common knowledge is their mutual knowledge.
Lemma 1.
In the setting described in this Section, and when all masks are known to all agents, the common knowledge of a group of agents $\mathrm{G}$ in state $s\mathrm{\in}\mathrm{S}$ is
$${\mathcal{I}}^{\mathcal{G}}=\{\begin{array}{cc}\hfill {\mathcal{M}}^{\mathcal{G}},\hfill & \text{\mathit{i}\mathit{f}}\underset{a,b\in \mathcal{G}}{\bigwedge}{\mu}^{a}({s}^{a},{s}^{b})\hfill \\ \hfill \mathrm{\varnothing},\hfill & \text{\mathit{o}\mathit{t}\u210e\mathit{e}\mathit{r}\mathit{w}\mathit{i}\mathit{s}\mathit{e}}\hfill \end{array}.$$ | (3) |
Proof.
The lemma follows by induction on $m$. The recursive definition of common knowledge (2) holds trivially if ${\mathcal{I}}^{\mathcal{G}}=\mathrm{\varnothing}$. Starting from the knowledge of any agent $a$ in state $s$, ${\mathcal{I}}_{0}^{a}={\mathcal{M}}^{a}$, definition (2) yields:
$${\mathcal{I}}_{1}^{a}=\{\begin{array}{cc}\hfill {\mathcal{M}}^{\mathcal{G}},\hfill & \text{if}\underset{b\in \mathcal{G}}{\bigwedge}{\mu}^{a}({s}^{a},{s}^{b})\hfill \\ \hfill \mathrm{\varnothing},\hfill & \text{otherwise}\hfill \end{array}.$$ |
Next we show inductively that if all agents in group $\mathcal{G}$ know the mutual knowledge ${\mathcal{M}}^{\mathcal{G}}$ of state $s$ at some iteration $m$, that is, ${\mathcal{I}}_{m}^{c}\stackrel{\text{ind.}}{=}{\mathcal{M}}^{\mathcal{G}}$, then this mutual knowledge becomes common knowledge two iterations later. Applying the definition (2) for any agent $a\in \mathcal{G}$ twice yields:
${\mathcal{I}}_{m+2}^{a}$ | $=$ | $\bigcap _{b\in \mathcal{G}}}{\displaystyle \bigcap _{c\in \mathcal{G}}}\left\{e\in {\mathcal{I}}_{m}^{c}|{\mu}^{a}({s}^{a},{s}^{b})\wedge {\mu}^{b}({s}^{b},{s}^{c})\right\}=\left\{e\in \mathcal{E}\right|{\bigwedge}_{b\in \mathcal{G}}\left({\mu}^{a}({s}^{a},{s}^{b})\wedge {\bigwedge}_{c\in \mathcal{G}}\left({\mu}^{b}({s}^{b},{s}^{c})\wedge e\in {\mathcal{I}}_{m}^{c}\right)\right)\$ | ||
$\stackrel{\text{ind.}}{=}$ | $\left\{e\in {\mathcal{M}}^{\mathcal{G}}\right|{\bigwedge}_{b,c\in \mathcal{G}}{\mu}^{b}({s}^{b},{s}^{c})\},$ |
which is the right side of (3), and where we used
$${\bigwedge}_{b\in \mathcal{G}}\left({\mu}^{a}({s}^{a},{s}^{b})\wedge {\bigwedge}_{c\in \mathcal{G}}{\mu}^{b}({s}^{b},{s}^{c})\right)={\bigwedge}_{b,c\in \mathcal{G}}{\mu}^{b}({s}^{b},{s}^{c}),\forall a\in \mathcal{G}.$$ |
Finally, applying (2) one more time to this result, yields:
${\mathcal{I}}_{m+3}^{a}$ | $=$ | $\bigcap _{b\in \mathcal{G}}}\left\{e\in {\mathcal{I}}_{m+2}^{b}|{\mu}^{a}({s}^{a},{s}^{b})\right\}\mathit{\hspace{1em}}=\mathit{\hspace{1em}}{\mathcal{I}}_{m+2}^{a}.$ |
For all $m\ge 3$, ${\mathcal{I}}_{m}^{a}$ remains thus the right hand side of (3). As ${\mathcal{I}}^{\mathcal{G}}={lim}_{m\to \mathrm{\infty}}{\mathcal{I}}_{m}^{a}$, we can thus conclude that, starting at the knowledge of any agent of group $\mathcal{G}$, in which all agents can see each other, the mutual knowledge is the common knowledge. ∎
The common knowledge can be computed using only the visible set ${\mathcal{M}}^{a}$ of every agent $a\in \mathcal{G}$. Moreover, actions that have been chosen by a policy, which itself is common knowledge, and that further depends only on common knowledge and a shared random seed, are also common knowledge. The common knowledge of group $\mathcal{G}$ up to time $t$ is thus some common prior knowledge $\xi $ and the commonly known trajectory ${\tau}_{t}^{\mathcal{G}}=(\xi ,{z}_{1}^{\mathcal{G}},{\mathbf{u}}_{1}^{\mathcal{G}},\mathrm{\dots},{z}_{t}^{\mathcal{G}},{\mathbf{u}}_{t}^{\mathcal{G}})$, with ${z}_{k}^{\mathcal{G}}=\{{s}_{k}^{e}|e\in {\mathcal{I}}^{\mathcal{G}}\}$. Knowing all binary masks ${\mu}^{a}$ makes it possible to derive ${\tau}_{t}^{\mathcal{G}}={\mathcal{I}}^{\mathcal{G}}({\tau}_{t}^{a},\xi )$ from the observation trajectory ${\tau}_{t}^{a}=({z}_{1}^{a},\mathrm{\dots},{z}_{t}^{a})$ of any agent $a\in \mathcal{G}$ and the shared prior knowledge $\xi $. A function that conditions on ${\tau}^{\mathcal{G}}$ can therefore be computed independently by every member of $\mathcal{G}$.
Note that (by definition) common knowledge can only arise from entities that are observed identically by all agents. If only one agent receives non-deterministic observations, for example induced by sensor noise, the other agents cannot deduce the group’s mutual (and thus common) knowledge. Our method therefore only guarantees perfect decentralisation of the learned policy in settings with deterministic observations, like simulations and computer games. However, in Section 4.1 we show empirically that, using a naive correlated sampling protocol similar to the theoretically optimal Holenstein protocol (Holenstein, 2007; Bavarian et al., 2016), MACKRL can still succeed in the presence of moderate sensor noise.