On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method
This addresses a theoretical bottleneck in reinforcement learning for researchers, offering improved convergence guarantees but is incremental as it builds on existing variance reduction techniques.
The paper tackles the issue of uncheckable assumptions in variance-reduced policy gradient methods by proposing a gradient truncation mechanism and a new method called TSIVR-PG, achieving sample complexities of $ ilde{\mathcal{O}}(ε^{-3})$ for finding an $ε$-stationary policy and $ ilde{\mathcal{O}}(ε^{-2})$ for global $ε$-optimality under specific assumptions.
Policy gradient (PG) gives rise to a rich class of reinforcement learning (RL) methods. Recently, there has been an emerging trend to accelerate the existing PG methods such as REINFORCE by the \emph{variance reduction} techniques. However, all existing variance-reduced PG methods heavily rely on an uncheckable importance weight assumption made for every single iteration of the algorithms. In this paper, a simple gradient truncation mechanism is proposed to address this issue. Moreover, we design a Truncated Stochastic Incremental Variance-Reduced Policy Gradient (TSIVR-PG) method, which is able to maximize not only a cumulative sum of rewards but also a general utility function over a policy's long-term visiting distribution. We show an $\tilde{\mathcal{O}}(ε^{-3})$ sample complexity for TSIVR-PG to find an $ε$-stationary policy. By assuming the overparameterizaiton of policy and exploiting the hidden convexity of the problem, we further show that TSIVR-PG converges to global $ε$-optimal policy with $\tilde{\mathcal{O}}(ε^{-2})$ samples.