  In collective tree exploration, a team of $k$ mobile agents is tasked to go
through all edges of an unknown tree as fast as possible. An edge of the tree
is revealed to the team when one agent becomes adjacent to that edge. The
agents start from the root and all move synchronously along one adjacent edge
in each round. Communication between the agents is unrestricted, and they are,
therefore, centrally controlled by a single exploration algorithm. The
algorithm's guarantee is typically compared to the number of rounds required by
the agents to go through all edges if they had known the tree in advance. This
quantity is at least $\max\{2n/k,2D\}$ where $n$ is the number of nodes and $D$
is the tree depth. Since the introduction of the problem by [FGKP04], two types
of guarantees have emerged: the first takes the form $r(k)(n/k+D)$, where
$r(k)$ is called the competitive ratio, and the other takes the form
$2n/k+f(k,D)$, where $f(k,D)$ is called the competitive overhead. In this
paper, we present the first algorithm with linear-in-$D$ competitive overhead,
thereby reconciling both approaches. Specifically, our bound is in $2n/k +
O(k^{\log_2(k)-1} D)$ and leads to a competitive ratio in $O(k/\exp(\sqrt{\ln
2\ln k}))$. This is the first improvement over $O(k/\ln k)$ since the
introduction of the problem, twenty years ago. Our algorithm is developed for
an asynchronous generalization of collective tree exploration (ACTE). It
belongs to a broad class of locally-greedy exploration algorithms that we
define. We show that the analysis of locally-greedy algorithms can be seen
through the lens of a 2-player game that we call the tree-mining game and which
could be of independent interest.
