Heterogeneity, Reinforcement Learning and Chaos in Population Games
Jakub Bielawski, Thiparat Chotibut, Fryderyk Falniowski, Michał Misiurewicz and Georgios Piliouras
Abstract
Traditional evolutionary game theory is a powerful tool for analyzing
the statistics of a large population participating in a game. However,
the behavior of the individual agents are based on simple memoryless
dynamics and this collective behavior is typically represented by a
single distribution encoding the frequency of the different actions
played deterministically by all the infinitesimal agents. In this
paper, we study a more general model that captures a large population
of agents of different types, each of them performing reinforcement
learning, leveraging memory of past actions' performance and
outputting unpredictable behavior. The state of the system is captured
not by a single discrete distribution but involves more complex
measures capturing all possible heterogeneous learning states of the
population of agents. We apply this advanced learning model in
congestion games, which are well known to admit an essentially unique
equilibrium solution. We showcase that our learning dynamics can
exhibit convergence to numerous asymmetric equilibrium states as well
as phase transitions to chaos. Remarkably, even in the chaotic regime,
precise predictions can be made about the system performance as the
time-average cost of all actions are shown to be equal to each other
and in fact agree with their values at equilibrium. Therefore, a
plethora of novel heterogeneous normative solutions are shown to be
dynamically emergent in population games.