Central limit theorems are obtained for the PARMSR (perturbation analysis Robbins-Monro single run) algorithm with averaging, updated either after every regenerative cycle or after every fixed-length observation period, for one-dependent regenerative processes. These stochastic approximation algorithms with averaging turn out to have identical limiting behavior, i.e., the same convergence rate and the same limit covariance matrix, when the convergence is expressed in terms of the total observation time of the system (or the total computing budget in the case of a simulation). Under certain assumptions, these algorithms are asymptotically efficient, in the sense that both their convergence rate and limit covariance are optimal. The strong convergence rate of the usual PARMSR algorithm updated after every fixed length observation period is established using a limit theorem on double array martingales. This is the key step for obtaining the asymptotic efficiency of the algorithms with averaging and has interest in its own right.