Polylogarithmic Collective Tree Exploration

We study asynchronous collective tree exploration, where $k$ agents with unrestricted communication start at the root of an unknown tree and discover edges online. At each step, an adversary chooses which agent moves. We give a deterministic algorithm that explores any tree with $n$ nodes and depth $D$ in at most $$2n+O(k{\log }^2(k)D)$$ moves, matching known lower bounds up to a constant factor. As a direct consequence, we obtain a near-optimal competitive ratio of $O({\log }^{2}k)$ for synchronous collective tree exploration, where all agents move at each round. The proof relies on a multiscale power regularizer that may be of independent interest.