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.

本文介绍了一种低秩 LSTD 算法，该算法能更好地平衡计算效率和采样效率，使过去的样本高效地实现对最少二乘法时间差分（LSTD）的采样复杂度，同时实现近似 LSTD 的样本复杂度。我们在模拟中给出了关于截断低秩逼近所得解的模拟界限，这表明一个偏差 - 方差折衷需要依赖秩的选择。我们证明了该算法在基准任务和高维能量分配领域的策略评估中有效地平衡了计算复杂性和采样效率。

增量式截断最小二乘法

Incremental Truncated LSTD

We consider LSTD($\lambda$), the least-squares temporal-difference algorithm
with eligibility traces algorithm proposed by Boyan (2002). It computes a
linear approximation of the value function of a fixed policy in a large Markov
Decision Process. Under a $\beta$-mixing assumption, we derive, for any value
of $\lambda \in (0,1)$, a high-probability estimate of the rate of convergence
of this algorithm to its limit. We deduce a high-probability bound on the error
of this algorithm, that extends (and slightly improves) that derived by Lazaric
et al. (2012) in the specific case where $\lambda=0$. In particular, our
analysis sheds some light on the choice of $\lambda$ with respect to the
quality of the chosen linear space and the number of samples, that complies
with simulations.

本文考虑 LSTD (λ) 算法，推导出了任意 λ 及 β-mixing 条件下该算法收敛速率的高概率估计及误差的高概率界，探究了 λ 值选择对线性空间质量和样本数的影响。

LSTD ($λ$) 的收敛速率和误差界

Rate of Convergence and Error Bounds for LSTD($λ$)

LSTD is a popular algorithm for value function approximation. Whenever the
number of features is larger than the number of samples, it must be paired with
some form of regularization. In particular, L1-regularization methods tend to
perform feature selection by promoting sparsity, and thus, are well-suited for
high-dimensional problems. However, since LSTD is not a simple regression
algorithm, but it solves a fixed--point problem, its integration with
L1-regularization is not straightforward and might come with some drawbacks
(e.g., the P-matrix assumption for LASSO-TD). In this paper, we introduce a
novel algorithm obtained by integrating LSTD with the Dantzig Selector. We
investigate the performance of the proposed algorithm and its relationship with
the existing regularized approaches, and show how it addresses some of their
drawbacks.

本文介绍了一种新的算法，通过将 LSTD 与 Dantzig Selector 结合，解决了 L1 正则化与 LSTD 整合的困难问题，该算法适用于高维问题。