Closing the Log Gap: Minimax-Optimal Regret for Episodic RL
Abstract
In this paper, we study the regret minimization problem in episodic tabular MDPs. Our algorithm achieves the first expected regret bound scaling as √(H3 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 \emph{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 Ω(H3 SAlog(1/δ)ε−2) minimax lower bound up to constants in some regimes.
Related
- Expected Utility Regret Rule: Minimax and Bayes Optimal Portfolio Choice
- Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity
- Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions
- Worst-Case Bayesian CVaR Regret Bounds for Episodic Markov Decision Processes
- Towards instance-dependent regret optimality in Episodic MDPs with Posterior Sampling
BibTeX
@misc{zamir2026closing,
title = {{Closing the Log Gap: Minimax-Optimal Regret for Episodic RL}},
author = {Guy Zamir and Victor Boone and Matthew Zurek and Yudong Chen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.40165},
eprint = {2610.40165},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.40165},
}
RIS
TY - UNPB
TI - Closing the Log Gap: Minimax-Optimal Regret for Episodic RL
AU - Guy Zamir
AU - Victor Boone
AU - Matthew Zurek
AU - Yudong Chen
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.40165
UR - https://arxiv.org/abs/2610.40165
AB - In this paper, we study the regret minimization problem in episodic tabular MDPs. Our algorithm achieves the first expected regret bound scaling as √(H^3 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 \emph{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^3 SAlog(1/δ)ε^−2) minimax lower bound up to constants in some regimes.
ER -