Title: TRAJECTORY REPRESENTATION LEARNING FOR MULTI-TASK NMRDPS PLANNING

Abstract: Expanding Non Markovian Reward Decision Processes (NMRDP) into Markov Decision Processes (MDP) enables the use of state of the art Reinforcement Learning (RL) techniques to identify optimal policies. In this paper an approach to exploring NMRDPs and expanding them into MDPs, without the prior knowledge of the reward structure, is proposed. The non Markovianity of the reward function is disentangled under the assumption that sets of similar and dissimilar trajectory batches can be sampled. More precisely, within the same batch, measuring the similarity between any couple of trajectories is permitted, although comparing trajectories from different batches is not possible. A modified version of the triplet loss is optimised to construct a representation of the trajectories under which rewards become Markovian.

1. INTRODUCTION:

One of the major objectives in reinforcement learning is to identify optimal policies of a given Markov Decision Process (MDP), whose existence is typically ensured if the environment is Markovian (Sutton et al., 1998) . However, this assumption is usually not fulfilled in many real life problems. A first possible cause is "partial observability", when the real state space is observable only through a projection on a sub-space. For instance, consider a (cleaning) robot that uses the distance from the walls in four directions as a state space. This representation of the environment does not necessarily correspond to the exact location in the house as different places share the exact same distances to walls. This setting is usually framed as a Partially Observed Markov Decision Process (POMDP) (Shani et al., 2013; Cassandra, 1998; Murphy, 2000; Hausknecht & Stone, 2015; Zhu et al., 2018) . A second possible cause is that reward functions might depend on the whole trajectory. Consider the example of a waiter/server robot whose state space is the current position in the coffee shop and the current interaction with the clients (taking orders, getting and delivering beverages). The objective is to train this robot to bring coffee when ordered. A possible reinforcement signal is to reward the agent when it processes an order that was not satisfied in the past. As the states do not include past requests, nor their fulfilment, the environment is not Markovian and the proposed reward is a function of the trajectory up to the present. This setting is a Non-Markovian Reward Decision Process (NMRDP) (Bacchus et al., 1997; Thiébaux et al., 2006; Bakker, 2002; Bacchus et al., 1996) . Both POMDP and NMRDP are special cases of Non Markovian Decision Processes. The second above example (waiter robot) is actually a multiple task problem. Planning in this setting is a challenging problem because it requires more than optimally and independently solving each task (Toro Icarte et al., 2018) . It is possible that a global optimal policy for the whole sequence of tasks induces sub-optimal policies for each one of the sub-tasks. Let us take a naive example of an agent building a shelter which requires gathering wood and stones from nearby resources. To gather wood/stones optimally, the agent should look for the nearest forest/quarry. However, if it wants to optimally gather all the resources, it should not just consider how close the forests or the quarries are, but how close they are to each other as it will have to walk from one to the other. Notice that this example shares similarities with the k-server problem (Manasse et al., 1990) . In those cases, the nature of the task is not encoded in the state space, so the Markov assumption is not verified. Casting the problems as an NMRDP requires using a (stage by stage) reward function that encodes the tasks specifications. In the shelter building scenario, the reward as a function of the states, while none of the tasks is achieved, is different from when stones or wood have been collected. If it is possible to map the previously observed states (the trajectory up to the present) into the current task, the problem can be expanded into a standard MDP, where it is known how to identify optimal policies. Motivated by the shared similarities of the described problems, we shall focus on learning to identify current tasks from the trajectory of visited states (Wilson et al., 2007) . Ideally, if annotated trajectory data sets are available, learning a trajectory representation function that expands the NMRDP into an MDP would be a supervised task. However this is a strong assumption. Indeed if a simple way of creating such data sets existed, it would be used to expand the NMRDP's state space. Another issue, is that given a set of tasks, there might exist multiple non Markovian reward functions of interest. For instance, consider an agent whose goal is to maximise customers satisfaction. In this case the reinforcement signals are the declared satisfaction of said customers (in the form of a rating for example). However even if different customers expect the same goals to be accomplished by the robot, their perception of the performance might differ. This example can be generalised to the case where several experts (or simply users) are training a robot to perform some tasks, possibly different from one expert to the other. They share a common NMRDP environment with different reward/reinforcement functions as the set of tasks (or their appreciations/preferences) might be different from one expert to the other. The same augmented MDP can be used for all of their respective NMRDP as they share the same latent global set of tasks (more or less whatever the robot can physically do). This training can be made by the expert independently but it will certainly be faster and more efficient if made collectively. In these cases, in order to identify the full set of tasks and annotate the trajectories, a central authority must be aware of the reward function of each expert. This might be impossible due to tractability reasons, or privacy constraints. Fortunately, the experts can easily provide "similarity" between trajectories with respect to the latent task, i.e., whether the robot was performing the same task or not at that time, without specifying precisely the task. In the customer example, the evaluations given by the same client can be used to compare if two trajectories are associated with the same task or not, but not if those trajectories come from batches associated to two different customers. Indeed, establishing comparisons between the tasks associated to subsets of the observed trajectories without actually knowing the actual task is possible. As a consequence, we are going to assume that learning is done using batches of trajectories, where we will have a task similarity measure within each batch.

In order to identify the tasks, standard techniques identify a latent state space in which policies become Markovian, thus optimal ones exist. Unfortunately these approaches require domain specific knowledge in the form of "relevant propositions" (Bacchus et al., 1997; Thiébaux et al., 2006; Bakker, 2002; Toro Icarte et al., 2018) , either by estimating the hidden state or by constructing additional features. For example, in the waiter robot case, received orders are the relevant propositions that the agent needs to save in order to identify current tasks. Our major contribution in this paper is a generic approach to discover a latent state space given a set of similar and different trajectories. This assumption requires weaker domain specific knowledge. Once the latent state space is available, multi-task and meta-learning related approaches provide efficient tools to identify optimal policies (Andrychowicz et al., 2017; Colas et al., 2019) or to learn a general purpose policy from which learning a specific task's optimal policy can be done in few steps (Duan et al., 2017; Rakelly et al., 2019) .

The remaining of the paper is organised as follows: we introduce the mathematical tools used in this paper and we explain how they relate to our work in Section 2. We specify in Section 3 a subset of NMRDPs that can be expanded with a Markovian latent space into MDPs and we provide a possible structure of such expansion. In Section 4, we propose an algorithm to learn trajectory representation functions that approximate the tasks' latent state space and thus approximates the proposed equivalent MDPs. Section 5 is dedicated to empirical results. We consider toy NMRDPs grid-world environment (where we solve a multi-task problem using learned representations) and a real-life data set of tourists visiting Salzburg (where we learn a trajectory representations that clusters their paths according to their destinations).

2. BACKGROUND:



2.1. NON MARKOVIAN REWARD DECISION PROCESS (NMRDP):

Both finite NMRDPs and MDPs are defined by a finite state space S, a finite action space A, a transition probability P, a discount factor γ, and a reward function R. In NMRDPs, the reward function maps trajectories into real values while in MDPs the reward function maps states into real values. To the extent of our knowledge, existing methods for planning in NMRDP (Toro Icarte et al., 2018; Bacchus et al., 1997; Thiébaux et al., 2006) define an augmented state space to build an equivalent MDP to the NMRDP. The most straightforward idea would be to define the augmented state space S * as the set of all possible trajectories. However, the number of possible trajectories grows exponentially with the horizon, which makes the numerical complexity intractable for state of the art reinforcement learning techniques.

An established approach to expand the state space requires a set of domain-specific propositions. Using temporal logical operator it combines these propositions to automatically construct a set of temporal variables (Bacchus et al., 1997; Thiébaux et al., 2006) that extends the state space to specify an equivalent MDP. These methods have been successfully used to teach a reinforcement learning (RL) agent multiple tasks (Toro Icarte et al., 2018) . However, the downside is that domain specific propositions are required to disentangle the non Markovianity of the reward function. Other approaches exploit the model free RL techniques by adding a Long Short Term Memory (LSTM) layer to the policy network (Bakker, 2002) . The agent policy becomes a function of the full trajectory and the agent has enough information to find the optimal policy. In the tested toy examples of POMDPs, the agent needs undesirable directed exploration techniques to have a good performance (Bakker, 2002) . Moreover, when dealing with similar NMRDPs with different reward functions, we need to start the training from scratch when using this approach.

Motivated by the lack of approaches to expand the state space when relevant information about the reward structure are not provided, we investigate the state expansion problem in NMRDPs.

2.2. TRIPLET LOSS AND CONTRASTIVE LEARNING:

Learning useful representations of the data has been done in an array of challenging tasks. The access to data in the form of similar and/or dissimilar observations enabled the development of multiple efficient contrastive learning techniques (Mikolov et al., 2013; Schroff et al., 2015; Kilian & Lawrence, 2009) . Recent work (Arora et al., 2019) establishes a link between contrastive learning and efficient linear separability of the data. The core idea is to find a representation in a metric space so that similar samples have nearby representations and vice versa.

The triplet loss is a clever evaluation of this idea. Multiple formulations have been suggested in the literature for both the loss definition and the batching procedure (Kilian & Lawrence, 2009; Arora et al., 2019; Ding et al., 2015; Oh Song et al., 2016; Hermans et al., 2017) . A recent success of this approach lies in a new formulation (Hermans et al., 2017) that outperforms existing techniques in the person re-identification task (i.e., representing pictures of the same person from different angles as similar embedding vectors, and representing pictures of different persons as different embedding vectors). The suggested batching (called P K Batch-hard) selects P classes (person identities) and for each of these, K examples (images from different angles). Each of the P K images is selected as an anchor, and each of the anchors is associated with the hardest positive (the same person's image from an angle which representation is the furthest to the anchor's representation) and with the hardest negative (a different person's image which representation is the closest to the anchor's). This allows to build a batch of anchors, positives and negatives of size P K.

Formally, let X be the set of the P K sampled elements, with X j i being the i th sample of the j th class, and f θ (X j i ) be a representation parameterised by θ in a metric space R d where d is the representation dimension. The metric of the representation space is denoted by D(u, v). The proposed loss is:

EQUATION

The margin m is a constraint on how far the negative samples should be from each other, and the relu function [x] + avoids correcting already well defined representations. The relu function can be substituted by any smooth approximation such as log1p(.) defined as log1p(x) = log(1 + e x ).

In multi-task problems, a representation that identifies the current task is sufficient to expand the state space and build the equivalent MDP. Given trajectory batches with similar and dissimilar tasks, the contrastive learning approaches, and particularly the triplet loss, lend themselves to construct trajectory representations that translate the task similarity. In these approaches, no information about the reward structure is required.

3. LATENT SPACE FOR MULTI-TASK NMRDPS:

Given an NMRDP denoted by N = {O, A, P, R, γ} where O (for "observable") is the state space, and the reward is a function of the trajectory (o t ) t=T t=0 , there always exists an equivalent MDP that extends N (Bacchus et al., 1996) .

Consider multi-task problems that do not suffer from partial observability. In other words, if the NMRDP N is a formulation of the multi-task problem, then the reward function is Markovian in the observables and some hidden goals (it depends on what task is being achieved and what current state o t is being visited). This restriction implies that given the nature of the current task, the agent is able to make optimal decisions based on the current observation. Many real life problems (like the examples described in the introduction) satisfy this constraint naturally.

Recall that in an NMRDP, the reward is a function of the whole trajectory R((o t ) t=T t=0 ). However we assume that given the mapping T from trajectories into the set of tasks H,

EQUATION

In multi-task problems, the mapping T can be defined recursively using the recent observations and tasks instead of using the whole trajectory. Consider the shelter building scenario, where the tasks can be defined as "collecting the wood", "collecting the stones" and "building the shelter". If the agents is currently "collecting the stones", and given that it already "collected the wood", it only need to check the current state (to verify if it is currently in the quarry or not) to decide if we keep "collecting the stones" or go on to "building the shelter".

In these cases and depending on the nature of the problem, T is a bounded memory process in O and H. Thus there exists a task horizon τ T ≥ 1 and an observation horizon τ O ≥ 0 such that:

T ((o t ) t=T t=0 ) = T ((o T -τ ) τ =τ O τ =0 , (h T -τ ) τ =τ T τ =1 ) ∀ T ∈ N.

To avoid cumbersome notations, we will restrict ourselves to the case where τ O = 0 and τ T = 1, however, our results can be generalised to any values of τ O and τ T . In this case, T can be further simplified in the following form:

EQUATION

In other terms, the considered NMRDPs admit an equivalent MDP formulation M * = {S * , A * , P * , R * , γ} whose state space is S * = H × O. By construction of the equivalent MDP (Bacchus et al., 1996) , and under the consideration of Equation 3, P * verifies the following:

P * ((o t+1 , h t+1 )|(o t , h t ), a t ) = P(o t+1 |o t , a t ) × 1 ht+1=T (ht,ot+1) .

In other terms, if the MDP satisfies the following Equation 4, then M * is equivalent to N (Bacchus et al., 1996) :

   A * (o t , h t ) = A(o t ) R * (o t , h t ) = R(o 0:t ) P * ((o t+1 , h t+1 )|(o t , h t ), a t ) = P(o t+1 |o t , a t ) × 1 ht+1=T (ht,ot+1) (4)

As N satisfies Equation 2, the construction of M * is straightforward once the mapping T is known.

3.1. FEATURE REPRESENTATION FOR THE LATENT SPACE:

Typical techniques to learn optimal policies in problems with large state space exploit feature functions (Lillicrap et al., 2015; Mnih et al., 2015; 2013) . This motivated learning an embedding φ : Γ(O) → R d where d is the dimension of the tasks' feature space. As the goal is learning optimal policies using classical RL techniques, it is important to evaluate an MDP M = { Ŝ, Â, P, R, γ},

equivalent to N , such that Ŝ = R d × O ⊇ φ(Γ(O)) × O.

In what follows we construct the MDP M as a reformulation of M * by substituting h t = T (o 0:t ) with φ(o 0:t ) in Equation 3 and Equation 4. We denote φ t = φ(o 0:t ).

Equation 4 implies that the feature-based equivalent MDP must satisfy the following properties:

   Â(o t , φ t ) = A(o t ) R(o t , φ t ) = R(o 0:t ) P((o t+1 , φ t+1 )|(o t , φ t ), a t ) = P(o t+1 |o t , a t ) × 1 φt+1=φ(o0:t+1) (5)

As a consequence, the construction of Â is straightforward from A. The reward ( R) and the transitions ( P) are constructed based on Equation 4and Equation 5given any function φ that separate the tasks, i.e. there exist a classifier C :

R d → H such that C • φ = T : R(o t , φ t ) = R * (o t , C(φ t )) = R * (o t , h t ) P((o t+1 , φ t+1 )|(o t , φ t ), a t ) = P * ((o t+1 , C(φ t+1 ))|(o t , C(φ t )), a t )

So from a practical point of view, the construction of an equivalent MDP to N boils down into approximating any trajectory representation function φ : Γ(O) → R d , as long as φ separates the tasks.

If an agent is learning the optimal policy of N using any RL (Reinforcement Learning) setting, it will receive both the rewards r t = R((o t ) t=T t=0 ) and the observations o t over time. But as the problem is non Markovian, the optimal policy can not be expressed using solely the observations o t . However if the same agent uses a trajectory representation function φ, it can construct over time the latent task feature φ t . Using RL techniques, finding an optimal policy π * in the equivalent MDP M (with the extended state space (o t , φ t )) is possible, and by extension (Bacchus et al., 1996) , π * is an optimal policy of N .

4. APPROXIMATION OF A TRAJECTORY REPRESENTATION FUNCTION:

Without loss of generality, consider the case where the NMRDP admits n possible tasks: H = {1, 2, .., n}. Let φ : Γ(O) → R d be a trajectory representation function that separates tasks such that:

EQUATION

Let e i = arg min 

EQUATION

Such classifier can be approximated in an unsupervised manner using K-means algorithm (Kanungo et al., 2002) . Let Ĉ be such approximation. As a consequence, Equation 7 simplifies the problem into finding any trajectory representation function f that satisfies Equation 6 for any two trajectories γ 1 , γ 2 ∈ Γ(O). We propose in the remaining to approximate such function using deep neural networks as a parametric family f θ and optimising the triplet loss introduced in Equation 1 with respect to θ.

The obtained trajectory representation functions f θ * can either be used to reconstruct an approximation of M * (by evaluating Ĉ • f θ * ) or to build an approximation of M (by using f θ * as a feature function instead of φ).

4.1. ARCHITECTURE OF THE TRAJECTORY REPRESENTATION FUNCTION:

We have tested multiple architectures for the f θ function. The most promising architectures were mostly inspired by the Long Short Term Memory (LSTM) cell architecture (Hochreiter & Schmidhuber, 1997) and the Gated Recurrent Unit (GRU) cell architecture (Cho et al., 2014) .

The architecture that we use in our implementation builds features from the observed states using a Multi-Layer Perceptron (MLP) architecture (Rumelhart et al., 1985) . The obtained features are concatenated with the last latent state φ past , and fed to two parallel MLPs. The first one generates a proposed latent state φnew , and the second generates a forget gate variable Z ∈ [0, 1] (Hochreiter & Schmidhuber, 1997; Cho et al., 2014) . The evaluated new latent state φ new is computed as follows:

φ new = Z × φnew + (1 -Z) × φ past

4.2. OPTIMISATION OF THE TRAJECTORY REPRESENTATION FUNCTION:

Batches of comparable trajectories are used in order to learn a representation function f θ that separates tasks. To construct these batches in practice, the only domain-knowledge required is the ability to compare tasks. As mentioned before, the batches can eventually be collected from different experts working with different reward functions that share the same latent task space H. Let (γ j i ) i≤K, j≤P ∈ Γ(O) be such that T (γ j i1 ) = T (γ j i2 ). Given a representation function f θ , the representation φ(θ) j i ∈ R d of the trajectory γ j i is constructed recursively with Equation 3:

EQUATION

In order to satisfy Equation 6, the batch hard loss function from Equation 1 is optimised with respect to θ:

EQUATION

Empirically, given the same computational power, using a special case of truncated back-propagation through time (Puskorius & Feldkamp, 1994 ) (where we update the weights one time step at the time after computing the representation of the whole trajectory) provided better performances. This approach can be seen as an EM (Expectation-Maximisation) algorithm. In the expectation step (E), the representation of the available data is evaluated under a fixed θ (i.e. φ(θ) j i is computed). In the maximisation step (M), the recursive definition of task features in Equation 8 is used to define Equation 10, a local version of Equation 9:

EQUATION

Let o j i be the last observation in the trajectory γ j i , and let φ(θ) j i the representation of the trajectory γ j i without the last observation. We define L max (γ j i , θ, θ old ) and L min (γ j i , θ, θ old ) as follows:

L max (γ j i , θ, θ old ) = max p≤K ||f θ (o j i , φ(θ old ) j i ) -f θ (o j p , φ(θ old ) j p )|| L min (γ j i , θ, θ old ) = min p≤K,c≤P,c =j ||f θ (o j i , φ(θ old ) j i ) -f θ (o c p , φ(θ old ) c p )|| .

Given a step size α, the maximisation step (M) is a gradient descent with respect to θ:

θ new = θ old -α∇ θ L local BH (θ, γ, θ old ).

Basically, optimising Equation 10 in the M-step, assumes that the previous representations φ(θ) j i is an input data and does not propagate the gradient further than the current observation. The E-step, re-evaluates the representations of the trajectory over time. By alternating these steps, we were able to obtain the provided experimental results.

ability to approximate such function in a simulated toy example and in a real life problem. We used an NMRDP Grid-world problem where the agent needs to visit a sequence of particular cells in order to be rewarded. The reward function is not Markovian because the state space is just the coordinates of the current cell. Using P K batches from randomly generated trajectories, we construct a representation function that separate the tasks and thus expands successfully the state space. This is detailed in Section 5.1 For the real life example, we used the GPS tracks of tourists in Salzburg City, Austria. The tourists can be seen as agents who are rewarded from certain "attractions" the first time they see them. So this can be stated as an NMRDP problem. We build a representation function of the GPS tracks that clusters trajectories going to the same place and separate those heading to different directions in Section 5.2. We also provide a github repository with our implementation of the solution (using TensorFlow) along with the necessary modules to simulate the toy example and the data of the real life example. In order to recreate the experimental results provided in what remains, you can access the contents on the following Microsoft Azure blob (This link is anonymous and respects the double-blind reviewing process, it will be substituted with a Github repository in the camera ready version)

5.1. GRID-WORLD PROBLEM:

We run our approach on a Grid-World problems with varying grid dimensions. The state space O is the grid cells, the action space A is the available directions (North, South, East, West) and staying still. Transition probabilities P are naturally defined by the action space. We will consider a non Markovian reward, with latent state structure H = {h i , i ∈ [0, n]}. Each of the latent states h i is associated with visiting a particular "target cell" T(h i ). If the target cell of h i is visited, N(h i ) defines the next task/latent state. Equation 11formally defines this setting.

         T(h i ) = o i ∈ O N(h i ) = h j ∈ H T ((o t ) t=T t=0 ) = T (o T , h T -1 ) = N(h T -1 ) if o T = T(h T -1 ) h T -1 if o T = T(h T -1 ) R((o t ) t=T t=0 ) = e -|o T -T(h T )| (11)

To simulate trajectories, we use a random policy to generate the action at each time step as this ensures generating a wide variety of trajectory patterns. We exploit the hidden states to construct the P K batches. P hidden states are sampled, and for each of them K trajectories are identified to build the batch. Training uses the EM algorithm in order to optimise the representation function.

In order to evaluate a given representation function in this toy example, we plot, for a set of trajectories, the obtained representations φ t ∈ R d and we colour label the points with respect to the hidden states h t ∈ H.

Figure 1 illustrates the results with 5 latent tasks, in a 5 × 5 grid. The graphs from left to right represent the following:

• A projection on the first two dimensions of the trajectories representations • An unsupervised dimension reduction using PCA (Principal Component Analysis)

• A supervised dimension reduction using LDA (Linear Discriminant Analysis)

The obtained representations, when reduced to two dimensions, show clearly that trajectories have been separated according to the associated task. Even when using unsupervised dimension reduction, we are able to spot clusters of representations that can be matched with different tasks. The third plot (with LDA reduction) proves that the data in the original representation space (R d ) can be separated linearly with respect to the tasks. We conclude that the construction of an n-class classifier (5 classes in the illustrated example) is possible. Using Equation 7, the function f θ that satisfies Equation 6 and a classifier, we construct an approximation of a task feature function φ • T . Therefore, an approximation of the equivalent MDP M * that expands the NMRDP. When optimising the trajectory representation function, an annealing procedure increased the convergence speed and the quality of the results. A relaxed version of the batch hard triplet loss defined in Equation 9is used. This allows exploring easier batches in the early stages of learning and generating harder batches as the representation gets better at separating the tasks. This is discussed further in Appendix A. The algorithm samples trajectories using an greedy policy with respect to the Q-function estimation and optimises a loss function based on the Bellman equation. By using a different neural network in the sampling steps than the one used for computing the parameter gradients, storing the recent trajectories in a buffer replay memory, and annealing , the neural network converges to an unbiased estimator of the optimal Q-function and thus identifies an optimal policy. In order to establish that the obtained representation is valuable to learning the optimal policy, we compare the performances of DQN-based agents with and without the use of the representation, and with the use a one-hotencoding of the actual task. The graph on the right in Figure 2 provides a comparison of the DQN performances when using only the state features, the state features along with the learned trajectory representation, and a recurrent version of the DQN (DRQN) (Hausknecht & Stone, 2015) provided the history of state features and rewards. Both the learned representations and the LSTM within the DRQN embed the trajectories in a latent space with the same dimension. In all experiments we used the same horizon, annealing step and the same replay memory size. As expected, using the learned representations enables the agent to outperform the settings where only the state features/rewards where provided. This represents quantitative proof that the evaluated trajectory representations are more useful to an agent learning downstream tasks than exploring previous rewards or previous observations within the policy network. The graph on the left side of Figure 2 , illustrate a comparison between the performances of a DQN-based agent when using either the learned representations or a one hot encoding of the actual task. Both performances are comparable, confirming that the obtained representations expended the NMRDP into an MDP. However, using the one-hot encoding of the actual task enables the agent to converge faster. This is a consequence of using an approximation of the actual equivalent MDP. However with this comparison we establish that in such NMRDP scenarios, having access to the task function is not a requirement. The ability to identify similar/different trajectories with respect to the latent task is sufficient to converge to an optimal policy.

5.2. SALZBURG CITY: TOURISTS GPS TRACKS:

The GPS tracking took place in Salzburg City, Austria. The participant of the data collection were tourists (44) residing in a youth hostel next to the old town (Kellner & Egger, 2016) . Given that the collected trajectories reflect the behaviour of a first time visitor of the city, it is likely that there exist a common latent task space. However, even though the actual mapping from trajectories to tasks is unknown, it is possible to identify trajectories with similar latent behaviours. To construct similarity batches from the data, we considered that each location where a tourist stays for more than 2 minutes is a potential task ("attraction"). The 2 minutes threshold was chosen to reduce the number of irrelevant stops. In the P K batches, the classes are P locations (stops), sparsely sampled. For each location, K trajectories heading to the same vicinity were sampled. On figure 3a , we plot the dataset of all the collected trajectories. The locations where the tourists stopped for more than 2 minutes are shown with circles. In figure 3b we plot an example of a P K trajectory batch that we use for the optimisation. Training and implementation details are provided in Appendix B.

In this real life problem, trajectories are not annotated, so evaluating the separability of the tasks is difficult if not impossible. As an alternative, we propose to qualitatively evaluate the obtained representation function. Recall that our P K batch procedure implied that the destination of the tourist is an indicator of the task it is accomplishing. A possible method to evaluate the performances of the obtained representation, is to sample trajectories that have similar representation and verify if these trajectories converge physically to a common area.

In Figure 4 , trajectories with similar representations were illustrated in red. As expected, the obtained representation clusters trajectories with similar latent tasks (destinations). This confirms that the obtained representation succeeded in separating tasks and thus expanding the associated NM-RDP into an MDP. Moreover, as the transformation clusters trajectories according to their destination, we can potentially exploit that to analyse the tourists' patterns of visiting Salzburg. Expanding NMRDPs state spaces into minimal MDPs that share the same latent space structure is a common practice to identify optimal policies in those contexts. In contrastive learning, looking for separable representations with respect to a particular goal is also a common practice to simplify more complex tasks. The principal novelty of our work is leveraging representation learning techniques to bridge planning in non Markovian contexts with state of the art reinforcement learning techniques without the need for extensive knowledge about the NMRDP reward. Gathering a set of comparable 

A ANNEALING THE BATCH DIFFICULTY OVER TRAINING:

Using hard samples provides a lot of nuanced information to the gradient computations which helps the generalisation property of the representation as it becomes harder to over fit. However, it is a recurrent issue (Hermans et al., 2017) that such sampling makes learning a lot harder in the beginning of the training. In fact the representation is still erratic and does not benefit much from difficult examples. We anneal the complexity of the batches as the representation is getting better at separating the tasks.

To circumvent this isue, we define a relaxed version of the batch hard loss defined in Equation 9where we use the worst positive and negative sample per anchor with probability p hard ∈ [0, 1] and use a random positive and a random negative sample with probability 1 -p hard .

Formally, Let P ∼ B(P K, p hard ) a random variable of P K binomial trials. We associate an anchor γ j i to the trial P j i . A hard sample is used when P j i = 1 and a random sample is used when P j i = 1. The relaxed loss is defined bellow in Equations 12

EQUATION

where

EQUATION

It is clear that L p hard =1 BH = L BH . However, as explained, optimising L BH is difficult from a random initialisation. In what follows we develop formally an annealing procedure that increases p hard as the quality of the representation improves.

Let us denote by P - θ and P + θ the probability distributions of distances between the representations of negative and positive samples. Let (L + θ , (σ + θ ) 2 ) and (L - θ , (σ - θ ) 2 ) be the associated means and

EQUATION

)

For B = 3000, we have that (1 -0.9987 B ) 2 0.96. We start with a low hard sampling probability and each time min b∈

[1,B] l+ b > max b∈[1,B]

lb we increase p hard . Figure 5 provides experimental analysis of the proposed procedure. In Figure 5a , we present the representation evaluation of the same problem addressed in Section 5.1. The obtained representation can be separated more easily. This allows us to conclude that obtained representation using the annealing procedure is a better approximation. The training details are provided in Figure 5b . From left to right we have illustrated the average loss value over the last used batches, the average distance between positive and negative samples as well as min b∈ [1,B] l+ b and max b∈[1,B] land the value of p hard along the training. As the hard sampling probability increases, the loss value increases. This is an expected behaviours as we are measuring a more difficult version of the loss. Starting off with p hard = 1 from a randomly initialised representation function did not converge in our toy example. In Section 5, we optimised L p hard =.1 BH to provide trajectory representation results.

B GPS TRACKS TRAINING DETAILS:

The collected GPS tracks required prepossessing in order to be used for the trajectory representation learning. We constrained the observable space to a window around the city of Salzburg to avoid outliers in the data (such as tourists wondering off to surrounding cities, in Figure 6a , we observed that these trips render the data useless). The data kept for training are the GPS tracks with longitude within [13.03, 13.06] and latitude within [47.77, 47.82] . The obtained measurement are noisy. To smooth trajectories, we apply a Kalman filter. We model humans as a moving particle, characterised with x = [x, ẋ, y, ẏ], where x and y are the respective longitude and latitude. As we want to reduce the noise of the measured positions, we can define the observable as z = [x, y] and the observation matrix H as: 

EQUATION

)

According to Equation 16, the transition matrix T is defined as follows:

T =   

1 1 0 0 0 1 0 0 0 0 1 1 0 0 0 1

EQUATION

Using the observation matrix from Equation 15 and the transition matrix from Equation 17, we apply a Kalman filter to denoise the GPS tracks and smooth the trajectories. We used the implementation from the python library pykalman. In Figure 6 , we illustrate the GPS tracks with and without the pre-processing operations. In Section 5.2, we use the data illustrated in Figure 6c .

B.1 TRAINING HYPER-PARAMETERS:

When constructing the trajectory batches, we sampled P = 10 stops that are at least 5 × 10 -3 far from each other1 . For each stop, we sampled K = 64 trajectories heading, in the next 40 observations, to a point at worst 10 -3 apart from the sampled stop. Figure ?? is a sample batch. We run 5000 iteration to optimise the relaxed batch hard loss L p hard =.1 BH , using the Adam routine from TensorFlow with a learning rate of 10 -3 , a momentum of .95 and a minimum gradient of 0.01. In Figure 7 , we illustrated the training results. The representation is indeed learning to separate trajectories that do not share the same destination. Therefore, we can conclude with more confidence that our representation separates the latent tasks of the agents (tourists). 

:

EXPERIMENTSAs described before, building an equivalent MDP to an NMRDP N can be reduced to expanding the state space with a trajectory representation that separates tasks. Experimentally, we establish the

For the sake of simplicity, the distance is evaluated as if the GPS coordinates were in an Euclidean plan.

Figures and Tables:

t.T (γ)=i |φ(γ) -e i | the centroid representations of each task. For a given trajectory representation e ∈ R d , the classifier C * (e) = arg min i∈H | e-e i | satisfies the following:

Figure 1: Evaluating the trajectory representation

Figure 3: Tourists GPS trajectory data

Figure 4: Sampled trajectories with similar representations

(a) Learned representation using annealed hard sampling probability (b) Training evaluation of annealed hard sampling

Figure 5: Evaluating annealing

Figure 6: Pre-processing the data to smooth trajectories

Peer review (iclr2020):
Short summary of paper: The paper investigates representation learning from trajectories in a framework which generalizes MDPs (NMRDPs), in which rewards are non-Markovian and follow a hidden process (this can be seen as a more structured, special case of a POMDP). The authors suggest learning a trajectory embedding by using a triplet loss, justified by a sufficient condition for learning an embedding which corresponds to the true task id. Overall I felt the paper fell a bit short of the standards for ICLR, based on subpar writing, lack of comparison to convincing baselines, and unclear applicability to more complex environments. Main issues: - The methodological sections of the paper seems conceptually accessible while being written in an overly mathematical, meandering fashion, using heavy, sometimes unclear notation, or referring to notation from other papers. As an example, mathcal{M}^* is first introduced by reference to another paper (the notation does not really need to be introduced until the mapping is made precise later in the paper); phi(	heta)_i^j(-1) is an unnecessarily heavy, unpleasant notation for the concept used. It was unclear if T is meant to represent the total trajectory length or a time index of a given trajectory (the notation would imply the former, the way it used, the latter). Similarly equation (6) is a very mathematical way to denote a relatively simple condition (which could be written more simply by comparing inf and sup distances between two trajectory embeddings corresponding to different or identical latent h). Again, equation (7) seems like a contrived way to write a relatively simple concept, and the simple proof that (6) implies (7) is not included. I feel this section could be improved by using precise but as simple notation as possible, and a sequence of propositions explaining why the triplet loss allows for identifiability of the reward process, with a clear flow between statements. - Lack of baselines: No alternative or baseline seems considered in the paper. The setting is perhaps a bit unusual, but since the data considered is essentially sequence of observations, any model of sequences could be used to produce embeddings (for instance, recurrent VAE, autoregressive models, time-contrastive methods) and compare the different trajectory representations. - Unclear generalization to more complex problems: (6) only implies (7) as far as I can tell, is sufficient but not necessary, and may be too strong of a condition to enforce; similary, theoretically requiring injectivity of phi seems practically too strong of a condition, as it essentially requires hashing each trajectory into a different embedding, in spite of the fact that many aspects of observations may be irrelevant for the task at hand). A key difficulty to scale this algorithm will be to find how to distance between trajectories in high dimension - perhaps the most important question for representation learning of trajectories, and a point the paper does not address. Positives: The method is overall well principled and the theoretical justification of the triplet loss is interesting. The dataset used for experiments is also interesting. Minor/Questions: - IIUC, the equation (3) needs to hold for all times T, this needs to be clearly stated as often T is used to denote total episode length. - Bottom of page 4, *The construction of the task ... phi_T=phi(mathcal T(o_T, phi_{T-1}); does this not require injectivity of phi, which is only stated afterwards? - Calling the algorithm *EM* is a bit of a stretch (there are no latent variables), it is better to call it a form of coordinate ascent. - The way the EM-like algorithm is set up, it appears the gradient with respect to theta is only computed with respect to a single time step (similar to elman networks style truncated backprop) - why not use regular backpropagation through time to train though the entire sequence? - typo on section 5.1: *Grid-world problem* - It is very hard to see on figure 3 what we are supposed to see (I don*t see these as having the same destination, perhaps highlight more clearly?)