Prediction-aware Learning in Multi-agent Systems

Aymeric Capitaine, Etienne Boursier, Eric Moulines, Michael I. Jordan, Alain Durmus · 2025

Read Prediction-aware Learning in Multi-agent Systems by Aymeric Capitaine, Etienne Boursier, Eric Moulines, Michael I. Jordan, Alain Durmus (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-19144.txt.

Introduction

Aymeric Capitaine and four co-authors let game players learn with a view of what comes next. In shifting games, past playbooks lose their grip fast, and score bounds go slack. Their 2025 frame lets each player forecast future payoffs from a hidden state of the world, then adapt.

Their method, POWMU, grows a classic weight-update rule with that forecast in hand. Proofs tie the frame to good welfare and drift toward stable play. When forecast error stays bounded, results near match the calm case of a fixed game. A traffic routing test showed the method working in practice. The team frames foresight as a missing piece in learning games.

Catalog record

CREATORAymeric Capitaine, Etienne Boursier, Eric Moulines, Michael I. Jordan, Alain Durmus
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE106 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-19144

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Prediction-aware Learning in Multi-agent Systems Aymeric Capitaine, Etienne Boursier, Eric Moulines, Michael I. Jordan, Alain Durmus 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. 1 Introduction. The framework of uncoupled online learning in multiplayer games has sparked a lot of interest for its ability to realistically model the interactions of rational players engaged in a dynamic game. Since the seminal works of Foster and Vohra (1997) ; Freund and Schapire (1999) ; Hart and Mas-Colell (2000a) , progress has been made towards obtaining fast convergence rates for different equilibrium concepts, including coarse correlated equilibrium ( Syrgkanis et al., 2015 ; Foster et al., 2016 ; Daskalakis et al., 2021 ; Piliouras et al., 2022 ; Farina et al., 2022 ) correlated equilibrium ( Chen and Peng, 2020 ; Anagnostides et al., 2022a ; Anagnostides et al., 2022b ; Peng and Rubinstein, 2023 ) and Nash equilibrium ( Anagnostides et al., 2022c ) . However, most of these works assume that the game remains constant over time. 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 et al., 2024 ) . Following methods initially developed by the online optimization community ( Chiang et al., 2012 ; Rakhlin and Sridharan, 2013 ) , these studies bound the dynamic regret incurred by players with measures of the time-variation 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 is important–making the above mentioned bounds vacuous–yet very simple to predict. In Example 1 , we exhibit a simple instance of time-varying game where the regret bounds derived in Zhang et al. (2022) grow linearly with the horizon T>0 . However, the dynamic underlying the payoff matrices is entirely deterministic, and knowing it would result in a constant regret. This highlights that the current time-varying framework fails to account for any predictive capacity of the agents. This is all the more surprising as predictive models become ubiquitous in numerous economic sectors ( Jordan and Mitchell, 2015 ; Gogas and Papadimitriou, 2021 ; Hinton and Jordan, 2024 ) , making it likely for strategic agents to possess a forecasting ability regarding their future payoffs. This work aims to fill the gap, by asking the following question: How does the quality of predictions made by rational agents in time-varying games regarding their future payoffs affects social welfare, as well as the convergence to equilibrium ? Contributions. We address this question with the following contributions. • First, we introduce the new prediction-aware learning framework, where players forecast future payoffs in an online fashion and design their strategies accordingly. In a nutshell, we build on the contextual setting 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 learning in games with contexts and predictions requires to introduce new regret and equilibrium concepts. In particular, we extend correlated equilibrium ( Aumann, 1987 ) to our framework. • Second, we propose an algorithm called POMWU —which a contextual extension of the optimistic Multiplicative Weight Update algorithm ( Daskalakis et al., 2021 ) —allowing 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 Syrgkanis 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 ( Daniely et al., 2014 , which is the case under realizability, see) , our bounds match the guarantees on social welfare and equilibrium convergence for static games. Our analysis builds upon a new notion of contextual Regret bounded by Variation Utility (RVU) which bounds contextual regret by the sum of the length of the context-specific sequences of feedbacks and strategies. Indeed, a naive application of the standard RVU framework results in looser bounds. 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 setting, where the optimizer interacts with other agents during the learning process. On the other hand, recent studies in 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 multiplayer games, Lauffer et al. (2023) ; Harris et al. (2024) focuses on Stackelberg games with side information. However, these works assume that the context is revealed to players at the beginning of each period, unlike ours where players have to 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

Read the complete text