Asymmetric Perturbation in Solving Bilinear Saddle-Point Optimization

Summary

The paper introduces asymmetric payoff perturbation for two-player zero-sum bilinear saddle-point problems: instead of adding a strongly-convex penalty $\frac{\mu}{2}\|\cdot\|^2$ to both players' payoffs, only one player's is perturbed. The conceptual move is that under this asymmetry the perturbed minimax strategy $x^\mu$ can exactly recover an equilibrium strategy $x^*$ of the original game whenever $\mu$ is below a game-dependent threshold $\alpha/\max_{x\in\mathcal X}\|x\|$ (Corollary 3.2). This equilibrium invariance is the central insight, and it lets AsymP-GDA — an alternating GDA method — attain a linear last-iterate rate to an equilibrium of the original game (Theorem 4.1), improving on the $\tilde O(1/t)$ rate of Liu et al. (2023)'s decreasing-schedule symmetric approach. A parameter-free variant with adaptive halving of $\mu$ retains the linear rate without knowing the threshold, and the method is extended empirically to extensive-form games via a dilated regularizer. The lever — leaving player $y$ unperturbed preserves the sharpness of $g(x)=\max_y x^\top Ay$ near $X^*$, so a small nudge cannot dislodge the minimizer — is genuinely new relative to the perturbation literature, and executed replication confirms it cleanly: $x^\mu$ equals $x^*$ to machine precision below the threshold, and the Kuhn-Poker extensive-form result reproduces at $\sim\!2\times10^{-15}$ NashConv where the symmetric variant plateaus. The main conceptual limitations are that the invariance is single-sided (a full pair needs two runs), that the linear rate hides a $\mu$-dependent constant $\beta_\mu$ whose $\mu\to 0$ scaling is undiscussed, and that the extensive-form extension has no convergence guarantee. Execution adds one substantive concern: because a single AsymP-GDA run only certifies the $x$-coordinate, its unperturbed $y$-iterate converges to the perturbed maximin set $Y^\mu$, and on biased Rock-Paper-Scissors the single-run joint NashConv plateaus at $\sim\!0.16$ rather than collapsing — so the normal-form figure's stated behavior did not reproduce at the paper's settings, even though the M-Ne panel did.

Strengths

• Conceptual contribution. One-sided perturbation preserving the sharpness structure of the linear objective, giving exact recovery in a regime rather than an $O(\mu)$ approximation, is simple, well-motivated (Figure 2 makes the geometry legible), and clearly distinct from Nesterov-style smoothing and the symmetric-perturbation line.
• Invariance reproduces to machine precision. Executed sweeps confirm Corollary 3.2 directly: proximity of $x^\mu$ to $x^*$ is numerically zero below a game threshold ($\sim\!2.5$ on biased RPS, in $(5,7]$ on biased matching pennies), then rises — the paper's most solidly validated claim.
• Rate separation. Theorem 4.1 / Corollary 4.2 give an explicit linear last-iterate rate to the original equilibrium under a bounded $\mu$, a strictly stronger guarantee than Liu et al. (2023)'s $\tilde O(1/\varepsilon)$ decreasing-$\mu$ scheme in the same setting.
• Parameter-free variant with backing. Algorithm 1 / Theorem 4.3 remove the need to know the threshold while retaining $O(\ln(1/\varepsilon))$ complexity — a practical answer to the honest concern that $\alpha$ is game-dependent.
• Honest scoping. Remark 4.4, Appendix E (Theorem E.1's shrinking interval), and Remark 5.1 (no guarantee for AsymP-DGDA) each acknowledge specific limits; the paper does not oversell what is proved.
• Empirical breadth and a reproduced headline. The extensive-form study spans Kuhn/Leduc Poker, Liar's Dice, and Goofspiel against a wide baseline set (SymP-DGDA, dilated MWU/GDA/OMWU/OGDA, plus CFR-family in Appendix A.5); the Kuhn-Poker last-iterate result and the AsymP-vs-SymP contrast reproduce convincingly.

Weaknesses

• Single-run joint convergence is not guaranteed and did not reproduce. Theorem 4.1 shows convergence to $Z^\mu=\{x^\mu\}\times Y^\mu$ and Corollary 4.2 only certifies $x^t\to x^*$; the unperturbed $y$-iterate converges to $Y^\mu$, which need not equal the original $Y^*$. The normal-form figures nonetheless plot a single run's joint NashConv. On biased RPS this plateaus at $\sim\!0.16$ (the $x$-player reaches $x^*$, the $y$-player drifts to $(0.28,0.60,0.12)$), contradicting the stated behavior, while M-Ne reproduces fully. This is the most important interpretive gap.
• AsymP-DGDA speaks past the theory. Section 5 asserts AsymP-DGDA "directly reaches an equilibrium strategy" across all five games, but Remark 5.1 concedes no convergence guarantee and Corollary 3.2 was proved for $\psi(x)=\frac12\|x\|^2$, not $\psi_{\mathrm{dil}}$. The invariance is empirical only in this setting.
• "Combined pair" mixes two decoupled optimizations. For AsymP-DGDA, $(x^t,y^t)$ pairs the $t$-th iterate of one perturbed game with that of a separate one; the baselines report a single coupled iterate. The half-budget accounting is transparent, but only one fairness axis (strategy updates) is equalized, not wall-clock or memory.
• $\mu$-dependence of the rate constant is undiscussed. The contraction factor depends on $\beta_\mu$ and a $\mu$-dependent step size; since invariance forces $\mu$ small (and Theorem E.1 makes the interval arbitrarily small), the factor may approach 1 as $\mu\to 0$. Figure 8 and the executed sweeps confirm the trade-off, but the "competitive/faster than optimistic methods" claim is unquantified without $\beta_\mu$'s scaling.
• Appendix B inconsistencies. Corollary B.2 as printed ($x^\mu=x^*$, $y^\mu=y^*$ for all $\mu>0$ under $A^\top=-A$) contradicts the sentences around it (and executed symmetric sweeps, which show $x^\mu$ distant from $x^*$ for all $\mu>0$ on skew-symmetric biased RPS). Theorem B.1's "for any $\mu>0$ such that $\mu=[\text{fixed value}]$" pins $\mu$ to one point where an "almost never coincides" complement is intended; Theorem C.1 shares the issue. Rock-Paper-Scissors also violates Theorem B.1's non-uniform-equilibrium assumption (its denominators degenerate at the uniform strategy), yet is used to illustrate Corollary B.2.
• Step-size typesetting. The condition $\eta\le\mu^2+\mu\|A\|^2$ (Theorem 4.1, reused in Corollary 4.2 and Algorithm 1) increases with $\|A\|$, which is backwards; the intended bound is presumably $\eta\le\mu/(\mu^2+\mu\|A\|^2)$. Algorithm 1 also substitutes $mn$ for $\|A\|^2$ without comment.
• "Parameter-free" is partial. Algorithm 1's stopping tolerance $\delta_k$ still uses $\|A\|^2$ and the diameter of $\mathcal Z$, so the term refers to not needing the invariance threshold, not to avoiding all game constants.
• Missing displays in Appendix G. The error bound of Lemma G.1, the definitions of $F^x_\mu$/$F^y_\mu$, the closed form of $\beta_\mu$ (Eq. (24)), and the concluding contraction are introduced but not shown, so the exact rate cannot be inspected.
• Empirical thresholds not linked to $\alpha$. The stated ranges ($\mu<2.5$ on biased RPS, $\mu\le 2.0$ in Figure 7) are never connected to the theoretical bound $\alpha/\max_x\|x\|$; $\alpha$ is not computed for any instance.
• Wording overclaims. The abstract's "known to require decreasing its strength" states a tendency as a necessity, and "provably faster than an $\tilde O(1/t)$ rate" can be read as "symmetric perturbation is provably sublinear" (it is not, against the perturbed target); both should be scoped.
• Theoretical scope. All theorems are two-player zero-sum bilinear; the dilated/sequence-form claims rest on this intuition without a formal bridge (Remark 5.1 is candid), and Markov games are only aspirational (Section 7).

Reproducibility & code

Executed replication (the repository's own nfg/main.py and efg/main.py paths, unmodified solvers/metrics) yields an overall reproduction score of $\approx 0.71$; the core mechanism holds while two headline figures reproduce only partially.

• Invariance regime — reproduces. Corollary 3.2 is confirmed to machine precision: $x^\mu=x^*$ (proximity $\lesssim 10^{-13}$) for $\mu$ below $\sim\!2.5$ (biased RPS, matching Figure 1b) and up to $\sim\!5$–$6.67$ (biased matching pennies, matching Figure 5b), then departing. The symmetric contrast (Theorem B.1) also reproduces: distant for all $\mu>0$ on biased RPS, a single coincidence dip near $\mu=4/3$ on BMP.
• Normal-form Figure 6 — partial. M-Ne reproduces the full headline (AsymP-GDA to $\sim\!10^{-15}$, SymP-GDA/GDA plateau). Biased RPS does not: AsymP-GDA's single-run joint NashConv plateaus at $\sim\!0.16$ (only the $x$-player reaches $x^*$; the $y$-player drifts to $Y^\mu$), and OGDA converges to $\sim\!10^{-14}$ rather than staying flat. This is consistent with the single-run theory and suggests the plotted panel used a different protocol or settings.
• Extensive-form Figure 4 / Figure 9 — partial. Kuhn Poker reproduces cleanly (AsymP-DGDA $\sim\!2\times10^{-15}$ vs SymP-DGDA $\sim\!2.1\times10^{-3}$; AsymP at least as low as every baseline) and Leduc directionally agrees, including Leduc as the named CFR exception. But Liar's Dice (4-sided) and Goofspiel (4-/5-card) produced no AsymP/SymP or CFR data — all runs failed on a command-quoting bug in the replication harness (a reduced driver), not in the paper's shipped per-game scripts, which handle the game names correctly. So three of five panels could not be assessed here for operational reasons; the released solver itself is sound.
• BMP specification — reproduces exactly. The equilibrium $(5/8,3/8)$ and value $-1/24$ are confirmed by direct computation (the code stores a sign-flipped matrix, applied self-consistently).
• Not exercised. The parameter-free Algorithm 1 (the $O(\ln(1/\varepsilon))$ headline) was not run and has no experiment in the paper; the $A_\gamma$ family of Theorem E.1 and the threshold constant $\alpha$ were not implemented/computed. Separately, no figure images were rendered anywhere (headless run) — every claim is a figure claim and all verdicts rest on the underlying CSVs, which is expected and not a code defect.

Recommended Changes

Essential

• Report per-player NashConv (or prove $y$-convergence) for the normal-form experiments. Because a single AsymP-GDA run only certifies $x^*$ (the $y$-iterate converges to $Y^\mu$), either plot the $x$-player NashConv, use the two-run combination as in Section 5, or state clearly that Figures 3/6 are single-run and only $x$ carries a guarantee — and reconcile the biased-RPS panel with the shipped script's plateau.
• Rescope the AsymP-DGDA empirical claims. Change "directly reaches an equilibrium strategy" to a per-game empirical statement, and add that Corollary 3.2 (proved for $\psi=\frac12\|x\|^2$) does not automatically carry to $\psi_{\mathrm{dil}}$.
• Fix Appendix B. Add the missing negation to Corollary B.2 (or correct the surrounding prose); rewrite Theorem B.1 / Theorem C.1 so the quantifier matches the "almost never coincides" reading; and replace Rock-Paper-Scissors as the illustrating example (or supply an assumption set admitting antisymmetric games).
• State the $\mu$-dependence of the contraction factor. Give how $\beta_\mu$ and the admissible $\eta$ scale as $\mu\to 0$, and qualify the "competitive/faster than optimistic methods" claim so the reader sees when the linear rate is practically fast versus merely present.
• Fix the step-size typesetting and justify the $mn$ substitution. Print a step size that decreases in $\|A\|$ (e.g. $\eta\le\mu/(\mu^2+\mu\|A\|^2)$) throughout Theorem 4.1, Corollary 4.2, Lemma G.1, and Algorithm 1, and add one line noting $mn\ge\|A\|^2$ under the Appendix D.1 normalization.

Suggested

• Add a wall-clock/FLOP comparison for AsymP-DGDA alongside "total strategy updates," and note in Section 5 that $(x^t,y^t)$ is not a coupled-solver iterate.
• Release the missing pieces: a reference implementation of Algorithm 1 with at least one experiment (ideally on the $A_\gamma$ family), the $A_\gamma$ game config, an $\alpha$ estimator, and the plotting/aggregation scripts for Figures 1, 4, 5, 6, 8, 9; and fix the reduced driver's quoting so Liar's Dice/Goofspiel run.
• Numerically link the empirical $\mu$-thresholds to $\alpha$ for biased RPS and one extensive-form game, treating any excess over the sufficient bound as an empirical observation.
• Soften the abstract/intro claims on decreasing schedules and "provably faster," clarifying that the rate gap concerns the original equilibrium.
• Clarify "parameter-free" — note that $\delta_k$ still depends on $\|A\|^2$ and $\max_z\|z\|^2$.
• Restore the missing Appendix G displays ($F^x_\mu$, Lemma G.1's error bound, $\beta_\mu$ in Eq. (24), the concluding contraction), and reconcile the "near-linear growth" wording in Section 7 with the sharpness inequality of Section 3.2.
• Add one sentence on the CFR reporting convention at first mention, reminding readers the CFR curves are average-iterate.