Source-linked AI summary
Repeated Inverse Reinforcement Learning
Kareem Amin, Nan Jiang, Satinder Singh
TL;DR
Repeated IRL studies how an agent can act for a human across sequential tasks despite not knowing the human’s intrinsic reward. The paper formalizes task-selection and demonstration settings, showing that agent-chosen tasks permit reward identification in O(log(1/ε)) demonstrations while also characterizing behavioral equivalence and limitations under nature-chosen tasks.
Problem
Standard IRL cannot uniquely identify rewards from a single task, making generalization to new tasks and safe behavior difficult.
Method
The paper separates a fixed intrinsic reward θ⋆ from task-specific rewards, formalizes repeated tasks with human demonstrations after suboptimal actions, and analyzes multiple task-selection settings.
Results
When the agent chooses tasks, θ⋆ can be identified to accuracy ε after O(log(1/ε)) demonstrations.
Takeaways & Limitations
Repeated tasks can resolve reward ambiguity behaviorally and support generalization to new tasks, while the paper provides bounds and identification guarantees for different task-sequence settings.
Takeaways & Limitations
If task environments provide no informative variation, such as identical state features across actions, some directions of θ⋆ cannot be recovered.
Abstract
from arXiv · showhide
We introduce a novel repeated Inverse Reinforcement Learning problem: the agent has to act on behalf of a human in a sequence of tasks and wishes to minimize the number of tasks that it surprises the human by acting suboptimally with respect to how the human would have acted. Each time the human is surprised, the agent is provided a demonstration of the desired behavior by the human. We formalize this problem, including how the sequence of tasks is chosen, in a few different ways and provide some foundational results.
1 Introduction
Repeated IRL addresses the ill-posedness of inferring human rewards from one task by studying how an agent can generalize behavior across a sequence of tasks. The paper formalizes several settings and develops foundational results for reducing surprises and reward misspecification.
- Motivation: Single-task IRL is ill-posed because many reward functions can make the observed human behavior optimal.This ambiguity makes performance and safety on other tasks difficult to assess.
- Contribution: The paper separates rewards into task-invariant intrinsic preferences and task-specific goals across repeated human-agent tasks.The same human may pursue different external goals while retaining concerns such as health, financial well-being, and moral or legal principles.
- Motivation: Repeated IRL asks an agent to minimize surprises by generalizing the human’s behavior to new tasks.When the agent acts suboptimally, the human provides a demonstration of the desired behavior.
- Contribution: The paper develops mathematical formulations and algorithmic solutions for a specific reward-misspecification problem relevant to AI safety.It focuses on a concrete formulation rather than the broad ethical concerns emphasized in much AI safety discussion.
- Contribution: Its contributions include efficient identification with agent-chosen tasks, surprise bounds under nature-chosen tasks, trajectory demonstrations, and guarantees when only task rewards are controllable.These results cover both complete behavior and sample-trajectory feedback.
2 Markov Decision Processes (MDPs)
The paper models tasks as finite Markov decision processes and represents policy quality through discounted long-term value. It introduces occupancy-vector notation that expresses expected policy value as a reward-weighted inner product.
- MDP components: An MDP specifies states, actions, an initial distribution, dynamics, a reward function, and a discount factor.A policy maps each state to an action, and an optimal policy maximizes value across states and actions.
- Policy value: A policy’s normalized value is its expected discounted reward from each starting state.The framework also defines Q-values for state-action pairs.
- Occupancy representation: Expected policy quality under an initial state distribution is written as the inner product Y^Tη^π_{μ,P}.Here η^π_{μ,P} is the normalized state-occupancy vector induced by the policy, initial distribution, and dynamics.
3 Problem setup
Repeated IRL treats a human’s unknown intrinsic reward as shared across tasks and combines it with each task’s known external reward. The paper studies both agent-chosen and nature-chosen task sequences, with demonstrations triggered by suboptimal proposed behavior.
- Problem setup: The human’s total reward in each task is Y = θ⋆ + R, combining private cross-task preferences with the task-specific reward.The agent cannot directly receive θ⋆ but can evaluate its behavior and observe optimal demonstrations.
- Problem setup: Tasks are pairs (E, R), where E contains the shared state and action spaces, discount factor, and task-specific initial distribution and dynamics.The intrinsic reward θ⋆ remains fixed across tasks, while R and parts of E may vary.
- Assumptions: The model assumes bounded normalized human rewards, with ||θ⋆||∞ ≤ 1, and gives the agent a prior candidate set Θ0 containing θ⋆.This prior knowledge constrains the unknown intrinsic reward.
- Task selection: With agent-chosen tasks, the agent identifies the human reward; with nature-chosen tasks, the analysis instead bounds the number of mistakes.These are the two principal repeated-IRL task-sequence settings.
- Feedback and settings: When a proposed policy is significantly suboptimal, the human demonstrates optimal behavior; the paper also considers demonstrations as occupancy information and extends this to trajectories.The objective in both task-selection settings is to minimize the number of demonstrations needed.
4 The challenge of identifying rewards
The paper separates meaningful reward identification from unavoidable representational ambiguity. It defines behavioral equivalence across all tasks and shows that only additive constants remain indistinguishable.
- The identification challenge: A single task cannot identify the human reward because infinitely many reward functions can produce the same observed policy.The paper therefore introduces behavioral equivalence to distinguish consequential ambiguity from representation.
- Behavioral equivalence: Two rewards are behaviorally equivalent when every task has the same set of optimal policies under either reward combined with its task reward.This definition focuses identification on behavior rather than a particular numerical representation.
- Characterization: Behavioral equivalence across all MDP tasks holds exactly when two reward vectors differ by an additive constant c·1_|S|.Identifying this equivalence class is sufficient for perfect generalization to new tasks.
- Canonicalization: The paper canonicalizes each equivalence class by fixing a reference state’s reward to zero.This removes the representational degree of freedom without changing optimal behavior.
5 Agent chooses the tasks
When the agent can choose tasks, it can identify the human’s invariant reward efficiently by manipulating task rewards, enabling near-optimal behavior across tasks.
- The protocol has the agent choose tasks and observe the human’s optimal policy for the combined reward θ⋆ + R_t.Task rewards can be manipulated while using a fixed environment in the constructive algorithm.
- The identification algorithm effectively performs binary search on each component of θ⋆ by manipulating the task reward.
- A related proof can instead keep all task rewards zero and manipulate the environment, with only a slight increase in complexity.
- Once θ⋆ is identified within an appropriate tolerance, the agent can compute a sufficiently near-optimal policy for all tasks.This achieves generalization through the stronger objective of reward identification.
- O(log(1/ε)) demonstrations suffice to identify θ⋆ within ε when the agent may choose any tasks.Theorem 1 guarantees ||θ − θ⋆||∞ ≤ ε under the stated assumptions.
6 Nature chooses the tasks
When Nature chooses tasks, repeated IRL becomes a mistake-minimization problem: the agent proposes policies, receives demonstrations only after significant suboptimality, and updates its uncertainty about the human’s reward. The paper gives an ellipsoid algorithm with dimension-dependent mistake bounds, matching lower bounds, and identification guarantees under additional diversity conditions.
- 6 Nature chooses the tasks: The agent proposes a policy for each Nature-chosen task, and a demonstration is supplied only when its loss exceeds ǫ.Human supervision requires only the binary signal indicating whether the loss exceeds the tolerance.
- 6.2 Ellipsoid Algorithm for Repeated Inverse Reinforcement Learning: O(d^2 log(d/ǫ)) mistakes are guaranteed for the ellipsoid algorithm in the linear-bandit formulation.The formulation represents actions by feature vectors, with MDP policies embedded as actions and state occupancies as features.
- 6.3 Lower bound: The worst-case lower bound is Ω(d log(1/ǫ)) mistakes for randomized algorithms facing adaptive adversarial tasks.The adversary shifts task rewards to keep the relevant posterior near a decision boundary, producing repeated errors while uncertainty contracts.
- 6.3 Lower bound: The lower bound transfers to MDPs as Ω(|S| log(1/ǫ)) mistakes, even when the action space has size |A| = 2.The transfer uses nonnegative, ℓ1-bounded feature vectors that can be emulated by MDPs.
- 6.4 On identification when nature chooses tasks: Identification is possible when all possible mistakes have been exhausted, yielding θ⋆ within ǫ of the estimated center.The guarantee depends on the tolerance defining a mistake and follows from the no-further-mistakes condition.
- 6.4 On identification when nature chooses tasks: Fixed environments require feature variation in every direction; otherwise degenerate features can permanently hide components of θ⋆.The diversity score spread(X) captures this requirement, and Theorem 4 gives T = O(d^2 log(d/ǫ)) rounds when spread(X) > 0.
7 Working with trajectories
The trajectory-based variant counts mistakes at individual actions and replaces complete-policy demonstrations with optimal trajectories starting where the agent errs. It updates reward estimates in mini-batches and provides a high-probability mistake bound.
- Error criterion: Action-level errors are counted when Q⋆(s, a) < V⋆(s) − ǫ, because a single trajectory’s total reward may not reveal policy near-optimality.Averaging V⋆(s)−Q⋆(s, π(s)) over the agent-induced occupancy recovers the earlier error notion.
- Demonstration protocol: The human demonstrates an optimal-policy trajectory from the state where the agent makes an error, avoiding the selection-bias problems of rolling out from the task’s initial distribution.The alternative protocol starts the human trajectory at the problematic state.
- Reduction: A spotted suboptimal action implies the agent’s policy is suboptimal when the problematic state is treated as the initial state.The reduction follows from V^π(s) ≤ Q⋆(s, π(s)) < V⋆(s) − ǫ.
- Algorithm: Instead of updating after every mistake, Algorithm 2 aggregates mini-batches of trajectory mistakes before updating the reward-parameter set.This aggregation produces accurate update rules for single-trajectory demonstrations.
- Guarantee: Theorem 5 gives a 1−δ probability guarantee that Algorithm 2 makes at most ˜O(d^2 …) mistakes.The supplied theorem statement contains only the beginning of the bound.
8 Related work & Conclusions
Prior IRL work mainly infers rewards from fixed environments or predicts behavior across exogenously fixed environments, whereas this paper targets generalization to new tasks. The paper also contrasts its repeated-task formulation with single-environment cooperative IRL.
- Prior IRL: Most existing IRL methods infer rewards from data collected in a fixed environment, with some extensions to multiple but exogenously fixed environments.These works include Ng and Russell, Abbeel and Ng, Coates et al., Ziebart et al., Ramachandran and Amir, Syed and Schapire, and Regan and Boutilier [Ng and Russell, 2000, Abbeel and Ng, 2004, Coates et al., 2008, Ziebart et al., 2008, Ramachandran and Amir, 2007, Syed and Schapire, 2007, Regan and Boutilier, 2010].
- Generalization: Unlike prior work that mimics optimal behavior in presented environments, this paper focuses on generalization to new tasks.The distinction is the paper’s stated main contribution.
- Cooperative IRL: Cooperative inverse reinforcement learning lets humans actively resolve reward uncertainty, but its single-environment setting leaves the IRL unidentifiability issue in place [Hadfield-Menell et al., 2016].The paper identifies combining that framework with its own resolution of unidentifiability as a possible direction.
A Proof of Proposition 1
The proof characterizes behavioral equivalence of reward parameters up to constant shifts and constructs an MDP whose policy occupancies encode arbitrary feature vectors. This reduction transfers a linear-bandit argument to the MDP setting and supports a repeated-error construction.
- Behavioral equivalence: Reward parameters differing by c·1_|S| induce the same set of optimal policies because every policy’s occupancy has the same total mass.Thus constant shifts are behaviorally irrelevant.
- Identifiability: The converse constructs an environment where any nonconstant difference between reward parameters changes the set of optimal policies.Choosing R = −θ′ makes all policies optimal under R + θ′, while an absorbing-state construction separates behavior under θ.
- Linear-bandit reduction: The MDP construction uses a reference state and absorbing states so an action’s induced occupancy matches a selected feature vector x.The remaining occupancy has total ℓ1 mass ||x||1 and is distributed proportionally to x, recovering the original linear bandit.
- Error construction: When the algorithm’s estimate differs from θ⋆ by more than ǫ in some coordinate, two available actions can differ by more than ǫ in value, allowing another error.The construction uses one zero-valued action and one coordinate basis-vector action.
D Proof of Theorem 4
The proof of Theorem 4 lower-bounds task separability through a difference matrix whose columns enumerate action-pair contrasts. Singular-value and geometric bounds then yield a task where the reward-estimation error causes a mistake.
- Conclusion: The assembled inequalities establish the theorem’s lower-bound argument by guaranteeing a sufficiently separating action pair under the constructed task.The proof’s final combination is stated after the component bounds.
- Mistake condition: The proof reduces a mistake to finding actions a and a′ with (θ⋆−c_t)^T(x_a−x_a′) > ǫ.Here y_t = θ⋆−c_t measures the current estimation error.
- Difference matrix: Matrix D contains one 1 and one −1 per column, enumerating all pairwise coordinate contrasts and rewriting the action-separation condition as a norm bound.Every column is orthogonal to 1_K.
- Geometric bound: The smallest nonzero singular value of the feature-derived matrix eX is bounded below by spread(X), supplying the key geometric term in the lower bound.The proof lower-bounds three terms, including the current error norm and the feature-matrix transformation.
E Proof of Theorem 3
The proof constructs phased tasks that repeatedly shrink the posterior interval for each coordinate while keeping the mistake probability bounded below, yielding an Ω(d log(1/ε)) expected-mistake lower bound.
- Lower bound: Any algorithm makes Ω(d log(1/ε)) expected mistakes under a randomized θ⋆, which also implies a worst-case lower bound.The expectation is over θ⋆ and the algorithm’s internal randomness; the worst-case result follows because a maximum is at least the corresponding average.
- Lower bound: The proof assumes θ⋆ is sampled coordinatewise from Unif([−1,1]) to establish the posterior-shrinking construction and then converts the average bound to a worst-case result.The randomized construction is the standard route to the lower bound.
- Adversarial construction: The adversary uses phases of d rounds, enumerating coordinates while holding the task reward R_t fixed within each phase.Each round asks whether θ⋆(j_t) ≥ −R_t(j_t).
- Technical refinement: Accounting for the ε-dependent information revealed in the first phase requires distinguishing whether each coordinate lies above or below ±ε before simplifying to a sign test.The proof later removes this simplification by tracking the interval shrinkage and adjusted error probability directly.
- Phase analysis: After centering the posterior with R_t, each phase halves its interval scale, preserving a mistake probability of at least 1/2 − ε/2^(−m+2).The process continues while this probability remains positive, and linearity of expectation sums mistakes across phases.
- Technical refinement: With the exact interval bound, the per-phase error probability remains at least 1/4 whenever 2^(−m+1) ≥ 5ε, giving the logarithmic number of contributing phases.This condition is equivalent to m ≤ ⌊log_2(1/(5ε))⌋.
G Proof of Theorem 5
The proof of Theorem 5 controls truncation and sampling errors through martingale concentration, while central-cut updates preserve θ⋆ and enough ellipsoid volume for a finite update bound.
- Concentration: Azuma’s inequality controls martingale deviations by choosing the increment bound and mini-batch size so the relevant error term is at most ε/3 with high probability.The proof sets b = 4 and chooses n sufficiently large, then union-bounds failure across updates.
- Ellipsoid updates: Central-cut updates preserve θ⋆ and a neighborhood around it, allowing the ellipsoid-volume argument from Theorem 2 to bound the number of updates.The update rule remains a central cut, so the volume reduction lemma applies.
- Update validity: The update validity condition follows by decomposing the target expression into three terms: one is at least ε, while the other two are each bounded by ε/3.The second error term uses the ℓ1 occupancy bound, convexity, Hölder’s inequality, and ||θ⋆−c||∞ ≤ 2.
- Final bound: The resulting number of updates is bounded by 2d(d + 1) log(12√…/ε), and total mistakes equal this update count multiplied by the mini-batch size n.The displayed bound is obtained after showing that B∞(θ⋆, ε/6) is never eliminated.