Quantile of Means: A Bonus-Free Ensemble Method for Minimax Optimal Reinforcement Learning

Optimal Reinforcement Learning (RL) algorithms typically rely on carefully constructed count-based uncertainty estimates, such as bonuses or posterior distributions, to drive exploration. Although theoretically sound, such estimates are difficult to scale and therefore offer limited insight for designing exploration heuristics in practice. 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 tabular MDPs. Our simple bonus-free approach achieves optimal variance-dependent regret bounds without explicit uncertainty estimation, providing theoretical grounding for ensemble-based exploration in RL.