Cooperative Inverse Reinforcement Learning

Dylan Hadfield-Menell, Anca Dragan, Pieter Abbeel, Stuart Russell

★ Must read June 2016

TL;DR Frames value alignment as a cooperative game in which only the human knows the reward and both players are paid by it, reduces optimal play to a POMDP over the robot's belief, and proves that expert demonstrations are not the best way to teach an IRL robot. In a gridworld, "instructive" demonstrations beat expert ones on regret over 500 sampled reward functions.

What they do

Inverse reinforcement learning (IRL) assumes the human acts optimally as if no robot were watching, which rules out teaching. Cooperative IRL (CIRL) is instead a two-player Markov game: the human observes the reward parameters θ, the robot only knows a prior, and both receive the human’s reward. Teaching and active learning are not built-in objectives; they emerge from optimal play.

How it works

POMDP reduction. Since θ is the only private information, finding an optimal policy pair reduces to a single-agent POMDP with

hidden states, exponentially simpler than a general (NEXP-complete) Dec-POMDP. The robot’s belief over θ is a sufficient statistic.

Apprenticeship CIRL. The players take turns in a learning phase; in deployment the robot acts alone and maximizes reward under its mean θ. IRL is the robot’s best response to a human who demonstrates as an expert, but that human is not best-responding in turn.
Instructive demonstrations. For rewards linear in features, the human picks a trajectory that trades off reward against the ℓ2 distance between its features and the feature counts θ would produce in expectation.

Results

In a paperclips-vs-staples example, the human’s best response makes one of each for θ in [41/92, 51/92], while an expert does so only at θ = 0.5.
In gridworld navigation, the robot runs Maximum-Entropy IRL and is tested on 500 random reward parameters with 3 or 10 features. Instructive demonstrations beat expert ones on regret, KL divergence and reward error (all F > 962, p < .0001), and the gap is larger with 3 features.
Regret is lowest when the robot assumes the human is only noisily optimal (intermediate λ).

Limitations

Optimal policy pairs assume both players agree on a coordination policy in advance, which the authors call infeasible in reality; how independent actors reach mutual best responses is left open. The reduced POMDP is still hard, with a much larger action space. The approximate algorithm needs linear rewards and uses ℓ2 distance as a proxy for regret, and all experiments are in a simulated gridworld.

Figures

From Figure 1: Ground-truth reward in the grid navigation task; lighter cells have higher reward.

From Figure 1: An expert demonstration, drawn over the reward the robot infers from it. The robot learns where the ma... — From Figure 1: An expert demonstration, drawn over the reward the robot infers from it. The robot learns where the maximum reward is, but little else.

From Figure 1: An instructive demonstration that visits both high-reward areas, so the reward the robot infers is clo... — From Figure 1: An instructive demonstration that visits both high-reward areas, so the reward the robot infers is closer to the ground truth.

From Figure 2: Regret, KL divergence and reward error for expert (πE) versus instructive (br) demonstrations with 3 a... — From Figure 2: Regret, KL divergence and reward error for expert (πE) versus instructive (br) demonstrations with 3 and 10 features, lower is better. Right: regret of the instructive policy against how optimal the robot expects the human to be (λ); it is lowest at intermediate λ.

Abstract

For an autonomous system to be helpful to humans and to pose no unwarranted risks, it needs to align its values with those of the humans in its environment in such a way that its actions contribute to the maximization of value for the humans. We propose a formal definition of the value alignment problem as cooperative inverse reinforcement learning (CIRL). A CIRL problem is a cooperative, partial-information game with two agents, human and robot; both are rewarded according to the human's reward function, but the robot does not initially know what this is. In contrast to classical IRL, where the human is assumed to act optimally in isolation, optimal CIRL solutions produce behaviors such as active teaching, active learning, and communicative actions that are more effective in achieving value alignment. We show that computing optimal joint policies in CIRL games can be reduced to solving a POMDP, prove that optimality in isolation is suboptimal in CIRL, and derive an approximate CIRL algorithm.

Summaries are written automatically from each paper's text. Figures and videos come from the paper and its project page; all credit goes to the authors.

Matt Strong