Evaluating Strategic Structures in Multi-Agent Inverse Reinforcement Learning

Justin Fu, Andrea Tacchetti, Julien Pérolat, Yoram BachrachJAIR 2021 · DOI

TL;DR

This paper introduces IESAR, a novel method for multi-agent inverse reinforcement learning (MAIRL) that decomposes the complex N-player problem into N independent single-agent IRL problems. This approach efficiently extracts reward functions that explain observed behavior, even in games with non-unique equilibria, and demonstrates strong rationality in normal-form games.

What Problem Does This Paper Address?

Understanding the motivations of agents in multi-agent systems is crucial for prediction, cooperation, and designing effective environments. Inverse Reinforcement Learning (IRL) aims to infer an agent's reward function from its observed behavior. However, extending IRL to multi-agent settings (MAIRL) is challenging due to the complexity of N-player interactions, the existence of multiple equilibria, and the difficulty of solving for these equilibria. Existing MAIRL methods often require solving N-player games, which is computationally expensive and can struggle with non-unique equilibria. This paper addresses the need for a more scalable and robust MAIRL approach that can handle these complexities.

Methods

The core contribution of this paper is the Inverse Equilibrium Single-Agent Reduction (IESAR) method. Instead of solving the full N-player game, IESAR reduces the MAIRL problem to N independent single-agent IRL problems. For each agent, it assumes the other agents' policies are fixed to the observed expert behavior and then solves a standard single-agent IRL problem to infer that agent's reward function. This decomposition significantly reduces computational complexity.

The paper also introduces and analyzes the concept of player-agnostic rationality, which is crucial for ensuring that learned reward functions are meaningful and predictive, especially when agents interact with new opponents. They also investigate conditions under which learned rewards can be uniquely identified, particularly in auction settings.

Datasets

The paper does not introduce new datasets. Instead, it uses simulated environments for evaluation:

  • Keep-Away: A stateful Markov game used to evaluate the method's ability to rationalize demonstrations and its performance in a continuous state-action space.
  • Chicken: A classic 2-player normal-form game used to highlight issues of reward ambiguity.
  • First-price, second-price, and generalized second-price (GSP) auctions: These are used to study the inference of player valuations and player-agnostic rationality in a Bayesian game setting.

Key Insights and Ideas

  • Decomposition is Key: Breaking down the complex multi-agent problem into simpler single-agent IRL problems is a powerful and computationally efficient strategy.
  • Beyond Unique Equilibria: IESAR can handle games with non-unique equilibria, a significant advantage over methods that rely on unique solutions.
  • Player-Agnostic Rationality Matters: Simply satisfying strong rationality (i.e., the observed behavior is an equilibrium) is not enough. Learned rewards must also be player-agnostic to generalize to interactions with new agents with different objectives.
  • Identifiable Games are Crucial: In settings like auctions, restricting the reward function class (e.g., to a single valuation parameter) is essential for learning identifiable and predictive reward functions.
  • Ambiguity is a Real Problem: Even with strong rationality, learned rewards can be ambiguous, leading to poor performance when agents interact with unseen opponents.

Key Results

  • IESAR demonstrates comparable performance to existing MAIRL methods that require full game-theoretic solvers, despite its simpler approach.
  • In the Keep-Away game, IESAR achieved regret close to the expert demonstrations, even though the game has non-interactive dynamics, which is a theoretical requirement for strong rationality guarantees.
  • In the Chicken game, IESAR recovered a cooperative game from an anti-coordination game demonstration, highlighting the issue of reward ambiguity. However, the learned behavior still matched the expert's equilibrium.
  • In auction experiments, IESAR successfully inferred player valuations, and importantly, the "Valuation" strategy (a restricted form of IESAR) showed superior performance in transfer learning scenarios (playing against new agents) compared to more general neural network reward functions.

Limitations and Future Work

  • Strong Rationality Guarantees: IESAR currently only provides strong rationality guarantees for normal-form games. Extending these guarantees to general Markov games remains an open problem.
  • Sample Complexity: The analysis does not explicitly account for sampling error from finite demonstrations. Developing finite-sample bounds for IESAR is a future direction.
  • Alternative Solution Concepts: The paper primarily focuses on Nash equilibria. Exploring other solution concepts like extensive-form correlated equilibria could be beneficial for modeling human behavior.
  • Learning Agnostic Rewards: Investigating methods to learn player-agnostic rewards with more general function classes, potentially by learning shared utilities across games, is a promising avenue.

Summary updated

BibTeX
@article{fu2021evaluating,
  author = {Justin Fu and Andrea Tacchetti and Julien Pérolat and Yoram Bachrach},
  title = {{Evaluating Strategic Structures in Multi-Agent Inverse Reinforcement Learning}},
  journal = {J. Artif. Intell. Res.},
  year = {2021},
  doi = {10.1613/jair.1.12594},
}
Figure