Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
This provides an almost optimal solution for reinforcement learning practitioners dealing with sample efficiency in model-free settings, representing a significant theoretical advance rather than an incremental improvement.
The paper tackles the problem of model-free reinforcement learning in finite-horizon episodic MDPs by proposing the UCB-Advantage algorithm, which achieves $ ilde{O}(\sqrt{H^2SAT})$ regret, matching the information-theoretic lower bound up to logarithmic factors and improving upon prior results.
We study the reinforcement learning problem in the setting of finite-horizon episodic Markov Decision Processes (MDPs) with $S$ states, $A$ actions, and episode length $H$. We propose a model-free algorithm UCB-Advantage and prove that it achieves $\tilde{O}(\sqrt{H^2SAT})$ regret where $T = KH$ and $K$ is the number of episodes to play. Our regret bound improves upon the results of [Jin et al., 2018] and matches the best known model-based algorithms as well as the information theoretic lower bound up to logarithmic factors. We also show that UCB-Advantage achieves low local switching cost and applies to concurrent reinforcement learning, improving upon the recent results of [Bai et al., 2019].