mlsanityData to 14 Oct 2026

The Horizon Threshold in Cooperative Multi-Agent Reward-Free Exploration

arXiv 2602.01453 ↗First posted 1 Feb 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

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 regime change governed by the horizon H. When the number of learning phases equals H, we present a computationally efficient algorithm that uses only tildeO(S6 H6 A / ε2) agents to obtain an ε approximation of the dynamics (i.e., yields an ε-optimal policy for any reward function). We complement our algorithm with a lower bound showing that any algorithm restricted to ρ < H phases requires at least AH/ρ agents to achieve constant accuracy. Thus, we show that having Theta(H) learning phases is both necessary and sufficient when restricting the number of agents to be polynomial.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 33 of its 41 references that are in the map. First posted on arXiv 1 Feb 2026.

Builds on

33 of 41 references.

References · 33

  1. 2022Scaling Instruction-Finetuned Language Modelscited by 3,024
  2. 2018Diversity is All You Need: Learning Skills without a Reward Functioncited by 752
  3. 2023A Survey of Reinforcement Learning from Human Feedbackcited by 264
  4. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  5. 2018Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimationcited by 227
  6. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  7. 2017Emergence of Locomotion Behaviours in Rich Environmentscited by 165
  8. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  9. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  10. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  11. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  12. 2020Adaptive Reward-Free Explorationcited by 77
21 more
  1. 2019Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learningcited by 75
  2. 2024Is Behavior Cloning All You Need? Understanding Horizon in Imitation Learningcited by 74
  3. 2021Exploration in Deep Reinforcement Learning: From Single-Agent to Multiagent Domaincited by 58
  4. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  5. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  6. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  7. 2021A Simple Reward-free Approach to Constrained Reinforcement Learningcited by 30
  8. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  9. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  10. 2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
  11. 2018Coordinated Exploration in Concurrent Reinforcement Learningcited by 17
  12. 2023Efficient Model-Free Exploration in Low-Rank MDPscited by 16
  13. 2024Layer by Layer: Uncovering Where Multi-Task Learning Happens in Instruction-Tuned Large Language Modelscited by 15
  14. 2023Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPscited by 14
  15. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
  16. 2022Near-Optimal Regret Bounds for Multi-batch Reinforcement Learningcited by 13
  17. 2018Scalable Coordinated Exploration in Concurrent Reinforcement Learningcited by 10
  18. 2024Scalable Online Exploration via Coverabilitycited by 10
  19. 2024Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoffcited by 8
  20. 2020Regret Bounds for Decentralized Learning in Cooperative Multi-Agent Dynamical Systemscited by 4
  21. 2022Cooperative Online Learning in Stochastic and Adversarial MDPscited by 4

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024Multi-agent cooperation through learning-aware policy gradients
  2. 2024Randomized Exploration in Cooperative Multi-Agent Reinforcement Learning
  3. 2025Optimistic ε-Greedy Exploration for Cooperative Multi-Agent Reinforcement Learning
  4. 2026Quality-Aware Exploration Budget Allocation for Cooperative Multi-Agent Reinforcement Learning
  5. 2026Multi-Agent Reinforcement Learning with Submodular Reward
  6. 2024MESA: Cooperative Meta-Exploration in Multi-Agent Learning through Exploiting State-Action Space Structure
  7. 2025Reinforcement Learning with Random Time Horizons
  8. 2025MIR: Efficient Exploration in Episodic Multi-Agent Reinforcement Learning via Mutual Intrinsic Reward