Source-linked AI summary
A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning
Marc Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Perolat, David Silver, Thore Graepel
TL;DR
Independent learners can overfit to the policies encountered during training, limiting generalization in multiagent environments. The paper introduces policy-space response oracles that combine deep-RL approximate best responses with empirical game-theoretic meta-solvers, and reports more general policies in partially observable games. A decoupled implementation reduces memory requirements, while the authors identify slower RL convergence and several directions for future work.
Problem
Independent reinforcement learners can overfit to other agents’ policies during training, limiting the generality of their learned policies.
Method
The paper combines deep reinforcement learning for approximate best responses with empirical game-theoretic meta-solvers that compute distributions over policies.
Results
PSRO/DCH produces general policies that significantly reduce joint-policy correlation in partially observable coordination games and robustly exploits opponents in imperfect-information poker.
Takeaways & Limitations
The framework generalizes independent RL, iterated best response, Double Oracle, and fictitious play while supporting decentralized execution with lower memory requirements.
Takeaways & Limitations
The RL response step can converge slowly because behaviors learned in one epoch may need to be relearned in later epochs.
Abstract
from arXiv · showhide
To achieve general intelligence, agents must learn how to interact with others in a shared environment: this is the challenge of multiagent reinforcement learning (MARL). The simplest form is independent reinforcement learning (InRL), where each agent treats its experience as part of its (non-stationary) environment. In this paper, we first observe that policies learned using InRL can overfit to the other agents' policies during training, failing to sufficiently generalize during execution. We introduce a new metric, joint-policy correlation, to quantify this effect. We describe an algorithm for general MARL, based on approximate best responses to mixtures of policies generated using deep reinforcement learning, and empirical game-theoretic analysis to compute meta-strategies for policy selection. The algorithm generalizes previous ones such as InRL, iterated best response, double oracle, and fictitious play. Then, we present a scalable implementation which reduces the memory requirement using decoupled meta-solvers. Finally, we demonstrate the generality of the resulting policies in two partially observable settings: gridworld coordination games and poker.
1 Introduction
The paper identifies policy overfitting as a central weakness of independent multiagent reinforcement learning and introduces a general game-theoretic framework to address it in partially observable settings.
- Motivation: Independent reinforcement learning treats other agents as part of each learner’s local environment, which is non-stationary and non-Markovian.This removes convergence guarantees for many algorithms and can produce policies that overfit to training partners or opponents.
- Related challenges: Prior MARL methods commonly address adaptation through joint values, adaptive learning rates, update scheduling, or online responses to other agents’ actions.Much of this work focuses on repeated matrix games or fully observable environments, with limited coverage of general partially observable settings.
- Contributions: The paper introduces joint-policy correlation to quantify how independently learned policies depend on the policies encountered during training.It uses this metric to study overfitting and generalization in multiagent interaction.
- Contributions: The proposed MARL algorithm combines deep reinforcement learning for approximate best responses with empirical game-theoretic analysis for computing meta-strategy distributions.It assumes centralized training and decentralized execution, with separate neural networks and no shared gradients or architectures among agents.
- Contributions: A distributed decentralized form removes the centralized payoff table and requires less memory.This provides a scalable implementation of the general framework.
2 Background and Related Work
The background develops game-theoretic and reinforcement-learning foundations for policy-space methods, emphasizing empirical analysis when strategy spaces are too large to enumerate. It positions the paper as a unification and extension of existing algorithms, while noting scalability limits in classical approaches.
- Overview: The paper aims to unify related multiagent algorithms and terminology across research communities.Its background section presents the building blocks needed to describe the proposed approach alongside relevant prior work.
- Game-theoretic foundations: A normal-form game specifies players, their policy sets, and a payoff table over joint policies.Players may select individual policies or sample from mixtures, whose quality depends on the other players’ strategies.
- Game-theoretic foundations: Strategy-computation methods include linear programming, fictitious play, replicator dynamics, and regret minimization, with extensions to sequential games facing larger state spaces.Many sequential extensions have focused on two-player settings, while fictitious play also converges in potential games such as cooperative identical-payoff games.
- Double Oracle: Double Oracle iteratively solves a subgame, computes an equilibrium, and adds best responses to expand the restricted strategy set.The method is guaranteed to converge in two-player games, but may require enumerating the entire strategy space in the worst case.
- Limitations: Extensive-form extensions remain difficult because sequential games can have exponentially larger representations and suffer from the curse of dimensionality.Rock-Paper-Scissors illustrates that full strategy-space support may be necessary for an equilibrium, although support sizes can shrink in some games.
- Empirical game-theoretic analysis: Empirical game-theoretic analysis constructs smaller simulated games, records estimated utilities, and iteratively discovers strategies when full enumeration is prohibitively expensive.The empirical game is repeatedly analyzed as the simulation process continues.
- Deep reinforcement learning: The paper uses reinforcement learning to discover approximate rather than exact best responses, extending earlier empirical-game approaches with deep neural networks and more epochs.Approximate responses are computationally more feasible and can accommodate bounded-rationality settings.
- Deep reinforcement learning: Deep reinforcement learning supplies neural policies for decision-making, building on deep learning and reinforcement learning.Prior successes include learning from screenshots in Atari and navigation tasks and combining deep RL with Monte Carlo tree search in AlphaGo.
3 Policy-Space Response Oracles
PSRO builds a policy space by repeatedly computing approximate best responses to opponents’ meta-strategies, then uses meta-solvers to select among policies. Its general framework subsumes several established algorithms, while DCH provides a scalable parallel approximation with reduced space complexity.
- Policy-Space Response Oracles: PSRO generalizes Double Oracle and Fictitious Self-Play by treating policies as meta-game choices and allowing any meta-solver to compute new meta-strategies.Parameterized policies provide state-space generalization without domain knowledge.
- Policy-Space Response Oracles: Each PSRO epoch adds learned oracle policies to the policy sets, evaluates missing joint-policy utilities through simulation, and updates the empirical game.The process starts from initial policy sets and grows the empirical game as new policies are generated.
- Policy-Space Response Oracles: Approximate best responses are trained with deep reinforcement learning against policies sampled from opponents’ meta-strategies.With opponents fixed in a partially observable episodic environment, best-response computation reduces to an MDP.
- Policy-Space Response Oracles: Independent RL, iterated best response, fictitious play, and Double Oracle arise as PSRO instances under different opponent meta-strategy choices.The corresponding choices include a single latest policy, a previous policy, a uniform mixture, or a Nash equilibrium of the meta-game.
- Meta-Strategy Solvers: The framework uses regret-matching, Hedge, and projected replicator dynamics to produce meta-strategies from empirical games, with exploration guaranteeing a minimum policy-selection probability.Projected replicator dynamics directs exploration through projection onto an exploratory simplex rather than isotropic mutation.
- Deep Cognitive Hierarchies: PSRO’s reinforcement-learning step can take a long time to converge, and behavior learned in one epoch may need to be relearned when later epochs restart from scratch.Many epochs may also be needed for oracle policies to reason through deeper contingencies.
- Deep Cognitive Hierarchies: Deep Cognitive Hierarchies parallelize fixed levels of oracle learning, update meta-strategies online, and trade PSRO correspondence accuracy for scalability and lower asymptotic space complexity.DCH avoids explicitly storing the empirical payoff tensor and periodically refreshes locally stored policies and meta-strategies.
4 Experiments
Experiments evaluate joint-policy correlation in partially observable gridworlds and compare DCH, PSRO, and NFSP in Leduc Poker. DCH substantially reduces independent-learning overfitting, while PSRO/DCH trade some convergence precision for stronger performance against fixed opponents.
- Joint Policy Correlation: JPC matrices compare returns when policies trained together are paired on the diagonal with returns from separately trained policies off-diagonal.The matrices use D = 30.44 and O = 20.03 in one example, yielding R− = 0.342.
- Joint Policy Correlation: 34.2%: independently learned policies lose this average reward when paired with another independently learned policy in Laser Tag small2.The result demonstrates correlation effects even in a nearly fully observable coordination domain.
- Joint Policy Correlation: DCH reduces expected JPC loss on small2 to 5.5%, a 28.7% reduction relative to independent learners.As maps become larger and more partially observed, the average loss reaches 71.7%, while DCH’s reduction grows to 56.7%.
- Joint Policy Correlation: Using only the highest-level policy instead of the fully mixed meta-strategy produces larger JPC values, though reductions remain 19.5%, 36.5%, and 59.9% across small2–4.This comparison shows that execution-time meta-strategy mixing matters for reducing correlation.
- Joint Policy Correlation: 56.1%: level 5 reduces JPC on small4, nearly matching level 10’s 56.7% reduction, whereas level 3 achieves 44%.The results indicate diminishing benefit from increasing the number of levels in this comparison.
- Leduc Poker: In Leduc Poker, decoupled replicator dynamics performs best for minimizing NashConv, followed by decoupled regret matching and Exp3, with higher levels helping but diminishing returns.For exploitation, γ = 0.1 performs best, while meta-solvers have little effect.
- Leduc Poker: DCH and PSRO converge faster initially than NFSP, but NFSP later reaches lower exploitability while PSRO/DCH perform better against fixed players.The authors attribute the fixed-player advantage to oracle training that adapts to exploitable opponent behavior.
5 Conclusion and Future Work
The paper identifies joint policy correlation as a severe limitation of independent reinforcement learning and presents PSRO/DCH as producing more general policies across partially observable games.
- Joint policy correlation limits the generality of policies learned by independent reinforcement learners.
- PSRO/DCH produces general policies that significantly reduce JPC in partially observable coordination games.
- PSRO/DCH produces robust counter-strategies that safely exploit opponents in a competitive imperfect-information game.
- Future work: Future work includes maintaining oracle diversity, expanding response-graph methods and environments, and investigating opponent modeling and online adaptation.
Appendices
The appendices describe alternative meta-solvers, their game-theoretic dynamics, exploratory variants, and supporting implementation details for coordination-game and poker experiments.
- Regret matching: Regret matching updates cumulative policy regrets and normalizes their positive portions to produce a new meta-strategy.
- Hedge: Hedge accumulates policy rewards and applies a softmax function to derive the next strategy.
- Replicator dynamics: Replicator dynamics evolve strategy populations by comparing each strategy’s fitness with the population’s average fitness.
- Replicator dynamics: Asymmetric replicator dynamics allow players from different strategy populations when players do not share the same strategy sets.
- Exploration: The paper uses projected replicator dynamics with lower bounds on strategy probabilities to enforce exploration.
B.2 JPC in General n-player Environments
The general n-player formulation extends JPC to symmetric or asymmetric games with arbitrary rewards and scales estimation by sampling off-diagonal entries when necessary.
- The generalized JPC formulation applies to finite symmetric or asymmetric n-player games with arbitrary rewards.
- For d independent learning instances, each player’s utility tensor has dimensionality d^n, with entries representing expected utility for combinations of learned policies.
- A utility-tensor entry specifies the expected return for one player under a particular combination of policies drawn from the independent learning instances.
- For player i, diagonal and off-diagonal averages use d and d^n−d values respectively, with off-diagonal values estimable by sampling O(d) entries.
- In asymmetric games, JPC can differ across players, so the paper recommends reporting a vector containing each player’s proportional reduction.
C.1 Network, Oracle, and Training Parameters
The appendices specify Reactor-based architectures and training procedures for gridworld and Leduc poker, including alternating PSRO phases and parameter-sensitivity findings.
- Training parameters: The default training configuration uses λ = 0.9, LSTM unroll length 32, batch size 4, learning rate α = 0.0001, and a replay buffer of 500000.
- Network architecture: The main network follows the Reactor architecture without a behavior-distribution head, using memorized behavior probabilities for Retrace corrections.
- Gridworld: Gridworld uses three convolutional layers, a 32-unit fully connected layer, and 32-unit LSTM layers with concatenated ReLU processing.
- Leduc poker: Leduc poker alternates oracle best-response training with empirical payoff updates and meta-strategy learning, while including the currently training oracle in the policy set.
- Sensitivity: The algorithms were fairly robust to parameter changes, while learning rate was identified as the most important parameter.
- Gridworld: In first-person gridworld games, parameter values had little to no effect on outcomes.
- Experience processing: Turn-based poker training constructs player-specific experience tuples spanning the intervening steps until the same player acts again.
E Results
This section presents the experimental settings and visualizations used to evaluate DCH in gridworld coordination games and Leduc Poker. The figures examine maps, parameter effects, NashConv, and exploitation against benchmark opponents.
- NashConv: Figure 10 evaluates DCH parameter effects on NashConv in two-player Leduc Poker.
- Exploitation: Figure 11 evaluates DCH parameter effects on exploitation in two-player Leduc Poker.
- Opponent comparisons: Figures 12 and 13 compare exploitation against CFR500pure in two-player Leduc and random bots in three-player Leduc, respectively.
- Experimental settings: The experiments include gridworld games for gathering, field pathfinding, and merge, alongside two- and three-player Leduc Poker.The supplied materials list the game categories and provide map layouts for the gridworld settings.
E.1 Linear Regression Analysis to Interpret the Effect on DCH Parameters
The analysis uses ordinary least squares regression to examine how individual DCH parameter settings relate to exploitability and exploitation. The authors caution that the resulting effects describe removal from an aggregate prediction, not necessarily optimal parameter values.
- Analysis design: The analysis tests removing individual DCH settings, including γ, meta-solver, levels, update period, and learning rate, for exploitability and exploitation outcomes.
- Analysis design: Ordinary least squares predicts exploitability or exploitation from the parameter values using Statsmodels.
- Interpretation: The regression output estimates each setting’s effect on an overall prediction that includes all experimental data.
- Interpretation: The analysis does not necessarily identify the best value for each parameter because parameter values may combine through complex nonlinear effects.
- Findings: The authors report that meta-solver and level structure appear more influential for lowering NashConv in three-player than two-player Leduc.
E.2 CFR Exploitability in Leduc
This section reports vanilla CFR exploitability results for two-player and three-player Leduc Poker without abstractions. It also situates the values relative to the exact two-player equilibrium value and related exploitation evaluations.
- CFR results: The vanilla CFR convergence graph uses no abstractions.
- CFR results: Vanilla CFR’s NashConv at iteration 500 is 0.063591 for two-player Leduc and 0.194337 for three-player Leduc.
- Equilibrium reference: The exact two-player Leduc equilibrium value is −0.085606424078 for the first player, indicating a slight advantage for the second player.
- Related evaluations: The surrounding evaluations include DCH exploitation in two-player Leduc and comparisons against CFR500pure.
E.3 Computing the Explicit Meta-Policy for Exploitability in PSRO/DCH
PSRO and DCH represent meta-strategies as distributions over policies and convert them into explicit stochastic policies through information-state action weights. The section also reports regression analyses and comparisons involving meta-solvers, NashConv, and Leduc settings.
- Meta-policy construction: In PSRO and DCH, each meta-strategy σ_i is a distribution over the player’s policies, whose combination encodes a single stochastic policy.
- DCH evaluation: Figures 14 and 15 examine γ’s effect on overall NashConv and NashConv by meta-solver in two-player Leduc.
- Meta-policy construction: For each information state I, action weights sum policy reach probabilities multiplied by each policy’s meta-strategy probability and action probability.
- Meta-policy construction: The final stochastic policy is obtained from these information-state action weights, while opponent policies need not be included because they cancel during normalization.
- Regression analysis: The reported OLS analyses include AUC models for DCH in two-player and three-player Leduc, with R-squared values of 0.555 and 0.750.
- Regression analysis: Figure 16 presents regression-test outputs using a MAUC of NashConv over the most recent 128 values.
- CFR evaluation: Figure 17 reports vanilla CFR NashConv values for two-player and three-player Leduc.