Success Probability of Exploration: a Concrete Analysis of Learning Efficiency
This work addresses practical challenges in reinforcement learning for practitioners, offering a concrete analytical tool, though it appears incremental as it builds on existing exploration theory.
The paper tackles the problem of analyzing exploration efficiency in reinforcement learning by proposing a new framework called the success probability of exploration, which answers key practical questions like parameter setting and MDP hardness, and demonstrates its utility through empirical verification.
Exploration has been a crucial part of reinforcement learning, yet several important questions concerning exploration efficiency are still not answered satisfactorily by existing analytical frameworks. These questions include exploration parameter setting, situation analysis, and hardness of MDPs, all of which are unavoidable for practitioners. To bridge the gap between the theory and practice, we propose a new analytical framework called the success probability of exploration. We show that those important questions of exploration above can all be answered under our framework, and the answers provided by our framework meet the needs of practitioners better than the existing ones. More importantly, we introduce a concrete and practical approach to evaluating the success probabilities in certain MDPs without the need of actually running the learning algorithm. We then provide empirical results to verify our approach, and demonstrate how the success probability of exploration can be used to analyse and predict the behaviours and possible outcomes of exploration, which are the keys to the answer of the important questions of exploration.