# One Policy is Enough: Parallel Exploration with a Single Policy is Near-Optimal for Reward-Free Reinforcement Learning

**Authors:** Pedro Cisneros-Velarde, Boxiang Lyu, Sanmi Koyejo, Mladen Kolar  
**arXiv:** [2205.15891](https://arxiv.org/abs/2205.15891)  
**Date:** 2022-05-31  
**Summary page:** https://www.summarizepaper.com/en/paper/2205.15891v3/

## Key points

- Investigating benefits of parallel exploration in reward-free RL in linear MDPs and two-player zero-sum MGs
- Using a single policy to guide exploration across all agents instead of diverse set of policies
- Achieving almost linear speedup compared to fully sequential exploration in all cases
- Near-minimax optimal for linear MDPs in the reward-free setting
- Single policy is sufficient and provably near optimal for incorporating parallelism during exploration phase
- Raising open questions about theoretical justifications and potential advantages of more intricate coordinated exploration strategies

## Summary

In this paper, the authors investigate the benefits of parallel exploration in reward-free reinforcement learning (RL) in linear Markov decision processes (MDPs) and two-player zero-sum Markov games (MGs). They focus on using a single policy to guide exploration across all agents instead of encouraging them to explore a diverse set of policies. The authors demonstrate that this simple approach can achieve an almost linear speedup compared to fully sequential exploration in all cases. Furthermore, they show that this procedure is near-minimax optimal for linear MDPs in the reward-free setting. From a practical perspective, the paper highlights that a single policy is sufficient and provably near optimal for incorporating parallelism during the exploration phase. The authors conclude by raising open questions regarding the theoretical justifications and potential advantages of more intricate coordinated exploration strategies compared to their simplistic approach.