Nearly Optimal Policy Optimization with Stable at Any Time Guarantee
  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 \citet{shani2020optimistic} 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})$. To bridge
such a gap, we propose a novel algorithm Reference-based Policy Optimization
with Stable at Any Time guarantee (\algnameacro), 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.
