Learning good policies for multi-agent systems is a complex task. Existing methods are often limited to a small number of agents, as learning becomes intractable when the agent number increases considerably. In this paper we describe Spatial Action Decomposition Learning that tries to overcome inefficiencies of standard multi-agent Q-learning methods by exploiting existing spatial action correlations. We apply our method to real-time strategy (RTS) game combat scenarios and show that Spatial Action Decomposition Learning based systems can outperform handcrafted scripts and policies optimized by independent Q-learning.
As multi-agent decision problems are ubiquitous,
building better AI agents that work together has numerous
real-world applications, such as city transport
optimization, stock trading, advertisement bidding, multi-player
online gaming, and coordinating robot swarms. Multi-agent
reinforcement learning (MARL)
A challenging aspect of decentralization is to find an effective representation of the centralized action-value function Qtot that integrates the effects of all agents’ actions. But such functions are difficult to learn in the presence of many agents and extracting the decentralised individual agent policy (one agent chooses one action based on individual/partial observation) is not straightforward.
In the next section we discuss in more detail related work that tackles multi-agent Q-learning in various ways – ranging from centralized learning, over simple Q-function decompositions, to learning expressive networks for mixing individual Q-functions. We then describe our novel learning approach which is based on the observation that agent actions are often spatially correlated, e.g., nearby agents frequently execute similar actions, such as moving in the same direction, or collaborating to achieve a local goal such as defending a choke point. We then present experimental results for our spatial action decomposition method — applying it to the popular multi-agent learning domain of 2-team combat in real-time strategy (RTS) games with up to 80 vs. 80 units. Finally, we conclude the paper with summarizing our findings and discussing future work.
Arguably the easiest and most commonly used learning
method for multiple agents is Independent Q-Learning
(IQL)
While there are ways of improving IQL’s stability
Alternatively, the joint action Q-function Qtot can be
learned directly. This avoids the non-stationarity
problem and can lead to better coordination and results, at the
cost of poor scaling performance. For example,
experiments in
Using a team reward signal makes credit assignment
challenging, even for simple problems. For example, in a
2player soccer game with the number of scored goals being
the team reward, the agent who is worse at scoring
sometimes ends up failing to learn to shoot at all, as its exploration
would impede its teammate
Coordination graphs have been used to decompose the
global reward into a sum of local agent rewards
A more elegant way of solving the credit assignment
problem is to use a value decomposition network (VDN) to
represent Qtot as sum of individual Q-functions Qi which depend
only on agent-local observations
One disadvantage is that the VDN representation of Qtot
is limited by the addition, because agents interactions are
usually more complex. QMIX addresses this issue by
replacing the sum operation with a mixing network that
combines all individual Qi into Qtot in a complex, monotone,
and non-linear fashion informed by the global state
information during training
While more natural, these methods still suffer when
handling larger numbers of agents as Q-learning becomes
infeasible due to noise accumulation caused by many exploratory
actions
In this work we focus on the MARL challenge of increasing the number of agents and the resulting combinatorial explosion of the joint action sets and interactions with other agents present in the environment, friend or foe. As previously mentioned, IQL is a quick and simple solution, but does not guarantee convergence and is poorly suited for modelling all interactions between agents. On the other hand, fully combinatorial approaches are better at handling coordination but don’t scale well with the number of agents.
One approach that showed good results is to estimate the
join action-value of a team of agents as a linear
We build on the value decomposition idea, but as we focus
on the number of agents as the main challenge, we choose
to work in a fully observable environment. As such we
don’t have to condition on agent-local observations. We
decompose Qtot into individual values similarly to VDN and
QMIX, but use the full, global state both during training and
evaluation. To handle the large number of agents and the
difficulty introduced by their exploratory actions, we use a
grid based spatial decomposition. We add a sector
abstraction, making the assumption that the joint action value can
be decomposed into value functions across sectors – disjoint
areas of the map – instead of individual agents. We use a
simple sum and leave more complex decompositions such as
QMIX to future work, as experiments in
After the sector actions are chosen by the network, each sector is responsible for emitting low-level actions for each agent present within, through a separate mechanism. The sector action can be as simple as selecting which action script to use to generate actions for the agents within that particular sector. Besides simple but resource inexpensive methods, other algorithms that don’t scale as well could be used due to the smaller problem size, for example search algorithms if there is a forward model.
Each sector’s Q-function QSi will be learned implicitly by the network and will not benefit from any reward specifically given to sector Si or to any individual agent. Strictly speaking QSi is more an utility function than a value function because it does not estimate an expected return by itself. For simplicity, however, we will continue to call both Qtot and QSi value functions.
Each sector chooses its action greedily with respect to its own QSi , and the joint action Qtot is chosen by maximizing Pi QSi . The maximization of Qtot can now be performed in time linear in the number of sectors, which will usually be much smaller than the number of agents. For this method to work well, the sectors dimension should be large enough such that at least a few agents are present in most sectors.
To reduce the number of learnable parameters it is common to use a neural network for each agent and to share its weights between the agents. This approach can be taken with sectors as well, but since we have access to the global state it is more natural to use convolutions to keep the number of parameters low.
A deep ConvNet computes higher and higher level features layer by layer, with the same or possibly different spatial resolutions. It’s a very good tool for a sector-based approach: it starts with higher resolution maps with low-level features and produces lower and lower resolution maps but with increasingly relevant features until reaching the target sector granularity.
An example network used for a grid-like 2-player combat scenario is shown in Figure 1. There are 5 input feature planes for a 64 64 grid map. Three of them are Boolean values indicating unaccessible terrain (e.g. walls), own and enemy unit presence on each square. Two planes represent the hit-points of the two armies, each cell containing at most one agent. More details about the environment used for experiments can be found in the next section.
Four convolutional layers with 4 4 stride-2 filters, each followed by a ReLU nonlinearity and using batch normalisation, are used to extract features and gradually halve the map resolution, obtaining activations C1 3 and S1. For simplicity, at a given resolution level we considered only square sector configurations of the type W W , resulting in W 2 total sectors. Using a granularity of 2 2 sectors – each 32 32 cells – was not enough to execute complex maneuvers. Consequently, we start with the 4 4 sector representation of S1, each sector being responsible for agents within 16 16 cells on the original map.
In certain situations it might be beneficial to have even
more precise control. For this purpose we can apply the
standard process of deconvolution, also known as transposed or
fractionally-strided convolution
Either S1 or S2 can be used to obtain QSi values,
depending on the desired sector granularity. The Q
functions are represented using value and advantage functions
Q(s; a) = V (s) + A(s; a) as recommended by the dueling
architecture
The same output head filters can be applied to any resolution Si layer to obtain Q-values for a desired sector granularity. Actions can be emitted based on the values from any of these layers, either by choosing a specific resolution beforehand, by taking the max across all resolutions, or even by adding a separate network component responsible for learning which sector granularity to pick given the current state.
Increasing the number of sectors provides more accurate control over the agents, but also increases the difficulty of the credit assignment and slows the learning process. Using fewer sectors and the resulting ability to specify large scale actions should make the exploration for actions leading to large rewards more efficient, and unnecessary micromanagement could be avoided for map areas that are largely empty or that do not require complex behaviors.
In this work we focus on spatial decomposition, and opt for the simple fully convolutional design described above. Although more sophisticated network blocks could be designed, and even though temporal abstractions are compatible with our method, they are not the focus of this paper. Stacking multiple input frames along the depth dimension, using gated architectures such as LSTM and GRU, or learning agent policies that implement the provided sector actions are left for future work.
In this section we describe the combat scenario problem to which we apply Spatial Action Decomposition Learning. We provide details of the state features and training methodology and evaluate our method’s performance in comparison to independent Q-learning.
Real-time strategy (RTS) games are now a well established benchmark for the RL community. They offer more difficult multi-agent challenges compared to previous environments such as Atari games. In particular, RTS game combat scenarios are a popular evaluation method for MARL algorithms, offering mixed cooperative and competitive multiagent environments. Combat scenarios have been traditionally used to test algorithms’ ability to scale, from simple search based methods (Churchill, Saffidine, and Buro 2012;
C1 32x32x32
C2
16x16x32
Ontan˜o´n 2017) to script and portfolio blended variants
The StarCraft II Learning Environment (SC2LE)
In this work we focus on a centralised micro-management scenario in which two groups of identical units fight on a grid-world map. The units of the first army are controlled by the learning method. The opposing units are controlled by a scripted algorithm that moves towards and focuses fire on its closest enemies. The initial placement of the units for each army is randomized at the start of each game: around two thirds are split randomly among a random number of 2 to 5 orderly groups, while the remaining units are randomly scattered on the map. An example scenario is shown in Figure 2. This setup is designed to mimic combat scenarios commonly occurring in popular RTS games such as StarCraft II. The small attack range compared to the size of the map and the number of units and clusters promote smart group maneuvering which is notoriously hard for agent-centric learning.
We adopt MAgent’s default combat settings: at each time step agents can either move to or attack any cell within a radius of two. When attacking a unit, the attacker’s attack value is subtracted from the attacked unit’s hit-point value. Units with hit-point value 0 are removed. The goal is to accumulate rewards by eliminating all opponents. The rewards are also closely following the default settings: 5 for killing an enemy unit, 0:1 for attacking an empty grid cell, 0:2 for attacking an enemy unit, and 1 for being killed (increased from the 0:1 default value). Additionally, there is a reward of 100 for killing all enemies. Each game is restricted to have a length of at most 300 time steps.
We use the full observability settings: there is no unit vision limitation or fog of war.
Necessarily, sector actions should translate into low-level actions for the agents located within. Here we choose to use 5 scripted algorithms to do so: four that move units in each of the cardinal directions and one for approaching and attacking enemy units, the same attacking script used by the enemy. In future work these scripts can be replaced with other fixed or even learnable agent policies, and the sector action can simply be which of these policies the agents within should use, similar to a meta-learning approach (Frans et al. 2017). To avoid switching behaviors too often and to make exploration easier via temporal abstraction, the sector action is only changed every k environment time steps. A value of k = 5 was chosen based on a brief tuning process. As a note, keeping the sector action fixed for a number of steps is recommended in conjunction with moderately intelligent scripts or policies. Otherwise, extremely basic scripts might move left for 1 step and then keep colliding into another unit or a wall for the remaining n 1 steps.
The network input is the global state, a 64 64 grid with 5 feature planes: obstacles, own and enemy units and own and enemy hit-points. All features are normalised by their maximum possible values.
The network used for the sector abstraction is shown in Figure 1, with actions being emitted on a 4 4 sector granularity, unless otherwise specified. For IQL, the input is a 13 13 observation centered around the agent’s position, with 7 feature planes. In addition to the 5 already mentioned, there are two more layers containing minimap information for both armies. For these layers, the original map unit information is scaled down to 13 13, and normalised such that each cell value is equal to the number of units within divided by total number of alive units. A value of 1 is added to the cell containing the acting agent, in the allied minimap. These minimap layers were included to provide the agents information about the global state.
The IQL network consists of one 4 4 stride-2 convolutional layer followed by two 3 3 stride-1 convolutional layers, all three with 32 filters and followed by ReLU activations and batch normalisation. A linear layer of 256 units follows, and two output heads for the value and advantage functions which are summed to extract the final Q-values.
The learning algorithm is based on DQN
All networks are trained using the Adam learning
algorithm
We train all models with 700k games against the handcrafted script mentioned in the previous section. After every 1000 training games 100 test games are played independently with actions chosen greedily in evaluation mode – i.e., " for exploration is set to 0. In what follows the proportion of these games in which all enemy units are defeated within the target time limit is called test win rate.
Figures 3 and 4 show the test win rate for three single runs of IQL and Spatial Action Decomposition Learning, on 64 64 grid scenarios with 20, 40, and 80 units for each side. For the chosen parameter settings IQL fails to learn how to defeat the script consistently — not even achieving a 50% win rate. The training also appears to be unstable at times. As described in the introduction, this may be caused by all agents exploring simultaneously. We speculate that using VDNs could mitigate this problem, and isolating the effect of the sector abstraction, comparison to an IQL+VDN baseline is on our todo-list.
Our method shows a more stable learning behavior and can consistently defeat the opponent in more than 80% of the games after training. Controlling 80 units well seems significantly more difficult than 20 or 40, as shown by the slower learning process. We think this is because there are more units placed randomly behind the enemy lines. Grouping allied units while dealing with the enemy’s requires more complex maneuvering, and often makes consolidation of one’s army more difficult.
From a qualitative point of view, our method displays forms of coordination such as surrounding or attacking the enemy on a wider front and fleeing from a stronger group of enemies until regrouping with the rest of the army. Snapshots from a sample game are shown in Figure 7. We observed our system often using a small number of units as bait to split the enemy forces and fighting them one-by-one.
Learning with a model that uses 8 8 sectors is more challenging. Firstly, it gets stuck more often in local optima of predominantly choosing to attack and avoiding move actions. This is likely due to the more difficult exploration induced by the 64 sectors. Using mostly attack actions leads to test win rates around 50%, as expected. After the convolutional layers and S1 were initialised with weights from a trained 4 4 sectors model, learning proceeded smoothly and 75% win rates were reached, as seen in Figure 5. Building on representations and features learned by the 4 4 model helps exploration in the more difficult 8 8 scenario. Assigning credit for four times as many sectors is more difficult and as expected, learning converges more slowly with the maximum win rate being 10% lower.
Finally, Figure 6 shows the win rate of the 6 trained models from Figures 3 and 4 on scenarios with a range of different starting army sizes, instead of the only one used throughout the training. Models trained with fewer units do not generalize well, and both models that learned using a maximum of 20 units fail to win a single match when controlling more than 100 units. Sector models trained with more units do not perform too well in smaller battles either, mostly because although the network eventually sees states with few units, they are very differently positioned from the starting states of small scenarios. Better performance could be obtained by designing a mixed curriculum of battles. IQL has worse performance, but using larger armies results in stronger policies even on the smaller scenarios. That might be because with IQL, more agents translate into more experience samples.
In this paper we study cooperative-competitive multi-agent RL with agents learning from a single team reward signal. Both individual as well as centralized learners fail to scale successfully with growing team sizes, and decomposing the joint action-value function into per-agent action-value functions has previously shown great promise. Here we present a method that exploits existing spatial action correlations to decompose the joint action-value function on a per-sector basis instead, and show its effectiveness in both small and large scale scenarios. Results for combat scenarios with 20 to 80 units per side show improved performance over simple scripting and independent Q-learning.
Without a doubt the presented method can be improved
in various ways. For instance, QMIX can be used to
facilitate non-linear Q-value mixing, and low-level sector policies
could be learned rather than using fixed scripts. Also,
skipconnections can be used to enrich high-level features with
low-level map details – providing high-fidelity context to
lower-level action generation. Another interesting research
avenue is a deeper integration of hierarchical action-value
functions operating at different temporal scales
A guide to conarXiv preprint