Stability and Convergence of Optimistic Exponential Weights with Asymmetric Step Sizes in Bimatrix Games
Abstract
We study bimatrix two-player games and investigate the last-iterate convergence and stability of equilibria for the iterates generated by the optimistic exponential weights method. In contrast to prior work, we allow the step sizes ηx and ηy to differ. Our first main result establishes, under the assumption that the set of fixed points is finite, a sufficient condition for global last-iterate convergence in the special case of zero-sum games, which constrains only the product ηxηy of the step sizes. This condition is practically relevant and partially explains empirically observed behavior. Our second main result provides an almost-tight threshold for asymptotic stability and instability, again in terms of products of the step sizes, for general bimatrix games. This result is primarily of theoretical interest. We derive several known results and practically relevant step size bounds for special cases and illustrate our results by experiments.
Related
- Exponential Convergence of the Sinkhorn Algorithm for the Schrödinger Bridge with Regime Switching
- Exponential convergence to a steady-state for a population genetics model with sexual reproduction and selection
- Near-Exponential Convergence Rates for kNN Classification based on Boltzmann Margin
- Exponential convergence of Sinkhorn algorithm for entropy martingale optimal transport
- Combining Exponential and Polynomial Convergence Rates for Accelerated Extremum Seeking: A High-Order Lie Bracket Approach
BibTeX
@misc{hadiji2026stability,
title = {{Stability and Convergence of Optimistic Exponential Weights with Asymmetric Step Sizes in Bimatrix Games}},
author = {Hédi Hadiji and Sarah Sachs},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.07517},
eprint = {2607.07517},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.07517},
}
RIS
TY - UNPB
TI - Stability and Convergence of Optimistic Exponential Weights with Asymmetric Step Sizes in Bimatrix Games
AU - Hédi Hadiji
AU - Sarah Sachs
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2607.07517
UR - https://arxiv.org/abs/2607.07517
AB - We study bimatrix two-player games and investigate the last-iterate convergence and stability of equilibria for the iterates generated by the optimistic exponential weights method. In contrast to prior work, we allow the step sizes η_x and η_y to differ. Our first main result establishes, under the assumption that the set of fixed points is finite, a sufficient condition for global last-iterate convergence in the special case of zero-sum games, which constrains only the product η_xη_y of the step sizes. This condition is practically relevant and partially explains empirically observed behavior. Our second main result provides an almost-tight threshold for asymptotic stability and instability, again in terms of products of the step sizes, for general bimatrix games. This result is primarily of theoretical interest. We derive several known results and practically relevant step size bounds for special cases and illustrate our results by experiments.
ER -