Current browse context:
cs.LG
Change to browse by:
References & Citations
Computer Science > Machine Learning
Title: One Policy is Enough: Parallel Exploration with a Single Policy is Minimax Optimal for Reward-Free Reinforcement Learning
(Submitted on 31 May 2022 (this version), latest version 1 Mar 2023 (v3))
Abstract: 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.
Submission history
From: Boxiang Lyu [view email][v1] Tue, 31 May 2022 15:41:55 GMT (70kb)
[v2] Thu, 13 Oct 2022 01:15:25 GMT (71kb)
[v3] Wed, 1 Mar 2023 21:39:50 GMT (53kb)
Link back to: arXiv, form interface, contact.