Provable Cooperative Multi-agent Exploration For Reward-free Mdps

Abstract

We study cooperative multi-agent reinforcement learning in the setting of reward-free exploration, where multiple agents jointly explore an unknown MDP in order to learn its dynamics (without observing rewards). We focus on a tabular finite-horizon MDP and adopt a phased learning framework. In each learning phase, multiple agents independently interact with the environment. More specifically, in each learning phase, each agent is assigned a policy, executes it, and observes the resulting trajectory. Our primary goal is to characterize the tradeoff between the number of learning phases and the number of agents, especially when the number of learning phases is small. Our results identify a sharp transition governed by the horizon \(H\). When the number of learning phases equals \(H\), we present a computationally efficient algorithm that uses only \(\tilde\{O\}(S^6 H^6 A / \epsilon^2)\) agents to obtain an \(\epsilon\) approximation of the dynamics (i.e., yields an \(\epsilon\)-optimal

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keybarnea2026provable

Related papers

• Improved Bounds For Reward-agnostic And Reward-free Exploration (2026)0.00
• Optimal Horizon-free Reward-free Exploration For Linear Mixture Mdps (2023)0.00
• Non-cooperative Multi-agent Systems With Exploring Agents (2020)0.00
• Coordinated Exploration Via Intrinsic Rewards For Multi-agent Reinforcement Learning (2019)0.00
• MESA: Cooperative Meta-exploration In Multi-agent Learning Through Exploiting State-action Space Structure (2024)2.26
• Minimax-optimal Reward-agnostic Exploration In Reinforcement Learning (2023)0.00
• Graph Exploration For Effective Multi-agent Q-learning (2023)5.24
• Prioritized Guidance For Efficient Multi-agent Reinforcement Learning Exploration (2019)0.00