Trajectory Graph Learning: Aligning with Long Trajectories in Reinforcement Learning Without Reward Design
Authors: Yunfan Li
Eric Liu
Lin Yang
Venue: NeurIPS 2025 spotlight ()
Keywords: Reinforcement Learning
Trajectory Alignment
Trajectory Graph Learning
Primary area: reinforcement_learning

Abstract: Reinforcement learning (RL) often relies on manually designed reward functions, which are difficult to specify and can lead to issues such as reward hacking and suboptimal behavior. Alternatives like inverse RL and preference-based RL attempt to infer surrogate rewards from demonstrations or preferences but suffer from ambiguity and distribution mismatch. A more direct approach, inspired by imitation learning, avoids reward modeling by leveraging expert demonstrations. However, most existing methods align actions only at individual states, failing to capture the coherence of long-horizon trajectories.

In this work, we study the problem of directly aligning policies with expert-labeled trajectories to preserve long-horizon behavior without relying on reward signals. Specifically, we aim to learn a policy that maximizes the probability of generating the expert trajectories. Nevertheless, we prove that, in its general form, this trajectory alignment problem is NP-complete. 
To address this, we propose Trajectory Graph Learning (TGL), a framework that leverages structural assumptions commonly satisfied in practice—such as bounded realizability of expert trajectories or a tree-structured MDP. These enable a graph-based policy planning algorithm that computes optimal policies in polynomial time under known dynamics. For settings with unknown dynamics, we develop a sample-efficient algorithm based on UCB-style exploration and establish sub-linear regret. Experiments on grid-world tasks demonstrate that TGL substantially outperforms standard imitation learning methods for long-trajectory planning.

Trajectory Graph Learning: Aligning with Long Trajectories in Reinforcement Learning Without Reward Design
Yunfan Li University of California, Los Angeles yunfanli@g ucla. edu
Eric Liu University Southern California eliu4913Gusc.
Lin F. Yang
University of California, Los Angeles linyang@ee ucla.edu
Abstract
Reinforcement learning (RL) often relies on manually designed reward functions, which are difficult specify and can lead issues such as reward hacking and suboptimal behavior. Alternatives like inverse RL and preference- based RL attempt to infer surrogate rewards from demonstrations preferences but suffer from ambiguity and distribution mismatch. A more direct approach, inspired by imitation learning, avoids reward modcling by leveraging expert demonstrations. However, most existing methods align actions only individual states, failing to capture the coherence of long-horizon trajectories.
In this work, we study the problem of directly aligning policies with expert- labeled trajectories to preserve long-horizon behavior without relying on reward signals. Specifically, we aim to learn policy that maximizes the probability of gencrating the expert trajectorics. Nevertheless, we prove that, in its general form, this trajectory alignment problem is NP-complete. To address this, we propose Trajectory Graph Learning (TGL), a framework that leverages structural assumplions commonly salisfied in practice such as bounded realizability of expert trajectories or tree-structured MDP. These enable graph-based policy planning algorithm that computes optimal policies polynomial time under known dynamics. For settings with unknown dynamics, develop sample-efficient algorithm based UCB- style exploration and establish sub-line aibliinerr regret. Experiments on grrd-world tasks demonstrate that TGL substantially outperforms standard imitation learning methods for long-trajectory planning.
1 Introduction
Reinforcement. learning (RI) has emerged as a powerful tool with numerous successful applications, ranging from early advancements in robotics and control [ee al., 2020] to more recent breakthroughs in self-driving technology [Dosovitskiy et al., 2017] and the fine-tuning of Large Language Models (LLMs) [Ouyang et al., 2022]. However, the success of RL in real-world applications often relies heavily on the design of the reward function, which typically requires significant prior knowledge. We face challenges such as reward hacking
"Coresponddig authors
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

[Amodei et al., 2016] where unintended behaviors maximize the given reward and reward shaping [Ng al., 1999] where improperly crafted rewards lead suboptimal learning.
Since designing scalar, numeric rewards is often impractical for complex real-world tasks, some alternative paradigms have been proposed. Inverse Reinforcement Learning (IRL) [Ng ct al., 2000] aims to recover a reward function that explains and justifics an expert's demonstrated behavior-so the agent can reproduce comparable policies without ever being given explicit rewards. More recently, Freference-basee 2011b, Christiano et al., 2017, Xu et al., 2020, Abdelkareem et al., 2022] replaces hand- crafted numeric rewards with human preferences typically pairwise or ordinal feedback over trajectories or behaviors- -nd learns either surrogate reward a policy that aligns with those preferences to guide decision- decision-making. However, learning a surogate reward from demonstrations or preferences does not guarantee alignment with expert intent; ambiguity [Waugh et al., 2013, Lambert and Calandra, 2023, Hu et al., 2023], overfitting [Brown et al., 2019a, Szot ct al., 2023] and distribution shift [Fu et al., 2017] all conspire to degrade final policy quality. These empirical and theoretical findings motivate approaches-sude as direct trajectory alignment that bypass reward modelling altogether.
Reinforcement Learning (PbRL) [Akrour et al.,
Imitation learning [Hussein et al., 2017] circunvents the need for handcrafted reward functions by training policies to replicate expert behavior, typically by learning mapping from observed states to corresponding expert actions. However, its classical instantiation- (BC) [Torabi et al., focuses solely state-action pair alignment, capturing the expert action conditioned on individual states while neglecting the broader trajectory-level structure. As a result, discrepancies between the trajectories generated by the learned policy and the expert demonsttrttonn can accumulate over time, ultimately undermining the preservation of coherent long-horizon behaviors [Ross al., 2011, Chang et al., 2021]. We illustrate this limitation with a concrete example in Appendix A.2, where BC fails to reliably reproduce entire expert trajectories with probability 1 even in deterministic environment. This shortcoming motivates our study of direct trajectory alignment, which seeks to directly maximize the likelihood of reproducing complete expert trajectories. Such alignment is particularly critical in applications like large language model (LLM) response generation [Zeng et al., 2024] and autonomous driving [Huang et al., 2024], where even small local deviations can propagate into significant degradations in overall quality or safety. To the best of our knowledge, the theoretical foundations of directly aligning policies with expert-labeled trajectories- without without relying on reward modeling remain largely unexplored.
cloning
In this paper, we systematically investigate the problem of direct trajectory alignment in reinforcement learning and develop a thcoretical framework that enables efficient policy learning through whole-trujectory aligmment. Our approach eliminates the need for explicit reward modeling and leverages struct ural assumptions such as reachable expert trajectories in terms of probability and tree-struct ured MDP to ensure computational tractability. We summarize our key contributions below.
Our Contributions
Hardness result for direct trajectory alignment. We prove that the general problem of finding an optimal policy via direct trajectory alignment is NP-complete, by presenting a novel reduction from a classical NP-complete problem. This result highlights the fundamental computational challenge of directly aligning policies with expert trajectories.
Theoretical framework: Trajectory Graph Learning (TGL). We introduce Tha- jectory Graph Learning (TGL), a theoretical framework that casts the direct trajectory alignment problem as a maximum weight independent set problem over trajectory- induced graph. Under structural assumptions such as bounded realizability of expert trajectories or a tree-structured MDP-we show that the optimal policy can be com- puted in polynomial time. In the setting with unknown dynamics, we integrate an upper-confidence bound (UCB) exploration strategy and design a learning algorithm with provably sub-linear cumulative regret.
Empirical validation. We empirically evaluate TGL on grrd benchmarks. Our results show that TGL. consistently aligns with expert-labeled trajectories more faithfully than standard behavior cloning across various trajectory sets.
2

---

Related work We review several classical RL approaches. The first line of work is inverse reinforcement learning (IRL), which infers surrogate rewards from expert demonstrations; the second is preference-based RT. (PbRL), which learns from preferences over trajectories; and the third is imitation learning, which directly maps expert demonstrations to policies without reward modeling.
Inverse RL Early work framed IRL as reward reconstruction: Ng et al. [2000]'s linear program formulation and Abbeel and Ng [2004]'s feature expectation matching seek a reward under which the expert is optimal, a paradigm later disambiguated with maximum-entropp regularization [Ziebart et al., 2008]. Deep variants such as Guided Cost Learning [Finn et al., 2016]; GAIL [Ho and Ermon, 2016], and AIRL [Fu ct al., 2018] scale this two-stage pipeline, yet their rewards remain trustworthy only near the demonstration distribution, leading to policy mis-alignment after exploration. Recent extrapolation and theory papers such as T-REX [Brown et al., 2019b], the finite-ammple analysis [Komanduru and Honorio, 2019], and empirical audits of RLHF reward models [Kaplan and et al., 2023] confirm that surrogate rewards do not guarantee alignment, motivating the need to analyze direct trajectory alignment as an alternative.
PERL From the first simulator free preference- based policy learning algorithms [Akrour et al., 2011a, Wilson et al., 2012, from human preferences framework [Christiano et al., 2017], most PbRL methods fit a surrogate reward to pairwise or K-wise feedback and then optimize it with standard RL. Recent PbRL algorithms still fit implicit reward surrogates whose quality hinges on pro- chosen feature embeddings and Bradley-Tery--Lce (BTL) style preference models. For instance, Saha et al. [2023] established finite-time regret bounds only after projecting trajectories into hand-crafted feature space, so alignment requires that this embedding fully captures lask-relevant differences. The finile-sample analysis of Xu el al. [2020) likewise assumes an unobserved latent reward and proves guarantees under the oracle condition that pairwise labels reflect that hidden function. Empirical pipelines such as Direct Preference Optimisation (DPO) [Rafailov et al., 2023] and Direct PB-PO [An et al., 2023] optimize the same BTL-based surrogate, while more recent theory SeqRank's principled comparison loss [Zhu et al., 2023], the reward-agnostic RAPT optimiscr [Zhan et al., 2023), and best- policy identification from preferences [Aguihotri et al., 2025] rely on accurate trajectory calibration
et al., 2013] to the widely cited deep RL
recover near-optimal policics. These dependencies indicate that PbRL, which relies on feature embeddings and preference models, may fail to guarantee alignment with expert behavior highlighting the need to study the problem of direct trajectory alignment.
embeddings and weefrrencellkkllhhoe
Imitation Learning Imitation learning (IL) dispenses with reward design by training a policy to copy expert demonstrations [Hussein et al., 2017]. The dominant variant, behaviour cloning, maps each observed state to the expert's action [Torabi et al., 2018]; because it matches actions state-by-state, it incurs covariate shift, so small errors push the learner into unseen states and the mismatch compounds along a trajectory [Ross et al., 2011]. Recent analyses confirm that even with offline fixes such as MILO trajectory-level fidelity remains loosely bounded [Chang et al., 2021]. Thus, no existing IL framework directly optimizes expected alignment with a set of expert-labelled trajectorics.
2 Problem Formulation
In this section, we first introduce and define the direct trajectory alignment problem. We consider a finite-horizon Markov Decision Process (MDP) M = (S, A, Tacl, H. p), where S is the state space, A is finite action space, P: S x A A(S) is the transition kernel, H is the planning horizon (i.c., episode length), and μ is the initial state distribution. The agent interacts with the environment episodically. In each episode of length H, the agent follows policy म = [T H ) where each Fa : S + A maps a state to an action at time step [H]. (81, (1, 82, (l2....,88 am)) where 82 ~ PP( 81, a1), 02 = T2(82), and so on. Tet T denote the set of all possible H-length trajectories in the environment. Instead of having a reward function as in traditional RL, we
A policy induces a trajectory
μr, 01 = (s1),
3

---

are given Expert-Labeles Trajectory Set, defined as a small subset = (Ti) CT where each T2 trajectory. Typically, the size of the expert-labeled trajectory set is small relative to the entire trajectory space, L.e., M < [T
Each policy induces distribution d' over the space of H-length trajectories T, where d' (r) ((8)) II==]II== <(an 8h) IP(84+1 an) The objective is to find policy that maximizes the visitation probability of the trajectories in the expert-labeled set.
Σ (T
π arg max
TEll
TET
Direct trajectory alignment replaces the cumulative reward used in standard RL with expert-labeled trajectory set as the criterion for policy evaluation. standard RL, the effectiveness of learning algorithm is often measured by regret, defined the difference between the cumulative reward of the optimal policy and that of the agent's 's learned policy over time. Analogously, in our direct trajectory alignment setting, regret that captures the performance gap in aligning with the expert-labeled trajectories. Specifically, for each round [K], suppose the agent starts from the same initial distribution and executes policy t to generate trajectory. The cumulative regret after K rounds is then defined as
define a notion of
K
Regret(K) (K)
Σ
Σ (T) Σ C -
(1)
TET
where (r) denotes the probability generating trajectory 7 under policy n
Notation We use [n] to represent index set [1....n). For x E R, [æ]] represents the largest integer not exceeding x and [z] represents the smallest integer exceeding x. We use O to represent leading orders in asymptotic upper bounds and to hide the polylog factors. For finite set A, we denote the cardinality of A by |A].
Hardness of General Direct Trajectory Alignment Problem
In this section, we will show the hardness of solving a general direct trajectory aligmment problem. We will show that getting the optimal policy general direct. trajectory alignment problem is equivalent lo solving a Maximum- Weight Independent Set (MWIS) problem in a graph. First, we will introduce some concepts here.
Definition (Conflict in State-Action Pair). Two stale-action pairs (s, a) and (8', a') in conflict if they share the same state but have different actions:
and # a'.
Definition (Conflict in Trajectories). Consider two trajectories of length H:
(81, (s1,a)..... ......8.. ..., aH), T2 a s'H d'y).
They are in conflict if there exists h {l,.... H} such that
8h = S/ and on + dh-
Remark. If Ti and T2 conflict, and Ti and T3 do not conftict, does not imply that T2 and T3 are conflict-free. Definition Prajecctry-Indducee Policy Sct). For a trajectory T (81. ($1. O1........... SH, az), its trajectory-indueed policy set nt' contains all policies π = {m ) satisfying (sh) = for each h, while (s())) is arbitrory for s' + Sn:
π {ग (8n) an Yh 1, 1,.... H; Tx(s') arbilrary for s' + sn).
"Our setting be naturally extended scenarios where the expert-labeled trajectory accompanied by scalar feedback, such as scores provided by experts. In this case, have Taa = {(T., M M C x V, where each т; denotes trajectory and yi E y represents its associated scalar label. Accordingly, the objective should incorporate the feedback by weighting each trajectory with its corresponding label y:.

---

This set represents all policies that exactly reproduce r on its specific states. Since we focus on deterministic policies, conflicts arise when policy must choose unique action at the same state, unlike randomized policies which can mix actions.
Remark. If TI and T2 conflict, then x n 0 because deterministic policy conmol choose conflicting actions at the same state, Conversely, if a set of trajectories (Ti,..., Tm are pairwise conflict-free, then O n * 0.
For each trajectory T; [s}
H ag
(4)
let
p: - u(s) (1
81 , ai
(1)
... PH- 1 88 8H-1
(
1
If deterministic policy a belongs to 1==1 ,", then
P(Agent visits
Te) (x) Σ ps.
i=1
At the same time we can consider a Conflict Graph G= (V, E, W): where the vertex set V represents the trajectories TI, - TM 7M in Tael, the edge set E constructed if any pair of trajectories are conflict. For the weight set W = {wi,, we let w; = Pi, the probability product of realizing that trajectory.
Thus, the original problem reduces to the following Maximum- Haximuu-Weight Independent Set (MWIS) problem on graph G with weights p;:
max
Ps PETA
24 +i S V (o),e)) E, I E (0.1) Vi.
(2)
Let S = (0;; be the optimal node set; the corresponding policy selects (s for all v S and h= 1,..., H.
d
(8)
It is well known that the Maximum Weight Independent Set (MWIS) problem in graph is NP-complete |Garey and Johnson, 1979]. We have demonstratod that our original problem-findiee
the optimal policy in the binary-labeled setting- can be reduced to instance of the MWIS problem. This motivates us to explore whether these two problems are equivalent in computational complexity. In fact, we establish the following result:
Theorem 1. The problem of finding the optimal policy in the direct trajectory alignment setting is NP-complede.
Remark. We prove this by showing reduction from a known NP-complete problem -the MWIS problem. We show that any weighted graph can be represented as a subset of trojectories with corresponding probabilities. We achieve this by using a novel BFSSBassed trajectory construction to transfer any weighted graph subset of trajectories in one MDP. Then we show that good policy implies high weight independent set, which concludes the proof. The details is provided in the Appendiz A.3.
Trajectory Graph Learning with Known Model
When we face the hardness of finding the exact optimal solution of the general problem in polynomial time implied by Theorem 1, one may think of the path to find approximation solution with polynomial time. Unfortunately, prior work by Johan [1999] shows that the MWIS problem is extremely hard to approximate, establishing that unless P = NP, there no - approximmaiionn algorithm for MWIS for any fixed E > 0, where n denotes the number of nodes in the graph. However, establish the Trajectory Graph Learning (TGL) framework with positive results when certain assumptions is added on the MDP or the expert-labeled trajectory set.
Case 1: Bounded realizability of expert trajectory set In the first case, assume that all trajectories in Teel are reachable, meaning they have non-negligible probability under the environment. This is standard and practical assumption, trajectories with vanishingly small probability are often ignored or excluded during data collection or preprocessing. As a result, the selected set Tedt contains only trajectorics that the agent has reasonable chance of encountering.
5

---

Algorithm 1 TGL-CP
Require: Finite-horizon MDP (. Expert-Labeledt Trajectory Set T
(T.....TM): MWIS oracle MWTS(G, w)
Ensure: Chosen trajectory subset S and derived policy /* Conflict graph */
1: V + {u
Teel), E+0
2: for all (T) with i jj do
3: if 3h: 8 = = a & of then
4:
E+ EU ( 2y)
/ Weights */
5: for all Ti E Teel do
P(s 1 S/ a/)) 6: Pi 1---h-1 /1 1
/*MWIS Oracle $/
7: S + MWIS(G, (Pi...., PM))
8: for all 0 E S with Ti = (sf, .i....,..................... s/ a44) do
9: for h= to H do
10: (+,)) at
For states not covered by Unes Tu sot Th via a default rule
12: return S,
Definition 4 (e Realizable). We say trajeclory т (81, 01, 82, 02, 80, E e-Realizable if the probobility product Pi P1 (2 $2, 02) ... (
Example. In nearly deterministic environment, where transitions deterministic have high probability (o.g., P(sh+1 8h. ap.) 0.9 for all steps), many trajectorics are g-rcalizable with relatively large (c.g., 0.9*-1). In contrast, in highly stochastic environments, some trajectories may have exponentially small realization probabilities (e.g., ~> p for small p), making them effectively unreachable in practice unless is extremely small.
Then we provide generic framework TGL-CP (Trajectory Graph Learning- Conflict Planner), which is also shown in Algorithm 1. Basically, the algorithm will first construct conflict graph, where the odges can be determined by checking the conflicts in the expert- labeled trajectory set and the weights can be calculated by the probability product of each trajectory. Then, a MWIS oracle applied to select a subset of trajectories S that forms a solution to the problem. The desired policy is subsequently obtained by following the actions specified in the trajectories contained in S, ensuring the policy aligns with the selected subset of trajectories. To implement this step explicitly, we introduce simple emumeration based oracle for MWIS, detailed in Algorithm in Appendix A.1. Then we have the following theorem.
Theorem 2. Assume that any trajectory in the expert-labeled trajectory set Teel is Eu- Realizable, then after applying Algoritium and 3, it can return the optimal policy n with time complerity O(M2 H + M1/Li/sa)).
Remark. The enumeration--oss based oracle exploits the lower bound w(v) Eo implied by the En eo-realizable assumption to deduce that any feasible independent set can contain al most K = [1/Eo] vertices. Leveraging this, the oracle exhaustively enumerates all subsets of vertices of size at most K, checks each for independence, and calculates their total weight. By keeping track of the heaviest feasible subset encountered, the oracle returns the caact mazimum-west weight independent set in time polynomial in the graph size, assuming K is treated as constant.
In the second case, instead of focusing on a general MDP, we instead look for some special structured but very useful MDP setting. The one will display here is a so-called Tree MDP.
Case 2: Sree-Structured MDP
Definition 5 (Tree MDP). A Tree MDP is defined as follows:
1. No subsequent crossover for different states: For any step [ft], for any two different states s
(1) and sh (2) the subsequent states after these two states should be different, i.e. if

---

the possible visiled states after 8h"" ( and sh are ) and (sf))) respeclively, then we have afs) (2) no(s)))) 0.
2. No subsequent crossover for different actions: For any step E [H], each state sn has possible actions leading to possible successor states with no merges; i.e. if action an leads to possible states (1)) and a different action 02 leads to (s)),,) then
(sn) (o(2) = Ø.
3. No revisits: once the MDP leaves Sh it never returns it in future steps.
Consequently, the transition graph is forward branchhb tree. A trajectory is any path from the inilial state 81 to a layer-H leaf. Two trajectories conftict if al some lime h they coincide in the same state but choose different actions, forming on edge in the conflict graph. Tree MDPs arise naturally in applications where future decisions unfold independently and paths do not merge. In LLMs, decoding strategies like beam search or top-k sampling generate diverse continuations from prompt, forming a forward tree where each branch represents a distinct sequence [AssemblyAI, 2023]. In self-driving, planning algorithms simulate future actions (e.g., turn, accelerate) under constraints that avoid revisiting past states, resulting in a branching structure of possible trajectories [Zhao et al., 2025].
Under the Tree MDP structure, we provide a novel algorithm TGL-PrunedTress which detailed in Algorithm 4 in Appendix A.1. It is backward trajectory selection and pruning algorithm tailored for solving the policy optimization problem in finite- horizon Tree MDP. Given a set of M trajectories Tze) = [ each of fixed length H, the algorithm first computes a weight for each trajectory based on the product of transition probabilities along its path. It then proceeds in a backward fashion, from the final timestep H to the root, performing aggregation and pruning at each level. For each state 8h at timestep h, it aggregates the weights of trajectories sharing the same action an and keeps only the action with the highest total weight. This approach prunes conflicting merges consistent ones, yielding a compatible, sigh-weights subset of the original trajectories.
suboptimal paths and
Theorem 3. Under the Tree MDP assumption ( (Definition 5), Algorithm 4 computes an optimal policy '' with time complexity O(H M |
Remark. The full proof is provided in Aypendir A.5. The key insight here is that, under the Tree MDP structure, the optimal policy can be computed efficiently using a tinear-time dynamic programmingg approach crathcch-rtthrr than solving an NP-hard problem in the general graph case. This result paves the way for analyzing more efficient algorithms, both in terms of time and sample complexity, within learning settings that exhibit tree-like structure.
Trajectory Graph Learning with Unknown Model
In real-world scenarios, even when expert trajectories or human-labeled datasets are available, the underlying environment dynamics are lypically unknown- that is, the transition matrix must still be learned. In this section, we investigate methods for jointly learning the environment and identifying a good policy, setting commonly referred to as online learning. Specifically, we introduce a UCB- exploration algorithm and provide its corresponding regret analysis.
In the online learning setting, we propose TGL-UCB (Algorithm 2), which learns an optimal subset of expert-labeled trajectories by combining Monte Carlo sampling with an Upper Confidence Bound (UCB) exploration strategy [Auer al., 2002] over a conflict graph. Each node in the graph represents a trajectory, and edges connect conflicting pairs that cannot. be realized simultaneously, For each trajectory node 0 E V, we track: T, (the total number of has been
times a matching policy has been played), N; (the number of times trajectory realized), and मu N₁/T; (the empirical realization probability). Initially, for each Us we generate policy и; by selecting an arbitrary maximal independent set containing es and play each once to initialize estimates. In each round, TGL-UCB computes optimistic upper confidence bounds for all trajectories, invokes an MWIS oracle to select an independent set maximizzing the lotal UCB values, executes the corresponding policy, and updates estimates. This ilerative process balances exploration and exploitation, enabling TGL-UCB to progressively refine its trajectory selection and align with expert-labeled demonstrations Before presenting the main theoretical result, we introduce some essential definitions.

---

Algorithm 2 TGL-UCB
Require:
Expert-Labeled Trajectory Set Teol f . Tarts Total number of rounds n MWIS oracle MWIS(G,w)
Ensure: Chosen trajectory subset S and derived policy
/ Conflict graph #/
1: V {u To Tael), E+
2: for all (T))T) with i < do
3: if 3h: S = a & oj then
4:
E E+ (1, 2y)
5: Initialization:
6: For each node (trajectory) & E V, use variable T, as the total number of policies played that matches trajectory variable N₂ as the times that Us is sampled so far, and variable Rt as the current estimated empirical probability of realizing trajectory T where AA; = N. T:
7: For cach node V, select an arbitrary maximum independent S; C V such that 8 E Sü, and get the corresponding policy π, from S,.
8: For each i E [M], play тe once and update variables T; and fü..
9: for = M + 1, M + 2, n do
10:
for i [M] do
11:
Set f4 +
3log
12:
Compute S+ + MWIS(G, (ur)ye))
13:
Play the corresponding policy N from S+ and update all Tis, Ni's and pr,'.
For any independent set c V, define ps = Eves Po and the optimal value p² maxs indep. Ps. The set of sub-optimal solutions is
Suub = {S c V ps < p'}
For each node v E V, define the sub-optimal gaps:
A = p" max {ps S Saub: U S}. The global gap bounds are:
max =p" min {ps S E Sanh. E S}.
Amin min A minn Amax
max A
max
BEV
Theorem 4.
The expected regret of Algorithm 2 over K rounds is at most O
(M
M log K-Aaaa Aim
Remark. This theorem establishes a gap-dependent regret bound and guarantees sub-linear regret, indicating that efficient learning is achievoble in our setting given access to good MWIS oracle. The detailed proof is provided in Appendix A.6. The key idea is to reduce our TCB-based graph learning problem to classicol combinatorial malti-armed bondit (CMAB) problem, enabling the application of standard onalysis techniques.
Experiments
To further demonstrate the effectiveness of our method, we conduct experiments comparing our TGL-UCB approach with the classical imitation learning bascline, behavior cloning. This experiment deliberately designed to stress trajectory-level aligument.
4 x FROZEN LAKE environment [Brockman et al., 2016] modified to make holes non-terminating and yield a - reward. The goal square returns +1 and ends the episode; otherwise the horizon is H 10. On every step the intended action is replaced by uniformly-random valid action with probability 0.10. Observations are one-hot state vectors and actions are the four cardinal moves.
Environment. All experiments
Demonstrations. For each condition in Table 1, we build set D = { of "expert" urajectories that serve as offline data: these trajectories are produced by a deterministic expert or by its stochastic variant. By our definition of trajectory conflicts, the trajectories produced by any deterministic agent. are not conflicting, which why we sample some trajectories from stochastic agent to induce more conflicts. We then tested various

---

Table 1: Trajectory match probability (1 better) over 10,000 episodes with 95% CIs (+).
Each row shows how many deterministic and stochastic demos are in D.
Expert-Labeled Set
TCL-UCB (Ours)
BC
PPO Expert
15 det. & stoch.
0.794 = 0.008
0.775
0.008
0.778 0.008
10 det. & 10 stoch.
0.801 = 0.008
0.778 = 0.008
0.800 = 0,008
5 det. & 15 stoch.
0.801 = 0.008
0.771 = 0.008
0.793 = 0.008
10 det. & 5 stoch.
0.814 + 0.008
0.793 0.008
0.803 = 0.008
8 det. & 7 stoch.
0.810 + 0.008
0.774 0.008
0.801 0.008
5 det. 10 stoch.
0.779 + 0.008
0.758 0.009
0.780 0.008
10 det. only
0.778 + 0.008
0.753 = 0.009
0.775 = 0.009
5 det. & 5 stoch.
0.740 + 0.009
0.713 = 0.009
0.735 = 0.009
10 stoch. only
0.738 + 0.009
0.714 0.009
0.739 = 0.009
5 det. only
0.730 + 0.009
0.703 0.009
0.713 0.009
5 stoch. only
0.675 = 0.009
0.673 = 0.009
0.661 = 0.009
3 det. only
0.672 + 0.009
0.672 0.009
0.670 = 0.009
3 stoch. only
0.657 + 0.009
0.653 0.010
0.648 1 0.010
1 det. only
0.634 + 0.010
0.627 0.010
0.621 0.010
trajectory set sizes (from 1 to 20) and various ctteemiiiisii/soocssstttee compositions. No further interaction with the environment is allowed during training.
Methods compared.
TGL (ours). Algorithm 2 (TGL-UCB) is run on D with initial number of samples my = 10, and successful probability = 0.9. We solve for the exact MWIS solution in the algorithm (since our environment is small). The resulting maximum-weige wwightt independent set S+ is turned into time-indexed lookup policy as described in Section of the paper.
Behavioural Cloning
(BC). We train the supervised learner imitation. algorithms bc from the opens ource imitation library [Gleave et al., 2022), with batch size of 8 for 20 epochs on the same trajectory set.
PPO Expert. The reference expert policy used to generate the deterministic demonstra- tions (trained for 50 k steps with PPO).
Metric. Because mumerical rewards are absent during training, we evaluate policies by the probability that a rollout & exactly matches one of the demonstration trajectories:
(m) Pr [ DD.
For each policy we execute 10000 episodes with fixed seed and report the empirical match frequency. This empirical trajectory match probability metric directly measures the objective of direct trajectory alignment (DTA): replicate the expert trajectories, rather than maximizing surrogate reward. Each episode can be viewed a Bernoulli trial that either matches demonstration trajectory or not, so the empirical match probability is a binomial proportion.
Error Bars. We report the 95% confidence intervals for each configuration using Wald intervals computed from the 10,000 trials. In the worst case = 0.5, the standard error is / (00.5(1-00) - 0.5)/100000 = 0.005, yielding a Rv 0.01 wide 95% interval. In practice, we report the error bars based the empirical P from each cell.
Discussion. Across every demo composition, TGL-UCB consistently matches exceeds the behavioural-cloning baseline and often surpasses the PPO expert, despite never observing rewards. The gains are the most pronounced when remonstrationns are scarce or highly mixed, highlighting the benefit of directly learning from trajectories.
Limitations and Future Work. Our study was done using a single finite and discrete 4 x 4 FROZEN LAKE gridworld-like environment. The current theory and algorithmic guarantees target finite MDPs with finite exppert set and do not extend continuous MDPs. Scaling grid size increases the number of states but does not qualitatively change the conflict structure, so the results here primarily serve to validate the trajectory-aligument mechanism and TGL- UCB algorithm. TGL-UCB is also more compulationally expensive than Behavioral Cloning due to solving MWIS over the conflict graph being the main bottleneck. we therefore capped the number of iterations at 50 (which is sufficient for the 4 x 4 FROZEN LAKE environment.
9

---

Future work includes improving the computational efficiency of our methods, extending the DIA framework continuous MDPs, and extending the experiments to evaluate alignment without reward modeling in more complex or richer environments.
Also, did not evaluate history-conditioned BC or recurrent sequence models because the environment is fully observed. A next step is to compare TGL to history-conditiones BC or recurrent models in controlled partially observed tasks and to develop a history-aware TGL that builds conflict graphs over history features or trajectory segments.
Conclusions and Future Work
This work introduces Trajectory Graph Learning (TGL), a novel framework for trajectory- level policy alignment that bypasses reward modeling. By leveraging structural assumptions often met in practice, TGL enables efficient and theoretically grounded planning in both known and unknown environments. Our theoretical results highlight the inherent complexity of direct. trajectory imitation, while our algorithms demonstrate strong empirical gains over conventional imitation learning methods. These findings underscore the promise of structure- aware trajectory alignment for reliable long-horizon decision-mal making in reinforcement learning. A key direction going forward is extending the theory to continuous MDP settings and the development of trajectory-Ieve RL benchmarks, specifically designed evaluate alignment without reward modeling. This may involve adapting existing environments designing new ones where trajectory sets can be meaningfully constructed, compared, and evaluated. Building such benchmarks is non-trivial and will likely require substantial engineering effort, especially in continuous or high-dimensional domains such as robotics, autonomous driving, or natural language generation. Additionally, improving the efficiency of TGL, through approximate solvers, amortized inference, or scalable graph-based methods, will be crucial for extending its applicability to larger and more complex settings.
Acknowledgements
YL is supported in part by NSF grant 2221871 and an Amazon AI Fellowship. LY is supported in part by NSF grant 2221871, and an Amazon Faculty Award.
References
P. Abbeel and A. Y. Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the twendy-first international conference on Machine learning, page 1, 2004.
Y. Abdelkareem, S. Shehata, and F. Karray. Advances in preferenco-based reinforcement learning: A review. In 2022 IEEE international conference on systems, man, and cyber- netics (SMC), pages 2527 2532. IEEE, 2022.
A. Agnihotri, R. Jain, D. Ramachandran, and Z. Wen. Best policy learning from trajectory preference feodback. arXie preprint arXiv:2501.1887 2025.
R. Akrour, M. Schoenauer, and M. Sebag. Preference- based policy learning. In ECML-PKDD, 201la.
R. Akrour, M. Schoenauer, and M. Sebag. Preference--assel policy learning. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2011, Athens, Greece, September 5-9, 2011. Proceedings, Port I 11, pages 12-27. Springer, 2011b.
D. Amodei, C. Olah, J. Steinhardt, P. Christiano, J. Schulman, and D. Mané. Concrete problems in ai safety, arXiv preprint Xic:1606600566 2016.
G. An, J. Lee, X. Zuo, N. Kosaka, K.-M. Kim, and H. O. Song. Direct preference-based policy optimization without reward modeling. Advances in Neural Information Processing Systems, 36:70247 70266, 2023.
Assembly AT. Decoding strategies: How 1lss choose the next word. wwtpo//ddooddnggtteoeoo -eooggissssso-lle how-llos------- weo--lmm-chhosettaee tepoose-the-mee wetooosetteeeeetttoooeeeee next-word, 2023. 2025-05-02.
Accessed:
10

---

P. Auer, N. Cesa- Bisa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 27(2-3):235-255) 2002.
G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba. Openai gym. Xiv prepriut orXiu:1606.011 01540, 2016.
D. Brown, W. Goo, P. Nagarajan, and S. Nickum. Extrapolating beyond suboptimal demonstrations via inverse reinforcement learning from observations. In International conference on machine learning, pages 783-792 PMLR, 2019a.
D. Brown, W. Goo, P. Nagarajan, and S. Niekum. Extrapolating beyond suboptimal demonstrations via inverse reinforcement learning from rankings. In ICLR, 2019b.
R. Busa-Fekete, B. Szörényi, P. Weng, W. Cheng, and E. Hüllermeier. Preference-basee evolutionary direct policy search. In ICRA Workshop on aulonomous learning, volume 2, 2013.
J. Chang, M. Uchara, D. Sreenivas, R. Kidambi, and W. Sun. Mitigating covariate shift in imitation learning via offline data with partial coverage. Advances in Neural Information Processing Systems, 34:965-979, 2021.
W. Chen, Y. Wang, and Y. Yuan. Combinatorial multi-armed bandit: General framework and applications. In International conference on machine learning, pages 151 159. PMLR, 2013.
P. F. Christiano, J. Leike, T. Brown, M. Martic, S. Legg, and D. Amodci. Deep reinforcement learning from human preferences. Advances in neural information processing syslems, 30, 2017.
A. Dosovitskiy, G. Ros, F. Codevilla, A. Lopez, and V. Koltun. Carla: An open urban driving simulator. In Conference robot learning, pages 1-16. PMLR, 2017.
C. Finn, Levine, and P. Abbeel. Guided cost learning: Deep inverse optimal control via policy optimization. In JCML, 2016.
Fu, K. Luo, and S. Levine. Learning robust rewards with adversarial inverse reinforcement learning. arXiv preprint arXix: 11248, 2017.
J. Fu, K. Luo, and S. Ermon. Learning robust rewards with adversarial inverse reinforcement learning. In JCML, 2018.
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP- 1P-CCopletteeess. W. H. Freeman, 1979.
A. Gleave, M. Taufeeque, J. Rocamonde, E. Jenner, S. H. Wang, S. Toyer, M. Ernestus, N. Belrose, Emmous, and S. Russell. imitation: Clean imitation learning implementations. arXiv preprint ar arXio:2211. 11917, 2022. doi: 10.48550/arXi 2211.11992. URL https:
//arxiv. org/
11972.
J. Ho and S. Ermon. Generative adversarial imitation learning. In NewrIPS, 2016.
X. Hu, J. Li, X. Zhan, Q-S. Jia, and Y.QQ. Zhang. Query-policy misalignment preference- based reinforcement learning. arXiv preprint arXiv:2305.17400, 2023.
W. Huang, H. Tiu, 7. Huang, and C. Lvv. Safety-aware human-in-the-llogg reinforcement learning with shared control for autonomous driving. IEFE Transactions on Intelligent Transportation Systems, 2024.
A. Hussein, M. M. Gaber, E. Elyan, and C. Jayne. Imitation learning: A survey of learning methods. ACM Computing Surveys (CSUR), 50(2):1-38 2017.
H. Johan. astad. clique hard approximate within nl. Acta Mathemalica, 182:105 142, 1999.
11

---

J. Kaplan and et al. A baseline analysis of reward models' ability to generalise. arXiv preprint arXiv:2305.01660 2023.
A. Komanduru and J. Honorio. On the correctness and sample complexity of inverse reinforcement learning. Advances in Neural Information Processing Systems, 32, 2019.
N. Lambert and R. Calandra. The aligmment ceiling: Objective mismatch in reinforcement learning from human leedback. arxiv preprinl arXiv:2311.000 1..0068, 2023.
J. Leo, J. Hwangbo, L. Wellhausen, V. Koltun, and M. Hutter. Learning quadrupedal locomotion over challenging terrain. Science roboties, xcab)565,5 2020.
A. Y. Ng, D. Harada, and S. Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In Leml, volume 99, pages 278-287. Citeseer, 1999.
A. Y. Ng, S. Russell, et al. Algorithms for inverse reinforcement learning. In leml, volume 1, page 2, 2000.
L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, el al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35:27730 0177730-2774,, 2022.
R. Rafailov, A. Sharma, E. Mitchell, C. D. Manning, S. Ermon, and C. Finn. Direct preference optimization: Your language model is secretly reward model. Advances in Neural Information Processing Systems, 36:53728 53741, 2023.
S. Ross, G. Gordon, and D. Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pages 627-635. JMLR Workshop and Conference Procoedings, 2011.
A. Saha, A. Pacchiano, and J. Lee. Ducling rl: Reinforcement learning with trajectory preferences. In International Conference on Artificial Intelligence and Statistics, pages 6263-6288. PMLR, 2023.
A. Szot, A. Zhang, D. Batra, Z. Kira, and F. Meier. Be-irl: Learning generalizable reward functions from demonstrations, arXiv preprint arXiv:2303.1619, 2023.
F. Torabi, G. Warnell, and P. Stone. Behavioral cloning from observation. arXiv preprint Xrxi 01954, 2018.
K. Waugh, B. D. Ziebart, and J. A. Bagnell. Computational rationalization: The inverse equilibrium problem. arXiv preprint ar 1rXiv:1308.3500 2013.
A. Wilson, A. Fern, and P. Tadepalli. A bayesian approach for policy learning from trajectory preference queries. Advances in neural information processing systems, 25, 2012.
Y. Xu, R. Wang, L. Yang, A. Singh, and A. Dubrawski. Preference-basee based reinforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems, 33:18784 18794, 2020.
Y. Zeng, G. Liu, W. Ma, N. Yang, H. Zhang, and J. Wang. Token-level direct preference optimization. arXie preprinl 24N.29444,1199,, 2024.
W. Zhan, Y. Chen, and D. Sadigh. Reward-agnostic preference-based policy optimization. In ICML, 2023.
Y. Zhao, M. Wang, and J. Doe. A survey of decision- making and planning methods for self- driving, Frontiers in Newrorobotics, 19:1451923, 2025. URL attps://wwi frontiersin. org/articles/ 2...03399//00 0389/fnbbr wnwot.....tt.. 2025. 1451923/fu11.
B. Zhu, M. Jordan, and J. Jiao. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. In International Conference on Machine Learning, pages 43037-43067. PMLR, 2023.
B. D. Ziebart, A. L. Maas, J. A. Bagnell, and A. K. Dey. Maximum entropy inverse reinforcement learning. In AAAI, 2008.
12

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning rescarch, addressing issues of reproducibility, transparency, rescarch cthics, and socictal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the chocklist guidelines carcfully for information how to answer these questions. For each question the checklist:
You should answer [Yes] [No] or [NA]
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to '[No] ', it is perfectly acceptable to answer '[oo] provided a proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive' or "we were unable to find the license for the dataset we used'). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true is often more muanced, so please just use your best judgment and write a justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The paper is organized based on the abstract and the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? [Yes]
Answer:
Justification:
We discussed the limitations of our theory and experiments
13

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate 'Limitations' section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g.. if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting, Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions favor of transparency play an important role in developing norms that preserve the inlegrity of the communily. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer:
[Yes]
Justification: The paper provides rigorous assumptions and complete proof in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question:
Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? [Yes]
Answer:
Justification: We provide all hyperparameters used our experiments in our appendix section.
Guidelines:
The answer NA means that the paper does not include experiments.
14

---

If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility For example, the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (e.g., in the case of large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
be accomplished in various ways.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contributtion. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility: In the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Docs the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer:
[No]
Justification: We believe we have provided detailed instructions to faithfully reproduce our experiment results.
Guidelines:
The answer NA mcans that paper docs not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (lttps://nips.cr cc/ for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers camnot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only a subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
15

---

Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code permitted.
6. Experimental setting/ details
Does the paper specify all the training and test details (e-g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: We have provided all of the settings used our experiments and described them in our experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, material.
supplemental
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes]
Question:
Justification: We found our experimental results over multiple tries remain consistent, and we reported 95% confidence intervals in our experiment.
Guidclines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confidence intervals, or statistical significance tests, at least. for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/ train/test /est split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they calculated and reference the corresponding figures tables in the text.
Experiments compute resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Answer: [Yes]
Justification:
We have described the compute resources used in the appendix.
Guidelines:
The answer NA mcans that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
16

---

The paper should provide the amount of compute required for each of the individual experimental runs well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g,, preliminary or failed experiments that didn't make it into the paper).
Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http://aarrppps..pppiiil//////// /ttppplcc//hicccuuueeeellllll csGuideliuidennnee
Answer: [Yes]
Justification: Our research do not have problems with ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors deviation from the Code Ethics.
No, they should explain the special circumstances that require
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification: There no society impact of our work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g,, disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point out. For example, point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
legitimate to
The authors should consider possible harms that could arisc when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (onael or unintentional) misuse of the technology.
If there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e-g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the elficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
17

---

Released models that have a high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
It is cited properly.
Guidelines:
The answer NA means that the paper does not use existing assels.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., websito), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode thcode. cowccoo////oooo/ datasete has curated licenses for some datascts. Their liconsing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assots?
Answer:
[NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codee model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of Instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Question:
Answer: [NA]
Justification: The research has nothing to do with human subjects.
Guidelines:
18

---

for The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, non-standard component of the core methods in this research?' Note that the LLM is used only for writing, oditing, formatting purposes and docs not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, or non-slandard components.
Please refer to our LLM policy pettss//nnurrpst httprrpp..../ooeeeeneee//////110 what should or should not be described.
A Technical Appendices and Supplementary Material
A.1 Remaining Algorithm pseudocodes
We provide the remaining algorithms in this section.
19

---

Algorithm 3 ENUMMWIS((G W,,6))
Require: Conflict graph G PV with [V] M; weights V (0, 1] satisfying
w(r) 2 ED
Ensure: Maximum-weight independent set S*
1: K + [1/e
> any independent set has size S K
2: Whest + 0. 5" 50
3: for all subsets X C with |X| S K do
4: if X independent in G then
5:
W Evex w(r)
6: if W > W best then West W, S -
7:
8: return S"
A Algorithm 4 TGI--PRNNDD
Require: Finite-horizon Tree MDP (S.A,P.H) Expert- Labeled Trajectory Set Tael {T]] where = (s), .i........ sH d'r).
Ensure: Pruned set .M with final weights
1: for all Tú E Tse do
2:
I H-1
P(s
s/1,a) 0i))
3: M T ((Ti, w; {TTomm: Woom]] } f {(T,) w;)}
active trajectories leaf - root
4: for = H. -1, do
5:
as.) + 0, (s)
b map (s, a) + summed weight Combine the non-conficting trajectories
6: Com (s, 2, as)
7:
for each (Toom: Woom) E E do
8:
Pick any trajectory
Tcom
Just choose a representative
9:
(8,a) < (T), (T)
10:
Agg (s,a) a) + Agg((s, a)] Wcom
Aggregate the weights for the same (sh an)
11:
Csm + Teom Com (s, a))
M + [(Com[(s (s, a)). Agg((s, a)) Com()))C(())..))) a)] * 0)
13:
for each E {s|Com (s,a) + 0) do
a" max.ex Agg (s, a)
15:
Delete Com (8,, a)), + from M
w" Agg.gg(s a)]
17: for all 7i E . with = (s) af
s d'y) do
for h == to H do
19:
(s),) oj.
For states not covered by U Tr, Th via a default rule return M, π
21:
A.2
Example: BC Fails to Capture Expert Trajectories
MDP Setup
States: 5 82,
Actions: A= [01,a2}
Transitions: Deterministic transitions from $1 to 82 with any action
Expert Trajectorics
Ti (51, 01, $2, (2)
72 (81, 02 82, (1)
Behavior Cloning (BC) Limitation Behavior cloning only observes state-action pairs: (81, 01); (21, (82, 01); (82, 02)
resulting in:
At s1, both a₁ and a2 appear equally good.
20

---

At 82, both a1 and appear equally good.
Thus, BC will learn:
<(ai8s)) = ( (1) - 0.5, M(a](32) - (a2 (2) = 0.5
Consequence Due to this ambiguity, the probability of correctly reproducing either expert trajectory is:
P(T.) t ( (1) [[22)3)) = 0.5 x 0.5 0.25
P(72) T (a2]))) ((i))))) [2) 0.5 0.5 0.25
Total expert trajectory probability = 0.5
Direct Trajectory Alignment Advantage Direct trajectory alignment explicitly optimizes for the sequence:
max
Σ
P+(T)
(T(
ensuring the policy preserves the correct sequence with probability 1, with either m(o1ls)) 1, (T(2)(5))) = 1; or (1))51)) = 1, (2)](s)) = 1, since it learns to produce both trajectories as whole entities, rather than decomposing them into ambiguous stale-action pairs.
A.3 Proof of Theorem 1
In this section, we want to prove that finding the optimal policy in the binary-labeled expert-labeled trajectory set setting is NP-complete. Before providing the main content of proof. We first define the following variant of MWIS problem. Definition 6 (MWIS<I).
Input.
A graph G EV,
A weight function w : V + (0,
rational threshold K E (0.1)
Condition For every independent set T C V it holds
Σ w(w)) <1
eEl
Question Does there exist an independent set I I with
Σ Ew( K
VET Theorem 5 (MWIS<1 is NP comoplette) The decision problem in Definition 6 is NP complete.
Proof. Membership in NP. A certificate is an independent set I C V. We can verify independence in O(E)) time and compute Ever w(w) in O([T) time, so the problem lies in NP.
We reduce from the classical MAXIMUM INDEPENDENT SET (MIS) problem, known to be NP uu-complete. The problem is: A graph G (V, E) and integer 2 and the question is: does contain an independent set of size at least t?
Reduction. Given an instance (G,t) of MIS with IV(G)), construct (G, w, K) for MWIS as follows
w(D) 1 VU V(G),
K n+1 (<
n n+1
The construction uses only Ollog bit rationals, henee is polynomial in n. For any independent set we have
Σ Ew(o)
< n
< 1,
DET n n
n
so the promise in Definition 6 is satisfied.
21

---

Because every vertex has the same weight,
2 1
E w(v)
2
= K.
n+1
n n+1
VEI
Thus t,,t) E MIS iff (G, K) EMWIS
The reduction polynomial, establishing NP hardness. Since MWIS is in NP and NP hard, it is NP complete.
Now we can establish the proof of Theorem 1.
Proof. First, let us restate the original problem.
Original Problem: Find the optimal deterministic policy
Input: A MDP and the binary expert-labeled trajectory set Teel = (T (or called level-1 trajectory)
Question: there any deterministic policy that can visit the level-1 trajectories with probability at least p?
We will do this in two steps:
Step 1: Show the original problem is in NP
To show that the original problem is in NP, we must demonstrate that a given solution can be verified in polynomial time.
Given a deterministic policy π = ]e]HH] we can:
1. Check whether the good trajectory does not have conflict with policy m.
To be specific, for a good trajectory = (31 01, $2, 02, 8H ah), check whether (1())) 01, (2(2)) = 02, TT = ag If yes, add up the weight (the probability product) of this trajectory (We denote this set as Q). The complexity is at most O(M H).
2. Sum the weights: Calculate Eweq w and check if it is at least p. This takes at most O(M) time.
Since both checks can be performed in polynomial time, the original problem in NP.
Step 2: Reduction from MWIS
We will reduce from the MWIS problem (Definition 6), which is known to be NP-complete from Theorem 2.
Reduction from MWIS<1 to original problem
1. Any weighted graph can be represented corresponding probability The basic idea is because we can always find a MDP with sufficient trajectories represent. the relation between these M vertexes, i.e. M << O(SS)*AA!" The construction process is detailed in Algorithm 5 and 6. To be specific, for an arbitrary graph, we can enumerate every vertex in Breadth-Firss Search (BFS). Each time we process one vertex and use conflict trajectory pairs to record all the edges it connocts to. Then we get set of trajectorics that encoded the information of this graph. The second step is to assign the probability of the MDP given the weights of the graph, which explained in Algorithm 6. The basic idea is assign the probability kernel with the given weights w(v) E (0, 1J, and make sure the summation of all probability odds is stiil 1.
subset of trajectories with
2. Good policy implies high weight independent set. First, for any deterministic policy æ, it will produce a set of non-conflicting trajectories (any two of these trajectories are non-conflicting, we denote this set as Σ(T), and now a deterministic policy that can visit the level-1 trajectories with probability at least p, then Σ w > which WeE(T)
implies there exists an independent set that the summation of weights is larger than p.
Notice that the reduction process Algorithm and is polynomial in M, therefore, we can conclude the original problem is also NP-complete.
22

---

Algorithm 5 BFS-Based Trajectory Construction
Require: Graph G = E), horizon H
Ensure: Trajectories (r(w))oEV, each of length
1: Pick an arbitrary root. vertex E V
2: Fix 7(1) < (81:0):...;H::0 (H)
3: Visited <- {u1}; enqueue i1 in queue Q
4: for all v V {wi} do
5: 7(V) +- (31, St,
St, "........0000.. (0,00,,5000)))))
undecided after step 1
6: while Q not empty do
7: <- Deqqeue(())
8: for all neighbor of u with v & Visited do
9: Fix remaining undecided steps in r(u) so it is unique
10: Construct T(r) so that there exists time with & r(o) ((u) and aj (00) * ai z(w)
11: Visited <- Visited U {v}; enqueue v
return (T(o)eeeV
Algorithm 6 Thaasitionn-Probabilii Assignment Using Vertex Weights
Require: Graph G = (V, E) with weights w V - (0, 1], Σves w(v) S 1, is an independent set.
Require: Trajectorics {T()) hev from Alg. 5
Ensure: Transition kernel P(- (.))
/* Preparation */
1: for all V do
2: Write T(u) = (s1, "1....,,................. SH, az)
/* First statc-action pair (s1, a1) */
3: for all edge {V1, 22) w/} E do
4: P(s2 a), mmx(((())) w(22)}
5: Distribute remaining mass over other successors of (81,a1)
/* Finalize each adjacent pair */
6: for edge (u, v) E do
7: if w(u)= > w(v) then
8:
Make the remainder of r(u) deterministic
In ((v) add one stochastic step with prob. w(v)/w(u) where ((0) = s,(()) and
9:
(1))
# a, T(u)
a
10:
else
11:
(Symmetric update with a + v)
12: for all (x) with stochastic successors do
13:
Normalize P( 18, a) so Σ. P( 8,0)
14: return P( 1
23

---

A.4 Proof of Theorem 2
Time complexity of Algorithm 1 with oracle Algorithm 3. Let M = [Tacl and H the horizon length, and set.
Then
"Conflict-graph construction (lines 3 7): 0 [M 2
H)) H( time.
2. "Weight computation ** (lines 9-11): O(MH).
3. **Oraele call** ENUMMWIS(G, w, co) (Alg. 3):
Σ M ( 0(1)
0 (M) O(M*) (since K is a constant).
**Policy extraction** ** (lines 15-18): O(S H) O(KH). Putting these together gives
T(M, H) O MH + M + KH) 0(MHH + M*).
In particular, if (hence K) is fixed constant, this is polynomial time O(M + M1/w).
A.5 Proof of Theorem 3
Proof of Time Complerity. Let:
M be the number of trajectories,
H be the trajectory horizon,
|A| be the number of discrete actions,
[S] be the number of possible states por timestep.
Weight Computation: Each trajectory т; assigned weight via the product of H transition probabilities. Across M trajectories, this requires:
O(M-H)
2. Backward Pruning Loop: For cach timestep h = HH 1 (total H iterations):
Aggregating weights across identical (sh, ax) pairs requires scanning all active trajectories: O(M),
Merging trajectories that share the same (sh, an) pair: O(M),
For each state 84, selecting the action dn with the maximum total weight among most [A] options Icads to: O(M (A]) in the worst case (since there are at most M unique state-action pairs).
Therefore, the total cost per timestep is:
O(M IA)
and over H timesteps:
O(H M [A))
3. Final Output: The pruned result. is returned by traversing at most M remaining elements:
O(M)
Total Time Complexity: Summing all terms, the dominating component from the backward pruning loop, yielding the final result:
O(H M (A)
24

---

A.6 Proof of Theorem 4
Proof. The proof of Theorem is based on the Theorem in [Chen et al., 2013]. For the convenience of the readers, we show the complete process here.
For variable T. let T. be the value of T, at the end of round t, that is, Tui is the number of times policy played that matches trajectory vs in the first rounds. For variable fa, let As.s be the value of A after the policy which matched trajectory os is played times. Then, the value of variable be at the end of round is As,,... For variable ui, let ug be the value of u, at the end of round t. Let un = (u1,t).... uMrz) be the random vector fed to the MWIS oracle as the input in line 12 of Algorithm 2 at round t.
We also maintain counter Qi for each trajectory es after the M initialization rounds. Let Qi be the value of Qi after the t-th round and Qi.M- = Note that Σ, Qi.M = M. Counters {Q.) M are updated as follows.
For a round & >> M, let St be the independent set selected in round t by the MW1S oracle (line 12 of Algorithm 2). Round & is bad if the oracle selects a bad set S, E Saub- If round t bad, let i argminges. Qj We increment Q2 by one, i.c., Qu = Qi,--1 we find the trajectory V with the smallest counter in St and increment its counter. If is not unique, we pick an arbitrary arm with the smallest counter in Sy. On the other hand, if S. & SB, no counter will be incremented.
That is,
By definition Qi, S Tu.- Notice that in every bad round, exactly one counter in {Q1)== incremented, the total number of bad rounds in the first rounds is less than or equal to Σ, Qi,
MM is
Define & = 6M Consider bad round 1, St E Saub is selected and counter Q2 of some A
arm E Se is updatod. We have
Qia m m.(a +1)
Σ
ISe E Saub] men
1=1
t=
I[S E Soub. Qi > P3.--1QQi111 > bn}
1=++1 [E|m]
8
I[S E Sau,, Qu > Qs,--,, 0,,-1 > 4
1= [|
Σ t=
IfS E Saub, vi E St, Qi,-1 > 4
I1S E Saub, Vi E S₁ T2,111 > {
1=
We first claim that P1(SS E Soub, vi E Ti, > ( 2 . In fact, for any i E [M],
P - mi 2 /3lnt/ (2T),
Pr
t-1
Pr KlRio - mll /3lnt/ (2s) Tea-1 = $}]
1-1
Σ Pr [|A.. - mil /3lnt/(25)
<
St. 2e 3lnt 2t 2
where the last inequality is due to the Chernoff Hoeffding bound. Define Ag. 3lnt (a random variable since T is a random variable), and event Ey = 21:a-1
VVi E (m). - ul S Ar.). By union bound, Pr[-E,] 2 M t-2 According
25

---

to line 11 of Algorithm 2, we have Wiς - Pe.Te-- = As,e- Thus AATT.. MMs S Ai, implies that ui,t 2 p4.
Let A V 24,
3lut which not random variable.
Define random variable A,
max (Ai, i E S.). Then
vi St, |4, 4 S 2A, (S, E Sub. E S, T,,-- > 4,) A> A,
=
Let. U. (ui,t).... UM,)) be the vector representing the adjusted expeclation vector at round Then,
E U. 2
If St E Saub, Vi St, T1,-11111 > 4 holds time t, we have the following important deriva- tion:
Σ DES,
Po + 2MA >
Σ JES
Po + 2MA 2
Σ
Uu 2 p'
DES.
Since 4 6M5 ht
have 2MA Amin- Therefore,
Pr| E Saubi Vi E St Ti,-1 > ()] = =0
Pr [ E Saub, Vi E St, Ti,--1 > 41)
- Pr < 2. M t
The claim thus holds. We have, E E Qin S M (e,, + + E
2M 1
6M
A
(5+1) ...).M. M.
Notice that each time we select bad independent set time incur regret at most Amax Then we obtain the regret bound as follows.
(n)
M
E
Qi,
max
6 log n
M2
nr?
+
+11
M
A max
A min
3
3 log K Amax
0
A2
min
A.7 Experimental Details and Hyperparameters
All ppeerpparamtter, stopping critcria and environment scttings are listed in Table 2.
A.8 Compute Resources
All runs use a single Google Colab instance with an NVIDIA T4 (16 GB GPU RAM) kernel. Training the PPO expert for 50 000 steps takes around min 20 s; one TGL-UCB run (50 iterations, 20 nodes) takes around 45 s. The evaluation of the three methods that we compare (TGL, BC, and PPO expert) takes around min 30 Most of the code are not GPU accelerated, so using CPU kernel is also feasible.
26

---

Table 2: Hyper-parameters used in every experiment.
Component
Hyper-parameter
Value
Environment
Grid size
4 x
Episode horizon H Random-action noise
10
0.10
PPO expert
Learning rate a_steps
1 1 10-3 -3
128
Batch size
64
Epochs per update
4
Discount ?
0.99
GAE X
0.95
Clip range
0.2
Total steps
50 000
TGL-UCB
0.9
Initial samples mp
10
0.01
Max iterations
50
Behavioural Cloning
Batch size
8
Training epochs
20
27


Reviews:
[{"review_id": "TBwajZzwpU", "reviewer": "Reviewer_1Der", "summary": "This paper proposes Trajectory Graph Learning (TGL), a novel framework that directly aligns policies with expert-labeled trajectories to preserve long-horizon behavior without relying on reward signals. By modeling the trajectory alignment problem as a Maximum-Weight Independent Set (MWIS) problem, the authors address the inherent complexity of the problem and develop efficient algorithms for both known and unknown environment dynamics. The theoretical analyses demonstrate the NP-completeness of the general trajectory alignment problem and provide polynomial-time solutions under certain structural assumptions. Experimental results on grid-world tasks show that TGL outperforms standard imitation learning methods, especially for long-trajectory planning.", "questions": "1.\tCan the authors conduct experiments on more complex and real-world environments to further validate the scalability and robustness of the proposed TGL framework? \n\n2.\tCan the authors report error bars or perform statistical significance tests on their experimental results to provide a more rigorous evaluation of the performance of TGL compared to baselines?\n\n3.\tCan the authors provide more details on the practical relevance and validity of the structural assumptions (bounded realizability of expert trajectories, tree-structured MDP) made in their theoretical analyses?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1．\tThe idea of modeling the trajectory alignment problem as an MWIS problem is interesting and provides a novel perspective on solving the trajectory imitation challenge.\n\n2．\tThe paper provides a thorough theoretical analysis, proving the NP-completeness of the general problem and presenting efficient algorithms under practical assumptions.\n\n3．\tExperiments on grid-world tasks demonstrate the effectiveness of the proposed framework compared to standard imitation learning methods.\n\n\nWeaknesses:\n\n1．\tThe experiments are conducted on relatively simple grid-world tasks. More experiments on larger or continuous MDPs are needed to fully evaluate the scalability and robustness of the proposed method.\n\n2．\tThe experimental results lack error bars or other statistical significance measures, which makes it difficult to assess the consistency and reliability of the reported performance.\n\n3．\tThe paper does not appear to have been compiled using the official NeurIPS 2025 LaTeX template, which is a requirement for submission.", "was_revised": true, "final_justification": "After considering the author response and the other reviews, I find my concerns have been adequately addressed. Specifically:\n\n+ The authors clarified why the method is not applicable to continuous MDP tasks, which appropriately bounds its scope.\n\n+ They added error bars to the experimental results and strengthened the discussion of their theoretical assumptions.\n\n+ They committed to submitting a version formatted with the official NeurIPS 2025 LaTeX template.\n\n+ I continue to find the idea of modeling the trajectory alignment problem as a maximum weight independent set (MWIS) problem interesting.\n\nGiven these points, I intend to retain my positive score.", "rebuttal": "We thank the reviewer for recognizing the value of our work and providing\nvaluable feedback. We address the concerns of the reviewer as follows.\n\n$\\textbf{Q1.}$ “The experiments are conducted on relatively simple grid-world tasks. More experiments on larger or continuous MDPs are needed to fully evaluate the scalability and robustness of the proposed method.\"\n\n$\\textbf{A1.}$ We appreciate the reviewer’s suggestion to evaluate our proposed TGL framework in more complex and real-world environments to further assess its scalability and robustness. First, we emphasize that the theoretical foundation of TGL is built upon a Markov Decision Process (MDP) with a finite number of states and actions, as well as a finite set of expert trajectories. Therefore, our current framework does not extend to continuous MDPs or settings involving an infinite number of expert trajectories. Regarding larger environments, our experimental objective is not to showcase raw performance in high-dimensional state and action spaces, but to isolate and validate TGL’s capacity to solve the trajectory alignment problem via the novel MWIS-based method. Scaling the grid to larger sizes—such as $8 \\times 8$ or $10 \\times 10$—increases the number of states by a constant factor but does not introduce qualitatively new types of trajectory conflicts. As a result, the core graph learning structure and learning dynamics of TGL remain consistent.\n\n\n$\\textbf{Q2.}$ “The experimental results lack error bars or other statistical significance measures, which makes it difficult to assess the consistency and reliability of the reported performance.\"\n\n$\\textbf{A2.}$ We appreciate the reviewer for pointing this out. Our primary metric, the empirical trajectory match probability, is a binomial proportion estimated over 10,000 episodes per evaluation, and each episode is essentially a Bernoulli trial: the generated trajectory either matches or doesn't match a demonstration trajectory. In the worst case: $p = 0.5$, the standard error is $\\sqrt{0.5(1-0.5)/10000} = 0.005$, which gives a 95\\% confidence interval of 0.01. Because of this, we originally decided to omit error bars as the extra numbers might add clutter to our paper. Nevertheless, we recognize that explicit intervals and better explanations make our results more reliable. Our method outperforms BC confidently when the trajectory set is large, and edges past BC when the trajectory set is small, which is expected because of the noise present in the environment (all of the methods are likely close to the maximum probability to match the demonstration trajectories). We will include these details in our revised version of the paper. Additionally, we have revised the Table 1 results in our paper using the empirical match rate as an estimate for p in standard error:\n\n**Table 1 – Trajectory-match probability (↑ better) over 10 000 episodes.  \nRows indicate the number of deterministic vs. stochastic demos in 𝒟.**\n\n| Expert-labelled set | TGL-UCB (Ours) | BC | PPO expert |\n|---------------------|---------------|----|------------|\n| 15 det / 5 stoch | **0.794 ± 0.008** | 0.775 ± 0.008 | 0.778 ± 0.008 |\n| 10 det / 10 stoch | **0.801 ± 0.008** | 0.778 ± 0.008 | 0.800 ± 0.008 |\n| 5 det / 15 stoch | **0.801 ± 0.008** | 0.771 ± 0.008 | 0.793 ± 0.008 |\n| 10 det / 5 stoch | **0.814 ± 0.008** | 0.793 ± 0.008 | 0.803 ± 0.008 |\n| 8 det / 7 stoch | **0.810 ± 0.008** | 0.774 ± 0.008 | 0.801 ± 0.008 |\n| 5 det / 10 stoch | 0.779 ± 0.008 | 0.758 ± 0.009 | **0.780 ± 0.008** |\n| 10 det only | **0.778 ± 0.008** | 0.753 ± 0.009 | 0.775 ± 0.009 |\n| 5 det / 5 stoch | **0.740 ± 0.009** | 0.713 ± 0.009 | 0.735 ± 0.009 |\n| 10 stoch only | 0.738 ± 0.009 | 0.714 ± 0.009 | **0.739 ± 0.009** |\n| 5 det only | **0.730 ± 0.009** | 0.703 ± 0.009 | 0.713 ± 0.009 |\n| 5 stoch only | **0.675 ± 0.009** | 0.673 ± 0.009 | 0.661 ± 0.009 |\n| 3 det only | **0.672 ± 0.009** | **0.672 ± 0.009** | 0.670 ± 0.009 |\n| 3 stoch only | **0.657 ± 0.009** | 0.653 ± 0.010 | 0.648 ± 0.010 |\n| 1 det only | **0.634 ± 0.010** | 0.627 ± 0.010 | 0.621 ± 0.010 |\n\n\n$\\textbf{Q3.}$ “The paper does not appear to have been compiled using the official NeurIPS 2025 LaTeX template, which is a requirement for submission.\"\n\n$\\textbf{A3.}$ We sincerely apologize for not using the official NeurIPS 2025 LaTeX template in our initial submission. We appreciate the reviewer’s attention to this requirement. We will promptly recompile the paper using the correct template and ensure that all formatting guidelines are strictly followed in the camera-ready version, should the paper be accepted. Thank you for pointing this out.\n\n$\\textbf{Q4.}$ “Can the authors conduct experiments on more complex and real-world environments to further validate the scalability and robustness of the proposed TGL framework?\"\n\n$\\textbf{A4.}$ We kindly refer the reviewer to our response to Question 1 (Answer 1), where we have addressed this point in detail.\n\n$\\textbf{Q5.}$ “Can the authors report error bars or perform statistical significance tests on their experimental results to provide a more rigorous evaluation of the performance of TGL compared to baselines?\"\n\n$\\textbf{A5.}$ We kindly refer the reviewer to our response to Question 2 (Answer 2), where we have addressed this point in detail.\n\n$\\textbf{Q6.}$ “Can the authors provide more details on the practical relevance and validity of the structural assumptions (bounded realizability of expert trajectories, tree-structured MDP) made in their theoretical analyses?\"\n\n$\\textbf{A6.}$ Thank you for your question. We explain the practical relevance and validity of structural assumptions in our theory here.\n\nA clear example of the bounded realizability assumption can be found in the OpenAI Gym's CartPole or MuJoCo locomotion benchmarks. In these settings, expert trajectories are often generated by a pre-trained high-performing policy (e.g., PPO or SAC). Since these policies reliably solve the task, each recorded expert trajectory corresponds to a successful rollout that occurs with consistent, non-negligible probability. Importantly, because the expert dataset is finite and curated—often by sampling from stable policy rollouts—all trajectories in the set are not only reachable but also share a uniform lower bound on their likelihood under the environment dynamics. This matches the bounded realizability assumption: each trajectory has at least some positive probability of being sampled during interaction, ensuring that the learning agent has a realistic chance of encountering similar trajectories during training.\n\nFor tree-structured MDPs, we kindly refer the reviewer to the practical motivation provided in lines 264–269. We reiterate the relevance here for clarity. Tree-structured MDPs naturally arise in scenarios where future decisions evolve independently and paths do not reconverge. For instance, in large language models (LLMs), decoding strategies such as beam search or top-k sampling generate diverse continuations from a given prompt, forming a forward tree where each branch corresponds to a distinct output sequence. Similarly, in autonomous driving, planning algorithms simulate future actions—such as turning or accelerating—under physical and safety constraints that prevent the system from revisiting prior states, yielding a branching structure of possible, non-overlapping trajectories."}, {"review_id": "R7zVwQXOM7", "reviewer": "Reviewer_CpAw", "summary": "The paper explores the problem of directly aligning policies with expert-labeled trajectories in reinforcement learning without relying on reward modeling. It proposes Trajectory Graph Learning (TGL), a framework that leverages structural assumptions to enable efficient policy planning.", "questions": "1. Given the current experiments are only conducted on a 4×4 Frozen Lake environment, it would be beneficial to validate the TGL framework on more complex environments such as larger grid-worlds or continuous state/action spaces. For example, environments like the Mujoco robotics simulations or more complex navigation tasks could provide a better understanding of the framework’s generalizability and robustness.\n2. Could you include comparisons with related methods such as Inverse RL and PbRL in the experiments? This would help to demonstrate the practical utility and advantages of the TGL framework beyond its theoretical merits.", "limitations": "The authors have not adequately addressed the limitations of their work. It is suggested to supplement the discussion on the limitations of the TGL framework in the paper, such as its applicability in different tasks and environments.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "* Strengths:\n1. The motivation of the paper is strong. It highlights the limitation of traditional behavior cloning in imitation learning, which only focuses on state-action pair alignment and neglects the broader trajectory-level structure, and proposes the idea of direct trajectory alignment, which is meaningful.\n2. The proposal of the TGL framework is innovative to some extent, aiming to solve the problem of trajectory alignment under structural assumptions.\n* Weaknesses:\n1. The paper is relatively theoretical, and some details are not well explained. For instance, the supplementary material includes the full paper with appendices in a single ZIP file, which is not in line with the NeurIPS submission guidelines. Reviewers primarily rely on the officially submitted PDF for their assessment, and any additional technical appendices should ideally be submitted together with the main paper before the full submission deadline to facilitate a more straightforward review process.\n2. The theoretical part of the paper is relatively strong, but to enhance the practical significance of the research, it would be valuable to include comparisons with related methods such as Inverse RL and PbRL in the experiments. This would help to demonstrate the practical utility and advantages of the TGL framework beyond its theoretical merits.\n3. Given the current experiments are only conducted on a 4×4 Frozen Lake environment, it would be beneficial to validate the TGL framework on more complex environments such as larger grid-worlds or continuous state/action spaces. For example, environments like the Mujoco robotics simulations or more complex navigation tasks could provide a better understanding of the framework’s generalizability and robustness.", "was_revised": true, "final_justification": "• Addressed issues\n\n– Authors will clearly state the paper’s scope (discrete, finite MDPs) and add a dedicated “Limitations & Future Work” section that explicitly discusses the need for broader benchmarks, scalability, and extension to continuous or high-dimensional domains.\n\n– Reproducibility and formatting concerns (supplementary ZIP) are acknowledged and will be corrected.\n\n\n• Unresolved issues\n\n– No new empirical results beyond the 4×4 Frozen Lake; continuous or larger-scale validation remains future work.\n\n\n• Reason for raising score to 4 (Borderline Accept)\n\n– The core contribution is a well-posed theoretical formulation and first algorithm for Direct Trajectory Alignment, accompanied by proofs of hardness and regret guarantees. The community traditionally values such foundational theory even when immediate practical impact is limited. After rebuttal, the authors commit to clarifying limitations and future directions, satisfying my main concerns.", "rebuttal": "We thank the reviewer for recognizing the value of our work and providing valuable feedback. We address the concerns of the reviewer as follows.\n\n$\\textbf{Q1.}$\n“The paper is relatively theoretical, and some details are not well explained. For instance, the supplementary material includes the full paper with appendices in a single ZIP file, which is not in line with the NeurIPS submission guidelines. Reviewers primarily rely on the officially submitted PDF for their assessment, and any additional technical appendices should ideally be submitted together with the main paper before the full submission deadline to facilitate a more straightforward review process.\"\n\n$\\textbf{A1.}$ We thank the reviewer for pointing this out and sincerely apologize for not adhering strictly to the NeurIPS submission guidelines regarding the formatting and inclusion of supplementary materials. We acknowledge that submitting the full paper and appendices as a single ZIP file may have made it more difficult to access key technical details during the review process. We will ensure that all technical appendices are properly integrated into the main supplementary PDF in accordance with the official requirements in any future submissions or revisions. We appreciate the reviewer’s understanding and will take greater care to streamline the presentation for ease of review.\n\n\n$\\textbf{Q2.}$\n“The theoretical part of the paper is relatively strong, but to enhance the practical significance of the research, it would be valuable to include comparisons with related methods such as Inverse RL and PbRL in the experiments. This would help to demonstrate the practical utility and advantages of the TGL framework beyond its theoretical merits.\"\n\n$\\textbf{A2.}$ \nWe appreciate the reviewer’s recognition of the theoretical strength of our paper. Regarding the suggestion to include comparisons with related methods such as Inverse Reinforcement Learning (IRL) and Preference-based Reinforcement Learning (PbRL), we would like to clarify that although these methods are discussed in the motivation and related work sections, our proposed TGL framework addresses a fundamentally different problem—namely, the General Direct Trajectory Alignment problem. Traditional IRL and PbRL approaches typically aim to recover a reward function and evaluate performance through value-based metrics. In contrast, TGL evaluates performance by measuring the matching probability of expert trajectories, which aligns more closely with the objectives of behavior cloning methods. This difference in problem formulation and evaluation criterion is the main reason why we chose to compare TGL against behavior cloning baselines in our experiments.\n\n\n\n$\\textbf{Q3.}$\n“Given the current experiments are only conducted on a 4×4 Frozen Lake environment, it would be beneficial to validate the TGL framework on more complex environments such as larger grid-worlds or continuous state/action spaces. For example, environments like the Mujoco robotics simulations or more complex navigation tasks could provide a better understanding of the framework’s generalizability and robustness.\"\n\n\n$\\textbf{A3.}$ We appreciate the reviewer’s suggestion to evaluate our proposed TGL framework in more complex and real-world environments to further assess its scalability and robustness. We would like to clarify that the theoretical foundation of TGL is built on a Markov Decision Process (MDP) with a finite number of states and actions, as well as a finite set of expert trajectories. As such, the current framework does not extend to continuous MDPs or settings involving infinitely many expert trajectories. With respect to larger environments, our experimental objective is not to highlight raw performance in high-dimensional state and action spaces, but rather to isolate and validate TGL’s effectiveness in solving the trajectory alignment problem through our novel MWIS-based method. Scaling the grid to larger sizes—such as $8 \\times 8$ or $10 \\times 10$—increases the number of states by a constant factor, but does not introduce qualitatively new types of trajectory conflicts. Consequently, the underlying graph structure and learning dynamics of TGL remain unchanged.\n\n$\\textbf{Q4.}$ “Given the current experiments are only conducted on a 4×4 Frozen Lake environment, it would be beneficial to validate the TGL framework on more complex environments such as larger grid-worlds or continuous state/action spaces. For example, environments like the Mujoco robotics simulations or more complex navigation tasks could provide a better understanding of the framework’s generalizability and robustness.\"\n\n$\\textbf{A4.}$  We kindly refer the reviewer to our response to Question 3 (Answer 3), where we have addressed this point in detail.\n\n$\\textbf{Q5.}$ “Could you include comparisons with related methods such as Inverse RL and PbRL in the experiments? This would help to demonstrate the practical utility and advantages of the TGL framework beyond its theoretical merits.\"\n\n$\\textbf{A5.}$  We kindly refer the reviewer to our response to Question 2 (Answer 2), where we have addressed this point in detail."}, {"review_id": "ELU9Gn5n4w", "reviewer": "Reviewer_nNgV", "summary": "This paper investigates the direct trajectory alignment problem, which aims to find a deterministic policy that maximizes the visitation probability of a given set of expert trajectories. The authors make a key theoretical contribution by proving that this problem is NP-complete, by showing its equivalence to the maximum-weight independent set problem. To overcome this computational hardness, the paper proposes polynomial-time algorithms for two special cases under known dynamics. For the unknown dynamics, a UCB-based online learning algorithm is developed and analyzed.", "questions": "- In general, the use of direct trajectory alignment is not well motivated. In the example in Appendix A.2, it is unclear to me why the DTA policy is superior than the BC policy. Could you elaborate on when and why DTA is better than BC?\n\n- In numerical experiments, could you present other performance metrics (e.g. distance to a ground-truth expert policy or task performances of the resulting policy). Additionally, how does the policy's performance vary as the horizon length (H) changes?\n\n- In line 240, I believe the complexity bound should be M^{1/\\epsilon_0}.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The proposed framework of direct trajectory alignment is a novel and interesting contribution, as it bypasses the need for reward model or any model assumptions.\n- The paper is well-structured and clearly presents its problem formulation, algorithms, and theoretical analyses.\n\nWeaknesses:\n- The proposed approaches in Section 4 and 5 appear to be well established techniques and their error bounds are also naïve.\n- While the paper claims that the method is effective for long-horizon problems, but this central claim lacks sufficient analytical or empirical support. It is not made clear why optimizing the proposed objective function inherently leads to better performance on long-horizon tasks compared to other methods.\n- The experimental validation is limited. The evaluation is conducted on a single, small-scale grid-world environment and the metric is the trajectory match probability, which is directly related to the method's objective function. This makes it difficult to assess the framework's generalization capabilities or its effectiveness on other standard performance metrics.\n- The analysis is limited to deterministic policies and the tabular setting.", "was_revised": true, "final_justification": "I have increased my score, as the authors have addressed my concerns.", "rebuttal": "We thank the reviewer for recognizing our work's value and providing an excellent summary of our results. Now we address some of the concerns and questions raised by the reviewer.\n\n$\\textbf{Q1.}$\n“The proposed approaches in Section 4 and 5 appear to be well established techniques and their error bounds are also naïve.\"\n\n$\\textbf{A1.}$\nThank you for your question. In Section 4, we introduce two practically motivated settings: bounded realizability of the expert trajectory set and tree-structured MDPs. Both settings are grounded in real-world scenarios and, importantly, admit polynomial-time algorithms. While the theoretical bounds we provide may appear relatively simple, the key contribution lies in identifying meaningful and realistic cases in which the otherwise NP-hard MWIS problem becomes tractable. In Section 5, we further develop a novel UCB-style exploration strategy tailored to our TGL framework. To analyze its sample complexity, we reduce the problem to a combinatorial multi-armed bandit (CMAB) setting. This reduction is non-trivial and reflects a careful design choice to make the exploration problem theoretically analyzable while preserving the core structure of trajectory alignment.\n\n$\\textbf{Q2.}$\n“While the paper claims that the method is effective for long-horizon problems, but this central claim lacks sufficient analytical or empirical support. It is not made clear why optimizing the proposed objective function inherently leads to better performance on long-horizon tasks compared to other methods.\"\n\n$\\textbf{A2.}$\nThank you for raising the concern regarding the analytical and empirical support for our method’s effectiveness in long-horizon problems. For analytical support, we kindly refer the reviewer to Appendix A.2, where we provide concrete examples illustrating how behavior cloning (BC) fails to capture expert trajectories. The key intuition is that traditional methods, such as BC, often rely solely on cumulative rewards and fail to preserve the sequential structure of trajectories. In contrast, our method directly aligns with entire trajectories, capturing richer and more complete information. This leads to better performance under trajectory-level metrics such as matching probability. On the empirical side, we have also discussed practical motivations in real-world applications—such as self-driving and large language models (LLMs)—where decision sequences are long and branch significantly. For instance, in self-driving, trajectory planning involves reasoning over long, non-overlapping future paths; in LLMs, decoding strategies like beam search generate diverse sequences that resemble tree-structured decisions. These examples further highlight the importance of modeling full trajectories rather than relying on scalar feedback alone.\n\n\n$\\textbf{Q3.}$\n“The experimental validation is limited. The evaluation is conducted on a single, small-scale grid-world environment and the metric is the trajectory match probability, which is directly related to the method's objective function. This makes it difficult to assess the framework's generalization capabilities or its effectiveness on other standard performance metrics.\"\n\n$\\textbf{A3.}$\nThank you for highlighting the scope of our experiment. Our experiment deliberately focuses on a small, discrete grid-world environment because (i) it allows us to control for confounding factors and isolate the effect of our new trajectory-alignment framework and objective, and (ii) the theoretical guarantees we have proven currently assume a finite state-action space, so extending the experiments beyond finite MDPs first requires extending our theoretical work. While the evaluation metric, trajectory match probability, indeed relates to the objective function, this similarity is intentional. In the direct trajectory alignment setting we propose, a policy is only considered \"good\" when it reproduces the demonstrations, independent of learned or assigned rewards. For example, even if the demonstration trajectory set is objectively \"poor\" based on rewards, the desired goal of our framework remains the same: match the demonstrations. That said, we agree that supplementing match probability with other metrics will help assess the framework's generalization capabilities. In the revised version of our paper, we will add additional measurements of trajectory quality and conflict-graph density, and error bars as a statistical measure to show the applicability of our framework in larger environments.\n\n$\\textbf{Q4.}$\n“The analysis is limited to deterministic policies and the tabular setting.\"\n\n$\\textbf{A4.}$\nThank you for the thoughtful suggestion. First, our paper begins with the deterministic policy setting because it offers a clearer formulation and is more straightforward to analyze. However, extending to stochastic policies is not a fundamental issue in our framework. In fact, for the trajectory alignment problem we consider, the optimal policy can always be found within the set of deterministic policies. One can think of the space of all policies as a polyhedron, where deterministic policies correspond to its vertices. Since the optimization objective is linear with respect to the policy distribution, the optimal solution lies on the boundary of this polyhedron—i.e., at a deterministic policy. Thus, it suffices to focus on deterministic policies.\n\nSecond, while our setting assumes a finite action space to ensure polynomial-time tractability, the state space can be infinite. This is because the core computational complexity of the TGL framework arises from learning the trajectory alignment graph, which depends on the number of expert trajectories rather than the total number of states. As a result, in the sample complexity bound of our UCB-style exploration method (Section 5), the number of states does not appear. This shows that our method is not restricted to the tabular setting and can generalize to environments with large or even infinite state spaces.\n\n$\\textbf{Q5.}$\n“In general, the use of direct trajectory alignment is not well motivated. In the example in Appendix A.2, it is unclear to me why the DTA policy is superior than the BC policy. Could you elaborate on when and why DTA is better than BC?\"\n\n$\\textbf{A5.}$\nThank you for your question regarding the example in Appendix A.2. We are happy to provide a more detailed explanation. In this example, we consider two expert trajectories to align with: $\\tau_1 = (s_1, a_1, s_2, a_2)$ and $\\tau_2 = (s_1, a_2, s_2, a_1)$. Traditional behavior cloning (BC) treats each state-action pair independently. In this case, since both $a_1$ and $a_2$ appear equally often at both $s_1$ and $s_2$ across the two trajectories, BC learns a uniform policy:\n\n$$\n\\pi_1(a_1 \\mid s_1) = \\pi_1(a_2 \\mid s_1) = 0.5,\\quad \\pi_2(a_1 \\mid s_2) = \\pi_2(a_2 \\mid s_2) = 0.5.\n$$\n\nwhere $\\pi_1$ and $\\pi_2$ are the policies in step 1 and 2 respectively.\nHowever, this policy fails to capture the sequential structure of either trajectory. The probability of reproducing each expert trajectory under this policy is:\n\n$$\nP(\\tau_1) = \\pi_1(a_1 \\mid s_1) \\cdot \\pi_2(a_2 \\mid s_2) = 0.5 \\times 0.5 = 0.25,\n$$\n$$\nP(\\tau_2) = \\pi_1(a_2 \\mid s_1) \\cdot \\pi_2(a_1 \\mid s_2) = 0.5 \\times 0.5 = 0.25,\n$$\n\nso the total matching probability for expert trajectories is only:\n$$\nP(\\tau_1) + P(\\tau_2) = 0.25 + 0.25 = 0.5.\n$$\n\nIn contrast, Direct Trajectory Alignment explicitly optimizes the sequence-level probability:\n\n$$\n\\max_{\\pi} \\sum_{\\tau \\in \\{\\tau_1, \\tau_2\\}} P_\\pi(\\tau),\n$$\n\nallowing the policy to recover the full structure of either trajectory. For instance, setting $\\pi_1(a_1 \\mid s_1) = 1$, $\\pi_2(a_2 \\mid s_2) = 1$ will reproduce $\\tau_1$ with probability 1; similarly, $\\pi_1(a_2 \\mid s_1) = 1$, $\\pi_2(a_1 \\mid s_2) = 1$ will reproduce $\\tau_2$. In both cases, the total expert trajectory\n\n$\\textbf{Q6.}$\n“In numerical experiments, could you present other performance metrics (e.g. distance to a ground-truth expert policy or task performances of the resulting policy). Additionally, how does the policy's performance vary as the horizon length (H) changes?\"\n\n$\\textbf{A6.}$ We thank the reviewer for the suggestion, but would like to clarify that our work introduces a new setting, direct trajectory alignment, for which the natural evaluation criterion is the probability that the resulting policy reproduces the finite expert trajectory set. Because the goal is replication rather than reward maximization, traditional RL metrics such as episode return or distance to an optimal \"ground-truth\" policy are not informative and could even be misleading. For example, a policy may score highly on those metrics while never matching any demonstration trajectories. In our framework, how good our policy is is determined solely by the quality and diversity of the provided trajectory set, which is why we designed our experiment in this way. As for the second question, by construction, the achievable match probability to the trajectory set does not change when horizon (H) is changed, since the number of trajectories remains fixed. As we change H, the runtime complexity of the resampling operation within our algorithm will scale linearly. \n\n$\\textbf{Q7.}$ In line 240, I believe the complexity bound should be $M^{1/\\epsilon_0}$.\n\n$\\textbf{A7.}$\nThank you for pointing out the typo. It should be $M^{1/\\varepsilon_0}$."}, {"review_id": "NndfpTtrE6", "reviewer": "Reviewer_srob", "summary": "The authors present a very interesting and well mathematically analyzed problem formulation to find a optimal subset of expert trajectories that are free of transition conflicts in specific states. The conflict-free trajectories are optimal with respect to the deducable policy that lead to trajctories well aligned to the expert trajectories. They present two algorithms to find policies in environments with unknown or known model dynamics (first is an approximation).", "questions": "Is there a difference between (l143) d^phi and (l182) p_i for phi_i? Why is it defined two times?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- The mathematical description of the problem is sound and reasonable. \n- The proof in showing the np-completeness seems correct and complete.\n- The idea of optimizing the MWIS to remove the covariance shift makes sense.\n\nWeaknesses:\n- Motivation:\nWhy should the agent be closer aligned to the expert trajectory with the cost of removing training data? Some removed trajectories could hold valuable information. For example: Was the tweak with \"make the holes passable\" in the evaluation necessary to make the algorithm able to solve the task? \n- Evaluation:\nNot reproducable in my opinion. Please explain the experimental setup and evaluation more in detail. For example: what is 'imitation.algorithms.bc'? Is BC and TGL trained on the PPO trajectories?  \nAlso the metric is questionable: Does it make sense that the PPO expert is worse in imitating itself? \nFurthermore: Whats the runtime dependency to the problem size? Is it applicable to real-world problems? Maybe the authors could extend the gridsize and measure the runtime.\nAbstact says \"substantially outperforms standard imitation learning methods for long-trajectory planning.\" but the experiments only include horizons of 10 steps. \n\n\nAll in all I appreciate the mathematically sound problem formulation and method. I would raise my score to accept, if the authors could give a motivation that explains why the algorithm is useful in practice (maybe with examples) and a more elaborated evaluation that leads to more insights and also presents more metrics like the accuracy on the main tasks.  \n\n\nMinor weaknesses:\n- Paper checklist: The instruction block is present, albeit its written to be deleted.\n- Some typos.  \n- L 144 (formula) \"Phi in BigPhi\" -> BigPhi not introduced.\n- Its hard to understand why the problem can be formulated as MWIS and I needed to read it multiple times. Please add a few lines to L 188 that qualitatively describe why a valid policy is equivalent to a independent set in the graph. That would make it easier to follow.", "was_revised": true, "final_justification": "The authors introduce novel and interesting algorithms. I raise my score to Borderline accept, because they showed during rebuttal, that they address theoretical aspects. However, due to the weaknesses in experiments and writing/style issues, I will not raise to Accept, because these are usually not appropriate to Top-Tier conferences.", "rebuttal": "We thank the reviewer for recognizing our work's value and providing an excellent summary of our results. Now we address some of the concerns and questions raised by the reviewer.\n\n$\\textbf{Q1.}$\n“Motivation: Why should the agent be closer aligned to the expert trajectory with the cost of removing training data? Some removed trajectories could hold valuable information. For example: Was the tweak with \"make the holes passable\" in the evaluation necessary to make the algorithm able to solve the task?\"\n\n$\\textbf{A1.}$ Thank you for your question. If we understand correctly, you're asking why our MWIS method selects a subset of expert trajectories—in other words, why we remove some seemingly valuable training data. This is because our objective is to learn a policy that maximizes the probability of matching one of the expert trajectories. While we may have access to a large set of expert demonstrations, many of them may conflict with each other. Intuitively, a single fixed policy cannot simultaneously follow two conflicting trajectories, as discussed in our theoretical analysis. To address this, we employ a graph-based approach to identify a maximum-weight independent set (MWIS), which allows us to select a consistent subset of non-conflicting trajectories for optimizing.\n\nMaking the holes passable within our environment was not needed for TGL-UCB algorithm to function, as the TGL algorithm works on the original Frozenlake. The original FrozenLake environment ends an episode when the agent falls into a hole. Making holes passable was just a useful minor modification to allow the failed episodes to continue, which (i) enables longer trajectories for the PPO expert to learn from, (ii) allows for more diverse trajectories and more complex conflicts within our conflict graph structure, and (iii) makes it less trivial to reproduce trajectories. These more diverse and longer (usually full horizon) trajectories are harder to replicate.\n\n$\\textbf{Q2.}$\n“Evaluation: Not reproducable in my opinion. Please explain the experimental setup and evaluation more in detail. For example: what is 'imitation.algorithms.bc'? Is BC and TGL trained on the PPO trajectories?\"\n\n$\\textbf{A2.}$ Thank you for pointing out that the some implementation details were not explicit enough. In our revised appendix and paper, we will add more details such as exact Python packages, seeds, etc., to ensure that our experiment is fully reproducible. Concretely, 'imitation.algorithms.bc' is the behavior-cloning package from the open-source imitation library(https://arxiv.org/abs/2211.11972), which provides the supervised behavior-cloning baseline that we compared against. For the training pipeline, we first train a PPO expert on the modified FrozenLake environment for 50k steps. We roll out this PPO policy to collect a pool of expert demonstration trajectories. TGL and BC both receive this same pool of demonstration trajectories, and no additional information about the environment noise and the PPO expert. The difference is how the two methods (TGL and BC) learn from the demonstration trajectory set. During evaluation, every method is run for 10,000 fresh episodes under the same seed for the environment, and we report the empirical match probability. \n\n$\\textbf{Q3.}$\n“Also the metric is questionable: Does it make sense that the PPO expert is worse in imitating itself? Furthermore: What's the runtime dependency to the problem size? Is it applicable to real-world problems? Maybe the authors could extend the gridsize and measure the runtime. Abstact says \"substantially outperforms standard imitation learning methods for long-trajectory planning.\" but the experiments only include horizons of 10 steps.\"\n\n$\\textbf{A3.}$ \n\"Does it make sense that the PPO expert is worse in imitating itself?\": At first glance it may seem counter-intuitive that the PPO expert is not the best at reproducing its own demonstrations, but the gap arises because the objectives are different. PPO is trained to maximize its chances of reaching the goal in the noisy FrozenLake environment, not to reproduce any particular action sequence. When we are sampling trajectories from the PPO expert, we ensured that there are no duplicate trajectories, either through environment noise or to sample from the PPO expert stochastically, which can lead to less efficient detours before reaching the goal. BC and TGL are trained explicitly to replicate the demonstration pool behavior, so they are rewarded for copying the detour behavior. Because our evaluation counts only perfect matches (every state and action must be the same as a demonstration trajectory), PPO's performance is limited to the fraction of demonstrations that lie on its preferred set of paths.\n\n\nRegarding the runtime dependency of our algorithm, we kindly refer the reviewer to Theorems 2 and 4, where the runtime is analyzed in two components: (1) constructing the conflict graph and (2) solving the maximum-weight independent set (MWIS) problem. Both components exhibit polynomial-time complexity with respect to the planning horizon $H$ and the number of expert trajectories $M$. We believe this complexity is reasonable and applicable to certain real-world scenarios.\n\nIn response to your suggestion to increase the grid world size, we would like to clarify that the purpose of our experiments is not to demonstrate raw performance in high-dimensional state-action spaces, but rather to isolate and validate the core capability of TGL in solving the trajectory alignment problem using the novel MWIS-based framework. Expanding the grid size to $8 \\times 8$ or $10 \\times 10$ does increase the number of states, but only by a constant factor. This does not introduce qualitatively new types of trajectory conflicts, nor does it alter the fundamental structure of the conflict graph or the underlying learning dynamics. However, we agree that reporting the runtime could improve transparency, and we are open to including that in future versions for fair comparison.\n\nAs for the concern that the planning horizon $H$ is too short, this is primarily due to the limited size of the $4 \\times 4$ grid world, which naturally restricts the maximum number of steps. We would also like to clarify a possible misunderstanding regarding our statement in the abstract: when we say our method \"substantially outperforms standard imitation learning methods for long-trajectory planning,\" we are not referring to large values of $H$ per se. Instead, we mean that our method can faithfully imitate entire expert trajectories in a temporally consistent manner—something that standard imitation learning methods often fail to do. The phrase \"long-trajectory\" here emphasizes exact trajectory alignment over time, rather than the absolute value of $H$.\n\n\n$\\textbf{Q4.}$\n“All in all I appreciate the mathematically sound problem formulation and method. I would raise my score to accept, if the authors could give a motivation that explains why the algorithm is useful in practice (maybe with examples) and a more elaborated evaluation that leads to more insights and also presents more metrics like the accuracy on the main tasks.\"\n\n$\\textbf{A4.}$\nThank you for your appreciation of our theoretical contributions and methodology. Regarding the motivation behind our approach, we offer both analytical and empirical justifications. On the analytical side, we refer the reviewer to Appendix A.2, where we provide concrete examples illustrating how behavior cloning (BC) can fail to capture expert trajectories. The key insight is that traditional methods like BC often rely solely on cumulative rewards and overlook the sequential structure of trajectories. In contrast, our method directly aligns with complete trajectories, thereby capturing richer temporal information. This leads to improved performance on trajectory-level metrics such as matching probability.\n\nOn the empirical side, we draw motivation from real-world applications—such as self-driving and large language models (LLMs)—where decision sequences are long, branching, and structurally complex. For example, in self-driving, trajectory planning involves reasoning over distinct, non-overlapping future paths; in LLMs, decoding strategies like beam search produce diverse, tree-structured output sequences. These settings highlight the need to model full trajectories rather than rely solely on scalar feedback.\n\nAs for your suggestion regarding more detailed evaluations and metrics, we clarify that our work introduces a new setting—direct trajectory alignment—where the natural evaluation criterion is the probability that a learned policy exactly reproduces the expert trajectory set. Since the goal is replication rather than reward maximization, traditional RL metrics such as episode return or proximity to a ground-truth policy can be uninformative or even misleading. For example, a policy may achieve high returns while never matching any expert trajectories. In our framework, policy quality is judged solely by its alignment with the provided demonstrations, which is why our experiments and metrics are designed around this alignment objective.\n\n$\\textbf{Q5.}$\n“Minor weaknesses\"\n\n$\\textbf{A5.}$\nThank you for pointing out these minor issues, and we will correct them in a revised version.\n\n$\\textbf{Q6.}$\n“Is there a difference between (l143) $d^\\pi$ and (l182) $p_i$ for $\\tau_i$? Why is it defined two times?\"\n\n$\\textbf{A6.}$\nThank you for your question. In line 143, $d^\\pi(\\tau)$ denotes the probability of generating trajectory $\\tau$ under policy $\\pi$—that is, it incorporates both the policy's action distribution and the environment's transition dynamics. In contrast, in line 182, $p_i$ refers to the raw probability of trajectory $\\tau_i$ based solely on the product of transition probabilities. These two quantities differ in that $d^\\pi(\\tau)$ accounts for the stochasticity of the policy, whereas $p_i$ considers only the environment's dynamics."}]

Author rebuttal:

Meta-review: This paper considers the problem of learning policies to mimic expert trajectories. The core issue with existing behavior cloning like methods is that even if fit perfectly to expert data, the learned policy can result in trajectories which are not supported under the expert distribution. The root cause of this can be traced to the step-by-step nature of behavior-cloning. To avoid this, they aim to do imitation at trajectory level. While imitation of the trajectory distribution itself  has been studied exhaustively (e.g., trajectory distribution matching objectives in convex MDP literature [Table1, 1]), the core contribution of the work is in establishing hardness of the problem and then providing assumptions under which one can hope to solve this problem.

The core idea is to frame the direct trajectory alignment problem as a Maximum-Weight Independent Set (MWIS) problem on a graph, which is known to be NP-complete. In this "conflict graph," trajectories are nodes, and an edge connects two trajectories if they require conflicting actions at the same state. To make the problem feasible, authors assume bounded realizability and tree-structured MDPs. For the setting where environment dynamics are unknown, paper proposes UCB style algorithm to achieve sub-linear regret.

Overall, the reviewers appreciated the novelty of the work and found the reduction to existing NP-complete problem interesting. The provided experiments are extremely basic, so left more for asking. However, given the foundational nature and the theoretical focus of the work, I believe the merits of the paper still prevail.

Some additional recommendations

- Consider moving Appendix A.2 into the main paper, since it makes the problem statement crystal clear for a broader audience.
- One could argue that the problem is due to ill-specified/partially-observed state space, and behavior cloning with history conditioned state (as done in practice often) could address the mentioned challenge. Having some discussion about when and how the proposed method could be relevant in such settings as well would be beneficial.

[1]  Mutti, Mirco, et al. "Challenging common assumptions in convex reinforcement learning." *Advances in Neural Information Processing Systems* 35 (2022): 4489-4502
Decision: Accept (spotlight)