# Regret Bounds for Decentralized Learning in Cooperative Multi-Agent Dynamical Systems

arXiv: https://arxiv.org/abs/2001.10122 · HTML: https://mlsanity.com/paper/2001.10122/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jan 2020.

## Built on by (most cited first, 4 of 4)

- [Provably Efficient Multi-Agent Reinforcement Learning with Fully Decentralized Communication](https://mlsanity.com/paper/2110.07392/) (2021)
- [QC-ODKLA: Quantized and Communication-Censored Online Decentralized Kernel Learning via Linearized ADMM](https://mlsanity.com/paper/2208.02777/) (2022)
- [Reinforcement Learning Policies in Continuous-Time Linear Systems](https://mlsanity.com/paper/2109.07630/) (2021)
- [The Horizon Threshold in Cooperative Multi-Agent Reward-Free Exploration](https://mlsanity.com/paper/2602.01453/) (2026)

## Abstract (arXiv)

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 tildeO(√T) regret bound. (Here tildeO(·) 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.