Research map / Multi-agent systems and games / Cooperative multi-agent RL
Randomized Exploration in Cooperative Multi-Agent Reinforcement Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces CoopTS-PHE and CoopTS-LMC, randomized (Thompson-sampling-type) exploration algorithms for cooperative multi-agent RL in parallel MDPs, with regret and communication-complexity guarantees and DQN-based experiments.
Problem
Provably efficient exploration in cooperative multi-agent RL with parallel MDPs, where existing UCB-based methods are hard to implement beyond linear settings and perform poorly in practice, and communication among agents is costly.
Approach
A unified LSVI-based framework for parallel MDPs with event-triggered (determinant-based) synchronization, instantiated with two randomized exploration strategies: perturbed-history exploration (Gaussian noise on rewards and regularizer) and Langevin Monte Carlo (noisy gradient updates), avoiding Laplace-approximation posterior sampling and UCB bonuses.
Key results
- Theory: CoopTS-PHE and CoopTS-LMC achieve Õ(d^{3/2}H^2 sqrt(MK)) regret with Õ(dHM^2) communication complexity in linear parallel MDPs.
- Experiments on N-chain (N=25, m=3 agents) show PHE and LMC outperform DQN, Double DQN, Bootstrapped DQN and Noisy-Net baselines.
- On Super Mario Bros with four agents, both randomized strategies outperform baselines, with LMC showing a larger advantage over PHE than on N-chain.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use randomized exploration with PHE or LMC instead of the evaluated DQN-based baselines | CoopTS-PHE and CoopTS-LMC · N-chain (N=25) | average episode return | Helped |
| Use randomized exploration with PHE or LMC instead of the evaluated baselines | CoopTS-PHE and CoopTS-LMC · Super Mario Bros | performance | Helped |
| Use PHE or LMC instead of the other evaluated methods | CoopTS-PHE and CoopTS-LMC · BuildingEnv, Tampa | return | Helped |
| Use PHE instead of LMC | CoopTS exploration on N-chain · N-chain (N=25) | fluctuation in average episode return | Helped |
| Use LMC instead of PHE | CoopTS exploration on Super Mario Bros · Super Mario Bros | performance | Helped |
| Use communication in the cooperative method rather than having agents act independently | CoopTS-PHE · Homogeneous parallel linear MDPs | regret: $\widetilde{\mathcal{O}}(M\cdot d^{3/2}H^2 \sqrt{K})$ to $\widetilde{\mathcal{O}}(d^{3/2}H^2\sqrt{MK})$ | Helped |
| Use CoopTS-PHE instead of Coop-LSVI | Multi-agent linear MDPs · Episodic, non-stationary linear MDPs | communication complexity: $\widetilde{\mathcal{O}}\big(dHM^3\big)$ to $\widetilde{\mathcal{O}}\big(dHM^2\big)$ | Helped |
Surprising findings
- Synchronous communication achieves the same communication complexity as the asynchronous variant, suggesting asynchrony only delays rather than reduces communication.
- PHE shows less fluctuation than LMC on N-chain, while LMC is better on Super Mario Bros.
Limitations
- Theory is restricted to (approximately) linear parallel MDPs; general function class requires sharing full datasets with high communication cost.
- Gaussian-noise PHE may not approximate the true Q-function posterior well in practical environments like Super Mario Bros.
- Experiments use DQN-based deep variants whose theory does not directly apply.
Experimental setup
Datasets: N-chain Super Mario Bros BuildingEnv
Benchmarks: N-chain Super Mario Bros BuildingEnv
Metrics: regret average episode return
Baselines: DQN Double DQN Bootstrapped DQN Noisy-Net Random action
Builds on: LSVI-UCB Coop-LSVI PHE LMC-LSVI Bootstrapped DQN
Closest papers by meaning
- Settling Decentralized Multi-Agent Coordinated Exploration by Novelty Sharing (AAAI 2024 · similarity 0.89)
- Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation (NeurIPS 2024 · similarity 0.88)
- The Horizon Threshold in Cooperative Multi-Agent Reward-Free Exploration (NeurIPS 2026 · similarity 0.88)
- Efficient Preference-Based Reinforcement Learning: Randomized Exploration meets Experimental Design (NeurIPS 2025 · similarity 0.88)
- Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learning (NeurIPS 2025 · similarity 0.88)
- Measuring Mutual Policy Divergence for Multi-Agent Sequential Exploration (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.