Multi-agent reinforcement learning for locally observable cooperative systems with acyclic dependence structure

Overview & Synopsis

Single-agent reinforcement learning algorithms can be directly applied to multi-agent systems in an independent learning approach, but often lose their convergence properties as the environment becomes non-stationary. We prove that in transition-independent Decentralized Markov Decision Process (TI Dec-MDP) non-stationarity can be mitigated by a multi-scale approach when the interdependence of agents' dynamics can be represented by a directed acyclic graph (DAG). Although TI Dec-MDPs are thought to be restrictive, we show that they can describe complex real world problems through a careful design of local states. We propose a multi-scale Q-learning algorithm (MQL) where agents update local Q-learning iterates at different timescales without communication and still converge. To this purpose, we first show that we can model the loss of information on the global state as a state-dependent Markovian noise. Then, we show that results from stochastic approximation theory can be used to prove the convergence of MQL under local state observability. We give practical solutions to exploit knowledge about agent interaction to assign learning rates that ensure convergence, and propose a NetworkMQL algorithm that can achieve convergence in Network-Distributed POMDP (ND-POMDP). We validate both MQL and NetworkMQL on a wind farm control problem.