Elliot Chane-Sane

Cordelia Schmid

Ivan Laptev

Goal-Conditioned Reinforcement Learning with Imagined Subgoals

Goal-conditioned reinforcement learning endows an agent with a large variety of skills, but it often struggles to solve tasks that require more temporally extended reasoning. In this work, we propose to incorporate imagined subgoals into policy learning to facilitate learning of complex tasks. Imagined subgoals are predicted by a separate high-level policy, which is trained simultaneously with the policy and its critic. This high-level policy predicts intermediate states halfway to the goal using the value function as a reachability metric. We don't require the policy to reach these subgoals explicitly. Instead, we use them to define a prior policy, and incorporate this prior into a KL-constrained policy iteration scheme to speed up and regularize learning. Imagined subgoals are used during policy learning, but not during test time, where we only apply the learned policy. We evaluate our approach on complex robotic navigation and manipulation tasks and show that it outperforms existing methods by a large margin.

Introduction

An intelligent agent aims at solving tasks of varying horizons in an environment. It must be able to identify how the different tasks intertwine with each other and leverage behaviors learned by solving simpler tasks to efficiently master more complex tasks. For instance, once a legged robot has learned how to walk in every direction in a simulated maze environment, it could use these behaviors to efficiently learn to navigate in this environment. Goal-conditioned reinforcement learning (RL) [START_REF] Kaelbling | Learning to achieve goals[END_REF][START_REF] Schaul | Universal value function approximators[END_REF][START_REF] Andrychowicz | Hindsight experience replay[END_REF] defines each task by the desired goal and, in principle, could learn a wide range of skills. In practice, however, reinforcement learning struggles to perform temporally extended reasoning. Hierarchical methods have proven effective for learning temporal abstraction in long-horizon problems [START_REF] Dayan | Feudal reinforcement learning[END_REF][START_REF] Wiering | Hq-learning[END_REF][START_REF] Sutton | Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning[END_REF][START_REF] Dietterich | Hierarchical reinforcement learning with the maxq value function decomposition[END_REF]. In the goal-conditioned setting, a high-level controller typically finds an appropriate sequence of subgoals that can be more easily followed by a low-level policy [START_REF] Nachum | Data-efficient hierarchical reinforcement learning[END_REF][START_REF] Gupta | Relay policy learning: Solving long-horizon tasks via imitation and reinforcement learning[END_REF]. When chosen appropriately, these subgoals effectively decompose a complex task into easier tasks. However, hierarchical methods are often unstable to train [START_REF] Nachum | Data-efficient hierarchical reinforcement learning[END_REF] and rely on appropriate temporal design choices.

In this work, we propose to use subgoals to improve the goal-conditioned policy. Instead of reaching the subgoals explicitly, our method builds on the following intuition. If the current policy can readily reach a subgoal, it could provide guidance for reaching more distant goals, as illustrated in Figure 1. We apply this idea to all possible state and goal pairs of the environment. This self-supervised approach progressively extends the horizon of the agent throughout training. At the end of training, the resulting flat policy does not require access to subgoals and can reach distant goals in its environment.

Our method does not require a full sequence of subgoals, but predicts subgoals that are halfway to the goal, such arXiv:2107.00541v1 [cs.LG] 1 Jul 2021 Figure 2. Overview over our Reinforcement learning with Imagined Subgoals (RIS) approach. During policy training, the policy π is constrained to stay close to the prior policy π prior through KL-regularization. We define the prior policy π prior as the distribution of actions required to reach intermediate subgoals sg of the task. Given the initial state s and the goal state g, the subgoals are generated by the high-level policy π H . Note that the high-level policy and subgoals are only used during training of the target policy π. At test time we directly use π to generate appropriate actions.

that reaching them corresponds to a lower level of temporal abstraction than reaching the goal. To handle this subgoal prediction problem, we simultaneously train a separate highlevel policy operating in the state space and use the value function of the goal-conditioned policy as a relative measure of distance between states [START_REF] Eysenbach | Search on the replay buffer: Bridging planning and reinforcement learning[END_REF][START_REF] Nasiriany | Planning with goal-conditioned policies[END_REF].

To incorporate subgoals into policy learning, we introduce a prior policy defined as the distribution over actions required to reach intermediate subgoals (Figure 2). When using appropriate subgoals that are easier to reach, this prior policy corresponds to an initial guess to reach the goal. Accordingly, we leverage a policy iteration with an additional Kullback-Leibler (KL) constraint scheme towards this prior policy. This adequately encourages the policy to adapt the simpler behaviors associated with reaching these subgoals to master more complex goal-reaching tasks in the environment. Because these subgoals are not actively pursued when interacting with the actual environment but only used to accelerate policy learning, we refer to them as imagined subgoals. Imagined subgoals and intermediate subgoals have equal meaning in this paper.

Our method, Reinforcement learning with Imagined Subgoals (RIS), builds upon off-policy actor-critic approaches for continuous control and additionally learns a high-level policy that updates its predictions according to the current goal-reaching capabilities of the policy. Our approach is general, solves temporally extended goal-reaching tasks with sparse rewards, and self-supervises its training by choosing appropriate imagined subgoals to accelerate its learning.

In summary, our contributions are threefold: (1) we propose a method for predicting subgoals which decomposes a goalconditioned task into easier subtasks;

(2) we incorporate these subgoals into policy learning through a KL-regularized policy iteration scheme with a specific choice of prior policy;

and

(3) we show that our approach greatly accelerates policy learning on a set of simulated robotics environments that involve motor control and temporally extended reasoning.1

Related Work

Goal-conditioned reinforcement learning has been addressed by a number of methods [START_REF] Kaelbling | Learning to achieve goals[END_REF][START_REF] Schaul | Universal value function approximators[END_REF][START_REF] Andrychowicz | Hindsight experience replay[END_REF][START_REF] Veeriah | Many-goals reinforcement learning[END_REF][START_REF] Pong | Temporal difference models: Model-free deep RL for model-based control[END_REF][START_REF] Nair | Visual reinforcement learning with imagined goals[END_REF]Zhao et al., 2019;[START_REF] Pitis | Maximum entropy gain exploration for long horizon multi-goal reinforcement learning[END_REF][START_REF] Eysenbach | Clearning: Learning to achieve goals via recursive classification[END_REF]. Given the current state and the goal, the resulting policies predict action sequences that lead towards the desired goal. Hindsight experience replay (HER) [START_REF] Kaelbling | Learning to achieve goals[END_REF][START_REF] Andrychowicz | Hindsight experience replay[END_REF] is often used to improve the robustness and sample efficiency of goal-reaching policies. While in theory such policies can address any goal-reaching task, they often fail to solve temporally extended problems in practice [START_REF] Levy | Learning multi-level hierarchies with hindsight[END_REF][START_REF] Nachum | Data-efficient hierarchical reinforcement learning[END_REF].

Long-horizon tasks can be addressed by hierarchical reinforcement learning [START_REF] Dayan | Feudal reinforcement learning[END_REF][START_REF] Wiering | Hq-learning[END_REF][START_REF] Dietterich | Hierarchical reinforcement learning with the maxq value function decomposition[END_REF][START_REF] Levy | Learning multi-level hierarchies with hindsight[END_REF][START_REF] Vezhnevets | Feudal networks for hierarchical reinforcement learning[END_REF]. Such methods often design highlevel policies that operate at a coarser time scale and control execution of low-level policies. To address goal-conditioned settings, high-level policies can be learned to iteratively predict a sequence of intermediate subgoals. Such subgoals can then be used as targets for low-level policies [START_REF] Nachum | Data-efficient hierarchical reinforcement learning[END_REF][START_REF] Gupta | Relay policy learning: Solving long-horizon tasks via imitation and reinforcement learning[END_REF][START_REF] Nair | Hierarchical foresight: Self-supervised learning of long-horizon tasks via visual subgoal generation[END_REF]. As an alternative to the iterative planning, other methods generate sequences of subgoals with a divide-and-conquer approach [START_REF] Jurgenson | Subgoal trees a framework for goal-based reinforcement learning[END_REF][START_REF] Parascandolo | Divide-and-conquer monte carlo tree search for goal-directed planning[END_REF]Pertsch et al., 2020b). While hierarchical RL methods can better address long-horizon tasks, the joint learning of highlevel and low-level policies may imply instabilities [START_REF] Nachum | Data-efficient hierarchical reinforcement learning[END_REF]. Similar to previous hierarchical RL methods, we use subgoals to decompose long-horizon tasks into simpler problems. Our subgoals, however, are only used during policy learning to guide and accelerate the search of the non-hierarchical policy.

Several recent RL methods use the value function of goalreaching policies to measure distances between states and to plan sequences of subgoals [START_REF] Nasiriany | Planning with goal-conditioned policies[END_REF][START_REF] Eysenbach | Search on the replay buffer: Bridging planning and reinforcement learning[END_REF]Zhang et al., 2020). In particular, LEAP [START_REF] Nasiriany | Planning with goal-conditioned policies[END_REF] uses the value function of TDM policies [START_REF] Pong | Temporal difference models: Model-free deep RL for model-based control[END_REF] and optimizes sequences of appropriate subgoals at test time. Similar to previous methods, we use the value function as a distance measure between states. Our method, however, avoids expensive test-time optimization of subgolas. We also experimentally compare our method with LEAP and demonstrate improvements. Moreover, we show that our approach can benefit from recent advances in learning representations for reinforcement learning from pixels on a vision-based robotic manipulation task [START_REF] Kostrikov | Image augmentation is all you need: Regularizing deep reinforcement learning from pixels[END_REF][START_REF] Laskin | Reinforcement learning with augmented data[END_REF].

Many approaches cast reinforcement learning as a probabilistic inference problem where the optimal policy should match a probability distribution in a graphical model defined by the reward and the environment dynamics [START_REF] Toussaint | Robot trajectory optimization using approximate inference[END_REF][START_REF] Kappen | Optimal control as a graphical model inference problem[END_REF][START_REF] Levine | Reinforcement learning and control as probabilistic inference: Tutorial and review[END_REF]. Several methods optimize an objective incorporating the divergence between the target policy and a prior policy. The prior policy can be fixed [START_REF] Haarnoja | Reinforcement learning with deep energy-based policies[END_REF]Abdolmaleki et al., 2018b;Haarnoja et al., 2018a;Pertsch et al., 2020a) or learned jointly with the policy [START_REF] Teh | Robust multitask reinforcement learning[END_REF][START_REF] Galashov | Information asymmetry in kl-regularized RL[END_REF][START_REF] Tirumala | Exploiting hierarchy for learning and transfer in klregularized rl[END_REF]. While previous work imposes explicit priors e.g., in the multi-task and transfer learning settings [START_REF] Teh | Robust multitask reinforcement learning[END_REF][START_REF] Galashov | Information asymmetry in kl-regularized RL[END_REF][START_REF] Tirumala | Exploiting hierarchy for learning and transfer in klregularized rl[END_REF], we constrain our policy search by the prior distribution implicitly defined by subgoals produced by the high-level policy.

Behavior priors have often been used to avoid value overestimation for out-of-distribution actions in offline reinforcement learning [START_REF] Fujimoto | Addressing function approximation error in actor-critic methods[END_REF][START_REF] Wu | Behavior regularized offline reinforcement learning[END_REF][START_REF] Kumar | Stabilizing off-policy q-learning via bootstrapping error reduction[END_REF][START_REF] Siegel | Keep doing what worked: Behavioral modelling priors for offline reinforcement learning[END_REF]Nair et al., 2020;[START_REF] Wang | Critic regularized regression[END_REF]. Similar to these methods, we constrain our high-level policy to avoid predicting subgoals outside of the valid state distribution.

Finally, our work shares similarities with guided policy search methods [START_REF] Levine | Guided policy search[END_REF][START_REF] Levine | Learning neural network policies with guided policy search under unknown dynamics[END_REF][START_REF] Levine | End-toend training of deep visuomotor policies[END_REF] which alternate between generating expert trajectories using trajectory optimization and improving the learned policy. In contrast, our policy search is guided by subgoals produced by a high-level policy.

Method

Our method builds on the following key observation. If an action a is well-suited for approaching an intermediate subgoal s g from state s, it should also be a good choice for approaching the final goal g of the same task. We assume that reaching subgoals s g is simpler than reaching more distant goals g. Hence, we adopt a self-supervised strategy and use the subgoal-reaching policy π(•|s, s g ) as a guidance when learning the goal-reaching policy π(•|s, g). We denote our approach as Reinforcement learning with Imagined Subgoals (RIS) and present its overview in Figures 1 and2.

To implement the idea of RIS, we first introduce a high-level policy π H predicting imagined subgoals s g , as described in Section 3.2. Section 3.3 presents the regularized learning of the target policy π using subgoals. The joint training of π and π H is summarized in Section 3.4. Before describing our technical contributions, we present the actor-critic paradigm used by RIS in Section 3.1 below.

Goal-Conditioned Actor-Critic

We consider a discounted, infinite-

V π defined as Q π (s, a, g) = E s0=s,a0=a,τ ∼d π (.|g) [ t γ t r(s t , a t , g)] and V π (s, g) = E a∼π(.|s,g) Q π (s, a, g).
In this work we assume states and goals to co-exist in the same space, i.e. S = G, where each state can be considered as a potential goal. Moreover, we set the reward r to -1 for all actions until the policy reaches the goal.

We follow the standard off-policy actor-critic paradigm [START_REF] Silver | Deterministic policy gradient algorithms[END_REF][START_REF] Heess | Learning continuous control policies by stochastic value gradients[END_REF][START_REF] Mnih | Asynchronous methods for deep reinforcement learning[END_REF][START_REF] Fujimoto | Addressing function approximation error in actor-critic methods[END_REF]Haarnoja et al., 2018a). Experience, consisting of single transition tuples (s t , a t , s t+1 , g), is collected by the policy in a replay buffer D. Actor-critic algorithms maximize return by alternating between policy evaluation and policy improvement. During the policy evaluation phase, a critic Q π (s, a, g) estimates the action-value

Q φ k+1 = arg min φ 1 2 E (st,at,st+1,g)∼D [y t -Q φ (s t , a t , g)] 2
(1) with the target value

y t = r(s t , a t , g) + γE at+1∼π(.|st,g) Q φ k (s t+1 , a t+1 , g).
During the policy improvement phase, the actor π is typically updated such that the expected value of the current Q-function Q π , or alternatively the advantage A π (s, a, g) = Q π (s, a, g) -V π (s, g), under π is maximized:

π θ k+1 = arg max θ E (s,g)∼D,a∼π θ (.|s,g) [Q π (s, a, g)]. (2)
Reaching distant goals using delayed rewards may require expensive policy search. To accelerate the training, we propose to direct the policy search towards intermediate subgoals of a task. Our method learns to predict appropriate subgoals by the high-level policy π H . The high-level policy is trained together with the policy π as explained below.

High-Level Policy

We would like to learn a high-level policy π H (.|s, g) that predicts an appropriate distribution of imagined subgoals s g conditioned on valid states s and goals g. Our high-level policy is defined in terms of the policy π and relies on the goal-reaching capabilities of π as described next.

Subgoal search with a value function. We note that our choice of the reward function r = -1 implies that the norm of the value function V π (s, g) corresponds to an estimate of the expected discounted number of steps required for the policy to reach the goal g from the current state s. We therefore propose to use |V π (s i , s j )| as a measure of the distance between any valid states s i and s j . Note that this measure depends on the policy π and evolves with the improvements of π during training.

Reaching imagined subgoals of a task should be easier than reaching the final goal. To leverage this assumption for policy learning, we need to find appropriate subgoals. In this work we propose to define subgoals s g as midpoints on the path from the current state s to the goal g, see Figure 3. More formally, we wish s g (i) to have equal distance from s and g, and (ii) to minimize the length of the paths from s to s g and from s g to g. We can find subgoals that satisfy these constraints by using our distance measure |V π (s i , s j )| and minimizing the following cost C π (s g |s, g)

C π (s g |s, g) = max (|V π (s, s g )|, |V π (s g , g)|) . (3)
However, naively minimizing the cost C π under the highlevel policy distribution, i.e.

π H k+1 = arg min π H E (s,g)∼D,sg∼π H (.|s,g) [C π (s g |s, g)], (4)
may lead to undesired solutions where the high-level policy samples subgoals outside the valid state distribution p s (.). Such predictions may, for example, correspond to unfeasible robot poses, unrealistic images, or other adversarial states which have low distance from s and g according to |V π | but are unreachable in practice.

Predicting valid subgoals. To avoid non-valid subgoals, we can additionally encourage the high-level policy to stay close to the valid state distribution p s (.) using the following KL-regularized objective:

π H k+1 = arg max π H E (s,g)∼D,sg∼π H (.|s,g) A π H k (s g |s, g) s.t. D KL π H (.|s, g) || p s (.) ≤ , (5)
where the advantage

A π H k (s g |s, g) = E ŝg∼π H k (.|s,g) [C π ( ŝg |s, g)] -C π (s g |s, g
) quantifies the quality of a subgoal s g against the high-level policy distribution. The Kullback-Leibler divergence term in (5) requires an esimate of the density p s (.). While estimating the unknown p s (.) might be challenging, we can obtain samples from this distribution, for example, by randomly sampling states from the replay buffer s g ∼ D.

We propose instead to implicitly enforce the KL constraint (5). We first note that the analytic solution to (5) can be obtained by enforcing the Karush-Kuhn-Tucker conditions, for which the Lagrangian is:

L(π H , λ) = E sg∼π(.|s,g) A π H k (s g |s, g) + λ ( -D KL (π(.|s, g) || p s (.))) .
The closed form solution to this problem is then given by: [START_REF] Peters | Relative entropy policy search[END_REF][START_REF] Rawlik | On stochastic optimal control and reinforcement learning by approximate inference[END_REF]Abdolmaleki et al., 2018b;a;Nair et al., 2020). We project this solution into the policy space by minimizing the forward KL divergence between our parametric high-level policy π H ψ and the optimal non parametric solution π H :

π H (s g |s, g) = 1 Z(s, g) p s (s g ) exp 1 λ A π H k (s g |s, g) (6) with the normalizing partition function Z(s, g) = p s (s g ) exp 1 λ A π H k (s g |s, g) ds g
π H ψ k+1 = arg min ψ E (s,g)∼D D KL π H (.|s, g) || π H ψ (.|s, g) = arg max ψ E (s,g)∼D,sg∼D log π H ψ (s g |s, g) 1 Z(s, g) exp 1 λ A π H k (s g |s, g) , (7)
where λ is a hyperparameter. Conveniently, this policy improvement step corresponds to a weighted maximum likelihood with subgoal candidates obtained from the replay buffer randomly sampled among states visited by the agent in previous episodes. The samples are re-weighted by their corresponding advantage, implicitly constraining the highlevel policy to stay close to the valid distribution of states.

A more detailed derivation is given in Appendix A.

Policy Improvement with Imagined Subgoals

Our method builds on the following key insight. If we assume s g to be an intermediate subgoal on the optimal path from s to g, then the optimal action for reaching g from s should be similar to the optimal action for reaching s g from s (see Figure 1). We can formalize this using a KL constraint on the policy distribution, conditioned on goals g and s g :

D KL (π(.|s, g) || π(.|s, s g )) ≤ .
We introduce the non-parametric prior policy π prior (.|s, g) as the distribution over actions that would be chosen by the policy π for reaching subgoals s g ∼ π H (.|s, g) provided by the high-level policy. Given a state s and a goal g, we bootstrap the behavior of the policy at subgoals s g ∼ π H (.|s, g) (see Figure 2):

π prior k (a|s, g) := E sg∼π H (.|s,g) [π θ k (a|s, s g )]. (8)
As we assume the subgoals to be easier to reach compared to reaching the final goals, this prior policy provides a good initial guess to constrain the policy search to the most promising actions.

We then propose to leverage a policy iteration scheme with additional KL constraint to shape the policy behavior accordingly. During the policy improvement step, in addition to maximizing the Q-function as in (2), we encourage the policy to stay close to the prior policy through the KLregularization:

π θ k+1 = arg max θ E (s,g)∼D E a∼π θ (.|s,g) Q π (s, a, g) -αD KL π θ (.|s, g) || π prior k (.|s, g) , (9)
where α is a hyperparameter.

In practice, we found that using an exponential moving average of the online policy parameters to construct the prior policy is necessary to ensure convergence:

θ k+1 = τ θ k + (1 -τ )θ k , τ ∈]0, 1[. ( 10
)
This ensures that the prior policy produces a more stable target for regularizing the online policy.

Algorithm

end for

We approximate the policy π θ , the Q-function Q φ and the high-level policy π H ψ with neural networks parametrized by θ, φ and ψ respectively, and train them jointly using stochastic gradient descent. The Q-function is trained to minimize the Bellman error (1), where we use an exponential moving average of the online Q-function parameters to compute the target value. The high-level policy is a probabilistic neural network whose output parametrizes a Laplace distribution with diagonal variance π H ψ (.|s, g) = Laplace(µ H ψ (s, g), Σ H ψ (s, g)) trained to minimize (7). The policy is also a probabilistic network parametrizing a squashed Gaussian distribution with diagonal variance π H ψ (.|s, g) = tanh N (µ θ (s, g), Σ θ (s, g)) trained to minimize (9). Finally we can approximate π prior using a Monte-Carlo estimate of (8).

The policy π and the high-level policy π H are trained jointly.

As the policy learns to reach more and more distant goals, its value function becomes a better estimate for the distance between states. This allows the high-level policy to propose more appropriate subgoals for a larger set of goals. In turn, as the high-level policy improves, imagined subgoals offer a more relevant supervision to shape the behavior of the policy. This virtuous cycle progressively extends the policy horizon further and further away, allowing more complex tasks to be solved by a single policy.

The full algorithm is summarized in Algorithm 1. We use hindsight experience replay [START_REF] Andrychowicz | Hindsight experience replay[END_REF] (HER) to improve learning from sparse rewards. Additional implementation details are given in Appendix B.

Experiments

In this section we first introduce our experimental setup in Section 4.1. Next, we ablate various design choices of our approach in Section 4.2. We, then, compare RIS to prior work in goal-conditioned reinforcement learning in Section 4.3.

Experimental Setup

Ant navigation. We evaluate RIS on a set of ant navigation tasks of increasing difficulty, each of which requires temporally extended reasoning. In these environments, the agent observes the joint angles, joint velocity, and center of mass of a quadruped ant robot navigating in a maze. We consider four different mazes: a U-shaped maze, a S-shaped maze, a Π-shaped maze and a ω-shaped maze illustrated in Figure 6. The obstacles are unknown to the agent.

During training, initial states and goals are uniformly sampled and the agents are trained to reach any goal in the environment. We evaluate agents in the most extended temporal settings representing the most difficult configurations offered by the environment (see Figure 6). We assess the success rate achieved by these agents, where we define success as the ant being sufficiently close to the goal position measured by x-y Euclidean distance.

Vision-based robotic manipulation. We follow the experimental setup in [START_REF] Nasiriany | Planning with goal-conditioned policies[END_REF] and also consider a vision-based robotic manipulation task where an agent controls a 2 DoF robotic arm from image input and must manipulate a puck positioned on the table (Figure 8a). We define success as the arm and the puck being sufficiently close to their respective desired positions. During training, the initial arm and puck positions and their respective desired positions are uniformly sampled whereas, at test time, we evaluate agents on temporally extended configurations.

These tasks are challenging because they require temporally extended reasoning on top of complex motor control. Indeed, a greedy path towards the goal cannot solve these tasks. We train the agents for 1 million environment steps and average the results over 4 random seeds. Additional details about the environments are given in Appendix C.

Alternative methods. We compare our approach, RIS, to off-policy reinforcement learning methods for goal-reaching tasks. We consider Soft Actor-Critic (SAC) (Haarnoja et al., 2018a) with HER, which trains a policy from scratch by maximizing the entropy regularized objective using the same sparse reward as ours. We also compare to Temporal Difference Models (TDM) [START_REF] Pong | Temporal difference models: Model-free deep RL for model-based control[END_REF] which trains horizon-aware policies operating under dense rewards in the form of distance to the goal. We chose to evaluate TDMs with a long policy horizon of 600 steps due to the complexity of considered tasks. Furthermore, we compare to Latent Embeddings for Abstracted Planning (LEAP) [START_REF] Nasiriany | Planning with goal-conditioned policies[END_REF], a competitive approach for these environments, which uses a sequence of subgoals that a TDM policy must reach one after the other during inference.

We re-implemented SAC, TDM and LEAP and validated our implementations on the U-shaped ant maze and visionbased robotic manipulation environments.

On the U-shaped Ant maze environment, we additionally report results of HIRO [START_REF] Nachum | Data-efficient hierarchical reinforcement learning[END_REF], a hierarchical reinforcement learning method with off-policy correction, after 1 million environment steps. The results were copied from Figure 12 in [START_REF] Nasiriany | Planning with goal-conditioned policies[END_REF].

We provide additional details about the hyperparameters used in our experiments in Appendix D.

Ablative Analysis

We use the Ant U-maze navigation task to conduct ablation studies to validate the role of our design choices.

Evaluating imagined subgoals. To evaluate the quality of the subgoals predicted by our high-level policy, we intro-duce an oracle subgoal sampling procedure. We plan an oracle trajectory, which corresponds to a point-mass agent navigating in this maze and does not necessarily correspond to the optimal trajectory of an ant. Oracle subgoals correspond to the midpoint of this trajectory between state and goal in x-y location (Figure 4 left).

Figure 4 (left) shows the subgoal distribution predicted by a fully-trained high-level policy for a state and goal pair located at opposite sides of the U-shaped maze. We can observe that its probability mass is close to the oracle subgoal.

To quantitatively evaluate the quality of imagined subgoals, we measure the x-y Euclidean distance between oracle subgoals and subgoals sampled from the high-level policy throughout training for a set of fixed state and goal tuples randomly sampled in the environment. Figure 4 (right)

shows that RIS successfully learns to find subgoals that are coherent with the oracle trajectory during training, despite not having prior knowledge about the environment.

We also assess the importance of using the implicit regularization scheme presented in Section 3.2 which discourages high-level policy predictions to lie outside of the distribution of valid states. We compare our approach against naively optimizing subgoals without regularization (i.e. directly optimize (4)). Figure 4 (right) shows that without implicit regularization, the predicted subgoals significantly diverge from oracle subgoals in x-y location during training. As result, imagined subgoals are not able to properly guide policy learning to solve the task, see Figure 5.

Prior policy with imagined subgoals. We evaluate the importance of incorporating imagined subgoals into the prior policy by comparing to a number of variants. To disentangle the effects of imagined subgoals from the actorcritic architecture used by RIS, we first replace our prior policy with simpler choices of prior distributions that do not incorporate any subgoals: (i) a uniform prior over the actions π prior k = U(A), which is equivalent to SAC without entropy regularization during policy evaluation, and (ii) a parametric prior policy that uses an exponential moving average of the online policy weights π prior k = π θ k . Figure 5 shows that, while they can learn goal-reaching behaviors on many configurations encountered during training (left), neither of these variants are able to solve the Ant U-maze environment in its most difficult setting (right). We also observe that the agent with a moving average action prior fails to learn (left). This highlights the benefits of incorporating subgoals into policy learning.

Finally, we propose to incorporate the oracle subgoals into our prior policy. We replace the subgoal distributions predicted by our high-level policy with Laplace distributions centered around oracle subgoals. Results in Figure 5 show that RIS with oracle subgoals learns to solve the U-shaped ant maze environment faster than using a high-level policy simultaneously trained by the agent. This experiment highlights the efficiency of our approach to guide policy learning with appropriate subgoals: if we have access to proper subgoals right from the beginning of the training, our approach could leverage them to learn even faster. However, such subgoals are generally not readily available without prior knowledge about the environment. Thus, we introduce a high-level policy training procedure which determines appropriate subgoals without any supervision.

Comparison to the State of the Art

Ant navigation. Figure 6 compares RIS to the alternative methods introduced in section 4.1 for the four ant navigation environments. For all considered mazes RIS significantly outperforms prior methods in terms of sample efficiency, often requiring less than 500 thousand environment interactions to solve the mazes in their most challenging initial state and goal configurations.

LEAP makes progress on these navigation tasks, but requires significantly more environment interactions. This comparison shows the effectiveness of our approach, which uses subgoals to guide the policy rather than reaching them sequentially as done by LEAP. While SAC manages to learn goal-reaching behaviors, as we will see later in Figure 7, it fails to solve the environments in their most challenging configurations. The comparison to SAC highlights the benefits of using our informed prior policy compared to methods assuming a uniform action prior. On the U-shaped maze environment, HIRO similarly fails to solve the task within one million environment interactions. Furthermore, we observe that TDMs fails to learn due to the sparsity of the reward.

Figure 7 evaluates how SAC, LEAP and RIS perform for varying task horizons in the S-shaped and ω-shaped mazes. Starting from an initial state located at the edge of the mazes, we sample goals at locations which require an increasing number of environment steps to be reached. Figure 7 reports results for RIS, LEAP and SAC after having been trained for 1 million steps. While the performances of LEAP and SAC degrades as the planning horizon increases, RIS consistently solves configurations of increasing complexity.

These results demonstrate that RIS manages to solve complex navigation tasks despite relying on a flat policy at inference. In contrast, LEAP performs less well, despite a significantly more expensive planning of subgoals during inference. Vision-based robotic manipulation. While the ant navigation experiments demonstrate the performances of RIS on environments with low-dimension state spaces, we also show how our method can be applied to vision-based robotic manipulation tasks. Our approach takes images of the current and desired configurations as input. Input images are passed through an image encoder, a convolutional neural network shared between the policy, high-level policy and Q-function. The encoder is only updated when training the Q-function during policy evaluation and is fixed otherwise during policy improvement and high-level policy improvement. Instead of generating subgoals in the highdimensional image space, the high-level policy therefore operates in the learned compact image representation of the encoder. Following recent works on reinforcement learning from images, we augment image observations with random translations [START_REF] Kostrikov | Image augmentation is all you need: Regularizing deep reinforcement learning from pixels[END_REF][START_REF] Laskin | Reinforcement learning with augmented data[END_REF]. We found that using such data augmentation was important for training image-based RIS and SAC policies. Moreover, we found that using a lower learning rate for the policy was necessary to stabilize training. Additional implementation details on the image encoding are given in Appendix B.

We compare our approach against LEAP and SAC in Figure 8b. RIS achieves a higher success rate than LEAP whereas SAC fails most of the time to solve the manipulation task consistently enough in the temporally extended configuration used for evaluation on the vision-based robotic manipulation task. Moreover, RIS and SAC only requires a single forward pass through their image encoder and actor network at each time step when interacting with the environment, whereas LEAP depends in addition upon an expensive planning of image subgoals.

Figure 9 visualizes the imagined subgoals of the high-level policy. Once the RIS agent is fully trained, we separately train a decoder to reconstruct image observations from their learned representations. Given observations of the current state and the desired goal, we then predict the representation of an imagined subgoal with the high-level policy and generate the corresponding image using the decoder. Figure 9 shows that subgoals predicted by the high-level policy are natural intermediate states halfway to the desired goal on this manipulation task. For example, for the test configuration (Figure 9 top), the high-level policy prediction corresponds to a configuration where the arm has reached the right side of the puck and is pushing it towards its desired position.

Additional reconstructions of imagined subgoals for different initial state and goal configurations in the robotic manipulation environment are given in Appendix E.

Conclusion

We introduced RIS, a goal-conditioned reinforcement learning method that imagines possible subgoals in a selfsupervised fashion and uses them to facilitate training. We propose to use the value function of the goal-reaching policy to train a high-level policy operating in the state space. We then use imagined subgoals to define a prior policy and incorporate this prior into policy learning. Experimental results on challenging simulated navigation and vision-based manipulation environments show that our proposed method greatly accelerates learning of temporally extended tasks and outperforms competing approaches.

While our approach makes use of subgoals to facilitate policy search, future work could explore how to use them to obtain better Q-value estimates. Future work could also improve exploration by using imagined subgoals to encourage the policy to visit all potential states.

A. High-level Policy Derivation

The following derivation is similar to (Abdolmaleki et al., 2018b) and (Nair et al., 2020). We consider the subgoal advantage function A π H , some distribution over valid states p s (s) and the distribution over states and goals µ(s, g) given by previously collected experience and experience relabelling. During high-level policy improvement, we maximize the following objective function, where expectations have been replaced by integrals:

π H k+1 =
Differentiating with respect to π H yields

∂L ∂π H = A π H (s g |s, g) -λ log π H (s g |s, g) + λ log p s (s g ) + η -λ. (13)
Setting this expression to zero, we get π H (s g |s, g) = p s (s g ) exp

A π H (s g |s, g) λ exp - λ -η λ . ( 14
)
As the second constraint in (11) must sum to 1, the last exponential is a normalizing factor. This gives the closed form solution:

π H (s g |s, g) = 1 Z(s, g) p s (s g ) exp A π H (s g |s, g) λ (15)
with the normalizing partition function

Z(s, g) = p s (s g ) exp 1 λ A π H (s g |s, g) ds g . (16)
We next project the closed form solution into the space of parametric policies by minimizing the reverse KL divergence between our parametric high-level policy π H ψ and the optimal non-parametric solution π H :

π H ψ k+1 = arg min ψ E (s,g)∼µ(.) D KL π H (.|s, g) || π H ψ (.|s, g) = arg max ψ E (s,g)∼µ(.) E sg∼π H (.|s,g) log π H ψ (s g |s, g) = arg max ψ E (s,g)∼µ(.),sg∼ps(.) log π H ψ (s g |s, g) 1 Z(s, g) exp 1 λ A π H (s g |s, g) (17)
We choose p s to be the distribution of states given by experience collected in the replay buffer D, such that high-level policy improvement corresponds to a weighted maximum-likelihood where subgoal candidates s g are randomly sampled from D among states visited by the agent in previous episodes.

B. Implementation Details

Actor-Critic. Our implementation of the actor-critic algorithm is based on Soft Actor-Critic (Haarnoja et al., 2018b), where we remove the entropy term during policy evaluation and replace the entropy term by the KL divergence between policy and our prior policy during policy improvement. The policy is a neural network that parametrizes the mean and diagonal covariance matrix of a squashed Gaussian distribution π θ (.|s, g) = tanh N (µ θ (s, g), Σ θ (s, g)). We train two seperate Q-networks with target networks and take the minimum over the two target values to compute the bootstrap value.

The target networks are updated using an exponential moving average of the online Q parameters:

φ k+1 = τ φ k + (1 -τ )φ k .
High-level policy training. The high-level policy is a neural network that outputs the mean and diagonal covariance matrix of a Laplace distribution π H ψ (.|s, g) = Laplace(µ ψ (s, g), Σ ψ (s, g)). Following (Nair et al., 2020), instead of estimating the normalizing factor Z(s, g) in ( 17), we found that computing the weights as softmax of the advantages over the batch leads to good results in practice. During the high-level policy improvement, we found that clipping the value function between -100 and 0, which corresponds to the expected bounds given our choice of reward function and discount factor, stabilizes the training slightly.

KL divergence estimation. We use an exponentially moving average of the policy weights instead of the weights of the current policy to construct the prior policy π prior : θ k+1 = τ θ k + (1 -τ )θ k with the same smoothing coefficient τ as the one used for the Q function. We estimate the prior density using the following Monte-Carlo estimate:

log π prior (a|s, g) ≈ log 1 I i π θ (a|s, s i g ) + , (s i g ) ∼ π H ψ (.|s, g), (18)
where > 0 is a small constant to avoid large negative values of the prior log-density. We use I = 10 samples to estimate π prior (a|s, g). We also use a Monte-Carlo approximation to estimate the KL-divergence term in Equation ( 9) of the submission:

D KL π θ (.|s, g) || π prior (.|s, g) = E a∼π(.|s,g) [log π θ (a|s, g) -log π prior (a|s, g)] ≈ 1 N n log π θ (a n |s, g) -log π prior (a n |s, g)
with (a n ) n=1,..,N ∼ π θ (.|s, g).

(

) 19
Following SAC (Haarnoja et al., 2018a), we use N = 1, plug the estimate (18) and use the reparametrization trick to backpropagate the KL divergence term to the policy weights (Haarnoja et al., 2018a).

Experience relabelling. In all of our experiments we use Hindsight Experience Replay [START_REF] Andrychowicz | Hindsight experience replay[END_REF]. We use the same relabelling strategy as [START_REF] Nair | Visual reinforcement learning with imagined goals[END_REF] and [START_REF] Nasiriany | Planning with goal-conditioned policies[END_REF] and relabel the goals in our minibatches as follows:

• 20%: original goals from collected trajectories, • 40%: randomly sampled states from the replay buffer, trajectories, • 40%: future states along the same collected trajectory.

Vision based environments On the vision-based robotic manipulation tasks, input images are passed through an image encoder shared between the policy, high-level policy and Q-function. Both states, goals and subgoals are encoded using the same encoder network. The encoder is updated during policy evaluation, where we only update the representation of the current state images whereas the representations of desired goal images, next state images and subgoal image candidates are kept fixed. We augment the observations with random translations by translating the 84 × 84 image within a 100 × 100 empty frame [START_REF] Laskin | Reinforcement learning with augmented data[END_REF][START_REF] Kostrikov | Image augmentation is all you need: Regularizing deep reinforcement learning from pixels[END_REF].

C. Environments

We adopt Ant Navigation environments provided by the code repository of [START_REF] Nasiriany | Planning with goal-conditioned policies[END_REF]. In these environments, a 4-legged ant robot must learn to navigate in various mazes. The state includes the position, orientation, the joint angles and the velocities of these components. The ant has a radius of roughly 0.75 units. We consider that the goal is reached if the x-y position of the ant is within 0.5 units of its desired location in Euclidean distance. The agent receives a reward r(s, a, g) = -1 for all actions until the goal is reached. The dimensions of the space for the U-shaped maze are 7.5 × 18 units. For the S-shaped maze, the dimensions are 12 × 12. For the Π-shaped and ω-shaped mazes, the dimensions are 16 × 16 units. The walls are 1.5 units thick. During training, initial states and goals are uniformly sampled anywhere in the empty space of the environment. At test time, we evaluate the agent on challenging configurations that require temporally extended reasoning, as illustrated in Figure 6 of the submission.

For the robotic manipulation task, we use the same image-based environment as in [START_REF] Nasiriany | Planning with goal-conditioned policies[END_REF]. In this task, the agent operates an arm robot via 2D position control and must manipulate a puck. The agent observes a 84 × 84 RGB image showing a top-down view of the scene. The dimension of the workspace are 40cm × 20cm and the puck has a radius of 4cm.

We consider that the goal is achieved if both the arm and the puck are within 5cm of their respective target positions. During training, the initial arm and puck positions and their respective desired positions are uniformly sampled in the workspace.

At test time, we evaluate the policy on a hard configuration which requires temporally extended reasoning: the robot must reach across the table to a corner where the puck is located, move its arm around the puck, pull the puck to a different corner of the table, and reach again the opposite corner.

D. Hyperparameters

Table 1 lists the hyperparameters used for the RIS. We use Adam optimizer and report results after one million interactions with the environment. For SAC, following (Haarnoja et al., 2018b), we automatically tune the entropy of the policy to match the target entropy ofdim(A). 1 × 10 -4 Critic learning rate 1 × 10 -3 1 × 10 -3 Policy learning rates 1 × 10 -3 1 × 10 -4 High-level policy learning rate 1 × 10 -4 1 × 10 -4 α 0.1 0.1 λ 0.1 0.1

In the vision based environment, our image encoder is a serie of convolutional layers with kernel sizes [3,3,3,3], strides [2, 2, 2, 1], channel sizes [32,32,32,32] and ReLU activation functions followed by a fully-connected layer with output dimension 16. For LEAP, we re-implemented [START_REF] Nasiriany | Planning with goal-conditioned policies[END_REF] and train TDM [START_REF] Pong | Temporal difference models: Model-free deep RL for model-based control[END_REF] policies and Q networks with hidden layers of size [400,300] and ReLU activation functions. In the ant navigation environments, we pretrain VAEs with mean squared reconstruction error loss and hidden layers of size [64,128,64], ReLU activation functions and representation

  Proceedings of the 38 th International Conference on Machine Learning, PMLR 139, 2021. Copyright 2021 by the author(s).

Figure 1 .

 1 Figure 1. Illustration of the KL-regularized policy learning using imagined subgoals. (Left): The policy fails to reach a distant goal, yet it can reach a closer subgoal. Our approach automatically generates imagined subgoals for a task and uses such subgoals to direct the policy search during training. (Right): At test time, the resulting flat policy can reach arbitrarily distant goals without relying on subgoals.

Figure 3 .

 3 Figure3. Given initial states s and goal states g, our subgoals are states on the middle of the path from s to g. We measure distances between states by the value function |V π (s1, s2)| corresponding to the current policy π. We obtain a distribution of subgoals from the high-level policy sg ∼ π H (.|s, g). We use subgoals only at the training to regularize and accelerate the policy search.

Figure 4 .

 4 Figure 4. (Left) Heatmap of the subgoal distribution obtained with our high-level policy and the oracle subgoal for a given state and goal for the ant U-maze environment. (Right) Distance between oracle subgoals and subgoals predicted by the high-level policy for RIS and RIS without implicit regularization. The dimensions of the space are 7.5 × 18 units and the ant has a radius of roughly 0.75 units.

Figure 5 .

 5 Figure5. Ablation of our method on the Ant U-Maze environment: simple priors that do not incorporate subgoals (uniform prior, moving average prior); ignoring the effect of out-of-distribution subgoal predictions (no implicit regularization); and using oracle subgoals (with oracle subgoals). Left: success rate on all configurations throughout training. Right: success rate on the test configurations.

Figure 6 .

 6 Figure 6. Comparison of RIS to several state-of-the-art methods (bottom row) on 4 different ant navigation tasks. We evaluate the success rate of the agent on the challenging configurations illustrates in the top row, where the ant is located at the initial state and the desired goal location is represented by a cyan sphere.

Figure 7 .

 7 Figure 7. Comparison of different methods for increasingly more difficult tasks on the S-shaped and ω-shaped ant maze. The goals with increasing complexity are numbered starting with 1, where 1 is the closest goal.

Figure 8 .

 8 Figure 8. Robotic manipulation environment: (a) illustration of the task; (b) results of our method compared to LEAP and SAC.

Figure 9 .

 9 Figure 9. Image reconstruction of an imagined subgoal (middle) given the current state (left) and the desired goal (right) on a temporally extended configuration used for evaluation (top) and a random configuration (bottom).

  Update π θ using Eq. 9 (Policy Improvement with Imagined

	Subgoals)

Summary Algorithm 1 RL with imagined subgoals Initialize replay buffer D Initialize Q φ , π θ , π H ψ for k = 1, 2, ... do Collect experience in D using π θ in the environment Sample batch (s t , a t , r t , s t+1 , g) ∼ D with HER Sample batch of subgoal candidates s g ∼ D Update Q φ using Eq. 1 (Policy Evaluation) Update π H ψ Using Eq. 7 (High-Level Policy Improvement)

  Zhang, L., Yang, G., and Stadie, B. C. World model as a graph: Learning latent landmarks for planning. arXiv preprint arXiv:2011.12491, 2020. Zhao, R., Sun, X., and Tresp, V. Maximum entropyregularized multi-goal reinforcement learning. In International Conference on Machine Learning, 2019.

  H (s g |s, g)ds g dsdg .

		arg max π	µ(s, g) π H (s g |s, g)A π H	(s g |s, g)ds g dsdg	(11)
	s.t.	µ(s, g)D KL π H (.|s, g) || p s (.) dsdg ≤ ,	µ(s, g) π H (s g |s, g)ds g dsdg = 1
	The Lagrangian is:
		L(π H , λ, η) =	µ(s, g) π H (s g |s, g)A π H	(s g |s, g)ds g dsdg
		+ λ	-	µ(s, g) π H (s g |s, g) log	π H (s g |s, g) p s (s g )	ds g dsdg
		+ η 1 -	µ(s, g) π

Table 1 .

 1 Hyper-parameters for RIS and SAC.

	Hyper-parameter	Ant Navigation Robotic Manipulation
	Q hidden sizes	[256, 256]	[256, 256]
	Policy hidden sizes	[256, 256]	[256, 256]
	High-level policy hidden sizes	[256, 256]	[256, 256]
	Hidden activation functions	ReLU	ReLU
	Batch size	2048	256
	Training batches per environment step 1	1
	Replay buffer size	1 × 10 6	1 × 10 5
	Discount factor γ	0.99	0.99
	polyak for target networks τ	5 × 10 -3	5 × 10 -3
		1 × 10 -16

Table 2 .

 2 Environment specific hyper-parameters for LEAP Hyperparameter U-shaped maze S-shaped maze Π-shaped maze ω-shaped Maze Robotic Manipulation

	TDM policy horizon 50	50	75	100	25
	Number of subgoals 11	11	11	11	3

Inria, École normale suprieure, CNRS, PSL Research University, 75005 Paris, France. Correspondence to: Elliot Chane-Sane <elliot.chane-sane@inria.fr>.

Code is available on the project webpage https://www. di.ens.fr/willow/research/ris/.

Acknowledgements

This work was funded in part by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d'avenir" program, reference ANR19-P3IA-0001 (PRAIRIE 3IA Institute) and by Louis Vuitton ENS Chair on Artificial Intelligence.

size of 8 for the encoders and the decoders. In the vision based robotic manipulation environment, we pretrain VAEs with mean squared error reconstruction loss and convolutional layers with encoder kernel of sizes [5,5,5], encoder strides of sizes [3,3,3], encoder channels of sizes [16,16,32], decoder kernel sizes of sizes [5,6,6], decoder strides of sizes [3, 3, 3], and decoder channels of sizes [32,32,16], representation size of 16 and ReLU activation functions. Table 2 reports the policy horizon used for each environment as well as the number of subgoals in the test configuration for the results in Figure 6 of the submission. For the results presented in Figure 7 of the submission, we adapted the number of subgoals according to the difficulty of each configuration.

E. Additional Results

In Figure 10, we provide image reconstructions of imagined subgoals on additional configurations of the vision-based robotic manipulation environment.


Once upon a time in micrometres… tools, activities and living spaces during

In 1964, the English translation of Sergei Semenov's pioneering technique of analysis of the microscopic wear marks on ancient tools, first published in Russian in 1957, made the diffusion of his work extremely rapid. Since the 1980's, this technique is in the mainstream of research on prehistoric stone tools. In the past twenty-five years, studies have been carried out on lithic and bone tools from three sites in Cyprus, dated to the Pre-pottery Neolithic, from the end of the 10 th millennium BC to the mid-6 th millennium BC. These sites are Ayios Tychonas-Klimonas, Parekklisha-Shillourokambos and Khirokitia-Vouni. Use-wear studies showed that these implements were involved in a variety of subsistence and craft activities. The relations between the modes of production and the functions of the tools were also addressed. At Khirokitia, the excavation and recording methods provide an opportunity to study the spatial organization of technical activities and gain insights into Neolithic daily life.

Text

Lithic tools responded to numerous needs in ancient societies, as they were employed for different activities related to subsistence and craft production. Following the English translation in 1964 of Sergei Semenov's 'Prehistoric Technology', use-wear analysis developed worldwide (Longo and Skakun 2005). Semenov's methodology is based on the observation of wear (scaling, striations, smoothing, and polish) with the naked eye and at various magnifications (up to 500X) and their interpretation in terms of cinematics and worked materials. These marks are interpreted by analogy with ethnographic examples of tool use and experiments taking into account the environmental and technological settings of the prehistoric tools studied. Physical methods (SEM, confocal microscopy, rugosimetry, tribology, etc., [START_REF] Anderson | Contribution of quantitative analysis of surface states to a multi-method approach for characterising plant-processing traces on flint tools with gloss[END_REF], 2006[START_REF] Astruc | Wear assesments of prehistoric instruments[END_REF][START_REF] Ibáñez | Cereal cultivation and domestication as shown by microtexture analysis of sickle gloss through confocal microscopy[END_REF]) are used to characterise tool wear. On macro-and microscopic wear, one should notably mention the studies of [START_REF] Keeley | Experimental Determination of Stone Tool Uses. A Microwear Analysis[END_REF], [START_REF] Anderson-Gerfaud | Contribution méthodologique à l'analyse des microtraces d'utilisation sur les outils préhistoriques[END_REF], [START_REF] Plisson | Étude fonctionnelle d'outillages lithiques préhistoriques par l'analyse des micro-usures : recherche méthodologique et archéologique[END_REF], [START_REF] Caspar | Contribution à la tracéologie de l'industrie lithique du Néolithique ancien de l'Europe nord-occidentale[END_REF], [START_REF] Van Gijn | The wear and tear of flint. Principles of functional analysis applied to dutch neolithic assemblages[END_REF], 2010), González [START_REF] González Urquijo | Metodogia de analisis funcional de instrumentos tallados en silex[END_REF], [START_REF] Gassin | Évolution socio-économique dans le Chasséen de la grotte de l'Église supérieure (Var). Apport de l'analyse fonctionnelle des industries lithiques[END_REF], Astruc 2002, Beyries and[START_REF] Beyries | The contribution of ethnoarchaeologic macro-and microscopic wear traces to the understanding of archaeological hide-working processes[END_REF]. Researchers have illustrated and clarified the link between stone production and human behaviour, and the reconstruction of technological developments. Artefacts are considered to be the results of technological, economic and social choices within the frame of cultural traditions. In more recent years, several colloquia offered updates, providing a 'status quo of the discipline' [START_REF] Longo | Prehistoric Technology' 40 Years Later: Functional Studies and the Russian Legacy[END_REF], Marreiros et al. 2012, 2014). Meanwhile, a special issue of the Journal of Archaeological Science [START_REF] Evans | Standardization, calibration and innovation: a special issue on lithic microwear method[END_REF]) considers future directions in lithic microwear analysis, emphasizing the search for methodological refinements to increase the reliability of results.

The aim of this paper is to present an overview of the lithic use-wear studies conducted on several sites covering a long period, the Pre-pottery Neolithic of Cyprus [START_REF] Briois | L'industrie en obsidienne de la phase ancienne du secteur 1[END_REF][START_REF] Briois | L'outillage de pierre taillée à Chypre du X e au milieu du VI e millénaire avant notre ère : une évocation[END_REF]2019). These sites are of Klimonas (8900-8600 cal. BC, Astruc et The Amathus region is a vast territory located east of Limassol in southern Cyprus, between the foothills of the Troodos Mountains and the coastal lowlands. An intensive survey was carried out and revealed a high density of Neolithic sites [START_REF] Briois | Histoire des campagnes d'Amathonte, I. L'occupation du sol au Néolithique[END_REF]. Two settlements, Shillourokambos and Klimonas, the former excavated between 1992 and 2004 and the latter under excavation since 2011, have shed light on the early stages of the Neolithic of Cyprus and its long-term developments. The very abundant lithic assemblages, collected and dated thanks to detailed chrono-stratigraphic studies, illustrate the evolution of lithic industries over more than two millennia.

Klimonas [START_REF] Vigne | Klimonas, a late PPNA hunter-cultivator village in Cyprus. New results[END_REF] together with two other sites, Ayios Tychonas-Throumbovounos in the Amathus region and Ayia Varvara-Asprokremnoson on the foothills of the central Troodos massif, define the earliest Pre-Pottery Neolithic phase, or Cypro-PPNA. The village is made of a dense network of oval houses and a communal building. So far, our sample shows no difference between the material of this building and the houses. Stone tools were used in various tasks: hunting; cereal harvesting; animal butchery; wood, plant, bone and hide scraping; wood, plant and rock cutting; and wood, stone and shell piercing (Figure 1). As regards lithic weapons, tanged pieces are of diverse forms and sizes. Since some of them bear impact fractures, they were interpreted as projectile points used for hunting. The faunal evidence has shown that the inhabitants of Klimonas hunted wild boars. They also cultivated emmer wheat harvested with stone tools. Sickle elements varied in shape and size. They were used unmodified or shaped by retouch (inverse, bifacial retouch or backs). The cutting edge tools were sometimes rejuvenated by microdenticulation. The majority of the blanks were fixed longitudinally onto a wooden haft. Butchering tools are poorly documented in our sample.

Heavy butchering tools (i.e. disarticulation and percussion) are absent. On the contrary, blanks used for meat cutting and filleting were identified. Small scale working of animal, vegetal and mineral materials are also well represented. Among them, the working of plant material is best attested, this material being used to manufacture objects. Wood, stone and shell boring are probably mostly related to the production of beads and pendants.

Three main, successive, phases of occupation were defined at Shillourokambos (Guilaine et al.

2011

). The early phase is dated 8600-7600 cal. BC, the middle 7500-7200 cal. BC, and the late 7200-6900 cal. BC. The site is mainly characterised by hollowed structures such as a large enclosure, post-holes and wells. A well was used as a collective grave. Use-wear analysis was conducted for the early and the middle phases. A small sample of flints tools from the early phase highlights the fact they were employed in various tasks, which included cereal harvesting, hunting, plant and wood processing, butchery, hide and stone working [START_REF] Philibert | Premières approches fonctionnelles des outillages lithiques de Shillourokambos (Parekklisha, Chypre). Les phases anciennes du pré-céramique, IXe-VIIIe millénaire cal. BC[END_REF][START_REF] Philibert | Approche fonctionnelle des outillages en pierre taillée[END_REF].

The importation of Anatolian obsidian is another characteristic feature of this phase. Obsidian came from the Kömürcü-Kaletepe source in Central Anatolia [START_REF] Briois | L'industrie en obsidienne de la phase ancienne du secteur 1[END_REF]. Analysis of usewear traces is rarely applied to obsidian tools. At Shillourokambos, these marks showed that imported obsidian was used in longitudinal motions to cut soft materials, mainly meat and hide.

It was also employed in plant processing. Transverse motions on the same materials were also identified. Two obsidian tools were used to harvest cereals. They were hafted longitudinally, just like their counterparts made from flint [START_REF] Astruc | Du Göllüdağ à Shillourokambos. De l'utilisation d'obsidiennes Anatoliennes en contexte insulaire[END_REF].

The toolkit of the middle phase consists of numerous retouched blades, end-scrapers, pièces esquillées, burins, backs, truncations and blades with gloss. Rare projectile points are present, including stemmed, rhombic and oval types. Arrowheads were not included in the use-wear sample, but other parts of the toolkit, both retouched and unretouched, were. The glossy pieces correspond to cereal harvesting. This activity was done with inserts hafted longitudinally and used on one, and, more rarely, two edges. Other kinds of silica-rich plants were processed using longitudinal or transverse motions. Scrapers were used to work either hide or vegetal materials, and burins to scrape and or incise plants, wood and bone. Unretouched blanks were also used for different types of activity, including vegetal and animal processing (Astruc forthcoming a).

The late phase of the Pre-pottery Neolithic in Cyprus is named Khirokitian after the site where it was identified. It is well documented by the extensive excavations conducted between 1976 and 2009 [START_REF] Le Brun | Fouilles récentes à Khirokitia (Chypre), 1977-1981[END_REF][START_REF] Le Brun | Fouilles récentes à Khirokitia (Chypre) 1983-1986[END_REF][START_REF] Le Brun | Fouilles récentes à Khirokitia (Chypre) 1988-1991[END_REF], Le Brun et al. 2017, Le Brun 2017, Le Brun forthcoming).

The Neolithic village, located in the Larnaca district in the coastal lowlands, consists of circular houses built around small exterior spaces. Twelve architectural levels were identified in the main excavation area: levels G to A and levels III to I. The village was surrounded by successive walls. Lithic tools are an important component of the material culture found in all excavated spaces [START_REF] Astruc | L'outillage lithique taillé de Khirokitia[END_REF]. These artefacts were used in various activities, mainly cereal harvesting, working wood and other plant materials, and, to a lesser extent, small butchery and skin, bone and stone working. Cereal harvesting was made using sickles composed of a wooden or antler haft and lithic elements fixed longitudinally (Figure 2). The plants were cut close to the soil, with a movement similar to the one traditionally used with metal sickles. Tools used to cut, saw or scrape wood and reeds were identified, and can be associated with the manufacture of objects such as hafts, tools, vessels, baskets and cloths. Arrowheads were not found at the site. Fallow dear was the only hunted animal and was relatively easy to tame and keep in enclosures. We have several tools used in small butchery. No large-scale butchery was identified. Several instruments used to scrape and cut bones were in all likelihood employed to manufacture tools, which represent the majority of the bone artefacts found at the site. Points, awls and needles were the most frequent bone tools. A small number of cutting-edge implements were found.

They were used to work bark, wood, soft and rigid vegetal materials as well as skins and leather (Legrand 2003[START_REF] Legrand | New Evidence on the Bone Reduction Techniques from Khirokitia -Cyprus (7 th millennium cal. B.C.)[END_REF][START_REF] Legrand | Fabrication et utilisation de l'outillage en matières osseuses du Néolithique de Chypre : Khirokitia et Cap Andreas-Kastros[END_REF], Legrand-Pineau 2009, 2010, forthcoming). These tools were probably employed for basketry, and, for instance sewing and seaming clothes. We also identified tools related to an activity that is emblematic of this Neolithic period, the use of limestone, diabase and picrolite to make vessels, engraved pebbles, mace-heads, beads, pendants and figurines (Astruc el al. 2008, Astruc forthcoming b). A careful experimental program [START_REF] Astruc | L'artisanat lié à la transformation des matières minérales : approche expérimentale[END_REF]) was conducted to identify the wear developed on stone-working tools made from cherts at Khirokitia [START_REF] Astruc | L'artisanat lié à la transformation des matières minérales : approche expérimentale[END_REF][START_REF] Astruc | L'outillage lithique taillé de Khirokitia[END_REF]. Tribology (i.e. the science and engineering of interacting surfaces in relative motion, [START_REF] Anderson | Contribution of quantitative analysis of surface states to a multi-method approach for characterising plant-processing traces on flint tools with gloss[END_REF]2006) offers insights into the mechanisms of wear of the tools [START_REF] Astruc | Wear assesments of prehistoric instruments[END_REF]. Using scratch tests and friction experiments in laboratory, 3D images and 3D statistical parameters, quantitative and qualitative analyses of the surface states of the cherts were carried out. The contact between the chert from the Lefkara formation, located near the Neolithic settlement, and diabase and picrolite, demonstrated two different processes of wear: adhesive wear for picrolite and abrasive wear for diabase. Moreover, the understanding of the mechanisms of wear validated the potential of standard use-wear analysis. The technical operations recognised are sawing, engraving, boring, picking and abrading of mineral materials.

At Khirokitia, the village and the excavation and recording methods permit spatial analyses of the artefact assemblages. The settlement consists in several dwellings (circular structures) erected around an external space. Circulation lanes are also apparent and a way out, set in one of the village surrounding walls, was identified. Fragmentary objects and incomplete technical sequences show that floors were frequently cleaned. Artefacts are more common in exterior spaces than in the dwellings, and the daily activities were mainly performed outdoors.

Nevertheless, the interior spaces appear complementary to the external ones: their functions are similar. The same activities were identified in both interior and exterior spaces. Stone knapping and vegetal processing were the most common ones. We have fewer indications for other activities, but they do not seem to be associated with one dwelling or another, or with one external space or another. There is only one exception: the location of tools used in stone working. Tools employed to incise diabase and saw limestone and an unused picking tool were found on the floor of a house (S.122, level C). This dwelling had a long duration (level E through B) and was continuously related to stone-working, as evidenced by vessel rough-outs and tools. A cache in one of the small post-holes contained picrolite pebbles stocked for bead or pendant manufacture. Several tombs containing stone vessels were found under successive floors of the house.

The organisation of stone working, an important component of insular cultural identity, could be evidenced in 2002 by the identification of a stone vessel workshop inside the village. Stone vessels were produced in another building S.134, its small annexe S.156, and the adjoining open-air space (level B, Figure 3). The careful analysis of the macro-traces of a significant series of hammering tools, or bouchardes, made from chert, chalcedony, diabase and jasper (Figure 4), as well as the reconstruction of detailed chaînes opératoires (manufacturing sequences) of the stone objects, demonstrated that these tools were mostly used to produce vessels. The presence of a thin powder of diabase or similar igneous rocks, hammers and flakes detached during the shaping and the rejuvenation/repair of these tools, as well as fragments of vessels made from diabase and a roughed-out vessel of this material confirm this identification.

Three hundred and sixty-three bouchardes were discovered in level B, while they do not exceed 10 specimens in the other levels. This specialized material was found in a house which is not different from the others, next to the ubiquitous lithic tools. Stone vessel production appears, therefore, to have been a specialized craft activity within daily domestic activity. It is difficult, however, to estimate the volume of workshop production, which probably did not exceed the needs of the community or a limited group of people.

During the Pre-Pottery Neolithic, the production and use of lithic tools was a constant feature. These tools were both unretouched blanks and formal tools. The ways in which they were manufactured evolved over time. During the Cypro-PPNA and the Cypro-PPNB, tools were produced applying rules, know-how and skills seen on the mainland, namely in the Near-East.

Small unipolar débitage was identified (Klimonas); it was replaced by bidirectional (bipolar) débitage (Shillourokambos). With the Khirokitian, the lithic artefacts were manufactured following simplified modes, and links with the mainland technology are no longer visible.

Incidentally, the importation of obsidian is far less frequent than in Cypro-PPNB. During the Pre-Pottery Neolithic of the island, the use of local lithic raw materials evolved. When one pays attention to the flint supply, one notices a shift in the varieties mined in the Lefkara formation, from the translucent type to the opaque, and later to the granular type. Regarding stone vessels, the raw material was, during the Cypro-PPNA and PPNB, mainly limestone, and in the course of the sequence of Khirokitia it became diabase.

Hunting practices and game hunted changed over time. During the Cypro-PPNA and -PPNB, arrowheads were manufactured in the villages and repaired when hunter(s) came back from expeditions. Likewise, during the entire Pre-Pottery Neolithic, sickles were produced, repaired and stored in the settlements. The way in which the sickles were manufactured did not change significantly over time. Longitudinal hafting predominates; oblique hafting took place with very particular sickle elements only during a brief period (the early phase B/C of Shillourokambos). The evolution of sickles during the Pre-Pottery Neolithic is specific to Cyprus and does not echo the mainland (Maeda et al. 2016, Astruc andBriois 2019). Apart from hunting and harvesting, lithic tools are related to meat consumption and various handicrafts.

These were sites where knapping, subsistence and craft activities took place. When it is possible to reconstruct the function of living spaces, as is the case at Khirokitia, the tools served multiple functions. Daily activities were similar inside and outside the buildings, simply more frequent outdoors. All activities identified belonged to the domestic sphere, even more specialised ones such as stone working. Our approach, which consisted in looking at artefacts from a microscopic perspective, opens new insights on modes of manufacture and use of ancient tools made from lithic or bone, and sheds light on the organization of subsistence and craft production. The study of the spatial distribution of the artefacts permits identification of the organisation of activities at the domestic level and is evidence for the existence of craft specialisation.

  al. forthcoming a), Shillourokambos (8600-6900 cal. BC, Astruc 2011, Philibert 2003, 2011, Astruc forthcoming a) and Khirokitia (7000-6000 cal. BC, Astruc 2002, Astruc forthcoming b). All three sites have provided evidence for in situ stone knapping, as well as for use of tools in various subsistence and craft activities.

Figure 1 .

 1 Figure 1. Klimonas. Borers. 1. Piercing of stone; a. Borer on a burin spall; b. microscope photograph showing use-wear (200x magnification): heavy abrasion of the edge of the tool and matte surface. 2. Piercing of shell; microscope photographs showing use-wear (a. 100x magnification, b. 200x magnification): heavy abrasion of the edge of the tool, flat surface with a highly developed semi-bright polish and dense striation with disrupt continuity.

Figure 2 .

 2 Figure 2. Khirokitia (level C and III). 1-6. Sickle elements with longitudinal gloss, hafted (in parallel) on a haft; 1. Blade with a lateral cortex, 2. Blade fragment, 3-4. Backed pierces, 5. Blade with lateral cortex and truncation, 6. Truncation. a-b. Variability of use-wear due to cereal harvesting (100x magnification): the gloss is visible to the naked-eye and can be described microscopically as characterized by a well-developed and invasive polish, flat, shiny with a very thin longitudinal striation and a rounded and polished edge.

Figure 3 .

 3 Figure 3. Khirokitia (level B5). Stone-working workshop in a domestic context (first stage). Stone powder, tools, waste from activities found inside the buildings S.134 and S.156 and on the floors of adjacent unbuilt spaces.

Figure 4 .

 4 Figure 4. Khirokitia (Level B). 1-4. Heavy tools found in the workshop, used to shape stone objects, most probably vessels (1. Jasper, 2 and 4. Chalcedony, 3. Diabase). a, b. Macroscopic photographs of active areas on a picking tool made of diabase.

Laurence Astruc