Closing the Log Gap: Minimax-Optimal Regret for Episodic RL

In this paper, we study the regret minimization problem in episodic tabular MDPs. Our algorithm achieves the first expected regret bound scaling as √H³ S A K for sufficiently large K, where H is the episode length, K is the number of episodes, and S and A are the numbers of states and actions, respectively. Our method is the first to match the minimax lower bound without extra polylog factors. We introduce a variant of UCBVI which does not maintain strictly optimistic estimates, and uses MOSS-style exploration bonuses whose logarithmic terms adapt to both visit counts and estimated variances. A key challenge is controlling the propagation of errors caused by under-optimism, which we accomplish in an occupancy-weighted way, avoiding logarithmic overhead that would be incurred by uniform-over-rows concentration. Our analysis develops time-uniform and variance-aware concentration bounds that may be of independent interest. As a corollary we also develop an algorithm for (ε, δ)-PAC best-policy identification, which is the first to match the Ω(H³ SAlog(1δ)ε⁻²) minimax lower bound up to constants in some regimes.