Research map / Reinforcement learning / MDPs and planning

Shift Before You Learn: Enabling Low-Rank Representations in Reinforcement Learning

NeurIPS 2025 · Reinforcement learning › MDPs and planning · approach: Function approximation in RL theory · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows the successor measure is not approximately low-rank but its k-shifted version is, gives finite-sample entrywise guarantees for estimating its low-rank SVD approximation via spectral recoverability and Type II Poincaré inequalities, and validates shifting in tabular goal-conditioned RL.

Problem

Explaining why low-rank structure arises in successor measures of MDPs and when it yields accurate, learnable entrywise estimates; the standard successor measure is full-rank-like and hard to estimate with entrywise guarantees.

Approach

Shift the successor measure by k steps (P^k(I-γP)^{-1}) so that its low-rank structure emerges from local mixing; introduce spectral recoverability (inverse of max_x sum_i σ_i ψ_i(x)^2) and Type II Poincaré inequalities to bound the required shift and give entrywise estimation guarantees for truncated SVD estimators.

Key results

• Shifted successor measure has sharper singular value decay and its low-rank approximation error decreases as shift k increases, while the unshifted successor measure is not approximately low-rank.
• With an oracle successor measure, a temporal shift improves goal-reaching performance, especially combined with low-rank approximation; a moderate shift k=3 gives the best performance in data-limited TD experiments with rank 40.
• For a four-room chain, ||P^k||_{2,inf}^2 is bounded by (min_i nu(G_i))^{-1} + (1-min_i lambda_i)^k nu_min^{-1}, so the required shift scales as log(n) for expander blocks versus mixing time n log n.

Measured effects reported in the paper

Surprising findings

• Larger shifts degrade performance when successor measures are learned via TD from data, due to longer-horizon estimation error in low-data regimes.
• The successor measure itself is not approximately low-rank, since its singular values are sandwiched by those of P^k, so the low-rank structure only appears after shifting.

Limitations

• Results restricted to tabular MDPs with i.i.d. generative-model data; no exploration analysis.
• Downstream policy optimization guarantees for greedy policies are not established.
• Only SVD-based low-rank approximation was tested empirically; function approximation extension left open.

Experimental setup

Datasets: Medium PointMaze transitions (offline dataset)

Benchmarks: Medium PointMaze (discrete, 104 states, 4 actions)

Metrics: accuracy (exact goal reaching probability) relaxed accuracy (reaching within two steps of goal) entrywise approximation error (2->inf norm)

Baselines: unshifted successor measure (k=0) oracle successor measure HIQL

Builds on: successor representation Eckart-Young-Mirsky theorem leave-one-out analysis for matrix completion temporal difference learning

Closest papers by meaning

• The Limits of Transfer Reinforcement Learning with Latent Low-rank Structure (NeurIPS 2024 · similarity 0.90)
• Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimation (NeurIPS 2024 · similarity 0.89)
• Reward-Consistent Dynamics Models are Strongly Generalizable for Offline Reinforcement Learning (ICLR 2024 · similarity 0.88)
• Compositional Conservatism: A Transductive Approach in Offline Reinforcement Learning (ICLR 2024 · similarity 0.87)
• Composite Flow Matching for Reinforcement Learning with Shifted-Dynamics Data (NeurIPS 2025 · similarity 0.87)
• Diffusion Spectral Representation for Reinforcement Learning (NeurIPS 2024 · similarity 0.87)