TY - GEN

T1 - Reinforcement Learning in Non-Stationary Discrete-Time Linear-Quadratic Mean-Field Games

AU - Uz Zaman, Muhammad Aneeq

AU - Zhang, Kaiqing

AU - Miehling, Erik

AU - Basar, Tamer

N1 - Funding Information:
Research support in part by Grant FA9550-19-1-0353 from AFOSR, and in part by US Army Research Laboratory (ARL) Cooperative Agreement W911NF-17-2-0196.

PY - 2020/12/14

Y1 - 2020/12/14

N2 - In this paper, we study large population multiagent reinforcement learning (RL) in the context of discretetime linear-quadratic mean-field games (LQ-MFGs). Our setting differs from most existing work on RL for MFGs, in that we consider a non-stationary MFG over an infinite horizon. We propose an actor-critic algorithm to iteratively compute the mean-field equilibrium (MFE) of the LQ-MFG. There are two primary challenges: i) the non-stationarity of the MFG induces a linear-quadratic tracking problem, which requires solving a backwards-in-time (non-causal) equation that cannot be solved by standard (causal) RL algorithms; ii) Many RL algorithms assume that the states are sampled from the stationary distribution of a Markov chain (MC), that is, the chain is already mixed, an assumption that is not satisfied for real data sources. We first identify that the mean-field trajectory follows linear dynamics, allowing the problem to be reformulated as a linear quadratic Gaussian problem. Under this reformulation, we propose an actor-critic algorithm that allows samples to be drawn from an unmixed MC. Finite-sample convergence guarantees for the algorithm are then provided. To characterize the performance of our algorithm in multi-agent RL, we have developed an error bound with respect to the Nash equilibrium of the finite- population game.

AB - In this paper, we study large population multiagent reinforcement learning (RL) in the context of discretetime linear-quadratic mean-field games (LQ-MFGs). Our setting differs from most existing work on RL for MFGs, in that we consider a non-stationary MFG over an infinite horizon. We propose an actor-critic algorithm to iteratively compute the mean-field equilibrium (MFE) of the LQ-MFG. There are two primary challenges: i) the non-stationarity of the MFG induces a linear-quadratic tracking problem, which requires solving a backwards-in-time (non-causal) equation that cannot be solved by standard (causal) RL algorithms; ii) Many RL algorithms assume that the states are sampled from the stationary distribution of a Markov chain (MC), that is, the chain is already mixed, an assumption that is not satisfied for real data sources. We first identify that the mean-field trajectory follows linear dynamics, allowing the problem to be reformulated as a linear quadratic Gaussian problem. Under this reformulation, we propose an actor-critic algorithm that allows samples to be drawn from an unmixed MC. Finite-sample convergence guarantees for the algorithm are then provided. To characterize the performance of our algorithm in multi-agent RL, we have developed an error bound with respect to the Nash equilibrium of the finite- population game.

UR - http://www.scopus.com/inward/record.url?scp=85098272095&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85098272095&partnerID=8YFLogxK

U2 - 10.1109/CDC42340.2020.9304279

DO - 10.1109/CDC42340.2020.9304279

M3 - Conference contribution

AN - SCOPUS:85098272095

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 2278

EP - 2284

BT - 2020 59th IEEE Conference on Decision and Control, CDC 2020

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 59th IEEE Conference on Decision and Control, CDC 2020

Y2 - 14 December 2020 through 18 December 2020

ER -