Stability and Convergence of Optimistic Exponential Weights with Asymmetric Step Sizes in Bimatrix Games
For researchers in game theory and online learning, this work extends convergence guarantees to asymmetric step sizes, offering practical guidance for algorithm design.
The paper studies optimistic exponential weights in bimatrix games with asymmetric step sizes, proving a sufficient condition for global last-iterate convergence in zero-sum games (constraining only the product of step sizes) and an almost-tight threshold for stability in general bimatrix games. The results explain empirically observed behavior and provide theoretical insights.
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.