Almost Optimal Model-Free Reinforcement Learningvia Reference-Advantage Decomposition
Abstract
We study the reinforcement learning problem in the setting of finite-horizon1episodic 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^2 SAT}) 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].
Cite
Text
Zhang et al. "Almost Optimal Model-Free Reinforcement Learningvia Reference-Advantage Decomposition." Neural Information Processing Systems, 2020.Markdown
[Zhang et al. "Almost Optimal Model-Free Reinforcement Learningvia Reference-Advantage Decomposition." Neural Information Processing Systems, 2020.](https://mlanthology.org/neurips/2020/zhang2020neurips-almost/)BibTeX
@inproceedings{zhang2020neurips-almost,
title = {{Almost Optimal Model-Free Reinforcement Learningvia Reference-Advantage Decomposition}},
author = {Zhang, Zihan and Zhou, Yuan and Ji, Xiangyang},
booktitle = {Neural Information Processing Systems},
year = {2020},
url = {https://mlanthology.org/neurips/2020/zhang2020neurips-almost/}
}