Reinforcement Learning in Multi-Agent Systems with Partial History Sharing

In this paper, we are interested in systems with multiple agents that wish to cooperate in order to accomplish a common task while a) agents have different information (decentralized information) and b) agents do not know the complete model of the system i.e., they may only know the partial model or may not know the model at all. The agents must learn the optimal strategies by interacting with their environment i.e., by multi-agent Reinforcement Learning (RL). The presence of multiple agents with different information makes multi-agent (decentralized) reinforcement learning conceptually more difficult than single-agent (centralized) reinforcement learning. We propose a novel multi-agent reinforcement learning algorithm that learns ✏-team-optimal solution for systems with partial history sharing information structure, which encompasses a large class of multi-agent systems including delayed sharing, control sharing, mean field sharing, etc. Our approach consists of two main steps as follows: 1) the multi-agent (decentralized) system is converted to an equivalent single-agent (centralized) POMDP (Partial ObservableMarkov Decision Process) using the common information approach of Nayyar et al, TAC 2013, and 2) based on the obtained POMDP, an approximate RL algorithm is constructed using a novel methodology. Particularly, in the second step, since the POMDP obtained in the first step requires the complete-knowledge of system model, we introduce a new concept that we call “Incrementally Expanding Representation (IER)”. The main feature of IER is to remove the dependency o