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

תקציר מקורי באנגליתarXiv:2610.03165v1 Announce Type: new Abstract: 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 assumption on the variance of the importance weights. In this paper, we propose the \algo (Defensive Policy Gradient) algorithm, based on defensive importance sampling, which achieves the same rate without any assumption on the variance of ordinary importance weights. We also establish lower bounds in a generalized black-box policy-optimization model that hides states and actions and permits parameter-dependent rewards. In this model, the optimal rates are $\Theta(\epsilon^{-4})$ with bounded-variance one-policy feedback and $\Theta(\epsilon^{-3})$ wit