Stateless Mean-Field Games: A Framework for Independent Learning with Large Populations

We thank reviewer qCUR for their comments.

Question 1: (regarding dependence on $N$)

We emphasize that (Guo et al. 2019) pointed out by the reviewer and many others in mean-field game literature rely on a very strong oracle/assumption: their algorithms are centralized and can prescribe any behavior to an infinite population and observe the resulting dynamics while learning (as in a “population generative model”). In a more realistic setting, however, the population distribution will be induced by the behavior of learners interacting with the game over many rounds leading to complicated interactions. We consider the much more challenging and realistic setting where $N$ decentralized learners repeatedly play the game while locally observing interactions. Namely, unlike past work, our setting is:

• Finite-agent: learning occurs by playing the finite-agent game, not by centrally simulating an infinite player approximation,
• Independent/decentralized: agents can not communicate and their observations are local,
• Limited feedback: agents can only partially observe rewards leading to a more realistic learning model.

All in all, the setting of SMFG is much more challenging compared to many works in MFG literature. Our analysis incurs a dependence on $poly(N)$, however, we solve a more challenging and realistic learning problem.

We agree with the reviewer that the setting of multi-player MAB as in Lugosi et al., 2022 can not be directly compared to our setting: in fact, the collision model employed by Lugosi et al., 2022 and others in MMAB literature has a much more restrictive structure than our setting. The SMFG incorporates a wide range of complicated payoff functions (including the much simpler binary collision rewards) hence the SMFG problem is much more complicated than the MMAB setting. The reference to Lugosi et al., 2022 served as an analogy for how independent/decentralized learning can introduce a dependence on $N$ even for the much more restrictive setting of collision models.

Finally, while the scaling of the number of iterations to $\mathcal{O}(N^{3/2})$ is indeed a polynomial dependence in the decentralized learning with bandit feedback, it might not be prohibitively large for the large class of payoff functions considered under decentralized learning. The MFG approximation is introduced to tractably solve a difficult problem, but the decentralized learning model nevertheless can introduce a dependence on $N$. Once again, while not a directly comparable result, we point out for example the polynomial $\mathcal{O}(N^{12})$ dependence in the decentralized case for congestion games [5].

Question 2: (regarding non-vanishing bias term)

The bias term is standard for mean-field games [1,2,3] and can be considered as trading off a small amount of bias/exploitability (when $N$ is large) for a tractable approximate solution of an otherwise intractable problem. Our work can be seen as proof that this approximation can be performed without explicitly constructing the $N\rightarrow\infty$ approximate problem by a centralized algorithm but rather independently by participants of the real-world $N$-player game.

We also note that SMFG solves a different class of problems compared to congestion games or potential games as we show in Section B.2 that SMFG in general does not admit a potential structure. While in the highly structured and restrictive settings of potential games and two-player zero-sum games, it is possible to solve the problem exactly, even for symmetric games the task of finding exact NE can be computationally intractable [4].

Question 3: (regarding lower bounds)

Developing such lower bounds for multi-agent systems is an active topic of research; such results are sparse even for structured games such as potential games. One result we are aware of is https://arxiv.org/pdf/2303.12287.pdf which provides hardness results of independent learning for Markov games. More relevantly, the works https://arxiv.org/pdf/1511.00785.pdf and https://arxiv.org/pdf/1606.04550.pdf provably show a lower bound on the query complexity of computing $\varepsilon$-NE growing exponentially in the number of players $N$, demonstrating that the mean-field approximation of our SMFG framework for large is relevant. Such lower bound results for SMFG, while being of fundamental interest, are out of the scope of this paper.

References:

[1] Cui K, Koeppl H. Approximately solving mean field games via entropy-regularized deep reinforcement learning. AISTATS 2021

[2] Anahtarci B, Kariksiz CD, Saldi N. Q-learning in regularized mean-field games. Dynamic Games and Applications. 2023.

[3] Yardim B, Cayci S, Geist M, He N. Policy mirror ascent for efficient and independent learning in mean field games. ICML 2023.

[4] A Survey of PPAD-Completeness for Computing Nash Equilibria, Paul W. Goldberg, 2011

[5] Cui, et al. "Learning in congestion games with bandit feedback." NeurIPS 2022.

Thanks the authors for the detailed response.

For the concern regarding the dependence on $N$, it is not clear to me why the setting in Lugosi et al., 2022 has a much more restrictive structure. The reason is that they do not implement the mean-field approximation, and the number of arms in their setting grows as number of agents grows.

In the seminal work of Lasry and Lions (2007), the mean-field game is formulated to study a “continuum limit”. The previous works also achieve this goal by deriving learning bounds that are independent of the number of agents. I understand that the $poly(N)$ appears since the authors consider the independent learning setting. But I am not sure whether this comes from the suboptimality of the algorithm or the problem setting itself.

I will keep my scores at this stage due to these reasons.

We thank the reviewer for their response.

Comparison with Lugosi et al.:

Regarding the work of Lugosi et al., the reason we consider their model restrictive is due to the collision model. In their case, if multiple agents choose a particular arm $k$, the reward obtained is a constant zero, and if an agent alone plays the arm $k$, it obtains a constant reward $r_k$ associated with the arm. In fact, it’s easy to formulate an NE in the setting of Lugosi et al. in the centralized case: we can simply place the $N$ agents to the arms with the highest rewards. There is no need for a mean-field approximation to make the problem tractable, their game model is simple enough.

In our case, the reward map $\mathbf{F}$ is an unknown nonlinear function of action occupancies (see beginning of Section 2.1). For instance, the payoff of arm $k$ can arbitrarily depend on how many agents played another arm $k’$ as well as how many agents played $k$. Therefore our game model is much more complicated to solve, even in the centralized learning case it is a computational challenge to formulate an NE. The mean-field approximation makes our problem tractable.

Regarding MFG and the work of Lasry and Lions

Regarding the seminal work of Lasry and Lions and subsequent research in mean-field RL, we point out that past MFG works solve the continuum limit (the MFG) directly without consideration of the real-world $N$ player game. This is considerably easier.

In other words, there is no dependence on $N$ in past works because there is no concept of agents, rather they are simplified to a distribution $\mu$. In this regard past work is theoretically convenient but not realistic: in the real world, regardless of the mean-field approximation the game played is always an $N < \infty$ player game. This is precisely the contribution of our paper: we could solve MF-VI (page 6) directly easily to obtain a bound similar to past work without a notion of independent agents, but instead for the first time we prove that efficient independent learning with $N < \infty$ agents is possible.

We refer the reviewer to the table provided above to reviewer qRij for a comparison with the past line of work that has followed the seminal paper by Lasry and Lions.

Sublinear dependence on $N$

We would also like to point out that $N$ appears sublinearly in our bounds in Theorem 1 and 2, which is much more tractable compared to an arbitrary polynomial dependence. Even in games such as potential games or congestion games, a $poly(N)$ cost is incurred when solving the game, which we reference in our original response. The $\log N$ dependence of Lugosi et al. is possible in the much simple collision model for the rewards, but not in the case when the game has more complicated reward dynamics such as ours.

We thank reviewer qRij for their comments.

SMFG vs. congestion games:

As Appendix B.2 demonstrates, in general, SMFGs are not congestion (or more generally potential) games. While combinations of VI and no-regret dynamics are thoroughly analyzed in structured games such as potential games or for the subclass congestion games, for our class of symmetric games independent learning guarantees have been largely absent. Our work is thus more directly comparable to mean-field games literature.

One parallel can be drawn with non-atomic congestion games which also approximate the infinite-agent limit (Roughgarden et al., 2004), however, we are not aware of any algorithms in this setting where learning is performed by $N$ agents in a decentralized manner. One of the main contributions of the work is utilizing the infinite-player approximation to understand independent learning in the more realistic finite-player setting with explicit finite-sample and finite-agent bounds.

In case the reviewer has particular works for comparison with our setting, we would be happy to provide further differences.

Independent learning and no-regret dynamics:

While no-regret dynamics are analyzed to provide learning guarantees for various classes of games, they can in general cycle or fail to converge. Despite many centralized learning results with strong oracles (e.g. Perrin et al., 2020 and others mentioned in the paper), independent learning guarantees in MFG literature have so far been understudied. We fill the gap in MFG literature by showing that certain algorithms (combined with particular exploration strategies) can be used to approximately solve large-scale games without communication.

Finally, we note that due to the particular regularization induced by $\tau$, our algorithms are not direct adaptations of no-regret methods. Instead, a particular regularization term depending on population size is required for optimal rates. A similar case can be made for the bandit feedback case: to obtain optimal rates, a particular exploration probability $\varepsilon$ depending on $N$ must be used.

Summary of theoretical contributions in MFG literature:

We provide the table below to compare the theoretical results of our paper to existing work in mean-field games literature.

Dependence on $K$:

Finally, we thank the reviewer for pointing out the dependence on $K$ in our bounds. Since the primary focus of our complexity results is to establish the dependencies on the number of agents $N$ and the number of iterations $T$, we move the explicit dependency on $K$ to the appendix due to space considerations. We will make the dependence explicit in the main paper as the reviewer suggested.

References:

Parise F, Ozdaglar A. Graphon games: A statistical framework for network games and interventions[J]. Econometrica, 2023, 91(1): 191-225.

Cui K, Koeppl H. Approximately solving mean field games via entropy-regularized deep reinforcement learning. In International Conference on Artificial Intelligence and Statistics 2021 Mar 18 (pp. 1909-1917). PMLR.

Anahtarci B, Kariksiz CD, Saldi N. Q-learning in regularized mean-field games. Dynamic Games and Applications. 2023 Mar;13(1):89-117.

Perrin S, Pérolat J, Laurière M, Geist M, Elie R, Pietquin O. Fictitious play for mean field games: Continuous time analysis and applications. Advances in Neural Information Processing Systems. 2020;33:13199-213.

Guo X, Hu A, Xu R, Zhang J. Learning mean-field games. Advances in neural information processing systems. 2019;32.

Yardim B, Cayci S, Geist M, He N. Policy mirror ascent for efficient and independent learning in mean field games. In International Conference on Machine Learning 2023 Jul 3 (pp. 39722-39754). PMLR.

Perolat J, Perrin S, Elie R, Laurière M, Piliouras G, Geist M, Tuyls K, Pietquin O. Scaling up mean field games with online mirror descent. arXiv preprint arXiv:2103.00623. 2021 Feb 28.

Roughgarden, T., & Tardos, É. (2004). Bounding the inefficiency of equilibria in nonatomic congestion games. Games and economic behavior, 47(2), 389-403.

Thanks for the response! I appreciate the pointer to Appendix B.2---I understand that SMFGs are not exactly congestion games, but it does seem to be the case (based on B.2 and the author's response) that the only additional generality afforded by SMFGs is allowing for monotonically decreasing costs. Regarding no-regret dynamics, I'm not entirely sure what the authors mean by no-regret dynamics will tend to cycle---perhaps the authors are conflating no-regret dynamics with e.g. fictitious play or similar dynamics? That the regularization term depends on the number of players is not something unique to the algorithm of this paper: even in the usual no-regret dynamics, the regularization that one applies to each player also depends on population size, since regularization depends on the number of iterations that one needs to run game dynamics which itself depends on the number of players. I'm still concerned regarding the significance of the submission's results and maintain my score.

We thank reviewer rayu for their comments.

As the reviewer points out, our algorithms produce an approximate NE, however, this bias term is standard for mean-field games [1,2,3] and can be considered as trading off a small amount of bias/exploitability (when $N$ is large) for a tractable approximate solution of an otherwise intractable problem. In general, as $N$ gets large (as in many real-world problems) the bias will vanish as our bounds explicitly show.

Regarding the question of whether an exact NE can be computed, intractability results exist even in the case the reward function is exactly known and learning is not decentralized [4].

[1] Cui K, Koeppl H. Approximately solving mean field games via entropy-regularized deep reinforcement learning. AISTATS 2021

[2] Anahtarci B, Kariksiz CD, Saldi N. Q-learning in regularized mean-field games. Dynamic Games and Applications. 2023.

[3] Yardim B, Cayci S, Geist M, He N. Policy mirror ascent for efficient and independent learning in mean field games. ICML 2023.

[4] A Survey of PPAD-Completeness for Computing Nash Equilibria, Paul W. Goldberg, 2011