acceptodds
Under review as a conference paper at ICLR 2027

Last-Iterate Convergence of Optimistic Gradient Descent-Ascent in Behavioral Form for Extensive-Form Games

Abstract

This paper shows that a simple learning algorithm in the behavioral-form representation of extensive-form games (EFGs) achieves last-iterate convergence, without modifying the game or enforcing exploration. Existing last-iterate guarantees for EFGs are developed mainly in sequence form, while behavioral-form guarantees often rely on regularization or payoff perturbation. Our method applies simultaneous optimistic gradient descent-ascent (OGDA) with independent Euclidean projections at each information set, using ordinary counterfactual values. We show that, for every perfect-recall, two-player zero-sum EFG, any fixed step size below a positive threshold yields last-iterate convergence. Because this guarantee does not follow from the sequence-form analysis, our analysis instead compares the behavioral-form dynamics with sequence-form dilated OGDA and controls the additional correction term that ordinary counterfactual values introduce. We also provide a parameter-free variant that halves the step size until it is small enough and achieves last-iterate convergence for any initial step size. Experiments on benchmark games are consistent with last-iterate convergence.

Primary area:
reinforcement learning
Keywords:
learning in games, last-iterate convergence, extensive-form games

Reviews

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

The paper studies simultaneous optimistic updates applied directly to behavioral strategies in finite two-player zero-sum extensive-form games with perfect recall. At each information set, the algorithm uses ordinary counterfactual values and performs independent Euclidean projections. It is proven in Theorem 6.1 that behavioral sequences can approach the Nash set with a sufficiently small fixed step size.

Critical strengths
  1. The result targets Nash equilibria of the original game. It does not replace the game with a regularized objective.
  2. The paper explains why separate local projections differ from a global treeplex proximal update. The proof does more than change coordinates.
  3. The strictly complementary reference equilibrium gives two useful controls: positive reach weights and positive dual slacks.
  4. The adaptive scheme avoids needing a safe threshold in advance. The experiments measure the current played policy's exploitability, which matches the last-iterate claim.
Critical weaknesses
  1. The update description is inconsistent. Section 5.1, lines 271–272, says that prediction and correction evaluate different profiles. Equation (2) and Algorithm 1 use the same previous-profile oracle for both projections.
  2. The guarantee is asymptotic. The safe threshold depends on equilibrium-related quantities. The adaptive theorem shows that step-size halving eventually stops.
Questions for authors

none

3 comments

Thank you for your positive assessment of our work and for your helpful comments.


On the Update Description in Section 5.1

You are correct. Both projections use the same value vector vi,I(πt−1)v_{i,I}(\pi^{t-1}), as stated in Eq. (2) and Algorithm 1. We have corrected the sentence in Section 5.1 accordingly.


On the Asymptotic Guarantee and the Step-Size Threshold

We agree that the convergence guarantee remains asymptotic. The purpose of the adaptive variant is to remove the need to know the equilibrium-dependent step-size threshold in advance. Theorem 6.4 guarantees that, from any positive initial step size, only finitely many halvings occur and the output sequences converge to the Nash equilibrium set. Although the bound on the number of halvings depends on equilibrium quantities, the algorithm does not require these quantities as input.

Thank you the response. I have read it and I will keep my rating.

Thank you for your constructive feedback and continued positive evaluation of our work.

Reviewer_JnL8OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies last-iterate convergence of Behavioral OGDA in two-player zero-sum perfect-recall extensive-form games, using independent local projections without game regularization or enforced exploration. They prove asymptotic last-iterate convergence to Nash equilibrium under sufficiently small fixed step sizes. They also introduce an adaptive variant that reduces the step size when a convergence-related condition is violated. Experiments on benchmark games show convergence behavior consistent with the theoretical results.

Critical strengths

The paper establishes last-iterate convergence for Behavioral OGDA without requiring game regularization or a lower bound on reach probabilities. The analysis is nontrivial because the independent behavioral updates do not directly satisfy the global potential argument used for sequence-form dilated OGDA. The proposed method uses independent local Euclidean projections with ordinary counterfactual values, making the updates straightforward to implement. The authors also provide a detailed comparison with dilated OGDA and introduce an adaptive variant that guarantees convergence without prior knowledge of the equilibrium-dependent step-size threshold.

Critical weaknesses
  1. The paper establishes asymptotic last-iterate convergence but does not provide a finite-time convergence rate. Since several existing methods for extensive-form games have quantitative convergence guarantees, it remains unclear how the convergence speed of Behavioral OGDA compares theoretically with these alternatives. Even a finite-time result under additional assumptions or for certain subclasses of games would strengthen the theoretical contribution.

  2. Although the paper emphasizes the simplicity of independent behavioral updates, the experimental performance of Behavioral OGDA is generally comparable to, or sometimes slightly worse than, dilated OGDA with suitable fixed step sizes. Moreover, the experiments compare methods using the number of full-tree counterfactual-value evaluations rather than wall-clock runtime. It is therefore unclear whether the simpler updates provide a meaningful computational advantage over the existing sequence-form baseline.

Questions for authors
  1. Could the authors provide runtime comparisons to demonstrate whether the simpler behavioral updates lead to computational savings?

  2. Could a similar adaptive step-size strategy also be applied to dilated OGDA? It would be helpful to clarify whether the proposed adaptive approach offers any particular advantage for Behavioral OGDA.

  3. The experiments suggest that different games favor different step sizes. Is it possible to determine a suitable step size in advance based on properties of the game, such as payoff magnitude or game-tree structure? Since the theoretical threshold depends on unknown equilibrium quantities, a more practical step-size selection condition would help clarify the applicability of the proposed method.

  4. Could the method be extended beyond two-player zero-sum perfect-recall games, for example, to imperfect-recall or structured multiplayer/general-sum games?

4 comments
AuthorsOpenReview ↗

Response to Reviewer JnL8 (1/2)

Thank you for taking the time to review our work and for providing your valuable feedback. Our detailed responses to your comments and questions are provided below.


On the Finite-Time Last-Iterate Convergence Rate

We agree that a finite-time last-iterate convergence rate would strengthen our result. However, even for the closest sequence-form baseline, dilated OGDA with the dilated Euclidean regularizer, only asymptotic last-iterate convergence has been established (Lee et al., 2021); to the best of our knowledge, an explicit finite-time rate remains unknown. This difficulty stems largely from the lack of global smoothness of the regularizer, which prevents a direct application of the linear-convergence analysis for vanilla Euclidean OGDA.

Our analysis faces the same difficulty and must additionally control the behavioral correction term in Eq. (9), which arises from independent behavioral updates. Specifically, Lemmas 6.2 and 6.3 show that these correction terms can be absorbed into the descent inequality, allowing us to establish last-iterate convergence. However, the resulting bound does not quantify how quickly the iterates approach equilibrium. Establishing an explicit finite-time last-iterate convergence rate therefore remains an important direction for future work.


On the Advantages of Behavioral Updates and Runtime Comparison

We would like to emphasize that the advantages of behavioral updates go beyond their per-iteration cost. First, they directly learn a policy that maps information sets to action probabilities. This representation naturally accommodates function approximation, making it suitable for learning in large games where maintaining a tabular strategy is impractical. Second, they allow a local regret minimizer to be chosen at each information set, so standard online learning algorithms over the simplex can be used directly. This provides flexibility in designing learning methods without constructing a global sequence-form update. Our contribution is to establish last-iterate convergence for the direct application of OGDA in this behavioral formulation.

We have also added a runtime comparison in Appendix D.1 (Figure 3). When measured against runtime, Behavioral OGDA shows faster empirical convergence than dilated OGDA in four of the five tested games. In contrast, Adaptive Behavioral OGDA incurs additional computation for the test in Eq. (10), making its relative performance less favorable when measured against runtime.

AuthorsOpenReview ↗

Response to Reviewer JnL8 (2/2)

On Applying Step-Size Adaptation to Sequence-Form Dilated OGDA

We agree that step-size adaptation could also be applied to sequence-form dilated OGDA. However, when the dilated regularizer is 1-strongly convex with respect to the Euclidean norm, the standard analysis of dilated OGDA provides a sufficient step-size bound in terms of the Lipschitz constant of FF defined in Section 5.1, which can be bounded directly from the known payoff matrix (Lee et al., 2021). Thus, a fixed step size ensuring last-iterate convergence can be specified from known problem constants, without equilibrium information.

In contrast, the threshold in our Theorem 6.1 depends on the minimum positive coordinate of ZscZ^{\mathrm{sc}} and the minimum positive dual slack of a strictly complementary equilibrium. These quantities are unavailable before solving the game, so our bound does not directly provide an implementable step-size choice. This motivates our adaptive variant, which halves the step size whenever the observable test in Eq. (10) fails. For sufficiently small step sizes, the test holds at every iteration, so only finitely many halvings can occur. Moreover, any fixed-step run that continues to satisfy the test converges. Together, these properties yield Theorem 6.4 without prior knowledge of the equilibrium-dependent threshold. This is the purpose of adaptation in our method.


On Selecting a Step Size from Game Properties

Our theoretical step-size bound depends on unknown equilibrium quantities, making it difficult to choose a suitable step size in advance. Nevertheless, our experiments suggest that larger step sizes accelerate convergence within the stable range, while larger games generally require smaller step sizes. A practical heuristic is therefore to tune the step size on a smaller game and reduce it according to the increase in game size, although this offers no theoretical guarantee. For guaranteed convergence without knowing the threshold in advance, one can instead use our adaptive variant.


On Extensions beyond Two-Player Zero-Sum Perfect-Recall Games

Our analysis relies heavily on the bilinear structure of the sequence-form representation under perfect recall. In imperfect-recall games, this structure is generally lost, making an extension of our convergence guarantee challenging.

However, extending beyond two-player zero-sum games appears more promising for structured classes, such as the multiplayer monotone games studied by Perolat et al. (2021) or the network zero-sum extensive-form games studied by Piliouras et al. (2022). We believe that similar arguments may be developed for these settings, although extending our control of the behavioral correction terms would require further analysis.


References

  • Lee et al. Last-iterate convergence in extensive-form games. In NeurIPS, 2021.
  • Perolat et al. From Poincaré recurrence to convergence in imperfect information games: Finding equilibrium via regularization. In ICML, 2021.
  • Piliouras et al. Fast convergence of optimistic gradient ascent in network zero-sum extensive form games. In SAGT, 2022.

I thank the authors for their responses. Most of my concerns have been addressed, although some remain open for future work. I agree with the authors' point about the advantages of behavioral updates: "This representation naturally accommodates function approximation, making it suitable for learning in large games where maintaining a tabular strategy is impractical." Given this motivation, I would expect to see how the method performs on larger-scale games, which the paper does not demonstrate. Nevertheless, I think the paper makes solid and nontrivial theoretical contributions, so I would like to raise my rating from 2 to 3 (weak acceptance).

Thank you for your constructive feedback and positive reassessment of our work. We appreciate your thoughtful engagement.

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

This paper studies optimistic gradient descent-ascent (OGDA) applied independently to behavioral strategies at each information set in finite, two-player zero-sum extensive-form games with perfect recall. The authors establish last-iterate convergence for sufficiently small fixed step sizes without game regularization or a lower bound on reach probabilities. They further propose an adaptive variant that repeatedly halves the step size and eventually obtains the same asymptotic convergence guarantee from any initial step size.

The main technical contribution is an analysis that goes beyond existing sequence-form OGDA arguments. In particular, the authors use a strictly complementary equilibrium and its dual slacks to control the additional error terms induced by independent behavioral updates, including updates at information sets with zero equilibrium reach probability.

Critical strengths
  1. The paper addresses an important gap between sequence-form and behavioral-form equilibrium computation. Establishing last-iterate convergence for independent projected OGDA updates, without regularization or explicit exploration constraints, is a substantive result.
  2. The authors carefully identify why the standard sequence-form potential argument does not transfer directly. The use of reach-weighted energy, strict complementarity, and dual slacks to control otherwise unaccounted-for local movements is a promising and technically interesting approach.
Critical weaknesses

Although this paper points out that the guarantee with time as the upper bound is not specified, future research can continue. Another aspect is the experiment. Although the performance is similar to the baseline algorithm, the main contribution of this paper lies in theory. It would be better to verify computational efficiency on a larger scale of games.

Questions for authors

My question is the weakness mentioned above. If the author could further elaborate, it would make me more convinced of this paper.

1 comment

Thank you for your positive assessment and helpful suggestions.

Regarding convergence rates, even for the closest sequence-form baseline, dilated OGDA with the dilated Euclidean regularizer, the last-iterate guarantee of Lee et al. (2021) is asymptotic. Our analysis must additionally control the behavioral correction term induced by independent local updates. Establishing a finite-time last-iterate convergence rate remains an important direction for future work.

To assess computational efficiency, we have added a runtime comparison in Appendix D.1 (Figure 3). When measured against runtime, Behavioral OGDA shows faster empirical convergence than dilated OGDA in four of the five tested games. Although evaluation on larger games remains future work, we expect the simpler local updates of Behavioral OGDA to offer greater computational benefits as game size increases.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.