A Statistical Analysis of Polyak-Ruppert Averaged Q-learning

Code

• github.com/lx10077/AveQLearning
  Officialnone★ 3

Abstract

We study Q-learning with Polyak-Ruppert averaging in a discounted Markov decision process in synchronous and tabular settings. Under a Lipschitz condition, we establish a functional central limit theorem for the averaged iteration Q_T and show that its standardized partial-sum process converges weakly to a rescaled Brownian motion. The functional central limit theorem implies a fully online inference method for reinforcement learning. Furthermore, we show that Q_T is the regular asymptotically linear (RAL) estimator for the optimal Q-value function Q^* that has the most efficient influence function. We present a nonasymptotic analysis for the _ error, E\|Q_T-Q^*\|_, showing that it matches the instance-dependent lower bound for polynomial step sizes. Similar results are provided for entropy-regularized Q-learning without the Lipschitz condition.

Tasks

Reproductions