Past Talks

Abstract: We consider a mean-field game model where the cost functions depend on a fixed parameter, called state, which is unknown to players. Players learn about the state from a a stream of private signals they receive throughout the game. We derive a mean field system satisfied by the equilibrium payoff of the game and prove existence of a solution under standard regularity assumptions. Additionally, we establish the uniqueness of the solution when the cost function satisfies the monotonicity assumption of Lasry and Lions at each state.

Abstract:  We provide a framework to analyse mean field control policies for the restless Markovian bandit model, under both finite and infinite time horizon. We show that when the population of arms goes to infinity, the value of the optimal control policy converges to the solution of a linear program (LP). We provide necessary and sufficient conditions for a generic control policy to be: i) asymptotically optimal; ii) asymptotically optimal with square root convergence rate; iii) asymptotically optimal with exponential rate. We then construct the LP-index policy that is asymptotically optimal with square root convergence rate on all models, and with exponential rate if the model is non-degenerate in finite horizon, and satisfies a uniform global attractor property in infinite horizon. We next define the LP-update policy, which is essentially a repeated LP-index policy that solves a new linear program at each decision epoch. We provide numerical experiments to compare the efficiency of LP-based policies. We also compare the performance of the LP-index policy and the LP-update policy with other heuristics. Our result demonstrates that the LP-update policy outperforms the LP-index policy in general. Joint work with Nicolas Gast and Chen Yan.

Abstract:  We study a new model of partially observed mean-field games with finitely many players, local action observability, and a general observation channel for partial observations of the global state. Specific observation channels considered include (a) global observability, (b) local and mean-field observability, (c) local and compressed mean-field observability, and (d) only local observability. We establish conditions under which the control problem of a given agent is equivalent to a fully observed MDP, as well as conditions under which the control problem is equivalent only to a POMDP. Building on the connection to MDPs, we prove the existence of perfect equilibrium among memoryless stationary policies under mean-field observability. Leveraging the connection to POMDPs, we prove convergence of so-called independent learning iterates under any of the aforementioned observation channels. We interpret the limiting values as subjective value functions, which an agent believes to be relevant to its control problem. These subjective value functions are then used to propose subjective Q-equilibrium, a new solution concept for partially observed n-player mean-field games, whose existence is proved under mean-field or global observability. If time permits, we will describe the convergence properties of a multi-agent reinforcement learning algorithm based on independent learning iterates, in which agents iteratively revise their policies and ultimately drive the joint policy process to subjective Q-equilibrium.

Abstract:  Mean-field reinforcement learning has become a popular theoretical framework for efficiently approximating large-scale multi-agent reinforcement learning (MARL) problems exhibiting symmetry. However, questions remain regarding the applicability of mean-field approximation: in particular, their approximation accuracy of real-world systems and conditions under which they become computationally tractable. We establish explicit finite-agent bounds for how well the MFG solution approximates the true $N$-player game for two popular mean-field solution concepts. We also present results charaterizing the robustness of MF-RL to violations of symmetry in the $N$-agent game. Furthermore, for the first time, we establish explicit lower bounds indicating that MFGs can be poor at approximating $N$-player games assuming only Lipschitz dynamics and rewards. Finally, we analyze the computational complexity of solving MFGs with only Lipschitz properties and prove that they are in the class of PPAD-complete problems conjectured to be intractable, similar to general sum $N$ player games. Our theoretical results complement and justify existing work by proving difficulty in the absence of common theoretical assumptions.

Abstract:  In this talk, we will discuss how we can utilize deep learning tools to solve complex (dynamic and stochastic) game theoretical problems where there are many agents interacting. We will first introduce a stochastic optimal control problem for one agent and explain how we can use neural networks to solve this problem. Later, we will go to the multi-agent setup, and we will discuss and compare two equilibrium notions in game theory: Nash equilibrium and Stackelberg equilibrium. After explaining how a Nash equilibrium can be approximated for dynamic and stochastic games for a large number of agents through mean field games, we will explain how neural networks can be utilized to find the Nash equilibrium. Finally, we will introduce the Stackelberg mean field game model between a principal (i.e., regulator) and a large number of agents to find optimal policies for large societies and discuss how the utilization of deep learning tools can be extended to solve this complex problem. (joint work w/ Mathieu Lauriere.)

Abstract: Mean Field Games (MFG) are those in which each agent assumes that the states of all others are drawn in an i.i.d. manner from a common belief distribution, and optimizes accordingly. The equilibrium concept here is a Mean Field Equilibrium (MFE), and algorithms for learning MFE in dynamic MFGs are unknown in general due to the non-stationary evolution of the belief distribution. Our focus is on an important subclass that possesses a monotonicity property called Strategic Complementarities (MFG-SC). We introduce a natural refinement to the equilibrium concept that we call Trembling-Hand-Perfect MFE (T-MFE), which allows agents to employ a measure of randomization while accounting for the impact of such randomization on their payoffs. We propose a simple algorithm for computing T-MFE under a known model. We introduce both a model-free and a model based approach to learning T-MFE under unknown transition probabilities, using the trembling-hand idea of enabling exploration. We analyze the sample complexity of both algorithms. We also develop a scheme on concurrently sampling the system with a large number of agents that negates the need for a simulator, even though the model is non-stationary. Finally, we empirically evaluate the performance of the proposed algorithms via examples motivated by real-world applications. This is joint work with Kiyeob Lee, Srinivas Shakkottai, and Dileep Kalathil.

Abstract:  We demonstrate the versatility of mean-field games (MFGs) as a mathematical framework for explaining, enhancing, and designing generative models. We establish connections between MFGs and major classes of flow and diffusion-based generative models by deriving continuous-time normalizing flows, score-based models, and Wasserstein gradient flows through different choices of particle dynamics and cost functions. Furthermore, we study the mathematical structure and properties of each generative model by examining their associated MFG's optimality condition, which consist of a set of coupled forward-backward nonlinear partial differential equations. The optimality conditions of MFGs also allow us to introduce HJB regularizers for enhanced training of a broad class of generative models. We present this framework as an MFG laboratory which serves as a platform for revealing new avenues of experimentation and invention of generative models.

Abstract:  This talk will present our recent work that introduces networked communication to the mean-field game framework. In particular, we look at oracle-free settings where N decentralised agents learn along a single, non-episodic evolution path of the empirical system, such as we may encounter for a large range of many-agent problems in the real-world. For comparison purposes with our new architecture, we have modified recent theoretical algorithms for the centralised and independent cases to make their practical convergence feasible. While contributing the first empirical demonstrations of these algorithms, we additionally demonstrate that our decentralised communication architecture brings benefits over both of the alternatives in terms of robustness to unexpected learning failures and changes in population size. We also show that our networked method can give faster convergence than the purely independent-learning case, while removing the reliance on a centralised controller, and will discuss various modifications and extensions to this early work which we are considering to leverage the advantages of our paradigm even further. 

Abstract:  Learning in multi-agent systems is highly challenging due to several factors including the non-stationarity introduced by agents' interactions and the combinatorial nature of their state and action spaces. In particular, we consider the Mean-Field Control (MFC) problem which assumes an asymptotically infinite population of identical agents that aim to collaboratively maximize the collective reward. In many cases, solutions of an MFC problem are good approximations for large systems, hence, efficient learning for MFC is valuable for the analogous discrete agent setting with many agents. Specifically, we focus on the case of unknown system dynamics where the goal is to simultaneously optimize for the rewards and learn from experience. We propose an efficient model-based reinforcement learning algorithm, M3-UCRL, that runs in episodes, balances between exploration and exploitation during policy learning, and provably solves this problem. Our main theoretical contributions are the first general regret bounds for model-based reinforcement learning for MFC, obtained via a novel mean-field type analysis. To learn the system’s dynamics, M3-UCRL can be instantiated with various statistical models, e.g., neural networks or Gaussian Processes. Moreover, we provide a practical parametrization of the core optimization problem that facilitates gradient-based optimization techniques when combined with differentiable dynamics approximation methods such as neural networks.

Abstract: Perhaps the most challenging aspect of research on multi-agent dynamical systems, formulated as non-cooperative stochastic differential/dynamic games (SDGs) with asymmetric dynamic information structures is the presence of strategic interactions among agents, with each one developing beliefs on others in the absence of shared information. This belief generation process involves what is known as second-guessing phenomenon, which generally entails infinite recursions, thus compounding the difficulty of obtaining (and arriving at) an equilibrium. This difficulty is somewhat alleviated when there is a high population of agents (players), in which case strategic interactions at the level of each agent become much less pronounced. With some structural specifications, this leads to what is known as mean field games (MFGs), which have been the subject of intense research activity during the last fifteen years or so.

This talk will provide a general overview of fundamentals of MFGs approach to decision making in multi-agent dynamical systems, discuss connections to finite-population games and how robustness features can be built into the solution process. It will also introduce, and discuss convergence and sample complexity of, selected learning algorithms for some specific model-free settings.

Abstract: Policy iteration is an effective algorithm for solving Hamilton Jacobi Bellman equations, discretized with monotone upwind schemes. One difficulty of understanding convergence of policy iteration for Mean Field Games is the lack of monotone improvement property of policy updates, due to the interactions between agents. We show that policy iteration has a linear rate of convergence if the time horizon T (or the intensity of interactions) is small, using contraction fixed point method. The same methods can be applied to MFGs with non-separable Hamiltonians.

We then introduce Smoothed Policy Iteration algorithms for potential Mean Field Games. The main idea is using some forms of weighted average policies for generating densities, in order to penalize deviation from the previous step and stabilize the learning procedures. This methodology is reminiscent of many ideas from machine learning literature, such as TRPO and online mirror descent. We show global convergence (starting from any initial guesses) if the system has a unique solution. Local convergence (starting from a close guess) to a stable solution can be shown if the system has multiple solutions. The convergence analysis is based on techniques previously used for fictitious play algorithms in the literature.

Abstract: In this talk, we study the problem of finding an approximate Nash equilibrium for regularized finite player games with symmetric and anonymous agents. Instead of working with the best-response operator as in most literature,  we first show that a policy mirror ascent map can be used to construct a contractive operator having the Nash equilibrium as its fixed point. We will introduce an efficient algorithm based on Policy Mirror Ascent that uses only a single sample trajectory without requiring any population generative model and allows for independent learning by the agents.  We further provide finite sample guarantees for both the centralized and independent learning settings.   This is joint work with Batuhan Yardim (ETH Zurich), Semih Cayci (RWTH Aachen), Matthieu Geist (Google Brain).

Abstract: In this talk, we will examine the long-run behavior of a wide range of dynamics for learning in nonatomic games, in both discrete and continuous time. The class of dynamics under consideration includes fictitious play and its regularized variants, the best-reply dynamics (again, possibly regularized), as well as the dynamics of dual averaging / “follow the regularized leader” (which in turn includes as special cases the replicator dynamics and Friedman’s projection dynamics). Our analysis concerns both the actual trajectory of play and its time-average, and will cover potential and monotone games, as well as games with an evolutionarily stable state (global or otherwise). We will focus on games with finite action spaces, but with an eye toward extending our results to nonatomic games with continuous action spaces - such as mean-field games.

Abstract: We present a simulation-based approach for solution of mean field games (MFGs), using the framework of empirical game-theoretical analysis (EGTA). Our primary method employs a version of the double oracle, iteratively adding strategies based on best response to the equilibrium of the empirical MFG among strategies considered so far. We present Fictitious Play (FP) and Replicator Dynamics as two subroutines for computing the empirical game equilibrium. Each subroutine is implemented with a query-based method rather than maintaining an explicit payoff matrix as in typical EGTA methods due to a representation issue we highlight for MFGs. By introducing game model learning and regularization, we significantly improve the sample efficiency of the primary method without sacrificing the overall learning performance. Theoretically, we prove that a Nash equilibrium (NE) exists in the empirical MFG and show the convergence of iterative EGTA to NE of the full MFG with either subroutine. We test the performance of iterative EGTA in various games and show that it outperforms directly applying FP to MFGs in terms of iterations of strategy introduction.

Abstract: Our recent works on the regularized mean field optimization aim at providing a theoretical foundation for analyzing the efficiency of the training of neural networks, as well as inspiring new training algorithms. In this talk we shall see how different regularizers, such as relative entropy and Fisher information, lead to different gradient flows on the space of probability measures.  Besides the gradient flows, we also propose and study an alternative algorithm, namely the entropic fictitious play, to search for the optimal weights of neural networks. Each of these algorithms is ensured to have exponential convergence, and we shall highlight their advantages. 

Abstract: Goal-based agents respond to environments and adjust behaviour accordingly to reach objectives. Understanding incentives of interacting agents from observed behaviour is a core problem in multi-agent systems. Inverse reinforcement learning (IRL) provides a solution to this problem, which infers underlying reward functions by observing the behaviours of rational agents. Despite IRL being principled, it becomes intractable when the number of agents grows because of the curse of dimensionality and the explosion of interactions among agents. The formalism of Mean field games (MFGs) has gained momentum as a mathematically tractable paradigm for studying large-scale multi-agent systems. It is thereby promising to push the limits of the agent number in IRL if we can ground IRL in MFGs. In this talk, I will show how to conquer the problem of many-agent IRL using mean-field games as the framework. Specifically, I will introduce two IRL methods for mean-field games: the first shows that an MFG cannot be reduced to a Markov decision process in general; it formalises the problem of IRL for MFGs and proposes the first solution framework to it. The second is based on the probabilistic inference that can further reason about uncertainties in agent behaviours. I will close the talk with an introduction to applications of IRL for mean-field games.

Abstract: One can conceive the term "mean field" as a physics concept that attempts to describe the effect of an infinite number of particles on the motion of a single particle. This concept has seen widespread use in population dynamics and evolutionary game theory, and researchers began to apply it to the social sciences in the early 1960s to study the way in which an infinite number of factors affect individual decisions. However, the key ingredient in a game-theoretic context is the influence of the distribution of states and/or control actions on decision-makers’ performance criteria; there is no need for a large population of decision-makers.

Mean-field-type game (MFTG) theory  studies interactions between two or more entities, which may include people, animals, devices, machines, companies, nations, networks, genes, populations, and so on. Decision-makers in MFTG theory can be atomic, non-atomic, or a mixture of both. MFTG interactions can be fully cooperative, partially altruistic, partially cooperative, selfish, selfless, co-opetitive, spiteful, or a mixture of these types. The key extension feature of MFTG theory is the integration of higher-order performance criteria like variance, quantile, and other risk-measures; such integration is not necessarily linear in the measure of the state or state action. MFTG has found applications in a variety of scenarios, including the evacuation of high-level buildings, smart energy systems, next-generation wireless networks, meta-learning in communication networks, smart transportation systems, epidemiology, predictive maintenance, marriage, and blockchains. 

Data-driven MFTG theory aims to incorporate certain data sets and real measurements into MFTG settings in a closed-loop fashion. Researchers use the measured data to learn and extract additional useful information from the field that the model then takes into consideration. One can thus utilize the model to study emerging dynamics and features and conduct new measurements, intervention measures, and actions. Scientists have developed mean-field-type filters, mean-field-type forecasting, and risk-aware filtering and forecasting based on MFTG theory; they apply these techniques to smart water, energy & transportation systems. In this talk, we revisit foundations of data-driven MFTG.

Bio:  Hamidou Tembine is the co-founder and co-chair of Timadie.

He graduated in Applied Mathematics from Ecole Polytechnique (Palaiseau, France) and received the Ph.D. degree from INRIA and University of Avignon, France. He further received the Master degree in game theory and economics. His main research interests are learning, evolution, and games. In 2014, Dr. Tembine received the IEEE ComSoc Outstanding Young Researcher Award for his promising research activities for the benefit of the society. He was the recipient of 10+ best paper awards in the applications of game theory. Dr. Tembine is a prolific researcher and holds 300+ scientific publications including magazines, letters, journals and conferences. He is author of the book on “distributed strategic learning for engineers “ (CRC Press, Taylor & Francis 2012) which received book award 2014, and co-author of the book “Game Theory and Learning in Wireless Networks” (Elsevier Academic Press) and co-author of the book on "Mean-Field-Type Games for Engineers". Dr. Tembine has been co-organizer of several scientific meetings on game theory in water, food, environment, networking, wireless communications and smart energy systems. He has been TPC member and reviewer for several international journals and conferences. He has been a visiting researcher at University of California at Berkeley (US), University of McGill (Montreal, Quebec, Canada), University of Illinois at Urbana-Champaign (UIUC, US), Ecole Polytechnique Federale de Lausanne (EPFL, Switzerland) and University of Wisconsin (Madison, US). He has been a Simons Participant and a Senior Fellow 2020. He is a senior member of IEEE. He is a Next Einstein Fellow, Class of 2017.

Abstract: Cluster analysis is a classical problem in unsupervised Machine Learning concerning the repartition of a group of  points into subgroups, in such a way that the elements within a same group are more similar to each other than they are to the elements of a different one. Most of the mathematical literature on cluster analysis, and more in general on Machine Learning, is in the framework of the finite-dimensional optimization.  In this talk, I will present  a multi-population Mean Field Games systems which can be interpreted as  an infinite-dimensional version of the classical Expectation-Maximization algorithm in soft clustering. I will discuss the theoretical aspects of the method and  the  application to some problems in cluster analysis. 

Abstract: As this era’s biggest game-changer, autonomous vehicles (AV) are expected to exhibit new driving and travel behaviors, thanks to their sensing, communication, and computational capabilities. However, a majority of studies assume AVs are essentially human drivers but react faster, “see” farther, and “know” the road environment better. We believe AVs’ most disruptive characteristic lies in its intelligent goal-seeking and adapting behavior. Building on this understanding, we propose a dynamic game based control leveraging the notion of mean-field games (MFG). I will first introduce how MFG can be applied to the decision-making process of a large number of AVs. To illustrate the potential advantage that AVs may bring to stabilize traffic, I will then introduce a multi-class game where AVs are modeled as intelligent game-players and HVs are modeled using a classical non-equilibrium traffic flow model. Last but not the least, I will talk about how the MFG-based control is generalized to road networks, in which the optimal controls of both velocity and route choice need to be solved for AVs, by resorting to nonlinear complementarity problems.

Abstract: The premise of our talk will be the fact that ants are believed to find shortest paths between their nest and sources of food by successive random explorations of their environment, without any means of communication other than the pheromones they leave behind them.

We will discuss a work in collaboration with Cécile Mailler and Bruno Schapira in which we introduce a general probabilistic model for this phenomenon, based on reinforcement-learning. We will present various variants of the model, with slightly different reinforcement mechanisms, and show that these small differences in the rules yield significantly different large-time behaviors. In the version called the loop-erased ant process, we are able to prove that the ants manage to find the shortest paths on all series-parallel graphs.

Abstract: Mean field theory provides an effective way of scaling multiagent reinforcement learning (RL) algorithms to environments with many agents that can be abstracted by a virtual mean agent. However, existing mean field RL techniques assume a single type for all agents, complete observability of the action distribution of all agents and centralized learning.  In this talk, I will describe extensions of mean field multiagent RL to partially observable domains, agents of multiple types and agents that learn independently of each other in a decentralized fashion.

Abstract: Stochastic differential games are notorious for their tractability barrier in computing Nash equilibria (social optima) in the competitive (resp. cooperative) framework.  The work presented in this talk aims to overcome this limitation by merging mean field theory, reinforcement learning and multi-scale stochastic approximation.

In recent years, the question of learning in MFG and MFC has garnered interest, both as a way to compute solutions and as a way to model how large populations of learners converge to an equilibrium. Of particular interest is the setting where the agents do not know the model, which leads to the development of reinforcement learning (RL) methods.

In the first part of the talk, we introduce a new definition of asymptotic mean field games and mean field control problems which naturally connects with the RL framework. We unify these problems through a two-timescale approach and develop a Q-learning based solving scheme in the case of finite spaces. Our first proposed algorithm learns either the MFG or the MFC solution depending on the choice of parameters. To illustrate this method, an application to an infinite horizon linear quadratic example is analyzed. Converge results are discussed based on stochastic approximation theory.

In the second part of the talk, we discuss an extension of this approach to finite horizon and extended mean field problems, where the mean field interaction is through the state/control joint distribution of the population. Our second algorithm is tested on two examples from economics/finance: a mean field problem of accumulated consumption with HARA utility function, and a trader’s optimal liquidation problem. The heterogeneity of the chosen examples shows the flexibility of our approach.

The talk concludes by presenting the preliminary results of our on-going work on solving problems in continuous spaces. We present our Unified 3-scale Actor Critic algorithm based on three learning rules. The first two are related to the optimal strategy (the actor) and the value function (the critic). An additional learning rule is adopted to target the distribution of the population at equilibrium. This method is tested on two examples of the infinite horizon type.

Abstract: Scalability of reinforcement learning algorithms to multi-agent systems is a significant bottleneck to their practical use. In this paper, we approach multi-agent reinforcement learning from a mean-field game perspective, where the number of agents tends to infinity. Our analysis focuses on the structured setting of systems with linear dynamics and quadratic costs, named linear-quadratic mean-field games, evolving over a discrete-time infinite horizon where agents are assumed to be partitioned into finitely-many populations connected by a network of known structure. The functional forms of the agents' costs and dynamics are assumed to be the same within populations, but differ between populations. We first characterize the equilibrium of the mean-field game which further prescribes an $\epsilon$-Nash equilibrium for the finite population game. Our main focus is on the design of a learning algorithm, based on zero-order stochastic optimization, for computing mean-field equilibria. The algorithm exploits the affine structure of both the equilibrium controller and equilibrium mean-field trajectory by decomposing the learning task into first learning the linear terms, and then learning the affine terms. We present a convergence proof and a finite-sample bound quantifying the estimation error as a function of the number of samples.

Abstract: In this talk, we first propose a new class of metrics and show that under such metrics, the convergence of empirical measures in high dimensions is free of the curse of dimensionality, in contrast to Wasserstein distance. Proposed metrics originate from the maximum mean discrepancy, which we generalize by proposing criteria for test function spaces. Examples include RKHS, Barron space, and flow-induced function spaces. One application studies the construction of Nash equilibrium for the homogeneous n-player game by its mean-field limit (mean-field game). Then we discuss mean-field games with common noise and propose a deep learning algorithm based on fictitious play and signatures in rough path theory. The first part of the work collaborates with Jiequn Han and Jihao Long; the second part is the joint work with Ming Min.

Abstract: Machine learning (ML) is a promising enabler for the fifth generation (5G) communication systems and beyond. By imbuing intelligence into the network edge, edge nodes can proactively carry out decision-making, and thereby react to local environmental changes and disturbances while experiencing zero communication latency. To achieve this goal, it is essential to cater for high ML inference accuracy at scale under time-varying channel and network dynamics, by continuously exchanging fresh data and ML model updates in a distributed way. Taming this new kind of data traffic boils down to improving the communication efficiency of distributed learning by optimizing communication payload types, transmission techniques, and scheduling, as well as ML architectures, algorithms, and data processing methods. This talk aims to provide a holistic overview of relevant communication and ML principles, and thereby present communication-efficient and distributed learning frameworks with selected use cases.

Abstract: In this talk, we consider learning approximate Nash equilibria for discrete-time mean-field games with nonlinear stochastic state dynamics subject to both average and discounted costs. To this end, we introduce a mean-field equilibrium (MFE) operator, whose fixed point is a mean-field equilibrium (i.e. equilibrium in the infinite population limit). We first prove that this operator is a contraction, and propose a learning algorithm to compute an approximate mean-field equilibrium by approximating the MFE operator with a random one. Moreover, using the contraction property of the MFE operator, we establish the error analysis of the proposed learning algorithm. We then show that the learned mean-field equilibrium constitutes an approximate Nash equilibrium for finite-agent games.

Abstract: The goal of this work is to demonstrate that common noise may serve as an exploration noise for learning the solution of a mean field game. This concept is here exemplified through a toy linear-quadratic model, for which a suitable form of common noise has already been proven to restore existence and uniqueness. We here go one step further and prove that the same form of common noise may force the convergence of the learning algorithm called ‘fictitious play’, and this without any further potential or monotone structure. Several numerical examples are provided in order to support our theoretical analysis. Joint work with A. Vasileiadis (Nice). 

Abstract: Mean field games facilitate an otherwise intractable computation of approximate Nash equilibria in many-agent settings. In this talk, we begin by considering discrete-time finite MFGs subject to finite-horizon objectives. We show that all non-trivial discrete-time finite MFGs fail to be contractive as commonly assumed in existing MFG literature, barring convergence via fixed point iteration. Instead, we incorporate entropy-regularization and softmax policies into the fixed point iteration. As a result, we obtain provable convergence to approximate fixed points where existing methods fail, and reach the original goal of approximate Nash equilibria. All proposed methods are evaluated with respect to their exploitability, on both instructive examples with tractable exact solutions and a high-dimensional problem where exact methods become intractable. In the second half of the talk, we consider a generalization of the considered MFGs to MFGs on dense graphs, the so-called graphon mean field games (GMFG). On the theoretical side, we rigorously show existence of solutions in the limiting system as well as the approximate Nash property in large, finite graph systems. On the practical side, we provide learning algorithms by discretization with error analysis, as well as by viewing the GMFG as a classical MFG.

Abstract: Multi-agent reinforcement learning has made significant progress in recent years, but it remains a hard problem. One often resorts to developing learning algorithms for specific classes of multi-agent systems. In this talk, we present reinforcement learning in a specific class of multi-agent systems systems called mean-field games. In particular, we consider learning in stationary mean-field games. We identify two different solution concepts---stationary mean-field equilibrium and stationary mean-field social-welfare optimal policy---for such games based on whether the agents are non-cooperative or cooperative, respectively. We then generalize these solution concepts to their local variants using bounded rationality based arguments. For these two local solution concepts, we present two reinforcement learning algorithms. We show that the algorithms converge to the right solution under mild technical conditions and demonstrate this using numerical examples.

Abstract: Games with many players have found numerous applications from macroeconomics and finance to crowd motion and swarm systems. However, solving such games remains very challenging when the number of players is extremely large. Mean Field Games (MFGs) have been introduced to allow the size of the population to grow to infinity by relying on a mean-field approximation. Traditional methods for solving these games are generally based on partial or stochastic differential equations with a full knowledge of the model. Recently, Reinforcement Learning (RL) is being used as an approach to tackle such games in a model-free fashion. The combination of MFGs and RL seems promising to address the curse of dimensionality in terms of both the population size and the environment size. In this talk, we review the literature on MFGs and learning algorithms for Nash equilibria or social optima. In particular, we present usual MFG settings, classical optimization algorithms and various RL methods. We illustrate these approaches with several numerical experiments.

Abstract: Multi-agent reinforcement learning (MARL) has enjoyed substantial successes for analyzing the otherwise challenging games, including two-agent computer games,  self-driving vehicles, real-time bidding games, ride-sharing, and traffic routing.  Despite its empirical success,  sample complexity for MARL by existing algorithms for stochastic dynamics grows exponentially with respect to the number of agents N, which in practice can be on the order of thousands or more, for instance, for Uber-pool and network routing for Zoom.

Mean-field approximation approach for MARL has shown to be promising for resolving the curse of the dimensionality issue of MARL, and is one of the most active areas for reinforcement learning. In this talk, I will first provide an overview of recent progress in the mean-field approach to MARL. I will then discuss our latest work for MARL with network structures and its convergence and sample complexity analysis.