2021/03/30 by Shaocong Ma, Ma, Shaocong, Ziyi Chen +5 · 1 citation
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Reinforcement Learning in Robotics #Smart Grid Energy Management
paper · pdf · doi:10.48550/arxiv.2103.16377
openalex publication_date 2021/03/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Greedy-GQ is a value-based reinforcement learning (RL) algorithm for optimal\ncontrol. Recently, the finite-time analysis of Greedy-GQ has been developed\nunder linear function approximation and Markovian sampling, and the algorithm\nis shown to achieve an \ε-stationary point with a sample complexity in\nthe order of \O(\ε-3). Such a high sample complexity is due\nto the large variance induced by the Markovian samples. In this paper, we\npropose a variance-reduced Greedy-GQ (VR-Greedy-GQ) algorithm for off-policy\noptimal control. In particular, the algorithm applies the SVRG-based variance\nreduction scheme to reduce the stochastic variance of the two time-scale\nupdates. We study the finite-time convergence of VR-Greedy-GQ under linear\nfunction approximation and Markovian sampling and show that the algorithm\nachieves a much smaller bias and variance error than the original Greedy-GQ. In\nparticular, we prove that VR-Greedy-GQ achieves an improved sample complexity\nthat is in the order of \O(\ε-2). We further compare the\nperformance of VR-Greedy-GQ with that of Greedy-GQ in various RL experiments to\ncorroborate our theoretical findings.\n