Asymmetric Perturbation in Solving Bilinear Saddle-Point Optimization

Kenshi Abe, Mitsuki Sakamoto, Kaito Ariu, Atsushi IwasakiSubmission to ICLR 2026 · Withdrawn

Its authors withdrew this paper, so there is no full text to read or summarize.

Abstract

This paper proposes an asymmetric perturbation technique for solving bilinear saddle-point optimization problems, commonly arising in minimax problems, game theory, and constrained optimization. Perturbing payoffs or values is known to be effective in stabilizing learning dynamics and equilibrium computation. However, it requires careful adjustment of the perturbation magnitude; otherwise, learning dynamics converge to only an approximate equilibrium. To overcome this, we introduce an asymmetric perturbation approach, where only one player's payoff function is perturbed. Exploiting the near-linear structure of bilinear problems, we show that, for a sufficiently small perturbation, the equilibrium strategy of the asymmetrically perturbed game coincides with an equilibrium strategy of the original game. This property yields a perturbation-based learning algorithm that achieves convergence to an equilibrium strategy in the original game without requiring parameter adjustments. Furthermore, we empirically demonstrate fast convergence toward equilibria in both normal-form and extensive-form games.
BibTeX
@inproceedings{abe2026asymmetric,
  author = {Kenshi Abe and Mitsuki Sakamoto and Kaito Ariu and Atsushi Iwasaki},
  title = {{Asymmetric Perturbation in Solving Bilinear Saddle-Point Optimization}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=fyae4jQ9Lw},
}
Figure