On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergence
We provide non-asymptotic bounds for the well-known temporal difference learning algorithm TD(0) with linear function approximators. These include high-probability bounds as well as bounds in expectation. Our analysis suggests that a step-size inversely proportional to the number of iterations cannot guarantee optimal rate of convergence unless we assume (partial) knowledge of the stationary distribution for the Markov chain underlying the policy considered. We also provide bounds for the iterate averaged TD(0) variant, which gets rid of the step-size dependency while exhibiting the optimal rate of convergence. Furthermore, we propose a variant of TD(0) with linear approximators that incorporates a centering sequence, and establish that it exhibits an exponential rate of convergence in expectation. We demonstrate the usefulness of our bounds on two synthetic experimental settings.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Approximation beats concentration? An approximation view on inference with smooth radial kernels
Positive definite kernels and their associated Reproducing Kernel Hilbert Spaces provide a mathematically compelling and practically competitive framework for learning from data. In this paper we take the approximation…
Concentration bounds for temporal difference learning with linear function approximation: The case of batch data and uniform sampling
We propose a stochastic approximation (SA) based method with randomization of samples for policy evaluation using the least squares temporal difference (LSTD) algorithm. Our proposed scheme is equivalent to running regul…
Multi-Armed BanditsNews RecommendationregressionTraffic Signal ControlConcentration of Contractive Stochastic Approximation and Reinforcement Learning
Using a martingale concentration inequality, concentration bounds `from time $n_0$ on' are derived for stochastic approximation algorithms with contractive maps and both martingale difference and Markov noises. These are…
Q-Learningreinforcement-learningReinforcement LearningReinforcement Learning (RL)Regularized Weighted Low Rank Approximation
The classical low rank approximation problem is to find a rank $k$ matrix $UV$ (where $U$ has $k$ columns and $V$ has $k$ rows) that minimizes the Frobenius norm of $A - UV$. Although this problem can be solved efficient…
A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging
Polyak-Ruppert averaging is a widely used technique to achieve the optimal asymptotic variance of stochastic approximation (SA) algorithms, yet its high-probability performance guarantees remain underexplored in general …
Q-Learning