We introduce an approach for augmenting model-free deep reinforcement learning agents with a mechanism for relational reasoning over structured representations, which improves performance, learning efficiency, generalization, and interpretability. Our architecture encodes an image as a set of vectors, and applies an iterative message-passing procedure to discover and reason about relevant entities and relations in a scene. In six of seven StarCraft II Learning Environment mini-games, our agent achieved state-of-the-art performance, and surpassed human grandmaster-level on four. In a novel navigation and planning task, our agent's performance and learning efficiency far exceeded non-relational baselines, it was able to generalize to more complex scenes than it had experienced during training. Moreover, when we examined its learned internal representations, they reflected important structure about the problem and the agent's intentions. The main contribution of this work is to introduce techniques for representing and reasoning about states in model-free deep reinforcement learning agents via relational inductive biases. Our experiments show this approach can offer advantages in efficiency, generalization, and interpretability, and can scale up to meet some of the most challenging test environments in modern artificial intelligence. Recent deep reinforcement learning (RL) systems have achieved remarkable performance in very challenging problem domains (Mnih et al., 2015; BID22 , in large part because of their flexibility in how they learn and exploit the statistical structure underlying observations and reward signals. But the downsides to such flexibility often include low sample efficiency and poor transfer beyond the specifics of the training environment BID32 Lake et al., 2017; Kansky et al., 2017) . Various structured approaches to RL (e.g. BID9 ; BID8 ; BID7 ; BID12 ) have attempted to overcome these limitations by explicitly incorporating entity-based and symbolic representations, and specialized building blocks for solving the task at hand. Although these approaches are often highly efficient, they constrain the representations and admissible learning algorithms, they struggle to learn rich representations, and they are therefore confined to relatively simple tasks and data conditions.To strike favorable tradeoffs between flexibility and efficiency, a number of recent approaches have explored using relational inductive biases in deep learning, to reap the benefits of flexible statistical learning and more structured approaches. Methods such as "graph networks" BID20 Li et al., 2015; explicitly represent entities and their relations using using sets and graphs, and perform relational reasoning using learned message-passing BID13 and attention BID23 Hoshen, 2017; BID24 BID28 schemes. Because they are implemented using deep neural networks, they can learn transformations from input observations into task-relevant entities, as well as functions for computing rich interaction among these entities. This provides a powerful capacity for combinatorial generalization, where their learned building blocks can be composed to represent and reason about novel scenarios BID2 BID19 BID5 BID27 BID21 Kipf et al., 2018; .Drawing on several lines of work, we introduce an approach for incorporating relational inductive biases for entity-and relation-centric state representations, and iterated relational reasoning, into a deep RL agent. In contrast with prior work exploring relational inductive biases in deep RL (e.g., BID27 , our approach does not rely on a priori knowledge of the structure of the problem and is agnostic to the particular relations that need to be considered. To handle raw visual input data, our architecture used a convolutional front-end to compute embeddings of sets of entities, similar to previous work in visual question answering, physical prediction, and video understanding BID19 BID29 BID28 . To perform relational reasoning, we used a self-attention mechanism BID23 Hoshen, 2017; BID24 applied iteratively within each timestep, which can be viewed as learned message-passing (Li et al., 2015; BID13 . Our deep RL agent is based on an off-policy advantage actor-critic (A2C) method which is very effective across a range of standard RL environments BID10 .Our results show that this relational deep RL agent scale to very challenging tasks, achieving state-ofthe-art performance on six out of seven StarCraft II mini-games , surpassing grandmaster level on four mini-games. Additionally, we introduce a novel navigation and planning task, called "Box-World", which stresses the planning and reasoning components of the policy, factoring out other challenges like complex vision or large action spaces. Our agent reaches higher ceiling performance, more efficiently, than non-relational baseline, and is able to generalize to solve problems with more complex solutions than it had been trained on within this task. We also found that the intermediate representations involved in the relational computations were interpretable, and suggest that the agent has rich understanding of the underlying structure of the problem. By introducing structured perception and relational reasoning into deep RL architectures, our agents can learn interpretable representations, and exceed baseline agents in terms of sample complexity, ability to generalize, and overall performance. Behavioral analyses showed that the learned representations allowed for better generalization, which is characteristic of relational representations. Analysis of attention weights showed that the model's internal computations were interpretable, and congruent with the computations we would expect from a model computing task-relevant relations.One important future direction is to explore ways to scale our approach to larger inputs spaces, without suffering, as this and other approaches do (e.g., BID28 BID19 , from the quadratic complexity that results from considering all input pairs. Possible avenues involve using a distinct attentional mechanisms that scales linearly with the number of inputs (Hoshen, 2017) or filtering out unimportant relations BID3 . Other future directions include exploring perceiving complex scenes via more structured formats, such as scene graphs BID31 BID4 , which could be powerful additions to our approach's input module. More complex relational modules could be explored, such as richer graph network implementations , learned approaches for inducing compositional programs BID17 Parisotto et al., 2017; BID0 BID6 ) and reasoning about structured data (Neelakantan et al., 2015; Liang et al., 2016) , or even explicit logical reasoning over structured internal representations BID11 , drawing inspiration from more symbolic approaches in classic AI. Our approach may also interface well with approaches for hierarchical RL , planning BID14 , and structured behavior representation (Huang et al., 2018) , so that the structured internal representations and patterns of reasoning can translate into more structured behaviors.More speculatively, this work blurs the line between model-free agents, and those with a capacity for more abstract planning. An important feature of model-based approaches is making general knowledge of the environment available for decision-making. Here our inductive biases for entityand relation-centric representations and iterated reasoning reflect key knowledge about the structure of the world. While not a model in the technical sense, it is possible that the agent learns to exploit this relational architectural prior similarly to how an imagination-based agent's forward model operates BID15 . More generally, our work opens new directions for RL via a principled hybrid of flexible statistical learning and more structured approaches.
Relational inductive biases improve out-of-distribution generalization capacities in model-free reinforcement learning agents A shared relational network architecture for parameterizing the actor and critic network, focused on distributed advantage actor-critic algorithms, that enhances model-free deep reinforcement techniques with relational knowledge about the environment so agents can learn interpretable state representations. A quantitative and qualitative analysis and evaluation of the self-attention mechanism combined with relation network in the context of model-free RL.