2019

Learning Mean-Field Games

Guo, Xin, Hu, Anran, Xu, Renyuan et al.

Understand

This paper presents a general mean-field game (GMFG) framework for simultaneous learning and decision-making in stochastic games with a large population.

It first establishes the existence of a unique Nash Equilibrium to this GMFG, and explains that naively combining Q-learning with the fixed-point approach in classical MFGs yields unstable algorithms.
It then proposes a Q-learning algorithm with Boltzmann policy (GMF-Q), with analysis of convergence property and computational complexity.
The experiments on repeated Ad auction problems demonstrate that this GMF-Q algorithm is efficient and robust in terms of convergence and learning accuracy.

Built on

Multi-agent reinforcement learning: independent vs. cooperative agents
M. Tan · 1993
Earlier work this paper cites.
On choosing and bounding probability metrics
A. L. Gibbs and F. E. Su · 2002
Earlier work this paper cites.
Learning rates for Q-learning
E. Even-Dar and Y. Mansour · 2003
Earlier work this paper cites.
Nash Q-learning for general-sum stochastic games
J. Hu and M. P. Wellman · 2003
Earlier work this paper cites.
Computing equilibria in multi-player games
C. H. Papadimitriou and T. Roughgarden · 2005
Earlier work this paper cites.
Large population stochastic dynamic games: closed-loop McKean-Vlasov systems and the Nash certainty equivalence principle
M. Huang, R. P. Malhamé, and P. E. Caines · 2006
Earlier work this paper cites.
Mean field games
J-M. Lasry and P-L. Lions · 2007
Earlier work this paper cites.
A class of mean field interaction models for computer and communication systems
M. Benaim and J. Y. Le Boudec · 2008
Earlier work this paper cites.
Separability and completeness for the Wasserstein distance
F. Bolley · 2008
Earlier work this paper cites.
Optimal transport: old and new
C. Villani · 2008
Earlier work this paper cites.
Discrete time, finite state space mean field games
D. A. Gomes, J. Mohr, and R. R. Souza · 2010
Earlier work this paper cites.
Mean field equilibria of dynamic auctions with learning
K. Iyer, R. Johari, and M. Sundararajan · 2011
Earlier work this paper cites.
Repeated auctions under budget constraints: Optimal bidding strategies and equilibria
R. Gummadi, P. Key, and A. Proutiere · 2012
Earlier work this paper cites.
Mean field stochastic adaptive control
A. C Kizilkale and P. E Caines · 2013
Earlier work this paper cites.

Similar

Learning in mean-field games
H. Yin, P. G. Mehta, S. P. Meyn, and U. V. Shanbhag · 2013
Cited alongside, same era.
Analysis of game bot’s behavioral characteristics in social interaction networks of MMORPG
S. H. Jeong, A. R. Kang, and H. K. Kim · 2015
Cited alongside, same era.
Discrete time mean field games: The short-stage limit
J. P. M. López · 2015
Cited alongside, same era.
Increasing the action gap: new operators for reinforcement learning
M. G. Bellemare, G. Ostrovski, A. Guez, P. S. Thomas, and R. Munos · 2016
Cited alongside, same era.
The sharing economy: Why people participate in collaborative consumption
J. Hamari, M. Sjöklint, and A. Ukkonen · 2016
Cited alongside, same era.
Asynchronous methods for deep reinforcement learning
V. M. Minh, A. P. Badia, M. Mirza, A. Graves, T. P. Lillicrap, T. Harley, D. Silver, and K. Kavukcuoglu · 2016
Cited alongside, same era.
Learning Nash equilibrium for general-sum Markov games from batch data
J. Pérolat, F. Strub, B. Piot, and O. Pietquin · 2016
Cited alongside, same era.
An alternative softmax operator for reinforcement learning
K. Asadi and M. L. Littman · 2017
Cited alongside, same era.
Real-time bidding by reinforcement learning in display advertising
H. Cai, K. Ren, W. Zhang, K. Malialis, J. Wang, Y. Yu, and D. Guo · 2017
Cited alongside, same era.
On the properties of the softmax function with application in game theory and reinforcement learning
B. Gao and L. Pavel · 2017
Cited alongside, same era.
Reinforcement learning with deep energy-based policies
T. Haarnoja, H. Tang, P. Abbeel, and S. Levine · 2017
Cited alongside, same era.
Mean field stochastic games with binary action spaces and monotone costs
M. Huang and Y. Ma · 2017
Cited alongside, same era.

Then

Is multiagent deep reinforcement learning the answer or the question? A brief survey
P. Hernandez-Leal, B. Kartal, and M. E. Taylor · 2018
Later among the works it cites.
Real-time bidding with multi-agent reinforcement learning in display advertising
J. Jin, C. Song, H. Li, K. Gai, J. Wang, and W. Zhang · 2018
Later among the works it cites.
Multi-agent reinforcement learning: A report on challenges and approaches
S. Kapoor · 2018
Later among the works it cites.
Decentralised learning in systems with many, many strategic agents
D. Mguni, J. Jennings, and E. M. de Cote · 2018
Later among the works it cites.
Actor-critic fictitious play in simultaneous move multistage games
J. Pérolat, B. Piot, and O. Pietquin · 2018
Later among the works it cites.
A tour of reinforcement learning: The view from continuous control
B. Recht · 2018
Later among the works it cites.
Markov–Nash equilibria in mean-field games with discounted cost
N. Saldi, T. Basar, and M. Raginsky · 2018
Later among the works it cites.
Reinforcement learning: An introduction
R. S. Sutton and A. G. Barto · 2018
Later among the works it cites.
Multi-agent reinforcement learning via double averaging primal-dual optimization
H. T. Wai, Z. Yang, Z. Wang, and M. Hong · 2018
Later among the works it cites.
Mean field multi-agent reinforcement learning
Y. Yang, R. Luo, M. Li, M. Zhou, W. Zhang, and J. Wang · 2018
Later among the works it cites.
A mean field game of portfolio trading and its consequences on perceived correlations
C-A. Lehalle and C. Mouzouni · 2019
Closest in time.
Computational optimal transport
G. Peyré and M. Cuturi · 2019
Closest in time.
Reinforcement learning in stationary mean-field games
J. Subramanian and A. Mahajan · 2019
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…