On Feasible Rewards in Multi-Agent Inverse Reinforcement Learning

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

This paper establishes theoretical foundations for Multi-agent Inverse Reinforcement Learning (MAIRL) by characterizing the set of reward functions consistent with observed expert behavior in general-sum Markov games. It proves that a single Nash equilibrium observation yields uninformatively broad and potentially misleading feasible reward sets, and resolves this via entropy-regularized Markov games with unique Quantal Response Equilibria (QRE), deriving explicit reward characterizations and sample complexity bounds.

Problem

Single-agent IRL has well-developed theory (feasible reward sets, identifiability conditions, sample complexity) but its extension to multi-agent settings lacks rigorous foundations. The core difficulty is the multiplicity of Nash equilibria: observing a single NE is insufficient to pin down a meaningful feasible reward set because recovered rewards can rationalize additional equilibria not present in the original game, allowing the nature of the game (e.g., coordination vs. anti-coordination) to shift entirely. This can produce a Nash Imitation Gap of order O((1−γ)⁻¹), making reward transfer to new environments unreliable.

Method

The paper proceeds in two main threads:

1. Feasibility under single NE observation: Defines the MAIRL feasible reward set analogously to single-agent IRL (all rewards under which the observed NE remains a NE), then proves via Proposition 3.4 that any non-constant reward drawn from this set can yield O((1−γ)⁻¹) Nash Gap because constraints on reward only bind for the observed opponent strategy, leaving unconstrained reward entries that introduce spurious equilibria.

2. Entropy-regularized MAIRL: Introduces λ-entropy-regularized Markov games whose unique solution concept is the Quantal Response Equilibrium (QRE). Under QRE experts, the full joint policy explores the action space (satisfying a coverage condition analogously to single-agent entropy-IRL), eliminating the equilibrium selection problem. The authors:

3. Derive an explicit closed-form characterization of feasible rewards (Lemma 3.6) as a function of QRE policies and transition dynamics.
4. Quantify error propagation from estimated (µ̂, ν̂, P̂) to recovered rewards (Theorem 3.7), showing sensitivity scales with 1/(ν(b|s)·ν̂(b|s)) and TV(ν, ν̂).
5. Prove a sample complexity bound using uniform sampling over S×A×B under a generative model (Theorem 3.9).
6. Address reward identifiability: derive rank conditions for average-reward identification (Theorem 4.1) and full identification in linearly separable games R(s,a,b) = Rₐ(s,a) + R_B(s,b) (Proposition 4.3).

Key Contributions

• Formal definition of the MAIRL feasible reward set in general-sum Markov games and the Nash Imitation Gap as performance criterion.
• Proposition 3.4: proof that single NE observation allows adversarial reward recovery with Nash Gap O((1−γ)⁻¹), demonstrated empirically on a Stag Hunt Markov game.
• Lemma 3.6: explicit algebraic characterization of feasible rewards in entropy-regularized 2-player Markov games.
• Theorem 3.7: error propagation bound showing recovered reward error is amplified by joint transition probability products and opponent policy estimation error (TV distance).
• Theorem 3.9: sample complexity of Õ(γ²R_max|S||A||B| / ((1−γ)⁴ε²Δ⁴_min)) for (ε,δ)-correct MAIRL via uniform sampling.
• Theorem 4.1 / Proposition 4.3: rank-based conditions for average-reward and full-reward identifiability (up to additive constants) in 2-player entropy-regularized Markov games.

Results

• Proposition 3.4 (formal): There exist Markov games where any non-constant reward from the single-NE feasible set induces Nash Gap O((1−γ)⁻¹), even with perfect observations.
• Empirical (Fig. 2): Single NE observations on a Stag Hunt Markov game yield multiple new pure equilibria with average Nash Gap ≈1.5 under the recovered reward; QRE observations (Fig. 3) yield zero new pure equilibria.
• Correlation: QRE-recovered rewards achieve substantially higher Pearson (PCC) and Spearman (SCC) correlation with ground-truth rewards compared to Nash-recovered rewards.
• Sample complexity (Theorem 3.9): Õ(γ²R_max|S||A||B| / ((1−γ)⁴ε²Δ⁴_min)); scales as product of joint action spaces, matching known lower bounds for NE learning in two-player zero-sum MARL with generative model access.
• Induced transition estimation (Theorem 4.2): O(|S||A||B|/ε²) samples to estimate P^ν within max-L₁ error ε.

Limitations

• Requires a generative model (can query any (s,a,b) tuple); extension to offline or online settings left for future work.
• Sample complexity has joint action-space factor |A||B|, which becomes exponential in the number of players n; no tight lower bound established for MAIRL specifically.
• Full reward identifiability requires linear separability R(s,a,b) = Rₐ(s,a) + R_B(s,b); in general-sum games without this structure, only average-reward identification is achievable.
• Theoretical analysis is primarily for 2-player games; n-player generalization is noted but not fully developed.
• QRE expert assumption (bounded rationality / entropy-regularized behavior) may not hold in practice.

Relevance to Agentic AI / LLM Agents

MAIRL is foundational for learning reward functions from multi-agent demonstrations, directly relevant to preference learning and RLHF-style training in settings with multiple interacting AI agents. The paper's result that single-equilibrium observations are structurally insufficient—and that the recovered reward can change the game's qualitative nature—has concrete implications for reward modeling in multi-agent LLM deployments or tool-using agent pipelines where agent incentives must be inferred. The entropy-regularized QRE framework parallels the use of KL-regularized objectives in RLHF and connects to maximum-entropy IRL, providing rigorous justification for why stochastic/exploratory expert policies are preferable data sources for inverse learning. The identifiability analysis (average reward recoverable; full reward only under linear separability) establishes hard information-theoretic limits relevant to intent inference in cooperative or competitive LLM agent systems.