Source-linked AI summary
Continuous Inverse Optimal Control with Locally Optimal Examples
Sergey Levine, Vladlen Koltun
TL;DR
IOC must recover rewards from expert demonstrations in continuous, high-dimensional settings where computing a full policy is impractical. The paper uses a local likelihood approximation that avoids global planning and accepts locally optimal examples, with evaluations showing convergence to the correct policy in the tested setting.
Problem
IOC must recover unknown rewards from demonstrations, but standard likelihood computation becomes intractable in high-dimensional spaces and commonly assumes globally optimal examples.
Method
The method uses a local approximation of trajectory likelihood around expert examples, with linear and nonlinear parameterized reward variants.
Results
Both algorithm variants converge to the correct policy on locally optimal examples, whereas MaxEnt does not converge under its global-optimality assumption.
Takeaways & Limitations
Local optimality can be easier to demonstrate than global optimality, particularly in high-dimensional domains, enabling learning from examples unsuitable for prior methods.
Takeaways & Limitations
The method requires differentiable reward features and currently applies only to deterministic, fixed-horizon control problems.
Abstract
from arXiv · showhide
Inverse optimal control, also known as inverse reinforcement learning, is the problem of recovering an unknown reward function in a Markov decision process from expert demonstrations of the optimal policy. We introduce a probabilistic inverse optimal control algorithm that scales gracefully with task dimensionality, and is suitable for large, continuous domains where even computing a full policy is impractical. By using a local approximation of the reward function, our method can also drop the assumption that the demonstrations are globally optimal, requiring only local optimality. This allows it to learn from examples that are unsuitable for prior methods.
1. Introduction
The paper presents an efficient IOC algorithm for large, continuous domains by modeling the reward locally around expert demonstrations. This local approach removes the need for globally optimal examples while retaining probabilistic learning.
- IOC recovers an unknown reward function in an MDP from expert demonstrations of the corresponding policy.
- The method handles deterministic MDPs with large, continuous state and action spaces by considering the learned reward near expert demonstrations.
- Local reward modeling avoids integrating global information along alternative paths, so demonstrations need only exhibit local rather than global optimality.
- The algorithm maximizes an approximate likelihood in which expert trajectories lie near prominent likelihood peaks.
- The paper provides linear and nonlinear reward variants, trading lower sample requirements with a known linear basis against greater expressiveness.
2. Related Work
Prior IOC methods commonly require repeated forward-control solutions, restrictive value-function bases, or globally optimal demonstrations. The proposed local reward approach avoids repeated forward solves while retaining informative reward features and accepting locally optimal examples.
- Many prior IOC methods repeatedly solve the full forward control problem, making reward learning substantially more expensive than forward control.
- The proposed method considers reward only around expert trajectories, removing repeated forward solves without discarding informative reward features.
- Value-function approaches avoid repeated forward solving but require domain-specific value-function bases that are difficult to construct and not portable.
- LQR-based methods are efficient for linear dynamics and quadratic rewards but are difficult to generalize beyond tasks satisfying those assumptions.
- Unlike most previous methods, this approach can learn rewards from demonstrations that are only locally optimal.
3. Background
The paper formulates IOC for deterministic, fixed-horizon continuous control and explains why standard maximum-entropy inference becomes intractable in high dimensions. Its approximation avoids the partition function and requires only local optimality.
- The setting consists of deterministic, fixed-horizon control with continuous states and actions evolving in discrete time under a dynamics function.
- IOC seeks a reward function whose optimal actions match expert demonstrations, while reward features may represent the unknown reward.
- Maximum-entropy IRL models action probabilities as proportional to exponentiated trajectory rewards and accommodates stochastic expert behavior.
- Computing the partition function requires finding the complete policy, which becomes intractable because the computation scales exponentially with state-space dimensionality.
- The proposed approximation breaks exponential dimensionality dependence and replaces global optimality with approximate local optimality.
4. IOC with Locally Optimal Examples
The method uses a Laplace approximation to locally model trajectory likelihood near expert actions, replacing global planning with local optimization. Its objective favors demonstrations near reward peaks that are steep in relevant directions.
- The Laplace approximation models the trajectory distribution locally as Gaussian, allowing likelihood evaluation without computing the partition function.
- In IOC, this approximation assumes the expert locally optimizes actions rather than performing global planning.
- The trajectory reward is represented as the sum of rewards along a path before approximation and likelihood optimization.
- A second-order Taylor expansion of the path reward around the action trajectory produces the approximate log likelihood.
- The likelihood favors reward functions with small trajectory gradients and large negative Hessians, corresponding to nearby and steep reward peaks.
5. Efficient Likelihood Optimization
The method evaluates and optimizes the locally approximated IOC likelihood efficiently by exploiting block structure after linearizing dynamics around expert examples. This reduces computation to time linear in trajectory length for the proposed approximate algorithms.
- Linear-time evaluation: The proposed approximate algorithms evaluate the likelihood in time linear in T by linearizing the dynamics, substantially accelerating longer examples.Without linearization, direct evaluation is cubic in path length T and action dimensionality.
- Structured computation: The Jacobian is block upper triangular because future actions do not influence past states, allowing recursive computations.The Markov property provides recursive expressions for the Jacobian’s nonzero blocks.
- Structured computation: Linearizing the dynamics makes the Hessian’s otherwise dense second-order term disappear, enabling structured likelihood computation.The discarded term is zero only for linear dynamics, so omitting it corresponds to linearizing the dynamics around the examples.
- Linear-time evaluation: The resulting two-pass solver computes h = H^-1g and the determinant |−H| in time linear in trajectory length T.An upward pass computes a partial solution, and a downward pass reconstructs the final values and solution.
- Gradient optimization: For a parameterized reward, gradient-based optimization identifies the most likely parameters by maximizing the approximate likelihood.The implementation uses LBFGS to optimize the reward parameters.
- Gradient optimization: Likelihood gradients remain computable in time linear in T when the discarded second-order dynamics term is zero.The required inverse-Hessian blocks can be computed while solving for h = H^-1g.
6. Algorithms for IOC with Locally Optimal Examples
The paper develops linear and nonlinear reward representations for locally optimal IOC, using feature-based rewards or Gaussian processes and optimizing the resulting approximate likelihood. The variants trade expressiveness against sample efficiency and model complexity.
- Reward representations: The objective supports both a linear combination of features and a Gaussian process for learning nonlinear reward functions.These are the two reward representations presented by the algorithm.
- Linear reward functions: In the linear variant, the reward is r(x_t, u_t) = θ^T f(x_t, u_t), with weights learned from feature derivatives and Hessians.The full derivatives are weighted sums of the corresponding derivatives for each feature.
- Optimization stabilization: A dummy regularizer feature keeps the negative Hessian positive definite during initialization, then its weight is driven to zero through augmented-Lagrangian optimization.The penalty weight is increased by a factor of 10 when the regularizer weight fails to decrease.
- Nonlinear reward functions: In the nonlinear variant, a Gaussian process maps feature values to rewards using inducing points selected on the example paths.The inducing-point outputs are learned, along with kernel hyperparameters λ and β.
- Nonlinear reward functions: The GP reward uses the posterior mean and can be augmented with linear features, while its prior encourages sparse feature weights and avoids degeneracies.The prior also encodes that inducing points should not be deterministically dependent.
- Empirical trade-offs: The linear method needs fewer examples when a linear basis is available, whereas the nonlinear variant works with less expressive features.The nonlinear representation offers more expressive rewards but incurs the usual bias–variance tradeoff from greater model complexity.
7. Evaluation
The evaluation tests the method on planar navigation, robot-arm control, and continuous driving, including locally optimal demonstrations and increasing task dimensionality. The proposed variants recover rewards and policies effectively, while the nonlinear variant also learns from end-effector position features and human driving demonstrations.
- Evaluation tasks: The evaluation covers planar navigation, simulated robot-arm control with state dimension 2n, and a fully continuous driving task.The robot-arm experiments vary the number of links to change dimensionality, while driving uses continuous gas, braking, and steering actions.
- Locally Optimal Examples: Both variants converge to the correct policy on planar navigation with locally optimal examples, whereas MaxEnt does not.The linear variant requires fewer examples because the supplied features form a good linear basis for the true reward.
- Locally Optimal Examples: Only the nonlinear variant learns the robot-arm reward from end-effector position features alone.The comparison uses reward loss with either Gaussian-grid features or end-effector position features on the 2-link arm task.
- Locally Optimal Examples: Our methods efficiently learn good rewards as robot-arm dimensionality increases with the number of links n.The corresponding state spaces have 2n dimensions, and the evaluation tracks both reward loss and processing time.
- Human Demonstrations: Learned driving policies produce task-relevant statistics similar to holdout human demonstrations for aggressive, evasive, and tailgating styles.The study uses sixteen 13-second examples and compares speed plus time spent near the front or rear of other cars.
8. Discussion and Future Work
The method remains efficient in continuous, high-dimensional domains by using a local reward-likelihood approximation, while learning from demonstrations that are only locally optimal. Its scope is limited by differentiability and deterministic fixed-horizon assumptions, and it does not exploit global optimality when available.
- Local reward-likelihood approximation keeps the method efficient in continuous, high-dimensional domains and removes the need for globally optimal demonstrations.This allows learning from examples that are only locally optimal, which can be easier to demonstrate in complex tasks.
- Prior methods do not converge to the underlying reward when demonstrations are only locally optimal, regardless of the number of examples.
- The method requires reward features differentiable with respect to states and actions, making discontinuous features poorly suited.Finite differences are practical when analytic derivatives are unavailable because the derivatives need to be precomputed only once.
- The current formulation covers only deterministic, fixed-horizon control problems; stochastic and infinite-horizon extensions remain future work.
- Unlike methods that exploit global optimality, this approach always assumes local optimality and therefore may infer less information from globally optimal examples.
- Applying the approach to broader high-dimensional continuous problems requires meaningful, generalizable features without detailed features or numerous examples.The nonlinear variant still relies on features to generalize rewards to unseen regions of the state space.