# Solving Common-Payoff Games with Approximate Policy Iteration

arXiv: https://arxiv.org/abs/2101.04237 · HTML: https://mlsanity.com/paper/2101.04237/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 80 references that are in the map.
- First posted on arXiv 11 Jan 2021.

## Builds on (most cited first, 27 of 27)

- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (2017)
- [Value-Decomposition Networks For Cooperative Multi-Agent Learning](https://mlsanity.com/paper/1706.05296/) (2017)
- [Deep Recurrent Q-Learning for Partially Observable MDPs](https://mlsanity.com/paper/1507.06527/) (2015)
- [Cooperative Inverse Reinforcement Learning](https://mlsanity.com/paper/1606.03137/) (2016)
- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- [The Complexity of Decentralized Control of Markov Decision Processes](https://mlsanity.com/paper/1301.3836/) (2013)
- [OpenSpiel: A Framework for Reinforcement Learning in Games](https://mlsanity.com/paper/1908.09453/) (2019)
- [Multi-Agent Cooperation and the Emergence of (Natural) Language](https://mlsanity.com/paper/1612.07182/) (2016)
- [Expectation Propagation for approximate Bayesian inference](https://mlsanity.com/paper/1301.2294/) (2013)
- [Combining Deep Reinforcement Learning and Search for Imperfect-Information Games](https://mlsanity.com/paper/2007.13544/) (2020)
- [DESPOT: Online POMDP Planning with Regularization](https://mlsanity.com/paper/1609.03250/) (2016)
- [Bayesian Action Decoder for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1811.01458/) (2018)
- [Simplified Action Decoder for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1912.02288/) (2019)
- [Online Planning Algorithms for POMDPs](https://mlsanity.com/paper/1401.3436/) (2014)
- [Safe and Nested Subgame Solving for Imperfect-Information Games](https://mlsanity.com/paper/1705.02955/) (2017)
- [Human-Level Performance in No-Press Diplomacy via Equilibrium Search](https://mlsanity.com/paper/2010.02923/) (2020)
- [Rethinking Formal Models of Partially Observable Multiagent Decision Making](https://mlsanity.com/paper/1906.11110/) (2019)
- [Improving Policies via Search in Cooperative Partially Observable Games](https://mlsanity.com/paper/1912.02318/) (2019)
- [Multi-Agent Common Knowledge Reinforcement Learning](https://mlsanity.com/paper/1810.11702/) (2018)
- [Learning to Play No-Press Diplomacy with Best Response Policy Iteration](https://mlsanity.com/paper/2006.04635/) (2020)
- [Monte Carlo Continual Resolving for Online Strategy Computation in Imperfect Information Games](https://mlsanity.com/paper/1812.07351/) (2018)
- [Online Planning for Decentralized Stochastic Control with Partial History Sharing](https://mlsanity.com/paper/1908.02357/) (2019)
- [Team Optimal Control of Coupled Subsystems with Mean-Field Sharing](https://mlsanity.com/paper/2012.01418/) (2020)
- [Reinforcement Learning in Decentralized Stochastic Control Systems with Partial History Sharing](https://mlsanity.com/paper/2012.02051/) (2020)
- [Structural Results and Explicit Solution for Two-Player LQG Systems on a Finite Time Horizon](https://mlsanity.com/paper/1303.3256/) (2013)

## Built on by (most cited first, 15 of 15)

- [Student of Games: A unified learning algorithm for both perfect and imperfect information games](https://mlsanity.com/paper/2112.03178/) (2021)
- [Multi-Agent Training beyond Zero-Sum with Correlated Equilibrium Meta-Solvers](https://mlsanity.com/paper/2106.09435/) (2021)
- [Common Information based Approximate State Representations in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2110.12603/) (2021)
- [A Marriage between Adversarial Team Games and 2-player Games: Enabling Abstractions, No-regret Learning, and Subgame Solving](https://mlsanity.com/paper/2206.09161/) (2022)
- [Abstracting Imperfect Information Away from Two-Player Zero-Sum Games](https://mlsanity.com/paper/2301.09159/) (2023)
- [Combining Tree-Search, Generative Models, and Nash Bargaining Concepts in Game-Theoretic Reinforcement Learning](https://mlsanity.com/paper/2302.00797/) (2023)
- [Public Information Representation for Adversarial Team Games](https://mlsanity.com/paper/2201.10377/) (2022)
- [The Update-Equivalence Framework for Decision-Time Planning](https://mlsanity.com/paper/2304.13138/) (2023)
- [Optimally Solving Simultaneous-Move Dec-POMDPs: The Sequential Central Planning Approach](https://mlsanity.com/paper/2408.13139/) (2024)
- [Adversarial Attacks in Cooperative AI](https://mlsanity.com/paper/2111.14833/) (2021)
- [Self-Explaining Deviations for Coordination](https://mlsanity.com/paper/2207.12322/) (2022)
- [Configurable Mirror Descent: Towards a Unification of Decision Making](https://mlsanity.com/paper/2405.11746/) (2024)
- [How Can Creativity Occur in Multi-Agent Systems?](https://mlsanity.com/paper/2111.14310/) (2021)
- [Automated Approach for Solving Infinite-state Polynomial Reachability Games](https://mlsanity.com/paper/2605.10169/) (2026)
- [Towards Learning Representations of Policies in Two-Player Zero-Sum Imperfect-Information Games](https://mlsanity.com/paper/2607.01498/) (2026)

## Abstract (arXiv)

For artificially intelligent learning systems to have widespread applicability in real-world settings, it is important that they be able to operate decentrally. Unfortunately, decentralized control is difficult -- computing even an epsilon-optimal joint policy is a NEXP complete problem. Nevertheless, a recently rediscovered insight -- that a team of agents can coordinate via common knowledge -- has given rise to algorithms capable of finding optimal joint policies in small common-payoff games. The Bayesian action decoder (BAD) leverages this insight and deep reinforcement learning to scale to games as large as two-player Hanabi. However, the approximations it uses to do so prevent it from discovering optimal joint policies even in games small enough to brute force optimal solutions. This work proposes CAPI, a novel algorithm which, like BAD, combines common knowledge with deep reinforcement learning. However, unlike BAD, CAPI prioritizes the propensity to discover optimal joint policies over scalability. While this choice precludes CAPI from scaling to games as large as Hanabi, empirical results demonstrate that, on the games to which CAPI does scale, it is capable of discovering optimal joint policies even when other modern multi-agent reinforcement learning algorithms are unable to do so. Code is available at https://github.com/ssokota/capi .