Perturbed Meta-Solvers Escape the Worst Case of Double Oracle

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 $k$ chance states, DO needs $2^{k-1}$ 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 $\tau$ times the KL divergence from an anchor, where $\tau >0$ is the temperature and the anchor mixes the previous round's meta-solution with the uniform distribution. Below a mild problem-dependent cap on $\tau$, the perturbed meta-solver collapses this worst case from $2^{k-1}$ to at most $4k$ rounds even under fully adversarial tie-breaking, given exact QRE solves and best-response oracles. An anchor of mass $1/(4k)$ 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 $(2/\tau )$-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 $\epsilon >0$ removes the deadlock on all seeds, and all $80$ terminal-bound runs satisfy the bound. Against regularized replicator dynamics and $\epsilon$-mixed Nash, fixed in advance, the anchored QRE has the lower exploitability AUC in $15/21$ noisy cells each.