  Learning the behavior of large agent populations is an important task for
numerous research areas. Although the field of multi-agent reinforcement
learning (MARL) has made significant progress towards solving these systems,
solutions for many agents often remain computationally infeasible and lack
theoretical guarantees. Mean Field Games (MFGs) address both of these issues
and can be extended to Graphon MFGs (GMFGs) to include network structures
between agents. Despite their merits, the real world applicability of GMFGs is
limited by the fact that graphons only capture dense graphs. Since most
empirically observed networks show some degree of sparsity, such as power law
graphs, the GMFG framework is insufficient for capturing these network
topologies. Thus, we introduce the novel concept of Graphex MFGs (GXMFGs) which
builds on the graph theoretical concept of graphexes. Graphexes are the
limiting objects to sparse graph sequences that also have other desirable
features such as the small world property. Learning equilibria in these games
is challenging due to the rich and sparse structure of the underlying graphs.
To tackle these challenges, we design a new learning algorithm tailored to the
GXMFG setup. This hybrid graphex learning approach leverages that the system
mainly consists of a highly connected core and a sparse periphery. After
defining the system and providing a theoretical analysis, we state our learning
approach and demonstrate its learning capabilities on both synthetic graphs and
real-world networks. This comparison shows that our GXMFG learning algorithm
successfully extends MFGs to a highly relevant class of hard, realistic
learning problems that are not accurately addressed by current MARL and MFG
methods.
