🤖 machine learning

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

This paper investigates cooperative multi-agent reward-free exploration in finite-horizon MDPs, identifying a critical threshold where having approximately $H$ learning phases allows for polynomial agent complexity, whereas fewer phases necessitate an exponential number of agents to achieve accurate dynamics estimation.

Original authors: Idan Barnea, Orin Levy, Yishay Mansour

Published 2026-05-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Idan Barnea, Orin Levy, Yishay Mansour

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to learn the layout of a massive, mysterious maze so that you can eventually guide a robot through it to find a treasure. However, there's a catch: you don't know where the treasure is yet. In fact, the treasure might be in a different spot tomorrow, or next week. Your only job right now is to map out the walls, doors, and corridors perfectly, without any clues about the goal.

This is the problem of "Reward-Free Exploration."

Now, imagine you have a team of explorers (agents) instead of just one. They can all run through the maze at the same time. The big question this paper asks is: How many explorers do you need, and how many rounds of running through the maze, to get a perfect map?

Here is the breakdown of their discovery, using some everyday analogies.

The Two Resources: Time vs. People

The researchers identified a trade-off between two things:

Parallel Time (Phases): How many rounds of exploration you allow. (Think of this as how many days you give the team to run).
Agent Complexity (People): How many explorers you send out in each round.

The "Horizon" is the Key

The maze has a length, called the Horizon ( $H$ ). This is the maximum number of steps you can take before the maze ends.

If the maze is 100 steps long, $H = 100$ .

The paper discovered a "Tipping Point" exactly at this number ( $H$ ).

Scenario A: The "Just Enough" Strategy ( $H$ Rounds)

If you allow your team to run through the maze for $H$ rounds (one round for every step of the maze), you can get away with a reasonable number of people.

The Analogy: Imagine you are learning a song that is $H$ notes long. If you practice one note per day for $H$ days, you can learn the whole song with a small group of musicians.
The Result: The paper provides an algorithm (called H-MARFE) that uses a "polynomial" number of agents. In math speak, this means the number of people needed grows in a manageable way (like $H^6$ ). It's a lot, but it's not impossible.

Scenario B: The "Rush Job" Strategy (Fewer than $H$ Rounds)

What if you are in a hurry? What if you only have half the time (fewer than $H$ rounds)?

The Analogy: Imagine trying to learn that same 100-note song in just 10 days. To do this, you would need to hire a staggering, exponential number of musicians to play every possible note combination simultaneously.
The Result: The paper proves that if you try to finish in fewer than $H$ rounds, the number of agents you need explodes. It goes from "a lot" to "an impossible number" (like needing $2^{100}$ people). The math shows that you simply cannot learn the map fast enough without an exponential army.

How the Algorithm Works (The "Sink" Trick)

The researchers' algorithm, H-MARFE, is clever. It doesn't try to learn the whole maze at once. Instead, it learns it layer by layer.

Focus on Reachability: It asks, "Which parts of the maze can we actually reach?"
The "Sink" State: If a part of the maze is so hard to reach that it's almost impossible to get there, the algorithm treats it like a "black hole" (called a sink). If you fall in, you stay there.
- Why? Because if a path is so rare that you almost never see it, it doesn't matter if your map of that specific corner is slightly wrong. It won't affect the overall plan much.
Layered Learning: In Round 1, they map the first step. In Round 2, they map the second step, using the map from Round 1 to know where to look. They do this for exactly $H$ rounds.

The "Hidden Key" Lower Bound

To prove that you can't do it faster, they created a special, tricky maze called the "Key-Dynamic."

The Setup: Imagine a hallway where, at every step, there is one specific "correct" door that keeps you in the hallway. If you pick the wrong door, you fall into a pit (the sink) and can never get back out.
The Secret: There is a secret sequence of doors (a "key") that keeps you safe for the whole length of the maze.
The Problem: If you only have a few rounds to explore, your team will almost certainly pick the wrong door at some point and fall into the pit. Once they fall in, they learn nothing about the rest of the hallway.
The Conclusion: To guarantee you find the secret "key" (the correct path) in fewer than $H$ rounds, you would need so many people that it's statistically impossible to fail. This proves that $H$ rounds is the absolute minimum to keep the number of people manageable.

Summary

The Goal: Map a complex environment without knowing the goal.
The Trade-off: You can't speed up the process (reduce rounds) without paying a massive price in manpower (exponential agents).
The Sweet Spot: If you let the process take as many rounds as the length of the environment ( $H$ ), you can do it with a manageable team.
The Warning: If you try to rush it (fewer than $H$ rounds), the cost becomes astronomical.

The paper essentially says: "Don't try to run a marathon in a sprint. If you want to map a long path efficiently, you need to give yourself enough time to walk it step-by-step."

Technical Summary: The Horizon Threshold in Cooperative Multi-Agent Reward-Free Exploration

Problem Statement

This work investigates cooperative multi-agent reward-free exploration within the framework of tabular finite-horizon Markov Decision Processes (MDPs). In this setting, $m$ agents interact in parallel with an unknown environment $M = (S, s_0, A, H, P, r)$ over $\rho$ learning phases. Crucially, during the exploration phase, agents do not observe the reward function $r$ ; their objective is to learn the transition dynamics $P$ accurately enough to compute an $\epsilon$ -optimal policy for any reward function revealed post-exploration.

The central research question addresses the trade-off between two resources:

Parallel Time: The number of learning phases $\rho$ .
Agent Complexity: The number of agents $m$ deployed per phase.

The paper seeks to characterize how the horizon $H$ governs the efficiency of learning, specifically determining whether a polynomial number of agents suffices when the number of phases is constrained.

Methodology

Upper Bound: The H-MARFE Algorithm

The authors propose H-MARFE (H-Phase Multi-Agent Reward-Free Exploration), an algorithm designed to operate in exactly $\rho = H$ phases using a polynomial number of agents.

Core Mechanism:
Unlike sequential regret-minimization approaches, H-MARFE utilizes a layer-wise exploration strategy that scales estimation accuracy with state reachability.

Phased Dynamics Estimation: In phase $i$ (where $i \in \{0, \dots, H-1\}$ ), the algorithm focuses exclusively on estimating the transition dynamics $P_i$ at timestep $i$ .
Reachability Filtering: The algorithm defines a set of "active" states $\hat{S}^\beta_i$ at each timestep, consisting of states with a reachability probability of at least $\beta$ under the current estimated dynamics. States with low reachability are effectively pruned by transitioning deterministically to a sink state $s_{sink}$ .
Policy Construction: For each active state-action pair $(s, a)$ , the algorithm computes a policy $\hat{\pi}_{i,s,a}$ that maximizes the probability of reaching $s$ at timestep $i$ and taking action $a$ , based on the dynamics learned in previous phases.
Parallel Execution: In each phase, $m$ agents are assigned random state-action pairs from the active set. They execute their assigned policies to collect trajectories, which are aggregated to form empirical transition estimates for the current layer.

Technical Innovation:
The analysis introduces an intermediate dynamics model $P^1$ that agrees with the true dynamics $P$ on the active set but transitions to $s_{sink}$ otherwise. The proof relies on bounding the policy-weighted error between the estimated dynamics $\hat{P}$ and $P^1$ . By controlling the additive error in occupancy measures relative to reachability, the algorithm ensures that the value estimation error remains bounded for any reward function, avoiding the exponential error accumulation typical of naive parallelization.

Lower Bound Construction

To establish the necessity of the horizon-scale number of phases, the authors construct a "Key-Dynamic" MDP.

Structure: The MDP has a state space of size 2 ( $s^\star$ and $s_{sink}$ ). There exists a hidden "key" sequence of actions $a^\star_0, \dots, a^\star_{H-1}$ . Taking the correct action $a^\star_h$ at state $s^\star$ keeps the agent in $s^\star$ ; any other action transitions to the absorbing sink state $s_{sink}$ .
Reward: A specific reward function $r_{key}$ assigns a reward of 1 only if the agent reaches the final timestep in state $s^\star$ having executed the correct final action.
Implication: To learn the dynamics (and thus the optimal policy), an algorithm must discover the entire key sequence. In a single phase, $m$ agents can uncover at most $\log_A(m)$ bits of the key. If the number of phases $\rho$ is significantly less than $H$ , the probability of discovering the full key drops exponentially unless the number of agents $m$ grows exponentially with $H/\rho$ .

Key Results

1. Upper Bound (Theorem 3.1)

The H-MARFE algorithm achieves an $\epsilon$ -optimal policy for any reward function with high probability using:

Phases: $\rho = H$ .
Agents: $m = \tilde{O}\left(\frac{S^6 H^6 A}{\epsilon^2}\right)$ .

This demonstrates that efficient learning (polynomial in $S, A, H, \epsilon^{-1}$ ) is achievable when the number of learning phases scales linearly with the horizon.

2. Lower Bound (Theorem 4.1)

For any cooperative multi-agent algorithm restricted to $\rho < H$ learning phases, achieving constant accuracy (e.g., $\epsilon = 0.1$ ) requires:

Agents: $m = \Omega\left(\frac{A^{(H-1)/\rho}}{\rho}\right)$ .

This lower bound proves that reducing the number of phases below the horizon necessitates an exponential increase in the number of agents.

3. The Horizon Threshold

The combined results identify a sharp regime change governed by the horizon $H$ :

Polynomial Regime: When $\rho \approx H$ , agent complexity is polynomial.
Exponential Regime: When $\rho \ll H$ , agent complexity becomes exponential in $H/\rho$ .

Significance and Claims

The paper claims to establish a fundamental limit on the parallel efficiency of reward-free exploration in tabular MDPs. The primary contribution is the identification of the horizon $H$ as a critical threshold for parallel time.

Necessity of Horizon-Scale Phases: The work demonstrates that to avoid exponential agent complexity, one cannot simply compress the exploration into a constant or sub-linear number of phases. The number of phases must scale with the horizon.
Algorithmic Efficiency: H-MARFE provides a computationally efficient method to achieve this optimal trade-off, contrasting with prior reward-free literature which is inherently sequential or requires switching costs that scale linearly with episodes.
Theoretical Gap: The authors note that while their upper bound achieves polynomial complexity, the dependence on $S$ and $H$ ( $S^6 H^6$ ) is higher than state-of-the-art single-agent bounds ( $S^2 H^3$ ). They explicitly state it remains an open question whether this gap is an inherent cost of parallelization or an artifact of their analysis.

The paper concludes that cooperative multi-agent reward-free exploration is feasible with polynomial resources only if the parallel time (phases) is allowed to scale with the problem's horizon, fundamentally distinguishing this setting from scenarios where parallelism can arbitrarily reduce time complexity without exponential resource costs.