  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 demonstrate that the algorithm effectively
balances computational complexity and sample efficiency for policy evaluation
in a benchmark task and a high-dimensional energy allocation domain.
