Observer Uncertainty of Learning in Games from a Covariance Perspective

We thank you for your careful reading and suggestions in improving the clarity of the paper. We will address your questions and we will be always open for further queries and discussion. Please see our itemized responses below:

Motivation of 'input uncertainty' and further implications for these cycling or divergent behaviors.

Please refer to the second point of the global respond for more discussion on the concept of input uncertainty. As it was shown in previous works, the dynamical behaviors of FTRL is complex, it can exhibit recurrence [1] and chaotic behaviors [2]. However, these properties only provide qualitative descriptions about the hardness of predicting the dynamics of these algorithms. The results in the current paper focus on the quantitative viewpoint, and demonstrates new characteristics of these dynamics, such as the tradeoff between cumulative strategies and payoff. For more discussion on significance, applications if needed see also our related response to Reviewer kXrY.

The role of cumulative strategies, relationships with convergence of the averaged strategies, and meaning of the covariance between cumulative strategies and payoffs.

Cumulative strategies have a nature game-theoretical explanation: they denote the historical frequencies of strategies used by a player, and they also provide a new coordinate system to describe the dynamics of the two players system. Cumulative strategies and payoffs are related by the identity $y_i(t) = y_i(0) + A^{(ij)} X_j(t)$, for $i,j = 1,2$, thus one player's cumulative strategies can determine another player's cumulative payoff (although the payoff matrix is unknown), this also explain why we can trace the behaviors of a two players system from the viewpoint of a single player.

We appreciate your suggestion to consider average strategies. Our results on the covariance of cumulative strategies can be used to derive corollaries about the average strategies using the relation $\text{Var}(X(t)/t) = \text{Var}(X(t))/t^2$. For example, in the alternating setting, Theorem 5.1 implies that when $AA^{\top}$ is non-singular, the variance of average strategies tends to $0$ at a rate of $O(1/t^2)$. In case $AA^{\top}$ is singular, the variance of average strategies tends towards a non-zero value, and this number can be determined through computational methods. This suggests that in such cases, the initial distribution will not concentrate as in non-singular cases.

The form of symplectic discretization.

Thank you for pointing this out, we have fixed this in the update manuscripts. The parts that were modified are marked by red color.

The result in Theorem 5.2 itself is less meaningful due to lake of amplification rates of the covariance.

In addition to providing a numerical lower bound, Theorem 5.2 also offers insight into the tradeoff phenomenon between the standard deviations of cumulative payoffs and strategies for more general regularizers. In the case of GDA, where the standard deviations can be calculated precisely, an example of such a tradeoff phenomenon is presented in figure (1) in the main paper. Note that the maximum points of the curve representing standard deviations of cumulative payoffs coincide with minimum points of the curve representing standard deviations of cumulative strategies, and vice versa. This insight cannot be obtained by analyzing the growth rate of standard deviations of cumulative payoffs and strategies independently since Theorem 5.1 only indicates that both curves are bounded.

Intuitions on the definition of the Hamiltonian function.

The Hamiltonian function used in the current paper comes from [3], and a similar non-canonical Hamiltonian system formulation (also known as a Possion system) for continuous time mirror descent algorithms is also presented in [4]. Theorem 5.1 of [3] demonstrates that the Hamiltonian function defined here is inherently connected to the Bregman divergence, which is a commonly used concepts in optimization, plus a an additional term determined by the regularizers and equilibrium of the game.

We thank you for your careful reading and suggestions in improving the clarity of the paper. We will address your questions and we will be always open for further queries and discussion. Please see our itemized responses below:

Motivation, significance of the results, and actual applications.

Please refer to the global respond for more explanation of the motivation.

For the significance : Game dynamics particularly based on zero-sum like game are seminal components in standard AI architectures such as GANS [1] (7000+ refs), PSRO [2] (600+ refs) and are actually useful even in n-player games (Diplomacy [3]) The typical way to control such dynamics so far has been to aim/hope for global convergence to equilibrium, however, there are many hurdles to this tasks both from a computational perspective [4,5] as well as from a dynamical systems perspective [6]. Here we aim at a different type of "stability" altogether. Stability/predictability of orbits without needing to converge to Nash as a necessary intermediary step from proving stability. By showing that this is possible we open the door for new multi-agent AI architectures that although maybe design around the pipe-dream of global convergence they can still be practically useful.

Actual applications: (Computer Poker). Poker is of course a standard benchmark for AI and a real world application. This direction of work could provide some insights behind the empirical success of CFR+ [7,8] in poker. CFR+ is a variant of Counter Factual Regret (CFR) minimization [9] with improved empirical performance. A key difference between CFR+ and vanilla CFR is switching from simultaneous updates to alternating updates. Our results provide some hints on why this could lead to increased performance. Increased orbit stability, reduced payoff variances due to symplectic-like discretization would lead to faster time average convergence to equilibrium and thus improved performance. Of course our current work is not on CFR and extensive form games but normal form games, nevertheless, we believe these are promising steps that provide a new vocabulary to study such real-world systems.

Minor stylistic issues :

Thank you for pointing out these issues. We have fixed these issues and updated the manuscript in the system. Footnotes are moved after punctuation marks, and the references have been unified in the (authors,year) format. Thank you again!

We hope these can address your concerns, and we are always open to future discussions.

References:

[1] Goodfellow, Ian, et al. "Generative adversarial networks." Communications of the ACM 63.11 (2020): 139-144.

[2] Lanctot, Marc, et al. "A unified game-theoretic approach to multiagent reinforcement learning." Advances in neural information processing systems 30 (2017).

[3] Meta Fundamental AI Research Diplomacy Team (FAIR)†, et al. "Human-level play in the game of Diplomacy by combining language models with strategic reasoning." Science 378.6624 (2022): 1067-1074.

[4] Daskalakis, Constantinos, et al. "The complexity of computing a Nash equilibrium." Communications of the ACM 52.2 (2009): 89-97.

[5] Daskalakis, Constantinos, et al. "The complexity of constrained min-max optimization." Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. 2021.

[6] Milionis, Jason, et al. "An impossibility theorem in game dynamics." Proceedings of the National Academy of Sciences 120.41 (2023): e2305349120.

[7] Oskari Tammelin. Solving large imperfect information games using cfr+. arXiv preprint arXiv:1407.5042, 2014

[8] Michael Bowling et al. Heads-up limit holdem poker is solved. Science, 347(6218):145–149, 2015.

[9] Martin Zinkevich et al. Regret minimization in games with incomplete information. In Advances in neural information processing systems, pages 1729–1736, 2008.

Thank you for your replying and interests to the application of our results. We have realized that the concern is about the specific application scenarios of our results. We guess the "gap" might refer to two possibilities, and we explain on both of them. If we have missed the point, please leave comments and we are happy to provide futher information.

1. If the gap means the model we consider and the applications mentioned, then the actual applications follows:

   First of all, we consider zero-sum games which is a model of multi-agent systems in AI, our results serves directly in any scenarios where zero-sum matrix games are involved.

   Secondly, in areas like GANs, theory of zero-sum games are studied as a simlified case to provide theoretical explanation to phenomenon from GANs (and other computer games), or provide theoretical guidence on algorithm designs.

   Thirdly, understanding algorithms in bilinear matrix games is a first and fundamental step towards general setting that actual captures models in real world. Recall that the standard approach on learning algorithms in min-max optimization is the following: $\text{zero-sum matrix game=>convex-concave game=>non-convex non-concave game},$ This is why we mentioned that current results have given promising steps on future works.

2. If the gap refers to the application of variance/covariance, we argue that The real-life application of variance/covariance is often tied with concentration inequalities. Let's take Chebyshev inequalities for example $Pr(|X>\mu|>k\sigma)<\frac{1}{k^2}.$ By results of Theorem 5.1, we know that $\text{Var}X^t_i$ is of $\Theta(t^2)$. Say $\text{Var}X^t_i=ct^2$ (the formulation of $\text{Var}X^t_i$ can be explicitly determined according to our analysis process in Appendix C.2.3, using the information provided by the payoff matrix and initial conditions), and then we have $\text{Pr}(|X^t_i-\mu|>k\sqrt{c}t)<\frac{1}{k^2}$ for any $k>1$. Therefore, we have concrete estimate of the probability for $X^t_i$ to deviate from the mean at Each Iterate, which captures the accuracy of prediction in each iterate. For the cumulative payoff $y^t_i$, the alternating play keeps variance bounded, i.e., $\text{Var}y^t_i=\mathbb{E}|y_i^t-\mu|^2\le c$ and this implies (using Markov inequality) $\text{Pr}(|y^t_i-\mu|>k)<\frac{c}{k^2},$ which also captures the accuracy of prediction of payoff, e.g., the probability of $y^t_i$ to be greater than $\mu+10$ or less than $\mu-10$ is less than $c/100$.

Thank you again for your feedback. Please let us know whether we have addressed the "actual application" concern or further clarifying is needed.

Dear reviewer kXrY,

Since the discussion time is coming to an end, may I ask if our response have solved your concerns? Please let us know if further clarifying is needed, and we are always open to provide additional discussion. If our answers have resolved your concerns, we would greatly appreciate it if you could consider updating your recommendation accordingly. Thank you again for your feedback !

Thank you for your supportive comments and interest to our work! We have added more discussions on related works, please see our global respond. We will be always open for further queries and discussion.

Thank you for your careful reading and suggestions in improving the clarity of the paper. We will clarify the issues in revision. Please see our itemized responses below:

This paper is not well-motivated.

Please refer to our global respond.

“I am also concerned…simple matrix calculations.”

We are trying to address this comment but we found the descriptions are too vague. It would be great if the reviewer can make the points specific so that we can address the concerns. To elaborate:

"The first 5 pages do not include new theory."

Yes, the first 5 pages are devoted to explaining the setting, motivation, and background material related to our work. Since we are combining ideas, tools and techniques from different fields such as online learning (e.g. GDA/MWU/AltMWU), game theory (strategies/zero-sum games), dynamical systems (Hamiltonians), information theory (differential entropy) and statistics (covariance), we clearly need some space to establish the necessary vocabulary for the reader. We believe that given the breadth of the ideas explored, we are actually using space rather efficiently. If the reviewer believes otherwise, we will be happy to hear some concrete suggestions about which parts are superfluous and should be cut out.

"Section 4 seems directly from Cheung et al. (2022)."

This is not true. Both the theoretical results and proof strategies of section 4 in the current paper are different from Cheung et al. (2022).

Firstly, Cheung et al. (2022) didn't consider how differential entropy evolve in the alternating play setting. In Proposition 4.2, we prove the differential entropy keeps constant in the alternating play setting, thus the concept of differential entropy can not capture the uncertainty evolution in the alternating play setting. This also motivate us to seek other measure of uncertainty evolution.

Secondly, the proof by Cheung et al. (2022) involves a complex calculation on the Jacobian of the multiplicative weights update algorithm, which is difficult to generalize to the alternating play setting due to its requirement for two strategies updating. Our proof of Proposition 4.2 simplifies this kind of calculation by establishing a connection between symplectic discretization and the alternating play setting (Proposition 3.1). Please refer to the discussion below Proposition 4.2 in the paper for more detailed explanations on the differences of the proof strategies.