PaperlayerView exact revision on arXiv

Source-linked AI summary

Inverse Reinforcement Learning with Simultaneous Estimation of Rewards and Dynamics

Michael Herman, Tobias Gindele, Jörg Wagner, Felix Schmitt, Wolfram Burgard

arXiv:1604.03912v1cs.AIcs.LGcs.SYeess.SYstat.ML

TL;DR

Many IRL approaches rely on known dynamics or dynamics estimated from demonstrations; this paper uses a gradient-based approach to jointly estimate rewards and dynamics while accounting for demonstration bias. It reports more accurate model estimates than MDCE IRL or REIRL, especially with limited data, and fewer demonstrations needed for good estimates.

  • Problem

    Many IRL approaches require known system dynamics, while estimating rewards from demonstrations when dynamics are unknown remains a challenge.

    Source: §1 · p. 1

  • Method

    The gradient-based SERD approach jointly estimates reward and transition-model parameters while accounting for the policy that generated the demonstrations.

    Source: §1 · p. 2, §7 · p. 8

  • Results

    The approach estimates models more accurately than MDCE IRL or REIRL, especially with limited data, and needs fewer demonstrations for good estimates.

    Source: §6 · p. 7, §7 · p. 8

  • Takeaways & Limitations

    The authors report particular benefit when both the reward function and transition model are transferred to new environments.

    Source: §7 · p. 8

    The policy-gradient computation requires a converged Q-function and value function.

    Source: §4 · p. 4

Abstract

from arXiv · show

Inverse Reinforcement Learning (IRL) describes the problem of learning an unknown reward function of a Markov Decision Process (MDP) from observed behavior of an agent. Since the agent's behavior originates in its policy and MDP policies depend on both the stochastic system dynamics as well as the reward function, the solution of the inverse problem is significantly influenced by both. Current IRL approaches assume that if the transition model is unknown, additional samples from the system's dynamics are accessible, or the observed behavior provides enough samples of the system's dynamics to solve the inverse problem accurately. These assumptions are often not satisfied. To overcome this, we present a gradient-based IRL approach that simultaneously estimates the system's dynamics. By solving the combined optimization problem, our approach takes into account the bias of the demonstrations, which stems from the generating policy. The evaluation on a synthetic MDP and a transfer learning task shows improvements regarding the sample efficiency as well as the accuracy of the estimated reward functions and transition models.

1 Introduction · 2 Fundamentals

Because demonstrations reflect a policy shaped by both rewards and dynamics, they may not provide enough data to estimate either accurately. The paper introduces a gradient-based approach that estimates rewards and dynamics together from demonstrations, including for unobserved transitions.

1 Introduction

  • IRL recovers rewards from demonstrations when specifying a reward for desired behavior is difficult; its reward representation is intended to capture an expert’s objective and transfer to new environments.The introduction situates the problem among approaches for stochastic behavior and methods that do not require known dynamics.Source: §1 · p. 1
  • Model-based IRL needs accurate dynamics, but expert demonstrations sample desired states; model-free methods may need more data or a simulator and can generalize incorrectly.Without additional data, model-free approaches may ignore rewards or transitions for unobserved states and actions, or rely on heuristics that produce wrong generalizations.Source: §1 · pp. 1–2
  • SERD jointly estimates rewards and transition dynamics by optimizing demonstration likelihood under the generating policy, using policy information to infer even unobserved transitions.The approach treats the demonstrations’ state-action frequencies as information about the expert’s objective and dynamics, which can improve estimation accuracy and sample efficiency.Source: §1 · p. 2
  • The paper derives a general gradient-based SERD solution and an MDCE IRL algorithm with a convergent iterative policy-gradient computation, evaluated on synthetic MDPs and a transfer task.The evaluation compares the approach with model-based and model-free IRL and tests its generalization capabilities in transfer.Source: §1 · p. 2

2 Fundamentals

  • The fundamentals define an MDP by its states, actions, transition probabilities, discount factor, reward function, and start-state distribution.The section introduces this notation to formulate IRL with simultaneous estimation of rewards and dynamics.Source: §2.1 · p. 2, §2 · p. 2

2.1 Markov Decision Processes

  • An MDP’s optimal policy specifies action probabilities that maximize expected discounted future reward.The policy is denoted π*(s, a) = P(a|s).Source: §2.1 · p. 2

2.2 Inverse Reinforcement Learning

  • IRL estimates the reward explaining observed stochastic-policy trajectories, often expressing rewards as weights on state-action features.Under the Markov assumption, trajectory likelihood depends on the start distribution, actions, and transitions; feature weights can be learned by maximizing demonstration log-likelihood.Source: §2.2 · pp. 2–3
  • MDCE IRL extends maximum causal entropy IRL to an infinite horizon, using stationary soft value iteration whose fixed point yields a Boltzmann policy over Q-values.The soft value iteration is a contraction mapping.Source: §2.2 · pp. 2–3

3 Simultaneous Estimation of Rewards and Dynamics (SERD)

SERD addresses how incorrect transition models can distort reward estimates because an agent’s policy depends on both rewards and its believed dynamics. It jointly estimates rewards, the agent’s dynamics model, and the real dynamics model from demonstrations.

3 Simultaneous Estimation of Rewards and Dynamics (SERD)

  • Because policy depends on transition dynamics, incorrect dynamics estimates can falsify reward estimates, motivating simultaneous learning of rewards and dynamics.The agent’s belief about the dynamics may also differ from the real dynamics and thereby yield a wrong policy.Source: §3 · p. 3

Given

  • The problem gives demonstrations from an agent whose policy depends on its reward and believed dynamics, while the MDP’s reward and dynamics are unknown.The formulation distinguishes the agent’s believed transition model from the real transition model.Source: Given · p. 3, §3 · p. 3
  • SERD parameterizes reward features, agent dynamics, and real dynamics, then maximizes demonstration likelihood over these parameters.The parameters are estimated from demonstrations without prior information about rewards or dynamics.Source: Given · p. 3
  • The proposed gradient-based optimization accounts for reward and agent-dynamics parameters in the policy, while the real transition model depends on its own parameters.The paper derives the policy gradient for MDCE IRL and notes that extension to other IRL solutions and policies is possible.Source: Given · p. 4

4 Maximum Discounted Causal Entropy SERD (MDCE-SERD)

MDCE-SERD computes policy gradients through soft Q-gradients, using either a linear system or a recursive iteration. Its proofs establish contraction and differentiability properties that support convergence to unique fixed points.

4 Maximum Discounted Causal Entropy SERD (MDCE-SERD)

  • The policy gradient depends on state-action Q-gradients and expected gradients, so its computation requires converged Q- and value-functions.The expected gradient is taken with respect to a stochastic policy that itself depends on the Q-function.Source: §4 · p. 4
  • Soft Q-gradients can be computed by solving a linear system or by recursively iterating the gradient equation from arbitrary initial gradients to its fixed point.The recursive iteration propagates expected gradients across states, actions, and parameter dimensions.Source: §4 · p. 4
  • MDCE-SERD initializes dynamics from demonstration transitions, then alternates soft Q-solving, policy derivation, soft Q-gradient iteration, gradient computation, and parameter updates.The process repeats until sufficiently converged.Source: §4 · p. 5

4.1 Proofs

  • The soft Q-iteration is a contraction with one fixed point, and the converged soft Q-function is differentiable with respect to θ.Its Lipschitz constant is γ, where γ ∈ [0, 1).Source: §4.1 · p. 5
  • The soft Q operator is a contraction on the whole input space with Lipschitz constant L = γ for γ ∈ [0, 1), and therefore has only one fixed point.Source: §4.1 · pp. 5–6

5 Related Work

Prior IRL approaches differ in their treatment of stochastic dynamics and demonstration requirements. MDCE-SERD learns rewards and transition models from suboptimal demonstrations, but requires repeated forward-problem and soft Q-iteration solves.

5 Related Work

  • MaxEnt IRL matches trajectory feature expectations but incompletely handles stochastic transitions; MCE IRL (Ziebart et al., 2010) supports them, while both require known dynamics and repeated RL solves.Source: §5 · p. 6
  • REIRL matches feature expectations via KL divergence to an importance-sampled baseline policy; it allows stochastic behavior but may fail in stochastic domains and requires non-expert demonstrations from arbitrary policies.Source: §5 · p. 6
  • MDCE-SERD learns rewards and transition models from suboptimal demonstrations, unlike deterministic-policy-only SCIRL, but repeatedly solves the forward problem and soft Q-iteration.More accurate reward and transition models are especially useful for transfer to environments where new demonstrations cannot be queried, because they can produce better policies.Source: §5 · p. 6
  • SCIRL classifies actions using demonstration-estimated feature counts, fills gaps with additional samples or heuristics, and requires a deterministic expert policy.Source: §5 · p. 6

6 Evaluation

In stochastic grid-world navigation, MDCE-SERD jointly estimated rewards and dynamics from expert demonstrations, outperforming MDCE IRL and REIRL on reported learning metrics and transfer-task likelihood.

6 Evaluation

  • The grid-world task used five actions, stochastic forest and open-terrain motion, and a reward combining normalized image gray scale with a goal-identity feature.Open-terrain motion succeeded with probability 0.8 and veered left or right with probability 0.1 each; forest motion succeeded with probability 0.3, with other outcomes random.Source: §6 · pp. 6–7
  • Evaluation compared MDCE IRL, REIRL, and MDCE-SERD across demonstration-set sizes using trajectories sampled from a stochastic policy, allowing suboptimal expert behavior.The setup assumed experts knew the true dynamics; it trained nine action-specific or shared transition models, each with five possible outcomes. REIRL’s required policy samples were generated from an estimated dynamics model and an m-estimated expert policy.Source: §6 · p. 7
  • MDCE-SERD outperformed MDCE IRL and REIRL in demonstration likelihood and learned-policy KL, while simultaneous optimization produced more accurate transition estimates.REIRL performed worse than MDCE IRL on demonstration likelihood, which the paper suggests may reflect its limited treatment of transition stochasticity.Source: §6 · pp. 7–8, Figure 2 · p. 8
  • In transfer, MDCE-SERD improved average log likelihood of demonstrations drawn from the true model under the estimated model versus the other approaches.The learned reward and transition model were transferred to another satellite-image environment, where more accurate estimates could help generate meaningful policies in rarely or never observed states and actions.Source: §6 · p. 8, Figure 2 · p. 8

7 Conclusion

The paper presents gradient-based IRL that jointly estimates rewards and transition dynamics while accounting for demonstration bias. The combined approach estimates models more accurately than MDCE IRL or REIRL, especially with limited data.

7 Conclusion

  • The paper introduces a gradient-based IRL problem and solution that jointly estimate reward and transition-model parameters from demonstrations while accounting for demonstration bias.The authors state that, to their knowledge, this joint estimation problem had not been considered previously and could not be handled by current approaches.Source: §7 · p. 8
  • The combined approach estimates models more accurately than MDCE IRL or REIRL, especially with limited data.This is particularly beneficial when transferring both the reward function and transition model to new environments, where optimal policies may visit rarely observed states and actions.Source: §7 · p. 8
  • Future work could extend SERD to partially observable domains or continuous state and action spaces, while prior information can be incorporated by estimating only a subset of parameters.This also permits subproblems such as estimating dynamics when rewards are given; the estimated transition model may itself be useful.Source: §7 · p. 8
  • Further examining the distinction between true system dynamics and the expert’s estimate could improve estimates and potentially yield policies that exceed the expert’s performance.Source: §7 · p. 8

Abstract · 1 Partial Derivative of the Policy

The document is supplementary material that provides expanded derivations, proofs, and evaluation-task illustrations and plots. It also records the paper’s publication details and the authors’ Freiburg affiliation.

Abstract

1 Partial Derivative of the Policy

  • The paper appeared at AISTATS 2016 in Cádiz, Spain.Source: §1 · p. 10
  • The publication is listed as JMLR: W&CP volume 51, with copyright 2016 by the authors.Source: §1 · p. 10
  • The listed affiliation is the University of Freiburg, D-79110 Freiburg, Germany.Source: §1 · p. 10

2 Partial Derivative of the Soft Q-Function with Respect to the Individual Parameter Types

The section simplifies the soft Q-function’s partial derivative by treating three parameter types separately.

2 Partial Derivative of the Soft Q-Function with Respect to the Individual Parameter Types

  • The derivative is simplified with respect to feature weights, agent dynamics parameters, and true-environment dynamics parameters.Source: §2 · p. 10

3 Proof: Soft Q-iteration is a Contraction Mapping

The section proves that soft Q-iteration is a contraction mapping with a unique fixed point. The proof establishes monotonicity and uses it with a sup-norm bound to obtain a Lipschitz constant of γ.

3 Proof: Soft Q-iteration is a Contraction Mapping

  • The proof introduces a componentwise partial order, derives a softmax property, and uses these to establish monotonicity of the soft Q-iteration operator.The operator’s partial derivatives are nonnegative given γ ∈ [0, 1) and transition probabilities in [0, 1].Source: §3 · p. 11
  • The soft Q-iteration operator is a contraction mapping with only one fixed point and is Lipschitz continuous with constant γ ∈ [0, 1).The proof identifies the Lipschitz constant as γ.Source: §3 · pp. 11–12
  • The proof bounds Q-function differences under the supremum norm, applies monotonicity and the softmax shift property, and obtains a Lipschitz bound with constant γ.Since γ < 1, this bound establishes contraction over the whole input space and rules out multiple fixed points.Source: §3 · pp. 11–12

4 Proof: The Converged Soft Q-Function is Differentiable

The converged soft Q-function is differentiable with respect to θ. The proof uses the implicit function theorem and an invertible Jacobian, under differentiability and convergence conditions.

4 Proof: The Converged Soft Q-Function is Differentiable

  • The converged soft Q-function is differentiable with respect to θ.This is Theorem 4.1.Source: §4 · p. 12
  • The soft Q-operator is differentiable with respect to Q and θ when the transition model Pθ is differentiable with respect to θ, and its iterations converge for γ ∈ [0, 1).The proof applies the implicit function theorem at the converged fixed point.Source: §4 · p. 12
  • Because γ||M||∞ < 1, (γM − I) is invertible via a Neumann series, establishing that the derivative of the converged soft Q-function exists.The inverse is given by −∑_{i=0}^∞(γM)^i.Source: §4 · p. 12

5 Grid World Terrain Motion Task

The grid-world evaluation compares SERD with other approaches on training and transfer tasks, finding statistically significant differences in demonstration log likelihood at larger sample sizes. Figures also depict each task’s discretized terrain and associated reward, value, and expected state-frequency plots.

5 Grid World Terrain Motion Task

  • The training and transfer task figures show discretized maps with start and goal states, forest and open terrain, and plots of reward, value, and expected state frequency.Source: Figure 1 · p. 13, Figure 2 · p. 13
  • SERD’s demonstration log-likelihood performance differs significantly from other approaches for training sample sets larger than 3 and transfer demonstration sets larger than 12.Welch’s t-test found these differences significant at p < 0.05.Source: §5 · p. 12, Figure 3 · p. 14
Loading 1604.03912v1…