PaperlayerView exact revision on arXiv

Source-linked AI summary

IR-PRM+ with Previous-Utility Prediction: Constant Regret and Best-Iterate Convergence

Michael Sullins, Ian A. Kash

arXiv:2610.19016v1cs.LGcs.GT

TL;DR

Regret-matching variants have lacked the stronger convergence guarantees available for optimistic and extra-gradient methods, and prior IR-PRM+ analysis did not cover previous-utility prediction or alternating updates. This paper controls the missing strategy displacement through regret-vector growth and establishes guarantees for both update schedules, extending them to CFR under full reach.

  • Problem

    Existing IR-PRM+ guarantees do not cover previous-utility prediction or alternating updates, despite the practical relevance of these settings.

    Source: §1 · p. 1

  • Method

    The analysis bounds missing post-update strategy displacement using relative regret-vector norm growth and couples the resulting bounds across players.

    Source: §1 · p. 2

  • Results

    Previous-utility prediction recovers constant regret and convergence guarantees for simultaneous and alternating IR-PRM+ and analogous guarantees for IR-PCFR+ under the stated full-reach setting.

    Source: §1 · p. 2, §7.1 · p. 6

  • Takeaways & Limitations

    The guarantees extend from finite two-player zero-sum matrix games to perfect-recall extensive-form games through a CFR variant under the weighted Minty condition and full-reach assumption.

    Source: §1 · p. 2, §7.1 · p. 6, §7.2 · p. 6

    The CFR result uses the full-reach condition, which ensures strictly positive weights for the weighted Minty condition.

    Source: §7.1 · p. 6, §7.2 · p. 6

Abstract

from arXiv · show

Regret matching (and its variants) and counterfactual regret minimization are central algorithms in practice for normal-form and extensive-form game solving. Yet these have historically lacked the stronger theoretical convergence guarantees available to optimistic and extra-gradient methods. Recent work introduced IREG-PRM+, a regret matching variant which does have strong theoretical convergence guarantees. However, it relies on a simultaneous, extra-gradient update. IREG-PRM+ is an instance of the more general IR-PRM framework, where empirically optimistic and alternating updates often have better performance. However, the prior extra-gradient analysis does not extend to these cases. We introduce a new approach that covers both settings. For simultaneous and alternating IR-PRM+ in finite two-player zero-sum matrix games, previous-utility prediction recovers the constant-regret and convergence-rate guarantees previously obtained with extra-gradient prediction: external regret bounded independently of T, an O(T^{-1}) average duality gap, and an O(T^{-1/2}) best-current-iterate gap. Moreover, the current duality gap vanishes and the current profile converges to the Nash equilibrium set. The key step bounds the component of consecutive strategy movement not controlled by the existing IR-PRM+ regret inequality using the relative growth of the nondecreasing regret-vector norm rho_t. Coupling this bound across the two players yields recurrences whose effective coefficient scales as 1/(rho_t^X rho_t^Y), preventing unbounded norm growth. We extend the analysis to finitely many simplex learners under a weighted Minty condition and, through the corresponding CFR variant IR-PCFR+, recover analogous guarantees for finite two-player zero-sum perfect-recall extensive-form games under the same full-reach condition as prior work.

1 Introduction

Regret-matching methods are practically successful, but existing IR-PRM+ guarantees leave previous-utility prediction and alternating updates uncovered. The paper controls previously unbounded strategy movement through regret-vector growth, recovering guarantees for both update settings and extending them to CFR.

1 Introduction

  • Previous IR-PRM+ guarantees rely on extra-gradient prediction and do not cover previous-utility prediction or alternating updates.Extra-gradient uses two game evaluations per update, whereas previous-utility prediction reuses prior feedback; empirical results favor alternating or simultaneous updates over extra-gradient on all six reported benchmarks when measured by gradient evaluations.Source: §1 · p. 1
  • Previous-utility prediction leaves part of consecutive strategy movement uncontrolled by the existing RVU bound, while alternating updates evaluate the players at different profiles.The second player responds to the first player's newly updated strategy, creating a separate timing difficulty.Source: §1 · pp. 1–2
  • Regret-vector norm growth controls the missing post-update displacement because larger norms make fixed regret-vector changes have less effect on normalized strategies.In self-play, each player's norm limits the effect of its prediction error, while the opponent's norm limits post-update movement and thereby reduces that error.Source: §1 · p. 2
  • The coupled norm-growth bounds keep both players' regret-vector norms bounded by making the effective coefficient shrink as either norm grows.Once the product of the norms is sufficiently large, the positive prediction-error contribution is dominated by the negative prediction-displacement term.Source: §1 · p. 2
  • In finite two-player zero-sum matrix games, simultaneous IR-PRM+ with previous-utility prediction achieves external regret bounded by constants independent of T and recovers IREG-PRM+ constant-regret and convergence-rate guarantees without extra-gradient evaluation.It has an O(T^-1) average duality gap, current duality gap tending to zero, current profiles converging to the Nash equilibrium set, and an O(T^-1/2) best-current-iterate guarantee.Source: §1 · p. 2
  • The analysis also recovers a two-displacement RVU bound and extends to simultaneous and alternating IR-PCFR+ under the weighted Minty condition and full-reach assumption.For finite two-player zero-sum perfect-recall extensive-form games, the resulting guarantees include bounded sequence-form external regret, an O(T^-1) average gap, current-profile convergence, and an O(T^-1/2) best-current-iterate guarantee.Source: §1 · p. 2

2 Related Work

Prior work developed regret-matching and predictive variants for practical game solving, while stronger convergence guarantees came from stabilized or modified dynamics. This paper establishes such guarantees within IR-PRM+ for previous-utility prediction and alternating updates.

2 Related Work

  • CFR decomposes global external regret into local counterfactual regrets, while CFR+ combines RM+ with alternating updates and weighted averaging.Predictive RM+ was shown to accelerate CFR in practice [7].Source: §2 · p. 2
  • RVU bounds combine utility variation with a negative own-movement penalty, and interacting learners can use these terms for faster-than-worst-case convergence [16].Other approaches include stabilized RM+ variants, extra-gradient and smooth predictive methods, weak-Minty guarantees, and average-to-last-iterate reductions.Source: §2 · p. 2
  • Within IR-PRM+, previous-utility prediction and alternating updates retain constant regret, O(T^-1) average-gap and O(T^-1/2) best-current-iterate rates, and current-profile convergence.These guarantees do not require extra-gradient prediction.Source: §2 · p. 3

3 Preliminaries and IR-PRM+

The paper formulates two-player zero-sum matrix games and a generic simplex learner, then describes IR-PRM+ strategies through normalized regret vectors and utility predictions. It contrasts previous-utility prediction with the extra-gradient evaluation used in earlier analysis.

3 Preliminaries and IR-PRM+

  • In the matrix-game setup, players choose strategies from their action simplices and receive utilities from the payoff matrix.The paper distinguishes simultaneous updates, based on information available before joint play, from alternating sequential updates.Source: §3 · p. 3
  • A generic k-action learner chooses a simplex strategy, observes a utility vector, and incurs external regret; IR-PRM+ maintains a nonnegative cumulative regret vector with Euclidean norm ρ_t.The stated unit-norm initialization avoids division by zero; the method also permits nonnegative initial regret vectors, including zero initialization with separate treatment of initial rounds.Source: §3 · p. 3
  • Before playing, IR-PRM+ incorporates a predicted utility vector into the regret vector and normalizes its positive part to obtain the played strategy.The strategy before prediction differs from the strategy actually played after incorporating the prediction; the prediction error is defined after observing utility.Source: §3 · p. 3
  • Extra-gradient prediction evaluates the game at an intermediate strategy pair before the played pair, whereas previous-utility prediction reuses the preceding round's observed utility.Previous-utility prediction requires no preliminary game evaluation and evaluates only the played pair.Source: §3 · p. 3

4 Starting from the IR-PRM+ RVU Bound

The existing IR-PRM+ RVU inequality penalizes prediction displacement, but previous-utility prediction makes prediction error depend on full movement between consecutive played strategies. The missing post-update displacement is the remaining control problem.

4 Starting from the IR-PRM+ RVU Bound

  • The existing constant-regret analysis uses an RVU-type inequality for IR-PRM+ that keeps the terminal regret-vector norm explicit.The cited intermediate inequality is attributed to Zhang et al. [19].Source: §4 · pp. 3–4
  • Under previous-utility prediction, prediction error depends on full movement between consecutive played strategies, but the existing negative RVU term controls only prediction displacement.The uncontrolled component is the post-update displacement from the preceding played strategy to the intermediate strategy.Source: §4 · p. 4

5 Single-Learner Displacement and Movement Bounds

Previous-utility prediction depends on the full movement between consecutive played strategies, while the existing IR-PRM+ regret bound controls only prediction displacement. The analysis bounds the missing post-update displacement through regret-vector norm growth.

5 Single-Learner Displacement and Movement Bounds

  • The regret bound controls prediction displacement but not the post-update movement from x_t to x̃_{t+1} required by previous-utility prediction.The missing displacement is controlled by the increase in the regret-vector norm.Source: §5 · p. 4
  • A normalization inequality relates the post-update displacement to the increase in the nondecreasing regret-vector norm.The norm’s monotonicity is established for IR-PRM+ by Zhang et al. [19].Source: §5 · p. 4
  • Consecutive strategy movement can be bounded using prediction displacement and post-update displacement, yielding a two-displacement RVU bound.The strengthened RVU bound is not used in the main convergence analysis, which works directly with regret-vector norm growth.Source: §5 · p. 4

6 Two-Player Analysis

The two-player analysis couples regret-vector norm growth through bounds on consecutive strategy movement. This yields constant regret and controls both average and current-profile convergence in simultaneous IR-PRM+.

6 Two-Player Analysis

  • Previous-utility prediction makes each player’s prediction error depend on the opponent’s consecutive strategy movement, which the displacement bound relates to norm growth.The resulting coupled recurrences control growth of both regret-vector norms.Source: §6 · p. 4
  • External regrets for simultaneous IR-PRM+ with previous-utility prediction are bounded by finite game-dependent constants independent of T.The result holds for finite two-player zero-sum matrix games.Source: §6 · p. 5
  • The regret-vector norm is nondecreasing, and the proof uses this property to bound norm growth after a sufficient threshold is reached.The threshold makes the effective coefficient small enough to control the recurrences.Source: §6 · pp. 4–5
  • The analysis bounds accumulated weighted squared prediction displacements by the regret-vector norms, then uses that bound to control further norm growth.The bounds also yield the O(T^-1) average-gap rate and square-summable movement underlying current-profile convergence.Source: §6 · p. 5

7 Simultaneous IR-PCFR+ in Extensive-Form Games

The paper extends previous-utility prediction from two-player matrix games to local learners in CFR. Under a weighted Minty condition, it obtains bounded local regret-vector norms and transfers these guarantees to extensive-form games with a full-reach Nash equilibrium.

7.1 Extensive-form games and CFR

  • CFR assigns a local learner to each information set, with counterfactual utility as its feedback; the local problems are coupled through the behavioral profile.Behavioral strategies comprise a local action distribution at every information set.Source: §7.1 · p. 6
  • A full-reach Nash equilibrium supplies strictly positive weights for the weighted Minty condition on the counterfactual-utility operator.The standard CFR decomposition connects local counterfactual utilities to the sequence-form game.Source: §7 · p. 5, §7.1 · p. 6

7.2 Simultaneous IR-PRM+ on a product of simplices

  • Product-space coupling handles the fact that one learner’s feedback can depend on every component of the profile, rather than only another learner’s movement.Lipschitzness bounds prediction error by full-profile movement, which is decomposed across local learners.Source: §7.2 · p. 6
  • For bounded, Lipschitz operators satisfying the weighted Minty condition, simultaneous IR-PRM+ keeps every local regret-vector norm bounded and gives each learner constant external regret.The regret bound is a finite game-dependent constant independent of T.Source: §7.2 · p. 6

7.3 Simultaneous IR-PCFR+

  • The CFR reduction transfers local constant-regret guarantees to sequence-form external regret for simultaneous IR-PCFR+ in full-reach games.The guarantee applies to finite two-player zero-sum perfect-recall extensive-form games and is bounded independently of T.Source: §7 · p. 5, §7.3 · p. 7
  • Theorem 5 establishes current sequence-form convergence in the same setting.The product-space movement argument controls current local counterfactual residuals, which the pointwise CFR decomposition transfers to the sequence-form duality gap.Source: §7.3 · p. 7

8 Alternating Updates

Previous-utility prediction retains the simultaneous-update guarantees when IR-PRM+ uses alternating updates. The analysis addresses staggered updates and extends the approach to alternating IR-PCFR+ in extensive-form games.

8 Alternating Updates

  • Alternating IR-PRM+ reuses each player’s newly observed utility as the next prediction, with the column update preceding the row update.Each round passes through an intermediate profile before producing the full profile.Source: §8 · p. 7
  • Alternation staggers regret-vector growth bounds and evaluates the column player’s controlled regret on intermediate rather than full profiles.The analysis handles both differences while retaining the simultaneous-case guarantees.Source: §8 · pp. 7–8
  • Both players’ external regrets under alternating IR-PRM+ are bounded by game-dependent constants independent of T.The result applies to finite two-player zero-sum matrix games.Source: §8 · p. 8
  • Square-summable consecutive strategy movement yields convergence of the current profiles under alternating updates.Theorem 7 states current-profile convergence in the same setting.Source: §8 · p. 8

8.1 Alternating IR-PCFR+

  • Alternating IR-PCFR+ controls row-player local regret on full profiles and initially controls column-player regret on intermediate profiles.The remaining comparison transfers the column half-step bounds to sequence-form regret on full profiles.Source: §8.1 · p. 8
  • Alternating IR-PCFR+ has bounded sequence-form external regret in finite two-player zero-sum perfect-recall games admitting a full-reach Nash equilibrium.The bound is a finite game-dependent constant independent of T; the argument applies the staggered matrix-game analysis to local learners and uses the standard CFR decomposition.Source: §8.1 · p. 8
  • The same local bounds yield control of current full profiles, and Theorem 9 states current sequence-form convergence in the same setting.The result concerns alternating IR-PCFR+ under the theorem’s stated assumptions.Source: §8.1 · p. 8

9 Conclusion and Future Work

The paper supplies the missing theoretical guarantees for previous-utility prediction in simultaneous and alternating IR-PRM+, with corresponding guarantees for IR-PCFR+. Its key proof device is a post-update displacement bound tied to regret-vector growth; empirical evaluation and broader settings remain for future work.

9 Conclusion and Future Work

  • Previous-utility prediction recovers extra-gradient IREG-PRM+ guarantees for simultaneous and alternating IR-PRM+, with corresponding guarantees for IR-PCFR+.The contribution is theoretical; the paper does not repeat an empirical evaluation and identifies extensions beyond the considered zero-sum and weighted-Minty settings as future work.Source: §9 · p. 8
  • A post-update displacement bound links strategy movement to regret-vector growth and is the key step in the analysis.Source: §9 · p. 8

A Proofs for the Simultaneous Matrix-Game Analysis

These appendices develop the proof machinery for simultaneous matrix-game and CFR guarantees: they control regret, prediction residuals, strategy movement, and the transfer from local CFR quantities to global sequence-form quantities.

A.1 Proof of Fact 1

  • External regret is the largest coordinate of the cumulative regret vector, and the proof bounds it using the regret-vector norm.The coordinatewise inequality is converted using the infinity norm bound by the Euclidean norm, which equals the stated regret-vector norm.Source: §A.1 · pp. 8–9

A.2 Predicted-utility residual bound

  • The predicted-utility residual lemma turns small prediction displacement into approximate optimality for the predicted utility.The lemma is used for current-profile results, not for the constant-regret proof.Source: §A.2 · p. 9

A.3 Proof of Theorem 2

  • Square-summable strategy movement yields vanishing current duality gap and convergence of the current profile to the Nash equilibrium set.The proof obtains square summability through prediction and post-update displacements, then uses the residual bound; compactness and continuity establish the distance conclusion.Source: §A.3 · pp. 9–10

B.1 Proof of Lemma 3

  • The product-space argument expresses each learner’s norm growth through nonnegative quantities for other learners and controls movement componentwise.The one-step norm-growth inequality then relates this expression to the learner’s norm.Source: §B.1 · p. 10

B.2 Current residual under weighted Minty

  • Under weighted Minty, local current residuals are square summable, so their sum converges to zero.The corollary states the current-residual bound under Theorem 3’s assumptions.Source: §B.2 · pp. 10–11

C.1 Standard CFR decomposition

  • The pointwise CFR decomposition connects global sequence-form deviations to weighted local behavioral deviations; a full-reach equilibrium supplies positive weights for the weighted Minty condition.The same identities transfer local residual bounds to sequence-form residuals.Source: §C.1 · p. 11

C.2 Proof of Theorem 4

The proofs transfer bounded local CFR regret and residuals to sequence-form guarantees, then establish analogous alternating-update bounds through staggered norm-growth recurrences.

C.2 Proof of Theorem 4

  • Bounded local counterfactual regrets transfer to O_T(1) sequence-form external regret for both players and an O(T^-1) average sequence-form duality gap.The proof uses the pointwise CFR decomposition and the regret-to-gap identity.Source: §C.2 · pp. 11–12

C.3 Proof of Theorem 5

  • Square-summable local current residuals bound the sequence-form gap, which converges to zero and implies convergence to the sequence-form Nash equilibrium set.The proof bounds the sequence-form gap by the local residual sum and uses compactness and continuity for the distance conclusion.Source: §C.3 · p. 12

D Proofs for Alternating IR-PRM+

  • Alternating updates require separate staggered norm-growth recurrences because the column player is half a step ahead of the row player.Their denominators reflect which column norm is available at each point in the indexing; the proof states that no additional game parameter is required.Source: D Proofs for Alternating IR-PRM+ · p. 13

D.1 Proof of Theorem 6

The alternating matrix-game proof bounds regret-vector norms and relates half-step regret to full-profile regret. It then establishes square-summable movements and current residuals, yielding best-iterate and convergence guarantees.

D.1 Proof of Theorem 6

  • The alternating proof keeps both norm sequences bounded over time, and both full-profile external regrets are O_T(1); the usual zero-sum regret-to-gap identity gives Gap(¯x_T, ¯y_T)=O_T(T^-1).Source: §D.1 · p. 15

D.2 Proof of Theorem 7

  • Square-summable current residuals yield an O(T^-1/2) best-current-iterate gap, vanishing current gap, and convergence to the Nash equilibrium set.The argument uses bounded norms and square-summable prediction displacements and strategy movements.Source: §D.2 · p. 15

E.1 Proof of Theorem 8

This section develops proof ingredients for IR-PRM+ guarantees, using full-reach equilibrium weights and a strengthened two-displacement RVU bound to control prediction displacement and establish bounded external regret, then deriving current-gap decay and convergence to the Nash equilibrium set. It also notes that the ℓ1-normalization bound affects dimension-dependent constants but not qualitative conclusions or asymptotic rates, and verifies that the guarantees extend to zero initialization.

E.1 Proof of Theorem 8

  • Both players have O_T(1) full-profile sequence-form external regret under the full-reach condition.Thresholded local norm recurrences bound accumulated prediction displacement; the sequence-form regret-to-gap identity then yields the average-gap guarantee.Source: §E.1 · p. 17

E.2 Proof of Theorem 9

  • The current duality gap vanishes, the best-current-iterate gap is O_T(T^-1/2), and the profile converges in distance to the Nash equilibrium set.The proof uses square-summable prediction displacements and local residuals, then compactness and continuity to establish Nash-set convergence.Source: §E.2 · p. 18

F.1 Handling zero regret vectors

  • At zero norm, the default strategy stays fixed with zero best-response residual; the first transition to positive norm still satisfies the displacement bound.After the first positive norm, monotonicity gives a fixed positive lower bound for subsequent rounds.Source: §F.1 · p. 18

F.2 Simultaneous matrix games

  • With zero initialization, simultaneous matrix games retain O_T(1) regret, O_T(T^-1) average-gap, vanishing-current-gap, Nash-set convergence, and O_T(T^-1/2) best-current-iterate guarantees.If a player’s regret norm remains zero, its fixed strategy makes the other player’s previous-utility prediction exact after one observation.Source: §F.2 · pp. 18–19

F.3 Products of simplices and simultaneous IR-PCFR+

  • Under zero initialization, the product-space and simultaneous IR-PCFR+ guarantees of Theorem 3, Corollary 2, and Theorems 4 and 5 continue to hold.Learners that remain at zero contribute neither strategy movement nor regret; finitely many zero-norm rounds and transitions add only a finite constant.Source: §F.3 · p. 19

F.4 Alternating updates

  • For alternating updates, the guarantees of Theorems 6–9 and Corollary 3 also hold under zero initialization.The proof handles the first positive-norm transition separately; later recurrences use a fixed positive lower bound, while learners remaining at zero have fixed strategies.Source: §F.4 · p. 19

F Standard Zero Initialization

  • All regret, average-gap, current-gap, Nash-set convergence, and best-current-iterate guarantees remain valid with zero-initialized IR-PRM+ and IR-PCFR+.The zero-norm rule uses a fixed default strategy until the stored regret vector becomes positive.Source: F Standard Zero Initialization · p. 18, §F.4 · p. 19

G Normalization Under ℓ1 Scaling

  • The normalization argument compares nonnegative Euclidean-unit vectors after scaling by their respective ℓ1 norms.It begins by adding and subtracting v/∥u∥1; the passages also note that each vector’s ℓ1 norm is at least one.Source: G Normalization Under ℓ1 Scaling · p. 20
  • The elementary ℓ1-normalization bound is used throughout; a sharper constant would change only dimension-dependent constants, not qualitative conclusions or asymptotic rates.Combining the preceding displays proves (G.1).Source: G Normalization Under ℓ1 Scaling · p. 20

H A Two-Displacement RVU Bound for IR-PRM+

  • The two-displacement IR-PRM+ RVU bound makes prediction and post-update displacements explicit, with regret-vector norm growth controlling the post-update displacement.The authors note that this strengthened form is not needed for the main convergence analysis, which works directly with regret-vector norm growth.Source: H A Two-Displacement RVU Bound for… · p. 20

AI-Assisted Technology Disclosure

  • The authors report using ChatGPT for research brainstorming and editing, while independently selecting research directions, checking mathematical arguments, and taking responsibility for the paper’s claims and proofs.Because interactions spanned multiple sessions, not every prompt and model version was retained; the authors report the nature of the interactions instead.Source: AI-Assisted Technology Disclosure · pp. 20–21
Loading 2610.19016v1…