Algorithms for Inverse Reinforcement Learning

Andrew Y. Ng and Stuart Russell study how to infer a reward function from an agent’s observed decisions. In their Markov decision process (MDP) formulation, a policy specifies which action to take in each state, and reward assigns value to states. Ordinary reinforcement learning starts with reward and seeks a good policy; inverse reinforcement learning asks which rewards make a given policy optimal. The paper appeared at ICML in 2000.^[1]

Compatible rewards and selection rules

The initial problem gives the learner the complete policy, transition probabilities and discount factor in a finite MDP. Discounted return adds future rewards with successively smaller weights. Theorem 3 characterizes compatible rewards through linear inequalities: at every state, following the demonstrated action must have at least as much expected continuation value as taking another action and then following the policy. This assumes optimal demonstrated behavior in the specified model.^[1]

Behavior leaves many solutions. An everywhere-zero or constant reward makes every policy optimal; even requiring the demonstrated policy to be uniquely optimal does not generally identify one reward. The authors choose among explanations by maximizing the summed gap between demonstrated actions and their best alternatives, subject to bounded rewards and optimality constraints. An optional penalty on the sum of absolute reward values favors smaller, often sparse rewards. Its strength changes the answer and can eventually force the zero solution. These are selection heuristics, not evidence that the original objective has been uniquely recovered (section 3).^[1]

For large or continuous state spaces, section 4 expresses reward as a linear combination of fixed, known, bounded basis functions. Constraints are sampled at finitely many states and violations penalized: the chosen feature class may not contain any nontrivial reward that makes the entire policy optimal. Section 5 instead uses sampled trajectories and iteratively finds a reward favoring the expert over previously generated comparison policies. It does not require an explicit transition model, but assumes simulation under chosen policies and a solver that can find an optimal policy for each candidate reward. Its discounted infinite-horizon estimates are truncated for practical sampling.^[1]

What the experiments establish

A 5-by-5 grid has a reward of 1 at its absorbing goal and actions that move randomly with 30% probability. The unpenalized reconstruction is irregular; a chosen penalty produces a reward closer to the simple goal structure. Mountain-car demonstrations use fixed Gaussian basis functions to recover both a goal-reaching reward and a modified task rewarding parking at the bottom of the hill. The latter reconstruction also contains an artifact the authors associate with unavoidable overshoot (section 6).^[1]

A continuous-grid experiment uses 225 Gaussian basis functions, discount 0.9, a uniform initial-state distribution, and 5,000 trajectories of 30 steps to estimate each policy. Figure 5 shows five runs. The inferred reward’s optimal policy typically disagrees with the original policy on 3–10% of states, yet after about 15 iterations its return under the true reward has no statistically significant detected difference from the comparison optimum. That return comparison uses 50,000 Monte Carlo trials of 50 steps. Similar task performance and identical action choices are different measurements; failure to detect a difference is not proof of exact equality.^[1]

From objective inference to alignment

In a September 23, 2016 Science Friday interview, Stuart Russell illustrated objective inference with someone’s morning coffee-making routine. This is an attributed public teaching example, separate from the paper’s simulated experiments.^[2]

For Outer Alignment, demonstrations offer one way to inform objective specification. But the paper leaves noisy observations, suboptimal behavior, identifiability and partial observability as open questions. Apprenticeship Learning via Inverse Reinforcement Learning later asks whether comparable task performance is possible despite uncertainty about the true reward. Neither explaining behavior nor matching performance determines whether an inferred objective represents defensible human values.^[1]