A new benchmark finds policy gradients beat game-theory algorithms
A benchmark presented at ICLR by MIT researchers and collaborators finds that policy gradient methods, a general-purpose family of reinforcement learning tools that date to the early 1990s, can outperform specialized game-theory algorithms in two-player zero-sum imperfect-information games. The result, the source reports, is less about policy gradients as a class and more about a long-standing evaluation gap: the field had assumed specialized algorithms were better suited, but had not built the engineering scaffolding to verify that assumption at scale. The benchmark itself, the authors say, is the actual contribution.
The metric the team uses is exploitability, a measure of how far a strategy is from optimal play against a worst-case opponent that knows the player's full policy. A zero on this scale would mean perfect play, and a high score means a player has many exploitable weaknesses. The team ran the benchmark on five two-player zero-sum games with imperfect information: two variants of Phantom Tic-Tac-Toe, in which players cannot see their opponent's moves; two imperfect-information variants of Hex; and Liar's Dice. The full game trees can reach roughly 30 billion states, including the full history of moves and counterfactuals, which is two to three orders of magnitude larger than the settings in which exploitability was typically measured before this work.
The 30-billion-state scale is where the paper makes its central technical claim. The source says previous researchers generally used exploitability on games roughly 100,000 times smaller, which made the technique both tractable and easy to misapply. Running it on games of this size required both new computational tooling and a careful accounting of what exploitability actually measures, since the worst-case adversary assumes a known target policy, not a hidden one. That detail matters when reading the result: the benchmark grades strategies under an idealized worst case, not against an opponent with the same information the player has.
In the experiments described in the source, neural networks trained with policy gradient algorithms produced lower exploitability scores than networks trained on game-theory-based algorithms across the five games. In a follow-up head-to-head round, the policy-gradient-trained networks also beat their game-theory-trained opponents directly. The authors frame both as confirmation that the benchmark works, not as a final verdict on which algorithm class is intrinsically better. Co-author Samuel Sokota of Carnegie Mellon, in the source, raises a sociological question worth holding onto: the field had taken specialized game-theory algorithms as the right tool largely because the engineering work to evaluate them rigorously had not been done.
What the benchmark does not establish is the next-order question, which is whether policy gradient methods will keep this advantage in richer, larger, or non-zero-sum settings, or when the opponent is another learning agent rather than a worst-case adversary with full knowledge. The five games are a narrow slice of imperfect-information settings, and three of them are obscure recreational games that the source itself acknowledges. The broader applicability claims in the source, from military operations to trading scenarios to negotiations, are framed as the kinds of strategic interactions policy gradient methods could eventually inform, not as settings the benchmark has been validated on.
The team has made the benchmark available as an addition to OpenSpiel, a commonly used collection of game-based reinforcement learning software, and says it can run on an ordinary laptop for these problem sizes. That accessibility is a real engineering contribution, because the original exploitability calculations for games this size were a bottleneck in the literature rather than a routine step. Whether outside teams reproduce the policy-gradient lead on independent implementations is a separate question, and the source does not present external replication data.
Ian Gemp, a game-theory researcher at Google DeepMind who was not involved in the study, is quoted in the source as finding the result encouraging and a reminder that modernizing classical tools remains a productive research path. That framing is useful because it puts the result in a measured context: this is a benchmarking paper and a methodological argument, not a single definitive ranking of algorithmic classes. The deeper question the paper raises is what other algorithm comparisons in reinforcement learning would change if the same engineering discipline were applied to them.
The paper's contribution is the benchmark, not a final ranking of algorithm classes. The exploitability advantage for policy gradient methods, the source says, holds in head-to-head play and worst-case analysis on five specific games. Whether the same lead extends to non-zero-sum settings, larger games, and adversarial training against other learning agents is the next comparison the benchmark framework does not yet include.