Research map / Reinforcement learning / MDPs and planning
Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimation
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.
Proposes LoRa-PI, a model-free approximate policy iteration algorithm for low-rank MDPs whose policy evaluation uses LME, a leverage-score-based adaptive sampling and CUR completion with entry-wise guarantees depending on spikiness rather than coherence.
Problem
Learning an epsilon-optimal policy in MDPs whose (state, action) value matrices are low-rank, without prior knowledge of anchors, rank, coherence, spikiness, or condition number, and with sample complexity that scales well in S, A, epsilon.
Approach
Estimate leverage scores of the value matrix via a spectral method on uniform Monte-Carlo samples, use them to sample anchor rows/columns, then complete the matrix with an inverse-leverage-weighted CUR estimator; policy iteration with this evaluation yields entry-wise guarantees depending on spikiness, not coherence.
Key results
- LoRa-PI learns an epsilon-optimal policy with sample complexity roughly (S+A)/epsilon^2 up to poly(1-gamma) and log factors, with dependence on spikiness alpha and condition number kappa, order-optimal in S, A, epsilon under milder conditions than prior work.
- LME gives entry-wise guarantees that depend on spikiness rather than coherence, the first such result for somewhat coherent matrices as claimed.
- In synthetic experiments with S=A=1000 and rank 4, leverage-score anchors reduce entry-wise error relative to uniform anchors, per the paper's reported figures.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| choose anchors using leverage scores instead of uniformly | Matrix completion with leveraged anchors · Synthetic 1000×1000 rank-5 matrix | entrywise error | Helped |
| use standard SVD instead of CUR with well-chosen anchors | Matrix completion · Synthetic 1000×1000 rank-5 matrix | entrywise error | Hurt |
| choose anchors using leverage scores instead of uniformly | Value iteration and policy iteration with anchors · Synthetic low-rank MDPs, S=70, A=50 | entrywise error | Helped |
| choose anchors using leverage scores instead of uniformly | LoRa-VI · Synthetic low-rank MDPs, S=A=1000 | entrywise error | Helped |
| choose anchors uniformly instead of using leverage scores | LoRa-VI · Synthetic low-rank MDPs, S=A=1000 | entrywise error | Hurt |
| use full-matrix VI instead of VI with leveraged anchors | LoRa-VI · Synthetic low-rank MDPs, S=A=1000 | entrywise error | Hurt |
| choose anchors using leverage scores instead of uniformly | LoRa-PI · Synthetic low-rank MDPs, S=A=1000 | Frobenius error | Helped |
Surprising findings
- Value iteration with the same low-rank estimator can pass through matrices with very high condition number (about 2500 in a toy example), motivating policy iteration over value iteration.
Limitations
- The (1-gamma)^-8 dependence is far from the (1-gamma)^-3 ideal, attributed to the model-free Monte-Carlo estimator.
- Guarantees require spikiness and condition number of all deterministic policies' value matrices to be bounded by alpha and kappa.
- Experiments are small synthetic settings; the authors note possible performance gains with better pseudoinversion and sample allocation.
Experimental setup
Metrics: entry-wise error Frobenius error sample complexity
Baselines: Algorithm 1 of prior low-rank RL work (anchors known) LR-EVI nuclear norm minimization uniform-anchor CUR full-matrix value iteration
Builds on: approximate policy iteration CUR decomposition leave-one-out analysis for spectral methods
Closest papers by meaning
- Shift Before You Learn: Enabling Low-Rank Representations in Reinforcement Learning (NeurIPS 2025 · similarity 0.89)
- Low-Rank Adaptation for Critic Learning in Off-Policy Reinforcement Learning (NeurIPS 2026 · similarity 0.89)
- The Limits of Transfer Reinforcement Learning with Latent Low-rank Structure (NeurIPS 2024 · similarity 0.86)
- The Laplacian Keyboard: Beyond the Linear Span (NeurIPS 2026 · similarity 0.86)
- Robust Offline Reinforcement Learning with Linearly Structured $f$-Divergence Regularization (ICML 2025 · similarity 0.86)
- Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.