Low-rank structure is a common implicit assumption in many modern reinforcement learning (RL) algorithms. For instance, reward-free and goal-conditioned RL methods often presume that the successor measure admits a low-rank representation. In this work, we challenge this assumption by first remarking that the successor measure itself is not approximately low-rank. Instead, we demonstrate that a low-rank structure naturally emerges in the shifted successor measure, which captures the system dynamics after bypassing a few initial transitions. We provide finite-sample performance guarantees for the entry-wise estimation of a low-rank approximation of the shifted successor measure from sampled entries. Our analysis reveals that both the approximation and estimation errors are primarily governed by a newly introduced quantitity: the spectral recoverability of the corresponding matrix. To bound this parameter, we derive a new class of functional inequalities for Markov chains that we call Type II Poincar\'e inequalities and from which we can quantify the amount of shift needed for effective low-rank approximation and estimation. This analysis shows in particular that the required shift depends on decay of the high-order singular values of the shifted successor measure and is hence typically small in practice. Additionally, we establish a connection between the necessary shift and the local mixing properties of the underlying dynamical system, which provides a natural way of selecting the shift. Finally, we validate our theoretical findings with experiments, and demonstrate that shifting the successor measure indeed leads to improved performance in goal-conditioned RL.

翻译：低秩结构是现代许多强化学习算法中常见的隐含假设。例如，无奖励与目标条件强化学习方法通常假设后继测度允许低秩表示。在本研究中，我们首先指出后继测度本身并非近似低秩，从而挑战了这一假设。相反，我们证明低秩结构自然出现在移位后继测度中，该测度捕捉了绕过若干初始转移后的系统动态。我们为从采样条目中估计移位后继测度的低秩近似提供了有限样本性能保证，分析了逐项估计的误差界。我们的分析表明，近似误差与估计误差主要受一个新引入的参量控制：对应矩阵的谱可恢复性。为界定该参数，我们推导出一类新的马尔可夫链函数不等式，称为II型庞加莱不等式，并借此量化实现有效低秩近似与估计所需的移位量。该分析特别表明，所需移位量取决于移位后继测度高阶奇异值的衰减程度，因此在实践中通常较小。此外，我们建立了必要移位量与底层动态系统局部混合特性之间的联系，这为选择移位量提供了自然依据。最后，我们通过实验验证了理论发现，并证明对后继测度进行移位确实能提升目标条件强化学习的性能。