Meta-Learning in Games
Authors: Keegan Harris
Ioannis Anagnostides
Gabriele Farina
Mikhail Khodak
Steven Wu
Tuomas Sandholm
Venue: ICLR 2023 poster (2023)
Keywords: meta-learning
algorithmic game theory
online learning

Abstract: 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 games, including two-player zero-sum games, general-sum games, Stackelberg games, and multiple extensions thereof. 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.

Published as a conference paper at ICLR 2023
META-LEARNING IN GAMES
Keegan Harris
Ioannis Anagnostides" Camegie Mellon University ianagnosècs cmu. edu
Gabriele Farina FAIR, Meta Al gfarina@mes com
Carnegie Mellon University keeganhecs.. www.uuuhhcc.u........cmmmmm.uu edu
cmu
Mikhail Khodak
Zhiwei Steven Wu Carnegie Mellon University zhi Phiweiw@cs. cmu. edu
Tuomas Sandholm
Camegie Mellon University mkhodakécs. cmu. edu
Camegie Mellon University Strategy Robot, Inc. Optimized Markets, Inc. Strategic Machine, Inc. sandholm@ cs cmu, edu
ABSTRACT
In the literature game-theoretic equilibrium finding, focus has mainly been on solving single game in isolation. In practice. however, strategic interactions- ranging from routing problems to online advertising auctions-eve 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 theoretc equilibria that depend 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 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.
dynamically,
INTRODUCTION
Research on game-theoretic equilibrium computation has primarily focused on solving a single game in isolation. In practice, however, there are often many similar games which need to be solved. One use-case is the setting where one wants to find an equilibrium for each of multiple game variations for example poker games where the players have various sizes of chip stacks. Another use-case is strategic interactions that evolve dynamically: in online advertising auctions, the advertiser's value for different keywords adapts based on current marketing trends (Nekipelov al. 2015); routing games- be it Internet routing or physical transportation -eeiatttiinnrreapeeeeeeee depending on the topology and the cost functions of the underlying network (Hoefer et al.) 2011];; and resource allocation problems (Johari and Tsitsiklis 2004) vary based on the values of the goods/services. Successful agents in such complex decentralized environments must effectively learn how to incorporate past experience from previous strategic interactions in order to adapt their behavior to the current and future tasks.
Meta-learning, or learning-to-lees tollarm (Thrun and Pratt 1998), is a common formalization for machine learning in dynamic single-agent environments. In the meta-learning framework, a learning agent faces sequence of tasks, and the goal is to use knowledge gained from previous tasks in order to improve performance results have not been tailored to tackle multiagent settings. This begs the question: Can players obtain provable performance improvements when meta- leernin across sequence of games? We answer this Equull contribution.
the current task hand. Despite rapid progress in this line of work. prior

---

Published as a conference paper at ICLR 2023
question in the affirmative by introducing meta-learning for equilibrium finding and learning to play games, and providing the first performance guarantees in a number of fundamental multiagent settings.
1.1 OVERVIEW OF OUR RESULTS
Our main contribution is to develop a general framework for establishing the first provable guarantees for meta-learning in games, leading to comprehensive set of results in a variety of well-studied multiagent settings. In particular, our results encompass environments ranging from two-player zero-sum games with general constraint sets (and multiple extensions thereof), to general-sum games and Stackelberg games. See Table for a summary of our results. Our refined guarantees parameterized based on natural similarity metrics between the sequence of games. For example, in zero-sum games we obtain last-iterate rates that depend on the variance of the Nash equilibria (Theorem 3.2); in potential games based on the deviation of the potential functions (Theorem) (34); and in Stackelberg games our regret bounds depend on the similarity of the leader's optimal commitment in hindsight (Theorem 3.8 All of these measures are gggorthmm-indepedden and tie naturally to the underlying game- thenreth solution concepts.
Importantly, our algorithms are agnostic to how similar the games are, but are nonetheless specifically designed to adapt to the similarity. Our guarantees apply under a broad class of no-regret learning algo- rithms, such as optimistic mirror descent (OMD) (Chiang et al., 2012) Rakhlin and Sridharan 2013b). with the important twist that each player employs additional regret minimizer for meta-learning the parameterization of the base-learner; the latter component builds on the meta-learning framework of Khodak al. (2019). ). For example, in zero-sum games we leverage bound (Syrgkamis et al. (2015) in order to meta-learn the initialization of CMD across the sequences of games, leading per-game convergence rates to Nash equilibria that closely match our refined lower bound (Theorem 3.3). More broadly, in the worst-case- -ie. when the sequence of games is arbitrary- recover the near-optimal guarantees known for static games, but the similarity metries become more favorable we establish significant gains in terms of convergence to different notions of equilibria.
inttializatinndepeeedee RVU
Along the way, we also obtain new insights and results even from single-game perspective, including convergence rates of OMD and the extra- girra-gradien method in Hölder continuous variational inequal- ities (Rakhlin and Sridharan, 2013a), and certain cencoonnee-nonoomcww problems such as those considered by (Diakonikolas et al.) [022T) and stochastic games. Further, our analysis is considerably simpler than prior techniques and unifies several prior results. Finally, in Section | we evaluate our techniques on a series of poker endgames faced by the poker agent Libratus (Brown and Sandholm, 2018) against top human professionals. The experiments show that our meta-learning algorithms offer significant gains compared to solving each game in isolation, often by order of magnitude.
Table 1: A summary of our key theoretical results on meta-learning in games.
Class of games
Specific problem
Key results
Location
Bilineur saddle ppint problems
Theorems Theorems
and
Section 3.1
Zero-sum games
Hölder continuous VIs
34
Appendices
C.2
C.6
Lower bound
Theorem
Section 3.1
Potential games
Theorem
3.4
Section 3.2
General-sum games
(Course) Correlated equilibria
Theorems
D.
and D.10
Appendices
D.2
and D.3
Appruximately optimal welfare
Theorem
3.6
Section 3.2
Stackelberg games
Security games
Theorem
3.8
Section 3.3
1.2 RELATED WORK
While most prior work on learning in games posits that the underlying game remains invariant, there is ample motivation for studying games that gradually change over time, such as online advertis- ing (Nekipelov et al. 2015 Lykouris et al. 2016 Nisan and Noti 2017) or congestion games (Hoefer
et al. 2011 Bertrand et al. 2020 Meigs et al. 2017). Indeed, a number of prior works study the
performance of learning al algorithms in time- varying zero-sum games (Zhang et al. 2022b Fiez et al. 2021b; Duvocelle et al. 2022 Cardoso et al. 2019); ; there, it is natural to espouse dy dynamic notions of regret Yang et al. 2016 Zhao et al. 2000). A work closely related to ours is the recent paper by Zhang
et al. 2022b), which provides regret bounds in time-varying bilinear saddle-poing problems parameter-
2

---

Published as a conference paper at ICLR 2023
ized by the similarity of the payoff matrices and the equilibria of those games. In contrast to our meta- learning setup, they study a more general setting in which the game can change arbitrarily from round- to-round. While our problem can be viewed a special type of a varying game in which the bound- aries between different games are fixed and known, algorithms designed for generic time-varying games will not perform as well in our setting, as they do not utilize this extra information. As result, we view these results as complementary to ours. For more detailed discussion, see Appendix [A]
An emerging paradigm for modeling such considerations is meta-learning, which has gained increas- ing popularity in the machine learning community in recent years; for a highly incomplete set of pointers, we refer to (Balcan al., 2015b Al-Shvdivat al. 2018 Finn et al.) 2017 2019 Balcan et al. 2019 Li et al. 2017 Chen et al., 2022). and references therein. Our work constitutes the natural coalescence of meta-learning with the line of work on (decentralized) online learning in games. Although, as we pointed out earlier, learning in dynamic games has already received considerable attention, we are the first (to our knowledge)
formulate and address such questions within the meta- learning framework; c.f., see (Kayaalp et al. 2020: 2021| Li et al. (022). Finally, our methods may be viewed within the algorithms with predictions paradigm (Mitzenmacher and Vassilvitskii, (2020): speed up equilibrium computation by learning to predict equilibria across multiple games, with the task- similarity being the measure of prediction quality. For further related work, see Appendix
2 OUR SETUP: META-LEARNING IN GAMES
Notation We use boldface symbols to represent vectors and matrices. Subscripts are typically reserved to indicate the player, while superscripts usually correspond to the iteration or the index of the task. We let N == {1. ........ be the set of natural numbers. For E N, we use the shorthand notation [T] = 21, ..... T}. For a nonempty convex and compact set X, we denote by 2x its fz-diameter: 2xx == max ex || - x' 222 Finally, to lighten the exposition we use the (() notation to suppress factors that depend polynomially on the natural parameters of the problem.
The general setup We consider a setting wherein players interact in a sequence of T repeated games (or tasks), for some N T >>>>> 1. Each task itself consists of m E N iterations. Any fixed task t corresponds to multiplayer game (1)) between set [n] of players, with > 2: it is assumed for simplicity in the exposition that n remains invariant across the games, but some of our results apply more broadly. Each player k E [n]] selects a strategy æy from convex and compact set of strategies Xx C de with nonempty relative interior. For a given joint strategy profile x := (#1,..., x.,) E X k= Xr, there is a multilinear utility function Wkg x +> (æt,, ut (x= for each player k; where x k == (zi,..., -k-1, Ik+1, ). We will also let L > 0 be a Lipschitz parameter of each game, in the sense that for any player [n]] and any two strategy profiles æ - x'x E X Xw.
(x_ - (==(""""))) S -
(1)
Here, we use the 2 for convenience in the analysis; (I) can be translated to any equivalent
k== Ty.. the social welfare is defined as SW(x) = Ei= u4. (x), so that OPT = max N. SW(x) denotes the optimal social welfare.
norm. Finally, for a joint strategy profile x E X
A concrete example encompassed by our setup is that of extensive-form games. More broadly, it captures general games with concave utilities (Rosen) 1965. Hsieh et al. 2021).
Online learning in games Learning proceeds in an online fashion as follows. At every iteration i E [m]] of some underlying game t, each player & E [n]] has to select a strategy x (t.3) E Xg. Then, in the full information setting, the player observes as feedback the utility corresponding to the other
players' strategies at iteration i; namely, uk (t.e) = un (x (f.1)) E Rdd For convenience, we will assume k
that In (a (t.6) (I.(..)) blo I 1. The canonical measure of performance in online learning is that of external
regret, comparing the performance of the learner with that of the optimal fixed strategy in hindsight:
Definition 2.1 (Regret). Fix a player & E [n] and some game t E [T]. The (external) regret of player is defined
m
}
Rog
(1.m) = max
Σ
(at
2
(off. 10f"0,,f (1.)))
a EX
i=
3

---

Published as a conference paper at ICLR 2023
We will let a be an optimum-in-hindsighh strategy for player k in game ties broken arbitrarily, but according to a fixed rule (e.g., lexicographically) In the meta-learning setting, our goal will be optimize the average performance perpicllnee-yyiccllyy measured in terms of convergence to different game-theoretic equilibria-accnt across the sequence of games.
Optimistic mirror descent Suppose that R& : Xx + is l-strongly convex regularizer with respect to a norm || ||- We let BR, (#t || z44) = Rx(xx) - R2 (x() (VR+ (x),), 2h x denote the Bregman divergence induced by RE. where 2/. is in the relative interior of Xt. Optimistic mirror descent (OMD) (Chiang et al. 2012 Rakhlin and Sridharan (013b) is parameterized by prediction (t.2) m
IR and a learning rate 1 > O, and is defined at every iteration E N as follows.
(t,f) k == arg max E
(ox, m (mx
(..0))
- -Bx (xx 1 (1)11))
(t,i)
( 2 (1.1))
BR. (+t || / (((1i-1))
= arg max by Ex
"
(1,0) and m m == ux (x) Under Euclidean regularization, R2 (ax) = 17 I2. we will refer to OMD as optimistic gradient descent (OGD).
(1.0) arg min n. Ex Rx(+s) Further, #x
META-LEARNING HOW TO PLAY GAMES
In this section, present our main theoretical results: provable guarantees for online and decen- tralized meta-learning in games. We commence with zero-sum games in Section and we then transition general-sum games (Section 3.2) and Stackelberg (security) games (Section 3.3
3.1 ZERO-SUM GAMES
We first highlight our results for bilinear saddle-point problems (BSPPs), which take the form min max æ Ay, where A Rd,, Xd, the payoff matrix of the game. canonical application for this setting is on the solution of zero-sum inperfect-informatio games (Romanovskil 1962] Koller and Megiddo 1992), as we explore in our experiments (Section 4 Next we describe number of extensions to gradually more general settings, and we conclude with our lower bound (Theorem 3.3 The proofs from this subsection are included Appendix C
extensive-
We first derive a refined meta-learning convergence guarantee for the average of the players' strategies. Below, denote by V 1 min Σt= (I=(() æ=12 the task similarity metric for player æ, written terms of the
strategies; analogous notation is used for player y.
Theorem 3.1 (Informal; Detailed Version in Corollary C.2 Suppose that both players employ
OGD with a suitable (fixed) learning rate and follow the leader over previous pptimum-in-hindsee strategies for the initialization. Then, the game-average duality gap of the players' average strategies is bounded by
Σ T
m [Reg!.. + Reegf
2L m (V2 +V2)
8L(1 + log T') (N + +2²)
mT
Here, the second term in the right-hand side of (2) becomes negligible for large number of games T, while the first term depends on the task similarity measures. For any sequence of games, Theorem 3.1 nearly matches the lower bound in the single-task setting (Daskalakis et al. 2015). but our guarantee can be significantly better when V?2 V2 << 1. To achieve this, the basic idea is to use-on top of OGD-a "meta" regret minimization algorithm that, for each player, learns sequence of initializations by taking the average of the past optima-in -innidssight, which is equivalent follow the leader (FTL) over the regret upper-bounds of the within-task algorithm; see Algorithm (in Appendix B for pseudocode of the veeta-version of OGD consider. Similar results can be obtained more broadly for OMD (c.f., see Appendices and We also obtain analogous refined bounds for the individual regret of each player (Corollary C.4).
One caveat of Theorem 3.1 is that the underlying task similarity measure could be algorithm- dependent, the -iwninuu------iiiiigle for each player could depend on the other player's
4

---

Published as a conference paper at ICLR 2023
behavior. To address this, show that if the meta-learner can initialize using Nash equilibria (NE) (recall Definition Cc55 from previously seen games, the game-average last-iterate rates gracefully decrease with the similarity of the Nash equilibria of those games. More precisely, if
m Ei= || - =112, where 2((.*) is any Nash equilibrium of the 1-th game. As we point out in the sequel, we also obtain results under more favorable notion of task similarity that does not depend the worst sequence of NE.
= (x, y) x Z, we let Vi == + max,(t..),......
Theorem 3.2 (Informal; Detailed Version in Theorem C.S). When both players employ OGD with a suitable (fixed) learning rate and FTL over previous NE stralegies for the initialization, then
2 8(1 + T)
m - e
(2²x + +5))
Tea
iterations suffice to reach an (c)) -ap--apppppaateee Nash equilibrium on average across the games.
Theorem 3.2 recovers the optimal -1/2 rates for OGD (Golowich et al. 2020a by under arbitrary sequence of games, but offers substantial gains in terms of the average iteration complexity when the Nash equilibria of the games are close. For example, when they lie within ball of fy-diameter
V |0(23 + 22,)), for some å E (0, 1J. Theorem 3.2 improves upon the rate of OGD by at least multi- plicative factor of 1/6 as T + oc. While
speaking, randomly perturbed-zero-sun (normal-form games have a unique Nash equilibrium (van Damme 1987). the worst-case NE simi- larity metric used in Theorem 3.2 can be loose under multiplicity of equilibria. For that reason, in Ap- pendix C.1.2 we further refine Theorem 3.2 using the most favorable sequence of Nash equilibria; this requires that players know each game after its termination, which is arguably well-motivated assump- tion in some applications. We further remark that Theorem 3.2 can be cast in terms of the similarity V? + V22 instead of V.NE: using the parameterization of Theorem 3.1 Finally, since the base-Icarnee can be viewed as an algorithm with predictions the number of iterations to compute an approximate NE is smaller if the Euclidean error of a prediction of it (the initialization) is small- 3.2 can also be viewed as learning these predictions (Khodak et al. 2022) by targeting that error measure.
Extensions Moving beyond bilinear saddle-pot -oont problems, we extend our results to gradually broader settings. First, in Appendix C.2 we apply our techniques to general variational inequality problems under Lipschitz continuous operator for which the so-called MVI property (Mertikopoulos) et al. 2019) holds. Thus, Theorems 3.1 and 3.2 are extended to settings such as smooth convex-concave games and zero-sum polymatrix (multiplayer) games (Cai al. 2016). Interestingly, extensions are possible even under the weak MVI property (Diakonikolas et al. 2021), which captures certain "structured"
nonooocc--non games. In a similar vein, we also study the challenging setting of Shapley's 's stochastic games (Shapley 1953) (Appendix C.5). There, we show that there exists a time-vrrying iisstead of constant but non-vanishing learning rate schedule for which OGD reaches minimax equilibria, thereby leading to similar extensions in the meta-learning setting. Next, we relax the underlying Lipschitz continuity assumption underpinning the previous results by instead imposing only HöHöld continuity (recall Definition C.32). We show that in such settings OGD enjoys a rate of m -0/2 (Theorem C.34j, which is to our knowledge a new result; in the special case where a = 1, we recover the recently established m -1/2 rates. Finally, while we have focused on the OGD algorithm, our techniques apply to other learning dynamiis as well. For example, in Appendix C.7 we show that the extensively studied extra-grading (EG) algorithm (Korpelevich) 1976) can be analyzed in a unifying way with OGD, thereby inheriting all of the aforementioned results under OGD; this significantly broadens the implications of (Mokhtari et al. 2020), which only applied in certain unconstrained problems. Perhaps surprisingly, although EG is not a no-regret algorithm, our analysis employs regret-based framework using a suitable proxy for the regret (see Theorem C.35).
Lower bound We conclude this subsection with lower bound, showing that our guarantee in Theorem 3.1 is essentially sharp under a broad range of our similarity measures. Our result significantly refines the single-game lower bound of Daskalakis et al. (2015) by constructing an appropriate distribution over sequences of zero-sum games.
Theorem 3.3 (Informal: Precise Version in Theorem C.39 For any >> 0, there exists a distribution over sequences of T zero-sum games, with sufficiently large T = T(c), such that
T
E E[Reg (t.m) + +Reg (t.m)
>
( + V22) -
2 Vi2 c.
T
2
5

---

Published as a conference paper at ICLR 2023
3.2 GENERAL-SUM GAMES
In this subsection, we switch our attention to general-sum games. Here, unlike zero-sum games, no-regret learning algorithms instead known to generally converge-in a time-average sense-to correlated equilibrium concepts, which are more permissive than the Nash equilibrium. Nevertheless, there are structured classes of general-sum games for which suitable dynamics do reach Nash equilibria; perhaps the most notable example being that of potential games. In this context, we first obtain meta-learning guarantees for potential games, parameterized by the similarity of the potential functions. Then, we derive meta-learning algorithms with improved guarantees for convergence to correlated and coarse correlated equilibria. Finally, we conclude this subsection with improved guarantees of convergence to near-optimal- in terms of social celfare--quilibria Proofs from this subsection are included in Appendices and D
Potential games A potential game is endowed with the additional property of admitting potential: a player-independent function that captures the player's benefit from unilaterally deviating from any given strategy profile (Definition D.2. In our meta-learning setting, we posit sequence of potential games ($(+)) each described by its potential function. Unlike our approach in Section 3.I a central challenge here is that the potential function is in general nonconcaveenonconvee, precluding standard regret minimization approaches. Instead, we find that by initializing at the previous last-iterate the dynamics still manage to adapt based on the similarity
=== = 7 Σ deviation of the potential functions. This initialization has the additional benefit of being agnostic to the boundaries of different tasks. Unlike our results in Section 3.1, the following guarantee applies
-1 A($!!), ((((+))) where A($, Φ') = max (+(x)) ('(x)), which captures the
even for vanilla (i.e., non-optimistic) projected gradient descent (GD).
Theorem 3.4 (Informal; Detailed Version in Corollary D.5). GD with suitable parumeterization
requires O (v + (xp)) iterations to reach an e-approximate Nash equilibrium on average across
the T potential games, where max (x)) < max--
Theorem 3.4 matches the known rate of GD for potential games in the worst case, but offers substantial gains in terms of the average iteration complexity when the games are similar. For example, if (z) + (((1) (a:) S ax for all x E X Xs and / 2 2, then O(a/+²) iterations suffice to reach an e-approximate NE on an average game, as T + -00. Such a scenario may arise in, e.g.,
sequence of routing games if the cost functions for each edge change only slightly between games.
Convergence to correlated equilibria In contrast, for general games the best one can hope for is to obtain improved rates for convergence to correlated or coarse correlated equilibria (Hart and Mas Colell 2000 Blum and Mansour 2007). It is important to stress that learning correlated equilibria is fundamentally different than learning Nash equilibria- which for the former any initialization conld fail to exploit the learning in the previous task (Proposition D.I]: unlike Nash equilibria, correlated equilibria (in general) cannot be decomposed for each player, thereby making uncoupled methods unlikely to adapt to the similarity of CE. Instead, our task similarity metrics depend on the optima-in iilima-in-hindaee hindsightt for each player. Under this notion of task similarity, we obtain task-average guarantees for CCE by meta- learnng the initialization (by running FTL) and the learning rate (by running the EWOO method of Hazan et al. (2007) over sequence of regret upper bounds) of optimistic hedge (Daskalakis et al. 2021) (Theorem D.7]- -OMD with entropic regularization. Similarly. to obtain guarantees for CE, we use the no-swap-regre' construction of Blum and Mansour (2007) in conjuction with the logarithmic barrier (Anagnostides et al. 2022a) (Theorem D.10).
product distributions. For example, is inevitably a product distribution in the case of uncoupled
3.2.1 SOCIAL WELFARE GUARANTEES
We conclude this subsection with meta-learning guarantees for converging to near-optimal equilibria (Theorem 3.6) Let us first recall the following central definition.
Definition 3.5 (Smooth games (Roughgarden, 2015)). A game G is (), p)-soooth, with X, p > if there exists strategy profile xx xX==1 Ns such that for any x X Xr.
uu (2 x xx 2 AOPT-
(3)

---

Published as a conference paper at ICLR 2023
where OPT is the optimal social welfare and (a)x) is the social welfare of joint strategy profile
Smooth games capture a number of important applications, including network congestion games (Awerbuch et al.) 2013 Christodoulou and Koutsoupias (005) and simultaneous auc- tions (Christodoulou et al. 2016 Roughgarden et al.J (017)) (see Appendix [ for additional examples); both of those settings are oftentimes non-static in real-world applications, thereby motivating our meta-learning considerations. In this context, we assume that there is a sequence of smooth games (g(t)) each of which is (A(t), (u())) --mooth (Definition 3.5
Theorem 3.6 (Informal; Detailed Version in Theorem B.IT). If all players OGD with suitable parameterization in sequence of games (G()) IEEST. each of which (A(5,, pl)) >-mooth,, then
m (W(all)))
1 T
X mOO)
OPT() 2L n V2 δ
(4)
mT
m
mT
where OPT(*) is the optimal social welfare attainable at game g and Ö() hides logarithmic terms.
The first term in the right-hand side of 4 is the average robust PoA in the sequence of games, while the third term vanishes as T + oc. The orchestrated learning dynamics reach approximately optimal equilibria much faster when the underlying task similarity is small; without meta-learning one would instead obtain the m -1 rate known from the work of #Syrgkanis et al. (2015). Theorem 3.6 is established by first providing a refined guarantee for the sum of the players regrets (Theorem [B.3)
and then translating that guarantee in terms of the social welfare using the smoothness condition for each game (Proposition B. Our guarantees are in fact more general, and apply for any suitable linear combination of players' utilities (see Corollary B.12
3.3 STACKELBERG (SECURITY) GAMES
To conclude theoretical results, we study meta-learning in repeated Stackelherg games. Following the convention of Balcan et al. (2015a), we present our results in terms of Stackelberg security games, although our results apply general Stackelberg games well (see (Balcan et al. 2015a Section 8) for details on how such results extend).
Stackelberg security games repeated Stackelberg security game is a sequential interaction between a defender and m attackers. In each round, the defender commits to mixed strategy over d targets to protect, which induces a coverage probability vector x: E A over targets. After having observed coverage probability vector, the attacker best responds by attacking some target b(x: E [d] in order to maximize their utility in expectation. Finally, the defender's 's utility is some function of their coverage probability vector æ and the target attacked b(æ)).
a well-known fact that no-regret learning in repeated Stackelberg games not possible without any prior knowledge about the sequence of followers (Balcan et al. 2015a| Section 7), so we study the setting in which each attacker belongs to one of & possible attacker types. We allow sequence of attackers to be adversarially chosen from the & types. and assume the attacker's type is revealed to the leader after each round. We adapt the methodology of Balcan et al. (2015a) to our setting by meta-learning the initialization and learning rate of the multiplicative weights update (henceforth MWU) run over a finite (but exponentially-large corresponds leader mixed strategy, and & can be constructed in such a way that it will always contain mixed strategy which is arbitrarily close to the optima-in-hindsighht for each task 2
set of extreme points & C A A Each point æ E &
Our results are given in terms of guarantees on the task-av ause-aeeage Stackelberg regret, which measures the difference in utility between the defender's 's deployed sequence of mixed strategies and the optima-in-hindsighe given that the attacker best responds.
Definition 3.7 (Stackelberg Regret). Denote attacker f(t.0)'s best response mixed strategy as bya.s (x). The Stackelberg regret of the attacker in repeated Stackelberg security game t is
StackReg (t.mm (t(()=
Σ (t ( (b (xo(t.)),
(t)) (byrr. (2) (t) ))).
'This is likely unavoidable, as Li et al. 2016) show computing Stackelberg strategy is strongly NP-Hard. For a precise definition of how to construct we point the reader (Balcan al. 20155a Section 4).
7

---

Published as a conference paper at ICLR 2023
In contrast to the standard notion of regret (Definition 2.1p. Stackelberg regret takes into account the extra structure in the defender's 's utility in Stackelberg games; namely that it is a function of the defender's 's current mixed strategy (through the attacker's best response).
Theorem 3.8 (Informal; Detailed Version in Theorem F.1 Given a sequence of repeated Stackelberg security games with d targets, k attacker types, and within time-horizon m, running MWU over the set of extreme points & as defined in Balcan et al. (2015a) with suitable initialization and sequence of learning rates achieves task-averaged expected Stackelberg regret
Σ T
1
E|StackReg (t.m) (0)]=-(vH))))) Hm) + or (poly(m,,11)),
where the sequence of attackers in each task can be adversarially chosen, the expectation is with respect to the randomness of MWU. == Et= git), where ÿ(t) is the optimum inmuum--i--aae in-hindsight distribution over mixed strategies in E for game t. H is the Shannon entropy of y, and or (1) suppresses terms which decay with T.
(y) < log [E), so in the worst-case our algorithm asymptotically matches the Olv m log [&]) performance of the algorithm of Balcan al. (2015a). Entropy (ÿ) small whenever the same small set of mixed strategies are optimal for the sequence of T Stackelberg games. For example, if in each task the adversary chooses from < 1t attacker types who are only interested in attacking u < targets (unbeknownst to the meta-learner) H HD)) O(sau O(s"ulog(su)) In Stackelberg security games | ((22 + dd ), so log [ = O(d k log(dk)) Finally, the distance between the set of opti- mal strategies does not matter, as y is categorical distribution over discrete set of mixed strategies.
EXPERIMENTS
In this section, we evaluate our meta-learning techniques in two River endgames that occurred in the Brains vs Al competition (Brown and Sandholm, 2018). We use the two public endgames that were released by the authors denoted 'Endgame A and 'Endgame B.' each corresponding to zero-sum extensive-form game. For each of these endgames, we produced T 200 individual tasks by varying the size of the stacks of each player according to three different task sequencing setups
(random stacks) In each task we select stack sizes for the players by sampling uniformly at random multiple of 100 in the range [1000, 20000).
2. (sorted stacks) Task & E { {1..... 200} corresponds to solving the endgame where the stack sizes are set to the amount x 100 for each player.
3. (alternating stacks) We sequence the stack amounts of the players as follows: in task 1, the stacks are set to 100; in task 2 to 200, 000; in task 3 to 200; in task 4 to 199, 900; and so on.
For each endgame, we tested the performance when both players (1) employ OGD while meta-learning the initialization (Theorem 3.1 with m. (f.1) Oa, and my (f.1) Oa,, (2) employ OGD while setting
the initialization equal to the last iterate of the previous task (see Remark [B.8). and (3) use the vanilla initialization of OGD-i.e. the players treat each game separately. For each game, players m := 1000 iterations. The f2 projection to the sequence-fore polytope (Romanovskij 1962 Koller and Megiddo 1992)-the strategy set of each player in extensive-form games required for the steps of OGD is implemented via an algorithm originally described by Gilpin et al. (2012), and further clarified in (Farina et al.) 2022 Appendix B). We tried different learning rates for the players selected from the set {0.1, 0.01, 0.001 J. Figure illustraates our results for == 0.01, while the others are deferred Appendix F In the table at the top of Figure [ we highlight several parameters of the endgames including the board configuration, the dimensions of the players' strategy sets-i.e -ie. the sequences-and the number of nonzero elements in each payoff matrix. Because of the scale of the games, we used the Kronecker sparsification algorithm of Farina and Sandholm (002 Technique A) in order to accelerate the training.
OOtainned from https::t//// //tgt//tttttb www/Sanchooooeoeeooooooooo m- hww.r///nniniiiiiiaaaussuunnaaaa 'While in the general meta- metaaleernnngg setup it is assumed that the number of tasks is large but per-task data is limited (i.e." T > m), we found that setting T 200 was already sufficient see substantial henefits.
8

---

Published as a conference paper at ICLR 2023
Sequences
Decision Points
Payoff Matrix
Game
Board
Pot
Pl. 1
Pl. 2
Pl.
Pl. 2
num. nonzeros
Endgame A
J
K 5
Q 7
3,700
18,789
19,237
6,710
6,870
14,718,290
Endgame
104
9
2
500
46,875
47,381
16,304
16,480
62,748,525
Endgame A [random stacks]
Endgame A ssorted stacks]
Endgame [altern. stacks]
Trek-vennge gap
100
60
100
40
20
20
Task
Task
Tisk
Endgame B [random stacks]
Endgame B [sorted stacks]
Endgame [altern. stacks]
150
gap
100
100
50
50
25
Task
Task
Tisk
Meta learning (avg. cast-i-hiindiihtt
Meta learning (last iterate)
meta learning
Figure I: (Top) Parameters of each endgame. (Bottom) The task-averaged NE gap of the players' average strategies across 200 tasks, 2 endgames, and 3 different stack orderings. Both players use OGD with 1) == 0.01. For the random stacks, we repeated each experiment 10 times with different random seeds. The plots show the mean (thick line) as well as the minimum and maximum values. We see that across all task sequencing setups, meta-learning the initialization (using either technique) leads to up to an order of magnitude better performance compared to vanilla OGD. When stacks sorted, initializing the last iterate of the previous game obtains the best performance, whereas when stacks are alternated or random, initializing according to Theorem 3.1 performs best.
CONCLUSIONS AND FUTURE RESEARCH
In this paper, we introduced the study meta-learning in games. In particular, we considered many of the most central game classes-including zero-sum games, potential games, general-sum multi-player games, and Stackelberg security games-and obtained provable performance guarantees expressed terms of natural measures of similarity between the games. Experiments on several sequences of poker endgames that were actually played in the Brains Al competition (Brown and Sandholm 2018) show that meta-learning the initialization improves performance even by an order of magnitude.
Our results open the door to several exciting directions for future research, including meta-learning in other settings for which single-game results are known, such as general sunconvve-nnoconnea min-max problems (Suggala and Netrapalli, (020)), the nonparametric regime (Daskalakis and Golowich| 2022), and partial feedback (such as bandit) models (Wei and Luo 2018 Hsieh et al. 2022 Balcan et al., 2022 Osadchiy et al.] (022). Another interesting, yet challenging, avenue for future research would be to consider strategy sets that can vary across tasks.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
We are grateful to the anonymous ICLR reviewers for valuable feedback. KH is supported by NDSEG Fellowship. IA and TS are supported by NSF grants IIS- 1901403 and CCF- and the ARO under award W91 INF2010081. MK is supported by Meta Research PhD Fellowship. ZSW is supported in part by the NSF grant 193-693, a Google Faculty Research Award, a J.P. Morgan Faculty Award, Meta Research Award, and Mozilla Research Grant. The authors would like to thank Nina Balcan for helpful discussions throughout the course of the project. IA grateful to loannis Panageas for insightful discussions regarding Appendix C.5
REFERENCES
Jacob D. Abernethy, Kevin A. Lai, Kfir Y. Levy, and Jun-Kun Wang. Faster rates for convex-concave games. In Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, volume 75 of Proceedings of Machine Learning Research, pages 1595-1625. PMLR, 2018
Alekh Agarwal, Sham M. Kakade, Jason D. Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Mach. Learn. Res., 22: 98:1-98:76, 2021.
Maruan Al-Shedivat, Trapit Bansal, Yura Burda, Ilya Sutskever, Igor Mordatch, and Pieter Abbeel. Continuous adaptation via meta-learning in nonstationary and competitive environments. In 6th International Conference on Learning Representations, ICLR 2018. OpenReview.net, 2018.
Ioannis Anagnostides, Gabriele Farina, Christian Kroer, Chung- Weing-Weilll Lee, Haipeng Luo, and Tuomas Sandholm. Uncoupled learning dynamics with (loo T) swap regret in multiplayer games. arXiv preprint arXiv:2204. 1417, 2022a.
Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On last-iterate convergence beyond pero-sum games. In International Conference on Machine Learning, ICML 2022, volume 162 of Proceedings of Machine Learning Research, pages 536-55 666558. PMLR, 2022b.
Robert J. Aumann. Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics, 1(1):67-96, 1974.
Baruch Awerbuch, Yossi Azar, and Amir Epstein. The price of routing unsplittable flow. SIAM J. Comput., 42(1): 160-7766 2013.
Waiss Azizian, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. The last-iterate convergence rate of optimistic mirror descent in stochastic variational inequalities. In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, volume 134 of Proceedings of Machine Learning Research, pages 326-358. PMLR, 2021.
Maria-Florina Balcan, Avrim Blum, Nika Haghtalab, and Ariel D Procaccia. Commitment without regrets: Online learning in stackelberg security games. In Proceedings of the sixteenth ACM conference on economics and computation, pages 61-78, 2015a.
Maria-Florina Balcan, Avrim Blum, and Santosh S. Vempala. Efficient representations for lifelong learning and autoencoding. In Proceedings of The 28th Conference on Learning Theory, COLT 2015, volume 40 of JMLR Workshop and Conference Proceedings, pages 191-210. JMLR.org, 2015b.
Maria-Florina Balcan, Mikhail Khodak, and Ameet Talwalkar. Provable guarantees for gradient-based meta-learning. In Proceedings of the 36th International Conference on Machine Learning, ICML. 2019, volume 97 of Proceedings of Machine Learning Research, pages 424-433. PMLR, 2019.
Maria-Florina Balcan, Keegan Harris, Mikhail Khodak, and Zhiwei Steven Wu. Meta-learning adversarial bandits. arXiv preprint arXiv:2205. 14128, 2022.
Arindam Banerjee, Srujana Merugu, Inderjit S. Dhillon, and Joydeep Ghosh. Clustering with bregman divergences. J. Mach. Learn. Res., 6:1 6:149917749 2005.
10

---

Published as a conference paper at ICLR 2023
Heinz H. Bauschke, Walaa M. Moursi, and Xianfu Wang. Generalized monotone operators and their averaged resolvents. Math. Program., 189:55-775 74, 2021.
Nathalic Bertrand, Nicolas Markey, Suman Sadhukhan, and Ocan Sankur. Dynamic network con- gestion games. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2020, volume 182 of LIPles, pages 40:1-40:16. Schloss Dagstuhl- Leibniz-7Zentrum für Informatik, 2020.
Benjamin E. Birnbau,, Nikhil R. Devanur, and Lin Xiao. Distributed algorithms via gradient descent for fisher markets. In Proceedings 12th ACM Conference on Electronic Commerce (EC-201 1), 20/1, pages 127-136. ACM, 2011.
Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as easy as statistical learning. In Conference on Learning Theory, 2-5 July 2022, volume 178 of Proceedings of Machine Learning Research, pages 1716-1786. PMLR, 2022.
Avrim Blum and Yishay Mansour. From external internal regret. Journal of Machine Learning Research, 8(6), 2007.
Noam Brown and Tuomas Sandholm. Regret transfer and parameter optimization. In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014, pages 594-601. AAAI Press, 2014.
Noam Brown and Tuomas Sandholm. Regret-based pruning in extensive-form games. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, pages 1972-1980. 2015a.
Noam Brown and Tuomas Sandholm. Simultaneous abstraction and equilibrium finding in games. In Proceedings of the Swenty-Fourts International Joint Conference on Artificial Intelligence, IJCAI 2015, pages 489 496. AAAI Press, 2015b.
Noam Brown and Tuomas Sandholm. Strategy-basee warm starting for regret minimization in games. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, pages 432-438. AAAI Press, 2016.
Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374) 2018.
Noam Brown and Tuomas Sandholm. Solving imperfect-infoon infoommatooo games via discounted regret minimization. In The Thirty-Third AAAI Conference Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, 2019, pages 1829-1836. AAAI Press, 2019.
Yang Cai and Weiqiang Zheng. Accelerated single-call methods for constrained min-max optimization. CoRR, abs/2210.0300 2022.
Yang Cai, Ozan Candogan, Constantinos Daskalakis, and Christos H. Papadimitriou. Zero-sum polymatrix games: A generalization of minmax. Math. Oper. Res., 41(2):648 660866555211 2016.
Ozan Candogan, Asuman E. Ozdaglar, and Pablo A. Parrilo. Dynamics in near-potential games. Games Econ. Behav., 82:66-9:: 90, 2013.
Adrian Rivera Cardoso, Jacob D. Abernethy, He Wang, and Huan Xu. Competing against nash equilibria in adversarially changing zero-sum games. In Proceedings of the 36th International Conference on Machine Learning. 2019, volume 97 of Proceedings of Machine Learning Research, pages 921-930 PMLR, 2019.
Nicolo Cesa- Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
Nicolò Yishay Mansour, and Gilles Stoltz. Improved second-ordes bounds for predic- tion with expert advice. Mach. Learn., 66(2-3):321-352, 2007.

---

Published as a conference paper at ICLR 2023
Xi Chen, Xiaotie Deng, and Shang-Hur Hua Teng. Settling the complexity of computing two-player nash equilibria. J. ACM, 16:3):1411114:55, 2009.
Xi Chen, Christos H. Papadimitriou, and Binghui Peng. Memory bounds for continual learning. CoRR, abs/2204.10830. 2022.
Chao-Kai Chiang. Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. COLT 2012- The 25th Annual Con- ference Learning Theory, 20/2, volume 23 of JMLR Proceedings, pages 6. 6.1-0. JMLR.org. 2012.
George Christodoulou and Elias Koutsoupias. The price of anarchy of finite congestion games. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 67-73. ACM, 2005.
George Christodoulou, Annamária Kováes, and Michael Schapira. Bayesian combinatorial auctions. J. ACM, (112)11:1-11:11 2016.
Patrick L. Combettes and Teemu Pennanen. Proximal methods for cohypomonotone operators. SIAM Control. Optim., 43(2):731-743 2004.
Constantinos Daskalakis and Noah Golowich. Fast rates for nonparametric online learning: from realizabillity to learning in games. STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing. 2022, pages 846-859, ACM, 2022.
Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing a nash equilibrium. SIAM J. Comput., 39(1):155-25, 2009.
Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algorithms for zero-sum games. Games Econ. Behav., 92:327-348, 2015.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with op- timism. In 6th International Conference on Learning Representations, ICLR 2018. OpenReview.net, 2018.
Constantinos Daskalakis, Dylan J. Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. Advances in Neural Information Prucessing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurIPS 2020, 2020.
Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, pages 27604-27616, 2021.
Jelena Diakonikolas, Constantinos Daskalakis, and Michael I. Jordan. Efficient methods for structured -ecconve-nnonconcave min-max optimization. In The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, volume 130 of Proceedings of Machine Learning Research, pages 2746-2754. PMLR, 2021.
John C. Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. J. Mach. Learn. Res., 12:2121-2159, 2011.
Benoit Duvocelle, Panayotis Mertikopoulos, Mathias Staudigl, and Dries Vermeulen. Multiagent online learning in varying games. Mathematics of Operations Research, 2022.
Gabriele Farina and Tuomas Sandholm. Fast payoff matrix sparsification techniques for structured extensive-form games. In AAAI Conference on Artificial Intelligence, 2022.
Gabriele Farina, loannis Anagnostides, Haipeng Luo, Chung Wei Lee, Christian Krocr, and Tuomas Sandholm. Near-optimal no-regret learning for general convex games. CoRR, abs/2206.08742. 2022.
Tanner Fiez, Lillian Ratliff, Eric Mazumdar, Evan Faulkner, and Adhyyan Narang. Global convergence to local minmax equilibrium in classes of nonconvex zero-sum games. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, pages 99049-29066 2021a
12

---

Published as a conference paper at ICLR 2023
Tanner Fiez, Ryann Sim, Stratis Skoulakis, Georgios Piliouras, and Lillian J. Ratliff. Online learning in periodie zero-sum games. In Advances Neural Information Processing Systems 34: Annual Conference Neural Information Processing Systems 2021, pages 10313-10325, 2021b.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-leaming for fast adaptation of deep networks. In Proceedings the 34th International Conference Machine Learning, ICML 2017, volume 70 of Proceedings of Machine Learning Research, pages 1126-1 135. PMLR, 2017.
Chelsea Finn, Aravind Rajeswaran, Sham M. Kakade, and Sergey Levine. Online meta-learning. In Proceedings of the 36th International Conference on Machine Learning, ICMI. 2019, volume 97 of Proceedings of Machine Learning Research, pages 1920-1930. PMLR, 2019.
Yoav Freund and Robert E. Schapire. decision-theoretii generalization of on-line learning and an application to boosting. J. Comput. Syst. Sci., 55(1):119-133) 1997.
Yuan Gao, Christian Kroer, and Donald Goldfarb. Increasing iterate averaging for solving saddle- point problems. In Thirty-Fiiy Fiith AAAI Conference Artificial Intelligence, AAAI 2021, pages 7537-7544. AAAI Press, 2021.
Angeliki Giannou, Emmanouil- Vasileios Vlatakis- KaaraaaGGaaaa,,,s,, and Panayotis Mertikopoulos. Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information. In Conference on Learning Theory, COLT 2021, volume 134 of Proceedings of Machine Learning Research, pages 2147-2148. PMLR, 2021.
Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. varia- tional inequality perspective generative adversarial networks. In 7th International Conference on Learning Representations, ICLR 2019. OpenReview.net, 2019.
Andrew Gilpin, Javier Peña, and Tuomas Sandholm. First-order algorithm with (In(1/c) con- vergence for c-equilibrium two-person zero-sum games. Math. Program.. 133(1 (3311)):279-11 2012.
Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis. Tight last-iterate convergence rates for no-regret learning in multi-player games. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020a.
Noah Golowich, Sarath Pattathil, Constantinos Daskalakis. and Asuman E. Ozdaglar. Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems. Conference on Learning Theory, COLT 2020, volume 125 of Proceedings of Machine Learning Research, pages 1758-1784. PMLR, 2020b.
Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang. Oracle-efficient online learning for beyond worst-case adversaries. CoRR, abs/2202.08549, 2022.
Sergiu Hart and Andreu Mas-Colell A simple adaptive procedure leading correlated equilibrium. Econometrica, 68(5):1127-111) 2000.
Sergiu Hart and David Schmeidler. Existence of correlated equilibria. Mathematics of Operations Research, 14(1):18 (00:18--55 25, 1989.
Jason D. Hartline, Vasilis Syrgkanis, and Éva Tardos. No-regret learning in bayesian games. In Advances Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, pages 3061-3069, 2015.
Elad Hazan and Satyen Kale. Extracting certainty from uncertainty: regret bounded by variation in costs. Mach. Learn., 80(2-3): 2010.
Elad Hazan and Satyen Kale. Better algorithms for benign bandits. Mach. Learn. Res., 12: 1287-1311, 2011.
Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2):169-192. 2007.
13

---

Published as a conference paper at ICLR 2023
Martin Hoefer, Vahab S. Mirrokni, Heiko Röglin, and Shang-Hur Teng. Competitive routing time. Theor. Comput. Sci., 412(33):5420-5444 5432, 2011.
Josef Hofbauer and William H. Sandholm. On the global convergence of stochastic fictitious play. Econometrica, 2066):2265,2294, 2002.
Yu-Guan Hsich, Franck Iutzeler, Jéröme Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra-gradice methods. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, pages 6936-6946, 2019.
Yu-Guan Hsieh, Kimon Antonakopoulos, and Panayotis Mertikopoulos. Adaptive learning in continuous games: Optimal regret bounds and convergence to nash equilibrium. In Conference on Learning Theory, COLT 2021, volume 134 of Proceedings of Machine Learning Research, pages PMLR, 2021.
Yu-Guan Hsieh, Kimon Antonakopoulos, Volkan Cevher, and Panayotis Mertikopoulos. No-regret learning in games with noisy feedback: Faster rates and adaptivity via learning rate separation. CoRR, abs/2206.00015, 2022.
Ramesh Johari and John N. Tsitsiklis. Efficiency loss in network resource allocation game. Mathematics of Operations Research, 29(3):407-435, 2004.
Mert Kayaalp. Stefan Vlaski, and Ali H. Sayed. Dif-maml: Decentralized multi aagent meta-learning. CoRR, abs/2010.02870, 2020.
Mert Kayaalp. Stefan Vlaski, and Ali H Sayed. Distributed meta-learning with networked agents. In 2021 29th European Signal Processing Conference (EUSIPCO), pages 1361-1365, IEEE, 2021.
Mikhail Khodak, Maria-Florina F Balcan, and Ameet S Talwalkar, Adaptive gradient-based meta- learning methods. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Mikhail Khodak, Maria-Florina Balcan, Ameet Talwalkar, and Sergei Vassilvitskii. Learning pre- dictions for algorithms with predictions. In Advances in Neural Information Processing Systems, 2022. To appear.
Robert Kleinberg, Georgios Piliouras, and Éva Tardos. Multiplicative updates outperform generic no-regret learning in congestion games: extended abstract. In Proceedings of the 41 Annual ACM Symposium on Theory of Computing, STOC 2009, pages 533-542. ACM, 2009.
Daphne Koller and Nimrod Megiddo. The complexity of two-person zero-sum games in extensive form. Games and Economic Behavior, 4(4):528-555) 1992.
Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Christian Kroer and Tuomas Sandholm. unified framework for extensive-fore form game abstraction with bounds. In Advances in Neural Information Processing Systems 31: Annual Conference Neural Information Processing Systems 2018, pages 613-624, 2018.
Stefanos Leonardos, Will Overman, Ioannis Panageas, and Georgios Piliouras. Global convergence of multi-agent policy gradient in markov potential games. In The Tenth International Conference on Learning Representations, ICLR 2022. OpenReview.net, 2022.
Shuangtong Li, Tianyi Zhou, Xinmei Tian, and Dacheng Tao. Learning to collaborate in decentralized learning of personalized models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9766-9775, 2022.
Yuqian Li, Vincent Conitzer, and Dmytro Korzhyk. arXiv:1602.018%6 2016.
Catcher-evader games.
arXiv preprint
Zhenguo Li, Fengwei Zhou, Fei Chen. and Hang Li. Meta-sgd: Learning to learn quickly for few shot learning. CoRR, abs/1 /0//1777.00 707.09835, 2017.
14

---

Published as a conference paper at ICLR 2023
Brendan Lucier and Allan Borodin. Price of anarchy for greedy auctions. In Proceedings of the Twenty-Firsy Anmual ACM- Symposium on Discrete Algorithms, SODA 2010, pages 537-553. SIAM, 2010.
Haipeng Luo and Robert E. Schapire. Achieving all with no parameters: Adanormalhedge. In Proceedings of The 28th Conference on Learning Theory, COLT 2015, volume 40 of JMLR Workshop and Conference Proceedings, pages 1286-1304. JMLR.org, 2015.
Thodoris Lykouris, Vasilis Syrgkanis, and Éva Tardos. Learning and efficiency in games with dynamic population. Proceedings of the Twenty-Sevenlee Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pages 120-129. SIAM, 2016.
H. Brendan McMahan. Follow-the teepwwthe-rggghe regularized-leatee leader and mirror descent: Equivalence theorems and LI regularization. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2011, I, volume 15 of JMLR Proceedings, pages 525-533.
JMLR.org. 2011.
Emily Meigs, Francesca Parise, and Asuman E. Ozdaglar. Learning dynamics in stochastic routing games. In 55th Annual Allerton Conference on Communication, Control, and Computing. Allerton 20/7, pages 259-266. IEEE, 2017.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-poin problems: Going the extra (gradient) mile. In 7th International Conference on Learning Representations, ICLR 2019. Open- Review.net, 2019.
Paul Milgrom and John Roberts. Rationalizability, learning, and equilibrium in games with strategic complementarities. Econometrica, 58(6):1255-1277 1990.
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Tim Roughgarden, editor, Beyond the Worst-Case Analysis of Algorithms, pages 646-662. Cambridge University Press, 2020.
Aryan Mokhtari, Asuman E. Ozdaglar, and Sarath Pattathil. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, volume 108 of Proceedings of Machine Learning Research, pages 1497-1507. PMLR, 2020.
Denis Nekipelov, Vasilis Syrgkanis, and Éva Tardos. Econometrics for learning agents. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC 11, pages 1-18. ACM, 2015.
J. V. Neumann. A model of general economic equilibrium. The Review of Economic Studies, 13(1): 1-9, 1945.
Noam Nisan and Gali Noti. An experimental evaluation of regret-based econometrics. In Proceedings of the 26th International Conference on World Wide Web, WWW 2017, pages 73-81, ACM, 2017.
Ilya Osadchiy, Kfir Y Levy, and Ron Meir. Online meta-learning adversarial multi-armed bandits. arXiv preprint arXiv: 2205./2:.0..92.. 55921, 2022.
Georgios Piliouras, Ryann Sim, and Stratis Skoulakis. Optimal no-regret learning in general games: Bounded regret with unbounded step-sizes via clairvoyant MWU. CoRR, abs/2111.147331 2021.
Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In COLT 2013 The 26th Annual Conference on Learning Theory, 2013, volume 30 of JMLR Workshop and Conference Proceedings, pages 993-1019, JMLR.org, 2013a.
Alexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable se- quences. In Christopher C. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 26: 27th Annual Conference Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, pages 3066-3074, 2013b.
15

---

Published as a conference paper at ICLR 2023
1. Romanovskii. Reduction of a game with complete memory to matrix game. Soviet Mathematics, 3, 1962.
J. B. Rosen. Existence and uniqueness of equilibrium points for concave n-person games. Economet- rica, 33(3):520-534 1965.
Tim Roughgarden. Intrinsic robustness of the price of anarchy. J. ACM, 62(5):32:1332444 2015.
Tim Roughgarden, Vasilis Syrgkanis, and Eva Tardos. The price of anarchy in auctions. J. Artif. Intell. Res., 59:59-101, 2017.
L. S. Shapley. Stochastic games. Proceedings of the National Academy of Sciences, (9()):1095- 1100, 1953.
Arun Sai Suggala and Praneeth Netrapalli. Follow the perturbed leader: Optimism and fast parallel algorithms for smooth minimax games. Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020.
Vasilis Syrgkamis and Eva Tardos. Composable and efficient mechanisms. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors. Symposium on Theory of Computing Conference, STOC'13, 2013, pages 211-220. ACM, 2013.
Vasilis Syrgkanis, Alckh Agarwal, Haipeng Luo, and Robert Schapire. Fast convergence of regularized learning in games. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lec, Masashi Sugiyama, and Roman Garnett, editors, Advances Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, pages 2989-29999 2015.
Oskari Tammelin. Solving large imperfect information games using CFR+. CoRR, abs/1407.500 2014.
Sebastian Thrun and Lorien Pratt. Learning to learn. Springer Science & Business Media, 1998.
Eric van Damme. Stability and Perfection of Nash Equilibria. Beringe--Verla,, Berlin, Heidelberg, 1987.
Adrian Vetta. Nash equilibria in competitive socicties, with applications to facility location, traffic routing and auctions. 43rd Symposium on Foundations of Computer Science (FOCS 2002), page 416. IEEE Computer Society, 2002.
Kun Wang, Jacob D. Abernethy, and Kfrr Y. Levy. No-regret dynamies in the fenchel game: unified framework for algorithmic convex optimization. CoRR, abs/2111.11300 2021.
Chen-Yo Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Conference Learning Theory, COLT 2018, volume 75 of Proceedings of Machine Learning Research, pages 1263-1291. PMLR, 2018.
Chen-Yo Yu Wei, Chung-War Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate conver- gence constrained saddle-point optimization. In 9th International Conference on Learning Representations, ICLR 2021. OpenReview.net, 2021.
Andre Wibisono, Molei Tao, and Georgios Piliouras. Alternating mirror descent for constrained min-max games. CoRR, 0bs/2200.04166) 2022.
Tianbao Yang. Lijun Zhang, Rong Jin, and Jinfeng Yi. Tracking slowly moving clairvoyant: Optimal dynamic regret of online learning with true and noisy gradient. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 457. JMLR.org, 2016.
Hugh Zhang, Adam Lerer, and Noam Brown. Equilibrium finding in normal-form games via greedy regret minimization. In Thitt AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty- Fourth Conference on Innovative Applications of Artificial Intelligence, 2022, pages 9484-9492.
AAAI Press, 2022a.
16

---

Published as a conference paper at ICLR 2023
Mengxiao Zhang, Peng Zhao, Haipeng Luo, and Zhi-Hur Zhou. No-regret learning in time-varying zero-sum games. In International Conference on Machine Learning. ICML 2022, volume 162 of Proceedings of Machine Learning Research, pages 16772-26808 PMLR, 2022b.
Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Dynamic regret of convex and smooth functions. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020.
17


Reviews:
[{"review_id": "YNRMDj_P2J", "reviewer": "Reviewer_K7Pm", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces meta-learning for equilibrium finding and learning to play games including two-player zero-sum games, general-sum\ngames, and Stackelberg games. The authors define somewhat natural notions of similarity between the sequence of games encountered. The work evaluates\nthe meta-learning algorithms on endgames faced by the poker agent Libratus. The experiments show that related games can be solved significantly faster using the meta-learning techniques than by solving them separately.", "summary_of_the_review": "Solid paper, main paper can be written more clearly.", "strength_and_weaknesses": "\n\nI think this is very good paper. I really have nothing to complain about about the results, the results also are a big enough advance.\nThe only issue I have is with the writing - I understand that this is a difficult paper to write, in fact I feel this paper is better suited for a journal than a venue which is so much page constrained. I found the informal theorem statements quite very informal, and the formal statement corresponding  to the theorem in the appendix requires tracking a few other theorems in the appendix. I think the appendix is more interesting than the main paper.\n\nExamples of too informal: \nIn Thm 3.1 it is stated \"meta-learning algorithm for the initialization\" - which algorithm? - later in the text below it is stated as Alg 1 but it is confusing to state something without introducing it first.\nThm 3.2 does not mention anything about meta-learner (or even the init strategy in the text before the Thm)\nIn definition of smooth games, OPT is not specified", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "PCYkuZuAjg", "reviewer": "Reviewer_fvHn", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes and investigates the problem of meta-learning in games. In particular, it builds the framework that uses meta-learning techniques to learn Nash equilibrium sequentially for a set of games by exploiting similarities between these games. Theoretical guarantees under this framework are derived for many classes of games and problems including two-player zero-sum games, potential games, optimal social welfare problems and stackelberg games. It also provides experiments on two Libratus endgames and shows supreme performance of the proposed meta-learning algorithms.", "summary_of_the_review": "This paper proposes a novel framework to study meta-learning in games and provides extensive results in many classes of problems. However, some assumptions need to be justified and it looks inherently difficult to put everything it covers into the limited number of pages in a clear way.", "strength_and_weaknesses": "### Strengths\nThe results provided in this paper is very extensive, showing that the proposed framework can be readily applied to many classes of meta-learning problems related to games. Meanwhile, these results also provide connections to many different directions, opening an area of future research.\n\n### Weaknesses\n\n- One major weakness of this paper in my concern is in its organization. Since the coverage is too extensive, the current main content is more like a list of results. That is, it looks very difficult to get the core idea of the proposed algorithm by solely reading the main content. If my understanding is correct, most of the theoretical results are derived based on Theorem B.3. Therefore, it's probably better to put more discussion about Theorem B.3 and less discussion about specific problems into the main content. Otherwise, considering **submitting this paper to a journal** can also be an alternative choice.\n- Another major weakness of this paper in my concern is in its assumptions. In particular, in this paper, the algorithm requires exact Nash equilibrium about previous games, while previous meta-learning algorithms usually don't require so much information about previous tasks (like the \"Online Meta-learning\"). Is there any unique properties in games making this amount of information necessary? Meanwhile, why this is a well-motivated assumptions in some applications, which seems not to be discussed in appendix?\n- Meanwhile, from my perspective, the setup in this paper is more close to \"online meta-learning\" instead of \"meta-learning\", so it's probably more appropriate to call it \"Online Meta-learning in Games\".", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "AIDCUigAqV", "reviewer": "Reviewer_xPwr", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper applies the well-known idea of meta learning to learning in games, across various game types and settings including zero-sum games, potential games, general-sum games and Stackelberg games. The authors show several theoretical results for convergence to relevant performance metrics in these games, depending on natural notions of similarity between games encountered by the learner. In general, meta-learning serves to improve the performance of standard algorithms, recovering the known guarantees in static games. The authors also experiment with meta learning poker (zero-sum) endgames, with meta learning used to determine appropriate initializations for the learners. The experiments show that the technique greatly improves performance compared to vanilla methods.\n", "summary_of_the_review": "In summary, this paper introduces a framework for meta learning in games which seems to be a useful and interesting idea to me. Many theoretical results in different game settings are described, all of which improve upon vanilla bounds and some new techniques are even shown in the supplementary material. The paper is well written enough to not feel bloated, but there is a lack of empirical evidence for the meta learning techniques in games beyond zero-sum. Overall I would recommend the paper for acceptance.\n", "strength_and_weaknesses": "Strengths:\n- This paper is very thorough in its exposition of related work and in extending the results in each of the settings studied. It is very ambitious to analyze so many different game types and settings, but I feel that the authors managed to do so in a way which still feels digestible and natural.\n-  As far as I can tell, despite the breadth of the paper's analyses, the theoretical results are presented clearly and the proofs (while typically derivative of the standard techniques in the field) contain some non-trivial ideas which would certainly be of independent interest in static game settings. A primary example of this is the analysis of the extragradient algorithm using a regret-proxy, allowing for an RVU-type bound to be written even though extragradient is not a no-regret algorithm.\n\nWeaknesses:\n- A somewhat minor weakness of the paper is that a lot of the results seem unsurprising, in the sense that by selecting natural similarity metrics and having agents learn initializations based on a 'stacking'-type setup with no-regret algorithms, one would certainly expect the performance to improve over time. It is of course still useful and interesting to formally analyze the performance improvements, but I would have liked to see more focus on the empirical results.\n- The experimental results in the paper are quite restricted, in the sense that despite a broad range of theoretical results, the authors only show experimental improvements for zero-sum games. It would have been interesting to see a visual representation of the improvements in potential, general-sum and even stackelberg games using meta-learning. \n- Finally, the choice of similarity metric in each setting, while usually appropriately motivated, leaves some room open for debate. In particular it would have been interesting to empirically compare different similarity metrics in settings where multiple metrics can be devised. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "2wWA_zgaC5", "reviewer": "Reviewer_RKWM", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies a framework on meta-learning in multi-agent games and considered a range of popular game structures, including zero-sum games, potential games, general-sum multi-player games, and Stackelberg security games. The general game is composed by  a sequence of multiple sub-games, where each sub-games have a number of iterations.\n\nThe authors analyzed theoretically the rates of convergence to different game equilibria which is dependent on the similarity between the sequence of sub-games, when each of the agents is performing some type of gradient descent updates. Experimentally, the game dynamics were demonstrated with two public Poker endgames.", "summary_of_the_review": "Overall the paper studies a new framework for meta-learning in several common game structures. The results cover a nice set of game settings and open up a few problems for future works. I suggest the authors to add further interpretations on the theoretical bounds, and experimental comparison with one of the prior works ([Zhang et al 2022b].\n\n\n\n\n-------- post rebuttal --------\n\nI have read the author's response and remain the original score.\n\n\n", "strength_and_weaknesses": "Strength:\n- I found the meta-learning in game perspective interesting, and the analysis and results in the paper directly lead to several problems for future works, such as more general game structures where the single-game results are known but the meta-game analysis remains open.\n- The authors were able to consider a set of common game structures and provide a comprehensive set of results. The experiments on the Poker endgames also nicely complement the theoretical analysis.\n- Overall the paper is well-written and the structure was very clear to follow. \n\nWeakness:\n- in the theoretical guarantees the task similarity notion significantly affects the convergence rate. It would be good to see more interpretation on the \"task similarity\" notion. What are some examples of sequences of games that exhibit a high/low task similarity?\n- In the experiments, how does the proposed algorithm compare with the one in [Zhang et al 2022b]? Given that their solution is for a more general setup that applies in the paper's setting, it would be good to see such comparisons.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster