acceptodds
Under review as a conference paper at ICLR 2027

Coupled Dual-Adversarial Regularized Self-Play

Abstract

Naive self-play for two-player zero-sum games can cycle in nontransitive games. Regularized self-play stabilizes training with a single network but only plays against itself, so it forgets earlier opponents and cannot use external ones; population methods keep an opponent pool, but their equilibrium lives in a mixture over the pool, and heuristic weightings such as PFSP carry no convergence guarantee. We propose Coupled Dual-Adversarial Regularized self-play (CoDA-R). Each round, CoDA-R sets the pool weights by a Euclidean projection anchored at pure self-play, so that only opponents currently beating the latest policy receive weight, and then takes a proximal policy step against the resulting mixture. The coupling yields one energy inequality that charges every policy step and every unit of pool weight to the remaining distance to a Nash equilibrium. For the exact algorithm, this gives last-iterate convergence of the latest policy to a Nash equilibrium however oracle opponents enter or leave the pool, plus certificates computable during training and error-tolerant versions of all bounds. In OpenSpiel at a matched budget, the latest network of CoDA-R cuts the tail exploitability on Goofspiel(4) from 0.797 for R-NaD-PPO to 0.083, on par with a multi-network PSRO mixture; on Leduc poker, with the dual strength scaled to the payoff range and an exact best-response oracle, it roughly halves that of R-NaD-PPO; on Liar's Dice the two tie.

Primary area:
reinforcement learning
Keywords:
self-play, two-player zero-sum games, Nash equilibrium, last-iterate convergence, regularized self-play, opponent pool, Euclidean projection, variational inequality, exploitability, multi-agent reinforcement learning

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_QhDgOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper addresses a well-known failure mode of self-play in two-player zero-sum games. Naive self-play can cycle in nontransitive games; regularized self-play (R-NaD, MMD) stabilizes training with a single network but plays only against itself, forgetting earlier opponents and admitting no external ones; population methods (Double Oracle, PSRO, PFSP, league training) retain a pool of opponents, but their equilibrium is a mixture over the pool and heuristic weightings such as PFSP carry no convergence guarantee. The proposed Coupled Dual-Adversarial Regularized self-play (CoDA-R) combines the openness of population methods with the single-network guarantee of regularized self-play. Each round it sets the pool weights by a Euclidean projection anchored at pure self-play, w(x) = ΠΔ(em + cℓ̃(x)), so that only opponents currently beating the latest policy receive weight, and then takes an implicit proximal policy step against the resulting mixture. The coupling yields a single energy inequality (Theorem 5.3) that charges both policy movement and pool weight to the squared distance from the latest policy to a Nash equilibrium. This gives last-iterate convergence of the trained policy to a Nash strategy for any sequence of pool admissions (Theorem 5.6), an explicit O(K⁻¹ᐟ⁴) last-iterate rate once the pool stops changing (Theorem 5.7), certificates computable during training (Theorem 5.5), and error-tolerant versions (Theorem 5.8). A fixed-point counterexample (Proposition 3.2) diagnoses why the moving-anchor predecessor CoDA fails. Finite-dimensional verification on random matrix games checks every inequality over about 3.7 million per-step records with no violation. On OpenSpiel at a matched budget of 5×10⁵ games (4 seeds, IQM with 95% CI), the single latest network of CoDA-R cuts the tail exploitability of R-NaD-PPO on Goofspiel(4) from 0.797 to 0.083, on par with a multi-network PSRO mixture; on Leduc poker with the dual strength scaled to the payoff range and an exact best-response oracle it roughly halves it; and on Liar's Dice the two tie.

Critical strengths

1.The theory is complete and elegant. The single energy inequality (Theorem 5.3) that charges both policy movement and pool weight to the distance to a Nash equilibrium is a clean idea, and it yields last-iterate convergence (Theorem 5.6), an explicit rate (Theorem 5.7), computable certificates (Theorem 5.5), and error-tolerant bounds (Theorem 5.8) under arbitrary pool changes. The counterexample for the moving anchor (Proposition 3.2) precisely diagnoses the defect of the predecessor CoDA. 2.The fixed dual anchor at pure self-play is a conceptually simple and well-motivated design: once latest is a Nash strategy no opponent can beat it, so the correct dual weight is the known point em (Sec. 4.1). The monotonicity argument for unique solvability (Prop. A.1) is careful. 3.The finite-dimensional verification is rigorous and unusually thorough: about 3.7 million per-step records with no inequality violation, and breaking any of three mechanisms produces thousands of violations, demonstrating that the checks can detect wrong algorithms (Sec. 6.1). 4.The neural experiments use a matched budget (all games consumed, oracle included) and IQM with bootstrap 95% CI per Agarwal et al. (2021), with 4 seeds; this is a sound protocol for comparing training methods (Sec. 6.2). 5.The controlled vulnerability-injection experiment validates the closed form of Lemma 4.1(c): the weight wA and the true lead drop to zero in sync, and the scatter hugs the theoretical form (Sec. 6.3).

Critical weaknesses

1.The neural evidence is narrow: a clear advantage appears on only one of three games. Goofspiel(4) shows a strong gain (0.083 vs 0.797, near tenfold); but Leduc requires the dual strength scaled to the payoff range (c = 48) and an exact best-response oracle to roughly halve the exploitability, and the PPO-oracle version at c = 48 has overlapping CIs with R-NaD-PPO on at_budget and AUC; Liar's Dice is a tie. The headline claim of an advantage is therefore supported by one game where R-NaD-PPO degenerates in a specific way (its entropy collapses). More games and a wider set of failure modes are needed to establish the general benefit (Sec. 6.2, Table 1). 2.The core selling point — certificates computable during training — is unreliable in the neural setting. The paper reports that latest_cert underestimates the true exploitability in 63 of 72 oracle evaluations and does not beat last-checkpoint selection, because the KL proxy does not bound the theoretical term and the exploiter gap τ is unknown (Sec. 6.3). Since the certificates are a principal claimed contribution, their failure in the deployed regime substantially weakens the practical value of the theory. 3.The theory is stated at the idealized normal-form level, but the experiments are sequential games, and the gap is only absorbed into error terms. The paper acknowledges that the gap between the idealized analysis and the neural implementation is absorbed into ek and δk (Sec. 2.2, 5.3). However, Theorem 5.8 gives only a min-per-step bound under constant errors, not convergence of the iterates, and the conditions under which a sequential game satisfies the normal-form assumptions are not made explicit. The theoretical guarantee and the neural evidence are thus not yet fully connected. 4. Statistical power is limited: only 4 seeds. With 4 seeds, the IQM and bootstrap CIs are wide (e.g., the tail_mean CIs on Goofspiel overlap at the high end, and the Leduc PPO-oracle comparison is not significant). The paper would benefit from more seeds or an explicit power argument for the reported differences.

Questions for authors
  1. With only 4 seeds, several comparisons have overlapping CIs (e.g., Leduc PPO-oracle at c = 48). Please provide more seeds or a power analysis for the reported differences.
  2. The estimator lag means vulnerabilities can be missed before the estimate catches up (54/61 holes on Goofspiel). Can you quantify how often this happens and whether a better estimator would recover the tail_worst spike of 0.49?
1 comment
AuthorsOpenReview ↗

5-Game / 10-Seed Evaluation, Certificate Scope, and Estimator Ablation

Thank you for the accurate summary and insightful critique. We expanded our experiments and clarified the theory to address every point:

  • 5 games, 10 seeds, 8×8\times budget, & matched tuning (§5.2–§5.3, Table 1, Appendix Tables 9 & 11):
    • At B=4×106B=4\times 10^6 games across 10 seeds (all methods tuned identically on held-out seeds), CoDA-R with standard PPO exploiters achieves the lowest single-network tail exploitability on Goofspiel(4) and Leduc, beating R-NaD-PPO and MMD-PPO on 10/10 seeds in both (−73%-73\% and −36%-36\% vs. R-NaD; paired CIs [−0.747,−0.586][-0.747,-0.586] and [−0.662,−0.399][-0.662,-0.399]) and beating PFSP on 10/10, 7/10, and 10/10 seeds across Goofspiel, Leduc, and Liar's Dice (all paired CIs <0<0).
    • Zero-shot on 3×3 abrupt Dark Hex and abrupt Phantom TTT (≈2.7×1010\approx 2.7\times 10^{10} nodes, 5 seeds), CoDA-R is best single network on Dark Hex (0.432 vs. 0.529 R-NaD, 0.743 PFSP) and ties R-NaD on Phantom TTT (0.512 vs. 0.509), while 4 controlled studies (§5.4) show benefits beyond entropy collapse (off-trajectory repair and near-Nash retention).
  • Certificates vs. calibrated lower bounds (§4.2–§4.3, §5.2): We removed neural upper-bound selection claims; Theorem 4.5 serves the exact convergence proof, while in PPO we report the exploiter lower bound [ℓ(x^;y^)−12]+≤Expl(x^)[\ell(\hat{\boldsymbol{x}};\hat{\boldsymbol{y}})-\tfrac{1}{2}]^+ \le \mathrm{Expl}(\hat{\boldsymbol{x}}). Across 3,950 admissions, its 95% lower confidence bound is positive 63.0% of the time and exceeds true exploitability only 3 times (0.08%).
  • Sequential games (§2.1, §4.4): We invoke Kuhn's theorem for normal-form equivalence under perfect recall and map each PPO approximation to (ξk,δk,ε)(\xi_k, \delta_k, \varepsilon) in Appendix Table 5.
  • Estimator lag (§5.5, Appendix C, Figure 12): We added count-adaptive EMA, 2.52.5-SE jump resets, and UCB probing (Table 6). Replacing this estimator with exact loss rates (ξk=0\xi_k=0, Figure 12) further lowers Goofspiel tail exploitability on 6/6 seeds, directly quantifying residual estimator lag.
Reviewer_uVg4OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

Unfortunately, the paper is very hard to follow. The problem is not clearly defined. For example, the authors study symmetric games, but symmetry is mentioned for the first time on page 3! Many terms and mathematical expressions are used without proper definitions. Even the abstract is difficult to follow, and I had to go through the paper several times to gain some basic understanding.

Based on my limited understanding, the paper proposes CoDA-R, a method for using external opponents in regularized self-play in two-player symmetric zero-sum games. The algorithm assigns weights to opponents based on how much they exploit the current policy, and then performs a proximal policy update against the resulting mixture. It appears that the authors also evaluate an approximate implementation of their algorithm based on PPO on several small games.

Critical strengths

It seems that the paper has some nteresting theoretical and practical merits, but unfortunately, it is not clear enough for me to evaluate them. I suggest that the authors rewrite the paper from scratch in a coherent and consistent way.

Critical weaknesses

I have two major concerns:

  1. What is the problem being studied here? Is the problem intended for games with large action spaces, such as extensive-form games, where direct computation or iterating over actions is not easy? The computational problem and the role of the opponent pool are not sufficiently motivated. What's the role of PkP_k? Is the full payoff matrix available? Why are these very basic details of the problem not clear? Is the goal to show that having access to the pool of opponents PkP_k gives faster convergence? A clear problem formulation and motivation are very necessary for both theory and practice.

  2. The paper is very difficult to read, and the presentation hides the main idea. Many terms and mathematical expressions are not clearly defined. I can give many examples of these ambiguities, even in the abstract.

Questions for authors

What's the advantage of having the pool? What are the exact theoretical results the authors are claiming? How does the theoretical study differ from the approximation used in the experiments, such as loss estimation or other details related to PPO? Since the exact algorithm converges even with an empty opponent pool, is there any theoretical or empirical characterization of when adding opponents improves convergence speed or sample efficiency? Is the proposed method related to classical approaches for monotone VIs with additional convex penalties? How can the approach be placed within the VI literature?

1 comment
AuthorsOpenReview ↗

Problem Setting, Pool Speed-Up Theory, and Monotone VI Link

Thank you for your constructive questions. Following your suggestion, we restructured and redrafted the paper from top to bottom, starting with a dedicated Problem Setting (§2) on page 2:

  • Problem & black-box pool (§2.1–§2.2): We target last-iterate convergence of a single network in sequential imperfect-information games (seat-randomized symmetric). CoDA-R needs neither the payoff matrix SS nor PSRO's N×NN\times N meta-payoff table, using only scalar win/loss outcomes between the learner and each frozen black-box opponent in PP.
  • Exact claims & why add a pool if empty-pool converges (§4, new Theorem 4.8, §5.4): Exact CoDA-R converges in the last iterate under arbitrary pool changes (Theorems 4.6–4.7). With P=∅P=\emptyset, per-step reduction in ∥xk−x⋆∥2\Vert \boldsymbol{x_k}-\boldsymbol{x}^\star \Vert^2 is only ∥sk∥2=O(1/η2)\Vert \boldsymbol{s_k} \Vert^2 = O(1/\eta^2) near an interior Nash because Sx⊥(x−x⋆)S\boldsymbol{x} \perp (\boldsymbol{x}-\boldsymbol{x}^\star). Theorem 4.8 proves that an ε\varepsilon-best response in PkP_k guarantees c4η([Expl(xk)−ε]+)2=O(1/η)\frac{c}{4\eta}([\mathrm{Expl}(\boldsymbol{x_k})-\varepsilon]^+)^2 = O(1/\eta) progress (Figure 2). Empirically (§5.4), PP also supplies gradients on rarely visited branches to repair off-trajectory holes and prevent equilibrium drift.
  • Theory vs. PPO (§2.1, §4.4, Appendix Table 5): Kuhn's theorem equates perfect-recall behavior policies with normal-form mixed strategies. PPO introduces loss-estimation error ξk\xi_k, KL/finite-rollout slack δk\delta_k, and oracle error ε\varepsilon; Theorem A.2 bounds all three (with ξk\xi_k entering only as aξka \xi_k, vanishing as pool weight a→0a\to 0).
  • Monotone VI link (§3.2, §6): Writing wP(x)\boldsymbol{w_P}(\boldsymbol{x}) for the pool coordinates of w(x)\boldsymbol{w}(\boldsymbol{x}), we have AwP(x)=∇ΨP(x)A \boldsymbol{w_P}(\boldsymbol{x}) = \nabla\Psi_P(\boldsymbol{x}) for the smooth convex penalty ΨP(x):=max⁡w∈ΔN+1[∑i=1Nwi(ℓi(x)−12)−12c∥w−esp∥2]\Psi_P(\boldsymbol{x}) := \max_{\boldsymbol{w}\in\Delta_{N+1}}\big[\sum_{i=1}^N w_i(\ell_i(\boldsymbol{x})-\tfrac{1}{2}) - \tfrac{1}{2c}\Vert \boldsymbol{w}-\boldsymbol{e_{\mathrm{sp}}} \Vert^2\big]. Because ΨP(x⋆)=0\Psi_P(\boldsymbol{x}^\star)=0 on all Nash strategies, Eq. (6) is an implicit proximal point step on the monotone operator Sx+∇ΨP(x)S\boldsymbol{x}+\nabla\Psi_P(\boldsymbol{x}) requiring no penalty annealing.
Reviewer_sWnhOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper is proposes CODA-R, a method that aims solve the failure mode of self-play. It first identifies the limitations of previous remedies for the self-play failure mode (regularised self-play and population methods) and then propose a hybrid solution.

Critical strengths
  1. The paper provide clear motivation of using the proposed method, CODA-R, by providing limitations of existing self-play strategies.
  2. Unlike population methods, the proposed method is not dependent on heuristics for selection of weights for the combination of set of agents/past-policies.
Critical weaknesses

The paper is not written in comprehensible manner. It is difficult to read and understand, below are mentioned few examples, thus it is suggested for author to do major revision of paper writing.

  1. The paper introduces terms like , PPO, PFSP, PSRO, R-NaD, NFSP, MMD, MWU without giving citation, and describing what it means? For example the acronym PPO, is not defined anywhere in the paper and left to the reader to infer. This not only reduces the paper’s readability but also makes its key ideas harder to understand.
  2. ΔM\Delta_M is not defined in line 124. what operation does delta perform? is it some interpolation of strategy? Similarly in line 138, subscript N appears over x without defining it.
  3. In equation (3) w{k+1}w_\{k+1\} is introduced without defining it. Similarly in the same equation cc is not defined, and later used in proposition 3.1 as result.
  4. Proposition and lemmas are introduced without proper defination of notations which makes proofs spurious.
Questions for authors

See weaknesses

3 comments
AuthorsOpenReview ↗

Complete Manuscript Rewrite and Self-Contained Notation

Thank you for highlighting CoDA-R's motivation and heuristic-free weighting, and for your candid feedback on readability. Following your advice, we restructured and redrafted the paper so every term and symbol is defined before use:

  • Acronyms & citations (§1, §6): Every acronym (PPO, PSRO, PFSP, R-NaD, MMD, NFSP, MWU) is now spelled out in full, briefly explained, and cited at first mention.
  • Simplex & Nash notation (§2.1): Δn:={z∈Rn:zi≥0,∑izi=1}\Delta_n := \lbrace \boldsymbol{z}\in\mathbb{R}^n : z_i\ge 0, \sum_i z_i=1 \rbrace is explicitly defined as the probability simplex, and policy steps are written sk:=xk+1−xk\boldsymbol{s_k} := \boldsymbol{x_{k+1}}-\boldsymbol{x_k} to avoid overloading Δ\Delta. Nash strategies are defined via Expl(x⋆)=0\mathrm{Expl}(\boldsymbol{x}^\star)=0 in Eq. (1) and written x⋆\boldsymbol{x}^\star instead of xN\boldsymbol{x_N} to avoid clashing with pool size NN.
  • Former Eq. (3) & Proposition 3.1 (§3, §4.5, Appendix A.13): CoDA-R is now presented directly in §3 (Figure 1). The moving-anchor predecessor (CoDA) is moved to §4.5 and Proposition A.4, with v⋆v^\star, φ(ρ):=min⁡xρ⊤ℓ(x)\varphi(\boldsymbol{\rho}) := \min_{\boldsymbol{x}}\boldsymbol{\rho}^\top\boldsymbol{\ell}(\boldsymbol{x}), and saddle optimality all defined prior to the proposition.
  • Self-contained proofs (§3–§4, Appendix A): Every lemma and theorem uses only previously defined quantities, summarized in Appendix Table 2.

Thank you for your reply. Some parts of your reply is not rendered properly. I also have a new concern now. If ℓ<12\ell < \frac12 according to line 104, it means Expl(x)\text{Expl}(x) is at most 12\frac12. Then how could results of Table 1 have values higher than 12\frac12? Also could authors clarify what they mean by rewriting paper from scratch?

AuthorsOpenReview ↗

Payoff Units in Table 1 and Scope of Structural Rewrite

Thank you for reading the revised PDF carefully, and apologies for the Markdown rendering glitch in our earlier comment (now fixed).

  • Why Table 1 has values above 1/21/2 (payoff units): Under the [0,1][0, 1]-normalized loss rate of §2.1 (line 104), Expl(x)∈[0,12]\mathrm{Expl}(\boldsymbol{x}) \in [0, \tfrac{1}{2}]. While our weight rule uses [0,1][0, 1]-normalized outcomes, Table 1 and §5.2–§5.5 follow standard OpenSpiel convention (exploitability.exploitability) and report exact full-tree exploitability in each game's native payoff units, NashConv(x)/2=R⋅Expl(x)∈[0,R/2]\mathrm{NashConv}(\boldsymbol{x})/2 = R \cdot \mathrm{Expl}(\boldsymbol{x}) \in [0, R/2], where R=umax⁡−umin⁡R = u_{\max} - u_{\min} is the payoff span:

    • Goofspiel(4) & Liar's Dice (u∈[−1,1]u \in [-1, 1], R=2R = 2): native range [0,1][0, 1] (e.g., 0.999 =2×0.4995= 2 \times 0.4995; CoDA-R's 0.256 equals normalized Expl(x)=0.128≤12\mathrm{Expl}(\boldsymbol{x}) = 0.128 \le \tfrac{1}{2}).
    • Leduc poker (u∈[−13,13]u \in [-13, 13] chips, R=26R = 26): native range [0,13][0, 13] chips (e.g., CoDA-R's 0.919 chips equals normalized Expl(x)=0.919/26=0.035≤12\mathrm{Expl}(\boldsymbol{x}) = 0.919 / 26 = 0.035 \le \tfrac{1}{2}). We have updated §2.1 (line 111), §5.2, and the Table 1 caption in the revised PDF to state R⋅Expl(x)R \cdot \mathrm{Expl}(\boldsymbol{x}) explicitly.
  • Meaning of "rewrote from scratch": Our core algorithm (CoDA-R) and theoretical framework are unchanged from the initial submission. We meant a structural and expositional rewrite—reorganizing the paper so a self-contained Problem Setting (§2) and CoDA-R (§3–§4) appear before the moving-anchor counterexample (§4.5), defining every symbol and acronym before use, and adding the reviewer-requested oracle bound (Theorem 4.8) and expanded experiments (§5).

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Major Revision: Full Rewrite, New Oracle Theory, and 5-Game / 10-Seed Experiments

We thank all reviewers for their candid feedback. We have rewritten the manuscript from scratch (within 10 pages) and substantially expanded our theory and experiments (with updated anonymized code in the supplementary material):

  1. Clarity & Self-Contained Notation (Reviewers sWnh, uVg4): Added a dedicated Problem Setting (§2) defining seat-randomized symmetry, normal-form equivalence (Kuhn's theorem), black-box pools, and every symbol before use (Figure 1, Appendix Table 2). All acronyms are spelled out and cited at first mention, and CoDA-R (§3–§4) now precedes the moving-anchor counterexample (§4.5).
  2. Pool Speed-Up Theory & VI Link (Reviewers uVg4, QhDg): New Theorem 4.8 proves that an ε\varepsilon-best response in the pool improves per-step progress toward Nash from O(1/η2)O(1/\eta^2) (empty-pool self-play) to O(1/η)O(1/\eta). Eq. (6) is explicitly situated as an implicit proximal point step on the monotone operator Sx+∇ΨP(x)S\boldsymbol{x}+\nabla\Psi_P(\boldsymbol{x}) (§3.2, §6).
  3. Expanded Evaluation (Reviewer QhDg): Scaled to 5 games (adding 2.7×10102.7\times 10^{10}-node 3×3 abrupt Dark Hex and abrupt Phantom TTT), 8×8\times budget (4×1064\times 10^6 games), 10 seeds, 7 equally tuned baselines (adding MMD-PPO, Uniform FSP, PFSP, NFSP), and 4 controlled mechanism studies (§5.4). Among single networks, CoDA-R beats PFSP on all 5 games and achieves or ties for lowest exploitability on 4 of 5 games.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.