Incremental Truncated LSTD. (arXiv:1511.08495v1 [cs.LG])

Balancing between computational efficiency and sample efficiency is an important goal in reinforcement learning. Temporal difference (TD) learning algorithms stochastically update the value function, with a linear time complexity in the number of features, whereas least-squares temporal difference (LSTD) algorithms are sample efficient but can be quadratic in the number of features. In this work, we develop an efficient incremental low-rank LSTD({\lambda}) algorithm that progresses towards the goal of better balancing computation and sample efficiency. The algorithm reduces the computation and storage complexity to the number of features times the chosen rank parameter while summarizing past samples efficiently to nearly obtain the sample complexity of LSTD. We derive a simulation bound on the solution given by truncated low-rank approximation, illustrating a bias-variance trade-off dependent on the choice of rank. We finally demonstrate sample complexity improvements over temporal difference approaches for policy evaluation in two benchmark tasks: mountain car and pendulum.

from cs.AI updates on arXiv.org http://ift.tt/1l14BRH
via IFTTT