# Randomized Exploration in Cooperative Multi-Agent Reinforcement Learning

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Apr 2024.

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

- [Inverse Reinforcement Learning with Dynamic Reward Scaling for LLM Alignment](https://mlsanity.com/paper/2503.18991/) (2025)
- [Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learning](https://mlsanity.com/paper/2409.20521/) (2024)
- [More Efficient Randomized Exploration for Reinforcement Learning via Approximate Sampling](https://mlsanity.com/paper/2406.12241/) (2024)
- [Gap-Dependent Bounds for Federated Q-learning](https://mlsanity.com/paper/2502.02859/) (2025)
- [Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning](https://mlsanity.com/paper/2506.04626/) (2025)
- [Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits](https://mlsanity.com/paper/2510.10730/) (2025)
- [Isoperimetry is All We Need: Langevin Posterior Sampling for RL with Sublinear Regret](https://mlsanity.com/paper/2412.20824/) (2024)
- [Nonparametric Bellman Mappings for Value Iteration in Distributed Reinforcement Learning](https://mlsanity.com/paper/2503.16192/) (2025)
- [A Reward-driven Automated Webshell Malicious-code Generator for Red-teaming](https://mlsanity.com/paper/2505.24252/) (2025)
- [Exploration by Random Reward Perturbation](https://mlsanity.com/paper/2506.08737/) (2025)
- [Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspective](https://mlsanity.com/paper/2510.05023/) (2025)
- [Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost](https://mlsanity.com/paper/2609.00193/) (2026)
- [VisuoAlign: Safety Alignment of LVLMs with Multimodal Tree Search](https://mlsanity.com/paper/2510.15948/) (2025)
- [Cooperative Multi-agent RL with Communication Constraints](https://mlsanity.com/paper/2601.12518/) (2026)
- [Multi-Agent Reinforcement Learning with Submodular Reward](https://mlsanity.com/paper/2603.06810/) (2026)
- [Quality-Aware Exploration Budget Allocation for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2605.01865/) (2026)
- [Heterogeneous Information-Bottleneck Coordination Graphs for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2605.17393/) (2026)

## Abstract (arXiv)

We present the first study on provably efficient randomized exploration in cooperative multi-agent reinforcement learning (MARL). We propose a unified algorithm framework for randomized exploration in parallel Markov Decision Processes (MDPs), and two Thompson Sampling (TS)-type algorithms, CoopTS-PHE and CoopTS-LMC, incorporating the perturbed-history exploration (PHE) strategy and the Langevin Monte Carlo exploration (LMC) strategy, respectively, which are flexible in design and easy to implement in practice. For a special class of parallel MDPs where the transition is (approximately) linear, we theoretically prove that both CoopTS-PHE and CoopTS-LMC achieve a widetildeO(d3/2H2√MK) regret bound with communication complexity widetildeO(dHM2), where d is the feature dimension, H is the horizon length, M is the number of agents, and K is the number of episodes. This is the first theoretical result for randomized exploration in cooperative MARL. We evaluate our proposed method on multiple parallel RL environments, including a deep exploration problem (i.e., N-chain), a video game, and a real-world problem in energy systems. Our experimental results support that our framework can achieve better performance, even under conditions of misspecified transition models. Additionally, we establish a connection between our unified framework and the practical application of federated learning.