Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimation

Thank you for your review! Please find our responses below.

A. Comparison with other matrix estimation methods. As mentioned in Section B.1 of our general rebuttal, our work is based on recent progresses in analysis of matrix completion methods providing entrywise guarantees [1,8,9]. It remains an open question how more global convergence guarantees (in Frobenius or spectral norm) can be utilized effectively for RL, so we compare our work only with methods providing entrywise guarantees.

As you suggested, an alternative to our SVD-based approach would be to use nuclear norm minimization. The authors of [34] leveraged the guarantees for nuclear norm minimization from [9] for learning the $Q$-function. However, there are a few reasons why applying nuclear norm minimization is theoretically not straightforward in our setting:

• Approximate low-rank structure. Since our algorithm is policy iteration-based, our estimates $Q_{\tau}^\pi$ are only approximately low-rank. The result of [9] is based on non-convex optimization, and it is unclear how this approximation error influences the final guarantee of the algorithm. In contrast, a simpler analysis using SVD allows us to explicitly express our bounds in terms of the approximation error.
• Coherence-free subspace recovery. In our subspace recovery result (Theorem 4), we can bound the subspace error $\Vert U_{i,:} - \widehat{U}\_{i,:} O\_{\widehat{U}}\Vert\_{2}$ in terms of $\Vert U_{i,:}\Vert_2$. It is not clear whether the same can be achieved using current guarantees for nuclear norm minimization, which might instead show dependence on $\max_{i\in [S]} \Vert U_{i,:}\Vert_2$. We believe this would lead to additional incoherence constants appearing in the sample complexity of our algorithm.

We refer reviewer to Section C of our general rebuttal for a more detailed comparison with other methods employing matrix completion for RL.

B. Real-world experiments. We refer the reviewer to part B.1 of our response to Reviewer WY9t for a discussion on applying our algorithm to gym environments. Moreover, our paper serves more as a proof of concept to show that we can use active sampling to decrease the sample complexity of the problem. We believe that adapting our analysis for more practical, real-world settings by combining our sampling schemes with deep learning can lead to interesting results, but this is beyond the scope of this paper.

C. Our low rank assumption ($Q^\pi$ low rank for every deterministic policy $\pi$) is less restrictive than previously used assumptions. We refer the reviewer to part B.3 of our general rebuttal for a discussion about our assumptions.

Dear reviewer,

Thanks again for your review. We have answered your concerns and would be grateful to hear your thoughts. If you need further clarification or want to ask more questions, we would be happy to respond.

Best regards.

Thank you for your careful and insightful review! Please find our responses below.

A. Our low-rank matrix estimation method is novel. Thank you for raising concerns about the novelty of our matrix estimation method. We believe this is an important point to clarify, so we have included a discussion on the novelty of our matrix completion method in Section A of the general rebuttal.

B. Spikiness is always better than coherence. First, note that we not only substitute dependence in incoherence $\mu$ for spikiness $\alpha$ in our sample complexities but also remove the term $\mu^2$ completely (please see the table in the general rebuttal and the discussion preceding it). Moreover, the spikiness constant appears as a proxy for $\frac{\Vert Q\Vert_{\max}}{\sigma_d(Q)}$, which essentially quantifies the difficulty of recovering low-rank structure from single observations. This makes it a more intuitive parameter than incoherence, which depends on the Euclidean norm of the rows of the singular vector matrices. Assuming bounded spikiness is less restrictive than bounded incoherence because it always holds that $$ \alpha(Q) = \sqrt{SA}\frac{\Vert Q\Vert_{\max}}{\Vert Q\Vert_\textup{F}} \leq \sqrt{SA} \frac{\Vert U\Vert_{2\to\infty} \Vert Q\Vert_{\textup{op}} \Vert W \Vert_{2\to\infty}}{\Vert Q\Vert_\textup{F}} \leq \mu(Q)^2 d.

Dear reviewer,

Thanks again for your review. We have answered your concerns and would be grateful to hear your thoughts. If you need further clarification or want to ask more questions, we would be happy to respond.

Best regards.

1. Thank you for recognizing the improvements made by our algorithm. Indeed, one key takeaway is that our adaptive, learning-based approach offers stronger guarantees than uniform random sampling and can even match the performance of settings with prior knowledge of the problem structure.

2. Regarding the condition on $T$ and its dependence on $\sigma_d$ . First of all, we wish to clarify that by saying we do not know $\sigma_d$, we mean that our algorithm does not require as input $\sigma_d$ or any lower bound on it. For example, the number of samples per epoch in the algorithms in [34] and [35] depends on $\sigma_d$, while our algorithm does not. This allows our approach to work without prior knowledge of the parameters of $Q$-matrices which previous algorithms require. This is especially challenging in iterative settings like ours, where prior knowledge would need to include the parameters of all $Q^\pi$ matrices encountered until convergence.

Next, both papers ([34] and [35]) are based on the CUR approach, and we will explain why this approach requires assumptions on the number of samples $T$. In the proof of our Theorem 5 we need to make use of the following inequality:

(Note that for simplicity, we set $L=R=\mathrm{Id}$.) The second term in the denominator is an error term that scales with $1/\sqrt{T}$. Therefore, to ensure the expression above is positive, we require a condition of the form $T\gtrsim 1/\sigma_d^2(Q^\pi(\mathcal{I},\mathcal{J}))$. This condition is thus necessary for the analysis of any CUR-based methods, including [34].

Now, note that in [35] (e.g., Theorem 14 or Corollary 16 for finite $S,A$), the authors use a much stronger assumption: the discount factor $\gamma = O\left( \frac{\sigma_d^2(Q(\mathcal{I},\mathcal{J}))}{d^2 V_{\max}} \right)$, which must hold even in the high sample regime (for large $T$). In contrast, our analysis works for any value of $\gamma$.

2.1. Regarding small $\sigma_d$. We agree that a very small $\sigma_d$ should not drastically affect the guarantees. If $\sigma_d$ is very small and, without loss of generality, $\sigma_{d-1}$ is sufficiently large, one could set $d_{\mathrm{eff}} = d-1$ and obtain bounds that depend on $\sigma_{d-1}$ instead. However, ignoring $\sigma_d$ introduces an approximation error that depends on the incoherence of the $d$-th singular vectors. To safely disregard the recovery of the $d$-th singular value and its associated singular vectors, we must ensure that $\sigma_d$ is small and that the $d$-th singular vector is sufficiently incoherent. This contrasts with Frobenius/spectral norm guarantees, where neglecting terms corresponding to the $d$-th singular value leads only to an additive error of $\sigma_d$, regardless of the singular vectors. We are not aware of any method that can select the rank parameter $d$ to address these issues without assuming knowledge of singular vectors or the appropriate incoherence parameters.

3. Regarding incoherence and spikiness. While our algorithm's worst-case guarantees scale with $\mu^4$, we believe this comparison is not particularly useful. As shown in the table, in a general, non-adaptive setting, the guarantees typically scale with $\alpha^2 \mu^2$ . However, in this paper (following [35]), we demonstrate that adaptive sampling allows us to eliminate the dependence on the incoherence parameter $\mu$. On the other hand, the spikiness parameter $\alpha$ quantifies the difficulty of recovering the full low-rank structure. We believe that the dependence on $\alpha$ cannot be improved through different sampling methods and instead requires a novel matrix recovery method. We will discuss these issues further in the paper and clarify our concept of incoherent-free matrix recovery.

3.1. Regarding the dependence on the rank parameter $d$. We omit explicit mention of the rank parameter $d$ because the sample complexity scales as $d^3$ in all three CUR-based settings, including ours and those in [34,35]. We believe that the nuclear norm-based method used in Theorem 21 of [34] offers slightly better scaling, with $d^2$. We will clarify this further in our revised version of the manuscript

Thank you for your review! Please find our responses below.

A. Appearance of low-rank $Q$ matrices in the real world problems. Low-rank $Q$ matrices have been observed practically, as shown in Section 4.1 in [43] for a wide range of environments (Atari games). Motivated by this observation, further empirical studies and the first theoretical results assuming prior knowledge of the most informative states have been presented in [34,35]. We believe that our paper is well-motivated by the fact that it is the first theoretical paper proving nearly optimal entrywise guarantees with no prior knowledge of the problem structure.

Furthermore, we recognize that assumptions made for theoretical analysis are seldom completely true in real-world problems. For example, regarding the extensively studied framework of linear MDPs, there are very few real-world problems where such structure holds (with fixed feature vectors). Nonetheless, we believe that our analysis should be used as a proxy for real-world environments and can be practically useful even in settings with an approximately low-rank structure.

B. Coherence/spikiness always appear in real-world control problems. Coherence and spikiness are general properties of matrices that are of constant order in very specific settings, assuming that all entries of the matrix are approximately equally informative. We believe that making RL algorithms robust and independent of the specific environment-related quantities, such as incoherence, is an important challenge. In this work, we address this challenge for a class of low-rank $Q$ matrices by providing robust algorithm that ensures low error for a wide range of matrix instances.

C. Numerical simulations in gym environments. We refer the reviewer to part B.1 of our response to reviewer WY9t for a discussion on applying our algorithm to gym environments. Moreover, since the focus of our work is primarily theoretical, we believe that numerical simulations should complement main theoretical results and be applied in the most illustrative environments. Thus, we are not convinced that repeating the experiments of [35] in the gym environment would significantly strengthen our work.

D. Comparison with literature on low-rank $Q$-learning. For a comparison with past work, we refer the reviewer to Section C of our global rebuttal.

Dear reviewer,

Thanks again for your review. We have answered your concerns and would be grateful to hear your thoughts. If you need further clarification or want to ask more questions, we would be happy to respond.

Best regards.

Thank you for your valuable review and positive feedback! Please find our responses below.

A. We do not impose any constraints on the rank/spikiness of the original matrix. According to Theorem 1, we need number of samples $T = \widetilde{\Omega} \left( \frac{(S+A)}{(1-\gamma)^3} \frac{r_{\max}^2\kappa^2 SA}{\sigma_d^2(Q)} \right)$, and note that the second term can be upper bounded by $\alpha^2$ (for $\kappa,d=\Theta(1)$). Thus, the number of samples required for this theorem to hold does depend on the spikiness parameter $\alpha$. However, this does not indirectly impose constraints on the spikiness, since this result holds for any level of spikiness. We only require a higher sample complexity for instances with higher spikiness, which intuitively correspond to more difficult instances of matrices. Furthermore, note that we do not require knowledge of the spikiness parameter $\alpha$ when sufficiently many samples are provided.

B. Numerical experiments.

• Comparison with numerical simulations from [35]. Note that the algorithm used in the experimental section in [35] corresponds roughly to our LoRa-VI algorithm with uniform anchors presented in Appendix A.4. More precisely, choosing anchor states uniformly at random in the first stage of our algorithm recovers the algorithm in [35] (with the slight modification of using PI instead of VI, which we do for theoretical reasons as discussed in Section 3.3). Thus, all results obtained in [35] are obtainable within our framework as well since it incorporates a more general setting.

• Additional simulations. We want to emphasize that our main contributions in this paper are theoretical. However, we conducted four different experiments to show the practical relevance of our work. We agree that experimentally testing the dependence on rank, spikiness and condition number is an interesting direction. We will incorporate new experiments regarding these settings in the revised version of our paper.

C. On notation. We thank the reviewer for giving useful feedback about our notation. Here are answers to your questions:

• using $L,R$ and $\ell,r$ for different quantities: We denote an element $(i,j)$ of a matrix $M$ by $M_{i,j}$ in this paper. Thus, elements of the matrices $L$ and $R$ are denoted by $L_{i,j}$ and $R_{i,j}$, respectively. We will add a sentence explaining this in the notation section of the revised paper.
• subscript in line 285: The subscript $\square$ is not a typo. We use notation $\Omega_{\square}$ to denote elements in the square matrix formed by entries $\mathcal{I}\times \mathcal{J}$ in the skeleton of the matrix.
• regarding acronyms: We will add descriptions of the acronyms we use. Note that CUR is not an acronym.

Dear reviewer,

Thanks again for your review. We have answered your concerns and would be grateful to hear your thoughts. If you need further clarification or want to ask more questions, we would be happy to respond.

Best regards.