Research map / Multi-agent systems and games / Cooperative multi-agent RL

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

NeurIPS 2026 · Multi-agent systems and games › Cooperative multi-agent RL · approach: Intrinsic-reward exploration for MARL · 0 citations (OpenAlex)

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.

Studies cooperative multi-agent reward-free exploration in tabular finite-horizon MDPs, showing an H-phase algorithm (H-MARFE) with polynomial agents and a lower bound requiring exponentially many agents when phases are fewer than H.

Problem

Reward-free exploration of an unknown tabular MDP by many parallel agents is limited by the number of sequential learning phases; the trade-off between parallel time (phases) and agent complexity is unclear.

Approach

A phased, layer-by-layer exploration algorithm that scales exploration effort with state reachability under the estimated model, learning one timestep's transitions per phase in parallel across agents, avoiding regret minimization; paired with a lower bound showing A^{H/rho} agents are needed for rho<H phases.

Key results

• H-MARFE learns the dynamics in exactly H learning phases with m = O~(S^5 H^6 A (log(SHA/delta)+S)/epsilon^2) agents (theorem's stated bound; abstract states S^6 H^6 A/epsilon^2).
• Lower bound: any algorithm with rho < H phases needs Omega(A^{(H-1)/rho}/rho) agents per phase to reach constant accuracy.
• The exploration analysis yields a parallelizable reward-free guarantee, with the transition from polynomial to exponential agent complexity occurring at rho on the order of H.

Surprising findings

• A3C requires exponentially many (2^H) learning phases before observing any reward on sparse-reward deterministic MDPs.

Limitations

• Polynomial dependence on S and H (S^5/S^6, H^6) is higher than single-agent state of the art (S^2 H^3 A/epsilon^2).
• Lower bound regime change is gradual; the exact threshold between H/2 and H phases is not resolved.
• Extension to linear MDPs or large state spaces is not provided.

Experimental setup

Metrics: sample complexity agent complexity value gap of epsilon-optimal policy

Baselines: A3C seed sampling DPPO

Builds on: reward-free exploration concurrent RL deployment-efficient RL

Closest papers by meaning

• Improved Bounds for Reward-Agnostic and Reward-Free Exploration (ICML 2026 · similarity 0.89)
• Multi-agent cooperation through learning-aware policy gradients (ICLR 2025 · similarity 0.89)
• Randomized Exploration in Cooperative Multi-Agent Reinforcement Learning (NeurIPS 2024 · similarity 0.88)
• Measuring Mutual Policy Divergence for Multi-Agent Sequential Exploration (NeurIPS 2024 · similarity 0.88)
• Settling Decentralized Multi-Agent Coordinated Exploration by Novelty Sharing (AAAI 2024 · similarity 0.88)
• Reinforcement Learning with Random Time Horizons (ICML 2025 · similarity 0.87)