2020/01/27 by Seyed Mohammad Asghari, Asghari, Seyed Mohammad, Yi Ouyang +3
Computer Science · Decision Sciences · Mathematics · #Adaptive Dynamic Programming Control #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Multiagent Systems (cs.MA) #Optimization and Control (math.OC) #Reinforcement Learning in Robotics #cs.LG #cs.MA #math.OC #stat.ML
paper · pdf · doi:10.48550/arxiv.2001.10122
arxiv created 2020/01/27 · openalex publication_date 2020/01/27 · arxiv updated 2020/01/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Regret analysis is challenging in Multi-Agent Reinforcement Learning (MARL) primarily due to the dynamical environments and the decentralized information among agents. We attempt to solve this challenge in the context of decentralized learning in multi-agent linear-quadratic (LQ) dynamical systems. We begin with a simple setup consisting of two agents and two dynamically decoupled stochastic linear systems, each system controlled by an agent. The systems are coupled through a quadratic cost function. When both systems' dynamics are unknown and there is no communication among the agents, we show that no learning policy can generate sub-linear in T regret, where T is the time horizon. When only one system's dynamics are unknown and there is one-directional communication from the agent controlling the unknown system to the other agent, we propose a MARL algorithm based on the construction of an auxiliary single-agent LQ problem. The auxiliary single-agent problem in the proposed MARL algorithm serves as an implicit coordination mechanism among the two learning agents. This allows the agents to achieve a regret within O(√(T)) of the regret of the auxiliary single-agent problem. Consequently, using existing results for single-agent LQ regret, our algorithm provides a O(√(T)) regret bound. (Here O(⋅) hides constants and logarithmic factors). Our numerical experiments indicate that this bound is matched in practice. From the two-agent problem, we extend our results to multi-agent LQ systems with certain communication patterns.