One Policy is Enough: Parallel Exploration with a Single Policy is Minimax Optimal for Reward-Free Reinforcement Learning
While parallelism has been extensively used in Reinforcement Learning (RL),
the quantitative effects of parallel exploration are not well understood
theoretically. We study the benefits of simple parallel exploration for
reward-free RL for linear Markov decision processes (MDPs) and two-player
zero-sum Markov games (MGs). In contrast to the existing literature focused on
approaches that encourage agents to explore over a diverse set of policies, we
show that using a single policy to guide exploration across all agents is
sufficient to obtain an almost-linear speedup in all cases compared to their
fully sequential counterpart. Further, we show that this simple procedure is
minimax optimal up to logarithmic factors in the reward-free setting for both
linear MDPs and two-player zero-sum MGs. From a practical perspective, our
paper shows that a single policy is sufficient and provably optimal for
incorporating parallelism during the exploration phase.