One Policy is Enough: Parallel Exploration with a Single Policy is Near-Optimal for Reward-Free Reinforcement Learning
Not on the map. Why?
Abstract (arXiv)
Although 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 in linear Markov decision processes (MDPs) and two-player zero-sum Markov games (MGs). In contrast to the existing literature, which focuses on approaches that encourage agents to explore 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. Furthermore, we demonstrate that this simple procedure is near-minimax optimal in the reward-free setting for linear MDPs. From a practical perspective, our paper shows that a single policy is sufficient and provably near-optimal for incorporating parallelism during the exploration phase.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 31 of its 52 references that are in the map. First posted on arXiv 31 May 2022.
Builds on
31 of 52 references.
References · 31
- 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
- 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
- 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
- 2019MAVEN: Multi-Agent Variational Explorationcited by 185
- 2020Reward-Free Exploration for Reinforcement Learningcited by 177
- 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
- 2020Game-Theoretic Multiagent Reinforcement Learningcited by 94
- 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 92
- 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
- 2020Differentially-Private Federated Linear Banditscited by 83
- 2015Massively Parallel Methods for Deep Reinforcement Learningcited by 82
- 2019Provably Efficient Q-Learning with Low Switching Costcited by 78
19 more
- 2021Federated Multi-armed Bandits with Personalizationcited by 62
- 2013Online Learning with Switching Costs and Other Adaptive Adversariescited by 61
- 2021Federated Linear Contextual Banditscited by 61
- 2020Federated Bandit: A Gossiping Approachcited by 55
- 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
- 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 40
- 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
- 2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
- 2021Provably Efficient Cooperative Multi-Agent Reinforcement Learning with Function Approximationcited by 23
- 2019A Multi-Agent Off-Policy Actor-Critic Algorithm for Distributed Reinforcement Learningcited by 21
- 2018Cooperative and Distributed Reinforcement Learning of Drones for Field Coveragecited by 20
- 2021Parallelizing Thompson Samplingcited by 20
- 2021On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Gamecited by 20
- 2021Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Gamescited by 18
- 2018Coordinated Exploration in Concurrent Reinforcement Learningcited by 17
- 2019A Communication-Efficient Multi-Agent Actor-Critic Algorithm for Distributed Reinforcement Learningcited by 16
- 2019Distributed off-Policy Actor-Critic Reinforcement Learning with Policy Consensuscited by 11
- 2021Communication Efficient Parallel Reinforcement Learningcited by 10
- 2022Transfer in Reinforcement Learning via Regret Bounds for Learning Agentscited by 2
Built on by
Citing papers per year: 2023: 2.
2 papers.