Matthieu Zimmer

Member, IEEE Stephane Doncieux

Bootstrapping Q-Learning for Robotics from Neuro-Evolution Results

Keywords: Developmental robotics, reinforcement learning, continuous environment, representation redescription

Reinforcement learning problems are hard to solve in a robotics context as classical algorithms rely on discrete representations of actions and states, but in robotics both are continuous. A discrete set of actions and states can be defined, but it requires an expertise that may not be available, in particular in open environments. It is proposed to define a process to make a robot build its own representation for a reinforcement learning algorithm. The principle is to first use a direct policy search in the sensori-motor space, i.e. with no predefined discrete sets of states nor actions, and then extract from the corresponding learning traces discrete actions and identify the relevant dimensions of the state to estimate the value function. Once this is done, the robot can apply reinforcement learning (1) to be more robust to new domains and, if required, (2) to learn faster than a direct policy search. This approach allows to take the best of both worlds: first learning in a continuous space to avoid the need of a specific representation, but at a price of a long learning process and a poor generalization, and then learning with an adapted representation to be faster and more robust.

I. INTRODUCTION

A large number of reinforcement learning algorithms explore a set of states and actions to find the sequence of actions maximizing a long-term reward [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF]. The definition of the set of actions and states has a critical importance. It needs to cover all relevant behaviours, but a too large set of actions and states will drastically decrease learning efficiency: this is the curse of dimensionality. In a robotic context, choosing actions and states is particularly difficult. The movements and most of the perceptions of a robot are continuous. A rough discretization results in too many actions and states. The design of smaller sets of relevant actions and states requires a deep insight on robot features and on the behaviours expected to solve the task. An adapted representation with appropriate approximation functions and a good exploitation of prior knowledge are, in practice, the key to success [START_REF] Kober | Reinforcement Learning in Robotics: A Survey[END_REF]. A learning algorithm is expected to let the robot discover its own abilities and to reduce the burden of robot behaviour implementation. The design of appropriate actions and states is then a strong limitation to the application of such algorithms to a robotics context. Reinforcement learning algorithms in continuous spaces do not require this design step, but they require exploring large and continuous search spaces and typically rely on demonstrations by an expert to bootstrap, or on non-random initial policies, or else on dedicated policy representations [START_REF] Kober | Reinforcement Learning in Robotics: A Survey[END_REF][START_REF] Abbeel | An Application of Reinforcement Learning to Aerobatic Helicopter Flight[END_REF][START_REF] Kober | Policy search for motor primitives in robotics[END_REF].

The first motivation of this work is to reduce the expertise required and to let the robot discover on its own the skills it needs to fulfil its mission. Besides simplifying the robot behavior design process, it should make the robot more adaptive to situations unknown during robot programming phase [START_REF] Doncieux | Creativity: A driver for research on robotics in open environments[END_REF]. The second motivation is to let the robot build upon its experience in a developmental robotics perspective [START_REF] Guerin | Learning like a baby: a survey of artificial intelligence approaches[END_REF], to have the robot acquire progressively better generalization, and to learn faster as it acquires more experience. To satisfy these motivations, it is proposed to use several learning algorithms requiring different representations and different levels of a priori knowledge about the robot and the task. The hypothesis explored here is that a robot with adapted representations [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF] is more robust to new situations and (2) can adapt its behaviour faster. The goal is then to allow the robot to change the representation it uses and the corresponding learning algorithm. The robot is provided with two learning algorithms. A first learning algorithm is slow but task agnostic. It relies on low-level sensori-motor values, i.e. raw sensor and effector values. A second one (Q-learning with discrete actions and continuous states) is expected to be faster, but needs high level representations, typically actions and states that are adapted to the robot task. The goal of providing both strategies and not only the fastest one is to bootstrap the second strategy with the knowledge extracted from the results of the first one (Figure 1). The slow and agnostic algorithm is then used first and followed by an analysis step that extracts from the corresponding learning traces the information relevant for the second learning algorithm. The proposed approach has then three different steps: (1) slow learning with a task agnostic algorithm, (2) analysis of the learning traces and extraction of actions and sensors to take into account and (3) exploitation of the representation-specific learning algorithm when facing a new situation. The generation of the first successful behaviours and the representation building process are not performed simultaneously, they are separated into two completely different processes.

The agnostic algorithm is a neuroevolution algorithm, i.e. an evolutionary algorithm that generates both the structure and parameters of a neural network [START_REF] Floreano | Neuroevolution: from architectures to learning[END_REF][START_REF] Yao | Evolving artificial neural networks[END_REF]. Up to millions of neural networks are explored to reach a result of interest. The first step of the proposed approach takes time, but has the advantage of requiring very little a priori knowledge about the task. This algorithm generates a neural network that is well suited for the domain used to evaluate the potential solutions during the learning experiment. When the robot faces a new domain, there is no guarantee that this neural network will generate the expected behaviour -this is the generalization problem [START_REF] Pinville | How to Promote Generalisation in Evolutionary Robotics : the ProGAb Approach Formalising the Generalisation Ability[END_REF]. If the neural network fails to exhibit the expected behaviour, the robot will have to learn again from scratch. The solutions generated on the first task nonetheless contain information about how to solve it. It contains many examples of the orders to send to motors in response to a particular set of sensor values. An analysis and extraction step is then proposed to extract relevant data so that when the robot faces a new situation, it relies on these data and uses another reinforcement learning algorithm to find out how to maximize the long-term reward. The space to explore being much smaller than for neuroevolution, the time required to learn is expected to be much shorter. The proposed approach is tested on two different tasks: a ball collecting task [START_REF] Ollion | Why and How to Measure Exploration in Behavioral Space[END_REF] and a box pushing task [START_REF] Mugan | Autonomous Learning of High-Level States and Actions in Continuous Environments[END_REF].

II. RELATED WORK

Robot positions, perceptions and actions are continuous. Furthermore robot state estimation is prone to error because of noise or perceptual aliasing and actions may fail. Applying a reinforcement learning algorithm to a robot is then not straightforward. Some examples of discrete reinforcement learning with predefined actions and states in a robotics context will be briefly reviewed in this section, followed by a review of approaches in which actions and states are built or updated using the experience acquired previously.

A. Predefined representations

In some problems, a simple and straightforward discretization gives satisfying results. Policies for controlling a ball in a beam [START_REF] Benbrahim | Realtime learning: a ball on a beam[END_REF], a crawler robot [START_REF] Tokic | The Crawler, A Class Room Demonstrator for Reinforcement Learning[END_REF] or a one degree of freedom (DOF) ball-in-the-cup [START_REF] Nemec | Learning of a ball-in-a-cup playing robot[END_REF] have thus been learned with a discrete reinforcement learning algorithm. It is possible because of a limited number of actions, two for [START_REF] Benbrahim | Realtime learning: a ball on a beam[END_REF], four for [START_REF] Tokic | The Crawler, A Class Room Demonstrator for Reinforcement Learning[END_REF] and five for [START_REF] Nemec | Learning of a ball-in-a-cup playing robot[END_REF].

Tasks involving a higher number of possible action values can be solved, but at the price of a more careful design of the actions available for the reinforcement learning algorithm. Willgoss and Iqbal solved an obstacle avoidance task with reinforcement learning by predefining actions like 'forward', 'forward left', 'backward', etc [START_REF] Willgoss | Reinforcement Learning of Behaviors in Mobile Robots Using Noisy Infrared Sensing[END_REF]. Konidaris et al. provided navigation actions (reach a particular position among a set of task-relevant positions) and robot arm movement actions in navigation tasks requiring to manipulate levers and buttons [START_REF] Konidaris | Autonomous Skill Acquisition on a Mobile Manipulator[END_REF]. Several participants of the Robocup Soccer competition have applied reinforcement learning. Kwok and Fox [START_REF] Kwok | Reinforcement learning for sensing strategies[END_REF] have used it for the robot to decide where to point its video camera when kicking a ball into the opponent's goal: the robot had to decide what to look for at a particular moment (ball, goal, opponents, landmarks, etc) as its limited field of view did not allow it to have a complete view of the scene. They have used a reinforcement learning algorithm to decide it with one 'looking at' action for each possible point of interest. Several works of the literature [START_REF] Stone | Reinforcement Learning for RoboCup Soccer Keepaway[END_REF][START_REF] Hester | Generalized model learning for Reinforcement Learning on a humanoid robot[END_REF] used sets of macro actions to apply reinforcement learning algorithms to various RoboCup domains. Depending on the considered soccer behavior they wanted their robot to exhibit, Riedmiller et al. provided either a rough discretization of motor commands (resulting in 76 different actions), or a set of possible motor increase or decrease commands for a set of five well chosen commands for the three motors of the robot [START_REF] Riedmiller | Reinforcement learning for robot soccer[END_REF].

A first conclusion from the review of these examples is that it is possible to make a robot learn with a reinforcement learning algorithm exploiting a set of discrete actions. The difficulty with such an approach is actually to design the set of actions [START_REF] Kober | Reinforcement Learning in Robotics: A Survey[END_REF]. Extending the learning process to build this representation on the fly while the system is learning or developing would make learning algorithms much easier to use in a robotics context.

B. Adapting representations

In a life-long learning perspective [START_REF] Thrun | Lifelong robot learning[END_REF], it makes sense to extract knowledge from the acquired experience in order to improve future problem resolution. This is the main motivation of transfer learning, which is a widely studied field in machine learning in general [START_REF] Pan | A Survey on Transfer Learning[END_REF] and in reinforcement learning in particular [START_REF] Taylor | Transfer Learning for Reinforcement Learning Domains: A Survey[END_REF]. The principle of transfer learning is to rely on the knowledge acquired while solving a source task to solve a target task more efficiently. There are many different kinds of transfer learning approaches in reinforcement learning, for instance transfer of the value function [START_REF] Taylor | Value functions for RL-based behavior transfer: A comparative study[END_REF] or through reward shaping [START_REF] Doncieux | Transfer learning for direct policy search: A reward shaping approach[END_REF][START_REF]Knowledge Extraction from Learning Traces in Continuous Domains[END_REF]. In the following, we focus on the transfer of knowledge through policies and the way they are represented.

Options are an extension of Markov Decision Processes to introduce sub-goals and the corresponding sequences of actions as new actions available for learning [START_REF] Sutton | Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning[END_REF]. Konidaris and Barto proposed an algorithm to discover them automatically [START_REF] Konidaris | Skill Discovery in Continuous Reinforcement Learning Domains using Skill Chaining[END_REF]. Furthermore, options learned in a particular setup can be transferred to a new task or domain if they are defined in a problem independent space [START_REF] Konidaris | Building portable options: Skill transfer in reinforcement learning[END_REF]. Koga et al. have proposed an approach to learn abstract policies in order to increase the generalization ability [START_REF] Koga | Speeding-up Reinforcement Learning Through Abstraction and Transfer Learning[END_REF][START_REF] Koga | Stochastic Abstract Policies: Generalizing Knowledge to Improve Reinforcement Learning[END_REF]. Riano and McGinnity proposed to represent sequences of actions with a finite state automaton and to explore its structure with evolutionary algorithms [START_REF] Riano | Automatically composing and parameterizing skills by evolving Finite State Automata[END_REF]. The advantage of this approach lies mainly in the versatility of evolutionary algorithms that allows both to design the finite state automaton and to tune actions on the fly or even create new ones. All of these approaches require providing a set of primitive actions to bootstrap the system. Once primitive actions are available, they can discover how to combine them to build more abstract actions, but none of those works addresses the question of bootstrapping the process and discovering primitive actions.

Neumann et al. propose to learn complex motion from simpler motion templates [START_REF] Neumann | Learning Complex Motions by Sequencing Simpler Motion Templates[END_REF]. Starting from given motion templates with some initial and relevant parameter values (although not optimal), a reinforcement learning algorithm searches for combinations of these templates together with their parameters. This approach does not require primitive actions, but primitive motion templates need to be defined. It goes further than the previously mentioned approaches with respect to bootstrapping, as a single motion template may result in different primitive actions depending on their parametrization, but it still requires providing significant prior knowledge on the task, a prerequisite that this work tries to avoid.

Mugan et al. proposed QLAP, Qualitative Learner of Action and Perception, a complete framework to bootstrap a cognitive system [START_REF] Mugan | Autonomous Learning of High-Level States and Actions in Continuous Environments[END_REF]. Dynamic Bayesian Networks (DBNs) are built to predict events with an adaptive discretization whose goal is to make models more reliable. The DBNs are then converted into plans that are used to build actions. Exploration starts from random motion and is then driven by a motivation inspired from artificial curiosity [START_REF] Schmidhuber | Curious model-building control systems[END_REF][START_REF] Oudeyer | Intrinsic motivation systems for autonomous mental development[END_REF]. Kompella et al. similarly proposed CCSA, Continual Curiosity driven Skill Acquisition, an approach to learn abstractions that consists in exploring, collecting observations and discretizing it to augment the agent state-space [START_REF] Kompella | Continual curiosity-driven skill acquisition from high-dimensional video inputs for humanoid robots[END_REF][START_REF]Explore to see, learn to perceive, get the actions for free: SKILL-ABILITY[END_REF]. Both approaches can then bootstrap with no primitive actions. It has then the same goal as the approach proposed here. QLAP relies on an initial set of random motor commands and tries to build the representation on the fly while it is learning and trying to maximize the reward. CCSA starts from at least one exploratory behaviour that is supposed to be given. This behaviour can be considered as a primitive action. The difference with respect to previously mentioned approaches, is that CCSA can create other primitive actions.

All the work reviewed in this section either relies on random actions or on dedicated primitives to generate the data that the developmental system will use to build states and actions. Avoiding to rely on predefined primitives is the main motivation of this work. Furthermore, random actions may not be enough to generate data of interest. In the case of interaction with objects, for instance, random motor actions leads, unsurprisingly, to very few interactions if the robot has enough degrees-of-freedom [START_REF] Maestre | Bootstrapping interactions with objects from raw sensorimotor data: a Novelty Search based approach[END_REF], and may thus not provide the system with relevant data to model object interaction. This limitation has motivated the development of the approach proposed here. Contrary to what is done in QLAP and CCSA, in this work the representation is not built while learning, but after having succeeded with a task-agnostic algorithm. The task of building the representation, i.e. actions and states, is then decomposed in three different and clearly separated steps:

(1) obtaining behaviours maximizing the reward, (2) analysing them and building the representation and (3) learning in new contexts while exploiting the representation. The advantages and drawbacks of each approach together with their complementarity will be discussed in Section VIII.

III. BACKGROUND

Reinforcement learning (RL) [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF][START_REF] Kaelbling | Reinforcement learning: A survey[END_REF] is a framework that models sequential decision problems where an agent has to learn to make better decisions by maximizing a reward informing it about the quality of its previous actions.

The underlying formalism of RL algorithms is Markov Decision Processes (MDP). A MDP is formally defined as a tuple S, A, T, R where S is a set of states, A a set of actions, T : S × A × S → [0, 1] are transition probabilities between states (T (s, a, s ) = p(s |a, s) is the probability of reaching state s from state s after executing action a) and R : S × A → R is a reward signal. A policy π : S → A is a mapping from states to actions (the action to be taken in each state) and encodes how the agent behaves. An optimal policy π * is a policy maximizing the expected long-term reward:

π * = arg max π E ∞ t=0 γ t × R(s t , π t (s t )) , (1)
where γ is a discount factor. In MDPs, T and R are given. An optimal policy π * can be computed using dynamic programming (e.g., value iteration, policy iteration) [START_REF] Howard | Dynamic Programming and Markov Processes[END_REF] for instance.

In RL, the agent does not know the transition probabilities T and the reward function R. Model-based methods aim at learning T and R to enable planning and model-free methods only estimate expected rewards. In this work, model-free methods are considered. They can be categorized into three approaches : (1) critic-only methods aim at learning value functions and deduce a policy from them, (2) actor-only methods attempt to learn directly the policy function, and (3) actor-critic methods intend to learn both a value function and a policy. Critic-only methods (Section III-A) are very difficult to apply to continuous actions and rather need a discrete set of actions, making them task-specific. They will be used during the second learning phase, after the creation of a set of discrete actions and the autonomous design of a state estimator. Actor-only methods [START_REF] Kober | Policy search for motor primitives in robotics[END_REF][START_REF] Deb | A and elitist multiobjective genetic algorithm: NSGA-II[END_REF] can deal with continuous state and action spaces, but they are slow. Such a method will be used as a task-agnostic algorithm during the first learning phase (Section III-B2). Actor-critic methods [START_REF] Lillicrap | Continuous control with deep reinforcement learning[END_REF][START_REF] Zimmer | Neural fitted actor-critic[END_REF] can also deal with continuous state and action spaces but not always with a better data efficiency [START_REF] Duan | Benchmarking deep reinforcement learning for continuous control[END_REF]. The actor-only method used here is neuroevolution (see Section III-B).

A. Reinforcement learning with value functions

The function Q estimates the long-term reward to be expected when an action a is chosen in state s (Q : S ×A → R):

Q π (s, a) = E π ∞ k=0 γ k r t+k+1 s t = s, a t = a
For the choice of an action, we will consider angreedy strategy, that exploits most of the time and performs a random exploration move with a small probability, i.e., π(s) = arg max a Q(s, a) with probability 1and π(s) is a random action uniformly drawn in A with probability .

RL with Q values stored in a table suffers from the lack of generalization: what is learned in a state does not impact the knowledge about the value of similar states. A solution to this problem is to use an approximation function to provide a means for both efficient computation and support for generalization. In these approaches, Q values are approximated by a function:

ψ θ : S × A → R,
parametrized by a vector θ whose values are updated whenever reward is received (Q(s, a) ≈ ψ θ (s, a)). This allows to represent Q-values for continuous domains. Moreover, this allows generalizing what is learned in a state to another similar state (notice that ψ θ can take many forms compatible with supervised learning methods: neural networks, linear regression, mixture of Gaussian, etc). In this work, we will rely on neural networks [START_REF] Lin | Scaling up reinforcement learning for robot control[END_REF][START_REF] Tesauro | Practical issues in temporal difference learning[END_REF][START_REF] Rummery | On-line Q-learning using connectionist systems[END_REF], where each action is associated to a different neural network. In this case, the inputs of the neural network are the components of the state, the single output is the Q value associated to this action, and finally θ are the connection weights. In Q-learning [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF], the goal is to train the neural network to approximate:

Q(s t , a t ) = R(s t , a t ) + γ max a ∈A Q(s t+1 , a ). (2)
If the temporal extensions of actions are not identical, and the reward function depends only on the state, the algorithm can be extended to [START_REF] Mcgovern | Roles of macro-actions in accelerating reinforcement learning[END_REF]:

Q(s t , a) = da i=1 γ i-1 R(s t+i ) +γ da max a ∈A Q(s t+da , a ), (3)
where d a is the duration of the action a.

B. Evolutionary Design of Robot's Neuro-controllers

Direct policy search methods optimize policy parameters with respect to the reward function. If the cumulated reward only is taken into account (i.e. intermediate rewards are ignored), it has been shown that direct policy search is equivalent to black-box optimization [START_REF] Stulp | Robot Skill Learning: From Reinforcement Learning to Evolution Strategies[END_REF]. Evolutionary algorithms are powerful black-box optimization tools that can be used to optimize policies. The use of evolutionary algorithms to design robot parts is called evolutionary robotics [START_REF] Doncieux | Evolutionary robotics: What, why, and where to[END_REF]. Neural networks are often used to represent policies for their ability to approximate any kind of function with an arbitrary precision [START_REF] Cybenko | Approximation by superpositions of a sigmoidal function[END_REF]. The use of evolutionary algorithms to design neural networks is named neuroevolution [START_REF] Floreano | Neuroevolution: from architectures to learning[END_REF]. These algorithms have been used on a large range of robotic tasks [START_REF] Nelson | Fitness functions in evolutionary robotics: A survey and analysis[END_REF] that can be grouped in three main categories: locomotion, navigation and foraging tasks. Locomotion tasks typically involve hexapod [START_REF] Filliat | Evolution of neural controllers for locomotion and obstacle-avoidance in a 6-legged robot[END_REF][START_REF] Doncieux | Behavioral diversity with multiple behavioral distances[END_REF] or biped robots [START_REF] Allen | Complex networks of simple neurons for bipedal locomotion[END_REF][START_REF] Lehman | Abandoning Objectives: Evolution Through the Search for Novelty Alone[END_REF]. If most work are focused on locomotion in a straight line, recent work have defined a control architecture including evolutionary approaches and able to learn to walk in any direction [START_REF] Cully | Evolving a behavioral repertoire for a walking robot[END_REF], and even to adapt to motor failures [START_REF] Cully | Robots that can adapt like animals[END_REF]. Navigation tasks are performed on a two-wheeled robot equipped with infrared sensors and range from avoiding obstacles [START_REF] Nolfi | Evolutionary robotics: The biology, intelligence, and technology of self-organizing machines[END_REF] to finding the output of a maze [START_REF] Lehman | Encouraging reactivity to create robust machines[END_REF]. Foraging tasks are also performed on two-wheeled robot and, besides the navigation abilities, require the robot to find objects, pick them up and bring them to a goal location [START_REF] Ollion | Why and How to Measure Exploration in Behavioral Space[END_REF].

Evolutionary robotics methods require few information about the task and do not need to define finite sets of discrete states or actions. There is however a price to pay: they need to explore many different policies and are thus in general very slow.

The general principles of evolutionary algorithms are first introduced, the specificities of their application to robotics are then presented and this section finally describes how to use them to generate neural networks.

1) General principles of evolutionary algorithms: Evolutionary algorithms rely on the Darwinian principles of variation and selection. They are iterative, population-based, stochastic algorithms [START_REF] Eiben | Introduction to Evolutionary Computing (Natural Computing Series)[END_REF]. An initial set of candidate solutions is randomly chosen. Each solution -called a genotype -is evaluated from a fitness function F : G → R no . G is the genotype space. Depending on the needs, it may be a string of binary digits, a vector of real values, a program or a graph, for instance. In this work, genotypes are neural networks, i.e. valued directed graphs. Once each solution is evaluated, a selection process determines the genotypes that will feed the next generation.

New genotypes are copies of their ancestors with some random modifications called mutations. The mutation is a stochastic operator that blindly modifies a genotype. It is the only search operator we will consider here. 1 New genotypes are also evaluated and selected. This process is repeated iteratively to maximize F. Each of these loops is called a generation.

When n o > 1, the problem is said to be multi-objective. Evolutionary algorithms, because of their population-based feature, are easy to adapt to this kind of problems [START_REF] Deb | Multi-objective optimization using evolutionnary algorithms[END_REF]. Considering separately each objective allows to optimize them in parallel and offers the opportunity to deal with policy learning issues through the definition of new and specific objectives [START_REF] Doncieux | Beyond black-box optimization: a review of selective pressures for evolutionary robotics[END_REF]. The Non-dominated Sorting Genetic Algorithm II (NSGA-II) [START_REF] Deb | A and elitist multiobjective genetic algorithm: NSGA-II[END_REF], a state-of-the-art multi-objective evolutionary algorithm, will be used in the following. It is an elitist algorithm that divides the current population into different fronts: the first front is the set of non-dominated solutions in the population 2 . The second front is the set of non dominated solutions once the first front has been removed, etc. The highest ranked fronts survive to the next generation and are used to generate new solutions [START_REF] Deb | A and elitist multiobjective genetic algorithm: NSGA-II[END_REF].

2) Evolutionary robotics: Evolutionary robotics relies on evolutionary algorithms to design policies [START_REF] Doncieux | Evolutionary robotics: What, why, and where to[END_REF][START_REF] Bongard | Evolutionary robotics[END_REF]. 3 Evolutionary algorithms are black-box optimization tools, but when used in robotics, it was shown to be interesting to take into account some of its specificities [START_REF] Doncieux | Beyond black-box optimization: a review of selective pressures for evolutionary robotics[END_REF].

The main specificity of evolutionary algorithms in this context, is the evaluation step. The genotype describes a robot policy. To evaluate it, the robot is placed in its environment in some initial conditions. The corresponding policy determines the orders to be sent to the motors out of robot perceptions. This sensori-motor loop determines the robot's behaviour for a given time length. The fitness value associated to the genotype is deduced from these observations. Task-oriented objectives will evaluate to what extent the robot fulfils the given task, but it has been shown that it was also important to take into account the behaviour in a task-independent way. Evolutionary algorithms include diversity keeping mechanisms that allow to balance exploration and exploitation. They were shown not to be sufficient in robotics applications, unless they take into account robot behaviours. Several approaches were thus defined to enhance exploration in the behaviour space [START_REF] Doncieux | Beyond black-box optimization: a review of selective pressures for evolutionary robotics[END_REF]. Novelty search objectives reward individuals that have a novel behaviour with respect to the current population and an archive of encountered behaviours [START_REF] Lehman | Abandoning Objectives: Evolution Through the Search for Novelty Alone[END_REF]. In this work, we will rely on behavioural diversity [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF]. In this approach, a behavioural diversity objective BD(x) rewards a genotype with respect to the difference of its behaviour with respect to the behaviour of other individuals in the current population:

BD(x) = 1 size(P ) y∈P d(x, y),
where P is the current population, x and y are genotypes. 1 Another operator exists in evolutionary algorithms literature: the crossover. It is a stochastic operator that builds a new genotype out of several parents. It raises difficult issues when dealing with neural networks, and is then often not used at all in this context. 2 A solution is non dominated if no solution is at least equal on all objectives and better on at least one objective. 3 It can also design robot morphology but we will focus here on policy.

d(x, y) is a distance in the behavioural space. Different definitions of behaviours have been tested and all revealed to lead to better results than approaches in which no behavioural diversity was used [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF]. Behavioural diversity is optimized as a separate objective in a multi-objective EA [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF].

Several diversity measures can be used in a same run. It avoids the need to choose a single one and also revealed to speed up convergence [START_REF] Doncieux | Behavioral diversity with multiple behavioral distances[END_REF]. The behavioural diversity objective becomes:

BD k (x) = 1 size(P ) y∈P d k (x, y),
where several behavioural distances d k (x, y) are defined. k is changed after a given number of generations. This approach will be used here and the definition of the behavioural distances used in the following experiments will be described in sections V and VI.

3) Neuroevolution: Evolutionary algorithms offer the possibility to optimize both the structure and the parameters of a neural networks [START_REF] Floreano | Neuroevolution: from architectures to learning[END_REF]. We have used this possibility here, with an approach called DNN [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF], a direct encoding inspired from NEAT. NEAT is a direct encoding that revealed to outperform many other encodings [START_REF] Stanley | Evolving neural networks through augmenting topologies[END_REF]. In NEAT, the mutation operator directly modifies the graph of neurons and connections. A specific mechanism is used to compare neural networks, define a crossover operator and to protect new networks when they appear. DNN is a simplified version of NEAT that do not include this mechanism. It was shown that DNN was actually more efficient than NEAT when associated with behavioural diversity [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF]. DNN consists in randomly generating neural networks without hidden nodes. Several mutation operators are defined. A first operator randomly modifies connection weights using the polynomial mutation [START_REF] Deb | Multi-objective optimization using evolutionnary algorithms[END_REF]. Other mutation operators can add a connection between two randomly selected neurons or remove connections. The last mutation operators can add a neuron by splitting an existing connection, or remove a randomly selected neuron with all of its connections [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF].

IV. METHOD

The proposed method makes no assumption about useful actions or sensors. It aims to extract them from preliminary experiments relying on direct policy search using raw sensori-motor values. It is proposed to generate policies using neuroevolution, a task-agnostic direct policy search. Neural networks take sensor values as inputs and send their outputs directly to robot effectors. They do not need finite set of states nor discrete actions. The price to pay is the time required for them to converge: up to a million policies evaluations may be required to converge. Furthermore, there is no guarantee that a policy maximizing the reward in a domain will still maximize it in a new domain. When facing a new situation, the direct policy search algorithm may need to be executed again.

It is proposed to extract from direct policy search learning traces, states and actions to be used with a reinforcement learning algorithm. Future learning episodes rely on it and are expected to converge faster to a policy maximizing the reward.

The steps of the proposed approach are the following: 1) Learn with direct policy search in a source domain 2) Extract actions and states from the learning traces: a) extract a finite set of actions from traces: i) split the motor flow ii) build linear models of actions iii) select the most representative actions with a clustering algorithm b) identify relevant sensor inputs for state estimation c) learn with Q-learning on the source domain with the extracted action and states (updates the estimator of Q-values) 3) Learn with Q-learning in the target domain.

A. Direct policy search and generation of learning traces

Neuroevolution relies on the principles of variation and selection to generate policies described by neural networks. Many policies are generated and evaluated. These evaluations provide examples of the behaviours that policies may generate, starting from inefficient policies and finishing with efficient ones. A subset of all the evaluations made is selected for actions and state extraction. It should be representative of what a robot can experience. We propose to rely on a sample of evaluations that contains successful individuals as well as inefficient ones. Instead of relying on randomly selected solutions, it is proposed to use the horizon-finite lineage of the best-of-run policy.

In an evolutionary run, a new policy π n+1 is generated through the mutation of another policy π n . 4 π n is the parent policy of π n+1 . The lineage of a solution is the set {π 0 , π 1 , . . . , π n } where π i is the parent of π i+1 . π 0 is a randomly generated policy. Some evolutionary algorithms, including NSGA-II, are elitists, which means that the best individuals are systematically part of the next generation. A policy can then be generated at generation 10, stay in the population, and still generate new policies at generation 100 or more. The parent of a policy π may then have been generated many generations before π enters the current population. 5As evolution is a stochastic process, each evolutionary run will generate a different best policy. This is the reason why we use the term best-of-run policy.

The horizon-finite lineage of a best-of-run policy contains the range of policies from the H last ancestors to the most efficient observed ones. It has then been selected as the set of behaviours to consider for action and state extraction with horizon H = 500.

Learning traces are made up with the sensori-motor flow experienced by the policies in the lineage of the best-of-run policy. Let O i be the set of observations (sensor values) made by the robot while it is controlled by policy π i and let U i be the set of effector commands proposed by the policy in response to those observations (len(O i ) = len(U i ) = n h , n h being the evaluation length).

In the following, the learning traces saved in a direct policy run are the set {(O 0 , U 0 ), (O 1 , U 1 ), . . . , (O n , U n )}, where {π 0 , π 1 , . . . , π n = π * } is the horizon-finite lineage of the bestof-run policy π * .

The learning traces are generated with NSGA-II [START_REF] Deb | A and elitist multiobjective genetic algorithm: NSGA-II[END_REF] as evolutionary algorithm and DNN as neural network encoding [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF] (see section III-B).

B. Discrete actions and continuous commands

The effector commands in the learning traces are continuous: U i = (u i (0), u i (1), . . . , u i (n h )) where u i (t) ∈ R ne , n e being the number of effectors. It is proposed to extract from these traces the set of discrete actions A required for discrete RL [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF]. A mapping between continuous commands and discrete actions then needs to be defined. We have chosen to define actions as follows:

• actions have different temporal extensions. Let us call d a the duration of action a; • actions map to linear functions in the effector space. Let us call Γ a the mapping between an action a, time and effector commands:

Γ a : {0, 1, . . . , d a -1} → R ne .
Γ a is defined as follows:

Γ a (t) =        ∆ (a) 1 (t) . . . ∆ (a) ne(t) , (4) where ∆ (a)
i (t) is the value to send to effector i at time t for the action a. ∆ are linear models:

∆ (a) i (t) = u i × t + v i . ( 5
)
The set of parameters V a describing Γ a is then the following:

V a =       u 1 v 1 . . . . . . u ne v ne    , d a    . (6)
Figure 2 shows examples of actions associated to two effectors. This formalism could be seen as an SMDP [START_REF] Sutton | Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning[END_REF], where the terminal conditions of options are based on the time d a and the internal policy of one option is restricted to a linear model.

We propose to extract V a from learning traces.

C. Extracting actions from traces

The learning traces contain the set of effector commands U i generated by each policy π i in the lineage of the best-of-run and in the evaluation conditions used during the neuroevolution search process. Each U i is a set of n h continuous value vectors: the values that were sent to the effectors at each time step. To extract actions from the different U i , a 2-steps process is defined: a heuristic splits U i in many linear actions, then a clustering algorithm extracts the most representative ones.

The proposed splitting heuristic considers the second derivative of effector commands. It binarizes these values: 0 if it is below the mean second derivative, 1 otherwise. The resulting binary sequence is then used to decide where to put splitting points. Each '1' in the sequence is a potential splitting point. In case of two following '1', the point that corresponds to the lowest second-derivative value is changed to '0'. In the case of a sequence of '1' whose length is above two, only the extreme points are kept. All the others are changed to '0'. The '1' in the sequence after these modifications correspond to the splitting points. The idea behind this strategy is to consider as a single action the sequences of effector commands with slow variations, but also action sequences in which there are fast oscillations. Both sequences are replaced by linear actions. It seems natural for the sequences with slow variations. For the sequence with oscillating values, the linear approximation is very far from the initial sequence. Our motivation was to avoid actions lasting only one time step. Our assumption is that the robot actually filters down the variations with the highest frequencies and thus that the error in practice is lower than what it seems. Robots are in general built with this property, notably to avoid fast oscillations that may have a dramatic impact on robot stability because of its inertia.

The algorithm used to determine the splitting points is provided in a python-like pseudo-language:

1: function SPLIT POINTS(U ∈ R ne×n h ) 2: U ← numerical second derivative(U) 3: M ← mean over ef f ectors(abs(U )) M ∈ R n h 4: L ← mean(M)
The limit to overcome 5:

P ← map(lambda x : x > L, M) P ∈ {0, 1} n h 6: i ← 0 7: while i < n h -1 do 8: j ← 1 9: if P [i] == 1 then 10:
while (i + j < n h ) and (P [i + j] == 1) do 11:

j ← j + 1 12:
end while 13:

if j == 2 then Handle (1,1) sequences.

14:

k ← index min([M i , M i+1 ]) 15: P [k] ← 0 16:
else if j > 2 then Handle longer sequences. 17: Once the splitting points are defined, a linear regression is used to learn V a (d a is set to the distance between the splitting points).

P [i + 1 : i + j -2] = [0] * (j -2)
Repeating this process on {U 0 , U 1 , . . . , U n } produces a huge number of different actions. A fuzzy c-means clustering is used to extract N a representatives from this set of actions [START_REF] Bezdek | FCM: The fuzzy c-means clustering algorithm[END_REF]. The actions extracted are the centroids of the N a clusters found by the fuzzy c-means algorithm. N a is a parameter of the proposed approach, its impact on the performance is studied in Section VII-C.

D. Identification of relevant inputs

Perceptual aliasing is a major problem when applying RL to robotics as it prevents an accurate estimation of the state of the system: identical perceptions can be associated to different states and different actions. Consider the case of a robot that is blocked against a wall with a uniform colour. No matter where the robot exactly is, the perceptions are the same. Suppose that the robot must find its way out of the room. If it is blocked against the wall at the left of the door, then it needs to turn right to go out and if it is at the right of the door, then it must turn left. Instantaneous perceptions do not allow to discriminate these two states. A simple solution consists in taking the past into account. As soon as a previous perception differs, the perceptual aliasing phenomenon vanishes. In our robot navigation example, before crashing into the wall, the robot will probably have different perceptions: it may perceive the door or notice that the left wall is closer or farther, for instance.

Here we assume that taking into account enough previous sensory inputs allows to discriminate states. Considering all past sensory information allows then for sure to determine the robot state, but it makes model training more difficult as much more parameters need to be tuned. There is then a trade-off between the efficiency of the Q -value estimation and the non-ambiguity of the state identification.

We propose to rely on a lasso linear model regression [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF] to identify relevant inputs. Identified inputs are then used to learn a non-linear model of the Q -values with a neural network trained with a back-propagation algorithm during the Q-learning process.

O (j) is the set of all observations in the learning traces in which only the j-th sensor is taken into account: The lasso method is used to build a model of the transition function T that predicts o (j) i (t) values out of a set of selected inputs among previous observations: O i,µ (t-1) = (o i (t-µ-1), o i (t -µ), . . . , o i (t -1)). µ = 8 was empirically chosen as higher values involved too many computations. The resulting set of weights is W = {w (0) , w (1) , . . . , w (ns) }, where w (j) are the weights to predict O (j) (w (j) is a n s × µ matrix). What matters here is whether a value is null or not, its exact value is not used. w (j) [k, l] = 0 means that the k-th input of o l%n h (l/n h ) can be neglected when trying to predict the next value of the j-th observation.

O (j) = o (j) i (t)|i ∈ {0, . . . ,
Let call w (j) bin the set:

w (j) bin = 1 if w (j) [k, l] = 0, 0 otherwise for all k ∈ {0, . . . , n s }, l ∈ {0, . . . , n * n h }} ,
with n the number of individuals in the learning traces and n h the evaluation length.

There is no reason that w

(j1) bin = w (j2)
bin for any j 1 = j 2 . We propose then to aggregate these different values using a majority vote: the inputs that are kept are those for which w (j) bin = 1 in more than half of the j values, i.e. inputs kept are those that are considered as relevant to predict more than half of the observations.

E. Q-learning

Q-values are computed by neural networks that takes as inputs the observations considered as relevant by the method presented in the previous section. Each action is associated to a specific neural network. Each time an action is executed, the corresponding set of observations and the reward thus obtained are used to train the neural networks with a back-propagation algorithm.

The choice of the action to apply is based on a -greedy strategy with a gradual decrease of over the episodes in order to foster exploration:

(t) = ( max -min ) 1+t
stepness + min . This strategy promotes exploration in the early stages, and then exploitation.

A second method is used to make network training more efficient: the replay of traces of interactions already carried out during learning [START_REF] Lin | Scaling up reinforcement learning for robot control[END_REF]. To avoid the few good actions to be overwhelmed by the great majority of wrongdoing, the best tracks are replayed multiple times. A trajectory T of length λ is described as < o(t), a(t), r(t + 1), o(t + 1) > t∈{0,...,λ-1} . After an episode, a new trajectory is produced and stored with its associated score λ-1 t=0 γ t r(t). The η best trajectories are replayed into the network, after each episode, in a random order. The replay of a single trajectory is done in reverse order from λ -1 to 0 to accelerate convergence.

F. Experimental methodology

Two tasks of the literature have been considered: a ball collecting task [START_REF] Doncieux | Behavioral diversity with multiple behavioral distances[END_REF] and a box pushing task [START_REF] Mugan | Autonomous Learning of High-Level States and Actions in Continuous Environments[END_REF]. For each task, two different sets of domains are defined: a source set and a target set.

The source set is used for the initial neuroevolution runs. These runs generate the learning traces out of which the states and relevant inputs are extracted. Once actions are extracted and relevant inputs are identified, neural networks, estimating the Q -values, are trained on the source set to check the Qlearning performance and to prepare it for tests on the target set.

The target set is used for two different goals:

• to compare the generalization ability of the neurocontrollers and of the policy learned with Q-learning (how do these policies perform without a new learning phase); • to compare their learning speed (when learning occurs, how fast is it on the new task). Two different configurations of neuroevolution are considered when comparing the learning speeds on the target task:

(1) neuroevolution starting from randomly generated solutions and (2) neuroevolution starting from the Pareto front generated on the source setup (transfer of the best neuro-controllers).

V. BALL COLLECTING TASK A. Experimental setup

In this task, a mobile robot has to move around in its environment and collect balls before putting them into a basket. The robot does not know where the balls and the basket are, but it has sensors that can tell whether they are in front of it (front left and front right) or not. The environment contains walls that are obstacles for both robot motion and perception. The robot needs then to explore its environment to find the balls and the basket. A switch is present in the environment to make new balls appear. The environment is continuous: the robot, the balls and the basket can be at any position (except within walls).

1) Robot and environment:

The robot has thirteen different sensors : three wall distance sensors, two bumpers, two ball detection sensors, two switch detection sensors, two basket detection sensors, one "carrying ball" sensor and one "switch pulled" sensor that tells the robot if it has already pulled the switch or not. It has three effectors : two wheel motors, and one crane motor to collect balls or activate the switch.

2) Neuroevolution: The same setup as Doncieux and Mouret was used [START_REF] Doncieux | Behavioral diversity with multiple behavioral distances[END_REF]. NSGA-II algorithm is used with the following objectives:

1. number of collected balls 2. dynamic behavioural diversity (see section III-B2) with the following behavioural similarity measures:

adhoc: euclidean distance between the end position of the balls; hamming: hamming distance between the discretized values of the sensors and effectors experienced by the robot; entropy: euclidean distance between the vectors of entropies of sensors and effectors; trajectory: edit distance between the discretized trajectories. The behavioural similarity measure used to compute the behaviour diversity is also randomly changed every 50 generations.

3) Q-learning: The reward function used is the following: R(s) = 100 if a ball just dropped in the basket 0 otherwise . (7)

4) Domains:

The source set is made with one environment and two ball positions. The target set is made with two new environments, each coming with three different robot and object positions (see Figure 4). The source set is then made up with two different domains and the target set with six different domains.

In the source setup, the robot can start from two starting positions (two different domains), and can bring back four balls in each. Thus, the maximum number of collected balls is eight. In the target set, there are six different domains with four balls in each. The maximum score is then twenty four.

B. Results

1) Neuroevolution results: 30 different runs have been performed with a population size of 128 and for 1,000 generations. 10 runs have been done with A environment, 10 with B and 10 with C. For one run, the time required is around 24 hours of simulation on a 2.2 GHz and 16 CPU cores computer.

The median reaches the maximum score after 287 generations, the lower quartile reaches it after 586 generations and the upper quartile after 198 generations (each generation corresponds to 128 evaluations of policies, i.e. 128 episodes, see Figure 6, ER curve). Figure 5 shows an example of a behaviour generated by neuroevolution. After clustering, the median temporal extension is 9 (lower quartile 7, upper 18). To extract sensors and actions, around 3 hours is required.

Q-learning is given 5,000 episodes to learn on the source set (Figure 6). An example of generated behaviour is shown in Figure 7.

The median reaches the best performance after 481 episodes (around 3 hours of simulation for one run).

3) Testing and learning on new domains: The generalization ability of policies trained on the source domain set is evaluated on the target domain set. Their performance is compared to that of Q-learning with the extracted actions (Figure 8). Without further training, the median performance reached by Q-learning is 10, whereas the best policies trained with ER reach a median of 2. The actions extracted from the learning traces provide then a significant generalization ability with respect to the best policies of the learning traces they were extracted from. This result aligns with our hypothesis of the increased robustness of adapted representations to new situations.

Figure 9 shows the learning performance of the different approaches when tested on the target set of domains. All the curves are averaged over 30 runs: one run with the actions and inputs extracted from each of the 30 evolutionary runs for the 'QL' experiments, one run starting with the Pareto For Q-learning, the median reaches the maximum score after 8,616 episodes and the upper quartile after 1,013 only. For ER, the median reaches the maximum score after 268,160 episodes and the lower quartile after 1,263,360 (upper 130,304). For ER + transfer, the median reaches the maximum score after 305,152 episodes and the lower quartile after 557,440 (upper 108,160). The median reaches then the maximum performance for Q-learning three times faster than ER approaches. For the upper quartiles, this difference even goes up to two orders of magnitude. This result aligns with our hypothesis of faster learning with adapted representations.

VI. BOX PUSHING TASK A. Experimental setup

In the second task, a robotic arm with three degrees of freedom must successfully move a box [START_REF] Mugan | Autonomous Learning of High-Level States and Actions in Continuous Environments[END_REF]. It needs to push the box to the left with the end effector centred on the box, which implies to move the arm to a precise position, on the right of the box.

1) Robot and environment: There are three different sizes for the cube and its position is randomly generated. The starting position of the arm is also random. In this environment, the evaluation of a policy does not always produce the same score as the arm and cube positions are random.

The 13 sensors are the same as described by Mugan and Kuipers [START_REF] Mugan | Autonomous Learning of High-Level States and Actions in Continuous Environments[END_REF] :

• the position of hand in x,y,z directions (3 sensors);

• the distance between :

the top of hand and bottom of block; the bottom of hand and top of block (in both x and z: 2 sensors);

the right side of hand and the left side of block; the left side of hand and the right side of block; the left edge of table and the left edge of block; the right edge of table and the right edge of block the top edge of table and the top edge of block.

• The location of hand in x,y directions relative to centre of block (2 sensors). 2) Neuroevolution: NSGA-II algorithm is used in a similar setup to the one used in the ball collecting task. The following objectives are used:

1. number of contacts with the block 2. dynamic behavioural diversity (see section III-B2) with the same behavioural similarity measures than what was used for the ball collecting task. Here, the adhoc measure is the euclidean distance between vectors containing the distance travelled by the arm and by the block in each evaluation and in each dimension. Hamming and entropy are the same and trajectory is the edit distance between the discretized trajectories of the end effector. As for the ball collecting experiment, the behavioural similarity measure is changed every 50 generations [START_REF] Doncieux | Behavioral diversity with multiple behavioral distances[END_REF].

3) Q-learning: The reward function is defined as: R(s) = 10 if the block just shifted to the left 0 otherwise .

The reward obtained when a block is shifted to the left is lower than that obtained when collecting a ball. This is due to the length of the sequence to generate to get a reward, that is longer in the collect ball experiment. This point is discussed in section VIII.

4) Domains: The source domain set is made up with three domains defined by objects of different sizes. The target domain set is made up with three other domains that are also defined by objects having different new sizes (Figure 11).

B. Results

1)

Neuroevolution results: 30 different runs have been performed with a population size of 128 and for 1,000 generations. During an episode, the robot has five tests on three boxes of different size: the optimal score is 15 (1 for each successful test).

The median reaches the maximum score after 390 generations, the lower quartile reaches it after 426 generations and the upper quartile after 333 generations (each generation corresponds to 128 evaluations, see Figure 14, ER curve). An example of behaviour is shown in Figure 12. For one run, the time required is around 12 hours of simulation.

2) Action and state extractions: There are 500 different traces in the filiation of the best individual. The median fitness of those individuals is 10, the lower quartile is 3 and the upper 13. The median number of extracted actions before clustering is 27,998 (lower quartile 26,535, upper quartile 34,634, mean 30,739). The median temporal extension after clustering is 6 (lower quartile 4, upper 18). The Q-learning algorithm is given 5,000 episodes to learn the Q-values (Figure 14). Figure 13 shows an example of how Q-learning used extracted actions: three different actions are used, one that puts the arm at a high position and in the lower right corner of the working space, the second action turns and starts the descent and the last one makes a straightforward trajectory towards the box until it pushes it to the left. Around 30 minutes is enough to extract sensors and actions. For one Q-learning run, the time required is around 1 hour.

3) Testing and learning on a new domain: The performance on the target domain set of policies trained on the source domain set are shown in Figure 15. As for the ball collecting task, policies trained with Q-learning generalize better, even if the difference is smaller than for the ball collecting experiment. This result is aligned with our hypothesis of a best generalization ability with adapted representations.

Figure 16 shows the learning performance of the different approaches on the target set of domains. As for the ball collecting experiment, all the curves are averaged over 30 runs: one run with the actions and inputs extracted for each of the 30 evolutionary runs for the 'QL' experiments, one run starting with the Pareto front of each of the 30 evolutionary runs for the 'ER+transfer' experiments. The parameters used are described in appendix B. For Q-learning, the median reaches the maximum score after 2,119 episodes and the lower quartile after 5,438 (upper 1,084). For ER, the median reaches the maximum score after 243,328 episodes and the upper quartile after 149,760 episodes. For ER + transfer, the median reaches the maximum score after 10,752 episodes and the lower quartile after 37,888 episodes (upper 7,168). These results also confirm our hypothesis of a faster learning with an adapted representation.

VII. ANALYSIS OF THE PROPOSED METHOD

Control experiments have been designed to estimate the contribution of specific aspects of the proposed algorithm We compare the knowledge they have extracted to randomly generated knowledge or to human designed knowledge. Other experiments have been defined to evaluate the sensitivity of the results to the number of chosen actions.

A. Action extraction

How do extracted actions compare to randomly generated or human designed actions? Q-learning experiments have been performed on the source domain set, in which the only difference between the setups are the used actions. The set of sensors on which state estimation relies has been chosen by a human expert. It is the same for all setups.

The actions chosen by the human expert for the collect ball environment are the following : 16 actions to move at a different angle while picking and one action to drop the ball. It is pretty smart as the robot will never need to perform an action for "taking a ball when I am near one". It only has to use the moving actions to catch a ball automatically.

In the robotic arm environment, there are 7 human designed actions: one neutral (don't apply any force) and 2 for each degree of freedom in order to be able to reach every possible position. All these actions were designed before looking at the actions extracted by the proposed approach.

For comparisons to be fair, the number of extracted actions N r and of random actions is the same: 17 for the collect ball experiment and 7 for the box pushing. The temporal extension of human designed actions is fixed for each actions (d a = 15 for ball collecting and d a = 9 for robotic arm). For the random action set, each action has a different temporal extension (drawn uniformly from [5; 25] for ball collecting and from [2; 20] for robotic arm). 6Figure 17 shows the learning speed of the different alternatives. The median is made over 30 runs with 30 different evolution traces (10 for A, 10 for B and 10 for C).

On the ball collecting task, extracted actions have a performance that is similar to human designed actions. Both setups clearly outperform the random actions setup that seldom converges (see p-values in Appendix A-A). On the box pushing task, all setups require a small number of episodes to maximize the reward, but within an episode, the setup with extracted actions needs less steps to reach this result than the human designed one. Both require less steps to maximize the reward than the random actions setup. The variance of human designed actions is low because it is always the same action set over the 30 runs.

The performance of the extracted actions are clearly better than random actions and are competitive with human designed actions.

B. Choice of sensors used for state estimation

What is the influence of the algorithm used to choose the sensors? To answer this question, we have built a set of dedicated Q-learning experiments: In these experiments the actions are fixed: these are the human designed actions described in the previous section. The performance after 10,000 learning episodes on the ball collecting task and 5,000 on the box pushing task, have been plotted on Figure 18. The number of inputs taken into account is plotted under the performance.

The 'instant' setup leads to the poorest performance on the ball collecting task, thus demonstrating the perceptual aliasing problem in this task. Its performance is maximal for the box pushing task, what suggests, unsurprisingly, the absence of perceptual aliasing in this task. The number of sensors used is minimal for this setup.

The number of input neurons selected by the AS strategy is two times lower with the box pushing than with the collect ball. This shows that the proposed strategy has automatically adapted the number of inputs to take into account the level of perceptual aliasing in the environment.

There is no significant difference between the AS and the rand + approach. This suggests that the number of inputs to take into account is an important parameter (that AS finds automatically), but once it is chosen, the sensors to take into account are of lesser importance. As there are perceptual aliasing in the environment, it is clearly important to take into account past sensor values to disambiguate the state estimation. These results suggest that most sensors can actually do it and thus that their choice is not a critical issue.

C. Influence of the number of actions

What is the influence of the number of actions? To investigate this question, we have designed experiments in which the sensors taken into account are the human chosen ones and in which the number of actions changes. Results obtained after 5,000 Q-learning episodes are plotted on Figure 19. For a high number of actions, it is expected to reach the same asymptotic performance but loosing learning speed as the space to explore is bigger. The final performance is constant with respect to the number of actions on both tasks. On the ball collecting task, the standard deviation of the average performance decreases rapidly when the number of actions increases, but its average remains constant. On the box pushing, the average performance slightly decreases. It suggests that the proposed approach is not sensitive to this parameter.

VIII. DISCUSSION AND FUTURE WORK A. Sequential versus iterative developmental process

In the approach introduced here, three different and separated steps are responsible for (1) generating data, (2) analyzing it to build actions and states and (3) exploiting it. It implies that the actions and states that are built during the second step do not influence the exploration part. The development is then sequential. In other approaches, exploration and representation building are iterative processes in which the knowledge currently acquired influences future exploration [START_REF] Mugan | Autonomous Learning of High-Level States and Actions in Continuous Environments[END_REF][START_REF] Kompella | Continual curiosity-driven skill acquisition from high-dimensional video inputs for humanoid robots[END_REF].

Many different intrinsic motivations have been proposed to take into account current knowledge, and how it changes, to choose the next actions to perform [START_REF] Oudeyer | What is Intrinsic Motivation? A Typology of Computational Approaches[END_REF][START_REF] Baldassarre | Intrinsically Motivated Learning in Natural and Artificial Systems[END_REF]. These approaches are very powerful as the system can, for instance, focus on actions that maximizes its learning progress [START_REF] Schmidhuber | Curious model-building control systems[END_REF][START_REF] Oudeyer | Intrinsic motivation systems for autonomous mental development[END_REF]. However, they may have troubles at the very beginning of the approach, when no action has been built. Two different approaches are used in the literature for this bootstrap, either relying on random actions or using dedicated primitive actions. Providing primitive actions requires an expertise about the robot and its Fig. 18. Performance and number of input neurons after convergence : 5000 episodes in box pushing environment and 10000 episodes in collect ball environment. There is 5 different strategies : keeping only the sensors at the current time (instant), human selected sensors, automatic selection from traces of evolution with the presented method, totally random selected (both in number and which) and with the same number of neurons as the AS strategy but randomly selected (rand+). Fig. 19. Impact of the number of actions on the performance. The final performance is computed after the learning algorithm converged, whereas the average performance also takes in account episodes where the algorithm didn't already converge. The final performance represents the asymptotic performance where the average performance represents the learning speed.

environment. It goes against our first motivation. Furthermore, these primitive actions have a direct and significant impact on the very first acquired data. It may then have a strong influence on the actions and states that will be built and may bias the developmental trajectory of the system. Random actions may also create potential problems. Using them requires making an assumption about their potential for generating data of interest, i.e. data that contain the actions or states that make sense with respect to the robot mission. In an environment with objects and for a robot that has many degrees-of-freedom, for instance, very few arm movements actually lead to interactions with objects [START_REF] Maestre | Bootstrapping interactions with objects from raw sensorimotor data: a Novelty Search based approach[END_REF]. If none are observed, the system will hardly bootstrap and will remain in a local optimum in which it perfectly learns to predict and reproduce useless actions but does not go further. The approach proposed here considers the process responsible for the generation of interesting behaviors as a separate process. It corresponds to defining a babbling process in a behavioural space. It can focus on the coverage of robot abilities in the generated data while not caring about how to do it with the representations under construction. Furthermore, from a practical point of view, it allows to separate each step (data generation, data analysis and exploitation of the representation) and study each of them in isolation, what is easier, both from a scientific and technical point of view.

B. Task-specific knowledge

Our main motivation is to reduce the expertise on a task when using a learning algorithm in robotics. To what extent did we satisfy it with the proposed approach?

Most parameters are not specific to the task (see Appendix B). For the neuroevolution step, the only task specific parameters are the kind of used neural networks (recurrent or feed-forward) and the maximum number of steps allowed during evaluation. Most behavioural similarity measures are not specific to a particular task, only the adhoc one is. The corresponding knowledge does not require deep insight on the task, just the knowledge of the important dimensions. For RL, γ and α are to be set, as well as the number of neurons on the hidden layer of the network estimating the Q-values.

Recurrent neural networks can exhibit oscillating behaviours or generate memory-like structures. Recurrent neural networks can thus generate richer behaviours than feed-forward ones.

Generating the structure and parameters of a feed-forward neural network with neuroevolution is in any case simpler and generally faster. Recurrent neural networks can thus be a default choice when little is known about the task and the feed forward structure can be chosen if it is known that the task does not require oscillations or memories.

The number of steps used for evaluation during neuroevolution and γ are both related to the time required to solve the task. An arbitrary long number of steps for evaluation can be used, but it will make neuroevolution runs longer as the main factor influencing neuroevolution run duration is the number of evaluations. A high value of γ in RL will give more weights to future rewards (see Equation 2) and thus encourage the robot to take it into account. A low value will give more weight to immediate rewards and will thus favour immediate small rewards to the detriment of delayed high rewards. The time to get a satisfying reward is then an important parameter for both neuroevolution and reinforcement learning. A metalearning algorithm can regulate this parameter for RL [START_REF] Doya | Metalearning and neuromodulation[END_REF][START_REF] Khamassi | Meta-learning, cognitive control, and physiological interactions between medial and lateral prefrontal cortex[END_REF], as well as for evolution [START_REF] Karafotias | Parameter Control in Evolutionary Algorithms: Trends and Challenges[END_REF]. Tuning these parameters does not require a deep understanding of the tasks, notably it does not require knowing how the robot should solve the task, whereas providing primitive actions implies to have a clear idea about it.

C. Action extraction and second phase learning

This article proposed to use state-of-the-art neuroevolution approaches to generate data out of which action could be extracted and state could be estimated. The very simple heuristics proposed in Section IV resulted in a significant increase of generalization and learning speed. More principled algorithms like Beta Process Autoregressive Hidden Markov Model [START_REF] Niekum | Learning grounded finite-state representations from unstructured demonstrations[END_REF] could achieve a better extraction of actions. To identify relevant dimensions, it is also possible to rely on the importance of weights of the model S t → A t (predicting the behavior) [START_REF] Cobo | Abstraction from demonstration for efficient reinforcement learning in high-dimensional domains[END_REF] instead of relying on S t → S t+1 (predicting the next state).

Many alternatives to the Q-learning algorithm, used during the second learning phase, could have been considered : (1) Neural Fitted Q Iteration [START_REF] Riedmiller | Neural fitted q iteration-first experiences with a data efficient neural reinforcement learning method[END_REF] which aims at learning a single neural network to represent the Q-values in an offline and data efficient manner, (2) NEAT+Q [START_REF] Whiteson | Evolutionary function approximation for reinforcement learning[END_REF] which combines neuro-evolutionary policy search with value-function based reinforcement learning in a continuing manner, or (3) any others data efficient reinforcement learning algorithms that relies on a finite set of actions. Future work should compare the different alternatives to identify the most relevant algorithm for each phase.

IX. CONCLUSION

In this work, an approach has been proposed to extract representations dedicated to discrete RL from learning traces generated by a neuroevolution approach. The goal is to bootstrap a fast RL with a slow, but task agnostic neurevolution approach.

The extracted representations consists in discrete actions with different temporal extensions and in a selection of sensors to take into account for state estimation. The RL algorithm was a Q-learning algorithm in which the Q-values were estimated with a neural network receiving as inputs the selected sensors and trained with back-propagation.

The extracted knowledge associated with the RL algorithm revealed to generalize better to new domains and to allow a faster learning on two simulated robotics tasks from the literature.

ACKNOWLEDGMENTS

This work has been supported by the FET project DREAM 7 , that has received funding from the European Unions Horizon 2020 research and innovation programme under grant agreement No 640891. The authors would like to thank Olivier Sigaud for his comments on a first draft of the article.

The data has been numerically analysed with the free software package GNU Octave [START_REF] Eaton | GNU Octave version 3.0. 1 manual: a high-level interactive language for numerical computations[END_REF] and scikit-learn [START_REF] Pedregosa | Scikitlearn: Machine learning in Python[END_REF]. Experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by INRIA and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr).

APPENDIX A STATISTICAL TESTS

The following tables contain the p -values of Mann-Whitney statistical tests. Near 0 means the 2 distributions are different.

• HD : Human designed

Fig. 1 .

 1 Fig. 1. Overview of the proposed approach.

a 1 a 2 a 3 a 4 a 5 a 6 Fig. 2 .

 62 Fig. 2. A sequence of 6 linear actions with different temporal extensions over r=2 effectors {m1, m2}. da 1 = da 2 = 30, da 3 = da 4 = da 5 = da 6 = 5.

Fig. 3 .

 3 Fig. 3. Example of traces with ne = 2 motors (m1, m2) and n h = 200.The third plot is the mean of the numeric second derivative from the previous traces. The splitting points found by the heuristic can be seen in green. Finally, linear models are learned in red on the 2 last plot.

Fig. 4 .

 4 Fig. 4. Different environments A, B, C (wall positions) used in the ball collecting task. There are three different positions for each object (robot, balls, switch, basket) and for each environment. The robot has to bring back the maximum amount of yellow balls in the green basket. He can also touch the purple switch button to make other balls available.

Fig. 5 .

 5 Fig. 5. Example of behaviour of a best individual generated with ER. The trajectory is plotted in red when the robot carries a ball and in blue otherwise.

2 )

 2 Action and state extraction: There are on average 487 individuals in the filiation of the best individual and thus 487 elements in the learning traces. The median number of extracted actions before clustering is 384,740 (the lower quartile is 246,406, the upper quartile 799,439 and the mean 505,560). The clustering process extracts 17 actions out of it.

Fig. 6 .

 6 Fig. 6. Median and quartile of ER and Q-learning experiments on source set. The first registered performance of ER begins at the 128 th episode because it takes the maximum of the random initial population (population that contains 128 individuals).

Fig. 7 .

 7 Fig. 7. Example of behaviour of a best individual generated with Q-learning with the actions and sensors extracted from the trace of ER. When the trajectory is full, the agent is carrying a ball. Each figure displays a different action of the same trajectory (the one in red). For this figure, the number of actions is reduced for clarity. In this specific case, the 4 actions can be (a posteriori) described as follows: 1) turn slightly right and keep the ball, 2) do not move and drop the ball, 3) turn slightly left and keep the ball, 4) sharp turn to left and keep the ball.

Fig. 8 .

 8 Fig. 8. Generalization ability. Performance on the target domain set of policies trained with ER or Q-learning on the source domain set (p-value : 1.084e-11).

Fig. 9 .

 9 Fig. 9. Medians and quartiles performances on new unknown environments after a learning session. For the ER+transfer, the Pareto front obtained on the previous learning session becomes the new population to optimize, on the contrary, ER starts with a new random population. For the Q-learning strategy, the neural networks are those obtained after the learning session on the source task. First episodes show generalization capacities of Figure 8. ER and ER+transfer curves start after having evaluated the initial population of 128 individuals.

Fig. 10 .

 10 Fig. 10. Continuous environment with realistic physics [70] where a robotic arm must push boxes of different sizes by hitting them on the left.

Fig. 11 .

 11 Fig. 11. The objects of the source domain set are in the top row, the objects of the target domain set are in the bottom row.

Fig. 12 .

 12 Fig. 12. Example of a best behaviour from ER. (x,y,z) is the position of the end effector. The green point is the starting point position and the red is the box position. The green box represents the end effector size (the dashed box shows the last position of the effector).

Fig. 13 .

 13 Fig. 13. Example of a converged behaviour from Q-learning. (x,y,z) is the position of the end effector. The green point is the starting position and the red point is the box position.

Fig. 14 .

 14 Fig. 14. Median and quartile of ER and Q-learning experiments on source set. The first registered performance of ER begins at the 128 th episode because it takes the maximum of the initial random population (population that contains 128 individuals).

Fig. 15 .

 15 Fig. 15. Generalization ability. Performance on the target domain set of policies trained with ER or Q-learning on the source domain set (t-test p-value=0.04804).

Fig. 16 .

 16 Fig. 16. Medians and quartiles performances on new unknown block size after a learning session. For the ER+transfer, the Pareto front obtained on the previous learning session becomes the new population to optimize, on the contrary, ER starts with a new random population. For the Q-learning strategy, the neural networks are those obtained after the learning session on the source task. First episodes show generalization capacities of Figure 15. ER and ER+transfer curves start after having evaluated the initial population of 128 individuals.

•

  instant: sensors in o i (t) are all taken into account. Sensors of previous time steps are ignored; • human: sensors chosen by an expert in the set O i,µ (t) • automatic selection (AS): sensors automatically selected with the proposed lasso approach in the set O i,µ (t) • random: sensors randomly chosen • rand +: sensors randomly chosen, but their number correspond to what the AS setup has found. For the random setup, the number of sensors is first drawn from a uniform distribution in the range [1; 156] (156 = 13 × 12, i.e. 12 times steps of the 13 sensors) and the sensors are then randomly chosen.

Fig. 17 .

 17 Fig. 17. Median and quartile of performance in the collecting ball environment during Q-learning learning with 3 different set of actions : human designed, extracted from evolution learning traces and randomly designed.

  n}, t ∈ {0 . . . , n h } , (t) is the j-th component of o i (t) and o i (t) ∈ R ns the observations experienced by individual i at time t, n s being the number of sensors.

	where o	(j)

i

  Random with the number of sensors selected by the automatic selection 10 -29 8.56 • 10 -10 8.34 • 10 -29 HD 1.51 • 10 -12 2.32 • 10 -2 1.51 • 10 -12 • 10 -5 1.17 • 10 -6 0.14 6.3 • 10 -5 HD 2.77 • 10 -2 4.96 • 10 -3 0.37 AS 9.19 • 10 -4 6.9 • 10 -2 R 1.61 • 10 -2 • 10 -13 1.54 • 10 -10 2.7 • 10 -13 HD 8.17 • 10 -5 1.17 • 10 -7 8.17 • 10 -5 AS 2.45 • 10 -5 R 2.45 • 10 -5 10 -3 6.53 • 10 -2 1.58 • 10 -2 AS 9.34 • 10 -2 2.46 • 10 -2 R 0.74

		HD	AS	R	R+
	I	1.39 Collecting ball performance
		HD	AS		R	R+
	I	0 2.7 Box pushing number input neurons
		HD	AS		R	R+
	I	0.29	0.35	0.81	0.61
	HD	3.94 • Box pushing performance
			APPENDIX B
		PARAMETERS AND NOTATION
		Shared parameters of evolution
	mutation probability			0.1
	cross-rate probability			0
	minimal weight of a connection		-5
	maximal weight of a connection		5
	maximum number of neuron		20
	maximum number of connections		75
	probability to modify a weight of a neuron	0.2
	probability to add a connection		0.133
	probability to add a new neuron		0.088
	probability to remove a connection		0.147
	probability to remove a neuron		0.098
	number of input neurons			13
	number of output neurons			3
	population size entropy discretization change period of behaviour diversity		128 9 50	A. Actions extraction HD	E	HD	E
	Unshared parameters of evolution topology feed-forward -ball collecting	no	5000	R HD	0.0000 0.0000 0.2018	3000	R HD	0.0000 0.0000 0.0000
	topology feed-forward -box pushing maximal number of step -ball collecting	yes 10000			HD	E	HD	E
	maximal number of step -box pushing Shared parameters of trace extraction τ µ Shared parameters of RL start	300 2 8 0.15	15000 30000	R HD R HD	0.0000 0.0000 0.0004 HD E 0.0000 0.0000 0.0081	6000 10000	R HD R HD	0.0000 0.0003 0.0000 HD E 0.0000 0.0006 0.0000
	end					0.01
	stepness η				0.99 3		Ball collecting	Box pushing
	Unshared parameters of RL γ -ball collecting γ -box pushing	0.9991 0.99	B. Sensors extraction HD	AS	R	R+
	α -ball collecting α -box pushing number of hidden neurons -ball collecting	0.001 0.1 125		I 0 8.34 • AS	0.14
	number of hidden neurons -box pushing	35		R	0.14
									Collecting ball number input neurons

• R : Random • E : Extracted from trace • AS : Automatic Selection • I : Instant sensors only • R+ : 7 http://www.robotsthatdream.eu/

Crossover may also contribute to the generation of new individuals, but this operator is not used here.

As a consequence, πn is not necessarily generated at generation n.

These intervals lead to the best results.