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

Pedro Cisneros-Velarde, Boxiang Lyu, Sanmi Koyejo, Mladen KolarAISTATS 2023 · OpenReview

Abstract

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 strategies where multiple agents follow a single shared policy. We prove that this approach achieves near-optimal exploration and an almost-linear speedup in reward-free settings for both linear Markov Decision Processes and two-player zero-sum games.

Introduction

Parallelism is a cornerstone of modern deep RL, enabling systems like AlphaGo and StarCraft II to process vast amounts of data. However, the theoretical foundations of parallel exploration remain underdeveloped. A common heuristic in the field is that parallel agents must be "diverse"—incentivized to explore different regions of the state space—to be efficient. This often leads to complex coordination protocols and high communication overhead.

This paper challenges that convention by asking: Is diversity of exploration policies actually necessary for a speedup? The authors investigate this in the "reward-free" RL setting, where agents explore an environment to learn its dynamics without a specific goal, eventually enabling them to solve any task provided later.

Methodology: POLSVI and RF-POLSVI

The authors propose two primary algorithms: Parallel Optimistic Least-Squares Value Iteration (POLSVI) and its reward-free variant, RF-POLSVI.

Algorithm 1: Parallel Optimistic LSVI (POLSVI) for reward-aware settings.

The core mechanism relies on a centralized-decentralized loop:

  1. Centralized Aggregation: A central server aggregates trajectories from $P$ parallel agents.
  2. Global Update: The server updates a global covariance matrix and computes an optimistic value function estimate using a UCB-style bonus.
  3. Unified Policy Deployment: Crucially, every agent is assigned the exact same greedy policy for the subsequent episode.
  4. Exploration via Pseudo-Rewards: In the reward-free version, the exploration bonus itself serves as the reward, driving agents toward high-uncertainty regions.
Algorithm 2: Reward-Free POLSVI (RF-POLSVI) for exploration without a pre-defined reward.

Theoretical Framework

This study focuses on Linear MDPs and Linear Markov Games (MGs). These models are standard in theoretical RL for analyzing algorithms that utilize function approximation. By proving results in these settings, the authors provide a rigorous mathematical basis for the efficiency of single-policy parallel exploration.

Key Insights

The "One Policy" Sufficiency

The most significant finding is that explicit diversity is unnecessary. The inherent stochasticity of the environment, combined with "optimism under uncertainty," ensures that a single shared policy generates a sufficiently diverse dataset.

Almost-Linear Speedup

The paper demonstrates that with $P$ agents, the time required to reach a performance threshold is reduced by a factor of nearly $P$. The suboptimality bound scales with $1/\sqrt{KP}$, where $K$ is the number of episodes.

The Price of Parallelization

While achieving speedup, the authors identify an "overhead term" caused by "doubling rounds." These occur when parallel agents collect such novel information that the policy becomes "stale" before the next synchronization. Fortunately, this overhead is shown to be minimal (polylogarithmic in $P$).

Results and Performance

  • Linear MDPs: RF-POLSVI achieves a suboptimality of $\tilde{O}(\sqrt{d^3 H^6 / KP})$, confirming the $1/\sqrt{P}$ speedup.
  • Markov Games: The paper introduces the first parallel reward-free RL algorithm for MGs with near-linear speedup guarantees.
  • Minimax Optimality: The algorithm is near-minimax optimal when the number of agents $P$ is proportional to the number of rounds $K$ ($P = O(K)$), which aligns with practical large-scale RL deployments.

Conclusion and Future Directions

This research proves that simple, unified policies are theoretically sufficient for efficient parallel exploration. However, several avenues for future work remain. The current model assumes synchronization after every episode; future research could investigate "deployment-efficient" versions with less frequent communication. Additionally, while linear models provide a strong foundation, extending these proofs to general function approximation or deep neural networks is a critical next step.

Summary updated

Abstract

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 simpl...
BibTeX
@inproceedings{cisnerosvelarde2023one,
  author = {Pedro Cisneros-Velarde and Boxiang Lyu and Sanmi Koyejo and Mladen Kolar},
  title = {{One Policy is Enough: Parallel Exploration with a Single Policy is Near-Optimal for Reward-Free Reinforcement Learning}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=_DzNNkev_t},
}
Figure