2018/07/09 by Hugo Penedones, Damien Vincent, Penedones, Hugo +10
Computer Science · Mathematics · Social Sciences · #Electoral Systems and Political Participation #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods #Privacy-Preserving Technologies in Data #Reinforcement Learning in Robotics
paper · pdf · doi:10.48550/arxiv.1807.03064
openalex publication_date 2018/07/09 · openalex created_date 2022/08/04 · openalex updated_date 2026/07/28
Temporal-Difference learning (TD) [Sutton, 1988] with function approximation\ncan converge to solutions that are worse than those obtained by Monte-Carlo\nregression, even in the simple case of on-policy evaluation. To increase our\nunderstanding of the problem, we investigate the issue of approximation errors\nin areas of sharp discontinuities of the value function being further\npropagated by bootstrap updates. We show empirical evidence of this leakage\npropagation, and show analytically that it must occur, in a simple Markov\nchain, when function approximation errors are present. For reversible policies,\nthe result can be interpreted as the tension between two terms of the loss\nfunction that TD minimises, as recently described by [Ollivier, 2018]. We show\nthat the upper bounds from [Tsitsiklis and Van Roy, 1997] hold, but they do not\nimply that leakage propagation occurs and under what conditions. Finally, we\ntest whether the problem could be mitigated with a better state representation,\nand whether it can be learned in an unsupervised manner, without rewards or\nprivileged information.\n