Reinforcement learning (RL) has proven to be a powerful paradigm for deriving complex behaviors from simple reward signals in a wide range of environments. When applying RL to continuous control agents in simulated physics environments, the body is usually considered to be part of the environment. However, during evolution the physical body of biological organisms and their controlling brains are co-evolved, thus exploring a much larger space of actuator/controller configurations. Put differently, the intelligence does not reside only in the agent's mind, but also in the design of their body. 
 We propose a method for uncovering strong agents, consisting of a good combination of a body and policy, based on combining RL with an evolutionary procedure. Given the resulting agent, we also propose an approach for identifying the body changes that contributed the most to the agent performance. We use the Shapley value from cooperative game theory to find the fair contribution of individual components, taking into account synergies between components. 
 We evaluate our methods in an environment similar to the the recently proposed Robo-Sumo task, where agents in a 3D environment with simulated physics compete in tipping over their opponent or pushing them out of the arena. Our results show that the proposed methods are indeed capable of generating strong agents, significantly outperforming baselines that focus on optimizing the agent policy alone. 

 A video is available at: www.youtube.com/watch?v=eei6Rgom3YY Reinforcement Learning (RL) uses a simple reward signal to derive complex agent policies, with recent progress on representing the policy using deep neural networks leading to strong results in game playing BID29 Silver et al., 2016) , robotics BID22 BID23 and dialog systems BID24 . Such algorithms were designed for stationary environments, but having multiple learning agents interact yields a non-stationary environment (Littman, 1994; BID2 . Various approaches were proposed for continuous control, required for locomotion in an physics simulator environment BID16 BID31 BID0 . Although very successful, such approaches consider the body of the agent to be fixed, simply a part of the environment. However, during evolution the physical body of biological organisms is constantly changing; thus, the controlling brain and physical body are jointly optimized, exploring a larger space of actuator-controller configurations.The interaction of evolution with learning by individual animals over their lifetime can result in superior performance (Simpson, 1953) . Researchers refer to how individual learning can enhance evolution at the species level as the "Baldwin Effect" (Weber & Depew, 2003) , where learning guides evolution by smoothing the fitness landscape. In learning agents, the physical shape of the body plays a double role. First, a good body has the capability of effectively exerting many forces in the environment. Second, a well-configured body is easier to learn to control, by making it simpler to identify good policies for exerting the forces. Consider a physical task which requires exerting certain forces at the right time, such as locomotion. Some bodies can exert the required forces, while others cannot. Further, some bodies exert the required forces only under a small set of exactly correct policies, whereas others have a wide range of policies under which they exert the required forces (at least approximately). In other words, some bodies have a wide "basin of attraction" where a learner can find a policy that exerts at least a part of the required forces; once discovering a policy in this wide basin, the learner can optimize the policy to exert the required forces.This indicates that the intelligence of agents resides not only in their mind (the controller), but also in the design of their body. Our contribution is proposing a method for uncovering strong agents, consisting of a good combination of a body and policy. This stands in contrast to the traditional paradigm, which takes the body as a given (i.e. a fixed part of the environment), as shown in FIG0 . Our technique combines RL with an evolutionary procedure. We also show how to identify the body changes that contributed the most to agent performance, taking into account synergies between them. We demonstrate our method in an environment similar to the Robo-Sumo task (AlShedivat et al., 2017) , where agents in a 3D environment with simulated physics compete in pushing the opponent out of the arena or tipping it over. This environment is based on the MuJoCo physics simulator (Todorov et al., 2012) , allowing us to easily modify the agent's body. Our results show that the proposed methods are indeed capable of generating superior agents, significantly outperforming baselines that focus on optimizing the agent policy alone.Related Work Evolving virtual creatures (EVCs) work uses genetic algorithms to evolve the structure and controllers of virtual creatures in physically simulated environments, without learning (Sims, 1994) . EVCs have a genetically defined morphology and control system that are co-evolved to perform locomotion tasks (Sims, 1994; BID7 BID4 , with some methods using a voxel-based "soft-body" BID4 BID17 BID28 . Most such attempts have yielded relatively simple behaviors and morphologies BID7 BID3 . One approach to enable continually increasing complex behavior is using a curriculum BID6 . Researchers hypothesized that embodied cognition, where a controller expresses its behavior through a body, may cause morphological changes to have an immediate detrimental impact on a behavior BID3 . For example, a mutation generating longer legs may harm performance with a controller optimized for shorter legs. This results in pressure to converge on a body design early in evolution, to give the controller a stable platform to optimize. This interdependence can be mitigated by giving the controller time to adapt to morphological changes, so bodies that are easier to learn to control would have an evolutionary advantage, and learning would smooth the fitness landscape; this may speed up body evolution, with the extent of learning required for new bodies decreasing over time (Simpson, 1953; Weber & Depew, 2003) .Scenarios where learning is used only in the evaluation phase of evolved agents are referred to as Baldwinian evolution (Weber & Depew, 2003) , where the results of learning are discarded when an offspring is generated. This is in contrast to "Lamarkian evolution" (Whitley et al., 1994; BID20 , where the result of learning is passed on to offspring. Typically the adaption stage uses a genetic algorithm operating to evolve the controller BID3 BID20 . In contrast , we use an RL algorithm to learn to control an evolving body. RL has achieved complex behaviours in continuous control tasks with fixed morphology BID16 BID31 BID0 , and has the potential to adapt to morphological changes. Our experiments evaluate the potential of evolving the bodies of a population of learning agents. We leverage Population Based Training BID18 (PBT), originally proposed to evolve parameters of the controller. To our knowledge, this is the first attempt at evolving the body of continuously controlled RL agents in a physically simulated environment.Preliminaries We apply multi-agent reinforcement learning in partially-observable Markov games (i.e. partially-observable stochastic games) BID34 Littman, 1994; BID13 . In every state, agents take actions given partial observations of the true world state, and each obtains an individual reward. Agents learn an appropriate behavior policy from past interactions. In our case, given the physics simulator state, agents observe an egocentric view consisting of the positions and velocities of their and their opponent's bodies (end effectors and joints) and distances from the edges of the pitch. Our agents have actuated hinges (one at the "knee" and one at the "hip" of every limb). The full specification for our environment (observations and actions) are given in the Appendix, and are similar to other simulated physics locomotion tasks BID16 . Every agent has its own experience in the environment, and independently learns a policy, attempting to maximize its long term γ-discounted utility, so learning is decentralized BID2 .Our analysis of the relative importance of the body changes uses cooperative game theory. We view the set of body changes as a "team " of players, and quantify the impact of individual components, taking into account synergies between them. Game theory studies players who can form teams, looking for fair ways of estimating the impact of individual players in a team. A cooperative game consists of a set A of n players, and a characteristic function v : 2 A → R which maps any team C ⊆ A of players to a real value, showing the performance of the team as a whole. In our case, A consists of all changes to body components resulting in the final body configuration. The marginal contribution of a player i in a team C that includes it (i.e. i ∈ C) is the change in performance resulting from excluding i: DISPLAYFORM0 We define a similar concept for permutations. Denote by π a permutation of the players ( i.e. π : {1, 2, . . . , n} → {1, 2, . . . , n} where π is a bijection), and by Π the set of all player permutations. We refer to the players occurring before i in the permutation π as the predecessors of i in π, and denote by S π (i) the predecessors of i in π, i.e. S π (i) = {j|π(j) < π(i)}. The marginal contribution of a player i in a permutation is the change in performance between i's predecessors and including i, and the performance of i's predecessors alone: BID35 ) is considered a fair allocation of the overall reward achieved by a team to the individual players in a team, reflecting the contribution of each individual player to the team's success BID12 Straffin, 1988) . It is the unique value exhibiting various fairness axioms BID9 BID11 , taking into account synergies between agents (see Section 8 in the Appendix for a detailed discussion and examples of how the Shapley value captures such synergies between body components). The Shapley value is the marginal contribution of a player , averaged across all player permutations, given by the vector DISPLAYFORM1 DISPLAYFORM2 We proposed a framework for jointly optimizing agent body and policy, combining continuous control RL agents with an evolutionary procedure for modifying agent bodies. Our analysis shows that this technique can achieve stronger agents than obtained by optimizing the controller alone. We also used game theoretic solutions to identify the most influential body changes. Several questions remain open. First, can we augment our procedure to also modify the neural network architecture of the controller, similarly to recent neural architecture optimizers BID27 ? Second, can we use similar game theoretic methods to guide the evolutionary process? Finally, How can we ensure the diversity of agents' bodies so as to improve the final performance? Darrell Whitley, V Scott Gordon, and Keith Mathias. Lamarckian evolution, the baldwin effect and function optimization. In International Conference on Parallel Problem Solving from Nature, pp. 5-15. Springer, 1994.
Evolving the shape of the body in RL controlled agents improves their performance (and help learning) PEOM algorithm that incorporates Shapley value to accelerate the evolution by identifying contribution of each body part