PaperlayerView exact revision on arXiv

Source-linked AI summary

Meta-Learning in Games

Keegan Harris, Ioannis Anagnostides, Gabriele Farina, Mikhail Khodak, Zhiwei Steven Wu, Tuomas Sandholm

arXiv:2209.14110v2cs.GT

TL;DR

Equilibrium computation has largely focused on isolated games, despite practical settings involving sequences of related games. This paper introduces meta-learning for equilibrium finding and learning to play across several game classes, with guarantees tied to game similarity. Its poker-endgame experiments report faster solving than treating games separately, often by an order of magnitude.

  • Problem

    Equilibrium computation has mainly studied single games in isolation, although practical strategic settings can involve many related games that change over time.

    Source: §1 · p. 3

  • Method

    The paper develops meta-learning for equilibrium finding and learning to play, with guarantees for several game classes parameterized by natural measures of similarity across games.

    Source: §1 · p. 3, §1.1 · p. 3

  • Results

    Poker endgames were solved significantly faster than by solving each game separately, often by an order of magnitude.

    Source: §1.1 · p. 4

  • Takeaways & Limitations

    The guarantees cover several central game classes and recover near-optimal static-game guarantees when the sequence of games is arbitrary.

    Source: §1.1 · p. 3

    For zero-sum games with multiple equilibria, the worst-case Nash-equilibrium similarity measure can be loose; a refinement requires players to know each game after it ends.

    Source: §3.1 · p. 7

Abstract

from arXiv · show

In the literature on game-theoretic equilibrium finding, focus has mainly been on solving a single game in isolation. In practice, however, strategic interactions -- ranging from routing problems to online advertising auctions -- evolve dynamically, thereby leading to many similar games to be solved. To address this gap, we introduce meta-learning for equilibrium finding and learning to play games. We establish the first meta-learning guarantees for a variety of fundamental and well-studied classes of games, including two-player zero-sum games, general-sum games, and Stackelberg games. In particular, we obtain rates of convergence to different game-theoretic equilibria that depend on natural notions of similarity between the sequence of games encountered, while at the same time recovering the known single-game guarantees when the sequence of games is arbitrary. Along the way, we prove a number of new results in the single-game regime through a simple and unified framework, which may be of independent interest. Finally, we evaluate our meta-learning algorithms on endgames faced by the poker agent Libratus against top human professionals. The experiments show that games with varying stack sizes can be solved significantly faster using our meta-learning techniques than by solving them separately, often by an order of magnitude.

1 Introduction

The paper addresses the gap between solving isolated games and learning across sequences of related games. It develops meta-learning guarantees for several game classes, relates convergence to game similarity, and evaluates the approach on poker endgames.

1 Introduction

  • Prior equilibrium-computation work focused on isolated games, while practical settings can require solving many related games as strategic interactions change.Examples include poker games with varying chip stacks, online advertising auctions, routing, and resource allocation.Source: §1 · p. 3

1.1 Overview of Our Results

  • The paper develops a framework for meta-learning guarantees across zero-sum, potential, general-sum, and Stackelberg games, with bounds parameterized by natural game-similarity measures.Examples include Nash-equilibrium variance, potential-function deviation, and similarity of the leader’s optimal commitment in hindsight.Source: §1.1 · p. 3, §1 · p. 3
  • The framework recovers near-optimal static-game guarantees for arbitrary game sequences while allowing stronger convergence guarantees as similarity measures improve.The algorithms are described as agnostic to how similar games are while adapting to their similarity.Source: §1.1 · p. 3
  • The analysis also yields new single-game results and a simpler framework that unifies several prior results.The paper cites convergence rates for optimistic mirror descent and extra-gradient methods in Hölder continuous variational inequalities, as well as results for certain nonconvex-nonconcave problems and stochastic games.Source: §1.1 · pp. 3–4
  • The poker experiments report significant gains over solving each game separately, often by an order of magnitude.The evaluation uses endgames faced by Libratus against top human professionals.Source: §1.1 · p. 4

1.2 Related Work

  • The paper positions its work at the intersection of meta-learning and decentralized online learning, and distinguishes it from warm-started abstraction methods that target performance on the ultimate game.It also frames the methods as learning to predict equilibria across games, with task similarity measuring prediction quality.Source: §1.2 · p. 4

2 Our Setup: Meta-Learning in Games

The setup treats meta-learning as learning across a sequence of repeated multiplayer games, each with its own within-game iterations. Players choose strategies from convex compact sets, receive feedback online, and performance is typically assessed by convergence to game-theoretic equilibria across tasks.

Notation

  • The notation uses boldface for vectors and matrices, reserves subscripts typically for players and superscripts usually for iterations or task indices, and defines [[T]] as the integers from 1 through T.It also defines the ℓ2-diameter of a nonempty convex compact set and uses O(·) to suppress polynomial factors in natural problem parameters.Source: §2 · p. 5

The general setup

  • The setup comprises T repeated games, each with m iterations, with a fixed player set and each player’s strategies drawn from a convex compact set.The exposition assumes the number of players remains fixed across games, while noting that some results apply more broadly.Source: §2 · p. 5
  • Each player’s utility is multilinear in the joint strategy profile, and the analysis uses a Lipschitz parameter for each game.The setup also defines social welfare and notes that it encompasses extensive-form games and broader games with concave utilities.Source: §2 · p. 5

Online learning in games

  • Players select strategies online and, in the full-information setting, observe feedback about the other players’ strategies; external regret compares play with the best fixed strategy in hindsight.The meta-learning objective is average performance across the game sequence, typically measured by convergence to game-theoretic equilibria.Source: §2 · p. 5

Optimistic mirror descent

  • The setup introduces optimistic mirror descent using a strongly convex regularizer, with initialization and learning rate as parameters.The supplied description identifies the learning rate as positive and the initialization as a vector.Source: §2 · pp. 5–6

3 Meta-Learning How to Play Games

This section develops online and decentralized meta-learning guarantees across zero-sum, general-sum, and Stackelberg games. Its bounds adapt to similarities between games while targeting different equilibrium and welfare objectives.

3.1 Zero-Sum Games

  • FTL over past optima-in-hindsight initializes OGD, giving game-average duality-gap bounds that approach single-task guarantees for arbitrary sequences and improve when task similarity is small.The initialization can be viewed as a learned prediction: smaller Euclidean error can reduce iterations to an approximate Nash equilibrium.Source: §3.1 · pp. 6–7
  • With OGD initialized by FTL over previous Nash equilibria, average iterations to an approximate Nash equilibrium improve when equilibria are close, while arbitrary sequences retain optimal m^-1/2 rates.When equilibria lie within a ball of ℓ2-diameter δ, the rate improves over OGD by at least a factor of 1/δ as T grows; worst-case similarity can be loose when equilibria are multiple.Source: §3.1 · p. 7
  • The framework extends to Lipschitz and weak-MVI games, stochastic games, Hölder operators, and extra-gradient; a sequence-distribution lower bound shows Theorem 3.1 is essentially sharp.For α-Hölder operators, OGD has rate m^-α/2; the lower bound refines the single-game lower bound by constructing a distribution over game sequences.Source: §3.1 · pp. 7–8

3.2 General-Sum Games

  • For potential games, initializing at the previous last iterate adapts to potential-function similarity; if consecutive potentials differ by at most α, O(α/ϵ²) iterations reach an ϵ-approximate Nash equilibrium on average as T grows.The initialization applies even with vanilla projected gradient descent.Source: §3.2 · p. 8
  • For general games, meta-learning optimistic-hedge initialization and learning rate yields CCE guarantees, while no-swap regret with a logarithmic barrier yields CE guarantees.Uncoupled product-distribution initializations may fail to exploit task similarity for correlated equilibria, which generally cannot be decomposed by player.Source: §3.2 · pp. 8–9

3.2.1 Social Welfare Guarantees

  • For sequences of smooth games, OGD reaches approximately optimal equilibria faster when task similarity is small; the guarantee uses average robust price of anarchy and extends to suitable linear combinations of utilities.The comparison without meta-learning is the m^-1 rate known from Syrgkanis et al. [2015].Source: §3.2.1 · p. 9

3.3 Stackelberg (Security) Games

  • For repeated Stackelberg games with adversarially chosen attacker types, MWU over extreme points meta-learns initialization and learning rates, with regret depending on the entropy of average hindsight-optimal strategies.In the worst case, the guarantee asymptotically matches O(m log |E|); entropy is small when a small set of mixed strategies is optimal across tasks.Source: Stackelberg security games · p. 10

Stackelberg security games

  • Across task-sequencing setups, meta-learning initialization yields up to an order-of-magnitude improvement over vanilla OGD, with the best initialization varying by stack ordering.The comparison averages the Nash-equilibrium gap across 200 tasks, two endgames, and three stack orderings.Source: Figure 1 · p. 11

4 Experiments

The experiments use two River endgames and vary player stack sizes across task sequences. They compare meta-learned initialization with warm-start and separate-game baselines.

4 Experiments

  • Two River endgames from Brains vs AI were each expanded into 200 tasks by varying both players’ stack sizes.The endgames are zero-sum extensive-form games.Source: §4 · p. 11
  • Tasks use random, sorted, or alternating stack sequences to test performance across different orderings of stack sizes.The random setup samples multiples of 100 from 1,000 to 20,000; the sorted setup increases both players’ stacks by 100 per task.Source: §4 · pp. 11–12
  • The comparison includes meta-learned OGD initialization, initialization from the previous task’s last iterate, and vanilla OGD solved separately.Each game uses 1,000 iterations; Figure 1 reports learning rate 0.01, and training uses Kronecker sparsification to accelerate computation.Source: §4 · p. 12

5 Conclusions and Future Research

The paper concludes that meta-learning yields similarity-dependent guarantees across several game classes and faster poker-endgame solving. It also contrasts its game-boundary-aware approach with related dynamic-regret work and outlines proof extensions.

5 Conclusions and Future Research

  • Meta-learning guarantees cover zero-sum, potential, general-sum multiplayer, and Stackelberg security games, with poker-endgame experiments showing gains often by an order of magnitude.Future directions include nonconvex-nonconcave min-max problems, nonparametric and partial-feedback settings, and strategy sets that vary across tasks.Source: §5 · p. 12

A Additional Related Work

  • For two-player zero-sum games, Zhang et al.’s dynamic-regret guarantees can grow with task count when game variation measures are Ω(T), whereas this paper’s game-boundary-aware bounds can decrease with task count.The comparison is limited to two-player zero-sum games; the cited variation measures are path-length, equilibrium-strategy, and payoff-matrix variation.Source: A Additional Related Work · p. 21

B Proofs from Section 3.2.1: Meta-Learning Approximately Optimal Equilibria

B.1 Bounding the Social Regret

The section derives a refined social-regret guarantee using initialization-dependent regret bounds. Its meta-OGD initialization follows the leader over earlier optima-in-hindsight, making the guarantee sensitive to similarity across tasks.

B.1 Bounding the Social Regret

  • The proof builds on initialization-parameterized regret bounded by variation in utilities, available for optimistic algorithms including OMD and OFTRL.For OGD, the stated learning rate is η = 1/(4L√n).Source: §B.1 · pp. 22, 24
  • OFTRL has a similar regret bound, but its unrefined initialization term impedes provable meta-learning guarantees under this approach.Under certain assumptions, mirror descent and follow-the-regularized-leader are equivalent.Source: §B.1 · p. 22
  • The analysis assumes players know the player count and each game's Lipschitz parameter, or suitable upper bounds, to tune the learning rate.A doubling-trick alternative requires additional communication to notify players when to halve the rate.Source: §B.1 · p. 23
  • Theorem B.3 gives a refined bound on total player regret parameterized by the similarity of each player's optimal-in-hindsight strategies across tasks.The analysis uses OGD with a specified learning rate; the theorem's bound is not fully reproduced in the supplied passages.Source: §B.1 · pp. 24, 26
  • Meta-OGD initializes each task using the previous tasks' optima-in-hindsight, an update equivalent to follow the leader over regret upper bounds.For the Euclidean regularizer, the resulting FTL regret contribution is bounded using a harmonic term no larger than 1 + log T.Source: §B.1 · pp. 24, 26
  • The guarantee can be improved by using different learning rates when Corollary B.2 applies; the exposition assumes a common rate for simplicity.If games have known sequential structure, initializing from a previous game's optimum or last iterate may be preferable to the theorem's initialization.Source: §B.1 · p. 26

B.2 Implications for the Social Welfare

For smooth games, the section relates players' regret to social-welfare guarantees and extends the analysis to weighted welfare. It then turns to meta-learning in two-player zero-sum games and broader settings.

B.2 Implications for the Social Welfare

  • The section extends the welfare analysis to positive player weights α, with standard utilitarian social welfare recovered when all weights equal 1.It states a corresponding result for sequences of smooth games.Source: §B.2 · pp. 27–28
  • In smooth games, the welfare guarantee is expressed using λ/(1 + µ), the robust price of anarchy, alongside players' regret.The robust price of anarchy is a welfare guarantee for coarse correlated equilibria as well as Nash equilibria.Source: §B.2 · pp. 27–28
  • When one weight is 1 and the others approach zero, the weighted-regret guarantee becomes vacuous because the required learning rate approaches zero.The passage identifies this as why near-optimal bounds on maximum individual regret require more refined techniques.Source: §B.2 · p. 29

C Proofs from Section 3.1: Meta-Learning in Zero-Sum Games

C.1 Bilinear Saddle-Point Problems

For bilinear saddle-point problems, the section applies OGD with previous optima-in-hindsight as initializations. It derives task-similarity-dependent guarantees for regret and average duality gap, with analogous extensions beyond two-player zero-sum games.

C.1 Bilinear Saddle-Point Problems

  • The average sum of players' regrets under OGD is bounded using the similarity of task optima-in-hindsight.The learning rate is set using the maximum spectral norm of the games' payoff matrices.Source: §C.1 · p. 30
  • The game-average duality gap of the players' average strategies is bounded in terms of task similarity, with an additional term that becomes negligible as T grows.The guarantee can significantly improve on the standard m^-1 rate when each game is treated separately.Source: §C.1 · p. 30
  • The section also derives refined guarantees for each player's individual regret using a bounded second-order path-length result.Source: §C.1 · pp. 30–31
  • Analogous guarantees apply to strategically zero-sum and zero-sum polymatrix games using the same technique.Source: §C.1 · p. 31

C.1.1 Last-Iterate Bounds

The section derives iteration-complexity guarantees for OGD last iterates to reach approximate Nash equilibria. The bounds depend on similarity between equilibria across games, and the initialization described assumes access to exact equilibria after completed games.

C.1.1 Last-Iterate Bounds

  • Theorem C.8 bounds the iterations needed for an iterate to be an approximate Nash equilibrium using a worst-case similarity measure over games' Nash equilibria.The initialization uses equilibria from preceding games.Source: §C.1.1 · p. 32
  • The worst-case Nash-equilibrium similarity measure can be loose when equilibria are non-unique; the section also considers the most favorable sequence of equilibria.For generic zero-sum games with a unique equilibrium, there is no equilibrium-selection issue.Source: §C.1.1 · p. 32
  • Implementing the stated initialization assumes players obtain an exact Nash equilibrium after each game.If they instead learn an O(1/m)-approximate equilibrium after m iterations, the theorem can use that approximate-equilibrium similarity measure.Source: §C.1.1 · p. 33

C.1.2 Improving the Task Similarity

This section refines task similarity for equilibrium learning and extends OMD and OGD analyses across broader update, weighting, regularization, and game settings. It establishes guarantees under stronger structural assumptions, including Hölder-continuous variational inequalities, and discusses a meta-learning extension and open lower-bound questions.

C.1.2 Improving the Task Similarity

  • When players observe game G(t) at each task’s end, they can use a loss based on its Nash-equilibrium set; an example has task similarity (24) 0 and improved similarity (21) Ω(1).Source: §C.1.2 · p. 33

C.1.3 Further Refinements

  • Under strong convexity-concavity, OMD converges linearly to the projection onto the Nash-equilibrium set; alternating updates also retain the stated guarantees.The linear rate is 1/(1 + µ/2), with step size constrained by the curvature and smoothness parameters; the alternating-update result follows by giving the second player a perfect prediction.Source: §C.1.3 · pp. 34–35

C.2 Beyond Bilinear Saddle-Point Problems: A VI Perspective

  • For L-Lipschitz operators satisfying the MVI property, OGD extends the meta-learning guarantees beyond bilinear saddle-point problems to a broader variational-inequality setting.The framework also includes smooth differentiable min-max objectives through their gradient operators.Source: §C.2 · pp. 35–37
  • For monotone, Lipschitz operators on a bounded set, the OGD average is an O(1/m)-approximate weak solution to the variational inequality.The result follows from an O(1/m) decay in average regret.Source: §C.2 · p. 37

C.2.1 Weak MVI Property

  • With the weak MVI property, OGD provides an iteration bound for reducing the operator norm to ε when 0 < ρ < 1/(8L) and 2ρ < η < 1/(4L).The corresponding meta-learning version is analogous to the MVI result; extending the analysis to constrained settings is left open.Source: §C.2.1 · pp. 38–39

C.3 Weighting the Strategies

  • OMD’s regret analysis extends to positive, nondecreasing weighting sequences, supporting weighted strategy averages such as linear and quadratic averaging.The subsection formulates a weighted alpha-regret guarantee using a 1-strongly convex regularizer.Source: §C.3 · p. 39
  • The analysis lifts many results of Syrgkanis et al. [2015] from their original setting to any class of monotone weighting schemes while retaining OMD.Source: §C.3 · p. 40

C.4 Adaptive Regularization

  • OptAdaGrad’s regret guarantee incorporates optimism and time-varying regularization, recovers OGD when σ(m) = 0, and makes its misprediction term depend on the preconditioner sequence.The preconditioners must satisfy Condition C.23.Source: §C.4 · pp. 41, 43

C.5 Stochastic Games

  • A generalized MVI condition captures distribution shift through weighted coefficients, and the ratio game satisfies it with coefficients determined by ζ and Smax.The property and proposition also extend directly to multi-state stochastic games.Source: §C.5 · p. 44
  • OGD with a suitable learning-rate schedule reaches an approximate minimax equilibrium of the ratio game in O(1/ϵ^2) iterations.The schedule is time-varying but non-vanishing; the authors note that they have not identified it in an algorithmically useful way.Source: §C.5 · pp. 43, 45, 46
  • The stochastic-game result has a meta-learning version parameterized by the similarity of the games’ minimax equilibria.Source: §C.5 · p. 46

C.6 Hölder Smooth Games

  • For an α-Hölder-continuous operator satisfying MVI, OGD yields an m^−α/2-approximate strong VI solution after O(m) iterations.The learning rate decays with the horizon, worsening the iteration bound relative to Lipschitz-continuous settings.Source: §C.6 · pp. 47–48
  • For α = 1, the guarantee recovers the tight m^-1/2 OGD rate under Lipschitz continuity [Golowich et al., 2020a,b].Source: §C.6 · p. 48
  • Lower bounds for the weaker Hölder continuity assumption studied here remain an open question.Source: §C.6 · p. 48
  • A meta-learning version of Theorem C.34 follows immediately from prior techniques, but the learning rate must also be meta-learned because Proposition C.33 assumes knowledge of z⋆ ∈ Z.This is analogous to the approach in Theorem D.7 in Appendix D.2.Source: §C.6 · p. 48

C.7 The Extra-Gradient Method

The section extends the regret framework to extra-gradient by analyzing its secondary sequence, yielding RVU-type bounds and variational-inequality guarantees under stated operator assumptions.

C.7 The Extra-Gradient Method

  • Extra-gradient updates use auxiliary feedback and are more general than the standard method with Euclidean regularization, but require two gradient-oracle calls per iteration.Source: §C.7 · p. 49
  • Although extra-gradient is outside the traditional no-regret framework, the analysis gives it an RVU-type bound using regret of its secondary sequence against auxiliary utilities.This provides a unified analysis with OGD and recovers prior results more simply.Source: §C.7 · p. 49
  • With Lipschitz continuity of F, secondary-sequence regrets sum to O(1), and monotonicity yields an O(1/m)-approximate weak solution to the VI problem.The average secondary sequences provide the stated solution guarantee.Source: §C.7 · p. 50
  • Under the MVI property, nonnegative summed secondary-sequence regret implies bounded second-order path lengths and O(1/ϵ^2) iterations for an ϵ-approximate strong VI solution.Source: §C.7 · p. 50

C.8 Lower Bounds

The section develops lower bounds for regret in meta-learning, extending a single-game zero-sum construction to sequences sampled from a known prior over games.

C.8 Lower Bounds

  • The construction uses zero-sum games whose payoff matrices have nonzero entries in one row; the row player searches for that row, while the column player cannot affect payoffs.Source: §C.8 · pp. 50–51
  • A single zero-sum game class has expected regret Ω(1), with expectation over the agents’ randomization.Source: §C.8 · p. 51
  • For meta-learning, the construction samples games independently from a known prior p over the family, allowing a refined lower-bound analysis; uniform sampling offers no exploitable additional structure.Source: §C.8 · p. 51

D Proofs from Section 3.2: Meta-Learning in General-Sum Games

This section distinguishes what meta-learning can transfer across general-sum games from zero-sum games, then develops guarantees for potential games and convergence to coarse correlated and correlated equilibria.

D Proofs from Section 3.2: Meta-Learning in General-Sum Games

  • Uncoupled initialization cannot encode a previous coarse correlated equilibrium; transferring regret across nearby games is O(ϵ) for zero-sum games but PPAD-hard in general-sum games.The separation holds even when the players have zero regret in the first general-sum game and the games are known.Source: D Proofs from Section 3.2:… · p. 52

D.1 Potential Games

  • For potential games, gradient descent with task-to-task initialization yields refined meta-learning guarantees based on potential-function similarity, without requiring concavity.The section derives refined second-order path-length bounds for gradient descent and uses them to obtain a meta-learning guarantee.Source: §D.1 · pp. 53–54

D.1.1 Refinements under Concave Potentials

  • With concave potentials available after each task, the meta-learner has o(T) regret and efficient implementation, while gradient updates can remain decentralized.The passage describes this as a refinement under the additional concavity and post-task-availability conditions.Source: §D.1.1 · pp. 54–55

D.2 Coarse Correlated Equilibria

  • For coarse correlated equilibria, OptHedge with EWOO-meta-learned learning rates gives a refined task-similarity-dependent convergence guarantee.The section identifies a main result for CCE convergence and describes EWOO as the mechanism for meta-learning the learning rate.Source: §D.2 · p. 55

D.3 Correlated Equilibria

  • For correlated equilibria, the refinement uses swap regret and Blum–Mansour no-swap-regret OMD with a logarithmic regularizer, avoiding learning-rate meta-learning.The cited approach expresses the swap-regret bound in terms of initialization.Source: §D.3 · p. 58

E Proofs from Section 3.3: Meta-Learning in Stackelberg Games

The Stackelberg-games proof uses multiplicative weights over extreme points and a meta-learned learning rate to bound task-averaged regret across repeated security games.

E Proofs from Section 3.3: Meta-Learning in Stackelberg Games

  • The theorem uses MWU over extreme points and a β-EWOO learning rate to bound expected task-averaged Stackelberg regret.The guarantee is stated for repeated Stackelberg security games with d targets, k attacker types, and within-game horizon m.Source: E Proofs from Section 3.3:… · p. 59
  • The attacker sequence may be adversarially chosen under the stated regret guarantee.This condition is stated explicitly for the sequence of attackers in each task.Source: E Proofs from Section 3.3:… · p. 59
  • The analysis uses an α boundary offset; the authors note that meta-learning this offset over a discretized grid may yield better rates.The passage presents this as a possibility, not as a result established by the theorem.Source: E Proofs from Section 3.3:… · p. 59

F Further Experimental Results

The additional experiments visualize task-averaged Nash equilibrium gaps for OGD variants across learning rates in two poker endgames.

F Further Experimental Results

  • Figure 2 compares vanilla OGD with meta-learning OGD variants across learning rates in Endgame A.The accompanying prose identifies the plotted quantity as task-averaged Nash equilibrium gap.Source: F Further Experimental Results · p. 61, Figure 2 · p. 62
  • In Endgame A, η = 0.1 is omitted because it was too large for any method to converge.This exclusion applies to Figure 2’s learning-rate comparison.Source: Figure 2 · p. 62
  • Figure 3 compares vanilla OGD with meta-learning OGD variants across learning rates in Endgame B.The accompanying prose identifies the plotted quantity as task-averaged Nash equilibrium gap.Source: F Further Experimental Results · p. 61, Figure 3 · p. 63

Related papers

Loading 2209.14110v2…