**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:
$$
\Vert \widetilde{Q}^\pi_{\tau}(\mathcal{I},\mathcal{J})^\dagger \Vert_{\mathrm{op}} = \frac{1}{\sigma_d(\widetilde{Q}^\pi_{\tau}(\mathcal{I},\mathcal{J}))} \leq \frac{1}{\sigma_d(Q^\pi(\mathcal{I},\mathcal{J})) - \Vert \widetilde{Q}^\pi_{\tau}(\mathcal{I},\mathcal{J}) - Q^\pi(\mathcal{I},\mathcal{J}) \Vert_{\mathrm{op}}}
$$
(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