acceptodds
Withdrawn from ICLR 2027

Best Response Convergence

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

As players update their strategies through repeated interaction within a multi-player game, they may increasingly favor one action while another is currently more profitable. Even when their behavior converges, small changes in the opponents' play can keep changing which of their actions is best. We study this distinction for follow-the-regularized-leader (FTRL). More specifically, we ask whether a fixed action eventually remains a current best response. To do this, we analyze learning near boundary equilibria—a subclass of weak Nash equilibria—where one player's limiting action is tied with several unused actions, which we call alternatives. We derive tight rates for the probabilities of these alternatives and identify a sharp best-response threshold for the Hedge algorithm, the entropy-regularized form of FTRL. With symmetric learning rates , the threshold is , independently of the number of alternatives. We also show an interesting consequence of our analysis: larger learning rates can make the gains from deviation vanish more slowly, despite faster concentration on the limiting action. Lastly, we also prove a best-response stability result for Euclidean FTRL and verify our findings using simulations.

Primary area:
learning theory
Keywords:
Best response, Last iterate convergence, FTRL, Learning dynamics

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_JodsOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the stability of the best-response (BR) correspondence along the trajectories of continuous-time FTRL with time-varying learning rates in a specific family of two-player games. For entropic FTRL (Hedge), it establishes a threshold above which one player's BR eventually stabilizes to a unique action and below which it switches infinitely often for almost every initialization. The authors also obtain a similar threshold for Tsallis FTRL and a sufficient stability condition for Euclidean FTRL, in a more restricted setting.

Critical strengths

The main result is interesting and technically nontrivial. I particularly appreciate the sharp threshold for best-response stabilization and the use of energy techniques and volume preservation in its proof.

Critical weaknesses

First, I am not entirely convinced that eventual stabilization of instantaneous best responses is an important property of learning dynamics given that the phenomenon studied occurs near a non-strict Nash equilibrium where payoff differences vanish. Thus, even when best responses change infinitely often, the gains from deviation converge to zero and the players' strategies converge to a Nash equilibrium. This leaves me rather perplexed and I do not think the importance of this question is sufficiently motivated, so I find the game-theoretic significance of these best-response changes somewhat unclear. Note also that the payoff gap results partly address this concern, but the implications remain limited to this very specific setting, which brings me to my second point.

Indeed, I find the results rather too specialized. The main theorem concerns a specific family of games with a very particular payoff structure and, much more importantly, the switching best response relies crucially on the time-varying learning rates. Indeed, in the two-action game, infinitely many best response changes are impossible under constant learning rates since player B's cumulative payoff difference is monotone so player A's instantaneous payoff difference is monotone as well and its best response cannot change more than once. I find this particularly important because autonomous continuous-time FTRL is the standard and most extensively studied model in the literature and stochastic approximation theory shows that these autonomous dynamics arise as the mean-field limit of standard discrete-time learning algorithms, including Hedge with diminishing step sizes (see Mertikopoulos et al., 2024, "A Unified Stochastic Approximation Framework for Learning in Games"). Hence I would have liked a stronger justification for focusing on these particular nonautonomous dynamics, as well as evidence that the phenomenon extends beyond the specific games considered.

Finally, I found the exposition somewhat dense in places, making the main text and the analysis harder to follow than necessary.

Questions for authors
  1. Could you elaborate on why eventual stabilization of instantaneous best responses is important from a game-theoretic or learning perspective, given that strategies converge to Nash equilibrium and gains from deviation vanish even when best responses keep switching ?
  2. What motivates your particular formulation of time-varying FTRL, given that autonomous FTRL also arises as the mean-field limit of discrete-time learning algorithms with diminishing step sizes ?
  3. What is the motivation for studying this specific family of games beyond illustrating the possibility of infinitely many best response changes ? Do you expect the switching to extend to more general games ?
  4. Do you expect the sharp threshold established in Theorem 3 to extend to the discrete-time Hedge algorithm ? Is there a way to establish this rigorously, beyond the numerical evidence provided ?
Reviewer_B3t7OpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies whether convergence of mixed strategies under follow-the-regularized-leader (FTRL) guarantees convergence of current best responses. The authors focus on boundary equilibria, where one player converges to a pure action while other actions yield the same payoff at the limit. For Hedge in (k)-boundary games, they identify a learning-rate threshold separating best-response stability from infinitely many best-response switches. They also derive convergence rates for the weighted payoff gap, consider other regularizers, and provide simulations in inspection games and discrete-time FTRL.

Critical strengths

I find it interesting that a larger learning rate can lead to faster concentration on the limiting action while the current best response keeps switching. Theorem 3 identifies an explicit threshold separating best-response stability from infinitely many switches under Hedge. I believe that this result provides useful insight into how the learning rate affects the difference between strategy convergence and best-response stability.

Critical weaknesses

My main concern is that the practical importance of best-response stability is not sufficiently explained. The introduction provides examples involving inspection and compliance, first-price auctions, and investment and repayment, but it is unclear in which situations infinitely many best-response switches would cause a practical problem. For example, in the inspection game, a violation may repeatedly become a current best response, but the gain from deviation can still vanish as the mixed strategies converge. I believe that explaining why best-response stability matters beyond last-iterate convergence and vanishing deviation gains would make the motivation clearer.

Additionally, I found it difficult to identify the main message of the paper. Paragraph headings are frequently used, and definitions and results are presented with similar emphasis, making it unclear which results are the main contributions and which are supporting results. Technical assumptions are also introduced by referring to later results before explaining what those results establish. For example, Section 3 states, “To derive the probability rate in Theorem 1,” and introduces an assumption on player B’s probabilities. However, the probability rate being studied and the purpose of Theorem 1 have not yet been explained, making it difficult to understand why this assumption is needed at that point. Moreover, Proposition 1 refers to conditions in Appendix A without stating them in the main text. I believe that explaining the purpose of each result before introducing its technical assumptions would make the paper easier to follow and help clarify its main message.

Questions for authors

My main concerns and questions are outlined in the Critical Weaknesses section.

Reviewer_LtpzOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

This paper studies whether convergence of mixed strategies under Follow-the-Regularized-Leader (FTRL) dynamics implies eventual stability of their current best responses. The authors focus on a family of two-player games with non-strict Nash equilibria and establish a sharp learning-rate threshold for best-response stability under Hedge.

Critical strengths

The paper addresses an interesting distinction between convergence of mixed strategies and stability of their best responses. The theoretical analysis appears technically substantial, particularly the characterization of sharp learning-rate thresholds and convergence rates.

Critical weaknesses

My main concern is the motivation and significance of studying best-response stability along FTRL dynamics. FTRL does not use instantaneous best responses in its updates. Moreover, the paper establishes that the mixed strategies converge to a Nash equilibrium while the gains from unilateral deviations vanish. It is therefore unclear what is lost when the identity of the current best response continues to change infinitely often.

As I understand it, the phenomenon concerns the trajectory approaching an equilibrium rather than a stability property of the equilibrium itself. The results also do not directly establish a vulnerability of FTRL against strategically responding opponents. I would appreciate a clearer explanation of what additional insight best-response stability provides beyond convergence to Nash equilibrium and vanishing deviation gains.

I also have some concerns regarding the presentation. The introduction does not sufficiently motivate the research question and contains relatively few references to position it within the existing literature. The title is too general and does not reflect the focus on FTRL. The abstract is difficult to follow, particularly because different notions of convergence, including strategy convergence, best-response stability, and payoff convergence, are discussed without clearly distinguishing them. The precise scope of the results could also be communicated more explicitly.

Questions for authors

What is the significance of eventual best-response stability when the learning dynamics already converge to a Nash equilibrium and the gains from unilateral deviations vanish? Can the authors provide an example in which persistent best-response switching has meaningful consequences for learning or strategic decision-making?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.