Maximum Entropy Inverse Reinforcement Learning

1 Maximum Entropy Inverse Reinforcement LearningBrianD. Ziebart, Andrew Maas, Bagnell,andAnind K. DeySchool of Computer ScienceCarnegie Mellon UniversityPittsburgh, PA research has shown the benefit of framing problemsof imitation Learning as solutions to Markov Decision Prob-lems. This approach reduces Learning to the problem of re-covering a utility function that makes the behavior inducedby a near-optimal policy closely mimic demonstrated behav-ior. In this work, we develop a probabilistic approach basedon the principle of Maximum Entropy .

2 Our approach providesa well-defined, globally normalized distribution over decisionsequences, while providing the same performance guaranteesas existing develop our technique in the context of modeling real-world navigation and driving behaviors where collected datais inherently noisy and imperfect. Our probabilistic approachenables modeling of route preferences as well as a powerfulnew approach to inferring destinations and routes based onpartial problems ofimitation learningthe goal is to learn to pre-dict the behavior and decisions an agent would choose ,the motions a person would take to grasp an object or theroute a driver would take to get from home to work.

3 Captur-ing purposeful, sequential decision-making behavior can bequite difficult for general-purpose statistical machine learn-ing algorithms; in such problems, algorithms must often rea-son about consequences of actions far into the powerful recent idea for approaching problems of imi-tation Learning is to structure the space of learned policies tobe solutions of search, planning, or, more generally, MarkovDecision Problems (MDP). The key notion, intuitively, isthat agents act to optimize an unknown reward function (as-sumed to be linear in the features) and that we must findreward weights that make their demonstrated behavior ap-pear (near)-optimal.

4 The imitation Learning problem thenis reduced to recovering a reward function that induces thedemonstrated behavior with the search algorithm serving to stitch-together long, coherent sequences of decisions thatoptimize that reward take a thoroughly probabilistic approach to reasoningabout uncertainty in imitation Learning . Under the constraintof matching the reward value of demonstrated behavior, weCopyrightc 2008,Association for the Advancement of ArtificialIntelligence ( ). All rights the principle ofmaximum entropyto resolve the am-biguity in choosing a distribution over decisions.

5 We pro-vide efficient algorithms for Learning and inference for de-terministic MDPs. We rely on an additional simplifying as-sumption to make reasoning about non-deterministic MDPstractable. The resulting distribution is a probabilistic modelthat normalizes globally over behaviors and can be under-stood as an extension to chain conditional random fields thatincorporates the dynamics of the planning system and ex-tends to the infinite research effort is motivated by the problem of mod-eling real-world routing preferences of drivers.

6 We applyour approach to route preference modeling using 100,000miles of collected GPS data of taxi-cab driving, where thestructure of the world ( , the road network) is known andthe actions available ( , traversing a road segment) arecharacterized by road features ( , speed limit, number oflanes). In sharp contrast to many imitation Learning tech-niques, our probabilistic model of purposeful behavior in-tegrates seamlessly with other probabilistic methods includ-ing hidden variable techniques. This allows us to extend ourroute preferences with hidden goals to naturally infer bothfuture routes and destinations based on partial key concern is that demonstrated behavior is prone tonoise and imperfect behavior.

7 The Maximum Entropy ap-proach provides a principled method of dealing with thisuncertainty. We discuss several additional advantages inmodeling behavior that this technique has over existing ap-proaches to Inverse Reinforcement Learning including marginmethods (Ratliff, Bagnell, & Zinkevich 2006) and those thatnormalize locally over each state s available actions (Ra-machandran & Amir 2007; Neu & Szepesvri 2007).BackgroundIn the imitation Learning setting, an agent s behavior ( ,its trajectory or path, , of statessiand actionsai) in someplanning space is observed by a learner trying to model orimitate the agent.

8 The agent is assumed to be attemptingto optimize some function that linearly maps the featuresof each state,fsj k, to a statereward valuerepresent-ing the agent s utility for visiting that state. This functionis parameterized by somereward weights, . The rewardvalue of a trajectory is simply the sum of state rewards, or,equivalently, the reward weight applied to the pathfeatureProceedings of the Twenty-Third AAAI Conference on Artificial Intelligence (2008)1433counts,f = sj fsj,which are the sum of the state fea-tures along the (f ) = f = sj fsjThe agent demonstrates single trajectories, i, and has anexpected empirical feature count, f=1m if i,based onmany (m) demonstrated the agent s exact reward weights is an ill-posed problem.

9 Many reward weights, including degenera-cies ( , all zeroes), make demonstrated trajectories opti-mal. Ratliff, Bagnell, & Zinkevich (2006) cast this problemas one ofstructured Maximum margin prediction(MMP).They consider a class of loss functions that directly measuredisagreement between an agent and a learned policy, andthen efficiently learn a reward function based on a convexrelaxation of this loss using the structured margin methodand requiring only oracle access to an MDP solver. How-ever, this method suffers from some significant drawbackswhen no single reward function makes demonstrated behav-ior both optimal and significantly better than any alternativebehavior.

10 This arises quite frequently when, for instance,the behavior demonstrated by the agent is imperfect, or theplanning algorithm only captures a part of the relevant state-space and cannot perfectly describe the observed & Ng (2004) provide an alternate approach basedon Inverse Reinforcement Learning (IRL) (Ng & Russell2000). The authors propose a strategy of matchingfeatureexpectations(Equation 1) between an observed policy anda learner s behavior; they demonstrate that this matchingis both necessary and sufficient to achieve the same perfor-mance as the agent if the agent were in fact solving an MDPwith a reward function linear in those features.