Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimation
Authors: Stefan Stojanovic
Yassir Jedra
Alexandre Proutiere
Venue: NeurIPS 2024 poster (2024)
Keywords: Low-rank RL; Entry-wise matrix estimation; Matrix completion
Primary area: reinforcement_learning

Abstract: We consider the problem of learning an $\varepsilon$-optimal policy in controlled dynamical systems with low-rank latent structure. 
For this problem, we present LoRa-PI (Low-Rank Policy Iteration), a model-free learning algorithm alternating between policy improvement and policy evaluation steps. In the latter, the algorithm estimates the low-rank matrix corresponding to the (state, action) value function of the current policy using the following two-phase procedure. The entries of the matrix are first sampled uniformly at random to estimate, via a spectral method, the *leverage scores* of its rows and columns. These scores are then used to extract a few important rows and columns whose entries are further sampled. The algorithm exploits these new samples to  complete the matrix estimation using a CUR-like method. For this leveraged matrix estimation procedure, we establish entry-wise guarantees that remarkably, do not depend on the coherence of the matrix but only on its spikiness. These guarantees imply that LoRa-PI learns an $\varepsilon$-optimal policy using $\tilde{\cal O}({(S+A)\over \mathrm{poly}(1-\gamma)\varepsilon^2})$ samples where $S$ (resp. $A$) denotes the number of states (resp. actions) and $\gamma$ the discount factor. Our algorithm achieves this order-optimal (in $S$, $A$ and $\varepsilon$) sample complexity under milder conditions than those assumed in previously proposed approaches.

Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimation
Stefan Stojanovic KTH, Stockholm, Sweden stesto@kth.se
Yassir Jedra MIT, Cambridge, USA jedra@mit.
Alexandre Proutiere
KTH, Digital Futures, Stockholm, Sweden alepročkth. se
Abstract
We consider the problem learning an e-optimal policy in controlled dynamical systems with low-rank latent structure. For this problem, present LoRa-PI (Low-Rank Policy Iteration), a model-free learning algorithm alternating between policy improvement and policy evaluation steps. In the latter, the algorithm esti- mates the low-rank matrix corresponding to the (state, action) value function of the current policy using the following two-phase procedure. The entries of the matrix are first sampled uniformly at random to estimate, via a spectral method, the leverage scores of its rows and columns. These scores then used to extract a few important rows and columns whose entries are further sampled. The algorithm exploits these new samples to complete the matrix estimation using CUR-like method. For this leveraged matrix estimation procedure, we establish entry-wise guarantees that remarkably, not depend on the coherence the matrix but only its spikiness. These guarantees imply that LoRa PI learns e-optimal policy using O
S+A (poly(1-7)=)) samples where S (resp. A) denotes the number of states (resp. actions) and y the discount factor. Our algorithm achieves this order-optimal (in S, A and e) sample complexity under milder conditions than those assumed in previously proposed approaches.
Introduction
Reinforcement Learning (RL) methods when applied dynamical systems with large state and action spaces suffer from the curse of dimensionality. For example. learning an E-optimal policy in tabular discounted Markov Decision Processes (MDPs) with S states and A actions requires number of samples scaling at least as
SA4 [17, 36). Fortunately, many real-world systems exhibit latent T
structure that if learnt and exploited could drastically improve the statistical efficiency of RL methods [25, 38). this paper, we are interested in developing methods to leverage low-rank latent structures. These structures have attracted lot of attention recently, see e.g. [22, 11. 15, 28, 16, 45, 39, 2, 29, 40, 32, 35, 37, 34]. Here, we consider a structure where the (state, action) value functions of policies, low-rank. This structure has been empirically motivated and studied in [35, 34, 43, 33]. The hope is that when exploiting it optimally, learning an E-optimal policy would samples. Such improvement would also imply significant statistical gains MDPs with continuous state and action spaces. If these spaces are of dimensions dj and d2, under natural smoothness conditions and using an appropriate discretization [35], the sample complexity would indeed be reduced from -
viewed as S x A matrices,
only require O( S+A
(without structure) to gmax(d]._2)12"
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In this paper, we present LoRa-PI (Low Rank Policy Iteration), a model-free algorithm that learns and exploits an initially hidden low-rank structure in MDPs. Unlike existing algorithms, LoRa-PI does not require any prior information on the structure. Yet, the algorithm offers the promised statistical gains: its sample complexity essentially exhibits an order-optimal dependence in S, A and e (i.e.. S+
Contributions. Our algorithm LoRa-PI relies on approximate policy iteration [4]. As such, alternates between policy evaluation and policy improvement steps. The design and performance analysis of these two steps constitute our main contributions.
1. Leveraged matrix estimation with entry-wise guarantees. LoRa-PI sequentially updates a candidate policy whose (state, action) value function has to be estimated. This function can be seen an S x A matrix that we consider to be low rank. The policy evaluation step then boils down to a novel low-rank matrix estimation procedure. We have main constraints for this procedure. (i) To be sample efficient, the matrix should be estimated from noisy observations of only a few of its entries. (ii) For RL purposes (when integrated LoRa-PI), the procedure should offer entry-wise performance guarantees. We present LME (Leveraged Matrix Estimation), a low-rank matrix estimation algorithm that meets these constraints. LME does not require knowledge of priori unknown parameters of the matrix (such as its rank, condition number, spikiness, or coherence), and it is the first algorithm enjoying non-vaed vacuous entry-wise guarantees even for coherent matrices.
Method
Err. Guarantees
Sampling
Assumplion
Complexity
LME (ours)
entry-wise
adaptive
bounded spikiness anchors apriori known
a² + A)/2" +
Algorithm [35]
entry-wise
apriori fixed anchors
LR-EVI (Thm 9 [34])
entry-wise
unif. anchors
incoherence
1²aa A//2
NNM [91 (Thm [34))
entry-wise
unif. anchors
incoherence noiseless
12a2 + A)/e2
Two-phase MC [7]
exact recovery
adaptive
not applicahle
Table I: Comparison of methods with entry-wise guarantees. For brevity, the factors and d are omitted. NNM: nuclear norm minimization, MC: matrix completion.
(1 1 (--))_1,
More precisely, LME guarantees an entry-wise estimation error within using only (8+
Ö Intaa (1-7)=02 samples, where a and a denote the spikiness and the condition number of the matrix, respectively. Note that in particular, this sample complexity does not depend on the coherence of the matrix. Its dependence S, A and e cannot be improved. To reach this level of performance, LME relies on an adaptive sampling strategy. It first estimates, via spectral method, the so-called leverage scores of the matrix. These scores quantify the amount of information about the matrix available in the different rows and columns. The algorithm then exploits the leverage scores to adapt its strategy and in turn, drive the sampling process towards more informative entries.
2. Design and sample complexity of LoRa-PI. Our RL algorithm LoRa-PI is policy iteration algorithm that relies on LME to perform policy evaluation steps. The algorithm inherits the advantages of LME. In contrast to existing algorithms, it is parameter-free and its performance can be analyzed and guaranteed under mild assumptions on the (state, actions) value functions. In particular, the corresponding low-rank matrices do not need to be incoherent. We establish that LoRa-PI learns an c-optimal policy using Ô (1=2 ($+
samples, where a and i are upper bounds on the spikiness and the condition number of the (state, action) value functions.
(1->)"a²)
3. Numerical experiments. We illustrate numerically the performance of our algorithms, LME and LoRa-PI, using synthetically generated low-rank MDPs. The experiments are presented in Appendix A due to space constraints.
Notation. We denote the Euclidean norm of a vector x by || 2-- Let M be an m x n matrix. We denote its i-th row (resp. j-th column) by M.. (resp. by M. M. We denote its operator norm by || llpp it Frobenius norm by ||M its infinity norm by | oloo max;e|m].jj|nl MMaj,, and its two-to-infinity norm by ||M = maxiem [|Maall2 We denote by Mt the Penrose inverse of M. For given subsets E [m]. J [m], we denote by MI.J the sub-matrix whose entries are (My (i.j) e I x J}. Finally, we use A b min(a, b) and a V b max(a, b).

---

2 Related Work
Low-rank MDPs. MDPs with low-rank latent structure have been extensively studied recently. We may categorize these studies according to the type of the underlying low-rank structure and to the nature of the algorithms used to learn this structure.
The most studied low-rank structure concerns MDPs whose transition kernels and the expected reward functions are low-rank. For instance, it is assumed that the transition probabilities can be written as p(s"|s, [s, a) 6(s, a) "u('), where 6(s, a) and uus") are d-dimensional feature maps [22, 11, 15, 28, 16, 45, 39, 2, 29, 40, 32]. These work additionally assume that the feature map & (and rich function class H. In this setting, the typical upper bounds derived similarly for (i) belongs
for the sample complexity of identifying an e-optimal policy scale as poly(A, (1 - -) log [H]] When no restrictions are imposed on the class H. one can find a low-rank structure such that log (H] scales as the number of states [20]. In this case, the aforementioned upper bounds are the same those for MDPs without structure. We also note that most algorithms using this framework rely on strong computational oracles (e.g., empirical risk minimizers, maximum likelihood estimators), see [23, 18, 44] for detailed discussions. In this paper, we do not limit our analysis to low-rank structures based on a given restricted class of functions, and our algorithms do not rely on any kind of oracle.
5t
The low-rank structure we consider is similar to that in [35, 34] and just assumes that the (state, action) value functions are low-rank. Actually, [35] considers the case where only the optimal Q-function is low-rank, say of rank d. As shown in [35], such a structure naturally arises when discretizing smooth MDPs with continuous state and action spaces. In both papers [35, 34), the authors devise algorithms with a minimax -pttimal sample complexity to identify an s-optimal policy roughly scaling as (S + A)/E². But the analysis presented in [35] suffers from the following important limitations. 1. First, it is assumed that the learner is aware of a set I (resp. J) of so-called anchors states (resp. actions), such that the rank of the matrix QI.T == (Q(s, ().((xx) is the same as that of the entire matrix Q. Such anchors are however initially unknown (since Q is unknown). Importantly, the proposed RL algorithms rely on a low-rank matrix estimation procedure whose performance strongly depends on the smallest singular value o oa (QQ..) of QI,5. The authors circumvent this difficulty by actually parametrizing their algorithms using Fa(QI.T). But again, the latter is unknown, and it remains unclear how one can avoid this issue. 2. The second limitation is that the analysis is valid for small values of the discount factor ry (the authors need to impose an upper bound on 7/0a( (Fr.I) )). When a (Q,y) is small, the analysis is limited to very short horizons. Note that in addition, [35] assumes that the collected rewards are deterministic, which together with the short horizon issue, greatly simplifies the learning problem.
To address the first limitation, the authors of [34] propose to sample rows and columns uniformly at random to get anchors. This solution requires to sample at least du² states and actions (Lemma 10 in [34]) where μ is the (unknown) coherence of the matrix to be estimated. Hence this essentially amounts to sampling almost the whole matrix for coherent matrices. The authors of [34] also propose a solution to the second limitation, but at the expense of imposing additional restrictive conditions. In this paper, address both limitations and devise RL algorithms that rely on new low-rank matrix estimation procedure that works without imposing the incoherence of the matrix and that does not require knowledge on a priori unknown parameters of this matrix.
Low-rank matrix estimation with entry-wise guarantees. Until recently, most results on low-rank matrix recovery concerned guarantees with respect to the spectral or Frobenius norms, see e.g. [12] and references therein. Over the past few years, methods to derive entry-wise guarantees have been developed. These include spectral approaches [1. 8, 37], nuclear-norm penalization and convex optimization techniques [9], CUR-based (or Nyström-like) methods [35, 3, 34].
The aforementioned literature provides guarantees not for all low-rank matrices, but for those typically enjoying additional structural properties such as incoherence. Relaxing the incoherence assumption is not easy, but can be achieved using adaptive sampling [24, 7, 41]. As far as we are aware, all results applicable to somewhat coherent matrices provide guarantees with respect to the spectral or Frobenius norms. In this paper, we develop a first adaptive matrix estimation method with provable entry-wise guarantees, valid for matrices with well-defined spikiness but not necessarily incoherent. Refer to [26, 30] and to $3.2 for detailed discussion about the notion of spikiness.
3

---

3 Preliminaries
3.1 Low-rank Markov Decision Processes
We consider a discounted MDP with finite state and action spaces S and A. These spaces are of cardinality S and A. respectively. The dynamics are described by the transition kernel p where denotes the probability to move to state s' given current state and that the action selected. The collected rewards are random but bounded by Tmax. and r(s, is the expected reward collected when action is selected in state s. A deterministic Markovian policy и is described by mapping from to A. We denote by V the state value function of æ:: for all E S, (s) = [E y'r(s, a, a 1 =], where s7 and of are, at time t. the state and the action selected under ग. Similarly, the (state, action) value function of π is defined by: for all (s, a) E S x A, (*(
p(s'|s, a))
r(s,, a) + + E. p(s'|s( (s, (s.a)V* (i))"(ss Q" can be seen as S x A matrix, referred to as the value matrix of π in the remainder of the paper. Let Kiz denote the condition number of Q". Finally, let V be the value function of the MDP (the value function of the optimal policy).
The objective is learn an s-optimal policy by interacting with the MDP. Such a policy satisfies: for all s E S, V= (s) 2 (s) - e. Without any assumption on the structure of the MDP, to identify such a policy, the learner needs to gather, even with a generative model, a number of samples' that scales as =-(1-ン} [17, 36). The hope is that exploiting an a-priori known structure in the MDP may considerably accelerate the learning process. In this paper, we focus low-rank latent structure. Formally, we define:
34
Definition (Rank of policy, rank of the MDP). The rank d. of a deterministic policy is the rank of its value matrix Q". The rank of an MDP is then defined as d = maxg dg, where the maximum is over all deterministic policies.
Throughout the paper, we assume that the MDP is low-rank: its rank satisfies d < (5 + A). This assumption is merely made simplify the exposition of our results and proof techniques. As we shall argue in Appendix E, our findings can naturally be extended to MDPs that are only low-rank in an approximate and well-precised sense.
3.2 Matrix estimation: coherence and spikiness
Our learning algorithm relies on the approximate policy iteration method, and in particular, in each iteration, it needs to estimate the low-rank value matrix of the current policy. To be sample efficient, the algorithm will estimate the matrix from the noisy observations of few of its entries. Recovering low-rank matrix from few of its entries is not always possible (see e.g. [12] for survey), and conditions on the degree to which information about a single entry is spread out across a matrix must be imposed. Examples of such conditions pertain to the coherence [6, 31] or the spikiness [30] of the matrix.
Matrix coherence. Let Q be rank-d S x A matrix with SVD UEWT. The coherence of Q is defined p(Q)= max S/d||U 22- v A/d|]/ J. Q is p-coherent if p(Q) S μ. Low coherence means that the energy of U and W are not concentrated around a few rows and columns.
Matrix spikiness. The spikiness of Q defined as aQQ) = VS E [1, /SA). Q is a-spiky if (Q)) < a. A matrix has low spikiness if the amplitude of its maximal entry is not much larger than the average amplitude of its entries, in which case, intuitively easier to estimate.
Most existing guarantees for low-rank matrix estimation are expressed through the spectral or Frobe- nius norm of the error matrix. For this type of guarantees, the estimation error scales polynomially either with the matrix coherence or with its spikiness [12, 30). The matrix spikiness was introduced in the matrix completion literature [30] to obtain guarantees under less restrictive conditions than the incoherence conditions imposed in previous work. Indeed, there are matrices with bounded spikiness but high coherence (say close to /5/d, in which case the aforementioned coherence- based guarantees are vacuous). In contrast, bounded incoherence provides an upper bound on spikiness since (Q) = V oz/ Q I /|2 @I! || ||| || S u())²d.
'Here a sample refers to an experience (s, a, r, 8'), the observation of the collected reward r and the next state s', starting with a given (state, action) pair (s, a). Under generative model, the learner can adapt the choice of (s, a) for the next observed experience without any constraint.

---

For RL purposes, we need to derive entry-wise guarantees for the estimate of the value matrix of some policy as demonstrated in [35, 37, 21]. Existing upper bounds for the entry-wise estimation error exhibit strong dependence in the matrix coherence and its condition number, see e.g. [9, 8, 37]. For instance, in [9], this dependence comes as a multiplicative factor yu ( Q)2 in the number of samples required for a given level of estimation accuracy. As far as we are aware, our matrix estimation method is the first able to yield entry-wise guarantees that do not exhibit a dependence on the matrix coherence but only on its spikiness (see Table 1). Our algorithm is better by factor of (Q)² than algorithms based on uniform sampling (studied in [34]), and requires the same sample complexity as the algorithm of [35], which has prior knowledge of anchor states. It remains however unclear whether the dependence of the entry-wise estimation error in the condition number can be avoided. This last observation guides the design of RL algorithms for low-rank MDPs discuss next.
3.3 Policy vs. Value Iteration: the condition number issue
We aim at devising an algorithm learning an efficient policy with provable guarantees while imposing conditions on the MDP that are as mild as possible. To this aim, one may think of applying either policy iteration approach, as we do, or value iteration approach.
Policy Iteration. Using this approach, in each iteration, we need to estimate the low-rank value matrix of the current candidate policy. As mentioned above, the entry-wise error of this estimation procedure depends on the condition number of the matrix. Note that this matrix belongs the finite set of (state, action) value functions of deterministic policies. As shown in [10, 42), this set can be seen as the vertices of simple polytope P. Hence get performance guarantees when applying PI approach, it is sufficient to impose an upper bound on the condition numbers K for all deterministic policies π, or equivalently, on the condition numbers of matrices corresponding the vertices of P.
Value Iteration. Here, we would maintain, in iteration t. an estimate V(t) of the value function V*, and samples would be used to compute V(++1), an estimate of T (V(()), where T denotes Bellman's operator. More precisely, starting from V(t), we would estimate the low-rank matrix Q(++1) F(V(0) defined by for all (s, a), F(V(O)(s,,) = r(s, a) + 7 E.' p(s'Is, Is, a)V( (s'). Then we would define (+++1 as the value function of the greedy policy with respect to Q(++1), Hence to get provable performance guarantees using value iteration approach, we would need to impose an upper bound on the condition number of (+)) in all iterations t. The main issue is that the set of matrices (Q(1) L 2 }} is stochastic and hard to predict. Indeed, we have no way of confining the iterates Q((++) to the polytope P: as shown in [10], the polytope is not stable by Bellman's ' operator. As a consequence, if we wish get performance guarantees for a value iteration approach, we would need to impose an upper bound on the condition number of all possible matrices of the form F(V) for some vector V.
In summary, policy iteration approaches offer a theoretical advantage compared to value iteration. requires the control of the condition numbers of matrices in a set much smaller than that for value iteration. This advantage is illustrated in Figure on a toy example of an MDP. Refer to Appendix A for additional numerical experiments (with larger MDPs).
4 Leveraged Matrix Estimation
In this section, we present Leveraged Matrix Estimation (LME), an algorithm that estimates the value matrix Q" of a policy œ. The algorithm relies on an active strategy for sampling the entries of the matrix based on estimated leverage scores as defined below. This active strategy accelerates the learning process and allows us to obtain entry-wise guarantees that do not depend on the coherence of the matrix but on its spikiness only.
Definition 2 (Leverage scores²). Lel Q be a rank-d S x A matrix with SVD UEWT. Its left and right leverage scores E and p are defined as l, |U,,11//d for all E S, and Pa. [Wo.:ll/a for all E A.
LME only takes as inputs a policy т and a sampling budget T. It proceeds in two phases: first, it uses half of the sampling budget to estimate the leverage scores of Q" via singular subspace recovery.
Our definition of leverage scores consistent up scale factor with that used in the literature [5. 13. 7].
5

---

V
log (econdittoon number
(3g
(8:)
Figure 1: Consider MDP with two states and two actions (see Appendix A. 1.1 for details). The black crosses correspond the value function the possible policies. When combining policy iteration with a low rank estimation procedure, we just need to control the condition number of the corresponding value matrices. The red dots correspond to the successive estimates V of V* when running value iteration. When applying value iteration approach, we would need to upper bound the condition number of all the corresponding matrices Q(+) (tV(t-1) for 1. For a given V, the background color in the figure indicates the value of the condition number of FV)). We see that the dynamics of (t) under the value iteration algorithm are such that the trajectory (Q(+), t 2 1) has to go through regions where the condition number is very high. Hence on this example, value iteration approach would not work well.
Second, selects a few anchor rows and columns sampled using the estimated leverage scores, and uses the remaining budget sample the entries of these and columns. It finally completes the matrix estimation using a CUR-based method. The full pseudo-code of LME is presented in Appendix C. Observe that LME is parameter-free: it does not require knowledge of the policy rank d,, upper bounds on unknown parameters such as Ki or ({Q") ) or p(Q"). Throughout this section, when presenting our guarantees, will abuse notation and d, and a, instead of dg Ki and (Q")).
4.1 Preliminaries
LME exploits a natural empirical estimator of Q" entries at numerous stages. This empirical estimator is essentially based on Monte-Carlo rollouts with truncation described next. De- fine the truncated value matrix at horizon as follows: for all (s, a) E S x A, (s, = E E >rr of) [[sr) l = 8, ag a]. By choosing appropriately, we may control the level of the approximation error Q Q We make this observation precise in the following lemma, proved in Appendix F.I.
1 log (I=uge) ). we have I|Q - Q: S.. Lemma 1. For any >> O and any 2 1-y
In view of the above, to estimate an entry, say (s, a), of Q", we will use an empirical estimator based trajectories of length + 1 of the system under and starting with (state, action) pair a). In our algorithms, this length chosen to get an appropriate accuracy level. Specifically, we choose and follows:
Tmax
T (1-7)
c=
and
T=
1 - log
(1)
T
These choices will become apparent from our analysis.
4.2 Phase 1: Leverage scores estimation via spectral subspace recovery
The first phase of LME is devoted to the estimation of the leverage scores of Q=. To this aim, using half of the sampling budget T/2, we estimate the singular subspaces of the matrix via spectral method.

---

Phase la. Data collection and the empirical truncated value matrix. As suggested in 1, to estimate individual entries of Q", we sample system trajectories length + 1. More precisely. for each of the N : (2( + 1)) trajectories, we first sample the starting (state, action) pair uniformly at random, and then observe the trajectory obtained under the policy and initiated at this pair. The data collected this way is D = {($ "k,0= " "k.or-..:- &h, "g,r =k,- k [N]]. Using this data, construct an empirical estimate of the truncated value matrix as follows V(s. a) E A:
(s,
SA N
Σ 1=0
1((5k,0.07,0) = (s,a)):
(2)
k=
Phase 1b. Singular subspace recovery. We compute the SVD of the empirical truncated value matrix SAA
OF. We obtain O -im1 8, ",ūي where 01, ....... USAA correspond, in decreasing order, to its singular values and u....., üy (resp. WI...., ,,,))) to its left (resp. right) singular vectors. Using this decomposition, we construct estimate of Q" follows:
SAA
Q" - 0,160, 2 2)0,0
(3)
where > 0 is threshold that we will precise shortly. We view Qn biased estimate of Q" with controlled bias through т. We also use 3 to estimate the rank of Q": d = Eim1 (ā; 2 B). Finally, the estimated left (resp. right) singular subspace is denoted
SAA
[ū
à E sxd
(resp. W = [ύ]
v d E RAx4). In the following proposition, we provide a choice for the threshold 3 that yields appropriate guarantees regarding subspace recovery.
Proposition 1. Let 8 E (0, and choose the threshold 8 as
22 SA(S + A)
(5 (ST' (1 (1-7)8
Tmax SA
B
=
max
log"
(4)
733
T
Then, provided that?:
SA (S+
= Ω6
max
(5)
(3((²) (1-7)a
have that events: = dz. for all
Tmax SA
S A
(S A)T
||U,,: - Ü.. (. U) S (1 - (3-7)3/20a(Q)
V (T + u.lUa..lly
log²
T
(1 7)-
hold with probability at least - 6. An analogous result holds for W.
The precise statement (Theorem 4) and the proof are presented in Appendix B.3 and B.4.
Phase Ic. Leverage Scores Estimation. To conclude, using the recovered subspaces Ú and W. estimate the leverage scores as follows 8= ||ž||; and X = ||p|| P. where:
d S' The performance of the estimation of the leverage scores is summarized in the following theorem, proved in Appendix B.2.
Ys S: i, = 10...
and Va E A: A. W A'
(6)
Theorem (Leverage Scores Estimation). Let 5 E (0, Suppose the threshold (3 is chosen as in
(4). Then, have that: PYVS S, t, < <44,) 2 6, provided that
k2 2 SA
SA (S + A)
T == T.
max
2 (1->)3)
An analogous result holds for p.
'To simplify the notation, all our sample complexity guarantees are expressed using (.),), the tilde-notation may hide poly-log dependencies in 6, S. A. (1 ->) d. a. log(e/s), and Tmax:.
7

---

4.3 Phase 2: Leveraged CUR-based Matrix Completion
Before we proceed with the description of the second phase, we briefty recall the so-called CUR decomposition [19, 27] for low-rank matrices. The decomposition says that for given rank-d S x A d, such that the sub-matrix QI.J matrix Q. there always exists C [S]. _ [A), with [ QI.j- As [35, 34, 3], we leverage this full rank and for all entries (i,j). Qi decomposition in our matrix estimation procedure, but without any requirement such as knowledge of I. J for which (QQII,)) bounded away from zero or upper bounds on parameters like the matrix coherence.
Phase 2a. Data collection to estimate the skeleton of the value matrix. We start by sampling K == 64d log(64d/8) rows (resp. columns) without replacement according to l (resp. ()) to form skeleton of the matrix. These rows and columns are referred to as anchors. We denote the set of selected rows (resp. columns) by I S (resp. J C A). We use the remaining sample budget T/2 to get samples of the entries of Q" in the skeleton. To this aim, we use the procedure described in $4.1, and sample trajectories of length + 1. For each entry (s, a) E Qg ;= I x J, we use N T/(((T + 1)K trajectories to compute Q (s, a), an empirical estimate of (8, a) (see (2)). For each entry (s, a) E S2+ =-
(U(())))X(((CC (A),)) we use N₂ = (K( trajectories, Note that N₂ S N, (this plays a role in the analysis).
Phase 2b. CUR-based completion with Inverse Leverage Scores Weighting. First, using the leverage scores, and the set of rows I and columns J, we define K K diagonal matrices L and as follows:
1
V I, Lu
min { L.. and VjEJ, R5j min (K,lVKkk))) K
Next, starting from the values of (s, for (8, the skeleton, we perform a CUR matrix completion to obtain Q=: (i) for all (s, E (S x J) U A), we set QT (s, = (7 a); (ii)
for all (s, a) E (SVZ)= (A)J), we set
(s, (7. [) (T(s.) (ORRLLQQ (Q; (I,
(8)
Note that the use of L and R in (8), referred Inverse Leverage Scores Weighting, corresponds to an importance sampling procedure. allows us to account for the fact that the skeleton has been sampled using the (estimated) leverage scores.
The next theorem summarizes the performance guarantees under LME. Its proof is presented in Appendix C.I.
Theorem 2. Let > 0, 5 E 1). Given a deterministic policy n, and a sampling budget T, the algorithm LME ensures that P(I 1= S 5) 2 5, provided that 5 [1@"ll>> and
(S A) aad
T 54
(1 - 322 (rmax
Theorem 2 states that the sample complexity of LME obtain entry-wise guarantees does not depend on the coherence y of Q" but rather on its spikiness a and condition number x only. Hence LME provides entry-wise guarantees even for coherent matrices. In addition, its sample complexity scales with 5, A, y and optimally. Indeed a, K = @(1) and d < + A, scales as 20(1-733- We also wish to emphasize that LME farameter-free, the sense that does not require knowledge of the so-called anchor rows and columns, does it require upper bounds unknown parameters such as coherence, spikiness, rank or condition number. These properties are desirable for RL purposes.
(S+A)
Low-Rank Policy Iteration
In this section, we present and evaluate LoRa-PI (Low Rank Policy Iteration), a model-free variant of the approximate policy iteration algorithm [4]. It alternates between policy improvement and policy evaluation steps and uses LME, our low rank matrix estimation procedure for policy evaluation. Refer to Algorithm I for the pseudo-code.
8

---

Algorithm 1: Low-Rank Policy Iteration (LoRa-PI)
Input:
sampling budget T, accuracy confidence level 6, discount factor y, rewards upper bound T maxx x initial deterministic policy
Set Nepochs 6- (1-1)) >) log ((4rmax) 7)
Set Toval T T/Nepachs
for t = 1,2..... 222...,Nooochh.
Nepochs do (Approximate policy evaluation), Obtain the value matrix of ((1); 2+t)) + LME(T((). (Tval) (Policy improvement) Improve (11) using ((t); Vs ( arg ma (s,
end
Output: Output क =x ((Nepocha1)).
The following theorem provides performance guarantees for LoRa-PI.
We state the results under the assumption that for any deterministic policy ıT Q is a-spiky and has condition number upper bounded by
Theorem
Les E 10,1) and &
Ō(1(@a") 11oo)
Under LoRa-PI, we have
P (IIV* V S {)) 2 1 1-6, ô, provided
(S A) + a²d
T T= l2
(1 - -82 (rmax x222))))))))
The proof of Theorem 3 is presented in Appendix D. Having entry-wise guarantees (as stated in Theorem at each iteration of the algorithm is critical to establish Theorem 3. fact, the proof starts from the observation (see Lemma 9) that
(1-7)llV* 10 2rmmxx" Neputo max
11 QT((") 1000
LoRa-PI PI combines numerous advantages. (i) It parameter-free: it does not require the knowledge of upper bounds on parameters such as the ranks, condition numbers, and spikiness of the value matrices of policies. This is thanks to LME, which is itself parameter-free. (ii) Its sample complexity does not depend on the coherence of the value matrices but only on their spikiness; which is an important improvement over existing algorithms [34]. (iii) LoRa-PI offers performance guarantees without having access to good anchor states and actions, without assuming that the rewards are deterministic and that the discount factor is (far too) small, in [35] (refer to Section 2 for detailed discussion). (iv) Its sample complexity has an order-optimal scaling in S, A and e. (v) Finally, since LoRa-PI uses policy iteration, its theoretical guarantees can be established under milder assumptions than if value iteration was used instead (see $3.3).
The dependence of order (1 7) -8 is far from the ideal minimal dependence of order (1 -- one would typically obtain in RL without low-rank structure. This is an artifact of using a model-fre free approach, and more specifically the Honte-Carlo estimator of entries of the value matrices. Avoiding such high dependence requires further assumptions and model-based approach.
-3 that
Furthermore, it is worth mentioning that the guarantees enjoyed by LoRa-PI can be naturally extended MDPs that are low-rank only in an approximate sense. We refer the reader Appendix for further details.
6 Conclusion
In this work, considered class of MDPs where the Q-function, viewed state-action matrix, admits low-rank representation under any deterministic policy. We devised LoRa-PI, a model-free learning algorithm based on approximate policy iteration, that provably exploits such low-rank representation to output a near-optimal policy. Critical to the design and performance guarantee of LoRa-PI is a novel low-rank matrix estimation procedure referred to as LME. LME is shown to enjoy a tight entry- wise guarantee while being parameter-free. i.e., it does not require knowledge of the so-called anchor rows and columns, nor upper bounds on unknown parameters such as spikiness, coherence, rank, or condition number. More importantly, its sample complexity does not scale with

---

the coherence but instead with the spikiness of the matrix. This allows us to estimate wider class of low-rank matrices with entry-wise guarantees than previous work. Such desirable properties are what make LME appealing for RI purposes, and in particular what allows us to show that LoRa-PI is sample-efficient under mild conditions. From a design perspective, LME and its analysis features many interesting tools and ideas. Notably, (i) we derived instance-dependeng row-wise singular subspace recovery guarantees, and (ii) we combined the use of the so-called leverage scores with a CUR-based approximation for matrix estimation. We believe such tools and ideas to be of independent interest. Finally, we provided experimental results that suggest the superior performance of our proposed algorithms.
10

---

Acknowledgment
This research was supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation, the Swedish Research Council (VR), and Digital Futures. YJ is supported by the Knut and Alice Wallenberg Foundation Postdoctoral Scholarship Program under grant KAW 2022.0366.
References
[1] Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong. Entrywise eigenvector analysis of random matrices with low expected rank. Annals of statistics, 48(3):1452, 2020.
[2] Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs. In Advances in Neural Informa- fion Processing Systems, volume 33, pages 20095-20107. Curran Associates, Inc., 2020.
[3] Anish Agarwal, Munther Dahleh, Devavrat Shah, and Dennis Shen. Causal matrix completion. In The Thirty Sixth Annual Conference Learning Theory, pages 3821-3826. PMLR, 2023.
[4] Dimitri Bertsekas and John N Tsitsiklis. Neuro-dynamic progranming. Athena Scientific, 1996.
[5] Christos Boutsidis, Michael W Mahoney, and Petros Drineas. An improved approximation algorithm for the column subset selection problem. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms,, pages 968-977. SIAM, 2009.
[6] Emmanuel J. Candes and Yaniv Plan. Matrix completion with noise. Proceedings of the IEEE, 98(6):925-95 996, 2010.
[7] Yudong Chen, Srinadh Bhojanapalli, Sujay Sanghavi, and Rachel Ward. Completing any low-rank matrix, provably. The Journal of Machine Learning Research, 16(1):2999-308 2015.
[8] Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, et al. Spectral methods for data science: A statistical perspective. Foundations and Trends@ Machine Learning. 14(5):566 2021.
[9] Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, and Yuling Yan. Noisy matrix completion: Understanding statistical guarantees for convex relaxation via nonconvex optimization. SIAM journal on optimization, 30(4):3098-311 3121, 2020.
[10] Robert Dadashi, Adrien Ali Taiga, Nicolas Le Roux, Dale Schuurmans, and Mare G Bellemare. The value function polytope in reinforcement learning. In International Conference on Machine Learning, pages 1486-1495. PMLR, 2019.
[11] Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. On Oracle-Efficient PAC RL with Rich Observations. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[12] Mark A. Davenport and Justin K. Romberg. An overview of low-rank matrix recovery from incomplete observations. JEEE Sel. Top. Signal Process., 10(4):608-6 6228,6622222222 2016.
[13] Petros Drineas, Malik Magdon-Ismail Michael W. Mahoney, and David P. Woodruff. Fast ap- proximation of matrix coherence and statistical leverage. J. Mach. Learn. Res., 13(1):3455-306, dec 2012.
[14] Petros Drineas, Michael W Mahoney, and Shan Muthukrishnan. Relative-error cur matrix decompositions. SIAM Journal on Matrix Analysis and Applications, 30(2):844-881) 2008.
[15] Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient RL with Rich Observations via Latent State Decoding. In Proceed- ings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1665-1674, PMLR, 09-15 Jun 2019.

---

[16] Dylan Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. Instance- Dependentt Complexity of Contextual Bandits and Reinforcement Learning: Disagreement-Beee Based Per- spective. In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 1059.2059. PMIR, 15-19 Aug 2021.
[17] Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen. Minimax pae bounds on the sample complexity of reinforcement learning with a generative model. Machine learning, 91:325-344 2013.
[18] Noah Golowich, Ankur Moitra, and Dhruv Rohatgi. Learning in Observable POMDPs, without Computationally Intractable Oracles. In Advances in Neural Information Processing Systems, volume 35. Curran Associates, Inc., 2022.
[19] Sergei A Goreinov, Hugene E. Tyrtyshnikov, and Nickolai L. Zamarashkin. A theory of pseu- doskeleton approximations. Linear algebra and applications, 261((-3):1-211 1997.
[20] Yassir Jedra, Junghyun Lee, Alexandre Proutiere, and Se- Young Yun. Nearly optimal latent state decoding in block mdps. In International Conference on Artificial Intelligence and Statistics, pages 2805 2904. PMLR, 2023.
[21] Yassir Jedra, William Réveillard, Stefan Stojanovic, and Alexandre Proutiere. Low-rank bandits via tight two-to-infinity singular subspace recovery. In Forty-first International Conference on Machine Learning, 2024.
[22] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. Contextual decision processes with low Bellman rank are PAC-learnable. In Proceedings of the 34th International Conference Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1704-1713, PMLR, 06-11 Aug 2017.
[23] Daniel Kane, Sihan Liu, Shachar Lovett, and Gaurav Mahajan. Computationallstatssttt gap in reinforcement learning. Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 1282-1302. PMLR, 02-05 Jul 2022.
[24] Akshay Krishnamurthy and Aarti Singh. Low-rank matrix and tensor completion via adaptive sampling. Advances in neural information processing systems, 26, 2013.
[25] Michael Laskin, Aravind Srinivas, and Pieter Abbeel. CURL: Contrastive Unsupervised Repre- sentations for Reinforcement Learning. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 5639-5650. PMLR, 13-18 Jul 2020.
[26] Lester W Mackey, Ameet Talwalkar, and Michael Jordan. Distributed matrix completion and robust factorization. J. Mach. Learn. Res., 16(1):913-960, 2015.
[27] Michael W Mahoney and Petros Drineas. Cur matrix decompositions for improved data analysis. Proceedings of the National Acudemy of Sciences, 106(3):697-702, 2009.
[28] Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 6961-6971. PMLR, 13-18 Jul 2020.
[29] Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model- free representation learning and exploration in low-rank mdps. Journal of Machine Learning Research, 1-66) 2024.
[30] Sahand Negahban and Martin J Wainwright. Restricted strong convexity and weighted matrix completion: Optimal bounds with noise. The Journal of Machine Learning Research, 13:1665- 1697, 2012.
[31] Benjamin Recht. A simpler approach to matrix completion. Journal of Machine Learning Research, 12(12), 2011.
12

---

[32] Tongzheng Ren, Tianjun Zhang, Lisa Lee, Joseph E Gonzalez, Dale Schuurmans, and Bo Dai. Spectral decomposition representation for reinforcement learning. In Proc. of ICLR, 2023.
[33] Sergio Rozada, Santiago Paternain, and Antonio G. Marques. Tensor and matrix low-rank value- function approximation in reinforcement learning. IEEE Transactions on Signal Processing, 12:1634-1649) 2024.
[34] Tyler Sam, Yudong Chen, and Christina Lee Yu. Overcoming the long horizon barrier for sample-efficient reinforcement learning with latent low-rank structure. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 7(2):1-60, 2023.
[35] Devavrat Shah, Dogyoon Song, Zhi Xu, and Yuzhe Yang. Sample efficient reinforcement learning via low-rank matrix estimation. Advances in Neural Information Processing Systems, 11112002--2100, 2020.
[36] Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang. and Yinyu Ye. Near-optimal time and sample complexities for solving markov decision processes with generative model. S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[37] Stefan Stojanovic, Yassir Jedra, and Alexandre Proutiere. Spectral entry-wise matrix estimation for low-rank reinforcement learning. Advances in Neural Information Processing Systems, 36, 2024.
[38] Adam Stooke, Kimin Lee, Pieter Abbeel, and Michael Laskin. Decoupling Representation Learning from Reinforcement Learning. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 9870-9879. PMLR, 18-24 Jul 2021.
[39] Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model- based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches. In Proceedings of the Thirty-Secone Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages Jun 2019.
PMLR, 25-28
[40] Masatoshi Uchara, Xuezhou Zhang, and Wen Sun. Representation Learning for Online and Offline RI in Low-rank MDPs. In International Conference on Learning Representations, 2022.
[41] Yining Wang and Aarti Singh. Provably correct algorithms for matrix column subset selection with selectively sampled data. Journal of Machine Learning Research, 18(156):1-42, 2018.
[42] Yue Wu and Jesús A. De Loera. Geometric policy iteration for markov decision processes. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '22, page 2070-2078, New York, NY, USA, 2022. Association for Computing Machinery.
[43] Yuzhe Yang, Guo Zhang, Zhi Xu, and Dina Katabi. Harnessing structures for value-based planning and reinforcement learning. In International Conference on Learning Representations, 2020.
[44] Tianjun Zhang. Tongzheng Ren, Mengjiao Yang, Joseph Gonzalez, Dale Schuurmans, and Bo Dai. Making Linear MDPs Practical via Contrastive Representation Learning. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 26447-26466. PMLR, 17-23 Jul 2022.
[45] Xuezhou Zhang, Yuda Song, Masatoshi Uehara, Mengdi Wang. Alekh Agarwal, and Wen Sun. Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approach. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedingy of Machine Learning Research, pages 26517-26547. PMLR, 17-23 Jul 2022.
13

---

A Numerical Experiments
All experiments in this section were performed on HP EliteBook 830 G8 with an Intel i7 core and 16 GB of RAM. Each experiment's 's runtime for individual realizations took at most 2-3 hours, and reproducing all results is feasible within day.
A.1 Parameters of the toy example in Figure 1
We considered an MDP with A = 2, = 0.87, a reward matrix given by
0..46
-0.48
0.14
0.28
and the following transition probabilities:
0.4
0.6
0.25
0.75
a( = a
P(s'|8, (1,8 a2)
0.15
0.85
0.29
0.71
We initialized VI with V(0) [2.86
2.98]
T Note that Vinax
Tmax 1-y
3.69 and thus V(())
[- (-Vmax; Vmax] ]2
For this example, the condition numbers of the Q-functions induced by policies are 16.08, 4.38, 15.29, 12.07, while the maximum condition number during value iteration is z 2497.82.
We stress here that this MDP is full-rank, and the purpose of this example is to demonstrate the potential instability of VI in the presence of large condition numbers. For low-rank MDPs, this corresponds to the matrix Q" having an effectively smaller rank than expected, and estimating all d singular vectors despite Tn (1") (Q"))/aa((")
cc.
A.2 Matrix completion with leveraged anchors
We consider matrix completion with fixed matrix M to be estimated, testing four different methods. First, test method based on CUR-approximation with anchors chosen uniformly at random. Next, we have a method based on the estimation of leverage scores, where, for a given budget of samples, use half of them for estimating leverage scores as described in the main text. Then, consider method with oracle anchors, where the anchors are chosen with respect to the true leverage scores. Lastly, we consider standard SVD decomposition, where keep only the first d largest singular values of the matrix.
uniform leveaagdd anchors oracle ouchors
uniform anchore leveraged anchors
0.25
oracle suchors SVD
SVD
M/ 1/
3/"1
0.15
11.
0.1
01
mumber sumples
mumber sumplee
Figure 2: Matrix completion: matrix M is of size 1000 x 1000, rank d = and sampled entries have additive Gaussian noise with o 0.01. Number of anchors used was K 10. All plots are averaged over 30 simulations and a new random matrix M was generated in every 5 simulations.
As expected, CUR-based methods depend heavily on the quality of anchor selection. The gap between leverage- senege--core-baeed anchors and oracle anchors is slight, even when half the samples are used to estimate the leverage scores. While SVD shows a smaller Frobenius error, has higher entrywise error compared to CUR-bare based methods with good anchors.
14

---

A.3 Leverage scores for VI and PI
We demonstrate the importance of choosing anchors based on leverage scores for value iteration (VI) and policy iteration (PI). We postpone learning of the anchor states to the next subsections and assume that the true leverage scores of matrices (121 are given. For methods with leveraged anchors, anchors are chosen as those with the highest leverage scores (true leverage scores of Q(+)). For uniform anchors, anchors are chosen uniformly without repetitions.
cndee unchors
onude mnchess unfform suclurs
unfforn sundhurs
2-
1.6
1L5
10
15
20
25
30
35
10 12
14
10
18
Ieeration cumber
Iteration number
(a) Value itcration with anchors.
(b) Policy iteration with anchors.
Figure 3: Matrix Q' is obtained from rank d 5 rewards and transition matrices. Moreover, S= 70, A = 50, 7 = 0.9, and we choose number of anchors = 15. Observations are noisy with additive Gaussian noise with a = 0.01. Plots are averaged over 100 simulations, and new MDPs are generated every simulations, while the number of samples in an iteration is 10(1.))
These results highlight that leveraged anchors reduce entrywise error significantly for general matrices. In contrast, uniform anchors show significant randomness, although the error decreases in expectation over iterations.
A.4 Low-rank Value Iteration
We evaluate a VI-based variant of Algorithm 1, that we refer to as LoRa-VI. We do not assume prior knowledge of the matrices, and use samples to estimate leverage scores and matrices (Q!)) )121-
0.16
VI levernged nuchors full-mattek VI
VI levernged enchars
Vi
full mall-mattex VI
7
10
0.10
0
0
cotal number of sazppies
total mimberr of samples
x12
Figure 4: LoRa-VI: Q' generated from low-rank and P of rank d = 4, S - A 1000, 0.1. We used K = 10 anchors, (0)) 0, rewards are noisy with Gaussian noise = 0.01. All plots are averaged over 5 simulations, each consisting of epochs, and the number of samples in an epoch is approximately 20(1.05)'(5 - A)K.
15

---

Even though we did not theoretically analyze the VI-based method in this work, for the reasons mentioned in Section 3.3, we note that this method works well in practice for the settings considered in this study. We consider three methods: VI with leveraged anchors, where we use half of the experiences to estimate leverage scores and based on them sample the second half in a CUR-like fashion. Next, we consider VI with uniform anchors, where anchors are chosen uniformly at random without repetitions. And finally, we consider full-matrix VI, a standard VI approach without any matrix completion steps, where each entry of the matrix gets observed certain number of times.
We see in Figure that VI with leveraged anchors achieves the best performance measured in Frobenius and entrywise norm. On the other hand, VI with uniform-ancee entries with high values well (as seen in the right figure), but because there are not too many entries with high values, it achieves decent performance in the Frobenius norm. Finally, even though full- matrix VI can observe all entries of the matrix, it still lags behind VI with leveraged anchors. We also want to remind the reader that VI with leveraged anchors uses only half of the available samples for matrix recovery, while the other half used for learning the leverage scores.
does not recover specific
The algorithm used in the experimental section of [35] closely resembles our LoRa-VI algorithm when uniform anchors are applied. As result, the numerical results from [35] can be reproduced within our framework, which offers a more general and flexible setting.
A.5 Low-rank Policy Iteration
Finally, we experimentally study performance of the proposed algorithm LoRa-PI.
0.25
Pll with Jeveraged anchots
Pl with leveaaged anchots
Pll with walform anchoes
Pll with unifoem anchoes
full mateix P1
0.
full marrix P1
11Qu Q2
0.15
1
0.
number crnjectories
X12
number trajectories
x13
Figure 5: LoRa-Pa PI: Q* generated from low-rank r and P of rank d 4, A 1000. 7 0.1, 5. We used K = 10 anchors, uniformly random initial policy, and noisy rewards with Gaussian noise a = 0.01. Plots for PI with anchors are averaged over simulations, while the one for full- matrix Pl is simulated once. Each simulation consisted of 20 epochs, and the number of samples in an epoch is approximately (0(1.15)'(S + A)K.
Similarly as in the previous subsection we study performance of three different methods using PI instead of VI this time, and the observed performance is similar to the one of VI-based methods. In contrast to the other methods, using leverage scores seems to ensure that Frobenius error behaves similarly to entrywise error, up to scaling factor. This might be caused by uniform dispersion of the estimation eтror over the entries with large values for PI/VI with leveraged anchors.
The choice of y = 0.1 is governed by an observation that this value of parameter ensures that the largest singular values of Q' are scaling similarly. In other words, it is heuristic for ensuring small needed for CUR-like methods. Furthermore, we believe that performance could be improved if for many
more tuned way of pseudoinversion is used. Namely, as ((+) is effectively epochs, it is crucial to implement a stable way of calculating the pseudoinverse of LQ JRR, and make it dependent
the current epoch and the level of the estimation error.
Lastly, we believe that the performance of the proposed methods can be significantly improved (compared to full-matrix methods) for larger state-action spaces, as well as by implementing more advanced way of distributing samples across epochs.
16

---

B Leverage Scores Estimation Analysis
In this section we provide the proof of Theorem 1. The proof relies on a tight instance dependent row-wise guarantee on the singular subspace recovery which is provided in Theorem 4 together with a proof. Throughout this section and for brevity, we use the notation
T
Tmax VSA
and
T ++1
(Q()")
in the entirety of this section to denote the number of sampled trajectories T,, and spikiness-relate parameter (recall definition of spikiness from Section 3.2). Furthermore, recall the truncated value matrix Q defined in Section 1, and let us define its corresponding approximation error by A Q7 Q".
B.1 Instance-dependent row-wise singular subspace recovery
Below, we present Theorem 4, which as highlighted before, is crucial deriving Theorem 1. Theorem 4. If = (a²(s + A)) and alop S ra(22)/322 then we have that the event: for every E j E [A]
d U
S S+1 A Tr
VS+ Al
|| op od (Q()))
[|U,, U1,08112=0
1ay
UR.
Tr
oa(Qa)
d
1SA A Tr
VS Al
||
ā
k:|
s.llay
+ W
Tr
oe(Q²)
(A(
holds with probability at least
8, where we define Og
T and Ow =WTW.
Corollary 1. A1 S min
dISAA)
and Tr á (a"(S + A)), then w.h.p:
T+
32VSA
(VG-
S
x: x||Us,.lle) )
|
ā
VT,
T
T,
An analogous inequality holds for [W., - WW),.
It is simple algebraic exercise to show that ||All from (1) satisfies condition of the corollary above in given regime of T,.
B.2 Proof of Theorem
Proof. First consider those states with ||U,,:113 > states and large enough T,:
d
From Corollary we obtain that for these
45
(V*
S + A Tz
(T + A)
|U - (0 S aă
x|IU,..112
log
T
w.h.p. and for some universal constant e₁ > Since
11
this implies that |U ll2
d V 4(++))= simplify last inequality follows:
IUa,; - (. U) S S2
S
k nilUa=:laalog3?
(T,( A)
8 1
Next, for T, 2 5S + A)k² log
T=(S++))
we have: |Ua, Ü.. (Ū TU)l2 s (1
V Ul, Finally, using reverse triangle inequality we obtain:
2> 1ū..11 2 (IUU,,Il2 - ||...: - -.. T))2) 2 2 IU...
17

---

and thus:
i. -0.00.111 12.
2
|00,,
s
2
Now we consider states with ||U,;:12 I
Again, by means of Corollary we get w.h.p:
48
S+A A
Tr (S + A)
- -
& 20,ān
log
log
3/2
1 1 45
Tr S
for T, 2 16c]aan2(SS) log" (T-(S+A)).
Thus we obtain that for all with 1U,,:
S
d it
48.
also holds:
11 ll2 - 112.:12- + 1U,,, (0 U))l2 S Vs
d
Since by definition f, 2 $. we obtain that E, 2 ||U,,:12 for states with IU,,; < 45'
Finally, we show similar inequalities hold for leverage scores l and Namely, we have:
l
11ell
1 Σ
11s
25.10,,.113
L.
11,,,.13
112
S
2d
4d
where we used first part of the proof for the final inequality.
B.3 Proof of Theorem 4
Proof based on leave-one-out method used for proving entry guarantees for singular vectors of SVD estimates. We refer the interested reader to [8] for comprehensive survey about the method. Here, we repeat the main arguments of the proof and improve the analysis in the following two ways:
(i) We keep track of approximation error during the whole proof in order to be able to apply it to approximately low rank matrix Q.;
(ii) Instead of showing guarantees in || 1/2- norm, prove row/columm specific guarantees. Indeed, note that our guarantees do not depend explicitly on the incoherence parameter ja but instead the guarantee specific to the row vector Ut,- of the singular subspace U, depends only on its own incoherence parameter, i.e., ||Ut,:12: This enables us to do leverage score analysis and obtain Theorem 1.
Leave-one-our method is applied to symmetric matrices, so we first redefine our matrices in this context. For matrix Q" E S with SVD Q" = UEWT define symmetrizated matrix Ma as follows:
Q Ma (Q7)T
Σ
U
U
V2
W
W
0
Σ
V2
W
WW
Σ
UT
and similarly define symmetrized matrix M from Q7, A from A, Ma from TT. and E from E Q7 Q Note that, using this notation, we have M Ma A, with rank d' 2d matrix
Ma and || | =0 = ||x A lopp = || Assume observation matrix is given by M = M + E = (T)U)l22 $ (VT U..
Ma + A + E and note that Ma ÜΣS and Ma MŪÔT. Thus, in order to prove lemma, it is
sufficient to show:
U,,, - OO,TOUT
Tmax
VSA
log
3/2
T, (S A)
VT. (M)
8
VS + A A 100
| ||
+ Ki
U2
σ (M)
T. (M)
18

---

For now, let us assume that |Biloop S J (M) and prove that such inequality holds for T, large enough (consequence Proposition 2).
Define Ma M2 + E. Fix any E [S A] and for any matrix A E R (S++))x* define seminorm:
||A||2, = ||, Now using that U = MaUE = (Ma EJUE
we have:
|MaU Ü 2)
EU 2,
| 00 U0,U,,,
d (M)
0 (M)
To bound the numerator of the first term, that -(-' 00 00 MaU OÜ (M A
U) Since Ô M Ô Ma = LÜT, we get
úल U
U-
~MÚ0'U+A00'U U0 [E + AJU
-M00 + U) AU O0 AE+
Consequently, for (+) = |M - 22, we have:
(+) & MM 00 U)ll,, + |E(U - 0 111,,
0O U)]22
+ | 1100 (E A)U |2,
Throughout the proof we use Davis-Kahani inequality (Corollary 2.8 in [8]): if E|lop (1 1/22)aa(M) then:
2 E
-U-Ū Ullop
0 (M)
Now, similarly to (39) in [37] and using that ||/B||,, S ||/||2,,.
Bloop we obtain:
2
||Ma(U - (0 < 2| Σ op
(M)
A -0T - 2|| A 2,1 a (M)
op
| 2.5 <
2.a
U up S A 22,
Using these inequalities together with Lemma 3 and
Ellly A llop (2r
1/16 obtain:
Σ lo
(+) $ |||
2, +
U
2, ox (M)
op + | lop) - - U) U0) + |E 2
which in the end gives
||U O0 Ul12, S
2
(5]IU)
22.
Σ Ollpp
E|
+ ||llop) |EU|22
ox (M)
σx (M)
- U)lu)ll + + |2.
(9)
Leave-one-out decomposition:
Define matrix M as follows:
M J.k
Mr
My
otherwise
and let ( denote matrix of d' dominant singular vectors of ( Then, by triangle inequality can write:
EEU - Uल U1)2, < EE(U- - t (ū())) (U)),, + E llp Ü (1()
U||
19

---

We bound the last term using Lemma 4 to obtain:
|E[UU - 00 U) U0"U)ll2+ 2
U ( 1)|
| op
EU 2, + B|
+ ||U - -( U)lla.)
de (M)
(10)
Substituting (10) into (9) we obtain:
Σ op
|U - 1U-Ú0 U22 2, S oe (M)
(1U]
E Blop + || + EE 2
Od' (M)
+ E(U - (Ū)) U))2, + |4
Then we apply Proposition on |EU and | + ( U)) We use that |U|F S v
and | (T Ull < 2vd d. Finally, we use that | 2 I v5 Alj the fact that
oa' (M) oa (Ma) - || A llop or (Ma) 1/32)
and thus
| Ty (.M)
|[ op (Ma)
2x.
B.4 Rank estimation guarantee
Recall from Section 4.2 and Proposition 1 that, given the singular values (ōi)s of our estimates Q7. estimate effective rank as follows: d ΣSAA ( 2 B} with
2 max
SA(S A) log" ( A)T) (1 71-
Y Ymax V VSA
B
+
TT
T
Here we repeat first part of the Proposition 1 and prove it: Lemma 2. I satisfies (5), then estimated rank d satisfies d= da with probability at least - 6.
Proof. By our assumptions a;(Q") > 0 only for E [d=], and thus vi > dz 6; S || - Q llop
and vi v d, à; Fd, (Q*) - || Q" llop- Recall that F. = O OF and A Q Q" and thus:
प - Q" olo S 1|llppp + ||
We bound the second term by ||p S / and use that || A S Emp from Lemma The
first term is upper bounded by Proposition 2. Combining the two, we obtain that ||Ê Q" ol S B with high probability. Thus, for 283 ad, (Q") we are guaranteed to recover the true rank d, since then Vi E [dw]:
8 2 oa, (Q=) - |ςē - -Q" 2 28 $28 B
is straightforward to check that, if
T Ω max S SA(S + log" (15-177
2
))²
then first term in definition of is < od. (Q*) and similar conclusion hold for the second term
after noting that Traax / (S + A) 2 1.
dd (Q")
B.5 Technical lemmas from the proof of Theorem 4
In this section we shortly present concentration results used in the proof of Theorem 4. We refer reader to Section F.2 for discussion about equivalent noise model and Poisson approximation. Concentration inequalities proposed are fairly standard (see for example [8]). but as discussed in [37] because of the sampling pattern, entries of the matrix E are slightly dependent. way to deal with these dependencies has been discussed in [37], and refer to the results from that paper here directly.
20

---

Proposition 2. Ler B be a (S + A) 2d matrix independent of E. Then, we have for all á E (0, 1),
for all T, 2 (S + A) log" ((S + A)/ both events:
B op
Tmax
SA T
VS
+ A
Alg
3/2
T7(S + A)
8
vi [S+
E B 2
Tmax
B
|Fv
SA
log
7+ + A)
T
hold with probability least 6.
Proof. Follows straightforwardly from proofs of Propositions 26 and 27 in [37] and using noise equivalent model from Section F.2. Note that we keep the variance term upper bounded by |||]i in the proof of Proposition 27 as in [37], and make use of inequality [/ S || to obtain dependence on |B|| in the second inequality.
Lemma 3. If E S o /M) then for every i:
BBllop + +| (|U1|2,))) + |2,,
J00 T (E 2) I
(M)
+ |E 2,, + IIM(UU O0 T U)]l2.)
Proof. Under condition
||| S o. (M)/33 we have aN (M) 2 ( - | 2 a (M)/2. Thus,
have:
(B+ 1 (EEAE)+JJI
A)U 2, = MUS - E + U 2.
E lop
- || 12,01
llop Ullop - M 2.
σ (M)
E op + | og | 2,4
< 2
(11)
Te (M)
Using Davis-Kahan's inequality [8] we have:
|| | Üsgn Ü U)
< MOO T Ull2. + | 12 |gn 1
U)
< MMOTU U12. 16 M
2,, a (M)²
1l22
< |MO U1|2, +
2
implying that M 2. s 2
U U||,, Furthermore, we have:
|MUUT Ul12. $ ||M 2,r + [M U TÚ
||U| 2. El + [| + AJU]22, + II ūū U)]22
where we have used that MU UE. Substituting this expression back into (11) finishes the proof.
Lemma 4. Under assumptions probability for every i:
A op S aw (M) and [ op S ar (M)/32, we have with high
6 (MM)
EU 2,5 + EE(U (( (T)
+ 2 E lop (|2 + U - Ú T U))l2.)
21

---

Proof. Proof follows similar steps Step 2.2 in the proof of Theorem 4.2 in [8], but we repeat it here for the sake of completeness and focus on differences in the proof caused by A matrix. First, we use that U is an orthogonal matrix (lop 1) and Davis-Kahan's inequality to obtain:
II - MO)
) - S ( Oū |l S o (M 0 01
Note that under the assumption | S o (M) analysis of singular values stays the same as in [8]. since, for example:
0 M (M 2 oa (M) ||| opp 2 or (M) (1-
08+1 (M - +1++1 + op - | lop + |Ellppp I a (M)/16
Thus, we can lower bound denominator in the inequality above by or (M) Now, term in the numerator can be written as:
(M M7 1 = E., 0 + (E.; E,,ee [
and bounded in the same way as in [8]:
IIM M 1 || < |ET 12, | - E,seil22 ( | 12,
|E 12, 2 E| t ((Ō))) U))la
where we used that [I((O)TT)
1|2 S 2 under our assumptions. Finally, we obtain:
| ( <
4
EU 2,,
2 Bl Ö l)
σ (M)
2| Ellop Ü0 U t (00))
and under condition E op S oa (M))333 we obtain result claimed in the lemma.
B.6 Nuclear norm minimization for leverage scores estimation
The authors of [34] leveraged the guarantees for nuclear norm minimization from [9] to learn Q matrices. However, several factors make the application of nuclear norm minimization theoretically challenging our context:
Approximate low-rank structure. As algorithm is based on policy iteration, estimates Q7 are only approximately low-rank. The result from [9] rely on non-convex opti- mization, leaving it unclear how this approximation eπror affects the final guarantees of the algorithm. In contrast, a more straightforward analysis using singular value decomposition allows to explicitly express bounds in terms of the approximation error.
* Coherence-free subspace recovery. In our subspace recovery result (Theorem 4), we can bound the subspace error |U Oz ll in relation to Ur: lz- It is uncertain whether current guarantees for nuclear norm minimization can achieve a similar outcome, which might instead depend (ax ||U,,:12 /l2. We believe this would introduce dependency the incoherence constant into the sample complexity of our algorithm.
22

---

C Leveraged Matrix Estimation Analysis
In this appendix, provide the proof of Theorem 2 corresponding sample complexity guarantee enjoyed by LME. First, we provide the pseudo-code of LME:
Algorithm 2: Leverage Matrix Estimation (LME)
Input: Deterministic policy n, sampling budget T
Set 1 t T/2, + T/2 1/2
Set = - t- (I-7) log T
- as in (1)
T-
(Phase 1). Leverage Scores Estimation:
(Phase la.) Data Collection & Emprirical Truncated Value matrix.
Sample uniformly at random T1/ T1/(T + trajectories of length + 1 using policy π and
gather them in D
Use the collected dataset D. to construct O7 as in (2)
(Phase lb.) Singular Subspace Recovery
Set the threshold (3 as (4)
Compute the SVD of QT and threshold with 3 as described in (3) to obtain d, Ú, W and Q (Phase Ic.) Leverage Scores.
Set the left (resp. right) leverage scores & resp. as described in (6).
(Phase 2.) CUR-based Matrix Estimation with Leverage.
(Phase 2a.) Data Collection with Leverage & Empirical Truncated Value Matrix:
Set K < (4ddogg644d]
Sample K rows (resp. columns) I C (resp. I C without replacement according to the leverage scores (resp. P)
Th Set N1 + 3(r=1)KT, N2 + 2(r+1)(R(S+ A) 2
To
For all a) E Qn (resp. (s,a) (24) sample N₁ (resp. N2) trajectories of length + using policy and construct the
empirical estimate Q (s, a) based on these trajectories
(Phase 2b. CUR-based Matrix estimation)
Set the matrices L and R as in (7)
Construct Q using CUR-based approach as in (8)
Output: Q".
C.1 Proof of Theorem
Before showing the proof of Theorem 2 we present two intermediate results used in the proof. As an immediate consequence Hoeffding's inequality we have:
Lemma 5. With probability at least 5 we have ((s a) E (I x A) (S x T):
(s, (*
a)) < 1
Fmax
2 N
log
4K(S + A)
+ ||Q7 - 17
8
where = N1 if (s E Un or N N₂ if as E ΩΩ_
Theorem 5. Let I and J be such that [Z) K, and (I, has rank d. Assume that for
some ED, E > 0:
a) V(s, a) E x (5, (" a)l s eD, and
b) a( E [I A) U x J) \ (I J) (s, - st.
If fn < sczez
1 aa(Q")
log 2 (S+A) < | 1o0 and K 2 64dlog(64d//5) then with probability
VSA
&:
VSA
/S+A
SA
/ S + A
1 Q² 11o00 $ | -+ oa(Q*))
1og2
||Q" 113 &D σ (Qx))
log
23

---

Proof of Theorem 5 is deferred to C.2.
Proof of Theorem 2. First, by Theorem 1 we require at least
2 max
|| Q2_ SA SA
(S + A)T
R (S + A)
log"
(12)
(²(
(1-
number of samples to recover leverage scores of Q" During the whole proof of Theorem we condition on the event where Theorem holds.
Recall that we use N1 1(++1)K2 N₂ ((+H)(((++A)22K2 and define the following quantities:
En 1
Tiax
log
4K(S + A)
E+ 1
Tmax
log N₂
4 + A)
N1
Note that by definitions of N1 and N2 we have that EO = E+ S+A-2K Next, recall that |0
1oo is upper-bounded by Kupas from (I), Combining this with Lemma 5 and our definition of 60 we can see that the conditions a) and b) of Theorem are met.
Hence, by Theorem we obtain that ||ÂT - QF S
E_
VSA log? (5 (1 + 1Qt | Io oa(
VSA az((²)
log" (5t V S+A-2K
Setting e+ to be equal to this value obtain that is sufficient have:
N₂ =2 r
IQ 7)2 03(0²)
(1 (1+ IQ g0(2²) S+A- - 2K
K
(5
S ( A 8
[(S + A)
log"
log²
6
Using definition N2 and rewriting inequality above in terms of T' gives the following condition:
2 T "max
d 1
(s A A 1 SA
(5+11)
(S (S+A)
(8 (SS
log
log"
382 (((2²)
03(Qa)
5
5(1 7)
Combining this with condition (12) and using the fact that condition:
1Q1112.44 (
I x²aad gives the final
T= Qs max a d(s + A)
f2 2
x²
dazn2
e + (S + A)E²
(1 713
Finally we verify that en and 5 satisfy conditions from Theorem 5. Note that |Q
VSA au(
||Q llo [Q=ll IF 2 1, well log² ( ($$4) for any 8 E (0, Thus we obtain that E S E and
thus, in order to have I 10 is sufficient to assume that $ || Using the same reasoning we have:
oa(Q²)
K S A
oa(Q²)
/S (S+A A 8
9D S E+ S+A S 11 Io (StA)
S
log
VSA
whenever & ||0T and S + A K.
C.2 Proof of Theorem
Note that (T. ( in general, and thus our estimation is different from a) used in [35]. However, weighting estimates by inverse leverage scores proposed in Section 4.3 still provides unbiased estimates, in the following sense:
(
Lemma 6. Assume that [Z] = K and rank(Q") = d. Then:
V(s,a) E S A:
24

---

Proof of Theorem 5. The proof follows from the proof of Proposition 13 of [35], to which we refer the reader for a more detailed exposition. Based on Lemma 6 and following the proof of Proposition
13 [35] (see (22) and (23) in [35]), we have v(s, a) E S x and (*) == == (5. - Q" (s,
(+) S 10t.:/000.....IaaAAAA.....EE.000
+ -[)
llop LQ (I, q (s, R) (13)
We will repeatedly use result from Lemma 8 and condition the event when given bounds ||op and [| hold. We begin by bounding the first term in (13). Using the assumption that
(s, EIx J: (8. Q (x,a)) S we obtain:
S
(S+A)
S SicJeuV/Alog
5
Combining this inequality with our assumption on em and Corollary 2 with vi = 1/4 gives:
cI(L()(I.T)RR)
1
(1))
8
aa(Q²)
Second term in (13) can be bounded as follows:
- - (
$
and then use that:
-0. 01 + +
(21
Combining this result with Lemma 8 we get:
(S+A)
- -
czcc +
(~8 8
Similarly to the proof of Proposition 13 [35], we bound the third term from 13 using inequality || - A'llop I LtvE
2 m
1|
| 11 H Allop as follows:
(LQ ( 1bp S 64cTey 0²(
ED
VSAlog
( SS+A A
And the last term from (13) can be bounded as follows:
(s &
(S A (8 8
$ ScccyVSA|Q log?
where we used that [IQ" J)l - 11 Combining all derived inequalities obtain:
VSA
(S A
1²²h Q" I Sezcy 1044 + +2) (a(
log²
8
SA
S A
64 a
log
25

---

Proof of Lemma 6. First, define matrices Du. Dw E ER by Du = LUz.: and Dw RWJ.:
and note that D and Dw are not orthogonal. However, we claim and prove in the end of this proof that:
-D (D
(14)
Moreover, since Do and Dw have full column rank, have that Di laxd and (D laxd. Thus we have v(s, E x A:
Q" Q( -,000,000,0
6a
= UD (D) ca
=C_UEW ca = (s,
Now proceed with proving (14) following similar argument in Lemma in [14]. Let SVD of Dy and Dw be given by Dy UD ED. WDD Dy and Du = UDw DDw WDw. First, we use that UD. and UDw are orthogonal matrices to get:
(DeED = (UDu ED WD EWoW Dow UDW! )
= UDw (EDy WD DWD,, EDw> UU
Since De and Dw are matrices with full column rank, all matrices inside of the pseudoinverse are of size d x d and full rank. Thus, their product is as well full rank and replacing pseudoinverse by inverse we obtain:
(f UDw Ep W
(DW))E-DD
C.3 Concentration results for the proof of Theorem 5
Lemma 7. Assume that p is a probability measure on S such that p. 2 1] Mis,lll
for all E [S] and i.e. for any
some 7) E 1]. Let I be set obtained by sampling K entries of S according i E [S] : with probability min (1, Kp.}. Define diagonal matrix L with entries min(1.KKpp))
for E I and matrix Dy E Kxd given by Du = LUI,, Then, for any å E (0, 1):
2d
IDD Du Taxallop 2/ Kn
log
8
holds with probability at least - 5 whenever K
4d log 2d
Proof.
First we argue that case p; k is simple. Denote by S states for which p3 S +/4 Then, we have:
DDD Taxallop = IUT, 1.2z. Ullop
Σ
TZ()))
Σ (Z()) T(
iEInS
iES,
where (+) are obtained from U by zeroing all rows except i-th, and 8,'s are i.idd Bemouli(KKp)) for i S4. Now we can rewrite the first term:
2(20)T2001
Σ
S.U,UU...
Kp
FES
VES+
and take expectation over 6,'s to get Eies, (7(2()) 70 ( = Eies, (Z()) (Z))) z(0
Now, define x (i) = (6, - KP:)) Kp:
U.T Un, for E S4. Note that:
| 1lop
10 Kn
Kp:
26

---

by our assumption on Moreover, using that Var(o,) = Kp:(1 - Kp:) I Kp: we have:
E
Σ #ESI
(X(O)
Σ iES
E(o, - Kpt)²
U UU.
Us S
Σ
U..
K2p
Kn iES
implying that | X (X S Knj Finally, noting that ( are symmetric matrices vi, we apply matrix Bernstein inequality obtain:
Kn t
DU Laxallop 2t)
Σ iE(S]
x
2t
S exp
2d 1 +
Setting right hand side equal to 6 finishes the proof.
Corollary 2. If anchor states of size least K we have with probability 2 ô:
1ed log(4d/6) are chosen according Lemma
"
1 f00(00))
oa(LQ - o (DDbDDDW) 2 oa(Do)ol(""oaa(On
Note that we could use inequality above since Du and Dw have full column rank.
Lemma 8. Consider setting of Lemma 7. Then there exist universal constants cr, CJ > 0 such that with probability at least 6:
S
s 7
A K
A 7
11 CI\
log
|Rllop S CJ
log
K
Proof. We note that if Li,
(iee Kp: 2 1), then obviously the inequality above holds for 2 K, and thus we consider only cases where Li,- <Kp. Now, note that [| = ||
where L ox = Ei= 6, TRp eee," and where 8, are i.d. Bernoull((Kp.. Next, we have:
Elo, Kkp Le,,l = KKpeee and thus:
EL 1
K max S VK
Define (0) (6; Kp.) /Kp. eee_ We have E| (Y()) = (1 Kp.)cee, and hence the variance term in matrix Bernstein is upper bounded by 1. Lastly by our assumption p have for all i E [S]:
S
| 1lpp S
$ cv
/Kpi
K
By matrix Bernstein we obtain:
P Ex op 2 t) =P =P
|
y())
21
2S 2Sexp exp
iE|s]
1 + t
Equating last term with 8 and using that S, > we obtain statement of the lemma.
27

---

D Sample Complexity Analysis of LoRa-PI
In this appendix, we present the proof of Theorem 3. It is direct consequence of the performance guarantee of LME (see Theorem 2) and enror bound on approximate policy iteration, which provide in this appendix (see Lemma 9).
D.1 Proof of Theorem 3
Proof of Theorem 3. start with, we first observe that, according to Lemma LoRa-PI outputs with |V V$ lloo I it holds that
2r m'amax? 7 (Naset))
(
x | - V=(
1100 I
E 2
1
(1 (1-7)
(ii)
(Q(00 (2) -Q S
E [Noooctss]
where introduce the notation Q(t) Qa(()) shorthand. Now, note that condition (i) is satisfied if
1
4r max
Nopochs
log
1
((1 7)E
which is already as chosen in LoRa-PI. Now, in order for (ii) to hold we use Theorem 2. We define the events:
& 1-000----0 S (1 11-77 (1-7)?E
4
We show that Dee[Nau & holds with high probability. To that end, it is sufficient analyse for each I [Nepoct),, the event E conditionally the event that (Dkett-1j&R) holds. Indeed, by using the elementary inequality P( U ( < P(EE(B) + P(B") in a recursive manner, we can write
PP(NLE (aguaal E P(UrE (N E8)
Σ
P(ε OkE(t-1] Ex)
(15)
NE (Neparte)
will show that all E [Nepochs]. P(E [kelt-1 Ex) S 8/ //Neposss which would entail that
P(( P((NeE[Nawaa)) Ee) < 5 and ensure that V V |cc I 1 - holds with probability at least
Let / [Nepoche]. Note that by using Theorem 2, we can immediately show that P(E Nke[e-1] Ex) S 8/Nepochs provided that
T
2 = ② mmxx add ((S A) aad)
N Nepuchs
log" 10
Napochs
7E-
which entails, by definition of Nepochs chosen in LoRa-PI, an equivalent sample complexity to
T == δ max 1 aadd ((S + A + a²d)
(1 (1- 7)E ) log ((1 (1-7)
F Fmax
Finx
log
log
(1 (1-2)8E2
(1 700
x 2d ((S + A) a²d) log 10 (c/8) log(e/E)
(1 - 882
where we emphasize that ((-) may hide poly-log dependencies on A, (1- (1-7)-1 -1 d, K, at Tmax log(e/e), log(e/6). This the desired sample complexity in Theorem 3.
Note that Theorem also requires that
(1 - (1-7)E
<
(1 oo
(16)
28

---

We show that this is satisfied by the condition E S First, we show that under this condition, we have || & 2||0(()) floo. Using Lemma 10, and conditionally on the event & holding, we have that for all l
2e
1ST (viktt)+ + 1-7 2e(k) 1 S (T.(Wettt) + 1-7
27c
(V(()) S ((+1)) +
1-7
where e -'-2)'s, implying, in particular, that
2y(1 -7)e
1 1l ||0 +
2
Summing the above inequalities from to / 1, together with the fact that / S N Nepochss gives
_100) 1xx 1|0 7(1 7) 1)s
(10 1|x0
7 log
4 4rxax
2
(1 ()-
In view of this inequality, we note that 2110(()) 1100 2 110 if
4r maxax
ye log
- 11000)000
- 7)
We can verify that the above condition is implied by:
1
167 max 47 log ((1 (1-
|0 x
85
(17)
8
IQ
27 log
16 (1-7)9 (Q00 1
where we used the elementary fact 2 2a log(a)) 26 = x 2 alog(z) + b for a, 0.
Thus, from (17) we conclude that the condition on E, (16), satisfied the following condition holds:
(1,
1
S min
1,
2y log
16 (1-7) (1-7)=1QQ())
This is the desired condition on in Theorem 3. With this we have concluded the proof.
D.2 Error Bound for Approximate Policy Iteration
The following result, a standard variant of Proposition 6.2 [4], shows that the described approximate policy iteration is guaranteed to converge within an e-accuracy.
Lemma 9. Let ){21 be a sequence of deterministic policies selected recursively described in
LoRa-PI, and denote V(t) = v* for all t 2 1. Let > 0 and suppose for all 2 1, it holds that
1Q/0 - 100 Se.
Then, for all t 2 1, we have
||V- y(+
< +'1l | (()) + (1 7'-
2e
The proof of Lemma 9 follows standard arguments, but we provide for completeness.
Lemma 10. Let a be a deterministic policy, and assume that I! 1o S Assume that policy a' is selected greedily with respect to Q", i.e for all s E S, (s)) arg max Q= a), then
2 1.
V < TV(**) < y +
7
29

---

Proof of Lemma 10. Before we proceed with the proof, let us define the composition of a determinis-
tic policy x" and a Q" function, x" (s) == Q" TT (s)). We know that
V = = o Q" I max x" o Q" = (V=*)
where < is applied component-wise. Next, we have
v S (V") max T" Q" S max T" o Q" + max T" (Q 11Q--Q" Q²")
x"
S T +el
S o Q" + o (Ô - Q²) +el
+v*))+*+2at
where Tx is the Bellman policy evaluation operator. By monotonicity of the operator Ta, we can re-iterate
(=(V)) (T+ + + S (3(*)++ 2ye1.
Thus, we finally obtain
V ST()) S T T (V=) + 2E
Σ 7/ 1.
Taking k + oo, we get
2e
V ST(" + 2el S V*
1 1- 1.
Proof of Lemma 9. We start by noting that, thanks to Lemma 10, we have: for all t 2 1,
2e 2 Tv((()))
v(+ + 1-7
where 2 is applied component-wise. Thus, applying this inequality recursively we obtain
2c
2c
20
v(+1) + 1
12T
[(0) +
1
1-7
7
> (TT) (v(--1)
207
1
2 (T))(((())
2e
1
1 1-7
W=1
2 (())
2c(1
7²)
2c
1 +
1,
(1 7)2
1 1-7
which gives at the end
2c(1 - -2t)
v(+1) > (T)))
(1 7)2
Thus, we have
V v(+1) v(+1) ( 2c(1 26(1- 7²)
1 1 5 - 2c(1 - 7²) (1 7)
1
(1 7)-
Thus, using the contraction property of T and that - gf $ 1, we have
2e
2
| - || < -
+ (1-7)) 7) S ~
(()) |o0 +
(1 - 7)
30

---

E Extension of Guarantees to Approximately-Low Rank MDPs
We consider the setting where the matrix QF is approximately low rank. Specifically, define constant Ça such that Ça = I|Q" (s, a)
where Q2 is the best d-rank approximation of Q" in the operator norm. Note that Ça S auti (Q") VSAGa In contrast to Theorem 4, where the additional perturbation term Á arises from controllable quantity (through roll-out length r), here we assume that Ça is fixed in advance and unknown. For simplicity, we omit terms stemming from the perturbation, but the results still hold in that setting. Here, we show that if:
Vd
Sa =
oa(Q²) min
(A+)
S KV SASA
can obtain similar guarantees for ||** lo as Theorem even in the approximate low rank setting, with an additive error scaling with 0 ( Cadn theorems still hold this setting.
Next, we show that our three main
Theorem 1: Leverage scores estimation. 4 to obtain, with high probability, Vs [S]:
We can repeat the arguments from the proof of Theorem
(V
S + A T,
+ SavS + A oa(Q²)
(Q")
a U2,08112 =
+ +.IUU,,112 (a(QT)
if if = inequality above. A similar inequality holds for the rows of the matrix of right singular vectors W.
2 (a? AA) A)). and (Q*) < oa(Q")/64 New terms are highlighted in blue in the
Under Assumption A4 and using that (a+1(Q") S VSAÇa, we have:
SaVS + A = Ō Vd
kl|Ua..ll2 Ca+ (Q (1UU,,112)
and
(Q(
VS+A
od(QT)
indicating that the contributions of the newly added terms negligible for leverage score estimation and that Theorem still holds in this setting.
Theorem 2: Complete matrix estimation. Theorem 5 holds with the same arguments. Instead of Lemma 5, we have that with high probability: V(s,a) a) E (I A) (S J):
@ (s, a) - (",00"""
(s. S Tmax
2 N
log
[K(S + A) + Ca
1
Note that conditions on and I (Q²)) ensure that the conditions eg and in Theorem: (EM $ (Q))
log" "og-2(a ( E+ $ ||QT (l0e) still hold, as:
VSA
Ca Ō [ Ō
VSAIQT (11
δ
S
8
+ A
S+A
Then, the upper bound on 1 Q7 from Theorem 5 will include an additive term: 11 log* (StA) Ō (Sadx²a aa)d Finally, under approximate low-rank structure, Theorem Sa d(()))
2 guarantees that with high probability, if Z I1Q and = ão ((5+A)+024 ( aadd)))
(1-7)822
have 1ςỘ² 1b + Ô (Sadn²a?).
This aligns with Theorem in [34], where the approximation error scales by terms corresponding to SA ? in setting, as both methods CUR-like matrix recovery. (
Theorem 3: Guarantee for LoRa-PI. PI. Based on the approximate policy iteration theorem, which claims:
(1 [1->)llV* - v$1 1o < 2rmax Nopole + 2 max
[1@(1)
Q*(*)) I
tE [ypccaa)
we observe that the error from approximate low rank propagates through the second term, yielding an additive error of magnitude Sad to the error of Theorem 3.
31

---

Miscellaneous Results
In this section, we provide some of the observations and results about the truncated value matrix. More specifically, we present the proof to Lemma 1, and a discussion on the variance proxy of the truncated discounted sum of rewards.
F.1
Truneated Value Matrix
Proof of Lemma 1. We know that Q" satisfies the following identity: for all (s,a) E E A.
(") = Σ r
(5 ag) = =s)
=
Σ x/-rr r3
(5), all = (3,
+
Furthermore, note that
7
ri
T 0g) = (8,
S
Tmax
7
r maax
L----1
and thus
10 - 101100 S T'ax
Tmax
exp exp(-r(1 -1))
1
where we used that y v exp(7 - for E (0, 1). Setting the right hand side of the last inequality
equal obtain statement of the lemma.
F.2 Equivalent Noise Model
Recall definition of Q from (2):
SA (+,
N
Σ Thi Il "(()))) V(s,a) E ESx A.
N
k=1
Consider one of N sampled trajectories with index h starting from (s (k,0) = (s, a), and note that
Σ
r'
The
S
Tmax
1 -
Moreover, since Q is given by:
~
T
Σ
2 rr 1l (15t) = =8,08 =
we have
Σ TT (15 (5k ak.) (2.0== = (s.00) = QT a) (7
In other words, each term inside of the outer loop in definition of Q is uniformly bounded and equal to QF a) ((5 in expectation. Thus we can view estimate Q (s, a) equivalently as:
SA N
N (s, + (0
(7
Σ
32

---

where Ss,o are i.idd across k, and (27(s, + Eo.a.kl S subgaussian random variables.
Imax 1-y²
implying that Es,a, are 1-?
2rmax.
Next note that the number of times (s) Ex= 1( %%,0) (s. a}} that we sample entries are random variables with multinomial distribution, since P[( o7.o) (s, a)) 5 and E(..)) ()) N. This weak dependence between the entries can be dealt with using the Poisson approximation argument (see Section C.2 in [37]). Essentially, this enables to rewrite matrix Q as matrix with i.idd. entries. Namely, we have for all (s, a):
(e,u)
SA
(s, = N Σ (o) + Ss,a,k)
where ((s, a) are ii.d. Poisson random variables with parameter E[Y 3A The fact that the two noise models are equivalent is depicted in Lemma 20 in [37] claiming that probability of an event under the multinomial model can be upper bounded by /T times probability the same event under the Poisson model. Practically, this adds multiplicative factor of T in probabilistic claims. For more thorough exposition of this issue check Section C.2 in [37].
33

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: To the best of our ability, we believe this to be the case as can be seen in our manuscript. Please refer to theoretical results throughout manuseript and Appendix A for the numerical results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Our work primarily theoretical, and we have discussed our results and assumptions whenever presented in manuscript.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
34

---

Answer: [Yes]
Justification: Please refer to the statements of our theoretical result and corresponding proofs in the appendix. To the best of our ability, we believe the proofs be correct. Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Please refer to Appendix A and provided code in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
35

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
Please refer to Appendix A and provided code in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //niss... wttpcccppppppeeeeeeeeeecccccceet htteg/duddeee/eeebniiittst /CCo///oodissssseeeeeeeee ssssonolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
Please refer to Appendix A and provided code in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Please refer to Appendix A and see provided code in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
36

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please refer to Appendix A.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the ines?
NeurIPS Code of Ethics https: http://wwwr...ppppppcii/e//////e
Answer: [Yes]
Justification:
To the best of our ability, we believe this to be the case.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper presents work that is primarily theoretical and whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
37

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswi twwoee.hooo..... com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
38

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
39


Reviews:
[{"review_id": "X2vyLF9XNR", "reviewer": "Reviewer_WY9t", "summary": "In this paper, the authors consider the problem of learning an $\\epsilon$-optimal policy in systems with low-rank latent structures and is order optimal under weaker conditions. The proposed algorithm iterates between exploitation (policy evaluation) and exploration (policy improvement). For policy evaluation, the entries are sampled in two stages to complete matrix estimation. The adopted approach provides entry-wise guarantees with respect to the spikiness of the matrix.", "questions": "- Theorem 1 shows that the Leverage Scores Estimation depends on the $d^{th}$ singular value, Wouldn't that impose constraints indirectly on the rank/spikiness of the original matrix?\n\n- In Line 285, is the subscript of $\\Omega$ a typo.", "limitations": "- Minor Comment: Please elaborate on acronyms before using them. The goal is to make the paper self-contained for a first-time reader as well even though these acronyms are widely known in practice. Line 10 - CUR, Line 30 - MDP, Line 88 - ERM, MLE\n- Can the authors compare the simulation results in Appendix A with existing approaches akin to [35]  to showcase if their algorithm indeed works in a practical setting?\n- Can the authors also showcase how their algorithm holds for different values of rank, spikiness, and condition number?", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The authors have done a great job of clearly defining the problem they are trying to solve and conducting a thorough literature survey showcasing the existing work as well as how their results improve upon the existing work.\n- The proposed algorithm is parameter-free which implies that it does not rely on spikiness/rank/coherence bounds to work. Similarly, the lack of dependence of sample complexity bounds also shows the strengths of these results.", "weaknesses": "- The notation can be hard to read especially as l and L and r and R imply completely different things, while in most cases they imply smaller letters imply matrix entries for the matrix indicated by the larger letter.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable review and positive feedback! Please find our responses below.\n\n**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.\n\n**B. Numerical experiments.** \n\n- **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. \n    \n- **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. \n\n **C. On notation.** \n We thank the reviewer for giving useful feedback about our notation. Here are answers to your questions:\n- 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.   \n- 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. \n- regarding acronyms: We will add descriptions of the acronyms we use. Note that CUR is not an acronym.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0f11tM5pAN", "reviewer": "Reviewer_Fr8E", "summary": "The works present a policy iteration algorithm that relies on supposedly low rank structure of value function (Q-function)\nThe proposed work first estimates the low-rank matrix of a given policy before performing policy iteration step. The Leveraged Matrix Estimation (LME) algorithm learns the Q-matrix for a given policy. LME for a given sampling budget estimates Q-matrix in a 3 step process.\nThe policy iteration algorithm also uses LME at the policy evaluation stage.", "questions": "See weakness", "limitations": "See weakness", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The proposed Q-matrix estimation and policy iteration algorithm are interesting for sparse MDPs.\nSample complexity bounds for the algorithm\nAnalysis is easy to follow", "weaknesses": "It is not clear where such low-rank Q-matrix appear in real-world. Is coherence and spikiness of Q generally appear in control problems?\nCan authors show any real-world application like gym environments?\nThere is significant body of work that leverage rank deficit structure of Q, it is not immediately what are the additional\ninsights the current draft has over the past work.\n\nCan you compare with other algorithms proposed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! Please find our responses below.\n\n**A. Appearance of low-rank $Q$ matrices in the real world problems.**\nLow-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.  \n\nFurthermore, 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.\n\n**B. Coherence/spikiness always appear in real-world control problems.** \nCoherence 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. \n\n**C. Numerical simulations in gym environments.** \nWe 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.\n\n\n**D. Comparison with literature on low-rank $Q$-learning.** \nFor a comparison with past work, we refer the reviewer to Section C of our global rebuttal.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ehODdZBZqp", "reviewer": "Reviewer_9Ehq", "summary": "This paper considers the reinforcement learning problem with low-rank latent structure. The objective of this problem is of learning an $\\epsilon$-optimal policy in a tabular setting. For this problem, they devised LoRa-PI (Low-Rank Policy Iteration), a model-free learning algorithm alternating between policy improvement and policy evaluation steps. \n\nTheir main innovation lies in the latter part where the algorithm estimates the low-rank matrix corresponding to the (state, action) value function of the current policy using the following two-phase procedure. The entries of the matrix are first sampled uniformly at random to estimate, via a spectral method, the leverage scores of its rows and columns. These scores are then used to extract a few important rows and columns whose entries are further sampled. The algorithm exploits these new samples to complete the matrix estimation using a CUR-like method. For this leveraged matrix estimation procedure, they used spikiness instead of coherence (two-to-infinity norm assumption).", "questions": "- (Important) Is spikiness always better than coherence? The authors state that in a specific case, spikiness could be finite but coherence could be very large. Is there a case where coherence is finite but spikiness blows up? To use the word 'less restrictive' I think this proof is also necessary. \n\n- (Important) Table (mentioned in the weakness section)\n\n- (Important) Could you explain how your threshold of the singular value could be free from the rank $d$? In many sparse linear or low-rank estimations, rank works as a parameter for the threshold. To alleviate the rank condition from the threshold, one must assume the minimum signal condition, such as $\\sigma_{min}>\\epsilon$ for some $\\epsilon>0$. Seems like in your paper it was possible since you assumes 'minimum signal condition' on Theorem 2, $\\epsilon < \\sqrt{\\frac{S+A}{SAd} \\sigma_d (Q^\\pi)}$. You don't know $d$ or $\\sigma_d$, how could you be sure about this? One main selling point of this paper is that the learner doesn't need to know $d$ or minimum eigenvalue conditions before the game starts. (line 224-225)\n\n- Is there any great idea to extend your estimation idea to the model-based method? \n\n- This idea works well in the tabular setting. What about the non-tabular settings, such as linear RL? Let me know the difficulty of extending your result to linear RL. \n\n\n*** Minor points\n\n1) Maybe using $\\sigma_{min}$ instead of $\\sigma_d$? Researchers frequently use $\\sigma_d (Q^\\pi)$ as $d$-th largest eigenvalue and $d=\\max_\\pi rank(Q^\\pi)$. This means in the traditional notation $\\sigma_d(Q^\\pi)=0$. Though they've mentioned it in their related works, it would be better to change it as $\\sigma_{min}$ or define $\\sigma_d$ somewhere near the Notation paragraph.", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1) According to the authors, their matrix estimation method is the first able to yield entry-wise guarantees that do not depend on the matrix coherence but on its spikiness instead. \n\n2) The authors used the tabular setting where entrywise estimation is important and applied an estimation method that fits well with entry-wise estimation. As they mentioned in Lemma 1, the singular value difference could be very large, but the tabular setting lets authors focus more on entrywise estimation. I believe this is a nice strategy for writing. \n\n3) The authors clearly state why policy iteration is much more useful than value iteration to alleviate condition number assumptions.", "weaknesses": "1) Readers might think this is another application of low-rank estimation literature. Of course, this type of 'adapting results of other fields appropriately' studies is also important in the research, but I'd say this is not ground-breaking. \n\n2) (Important) I am not sure how meaningful the transition from 'coherence' to 'spikiness' is. Maybe it is directly related to Question 1. If I understand correctly, this is the main reason for using the CUR-based matrix completion instead of others, but I believe the authors should provide a more convincing reason (such as theorems?) to make authors study CUR-based matrix completion.\n\n3) (Important) It is not clear how much improvement they made. It would be great if there's a table for low-rank RL that compares the performance/assumptions of previous works concisely. Could you add a table of reference that includes all low-rank and many recent tabular RL results to see how much improvement you made?\n\n4) (Important) Dependence of the threshold parameter $\\beta$ with parameter $d$ or $\\sigma_d(Q^\\pi)$. See the questions section for details. Also, this $\\beta$ seems very important, but it is written in the appendix. It feels like the authors are trying to deceive readers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful and insightful review! Please find our responses below.\n\n**A. Our low-rank matrix estimation method is novel.**\nThank 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. \n\n**B. Spikiness is always better than coherence.** \nFirst, 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 $$\n\\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\n\\mu(Q)^2 d.\n$$\nSo bounded incoherence always implies bounded spikiness. Furthermore, note that the CUR method is not crucial for our improvement in the scaling with the incoherence constant. It is active sampling (choosing which rows and columns to sample more) that brings this improvement. However, it is unclear how to leverage active sampling for other methods besides CUR, which is why we employ it in our algorithm.\n\n**C. Comparison with literature on low-rank $Q$-learning.** \nWe are thankful again for raising this question. We include a tabular comparison with past works in Section C of our global rebuttal. \n\n**D. About the singular value threshold $\\beta$.** \nWe reassure the reviewer that we included the definition of $\\beta$ in Appendix B.4 (see eq. (10) line 639) only due to space constraints in the main paper. It is clearly stated in Proposition 1 where the definition of the threshold $\\beta$ can be found. For the sake of clarity, we will introduce $\\beta$ in the main text in the updated version of our paper.\n\nNext, we discuss why $\\beta$ does not depend on $d$ or $\\sigma_d$ explicitly. Note that, by definition, the threshold $\\beta$ depends on the number of samples $T$ and moreover, it decays with $\\sqrt{T}$. Thus, under assumptions on sample complexity (see (4) in Proposition 1), we ensure that $\\beta$ is smaller than $\\sigma_d(Q)$. Therefore, all relevant singular values (of which there are $d$) are preserved, and the rest (corresponding to the noise and having a norm smaller than $\\beta$) are removed. Please check Appendix B.4 for a more detailed proof. It is also important to note that we do not require knowledge of $\\sigma_d(Q)$ for our algorithm to work, but our guarantees are valid for a number of samples $T$ that is sufficiently large depending on $\\sigma_d(Q)$.\n\n\n**F. Extension to model-based RL.**\nWe refer the reviewer to [37] for entrywise guarantees for model-based RL. In that work, the recovery depends on the properties of the transition kernels and the reward matrix, and not directly on the properties of $Q$-matrix. The authors of [37] do not use a complex iterative scheme with two-phases as we have done in this paper, since in their setting, the matrices $P$ and $r$ they observe are those that should be recovered. Our setting is more challenging because we do not have direct observations of the $Q$-matrix, we employ active sampling, and we achieve coherence-free guarantees. \n\n**G. Extension to linear RL.**\nAlthough they are not directly comparable, we believe that linear RL requires a stronger assumption than the one we use in the paper. Specifically, in linear RL, the $Q$-function can be written as $Q(s,a) = \\phi(s,a)^\\top \\theta$ with $\\theta\\in\\mathbb{R}^d$ and a known nonlinear mapping $\\phi \\in \\Phi$. In our setting, $Q(s,a) = U_{s,:} \\Sigma W_{a,:}^\\top = \\mathrm{vec}(U^\\top e_s e_a^\\top W)^\\top \\mathrm{vec}(\\Sigma)$, and we do not assume knowledge of $U$ or $W$. Therefore, we believe our work is better aligned with low-rank MDPs where neither $\\theta$ nor $\\phi$ are known. Note that our setting is a special case of low-rank MDPs where the functions $\\phi$ have a specific structure (depending on the singular vectors $U,W$). Solving low-rank MDPs in full generality with computationally tractable algorithms remains an interesting open research question.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zFGUqSWiQq", "reviewer": "Reviewer_ff2R", "summary": "This paper proposes a leveraged matrix estimation method for low-rank policy evaluation and extends it to policy iteration as a model-free learning algorithm. The main idea is to separate the Q matrix estimation into two phases. The first step is to use half of the sample budget to estimate the leverage scores of the Q matrix. Based on the leverage scores, a skeleton of the value matrix is sampled. Then roughly one-fourth of the sample budget is used to sample the entries in the skeleton. The left sample budget is used to sample the entries outside the skeleton, and the final Q-value matrix is constructed by CUR decomposition with inverse leverage scores weighting. It's proved that the leveraged matrix estimation method relaxed eliminates the commonly used assumption of incoherence., and guarantees an entry-wise estimation error. The effectiveness of the proposed method is demonstrated via simulation in the Appendix.", "questions": "Is the low-rank assumption of the Q function under any deterministic policy very restrictive? How does that compare to related works?\n\nIt would be better to replace shadows in the figures (experiments) with error bars, as shallows overlay each other and make it hard to read.", "limitations": "The paper is more in a theoretical flavor and lacks real-world experiments.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written and easy to follow. The theoretical investigation comes with rigorous proof. By adopting leveraged matrix estimation, the authors can relax the incoherence assumption of the low-rank Q matrix, which serves as a major advantage of the proposed method.", "weaknesses": "It seems there is a lack of discussion about leveraged matrix estimation methods in matrix completion/low-rank matrix estimation literature. How does the proposed method perform when compared with other regularized policy evaluation approaches (for example, nuclear-norm/max-norm regularization)? It is crucial in assessing the significance and novelty of this work.\n\nIs that possible to include experiments in real-world datasets to enhance the significance of this work?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! Please find our responses below.\n\n**A. Comparison with other matrix estimation methods.**\nAs 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.\n\nAs 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:\n\n- **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. \n- **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.  \n\n\nWe refer reviewer to Section C of our general rebuttal for a more detailed comparison with other methods employing matrix completion for RL.\n\n**B. Real-world experiments.**\nWe 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.\n\n**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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thank you all for your efforts in reviewing our paper. We feel that some of the paper contributions might have been overlooked and we take the freedom to highlight them below.

**A. Our matrix completion scheme is novel.**

We want to emphasize that our matrix completion method is novel and not merely an application of existing results from matrix completion literature: our work is the first one to leverage entrywise bounds for estimating leverage scores and use them for adaptive sampling. Previously known two-phase matrix completion algorithms (such as that of [7]) only work in noiseless settings since estimating leverage scores has been challenging without appropriate entrywise (or $\Vert \cdot \Vert_{2\to\infty}$) guarantees. We use recent advancements in establishing entrywise guarantees to prove that we can **1)** successfully estimate leverage scores and **2)** use these estimates to sample in a manner that results in incoherence-free entrywise guarantees.

**B. Main contributions of our paper.**

Next, we want to emphasize three crucial points in which our algorithm is superior compared to previously known methods:

- Our proposed method enjoys **entrywise guarantees**. As discussed in [35], entrywise guarantees are crucial for RL algorithms. Handling error in Frobenius or spectral norm does not seem to be sufficient for studying RL algorithms (see section F.2 in [35]).

- **No explicit dependence on incoherence**. As shown in the table below, we remove explicit dependence on incoherence in sample complexity bounds. In [34], sample complexities scale with the incoherence constant $\mu$ roughly as $\mu^6$, but by decoupling the effect of incoherence from the effect of spikiness (corresponding to terms with $\sigma_d(Q)$), their sample complexity scales as $\mu^2 \alpha^2$ (note that spikiness constant $\alpha$ satisfies $\alpha \leq \mu^2 d$). In other words, our algorithm is better by a factor of $\mu^2$ than algorithms based on uniform sampling (studied in [34]), and requires the same sample complexity as the algorithm of [35], which has prior knowledge of anchor states.   

- Our proposed method requires **milder assumptions**. Specifically, we make two significant improvements in reducing the set of assumptions: 
  - we do not require prior knowledge of the most informative states (anchor states) as in [35]. Such knowledge greatly simplifies the problem, essentially reducing it to estimating the part of the matrix corresponding to the anchor states only. We believe this assumption is too strong for real-world applications, and we devise a way to learn such states without any prior knowledge.
  - our low rank assumption ($Q^\pi$ low rank for every deterministic policy $\pi$) is a relaxation of the previous assumption in [34] ($r$ and $P^\pi$ are low rank for any deterministic $\pi$). We achieve this by applying policy iteration-based algorithm instead of previously reported algorithms based on value iteration. We refer reviewers to Section 3.3 in the paper, where we explain in detail the benefits of using PI-based methods.

**C. Comparison with other methods**

Below, we provide a brief tabular overview of the most relevant algorithms, their performance and assumptions. For the sake of brevity, we omit writing the factors $\kappa,d$ and use the abbreviations NNM: nuclear norm minimization and MC: matrix completion.

|         Method        | Error guarantees |     Sampling model    |       Assumption      |         Sample complexity         |
|:---------------------:|:----------------:|:---------------------:|:---------------------:|:---------------------------------:|
|          Ours         |     entrywise    |        adaptive       |   bounded spikiness   |    $\alpha^2 (S+A)/\epsilon^2 $   |
|    Algorithm 1 [35]   |     entrywise    | apriori fixed anchors | anchors apriori known |    $\alpha^2 (S+A)/\epsilon^2$    |
|  LR-EVI (Thm 9 [34])  |     entrywise    |     unif. anchors     |      incoherence      | $\mu^2 \alpha^2 (S+A)/\epsilon^2$ |
| NNM [9] (Thm 21 [34]) |     entrywise    |     unif. anchors     |      incoherence      | $\mu^2 \alpha^2 (S+A)/\epsilon^2$ |
|    Two-phase MC [7]   |  exact recovery  |        adaptive       |       noiseless       |           not applicable          |

We also note that a different type of low-rank structure has recently received significant attention. Namely that $Q$-function can be written as $Q(s,a) = \phi(s,a)^\top \theta$ for an unknown vector $\theta \in \mathbb{R}^d$ and an unknown feature mapping $\phi$ belonging to some function class $\Phi$. These methods are not directly comparable to those presented in the table above and usually do not utilize matrix completion.

Meta-review: The paper provides a method for RL when the policy reward matrices are assumed to be low rank. While similar setups have been considered before, the paper particularly focuses on replacing the assumption of incoherence or known anchors with bounded spikiness. As the authors argued in the rebuttal, spikiness is a weaker assumption. The main component of their method is a matrix completion algorithm that is based on estimating leverage scores. I believe this component by itself is a nice contribution and imo in fact the main point of the paper. Important to note that guarantee required by RL application is entrywise recovery guarantees and not spectral/Frobenius norm guarantees which have been established for the spikiness assumption. 

There are a few weaknesses in the presentation of the paper that need to be addressed which put this paper right on the borderline. There are many clarifications made by the authors in the rebuttal including the understanding of the spikiness considition and comparison with incoherence as well as a clean table comparing their methods to other approaches. These are both extremely important to include in the revision. In fact the entire clarifications in their general rebuttal needs to be included in the paper in my opinion. 

Overall this is a borderline paper with interesting results and a presentation that can be signifcantly improved. I am voting for acceptance wuth the caveat that my set is very competitive and the presentation shortcomings put this paper on the borderline.
Decision: Accept (poster)