Optimistic Natural Policy Gradient: a Simple Efficient Policy Optimization Framework for Online RL
This provides a computationally efficient solution for online RL with improved sample complexity, addressing a key bottleneck in theoretical RL, though it is incremental as it builds on existing NPG methods.
The paper tackles the problem of inefficient sample complexity in online reinforcement learning by proposing Optimistic Natural Policy Gradient (NPG), which combines natural policy gradient with optimistic policy evaluation. It achieves an optimal sample complexity of Õ(d²/ε³) for linear MDPs, improving over prior work by a factor of d, and is the first policy optimization algorithm with polynomial sample complexity for general function approximation.
While policy optimization algorithms have played an important role in recent empirical success of Reinforcement Learning (RL), the existing theoretical understanding of policy optimization remains rather limited -- they are either restricted to tabular MDPs or suffer from highly suboptimal sample complexity, especial in online RL where exploration is necessary. This paper proposes a simple efficient policy optimization framework -- Optimistic NPG for online RL. Optimistic NPG can be viewed as a simple combination of the classic natural policy gradient (NPG) algorithm [Kakade, 2001] with optimistic policy evaluation subroutines to encourage exploration. For $d$-dimensional linear MDPs, Optimistic NPG is computationally efficient, and learns an $\varepsilon$-optimal policy within $\tilde{O}(d^2/\varepsilon^3)$ samples, which is the first computationally efficient algorithm whose sample complexity has the optimal dimension dependence $\tildeΘ(d^2)$. It also improves over state-of-the-art results of policy optimization algorithms [Zanette et al., 2021] by a factor of $d$. In the realm of general function approximation, which subsumes linear MDPs, Optimistic NPG, to our best knowledge, stands as the first policy optimization algorithm that achieves polynomial sample complexity for learning near-optimal policies.