Timezone: »

 
Spotlight
Nearly Optimal Policy Optimization with Stable at Any Time Guarantee
Tianhao Wu · Yunchang Yang · Han Zhong · Liwei Wang · Simon Du · Jiantao Jiao

Tue Jul 19 01:55 PM -- 02:00 PM (PDT) @ Room 310
in Theory »
Policy optimization methods are one of the most widely used classes of Reinforcement Learning (RL) algorithms. However, theoretical understanding of these methods remains insufficient. Even in the episodic (time-inhomogeneous) tabular setting, the state-of-the-art theoretical result of policy-based method in Shani et al. (2020) is only $\tilde{O}(\sqrt{S^2AH^4K})$ where $S$ is the number of states, $A$ is the number of actions, $H$ is the horizon, and $K$ is the number of episodes, and there is a $\sqrt{SH}$ gap compared with the information theoretic lower bound $\tilde{\Omega}(\sqrt{SAH^3K})$ (Jin et al., 2018). To bridge such a gap, we propose a novel algorithm Reference-based Policy Optimization with Stable at Any Time guarantee (RPO-SAT), which features the property ``Stable at Any Time''. We prove that our algorithm achieves $\tilde{O}(\sqrt{SAH^3K} + \sqrt{AH^4K})$ regret. When $S > H$, our algorithm is minimax optimal when ignoring logarithmic factors. To our best knowledge, RPO-SAT is the first computationally efficient, nearly minimax optimal policy-based algorithm for tabular RL.
Keywords: T: Reinforcement Learning and Planning

Author Information

Tianhao Wu (UC Berkeley)
Yunchang Yang (Peking University)
Han Zhong (Peking University)
Liwei Wang (Peking University)
Simon Du (University of Washington)
Jiantao Jiao (University of California, Berkeley)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors