acceptodds
Under review as a conference paper at ICLR 2027

Tight worst case for the double oracle algorithm

Abstract

The double oracle algorithm (DO) is an iterative algorithm that computes a mixed-strategy Nash equilibrium of a game without fully expanding the players' strategy spaces. It is the basis of Policy-Space Response Oracles (PSRO) and many related population-based methods for multiagent reinforcement learning, where each iteration trains a new policy. In this paper, we give a general, explicit construction that maximizes the number of iterations DO needs to converge. Specifically, for all integers , we give an explicit -by- matrix that forces DO, starting from the first row and column, to run for iterations. This equals the trivial worst-case upper bound. DO does not specify how to choose among multiple Nash equilibria or best responses, and our construction works for every choice. It also works when the equilibrium and best-response oracles are inexact, as in PSRO, provided they are sufficiently accurate. To our knowledge, this is the first such general construction. We formalize these results in Lean.

Primary area:
reinforcement learning
Keywords:
game theory, double oracle, game solving, Nash equilibrium

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_5k8TOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper constructs explicit M×NM\times N zero-sum games on which Double Oracle requires exactly M+N−2M+N-2 strategy expansions from a specified initialization, regardless of equilibrium or best-response selection. This matches the standard upper bound.

Critical strengths
  • The construction establishes a tight worst-case bound for arbitrary matrix dimensions.
  • Independence from selection rules strengthens the result beyond examples relying on adversarial tie-breaking.
  • The analysis explicitly quantifies robustness to oracle errors.
Critical weaknesses
  • Preserving the full worst-case path in highly rectangular games requires exponentially accurate best responses, limiting its relevance to practical PSRO.
  • The bound concerns exact termination. On this construction, a fixed-tolerance approximate equilibrium can be reached substantially earlier, so the result does not establish comparable difficulty for approximate solution.
  • A more explicit account of the trade-off between oracle accuracy, target exploitability, and required strategy expansions would strengthen the practical interpretation.
Questions for authors

please see the weaknesses

Reviewer_mo2AOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the worst-case iteration complexity of the Double Oracle (DO) algorithm for two-player zero-sum normal-form games. For every M,N≥2M,N\ge2, it constructs an explicit payoff matrix that forces DO to take exactly M+N−2M+N-2 iterations starting from a prescribed singleton initialization. This matches the trivial upper bound. The construction combines a staircase component with a Fibonacci-based component that forces the remaining strategies to enter sequentially. The result holds independently of equilibrium and best-response selection. The paper also quantifies when this trajectory persists under sufficiently accurate approximate equilibrium and best-response oracles.

Critical strengths

The paper provides a precise and general characterization of the worst case. The construction covers every rectangular dimension, including highly asymmetric games, and attains the exact upper bound under every selection rule from the specified initialization. Forcing strategies to enter one at a time even after the smaller strategy set has been exhausted is a nontrivial feature of the construction.

Critical weaknesses

My main concern is the significance of the improvement over existing lower bounds. Zhang and Sandholm (2024) already establish worst-case behavior for DO, including results independent of adversarial tie-breaking and lower bounds for approximate-equilibrium computation. This paper's distinctive contribution is therefore the exact M+N−2M+N-2 count across all rectangular dimensions. This is a clean and technically nontrivial refinement. However, when complexity is measured against the number of pure strategies, the square-case improvement is primarily in the exact iteration count rather than its asymptotic order.

The paper clearly distinguishes its contribution from prior work and provides additional robustness and structural results. My concern is whether these advances collectively offer a sufficiently substantial conceptual contribution, rather than whether the comparison with prior work is accurate. In particular, I remain uncertain whether the rectangular extension and exact characterization substantially change our understanding of DO or its implications for learning algorithms.

Questions for authors
  1. Section 3 clearly distinguishes the exact, rectangular worst-case characterization from prior lower bounds. Beyond this sharpening, what qualitative takeaway about DO/PSRO behavior do the authors consider the main conceptual advance?

  2. Appendix C.2 explains why ADO bypasses the long corridor through the structure of the columns tight against the optimal row distribution. Is this advantage mainly specific to the construction, or does the argument suggest conditions under which ADO avoids full expansion on a broader class of games? A brief discussion would help clarify the scope of this insight.

Reviewer_XANYOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper gives an explicit M-by-N zero-sum matrix game for every M,N >= 2 on which Double Oracle, initialized with the first row and column, takes exactly M+N-2 expansion steps under every equilibrium and best-response selection rule. The construction has a staircase phase and a Fibonacci-based corridor. The paper also analyzes oracle tolerances, perturbations, and the duality gap, and provides a Lean formalization. Proposition 2 gives a square construction with a pure equilibrium and a constant preterminal gap.

Critical strengths
  1. The main theorem exactly matches the trivial expansion-step upper bound for arbitrary rectangular dimensions and is robust to all selection rules from the prescribed initial state.

  2. The equilibrium certificates, gap formulas, and oracle-accuracy analysis make the mechanism and scope of the construction checkable.

  3. The square construction in Proposition 2 is especially informative because it has a pure final equilibrium while still forcing inefficient strategy discovery.

Critical weaknesses
  1. The lower-bound construction does not establish hardness for a full-support mixed equilibrium. In particular, the constant-gap construction in Proposition 2 terminates at a pure (single-support) equilibrium; omitting the last row or column leaves an exploitable gap that the terminal strategy can remove. Thus exhaustive expansion here is tied to the prescribed singleton initialization and the requirement of exact termination, rather than to the need to discover all strategies in a full-support equilibrium. The paper should state this limitation explicitly and avoid presenting the result as a general full-support lower bound.

  2. The significance of the exact-count refinement should be positioned more sharply relative to the full-support examples and the exponential lower bounds of Zhang and Sandholm (2024). The result is precise, but the broader statement that exact DO may exhaust the strategy space is not itself new.

  3. The general rectangular construction has limited implications for fixed-accuracy solving: its corridor gaps shrink rapidly and maintaining the full path requires increasingly accurate oracles. The more practically relevant constant-gap Proposition 2 is underemphasized, and its sensitivity to approximate best responses and alternative initialization is not fully developed.

Questions for authors
  1. The main theorem shows that exact DO convergence can require expanding every entry, but a simple full-support Nash-equilibrium construction can also achieve this condition. For every rectangular shape M × N, can the authors construct a game and a prescribed initial singleton pair such that DO follows a full-length run while the duality gap remains bounded below by a positive constant independent of M and N at every preterminal iterate? If not, what is the strongest dimension-dependent lower bound on the minimum preterminal gap achieved by the proposed construction?

  2. Can the authors clearly distinguish full strategy inclusion, the exact worst-case expansion count, and fixed-accuracy approximation complexity, and state that Proposition 2 is a single-support construction?

  3. Can Proposition 2 and its approximation implications be made more prominent, including oracle-error sensitivity and random singleton initialization? What conclusion remains for fixed target gap and fixed oracle tolerance as the dimensions grow?

Comments on the paper

3 comments

We thank the reviewers. All three agree that, from the first row and column, our matrix forces the trivial bound of M+N−2M + N - 2 iterations, for every shape and every selection rule. None raises a concern about soundness.

Fixed accuracy (XANY, 5k8T). Our results give a dichotomy. It is also the main conceptual advance that mo2A asks about. At exact termination, DO's worst case is M+N−2M + N - 2 (Theorem 1). If DO instead stops once the duality gap is at most a fixed τ\tau, its worst case does not grow with the larger dimension, yet still reaches the trivial bound when M=NM = N. Propositions 1 and 2 in Appendix B, which we have moved into the body and extended, show this.

  • For M=NM = N, the matrix of Proposition 2 forces all 2M−22 M - 2 iterations while the duality gap stays arbitrarily close to its maximum, 22.
  • For M<NM < N, the argument of Proposition 1 gives a cap that does not depend on NN. At stopping tolerance τ\tau, DO takes at most M−2+(1+2/τ)MM - 2 + (1 + 2 / \tau)^M iterations on every M×NM \times N matrix with entries in [−1,1][-1, 1].

Whether the full count survives a fixed tolerance for M<N≤(1+2/τ)MM < N \leq (1 + 2 / \tau)^M is open (Open Problem 2). Our main matrix needs exponentially small tolerances there.

Full support (XANY). For M=NM = N, our main matrix has a unique, fully mixed equilibrium, and its strategies still enter one at a time. Full support alone gives much less. It does not force one new strategy per iteration. At fixed accuracy τ\tau, it forces at most O(log⁡(MN)/τ2)O(\log(M N) / \tau^2) strategies (Lipton and Young, 1994). For M<NM < N, our main matrix makes DO add N−MN - M columns that its unique equilibrium never uses.

Prior work (XANY, mo2A). Zhang and Sandholm (2024) have two bounds that hold under every selection rule. One follows from support alone, since every equilibrium there has support exponential in the game's size (their Theorem 3.1). The other reaches at most half the trivial bound, at a constant gap (their Theorem 3.2). For M=NM = N, the matrix of our Proposition 2 forces all 2M−22 M - 2 iterations at a constant gap. Our main matrix forces the trivial bound under every rule, for every shape, and so does every nearby matrix (our Corollary 2).

Revision. We have uploaded a new version of the paper that uses the extra page for the new statements, with proofs in the appendix. The main theorem and its statement in Lean are unchanged.

  1. Propositions 1 and 2 move into Section 5. Proposition 1 gains the cap above. Proposition 2 gains its oracle tolerances and a bound for random starts. We also state that it ends at a pure equilibrium.
  2. A paragraph separates the inclusion of every strategy, the exact count, and fixed accuracy.
  3. Section 3 sharpens the comparison with Zhang and Sandholm.
  4. A summary shows how the stopping tolerance and the oracle tolerances bound the number of forced iterations.
  5. Appendix C.2 gives the general form of the argument for Anytime Double Oracle (ADO).
  6. The introduction states the main takeaways.

We checked the new claims on Proposition 2's matrix exactly, over every equilibrium and best response, for small MM. We have included these checks in the supplement.

AuthorsOpenReview ↗

New result on Open Problem 4: a compact game that forces the trivial bound

We have uploaded one more revision. It resolves Open Problem 4 of the submission. That problem asked whether some game of size poly(k)\mathrm{poly}(k) has our matrix with M=N=2kM = N = 2^k as its reduced normal form.

POSGs. For partially-observable stochastic games, the answer is yes (Proposition 3, Appendix A.7). In our POSG, each player picks the bits of its index, one per stage, and observes nothing. A three-label automaton reads the bits and computes the payoff. Counting the stage, the game has 3k+13 k + 1 states. Hence, DO on this POSG, started from the all-zero strategies, takes all 2k+1−22^{k+1} - 2 iterations under every selection rule, exponentially many in the size of the game. So a compact game can force DO to reach the trivial bound. None of Zhang and Sandholm's theorems shows this (Section 3). The oracles must still be exponentially accurate in kk (Theorem 3).

EFGs. For extensive-form games, the answer is no. The reduced normal form of an EFG has rank at most its number of leaves, while our square matrix has full rank. So every EFG with our matrix as its reduced normal form has at least 2k2^k leaves. This also holds for the payoffs aAij+ba A_{ij} + b with a>0a > 0, which DO treats exactly as our matrix. Zhang and Sandholm's extensive-form bounds require adversarial tie-breaking. Open Problem 4 now asks whether some family of two-player zero-sum EFGs of size poly(k)\mathrm{poly}(k) forces DO, from some initial state, to take 2Ω(k)2^{\Omega(k)} iterations.

Changes. Appendix A.7 states and proves Proposition 3, and the conclusion and Section 3 point to it. In Lean, we prove that the automaton computes our matrix, so DO on its payoffs has the paths of the main theorem. We also prove the rank bound (Table 3). The POSG and EFG models themselves are not formalized. The main theorem and its statement in Lean are unchanged, and the body still fits in ten pages.

AuthorsOpenReview ↗

Second new result: a matrix that forces Anytime Double Oracle's worst case (Proposition 4)

We have uploaded another revision, with a second new result. It concerns Anytime Double Oracle (ADO), the first variant in Open Problem 6 of the submission. It also completes our answer to mo2A's Q2.

A matrix that forces ADO's worst case. Our main matrix does not force ADO's worst case once N>M+2N > M + 2 (Appendix C.2). Another matrix does (Proposition 4, Appendix A.8). Pad the square staircase with N−MN - M columns whose entries all equal a constant cc, positive and at most the staircase's value. Then every path of ADO from the first row and column, on it and on its negative transpose, takes all M+N−2M + N - 2 iterations. Once every row is present, ADO's row mixture is optimal, and every padding column pays exactly cc, the value of the padded game, against it. So ADO, which adds a novel best response whenever there is one, adds the padding columns one at a time. That relies on this preference (Proposition 4, part 2). If ADO's oracles may return a best response already present, some path stops after one iteration, short of an equilibrium. Another stops at an equilibrium within 2M−12 M - 1 iterations, fewer than M+N−2M + N - 2 if N≥M+2N \geq M + 2.

When ADO avoids full expansion (mo2A, Q2). Our reply showed that, once one population is complete, ADO adds only strategies tight against an optimal strategy. So it avoids full expansion if some strategy still missing at that point is tight against no optimal strategy. This happens on our main matrix once N>M+2N > M + 2, and on nondegenerate games once more than min⁡(M,N)\min(M, N) strategies are missing at that point. The padded matrix makes every missing column tight, and ADO then expands it fully.

Changes. Appendix A.8 states and proves Proposition 4, and Appendix C.2 and the conclusion point to it. Open Problem 6 now asks only about Online Double Oracle. Proposition 4 is proved in Lean (Table 3), and the supplement's code/variants.py now checks every path of ADO exactly. The main theorem and its statement in Lean are unchanged, and the body still fits in ten pages.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.