Nearly Optimal Policy Optimization with Stable at Any Time Guarantee

Reinforcement Learning (RL) has achieved phenomenal successes in solving complex sequential decisionmaking problems (Silver et al., 2016, 2017; Levine et al., 2016; Gu et al., 2017). Most of these empirical successes are driven by policy-based (policy optimization) methods, such as policy gradient (Sutton et al., 1999), natural policy gradient (NPG) (Kakade, 2001), trust region policy optimization (TRPO) (Schulman et al., 2015), and proximal policy optimization (PPO) (Schulman et al., 2017). For example, Haarnoja et al. (2018) proposed a policy-based state-of-the-art reinforcement learning algorithm, soft actor-critic (SAC), which outperformed value-based methods in a variety of real world robotics tasks including manipulation and locomotion. In fact, Kalashnikov et al. (2018) observed that compared with value-based methods such as Q-learning, policy-based methods work better with dense reward. On the other hand, for sparse reward cases in robotics, value-based methods perform better. Motivated by this, a line of recent work (Fazel et al., 2018; Bhandari and Russo, 2019; Liu et al., 2019; Wang et al., 2019; Agarwal et al., 2021) provides global convergence guarantees for these popular policybased methods. However, to achieve this goal, they made several assumptions.