Finite Sample Analysis of LSTD with Random Projections and Eligibility Traces
This work addresses computational challenges in reinforcement learning for high-dimensional feature spaces, offering an incremental improvement over existing methods.
The paper tackles policy evaluation in high-dimensional reinforcement learning by proposing LSTD(λ)-RP, which combines random projections and eligibility traces to improve computational efficiency and approximation quality, achieving better performance than prior algorithms with theoretical error bounds.
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($λ$)-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($λ$)-RP, and provide meaningful upper bounds of the estimation error, approximation error and total generalization error. These results demonstrate that LSTD($λ$)-RP can benefit from random projection and eligibility traces strategies, and LSTD($λ$)-RP can achieve better performances than prior LSTD-RP and LSTD($λ$) algorithms.