Computing Approximate Equilibria in Sequential Adversarial Games by Exploitability Descent

By Edward Lockhart, Marc Lanctot, Julien Pérolat, Jean-Baptiste Lespiau, Dustin Morrill, Finbarr Timbers, Karl Tuyls. 2019

93 citations recorded by the source corpus.

In this paper, we present exploitability descent, a new algorithm to compute approximate equilibria in two-player zero-sum extensive-form games with imperfect information, by direct policy optimization against worst-case opponents. We prove that when following this optimization, the exploitability of a player's strategy converges asymptotically to zero, and hence when both players employ this optimization, the joint policies converge to a Nash equilibrium. Unlike fictitious play (XFP) and counterfactual regret minimization (CFR), our convergence result pertains to the policies being optimized rather than the average policies. Our experiments demonstrate convergence rates comparable to XFP and CFR in four benchmark games in the tabular case. Using function approximation, we find that our algorithm outperforms the tabular version in two of the games, which, to the best of our knowledge, is the first such result in imperfect information games among this class of algorithms.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning, Game & Decision Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Sergey Levine
2. Zhuoran Yang
3. Pieter Abbeel
4. Yuxi Li
5. Yoshua Bengio
6. Kaiqing Zhang
7. Tamer Basar
8. R´emi Munos

In Management Science and Operations Research

1. Zhuoran Yang
2. Kaiqing Zhang
3. Tamer Basar
4. Marc Lanctot
5. Julien Pérolat
6. Karl Tuyls
7. Pablo Hernandez-Leal
8. Matthew E. Taylor

In Reinforcement Learning

1. Zhuoran Yang
2. Karl Tuyls
3. R´emi Munos
4. Pablo Hernandez-Leal
5. Kaiqing Zhang
6. Tamer Basar
7. Sergey Levine
8. Julien Pérolat

In Game & Decision Theory

1. Karl Tuyls
2. Zhuoran Yang
3. Julien Pérolat
4. Tamer Basar
5. Kaiqing Zhang
6. Marc Lanctot
7. Jean-Baptiste Lespiau
8. R´emi Munos

Citations in the corpus

• OpenSpiel: A Framework for Reinforcement Learning in Games (2019, background): “There have been recent efforts to harmonize the terminology and make useful associations among algorithms between computational game theory and reinforcement learning [66, 38, 32], so we base our terminology on classical concepts and these recent papers.”
• A survey and critique of multiagent deep reinforcement learning (2018, methodology): “The result is also used to support policy gradient optimization against worst-case opponents, in a new algorithm called Exploitability Descent [137].”
• Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, methodology): “Moreover, [298] proposes a policy optimization method known as exploitability descent, where the policy is updated using actor-critic, assuming the opponent plays the best counter-policy.”
• From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization (2020, methodology): “, 2018) empirically show a convergence in time-average without formal proof, and (Lockhart et al., 2019) require the exact computation of a best response.”
• Neural Replicator Dynamics (2019, methodology): “These include approaches relying on self-play [23], regret minimization [9, 10, 12, 34, 43, 69], and a large body of works that assume a standard centralized learning, decentralized execution paradigm [18, 35, 44, 51].”