acceptodds
Under review as a conference paper at ICLR 2027

Perturbed Meta-Solvers Escape the Worst Case of Double Oracle

Abstract

Double oracle (DO) and policy-space response oracles (PSRO) target zero-sum games too large to solve directly. They grow a population of strategies: each round solves the meta-game, the payoff matrix of the current population against itself, and appends a full-game best response to the resulting equilibrium. The best response is the expensive step, so the round count is the cost; three failures inflate it. First, on a family of depth-two games with chance states, DO needs rounds when both the meta-game equilibrium and the best-response ties are chosen adversarially, and whether the bound survives removing either choice is open. Second, the meta-game is estimated from noisy simulations, and the exact-Nash meta-solver is a discontinuous function of it. Third, anchoring each round's meta-solution to the previous round's, the meta-level analogue of a standard stabilizer, freezes it: strategies added since receive zero anchor mass. We show that a single mechanism addresses all three failures: perturb the meta-solver, replacing exact Nash by an anchored quantal-response equilibrium (QRE), the saddle point of the meta-game payoff penalized by times the KL divergence from an anchor, where is the temperature and the anchor mixes the previous round's meta-solution with the uniform distribution. Below a mild problem-dependent cap on , the perturbed meta-solver collapses this worst case from to at most rounds even under fully adversarial tie-breaking, given exact QRE solves and best-response oracles. An anchor of mass tolerates inverse-polynomial oracle error and extends the escape to every rule for selecting among the meta-game's equilibria. The same anchor restores a mass floor and a quality-bounded termination that repair the anchoring deadlock. The meta-solution becomes -Lipschitz in the estimated meta-game, which gives finite-sample bounds on the terminal exploitability under noisy meta-game payoffs; the temperature trades terminal bias against per-round stability, a trade we treat as a direction-only heuristic. Pre-registered experiments confirm the theory: the adversarial replay is exactly exponential while the perturbed solver escapes within five rounds, every removes the deadlock on all seeds, and all terminal-bound runs satisfy the bound. Against regularized replicator dynamics and -mixed Nash, fixed in advance, the anchored QRE has the lower exploitability AUC in noisy cells each.

Primary area:
reinforcement learning
Keywords:
Policy Space Response Oracles, Multi-Agent Reinforcement Learning, Quantal Response Equilibrium, Algorithmic Game Theory

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_a3Y4OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the effect of changing the meta-solver in double oracle and PSRO. The authors propose to use an anchored quantal-response equilibrium (QRE), where the anchor mixes the previous meta-solution with a uniform distribution.

The main theoretical result shows that this approach reduces the exponential worst-case number of rounds to O(k) on a particular family of zero-sum games, even under adversarial tie-breaking. The paper also analyzes why anchoring only to the previous solution causes deadlock, and establishes stability and finite-sample guarantees under noisy meta-game payoffs. Experiments on several games support the theoretical results and compare the proposed method with existing meta-solvers. The results are generally encouraging, although the method does not consistently outperform simpler alternatives.

Critical strengths
  1. This paper has a clear and interesting theoretical result. The strongest contribution is showing that a relatively simple change to the meta-solver can avoid a difficult known construction. The case of adversarial best-response tie-breaking makes it more interesting.

  2. The experimental analysis are relatively careful.

Critical weaknesses
  1. The theoretical guarantee is narrow. The O(k) bound applies to a particular lower-bound construction and assumes exact QRE computation and exact best responses. The extension to approximate best responses for QRE requires a small error tolerance, which limits what the current analysis establishes for practical PSRO with learned oracles. The experiment using a DQN oracle is also too limited to resolve this concern.

  2. The benefit of adaptive anchoring over simpler alternatives is not entirely clear. Uniform-anchor QRE and Nash mixed with uniform exploration already avoid the zero-support problem. I want to understand more clearly when using the previous meta-solution as an anchor is actually beneficial, rather than simply using uniform regularization.

Questions for authors
  1. How sensitive is the escape guarantee to approximate best-response oracles in practice? The sufficient error bound for QRE becomes extremely small under the theoretical temperature schedule. Is this mainly an artifact of the proof, or does the method actually require very accurate oracles on harder instances?

  2. What is the main practical advantage of adaptive anchoring compared with uniform-anchor QRE? Since the latter already provides full support and stability, and sometimes performs better experimentally, it would be helpful to clarify which settings specifically benefit from using the previous meta-solution as an anchor.

Reviewer_YoYuOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

In double-oracle algorithms, each player starts with a small collection of candidate strategies, which is progressively expanded by adding new best responses. The present paper addresses three issues: (1) expanding the collection does not necessarily lead to improved solution quality; (2) update rules can prevent newly added strategies from influencing subsequent iterations; and (3) small errors in payoff estimates can lead to large changes in the resulting mixed strategies.

To address these issues, the authors propose combining two ingredients: ensuring that every candidate strategy receives positive probability in the mixed strategy, and regularising the selection of that mixture to improve stability.

Critical strengths

The paper has three main merits, corresponding to the three problems mentioned above:

  • It provides conditions under which the exploitability of the mixed strategies decreases faster than in standard double-oracle algorithms.
  • It establishes bounds on the exploitability of the final mixed strategies.
  • It provides guarantees on the sensitivity of the mixed strategies to payoff estimation errors.

A particularly interesting result concerns a family of games in which double-oracle algorithms may require exponentially many iterations without significantly reducing exploitability. Under specific assumptions, the authors show that their approach overcomes this pathological behaviour, reducing the number of iterations from exponential to linear.

Critical weaknesses

The major limitation of the paper is its lack of clear organisation. The manuscript focuses heavily on algorithmic details and technicalities, many of which would be better placed in the appendices. As a result, the main scientific argument appears fragmented, leaving the reader to reconstruct the central contribution from its individual components.

The paper should first precisely define the problem and the guarantees it aims to establish. It should then identify the fundamental obstacle preventing standard double-oracle algorithms from achieving the desired behaviour. Next, it should establish sufficient conditions under which a meta-solver can overcome this obstacle and achieve the targeted guarantees. Only then should the paper introduce the proposed algorithmic construction, followed by the supporting theoretical analysis and empirical evaluation.

The lack of a coherent organisation makes it difficult for reviewers to identify the central scientific contribution, understand how the different results fit together, and ultimately assess the significance of the work.

Questions for authors

What convergence-rate guarantees does the proposed approach provide beyond the specific pathological family considered in Theorem 4.3? In particular, can the authors establish an iteration-complexity bound for reaching an \varepsilon-Nash equilibrium in a more general class of games, and clarify whether regularisation provides any convergence advantage over simpler full-support meta-solvers?

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

This paper studies how perturbing the meta-strategy solver changes the behavior of double oracle (DO) and policy-space response oracles (PSRO) in two-player zero-sum games. It replaces the restricted-game Nash equilibrium with a KL-regularized, anchored quantal-response equilibrium (QRE), using an anchor that mixes the previous meta-solution with a uniform distribution over the current population.

The main result shows that, on the selection-dependent hard family of Zhang and Sandholm (2024), an interior QRE satisfying a temperature condition reaches a maximum per-player deviation gap below 2/k2/k within 4k4k rounds, despite adversarial best-response tie-breaking. The paper also extends the escape argument to uniform-mixed Nash solutions, characterizes the support-trapping failure of an unmixed previous-solution anchor, and establishes fixed-anchor Lipschitz stability and terminal exploitability bounds under sampled restricted-game payoffs. Experiments examine the hard family, anchoring failures, noisy tabular games, and approximate-oracle settings, with both positive and negative results reported.

Critical strengths
  1. A meaningful structural result for an established hard instance.

    Theorem 4.3 explains how full support converts best-response constraints into persistent information about dirty and attacked bits. Together with the restricted-gap bound, this allows the number of blocked rounds to be bounded by a linear certificate count. This goes beyond an empirical observation that regularization improves convergence.

    Corollary A.9 strengthens the insight by showing that the same mechanism applies to any selected restricted Nash equilibrium after uniform mixing, with an inverse-polynomial admissible oracle error under the additional oracle conditions. Although the result concerns one particular hard family, it usefully clarifies a mechanism behind the earlier exponential lower bound.

  2. Complementary analysis and a balanced empirical investigation.

    The support-trapping analysis, the fixed-anchor stability bound, and the noisy terminal guarantee explain different consequences of the modification. The paper also reports limitations explicitly: failed robustness criteria, losses on Kuhn and dark hex, rejection of the proposed square-root scaling on synthetic instances, and unresolved rankings with a DQN oracle.

    The fixed-comparator analysis and common-budget check in Tables 16–17 strengthen the empirical evidence. Table 15 and the starred comparisons in Table 1 also provide evidence that adaptive anchoring can improve on uniform-anchored QRE in several settings, while Tables 18–19 help explain why it can be detrimental elsewhere.

Critical weaknesses
  1. The connection between the exact escape mechanism and its numerical implementation needs stronger validation.

    The QRE escape mechanism relies on strictly positive probabilities making certain best-response choices mandatory. Under the temperature condition, the sufficient oracle-error tolerance in Theorem A.7 can be extremely small; the paper reports values below 10−2110^{-21} from the second round of the probe schedule. The theorem also requires per-player novelty and exact optimization of player 2's first bit.

    Appendix F reports numerical QRE computation using a logit fixed-point residual, including residuals below 10−810^{-8}. This residual and the oracle-error tolerance measure different quantities and cannot be compared directly. Moreover, the sufficient tolerance may be conservative: its small magnitude does not establish that the realized payoff advantages are comparably small or that the experiments are numerically invalid. Nevertheless, the reported residual alone does not certify preservation of the forcing conditions and the restricted-gap bound used in the proof.

    Run-specific diagnostics would therefore strengthen the interpretation of the capped-temperature experiments. The uniform-mixed Nash corollary partly addresses the theoretical oracle-tolerance limitation, but it does not establish the same robustness for the proposed anchored QRE.

  2. The conditions under which adaptive anchoring improves on uniform anchoring remain insufficiently characterized.

    Uniform-anchored QRE already supplies interiority and fixed-anchor smoothing. Theorem 6.1 compares solutions with a common fixed anchor, and Corollary 6.2 conditions on the realized anchor; neither establishes stability of the complete adaptive trajectory.

    There is positive empirical evidence for adaptive anchoring: Table 15 reports lower mean AUC than uniform-anchored QRE on several domains, and Table 1 includes paired comparisons against that baseline in selected cells. However, Tables 18–19 show that the previous-solution anchor can substantially delay adoption of new best responses on Kuhn and dark hex. The separate anchor-value experiment in Table 4 does not establish a significant advantage for the interior mixing choice over uniform anchoring on the noisy matrix and Kuhn settings. The DQN experiment is also inconclusive.

    The remaining issue is therefore the scope and reliability of the benefit, rather than an absence of supporting evidence. Direct paired comparisons against uniform-anchored QRE on a common simulation budget would help isolate the contribution of temporal anchoring from that of QRE regularization.

Questions for authors
  1. Numerical validation of the escape experiments.

    For the capped-temperature experiments, what numerical precision, residual norm, and best-response tie tolerances are used? Could you report run-specific checks of full support, the payoff-sign comparisons required by Lemma A.2, and the restricted-game gaps? In particular, how does the stopping criterion for the QRE solver relate to these conditions? This would clarify whether the numerical runs directly exercise the theorem's mechanism, without assuming that the conservative mass-floor bound is tight.

  2. Scope of the inverse-polynomial robustness claim.

    Is the abstract's 1/(4k)1/(4k) statement intended to describe the uniform-mixed Nash solver of Corollary A.9? If so, please distinguish this explicitly from uniform mixing of the QRE anchor, and state that the approximate-oracle extension retains the novelty and exact-first-bit conditions of Theorem A.7.

  3. Evidence for adaptive anchoring under noise.

    Table 15 and the starred entries in Table 1 already provide evidence of gains over uniform-anchored QRE on several domains. Could you extend this comparison to paired common-budget differences with confidence intervals, using the existing runs? Tables 16–17 emphasize RRD and uniform-mixed Nash. A corresponding comparison against uniform-anchored QRE would clarify whether the gains persist after aligning simulation budgets.

Comments on the paper

1 comment
Area_Chair_o55gOpenReview ↗

Reviewer–Author Discussion Period Ending Soon

Dear Reviewers,

With the discussion period coming to a close, I encourage you to revisit the authors’ responses and let us know if you have any further comments.

Thank you for your careful reviews and engagement in the discussion!

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.