Pith. sign in

REVIEW 1 major objections 5 minor 51 references

Asymmetric Perturbation in Solving Bilinear Saddle-Point Optimization

T0 review · 1 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Perturbing only one player's payoff preserves exact equilibria in bilinear saddle-point games, and a gradient descent-ascent method on the perturbed game converges linearly to the original equilibrium for a fixed small perturbation…

desk verdict The invariance result and fixed-perturbation linear rate are real and well argued; the parameter-free variant has a fixable proof bug that should be corrected before publication. read the letter →

arxiv 2506.05747 v4 pith:V5MFKLF7 submitted 2025-06-06 math.OC

Kenshi Abe , Mitsuki Sakamoto , Kaito Ariu , Atsushi Iwasaki This is my paper
classification math.OC MSC 90C4791A0590C25
keywords bilinearsaddle-pointoptimizationasymmetricperturbationequilibriuminvariancelast-iterateconvergencegradientdescentascentminimaxgamesNashextensive-form
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that a one-sided payoff perturbation eliminates the approximation bias that plagues symmetric regularization in bilinear saddle-point games. For the problem min_{x in X} max_{y in Y} x^T A y with polytope strategy sets, adding the penalty (mu/2)||x||^2 only to the minimizer's payoff leaves the equilibrium unchanged: whenever 0 < mu < $\alpha$ / max_{x in X} ||x||, the perturbed game's minimizer is exactly a minimax strategy of the original game, for a constant $\alpha$ that depends only on the game. Building on this invariance, the paper constructs AsymP-GDA, an alternating gradient descent-ascent method that converges linearly in the last iterate to an original equilibrium, and a parameter-free variant that halves mu adaptively and still runs in O(ln(1/epsilon)) iterations. A KKT-based impossibility theorem shows the symmetric counterpart almost never enjoys this property, and experiments on normal-form and extensive-form games demonstrate fast convergence to exact equilibria.

What carries the argument

The load-bearing object is the invariance interval (0, alpha / max_{x in X} ||x||), built from the linear-growth constant alpha of Lemma F.1, which lower-bounds the increase of the minimizer's objective by alpha times the distance to the minimax set. On the algorithmic side, the proof of the linear rate combines a monotone decrease of the distance to the equilibrium set with a Hoffman-type error bound for affine variational inequalities over polytopes: it shows that the update operator T_{eta,mu} moves the point by at least (eta/beta_mu) times its distance to the equilibrium set, which turns a one-step contraction into a geometric last-iterate rate. The impossibility result for symmetric perturbation is a KKT computation that pins the only mu at which the symmetric solution could equal the original equilibrium to a specific formula involving the uniform strategy and the game value.

What would settle it

Take the game A_gamma = diag(gamma, 2gamma, 1) on the 3-simplex from Appendix E and measure, for a decreasing sequence gamma -> 0, the largest mu such that x_mu equals the minimax strategy x*; the claim predicts this threshold is exactly bar{mu}(gamma) = 2gamma(2gamma+3)/(1+4gamma-$4gamma^{2}$), which tends to zero. Any positive-mu coincidence beyond the predicted threshold for some gamma, or any game where inf_{x not in X*} (g(x) - v*)/dist(x, X*) equals zero while the threshold is claimed positive, would falsify Corollary 3.2 and, with it, the linear-rate guarantee of AsymP-GDA. The symmetric side can be tested directly: for a unique interior equilibrium with non-uniform play, Theorem B.1 forbids exact coincidence except at one exceptional mu, so finding two distinct positive mu values with x_mu = x* for the symmetric game would falsify it.

Watch

Extended reading notes

Core claim

The central claim is that for bilinear saddle-point problems, the asymmetric perturbed game min_{x in X} max_{y in Y} { x^T A y + (mu/2)||x||^2 } exhibits an equilibrium-invariance regime: for every mu in (0, $\alpha$ / max_{x in X} ||x||), its unique minimizer x_mu lies in X*, the minimax set of the original game (Corollary 3.2). The regime follows from a uniform linear-growth inequality: g(x) = max_{y in Y} x^T A y satisfies g(x) - v* >= $\alpha$ dist(x, X*) for all x in X, so the linear objective's kink at X* beats the quadratic tug of the penalty when mu is small. The paper then shows that alternating gradient descent-ascent on this one-sided perturbed game converges linearly in the last iterate to Z_mu = {x_mu} x Y_mu, and hence, within the invariance regime, to an equilibrium of the original game; it also proves that symmetric perturbation almost never achieves exact recovery, since for a generic interior equilibrium the symmetrically perturbed solution coincides with the original only for at most one exceptional mu.

Load-bearing premise

The entire construction depends on a uniform positive constant alpha: the minimizer's payoff must increase at least linearly as one moves away from the set of minimax strategies. If a game has alpha = 0, or if the needed range of mu shrinks to zero as it does for the A_gamma family in Appendix E, then no fixed small positive mu guarantees exact recovery and the claimed rate applies to a biased target.

Editorial extensions

If this is right

  • For any bilinear saddle-point game with polytope strategy sets, a fixed small one-sided penalty yields an exact equilibrium of the original game, so no annealing schedule or iteration-dependent tuning of mu is needed.
  • AsymP-GDA attains a linear last-iterate rate to an original equilibrium with only one vector addition of per-iteration overhead relative to plain alternating GDA, competitive with optimistic methods in bilinear settings.
  • The parameter-free variant of Algorithm 1 achieves NashConv <= epsilon in O(ln(1/epsilon)) total iterations from an arbitrarily large initial mu, without knowing alpha, whereas decreasing-mu symmetric perturbation requires about O(1/epsilon) iterations.
  • In extensive-form games, running the dilated variant separately for each player reaches equilibria faster or as fast as SymP-DGDA, DMWU, DGDA, DOGDA, DOMWU, and CFR-family baselines in the tested games.
  • Symmetric perturbation almost never gives exact recovery: for a unique interior equilibrium with non-uniform play, the symmetrically perturbed solution coincides with the original only for at most one exceptional mu.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The invariance may carry to more general convex-concave saddle problems where a sharpness or linear-growth condition holds, not just bilinear ones; the paper hints at Markov games, and a testable step would be verifying an analogous alpha for two-player zero-sum Markov games.
  • Because the required mu-range is game-dependent and can be arbitrarily narrow, a robust practice would be to use the parameter-free halving variant, or to adaptively estimate alpha from observed duality gaps during training, rather than relying on a hand-tuned fixed mu.
  • The separate-runs asymmetry, one run for x and one for y, doubles the strategy-update cost; if a principled way to extract both players' strategies from a single asymmetric run were found, the method's practical overhead would halve.
  • The linear-rate constant degrades as mu shrinks, since the contraction ratio depends on eta^2/beta_mu^2, so there is a genuine trade-off between accuracy of recovery and speed; a schedule that starts large and halves mu preserves the O(ln(1/epsilon)) rate while keeping early speed.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 5 minor

Summary. The paper studies bilinear saddle-point optimization and proposes asymmetric payoff perturbation, in which only the x-player's payoff is regularized by a strongly convex term. The main structural result (Theorem 3.1, Corollary 3.2) is that for sufficiently small perturbation strength the minimax strategy of the perturbed game exactly coincides with a minimax strategy of the original game, relying on a linear-growth bound imported from Wei et al. (2021). The paper then proposes AsymP-GDA and proves linear last-iterate convergence to the equilibrium set of the perturbed game (Theorem 4.1, Corollary 4.2). A parameter-free variant (Algorithm 1) is claimed to retain a linear rate without knowing the allowable range of the perturbation strength (Theorem 4.3). The paper also presents experiments in normal-form and extensive-form games and proves impossibility results for symmetric perturbation for unique interior equilibria.

Significance. If the results hold, the paper contributes a conceptually useful observation: one-sided regularization can remove the approximation bias inherent in symmetric regularization for bilinear saddle-point problems, while preserving linear last-iterate convergence. The detailed proofs of Theorems 3.1 and 4.1, the explicit constants, and the honest discussion of the worst-case narrowness of the invariance interval (Appendix E) are strengths. The empirical comparison in extensive-form games is suggestive, though Remark 5.1 correctly notes that no theoretical guarantee is provided for the dilated variant. The main weakness is that the proof of the parameter-free linear-rate claim, Theorem 4.3, has a load-bearing gap in the stopping-threshold logic of Algorithm 1; this is fixable without changing the core structural results.

major comments (1)
  1. The stopping threshold used by Algorithm 1 is not small enough for Lemma H.4 to be applicable in the proof of Theorem 4.3. Line 6 sets delta_k = mu_k * epsilon^2 / (2 * ||A||^2 * max_{z in Z} ||z||^2), but Lemma H.4 requires the x-subroutine gap to be at most mu_k * epsilon^2 / (2m) and the y-subroutine gap to be at most mu_k * epsilon^2 / (2n). These requirements are not implied by the line-6 threshold under the normalization of Appendix D.1. For example, with X = Y = Delta_3 and A = e1 e1^T we have ||A||^2 = 1 and max_{z in Z} ||z||^2 = 2, so line 6 gives delta_k = mu_k * epsilon^2 / 4, which is strictly larger than the mu_k * epsilon^2 / 6 required for m = 3. Consequently, the inner subroutine can certify a perturbed duality gap that is too large for Lemma H.4 to convert into the desired NashConv bound, and the proof of Theorem 4.3 does not establish that the outer NashConv check at line 11 ever fires. This is readily fixable by setting delta_k to the minimum of mu_k * epsilon^2 / (2m), mu_k * epsilon^2 / (2n), and the line-6 expression; the iteration bound then remains O(ln(1/epsilon)).
minor comments (5)
  1. [Section 2] The sentence describing the standard two-player perturbation says "we refer to this perturbed game as asymmetrically perturbed game"; this should read "symmetrically perturbed game".
  2. [Abstract] The abstract contains the typo "proposesasymmetric perturbation"; a space is missing after "proposes".
  3. [Lemma H.4] The stated assumption mu in (0, alpha / (max_{x in X} ||x|| + max_{y in Y} ||y||)) is stronger than what the proof actually uses; the x-side bound only needs mu < alpha / max_{x in X} ||x||, and the y-side bound only needs the analogous condition. The statement could be simplified to match the proof.
  4. [Algorithm 1] The proof of Theorem 4.3 silently replaces the actual threshold delta_k by the smaller thresholds mu_k * epsilon^2 / (2m) and mu_k * epsilon^2 / (2n) when applying Lemma H.2. Even after fixing the threshold, the proof should explicitly state which delta_k is substituted into Lemma H.2 and verify that the line-6 constant is compatible with the normalization assumptions.
  5. [Section 5] The text introducing AsymP-DGDA would benefit from a reminder that, as stated in Remark 5.1, the theoretical guarantees of Section 4 do not apply to the dilated regularizer; currently the reader could mistake the empirical results for a proven convergence claim in extensive-form games.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the invariance result is an explicit consequence of an external linear-growth lemma, not a relabeled input or a fitted parameter.

full rationale

The central claim — Corollary 3.2 — is derived from Lemma F.1 (imported from Wei et al. 2021), which states that for the polytopal bilinear game there exists a positive constant alpha with g(x) - g(x*) >= alpha dist(x, X*). Theorem 3.1 combines this external linear-growth bound with the explicit inequality for the perturbation term (Eq. 12) to obtain the distance bound dist(x_mu, X*) <= 2 max(0, max||x|| - alpha/mu). Corollary 3.2 is then a direct instantiation of this bound, not a definitional restatement of the desired conclusion. The contraction proof of Theorem 4.1 is self-contained (Lemma G.1, Hoffman-type Lemma G.2, and the distance-recursion argument), and Corollary 4.2 merely composes it with Corollary 3.2. The parameter-free construction in Appendix D also uses the same derived invariance, with the number of episodes controlled by the same alpha; the paper explicitly acknowledges that alpha can be arbitrarily small (Appendix E and Remark 4.4), which is a robustness limitation rather than circularity. Self-citations in the introduction (e.g., Abe et al. 2024 for the O(mu) bias of symmetric perturbation) are contextual; the paper also gives its own independent impossibility proof in Appendix B, and Appendix B is not used as a load-bearing premise for the main theorems. The skeptic-identified mismatch between Algorithm 1's inner threshold delta_k and Lemma H.4's required threshold is a possible proof-completeness gap, but it is a correctness issue in the written argument, not a reduction of a prediction to its inputs. No fitted parameter is renamed as a prediction, and no load-bearing result is imported solely from the authors' own prior work. Therefore the derivation chain is genuinely self-contained with respect to circularity concerns.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The ledger is light: the central theorem uses one external linear-growth lemma, a Hoffman error bound, and standard minimax facts. The user-chosen mu and eta are method parameters, not fitted values. No new physical or mathematical entities are postulated.

free parameters (2)
  • mu (perturbation strength)
    User-chosen; for exact invariance it must lie below the unknown game-dependent threshold alpha / max_{x in X} ||x||. Algorithm 1 is designed to remove the need to know this value.
  • eta (learning rate)
    User-chosen; Theorem 4.1 requires eta <= mu / (mu^2 + ||A||^2). This is a convergence constraint, not a fit to data.
assumptions (4)
  • domain assumption Existence of linear-growth constant alpha: for all x in X, max_y x^T A y - v* >= alpha dist(x, X*) (Lemma F.1, after Wei et al. 2021).
    Needed in Theorem 3.1 to show a small quadratic perturbation cannot dominate the linear objective growth. It is imported as a black box and alpha is not computable; Appendix E shows alpha can be arbitrarily small.
  • standard math Hoffman-type error bound for affine variational inequalities over polytopes (Lemma G.2).
    Used in Lemma G.1 to lower-bound the path length by the distance to Z_mu. The proof is included and relies on standard polyhedral normal cone theory.
  • standard math Minimax theorem and existence of equilibria for bilinear games over compact convex polytopes.
    Underpins the definitions of X*, Y*, and the game value v* in Section 2, and is used throughout the paper.
  • domain assumption Sequence-form polytopes for extensive-form games with perfect recall yield a bilinear saddle-point formulation.
    Needed for the extensive-form experiments and for the claim that the bilinear setting covers normal-form and extensive-form games.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Asymmetric Perturbation in Solving Bilinear Saddle-Point Optimization." pith.science (2026). https://pith.science/paper/V5MFKLF7

@misc{pith2026250605747,
  author       = {Pith},
  title        = {Pith review of: Asymmetric Perturbation in Solving Bilinear Saddle-Point Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/V5MFKLF7}},
  note         = {Machine review of arXiv:2506.05747}
}
read the original abstract

This paper proposes asymmetric perturbation, where only one player's payoff function is perturbed, for solving bilinear saddle-point optimization problems, commonly arising in minimax problems, game theory, and constrained optimization. Symmetric perturbation is known to require decreasing its strength to ensure convergence to a solution, i.e., an equilibrium in the original game, resulting in a slower rate. First, with asymmetric perturbation, we show that, for a sufficiently small perturbation strength, the equilibrium strategy of the asymmetrically perturbed game coincides with an equilibrium strategy of the original unperturbed game. Second, building on this coincidence, we construct a learning algorithm with a linear last-iterate convergence rate. Third, motivated by the fact that the coincidence relies on the perturbation strength being sufficiently small, we also provide a parameter-free variant, retaining the linear rate. Finally, we empirically demonstrate fast convergence toward equilibria in both normal-form and extensive-form games.

Figures

Figures reproduced from arXiv: 2506.05747 by the authors.

Figure 1
Figure 1. The proximity of x µ to x ∗ under the symmetric perturbation and the asymmetric perturbation with varying µ. The game matrix A is given by [[0, 1, −3], [−1, 0, 1], [3, −1, 0]]. The proximity to the minimax strategy is measured by the value of maxy∈Y (x µ ) ⊤Ay − v ∗ . et al., 2023; Sokota et al., 2023). It is known that the solution (x µ, yµ) is only an approximation of an equilibrium of the original game, with an e… view at source ↗
Figure 2
Figure 2. The landscape of the objective function for player x in asymmetrically perturbed games. The functions g(x) and g µ asym(x) are defined as g(x) := max y∈Y x ⊤Ay and g µ asym(x) := g(x) + µ 2 ∥x∥ 2 , respectively. Theorem 3.1. For any µ > 0, the minimax strategy x µ of the asymmetrically perturbed game (3) satisfies: dist(x µ , X ∗ ) ≤ 2 max  0, max x∈X ∥x∥ − α µ  , where α > 0 is a constant depending only on the or… view at source ↗
Figure 3
Figure 3. Trajectories of strategies for player x using AsymP-GDA, SymP-GDA, and GDA. The learning rate is set to η = 0.002 for all methods, and the perturbation strength is set to µ = 1.5 for AsymP-GDA and SymP-GDA. The game matrix A is set to A = [[0, 1, −3], [−1, 0, 1], [3, −1, 0]], and the strategy spaces are set to X = Y = ∆3 . The red point represents the minimax strategy of the original game. The trajectories originate… view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: Performance in extensive-form games. The y-axis reports the NashConv of the strategy pair (x t , yt ) in the original game; for AsymP-DGDA, (x t , yt ) is obtained by combining two separate runs for players x and y. The x-axis reports the total number of strategy updat…
Figure 5
Figure 5. Figure 5: The proximity of x µ to x ∗ under the symmetric perturbation and the asymmetric perturbation with varying µ. The game matrix A is given by [[ 1 3 , − 2 3 ], [− 2 3 , 1]]. A. Experimental Details and Additional Experimental Results A.1. Information on the Computer Resou…
Figure 6
Figure 6. Figure 6: Performance of AsymP-GDA, SymP-GDA, GDA, and OGDA in normal-form games. The shaded area represents the standard errors. 0.0 0.2 0.4 0.6 0.8 1.0 1.0 0.8 0.6 0.4 0.2 0.0 0.0 0.2 0.4 0.6 0.8 1.0 x1 x2 x3 SymP-GDA ( = 0.5) 0.0 0.2 0.4 0.6 0.8 1.0 1.0 0.8 0.6 0.4 0.2 0.0 0.…
Figure 7
Figure 7. Figure 7: Trajectories for SymP-GDA (top row) and AsymP-GDA (bottom row) under different perturbation strengths µ ∈ {0.5, 1.0, 2.0, 4.0} in BRPS. The learning rate is set to η = 0.002 for both methods. strengths µ ∈ {0.5, 1.0, 2.0, 4.0} in BRPS. For SymP-GDA, the trajectories do…
Figure 8
Figure 8. Figure 8: Sensitivity to the perturbation strength for AsymP-GDA with η = 0.01 in BRPS and M-Ne. asymmetric perturbations [PITH_FULL_IMAGE:figures/full_fig_p014_8.png]
Figure 9
Figure 9. Figure 9: Performance in extensive-form games. AsymP-DGDA performs two strategy updates per iteration for each player. For a fair comparison across methods with different per-iteration computational costs, we report the total number of strategy updates on the x-axis rather than …

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

51 extracted references · 43 canonical work pages

  1. [1]

    Mutation-driven follow the regularized leader for last-iterate convergence in zero-sum games

    Kenshi Abe, Mitsuki Sakamoto, and Atsushi Iwasaki. Mutation-driven follow the regularized leader for last-iterate convergence in zero-sum games. In UAI, pages 1--10, 2022

    work page 2022

  2. [2]

    Last-iterate convergence with full and noisy feedback in two-player zero-sum games

    Kenshi Abe, Kaito Ariu, Mitsuki Sakamoto, Kentaro Toyoshima, and Atsushi Iwasaki. Last-iterate convergence with full and noisy feedback in two-player zero-sum games. In AISTATS, pages 7999--8028, 2023

    work page 2023

  3. [3]

    Adaptively perturbed mirror descent for learning in games

    Kenshi Abe, Kaito Ariu, Mitsuki Sakamoto, and Atsushi Iwasaki. Adaptively perturbed mirror descent for learning in games. In ICML, pages 31--80, 2024

    work page 2024

  4. [4]

    Multiplicative weights update in zero-sum games

    James P Bailey and Georgios Piliouras. Multiplicative weights update in zero-sum games. In Economics and Computation, pages 321--338, 2018

    work page 2018

  5. [5]

    Last-iterate Convergence to Trembling-hand Perfect Equilibria

    Martino Bernasconi, Alberto Marchesi, and Francesco Trov \`o . Last-iterate convergence to trembling-hand perfect equilibria. arXiv preprint arXiv:2208.08238, 2022

    work page Pith review arXiv 2022

  6. [6]

    Convex optimization

    Stephen P Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004

    2004

  7. [7]

    Solving imperfect-information games via discounted regret minimization

    Noam Brown and Tuomas Sandholm. Solving imperfect-information games via discounted regret minimization. In AAAI, pages 1829--1836, 2019

    work page 2019

  8. [8]

    Uncoupled and convergent learning in two-player zero-sum markov games with bandit feedback

    Yang Cai, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng. Uncoupled and convergent learning in two-player zero-sum markov games with bandit feedback. In NeurIPS, pages 36364--36406, 2023

    work page 2023

Show all 51 references
  1. [9]

    Fast policy extragradient methods for competitive games with entropy regularization

    Shicong Cen, Yuting Wei, and Yuejie Chi. Fast policy extragradient methods for competitive games with entropy regularization. In NeurIPS, pages 27952--27964, 2021

    2021

  2. [10]

    Faster last-iterate convergence of policy optimization in zero-sum Markov games

    Shicong Cen, Yuejie Chi, Simon S Du, and Lin Xiao. Faster last-iterate convergence of policy optimization in zero-sum Markov games. In ICLR, 2023

    2023

  3. [11]

    Vortices instead of equilibria in minmax optimization: Chaos and butterfly effects of online learning in zero-sum games

    Yun Kuen Cheung and Georgios Piliouras. Vortices instead of equilibria in minmax optimization: Chaos and butterfly effects of online learning in zero-sum games. In COLT, volume 99, pages 807--834, 2019

    2019

  4. [12]

    Penalty-regulated dynamics and robust learning procedures in games

    Pierre Coucheney, Bruno Gaujal, and Panayotis Mertikopoulos. Penalty-regulated dynamics and robust learning procedures in games. Mathematics of Operations Research, 40 0 (3): 0 611--633, 2015

    2015

  5. [13]

    Last-iterate convergence: Zero-sum games and constrained min-max optimization

    Constantinos Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. In ITCS, pages 27:1--27:18, 2019

    2019

  6. [14]

    Training GANs with optimism

    Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. In ICLR, 2018

    2018

  7. [15]

    Convergence of optimistic gradient descent ascent in bilinear games

    \'E tienne de Montbrun and J \'e r \^o me Renault. Convergence of optimistic gradient descent ascent in bilinear games. arXiv preprint arXiv:2208.03085, 2022

    2022 arXiv

  8. [16]

    Finite-dimensional variational inequalities and complementarity problems

    Francisco Facchinei and Jong-Shi Pang. Finite-dimensional variational inequalities and complementarity problems. Springer, 2003

    2003

  9. [17]

    A variational inequality perspective on generative adversarial networks

    Gauthier Gidel, Hugo Berard, Ga \" e tan Vignoud, Pascal Vincent, and Simon Lacoste - Julien. A variational inequality perspective on generative adversarial networks. In ICLR , 2019

    2019

  10. [18]

    Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems

    Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman Ozdaglar. Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems. In COLT, pages 1758--1784, 2020

    2020

  11. [19]

    Asymptotic convergence and performance of multi-agent q-learning dynamics

    Aamal Abbas Hussain, Francesco Belardinelli, and Georgios Piliouras. Asymptotic convergence and performance of multi-agent q-learning dynamics. In AAMAS, page 1578^^e2^^80^^931586, 2023

    2023

  12. [20]

    Single timescale regularized stochastic approximation schemes for monotone nash games under uncertainty

    Jayash Koshal, Angelia Nedi \'c , and Uday V Shanbhag. Single timescale regularized stochastic approximation schemes for monotone nash games under uncertainty. In CDC, pages 231--236. IEEE, 2010

    2010

  13. [21]

    Shanbhag

    Jayash Koshal, Angelia Nedic, and Uday V. Shanbhag. Regularized iterative stochastic approximation methods for stochastic variational inequality problems. IEEE Transactions on Automatic Control, 58 0 (3): 0 594--609, 2013

    2013

  14. [22]

    Openspiel: A framework for reinforcement learning in games

    Marc Lanctot, Edward Lockhart, Jean-Baptiste Lespiau, Vinicius Zambaldi, Satyaki Upadhyay, Julien P \'e rolat, Sriram Srinivasan, Finbarr Timbers, Karl Tuyls, Shayegan Omidshafiei, et al. Openspiel: A framework for reinforcement learning in games. arXiv preprint arXiv:1908.09453, 2019

    1908 arXiv

  15. [23]

    Last-iterate convergence in extensive-form games

    Chung-Wei Lee, Christian Kroer, and Haipeng Luo. Last-iterate convergence in extensive-form games. NeurIPS, pages 14293--14305, 2021

    2021

  16. [24]

    Fundamental benefit of alternating updates in minimax optimization

    Jaewook Lee, Hanseul Cho, and Chulhee Yun. Fundamental benefit of alternating updates in minimax optimization. In ICML, pages 26439--26514, 2024

    2024

  17. [25]

    Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes

    Qi Lei, Sai Ganesh Nagarajan, Ioannis Panageas, and xiao wang. Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes. In AISTATS , volume 130, pages 1441--1449, 2021 a

    2021

  18. [26]

    Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes

    Qi Lei, Sai Ganesh Nagarajan, Ioannis Panageas, et al. Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes. In AISTATS, pages 1441--1449, 2021 b

    2021

  19. [27]

    Individual q-learning in normal form games

    David S Leslie and Edmund J Collins. Individual q-learning in normal form games. SIAM Journal on Control and Optimization, 44 0 (2): 0 495--514, 2005

    2005

  20. [28]

    Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks

    Tengyuan Liang and James Stokes. Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks. In AISTATS, pages 907--915, 2019

    2019

  21. [29]

    The power of regularization in solving extensive-form games

    Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu, and Kaiqing Zhang. The power of regularization in solving extensive-form games. In ICLR, 2023

    2023

  22. [30]

    Learning in games with continuous action sets and unknown payoff functions

    Panayotis Mertikopoulos and Zhengyuan Zhou. Learning in games with continuous action sets and unknown payoff functions. Mathematical Programming, 173 0 (1): 0 465--507, 2019

    2019

  23. [31]

    Cycles in adversarial regularized learning

    Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. In SODA, pages 2703--2717, 2018

    2018

  24. [32]

    Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile

    Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In ICLR, 2019

    2019

  25. [33]

    A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach

    Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In AISTATS, pages 1497--1507, 2020

    2020

  26. [34]

    Nash learning from human feedback

    Remi Munos, Michal Valko, Daniele Calandriello, Mohammad Gheshlaghi Azar, Mark Rowland, Zhaohan Daniel Guo, Yunhao Tang, Matthieu Geist, Thomas Mesnard, C \^o me Fiegel, Andrea Michi, Marco Selvi, Sertan Girgin, Nikola Momchev, Olivier Bachem, Daniel J Mankowitz, Doina Precup,...

    2024

  27. [35]

    Symmetric (optimistic) natural policy gradient for multi-agent learning with parameter convergence

    Sarath Pattathil, Kaiqing Zhang, and Asuman Ozdaglar. Symmetric (optimistic) natural policy gradient for multi-agent learning with parameter convergence. In AISTATS, pages 5641--5685, 2023

    2023

  28. [36]

    From Poincar \'e recurrence to convergence in imperfect information games: Finding equilibrium via regularization

    Julien Perolat, Remi Munos, Jean-Baptiste Lespiau, Shayegan Omidshafiei, Mark Rowland, Pedro Ortega, Neil Burch, Thomas Anthony, David Balduzzi, Bart De Vylder, et al. From Poincar \'e recurrence to convergence in imperfect information games: Finding equilibrium via regulariza...

    2021

  29. [37]

    Connor, Neil Burch, Thomas Anthony, Stephen McAleer, Romuald Elie, Sarah H

    Julien Perolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T. Connor, Neil Burch, Thomas Anthony, Stephen McAleer, Romuald Elie, Sarah H. Cen, Zhe Wang, Audrunas Gruslys, Aleksandra Malysheva, Mina Khan, Sherjil Ozair, F...

    2022

  30. [38]

    Online learning with predictable sequences

    Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In COLT, pages 993--1019, 2013 a

    2013

  31. [39]

    Optimization, learning, and games with predictable sequences

    Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In NeurIPS, pages 3066--3074, 2013 b

    2013

  32. [40]

    Variational analysis, volume 317

    R Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009

    2009

  33. [41]

    Online learning and online convex optimization

    Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and trends in Machine Learning, 4 0 (2): 0 107--194, 2011

    2011

  34. [42]

    A unified approach to reinforcement learning, quantal response equilibria, and two-player zero-sum games

    Samuel Sokota, Ryan D'Orazio, J Zico Kolter, Nicolas Loizou, Marc Lanctot, Ioannis Mitliagkas, Noam Brown, and Christian Kroer. A unified approach to reinforcement learning, quantal response equilibria, and two-player zero-sum games. In ICLR, 2023

    2023

  35. [43]

    Solving large imperfect information games using CFR+

    Oskari Tammelin. Solving large imperfect information games using CFR+ . arXiv preprint arXiv:1407.5042, 2014

    2014 arXiv

  36. [44]

    Learning Nash equilibria in monotone games

    Tatiana Tatarenko and Maryam Kamgarpour. Learning Nash equilibria in monotone games. In CDC, pages 3104--3109. IEEE, 2019

    2019

  37. [45]

    An evolutionary dynamical analysis of multi-agent learning in iterated games

    Karl Tuyls, Pieter Jan Hoen, and Bram Vanschoenwinkel. An evolutionary dynamical analysis of multi-agent learning in iterated games. Autonomous Agents and Multi-Agent Systems, 12 0 (1): 0 115^^e2^^80^^93153, 2006

    2006

  38. [46]

    J v. Neumann. Zur theorie der gesellschaftsspiele. Mathematische annalen, 100 0 (1): 0 295--320, 1928

    1928

  39. [47]

    Efficient computation of behavior strategies

    Bernhard von Stengel . Efficient computation of behavior strategies. Games and Economic Behavior, 14 0 (2): 0 220--246, 1996

    1996

  40. [48]

    Linear last-iterate convergence in constrained saddle-point optimization

    Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence in constrained saddle-point optimization. In ICLR, 2021

    2021

  41. [49]

    On smoothing, regularization, and averaging in stochastic approximation methods for stochastic variational inequality problems

    Farzad Yousefian, Angelia Nedi\' c , and Uday V Shanbhag. On smoothing, regularization, and averaging in stochastic approximation methods for stochastic variational inequality problems. Mathematical Programming, 165: 0 391--431, 2017

    2017

  42. [50]

    Near-optimal local convergence of alternating gradient descent-ascent for minimax optimization

    Guodong Zhang, Yuanhao Wang, Laurent Lessard, and Roger B Grosse. Near-optimal local convergence of alternating gradient descent-ascent for minimax optimization. In AISTATS, pages 7659--7679, 2022

    2022

  43. [51]

    Regret minimization in games with incomplete information

    Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. In NeurIPS, pages 1729--1736, 2007

    2007

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.