Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning

Summary

This paper presents a detailed analysis of matrix estimation problems in low-rank bandit and low-rank RL scenarios. The authors investigate the effectiveness of spectral-based matrix estimation methods and demonstrate their ability to accurately recover the singular subspaces of the matrix with minimal entry-wise error. Building upon these findings, the paper introduces a regret minimization algorithm for low-rank bandit problems and a best policy identification algorithm for reward-free RL in low-rank MDPs.

Strengths

1. The paper tackles the challenging task of deriving the entry-wise error of low-rank matrix estimation, specifically focusing on the correlated noise case. This analysis extends existing results and enables the study of bandit and RL settings. The techniques employed, such as leave-one-out arguments and Poisson approximation, demonstrate technical prowess. 2. Despite being a theoretical paper, the writing is clear and easy to comprehend, enhancing its accessibility.

Weaknesses

1. The paper fails to address the necessity of deriving entry-wise error in low-rank matrix estimation for bandit and RL settings. In the context of low-rank bandit problems, the primary objective is to identify the best entry, such as the largest value, in the matrix as quickly as possible. Consequently, the emphasis should be on selecting the arm with the highest reward, rather than achieving a small entry-wise error for the entire matrix. Entries with very small values do not necessitate extensive exploration. Thus, caring about entry-wise error may lead to unnecessary over-exploration, which is not desirable in low-rank bandit or low-rank MDP settings. 2. In low-rank bandit and MDP scenarios, the focus should primarily be on minimizing regret. Several existing approaches have achieved minimax regret bounds in these settings. For instance, Kang et al. (2022) addressed a more general low-rank matrix bandit problem and proved a minimax regret of $O((n+m)\sqrt{T})$. Jain and Pal (2023) also considered a similar low-rank matrix bandit problem and used a similar entry-wise matrix estimation result to achieve a regret bound of $polylog(n+m)\sqrt{T}$ for the rank-1 case. Unfortunately, the paper only discusses sub-optimal approaches in the main body, while the superior results of these references are mentioned in the last section of the supplementary materials. 3. The lack of numerical experiments to evaluate the proposed regret minimization algorithm and compare it against benchmark methods in the literature is a notable drawback. Merely comparing regret upper bounds does not provide a comprehensive understanding of the algorithms' actual performance. It would be more convincing to include extensive numerical experiments that directly compare the regret achieved by different algorithms, thereby justifying the usefulness of deriving entry-wise error of low-rank matrix estimation in bandit and RL settings.

Questions

1. Could you elaborate on how deriving the entry-wise error of low-rank matrix estimation is justified in bandit and RL settings, providing detailed explanations and extensive numerical experiments? 2. In the discussion of related work, it is crucial to compare the paper's results with state-of-the-art approaches and provide a fair and objective analysis.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

No numerical experiments were provided.

Summary

The authors investigate matrix estimation in reinforcement learning and bandit settings with low-rank structures. They demonstrate the effectiveness of spectral-based methods in recovering matrix subspaces and minimizing entry-wise error. This enables the development of efficient RL algorithms tailored for low-rank bandits and Markov Decision Processes (MDPs). This paper is solid, supported by robust results and technically intriguing proofs. It builds upon the recent trend of examining entry-wise error bounds for matrix completion problems and extends it to dynamic settings like RL and bandits. While the guarantees may not be surprising and the algorithms largely follow an explore-and-commit approach, the authors introduce an interesting technique using Compound Poisson Noise to transform a non-i.i.d. problem into an i.i.d. problem, which may have a larger implication for other applications.

Strengths

- Theoretical Soundness - Compound Poisson Noise Reduction for MDP is interesting - Exploring the potential of entry-wise guarantees of matrix completion in a dynamic setting is in general interesting

Weaknesses

While acknowledging the efforts invested in developing the theory, the novelty of the research appears limited given the well-established techniques of entry-wise recovery and leave-one-out. Moreover, the current algorithms are constrained to explore-and-commit and (pseudo) i.i.d. sampling schemas, compared to adaptive algorithms such as UCB, due to the limitations of the theoretical guarantees.

Questions

How is the result for matrix completion with Poisson noise in this paper related to "Near-optimal entrywise anomaly detection for low-rank matrices with sub-exponential noise." In International Conference on Machine Learning, pp. 3154-3163. PMLR, 2021?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

I do not perceive any immediate potential negative social impact.

Summary

This paper provides a theoretical study of low-rank matrix estimation in three contexts: **Context 1**: in the case of standard matrix estimation with uniformly sampled entries, where the authors prove a sample complexity comparable to approximate recovery results of $\tilde{O}(m+n)$ (when the rank is $O(1)$), with the following two main differences compared to existing methods: a (makes the result easier). It is assumed the rank is known, and the function class restriction is based directly on an explicit low-rank assumption. b (makes the result much harder and stronger). the error is measured with the maximum norm rather than Frobenius norm or expected loss. Because of the general context of the paper which concerns mostly reinforcement learning (see other results below), these results are formulated as a reinforcement learning/bandit problem where the arms are arranged as pairs of integers and the matrix of rewards is assumed to be low-rank. However, note that independence of the noise components is required (cf. lines 689-693 in the supplementary). **Context 2.1** In this model, recovery guarantees are proved for estimating a low-rank transition matrix from observations of independent transitions. Here, the matrix must be square, with the dimension being equal to the number of states. **Context 2.2** In this more natural setting, we estimate the transition matrix from context 2.2 based only on full trajectories. Regret bounds proved in this case rely on the ergodicity of the Markov chain by splitting the expression of the average error over time into sums where the time steps are separated by a large number $\tau$, so that the distributions of the corresponding observations are approximately independent and distributed as the limiting distribution. Finally, the authors introduce a novel algorithm for performing reinforcement learning in a low-rank bandit setting. The algorithm works in epochs: at a given epoch, with each iteration providing a more and more refined estimate of a set of candidate arms. Whilst the set of candidate arms has more than 2 elements, the algorithm recommends a uniformly random arm, after the set of candidate arms degenerates to a single element, the algorithm keeps recommending that one. A bound is shown on the expected amount of time it takes to identify the best arm. This culminates in a gap-independent regret bound of $\tilde{O}(T^{1/2})$ for this case, which to the best of my knowledge, solves a highly significant open problem in the nascent theory of low-rank bandits. The proofs rely on an ingenious combination of existing ideas, with the most salient one being that of poison approximation: the matrix of observed rewards is approximated by a matrix with entries equal to $M_{i,j}T_i$ where $T_i$s are independent Poisson random variables. (this general technique has previously been introduced in [7)]. Then, concentration inequalities for such matrices are used in combination with bounds on the error in approximating the true matrix of observed rewards by this Poisson approximation. ==========Post-rebuttal======= My doubts have been adequately addressed in the rebuttal and I will keep my score of **strong accept**. I remain convinced this is an excellent paper. However, I do hope the authors will take the trouble to add more detailed derivations and also tone down the statements and claims of novelty over the lack of independence of the $E_{i,j}$. Indeed, since this is an impressive contribution that many readers will be interested in studying, it would be a great service to the community to make the paper as approachable as possible. ======== **References** [1] Nathan Srebro, "Rank, Trace-Norm and Max-Norm", COLT 2005. [2] Ohad Shamir, Shai Shalev-Shwartz. Matrix Completion with the Trace Norm: Learning, Bounding, and Transducing. JMLR 2014. [3] Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, Yuling Yan. Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization. SIAM journal of Optimization, 2020. [4] Prateek Jain, Soumyabrata Pal Online Low Rank Matrix Completion. ICLR 2023 [5] Sahand Negahban, Martin J. Wainwright. Restricted Strong Convexity and Weighted Matrix Completion: Optimal Bounds with Noise. JMLR 2012. [6] Mitzenmacher, Michael and Upfal, Eli. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge UNiversity Press 2017. [7] Yuxin Chen, Yujie Chi, Jianqing Fan, Cong Ma et al. Spectral Methods for data science: a statistical perspective.

Strengths

**1** This is an excellent contribution to the field: although I am not completely sure about the originality (especially that of theorem 1 as compared to other results in [5]) since I am not fully up to speed on the reinforcement learning theory, I think there is a good chance this is groundbreaking work. The algorithm of successive arm elimination is simple and elegant, with a nearly optimal regret bound. Whilst it is true that the fact that explicit rank restriction is used (as opposed to, for instance, nuclear norm regularization) makes the matrix completion results seem a little trivial, the regret bound in the RL setting seems to be new and is a natural starting point to kick-start this branch of research. **2** Aside from very minor things (mostly related to the contextualization of the work within the related works), this paper is excellently written. The proofs are very well organized, to an extent which is demonstrably superior to the majority of accepted papers I have reviewed. The authors clearly organize the proof into steps (Poisson approximation, dilation trick, general concentration inequalities for Poisson matrices, specific calculations for the Poisson approximation to this problem, bounds on the error introduced by the approximation). Each parts of the proofs contain references to existing literature where relevant.

Weaknesses

**1** One thing that threw me off a bit was the lack of contextualization and explanation of the first results (Theorem 1). In particular, on lines 90 to 92 (see also lines 125 to 130), it seems like the authors want to distance their results from standard matrix completion results by hinting that noise components are not independent (they are not stated to be independent at that point), when in fact it also seems this setting is exactly matrix completion with an explicit rank restriction. Indeed, lines 689-693 in the supplementary appear to suggest independence **is** required. It would be quite appropriate to compare to existing results in this case as well. For a bounded loss, a similar sample complexity goes all the way back to [1] for approximate recovery with a bounded loss. For connected problems with the trace norm, we also have the result of [2] and the extremely impressive result of [3], which is much stronger than the results presented here due to improved dependence on the variance of the noise. Similarly, I am also a bit confused by the statement on line 334 that "we do not assume the transition matrices are constructed based on a given restricted class of functions" since it appears there is a low rank assumption in the work. **2** Similarly, I feel like the related works on low-rank bandits missed some of the recent literature [4]. **3** In the low rank bandit result, the algorithm eventually recommends the same arm, that is, the same entry, all the time. This is highly restrictive in a recommender systems context: the algorithm isn't even able to identify the best item for each user, only the best user-item combination... **References** [1] Nathan Srebro, "Rank, Trace-Norm and Max-Norm", COLT 2005. [2] Ohad Shamir, Shai Shalev-Shwartz. Matrix Completion with the Trace Norm: Learning, Bounding, and Transducing. JMLR 2014. [3] Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, Yuling Yan. Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization. SIAM journal of Optimization, 2020. [4] Prateek Jain, Soumyabrata Pal Online Low Rank Matrix Completion. ICLR 2023 [5] Sahand Negahban, Martin J. Wainwright. Restricted Strong Convexity and Weighted Matrix Completion: Optimal Bounds with Noise. JMLR 2012. [6] Mitzenmacher, Michael and Upfal, Eli. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge UNiversity Press 2017. [7] Yuxin Chen, Yujie Chi, Jianqing Fan, Cong Ma et al. Spectral Methods for data science: a statistical perspective.

Questions

**1** Could you clarify what you mean in lines 90 to 92 and lines 125 to 130 regarding the independence of the noise? Although I can find such an example in the literature, it is seems unlikely to me that this result (corollary 1) is new. Is there any similar result for matrix completion with the maximum absolute value of the error as the performance measure? Perhaps in [5]? **2** Could you clarify to what extent theorem 1 and its proof differs from the existing results and proofs from [7] (what is the most similar result to Theorem 1 which was proved in [7])? **3** ( I would really like to have the answer to this!) In lines 957 to 958, could you explain clearly ho you arrive at the equation on the bottom of page 33? I am a little stuck there, I need far more details than what is written as it seems you are using another equation from the same page without stating it. Also, did you really mean $\sigma_{2r}(M)$ in the denominator or did you mean $\sigma_r(M)$ instead (which is the quantity mentioned in the textual explanation on the line above)? **4** Could you give a few more details in the page 32? It feels the reference to Lemma 4.16 in other work breaks the reader's momentum, it would be nice to write down the lemma again in the paper. Indeed, I think it is a key step in the argument that allows you to obtain this fascinating result with the max norm (theorem 1). **5** Line 1098, second equation, do you mean $\ell+2$ instead of $\ell-2$ in the exponent **6** In the second to last equation on line 1114 (page 42) should it not be $\lceil \log_2(1/\Delta_{min})\rceil$ or $\log_2(e/\Delta_{min})$ instead of $\log_2(1/\Delta_{min})$? Again, I see that you are not being too careful about constants in general but there is no $O$ notation in this particular inequality. **7** In line 90, you say that the entries are sampled "uniformly at random for simplicity", do you in fact require this assumption in the proof of the theorem? (based on existing results for matrix completion with explicit low-rank assumptions, it would seem that this is not required. In general, it would be nice to add a bit more details to each of the theorem statements to clarify the assumptions. **8** Is Lemma 25 known? It seems very general and standard, I feel like it is probably in some well known book. **Minor comments/typos** A citation would be nice on lines 226-227 It could be nice to reorganize sections C1 and C2.2 a little bit. For instance, in line 707, you are using a lemma which comes from a subsection that concerns the Markov problem when proving a result about Model 1, it would be nice to make it clear that Lemma 22 doesn't, in fact, require any proof elements from the context of Model 2. In the same vein, I think it would be nice, for completeness, to write down the proof of Lemma 22, even if it is very similar to the proof of Theorem 5.7 in [6]. It is a bit funny that the proof of Lemma 21 is there but not that of Lemma 22 since Lemma 21 is pretty much trivial whilst Lemma 22 is a bit more advanced. Making the paper fully self contained would be a nice way to get even more citations by further improving the encylopaedic quality of the appendix. Line 1098 (page 41), second equation, I think you mean $4e$ not $2\sqrt{e}$, though I understand you are not being too bothered about constants given the final results are in $O$ notation In the last inequality of the sequence of inequalities on page 43, and in line 1124 I think it would be nice to remind the reader of the definition of $\bar{\Delta}$ from line 239, since it is instrumental in deriving the equality on line 1124, which unfortunately relies on the fact that the recommendations are uniformly at random in $[m]\times [n]$ instead of the more natural $\mathcal{A}_{\ell}$. Typos: Line 951: missing "the" Line 706: extra square bracket inside the equation. In line 727, I recommend adding more details for ho you prove that $\tau(\epsilon)\leq \tau$, it takes quite a bit of massaging of previous equations to get this with the correct constant! Line 741: be joint probability==> be the joint probability line 742 "for Poisson and multinomial model ==> "for the Poisson and multinomial models" line 793 (proof of Lemma 25): "variables" ==> "variable" line 957 add "following" before "condition Line 980, Model\ref{10} should probably be Model\eqref{10} line 1097 (page 41) You say " in order for the above guarantee to hold we require the following two conditions to hold. I think that is not technically true: the conditions below are what is needed to apply the specific previously established results, so technically those are sufficient rather than necessary conditions. Line 1114 (page 42): I think there was an error with copy and paste: "rounds" should be after $\tau$ and before the first, not the second comma of the line. In the first equality after line 1122, using \left and \right might be nicer. [1] Nathan Srebro, "Rank, Trace-Norm and Max-Norm", COLT 2005. [2] Ohad Shamir, Shai Shalev-Shwartz. Matrix Completion with the Trace Norm: Learning, Bounding, and Transducing. JMLR 2014. [3] Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, Yuling Yan. Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization. SIAM journal of Optimization, 2020. [4] Prateek Jain, Soumyabrata Pal Online Low Rank Matrix Completion. ICLR 2023 [5] Sahand Negahban, Martin J. Wainwright. Restricted Strong Convexity and Weighted Matrix Completion: Optimal Bounds with Noise. JMLR 2012. [6] Mitzenmacher, Michael and Upfal, Eli. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge UNiversity Press 2017. [7] Yuxin Chen, Yujie Chi, Jianqing Fan, Cong Ma et al. Spectral Methods for data science: a statistical perspective.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

See "weaknesses", especially Weakness 3. In addition, it seems that the algorithm is a little unnatural in that it doesn't use the successive estimates of the set of candidate arms and merely recommends uniformly random entries amongst all arms until it is confident it has identified the best arm overall. It would be interesting to see if it is possible to prove similar guarantees for the algorithm which recommends a random arm in the set $\mathcal{A}_{\ell}$ instead of ($\mathcal{A}_1=[m]\times [n]$) at each time step $\ell$.

Summary

This paper studies two problems in RL involving low-rank matrix estimation. It provides entry-wise estimation error bounds for simple spectral methods in low-rank bandits and low-rank MDP under different sampling mechanisms. Based on these, it provides performance guarantees for two algorithms designed for low-rank bandit and low-rank MDP respectively.

Strengths

The paper makes contribution towards the estimation of low-rank matrices in the setting of bandits and MDP respectively, as well as how these results can be useful in devising efficient algorithms to make full use of the low-rank structure. Specifically, the paper considers the challenging case of low-rank matrix estimation in the presence of dependent noise and provides sharp entry-wise estimation error bounds using involved techniques. This is likely to help the development of algorithms which are better fitted for low-rank settings.

Weaknesses

1. Compared with standard matrix completion problem, Model I in this paper extends to the case of dependent noise, but it restricts the magnitude of noise terms $\xi_t$ to be upper bounded by $c_1\Vert M\Vert_{\infty}$ (see Page 3 Line 91). Therefore, the results here can’t reduce to the state-of-the-art results in matrix completion with independent noise, where the noise level can be orderwise larger than $\Vert M\Vert_{\infty}$ [1]. We suggest the authors to discuss why their condition becomes more stringent when the noise are independent. 2. There are a few typos in the paper. For example: On Page 2 Line 71, it would be better to avoid using acronyms list “wlog”. On Page 7 Line 224, “where in a first phase” —> “where in the first phase” On Page 5 Line 175, “is a small when“ [1] Chen, Yuxin, Yuejie Chi, Jianqing Fan, and Cong Ma. "Spectral methods for data science: A statistical perspective." Foundations and Trends® in Machine Learning 14, no. 5 (2021): 566-806.

Questions

On Page 7 Line 220, it is assumed that the low-rank bandit has an homogeneous rank-$r$ reward matrix M, while this is not mentioned in the corresponding result Theorem 7. This makes the setting kind of confusing. Can you provide more explanations on this?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

This paper does not have potential negative social impact.

Addressed. Congratulations. Please add substantially more details in the derivations in the final version.

Many thanks for your many clarifications, and for agreeing to fix the typos. Regarding the lack of independence of the entries of $E_{i,j}$ in your setting, I now understand what you mean, thank you. However, it certainly doesn't feel very significant, since you still have independence of the $\xi_t$ for various $t$s. It is a classic issue in matrix completion that we need to be careful with repeated entries, as you are there, but it is usually just (highly) technical. However, I am still very convinced by the overall significance of the work and the other results. Still, it would be nice to incorporate part of this rebuttal in the paper to better explain what you mean there. Regarding A1, I understand what you mean. However, the concept of "entry-wise" isn't completely standard, and it is still worth comparing. I personally think it is nice, and doesn't diminish the value of your work at all, that the bounds scale similarly to those works, since your bounds are entry-wise (with a max over entries) and therefore much stronger. Thanks for the clarification for question 3 as well, and for the fantastic paper and results. I incline to keep my score.