Recent work in (deep) reinforcement learning has increasingly looked to develop better agents for multi-agent/multitask scenarios as many successes have already been seen in the usual single-task single-agent setting. In this paper, we propose a solution for a recently released benchmark which tests agents in such scenarios, namely the MARLÖ competition. Following the 2018 Jeju Deep Learning Camp, we consider a combined approach based on various ideas generated during the camp as well as suggestions for building agents from recent research trends, similar to the methodology taken in developing Rainbow (Hessel et al. 2017). These choices include the following: using model-based agents which allows for planning/simulation and reduces computation costs when learning controllers, applying distributional reinforcement learning to reduce losses incurred from using mean estimators, considering curriculum learning for task selection when tasks differ in difficulty, and graph neural networks as an approach to communicate between agents. In this paper, we motivate each of these approaches and discuss a combined approach that we believe will fare well in the competition.
Reinforcement Learning (RL) is a subfield of machine learning that studies how agents can learn to maximize total reward while acting in environments that provide minimal supervision through reward signals (Sutton, Barto, and others 1998). Generally, the formulation of RL assumes that the environment is modeled as a Markov Decision Process (MDP), given by the 5-tuple hS; A; R; T; i where S denotes the state space, A the action space, R the reward function, T the transition function, and the discount factor which controls how much agents favor short-term vs. long term rewards. The objective is usually to maximize the expected 1 return E[G] = P t 1rt, where rt is the reward obtained t=1 at time t.
Often the MDP and the state space in particular is very large
or complex, and, thus, using traditional table-lookup
methods that store information per state can be very expensive
or lead to poor generalization performance. This problem
is generally tackled with function approximation where the
states are first mapped onto a lower dimensional space and
RL algorithms then work with the extracted features.
Deep Learning is a method to learn general functions using
artificial neural networks and hence is a way towards
nonlinear function approximation
In this section, we outline some necessary background information that will be useful in explaining our proposed method and the motivation for various decisions. We first discuss a particular model-based algorithm that we base our agents on. Then, we consider the general RL landscape, and the recent interest in distributional RL. After that discussion, we talk about some important things to note about the MARLÖ competition in particular. Finally, we discuss NerveNet and Graph Neural Networks which provide for an approach to think about when considering multi-agent communication. When designing reinforcement learning algorithms, there is a choice between model-free algorithms and model-based algorithms. Model-free approaches only focus on the problem of how to act so as to maximize reward. On the other hand, model based approaches also try to understand how the “world” works by learning the underlying MDP of the environment. A recent such approach that has shown promise and which we propose to use is World Models.
World Models
While V and M can simply be trained through supervised
learning, C can be trained in various ways. However, since
the controller portion of the setup is very small (on the order
of a few hundred parameters in the experiments used by the
authors), training using an evolutionary technique, CMA-ES
(Covariance Matrix Adaptation Evolution Strategy
When designing RL agents, another common choice to be
made is whether the agents should directly learn in
policy space (how to act in different states) or learn value
functions that define the “goodness” of states or
stateaction pairs in terms of expected return. In the
valuebased paradigm, Q-Learning
Recently, there have been questions about the general
approach taken in RL. Namely, the observation is that most
prior RL algorithms estimate the average expected return
and use these estimates when choosing actions.
Distributional RL
One major aspect of the competition is that multiple agents will be involved. With teams, cooperative tasks and competitive tasks become important subsets of tasks to consider. With regard to terminology in fact, the competition specification makes an important distinction between tasks and games by defining a game as a collection of tasks of varying difficulty and level layouts. The competition is structured such that we have access to some publicly available tasks for every game, but some tasks are private and to be used later for evaluation.
NerveNet
The updates of GNNs begin with propagation of messages to neighboring nodes. The feature vector of the current state for each node u at propagation step 0 is denoted h0u. After each node passes messages to neighboring nodes, it aggregates messages it receives from its neighborhood, then updates its feature vector and outputs a vector combining the information from the current and the aggregated messages. A policy network parameterized by the graph can learn what actions to take for each part. This process can be described using the equations below: m(u;v) = MPv (htu) where v 2 Nout(u)
t Atv = MAv (fm(u;v)ju 2 Nin(v)g)
t ht+1 = U v(htv; Atv) v
T y^ = O(fhv j v 2 Gg) (1) (2) (3) (4) where Nin( ) and Nout( ) represent the in- and outneighborhoods respectively, y^ represents the output of the GNN and MPv , MA, U v and Ov may be neural networks and parameter sharing can be applied as necessary. For example, a node u can use the same network MP for message passing to all nodes on its out-neighborhood v 2 Nout(u) or use separate ones for messages to each of these nodes MPv and hence the additional superscript v.
We now consider a few different agents as a combination of some of the ideas explained previously. The motivation for these agents and design choices therein will be described in the following section.
The simplest agent we propose is a multi-agent variation of World Models. Firstly, we note that we assume V and M are shared. Alternatively, they can be trained separately for each agent. Regardless, in the explanations that follow, we will only discuss training the controllers. Owing to the small number of parameters in the controllers of world models, we can view them as being “policy embeddings” which dictate how each agent acts in the environment. Assuming that each agent’s controller is trained separately, let the parameters of the controllers learned be denoted by Ci for agent i where Ci corresponds to the controller parameters [Wc; bc] for agent i’s controller Ci. If each agent were to act independently, then it would just forward the latent vector embedding of its current state and hidden state of the LSTM from the MDN-RNN, say [zti; hit], through its controller Ci to get the action it should take. However, in a multi-agent setting, we are often interested in maximizing total reward for a team of agents (particularly so in co-operative settings.) So, we define a meta-controller as a controller which takes in [zt1; ht1; :::; ztn; htn] and outputs [ a10 ; :::; a1m ; :::; an0 ; :::; anm ] assuming n agents are “under” the teams control, there are m actions and where aij is the probability of agent i taking action aj .
The next agent we consider is one where the controllers are trained separately, but a Graph Neural Network style approach is used, reducing the number of parameters and encouraging communication of shared knowledge. To do this, we first concatenate the hidden state vectors hit for each agent i, say H = [ht1; :::; htn]. We then use this matrix to construct a graph Gt. At the next timestep, we can do the same to get a graph Gt+1. Now, the graph is to represent the beliefs of how the world works and how the agents relate to each other (which it can do so given the information from the memory module from each agent). So, we can expect that if graphs are learned appropriately, we can infer the graph at time t + 1, given the graph and the actions taken by each agent [at1; :::; atn] at time t. Thus, we can use supervised learning to train the graph construction. The actual construction process can be done in many ways, but we propose using cosine-distance row- and column-wise to get how entities in the environment and agents relate to each other. With these graphs serving as a proxy for useful information about the environment and agents, these graphs can serve as useful input to each agent’s controller.
Past work has looked at action-conditional next state
prediction, but has often made the implicit assumption that the
environment is deterministic. Since many environments are
stochastic and world models itself consists of a parameter
which controls the environments stochasticity, we can look
to previous work in distributional RL to consider a better
approach to generating and using next state predictions.
Notably, when there are many possible next states, we can
integrate over them by the probability to get an “averaged” next
state vector. The probability distribution over next states,
P (zt+1jat; zt; ht), is modeled by M in the world models
approach. So, instead of sampling from the mixture density
model and using a single sample, we can easily sample
repeatedly or even in some uniform interval of to get
multiple possible next states with various probabilities of
occurring. Averaging them could give us a more useful z and this
is an approach we wish to study. Using all of the sampled
z’s separately, as in
Lastly, in a multi-task setting, there may be tasks of varying types and difficulties. Curriculum learning is a common approach as the agent can slowly learn tasks of increasing difficulty without which some tasks may be very hard to solve. We propose having a teacher suggesting tasks using a bandit algorithm, EXP3 (Exponential-weight algorithm for Exploration and Exploitation) that keeps track of how each arm (or task in this case) fares. The general pattern we wish to see here is that as agents show signs of improving in one task (say, in an average reward sense), we select that task more until it is essentially solved and then we move on to another task that is next up in the hierarchy of tasks based on difficulty. Since MARLÖ has the concept of games and tasks, we can use a hierarchical approach whereby we first choose the game and then the task to train on. Alternatively, the teacher can select from all the available tasks directly.
In this section, we explain the reasoning behind some of our design decisions and choices.
While model-free approaches such as Deep Q-Networks
World models in particular is appealing for a few concrete reasons. Firstly, Minecraft is partially-observable, the hidden state of the LSTM h in the MDN-RNN module could be very useful in making the POMDP more like an MDP. The hidden state encodes information about past observations and actions taken. Hence, h combined with the current state encoding z represents a new state that encodes the history as well.
Secondly, as the tasks in the MARLÖ competition involve multi-agent multi-task scenarios, we need to think about how to train the agents. With world models, we can share the V , the state feature-extraction module, across the agents and games. The memory module M can also be shared with some consideration for how to train it given that agents may have differing roles. The main point however is that world models is structured in such a way that we can share many modules between agents, reducing computational costs and introducing some useful priors. While such sharing of state representations might be possible in model-free algorithms, the learned representations can be quite different given how the architectures are trained (supervised learning vs. RL and hence with different loss functions.) As a related note, even the structure of the controller, C, is amenable to the multi-agent setting. Since most of the complexity in terms of number of parameters is in the V and M models, C is very small. With multiple agents, we can train a meta-controller with a lot fewer parameters than if we were using separate model-free architectures for each. Finally, we discuss some motivations behind taking a certain approach to training the controller, C, using RL. Naively using CMA-ES in a multi-task cooperative task setting with each controller being trained separately would lead to an exponential blow-up whereby we need to perform a combinatorial search to find good parameters for each agent in order to maximize “global” reward. Also, notably, while evolutionary algorithms and the controller architecture is suited to policy search, complex tasks often require long term planning and hence value functions are useful. This is the same dichotomy seen in continuous control tasks where policy based methods generally perform much better while in games with some amount of planning necessary, like Atari 2600 games or Go, value based methods have generally done much better. Hence, we believe we should use parameter sharing or metacontrollers (to deal with the exponential blow-up) and Actor-Critic methods given how Minecraft combines the need for impulsive quick-actions and long term planning.
Recently, we have also seen that deep RL seems to benefit
from learning distributions even when acting in an expected
sense. While it is still unclear why, one reasonable
argument for this is that there seems to be some bias induced
in the deep RL setting when collapsing distributions to their
means. And, indeed, recent work has shown that
distributional RL doesn’t seem to be of much help in the linear
function approximation case
There have been multiple approaches recently in the area
of multi-task multi-agent scenarios and, particularly in the
Minecraft platform, Malmö, such as
The multi-agent problem of learning from a single scalar
reward signal has generally been quite difficult to approach
but has recently been looked at. Value Decomposition
Networks
We believe this study is particularly useful and wellmotivated because most of the challenges faced by agents evaluated in a multi-task/multi-agent settings are with understanding of the interactions between agents and their respective policies. Our approach attempts to alleviate these difficulties with a Graph Neural Network and Policy Embedding approach. We further can address issues of uncertainty and model interpretability using distributional RL. Finally, we utilize curriculum learning to address agents’ need to balance performance on multiple tasks of varying difficulties, intelligently deciding which tasks to train on and alleviating issues with catastrophic forgetting .
The immediate next steps are to continue implementations of the above ideas into an agent and evaluate its performance in the MARLÖ competition compared to other common benchmark agents. We also wish to look into how to construct simulated environments with various types of opponents and do ablation tests to see which of the ideas detailed above lead to the most improvement. We will keep up-to-date our progress and thoughts here at this webpage: https://sites.google.com/view/rainbowmarlo/.
Mitchell, T. M. 1980. The need for biases in learning generalizations. Department of Computer Science, Laboratory for Computer Science Research, Rutgers Univ. New Jersey. Networks For Cooperative Multi-Agent Learning. ArXiv eprints.