Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds

Gabor Paczolay, Matteo Papini, Alberto Maria Metelli +2

Several variance-reduced versions of REINFORCE based on importance sampling achieve an improved $O({\epsilon }^{-3})$ sample complexity to find an $\epsilon$-stationary point, under an unrealistic…