Trajectory representation learning for Multi-Task NMRDPs planning
Authors: Firas JARBOUI
Vianney PERCHET
Roman EGGER
Venue:  (2020)
Keywords: Representation Learning
State Estimation
Non Markovian Decision Process

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.

Under review as a conference paper at ICLR 2020
TRAJECTORY REPRESENTATION LEARNING FOR MULTI-TASK NMRDPS PLANNING
Anonymous authors Paper under double-blind review
ABSTRACT
Expanding Non Markovian Reward Decision Processes (NMRDP) into Markov Decision Processes (MDP) enables the use of state of the art Reinforcement Learn- ing (RL) techniques to identify optimal policies. In this paper an approach to ex- ploring 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 trajec- tory 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 re- wards become Markovian.
INTRODUCTION
One of the major objectives in reinforcement learning is to identify optimal policies of given Markov Decision Process (MDP), whose existence is typically ensured if the environment is Marko- vian (Sutton et al. 1998). However, this assumption is usually not fulfilled in many real life prob- lems. 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 walls. This setting is usually framed as Partially Observed Markov Decision Process (POMDP) (Shani et al. 2013 Cassandra 1998 Murphy 2000; Hausknecht & Stone 2015 Zhu al. 2018). A second possible cause is that reward functions might depend on the whole trajectory. Consider the example of 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 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- Non-Markovian Reward Decision Process (NMRDP) (Bacchus et al. 1997;; Thiébaux 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 possible that 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 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 map the previously observed states (the trajectory up to the present)

---

Under review as a conference paper at ICLR 2020
into the current task, the problem can be expanded into 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 supervised task. However this is strong sumption. Indeed if 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 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 robot to perform some tasks, possibly different from one expert to the other. They share a common NMRDP environment with different rewarr/rrinnforeementt functions as the set of tasks (or their ap- preciations/preferenee)) 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 inde- pendently 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 tractability reasons, or pri- vacy 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 consequence, using batches of trajectories, where we will have a task similarity measure within each batch.
are going to assume that learning is done
In order identify the tasks, standard techniques identify a latent state space in which policies become Markovian, thus optimal ones exist. Unfortunately these approaches require domain spe- eific knowledge in the form of "relevant propositions" (Bacchus et al. 1997 Thiébaux al. 2006 Bakker 2002 Toro Icarte et al. 20018). either by estimating the hidden state or by constructing ad- ditional 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 a generic approach to discover latent state space given a set of similar and different trajectories. This assumption requires weaker domain specific knowledge.
Once the latent state space available, multi-task and meta-learning related approaches provide ef- ficient tools to identify optimal policies (Andrychowicz et al. 2017 Colas et al. (2019) or to learn 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 explain how they relate to work in Section 2 We specify in Section B subset of NMRDPs that can be expanded with a Markovian latent space into MDPs and we provide 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. Scction 5s 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 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 finite state space S, finite action space A, transition probability P, a discount factor 7, 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
2

---

Under review as a conference paper at ICLR 2020
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 of domain-specific propositions. Using temporal logical operator it combines these propositions to automatically construct a set of temporal variables (Bacchus al. 1997 Thiébaux et a 2006) that extends the state space to specify an equivalent MDP. These methods have been successfully used to teach a reinforcement learning (RI. agent multiple tasks (Toro learte et al. 2018). However, the downside is that domain spe- cific propositions are required to disentangle the non Markovianity of the reward function. Other approaches exploit the model free RI. techniques by adding Long Short Term Memory (LSTM) layer to the policy network (Bakker) 2002). The agent policy becomes function of the full trajec- tory 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 have good performance (Bakker (002). Moreover, when dealing with similar NMRDPs with different reward functions, we need 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 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 al. 2013 Schroff al. 2015 Kilian & Lawrrence] 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 representation in a metric space so that similar samples have nearby representations and vice versa.
The triplet loss is 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 al. 2019 Ding et al., 2015; Oh Song et al.] 2016 Hermans et 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 PK Batch-hard) selects P classes (person identities) and for each of these, K examples (images from different angles). Each of the PK images is selected as an anchor, and each of the anchors is associated with the hardest positive (the same person's 's image from angle which representation is the furthest to the anchor's 's representation) and with the hardest negative (a different person's 's image which representation is the closest to the anchor's) s). This allows build batch of anchors, positives and negatives of size PK.
Formally, let X be the set of the PK sampled elements, with X being the ith sample of the jth class, and fo(X²) be a representation parameterised by in a metric space Rd where d is the representation dimension. The metric of the representation space is denoted by D(u, v). The proposed loss is:
P
K
(0, =
Σ
m + max D(fo(X)). P
min PSKeSP.off
D(G(())),6(x3)) (1)
The margin m is a constraint on how far the negative samples should be from each other, and the relu function [z]+ avoids correcting already well defined representations. The relu function can be substituted by any smooth approximation such as loglp(.) defined as loglp(x) = log(1 + e*).
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
3

---

Under review as a conference paper at ICLR 2020
trajectory representations that translate the task similarity. In these approaches, information about the reward structure is required.
LATENT SPACE FOR MULTI-TASK NMRDPS
Given an NMRDP denoted by = [O,A, R. 7 where O (for "observable") is the state space, and the reward is function of the trajectory (o,) 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-tat talti-taskk 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 is being visited). This restriction implies that given the nature of the current task, the agent 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 function of the whole trajectory (((o))))) However we assume that given the mapping T from trajectories into the set of tasks H.
T (((o)) VT E IN = ((O) H,
the reward function R can be rewritten as: R((o.) R(or, T((o)) R(or, VTEN
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 check the current state (to verify if it is currently in the quarry not) decide if keep "collecting the stones" or to "building the shelter".
In these cases and depending on the nature of the problem. T is a bounded memory process O and H. Thus there exists task horizon 2 and an observation horizon 2 0 such that:
T((o))t))) = (((or-)) ((or=)))_(,,(()))))))) ET
To avoid cumbersome notations, we will restrict ourselves the case where TO and TT 1, however, our results can be generalised to any values of To and Tr. In this case, T can be further simplified in the following form:
T((o)) ( ((or,hr-1) = hr VTEN.
In other terms, the considered NMRDPs admit equivalent MDP formulation M = {S*, ,"' ..>) whose state space is S* = H. O. By construction of the equivalent MDP (Bacchus al. 1996), and under the consideration of Equation 3 P' verifies the following:
(((ott1,het))l he), ot) P(o a:) Ihun)T((he.up)
In other terms, if the MDP satisfies the following Equation then M is equivalent to N (Bacchus) ct al. 1996):
A (o., R (or ha)
A(o:)
R(o0:)
P' ((0 (ot, az) = P(o a:) x In
As As N satisfies Equation the construction of M is straightforwwrd 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 func-
tions (Lillicrap et al. 2015 Mnih et al. 2015 2013). This motivated learning embedding
4

---

Under review as a conference paper at ICLR 2020
6: [())) - R where is the dimension of the tasks' feature space. As the goal is learning optimal
policies using classical RL techniques, it is important to evaluate MDP .M A P, R, 7), equivalent N,, such that S R O 2 ((T())) O. In what follows we construct the MDP M as reformulation of MM by substituting he = T ((o::) with ((00:)) in Equation 3 and Equation We denote o, = ((00:))
Equation implies that the feature-based based equivalent MDP must satisfy the following properties:
Alor, Φ1) Rloi, Φ1)
A(o:)
R(oo:)
(5)
0.),
P(o++1lor,a)) a4) x d(+1=v(onee))
As consequence, the construction of Á straightforward from A. The reward (R) and the transi- tions (P) are constructed based on Equation 4 and Equation given any function e that separate the tasks, i.c there exist classifier C RR + H such that C T=
R(o, Φ.) = (o, (().)) = (" {
P((0141, θt+1) (or. 01), aq) P ((on)))
So from a practical point of view, the construction of an equivalent MDP to A boils down into approximating any trajectory representation function Φ T(O) - Rd, as long as Φ separates the tasks.
If agent is learning the optimal policy of N using any RL (Reinforcement Learning) setting, will receive both the rewards r; R((or){=0) and the observations o, over time. But as the problem is non Markovian, the optimal policy not be expressed using solely the observations oІ- However if the same agent uses trajectory representation function Φ, it can construct over time the latent task feature &i. Using RL techniques, finding an optimal policy n in the equivalent MDP M (with the extended state space (oe, d.)) is possible, and by extension (Bacchus al. 1996), an optimal policy of A.
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 I(O)- Rd be trajectory representation function that separates tasks such that:
inf (osTT
((()) - 6(12)1 >
sup (mn
pp(n) - -(1)))((2)
(6)
Let 6; = arg min max (p(7) - esl the centroid representations of each task. For a given eaR' <x)((===
trajectory representation E Rd, the classifier (e = arg min |e-eyl satisfies the following: K
C' or = Vy E T(O).
Such classifier can be approximated in an unsupervised manner using K-means algorithm Kanungo 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 71, 72 E I(O). We propose in the remaining to approximate such function using deep neural networks as a parametric family fe and optimising the triplet loss introduced in Equation with respect to 0.
The obtained trajectory representation functions for can either be used to reconstruct an approxima- tion of M (by evaluating Č fo-) or to build an approximation M (by using for as a feature function instead of Φ).
5

---

Under review as a conference paper at ICLR 2020
4.1 ARCHITECTURE OF THE TRAJECTORY REPRESENTATION FUNCTION
We have tested multiple architectures for the Sa function. The most promising architectures were mostly inspired by the Long Short Term Memory (LSTM) cell architecture (Hochreiter & Schmid- huber (197)) and the Gated Recurrent Unit (GRU) cell architecture (Cho et 20144)
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 Opan, and fed to two parallel MLPs. The first one generates proposed latent state &news and the second generates a forget gate variable Z E [0, 1] (Hochreiter & Schmidhuber 1997 Cho al. 2014). The evaluated new latent state &new is computed follows:
Onew Z x &new + (1 - Z) x Opast
4.2 OPTIMISATION OF THE TRAJECTORY REPRESENTATION FUNCTION
Batches of comparable trajectories are used in order to learn a representation function so that sepa- rates tasks. To construct these batches in practice, the only domain-knowledn required is the ability to compare tasks. As mentioned before, the batches can eventually be collected from different ex- perts working with different reward functions that share the same latent task space H.
Let JSP I(O) be such that T( T(2 Given a representation function fo. the representation ( E Rd of the trajectory 7 is constructed recursively with Equation
Φ So (or, 01-1).
(8)
In order to satisfy Equation to 8:
6 the batch hard loss function from Equation
optimised with respect
P
K
Lan(0,7) Σ j=1
Σ
loglp m max [()(0) ((0))11
min P K.e.P..cf
[(((0) ((0)))))
PSK
Empirically, given the same computational power, using a special case of truncated pookkproppggtioon 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-Mximiise) the representation of the available data is evaluated under fixed 0 (i.e. 6(0) is computed). In the maximisation step (M), the recursive definition of task features in Equation is used detine Equation 10 local version of Equation
algorithm. In the expectation step (E),
P
K
Chn (0, Pold)
loglp m + Lmax Smax(12 (7,,0, 0ota)) Emiu (1d 0, Bow))
(10)
j=1
Let of be the last observation in the trajectory T/ and let σ(0) the representation of the trajectory
of without the last observation. We define Lmax (7/ 0, Pou) and Lmin(r? 0, Boud) as follows:
{ Lumax (16 Goua) = maxpsk [lfo(o), ((oo)))) - fo -o((o,,((0u)))))
((0m)))))
Liin (72 O, Gata) minpsK,esP.e.. [[fo(o) a(0mu))) So [o ((Oa)))))l
Given a step size a, the maximisation step (M) a gradient descent with respect to
Opew
Oni V Clocal (0, 7,, Oot))
Basically, optimising Equation 10 in the M-step, assumes that the previous representations 200) 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, were able to obtain the provided experimental results.
5 EXPERIMENTS
As described before, building an equivalent MDP to an NMRDP A can be reduced to expanding the state space with trajectory representation that separates tasks. Experimentally, we establish the

---

Under review as a conference paper at ICLR 2020
ability to approximate such function in a simulated toy example and in 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 PK 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 [.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 Section 5.2
We also provide 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 recreate the experimental results provided in what remains, you access the contents on the following Microsoft Azure blob (This link is anonymous and respects the double-bling reviewing process, it will be substituted with a Github repository in the camera ready version)
5.1 GRID-WORLD PROBLEM
We 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 7 {h,, é E [0, n|}. Each of the latent states h; is associated with visiting a particular "target cell" Th;.). If the target cell of h2 is visited, Nh;,) defines the next task/latent state. Equation [ formally defines this setting.
T(h:) = 0; E E N(h,) h, H T((O)EE) = T(or, h1- { (((O))(E)) --lor-T(hr))
N(hr-1) if = -T(hr-1)
(11)
hT-1 if or * T(hT-1)
To simulate trajectories, we use random policy to generate the action each time step as this ensures generating wide variety of trajectory patterns. We exploit the hidden states to construct the PK batches. hidden states are sampled, and for each of them K trajectories are identified to build the batch. Training uses the EM algorithm in order optimise the representation function. In order to evaluate a given representation function in this toy example, we plot, for set of trajecto- ries, the obtained representations Φe Rd and we colour label the points with respect to the hidden states h4 E H.
Figure I illustrates the results with 5 latent tasks, in a 5 x 5 grid. The graphs from left to right represent the following:
A projection 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 the associated task. Even when using unsupervised dimension reduc- tion, 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 (Rd) can be separated linearly with respect to the tasks. We conclude that the construction of an n-class classi- fier (5 classes in the illustrated example) is possible. Using Equation 7 the function fo that satisfiss Equation 6 and classifier, we construct an approximation of a task feature function Φ a T. There- fore, an approximation of the equivalent MDP M" that expands the NMRDP.
When optimising the trajectory representation function, annealing procedure increased the con- vergence speed and the quality of the results. A relaxed version of the batch hard triplet loss defined in Equation 9 is used. This allows exploring easier batches in the early stages of learning and gener- ating harder batches as the representation gets better at separating the tasks. This is discussed further in Appendix| A
7

---

Under review as a conference paper at ICLR 2020
-14
Figure 1: Evaluating the trajectory representation
perfemenc BOX boodd Sewe
Figure 2: DQN performances with and without using the trajectory representation
Deep Q-Networks (Mnih al. 2013) are of the widely used off-the-shelf approaches in RL. The algorithm samples trajectories using an e greedy policy with respect to the Q-function estimation and optimises a loss function based on the Bellman equation. By using different neural network in the sampling steps than the one used for computing the parameter gradients, storing the recent trajectories in buffer replay memory, and annealing c, the neural network converges to an unbiased optimal policy. In order to establish that
estimator of the optimal Q-function and thus identifies 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 one-hot- encoding the actual task. The graph on the right in Figure 2 provides 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 guantitative proof that the evaluated trajectory representations are more useful to an agent learning downstream tasks than exploring previous rewards or previous ob- servations within the policy network. The graph on the left side Figure illustrate a comparison between the performances of a DQN-based agent when using either the learned representations or 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 ac- tual task enables the agent to converge faster. This a consequence of using an approximation of the actual equivalent MDP. However with this comparison we establish that in such NMRDP scenar- ios, having access to the task function not a requirement. The ability to identify similar/different trajectories with respect to the latent task is sufficient to converge optimal policy.
8

---

Under review as a conference paper at ICLR 2020
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 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 potential task ("attraction")). The 2 minutes threshold was chosen to reduce the number of irrelevant stops. In the PK batches, the classes are P locations (stops), sparsely sampled. For each location, K trajectories heading to the same vicinity were sampled. On figure [a| plot the dataset of all the collected trajectories. The locations where the tourists stopped for more than 2 minutes shown with circles. In figure (3b we plot an example of PK trajectory batch that 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 repre- sentation function. Recall that our PK 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 ob- tained 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, the transformation clusters trajectories according to their destina- tion, we can potentially exploit that to analyse the tourists' patterns of visiting Salzburg.
032
0.3
0.7
617
sés
tolen Leowcc
Loakue
(a) Measured trajectories
(b) A sample PK batch
Figure 3: Tourists GPS trajectory data
CONCLUSION
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 set of comparable

---

Under review as a conference paper at ICLR 2020
6016
0.7
Figure 4: Sampled trajectories with similar representations
trajectories with respect to the associated latent task requires a weaker domain specific knowledge of the NMRDP problem than providing "relevant propositions" about the reward structure. The fact that the obtained representation could be used to identify behavioural patterns of the tourists (agents) motivates our future work consider inverse reinforcement learning in Non Markovian Decision Process.
REFERENCES
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience re- play. In Advances in Neural Information Processing Systems, pp. 5048 0048-5058, 2017.
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saun- shi. theoretical analysis of contrastive unsupervised representation learning. arXiv preprint arXiv: 1902.0929,, 2019.
Fahiem Bacchus, Craig Boutilier, and Adam Grove Rewarding behaviors. In Proceedings of the National Conference on Artificial Intelligence, pp. 1160-1167 1167, 1996.
Fahiem Bacchus, Craig Boutilier, and Adam Grove. Structured solution methods for mon-markov decision processes. In AAAI/AAI, pp. 112-117. Citeseer, 1997.
Bram Bakker. Reinforcement learning with long short-term memory. In Advances in neural infor- mation processing systems, pp. 1475-1482, 2002.
Anthony Cassandra. survey of pomdp applications. Working notes of AAAI 1998 sympo- sium on planning with partially observable Markov decision processes, volume 1724, 1998.
Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Hol- ger Schwenk, and Yoshua Bengio. Learning phrase representations using rnn encoder-decoder for statistical machine translation. arXiv preprint arXiv: 14X.::1406.1190 2014.
Cédric Colas, Pierre- Yves Oudeyer, Olivier Sigaud, Pierre Fournier, and Mohamed Chetouani. Cu- rious: Intrinsically motivated modular multi-gos goal reinforcement learning. In International Con- ference Machine Learning, pp. 1331-1340, 2019.
10

---

Under review as a conference paper at ICLR 2020
Shengyong Ding, Liang Lin, Guangrun Wang, and Hongyang Chao. Deep feature learning with relative distance comparison for person re- re-idenifficatinn. Pattern Recognition, 48(10): 2015.
Yan Duan, Marcin Andrychowicz, Bradly Stadie, OpenAl Jonathan Ho, Jonas Schneider, Ilya Sutskever, Pieter Abbeel, and Wojciech Zaremba. One-shot imitation learning. In Advances in neural information processing systems, pp. 1087-1098, 2017.
Matthew Hausknecht and Peter Stone. Deep recurrent q-learning for partially observable mdps. In 2015 AAAI Fall Symposium Series, 2015.
Alexander Hermans, Lucas Beyer, and Bastian Leibe. In defense the triplet loss for person re- identification. arXiv preprini
2017.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Tapas Kanungo, David M Mount, Nathan S Netanyahu, Christine D Piatko, Ruth Silverman, and Angela Y Wu. An efficient k-means clustering algorithm: Analysis and implementation. IEEE Transactions on Pattern Analysis & Machine Intelligence, (7):881 892, 2002.
Lenka Kellner and Roman Egger. Tracking tourist spatial-temporal behavior in urban places, a methodological overview and gps case study. Information and Communication Technologies in Tourism 2016, pp. 48 1-44. Springer, 2016.
Weinberger Kilian and Saul Lawrence. Distance metric learning for large margin nearest neighbor classification. In JMLR,, pp. 10:207244, 2009.
Timothy P Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint N0XXv::500900971.. 2015.
Mark S Manasse, Lyle McGeoch, and Daniel D Sleator. Competitive algorithms for server prob- lems. Journal of Algorithms, 11(2):28--233 1990.
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word represen- tations in vector space. arXiv preprint arXiv: 2013.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602. 2013.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver. Andrei A Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 529,, 2015.
Kevin P Murphy. A survey pomdp solution techniques. enviromment 2:X3, 2000.
Hyun Oh Song, Yu Xiang, Stefanie Jegelka, and Silvio Savarese. Deep metric learning via lifted structured feature embedding. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 4004-4012, 2016.
GV Puskorius and LA Feldkamp. Truncated backpropagation through time and kalman filter training for neurocontrol. In Proceedings of 1994 IEEE International Conference on Neural Networks (ICNN'94), volume 4, pp. 1488-2493, IEFE, 1994.
Kate Rakelly, Aurick Zhou, Deirdre Quillen, Chelsea Finn, and Sergey Levine. Efficient off-policy leamningg meta-reinforceement learning via probabilistic context variables. arXiv preprint arXiv: 1903.00:9 2019.
David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning internal representations by error propagation. Technical report, California Univ San Diego La Jolla Inst for Cognitive Science, 1985.
11

---

Under review as a conference paper at ICLR 2020
Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In Proceedings of IEEE conference on computer vision and pattern recognition, pp. 2015.
Guy Shani, Joelle Pineau, and Robert Kaplow. survey of point- pomdp solvers. Autonomous Agents and Multi-Agent Systems, 27(1):1-51, 2013.
Richard S Sutton, Andrew G Barto, et al. Introduction reinforcement learning, volume 135. MIT press Cambridge, 1998.
Sylvie Thiébaux, Charles Gretton, John Slaney, David Price, and Froduald Kabanza. Decision- theoretic planning with non-markovian rewards. Journal of Artificial Intelligence Research, 25: 17-74, 2006.
Rodrigo Toro Iearte, Toryn Klassen, Richard Valenzano, and Sheila A Mcllraith. Teaching multiple tasks to an rl agent using Itl. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pp. 452 461. International Foundation for Au- tonomous Agents and Multiagent Systems, 2018.
Aaron Wilson, Alan Fem, Soumya Ray, and Prasad Tadepalli. Multi-task reinforcement learning: hierarchical bayesian approach. In Proceedings of the 24th international conference on Machine learning, pp. 1015-1022. ACM, 2007.
Pengfei Zhu, Xin Li, Pascal Poupart, and Guanghui Miao. On improving deep reinforcement learn- ing for pomdps. arXiv preprint arXiv: vrXiiv1804.000 1804.06309 2018.
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, is re- current issue (Hermans et al. (017)) 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 ex- amples. We anneal the complexity of the batches as the representation is getting better at separating the tasks.
To circumvent this isue, we define relaxed version of the batch hard loss defined in Equation where we use the worst positive and negative sample per anchor with probability Phant E [0, and use random positive and random negative sample with probability Phord-
Formally, Let P B(PK, Phard) random variable of PK binomial trials. We associate an anchor of to the trial P/ A hard sample is used when p and a random sample is used when Pi + 1. The relaxed loss is defined bellow in Equations 12
P
K
C (0,
loglp ( + [[0(0)) 500) 200 |(((0) (())))))))) 11.
(12)
==
where
p(i,j) = { arg max, PSK |10(0)/ <(0)%11 if P. =1 if p =0
U11 ((())
(13)
c(i.)). = arg min n KS [0)00} - 200)11
if =
U(I.... U (1..
if P
is clear that Con [Poa==1 LsH- However, as explained, optimising Laи is difficult from a random initialisation. In what follows develop formally an annealing procedure that increases Phont as the quality of the representation improves.
Let us denote by PT and P the probability distributions of distances between the representations of negative and positive samples. Let (L. (ot)² and (T. (o5) )2) be the associated means and
12

---

Under review as a conference paper at ICLR 2020
variances. The average positive distance over random batch of size N PK, denoted by 1 (N), is an unbiased estimator of the mean as
) N
(0g )
(N)~~NiH NLL
(N) NL
N
As a consequence, the probability of sampling an average value bigger than Lo of VN
roughly
0.9987 0.0013 (N) > T - 3 Let us denote by 1 the average positive distance over the batch b. If batches were i.i.d. (which is not the case as 0 evolves over time), and if denote by minge[1. 1 the minimum average distance between negative samples over B batches, the following would hold:
P( min 15 6EIL.B]
LØ
3 p ~ 0.9987
The same reasoning holds for maxse(1, 15:
T5 < Lg + 0 ~ 0.9987
P max
bE[1,]]
Consider the events A+ {mingel1
1/ < Lg 3 vN
and A = {max6e]1,81 > Lig +
3 c }, the following property holds:
V
~ (1 0.99878).
This leads to the following conclusion:
PP LT
Lg +
VN
min [E[
6
max 11
[5 > 01 - O..998777
(14)
For B = 3000, we have that (1 - 0.9987 0.96. We start with low hard sampling probability and each time minse(1,,1) 1,t > maX 1 we increase Phand-
Figure 5 provides experimental analysis of the proposed procedure. In Figure 5a we present the representation evaluation of the same problem addressed in [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 5bb] From left to right we have illustrated the average loss value over the last used batches, the average distance between positive and negative samples well min6g[1.8] [tt and max | and the value of Phont along the training. As the hard sampling probability increases, the loss value increases. This is an expected behaviours
measuring more difficult version of the loss. Starting off with from a randomly initialised representation function did not converge in our toy example. we optimised C C to provide trajectory representation results.
Phont =
In Section 5
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 window around the city of Salzburg to avoid outliers in the data (such as tourists wondering off to surrounding cities, in Figure (aa 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 humans as a moving particle, characterised with x = [x, I,, vl. where and y are the respective longitude and latitude. As we want reduce the noise of the measured positions, we can define the observable as [r,, 2/ and the observation matrix H as:
noisy. To smooth trajectories, we apply Kalman filter. We model
1
0 0
10010)
0
(15)
13

---

Under review as a conference paper at ICLR 2020
Ar
Mr
(a) Learned representation using annealed hard sampling probability
(b) Training evaluation of annealed hard sampling
Figure 5: Evaluating annealing
linear approximation of the system dynamics is used to establish, for the 1 observation, the following:
4k Tk-1 + 5k-1
d dx-1
(16)
3k = l/k-1 + 2k-1
1/k f/-1
According to Equation 16 the transition matrix T defined as follows:
0
0
0
0
0
T
(17)
1
0
0
1
Using the observation matrix from Equation and the transition matrix from Equation 17 we apply 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 x 10 10-3 far from each other!] For each stop, we sampled K 64 trajectories heading, in the next 40 observations, to point at worst -0-3 apart from the sampled stop. Figure ?? is sample batch. We run 5000 iteration to optimise the relaxed batch hard loss Lag /Pow==1 using the Adam routine from TensorFlow with a learning rate 10 a momentum of .95 and minimum gradient of 0.01. In Figure 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).
For the sake of simplicity, the distance is evaluated if the GPS coordinates in Fuclidean plan.
14

---

Under review as a conference paper at ICLR 2020
Noisy trajectories
48.4
48.2
Latitude
48.0
47.6
12.0
12.5
13.0
13.5
14.0
Longitude
(a) Raw data
stapetares
Descoud Expecenees
08
cM
07.7
6:10
13.322
13.055
13300
13345
13.05
13
22,00
13:50
13.40)
13:45
13.00
25,555
23,00
Constrained data
(c) Clean data
Figure 6: Pre-processing the data to smooth trajectories
Figure 7: Optimising the trajectory representation
15


Reviews:
[{"review_id": "SJeWQR52KS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "** Summary\nThe paper studies a specific class of Non-Markovian Reward Decision Processes (NMRDPs). In general, in NMRDP the dynamics is Markovian but the reward function may depend on the entire trajectory. The authors consider a sub-case where the trajectory can be mapped to a specific \"task\" and the reward function can be formalized as a mapping between the state-task pair to the reward. This greatly simplifies the problem that can be mapped onto an augmented MDP and solved using standard RL tools. The authors focus on the representation learning problem of the mapping between trajectories to an embedding of the task itself. In particular, they consider contrastive learning to find a representation that discriminate between trajectories associated to the same task and trajectories coming from different tasks. The resulting LSTM-based architecture is then evaluated on a grid-world synthetic problem and on GPS trajectories from tourists in the city of Salzburg.\n\n** Overall evaluation\nMy main concerns about the paper is that the exact objective of the setting and the representation learning is not that clear and the empirical validation is limited to a qualitative assessment of the representation learning with no down-stream task. More in detail.\n\n1- The assumption of task-dependent reward functions is very sensible. Yet I wonder to which extent it overlaps with literature in multi-task and meta-learning, or more in general with embedding of time-series (the trajectory in your case). It would be useful to frame/compare at the conceptual level the similarities and differences of the proposed setting with those fields.\n2- At training time, the PK dataset is somehow supervised, as it is possible to know which trajectories are associated to the same task. At test time, the learned f_theta recursively maps trajectories to tasks. As such, it seems like it could effectively detect changes into the task itself by tracking how the trajectory evolves (when the task function is unknown). This aspect is never really evaluated in the empirical section, but it would be one of the most interesting uses of the learned representation.\n3- If the task function T is known, it means that standard RL techniques can be used to solve MDP N. The actual advantage of using a specific function to embed the task to a space in Re^d is never really explained in the paper. Does it make solving N simpler or more effective than using a simple encoding for the task? No evaluation is available in this sense.\n4- The empirical evaluation is limited to qualitative analysis of the representation learned in the problem. Yet, there is no clear support that the representation is good/useful in a more quantitative way (e.g., by actually solving the RL part or in identifying quickly the current task).\n\nSome more specific questions/comments\n\n1- Some of the notation is a bit redundant. For instance, phi is mapping from H to Re^d, while f is a mapping from trajectories to Re^d, but in the end they are doing the same thing, as H itself can be obtained as a mapping from trajectories to tasks through T. \n2- \"Using RL techniques, finding an optimal policy pi* in the equivalent MDP \\hat M is possible and by extension pi* is optimal for N\". This passage is not fully clear, if phi is introducing some form of approximation, then pi* may no longer be optimal for the original MDP N. On the other hand, if phi is not approximating but \"just\" changing the representation from H to Re^d, then it is not clear what is the interest of it.\n3- The assumption that similar trajectories can be identified is somehow strong. It would be good to have a more thorough support for it.\n4- It is not fully clear what L_BH^local is indeed a local loss. It seems like you are simply using the mapping from the whole trajectory. Is this why it is called local?\n5- While I appreciate that the introduction is sketching many different scenarios to support the models studied in the paper, in the end they mostly lack of depth and they rather give a confusing impression instead of clarifying in a compelling way what is the problem studied in the paper. I suggest you rather pick one single scenario with a good level of detail to provide a more solid support to the paper.\n\n** Minor comments\n1- You often use \"he\" to refer to the agent. It would be better to use \"it\" or \"she\".", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "Hylke1JaqS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Short summary of paper:\nThe 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.  \n\nOverall 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.\n\nMain issues:\n- 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.\n\nAs 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(\\theta)_i^j(-1) is an unnecessarily heavy, unpleasant notation for the concept used. \nIt 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.\nI 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.\n\n- Lack of baselines:\nNo 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.\n\n- Unclear generalization to more complex problems:\n(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.\n\n\nPositives:\nThe method is overall well principled and the theoretical justification of the triplet loss is interesting. The dataset used for experiments is also interesting.\n\nMinor/Questions:\n- 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.\n- 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?\n- 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.\n- 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?\n- typo on section 5.1: 'Grid-world problem'\n- 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?)\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "BklQHOmjtH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary of the Paper:\n  \n        This paper proposes a method to address Non Markovian Reward Decision Processes using RL. For this, NMRPDs are transformed into Markovian Decision Processes. The idea is that the reward function can only depend on the last state of the trajectory and the task. A task representation is introduced. This is learned recursively. The proposed approach is evaluated in several experiments.\n\nDetailed comments:\n\nA point of criticism is that it seems that the authors do not compare with similar or related methods in the experiments. In any case, I think that the paper is interesting and will receive the attention of the community.\n\nThe paper is well written in general with only some typos: E.g.\n\n\"that separate\"\n\n\"these proposition\"\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers a special case of decision making processes with                                                               
non-Markovian reward functions, where conditioned on an unobserved task-label                                                      
the reward function becomes Markovian.                                                                                             
A semi-supervised loss for learning trajectory embeddings is proposed.                                                             
The approach is tested on a multi-task grid-world environment and ablation                                                         
studies are performed.                                                                                                             
                                                                                                                                   
The reviewers mainly criticize the experiments in the paper. The environments                                                      
studied are quite simple, leaving it uncertain if the approach still works in                                                      
more complex settings.                                                                                                             
Apart from ablation results, no baselines were presented although the setting is                                                   
similar to continual learning / multi-task learning (with unobserved task label)                                                   
where prior work does exist.                                                                                                       
Furthermore, the writing was found to be partially lacking in clarity, although                                                    
the authors addressed this in the rebuttal.                                                                                        
                                                                                                                                   
The paper is somewhat below acceptance threshold, judging from reviews and my own                                                  
reading, mostly due to lack of convincing experiments. Furthermore, the general setting                                            
considered in this paper seems quite specific, and therefore of limited impact.
Decision: Reject