Defensive policy gradient improves learning speed with weaker assumptions
Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds
Machine Learning
Summary
Finding good strategies in decision-making problems often requires testing many options, which can be slow. This paper introduces a new method, Defensive Policy Gradient, that speeds up learning without relying on unrealistic assumptions about uncertainty. The authors show it matches the best known speed in theory and prove that this speed is likely the fastest possible under similar conditions. Their work clarifies why this new method is genuinely better than traditional approaches in terms of efficiency.
What this means in practice
- •For reinforcement learning engineers: Use defensive importance sampling in policy gradient algorithms to achieve faster convergence without assuming bounded importance weight variance.
- •For robotics control teams: Incorporate the Defensive Policy Gradient method to improve data efficiency when training control policies in uncertain or complex environments.
A theory result. No direct application yet.
Authors
Gabor Paczolay, Matteo Papini, Alberto Maria Metelli, Istvan Harmati, Marcello Restelli
Abstract
Several variance-reduced versions of REINFORCE based on importance sampling achieve an improved $O(ε^{-3})$ sample complexity to find an $ε$-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 $Θ(ε^{-4})$ with bounded-variance one-policy feedback and $Θ(ε^{-3})$ with mean-square-smooth coupled two-policy feedback. Under standard policy-regularity conditions, REINFORCE and \algo realize the corresponding oracle conditions and attain the $O(ε^{-4})$ and $O(ε^{-3})$ upper bounds, respectively. Although the lower bounds do not apply directly to the classical MDP interaction model in which these algorithms operate, this correspondence provides oracle-level evidence that the faster rate of \algo is optimal and genuinely separated from that of vanilla policy gradient.