cs.AIJul 9, 2024

Games played by Exponential Weights Algorithms

Authors: Maurizio d'Andrea, Fabien Gensbittel, Jérôme Renault

Organizations: TSE-R

Abstract

This paper studies the last-iterate convergence properties of the exponential weights algorithm with constant learning rates. We consider a repeated interaction in discrete time, where each player uses an exponential weights algorithm characterized by an initial mixed action and a fixed learning rate, so that the mixed action profile ptp^t played at stage tt follows an homogeneous Markov chain. At first, we show that whenever a strict Nash equilibrium exists, the probability to play a strict Nash equilibrium at the next stage converges almost surely to 0 or 1. Secondly, we show that the limit of ptp^t, whenever it exists, belongs to the set of ``Nash Equilibria with Equalizing Payoffs''. Thirdly, we show that in strong coordination games, where the payoff of a player is positive on the diagonal and 0 elsewhere, ptp^t converges almost surely to one of the strict Nash equilibria. We conclude with open questions.

Explore similar work

Jul 8, 2026

Stability and Convergence of Optimistic Exponential Weights with Asymmetric Step Sizes in Bimatrix Games

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\eta_x and ηy\eta_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\eta_x\eta_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.
Apr 17, 2026

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback

We study the problem of learning in zero-sum matrix games with repeated play and bandit feedback. Specifically, we focus on developing uncoupled algorithms that guarantee, without communication between players, the convergence of the last-iterate to a Nash equilibrium. Although the non-bandit case has been studied extensively, this setting has only been explored recently, with a bound of O(T−1/8)\mathcal{O}(T^{-1/8}) on the exploitability gap. We show that, for uncoupled algorithms, guaranteeing convergence of the policy profiles to a Nash equilibrium is detrimental to the performance, with the best attainable rate being Ω(T−1/4)Ω(T^{-1/4}) in contrast to the usual Ω(T−1/2)Ω(T^{-1/2}) rate for convergence of the average iterates. We then propose two algorithms that achieve this optimal rate up to constant and logarithmic factors. The first algorithm leverages a straightforward trade-off between exploration and exploitation, while the second employs a regularization technique based on a two-step mirror descent approach.
Sep 28, 2026

Minimax Last-Iterate Convergence in Matrix Games with Observed Actions

We study last-iterate convergence in unknown two-player zero-sum matrix games with bandit payoff feedback and observed opponent actions. For games with dd actions per player, we develop an algorithm achieving a duality gap of O~(d/t)\widetilde{\mathcal{O}}(\sqrt{d/t}) with high probability, simultaneously at every round tt. This improves the dimension dependence of the best previously known guarantee by a factor of d3/2d^{3/2}. The rate matches a standard bandit lower bound, establishing minimax optimality in both the number of actions and the number of rounds, up to logarithmic factors. The algorithm is computationally efficient, requiring only O(d)\mathcal{O}(d) time and memory per round. Our technical contribution is a joint design of adaptive averaging and corrected exponential weights that absorbs estimation variance, together with a potential argument that bounds phase durations.