← Back to papers
2018 IJCAI IJCAI 2018

Finite Sample Analysis of LSTD with Random Projections and Eligibility Traces

Abstract

Policy evaluation with linear function approximation is an important problem in reinforcement learning. When facing high-dimensional feature spaces, such a problem becomes extremely hard considering the computation efficiency and quality of approximations. We propose a new algorithm, LSTD(lambda)-RP, which leverages random projection techniques and takes eligibility traces into consideration to tackle the above two challenges. We carry out theoretical analysis of LSTD(lambda)-RP, and provide meaningful upper bounds of the estimation error, approximation error and total generalization error. These results demonstrate that LSTD(lambda)-RP can benefit from random projection and eligibility traces strategies, and LSTD(lambda)-RP can achieve better performances than prior LSTD-RP and LSTD(lambda) algorithms.

🌉 Interdisciplinary Bridge — Machine Learning and Reinforcement Learning
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Interdisciplinary, Machine Learning, Mathematics & Optimization, Reinforcement Learning, Robotics, Security & Privacy
🐣 Hot Topic Early Bird — temporal difference learning

Authors

Haifang Li , Yingce Xia , Wensheng Zhang

Topics

Machine Learning > Optimization & Theory > Statistical Learning Machine Learning > Optimization & Theory > Theory Reinforcement Learning > Methods > Deep RL Reinforcement Learning > Methods > Policy Learning Reinforcement Learning > Applications > Value Iteration Machine Learning > Learning Types > Reinforcement Learning

Keywords

temporal difference learning policy evaluation function approximation finite sample analysis generalization error linear function approximation random projection eligibility trace least squares temporal difference
Download PDF

Related papers

Semi-Supervised Multi-Modal Learning with Incomplete Modalities 2018
High-dimensional Similarity Learning via Dual-sparse Random Projection 2018
FISH-MML: Fisher-HSIC Multi-View Metric Learning 2018
Generative Warfare Nets: Ensemble via Adversaries and Collaborators 2018
Semi-Supervised Optimal Margin Distribution Machines 2018