Computing Approximate Equilibria in Sequential Adversarial Games by Exploitability Descent
Edward Lockhart1 Marc Lanctot1 Julien Pérolat1 Jean-Baptiste Lespiau1 Dustin Morrill1,2 Finbarr Timbers1 Karl Tuyls1 1DeepMind 2University of Alberta, Edmonton, Canada {locked, lanctot, perolat, jblespiau, dmorrill, finbarrtimbers,
Abstract
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, when using counterfactual values, 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.
中文速览
双人零和不完全信息博弈（imperfect information game）中，经典算法CFR和虚拟博弈（XFP）只能保证"平均策略"收敛到纳什均衡，而不是当前正在优化的策略本身，这给函数近似等实际应用带来了不便。本文提出"可利用性下降"算法（Exploitability Descent, ED）：每轮迭代先为每位玩家计算针对对手策略的最优应答（best response），再利用反事实值（counterfactual values）对当前策略直接做梯度上升并投影回策略空间，使策略逐步降低自身的可利用性（exploitability）。理论上可以证明，这样优化的策略本身——而非其历史平均——会渐近收敛至纳什均衡，这是同类算法中的首次结果。实验表明，在四个基准博弈的表格（tabular）设置下，ED的收敛速度与CFR和XFP相当；更重要的是，引入神经网络函数近似后，ED在其中两个游戏上超越了纯表格版本，据作者所知这是不完全信息博弈此类算法中函数近似带来性能提升的首个实证，为将深度学习与博弈论求解器结合提供了新的理论支撑和实践路径。
原文 arXiv:1903.05614;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1903.05614v4