Introduction
Reinforcement Learning (RL) in tabular settings often faces the "curse of dimensionality." To learn an $\epsilon$-optimal policy in a Markov Decision Process (MDP) with $S$ states and $A$ actions, standard methods typically require a number of samples proportional to the product $SA$. In many real-world applications, $S$ and $A$ are massive, rendering traditional tabular approaches impractical.
Fortunately, many high-dimensional systems possess a latent low-rank structure, meaning the $S \times A$ matrix representing the $Q$-function can be compressed. While previous research has attempted to exploit this structure, existing algorithms often rely on restrictive assumptions, such as "coherence" (where information is spread evenly across the matrix) or the prior knowledge of "anchor" states—representative rows or columns that span the matrix. This paper introduces LoRa-PI (Low-Rank Policy Iteration), a model-free algorithm designed to overcome these limitations by discovering important states on the fly.
The LoRa-PI Framework
LoRa-PI follows the classic Approximate Policy Iteration (API) framework, alternating between Policy Evaluation (estimating the $Q$-function of the current policy) and Policy Improvement (updating the policy to be greedy with respect to that estimate). The core innovation of the paper lies in the Policy Evaluation step, which is powered by a novel Leveraged Matrix Estimation (LME) algorithm.
Leveraged Matrix Estimation (LME)
LME operates in two distinct phases to reconstruct the $Q$-matrix efficiently:
- Phase 1 (Exploration): The algorithm samples entries of the $Q$-matrix uniformly at random. It then employs a spectral method to estimate the leverage scores of the rows and columns. These scores act as a structural "heat map," identifying which states and actions carry the most information.
- Phase 2 (Exploitation): Using the estimated leverage scores, the algorithm adaptively samples specific "anchor" rows and columns. It then performs a CUR-like matrix completion—a technique that reconstructs the full large matrix using only these representative components.
Crucially, LoRa-PI is both model-free (it does not attempt to learn transition probabilities) and parameter-free (it does not require prior knowledge of the matrix's rank or its level of "spikiness").
Theoretical Insights
Spikiness vs. Coherence
A major theoretical contribution of this work is the shift from coherence to spikiness. Standard matrix completion often fails if a matrix is "spiky" (where information is concentrated in a few entries). The authors prove that LoRa-PI’s entry-wise guarantees depend on spikiness rather than coherence. Because spikiness is a much milder condition, LoRa-PI is applicable to a significantly wider variety of MDPs than previous methods.
Policy Iteration vs. Value Iteration
The paper provides a compelling argument for the use of Policy Iteration (PI) over Value Iteration (VI) in low-rank settings. In VI, the sequence of matrices generated can pass through regions with extremely high condition numbers, leading to numerical instability. In contrast, PI deals with a finite set of deterministic policies that are generally better-behaved, providing a more stable path to convergence.
Experimental Results
The authors evaluated LoRa-PI using synthetic low-rank MDPs, ranging from toy 2-state models to large-scale environments with $S=1000$ and $A=1000$ (representing a $10^6$ entry matrix) with a latent rank of $d=4$ or $d=5$.
- Sample Complexity: LoRa-PI achieves a sample complexity of $\tilde{O}\left(\frac{S+A}{\text{poly}(1-\gamma)\epsilon^2}\right)$. This is order-optimal in $S$, $A$, and $\epsilon$, matching the best known theoretical bounds while operating under significantly milder assumptions.
- Accuracy and Robustness: In numerical experiments, LME consistently outperformed uniform sampling and standard SVD-based methods. Even when half the sample budget was dedicated solely to estimating leverage scores, the resulting matrix reconstruction was far more accurate than "blind" uniform sampling. The algorithm successfully identified near-optimal policies in high-dimensional environments where standard tabular methods would require orders of magnitude more data.
Limitations and Future Directions
While LoRa-PI represents a significant step forward, the authors note some areas for improvement:
- Discount Factor Sensitivity: The current analysis shows a dependence on the discount factor $\gamma$ of $(1-\gamma)^{-8}$. This is higher than the $(1-\gamma)^{-3}$ typically seen in model-based RL, likely due to the use of model-free Monte-Carlo estimators.
- Model-Based Extensions: Future work may explore a model-based version of this approach to improve the dependence on the horizon and discount factor.
- Real-World Application: While the paper addresses "approximately" low-rank MDPs in its appendix, further testing on real-world datasets where the rank is not strictly defined remains a priority for future research.
Summary updated