One-sentence Summary

Carnegie Mellon University proposes a maximum entropy inverse reinforcement learning approach that yields a well-defined, globally normalized distribution over decision sequences while matching the performance guarantees of existing methods, enabling probabilistic modeling of noisy navigation and driving behaviors, route preference inference, and destination prediction from partial trajectories.

Key Contributions

• A maximum entropy probabilistic approach to inverse reinforcement and imitation learning defines a globally normalized distribution over decision sequences and preserves the performance guarantees of earlier feature-matching methods.

• The method resolves ambiguity in prior models by formulating behavior prediction as convex optimization over a globally normalized policy, avoiding label bias so that paths with equivalent expected reward receive equal probability and higher-reward paths receive higher probability.

• The approach is evaluated on real-world navigation and driving behavior, including large-scale demonstrated driving data and route-preference modeling with a small feature space, supporting inference of routes and destinations from partial trajectories.

Introduction

In imitation learning, the goal is to infer an agent’s sequential decision-making policy from observed behavior, a task that is especially useful for applications such as modeling driver route preferences from GPS trajectories. Prior inverse reinforcement learning methods recover an unknown reward function by making demonstrated behavior appear optimal, but they often face ambiguity because many reward functions or policies can explain the same data, and demonstrated behavior may also be noisy or only partially optimal. Structured margin methods can handle some forms of this problem but may struggle when no single reward makes the observed behavior clearly better than alternatives, while locally normalized probabilistic models can introduce label bias and require more difficult optimization. The authors address these issues by leveraging a maximum entropy probabilistic approach that learns a globally normalized distribution over trajectories, resolves ambiguity in a principled way, provides efficient learning and inference for MDPs, and can be combined with hidden variables to infer future routes or destinations.

Dataset

• Dataset source: The authors collect GPS trace data from 25 Yellow Cab taxi drivers over 12 weeks, across all times of day, around Pittsburgh. The raw traces cover more than 100,000 miles of travel during more than 3,000 hours of driving.

• Trip construction: The sparse GPS traces are fitted to the road network using a particle filter. Fitted traces are then segmented into approximately 13,000 distinct trips using a time-based threshold to identify stopping locations.

• Filtering rules: About 30% of the trips are discarded because they are too short, too cyclic, or too noisy. Trips with fewer than 10 road segments are treated as too short.

• Splitting: After filtering, 20% of the remaining trips are used for training, and 80% are used for testing, yielding a testing set of 7,403 examples.

• Feature schema: Each trip is represented using road segment characteristics across four dimensions: road type, speed, lanes, and transitions. Road types range from interstate to local, speeds range from high to low, and lanes range from one to many. Transitions are categorized as straight, left, right, hard left, and hard right.

• Metadata construction: Each path is described by the number of miles of road in each segment category and the count of each transition type. Each road segment contributes to 22 different feature counts.

Method

The authors build the method around maximum entropy inverse reinforcement learning. They leverage the principle of maximum entropy to resolve ambiguity when several reward functions or policies can reproduce the demonstrated behavior. Rather than selecting an arbitrary policy or an arbitrary reward function, they define a probability distribution over complete behavioral paths and choose the distribution that matches the empirical feature expectations of the demonstrations while introducing no additional preferences beyond what the observed features require.

The core model is a path distribution parameterized by reward weights $\theta$θ. In a deterministic Markov decision process, a demonstrated trajectory can be viewed as a variable-length sequence of states, and the resulting path probability is proportional to an exponential reward score:

Here, $\mathbf{f}_{\zeta_i}$fζi​​ is the summed feature vector of the path, and $Z(\theta)$Z(θ) is the partition function. Under this formulation, paths with the same total reward receive equal probability, while paths with higher reward are exponentially more likely. The partition function always converges for finite horizon problems and for infinite horizon problems with discounted rewards. For infinite horizon problems with absorbing zero reward states, the partition function may fail to converge, but if demonstrated trajectories are absorbed in a finite number of steps, the maximum entropy reward weights remain well defined.

For nondeterministic Markov decision processes, the transition outcome is random. The authors condition the path distribution on the transition distribution $T$T and require compatibility between the realized path and the sampled transition outcomes. The exact expression is

This sum over possible outcome assignments is generally intractable. The authors therefore assume that transition randomness has a limited effect on overall behavior and that the partition function is approximately constant across outcome samples. This yields a tractable approximation:

When this approximate partition function converges, the path distribution induces a stochastic policy. The probability of an action is obtained by aggregating over all complete paths that begin with that action:

The learning process maximizes the likelihood of the demonstrated paths under the maximum entropy path distribution. The optimal reward weights are given by

For deterministic MDPs, this objective is convex, so gradient based optimization can be used. The gradient measures the difference between empirical feature expectations from the demonstrations and model expected feature counts:

Here, $D_{s_i}$Dsi​​ is the expected state visitation frequency of state $s_i$si​ under the current path distribution. At the optimum, the feature expectations match, meaning the learned model reproduces the observed behavior without needing to recover the exact reward weights originally used by the demonstrated agent.

A central computational component is the calculation of expected state frequencies. Direct enumeration of all possible paths is infeasible because the number of paths grows exponentially with the time horizon. Instead, the method computes approximate state occupancy frequencies using a procedure similar to forward backward computation in conditional random fields or value iteration in reinforcement learning. The algorithm replaces an infinite horizon with a sufficiently large fixed horizon. It begins by backing up probability mass from possible terminal states, computes branch values associated with the partition function at each action and state, converts those branch values into local action probabilities, and then propagates those probabilities forward to accumulate state visitation frequencies over time. These frequencies are used to evaluate the model feature expectations and form the gradient.

In route planning settings, the authors instantiate this pipeline as a maximum entropy IRL model over a road network. Road segments are treated as states and intersection transitions as actions. The destination is represented as an absorbing state where no further cost is accumulated. Drivers are assumed to optimize a latent cost function that represents a balance among factors such as travel time, safety, fuel usage, and other travel costs. Because the reward weights are assumed to be independent of the goal, a single utility model can be learned across trips that differ only by destination.

For efficiency, the path space can be restricted to a fixed class of reasonably good paths instead of considering all paths below a maximum length. This keeps the optimization tractable, reduces unnecessary cycle exploration, and preserves the benefits of the maximum entropy formulation.

The advantage of reasoning over whole paths rather than local actions is highlighted by comparing the maximum entropy path model with an action based distribution model. The action based model assigns probability according to the future optimal value of taking an action:

This model normalizes locally at each action, whereas the maximum entropy model normalizes over complete paths. The resulting difference is illustrated in the following example.

In the depicted graph, if the possible paths from one point to another have the same total reward, the maximum entropy model assigns them equal probability. The action based model can assign different probabilities because probability mass is split locally at each state. Paths with different branching structure can therefore receive different probability even when their total reward is identical. This behavior reflects a local normalization bias and motivates the path level maximum entropy distribution used in the method.

Experiment

The experiments evaluate trained route models on held-out driver trajectories using path-overlap, path-match, and likelihood criteria, comparing the maximum entropy action model against cost-based and speed-based fastest-route baselines. The maximum entropy model consistently produces the best qualitative match to observed paths, and its learned costs capture useful preferences such as penalizing routes made of many short roads. Additional evaluations show that the model can infer likely destinations from partially observed routes through Bayesian reasoning, supporting personalized route-aware applications and suggesting that contextual information such as time of day could further improve prediction.

The maximum entropy model produces the closest matches to withheld driver paths and the strongest reported route likelihood among the evaluated methods. It improves on expected travel time, maximum margin, and action-based predictions across route overlap and high-coverage matching metrics. Maximum entropy path prediction yields the strongest agreement with demonstrated routes. Travel time based routing trails the learning based models on route matching. Learning edge costs from the action based model improves matching over its most likely path. The maximum entropy model also assigns a more favorable average log probability than the action based model.

Experiments compare learning-based path prediction methods with travel-time routing on matching demonstrated driver routes. The maximum entropy model consistently achieves the closest agreement with withheld routes and provides the most favorable route likelihood, outperforming action-based and travel-time approaches across overlap and coverage-based evaluations. These results support maximum entropy as the strongest method for route prediction, while learning edge costs from the action-based model improves matching over using its most likely path.