Exponential Lower Bounds on the Double Oracle Algorithm in Zero-Sum Games

Brian Hu Zhang, Tuomas Sandholm

Abstract

The double oracle algorithm is a popular method of solving games, because it is able to reduce computing equilibria to computing a series of best responses. However, its theoretical properties are not well understood. In this paper, we provide exponential lower bounds on the performance of the double oracle algorithm in both partially-observable stochastic games (POSGs) and extensive-form games (EFGs). Our results depend on what is assumed about the tiebreaking scheme—that is, which meta-Nash equilibrium or best response is chosen, in the event that there are multiple to pick from. In particular, for EFGs, our lower bounds require adversarial tiebreaking, whereas for POSGs, our lower bounds apply regardless of how ties are broken.

Introduction

The Double Oracle (DO) algorithm, and its deep-learning extension Policy Space Response Oracles (PSRO), has become a cornerstone of modern algorithmic game theory. By iteratively expanding a restricted set of strategies with best responses, it has successfully tackled complex domains like StarCraft II and Stratego. Despite its empirical success, the theoretical efficiency of DO remained largely uncharacterized. This work provides a theoretical "reality check" by establishing the first exponential lower bounds for DO in zero-sum games, demonstrating that the algorithm can be forced into an exponential number of iterations even in games with simple structures.

Methodology: Constructing the "One-at-a-Time" Trap

The core of the proof lies in constructing games where the best response only provides marginal progress toward the Nash equilibrium. The authors introduce the "n-bigger-number" game, where players choose numbers and the best response to any strategy set is simply the current maximum plus one. This forces DO to crawl through the strategy space linearly rather than leaping toward an equilibrium.

To extend this to standard game representations, these numerical games are mapped onto Partially-Observable Stochastic Games (POSGs) and Extensive-Form Games (EFGs). Using only $O(k)$ states, the authors represent a strategy space of size $2^k$, effectively hiding the exponential complexity within a compact game description.

Figure 1: POSG construction mapping numerical strategies to a state-machine representation.

Key Results and Tiebreaking Analysis

The research reveals a hierarchy of lower bounds based on game properties and tiebreaking assumptions. In POSGs, the exponential slowdown persists even with random initialization and non-adversarial choices. In contrast, for EFGs—specifically tree-form games—the lower bounds often rely on "adversarial tiebreaking," where the environment selects the least helpful best response among multiple candidates.

Figure 6: Summary of lower bounds and theoretical properties across different game classes.

As summarized in Table 1 (Figure 6), Theorem 3.2 establishes that for a POSG with $O(k)$ states, DO requires $\Theta(2^k)$ iterations to reach an $\epsilon$-equilibrium. Theorem 3.5 shows that even in fully-observable tree-form games, DO can be forced into $2^{k-1}$ iterations under adversarial tiebreaking. These results highlight that while DO might find an approximate equilibrium quickly in some cases, reaching high-precision equilibria is where exponential complexity becomes a bottleneck.

Discussion and Future Work

While these results highlight the worst-case limitations of the Double Oracle framework, they do not negate its practical utility. The gap between these theoretical lower bounds and the "average-case" efficiency seen in practical applications remains an open area for research. Future work may explore "$\alpha$-Double Oracle" variants that require a minimum improvement threshold for new strategies, potentially bypassing the "crawling" behavior identified in this study.

Summary updated

Abstract

The double oracle algorithm is a popular method of solving games, because it is able to reduce computing equilibria to computing a series of best responses. However, its theoretical properties are not well understood. In this paper, we provide exponential lower bounds on the performance of the double oracle algorithm in both partially-observable stochastic games (POSGs) and extensive-form games (EFGs). Our results depend on what is assumed about the tiebreaking scheme---that is, which meta-Nash equilibrium or best response is chosen, in the event that there are multiple to pick from. In particular, for EFGs, our lower bounds require adversarial tiebreaking, whereas for POSGs, our lower bounds apply regardless of how ties are broken.
BibTeX
@inproceedings{zhang2024exponential,
  author = {Brian Hu Zhang and Tuomas Sandholm},
  title = {{Exponential Lower Bounds on the Double Oracle Algorithm in Zero-Sum Games}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=qPFEo5BD5S},
}
Figure