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.

本文提出了一种名为“Exploitability Descent”的新算法，通过直接针对最坏情况的对手进行策略优化，计算具有不完全信息的两人零和博弈的近似均衡。我们证明，当遵循此优化时，玩家策略的可利用性会渐近地收敛于零，因此当两个玩家同时使用此优化时，联合策略会收敛于纳什均衡。与虚拟实现（XFP）和反事实后悔（CFR）不同，我们的收敛结果涉及到被优化的策略而不是平均策略。我们的实验在纸面上就达到了XFP和CFR相当的收敛速率，利用函数逼近，我们发现我们的算法在两个游戏中优于纸面情况，这是在此类算法中不完全信息游戏中的首个结果。

使用利用率下降算法计算序列对抗游戏的近似均衡