Prediction-Aware Learning in Multi-Agent Systems

We thank the reviewer for their very relevant remarks. We answer below to the points they raise.

“What is ARIMA in Line 130? I might have missed the definition.”

ARIMA 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.

[3] Hamilton, J. D. (2020). Time series analysis. Princeton university press.

“there is a typo in "is an interesting topics for future research" in Line 348.”

Thank you for pointing out this typo, we will correct it in the revised version of the text.

“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. [...].”

We 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.

Regarding [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].

As 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. Additionally, [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.

[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.

[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.

" [...] 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."

The 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.

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.

We thank the reviewer for their feedback. We reply to the points they raise below.

“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.”

We respectfully disagree with the characterization of our work as incremental. Our contributions go beyond standard derivations in several important ways.

First, 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.

Second, 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.

“The authors start the motivation interestingly with an example of predictions that are regression-based [...]”

We 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.

“[...] postponing the more challenging and interesting problem to future work. This work, despite strongly motivated examples, seems incomplete.”

While 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.

We thank the reviewer for their valuable feedback. We respond below to the weaknesses they indicate, and reply to their questions.

“The paper assumes bounded prediction errors, which may not always be realistic.”

We 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.

“Limited empirical evaluation [...]”

We 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.

[3] Wang et al., 2023. Robust Contextual Portfolio Optimization with Gaussian Mixture Models.

“Complexity of the proposed algorithm[...].” If 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.

“How does the performance of POWMU compare to other state-of-the-art algorithms in time-varying games?”

The 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.

[1] Zhang et al., 2022. No-regret learning in time-varying zero-sum games. [2] Anagnostides et al. 2023. On the convergence of no-regret learning dynamics in time-varying games.

Can the framework be extended to handle partial information or bandit feedback settings? We 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..

How sensitive is the algorithm to the quality of predictions,[...]

Propositions 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.

"Are there any specific real-world applications where this approach could provide significant improvements over existing methods?"

Our 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.

“How does the complexity of the proposed algorithm handled?”

We kindly refer the reviewer to the third point of our reply for this question.