Learning non-Markovian Decision-Making from State-only Sequences
Authors: Aoyang Qin
Feng Gao
Qing Li
Song-Chun Zhu
Sirui Xie
Venue: NeurIPS 2023 poster (2023)
Keywords: Sequential Decision Making
Generative Model
Imitation Learning

Abstract: Conventional imitation learning assumes access to the actions of demonstrators, but these motor signals are often non-observable in naturalistic settings. Additionally, sequential decision-making behaviors in these settings can deviate from the assumptions of a standard Markov Decision Process (MDP). To address these challenges, we explore deep generative modeling of state-only sequences with non-Markov Decision Process (nMDP), where the policy is an energy-based prior in the latent space of the state transition generator. We develop maximum likelihood estimation to achieve model-based imitation, which involves short-run MCMC sampling from the prior and importance sampling for the posterior. The learned model enables $\textit{decision-making as inference}$: model-free policy execution is equivalent to prior sampling, model-based planning is posterior sampling initialized from the policy. We demonstrate the efficacy of the proposed method in a prototypical path planning task with non-Markovian constraints and show that the learned model exhibits strong performances in challenging domains from the MuJoCo suite.

Learning non-Markovian Decision-Making from State-only Sequences
Aoyang Q.n Feng Gao Qing Li
Song-Chun Z2u Sirui X
12,4
Department of Automation, Tsinghua University Beijing Institute for General Artificial Intelligence (BIGAI)
3 Department of Statistics, UCLA School of Artificial Intelligence, Peking University Department of Computer Science, UCLA
Abstract
Conventional imitation learning assumes access to the actions demonstrators, but these motor signals often non-observable in naturalistic settings. Additionally, sequential recision-making behaviors in these settings can deviate from the assump- tions of standard Markov Decision Process (MDP). To address these challenges, we explore deep generative modeling of state-only sequences with non-Markov Decision Process (nMDP), where the policy is an energy-based prior in the latent space of the state transition generator. We develop maximum likelihood estimation learn both the transition and the policy, which involves short-run MCMC sam- pling from the prior and importance sampling for the posterior. The learned model enables decision-making as inference: model-free policy execution equivalent to prior sampling, model-based planning is posterior sampling initialized from the policy. We demonstrate the efficacy of the proposed method planning task with Non-Markovian constraints and show that the learned model exhibits strong performances in challenging domains from the MuJoCo suite.
prototypical path
Introduction
Imitation from others is a prevalent phenomenon in humans and many other species, where individuals learn by observing and mimicking the actions of others. An intriguing aspect of this process is the brain's ability to extract motor signals from sensory input. This remarkable capability facilitated by mirror neurons [1, 2]. which respond to observations if the imitator is performing the actions themselves. In conventional imitation learning [3, 4] and offline reinforcement learning [5], action labels have served proxies for mirror neurons. But it is important to recognize that they actually productions of human interventions. Given the recent advancements in AI, now is probably an opportune time to explore imitation learning in more naturalistic setting.
While the setting of state-only demonstrations not common, there are certain exceptions. For example, Inverse Reinforcement Learning (IRL) initially formulated the problem state visitation matching [6], where demonstrations consist solely of state sequences. Subsequently, this state- only setting was rebranded as Imitation Learning from Observations (ILfO), which introduced the generalized formulation of matching marginal state distributions [7. 8). These methods typically rely (TD) learning techniques [9]. One consequence
on the Markov assumption and Temporal Difference of this assumption, previously believed to be advantageous, is that sequences with different state orders treated equivalent. However, the success of general sequence modeling [10] has challenged
indicates equal contribution. Correspondence: Sirui Xie (srxie @ ucla.edu). Code and data are available https://ithub..om//gge https//gghubboomm//gggg////////u
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

42
44
41
(a) Policy and transition in MDP
(b) Policy and transition in nMDP
Figure I: Graphical model of policy and transition in standard Markov Decision Process and non- non-Markov Decision Process. Reward variables are omitted in the probahilistic graph to emphasize the difference in dependency between actions and states. nMDP is natural generalization of standard MDP.
this belief, leading to deep reflections. Notable progresses since then include an analysis of the expressivity of Markovian rewards [11] and series of sequence models tailored for decision-making problems [12-15]. Aligning with this evolving trend, we extend the state-only imitation learning problem encompass non-Markovian domains.
In this work, we propose a generative model based on non-Markov Decision Process (nMDP), in which states are fully observable and actions latent. Unlike existing monolithic sequence models, we factorize the joint state-action distribution into policy and causal transition according to the standard Markov Decision Process (MDP). To further extend to the non-Markovian domain, we condition the policy on sequential contexts. The density families of policy and transition are consistent with conventional IRL [4]. We refer to this model as Latent-action nor-Markov Decision Process (LanMDP). Because the actions are latent variables following Boltzmann distribution, the present model is closely related the Latent-space Energy-Based Model (LEBM) [16]. To learn the latent policy by Maximum Likelihood Estimation (MLE), we need to sample from the prior and the posterior. We sample the prior using short-run Markov Chain Monte Carlo (MCMC) [17], and the posterior using importance sampling, Specifically, the proposed importance sampling sidesteps back-propagation through time in posterior MCMC with single-step lookahead of the Markov transition. The transition is learned from self-interaction.
Once the LanMDP is learned, it can be used for policy execution and planning through prior and posterior sampling, or other words, policy as prior, planning as posterior inference [18, 19]. In our analysis, derive objective of the non-Markovian decision-making problem induced from the MLÉ. We show that the prior sampling at each step can indeed lead to optimal expected returns. Almost surprisingly, find that the entire family of maximum entropy reinforcement learning [4, 20- 24] naturally emerges from the algebraic structures in the MIFE of latent policies. This formulation avoids the peculiarities of maximizing state transition entropy in prior arts [20, 24]. We also show that when a target goal state is in-distribution, the posterior sampling is optimizing a conditional variant of the objective, realizing model-based planning. In our experiments, we validate the necessity and efficacy of our model in learning to sequentially plan cubic curves, and illustrate an over-imitation phenomenon [25, 26] when the learned model repurposed for goal-reaching. We also test the proposed modeling, learning, and computing method in MuJoCo, domain with higher-dimensionn dimensional state and action spaces, and achieve performance competitive to existing methods, even those that learn with action labels.
2 Non-Markov Decision Process
The most well-known sequence model of decision- makinn process is Markov Decision Process. A MDP is a tuple M = (S, A, T, R, p, H) that contains a set 5 of states, a set A of actions, a transition T: S + II(S) that returns for every state s, and action 0r distribution over the next state 8 a reward function Rt S x A + R that specifies the real-valued reward received by the agent when taking action a, in state s:; initial state distribution p II(S); and horizon H that is the maximum number of actions/steps the agent can execute in one episode. A solution to an MDP is policy that maps states to actions, S I(AA). The value of policy æ, V (*)) E,, D R(s;){so = s] is the expected cumulative reward (i.e. return) when executing with this policy starting from state The state-action value of policy is Q*)(s, dz) R(st, az) (ssssts LV* [V (s++
The optimal policy n can maximize either [V* [V*(s))], or the same objective plus the policy entropy [27, 4, 22]. The Markovian assumption supports the convergence
series of TD-learning methods [9], whose reliability in non-Markovian domains is still an open problem.

---

A Mor-Markov Decision Process is also a tuple M AS, p. H). It generalizes MDP by allowing for non- non-Markovian transitions and rewards [28]. Notably, assuming Markovian transition and non-Markovian reward is usually sufficient since a state space with non-Markovian transition can be represented with its Markov abstraction [29]. Markov abstraction can be done either by treating the original space as observations generated from the latent belief state in a Partially Observable Markov Decision Process (POMDP) [30], or by projecting historic contexts into an embedding space for sequence pattern detection [31, 32, 28J. Presumably, it is statistically more interesting in deep learning to focus our attention on non-Markovian domains where the temporal dependencies in transition and reward differ. Therefore, without loss of generality,
assume that the state transition Markovian T : S x A - IS(S, while the reward not [33. 11], i.e. R : S - R, with S* denotes the set of all finite non compy state sequences with length smaller than H. Obviously, the policy should also be non-Markovian π S - IT(A). Check Figure 1 for a probabilistic graphical model of the generation process of state sequences from policy.
3 Learning and Sampling
3.1 Latent-action nMDP
A complete trajectory is denoted by
= {su, Go $1, "1.'' ,r),
(1)
where T' the maximum length of all observed trajectories and T & H. The joint distribution of state and action sequences can be factorized according to the causal assumptions in nMDP:
pe (C) = Pa (col=)))p(s 10000 an) Pa
(2)
= p(so) I Ti Pa (a(a (1 az),
where Pa (ag) 10) is the policy model with parameter a, Pa (,-1,, is the transition model with parameter B, both of which are parameterized with neural networks, (a, (). p(so) is the initial state distribution, which can be sampled as a black box.
The density families of policy and transition are consistent with the conventional setting of IRL [4]. where the transition describes the predictable change state as a single-mode Gaussian, 8t+1 ((gs(8,, (z), o²), and the policy accounts for bounded rationality as Boltzmann distribution with state-action value as the unnormalized energy:
Pa (aelos)):)
exp (Ja(a)) 80:)):
((a, sox))
where (az; so:z) is the negative energy, Z(a, so.z) S exp(fa s0:4) (a:;))))) is the normalizing constant given the contexts 5y.t. We discuss a general push-forward transition in Appx A.3.
Since we can only observe state sequences, the aforementioned generative model can be understood as a sequential variant of LEBM [16], where the transition serves as the generator and the policy is a distribution action sequences are:
latent prior. The marginal distribution of state sequences and the posterior
(o(So:T) po(SorT, -0.T- p=(00TT-1/0.T) Po(Su:T, 00:T-1) Po(5o:T)
3.2 Maximum likelihood learning
We need to estimate (a, Suppose we observe offline training examples: (E),, 1, n, E = [o s1 .... s.... The log-likelihooe function is:
(o) 1"____ope(( log
(5)
Denote posterior distribution of action sequence (1 as Pp(A))) for convenience where A and S means the complete action and state sequences in trajectory. The full derivation of the learning method can be found in Appx A.2, which results in the following gradient:
a log (E = Ep (A[S)
(a (ag V log (9 18,, az))].
(6)
policy/prior
transition
3

---

Due to the normalizing constant ((a, s0:t) in the energy-based prior Pa. the gradient for the policy term involves both posterior and prior samples:
(a,((S) (A [Va log (a
(A(() [Vafalar; so:)] so:))]pp.... (a.) Vafa(ae: su:z }
where (S)) denotes the expected gradient policy term for time step Intuition can be gained from the perspective of adversarial training [34, 35]: On one hand, the model utilizes action samples from the posterior po( (A[S) as pseudo-labels to supervise the unnormalized prior each step. On the other hand, it discourages action samples directly sampled from the prior. The model converges when prior samples and posterior samples are indistinguishable.
To ensure the transition model's validity, it needs to be grounded in real-world dynamics Tr when jointly learned with the policy. Otherwise, the agent would be purely hallucinating based the demonstrations, Throughout the training process, we allow the agent to periodically collect on-policy data {(s), di, 11+1), 1, 2.... ,,, t 1,2,-.. with (a (o.(e))))) and update the transition with composite likelihood [36]
T Σ i- Σ logps(8i+11
Loamp (3) (0) + (3), Lon (g)
(8)
3.3 Prior and posterior sampling
The maximum likelihood estimation requires samples from the prior and the posterior distributions of actions. It would not be a problem if the action space is quantized. However, since we target general latent action learning, we proceed to introduce sampling techniques for continuous actions.
When sampling from a continuous energy space, short-run Langevin dynamics [17] can be an efficient choice. For target distribution (a). Langevin dynamics iterates dg+1 ak + sV az log (axx) + v28CK, where l indexes the number of iteration, is small step size, and e is the Gaussian white noise. π (a) can be either the prior Pa (a. 80:e) or the posterior pe (A] S). One property of Langevin dynamics that is particularly amenable for EBM is that we can get rid of the normalizing constant. So for each the iterative update for prior samples is
01,k+1 0t,k sV ae. fa (a Spa) 225k..
(9)
Given state sequence S0:7 from the demonstrations, the posterior samples at each time step come from the conditional distribution p(at) so.T). Notice that with Markov transition, we can derive
T-1 = pe(a)(so.r)
2'-1
pe pe(co:T-1s0orT)
== pa (arl (0r(50:++)).
(10)
Eq. (10) reveals that given the previous and the next subsequent state, the posterior can sampled at each step independently. So the posterior iterative update is
0+ Ct.k + 8 Vaa. (log (0r, 80:e) + log
a+,x)) + + 28Ek-
(11)
policy/prior
transition
Intuitively, action samples at each step are updated by back prokppropagttion from its prior energy and single-step lookahead. While gradients from the transition term are analogous to the inverse dynamics Behavior Cloning from Observations (BCO) [37], it may lead to poor training performance due to non-injectiveness in forward dynamics [38].
We develop alternative posterior sampling method with importance sampling to overcome this challenge. Leveraging the learned transition, we have
(5(8 ar)
Po (or (80:++1) Eps (ax [pa(st+1|sa 8t, a:)]
Pex (at (8or).
(12)
Let clas; 90.44) Ep. (aelso)) (ps(Sc+1|so, dz)], posterior sampling from ((50)) can be realized by adjusting importance weights of independent samples from the prior Pa (o:e). in which the estimation of weights involves another prior sampling. this way, we avoid propaptoogg through non-injective dynamics and save some computation overhead.
To train the policy, Eq. (7) can now be rewritten as
pe p at) V Vafa(ari sox) - Ep.(asloou) Cafa(ariso:)] (13)
8a, (o.((S) ) = E8 (ar so
c(ar; 80441)

---

Deaksion-making as Inference
In Section 3, we present our method within the framework of probabilistic inference, providing self-contained description. However, from pecision-mmking perspective, the learned policy may appear arbitrary. In this section, we establish a connection between probabilistic inference and docision-making contributing novel analysis that incorporates the latent action setting, the non- Markovian assumption, and maximum likelihood learning. This analysis is inspired by, but distinet from, previous studies on the relationship between these two fields [39, 20, 40, 41, 24].
4.1 Policy execution with prior sampling
Let the ground-truth distribution of demonstrations be p" ($o:T). and the learned marginal distributions of state sequences be pa (So:T). Eq. (5) in Section 3.2 is an empirical estimate of
(s [log po (e(so (so:r) }] = (so) [log (su)) + (x1rr [log (s1.r [so]]]
(14)
We can show that sequential decision-making problem can be constructed to maximize the same objective. Our main result is summarized as Theorem
Theorem 1. Assuming the Markovian transition Pas (8 at) is known, the ground-truth conditional state distribution p ($1+1) (0:t) for demonstration sequences is accessible, we can construct a sequential decision-making problem, based on a reward function T Ta($141, 80:t) log S (a (o: ($t+1]8r, at) de for an arbitrary energy-based based policy Pa(at) Soa). ). Its objective
T Σ. ( [VPo (80:)) Eyp (SU:T) [ ra Ea (0
where Vpu (so:) == Ep (s (ow 1= (Sk+1 so:k)] ] is the value function for Po- This objective yields the same optimal policy the Maximum Likelihood Estimation (so pe (So.T)]
If we further define reward function To Ta (8t41, Ot, 80:) == (8 80a) + log Pa (0a) to con- struct Q function for Pa
QPa (at; 80:1) == Enp (sesalaar)) [Ta(s141, at, 80.) VPa (80:+1)]]-
The expected return of Q Sus) forms an alternative objective
Ep (a.1=..)))))).. so. 10Q% (ag; so:))] VPa (sua) Ha(aa (a))s)) - - (p (aa
that yields the same optimal policy, for which the optimal Q* (ax; S0:z) can be the energy function. Only under certain conditions, this sequential decision-making problem is solvable through non- Markovian extensions of the maximum entropy reinforcement learning algorithms.
Proof. See Appx B.
The constructive proof above offers profound insights. By starting with the hypothesis of latent actions and MLE, and then considering known transition and accessible ground-truth conditional state distribution, we witness the automatic emergence of the entire family of maximum entropy (inverse) RL. This includes prominent algorithms such as soft policy iteration [20], soft Q learning [22] and soft Actor-Critic (SAC) [23]. Among them, SAC is the best-performing off-policy RL algorithm in practice. Unlike the formulation with joint state-action distribution [20, 24), our formulation avoids the peculiarities associated with maximizing state transition entropy. The choice of the maximum entropy policy aligns naturally with the objective of capturing uncertainty in latent actions, and it offers inherent advantages for exploration in model-free learning [42, 22].
4.2 Model-based planning with posterior sampling
Lastly, with the learned model, we can do posterior sampling given any complete incomplete state sequences. The computation involved is analogous to model-based planning. In Section 3.3, we introduce posterior sampling with short-run MCMC and importance sampling when we have the target next state, which generalizes all cases where the targets of immediate subsequent states are given. Here we introduce the complementary case, where the goal state sy is given the target.
5

---

The posterior of actions given the sequential context So:t and a target goal state is
Po (t:T S0:s, (
T-t-1 - - k-o (ps(s+**11a4tt Se+ Pa ptt.
(15)
in which all Gaussian expectation E- can be approximated with the mean [43]. Therefore, a;:T' can be sampled via short-run MCMC with Varr log po(aer, 8T) (r:1))))) back propagated through time. The learned prior can be used to initialize these samples and facilitate the MCMC mixing.
5
Experiments
5.1 Cubic curve planning
To demonstrate the necessity of mon-Markovian value and test the efficacy of the proposed model, we designed a motivating experiment. Path planning is a prototypical decision-making problem. in which actions are taken in a 2D space, with the x-y coordinates without loss of generality, we can further assume 2; to change with constant speed h, such that the action is yyt. Obviously, the transition model (æ++1, Me+1) (æ: + h, ye + Ays) is Markovian.
states. To simplify the problem
Path planning can have various objectives. Imagining you are passenger of an autonomous driving vehicle. You would not only care about whether the vehicle reaches the goal without collision but also how comfortable you feel. To obtain comforting smoothness and curvature, consider y is constrained to be cubic polynomial F(x) ax. + bxz + cr + d of where (a, d) are polynomial coefficients. Then the policy for this sreision-making problem
Mar-Markovian.
To see that, suppose we are at (It, y1) at this moment, and the next state should be (xt + h, F(I, +aree+10 hi).
With Taylor expansion, we know F(x; + h) F(xx) + F (x()) + 2: ("(xx)/2 + F n2, so we have a representation for the policy, <Ayy, (ra, y1) F'(xx)h + =="(x)) 122 Fm)())) 1 However, our representation of state only gives us (1r) so we will need to estimate those derivatives. This can be done with the finite difference method we happen remember the previous states (I:-1, 1t-1), (t=-), .... (Z1-3, 31-3). Taking the highest order derivative for example, (x;) = (y: 3y--1 + 3yt-2 Yt-
3/-3)//t 3)/h² 3. is thus apparent that the policy would not be possibly represented if we are Markovian or don't remember sufficiently many prior states.
This representation of policy is what models should learn through imitation. However, they should not know the polynomial structure a priori. Given a sufficient number of demonstrations with different combinations of polynomial coefficients, models expected to discover this rule by themselves. This experiment is a minimum viable prototype for general non-Markovian decision-making. It can be easily extended to higher-order and higher-dimensional state sequences.
Setting We employ multi-layer perception (MLP) for this experiment. Demonstrations can be generated by rejection sampling. We constrain the demonstration trajectories to the (x, 3) E (-1, (-1,1) area, and randomly select and y at x = -1 and x = 1. Curves with third-order coefficients less than 1 are rejected. Otherwise, the models may be confused in learning the cubic characteristics.
Non-Markovian dependency and latent mergy-based policy are two prominent features of the proposed model. To test the causal role of non-Markovianness, we experiment with context length (1,2, 4, 6). Context length refers to how many prior states the policy is conditioned on. When it 1, the policy is Markovian. From our analysis above, we know that context length 4 should be the ground truth, which helps categorize context lengths 2 and 6 into insufficient and excessive expressivity. With these four context lengths, we also train Behavior Cloning (BC) models the control group. In a deterministic environment, there should not be a difference between BC and BCO, as the latter basically employs inverse dynamics to recover action labels. For model, this simple transition can either be learned or implanted. Empirically, we don't 't notice a significant difference.
Performance is evaluated both qualitatively and quantitatively. As a 2D planning task, visualization of the planned curves says a thousand words. In our experiment, we take h = 0.1, so the planned paths are rather discretized. We use mean squared error to fit a cubic polynomial and use the residual error as a metrie. When calculating the residual error, we exclude those with a third-order coefficient is less than 0.5. Actually, the acceptance rate itself is also viable metric. It is the number of accepted

---

Markovian
(b) Context Length
(c) Context Length
(d) Demonstration
vio
-15
16
45
(e) Acceptance Rate
(f) Residual Error
(g) BC Context Length
(h) Goal-reaching Planning
Lasttop
Enclosed Mamterien Raverd
Laskle Comeet
Lesiti
Costorn Roadss
corsus
Cartack
100
Figure 2: Results for cubic curve generation. (a-c) show curves generated at training step 3000 with context
lengths 1, 2, 4. Starting points are randomly selected, and all following are sampled from the policy model. Only
models with context length 4 learn the cubic characteristic. (d) shows curves from demonstrations. (e) and (1) present the smoothed acceptance rate and fitting residual of trajectories from policies with context lengths 1, 2. 6. The x-axis is the training steps. (e)(f) are better he viewed together because residual errors will only be calculated the acceptance rate above a threshold. For context length 1, the acceptance rate is always zemo for BC, so it is not plotted here. (g) shows curves planned by BC with context length 2. It can be compared with (h). Interestingly. LanMDP with context length 2 demonstrates certain cubic characteristics when trained sufficiently long, while the BC counterpart only plans straight lines. (h) is the result of goal-reaching planning, where the dashed line comes from designdd Markov reward, the solid line from the trained LanMDP.
trajectories divided by the total number of testing trajectories. complementary to the residual error because it directly measures the understanding of cubic polynomials.
Results Fig. 2(a-c) show paths generated with LanMDP after training for 3000 steps. They have context lengths 1, 2. 4 respectively. Compared with demonstrations in Fig. 2(d), only paths from the policy with context length 4 exhibit cubic characteristics. The Markovian policy totally fails this task. But it still generates curves, rather than straight lines from Markovian BC (see Fig. A1). The policy with context length can plan cubic-like curves at times. But some of its generated paths are very different from demonstrations. To investigate this interesting phenomenon, we plot the training curves in Fig. (f)) While LanMDP policies with sufficient and excessive expressivity achieve high acceptance rates at the very beginning of the training, policies with Markovian and insufficient expressivity struggle to generate expected curves at the same time. Remarkably, as training goes by, the policy with context length 2, which can only approximate the ground- -ruth action in the first order, gradually improves in acceptance rate and residual error. This observation is consistent with Fig. 2(b).
Continuing our investigation, we plot curves generated by its BC counterparts in Fig. 2(g) but only see straight lines like the Markovian BC. Therefore, we conjecture that the LanMDP policy with length context 2 leverages its energy- multi- to capture the uncertainty induced by marginalizing part of the necessary contexts. The second-order error in Taylor expansion is possibly remedied by this, especially after long-run training. The Markovian LanMDP policy, however, fails to unlock such potential because it cannot even figure out the first-order derivative.
There are some other note-worthy observations. (i) Excessive expressivity does not impair perfor- mance, it just requires more training. As shown in Fig. (f)) the end of training, LanMDP policies with context length 6 perform as well as ones with context length 4. This demonstrates LanMDP's potential in inducing proper state abstraction from sequential contexts. TD learning,
however, has been shown to be incapable of such abstraction in a prior work [44]. (ii) BC policies with sufficient contexts do not perform as well as LanMDP, as shown in Fig. ((e) We conjecture that this might be attributed to the larger compounding error in BC. To shield the influence of com- pounding errors, we design an experiment where we measure the residual error of the next state after filling the historical contexts in the learned LanMDP context 4 and BC context 4 with expert states, rather than sampled states. The errors are both around 0.0004 for LanMDP and BC, closing the gap in Fig. 2f. The implication seems to be LanMDP is more robust to compounding errors than BC.
7

---

-0.1
-0.4
-0.8
2 -24
-2 450
2
-221
Figure 3: Mapping a generated curve to a trajectory in the value landscape. We train a neural network to approximate the non-Markovian value function constructed with the learned policy and transition following Theorem 1, and then visualize the landscape by projecting all top view (left) and front view (middle). Starting from a random initial state, decisions are sequentially made according to the learned policy, leaving a curve in the original state space (right) and a trajectory on the value landscape. It is evident that the non-Markovian value increases monotonically along the trajectory.
states 2D space with
To verify our analysis in Section 4, we visualize the non-Markovian value function defined in Theorem in Fig. 3. The value increases monotonically when the policy generates the cubic curve step by step. In an animation we included on the project homepage', we further show that the action sampling at each state yields the highest value in reachable next states.
At last, we study repurposing the learned sequence model for goal-reaching. This is inspired by a surprising phenomenon, over-imitation, from psychology. Over-imitation occurs when imitators copy actions unnecessary for goal-reaching. In seminal study [25], 3- to 4-year-old children and young chimpanzees were presented with a puzzle box containing hidden treat. An experimenter demonstrated a goal-reaching sequence with both causally necessary and unnecessary actions. When box was opaque, both chimpanzees and children tended to copy all actions. However, when a transparent box was used such that the causal mechanisms became apparent, chimpanzees omitted unnecessary actions, while human children imitated them. As shown in Fig. 2(h), planning with the learned non non-Marke Mon-Markovian value indeed leads to casually unnecessary states, consistent with the demonstrations. Planning with designed Markov rewards produces causally shortest paths.
5.2 Mujoco control tasks
We also report the empirical results of our model and baseline models on MuJoCo control tasks: Cartpole-v1, Reacher-v2, Swimmer-v3, Hopper-v2 and Walker2d-v2. We train an expert for each task using PPO [45]. They are then used generate 10 trajectories for each task as demonstrations. Actions are deleted in the state-only setting.
Setting We conduct comparative analysis of LanMDP against several established imitation learning baselines including BC [46]. BCO [37], GAIL [35], GAIFO [7], and OPOLO [38]. Note that BC and GAIL have access action labels, positioning them as the control group. The experimental group includes state-only methods such as LanMDP, BCO, GAIFO, and OPOLO. The expert is the idealized bascline. For all tasks, we adopt the MLP architecture for both transition and policy. The input and output dimensions are adapted to the state and action spaces in different tasks, and so are short-run sampling steps. Sequential contexts are extracted from stored episodic memory. The number of neurons in the input and hidden layer in the policy MLP varies according to the context length. We use replay buffers to store the self-interaction experiences for training the transition model offline. See Appendix D for detailed information on network architectures and hyper aiper-parameters.
illustrated through learning curves and bar plot in Fig. 4. These learning curves are the average progress across 5 seeds. Scores in the bar plot are normalized relative the expert score. Our model demonstrates significantly steeper learning curves compared to the state-only GAIFO basclines, especially in Cartpole and Walker2d. This illustrates the remarkable data efficiency of model-based methods. Additionally, LanMDP consistently matches or surpasses the performance of BC and GAIL, despite the latter having access to action labels. In comparison to the expert, LanMDP only lags behind in the most complex Walker2d task. However, it still maintains a noticeable margin over other state-only baselines.
Results Results for context length
making

---

Cartpole-v1 (10 traj.)
Swimmer-v3 (10 traj.)
Reacher-v2 (10 traj.)
100
Return (Value)
Return (Value)
300
20
-49
Return
-60
expert
bc
100
-80
gaifo
gall
ebm
Online Samples
Online Samples
Online Samples
Ied
H4 (10 traj.)
Walker2d-v4 (10 traj.)
2000
Normalized Score
Return (Value)
Return (Value)
1100
2000
0.6
2500
3000
0.4
3000
0.2
0.5
1.0
1.5
2.0
Sampies
2.5
3.0 3.5
0.5
1.0 1.5
Online Samples
20
2.5
3.0
35
4.8
0.8
Carppste
Readee
Salmmer
Hopper
Weleerb
Figure 4: Results MuJoCo. for our LanMDP (red), BC (orange), BCO (green), GAIL, (purple), GAIFO (cyan), OPOLO (gray), expert (blue). The learning curves are obtained by averaging progress over 5 seeds. We only plot curves for interactive learning methods. The scores of all other methods are plotted as horizontal lines. LanMDP does not have performance scores in the first K steps because this data is collected with random policy to the replay buffer, which is then used to train the transition model. K Reacher and Swimmer, 2c5 for Hopper and Walker2d. We include these steps for fair comparisons. LanMDP outperforms existing state-only methods and matches BC, the best- cest-performing statc-action counterpart. The bar plot presents the scores from the best-performngg policy during the training process, averaged across 5 seeds and normalized with the expert mean. The score Reacher offsct by constant before the division of the expert mean to align with the positive scores in other tasks. The expert mean is plotted as horizontal line. Our model clearly stands out in state-only methods, while matching and even outperforming those with action labels. Its scores only lag behind the expert mean in the most complex task. Better viewed in color.
for Cartpole, 2e4 for
Table I: Comparison between Markovian and non-Markovian policy in MuJoCo control task. Context length the number of prior sequential states that the policy depends on, with the current one included. Recall that these MuJoCo tasks are inherently Markovian, thanks to highly specified state features. Nevertheless, non-Markovian policies perform par with Markovian ones and BC, despite having higher expressivity than sufficient. The best and the sccond-best results are highlighted. Results are averaged over 5 random seeds.
TASK
CONTEXT
CONTEXT 2
CONTEXT I
BC
CARTPOLE
500.00
5.0000+0.00
500.00=0.00
474.80 1 8.87
REACHER
-0..91
-9.70=0.64
-9.00+0.87
-8.76 0.12
SWIMMER
42.6711.66
43.5214.31
41.2211.67
3..6411.76
HOPPER
3051.161111.78
3053.911176.5
3045.27+240.45
3083.321156.61
WALKER2D
1703.021228.86
1811.771369.54
1753.46
1839.941376.87
Results for longer context lengths, i.e. the non-Markovian setting, are reported in Table 1, in which the highest return across the training process is listed. Originally invented for studying differentiable dynamics, MuJoCo offers state features that are inherently Markovian. Though a MDP is sufficiently expressive, learning more generalized nMDP does not impair the performance. Sometimes it can even improve a little bit. Due to the limit of time, the maximum context length is only 3. Within the investigated regime, our result is consistent with that reported by Janner et al. [12]. We leave the experiments with longer memory and more sophisticated neural networks to future research.
Table 2 is study of the computational overhead for the sampling techniques involved. The short-run MCMC for posterior inference takes longer than a single step of gradient descent. Replacing it with the proposed importance sampling improves training efficiency by large margin.

---

Table 2: Computational overheads for posterior sampling. importance sampling, and gradient descent (in seconds) one training step. MLP(n,m) means that we implement the policy model as an MLP with m layers and hidden neurons each layer. Results are averaged over 10 epochs. The number of MCMC steps is set to 10, 50 respectively, Replacing posterior sampling with importance sampling improves training efficiency.
TASK
DIM
ARCHITECTURE
10 STEPS
50 STEPS
REACHER
2
11
MLP(150:4)
0.0108/0.007660 000.000000000014.0
04480/0.0350/0.000 0014
SWIMMER
2
MLP(150:4)
0.0100/0.000 00007//000111
00463/0.0330///
HOPPER
3
12
MLP(512:4)
0.0268/0.01 00/400077
0.1403/0.08 0tt.:/0083/00000000
WALKER2D
6
18
MLP(512:4)
0.0282/0.01 01182/00.114/0.00777
84/0.0077
0. 21187/0.0899/0.00
6 Discussion
Related work in imitation learning Earliest works in imitation learning utilized BC [3, 47]. When the training data is limited, temporal drifting in trajectories [48, 49] may occur, which led to the development of IRL. [6, 50, 4, 34, 35J. In recent years, the availability of abundant sequence/video data is not the primary concern, but rather the difficulty in obtaining action labels. There has since been increasing attention in ILfO [52, 53, 7, 38, 8J. a setting similar to ours. Distinguished from existing ILfO solutions, our model probabilistically describes the entire trajectory. In particular, the energy-based model [54, 55] in the latent policy space [16] has been relatively unexplored. Additionally, the capability for model-based planning is also novel contribution.
Limitation and potential impact The proposed model factorizes the joint distribution of state- action sequences into time-invariant causal transition and latent policy modulated by sequen- tial contexts. While this model requires sampling methods, and can be non-negligible for higher- dimensional actions, it is worth noting that action quantization, as employed in transformer-basee models [12, 13], has the potential to reduce the computation overhead. of the diversity of behavior is omitted, similar to other works in the literature of reinforcement Iearn- ing. However, it deserves further investigation since multi- modll density matching is a crucial metric in generative modeling. Importantly, our training objective and analysis are independent of specific modeling and sampling techniques, as long as the state transition remains time-invariant. Given the ability of neural networks to learn approximate invariance through data augmentation [56-59], anticipate that our work will inspire novel training and inference techniques for monolithic sequential decision-makin models [12-15].
our experiments, a measure
Implications in neuroscience and psychology The proposed latent model an amenable frame- work for studying the emergent patterns in the mirror neurons [60, 61], echoing recent studies in grid cells and place cells [62, 63]. When the latent action is interpreted as an internal intention, the inference process is manifestation of Theory of Mind (ToM) [64]. The phenomenon of over- imitation [25, 26, 65] can also be relevant. As shown in Section 5, although the proposed model learns causal transition and hence understands causality, when repurposed for goal-reaching tasks, the learned non- Mar-Mvaonv value can result in "unnecessary" state visitation. It would be interesting to explore if over-imitation is simply an overfitting due excessive expressivity in sequence models.
Conclusion
In this study, we explore deep generative modeling of state-only sequences in non-Markovian domains. We propose model, LanMDP, in which the policy functions as an energy-basse prior within the latent space of the state transition generator. This model learns by EM-style maximum likelihood estimation. Additionally, we demonstrate the existence of a decision decision-making making problem inherent in such probabilistic inference, providing fresh perspective maximum entropy reinforcement learning. To showcase the importance of non Mon-Markovian dependency and evaluate the effectiveness of our proposed model, introduce specific experiment called cubic curve planning. Our empirical results also demonstrate the robust performance of LanMDP across the MuJoCo suite.
Acknowledgment AQ, QL and SZ. are supported by the National Key R&D Program of China (20212ID1152000) FG contributed to this work during his PhD study at UCLA. SX is supported by a Teaching Assistantship from UCLA CS. The authors thank Prof. Ying Nian Wu at UCLA, Baoxiong
10

---

Jia and Xiaojian Ma at BIGAI for their useful discussion. The authors would also like to thank the reviewers for their valuable feedback.
References
[1] Giuseppe Di Pellegrino. Luciano Fadiga, Leonardo Fogassi, Vittorio Gallese, and Giacomo Rizzolatti. Understanding motor events: a neurophysiological study. Experimental brain research, 91:176-180, 1992.
[2] Giacomo Rizzolatti, Leonardo Fogassi, and Vittorio Gallese. Neurophysiological mechanisms underlying the understanding and imitation of action. Nature reviews neuroscience, 2(9): 661-670, 2001.
[3] Gillian M Hayes and John Demiris. A robot controller using learning by imitation. University of Edinburgh, Department of Artificial Intelligence, 1994.
[4] Brian Ziebart, Andrew L Maas, J Andrew Bagnell, Anind K Dey, et al. Maximum entropy inverse reinforcement learning. In Aaai, volume 8, pages 1433-1438. Chicago, IL, USA, 2008.
[5] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643 2020.
[6] Andrew Y Ng and Stuart J Russell. Algorithms for inverse reinforcement learning. In Ieml, volume 1, page 2, 2000.
[7] Faraz. Torabi, Garrett Warnell, and Peter Stone. Generative adversarial imitation from observa- tion. arXiv preprint arXiv:1807.06133 2018.
[8] Wen Sun, Anirudh Vemula, Byron Boots, and Drew Bagnell. Provably efficient imitation learning from observation alone. In International conference machine learning, pages 6045. PMLR, 2019.
[9] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[10] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
[11] David Abel, Will Dabney, Anna Harutyunyan, Mark K Ho, Michael Littman, Doina Precup. and Satinder Singh. the expressivity of markov reward. Advances Neural Information Processing Systems, 34:7799-7812, 2021.
[12] Michael Janner, Qiyang Li, and Sergey Levine. Offline reinforcement learning as one big sequence modeling problem. Advances neural information processing systems, 34: 1273- 1286, 2021.
[13] Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Misha Laskin, Pieter Abbeel, Aravind Srinivas, and Igor Mordatch. Decision transformer: Reinforcement learning via sequence modeling, Advances in neural information processing systems, 14:45084-, 2021.
[14] Michael Janner, Yilun Du, Joshua Tenenbaum, and Sergey Levine. Planning with diffusion for flexible behavior synthesis. In International Conference on Machine Learning, pages 9902-9915. PMLR, 2022.
[15] Anurag Ajay, Yilun Du, Abhi Gupta, Joshua Tenenbaum, Tommi Jaakkola, and Pulkit Agrawal. Is conditional generative modeling all you need for decision making? In The Eleventh International Conference on Learning Representations, 2023. URL https:// set/foruumid==sPPfo20
[16] Bo Pang, Tian Han, Erik Nijkamp. Song-Chun Zhu, and Ying Nian Wu. Learning latent space energy-based prior model. Advances Neural Information Processing Systems, 33: 21994-22008, 2020.
11

---

[17] Erik Nijkamp, Mitch Hill, Song-Chun Zhu, and Ying Nian Wu. Learning non convergen non non-persistent short-run meme toward energy- model. Advances in Neural Information Processing Systems, 32, 2019.
[18] Hagai Attias. Planning by probabilistic inference. In International workshop on artificial intelligence and statistics, pages 9-16. PMLR, 2003.
[19] Matthew Botvinick and Marc Toussaint. Planning as inference. Trends in cognitive sciences, 16 (10):485 488, 2012.
[20] Brian D Ziebart. Modeling purposefuul adaptive behavior with the principle of maximum causal entrpy. Carnegie Mellon University, 2010.
[21] Roy Fox, Ari Pakman, and Naftali Tishby. Taming the noise in reinforcement learning via soft updates. In 32nd Conference on Uncertainty in Artificial Intelligence 2016, UAI 2016, pages 202-211, Association For Uncertainty in Artificial Intelligence (AUAI), 2016.
[22] Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy- -assdd policies. In International conference on machine learning, pages 1352-1361. PMLR, 2017.
[23] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference on machine learning, pages 1861-1870. PMLR, 2018.
[24] Sergey Levine. Reinforcement learning and control as probabilistic inference: Tutorial and review. arXiv preprint arXiv: 1XX5::880500000 2018.
[25] Victoria Horner and Andrew Whiten. Causal knowledge and imitation/emulation switching in chimpanzees (pan troglodytes) and children (homo sapiens). Animal cognition, 8:164-181, 2005.
[26] Derek E Lyons, Andrew G Young, and Frank C Keil. The hidden structure of overimitation. Proceedings of the National Academy of Sciences, (04(50):17511-1955)) 2007.
[27] Emanuel Todorov. Linearly-solvabll solvable markov decision problems. Advances neural information processing systems, 19, 2006.
[28] Ronen Brafman and Giuseppe De Giacomo. Regular decision processes: A model for non- markovian domains. In IJCAI, pages 5516-5522, 2019.
[29] Alessandro Ronea, Gabriel Paludo Licks, and Giuseppe De Giacomo. Markov abstractions for pac reinforcement learning in non-markov decision processes. arXiv preprint arXiv:2205.01053, 2022.
[30] Leslie Pack Kaelbling, Michael I. Littman, and Anthony Cassandra. Planning and acting in partially observable stochastic domains. Artificial intelligence, 101(1-2):99-33, 1998.
[31] Marcus Hutter. Feature reinforcement learning: Part i. unstructured mdps. Journal of Artificial General Intelligence, 1(1):3-24, 2009.
[32] Rodrigo Toro Icarte, Ethan Waldie, Toryn Klassen, Rick Valenzano, Margarita Castro, and Sheila Mcllraith. Learning reward machines for partially observable reinforcement learning. Advances in neural information processing systems, 32, 2019.
[33] Rodrigo Toro Icarte, Toryn Klassen, Richard Valenzano, and Sheila Mcllraith. Using reward machines for high-level task specification and decomposition in reinforcement learning. In International Conference on Machine Learning, pages 2107-2116. PMLR, 2018.
[34] Chelsea Finn, Paul Christiano, Pieter Abbeel, and Sergey Levine. connection between generative adversarial networks, inverse reinforcement learning, and energy-based models. arXiv preprint arXiv:1611.03330 2016.
[35] Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. Advances in neural information processing systems, 29, 2016.
12

---

[36] Cristiano Varin, Nancy Reid, and David Firth. An overview of composite likelihood methods. Statistica Sinica, pages 5-42, 2011.
[37] Faraz Torabi, Garrett Warnell, and Peter Stone. Behavioral cloning from observation. arXiv preprint arXiv; 1805.01954, 2018.
[38] Zhuangdi Zhu, Kaixiang Lin, Bo Dai, and Jiayu Zhou. Off-policy imitation learning from observations. Advances in Neural Information Processing Systems, 33:12402-12413, 2020.
[39] Emanuel Todorov. General duality between optimal control and estimation. In 2008 47th IEEE Conference Decision and Control, pages 1286-4292 IEEE, 2008.
[40] Mare Toussaint. Robot trajectory optimization using approximate inference. In Proceedings of the 26th annual international conference on machine learning, pages 1049-1056, 2009.
[41] Hilbert J Kappen, Vicenç Gómez, and Manfred Opper. Optimal control as a graphical model inference problem. Machine learning, 87:159-182, 2012.
[42] Richard S Sutton. Integrated architectures for learning, planning, and reacting based approximating dynamic programming. In Machine learning proceedings 1990, pages 216-224. Elsevier, 1990.
[43] Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114, 2013.
[44] Jonathan Ferrer-Mestres, Thomas G Dietterich, Olivier Buffet, and Iadine Chades, Solving k-mdps. In Proceedings of the International Conference on Automated Planning and Scheduling. volume 30, pages 110-118 118, 2020.
[45] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 0634776777 2017.
[46] Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 661-668.
JMLR Workshop and Conference Proceedings, 2010.
[47] Ramesh Amit and Maja Matari. Learning movement sequences from demonstration. In Proceedings 2nd International Conference on Development and Learning. ICDL 2002, pages 203-208, IEEE, 2002.
[48] Christopher G Atkeson and Stefan Schaal. Robot learning from demonstration. In JCML, volume 97, pages 12-20. Citeseer, 1997.
[49] Brenna D Argall, Sonia Chernova, Manuela Veloso, and Brett Browning. A survey of robot learning from demonstration. Robotics and autonomous systems, 57(5):469 483, 2009.
[50] Pieter Abbeel and Andrew Y Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the 21 international conference on Machine learning, page 1, 2004.
[51] Nathan D Ratliff, J Andrew Bagnell, and Martin Zinkevich. Maximum margin planning. In Proceedings of the 23rd international conference on Machine learning, pages 729-736, 2006.
[52] Rahul Kidambi, Jonathan Chang, and Wen Sun. Mobile: Model-based imitation learning from observation alone. arXiv preprint 27X. 2021.
[53] YuXuan Liu, Abhishek Gupta, Pieter Abbeel, and Sergey Levine. Imitation from observation: Learning to imitate behaviors from raw video via context translation. In 2018 IEEE International Conference on Robotics and Automation (ICRA), pages 1118 1225. IEEE, 2018
[54] Song Chun Zhu, Yingnian Wu, and David Mumford. Filters, random fields and maximum entropy (frame): Towards unified theory for texture modeling. International Journal of Computer Vision, 27 1998.
[55] Yann LeCun, Sumit Chopra, Raia Hadsell, M Ranzato, and Fujie Huang. A tutorial on energy- based learning. Predicting structured data, 1(0), 2006.
13

---

[56] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie. and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 9739-9738, 2020.
[57] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. International conference on machine learning, pages 1597-1607. PMLR, 2020.
[58] Misha Laskin, Kimin Lee, Adam Stooke, Lerrel Pinto, Pieter Abbeel, and Aravind Srinivas. Reinforcement learning with augmented data. Advances in neural information processing systems, 33:19884-19895, 2020.
[59] Samarth Sinha, Ajay Mandlekar, and Animesh Garg. S4rl: Surprisingly simple self- ceff-supervision for offline reinforcement learning in robotics. In Conference on Robot Learning, pages 907-917 PMLR, 2022.
[60] Richard Cook, Geoffrey Bird, Caroline Catmur, Clare Press, and Cecilia Heyes, Mirror neurons: from origin to function. Behavioral and brain sciences, 37(2):177-19) 2014.
[61] Cecilia Heyes and Caroline Catmur. What happened mirror neurons? Perspectives on Psychological Science, 17(1):153-168, 2022.
[62] Ruiqi Gao, Jianwen Xie, Song-Chun representation self- self-position coupled with matrix representation of self-motion. arXiv preprint arXiv:1810.05599, 2018.
Chun Zhu, and Ying Nian Wu. Learning grid cells as vector
[63] Rajkumar Vasudeva Raju, Swaroop Guntupalli, Guangyao Zhou, Miguel Lázaro-Gredill and Dileep George. Space latent sequence: Structured sequence learning as unified theory of representation in the hippocampus. arXiv preprint arXiv:22 2022.
[64] Chris L Baker, Rebecca Saxe, and Joshua B Tenenbaum. Action understanding inverse planning. Cognition, 113(3):329-344 2009.
[65] Michael Tomasello. Becoming human: A theory of ontogeny. Harvard University Press, 2019.
[66] Edwin T Jaynes. Information theory and statistical mechanics. Physical review, 106(4):620, 1957.
[67] Sultan Javed Majeed and Mareus Hutter. On q-learning convergence for non-markov decision processes. In IJCAI, volume 18, pages 2546-2555 2552, 2018
[68] Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims. Morel: Model-based offline reinforcement learning. Advances in neural information processing systems, 33:21810-2188 2020.
[69] Thanard Kurutach, Ignasi Clavera, Yan Duan, Aviv Tamar, and Picter Abbeel. Model-ensemble trust-region policy optimization. arXiv preprint arXiv: 1802. 10592, 2018.
[70] Yuping Luo, Huazhe Xu, Yuanzhi Li, Yuandong Tian, Trevor Darrell, and Tengyu Ma. Algo- rithmic framework for modeel-based deep reinforcement learning with theoretical guarantees. arXiv preprint 1fXiiv1807.038855 2018.
[71] Anusha Nagabandi, Gregory Kahn, Ronald S Fearing, and Sergey Levine. Neural network dynamics for model-based deep reinforcement learning with model-free fine-tuning. In 20/8 IEEE international conference robotics and automation (ICRA), pages 7559-7566. IEEE, 2018.
[72] Aravind Rajeswaran, Igor Mordatch, and Vikash Kumar. A game theoretic framework for model based reinforcement learning. In International conference on machine learning, pages 7953-7963. PMLR, 2020.
[73] Will Grathwohl, Kuan-Chieh Wang, Jörn-Henrik Jacobsen, David Duvenaud, Mohammad Norouzi, and Kevin Swersky. Your classifier is secretly an energy based model and you should treat it like one. arXiv preprint arXiv: 1rXiv:1912.03263., 2019.
14

---

[74] Yilun Du and Igor Mordatch. Implicit generation and modeling with energy based models. Advances in Neural Information Processing Systems, 32, 2019.
[75] Pete Florence, Corey Lynch, Andy Zeng, Oscar Ramirez, Ayzaan Wahid, Laura Downs, Adrian Wong, Johnny Lee, Igor Mordatch, and Jonathan Tompson. Implicit behavioral cloning. In Conference on Robot Learning, pages 558-168, PMLR, 2022.
15

---

A Learning and Sampling
A.1 Deep generative modelling
complete trajectory is denoted by
- {so, ao, $1, 01 ... .T-1, ST):
(I)
where T' is the maximum length of all observed trajectories. The joint distribution of state and action sequences be factorized according to the causal assumptions in nMDP:
Po(() p(so)po (aol (s. an) Po (o
IT_ Pa (or)):)))sll (5 az),
= (0)
where Po (0x|800t-) is the policy model with parameter a, ( (188/88:1111 az-1) is the transition model with parameter B, both of which are parameterized with neural networks, (ar, 3). p(80) initial state distribution, which can be sampled black box.
The density families of policy and transition are consistent with the conventional setting of IRL [4]. The transition describes the predictable change in state space, which is often possible to express the random variable 11+1 deterministic variable 5 = g ae e), where an auxiliary variable with independent marginal p(c), and gs(.) (.) is some vector- vector-valued valued function parameterized by B. The policy accounts for bounded rationality as Boltzmann distribution with state-action value as the unnormalized energy:
Pa (ar(a() Z(a, 80:))
exp (fa (ar; so:)),
(3)
where (ay; 80:2) is the negative energy, Z(a, spa)) = S Sexp(Ja(a; (oo))))a is the normalizing constant given the history 8p:t-
Since we can only observe state sequences, the aforementioned generative model can be understood sequential variant of LEBM [16], where the transition serves the generator and the policy a history-conditionn latent prior. The marginal distribution state sequences and the posterior distribution of action sequences
Po( (o:T-1) po(Su:T)
(o(Su:))
po du:r- -d:--)d 1o
(4)
A.2 Maximum likelihood learning
need to estimate (ox, B). Suppose we observe training examples: (E*), = 1,,,.... ,,,, e [o] s.]. The log-likelihood function is:
(( Σ log Pe()))
Denote posterior distribution of action sequence pn(aoT---so.r7 as (o(A) for convenience where
A and S means the complete action and state sequences in trajectory. The gradient of log-likelihood is:
V Pe(E)
Ve log (a $ .T)
= Eps(a
V log (0 "1,"".,,77 [8T]
= Epp(A|s)
V
.1....,. ,87) + + log (o
Epo(A|sT
log au. $1, 01. (81-1.8)
Epp(A|s]
log (esoppssspploooom -
(6)
= E
(log (8x) + a+))
= EpocAISs)
Vo log (ax))0a)
V log (8t+ |st, az
policy/prior
transition
16

---

where the third equation is because of a simple identity (ma(a) (V log To(a)] 0 for any probability distribution (a).). Applying this simple identiy, we also have:
pp (oelsore)
[V log (ar ss:e)
pp. (oelsor)) Va 50.e) V. log Z(a, s0.z)]
Bpa (orlaae)
[V Ja (at; s0:+)] Va log Z ((a, s0:1)-
Due to the normalizing constant Z(a, so:t) in the energy-based prior Pa, the gradient for the policy term involves both posterior and prior samples:
(c, (pl()))) V. log
Po((A(s)
V VaJa TaJa(a: S04) - Va log ((a, Suz)]
(8)
(pA() V fa so:z) Ppa(asloon (so:s)
V fa( 80:)]]
Epu(A[s) V fa fa(e; so.a]] - (a.l(ar [ Vafa S0x)],
where (S) denotes the surrogate loss of policy term for time step L. Intuition can be gained from the perspective of adversarial training [34, 35]: On one hand, the model utilizes action samples from the posterior Po( (A) as pseudo-labels to supervise the unnormalized prior at each step (a, (oxx)- On the other hand, it discourages action samples directly sampled from the prior. The model converges when prior samples and posterior samples are indistinguishable.
To ensure the transition model's validity, it needs to be grounded in real-world dynamics when jointly learned with the policy. Otherwise, the agent would be purely hallucinating based on the demonstrations. Throughout the training process, allow the agent periodically collect self- interaction data with Pa (ax) Sua) and mix transition data from two sources with weight wp:
(S) (AIS) IV logps at) (1 Wg pa
V log (s a,)
A.3 General transition model
We need to compute the gradient of 3 for the logarithm of transition probability in Equation 9, and as we will see in section 3.3, we also need to compute the gradient of the action during sampling actions. The reparameterization [43] is useful since it can be used to rewrite an expectation w.r.t Pa( 2a($++1 (s;, az) such that the Monte Carlo estimate of the expectation is differentiable, so we use expectation:
delta function 8()) to rewrite probability
Pa(s141|se, at) = 8(5111 -
(r).,,,,)))d ar)ds'42
(10)
6(st+1 go(se, ar, e))
Taking advantage of the properties of 8(.):
[())8(=)dr= f(0), 5(f(x)) = En (f((())) 8(x xn),
-(==,
(11)
where / differentiable and have isolated zeros, which Tin we can rewrite the transition probability as:
pa(Stt1/a0 188, ax) = Σ
5(E - 6n )p()dde
ga(ss, at e)
(12)
p(en)
Σ
à de gs(ss at, c)lce..
where G, is the of S1+1 ga at, c). Therefore, if we have differentiable simula- tor V., (l a.) and the analytical form of p(c) then gradient of both a, and / for log p5( (1,8,,,, can be computed.
The simplest situation is:
St+1 go(ss, ar) +e, p(e) o3),
(13)
17

---

In this case, there is only one zero c* for the transition function, St+1 = ga(st, + c", and the gradient of log probability is:
p(c*)
V logpo(sct1ls),
V Vlg
2 (go ar) + +e)l=cc
v log p(E"
(14)
v log Vlgg((8t+1 gs(();
(s g3(8;, Vgo(s)))
A.4 Prior and posterior sampling
The maximum likelihood estimation requires samples from the prior and the posterior distributions of actions. It would not be a problem if the action space is quantized. However, since we target general latent action learning, we proceed to introduce sampling techniques for continuous actions.
When sampling from continuous energy space, short-run Langevin dynamics [17] can be an efficient choice. For a target distribution π (a)) Langevin dynamics iterates 4x++1 ag + 8 ax log ग ((ax) ) + v v2SEk, where k indexes the number of iteration, is small step size, and is the Gaussian white noise. π (a) can be either the prior (ar) so:t) or the posterior p& (A]S). One property of Langevin dynamics that is particularly amenable for EBM is that we can get rid of the normalizing constant. So for each the iterative update for prior samples is
0r,k+1 = 0t,k + V (a 80.) + 2se
(15)
Given state sequence S0:7 from the demonstrations, the posterior samples at each time step a come from the conditional distribution (o:r). Notice that with Markov transition, we can derive
po(a (o:T) = I
2' - pe pa (0.000.))))
Pe(
(16)
The point is, given the previous and the next subsequent state, the posterior can be sampled at each step independently. So the posterior iterative update is
a1 = at.k + s Var, e log pe (o (o.,N)500+11) + 2
0r.k + V ar lo De (80nt ar,,, 8t+1) + V2SEE
(17)
= Gt.k + (log Pro (atx))0=)) log ps
ps( (1++ 1 at)) ) 28Eg.
policy/prior
transition
Intuitively, action samples at each step updated with the energy of all subsequent actions and a single-step forward by back- mack-propagation. However, while gradients from the transition term are analogous to the inverse dynamics in BCO [37]. it may lead to poor training performance due to non-injectiveness in forward dynamics [38].
We develop an alternative posterior sampling method with importance sampling to overcome this challenge. Leveraging the learned transition, we have
P at)
(8:4415 (aslsos)))) [pa(s 191, a:)]
Pa (aelsax)))
(18)
Let c(a:; 10:++) Ep. [ps(Sc+1 dr)], posterior sampling from 1l00o. can be
realized by adjusting importance weights of independent samples from the prior pa (ar (8:)), in which the estimation of weights involves another prior sampling. this way, we avoid back-propagating through non-injective dynamics and save some computation overhead in Eq. (17).
To train the policy, Eq. (8) can now be rewritten as
pa po(s141 at) c(ar; 80:++1
Sa.(SS) (as
Vafa(a;; sox))
Epp(acl [Va s0x)]. (19)
A.5 Algorithm
The learning and sampling algorithms with MCMC and with importance sampling for posterior sampling are described in Algorithm and Algorithm 2.
18

---

Algorithm 1:
LanMDD without importance sampling
Learning iterations N, learning rate for energy-based policy 7/.. learning rate for transition model 778, initial parameters 0g ( 3o), expert demonstrations (s0.r), context length L,, batch size m, number of prior and posterior sampling steps (Ko Ki), prior and posterior sampling step
Input:
sizes 81).
Output: Og (aN,,x')
Reorganize {50:H] } to state sequenec segments (st- 1-+1>" St+1) with length Use energy-based policy with collect transitions to fill in the replay buffer. Use transitions in replay buffer pre-train transition model Sp.
for = 0 to N - do
Demo sampling Sample observed examples (st- (St-L+1,"". ..t.1))
S1+1);
Posterior sampling: Sample {a,) using Eq. (17) with K iterations and stepsize Prior sampling: Sample { 1m using Eq. (15) with Ko iterations and stepsize 80-
Policy learning: Update
04+1 by Eq. (8) with learning rate 1/a-
Transition learning: Update replay buffer with trajectories from current policy model 0t+11 then update 3r to B by Eq. (9) with learning rate 173.
end for
Algorithm 2: LanMDP with importance sampling
Input: Learning iterations N, learning rate for energy-basee based policy Ma. learning rate for transition model 178. initial parameters 0g = (ao, 8o), expert demonstrations {Se.H), ), context length L, batch size m, number of prior sampling steps K and step sizes
Output: 0x (o.N,3x)
Reorganize { { } to state sequenec segments (st- I, .... 8841) with length Use energy-based policy with collect transitions to fill in the replay buffer. Use transitions in replay buffer pre-train transition model Sg.
for t 0 to N do
Demo sampling Sample observed examples (st- (St_L+1."". St+1) - 1
Prior sampling: Sample {ār) using Eq. (15) with Ko iterations and stepsize su-
Policy learning: Update a; 04++1 by Eq. (19) with learning rate 7)-
Transition learning: Update replay buffer with trajectories from current policy model at+1.
then update 3, to 3r+1 1 by Eq. (9) with learning rate 7)3.
end for
19

---

B A Decision-making Problem in MLE
Let the ground-truth distribution of demonstrations be p" (5:T)) and the learned marginal distributions of state sequences be pa (So.r). Eq. (5) is an empirical estimate of
(x > log (o (su:r) (s0)
[log (su) + (ps Dog (11:2 |so]]]
(20)
We can show that a sequential decision-making problem can be constructed to maximize the same objective. To start off, suppose the MLE yields the maximum, will have pa* =p".
Define (*0) (ourrlo))) (S1:T|80)) we can generalize have a V function
(sua)) E,, (sc [lgg p² (st+1r)s0aa)]
(21)
which comes with Bellman optimality equation:
V (soxt) = (e so.e) [r(st-1, 80.4) + V (80r++11)]
(22)
with r($++1, s0.t) == log ($t+1ls00)) log Pa. (aelso:) P3* (54+1|s;, a₂ a))da,, (*(or)) == 0. It is worth noting that the r defined above involves the optimal policy, which may not be known priori.
We can resolve this by replacing with ra for an arbitrary policy (a(ar//o:e) All Bellman identities and updates should still hold. Anyways, involving the current policy in the reward function should not appear to be too odd given the popularity maximum entropy RL [20, 24].
The entailed Bellman update, value iteration, for arbitrary V and a is
(sua)) = (s 1(50.)) [a 1(+1) + V(sus+1)). We then define r(8441, (4,, 80:)) r(s+11, 80:1) + log (ag (0::) construct a Q function:
(23)
Q* (at so.a) (ec [r(s++1 ae sp:t) + V (sa:+1))),
(24)
which entails a Bellman update, Q backup, for arbitrary a, Q and V
(axi Soa) = E (a141 TTa (Su:2) at S(41) + ((sa++1)]
(25)
Also note that the V and Q in identities Eq. (23) and Eq. (25) respectively are not necessarily associated with the policy Pe. Pa(a||so sox). Slightly overloading the notations, we use Qo, Va to denote the expected returns from policy Pa. Pa(a.]so.))
By now, we finish the construction of atomic algebraic components and move on check the relations between them align with the algebraic structure of sequential decision-making problem [9].
We first prove the construction above is valid optimality.
Lemma 1. When fa (az; so.a) = Q* (ax; so.a) - (so:e) Pa(a:lsocl is the optimal policy.
Proof. Note that the construction gives us
(ari so.e)
Ep ( [r( (r($5+1, S0a)) + log Pa# (arls0s) + V V* (s0:r- 1)]
Po (ar(su:t) + E,, (M1411900)) [r(se+1: Sua) + V* +V*(+=V*00 (90:1-1)
(26)
logPa Pa (us)) + {voxe)
Obviously, Q* (ay; So.e) lies in the hypothesis space of fa (ag; s0:)-
Lemma I indicates that we need to either parametrize fa so:t) or Q(a; so:))
While Q" and y are constructed from the optimality, the derived Q" and V measure the perfor- mance of an interactive agent when it executes with the policy Pa (ae Sua). They should be consistent with each other.
Lemma 2. (so.t) and Ep,, loo (ar; so:z)] yield the same optimal policy Pas (axl (ar)) Proof.
E Epa (ox) 80:)) : Eps (celso))) [ ( [r(
80:t) + V* (8(::++)))))
Exp (
[log Pa (rd (8xc) + r(st+1, s0xe) + V (s0:e+1]]]
(27)
-Epe(set [r( 80:2)
Hal (ar (8oze) + V (80:++))
(sox)) Ha (Me((a))))))
> k=tt+ E [Ha (aslsox)))))
20

---

where the last line is derived by recursively applying the Bellman equation in the line above until SU:T and then applying backup with Eq. (23), As an energy-based policy, Pax So:e)'s (ar]Ss:))'s entropy is inherently
maximized [66]. Therefore, within the hypothesis space, Po (01|80.) that optimizes (*(os:) also leads to optimal expected return (a.lee))) (Qaa))(Q(aaa 80:+)]
we parametrize the policy as Pa $oa) exp(Q"(a;: So:)).. the logarithmic normalizing constant log z (8o:z) will be the soft V function in maximum entropy RI. [21-23]
V (Su:) == log exp(Q (ax; Sua)) Sux)
(28)
even if the reward function is defined differently. We further show that Bellman identities and backup updates above can entail RL. algorithms that achieve optimality of the decision-making objective Va, including soft policy iteration [20]
exp( Q (a;: S0+)) Yso.,, k [0, [M: Zau (s0:)
Pas+s (acls0a)
(29)
and soft Q iteration [21]
(oc: - Ep (5 ra(s0 az, st+1) + Ve -soat ac,
(30)
Voott (s0.t) log exp(("** so:r)) Vooit & [0, M...
Lemma pf (st+1|s0a)) accessible and p** (sc+1 (st, oe) is known, soft policy iteration and soft Q learning both converge to Pa* (ar (0:) = PQ* (a, (0::) exp(Q* Suz)) under certain conditions.
Proof. See the convergence proof by Ziebart [20] for soft policy iteration and the proof by Fox et al. [21] for soft Q learning. The latter requires Markovian assumption. But under some conditions, it can be extended non-Markovian domains the same way as proposed by Majeed and Hutter [67]. D
Lemma means given p*(s==* (50:z) and p&** (s1+ [t, ac), we recover pa through reinforcement learning methods, instead of the proposed MLE. So Pa (ar (a:lso)) is a viable policy space for the constructed sequential decision-making problem.
Together, Lemma 1, Lemma and Lemma provide constructive proof for valid sequential cocision-making problem that maximizes the same objective of MLE, described by Theorem 1.
Theorem 1. Assuming the Markovian transition P3* ($t+ 1|s,, a.) is known, the ground-truth conditional state distribution pd (8441 (8:1)) for demonstration sequences is accessible, construct a sequential decision-making problem, based on a reward function ra(#141 80:e) :- log S Pa (a, S0:t) P3s (8t+1/8t, at yaa for an arbitrary mergy-basee policy Pa(as) (0a))))0).. Its objective is
can
Σ (so [VPa (s0z)) Epp (50.r) EE.E" ra(su41 Pa so.k)
( where VPu (80a) := (es4 (Sa)) E (ak 80ck)] is the value function for pa- This objective yields the same optimal policy as the Maximum Likelihood Estimation Eyy (#a.r) [log po (su:r))
If we further define a reward function Ta (8(411, aty 80:) := (8 S0a)) + log Pa (ag/soa) to con- struct Q function for Pa
QBa (ar; sox) = (spe [a a,, so.)) + VPa (802+11]
The expected return of Q (ac; s0:1) forms alternative objective
Eps (a.le.)) IQ (aq; Sux) VP- Ha. ETT Ept IPH (ax [o:x]]
that yields the same optimal policy, for which the optimal Q* (att 80:)) can be the energy function. Only under certain conditions, this sequential decision-makinn problem is solvable through non- Markovian extensions of the maximum entropy reinforcement learning algorithms.
21

---

C More results on Curve Planning
The energy function parameterized by small MLP with one hidden layer and L hidden neurons, where L is the context length. In short-run Langevin dynamics, the number of samples, the number of sampling steps, and the stepsize are 20 and respectively. We use Adam optimizer with learning rate le-4 and batch size 64. Here present the complete result in Fig. A1 with different training steps under context length 4 6, the acceptance rate and residual error of the testing trajectories, as well as the behavior cloning results. We than LanMDP. Also, from the result of context length 6 we can see that excessive expressivity does not impair performance, just requires more training.
that even with sufficient context, BC performs worse
Rate
Residual
Markovian
Context
Cornet
Context Length
400 20
Contoxt
150
00
20 29
40
Context
Training Step 1500
Training Step 2500
Training Step 3000
Training Step 4000
Figure A1: More results for cubic curve generation
D Implementation Details of MuJoCo Environment
This section delineates the configurations for the MuJoCo environments utilized in our research. In particular, we employ standard environment horizons of 500 and 50 for Cartpole-vl and Reacher- v2, respectively. Meanwhile, for Swimmer-v2, Hopper-v2, and Walker2d-v2, we operate within an environment horizon set at 400 as referenced previous literature [52, 68-72]. Additional specifications are made for Hopper-v2 and Walker2d-v2, where the velocity of the center of mass was integrated into the state parameterization [52, 68, 70, 72]. We leverage PPO [45] approach to train the expert policy until it reaches (approximately) 450, -10, 40, 3000, 2000 for Cartpole-v 1, Reacher-v2,
22

---

Swimmer-v2, Hopper-v2. Walker2d-v2 respecccivi It should be noted that all results disclosed in the experimental section represent averages over five random seeds. Comparative benchmarks include BC [46], BCO [37], GAlI. [35], and GAIFO [7]. MobIL. [52] is a recent method for Markovian model-based imitation from observation. However, we failed to reproduce the expected performance utilizing various sets of demonstrations, so it is prudently omitted from the present displayed result. We specifically point out that BC/GAIL algorithms are privy to expert actions, however, our algorithm is not. We report the mean of the best performance achieved by BC/BCO with five random seeds, even though these peak performances may transpire at varying epochs. For BC, we executed the supervised learning algorithm for 200 iterations. The BCO/GAIL algorithms are with equivalent number of online samples as LanMDP for a fair comparison. All benchmarking is performed using a single 3090Ti GPU and implemented using the Py PyTorch framework. Notably, in codebase, the modified environments of Hopper-v2 and Walker2d-v2 utilize MoblL.E's implementation [.2]. Referring to the results in the main text, our presentation of normalized results in bar graph form is derived by normalizing each algorithm's 's performance (mean/standard deviation) against the expert mean. For Reacher-v2, due the inherently negative rewards, first add constant offset of 20 to each algorithm's 's performance, thus converting all values to positive before normalizing them against the mean of expert policy.
We parameterize both the policy model and the transition model as MLPs, and the non- -inearn activation function is Swish and LeakyReLU respectively. We use AdamW to optimize both policy and transition. To stabilize training, we prefer using actions around which the transition model is more certain for computing the expectation over aepporrance-weighee Therefore, we use a model ensemble with two transition models and use the disagreement between these two models measure the uncertainty of the sampled actions. We implement Algorithm 2 for all experiments to avoid expensive computation of the gradient for the transition model in posterior sampling. As for better and more effective short-run Langevin sampling, we use a polynomially decaying schedule for the step size as recommended in [73]. We also use weakly L2 regularized energy magnitudes and clip gradient steps like [74], choosing clip the total amount of change value, i.e, after the gradient and noise have been combined. To realize more delicate decision- decision-making making, another trick in Implicit Behavior Clone [75] is also adopted for the inference/testing stage that we continue rumning the MCMC chain after the step size reaches the smallest in the polynomial schedule until we get twice as many inference Langevin steps as were used during training.
prior distribution in Eq. (19).
prper-parrmeters are listed in Table 3. Other hyperparameters that are not mentioned here are left as default in Py PyTorch. Also, note that the Cartpole-vl task has no parameters for sampling because expectation can be calculated analytically.
Table 3: Hyper- prpemmtrraetter list of MuJoCo experiments
Parameter
Carppolevv
Reacher-v2
Swammer-v2
Hopper-v2
Walker2d-12
Environment Specification
Horizon
500
400
400
400
Expert Performance (2:)
450
-10
40
3000
2000
Transition Model
Architctuuchhiddenllyess)
MLP(64:4)
MLP(64:4)
MLP(128:4)
MLP(512:4)
MLP(512:4)
OptinizerLRR)
3e.3
3e.3
3e-3
3e:3
Batch Size
2500
20000
20000
32768
32768
Replay Butler Size
2500
20000
20000
200000
200000
Policy Model (with context length L)
Acchiectue(hiddeellaesss))
MLP(150*L:4)
MLP(150-L:4)
MLP(150%L:4)
M:1(512
LL))512
Learning rate
le-3
1e-2
1e-2
1e-2
50-3
Batch Size
2500
20000
20000
32768
32768
Nurbber of test trajectories
5
20
20
50
50
Sampling Parameters
Numbber of prior samples
8
8
Number Langevin steps
100
100
100
Langevin initial stepsize
10
10
10
10
Langevin ending stepsize
23


Reviews:
[{"review_id": "PvWYkBx3r1", "reviewer": "Reviewer_tbAW", "summary": "This paper proposes a new approach to imitation learning from observation (ILfO) on a non-Markovian decision process (nMDP). To achieve this, the authors derive their own objective using maximum likelihood estimation, drawing inspiration from deep generative modeling of state-only sequences. After providing a connection between probabilistic inference and decision-making, the authors conduct experiments on cubic curve planning and MuJoCo control tasks.", "questions": "Mentioned in the weakness + following questions\n\n- (related to [Lack of baselines]) In experiments, I believe that at least one of the off-policy ILfO algorithms (e.g., OPOLO) and one of the model-based ILfO algorithms (e.g., MobILE) should be added as baselines.\n- (related to [Exploration]) Compared to MobILE, why does LanMDP not need to consider an exploration term? In addition, is there no risk in a stochastic environment without exploration such as mentioned in weakness part?\n- What is the final objective of LanMDP, which is used for gradient-based updates? Additionally, compared to the baselines (OPOLO and MobILE), what is the main contribution of LanMDP?\n- I think $R: S^+\\rightarrow \\mathbb{R}$ is a generalization of $R(s)$. Is there any reason not to use $R: S^+\\times A^+\\rightarrow \\mathbb{R}$, which is a natural generalization of $R(s,a)$?\n- In equation (13), we need to compute $c(a\\_t;s\\_{0:t+1})$, which involves an expectation over $p\\_\\alpha I believe this part involves intractable integration in the continuous domain. If the authors use MCMC to address this issue, I am curious about the computational time it takes (compared to other baselines).", "limitations": ". ", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "While there are several works addressing ILfO for MDPs, this work appears to be the first attempt to handle ILfO for nMDPs. To this end, the authors derive their own objective based on probabilistic inference.", "weaknesses": "**[Hard to understand]** this paper is hard to understand due to the lack of explanation. For example, there are various policy-like terms as $p\\_\\theta(A|S)$, $p\\_alpha(a\\_t|s\\_{0:t})$, and $p\\_\\theta(a\\_t|s\\_{0:t+1})$. I believe $p\\_\\alpha(a\\_t|s\\_{0:t})$ corresponds to the policy of the current agent in RL. However, in the context of RL, there is no explicit explanation provided for what $p\\_\\theta(A|S)$ and $p\\_\\theta(a\\_t|s\\_{0:t+1})$ correspond to. In addition, the final objective function is not formulated.\n\n**[Lack of baselines]** In the context of RL, there are two ways to improve sample efficiency: off-policy RL and model-based RL. Thus, at least one of the off-policy ILfO algorithms (e.g., OPOLO [1]) and one of the model-based ILfO algorithms (e.g., MobILE [2]) should be considered as baselines.\n\n**[Objective]** First of all, I wonder if the proposed objective (5) is valid in a stochastic environment. Indeed, the learned $p\\_\\beta$ can differ from the true transition in a stochastic environment, although it is possible to learn an accurate transition with enough online samples. Moreover, (8) may also allow for learning an accurate transition with enough online samples, but it is modified without any theoretical justification from the original objective (5).\n\n**[Exploration]** I think LanMDP might fail to obtain a good policy in a stochastic environment (i.e., with stochastic transition probabilities) because there is no exploration. For example, if the algorithm obtains $(s,a,s’)$ during interaction, then there is no need to find other possible actions $a’$ that might be better to reach $s’$ from $s$.\n\n**[Motivation of task]** This work aims to solve ILfO for nMDPs. However, there are no motivating examples explaining why ILfO for nMDPs should be studied. Specifically, even though the reward function is non-Markovian, the expert policy should not necessarily be a non-Markovian expert policy. Moreover, while the expert policy is non-Markovian, it is not clear if existing ILfO algorithms fail to solve ILfO for nMDPs.\n\n**[Motivation of LanMDP]** It is not clear why we should use decision making as inference instead of a simple modification of prior works. Indeed, we can also handle ILfO on an nMDP by modifying MobILE - for example, if we replace $(s,a)\\sim\\mathbb{E}\\_{d^\\pi}$ and $s\\sim D\\_e$ with $\\tau\\sim\\mathbb{E}\\_{\\pi}$ and $\\tau\\_s\\sim D\\_e$ for a non-Markovian policy $\\pi$ and a state-only trajectory $\\tau\\_s$, then it can be used to solve ILfO on an nMDP.\n\n[1] Zhu, Zhuangdi, et al. \"Off-policy imitation learning from observations.\" Advances in Neural Information Processing Systems 33 (2020): 12402-12413.\n\n[2] Kidambi, Rahul, Jonathan Chang, and Wen Sun. \"Mobile: Model-based imitation learning from observation alone.\" Advances in Neural Information Processing Systems 34 (2021): 28598-28611.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your feedback!\n\n> [Hard to understand] this paper is hard to understand due to the lack of explanation. For example, there are various policy-like terms as $p_\\theta(A|S)$, $p_\\alpha(a_t|s_{0:t})$, and $p_\\theta(a_t|s_{0:t+1})$. I believe $p_\\alpha(a_t|s_{0:t})$ corresponds to the policy of the current agent in RL. However, in the context of RL, there is no explicit explanation provided for what $p_\\theta(A|S)$ and $p_\\theta(a_t|s_{0:t+1})$ correspond to. \n\nWe believe we have provided sufficient explanation for every notation we use. For example, in L110-111, we explain that $p_\\theta(A|S)$ denotes $p_\\theta(a_{0:T-1}|s_{0:T})$, a posterior probability in which $A$ denotes the complete action sequence $a_{0:T-1}$, $S$ denotes the complete state sequence $s_{0:T}$. We understand that this posterior probability isn’t usually seen in the literature of RL. So we explicitly define $p_\\theta(a_{0:T-1}|s_{0:T})$ in Eq. 4. The notation of $p_\\theta(a_t|s_{0:t+1})$ also follows the conventions of conditional distribution and Bayesian statistics. \n\n> [Lack of baselines] In the context of RL, there are two ways to improve sample efficiency: off-policy RL and model-based RL. Thus, at least one of the off-policy ILfO algorithms (e.g., OPOLO [1]) and one of the model-based ILfO algorithms (e.g., MobILE [2]) should be considered as baselines.\n\nWe appreciate the reviewer's suggestion to include off-policy and model-based ILfO algorithms as baselines. We initially considered MobILE as a baseline since it is also a model-based method for imitation from observation. However, our experiments with MobILE, using various sets of expert demonstration trajectories, did not yield satisfactory results. We will include this observation in the revision. We have included the result of OPOLO in Table 1 in the attached PDF file. The proposed LanMDP shows comparable performance. \n\n> [Objective] First of all, I wonder if the proposed objective (5) is valid in a stochastic environment. Indeed, the learned $p_\\beta$ can differ from the true transition in a stochastic environment, although it is possible to learn an accurate transition with enough online samples. Moreover, (8) may also allow for learning an accurate transition with enough online samples, but it is modified without any theoretical justification from the original objective (5).\n\nThe learning paradigm we employ is maximum likelihood. Eq. 5 is the general maximum likelihood objective, which is supposed to be applicable to any distribution to be learned, no matter whether the environment is deterministic or stochastic. The potential issue of using Eq. 5 alone is that the learned transition may not be grounded because actions are latent. To overcome this issue, we introduce the extra online learning term in Eq. 8, making it deviate from Eq. 5. Apparently, it is derived from jointly optimizing two log-likelihood, Eq. 5 and $L_{online}(\\beta) = \\sum_{i=1}^{m} \\sum_{t=1}^{T} \\log p_\\beta (s_{t+1}^i | s_{t}, a_t)$. We will include this explanation in the revision.  \n\n> [Exploration] I think LanMDP might fail to obtain a good policy in a stochastic environment (i.e., with stochastic transition probabilities) because there is no exploration. For example, if the algorithm obtains $(s, a, s’)$ during interaction, then there is no need to find other possible actions a’ that might be better to reach s’ from s. \n\nWe disagree with this comment. As stated in L182-184, LanMDP is inherently advantageous in exploration thanks to the energy-based modeling of policies. The maximum entropy inclination in energy-based policies has been shown to encourage explorations in [1]. \n\n> [Motivation of task] This work aims to solve ILfO for nMDPs. However, there are no motivating examples explaining why ILfO for nMDPs should be studied. Moreover, while the expert policy is non-Markovian, it is unclear if existing ILfO algorithms fail to solve ILfO for nMDPs.\n\nWe could not help arguing that this critic is unsubstantiated. Actually, the cubic planning task in Sec 5.1 is deliberately included to motivate the importance of non-Markovian modeling. The empirical results justify the insufficiency of the Markovian Imitation Learning methods (with or without action labels) and the efficacy of the proposed model. \n\n> [Motivation of LanMDP] It is not clear why we should use decision making as inference instead of a simple modification of prior works. Indeed, we can also handle ILfO on an nMDP by modifying MobILE. \n\nAs far as we know, there is no established work showing the suggested modification can principally solve the problem of imitation learning in non-Markovian domain. We also believe the non-Markovian extension of state-matching methods is non-trivial. It would be helpful if the reviewer would like to provide us with some pointers. \n\n> I think $R: S+ -> \\mathbb{R}$ is a generalization of $R(s)$. Is there any reason not to use $R: S+ x A+ -> \\mathbb{R}$, which is a natural generalization of $R(s, a)$?\n\nIn Sec 2, we introduce statistical assumptions in LanMDP. Since actions are assumed to be unobservable in the dataset, we exclude them from the dependency of $R$. It could be an interesting future direction to explore the setting that the reviewer suggested. \n\n> In equation (13), we need to compute $c(a_t; s_{0:t+1})$, which involves an expectation over $p_\\alpha$ I believe this part involves intractable integration in the continuous domain. If the authors use MCMC to address this issue, I am curious about the computational time it takes (compared to other baselines).\n\nWe add experiments to measure the time of posterior sampling, the time of prior MCMC sampling, and pure training time in Table 1 in the attached PDF. Importance sampling can bypass the additional cost of posterior sampling since it involves only prior sampling.\n\n[1] Haarnoja, Tuomas, et al. \"Reinforcement learning with deep energy-based policies.\" International conference on machine learning. PMLR, 2017.\n"}, {"review_id": "RX9EvM0cnI", "reviewer": "Reviewer_N9u8", "summary": "The goal of this approach is to learn from state-only sequences, in the case where action labels are not present, especially in non-markovian settings. The method formulates a non-Markovian Decision Process (nMDP) with latent actions as a Latent-space Energy Based Model, showing that the inference on the model is equivalent to policy execution/planning. Using a dynamics model and posterior sampling, the learned model can be used for planning, even for reaching new goal states. The paper alsow draws a connection of the proposed approach to max-ent RL. The results show good performance for non-markovian (and even some markovian) tasks. ", "questions": "See weaknesses section", "limitations": "These are sufficiently addressed", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper addresses an interesting problem of learning in non-Markovian settings\n- The application to learning from action-free data is very interesting as well \n- The approach outperforms IRL and BCO baselines on toy and control tasks \n- The approach is sound and novel (to my knoweldge)\n", "weaknesses": "I think there could be more analysis on the different types of non-Markovian tasks (i.e. tasks that require more long term versus short term memory). In general, more robotics focused applications would be a better showcase for this method. The context seems to be important - it would be good to investigate howhe use of sequence based architectures such as the Decision Transformer (Chen et al., 2021) fits into this general problem as well. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the feedback! \n\n> I think there could be more analysis on the different types of non-Markovian tasks (i.e. tasks that require more long term versus short term memory). In general, more robotics focused applications would be a better showcase for this method. The context seems to be important - it would be good to investigate howhe use of sequence based architectures such as the Decision Transformer (Chen et al., 2021) fits into this general problem as well.\n\nWe agree that systematically categorizing long-/short-term memory in nMDPs and testing various sequential decision-making architectures [1,2] in different regimes are crucial research topics. However, to the best of our knowledge, research as such awaits more infrastructure due to the lack of systematic benchmarks. We hope our work can invoke more efforts in the emerging area of non-Markovian decision-making, which could get us more prepared for the suggested investigation of the influence of different sequence-based architectures. We’d also love to explore in futhre work more robotics-focused applications beyond the toy or simulated control tasks presented here. \n\n[1] Janner, Michael, Qiyang Li, and Sergey Levine. \"Offline reinforcement learning as one big sequence modeling problem.\" Advances in neural information processing systems 34 (2021): 1273-1286.\n\n[2] Ajay, Anurag, et al. \"Is conditional generative modeling all you need for decision-making?.\" arXiv preprint arXiv:2211.15657 (2022).\n"}, {"review_id": "ZSRHnoRc1w", "reviewer": "Reviewer_LurP", "summary": "The paper proposes a generative model for learning non-Markovian decision-making from state-only sequences, where the policy is an energy-based prior in the latent space of the state transition generator. To solve the problems, the authors develop a maximum likelihood estimation method (LanMDP) for model-based imitation learning, which involves MCMC and importance sampling techniques. Besides, the papers shows how the learned model can be used for decision-making as inference, where model-free policy execution and model-based planning are equivalent to prior and posterior sampling, respectively. Experiments on a path planning task with non-Markovian constraints and several domains from the MuJoCo suite, LanMDP achieves comparable or superior performance than baselines (BC, LfO and GALfO).", "questions": "Here are some questions for the authors:\n\n1. How do you evaluate the quality and diversity of the samples generated by the model? Do you use any quantitative metrics or qualitative visualizations to assess the fidelity and diversity of the generated sequences?\n\n2. How do you compare the proposed method with other methods that learn non-Markovian decision-making from state-only sequences, such as inverse reinforcement learning or variational inference methods? What are the advantages and disadvantages of each approach?", "limitations": "The major limitations I am concerning are presented in 'Weakness' part. ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "State-only imitation is a important and a widely studied topic. This paper proposes an interesting idea of model-based imitation, and combines MCMC and importance sampling to estimate the model parameters from state-only data. \nThe paper demonstrates the versatility of the learned model for both model-free and model-based decision-making, where inference is performed by sampling from the prior or the posterior. The empirical evidence also supports the effectiveness of LanMDP. ", "weaknesses": "I am not familiar with of the domain of nMDP, and I would like to share my concerns about the method and experiments:\n\nMy major concern is that the proposed method relies on MCMC and importance sampling techniques to estimate the model parameters and perform inference. However, these techniques can be computationally expensive, sample inefficient, and sensitive to initialization and tuning. Therefore, it is unclear how well the proposed method scales to more realistic and challenging scenarios.\n\nBesides, the proposed method assumes that state-only sequences are sufficient to infer and imitate non-Markovian decision-making behaviors. In some cases, state-only sequences may not be enough to capture the relevant information or causal factors that influence decision-making, such as intentions, preferences, beliefs, or emotions. In such cases, state-only sequences is enough to learn meaningful or generalizable policies.\n\n\nThe motivation is unclear. For example, what is the advantage about using nMDP? Why does model-based imitation outperforms conventional methods? Additionally, I feel that there is a lack of cohesion between Sections. For example, Section 3 titles as 'Learning and Sampling'. However, it is separate from the previous Section and I do not know learning what and sampling what when I first read.\n\nFor experiments, the baseline methods are all from the 'imitation from observation' domain, which are built based on the standard MDP. I encourage authors to make comparisons with more related domain, i.e., methods that learn non-Markovian decision-making from state-only sequences.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback! \n\n> Computational cost of MCMC.\n\nWe recognize this concern. But we are rather optimistic in the short-run MCMC methods [1] since in realistic tasks the dimensionality of the action space is normally small in comparison with the state space. We add experiments to measure the time of posterior sampling, the time of prior MCMC sampling, and pure training time. As shown in Table 2, the posterior sampling is more consuming than prior sampling due to the additional computation of gradient of transition model. Importance sampling can bypass the additional cost since it involves only prior sampling. \n\n> ​​Assumes that state-only sequences are sufficient to infer and imitate non-Markovian decision-making behaviors? \n\nWe feel that this is a misunderstanding. We hope the reviewer would like to clarify what “sufficient” means. If it means state-only sequences are insufficient to uniquely identify a latent action, we certainly agree. Actually, existing works attribute the unsatisfying performance of inverse dynamics methods to such insufficiency [2]. We indeed take this into consideration in model design by making the policy multi-modal. \n\nIn terms of “intentions,... emotions”, we want to argue that people don’t, for example, carry a belief label when behaving, but we can infer it from our observations. Therefore, these are all latent variables, just like the latent actions in our model. \n\n> The motivation is unclear. \n\nThe motivation is communicated in the introduction. Specifically, we want to draw the reviewer’s attention to L28-29, where we reveal the limitation of the conventional imitation method due to the reliance on Markovian assumption and TD learning. The motivation is further illustrated with a toy task in Sec. 5.1. We hope the reviewer would like to discuss with reviewers W5w2 and wvit the relevance of nMDP. \n\nWe believe “model-based imitation outperforms conventional methods” is a misconception of our results. For example, BCO in Fig. 3 is also a model-based method. Our employment of a model-based method is largely due to the restrictions of latent actions and nMDPs, where model-free methods may not directly apply. We reckon that this misconception may attribute to the statement “We develop maximum likelihood estimation to achieve model-based imitation” in the abstract (L8), for it implies certain senses of purpose towards model-based imitation despite our real intention of conveying all constituents of nMDP (L6) are learned. We will resolve this confusion in the revision. \n\n> A lack of cohesion between Sections. \n\nThanks for this feedback! We believed the structure of this paper was implied in the last two paragraphs (L36-62) of the introduction, and the format of “modeling, learning, analysis” was conventional in machine learning papers. We will add a paragraph at the end of the introduction to explicitly sketch the structure in the revision. In short, in Sec. 2 we introduce the model; in Sec. 3 we introduce learning this model with neural networks as function approximators, which involves sampling; in Sec. 4 we analyze the connections between the learned model with sequential decision-making problems. \n\n> Comparisons with methods that learn non-Markovian decision-making from state-only sequences.\n\nTo the best of our knowledge, there is no established research in this particular setting.\n\n> Quantitative metrics or qualitative visualizations for the fidelity and diversity of the generated sequences?\n\nThe quality of generated sequences in the cubic planning task is evaluated by the residual errors and acceptance rate detailed in L233-239. In a word, we evaluate if the model learns to generate cubic sequences. This can also be qualitatively evaluated by the figures we plot in Fig. 2. For Mujoco tasks, the quality is assessed by the final score of the test trajectory. To answer the reviewer’s request, we upload some videos for qualitative evaluation. \n\nThanks for raising our attention to diversity, for which we don’t have a systematic metric currently. In a published benchmark for unsupervised RL [3], such a measure is also omitted. Other sequence models for decision-making don’t have such evaluation either. We agree this is an important concern and will include this limitation in the revision. \n\n> Comparison with as IRL or variational inference methods? \n\nWe hope the reviewer has been reminded in previous answers that there seems to be no established work for non-Markovian IRL yet due to IRL’s reliance on the Markovian limitation. We pick behavior cloning (BC) as the major baseline because it is free from the Markovian assumption. Putting the Markovianness aside, we believed with abundant data, behavior cloning with action labels empirically upper bounds the performance of IRL. This is supported by the result from [4,5], as well as our results in FIg. 3. We are very much anticipating future progress from RL’s perspective. \n\nWe feel thrilled for the reviewer mentioned variational inference as an alternative to MCMC. It is actually the next project in our plan, as we believed learning amortized sampler for latent EBM in nMDP deserved a standalone paper.\n\n\n[1] Erik Nijkamp, Mitch Hill, Song-Chun Zhu, and Ying Nian Wu. Learning non-convergent non-persistent short-run mcmc toward energy-based model. Advances in Neural Information Processing Systems, 32, 2019.\n\n[2] Zhu, Zhuangdi, et al. \"Off-policy imitation learning from observations.\" Advances in Neural Information Processing Systems 33 (2020): 12402-12413.\n\n[3] Laskin, Michael, et al. \"URLB: Unsupervised reinforcement learning benchmark.\" Neural Information Processing Systems Track on Datasets and Benchmarks (2021).\n\n[4] Goo, Wonjoon, and Scott Niekum. \"Know Your Boundaries: The Advantage of Explicit Behavior Cloning in Offline RL.\" (2022).\n\n[5] Florence, Pete, et al. \"Implicit behavioral cloning.\" Conference on Robot Learning. PMLR, 2022.\n"}, {"review_id": "xoT23Oxsm5", "reviewer": "Reviewer_W5w2", "summary": "The paper considers the problem of imitation learning from state observations in a setting where the transition dynamics are Markovian, but the (unknown) reward function and, therefore, the optimal policy are not. The problem is framed as maximizing the likelihood of the expert's state marginal based on a generative process that is parameterized via a history-based EBM-policy and a nonlinear Gaussian transition model (hence, the method is model-based). To optimize the likelihood of the state-only trajectory with respect to these action-related models, the method exploits that the gradient of the state-likelihood is equivalent to the expected gradient of the state-action likelihood, $\\nabla\\_{\\theta}\\log p\\_{\\theta}(\\tau\\_{S}) =  \\nabla\\_{\\theta} E\\_{p\\_{\\theta}(A|S)}[\\log p\\_{\\theta}(\\tau\\_{S,A})]$, where $p(A|S)$ is the posterior distribution (which takes into account that $s\\_{t+1}$ contains information about $a\\_{t}$). As the optimization involves expectations with respect to intractable models (not only the posterior, but also the prior, that is, the EBM policy is intractable), the proposed method uses a combination of Langevian MCMC and importance sampling.\n\nThe method is tested on a toy-problem, where a 2D point-mass should get velocity-controlled towards a goal location, while following a 3rd-order polynomial path (which corresponds to a non-Markovian reward). When providing a sufficiently large history to the policy, it can indeed learn to exhibit the desired behavior.\n\nIn the main experiments on (Markovian) Mujoco locomotion tasks, the method is compared to GAIL, and behavioral cloning (BC), which both get groundtruth access to the expert actions, and their counterparts GAIfO, and behavioral cloning from observations (BCO) that only use state observations. In these experiments the proposed method outperforms the competing imitation learning from observation methods and matches or even outperforms the baselines that have priviledged information about expert actions. ", "questions": "- It is not clear how the goal position is specified for the toy experiment. Is it added to the state space?\n\n- Line 77 argues that it non-Markovian rewards and Markovian states are usually sufficient because we can always define a state space that makes the dynamics Markovian. Couldn't we just as well argue that we can always define a state space that makes the reward function Markovian?\n\n- What is the computational overhead caused by MCMC?\n\n- What is the motivation for using an EBM instead of a more tractable policy such as a normalizing flow?\n\n- Line 192 states that Gaussian expectations can be approximated by the mean and refers to Kingma & Welling. What statement are you exactly referring to?\n\n- Is there any theoretical justification for mixing in online samples in the maximum likelihood objective?\n\n- Line 222. What is y' ? is it the target y location? Should it then also be $x' = 1$ instead of $x = 1$?\n\n- What is the main insight of Section 4? That there exists a reward function such that we can frame the MLE problem as a MaxEnt-RL problem? What are the implications?\n\n- Why is it overimitation if the agent imitates the cubic path of the expert? In the cited psychology experiments there was an mechanism and an extrinsic reward and therefore overimitation can be defined as imitating features that are not relevant for obtaining the extrinsic reward. How is overimitation defined in a setting without extrinsic reward?", "limitations": "While the paper mentions the limitation that MCMC may become prohibitively expensive, the paper does not provide evaluations of the computational cost. Also, MCMC can suffer from high variance and bad mixing time. ", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The proposed method is novel and the formulation as an MLE problem is interesting.\n\n- The problem setting is very relevant. Imitation learning from observations is an important topic because oftentimes we can not observe the expert's actions. Also learning from non-Markovian policies is important, because for general tasks, we can not assume that the provided state-action space is Markovian.\n\n- The claims seem correct. I checked the derivations and could not spot any issues.\n\n- The paper is well-written and clear.", "weaknesses": "Technical Soundness\n--------------------------\n\nIn the derivation that I sketched in the summary, the actions would not be grounded. The maximum likelihood objective would be an offline objective (similar to behavioral cloning), where the \"actions\" are latent variables with no particular meaning. Hence, for computing the gradient with respect to the transition model, the paper mixes in samples from policy rollouts. While grounding the latent variables in such manner is intuitively reasonable and based on the experiments sufficient to learn meaningful policies, it also seems to break the derivations. For all I can tell, the resulting method does no longer maximize the log-likelihood of the state trajectory.\n \n\nExperiments\n----------------\n\n- In the toy experiments, behavioral cloning fails to produce the desired cubic trajectories, even when using a history-based policy. The paper states that this might be caused due to the fact that their BC implementation uses a Gaussian (and, thus, unimodal) policy, whereas the proposed method uses a much more expressive EBM. I don't see why the task would require a unimodal policy because with a sufficiently large history (>= 4), there is at most a single action that stays on a 3-rd order polynomial path. Furthermore, it would be straightforward to use a multimodal policy such as a normalizing flow, or for an even fairer comparison an EBM (which could also be trained using Langevian MC estimates of the partition function, or using more advanced techniques). Of course, the comparison to BC is not fair anyways, since it does not make use of online samples. I wonder why GAIfO was not trained in this toy setting.\n \n- I could expect the method to outperform BC and BCO mainly due to the fact that those methods can suffer from compounding errors (BCO is online, but uses the interactions only for labeling expert actions using a learned inverse dynamic model). GAIL and GaifO are online methods, but they are not very sample efficient as they are not model-based, and so it's also not surprising that they underperform in the low data regime. Model-based imitation learning from observations alone (MobILE) would seem to be a more appropriate baselines, and as mentioned in the supplementary the modified Hopper and Walker environments where even taken from this work. Furthermore, least-squares inverse Q-Learning (LS-IQ) (Al-Hafez et al., 200) was tested in the imitation learning from observation setting using an inverse dynamic model, where it also cleraly outperformed GaifO.\n \n- The method relies on MCMC during training, but also during inference. The submission does not evaluate the compuational overhead resulting from this design choice.\n\n- Table 1 seems to be based on a single seed.\n\nReferences\n---------------\nAl-Hafez, F., Tateo, D., Arenz, O., Zhao, G., & Peters, J. (2022). LS-IQ: Implicit Reward Regularization for Inverse Reinforcement Learning. In The Eleventh International Conference on Learning Representations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the feedback! \n\n> Learning objective\n\nThe mixing of gradients in Eq.8  is derived from jointly optimizing two log-likelihood, Eq. 5 and $L_{online}(\\beta) = \\sum_{i=1}^{m} \\sum_{t=1}^{T} \\log p_\\beta (s_{t+1}^i | s_{t}, s_t)$. We will include this explanation in the revision. \n\n> Confusion about BC's result with sufficient history in the toy experiment\n\n“Behavioral cloning fails to produce the desired cubic trajectories, even when using a history-based policy” is a misunderstanding. Thanks to this comment, we realize that putting the result of behavior cloning with sufficient history in the supplementary and leaving only the one with insufficient history in the main text could be confusing. Please kindly refer to the two subfigures at the bottom right corner of Fig. 1 in the supplementary for the result aligning with your prediction. \n\nSince there seems to be a typo in “I don't see why the task would require a unimodal policy”, we reckon that the reviewer may also be wondering about the gap between LanMDP context 4 and BC context 4 in Fig. 2f. We hypothesize that this might be attributed to the larger compounding error in BC. To isolate the influence of compounding error, we design an experiment where we measure the residual error of the next state after filling the historical contexts in the learned LanMDP context 4 and BC context 4 with expert states, rather than sampled states. Interestingly, the error is around 0.0004 for both LanMDP and BC, closing the gap in Fig. 2f. The implication seems to be LanMDP is more robust to compounding error than BC. \n\n> In the toy task, how about baseline models other than BC\n\n1. Fair comparison with BC: As stated in L230-232, “in a deterministic environment, there should not be a difference between BC and BCO, as the latter basically employs inverse dynamics to recover action labels. For our model, this simple transition can either be learned or implanted. Empirically, we don’t notice a significant difference.”  \n\n2. Other multimodal latent policy such as normalizing flow model: We agree that it would be interesting to explore these models in future work. Our major consideration in choosing latent EBM is that it makes the least statistical assumptions (though the computational assumption of MCMC may be strong), such that the exposition of the decision-making process (Sec. 2) is clean to people from both literatures of generative modeling and decision making. \n\n3. Comparison with EBM with action labels: In a deterministic environment with such a simple Markovian transition, sampling the posterior $p(a_t | s_{0: t+1})$ can be done by inverse dynamics $g(a_t | s_t, s_{t+1})$ in which $a_t$ can be uniquely identified. So there is actually no difference between latent EBM with grount-truth transition and EBM with action labels. \n\n4. Comparison with GAIfO: Unlike BC which can be extended to non-Markovian setting, GAIFO, as a state-matching method, is limited to Markovian tasks. \n\n> Model-based baselines\n\nWe have been experimenting with the public code of MobILE on our demonstration sets since we were preparing this submission but haven’t obtained results comparable to those reported in their paper. Unfortunately, the contacts we sent out to the authors have all gone unanswered. \n\nThanks for pointing us to the LS-IQ paper. Since the major contribution of our work is not model-based Markovian imitation, we didn’t exhaust every paper in the Markovian domain thus wasn’t aware of this one, but we are definitely awed by its performance against the expert. We will include the training curves of LS-IQ in the revision. \n\n> MCMC cost\n\nWe add experiments to measure the time of posterior sampling, the time of prior MCMC sampling, and pure training time. As shown in Table 2, the posterior sampling is more consuming than prior sampling due to the additional computation of gradient of transition model. Importance sampling can bypass the additional cost since it involves only prior sampling.\n\n> Table 1\n\nThe results are actually based on 5 seeds. We have updated the table to includ the standard deviation in the attached pdf file. \n\n> Goal position? Overimitation and extrinsic reward?\n\nIt is more or less a philosophical question how humans understand the concept of “goal” through imitation. In L191, we stated that the “goal” means the last state $s_T$ in the sequence. The reviewer seems to have a different idea since in the cited psychology experiments, the object to be picked up at the end of demonstration sequences seems to be an extrinsic reward that further hints the “goal”.  We hope the reviewer would like to accept our hypothesis that agents may regard the last state as \"goal\" since it is simpler than the suggested one, and hence more preferable by the principle of Occam’s razor. Under this hypothesis, it is clear that overimitation is visiting the demonstrated goal with some causally unnecessary states in demonstrations. \n\n> non-Markovian rewards and Markovian states are usually sufficient? \n\nWe hope to remind the reviewer of the distinction between sufficiency and necessity. Indeed, a non-Markovian decision-making problem is not necessarily represented by non-Markovian rewards and Markovian transitions. Our motivation for this design choice is communicated in L82-84. \n\n> Insight of Sec. 4\n\nAs the reviewer points out, Sec. 4 proves there exists a reward function such that we can frame the MLE problem as a non-Markovian MaxEnt-RL problem, and this problem is solvable if MaxEnt-RL can be generalized to non-Markovian domains. This may further allude that the decision theory, especially offline MaxEnt-RL, might be a consequence of emergence from generative sequence modeling, rather than the essence. \n\n\n\n"}, {"review_id": "r5rqjYIzHO", "reviewer": "Reviewer_wvit", "summary": "This paper proposes an offline model-based method for learning a non-Markovian Decision Process (nMDP), i.e. the environment is Markovian but the policy is related to previous histories. In the dataset, we can only observe the sequence of states. This paper proposes a Lan-MDP algorithm, which estimates the transition and policy through MLE. Specifically, Lan-MDP leverages Langevin dynamics to calculate the weights in the posterior distribution. The algorithm then transforms behavior cloning into a reward-maximization problem by constructing a reward with the estimated transition/policy to do planning for sequential decisions.", "questions": "Line 226: Additional 'including' could be a typo", "limitations": "See Weakness", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper aims to tackle the issue of non-Markovian imitation learning where we can only observe a dataset of sequential state (with no actions), which is known to be very hard due to long history dependency (generally NP-hard, see [1]). \n\n[1] Learning in Observable POMDPs, without Computationally Intractable Oracles, Noah Golowich, Ankur Moitra, Dhruv Rohatgi", "weaknesses": "In my humble opinion, I think the author could illustrate more examples (either in the real-world or synthetic problems) that satisfy the setting they proposed. POMDP should be one important example that is confounded/has a non-Markovian structure, but its transition doesn't have a Markovian structure. Intuitively, the history-dependency of the transition would cause difficulty in planning/learning in non-Markovian problems ([1]), and I am not sure Lan-MDP could tackle this.\n\n\n[1] Learning in Observable POMDPs, without Computationally Intractable Oracles, Noah Golowich, Ankur Moitra, Dhruv Rohatgi", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your feedback! \n\n\n> Q: Could LanMDP tackle POMDP? \n\nIndeed, with the Markovian assumption in transition, the proposed model cannot directly extend to POMDP, where the transition is non-Markovian. However, it is worth a trial with the general modeling of latent EBM with non-Markovian transition and policy. "}]

Author rebuttal:
We would like to thank all reviewers for your helpful feedback!

We add two tables for some additional experiments in response to your requests. Table 1 includes a new baseline for the MoJoCo task, as well as the omitted std of the proposed model. The proposed model still exhibits comparable performance to the baselines. Table 2 measures the time for prior and posterior sampling. It supports that importance sampling indeed improves efficiency. 

Meta-review: The goal of the paper is to learn from demonstrations consisting of sequences of states only (without action labels), especially in non-Markovian settings. The authors propose an energy-based formulation that can be solved using inference technique. The resulting methods is tested in several domains with simulated robots, and shows good performance compared to a number of baselines.

One reviewer was critical of the paper, mentioning presentation, lack of baselines, performance in a stochastic environment, and relevance. The authors explained or rebutted most of these points with a clearly articulated rebuttal.

The other reviewers are mostly positive of the paper. The problem addressed is seen as relevant, novel, and challenging. The empirical results are also mostly seen as convincing. There was some concern about the learning objective, which was clarified in the discussion. Another suggestion was to add more examples of (realistic) nMDP problems and a more structured analysis in different types of non-Markovian tasks.
Decision: Accept (poster)