A Concentration Bound for TD(0) with Function Approximation
We derive a concentration bound of the type `for all $n \geq n_0$ for some $n_0$' for TD(0) with linear function approximation. We work with online TD learning with samples from a single sample path of the underlying Markov chain. This makes our analysis significantly different from offline TD learning or TD learning with access to independent samples from the stationary distribution of the Markov chain. We treat TD(0) as a contractive stochastic approximation algorithm, with both martingale and Markov noises. Markov noise is handled using the Poisson equation and the lack of almost sure guarantees on boundedness of iterates is handled using the concept of relaxed concentration inequalities.
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 of Contractive Stochastic Approximation: Additive and Multiplicative Noise
In this paper, we establish maximal concentration bounds for the iterates generated by a stochastic approximation (SA) algorithm under a contractive operator with respect to some arbitrary norm (for example, the $\ell_\i…
Q-LearningConcentration analysis of multivariate elliptic diffusion processes
We prove concentration inequalities and associated PAC bounds for continuous- and discrete-time additive functionals for possibly unbounded functions of multivariate, nonreversible diffusion processes. Our analysis relie…
Concentration 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)Tight Bounds on $\ell_1$ Approximation and Learning of Self-Bounding Functions
We study the complexity of learning and approximation of self-bounding functions over the uniform distribution on the Boolean hypercube ${0,1}^n$. Informally, a function $f:{0,1}^n \rightarrow \mathbb{R}$ is self-boundin…