Research map / Multi-agent systems and games / Games and equilibria
On Feasible Rewards in Multi-Agent Inverse Reinforcement Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Characterizes feasible reward sets for multi-agent IRL in Markov games, shows single Nash equilibrium observations are ambiguous, proposes entropy-regularized (QRE) experts with a sample complexity bound and identifiability results for linearly separable rewards.
Problem
Multi-agent inverse reinforcement learning in general-sum Markov games is ill-posed: a single Nash equilibrium observation yields an uninformative feasible reward set due to equilibrium multiplicity and selection, and reward identifiability is unclear.
Approach
Defines feasible reward sets for Nash equilibria in Markov games, then uses entropy-regularized Markov games whose unique quantal response equilibrium gives explicit reward characterizations, error propagation bounds, and identifiability conditions (average-reward and linearly separable cases).
Key results
- Shows a single observed Nash equilibrium can lead to recovered rewards whose learned equilibrium has Nash gap of order (1-gamma)^{-1} in the original game.
- Sample complexity of order O~(gamma^2 R_max^2 |S||A||B| / ((1-gamma)^4 eps^2 Delta_min^4)) for uniform sampling with a generative model under QRE experts.
- Reward identifiability up to a constant is possible for linearly separable reward Markov games under a rank condition; in general only average reward is identifiable.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a single Nash equilibrium observation to define the feasible reward set | MAIRL in general-sum Markov games · Markov games | Nash Gap: of order $(1-\gamma)^{-1}$ | Hurt |
| Use QRE rather than a potentially pure Nash equilibrium observation | MAIRL reward recovery · Simple games | PCC | Helped |
| Use QRE rather than a potentially pure Nash equilibrium observation | MAIRL reward recovery · Simple games | SCC | Helped |
| Use QRE rather than a potentially pure Nash equilibrium observation | MAIRL reward recovery · Simple games | New pure equilibria | Helped |
Surprising findings
- A single Nash equilibrium observation can change the nature of the game (e.g., coordination to anti-coordination) when recovered rewards are used.
Limitations
- Sample complexity analysis assumes a generative model and uniform sampling.
- Computing even one Nash equilibrium is computationally intractable in general-sum Markov games, so the set-of-equilibria definition is not tractable.
- Identifiability in general general-sum games only holds for average reward; full reward identification needs linear separability.
Experimental setup
Metrics: Nash imitation gap Pearson correlation coefficient Spearman correlation coefficient
Baselines: Behavioral cloning
Builds on: Inverse reinforcement learning feasible reward set (Metelli et al.) Entropy-regularized IRL identifiability (Cao et al.) Nash Imitation Gap
Closest papers by meaning
- Decoding Rewards in Competitive Games: Inverse Game Theory with Entropy Regularization (ICML 2025 · similarity 0.90)
- Non-Cooperative Inverse Reinforcement Learning (NeurIPS 2019 · similarity 0.90)
- Recent Advancements in Inverse Reinforcement Learning (AAAI 2024 · similarity 0.90)
- Is Inverse Reinforcement Learning Harder than Standard Reinforcement Learning? A Theoretical Perspective (ICML 2024 · similarity 0.89)
- Towards Principled Unsupervised Multi-Agent Reinforcement Learning (NeurIPS 2025 · similarity 0.88)
- Sub-optimal Experts mitigate Ambiguity in Inverse Reinforcement Learning (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.