Algorithm achieves optimal learning speed in episodic reinforcement learning
Closing the Log Gap: Minimax-Optimal Regret for Episodic RL
Machine Learning
Summary
This paper addresses how to make computers learn the best actions in a limited number of tries within a game or task that has many steps. The authors developed an algorithm that learns almost as fast as theoretically possible, without extra slowdowns usually caused by complicated calculations. Their approach adjusts how it explores the task, balancing risk and uncertainty to improve learning speed. They also provided a new method to identify the best strategy reliably with fewer samples than previous methods.
What this means in practice
- •For reinforcement learning engineers: Develop systems that learn optimal policies faster and with fewer samples in settings with clear episodic tasks and defined states and actions.
- •For autonomous robotics teams: Improve robot decision-making efficiency during repeated tasks with multiple steps by using algorithms that minimize learning errors optimally.
Authors
Guy Zamir, Victor Boone, Matthew Zurek, Yudong Chen
Abstract
In this paper, we study the regret minimization problem in episodic tabular MDPs. Our algorithm achieves the first expected regret bound scaling as $\sqrt{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 $(\varepsilon, δ)$-PAC best-policy identification, which is the first to match the $Ω\big(H^3 SA\log(\frac{1}δ)\varepsilon^{-2}\big)$ minimax lower bound up to constants in some regimes.