TY - JOUR
T1 - Finite-time performance bounds and adaptive learning rate selection for two time-scale reinforcement learning
AU - Gupta, Harsh
AU - Srikant, R.
AU - Ying, Lei
N1 - Funding Information:
Research supported by ONR Grant N00014-19-1-2566, NSF Grants CPS ECCS 1739189, NeTS 1718203, CMMI 1562276, ECCS 16-09370, and NSF/USDA Grant AG 2018-67007-28379. Lei Ying’s work supported by NSF grants CNS 1618768, ECCS 1609202, IIS 1715385, ECCS 1739344, CNS 1824393 and CNS 1813392.
PY - 2019
Y1 - 2019
N2 - We study two time-scale linear stochastic approximation algorithms, which can be used to model well-known reinforcement learning algorithms such as GTD, GTD2, and TDC. We present finite-time performance bounds for the case where the learning rate is fixed. The key idea in obtaining these bounds is to use a Lyapunov function motivated by singular perturbation theory for linear differential equations. We use the bound to design an adaptive learning rate scheme which significantly improves the convergence rate over the known optimal polynomial decay rule in our experiments, and can be used to potentially improve the performance of any other schedule where the learning rate is changed at pre-determined time instants.
AB - We study two time-scale linear stochastic approximation algorithms, which can be used to model well-known reinforcement learning algorithms such as GTD, GTD2, and TDC. We present finite-time performance bounds for the case where the learning rate is fixed. The key idea in obtaining these bounds is to use a Lyapunov function motivated by singular perturbation theory for linear differential equations. We use the bound to design an adaptive learning rate scheme which significantly improves the convergence rate over the known optimal polynomial decay rule in our experiments, and can be used to potentially improve the performance of any other schedule where the learning rate is changed at pre-determined time instants.
UR - http://www.scopus.com/inward/record.url?scp=85077789911&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85077789911&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:85077789911
SN - 1049-5258
VL - 32
JO - Advances in Neural Information Processing Systems
JF - Advances in Neural Information Processing Systems
T2 - 33rd Annual Conference on Neural Information Processing Systems, NeurIPS 2019
Y2 - 8 December 2019 through 14 December 2019
ER -