Provably Efficient Exploration in Policy Optimization
  While policy-based reinforcement learning (RL) achieves tremendous successes
in practice, it is significantly less understood in theory, especially compared
with value-based RL. In particular, it remains elusive how to design a provably
efficient policy optimization algorithm that incorporates exploration. To
bridge such a gap, this paper proposes an Optimistic variant of the Proximal
Policy Optimization algorithm (OPPO), which follows an ``optimistic version''
of the policy gradient direction. This paper proves that, in the problem of
episodic Markov decision process with linear function approximation, unknown
transition, and adversarial reward with full-information feedback, OPPO
achieves $\tilde{O}(\sqrt{d^2 H^3 T} )$ regret. Here $d$ is the feature
dimension, $H$ is the episode horizon, and $T$ is the total number of steps. To
the best of our knowledge, OPPO is the first provably efficient policy
optimization algorithm that explores.
