First return, then explore.

Reinforcement learning promises to solve complex sequential-decision problems autonomously by specifying a high-level reward function only. However, reinforcement learning algorithms struggle when, as is often the case, simple and intuitive rewards provide sparse1 and deceptive2 feedback. Avoiding these pitfalls requires a thorough exploration of the environment, but creating algorithms that can do so remains one of the central challenges of the field. Here we hypothesize that the main impediment to effective exploration originates from algorithms forgetting how to reach previously visited states (detachment) and failing to first return to a state before exploring from it (derailment). We introduce Go-Explore, a family of algorithms that addresses these two challenges directly through the simple principles of explicitly 'remembering' promising states and returning to such states before intentionally exploring. Go-Explore solves all previously unsolved Atari games and surpasses the state of the art on all hard-exploration games1, with orders-of-magnitude improvements on the grand challenges of Montezuma's Revenge and Pitfall. We also demonstrate the practical potential of Go-Explore on a sparse-reward pick-and-place robotics task. Additionally, we show that adding a goal-conditioned policy can further improve Go-Explore's exploration efficiency and enable it to handle stochasticity throughout training. The substantial performance gains from Go-Explore suggest that the simple principles of remembering states, returning to them, and exploring from them are a powerful and general approach to exploration-an insight that may prove critical to the creation of truly intelligent learning agents.

Environmental, individual and social traits of free-ranging raccoons influence performance in cognitive testing.

Cognitive abilities, such as learning and flexibility, are hypothesized to aid behavioral adaptation to urbanization. Although growing evidence suggests that cognition may indeed facilitate persistence in urban environments, we currently lack knowledge of the cognitive abilities of many urban taxa. Recent methodological advances, including radio frequency identification (RFID), have extended automated cognitive testing into the field but have yet to be applied to a diversity of taxa. Here, we used an RFID-enabled operant conditioning device to assess the habituation, learning and cognitive flexibility of a wild population of raccoons (Procyon lotor). We examined how several biological and behavioral traits influenced participation and performance in testing. We then compared the cognitive performance of wild raccoons tested in natural conditions with that of wild-caught raccoons tested in captivity from a previous study. In natural conditions, juvenile raccoons were more likely to habituate to the testing device, but performed worse in serial reversal learning, compared with adults. We also found that docile raccoons were more likely to learn how to operate the device in natural conditions, which suggests a relationship between emotional reactivity and cognitive ability in raccoons. Although raccoons in both captive and natural conditions demonstrated rapid associative learning and flexibility, raccoons in captive conditions generally performed better, likely owing to the heightened vigilance and social interference experienced by raccoons in natural conditions. Our results have important implications for future research on urban carnivores and cognition in field settings, as well as our understanding of behavioral adaptation to urbanization and coexistence with urban wildlife.

Evolving Multimodal Robot Behavior via Many Stepping Stones with the Combinatorial Multiobjective Evolutionary Algorithm.

An important challenge in reinforcement learning is to solve multimodal problems, where agents have to act in qualitatively different ways depending on the circumstances. Because multimodal problems are often too difficult to solve directly, it is often helpful to define a curriculum, which is an ordered set of subtasks that can serve as the stepping stones for solving the overall problem. Unfortunately, choosing an effective ordering for these subtasks is difficult, and a poor ordering can reduce the performance of the learning process. Here, we provide a thorough introduction and investigation of the Combinatorial Multiobjective Evolutionary Algorithm (CMOEA), which allows all combinations of subtasks to be explored simultaneously. We compare CMOEA against three algorithms that can similarly optimize on multiple subtasks simultaneously: NSGA-II, NSGA-III, and ε-Lexicase Selection. The algorithms are tested on a function-optimization problem with two subtasks, a simulated multimodal robot locomotion problem with six subtasks, and a simulated robot maze-navigation problem where a hundred random mazes are treated as subtasks. On these problems, CMOEA either outperforms or is competitive with the controls. As a separate contribution, we show that adding a linear combination over all objectives can improve the ability of the control algorithms to solve these multimodal problems. Lastly, we show that CMOEA can leverage auxiliary objectives more effectively than the controls on the multimodal locomotion task. In general, our experiments suggest that CMOEA is a promising algorithm for solving multimodal problems.

Variation in reversal learning by three generalist mesocarnivores.

Urbanization imposes novel challenges for wildlife, but also provides new opportunities for exploitation. Generalist species are commonly found in urban habitats, but the cognitive mechanisms facilitating their successful behavioral adaptations and exploitations are largely under-investigated. Cognitive flexibility is thought to enable generalists to be more plastic in their behavior, thereby increasing their adaptability to a variety of environments, including urban habitats. Yet direct measures of cognitive flexibility across urban wildlife are lacking. We used a classic reversal-learning paradigm to investigate the cognitive flexibility of three generalist mesocarnivores commonly found in urban habitats: striped skunks (Mephitis mephitis), raccoons (Procyon lotor), and coyotes (Canis latrans). We developed an automated device and testing protocol that allowed us to administer tests of reversal learning in captivity without extensive training or experimenter involvement. Although most subjects were able to rapidly form and reverse learned associations, we found moderate variation in performance and behavior during trials. Most notably, we observed heightened neophobia and a lack of habituation expressed by coyotes. We discuss the implications of such differences among generalists with regard to urban adaptation and we identify goals for future research. This study is an important step in investigating the relationships between cognition, generalism, and urban adaptation.

Guiding Neuroevolution with Structural Objectives.

The structure and performance of neural networks are intimately connected, and by use of evolutionary algorithms, neural network structures optimally adapted to a given task can be explored. Guiding such neuroevolution with additional objectives related to network structure has been shown to improve performance in some cases, especially when modular neural networks are beneficial. However, apart from objectives aiming to make networks more modular, such structural objectives have not been widely explored. We propose two new structural objectives and test their ability to guide evolving neural networks on two problems which can benefit from decomposition into subtasks. The first structural objective guides evolution to align neural networks with a user-recommended decomposition pattern. Intuitively, this should be a powerful guiding target for problems where human users can easily identify a structure. The second structural objective guides evolution towards a population with a high diversity in decomposition patterns. This results in exploration of many different ways to decompose a problem, allowing evolution to find good decompositions faster. Tests on our target problems reveal that both methods perform well on a problem with a very clear and decomposable structure. However, on a problem where the optimal decomposition is less obvious, the structural diversity objective is found to outcompete other structural objectives-and this technique can even increase performance on problems without any decomposable structure at all.

The Evolutionary Origins of Hierarchy.

Hierarchical organization-the recursive composition of sub-modules-is ubiquitous in biological networks, including neural, metabolic, ecological, and genetic regulatory networks, and in human-made systems, such as large organizations and the Internet. To date, most research on hierarchy in networks has been limited to quantifying this property. However, an open, important question in evolutionary biology is why hierarchical organization evolves in the first place. It has recently been shown that modularity evolves because of the presence of a cost for network connections. Here we investigate whether such connection costs also tend to cause a hierarchical organization of such modules. In computational simulations, we find that networks without a connection cost do not evolve to be hierarchical, even when the task has a hierarchical structure. However, with a connection cost, networks evolve to be both modular and hierarchical, and these networks exhibit higher overall performance and evolvability (i.e. faster adaptation to new environments). Additional analyses confirm that hierarchy independently improves adaptability after controlling for modularity. Overall, our results suggest that the same force-the cost of connections-promotes the evolution of both hierarchy and modularity, and that these properties are important drivers of network performance and adaptability. In addition to shedding light on the emergence of hierarchy across the many domains in which it appears, these findings will also accelerate future research into evolving more complex, intelligent computational brains in the fields of artificial intelligence and robotics.

The Emergence of Canalization and Evolvability in an Open-Ended, Interactive Evolutionary System.

Many believe that an essential component for the discovery of the tremendous diversity in natural organisms was the evolution of evolvability, whereby evolution speeds up its ability to innovate by generating a more adaptive pool of offspring. One hypothesized mechanism for evolvability is developmental canalization, wherein certain dimensions of variation become more likely to be traversed and others are prevented from being explored (e.g., offspring tend to have similar-size legs, and mutations affect the length of both legs, not each leg individually). While ubiquitous in nature, canalization is rarely reported in computational simulations of evolution, which deprives us of in silico examples of canalization to study and raises the question of which conditions give rise to this form of evolvability. Answering this question would shed light on why such evolvability emerged naturally, and it could accelerate engineering efforts to harness evolution to solve important engineering challenges. In this article, we reveal a unique system in which canalization did emerge in computational evolution. We document that genomes entrench certain dimensions of variation that were frequently explored during their evolutionary history. The genetic representation of these organisms also evolved to be more modular and hierarchical than expected by chance, and we show that these organizational properties correlate with increased fitness. Interestingly, the type of computational evolutionary experiment that produced this evolvability was very different from traditional digital evolution in that there was no objective, suggesting that open-ended, divergent evolutionary processes may be necessary for the evolution of evolvability.