Maximum Entropy Inverse Reinforcement Learning

Brian D. ZiebartAndrew L. MaasJ. Andrew BagnellAnind K. Dey

article2008AAAI3,521 citationsAAAI Classic Paper Award

Presents the Maximum Entropy Inverse Reinforcement Learning framework, which resolves demonstration ambiguity and label bias by defining a globally normalized probabilistic distribution over paths, providing an efficient convex optimization method for recovering reward functions and predicting sequential decisions from noisy human behavior.

Listen

Researchers have long struggled to imitate purposeful human behaviors such as driving routes because simple statistical models fail to capture long-term planning under uncertainty. Noisy GPS traces and imperfect demonstrations make it hard to recover the hidden rewards that guide decisions, and prior inverse reinforcement learning methods either produce ambiguous reward functions or assign probabilities in ways that favor shorter branches over higher-value paths.

This paper develops a maximum-entropy approach to inverse reinforcement learning that resolves those ambiguities by selecting the single distribution over paths that matches observed feature counts while remaining as uniform as possible otherwise. The resulting model yields a globally normalized probability over entire trajectories, extends naturally to stochastic dynamics, and supports hidden-goal inference.

The authors tested the method on more than 100,000 miles of taxi GPS data collected over twelve weeks in Pittsburgh. They represented the road network as a deterministic MDP with roughly 300,000 states and learned a linear reward function over road type, speed, lanes, and turn features. Performance was measured against maximum-margin planning and locally normalized action models on a held-out test set of 7,403 trips using path-overlap, 90-percent match rate, and log-likelihood.

The maximum-entropy model improved route overlap to 78.8 percent, raised the share of trips matched at 90 percent or better to 53 percent, and achieved higher likelihood than the alternatives. It also produced intuitive costs, such as penalizing local roads relative to interstates and assigning a fixed per-edge cost that discourages unnecessary turns. Because the distribution is globally normalized, the same weights support destination prediction from partial trajectories with useful accuracy once a prior over destinations is supplied.

These results indicate that the method can improve route recommendation systems, enable proactive driver alerts, and integrate directly with other probabilistic models for vehicle energy management or home automation. The approach remains computationally tractable through an efficient forward-backward procedure that computes state visitation frequencies without enumerating all paths.

Further gains are likely from adding time-of-day and weather features and from learning road-specific or region-specific costs. The current evaluation used a modest feature set and taxi drivers whose preferences may differ from those of private motorists; larger and more diverse datasets would strengthen confidence in broader deployment.

Carnegie Mellon University imitation learning optimal policies performance guarantees maximum entropy inverse reinforcement learning imitation learning maximum margin planning

Ziebart et al (2008).pdf

Paper: Algorithms for Inverse Reinforcement Learning, Andrew Y. Ng et al. (2000). This foundational paper introduces the iterative reward-fitting framework for inverse reinforcement learning that the source paper generalizes using maximum entropy.
Paper: Apprenticeship learning via inverse reinforcement learning, P. Abbeel et al. (2004). Understanding this earlier apprenticeship learning formulation is essential because the source work builds directly upon its feature expectation matching while replacing linear programming with a probabilistic model.
Paper: Q-learning, CHRISTOPHER J.C.H. WATKINS et al. (1992). Familiarity with Q-learning provides the necessary background in value-based Markov decision processes that underpin policy updates in inverse reinforcement learning.

Paper: Generative Adversarial Imitation Learning, Jonathan Ho et al. (2016). This work extends the source's maximum entropy principles by framing imitation learning through an adversarial objective that eliminates the need for expensive inner reinforcement learning loops.
Paper: Deep reinforcement learning from human preferences, Paul F. Christiano et al. (2017). Building on the principle of recovering reward functions from observed behavior, this study scales preference-based learning to deep reinforcement learning settings using human feedback.
Paper: A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning, Stephane Ross et al. (2010). This paper continues the exploration of imitation learning challenges by framing sequential decision-making errors as a reduction to no-regret online learning.

Cover for Maximum Entropy Inverse Reinforcement Learning

Abstract

Recent research has shown the benefit of framing problems of imitation learning as solutions to Markov Decision Problems. This approach reduces learning to the problem of recovering a utility function that makes the behavior induced by a near-optimal policy closely mimic demonstrated behavior. In this work, we develop a probabilistic approach based on the principle of maximum entropy. Our approach provides a well-defined, globally normalized distribution over decision sequences, while providing the same performance guarantees as existing methods.

We develop our technique in the context of modeling real-world navigation and driving behaviors where collected data is inherently noisy and imperfect. Our probabilistic approach enables modeling of route preferences as well as a powerful new approach to inferring destinations and routes based on partial trajectories.

Topics

imitation learning optimal policies performance guarantees utility functions routing scheme learning from demonstration multiple routes user preferences

Keywords

maximum entropy inverse reinforcement learning imitation learning maximum margin planning stochastic policy Markov decision problems reward function destination prediction feature expectation route preference

Introduction
Background
Maximum Entropy IRL
Deterministic Path Distributions
Non-Deterministic Path Distributions
Stochastic Policies
Learning from Demonstrated Behavior
Efficient State Frequency Calculations
Algorithm 1 Expected Edge Frequency Calculation
Backward pass
Local action probability computation
Forward pass
Summing frequencies
Driver Route Modeling
Route Choice as an MDP
Collecting and Processing GPS Data
Path Features
IRL Models
Comparative Evaluation
Applications
Related Work
Conclusions and Future Work
References

Knowls

Knowl 1 — Maximum Entropy Trajectory Distribution
model/method
In Inverse Reinforcement Learning (IRL), an agent operates in a Markov Decision Process (MDP) with states $s \in \mathcal{S}$ , actions $a \in \mathcal{A}$ , and transition probabilities $P_T(s' \mid s, a)$ . State reward is parameterized as a linear function of state features, $\text{reward}(s) = \theta^\top f_s$ , where $f_s \in \mathbb{R}^k$ and $\theta \in \mathbb{R}^k$ are reward weights. The reward of a trajectory $\zeta = (s_1, a_1, s_2, \dots, s_K)$ is $\text{reward}(\zeta) = \theta^\top f_\zeta = \sum_{s_j \in \zeta} \theta^\top f_{s_j}$ , where $f_\zeta = \sum_{s_j \in \zeta} f_{s_j}$ is the path feature count vector.

Applying the principle of maximum entropy subject to matching empirical feature expectations resolves ambiguity among reward functions and policies without introducing unobserved preferences. For deterministic MDPs, the maximum entropy distribution over paths $\zeta$ is globally normalized:

$P(\zeta \mid \theta) = \frac{1}{Z(\theta)} \exp\left(\theta^\top f_\zeta\right) = \frac{1}{Z(\theta)} \exp\left(\sum_{s_j \in \zeta} \theta^\top f_{s_j}\right)$

where $Z(\theta) = \sum_{\zeta} \exp(\theta^\top f_\zeta)$ is the partition function.

For non-deterministic MDPs with state transition dynamics $P_T(s_t \mid a_{t-1}, s_{t-1})$ , marginalizing over environmental action outcomes yields the trajectory distribution:

$P(\zeta \mid \theta, T) = \frac{1}{Z(\theta, T)} \exp\left(\theta^\top f_\zeta\right) \prod_{s_t, a_{t-1}, s_{t-1} \in \zeta} P_T(s_t \mid a_{t-1}, s_{t-1})$

This distribution induces a stochastic policy at each state where action choice probabilities are proportional to the expected exponentiated reward of all paths initiated by that action:

$P(a \mid s, \theta, T) \propto \sum_{\zeta: a_0 = a, s_0 = s} P(\zeta \mid \theta, T)$
Knowl 2 — Maximum Likelihood Objective and Gradient for Maximum Entropy IRL
equation
Given $M$ demonstrated trajectories $\{\tilde{\zeta}_m\}_{m=1}^M$ with empirical feature expectations $\tilde{f} = \frac{1}{M} \sum_{m=1}^M f_{\tilde{\zeta}_m}$ , finding the maximum entropy reward weights $\theta$ is equivalent to maximizing the log-likelihood $L(\theta)$ under the maximum entropy exponential family trajectory distribution:

$\theta^* = \arg\max_\theta L(\theta) = \arg\max_\theta \sum_{m=1}^M \log P(\tilde{\zeta}_m \mid \theta, T)$

The log-likelihood objective function $L(\theta)$ is concave with respect to the linear reward parameters $\theta$ . Its gradient is the difference between the empirical feature counts and the model's expected feature counts:

$\nabla_\theta L(\theta) = \tilde{f} - \sum_\zeta P(\zeta \mid \theta, T) f_\zeta = \tilde{f} - \sum_{s_i} D_{s_i} f_{s_i}$

where $D_{s_i}$ is the expected state visitation frequency of state $s_i$ under parameter $\theta$ , and $f_{s_i}$ is the feature vector of state $s_i$ . At the global optimum where $\nabla L(\theta) = 0$ , the expected feature counts matched by the learner equal the empirical demonstrated feature expectations: $\sum_{s_i} D_{s_i} f_{s_i} = \tilde{f}$ .
Knowl 3 — Expected State Visitation Frequency Calculation
algorithm
Directly computing expected state visitation frequencies $D_{s_i}$ via path enumeration is intractable due to exponential path growth. The dynamic programming algorithm computes exact state frequencies in polynomial time using forward-backward passes analogous to soft value iteration and the forward-backward algorithm for Conditional Random Fields.
Input: State transitions $P(s_k \mid s_i, a_{i,j})$ , reward parameters $\theta$ , state features $f_{s_i}$ , start state distribution $P(s_{\text{initial}})$ , time horizon $T$
Output: Expected state visitation frequencies $D_{s_i}$ for all states $s_i$
Backward pass (partition functions and local action probabilities):
Initialize $Z_{s_i, 0} = 1$ for all terminal states / states $s_i$
for iteration $t = 1 \dots T$ :
    for each state $s_i$ and action $a_{i,j}$ :
         $Z_{a_{i,j}} = \sum_k P(s_k \mid s_i, a_{i,j}) \exp(\theta^\top f_{s_i}) Z_{s_k, t-1}$
    for each state $s_i$ :
         $Z_{s_i, t} = \sum_{a_{i,j}} Z_{a_{i,j}}$
for each state $s_i$ and action $a_{i,j}$ :
     $P(a_{i,j} \mid s_i) = \frac{Z_{a_{i,j}}}{Z_{s_i}}$
Forward pass (state occupancy propagation):
Initialize $D_{s_i, 1} = P(s_i = s_{\text{initial}})$ for all states $s_i$
for $t = 1 \dots T-1$ :
    Initialize $D_{s_i, t+1} = 0$ for all states $s_i$
    for each state $s_i$ :
         $D_{s_i, t+1} = \sum_{s_k} \sum_{a_{k,j}} D_{s_k, t} P(a_{k,j} \mid s_k) P(s_i \mid a_{k,j}, s_k)$
Summing frequencies:
for each state $s_i$ :
     $D_{s_i} = \sum_{t=1}^T D_{s_i, t}$
return $D$
The algorithm approximates infinite-horizon state frequencies using a sufficiently large finite time horizon $T$ .
Knowl 4 — Resolution of Label Bias via Global Trajectory Normalization
theoretical result
Probabilistic IRL methods that normalize action probabilities locally at each state using optimal action-value functions, such as $P(a \mid s, \theta) \propto \exp(Q^*(s, a))$ , suffer from the label bias problem. In locally normalized models, paths only compete for probability mass against alternative actions available at the immediate state node, rather than globally against alternative paths that branched at earlier stages.

As a consequence of label bias in locally normalized formulations:
1. Paths traversing regions of the state space with higher branching factors receive lower probability mass than paths traversing regions with lower branching factors, even when both paths yield identical cumulative rewards.
2. The highest-reward policy in an MDP is not guaranteed to be the most probable policy under the model.
3. Optimizing the likelihood under locally normalized formulations results in non-convex optimization problems with multiple local optima.
Global normalization in Maximum Entropy IRL ( $P(\zeta \mid \theta) \propto \exp(\theta^\top f_\zeta)$ ) eliminates label bias: trajectories with equivalent cumulative rewards are assigned equal probabilities, trajectories with higher rewards are exponentially more probable, and the optimization objective is globally concave.
Knowl 5 — Bayesian Destination and Future Route Inference from Partial Trajectories
model/method
When an agent's destination is unknown, the Maximum Entropy IRL trajectory distribution enables closed-form Bayesian inference over destinations $d \in \mathcal{D}$ conditioned on an observed partial trajectory $\tilde{\zeta}_{A \to B}$ from starting location $A$ to current location $B$ :

$P(d \mid \tilde{\zeta}_{A \to B}) = \frac{P(\tilde{\zeta}_{A \to B} \mid d) P(d)}{\sum_{d' \in \mathcal{D}} P(\tilde{\zeta}_{A \to B} \mid d') P(d')}$

Using the globally normalized path distribution parameterized by reward weights $\theta$ , the likelihood of the observed partial path given destination $d$ reduces to the ratio of the unnormalized partition functions of paths continuing from $B$ to $d$ versus paths starting at $A$ to $d$ :

$P(\tilde{\zeta}_{A \to B} \mid d) \propto \frac{\sum_{\zeta_{B \to d}} \exp\left(\theta^\top f_\zeta\right)}{\sum_{\zeta_{A \to d}} \exp\left(\theta^\top f_\zeta\right)}$

Both numerator and denominator partition sums are computed directly using the backward pass of the dynamic programming inference algorithm. This enables simultaneous posterior inference of intended destinations and the probability distribution over remaining path extensions without explicitly querying the agent.
Knowl 6 — Large-Scale GPS Taxi Route Experimental Benchmark
experimental setup
The Maximum Entropy IRL approach was evaluated on a large-scale driver route modeling task in the road network of Pittsburgh, Pennsylvania:
- Planning Space: Modeled as a deterministic MDP comprising over 300,000 states (road segments) and 900,000 actions (intersection transitions), with destinations modeled as zero-cost absorbing states.
- Dataset: Over 100,000 miles of GPS trace data collected from 25 Yellow Cab taxi drivers over 12 weeks (exceeding 3,000 hours of driving). Traces were fitted to the road network using a particle filter and segmented into approximately 13,000 trips. After discarding trips that were too short (fewer than 10 segments), cyclic, or noisy (roughly 30%), 20% were used for training and 80% (7,403 trips) were reserved for testing.
- Feature Space: 22 road features per segment categorized across four dimensions: road classification (interstate to local road), speed categories, lane count categories (one to many lanes), and intersection turn transitions (straight, left, right, hard left, hard right).
- Compared Models: Maximum Entropy IRL (MaxEnt paths), Maximum Margin Planning (MMP), Action-based distribution ( $P(a \mid s) \propto \exp(Q^*(s, a))$ evaluated on most likely path and cost-weighted path), and a speed-limit Time-based model.

Knowl 7 — Empirical Route Prediction and Log-Likelihood Performance

data/table

Evaluation of route imitation and density estimation across 7,403 withheld test trajectories:

Model	Matching (%)	90% Match (%)	Log Prob
Time-based	72.38%	43.12%	N/A
Max Margin	75.29%	46.56%	N/A
Action	77.30%	50.37%	-7.91
Action (costs)	77.74%	50.75%	N/A
MaxEnt paths	78.79%	52.98%	-6.85

Matching: The average percentage of route distance shared between the model's most likely predicted path and the demonstrated path.
90% Match: The percentage of test trajectories where the predicted route shares at least 90% of total distance with the ground-truth route.
Log Prob: The average log probability assigned to the test trajectories under the model (MMP and cost-only models do not define valid probability densities over trajectories).

MaxEnt paths significantly outperformed all baseline models across all three metrics ( $p < 0.01$ ).

Knowl 8 — Learned Driver Utility Costs for Road Types and Intersection Turns
empirical result
Applying Maximum Entropy IRL to taxi navigation data recovers an interpretable linear utility function (expressed in equivalent seconds of driving cost):
- Intersection Turn Costs: Going straight through an intersection costs 1.4 seconds; turning right costs 4.9 seconds; turning left costs 5.2 seconds; making a hard right costs 8.8 seconds; and making a hard left costs 12.2 seconds.
- Road Classification Costs: Relative to interstate highways (normalized to 65 mph and 0 additional cost), driving costs per mile increase monotonically as road type downgrades, reaching nearly 200 seconds of additional cost per mile on local residential roads.
- Per-Edge Fixed Cost: A fixed penalty of 1.4 seconds per road segment is learned, which penalizes fragmented routes made up of numerous short road segments.
Knowl 9 — Posterior Destination Prediction Accuracy from Partial Path Observations
empirical result
In a destination inference evaluation across 5 candidate terminal locations around Pittsburgh:
- When 0% of the trajectory is observed, prediction accuracy matches the prior destination distribution (~40-42%).
- As the fraction of the trajectory observed increases from 0.0 to 0.45, the posterior prediction accuracy increases monotonically from ~42% to over 85%.
Because MaxEnt IRL assigns exponentially lower probability to routes that deviate from optimal travel toward a given goal, partial trajectories moving away from candidate destinations rapidly extinguish posterior probability mass on those destinations, concentrating mass on the true destination.

Coverage note — Omitted only generic optimization details (exponentiated gradient descent and Hoeffding error bounds on feature counts) and brief high-level mentions of contextual feature extensions (weather, rush hour) noted as future work.

References

1.Abbeel, P., and Ng, A. Y. 2004. Apprenticeship learning via inverse reinforcement learning. In Proc. ICML, 1–8.
2.Dud1́k, M., and Schapire, R. E. 2006. Maximum entropy distribution estimation with generalized regularization. In Proc. COLT, 123–138.
3.Jaynes, E. T. 1957. Information theory and statistical mechanics. Physical Review 106:620–630.
4.Krumm, J., and Horvitz, E. 2006. Predestination: Inferring destinations from partial trajectories. In Proc. Ubicomp, 243–260.
5.Lafferty, J.; McCallum, A.; and Pereira, F. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proc. ICML, 282–289.
6.Letchner, J.; Krumm, J.; and Horvitz, E. 2006. Trip router with individualized preferences (trip): Incorporating personalization into route planning. In Proc. IAAI, 1795–1800.
7.Liao, L.; Patterson, D. J.; Fox, D.; and Kautz, H. 2007. Learning and inferring transportation routines. Artificial Intelligence 171(5-6):311–331.
8.Neu, G., and Szepesvri, C. 2007. Apprenticeship learning using inverse reinforcement learning and gradient methods. In Proc. UAI, 295–302.
9.Ng, A. Y., and Russell, S. 2000. Algorithms for inverse reinforcement learning. In Proc. ICML, 663–670.
10.Ramachandran, D., and Amir, E. 2007. Bayesian inverse reinforcement learning. In Proc. IJCAI, 2586–2591.
11.Ratliff, N.; Bagnell, J. A.; and Zinkevich, M. 2006. Maximum margin planning. In Proc. ICML, 729–736.

Citation

MLA

Ziebart, B. D., et al. “Maximum Entropy Inverse Reinforcement Learning”. Carnegie Mellon University, 2018, https://doi.org/10.1184/r1/6555512.

APA

Ziebart, B. D., Maas, A., Bagnell, J. A., & Dey, A. K. (2018). Maximum Entropy Inverse Reinforcement Learning. Carnegie Mellon University. https://doi.org/10.1184/r1/6555512

Chicago

Ziebart, B. D., A. Maas, J. A. Bagnell, and A. K. Dey. 2018. “Maximum Entropy Inverse Reinforcement Learning”. Carnegie Mellon University, ahead of print. https://doi.org/10.1184/r1/6555512.

Harvard

Ziebart, B.D. et al. (2018) “Maximum Entropy Inverse Reinforcement Learning”, Carnegie Mellon University [Preprint]. Available at: https://doi.org/10.1184/r1/6555512.

Vancouver

1. Ziebart BD, Maas A, Bagnell JA, Dey AK (2018) Maximum Entropy Inverse Reinforcement Learning. Carnegie Mellon University. https://doi.org/10.1184/r1/6555512

BibTeX

@article{https://doi.org/10.1184/r1/6555512,
  doi = {10.1184/R1/6555512},
  url = {https://kilthub.cmu.edu/articles/journal_contribution/Maximum_Entropy_Inverse_Reinforcement_Learning/6555512},
  author = {Ziebart, Brian D. and Maas, Andrew and Bagnell, J. Andrew and Dey, Anind K.},
  keywords = {Intelligent robotics},
  title = {Maximum Entropy Inverse Reinforcement Learning},
  publisher = {Carnegie Mellon University},
  year = {2008},
  copyright = {In Copyright}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Maximum Entropy Inverse Reinforcement Learning

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Maximum Entropy Trajectory Distribution

Knowl 2 — Maximum Likelihood Objective and Gradient for Maximum Entropy IRL

Knowl 3 — Expected State Visitation Frequency Calculation

Knowl 4 — Resolution of Label Bias via Global Trajectory Normalization

Knowl 5 — Bayesian Destination and Future Route Inference from Partial Trajectories

Knowl 6 — Large-Scale GPS Taxi Route Experimental Benchmark

Knowl 7 — Empirical Route Prediction and Log-Likelihood Performance

Knowl 8 — Learned Driver Utility Costs for Road Types and Intersection Turns

Knowl 9 — Posterior Destination Prediction Accuracy from Partial Path Observations

References

Citation

BibTeX

Access the Paper