Timezone: »

 
Poster
Almost Optimal Model-Free Reinforcement Learningvia Reference-Advantage Decomposition
Zihan Zhang · Yuan Zhou · Xiangyang Ji

Tue Dec 08 09:00 PM -- 11:00 PM (PST) @ Poster Session 2 #576

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].

Author Information

Zihan Zhang (Tsinghua University)
Yuan Zhou (UIUC)
Xiangyang Ji (Tsinghua University)

More from the Same Authors