Incremental Truncated LSTD
This work addresses computational bottlenecks in reinforcement learning for policy evaluation, offering a practical improvement but is incremental in nature.
The paper tackles the trade-off between computational and sample efficiency in reinforcement learning by developing an incremental low-rank LSTD(λ) algorithm, which reduces complexity to linear in features times rank while nearly matching LSTD's sample efficiency, as demonstrated in benchmark and high-dimensional tasks.
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(λ) 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.