Quantile of Means: A Bonus-Free Ensemble Method for Minimax Optimal Reinforcement Learning
It provides theoretical justification for ensemble-based exploration in reinforcement learning, a practical but previously ungrounded approach.
The paper proposes a quantile-based ensemble method for finite-horizon MDPs that achieves optimal variance-dependent regret bounds without using count-based uncertainty estimates, providing theoretical grounding for ensemble-based exploration in RL.
Optimal Reinforcement Learning (RL) algorithms typically rely on carefully constructed count-based uncertainty estimates to drive exploration. Although theoretically sound, such estimates are hard to compute in practical settings and therefore offer limited insight for designing exploration heuristics. Meanwhile, ensembling has emerged as a practical approach, but remains without theoretical justification. Building on a recent ensemble-based method for Multi-Armed Bandits, we propose a quantile-based ensemble method for finite-horizon Markov Decision Processes (MDPs). Our simple count-free approach achieves optimal variance-dependent regret bounds, providing theoretical grounding for ensemble-based exploration in RL.