PrELIN: Provably Efficient Local-Information Networked Multi-Agent Reinforcement Learning

Recently, there has been a surge of interest in decentralized learning approaches to tackle complex collaborative tasks in multi-agent systems. One of the most promising approaches is multi-agent reinforcement learning (MARL). Yet, as the number of agents becomes larger, the sample complexity in MARL increases exponentially, making scalability a fundamental issue. Networked MARL algorithms can address this issue by leveraging a communication network for information exchange between the agents. For homogeneous network MARL, previous research established a regret upper-bound √MH⁴SAT. Recent approaches rely on global knowledge about the structure of the communication network, which poses a serious limitation when it is not known or changes depending on the task. In this paper, we overcome this limitation by proposing a novel networked MARL algorithm with an upperconfidence bound (UCB) exploration strategy, called provably efficient local-information networked (PrELIN) MARL, that does not require any global information and relies only on the local interactions between the agents. Furthermore, we derive the regret and sample complexity for our algorithm and show that the regret bound remains sublinear.