acceptodds
Under review as a conference paper at ICLR 2027

Beyond KL Divergence: General Payoff Perturbations in Extensive-Form Games

Abstract

Payoff perturbation is a useful principle for last-iterate convergence in games, but existing analyzes of behavioral-form Follow-the-Regularized-Leader (FTRL) in extensive-form games have focused mainly on a KL reward transformation. We use a strongly convex potential to construct Bregman-based payoff adjustments at each history–action pair relative to a anchoring strategy profile, and show that these adjustments make a global Lyapunov function decrease. Under explicit regularity assumptions, this yields last-iterate convergence of continuous-time perturbed FTRL (PFTRL) to a stationary point of the modified game when the anchoring strategy profile is held fixed. We instantiate the framework with KL and reverse-KL perturbations and derive a specialized perturbation and convergence result for two-player zero-sum games. Building on anchoring strategy updates from prior work, we also analyze an idealized outer iteration that solves each modified game exactly before updating the anchoring strategy profile; this result does not cover the finite-inner-loop discrete-time implementation. Experiments on two-player zero-sum benchmarks show that discrete-time PFTRL substantially reduces last-iterate exploitability, while perturbed CFR+ variants remain the strongest solver-level baselines in most settings.

Primary area:
learning theory
Keywords:
learning in games, extensive-form games, payoff perturbation, last-iterate convergence

Reviews

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

This paper studies last-iterate convergence of Follow-the-Regularized-Leader (FTRL) in extensive-form games. The authors propose a general payoff perturbation framework based on Bregman divergences, extending the existing KL-based approach. They provide convergence analysis for continuous-time perturbed FTRL in monotone games and introduce a separate perturbation for two-player zero-sum games. Experiments on several benchmark games compare the proposed PFTRL variants with CFR-based methods and show that PFTRL can achieve low exploitability, although PCFR+ performs better in most cases.

Critical strengths
  1. The presentation of this paper is complete.
  2. The topic of this work is interesting and useful for the game field, especially imperfect-information games.
  3. The paper seems to provide a set of solid mathematical proofs.
Critical weaknesses
  1. The writing style of this article is rather difficult to understand. In the introduction, the author does not clearly summarize their contributions. This writing style is not friendly to the readers.
  2. The structure of Section 4 and 5 is rather chaotic. The logical connections between lemmas, theorems, and corollaries are not clear enough, making it difficult for readers to understand the necessity of reading this section or what information they can gain from it. For example, what is the relation among Theorem 3, Theorem 9, and Theorem 11?
  3. The presentation in Figure 1 fails to effectively demonstrate the advantages of the proposed method. From Figure 1, the baseline method appears to outperform the proposed method.
Questions for authors

Please review my weaknesses.

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

The authors study the by-now-common framework of perturbing payoffs to improve convergence to equilibria in games. By my understanding, the main contribution of the paper is to generalize the framework, which has previously been studied primarily for KL divergence and L2, to arbitrary Bregman divergences. By specializing back to particular Bregman divergences, they recover algorithms for two-player monotone (e.g., zero-sum) extensive-form games with guaranteed (continuous-time) convergence.

Critical strengths

The framework developed seems general, and the algorithms seem reasonably effective in both theory and practice.

Critical weaknesses

The paper is missing the required AI disclosure statement. However, at least the writing in the paper does not seem fully AI-generated. I will therefore give this paper a proper review in spite of the lack of AI disclosure.

I would avoid calling the perturbed CFR+ algorithm "PCFR+". This initialism has already been taken by predictive CFR+. In this review I will consistently write out "Perturbed" and "Predictive" CFR+ to avoid this confusion.

The writing in some places has the same confusing exposition quirks that a lot of AI mathematical writing does. I suggest that the authors do a pass and rewrite everything in their own words; this would improve readability.

As a related notes, the authors should test their algorithm against Predictive CFR+. For extensive-form games in particular it is often difficult to beat even for more theoretically-sound algorithms--see, for example, this paper. Moreover, Predictive CFR+ and many variants thereof require no tuning of hyperparameters.

Overall, I found the results somewhat underwhelming.

Experimentally, despite the perhaps-more-theoretically-friendly nature of the proposed algorithm, in experiments, it seems consistently outperformed by Perturbed CFR+. Moreover, the algorithms--unlike the more basic CFR+ algorithm and its predictive variants seem to require careful tuning of hyperparameters. As such, both practically and theoretically, I see little reason to prefer the algorithms presented in this paper over those already known in the literature.

Theoretically, discrete time behaves very differently from continuous time. I would like to see discrete-time convergence results as well, paralleling those commonly found for CFR-based algorithms in extensive-form games. Even average-iterate results are better than nothing. Moreover, the results and frameworks given by the authors do not seem significantly different from those given in earlier works of Perolat et al and Meng et al (see Questions below).

Questions for authors

The comparison between the algorithms in the present paper and the algorithms proposed by past work was not fully clear to me. For example, besides the normalization by the size of the information set (which in my opinion is not important conceptually),

  • is there any difference between PFTRL with KL-divergence and the algorithm of Perolat et al.?
  • is there any difference between PFTRL with L2 distance and the algorithm of Meng et al.?
Reviewer_DAVEOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper considers NN players games in which players take actions sequentially and studies how to make learning algorithms converge to stable strategies. Traditional methods like FTRL are shown to be stable when modifying players' payoffs using KL divergence. This paper asks whether this result is limited to KL or can other adjustments like Bregman-based could also make the learning stabalized. In addition, Authors show in Theorem 9 that under some conditions, the method will converge to the original Nash equilibrium (before modifying the players' payoff).

Critical strengths

Extending the notion of distance to a broader family which is not just limited to KL is interesting.

Critical weaknesses

The paper is very hard to read and follow. Too many notations are used which made the paper unreadable and confusing. The experiment section is not sufficiently discussed and is not informative. The proofs of lemmas and theorems in appendix (e.g, AppendixG pages 22–28) are not clearly written and very hard to follow without any explanation about the steps and what is the core idea behind the proof.

Questions for authors

Is the negative sign in eq 16 correct? can you explain why is there a minus sign?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.