PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey of Inverse Reinforcement Learning: Challenges, Methods and Progress

Saurabh Arora, Prashant Doshi

arXiv:1806.06877v3cs.LGstat.ML

TL;DR

IRL seeks to infer an agent’s reward function from observed behavior, but accurate inference, generalization, evaluation, and scalability remain challenging. This survey categorizes existing methods, examines how they mitigate these challenges, and identifies progress alongside open questions.

  • Problem

    IRL must infer rewards from demonstrations that cover only part of the state space, while evaluation may require the unknown true reward function.

  • Method

    The survey categorizes IRL methods, compares foundational approaches and extensions, and examines how they address central challenges and real-world settings.

  • Results

    The survey reports improved understanding of IRL’s challenges, methods for mitigating them, and extensions toward real-world applications.

  • Takeaways & Limitations

    Selecting an IRL approach requires coherent comparison of methods, while future progress may combine complementary techniques for complex problems with multiple challenges.

  • Takeaways & Limitations

    Existing IRL methods generally do not scale reasonably beyond a few dozen states or more than ten possible actions.

Abstract

from arXiv · show

Inverse reinforcement learning (IRL) is the problem of inferring the reward function of an agent, given its policy or observed behavior. Analogous to RL, IRL is perceived both as a problem and as a class of methods. By categorically surveying the current literature in IRL, this article serves as a reference for researchers and practitioners of machine learning and beyond to understand the challenges of IRL and select the approaches best suited for the problem on hand. The survey formally introduces the IRL problem along with its central challenges such as the difficulty in performing accurate inference and its generalizability, its sensitivity to prior knowledge, and the disproportionate growth in solution complexity with problem size. The article elaborates how the current methods mitigate these challenges. We further discuss the extensions to traditional IRL methods for handling: inaccurate and incomplete perception, an incomplete model, multiple reward functions, and nonlinear reward functions. This survey concludes the discussion with some broad advances in the research area and currently open research questions.

1. Introduction

IRL infers an agent’s preferences and reward function from observed behavior, reducing manual task specification and supporting applications such as behavior modeling and apprenticeship learning. This survey organizes IRL’s challenges, methods, applications, milestones, and open questions for selecting suitable approaches.

  • Motivation: IRL models another agent’s preferences from observed behavior, avoiding manual specification of its reward function.
  • Motivation: Recorded demonstrations can broaden RL’s applicability when manually specifying a reward function is difficult or requires balancing conflicting attributes.Hand-designed rewards may require extensive tuning for safety, speed, distance, and other objectives.
  • Potential Applications: IRL applications include learning expert preferences for agent control and predicting another agent’s behavior from demonstrations.Examples include helicopter flight control, taxi route prediction, pedestrian interaction anticipation, and energy-efficient driving.
  • Importance of this Survey: The survey introduces IRL formally, studies its challenges and partial solutions, compares foundational and extended methods, and identifies milestones and open research avenues.
  • Organization: The article organizes its discussion around IRL as a research problem, covering technical background, core challenges, foundational methods, extensions, and future work.

2. Formal Definition of IRL

IRL reverses the forward RL setup: instead of learning a policy from rewards, it infers a reward function that explains an expert’s policy or demonstrated trajectories. The survey commonly models the expert–environment interaction as an MDP and represents rewards through weighted features.

  • Modeling Framework: IRL commonly models the observed agent’s interaction with its environment as an MDP, while acknowledging alternative frameworks such as POMDPs.
  • MDP Definition: An MDP comprises states, actions, transition dynamics, rewards, and a discount factor governing sequential decision-making.The transition function maps state-action pairs to distributions over next states, and the discount factor weights past rewards.
  • Policies and Values: A policy maps states to actions, and its value function measures expected long-term cumulative reward from following that policy.
  • Reward Representation and Demonstrations: IRL represents rewards as weighted combinations of feature functions and estimates expected feature counts from policies or demonstrated trajectories.The learned reward is chosen to best explain an expert policy when available or observed state-action trajectories otherwise.
  • RL and IRL: In forward RL, an agent learns an optimal policy from experiences containing states, actions, and rewards, whereas IRL learns a reward function from expert behavior.

3. Primary Challenges of IRL

IRL must infer rewards from limited behavior despite solution ambiguity, difficult evaluation, incomplete coverage, sensitivity to prior knowledge, and rapidly increasing computational and sample demands. The survey frames these challenges across reward learning and policy matching approaches.

  • Many reward functions, including degenerate ones, can explain a finite demonstration or policy, making IRL solutions inherently ambiguous.
  • Reward-function accuracy is difficult to assess because affine-equivalent rewards induce the same optimal policy, while small policy differences can have major task consequences.
  • Generalization requires extrapolating expert preferences to unobserved states and actions even though demonstrations cover only a fraction of the state space.
  • Using fewer demonstrations can increase approximation error and inaccurate inference despite the goal of generalizability.
  • IRL accuracy depends on prior feature and transition knowledge, whose correctness must be ensured or whose influence must be reduced.
  • As problem size grows, solving the induced MDP becomes difficult because state spaces can grow exponentially with state dimensions, while demonstrations require more trajectories for coverage.
  • Direct reward learning depends on a complete reward structure, whereas policy matching becomes nonconvex and especially sensitive to missing demonstration states.

4. Foundational Methods for IRL

Foundational IRL methods iteratively parameterize a reward, solve the expert’s MDP, compare learned and observed behavior, and update the parameters until divergence is reduced. The survey organizes methods by their mathematical learning framework.

  • The learner may receive demonstrations or the expert policy together with reward-function features, under the common assumption that the expert MDP is otherwise known.
  • The standard IRL template models behavior as an MDP with unknown reward, initializes a parameterized reward, solves the MDP, updates parameters, and repeats.
  • Reward hypotheses can use weighted feature combinations, distributions over reward maps, or other representations whose parameters are iteratively updated.
  • The survey categorizes methods into margin optimization, entropy optimization, Bayesian inference, classification, and regression.

4.1. Margin Optimization

Margin-based IRL selects reward functions that separate demonstrated behavior from alternatives or match expert and learner feature expectations. Its methods differ in the margin, representation, and optimization procedure used.

  • Maximum-margin methods seek rewards that explain demonstrated policies better than alternatives by a margin, addressing solution ambiguity through margin maximization.
  • Ng and Russell’s method uses a linear program to make the expert policy optimal while maximizing the action-value margin and preferring smaller rewards.
  • Learch iteratively modifies costs where learned behavior deviates from demonstrations, generalizes those changes across feature space, and updates the reward hypothesis.
  • Max-margin and projection iteratively update feature weights by comparing learner feature counts with empirical expert counts.
  • Feature-expectation matching can fail to recover an accurate reward because feature expectations depend on policy, although its sample complexity depends on feature count rather than state-space or policy complexity.
  • Other margin objectives minimize differences between stochastic action probabilities using empirically estimated state-visitation and action frequencies.

4.2. Entropy Optimization

Entropy-based IRL resolves reward ambiguity by selecting minimally committed distributions over demonstrated behaviors, typically through constrained maximum-likelihood optimization. Extensions address continuous states, nonlinear rewards, spatial structure, and alternative trajectory distributions.

  • Maximum-entropy methods address IRL’s ill-posedness by choosing behavior distributions that make minimal commitments beyond demonstration constraints.
  • The trajectory-distribution search space grows exponentially with trajectory length, motivating formulations over policies whose space grows as O(|A||S|).
  • MaxentIRL constrains trajectory probabilities and expected feature counts, then learns reward weights parameterizing the highest-likelihood exponential-family distribution.
  • Deep maxentIRL replaces linear rewards with neural networks and updates their weights by backpropagating the known likelihood gradient.
  • Pi-IRL extends maxentIRL to continuous states using path-integral reward features and iterative trajectory sampling.
  • Structured apprenticeship learning exploits neighboring-state action similarity through a Markov random field while matching empirical feature counts.
  • REIRL minimizes relative entropy between an empirically sampled baseline trajectory distribution and a feature-count-constrained distribution.

4.3. Bayesian Update

Bayesian IRL updates a prior over candidate reward functions using the likelihood of observed state-action trajectories. Methods vary by their likelihood model, including Boltzmann policies, active querying, Gaussian-process structure, and direct likelihood optimization.

  • Bayesian inference: Bayesian IRL treats trajectory state-action pairs as observations for updating a prior distribution over candidate reward functions.The posterior is updated repeatedly for each demonstrated trajectory.
  • Likelihood models: The surveyed methods categorize Bayesian IRL according to how they model the observation likelihood.A common likelihood choice is the Boltzmann distribution, with Q-values serving as the energy function and β controlling action randomness.
  • BIRL: BIRL supports different reward-function priors, including uniform, Gaussian, Laplacian, and Beta choices suited to different reward structures.Uniform priors are agnostic, while Gaussian or Laplacian priors can suit sparse rewards and Beta densities can suit planning problems with large reward dichotomies.
  • Active learning: Active Bayesian IRL queries experts in states where the posterior-induced action distribution has high entropy, using new samples to improve the posterior.The entropy measures how discriminating the learned expert policy is at each state.
  • Gaussian-process methods: GPIRL models nonlinear rewards as Gaussian processes and computes a posterior over rewards and kernel parameters from trajectories and features.It generalizes from rewards observed in trajectories and a few additional random states, then optimizes likely rewards using L-BFGS with restarts.
  • Direct likelihood optimization: Direct likelihood methods use softmax Boltzmann exploration to make the trajectory likelihood differentiable and optimize reward-feature weights by gradient ascent.The resulting optimization converges to locally optimal weights according to the surveyed description.

4.4. Classification and Regression

Classification and regression recast IRL as supervised-style learning while addressing its nonstandard structure. The surveyed methods use action-value scores, transition-model estimation, trajectory preferences, and regression trees to learn reward representations.

  • Overview: IRL is not straightforward supervised learning, but it can be formulated through classification and regression techniques.The surveyed methods adapt classical machine-learning frameworks to infer reward functions.
  • Classification: Multi-class IRL treats demonstrated state-action pairs as data-label pairs, with the demonstrated action serving as the label for each state.The action-value function provides a score for comparing possible actions.
  • Classification: The classifier learns the reward feature weights by minimizing errors between demonstrated actions and actions selected by maximizing the action-value function.The scoring function is linear and uses the same feature-weight vector as the reward function.
  • Classification: SCIRL trains a classifier with action-value scores and uses a structured large-margin algorithm to estimate the reward weights.Any linear-score multiclass classifier could be used, but SCIRL chooses structured prediction with a large-margin approach.
  • Unknown transition models: CSI extends SCIRL by estimating unknown transition probabilities through regression on simulated demonstrations before learning the reward function.SCIRL itself assumes that a transition model is available.
  • Suboptimal demonstrations: When demonstrations are suboptimal, ranked trajectory preferences can train a neural reward model to assign higher cumulative reward to preferred trajectories.A cross-entropy loss is used to enforce the preference ordering.
  • Regression trees: Regression-tree reward models partition large state-action spaces into regions represented by feature-function paths and conjunctions of indicator features.FIRL alternates reward optimization with feature construction by splitting coarse leaves or merging leaves with equal average rewards.

4.5. Summary of the Methods

The survey’s method summary organizes IRL techniques by their learned parameters, optimization metrics, and distinguishing contributions, enabling comparison across approaches.

  • Summary of the Methods: Table 2 summarizes IRL methods by identifying their learned parameters, optimization objective metric, and distinguishing contribution.The summary is intended to facilitate comparison and help align techniques with the problem at hand.

5. Mitigating the Challenges

The survey organizes methods that mitigate IRL’s central challenges, including noisy or incomplete demonstrations, ambiguity among reward hypotheses, accuracy guarantees, generalization, prior-knowledge sensitivity, and scalability. Across these challenges, methods use probabilistic modeling, slack variables, entropy objectives, formal bounds, transferable reward representations, and more efficient sampling or computation.

  • 5.1.1. Learning from Noisy Input: Probabilistic frameworks, slack variables, and robust trajectory models help IRL accommodate noisy, perturbed, suboptimal, or incomplete demonstrations.REIRL remains robust to perturbations; maximum entropy IRL outperformed maximum-margin planning on imperfect helicopter demonstrations, while T-REX learned from suboptimal input and surpassed demonstrator performance in simulated domains.
  • 5.1.2. Ambiguity and Degeneracy of Reward Hypotheses: Later methods address reward ambiguity by aligning state-action visitations with demonstrations, distributing probability through entropy, or favoring demonstrated-behavior rewards.These approaches reduce the issue of learned policies assigning zero probability to demonstrated actions, which affected several early biased or maximum-likelihood methods.
  • 5.1.3. Theoretical Bounds on Accuracy: Theoretical analyses provide performance or error guarantees for maximum-entropy, classification-based, feature-expectation, and state-visitation methods under stated assumptions.For example, maximum entropy minimizes worst-case expected loss, while some bounds require small classification and regression errors or a minimum sample complexity.
  • 5.2. Generalizability: Generalization methods learn rewards for unseen state-action pairs or mildly different environments, reducing reliance on demonstrations that cover every state.GP-IRL, FIRL, guided cost learning, and bisimulation-based BIRL each extend reward use beyond the original demonstrated setting in different ways.
  • 5.3. Lowering Sensitivity to Prior Knowledge: Maximum-entropy methods reduce feature-space sensitivity from linear dependence on k to O(log k) under bounded linear-reward features.The linear dependence applies to methods relying on feature expectations, including projection, MMP, MWAL, and MaxEntIRL; the passage specifically reports improved dependence for maximum-entropy methods.
  • 5.4. Reducing Computational and Sample Complexity: IRL scalability improves through entropy optimization, Gaussian-process methods, active querying, and model-free approaches that reduce computational or input-sample demands.Active BIRL targets informative states to reduce demonstrations, while model-free REIRL uses fewer input trajectories than alternatives; the survey also reports MaxEntIRL results on MDPs with thousands of states and actions.

6. Extensions of Basic IRL

The survey extends basic IRL to settings with imperfect perception, hidden variables, partial observability, and multiple reward functions. These extensions adapt inference to missing or noisy observations and heterogeneous expert behavior.

  • 6.1.1. Extended Definition: Imperfect-perception IRL allows demonstrated state-action pairs to be missing or different from the actual trajectory.The learner must infer unobserved or corrupted portions from available information.
  • 6.1.2. Methods: irl* generalizes maximum-entropy apprenticeship learning to feature expectations over only the observable state space under trajectory occlusion.It is applied to multi-robot patrolling, where the learner predicts possible patroller locations from partially visible trajectories.
  • 6.1.2. Methods: Latent maximum entropy and hidden-variable IRL use expectation-maximization or observation features to handle hidden actions and noisy state observations.The E-step estimates hidden variables, while the M-step performs maximum-entropy optimization; HIOC incorporates observation likelihoods into the reward model.
  • 6.1.2. Methods: POMDP-IRL models an imperfectly sensing expert with beliefs and a finite-state-machine policy, then searches reward functions until the observed behavior is explained.Exact POMDP solution is PSPACE-hard, motivating comparisons with slightly deviating policies rather than all possible policies.
  • 6.2. Multi-task IRL: Multi-task IRL learns multiple reward functions from mixed demonstrations, potentially clustering trajectories by the reward function that generated them.The number of experts may be unknown in dpm-birl, while related formulations iteratively cluster trajectories and update reward weights.

6.3. Incomplete Model

Incomplete transition dynamics and insufficient feature sets make standard IRL assumptions unrealistic. The surveyed methods estimate unknown dynamics, learn without transition probabilities, or construct richer nonlinear and relational reward representations.

  • 6.3.1. Extended Definition: Standard IRL assumes complete transition dynamics and reward features, but transition probabilities and feature sets are often difficult or unrealistic to specify.Hand-designed features increase engineering burden, and incomplete dynamics or features can fail to model the expert’s behavior.
  • 6.3.1. Extended Definition: Incomplete-dynamics IRL seeks a reward that explains demonstrations or an expert policy when only a subset of transition probabilities is known.The corresponding pipeline explicitly represents partially specified transition dynamics.
  • 6.3.2. Methods: mwal estimates unknown transition probabilities from frequently observed state-action pairs and routes remaining transitions to an absorbing state.mIRL*T extends this setting to limited observations, unknown transition probabilities, and multiple experts using shared transition features.
  • 6.3.2. Methods: pi-irl learns a reward without input transition probabilities, while gcl alternates trajectory generation, local linear-Gaussian dynamics fitting, and policy updates.These approaches address inaccuracies that can arise when transition models are approximated from few demonstrations.
  • 6.4. Nonlinear Reward Functions: mmpboost searches nonlinear combinations of primitive features to make demonstrations more likely than alternative trajectories.Other methods infer nonlinear rewards with image cost maps, Gaussian processes, or automatically constructed feature relationships.
  • 6.5. Summary: The surveyed methods are abstracted in a comparative table covering extensions intended to generalize IRL to pragmatic settings.The table summarizes key properties of methods reviewed in this section.

7. Concluding Remarks and Future Work

The survey reports substantial progress in understanding IRL challenges and developing methods for real-world extensions, while identifying major gaps in theory, scalability, evaluation, and changing preferences. It argues that future systems may need combinations of methods to address problems with multiple simultaneous challenges.

  • Concluding Remarks: IRL research has improved understanding of inherent challenges, developed mitigation methods, and extended these challenges toward real-world applications.The survey focuses on how methods address specific challenges and contribute to ongoing progress.
  • Open Questions: Few IRL methods provide provable sample- or time-complexity analyses, leaving limited theoretical guidance on complexity and accuracy.Among foundational methods, projection and mwal provide sample-complexity analyses using Hoeffding’s inequality, while most rely on empirical comparisons.
  • Open Questions: Existing methods do not scale reasonably beyond a few dozen states or more than ten possible actions, restricting demonstrations mainly to toy problems.The survey identifies meta-heuristic optimization as a direction for studying more efficient parameter estimation in IRL.
  • Open Questions: IRL lacks a standard testbed of problem domains for coherent evaluation across relevant dimensions.The survey contrasts this gap with repositories and libraries that support progress in supervised and reinforcement learning.
  • Future Directions: Future work should analyze direct reward learning versus policy matching and investigate their possible synergies when state spaces are large.The survey notes that direct reward learning can generalize better than policy matching when precise expert-policy identification is cumbersome.
  • Future Directions: Most methods assume fixed rewards, although agent preferences may change over time and require time-variant reward models.Representing dynamic rewards as multiple rewards is described as a crude approximation.
Loading 1806.06877v3…