Prediction-Aware Learning in Multi-Agent Systems
Authors: Aymeric Capitaine
Etienne Boursier
Eric Moulines
Michael I. Jordan
Alain Oliviero Durmus
Venue: ICML 2025 poster (2025)
Keywords: Learning in Games
Multi-agent systems
Online Learning
Equilibrium
Social Welfare
Time-varying games
Primary area: theory->online_learning_and_bandits

Abstract: The framework of uncoupled online learning in multiplayer games has made significant progress in recent years. In particular, the development of  time-varying games has considerably expanded its modeling capabilities. However, current regret bounds quickly become vacuous when the game undergoes significant variations over time, even when these variations are easy to predict. Intuitively, the ability of players to forecast future payoffs should lead to tighter guarantees, yet existing approaches fail to incorporate this aspect. This work aims to fill this gap by introducing a novel prediction-aware framework for time-varying games, where agents can forecast future payoffs and adapt their strategies accordingly. In this framework, payoffs depend on an underlying state of nature that agents predict in an online manner. To leverage these predictions, we propose the POMWU algorithm, a contextual extension of the optimistic Multiplicative Weight Update algorithm, for which we establish theoretical guarantees on social welfare and convergence to equilibrium. Our results demonstrate that, under bounded prediction errors, the proposed framework achieves performance comparable to the static setting. Finally, we empirically demonstrate the effectiveness of POMWU in a traffic routing experiment.

Prediction-aware
Learning in Multi-agent Systems
Aymeric Capitaine'
Etienne 3oursier?
Eric Moulines
Michael I. Jordan" Alain Durmus'
Abstract
dynamic game. Since the seminal works of Foster and Vohra (1997); Freund and Schapire (1999); Hart and (2000a), progress has been made towards obtaining fast con- vergence rates for different equilibrium concepts, including coarse correlated equilibrium (Syrgkanis et al., 2015; Foster et al., 2016; Daskalakis et al., 202 I; Piliouras et al., 2022; Farina et al., 2022) correlated equilibrium (Chen and Peng, 2020; Anagnostides al., 2022a;b; Peng and Rubinstein, 2023) and Nash equilibrium (Anagnostides et al., 2022c). However, most of these works assume that the game remains constant over time.
The framework of uncoupled online learning in multiplayer games has made significant progress in recent years. In particular, the development of time-varying games has considerably expanded its modeling capabilities. However, current re- gret bounds quickly become vacuous when the game undergoes significant variations over time, even when these variations are easy to predict. Intuitively, the ability of players to forecast fu- ture payoffs should lead to tighter guarantees, yet existing approaches fail to incorporate this aspect. This work aims to this gap by intro- ducing novel inadicctio-aaaae framework for time-varying games, where agents can forecast future payoffs and adapt their strategies accord- ingly. In this framework, payoffs depend on an underlying state of nature that agents predict in an online manner. To leverage these predictions, we propose the POMWU algorithm, a contextual ex- tension of the optimistic Multiplicative Weight Update algorithm, for which we establish theo- retical guarantees social welfare and conver- gence to equilibrium. Our results demonstrate that, under bounded prediction errors, the pro- posed framework achieves performance compara- ble to the static setting. Finally, we empirically demonstrate the effectiveness of POMWU in a traffic routing experiment.
Only recent studies have begun to consider time-varying games, in both two-player zero-sum games (Zhang et al., 2022) and multiplayer general-sum games (Duvocelle et al., 2018; Anagnostides al., 2024). Following methods ini- tially developed by the online optimization community (Chi- ang et al., 2012; Rakhlin and Sridharan, 2013), these studies bound the dynamic regret incurred by players with measures of the iine-variaiion of the underlying game. While this approach looks satisfactory at first glance, it is not hard to come up with simple examples for which the variation important-making the above mentioned bounds vacuous- yet very simple to predict. In Example we exhibit simple instance of time-varying game where the regret bounds de- rived in Zhang et al. (2022) grow linearly with the horizon T > 0. However, the dynamic underlying the payoff matri- ces is entirely deterministic, and knowing it would result in a constant regret. This highlights that the current time-vary varying framework fails account for any predictive capacity of the agents. This all the more surprising predictive models become ubiquitous in numerous economic sectors (Jordan and Mitchell, 2015; Gogas and Papadimitriou, 2021; Hin- ton and Jordan, 2024), making it likely for strategic agents to possess a forecasting ability regarding their future pay- offs. This work aims to fill the gap, by asking the following question:
1. Introduction.
The framework of uncoupled online learning in multiplayer games has sparked lot of interest for its ability realisti- cally model the interactions of rational players engaged in
'Centre de Mathématiques Appliquées - CNRS École polytechnique Palaiseau, 91120, France "Inraa Saclay, Uni- versité Paris Saclay. LMO Orsay. 91400, France "Inria Paris, Ecole Normale Supérieure, PSL Research University Paris, 75, France. Correspondence name.lastnamee woweee@eooooyooocccicu.t
How does the quality of predictions made by ratio- nal agents time-varying games regarding their future payoffs affects social welfare, as well as the convergence to equilibrium?
Aymeric Capitaine <first-
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Contributions.
We address ing contributions.
this question with the follow-

---

Prediction-aware Learning in Multi-agent Systems
First, we introduce the new prediction-aware learning framework, where players forecast future payoffs in online fashion and design their strategies accord- ingly. In a nutshell, we build on the contextual set- ting proposed by Sessa et al. (2021) by introducing an underlying state of nature, either adversarially or stochastically drawn, which determines the payoff of all agents. They play a time-varying game which can be decomposed into three stages. First, each player forecasts the current state of nature based on their local predictor before picking an action in the game. Then, they observe their payoff' and the actual state of nature. Finally, they update their policy and predictor based on these new observations. Augmenting uncoupled learn- ing in games with contexts and predictions requires to introduce new regret and equilibrium concepts. In particular, extend correlated equilibrium (Aumann, 1987) to our framework.
game theory have incorporated the idea of an underlying state of nature jointly determining the payoffs of players.
While Sessa et al. (2021); Maddux and Kamgarpour (2024) studies the contextual version of uncoupled learning in mul- tiplayer games, Lauffer et al. (2023); Harris et al. (2024) focuses on Stackelberg games with side information. How- ever, these works assume that the context revealed to players at the beginning of each period, unlike ours where players have predict the context before moving. In the end, the social learning framework might be the one that relates the most to ours. Pioneered by the work of Banerjee (1992); Bikhchandani et al. (1992); Smith and Sørensen (2000), it features agents receiving private signals about a true, unobserved state of nature. These agents are able to learn from both their signal and the actions played by other players, which reflect their signals Chamley (2004). Most of the social learning literature has been devoted to ana- lyzing the resulting collective behaviors, such as cascading and herding phenomena (Mossel et al., 2020), While re- cent studies have broadened the analytical toolbox of social learning by considering for instance time-varying states of nature (Frongillo et al., 201 Boursier et al., 2022; Levy et al., 2024), it mostly relies on very strong assumptions (e.g, a binary state and binary actions, Mossel et al., 2020) and a Bayesian modeling where all agents share a common prior about the state of nature's 's distribution. In contrast, we believe that the uncoupled learning framework (Hart and Mas-Colell, 2000b; 2003; Daskalakis et al., 2011) upon which our work relies is a more general setting for studying this question, and allows study more natural equilibrium concepts such correlated equilibria (Aumann, 1987) with stronger guarantees.
Second, we propose an algorithm called POMWU- which a contextual extension of the optimistic Mul- tiplicative Weight Update algorithm (Daskalakis et al., (021>aallowngg players to leverage their prediction about the state of nature. In particular, we show that if all players use POMWU, we match the results of Syrgka- nis et al. (2015) established for static games, regarding social welfare (Corollary 3), equilibrium convergence (Corollary 2) and robustness in the adversarial setting (Proposition 8) up to a factor that depends polynomially on the number of prediction errors by players. Thus, when predictions errors are bounded by a constant (which is the case under realizability, see Daniely et al., 2014), our bounds match the guarantees on social wel- fare and equilibrium convergence for static games. Our analysis builds upon a new notion of contextual Regret bounded by Variation Utility (RVU) which bounds con- textual regret by the sum of the length of the context- specific sequences of feedbacks and strategies. Indeed, naive application of the standard RVU framework results in looser bounds.
Organization. This work is organized as follows. In Sec- tion 2, we present our model, notion of regret and main assumptions. In Section 3, we introduce the POMWU algo- rithm and establish the convergence of social welfare and individual utilities. In Section 4, we empirically demon- strate the performance of POMWU on the Sioux Falls routing problem (LeBlanc et al., 1975).
Additional related works. The problem tackled in this work relates with several lines of research in game theory and online optimization. On the one hand, the contextual optimization literature (Donti et al., 2019; Elmachtoub and Grigas, 2020; Bennouna et al., 2024) has considered the problem of minimizing an objective function defined by an unobserved random context, which the optimizer can predict via a regression function. This idea has also been studied in the contextual bandit framework (Lattimore and Szepesvári, 2020) with noisy contexts (Kirschner and Krause, 2019; Yang and Ren, 2021; Nelson et al., 2022; Guo et al., 2024). However, none of these works consider the multi-agent set- ting, where the optimizer interacts with other agents during the learning process. On the other hand, recent studies in
Example 1. Consider the two-players setting in (Zhang el al., 2022) where X E BD and y E IRm are respectively the strategy spaces of player x and y. A. E [[1,1]uxm is their time-varying payoff matrix and & C X x is the set of Nash equilibria at time E [T]. The two measures of variations considered in (Zhang et al. 2022, and up to minor modifications Anagnostides et al. 2024) are
Pr = min
Σ
E(1=1 2; 1111 + lut vi-1))),
Exx... ET KE(TT
and
VT Σ
11 - 1
2

---

Prediction-aware Learning in Multi-agent Systems
which are respectively the variation of Nash equilibria and the variation of payoff matrices. Zhang et al. (2022, Theo- rem 6) show that the dynamic regret can be bounded by
[J]. This cost function is flexible and is customary in contextual optimization (Sadana al., 2024) and contextual bandit (Li et al., 2010; Lattimore and Szepesvári, 2020). (2), Φi represents standard payoff function, while Z E Z can be interpreted as a state of nature that linearly influences preferences. Note that a time-varying game can easily be constructed by considering a sequence of states of nature (ZI....,Zy E z for T 0. We rewrite (2) in a more compact way with the following lemma.
Óminn PT)
+ VT) + PT, + WT)),
(1)
where WT = =
A A. A EETT Ar = (.VT)
On the other hand, if we consider for any I. E (T], Ar = B + (-1) where
B B-
-)
Lemma 1. Let j E [J], w E (A) with w w @ w and D (w-J) 5) (Ew [ (0 (a a Meelee E Baxk K We have:
it is not hard to check that
e d(w, Z) ( $5 (w ww))
& E { ((1,0), (1
is is even
{ ((:11).(2:))) })} otherwise
In Lemma 1, (w- is a matrix whose column contains the cost of playing the pure action af when opponents play their mixed-strategy w-1. This quantity appears naturally in online learning for games (Syrgkanis et al., 2015). Note that by Lemma 1, / (w entirely determines c², so having access to this matrix is equivalent to having access to e². Moreover, Lemma 1 stresses that el is conveniently linear in w E A for any j E [J].
This implies that Pr- = 2T. Likewise, one can verify that Vr T, so the bound in (1) grows linearly with T. At the same time, we remark that Y; = -Y with Y, = A This shows that (A))aE(T) is a determin- istic process (more precisely, a deterministic ARIMA(1,1,0) process (Hamilton, 2020]).
We introduce the two following assumptions for the rest of the analysis.
2. Model.
HI. For any j E [J] a E and 2 E Z, (z, < 1.
Notation. In what follows, denote the L-th coordi- nate of any vector E Rd by x[{] E IR. Likewise, the 6-th row of any matrix X E Rdxk is denoted by XI[] E RKK For any vectors (I, v) E Rd x IR,, we write (x, y) = x'y the standard euclidian inner product and x.y = (a[1] v(t],]]],,..... ==(d] y(d)) the Hadamard product. (A) denotes the set of probability measures over mea- surable space A, and A fw RK : VV E [K], w [$] >> and ΣK w w([[] = 1} the simplex of dimension K > 0. When A 1 x... A is the product of J spaces, write A- = A² x .... x A x A++1 A' for (AA,
This boundedness assumption is usual in learning in games and more generally in online learning (Hazan et al., 2014). In particular, HI ensures that for any j E [J] w E (A) and Z E Z, e (w, Z) & 1. H2. The set is finite = (.1,..., Zm for m > O.
Assuming a finite context set is customary in bandit theory (Lattimore and Szepesvári, 2020; Slivkins et al., 2019) and game theory (Kamenica and Gentzkow, 201 Kamenica, 2019), and is often relevant in practical settings. We believe that the analysis to infinite context set is possible, but such an extension falls outside the scope of the current pa- per, as it would require introducing fundamentally different concepts and proof techniques, see Appendix B for further discussion.
any j [J]. so A = A x A-i, For any we write [a] = I dw(()) the associated expecta- tion. When the context is clear, we rather write Fw in- stead of Ea-w- When w = w- 8... @ w is a prod- uet of > O measures, we define for any j E [J] w = w 8 ... wi & wi+1 @ .... & wd and Ew- the associated expectation operator.
We assume that agents play time-varying game, which is determined by sequence of states of nature (Zi...., Zr) E 2t of length T > 0. At the beginning of each period t E [T], nature draws state of nature Z, E Z, which is not revealed to agents, while each player j E [J] receives a signal 2 E Z about this state. They then select a strategy w E AK based on this signal. Finally, each agent j get as a feedback the cost matrix T (w( ") as well as the actual state of nature Z..
Setting. We consider set of J > 0 agents denoted by [J]. We suppose that each agent has access to action set A = (af...., } with |4'| = K. In addition, we assume that the cost function of agent j E [J] is given for
Z E 2 C Rdd and di A + Rd by:
d' ((w, Z)= Ea-w (0" (a), z)]
(2)
where WE E (A). Typically, we will consider w = w' @ ... @ w.d where w E Ax is a mixed strategy played by
Remark 1. In many practical settings, the private signals 2 E 2 for j E [J] and E (T) are predictions made by
3

---

Prediction-aware Learning in Multi-agent Systems
supervised learning algorithms. In this case, at the begin- ning of each round E (T), each agent j [J] observes covariates X3 E X and makes prediction
for any = E 2 and w P(A"). The comparator कं maps each context 2 the best action in hindsight on the time steps when was observed. Denoting w/ = ./ (2)) the strategy of agent j for any t E [T], we then define the following contextual external regret:
= ox
where gf E CCCCE {g X + 2} is some prediction al- gorithm based on the history of observations up to time L. Under H2, this situation corresponds multiclass online learning, for which several theoretical results are avail- able in the litterature (Daniely et al., 2014: Daniely and Shalev-Shwart,, 2014).
[(d(w, , d wT, [0] EE(T)
(4)
Note that Ry is not fully static as the comparator is allowed to vary from a context another. In this sense, (4) can be viewed an intermediary between external regret and dynamic regret (Hall and Willett, 2013; Besbes et al., 2015). The existing literature on time-varying games typically fo- cuses on dynamic regret (Duvocelle et al., 2018; Zhang et al., 2022; Anagnostides et al., 2024), which is the most stringent notion of regret. However, the resulting bounds often include a path length term. This term captures the intrinsic variation of the comparator sequence, such as Pr and Vr in Example 1. In contrast, we will show that bounds on regret (4) depend only on a prediction error term, which vanishes if agents are able to accurately predict the states of nature.
To formally describe the game, we define TP as the set of policies n² (UEer))H)) x 2 + A for player j E [J], where H., is the set of histories at time t E [T] with elements
he = { (w hergg. At the beginning of the game, hgg = 0. Then for any E [T],
1. Each agent j E [J] observes a private signal 2/ E Z, and picks a mixed strategy wi E AR where /i is the output of policy कं T (h) (k/_1) :): 2 Ax. that is wy = T/ (22).
2. Each agent) incurs cost (Z,, D (w; " and gets as a feedback (Z, Φ ('w,," (w,")). They then update he = h U (wi") Zz}.
While external regret has been cornerstone measure of performance in online learning for games, swap regret has recently aroused lot of interest since it sets more de- manding learning benchmark and leads to tighter equilib- rium concepts ( (Anagnostides et al., 2022b; Peng and Rubin- stein, 2024; Dagan et al., 2024). We therefore supplement our analysis of regret Equation (4) by a similar study of contextual swap regret, which we introduce below. Let A = {> : AK + AAx] be the set of swap deviation maps, and define for any j [J]. AK Z - AR the optimal swap comparator, which satisfies for any z E Z and any
Remark 1 (continuing from p.)). In the case where private signals are predictions from an online algorithum, agents train policies v²: : X > AK mapping covariates to strate- gies. Indeed, for any j E [J] and t E [T]]
w/ = ने. (2.) (m] o (g))(()))) (xxx))
We consider the standard full tull-information feedback setting, where each player j E [J] observes Φ5 ('(w)). We believe that extending our results to bandit feedback - i.c., when agents only observe the reward from their realized action- (Foster et al., 2016) feasible. though it would require additional technical refinements.
X E A:
Σ (()(w())), t
& Σ Ed (X(wE), we wr² te
Regrets. We now present the two regret concepts used in this paper to quantify the optimality of a policy x³ E IP., They are essentially contextual versions of the classic external (Zinkevich, 2003) and swap (Blum and Mansour, 2007) regrets. In what follows, f== = {t E [T] : Z, = z} denotes the timesteps at which E Z.
Given a context 2, the swap comparator X maps any played strategy w/ to an alternative strategy that would have achieved better performance on the time steps when z was observed. Importantly, competing against X is strictly more demanding than competing against n.. from (3). While T assigns fixed optimal action to each context z, inde- pendent of the strategies actually played, XLw,, 2) adapts to the specific strategy used. This flexibility allows X to identify better-performing alternatives conditioned on past decisions, making it a stronger-and thus more challeng- ing benchmark.
First, following Sessa et al. (2021), we introduce a con- textual external regret. For any j [J], given fixed sequence of opponent strategies (w, " )><)()) we denote by no. 2 + AK the static comparator which satisfies
Σ c(F((z), WT ' 2,2,) < Σ 1
cww, w, ,,Z)) (3)
With ni = n/. (2{) being the strategy played by agent j at
4

---

Prediction-aware Learning in Multi-agent Systems
time I, we define the following contextual swap regret:
coarse deviations. On the other hand, correlated equilibrium (Aumann, 1987) is tighter equilibrium concept which pre- vents swap deviations, see Appendix C for more discussion. We introduce below an equivalent concept adapted to our framework. In the following definition, e' : x 2 - A is any swap deviation function, which given an action and context (a² ;=) returns an alternative action ă².
R4
Σ [E
(w?, w -z) -2 (X Z.), wT, 2:)
(5)
Finally, in the non-contextual case, the Blum- re- duction (Blum and Mansour, 2007) is convenient proce- dure which allows to design no-swap regret algorithm from any no-external regret one. A natural question is whether a similar reduction exists in our setting, that is, whether an algorithm minimizing (5) can be obtained from an algo- rithm minimizing (4). We answer by the positive with the following proposition.
O. An E-contextual correlated equilibrium is joint policy V 2 + P(A) such that for any j E [J] and g² A x Z - A::
Definition 2. Let
Σ E BawD (10) (a), Zi)]
NETT]
< T
Ea- (( (d'(a), (,)(a",2)) a)), t 6E|2
Proposition 1. Assume that player j. E [J] plays an al- gorithm T E IP achieving Ri & [[J,T, K,m,) for some N: - R.+ Then, one can design algorithu री E 113 achieving
Definition 2 extends the classic correlated equilibrium no- tion (Aumann, 1987) to the contextual case, by letting the swap functions g (+, depend on the state of nature.
RS & (J(J,T,K,
The explicit procedure to design म from x² is described in Algorithm 2, and the proof of Proposition 1 is deferred to Appendix G. A direct consequence of Proposition is that any algorithm with a guarantee on external regret (4) can be converted into another algorithm with a guarantee on swap regret (5), at the cost of an additional K factor. This will be particularly useful to extend the analysis from external to swap regret. Note that more recent procedures (Dagan et al., 2024; Peng and Rubinstein, 2023) allow to deal with larger action spaces by reducing the dependence of K, yet at the cost of a degraded dependence on T.
In the non-contextual case, there exists a well-known and powerful connection between external regret minimization and coarse-correlated equilibrium. If all players use no- external regret algorithms, their empirical average strategy is an approximate coarse correlated equilibrium. Crucially, we show that the same property holds in our contextual framework. In the following proposition, notes the number of time state 2 E Z occurs.
= | de-
Proposition 2. Assume that for any j E [J], agent j uses policy n³ IP incurring an external regret Ry in (4), and denote by w! = nł (2)) for any t [T.. Let DT : Z + (AA be such that for any Z,
Equilibrium. We consider two equilibrium concepts, which naturally relates to the two regrets previously defined. First, we focus on the classic contextual coarse-correlated equilibrium (Sessa et al., 2021; Maddux and Kamgarpour, 2024), whose definition is recalled below.
ir(()) = n3 Eie w/ 8 ....C. 8 w/ if >0 (K-1,.... K-I)
otherwise
Then, Dr is an e-contextual course correlated equilibrium with
Definition 1. [Sessa al. 2021] Let 0. An E-contextual coarse-correlated equilibrium is joint policy v : Z (AA) such that for any j E [J] and T E IT::
E max T JE(J]
The proof of Proposition 2 is deferred to Appendix G. It is clear from this proposition that if RM o(T) for every j E [J]. iy asymptotically convergences to an exact coarse- correlated equilibrium.
Σ c (V))
(7x), -ー (7t); (1)),7)) 7x)
TE[T]
TT (TT 2.) + AE(T]
Moreover, the same connection exists for swap regret and correlated equilibrium in the non-contextual setting. We also retrieve this property in our contextual setting, as showed by the following proposition.
Note that Definition 1 extends the classic coarse correlated equilibrium concept (Foster and Vohra, 1998) to the case where the underlying state of nature changes over time. A more detailed interpretation of Definition is provided in Appendix C.
Proposition 3. Assume that for any j E [J], agent j uses a policy म5 E IT incurring a swap regret Ry defined as in (5). Let Dr Z + (A) be defined as in Definition 1. Then, Dr is an e-contextual correlated equilibrium with
While coarse-correlate equilibrium has been extensively studied, it is arguably weak in the sense that only prevents
6 = max T P-I ]E(J]
5

---

Prediction-aware Learning in Multi-agent Systems
The proof of this result can be found in Appendix G. It shows that if all players use algorithms incurring sub-linear swap regret, their empirical average strategy converges to an exact correlated equilibrium. Both Proposition 2 and Proposition 3 are key to our analysis, since they convert individual regret guarantees into convergence rates to equi- librium. Hence, bounding individual regrets is our first objective.
cost is guaranteed converge fraction of the optimal one. Therefore, bounding Σje(n Ry will be our second objective.
3. Prediction-aware learning.
Algorithm. In the non-contextual case, the optimistic Mul- tiplicative Weight Update (OMWU) algorithm has proven par- ticularly effective for controlling individual and social re- grets in uncoupled multiplayer games. We propose below the Predictive-OMWU algorithm, abbreviated POMWU, which is an extension of OMWU to our framework. Broadly speaking, POMWU maintains one OMWU instance per context. At the beginning of each round, agents predict the context and use the corresponding OMWU to play. Once the actual state of nature has been revealed, they update the algorithm based the cost feedback for future rounds. The pseudo-code of POMWU is displayed in Algorithm 1.
Social welfare. On top of convergence to equilibrium, we study social welfare, and in particular whether no-regret strategies may result in welfare close to the optimal one. In non-contextual games, the so-called Roughgarden smooth- ness condition (Roughgarden, 2015) is particularly conve- nient to address this question (Syrgkanis et al., 2015). This condition- which is satisfied by a wide class of games, in- cluding congestion games (Roughgarden and Tardos, 2002; Christodoulou and Koutsoupias, 2005), facility games and second price auctions (Roughgarden, 2015)-states that even when players deviate from the optimal strategy, the total cost in a game doesn't 't increase too much. Under this condition, it can be shown that the average social cost con- verges to the optimal one times the price of anarchy.
Algorithm Optimistic MWU with predicted contexts (POMWU) for agent j E [J].
1: Initialize P=1 = = Pam = (K 1K-,,..., K k-) and
Vx, _... = V/ 2m = 0ax K.
Here, we assume that our game satisfies the contextual coun-
for each E [T] do
terpart to the Roughgarden smoothness condition.
3: Predict 24 E 2, set Mt- V z4 and ge = P27
H3. There exist ó >>0 0 and μ > 0 such that for any E A.
Play w E AK where for each E {l...., K}.
a, E AAana and E 2,
of e10expp-MMM (1]
Σ (2, (4 (22, 1)) &
18(2, (a.)) + ~12,,,(a))) (a)))
f [1] =
Exe[K] si [k] exp( () Mi (M]2))
JE(J]
JE(J]
5: Observe Z, E .2d and Φ (w,
is well known that under H3, 7 8(1 - p1 is an upper bound on the price of anarchy (Roughgarden, 2015). In what follows,
6: Update Vi,, + Φ (wi"))
Update pz, + pz. eexp(11190 (opD>(w, (w, (w.')1Z2)
8:
end for
C((w))= = Σ el (w., Zr)
JE(J]
denotes the social cost at time E [T' and
RVU analysis. The Regret bounded by Variation in Util- ity (RVU) bound (Syrgkanis et al., 2015) is effective method for deriving guarantees regarding individual regrets in multiplayer games. Intuitively, this approach ties play- ers' utilities to the variation in observed utilities and played strategies. The RVU ensures that players' regrets remain low when they efficiently adapt their strategy to counter the variation in payoffs. In the following key lemma, we estab- lish a contextual RVU bound adapted to our framework. In what follows, we write T= = (li..... { for any Z, and L Enerr 1121 * Zz} the total number of mis- predictions made by agent j E [J] throughout of the game.
C* min P-Z-A
T-1 Σ
Σ é (p(Z.) Z,), JEMT
the optimal average social cost in pure strategy. The follow- ing proposition shows that under HB, the distance between the average social cost and the optimal one is bounded by the sum of external contextual regrets.
Proposition 4. Assume H3. Then with 7 = 5(1 - 11
Σ C,(w.)) & g + (1- EE[T]
Σ My
T
JE(J
The proof of Proposition can be found in Appendix G. In particular, when Σ Rt. = oTT), the average social
Proposition 5. Assume HI and H2 Any j E [J] applying Algorithm with learning rate 1j > 0 has an external regret
6

---

Prediction-aware Learning in Multi-agent Systems
bounded as follows:
1j 0, then for any j E [J]:
(5+ 3++n(K))Lr + m In()
(5+ 3+In(K)) + m In(K)
Rz <
+ +n[(J - 19T + 4LT) + 4Lr]
+ 17
Σ Σ
(>((w(z))
T (W
+ 414/
In particular if T LT)) setting ""
#EZ i
@(J-1/2T-1/ 1/4 (lnn/|lnnKLLL m)) leads to:
Σ BEZ 15
Ry (0 ([((l())((rr))) + //1
16n
In the realizable case of Remark 1 where Lr- Or we recover the result Rt. ((T4/1 from Syrgkanis et al. (2015). We also observe that setting the learning rate to 17* requires agents know Σzy This is reasonable if they use the same hypothesis class, since uniform bounds on Ly are known (see e.g., Remark 1).
Contrary the classic RVU approach (Syrgkanis et al., 2015), the bound in Proposition 5 depends on the lengths of the context-specifer paths 4 (w.r").... / (wa= and w/y w.:....., w/, The need for this new contextual RVU stems from the fact that players may mispredict states of nature at different periods, preventing the naive of classic RVU, Appendix G for more details. Note that in its current form, Proposition 5 holds for any arbitrary sequence of strategies by other agents, and does not provide an explicit bound for individual regrets.
Remark 1 (continuing from p) Recently, collaborative and federated learning has emerged as topic of prime importance in Machine learning (Blum et al,, 2017; Kairouz et al., 2021). One may wonder whether agents sharing a common model, so 2 = 2z E Z for any j E [J], may im- prove Proposition 6. Indeed, even though agents play uncou- pled strategies, policies zं =2{2) are implicitly coordinated as they rely on a same signal. We show in Proposition 9 in Appendix G that in this case, we can drop the assumplion T (2(J'Lr)) and still recover the guarantee of Proposi- tion 6 by a direct improvement of the proof. Studying the impacts of collaborative learning games more broadly interesting topic for future research.
Remark (continuing from p. 3). It is possible to quantify T. under H2 when agents use online algorithu for predicting (Ze)ue(r). Indeed, this boils down to multiclass online classification problem, for which bounds on Li have been established by Daniely et al. (2014). Assume that G has a finite Liulestone dimension dim (g) oo (Littlestone, 1 1988). In the realizable case, that is when for every j E [J], there exists 97 E G such that Ze 7x=9% (x{))) for any t E [T]. there exists an online algorithm gt X + such that Dy = Exe(T)
It is now possible to obtain an explicit convergence rate to coarse-correlated equilibrium by combining Proposition 2 with Proposition 6.
+ Z.} satisfies:
Corollary 1. Assume HI, H2 and T ((JLLr). If all agents use Algorithm I with 1f" > 0 as defined in Propo- sition 6, then DT (as defined as in Proposition 2) is an E-coarse correlated equilibrium, with
Li & dim
(6)
In the agnostic case, denoting L
eg E. (X)) + Zi). there exists al- gorithm such that
c = ==0( =O(IT())(TT + 3/
In addition, it is possible to obtain a convergence rate for the more demanding contextual correlated equilibrium concept defined in Definition 2. As a matter of fact, the reduction described in Algorithm 2 allows to transform POMWU, which enjoys the guarantee on Rt presented in Proposition into an algorithm मी with guarantee on Vz Proposition 1. Then, applying Proposition 3 leads to the following corol- lary.
14 & Lif + + V/2 dim (9)T (T(m)).
The algorithms leading to (6) and (7), namely Algorithm and Algorithu 4, are both recalled in Appendix D.
Equipped with Proposition 5, we first fo- cus on convergence to equilibrium. As discussed in Sec- tion 2, this only requires bounding individual regrets. The following proposition, which follows from Proposition 5, establishes this bound.
Equilibrium.
Corollary 2. Assume HI, H2 and = ((J If all agents use Algorithm 1 in conjonction with Algorithm and 11" > 0 as Proposition 6, then Dr is an E-correlated equilibrium, with
Propusition 6. Define Lr = maxje(J) J] Li and assume HI and H2. all agents use Algorithm with a learning rate
È = O [K In In(K)(TTTr 3//
7

---

Prediction-aware Learning in Multi-agent Systems
Social welfare. We now turn our attention to social wel- fare when agents use POMWU. As discussed in Section 2, this requires bounding the sum of regrets. A first, naive approach would be to sum the bound of individual regrets obtained in Proposition 6. However, we show below that another choice of vi leads to a much better guarantee.
each other city. Agents want to minimize their travel time, which is determined by both congestion the network, and external factors such as weather and road condition. Formally, we consider graph (V,E) with J = | 1) agents, each of whom wants to send Ø > 0 units from n E V to my E V. For any j E [J]. we let AA' be the set of K > 0 shortest paths connecting n, to my, that is any a² E A' can be written as a² = (2...., xx) with of njj R my. and (+r))++1) E & for any r E (l..... R - 1}. For any profile of actions a (a (a',.....'' aa) E A and pair of nodes (p, E) E E, we denote by
Proposition 7. Let LT = Ejen Li,, and assume II, H2. If all agents use Algorithm 1 with a learning rate 7 = (4(J - 1)) then
LT J-1
Ri < ()((5 + +n(K))]( + mJ [n(K]] jE(J]
Σ
(a) = Eiery l((,,) E Jd if (p, (p, E otherwise,
=[(JIn(K)LL mJ)).
mmJ)
Note that in the setting of Remark 1 under the realizable assumption, L Or (1) and hence we recover the classic result [J Ry = Or(1) of Syrgkanis et al. (2015) in
the total congestion' faced by j E [J] on (). and Φ5 (a) = (a)))( E IR VIX[V| the corresponding ma- trix. Agents are allowed randomize over routes, so they play w AK.- To each pair (p,e) V x V, we also as- sociate cost coefficient zp.e > 0 related to road condition or weather, and we denote by Z = (=p,t)p. E [ the corresponding matrix. Then for any w E (PA) and Z E RIVIX/VI, the cost for any j E [J] is given by:
the static setting.
The bound in Proposition 7 can immediately be converted into a convergence rate of social cost to a fraction of the optimal one via Proposition 4.
Corollary 3. Assume HI, H2 and H3. If Assume all agents use Algorithm with n = (4(J 1))_ then
c(w, 2) = Ew (2, (a))))
1 T
Σ C((w) < g0 (J]In(() (Lx+ [E[T]
= where (A, : =T(AA = En, Ar. Ba, is the Frobe- nius inner product. el captures the expected travel time of player j E [J] when they pick routes according to we E Ak and other agents according to w-j E (AA under con- text Z E Z. Additional experimental details can be found in Appendix A.
Robustness. Finally, we turn our attention to the adver- sarial regime where not all agents use POMWU. Specifically, we ask whether the regret of POMWU remains low against any arbitrary sequence of cost feedback. This robustness property is common desiderata in the literature (Syrgkanis et al., 2015; Foster et al., 2016).
Supervised learning. In our experiment, there are 0 random contexts denoted Z = {zI, ,.....,,.)..... J. For any E 2, there exists 8 E RR such that
Proposition 8. Assume HI and H2. Ifplayer j E [J] [s]usss.. Al- gorithm I with ((In(())L)) + m))3// (12 +T)--11) then for any sequence ......., WT') (AA
1/2
exp(3;X0)
PPZZ = =|x0) = ((3,,
Σ Ezez exp(83,X7)
H4. - (V([O((()) + + (14)
where X E R is vector of covariates (which can be thought of as meteorogical or traffic forecast) drawn from standard Normal multivariate distribution. At each round E [T], agents observe X E RR' and predict with a logistic regression 2. E Z, that is 2. = argmax (( XP). They then update B Brn, in an online fashion with a stochastic gradient descent. More details can be found in Appendix A.
Here again, in the setting of Remark under realizability, T. = (1) and therefore we recover the guarantee Rt. O(VT).
4. Experiments.
Setting. We illustrate the performances of POMWU on the Sioux Falls routing problem from LeBlanc et al. (1975) with the parameters from Sessa et al. (2019). We consider a network of cities connected by roads. In each city, there one agent willing to send a given quantity of goods to
'In Sessa et al. (2019), the congestion is form Φp (a) EEELy 11 E) E a" >'u)", We only keep the term d in this sum so Φx.. is lincar in a E A, which is necessary to compute expectations given the size of action space |A| = mm 1V(0V1-1)
8

---

Prediction-aware Learning in Multi-agent Systems
Figure I: Average repartition of agents on the network for each context under a 10 -coarse correlated equilibrium.
proditti CHNVU
Bampo ginditio 45102
60-
Sf
40-
20-
2500
1000
7000
18800
17900
15200
19600
20000
2020
1906
7000
10660
13500
19600
17500
20000
1ime
Tinc
Figure Average regret over agents for POMWU and OMWU.
Figure 3: Average prediction error from the online logistic regression.
Figure 4: Proportion of average regret
incurred under mispredicted contexts.
Game There are 7' > 0 rounds. At each E [7]. A pair (X), Zi) is drawn, each agent j E [J] observe X predict 2/. and play w/ E A according to Algorithm They then receive Ze and (Bw, [ (a f. a, a,)))aa [)) as a feedback, which they use to update POMWU and their logistic regression. The parameters used in our experiment are summarized in Appendix A.
5. Conclusion
The recent extension of uncoupled learning to time-varying games marks significant progress, it enables the mod- eling of non-stationary payoff environments. However, ex- isting literature overlooks the fact that they may be able to forecast future variations of the game. this work, we introduce prediction mediction-awaae aware learning, a framework which agents can leverage predictions about future payoffs to in- form their strategies. Specificallly, we propose the POMWU algorithm, inspired by the classic OMWU approach, which incorporates the predicted state of nature into the optimism step. We provide explicit guarantees both individual re- grets and social welfare, and demonstrate the effectiveness of POMWU in a simulated contextual game.
Results. Figure 2 displays the the regret averaged over players² for a naive OMWU algorithm which ignores states of nature, and POMWU. The effectiveness of POMWU in adapting to time-varying payoffs is clear, especially when compared to the classic OMWU, whose contextual regret grows linearly due to its inability to account for states of nature. Inter- estingly, Figure shows that rounds where contexts are mispredicted contributes to large and growing share of regret time for POMWU. This illustrates the convergence of the algorithm each context. The fact that average prediction error of the online logistic regression (Figure 3) decreases at slow rate thus explains most of the regret trend of POMWU in late rounds. Finally, Figure depicts the average proportion of agents occupying each edge of the network in different contexts under the empirical policy á defined in Proposition By Proposition this is a depic- tion of 10 10-3-aamm approximat coarse correlated equilibrium of the game.
We believe that these findings provide a strong foundation for incorporating predictive capabilities into dynamic game- theoretic settings, with significant implications for strategic decision-makinn in economic and industrial applications. There are several avenues for future work to improve and expand upon this framework. First, it would be valuable to weaken the feedback provided to players- instance, by restricting it bandit feedback and analyze the impact theoretical guarantees. Second, extending the model to accommodate an infinite number of contexts presents challenging but important direction. Finally, exploring how collaborative inference influences the game dynamics and designing algorithms that account for this interplay remains an essential question from a game-theoretic perspective.
Shaded correspond to standard computed multiple runs.

---

Prediction-aware Learning in Multi-agent Systems
Impact Statement
mization, 2024. URL wtt.tttss///axiv..oo http:///axxivv..r/bbb.e. 10479.
This paper presents work whose goal is to advance the under- standing of aggett systems. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non- stationary stochastic optimization. Operations research, 63(5):1227-1244, 2015.
Sushil Bikhchandani, David Hirshleifer, and Ivo Welch. theory of fads, fashion, custom, and cultural change as informational cascades. Journal of political Economy. 10065):992-1026, 1992.
Acknowledgment
Funded by the European Union (ERC, Ocean, (01071601) Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Execu- tive Agency. Neither the European Union nor the granting authority can be held responsible for them.
Avrim Blum and Yishay Mansour. From external to inter- nal regret. Journal of Machine Learning Research, 8(6), 2007.
Avrim Blum, Nika Haghtalab, Ariel D Procaccia, and Mingda Qiao. Collaborative pac learning. Advances in Neural Information Processing Systems, 30, 2017.
References
Joannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuo- mas Sandholm. Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 736-749, 2022a.
Etienne Boursier, Vianney Perchet, and Marco Scarsini. Social learning in non-stationary environments. In San- joy Dasgupta and Nika Haghtalab, editors, Proceedings The 33rd International Conference on Algorithmic Learning Theory, volume 167 of Proceedings of Machine Learning Research, pages 128-129. PMLR, 29 Mar-0l Apr 2022. URL https: httpps://proceeedigggss mlr. fress/vv66/bbuussee2222 html.
Ioannis Anagnostides, Gabriele Farina, Christian Kroer, Chung-Wet Lee, Haipeng Luo, and Tuomas Sandholm. Uncoupled learning dynamics with o (log t) swap regret in multiplayer games. Advances in Neural Information Processing Systems, 35:3292-3304 2022b.
Christophe Chamley. Rational herds: Economic models of social learning. Cambridge University Press, 2004.
Chen and Binghui Peng. Hedging in games: Faster convergence of external and swap regrets. Advances in Neural Information Processing Systems, 33:18990- 18999, 2020.
Ioannis Anagnostides, Gabriele Farina, loannis Panageas, and Tuomas Sandholm. Optimistic mirror descent either converges to nash or to strong coarse correlated equilibria in bimatrix games, 2022c. URL hwtph:tt////rttsee org/ abs/2203. 12074.
Chao Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. On- line optimization with gradual variations. Conference on Learning Theory, pages 6-1. JMLR Workshop and Conference Proceedings, 2012.
Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On the convergence no-regret learning dynamics in time-varying games. Advances in Neural Information Processing Systems, 36, 2024.
George Christodoulou and Elias Koutsoupias. The price of anarchy of finite congestion games. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 67-73, 2005.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert Schapire. The nonstochastic multiarmed ban- dit problem. SIAM journal on computing, 32(1):48-77, 2002.
Yuval Dagan, Constantinos Daskalakis, Maxwell Fishel- son, and Noah Golowich. From external to swap re- gret 2.0: An efficient reduction for large action spaces. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1216-1222, 2024.
Robert Aumann. Correlated equilibrium an expression of bayesian rationality. Econometrica: Journal of the Econometric Society, pages 1-18, 1987.
Abhijit V Banerjee. A simple model of herd behavior. The quarterly journal of economics, 107(3):777-817, 1992.
Amit Daniely and Shai Shalev-Shwartz. Optimal learn- ers for multiclass problems. In Conference on Learning Theory, pages 287-316. PMLR, 2014.
Omar Bennouna, Jiawei Zhang, Saurabh Amin, and Asuman Ozdaglar. Addressing misspecification in contextual opti-
10

---

Prediction-aware Learning in Multi-agent Systems
Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz. Multiclass learnability and the principle, 2014. URL https://arxix httpps//aarxtv.oor//bb//////// 2893.
Periklis Gogas and Theophilos Papadimitriou. Ma- chine Learning in Economics and Finance. Computational Economics, 57(1):1-4, January 2021. doi: 10.10077s100144-01--099999 https://idens http://ddaaaeeec.rrrreeeeee sogpec..rg///kap///opped v57y2021i1d10 1007_ 10000001001000222100-9----9
URL
Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Ncar-optimal no-regret algorithms for zero-sum games. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 235-254. SIAM, 2011.
Yongyi Guo, Ziping Xu, and Susan Murphy. On- line learning in bandits with predicted context. In International Conference Artificial Intelligence and Statistics, pages 2215-2223, PMLR, 2024.
Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, 34:27604-27616, 2021.
Eric Hall and Rebecca Willett. Dynamical models and tracking regret in online convex programming. In International Conference on Machine Learning, pages 579-587. PMLR, 2013.
Priya L. Donti, Brandon Amos, and J. Zico Kolter. Task- based end-to-end model learning in stochastic opti- mization, 2019. URL https://arxiv. httbps:/aaxxiv.org/bb//////0 org/abs//703.. 04529.
James D Hamilton. Time series analysis. Princeton univer- sity press, 2020.
Keegan Harris, Zhiwei Steven Wu, and Maria-Florina Bal- can. Regret minimization in stackelberg games with side information. arXiv preprint arXiv:2402.08576, 2024.
Benoit Duvocelle, Panayotis Mertikopoulos, Mathias Staudigl, and Dries Vermeulen. Learning in time-varying games. arxiv preprint arXiv:1809.03066, page 17, 2018.
Sergiu Hart and Andreu Mas-Colell. A simple adaptive pro- cedure leading correlated equilibrium. Econometrica, 6865):112711150 2000a.
Adam N. Elmachtoub and Paul Grigas. Smart "predict, then optimize". 2020. URL https://///at arg/abs/ 7710.08000
Sergiu Hart and Andreu Mas-Colell. A simple adaptive pro- cedure leading to correlated equilibrium. Econometrica. 68(5):1127-11555 2000b.
Gabriele Farina, Christian Kroer, Chung-Wei Lee, and Haipeng Luo. Clairvoyant regret minimization: Equiv- alence with nemirovski's conceptual prox method and extension to general convex games. arXiv preprint arXiv:2208. 0100088..489.. 14891, 2022.
Sergiu Hart and Andreu Mas-Colell. Uncoupled dynamics do not lead to nash equilibrium. American Economic Review, 93(5):1830 1836, 2003.
Dean P Foster and Rakesh V Vohra. Calibrated learning and correlated equilibrium. Games and Economic Behavior, 21(1-2):40-55, 1997.
Elad Hazan and Nimrod Megiddo. Online learning with prior knowledge. In Learning Theory: 20th Annual Conference on Learning Theory, COLT 2007, San Diego, CA, USA; June 13-15, 2007, Proceedings 20, pages 499- 513. Springer. 2007.
Dean P Foster and Rakesh Vohra. Asymptotic calibration. Biometrika, 85(2):379-355 -900, 1998.
Dylan Foster, Zhiyuan Li, Thodoris Lykouris, Karthik Srid- haran, and Eva Tardos. Learning in games: Robustness of fast convergence. Advances in Neural Information Processing Systems, 29, 2016.
Elad Hazan, Tomer Koren, and Kfrr Y. Levy. Logistic regres- sion: Tight bounds for stochastic and online optimization, 2014. URL https: org abs 1101/11155000 3843.
Geoffrey Hinton and Michael I. Jordan. Advancing health- care, e-commerce, and computational analysis with ai- ap- plications in diagnostics, market insights, and efficiency. Algo Journal of Al and Computer Science, 3(2), Nov. 2024. URL https://algovistaa org/indes 2hhp/AV/oc//artiicl//rree//////
Yoav Freund and Robert E Schapire. Adaptive game play- ing using multiplicative weights. Games and Economic Behavior, 29(1-2):79-103, 1999.
Rafael M. Frongillo, Grant Schoenebeck. and Omer Tamuz. Social learning in a changing world. In Ning Chen, Edith Elkind, and Elias Koutsoupias, editors, Internet and Network Economics, pages 146-157, Berlin, Heidel- berg. 2011. Springer Berlin Heidelberg, ISBN 978-3-642- 25510-6.
Michael Jordan and T.M. Mitchell. Machine learning: Trends, perspectives, and prospects. Science (New York, N.Y.). 349:255-60) 07 2015. doi: 10.1 10.6////cce.c.e aaa8415.

---

Prediction-aware Learning in Multi-agent Systems
Peter Kairouz, H Brendan McMahan, Brendan Avent, Au- rélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in fed- erated learning. Foundations and trends@) in machine learning. 14(1-2):1-210, 2021.
Binghui Peng and Aviad Rubinstein. Fast swap regret mini- mization and applications approximate correlated equi- libria, 2023. URL https: //axiv.//xxivvve/a org abs/2310. 19647.
Binghui Peng and Aviad Rubinstein. Fast swap regret minimization and upplications to approximate correlated equilibria. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1223-1234, 2024.
Emir Kamenica. Bayesian persuasion and information design. Annual Review of Economics, 11(1):249-273 2019.
Emir Kamenica and Matthew Gentzkow. Bayesian persua- sion. American Economic Review, 10166):5500-615, 2011.
Georgios Piliouras, Ryann Sim, and Stratis Skoulakis. Be- yond averaee convergence: Near-optimal uncoupled online learning via clairvoyant multiplicative weights update. Advances in Neural Information Processing Systems, 35:22258-22266 2022.
Johannes Kirschner and Andreas Krause, Stochastic bandits with context distributions, 2019. URL brg/abs/1900 026199966.......... 02685.
Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Conference on Learning Theory, pages 991-1019. PMLR, 2013.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Niklas Lauffer, Mahsa Ghasemi, Abolfazl Hashemi, Yagiz Savas, and Ufuk Topcu. No-regret learning in dynamic stackelberg games. IEEE Transactions on Automatic Control, 2023.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning via sequential complexities. Mach. Learn. Res., 16(1):155-186) 2015.
Tim Roughgarden. Intrinsic robustness of the price of anar- chy. Journal of the ACM (JACM), 62(5):1 2015.
Larry LeBlanc, Edward K Morlok, and William Pier- skalla. An efficient approach solving the road network equilibrium traffic assignment problem. Transportation research, 95):309-3118 1975.
Tim Roughgarden and Êva Tardos. How bad is selfish routing? Journal of the ACM (JACM), 49(2):236-259, 2002.
Raphaël Levy, Marein Pęski, and Nicolas Vieille. Stationary social learning in changing environment. Econometrica, 92(6):199911966 2024.
Utsav Sadana, Abhilash Chenreddy, Erick Delage, Alexan- dre Forel, Emma Frejinger, and Thibaut Vidal. A survey of contextual optimization methods for decision-makinn under uncertainty. European Journal of Operational Research, 2024.
Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandi approach personalized news ar- ticle recommendation. In Proceedings of the 19th international conference on World wide web, pages 661- 670,20 2010.
Pier Giuseppe Sessa, Ilija Bogunovic, Maryam Kamgarpour, and Andreas Krause, No-regret learning in unknown games with correlated payoffs. Advances in Neural Information Processing Systems, 32, 2019.
Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning, 2:285-318, 1988.
Pier Giuseppe Sessa, Ilija Bogunovic. Andreas Krause, and Maryam Kamgarpour. Contextual games: Multi-agent learning with side information, 2021. URL https:// arriiv.orr//bgg. /2107 /11///11077.......2
Anna M. Maddux and Maryam Kamgarpour. Multi-agent learning in contextual games under unknown constraints, 2024. URL htt.h:ttt:::/ettm //tpx//axvvvvv//////// http//rrii..ooo/baaaa/ 2210. 14685.
Aleksandrs Slivkins et al. Introduction to multi-armed ban- dits. Foundations and Trends@ in Machine Learning, 12 (1-2):1-286, 2019.
Elchanan Mossel, Manuel Mueller-Frank, Allan Sly, and Omer Tamuz. Social learning equilibria. Econometrica, 18(5)11235 2020.
Lones Smith and Peter Sørensen. Pathological outcomes of observational learning. Econometrica, 68(2):371-398, 2000.
Elliot Nelson, Debarun Bhattac harjya, Tian Gao, Miao Liu, Djallel Bouneffouf,, and Pascal Poupart. Lineariz- ing contextual bandits with latent state dynamics. In Uncertainty in Artificial Intelligence, pages 1477-1487.
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E. Schapire. Fast convergence of regularized
PMLR, 2022.
12

---

Prediction-aware Learning in Multi-agent Systems
learning in games, 2015. URL https://arxiv..rr//
Abs/1507.00407
Jianyi Yang and Shaolei Ren. Bandit learning with predicted
context: Regret analysis and selective context query. In IEEE INFOCOM 2021-IEEE Conference Computer
Communications, pages 1-10. IEFF, 2021.
Mengxiao Zhang, Peng Zhao, Haipeng Luo, and Zhi- Hua Zhou. No-regret learning in time-varying zero- sum games. In International Conference on Machine Learning, pages 26772-26808. PMLR, 2022.
Martin Zinkevich. Online Convex Programming and Generalized Infinitesimal Gradient Ascent. Machine Learning. Proceedings of the Twentieth International Conference (ICML 2003), August 21-24, 2003, Washington, DC, USA, 2003,
13

---

Prediction-aware Learning in Multi-agent Systems
A. Experiment.
Additional information about the setting of the experiment. The graph used to model the Sioux Falls road network from LeBlanc et al. (1975) has [V 24 nodes and |&| 76 edges. The network topology, the cost coefficients pp,e >> as well as the quantities d 0 to be sent are downloaded from https //github. com connssssap/// contextualgames/ cree/main//it mmaai//Soouxaallseee.. In the experiment, we consider = 5 states of nature. Each state of nature
[m]] is generated by adding noise e > 0 drawn from exponential distribution with scale parameter À 10 2 to each edge (p, 8) E. For each player [J], we let A be the K shortest paths connecting n2 E to mj M.. While there are W[[[W]]
552 agents in total on the network, we exclude agents for whom the lengths of the longest path exceeds the length of the shortest path by more than 2. This is because the optimal action tends to trivially be the shortest path irrespective of the state of nature for these agents. With this choice, we are left with J = 91 agents having actions generating rewards of the same order of magnitude. The simulation is run over T = 2.10 timesteps. The displayed regrets for predMWU and OMWU are averaged over agents.
Online supervised learning in the experiment. As explained in the main text, for any & [T].
exp(3;X0)
P(Z = 2 x|x²]) = ((32, = Evez exp(3
where X E R with b = 10. In the experiment, for any t E [T], X² ~ (m, 5L) with m E [1, 4| All agents receive the same covariates from sack of simplicity. For any = E 2, 8 E TR drawn before the simulation according to a Normal distribution (0, 51)).
B. Discussion of H2.
In this appendix, we briefly outline two possible approaches to carry our analysis without H2. More precisely, we assume in this section that 2 C a compact context set.
1. One first natural strategy involves discretizing 2 using an e-net and projecting each incoming context E 2 to its nearest neighbor on the net. Under suitable smoothness conditions on the loss or reward functions, this could enable reduction the finite context case. However, this method typically results in regret bounds with exponential dependence on the dimension d, which can severely limit its applicability in high-dimensional settings (see, e.g.. Theorem 4 in Hazan and Megiddo (2007)).
2. Alternatively, one could seek to work directly with the continuous context space. However, without placing restrictions on the policy class, it is possible to construct problem instances where both external and swap regrets grow linearly in the number of rounds. This highlights the necessity of controlling model complexity, for example by (i) restricting to a finite policy class (as in Auer et al. (2002)), or (ii) assuming linear structure in the policies (cf. LinUCB-style approaches). possibly combined with complexity measures such as sequential Rademacher complexities (Rakhlin et al., 2015). Each of these directions would require introducing new assumptions, proof techniques, and analytical frameworks, and therefore warrants a dedicated study.
C. Discussion on Definition 1 and Definition 2.
In this section, we provide further interpretation about the equilibrium concepts defined in Definition I and Definition 2. First, of all, recall that e-contextual coarse correlated equilibrium is defined as follows:
Definition 1. [Sessa et al. 2021] Let > 0. An E-contextual coarse-correlated equilibrium is jojon policy v Z (AA) such that for any j E [J] and n² E IP:
T-1 Σ (()
KE[T]
< T Σ
d(T (2x), Ez) te.
EE(T]
14

---

Prediction-aware Learning in Multi-agent Systems
For any Z 2, the distribution (=) can be interpreted as correlation device that generates and recommends pure actions agents. We say that (=) is equilibrium in the sense of Definition if player can decrease their expected cost by ignoring the recommendations from before they have even been drawn on average over time. Note that contrary to the classic coarse correlated equilibrium (Foster and Vohra, 1998). V 2 E 2 + v()) E P(A) is policy that maps contexts to distributions over joint actions.
Second, a e-correlated equilibrium is defined as follows.
Definition 2. Let E > 0. An E-contextual correlated equilibrium is a joint policy V 2 - (A)) such that for any j E [J] and e² A x 2 + A
T
Σ TE|T]
E. BaND
(()))))
2+)]
T
2 Z.), a)), NE(T]
2), +
Just before, can be regarded correlation device. It is equilibrium in the sense of Definition if player can decrease their expected cost by deviating from their recommended action after it has been drawn, average over time. From this point of view, being a correlated equilibrium is more demanding than coarse correlated equilibrium. Note that Definition 2 extends the classic correlated equilibrium notion (Aumann, 1987) to the contextual case, by letting the swap functions g² () depend on the state of nature.
D. Useful algorithms.
Algorithm 2 Contextual Mannour algorithm.
1: Input: no-external regret policy Td E IP.
2: Initialize hi = 0 for any k E {1,...,K}.
3: for each t. E (1,...,77 T):
do
4: Predict 2i E Z.
5: For every &o E {1..... K}, get ph. T² (bp, 24). and define P/- (ri,el... ... pk,,) RR
6: Play wi AK such that
P/wl w/
7: Observe Ze E Z and d (w, E Bdxk
8: Update hgg = hiee U fw [k] (w, Zz} for ay E fl..... K}.
9: end for
Algorithm 3 Standard Optimal Algorithm (SOA) from Daniely et al. (2014).
1: Input: An hypothesis class G C {g X' + 2} with Littlestone dimension dim y (9) < co.
2: Initialize Vo = G.
3: for each t E {1,..., T): do
4: Receive X, E X' and define v.(2) {g V g(X,) 2} for any Z
5: Predict 2, E argmaxzez dim e (V((*) ())
6: Receive Z, Z and update V, (((2)
7: end for
E. Notations
For the proofs, we use the following notations and shorthands.
For any E 2, x -1 E [T): Z, = 2) ...,..., 12 where n. = -
15

---

Prediction-aware Learning in Multi-agent Systems
Algorithm 4 Learning with Expert Advice (LEA) from Daniely et al. (2014).
Input: An hypothesis class C {g + }} with Littlestone dimension dim (g) < 00, N Algorithm 3 with N & (m?T)dimz (9).
experts using
2: Set 1 / /8)n
3: for each 1. (I,...,7)) do
4: Observe X, E receive expert advices (Xt) ff (x,)) E ZN
5: Predict 2, = (X₂, with probability proportional to exp( -n Ex<l (x, + Z+)).
6: Receive Z 2 and send it to experts as a feedback.
7: end for
Algorithm 5 Optimistic Mirror Descent with predicted context.
1: Initialize V
V a.. Oa K and Ps1
Pam arg R(Ø).
2: for each t E [T] do
3: Observe 2/ 2, set Mi- 21 and D7 p2:--
4: Play :i- argmin Ax 11 MM Zi, w + DR ;.)
5: Observe Ze E Fd and ' (w, ' Rack
6: Compute Pr argmin 1 (w( " -Z,00) + DR(g,T))
7: Update Vz,- < T (w,") and + pr.
8: end for
Algorithm 6 Optimistic FTRL with predicted context.
1: Initialize we argmin weAx R(w) and V 1 sm OdxK-
2: for each / E [T] do
3: Observe 27 and set Mi 1p z
4: Play wi argmin - 112, Zi } 3 M," Z7, w)
Dre (w)
5: Observe Ze E Rd and Φ (w; ) update 2z + D (ww,"))
6: end for
For any j E E and i E (1...., nz))
T (w -;²) = 2,1
w = w
M1. = 2,
g 9
24 7
F. Technical lemmas.
Lemma 1. Let E [J], w E (AA) with w = w X wwwi and 4 (w (w- 1) = (Bw- 16 a E 12dx
We have:
d(w, Z) = (Z, q (w" )w")
Proof. Let j E [J], 7 E 2 and w E (A) with w = u x w - By Fubini theorem,
dl (w, Z) Engz (Ew- (Z, 0 (a. 1|
Σ k=1
w [k] Ew-, (Z.
K
2,
Σ
n [k] Ew
[0,(a,, ))
= (Z, 20 "wwdd
16

---

Prediction-aware Learning in Multi-agent Systems
Lemma 2. Let E [J]. For given sequences (Z1,...,23 ZT) E zT, (2i...., 24,) z and (wi ................................ wT')
((A-))", Algorithm and Algorithm with R w + EkE(K] w|k] In w[k] - w[k] produce the same iterates: wy w/ for any t E [T].
Proof. Observe that the Bregman divergence DR(w, (w(wee) 2) = R(w) - -())) - (VR(u), w -u) generated by R w T Ene[K] [[k] In w[k] - wi[k] is for any w, E Ax:
DR(W,, u) KT,(w, v)
where KL denotes the the Kullback-Leible divergence. Therefore, in this proof we write KL instead of DR. Algorithm 1 produces an iterate / E Ax such that for any é E [K]]
MP + Σ 1 = =
exp 77
w/(0
(8)
]KE(]] exp
-
M + + 112 = 2:300 |1> 22:
We will show that the iterate of Algorithm 5, पे = argmin 1/ MM 2i, w) KL F.') is equal to (8). this end, we define
P = (T E (1...., 1- 13: 2r = 2
and we write P/-- . ,xy) where No Erst 112r 2/}. We prove with a recursion that for any r {L...., N we have for any E [K]:
-11 >i c (w 10929
exp
g 10
(9)
EnE(K]
Fr.
[k] exp
11 - T ( 27
For I, by definition of Algorithm 5, 32 argmin R(g) mmmmm11 'Im where 1m (1...., 1)" so (9) is true by the convention Eieo k; = O. Suppose now that (9) holds true for some r E .I....,N/ 1}. By definition,
WEAK argmin Tf (w.,)) + KL(w,TH).
Equivalently, it is the solution to
min max C(y, A) with C(g,A) - 9 AER
= ((g,A)=11(
(w -KI(I. + X( Σ
glC - 1).
KE(K]
In particular VL(G A) = 0, that is for any l E [K]:
(w,",,;"" 11,2, In(G In [0]) = so I 3.. exp 11100 "p00"/(w,,"" (w.:')
10922 ->) -
(10)
Using the fact that EME[K] Pi. [k] 1, we obtain from (10) exp(A) EkE[K] H.. [k] exp((1)0 (w
of. 14 expl-1pff (we 2 EnE(K] o.. [k] exp exp(-114>) (w 24.)
/ [
(11)
and using the recursion assumption establishes the result. Finally, observe that ( Mr 2/, w) + KL(w, g.)
argmin
weAx
By the same lines of computation as previously, we obtain that for any E [K]:
ol exp
- [M
[1
ElE(K of exp
M [+] 2x
17

---

Prediction-aware Learning in Multi-agent Systems
Finally, by definition of Algorithm 5, of x Jxe exp(-n/(b (w )) hence by (9):
-n Ei= D (w ( [C] + M 2
exp
EkE(K: [ exp -17 Ei=l 2 (w [k] + ME [k]] 27
Observing that MP- = My by definition for any t E [T], we obtain the desired result.
Lemma 3.
For given sequences (Z,,..., ZT) zz (Z),..., 2/)) E z and (wi 2............................... W WT') E P(A-)), Algo- rithm I and Algorithm 6 produce the same iterates.
Proof. The proof proceeds as the one of Lemma 2: writing the first order condition of step 4 in Algorithm 6 leads to the expression (8) of the iterate of Algorithm 1.
G. Proofs.
Proposition 1. Assume that player j [J] plays algorithm n E II achieving Rt & f(J,T, m) for some
[:N: R.. Then, one can design algorithm Tt E TP achieving
Ry < Kf(J,T,K,
Proof. Let E [J]. Assume that there exists T² II' and f No R4 such that the regret Ry R of m² satisfies:
R < m.
(12)
We consider the policy Th. III described in Algorithm 2. this proof, we define for any A: E (I....,K] K]:
r
Ze. ph.
min ma:Z AA
W/ TT (2
(E(T]
tE[T]
the regret incurred by म5 when fed with the histories i..,,... M Ht. The swap-regret of कग reads:
Σ (''( (w, )) ut N((w] 2r)) (E
KxK allows Note by linearity of c in w E AK (Lemma 1), defining A E Z + (Ai(a),)) 2) (. E {0, 12Kx rewrite X4 X&w, 7+) A Z, Juy hence:
Σ
D (w, Ze, Pf. wx) (D'(w,)) No. (Ze mut)
(because mi Pf w!
17
Σ
w [k] ('( b
Zei Σ
( X X2 2i))
13 []
[E(
kE(R]
rhe & IKf(JT,KK,.
K
Proposition 4. Assume H3. Then with 7 6(1 - -1
1
Σ C.(w)) < 7C'h x
1
Σ 9t
T
(1 PTT jE[J]
1E|21
18

---

Prediction-aware Learning in Multi-agent Systems
Proof. Let p: 2 + A be optimal pure strategy policy, which satisfies EeErr C((p(Z,) C*,, For any j E [J] and E Z, we denote by 82 (Z+) the distribution which puts mass 1 on the optimal action p(Zi)lj} for agent E [J]. For any (Wi...., .T). 9 (A)", we have
T
J T
Σ C.(w,) = ΣV
Zeo 2 (wr )ue)
E
Σ j=1
+
Ze (w, (ww,7)8611)))
j=1
j=1
Σ Ry +
Ze, E w, (0s 1)
j=1
j=1t=1
Ry + STC + Σ Ci(wi).
where we used the (6. smoothnsss assumption in the last line. Re-arranging the terms allows to conclude.
Proposition 2. Assume that for any E [J], agent j uses a policy x E IT incurring an external regret Ry as in (4), and denote by wi - mi (2i) for any & [T). Let Dr 2 - (AA) be such that for any z 2.
n2 E1 8... ... ... ww ifn, 00 (K K-1)
ir(2)=
otherwise.
Then, Dr is an e-contextual coarse correlated equilibrium with
max T 1R
JE(J]
Proof. Let j E [J] and X² E TP, By definition, for any = 2 such that ni > 0,
T-1 Σ (er(2)) = TT
Σ
Σ
Σ Ew, [d] (a)) =T
Σ BE[T]
Ew (a))
n
EE(T)
1
This observation and Lemma lead to:
Σ (c(((Z)), Z)) - (Z), 20)
[E[T]
7
Epp (2)
(Z,) [Z, (aa))) TT Σ
B (1)))880-)11)) (z) (2000)00
(E[T]
EE(TT
T
Σ
Ew. < (Ze, ( (a:))] -T
IE (2.) ; ( (a),
(E|T]
T Σ
Ze, T (w, 3) )we}
-T-1 Σ
Ze, T (w, (w,")sa (Zo)
1E/21
1E|21
< T
Σ
Le, 4- (w, "ome]
)
-T Σ
Zz, の (w, (w)))xz() )Tm
[E[T]
TE[T]
T '
Proposition 3. Assume that for any j E [J], agent j uses a policy मs E IP incurring a swap regret Ry defined as in (5).
Lei Dr: Z > (AA) be defined as in Definition Then, Dy is an e-contextual correlated equilibrium with
= max T 1 JE(M
19

---

Prediction-aware Learning in Multi-agent Systems
Proof. Let [J] and @² A 2 A. We have:
T-1 Σ
Bo(z.) ( (zz 0 (a)) (Z,, o² ( a
= T
Bw (a) of o ;2)
2EZ 1E
And denoting (w/)) = (B w (00) (d a>
})([l))e E Raxk for any E -=, by Lemma 1:
=T Σ
- -(( wb
ZE2 :
For any 2 E 2, define the matrix B. E [0,1] with coefficients (Bi)&.e = 1(e((a..)) = =a²). Observe that
1 (wi (w, So:
E BEZ 1
Σ
2" 2' (w,
Denoting oi! Blw! E Ax:
Σ
N (w, ")o?
Σ
2' " (w; (w;")oit
ZEZ MEg:
T
z / (w,
Σ
z 4 (w, (w; (2((()))
2EZ
T
Proposition 5. Assume HI and H2. Any j E [J] applying Algorithm with learning rate 1j > 0 has an external regret bounded as follows:
(5 + In(K))L +m In(K)
R4 <
11
Σ
(<'(ww;)) - Φ (w ( + 4L1
+ //
sE2 FE
w 6:-1 12
2
w
16n
sEZ VER
Proof. By Lemma 2, it is equivalent to show the result holds when players use Algorithm 5 with R. + ΣeejK] Wy In(w)) - we. We assume that this is the case for the rest of the proof. To lighten notation, we drop the tilde on g. M and i as compared to the pseudo-code Algorithm 5.
Let E [J]. We denote by (+) = Ei 1(2 # =} the number of mispredictions of player j on the context = E 2. We will prove the following inequality for any Z:
(5 + In K)) + In(K)
n2
Σ 4'' (w, wi x1(3)) < 2
Σ
Φ 22,
+ 4ef(2)
+ 17
w 2,4
(13)
811
20

---

Prediction-aware Learning in Multi-agent Systems
Let E Z. For any L E g=, the instantaneous regret decomposes as:
( w/ -d(())) = (( (wT") (<<'(w)))
M() 2, m! - (i)) + ( (M 2, ut - pa) + ( (b)(w;))) 2, pr. T (2)
(a)
(b)
(14)
where 7e argmingess ( (w, (,,')),,0) + DR(g, 9t) (see Algorithm 5). We bound each of these three terms, First, because ||- 111 and ||- oo are dual,
(a) < (F'(w,)) -M)+)) mm - - p=]1
(15)
For the second and third term, we use the following classic lemma, whose proof relies on the definition of the Bregman divergence and the first order condition.
Lemma 4 (Rakhlin and Sridharan (2013)). let b R and e E RT, and define a* argmin (a.c) + DR(a, b). Then for any d E T
(c, a- - d) < (x(d, b) Dz(d, (r(aa,))
Since wi argminwEdx n( M 2/, w) + DR(w, st), applying Lemma to (b) gives
1 1) Mi 23), wř - - -m) (DRiee si) DR( w²) - DR Pr(w(()))
(b) <
Observe that with R(p) = ErE(K] Pe Inpe pe, we have DR (p. KL(p, q). Hence by Pinsker's 's inequality,
< ( AMT (2- 27), wa - -p.) + 17
! ( ( ot)
1 (10- well +
+1| Wu - of 13))
(16)
2
Likewise, P. arrginngess (0! Zr.9) + PP< gt) so by Lemma 4:
(c) < _ (D (DR( (R((T((2).p) Dr((d.
(17)
Plugging (15), (16), (17) in (14) and summing over T2t yields
(' (), wi n((()) <
Σ
O (w, ((,"))
M .0 we T011,
1
I1uut - -ral, +
1u of 11;
21
1
MP (z 22), ut ii) + 1 Σ
(DR( Dre (x)(
1 teF=
Now, since ||a|2001611] 1661, < 5 |a||
1
|b|1 for any μ > O.
2/0
( (w' 55 -Mi)² 1
1
Σ
1
w/
2
2n
2/1
2n
LE
1
Me (z 21), mn p.)
+
1
Σ
DR Dre(tt(()) (18)
" g
1
teg=
Setting 1a = 2n) and noticing that 11/2n < - 1/ 1/4 leads to
< Σ
-M) (w
(w, -
pr || + |uo (8l1))
2
4n
tE
i
(
1 Σ
D -
- Σ
MM (z 21), w/ p.) (19)
21

---

Prediction-aware Learning in Multi-agent Systems
We now bound each sum. First for term (i), writing g= ===-(i,-....
-(i,...., ( (and using the shorthands defined in Appendix E):
2
2
Mi
( 2,t
-,,,
20
By definition of Algorithm for any i E [I,...,0z]] we have M
+ 2,2-1
if 2/ 2,
2, SO:
n2
1 1 2,
= 23 (0/
Φ Φ
+ Σ
R2
1[2,, *
M 1 '2) 1 -
2,1-1
2
im1
im1
By HI:
Σ
11s
1 1 2,
= =
( ( - 11
T
+
Σ
n2
1 1 #2)
80
i=1
T
+ (2)
(20)
For the term (ii), observe that for any i E {I.... nzJ
| -
||
2
< 4
w - 22.1 |1: + g2. - p2..-111
2 +4 w 2, - p p/
(21)
We then have:
2 +
(2l1')
(1
/w - 22.111)
Σ
w/ - -5
=
+
1E
1=1
[ 2,,1-1 - P
2
+ w 2 22.
i=1
[
Pa
112
P2.0
1
2
20
p P2,i-11 ||
w
2,
w
2,0-1
g2
(by (21))
Moreover, by definition of Algorithm 5, g0,
p2 p2, whenever 2/, 2, So:
2 || 2
1 + =2)/102,1 - P... 1|3
W 2,1
w
i=1
M2
11
w
w
42f(2)
(22)
Regarding the term (iii), we can use the same reasoning by writing for any E fl....,
(R( - - = (R( D'e (T{ DD P1.
Since L2, =
if 22 -
z, summing over T2 gives:
Σ - DR(( = Σ 112g, # x)
- -Datt))))))
- (3)
22

---

Prediction-aware Learning in Multi-agent Systems
Observing that 0 & (p( ln( for any (p.g) A and that the second sum is telescoping:
Σ DR(((((). - DR((T(()) < (z)() + ())
(23)
Finally for the term (iv), observe that for any E T we have by H1:
(M. 72), ut ir)
41 ( マ 2}
Σ
Mr 23), ft b.) < (2)
(24)
Then, plugging (20), (22), (23) and (24) in (19) establishes Equation (13), and summing (13) over 2 gives the desired result.
Proposition? 7. Let Lr = Eje(s Lt and assume HI, H2. If all agents use Algorithm I with a learning rate
(4(J- - 1)) then
Σ EE|
Ry < 4J +
LT J-1
O (LT)
Proof. Our proof follows from Syrgkanis et al. (2015) with our new RVU bound. Let (1, (3) E [T]2 and E [J]. Observe that:
- 20 ('(w"')) (
ww, (K (f)))) - Bw, (oss(ar,
max KE,K]
And since (Øy(a), 2) & for any a E A by HI, with TV denoting the total variation:
TV(W,' ) =V
TV
X w
kÿj
TV wx)
Σl
w
11
Squaring the previous inequality and applying Cauchy-Schwarz Schwarz leads to
2 w 111
(T) E (i(ww,
<
Σ
(J-
Σ
Juo w
(25)
This implies:
2
Σ (W())) (
<J
E
ΣΣ
Σ
w (J 1)²
Σ
m
(26)
JE[J]
JE(J] kサン
jE|
On the other hand, summing the RVU bounds featured in Proposition 5 over players gives:
Σ oi <
(5 LT + mJ In(K)
+1
ΣΣ Σ #EZ (E jE(
| - 22 (0%,
+ ALT
x
Σ ΣΣ>>
W. w 2
16n
#E2 (e jE[J]
Plugging (26) for any z 6 Z, = to and t' = = for i (1y) gives:
(5 In( K)) Lo + mJ (n(K) + 4nLT + (n(s-19) - 1)2
1 DE Σ
16n
2,1-1
=ez sE(n,] JE(J]
Then, picking = (4(J 1) yields the desired result.
23

---

Prediction-aware Learning in Multi-agent Systems
Lemma S. If player E [J] uses Algorithm I with learning rate 1j 0, for any fl....,n..
[ w w
111 < 31 = + 2(1 - 1 = =]}]
Proof. jet E [J] and i (I,...,11)) By Lemma 3, it is sufficient to prove that the claim holds true for Algorithm
First if 2 # 2, Iuu -2,5-1l12 < Second, assume that 2 2. We define for any {l...., nz fv w +
w: - Th 2 + Ma + + and gr : : + w. E D.T TT + +1 (R((). Observe that for any w E Ak.
[i(w)= gv))) (w, (M 22 )')')) and Sa(w) gr- (w)) (u, M2
(27)
We also define f/-1 = argmin Di- (v). We have:
| w - || < W v--1/,, + p
(28)
One the one hand, by n -trong convexity fa with respect to || 112. we have
2n w v2-1/,, & f((--1)) - f((w(,)) + Vil(W,,)..d -1-11
-
And since w argmin f((w) by definition in Algorithm the first order condition gives:
w 2,
v/-1/, ||, < - - f((w
(29)
2n
Since f:-1 = argmin Di- ( we obtain by the same reasoning,
vi-11,, |1, < (i-1( - gi- 1 (vi-1)
(30)
27y
Summing (29) with (30) and applying remark (27) leads to:
[w/, vz vi-11, 11: & n 11-11 w/ M ) 17 w
0-
Mr
2
Dividing on both sides by |/mg, 1111l11 gives:
W - w- ||, < 1) M En
(31)
Similarly, it easy to check that
2n 0 - I| fi-1(1=-)- (-1 and
1
1
w | 1i-1(w
9:
2n
So once again summing these two inequalities and making use of remark (27) leads to
| Vi- 1 & n 1i-1 w - (M,, 22 22,''') < <n|[w
-
Ui-1
Dividing both sides by | - 1/, gives:
W 04-1/ < M $ T..''2
$ 2n
(32)
Finally, plugging (31) and (32) in (28) yields the result.
24

---

Prediction-aware Learning in Multi-agent Systems
Proposition 6. Define LT maxxe(]) Bp and assume HI and H2. If all agents use Algorithm with learning rate then for any [J]:
(5 (nlnnK)]L mln(K)
Ry <
27
+n[(J- - (9Th) 4LT) + 4Lr]
In particular ifT = (())LLT), setting ni" = -6J-1/27-1 [ln + m)) leads to:
Ry = (1)=
Proof. Let j E [J]. By Proposition 5 we know that
By $ (5+ + L m ml))
+ 17
Σ ZEZ [E[
① 2,, - 0 11
+ +444
(33)
7
Moreover, we proved in (25) that for any Z and E {l, (l....,ma), |1(0 we 1.li. so summing over contexts and timesteps gives:
Φ 22,--1) 1 < <J - 1)
ΣΣ
- 2,
& 1)-1)
w 2,,
- 1/2
=EZ ]
#E2 iE(nal
Applying Lemma yields:
< 1)-11 Σ
=
= = # xz)
2E2 iE [n_] bzj
(J 1) Σ
9n 1 = + #2)
=EZ kzj
[E|nz]
(J-11) Σ
Σ
9nzn) + 407
1262
Therefore,
ΣΣ ( 2,,-1) & (J 1) Σ + & (J ()3 + 4T,).
-
1'2
(34)
#EZ v
Plugging (34) into (33) establishes the first part of the proposition. For the second part of the proposition, define for any 1) 0:
(5 + In(K))[r + In(K)
h(n)
+ (1) ALT) + ALT)
a = (5 (n)(nn()) ml
bnz
en with
b 9(J 1
4((J 1) + T
We looking for minimizer of h make the bound tight. Since h is continuous and lim h(n) lim h(n) +oo, it admits minimum on (0, oc), which is also unique by strict convexity. By the first order condition, h is minimized
for
12ab + 2
6b
25

---

Prediction-aware Learning in Multi-agent Systems
We now determine the order of magnitude of 1j" On the one hand, by sub-additivity of + va:
rj [La)))))(())2===((((((())))))33) 0((a6))/46-112)
(35)
On the other hand, observe that by assumption T (( so ab (2(c²). Consequently, for T large enough there exists 7 such that 12ab e yo² and it follows that
v 2 + 12ab-1h2 c=
+12ab dt
12ab
12ab
v 12ab
2/B
2 + 12mb
2 MV1+77
12ab
2/ 1 +
so we deduce that for 7 > large enough,
/12bb
17 >
12/1 + that is 1f" 2==(((a)1/44
Therefore, 17' = @((ab)1/4B- 1/2). Plugging this value in h finally gives:
h(r²) 0(614400 3/4 + c/4 = 0(b2/408/4)
because = (26112)22) by assumption. Replacing and b with their actual values yields the claimed bound.
Proposition 8. Assume HI and H2. player j E [J] uses Algorithm I with ((In(())L)) + / 1/2)) then for any sequence (w.',..., wT') E 3 (A-))²
Ry = 0( (VIn())(1) + mL + +T)
Proof. Let j E [J] and (wi ,...,.,,??? ((A-j)2 be any sequence of competitor strategies. We have for any (t,t') [7]2 and Z:
( (00 (w; 10 (www)))
2
< 2
④ ( 2/222
+ (w(;"""")))
max w [o (a)) (.))) 2 kEld]
W, (o(0o). (2)
max E
+
kEld
2
2
max E kEld] w, { (0'((a-- (a))aa--)))))))
max Bw (ol kEld
+
<,,
where we have used HI in the last line. Therefore by Proposition 5, we have:
(5 + In(K)) In(K) + 4nT + TdT)) O
In In( + m)
+ nn((l + +7)
Jy x
"
17
Then, setting 7 ((lIn(K) + m)) + +T) + leads to
Ry = ([I( + 12)
Proposition 9. Suppose that for any L E [T], there exists 2e E Z such that 2/ = Z. for any j E [J], and let LT = Enery 112, * Zt}. Assume HI and H2. If all agents use Algorithm with a learning rate nT* =
1///1/2--/4(|m((X3 m4) then:
24 = ([nn((()]LLL m)83/111/11122)
26

---

Prediction-aware Learning in Multi-agent Systems
Proof. In this proof, write for any E and E ( ncy Zez
Zz.i By Proposition 5 know that
K x (5 LT + m In(K)
+1
ΣΣ cEZ i=1
② 2,8
T ) + +
(36)
For any & E 2, we define C7(2) = EiEg. 112 22} and 8 = fi nz? 2n, = 2 and 22,5-1 = 2}. We have:
② q 5,5-1
2
= #E2 NE
Φ
2,1-1
2
+
2,1
262 Gml
Note that g² \ 6== = EiE n......,..]: Ze, & or Z20011 + so gr
80
(br(2) Together with the fact that
[1 2, Φ == for any [J] and g= \ 6 this implies:
( ( - 2 2
+ +86((z)
=EZ
VEE
We proved in (25) that for any = E 2 and i E (l,...,mzh. ( - Φ
1= < (J - 1) Exkzllluf,...
- so
Σ
1J-1) Σ
w w 8Lr(2)
262
1 keyl
And by Lemma 5:
Σ (9(J - 1) !n? + 887(2))
2EZ
< 9(J 1)? + 8Lr
Plugging this bound in (36) yields:
à (5 + Lr( + m In()
à + bnp on with
Ry & h(n)
b 9( 1)
1)
ē 12LT
We observe that ē x J 2c, where c > 0 is defined in the proof of Proposition particular, since Ly & T, we have ab (((²), hence do not need it assumption. The rest of the proof follows exactly as in Proposition
27


Reviews:
[{"review_id": "dkbEahBhvc", "reviewer": "Reviewer_RGHK", "summary": "This paper introduces a prediction-aware learning framework for time-varying games, where agents can forecast future payoffs and adapt their strategies accordingly. The authors propose the POWMU algorithm, a contextual extension of the optimistic Multiplicative Weight Update algorithm, and provide theoretical guarantees on social welfare and convergence to equilibrium. The framework achieves performance comparable to static settings when prediction errors are bounded", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We thank the reviewer for their valuable feedback. We respond below to the weaknesses they indicate, and reply to their questions.\n\n> “The paper assumes bounded prediction errors, which may not always be realistic.”\n\nWe emphasize that our results hold in full generality, without requiring a bounded number of mispredictions. The case where $L_T​=O(1)$ is presented solely for illustrative purposes, highlighting the connection with the well-known static guarantees from Syrgkanis (2015). However, this is not an assumption underlying our analysis.\n\n> “Limited empirical evaluation  [...]”\n\nWe thought that our traffic routing experiment was sufficient to demonstrate the empirical effectiveness of POWMU, which seems to be an opinion shared by other reviewers. However, we are open to adding another experiment if the reviewer considers it helpful. An interesting case would be optimal trading strategy on a financial market, where thehe actual price of the asset would depend (for instance linearly) on the actions of the traders. Before making orders on the market, the trader would forecast the future prices of the asset based on public information. We could work with the historical financial data and contextual information from [3] to run the experiment.\n\n[3] Wang et al., 2023. Robust Contextual Portfolio Optimization with Gaussian Mixture Models. \n\n> “Complexity of the proposed algorithm[...].”\nIf the reviewer refers to the algorithm's design complexity, we respectfully emphasize that POWMU is quite straightforward to implement. Indeed, the method merely involves maintaining a separate instance of OMWU for each context and updating these instances based on feedback from nature. If the reviewer's concern pertains to computational or memory complexity, we also note that POWMU is not particularly demanding in this respect. The algorithm primarily requires storing vectors and matrices and performing only basic operations, such as element-wise multiplication, matrix multiplication, and exponentiation—all of which are computationally efficient.\n\n> “How does the performance of POWMU compare to other state-of-the-art algorithms in time-varying games?”\n\nThe most recent studies on time-varying games [1, 2] primarily use OMWU as their main algorithm. Figure 2 in our paper compares the regret incurred by OMWU and POWMU in our experiments, showing that POWMU significantly outperforms OMWU. This advantage arises because POWMU leverages context predictions, whereas OMWU relies solely on the previous round’s information to determine its strategy. When the game dynamics change gradually, OMWU can perform well, as suggested by the regret bounds in [1] and [2]. However, in highly unstable payoff environments, our approach achieves substantially better performance, as it selectively incorporates information from past rounds with similar contexts.\n\n[1] Zhang et al., 2022. No-regret learning in time-varying zero-sum games.\n[2] Anagnostides et al. 2023. On the convergence of no-regret learning dynamics in time-varying games.\n\n> Can the framework be extended to handle partial information or bandit feedback settings?\nWe believe extending prediction-aware learning to partial information or bandit feedback is a promising yet challenging direction. A potential approach could involve adapting the Low Approximate Regret (LAR) concept from [3] to the contextual setting, building upon standard bandit algorithms to create a bandit variant of POWMU. However, working with the LAR property is inherently more complex than handling RVU, making such an adaptation non-trivial. Although this extension lies beyond the scope of the current paper, we recognize it as an important avenue for future research..\n\n> How sensitive is the algorithm to the quality of predictions,[...]\n\nPropositions 5 and 6 explicitly characterize the dependence of the social and individual regret bounds on prediction errors. Specifically, our bound for social welfare grows linearly with $L_T$, while individual regret scales as $\\bar{L}_T^{3/4}$. Regarding the boundedness of prediction errors, we kindly refer the reviewer to the first point of our response for further clarification.\n\n> \"Are there any specific real-world applications where this approach could provide significant improvements over existing methods?\"\n\nOur framework is broad enough to be applied to various real-world scenarios. Examples include power production and trading, where the state of nature may encompass factors such as wind speed and temperature, which influence renewable energy generation and overall power consumption. Other applications include portfolio management, where agents predict future asset prices, and traffic management. We are currently engaging with a power production firm to explore the application of our method to power generation and trading.\n\n> “How does the complexity of the proposed algorithm handled?”\n\nWe kindly refer the reviewer to the third point of our reply for this question.", "claims_and_evidence": "1. Introduction of a prediction-aware learning framework for time-varying games\n2. Development of the POWMU algorithm for leveraging predictions about the state of nature\n3. Theoretical guarantees on social welfare and convergence to equilibrium are the evidences for the paper.\n4. Empirical demonstration of POWMU's effectiveness in a traffic routing experiment also varifies the claim.", "methods_and_evaluation_criteria": "1.The major method and the evaluation criteria used is regret, and the gurantees on the social welfare.", "theoretical_claims": "The proofs are well written and I have skimmed through the proofs, though not verified them line by line, but they appear to be correct.", "experimental_designs_or_analyses": "Empirical demonstration of POWMU's effectiveness in a traffic routing experiment is shown, however, this alone might not be sufficient, I would like to see some more experiments.", "relation_to_broader_scientific_literature": "The problem is well posed and novel, it will be a good addition to the missing literature.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strenghts:\n\n1. Addresses a gap in existing literature by incorporating agents' predictive capabilities\n2. Provides theoretical guarantees that match non-contextual guarantees for static games under certain conditions\n3. Demonstrates robustness in adversarial settings\n\nWeaknesses:\n\n1. Assumes bounded prediction errors, which may not always be realistic\n2. Limited empirical evaluation (only one traffic routing experiment)\n3. Complexity of the proposed algorithm might not be practical to implement.", "other_comments_or_suggestions": "NA", "questions_for_authors": "1. How does the performance of POWMU compare to other state-of-the-art algorithms in time-varying games?\n2. Can the framework be extended to handle partial information or bandit feedback settings?\n3. How sensitive is the algorithm to the quality of predictions, and what happens when prediction errors are not bounded?\n4. Are there any specific real-world applications where this approach could provide significant improvements over existing methods?\n5. How does the complexity of the proposed algorithm handled?", "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": "", "extra_scores": {"ethical_review_concerns": "NA"}}, {"review_id": "lIHiV6JdZz", "reviewer": "Reviewer_798F", "summary": "This paper discusses the problem of no-regret learning in general time-varying games with predictions. The authors argue that current regrets, defined as a function of variations in the payoff matrix and variations in the Nash equilibria, become vacuous even in simple examples like the one provided in Example 1. In this way, the paper motivates an alternative viewpoint toward prediction-aware learning by considering prediction oracles that account for changes in nature (parameterized in some way). Building on this, the authors define the notions of external and swap contextual regret and generalize the constructions of [Blum and Mansour, 2007], RVU bounds, CCE convergence, and social welfare guarantees of [Syrgkanis et al., 2015] for this new setting.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "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": "We thank the reviewer for their feedback. We reply to the points they raise below. \n\n> “The significance of the results is questionable. Once the problem is well-defined in terms of costs, etc., the derivations are straightforward and follow standard techniques in the literature.”\n\nWe respectfully disagree with the characterization of our work as incremental. Our contributions go beyond standard derivations in several important ways.\n\nFirst, we view the formalization of the problem — including the explicit definition of costs — as a significant contribution in itself. In doing so, we introduce several novel concepts, such as contextual swap regret and contextual correlated equilibrium, which represent meaningful advances in the study of contextual multi-player decision-making.\n\nSecond, the derivation of our results are not as straightforward as they may seem at first sight. Beyond handling the inherent complexity of contextual decision-making, we must also account for the intricate dynamics introduced by multiple players. In particular, players may predict different contexts at each timestep, preventing a direct application of Syrgkanis’ analysis on batches of timesteps with the same revealed context. To address this challenge, we develop a novel regret decomposition in the proof of proposition 4, which is essential for our analysis and enables us to reach our conclusions.\n\n> “The authors start the motivation interestingly with an example of predictions that are regression-based [...]”\n\nWe believe our motivating example aligns with the classification setting, as it involves only two distinct payoff matrices (one for even timesteps, one for odd timesteps), which can be mapped to a {0,1} context set.\n\n> “[...]  postponing the more challenging and interesting problem to future work. This work, despite strongly motivated examples, seems incomplete.”\n\nWhile many real-world problems can be modeled with a finite number of contexts, we acknowledge the reviewer’s point that extending our framework to regression is both valuable and important. However, such an extension would require an entirely different set of analytical tools and falls beyond the scope of this paper.", "claims_and_evidence": "Yes, the theoretical claims are well supported; the claims are fairly standard, and there is no magic.", "methods_and_evaluation_criteria": "The authors evaluate the proposed algorithm on the Sioux Falls routing problem from [LeBlanc et al. (1975)] to assess its performance under mispredicted contexts.", "theoretical_claims": "Even though I skimmed, I don’t think any major issues exist since the theoretical claims are pretty standard.", "experimental_designs_or_analyses": "The routing problem used is quite interesting, and the results seem valid.", "relation_to_broader_scientific_literature": "Learning in time-changing games with supervised learning is an interesting and fundamental problem with many real-world applications.", "essential_references_not_discussed": "None that I can think of.", "other_strengths_and_weaknesses": "The significance of the results is questionable. Once the problem is well-defined in terms of costs, etc., the derivations are straightforward and follow standard techniques in the literature.\n\nThe authors start the motivation interestingly with an example of predictions that are regression-based, but the focus of the paper is solely on online classification and Littlestone dimension, postponing the more challenging and interesting problem to future work. This work, despite strongly motivated examples, seems incomplete.", "other_comments_or_suggestions": "I cannot suggest acceptance of this work at this stage since it seems too incremental. However, I am willing to reconsider if the prediction-aware rates under regression oracles yielding regret rates matching those of [Syrgkanis et al., 2015], with perfect predictions as a special case, are included in the results.", "questions_for_authors": "No questions. The paper is well-written and straightforward.", "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": "", "extra_scores": {}}, {"review_id": "b2b0xRXDj1", "reviewer": "Reviewer_W7RW", "summary": "This paper considers time-varying games where better guarantees (wrt (swap) regret, equilibrium concepts and social welfare)  can be achieved when the agents can predict/estimate the time-varying utilities. For a J-player game with utility $c^{j}(w,Z)$ (where $Z$ captures the time-variance), the players use a variant of optimistic exponential weights method to predict $\\hat Z_t$ and update the iterates $w_t$. The analysis is relying on the assumption that $Z$ is from a finite set, which limits the variations of the time-varying games. \nThe authors provide guarantees for the regret of each individual player (Prop. 4) which is of similar order as the bound for optimistic Hedge plus a multiplicative factor of $\\bar L_T$ (total number of mispredictions of $Z$). From this a bound on the social welfare is derived (Prop 5) and guarantees for the approximation quality of an $\\epsilon$-CCE and $\\epsilon$-CE. Robustness guarantees wrt the incentive of deviating from the proposed strategy are provided in Prop. 7. Furthermore, the theoretical findings are supplemented with illustrating experiments.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We sincerely appreciate the reviewer’s positive feedback and the highly relevant reference they have suggested. We will incorporate it into our literature review in the revised version.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "This is theoretical work. The illustrating experiments make sense.", "theoretical_claims": "Yes, mostly (for anything that was not clear from the claims). To the best of my understanding, all theoretical results are correct.", "experimental_designs_or_analyses": "This is theoretical work. The illustrating experiments make sense.", "relation_to_broader_scientific_literature": "The work extends the research on time-varying games in the case where the time-variance can be estimated. It relates to the research on time-varying games on the one hand and ideas from contextual bandits (however, full feedback is considered here!) on the other hand.", "essential_references_not_discussed": "The authors should consider adding the reference 'Multi-agent online learning in time-varying games', Benoit Duvocelle, Panayotis Mertikopoulos, Mathias Staudigl, Dries Vermeulen, in addition to the reference to Zhang et al.", "other_strengths_and_weaknesses": "The paper is clearly written, nice to read and provides an interesting extension to existing results.", "other_comments_or_suggestions": "none.", "questions_for_authors": "none.", "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": "", "extra_scores": {"ethical_review_concerns": "none."}}, {"review_id": "MKHPP4uSiu", "reviewer": "Reviewer_DNiF", "summary": "The paper considers learning in time-varying multi-player games using prediction-aware algorithms. It begins by observing that prior results quickly become vacuous when there is a large variation between the games, even though the underlying sequence can be entirely predictable. In light of this, the paper proposes a new algorithm that incorporates predictions under the framework of contextual learning, wherein, in each round, the algorithm makes a prediction about the underlying state of nature. When the sequence of states is somewhat predictable. the paper shows that existing results from the static setting can be generalized even when there is substantial variation between the games.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We thank the reviewer for their very relevant remarks. We answer below to the points they raise. \n\n> “What is ARIMA in Line 130? I might have missed the definition.”\n\nARIMA refers to Auto Regressive Integrated Moving Average process, a popular process in time series analysis (see, e.g., [3]). We will make this acronym explicit in the revised version of the text. \n\n[3] Hamilton, J. D. (2020). Time series analysis. Princeton university press.\n\n> “there is a typo in \"is an interesting topics for future research\" in Line 348.”\n\nThank you for pointing out this typo, we will correct it in the revised version of the text.\n\n> “The paper mostly follows the techniques of Syrgkanis et al. I wonder whether the authors tried to use some more recent results that, in the static setting, obtain polylog(T) regret bounds. [...].”\n\nWe appreciate the reviewer’s insightful question. We did consider leveraging techniques that achieve polylog(T) regret guarantees in the static setting, such as those in [4] and [5]. However, several limitations led us to build upon Syrgkanis’ framework instead.\n\nRegarding [4], the proof techniques are particularly intricate, and it remains unclear whether their approach can be extended to the contextual setting. In fact, the complexity of [4]’s analysis is explicitly acknowledged in the abstract of [5].\n\nAs for [5], its theoretical framework—based on self-concordant barriers—appears more adaptable to prediction-aware learning. However, it comes with several drawbacks. First, the polylog(T) regret bound in [5] (Corollary 4.5) introduces a dependence on the number of players J and the number of pure actions K through a factor of JK^{5/2}. In contrast, our external and swap regret bounds scales as $\\sqrt{J}  \\ln K$ and $ \\sqrt{J} K \\ln K$ (Propositions 1 and 6) respectively, which is significantly more favorable.\nAdditionally, [5] is somewhat less general in scope, as its analysis is restricted to swap regret and does not apply to external regret. This limitation arises because their main proof relies on the positivity of swap regret, which is not guaranteed for external regret. Consequently, adopting their approach would prevent us from providing guarantees for coarse correlated equilibria and social welfare, as Roughgarden’s smoothness condition relies on external regret.\n\n[4] Daskalakis, C., Fishelson, M., & Golowich, N. (2021). Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, 34, 27604-27616.\n\n[5] Anagnostides, I., Farina, G., Kroer, C., Lee, C. W., Luo, H., & Sandholm, T. (2022). Uncoupled learning dynamics with $ o (\\log t) $ swap regret in multiplayer games. Advances in Neural Information Processing Systems, 35, 3292-3304.\n\n> \" [...] I also did not find any guarantees about POMWU instantiated with Blum-Mansour, which is introduced in the preliminaries; but I might have missed that.\"\n\nThe Blum-Mansour reduction from external to swap regret stated in Proposition 1 is used to establish Corollary 2-(ii). We will highlight this more clearly in the text of the revised version.", "claims_and_evidence": "All claims made in the paper are clear and sound.", "methods_and_evaluation_criteria": "The paper is mostly theoretical. The experimental evaluation supports the theoretical claims and drives home the main argument of the paper: it shows that existing algorithms, namely OMWU, fail to take into account the predictability in the underlying sequence of states, unlike the proposed algorithm. The sequence of games constructed is sufficiently rich to make a convincing argument--it's not just a toy example.", "theoretical_claims": "I checked the proofs, and all claims appear to be sound; I did not find any notable issue.", "experimental_designs_or_analyses": "The experimental design and the interpretation of the results are, as far as I can ascertain, sound.", "relation_to_broader_scientific_literature": "The contributions of the paper lie mostly in the area of learning in games, and in particular, time-varying games. It addresses some drawbacks of existing results, as I pointed out above. The paper does a good job at placing the contributions accurately in the context of existing work. In particular, it extends the framework of Syrgkanis et al. from the static setting to the time-varying setting.", "essential_references_not_discussed": "I did not identify any essential reference missing.", "other_strengths_and_weaknesses": "On the positive side, the paper makes a clear contribution by addressing an important gap in prior work in the context of time-varying games. The proposed algorithm is natural and very much relevant in practice--as long as the number of states is reasonably small. I can certainly see many possible applications in which the results of the paper can be used. The paper is also very well-written and organized. The key ideas of the paper are explained very clearly.\n\nOne drawback is that most of the results are not particularly challenging to obtain, and follow mostly by adapting in a straightforward way existing techniques. But I do not believe that this alone is a basis for rejection.", "other_comments_or_suggestions": "Some minor points:\n\n- What is ARIMA in Line 130? I might have missed the definition.\n\n- there is a typo in \"is an interesting topics for future research\" in Line 348.", "questions_for_authors": "The paper mostly follows the techniques of Syrgkanis et al. I wonder whether the authors tried to use some more recent results that, in the static setting, obtain polylog(T) regret bounds. I also did not find any guarantees about POMWU instantiated with Blum-Mansour, which is introduced in the preliminaries; but I might have missed that.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper discusses the impact of predictability in time-varying games. Specifically, the authors consider a contextual normal form game in mixed strategies where the cost to player $i$ is of the form
$$
c_j(x;z)
	= \sum_{a_1\in\mathcal A_1} \dotsb \sum_{a_J\in\mathcal A_J}
	x_{1,a_1}\dotsm x_{J,a_J} \, c_j(a_1,\dots,a_N;z)
$$
where $z$ is a context variable, the $a$'s represent pure strategies, the $x$'s are mixed strategies, and the inner $c_j$ is linear in $z$. During play, the context variable $z$ evolves over a finite set, leading to a time-varying game. The authors then provide bounds for a contextual version of the external and swap regret of the players, assuming that they all follow a likewise contextual version of the optimistic multiplicative weights algorithm. Finally, assuming the game satisfies a certain "contextual smoothness" condition (a context-based version of Roughgarden's $(\lambda,\mu)$-smoothness condition), they translate these bounds into social welfare approximation guarantees.

The paper's main premise is the following observation: previous results on time-varying games become vacuous when there is high variation in the underlying game, even when this variation is completely predictable. This is a solid and insightful observation, which was well-received by the reviewers. At the same time however, the paper is not without its flaws:
1. The paper is heavy on notation, often dense and not always well-motivated, and which significantly hampers readability—even for experts. 1. Assumptions are introduced without sufficient justification, including the finiteness of the context set (a point of concern for reviewers), and the “linear bandit” structure. This lack of clarity makes it difficult to parse the mathematical content and evaluate the plausibility of the results.[1. For example, the smoothness assumption H3 is said to hold for a wide class of games, but the only examples provided are context-free.]
2. The motivation for several modeling choices is often underdeveloped. For example, it is unclear why the authors emphasize swap regret rather than the dynamic regret - which is more commonly studied in time-varying games. Choices of this type feel incidental – as opposed to driven by a clear conceptual argument – making the narrative of the paper weaker.
3. The technical insights in the paper are also relatively limited: for example, in the case of the swap regret mentioned above, the authors invoke the standard Blum-Mansour reduction, and there is little more going on than that, so it is not clear how this expands our understanding (and likewise for the RVU framework of Syrgkanis et al., etc.).
4. The paper also has some issues with positioning - for instance, given the work of Besbes et al (2015) on dynamic regret, or the original paper on time-varying games by Duvocelle et al (2018).

Overall, it was not easy to make a recommendation for this paper: the authors tackle an important problem with a compelling starting point, but the presentation needs substantial revision. The writing should be simplified, the assumptions clarified, and the technical and conceptual motivations better developed.

My honest opinion is that the paper does not quite clear the bar for acceptance in its current form; at the same time however, it is not out of line with other papers that have appeared in ICML (or similar venues). I am therefore making a "conditional accept" recommendation contingent on a significant rewrite that addresses the concerns above.
Decision: Accept (poster)