Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning
Authors: Stefan Stojanovic
Yassir Jedra
Alexandre Proutiere
Venue: NeurIPS 2023 poster (2023)
Keywords: Low-rank matrix estimation; low rank bandits; low rank MDP; spectral methods
TL;DR: We investigate simple spectral methods towards the entry-wise estimation of low-rank matrices arising in reinforcement learning.

Abstract: We study matrix estimation problems arising in reinforcement learning with low-rank structure. In low-rank bandits, the matrix to be recovered specifies the expected arm rewards, and for low-rank Markov Decision Processes (MDPs), it characterizes the transition kernel of the MDP. In both cases, each entry of the matrix carries important information, and we seek estimation methods with low entry-wise prediction error. Importantly, these methods further need to accommodate for inherent correlations in the available data (e.g. for MDPs, the data consists of system trajectories). We investigate the performance of  simple spectral-based matrix estimation approaches: we show that they efficiently recover the singular subspaces of the matrix and exhibit nearly-minimal entry-wise prediction error. These new results on low-rank matrix estimation make it possible to devise reinforcement learning algorithms that fully exploit the underlying low-rank structure. We provide two examples of such algorithms: a regret minimization algorithm for low-rank bandit problems, and a best policy identification algorithm for low-rank MDPs. Both algorithms yield state-of-the-art performance guarantees.

Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning
Stefan Stojanovic
Yassir Jedra EECS KTH, Stockholm, Sweden jedra@kth.se
EECS
KTH, Stockholm. Sweden stesto@kth.se
Alexandre Proutiere EECS
KTH, Stockholm, Sweden alepro@kth.se
Abstract
We study matrix estimation problems arising reinforcement learning (RL) with low-rank structure. In low-rank bandits, the matrix to be recovered specifies the expected arm rewards, and for low-rank Markov Decision Processes (MDPs), it may for example characterize the transition kernel of the MDP. In both cases, each entry of the matrix carries important information, and we seek estimation methods with low entry-wise error. Importantly, these methods further need to accommodate for inherent correlations in the available data (e.g. for MDPs, the data consists of system trajectories). We investigate the performance of simple spectral-based matrix estimation approaches: we show that they efficiently recover the singular subspaces of the matrix and exhibit results on low low-rank matrix estimation make it possible to devise reinforcement learning algorithms that fully exploit the underlying low-rank structure. We provide two examples such algorithms: a regret minimization algorithm for low-rank bandit problems, and a best policy identification algorithm for reward-free free RL in low-rank MDPs. Both algorithms yield state-of-the-an performance guarantees.
entry-wiss error. These new
Introduction
Learning succinct representations the reward function or of the system state dynamics in bandit and RL problems is empirically known to significantly accelerate the search for efficient policies [38, 55, 13]. also comes with interesting theoretical challenges. The design of algorithms learning and leveraging such representations and with provable performance guarantees has attracted considerable attention recently, but remains largely open. In particular, significant efforts have been made towards such design when the representation relies a low-rank structure. In bandits, assuming such structure means that the arm-to-reward function can be characterized by low-rank matrix [37, 32, 27]. In MDPs, it implies that the reward function, the Q-function the transition kernels represented by low-rank matrices [56, 4, 46, 60, 49]. In turn, the performance algorithms exploiting low-rank structures mainly determined by the accuracy with which we are able to estimate these matrices.
In this paper, study matrix estimation problems arising in low-rank bandit and RL problems. Two major challenges are associated with these problems. (i) The individual entries the matrix carry important operational meanings (e.g. in bandits, entry could correspond the average reward of an arm), and we seek estimation methods with low entry-wise error. Such requirement calls for
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

fine-gran tine-grained analysis, typically much more involved than that needed to only upper bound the spectral or Frobenius norm of the estimation error [22, 21, 12, 2, 54, 15. 53, 47]. (ii) Our estimation methods should further accommodate for inherent correlations in the available data (e.g.. in MDPs, we have access to system trajectories, and the data hence Markovian). We show that, essentially, spectral methods successfully deal with these challenges.
Contributions. 1) We introduce three matrix estimation problems. The first arises in low-rank bandits. The second corresponds to scenarios in RL where the learner wishes to estimate the (low- rank) transition kernel of a Markov chain and to this aim, has access to a generative model. The last problem is similar but assumes that the learner has access to system trajectories only, a setting referred to as the forward model in the RL literature. For all problems, we establish strong performance guarantees for simple spectral-base based estimation approaches: these efficiently recover the singular subspaces of the matrix and exhibit nearly-minimal entry-wise error. To prove these results, we develop and combine involved leave-one-out arguments and Poisson approximation techniques (to handle the correlations in the data).
2) We apply the results obtained for our first matrix estimation problem to devise an efficient regret-minimization algorithm for low-rank bandits. We prove that the algorithm enjoys finite-time performance guarantees, with a regret at most roughly scaling as (m + n) log (T)
where (m, n) are the reward matrix dimensions, T is the time horizon, A is the average of the reward gaps between the best arm and all other arms, and min is the minimum of these gaps.
3) Finally, we present an algorithm for best policy identification in low-rank MDPs in the reward- free setting. The results obtained for the second and last matrix estimation problems imply that our algorithm learns an c-optimal policy for any reward function using only a number of samples scaling as (nn//²² up to logarithmic factors, where and A denote the number of states and actions, respectively. This sample complexity is mini-max optimal [28]. and illustrates the gain achieved by leveraging the low-rank structure (without this structure, the sample complexity would be 2nn2 (2(n2//²2).
Notation. For any matrix A E R_=x, Ai,: (resp. A..j) denotes its i-th row (resp. its j-th column), Amin = min A,, and Amax = (i,( Arj. We consider the following norms for matrices: ||A||| denotes the spectral norm, ||A||1-xc = max ||A,,:II1, ||Al||=+>0 = [a |1:1,, and ) the matrix sign function of A (see Definition 4.1 in [14]). O"xr denotes the set of (r x r) real orthogonal matrices. For any finite set S, let P(S) be the set of distributions over S. The notation a(n, m, T) < b(n, m. m, (resp. a(n, m. T) = (b(n, m. T))) means that there exists a universal constant C > 0 (resp. c, C 0) such that a(n, m, T) < Cb(n, m, T) (resp. cb(n, m, T) < a(n, m. T) < Cb(n, m, T)) for all n, m, T. Finally, we use a/b = min(a, b) and avb = -max b).
finally ||A| = max(i |A, If the SVD of A is UEVT, we denote by sgn(() = UVT
2 Models and Objectives
Let M E guxx be unknown rank matrix that we wish to estimate from T' noisy observations of its entries. We consider matrices arising in two types of learning problems with low-rank structure, namely low-rank bandits and RL. The SVD of M is UEVT where the matrices U E Rm and V E RRa contain the left and right singular vectors of M, respectively, and Σ = We assume without loss of generality that the singular values have been ordered, i.e., σ1 The accuracy of our estimate M of M will be assessed using the following criteria:
dr.
(i) Singular subspace recovery. Let the SVD of M be UΣVT. To understand how well the singular subspaces of M are recovered, we will upper bound minoeorx IIU 00l|2- and minogorx IIV - -V (the mingeorx~ problem corresponds to the orthogonal Procrustes problem and its solution aligns Ö and U as closely as possible, see Remark 4.1 in [14)).
(ii) Matrix estimation. To assess the accuracy of M, we will upper bound the row-wise error M M M|]1-000 or [M - M M as well as the entry-wise error || MM/ Ml (the spectral
error || M M is easier deal with and is presented in appendix only).

---

We introduce two classical quantities characterizing the heterogeneity and incoherence of the matrix M [11, 48]. Let k 01/0r, and let μ(U) = Vm/rllulla>> (resp. v²V) = /M/r/ denote the row-incoherence (resp. column-incoherencee) parameter of M. Let = max (u(U), p(V)). Next, we specify the matrices M of interest in low-rank bandits and RL, and the way the data used for their estimation is generated.
Model Reward matrices low-rank bandits. For bandit problems, M corresponds to the average rewards of various arms. To estimate M, the learner has access to data sequentially generated as follows. In each round t = 1,..., T, an arm (ee) E [m]] x [m]] is randomly selected (say uniformly at random for simplicity) and the learner observes M. Êt, unbiased sample of the corresponding entry of M. (5t) is a sequence of zero-mean and bounded random variables.
Specifically, we assume that for all / 2 1, [6el S [|M || no a.s., for some constant 6₁ >> 0.
Model II: Transition matrices in low-rank MDPs. In low-rank MDPs, we encounter Markov chains whose transition matrices have low rank r (refer to Section 5 for details). Let P R be such a transition matrix. We assume that the corresponding Markov chain is irreducible with stationary distribution v. The objective is to estimate from the data consisting of samples of transitions of the chain. More precisely, from the data, we will estimate the long-term frequency matrix M = diag(u) (My is the limiting proportion of transitions from state to state j as trajectory grows large). Observe that M is of rank r, and that Pt.: = M Mi, To estimate M, the learner has access to the data (xI,.... .r) ) E [n]] generated according to one of the following two models.
(a) In the generative model, for any E [7], if is odd, xı is selected random according to some distribution Vo, and 2441 is sampled from Pa..:
(b) In the forward model, the learner has access to a trajectory (II,..., of length T of the Markov chain, where xj vo and for any 2 1,-11 ~ Pz..
3 Matrix Estimation via Spectral Decomposition
In the three models (Models I, II(a) and II(b)), we first construct a matrix M directly from the data, and from there, we build estimate M, typically obtained via spectral decomposition, i.e., by taking the best rank-r approximation of M. the remaining of this section, let UEV" denote the SVD of M. Next, we describe in more details how M is constructed in the three models, and analyze the corresponding estimation error.
3.1 Reward matrices
For Model I, for 1 = I,...,T, we define M, = ((Mis + E. ((.)((())( (s and M
Σts Mr. Let M denote the best rank-r approximation of M. Theorem 1. Let 8 > O. We introduce:
YUTE B = V T
(Vin m) log
e(nn (m) 3/2 + log
(e(n+ + m)T
8
8
Assume that T 2 2 + m) log (e(m + n)) for some universal constant c >> 0. Then there exists universal constant C > O such that the following inequalities hold with probability at least 8:
TVV22)ll- S SC (1²x213/22 B,
(1)
max (IIU
mnnn A m)
JM - -M11222000 I G cluunn
k223112) (2/12)
(it)
|| Io
VmA
(tii
M - 1 SC (221/2 x2,1/2 + + k/ 3/2
m +
1
|oo
Vmn
(n A m))
3

---

Corollary 2. (Homogeneous reward matrix) When m = (()), k= (1), (1), || = @(1), r (1). we say that the reward matrix M is homogeneous. In this case, for any when 2 a(n + mmmmlog log (e(m + n)T/8) /8) for some universal constant c. > 0, we have with probability at
least 1 8:
(n + m)T (m1 (n+m)T
max [IU - (112-,00 1I -VV V)
VVVVVVVVVlla-a 2
log
3/2
VT
8
(n + m)
[n + m)]
|M M112-100 S
log
3/2
VT
(n + m)
(n + m){
|M - - S
log 3/2
V
T
8
For homogeneous reward matrix, [ (m//mm) and || @ and hence, from
the above corollary, we obtain estimates whose relative errors (e.g., ||M - M / /|loo/| || scale at most as /m/T T up to the logarithmic factor.
We may also compare the results of the above corollary to those of Theorem 4.4 presented in [14]. There, the data consists for each pair (i,j) of a noisy observation M., + Eij- The E,j are independent across (i.j). This model is simpler than ours and does not include any correlation in the data. But it roughly corresponds to the case where = nm in our Model I. Despite having deal with correlations, we obtain similar results as those of Theorem 4.4: for example, ||M
M 2 v1/(n + m) (up to logarithmic terms) with high probability.
3.2 Transition matrices under the generative model
For Model II()), the matrix M records the empirical frequencies of the transitions: for any pair of
states (i,5), Mc,- = [T/2] Σ T/2) ((00)1122)) M is the best rank-r approximation of M
and the estimate of the transition matrix P is obtained normalizing the rows of M: for all i E [m].
(M, //4. /lIM,,))l if || [I 1114 if (M,M.)) O.
P...
In,
where (-)+ is the function applying max(0,-) -) component-wise and 1,, is the n-dimensional vector of ones. The next theorem is simplified version and consequence of more general and tighter theorem presented in App. B.2. To simplify the presentation of our results, we define
log( myx" (1
g(M,T,8) = n log( T
max p k
log(1+ )pp))
Theorem 3. Let > O. Introduce
pn (rllM (T) log log ( TO)). Assume that we have
(Vo)min mm) (Vo); > O. If (a) 2 clog2 2lTg/(TT//2/ and (b) T 2 cg(M, T, 5) for some universal constans c > O, then there exists a universal constant C > O such that the following inequalities hold with probability least 1-d:
(1)
max {oIU - U112-20000 DV(VVVV) S
B,
M||
M - -1112 - CCRB, | -P S C Ky B. (Mo)
(ii)
M - Ml S <0 2
(iid)
B.
nn
B
| + (1
xB
kp2r
(iv)
p P P 5
VnR
(Vo)min
(Mu)anin
vn
|M
vn
where (iv) holds if in addition T > cn|| [ ||x (2o) ru² 2x²xx log(nVTT/))
Note that in theorem, the condition (a) on n has been introduced just to simplify the expression of (refer to App. B.2 for full statement of the theorem without this condition).

---

r- Corollary 4. (Homogeneous transition matrix) When M r= (1), Mmax = (iMmin), we say that the frequency matrix M is homogeneous. If 2 en lngognn [n]] for some universal constant > 0, then we have with probability at least 1 min -
H
log(n
max -
IV VVVT2))l2-
S
T
1
log(nI))
1 log(nI)
| M M112-000-
|| -M x
1
T
1
ri
nlog(nn())
[lg(n'T)
|P 2
|| 1P-Plla0 S
nf
For homogeneous frequency matrix, |1 (L//vR), | = ((1/nvn), || ((L/n²), || = 1, || = (1/n). Thus for all these metrics, our estimates achieve a relative error scaling at most as /n/T up to the logarithmic factor.
3.3 Transition matrices under the forward model
For Model Il(b), we first split the data into subsets of transitions: for k 1.... the k-th subset is ([r2, FR-1): (#++7, #*+1+7), (F Fh 11---TT-- separating two transitions in the same subset, we break the inherent correlations in the data if is large enough. Now we let (a) be the matrix recording the empirical frequencies of the transitions
where T, [T/T]: By
in the k-th subset: M = 1 T. Σi= 1 [( (( )+d)))))))))))))))))) for any pair of states (i,j). Let (R)
be the best r-rank approximation of (4)) As in (1), we define the corresponding P(R) Finally we may aggregate these estimates M = 1 Ex= (A) and P = 7 Ex=, p(k), We present below the performance analysis for the estimates coming from single subset; the analysis of the aggregate estimates easily follows.
For any O, we define the e-mixing time of the Markov chain with transition matrix P as T(E) min(t 2 1: maxi PI I1 S {) and its mixing time as r" = 71144) The next theorem simplified version and consequence of more general and tighter theorem presented in App. B.3. To simplify the presentation, we define:
((M.T.8) = nT* log( TVT log(T ( max k log" ( ("xTT) )1 (ac.T- 1 51)
11+ 7. x
Theorem 5. Let 8 > O. Assume that Mmin = minke[m) for some universal constants 02 > ci 2 Introduce:
> 0 and that T T/(T" log(To,,.g)ooo. ())))))))) E cal
rT* |
nVTT
T
B = ung
log
log
T
Vinin
(a) n. 2 CT log 3/2 (nT3/2 (8) log" 1/2 (Tu-t)
miin and (b) T 2 ch( T, for some universal constant
>> then there exists universal constant C >> O such that the following inequalities hold with probability at least 5:
kpL2T B.
(1)
max ( U)) -IV-VV V(V V V)
)
S
SC
n|llM] |loc
| -1-MM -111 S CCBB || 1P-Plli-so S CKVLIL
(ii)
Vmunn
| -l S m (iit)
B,
Vn
B
M M
+ (1+
kB
(iv)
|1 C
Vnk
Vniin
Unnin
vn |
/n
where (iv) holds if in addition T cn||M||ll
|M min Trp= T xd log(n T/0) Log(Tu=l)
Note that our guarantees hold when 7 roughly scales as T* log(T Hence to select T, one would need an idea of the latter quantity. It can be estimated typically using T' ymun samples [61] (which
5

---

is small when compared to the constraint T 2 ch(M,T, as soon as Vmin = (2(1nn)). Further observe that in the theorem, the condition (a) can be removed (refer to App. B.3 for full statement of the theorem without this condition).
Corollary 6. (Homogeneons transition matrices) Assume that M is homogeneous (as defined in Corollary 4), Let log( IfT' 2 en log" (n'l") for some universal constant e > 0, then we have with probability at least 1 min(n -,n=,,, T,
max {IU -Ū U)122-10 VVVVVVVV)le &
1 VT log(nT),
|M -M112-00 S
log(n7), || - M1 S nvnT log(n?)
nvT
|| Pll 100 S T log(nT), ||- -1 S log(nT).
As for the generative model, for homogeneous frequency matrix, our estimates achieve a relative error scaling at most as vn/T up to the logarithmic factor for all metrics. Note that up to a logarithmic factor, the upper bound for ||P Pll Pll (and similarly for M) matches the minimax lower bound derived in [63].
3.4 Elements of the proofs
The proofs of the three above theorems share similar arguments. We only describe elements of the proof of Theorem 5, corresponding to the most challenging model. The most difficult result concerns the singular subspace recovery (the upper bounds (i) in our theorems), and it can be decomposed into the following three steps. The first two steps meant to deal with the Markovian nature of the data. The third step consists in applying a leave-one-out analysis to recover the singular subspaces.
Multinomial approximation of Markovian data We treat the matrix M() arising from one subset of data, and for simplicity, we remove the superscript (k), i.e., M ( Note that T.M is matrix recording the numbers of transitions observed in the data for any pair of states: denote by Ni, this number for (i. We approximate the joint distribution of N = (NN) by multinomial distribution with n² components and parameter T.M;, for component (i,j). Denote by Z = =Zz,,) )(.) the corresponding multinomial random variable. Using the mixing property of the Markov chain and the choice of T, we establish (see Lemma 21 in App. C) that for any subset Z of
Step 1:
{a NT² EEi,)
Zz.j T.}. we have P[N- E Z S 3 Z].
Step 2: Towards Poisson random matrices with independent entries. The random matrix Z does not have independent entries. Independence is however a requirement if we wish to apply the leave- one-out argument. Consider the random matrix Y whose entries are independent Poisson random variables with mean T, M,., for the (i,j)-th entry. We establish the following connection between the distribution of Z and that of Y: for any Z C No², we have PIZ E 2 < eVT,P(Y e 2]. Refer to Lemma 22 in App. C for details.
Step 3: The leave-one-out argument for Poisson matrices. Combining the two first steps provides a connection between the observation matrix M and Poisson matrix Y with independent entries. This allows us apply a leave-one-out analysis to M if it had independent entries (replacing M by Y). The analysis starts by applying the standard dilation trick (see Section 4. 10 in [14]) so as to make M symmetric. Then, we can decompose the error | - (Ū U) (see Lemma 32 in App. E) into several terms. The most challenging of these terms [[(M MU Ō U)) maxieln] [M (U - ÜŪ U))ll2 because of inherent dependence between M M and U Ú-Ū (U). The leave-one enve--neeouut out analysis allows us to decouple this statistical dependency. It consists in exploiting the row and column independence of matrix M to approximate [|(Mr MU
ūūū U)) by [I(M, (U 8 ((Ō ())T))) U)]l2 where ( is the matrix of eigenvectors of matrix MO obtained by zeroing the I-th row and column of M. By construction, (M.: M,.) and
U - ( are independent, which simplifies the analysis. The proof is completed by

---

further uppropriate decomposition of this term, combined with concentration inequalities for random Poisson matrices (see App. D).
4 Regret Minimization in Low-Rank Bandits
Consider a low-rank bandit problem with homogeneous rank-r reward matrix M. We wish to devise an algorithm x with low regret. a selects in round an entry (X7 (F based on previous observations, and receives
feedback the noisy reward Mer .f + &.. The regret up round T T E Mi where (i", (?" is an optimal entry. One could (ETC) algorithm, where in the first phase entries sampled uniformly at random, and where in a second phase, the algorithm always selects the highest entry of M built using the samples gathered in the first phase and obtained by spectral decomposition. When the length of the first phase is 72/3(n (n + m) the ETC algorithm would yield regret upper bounded by (( + m) for T = (( + m) log" (n + m)).
defined by R (T) = TM : E think of simple
Misiore-Then-oomeeee
To get better regret guarantees, Elimination), an algorithm meant to identify the best entry as quickly as possible with a preseribed level of certainty. After the SME-AE has returned the estimated best entry, commit and play this entry for the remaining rounds. The pseudo-code of SME-AE is presented in Algorithm 1. The algorithm runs in epochs: in epoch it samples T7 entries uniformly at random among all entries (in Ty, the constant C' just depends on upper bounds of the parameters J4, K, and || [|M]] so refer to App. G); from these samples, matrix ( is estimated and Ar, the set of candidate arms, is pruned. The pruning procedure based on the estimated gaps: A M M where M max.,j M
present SME-AE (Successive Matrix Estimation and Arm
Algorithm 1: Succesive Matrix Estimation and Arm Elimination (SME-AE)
Input: Arms [m] [n)] confidence level
f 1
A1
[m] [n]:
while
[Ag] > 1-10 do
82 = 8/2;
T = c ( (m + n) log" (220+1(m + m)/68)
Sample uniformly at random T/ entries from A1: (Mau + Ee):=I....TTT" Estimate M9 via spectral decomposition described in Section 3.1 Aet1 (1,5) Ae 3 2--((+2) }: = 1;
end
Output: Recommend the remaining pair (f+: in Ae-
The following theorem characterizes the performance of SME-AE and the resulting regret. To simplify the notation, we introduce the gaps: for any entry (i, Ar, = (Mr M.,). ). Amin = 2. Ai.j, Amax = max( Ai.j. and = E(E)) (i-)) A We define the function
(n2 m, 8) c(m++n) logie/Amin) log (e(m+tn)))og lowee//looo////ao (mmi)) for some universal constant e >>> 0.
A
Amind
Theorem 7. (Best entry identification) For any 5 E (0, 1), SME-AE(6) stops at time 7 and recommends arm (Rr.3r) with the guarantee P((i,,jr) = (it,j"), I snn, m, 6)) Z 1- Moreover, for any 2 1 and > O, the sample complexity of SME-AE(L/T") satisfies E[T AT] < whnn, T +Ti-a (Regret) Let T 2 1. Consider the algorithm n that first runs SME-AE( T22 and then commits to its output (+r after т. We have: R (T) < A (v,n, m, T 7-2 + 1) + Agos.
The proof of Theorem 7 is given in App. G. Note that the regret upper bounds hold for any time horizon T > 1, and that it scales as O((m + n) ( ? (up to logarithmic factors in vn, and 1/Amin). The cubic dependence in log is an artifact of our proof techniques. More precisely, due to the Poisson approximation used obtain entry-wise guarantees. Importantly, for any time horizon, the regret upper bound only depends on (m n) rather than mn (the number
7

---

of arms / entries), and hence, the low-rank structure is efficiently exploited. If we further restrict our attention to problems with gap ratio m / upper bounded by Ç, our regret upper bound becomes O + n) log (T)) Amin), / and can be transformed into the minimax gap-independent upper bound O((((m + x))) log (T)), see App. G. Finally note that Q(((m + n)²) is an obvious minimax regret lower bound for our low-rank bandit problem.
very similar low-rank bandit problem has been investigated in [7]. There, under similar assumptions (see Assumption 1 and Definition 1). the authors devise an algorithm with both gap-dependent and gap-independent regret guarantees. The latter are difficult to compare with ours. Their guarantees exhibit a better dependence in I"' and Amin. but worse in the matrix dimensions n and m. Indeed in our model, b* in [7] corresponds to M and scales as /n. As a consequence, the upper bounds in [7] have dependence in n and m scaling as vn(n + m) in the worst case for gap-dependent guarantees and even nm (through the constant C2 in [7]) for uup-indeenndent guarantees.
5 Representation Learning in Low-Rank MDPs
The results derived for Models lI(a) and lIbb) are instrumental towards representation learning and hence towards model-based or reward-free RL in low-rank MDPs. In this section, we provide an example of application of these results, and mention other examples in Section 7. A low-rank MDP defined by (S, A. [P")assA R. 7) where S, A denote state and action spaces of cardinalities n and A, respectively. pa denotes the rank-r transition matrix when taking action a, R is the reward function, and 7 the discount factor. We assume that all rewards are in [0, 1]. The value function Do of policy π S + A is defined as VĀ E| t=1 7- R(x,, (e(a;) 2)a= = x]] where x; is the state visited under æ in round t. We denote by x (R) an optimal policy (i.e., with the highest value function).
Reward-free RL. In the reward-free RL setting (see e.g. [36, 30, 66]), the learner does not receive any reward signal during the exploration process. The latter is only used to construct estimates [P") of (P" The reward function R is revealed at the end, and the learner may compute A (R) optimal policy for the MDP (S, AA
(aa) (r))ae. J.E R, 7). The performance of this model-based -V V ||xo- In tabular MDP, to identify an e-optimal policy for all reward functions, i.e., ensure that r S e, we believe that the number of samples that have to be collected should be ( 2² (the exact degree of the polynomial in 1/(1 7/) has to be determined). This conjecture is based on the sample complexity lower bounds derived for reward-free RL in episodic tabular MDP [30, 43]. Now for low-rank MDPs, the equivalent lower bound would be [(poly( [ 2 [28] (this minimax lower bound is valid for Block MDPs, a particular case of low-rank MDPs).
approach is often assessed through r = supæ I (R)
n.
Leveraging our low-rank matrix estimation guarantees, we propose algorithm matching the aforementioned sample complexity lower bound (up to logarithmic factors) at least when the frequency matrices (M") J are homogeneous. The algorithm consists of two phases: (1) in the model estimation phase, it collects A trajectories, each of length T/A, corresponding to the Markov chains with transition matrices (P')aEA, From this data, it uses the spectral decomposition method described $3 to build estimates {P*)aEA (2) In the planning phase, based on the reward function R, it computes the best policy # (R) for the MDP (S,A, A, summarizes the performance of this algorithm. To simplify the presentation, we only provide the performance guarantees of the algorithm for homogeneous transition matrices (guarantees for more general matrices can be derived plugging in the results from Theorem 5).
R, 7). The following theorem
Theorem 8. Assume that for any E A, Ma is homogeneous (as defined in Corollary 4). If T Z enA log2 (nAT) for some universal constant >> O, then we have with probability at least 1 min(n 12 2,, 11: r supR || V. (R) (((R)
0o S -
DA log(nAT)).
Theorem 8 is direct consequence of Corollary and of the fact that for any reward function R: 2y
Pa Pa 111 App. A. The theorem implies that if we wish to guarantee r < e, we just need to collect O nd (< samples up to logarithmic factor.
V (R) ( || [I-7)= A
8

---

This sample complexity is minimax optimal in n, A, and in view of the lower bound presented in [28].
6 Related Work
Low-rank matrix estimation. Until recently, the main efforts on low-rank matrix recovery were focused on guarantees w.r.t. the spectral or Frobenius norms, see e.g. [19] and references therein. The first matrix estimation and subspace recovery guarantees in -2-200 and lxx. were established in [22], [21] via a more involved perturbation analysis than the classical Davis-Kahan bound. An alternative approach based on a leave-one-out analysis was proposed in [2], and further refined in [10, 12, 17], see [14] for survey. Some work have also adapted the techniques beyond the independent noise assumption [39, 1, 5J, but for very specific structural dependence. We deal with a stronger dependence, and in particular with Markovian data (an important scenario in RL).
The estimation of low-rank transition matrices of Markov chains has been studied in [63, 9] using spectral methods and in [40, 67] using maximum-likelihood approaches. [63] does not conduct any fine-grained subspace recovery analysis (such as the leave-one-out), and hence the results pertaining to the || || -o -guarantees are questionable; refer to App. H for detailed justification. All these papers do not present entry-wise guarantees.
It is worth mentioning that there exist other methods for matrix estimation that do not rely on spectral decompositions like ours, yet enjoy entry-wise matrix estimation guarantees [51, 3. 50]. However, these methods require different assumptions than ours that may be too strong for our purposes, notably having access to the so-called anchor rows and columns. Moreover, we do not know if these methods also lead to guarantees for subspace recovery in the norm || 1|2-000. nor how to extend those results to settings with dependent noise.
Low-rank bandits. Low-rank structure in bandits has received a lot of attention recently [35, 37, 32, 57, 41, 7, 34, 27]. Different set-ups have been proposed (refer to App. H for a detailed exposition, in particular, we discuss how the settings proposed in [32, 7] are equivalent), and regret guarantees in an instance dependent and minimax sense have been both established.
Typically minimax regret guarantees in bandits scale as VT, but the scaling in dimension may defer when dealing with a low rank structure [32, 34, 7]. In [32], the authors also leverage spectral methods. They reduce the problem to a linear bandit of dimension nm but where only roughly n + m dimensions are relevant. This entails that regret lower bound of order (n + m is inevitable. Actually, in their reduction to linear bandits, they only use a subspace recovery in Frobenius norm, which perhaps explains the scaling (n + 3/22 in their regret guarantees. It is worth noting that in [34], the authors manage to improve upon the work [32] and obtain a scaling order (m + n)) in the regret. Our algorithm leverages entry-wise guarantees which rely on a stronger subspace recovery guarantee. This allows us to obtain scaling /n + in the regret. The work of [27] is yet another closely related work to ours. There, the authors propose an algorithm achieving a regret of order polylog(n + m for a contextual bandit problem with low rank structure. However, their result only holds for rank 1 and their observation setup is different than ours because in their setting, the learner observes m entries per round while ours the learner only observes one entry per round. In [7]. the authors matrix estimation with nuclear norm penalization estimate the matrix M. Their regret guarantees are already discussed in $4.
Some instance-dependent guarantees with logarithmic regret for low rank bandits have been established in [35, 37, 57]. However, these results suffer what may be qualified as serious limitations. Indeed, [35, 57] provide instance dependent regret guarantees but only consider low-rank bandits with rank 1, and the regret bounds of [35] are expressed in terms of the so-called column and row gaps (see their Theorem 1) which are distinct from the standard gap notions. [37] extend the results in [35] to rank r with the limitation that they require stronger assumptions than ours. Moreover, the computational complexity of their algorithm depends exponentially the rank r; they require search over spaces of size (m) and (*). Our proposed algorithm does not suffer from such limitations.
We wish to highlight that our entry-wise guarantees for matrix estimation are the key enabling tool that led us to the design and analysis of our proposed algorithm. In fact, the need for such guarantees arises naturally in the analysis of gap-dependent regret bounds (see Appendix G. Therefore, we

---

believe that such guarantees can pave the way towards better, faster, and efficient algorithms for bandits with low-rank structure.
Low-rank Reinforcement Learning. RL with low rank structure has been recently extensively studied but always in the function approximation framework [29, 18, 20, 44, 24, 65, 56, 4, 46, 59, 60, 49]. There, the transition probabilities can be written as oxx, a) uu(²) where the unknown feature functions o(x, a), p(x') R' belong some specific class F of functions. The major issue with algorithms proposed in this literature is that they rely on strong computational oracles (e.g.. ERM, MLE), see [33, 25, 64] for detailed discussions. In contrast, we do not assume that the transition matrices are constructed based on given restricted class of functions, and our algorithms do not rely on any oracle and are computationally efficient. In [51, 50], the authors also depart from the function approximation framework. There, they consider low rank structure different than ours. Their matrix estimation method enjoys an entry-wise guarantee, but requires identify subset of rows and columns spanning the range of the full matrix. Moreover, their results are only limited the generative models, which allows actually rely on independent data samples.
Conclusion and Perspectives
In this paper, we have established that spectral methods efficiently recover low-rank matrices even in correlated noise. We have investigated noise correlations that naturally arise in RL., and have managed prove that spectral methods yield nearly-minimal entry-wise estimation have been applied to design efficient algorithms in low-rank RL, problems and to analyze their performance. We believe that these results may find many more applications in low-rank RL. They can be applied (i) to reward-free RL in episodic MDPs (this setting is easier than that presented independent); (ii) scenarios corresponding offline RL [62]
Our results for low-rank matrix
in $5 since successive episodes where the data consists of single trajectory generated under given behavior policy (from this data, we can extract the transitions (z, a, x') where given action a is involved and apply the spectral method to learn Pa); (iii) to traditional RL where the reward function R has to be learnt (learning R is problem that lies in
sense between the inference problems in our Models I and II); (iv) to model-fres free--feeeeeee RL where we would directly learn the Q function as done in [52] under a generative model; (v) to low-rank RL problems with continuous state spaces (this can be done if the transition probabilities are smooth in the states, and by combining our methods to an appropriate discretization of the state space).
Acknowledgment
This research was supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.
10

---

References
[1] Emmanuel Abbe, Jianqing Fan, and Kaizheng Wang. An e theory of pea and spectral clustering. The Annals of Statistics, 50(4))2359 2022. (Cited on page 9.)
[2] 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. (Cited on pages 2, 9, and 34.)
[3] Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms, CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, pages 10-4, 2019. (Cited pages 9 and 18.)
[4] Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy. and Wen Sun. FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs. Advances Neural Information Processing Systems, volume 33, pages 20095-20100 Curran Associates, Inc., 2020. (Cited on pages and 10.)
[5] Joshua Agterberg, Zachary Lubberts, and Carey E Priebe. Entrywise estimation of singular vectors of low-rank matrices with heteroskedasticity and dependence. IEEE Transactions on Information Theory, 68(7):4618 46500, 2022. (Cited on page 9.)
[6] Afonso S Bandeira and Ramon Van Handel. Sharp nonasymptotic bounds on the norm of random matrices with independent entries. The Annals of Probability, 44(4):2479-2566, 2016. (Cited on page 31.)
[7] Mohsen Bayati, Junyu Cao, and Wanning Chen. Speed up the cold-start learning in two-sided bandits with many arms. arXiv preprint arXiv:2210.00340, 2022. (Cited on pages 1, 8, 9, and 50.)
[8] George Bennett. Probability inequalities for the sum of independent random variables. Journal of the American Statistical Association, 57(297):33-45, 1962. (Cited on page 26.)
[9] Shujun Bi, Zhen Yin, and Yihong Weng. A low-rank spectral method for learning markov models. Optimization Letters, 17(1):133-12, 2023. (Cited on page 9.)
[10] Tony Cai and Anru Zhang. Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics. The Annals of Statistics, 46(1):60-89, 2018. (Cited on page 9.)
[11] Emmanuel J Candès and Terence Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Transactions Information Theory, 56(5):2053-208) 2010. (Cited on
page 3.)
[12] Joshua Cape, Minh Tang, and Carey E Priebe. The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics. The Annals of Statistics, 47(5):2405- 2439, 2019. (Cited on pages 2, 9, 18, 35, and 43.)
[13] Yash Chandak, Shantanu Thakoor, Zhaohan Daniel Guo, Yunhao Tang, Remi Munos, Will Dabney, and Diana L Borsa. Representations and exploration for deep reinforcement learning using singular value decomposition. In Proc. of ICML. 2023. (Cited on page 1.)
[14] Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, et al. Spectral methods for data science: A statistical perspective. Foundations and Trends@ in Machine Learning, 14(5):566 806, 2021. (Cited on pages 2, 4, 6, 9, 34, 39, 40, 41, and 43.)
[15] 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 -121,, 2020. (Cited on page 2.)
[16] 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, 309-)3309--312,, 2020. (Cited on page 50.)
[17] Yuxin Chen, Jianqing Fan, Cong Ma, and Kaizheng Wang. Spectral method and regularized mle are both optimal for top-k ranking. Annals of statistics, 47(4):2204, 2019. (Cited on page 9.)
11

---

[18] 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. (Cited on page 10.)
[19] Mark A. Davenport and Justin K. Romberg. An overview of low-rank matrix recovery from incomplete observations. IEEE J. Sel. Top. Signal Process., 10(4):608 622, 2016. (Cited on page 9.)
[20] Simon Du, Akshay Krishnamurthy, Nan Jiang, Alckh Agarwal, Miroslav Dudik, and John Langford. Provably efficient RL with Rich Observations via Latent State Decoding. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1665-1674. PMLR, 09-15 Jun 2019. (Cited on page 10.)
[21] Justin Eldridge, Mikhail Belkin, and Yusu Wang. Unperturbed: spectral analysis beyond davis-kahan. In Algorithmic Learning Theory, pages 321-358. PMLR, 2018. (Cited on pages
and 9.)
[22] Jianqing Fan, Weichen Wang, and Yiqiao Zhong. An tor eigenvector perturbation bound and its application to robust covariance estimation. Journal of Machine Learning Research, 18(207):1-42, 2018. (Cited on pages 2 and 9.)
[23] Vivek Farias, Andrew A Li, and Tianyi Peng. Near-optimal entrywise anomaly detection for low-rank matrices with sub-exponential noise. In International Conference on Machine Learning, pages 3154-3163. PMLR, 2021. (Cited on page 34.)
[24] Dylan Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. Instance-Dependee Complexity of Contextual Bandits and Reinforcement Learning: Disagreement- Perspective. In Proceedings of Thirty Fourth Conference Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 2059-2059. PMLR, 15-19 Aug 2021. (Cited on page 10.)
[25] Noah Golowich, Ankur Moitra, and Dhruv Rohatgi. Learning in Observable POMDPs, without Computationally Intractable Oracles. In Advances Neural Information Processing Systems, volume 35. Curran Associates, Inc., 2022. (Cited on page 10.)
[26] Samuel B Hopkins, Tselil Schramm, Jonathan Shi, and David Steurer. Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors. In Proceedings of the forly-eighth annual ACM symposium on Theory of Computing, pages 178-191, 2016. (Cited on page 26.)
[27] Prateek Jain and Soumyabrata Pal. Online low rank matrix completion. In Proc. of ICLR, 2023. (Cited on pages 9, and 50.)
[28] 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. (Cited on pages 2, 8, and 9.)
[29] 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 on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1704-1713. PMLR, 06-11 Aug 2017. (Cited on page 10.)
[30] Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-Free Exploration for Reinforcement Learning. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 4879, PMLR, 13-18 Jul 2020. (Cited on page 8.)
[31] Kwang-Sung Jun, Rebecca Willett, Stephen Wright, and Robert Nowak. Bilinear bandits with low-rank structure. In International Conference on Machine Learning, pages 3163-3172. PMLR, 2019, (Cited page 50.)
12

---

[32] Kwang- Drran--unggaaa Jun, Rebecca Willett, Stephen J. Wright, and Robert D. Nowak. Bilinear bandits with low-rank structure. Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings Machine Learning, ICML. 2019, 9-15 June 2019, Long
of the 36th International Conference Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 3163 3172. PMLR, 2019. (Cited on pages 1 and 9.)
[33] Daniel Kane, Sihan Liu, Shachar Lovett, and Gaurav Mahajan. Computationallstatisiccaaa gap in reinforcement learning. Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 1282-13002 1302. PMLR, 02-05 Jul 2022.
(Cited on page 10.)
[34] Yue Kang, Cho-Jui Hsieh, and Thomas Chun Man Lee. Efficient frameworks for generalized low- rank matrix bandit problems. Advances in Neural Information Processing Systems, 35:19971- 19983, 2022. (Cited on pages 9 and 50.)
[35] Sumeet Katariya, Branislav Kveton, Csaba Szepesvari, Claire Vernade, and Zheng Wen. Stochastic Rank-1 Bandits. In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages
PMLR, 20-22 Apr 2017. (Cited on page 9.)
[36] Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive Reward-Free Exploration. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory, volume 132 of Proceedings of Machine Learning Research, pages 865-891. PMLR, 16-19 Mar 2021. (Cited page 8.)
[37] Branislav Kveton, Csaba Szepesvari, Anup Rao, Zheng Wen, Yasin Abbasi- Yadkori, and Muthukrishnan. Stochastic low-rank bandits, 2017. (Cited on pages and 9.)
[38] Michael Laskin, Aravind Srinivas, and Pieter Abbeel. CURL: Contrastive Unsupervised Representations 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. (Cited on page 1.)
[39] Lihua Lei. Unified f-- eigenspace perturbation theory for symmetric random matrices. arXiv preprint arXiv: 911999990779.. 2019. (Cited page
[40] Xudong Li, Mengdi Wang, and Anru Zhang, Estimation of markov chain via rank-constrained likelihood. International Conference on Machine Learning, pages 3033-3042. PMLR, 2018 (Cited on page 9.)
[41] Yangyi Lu, Amirhossein Meisami, and Ambuj Tewari. Low-rank generalized linear bandit problems. In Arindam Banerjee and Kenji Fukumizu, editors, The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pages 460 468. PMLR, 2021. (Cited on page 9.)
[42] Andrew D McRae and Mark A Davenport, Low-rank matrix completion and denoising under poisson noise. Information and Inference: A Journal of the IMA, 10(2):697-720, 2021. (Cited page 31.)
[43] Pierre Menard, Omar Darwiche Domingues, Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration in reinforcement learning. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 7599-7608. PMLR, 18-24 Jul 2021. (Cited on page 8.)
[44] Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic State Abstraction and Provably Efficient tich-Observation Reinforcement Learning. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 1961-6977 PMLR, 13-18 Jul 2020. (Cited on page 10.)
[45] Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017. (Cited on page 22.)
13

---

[46] Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free representation learning and exploration in low-rank mdps. To appear Journal of Machine Learning Research (JMIR), 2023. (Cited on pages and 10.)
[47] Sahand Negahban and Martin Wainwright. Restricted strong convexity and weighted matrix completion: Optimal bounds with noise. The Journal of Machine Learning Research, 13(1):1665-119) 2012. (Cited on page 2.)
[48] Benjamin Recht. A simpler approach to matrix completion. Journal of Machine Learning Research, 12(12), 2011. (Cited on page 3.)
[49] 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. (Cited on pages and 10.)
[50] Tyler Sam, Yudong Chen, and Christina Lee Yu. Overcoming the long horizon barrier for sample-efficiet reinforcement learning with latent low-rank structure. ACM SIGMETRICS Performance Evaluation Review, 50(4):41-43, 2023. (Cited on pages 9 and 10.)
[51] Devavrat Shah, Dogyoon Song, Zhi Xu, and Yuzhe Yang. Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation. In Advances in Neural Information Processing Systems, volume 33, pages 12092-12103. Curran Associates, Inc., 2020. (Cited on pages 9 and 10.)
[52] Devavrat Shah, Dogyoon Song, Zhi Xu, and Yuzhe Yang. Sample efficient reinforcement learning via low-rank matrix estimation. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS'20, 20) Curran Associates Inc., 2020. (Cited on page 10.)
[53] Ohad Shamir and Shai Shalev-Shwartz. Matrix completion with the trace norm: Learning, bounding, and transducing. The Journal of Machine Learning Research, 15(1):3401-342) 2014. (Cited on page 2.)
[54] Nathan Srebro and Adi Shraibman. Rank, trace-norm and max-norm. In International conference on computational learning theory, pages 545-560. Springer, 2005. (Cited on page 2.)
[55] 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 18-24. Jul 2021. (Cited on page 1.)
[56] 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 2898-2933. PMLR, 25-28 Jun 2019. (Cited pages and 10.)
[57] Cindy Trinh, Emilie Kaufimann, Claire Vernade, and Richard Combes. Solving bernoulli rank- one bandits with unimodal thompson sampling. In Aryeh Kontorovich and Gergely Neu, editors, Proceedings of the 31st International Conference on Algorithmic Learning Theory, volume 1 117 of Proceedings of Machine Learning Research, pages 862- 889. PMLR, 08 Feb-11 Feb 2020. (Cited on page 9.)
[58] Joel A Tropp et al. An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1-2):1-230, 2015. (Cited on page 34.)
[59] Masatoshi Uehara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline in low-rank mdps. arXiv preprint arXiv:2110004652, 2021. (Cited on page 10.)
[60] Masatoshi Uehara, Xuezhou Zhang, and Wen Sun. Representation Learning for Online and Offline RL in Low-rank MDPs. In International Conference on Learning Representations, 2022. (Cited pages I and 10.)
14

---

[61] Geoffrey Wolfer and Aryeh Kontorovich. Estimating the mixing time of ergodic markov chains. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Secons Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 3120-3159. PMLR, 25-28 Jun 2019. (Cited on page 5.)
[62] Ming Yin and Yu-Xiang Wang. Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogene Homogeneous, Reward-Free and Tank-Agoostic Settings. In Advances in Neural Information Processing Systems, volume 34, pages 12890-12903, Curran Associates, Inc., 2021. (Cited page 10.)
[63] Anru Zhang and Mengdi Wang. Spectral State Compression of Markov Processes. IEEE Transactions on Information Theory, 6665):320--3231, 2020. (Cited on pages 6, 9, 18, 21, 44, 49, and 50.)
[64] 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. (Cited page 10.)
[65] 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 Machine Learning, volume 162 Proceedings of Machine Learning Research, pages 26517-26547. PMLR, 17-23 Jul 2022. (Cited page 10.)
[66] Zihan Zhang, Simon Du, and Xiangyang Ji. Near Optimal Reward-Free Reinforcement Learning. In Proceedings of the 38th International Conference on Machine Leurning, volume 139 of Proceedings of Machine Learning Research, pages 12402-122 12412. PMLR. 18-24 Jul 2021. (Cited on page 8.)
[67] Ziwei Zhu, Xudong Li, Mengdi Wang, and Anru Zhang. Learning markov models via low-rank optimization. Operations Research, 70(4):2384-225) 2022, (Cited on page 9.)
15


Reviews:
[{"review_id": "lQxlO2rfOk", "reviewer": "Reviewer_JAik", "summary": "This paper studies two problems in RL involving low-rank matrix estimation. It provides entry-wise estimation error bounds for simple spectral methods in low-rank bandits and low-rank MDP under different sampling mechanisms. Based on these, it provides performance guarantees for two algorithms designed for low-rank bandit and low-rank MDP respectively. ", "questions": "On Page 7 Line 220, it is assumed that the low-rank bandit has an homogeneous rank-$r$ reward matrix M, while this is not mentioned in the corresponding result Theorem 7. This makes the setting kind of confusing. Can you provide more explanations on this?", "limitations": "This paper does not have potential negative social impact. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper makes contribution towards the estimation of low-rank matrices in the setting of bandits and MDP respectively, as well as how these results can be useful in devising efficient algorithms to make full use of the low-rank structure. \n\nSpecifically, the paper considers the challenging case of low-rank matrix estimation in the presence of dependent noise and provides sharp entry-wise estimation error bounds using involved techniques. This is likely to help the development of algorithms which are better fitted for low-rank settings. ", "weaknesses": "1. Compared with standard matrix completion problem, Model I in this paper extends to the case of dependent noise, but it restricts the magnitude of noise terms $\\xi_t$ to be upper bounded by $c_1\\Vert M\\Vert_{\\infty}$ (see Page 3 Line 91). Therefore, the results here can’t reduce to the state-of-the-art results in matrix completion with independent noise, where the noise level can be orderwise larger than $\\Vert M\\Vert_{\\infty}$ [1]. We suggest the authors to discuss why their condition becomes more stringent when the noise are independent.\n\n2. There are a few typos in the paper. For example:\n\nOn Page 2 Line 71, it would be better to avoid using acronyms list “wlog”. \n\nOn Page 7 Line 224, “where in a first phase” —> “where in the first phase” \n\nOn Page 5 Line 175, “is a small when“\n\n[1] Chen, Yuxin, Yuejie Chi, Jianqing Fan, and Cong Ma. \"Spectral methods for data science: A statistical perspective.\" Foundations and Trends® in Machine Learning 14, no. 5 (2021): 566-806.", "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 below our responses.\n\n*Answer to Weakness 1.*\n\n**A. Relaxing the assumption on the noise upper bound.** We would like to thank you for highlighting this difference between our setting and those for matrices with independent noise (ex. Chen et al. (2021) cited as [14] in our supplementary material) and we think this is an interesting question that should be addressed in the updated version of the paper. However, we would like to stress the following two points:\n\n**A.1** First, the main focus of this paper has been obtaining error bounds with near-optimal scaling with respect to problem dimensions $n,m,T$, and addressing the problem of dependence between different entries of the observation matrix. Hence, in the analysis for Model I, we made a compromise by upper-bounding the standard deviation of the noise by $c \\|\\|M\\|\\|\\_{\\infty}$ for some universal constant $c > 0$ and simplifying the analysis - see Lemma 25 where we define $L = \\max (\\|\\|M\\|\\|\\_{\\infty},\\sigma)$. \n\n**A.2** We agree that state-of-the-art results for matrix recovery with independent noise have weaker assumption for the noise magnitude, but these results are applicable only to models with independent noise. The results we presented should not be reduced to independent setting, but considered as a first step to obtaining matrix recovery guarantees for matrices with dependent entries. \n\n*Answer to Weakness 2 -- Typos.* \n\nThanks a lot for noticing. We will correct these typos.\n\n*Answer to Questions.*\n\n**B. On the setting of Theorem 7.** The assumption of homogeneous rank-$r$ reward matrix $M$ stays valid in the entirety of Section 4 and thus we also assume it when presenting Theorem 7. We will clarify this. Actually, we could remove this assumption, but at the expense of clarity and simplicity of the results. More precisely, to remove the assumption, we just need to use the explicit expressions of the  constants $c_1, C_1$ in the analysis. These constants depend on $\\mu$, $\\kappa$, $r$, $m$, and $n$ as described Line 1093 in Appendix G.  "}, {"review_id": "OFbYUqXQMD", "reviewer": "Reviewer_j7uj", "summary": "This paper provides a theoretical study of low-rank matrix estimation in three contexts: \n\n**Context 1**: in the case of standard matrix estimation with uniformly sampled entries, where the authors prove a sample complexity comparable to approximate recovery results of $\\tilde{O}(m+n)$ (when the rank is $O(1)$), with the following two main differences compared to existing methods: \n\na (makes the result easier). It is assumed the rank is known, and the function class restriction is based directly on an explicit low-rank assumption. \nb (makes the result much harder and stronger). the error is measured with the maximum norm rather than Frobenius norm or expected loss.  \n\nBecause of the general context of the paper which concerns mostly reinforcement learning (see other results below), these results are formulated as a reinforcement learning/bandit problem where the arms are arranged as pairs of integers and the matrix of rewards is assumed to be low-rank. However, note that independence of the noise components is required (cf. lines 689-693 in the supplementary). \n\n**Context 2.1** \n\nIn this model, recovery guarantees are proved for estimating a low-rank transition matrix from observations of independent transitions. Here, the matrix must be square, with the dimension being equal to the number of states. \n\n\n**Context 2.2** \nIn this more natural setting, we estimate the transition matrix from context 2.2 based only on full trajectories. Regret bounds proved in this case rely on the ergodicity of the Markov chain by splitting the expression of the average error over time into sums where the time steps are separated by a large number $\\tau$, so that the distributions of the corresponding observations are approximately independent and distributed as the limiting distribution. \n\n\n\nFinally, the authors introduce a novel algorithm for performing reinforcement learning in a low-rank bandit setting. The algorithm works in epochs: at a given epoch, with each iteration providing a more and more refined estimate of a set of candidate arms. Whilst the set of candidate arms has more than 2 elements, the algorithm recommends a uniformly random arm, after the set of candidate arms degenerates to a single element, the algorithm keeps recommending that one. A bound is shown on the expected amount of time it takes to identify the best arm. This culminates in a gap-independent regret bound of $\\tilde{O}(T^{1/2})$ for this case, which to the best of my knowledge, solves a highly significant open problem in the nascent theory of low-rank bandits. \n\n\n\nThe proofs rely on an ingenious combination of existing ideas, with the most salient one being that of poison approximation: the matrix of observed rewards is approximated by a matrix with entries equal to $M_{i,j}T_i$ where $T_i$s are independent Poisson random variables. (this general technique has previously been introduced in [7)]. Then, concentration inequalities for such matrices are used in combination with bounds on the error in approximating the true matrix of observed rewards by this Poisson approximation. \n\n==========Post-rebuttal=======\n\nMy doubts have been adequately addressed in the rebuttal and I will keep my score of **strong accept**. I remain convinced this is an excellent paper. However, I do hope the authors will take the trouble to add more detailed derivations and also tone down the statements and claims of novelty over the lack of independence of the $E_{i,j}$. Indeed, since this is an impressive contribution that many readers will be interested in studying, it would be a great service to the community to make the paper as approachable as possible. \n\n\n\n========\n\n\n\n**References**\n[1] Nathan Srebro, \"Rank, Trace-Norm and Max-Norm\", COLT 2005.\n\n[2] Ohad Shamir, Shai Shalev-Shwartz. Matrix Completion with the Trace Norm: Learning, Bounding, and Transducing. JMLR 2014.\n\n[3] Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, Yuling Yan. Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization. SIAM journal of Optimization, 2020.\n\n[4] Prateek Jain, Soumyabrata Pal Online Low Rank Matrix Completion. ICLR 2023\n\n[5] Sahand Negahban, Martin J. Wainwright. Restricted Strong Convexity and Weighted Matrix Completion: Optimal Bounds with Noise. JMLR 2012. \n\n[6] Mitzenmacher, Michael and Upfal, Eli. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge UNiversity Press 2017. \n\n[7] Yuxin Chen, Yujie Chi, Jianqing Fan, Cong Ma et al. Spectral Methods for data science: a statistical perspective.", "questions": "**1** Could you clarify what you mean in lines 90 to 92 and lines 125 to 130 regarding the independence of the noise? \nAlthough I can find such an example in the literature, it is seems unlikely to me that this result  (corollary 1) is new. Is there any similar result for matrix completion with the maximum absolute value of the error as the performance measure? Perhaps in [5]? \n\n**2** Could you clarify to what extent theorem 1 and its proof differs from the existing results and proofs from [7] (what is the most similar result to Theorem 1 which was proved in [7])?\n\n**3** ( I would really like to have the answer to this!) In lines 957 to 958, could you explain clearly ho you arrive at the equation on the bottom of page 33? I am a little stuck there, I need far more details than what is written as it seems you are using another equation from the same page without stating it. Also, did you really mean $\\sigma_{2r}(M)$ in the denominator or did you mean $\\sigma_r(M)$ instead (which is the quantity mentioned in the textual explanation on the line above)?\n\n**4** Could you give a few more details in the page 32? It feels the reference to Lemma 4.16  in other work breaks the reader's momentum, it would be nice to write down the lemma again in the paper. Indeed, I think it is a key step in the argument that allows you to obtain this fascinating result with the max norm (theorem 1). \n\n**5** Line 1098, second equation, do you mean $\\ell+2$ instead of $\\ell-2$ in the exponent\n\n\n**6** In the second to last equation on line 1114 (page 42) should it not be $\\lceil  \\log_2(1/\\Delta_{min})\\rceil$ or $\\log_2(e/\\Delta_{min})$ instead of $\\log_2(1/\\Delta_{min})$? Again, I see that you are not being too careful about constants in general but there is no $O$ notation in this particular inequality. \n\n\n**7** In line 90, you say that the entries are sampled \"uniformly at random for simplicity\", do you in fact require this assumption in the proof of the theorem?  (based on existing results for matrix completion with explicit low-rank assumptions, it would seem that this is not required. In general, it would be nice to add a bit more details to each of the theorem statements to clarify the assumptions. \n\n\n**8** Is Lemma 25 known? It seems very general and standard, I feel like it is probably in some well known book. \n\n\n\n\n\n\n\n\n\n\n\n\n**Minor comments/typos**\n\nA citation would be nice on lines 226-227\n\nIt could be nice to reorganize sections C1 and C2.2 a little bit. For instance, in line 707, you are using a lemma which comes from a subsection that concerns the Markov problem  when proving a result about Model 1, it would be nice to make it clear that Lemma 22 doesn't, in fact, require any proof elements from the context of Model 2. \n\nIn the same vein, I think it would be nice, for completeness, to write down the proof of Lemma 22, even if it is very similar to the proof of Theorem 5.7 in [6]. It is a bit funny that the proof of Lemma 21 is there but not that of Lemma 22 since Lemma 21 is pretty much trivial whilst Lemma 22 is a bit more advanced. Making the paper fully self contained would be a nice way to get even more citations by further improving the encylopaedic quality of the appendix. \n\n\n\nLine 1098 (page 41), second equation, I think you mean $4e$ not $2\\sqrt{e}$, though I understand you are not being too bothered about constants given the final results are in $O$ notation\n\n\nIn the last inequality of the sequence of inequalities on page 43, and in line 1124 I think it would be nice to remind the reader of the definition of $\\bar{\\Delta}$ from line 239, since it is instrumental in deriving the equality on line 1124, which unfortunately relies on the fact that the recommendations are uniformly at random in $[m]\\times [n]$ instead of the more natural $\\mathcal{A}_{\\ell}$.\n\n\n\nTypos: \n\nLine 951: missing \"the\" \n\nLine 706: extra square bracket  inside the equation.\n\nIn line 727, I recommend adding more details for ho you prove that $\\tau(\\epsilon)\\leq \\tau$, it takes quite a bit of massaging of previous equations to get this with the correct constant!\n\nLine 741: be joint probability==> be the joint probability \n\nline 742 \"for Poisson and multinomial model ==> \"for the Poisson and multinomial models\"\n\nline 793 (proof of Lemma 25): \"variables\" ==> \"variable\" \n\nline 957 add \"following\" before \"condition\n\nLine 980, Model\\ref{10} should probably be Model\\eqref{10}\n\nline 1097  (page 41) You say \" in order for the above guarantee to hold we require the following two conditions to hold. I think that is not technically true: the conditions below are what is needed to apply the specific previously established results, so technically those are sufficient rather than necessary conditions. \n\n\nLine 1114 (page 42):  I think there was an error with copy and paste: \"rounds\" should be after $\\tau$ and before the first, not the second comma of the line. \n\nIn the first equality after line 1122, using \\left and \\right might be nicer. \n\n\n[1] Nathan Srebro, \"Rank, Trace-Norm and Max-Norm\", COLT 2005.\n\n[2] Ohad Shamir, Shai Shalev-Shwartz. Matrix Completion with the Trace Norm: Learning, Bounding, and Transducing. JMLR 2014.\n\n[3] Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, Yuling Yan. Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization. SIAM journal of Optimization, 2020.\n\n[4] Prateek Jain, Soumyabrata Pal Online Low Rank Matrix Completion. ICLR 2023\n\n[5] Sahand Negahban, Martin J. Wainwright. Restricted Strong Convexity and Weighted Matrix Completion: Optimal Bounds with Noise. JMLR 2012. \n\n[6] Mitzenmacher, Michael and Upfal, Eli. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge UNiversity Press 2017. \n\n[7] Yuxin Chen, Yujie Chi, Jianqing Fan, Cong Ma et al. Spectral Methods for data science: a statistical perspective.", "limitations": "See \"weaknesses\", especially Weakness 3. In addition, it seems that the algorithm is a little unnatural in that it doesn't use the successive estimates of the set of candidate arms and merely recommends uniformly random entries amongst all arms until it is confident it has identified the best arm overall. It would be interesting to see if it is possible to prove similar guarantees for the algorithm which recommends a random arm in the set $\\mathcal{A}_{\\ell}$ instead of ($\\mathcal{A}_1=[m]\\times [n]$) at each time step $\\ell$.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "**1** This is an excellent contribution to the field: although I am not completely sure about the originality (especially that of theorem  1 as compared to other results in [5]) since I am not fully up to speed on the reinforcement learning theory, I think there is a good chance this is groundbreaking work. The algorithm of successive arm elimination is simple and elegant, with a nearly optimal regret bound. Whilst it is true that the fact that explicit rank restriction is used (as opposed to, for instance, nuclear norm regularization) makes the matrix completion results seem a little trivial, the regret bound in the RL setting seems to be new and is a natural starting point to kick-start this branch of research. \n\n\n**2** Aside from very minor things (mostly related to the contextualization of the work within the related works), this paper is excellently written. The proofs are very well organized, to an extent which is demonstrably superior to the majority of accepted papers I have reviewed.    The authors clearly organize the proof into steps (Poisson approximation, dilation trick, general concentration inequalities for Poisson matrices, specific calculations for the Poisson approximation to this problem, bounds on the error introduced by the approximation). Each parts of the proofs contain references to existing literature where relevant.", "weaknesses": "**1** One thing that threw me off a bit was the lack of contextualization and explanation of the first results (Theorem 1). In particular, on lines 90 to 92 (see also lines 125 to 130), it seems like the authors want to distance their results from standard matrix completion results by hinting that noise components are not independent (they are not stated to be independent at that point), when in fact it also seems this setting is exactly matrix completion with an explicit rank restriction. Indeed,  lines 689-693 in the supplementary appear to suggest independence **is** required. It would be quite appropriate to compare to existing results in this case as well. For a bounded loss, a similar sample complexity goes all the way back to [1] for approximate recovery with a bounded loss. For connected problems with the trace norm, we also have the result of [2] and the extremely impressive result of [3], which is much stronger than the results presented here due to improved dependence on the variance of the noise. \n\nSimilarly, I am also a bit confused by the statement on line 334 that \"we do not assume the transition matrices are constructed based on a given restricted class of functions\" since it appears there is a low rank assumption in the work. \n\n**2**  Similarly, I feel like the related works on low-rank bandits missed some of the recent literature [4]. \n\n**3** In the low rank bandit result, the algorithm eventually recommends the same arm, that is, the same entry, all the time. This is highly restrictive in a recommender systems context: the algorithm isn't even able to identify the best item for each user, only the best user-item combination...\n\n\n\n\n\n\n\n**References**\n[1] Nathan Srebro, \"Rank, Trace-Norm and Max-Norm\", COLT 2005.\n\n[2] Ohad Shamir, Shai Shalev-Shwartz. Matrix Completion with the Trace Norm: Learning, Bounding, and Transducing. JMLR 2014.\n\n[3] Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, Yuling Yan. Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization. SIAM journal of Optimization, 2020.\n\n[4] Prateek Jain, Soumyabrata Pal Online Low Rank Matrix Completion. ICLR 2023\n\n[5] Sahand Negahban, Martin J. Wainwright. Restricted Strong Convexity and Weighted Matrix Completion: Optimal Bounds with Noise. JMLR 2012. \n\n[6] Mitzenmacher, Michael and Upfal, Eli. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge UNiversity Press 2017. \n\n[7] Yuxin Chen, Yujie Chi, Jianqing Fan, Cong Ma et al. Spectral Methods for data science: a statistical perspective.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful review and very positive feedback. \n\n**A. Answer to Weakness 1 \\& Question 1.** Thanks for mentioning these papers; we will cite them. We clarify below the differences between these papers and our contributions for Model I. \n\n**A.1.** [1, 2, 5] (see the refs in your review) do not provide entry-wise guarantees for the problem of matrix estimation with low-rank constraint under any noise assumptions. \n\n**A.2.** [3] provides entry-wise guarantees for a nuclear norm penalized estimator. [7] surveys entry-wise guarantees for spectral methods. The data model considered in these references is the matrix plus noise model, i.e., $M + E$, where the noise matrix, $E$, has independent entries. The setting we describe in Model I is different: if we write it in the form of a matrix plus noise model, we obtain that the noise matrix $E$ can be expressed as \n    $$\\forall (i,j)\\in [n]\\times [m], \\quad  E\\_{i,j} =\\widetilde{M}\\_{i,j}-M\\_{i,j} = \\left(\\frac{nm}{T}\\sum\\_{t=1}^T (M\\_{i_t, j_t} + \\xi\\_t) 1\\_{\\lbrace (i_t, j_t)=(i,j)\\rbrace}\\right)-M\\_{i,j}$$\nwhere we use the expression of $\\widetilde{M}$ provided in eq. (10) in Appendix C.1. From this, we clearly see that the entries of $E$ are not independent. Therefore, the entry-wise guarantees of [3, 7] do not apply in our setting. In fact, the leave-one-out argument relies heavily on the independence of the noise entries. \n\n**A.3.** In [4], the authors have a model where $m$ entries are observed per round, whereas in Model I, we observe one entry only. In addition, to obtain entry-wise guarantees, they resort to a couple of algorithmic tricks, explained in Remarks 2, 3, and 4 of [4]. In contrast, we show that simpler spectral methods enjoy entry-wise guarantees without any additional tricks. \n\n**B. Answer to Weakness 2 -- Regarding [4].** We actually cited this work in the related work (ref. [25] in our supplementary material), but only discussed it in Appendix H.2. We will discuss it further in the main part of the paper.\n\n**C. Answer to Weakness 3.** Indeed, our algorithm eventually recommends the same (but provably optimal) arm/matrix entry. When devising SME-AE, we had the applications mentioned in the introduction of Bayati et al. [6] (ref. in our supplementary material), where recommending the same arm is not a problem. This could become a problem in other types of recommender systems. We believe that our approach can be extended to these systems.\n\n**D. Answer to Question 2.** The results in [7] that are the closest to our Theorem 1 are Theorems 4.2 and 4.5 (Chapter 4). However, they are not really comparable to our results. Indeed:\n\n**D.1.** In [7], the results for entry-wise guarantees are for a matrix plus noise model with independent entries -- see our answer A.2. to Weakness 1 for details. In our setting, the leave-one-out argument of [7] breaks. Our proof of Theorem 1 introduces new techniques such as the Poisson approximation, needed to deal with dependencies in the noise model.\n\n**D.2.** The leave-one-out argument in [7] is only valid when the entries are sub-Gaussian. For our purposes, the observed matrix has entries distributed as Compound Poisson r.v.. Hence, we had to use different concentration inequalities than those of [7]. In particular, we needed a Truncated version of matrix Bernstein inequality (see Proposition 27 and Lemma 29 in App. D). \n\n**D.3.** Finally, the results in [7] only focus on how the guarantees scale with matrix dimensions $n$ and $m$. In addition, we care about how they scale with the confidence level $\\delta \\in (0,1)$, and the number observations $T$. Tracking these dependencies is not trivial.\n\n**E. Answer to Question 3.** Thank you bringing this to our attention. We will detail this part in our manuscript. In the meanwhile, we clarify below the key steps leading to the equations lines 957 to 958. First, we wish to disclose a typo in the definition of $\\widetilde{S}^{\\ell}$. The correct definition is:\n$$\\forall i,j \\in [n+m], \\qquad  \\widetilde{S}^{(\\ell)}\\_{i,j} = \\begin{cases} \\widetilde{S}\\_{i,j} & \\text{if } i \\neq \\ell \\text{ or }  j \\neq \\ell \\\\\\\\ S\\_{i,j} & \\text{otherwise}\\end{cases}$$\nWe can first establish $$\\Vert\\widehat{Q}W_{\\widehat{Q}}-\\widehat{Q}^{(\\ell)} W_{\\widehat{Q}^{(\\ell)}} \\Vert_F\\le\\Vert\\widehat{Q}\\widehat{Q}^\\top -  (\\widehat{Q}^{(\\ell)})(\\widehat{Q}^{(\\ell)})^\\top\\Vert_F\\le\\frac{4\\Vert(\\widetilde{S}-\\widetilde{S}^{(\\ell)})\\widehat{Q}^{(\\ell)}\\Vert_F}{\\sigma_{2r}(S)}$$\nwhere the first inequality follows by definition of $W$ and the second follows from Davis-Kahan's inequality. Next, we have  \n$$\\Vert(\\widetilde{S}-\\widetilde{S}^{(\\ell)})\\widehat{Q}^{(\\ell)}\\Vert_F\\le\\Vert E_{\\ell,:}\\widehat{Q}^{(\\ell)}\\Vert_2+2\\Vert E\\Vert\\Vert \\widehat{Q} W_{\\widehat{Q}}\\Vert_{2\\to\\infty}+2\\Vert E\\Vert\\Vert\\widehat{Q}W_{\\widehat{Q}}-\\widehat{Q}^{(\\ell)}W_{\\widehat{Q}^{(\\ell)}}\\Vert_{2\\to\\infty}$$\nwhere the inequality follows by definition of $\\widetilde{S}^{(\\ell)}$ and a couple of triangular inequalities and norm definitions. From the inequalities above and with the assumption that $\\Vert E\\Vert\\le 16\\sigma_r(M)=16\\sigma_{2r}(S)$, we recover the inequality in lines 957 to 958. Moreover, yes, it should be $\\sigma_r(M) $ (or $\\sigma_{2r}(S)$) in the inequality.\n\n**F. Answers to Questions 4 to 8.** Thank you for the many suggestions and thorough reading of our manuscript. We will add Lemma 4.16 for completeness instead of simply citing it. Yes, in line 1098,  $\\ell - 2$ should be instead $\\ell + 2$. In line 1114, $\\log_2(1/\\Delta_{\\min})$ in the fourth inequality should be instead $\\lceil \\log_2(1/\\Delta_{\\min}) \\rceil $ which we bound later by $\\log_2(e/\\Delta_{\\min})$. Regarding sampling uniformly at random, we can relax this at the expense of technical clarity and presentation simplicity. We will provide more details for our theorems to further clarify their assumptions. Regarding Lemma 25, we ended up proving it because we couldn't find a similar result in the literature."}, {"review_id": "LzigYvvtTI", "reviewer": "Reviewer_zbTi", "summary": "The authors investigate matrix estimation in reinforcement learning and bandit settings with low-rank structures. They demonstrate the effectiveness of spectral-based methods in recovering matrix subspaces and minimizing entry-wise error. This enables the development of efficient RL algorithms tailored for low-rank bandits and Markov Decision Processes (MDPs).\n\nThis paper is solid, supported by robust results and technically intriguing proofs. It builds upon the recent trend of examining entry-wise error bounds for matrix completion problems and extends it to dynamic settings like RL and bandits. While the guarantees may not be surprising and the algorithms largely follow an explore-and-commit approach, the authors introduce an interesting technique using Compound Poisson Noise to transform a non-i.i.d. problem into an i.i.d. problem, which may have a larger implication for other applications. \n\n", "questions": "How is the result for matrix completion with Poisson noise in this paper related to \"Near-optimal entrywise anomaly detection for low-rank matrices with sub-exponential noise.\" In International Conference on Machine Learning, pp. 3154-3163. PMLR, 2021?", "limitations": "I do not perceive any immediate potential negative social impact.\n\n\n\n\n", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- Theoretical Soundness\n- Compound Poisson Noise Reduction for MDP is interesting\n- Exploring the potential of entry-wise guarantees of matrix completion in a dynamic setting is in general interesting", "weaknesses": "While acknowledging the efforts invested in developing the theory, the novelty of the research appears limited given the well-established techniques of entry-wise recovery and leave-one-out. Moreover, the current algorithms are constrained to explore-and-commit and (pseudo) i.i.d. sampling schemas, compared to adaptive algorithms such as UCB, due to the limitations of the theoretical guarantees.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful review, and constructive feedback! We address your comments below.  \n\n\n*Response to Weaknesses*\n\n**A. About the novelty of our analysis and of our algorithms.**\n\n**A.1.** As far as we are aware, the leave-one-out argument has been so far limited to a matrix plus noise model with independent noise entries. We feel that extending it to dependent noise entries was non-trivial. Notably, we establish entry-wise matrix estimation guarantees under Markovian noise structures (see our results for Model II in Section 3.3. and Appendix B.3)\n\n**A.2.** Note that our algorithm for the low-rank bandit problem is adaptive because it uses an adaptive stopping rule to end the exploration phase (this contrasts with naive Explore-Then-Commit (ETC) algorithms). We actually explain at the beginning of Section 4 that a naive ETC algorithm would lead to poor regret guarantees. Our algorithm remains simple, yet it achieves the best regret guarantees obtained so far. \n\n*Response to Questions*\n\n**B. Comparison with Farias et al., \"Near-optimal entrywise anomaly detection for low-rank matrices with sub-exponential noise\", ICML 2021.** Thank you for pointing us to this relevant paper, referred to as [0] below. We will cite it and discuss its results in the revised version of our manuscript. [0] provides entry-wise matrix estimation guarantees for random matrices with entries that are independent (see Theorem 2 in [0]). In contrast, we provide entry-wise matrix estimation guarantees for matrices with dependent entries (See our Theorems 1, 2 and 3). Both [0] and our submission rely on the leave-one-out argument for random matrices with sub-exponential entries. In our case, we use this argument as a sub-step of our analysis after performing the Poisson approximation. However, we believe that, as explained below, our final results are richer, more precise and actually needed for our RL applications.\n\n**B.1.** We provide guarantees on subspace recovery in $\\Vert \\cdot \\Vert_{2\\to \\infty}$ (See (i) Theorem 1, 2, and 3) and guarantees in $\\Vert \\cdot \\Vert_{1\\to \\infty}$ (see Theorem 2, and 3). This type of guarantees are not provided in [0]. The subspace recovery guarantees are useful as a sub-step of our analysis and we believe they are of independent interest. The guarantees in $\\Vert \\cdot \\Vert_{1\\to \\infty}$ are useful in reward-free RL.\n\n**B.2.** The entry-wise guarantees of [0] are only expressed in terms of the matrix dimensions $n$ and $m$, while our guarantees exhibit a dependence on the number of observations $T$, the dimensions $n$ and $m$, and the confidence level $\\delta$. Having guarantees with an explicit dependence for all  $T \\ge 1$ and $\\delta \\in (0,1)$ is crucial in the design of our algorithm for low-rank bandits. \n\n**B.3.** At a more technical level, we cannot apply the proof of Theorem 2 from [0] to our setting unless the number of samples $T = \\Omega(n\\sqrt{n})$ in the homogeneous case, a far larger number compared to $T=\\Omega( n\\log n)$ in our setting. The authors of [0] require this condition in order to apply a well-known leave-one-out theorem (Lemma 6 in [0]) which requires $32 \\kappa \\max(\\gamma,\\phi(\\gamma))\\leq 1 $ where $\\gamma$ and $\\phi(\\cdot)$ are quantities defined in the proof of Proposition 2 in [0]. Applied to our setting, this condition can be rewritten as $\\sqrt{n \\log (n)}(T\\Vert M \\Vert_{\\infty} + 1)\\kappa^2 \\leq C T\\Vert M \\Vert_2$ (see the second assumption in Proposition 2 in [0]). In particular, for the homogeneous case, this condition requires $T = \\Omega(n\\sqrt{n})$ as mentioned above. Moreover, our proof uses tighter results (such as application of Bennett's inequality in our Lemma 29) which enables us to achieve very tight bounds (even at logarithmic scale). "}, {"review_id": "UxU4xHUbFs", "reviewer": "Reviewer_N4Ue", "summary": "This paper presents a detailed analysis of matrix estimation problems in low-rank bandit and low-rank RL scenarios. The authors investigate the effectiveness of spectral-based matrix estimation methods and demonstrate their ability to accurately recover the singular subspaces of the matrix with minimal entry-wise error. Building upon these findings, the paper introduces a regret minimization algorithm for low-rank bandit problems and a best policy identification algorithm for reward-free RL in low-rank MDPs.", "questions": "1. Could you elaborate on how deriving the entry-wise error of low-rank matrix estimation is justified in bandit and RL settings, providing detailed explanations and extensive numerical experiments?\n\n2. In the discussion of related work, it is crucial to compare the paper's results with state-of-the-art approaches and provide a fair and objective analysis.\n\n", "limitations": "No numerical experiments were provided.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper tackles the challenging task of deriving the entry-wise error of low-rank matrix estimation, specifically focusing on the correlated noise case. This analysis extends existing results and enables the study of bandit and RL settings. The techniques employed, such as leave-one-out arguments and Poisson approximation, demonstrate technical prowess.\n\n2. Despite being a theoretical paper, the writing is clear and easy to comprehend, enhancing its accessibility.\n\n", "weaknesses": "1. The paper fails to address the necessity of deriving entry-wise error in low-rank matrix estimation for bandit and RL settings. In the context of low-rank bandit problems, the primary objective is to identify the best entry, such as the largest value, in the matrix as quickly as possible. Consequently, the emphasis should be on selecting the arm with the highest reward, rather than achieving a small entry-wise error for the entire matrix. Entries with very small values do not necessitate extensive exploration. Thus, caring about entry-wise error may lead to unnecessary over-exploration, which is not desirable in low-rank bandit or low-rank MDP settings.\n\n\n2. In low-rank bandit and MDP scenarios, the focus should primarily be on minimizing regret. Several existing approaches have achieved minimax regret bounds in these settings. For instance, Kang et al. (2022) addressed a more general low-rank matrix bandit problem and proved a minimax regret of $O((n+m)\\sqrt{T})$. Jain and Pal (2023) also considered a similar low-rank matrix bandit problem and used a similar entry-wise matrix estimation result to achieve a regret bound of $polylog(n+m)\\sqrt{T}$ for the rank-1 case. Unfortunately, the paper only discusses sub-optimal approaches in the main body, while the superior results of these references are mentioned in the last section of the supplementary materials.\n\n\n3. The lack of numerical experiments to evaluate the proposed regret minimization algorithm and compare it against benchmark methods in the literature is a notable drawback. Merely comparing regret upper bounds does not provide a comprehensive understanding of the algorithms' actual performance. It would be more convincing to include extensive numerical experiments that directly compare the regret achieved by different algorithms, thereby justifying the usefulness of deriving entry-wise error of low-rank matrix estimation in bandit and RL settings.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback and insightful review! Please find below our responses.\n\n*Answer to Weakness 1 and Question 1*\n\n**A. Necessity of entry-wise guarantees in low-rank bandits and RL.**  Thank you for bringing this point to our attention. Indeed, we did not explicitly motivate the need for entry-wise matrix estimation guarantees in low-rank bandits and RL. We will revise our manuscript accordingly. Below, we argue why entry-wise guarantees in low rank bandits and RL are useful. \n\n**A.1.** The need for entry-wise matrix estimation guarantees arises naturally in our analysis. In low-rank bandits, in order to obtain logarithmic regret bounds, we need control of the estimated gaps. This in turn requires entry-wise guarantees (see Appendix G.1 - Line 1090). In reward-free RL, in order to obtain PAC-bounds, we need to control the value difference error. This in turn requires control of matrix estimation errors in the norm $\\Vert \\cdot \\Vert_{1 \\to \\infty}$ (see Lemma 12, Appendix A.3). Controlling this error is akin to controlling the entry-wise error in terms of analysis (see Appendix F). \n  \n**A.2.**  Existing work on low-rank bandits showcases regret analysis that do not use entry-wise guarantees. However, these guarantees are only minimax while ours are gap-dependent, exhibit logarithmic scaling in the time horizon and even enjoy better minimax guarantees in some scenarios. Indeed, the work of Jun et al. (2019) (cited as [29] in our supplementary material) proposes a clever algorithm with a minimax regret guarantee scaling as $\\tilde{O}((m+n)^{3/2} \\sqrt{T})$. Their regret decomposition (Corollary 1 in [29]) suggests that both entry-wise guarantees and guarantees in Frobeinus norm yield the same results. The follow-up work of Kang et al. (2022) (cited as [32]) proposes an algorithm leveraging a novel estimator and attaining an improved minimax regret guarantees of order $\\tilde{O}((m+n)\\sqrt{T})$. In contrast, our work complements and, in some aspects, improves upon these results: **(i)** our analysis allows us to obtain logarithmic regret bounds which are gap-dependent $\\tilde{O}((m+n)(\\bar{\\Delta}/\\Delta_{\\min}^2) \\log^3(T))$. Both [29] and [32] do not provide gap-dependent guarantees with logarithmic regret; **(ii)** under the assumption that $\\Delta_{\\max}/\\Delta_{\\min} \\le \\xi$, our algorithm, SME-AE, achieves a minimax regret bound scaling as $\\xi \\sqrt{(m+n)T}\\log(T)^2$. This is a better minimax guarantee than the ones presented in [29] and [32]; **(iii)** we also perform best-entry identification with provable guarantees (see Theorem 7). This problem remains at large under-explored.\n    \n**A.3.** Existing work has also noted the importance and need of entry-wise guarantees but with limited success. Please refer the works of Bayati et al. (2022), Jain and Pal (2023), and  Shah et al. (2020) (cited as [7], [25], and [48], respectively, and discussed in Section 6 and Appendix H.2). [7] is the closest to our setting. There, they use a row enhancement procedure to obtain a matrix estimation guarantee in the norm $\\Vert \\cdot \\Vert_{2\\to \\infty}$ (see Proposition 1 in [7]). They implicitly assume that one of the dimensions, say $m$ for example, is $\\Theta(1)$ (see Assumption 1 and the discussion before it in [7]), thus making their guarantee equivalent to an entry-wise guarantee. Hence, their regret bounds (e.g., see Theorem 1 in [7]) may suffer an extra dependence on $\\sqrt{m}$ while ours do not.\n    \nPlease note that we do not claim that entry-wise guarantees are absolutely needed but we don't see how to obtain our guarantees without.\n\n**B. Exploration in low-rank bandits and RL and entry-wise guarantees.**  The reviewer raises an exciting question which is that of optimal exploration under low rank structure. Unfortunately, this question is at large still open. Note however that our approach based on entry-wise guarantees already allows us to considerably trim the exploration process. Indeed, our algorithm, SME-AE, achieves a gap-dependent regret bounds of order $\\widetilde{O}((m+n) (\\bar{\\Delta}/\\Delta_{\\min}) \\log^3(T))$, thus showing that we do not scale with the number of arms $nm$. Also note that our algorithm, SME-AE, does not perform matrix estimation up to an arbitrary small entry-wise error but only up to the minimal gap $\\Delta_{\\min}$ which is necessary to obtain logarithmic regret.\n\n*Answer to Weakness 2 and Question 2.* \n\n**C. PAC guarantees in low-rank bandits and RL.** The reviewer commented  \"In low-rank bandit and MDP scenarios, the focus should primarily be on minimizing regret.\" We believe that the problem of pure exploration in low-rank bandits and RL (a.k.a. PAC-RL) is also important. In low rank bandits, we have in fact also provided regret guarantees in addition to guarantees on best-entry identification. We believe this is a strength of our work rather than a weakness. \n\n**D. On related work.** First, we wish to clarify that we ended up putting the work of Kang et al. (2022) (cited as [32]) and Jain and Pal (2023) (cited as [25]) in Appendix H simply because we didn't have enough space in the main body. Moreover, we clearly stated in the main body (see line 318) that further details are provided on the related work (including [25] and [32]) in Appendix H. However, we understand the reviewer's sentiment that all relevant work should be mentioned in the main, especially those with state-of-the-art results. We thank the reviewer for bringing this to our attention and we will revise our manuscript accordingly. \n \n*Answer to Weakness 3.*\n\n**E. Experimental results.** We think that our theoretical contributions are numerous (matrix estimation under correlated noise and entry-wise guarantees + algorithms with better performance guarantees in low-rank bandits and RL). But, we agree that adding numerical experiments would nicely complement our theoretical findings. We intend to include experiments when revising our paper.  "}]

Author rebuttal:

Meta-review: In this paper, the authors studied the effectiveness of spectral methods for two problems in reinforcement learning: low-rank bandits and low-rank MDP under different sampling mechanisms. Sharp entrywise estimation error bounds have been developed despite the presence of dependent noise. While entrywise statistical analysis has been widely conducted in the statistics literature, it was previously rarely available in the RL literature.  As one reviewer pointed out, it would be great if the authors could extend their theory to accommodate an enlarged range of noise levels.  A more detailed discussion about the necessity of deriving entrywise estimation bounds in these two RL contexts would also strengthen the paper.
Decision: Accept (poster)