The Trajectory Count Is Not the Training Bill
TL;DR for operators Generating fresh training trajectories can be expensive. Reusing gradient information from previous policy updates may reduce that expense, but changes in the policy make earlier estimates increasingly difficult to trust. In Variance-Reduced Policy Gradient is Nearly Minimax-Optimal, Leonardo Cesani, Matteo Papini, and Marcello Restelli1 establish that a class of first-order, actor-only policy-gradient algorithms can achieve an expected final-policy suboptimality gap of at most $\psi+\epsilon$ using $\widetilde{\mathcal O}(\epsilon^{-2})$ trajectories, under specified assumptions. A matching lower bound establishes the optimality of the target-accuracy exponent, up to logarithmic factors. ...