# Efficiency of Parallel and Restart Exploration Strategies in Model Free Stochastic Simulations

arXiv: https://arxiv.org/abs/2503.03565 · HTML: https://mlsanity.com/paper/2503.03565/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 2 of its 31 references that are in the map.
- First posted on arXiv 5 Mar 2025.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 2 of 2)

- [First return, then explore](https://mlsanity.com/paper/2004.12919/) (2020)
- [Hitting Times in Markov Chains with Restart and their Application to Network Centrality](https://mlsanity.com/paper/1503.08548/) (2015)

## Abstract (arXiv)

We analyze the efficiency of parallelization and restart mechanisms for stochastic simulations in model-free settings, where the underlying system dynamics are unknown. Such settings are common in Reinforcement Learning (RL) and rare event estimation, where standard variance-reduction techniques like importance sampling are inapplicable. Focusing on the challenge of reaching rare states under a finite computational budget, we model exploration via random walks and L'evy processes. Based on rigorous probability analysis, our work reveals a phase transition in the success probability as a function of the number of parallel simulations: an optimal number N^* exists, balancing exploration diversity and time allocation per simulation. Beyond this threshold, performance degrades exponentially. Furthermore, we demonstrate that a restart strategy, which reallocates resources from stagnant trajectories to promising regions, can yield an exponential improvement in success probability. In the context of RL, these strategies can improve policy gradient methods by enabling more efficient state-space exploration, leading to more accurate policy gradient estimates.