# When Simple Exploration is Sample Efficient: Identifying Sufficient Conditions for Random Exploration to Yield PAC RL Algorithms

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2018.

## Built on by (most cited first, 11 of 11)

- [Hybrid RL: Using Both Offline and Online Data Can Make RL Efficient](https://mlsanity.com/paper/2210.06718/) (2022)
- [Temporal Abstraction in Reinforcement Learning with the Successor Representation](https://mlsanity.com/paper/2110.05740/) (2021)
- [Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/2206.09421/) (2022)
- [Beyond Fine-Tuning: Transferring Behavior in Reinforcement Learning](https://mlsanity.com/paper/2102.13515/) (2021)
- [Reinforcement Learning with Function Approximation: From Linear to Nonlinear](https://mlsanity.com/paper/2302.09703/) (2023)
- [Policy Gradient with Tree Expansion](https://mlsanity.com/paper/2301.13236/) (2023)
- [The Effective Horizon Explains Deep RL Performance in Stochastic Environments](https://mlsanity.com/paper/2312.08369/) (2023)
- [Analysing the Sample Complexity of Opponent Shaping](https://mlsanity.com/paper/2402.05782/) (2024)
- [Sample Efficient Myopic Exploration Through Multitask Reinforcement Learning with Diverse Tasks](https://mlsanity.com/paper/2403.01636/) (2024)
- [ETGL-DDPG: A Deep Deterministic Policy Gradient Algorithm for Sparse Reward Continuous Control](https://mlsanity.com/paper/2410.05225/) (2024)
- [Knowledge Transfer from Teachers to Learners in Growing-Batch Reinforcement Learning](https://mlsanity.com/paper/2305.03870/) (2023)

## Abstract (arXiv)

Efficient exploration is one of the key challenges for reinforcement learning (RL) algorithms. Most traditional sample efficiency bounds require strategic exploration. Recently many deep RL algorithms with simple heuristic exploration strategies that have few formal guarantees, achieve surprising success in many domains. These results pose an important question about understanding these exploration strategies such as e-greedy, as well as understanding what characterize the difficulty of exploration in MDPs. In this work we propose problem specific sample complexity bounds of Q learning with random walk exploration that rely on several structural properties. We also link our theoretical results to some empirical benchmark domains, to illustrate if our bound gives polynomial sample complexity in these domains and how that is related with the empirical performance.