Research map / Multi-agent systems and games / Games and equilibria
Prediction-Aware Learning in Multi-Agent Systems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces prediction-aware learning for time-varying (contextual) games where players forecast the state of nature online, and proposes POMWU, a contextual optimistic MWU with one OMWU instance per context, giving regret/welfare/equilibrium guarantees that scale with misprediction count, validated on Sioux Falls traffic routing.
Problem
Existing regret bounds for uncoupled learning in time-varying games become vacuous under large but predictable payoff variation because agents cannot exploit their ability to forecast future payoffs.
Approach
Players predict a state of nature (context) before acting, and POMWU keeps a separate optimistic MWU instance per context, using the predicted context in the optimism step; regret is bounded by misprediction counts rather than payoff variation via a new contextual RVU bound.
Key results
- In the Sioux Falls routing experiment (J=91 agents, T=2e4), POMWU's contextual regret stays low while OMWU's regret grows linearly with time.
- Theory: POMWU achieves external regret O(T^{1/4} J^{1/2}) in the realizable case, recovering the static-game rate, and sum of regrets O(J ln(K)(L_T+mJ)) with bounded mispredictions.
- Rounds with mispredicted contexts account for a large and growing share of POMWU's regret in the experiment.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use POMWU, which conditions play on predicted contexts, instead of OMWU, which ignores contexts | Sioux Falls routing · Sioux Falls routing | average contextual regret | Helped |
| Mispredict contexts | POMWU · Sioux Falls routing | average regret | Hurt |
| Use online logistic regression for context prediction | POMWU · Sioux Falls routing | average regret trend | Mixed |
Surprising findings
- Mispredicted rounds make up a growing share of POMWU's regret over time, because the online logistic regression's prediction error decreases only slowly.
Limitations
- Finite context set assumption; extension to infinite contexts left open.
- Full-information feedback assumed; bandit feedback not analyzed.
- Regret bounds depend on the number of mispredictions, which can be large under slow online learning of the predictor.
Experimental setup
Datasets: Sioux Falls road network
Benchmarks: Sioux Falls routing simulation
Metrics: average regret over agents prediction error proportion of regret under mispredicted contexts
Baselines: OMWU
Builds on: optimistic multiplicative weights update regret bounded by variation in utility (RVU) Blum-Mansour reduction Roughgarden smoothness
Closest papers by meaning
- Learning from Delayed Feedback in Games via Extra Prediction (NeurIPS 2025 · similarity 0.87)
- Maximizing utility in multi-agent environments by anticipating the behavior of other learners (NeurIPS 2024 · similarity 0.87)
- Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games (ICML 2025 · similarity 0.87)
- Impact of Decentralized Learning on Player Utilities in Stackelberg Games (ICML 2024 · similarity 0.86)
- Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Sequential Games (ICLR 2024 · similarity 0.86)
- Do LLM Agents Have Regret? A Case Study in Online Learning and Games (ICLR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.