High-probability sample complexities for policy evaluation with linear function approximation

arXiv:2305.19001v2 Announce Type: replace-cross
Abstract: This paper is concerned with the problem of policy evaluation with linear function approximation in discounted infinite horizon Markov decision processes. We investigate the sample complexities required to guarantee a predefined estimation error of the best linear coefficients for two widely-used policy evaluation algorithms: the temporal difference (TD) learning algorithm and the two-timescale linear TD with gradient correction (TDC) algorithm. In both the on-policy setting, where observations are generated from the target policy, and the …

abstract algorithms approximation arxiv complexities cs.it cs.lg decision error evaluation function horizon linear markov math.it math.oc math.st paper policy probability processes sample stat.ml stat.th type