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 . 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.

2 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. 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 .

3 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. 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. 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).

4 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. 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.

5 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; 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).

6 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. 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.

7 Path iP( i)f i= f(1)Unfortunately, both the IRL concept and the matching offeature counts are ambiguous. Each policy can be optimalfor many reward functions ( , all zeros) and many policieslead to the same feature counts. When sub-optimal behavioris demonstrated, mixtures of policies are required to matchfeature counts, and, similarly, many different mixtures ofpolicies satisfy feature matching. No method is proposed toresolve the Entropy IRLWe take a different approach to matching feature counts thatallows us to deal with this ambiguity in a principled way, andresults in a single stochastic policy. We employ the princi-ple of Maximum Entropy (Jaynes 1957) to resolve ambigui-ties in choosing distributions. This principle leads us to thedistribution over behaviors constrained to match feature ex-pectations, while being no more committed to any particularpath than this constraint Path DistributionsUnlike previous work that reasons about policies, we con-sider a distribution over the entire class of possible behav- (a)s1s2s3a1a2a3a5a4a6(c)s1s2s3a1a2a3a5a4 (b)s1s2s2s3s3s1s2a1a4a6a2a5a3(d)s1s2s1s2 s3s3s2a1a4a5a2a3 Figure 1: A deterministic MDP (a) and a single path fromits path-space (b).

8 A non-deterministic MDP (c) and a singlepath from its path-space (d).iors. This corresponds to paths of (potentially) variablelength (Figure 1b) for deterministic MDPs (Figure 1a).Similar to distributions of policies, many different dis-tributions of paths match feature counts when any demon-strated behavior is sub-optimal. Any one distribution fromamong this set may exhibit a preference for some of thepaths over others that is not implied by the path employ the principle of Maximum Entropy , which re-solves this ambiguity by choosing the distribution that doesnot exhibit any additional preferences beyond matching fea-ture expectations (Equation 1). The resulting distributionover paths for deterministic MDPs is parameterized by re-ward weights (Equation 2). Under this model, plans withequivalent rewards have equal probabilities, and plans withhigher rewards are exponentially more ( i| ) =1Z( )e f i=1Z( )ePsj i fsj(2)Given parameter weights, thepartition function,Z( ), al-ways converges for finite horizon problems and infinite hori-zons problems with discounted reward weights.

9 For infinitehorizon problems with zero-reward absorbing states, the par-tition function can fail to converge even when the rewards ofall states are negative. However, given demonstrated tra-jectories that are absorbed in a finite number of steps, thereward weights maximizing Entropy must be Path DistributionsIn general MDPs, actions produce non-deterministic transi-tions between states (Figure 1c) according to the state tran-sition distribution,T. Paths in these MDPs (Figure 1d) arenow determined by the action choices of the agent and therandom outcomes of the MDP. Our distribution over pathsmust take this randomness into use the Maximum Entropy distribution of paths con-ditioned on the transition distribution, T, and constrained tomatch feature expectations (Equation 1). Consider the space1434of action outcomes,T,and an outcome sample,o, speci-fying the next state for every action. The MDP is deter-ministic givenowith the previous distribution (Equation 2)over paths compatible witho( , the action outcomes of thepath andomatch).

10 The indicator function,I ois 1 when is compatible withoand 0 otherwise. Computing this dis-tribution (Equation 3) is generally intractable. However, ifwe assume that transition randomness has a limited effecton behavior and that the partition function is constant for allo T, then we obtain a tractable approximate distributionover paths (Equation 4).P( | , T) = o TPT(o)e f Z( , o)I o(3) e f Z( , T) st+1,at,st PT(st+1|at, st)(4)Stochastic PoliciesThis distribution over paths provides a stochastic policy ( ,a distribution over the available actions of each state) whenthe partition function of Equation 4 converges. The proba-bility of an action is weighted by the expected exponentiatedrewards of all paths that begin with that (actiona| , T) :a t=0P( | , T)(5) Learning from Demonstrated BehaviorMaximizing the Entropy of the distribution over paths sub-ject to the feature constraints from observed data implies thatwe maximize the likelihood of the observed data under themaximum Entropy (exponential family) distribution derivedabove (Jaynes 1957).